On the Maximum Buffer Size Achieved in a Class of Constructions of Optical Priority Queues

I. INTRODUCTION

THE design and implementation of optical buffers for contention resolution among packets competing for the same resources has been well recognized as an important and challenging issue in all-optical packet switching. One of the feasible approaches for the implementation of optical buffers has the following features: (i) Using optical fiber delay lines as storage media to store optical packets. (ii) Using optical (bufferless) crossbar switches to route optical packets through the fiber delay lines.

We note that optical packets are constantly moving along the fibers into which they are routed, and they cannot be accessed until they reach the outputs of the fibers. As a result, such an approach by using optical fiber delay lines as storage media does not have random-access capability. Therefore, the delays of the optical fiber delay lines have to be properly chosen and the routing policy performed by the optical (bufferless) crossbar switches also has to be carefully designed. By so doing, packets can be routed to the right places at the right times, and exact emulations of the desired optical buffers can be achieved.

In the last three decades, there have been extensive studies on the constructions of optical buffers by using the switcheddelay- lines (SDL) approach described above. Indeed, such an SDL approach has been successfully used to construct a variety of optical buffers in the literature. These works include: (i) The early feasibility studies in [1]–[4], (ii) output-buffered switches in [5]–[10], (iii) first-in first-out (FIFO) multiplexers in [5] and [10]–[20], (iv) FIFO queues in [20]–[25], (v) lastin first-out (LIFO) queues in [22], [23], and [26], (vi) priority queues in [27]–[36], (vii) time slot interchanges in [20] and [37], (viii) linear compressors/decompressors, non-overtaking delay lines, and flexible delay lines in [20] and [38]–[43], and (ix) FIFO/LIFO/absolute contractors in [44]. Furthermore, results on the fundamental complexity of SDL constructions of optical queues can be found in [45] and performance analysis for optical queues has been addressed in [46] and [47].

In this paper (as well as many of the works in the literature), we focus on the theoretical aspect of the constructions of optical buffers. We are aware of many important practical feasibility issues such as: (i) Router buffer sizing problem, (ii) fault-tolerant capability, and (iii) limitation on the number of times that an optical packet can recirculate through optical switches and fiber delay lines. For those who are interested in such practical feasibility issues, we refer to Sections V-A and V-C in [36] and the references therein for details. For review articles on SDL constructions of optical buffers as well as related implementation and feasibility issues, we refer to [48]–[53] and the references therein.

One of the most general types of buffering schemes is priority queues, which includes FIFO queues and LIFO queues as special cases. A priority queue can be described as follows: (i) Each packet is associated with a unique priority upon its arrival, (ii) the packet with the highest priority is sent out from the queue whenever there is a departure request and there are packets in the queue, and (iii) the packet with the lowest priority is dropped from the queue whenever there is a buffer overflow. We note that the assignment of packet priorities can be arbitrary subject to the constraint that every packet in the queue has a distinct priority and the relative priority order between any two packets remains unchanged as long as they are in the queue. In the special case of a FIFO (resp., LIFO) queue, the packet arrival times are used for the assignment of packet priorities so that a packet with earlier arrival time has higher (resp., lower) priority than a packet with later arrival time.

The first construction of optical priority queues was given in [27] by Sarwate and Anantharam of UC Berkeley more than one and a half decades ago. It was shown in [27] that an optical priority queue with buffer size [TeX:] $$O\left(M^2\right)$$ can be constructed by using a feedback system consisting of an optical [TeX:] $$(M+2) \times(M+2)$$ (bufferless) crossbar switch and M fiber delay lines (see Fig. 1). Since the publication of the paper [27], there have been several works [28]–[36] on the constructions of optical priority queues that improve on the [TeX:] $$O\left(M^2\right)$$ buffer size. The buffer size achieved in [36] is [TeX:] $$2^{O(\sqrt{\alpha M})},$$ where is a constant that depends on the parameters used in the constructions in [36]. This buffer size [TeX:] $$2^{O(\sqrt{\alpha M})}$$ (which is exponential in [TeX:] $$\sqrt{M}$$) dramatically outperforms all previous results in [27]–[35] (all of which are only polynomial in M) and is the best result currently available in the literature.

In this paper, we focus on the constructions of optical priority queues in our previous work [36]. The main contributions of this paper are as follows:

(i) We derive a closed-form expression for the maximum buffer size [TeX:] $$U_k$$ (see (14) and (15) in Theorem 4 in Section III-A) that can be achieved in the constructions in [36]. Such a closed-form expression is not only of sufficient theoretical interest itself, but also can be used to directly compute the maximum buffer size. In contrast, the maximum buffer size has to be computed recursively in [36].

(ii) We use the closed-form expression to show that in the regime that [TeX:] $$s \geq 2, k \geq 2 s+1, \text { and } m \geq 2$$, where s, k, and m are parameters used in the constructions, the maximum buffer size [TeX:] $$U_k$$ is given by [TeX:] $$U_k=2^{O\left(\sqrt{M \log _2(2 s+2) \log _2 m /((2 s+1) m)}\right)}$$ (see (24) in Theorem 6 in Section IV) under a mild constraint that is applicable in practical scenarios. As there is no closedform expression available for the maximum buffer size in [36], an approximate analysis was resorted to in [36] to obtain the approximate result [TeX:] $$U_k \approx 2^{O\left(\sqrt{M \log _2(2 s+2) \log _2 m /((2 s+1) m)}\right)}$$ in this regime. Therefore, our result in this paper complements the results in [36].

