3.6.1   Buffering

The most popular method of resolving contentions in electronic switches is buffering,
which exploits the time domain. In buffering schemes, the packets that lose a
contention (all but one of those who contend) are queued in an electronic RAM
module and are thus delayed until the switch is ready to forward them. When the
switch determines that it can forward a packet, it retrieves it from its memory and
directs it to the proper output port. This mode of operation is referred to as the
“store-and-forward” paradigm. Electronic random access memory is a mature
technology and is available in large quantities at a low cost. This justifies why buffering
is the preferred contention resolution method in the electronic domain.

However, similar buffers cannot be directly implemented in optical switches
because of the primitive state of optical RAM technology, limited to experimental
laboratory demonstrations [2].

The optical alternative to buffering is the use of fiber delay lines (FDLs) [34–37].
These are merely additional pieces of fiber that contending packets must traverse in
order to be delayed until the switch is ready to forward them. Given the constantly
increasing rate at which optical signals travel, the lengths of fiber delay lines are
estimated in the order of several kilometers. Such FDLs can offer a finite and
fixed amount of delay, so their operation is not equivalent to an electronic
memory module. Furthermore, there is no random access capability, because a
packet that enters a continuous piece of fiber cannot be retrieved before it
emerges on the other side.

In an optical packet switch, the wavelength dimension can be used to increase the
capacity and utilization of an FDL buffer. By using wavelength division multiplexing,
packets in different wavelengths can be “stored” on the same delay line,
thus increasing the buffer capacity [38]. Assuming that N wavelengths can be multiplexed
on a single FDL, each FDL has a capacity of N packets. The number of
packets that can be stored in an FDL buffer is referred to as the buffer depth.

If a packet needs to be stored on a particular FDL and its wavelength is already
occupied, a tunable optical wavelength converter can be used to shift the packet to
a different wavelength that can be accommodated in the buffer in question. These
points are illustrated in Figure 3.10. In the first scenario (Fig. 3.10a), two packets
having the same wavelength need to be buffered concurrently. Because there are
no wavelength converters available in this case, two FDLs must be utilized in
order to accommodate both packets, despite the fact that there is “room” (i.e., available
wavelengths) in FDL 1. In the second case (Fig. 3.10b), one of the packets is
converted to a suitable wavelength and both packets are stored in the same FDL [2].

Buffers can be placed at the switch inputs, outputs, or both.² Input buffering leads
to head-of-line blocking, because a packet in the head of the queue whose output is
blocked does not allow other packets whose outputs are free to be served before it;
this limits the switch throughput. Input buffering is also not easy to realize optically
because a packet’s delay in an input buffer is not determined before entering it. Conversely,
the advantage in output buffering is that the packet delay is determined
before the packet enters the buffer so that the desired output port is free when it
exits [39].

We can distinguish between two fundamental architectures, namely feed forward
and feedback optical buffers. In a feed forward architecture, a packet is buffered
only once and is subsequently sent to the switch in order to be forwarded. In a feedback
architecture, packets can recirculate in the buffer more than once in order to
achieve a delay that is longer than the maximum delay of the buffer. For this
reason, feedback architectures are also referred to as recirculating buffers, and
feed forward architectures are referred to as traveling buffers. Obviously a packet
cannot travel in the buffer indefinitely due to signal impairments (e.g., attenuation
and crosstalk) [2]. In a feedback architecture, arriving packets can preempt
packets that are already in the switch. This allows the implementation of multiple
quality-of-service (QoS) classes [1]. Buffers that allow recirculation can offer
longer delays with smaller fiber lengths, but cannot handle packets larger than the
delay achievable with one recirculation. The maximum delay achievable in a
recirculating buffer depends on the loop length and the maximum allowed
number of recirculations. The maximum delay achievable in a traveling-type
buffer is determined by the length of the delay lines, namely, the optical signal
path. A large packet buffer depth requires many delay lines of different lengths.
Consequently, this type of buffer is bulky [40]. Approaches for achieving large
delays while reducing the length of traveling buffers are under study and may for
example require that packets traverse the same delay line twice (in opposite
directions) in order to halve the delay line length [41].

