USING MAXIMUM AND MAXIMUM CONCURRENT
MULTICOMMODITY FLOWS FOR QOS
ROUTING IN THE INTERNET
By
SATOKO CHIKA
Bachelor of Science
The University of Aizu
Aizu-Wakamatsu, Japan
2002
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
July, 2007
ii
USING MAXIMUM AND MAXIMUM CONCURRENT
MULTICOMMODITY FLOWS FOR QOS
ROUTING IN THE INTERNET
Thesis Approved:
Dr. Venkatesh Sarangan
Thesis Adviser
Dr. John P. Chandler
Dr. Nohpill Park
Dr. A. Gordon Emslie
Dean of the Graduate College
iii
Acknowledgments
I would like to express my deep gratitude to my thesis advisor Dr. Sarangan. I
could not complete this thesis without his advice, strong support, and earnest labor. I am
also thankful to committee members, Dr. Chandler and Dr. Park. Further, I would like to
thank Dr. Chandler for his advice on statistic areas and support throughout this thesis.
I am also thankful to the Computer Science Department for giving me a teaching
assistant position. I learned many things from both supervisors and students. These
wonderful experiences will help my future work.
I would like to convey my gratitude to my friends for supporting me. Warm and
kind words of encouragement pushed me forward beyond any setbacks.
Finally, I would like to express my sincere thanks to my parents and sister. I could
not overcome life abroad without their strong support and encouragement.
iv
TABLE OF CONTENTS
Chapter Page
I. INTRODUCTION......................................................................................................1
II. REVIEW OF LITERATURE
2.1 Quality of Service (QoS) ...................................................................................3
2.2 Hierarchical Routing Algorithm........................................................................4
2.3 Topology Aggregation (Network State Aggregation) .......................................4
2.4 Maximum Flow ProblemError! Reference source not found. .......................5
2.5 Multicommodity Flow Problem.........................................................................7
2.6 Maximum Multicommodity Flow Problem.......................................................8
2.7 Maximum Concurrent Flow Problem..............................................................10
2.8 Goodness Measures .........................................................................................13
2.9 General Maximum Flow vs. Maximum and Maximum Concurrent
Multicommodity Flow Algorithms ........................................................................13
III. METHODLOGY
3.1 Discrete Events Simulator (DES) ....................................................................15
3.2 Implementing a DES........................................................................................15
3.3 Assumptions.....................................................................................................16
3.4 Input .................................................................................................................19
3.5 Simulation Circumstances ...............................................................................19
v
IV. FINDINGS
4.1 Goodness Measures vs. Number of Events......................................................20
4.1.1 BAR vs. Number of Events ....................................................................21
4.1.2 BUR vs. Number of Events ....................................................................22
4.1.3 BOR vs. Number of Events ....................................................................23
4.1.4 Discussion...............................................................................................24
4.2 Goodness Measures vs. Average Time between Requests ..............................25
4.2.1 BAR vs. Average Time between Requests .............................................25
4.2.2 BUR vs. Average Time between Requests .............................................27
4.2.3 BOR vs. Average Time between Requests ............................................28
4.2.4 Discussion...............................................................................................29
4.3 Goodness Measures vs. Time between Updates .............................................30
4.3.1 BAR vs. Time between Updates ............................................................31
4.3.2 BUR vs. Time between Updates ............................................................32
4.3.3 BOR vs. Time between Updates ............................................................33
4.3.4 Discussion...............................................................................................34
4.4 Summary of Findings.......................................................................................35
V. CONCLUSION......................................................................................................36
REFERENCES ............................................................................................................38
vi
LIST OF FIGURES
Figure Page
Figure 1. Hierarchical Network Model....................................................................6
Figure 2. Max Flow with Multiple Sinks.................................................................7
Figure 3. Maximum Multicommodity Flow Pseudo-Code......................................9
Figure 4. Maximum Concurrent Flow Pseudo-Code.............................................12
Figure 5. Network Model.......................................................................................14
Figure 6. Discrete Events Simulator ......................................................................18
Figure 7. BAR vs. Number of Events ....................................................................21
Figure 8. BUR vs. Number of Events ....................................................................22
Figure 9. BOR vs. Number of Events ....................................................................23
Figure 10. BAR vs. Average Time between Requests ..........................................26
Figure 11. Unweighted Nonlinear Regression Fits................................................27
Figure 12. BUR vs. Average Time between Requests ..........................................28
Figure 13. BOR vs. Average Time between Requests ..........................................29
Figure 14. BAR vs. Time between Updates ..........................................................31
Figure 15. BUR vs. Time between Updates .........................................................32
Figure 16. Unweighted Nonlinear Regression Fits with MMF .............................33
Figure 17. BOR vs. Time between Updates .........................................................34
1
CHAPTER I
INTRODUCTION
The Internet is a major source of information, news and entertainment.
“Connecting” was the highest priority when the Internet was designed and implemented.
Now, there is no question that the Internet is “connected”. The Internet has started using
Quality of Service (QoS) features, and QoS is the key for the further success of the
Internet. With a variety of services over the large network, users expect QoS
improvements.
An inevitable issue in QoS routing is scalability. Frequently updating state
information is required in QoS routing, and it causes not only consumption of network
bandwidth but power to generate and advertise update messages [1]. This scalability
concern increases as the network size becomes larger.
Hierarchical QoS routing is one of the solutions to deal with this scalability
concern in a larger network. In hierarchical routing, nodes are grouped and treated as
domains. This clustering is repeated to create a multi-level hierarchy. Since continually
updating detailed information at every router increases the communication overhead in
such a large network, topology information is aggregated before being advertised. This
technique is called topology aggregation [2]. In hierarchical QoS routing with topology
2
aggregation, upper level nodes receive concise topology information from lower level
nodes [12].
A general maximum flow algorithm is used to find a feasible path in bandwidth
aggregation. It displays a high Bandwidth Over-estimation Ratio (BOR) and low
Bandwidth Under-estimation Ratio (BUR). The maximum multicommodity flow and
maximum concurrent flow algorithms can reduce BOR because of their more accurate
acceptance criteria. The objective in this thesis is to compare the statistical results
obtained by simulation using general maximum flow algorithm and maximum
multicommodity flow and maximum concurrent flow algorithms.
3
CHAPTER II
REVIEW OF LITERATURE
2.1 Quality of Service (QoS)
Assurance of QoS involves selecting a path with sufficient resources for the
requested QoS parameters, such as bandwidth, delay, jitter and packet loss. The QoS
problem is intractable when dealing with multiple constraints [7].
Many applications use the Internet, and packets flowing within the network
include those for Web browsers, e-mail and so on. The sender has to deal with routing of
various commodities. On the other hand, the receiver expects data to be delivered with
guaranteed QoS. Frequent updating is needed in QoS routing. However, as the network
becomes larger, it is almost impossible to advertise topology information to every node in
the network due to the time, space and bandwidth required. Therefore, scalability will be
the main concern as network size increases. There are two possible solutions to deal with
this problem: quantity reduction and frequency reduction [13]. Quantity reduction
emphasizes reducing the number and size of the messages which must be sent to inform
one router of another’s state. The objective of frequency reduction is to try to create
messages infrequently as keeping routing performance. The topology aggregation scheme
belongs in the quantity reduction strategies [1].
4
2.2 Hierarchical Routing Algorithm
The nodes are classified into groups, and nodes and links in a group are
aggregated recursively [11]. Figure 1 (a) shows a physical network. A.a.*, A.b.*, A.c.*,
B.a.* and so on are clustered and represented as a logical node, A.a, A.b, A.c and B.a and
so on respectively. This is first-level abstraction and shown in Figure 1 (c). And then
repeatedly A.* is clustered to A, B.* is clustered to B, and C.* is clustered to C. This is
second-level abstraction and shown in Figure 1 (d).
2.3 Topology Aggregation (Network State Aggregation)
The objective of the topology aggregation technique is to allow the application of
both concise and detailed information to the routing. This topology aggregation is
important for scalability in hierarchical large networks and contributes to the reduced
overhead. The nodes are clustered into domains and each domain is connected with
others through border routers (BRs). BRs in a particular domain have detailed
information about their own domain and concise information about neighboring domains.
For example, A.a.3 in Figure 1 (e) has detailed information about connectivity and
resources of its domain (A.a.1, A.a.2, and A.a.4) and aggregated information of A.b. A
BR sends reduced network information to nodes outside of its domain and detailed
information to those within its domain. In other words, it has a complete view for inside
5
the domain and aggregated view for outside the domain. Detailed inside domain
information is aggregated before being advertising. The exchanged information between
domains contains an aggregation of the connectivity and resource availability [10].
Hierarchical QoS routing is the technique to find a feasible path using these detailed and
aggregated information sets [9].
2.4 Maximum Flow Problem
The objective of the maximum flow problem is to find a flow of maximum value
from a single-source to a single-sink in a flow network G = (V, E), where V is a vertex set
and E is a collection of edges. Ford-Fulkerson, Edmonds-Karp, and push-relabel
algorithms are major algorithms to solve maximum flow problem [8]. In this simulation,
Edmonds-Karp is used. We add a super-sink to calculate the advertised capacity. Figure 2
shows an example of calculating advertised capacity when domain B requests to domain
A. The edges are added from c, d, and e to the super sink with an infinity capacity.
Adding a super sink enables max flow algorithm to calculate advertised capacity of the
topology with multiple sinks.
6
(a) Physical network (b) clustering
(c) First-level abstraction (d) Second-level abstraction (e) the network image viewed by node A.a.1
Figure 1. Hierarchical Network Model [7]
B.b.4 B.b.5
A.a.1 A.a.2
A.a.3 A.a.4
A.b.2
A.b.3
A.c.1
A.c.2
A.c.3
A.c.4 A.c.5
B.a.1
B.a.2
B.a.3
B.a.4
B.b.2
B.b.1
B.b.3
B.b.4 B.b.5
C.b.2
C.b.3
C.b.1
C.a.1
C.a.2
C.a.3
C.a.4 C.a.5
A.b.1
A.c.2
C.b.2
C.a.2
A.a.1 A.a.2
A.a.3 A.a.4
A.b.2
A.b.3
A.c.1
A.c.3
A.c.4 A.c.5
B.a.1
B.a.2
B.a.3
B.a.4
B.b.2
B.b.1
B.b.3
C.b.3
C.b.1
C.a.1
C.a.3
C.a.4 C.a.5
A.b.1
A.a
A.b A.c
B.a
B.b
C.a
C.B
A
B C
A.a.1 A.a.2
A.a.3 A.a.4
A.b A.c
B C
7
Figure 2. Max Flow with Multiple Sinks
2.5 Multicommodity Flow Problem
Given a graph G = (V, E) with a non-negative capacity u 0 . There are k
commodity pairs ( , ), ( , ),.......( , ) 1 1 2 2 k k s t s t s t . j s and j t represent source and sink of
commodity j, 1 j k respectively. Let i f be a real-valued function. f (u,v) j is the
flow from vertex u to v of commodity j. Define f (u,v) as an aggregate flow. The
aggregate flow on edge (u,v) is sum of all commodity flows, = = k
j j f u v f u v
1
( , ) ( , ) and
cannot exceed the capacity of edge (u,v). The multicommodity flow problem is to
determine if there is such a flow.
A
B
C
D E
b c
d e
super sink
8
2.6 Maximum Multicommodity Flow Problem
Given a directed network G = (V, E) with non-negative capacities u, E -> R and k
ordered pairs of vertices ( , ), ( , ),.......( , ) 1 1 2 2 k k s t s t s t . The pair, ( , ) j j s t , 1 j k represents
a source-sink terminal pair for commodity j. Let j f be the amount of flow from j s to j t .
The objective of maximum multicommodity flow problem is to maximize the sum of
flows, j j max f without exceeding capacity of any edge [3]. Let j denote the set of
paths from j s to j t and let j j := . Let x(P) define as an amount of flow sent along
path P and let u(e) be a capacity of edge e. The linear programming formulation is
defined as follows:
: ( ) 0.
: ( ) ( )
max ( )
:
P x P
e x P u e
x P
P e P
P
The length of an edge means the “marginal cost of using an additional unit of capacity of
the edges” [3]. Let l denote the length function. When applying lengths to each edge in
the graph, the dual for the above linear program is given as follows:
9
: ( ) 0
: ( ) 1
min ( ) ( )
e l e
P l e
u e l e
e P
e
Fleischer [3] provides pseudo-code for maximum multicommodity flow problem
invented by Garg and Konemann [6], and it is shown in Figure 3. This pseudo-code is
used for simulation.
Figure 3. Maximum Multicommodity Flow Pseudo-Code
Input: network G, capacities u(e), commodity pairs ( , ) j j s t , 1 j k ,
accuracy
Output: primal (infeasible) and dual solutions x and l
Initialize l(e) =
e, x 0
while there is a P with l(P) < 1
select a P with l(P) < 1
( )
, ( ) ( )(1
( ) ( )
min ( )
u e
u
e P l e l e
x P x P u
u u e e P
+
+
end while
Return (x, l).
10
2.7 Maximum Concurrent Flow Problem
Given a directed network G = (V, E) with non-negative capacities u, E -> R and k
ordered pairs of vertices ( , ), ( , ),.......( , ) 1 1 2 2 k k s t s t s t . At commodity j, source-sink pair,
( , ) j j s t has demands j d , 1 j k . The objective of this problem is to maximize the
possible portion of all demands: f d j j j max , , . Let j denote the set of paths
from j s to j t and let j j := . x(P) is defined as an amount of flow sent along path P
and u(e) denotes a capacity of edge e. The notation j z stands for weights at commodity
j. The maximum concurrent flow problem is represented using linear program as follows.
: ( ) 0
: ( )
: ( ) ( )
max
:
P x P
j x P d
e x P u e
P j
j
P e P
The lengths are assigned to the edges just as in the maximum commodity flow problem.
In addition to them, weights are assigned to the commodities. The length of an edge
means “the marginal cost of using an additional unit of capacity of the edges” [3]. The
weight is defined as “the marginal cost of not satisfying another unit of demand of the
11
commodity” [3]. Let l denote the length function. The dual for above linear program is
expressed as follows:
: 0
: ( ) 0
1
, : ( )
min ( ) ( )
1
j
j k
j j
j
e P
j
e
j z
e l e
d z
j P l e z
u e l e
Fleischer’s paper [3] introduces maximum concurrent flow pseudo-code in Figure 4. This
simulation is based on this pseudo-code. Demands should be given as we can see from
her pseudo-code; however, they are not provided in the network topology we use in this
simulation. They are calculated as follows. Add a super sink to border routers which are
not the source border router. Then, calculate maximum flow from source to the super sink
and divide it by the number of (border routers -1). 1 is for source border router.
12
Figure 4. Maximum Concurrent Flow Pseudo-Code
Input: network G, capacities u(e), vertex pairs ( , ) j j s t with demands
d i k i ,1 , accuracy
Output: primal (infeasible) and dual solutions x and l
Initialize l(e) =
/u(e), e, x 0
while D(l) < 1
for j = 1 to k do
j j d' d
while D(l) < 1and ' > 0 j d
P shortest path in j using l
+
+
( )
, ( ) ( ) 1
( ) ( )
' '
min{ ' ,min ( )}
u e
u
e P l e l e
x P x P u
d d u
u d u e
j j
j e P
end while
end while
Return (x,l)
13
2.8 Goodness Measures
The following are used for statistical measurements [10].
Bandwidth Admission Ratio (BAR): Ratio of bandwidth admitted to bandwidth
requested
Bandwidth Over-estimation Ratio (BOR): Ratio of bandwidth dropped in a
domain to bandwidth sent
Bandwidth Under-estimation Ratio (BUR): Ratio of non-forwarded bandwidth
that could have been successful to bandwidth not sent
2.9 General Maximum Flow vs. Maximum and Maximum Concurrent Multicommodity
Flow Algorithms
Suppose that a border router in domain B wants to send to domain E through
domain A in Figure 5. In the general maximum flow problem, it is assumed that other
neighbor domains of A, C and D are not using resources in A. In other words, domains C
and D cannot share resources in domain A. This makes BOR increase and BUR decrease.
We believe that maximum multicommodity flow and maximum concurrent flow
algorithms can reduce BOR since their property allows sharing resources among domains.
14
The maximum multicommodity flow and maximum concurrent flow algorithms can be
better than the general maximum flow algorithm.
Figure 5. Network Model
A
B C
D E
Border Router
15
CHAPTER III
METHODOLOGY
3.1 Discrete Events Simulator (DES)
A DES is a dynamic system model to simulate the flow of people, things or events,
where the system consists of queued events and a virtual clock. Simulation languages
such as GPSS, SIMSCRIPT and SIMULA, as well as simulation software have been
developed. Programming languages can substitute for simulation languages or simulation
software. In this research, we used the Java language to implement both a DES as well as
the routing algorithms to be applied.
3.2 Implementing a DES
The system is simulated for a given number of events. Events can be one of two
kinds: (1) resource reservation event or (2) resource release event. A new, resource
reservation event includes four pieces of information: the time the event occurred, source,
destination and bandwidth required to allocate. The time which the event occurred is
generated by the equation, 1 = n n T T + (exponential random value, 1 μ
), 1 n maximum
number of events. Source and destination domain are randomly chosen from neighbors of
16
main domain and created such that source and destination are not equal. Neighbor
domains request a bandwidth amount of either 1 or 2. The system updates advertised
capacity every 30 seconds as a default value. Once an algorithm decides that the
requested bandwidth can be allocated, then the time when resource along the selected
path will be released is randomly generated by the equation, n n releaseTime = T +
(exponential random value, 2 μ ), 1 n maximum number of events. This release event
is added to a heap data structure. The current network topology, G is copied and edges
whose capacity is less than requested bandwidth are dropped. This copied topology, G’ is
used by Edmonds-Karp algorithm to see if a feasible path is found in the Network
topology. A code sequence of the DES, when the number of events is variable, and the
values of average time between requests and time between updates are fixed, is
summarized in Figure 6.
3.3 Assumptions
Here is a summary of the assumptions made in this simulation.
1. If the network cannot reserve a requested unit, the request is dropped and has no
second try.
2. Source and destination nodes are not the same.
3. Requested bandwidth is either 1 or 2.
17
4. All edges’ capacity is a fixed number, 4.
5. For more accurate results, the simulation is taken 50 times and then averaged.
6. The default values for maximum number of events, update time, and the
average time between requests are 20000, 500 seconds, and 0.05 seconds
respectively.
7. The average time a request uses resource in the network is fixed at 10 seconds.
18
Figure 6. Discrete Events Simulator
for i from 1 to MaxEvents do{
// generate event (time)
// do resource release events
// if current time modulo 500 == 0, update advertised capacity
// generate event (source)
// generate event (destination)
// generate event (bandwidth, 1 or 2)
// check advertised capacity
// copy topology G’ G
// drop edges whose capacity are less than requested bandwidth in G’
// find a path using Dijkstra
If (advertised capacity > request){
If (path is found in G’){
// generate resource release event time
// add this event to heap
}
else if (path is NOT found in G’)
// over-estimation
}
else if (advertised capacity request){
if( path is found in G’)
// under-estimation
}
}
19
3.4 Input
The DES program takes one input file as an argument that contains the network
topology of the main domain with adjacent matrix style: 0 represents no edges between
vertices and 1 means there is an edge between vertices.
3.5 Simulation Circumstances
In this simulation, we tested three circumstances as follows [10].
1) BAR/BOR/BUR vs. Number of events
2) BAR/BOR/BUR vs. Average time between requests
3) BAR/BOR/BUR vs. Time between updates
20
CHAPTER IV
FINDINGS
Three algorithms, maximum multicommodity flow (MMF), maximum concurrent
flow (MCF) and general maximum flow (MAX) are simulated to see how each algorithm
differs from the others under three situations: sensitivity to (1) the number of events, (2)
average time between requests and (3) time between updates. The standard deviations
from mean are from the simulations. The results are shown in the graphs (Figures 7 - 17).
The error bars in some graphs cannot be seen because of their small values. The vertical
lines shown in Figures 7 – 10, 12 – 15, and 17 are connected to the mean and are only
given for visual confirmation.
4.1 Goodness Measures vs. Number of Events
An event is defined as a resource request. This simulation is to see how BAR,
BUR and BOR change as the number of events increase. The number of events is
incremented from 1000 to 40000 at intervals of 1000. The average time between requests
is fixed as 0.05 seconds, update interval is every 500 seconds, and the average time a
request keeps resources in the network is fixed at 10 seconds. The results shown are the
average obtained after 50 runs.
21
4.1.1 BAR vs. Number of Events
The MAX and MMF draw almost the same lines (Figure 7). MCF follows a
similar curve as MMF and MAX do, though the values are not even close. Starting with a
gentle curve and staying flat for a moment, each algorithm decreases quickly and then
keeps stable as the number of events increases. We can say that the BAR becomes lower
and then stable as the number of events increase.
0.04
0.06
0.08
0.1
0.12
0.14
0.16
0.18
0.2
0.22
0.24
0 5000 10000 15000 20000 25000 30000 35000 40000
Bandwidth Admission Ratio
Number of Events
MMF
MCF
MAX
Figure 7. BAR vs. Number of Events
22
4.1.2 BUR vs. Number of Events
MCF stays high from the beginning compared to other algorithms (Figure 8). The
BUR of MMF and MAX stays flat until some point and then increases. MMF keeps
stable with a slight increase, and MAX falls over a narrow range of y as the number of
events increase.
-0.2
0
0.2
0.4
0.6
0.8
1
1.2
0 5000 10000 15000 20000 25000 30000 35000 40000
Bandwidth Under-estimation Ratio
Number of Events
MMF
MCF
MAX
Figure 8. BUR vs. Number of Events
23
4.1.3 BOR vs. Number of Events
MAX stays high from the beginning to the end (Figure 9). On the other hand, the
other two algorithms keep a low BOR. Though MMF decreases slightly, all three
algorithms seem unaffected by the number of events simulated. The characteristics of this
graph are that all lines stay flat, and the standard deviations from the simulations of all
three algorithms are very small. MCF always has a value of zero. Therefore, the error
bars cannot be seen.
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0 5000 10000 15000 20000 25000 30000 35000 40000
Bandwidth Over-estimation Ratio
Number of Events
MMF
MCF
MAX
Figure 9. BOR vs. Number of Events
24
4.1.4 Discussion
As mentioned before, each edge’s capacity is 4, the average time a resource is
kept in use is 10 seconds, information is updated every 500 seconds, and the average time
between requests is 0.05 seconds. We are able to estimate the time the simulation takes,
and how many times network information is updated. The simulation times are calculated
by multiplying the number of maximum event and the average time between requests,
0.05 seconds. At x = 1000, the simulation takes 50 seconds, 1000 times 0.05 equals to 50.
In this case, network is updated just one time, at 0 second. Therefore, between x = 1000
and x = 9000, information is updated only one time, at 0 second. Between x = 10000 and
x = 19000, information is updated two times, at 0 and 500 seconds. The network update
affects performance of some algorithms at x = 10000, 20000, 30000 in BAR and BUR as
graphs show, and we can see the changes of behaviors of goodness measures at these
instances. BOR is not affected by update.
Though MMF and MAX show almost the same performance in BAR, the BOR of
MMF is very low and that of MAX is very high. This tells us that MMF is more
conservative than MAX.
MCF does not perform as well as the two others do in BAR. This is because of
how it is implemented, and is explained in section 2.7. It makes advertised capacity low,
and finally, ends up with poor performance.
25
4.2 Goodness Measures vs. Average Time between Requests
This scenario is to see how BAR, BUR and BOR change as the average time
between requests increases. The results are recorded at x = 0.01, 0.05, 0.10, 0.15, 0.20,
0.25, 0.30, 0.35, 0.40, 0.45. The number of events, the time network information is
updated, and the average time a request uses resources in the network are fixed at 20000
events, 500 seconds and 10 seconds respectively. The results under the standard
deviations from mean due to simulations are the average obtained after 50 runs.
4.2.1 BAR vs. Average Time between Requests
The values of BAR of all three algorithms are almost the same at the beginning,
but the differences increase as the average time between requests grows (Figure 10). The
values of MAX are the highest, and those of MCF are the lowest. We can say that the less
heavily loaded the network is, the better all three algorithms perform, especially MAX.
The unweighted nonlinear regression fits help to see the patterns (Figure 11). The
data sets of MAX, MMF, and MCF are fitted well by y =1.185*(1 e 2.563x ) ,
y = 0.6013*(1 e 4.156x ) , and y = 0.4484*(1 e 2.528x ) respectively. The equations tell us
that MMF is approaching its asymptote faster than others; MAX and MCF increase at
almost the same rate. Since the ratio cannot be above 1, the equation of MAX is
unreasonable. The best fit with the coefficient constrained not to exceed 1.0 is
26
y = 1.0 * (1 e 3.369x ) , although the quality of this fit is not very good.
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45
Bandwidth Admission Ratio
Avg Time between Requests (sec)
MMF
MCF
MAX
Figure 10. BAR vs. Average Time between Requests
27
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45
Bandwidth Admission Ratio
Avg Time between Requests (sec)
1.185 * (1-exp(-2.563 * x))
0.4484 * (1-exp(-2.528 * x))
0.6013 * (1 -exp(-4.156 * x))
1.0 * (1-exp(-3.369 * x))
MMF
MCF
MAX
Figure 11. Unweighted Nonlinear Regression Fits
4.2.2 BUR vs. Average Time between Requests
MCF values do not change and keep a high ratio (Figure 12). The values of MMF
start low with high standard deviations, get higher quickly, and keep their high values
with small standard deviations. The values of MAX increase quickly after the beginning
stage, and then seem to be stable, although they show some variation.
28
0
0.2
0.4
0.6
0.8
1
1.2
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45
Bandwidth Under-estimation Ratio
Avg Time between Requests (sec)
MMF
MCF
MAX
Figure 12. BUR vs. Average Time between Requests
4.2.3 BOR vs. Average Time between Requests
The values of MCF and MMF are always low (Figure 13). On the other hand, the
MAX line shows dramatic changes; decreasing as the time increases. The standard
deviations from mean for all three algorithms are extremely small, especially in longer
average time between requests. This is why the error bars cannot be seen in the graph.
29
-0.1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45
Bandwidth Over-estimation Ratio
Avg Time between Requests (sec)
MMF
MCF
MAX
Figure 13. BOR vs. Average Time between Requests
4.2.4 Discussion
This simulation shows the influences of updates frequency as well as the network
load.
We can estimate the time when the simulation ends by multiplying maximum
number of event and average time between requests. In this simulation, 20000 is the
number of maximum event. At x = 0.05, information is updated 2 times and 18 times at x
= 0.45. Low x values means a heavily loaded network and high x values are for a lighter
load.
30
In BAR, all algorithms result almost 0% at x = 0.01. Heavy load and infrequent
updates cause this low ratio. Raw data shows us that numerator (accepted bandwidth) is
extremely low. As the average time between requests increases, the network becomes less
heavily loaded, and also the network information is updated more frequently. This
reflects increases of the accepted bandwidth. As a result, BAR increases in all algorithms.
The way each algorithm is implemented shows different increase rates in BAR graph.
MAX is using general max-flow algorithm, so its returning advertised capacity may be
large. As described in section 2.7, MCF will result in a low advertised capacity.
The business of network and frequency of updates do not influence BUR, but may
have impacts on the BOR of MAX. As the network is less heavily loaded with more
accurate network information, bandwidth dropped in the main network becomes less;
therefore, we can see a declining line in Figure 13.
4.3 Goodness Measures vs. Time between Updates
This simulation is to see how BAR, BUR and BOR change as the time between
updates increases. The results are recorded at x = 10, 50, 100, 150, 200, 250, 300, 350,
400, 450, 500. The number of events is fixed at 20000 events, the average time between
requests is 0.05 seconds, and the average time a request uses resource in the network is
fixed at 10 seconds. The averaged values are obtained after 50 runs.
31
4.3.1 BAR vs. Time between Updates
The values of two algorithms, MMF and MAX, are especially unstable and their
lines curve almost the same after x = 150 (Figure 14). The differences between mean of
MMF and MAX are less than 2% after x = 200. As seen from the graph, the standard
deviation of MAX is high after x = 250 and that of MMF is small. Therefore, the line of
MMF and MAX could be much closer. The values of MCF seem to be stable.
0.04
0.06
0.08
0.1
0.12
0.14
0.16
0 50 100 150 200 250 300 350 400 450 500
Bandwidth Admission Ratio
Time between Updates (sec)
MMF
MCF
MAX
Figure 14. BAR vs. Time between Updates
32
4.3.2 BUR vs. Time between Updates
The values of MCF are the highest and MAX are the lowest (Figure 15). MMF
has high values at the very short update intervals, but decrease gradually. The values of
MCF keep flat. Those of MAX look unstable, but it seems they are within some range.
BUR of MCF is inadequate, but that of MMF is not as bad as MCF. MAX displays
reasonable result values.
Unweighted nonlinear regression fits show that the data set of MMF is fitted well
by y = 0.710 + (1 0.710)*e 0.00311x in Figure 16. The equation says that y values
approach to y = 0.710 as further simulation occurs.
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
1.1
0 50 100 150 200 250 300 350 400 450 500
Bandwidth Under-estimation Ratio Time between Updates (sec)
MMF
MCF
MAX
Figure 15. BUR vs. Time between Updates
33
0
0.2
0.4
0.6
0.8
1
0 100 200 300 400 500
Bandwidth Under-estimation Ratio
Time between Updates (sec)
0.710 + (1-0.710) * exp(-0.00311 * x)
MMF
MCF
MAX
Figure 16. Unweighted Nonlinear Regression Fits with MMF
4.3.3 BOR vs. Time between Updates
The values of MAX are the highest among the three algorithms (Figure 17). The
values of MMF gradually get higher and keep stable, and MCF stay extremely low from
the beginning to the end. MAX begins with slightly low values, but the values increase
gradually and keep flat.
34
-0.1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0 50 100 150 200 250 300 350 400 450 500
Bandwidth Over-estimation Ratio
Time between Updates (sec)
MMF
MCF
MAX
Figure 17. BOR vs. Time between Updates
4.3.4 Discussion
The simulation time is estimated by multiplying number of maximum event and
the average time between requests; 20000 times 0.05 equal to 1000 sec. With this time
and x value, we can see how many times network information is updated. The smaller the
x value, the more updates occur. It seems that they do not affect the performance. There
are no recognizable patterns on simulations except BOR. Here, also, how MCF is
implemented seems to affect the performance.
35
4.4 Summary of Findings
We carried out simulations using three variables: (1) number of events, (2) time
between requests, and (3) time between updates. Some graphs are obvious to see that they
are affected by number of update times and network density. However, we cannot see
recognizable patterns in some graphs.
In (1) and (3), MMF and MAX have almost the same performance in BAR. The
BOR of MMF always shows an extremely low ratio. The way how each algorithm is
implemented may help us to understand some of results. MAX calculates its advertised
capacity by adding super sink, and returns a large number. On the other hand, MMF
returns its advertised capacity so that each path can have maximum flow. Therefore, its
number may not be as large as MAX’s. This differences show well in some BOR graphs.
We conclude that MMF is more conservative than MAX.
We can also explain poor MCF performance by how it is implemented. As
mentioned in section 2.7, it returns a low advertised capacity. In conclusion, its
performance is not as good as the other’s in BAR. We are sure that a network topology
with precise demands would increase its performance relative to the others.
36
CHAPTER V
CONCLUSION
The higher BAR and lower BOR and BUR are, the better the algorithm is. The
motive of this research is to demonstrate that maximum multicommodity flow and
maximum concurrent flow algorithms can result in lower BOR than the general
maximum flow algorithm. This is because the general maximum flow algorithm finds a
path from a single source to a single destination and does not allow sharing of resources
which are requested from other domains. On the other hand, maximum multicommodity
flow and maximum concurrent flow algorithms can deal with multiple sources and
destinations and the problem of sharing resources with other domains. Their purpose is to
maximize all paths’ resource usage in the network. As we expected, maximum
multicommodity flow and maximum concurrent flow algorithm reduced BOR. Also, we
find that maximum multicommodity flow and general maximum flow algorithm produce
almost the same results in BAR under heavy network usage with a long enough time
between updates.
In addition to this, we can conclude that the maximum multicommodity flow
algorithm is a more conservative approach than the general maximum flow algorithm.
This is because the general maximum algorithm calculates advertised bandwidth
capacities that can be forwarded through the main network; giving a tendency to return
37
large values. On the other hand, the advertised bandwidth capacities calculated by
maximum multicommodity flow algorithm are reasonable in that it computes the values
which can be routed with 100% guarantee to border routers in other domains.
As future work, various situations should be performed such as using a broad
range of capacity of edges and request bandwidth, networks with more nodes and
neighbor domains, dense networks, sparse networks, the length of time a resource is kept,
etc. In addition to these, it would be exciting to simulate MCF again using demands of
each commodity pair as an input.
Further development and analysis are needed for the QoS seeking algorithms to
be used in the Internet [5]. I believe that this research can be another step toward the fast
and efficient next generation network.
38
REFERENCES
[1] F. Hao and E. W. Zegura, “On Scalable QoS Routing: Performance Evaluation of
Topology Aggregation,” in Proc. IEEE INFOCOM, pp. 147-156, Mar. 2000.
[2] K.S. Lui, K. Nahrstedt, and S. Chen, “Hierarchical QoS routing in delay-bandwidth
sensitive networks,” in Proc. of IEEE LCN, Tampa, FL, pp. 176-189, 2000.
[3] L. K. Fleischer, “Approximating fractional multicommodity flow independent of the
number of commodities,” SIAM J. Discrete Math. vol. 13, no. 4, pp. 505-520, 2000.
[4] M. Bouklit, D. Coudert, J-F. Lalande, C. Paul, and H. Rivano, “Approximate
Multicommodity Flow for WDM Networks Design,” SIROCCO ’03, 2003, pp. 43-56.
[5] M. Gopal, and K. Latha, “A QoS Engineering Architecture for the Next-Generation-
Internet,” in Proc. of the International Conference on Computer Communications
and Networks, 1998, pp. 599.
[6] N.Garg and J. Könemann, “Faster and Simpler Algorithms for Multicommodity Flow
and other Fractional Packing Problems,” in Proc. of the 39th Annual Symposium on
Foundations of Computer Science (FOCS), Nov. 1998, pp. 300-309.
[7] S. Chen and K. Nahrstedt, “An Overview of Quality-of-Service Routing for the Next
Generation High-Speed Networks: Problems and Solutions,” IEEE Network, vol. 12,
no. 6, pp. 64-79, Nov.-Dec. 1998.
[8] T. H. Cormen, C. E. Leiserson, R. L. Riverst, and C. Stein, Introduction to
Algorithms, 2nd edition. Cambridge, MA: MIT Press, 2001.
39
[9] V. Sarangan and R. Acharya, “A study on using network flows in hierarchical QoS
routing,” GLOBECOM ’01, vol. 4, pp. 2188-2192, 2001.
[10] V. Sarangan, D. Ghosh, and R. Acharya, “Capacity-Aware State Aggregation for
Interdomain QoS Routing,” IEEE Transactions on Multimedia, vol. 8, no. 4, pp. 792-
808, Aug. 2006.
[11] W. C. Lee, “Topology aggregation for hierarchical routing in ATM networks,” in
ACM SIGCOMM Computer Communication Review, vol. 25, no. 2, pp. 82-92, Apr.
1995.
[12] W. Pak and S. Bahk, “Partial Optimization Method of Topology Aggregation for
Hierarchical QoS Routing,” IEEE International Conference on Communications, vol.
2, pp. 1123-1127, Apr. 2002.
[13] Y. Jia, I. Nikolaidis, and P. Gburzynski, “On the effectiveness of alternative paths in
QoS routing: Research Articles,” International Journal of Communication Systems,
vol. 17, pp. 1-26, 2004.
VITA
Satoko Chika
Candidate for the Degree of
Master of Science
Thesis: USING MAXIMUM AND MAXIMUM CONCURRENT
MULTICOMMODITY FLOWS FOR QOS ROUTING IN THE INTERNET
Major Field: Computer Science
Biographical:
Education: Received Bachelor of Science degree in Computer Science and
Engineering from The University of Aizu, Aizu-Wakamatsu,
Fukushima, Japan in March 2002; Completed the requirements for the
degree of Master of Science in Computer Science at Oklahoma State
University, Stillwater, July 2007.
Name: Satoko Chika Date of Degree: July, 2007
Institution: Oklahoma State University Location: Stillwater, Oklahoma
Title of Study: USING MAXIMUM AND MAXIMUM CONCURRENT
MULTICOMMODITY FLOWS FOR QOS ROUTING IN THE
INTERNET
Pages in Study: 39 Candidate for the Degree of Master of Science
Major Field: Computer Science
Once we connect the network cable to a plug-in jack on the wall, ‘connecting’ is a
mundane event unless the service is unavailable. “How can we use limited resources
efficiently in the Internet?” is an important question for future development. Efficiency is
a requirement for next generation networks and will be a major benefit of QoS routing in
the Internet. In this research, we simulated a simple network topology using general
Maximum Flow, Maximum Multicommodity Flow and Maximum Concurrent Flow
algorithms to calculate advertised bandwidth capacities. Under sensitivity to (1) number
of events, (2) average time between requests and (3) time between updates, the results
from the simulations showed that the Maximum Multicommodity Flow Algorithm is
more conservative than a general Maximum Flow Algorithm. The Maximum Concurrent
Flow Algorithm did not perform well compared to the others in this simulation.
ADVISER’S APPROVAL: Dr. Venkatesh Sarangan