{"id":{"repo_id":"freiburg-diss","oai_identifier":"oai:freidok.uni-freiburg.de:2349"},"canonical_url":"https://search.dev.ndltd.org/etd/freiburg-diss/oai:freidok.uni-freiburg.de:2349","repository":{"repo_id":"freiburg-diss","name":"University of Freiburg","base_url":"https://freidok.uni-freiburg.de/oai/oai2.php"},"display":{"title":"Online packet buffering","abstract":"This thesis treats several buffering problems that occur in routers or switches of computer networks. We develop and investigate algorithms for temporary data packet buffering, where information about the packets is not completely known in advance, but arrives by and by over time. In the classical approach of designing algorithms, all data are assumed to be known in advance. However, in practical applications, this assumption often does not hold. It may happen that decisions on a process must be made although information about this process is still incomplete. For such scenarios, online algorithms, which are able to make decisions without complete knowledge on the input, are used. A well-known example of an online problem is makespan minimization in job scheduling.
In order to measure how well it copes with the difficulty of incomplete knowledge about the input, we compare an online algorithm to an optimal offline algorithm that knows the whole input sequence in advance. In a competitive analysis, we determine the competitive ratio of the online algorithm, which is defined to be the asymptotic worst case ratio between the profit of the
optimal offline algorithm and the profit of the online algorithm, where if the online algorithm is randomized, i.e. if it makes random decisions, the expected profit of the online algorithm is considered.
In computer networks, data is nowadays interchanged between several computers by means of data packets where the data packets are forwarded by routers on their way from their origin computer to their destination computer. Since data traffic
may be bursty and packet loss is wished to be kept small, routers are equipped with buffers where packets can be stored temporarily. In this thesis, we first investigate routers having several input and output ports. The packets arriving at the input ports are to be transmitted via the output ports, where the forwarding of each packet results in the same profit. Then, we consider routers at which the transmission of different packets may result in different profits where we are only paid if the packet is forwarded within a given deadline. The puffers in the routers are of bounded capacity. We consider different scenarios in each of which the goal is to forward as many packets as possible.
In the case of several input and output ports, each output port is equipped with a distinct buffer for the different input ports. At each time step, an arbitrary number of packets arrive. They are appended to the buffers if space permits. At each output port, only one packet from the buffers assigned can be transmitted.
We investigate deterministic online algorithms for the multiqueue problem and derive lower bounds for greedy and other deterministic algorithms. Moreover, we show that a modified (semi-)greedy algorithm has a better competitive ratio than the greedy algorithm itself and analyze the performance of online algorithms that are granted more resources than the optimal offline algorithm they are compared to. We consider resource augmentation with respect to memory and speed.
Eventually, we present an optimal offline algorithm with a linear running time.
The analysis of randomized online algorithms for the multiqueue buffering problem starts by discussing a randomized lower bound for arbitrary buffer sizes. We then show how to generalize algorithms for unit buffers, which can store only one packet per queue, to arbitrary buffers without increasing their competitive ratio. First, we investigate an online algorithm that tosses a multisided coin in every time step, whereas, therafter, we consider a randomized online algorithm that makes all random decisions in advance and then acts like a deterministic algorithm.
Finally, we discuss the bounded delay buffering problem for weighted packets in a single queue. After deducing a randomized lower bound, we investigate two different greedy algorithms and show that their competitive ratios differ.
Eventually, we consider the special case that there are only two packet values and present both lower and upper bounds.","abstract_html":"This thesis treats several buffering problems that occur in routers or switches of computer networks. We develop and investigate algorithms for temporary data packet buffering, where information about the packets is not completely known in advance, but arrives by and by over time. In the classical approach of designing algorithms, all data are assumed to be known in advance. However, in practical applications, this assumption often does not hold. It may happen that decisions on a process must be made although information about this process is still incomplete. For such scenarios, online algorithms, which are able to make decisions without complete knowledge on the input, are used. A well-known example of an online problem is makespan minimization in job scheduling. <br> <br>In order to measure how well it copes with the difficulty of incomplete knowledge about the input, we compare an online algorithm to an optimal offline algorithm that knows the whole input sequence in advance. In a competitive analysis, we determine the competitive ratio of the online algorithm, which is defined to be the asymptotic worst case ratio between the profit of the <br>optimal offline algorithm and the profit of the online algorithm, where if the online algorithm is randomized, i.e. if it makes random decisions, the expected profit of the online algorithm is considered. <br> <br>In computer networks, data is nowadays interchanged between several computers by means of data packets where the data packets are forwarded by routers on their way from their origin computer to their destination computer. Since data traffic <br> may be bursty and packet loss is wished to be kept small, routers are equipped with buffers where packets can be stored temporarily. In this thesis, we first investigate routers having several input and output ports. The packets arriving at the input ports are to be transmitted via the output ports, where the forwarding of each packet results in the same profit. Then, we consider routers at which the transmission of different packets may result in different profits where we are only paid if the packet is forwarded within a given deadline. The puffers in the routers are of bounded capacity. We consider different scenarios in each of which the goal is to forward as many packets as possible. <br> <br>In the case of several input and output ports, each output port is equipped with a distinct buffer for the different input ports. At each time step, an arbitrary number of packets arrive. They are appended to the buffers if space permits. At each output port, only one packet from the buffers assigned can be transmitted. <br> <br>We investigate deterministic online algorithms for the multiqueue problem and derive lower bounds for greedy and other deterministic algorithms. Moreover, we show that a modified (semi-)greedy algorithm has a better competitive ratio than the greedy algorithm itself and analyze the performance of online algorithms that are granted more resources than the optimal offline algorithm they are compared to. We consider resource augmentation with respect to memory and speed. <br>Eventually, we present an optimal offline algorithm with a linear running time. <br> <br>The analysis of randomized online algorithms for the multiqueue buffering problem starts by discussing a randomized lower bound for arbitrary buffer sizes. We then show how to generalize algorithms for unit buffers, which can store only one packet per queue, to arbitrary buffers without increasing their competitive ratio. First, we investigate an online algorithm that tosses a multisided coin in every time step, whereas, therafter, we consider a randomized online algorithm that makes all random decisions in advance and then acts like a deterministic algorithm. <br> <br>Finally, we discuss the bounded delay buffering problem for weighted packets in a single queue. After deducing a randomized lower bound, we investigate two different greedy algorithms and show that their competitive ratios differ. <br>Eventually, we consider the special case that there are only two packet values and present both lower and upper bounds.","abstract_has_math":false,"creators":["Schmidt, Markus"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Albers, Susanne"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-07-24T02:22:46Z","subjects":["Kompetitive Analyse","Kompetitiver Faktor","Paketpufferung","Paketvermittlung","Competitive analysis","Competitive ratio","Packet buffering"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://freidok.uni-freiburg.de/data/2349","outbound_label":"Repository record","outbound_source":"source_url"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Albers, Susanne"]},{"key":"dc:creator","label":"Author","values":["Schmidt, Markus"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:type","label":"Dc Type","values":["DoctoralThesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Kompetitive Analyse","Kompetitiver Faktor","Paketpufferung","Paketvermittlung","Competitive analysis","Competitive ratio","Packet buffering"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["This thesis treats several buffering problems that occur in routers or switches of computer networks. We develop and investigate algorithms for temporary data packet buffering, where information about the packets is not completely known in advance, but arrives by and by over time. In the classical approach of designing algorithms, all data are assumed to be known in advance. However, in practical applications, this assumption often does not hold. It may happen that decisions on a process must be made although information about this process is still incomplete. For such scenarios, online algorithms, which are able to make decisions without complete knowledge on the input, are used. A well-known example of an online problem is makespan minimization in job scheduling.
In order to measure how well it copes with the difficulty of incomplete knowledge about the input, we compare an online algorithm to an optimal offline algorithm that knows the whole input sequence in advance. In a competitive analysis, we determine the competitive ratio of the online algorithm, which is defined to be the asymptotic worst case ratio between the profit of the
optimal offline algorithm and the profit of the online algorithm, where if the online algorithm is randomized, i.e. if it makes random decisions, the expected profit of the online algorithm is considered.
In computer networks, data is nowadays interchanged between several computers by means of data packets where the data packets are forwarded by routers on their way from their origin computer to their destination computer. Since data traffic
may be bursty and packet loss is wished to be kept small, routers are equipped with buffers where packets can be stored temporarily. In this thesis, we first investigate routers having several input and output ports. The packets arriving at the input ports are to be transmitted via the output ports, where the forwarding of each packet results in the same profit. Then, we consider routers at which the transmission of different packets may result in different profits where we are only paid if the packet is forwarded within a given deadline. The puffers in the routers are of bounded capacity. We consider different scenarios in each of which the goal is to forward as many packets as possible.
In the case of several input and output ports, each output port is equipped with a distinct buffer for the different input ports. At each time step, an arbitrary number of packets arrive. They are appended to the buffers if space permits. At each output port, only one packet from the buffers assigned can be transmitted.
We investigate deterministic online algorithms for the multiqueue problem and derive lower bounds for greedy and other deterministic algorithms. Moreover, we show that a modified (semi-)greedy algorithm has a better competitive ratio than the greedy algorithm itself and analyze the performance of online algorithms that are granted more resources than the optimal offline algorithm they are compared to. We consider resource augmentation with respect to memory and speed.
Eventually, we present an optimal offline algorithm with a linear running time.
The analysis of randomized online algorithms for the multiqueue buffering problem starts by discussing a randomized lower bound for arbitrary buffer sizes. We then show how to generalize algorithms for unit buffers, which can store only one packet per queue, to arbitrary buffers without increasing their competitive ratio. First, we investigate an online algorithm that tosses a multisided coin in every time step, whereas, therafter, we consider a randomized online algorithm that makes all random decisions in advance and then acts like a deterministic algorithm.
Finally, we discuss the bounded delay buffering problem for weighted packets in a single queue. After deducing a randomized lower bound, we investigate two different greedy algorithms and show that their competitive ratios differ.
Eventually, we consider the special case that there are only two packet values and present both lower and upper bounds.","Diese Dissertation befasst sich mit Online-Algorithmen zur Pufferung von Datenpaketen in Rechnernetzwerken. Online-Algorithmen sind Algorithmen, denen zur Findung einer Lösung eines Problems nicht bereits zu Beginn alle Eingaben vorliegen, sondern denen diese erst im Laufe der Zeit nach und nach bekannt gegeben werden. Somit müssen Online-Algorithmen Entscheidungen treffen, ohne vollständige Kenntnis über die Eingabedaten zu haben. In der Praxis kommen solche Situationen häufig vor, z.B. bei der Minimierung der Produktionsspanne in der Zeitablaufsteuerung.
Um zu messen, wie gut er bei der Lösung eines Problems die Schwierigkeit unvollständiger Kenntnis der Eingabe meistert, wird ein Online-Algorithmus mit einem optimalen Offline-Algorithmus verglichen, dem die Eingabe von Beginn an vollständig vorliegt. Hierzu wird der kompetitive Faktor des Online-Algorithmus bestimmt, der definiert ist als das schlechtestmögliche Verhältnis zwischen dem Profit des optimalen Offline-Algorithmus und dem Profit des Online-Algorithmus. Handelt es sich um einen randomisierten Online-Algorithmus, d.h. der Online-Algorithmus verwendet Zufallsentscheidungen, so ist bei der Bestimmung des kompetitiven Faktors sein erwarteter Profit heranzuziehen.
In Rechnernetzwerken werden heutzutage Daten zwischen verschiedenen Rechnern in Form von Datenpaketen ausgetauscht, wobei die Pakete auf ihrem Weg vom Start- zum Zielrechner von Routern weitergeleitet werden. Da es sein kann, dass Datenpakete an solchen Routern in dichterer Abfolge eintreffen, als sie abgearbeitet werden können, werden sie in den Routern zwischengepuffert. In dieser Arbeit untersuchen wir zum einen Router, an denen an mehreren Eingängen Pakete ankommen, die über verschiedene Ausgänge weitergesendet werden, wobei die Weiterleitung eines jeden Pakets den gleichen Profit erbringt, zum anderen solche, bei denen Pakete unterschiedlich großen Profit mit sich bringen, dieser allerdings nur dann gutgeschrieben wird, wenn das Paket innerhalb einer bestimmten, bekannten Zeit weitergeleitet worden ist. Die Puffer, die in den Routern zur Verfügung stehen, sind dabei jeweils von begrenzter Kapazität.
Wir betrachten verschiedene Szenarien, wobei in allen das Ziel darin besteht, einen möglichst großen (gewichteten) Durchsatz von Paketen zu erreichen, d.h. möglichst viele Pakete weiterzuleiten.
Im Falle mehrerer Ein- und Ausgänge gibt es an jedem Ausgang für jeden der möglichen Eingänge einen Puffer. In jedem Zeittakt können beliebig viele Datenpakete eintreffen, die dann dem zugehörigen Puffer beigefügt werden, sofern der Speicherplatz ausreicht. An jedem Ausgang kann allerdings pro Zeittakt nur ein Paket aus der Gesamtheit der ihm zugeordneten Puffer abgearbeitet werden.
Wir untersuchen deterministische Online-Algorithmen für dieses Problem und leiten deterministische untere Schranken für Greedy- und beliebige Algorithmen her. Ferner zeigen wir, dass ein modifizierter (Halb-)Greedy-Algorithmus einen besseren kompetitiven Faktor als der Greedy-Algorithmus selbst aufweist, und analysieren die Güte von Online-Algorithmen, denen in Form eines größeren Puffers oder einer größeren Abarbeitungsrate mehr Ressourcen zur Verfügung stehen als dem optimalen Offline-Algorithmus, mit dem sie verglichen werden.
Es wird ein optimaler Offline-Algorithmus mit linearer Laufzeit vorgestellt.
Die Analyse randomisierter Online-Algorithmen zu der Fragestellung beginnt mit der Diskussion einer randomisierten unteren Schranke für beliebige Puffergrößen.
Wir zeigen dann, wie sich Algorithmen für Einheitspuffer auf beliebige Puffergrößen verallgemeinern lassen, ohne dass ihr kompetitiver Faktor steigt.
Zunächst untersuchen wir einen Online-Algorithmus, der in jedem Schritt eine neue Zufallsentscheidung auswürfelt, sodann betrachten wir einen randomisierten Online-Algorithmus, der sämtliche Zufallsentscheidungen vor Beginn der Paketbearbeitung trifft und sich dann wie ein deterministischer Algorithmus verhält.
Auch für das Problem gewichteter Pakete mit vorgegebener Abarbeitungszeit leiten wir zunächst eine randomisierte untere Schranke her. Danach untersuchen wir zwei unterschiedliche Greedy-Algorithmen und zeigen, dass ihre kompetitiven Faktoren verschieden sind. Schließlich wenden wir uns dem Spezialfall zu, dass es nur zwei verschiedene Paketwerte gibt, und zeigen hierfüur sowohl untere als auch obere Schranken."]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Online packet buffering","Kompetitive Analyse von Online-Algorithmen zur Pufferung von Datenpaketen in Rechnernetzwerken"]}]}],"canonical_facts":{"dc:contributor":["Albers, Susanne"],"dc:creator":["Schmidt, Markus"],"dc:description.abstract":["This thesis treats several buffering problems that occur in routers or switches of computer networks. We develop and investigate algorithms for temporary data packet buffering, where information about the packets is not completely known in advance, but arrives by and by over time. In the classical approach of designing algorithms, all data are assumed to be known in advance. However, in practical applications, this assumption often does not hold. It may happen that decisions on a process must be made although information about this process is still incomplete. For such scenarios, online algorithms, which are able to make decisions without complete knowledge on the input, are used. A well-known example of an online problem is makespan minimization in job scheduling.
In order to measure how well it copes with the difficulty of incomplete knowledge about the input, we compare an online algorithm to an optimal offline algorithm that knows the whole input sequence in advance. In a competitive analysis, we determine the competitive ratio of the online algorithm, which is defined to be the asymptotic worst case ratio between the profit of the
optimal offline algorithm and the profit of the online algorithm, where if the online algorithm is randomized, i.e. if it makes random decisions, the expected profit of the online algorithm is considered.
In computer networks, data is nowadays interchanged between several computers by means of data packets where the data packets are forwarded by routers on their way from their origin computer to their destination computer. Since data traffic
may be bursty and packet loss is wished to be kept small, routers are equipped with buffers where packets can be stored temporarily. In this thesis, we first investigate routers having several input and output ports. The packets arriving at the input ports are to be transmitted via the output ports, where the forwarding of each packet results in the same profit. Then, we consider routers at which the transmission of different packets may result in different profits where we are only paid if the packet is forwarded within a given deadline. The puffers in the routers are of bounded capacity. We consider different scenarios in each of which the goal is to forward as many packets as possible.
In the case of several input and output ports, each output port is equipped with a distinct buffer for the different input ports. At each time step, an arbitrary number of packets arrive. They are appended to the buffers if space permits. At each output port, only one packet from the buffers assigned can be transmitted.
We investigate deterministic online algorithms for the multiqueue problem and derive lower bounds for greedy and other deterministic algorithms. Moreover, we show that a modified (semi-)greedy algorithm has a better competitive ratio than the greedy algorithm itself and analyze the performance of online algorithms that are granted more resources than the optimal offline algorithm they are compared to. We consider resource augmentation with respect to memory and speed.
Eventually, we present an optimal offline algorithm with a linear running time.
The analysis of randomized online algorithms for the multiqueue buffering problem starts by discussing a randomized lower bound for arbitrary buffer sizes. We then show how to generalize algorithms for unit buffers, which can store only one packet per queue, to arbitrary buffers without increasing their competitive ratio. First, we investigate an online algorithm that tosses a multisided coin in every time step, whereas, therafter, we consider a randomized online algorithm that makes all random decisions in advance and then acts like a deterministic algorithm.
Finally, we discuss the bounded delay buffering problem for weighted packets in a single queue. After deducing a randomized lower bound, we investigate two different greedy algorithms and show that their competitive ratios differ.
Eventually, we consider the special case that there are only two packet values and present both lower and upper bounds.","Diese Dissertation befasst sich mit Online-Algorithmen zur Pufferung von Datenpaketen in Rechnernetzwerken. Online-Algorithmen sind Algorithmen, denen zur Findung einer Lösung eines Problems nicht bereits zu Beginn alle Eingaben vorliegen, sondern denen diese erst im Laufe der Zeit nach und nach bekannt gegeben werden. Somit müssen Online-Algorithmen Entscheidungen treffen, ohne vollständige Kenntnis über die Eingabedaten zu haben. In der Praxis kommen solche Situationen häufig vor, z.B. bei der Minimierung der Produktionsspanne in der Zeitablaufsteuerung.
Um zu messen, wie gut er bei der Lösung eines Problems die Schwierigkeit unvollständiger Kenntnis der Eingabe meistert, wird ein Online-Algorithmus mit einem optimalen Offline-Algorithmus verglichen, dem die Eingabe von Beginn an vollständig vorliegt. Hierzu wird der kompetitive Faktor des Online-Algorithmus bestimmt, der definiert ist als das schlechtestmögliche Verhältnis zwischen dem Profit des optimalen Offline-Algorithmus und dem Profit des Online-Algorithmus. Handelt es sich um einen randomisierten Online-Algorithmus, d.h. der Online-Algorithmus verwendet Zufallsentscheidungen, so ist bei der Bestimmung des kompetitiven Faktors sein erwarteter Profit heranzuziehen.
In Rechnernetzwerken werden heutzutage Daten zwischen verschiedenen Rechnern in Form von Datenpaketen ausgetauscht, wobei die Pakete auf ihrem Weg vom Start- zum Zielrechner von Routern weitergeleitet werden. Da es sein kann, dass Datenpakete an solchen Routern in dichterer Abfolge eintreffen, als sie abgearbeitet werden können, werden sie in den Routern zwischengepuffert. In dieser Arbeit untersuchen wir zum einen Router, an denen an mehreren Eingängen Pakete ankommen, die über verschiedene Ausgänge weitergesendet werden, wobei die Weiterleitung eines jeden Pakets den gleichen Profit erbringt, zum anderen solche, bei denen Pakete unterschiedlich großen Profit mit sich bringen, dieser allerdings nur dann gutgeschrieben wird, wenn das Paket innerhalb einer bestimmten, bekannten Zeit weitergeleitet worden ist. Die Puffer, die in den Routern zur Verfügung stehen, sind dabei jeweils von begrenzter Kapazität.
Wir betrachten verschiedene Szenarien, wobei in allen das Ziel darin besteht, einen möglichst großen (gewichteten) Durchsatz von Paketen zu erreichen, d.h. möglichst viele Pakete weiterzuleiten.
Im Falle mehrerer Ein- und Ausgänge gibt es an jedem Ausgang für jeden der möglichen Eingänge einen Puffer. In jedem Zeittakt können beliebig viele Datenpakete eintreffen, die dann dem zugehörigen Puffer beigefügt werden, sofern der Speicherplatz ausreicht. An jedem Ausgang kann allerdings pro Zeittakt nur ein Paket aus der Gesamtheit der ihm zugeordneten Puffer abgearbeitet werden.
Wir untersuchen deterministische Online-Algorithmen für dieses Problem und leiten deterministische untere Schranken für Greedy- und beliebige Algorithmen her. Ferner zeigen wir, dass ein modifizierter (Halb-)Greedy-Algorithmus einen besseren kompetitiven Faktor als der Greedy-Algorithmus selbst aufweist, und analysieren die Güte von Online-Algorithmen, denen in Form eines größeren Puffers oder einer größeren Abarbeitungsrate mehr Ressourcen zur Verfügung stehen als dem optimalen Offline-Algorithmus, mit dem sie verglichen werden.
Es wird ein optimaler Offline-Algorithmus mit linearer Laufzeit vorgestellt.
Die Analyse randomisierter Online-Algorithmen zu der Fragestellung beginnt mit der Diskussion einer randomisierten unteren Schranke für beliebige Puffergrößen.
Wir zeigen dann, wie sich Algorithmen für Einheitspuffer auf beliebige Puffergrößen verallgemeinern lassen, ohne dass ihr kompetitiver Faktor steigt.
Zunächst untersuchen wir einen Online-Algorithmus, der in jedem Schritt eine neue Zufallsentscheidung auswürfelt, sodann betrachten wir einen randomisierten Online-Algorithmus, der sämtliche Zufallsentscheidungen vor Beginn der Paketbearbeitung trifft und sich dann wie ein deterministischer Algorithmus verhält.
Auch für das Problem gewichteter Pakete mit vorgegebener Abarbeitungszeit leiten wir zunächst eine randomisierte untere Schranke her. Danach untersuchen wir zwei unterschiedliche Greedy-Algorithmen und zeigen, dass ihre kompetitiven Faktoren verschieden sind. Schließlich wenden wir uns dem Spezialfall zu, dass es nur zwei verschiedene Paketwerte gibt, und zeigen hierfüur sowohl untere als auch obere Schranken."],"dc:format.medium":["application/pdf"],"dc:subject":["Kompetitive Analyse","Kompetitiver Faktor","Paketpufferung","Paketvermittlung","Competitive analysis","Competitive ratio","Packet buffering"],"dc:title":["Online packet buffering","Kompetitive Analyse von Online-Algorithmen zur Pufferung von Datenpaketen in Rechnernetzwerken"],"dc:type":["DoctoralThesis"]},"updated_at":"2026-07-24T02:22:46Z"}