Online algorithms for packet scheduling and buffer management
Kamal Al-Bawani, Matthias Englert, Walter Unger, Peter Rossmanith · 2016
In this work, we study the problem of buffer management in network switches from an algorithmic perspective. In a typical switching scenario, packets with different service demands arrive at the input ports of the switch and are stored in buffers (queues) of limited capacity. Thereafter, they are transferred over the switching fabric to their corresponding output ports where they join other queues. Finally, packets are transmitted out of the switch through its outgoing links to their next destinations in the network.Due to limitations in the link bandwidth and buffer capacities, buffers may experience events of overflow and thus it becomes inevitable to drop some packets. In other switching models, packets that are sensitive to delay are dropped if they exceed a specific deadline inside the queue. We consider multiple models of switching with the goal of maximizing the throughput of the switch. If all packets are treated equally, i.e., corresponding to the best-effort concept of the Internet, we quantify the throughput as the number of packets that are successfully transmitted through the switch. In networks with Quality of Service (QoS) requirements, packets are assigned values that correspond to their levels of service, and the throughput in this case is equal to the total value of packets that are successfully transmitted. We present different algorithms for the problem of buffer management. In the buffering phase of these algorithms, we examine whether an arriving packet is accepted or rejected, and whether an already queued packet is preempted (dropped) to save space for more valuable packets. In the scheduling phase, we seek to answer questions of the kind "which packet to transfer from an input port to an output port in a given time step?'', and "which packet to transmit from an output buffer?''. An input instance for our algorithms is a finite sequence of packets arriving in an ``online'' manner, i.e., packets arrive one by one over time and an irrevocable decision has to be made on the fly before future arrivals become known. Such algorithms which need to cope with incomplete information about future and cannot undo their decisions are called online algorithms. It is known that packet arrivals do not adhere to any specific arrival distribution. In reality, packets tend to arrive "in bursts'' rather than in smooth Poisson-like distributions. Thus, we do not make any prior assumptions about the arrival process of packets. We therefore resort to the framework of competitive analysis which is the typical worst-case analysis used to assess the performance of online algorithms. In competitive analysis, the benefit of an online algorithm is compared to the benefit of an optimal algorithm which is assumed to know the entire input sequence in advance. An online algorithm is called c-competitive if for each input sequence, the benefit of the optimal algorithm is at most c times the benefit of the online algorithm. The value c is also called the competitive ratio of the online algorithm. We prove upper and lower bounds on the competitive ratio of several online algorithms, and show that some of these algorithms are optimal.