Routing and Wavelength Assignment of Static Manycast Demands Over All-Optical Wavelength-Routed WDM Networks

Neal Charbonneau; Vinod M. Vokkarane

doi:10.1364/JOCN.2.000442

Journal of Optical Communications and Networking
Vol. 2,
Issue 7,
pp. 442-455
(2010)
•https://doi.org/10.1364/JOCN.2.000442

Routing and Wavelength Assignment of Static Manycast Demands Over All-Optical Wavelength-Routed WDM Networks

Neal Charbonneau and Vinod M. Vokkarane

Not Accessible

Your library or personal account may give you access

Get PDF
Email
Share
Get Citation
Copy Citation Text
Neal Charbonneau and Vinod M. Vokkarane, "Routing and Wavelength Assignment of Static Manycast Demands Over All-Optical Wavelength-Routed WDM Networks," J. Opt. Commun. Netw. 2, 442-455 (2010)

Export Citation
- BibTex
- Endnote (RIS)
- HTML
- Plain Text
Citation alert
Save article

Abstract

In this paper we present the static manycast routing and wavelength assignment (MA-RWA) problem along with heuristics and an integer linear program (ILP) to solve it. Manycast is a point-to-multipoint communication paradigm with applications in e-Science, Grid, and cloud computing. A manycast request specifies a candidate set of destinations, of which a subset must be reached. To solve MA-RWA, a light-tree must be assigned to each manycast request in a static set such that the number of wavelengths required is minimized. We present two heuristics, the shortest path heuristic (SPT) and the lambda path heuristic (LPH), a tabu search meta-heuristic (TS), and an ILP formulation. We show that TS provides results close to the optimal solution (from the ILP) for small networks. We then show that TS provides a 10% improvement over LPH and a 30%–40% improvement over SPT for various realistic networks.

Full Article | PDF Article

More Like This

Quality-of-Transmission-Aware Manycasting Over Optical Burst-Switched Networks

Balagangadhar G. Bathula, Rajesh R.C. Bikram, Vinod M. Vokkarane, and Srinivas Talabattula
J. Opt. Commun. Netw. 2(10) 820-830 (2010)

Minimizing Blocking Probability for the Multicast Routing and Wavelength Assignment Problem in WDM Networks: Exact Solutions and Heuristic Algorithms

Dinh Danh Le, Fen Zhou, and Miklós Molnár
J. Opt. Commun. Netw. 7(1) 36-48 (2015)

Multicast Overlay for High-Bandwidth Applications Over Optical WDM Networks

Arush Gadkar, Jeremy Plante, and Vinod M. Vokkarane
J. Opt. Commun. Netw. 4(8) 571-585 (2012)

Previous Article Next Article

Cited By

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Figures (8)

You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Tables (3)

You do not have subscription access to this journal. Article tables are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Equations (12)

You do not have subscription access to this journal. Equations are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Network	V	E	δ	τ	$D_{\max} = 6$						$D_{\max} = 8$						$D_{\max} = 10$
					TS		LPH		SPT		TS		LPH		SPT		TS		LPH		SPT
					$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$
AT&T	27	41	3.0	3.4	28.8	11.7	32.5	11.6	43.9	11.2	30.2	11.3	34.5	11.3	47.1	10.8	31.6	11.4	35.8	11.4	47.6	10.7
NSFnet	14	21	3.0	4.3	32.9	9.6	36.7	9.4	46.4	8.6	35.8	9.6	39.6	9.5	49.6	8.4	39.3	9.8	43.0	9.6	55.1	8.4
Italy	21	36	3.4	0.6	29.4	1.7	33.3	1.7	47.0	1.5	31.9	1.8	35.9	1.7	50.8	1.6	33.3	1.8	37.5	1.7	51.5	1.5
24 node	24	43	3.6	3.9	25.5	11.6	28.6	11.4	37.7	10.6	26.8	11.5	30.5	11.3	40.0	10.3	28.4	11.5	32.2	11.4	42.3	10.2

Network	V	E	δ	τ	$D_{\max} = 6$						$D_{\max} = 8$						$D_{\max} = 10$
					TS		LPH		SPT		TS		LPH		SPT		TS		LPH		SPT
					$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$	$w_{a}$	$d_{a}$
