19-07-2012, 11:39 AM
Channel Scheduling Algorithms using Burst Segmentation and FDLs for Optical Burst-Switched Networks
Channel Scheduling Algorithms using Burst Segmentation and FDLs for Optical.pdf (Size: 124.43 KB / Downloads: 22)
Abstract
Optical burst switching is a promising solution for
terabit transmission of IP data bursts overWDMnetworks. One of
the key components in the design of optical burst-switched nodes
is the development of channel scheduling algorithms that can
efficiently handle data burst contentions. Currently, traditional
scheduling techniques use wavelength conversion and buffering to
resolve burst contention. In this paper, we reduce packet losses by
proposing a number of data channel scheduling algorithms that
use burst segmentation and fiber delay lines (FDLs). The proposed
scheduling algorithms are classified based on the placement of the
FDL buffers in the optical burst-switched node and are referred
to as delay-first or segment-first schemes. Simulation results
show that these algorithms can effectively reduce the packet loss
probability compared to existing scheduling techniques.
I. INTRODUCTION
There has been a steady growth of Internet traffic during the
past several years. Future growth is expected with the emergence
of high bandwidth applications, such as Tele-Immersion,
HDTV, and broadband video to name a few. There has been
growing interest in the realization of an optical Internet (IP
over WDM) to support these future applications. The advantage
of an optical Internet is that it eliminates the complexity
and overhead associated with the ATM and SONET layers.
Optical burst switching (OBS) is one approach that can be
used to efficiently transmit bursts of IP data over WDM networks.
In an OBS network, a WDM link consists of multiple
data channels to transmit the payload (data bursts) and one or
more dedicated control channels to transmit the corresponding
burst header packets (BHP). The BHP is transmitted ahead of
the burst in order to configure the switches along the burst’s
route. The burst follows the header without waiting for an acknowledgment
for the connection establishment. The header
and the data burst are separated at the source, as well as subsequent
intermediate nodes, by an offset time. The offset time
allows for the header to be processed at each node before the
arrival of the burst; thus, no fiber delay lines are necessary at
the intermediate nodes to delay the burst while the header is
being processed. The control message may also specify the
duration of the burst in order to let a node know when it may
reconfigure its switch for the next burst, a technique known as
Just-Enough-Time (JET) [1]. In this paper, we will consider an
optical burst switched network which uses the JET technique.
One of the key issues in OBS is the scheduling of bursts
on output data channels. Currently, contention resolution
techniques used in scheduling are wavelength conversion and
buffering. In wavelength conversion, if multiple bursts on
the same wavelength compete for the same output port at the
same time, then the bursts are shifted to different independent
wavelengths. In optical buffering, FDLs are used to provide
limited delay to the data bursts, proportional to the length of
fiber delay line, in order to resolve the contention. Current
data channel scheduling algorithms that use wavelength conversion
and FDLs include latest available unscheduled channel
(LAUC), and latest available unscheduled channel with void
filling (LAUC-VF) [3]. However, these techniques drop the
burst completely if all of the data channels are occupied at the
arrival time of the burst. Instead of dropping the burst in its
entirety, it is possible to drop only the overlapping parts of a
burst. This technique is referred to as burst segmentation [2].
In this paper, we propose new scheduling techniques incorporating
segmentation and FDLs. We show that the performance
of the proposed algorithms in terms of packet loss probability
is better than existing scheduling techniques.
This paper is organized as follows. Section II discusses
the architecture of the FDLs. Section III discusses the new
scheduling algorithms with burst segmentation and FDLs. Section
IV provides numerical results. Section V concludes the
paper and proposes directions for future research.
II. ARCHITECTURE OF OPTICAL ROUTERS
We consider two FDL architectures in the OBS node, for
realizing the proposed scheduling algorithms to be described in
the next section. The architecture in Fig. 1(a) shows an inputbuffered
FDL OBS node with FDLs dedicated to each input
port, while Fig. 1(b) shows an output buffered FDL OBS node
with FDLs dedicated to each output port. The basic architecture
of the FDL buffered OBS node is introduced in [3].
In the input-buffer OBS node architecture shown in Fig. 1(a),
each input port is equipped with an FDL buffer containing
N delay lines. The n data channels are de-multiplexed from
each input fiber link and are passed through wavelength converters
whose function is to convert the input wavelengths to
wavelengths that are used within the FDL buffers. The use
of different wavelengths in the FDL buffers and on the output
links helps to resolve contentions among multiple incoming
data bursts competing for the same FDL and the same output
link. In the design of FDL buffers, we can have fixed delay
FDL buffers, variable delay FDL buffers, or a mixture of both.
In this paper, we follow the architecture of variable delay FDL
buffers.
0-7803-7802-4/03/$17.00 © 2003 IEEE
Broadcast and Select Switch
Optical
Space Switch
Wavelength
Convertors
BSS
BSS
BSS
Input Fiber N
Input Fiber 1
Input Fiber 2
Data
Channels
Output Fiber 1
Output Fiber 2
Output Fiber N
FDLBuffer
Switch Control Module - Control Signals
Optical
Space Switch
BSS
BSS
BSS
Input Fiber N
Input Fiber 1
Input Fiber 2
Data
Channels
Output Fiber 1
Output Fiber 2
Output Fiber N
Wavelength
Convertors
Buffer
FDL
Switch Control Module − Control Signals
Fig. 1. (a) Input-Buffer and (b) Output-Buffer FDL Architecture.
In the output-buffer OBS node architecture, shown in
Fig. 1(b), the FDL buffers are placed after the switch fabric.
The input wavelength converters are used to convert the input
wavelengths to the wavelengths that are used within the switching
fabric. The functions of the output wavelength converters
are the same as described in the input-buffer FDL architecture.
III. CHANNEL SCHEDULING ALGORITHMS
There has been substantial work on scheduling using FDLs
in OBS [3]. In this section, we propose a number of scheduling
algorithms incorporating both segmentation and FDLs. Based
on the two FDL architectures presented in the previous section,
we have two classes of scheduling schemes. Algorithms
based on the input-buffer FDL node architecture are called
delay-first scheduling algorithms, while scheduling algorithms
based on the output-buffer FDL node architecture are called
segment-first scheduling algorithms. In both schemes, we assume
that full wavelength conversion, FDLs, and segmentation
techniques are used to resolve burst contention for an output
data channel. However, the order of applying the above
techniques depends on the FDL architecture. In the delayfirst
scheme, we resolve contention by wavelength conversion,
FDLs, and segmentation, in that order. In the segment-first
scheme, we resolve contention by wavelength conversion, segmentation,
and FDLs, in that order. Before going on to the
detailed description of the schemes, it is necessary to discuss
the motivation for developing two different schemes. In delayfirst
schemes, FDLs are primarily used to delay the entire burst,
while in segment-first schemes, FDLs are primarily used to delay
the segmented bursts. Delaying the entire burst and then
segmenting the burst keeps the packets in order; however, when
delaying segmented bursts, packet order is not always maintained.
In general, segment-first schemes will incur lower delays
than delay-first schemes.
We will now describe the new scheduling algorithms which
use segmentation, wavelength conversion, and FDLs. In this
paper, the bursts which have already been assigned a data channel
are referred as the scheduled bursts, and the burst which
arrives to the node waiting to be scheduled is referred to as the
unscheduled burst.
When a BHP arrives at a node, a data channel scheduling
algorithm is employed to assign a data channel on the outgoing
link for the unscheduled burst. The channel scheduler
obtains the burst arrival time and duration of the unscheduled
burst from the BHP. The algorithm may need to maintain the
latest available unscheduled time (LAUT), gaps, and voids, on
every outgoing data channel. The LAUT of a data channel is
the earliest time at which the data channel is available for an unscheduled
data burst to be scheduled. A gap is the time between
the arrival of the unscheduled burst and ending time of the previously
scheduled burst. A void is the unscheduled duration
between two scheduled bursts on a data channel. For void filling
algorithms, the starting and the ending time for each burst
on every data channel must be maintained.
The following information is needed by the scheduling algorithm: