Table 1
Lightpath-Based Minimum-Cost Groupcast RWA Algorithm (MC_GCRWA)
| |
---|
Step 1
| Given a network
and a group of nodes
, choose
and compute the MCP from
to all other nodes
. |
Step 2
| Store the routes found in Step 1 in
. |
Step 3
| Repeat Steps 1 and 2 for all members of the group
and construct the light-forest matrix:
The light-forest F consists of k light-trees, where light-tree
is represented by the row-vector
. Note that row-vector
has
routes, as no loopback route is allowed. |
Step 4
| Return light-forest F to wavelength assignment function. |
Step 5
| Choose the route
represented by the link set array
, and find a free wavelength
,
, where W represents the total number of wavelengths per fiber in the network. |
Step 6
| Mark the wavelength
chosen in Step 5 as unavailable in all links from the link set
. |
Step 7
| Repeat Steps 5 and 6 for all elements of F or lightpaths represented by
where
. |
Table 2
Lightpath-Based Minimum-Cost Multicast RWA Algorithm (MC_MCRWA)
| |
---|
Step 1
| Given a network
and a group of nodes
, choose
and compute the MCP from
to all other nodes
. |
Step 2
| Store the routes found in Step 1 in
. |
Step 3
| Choose the route
represented by the link set array
, and find a free wavelength
, where W represents the total number of wavelengths per fiber in the network. |
Step 4
| Mark the
chosen in Step 3 as unavailable in all links from the link set
. |
Step 5
| Repeat Steps 3 and 4 for all elements of R or lightpaths represented by
where
. |
Table 3
Lightpath-Based MHP GC-RWA Algorithm (MHP_GCRWA)
| |
---|
Step 1
| Given a network
and a group of nodes
, choose
and compute shortest path from
to all other nodes
based on hop counts. |
Step 2
| Store the routes found in Step 1 in
. |
Step 3
| Repeat Steps 1 and 2 for all members of the group
and construct the light-forest matrix:
The light-forest F consists of k light-trees, where light-tree
is represented by the row-vector
. Note that row-vector
has
routes, as no loopback route is allowed. |
Step 4
| Return light-forest F to wavelength assignment function. |
Step 5
| Choose the route
represented by the link set array
, and find a free wavelength
, where W represents the total number of wavelengths per fiber in the network. |
Step 6
| Mark the wavelength
chosen in Step 5 as unavailable in all links from the link set
. |
Step 7
| Repeat Steps 5 and 6 for all elements of F or lightpaths represented by
where
. |
Table 4
Lightpath-Based Groupcast With No Wavelength Conversion: Optical Groupcast Heuristic for Monocolor Light-Trees
| |
---|
Step 1
| Given a network
and a list of groupcast sessions S, choose the first session
. |
Step 2
| Begin with
and compute shortest lightpaths from
to all nodes
based on hop counts. Construct light-tree
with source node
. |
Step 3
| Find a wavelength
from W wavelengths such that all lightpaths from Step 2 can be served. Mark wavelength
as used along the lightpaths for light-tree
. |
Step 4
| Repeat Steps 2 and 3 for all nodes in Session
until all nodes are served (a total of k light-trees.) |
Step 5
| Repeat Steps 1–4 until all sessions in S are served (a total of
light-forests.) |
Table 5
Lightpath-Based Groupcast With No Wavelength Conversion: Optical Groupcast Heuristic for Multicolor Light-Trees
| |
---|
Step 1
| Given a set of groupcast sessions
, where g is the number of sessions, construct a list
by decomposing each session into multiple point-to-point source–destination pairs. |
Step 2
| Choose sequentially a wavelength
and construct graph
to find the lightpath to serve the first session from list Λ. |
Step 3
| Mark the wavelength
as used along the lightpath. If the lightpath is not found, choose the next wavelength in Step
2 and repeat Step 2 until the session is served. |
Step 4
| Repeat Step 3 for all sessions until list Λ is completed. |
Table 6
Lightpath-Based Groupcast With Wavelength Conversion for Rainbow Light-Trees: Optical Groupcast Heuristic for Rainbow Light-Forests
| |
---|
Step 1
| Given a network
and a list of groupcast sessions
, where g is the number of sessions, construct a list Λ by decomposing each session into multiple point-to-point source–destination sessions. |
Step 2
| Compute shortest lightpath for each session in Λ. |
Step 3
| Make a link set
required in order to construct the lightpath to serve session
. Find a wavelength
from W wavelengths for each link in
. |
Step 4
| Mark each wavelength assigned
for the link set
. |
Step 5
| Repeat Steps 2–4 until all sessions in Λ are served. |
Table 7
Layered-Graph-Based Groupcasting for Wavelength-Continuous OXC-Based Networks: Wavelength-Optimized Optical Groupcast Heuristic
| |
---|
Step 1
| Given a network
and a list of groupcast sessions
, where g is the number of sessions, construct a list Λ by decomposing each session into multiple point-to-point source–destination sessions. |
Step 2
| Compute shortest lightpath for each session in Λ and sort it based on cost or hop counts. It must be sorted in ascending or descending order. For random heuristic the sorting is done in a random fashion. |
Step 3
| Choose sequentially a wavelength
from W wavelengths and construct a new graph
. Choose a session from Step 2 and compute the lightpath to serve it. Mark the wavelength
as used along the lightpath. |
Step 4
| Repeat Step 3 for all sessions until Λ is completed. |
Table 8
Routing Algorithms to Build Groupcast Light-Forest
Step | Lightpath-Based | Light-Tree-Based |
---|
1 | Calculate all pairs of minimum cost paths (MCH) and store the paths in a table. | Calculate all pairs of minimum cost paths (MCH) and store the paths in a table. |
2 | For a groupcast call, find the shortest paths from one group participant to all other group members (set of lightpaths). Repeat the process until all group members are served (make light-forest). | For a groupcast call, find and combine the shortest paths from one group participant to all other group members (make light-tree). Repeat the process until all the group members are served (make light-forest). |
3 | Find wavelengths for each lightpath until the complete light-forest is illuminated. | Find wavelengths for each light-tree until the complete light-forest is illuminated. |
Table 9
Light-Tree-Based Groupcasts With No Wavelength Conversion: Cost Optimization Heuristic for Groupcast in MC-OXC Networks
| |
---|
Step 1
| Given a groupcast session list with g sessions, select the first groupcast session. |
Step 2
| For groupcast size k, generate k multicast trees using the Steiner tree MCH. |
Step 3
| Index each tree found in Step 2 in terms of source (s), destinations (d), cost (c), and wavelength (w) in the session list
. |
Step 4
| Repeat Steps 2 and 3 until all of the g groupcast sessions are served. Sort the sessions in S based on destination group size or session cost (or randomly). |
Step 5
| Select the first session from list S. |
Step 6
| Choose the first wavelength
from the W-wavelength list and construct a graph
based on the wavelength availability per link. If the wavelength is unavailable, the link is removed from the original physical graph G. |
Step 7
| Route the
session on graph
from Step 6 by using the Steiner tree MCH. If the routing is successful, assign wavelengths to the links selected during multicast tree construction and update the cost
in the
list. If the multicast routing fails, increment the wavelength
and go to Step 6. |
Step 8
| Repeat Steps 6 and 7 until all sessions from list
are served. |
Step 9
| Compute the total cost of the sessions using
. |