## Abstract

Optical buffering is a major challenge in realizing all-optical packet switching. In this paper we propose a new buffer called a multiple-input single-output FIFO (MISO-FIFO) optical buffer that supports several functions normally associated with electronic RAM. Our structure reduces the physical size of a buffer by up to an order of magnitude or more by allowing reuse of its basic optical delay line (ODL) elements. Moreover, by using controllable fractional delay lines (CFDLs) as the basic building block we are able to reduce the size and frequency of voids in the output of the buffer. We develop a Markov Chain (MC) model for the performance of our new buffering scheme, and demonstrate the advantages of our structure over buffer structures that use ODLs in terms of throughput and link utilization.

©2008 Optical Society of America

## 1. Introduction

Optical packet switching has been proposed as an alternative to electronic packet switching because of its transparency to different protocols and line rates and because of its potential for integration within future WDM transmission infrastructure [1–4]. It has also been conjectured that all-optical packet switching can achieve higher data rates and therefore better scalability because optical routers are expected to minimise the need for optical-electrical-optical (OEO) conversion and other packet-related processing [1–4]. However, there are technological issues preventing the deployment of optical packet switching. Specifically, the available optical buffering structures mostly rely on optical delay lines (ODLs) [1, 3, 5] which occupy larger footprints [6, 7] and lack the random access capabilities of their electronic counterparts [6, 7]. In this paper we propose a novel buffering structure to reduce the size of optical buffers and to improve their random access capabilities. We provide an analytical model to show that our structure is able to achieve substantially higher link utilization than existing optical buffers and reduces the size by up to an order of magnitude or more.

A widely used guideline to determine the required size of the buffer in a router is to make the buffer size equal to the bandwidth delay product of the link [8]. For a 40-Gb/s link this leads to a buffer size of 1 GB [8]. Therefore, in all-optical routers, ODL buffers would require a fiber length of 75 Gm to achieve a 90-Tb/s router equivalent to a Cisco CRS-1 backbone router [9]. This suggests that current approaches to optical buffering are unrealistic and infeasible. Recent advances in the area of slow light devices have increased the hope of optical buffering by restricting the velocity of light [6] and eventually reducing the space requirement for optical buffers. However, slow light devices suffer from multiple disadvantages, such as limited bandwidth, high transmission losses and limited cascadability [6, 7]. Consequently, for the near future we still need to rely on ODLs when designing optical buffers.

A major challenge of building optical buffers using ODLs is that each ODL can offer only a fixed amount of delay. Therefore optical buffers proposed in the literature using ODLs [1–4] lack full random access capability, and time gaps or voids are created between successive packets released from the ODL buffers [10]. These voids lead to a lower link utilization and wastage of channel bandwidth. This problem of void creation has been addressed in the literature in two different ways: either by building a synchronous optical network (SON) [11–12] or by employing a void-filling packet scheduling scheme [10]. However, both schemes require complex control and additional router hardware. In particular, synchronous optical networks require complex optical synchronizers - one for every wavelength of every input fiber, each comprising many delay lines and optical switches [13]. For example, it has been observed in [10] that routers used in the KEOPS project [13] require a hardware overhead of 50% for performing synchronization.

Our aim in this paper is to propose a new buffering structure that reduces the occurrence of voids between successive packet transmissions while maintaining a simplified buffer management and control scheme. We aim to enhance the random access capability of optical buffers in order to achieve better queuing performance and output link utilization. We also focus on reducing the physical size of the buffering structure. To accomplish these goals, we introduce a novel structure for buffers called a multiple-input single-output first-in first-out (MISO-FIFO) buffer, which supports several functions that are normally associated with electronic RAM. Our structure reduces the physical size of a buffer by allowing reuse of its basic ODL elements. Moreover, by using controllable fractional delay lines (CFDLs) as the basic building block of our structure we are able to reduce the size and frequency of voids in the output of the buffer. By developing a Markov Chain (MC) model for the performance of our new buffering scheme, we demonstrate that our structure improves link utilization by 30% compared to previous buffer structures that use fixed ODLs.

The rest of the paper is organized as follows. Section 2 formulates the problem that we address in this paper. In Section 3 we present the MISO-FIFO buffering structure with CFDLs, and highlight its advantages over an existing buffering structure using ODLs. Section 4 briefly describes the advantages using MISO-FIFO buffers with CFDLs. Section 5 models and compares the performance of an existing buffering structure using ODLs with our MISO-FIFO buffer using CFDL elements. We also derive an upper bound on the utilization of our buffering structure with fixed length ODLs. Section 6 summarizes the results and is followed by the conclusion.

## 2. Problem statement

In this section we briefly summarise some challenges associated with optical buffering and describe the problem we address in this paper.

The buffers in a router are typically FIFO. One advantage in an optical delay line is that it intrinsically has FIFO characteristics but with a fixed amount of delay. However, optical FIFO buffers differ in numerous ways from their electronic counterpart. Electronic FIFO buffers, which are mostly constructed using random access memory (RAM), have the following features that are missing from optical delay line buffers:

• A packet can enter an electronic RAM at any time, thus enabling packets to be written into the buffer at a much faster rate than they are read from the buffer.

• A packet at the exit of a FIFO buffer can wait an arbitrary amount of time before the output link is free, and the following packets can be delayed accordingly.

• A packet in the buffer can be released at any time irrespective of the time at which the packet enters the buffer, whereas in ODL buffers, packets can be released only at predefined time intervals.

