We show that the Longest Queue Drop algorithm is 1.5-competitive for shared-memory switches with three output ports. This improves upon the previous best upper bound of (2 M1 bM=3c M3 ) for the competitive ratio of the Longest Queue Drop algorithm, for 3-port shared-memory switches, where M denotes the shared-memory size.
Introduction The area of memory management is strongly related to that of online computation, due to the unpredictability of future requests that naturally arises in related problems. Hence, the fact that a great deal of research has been dedicated to online algorithms improving the throughput of devices that incorporate bu ers, comes as no surprise.
A shared-memory switch is a bu er equipped with a number of input and output ports; in our case with three output ports. Assuming that time is slotted, packets arrive at any time step to any of the input ports and must be immediately accepted by the bu er or be immediately rejected. Each arriving packet is labelled with a single output port of the switch. Any rejected packet is inevitably lost and any accepted packet is stored in the bu er. At any time step, one packet is transmitted by each output port of the switch, to which at least one packet stored in the bu er is destined.
Since there may exist at most three di erent types of packets stored in the bu er at any time, we may assume that the packets stored in the bu er which are destined to the same output port, are arranged in their own queue. In other words, we may have at most three queues at any time step.
An algorithm is called preemptive if an eviction from the bu er of an already accepted packet is possible. Otherwise, the algorithm is called non-preemptive.
In this paper, we discuss the Longest Queue Drop algorithm (LQD), for the case of shared-memory switches equipped with three output ports. According to LQD, which is a preemptive online algorithm, any packet is accepted by the bu er if there exists free bu er space at the time step when this packet arrives. If the bu er is full at the time step when the packet arrives, a packet is preempted from the longest queue in the bu er at this point in time, releasing bu er space for the arriving packet which is accepted. After all packet acceptances and preemptions take place, at each time step, one packet of each queue is forwarded from the bu er to its designated output port to be transmitted.
The LQD algorithm was introduced in [7] and there exists a considerable amount of literature regarding it (for example [2, 3]). 1.1
Hahne et al. [5] show a lower bound of 4/3 for the competitive ratio of any deterministic online algorithm, for the problem of maximizing the number of transmitted packets from a shared-memory switch equipped with any number of output ports. Aiello et al. [1] show that LQD is 2-competitive and at least p2competitive, when the number of output ports N 2 of the switch is assumed to be arbitrary.
competitive ratio for 2-port shared-memory switches, where M 2 Z+ denotes the bu er size. In [6], an upper bound of (2 M1 bM=N c MN ) is, also, shown for the LQD competitive ratio. This bound tends to 5/3 as M ! 1 when N = 3, being larger than 1.5 for M 19 when N = 3.
We show that LQD is 1.5-competitive for 3-port shared-memory switches. We assume that M N = 3 throughout the following analysis. We note, however, that several of our lemmas and corollaries hold for switches equipped with any number of output ports N M . 2 2.1
Preliminaries
Both LQD and OPT are assumed to use their own bu ers, each of size M . Time proceeds in discrete time steps and T 1 will denote the latest time step when a packet exists in any bu er. Analysis will proceed by comparing the two bu er contents. As [n] we denote the set f1; :::; ng for a positive integer n.
Let ALG denote any algorithm for the problem of maximizing the number of transmitted packets from a shared-memory switch equipped with any number of output ports N M . A packet accepted by the ALG bu er will be called ALG packet, in short.
All de nitions that follow until the end of the current paragraph, refer to the bu er content of ALG, after all packet acceptances, rejections and preemptions have taken place, at each time step: We denote as pit;ALG the length of a queue i 2 [N ] in the ALG bu er at a time step t 2 [T ]. A queue i 2 [N ] is said to be active in the ALG bu er at a time step t 2 [T ] if pit;ALG > 0, else i is inactive in the ALG bu er at t. As `tALG(q) 2 [M ], we denote the queue position of a packet q in the ALG bu er, at a time step t 2 [T ].
call the set of consecutive time steps from t1, inclusive, to t2, inclusive and we denote the period as [t1; t2].
t. At any time step when the LQD bu er over ows, this bu er is full. Observation 1 The lengths of two queues in the LQD bu er, that over owed in the LQD bu er at the same time step t 2 [T ], may di er by at most 1 at t.
We denote as h (ALG) 0 the number of packets that ALG transmits in the period [1; T ], where denotes the incoming packet sequence.
pit;ALG 0 1, for each queue i 2 [N ] and at each time step t 2 [T 0], where T 0 T .
Since M N , no (o ine or online) algorithm can keep active at time step t = 1 strictly more queues than the number of active queues of LQD at t = 1, for any incoming packet sequence . Hence, no algorithm can transmit strictly more packets at t = 1 than the number of packets that LQD transmits at t = 1, for the same . Taking into consideration the fact that LQD is, trivially, an 1-balanced algorithm, we have the next observation: Observation 2 Let ALG0b denote any algorithm that keeps inactive at t = 1 an active queue in the LQD bu er at t = 1, for an incoming sequence . Then, there exists an 1-balanced algorithm ALG1b such that h (ALG1b) h (ALG0b). Lemma 1. There exists an optimal o ine algorithm which is T -balanced and which never preempts any packet.
Proof. Let ALG1 be an o ine algorithm which is t0-balanced but not (t0 + 1)balanced, where t0 2 [T 1]. We assume that ALG1 never preempts any packet, since otherwise we can modify ALG1 so that it never preempts any packet without decreasing h (ALG1), where is the incoming packet sequence.
It is ptj0;A+L1G1 = 0 and ptj0;L+Q1D > 0 for a queue j 2 [N ], because ALG1 is t0balanced but not (t0 + 1)-balanced. But then, there has to exist a queue k 6= j and a time step t00 t0 + 1 so that: { It holds ptk0;0LQD < ptk0;0ALG1 or { The sum of the empty ALG1 bu er space at t00 and ptk0;0ALG1 is strictly greater than ptk0;0LQD .
de ned above, then we choose the latest time step t00 in the period [1; t0 + 1] and we break ties arbitrarily for choosing the queue k, at this chosen t00.
We, now, modify ALG1 so that one more packet for j is accepted in the period [1; t0 + 1]. For this, one packet less for k (if pk;LQD < ptk0;0ALG1 ) may need to be t00 accepted by the modi ed algorithm, at the latest over ow time step in the LQD bu er of k in the period [1; t00]. This gives us a new t^-balanced algorithm ALG2 (for some t^ t0) for which it holds h (ALG2) h (ALG1) because j becomes active in the ALG2 bu er at t0 + 1.
Working as above, we obtain a sequence of algorithms ALG1; : : : ; ALGv (for a v 2 Z+), where ALG1; : : : ; ALGv 1 are not T -balanced, ALGv is T -balanced and it holds h (ALGl) h (ALGl 1) for each l 2 [v]. By their design, none of the algorithms ALG1; : : : ; ALGv preempts any packet from any queue. It follows that h (ALGv) h (ALG1) which by Observation 2, completes the proof. tu 2.2
A queue i 2 [N ] is called as established at t 2 [T ], if pit;LQD = 0 and pit;OPT > 0.
is a dominating queue at t. We denote as Dt, Et, F t, the sets of dominating, established and free queues, respectively, at t 2 [T ].
`tOPT(q) > pit;LQD , is called extra packet at t. An OPT packet of an established queue at a t 2 [T ] is, also, called extra packet at t. An LQD packet of a queue i 2 F t at a time step t 2 [T ], is called free packet at t. An LQD packet of a dominating queue at a t 2 [T ] is called common packet, at t.
We denote as e(t) 0 the number of extra packets in the OPT bu er at t 2 [T ] and as f (t) 0 the number of free packets in the LQD bu er, at t.
By Lemma 1, a queue cannot be inactive in the OPT bu er and active in the LQD bu er at the same time step. This gives us the next corollary: Corollary 1. Any queue at any time step t 2 [T ] can either belong to set Dt or to set F t or to set Et or be inactive in both bu ers at t.
By Corollary 1, the ratio of transmitted packets between OPT and LQD, for an incoming packet sequence , is de ned as: r = h (OPT) h (LQD) = 1 +
Ptt==1T jEtj
h (LQD)
1
(
The numerator of the fraction in the right hand side of (
Observation 3 Since M N , if a queue i 2 [N ] is inactive in the LQD bu er at a time step t 2 [T 1] and at least one packet arrives destined to i at t + 1, then i will be active in the LQD bu er at t + 1.
Lemma 2. If i 2 Et+1 for any queue i 2 [N ] at any time step t 2 [T it is i 2 Dt [ Et. 1], then Proof. First, we show that if i 2 Et+1 then pit;OPT > 0: Assume that pit;OPT = 0 and, therefore, that it holds pit;LQD = 0 due to Lemma 1. If no packet arrives to i at t + 1, then i 2= Et+1 by the de nition of an established queue. Otherwise, if at least one packet arrives destined to i at t + 1 then i has to be active in the LQD bu er at t + 1, by Observation 3; therefore it is i 2= Et+1.
We, now, show that if i 2 Et+1 then i 2= F t: Assume that i 2 F t. The length of a free queue in the LQD bu er at any time step is at least 2, by the de nition of a free queue and Lemma 1; hence since i 2 F t then i has to be active in the LQD bu er at t + 1 and, therefore, it has to be i 2= Et+1.
By Corollary 1 and the arguments of the rst two paragraphs of this proof, the lemma follows.
Lemma 3. If i 2 F t for any queue i 2 [N ] at any time step t 2 [T holds i 2 F t+1 [ Dt+1. 1], then it Proof. The length of a free queue in the LQD bu er is at least 2, by the de nition of a free queue and Lemma 1. It follows that pit;LQD 2. But then, i has to be active in the LQD bu er at t + 1, which by Corollary 1, completes the proof. tu Lemma 4. It holds f (t) Proof. (see Appendix).
e(t) + Pi2F t pit;OPT at any time step t 2 [T ].
denote as t1;ii 2 [T ] the latest time step in the period [1; t] when i over owed in the LQD bu er as a dominating queue and we know that such a time step exists by Lemma 2 and Observation 3. Also, we denote as t2;ii t the rst time step after t1;ii when i becomes an established queue, where the superscript i 2 Z+ will be de ned shortly. This gives us a strict total order: t11;i < t2;i < t1;i < t2;i < :::, 1 2 2 where the superscript denotes each pair of two consecutive time steps in the total order, starting from pair ft11;i, t2;ig, then pair ft12;i, t2;ig etc. Finally, let 1 2 us say that we have i 2 Z+ pairs of time steps in this total order, i.e., it holds 1 1 t1;i < t2;i < ::: < t1;ii < t2;ii and, hence, i 2 [ i].
1 time in [1; T ] at time step 10. Then, it is t2;i = 10 (note that time step 10 may be equal to t1;jj or t2;jj for another queue j 6= i and for a j 2 [ j]). By Lemma 2 and Observation 3, it follows that i has over owed in the LQD bu er as a dominating queue, for at least one time step before time step 10 and assume that the latest time step in the period [1,10] of such an over ow is time step 7, i.e., t11;i = 7. Assume, also, that the rst time step after t21;i = 10 when i over ows as a dominating queue in the LQD bu er is time step 30 and the rst time step after time step 30 when i becomes an established queue is time step 40. It follows that t22;i = 40 and that t21;i is the latest time step in [30, 39] when i over ows as a dominating queue in the LQD bu er. This concludes our example. Lemma 5. The queue i 2 [N ] is a dominating queue at each time step of the period [t1;ii; t2;ii 1], for any i 2 [ i].
Proof. (see Appendix). tu tu Lemma 6. The number of extra packets of any queue i 2 [N ] cannot strictly increase between any two consecutive time steps of the period [t1;ii; t2;ii], for any i 2 [ i], i.e., it holds pit;OPT pit;LQD pit;+O1PT pit;+L1QD , where t 2 [t1;ii; t2;ii 1]. Proof. (see Appendix). t2;ii (for any i 2 [ i upper-bounds the number of transmitted extra packets of i in the period [t2;ii; T ].
We shall work similarly to Aiello et al. [1], assigning connections between extra packets and LQD packets.
De nition 1. A connection between an extra packet e and an LQD packet e0 which is assigned at a time step t 2 [T ] when both packets are in their respective bu ers, will be called valid if `tLQD(e0) `tOPT(e).
All connections will be valid, hence a valid connection will be usually called from now as, simply, connection. We say that an extra packet u is connected with an LQD packet u0 at a time step t 2 [T ], if: { These packets were assigned the connection between them at a t0 2 [1; t] and { These two packets remain connected together at each time step of [t0; t] and { These two packets are in their respective bu ers at t.
Fact 1 From the time step tc 2 [T ] when an extra packet x is assigned a connection with an LQD packet y, these two packets are assumed to stay connected at each later time step, until any of the following takes place, in any order: 1. The LQD packet y is transmitted, or 2. The LQD packet y is preempted, or 3. The extra packet x becomes a non-extra packet at a time step t0c > tc, i.e., x is still in the OPT bu er at t0c but it is not an extra packet at t0c. In the rst case of Fact 1, that is if the LQD packet y is transmitted at a time step ts > tc, we delete the connection between x and y at ts, i.e., x and y are no more connected in the period [ts; T ] (note that by De nition 1, the LQD packet y will be transmitted not later than the extra packet x is transmitted). Finally, we shall say that x is associated with the transmitted LQD packet y, in [ts; T ].
In the second case of Fact 1, that is in the case the LQD packet y is preempted at a time step tp > tc, we delete the connection between x and y at tp and we assign at tp, a new connection between x and the newly accepted LQD packet. Since the newly accepted LQD packet cannot be located at a greater queue position than that of the preempted LQD packet y at the preemption time step tp, this new connection is valid.
For the third case of Fact 1, we rst need De nitions 2 and 3: LQD i p j
OP T LQD i p0 p j
OP T LQD i p0 p
LQD j De nition 2. As con(e; t) 0, we de ne the number of LQD packets that an extra packet e (which is in the OPT bu er at a time step t 2 [T ]) is connected with at t, plus the number of transmitted LQD packets associated with e at t. De nition 3. Let p and p0 6= p be two extra packets belonging to the same queue i 2 [N ] in the OPT bu er, at a time step t 2 [T ]. We shall say that p0 is inferior to p at t, if it is `tOP T (p0) > `tOP T (p) and it is con(p0; t) < con(p; t).
Therefore, in the third case of Fact 1, that is if x is an extra packet in [tc; t0c 1] but not an extra packet at t0c, then: { If there exists an inferior extra packet of x at t0c, then we choose the inferior extra packet x0 of x which is located at a smaller queue position than any inferior extra packet of x at t0c and:
We delete all connections and associations of both x and x0 at t0c and We assign to x0 at t0c all connections and associations that we deleted from x at t0c and we set con(x0; t0c) = con(x; t0c).
{ Else we delete all connections and associations of x at t0c. 3
Analysis De nition 4. A valid connection between an extra packet e of a queue i 2 [N ] and an LQD packet c, which is assigned at a time step t1;ii (for any i 2 [ i]), is called strong connection, if c is a common packet of i at this t1;ii time step.
By Observation 1 and De nition 1 we have Observation 4. Observation 4 A connection that is assigned to an extra packet of a queue i 2 [N ] at any of its t1;ii time steps ( i 2 [ i]) is valid.
Lemma 8. Assume that an extra packet of a queue i 2 [N ] is assigned a strong connection with an LQD packet c at a t1;ii time step (for a i 2 [ i]). Then, c will never be preempted and will never become a free packet until its transmission.
By Observation 1 and since M
N , we have Observation 5:
De nition 5. Assume that i 2 Dt at a time step t 2 [T ]. Then, the upmost h extra packets of i at t (where h 2 Z+) are the h extra packets of i that occupy the h greatest queue positions of i at t.
De nition 6. An extra packet s of a queue i 2 [N ] for which it holds `tOP T (s) > t 2 pi;LQD at a time step t 2 [T ], is called upper extra packet of i at t. Any other extra packet of i at t is called lower extra packet of i at t.
respectively, that a queue i 2 [N ] has at a time step t 2 [T ].
De nition 7. If 2 pi;LQD < pit;OPT at a time step t 2 [T ] for a queue i 2 [N ], t then i is called primary dominating queue at t else if 2 pit;LQD pit;OPT then i is called secondary dominating queue at t. tu tu tu tu
According to the connection assignment process that we describe in Section 3.1, if an extra packet r is connected with at least one LQD packet at a time step t 2 [T ], then we may assign a new connection to r at t, only if each connection that r currently has, is strong. This gives us the next lemma.
Observation 5 At any t 2 [T ] when a packet of a queue i 2 [N ] is preempted or rejected from the LQD bu er, it holds pit;LQD bM=N c.
Lemma 9. If a queue i 2 [N ] over ows in the LQD bu er at a time step t 2 [T ] and i is a primary dominating queue at t, then it holds jF tj = 2. Proof. (see Appendix).
Lemma 10. If i 2 F t and a dominating queue over ows in the LQD bu er at t, then pit;LQD dM=2e.
Proof. Assume for contradiction that pit;LQD M=2 + 1. By Observation 1, the length of the dominating queue that over ows in the LQD bu er at t, is at least equal to the length of i in the LQD bu er at t, minus 1. Taking the sum of the packet numbers for these two queues at t in the LQD bu er, it follows that at least M + 1 packets exist in the LQD bu er at t, which cannot happen. Lemma 11. If jF tj = 1 then it is e(t) dM=2e, at any time step t 2 [T ].
Proof. (see Appendix). Lemma 12. Each extra packet of any queue i 2 [N ] may be connected with at most one LQD packet of a queue other than i, at any time step of [1; T ]. Proof. The lemma follows by Lemma 8 and Fact 1.
Lemma 13. Any extra packet may be connected with at most one free packet, at any time step of [1; T ].
3.1
We shall, now, assign connections between extra packets and LQD packets, proving that the next invariant holds at every time step t 2 [1; T ]: Invariant 1 No LQD packet is connected with two or more extra packets at t.
step (for a i 2 [ i]). For simplicity, let t1;i = t1;ii and t2;i = t2;ii. We distinguish between the cases that i is primary dominating or secondary dominating, at t1;i: tu tu
By Lemma 9, it is jF t1;i j = 2 and, hence, the only dominating or established queue at t1;i is i. It follows that all LQD packets are currently not connected at t1;i, since it is only i that has extra packets in the OPT bu er at t1;i.
We assign one connection to each lower extra packet of i at t1;i with a di erent common packet of i. The number of common packets of i at t1;i su ces so that each lower extra packet of i is assigned one connection, by De nition 6. We, also, assign one connection to every extra packet of i with a di erent free packet at t1;i. The number of free packets at t1;i su ces to assign one connection to each extra packet of i with a di erent free packet, due to Lemma 4.
Wrapping up, we assigned two connections to each lower extra packet of i at t1;i and one connection to each upper extra packet of i at t1;i, so that Invariant 1 holds at t1;i. Any connection assigned is valid, by Observation 4. Lemma 14. No packet in the LQD bu er at time step t2;i > t1;i may be connected with a connection which was assigned at time step t1;i.
Proof. (see Appendix).
If lit1;i
pit;2O;iPT then the connection assignment for Case 1 is complete. Otherwise, if lit1;i < pit;2O;iPT , we distinguish between sub-cases (A1), (A2) and (A3):
(A1) If jF t2;i j = 2, then it is only queue i that has extra packet(s) at t2;i. By this and Lemma 14, no LQD packet is currently connected at t2;i. Hence, we OP T LQD ut1,i
i `t1,i i
OP T
LQD LQD
LQD
OP T LQD i
F t1,i i w j assign a connection at t2;i to each of the upmost pit;2O;iPT lit1;i extra packets of i at t2;i, with a di erent free packet. By Lemma 4, the number of free packets su ces for these connections to be assigned at t2;i and Invariant 1 holds at t2;i.
(A2) If jF t2;i j = 1, then it is e(t2;i) dM=2e, by Lemma 11. We denote the single free queue we have at t2;i as w 6= i and the third queue that we may have at t2;i (which can be dominating or established) as j 6= fi; wg (see Figure 2). By Observation 5 it is pit;1L;iQD bM=3c, which by De nition 6 gives us lit1;i bM=3c. By the last inequality and since e(t2;i) dM=2e, it is: 2 lt1;i i e(t2;i) 1
But the number of extra packets in the OPT bu er at t2;i is equal to the
number of extra packets of i at t2;i plus the number of extra packets of j at t2;i:
By (
ptj2;L;iQD) + pit;2O;iPT
lt1;i
i
ptj2;O;iPT
ptj2;L;iQD
(
Hence, we assign a valid connection to each of the upmost (pit;2O;iPT lit1;i )
extra packets of i, without violating Invariant 1 at t2;i. This is because each of
the upmost (pit;2O;iPT lit1;i ) extra packets of i at t2;i, is located at a queue position
at t2;i which is at least equal to lit1;i . But, by (
(A3) It cannot be jF t2;i j = 0, since at least one extra packet of i exists in the OPT bu er, at t2;i. Therefore, by Lemma 4, it has to be jF t2;i j 1.
OP T
LQD
OP T
LQD i w j
We distinguish between sub-cases (B1), (B2) and (B3), for the rst connection to each extra packet of i at t1;i:
(B1) If jF t1;i j = 2 then all LQD packets are currently not connected at t1;i. Hence, we assign at t1;i one connection to each extra packet of i with a di erent common packet of i. The number of extra packets of i at t1;i is at most equal to the number of common packets of i at t1;i, by De nition 7. It follows that the number of common packets of i su ces for these connections at t1;i and Invariant 1 holds at t1;i. Each connection is valid, by Observation 4.
(B2) If jF t1;i j = 1, then one other dominating (or established) queue j 6= i
may exist at t1;i. Let us denote as w 6= fi; jg the single free queue we have at t1;i.
By Lemma 4 it is e(t1;i) f (t1;i) 1. Also, it is f (t1;i) = ptw1;;LiQD pit;1L;iQD + 1
due to Observation 1. By the last two inequalities, we get:
pit;1L;iQD
(
By (
Finally, by Lemmas 4 and 13, we assign a second connection to each extra packet of i with a di erent and currently not connected free packet at t1;i. This second connection is valid by Observation 4.
Upper-bounding the LQD Competitive Ratio, when N = 3 The connection assignment process that we described in Cases 1 and 2, is applied for every queue k 2 [N ] and at each t1;kk time step ( k 2 [ k]).
Lemma 15. Invariant 1 holds at every time step of [1; T ].
Proof. Invariant 1 may be violated only at a time step when a connection between an extra packet and an already connected LQD packet is assigned. But we showed in both Cases 1 and 2 that at any time step when a connection is assigned to an extra packet of i 2 [N ], Invariant 1 is not violated. tu Lemma 16. For any transmitted extra packet e, it holds con(e; t) = 2 where t 2 [T ] denotes the transmission time step of e.
Proof. (see Appendix). tu
By Lemmas 15 and Lemma 16, it follows that 2 PtT=1 jEtj h (LQD),
for any incoming packet sequence . Therefore, by (
Appendix
First, let us say that at least one queue over ows in the LQD bu er at t. Assume for contradiction that f (t) < e(t) + Pi2F t pit;OPT , that is Pi2F t pit;LQD < Pi2Dt[Et (pit;OPT pit;LQD ) + Pi2F t pit;OPT , which gives us the next inequality: X pi;LQD +
t i2F t
X pi;LQD <
t i2Dt
X pi;OPT +
t i2Dt
X pi;OPT +
t i2Et
X pi;OPT
t
i2F t
(
The left hand side of (
Now, assume that no queue over ows at t in the LQD bu er and let t0 < t be
the latest time step before t when a queue over owed in the LQD bu er (if time
step t0 < t does not exist, then the lemma holds trivially at t, since no extra
packets may exist in the OPT bu er at t). By the argument of the rst two
paragraphs of this proof, it holds f (t0) P t0 e(t0). Also, it holds
e(t0) e(t), since no new extra packets arei2oFbtt0apini;OedPTin the period [t0 + 1; t],
according to our assumption that no queue over ows in the LQD bu er, in this
period. By the last two inequalities, we have:
By (
queue. But this contradicts the de nition of time step t2;ii.
f (t0)
X pi;OPT
t0 i2F t0 e(t)
Since no queue over ows in the LQD bu er, in the period [t0 + 1; t], it follows by Lemma 3 that any queue that is a free queue at t0 will stay a free queue at every time step of the period [t0 + 1; t] and that any arriving packet destined to a free queue in [t0 + 1; t] will be accepted by the LQD bu er. This gives us the next inequality:
X pi;LQD
t i2F t
X pi;OPT
t i2F t
X pi;LQD
t0 i2F t0
X pi;OPT
t0 i2F t0 By (8) and since f (t) = Pi2F t pit;LQD and f (t0) = Pi2F t0 pit;0LQD , we have: f (t)
X pi;OPT
t i2F t f (t0)
X pi;OPT
t0 i2F t0 Pi2F t pit;OPT e(t), completing the proof.
(
But then, i has to over ow in the LQD bu er after t so that it becomes a dominating queue before t2;ii (due to Lemma 2). But this contradicts the de nition of time step t1;ii.
Finally, i cannot become an inactive queue in both bu ers at a time step t 2 [t1;ii; t2;ii 1], since i has to over ow in the LQD bu er as a dominating queue after t and before t2;ii, due to Lemma 2. But this contradicts the de nition of time step t1;ii.
By the arguments of the rst three paragraphs of this proof and Corollary 1, the lemma follows. tu A.3
For the number of extra packets of i to strictly increase between two consecutive time steps t and t + 1 both of which belonging to a period [t1;ii; t2;ii], the queue i has to over ow in the LQD bu er at time step t + 1 as a dominating queue. But this contradicts the de nition of time step t1;ii (if (t + 1) 2 [t1;ii + 1; t2;ii 1]), or the de nition of time step t2;ii (if (t + 1) = t2;ii). tu A.4
Assume that the number of transmitted extra packets of i in the period [t2;ii; t1;ii+1 1] (for a i 2 [ i 1]) is strictly greater than pit;2O;iiPT (which equals the number of extra packets that i has at t2;ii, since i is an established queue at this time step). But this means that: { The queue i has over owed in the LQD bu er as a dominating queue, in at least one time step of the period [t2;ii; t1;ii+1 1] (let us denote as t0 the 1] when i over ows as a dominating rst time step in the period [t2;ii; t1;ii+1 queue in the LQD bu er) and { The queue i is an established queue in at least one time step of the period [t0 + 1; t1;ii+1 1].
happen for the strict total order de ned before. This completes the proof for the rst statement of the lemma.
Working in the same way, we prove the second statement, i.e., that the number of extra packets that i 2 [N ] has at time step t2;ii, upper-bounds the number of transmitted extra packets of i in the period [t2;ii; T ]. tu A.5
the LQD bu er, i.e., it will be transmitted by the LQD bu er at a time step of the period [t1;ii; t2;ii 1] since i becomes inactive in the LQD bu er at t2;i.
Also, the packet c will stay a common packet at each time step until its transmission by the LQD bu er. This is because i cannot become a free queue at any time step of the period [t1;ii; t2;ii 1], by Lemma 5. Since the free packets are kept only by free queues and because any LQD packet can be either a free packet or a common packet at the same time step, the proof follows. A.6
First of all, it cannot be jF tj = 0, because at least one extra packet of i exists in the OPT bu er at t; therefore at least one free packet must exist in the LQD bu er at t due to Lemma 4. Also, it has to be jF tj < N = 3 since i is a dominating queue at t and, hence, not a free queue at t.
Assume for contradiction that jF tj = 1. The number of extra packets of i t at t is at least pi;LQD + 1, by De nition 7. Therefore, by Lemmas 1 and 4, we have f (t) (pit;LQD + 1) + jF tj = pit;LQD + 2. But a single free queue at t cannot have pit;LQD + 2 free packets, since i over ows at t in the LQD bu er and due to Observation 1. Hence, it cannot be jF tj = 1 and, therefore, it has to be jF tj = 2. tu A.7
If a dominating queue over ows in the LQD bu er at t, the lemma follows from Lemmas 4 and 10. If no dominating queue over ows at t, then let t0 be the latest time step before t > t0 when a dominating queue over owed in the LQD bu er; hence we have e(t0) e(t) since no new extra packets are obtained in the period [t0 + 1; t], according to our hypothesis that no dominating queue over ows in the LQD bu er in [t0 + 1; t].
By Lemma 4, at any time step when at least one extra packet exists in the OPT bu er, at least one free packet has to exist in the LQD bu er; therefore it is jF t0 j 1. But it cannot be jF t0 j = 2, since a free queue has to become dominating at a time step of the period [t0 + 1; t] so that it holds jF tj = 1. To see that, note that in order for a free queue at any time step tf 2 [T 1] to become dominating at tf + 1, this queue has to over ow in the LQD bu er at tf + 1. This contradicts our assumption that no dominating queue over ows in [t0 +1; t]. Therefore, it has to be jF t0 j = 1. By Lemmas 4 and 10 and since e(t0) e(t), the proof is complete. tu A.8
The lemma holds for each common packet of i that is assigned a connection at t1;i, since i becomes an established queue at t2;i and therefore it is inactive in the LQD bu er at t2;i.
Now, for the free packets that are assigned connections at t1;i, it su ces to show that we only assign connections at t1;i to free packets each of which is located at a queue position at most equal to pit;1L;iQD at this time step. But, by Lemmas 4 and 9, the number of free packets in the LQD bu er at t1;i is at least equal to the number of extra packets of i at t1;i, plus 2. Therefore, we do not need to assign connections to the at most two free packets that may be located at a queue position equal to pit;1L;iQD + 1 at t1;i (by Observation 1). It follows that the maximum queue position at t1;i of any free packet which is assigned a connection at t1;i is pit;1L;iQD, which completes the proof.
was either primary dominating or secondary dominating at the latest time step before t, when i over owed in the LQD bu er, due to Lemma 2 and Observation 3. Denoting this time step as t1;i = t1;ii, for some i 2 [ i], we shall distinguish between two cases.
Before doing so, recall, that (see Fact 1) if an extra packet becomes nonextra, then we transfer all its connections and associations to the inferior extra packet of it, which is located at the smaller queue position of the same queue, if such an inferior extra packet exists.
Let us start with the case that i was secondary dominating at t1;i = t1;ii: Each extra packet of i is assigned two connections at t1;i, as we describe in the analysis of Case 2. Due to Lemmas 6 and 7, the number of transmitted extra packets of i in the period [t2;ii; t1;ii+1 1] is at most equal to the number of extra packets that i has at t1;i. By the argument of the previous paragraph, it follows that for each transmitted extra packet e of i, it has to be con(e; t) = 2 at its transmission time step t 2 [t2;ii; t1;ii+1 1].
Assume, now, that i was primary dominating at t1;i = t1;ii (i.e., Case 1). At t1;i = t1;ii we assigned two connections to each of the lit1;i lower extra packets of i and one connection to each of the upper uit1;i extra packets of i. At t2;i = t2;ii we assigned one connection to each of the pit;2O;iPT lit1;i extra packets of i (if pit;2O;iPT > lit1;i ) or none connection (if pit;2O;iPT lit1;i ). Hence, by Lemma 6 and the argument of the second paragraph of this proof, we have that each extra packet of i at t2;i has two connections or associations at t2;i (after the connections at time step t2;i take place). Therefore, by Lemma 7, we have that for each extra packet e transmitted by i at a time step t 2 [t2;ii; t1;ii+1 1], it is con(e; t) = 2. tu