We note the motivation for deriving a closed-form expression for the maximum buffer size [TeX:] $$U_k$$ in this paper is to use such an expression to give a rigorous mathematical proof that the approximate result [TeX:] $$U_k \approx 2^{O\left(\sqrt{M \log _2(2 s+2) \log _2 m /((2 s+1) m)}\right)}$$ in [36] is indeed an exact result in the regime that [TeX:] $$s \geq 2, k \geq 2 s+1, \text { and } m \geq 2.$$ It turns out that the closed-form expression obtained in this paper holds for all regimes of the parameters s, k, and m, i.e., for all [TeX:] $$1 \leq s \leq k-1 \text { and } m \geq 2.$$

This paper is organized as follows.We first give in Section II a review of the constructions of optical priority queues in [36]. In Section III, we derive a closed-form expression for the maximum buffer size and present our numerical results on the maximum buffer size. Then in Section IV, we show that in the regime that [TeX:] $$s \geq 2, k \geq 2 s+1 \text {, and } m \geq 2 \text {, }$$ the maximum buffer size [TeX:] $$U_k$$ is given by [TeX:] $$U_k=2^{O\left(\sqrt{M \log _2(2 s+2) \log _2 m /((2 s+1) m)}\right)}$$ under a mild constraint that is applicable in practical scenarios. Finally, we give a brief conclusion in Section V.

II. THE CONSTRUCTIONS IN OUR PREVIOUS WORK

In this section, we review the constructions of optical priority queues in [36]. The constructions in [36] use a feedback system (see Fig. 2) consisting of an optical (kmn + 2) × (kmn+2) (bufferless) crossbar switch and k groups of optical n-to-1 FIFO multiplexers with delay one (nFM1’s). The i th group in Fig. 2 has m parallel optical nFM1’s with the same buffer size [TeX:] $$B_i\left(B_i \geq 1\right)$$ for i = 1, 2, · · ·, k.

In [36], every packet that has to be buffered in the queue is associated with a distinct buffering tag, and each group of nFM1’s in Fig. 2 is associated with a unique set of buffering tags. A packet at the input links of the crossbar switch in Fig. 2 that has to be buffered in the queue (i.e., the packet is not routed to the departure link or the loss link) is routed to the group of nFM1’s whose associated set of buffering tags contains the buffering tag of the packet. Furthermore, packets routed to a group of nFM1’s are distributed to the m nFM1’s in that group in a round-robin fashion so that load balancing among the nFM1’s in that group can be achieved and hence the buffering capacity of the nFM1’s can be fully utilized. By so doing, the highest-priority (resp., lowest-priority) packet is always available at the input links of the crossbar switch whenever it needs to be routed to the departure (resp., loss) link. This is why an optical priority queue can be successfully constructed in [36].

Indeed, with appropriate choices of the parameters used in the constructions, a class of constructions of optical priority queues was obtained in Theorem 7 in [36]. By using the SDL constructions in [12] to implement the nFM1’s in Fig. 2, it was further shown in [36] that the construction in Fig. 2 can be implemented by using a feedback system consisting of an optical [TeX:] $$(M+2) \times(M+2)$$ (bufferless) crossbar switch and M fiber delay lines as in Fig. 1. The maximum buffer size [TeX:] $$U_k$$ that can be achieved in the class of constructions in [36] and the corresponding value of M in Fig. 1 are recalled in the following theorem.

Theorem 1 [36, Theorem 9] Suppose [TeX:] $$1 \leq s \leq k-1$$ and [TeX:] $$m \geq 2.$$ Then an optical priority queue with buffer size [TeX:] $$U_k$$ can be constructed by using a feedback system consisting of an optical [TeX:] $$(M+2) \times(M+2)$$ (bufferless) crossbar switch and M fiber delay lines as in Fig. 1, where

and

in which n = min{2s + 1, k} + 1 and [TeX:] $$B_1, B_2, \cdots, B_k$$ are given as follows: If [TeX:] $$s+1 \leq k \leq 2 s,$$ then [TeX:] $$B_1=B_k=1$$ and [TeX:] $$B_2, B_3, \cdots, B_{k-1}$$ are recursively given by

On the other hand, if [TeX:] $$k \geq 2 s+1,$$ then [TeX:] $$B_1=B_k=1$$ and [TeX:] $$B_2, B_3, \cdots, B_{k-1}$$ are recursively given by

As mentioned in Section I that the maximum buffer size [TeX:] $$U_k$$ is given by [TeX:] $$2^{O(\sqrt{\alpha M})}$$, where is a constant that depends on the parameters s, k, and m used in the constructions. We recall this result in the following theorem.

Theorem 2 [36, Theorem 11] Suppose that [TeX:] $$1 \leq s \leq k-1$$, [TeX:] $$m \geq 2, U_k$$ is given by (1), and M is given by (2).

(i) If [TeX:] $$s=1, k \geq 3, \text { and } m \geq 3,$$ then we have