Our goal is to design an ODL buffer structure that behaves in a similar way to electronic RAM with a compact size and minimal control.

## 3. The new multiple-input single-output FIFO (MISO-FIFO) optical buffer

In this section we provide a new buffering scheme to address the issues discussed in the previous section. Before providing the detailed structure of our proposal, we briefly review relevant buffering structures in the literature and their limitations.

In the literature, three basic buffering elements have often been used to construct optical buffers as shown in Fig. 1. The first structure in Fig. 1(a) is the simple travelling wave delay line or ODL with a delay of D seconds. This is the basic structure that is used in almost all optical buffers (including the buffering elements shown in Fig 1(b) and 1(c)). The ODL is not a buffer in itself, but can be used with optical switches to provide a buffering function. The recirculating delay line shown in Fig. 1(b) utilizes a 2×2 switch and an ODL providing D delay. In this case, the delay can be adjusted in multiples of D by controlling the switch. The third structure in Fig. 1(c) is the controllable fractional delay line (CFDL), where the delay can be a fraction of D and is potentially adjustable. The number of stages (*n*) in this structure is determined by the granularity of delay required. Each stage comprises a switch and an ODL element as shown in Fig. 1(c). We refer to *F* as the delay factor, such that the smallest delay realizable is *D*/*F* and any multiple of this smallest delay unit can be achieved by adjusting the switching stages. From Fig. 1(c), it is easy to see that the smallest delay realizable is *D*/2^{n-1}.Therefore, the parameters *F* and *n* are related by the expression *F*=2^{n-1}. There are multiple structures suggested in the literature to realize a CDFL. Three potential structures are the staggered delay line (as shown in Fig. 1(c)), the broadcast and select structure [17] and the folded path structure [14]. Among these, the folded path structure has the advantage of reducing the ODL length by half [14].

Optical buffering structures can be built from the basic ODL buffering elements shown in Fig. 1. Figure 2 shows a degenerate buffer array along with a strictly non-blocking switch used for an asynchronous output buffered optical switch [17]. Figure 2(a) shows the overall switching architecture, where packets from *N* different input ports are first switched through an *N*×*N ^{2}* optical switch to achieve strictly non-blocking switching in an output buffered scenario. A bundle of

*N*output ports from the first switch is then connected to the

*N*input ports of a buffering structure as shown in Fig. 2(b). In the buffering structure of Fig. 2(b), (

*B*-1) ODLs offering delay values that are a multiple of

*D*are arranged in parallel. Each ODL is represented by a shaded rectangle in Fig. 2(b) and consists of a travelling wave delay line as in Fig. 1(a). The offered delay in each ODL varies from

*D*to (

*B*-

*1*)

*D*as shown. The

*N*input ports in the buffering structure are switched to

*B*degenerate ODL elements through an

*N*×

*B*space switch. The buffer structure shown in Fig. 2 (b) has a multiple-input single-output structure.

As an alternative to the buffer array shown in Fig. 2, we propose a new multi-input single-output FIFO (MISO-FIFO) buffering scheme as shown in Fig. 3. Here *B*-1 similar buffering elements are connected in sequence and are also attached to the output port of an *N*×*B* space switch as shown in Fig. 3. The switch provides access to any of the B buffering elements for packets from N different input ports. Each buffering element is connected to the next element with a 2×2 optical coupler with a coupling coefficient that depends on its relative position in the overall buffer. The coupling coefficients are adjusted to ensure that the total power loss through the buffering elements and the couplers is the same, regardless of which of the *B* buffering elements a packet is injected into. Assuming that the buffering elements have negligible loss, it is a trivial exercise to show that the power loss from each of the B input ports are the same if the values of the coefficients are as follows:

*a*
_{1}=1/2, *a*
_{2}=1/3, *a*
_{3}=1/4,…,*a*
_{B-1}=1/*B*.

With this set of coupling coefficients, the power loss from each of the *B* input ports to the output is *10*
*log _{10}B* dB. This is identical to the loss in the well-known buffer structure in Fig. 2. If the loss in the buffering elements is non-zero, the coupling coefficients can be adjusted to ensure that the input to output power ratios remain the same.

In Fig. 3 we have shown the MISO-FIFO structure with fixed ODLs. However, the buffering elements can be either controllable or fixed as required. The parallel structure ensures that output port collisions do not occur if multiple input ports simultaneously have data for the same output port. Therefore the structure automatically allows packets to be written into the buffer at a much higher speed than the link capacity. This conforms to the first requirement of RAM like functionality mentioned in the previous section. The major advantage of our MISO-FIFO structure over the structure shown in Fig. 2 is that the MISO-FIFO buffer reduces the length of ODLs required by reusing the ODLs for delayed packets. From Fig. 2 and 3 it is evident that the MISO-FIFO buffer uses ODLs with a total length of (*B*-1)*D*, whereas a conventional buffer array needs ODLs with a total length of *B*(*B*-1)*D*/2. The overall reduction factor is *B*/*2*, which increases linearly with the buffer size (*B*). For example, if *B* is 20, the total buffer length is reduced by an order of magnitude.

Furthermore, if we use controllable fractional delay lines (CFDLs) as the basic buffering elements instead of fixed ODLs in Fig. 3, we can enhance the random access capability of our structure by adjusting the time at which buffers are cleared. By controlling the CFDL delay in each buffering arm, the voids between successive packets can be minimized. The void filling improves as the granularity (*D*/*F*) of the CFDL buffers decreases. This eventually makes the functionality of our buffering structure closer to that of electronic RAM in terms of random access.

