Information Technology Reference
In-Depth Information
algorithms. Though the first pursues an optimal solution, it is sometimes impractical
due to its NP-hard nature. Thus the second approach can be a feasible alternative in-
stead. Some metaheuristics for the delay-constrained or more constraint multicast rout-
ing problems have been studied in the literature [12-15]. The simulation results given
by Salama et al. [16] have shown that most of the metaheuristic algorithms either work
too slowly or cannot compute the delay constrained multicast tree with least cost.
6.1 Problem Formulation of QoS Based Multicast Routing
Communication networks consist of nodes connected via links. The nodes are the
originators and receivers of information, while the links serve as the transport between
nodes. A network is modeled as a directed weighted graph G=(V, E) where V is a finite
set of nodes representing routers or switches and E is a set of edges representing com-
munication links between network nodes. Three non-negative real-valued functions are
associated with each link e(e
E ): cost C (e): E→R + , delay D (e): E→R + , and available
bandwidth B (e): E→R + . Function D (e) represents the delay that the packet experiences
on a link including queuing, transmission, and propagation delay and B (e) is band-
width where C (e) defines the link cost function. C (e) defines the measure we want to
optimize (minimize), D (e)and B (e) define the criteria we want to constrain (bound).
A multicast tree
T
(
s
,
D
)
is a tree routed at s and spanning all members of
{}
s
D
as the multicast
group . Furthermore, the multicast tree may contain relay nodes, called Steiner nodes .
The Steiner node is a node that belongs to the multicast tree but not to the multicast
group. Let
D
V
s
. We refer to D as the destination group and
P T
(
s
,
d
)
be a unique path in the tree T from the source node s to a destina-
tion node
d
D
. The cost of the tree
T
(
s
,
D
)
is the sum of the costs of all links in
that tree and is as follow:
(16)
Cost T
()
=
C e
()
eT sD
(, )
The total path delay from s to any destination d , is simply the sum of the delay of
edges along
P T
(
s
,
d
)
, i.e.
(17)
Delay
((,
P
s d
)
=
D e
()
T
eP sd
(, )
T
The bottleneck bandwidth of the path from s to any destination d , denoted by
Bandwidth(
P T
(
s
,
d
)
) is defined as the minimum available residual bandwidth at any
link along the path:
BandwidthPsd
(
( ,
) )
=
min{
Bee Psd
( ),
( ,
)}
(18)
T
T
to
represent the bandwidth constraint of the destination node d in a multicast tree T .
Based on these definitions, the bandwidth-delay constrained least-cost multicast prob-
lem is defined as minimization of Cost ( T ) subject to:
(
For notational convenience, we use
Δ
to represent delay constraint and
β
d
d
Delay
P
( ,
s d
) )
≤Δ
,
d
D
T
Bandwidth P
d
(19)
((,
s d
)
β
,
d
D
T
d
Search WWH ::




Custom Search