(ii) If [TeX:] $$s \geq 2, s+1 \leq k \leq 2 s, \text { and } m \geq 2 \text {, }$$ then we have

(iii) If [TeX:] $$s \geq 2, k \geq 2 s+1, \text { and } m \geq 2,$$ then we have the following approximate result:

For the two simple regimes that "[TeX:] $$s=1, k \geq 3, \text { and } m \geq 3$$" and "[TeX:] $$s \geq 2, s+1 \leq k \leq 2 s, \text { and } m \geq 2$$" in Theorem 2(i)(ii), [TeX:] $$B_1, B_2, \cdots, B_k$$ can be obtained in closed forms (see Theorem 10(i)(ii) in [36]), and hence the maximum buffer size [TeX:] $$U_k$$ can be obtained as in (5) and (6) in these two regimes.

However, for the broader regime that "[TeX:] $$s \geq 2, k \geq 2 s+1, \text{ and } m \geq 2$$" in Theorem 2(iii), there is no closed-form expression available in [36] for [TeX:] $$B_1, B_2, \cdots, B_k$$. As a result, an approximation analysis was used in [36] as described below. It was first shown in Theorem 10(iii) in [36] that

for [TeX:] $$1 \leq i \leq\lceil k / 2\rceil.$$ In (8), [TeX:] $$\lambda_1, \lambda_2, \cdots, \lambda_s$$ are the roots of the characteristic polynomial [TeX:] $$p(z)=z^s-\sum_{j=0}^{s-1}(m-1) z^j$$ associated with the s th-order nonhomogeneous linear diff Perence equation with constant coefficients given by [TeX:] $$B_i=\sum_{j=i-s}^{i-1}\left((m-1) B_j+1\right)$$ for [TeX:] $$s+1 \leq i \leq\lceil k / 2\rceil,$$ and [TeX:] $$\alpha_1, \alpha_2, \cdots, \alpha_s$$ can be obtained by solving the s equations [TeX:] $$B_1=1 \text { and } B_i=m^{i-1}+\frac{m^{i-2}-1}{m-1}, i=2,3, \cdots, s.$$

Let [TeX:] $$\lambda_{+}$$ be the positive root of [TeX:] $$p(z)$$ (it was shown in Lemma 12 in the full version of the paper [36] that [TeX:] $$p(z)$$ has only one positive root) and let [TeX:] $$\alpha_{+}$$ be the coefficient corresponding to [TeX:] $$\lambda_{+}$$ in (8). By approximating [TeX:] $$B_1, B_2, \cdots, B_k$$ by [TeX:] $$B_i=B_{k-i+1} \approx \alpha_{+} \lambda_{+}^i \text { for } 1 \leq i \leq\lceil k / 2\rceil \text {, }$$ and substituting the approximate [TeX:] $$B_1$$ into (1), we have the following approximate result on [TeX:] $$U_k$$

By further approximating [TeX:] $$\lambda_{+} \text {by } m \text {, }$$ the approximate result on [TeX:] $$U_k$$ in (7) was obtained in [36].

In the rest of the paper, we will derive a closed-form expression for [TeX:] $$B_1, B_2, \cdots, B_k$$ (see (13) in Theorem 4 in Section III-A), and substitute it into (1) to obtain a closedform expression for the maximum buffer size [TeX:] $$U_k$$ (see (14) and (15) in Theorem 4 in Section III-A) for all regimes of the parameters s, k, and m, i.e., for all [TeX:] $$1 \leq s \leq k-1$$ and [TeX:] $$m \geq 2$$. For the regime that [TeX:] $$s \geq 2, k \geq 2 s+1, \text { and } m \geq 2$$, we will use these closed-form expressions to show that [TeX:] $$U_k$$ is given by [TeX:] $$U_k=2^{O\left(\sqrt{M \log _2(2 s+2) \log _2 m /((2 s+1) m)}\right)}.$$ (see (24) in Theorem 6 in Section IV) under a mild constraint that is applicable in practical scenarios.

III. A CLOSED-FORM EXPRESSION FOR THE MAXIMUM BUFFER SIZE

In this section, we derive a closed-form expression for the maximum buffer size and present our numerical results on the maximum buffer size.

A. The Closed-Form Expression

We first give a lemma that is the key to the derivation of the closed-form expression for the maximum buffer size in this paper.

Lemma 3 Suppose that s is a positive integer and a is a positive real number. Assume that [TeX:] $$x_1=1 \text { and } x_i, i \geq 2,$$ are recursively given as follows:

For [TeX:] $$i \geq 1,$$ let [TeX:] $$q_i$$ be the unique nonnegative integer such that [TeX:] $$q_i(s+1)+1 \leq i \leq\left(q_i+1\right)(s+1), \text { i.e., } q_i=\lceil i /(s+1)\rceil-1 \text {. }$$

(i) If [TeX:] $$i \geq 3,$$, then [TeX:] $$x_i$$ can be recursively given as follows:

(ii) If [TeX:] $$i \geq 2,$$, then [TeX:] $$x_i$$ can be expressed in closed form as follows:

where [TeX:] $$(y)_j$$ is the Pochhammer symbol given by [TeX:] $$(y)_{-1}=(y)_0=1$$ and [TeX:] $$(y)_j=y(y+1)(y+2) \cdots(y+j-1)$$ for every positive integer j.