## 4. Advantages of the new MISO-FIFO buffers with CFDL

In this section we describe the advantages of our new buffering structure before analytically modelling and qualitatively analysing our buffering structure.

The main advantage of our MISO-FIFO buffer architecture is that it requires a substantially reduced total length of delay lines to achieve the same amount of buffering as the structure in Fig. 2. Therefore, the structure is less bulky than the structure in Fig. 2 and, if losses in the delay lines are significant, it has lower losses than the structure in Fig. 2.

The other major advantage of the MISO-FIFO buffer with CFDL is that it is better suited to asynchronous switching architectures as it can handle random packet arrivals and packets of variable lengths. We propose to use our new buffering structure in an output buffered asynchronous optical switch. We consider asynchronous optical networks (AONs) rather than synchronous optical networks (SON) as AONs can accept variable packet lengths and therefore is a better candidate for supporting direct IP over WDM in optical packet switching. However, as shown in [1–4], AONs with a shared buffering scheme require higher switching speeds and additional control. In contrast, ODL buffers perform better under time slotted operation, and exhibit higher packet losses under asynchronous conditions [1–4]. The major advantage of CFDL buffers is that the limitation of higher packet loss in asynchronous conditions can be minimized by reducing voids. The other advantage of the new MISO-FIFO buffers with CFDL is that if they are used with an output buffered architecture, they can reduce the complexity of AONs by decoupling the control and scheduling for each output port. We rule out the option of input buffering since it has already been proven that output buffering gives much better performance in terms of link utilization and queuing delay compared to input buffering [15]. Moreover, ODLs are not well suited to input buffering because in an input buffered switch, it is very hard to predict when a packet will leave an input buffer. On the other hand, in an output buffered switch, it is easy to do so. It has also been shown through simulation [16] that input buffering in optical routing is only feasible when the load on the network is very low (≈50%).

To demonstrate the benefits of introducing CFDLs, in the following section we provide an analytical model for link utilization in conventional buffers using ODLs, as well as for our MISO-FIFO with CFDLs.

## 5. Analytical model of the MISO-FIFO optical buffer

In this section, we quantify the advantage of our buffering structure by developing an analytical model for the output link utilization and packet loss probability of MISO-FIFO optical buffers with CFDL. Before presenting our analytical model we provide background on different modeling approaches that have been reported in the literature.

Several analytical models have been reported for both synchronous and asynchronous packet switching networks with fixed fiber delay line buffers. In [17–19], shared memory synchronous architectures were evaluated, while [17, 20–24] provided analysis of asynchronous architectures. In this paper we consider an asynchronous architecture as it is better suited for direct IP over WDM. A Markov Chain (MC) based analysis has been developed in [17] for asynchronous architectures, and our model closely follows the MC model described in [17]. However we improve on the MC based model proposed in [17], and extend our model to include controllable fractional delay lines.

We assume a Poisson arrival process, since in the core network packets are aggregated from a large number of flows [17]. Although it has been observed that real Internet traffic tends to be self similar [28], in core routers, where our optical buffer array will be used, the traffic load tends to remain Poisson, as shown in [29, 30]. Therefore we use Poisson model for our analytical evaluation of ODL and CFDL buffers. We consider the case of fixed length packets, which is consistent with the assumption made in [17]. Also, it has been experimentally observed in [31] that the majority of the IP packets have a fixed length of either 1024 bytes (ignoring the acknowledgement packets of 40 bytes) and therefore the IP packets can be modeled as fixed length packets. However, it is also possible to enhance our model to incorporate any type of packet length distribution using the methodologies provided in [23–24]. We first investigate the limitations of fixed length ODLs. We provide the simple MC model presented in [17] for fixed length ODLs, and the performance parameters such as packet loss probability (PLP) and output link utilization calculated using that MC [17]. We then perform an asymptotic analysis on the link utilization formula published in [17] to find an upper bound on link utilization assuming fixed-length packets and a Poisson traffic arrival process. We also identify an important limitation of the MC model proposed in [17] and suggest a remedy to this limitation. We next provide a similar analytical framework to model our MISO-FIFO buffer with CFDLs. We begin with an analysis based on a delay factor of *F*=2, and later generalize the model for any F.

#### 5.1 Markov chain model for fixed length ODLs

In this model we use a MISO-FIFO structure with fixed length ODL units as single buffering elements. It is easy to see that the queuing performance of the MISO-FIFO structure is similar to the buffer structure shown in Fig. 2. However, we consider the MISO-FIFO structure here, as it reduces the number of buffering elements. An example timing diagram is shown in Fig. 4. The packet length is of a fixed duration *D*. The delay units have the same delay *D*. The value of *Q _{L}* in the left margin of the timing diagram of Fig. 4 indicates the instantaneous queue length. The

*P*indicates a state transition from

_{ij}*Q*=

_{L}*i*to

*Q*=

_{L}*j*. The bottom part of the timing diagram shows the output link occupancy, which provides information about the timing when the buffering units place the packets on the output link. Each packet arrival (indicated by a bold arrow) is followed by the sequence of events the packet experiences in the buffer. The first event in the sequence is the gray shaded service time indicating the time the packet takes to pass the corresponding coupler. Next are the series of delays through the delay lines (indicated by white boxes). The number of delays depends on where in the queue the packet has been inserted. For example, if

