Online packet buffering

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.

Author dc:creator

• Schmidt, Markus

Contributors dc:contributor

• Albers, Susanne

• Kompetitive Analyse
• Kompetitiver Faktor
• Paketpufferung
• Paketvermittlung
• Competitive analysis
• Competitive ratio
• Packet buffering

Repository record source_url

https://freidok.uni-freiburg.de/data/2349

OAI identifier oai:identifier

oai:freidok.uni-freiburg.de:2349