(iii) The sequence [TeX:] $$\left\{x_i\right\}_{i=1}^{\infty}$$ is strictly increasing.

Proof. See Appendix A.

In the following theorem, we use Lemma 3 to derive closedform expressions for [TeX:] $$B_1, B_2, \cdots, B_k$$ that are given by (3) and (4) and for the maximum buffer size [TeX:] $$U_k$$ that is given by (1).

Theorem 4 Suppose that [TeX:] $$1 \leq s \leq k-1 \text { and } m \geq 2.$$ Let [TeX:] $$x_1=1$$ and let [TeX:] $$x_i$$ be given by the closed-form expression in (12) (with a = m − 1 in (12)) for [TeX:] $$2 \leq i \leq\lceil k / 2\rceil$$.

(i) We have

Therefore, we have [TeX:] $$B_1 \lt B_2 \lt \cdots \lt B_{\lceil k / 2\rceil}$$.

(ii) Suppose that k is even, say [TeX:] $$k=2 \ell$$ for some [TeX:] $$\ell \geq 1.$$ Let [TeX:] $$q_{\ell}$$ be given as in Lemma 3. Then we have

(iii) Suppose that k is odd, say [TeX:] $$k=2 \ell+1$$ for some [TeX:] $$\ell \geq 1$$ (note that [TeX:] $$k \geq s+1 \geq 2$$). Let [TeX:] $$q_{\ell}$$ be given as in Lemma 3. Then we have

Proof. (i) It is clear that (13) follows from (3), (4), (10), and Lemma 3(ii) (with [TeX:] $$a=m-1\gt 0$$). From (13) and Lemma 3(iii), we obtain [TeX:] $$B_1 \lt B_2 \lt \cdots \lt B_{\lceil k / 2\rceil} .$$

(ii) From (1) and (13), we have

If [TeX:] $$\ell=q_{\ell}(s+1)+1,$$ then we have

On the other hand, if [TeX:] $$q_{\ell}(s+1)+2 \leq \ell \leq\left(q_{\ell}+1\right)(s+1),$$ then we have from (10) (with a = m−1) and [TeX:] $$2 \leq \ell-q_{\ell}(s+1) \leq s+1$$ that

For [TeX:] $$0 \leq r \leq q_{\ell}-1,$$ we have from (10) (with a = m−1) and [TeX:] $$\ell-r(s+1) \geq q_{\ell}(s+1)+1-\left(q_{\ell}-1\right)(s+1)=s+2$$ that

By substituting (17)–(19) into (16), we obtain (14).

(iii) From (1) and (13), we have

As it is clear from (16) that [TeX:] $$2 \sum_{j=1}^{\ell}\left((m-1) x_j+1\right)$$ is given by the right-hand side of (14), we immediately see that (15) follows from (20) and (14).

B. Numerical Results

We have performed numerical analysis for extensive ranges of the parameters s, k, and m, and our numerical results show that the maximum buffer size [TeX:] $$U_k$$ computed directly by using the closed-form expressions in (14) and (15) is the same as that computed recursively by using (1), (3), and (4). This can be easily seen from Fig. 3 for the case that s = 2, m = 4, and [TeX:] $$5 \leq k \leq 14$$, and from Fig. 4 for the case that s = 3, m = 4, and [TeX:] $$7 \leq k \leq 15$$. Furthermore, these numerical results serve as a verification of the correctness of the closed-form expressions for [TeX:] $$U_k$$ in (14) and (15).

Our numerical results also show that the approximate maximum buffer size [TeX:] $$\widetilde{U}_k$$ given by (9) is very close to the maximum buffer size [TeX:] $$U_k$$. In fact, [TeX:] $$\widetilde{U}_k$$ is slightly larger than [TeX:] $$U_k$$. This is due to the fact that when we approximate [TeX:] $$B_i$$ given in (8) by [TeX:] $$\alpha_{+} \lambda_{+}^i,$$ the terms in (8) that are omitted contribute negatively to the maximum buffer size. As a result, [TeX:] $$\widetilde{U}_k$$ is slightly larger than [TeX:] $$U_k$$. Since it is not easy to tell the difference between [TeX:] $$\widetilde{U}_k$$ and [TeX:] $$U_k$$ visually from Figs. 3 and 4, we show the values of [TeX:] $$\widetilde{U}_k$$ and [TeX:] $$U_k$$ in Table I and Table II. It can be easily seen from Table I and Table II that the difference between [TeX:] $$\widetilde{U}_k$$ and [TeX:] $$U_k$$ is at most equal to 22 in these cases. These numerical results tell us that the approximate result in [36] gives a slight overestimate of the maximum buffer size [TeX:] $$U_k$$. Fortunately, the difference between [TeX:] $$\widetilde{U}_k$$ and [TeX:] $$U_k$$ is insignificant in most scenarios when compared with the values of [TeX:] $$U_k$$, especially when s, k, and m are large.

The observation from the numerical results that the approximate maximum buffer size [TeX:] $$\widetilde{U}_k$$ is very close to the maximum buffer size [TeX:] $$U_k$$ is a good indication that the approximate result in (7) is indeed an exact result as given in (24). In Section IV, we will use the closed-form expressions in (14) and (15) to prove that the exact result in (24) holds.

IV. THE MAXIMUM BUFFER SIZE IN TERMS OF THE SWITCH SIZE IN FIG. 1

To express the maximum buffer size [TeX:] $$U_k$$ (which is given by (1)) in terms of the switch size M (which is given by (2)) in the regime that [TeX:] $$s \geq 2, k \geq 2 s+1 \text {, and } m \geq 2 \text {, }$$ we need the following lemma on an upper bound and a lower bound for the [TeX:] $$x_i$$’s in Lemma 3 under the constraint that [TeX:] $$(a+1)^{s+1} \geq q_i(s+1) a+1$$.

Lemma 5 Suppose that [TeX:] $$s, a, x_i, i \geq 1, \text { and } q_i, i \geq 1$$, are as given in Lemma 3. If [TeX:] $$(a+1)^{s+1} \geq q_i(s+1) a+1$$ for some [TeX:] $$i \geq 1$$, then we have the following upper bound and lower bound for [TeX:] $$x_i$$:

and

Proof. See Appendix B.

Now we use the closed-form expressions in Theorem 4 and the bounds in Lemma 5 to show that [TeX:] $$U_k$$ can be expressed in terms of the switch size M and the parameters s, k, and m as given by (24) below in the regime that [TeX:] $$s \geq 2, k \geq 2 s+1 \text {, } m \geq2.$$

Theorem 6 Suppose that [TeX:] $$s \geq 2, k \geq 2 s+1 \text {, } m \geq2.$$

(i) Suppose that k is even, say [TeX:] $$k=2 \ell$$ for some [TeX:] $$\ell \geq s+1$$ (note that [TeX:] $$k \geq 2 s+1$$). Let [TeX:] $$q_{\ell}$$ be given as in Lemma 3. Assume that [TeX:] $$m^{s+1} \geq q_{\ell}(s+1)(m-1)+1.$$ Then we have

Therefore, in this case we have

(ii) Suppose that k is odd, say [TeX:] $$k=2 \ell+1$$ for some [TeX:] $$\ell \geq s$$ (note that [TeX:] $$k \geq 2 s+1$$). Let [TeX:] $$q_{\ell}$$ be given as in Lemma 3. Assume that [TeX:] $$m^{s+1} \geq q_{\ell+1}(s+1)(m-1)+1.$$. Then we have

Therefore, in this case (24) also holds.

Remark 7 (i) As mentioned earlier in this paper, the exact result on [TeX:] $$U_k$$ in (24) can be viewed as a complement to the approximate result in (7) in the regime that [TeX:] $$s \geq 2, k \geq 2 s+1, m \geq 2$$ under the constraints in Theorem 6.

(ii) We note that the constraints [TeX:] $$m^{s+1} \geq q_{\ell}(s+1)(m-1)+1$$ in Theorem 6(i) and [TeX:] $$m^{s+1} \geq q_{\ell+1}(s+1)(m-1)+1$$ in Theorem 6(ii) are not very stringent as they are applicable in practical scenarios. For example, in Table III we first find the largest [TeX:] $$q_{\ell}$$ that satisfies the constraint [TeX:] $$m^{s+1} \geq q_{\ell}(s+1)(m-1)+1,$$ i.e., [TeX:] $$q_{\ell}=\left\lfloor\left(m^{s+1}-1\right) /((s+1)(m-1))\right\rfloor,$$ then we find the largest [TeX:] $$\ell$$ that satisfies [TeX:] $$q_{\ell}(s+1)+1 \leq \ell \leq\left(q_{\ell}+1\right)(s+1),$$ i.e., [TeX:] $$\ell=\left(q_{\ell}+1\right)(s+1),$$ and let [TeX:] $$k=2 \ell=2\left(q_{\ell}+1\right)(s+1)$$, and finally we calculate [TeX:] $$U_k$$ by using (14) for [TeX:] $$s=1 \text { and } 2 \leq m \leq 9$$ and for [TeX:] $$s=2 \text { and } 2 \leq m \leq 5.$$ It is clear from Table III that for moderate values of s, m, and k (the smaller the values of s, m, and k are, the lower the construction complexity/cost of the constructions is), the maximum buffer size [TeX:] $$U_k$$ that can be achieved is large enough and exceeds the order of millions of packets that is needed in today’s commercial backbone routers. For example, for s = 1 and m = 6, we only need [TeX:] $$k \geq 16 \text { for } U_k$$ to exceed [TeX:] $$10^6$$; and for s = 2 and m = 3, we only need [TeX:] $$k \geq 30 \text { for } U_k$$ to exceed [TeX:] $$10^6$$.

(iii) Finally, we note that for the regime that [TeX:] $$s \geq 2, s+1 \leq k \leq 2s, \text{and } m \geq 2,$$ we have n = min{2s+1, k}+1 = k+1 and by using n = k + 1 (instead of n = 2s + 2) in the proof of Theorem 6, we can obtain the same result on [TeX:] $$U_k$$ as that given in (6)

Proof. (Proof of Theorem 6)

