Transcript Constrained Optical Multicast Routing

APAN Network Research
Workshop 2007
Optical Multicasting for Interactive Real-time
Application in Sparse Splitting Optical Networks
Ju-Won Park, Hyunyong Lee, and JongWon Kim
2007/ 08/ 27
Networked Media Laboratory
Dept. of Information & Communications
Gwang-ju Institute of Science & Technology (GIST)
http://netmedia.gist.ac.kr
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Contents



Introduction
Related Work
Constrained Optical Multicast Routing




Problem statement
The proposed light-tree construction algorithm
Experiment Results
Conclusion
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Introduction
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Multicast over WDM networks

Multicast in IP over WDM Networks




IP layer multicast
Multicast via WDM unicast
WDM layer multicast
Multicast tree constructed by the IP layer can make
copies of a data packet and transmit a copy to each of its
child

Require O/E/O conversion



Undesirable
Inefficient
Long latency
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Multicast over WDM networks

Construct a virtual topology consisting of a set of lightpaths from the multicast
source to each destination (b)



WDM switches make copies of data packets in the optical domain via light
splitting (c)



Using multiple unicasts
Inefficient bandwidth – large multicast session
More desirable – transmission to different destinations can now share bandwidth on
common link
Useful to support high-bandwidth multicast application such as HDTV.
WDM layer multicast potential advantages




Knowledge of the physical topology – more efficient multicast routing is possible
Light splitting is more efficient than copying packets
Avoid the electronic processing bottleneck
Support of coding format and bit-rate transparency across both unicast and multicast
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Related Work
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Related Work




The main mechanism of transport over optical network is light-path, a point
to point all optical channel connecting from source to destination.
To incorporate optical multicasting capability, a light-tree, light-forest
concept is introduced.
The problem of constructing a light-tree that spans a given source and a set of
destinations is similar to the Steiner tree problem which is known to be NPcomplete
Consider several new issues and complexities for QoS provisioning of optical
multicasting



Sparse splitting (X. Zhang, J. Wei and C. Qiao, “Constrained Multicast Routing in WDM
Networks with Sparse Light Splitting,” in J. of Lightwave Technology, vol. 18, no. 12,
December 2002.)
Power constraint (Y. Xin and G. Rouskas, “Multicast routing under optical layer constraints,”
In Proc. of INFOCOM 2004)
Delay boundary (M. Chen, S.Tseng, B. Lin, “Dynamic multicast routing under delay
constraints in WDM networks with heterogeneous light splitting capabilities,” in Computer
Communications 29 (2006) 1492-1503)
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Constrained Optical Multicast
Routing
•Problem statement
•The proposed light-tree construction algorithm
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Problem Statement

Sparse splitting optical network




MC (multicast capability) node
MI (multicast in-capability) node
 D ( )
We define a delay function which assigns a
nonnegative weight to each link the network
To deliver interactive real-time application
via light-tree, we consider three parameters

Adequate signal quality – power constraint

End-to-end delay boundary
H T ( s ,v )
 D()  
H T ( s ,v )

inter-destination delay variation boundary

Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
H T ( s ,v )
D ( ) 
 D ( )  
H T ( s ,u )
Constrained Optical Multicast Routing

Goal




Every member of session is connected
Satisfy the delay and inter-destination delay variation
tolerance
Balanced tree to guarantee a certain level of optical signal
power
The way

Adopt hierarchical approach
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Constrained Optical Multicast Routing

Make multicast backbone network

Build the auxiliary MC network as referred as multicast
backbone network,



Every MC node is included.
Adjacent MC node is connected using logical link if there is available
wavelength on the path. If there are multiple path between MC nodes,
the shortest path is selected.
The delay of logical link is equal to the delay summation of path
D( H LTMC ( i , j ) ) 
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
 D ( )
H LTMC ( i , j )
Constrained Optical Multicast Routing
Multicast Backbone Networks
(MC network, G’)
1
Physical Network
(MC & MI network, G)
MC node
1
1
MI node
1
Source of session 1
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
1
1
Source
1
Destination
Constrained Optical Multicast Routing

Build the light-tree based on application requirement

Source searches the MC node which is nearest from source
as referred to primary MC node.


The primary MC node is unique of each session
Build the light-tree which has primary MC node as root in
multicast backbone network based on constraints.
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Constrained Optical Multicast Routing
Primary MC Node
of session 1
Multicast Backbone Networks
Build the light-tree based on application
requirement in MC network
(MC network, G’)
1
Physical Network
(MC & MI network, G)
MC node
1
1
MI node
1
Source of session 1
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
1
1
Source
1
Destination
Constrained Optical Multicast Routing

Each destination selects a adequate MC node


The MC selection by receiver is a key to construct feasible light-tree
Each MI node finds the subset of on-tree MC nodes which satisfy the
delay boundary
 D()    D( )  
H LTMC ( s ,i )

H LT ( i ,k )
MI node chooses the MC node which has minimum fanout in subset and
then, join the light-tree by connection with selected MC node
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Constrained Optical Multicast Routing
Primary MC Node
of session 1
Multicast Backbone Networks
Build the light-tree based on application
requirement in MC network
(MC network, G’)
1
Physical Network
(MC & MI network, G)
MC node
1
1
MI node
1
Source of session 1
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
1
1
Source
1
Destination
Constrained Optical Multicast Routing



Completed light-tree meets the delay boundary with balanced
aspect.
It does not satisfy the inter-destination delay variation boundary.
Reduce the inter-destination delay variation by swapping MI
nodes
 max  max
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST

H LT ( s ,v )
D ( ) 
 D ( )
H LT ( s ,u )
Constrained Optical Multicast Routing
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Constrained Optical Multicast Routing

Advantages

Source need not know about the location of destinations.


Simple construction of member-only light-tree


Every destination need not find the minimum cost path from itself to
source. It just must find the location of MC node which satisfies
application requirement.
The procedure of joining the light-tree is only performed at member.
The procedure of dynamic addition or deletion of members in
a group is simple.


Join: The node which wants to join in the multicast session can be
connected to its nearest MC node.
Leave: The node which wants to leave can be disconnected send the
prune message to connected MC node.
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Experiment Results
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Experiment Results
Inter-destination delay variation (ms)
240
220
200
180
160
140
120
100
80
Shortest path approach
Balanced approach (LT0)
60
Proposed approach
40
0
20
40
60
80
The number of MI nodes
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
100
120
140
Experiment Results
500
Shortest path approach
Balanced approach, proposed approach
Maximum Split Ratio
400
300
200
100
0
0
20
40
60
80
Number of MI nodes
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
100
120
140
Conclusion
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Conclusion & Future Work

To support multicast in optical network


a balanced light-tree to guarantee signal quality
Delay and inter-destination delay variation along all source-destination
paths in the tree should be bounded in sparse splitting optical network.

The proposed algorithm is heuristic approach to obtain the
feasible light-tree

Wavelength assignment algorithm should be explored in future
research.

Minimize wavelength cost
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST
Q&A
Networked Media Lab.
DEPT. OF INFO. & COMM., GIST