Switched Delay Lines
One common approach to construct optical queues is to use optical Switches and fiber Delay Lines (SDL). The idea of using SDL for constructing an optical queue is to route (non-stopping) optical packets through a series of fiber delay lines so that optical packets depart from the queue at the right time.
Fig. 1. An illustrating example of using switched delay lines for conflict resolution
In Fig. 1, we illustrate this idea via a simple example. There are two input links that are multiplexed into an output link. Suppose that two packets arrive at both input links. This causes a conflict for the output link. To resolve such a conflict, we can first put these two packets through a 2 ¡Ñ 2 switch and distribute one packet to a zero delay transmission line (the upper link) and the other to a fiber delay line with one unit of delay (the lower link). By so doing, these two packets can be multiplexed into the same link sequentially.
Construction Theory
To construct an optical queue with a large buffer, one might need to cascade multi-stage SDL units. However, finding efficient control of the switches that distribute packets to resolve conflicts becomes a problem. For this, we have developed several systematic constructions for various optical queues.
(i) A self-routing n-to-1 multiplexer:
Fig. 2. A self-routing n-to-1 multiplexer with buffer nk -1
As shown in Fig. 2, there are k stages of SDL units (the last one is simply a bufferless multiplexer). Each stage, except the first stage, consists of an n ¡Ñ n crossbar switch and n fiber delay lines (with delays specified in the figure). Packets are assumed to be of the same size and it takes one unit of delay to transmit a packet. The first stage requires an n ¡Ñ (2n-1) switch as additional output links are used for dropping packets due to buffer overflow. The buffer size of such a multiplexer is nk -1.
We use output buffer emulation for this system. It keeps track of the number of packets stored in the system. If such a number exceeds nk -1, further arrivals are lost immediately. Let q be the number of packets stored in the system when a particular packet enters the system. Then we use the r-ary representation (r1, r2, ¡K, rk) of q for routing the packet through the network. There will not be any conflicts in the self-routing multiplexer, i.e., no more than one packet occupies the same link at any time.
(ii) Non-overtaking delay lines and FIFO queues:
A First-In-First-Out (FIFO) queue with buffer B is a network element that has one input link, one control input and two output links. One output link is for departing packets and the other is for lost packets. It satisfies the following four properties: (a) flow conservation: arriving packets from the input link are either stored in the buffer or transmitted through the two output links, (b) non-idling: if the control input is enabled, then there is always a departing packet if there are packets in the buffer or there is an arriving packet, (c) maximum buffer usage: if the control input is not enabled, then an arriving packet is lost only when buffer is full, and (d) FIFO: packets depart in the first in first out (FIFO) order. In Fig. 3, we show a construction of a FIFO queue with buffer 7.
Fig. 3 An implementation of a FIFO queue with buffer 7
A non-overtaking delay line is a FIFO queue with known departure times when packets arrive. As such, a non-overtaking delay line can also be implemented by a FIFO queue (see Fig. 3). The good thing for a non-overtaking delay is that self-routing is feasible and thus the control of switches is easy.
(iii) Priority Queues:
Like a FIFO queue, a priority queue with buffer B is a network element that has one input link, one control input link, and two output links. One output link is for departing packets and the other is for lost packets. When a packet arrives at the queue, it is associated with a label, called priority . As in a FIFO queue, a priority queue also satisfies the flow conservation property, the non-idling property, and the maximum buffer usage property. The only difference is that packets no longer depart in the FIFO order. Instead, if there is a departing packet at time t, then the departing packet is the one with the highest priority. A priority queue with buffer d1+d2+..+dMcan be constructed by using a single (M+1) ¡Ñ (M+1) switch as shown in Fig. 4.
Fig. 4 A construction of a priority queue via a single switch and fiber delay lines
Implementation
In this project, we will use a feedback system like the one in Fig. 4 to construct a 2-to-1 multiplexer. For example, in Fig. 5, we show a construction of a 2-to-1 multiplexer with buffer 22. When a packet with delay 14 arrives at time t, the packet is routed to the delay line with delay 1 at time t, the delay line with delay 3 at time t+1, and the delay line with delay 10 at time t+4, and to the output line at time t+14.
Fig. 5 A construction of a 2-to-1 multiplexer with buffer 22
To implement an 8 ¡Ñ 8 crossbar switch, we shall use an 8 ¡Ñ 8 AWG and wavelength converters. As shown in Fig. 6, an 8 ¡Ñ 8 AWG is a device that can route packets to different outputs according to their wavelengths. For instance, there are 8 wavelengths, indexed from 1,2,¡K8, in each input. Packets that use the kth wavelength in the first input are routed to the kth output. Packets that use the kth wavelength in the second input are routed to the k+1th output, k=1,2,¡K7, and to the first output when k=8. In general, packets that use the kth wavelength in the ith input are routed to the ((k+i-2) mod 8) +1 output. Thus, in conjunction with wavelength converters, we can implement an 8 ¡¦ 8 crossbar switch with an 8 ¡Ñ 8 AWG.
Fig. 6 Functions of an 8 ¡Ñ 8 AWG.