Another distinction between optical buffer architectures can be made based on
the number of stages they contain. Optical buffers are either single-stage or multi-
stage, where each stage is a single continuous piece of fiber (a single delay line).
A single stage is generally easier to control, but with multiple stages it is possible
to economize on the amount of hardware required for large buffer depths [42].

Packets are assigned to a wavelength on a particular FDL by the buffer control
algorithm. The choice of the buffer control algorithm is also a critical decision, as
it can greatly affect the packet loss rate. For example, packets may be assigned to
wavelengths in a round robin fashion. In this scheme packets are served in the
order of arrival and they are assigned to the first available wavelength. Another
approach is to assign a packet to the least occupied wavelength in an effort to
balance the load among all wavelengths.

Generally, the complexity of the algorithm that assigns packets to wavelengths
and FDLs increases as the complexity of the buffer architecture increases. Consider
for instance a buffering unit with recirculation capability. At the end of a recirculation
a packet that cannot be immediately served but has not exceeded the allowed
number of recirculations may be assigned a different delay line and enter the
buffer again. The issue of determining a suitable wavelength and a set of delays
(i.e., fiber delay lines for each recirculation) that will allow a packet to exit the
buffer when its output port is free and can accommodate it is challenging, particularly
because this process has to be executed very quickly yet efficiently in order
to maintain a high switch throughput and a low packet loss rate. The selected wave-
length must be free on all delay lines and the output port for the packet duration,
and the total delay incurred by the packet should be as low as possible. The
control algorithm may consider individual packets or groups of packets in order
to make faster and better scheduling decisions [43, 44]. A packet that cannot be
accommodated by any combination of delays and wavelengths should be discarded
as early as possible in order to prevent wastage of resources.

For bursty traffic, which is more realistic, the buffer depth must be increased
significantly [45]. Sophisticated scheduling is required to efficiently use the
available buffer space. The implementation of large buffer depths requires the
use of many delay lines and results in bulky and complex hardware. Several
architectures for optical packet switches using optical buffers have been proposed,
and a key issue in these architectures is the difficulty in achieving large buffer
depth [39].

The need for variable packet delays is satisfied by using fibers of different
lengths. The distribution of fiber lengths as well as the minimum and maximum
lengths (corresponding to the minimum and the maximum achievable delays) are
important design parameters. These parameters are calculated based on a study
of the network traffic, the distribution of packet lengths, and the overall network
operation (i.e., synchronous or asynchronous), and they determine the maximum
amount of bits that can be stored in the buffer for a given data rate. The delays
that can be achieved are usually multiples of a basic unit D, referred to as the
buffer granularity [46], whereas the maximum delay achievable (usually equal to
the maximum packet length in unslotted networks) is also referred to as buffering
capacity. The importance of the proper dimensioning of the delay unit and the
choice of an optimal value of the maximum delay is evident from the following
observations [2]:

• If the delay unit is very small, the time resolution of the FDL buffer increases
  but the buffering capacity (which is a multiple of the delay unit) decreases.
• If the delay unit is chosen to be large, then the buffering capacity is also
  large, but the time resolution of the buffer is very coarse and the output link
  is underutilized; as a result there is a degradation in the buffer performance
  and therefore in the performance of the overall switch.

In a network with fixed-length packets it is natural to choose D equal to the length
of the packets [47]. The optimal value of the delay unit realizes the best trade-off
between time resolution and amount of delay achievable [2]. As for the number
of FDLs that are required in a switching node in order to achieve a specified
packet loss ratio, there have been various suggested architectures in the literature,
ranging from switches with large optical buffers [45] to switches with absolutely
no buffering capacity that only rely on wavelength conversion for contention
resolution [48]. It has been shown that increasing the number of FDLs or the
number of allowed recirculations above a certain threshold provides only small
improvements, which are observed only under heavy loads [49].

The asynchronous operation of the switch impacts negatively on the performance
of the FDL buffer because of the unpredictable nature of the network traffic.
In order to reach a low packet loss probability, a large number of delays would
be necessary, and thus a large number of FDLs. However, technological and
practical issues limit the number of FDLs that can be accommodated in a
single array. One possible way to overcome this limitation is by means of multiple
stages of buffering. The main problem is that, because of the finite and
usually small number of delay lines, delays are available in a discrete set, and
the queuing of asynchronous and variable-length packets requires delay values
from a continuous set that depends on the arrival pattern and packet lengths.
The resulting effect is that the FDL buffer creates artificial gaps between
packets, resulting in an underutilization of the output links. This effect can be
considered equivalent to an artificial increase in the average packet length (or
the introduction of excess traffic), and the performance of the buffer is very
sensitive to this phenomenon [2].