(i) It is clear from the definition of [TeX:] $$q_i$$ that [TeX:] $$q_i$$ is nondecreasing in i, and hence we see from the assumption [TeX:] $$m^{s+1} \geq q_{\ell}(s+1)(m-1)+1$$ that [TeX:] $$m^{s+1} \geq q_i(s+1)(m-1)+1$$ for [TeX:] $$1 \leq i \leq \ell$$. It then follows from (13), (21), (22), [TeX:] $$1 /(m-1) \leq 2 / m \text { (as } m \geq 2), \text { and } B_i \geq 1$$ that

It is easy to see from (14), (13), and (26) that

and from (14), (13), (26), [TeX:] $$2 q_{\ell}+2 \leq q_{\ell}(s+1)+2 \leq \ell+1 \leq m^{\ell},$$, and [TeX:] $$m^{s+1} \geq 2^2=4$$ that

Note that [TeX:] $$n=\min \{2 s+1, k\}+1=2 s+2 \text { (as } k \geq 2 s+1) .$$ From (26), we can see that [TeX:] $$\left\lceil\log _{2 s+2} B_i\right\rceil\lt \log _{2 s+2} B_i+1 \leq (i-1) \log _{2 s+2} m+\log _{2 s+2} 2+1 \leq(i-1) \log _{2 s+2} m+2$$ and [TeX:] $$\left\lceil\log _{2 s+2} B_i\right\rceil \geq \log _{2 s+2} B_i \geq \max \left\{(i-s-3) \log _{2 s+2} m, 0\right\}$$ for [TeX:] $$1 \leq i \leq \ell.$$ As such, we have from (2) and (13) that

and

Therefore, we see that the first inequality in (23) follows from [TeX:] $$U_k \geq 2 m^{\ell-s-2}=2^{(\ell-s-2) \log _2 m+1}$$ in (27) and [TeX:] $$\ell \geq \sqrt{M \log _2(2 s+2) /\left((2 s+1) m \log _2 m\right)}-4 \log _2(2 s+2)/ \log_2m$$ in (29). Similarly, we see that the second inequality in (23) follows from [TeX:] $$U_k \leq 8 m^{\ell}=2^{\ell \log _2 m+3}$$ in (28) and [TeX:] $$\ell \leq \sqrt{M \log _2(2 s+2) /\left((2 s+1) m \log _2 m\right)}+s+3$$ in (30).

(ii) As in the proof of (i) above, we can use the assumption [TeX:] $$m^{s+1} \geq q_{\ell+1}(s+1)(m-1)+1$$ to show that (26) holds for [TeX:] $$1 \leq i \leq \ell+1.$$ It is then easy to see from (15), (13), and (26) that

and from (15), (13), (26), [TeX:] $$2 q_{\ell}+3 \leq q_{\ell}(s+1)+3 \leq \ell+2 \leq 2m^\ell,$$ and [TeX:] $$m^{s+1} \geq 2^2=4$$ that

Note that [TeX:] $$n=\min \{2 s+1, k\}+1=2 s+2\text { (as } k \geq 2 s+1) \text {. }$$ As in the proof of (i) above, we have from (2) and (13) that

and

Therefore, we see that the first inequality in (25) follows from [TeX:] $$U_k \geq m^{\ell-s-1}=2^{(\ell-s-1) \log _2 m}$$ in (31) and [TeX:] $$\ell \geq \sqrt{M \log _2(2 s+2) /\left((2 s+1) m \log _2 m\right)}-6 \log _2(2 s+2)/ \log_2m$$ in (33). Similarly, we see that the second inequality in (25) follows from [TeX:] $$U_k \leq 8 m^{\ell+1}=2^{(\ell+1) \log _2 m+3}$$ in (32) and [TeX:] $$\ell \leq \sqrt{M \log _2(2 s+2) /\left((2 s+1) m \log _2 m\right)}+s+2$$ in (34).

V. CONCLUSION

In this paper, we have obtained a closed-form expression for the maximum buffer size that can be achieved by the constructions in [36]. Such an expression is of enough theoretical interest itself. It not only allows us to directly compute the maximum buffer size, but also makes it possible for us to give a rigorous mathematical proof that an approximate result on the maximum buffer size in [36] is indeed an exact result. Therefore, this paper complements the work in [36].

APPENDIX A

PROOF OF LEMMA 3

(i) Suppose that [TeX:] $$i \geq 3$$. If [TeX:] $$3 \leq i \leq s+1,$$ then we have from (10) and [TeX:] $$2 \leq i-1\lt i \leq s+1$$ that

On the other hand, if [TeX:] $$i \geq s+2$$, then we have from (10) and [TeX:] $$i>i-1 \geq s+1$$ that

(ii) We show by induction on i that (12) holds for [TeX:] $$i \geq 2$$. It is clear from (10) that

Thus, we have proved the base case that (12) holds for i = 2 (note that [TeX:] $$\left.q_2=0 \text { as } 0 \cdot(s+1)+1\lt2 \leq 1 \cdot(s+1)\right)$$.

Assume as the induction hypothesis that (12) holds up to i − 1 for some [TeX:] $$i-1 \geq 2.$$ We need to consider the following three cases.