AT&T	27	41	3.0	3.4	28.8	11.7	32.5	11.6	43.9	11.2	30.2	11.3	34.5	11.3	47.1	10.8	31.6	11.4	35.8	11.4	47.6	10.7
NSFnet	14	21	3.0	4.3	32.9	9.6	36.7	9.4	46.4	8.6	35.8	9.6	39.6	9.5	49.6	8.4	39.3	9.8	43.0	9.6	55.1	8.4
Italy	21	36	3.4	0.6	29.4	1.7	33.3	1.7	47.0	1.5	31.9	1.8	35.9	1.7	50.8	1.6	33.3	1.8	37.5	1.7	51.5	1.5
24 node	24	43	3.6	3.9	25.5	11.6	28.6	11.4	37.7	10.6	26.8	11.5	30.5	11.3	40.0	10.3	28.4	11.5	32.2	11.4	42.3	10.2


1: $sort_desc (M)$
2: for all m in M do
3: $D = kShortest (D_{m c})$
4: $T = (V^{'}, E^{'})$ s.t. $V^{'} = {s_{m}}$ , $E^{'} = ϕ$
5: $path = \min {SP (s_{m}, u)}$ $u ∊ D$
6: $Update (T, path)$
7: $copy = 1$
8: while $copy < k$ do
9: $path = \min {SP (u_{1}, u_{2})}$ $u_{1} ∊ V^{'}$ , $u_{2} ∊ D - V^{'}$
10: $Update (T, path)$
11: $copy = copy + 1$
12: end while
13: $T . cost = \sum_{i, j ∊ E^{'}} c_{i, j}$
14: $FirstFit (G, T)$
15: end for


1: $sort_desc (M)$
2: for all m in M do
3: $D = {}$
4: $allTrees = list ()$
5: while $D_{m c} - D \neq ϕ$ do
6: $T = (V^{'}, E^{'})$ s.t. $V^{'} = {s_{m}}$ , $E^{'} = ϕ$
7: $path = \min {SP (s_{m}, u)}$ $u ∊ D_{m c} - D$
8: $Update (T, path)$
9: $D = \cup (u)$
10: $copy = 1$
11: while $copy < k$ do
12: $path = \min {SP (u_{1}, u_{2})}$ $u_{1} ∊ V^{'}$ , $u_{2} ∊ D_{m c} - V^{'}$
13: $Update (T, path)$
14: $copy = copy + 1$
15: end while
16: $T . cost = \sum_{i, j ∊ E^{'}} c_{i, j}$
17: $T . newWL = increasesWL (G, T)$
18: $allTrees . append (T)$
19: end while
20: $T = \min (allTrees)$
21: $FirstFit (G, T)$
22: $updateWeights (α, 1 - α)$
23: end for


1: $sort_desc (M)$
2: for all m in M do
3: $D = kShortest (D_{m c})$
4: $T = (V^{'}, E^{'})$ s.t. $V^{'} = {s_{m}}$ , $E^{'} = ϕ$
5: $path = \min {SP (s_{m}, u)}$ $u ∊ D$
6: $Update (T, path)$
7: $copy = 1$
8: while $copy < k$ do
9: $path = \min {SP (u_{1}, u_{2})}$ $u_{1} ∊ V^{'}$ , $u_{2} ∊ D - V^{'}$
10: $Update (T, path)$
11: $copy = copy + 1$
12: end while
13: $T . cost = \sum_{i, j ∊ E^{'}} c_{i, j}$
14: $FirstFit (G, T)$
15: end for


1: $sort_desc (M)$
2: for all m in M do
3: $D = {}$
4: $allTrees = list ()$
5: while $D_{m c} - D \neq ϕ$ do
6: $T = (V^{'}, E^{'})$ s.t. $V^{'} = {s_{m}}$ , $E^{'} = ϕ$
7: $path = \min {SP (s_{m}, u)}$ $u ∊ D_{m c} - D$
8: $Update (T, path)$
9: $D = \cup (u)$
10: $copy = 1$
11: while $copy < k$ do
12: $path = \min {SP (u_{1}, u_{2})}$ $u_{1} ∊ V^{'}$ , $u_{2} ∊ D_{m c} - V^{'}$
13: $Update (T, path)$
14: $copy = copy + 1$
15: end while
16: $T . cost = \sum_{i, j ∊ E^{'}} c_{i, j}$
17: $T . newWL = increasesWL (G, T)$
18: $allTrees . append (T)$
19: end while
20: $T = \min (allTrees)$
21: $FirstFit (G, T)$
22: $updateWeights (α, 1 - α)$
23: end for

Abstract

Cited By

Figures (8)

Tables (3)

Equations (12)

Journal of Optical Communications and Networking