Transcript Traffic Engineering in Multi-Granularity, Heterogeneous, WDM

Traffic Engineering in
Multi-Granularity, Heterogeneous,
WDM Optical Mesh Networks
Through Dynamic Traffic Grooming
Keyao Zhu, Hongyue Zhu, and Biswanath
Mukherjee
1
• Introduction
• Node Architecture in Heterogeneous WDM
Backbone Networks
• Provisioning connections in
Heterogeneous WDM networks
• A Generic Provisioning Model
• Illustrative Numerical Examples
• Future Work
2
Introduction
• Traffic engineering：it is an effective
solution to control the network congestion
and optimize network performance.
• purpose：it is to facilitate efficient and
reliable network operations while
simultaneously optimizing network
resource utilization and traffic performance.
3
Traffic Engineering In Optical WDM
Networks Through Traffic Grooming
Traffic Grooming
• High-bandwidth wavelength channels will be
filled up by many low-speed traffic streams
• Efficiently provisioning customer connections
with such diverse bandwidth needs is the trafficgrooming problem.
4
Dynamic traffic-grooming problem
• Each such connection needs to be
properly routed through the network based
on the current network state.
5
Optical WDM Network
Heterogeneity
Network equipment (NE) may come from different vendors
and new equipment has to co-exist with legacy equipment.
For example:
• (1) network nodes may have optical crossconnects
(OXCs) employing different architectures and
technologies;
• (2) not all nodes may have wavelength conversion and
traffic grooming capabilities
• (3) wavelength conversion and traffic grooming may only
be available on certain wavelength channels
• (4) different fiber links may support different numbers of
wavelength channels, which may also operate at
different speeds.
6
Node Architecture in Heterogeneous
WDM Backbone Networks
There are transparent and opaque
approaches to build these OXCs.
• The transparent approach refers to alloptical (O-O-O) switching
• The opaque approach refers to switching
with optical-electronic-optical (O-E-O)
conversion.
7
Four kinds of OXCs(1/7)
According to their grooming capabilities, OXCs can be
divided into four categories
(1)Non-grooming OXC:
• It has wavelength-switching capability.
• There is no low-data-rate port on a nongrooming OXC.
8
Four kinds of OXCs(2/7)
(2)Single-hop grooming OXC:
• This type of OXC will only switch traffic at wavelength
granularity.
• It may have some lower-data-rate ports, which can
directly support low-speed traffic streams.
• The traffic from these low-speed ports can be
multiplexed onto a wavelength channel using a TDM
scheme, before the traffic enters the switch fabric.
• All of low-speed streams on one wavelength channel at
the source node will be switched to the same destination
node
9
Four kinds of OXCs(3/7)
• Fig. 1(a) shows how a low-speed
connection (C1) is carried by a lightpath
(L4) from node 1 to node 5 using the
single-hop grooming scheme.
• In Fig. 1(a), nodes 1 and 5 are equipped
with single-hop grooming OXCs, which
can only switch at wavelength granularity.
10
11
Four kinds of OXCs(4/7)
(3)Multi-hop partial-grooming OXC:
• the switch fabric of this type of OXC is composed of two
parts:
• A wavelength-switch fabric (W-Fabric)
• An electronic-switch fabric which can switch lowspeed traffic streams is called grooming fabric (G-Fabric).
• With this hierarchical switching and multiplexing
architecture, this type of OXC can switch low-speed
traffic streams from one wavelength channel to other
wavelength channels and groom them with other low
speed streams
12
13
Four kinds of OXCs(5/7)
• Fig. 1(a) also shows how a low-speed
connection (C2) can be carried by multiple
lightpaths (L1, L2, and L3) from node 1 to
node 5.
• nodes 2 and 3 are equipped with multihop
partial-grooming OXCs, and only their GFabrics are shown in the figure.
14
15
Four kinds of OXCs(6/7)
• In this architecture, only a few of
wavelength channels can be switched to
the G-Fabric for switching at finer
granularity.
• Assuming that the wavelength capacity is
OC-N and the lowest input port speed of
the electronic switch fabric is OC-M ( M ≤
N ), the ratio between N and M is called
the grooming ratio.
16
Four kinds of OXCs(7/7)
(4) Multi-hop full-grooming OXC:
• Every OC-N wavelength channel arriving
at the OXC will be de-multiplexed into its
constituent OC-M streams before it enters
the switch fabric.
• Then, the switched streams will be
multiplexed back onto different wavelength
channels.
17
18
Provisioning Connections in
Heterogeneous WDM Networks
There are three important components in
WDM network control, which determine how
connections of different bandwidth
granularities are provisioned.
(1) resource-discovery protocol
(2) route-computation algorithm.
(3) signaling protocol
19
Resource Discovery:
Four types of lightpaths(1/4)
Multi-hop un-groomable lightpath:
• It is not connected with a finer-granularity
switching element at its end nodes.
• This lightpath can only be used to carry
the traffic directly between node pair (i, j).
• Lightpath L4 in Fig. 1(a) is a multihopungroomable lightpath.
20
21
Resource Discovery:
Four types of lightpaths(2/4)
Source-groomable lightpath:
• It is only connected with a finer-granularity
switching element at its source node.
• All traffic on this lightpath has to terminate
at node j, but the traffic may originate from
any other network node as well.
• Lightpath L3 in Fig. 1(a) is a sourcegroomable lightpath.
22
23
Resource Discovery:
Four types of lightpaths(3/4)
Destination-groomable lightpath:
• it is only connected with a finer-granularity
switching element at its destination node.
• All traffic on this lightpath has to originate from
node i. At the lightpath destination node j, the
traffic on lightpath (i, j) can either terminate at j
or be groomed to other lightpaths and routed
towards other nodes.
• Lightpath L1 in Fig. 1(a) is a destinationgroomable lightpath.
24
25
Resource Discovery:
Four types of lightpaths(4/4)
Full-groomable lightpath:
• It connects to finer-granularity switching
elements at both end nodes.
• Lightpath L2 in Fig. 1(a) is a fullgroomable lightpath.
26
27
Resource Discovery:
Link type(1/3)
we present the link state of each network link type as
follows.
Fiber Link:
The representation of a fiber link (in a full wavelengthconvertible network) can be denoted as f (m, n, t, w, c)
• m and n : the end nodes of the fiber link
• t : fiber index (for numbering multiple fibers between the
same node pair)
• w : the available (free) wavelength channels on that fiber
• c : the administrative link cost.
28
Resource Discovery:
Link type(2/3)
• If there are multiple fibers between the
same node pair, they may be further
bundled.
• The purpose of link bundling is to improve
routing scalability by reducing the amount
of information that has to be handled by
the network control plane.
29
Resource Discovery:
Link type(3/3)
Virtual Link:
The representation of a lightpath can be denoted as l (i, j, v,
t, m1, m2, c)
• i and j : the end nodes of the lightpath
• v : the lightpath type
• t : the lightpath id
• m1:the minimal reservable bandwidth on this lightpath,
which is determined by the grooming ratio of the end
nodes
• m2 : the maximal reservable bandwidth on this
lightpath,which is bounded by the total available (free)
capacity on the lightpath
• C: denotes the administrative link cost.
30
Route Computation(1/2)
The route of a connection request will be
computed either by the source node of the request
or by the network control and management system.
Let Req(s, d, r) denote a connection request
s : the source node
d : the destination node
r : the capacity requirement of the connection.
31
Route Computation(2/2)
• Carry Req using an existing lightpath l(s, d, v, t,
m1, m2, c) between nodes s and d, if m1≤r ≤m2 .
• Carry Req using multiple existing groomable
lightpath.
• Carry Req by establishing a new lightpath
(either groomable or non-groomable) between
node pair (s, d) if enough resources exist.
• Carry Req using a combination of both existing
groomable lightpaths and setting up new
groomable lightpaths using available wavelength
channels in fiber links and grooming resources
in network nodes.
32
Signaling
• After a route is successfully computed,
every intermediate node along the route
needs to be informed through appropriate
signaling protocols.
33
A Generic Provisioning Model (1/10)
• A generic bandwidth-provisioning model,
which can incorporate various network
elements and accommodate different
grooming policies, will enable network
operators to manage their transport
networks easily and efficiently
34
A Generic Provisioning Model(2/10)
The graph is divided into four layers, namely access layer,
mux layer, grooming layer, and wavelength layer.
• The access layer : the access point of a connection
request, i.e., the point where a customer’s connection
starts and terminates. It can be an IP router, an ATM
switch, or any other client equipment.
• The mux layer : the OXC ports from which low-speed
traffic streams are directly multiplexed (de-multiplexed)
onto (from) wavelength channels without going through
the grooming fabric.
• The grooming layer : the grooming component of the
network node.
• The wavelength layer : the wavelength-switching
capability and the link state of wavelength channels.
35
A Generic Provisioning Model(3/10)
• A network node is divided into two vertices
at each layer.
• These two vertices represent the input and
output ports of the network node at that
layer.
36
37
A Generic Provisioning Model(4/10)
The links in this graph model are named and work
as follows.
1. Grooming switching link connects the input
port of the grooming layer to the output port of
the grooming layer at a given node i, when
node i has multi-hop traffic-grooming capability.
2. Wavelength switching link connects the input
port of the wavelength layer to the output port
of the wavelength layer at a given node i. It
represents the wavelength-switching capability
of the network node.
38
1
2
2
1
2
39
A Generic Provisioning Model(5/10)
3.Mux link connects the output port of the access layer to
the output port of the mux layer at a given node i.
It represents that the traffic starting from node i can be
packed to some wavelength channels and transmitted
to other network node together without going through
any grooming fabric.
4.Demux link connects input port of the mux layer to the
input port of the access layer at a given node i.
It represents that the traffic on a wavelength channel has
been de-multiplexed and terminated at this node without
going through any grooming fabric.
40
4
3
41
A Generic Provisioning Model(6/10)
5. Mux to wavelength transmitting link
connects the output port of the mux layer
to the output port of the wavelength layer
at a given node i.
6. Wavelength to mux receiving link is the
link which connects the input port of the
wavelength layer to the input port of the
mux layer at a given node i.
42
6
5
43
A Generic Provisioning Model(7/10)
7. Grooming link connects the output port of the access
layer to the output port of the grooming layer at a given
node i, when node i has multi-hop grooming capability
It represents that the traffic starting from node i can be
groomed with other traffic streams to the same
wavelength channel and transmitted to the next network
node together.
8. De-grooming link connects the input port of the grooming
layer to the input port of the access layer at a given node
i, when node i has multi-hop grooming capability.
It represents that the traffic on a wavelength channel have
been de-multiplexed, and then they may be either
terminated at node i or switched to other lightpaths.
44
8
7
45
A Generic Provisioning Model(8/10)
9. Grooming to wavelength transmitting link connects the
output port of the grooming layer to the output port of the
wavelength layer at a given node i, when node i has
multi-hop grooming capability .
It denotes that a multi-hop groomable lightpath (i.e., either
a source-groomable lightpath or a multi-hop fullgroomable lightpath) can be originated at node i.
10. Wavelength to grooming receiving link connects the
input port of the wavelength layer to the input port of the
grooming layer at a given node i, when node i has multihop grooming capability .
It denotes that a multi-hop groomable lightpath (i.e., either
a destination-groomable lightpath or a multi-hop fullgroomable lightpath) can be terminated at node i.
46
10
9
47
A Generic Provisioning Model(9/10)
11. Wavelength link connects the output port of the
wavelength layer at node i to the input port of the
wavelength layer at node j.
It denotes the availability of the wavelength
channels between node pair (i, j).
12.Lightpath link can start at the output port of the
mux layer (grooming layer) at node i, and
terminate at the input port of the mux layer
(grooming layer) at node j.
The four combinations of the end points represent
the four possible lightpath types between node
pair (i, j)
48
12
11
49
A Generic Provisioning Model(10/10)
• A link is removed if the corresponding network resource
is not available (e.g., deleting a wavelength link),
• A link is added if the corresponding network resource
becomes available from unavailable state (e.g., adding a
lightpath link).
• A customer’s connection request will always originate
from the output port of the access layer at the source
node and terminate at the input port of the access layer
at the destination node.
• After adjusting the administrative link cost, suitable
routes can be found according to different grooming
policies for a request by simply applying standard
shortest path route-computation algorithms.
• This strategy provides a platform for network operators
to realize different grooming policies, and eventually
improve the provisioning flexibility and network resource50
efficiency.
A sample network state and the
graph representation(1/3)
• Figures 2(a) and 2(b) show the network state for a
simple three-node network.
• The shaded node (node 0) is the node which employs a
multi-hop partial-grooming OXC and the un-shaded
nodes (nodes 1 and 2) are equipped with single-hop
grooming OXCs.
• Each link in Fig. 2(a) represents a free wavelength
channel between a node pair
• Each link in Fig. 2(b) represents an established lightpath.
The lightpath (0, 2) is a source-groomable lightpath
• The lightpath (1, 0) is a destination-groomable lightpath
The lightpath (2, 1) is a multi-hop un-groomable lightpath.
51
52
A sample network state and the
graph representation(2/3)
• A low-speed connection request from node
1 to node 2 can be carried by lightpaths (1,
0) and (0, 2).
• On the other hand, a request from node 2
to node 0 cannot traverse lightpaths (2, 1)
and (1, 0) since node 1 does not have
multi-hop grooming capability.
53
A sample network state and the
graph representation(3/3)
• By assigning proper weights to each link in
the graph in Fig. 2(c), the corresponding
routes will be computed through standard
shortest-path computation algorithms
according to different grooming policies.
54
A sample network 2(1/3)
• Figure 4 shows an example on how to
achieve different traffic-engineering
objectives through different grooming
policies by using our generic graph model.
55
56
A sample network 2(2/3)
• Assuming that there is a new traffic
request from node 1 to node 2, Fig. 4
shows two possible routes (in thick links)
for this connection request.
• The route shown in Fig. 4(a) traverses two
existing lightpath links,
• The route shown in Fig. 4(b) will employ
two new wavelength channels
57
A sample network 2(3/3)
• If the connection requires full wavelengthchannel capacity, or if the overall bandwidth
requirement of the future traffic demands
between the node pair is estimated to be close
to full wavelength-channel capacity, the route in
Fig. 4(b) is preferred since the wavelength
channels are fully utilized and no grooming is
needed at node 0;
• The route in Fig. 4(a) may be preferred if
enough free capacity is available in the existing
lightpaths.
58
Computational Complexity(1/2)
• The auxiliary graph will consist of 2x4xN nodes
and at most 2  4  N 2 links.
• The computation complexity for a standard
shortest-path algorithm in a N-node network is
O( N 2 )
• The computational complexity to provision a
connection request using this model in a full
wavelength-convertible WDM network is O( N 2 )
59
Computational Complexity(2/2)
• If the WDM network does not have full
wavelength-conversion capability, there will be
2 * (W  3) * N  nodes and at most 2 * (W  3) * N 2 links
in the auxiliary graph, where W is the number of
wavelength channels a fiber supports in the
network.
• The computational complexity to provision a
connection request using this model will be
O(W 2 N 2 ) in such a wavelength-continuous WDM
network
60
Illustrative Numerical
Examples(1/6)
• Figure.5 represents a typical operator’s
optical backbone network topology, which
has 24 nodes and 43 bi-directional links.
• The capacity of each wavelength channel
is OC-192.
61
62
Illustrative Numerical
Examples(2/6)
• The bandwidth requirements of the
connection requests follow an uniform
distribution between OC-3, OC-12, OC-48,
OC-192 (i.e., OC-3 : OC-12 : OC-48 : OC192 = 1 : 1 : 1 : 1)
• Connection requests are uniformly
distributed among all node pairs;
• The cost of a fiber link is modeled as unity;
63
Illustrative Numerical
Examples(3/6)
• We employ two metrics to evaluate the network
performance, namely Traffic Blocking Ratio
(TBR), Connection Blocking Probability (CBP).
Traffic Blocking Ratio represents the percentage
of the amount of blocked traffic over the amount
of bandwidth requirement of all traffic requests
during the entire simulation period.
• Connection Blocking Probability represents the
percentage of the total number of blocked
connection requests over the number of all traffic
requests during the entire simulation period.
64
Illustrative Numerical
Examples(4/6)
• In Configuration 1, all network nodes are only
equipped with single-hop grooming OXCs.
• In Configurations 2, 3, and 4, the shaded nodes
in Fig. 5 are equipped with multi-hop partialgrooming OXCs. The numbers of grooming ports
in multi-hop partial-grooming OXCs are 4, 8, and
16 in Configurations 2, 3, and 4, respectively.
• In Configuration 5, all shaded nodes in Fig. 5 are
equipped with multi-hop full-grooming OXCs
• Each bi-directional link in Fig. 5 contains two unidirectional fibers and each fiber supports eight
wavelength channels
65
66
67
Future work
• We observed that the unfairness problem
can become more severe when a network
has more grooming capability.
• This may lead to an interesting research
topic in our future work.
68