=Paper=
{{Paper
|id=Vol-1548/043-Matsakis
|storemode=property
|title=LQD is 1.5-competitive for 3-port Shared-Memory Switches
|pdfUrl=https://ceur-ws.org/Vol-1548/043-Matsakis.pdf
|volume=Vol-1548
|authors=Nicolaos Matsakis
|dblpUrl=https://dblp.org/rec/conf/sofsem/Matsakis16
}}
==LQD is 1.5-competitive for 3-port Shared-Memory Switches==
https://ceur-ws.org/Vol-1548/043-Matsakis.pdf
LQD is 1.5-competitive for 3-port
Shared-Memory Switches
Nicolaos Matsakis
Department of Computer Science and Centre for Discrete Mathematics
and its Applications (DIMAP), University of Warwick
nmatsakis@dcs.warwick.ac.uk
Abstract. We show that the Longest Queue Drop algorithm is
1.5-competitive for shared-memory switches with three output ports.
1 3
This improves upon the previous best upper bound of (2− M ·bM/3c− M )
for the competitive ratio of the Longest Queue Drop algorithm, for 3-port
shared-memory switches, where M denotes the shared-memory size.
1 Introduction
The area of memory management is strongly related to that of online computa-
tion, 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 buffers,
comes as no surprise.
A shared-memory switch is a buffer 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 immedi-
ately accepted by the buffer 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 buffer. At any time step, one packet
is transmitted by each output port of the switch, to which at least one packet
stored in the buffer is destined.
Since there may exist at most three different types of packets stored in the
buffer at any time, we may assume that the packets stored in the buffer 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 buffer 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 buffer
if there exists free buffer space at the time step when this packet arrives. If the
buffer is full at the time step when the packet arrives, a packet is preempted from
the longest queue in the buffer at this point in time, releasing buffer space for the
arriving packet which is accepted. After all packet acceptances and preemptions
44 N. Matsakis
take place, at each time step, one packet of each queue is forwarded from the
buffer 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 Related Work
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 2-
competitive, when the number of output ports N ≥ 2 of the switch is assumed
to be arbitrary.
−4
Kobayashi et al. [6], show a tight upper bound of 4M 4
3M −2 < 3 for the LQD
competitive ratio for 2-port shared-memory switches, where M ∈ Z+ denotes
1 N
the buffer size. In [6], an upper bound of (2 − M · bM/N c − M ) is, also, shown
for the LQD competitive ratio. This bound tends to 5/3 as M → ∞ 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 Preliminaries
2.1 An Optimal Offline Algorithm
Both LQD and OPT are assumed to use their own buffers, 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 buffer. Analysis will proceed by comparing the two buffer
contents. As [n] we denote the set {1, ..., n} 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 buffer will be called ALG
packet, in short.
All definitions that follow until the end of the current paragraph, refer to the
buffer content of ALG, after all packet acceptances, rejections and preemptions
have taken place, at each time step: We denote as pti,ALG the length of a queue
i ∈ [N ] in the ALG buffer at a time step t ∈ [T ]. A queue i ∈ [N ] is said to be
active in the ALG buffer at a time step t ∈ [T ] if pti,ALG > 0, else i is inactive in
the ALG buffer at t. As `tALG (q) ∈ [M ], we denote the queue position of a packet
q in the ALG buffer, at a time step t ∈ [T ].
Let t1 ∈ [T ] and t2 ∈ [T ] be two time steps such that t1 ≤ t2 . As period we
call the set of consecutive time steps from t1 , inclusive, to t2 , inclusive and we
denote the period as [t1 , t2 ].
LQD is 1.5-competitive for 3-port ... 45
If a packet destined to a queue i ∈ [N ], is rejected or preempted from the
LQD buffer at a time step t ∈ [T ], we say that i overflows in the LQD buffer at
t. At any time step when the LQD buffer overflows, this buffer is full.
Observation 1 The lengths of two queues in the LQD buffer, that overflowed
in the LQD buffer at the same time step t ∈ [T ], may differ 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.
We define as T 0 -balanced any algorithm ALG0 such that if pti,LQD ≥ 1 then
pti,ALG 0 ≥ 1, for each queue i ∈ [N ] and at each time step t ∈ [T 0 ], where T 0 ≤ T .
Since M ≥ N , no (offline 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 buffer 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 offline algorithm which is T -balanced and
which never preempts any packet.
Proof. Let ALG1 be an offline algorithm which is t0 -balanced but not (t0 + 1)-
balanced, where t0 ∈ [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.
t0 +1 0
It is pj,ALG 1
= 0 and ptj,LQD
+1
> 0 for a queue j ∈ [N ], because ALG1 is t0 -
0
balanced but not (t + 1)-balanced. But then, there has to exist a queue k 6= j
and a time step t00 ≤ t0 + 1 so that:
00 00
– It holds ptk,LQD < ptk,ALG1 or
00
– The sum of the empty ALG1 buffer space at t00 and ptk,ALG1 is strictly greater
00
than ptk,LQD .
In case two or more different pairs of queues and time steps {k, t00 } exist, as
defined 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
00 00
[1, t0 + 1]. For this, one packet less for k (if ptk,LQD < ptk,ALG1 ) may need to be
accepted by the modified algorithm, at the latest overflow time step in the LQD
buffer 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 buffer at t0 + 1.
46 N. Matsakis
Working as above, we obtain a sequence of algorithms ALG1 , . . . , ALGv (for
a v ∈ Z+ ), where ALG1 , . . . , ALGv−1 are not T -balanced, ALGv is T -balanced
and it holds hσ (ALGl ) ≥ hσ (ALGl−1 ) for each l ∈ [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. t
u
2.2 Classifying the Queues and Packets
A queue i ∈ [N ] is called as established at t ∈ [T ], if pti,LQD = 0 and pti,OPT > 0.
If pti,LQD > pti,OPT then i is a free queue at t, else if 1 ≤ pti,LQD ≤ pti,OPT then i
is a dominating queue at t. We denote as Dt , E t , F t , the sets of dominating,
established and free queues, respectively, at t ∈ [T ].
An OPT packet q of a queue i ∈ Dt at a time step t ∈ [T ], for which it holds
`OPT (q) > pti,LQD , is called extra packet at t. An OPT packet of an established
t
queue at a t ∈ [T ] is, also, called extra packet at t. An LQD packet of a queue
i ∈ F t at a time step t ∈ [T ], is called free packet at t. An LQD packet of
a dominating queue at a t ∈ [T ] is called common packet, at t.
We denote as e(t) ≥ 0 the number of extra packets in the OPT buffer at
t ∈ [T ] and as f (t) ≥ 0 the number of free packets in the LQD buffer, at t.
By Lemma 1, a queue cannot be inactive in the OPT buffer and active in the
LQD buffer at the same time step. This gives us the next corollary:
Corollary 1. Any queue at any time step t ∈ [T ] can either belong to set Dt or
to set F t or to set E t or be inactive in both buffers at t.
By Corollary 1, the ratio of transmitted packets between OPT and LQD, for
an incoming packet sequence σ, is defined as:
Pt=T t
hσ (OPT) |E |
rσ = = 1 + t=1 ≥1 (1)
hσ (LQD) hσ (LQD)
The numerator of the fraction in the right hand side of (1) equals the number
of transmitted extra packets in [1, T ], i.e., the number of OPT packets which are
extra packets when transmitted by the OPT buffer. The denominator equals the
number of LQD packets transmitted in [1, T ].
Observation 3 Since M ≥ N , if a queue i ∈ [N ] is inactive in the LQD buffer
at a time step t ∈ [T − 1] and at least one packet arrives destined to i at t + 1,
then i will be active in the LQD buffer at t + 1.
Lemma 2. If i ∈ E t+1 for any queue i ∈ [N ] at any time step t ∈ [T − 1], then
it is i ∈ Dt ∪ E t .
Proof. First, we show that if i ∈ E t+1 then pti,OPT > 0: Assume that pti,OPT = 0
and, therefore, that it holds pti,LQD = 0 due to Lemma 1. If no packet arrives to
/ E t+1 by the definition of an established queue. Otherwise, if
i at t + 1, then i ∈
LQD is 1.5-competitive for 3-port ... 47
at least one packet arrives destined to i at t + 1 then i has to be active in the
/ E t+1 .
LQD buffer at t + 1, by Observation 3; therefore it is i ∈
t+1
We, now, show that if i ∈ E / F : Assume that i ∈ F t . The length
then i ∈ t
of a free queue in the LQD buffer at any time step is at least 2, by the definition
of a free queue and Lemma 1; hence since i ∈ F t then i has to be active in the
/ E t+1 .
LQD buffer at t + 1 and, therefore, it has to be i ∈
By Corollary 1 and the arguments of the first two paragraphs of this proof,
the lemma follows. t
u
Lemma 3. If i ∈ F t for any queue i ∈ [N ] at any time step t ∈ [T − 1], then it
holds i ∈ F t+1 ∪ Dt+1 .
Proof. The length of a free queue in the LQD buffer is at least 2, by the definition
of a free queue and Lemma 1. It follows that pti,LQD ≥ 2. But then, i has to be
active in the LQD buffer at t + 1, which by Corollary 1, completes the proof. t u
Lemma 4. It holds f (t) ≥ e(t) + i∈F t pti,OPT at any time step t ∈ [T ].
P
Proof. (see Appendix). t
u
Assume, now, that i ∈ E t at a time step t ∈ [T ] for a queue i ∈ [N ]. We
denote as tλ1,ii ∈ [T ] the latest time step in the period [1, t] when i overflowed in the
LQD buffer as a dominating queue and we know that such a time step exists by
Lemma 2 and Observation 3. Also, we denote as tλ2,ii ≤ t the first time step after
tλ1,ii when i becomes an established queue, where the superscript λi ∈ Z+ will be
defined shortly. This gives us a strict total order: t11,i < t12,i < t21,i < t22,i < ...,
where the superscript denotes each pair of two consecutive time steps in the
total order, starting from pair {t11,i , t12,i }, then pair {t21,i , t22,i } etc. Finally, let
us say that we have Λi ∈ Z+ pairs of time steps in this total order, i.e., it holds
t11,i < t12,i < ... < tΛ Λi
1,i < t2,i and, hence, λi ∈ [Λi ].
i
For example, assume that a queue i ∈ [N ] becomes established for the first
time in [1, T ] at time step 10. Then, it is t12,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 ∈ [Λj ]). By
Lemma 2 and Observation 3, it follows that i has overflowed in the LQD buffer 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 overflow is time step
7, i.e., t11,i = 7. Assume, also, that the first time step after t12,i = 10 when i
overflows as a dominating queue in the LQD buffer is time step 30 and the first
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
overflows as a dominating queue in the LQD buffer. This concludes our example.
Lemma 5. The queue i ∈ [N ] is a dominating queue at each time step of the
period [tλ1,ii , tλ2,ii − 1], for any λi ∈ [Λi ].
Proof. (see Appendix). t
u
48 N. Matsakis
Lemma 6. The number of extra packets of any queue i ∈ [N ] cannot strictly
increase between any two consecutive time steps of the period [tλ1,ii , tλ2,ii ], for any
λi λi
λi ∈ [Λi ], i.e., it holds pti,OPT − pti,LQD ≥ pt+1 t+1
i,OPT − pi,LQD , where t ∈ [t1,i , t2,i − 1].
Proof. (see Appendix). t
u
Lemma 7. The number of extra packets of any queue i ∈ [N ] at any time step
tλ2,ii (for any λi ∈ [Λi − 1]) upper-bounds the number of transmitted extra packets
of i in the period [tλ2,ii , tλ1,ii +1 − 1]. Also, the number of extra packets of i at tΛ i
2,i
Λi
upper-bounds the number of transmitted extra packets of i in the period [t2,i , T ].
Proof. (see Appendix). t
u
2.3 Introducing the Packet Connections
We shall work similarly to Aiello et al. [1], assigning connections between extra
packets and LQD packets.
Definition 1. A connection between an extra packet e and an LQD packet e0
which is assigned at a time step t ∈ [T ] when both packets are in their respective
buffers, 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 ∈ [T ], if:
– These packets were assigned the connection between them at a t0 ∈ [1, t] and
– These two packets remain connected together at each time step of [t0 , t] and
– These two packets are in their respective buffers at t.
Fact 1 From the time step tc ∈ [T ] when an extra packet x is assigned a con-
nection 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 buffer at t0c but it is not an extra packet at t0c .
In the first 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 Definition 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 first need Definitions 2 and 3:
LQD is 1.5-competitive for 3-port ... 49
OP T OP T OP T
p0 p0
p LQD
p p
LQD
LQD LQD
i j i j i j
Fig. 1. In the figure we have two queues (i and j 6= i) and in orange color we identify
the extra packets of i. Left: At time step t0c − 1 the extra packet p is connected with an
LQD packet (bold line segment) and associated with a transmitted LQD packet (dotted
line segment). Center : At t0c the OPT packet p becomes a non-extra packet because i
accepts packets in the LQD buffer; therefore we assign (on the right, again at time step
t0c ) to an inferior extra packet p0 of the same queue i the connection and association
that p had, after deleting the single connection of p0
Definition 2. As con(e, t) ≥ 0, we define the number of LQD packets that an
extra packet e (which is in the OPT buffer at a time step t ∈ [T ]) is connected
with at t, plus the number of transmitted LQD packets associated with e at t.
Definition 3. Let p and p0 6= p be two extra packets belonging to the same queue
i ∈ [N ] in the OPT buffer, at a time step t ∈ [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
Definition 4. A valid connection between an extra packet e of a queue i ∈ [N ]
and an LQD packet c, which is assigned at a time step tλ1,ii (for any λi ∈ [Λi ]),
is called strong connection, if c is a common packet of i at this tλ1,ii time step.
By Observation 1 and Definition 1 we have Observation 4.
50 N. Matsakis
Observation 4 A connection that is assigned to an extra packet of a queue
i ∈ [N ] at any of its tλ1,ii time steps (λi ∈ [Λi ]) is valid.
Lemma 8. Assume that an extra packet of a queue i ∈ [N ] is assigned a strong
connection with an LQD packet c at a tλ1,ii time step (for a λi ∈ [Λi ]). Then, c will
never be preempted and will never become a free packet until its transmission.
Proof. (see Appendix). t
u
Definition 5. Assume that i ∈ Dt at a time step t ∈ [T ]. Then, the upmost h
extra packets of i at t (where h ∈ Z+ ) are the h extra packets of i that occupy
the h greatest queue positions of i at t.
Definition 6. An extra packet s of a queue i ∈ [N ] for which it holds `tOP T (s) >
2 · pti,LQD at a time step t ∈ [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.
Let lit ≥ 0 and uti ≥ 0 denote the numbers of lower and upper extra packets,
respectively, that a queue i ∈ [N ] has at a time step t ∈ [T ].
Definition 7. If 2 · pti,LQD < pti,OPT at a time step t ∈ [T ] for a queue i ∈ [N ],
then i is called primary dominating queue at t else if 2 · pti,LQD ≥ pti,OPT then i
is called secondary dominating queue at t.
By Observation 1 and since M ≥ N , we have Observation 5:
Observation 5 At any t ∈ [T ] when a packet of a queue i ∈ [N ] is preempted
or rejected from the LQD buffer, it holds pti,LQD ≥ bM/N c.
Lemma 9. If a queue i ∈ [N ] overflows in the LQD buffer at a time step t ∈ [T ]
and i is a primary dominating queue at t, then it holds |F t | = 2.
Proof. (see Appendix). t
u
Lemma 10. If i ∈ F t and a dominating queue overflows in the LQD buffer at
t, then pti,LQD ≤ dM/2e.
Proof. Assume for contradiction that pti,LQD ≥ M/2 + 1. By Observation 1, the
length of the dominating queue that overflows in the LQD buffer at t, is at least
equal to the length of i in the LQD buffer at t, minus 1. Taking the sum of the
packet numbers for these two queues at t in the LQD buffer, it follows that at
least M + 1 packets exist in the LQD buffer at t, which cannot happen. t
u
Lemma 11. If |F t | = 1 then it is e(t) ≤ dM/2e, at any time step t ∈ [T ].
Proof. (see Appendix). t
u
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 ∈ [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.
LQD is 1.5-competitive for 3-port ... 51
Lemma 12. Each extra packet of any queue i ∈ [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. t
u
Lemma 13. Any extra packet may be connected with at most one free packet,
at any time step of [1, T ].
Proof. The lemma follows by Lemma 12 and the definition of a free packet. t
u
3.1 Assigning the Packet Connections
We shall, now, assign connections between extra packets and LQD packets, prov-
ing that the next invariant holds at every time step t ∈ [1, T ]:
Invariant 1 No LQD packet is connected with two or more extra packets at t.
Hence, assume that a queue i ∈ [N ] overflows in the LQD buffer at a tλ1,ii time
step (for a λi ∈ [Λi ]). For simplicity, let t1,i = tλ1,ii and t2,i = tλ2,ii . We distinguish
between the cases that i is primary dominating or secondary dominating, at t1,i :
Case 1: The queue i is primary dominating at t1,i
By Lemma 9, it is |F t1,i | = 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 buffer at t1,i .
We assign one connection to each lower extra packet of i at t1,i with a different
common packet of i. The number of common packets of i at t1,i suffices so that
each lower extra packet of i is assigned one connection, by Definition 6. We, also,
assign one connection to every extra packet of i with a different free packet at
t1,i . The number of free packets at t1,i suffices to assign one connection to each
extra packet of i with a different 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 buffer at time step t2,i > t1,i may be con-
nected with a connection which was assigned at time step t1,i .
Proof. (see Appendix). t
u
t t
If li 1,i ≥ pi,OPT
2,i
then the connection assignment for Case 1 is complete.
t t
Otherwise, if li 1,i < pi,OPT
2,i
, we distinguish between sub-cases (A1), (A2) and
(A3):
(A1) If |F t2,i | = 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
52 N. Matsakis
t
ui1,i
OP T
t LQD
`i1,i
OP T OP T
LQD LQD LQD
LQD
i F t1,i i w j
Fig. 2. An example of the connection assignment of Case 1. Left: The queue i overflows
at t1,i . Each lower extra packet of i is assigned two connections and each upper extra
packet of i, one connection. On the right we have sub-case (A2): At t2,i all connected
LQD packets from t1,i have left the buffer (dotted line segments) and we assign one
t2,i t
connection to each of the (pi,OPT − li 1,i ) upmost extra packets of i at t2,i . Even if
another dominating queue j exists at t2,i and each of j’s extra packets is connected
with one free packet, Invariant 1 is not violated at t2,i
2,i t t
assign a connection at t2,i to each of the upmost pi,OPT − li 1,i extra packets of
i at t2,i , with a different free packet. By Lemma 4, the number of free packets
suffices for these connections to be assigned at t2,i and Invariant 1 holds at t2,i .
(A2) If |F t2,i | = 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= {i, w} (see Figure 2). By
t1,i t
Observation 5 it is pi,LQD ≥ bM/3c, which by Definition 6 gives us li 1,i ≥ bM/3c.
By the last inequality and since e(t2,i ) ≤ dM/2e, it is:
t
2 · li 1,i ≥ e(t2,i ) − 1 (2)
But the number of extra packets in the OPT buffer 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 :
2,i t 2,i t 2,i t
e(t2,i ) = (pj,OPT − pj,LQD ) + pi,OPT (3)
t t
By (2), (3) and since we have assumed that li 1,i < pi,OPT
2,i
, it holds:
t t t
li 1,i ≥ pj,OPT
2,i 2,i
− pj,LQD (4)
2,i t t
Hence, we assign a valid connection to each of the upmost (pi,OPT − li 1,i )
extra packets of i, without violating Invariant 1 at t2,i . This is because each of
LQD is 1.5-competitive for 3-port ... 53
t
2,i t
the upmost (pi,OPT − li 1,i ) extra packets of i at t2,i , is located at a queue position
t
at t2,i which is at least equal to li 1,i . But, by (4) and Lemma 13, the number of
t
free packets already connected with extra packets of j at t2,i is at most li 1,i .
(A3) It cannot be |F t2,i | = 0, since at least one extra packet of i exists in
the OPT buffer, at t2,i . Therefore, by Lemma 4, it has to be |F t2,i | ≥ 1.
Case 2: The queue i is secondary dominating at t1,i
OP T
LQD OP T
LQD
i w j
Fig. 3. An example of the connection assignment of Case 2: One connection to each
extra packet of i is assigned with a common packet of i at t1,i . A second connection is
assigned with a free packet, at the same time step
We distinguish between sub-cases (B1), (B2) and (B3), for the first connec-
tion to each extra packet of i at t1,i :
(B1) If |F t1,i | = 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 different
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 Definition 7. It follows that
the number of common packets of i suffices for these connections at t1,i and
Invariant 1 holds at t1,i . Each connection is valid, by Observation 4.
(B2) If |F t1,i | = 1, then one other dominating (or established) queue j 6= i
may exist at t1,i . Let us denote as w 6= {i, j} the single free queue we have at t1,i .
t1,i t1,i
By Lemma 4 it is e(t1,i ) ≤ f (t1,i ) − 1. Also, it is f (t1,i ) = pw,LQD ≤ pi,LQD +1
due to Observation 1. By the last two inequalities, we get:
t1,i
e(t1,i ) ≤ pi,LQD (5)
54 N. Matsakis
By (5) and Lemma 12, the number of common packets of i that are not cur-
rently connected at t1,i with extra packets of j, is at least equal to the number of
extra packets of i at t1,i . Hence, we assign a connection to each extra packet of
i with a different common packet of i at t1,i , without violating Invariant 1 at t1,i .
(B3) It cannot be |F t1,i | = 0, for the same reason as in sub-case (A3).
Finally, by Lemmas 4 and 13, we assign a second connection to each extra
packet of i with a different and currently not connected free packet at t1,i . This
second connection is valid by Observation 4.
3.2 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 ∈ [N ] and at each tλ1,k
k
time step (λk ∈ [Λ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 be-
tween 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 ∈ [N ], Invariant 1 is not violated. t
u
Lemma 16. For any transmitted extra packet e, it holds con(e, t) = 2 where
t ∈ [T ] denotes the transmission time step of e.
Proof. (see Appendix). t
u
PT
By Lemmas 15 and Lemma 16, it follows that 2 · t=1 |E t | ≤ hσ (LQD),
for any incoming packet sequence σ. Therefore, by (1), we have that LQD is
1.5-competitive for 3-port shared-memory switches.
References
1. Aiello, W., Kesselman, A., Mansour, Y.: Competitive buffer management for
shared-memory switches. ACM Transactions on Algorithms, vol. 5(1) (2008)
2. Chao, H.J., Guo,X.: Quality of Service Control in High-Speed Networks. Wiley-
IEEE Press (2001)
3. Chao, H.J., Liu, B.: High Performance Switches and Routers. Wiley-IEEE Press
(2007)
4. Goldwasser, M.H.: A survey of buffer management policies for packet switches.
SIGACT News, vol. 41(1), pp. 100–128 (2010)
5. Hahne, E.L., Kesselman, A., Mansour, Y.: Competitive buffer management for
shared-memory switches. In:SPAA, pp. 53–58 (2001)
6. Kobayashi, K.M., Miyazaki, S., Okabe, Y.: A tight bound on online buffer man-
agement for two-port shared-memory switches. In SPAA, pp. 358–364 (2007)
7. Wei, S.X., Coyle, E.J., Hsiao, M.T.: An optimal buffer management policy for high-
performance packet switching. In: Proc. IEEE GLOBECOM ’91, vol. 2 (1991)
LQD is 1.5-competitive for 3-port ... 55
A Appendix
A.1 Proof of Lemma 4
First, let us say that at least one queue P overflows in the LQD P buffer at t. As-
sume for contradiction that f (t) < e(t) + i∈F t pti,OPT , that is i∈F t pti,LQD <
t t t
P P
i∈D t ∪E t (pi,OPT − pi,LQD ) + i∈F t pi,OPT , which gives us the next inequality:
X X X X X
pti,LQD + pti,LQD < pti,OPT + pti,OPT + pti,OPT (6)
i∈F t i∈D t i∈D t i∈E t i∈F t
The left hand side of (6) equals M , since the LQD buffer becomes full at
t. But the right hand side of (6) lower-bounds the OPT buffer size which has
to be P equal to M . Therefore, we obtain a contradiction and it holds f (t) ≥
e(t) + i∈F t pti,OPT .
Now, assume that no queue overflows at t in the LQD buffer and let t0 < t be
the latest time step before t when a queue overflowed in the LQD buffer (if time
step t0 < t does not exist, then the lemma holds trivially at t, since no extra
packets may exist in the OPT buffer at t). P By the0 argument of the first two
paragraphs of this proof, it holds f (t0 ) − i∈F t0 pti,OPT ≥ e(t0 ). Also, it holds
e(t0 ) ≥ e(t), since no new extra packets are obtained in the period [t0 + 1, t],
according to our assumption that no queue overflows in the LQD buffer, in this
period. By the last two inequalities, we have:
X 0
f (t0 ) − pti,OPT ≥ e(t) (7)
i∈F t0
Since no queue overflows in the LQD buffer, 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 buffer. This gives us the
next inequality:
X X X 0 X 0
pti,LQD − pti,OPT ≥ pti,LQD − pti,OPT (8)
i∈F t i∈F t i∈F t0 i∈F t0
t0
t
and f (t0 ) =
P P
By (8) and since f (t) = i∈F t pi,LQD i∈F t0 pi,LQD , we have:
X X 0
f (t) − pti,OPT ≥ f (t0 ) − pti,OPT (9)
i∈F t i∈F t0
t
P
By (7) and (9), we have f (t) − i∈F t pi,OPT ≥ e(t), completing the proof. t
u
A.2 Proof of Lemma 5
Assume that there exists a time step t ∈ [tλ1,ii , tλ2,ii − 1], when i is an established
queue. But this contradicts the definition of time step tλ2,ii .
56 N. Matsakis
Assume that there exists a time step t ∈ [tλ1,ii , tλ2,ii − 1] when i is a free queue.
But then, i has to overflow in the LQD buffer after t so that it becomes a do-
minating queue before tλ2,ii (due to Lemma 2). But this contradicts the definition
of time step tλ1,ii .
Finally, i cannot become an inactive queue in both buffers at a time step
t ∈ [tλ1,ii , tλ2,ii − 1], since i has to overflow in the LQD buffer as a dominating queue
after t and before tλ2,ii , due to Lemma 2. But this contradicts the definition of
time step tλ1,ii .
By the arguments of the first three paragraphs of this proof and Corollary 1,
the lemma follows. t
u
A.3 Proof of Lemma 6
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 [tλ1,ii , tλ2,ii ], the queue i
has to overflow in the LQD buffer at time step t + 1 as a dominating queue. But
this contradicts the definition of time step tλ1,ii (if (t + 1) ∈ [tλ1,ii + 1, tλ2,ii − 1]), or
the definition of time step tλ2,ii (if (t + 1) = tλ2,ii ). t
u
A.4 Proof of Lemma 7
Assume that the number of transmitted extra packets of i in the period [tλ2,ii , tλ1,ii +1
λ
2,it i
− 1] (for a λi ∈ [Λi − 1]) is strictly greater than pi,OPT (which equals the number
λi
of extra packets that i has at t2,i , since i is an established queue at this time
step). But this means that:
– The queue i has overflowed in the LQD buffer as a dominating queue, in
at least one time step of the period [tλ2,ii , tλ1,ii +1 − 1] (let us denote as t0 the
first time step in the period [tλ2,ii , tλ1,ii +1 − 1] when i overflows as a dominating
queue in the LQD buffer) and
– The queue i is an established queue in at least one time step of the period
[t0 + 1, tλ1,ii +1 − 1].
But the second argument, above, implies that tλ2,ii +1 < tλ1,ii +1 which cannot
happen for the strict total order defined before. This completes the proof for the
first statement of the lemma.
Working in the same way, we prove the second statement, i.e., that the num-
ber of extra packets that i ∈ [N ] has at time step tΛ2,i , upper-bounds the number
i
of transmitted extra packets of i in the period [tΛ2,i , T ].
i
t
u
A.5 Proof of Lemma 8
By the definition of time step tλ1,ii , we have that c will never be preempted from
the LQD buffer, i.e., it will be transmitted by the LQD buffer at a time step of
the period [tλ1,ii , tλ2,ii − 1] since i becomes inactive in the LQD buffer at t2,i .
LQD is 1.5-competitive for 3-port ... 57
Also, the packet c will stay a common packet at each time step until its
transmission by the LQD buffer. This is because i cannot become a free queue
at any time step of the period [tλ1,ii , tλ2,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. t
u
A.6 Proof of Lemma 9
First of all, it cannot be |F t | = 0, because at least one extra packet of i exists
in the OPT buffer at t; therefore at least one free packet must exist in the
LQD buffer at t due to Lemma 4. Also, it has to be |F t | < N = 3 since i is
a dominating queue at t and, hence, not a free queue at t.
Assume for contradiction that |F t | = 1. The number of extra packets of i
at t is at least pti,LQD + 1, by Definition 7. Therefore, by Lemmas 1 and 4, we
have f (t) ≥ (pti,LQD + 1) + |F t | = pti,LQD + 2. But a single free queue at t cannot
have pti,LQD + 2 free packets, since i overflows at t in the LQD buffer and due to
Observation 1. Hence, it cannot be |F t | = 1 and, therefore, it has to be |F t | = 2.
t
u
A.7 Proof of Lemma 11
If a dominating queue overflows in the LQD buffer at t, the lemma follows from
Lemmas 4 and 10. If no dominating queue overflows at t, then let t0 be the latest
time step before t > t0 when a dominating queue overflowed in the LQD buffer;
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 overflows in the
LQD buffer in [t0 + 1, t].
By Lemma 4, at any time step when at least one extra packet exists in the
OPT buffer, at least one free packet has to exist in the LQD buffer; therefore
0 0
it is |F t | ≥ 1. But it cannot be |F t | = 2, since a free queue has to become
dominating at a time step of the period [t0 + 1, t] so that it holds |F t | = 1. To see
that, note that in order for a free queue at any time step tf ∈ [T − 1] to become
dominating at tf + 1, this queue has to overflow in the LQD buffer at tf + 1.
This contradicts our assumption that no dominating queue overflows in [t0 +1, t].
0
Therefore, it has to be |F t | = 1. By Lemmas 4 and 10 and since e(t0 ) ≥ e(t),
the proof is complete. tu
A.8 Proof of Lemma 14
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 buffer at t2,i .
Now, for the free packets that are assigned connections at t1,i , it suffices to
show that we only assign connections at t1,i to free packets each of which is
t1,i
located at a queue position at most equal to pi,LQD at this time step. But, by
58 N. Matsakis
Lemmas 4 and 9, the number of free packets in the LQD buffer 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
t1,i
at a queue position equal to pi,LQD + 1 at t1,i (by Observation 1). It follows
that the maximum queue position at t1,i of any free packet which is assigned
t1,i
a connection at t1,i is pi,LQD , which completes the proof.
t
u
A.9 Proof of Lemma 16
The extra packet e that is transmitted at t ∈ [T ] belongs to a queue i ∈ [N ] that
was either primary dominating or secondary dominating at the latest time step
before t, when i overflowed in the LQD buffer, due to Lemma 2 and Observation
3. Denoting this time step as t1,i = tλ1,ii , for some λi ∈ [Λi ], we shall distinguish
between two cases.
Before doing so, recall, that (see Fact 1) if an extra packet becomes non-
extra, 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 = tλ1,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 [tλ2,ii , tλ1,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 ∈ [tλ2,ii , tλ1,ii +1 − 1].
Assume, now, that i was primary dominating at t1,i = tλ1,ii (i.e., Case 1). At
t
t1,i = tλ1,ii we assigned two connections to each of the li 1,i lower extra packets of
t1,i
i and one connection to each of the upper ui extra packets of i. At t2,i = tλ2,ii
t2,i t
we assigned one connection to each of the pi,OPT − li 1,i extra packets of i (if
t2,i t t t
pi,OPT > li 1,i ) or none connection (if pi,OPT
2,i
≤ li 1,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 ∈ [tλ2,ii , tλ1,ii +1 −1], it is con(e, t) = 2. t
u