*Q*=3, the packet has to pass through two successive ODL elements before entering the output link.

_{L}The ODLs in Fig. 4 act as memory-less buffers. This is because the queue length evolution depends only on the current queue length and the current inter-arrival time. It does not depend on the history of the process. This is why ODL buffers can be analyzed using a Markov Chain model. The queue length always increases by one if a packet arrives within the previous service time, irrespective of the occupancy of any of the buffering elements. As shown in the timing diagram, whenever a packet arrives within the service time of the last arrived packet (packet duration-*D*) the queue length grows by one (as happened for the transitions *P _{12}*,

*P*and

_{23}*P*). Similarly from Fig. 4, as depicted in the transition P

_{34}_{44}, the queue remains in the same state if the inter-arrival time between packets is between

*D*and

*2D*. The queue length is reduced by n when (

*n*+

*1*)

*D*< inter-arrival time <(

*n*+

*2*)

*D*. For example, the transition

*P*(where

_{42}*n*=2) requires the inter-arrival time between the 5

^{th}and 6

^{th}arrivals to be between

*3D*and

*4D*. From these observations we can draw the Markov Chain state transition diagram as described in [1].

To show that the states in the MC have a stationary distribution, we can argue as follows. Because the arrival process is Poisson, any new arrival is independent of the previous arrival. Moreover, we have already seen that the queue evolution in ODLs depends only on current queue length and the last inter-arrival time. Therefore we can conclude that the queue state transition probabilities are independent of time and queue states have stationary probabilities.

Figure 5 shows the finite-state MC state transition diagram indicating all the state transition probabilities, where *B* denotes the number of buffering elements and *Q* denotes the overall traffic load at that output port. If the packet arrival rate is *λ*, then *Q*=*λD*. The balance equation derived in [17] is as follows:

where *π _{i}* is the probability of being in state

*i*. The solution of Eq. (1) can be found through successive substitution:

where *q*=*e*
*Q*-1. Additionally it has been shown in [17] that when B→∞, *π _{i}*=

*π*1

*q*

^{i-1}. It is well known that for

*q*<1 (equivalently

*Q*<ln(2) or

*Q*<0.693), the countable state space MC is positive recurrent and will have a stationary distribution [25]. For

*Q*>0.693, MC becomes transient and

*π*=0 for any

_{i}*i*<∞. This implies that no matter how large the buffer is, the queuing system will use up all the buffering space for

*Q*>0.693.

The packet loss probability PLP can be calculated as the probability that a packet arrives while the queue is in the (*B*+*1*)^{th} state. Therefore,

For electronic buffers PLP is always equivalent to *π*
_{B+1}, as a packet that arrives when the queue is full will always be lost. However, in ODLs, while in the (*B*+1)^{th} state, a packet can still be served if the inter-arrival time is greater than the value *D* and less than 2*D*.

Similarly the link utilization (*ρ*) can be calculated as the percentage of the traffic load that has been successfully delivered. Therefore,

For the scenario *B*≫1and high load scenario, i.e., q→1- :

The limits in equation (5) are valid because when, *q*→1-, the states can still be considered to have stationary distribution at the limiting condition. Also, here the limit on *B* is evaluated prior to the limit on *q* because in a real network scenario we have to ensure first that the queue is long enough before imposing the high traffic load condition.

It is easy to show that the maximum value of *ρ* occurs when *Q*=0.693 and the value is *ρ*=0.693. Therefore with finite delay ODLs the maximum link utilization that can be achieved is 69.3% for Poisson traffic arrivals. This is due to the voids created by the fixed delay lines in between successive packet transmissions as depicted in the timing diagram in Fig. 4. This simplified MC model [17] does not take into account packets dropped after the queue reaches the (*B*+1) state. A timing diagram of a typical packet drop scenario is provided in Fig. 6, where it has been assumed that the queue is already in the *B*+1 state. As shown in the diagram, if the next packet arrives within the service time of the last queued packet, it is discarded and the queue waits for a new arrival. If the next packet arrives just after the service time is over, it is queued and the queue remains in the *B*+1 state. Here the total inter-arrival time is the summation of the two previous inter-arrival times. Therefore, ideally this new inter-arrival time should follow the Erlang distribution with shape parameter *k*=2 [26] as it is the summation of two independent and exponentially distributed random variables. However, for simplicity we assume the inter-arrival process remains exponentially distributed with a new offered load reduced by a factor of 2. If 2 packets are discarded, similarly the load will be one-third and so on. This approximation has minimum effect over the end results as we shall see in Section 6. This formulation leads to a modified state transition diagram as shown in Fig. 7.

The added two states represent the scenario where 1 or 2 packets are discarded respectively. Similarly more states can be added to signify the scenario where more than 2 packets are discarded simultaneously. However, the effect of higher states diminishes as the probability of their occurrence is small. The transition probabilities from those newly added states to lower states are determined by the instantaneous load (*Q*/2 or *Q*/3) as described in Fig. 6. The transition from state (*B*+3) to itself represents when more than 2 packets has to be discarded. We calculated the PLP and the link utilization as described before. Since this MC model has no closed form solution, we calculate the utilization using numerical methods and observed that the utilization floor is 0.64 under high load (100%) and with a sufficiently large buffer size (100 packets). This is validated by simulations in Section 6. Additionally, we provide justification for adding 2 additional states (states *B*+2 and *B*+3 in Fig. 7) instead of only one state or more than two states as follows. We have evaluated the numerical solution for 1, 2, 3 and 4 added states and the calculated utilization floors are 0.66, 0.64, 0.637 and 0.636 respectively. Therefore, we can conclude that adding just 2 states provides sufficient accuracy in terms of the calculated link utilization for ODL buffers. In the next subsection we develop a similar MC model for the CFDL case.

