A STUDY OF QUALITY·OFSERVICE ROUTING
By
ZHENTAOLI
Bachelor of Science
Beijing Institute of Technology
Beijing, Chma
1992
Submitted to the Faculty of the
Graduate College of the
Oklahoma State University
in partial fulfillment of
the requirements for
the Degree of
MASTER OF SCIENCE
May 2003
Ok/ahoma State University Library
A STUDY OF QUALITYOFSERVICE ROUTING
Thesis APpr~
Thesis Adviser
\l~
11
PREFACE
QualityofService lQoS) is a key issue in fOuting. Finding a path with
guaranteed QoS is one of the major routing problems. However, finding a palh with
more than one additive constraints is NPhard. Few studies were done on more than two
constraints.
The objective of this thesis is to study the QoS routing problem with three
constraints: cost, delay, and bandwidth. Three heuristic algorithms were developed bascd
on Dijkstra's algorithm, BellmanFord algorithm, and Linear Lagrange Relaxation. The
run time of these three heuristics is polynomial. After evaluated the performance of each
heuristic, some recommendations are given on selecting heuristics under certain
circumstances.
1ll
ACKNOWLEDGMENTS
I would like 10 express my sincere appreciation to my major professor, Dr. H. K.
Dai, for his guidance, assistance, and kindness in completing my thesis. I also want to
extend my sincere appreciatioll Lo Dr. George E. Hedrick and Dr. John P. Chandler for
their advice and will ingness to serve on my graduate committee.
I also would like (0 extend special appreciation to my parents, who always
believed in my abilities, for their moral and financial support and encouragemenl and me.
Without their support and encouragement, I would not have been finished the graduate
study.
Finally, f want to thank all my friends and colleagues for their valuable
suggestions.
IV
Chapter
TABLE OF CONTENTS
Page
I Introduction 1
II Preliminaries and DefInitions 3
III Relevant Work 6
3.1 Source Routing Algorithms 7
3.1.1 Unicast Routing Problems 7
3.1.2 Multicast Routing Problems 8
3.1.3 Hierarchical Routing Problems 10
3.2 Distributed Routing Algorithms 11
3.2.1 Unicast Routing Problems 11
3.2.2 Multicast Routing Problems 12
IV Heuristic Based on Dijkstra's Algorithm 14
4.1 Dijkstra's Algorithm 14
4.2 A New Heuristic Developed from Dijkstra's Algorithm 17
V Heuristic Based on the BellmanFordMoore Algorithm 25
5.1 BellmanFordMoor Algoritlun 25
5.2 A New Heuristic Developed from BFM Algorithm 30
VI Heuristic Based on Linear Lagrange Relaxtion 38
6.1 Linear Lagrange Relaxtion 38
6.2 A New Heuristic Developed from Linear Lagrange Relaxtion .40
VII Results and Analysis .44
7.1 Testing Graphs 44
7.1.1 Regular Graph 44
7.1.2 Irregular Graph 45
7.1.3 Parameters for Generated Graphs 46
7.2 Comparison of Dijkstra Based, BFM Based, and LR Based Heuristics 47
7.2.1 Results for Case 1 47
7.2.2 Results for Case 2 51
7.2.3 Results for Case 3 54
VIII Conclusions and Future Work. 56
References 60
Appendix A 63
v
LIST OF TABLES
Table Page
Table 71 Regular Graph with Randomly Generated Cost, Delay, and
Bandwidth 48
Table 72 Regular Graph with Related Cost, Delay, and Bandwidth 51
Table 73 Irregular Graph with Related Cost, Delay, and Bandwidth 54
VI
Figure
LIST OF FIGURES
Page
Figure 41. Dijkstra's Algorithm .." j()
Figure 42. Heuristic for the BD_CB_LC Problem Based on Dijkstra's
Algorithm 19
Figure 43. An Example of Network with Cost, Delay, and Bandwidth 20
Figure 44. Initialization 2D
Figure 45. Iteration 1 2 i
Figure 46. Iteration 2 21
Figure 47. Iteration 3 22
Figure 48. Iteration 4 ' 22
Figure 49. Iteration 5 23
Figure 410. Procedure for Path Trace 23
Figure 51. The BFM Algorithm 26
Figure 52. An Example of Network with Cost.. 27
Figure 53. Initialization , 28
Figure 54. Sweep 1 28
Figure 55. Sweep 2 29
Figure 56. Sweep 3 29
Figure 57. Sweep 4 30
Figure 58. Heuristic for the BD CB LC Problem Based on the BFM
Algorithm 32
Figure 59. An Example of Network with Cost, Delay, and Bandwidth 33
Figure 510. Initialization 33
Figure 511. Sweep 1 34
Figure 512. Sweep 2 34
Figure 513. Sweep 3 35
Vll
Figure 514.
Figure 515.
Figure 516.
Figure 61.
Figure 62.
Figure 71.
Figure 72.
Figure 73.
Figure 74.
Figure 75.
Figure 76.
Sweep 4 35
Sweep 5 36
Procedure for Path Trace 37
Heuristic for the BD_CB_LC Problem Based on Lagrange
Relaxation 42
Function of Reduce Network .43
An Example of Regular Graph .45
Comparison of Search Time for Regular Graph with
Randomly Generated Cost, Delay, and Bandwidth 49
Comparison of Least Cost for Regular Graph with Randomly
Generated Cost, Delay, and Bandwidth 50
Comparison of Search Time for Regular Graph with Related
Cost, Delay, and Bandwidth 52
Comparison of Least Cost for Regular Graph with Related
Cost, Delay, and Bandwidth 53
Comparison of Search Time for Irregular Graph with Related
Cost, Delay, and Bandwidth 55
Vlll
Chapter I
Introduction
In today's computer networks, routing is primari ly concerned with connectivity.
Routing protocols usually characterize the network with a single metric such as hopcount
or delay, and use shortestpath algorithms for path computation. However, such
routing protocols are not satisfied for multimedia applications, such as video
conferencing, which often require guaranteed and stringent qualityofservice (QoS). The
notion of QoS is proposed to capture the qualitatively or quantitatively defined
perfonnance contract between the service provider and the user applications [1]. To
achieve this goal, routing protocol should have a more complex model of the network,
taking into account important network parameters, such as bandwidth, delay, and loss
probability.
The basic work of QoS routing is to find a path that satisfies multiple constraints.
The constraints can be link constraints, path constraints, or tree constraints [2]. A link
constraint specifies a restriction on the use of links. A bandwidth constraint of a unicast
connection requires, for example, that the links composing the path must have certain
amount of free bandwidth available. A path constraint specifies the endtoend QoS
requirement on a single path. For example, the delay constraint of a unicast connection
requires the delay from the source to the destination cannot exceed an upper bound. A
tree constraint specifies the QoS requirement for the entire multicast tree.
I
A path that has sufficient residual (unused) resources to satisfy the QoS
constraints of a connection is called a feasible path. The basic aim of QoS routing is to
find such a feasible path. In addition, optimization 0 f resource utilization measured by an
abstract metric, cost, is often considered. The cost of a link can be defined in dollars or
as a function of the buffer or bandwidth utilization. The cost of a path is the total cost of
aU links on the path. The optimization problem is to find the lowestcost path among all
feasible paths. This thesis aims at developing new routing algorithms to find paths with
more than one constraint.
The rest of this thesis is organized as follows: Chapter II introduces some
preliminaries of constraint selection in QoS routing. Chapter III discusses existing
routing algorithms for QoS routing. In Chapter IV, V, and VI, three new heuristic
algorithms are developed based on Dijkstra's algorithm, BellmanFord algorithm, and
Linear Lagrange Relaxation, respectively. Chapter vn is the simulation and results.
Chapter VIn concludes this thesis and points out certain directions for further research.
2
Chapter II
Preliminaries and Definitions
Definition: Let a pointtopoint communication network be represented as a
directed graph N = (V, E), where V is the set of nodes, and E is the set of links in N. A
link directed from node u to node v is denoted by e = (u, v). Then a path P from node Vo
to node Vb denoted by P(vo, vk), is defined as an alternating sequence (vo, e., VI> e2, ... , ek,
Vk) of distinct nodes and links for some ej = (Vi _" Vi) E E, for 1~i~k.
The selection of routing metrics is very important in QoS routing algorithms
because they have critical implications on the complexity of path computation and also
on the range of QoS requirements that can be supported. The factors for metric selection
to be considered are [3]:
I) For any metrics selected, efficient algorithms should exist for path
computation, therefore the routing protocol can be scaled to large networks.
2) The metrics must reflect the basic characteristics of a network. Any QoS
requirements have to be mappeu onto the constraints on a path expressed in tenns
of the metrics.
3) :Yletrics should be independent to each other, which means no redundant
information among the metrics. Recursive evaluation among metrics can make
path computation significantly complex.
The computational complexity is primarily determined by the composition rules
of the metrics. The three basic composition rules are discussed below.
3
Definition: Let M (e) be a metric for link e E E, and M (?) be a metric for a
M is additive if
k
M(?) = IM(e,);
;~I
the metric M is multiplicative if
k
M(?) =nM(e,);
;=1
and the metric M is concave if
Considering some routing metrics: delay, delay jitter, cost, loss probability, and
bandwidth, it is easy to see that delay, delay jitter, and cost follow the additive rule, and
bandwidth follows the concave rule. The composition rule for loss probability is
complicated, but loss probability can be easily transformed to an equivalent metric, the
probability of successful transmission, which follows the multiplicative rule [4].
Path computation algorithms for a single metric have been widely used in the
current networks. These most widely studied single metrics include delay, and hopcount.
However, using a single metric cannot support user QoS requirements. We still
need information on other resources such as bandwidth.
One possible approach is to define a function and generate a single metric from
multiple parameters. This approach means various pieces of infonnation are combined
into a single measure, then use it as the basis for routing decisions [3, 4]. However, a
mixed metric only reflects the status of the network at a particular time instancel and it
docs not provide infonnation for making quantitative assessment as to whether
4
application's req uirement can be met or not. In addition, mixing metrics may invalidate
the composition rule. Therefore, mixed metTLc approach is just a tempting heuristic. It is
not sufficient to suppol1 QoS requirements.
Clearly, multiple metrics can model the characteristics of a network more
accurately. However, finding a path with muttiple constraints is mherently hard. For
example, finding a path with two simple additive metrics is NPcomplete [5]. The
problem In QoS routing is much more complicated since the resource requirements
specified by the applications are often diverse and applicationindependent, and the
network state changes dynamically due to transient load fluctuation, connections in and
out, links LIp and down.
5
Chapter III
Relevant Work
The routing problems can be categorized into two major classes: unicast routing
and multicast routing [1]. The unicast routing problem is defined as follows: given a
source node s, a destination node t, a set of QoS constraints C, and possibly an
optimization goal, find the best feasible path from s to t which satisfies C. The
multicasting problem is defined as follows: given a source node s, a set Rof destination
nodes, a set of constraints C, and possibly an optimization goal, find the best feasible tree
covering s and all nodes in Rwhich satisfies C. These two classes of routing problems
are closely related. Unicast routing problem can be considered as a special case of the
multicast problem.
There are three routing strategies that are source routing, distributed routing, and
hierarchical routing. They are classified according to how the state information is
maintained and how the search of feasible paths is carried out. In source routing, each
node maintains the complete global state, including the network topology and the state
information of every link. Base on the global state, a feasible path is locally computed at
the source node. Acontrol message is then sent out along the selected path to inform the
intermediate modes of their precedent and successive nodes. In distributed routing, the
path is computed by a distributed computation. Control messages are exchanged among
the nodes, and the state information kept at each node is colJectively used for the path
6
search. The routing is done on a hopbyhop basis. In hierarchical routing, nodes are
clustered into groups, which are further clustered into higher level groups recmsively,
creating a multilevel hierarchy. Each physical node maintains an aggregated global state.
This state contains detailed state information about the nodes in the same group and
aggregate state information about other groups. Source routing is used to find a feasible
path on which some nodes are logical nodes representing groups. A control message is
then sent along this path to establish the connection. When the border node of a group
represented by a logical node receives the message, it uses the source routing to expend
the path through the group.
3.1 Source Routing AJgorithms
Source routing algorithm is also called sequential algorithm. The source routing
algorithm can be categorized into three major classes, which are unicast routing problem,
multicasting routing problem, and hierarchical routing problem, respectively. They will
be discussed below in detail.
3.1.1 Unicast Routing Problems
In general, source routing algorithms need to maintain global states at every node.
Most unicast source routing algorithms [3,4,6, 7, 8, 9, 10] used extended Dijkstra's or
the BellmanFord algorithm to solve the multiple constraints routing problem.
Wang and Crowcraft [3, 4] proposed a source routing algorithm and a distributed
routing algorithm to find a bandwidthdelayconstrained path. In the source routing
algorithm, the path is computed by Dijkstra's shortestpath algorithm. The links with
7
bandwidth less than the requirement are eliminated so that any paths in the resulting
graph will satisfy the bandwidth constraint. Then the shortest path in terms of delay is
found. The path is feasible if and only if it satisfies the delay constraint. The distributed
algorithm will be discussed later.
Chen and Nahrstedt [6] proposed a heuristic algorithm for the NPcomplete 1TI1IJtipath
constrained routing problem. For a delaycostconstrained routing problem, the idea
is to map the cost (or delay) to every link fonn an unbounded real number a bounded
integer. Therefore, the reduced new problem can be solved by an extended Dijkstra's
algorithm or an extended BellmanFord algorithm in polynomial time.
Ma and Steenkiste [7] showed that the endtoend delay, delay jitter, and buffer
space bounds are not independent when a class of Weighted Fair Queuinglike scheduling
algorithm is used. These parameters are functions of the reserved bandwidth, the selected
path, and the traffic characteristics. Therefore, we can simplify the problem of finding a
path satisfying bandwidth, delay, delay jitter, and buffer space constraints from NPcomplete
to polynomial time. Ma and Steenkiste [7] used a modified BellmanFord
algorithm to solve this kind of routing problem by considering the functional relationship
of constraints.
Lua et al. [8] proposed a simple heuristic algorithm to solve the boundeddelaymin
cost problem. This algorithm first used Dijkstra's shortest path algorithm to find the
minimum delay for each node 1I to the destination node t. Then only the paths satisfying
the delay constraint are selected, and in the mean time, the minimum cost in such paths is
computed.
8
3.1.2 Multicast Routing Problems
The multicast routing problem is similar to the unicast routing problem, except
that an optimization or a constraint must be applied to the entire tree instead of a single
path. Multicasting consists of concurrently sending the same infonnation to a group of
destinations. This is becoming a key requirement of computer networks supporting
multimedia applications. The Steiner tree problem is a wellknown multicast problem.
The tree covers a group of destinations with the minimum total cost over all links. The
constrained Steiner tree problem is to find the least cost with hounded delay, which is
NPcomplete [11].
Widyono [9] proposed several heuristic algorithms for the constrained Steiner tree
problem. The one with best perfonnance is based on the BellmanFord algorithm. At
each step, a delayconstrained least path from source to a destination is found by
performing a breadthfirstsearch. However, the complexity of such algorithm IS
exponential, therefore it is less scalable and not suitable for real large network.
Zhu et a1. [10] developed a heuristic algorithm for constructing minimumcost
multicast trees with delay constraints. This algorithm can handle variable delay bounds
on destination, and it is based on a feasible search optimization method which starts with
the minimum delay. The basic idea of this algorithm is to first construct a shortestpath
tree in terms of delay Llsing Dijkstra's algorithm, then to replace a path in the tree by
another path with lower cost unless such areplacement cannot be found.
Kompella et al. [11] proposed a source routing heuristic algorithm to construct a
constrained Steiner tree. The multicast tree construction depends on the bounded endtoend
delay and the minimum cost of each path. The first step is to create a complete
9
graph, where the nodes represent the source and destinations, and the edges represent the
delayconstrained leastcost paths between these nodes. The second step is to construct a
delayconstrained spanning tree of the complete graph. ThIs algorithm shows the good
average case behavior in terms cost, as determined through simulation on a large number
of graphs.
Sun and Langendoerfer [12] proposed an algorithm to construct an approximated
constrained Steiner tree by Dijkstra's algorithm. It first computes the shortestpath tree in
tenus of cost. Then the tree is modified to satisfy the delay constraint. The time
complexity of this algorithm is O(IVllogIVI), which is the same as Dijkstra's algorithm.
Attentions should be paid to other existing heuristics, such as the algorithm to find
a Steiner tree by an incremental approach called nearest destination first [13], the
algorithm proposed by Kou et al. [14], which used Prim's algorithm [15] to construct a
minimum spanning tree in a complete graph, and the algorithm proposed by Rouskas and
Baldine [16] to construct adelaydelayjitterconstrained multicast tree.
In summary, most of the existing multicast source routing algorithms need to
maintain the global state at every node. Most heuristic algorithms for the NPcomplete
multicast routing problems construct a constrained tree incrementally by adding one
destination into the tree each time based on certain selection criteria.
3.1.3 Hierarchical Routing Problems
Large networks are often structured hierarchically by groupmg nodes into
different domains in order to deal with the scaling problem. In such networks, it is
infeasible to maintain the detailed network information at every router. Therefore,
10
topological infonnation of domains is summarized before broadcasted. Hierarchical
routing protocols are then used to find a route among the domains [16]. In order to
perfonn hierarchical routing efficiently, the network will consist of subnetworks, called
peer groups, and peer groups will advertise the aggregate infonnation periodically, which
is based on timebased update interval or on an event driven basis [17]. For more
information about hierarchical QoS routing, refer to the related papers [16. 17. 18, 19]
and references in them.
3.2 Distributed Routing Algorithms
A distributed routing is also called hopbyhop routing. In distributed routing, a
path is detennined in a distributed manner. Routing messages are exchanged among the
nodes so that the network state infonnation maintained at different nodes can be
collectively utilized.
3.2.1 Unicast Routing Problems
Reeves and Salama [20] proposed a socalled delayconstrained unicast routing
(DCUR) algorithm to solve the NPhard delayconstrained leastcost path problem.
DCUR only requires a cost vector and a delay vector to be kept at each node. DCUR is
always capable of constnlcting a loopfree delayconstrained path with finite time, if such
a path exists. The worst case message complexity of DCUR is O(lVI) where IVI is the
number of nodes. Since the fewer messages are required by DCUR, DCUR has a good
scalability to apply to large networks. The basic idea of DCUR is that at any point, a
node checks for the feasibility of a path along the shortest cost path from itself to the
11