Assume two packets with lengths L₀ and L₁, arriving at times t₀ and t₁, are contending
for the same output. The second packet will have to be delayed in the FDL
buffer for an amount D₁, which can only be ≥(t₀ + L₀ - t₁). If the inequality holds
(which is true in most cases due to asynchronous arrivals), the output distribution of
the packets features a gap or void between the two packets. If nothing is done
to access that void, it will appear as if the first packet stretches all the way to the
second packet, and hence as if the traffic load has been increased. Thus, the
process of creation of voids in the output distribution results in excess load. This
phenomenon is one of the most important loss mechanisms in asynchronous
operation, impairing the performance sizably. It should be stressed that the effect
occurs solely due to the large granularity of the optical FDL buffer; electronic
buffers operate on a much finer granularity and can delay the packet for almost
an arbitrary amount, hence no voids are present [6].

The size of the voids, and therefore the associated excess load, depends on the
distribution of packet lengths and on the distribution of interarrival times, both of
which are crucial traffic parameters. On the other hand, it depends on the amount
of delay D, which corresponds to the granularity of the FDL optical buffer, and is
therefore a switch parameter [6].

Rather than scheduling a new packet under consideration for a particular output
to be transmitted immediately after the last one, it may be scheduled to “fill” a void
on the correct output in a non-FIFO manner [50]. Void filling permits a more efficient
use of the buffering capacity. On the negative side, void-filling algorithms
may disturb the sequence of packets and naturally increase the control complexity
of the switch. The complexity of the algorithm depends on the number of wavelengths
per fiber, the number of voids that can be stored in the switch’s electronic
memory (and can be used for scheduling a packet), and the number of distinct
delay lines in the FDL buffer. Conditions 1 and 2 contribute to the complexity by
increasing the number of voids that need to be inspected in each scheduling, and
are in that sense interrelated. Condition 3 increases the checking time to determine
whether there is available delay capable of delaying the packet such that it coincides
with an existing void [6].

Voids between packets can also emerge if the lengths of the delay lines are not
consecutive multiples of the basic delay unit, that is, in nondegenerate buffers.
Buffers with FDLs whose delays are consecutive multiples of D are referred to as
degenerate [51]. In a buffer consisting of B FDLs, the first introduces a delay of 0
time units (e.g., μ s), the second of D time units, the third of 2D units, and the Bth
a delay of D_MAX = (B - 1)D time units [47]. The advantage of nondegenerate
buffers is that longer delays can be achieved with fewer delay lines (as not all
intermediate delays are supported).

The implementation of optical buffers using FDLs features several disadvantages.
Fiber delay lines are expensive and bulky, because the required fiber length
is directly proportional to the propagation time of light in the fiber. A packet
cannot be stored indefinitely on an FDL. Delay line optical buffers increase the
accumulation of intraband crosstalk and ASE noise. Because of these quality degradations,
optical signals may require amplification. In addition, buffering can lead to
an increase in the end-to-end delay [52]. These disadvantages suggest that the use of
optical buffers based on FDLs should be combined with other methods for contention
resolution (such as wavelength conversion) so that the need for buffering is
reduced [2].

The flexibility of an optical packet switch could be enhanced if the FDL buffers
were tunable. Inclusion of tunable all-optical buffers enhances the performance of
OPS routers in terms of packet loss rate, buffering latency, and jitter [53]. Furthermore,
the negative impact of voids could be alleviated if FDLs were tunable. A
tunable FDL can change its size to fit a buffered burst and, hence, reduce the time
for which the output port is free after transmission of the previous burst (void).
Several approaches for tunable FDLs are also being investigated. Examples
include implementations of recirculating loops, which are controlled using optical
processing technology [18] and variable optical delay circuits using highly nonlinear
parametric wavelength converters.

_________________________________________________
²The buffers described in this section are the ones used for contention resolution. Delay lines may also be
included in the input of the switch to delay the packets while their headers are being processed.