#### 5.2 Markov chain model for the MISO-FIFO with CFDLs

In this subsection we first analyze the queuing performance of the MISO-FIFO buffer using CFDLs with a delay factor of *F*=2. We then generalize the model for any delay factor.

Figure 8(a) shows a typical MISO-FIFO buffer using CFDLs with F=2, where each of the CFDL structures uses a staggered delay line similar to Fig 1 (c) to realize variable delays of either *D* or *D*/2. Note that the use of a staggered delay line structure introduces multiple connectors, switches and delay lines that may further introduce some additional loss. We It is a straight forward matter to equalize these losses by readjusting the split ratios of the couplers in Figure 3. Figure 8(b) shows a typical timing diagram for a MISO-FIFO buffer using CFDLs with *F*=2 to show how adjustable buffering using CFDLs achieves void filling. Similar to the Fixed ODL, the queue grows by one if the next packet arrives within the previous service time. However, the delay here in every stage is variable as compared to the fixed ODL where the delays are always fixed (*D*). This destroys the memoryless property of the process. The state transition from a higher to a lower state and even the transition probability of being in the same state depends on the various delays in all the successive stages. If *F*=2, the delay variable can only have two states, either *D* or *D*/*2* as shown in the timing diagram. Hence to calculate the transition probabilities we need to compute all possible combinations of delays in the relevant successive stages. We first start with a simple scenario where the packet arrives within the previous service time. Therefore the queue grows by one and a delay is scheduled according to the following rules:

Delay=*D* if packet inter-arrival time <*D*/*2*

Delay=*D*/*2* if packet inter-arrival time ≥*D*/*2*

The above rules are evident from the timing diagram in Fig. 8 in transitions *P _{23}* and

*P*respectively. We now calculate the probability of these two discrete events (assuming Poisson arrivals) as follows:

_{12}*p*(*D*/2)=*p*(*D*/2≤ inter-arival time ≤*D*|inter-arival time ≤*D*)

$$=\frac{{\int}_{D\u20442}^{D}\lambda {e}^{-\lambda t}\mathrm{dt}}{{\int}_{0}^{D}\lambda {e}^{-\lambda t}\mathrm{dt}}={e}^{-Q\u20442}\left[\frac{1-{e}^{-Q\u20442}}{1-{e}^{-Q}}\right]=x\phantom{\rule{.2em}{0ex}}\mathrm{where}\phantom{\rule{.2em}{0ex}}x={e}^{-Q\u20442}\left[\frac{1-{e}^{-Q\u20442}}{1-{e}^{-Q}}\right]$$