destination. If such a feasible path exists, then the next hop with respect to the shortest
cost is selected, else the next hop with respect to the shortest delay is selected.
Wang and Crowcroft [3, 4] proposed a distributed algorithm to solve the
bandwidthdelayconstrained routing problem. This algorithm is based on the distributed
BellmanFord algorithm using distance vectors, and precomputes a forward entry for
every possible destination. Since a path with maximum bandwidth and minimum delay
may not exist, the precedence is defined as bottleneck bandwidth and then propagation
delay in this algorithm. The search strategy is to find a path with maximum bottleneck
bandwidth (a widest path), and ifmore than one widest path exists, the one with shortest
propagation delay is selected.
Jaffe [21] studied a variation of the problem in which the path cost and the path
delay are defined as two constraints. He proposed a pseudopolynomialtime heuristic
and a polynomialtime heuristic for solving the problem. The polynomialtime algorithm
minimizes (L(P) + d*W(p)), where L(p) is the length of the path p, W(p) is the cost of the
path, and d is a weighing factor. However, this algorithm could fail to find a delayconstrained
solution when one exists.
Other papers [12, 22, 23, 24] related to unicast distributed routing problem are
also of great interest. For detailed information, refer to these papers and references in
them.
3.2.2 Multicast Routing Problems
Kompella [25] et al. proposed a distributed heuri stic algoritlun to construct the
constrained Steiner tree. The algorithm requires every node to maintain a distance vector
12
to store the minimum delay to every other node. Starting from the source node, the
multicast tree is constructed iteratively by adding a link into the tree each time until every
destination is included in the tree. The algorithm requires intensive message exchange.
The worst complexity is O(IVI\ where IVI is the number of nodes in a network.
Carlberg and Crowcroft [26] proposed an algorithm to construct multicast trees
across different domains using spanningjoins approach. A new group member
broadcasts a joinrequest message. When an ontree node receIves the message, it sends
a unicast reply message back to the new member. The path of the reply message is
determined by the existing unicast routing algorithm. This algorithm handles dynamic
membership and does not require any global network state. However, it has excessive
communication overhead because it relies on flooding to find a feasible tree branch to
connect a new member.
13
Chapter IV
Heuristic Based on Dijkstra's Algorithm
In this chapter, a heuristic, based on Dijkstra's algorithm, for the bounded delay
constrained bandwidth least cost (BD_CB_LC) path problem will be introduced. The
formal description ofBD_CB_LC problem is as below.
N(V, E) is the given graph with costs and delays and bandwidth associated with
its edges, where V is the set of nodes, and E is the set of links in N. A least cost feasible
path from node s to node t in N is required. The upper bound on the delay of a path is T,
and the least bandwidth of a path is B. Therefore, the solution to BD_CB_LC problem is
to find a path with least cost and the delay of this path not greater than T and the
bandwidth of each link in this path not less than B.
4.1 Dijkstra's Algorithm
Before introducing the heuristic for the bounded delay and bandwidth least cost
path problem, the wellknown Dijkstra's algorithm will be presented first.
Dijkstra's algorithm is used to find a least metric st path in a network N where s
is the source node, and t is the destination node. The applied metric should be additive
such as delay, cost. The algorithm associates three variables with each node u, namely,
MLABEL[u], PERM[u], and PRED[u]. At any step in this algorithm, MLABEL[u]
14
represents the evaluated metric of a path from nodc s to node t, PERM[u] indicates
whether a node u has been permanently laheled or not, and PERD[u] indicates the node
form which node u has received its latest MLABEL value. Figure 41 is the pseudocode
for Dijkstra's algorithm.
In Figure 41, lines 1 to 6 ini tializc the parameters. Lines 9 to 12 are the general
steps to calculate the values of MLABEL[v], wi th fill \ refers to the val ue of metric of the
link directed from node u to node v. Lines 13 and 14 are used to find the nonpermanently
labeled node w with smallest MLABEL valuc. In case of a tie the choice can
be made arbitrarily. In the implementation of Dijkstra's algorithm, the first nonpermanently
labeled node with smallest MLABEL value is selected. Dijkstra's algorithm
terminates when destination node t is permanently labeled. After termination, the
predecessor array PRED is used to trace the least metric st path, and MLABEL[t)] is the
least value of metric from s to 1. Dijkstra's algorithm runs in O(IVI2
) time complexity.
1 "
Dijkstra (N(V, E), s, t)
for all node vin VIlinitiali7.ation
2 MLABEL[v] = CI)
3 PERM[v] = false
4 PERD[v] =v
5 MLABEL[s] =0
6 PERM[s] =true
7 u = s II u is the latest permanently labeled node
8 while (u 1 t)
9 for all node v adjacent to u
10 if (nol PERM[v] and MLABEL[v] >MLABEL[u] + Illu,v)
11 MLABEL[v] = MLABEL[u] I mu,V
12 PRED[v]=u
13 for all nodes not permanently labeled
14 find node wwith smallest MLABEL value
15 PERM[w] =true
16 u=w
17 return MLABEL[t]
Figure 4l. Dijkstra's algorithm
16
4.2 ANew Heuristic Developed from Dijkstra's Algorithm
The proposed heuristic adapts Oijkstra's algorithm for suboptimal solution to the
BD_CB_LC problem. The heuristic, called Oijkstrabased heuristic, first computes the
delay of a least delay ut path for each node u. In order to compute the delay, Dijkstra's
algorithm is applied on the network N*, which is obtained by reversing the directions of
all links in the given network N, and using the link delays as the computation criterion,
and using node t as the source.
In addition to the variables PERM[u] and PERD[u], three more variables are
defined in the proposed heuristic, whieh are O[u], CLABEL[u], and OLABEL[u]. O[u]
represents the delay of a least delay nt path, CLABEL[u] represents the cost of an sou
path, and DLABEL[u] represents the delay of an su path. Initially, DLABEL[u] is set to
ofor all U E V, CLABEL[s] = 0, and CLABEL[u] = co for u1: s. PERM(u] and PERD(u]
are initialized same as in Dijkstra's algorithm. Figure 42 is the pseudocode for
Dijkstrabased heuristic.
In Figure 42, line 1 constructs a network N* based on the given network Nby
reversing all links in N. Line 2 computes for each node u the value of D[u], the delay of
a least delay path [rom t to u. Lines 3 to 5 are the initiaJizations thal are same as in
Dijkstra's algorithm, except that a new valiable DLABEL[v] is initialized. Lines 8 to !3
calculate the values of CLABEL[v] and DLABEL[v] and PRED(v] [or each none
pemlanently labeled node v adjacent node u. Line 9 checks if there exists a feasible s·t
path through link (u,v) by testing the bandwidth of link (u,v) as well as the delay
constraint. If both the bandwidth and the delay constraints arc satisfied, the algorithm
continues checking whether this node v is pennanently labeled or not, and the cost of sv
is less than the cost of su plus C\I,Y' Here d\l,v and C\I,V refer to the cost ana delay of the
link directed from node u to node v, respectively. j[ the conditions are satisfied.. the
values ofCLABEL[v], DLABEL(v], and PRED[v] are updated. Lines 9 to 13 are the key
steps 0 f the proposed heuristic for BC_CB_LC problem. The rest is same as in Dijbtra's
algorithm. Dijkstrabased heuristic terminates till destination node t is pcnmmendy
labeled. The time complexity ofDijkstrabased heuristics is O( lyI2).
18
D~kstrabased (N(V, E), s, t, T, B)
Construct a network N* by reversing the directions of all links in N
2 Compute for eaeh node u the value of D[ u] by Dijkstra' s algorithm on 01"*
3 for all node v in VIlinitialization
4 CLABEL[v] = co, DLABEL[v] =0, PERM[v] = false, PRED[v] = v
5 CLABEL[s] = 0, PERM[s] = true
6 u = s II u is the latest permanently labeled node
7 while (u:;t: t)
8 for all node vadjacent to u
9 if(bu,v ~ Band DLABEL[u] +du.v+ D[v] ~ T)
10 if(not PERM[v] and CLABEL[v] > CLABEL[u] +cu,v)
11 CLABEL[v] = CLABEL[u] + cu,v
12 DLABEL[v] = DLABE:[u] I du,v
13 PRED[v] ' u
14 for all nodes not pennanently labeled
15 find node wwith smallest CLABEL value
L6 PER1V[[w] =true
17 u = w
18 return CLABEL[t] and DLABEL[t]
Figure 42. Heuristic for the BD_CB_LC Problem Based on Dijkstra's Algorithm
19
An example of how to use Dijkstrabased heuristic is shown below. The proposed
heuristic is applied on the graph of Figure 43.
T=70,8=20
• • u CII.". dll , \', h1,1Y v
10,12,18
\,20,28
6,lO,30 5,1O,22
4,10,21 1,10,23
1,30,30 2,S.IR
J,J 0.15
1,10,29
Figure 43. An Example of Network with Cost, Delay, and Bandwidth
D(I]~15 D[2]=10
(co,O) (00,0)
1,20,28
10,12,18
(,,10,30 5,10,22
4,10,21 1,10,23
D[t]=O
D[s]=27
(co,O)
(0,0)
1,30,30 2,5, I~
1,10,29
1.10,15
D[2]=20 D[4]=10
('Xl,0) (00,0)
Figure 44. Initialization
20
O[ t ]~15 0[2]=10
(00,0) (00,0)
1,20,28
10,12,18
6,10,30 5,10,22
4,10,21 1,10,23
D[t]'O
O[s]=27 (00,0)
(0,0)
1,30,30 2,5,18
1,10,29
1.10.15
0[2]=20 0[4]=10
( I, 30) (00,0)
Figure 45. Iteration 1
0[1 ]=15 0[2]=10
(5,40) (7,40)
1,20,28
10,12,18
6,10,30 5, I0,22
4,10,21 1,10,23
0[1]=0
O[s]=27
(00,0)
(0,0)
1,30,30 2,5,18
1,10,29
1,10,15
0[2]=20 D[4]=10
(I, 30) (00,0)
Figure 46. Iteration 2
21
0[1]=15 0[2}=10
(5,40) (6,60)
1.20.28
10,12,18
6,10,30 5,10,22
4,10,21 1,10,23
Dlt] =0
D[s]=27
(00,0)
(0,0)
1,30.30 2,5,18
1,10,29
1,10,15
D[2]=20 D[4]=IO
(1, 30) (00,0)
Figure 47. Iteration 3
D[I)=15 D[2]=1O
(5,40) (6,60)
1,20,28
10,12,18
6,10,30 5,10,22
4,1 0,21 1,10,23
D[tJ=O
D[sJ~27
(II, 70)
(0,0)
1,30,30 2,5,18
1,10,2<)
1,10,15
D[2)=20 0[4]= 1O
(1,30) (00,0)
Figure 48. Iteration 4
22
Figure 49. Iteration 5
After iteration 5, node t gets permanently labeled. The final st path can be traced from
the value of array PRED. The procedure is shown in Figure 410.
Path_Trace (PRED, s, t)
u = t
2 Insert u to an empty linked list L
3 while (u ::f s)
4 u =PRED[u]
5 Insert u to the front of L
6 return L
Figure 410. Procedure for Path Trace
23
The returned list contains the nodes in the st path produced by Dijkstrabased
heuristic. For the graph in Figure 43, the heuristic found the path P= (s, 2, 1,3, t), which
has a cost of 11 and a delay of 70, and the bandwidth of each link in this path is greater
than B which is 20. However, the optimal path is (s. 2, 3. 4, t) with a cost of 9 and a delay
of 60. This concludes that the path found by Dijkstrabased heuristic may not be the
optimal one.
24
Chapter V
Heuristic Based on the BellmanFordMoore Algorithm
In Chapter IV, a heuristic based on Dijkstra's algorithm is introduced. Dijkstra's
algorithm is one of the two algorithms for the single source shortest path problem. The
Bel1manFordMoore (BFM) algorithm is another one. In this chapter, a heuristic for
bounded delay constrained bandwidth least cost (BD_CB_LC) problem will be
introduced based on the BFM algorithm.
5.1 BellmanFordMoore Algorithm
The variables defined in the BFM algorithm are MLABEL[u] and PERD[u],
which are same as those in Dijkstra's algorithm. Figure 51 is the pseudocode for BFM
algorithm.
In Figure 51, lines 1 to 5 are the initialization for BFM algorithm. Lines 6 to 13
are the key steps for BFM algorithm. Lines 8 to 12 examine all the edges of a node u,
and label the neighbor nodes of u, if possible. This procedure is called a scanning of a
node u. Lines 8 to 12 scan all the nodes as 1, 2, 3, "', in that order. This procedure is
caned as sweep. BFM algorithm tenninates if no MLABEL value gets update. The
returned value MLABEL[t] is the least metric value of st path. The BFM algorithm runs
in O(nm) time complexity, where n is the number of nodes, and ill is the number of
edges, respectively.
25
BFM (N(V, E), s, t)
for each node v E V
2 MLABEL[v] = 00
3 PRED[v] = v
4 MLABEL[s] = 0
5 update = true
6 while (update)
7 update = false
8 for each edge (u, v) E E
9 if(MLABEL[u};t:oo and MLABEL[u]+mu,v<MLABEL[v])
10 MLABEL[v] = MLABEL[u] + mu,v
11 PRED[v]=u
12 update = true
13 return MLABEL[t]
Figure 51. The BFM algorithm
26
There are two versions of implementation of the BFM algorithm. One is called
asynchronous implementation in which the current value of MLABEL[u] is used to
update the labels of neighbors of node u while scanning a node u during a sweep.
Another is called synchronous implementation in which the value of MLABEL[u] at the
end of the previous sweep is used to label the neighbors of node u while scanning a node
u during a sweep. An example of how the synchronous version of BFM algorithm IS
applied on Figure 52 is shown below.
•u CII,V
•v
10
4
6
2
5
Figure 52. An Example of Network with Cost
27
(0)
10
(co)
4
(co)
6
2
(oc )
5
(co)
Figure 53. Initialization
(0)
10
(10)
(I)
6
2
(co)
(co)
5
(co)
Figure 54. Sweep I
28
(0)
10
(5)
4
( 1)
(7)
6
2
5
(00)
(4)
Figure 55. Sweep 2
(3)
(0)
10
4
(I)
6
2
(2)
5
(3)
Figure 56. Sweep 3
29
(4) (3)
10 6 5
(0)
4
(I)
2
(2)
Figure 57. Sweep 4
t
(3)
After Sweep 4, no CLABEL values get update, therefore the algorithm stops. The
shortest path can be traced from PRED arrays. The procedure is same as given in Figure
410. In this case the final st path is s24t with the cost of 3.
5.2 A New Heuristic Developed from BFM Algorithm
The ne,;", heuristic for the bounded delay constrained bandwidth least cost
problem is based on the BFM algorithm. In this heuristic, each node u is associated with
the variables CLABEL[u], DLABEL[u], and PRED[uJ. Before the initialization of these
variables, D[uJ, the minimum delay of each ut path should be calculated, which is same
as in Chapter IV. Initially, DLABEL[u] is set to °for all U E V, CLABEL[s] = 0, and
CLABEL[u] = 00 for u * s. PERD[u] is a list of entries. Each entry in the list consists of
three components (x, y, z). Initially, each node u has only one entry, namely (u, 0, 0).
When the labels of a node u are updated by node, an entry (x, y, z) is added to the list
30
PRED[u]. where x == v, y = CLABELfv}, and z = DLABEL[v]. However, only those
entries causing node u to propagate new waves need to be added to PREDluJ. Figure 5~8
IS the pseudocode fOf the BFMbased heuristics algorithm,
In Figure 58, lines 15 are the initialization of variahles, WhlCh are similar to
those in Dijkstrabased algorithm. Lines 10  14 are the key steps in the heuristic
algorithm. Line 10 checks ifa feasible path containing link uv exists. It checks if the
bandwidth satisfies the bandwidth constraint, the delay satisfies the bounded delay, and
the cost of sv is less than the cost of su plus Cu,v. Here d\l.v and Cll,V refer to the cost and
delay of the llnk directed from node u to node v, respectively. If the conditions are
satisfied, the values of CLABEL[v], DLABEL[v], and PRED[v] are updated. The
algorithm terminates when no update is made on the variables CLABEL[u). The run
time complexity for BFM based heuristic algorithm is O(nm), where n is number of
nodes, and m is number of edges, respectively.
31

BFMbased (N(V, E), s, t, B, T)
Construct a network N* by reversing the directions of all links in N
2 Compute for each node u the value ofD[u] by BFM algorithm on N*
3 for all node v in V Ilinitialization
4 CLABEL[v] = 00, DLABEL[v] = 0, PRED[v] = (v, 0, 0)
5 CLABEL[s] = °
6 update = true
7 while (update)
8 update = false
9 for each edge (u, v) E E
10 if (bu,v ~ Band DLABEL[u) + du.v+ Div) ~ T
and CLABEL[u]+cu,v<CLABEL[v])
11 CLABEL[v] == CLABEL[u] + Cu.v
12 DLABEL[v] = DLABEL[u] + du.v
13 PRED[v] = (u, CLABEL[u], DLABEL[u])
14 update = true
15 return CLABEL[t] and DLABEL[t]
Figure 58. Heuristic for the BD_CB_LC Based on the BFM Algorithm
32
An example of how to use BFMbased heuristic is shown below. The proposed
heuristic is applied on the graph of Figure 59.
Figure 59. An Example of Network with Cost, Delay, and BandwiLlth
Figure 510. Initialization
33
0111' 15 0[2]10
(CIl,O) (CIl,O)
1,20,28
10,12,18
6,10,30 5,10,22
4,10.21 1,10,23
0[1]'0
D[s]=27 (CIl,O)
(0,0)
2,5,\8
1,10,29
1,30,30
4
1,10,15
D[2]=20 0[4]=10
(1,30) (CIl,O)
Figure 5 J 1. Sweep 1
D[I]15 0[2]010
(5,40) (7.40)
1,20,28
10,12,18
6,10,30 5,10,22
4,10,21 1,10,23
0[1]'0
D[sJ=27 (CIl,O)
(0,0)
1,30,30 2,5,18
1,10,29
1,10,15
D[2Jc20 D[4]=10
(1,30) (CIl,O)
Figure 512. Sweep 2
34
t
Figure 513. Sweep 3
Figure 514. Sweep 4
35
r
0[1]=15 D[2]c \0
(5,40) (6,60)
1,20,28
10,12,18 3
6,10,30 5,10,22
4,10,21 1,10,2.1
D[I]=O
D[s]~27
(9,60)
(0,0)
1,30,30 2,5,18
1.10,29
4
1,10,15
0[2]=20 0[4]010
(1,30) (8, SO)
Figure 515. Sweep 5
The heuristics terminates at the end of Sweep 5 since no update is made on
CLABELs. However, the path trace is difficult since PRED is a list of entries instead of
a single node. Figure 515 is the pseudocode for path trace of the BFMbased heuristic
algorithm. The final path is P=(s, 2, 3,4, t), which has a cost of 9and a delay of 60.
36
Path_Trace (PRED, s, t)
set (x, y, z) to be the last entry in PRED[t]
2 Insert u to an empty linked list L
3 while (x ~ s)
4 for eaeh entry (xl, yl, tl) ill PRED[x] list
5 if (y=yl +c~l.xalldz=zl+dx1 ,x)
6 x=xl;
7
8
9
10
11 return L
z = zl;
Insert x to the front oflist L
goto line 3
Figure 516. Procedure for Path_Trace
37
..
Chapter VI
Heuristic Based on Lagrange Relaxation
ill this chapter, a heuristic for the bounded delay constrained bandwidth least cost
(BD_CB_LC) problem will be introduced based on linear Lagrange relaxation.
6.1 Linear Lagrange Relaxation
The basic idea of Linear Lagrange Relaxation (LR) is to first combine the delay
and cost in telms of a parametera to form an aggregate metric m=d+a *cfor each
link, where d is the delay and c is the cost. As long as an appropriate parameter value
for a is obtained, the resulting shortest path could be a feasible solution of high quality.
We formulate the Linear Lagrange Relaxation for the BD_CB_LC problem as follows.
A path p = Dijk(m) means that p is a shortest path with respect to metrlc m
between source s and destination t found by Dijkstra's algorithm. Therefore, Dijk(c) and
Dijk(d) are the least cost path and least delay path, respectively. The delay and cost of
path p are given by Dp and Cp, respectively.
Theorem 6.1 If P = Dijk (d +a "'c), q = Dijk (d +/3*c), a? /3,a,/3 E R;,
where R; is the set ofpositive real number, then Cp~Cq and Dp? Dq.
Proof: According to the definition, p = Dijk (d +a'" c) is a shortest path
obtained by using Dijkstra's algorithm with metric m= d+a '" con each link. Therefore,
the following holds:
38
Similarly,
D +a*C <D +a*C. p p  q "
D +fJ*C <D +fJ*C. 'I q  P P
(I)
(2)
Inequality (1) plus Inequality (2), and omit same telms, the fol1owing inequality is
obtained:
a*C +fJ*C <a*C +fJ*C . p q  q p
Since a ~ fJ, Cp :s: C" holds. Furthennore, the following inequality holds.
(3)
(4)
(5)
Theorem 6. I indicates the impact of the parameter on the delay and cost of the
resulting shortest path. The larger the parameter is, the larger the delay, and the smaller
the cost. So it means as long as the resulting shortest path does not violate the delay
constraint, a larger parameter will definitely give rise to a better solution, a lower cost.
Theorem 6.2 is the theoretical basis for finding the largest parameter with corresponding
path not violating the delay constraint.
Tbeorem 6.2 Ifp = Dijk(d+a*c), q = Dijk(d+fJ*c), r ~ Dijk(d+y*c),
D D
where a<j3,Cp ;t:.C",y= C" _/ ,thenCp 2C,2Cq,Dp :S:D.. :S:D".
p q
Proof: From Theorem 6.1, if a ~ y ~ fJ holds, then Theorem 6.2 is true. Since
p= Dijk( d + a * c ), the fol1owing holds
D +a*C ~D +a*C p p qq'
Arrange (6), we get
39
(6)
r (7)
From Theorem 6.I,a <f3 implies thatC" ~ (" Since(" 1 C'q. Inequality (7) can
be rewritlen as follows:
D D
a~qp
C" Cq
D D
Since y =q ", we get
Cp Cq
Similarly, r ~ f3 can be proved.
(8)
(9)
D D
Theorem 6.2 indicates that with r = q p , the resulting shortest path must
Cp Cq
yield a delay between the delays of paths p and q, and a cost between the costs of the two
paths. The heuristic for the BD_CB_LC problem, which will be introduced in Section
6.2, is actually based on Theorem 6.2.
6.2 Heuristic Based on Linear Lagrange Relaxation
The heuristic based on Linear Lagrange Relaxation is shown in Figure 61. In
Figure 62, line I reduces the network with respect to the constrained bandwidth B. The
detailed method will be introduced in Figure 62. The least cost (LC) path is obtained in
line 2. Line 3 tests if such a path satisfies the delay constraint T. If yes, then the path is
the optimal solution. It is returned by line 4, and the algorithm tenninates, If not, the
least delay (LD) path is obtained in line 5. Line 6 tests if the delay is greater than the
dejay constraint T. If yes, it means no desired path exists. The null is returned by line 7,
40
.. r
and the heuristic terminates. Otherwise, an iterative procedure will begin from line 8.
Line 8 is necessary since even if LC palh is infcasibk and LD path is feasible, the two
paths might have the same cost because Dijkstra's algorithm breaks ties arbitrarily. Line
12 calculates the parametera by using the two previous paths p and q. Therefore, a new
mixed metric is obtained based on the parameter a, and a new path r is found by using
Dij kstra' s algorithm in line 12. From lines 13  17, either p is updated with a better
feasible solution r in the sense that r has a lower cost, or q is updated with a better
infeasible solution r in the sense that r has a lower delay. The algorithm terminates if no
better solution can be found. Then the path pis the final solution.
The function Reduce_Network is introduced in Figure 62. The main idea is to
set the cost and delay of each edge to 00 whose bandwidth b is less than bandwidth
constraint B. Then the final path is found based on the new revised network.
41
•f
LRbased (E, V, s, t, c, d, T, B)
Reduce_Network (E. V. B)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
q f Dijk(c)
if(Dq ~ T) then
retUlll q
p ~ Dijk(d)
if (Dp> T) then
retum nuJl
if (Cp t Cq) then
continue =true
while continue do
rf Dijk(d+a *c)
if (Cr = Cq or C. = Cp) then
continue:..; false
else if (Dr ~ T) then
p f I'
else
q f I'
return p
Figure 61. Heuristic for the BD_CB_LC problem based on Lagrange Relaxation
42
 T Reduce_Network fL V, B)
for each edge (1I, v) in E
2
3
4 du•v = OCJ
Figure 62. Function of Reduce_Network
43
Chapter VII
Results and Analysis
In this cbapter, the experiment results will be presented [or the three heuristics
introduced in the previous chapters. The results of three beuristics. Dijkstra based, BFM
based, and LR based will be compared with each other.
7.] Testing Network Instances
In order to evaluate the results of the proposed heuristics, two kinds of network
topologies are used. One is the regular graph, and another is the ilTegular graph, which
will be presented below.
7.1.1 Regular Graph
Regular graph Hk.n• was proposed by Thulasiraman and Swamy [28], where k is
the vertex degree and nis the number of vertices. The graph fh,n is defined as follows.
Case 1: k even
Let k =2r. Then H2r.n has vertices Va, VI, V2, ... , VIII and two vertices VI and Vj are
adjacent if and only if i  r ~j ~i +r, where addition is modulo n.
Case 2: kodd, neven
Let k =2r + I. H2rtl,1I is constructed by first constructing H2rll and then adding
edges j oi oj ng vertex Vi to vertex Vj for i = 1, 2, ..., n/2 and j = (i +n/2)mod n.
Case 3: k odd, nodd
44
 +
Let k =2r + 1. H2r+I.II is constructed by first constructing H2r.1I and then adding
edges joining Vi and Vj for i =0, 1,2, ... , (II .. I) /2 andj =[i +(n + 1)/2] mod n.
An example of graph H6,8 is shown in Figure 71.
va
V6 V2
Figure 71. An Example of Regular Graph
7.1.2 Irregular Graphs
In order to best evaluate the heuristics proposed in previous chapters, a realistic
random topology for simulation is in need. To illustrate the current stateoftheart in the
area of generating Internetlike topologies, Winick and Jamin [29] developed an Internet
topology generator called Inet, which generates the Internet topology based on
autonomous system connectivity.
An autonomous system (AS) is a network under a single administrative autholity.
ASs connect to each other through border routers, so the Internet can be considered as
4S
consisting of interconnected ASs. Within each AS, the network could be further divided
into subnetworks connectcd by intemal routers. Hence, the Internet can either be
modeled as a graph where each node represents a router, or as a graph where each node
represents an AS. The graph generated by lnet has the power law structure, which is
more like the real existing network since only a few super routers in large cities control
the routing traffic. In 1999, Faloutsos et al. [30] found several power laws relating to the
topology of the Internet. One of these power laws was f(d) ex: rf, that is, the frequency of
nodes with degree d is proportional to d raised to a power of a constant O. Inet 3.0 uses
this power law to generate the Internet topology.
7.1.3 Parameters for Generated Graphs
For the generated graph, both regular and irregular, the parameters for each edge
need to be detennined. For each edge, three parameters exist. They are cost, delay, and
bandwidth, respectively. There are two ways to select these parameters.
1. Randomly generated cost and delay from 1 to a specific number max, and
bandwidth greater than a specific number min.
2. Randomly generated cost and delay such that ci,j+dij"'max, and
bi,j=Ci/di,j+m in.
The reason for choice 2 is that cost and delay inversely related, and the larger the
cost and the less the delay, the larger the bandwidth. This could be the worstcase
scenario to test, and can test which heuristic is better. In the simulation, select max=50,
and min=18. The bound delay T is computed as the two times of the least path delay
46
from source node to the destination node and the constraint bandwidth Bis computed as
min + 2, which equals 20, _ 
7.2 Comparison of Dijkstra based, BFM based, and LR based heuristics
Three cases are used to evaluate the proposed heuristics. These cases are
1, Regular grarhs with randomly generated cost, delay, and bandwidth,
which correspond to choice 1,
2. Regular graphs with related cost, delay, and bandwidth, which correspond
to choice 2, and
3, Irregular graphs with related cost, delay, and bandwidth, which cOITespond
to choice 2,
For each case, 100 times simulation will be nm to see the average results,
Therefore, the results in tables and figures are average results, not for a single case.
7.2.1 Results for Case 1
In Table 71, the results of three proposed heuristics for test case 1 are presented,
The graphical results arc shown in Figures 72 and 73. BFM based heuristic has the
largest search time, and Dijkstra base heuristic has the least search time. But BFM based
heuristic found the feasible path with the least cost, and LR based heuristic found the path
with the largest cost. Dijkstra based heuristic can find the path with a slightly larger cost
than that of BFM based heuristic, but it spends much less time on searching. Therefore,
considering overall perfol1l1ance for the regular graph with randomly generated cost,
delay, and bandwidth, Dijkstra based heuristic is the best.
47
Table 71 Regular Graph with Randomly Generated Cost, Delay, and Bandwidth
rOde Edge bound Dijkstra based BFM based LR based
delay~and cost~elay Time cost delay Time cost delay Time
~/idth (ms) (ms) (ms)
450 2925 246 20 400 244 51 355 244 88 723 141 140
500 2250 566 20 680 565 52 594 563 99 950 367 145
750' 4125 543 20 933 543 90 816 542 183 1254 339 245
900 9000 336 20 1344 335 170 1237 335 607 1909 168 461
1000 11000 301 20 1405 301 232 1293 30e 818 1950 150 559
1300 16250 154 20 761 154 399 714 154 899 1276 77 983
2500 42500 245 20 2716 245 1323 2612 245 6636 3526 122 3967
3000 61500 92 20 1306 92 1473 1229 92 4227 2054 46 3995 '
48
Search time vs number of nodes for regular graph
with random cost and delay anu bandwidth
7000
[~o;> ",,'" 6000 BFM based
LRbased
5000
Vi 4000 . .s
'E"
0= 3000 .
2000
, •,
/
.'
,
l..J.
1000
_. '~
800 1200 1600 2000 2400 2800 3200
o .\.M~3b;:=:~=..,~ ~j
400
number of nodes
Figure 72. Comparison of Search Time for Regular Graph with
Randomly Generated Cost, Delay, and Bandwidth
49
Least cost vs number of nodes for regular graph
wtth random cost and delay and bandwidth
4000
3500
3000
2500
1500
1000
500
Dljk based
BFM based I
. LR based J
800 1200 1600 2000 2400 2800 3200
of,~__r._.__._
400
number of nodes
Figure 73. Comparison of Least Cost for Regular Graph with
Randomly Generated Cost, Delay, and Bandwidth
50
7.2.2 Results for Case 2
In Table 2, the results for test case 2 are presented. Figures 74 and 75 are the
graphical results for test case 2. The results for case 2 are similar to those for case I.
BFM based heuristic found the path with the least cost but with the largest search time.
Dijkstra based heuristic runs on the smallest search time. The cost of the path found by
Dijkstra based heuristic is close to that by BFM based heuristic. Therefore, for the
overall performance, Dijkstra based heuristic is the best.
Table 72 Regular Graphs with Related Cost, Delay, and Bandwidth
Node Edge bound Dijkstra based BFM based LR based
delay Band cost delay Time cost delayjTime cost delay Time
width (ms) (ms) (ms)
450 2925 310 20 849 309 44 787 309 68 1335 155 108
50C 2250 673 20 1349 673 41 1193 672 77 1990 353 108
75C 4125 672 20 1863 672 117 1693 672 238 2603 336 344
900 9000 480 20 2621 480 118 2498 480 420 3290 240 382
1000 11000 447 20 2731 447 222 2589 447 778 3367 223 625
1300 16250 251 20 1566 251 273 1523 251 594 2121 125 817
2500 42500 502 20 4754 502 1011 4636 502 4472 5508 251 3639
3000j 61500 229 20 2321 229 1895 2303 229 4646 2900 114 6597
51
Search time vs number of nodes for regular graphs
with related cost and delay and bandwidth
•
lOOO 1Oijk based '
6000 • BFM based I
LRbased
SODA
! 4000
(l)
E
i= 3000·
2000
1000
O·
400 800 1200 1600 2000
./
.'
2400 2800
number of nodes
Figure 74. Comparison of Search Time for Regular Graph with
Related Cost, Delay, and Bandwidth
52
Least cost vs number of nodes for regular graphs
with related cost and delay and bandwidth
6000 r,
1 DiJk based
5000 .• 8FM based
;lRbased
4000 .
~ 3000
<)
2000
800 1200 1600 2000 2400 2800 3200
o >..,.....,..._~___1
400
number of nodes
Figure 75. Comparison of Least Cost for Regular Graph with
Related Cost, Delay, and Bandwidth
53
7.2.3 Results for Case 3
The results for test case 3 are presented 11l Table 73. An interesting result is
observed that BFM based and Dijkstra based heuristics found the paths with almost
identical cost and delay, and LR based heuristic found the paths with the delay and cost
very close to those found by BFM and Dijkslra based heuristics. The reason is that the
irregular graphs are generated by Inet, which applies power law for network growing and
evolving. So only a few super routers will dominate the traffic flow, which means only a
few possible paths to select for routing. Therefore, all these three heuristics found almost
the same path. However, the search times are different. This can be seen from Figure 7
6. BFM based heuristic may be the best choice for irregular graph, the simulated
network, since the search time steadily increases with the number of nodes increasing. In
addition, BFM based heuristic also gives the good performance.
Table 73 Irregular Graphs with Related Cost, Delay, and Bandwidth
I Node Edge bound Dijkstra based' BFM based LR based
delat~nd cost delayTime cost delay Time co IdelayTime
idth (ms) (ms) st (ms)
3037 4788 331 I 20 85 270 1542 84 267 1134 99 249 2299
3500 5666 343 20 87 286 1916 87 287 1468 124 269 3530
4000 6644 307 20 68 244 2318 68 244 1911 86 230 3990
4500 7653 310 20 68 269 2440 66 266 2038 101 239 5497
5000 869C 296 20 53 227 3091 53 227 2816 57 218 3694
6000 10849 325 20 67 274 4486 66 273 3705 8Q 257 8804
7000 13116 339 20 87 297 7059 86 298 5021 132 267 18105
8000 15493 317 20 74 265 8370 74 264 6685 106 242 18347
10000 20575 302 20 71 258 12684 70 258 10886 99 238 25971
54
30000
25000
Search time vs number of nodes for irregular graph
with related cost and delay and bandwidth
+ Dijk basj
.. BFM base.d
LRbased
!20000
lil .s
QI 15000
E
1=
10000 
5000
0
3000 4000 5000 6<J00
//
7000
number of nodes
BODO 9000 1 סס oo 11000
Figure 76. Comparison of Search Time for Regular Graph with
Related Cost, Delay, and Bandwidth
55
Chapter VIII
Conclusions and Future Work
In this thesis, three heuristic for bounded delay constrained bandwidth least cost
(BD_CB_LC) problem were proposed. This problem is NPhard, and usually two kinds
of schemes are applied: heuristic scheme or approximation scheme. The three heuristics
proposed in this thesis used heuristic scheme. These three heuristics are based on
Dijkstra's algorithm, BFM algorithm, and Linear Lagrange relaxation.
All of the proposed heuristics find the feasible path at polynomial time. However,
the perfonnanccs are different. After the simulation and careful comparison, the
following conclusion can be drawn:
1. Regular Topology
There are much more routes III a regular topology than those in an irregular
topology that simulates the real world network. So it is difficult to find the least cost path
for a regular topology. In other words, more routes should be explored to find the least
cost path.
For the regular topology, BFM based heuristic can find the least cost path but
with a slightly longer search time and Dijkstra based heuristic needs least time on finding
the st path. The reason that BFM based heuristic can find the least cost path but with a
slightly longer search time is that during a sweep, a number of paths are initiated, which
means a large number of paths are considered for further extensions to feasible st paths.
56
So every node whose CLABEL gets updated during a sweep gets a chance to initiate a
new path for exploration and does not have to wait until it becomes pennanently labeled
as in the case of the Dijkstra based and LR based heuristics. So it is expected that BFM
based heuristic can find a better st path with lower cost. However, since more paths are
explored, BFM based heuristic needs the longer search time. Dijkstra based heuristic
needs least time on fmding the st path because fewer paths are explored comparoo with
BFM based heuristic. As for LR based heuristic, its run time is not the least and the st
path is not the best. The reason is that LR based heuristic calls Dijkstra algorithm a
number of times to search for st path, which is time consuming. So LR based heuristic
needs the longest run time. On the other hand, LR based heuristic combines cost and
delay together to find st path. Compared with Dijkstra based and BFM based heuristics,
which take into account the two metrics, delay and cost simultaneously, LR based
heuristic only considers the single mixed metric. Therefore, LR based heuristic is not
able to find the least st path compared with BFM based and Dijkstra based heuristics.
Analyzing the time complexity of each heuristic supports the above conclusion.
The time complexity for BFM based heuristic is O(mn), for Dijkstra based heuristic is
O(n2
), and for LR based heuristic is O(kn\ where m is the number of edges, n is the
number of nodes, and k is the number of called times of Dijkstra's al gorithm in LR based
heuristic. In a regular topology, the number of edges m is much greater than the number
of nodes n, so it is expected that BFM based heuristic needs longer run time than that of
Dijkstra based heuristic. Also for a regular topology, LR based heuristic should call
Dijkstra's algorithm a great number of times, which means k is large. So kn is greater
than m. Therefore, the time complexity is in the following order:
57
LR based heuristic> BFM based heuristic> BFM based heuristic.
2. Irregular topology
There are fewer possible routes in irregular topology compared with the regular
topology. The irregular graphs used for simulating the real existing network are
generated by Inet, which applies power law for network growing and evolving. Only a
few super routers dominate the traffic flow. This is reasonable since only a few large
cities have such super routers. So when exploring the st path, at least one of such super
routers (nodes or cities) must be selected. In other word, there are only a few possible
paths to select for routing. It is the reason that all three heuristics found the st path with
almost the same cost and delay.
However, these three heuristics have the different search times. The search time
of BFM based heuristic steadily increases with the number of nodes increasing, but still
keeps at a low level. The reason is that the irregular topology has few number of edges
compared with the regular topology. On the other hand, Dijkstra based heuristic takes
extra O(n1
) time to find the node with the smallest CLABEL value. So Dijkstra based
heuristic takes a slightly longer time than BFM heuristic.. The search time of LR based
heuristic is larger than that of Dijkstra based heuristic because LR based heuristic needs
to run a great number of Dijkstra's algorithm to find the st path. This can also be shown
by comparing the time complexity of LR based and Dijkstra based heuristics.
The heuristics proposed in this thesis could be applied for real network since these
heuristics were tested on the simulated networks with a large number of nodes. All the
heuristics performed well: They can find the feasible path with relatively small executing
time. However, they are only applicable for unicast routing problem. The future work
58
should focus on developing a heuristic for multicast routing and for distributed
environment.
59
References
[1] S. Chen and K. Nahrstedt, "An overview of quality of service routing for nextgeneration
lughspeed networks: problems and solutions," IEEE Network,
NovemberlDecember ]998, pp. 64  79.
[2] W. C. Lee, M. G. Hluchyi, and P. A. Humblet, "Routing subject to quality of service
constraints integrated communication networks," IEEE Network, vol. 9, no. 4,
July/August, 1995, pp. 46  55.
[3] Z. Wang and J. CrowcToft., "Bandwidthdelay based routing algorithms," IEEE
Proceedings ofGLOBECOM '95, vol. 3, 1995, pp. 2129  2133.
[4] Z. Wang and J. Crowcroft, "Qualityofservice routing for suppOliing multimedia
applications," IEEE Journal on Selected Areas in Communications, vol. 14, no. 7,
September 1996, pp. 1228  1234.
[5] M. R. Garey and D. S. Johnson, Computers and Intractability  A Guide to the Theory
ofNPComp{eteness, Freeman, California, USA, 1979.
[6] J. Chen and K. Nahrstedt, "On finding multiconstrained paths," Proceedings ofIEEE
ICC 98, Atlanta, GA, June 1998, pp. 874  879.
[7] Q. Ma and P. Steenkiste, "Qualityofservice routing with perfonnance guarantees,"
Proceedings of4111 InternationalIFIP Workshop, OoS, May 1997.
[8] G. Luo, K.Huang, J. Wang, C. Hobbs and E. Munter, "MultiQoS constraints based
routing for IP and ATM networks," Proceedings ofIEEE Workshop on QoS Support
for RealTime Internet Applications, June 1999, Vancouver Canada
[9]. R. Widyono , "The design and evaluation of Touting algorithms for realtime
channels," Technical Report, ICSI TR94024, University of California at Berkley,
International Computer Science Institute, June 1994.
[10] Q. Zhu, M. Parsa, and 1. J. CraciLunaAceves, "A sourcebased algorithm for
delayconstrained minimumcost multicasting," IEEE INFOCOM '95, MA, April
1995, pp. 377  385.
[11] V. P. Kompel/a, J. C. Pasquale, and G. C. Polyzos, "Multicast routing for
multimedia communications," IEEE/ACM Transactions on Networking, vol. 1, no. 3,
June 1993. pp. 286  292.
60
[12] Q. Sun and H. Langendorfer, "A new distributed routing algorithm with endtoend
delay guarantee," 2"d Workshop on Protocols Multimedia Syslenls, October 1995, pp.
452  458.
[13] H. Takahashi and A. Matsuyama, "An approximate solution for Steiner tree problem
in graphs," Mathematica Japanica, 1980.
[14] L. Kou, G. Markowsky and L. Berman, "A fast algorithm for Steiner tree," Acta
Informatica, vol. 15, 1981, pp. 141 145.
[15] R. Prim, "Shortest connection networks and some generalizations," Bell Systems
Technical Journal, vol. 36,1957, pp. 1389  1401.
[16] K. Lui, K. Nahrstedt, and S. Chen, "Hierarchjcal QoS routing in delaybandwidth
sensitive networks," Proceedings ofIEEE Conference on Local Computer Networks
(LCN 2000), Tampa, FL, November 2000, pp. 579  588.
[17] B. Chang and R. Hwang, "Dynamic update of aggregated routing infonnation for
hierarchical QoS routing in ATM networks," Parallel and Distributed Systems,
2001, pp. 653 660.
[18] B. Awerbuch, Y. Du, and Y. Shavit, "The Effect of network hierarchy structure on
perfonnance of ATM PNNl hierarcrncal routing," IEEE Computer Communications
and Networks, 1998, pp. 406  412.
[19] S. Pradhan, Y. Li, and M. Maheswaran, "QoSaware hierarchical multicast routing
on next generation intemetworks," IEEE International Conference on Performance,
Computing, and Communications, 2001, pp. 9 16.
[20] D. Reeves and H. Salama, "A distributed algorithm for delayconstrained unicast
routing," IEEE/ACM Transactions on Networking, Vol. 8 No.2, April 2000, pp. 239
 250.
[21] J. Jaffe, "Algorithm for finding paths with multiple constraints," Networks, vol. 14,
1984, pp. 95  116.
[22] H. F. Salama, D. S. Reeves, and Y. Viniotis, "A distributed algorithm for delayconstrained
unicast routing," IEEE INFOCOM '97, Japan, April 1997.
[23] S. Chen and K. Nahrstedt, "Distributed qualityofservice routing in high speed
networks based on selective probing," Technical Report, University ofIL at UrbanaChampaign,
Department of Computer Science, 19<,)8.
[24] K. G. Shin and C. C. Chou, "A distributed routeselection scheme for establishing
realtime channel," 6th IFfP, International Conference on High Peiformance
Networking, September] 995, pp. 319  329.
61
[25J V. P. Kompella, J. C. Pasquole and G. C. Polyzos, "Two distributed algorithms for
multicasting muLtimedia information," ICCCN '93, San Diego, CA, June 1993, pp.
343· 349.
[26] K. Carlberg and 1. Crowcroft, "Building shared trees using a onetomany joining
mechanism," Computer Communication Review, January 1997, pp. 5  11.
[27J G. Feng, C. Douligeris, K. Makki, and N. PissinoLl, "PerfOImance evaluation of
delayconstrained leastcost QoS routing algorithms based on linear and nonlinear
Lagrange relaxation," IEEE International Conference on Communications, Volume:
4, 2002, pp. 2273 2278.
[28] K. Thulasiraman and M.N. S. Swamy, Graphs, Theory and Algorithms, JohnWiley,
1992, New York.
[29] J. Winick and S. Jamin, "Inet3.0: internet topology generator,"
http://topology.eecs.umich.edu/inetl, Date accessed: December 2, 2002, Last
modified: June 4, 2002.
[30] M. Faloutsos, P. Faloutsos, and C. Faloutsos. "On powerlaw relationships of the
internet topology." Proc. ofACMSIGCOMM, 1999, pp. 251262.
62
Appendix A
Below is the source codes which incl LLde the network topology generation and
simulation.
import java.util.*;
import java.io.*;
class Simulation
{
static final int DELAY = 1;
static final int COST = 2;
static final int ADDITION = 3;
public static void main(String args[]) {
Network N=null;
II
0; i < fileNames. length; i++)
try
{
//File directory = new File ("revisedjreal_network") ;
//File directory = new File ("revisedjregularjrandom") ;
File directory = new File ("revised/regularjrelated") ;
String[] fileNames = directory.list();
String path = directory.getCanonicalPath();
System.out.println("Node\tEdge" + "\t" + "bound\t\t" + II
Dijk\t\t" + "BFM\t\t" + "\tLR");
System.out.println("\t\tdelay band I II + "cost delay
time I " + "cost delay time I "+"cost delay Lime
" ) ;
for (int i
N=new Network (path + File.separator + fileNames[i]);
System.out.print(N.numNode + "\t" + N.numEdge +"\t");
Date begin = new ~ate ();
System.out.println("By Dijkstrabased");
LHWHM (N);
Date after = new Date();
System.out.print{" II +(after.getTime()
begin.getTime ()) +" I ");
begin = new Date ();
System.out.println(IBFMbase");
BFM_Revised(N) ;
after = new Date();
System.out.print(" "+(after.getTime()
begin.getTime()) +" II);
begin = new Date ();
System.out.println("LRbased") ;
LR (N);
63
after = new Date();
System.out.println(" "+ (after.getTime() 
begin.getTime())) ;
System.out.println();
}
catch (Exception e)
(
System.out.println(e.getMessage(» ;
System. exit (1);
}
}//end of main
public static void LHWHM (Network N)
{
int CLABEL[]=new int[N.numNode];
int DLABEL[]=new int[N.numNode];
int D[]=new int[N.uumNode];
boolean PERM[]=new boolean [N.numNode] ;
int PRED[]=new int[N.numNode];
//initialization
compute_D(N,D) ;
for (int i=O;ieN.numNode;i++) {
CLABEL[i]=Network.INFINITY;
DLABEL[i]=o;
PERM[i]=false;
PRED[i]=i;
}
CLABEL[N.s]=O;
for (int i=O;ieN.numNode;i++){
int u=O;
int minCLABEL=Network.INFINITY;
//This for loop is to find the min cost node not
permanently labeled
for (int j=O;jeN.numNode;j++)
if (! PERM[j] && CLABEL[j}eminCLABEL)
u=j;
minCLABEL=CLABEL[j];
PERM[u]=true;
if (u==N.t) break;
for (int j=O;jeN.node[u] .edge.length;j++)
int edge=N.node[u] .edge[j];
int V;
if (u==N.edge[edge] .vertex[O])
v=N.edge[edge] .vertex[l];
64
else v=N.edge[edgeJ .vertex[O];
if (N.edge[edgeJ .bandwidth >= N.B)lladded by Zhentao Li
if (JPERM[v] && CLABEL[u]+N.edge[edge] .c<CLABEL[vJ
&& DLABEL[uJ+N.edge[edgeJ .d+D[v] <,,N.T )
CLABEL[v] =CLABEL[u] +N.edge[edge] .c;
DLABEL[v] =DLABEL[uJ +N.edge [edge] .d;
PRED[vJ=u;
}
}ller.d of for (int i
System.out.print(N.T) ;
System.out.print("\t" +N.B+"\t");
System.out.print(CLABEL[N.tJ+" "+DLABEL[N.t]);
}llend of LHWHM method
static void compute_D(Network N,int D[J) {
l/initialization
boolean PERM[]=new boolean [N.numNodeJ ;
for (int i=O;i<N.numNode;i++)
D[iJ=Network.INFINITY;
PERM[iJ=false;
}
N.t=N.numNodel;
D[N.t]=O;
for (int i=O;i<N.numNode;i++) {
int u=O;
int minD=Network.INFINITY;
for (int j=O;j<N.numNode;j++)
if (! PERM[j] && D[j)<minD)
u=j;
minD=D[jJ i
PERM[uJ=true;
for (int j=Oij<N.node~u].edge.lengthij++)
int edge=N.node[uJ .edge[j] i
int vi
if (u==N.edge[edge) .vertex[O])
v=N.edge[edge] .vertex[l] i
else v=N.edge[edge] .vertex[O] i
if (!PERM[v] && D[u]+N.edge[edge] .d<D[v])
D[v]=D[u]+N.edge[edge] .d;
}
}/Iend of for (int i
int maxD=Oi
for (int i=O;i<N.numNodeii++)
if (D [i ]>maxD) {
maxD=D[i] ;
N. s=i;
65
//System. out. println ("maxD=" +maxD) ;
N.T= (int) (maxD*2);
public static void BFM (Network N)
(
int CLABEL[]=new int[N.numNode];
int DLABEL[]=new int[N.numNode];
int D[]=new int[N.numNode];
int PRED[]=new int[N.numNode];
//initialization
compute_D(N,D) ;
for (int i=O;i<N.numNode;i++l {
CLABEL[i]=Network.INFINITY;
DLABEL[i] =0;
PRED~i]=i;
}
CLABEL [N. s] =0;
boolean update true;
while (update)
{
update = false;
for (int i=O;i<N.numNode;i++)
int u=i;
for (int j =0 i j <N. node [u] . edge. length; j ++)
{
int edge=N.node[u] .edge[j];
int Vi
if (u==N.edge[edge] .vertex[O])
v=N.edge[edge] .vertex[l];
else v=N.edge[edge] .vertex[O];
if (N.edge[edge] .bandwidth >= N.Bl//added
{
if (CLABEL[u] != Network.INFINITY
&& CLABEL[u] +N.edge [edge] .c<CLABEL[v]
&&LABEL[u]+N.edge[edge] .d+D[v]<=N.T )
CLABEL[v]=CLABEL[u]+N.edge[edge] .c;
DLABEL[v] =DLABEL[u] +N.edge[edge] .d;
PRED[v]=u;
update = true;
III
}
}//end of for (int j
}//end of for (int i
}//end of while
System.out.print(lf " + CLABEL[N.t]+"
public static void BFM Revised (Network N)
66
" +DLABEL[N.t]);
int CLABEL[]=new int[N.numNodeJ;
int DLABEL[]=new int[N.numNode];
int D[]=new int[N.numNode];
int PRED[]=new int[N.numNode];
//initialization
compute_D(N,D) ;
for (int i=Oji<N.numNode;i++) l
CLABEL(i] =Network. INFINITY;
DLABEL[i]=o;
PRED(i]=i;
}
CLABEL[N.s] =0;
boolean update
while (update)
{
true;
update = false;
for (int i=O;i<N.numEdge;i++)
int u = N.edge(i] .vertex[O];
int v = N.edge[i] .vertex[l];
if (N.edge[i; . bandwidth >= N.B)//added by Zhentao Li
{
if (CLABEL[u] != Network.INFINITY
&& CLABEL[u]+N.edge[i] .c<CLABEL[v]
&& DLABEL(u]+N.edge[i] .d+D[v]<=N.T
CLABEL[v]=CLABEL[u]+N.edge[i] .c;
DLABE~[v]=DLABEL(u]+N.edge[i].d;
PRED[v]=u;
update = true;
}
else if (CLABEL[v] != Network. INFINITY
&& CLABEL[v]+N.edge[i] .c<CLABEL[u]
&& DLABEL [v] +N. edge [i] . d+D (u] <=N. T
CLABEL[u]=CLABEL[v]+N.edge[i] .c;
DLABEL[u]=DLABEL[v]+N.edge[i] .d;
PRED[u]=vj
update = truej
}//end of for (int i
}//end of while
System.out.print(" " + CLABEL[N.tJ+" II +DLABEL[N.t]) j
public static Results Dijkstra (Network N, int option, double alpha)
{
int [] PRED = new int[N.numNode];
boolean[] PERM ~ew boolean [N.numNode] ;
doubler] LABEL = new double [N.numNode] ;
67
intI] CLABEL = new int[N.numNode];
intI] DLABEL = new int[N.numNode];
for (int i = 0; i < N.numNode; i++)
LABEL[i] = Network. INFINITY;
CLABEL[i] = Network. INFINITY;
DLABEL(i] = Network. INFINITY;
PERM [i] false;
PRED [i] = i;
}
LABEL[N.s] = 0;
CLABEL[N.s~ = 0;
DLABEL[N.s] = 0;
PERM[N.s] = true;
int u = N.s;
while (u != N.t)
{
for (int j = 0; j < N.'.1ode[u] .edge.length; j++)
int edge = N.node[~] .edge[j];
int V;
if (u == N.edge[edge] .vertex[O])
V = N.edge[edge] .vertex[ll;
else v= N.edge[edge] .vertex[O];
double comparison = 0;
if (option == DELAY)
comparison = N.edge[edge] .d;
else if (option == COST)
compari son = N. edge [edge] . c;
else if (option == ADDITION)
comparison = N.edge[edge].d + alpha*N.edge[edge] .c;
else
System.out.println("wrong selection");
System.exit(l) ;
}
if (!PERM[v] && LABEL [v] > LABEL[ul + comparison)
[
LABEL [v] = LABEL[u] + comparison;
CLABEL[v] = CLABEL[u] + N.edge[edge] .c;
DLABEL[v] = DLABEL[u] + N.edge[edge] .d;
PRED[v] = U;
}
}//endoE (for int j ...
int k = 0;
for (; PERM[k]; k++);
//Eind the first unlabeled node
u = k;
double minLABEL = LABEL[u];
k++;
for ( ; k <N.numNode; k++)
:f (I PERM [k] && LABEL [k] < minLABEL)
{
68
u = k;
minLABEL
}
PERM[u] = true;
}//end of while
LABEL[kJ;
III
return new Results (DLABEL[N.t], CLABEL[N.t]);
}//end of Dijkstra
public static void LR (Network N)
{
for (int i = 0; i < N.numEdge; i++)
if (N.edge[i] .bandwidth < N.B)
{
N. edge [i] . c
N.edge[iJ .d
Network. INFINITY;
Network. INFINITY;
}
Results q = Dijkstra (N, COST, 0);
if (q.delay <= N.T)
{
System.out.println (" II + q.cost + II II + q.delay);
return;
}
Results p = Dijkstra (N, DELAY, 0);
if (p.delay > N.T)
{
System.out.println(IINo route found");
return;
}
if (q.cost J= p.cost)
{
doubler] aggregate
boolean go = true;
while (go)
{
new double [N.numNode] ;
double alpha = (q.delayp.delay)/(p.cost q.
cost) ;
Results r = Dijkstra (N, ADDITION, alpha);
if (r.cost == q.cost I I r.cost == p.cost)
go = false;
else if (r.delay <= N.T)
P = r;
else q = r;
}//end of while
}//end of if (q.cost ...
System.out.print (" "+ p.cost +" II + p.delay);
}//end of LR
class Results
int delay, cost;
public Results (int delay, int cost)
{
69
this.delay = delay;
this.cost = cost;
~int vertex[]=new int[2];
Edge
inc. edge []
}
class Node
{
}
c~ass
{
Iiall edges connected to this node
int c' Ilcost
int d; Iidelay
int bandwidth;
public Edge (int vertexO,int vertexl,int c,int d, int bandwidth) {
vertex[O]=vertexO;
vertex[l]=vertexl;
this.c=c;
this.d=d;
this.bandwidth=bandwidth;
class Network
static final int INFINITY=1000000;
int s; Iisource
int t·, Iidestination
int T; Ilbound
:.nt B = 20; Ilbound of bandwidth
int numNode;
int numEdge;
Node node[] j
Edge edge [] ;
public Network(String fileName) throws Exception{
BufferedReader in = new BufferedReader(
new FileReader(fileName)) ;
String s = new String();
s = in.readLine();
StringTokenizer st = new StringTokenizer(s);
numNode=Integer.parseInt(st.nextToken()) ;
numEdge=Integer.parseInt(st.nextToken());
node=new Node [numNode] ;
edge=new Edge [numEdge] i
for (int i=O;i<numEdge;i++)
s=in.readLine() ;
st = new StringTokenizer(s);
70
import
import
public
{
int vertexl=Integer.parselnt(st.nextToken())j
int vertex2=Integer.parselnt(st.nextToken());
int cost=Integer.parselr.t(st.nextToken());
int delay=Integer.parselnt(st.nextToken()) i
int bandwidth=Integer.parselnt(st.nextToken())j
edge [i] =new Edge (vertexl,vertex2,cost,delay, bandwidth) j
in.close() j
int degree [] =new int[numNode] i
for (int i=Oji<numNodeii++) degree[i]=O;
for (int i=O;i<numEdgeii++) {
degree[edge[i] .vertex[O]]++;
degree[edge[i] .vertex[l]]++j
for (int i=O;i<numNodeii++)
node [i]=new Node();
node[i] .edge=new int [degree [i] ]j
for (int i=Oji<numEdge;i++)
for (int j=O;j<=l;j++) {
int vertex=edge[iJ .vertex[j];
node [vertex] . edge [ degree [vertex] ] =i;
}
}//end of public Network
J.ava .l.O. * ;
java.util.*;
class DataManipulation
public static void main (String [] args)
{
try
{
Random generator = new Random();
File pathName = new File("original");
String[] fileNames = pathName.list();
for (int i = 0; i < fileNames. length; i++)
{
BufferedReader fileIn = new BufferedReader(new
FileReader (loriginal/"+fileNames[il));
PrintWriter fileOut = new PrintWriter(new
FileWriter("related/" + fileNames[i]));
String oneLine = fileln.readLine();
fileOut.println (oneLine);
7l
e.printStackTrace() ;
}
catch
{
}
while ((oneLine = fileln.readLine()) != null)
{
StringTokenizer token = new StringTokenizer
(oneLine) ;
//String dummy = token. nextToken () ;// for brite
String first = token.nextToken();
String second = token.nextToken();
//randomly generate cost and delay from 1 to SO
int cost = Math.abs (generator.nextlnt ())%50;
//cost = 50 delay
int delay = 50  cost;
//randomly generate bandwidth from 18 to 50
//related bandwidth
int bandwidth = (int) ((cost+0.O)/delay)*30 + 18;
fileOut.println (first + "\t" + second + "\t" +
cost + "\t" + delay + "\t" + bandwidth);
}
fileln.close() ;
fileOut. close () ;
(Exception e)
72
1\VITA
ZHENTAOLI
Candidate for the Degree of
Master of Science
Thesis: A STUDY OF QUALITYOFOSERVICE ROUTING
Major Field: Computer Science
Biographical:
Personal Data: Born in Nei Mongol, China, March 1, 1970, son of Mr. Zhanyu Li
and Mrs. Fengxia Liu Li.
Education: Recei ved Bachelor of Science degree in Chemical Engineering from
Beijing Institute of Technology, China, in June 1992; completed the
requirements for Master of Science degree in Computer Science at the
Computer Science Department at Oklahoma State University in May
2002.
Professional Experiences: Teaching Assistant, Computer Science Department,
Oklahoma State University, August 2001 to December 2002; Research
Assistant, Chemical Engineering Department, Oklahoma State University,
JanuaryJ 998 to December 2000.