7/30/2019 Giai Quyet Tranh Chap Trong Obs
1/85
NEW CONTENTION RESOLUTION
TECHNIQUES
FOR
OPTICAL BURST SWITCHING
A Thesis
Submitted to the Graduate Faculty of the
Louisiana State University and
Agricultural and Mechanical College
in partial fulfillment of the
requirements for the degree of
Master of Science in Electrical Engineering
in
The Department of Electrical Engineering
ByKishore Koduru
Bachelor of Engineering (Computer Engineering), BIET, 2002
May 2005
7/30/2019 Giai Quyet Tranh Chap Trong Obs
2/85
Dedicated to my dear parents
ii
7/30/2019 Giai Quyet Tranh Chap Trong Obs
3/85
Acknowledgements
I would like to thank my advisor Dr. Ahmed El. Amawy for theideas that led to
this work, for his timely comments, guidance, support andpatience throughout the course of
this work. I thank Dr. Jerry Trahan and Dr. Hsiao-Chun Wu forbeing on my defense
committee. I thank all the members of the Optical Networksresearch group for assisting me
with their ideas during Friday-meetings. I thank Mr. Moc Elgoogfor his extended support
during my entire stay at LSU. Last but not the least, I thankall my friends who have remotely
helped in the successful completion of this work.
iii
7/30/2019 Giai Quyet Tranh Chap Trong Obs
4/85
Table of Contents
ACKNOWLEDGEMENTS....iii
LIST OF FIGURES....vi
ABSTRACT.viii
CHAPTER 1: INTRODUCTION........1
1.1Optical Transmission System...31.2OpticalFiber.41.3Wavelength Division Multiplexing (WDM)61.4Components ofWDM Optical Networks.7
1.4.1 Wavelength Multiplexer...7
1.4.2 Wavelength Add/Drop Multiplexer..81.4.3 OpticalCrossconnects (OXC)..9
1.4.4 Optical Amplifier111.5 WDM Network Architectures.12
1.5.1 Broadcast-and-Select Networks..12
1.5.2 Wavelength Routed Networks14
1.6 Routing and Wavelength Assignment151.6.1 RouteSelection...16
1.6.2 Wavelength Selection.17
1.7 Problem Formulation and Layout of Thesis...18
CHAPTER 2: OPTICAL BURST SWITCHING (OBS)..20
2.1 OBS Network Architecture.222.2 Reservation Schemes inOBS.24
2.2.1 Tell-and-Go (TAG).25
2.2.2 Just-In-Time (JIT)...262.2.3 Just-Enough-Time...27
2.3 Contention Resolution29
2.3.1 Optical Buffering30
2.3.2 Wavelength Conversion..322.3.3 Deflection Routing..34
CHAPTER 3: NEW DEFLECTION-BASED CONTENTION RESOLUTIONSCHEMES.......373.1 Backtrack on Deflection Failure.38
3.1.1 Routing Protocol.38
3.1.2 Backtrack on Deflection Failure with Increase in InitialOffset.403.1.2.1 Routing Procedure..40
3.1.3 Backtrack on Deflection Failure with Open LoopReservation..42
3.1.3.1 Routing Procedure..43
iv
7/30/2019 Giai Quyet Tranh Chap Trong Obs
5/85
3.1.4 Example for Backtrack on Deflection Failure44
3.2 Bidirectional Reservation on Burst Drop for RetransmissionBursts.47
3.2.1 Offset Calculation...49
CHAPTER 4: SIMULATION & RESULTS.....52
4.1 Simulator Setup...524.2 Assumptions53
4.3 Simulation Parameters55
4.4 Results.55
CHAPTER 5: CONCLUSION AND FUTURE SCOPE...72
BIBLIOGRAPHY..74
VITA..76
v
7/30/2019 Giai Quyet Tranh Chap Trong Obs
6/85
List of Figures
1.1Optical transmission system..31.2Fiber opticcable.....51.3Different modes of propagation.51.4Wavelengthdivision multiplexing.61.5Diffraction grating for separation ofwavelengths.81.6Wavelength add/drop multiplexer..91.7Wavelengthcross-connect...101.8Erbium-dopedamplifier...121.9Broadcast-and-Select network.131.10 Wavelengthrouted network...14
2.1 Comparison of optical switching schemes...21
2.2 OBS network architecture23
2.3 Use of delayed reservation...24
2.4 JIT scheme...27
2.5 JET scheme..28
2.6 Contention resolution using FDL.32
2.7 Wavelength conversion34
2.8 Deflection routing35
3.1 Information fields in a control burst39
3.2 Backtrack on deflection failure45
3.3 Decision table for time period (0-4).45
vi
7/30/2019 Giai Quyet Tranh Chap Trong Obs
7/85
3.4 Decision table for case 1..46
3.5 Decision table for case 2..47
3.6 Control burst drop due to reservation failure...49
3.7 Bidirectional reservation on control burst drop...50
4.1 NSFNET with 14 nodes...54
4.2 USA long haul network with 28 nodes54
4.3 Packet loss probability at low loads.56
4.4 Packet loss probability at high loads57
4.5 Packet loss probability versus low load (BDF-BR) 58
4.6 Packet loss probability versus high load (BDF-BR) ...59
4.7 Blocking probability versus fixed offset..60
4.8 Average number of hops traveled versus intended number ofhops62
4.9 Average number of hops traveled versus load.63
4.10 Poisson traffic versus bursty traffic (low loads)64
4.11 Poisson traffic versus bursty traffic (high loads) ..65
4.12 Link utilization versus load....66
4.13 Packet loss probability with different number ofwavelengths per fiber...67
4.14 Throughput versus offered load.68
4.15 Throughput versus offered load (singleretransmission)...69
4.16 Average transmission count versus offered load...70
4.17 Packet loss probability versus load (USA long haulnetwork)..71
vii
7/30/2019 Giai Quyet Tranh Chap Trong Obs
8/85
Abstract
Optical burst switching (OBS) is a technology positioned betweenwavelength
routing and optical packet switching that does not requireoptical buffering or packet-level
parsing, and it is more efficient than circuit switching whenthe sustained traffic volume does
not consume a full wavelength. However, several critical issuesstill need to be solved such as
contention resolution without optical buffering which is a keydeterminant of packet-loss with
a significant impact on network performance.
Deflection routing is an approach for resolving contention byrouting a contending
packet to an output port other than the intended output port. InOBS networks, when contention
between two bursts cannot be resolved through deflectionrouting, one of the bursts will be
dropped. However, this scheme doesnt take advantage of all theavailable resources in
resolving contentions. Due to this, the performance of existingdeflection routing scheme is not
satisfactory. In this thesis, we propose and evaluate three newstrategies which aim at resolving
contention.
We propose a new approach called Backtrack on DeflectionFailure, which
provides a second chance to blocked bursts when deflectionfailure occurs. The bursts in this
scheme, when blocked, will get an opportunity to backtrack tothe previous node and may get
routed through any deflection route available at the previousnode. Two variants are proposed
for handling the backtracking delay involved in this schemenamely: (a) Increase in Initial
Offset and (b) Open-Loop Reservation. Furthermore, we propose athird scheme called
Bidirectional Reservation on Burst Drop in which bandwidthreservation is made in both the
forward and the backward directions simultaneously. This schemecomes into effect only when
viii
7/30/2019 Giai Quyet Tranh Chap Trong Obs
9/85
control bursts get dropped due to bandwidth unavailability. Theretransmitted control bursts
will have larger offset value and because of this, they willhave lower blocking probability than
the original bursts.
The performance of our schemes and of those proposed in theliterature is studied
through simulation. The parameters considered in evaluatingthese schemes are blocking
probability, average throughput, and overall link utilization.The results obtained show that our
schemes perform significantly better than their standardcounterparts.
ix
7/30/2019 Giai Quyet Tranh Chap Trong Obs
10/85
Chapter 1
Introduction
In recent years, explosive demand for network bandwidth hasbecome a
major challenge for network engineers due to increasing globalpopularity of the
Internet and the increased applications it affords. A continuousdemand for networks of
high capacities at low cost exists. Optical data communicationhas been acknowledged
as the best solution for meeting the present bandwidthrequirements of the users and for
supporting future network services. This is because; in theoryeach optical fiber has the
ability to support bandwidth demand of up to 50 THz [1]. Apartfrom this, optical fibers
are inexpensive and provide extremely low bit-error rates(typically 10-12
) [2]. The
optical fiber is less bulky than other cables. Optical signalstravel clearly for longer
distances and are immune to electrical interferences.Furthermore, fiber cables are much
more difficult to tap than copper wires, so in addition there isa security advantage [2].
All these factors make optical data networks the networks of thefuture.
Optical Networks may be classified as:
1. First Generation Optical Networks:These optical networksinvolved replacing
copper cables by optical fibers as the medium of transmission.The switching and
processing of bits were, however, handled in the electronicdomain as before.
Optical fibers were preferred for bit rates greater than 10Mbps. Examples of first
generation optical networks are SONET/SDH networks that form thecore telecom
networks in North America, Europe and Asia [3, 5]. Otherexamples include the
FDDI-based enterprise networks. From a network layering point ofview, the
impact of first generation optical networks was felt primarilyin the physical layer.
1
7/30/2019 Giai Quyet Tranh Chap Trong Obs
11/85
From hereon, there were primarily two fundamental ways ofincreasing the speed
in networks; either increase the electronic processing speeds byimproved time
division multiplexing (TDM) techniques or increase the capacityby using multiple
carrier wavelengths in the fiber at the same time [7].
2. Second Generation Optical Networks:These networks were madecapable of
using multiple carrier wavelengths that were multiplexed onto asingle fiber thus
offering increased bandwidth. The technique is called WavelengthDivision
Multiplexing (WDM) [3, 4, 10]. The primary improvement of secondgeneration
optical networks over their first generation counterparts from atechnological point
of view was in incorporating the switching and routingfunctionality in the optical
domain and allowing for the transparency of data format,protocol and bit rates. It
thus allowed for smaller electronic load on a node by ensuringthe need to
terminate the traffic intended only for that node while allowingthe other traffic to
cut right through the node in the optical domain. In firstgeneration networks, a
node would have to terminate all the optical signals(irrespective of whether they
are intended for itself or not), convert them to electronicsignals, process them and
then regenerate the traffic not intended for itself into opticalsignals and send them
on the appropriate outgoing links. The second generation opticalswitches are
called Optical Cross-connects (OXCs). These switches may beconfigured to
switch optical signals from any incoming port to any outgoingport.
The next-generation optical networks will involve optical packetswitching and All-
Optical Networks (AON). In an AON, all network-to-networkinterfaces are based on
optical transmission, and all user-to-network interfaces useoptical transmission on the
2
7/30/2019 Giai Quyet Tranh Chap Trong Obs
12/85
network side of the interface. All buffering, switching androuting within AON network
nodes are performed optically. In these networks, it isenvisioned that the DWDM based
dynamic optical network elements such as optical cross-connectsand optical add/drop
multiplexers will have full control of all wavelengths [5]. Inaddition, they are expected
to have full knowledge of the traffic carrying capacity and thestatus of each wavelength.
With such intelligence, these networks are envisioned as beingself-connecting and self-
regulating.
1.1Optical Transmission System
Todays low-loss glass fiber optic cable offers almost uniqueadvantages
over all previously developed transmission media. The basicpoint-to-point fiber optic
transmission system consists of three basic elements: theoptical transmitter, the fiber
optic cable and the optical receiver as shown in Figure 1.1.
Optical FiberOpticalDetector
Receiver
Modulator
Regenerator
OpticalSource
Transmitter
ElectricalSignal
Figure 1.1 Optical transmission system
3
7/30/2019 Giai Quyet Tranh Chap Trong Obs
13/85
The transmitter converts an electrical analog or digital signalinto a
corresponding optical signal. The source of the optical signalcan be either a light
emitting diode, or a solid state laser diode. The light sourcecan be modulated according
to an electrical input signal to produce a beam of light whichis transmitted into the
transmission medium [2]. The optical fiber is the transmissionmedium. When the
optical information reaches the receiver, the on/off lightsignals are converted back to
electrical signals by an optical detector. In this system, theinformation undergoes
electronic-optical-electronic conversion. The transmissioncharacteristics of an optical
fiber are usually given in terms of attenuation for a givenwavelength over a given
distance (length of the fiber). As the distance traveled by thesignal increases, the
attenuation also increases. When the signal becomes weak, theinformation carried
cannot be retrieved from the signal. In order to preventexcessive attenuation,
regenerators are used to boost the signal power and to restorethe shape of the signal.
1.2 Optical Fiber
The main purpose of an optical fiber is to guide light waveswith minimum
attenuation (loss of signal). Optical fibers are composed offine threads of glass in
layers, called the core and cladding that can transmit light atabout two-thirds the speed
of light in vacuum. Though admittedly an oversimplification, thetransmission of light
in optical fiber is commonly explained using the principle oftotal internal reflection
[6]. With this phenomenon, 100 percent of light that strikes asurface is reflected. Light
is either reflected or refracted depending on the angle ofincidence (the angle at which
light strikes the interface between an optically denser and anoptically thinner material).
4
7/30/2019 Giai Quyet Tranh Chap Trong Obs
14/85
The core has a higher refractive index than the cladding,allowing the beam that strikes
that surface at less than the critical angle to bereflected.
Figure 1.2 Fiber optic cable
Figure 1.3 Different modes of propagation
There are two modes of fiber propagation known as multi-mode andsingle-
mode. The single-mode fiber optic cable provides betterperformance but at a higher cost.
The multimode fiber has a graded refractive index profile, dueto which many rays of
light can bounce at different angles [7]. Each ray is said tohave a different mode, hence,
the name multimode fiber. If a stepwise refractive index isused, the fiber will act like a
waveguide and the light will travel in a straight line along thecenter axis of the fiber.
5
7/30/2019 Giai Quyet Tranh Chap Trong Obs
15/85
Such fibers are known as single mode fibers. A single mode fiberhas lower attenuation
and less time dispersion. However it is more expensive than themultimode fiber. These
fibers are used mainly in Wide Area Networks [7].
1.3 Wavelength Division Multiplexing
In order to fully exploit the offered bandwidth of a fiber, thebandwidth is
divided into a number of channels on different wavelengths. Thismethod of sending
many light beams of different wavelengths simultaneously on thesame fiber is referred
to as Wavelength division multiplexing (WDM) [3]. This methodexploits the huge
opto-electronic bandwidth mismatch by requiring that eachend-users equipment
operate only at electronic rate. But multiple WDM channels fromdifferent end-users
may be multiplexed on the same fiber.
Fiber
Lasers
Figure 1.4 Wave division multiplexing
In a simple WDM system shown in Figure 1.4, the transmittingside has a
series of fixed-wavelength or tunable light sources, each ofwhich emits signals at a
6
7/30/2019 Giai Quyet Tranh Chap Trong Obs
16/85
unique wavelength. A multiplexer is used to combine theseoptical signals into a
continuous spectrum of signals and to couple them onto a singlefiber. Within the
optical link, there will be various types of optical amplifiers.At the receiving end, a de-
multiplexer is used to separate the optical signals intoappropriate detection channels
for signal processing. The WDM systems are classified into densewavelength division
multiplexing (DWDM) systems and coarse wavelength divisionmultiplexing (CWDM)
systems. In DWDM, the bandwidth of the fiber is divided intomore than 8
wavelengths. CWDM refers to the systems where the fiberbandwidth is divided into
less than 8 wavelengths.
1.4 Components of a WDM Optical Network
Some of the major modules contained in a WDM optical netowrkinclude
wavelength multiplexers, optical crossconnects, opticalamplifiers, and wavelength
add/drop multiplexers. The following subsections discuss thesecomponents and their
functions in a WDM network.
1.4.1 Wavelength Multiplexers
The function of this device is to combine independent signalstreams
operating at different wavelengths onto the same fiber and toseparate them at the
receiver. In principle, any demultiplexer also can be used as amultiplexer [8]. For
simplicity, the word multiplexer is used as a general term thatrefers to both the
combining and separating functions. The technologies used inthese devices are include
thin-film filters, arrayed waveguide gratings, Bragg fibergratings, diffraction gratings,
and interleavers. Among these, diffraction grating is the toolof choice for spatially
separating different wavelenghts contained in a beam of light[6]. The grating technique
7
7/30/2019 Giai Quyet Tranh Chap Trong Obs
17/85
is shown in Figure 1.5. The device consists of a set ofdiffracting elemets, such as
narrow parallel slits or grooves, separated by a distancecomparable to the wavelength
of light. These diffracting elements can be either reflective ortransmitting. With this
method, separating and combining wavelengths is a parallelprocess.
Figure 1.5 Diffraction grating technique for separatingwavelengths
1.4.2 Wavelength Add/Drop Multiplexer
See AlsoTitin strain contributes to the Frank Starling law of the heart …...2016/02/04 · Titin strain contributes to the Frank–Starling law of the heart by structural rearrangements - [PDF Document]Alpha Lubricator System Operation (ALCU 2004-04-13) Manual M - [PDF Document]Charles Stanley- Be still and know I am GOD! - [PDF Document]Hierarchical Reinforcement Learning with …papers.nips.cc/paper/8421-hierarchical-reinforcement...these challenging tasks [6]. In addition, Hierarchical Reinforcement Learning (HRL) - [PDF Document]A wavelength add/drop multiplexer (WADM) allows the insertionor
extraction of a wavelength from a fiber at a point betweenterminals. A WADM can
operate either statically or dynamically. WADM consists of ade-multiplexer, followed
by a set of 2 x 2 switches, one for each wavelength. Theswitches are followed by a
multiplexer. The switches are managed electrically. They controlwhich of the incoming
wavelengths flow through the WADM and which are dropped locally.If some incoming
wavelengths are dropped locally in WADM a new data stream can beadded on to the
same wavelength at this WADM location. More than one wavelengthcan be dropped and
added if the WADM interface has the necessary hardware andprocessing capabilities [4].
8
7/30/2019 Giai Quyet Tranh Chap Trong Obs
18/85
Figure 1.6 Wavelength add/drop multiplexer
1.4.3 Optical Crossconnects (OXC)
Optical crossconnects are used to route wavelengths betweeninput ports and
out ports. The main function of the OXC is to dynamicallyreconfigure the network at
the wavelength level for restoration or to accommodate changesin bandwidth demand.
OXC systems are expected to be the cornerstone of the photoniclayer providing
carriers more dynamic and flexible options in building networktopologies with
enhanced survivability. The architecture of an OXC is shown inFigure 1.7. The typical
OXC capabilities are
Fiber switching: the ability to route all of the wavelengths onan incoming fiberto a different outgoing fiber.
Wavelength switching: the ability to switch specific wavelengthsfrom anincoming fiber to multiple outgoing fibers.
9
7/30/2019 Giai Quyet Tranh Chap Trong Obs
19/85
Wavelength conversionthe ability to take incoming wavelengthsandconvert them (on the fly) to other optical frequencies on theoutgoing ports; this
is necessary to achieve strictly non-blocking architectures whenusing
wavelength switching.
Figure 1.7 Wavelength cross-connect
OXCs can be divided into the following classes [3]:
The fiber switch cross-connect (FXC) The wavelength selectivecross-connect (WSXC) The wavelength interchanging cross-connect(WIXC)
A fiber switch cross-connect switches all of the wavelengthchannels on one input fiber
to an output fiber, in effect acting as an automated fiber patchpanel. FXC are less
complex, and thus expected to be less costly, than a wavelengthselective or wavelength
10
7/30/2019 Giai Quyet Tranh Chap Trong Obs
20/85
interchanging cross-connect. A wavelength selectivecross-connect can switch a subset
of the wavelength channels from an input fiber to an outputfiber. Functionally, they
therefore require de-multiplexing (in the frequency spectraldomain) of an incoming
wavelength multiplex into its individual constitutingwavelengths. This cross-connect
type offers much more flexibility than an FXC, allowing theprovisioning of
wavelength services, which in turn can support videodistribution, distance learning, or
a host of other applications. A wavelength interchangingcross-connect is a WSXC with
the added capability to translate or change the frequency (orwavelength) of a channel
from one frequency to another. This feature reduces theprobability of not being able to
route a wavelength from an input fiber to an output fiberbecause of wavelength
contention. WIXC offers the most flexibility for restoration andprovisioning of
services. The WIXC may not be very cost effective since somecircuits may not always
need wavelength conversions. One effective method is to sharewavelength converters.
1.4.4 Optical Amplifier
Optical amplification is required to compensate for variouslosses such as
fiber attenuation, coupling and splitting loss in the starcouplers, as well as coupling
losses in the wavelength routers. The advent of a fiber opticrepeater device called the
Erbium doped fiber amplifier has enabled WDM to be acost-effective technology. An
Erbium doped fiber amplifier (EDFA), is an optical or IRrepeater that amplifies a
modulated laser beam directly, without opto-electronic andelectro-optical conversion
[5]. Some of the important properties which have led to usingEDFAs in large numbers
in optical transmission systems are high power conversionefficiency, high gain, low
noise, and low polarization dependence and temperaturesensitivity [3].
11
7/30/2019 Giai Quyet Tranh Chap Trong Obs
21/85
The structure of a typical EDFA is shown in Figure 1.8. Thedevice uses a
short length of optical fiber doped with the rare-earth elementErbium. When the signal-
carrying laser beams pass through this fiber, external energy isapplied, usually at IR
wavelengths. This so-called pumping excites the atoms in theErbium-doped section of
the optical fiber, increasing the intensity of the laser beamspassing through.
Figure 1.8 Erbium doped fiber amplifier structure
1.5 WDM Network Architectures
The most common classes of WDM network architectures are:Broadcast-
and-select (local-area) networks and Wavelength routed(wide-area) networks. The
following sections deal with these network architectures.
1.5.1 Broadcast-and-Select Networks
In a broadcast-and-select network, a passive coupler isconnected to all
the nodes in the network as shown in Figure 1.9. Each node inthe network has a set of
tunable optical transmitters and tunable optical receivers. Anode sends its information
to the star coupler on one of the available wavelengths usingthe tunable laser which
produces optical information stream. The information frommultiple sources is optically
12
7/30/2019 Giai Quyet Tranh Chap Trong Obs
22/85
combined by the star and the signal power of each stream isequally split and broadcast to
all of the nodes. An optical filter is used by the destinationnodes receiver to extract the
required wavelength stream from the received broadcast. When onenode sends
information, it is received by all the nodes in the network andonly those nodes which
need that information will tune their receivers to the desiredwavelength. Thus, the
network provides multicast capability. In this model, when anode failure occurs, the rest
of the network can still function without any problems. Hence,the passive-star model
enjoys a fault-tolerance advantage over some other distributedswitching networks [4, 7].
PassiveStar
Coupler 3
1
2
W 3 W 0
W 0
W 1W 2
W 3
W 1W 2
Figure 1.9 Broadcast-and-select network
However, broadcast and select networks have certain limitations.They
require a large number of wavelengths, typically at least asmany as the number of nodes
in the network. Thus the networks are not scalable beyond thenumber of available
wavelengths [5]. Since the transmitted power is split among thevarious nodes of the
13
7/30/2019 Giai Quyet Tranh Chap Trong Obs
23/85
network, the signal will not be able to span long distances.Because of these limitations,
this model is suitable only for local area networks.
1.5.2 Wavelength Routed Networks
Wavelength routed networks have the potential to avoid theproblems
associated with the broadcast-and-select networks. They avoidthe power splitting loss
due to broadcast and they can be scalable to wide area networks.A wavelength routed
network consists of wavelength cross connects (active switches)interconnected by point-
to-point fiber links to form an arbitrary physical topology.Each node in the network is
equipped with a set of transmitters and receivers, both of whichmay be tunable. Each end
user is connected to the active switch by a fiber link. Thecombination of end user and its
corresponding active switch is referred to as a node.
4
1
3 2
W 0
W 1
P 3
P 0P 2
P 1
Figure 1.10 Wavelength routed network
In wavelength routed networks, the communication mechanism iscalled a
Lighpath. A lightpath is an all-optical wavelength continuouspath which is established
between two nodes in the network. It may span more than onefiber link and is created by
allocating the same wavelength throughout the path [6]. Amessage is sent from one node
14
7/30/2019 Giai Quyet Tranh Chap Trong Obs
24/85
to another node using a lightpath without requiring anyoptical-electronic-optical
conversion or buffering at the intermediate nodes. Therequirement that the same
wavelength be used on all the links of the path between twonodes is called the
wavelength continuity constraint [2] [6]. No two lightpaths canhave the same
wavelength on any common fiber. This is known as the distinctwavelength assignment
constraint [6]. The wavelength continuity may not be necessaryif the network is
equipped with wavelength converters which have the ability toconvert the information
stream from wavelength to another wavelength without electronicconversion.
A typical wavelength routed network is shown in Figure 1.10. Thenetwork
has five nodes and two wavelengths. Lightpaths need to beestablished between node
pairs , , and . The figure shows the lightpath establishment
for those node pairs with out any problem. The lightpaths p0 andp2 use wavelength w0
and lightpaths p1 and p3 use wavelength w1. Suppose we need toestablish another
lightpath between node pair . The route for this is 401.Wavelength w0 is
available on the link 40 and wavelength w1 is free on link 01.Though bandwidth is
available along the path, a lightpath cannot be establishedbecause of wavelength
continuity constraint.
1.6 Routing and Wavelength Assignment (RWA)
Routing and wavelength assignment is the fundamental controlproblem in
WDM wavelength routed networks. In WDM wavelength routed opticalnetworks,
lightpaths need to be established before any communication takesplace between the
nodes. In order to establish a lightpath between two nodes, twodecisions have to be
made. The first is the selection of the path from the sourcenode to the destination node
15
7/30/2019 Giai Quyet Tranh Chap Trong Obs
25/85
and the second is the selection of wavelength to be assigned tothe path. Many problems
in wavelength routed networks have RWA as a sub problem.
Depending on the traffic in the network, the RWA problem isclassified into
static and dynamic. In case of static traffic demand, theconnection requests are known
in advance. The traffic demand may be provided in terms ofsource-destination pairs.
The objective is to assign routes and wavelengths so as tomaximize the number of
demands satisfied. In dynamic traffic demand, the connectionrequests arrive and depart
randomly. The established lightpaths will remain only for afinite time. Since the traffic
is dynamic, the network has no knowledge of future connectionrequests. Because of
this, the dynamic RWA algorithms perform poorly when compared tothe static RWA
algorithms [10]. A dynamic RWA algorithm processes theconnection requests strictly
in the order of connection arrival time, whereas a static RWAalgorithm processes the
connection requests in the order decided by some heuristic. TheRWA problem can be
divided into route selection and wavelength selection.
1.6.1 Route Selection
Route selection algorithms can be classified into three types:fixed routing
(FR), alternate routing (AR), and exhaust routing (ER).
Fixed routing: For each node pair in the network, a fixed routeis assigned. These
routes are calculated offline and they do not change with thechanging network
conditions. The performance degrades as the offered loadincreases.
Alternate routing: For each node pair in the network, a set ofcandidate routes are
computed offline. When a connection request arrives, the routeis selected from among
only those in the set of candidate routes assigned for that nodepair.
16
7/30/2019 Giai Quyet Tranh Chap Trong Obs
26/85
Exhaust routing: In exhaust routing, when a connection requestarrives for a node pair,
all the possible routes between the node pair are considered andone among them is
selected. A conventional shortest path algorithm is typicallyused to find the best
possible route.
1.6.2 Wavelength Selection
The wavelength selection algorithms can be classified intomost-used, least-
used, fixed-order, random-order, and round-robin.
Most-used: This algorithm gives preference to the wavelengthwhich is used on the
largest number of links in the network. The wavelengths aresearched in descending
order of their use. The main idea behind this algorithm is topack the lightpaths tightly
so that future connection requests will have many availablewavelength continuous
routes. In order to know the wavelength usage, the global stateinformation of the
network is to be known.
Least-used: In this case, the wavelength which is used on theleast number of links in
the network will be selected. This scheme attempts to distributethe load on the
wavelengths uniformly across the entire network.
Fixed-order: All the wavelengths in the network are indexed.This algorithm searches
for wavelength in a fixed order and the first free wavelengthwill be selected.
Random-order: All the wavelengths are indexed and the selectionis done randomly.
Each wavelength has equal probability of being selected.
Round-robin: This method tries to distribute the load on thewavelengths equally by
assigning the wavelengths in a round-robin fashion from the poolof available
wavelengths.
17
7/30/2019 Giai Quyet Tranh Chap Trong Obs
27/85
Another important issue in WDM wavelength routed networks isthe
connection blocking probability. It is a measure of how likely aconnection request will
get blocked because of unavailable network resources. Thewavelength continuity
constraint increases the blocking probability of connectionswith larger hop counts
when compared to connections with smaller hop counts [10] [3].Fairness and
admission control algorithms are used to regulate networktraffic and to provide
fairness among connection requests.
1.7 Problem Formulation and Layout of Thesis
Wavelength division multiplexing technology on optical fiber
communication has produced tremendous amount of raw bandwidth.Nowadays, bursty
internet traffic is consuming most of the available bandwidth asopposed to non-bursty
voice traffic [15]. This bursty internet traffic, which isincreasing day by day, has to be
handled with proper technology. An all-optical transportprotocol has to be developed
to utilize this bandwidth efficiently and to avoid opticalbuffering while handling bursty
traffic.
Circuit switching and packet switching have been used for manyyears.
However, these technologies are mainly used with voice and datatraffic, respectively
[12] [13]. Though optical packet switching can handle internettraffic more efficiently,
the optical hardware technology has not been developed wellenough to afford this.
Optical burst switching (OBS) is a scheme which has been viewedas a viable option
for handling the bursty traffic until optical packet switchingtechnology becomes a
reality [9][12][13]. OBS has been designed to achieve a balancebetween the coarse-
grained circuit switching and fine-grained packet switching. Inthis work, we
18
7/30/2019 Giai Quyet Tranh Chap Trong Obs
28/85
investigate the various issues related to optical burstswitching technologies. Our main
interest is concentrated on contention resolution techniques inOBS networks which
play a great part in reducing packet loss and congestion in thenetwork. This thesis
presents and studies the performance of three new techniques forreducing packet loss
in OBS schemes. The results obtained through simulations showthat our schemes
exhibit low blocking probabilities when compared to othertechniques proposed in the
literature.
The remainder of the thesis is organized as follows: Chapter 2discusses the
details of optical burst switching including various reservationtechniques proposed in
the literature. It also covers the traditional contentionresolution techniques used in
OBS. Chapter 3 proposes our new packet loss reduction techniquesalong with their
signaling protocols and timing diagrams. Chapter 4 studies theperformance of our
schemes using simulations. It also compares our results withthose for previously
known schemes. Chapter 5 concludes the thesis and identifiesareas of future work.
19
7/30/2019 Giai Quyet Tranh Chap Trong Obs
29/85
Chapter 2
Optical Burst Switching
Optical burst switching (OBS) is a promising new technique whichattempts to
address the problem of efficiently allocating resources forbursty internet traffic. Circuit
switching and packet switching have been used for many years forvoice and data
communication, respectively. OBS can combine the best of thecoarse-grained circuit-
switching and the fine-grained packet-switching paradigms whileavoiding their shortcomings,
thereby efficiently supporting bursty traffic generated by upperlevel protocols or high-end
user applications directly [11, 13, 16]. OBS differs fromcircuit and packet-switching primarily
in whethercut-through orstore-and-forward is used and in howbandwidth is reserved (and
released).
In circuit switching, a dedicated path has to be establishedbetween two nodes
before any data transmission takes place [19]. The time takenfor establishing such path is
equal to the round trip delay. The reserved resources stay idlefor the entire path setup time and
account for poor resource utilization. The benefit of OpticalBurst Switching (OBS) over
conventional circuit switching is that there is no need todedicate a wavelength for each end to
end connection [13]. In addition to this, the path setup time ismuch less than the round-trip
delay. In packet switching, the data is broken into smallpackets and transmitted. The data is
transmitted using store and forward technique. The resources canbe shared by different
sources. End stations can send/receive data at their own speed[11, 12]. The individual packet
can be individually switched or a virtual circuit can be set up.Packet switching has large buffer
requirement and complex control and sync issues. For the opticaldomain, packet switching is
20
7/30/2019 Giai Quyet Tranh Chap Trong Obs
30/85
not yet feasible because of optical hardware limitations.Optical RAMs do not exist yet to meet
the high buffer requirements of packet switching. In addition,optical burst switching seems to
be more viable than optical packet switching since burst datadoes not need to be buffered or
processed at intermediate nodes. This allows the strengths ofoptical switching technologies to be
leveraged effectively and the problem of buffering in theoptical domain to be circumvented.
OBS combines the advantages of both circuit and packet switchingand ensures efficient
bandwidth and resource utilization [11, 15].
Figure 2.1 Comparison of optical switching schemes
Optical burst switching is based on the separation of thecontrol plane and the data
plane [14]. The basic switching entity in OBS is called a burstwhich is a (digitized) talk spurt
or a data message. In optical burst switching data packets areaggregated into much larger
bursts before transmission through the network. This allowsamortization of the switching
overhead across multiple packets. The data burst (DB) ispreceded in time by a control burst
(CB), which is sent on a separate control wavelength. Thecontrol burst requests resource
allocation at each switch. At each intermediate node, the CB isprocessed electronically and the
time taken for processing a CB is known as the processing time.After processing, the CB
reserves a wavelength on an outgoing link for the DB. Thisreservation will be for a time
21
7/30/2019 Giai Quyet Tranh Chap Trong Obs
31/85
period starting from the time the DB is expected to arrive tothe time the DB is transmitted
completely. The reservation time and duration can be calculatedusing the offset and the DB
length. If no reservation can be made, then the CB is dropped.If the reservation is successful,
the CB is forwarded to the next node along the path to thedestination. The offset is chosen in
such a way that the reservation is already made at each nodebefore the DB arrives at that node.
OBS uses one-way reservation schemes with immediatetransmission, in which the data burst
follows a corresponding control burst after waiting for a shortoffset time without waiting for
an acknowledgement [13]. The offset time gap between the CBtransmission and the DB
transmission is generally used for aggregating the data packetsinto a data burst [12, 16].
2.1 OBS Network Architecture
An OBS network consists of optical core nodes and electronicedge nodes connected
by WDM links. Packets are assembled into bursts at networkingress, which are then routed
through the OBS network and disassembled back into packets atnetwork egress to be forwarded to
their next hops [14]. Edge nodes provide burstassembly/disassembly functions. A core node is
mainly composed of an optical switching matrix and a switchcontrol unit.
An OBS node is built from optical and electronic componentsbesides optical receivers
and optical transmitters. The optical components includemultiplexers (Mux), demultiplexers
(Demux) and an optical switching network (OSN). The electroniccomponents include input
modules (IM), output module (OM), a control burst router (CBRT),and a scheduler [2]. An
optical burst switch control unit transfers a burst coming infrom an input port to its destination
output port. Depending on the switch architecture, it may or maynot be equipped with optical
buffering. The fiber links carry multiple wavelengths, and eachwavelength can be seen as a
22
7/30/2019 Giai Quyet Tranh Chap Trong Obs
32/85
channel. The control packet associated with a burst may also betransmitted in-band over the same
channel as data, or on a separate control channel. The burstsize may be fixed to carry one or more
IP packets.
Figure 2.2 OBS network architecture
When an edge node intends to transmit a data burst, it firstsends a control burst on the
control wavelength to the nearest core node. At the core node,the CB on the control wavelength is
input to the corresponding IM, which converts the CB intoelectronic form by the receiver. The
control fields are extracted from the CB. The CBRT uses thesecontrol fields to determine the next
outgoing fiber for the corresponding DB by consulting a routingtable maintained locally. The CB
is scheduled for transmission onto the selected outgoing link bythe scheduler and the CB is
buffered until the scheduled time. The scheduler maintains a CBqueue. The scheduler also
reserves wavelength on the determined links for the upcoming DB.The CB is then forwarded onto
23
7/30/2019 Giai Quyet Tranh Chap Trong Obs
33/85
the OM, which updates its control fields and transmits it to theselected outgoing fiber using the
optical transmitter. Just before the DB arrives, the switchingelement in the node is configured to
connect the input port to the corresponding output port for theentire duration of the burst
transmission. If the CB is unable to reserve the wavelength forits corresponding DB, then the CB
will be dropped as well as its DB.
2.2 Reservation Schemes in OBS
Optical Burst switching schemes differ based on how and when thenetwork
resources like bandwidth, are reserved and released. Opticalburst switching is an adaptation of
burst switching technique in asynchronous transfer mode (ATM)networks, known as ATM
block transfer (ABT) [17]. There are two versions of ABT: ABTwith delayed transmission and
ABT with immediate transmission.
C B
D B
Figure 2.3 Use of offset delayed reservation
In case of an immediate reservation scheme, an output wavelengthis reserved for a data burst
immediately after the arrival of the corresponding controlburst; if a wavelength cannot be
24
7/30/2019 Giai Quyet Tranh Chap Trong Obs
34/85
reserved at that time, then the setup message is rejected andthe corresponding burst is dropped
[16]. In a delayed reservation scheme, the CB and the DB areseparated in time by an offset
value in order to accommodate the processing of the CB. Anoutput wavelength is reserved for
a burst just before the arrival of the first bit of the burst.If, upon arrival of the setup message,
it is determined that no wavelength can be reserved at theappropriate time, then the setup
message is rejected and the corresponding burst is dropped [16].These two techniques have
been adopted in OBS. Depending on bandwidth reservation, offsettime and control
management, three schemes for OBS implementation have beenproposed: Tell-and-go (TAG)
[16], Just-in-time (JIT) [12][13] and Just-enough-time (JET)[14].
2.2.1 Tell-And-Go (TAG)
This is an immediate reservation scheme. In TAG, the CB istransmitted on a
control channel followed by a DB, which is transmitted on a datachannel with zero or
negligible offset. The CB reserves the wavelength and buffer(FDL) at each intermediate node
along the path for the DB. When the DB reaches an intermediatenode, it is buffered using the
reserved FDL until the CB processing is finished. Then the DB istransmitted along the
reserved channel. If no wavelength is available for reservation,the burst is dropped and a
negative acknowledgement (NAK) is sent to the source. The sourcenode sends another CB
after transmitting the DB for releasing the reserved wavelengthsalong the path. Here, the burst
size is not fixed in advance. FDLs are expensive and they canonly buffer data optically for a
very short time. Optical buffering is the main drawback of thisscheme. Furthermore, if the
release CB which is sent to release the reserved bandwidth alongthe path is lost, then these
wavelengths will not be released and this creates bandwidthwastage [13, 14].
25
7/30/2019 Giai Quyet Tranh Chap Trong Obs
35/85
2.2.2 Just-In-Time (JIT)
This scheme also comes under immediate reservation. Here, anoutput wavelength
is reserved for the upcoming burst as soon as the CB processingis finished. The source
transmits the DB after an offset time which is greater than thetotal CB processing time. If the
wavelength is not available, the burst is dropped. Thedifference between JIT and TAG is that
the buffering of the DB at each node is eliminated by insertinga time gap between the CB and
the DB. Since the bandwidth is reserved immediately after the CBprocessing, the wavelength
will be idle from the time the reservation is made till thefirst bit of the DB arrives at the node.
This is because of the offset between the CB and the DB. Sincethe offset value decreases as
the CB gets closer to the destination, the idle time alsodecreases. An in-band-terminator is
placed at the end of each burst which is used by each node torelease the reserved wavelength
after transmitting the DB [12, 19].
Wavelength reservation in JIT at an intermediate node is shownin Figure 2.4. Let t
be the time a CB arrives at some OBS node along the path to thedestination. Let Tsetup be the
amount of time it takes an OBS node to process the controlburst. Let Toffset be the offset value
of a burst. This is equal to the time gap between the CB and theDB transmission. The offset
value depends on (1) the wavelength reservation scheme, (2) thenumber of nodes the burst has
already traversed, and (3) other factors, such as whether theoffset is used for service
differentiation [11]. Toxc is the amount of time it takes theOXC to configure its switch fabric to
set up a connection from an input port to an output port. Oncethe processing of the CB is
complete at time t + Tsetup, a wavelength is immediatelyreserved for the upcoming burst, and
26
7/30/2019 Giai Quyet Tranh Chap Trong Obs
36/85
7/30/2019 Giai Quyet Tranh Chap Trong Obs
37/85
reserves wavelength for the upcoming burst for a fixed durationof time. The reservation is
made from the time when the first bit of DB reaches the nodetill the last bit of DB is
transmitted to the output port. This eliminates the wavelengthidle time which is the main
difference between JET and JIT. Since the wavelength is reservedfor a fixed duration, there is
no need for explicit signal for releasing the reservedwavelength along the path. Since there is
no wastage of bandwidth in this scheme, the network utilizationfor this scheme is higher than
with the other schemes. But, this scheme involves complexscheduling when compared to other
schemes.
Figure 2.5 JET scheme
The operation of delayed reservation in JET is shown in Figure2.5. Let us again
assume that a control burst arrives at an OBS node at time t.Let the offset be Toffset and let the
length of the DB be . The first bit of the corresponding burstis expected to arrive at time
t+Toffset. After processing the CB, the node reserves awavelength for the DB starting at time t 1
= t + Toffset TOXC and ending at time t1+. At time t0, the OBSnode instructs its OXC fabric
28
7/30/2019 Giai Quyet Tranh Chap Trong Obs
38/85
to configure its switch elements to carry the data burst, andthis operation completes just before
the arrival of the first bit of the burst. Thus, whereasimmediate reservation protocols only
permit a single outstanding reservation for each outputwavelength, delayed reservation
schemes allow multiple setup messages to make futurereservations on a given wavelength
(provided of course, that these reservations, do not overlap intime). A void is created on the
output wavelength between time (t + Tsetup), when thereservation operation for the upcoming
burst is completed, and time (t1 = t + Toffset - TOXC), when theoutput wavelength is actually
reserved for the burst. In an attempt to use the voids createdby the earlier setup messages, void
filling algorithms are employed in JET [16].
TAG and JIT schemes are significantly simpler than JET sincethey do not involve
complex scheduling or void-filling algorithms. On the otherhand, previous studies have shown
that JET performs better than either JIT or TAG in terms ofburst loss probability [14] [16].
2.3 Contention Resolution Schemes
Contention resolution is necessary for handling certain caseswhere two or more
bursts try to reserve the same link and the same wavelength forthe same time. This is called
external blocking. In packet switching, this is avoided bybuffering the contending packets. In
OBS, when two or more bursts contend for the same wavelength andfor the same time
duration, only one of them is allotted the bandwidth. In suchcase, one or a combination of the
following three major options for contention resolution can beapplied in addition to the option
of dropping the unsuccessful bursts.
Wavelength domain:By means of wavelength conversion, a burst canbe sent on a different
wavelength channel of the designated output line [18].
29
7/30/2019 Giai Quyet Tranh Chap Trong Obs
39/85
Time domain:By utilizing an FDL buffer, a burst can be delayeduntil the contention situation
is resolved. In contrast to buffers in the electronic domain,FDLs only provide a fixed delay
and data leave the FDL in the same order in which they entered[18].
Space domain: In deflection routing, a burst is sent to adifferent output link of the node and
consequently on a different route towards its destination node.Space domain can be exploited
differently in case several fibers are attached to an outputline. A burst can also be transmitted
on a different fiber of the designated output line withoutwavelength conversion [18].
When there is no available unscheduled channel, and a contentioncannot be
resolved by any one of the above techniques, one or more burstsmust be dropped. The policy
for selecting which bursts to drop is referred to as the softcontention resolution policy and is
aimed at reducing the overall burst loss rate, BLR, andconsequently, enhancing link utilization
[9]. Several soft contention resolution algorithms have beenproposed and studied in earlier
literature, including the shortest-drop policy [25] andlook-ahead contention resolution [26]. In
burst segmentation, only that part of the burst which isinvolved in a reservation conflict will
be dropped [16]. The contention resolution policies areconsidered as reactive approaches in
the sense that they are invoked after contention occurs. Analternative approach to reduce
network contention is by proactively attempting to avoid networkoverload through traffic
management policies [9].
2.3.1 Optical Buffering
Optical buffering is achieved through the use offiber delaylines (FDL). Due to the
lack of optical random access memory, FDL is currently the onlyway to implement optical
buffering. By implementing multiple delay lines in stages [16]or in parallel [17], a buffer may
30
7/30/2019 Giai Quyet Tranh Chap Trong Obs
40/85
be created that can hold a packet for a variable amount of time.In any optical buffer
architecture, the size of the buffers is severely limited, notonly by signal quality concerns, but
also by physical space limitations. The FDLs are bulky. To delaya single packet for 5s would
require over a kilometer of fiber [17]. Because of this sizelimitation of optical buffers, a node
may be unable to effectively handle high load or bursty trafficconditions. Furthermore, signal
dispersion and attenuation are some of the limitations of FDLs.Because of these drawbacks,
delay lines may be acceptable in prototype switches, but are notcommercially viable.
The reservation scheme involving optical buffer contentionresolution consists of
two phases: wavelength reservation in the output port and FDLreservation in the optical
buffer [19]. During the wavelength reservation phase, thescheduler checks the required
wavelength at the output port first. If the required wavelengthwill be idle at t+ and the idle
duration is long enough to accommodate the DB, this wavelengthis reserved immediately. If
the wavelength is not available for that particular period oftime, then the minimum waiting
time W for reserving the wavelength is computed. If W>D(fiber delay), the DB has to be
discarded, since no FDL can provide such a delay. In the caseofW D, FDL reservation is
performed. The wavelength reservation is made for the latestavailable time and until then the
DB will be buffered through the reserved FDL. The DB will betransmitted from the FDL onto
to the reserved output wavelength as soon as the waiting timeequals W. In case, both the
required wavelength and the FDL are not available, then theburst will be dropped. Optical
buffering is generally used in combination with the othercontention resolution schemes such
as wavelength converters and deflection routing to improveperformance. How ever, they are
not feasible for large scale deployment.
31
7/30/2019 Giai Quyet Tranh Chap Trong Obs
41/85
Figure 2.6 Contention resolution using FDL
2.3.2 Wavelength Conversion
In wavelength routed networks, lightpaths are required to carrymessages. The
wavelength continuity constraint has to be satisfied forsuccessful communication. If a route is
free but no common wavelength is available on it, then it cannotbe used for setting a lightpath.
This results in the blocking of the connection, even though thebandwidth is available. All such
connections would have been successful if there were nowavelength continuity constraint.
Wavelength conversion is the process of converting a wavelengthon an incoming
channel to another wavelength on the outgoing channel [2, 4]. Awavelength converter is a
device that is capable of converting an incoming signalswavelength to a different outgoing
wavelength. The wavelength continuity constraint can be relaxedby the use of wavelength
32
7/30/2019 Giai Quyet Tranh Chap Trong Obs
42/85
conversion. The wavelength conversion is classified into:optical-electronic conversion and all-
optical conversion. The disadvantages ofoptical-electronic-optical conversion (such as
complexity and large power consumption) have increased theinterest on to all-optical
conversion [19].
The following are the different categories of wavelengthconversion:
Full conversion:Any wavelength shifting is possible. Channelscan be connected regardless of
their wavelengths.
Limited conversion:Wavelength shifting is restricted so that notall combinations of channels
may be connected.
Fixed conversion: A restricted form of limited conversion suchthat, for each node, each
channel maybe connected to exactly one pre-determined channel onall other links.
Sparse wavelength conversion:Networks are comprised of a mix ofnodes having full and no
wavelength conversion capabilities; i.e. only a subset of nodesin the network have conversion
capability.
The concept of wavelength conversion is shown in Figure 2.7.Assume that
connections are required to be established between node pairs(C, D) and (A, D). Both
connections will select the wavelength W1 for lightpathestablishment. At node B, both
connections try for wavelength W1 on link BD. Only one of theconnections can be accepted.
Let that be the connection (C, D). Wavelength W2 is available onthe link BD. Since the
connection (A, D) is unable to satisfy the wavelength continuityconstraint, it would be
dropped. But, by converting the wavelength of connection (A, D)from W1 to W2, the
connection can be routed onto link BD. Thus, the connection willbe successful by using the
wavelength conversion capability.
33
7/30/2019 Giai Quyet Tranh Chap Trong Obs
43/85
Wavelength converters offer a 10%-40% increase in reuse valueswhen
wavelengths availability is small [15]. There are manywavelength conversion algorithms and
algorithms to minimizing the number wavelength converters.Despite the high expectations and
some promising experimental reports, wavelength conversiontechnologies are as yet immature
and are highly expensive for deployment in real networks.
A B
C D
E
W 1
W 1W 1
W 2
Wavelength conversionW 1--> W 2
Figure 2.7 Wavelength conversion
2.3.3 Deflection Routing
Deflection routing is the approach of resolving contention byrouting a contending
packet to an output port other than the intended output port[22, 23, 24]. However, the
deflected packet may end up following a longer path to itsdestination. As a result, the end-to-
end delay for a packet may be unacceptably high. Deflectionrouting is generally not favored in
electronic packet-switched networks due to potential looping andout-of-sequence delivery of
packets. In WDM optical networks where buffer capacity is verylimited and wavelength
conversion is not feasible, implementation of deflection routingmay be necessary in order to
maintain a reasonable level of packet losses.
34
7/30/2019 Giai Quyet Tranh Chap Trong Obs
44/85
An example of deflection routing in WDM networks is given inFigure 2.8. Both
nodes A and B are sending bursts to node E. Before sendingbursts, nodes A and B send
control packets (denoted as C (A, E) and C (B, E)) on theirout-of-band control channels for
bandwidth reservation for their respective data bursts. Letssay, C (B, E) arrives at Node C
earlier than C (A, E). In this case, the output link CE isreserved by C (B, E). When C (A, E)
arrives at node C, the link CE is not available. Withoutdeflection, this burst will be dropped.
But, Node C checks other output links and selects the deflectionlink CD which is idle, to
deflect B (A, E). Node D forwards B (A, E) via the link betweenD and E based on its routing
table. Since every node performs deflection routing in thismanner, the deflected burst arrives
at its destination with some extra propagation delay, i.e., ittraverses several additional nodes
than the shortest path. The idle optical links can be consideredas fiber delay lines for
buffering the blocked bursts. The bursts in the congested partof the network are then
distributed to other underused parts, thus overall linkutilization and network performance can
be improved. If the burst cannot be deflected, then it will bedropped. Such an instance will be
referred to as normal deflection failure in this thesis.
B
D
A
C
E
F
C ( B , E )
C (A ,E )
Figure 2.8 Deflection routing
35
7/30/2019 Giai Quyet Tranh Chap Trong Obs
45/85
Deflection routing implementation in OBS has many benefits. Whena burst is
dropped, it wastes the bandwidth on the partially establishedpath. If the burst data has been
injected into the network, the network should do the best toforward it to the destination, rather
than simply drop it. Also, when a retransmission of the droppedburst is done, the total
transmission delay will be the sum of the delay of the droppedburst and the delay of the
retransmitted burst. This delay becomes very large whenretransmitting a blocked burst in
long- distance links. By applying suitable algorithms likelimited deflection [18], burst looping
can be reduced. In JET, deflection routing coupled with opticalbuffering (FDL) tends to
reduce the problem of insufficient offset time [19].
36
7/30/2019 Giai Quyet Tranh Chap Trong Obs
46/85
Chapter 3
New Deflection-Based Contention Resolution Schemes
As of now, optical wavelength conversion and optical bufferingtechnologies are
very immature. It seems that the most viable option for reducingburst loss caused by
contentions is deflection routing. However, the traditionaldeflection routing scheme doesnt
consider all the available resources in resolving a contention.Due to this, the degree of success
in contention resolution gained by the deflection routing schemeis not satisfactory. In this
chapter, three new schemes are proposed for handling contentionsthat aim to improve on the
existing schemes.
Consider Figure 2.8 in the previous chapter. As the controlburst C (A,E) reaches
node C, the status of the outgoing links at node C is checked.If both the links CE and CD are
unavailable for reservation, then the burst is dropped.Basically, at each node, each burst has
only one chance for deflection. If no idle bandwidth isavailable at any node, the burst is
dropped without getting a second chance. For instance, supposethat node C is congested. If the
control burst fails to reserve bandwidth at node C even on thedeflection route, then the control
burst will be dropped. Since the complete network state is notknown to all the nodes, nodes
will try to send their bursts through C till they realize thecongestion at C after losing some
bursts.
We propose a new scheme called Backtrack on deflection failurewhich
provides a second chance to a blocked burst when a deflectionfailure occurs. Two variants are
proposed to handle the backtracking delay involved in thisscheme. Furthermore, we propose a
third scheme called Bidirectional reservation on burst drop inwhich bandwidth
reservation is made in both the forward and the backwarddirections at the same time. This
37
7/30/2019 Giai Quyet Tranh Chap Trong Obs
47/85
scheme comes into effect only when a control burst gets droppeddue to bandwidth
unavailability. In the following sections, we describe how thesenew schemes work.
3.1 Backtrack on Deflection Failure
In this scheme, at any node, if the control burst fails toreserve a wavelength on
any of its primary or deflection routes, the burst will not bedropped as in earlier deflection
schemes. Instead, the burst in this scheme will get a secondchance to backtrack to the previous
node and may get routed through any deflection route availableat the previous node. Due to
backtracking, each burst will face an increase in the lightpathsetup delay. The additional setup
delay will be equal to twice the propagation delay between thetwo nodes involved in
deflection failure and backtrack and twice the control burstprocessing time. This is because,
on deflection failure, the burst will backtrack to the previousnode and no reservations will be
made during this round trip time period. When this happens, itwill reduce the offset gap
between the control burst and its corresponding data burst.Therefore, the chances of the data
burst reaching a node before a reservation is made willincrease. To avoid such an event, the
extra delay created through backtracking should be properlyaccommodated. This is part of the
tradeoff involved in providing a second chance for any burst. Inorder to accommodate the
extra delay that may be caused by deflection failure andsubsequent backtracking, two
approaches are proposed. They are Increase in the initial offsetand Open loop
wavelength reservation.
3.1.1 Routing Protocol
The lightpath setup mechanism involves four types of controlbursts: primary
control burst (PCB), backtrack control burst (BCB), probe burst(PB) and backtrack probe
burst (BPB) in addition to a negative acknowledgement (NAK).Whenever a burst drop occurs,
38
7/30/2019 Giai Quyet Tranh Chap Trong Obs
48/85
a NAK is sent to the source to inform it about the burst drop. Aprimary control burst is used
for wavelength reservation along the path to the destination.This control burst contains all the
information required for lightpath setup. Whenever a normaldeflection failure occurs, a BCB
is created which is a copy of the corresponding PCB. The BCB isused for backtracking to the
previous node on normal deflection failure. A probe burst issimilar to a PCB except that no
reservation will be made by a probe. The main function of PB isto probe the network and to
inform the previous node about congestions. BPB is similar toBCB. When PB encounters
contention and deflection failure, a BPB is created and sent tothe previous node to inform it
about the contention. The most common information fields andtheir descriptions in a typical
control burst are shown in Figure 3.1.
Information Description
Packet identifier Kind of control burst (PCB,BCB,PB,BPB,ACK,NAK)
Sender address Source node address of the burst
Receiver address Destination node address of the burst
Burst number Sequence number of the burst
Offset time Time gap between control and data bursts
Absolute time Departure time of CB at each node
Burst length Duration of the data burst
Timeout Time for the burst to live in the network to preventlooping
Backup flag Set when both primary and deflection routes areavailable
Deflection flag Set when the burst deflects or backtracks
Figure 3.1 Information fields in a control burst
39
7/30/2019 Giai Quyet Tranh Chap Trong Obs
49/85
3.1.2 Backtrack on Deflection Failure with Increase in InitialOffset
In order to provide backtracking capability for a control burst,the extra delay
that will be caused by backtracking should be considered. Onesolution for this problem is to
increase the initial offset. Initial offset of a burst isgenerally equal to the total processing time
of the control burst from its source to the destination. Thisshould be increased to
accommodate the backtrack delay. The backtrack delay is equal tothe sum of the round trip
propagation delay between any two nodes in the network and twotimes the control processing
delay. No reservation is made during this entire time duration.Thus, for providing
backtracking capability, the total initial offset should begreater than the sum of the total
processing delay and the backtrack delay.
3.1.2.1 Routing Procedure
The routing procedure for each intermediate node in an OBSnetwork is as follows:
When a node receives a control burst, it is processed. Dependingon the status of the outgoing
links and the status of the information fields in the CB, thenode takes an appropriate decision.
A routing algorithm for the above scheme which describes allpossible routing decisions is
given below.
1. Begin
2. If (BURST IDENTIFIER=PCB) then
3. If(both the primary and deflection routes are available)then
4. Make reservation on the primary link. Forward a PCB along thereserved path.
5. Convert a copy of PCB into a PB and send it along thedeflection link.
6. end-if
7. If(only one among the primary and deflection links isavailable) then
40
7/30/2019 Giai Quyet Tranh Chap Trong Obs
50/85
8. Make reservation on the available link and forward the PCB onthat link.
9. If(neither the primary nor the deflection link is available)then
10. If(Backup flag is set) /*it denotes that the burst canbacktrack to the previous node in
the path and can take the deflection route available*/ then
11. Convert the PCB into a BCB and send it to the previousnode.
12. Else
13. Drop the burst and send a NAK to the source.
14. end-if
15. end-if
16. If (BURST IDENTIFIER=BCB) then
17. Delete the reservation made on the primary link for thisburst (because the burst
faced deflection failure at the next node on that link).
18. If(deflection route is available at the present node)then
19. Make reservation on that link. Convert the BCB into a PCBand
forward it on the deflection link.
20. Else
21. Drop the burst and send a NAK to the source.
22. end-if
23. If(BURST IDENTIFIER=PB) then
24. If(both the primary and deflection routes are available)then
25. Forward the probe burst on the primary output link. Noreservation is made.
26. If(only one among the primary and deflection links isavailable) then
Forward the probe burst along the available output link.
41
7/30/2019 Giai Quyet Tranh Chap Trong Obs
51/85
27. If(neither primary nor deflection route is available)then
Transmit the probe burst to the previous node on its traveledpath after
changing the burst identifier to a BPB (backtrack probeburst).
28. end-if
29. If(BURST IDENTIFIER=BPB) then
30. Mark the link, between the present node and the node fromwhich the BPB has
backtracked, as unavailable for that particular burst. /* Due tothis, if the primary CB
corresponding to that probe burst reaches this node, it will notmake reservation along
this path which has a deflection failure on the next node in thepath. The PCB will opt
for an alternate available route. This avoids backtracking ofthe primary control burst
due to unavailability of bandwidth on the next node which hadbeen probed by its PB*/.
31. end-if
32. End
3.1.3 Backtrack on Deflection Failure with Open LoopReservation
When a deflection failure occurs at a node, the control burstbacktracks if it has an
available deflection route at the previous node. In the previousscheme, in order to provide
backtracking capability, the offset has been increased. Lets saythat only 20% of the bursts get
blocked due to normal deflection failure and hence will utilizebacktracking capability. The
remaining 80% of the bursts will thus be successful withoutbacktracking. Even though these
bursts dont use the backtracking capability, they face an extradelay due to the increase in
initial offset which provides the backtracking capability. Thismay be considered a drawback.
By reserving available bandwidth on the backtrack link, thisinitial offset increase can be
42
7/30/2019 Giai Quyet Tranh Chap Trong Obs
52/85
eliminated. The scheme we describe here uses this idea whilebacktracking, and thus
overcomes the drawback associated with the Increase in initialoffset approach.
When a control burst faces a normal deflection failure and if ithas an available
deflection route on the previous node in the path, then theburst checks for bandwidth
availability on the link from the present node to the previousnode. If bandwidth is not
available on that link, the burst is dropped. If it isavailable, it is reserved. This creates an open
loop in the path reserved for the data burst. The control burstthen backtracks to the previous
node and tries the deflection route at that previous node. Byreserving bandwidth on the
backtrack link, the length of the path for the upcoming databurst is increased as it creates a
loop between those nodes involved in backtracking anddeflection. This will accommodate the
backtrack propagation delay. In short, the purpose of thisapproach is to keep the data burst far
enough in time behind its control burst while providing thebacktracking capability to the
control burst without increasing the initial offset.
3.1.3.1 Routing Procedure
The only situation when this protocol differs from the one insection 3.1.2 occurs when the
Primary Control Burst (PCB) faces a normal deflection failure.The following algorithm details
the routing decisions taken by the intermediate node in suchsituations.
1. Begin2. If (BURST IDENTIFIER=PCB) then3. If(both primary anddeflection routes are not available) then4. If(Backup flag is set)then5. Check for bandwidth availability on the backtrack link andreserve
it, if available. Convert the PCB into a BCB and send it tothe
43
7/30/2019 Giai Quyet Tranh Chap Trong Obs
53/85
7/30/2019 Giai Quyet Tranh Chap Trong Obs
54/85
Figure 3.2 Backtrack on deflection failure
Time 0 1 2 3 4
CB S (S---A)(S---K)
A (A-x-B)(A---C)
C (C---B)(C---E)
Backup flag=1
B (B-x-D)
(B-x-G)
Backtrack
C (C---E)
Probe P1(S---K) C P2(C---E) E P2(E---G) G P2(G---D)
Figure 3.3 Decision table for time period (0-4)
The shortest route from S to D is along S-A-B-D. At time 0, theCB is processed by the source S.
At S, both the primary link (SA) and the deflection link (SK)are available. Bandwidth is
reserved on the primary link and the CB is forwarded on the link(SA). A probe burst P1 is
created and is forwarded on the link (SK). At time 1, the CBreaches node A. At node A,
bandwidth on the primary link (AB) is not available. Thedeflection link (AC) is available
and the reservation is made on the deflection link. The CB isforwarded on link (AC). At time
2, the CB reaches node C. At node C, both the primary link (CB)and the deflection link (C
E) are available. Reservation is made on the primary link. Thebackup flag in the CB is set to
unity and the CB is sent to the next node on link (CB). A newprobe P2 is created and
45
7/30/2019 Giai Quyet Tranh Chap Trong Obs
55/85
forwarded on the link (CE). At time 3, the CB reaches node B.Neither the primary link (B
D) nor the deflection link (BG) are available at node B. In sucha case, the burst would be
dropped in the earlier deflection schemes. In our scheme, the CBbacktracks to the previous node
and tries to use an alternate path to reach the destination.Since the backup flag is set to unity in
the CB, node B sends the CB to the previous node C. In the meantime, the probe P2 reaches
node E. At the node E, both the primary link (EG) and thedeflection link (EF) are available.
P2 is forwarded on the primary link to node G. At time 4, the CBbacktracks from the node B
and reaches C. The deflection link (CE) is available and thereservation is made on that link.
The CB is then sent to the node E. The probe P2 reaches node G.To understand the idea behind
the use of probe bursts, let us consider the following twodifferent cases.
Time 5 6 7
CB E (E---G)(E---F)
G (G---D) DEST D
Probe P2(DEST D)
Figure 3.4 Decision table for Case 1
Case 1: If the link (GD) is available, the probe P2 is forwardedon that link to the destination
D. At time 5, node E receives the CB. After processing the CB,reservation is made on the
available primary link (EG) and the CB is forwarded to the nextnode G. The probe P2 reaches
the destination D at time 5. At time 6, node G receives the CBand sends it on the available
primary link (GD) after making the wavelength reservation. Attime 7, the CB reaches the
destination. The corresponding data burst will follow thereserved route S-A-C-E-G-D.
Case 2: If both the primary link (GD) and the deflection link(GB) are unavailable, the
probe P2 is sent back to the previous node E. At time 5, node Ereceives P2 and the CB. Node E
processes P2 and marks the link (EG) as unavailable for thecorresponding CB even though
46
7/30/2019 Giai Quyet Tranh Chap Trong Obs
56/85
the link is available. This is because, P2 has backtracked fromG to E due to bandwidth
unavailability. If the CB is sent on this link to node G, itwill also have to backtrack to E due to
bandwidth unavailability at G. This will cause an extra roundtrip delay in the reservation
process. After processing the CB, the bandwidth is reserved onthe deflection link (EF). The
main purpose of the probe burst is to minimize the chances ofbacktracking by the corresponding
CB due to unavailable bandwidth and in turn reduce the totalroute reservation time. At time 6,
node F receives the CB and sends it to the next node D aftermaking reservation on link (FD).
At time 7, the CB reaches the destination.
Time 5 6 7CB E (E---G)
(E---F)F (F---D) DEST D
Probe E P2(Drop)(E-x-G)
Figure 3.5 Decision table for Case 2
3.2 Bidirectional Reservation on Burst Drop for RetransmissionBurst
In OBS, when a control burst encounters a deflection failure,the burst is dropped and a NAK is
sent to the sender. After receiving the NAK, the sender sends anew control burst for reservation
of bandwidth. However, the probability of this control burstgetting blocked will be the same as
the probability of the previously failed control burst. Also,even though the data burst is ready to
be sent into the network, it has to wait for certain amount oftime equal to the offset before it can
be retransmitted.
In Bidirectional reservation on burst drop scheme, when acontrol burst is
blocked at any intermediate node, the node calculates the totaltime a control burst will
consume to reach the sender from the present node. It alsocalculates the total propagation
47
7/30/2019 Giai Quyet Tranh Chap Trong Obs
57/85
delay for a data burst to reach the present node from thesender. This total time will be taken as
the offset and tries to reserve bandwidth on the output link. Ifthe output link is not available
for that time, then the link will be reserved starting at timeit is available which is greater than
the offset and the offset value will be changed accordingly. Thenode then creates two new
control bursts one for forward reservation and one for backwardreservation.
With the value of the offset decided, the forward control burstis sent on the output
link towards the destination. At each node on its path, theforward control burst reserves
available bandwidth and tries to reach the destination. Inparallel, the backward control burst
will be sent to output link which leads to the source. At eachintermediate node en route to the
source, the backward control burst tries to reserve bandwidth onthe output link leading to the
previous node in its path to the source. The reservation timewill be calculated based on its
offset. If either of the control bursts encounters a block(while going forward or backward),
that control burst is dropped and a NAK will be sent to thesource as well as the destination.
The NAK will inform the intermediate nodes about theunsuccessful lightpath setup and the
intermediate nodes will remove any reservations made for thecorresponding data burst. This
way, the route between source and destination is split into twoparts and the reservation is
made concurrently in both directions.
In existing OBS schemes, the size of the offset is typically setto a value equal to
the total control burst processing delay. But in our thirdscheme, for the retransmission burst,
the offset will include the propagation delay in addition to thetotal processing delay.
Propagation delay is assumed to be much greater than theprocessing delay (generally,
propagation delay is in milliseconds and processing delay is inmicroseconds). All those bursts
which get blocked will have this extra offset time. The firsttime bursts will have normal offset
48
7/30/2019 Giai Quyet Tranh Chap Trong Obs
58/85
which will be much smaller than the retransmitted bursts. Hence,the contention if occurs will
be either among retransmission bursts or among first timebursts. This should tend to increase
the probability of success for a retransmission burst. Also, thesender can transmit the data
burst as soon as it receives the backward control packet byexamining its offset.
3.2.1 Offset Calculation
Consider a multi-node optical network shown in Figure 3.6. Letthe diameter of the
network be N hops. Let Tp be the CB processing time, Td be thepropagation delay between
any two nodes in the network and L be the length of the databurst. In general, Tp
7/30/2019 Giai Quyet Tranh Chap Trong Obs
59/85
The time at which the first bit of the data burst reaches thenode k = tk+ (N-K) Tp
The time at which the last bit of the data burst leaves the nodek = tk+ (N-K) Tp + L
Hence, the reservation is to be made for the time period [tk +(N-K) Tp , tk + (N-K) Tp + L]. If
the bandwidth is unavailable for the calculated time period andif the deflection is not possible,
then the control burst will be dropped by node K and a NAK willbe sent to the source.
Figure 3.7 Bidirectional reservation on control burst drop
In Bidirectional reservation on burst drop scheme shown inFigure 3.7, a NAK will not be
sent to the source. Instead, two new control bursts, a forwardcontrol burst (FCB) and a
backward control burst (BCB), are created at that node (node Kin our example). The FCB is
sent forward to the destination and the BCB is sent backward tothe source. These two control
bursts try to reserve the bandwidth for the data burst whosecorresponding control burst has
been dropped. Before sending the new control bursts into thenetwork, offset value is to be
determined.
The offset for the newly created control bursts is calculated asfollows:
The number of hops between the present node and the source isk.
50
7/30/2019 Giai Quyet Tranh Chap Trong Obs
60/85
The time required for the BCB to reach the source from thepresent node = K (Td + Tp)
The time required for the DB to reach the present node from thesource = K Td
The total time required for the DB to reach the present nodefrom the source = K (2 Td + Tp)
This will be the new minimum offset for the new control bursts.Certain processing time is
required for creating new CBs and for calculating the offset.Let us suppose that the bandwidth
reservation is made at time tk+1. The node will reserve thebandwidth for the time period [tk+1 +
K (2 Td + Tp) , tk+1 + K (2 Td + Tp) + L]. If the reservation isunavailable for the required time
period, then the earliest available time greater than [tk+1 + K(2 Td + Tp)] is selected and the
reservation is made accordingly. The new offset is increasedbased on the starting time of the
bandwidth reservation.
After the reservation is made at node k, the FCB is sent in theforward direction
and the FCB performs the bandwidth reservation for the DB alongits path to the destination.
The BCB backtracks towards the source reserving the bandwidthalong its path. The
intermediate nodes which receive these control bursts use thestored offset value for calculating
the time period of bandwidth reservation.
Since the new offset in bidirectional reservation is much largerthan the normal
offset, the probability of such bursts getting dropped will bemuch less than the dropping
probability for the bursts with normal offset. Thus, theprobability of success for retransmitted
burst is expected to be higher than the probability of successfor first time bursts. This is the
hypothesis behind this third approach of ours. The next chapterpresents the results for our
proposed approaches which were obtained through simulations.
51
7/30/2019 Giai Quyet Tranh Chap Trong Obs
61/85
Chapter 4
Simulation & Results
In this chapter, we present the results obtained throughsimulations for our
proposed approaches and for the schemes presented in theliterature. We compare the results
and show that our schemes perform better than those previouslyproposed in the literature. Two
previous schemes No deflection and Deflection are compared withour proposed schemes
which include the two versions of Backtrack on deflectionfailure and Bidirectional
reservation on burst drop.
4.1 Simulator Setup
In order to evaluate the performance of the new contentionresolution schemes, we
designed a new simulator. The simulator was developed in the Clanguage. The sample
networks used in the evaluation are NSFNET and USA long haulnetwork. A separate Poisso
![Giai Quyet Tranh Chap Trong Obs - [PDF Document] (2024)](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABCAQAAAC1HAwCAAAAC0lEQVR42mP8/h8AAvMB+NzmkbcAAAAASUVORK5CYII=)