*p*(*D*=*p*(inter-arival time <*D*/2| inter-arival time ≤*D*)

$$=1-p(D\u20442)=\left[\frac{1-{e}^{-Q\u20442}}{1-{e}^{-Q}}\right]=\mathrm{xy}\phantom{\rule{.2em}{0ex}}\mathrm{where}\phantom{\rule{.2em}{0ex}}y={e}^{Q\u20442}$$

Here *λ* is the average inter-arrival time and *Q*=*λD*=average load in the network. The state transition diagram is the same as Fig. 7 with different transition probabilities. We segregate the transition probabilities into four categories:

*p*
_{r,r+1}: transition to a higher state

*p*
_{n,r} (where *n*>*r* and *r*>1): transition to a lower state without emptying the queue

*p*
_{r,1} (where *r*>1): transition to state 1

*p*
_{r,r}: transition to the same state

From the previous discussion we know that *P*
_{r,r+1}=1-*e*
^{-Q}, 1 for category (A). The details of the other three transition probabilities are presented in the Appendix.

With these transition probabilities the state transition diagram is shown in Fig. 9. Here we also added two extra states, namely (*B*+2) and (*B*+3) to accommodate the scenarios where packets are discarded. It is easy to verify the accuracy of our model from the observation that the sum of the probabilities leaving a state should be 1. For example, for any state $r,\sum _{i=1}^{r+1}{p}_{r,i}=1$. It is a trivial exercise to show this condition holds in the state diagram shown in Fig. 9 for any *r*.

The balance equations for Fig. 9 are as follows:

where *π _{i}* is the probability of being in state

*i*. We numerically solve the set of equations for all

*π*. Next the link utilization is calculated as described in equation 4. This concludes the queuing analysis of the MISO-FIFO buffer with CFDLs with a delay factor of

_{i}*F*=2. We now provide a way to generalize the model for any factor F.

With a factor of F, the delay provided by any CFDL unit can vary from *D*/*F*, *2D*/*F*, …, *D*. Similar to eq. (6) and (7) we can derive the probability that the delay is (*F*-*j*)*D*/*F* as *p*(*F*-*j*), given that the delay is offered due to overlapping packet arrivals. Here *j* varies from 0 to *F*-1.

$p\left(F-j\right)=\frac{{\int}_{jD\u2044F}^{\left(j+1\right)D\u2044F}\lambda {e}^{-\lambda t}\mathrm{dt}}{{\int}_{0}^{D}\lambda {e}^{-\lambda t}\mathrm{dt}}={\left({e}^{-Q\u2044F}\right)}^{j}\frac{\left(1-{e}^{-Q\u2044F}\right)}{\left(1-{e}^{-Q}\right)}={\alpha}^{j}\beta $

where α=*e ^{−Q/F}* and $\beta =\left[\frac{1-{e}^{-Q\u2044F}}{1-{e}^{-Q}}\right]$

Now for the *r* subsequent packet arrivals where all these packets have to be queued, the total delay offered can vary from *rD*/*F* to *rD* with a step size of *D*/*F*. Therefore the probability that the total delay is *iD*/*F* will be:

$p\left(i\right)={i}^{\mathrm{th}}\mathrm{term}\phantom{\rule{.2em}{0ex}}\mathrm{of}{\left[\sum _{j=1}^{F}{\alpha}^{j}\beta \right]}^{r}$

where *r*≤*i*≤*rF*. Now,

${\left[\sum _{j=1}^{F}{\alpha}^{j}\beta \right]}^{r}={\left(\alpha \beta \right)}^{r}{\left[1+\alpha +\dots +{\alpha}^{F-1}\right]}^{r}={\left(\alpha \beta \right)}^{r}{\left(1-{\alpha}^{F}\right)}^{r}{\left(1-\alpha \right)}^{-r}$

$={\left(\alpha \beta \right)}^{r}\left[1-{\phantom{\rule{.2em}{0ex}}}^{r}{C}_{1}{\alpha}^{F}+{\phantom{\rule{.2em}{0ex}}}^{r}{C}_{2}{\alpha}^{2F}+\dots +{(-\alpha )}^{\mathit{rF}}\right].$

$\left[1+r\alpha +\frac{r\left(r+1\right)}{2}{\alpha}^{2}+\frac{r\left(r+1\right)\left(r+2\right)}{2.3}{\alpha}^{2}+\dots +\frac{r\left(r+1\right)\dots \left(r+\mathrm{rF}\right)}{2.3\dots \left(\mathrm{rF}\right)}{\alpha}^{\mathrm{rF}}\right]$

From this expression the values of *p*(*i*) can be numerically calculated. We can then calculate the transition probabilities in a similar manner to equations (A1), (A2) and (A3). We follow the same steps to evaluate the link utilization as described for the case of *F*=2.

## 6. Results and discussion

In this section we consider the queuing performance of the MISO-FIFO buffer with fixed ODLs and with CFDLs, and discuss the advantages of using CFDLs. First, to observe the limitation of fixed ODLs we simulate the MISO-FIFO queue in Matlab with fixed ODLs for Poisson traffic arrivals. We use the Matlab matrix methods to solve the simultaneous equations for the probability of the queuing states (*π _{i}*’

*s*) in order to obtain our analytical results. We vary the load offered and the buffer size. Figure 10 shows a plot of the output link utilization with respect to the buffer size for different traffic loads.

Figure 10 suggests that an upper bound on utilization exits and the throughput is always less than an upper bound of 63%, no matter how high the traffic load is. The utilization floor appears to be due to the void creation between transmissions. This also suggests that our correction in Section 5 over the model proposed for fixed length ODLs in [17] achieves a more accurate result for PLP and link utilization calculations. It has been shown in Section 5 that the asymptotic bound on utilization is predicted to be 69.4% by the model proposed in [17], which is almost 6% higher than the simulation results suggest in Fig. 10. In contrast, our corrected model in Section 5 provides a more accurate value of 64% for the utilization floor. The other interesting point to observe is that for fixed ODLs, if the load is high then the throughput remains almost constant for varying buffer sizes. This is encouraging for optical buffering, as it enables the possibility of designing optical routers with minimal or even no buffers. While this observation is true with our simplified Poisson arrival process, in a real network, the traffic load is always controlled due to the transmission control protocol’s (TCP) flow control mechanism and it has been observed to follow a well known saw-tooth pattern [27]. Nevertheless, as shown in [27] the saw-tooth patterns of TCP flows tend to smooth each other out once multiple competing TCP flows are present. Therefore, the traffic flows from multiple sources can be well approximated by a Poisson process. However, the results in Fig. 10 also suggest that this independency of throughput over buffer size is achievable only with a significant compromise in channel utilization (>30%).

We next simulate the MISO-FIFO buffer with CFDLs for different controllable buffer delay factors (i.e., *F*=2, 4, 8). We plot the link utilization for different buffer sizes and different traffic loads. Figure 11 shows the plots of output link utilization with different buffer sizes for offered traffic loads of 0.8 and 1 respectively. Figure 11 demonstrates how the void filling of CFDL buffers improves the link utilization. As the granularity of CFDL decreases (i.e., when *F* increases), the void filling capabilities are higher and hence the link utilization increases. Figure 11 shows that with F=8, we can achieve a utilization of 93%, in comparison to a maximum 64% utilization achievable without CFDL. This is an increase of 30% in link utilization and makes the CFDL buffers an important candidate for future all-optical buffers. Figure 11 also demonstrates that CFDL buffers provide a closer approximation to RAM like functionality in comparison to conventional fixed length ODLs. With CFDL buffers the link utilization improves as the buffer length increases instead of reaching an upper limit. This is evident when we compare the graphs in Fig. 10 and 11 with load=1. This kind of behavior is typical of electronic RAM buffers. Hence the MISO-FIFO buffer with CFDLs is a better candidate to replace electronic RAM in order to design future all-optical routers.

Finally, we validate our analytical model with the simulation of CFDLs. Figure 12 shows a comparison of both analytical and simulation results for link utilization vs. buffer size with various controllable factors (*F*=2, 4). Figure 13 provides a further comparison between the analytical and the simulation results in terms of packet loss probability (PLP) for CFDL buffers with F=2. The plot shows good agreement between the simulation and our analytical model, validating our analytical approach.

## 7. Conclusion

We have proposed a new all-optical buffering architecture (MISO-FIFO) that substantially reduces the overall length of the ODLs required compared to existing optical buffers with fixed ODLs and improves link utilization. We have investigated the queuing performance of such buffers in terms of output link utilization and packet loss probability. We have also introduced an improved Markov Chain model for optical buffers with fixed delay lines. The fixed delay lines create voids between successive transmissions due to the fixed delay they can offer and eventually reduce the link utilization. Our model demonstrates that an upper bound on link utilization exists (≈ 64%) for buffers using fixed ODLs due to void creation, and the maximum link utilization is independent of buffer length. Hence small buffering or even no buffering suffices. This observation encourages the implementation of all-optical packet switching with little or no optical buffering. However, this comes with a severe penalty (≈ 36%) in link utilization and hence the overall network expenditure. We then introduced controllable fractional delay lines (CFDLs) as the basic buffering elements instead of fixed delay lines to mitigate the effect of void creation. We provided an analytical model for the queuing performance of MISO-FIFO buffers with CFDLs and validated our model using simulations. Our results show that as the granularity of the CFDL buffers reduces, the link utilization increases. With a granularity factor of *F*=8, the CFDL can improve the link utilization by almost 30%, and the upper bound for link utilization increases to 93%.

## Appendix: calculation of transition probabilities (F=2)

(A) *p*
_{r,r+1}: From section 5.1 we know that *p*
_{r,r+1}=1-e^{-Q}.

(B) *p*
_{n,r}: To compute *p*
_{n,r} we assume that in all the previous (*n*-*r*) stages the total delay accumulated is *i*′*D*/*2* where *i*′ is a random variable in the range (*n*-*r*)≤*i*≤2(*n*-*r*). The variable *i*=*i*′-(*n*-*r*) is binomially distributed with parameters *x* and (*n*-*r*). The delay in the (*n*-*r*-*1*)^{th} stage may be either *D* or *D*/*2*. Depending on this, if the packet service time is fixed (D), to have a transition from state n to state r, the following conditions have to be satisfied:

1. If the (*n*-*r*-*1*)^{th} delay is *D*/*2*, (*n*-*r*)*D*/*2*+*iD*/*2*+*D* ≤ inter-arrival time ≤ (*nr*) *D*/*2*+*iD*/*2*+*D*+*D*/*2*

The probability of this event is *p*(*D*/*2*)*e*
^{-(n-r+i+2)Q/2}(1-*e*
^{-Q/2})

2. If the (*n*-*r*-*1*)^{th} delay is *D*, (*n*-*r*)*D*/*2*+*iD*/*2*+*D* ≤ inter-arrival time ≤ (*n*-*r*)*D*/*2*+*iD*/*2*+*D*+*D*

The probability of this event is *p*(*D*)*e*
^{-(n-r+i+2)Q/2}(1-*e*
^{-Q})

Therefore

$$+p\left(D\right){e}^{-\left(n-r+i+2\right)Q\u20442}\left(1-{e}^{-Q}\right)]\phantom{\rule{.2em}{0ex}}\mathrm{where}\phantom{\rule{.2em}{0ex}}p\left(i\right)={\phantom{\rule{.2em}{0ex}}}^{\left(n-r\right)}{C}_{i}{y}^{i}{x}^{n-r}$$

$$={\left(\frac{2{e}^{-Q}}{1+{e}^{-Q\u20442}}\right)}^{n-r+1}\left[\frac{{e}^{-Q\u20442}-2{e}^{-Q}+1}{2}\right]$$

(C) *p*
_{r,1}: Similarly *p*
_{r,1} is the probability that no arrival happens in the next period (*r*-*1*)*D*/*2*+*iD*/*2*+*D*, where *i* is again binomially distributed with parameters *x*, (*r*-*1*).

$$={\left(\frac{2{e}^{-Q}}{1+{e}^{-Q\u20442}}\right)}^{r-1}{e}^{-Q}$$

(D) *p*
_{r,r}: Finally, *P*
_{r,r} is the probability that no arrival happens between *D* and *3D*/*2* if the previous delay is *D*/*2* or between *D* and *2D* if the previous delay is *D*.

## References and links

**1. **S. Yoo and B. Mukherjee, “Advances in photonic packet switching an overview,” IEEE Commun. Mag. **2**, 84–94 (2000).

**2. **D. K. Hunter and I. Andonovic, “Approaches to optical internet packet switching,” IEEE Commun. Mag. **9**, 116–122 (2000). [CrossRef]

**3. **M. J. O’Mahony, D. Simeonidou, D. K. Hunter, and A. Tzanakaki, “The application of optical packet switching in future communication networks,” IEEE Commun. Mag. **3**, 128–135 (2001). [CrossRef]

**4. **D. K. Hunter et al., “WASPNET: a wavelength switched packet network,” IEEE Commun. Mag. **3**, 84–94 (1999).

**5. **D. K. Hunter, M. C. Chia, and I. Andonovic, “Buffering in optical packet switches,” IEEE/OSA J. Lightwave Technol. **16–12**, 2081–1094 (1998). [CrossRef]

**6. **R. S. Tucker et al., “Slow-light optical buffers: capabilities and fundamental limitations,” IEEE/OSA J. Lightwave Technol. **23–12**, 4046–4066 (2005). [CrossRef]

**7. **R. S. Tucker, “The role of optics and electronics in high capacity routers,” IEEE/OSA J. Lightwave Technol. **24–12**, 4655–4673 (2006). [CrossRef]

**8. **N. McKeown et al., “Part III: routers with very small buffers,” ACM SIGCOMM Computer Communication Review **35–2**, 73–89 (2005). [CrossRef]

**9. **
CISCO router specification, “CRS1 specification” (CISCO Networks 2004), http://newsroom.cisco.com/dlls/2004/prod_052504.html.

**10. **L. Tancevski, S. Yegnanarayanan, G. Castanon, L. Tamil, F. Masetti, and T. McDermott, “Optical routing of asynchronous, variable length packets,” IEEE J. Sel. Areas Commun. **18–10**, 2084–2093 (2000).

**11. **S. H. Chin, A. Franzen, D. K. Hunter, and I. Andonovic, “Synchronisation schemes for optical networks,” IEE Proc. Optoelectron **147–6**, 423–427 (2000). [CrossRef]

**12. **I. Chlamtac et al, “CORD: contention resolution by delay lines,” IEEE J. Sel. Areas Commun. **14–5**, 1014–1029 (1996). [CrossRef]

**13. **P. Gambini et al., “Transparent optical packet switching: network architecture and demonstration in KEOPS project,” IEEE J. Sel. Areas Commun. **16–17**, 1245–1259 (1998). [CrossRef]

**14. **Y. K. Yeoet al., “A dynamically reconfigurable folded-path time delay buffer for optical packet switching.” IEEE Photon. Technol. Letters **16–11**, 2559–2561 (2004). [CrossRef]

**15. **M. J. Karol et al., “Input versus output queueing on a space-division packet switch,” IEEE Trans. Commun. **35–12**, 1347–1356 (1987). [CrossRef]

**16. **R. Geldenhuys et al., “Selecting fibre delay line distributions for travelling buffers in an all-optical packet switched cross-connect,” in *Proceedings of IEEE CCECE* (Montreal, Canada, 4–7 May 2003).

**17. **X. Zhu and J. M. Khan “Queuing models of optical delay lines in synchronous and asynchronous optical packet-switching networks,” Optical Engin. **42–6**, 1741–1748 (2003). [CrossRef]

**18. **M. C. Chia and D. K. Hunter et al., “Packet loss and delay performance of feedback and feed-forward arrayed-waveguide gratings-based optical packet switches with WDM inputs-outputs.” IEEE/OSA J. Lightwave Technol. **19–9**, 1241–1254 (2001). [CrossRef]

**19. **P. D. Bergstrom, M. A. Ingram, A. J Vernon, J. L. A. Hughes, and P. Tetali, “A Markov chain model for an Optical Shared-Memory Packet Switch,” IEEE Trans. Commun. **47–10**, 1593–1603 (1999). [CrossRef]

**20. **T. Zhang, K. Lu, and J. R. Jue, “Shared fiber delay line buffers in asynchronous optical packet switches,” IEEE J. Sel. Areas Commun. **24–4**, 118–127 (2006). [CrossRef]

**21. **F. Callegati, “Optical buffers for variable length packets,” IEEE Commun. Letters , **4–9**, 292–294 (2000). [CrossRef]

**22. **F. Callegati, “On the design of optical buffers for variable length packet traffic,” *Ninth International Conference on Computer Communications and Networks *(Las Vegas, Nevada, USA, 6–18 Oct. 2000), pp. 448–452.

**23. **R. C. Almeida, J. U. Pelegrini, and H. Waldman, “A generic-traffic optical buffer modeling for asynchronous optical switching networks,” IEEE Commun. Letters **9–2**, 175–177 (2005). [CrossRef]

**24. **R. C. Almeida, J. U. Pelegrini, and H. Waldman, “Optical buffer modeling for performance evaluation considering any packet inter-arrival time distribution,” *IEEE International Conference on Communications***3**, (Paris, France, 20–24 June 2004), pp. 1771–1775.

**25. **G. F. Lawler, *Introduction to Stochastic Processes*Chapman & Hall (1995).

**26. **L. Kleinrock, *Queuing systems: volume I - Theory* (Wiley Interscience, New York, 1975).

**27. **G. Appenzeller, I. Keslassy, and N. McKeown, “Sizing router buffers,” *Proceedings of ACM SIGCOMM*, (Aug. 2004).

**28. **V. Paxson and S. Floyd, “Wide-Area Traffic: The Failure of Poisson Modeling,” IEEE/ACM Trans. on Networking , **3–3**, 226–244 (1995). [CrossRef]

**29. **J. Cao, W. Cleveland, D. Lin, and D. Sun, “Internet traffic tends toward Poisson and independent as the load increases” in *Nonlinear Estimation and Classification* (Springer, New York 2002).

**30. **J. Cao, W. Cleveland, D. Lin, and D. Sun, “The effect of statistical multiplexing on the long range dependence of Internet packet traffic,” Bell Labs Tech. Reports (2002).

**31. **P. Salvador, A. Pacheco, and R. Valadas, “Modeling IP traffic: joint characterization of packet arrivals and packet sizes using BMAPs,” Elsevier J. Comput. Networks **44–3**, 335–352 (2004). [CrossRef]