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

Dinh Danh Le; Fen Zhou; Miklós Molnár

doi:10.1364/JOCN.7.000036

Journal of Optical Communications and Networking
Vol. 7,
Issue 1,
pp. 36-48
(2015)
•https://doi.org/10.1364/JOCN.7.000036

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

Not Accessible

Your library or personal account may give you access

Get PDF
Email
Share
Get Citation
Copy Citation Text
Dinh Danh Le, Fen Zhou, and Miklós Molnár, "Minimizing Blocking Probability for the Multicast Routing and Wavelength Assignment Problem in WDM Networks: Exact Solutions and Heuristic Algorithms," J. Opt. Commun. Netw. 7, 36-48 (2015)

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

Abstract

Given a sparse splitting wavelength division multiplexing (WDM) network and a set of available wavelengths, we investigate the problem of provisioning a set of multicast requests simultaneously with the objective of minimizing the blocking probability. Two blocking models are taken into account: full blocking probability and partial blocking probability. As the problem is NP-hard, we propose an integer linear programming (ILP) formulation with two variants (each for a blocking model) to search for the optimal solution and several efficient adaptive heuristic algorithms to compute approximated solutions. In particular, instead of using light-trees, both ILP and heuristics use light-hierarchy, a recently proposed optimal route under sparse splitting configurations. Extensive simulations reveal that our adaptive algorithms are able to compute near-optimal solutions, and they outperform static approaches under both blocking probability models. The results also show that it is more advantageous to provision multiple multicast communications with light-hierarchies, since they are able to accommodate more requests and destinations compared to the light-tree solutions.

Full Article | PDF Article

More Like This

Slotted Advance Reservation for Multicast-Incapable Optical Wavelength Division Multiplexing Networks

Arush Gadkar, Tim Entel, Jeremy M. Plante, and Vinod M. Vokkarane
J. Opt. Commun. Netw. 6(3) 340-354 (2014)

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

Neal Charbonneau and Vinod M. Vokkarane
J. Opt. Commun. Netw. 2(7) 442-455 (2010)

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 (7)

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 (5)

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 (24)

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

$G$	A digraph representing the WDM network
$V$	A set of OXCs in the network
$E$	A set of fibers connecting OXCs in the network
$R$	A set of multicast requests
$W$	The set of wavelengths supported per fiber
$λ$	A wavelength, $λ \in W$
$N^{+} (v)$	Extremities of the outgoing arcs from OXC $v$
$N^{-} (v)$	Extremities of the incoming arcs to OXC $v$
Deg	The maximum nodal degree in $G$
$(u, v)$	The arc from OXC $u$ to $v$
$c_{u v}$	The cost of the arc from OXC $u$ to $v$
$Δ$	An integer big enough such that $Δ > \| W \| \times \sum_{(u, v) \in E} c_{u v}$
MC	The set of MC-OXCs in $G$
MI	The set of MI-OXCs in $G$
$i \in I$	The index $i$ and the index set $I$ of $R$
$f_{i}$	The importance of multicast request $r_{i}$

$L_{u v}^{i λ} \in {0,1}$	Equals 1 if multicast request $r_{i}$ uses wavelength $λ$ on link $(u, v)$ ; equals 0 otherwise
$F_{u v}^{i λ} \in [D_{i}]$	Commodity flow; denotes the number of destinations in request $r_{i}$ receiving a flow from $s_{i}$ via arc $(u, v)$ on $λ$
$B_{i} \in {0,1}$	Equals 1 if request $r_{i}$ is accepted; 0 otherwise
$B_{i}^{d} \in {0,1}$	Equals 1 if destination $d$ of request $r_{i}$ is accepted; 0 otherwise

		$\| W \| = 1$		$\| W \| = 2$		$\| W \| = 3$		Avg. Ratio
	Algorithms	$S = 0$	$S = 3$	$S = 0$	$S = 3$	$S = 0$	$S = 3$	$S = 0$	$S = 3$
SBP (%)	MO-FIX	80	73	64	63	43	50	2.2	2.4
	MO-ALT	79	72	61	59	37	47	2.1	2.3
	SeqR	74	65	46	36	21	14	1.7	1.5
	SRF	62	60	40	36	17	13	1.4	1.4
	LRF	79	77	53	46	23	21	1.8	1.8
	ILP	58	52	24	22	2	4	1.0*	1.0*
DBP (%)	MO-FIX	80.5	80.7	65.9	65.2	44.1	54.3	2.6	2.8
	MO-ALT	77.1	78.4	61.3	63	38.5	46.7	2.4	2.6
	SeqR	61.9	60.5	33.5	31.1	11.1	5.9	1.4	1.4
	SRF	68.7	68.5	38.8	35.2	10.1	4.1	1.6	1.5
	LRF	58.9	56.9	28.5	24	6.7	4.3	1.3	1.2
	ILP	54	54.3	19.1	15.2	1.2	1.7	1.0*	1.0*

$G$	A digraph representing the WDM network
$V$	A set of OXCs in the network
$E$	A set of fibers connecting OXCs in the network
$R$	A set of multicast requests
$W$	The set of wavelengths supported per fiber
$λ$	A wavelength, $λ \in W$
$N^{+} (v)$	Extremities of the outgoing arcs from OXC $v$
$N^{-} (v)$	Extremities of the incoming arcs to OXC $v$
Deg	The maximum nodal degree in $G$
$(u, v)$	The arc from OXC $u$ to $v$
$c_{u v}$	The cost of the arc from OXC $u$ to $v$
$Δ$	An integer big enough such that $Δ > \| W \| \times \sum_{(u, v) \in E} c_{u v}$
MC	The set of MC-OXCs in $G$
MI	The set of MI-OXCs in $G$
$i \in I$	The index $i$ and the index set $I$ of $R$
$f_{i}$	The importance of multicast request $r_{i}$

$L_{u v}^{i λ} \in {0,1}$	Equals 1 if multicast request $r_{i}$ uses wavelength $λ$ on link $(u, v)$ ; equals 0 otherwise
$F_{u v}^{i λ} \in [D_{i}]$	Commodity flow; denotes the number of destinations in request $r_{i}$ receiving a flow from $s_{i}$ via arc $(u, v)$ on $λ$
$B_{i} \in {0,1}$	Equals 1 if request $r_{i}$ is accepted; 0 otherwise
$B_{i}^{d} \in {0,1}$	Equals 1 if destination $d$ of request $r_{i}$ is accepted; 0 otherwise

Abstract

Cited By

Figures (7)

Tables (5)

Equations (24)

Journal of Optical Communications and Networking