Case 1: [TeX:] $$q_i=0.$$ In this case, we have [TeX:] $$3 \leq i \leq s+1$$ and hence [TeX:] $$q_{i-1}=0\text { (as } 1\lt i-1\lt s+1)$$. It follows that

where the first equality follows from (11) (note that [TeX:] $$3 \leq i \leq s+1$$) and the second equality follows from the induction hypothesis that (12) holds for i − 1 (note that [TeX:] $$q_{i-1}=0$$). Thus, we have proved that (12) holds for i (note that [TeX:] $$q_i=0$$).

Case 2: [TeX:] $$q_i \geq 1 \text { and } i=q_i(s+1)+1.$$ In this case, we have [TeX:] $$q_{i-1}=q_i-1\left(\text { as }\left(q_i-1\right)(s+1)+1\lt i-1=q_i(s+1)\right)$$ and [TeX:] $$q_{i-s-1}=q_i-1\left(\text { as }\left(q_i-1\right)(s+1)+1=i-s-1\lt q_i(s+1)\right)$$.

In the following, we discuss the two subcases [TeX:] $$q_i=1$$ and [TeX:] $$q_i \geq 2$$ separately.

Subcase 2(a): [TeX:] $$q_i = 1$$. In this subcase, we have i = s + 2 and hence

where the first equality follows from (11) and the second equality follows from the induction hypothesis that (12) holds for i −1 = s +1 (note that [TeX:] $$q_{s+1}=0$$). Thus, we have proved that (12) holds for i = s + 2 (note that [TeX:] $$q_{s+2}=1$$).

Subcase 2(b): [TeX:] $$q_i \geq 2$$. In this subcase, we let [TeX:] $$y_j=i-j(s+1)$$ for [TeX:] $$0 \leq j \leq q_i$$ and hence we have

where the first equality follows from (11) (note that [TeX:] $$i=q_i(s+\text { 1)}+1 \geq 2(s+1)+1>s+2$$), the second equality follows from the induction hypothesis that (12) holds for i-1 and i-s-1 (note that [TeX:] $$i-s-1=\left(q_i-1\right)(s+1)+1 \geq 1 \times(s+1)+1\gt 2$$ and [TeX:] $$\left.q_{i-1}=q_{i-s-1}=q_i-1\right)$$, the third equality follows from [TeX:] $$y_{q_i}=i-q_i(s+1)=1,(1)_{q_i-2}=\left(q_i-2\right) !$$, and [TeX:] $$(1)_{q_i-1}=\left(q_i-1\right) !$$ and the last equality follows from [TeX:] $$y_{q_i}=1,(1)_{q_i-1}=\left(q_i-1\right) ! \text {, }$$ [TeX:] $$(1)_{q_i}=\left(q_i\right) ! \text {, }$$ and [TeX:] $$(y-1)_{j-1}+(j-1) y_{j-2}=(y)_{j-1}$$ for [TeX:] $$1 \leq j \leq q_i$$. Thus, we have proved that (12) holds for i.

We note that in Subcase 2(a) the induction hypothesis does not imply that (12) holds for i = 1 (in fact, [TeX:] $$x_1$$ is not given by (12)), and this is why we need to discuss the two subcases [TeX:] $$q_i=1 \text { and } q_i \geq 2$$ separately.

Case 3: [TeX:] $$q_i \geq 1 \text { and } q_i(s+1)+2 \leq i \leq\left(q_i+1\right)(s+1) \text {. }$$ In this case, we have [TeX:] $$q_{i-1}=q_i\text { (as } q_i(s+1)+1 \leq i-1\lt(q_i+1)(s+1))$$ and [TeX:] $$q_{i-s-1}=q_i-1\text { (as }\left(q_i-1\right)(s+1)+1\lt \left.i-s-1 \leq q_i(s+1)\right)$$.

Similar to the proof in Case 2 above, we prove that (12) holds for i in this case as follows:

where the first equality follows from (11) (note that [TeX:] $$i \geq q_i(s+\text { 1) }+2 \geq 1 \times(s+1)+2\gt s+2)$$, the second equality follows from the induction hypothesis that (12) holds for i - 1 and i - s - 1 (note that [TeX:] $$i-s-1 \geq\left(q_i-1\right)(s+1)+2 \geq 2, \left.q_{i-1}=q_i, \text { and } q_{i-s-1}=q_i-1\right)$$, and the last equality follows from [TeX:] $$(y-1)_{j-1}+(j-1) y_{j-2}=(y)_{j-1} \text { for } 1 \leq j \leq q_i+1.$$

(iii) To show that the sequence [TeX:] $$\left\{x_i\right\}_{i=1}^{\infty}$$ is strictly increasing, we prove by induction on i that [TeX:] $$x_1\lt x_2\lt \cdots\lt x_i$$ for [TeX:] $$i \geq 2$$. It is clear from (10) and a > 0 that

Thus, we have proved the base case that [TeX:] $$x_1\lt x_2$$

Assume as the induction hypothesis that [TeX:] $$x_1\lt x_2\lt \cdots\lt x_{i-1}$$ for some [TeX:] $$i-1 \geq 2$$. To complete the induction, it suffices to prove that [TeX:] $$x_{i-1}\lt x_i \text {. }$$ We consider the following two cases.

