Understanding Buffering Problems in Communication Networks
Buffering problems in communication networks involve managing the flow of packets at routers to maximize throughput while considering factors like packet deadlines and buffer size limitations. These problems are often viewed as online games between algorithms and adversaries, with competitive ratios used to evaluate algorithm performance. Online algorithms need to make decisions before seeing all input, making them crucial in handling dynamic network conditions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Buffering problems Moran Feldman Technion Based on joint work with Seffi Naor
Outline Introduction to Buffering Problems Known Results Results for standard buffering problems A few proofs Our Contribution The problem we consider Our results A few proofs 2
Buffering Problems A router in a communication network receives, buffers and transmits packets. Often the router has to drop some of the packets arriving: Not enough memory to keep waiting packets. Packets have deadline, and they expire before transmission. A buffering problem: Describes a model of a router. Asks for a policy for managing the packets (how to decide which packets to transmit/accept/drop). The objective is to maximize (or minimize) some function over set of packets transmitted. 3
Standard Buffering Problems Common Properties Packets arrive continuously. One packet can be transmitted at every given time unit. Every packet d has an internal value w(d). The objective is to maximize the total value of transmitted packets (throughput). Bounded Delay Preemptive FIFO Non-Preemptive FIFO Each packet has a deadline. A packet can be transmitted only before its deadline. Any buffered packet can be transmitted. Packets are buffered in a limited size FIFO queue. The first packet in the queue is transmitted. At any time, packets can be preempted from the queue. Packets are buffered in a limited size FIFO queue. The first packet in the queue is transmitted. A packet must be either accepted to the queue or rejected upon arrival. 4
Online Problems Buffering problems are online problems. What makes a problem online? The input arrives on the fly. An algorithm for the problem has to make irrevocable decisions before seeing all the input. Game against an adversary Online problems are often viewed as a game between the algorithm and a malicious adversary. The adversary gives the input step by step. The algorithm responds to every piece of input. 5
Competitive Ratio Standard performance measure for online algorithms. Notation I An instance of an online problem. ALG(I) The value of the online algorithm ALG on I. OPT(I) The value of an optimal offline algorithm on I. Deterministic Algorithms The competitive ratio is: ( ) ( ) I OPT I sup ALG I Intuitively: the adversary inspects the algorithm, and chooses the worst input for it. Remark: Usually exponential time does not improve the achievable competitive ratio. Time complexity is less important in online settings. 6
Competitive Ratio (cont.) Randomized Algorithms There are three adversary types with different powers. Most works assume an oblivious adversary, i.e., an adversary that can inspect the algorithm, but not its random coins. The competitive ratio against oblivious adversary is: ( ) ( ) I OPT I sup E ALG I Intuitively: the adversary choose the entire input beforehand, and then feeds it to the algorithm step by step. Randomization often improves the achievable competitive ratio. 7
Outline Introduction to Buffering Problems Known Results Results for standard buffering problems A few proofs Our Contribution The problem we consider Our results A few proofs 8
Known Results Bounded Delay Deterministic Randomized e/(e 1) 1.582 [CCFJST06] Best Competitive Ratio 1.828 [EW07] Lower Bound 1.618 [AMZ03] 5/4 = 1.25 [CF03] Agreeable deadlines assumption: the packets arrive in a non-decreasing deadline order. Competitive ratio of [SS05]. Other assumptions yielding improved competitive ratios: s bounded: at most stime units between packet s arrival and deadline. s uniform: exactly stime units between packet s arrival and deadline. 9
Known Results Preemptive FIFO Results for this model tend to be better than for the previous one. Deterministic Randomized Best Competitive Ratio 3 1.732 [EW06] - Lower Bound 1.419 [KMS05] - If only two packet values are allowed: 1 and . Deterministic Randomized Best Competitive Ratio 1.303 [LP02] 1.25 [A05] Lower Bound 1.281 [KLMP04] 1.197 [A05] The worst case is usually a buffer of size 2. Improved competitive ratios are known for larger buffers. 10
Known Results Non-Preemptive FIFO The optimal algorithm never preempts. Therefore, results in this model are much worse. If packets take values from the set {1, } only. Tight competitive ratio of (2 1) / for both deterministic and randomized algorithms [AMZ03, AMRR00]. If packets take values from the range [1, ]: Deterministic competitive ratio of e ln [AMZ03]. Deterministic lower bound of 1 + ln [AMZ03]. Remark: Our results are for a variant of this problem allowing better results. 11
Other Buffering Problems Most buffering problems are variants of the standard problems. Variants of the model Variants of the objective Minimize the maximum delay Multiple input queues General output bandwidth: W packets transmitted per time unit Minimize the total delay 12
Greedy Algorithm for Bounded Delay Algorithm [KLMPSS01] At every time unit: 1. Discard packets that expired. 2. Transmit the remaining packet with maximum value. Notation ALGt - the value ALG gains till time t. OPTt - the value OPT gains starting from time t if given ALG s configuration at time t (also denotes the corresponding schedule) . t - a time after the deadline of the last packet. Goal Prove 2ALGt OPT0. 13
Greedy Algorithm for Bounded Delay (cont.) Lemma For every time t, 2(ALGt+1 ALGt) OPTt OPTt+1. Proof Let dOPT (dALG) be the packet OPTt (respectively, ALG) transmits at time t. OPTt+1 can use the schedule of OPTt without dALG and dOPT. OPTt OPTt+1 w(dOPT) + w(dALG) 2w(dALG) = 2(ALGt+1 ALGt). Corollary 2(ALGt ALG0) OPT0 OPTt . 14
Algorithm for Agreeable Deadlines Algorithm [LSS05] Every time a packet arrives Discard all but a schedulable set of packets of maximum value. Sort the packets in non-decreasing deadline order. Definitions e The most valuable packet among the packets with the earliest deadline. h The packet with the earliest deadline among the most valuable packets. Decide which packet to transmit If w(e) w(h) / , transmit e. Otherwise, transmit the first packet f with w(f) w(h) / and w(f) w(e) . 15
Algorithm Analysis Analysis We want to prove that ALG is competitive. We keep the buffers of OPT and ALG identical, at the cost of increasing OPT s value. Assume OPT transmits packets in non-decreasing deadline order. Events to Consider A packet is transmitted. A packet arrives. Packet Transmission - (A Bit Tedious) Case Analysis 1. If both OPT and ALG transmit the same packet, their buffers remain identical. In the other cases, we use the following notation: dALG The packet ALG transmits. dOPT The packet OPT transmits. 16
Packet Transmission (cont.) 2. If dALG comes before dOPT. The deadline of dALG is before that of dOPT. OPT does not transmit dALG, therefore, w(dOPT) w(dALG). On the other hand, w(dALG) w(h) / w(dOPT) / . We let OPT transmit dOPT, and then replace dALG in its buffer with dOPT. ALG s gain is at least -1 times OPT s gain. The future gain of OPT only improves by the replacement. 3. If dOPT = e. w(dALG) w(e) Let OPT transmit both e and dALG, and keep e in its buffer. Clearly, we just helped OPT. ALG s gain is w(dALG). OPT s gain is w(e) + w(dALG) (1 + -1) w(dALG) = w(dALG) . The common buffer: dALG dOPT dOPT 17
Packet Transmission (cont.) 4. If dOPT e appears before dALG. dALG is better than dOPT: later deadline and higher value. OPT is guaranteed to transmit dALG in the future. OPT is not going to transmit e. We make OPT transmit dALG now, and then continue as before. Only the transmission times (by OPT) of packets appearing before dALG are effected. Each such packet d is still transmittable even after transmitting all earlier packets in the range e d. The modified OPT sends dALG and a subset of e d excluding e. Hence, d remains transmittable. The common buffer: e d dOPT dALG 18
Packet Arrival What Happens When a Packet Arrives? The algorithm discards all but a schedulable set of packets of maximum value. Can be reduced to bipartite matching (nodes on the left side are the packets, and on the right side are the transmission slots). Our Objective Let D be the set of packets dismissed. We want to show that: There is a schedule for OPT that does not contain any packet of D. Hence, OPT can dismiss D, and keep the same buffer as ALG. Proof Let B be the set of packets ALG keeps, and let S be a schedule for transmitting all of them. Assume the next transmission time is 1, and OPT first transmits a packet outside of B D in time t. 19
Packet Arrival (cont.) Observe that OPT transmits: Till time t-1: only packets of B D. Starting from time t: only packets outside B D. Case 1: t > |B| Replace OPT with the following schedule: Mimic S till time |B|. Mimic the original OPT starting from time t. Case 2: t |B| Consider the schedules of OPT and S for packets of B D. t OPT: S: 1 |B| 20
Packet Arrival (cont.) Assume OPT transmits a packet d D. S transmits on the same time a packet d B such that: w(d ) w(d) because S could transmit d instead. If OPT does not transmit d , we just replace d with d . Otherwise, during the time when OPT transmits d , S transmits a packet d B such that: w(d ) + w(d ) w(d ) + w(d) because S could transmit d instead of d and d instead of d . If OPT does not transit d , we do these replacemts. Otherwise, continue in the same way till d is removed. t OPT: d d S: d' d 1 |B| 21
Outline Introduction to Buffering Problems Known Results Results for standard buffering problems A few proofs Our Contribution The problem we consider Our results A few proofs 22
Motivation Consider a path in a communication network: Router Router Router A packet going through the path often has a deadline. The deadline refers to the arrival of the packet to its destination. An online model of a router must deal with these deadlines: The standard models assume a deadline for leaving the router. A new model (proposed by Fiat, Mansour and Nadav [SODA 2008]), associates each packet with a value that diminishes over time. 23
The Model Our model is based on the model of Fiat et. al. 3 4 2 Router s queue Packets Time Unlimited size Arrive online, each has an associated value w(d). Must be rejected or accepted immediately. Packets arrive at fractional times and are transmitted at integral ones. At each integral time the first packet of the queue is transmitted. Its revenue is w(d) minus the delay it suffered in the queue. Continues, starting at time 0 24
Results for this Model Sub models Unrestricted model A packet can have any positive value. Real valued model A packet can have any value 1. Integral valued model A packet can have any positive integral value. Unrestricted Model Model Unrestricted Real Valued Model Model Real Valued Integral Valued Model Valued Model Integral 3 4.236 (3) Lower bound Lower bound (3) 3 3 4 (3) 3 Deterministic Deterministic Upper bound Upper bound - - 4.24 4.24 4.24 4 (4.24) Lower bound Lower bound 1.618 ( ) 1.618 4 ( ) 1.618 4 ( ) Randomized Randomized Upper bound Upper bound - - 4.24 4 (4.24) 4.24 4 (4.24) Known results inferred from Fiat et. al. New results appear in red. 25
Unrestricted Model Lower Bound Consider any algorithm ALG and a constant c. Our job: Show that ALG is not c-competitive. Plan of Adversary 1. For i = 1 to 2c do: 2. Give ALG a packet of value (1/2c)2c+1-i. 3. If the probability that ALG accepted any packet, so far, is less than i/2c, terminate. 4. Give ALG a packet of value 1. Proof Idea Packets have exponentially increasing values, but all values are at most 1, so only one packet gives revenue. ALG must accept each packet with some probability. OPT accepts with probability 1 the last packet. 26
The Dual-Fitting Method Offline Primal Program ( ) t d y d a t , ( ( ) ( ) ) ) t ) ( ) max w + , d d ( ) d ( ) ( ( ) ( d y a d + | d t a t w d a ( ( ) . t . s 1 packet constraint y d a t d ( ) d ( ) d + | t a t w d ) , 1 constraint time t ( ) ( d ( ) ( ) d , | d a d t w ) ( ) d ( ) d ( ) d + 0 , y t d a t w a y(d,t) Indicates whether packet d was transmitted at time t. w(d) The value of packet d. a(d) The time when packet d arrived. Remark The LP contains no FIFO constraint because this is no constraint from the offline point of view. 27
The Dual-Fitting Method (cont.) Offline Dual Program + min x z t d t d ( ) d ( ) d ( ) d ( ) d ( ) d + + . t . s , x z w 0 t a d a t w a t d , , x z d t t d Method Every dual solution is an upper bound on OPT. To show that an algorithm is c-competitive we do the following: Consider any input sequence . Calculate the revenue R of the algorithm on . Find a dual solution of value D for . Prove that D /R c. 28
Deterministic Reduction to Simple Inputs Definition An input sequence is simple if all packets in it arrive before time 1. Reduction If there is a deterministic R-competitive algorithm A on simple input sequences, then there exists a deterministic R-competitive algorithm B on all input sequences. Definition of B B s Input: 5 3 7 A s Input: 5 3 8 0 1 2 3 4 5 1. B simulates A and maps each input packets to A s input. 2. Map each packet to time before time 1, and increase its value by the number of transmissions so far. 3. Reset the algorithm when the queue empties. 29
Deterministic Reduction to Simple Inputs (cont.) Why Does It Work? Let an interval be the time between two consecutive resets. B (and A) transmit packets at all integral times in an interval. Moving packets to earlier time: Does not effect the transmission times. Increase the delay that the packets suffer. Increasing the value of the packets counters the additional delay. 5 3 7 5 3 8 0 1 2 3 30
Deterministic Algorithm for Integral Simple Inputs Algorithm (NDT) 1. Let Qbe the number of packets in the router s queue. 2. Accept a new packet d if and only if w(d) 2Q + 1. Remark The algorithm also works for general integral inputs, although it is more difficult to show that. Reduction Assume that if a packet d is accepted, then its value is exactly 2Q+1. Proof This is the lowest value that will get the packet accepted. 31
Analyzing NDT Assume k packets have been received: Value for the Algorithm Assignment to the Dual LP ( ) + + + min 2 x z 1 1 k = k k k k ( ) t d + = = 2 1 Q Q t d ( ) d ( ) d ( ) d ( ) d ( ) d + + . t . s , x z w 0 t a d a t w a 2 2 t d 0 Q , , x z d t t d zd = 0 xt = max{2k - t, 0} ( k k = 2 ) Delay Packet Value 2 1 2 2 1 k Value of solution: ( ) = = 2 2 2 k t k k 1 t k 2 The competitive ratio of NDT is: 2 k k 4 ( ) + 2 / 2 k 32
Randomized Reduction to Simple Inputs Difficulty The previous reduction does not work for randomized algorithms: If we restart each time the queue empties, the simulated algorithm A will face a non-oblivious adversary. If we do not restart, the algorithm will not necessarily have a packet to send at each integral time of an interval. Definition A randomized algorithm is good if at all times an external observer can give a number P such that: The algorithm has either P or P+1 packets in its queue. P does not depend on the random decisions of the algorithm. Remark In a sense, a good algorithm is a randomized algorithm with minimal randomness. 33
Randomized Reduction to Simple Inputs (cont.) Objective Make the previous reduction work for good randomized algorithms. Idea We reset A s simulation after every integral time in which we might not have a packet to transmit. This ensures that the queue is empty after every reset. Either: The queue was empty before the integral time. The last packet was sent during the integral time. A faces an oblivious adversary. The reduction does not depend on A s randomized decisions. The algorithm transmits at each integral time between resets. 34
Randomized Algorithm for Real Valued Simple Inputs Algorithm (RNDT) 1. Let Q be a random variable of the size of the queue. 2. Keep the invariant Q = E(Q) or Q = E(Q) . 3. Accept a new packet d with probability: d first packet w(d) 2E(Q)+0.5 2E(Q)+0.5 w(d) 2E(Q)+2.5 w(d) 2E(Q)+2.5 0 w(d) / 2 0.25 E(Q) 1 To keep the invariant, true acceptances probability depends on the actual value of the random variable Q. Reduction Let Ef be the final value of E[Q]. No packet had value over 2Ef + . Proof For rejected packets: implied by the acceptance probabilities. For packets d accepted with probability p: We can assume w(d) 2E[Q] + 0.5 + 2p. E[Q] increases following the arrival by p. 35
Analyzing RNDT Value for the Algorithm Assignment to the Dual LP E + / 1 + + 2 f 4 E E 1 min f x z ( ) + t d f 5 . 0 + = x dx t d ( ) d ( ) d ( ) d ( ) d ( ) d + + . t . s , x z w 0 t a d a t w a 2 2 t d / 1 2 , , x z d t t d zd = 0 xt = max{2Ef + 1.5 - t, 0} ( 2 5 . 1 + t ) 2 The packet which caused E[Q] to exceed x must have value of at least 2x + 0.5. First Packet 5 . 1 + 2 1 E E ( ) f = t Value of solution: f = 2 E f 2 1 E = + / 1 + 2 f 2 2 2 E f + E / 1 + 2 f 2 E 2 2 E E The competitive ratio of RNDT is: ( f = 4 ) + / 1 + 2 f 4 / 2 f 36
Open Problems Adversary that draws from a malicious distribution. Competitive analysis provides too pessimistic a view. Classic queuing theory analyzes Poisson distributed source. Provides a middle ground between the two approaches. A sub-model where all values above some constant c are allowed. Generalizes the unrestricted and real-valued models. The constant c represent the ratio between the shortest deadlines and the speed of the network. The main question is finding the relation between c and the competitive ratio. 37
