ON BOUNDED-DELAY MINIMUM-COST PATH
PROBLEM
By
YUANBINGDU
Bachelor of Art
Iinan University
Guangzhou, P.R.China
1996
Submitted to the Faculty of the
Graduate College of
Oklahoma State Uni ver ity
in partial fulfillment of
the requirement for
the Degree of
MASTER OF SCIE CE
May, 2003
ON BOUNDED-DELAY MINIMUM-COST PATH
PROBLEM
Thesis Approved:
WLt"l~-Thesis
Advisor
1I PREFACE
Real time applications over the Internet require guaranteed end-to-end quality of service (QoS). The task of QoS-ba ed routing is to find a route in the n twork which ha sufficient resources to satisfy the QoS requirement. One of the QoS-based routing problems ---the Bounded-Delay Minimum-Cost Path Problem (BDMCP) is NP-hard. Several heuristic algorithms including LHWHM algorithm and BFM-BDMCP algorithm have been proposed to find suboptimal solutions. In trus thesis, we propose a new heuristic algorithm called K-BFM-BDMCP which has better chance to find optimal solution than BFM-BDMCP and stm runs in polynomial time. We also do a comparative study of the new algorithm with BFM-BDMCP algorithm.
111 A OWLEDGEMENTS
Many thanks are gi en to my advi or, Dr. H.K. Dai, for hjs continuous upport and help on all aspects from technical to material. His guidance and advice helped me overcome many technical obstacles which otherwi e would take much more efforts.
Special thanks are given to Ruibin for his love and constant support, which make this long journey fuJI of joy.
I would like to thank Dr. Nohpill Park and Dr. Dougla Heisterkarnp for serving on my thesis committee and for their invaluable input.
Thanks also go to Iker Gondra, Shim Chow, Yong Hu and ling Ding for their help and support during my preparation for thesis defense.
The thesis is dedicated to my father and mother. It is their love, encouragement, belief and understanding that make everytmng I have possible.
IV TABLE OF CONTENTS
Chapter 1
Introduction , 1
1.1
Quality-of-Service 1
1.2
QoS-Based Routing 4
1.3
Bounded-Delay Minimum-Cost Path Problem (BDMCP) 9
1.4
Related Work 10
1.5
Scope of This Thesis 12
Chapter 2
Review of Related Algorithms ' , ' 13
2.1
Dijkstra's Algorithm 13
2.2
LHWfIM Algorithm 19
2.3
Bellman-Ford-Moore Algorithm '21
2.4
BFM-BDMCP 23
2.5
Pseudopolynomial Time Algorithms for BDMCP , 27
Chapter 3 A New Heuristic Algorithm 30
3.1
The Drawback of BFM-BDMCP 30
3.2
Improving BFM-BDMCP 31
3.3
K-BFM-BDMCP
..:
35
3.4
The advantage of K-BFM-BDMCP 44
Chapter 4
Experimental Evaluation 46
4.1
Test Graphs 46
4.1.1
Regular Graph 46
4.1.2
Irregular Graph 47
4.1.3
Generating Parameters 48
v 4.2 The Relationship between k and Performance of K-BFM-BDMCP .49ı
4.3 Comparison of BFM-BDMCP Algorithm and K-BFM-BDMCP Algorithm 51ı
Chapter 5 Conclusion and Future Work 57ı
References 59ı
Appendices 62ı
Code Lishngs 62ı
VI
LIST OF TABLES
Table 4-1: Comparison of the performance of cliffer nt k values .49
Table 4-2: Comparison using reguLar graph and random co ts and deLay 51
Table 4-3: Comparison using regular graph and related costs and delays 53
Table 4-4: Comparison using irregular graph and random costs and deLays 54
Table 4-5: Comparison using irregular graph and related costs and delay 55
vii LIST OF FIGURES
Figure 1-1: A QoS-based routing example 4
Figure 1-2: An ex.ample of network with bandwidths and delays 8
Figure 1-3: An ex.ample ofBDMCP problem 10
Figure 2-1: Procedure relax(u,v) 14
Figure 2-2: Dijkstra's algorithm 15
Figure 2-3: Network N* 16
Figure 2-4: Initialization 16
Figure 2-5: Iteration 1 17
Figure 2-6: Iteration 2 17
Figure 2-7: Iteration 3 17
Figure 2-8: Iteration 4 , 18
Figure 2-9: Iteration 5 " 18
Figure 2-10: Iteration 6 18
.
Figure 2-11: Modified-relax procedure 20
Figure 2-12: LHWHM algorithm 21
Figure 2-13: BFM algorithm 22
Figure 2-14: BFM-BDMCP algorithrn 24
Figure 2-15: Initialization 25
Figure 2-16: Sweep 1. 25
Figure 2-17: Sweep 2 26
Figure 2-18: Sweep 3 26
Figure 2-19: Dynamic-Programming A 28
VlIl Figure 2-20: Dynamic-Programming-B. 29
Figure 3-1: A simple example of BDMCP problem 30
Figure 3-2: Solution found by BFM-BDMCP 31
Figure 3-3: Initialization 32
Figure 3-4: Sweep 1. '" 32
Figure 3-5: Sweep 2 32
Figure 3-6: An optimal algorithm for BDMCP 34
Figure 3-7: The execution of OPTIMAL-BFM-BDMCP 34
Figure 3-8: K-BFM-BDMCP algorithm 38
Figure 3-9: The execution of K-BFM-BDMCP 39
Figure 3-I0: Initialization 42
Figure 3-11: Sweep 1 42
Figure 3-12: Sweep 2 43
Figure 3-13: Sweep 3 43
Figure 3-14: Sweep 4 44
Figure 4-1: Regular graph H4,8' 47
Figure 4-2: Cost comparison of the performance of different k values 50
Figure 4-3: Time comparison of the pertonnance of different k value 50
Figure 4-4: Cost comparison using regular graph and random costs and delays 52
Figure 4-5: Time comparison using regular graph and random costs and delays 52
Figure 4-6: Cost comparison using regular graph and related costs and delays 53
Figure 4-7: Time comparison using regular graph and related costs and delays 54
Figure 4-8: Time comparison using ilTegular graphs and random costs and delays 55
IX 56
Figure 4-9: Time comparison u ing irregular graph and r lated costs and delays
x
Chapter 1 Introduction
The Internet has been around for nearly twenty y ars and it keeps growing rapidly in terms of speed, size and user. But so far the underlying protocols have not changed and the Internet can still only provide "best-effort' service, which means it will try its best to forward network traffic, giving better service to some traffic at the expense of giving worse to the rest. While traditional applications (such as File Transfer Protocol and email) work fine with this kind of service, newly emerged real time applications (such as video-conferencing and Video on-Demand) are having a hard time because they require high bandwidth, low delay and small jitter. In other words, these new applications require better transmission service than "best-effort". Quality-of-Service (QoS) is a framework that is being developed to bring down the disparity and unfairness in the usage of Internet resources such that a set of service requirements by the users can be satisfied. To provide QoS in the Internet, many technique have been propo ed and studied, one f which i QoS-based routing. The aim of QoS routing is to determine path based on Qos parameters such as delay, jitter, bandwidth, loss probability and other end-to-end quality features. The proposed thesis will be dealing with QoS-ba ed routing problems.
1. 1 Quality-or-Service
Definitions
The notion of Quality-of-Service has been proposed to capture the qualitatively or quantitatively defined performance contract between the service provider and the user applications. A defined in [1], QoS is ' a set of service r quirements to be met by the network while transporting a flow". The ervice requirements are expre ed in some measurable QoS rnetrics.. Well-known metrics include bandwidth, delay, jitter, monetary cost, etc.
QoS M.etrics
Bandwidth
Bandwidth is defined as the difference between the highest and lowest frequencies of a transmission channel. It is used to measure how fast data flows on a given transmission path and is expressed as data speed in bits per second (bps). Now, what we are interested most is the available bandwidth, which refers to the residual bandwidth that could be used to route traffic on a particular link.
Delay Delay refers to the time taken for a packet to travel from the source to the de tination. The most direct way to determine the delay is to send a packet from the source to the destination and the destination is required to send back immediately. By mea uring the round-trip time and dividing it by two, we can get the delay.
Jitter
Jitter is defined as the amount of variation in th'e end-to-end packet transit time. It happens due to the varying sizes of packets of a given flow, which result in differences in delay while the packets are delivered. Jitter plays a very important role in rea] time
2
applications such as audio and video transmission. A high jitter will give an uneven quality to sound or image.
Monetary Cost Monetary cost is the cost incurred when the users are required to pay for u ing the Internet resources.
UsuaUy, different metrics may have different feature. There are three types of metrics: additive, multiplicative, and concave [9]. They are defined as follows.
Let m(nl,n2) be a metric for link(nJ,nz). For any path P =(nl' nz, ..., nj_l, nj), the metric m is: (Note here n" n2, n ..., nj_] , nj represent network nodes.)
•
Additive: if m(P) =m(n"n2) + m(n2,1t ) +... + m(nj_I,llj) Examples are delay, jitter, cost and hop-count. For in tance, the delay of a path is the sum of the delay of every hop.
•
Multiplicative: if m(P) =m(nl,n2) x m(n2,n3) x ... x m(nj_l,nj)
An example is reliability, in which case 0 ~ m(ni, ni+') ~ 1 for l~ i ~j-l.
•
Concave: if m(P) =min{ m(nr,n2) , m(n2,1t3) , ... , m(nj_l,nj) } An example is bandwidth, which means that the bandwidth of a path is determined by the link with the minimum available bandwidth.
3
1.2 OoS-Based Routing
Definitions QoS-based routing is defined in [1] as: "A routing mechanism under which paths for flows are determined based on some knowledge of resource avai Lability in the network as well as the QoS requirement of the flows." Here, the QoS requirement of a flow is given as a set of constraints such as avaiLable bandwidth, cost, delay, link and end-to-end path utilization, and induced jitter. The basic function of QoS-based routing is to find a network path to satisfy the given constraints. In addition, most QoS-based routing algorithms consider the optimization of resource utilization.
Figure 1-1 shows a simple example of QoS-based routing. Suppose that there is a traffic
flow from node A to node C which requires 4M bps bandwidth. A we can see, although
path A~B~C is shorter, which has 2 hops, it wil.l not be eLected becau e it do s not
have enough bandwidth. Instead, path A~D~E~C i selected.
Figure I-I: A QoS-based routing example. 4 Objectives of QoS-Based routing
The main objectives of QoS-Based TOuting are:
•
First, to find a path that has a good chance of meeting the QoS requjrements of end users. At the same time, this should be done dynamically so that enable the routing to select a path among several feasible paths based on orne policy constraints.
•
Second, to optimize the network resource usage. A network QoS-based routing scheme can aid in the efficient utilization of network resources by improving the total network throughput.
•
Third, to degrade network performance gracefully when things like congestion happen. When network is in heavy load, QoS-based routing is expected to give better performance (e.g., better throughput) than best-effort routing, which can degrade the performance dramatically.
Requirements for QoS-Based Routing Algorithm
The current Internet routing protocols are based on two routing algOlithms -Di tance Vector algorithm and Link-State algorithm. In Di tance Vector algorithm, neighboring routers exchange routing information periodically. Thus every router can learn the routing information from others. Based on that information, the shortest path to every destination can be computed. An example is the well-known Routing Information Protocol (RIP). This is also called Bellman-Ford-Moore algorithm.
5
While in Link-State algorithm e ery rout r ad erti it link tate information to the
whole network, thus every router can r ceive the link-tat information. Such information is maintained in a local database in every router, from whjch the routing table is calculated using Dijkstra's algorithm. The ad erti ing is triggered by events and it also happens periodicaJIy. An example is the Open Shortest Path First (OSPF) protocol.
Below are some basic requirements for QoS-based routing algorithms:
•
The algorithms should be efficient and calable enough that they can be used for large network.
•
The algorithms should not be so complicated that they can be implemented easily.
•
The algorithms should be suitable to current Internet architecture.
Note that some of them are conflicting with each other, so that compromise has to be made. We have to make orne trade off betw en efficiency and c mplexity.
QoS-based routing algorithms are expected to be employed in cun'ent Internet. They must be easy to implement and compatible with the current "best-effort" routing protocols.
QoS-Based Routing Problems
The QoS-based routing problems can be divided into two major classes: unicast routing and multicast routing. The unicast routing problem refers to fincting the best feasible path between a single source and a single destination, which satisfies a set of QoS requirements. On the other hand, multicast routing problem refers to finding the best
6
feasible tree covering a single source and a et of destinations which atisfya et of QoS requirements. This thesis deals with solving unicast routing problem.
Unicast routing problems can be further partitioned into sub-c.las es based on the type of QoS metric that is used for routing. For the concave QoS metric such as available bandwidth, the state of a path is determined by the state of the bottleneck link. For example, in Figurel-2, the bandwidth of the path S~A~B~C is 1, which is the bandwidth of the bottleneck link (A. B). For these metrics, two basic routing problems can be defined. One is called link-optimization routing. An example is the bandwidthoptimization routing, which is to find a path that has the largest bandwidth on the bottleneck link. The other problem is called link-constrained routing. An example is the bandwidth-constrained routing, whi.ch is to find a path whose bottleneck link bandwidth is above a required value.
For additive metrics such as delay, delay jilt r and cost, the state of a path is determined by the combined state over all links on the path. For example, in Figurel-2, the delay of the path S~A~B~T is 7, 'which is the total delay of all links on the path. For these metrics, two basic routing problems could be defined. One is path-optimization routing. An example is the least-cost routing, which is to find a path whose total cost is minimized. The other problem is path-constrained routing. An example is the delayconstrained routing, which is to find a path whose delay is bounded by a required value. The above four basic problems can be combined into many different routing problems. For example, the bandwidth-constrai.ned least-delay routing problem belongs to the link7
constrained path-optimization problem. The delay-constrained lea t-cost routing problem belongs to the path-constrained path-optimization problem. There are some other problems such as Link-constrained path-constrained routing and path-constrained linkoptimization routing.
The problem with which we are dealing in this thesis is a path-constrained pathoptimization problem, which we call the Bounded-Delay Minimum-Cost Path Problem.
bandwidth, delay •
------I
• T
Figure 1-2: An example of network with bandwidths and delays.
8
1.3 Bounded-Delay Minimum-Cost Path Problem (BDMCP)
In this section, we will introduce the Bounded-Delay Minimum-Cost Path Problem (BDMCP).
Let R+ denote the set of all positive real numbers. Given a network N r presented by a directed graph G(V,E), a source vertex s, a destination vertex t, a cost function c: E~R+ , a delay function d: E~R+, and a constant Te R+, an instance of BDMCP problem BDMCP(N,s,t,n is to find a path p from s to t (p is thus called an s-t path) such that d(p)'.'5:.T with smallest c(P) if such a path exists.
An s-t path p which satisfies d(P)5:T is called a feasible path. We assume that both functions c and d are additive in the sense that the value of function (d, re pectively) of a path is equal to the summation of the values of function c (d, r spectively) of all edges on the path.
An undirected graph may be viewed as a directed graph with each link e =(u, v) replaced by two oppositely oriented links e, = (u, v) and e2 = (v, u). In this case c(e,) = c(e2) and dee,) =d(e2)' For e =(u, v), c(e) and dee) are also denoted as cu.v and du•v respectively.
Figure 1-3 shows an example ofBDMCP problem with the delay constraint of 50.
9
T=50
uv
30,40
Figure 1-3: An example of BDMCP problem.
In the above example, there exist a number of feasible s-t paths such as
s 5.JO ) 1 5.10 )3_40=.J0~) t and s 6,5 ) 2 14,5 )3 7,10 ) 4 3,10 ) t , with cost 50
and 30 respectively. The latter is the feasible minimum-cost path.
Throughout the thesis, we use n to denote IVI and m to denote lEI unles otherwise stated.
1.4 Related Work
Wang and Crowcroft [5] proved that the problem of finding path subject to two or more additive constraints is NP-complete. The corresponding decision problem of BDMCP is the problem of finding paths subject to two additive constraints. So BDMCP problem is NP-hard. Wang and Crowcroft also presented a centralized algorithm and two distributed algorithms for finding paths in a network satisfying bandwidth and delay constraints.
10
Widyono [24] proposed a routing method that gi e the optimal path having the lowest possible cost without violating the delay constraint, unfortunately with an exponential running time. The constrained Bellman-Ford (CBF) routing algorithm performs a breadth-first search, discovering paths of monotonically increasing delay while recording and updating lowest cost path to each node it visits. It stops, when the highest constraint is exceeded, or there is no more possibility of improving the paths. It al 0 has exponential worst-case running time.
Chen and Nahrstedt[ll] have done a comparison study of algorithms that have been proposed for QoS-based routing for both unicast and multicast routing.
Hassin[23] presented a full polynomial approximation scheme for the BDMCP problem one of which runs in time O(log 10g(UIL)[IEllVle-1+1og 10g(U/£))) where U and L denote the upper bound and lower bound of the cost respectively. Later works improved Rassin's algorithm with better complexity propertie . However, these approximation algorithms are computationally expensive and not easy to implement.
Luo et al. [5] proposed a simple heuristic algorithm called LHWHM algorithm for the BDMCP problem. This algorithm is based on Dijkstra's algorithm and performs well on sparse graphs.
Most recently, Ravi et al. [8] designed a new heuristic algorithm called BFM-BDMCP and it is based on Bellman-Ford-Moore algorithm. It is also suitable for distributed
11
implementations. They have also done a comparative evaluation and the experimental results showed that LHWHM algorithm and BFM-BDMCP algorithm are erious candidates for implementation in real network environment.
1.5 Scope of This Thesis
This thesis is concerned with the design and analysis of heuristic algorithms for the BDMCP problem. The thesis is organized as folJows.
In Chapter 2, we review two classic algorithms for shortest path problem and two major existing heuristic algorithms, LHWHM algorithm and BFM-BDMCP algorithm, for BDMCP problem. We also review two pseudopolynomial time algorithms for BDMCP. In Chapter 3, we discuss the drawback of BFM-BDMCP algorithm and propose an improved version of BFM-BDMCP algorithm called K-BFM-BDM P. Then w pr ve that K-BFM-BDMCP runs in polynomial time and discu its advantage over 8 MBDMCP. In Chapter 4, we present our experimental results.
12
Chapter 2 Review of Related Algorithms
In this chapter, we review several exi ting algorithms that are related to BDMCP problem. Dijkstra's algorithm and BeJlman-Ford-Moore algorithm are classic algorithms for shortest-path problem. LHWHM algorithm and BFM-BDMCP are heuristic algorithms for BDMCP problem. They are based on Dijkstra s algOlithm and BeUmanFord-Moore algorithm respectively. At the end of this chapter, we review two pseudopolynomial time algorithms for BDMCP problem which we will use for evaluating our algorithms.
2. 1 Dijkstra's Algorithm
Dijkstra's algorithm solves the single-source shortest-path problem on a weighted, directed graph G =( V, E) for the case in which all edge weights are nonnegative. In this section, we assume that we are to solve a problem related to the two major h uri tic algorithms for BDMCP presented in this chapter: given an in tance of BDM P(N,s t,n, find the minimum delay path from de tination t to every vertex in V.
First we construct a network N* by reversing the direction of all links in N and treat destination node t as the source node in N*. We will apply Dijkstra's algorithm to N*.
Dijkstra's algorithm proceeds as follows. The algorithm associates three attributes with each node u, namely, DLABEL(u), PERM(u) and PRED(u). At any step in this algorithm DLABEL(u) represents the delay of a path from node t to node u, PERM(u) indicates
13
whether a node u has been pennanently labeled or not, and PRED(u) indicates the node
from which node u has received its Latest DlABEL value.
Dijkstra's algorithm uses the technique of relaxation. The process of relaxing an edge (u,v) consists of testing whether we can improve the minimum-delay path to v found so far by going through u and, if so, updating DLABEL(v) and PRED(v). A relaxation step may decrease the value of the minimum delay path estimate DLABEL(v) and update v's predecessor field PRED(v). The following code performs a relaxation step on edge (u,v).
PROCEDURE relax(u,v)
1.
if DLABEL(v»DLABEL(u)+ du,v then
2.
DLABEL(v):=DlABEL(u)+ d",v
3.
PRED(v):=u
END
Figure 2-1: Procedure relax(u,v).
Initially, we have DlABEL(t) = 0 and DLABEL(u) = 00 for u :f. t, PERM(t) =1 and PERM(u) = 0 for u:f. t and PRED(u) =u for all u E V. The algorithm repeatedly selects a node, say u, from the nodes not yet permanently labeled which has the minimum
DLABEL value, set PERM(u) =1 and relax all edges leaving u. This continues until a11 the nodes are permanently labeled.
14
ALGORITHM Dijkstra(N*,t)
1.
DLABEL(t):=O
2.
PERM(r):=1
3.
foreach vE V(N*)
4.
if #t then
5.
DLABEL(v):=oo
6.
PERM(v):=O
7.
PRED(v):=v
8.
u:=t
9.
for each vertex v adjacent to u
10.
relax(u,v)
11.
from all the nodes which are not yet permanently labeled, pick a node u with smaIJest . DLABEL value and set PERM(u):=l
12.
!fno such u exists, HALT
13.
goto 9 END
Figure 2-2: Dijkstra's algorithm.
At termination, the predecessor array PRED can be used to trace the minimum delay path generated by the algorithm. The main feature of Dijkstra's algorithm is that the label DLABEL(u) of a pennanentIy labeled node u is the delay of a minimum delay t-u path. So once a node is labeled permanently, no further labeling of this node is necessary.
15
From a recently permanently labeled node It, the algorithm extends the minimum delay path t-u to a t-v path where v is a neighbor of u. Dijkstra s algorithm runs in o(n2).
A formal description of Dijkstra's algorithm is given in Figure 2-2.
Let us apply Dijkstra's algorithm to the example of BFMCP problem in Figure 1-3. First we obtain the network N* showed in Figure 2-3:
10
40
Figure 2-3: Network N*. Then we proceed as follows:
10
(0)
40
t
DLABEL
Figure 2-4: Initialization.
16
10
40
Figure 2-5: Iteration 1.
10
40
Figure 2-6: Iteration 2.
10
Figure 2-7: Iteration 3.
17
Figure 2-8: Iteration 4.
40
Figure 2-9: Itcrution S.
10
40
Figure 2-10: Iteration 6.
18
2.2 LHWHM Algorithm
The LHWHM algorithm is based on Dijkstra's algorithm. It wa propo ed by Luo, Huang, Wang, Hobbs and Munter in [5]. It finds suboptimal solution to BDMCP problem.
Definition 2.1. A cost-delay label is a 2-tuple (c,d) where C and d are nonnegative real numbers and denote cost and delay respectively.
The algorithm associates four attributes with each node u, namely, LABEL(u), PERM(u), D(u), and PRED(u). The attribute D(u) stores the delay of a minimum delay u-t path which can be done easily by applying Dijkstra's algorithm to the network N·, which is obtained by reversing the directions of all links in the given network, using the link delays and using node t as the source. We have shown how thi is done in the previou section. At any step in this algOlithm LABEL(u) (i a cost-delay label) repre ents the co t of a path from node s to node u and the delay of a path from node s to node u. The attribute PERM(u) indicates whether the node u ha been permanently labeled or not, and PRED(u) indicates the node from which node u ha received its late t LABEL value.
LHWHM algorithm uses a modification of relax procedure u ed in Dijkstra's algorithm. It is showed in Figure 2-11.
19
PRECEDURE modified.relax(u,v)
1.
if LABEL(u).delay+dll,1' +D(v)~T and then LABEL(u).cost+cu,1' < lABEL(v).COSf then
2.
lABEL(v).cost:=lABEL(u).COSH CIII'
3.
lABEL(v).delay:=lABEL(u).delay+ dll,v
4.
PRED(v):=u
END
Figure 2-11: Modified-relax procedure.
A fonnal description of the LHWHM algorithm is given below.
ALGORITHM LHWHM(N,s,t,n
1. Construct a network N* by reversing the directions of all links in N . Apply Dijkstra's algorithm on N* (using delays, instead of costs) and calcul.ate for each node u the value of D(u), the delay of a minimum delay path from t to u
2.
IABEL(s):=(O,O)
3.
PERM(s):=l
4. for each v E V
5.
if v:;z!:s then
6.
LABEL(v):=(oo,O)
7.
PERM(v):=O
8.
PRED(v):=v
9.
u:=s
20
10.
for each vertex v adjacent to u
11.
modified-rel ax(u,v)
12.
from all the nodes which are not yet permanently labeled, pick a node u with the smaJJest cost of LABEL value and set PERM(u):=l
13.
If no such u exists, HALT
14.
goto 10
END
Figure 2-12: LHWHM algorithm.
2.3 Bellman-Ford-Moore Algorithm
The Bellman-Ford-Moore algorithm (BFM for short) solves the single-source shortestpaths problem in the more general case in which edge weights can be negative. Since for BDMCP problem, all the edge weights (costs and delays) are nonnegative, BFM seems no better than Dijkstra's algorithm. But BFM doe have orne propelties that make the heuristic algoritlim for BDMCP based on it outperform LHWHM algorithm. We will come back to this in the next section.
Again, we present BFM by using it to solve the same problem as in Section 2.1. The BFM algorithm associates with each node u two attributes DLABEL(u) and PRED(u). Initially DLABEL(t) =0, DLABEL(u) = 00 ,for all u E V and u :1= t and PRED(u) =u for all
u E V.
21
Like Dijkstra's algorithm, the BFM algorithm u es the techniqu of relaxation,
progressively decrea ing an estimate DLABEL(v) on the delay of a minimum-delay path from the source t to each vertex v in V until it achieves the actual minimum-delay path delay. On the other hand, unlike Dijkstra s algorithm in which just relaxing all the outgoing edges of a particular node during one iterati,on, the BFM algorithm relaxes all outgoing edges of all nodes (we call relaxing all outgoing edges for a node when scanning that node) during one iteration, which is caUed a sweep. It keeps weeping until no relaxation in a sweep succeeds to update the DLABEL value of any node.
A formal description of the BFM algorithm (asynchronous version) is given below:
ALOGORITHM BFM(N*,t)
1. DLABEL(t):=O
2.
for each v E V
3.
if v:t-t then
4.
DLABEL(v):=00
5.
PRED(v):=v
6.
for each edge (u,v) E E
7.
relax(u,v)
8.
If no node's DLABEL value is updated during the previous sweep, HALT
9.
goto 6 END
Figure 2-13: BFM algorithm.
22 It can be shown that after performing n-l sweeps the BFM algorithm will terminate,
resulting in the time complex,ity of O(nm). The above implementation of the BFM
algorithm permits two choices which are presented below.
Version 1 (Asynchronous)
While scanning a node u during a sweep, use the current value of DLABEL(u) to label the
neighbors of node ll.
Version 2 (Synchronous)
While scanning node u during a sweep, use the value of DLABEL(u) at the end of the
previous sweep for updating the labels of the neighbors of node u.
2.4 BFM-BDMCP
The BFM-BDMCP algorithm [7J for the BDMCP problem is based on the BPM algorithm. As in the case of the LHWHM algorithm, we first compute D(u) for each node u where D(u) is the minimum delay of any u-t path. Again each node u is a sociated with the attributes LABEL(u) and PRED(u).
The BFM-BDMCP algorithm also uses the technique of modified relaxation as m LHWHM.
23
A formal presentation of the BFM-BDMCP algorithm (asynchronous ver ion) is as follows:
ALGORITHM BFM·BDMCP(N, l 7)
1. Construct a network N· by reversing the directions of all link in N. Apply Dijkstra' algorithm on N· (using delays, instead of costs) and calculate for each node u the value of D(u), the delay of a minimum delay path from t to u
2. lABEL(s):=(O,O)
3.
foreachv E V
4.
if v;cs then
5.
LABEL(v):=(oo,O)
6.
PRED(v):=v
7.
for each (u,v) E E
8.
rnodified-relax(u,v)
9.
if no node's LABEL value is updated during the previou sweep, HALT
10.
goto 7 END
Figure 2-14: BFM·BDMCP algorithm.
Let us apply BFM-BDMCP algorithm (synchronous version) to the example in Figure 13.
24
D(s) =20
D(s) =20
(0,0)
D(l) =20 (00,0)
5,10
T=50 D(t) = 0
30,40
Figure 2·15: Initialization.
D(l) =20 (5,30)
5,10
T=50 D(t) = 0
(6,5) D(2) =15
(00,0) D(4) =10
Figure 2-16: Sweep 1.
25
T=50
5,10
D(s) =20 D(t) = 0
30,40
(6,5) D(2) = 15
Figure 2-17: Sweep 2.
D(1) =20 T=50 (5,30)
D(s) =20 D(t) =0
(6,5) D(2) =15
Figure 2-18: Sweep 3.
Suppose while labeling from node u, the LABEL(v) of neighbor node v is updated. We can view this as "node u initiating a wave to node v". Basically this mean that node u has extended a current s-u path to an s-v path.
26
In the case of the LHWHM algorithm, during an iteration only one node (the most recently permanently labeled node) is scanned. Thus at most n new wave (equivalently paths) are initiated. And only one of these waves gets cho en for propagation of wave in the subsequent iteration. In fact, at most n-l waves will get a chan e to propagate new waves during the entire algorithm. On the other hand, in the case of the BFM-BDMCP algorithm, an iteration corresponds to a sweep, that is, the scanning of all the nodes of the network. This means that during a sweep a number of waves are initiated. Therefore a large number of paths become considered for further extensions to feasible s-t paths. This is because every node v whose LABEL(v).cost gets updated during a sweep gets a chance to initiate a wave (a new path) for exploration and does not have to wait until it becomes permanently labeled as in the case of the LHWHM algorithm. It is for this reason that the BFM-BDMCP algorithm is expected to outperform the LHWHM algorithm in terms of the cost of the solution.
Ravi[7] proved th'at the BFM-BDMCP algorithm terminate with a feasible s-t path ifone such path exists.
2.5 Pseudopolynomial Time Algorithms for BDMCP
Although BDMCP problem is NP-hard, it can be solved by pseudopolynomial algorithm[16]. Thus if the input numbers are uniformly bounded it is polynomially solvable. The pseudopolynomial algorithm uses the idea of dynamic programming.
Dynamic programming can be applied to problems which can be solved by combining the solutions to subproblems and the subproblems are not independent. A dynamic27
programming algorithm solves every subproblem just once and aves its an wer in a table, therefore avoiding the work of recomputing the answer every time the ubproblem is encountered.
There are two dynamic programming algorithms for BDMCP:
Algorithm A.
Let I/x) denote the cost of a shortest path from s to j, such that the delay of the path is at
most x. Assume that diJ > 0 for all (i,j) E E.
ALGORITHM Dynamic-Programming-A(N,s,t,T)
1.
for each vertex j E V do
2.
ifj :f. s then I/O): =00
3.
for x:=O to T
4. f.~(x):= 0
5.
for x:=l to T
6.
for each vertex j E V do
7.
ifj =I-s then
8.
!j(x):= min {fix-I) , min ke ~tJ{ I k(X -dkJ) + Ckj }}
9.
return I t(T) END
Figure 2-19: Dynamic-Prograinming A. This algorithm runs in O(nT).
28
Algorithm B.
Let gj(e) denote the time of a quicke t path from s to j, such that the co t of the path is at
most e.
ALGORITHM: Dynamic-Programming-B(N,s,t,1)
1. for each vertex j E V do
2. ifj :t s then g/O):= 00
3. for e:=O to OPT
4. g s(c):=O
5.
for e:=l to OPT
6.
for each vertex j E V do
7.
if} :t s then
8.
g JCe):=min{ g j(e-I) , min keVJ C~Ct) g k(e -ekJ) + dkJ }} END
Figure 2·20: Dynamic.Programming.n.
Here OPT is the optimal solution of BDMCP problem. In the above algorithm, OPT is not know a priori, but it satisfies that OPT=min {el gt(e)$T}. Thus OPT is th fir t value of c for which gt(e)~T. This algorithm runs in time O(m·O?1).
29
Chapter 3 A New Heuristic Algorithm
According to [8], LHWHM algorithm performs well on spar e networks and BFMBOMCP algorithm generally outperfonns LHWHM algorithm. But till, they fail to find the optimal solutions for some networks since they are just heuristic algorithms for BOMCP problem. In this chapter, we present an improved versi.on of BFM-BDMCP, called K-BFM-BDMCP, which has better chance than BFM-BOMCP to find optimal solutions yet still runs in polynomial time.
3. 1 The Drawback of BFM-BDMCP
Why does BFM-BOMCP algorithm fail to find the optimal solution for some networks? To answer this question, let us first look at the following simple example of BOMCP problem:
T=5
4,1
1,2
Figure 3-1: A simple example of BDMCP problem. When applying BFM-BOMCP algorithm to this network, we have the feHewing result:
30
1,4 4,1
2,1 1,2
Figure 3-2: Solution found by BFM-BDMCP.
BFM-BDMCP algorithm found the solution of (5,5) and the conesponding s-t path is
s 1,4) 1 4,1) t . But obviously the optimal solution for this example is (3,3) and the
optimal s-t path is s 2,\) 1 1,2) t . The reason why it fails to find the optimal solution
is that it measures the goodness of a cost-deJay label only by cost and does not take delay into account. In the above example, two possible cost-delay labels for node 1 are (1,4) and (2,1), but the label (2,1) which would lead to the optimal solution was discarded because its cost value is greater than that of the label (1,4), though its delay value is less than that of the label (1,4).
Note that the LHWHM algorithm also suffers from the same problem, namely, when a node has obtained several cost-delay labels that all have chance to get to the optimal solution, it.just blindly gambles on the one that has the smallest cost value.
3.2 Improving BFM-BDMCP
The cause of the problem with BFM-BDMCP algorithm is that each node holds one costdelay
label. Intuitively, the possible remedy for this problem would be increasing the
memory of each node so that more labels could be stored in each node to initiate waves to
31
the neighbors. For in tance if we aIlow each node to tor up to three co t-delay I.abels
in BFM-BDMCP, and during each weep every label stored in each node needs to initiate waves to the neighbor nodes, we expect to find better solutions. Let us apply this strategy to the example in Section 3.1:
1,4 4,1
(0,0)
2,1 1,2
Figure 3-3~ Initialization.
1,4 4,1
(0,0)
2,1 1,2
Figure 3-4: Sweep 1.
1,4 4,1
D(s) = 2 D(t) = a
(3,3)
(0,0)
(5,5)
(4,2)
(6,2)
2,1 1,2
Figure 3-5: Sweep 2.
In this case, we found not only better solution than that of BFM-BDMCP algorithm, but also the optimal solution. In fact, if each node had infinite memory to remember as many
32
cost-delay labels as it should remember, the optimal solution would guarantee to be found. Based on this idea, an optimal algorithm based on BFM-BDMCP algorithm for BDMCP problem can be obtained. Note that we use "optimal" only to mean that thi algorithm is able to find the optimal solution.
In this optimal algorithm, we associate each node with a set of cost-delay labels instead of just one cost-delay label as in BFM-BDMCP. The algorithm takes n-l sweeps and stores all the cost-delay labels for node v generated during the ith sweep in LABEL(v,i). Initially, LABEL(s,O)={ (O,O)} and LABEL(v,O)=¢ for #s. Every label in LABEL(v,i) needs to initiate waves to the neighbor nodes of v during the (i+ 1)st sweep.
Below is the formal description of the optimal algorithm.
ALGORITHM OPTIMAL.BFM·BDMCP(N,s,t)
1.
use Dijkstra's' algorithm or BFM algorithm to compute D(v) for every v E V
2.
for each v in V do
3.
lABEL(v,O):= ¢
4.
LABEL(s,O):={ (O,O)}
5.
for i:=1 to n-l do
6.
for each v E V do
7. LABEL(v,i):=LABEL(v,i-l)
8.
for each edge(u,v) E E do
9.
for each cost-delay label (c,d) in LABEL(u,i-l) do
33
10. (C d ):=(c+clI,v, d+dll,v) ll. if d +D(v) ~ T then
12. LABEL(v i):=IABEL(v,i) u {(c',d')}
13. return the cost-delay label with the smallest cost in LABEL(t,n-l) END
Figure 3-6: An optimal algorithm for BDMCP.
Obviously, this optimal algorithm uses the brute-force approach. Thus when it terminates, LABEL(t,n-l) contains all the feasible s-t paths.
start
LABEL(v1,0)
•
•
•
LABEL(vn'O)
sweep 1
LABEL(v"l )
•
•
•
LABEL(vn' 1)
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
sweep n-1
LABEL(v1,n-l)
•
•
•
LABEL(vn,n-l)
Figure 3-7: The execution ofOPTIMAL-BFM-BDMCP.
34
Although this optimal algorithm g:i es us the optimal solution it is impractical. Th
problem with it is that remembering a1l the possible co t-d lay labels for each node might lead to exponential growth of the number of the cost-delay lab Is stored in some nodes and the running time would be exponential. In fact, this i an e ponential time algorithm and it is intractable.
A natural solution for the above problem is to limit the size of the memory in each node to a constant, say k. This modified version of BFM-BDMCP algorithm is called K-BFMBDMCP algorithm. Later we will see that BFM-BDMCP algorithm is a special case of K-BFM-BDMCP with k=l. Intuitively, if k>1, which means every node can remember more labels than BFM-BDMCP, K-BFM-BDMCP is more likely to yield better solutions than BFM-BDMCP. Also, since the number of labels in each label set is at most k, a polynomial number of labels are scanned during each sweep, thus K-BFM-BFMCP should still run in polynomial time.
In the following section, we will present K-BFM-BDMCP algorithm and how that it runs in polynomial time.
3.3 K-BFM-BDMCP
The K-BFM-BDMCP algorithm can be derived from the optimal algorithm from the previous section. The main task is to throwaway certain cost-delay labels in the label sets after each sweep so that each node does not run out of memory during the execution. Now the probleTJ? is what labels we should throwaway.
35
Definition 3.1. Let (cl,dt) and (c2,d2) be two cost-delay labels. We say that (c'l,dl ) ,equals (c2,d2) (denoted by (ct,dl ) = (cz,dz» if C1=C2 and dl=d2. We say that (cl,d,) dominates (c2,d2) (denoted by (cl,dl) ~ (c2,d2»if Ct~C2 and dl~d2' and (cl,dl) strictly dominates
(c2,d2) (denoted by (cl,dl) > (c2,d2» if (cl,dl)~(c2'dz) and (cl,dl);t:(c2,dz). (The relations ">" and "~" on cost-delay labels are called dominance and strict dominance.)
The relation (strict) dominance on a set of cost-delay labels is clearly a partial ordering on the set. Any two distinct cost-delay labels might be compared based on the dominance relation. For two cost-delay labels [J and [2' if [J dominates [2 ' then lJ is better than 12 since the cost and the delay of [J are no greater than the corresponding values of [2' But if no one can dominate the other, then we cannot teB which one is better except for the destination node. The reason is that even though the co t-delay label with smaller cost
value seems better than the other one with smaller delay value, later the latter one would be able to get to the destination through celtain low cost and high delay path to obtai'n a better solution because the former one cannot get through the same path due to delay constraint. For the labels in the destination node, since we have already achieved the goal, so the one with smallest cost value is better than the others.
Now what if we had more than k cost-delay labels for a node and none of them is dominated by one another? Due to the memory limit,' we need some criteria to compare these cost-delay labels and throwaway some "not-so-good" ones.
36
Definition 3.2. Let (cl,dt) and (C2'~) be two cost-delay labels. We say that (cl,dl ) is biassedly better than (C2'~) (denoted by (c"d.)>-(c2 cLz» if C1<C2 and d,>d2·
The relation" >-" enforces a total ordering on a set of cost-delay labels in whjch no one is dominated by another. Here we have bias towards labels with larger cost value since our goal is to find the path with smallest cost and without any knowledge of future, the labels with smaller cost value would be more likely to achieve our goal.
Below is the formal descriptjon of K-BFM-BDMCP.
ALGORITHM K-BFM-BDMCP(N,s,t,T,k)
1.
use Dijkstra's algorithm or BFM algorithm to compute D(v) for every v E V
2.
for each vertex v E V do
3.
lABEL(v,l): =¢
4.
LABEL(s, l):={ (O,O)}
5.
for i: =1 ton-l do
6.
for each vertex v E V do
7. LABEL(v,i): =LABEL(v,i-1)
8.
for each vertex (u,v) E E do
9.
for each cost-delay label (c,d) E LABEL(u,i-l) do
10. (c' ,d'):=(c+cu,v, d+du,v)
11. if d'+D(y) S; T then
37
12. LABEL(v i):=lABEL(v,i) U{( , d )}
13.
for each vertex v E V do
14.
remove aU cost-delay labels in LABEL(v i) that are dominated by some other label in the same set
15.
if ILABEL(v,i)l>k then
16.
trim LABEL(v,i) only to keep the k biassedly better cost-delay labels
17. return the cost-delay label with the smallest cost in LABEL(t,n-l) END
Figure 3-8: K-BFM-BDMCP algorithm.
In the K-BFM-BDMCP algorithm, each node is associated with a set of cost-delay labels. The sweep is taken n-l times. lABEL(v,i) denotes the set of cost-delay labels associated with vertex v during the ith sweep. Each cost-delay label in lABEL(v,i) is either copied from LABEL(v,i-l) or computed from some cost-delay label in LABEL(u,i-l) wher u*v. In other words, 'each cost-delay label in LABEL(v,i) is due to some cost-label existing in the previous sweep which we call predecessor. Following the relation of predece or, every cost-delay label I except for (0,0) in lABEL(s,O) can be traced back to the (0,0) label in LABEL(v,O). Thus we can reconstruct the paths we have already found.
38
• • •
• • • •
• • • •
• • • •
start • • •
l~v'~1 I~~~I I~VAI
~1 • ••
I
[~v"l) II~v,1) [~v.'J
I
~n-1 • • •
I~V~1)1
l~v'~')1 I~~')I
Figure 3-9: The execution of K·BFM-BDMCP.
We first prove the correctness of K-BFM-BDMCP.
Theorem 3.1. K-BFM-BDMCP returns a feasible s-t path if one such path exist.
Proof. Let the label sets in the optimal algorithm in Section 3.2 be denoted by lABEL and the label sets in K-BFM-BDMCP denoted by 'LABEL'. First we prove that (1) lABEL'(v,i) c IABEL(v,i); (2) if LABEL(v,i) :1= ¢, then lABEL'(v,L) :1= ¢ where v E Vand 0:::; i:::; n-l.
39
This can be done by induction on i.
The base case for which i=O is obviously true since lABEL(v,O) = lABEL'(v,O) forv E V.
In the inductive step, we assume that the claim holds for lABEL(v,i) and LABEL'(v,i) for v E V. Consider LABEL(v,i+l) and LABEL'(v,i+l) where v E V. At first, LABEL(v,i) is copied to LABEL(v,i+l) and lABEL'(v,i) is copied to LABEL'(v,i+l). According to the induction hypothesis, LABEL'(v,i+l) c lABEL(v,i+l) at this point. Afterwards, for any cost-delay label 1 that is added to LABEL'(v,i+l), let l' be its predecessor. Then l' E lABEL'(u,i) for some u E V. According to the induction hypothesis, l' E LABEL(u, i). Therefore 1will be also added to lABEL(v,i+l) through the same edge. Thus before line 13 in K-BFM-BDMCP algorithm, We have LABEL'(v,i+l) c lABEL(v,i+l). After that, we only remove labels from lABEL'(v,i+I), so in the end we still have LABEL'(v,i+l) ~ LABEL(v,i+I).
In addition, if lABEL(v,i+l) "" ¢ where v E V, let l E LABEL(v,i+.L) and l' be its predecessor, then l' E LABEL(u,i) for some u E V which mean LABEL(u,i) '1= ¢. According to tlTe induction hypothesis, LABEL'(u,i) "" ¢. Thus the co t-delay label in LABEL'(u,i) will generate a cost-delay label in LABEL'(u,i+l) through the same edge through which l' generated l. Therefore LABEL'(u,i+l) '1= ¢.
40
Since LABEL(l, n-l) contains all the fea ible s-t paths, if there exists a feasible path in the network, then LABEL(t, n-1) :t:-</J which means LABEL (t, 1'1-1) :t:-</J and LABEL'(t, n-l) k LABEL(t, 1'1-1). In other words, it returns a feasible path.
The time complexity of K-BFM-BDMCP depends on how to implement it. In a careful implementation, we use red-black tree to implement label sets. Red-black trees are one of many search-tree schemes that are nearly balanced in order to guarantee that basic set operations such as search, insertion and deletion take O(lgn) time in the worst case where 1'1 is the number of elements in the set. The cost-delay labels can be ordered on cost values with delay values being the tie-breakers.
Theorem 3.2. K-BFM-BDMCP algorithm runs in O(n3klog(nk» time with space complexity 0(kn2).
Proof. From the formal description of K-BFM-BDMCP algorithm, Line 1 take O(mn) .if we use BFM algorithm. Line 2-3 takes 0(1'1). There are 1'1-1 weep. During the ith sweep, copying label sets takes O(nk) (line 6-7). After that we need to scan aJI the m edges. For each edge (u,v), we need to scan all the cost-delay label in LABEL(u,i-l) which is of size O(k). LABEL(v,i) can be of size O(nk) in the worst ca e, so line 12 takes O(log(nk». Line 13-16 contains n iteration. In each iteration, line 14 actually computes the maxima of LABEL(v,i) which can be done in O(nklog(nk» [25]. Trimming is relatively cheaper and only takes O(k). So the total running time is:
0(mn+n+n(nk+mklog(nk)+n2klog(nk»)= O(n3klog(nk».
41 The space for lABEL is O(kn?) and it i the dominant factor. 0 th space complexity is
Let us apply K-BFM-BDMCP algorithm to the example showed in Section 1.3.
D(l) =20 D(3) =10 T=50
(00,0) (00,0) (00,0) (00,0)
5,10
D(s) =20 D(t) =0
...
U1 :oJ
...
N
00
~s
30,40
(00,0) (00,0) D(2) =1~00,0) D(4) =£0,0)
Figure 3-]0: Initialization.
D(l) =20
D(3) =t£.,O) T=50
(5,30)
(00,0) 5,10 (00,0)
D(s) =20 D(t) =0
...
b<'? -~
U1 ...
N
0
0 "
30,40
(6,5) (00,0) D(2) =l~00,0) f?(4) =to,O)
Figure 3-11: Sweep 1.
42 D(3) = 10 T-50
(10 40) 5,10 2010)
D(s) =20 D(l =0
30,40
(6,5) (00,0)
D(2) =1~00,0) D(4) =fo'O)
Figure 3-12: Sweep 2.
D(l) =20 D(3) =10 T-50
(5,30) (10,40) 21,25) 5,10 20,10)
D(s) =20 D(t) =0 ....
en ~'? ~
;..., ....
00 "
,I:)
~,
30,40
(6,5) 27,20) D(2) =1~00,0) D(4) =(10'0)
Figure 3-13: Sweep 3.
43
D(l) -20 D(3) =d8 40) T=50
(5,30) 21,25) 5,10 2010)
D(s) =20 D(t) =0
~
.~
<.n
0
~~
30,40
(6,5) 27,20)
D(2) ={-S,O) D(4) =(1&0)
Figure 3-14: Sweep 4.
3.4 The advantage of K-BFM-BDMCP
The main advantage of K-BFM-BDMCP is its scalability. In fact from the analysis of the previous section, we can see BFM-BDMCP algorithm i a sp cial ca e of K-BFMBDMCP algorithm with k=1. Thus the idea of K-BFM-BDM P i to trade off time with quality of solution. The greater the value of k that is fed into K-BFM-BDMCP, the longer the running time but the better.chance to find better solutions. The running time i stiLI polynomial so it is tractable. Thus this algorithm embodies the trade-off and balance between time and the quality of solution.
When employing K-BFM-BDMCP in the real world, we can make the value of k adaptive, which means the value of k is adjustable over time. A monitor program can be set up to monitor the topology change and traffic change to adjust the k value fed to the routing program .that answers routing requests. Furthermore, we can use different k
44
values for different. runs of the algorithm. In thi case, each request contain t.he
expectation of the quality of routes. If the quality of routes i very important, a bigger k value can be used in order to answer this request. Ifthe request just needs a good feasible path, a lower k value can be used.
Another advantage of K-BFM-BDMCP is that it is also easy to implement in a distributed fashion because of the inherent nature of distributedness of BFM algorithm. In fact, Ravi
[7] has proposed a distributed version of BFM-BDMCP algorithm that is easy to implement. Since K-BFM-BDMCP algorithm is based on BFM-BDMCP algorithm, its distributed version could be obtained similarly. This is also our future work.
45
Chapter 4 Experimental Evaluation
In this chapter, we first present our experimental results on the relation hip between the value of k and the pelformance of K-BFM-BDMCP algorithm. Then we do a comparative evaluation with BFM-BDMCP algorithm and K-BFM-BDMCP algorithm.
4. 1 Test Graphs
We use two kinds of graphs to do our experiments. One is regular graph and the other is irregular graph.
4.1.1 Regular Graph
The kind of regular graph we use is proposed by Harary[22]. A regular graph Hk,n, where k refers to the vertex degree and n refers to the number of vertices, is defined as follows .
•
Case 1: k even. Let k =2r. Then H2r,II has vertices Va, VI. V2•... VII_I and two venice Vi
and Vj are adj~cent if i -r 5) 5 i+ r, where addition is modulo n.
•
Case 2: k odd, n even. Let k =2r + 1. H2r+I,n is constructed by fir t constructing H2r,rl
and then adding edges joining vertex Vi to vertex Vj for i = 1, 2, ..., nl2 and j = i + nl2
(mod n).
•
Case 3: k odd, n odd. Let k = 2r + 1. H2r+I,1I is constructed by first can tructing H2r,1I
and then adding edges joining Vj and Vj for i =0, 1, 2, ..., (n -1) 12 and) =i + (n + 1)/2
(mod n).
As an example, graph H4,8 is shown in Fig. 4-1.
46
Figure 4-1: Regular graph 8 4,so Regular graphs can be used to model interconnection networks and dense networks.
4.1.2 Irregular Graph
Irregular graphs are like random graphs in the sense that they have no well-defined structures yet abide by some desired properties. Since BDMCP problem i on of the QoS-based routing problems, we need to experiment our algorithm on the Internet. Due to the immense scale of the lnternet, deploying an Internet-wide ~xperiment is n arly impossible. So we evaluate our algorithms using randomly generated network topologies.
Currently, there are five Internet topology generators available: Waxman[17], Tiers[18], GT-ITM[19], Inet[20] and BRlTE[21]. We choose Inet because it is based on Autonomous System (AS) connectivity in the Internet and it generates topologies that best approximate the actual Internet AS topology.
47
Empirical evidence shows that Internet AS topology exhibits power-law connecti vity which may also hold for route topoJogie . Power-law graph structure induces "center" where connectivity is concentrated on a few nodes with most veltices possessing spar e connecti vity.
4.1.3 Generating Parameters
For an instance of BDMCP problem, we need not only the underlying graph, but also the other parameters such as link costs and delays, source node, destination node and the delay constraint.
Link costs and delays are selected in one of the following two ways:
1.
Randomly generated costs and delays in the range 1 to mCI.X;
2.
Randomly generated costs and delays such that di,j + Ci.} =max.
Here max is a predefined constant. The motivation for the choice (2) above is to te t the heuristics under what we believe to be a worst-case scenario, and to capture the fact that delay and cost are inVersely related.
For the source node and destination node, our criterion is the longer distance between them, the better. Thus first we pick the node with the smallest degree as the source node. Then we apply Dijkastra's algorithm to obtain the minimum delay from the source node to the others node and pick the one with the maximum minimum delay as the destination node. Finally, we assign twice this maximum minimum delay as the delay constraint.
48
4.2 The Relationship between k and Performance of KBFM-
BDM'CP
The results of the experiments are presented in Table 4-1. Here we choose regular graphs with random costs and delays as the test graphs. A expected, the quaJjty of solution is improved in tenns of cost when we increase the k value, and the running time is also increasing but the increments are vel)' steady.
From Figure 4.2, we can see that there is a dramatic improvement from k=2 to k=5, but the running time is only increased by a small number, as shown in Figure 4.3. So in this case k=5 seems to obtain the balance between the quality of solution and running time.
Table 4-1: Comparison of the performance of different k values
GRAPH NODES K-BFM-BDMCP OPTIMAL
k,-Z ~s ~7~9
cost time cost tIme COSl time cost time co t
k-5 400 1659 3.0 1640 3.8 1640 4.6 1636 5.3 1636
k.-5 450 2069 3.4 1890 4.8 1890 6.0 1890 6.9 1890
k-7 500 1396 3.1 1355 4.5 1355 5.5 1348 6.5 1330
k-7 550 1357 3.4 1261 4.8 1243 5.9 1235 7.4 1226
k-7 600 1882 3.6 1685 5.4 1654 6.8 1638 8.4 1417
k=9 650 1766 3.6 1321 5.4 1317 6.6 1293 -8.2 1188
k=9 700 14L3 3.8 1301 6.1 1296 7.4 1296 9.3 1232
49
Comparison of the performance of different k values
2500 -------------......,
2000 -l---J.~-.,.....-~-";""----.--Jr-~--k-=-2---"
k=5 k=7 -*-k=9
Cost1500 -+------..;~~~
~OPTIMAL
400 450 500 550 600 650 700
Nodes
Figure 4-2: Cost comparison of tbe performance of different k values.
Comparison of the performance of different k values
10-r-----.,.-------------.
8 -.I---~~~~--,...:......;;~......:.:!:..:------1
---+-k=2
Time6 ..J-,:.....,..;..,.~""JII
-k=5 4+--........~ k=7
2 +------,.,-; -*-k=9
O+--,-.-.;...::....,.:.:...--..........,....;.---"......,...------.---..,---l
400 450 500 550 600 650 700
Nodes
Figure 4-3: Time comparison of tbe performance of different k values.
50
4.3 Comparison ot' BFM-BDMCP Algorithm and K-BFMBDMCP Algorithm
The comparison results are presented in Table 4-2, 4-3, 4-4, and 4-5. From the re ults we can see that for regular graphs K-BFM-BDMCP algorithm does result in a considerable improvement over BFM-BDMCP at the cost of a small amount extra time, as shown in Figures 4-4,4-5,4-6, and 4-7. But for irregular graphs the perfOlmanc of KBFM-BDMCP .is worse than that of BFM-BDMCP because they both obtain the optimal solution most of time and the running time of K-BFM-BDMCP is longer, as shown in Figures 4-8 and 4-9. This is due to the fact that there are more routing choices in regular graphs than in irregular graphs. Recall that we use the Inet Internet topology generator to generate irregular graphs. The Internet has the power-law structure which means there are a few super routers that take control of the traffic over the Internet and there are few choices when doing the routing.
Table 4·2: Comparison using regular graph and random costs and delays
GRAPH NODES EDGES BOUND BFM·BDMCP K·BFM-BDMCP OPTlMAL
cost delay time cost delay time cost delay k 5 400 1000 2610 1659 2610 1.1 1640 2602 4.0 1636 2602 k 5 450 1125 '2946 2081 2895 1.2 1890 2937 4.8 1890 2937 k-7 500 1750 j848 1703 1848 1.2 1355 1845 4.6 1330 1845 k-7 550 1925 1986 1378 1971 1.2 1261 1968 4.8 1226 1977 k 7 600 2100 2250 1897 2250 1.2 1685 2241 5.4 1417 2246 k 9 650 2925 1436 1881 1434 1.4 1321 1435 5.2 1188 1432 k 9 700 3150 1563 1413 1561 1.4 1301 1539 61 1232 1556
51
Com parison using regular graph and random costs and de.lays
2500
2000
-BFM-BDMCP
-VI 1500 0 -K-BFM-BDMCP
c.>
1000
OPTIMAL
500
0
0
0
0
0
0
0
0
0
to
0
to
0
to
0
~
~
to
to
to
to
......
Nodes
Figure 4-4: Cost comparison using regular graph and random costs and delays.
Comparison using regular graph and random costs and delays
7-..---........,--.------.....,..,~ 6+--------.;...-----------.,.-1
5 -.~~~~..,.....,=:::=::tr:..~ ~4-HF--...,.....--------------1 -+-BFM-BDMCP j::3+--.....,.....--.......--------l ----K-BFM-BDMCP
2+--~..,....,~.....-~----_:__I
1 ~~~~~~=*=:::!::=:!~
O-+----+----i--.....,.-...,..-...,....-~__'!
400 450 500 550 600 650 700
Nodes
Figure 4-5: Time comparison using regular graph and random costs and delays.
52
Table 4-3: Comparison using regular graph and related co ts and delays
GRAPH NODES EDGES BOUND BFM-BDMCP K·BFM·BDMCP OPTIMAL
co t delay time cost delay time cost delay
k=5 400 1000 5161 4694 4906 1.1 4694 4906 2.7 4639 5161 k-5 450 1125 5891 5088 5712 1.1 4924 5876 3.3 4901 5891 k=7 500 1750 3260 6356 3244 1.2 5943 3257 3.0 5340 3260 k=7 550 1925 4006 5794 4006 1.2 5196 4004 3.2 4594 4006 k=7 600 2100 4081 7721 4079 1.2 6723 4077 3.6 6217 4081
,
k=9 650 2925 2925 6078 2922 1.3 6076 2924 3.4 5075 2925 k=9 700 3150 2801 8201 2799 1.4 8199 2801 3.6 6399 2801
Comparison using regular graph and related costs and delays
10000.,...----------..,......"
8000 +------~~-......,.y ~BFM_BDWCP
1ii 6000 -k~,....:-.,4~~~~' o ---K-BFM-BDWCP
(,) 4000 +-----....:;;;..-.......---1
OPTI~L 2000 +-----~------J
O-F'----1--.-"i"""'""--'T--r--~"""""
400 450 500 550 600 650 700
Nodes
Figure 4-6: Cost comparison using regular graph and related costs and delays.
53
Comparison using regular graph and related costs and delays
4-r-------------...,
-+-BFM-BDMCP K-BFM-BDMCP
400 450 500 550 600 650 700
Nodes
Figure 4-7: Time comparison using regular graph and related costs and delays.
Table 4-4: Comparison using irregular graph and random costs and delays
NODES EDGES BOUND BFM-BDMCP K-BFM-BDMCP OPTIMAL
cost delay time cost delay time cost delay
3050 4810 626 303 419 2.2 303 419 6.3 303 419 3100 4904 610 263 407 2.1 263 407 6.3 263 407 3150 4998 555 218 423 2.2 218 423 5.1 218 423
I
3200 5094 615 250 407 2.4 250 407 5.6 250 407 3250 5189 733 185 450 2.2 185 450 6.7 185 450
.
3300 5284 700 261 560 2.4 261 560 5.2 261 560 3350 5379 503 234 394 2.4 234 394 5.7 234 394 3400 5474 465 149 283 2.4 149 283 4.7 149 283
54
Comparison using irregular graphs and random costs and delays
8,.....----...,--:";"":"'=""""'"-------,
6+--~~
Ql --+-BFM-BDMCP E 4+--~~~
_ K-BFM-BDMCP
i=
O+--.,,----..:~=-r-......-f-~----_....-....,.-__l
0() ()() ~() ()() <-:>() ()() ~() ()() ~() ~" ~" <>.JC!; <>.J'l; ~flj ~Oj ~
Nodes
Figure 4-8: Time comparison using irregular graphs and random costs and delays.
Table 4-5: Comparison using irregular graph and related costs and delays
NODES EDGES BOUND BFM-BDMCP K-BFM·BDMCP OYflMAL
cost delay time cost delay time cost delay
3050 4810 1506 311 1489 2.2 294 1506 6.0 294 1506 3100 4904 1464 297 1303 2.2 297 1303 5.8 297 1303 J150 4998 1336 286 1114 2.3 286 1114 6.2 286 1114 3200 5094 1472 323 1277 2.2 323 1277 6.5 323 '1277 3250 5189 1758 16 1584 2.3 16 1584 6.8 16 1584 3300 5284 1684 12 1612 2.3 12 1612 6.3 12 1612 3350 5379 1206 308 1092 2.6 308 1092 6.1 308 1092 3400 5474 1118 245 755 2.4 245 755 5.6 245 755
55
Comparison using irregular graphs and related costs and delays
8....-----~.......,,"-"
GI
6t---~~m1
-.-BFM-BDMCP
E i=
4+--.....-~~~
K-BFM-BDMCP
2 -H.........~¥ll!t
O+----,--,-.......,-.....;..;>;r-I&<:.f";:.;..:..;-,...;--r-----l
~() ()() 0() ()() 0(:) ~() ~() ()() 0() 0" 0" 0rr/ 0'1,; 003 003 ~
Nodes
Figure 4-9: Time comparison using irregular graphs and related costs and delays.
56
Chapter 5 Conclusion and Future Work
In this thesis, we have studied the problem of finding the minimum co t path from a source node to a destination node satisfying a delay constraint in a network represented by a directed graph. We call this problem the Bounded-Delay Minimum-Cost Path Problem (BDMCP). This problem is NP-hard and people have been taking two approaches to attack this problem: heuristics scheme and approximation scheme. We adopt the heuristics scheme.
We began by reviewing several important algorithms related to BDMCP problem. Among them BFM-BDMCP is of our most interest because of its efficiency and effectiveness.
We then discussed the drawback of BFM-BDMCP and propo ed a new algorithm ba ed on the BFM-BDMCP algorithm. We call thi new algorithm the K-BFM-BDMCP algonthm. K-BFM-BDMCP is expected to find better olutions than B M-BDM P at the cost of longer, but still polynomj.al, running time. We proved its correctness.
An experimental evaluation has been carried out to compare the performance of K-BFMBDMCP with different k values and comparing the performance of the BFM-BDMCP and K-BFM-BDMCP. The comparison is with respect to the cost of the resulting path, and the time taken for the execution of the algorithms on different types of graphs. The experimental results show that K-BFM-BDMCP algorithm gives paths with better costs
57
when compared to the BFM-BDM P algorithm and that their time of exe ution are
comparable.
Future work would be improving K-BFM-BDMCP algorithm by modifying the way it trims the cost-delay label sets associated with the nodes when they are out of space. Al 0, we plan to design a distributed version of K-BFM-BDMCP algorithm.
58
References
[1] E. Crawley, R.Nair, B.Rajagopalan, H.Sandick A Framework for QoS-ba ed Routing in the Internet", RFC2386, Aug. 1998, 37 pages. Available: http://www.ietf.orglrfc/rfc2386.txt
[2] Wei Sun, "QoSlPolicy/Constraint Based Routing", Dec. 1999. Available: http://www.cis.ohio-state.edu/-jain/cis788-99/qos_foutinglindex.htmJ
[3] Z. Wang and J. Crowcroft, "Quality-of-Service Routing for Supporting Multimedia Application", IEEE on Selected Areas in Communications, vol. 14, no.7, pp.12281234, Sep.1996.
[4] K. M. Chandy and J. Mishra, "Distributed Computation on Graphs: Shortest Path Algorithms", CACM, vol. 25(11), pp. 833-837, Nov. 1982.
[5] Gang Luo, Kaiyuan Huang, Jianli Wang,Chris Hobbs and Ernst Munter, "Multi-Qos Constraints Based Routing for IP and ATM Network", Proceedings of IEEE Workshop on QoS Support for Real-Time Internet Applications, Jun 1999, Vancouver, Canada.
[6] Shigang Chen, Klara Nahrstedt, "On Finding Multi-Constrained Paths", Proceedings of IEEE International Conference on Communications (ICC 98), pp.874-879, June 1998, Atlanta, Georgia.
[7] Ravi Ravindran, "Distributed and Sequential Heuristics for QoS Routing in Communication Networks", M.S. Thesis, June 2000, Computer Science Dept. University of Oklahoma, Norman, Oklahoma.
59
[8] Ravi Ravindran, Krishnaiyan Thulasiraman, Anindya Da Kaiyuan Huang, Gang
Luo, Guoliang Xue "Quality of Service Routing: Heuri tics and Approximation
Schemes with a Comparative Evaluation', ISCAS 2002 May 2002, Scottsdale,
Arizona.
[9] Shigang Chen, "Routing Support for Providing Guaranteed End-to-End Quality-ofService", Ph.D. thesis, May 1999, Vniversity of illinois at Urbana-Champaign.
[10] S.Shenker, C.Patridge, R.Guerin, "Specification of Guaranteed Quality of Service", Network Working Group, RFC 2212.
[11] S.Chen and K.Nahrsedt, "An Overview of Quality of Service Routing for NextGeneration High Speed Networks: Problems and Solutions", IEEE Network Magazine, vol. 12 (6), 1998.
[12] Douglas S.Reeves, Hussein F.Salama, "A Distributed algorithm for DelayConstrained Unicast Routing". IEEE/ACM transactions on Networking, vol. 8, no 2, pp. 239-250, Apr. 2000.
[13] Jaffery M.Jaffe, "Algorithm for finding Paths with Multiple Constraints", Networks, vol. 14 (1984), pp. 95-116. [14) Roch A.Gue'rin, "QoS Routing in Networks with Inaccurate Information: Theory and Algorithms,", lEEE/ACM Transactions on Networking, vo1.7, no.3, June 1999.
[15J Q.Ma and P.Steenkiste, "Quality of Service Routing with Performance Guarantees," Proceedings o/4th Int'[ IFIP Workshop QoS, May 1997.
[16] R.K.Ahuja, T.Magnanti and J.B.Orhn, "Network Flows Theory, Algorithms and Applications", Prentice Hall, 1993.
60
[17] B.M. Waxman. Routing of Multipoint Connections. IEEE Journal of Selected Areas in Communication, vol. 6(9), pp. 1617-1622, Dec. 1988.
[18] M. Doar. A Better Model for Generating Test Networks. Proc edings Of IEEE COLBECOM, Nov. 1996.
[19] K. Calvert, M.B. Doar, and E.W.Zegura. "Modeling Internet Topology". IEEE Communications Magazine, June 1997.
[20] C. Jin, Q. Chen, and S.Jamin. Inet: Intemet topology generator. Tech.rep.cse-tr433-00, University of Michigan EECS Department, 2000.
[21] Alberto Medina and Ibrahim Matta. Brite: A flexible generator of internet topologies. Technical Report BU-CS-TR-2000-005, Boston University, Boston, Massachusetts, 2000.
[22] K. Thulasiraman and M.N.S.Swamy, Graphs: Theory and Algorithms. JohnWiley and Sons, 1992.
[23] Rassin R, "Approximation Schemes for the Restricted Shorte t Path Problem", Mathematics ofOperation Research, vol. 17(1), pp. 36-42.
[24] R. Widyono. "The design and evaluation of routing algorithms for real-time channels", Technical Report TR-94-024, University of California at Berkeley, June 1994.
[25] Kung, H.T., "On the computational complexity of finding the maxima of a set of vectors", Proceeding of 15th Annual IEEE Symposium on Switching and Automata Theory, pp. 117-121, Oct. 1972.
61
Appendices
Code Listings
This appendix contains the code listings of the Java programs that we used to do our
experimental evaluations.
BFM.java
IIUsage: java BFM network filename
class BFM
{
public static void main(String args[]) {
Network N=null;
try {
N=new Network(args[O);
catch (Exception e) (
System.out.println(e.getMessage(» ;
System.exit(l);
int prevCLABEL[)!=new int[N.numNode);
int CLABEL[)=new int[N.numNode);
int prevDLABEL[)=new int[N.numNode);
int DLABEL[)=new int[N.nurnNode);
int D[)=new int[N.numNode];
int PRED[)=new int[N.nurnNode);
Ilinitialization
LHWHM.compute_D(N,D) ;
for (int i=O;i<N.numNpde;i++)
CLABEL[i)=Network.INFINITY;
DLABEL[i)~O;
PRED[i)=i;
}
CLABEL[N.s)=O;
boolean hasUpdate;
while (true) {
for (int u=O;u<N.nurnNode;u++) (
prevCLABEL[u)=CLABEL[u) ;
prevDLABEL[u]=DLABEL[u);
hasUpdate=false;
for (int u=O;u<N.numNode;u++)
62
for (int j=O;j<N.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]; else v=N.edge[edge] .vertex[O];
if (prevCLABEL[u]+N.edge[edge] .c<CLABEL[v] &&
prevDLABEL[u]+N.edge[edge] .d+D[v]<=N.T ) CLABEL[v] =prevCLABEL[u] +N. edge [edge] .c; DLABEL [v] =prevDLABEL [u] +N. edge [edge] .. d; hasUpdate=true;
}
if (!hasUpdate) break;
System.out.println(CLABEL[N.t]+" , "+DLABEL[N.t)) ;
Convert.java
II Convert a network file generated by Inet to a file we need II Usage: java Convert inet_file random_seed method max II method=l: cost=l ..max and delay=l ..max II method=2: cost+delay=max import java.util.*; import java.io.*;
class Convert {
public static void main(String args[]) throws Exception {
String inet_file=args[O];
int random_seed=Integer.parselnt(args[l]);
int method=Integer.parselnt(args[2]);
int rnax=Integer.parselnt(args[3))i
BufferedReader in =
new BufferedReader(
new FileReader(inet_file»;
String s = new String();
s = in.readLine();
StringTokenizer st = new StringTokenizer(s);
int numNode=Integer.parselnt(st.nextToken(»);
int nurnEdge=Integer.parselnt(st.nextToken(»;
Systern.out.println(nurnNode+" "+nurnEdge);
Random ran=new Random (random_seed) ;
for (int i=O;i<numNode;i++) s=in.readLine();
for (int i=O;i<nurnEdge;i++)
s=in.readLine();
st = new StringTokenizer(s) ;
int vl=!nteger.parselnt(st.nextToken(»;
63
int v2=Integer.parselnt(st.nextToken(»;
int weight=Integer.parseInt(st.nextToken(»;
int cost,delay;
delay=1+(max-l)*weight/9999;
Ildelay=ran.nextInt(max-l)+l;
if (method==l)
cost=ran.nextInt(max-l)+l;
else cost=max-delay;
System.out.println(vl+" "+v2+" "+cost+" "+delay);
)
in.close() ;
DynamicProgramming. java
IIOptimal solution Ilassuming d(i,j»O class DynamicProgramrning {
public static void main(String args[]) {
Network N=null;
try {
N=new Network (args [0] );
) catch (Exception e) {
System.out.println(e.getMessage{» ;
System.exit(l) ;
}
int D[)=new int[N.numNode];
LHWHM.compute_D(N,D) ;
Ilinitialization
int f[) [) []=new int[N.numNode] [N.T+l] [3];
for (int i=O;i<N.numNode;i++)
f [i] (0) (0) =Network ..INFINITY;
f[N.s] [0) [0]=0;
for (int x=l;x<=N.T;x++) {
for (int j=O;j<N.numNode;j++)
if (j==N.s) continue;
/Icompute f[j) [x]
int min=f[j][x-l][O];
int minj=j;
int minx=x-l;
for (int i=O;i<N.node[j) .edge.length;i++) int edge=N.node[j] .edge[i]; . int k; if (j==N.edge[edge] .vertex[O)
k=N.edge[edge) .vertex[l];
else k=N.edge[edge] .vertex[O];
64
if (x<N.eOge[edge] .d) continue;
if (f(kJ [x-N. edge (edge) .d) [0) +N. edge [edge) .c<min) rnin=f(k) (x-N.edge[edge) .d] [O]+N.edge[edge] .c; rninj=k; rninx=x-N. edge [edge] .d;
}
}
f(j) [xJ [OJ=rnin;
f [j J [xJ [1] =minj;
f [ j] [xJ [2] =minx;
}
int totalDelay=O;
int j=N.t;
int x=N.T;
while (j !=N.s II x!=O) {
int jj,xx;
jj=f[j] [x] [lJ;
xx=f [j] [x] [2] ;
if (j!=jj) totalDelay+=delay(N,jj,j);
j =j j;
x=xx;
)
System.out.println(f[N.t] [N.T] [OJ+", "+totalDelay);
}
Ilassume there is at most one edge between any two vertices
static int delay(Network N,int k,int j){
for (int i=O;i<N.node[k] .edge. length; i++)
int edge=N.node(kJ .edge[i];
if « k==N . edge [edge] . vertex [0] && j ==N . edge [edge] . vertex [1]) II (k==N.edge[edgeJ .vertex[l] && j==N.edge[edge] .vertex[O]»
return N. edge [edge] .d;
}
return Network. INFINITY;
)
Edge. java
class Edge
(
int vertex[]=new int(2];
int c; Ileost
int d; Iidelay
public Edge(int vertexO,int vertexl,int c,int d) {
vertex[O]=vertexO;
vertex[lJ=vertexl;
this.c=c;
this.d=d;
65
KBFM.java
import java.util.*;
class KBFM {
public static void main(String args[]) {
Network N=null;
try {
N=new Network (args [0] );
catch (Exception e) {
System.out.println(e.getMessage(» ;
System.exit(l) :
}
int k=Integer.parseInt(args[l]);
Label prevLabel [] =new Label [N.numNode];
Label label[]=new Label [N.numNode] ;
int D[]=new int[N.numNode];
Ilinitialization
LHWHM.compute_D(N,D);
for (int i=O;i<N.numNode:i++)
label [i]=new Label():
label[N.s] .add(new CostDelayLabel(O,O,null»;
boolean hasUpdated:
int sweep=O;
while (true)
sweep++:
for (int u=O:u<N.numNode:u++)
prevLabel[u]=(Lab~l) label[u] .clone();
hasUpdated=false;
for (int u=O:u<N.numNode:u++) {
Iterator it=prevLabel[u] .iterator();
while (it.hasNext(» {
CostDelayLabel cdp_u=(CostDelayLabel) it.next():
if (cdp_u.hasScanned) continue;
for (int j=O;j<N.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]; else v=N. edge [edge] .vertex[O];
int cost=cdp_u.c+N.edge[edge] .c:
66
int delay=cdp_u.d+N.edge[edge] .d;
if (delay+D[v]<=N.T) ( if (label[v] . add (new CostDelayLabel(cost, delay,
hasUpdated=true;
cdp_u.hasScanned=true;
}//finish scanning u
//finish sweeping
if (! hasUpdated) break;
for (int u=O;u<N.numNode;u++)
label [ul . trim(k) ;
CostDelayLabel result=label[N.tl .first();
System.out.println(result.c+", "+result.d);
static class Label implements Cloneable( TreeSet holder;
public LabeI (){
holder=new TreeSet();
public Object clone() {
Label lbl=new Label();
lbl.holder=(TreeSet) holder.clone();
return lbl;
public Iterator iterator() {
return holder.iterator();
public CostDelayLabel first() {
return (CostDelayLabel) holder.first();
public int size(') (
return holder.size();
public void print() {
Iterator it=iterator();
while (it.hasNext(» (
CostDelayLabel cdp=(CostDelayLabel) it.next();
System.out.print(" ("+cdp.c+","+cdp.d+") ");
}
System.out.println(} ;
67
public boolean add(CostDelayLabel cdp) {
if (!holder.add(cdp)
return false;
CostDelayLabel tmp=null;
SortedSet ss=holder.headSet(cdp);
if (! ss. isEmpty (» {
tmp=(CostDelayLabel) ss.last();
if (tmp. isDominating (cdp) )
holder. remove (cdp) ;
return false;
Ilremove all cost-delay labels that are dominated by cdp
Iterator it=holder.tailSet(cdp) .iterator();
it.next(); Iiskip cdp itself
TreeSet ts=new TreeSet();
while (it.hasNext(» (
Object o=it.next();
if (cdp.isDominating(o»)
ts.add(o) ;
else break;
it=ts.iterator() ;
while (it.hasNext(»
holder.remove(it.next(») ;
return true;
public void trim(int k) (
int i=holder.size()-k;
while (i>O) {
holder.remove(holder.last(» ;
i--;
static class CostDelayLabel implements Comparable{ int c,d; CostDelayLabel predecessor; boolean hasScanned;
public CostDelayLabel(int c,int d,CostDelayLabel predecessor) ( this.c=c; this.d=d; this.predecessor=predecessor; hasScanned=false;
public int .compareTo(Object 0)
68
CostDelayLabel p=(CostDelayLabel) 0;
if (c<p.c) return -1;
if (c==p.c) {
if (d<p.d) return -1;
else return 0;
}
return 1;
public boolean isDominating(Object 0) ( CostDelayLabel p=(CostDelayLabel) 0;
if (c<=p.c && d<=p.d) return true; return false;
LHWHM.java
import java.util.*; class LHWHM
(
public static void main(String args[]) { Network N=null; try {
N=new Network (args [0] );
catch (Exception e) { System.out.println(e.getMessage(}) ; System.exit(l);
int CLABEL[]=new int[N.numNode]; int DLABEL[]=new int[N.numNode]; int D[]=new int[N.numNode]; boolean PERM[]=new boolean[N.numNode]; int PRED[)=new int[N.n~ode];
//initialization
compute_D (N, D) ;
for (int i=O;i<N,numNode;i++)
CLABEL[iJ=Network.INFINITY;
DLABEL[iJ=O;
PERM[i]=false;
PRED[i]=i;
}
CLABEL[N.s]=O;
for (int i=O;i<N.numNode;i++) { int u=O; int minCLABEL=Network.INFINITY; for (int j=O;j<N.numNode;j++)
if (! PERM[j] && CLABEL[j]<minCLABEL)
69
u=j;
minCLABEL=CLABEL[j) ;
PERM[u)=true;
if (u==N.t) break;
for (int j=O;j<N.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); else v=N.edge[edge] .vertex[O);
if (!PERM[v] &&
CLABEL[u]+N.edge edge] .c<CLABEL[v] &&
DLABEL[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;
System.out.println(CLABEL[N.t]+","+DLABEL[N.t]);
static void compute_D(Network N,int D[]) { Ilinitialization boolean PERM[]=new boolean[N.numNode);
for (int i=O;i<N.numNodeii++)
D[i]=Network.INFINITY;
PERM[i)=false;
I/find a node with the minimum degree and name it as destination
int minDegree=Network.INFINITY;
for (int i=O;i<N.numNode;i++)
if (N.node[i] .edge.length<minDegree)
minDegree=N.node[iJ .edge.length;
N.t=i;
}
D[N.t]=O;
Ilgo
for (int i=O;i<N.numNode;i++) {
int u=O;
int minD=Network.INFINITY;
for (int j=O;j<N.numNode;j++)
if (l PERM[j] && D[j]<minD)
u=j;
minD=D[j] ;
PERM[u]=true;
for lint j=O;j<N.node{u] .edge.length;j++)
70
int edge=N.node[u] .edge[j];
int v;
if (u==N. edge [edge] .vertex[O]) v=N.edge[edge] .vertex[l);
else v=N. edge [edge] .vertex[O];
if (lPERM[v] && D[u]+N.edge[edge) .d<D[v]) D[v]=D[u]+N.edge[edge] .d;
int maxD=O;
for (int i=O;i<N.numNode;i++)
if (D[i]>maxD)
maxD=D [i] ;
N. s=i;
}
IISystem. out .println ("maxD=" +maxD) ;
N.T=maxD*2;
Network.java
import java.util.*;
import java.io.*;
class Network
{
static final int INFINITY=lOOOOOO;
int s; Iisource
int t; Iidestination
int T; Ilbound
int numNode;
int numEdge;
Node node[];
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.parselnt(st.nextToken());
numEdge=Integer.parselnt(st.nextToken(); .
node=new Node [numNode) ;
edge=new Edge[numEdge);
for (int i=O;i<numEdge;i++)
71
s=in.readLine() ;
st = new StringTokenizer(s) ;
int vertexl=Integer.parselnt(st.nextToken());
int vertex2=Integer.parselnt(st.nextToken());
int cost=Integer.parselnt(st.nextToken());
int delay=Integer.parselnt(st.nextToken());
edge[i]=new Edge (vertexl,vertex2,cost,delay) ;
in.close() ;
int degree[]=new int[numNode];
for (int i=O;i<numNode;i++) degree[i]=O;
for (int i=O;i<numEdge;i++) {
degree[edge[i] .vertex[O]]++;
degree[edge[i] .vertex[l]]++;
}
for (int i=O;i<numNode;i++)
node[i]=new Node();
node [i] . edg'e=new int [degree [i] ] ;
for (int i=O;i<numEdge;i++)
for (int j=O;j<=l;j++) { int vertex=edge[i] .vertex[j]; node (vertex] .edge[--degree[vertex]]=i;
public static void main(String args(]) throws Exception{ Network N=new Network (args [0] I; int D[]=new int[N.numNode]; LHWHM.compute_D(N,D) ; System.out.print(N.T+", "+N.numEdge);
Node.java
class Node { int edge[]; Iiall edges connected to this node }
RegularGraph. java
II Usage: java RegularGraph k n random_seed method max II k connectivity II n ---the number of nodes
72
II cost+delay=max import java.util.*;
class RegularGraph {
public static void main(String args[]l throws Exception { int k=Integer.parselnt(args[O]); int n=Integer.parselnt(args[l]); int random_seed=Integer.parselnt(args[2]}; int method=Integer.parselnt(args[3JI; int max=Integer.parselnt(args[4] I ;
int r=k/2;
TreeSet edge=new TreeSet();
for (int i=O;i<n;i++1 {
for (int j=i-r;j<=i+r;j++)
if (i==jl continue;
int jj=j % n;
if (jj<O) jj+=n;
edge.add(new Edge(i,jjll;
if (kl=r*21 Ilr is odd
if «n/21 *2==nl { I In is even
for (int i=1;i<=n/2;i++1
edge.add(new Edge(i, (i+n/2) % nl);
else {
for (int i=O;i<=(n-11/2;i++1
edge.add(new Edge(i, (i+(n+lI/21 % nIl;
System.out.println(n+" "+edge.sizell);
Random ran=new Random (random_seed) ;
Iterator it=edge.iterator();
while lit.hasNext()) {
Edge e=(Edge) it.nextl);
int cost,delay;
if (method==l) {
cost=ran.nextlnt(max-l) +1;
delay=ran.nextlnt(max-ll+l;
} else {
cost=ran.nextlnt(max-11+1;
delay=max-cost;
}
Sys'tem. out. println (e. vO+" "+e. v1+" It +cost+" "+delayl;
static class Edge implements Comparable{
int vO,vl;
public Edge(int vO,int vll {
if (vO<vl) {
73
this.vO=vO;
this. vl=vl ;
else {
this.vO=vl;
this.vl=vO;
public int compareTo(Object 0) { Edge e=(Edge) 0;
if (vO==e.vO && vl==e.vll return 0; if (vO<e.vO II (vO==e.vO && vl<e.v1l) return -1; return 1;
74
VITA 2.
Yuanbing Du
Candidate for the Degree of
Master of Science
Thesis: ON BOUNDED-DELAY MlNIMUM-COST PATH PROBLEM
Major Field: Computer Science
Biographical: Personal Data: Born in Shaoguan, Guangdong, China, January 1, 1974, daughter Of Tianlv Long and Hanning Du.
Education: Graduated from Shaoguan No.1 Middle School, Shaoguan, Guangdong, China, in July 1992; received Bachelor of Economic in International Finance from Jinan University, Guangzhou, hina, in June 1996; completed the requirements for the degre of Ma ter f Science in Computer Science at the Computer Science Department of Oklahoma State University in May 2003.
Experience: Employed by Industrial and Commercial Bank of China, China, as an Accountant from.July 1996 to August 1999; employed by Midland Realty, China, as a Consultant from August 1999 to May 2000. Name: Yuanbing Du Date of Degree: May 2003
Institution: Oklahoma State University Location: Stillwater, Oklahoma
Title of Study: ON BOUNDED-DELAY MINIMUM-COST PATH PROBLEM
Pages in Study: 74 Candidate for the Degree of Master of Science
Major Field: Computer Science
Scope and Method of Study: Real time applications over the Internet require guarenteed end-to-end quality of service CQos). The task of QoS-based routing is to find a route in the network which has sufficient resources to satisfy the QoS requirements. One of the QoS-based routing problems -the Bounded-Delay Minimum-Cost Path Problem (BDMCP) is NP-hard. There are two directions to solving NP-hard problems: approximation scheme and heuristic approaches. In this thesis, we focus on heuristic approaches. Several heuristic algorithms which are based on Dijkstra's algorithm or Bellman-Ford-Moore algorithm have been proposed to find suboptimal solutions, but they share the same drawback --nonscalability. We propose a new heuristic algorithm called K-BFM-BDMCP in which the memory of each node in networks is increased to predefined constant k so that more potentially good intermediate results could be stored to reach a better final solution. We prove that the new algorithm still runs in polynomial time which means it is feasible in practice. An experimental study is conducted to find out the relationship between the value of k and the performance of K-BFM-BDMCP. We also do a comparative study of the new algorithm with BFM-BDMCP algorithm.
Findings and Conclusions: With high probability K-BFM-BDMCP finds better solution than BFM-BDMCP with a tolerable amount of extra time. The main advantag i it scalability and is very suitable for real network enviroments.
! iJ"
/l_'
ADVISOR'S APPROVAL: ----t-I:--~---""""-.c:......:..----'~~::........>..._,