Case 1: [TeX:] $$3 \leq i \leq s+1.$$ In this case, we have

where the equality follows from (11), the first inequality follows from a > 0 and the induction hypothesis that [TeX:] $$x_{i-1}>x_1$$ (note that i−1 > 1), and the last inequality follow from a > 0.

Case 2: [TeX:] $$i \geq s+2.$$. In this case, we have

where the equality follows from (11), and the inequality follows from a > 0 and the induction hypothesis that [TeX:] $$x_{i-1}\gt x_{i-s-1}$$ (note that [TeX:] $$1 \leq i-s-1\lt i-1$$).

APPENDIX B

PROOF OF LEMMA 5

Suppose that [TeX:] $$(a+1)^{s+1} \geq q_i(s+1) a+1$$ for some [TeX:] $$i \geq 1$$. If i = 1, then [TeX:] $$q_i = 0$$ and it is clear from [TeX:] $$x_1 = 1$$ and a > 0 that (21) and (22) hold for i = 1. Therefore, we assume that [TeX:] $$i \geq 2$$ in the rest of the proof.

Write [TeX:] $$x_i$$ in (12) as follows:

where

for [TeX:] $$0 \leq j \leq q_i.$$ Note that it is easy to see that [TeX:] $$\delta_j\gt 0$$ (as [TeX:] $$\left.i-j(s+1) \geq i-q_i(s+1) \geq 1 \text { and } a\gt0\right)$$ for [TeX:] $$0 \leq j \leq q_i.$$ Then we consider the cases [TeX:] $$q_i=0 \text { and } q_i \geq 1$$ separately.

Case 1: [TeX:] $$q_i=0.$$ In this case, we have from (35), (36), a > 0, and [TeX:] $$i \geq 2$$ that

Thus, (21) and (22) hold in this case.

Case 2: [TeX:] $$q_i \geq 1.$$ In this case, we first show that the sequence [TeX:] $$\left\{\delta_j\right\}_{j=1}^{q_i}$$ is strictly decreasing. Suppose [TeX:] $$1 \leq j \leq q_i-1.$$ Note that

To show that [TeX:] $$\delta_j\gt \delta_{j+1}$$ we give upper bounds for the two terms [TeX:] $$(i-(j+1)(s+1))_j$$ and [TeX:] $$(i-(j+1)(s+1))_{j+1}$$ that appear in the expression for [TeX:] $$\delta_{j+1}$$ in (38). Specifically, we have

where the inequality follows from [TeX:] $$(i-j(s+1))_{j-1} \geq(i-(j+1)(s+1))_{j-1}\gt 0$$ (as [TeX:] $$1 \leq j \leq q_i-1 \text { and } i-j(s+1)\gt \left.i-(j+1)(s+1) \geq i-q_i(s+1) \geq 1\right)$$ and [TeX:] $$0\lt i-(j+\text { 1) }(s+1)+j-1 \leq\left(q_i+1\right)(s+1)-(j+1)(s+1)+j-1=\left(q_i-1\right)(s+1)-(j-1) s \leq\left(q_i-1\right)(s+1) .$$ Similarly we have

As such, we have

where the equality follows from (36) and (38), the first inequality follows from a > 0, (39), and (40), and the last inequality follows from [TeX:] $$j \geq 1$$ and [TeX:] $$(a+1)^{s+1} \geq q_i(s+1) a+1 \text {. }$$

Now we use the strict monotonicity of the sequence [TeX:] $$\left\{\delta_j\right\}_{j=1}^{q_i}$$ in (41) to show that

Specifically, if [TeX:] $$q_i$$ is odd, say [TeX:] $$q_i=2 \ell-1$$ for some [TeX:] $$\ell \geq 1$$, then it follows from (35), the strict monotonicity of the sequence [TeX:] $$\left\{\delta_j\right\}_{j=1}^{q_i}$$, and the positivity of the [TeX:] $$\delta_j^{\prime} s$$ that

and

Similarly, if [TeX:] $$q_i$$ is even, say [TeX:] $$q_i=2 \ell$$ for some [TeX:] $$\ell \geq 1$$, then we also have

and

Finally, we have from (42) and [TeX:] $$\delta_0-1 / a \leq(a+1)^i / a$$ in (37) that

Thus, (21) holds in this case. To show that (22) holds in this case, we note from (42) and (36) that

If [TeX:] $$q_i(s+1)+1 \leq i \leq\left(q_i+1\right)(s+1)-1 \text {, }$$ then we have [TeX:] $$(a+1)^{s+1}-(i-s-1) a \geq q_i(s+1) a+1-\left(q_i(s+1)-\right.\text { 1) } a=a+1$$, and hence it follows from (43), a 0, and [TeX:] $$i-s-2 \geq\left(q_i-1\right)(s+1) \geq 0$$ that

On the other hand, if [TeX:] $$i=\left(q_i+1\right)(s+1)$$, then we have [TeX:] $$(a+1)^{s+1}-(i-s-1) a \geq q_i(s+1) a+1-q_i(s+1) a=1 \text {, }$$ and hence it follows from (43), a 0, and [TeX:] $$i-s-3=q_i(s+1)-2 \geq 1 \times 2-2=0$$ that

Thus, we see from (44) and (45) that (22) holds in this case.