=Paper=
{{Paper
|id=None
|storemode=property
|title=Analyses of QoS Routing Approach and the Starvation's Evaluation in LAN
|pdfUrl=https://ceur-ws.org/Vol-920/p63-bejleri.pdf
|volume=Vol-920
|dblpUrl=https://dblp.org/rec/conf/bci/BejleriTBBF12
}}
==Analyses of QoS Routing Approach and the Starvation's Evaluation in LAN==
https://ceur-ws.org/Vol-920/p63-bejleri.pdf
Analyses of QoS Routing Approach and the Starvation’s
Evaluation in LAN
Ariana Bejleri Igli Tafaj Aleksander Biberaj
Polytechnic University of Tirana Polytechnic University of Tirana Polytechnic University of Tirana
Faculty of Information Technology Faculty of Information Technology Faculty of Information Technology
Computer Engineering Department Computer Engineering Department Electronic and Telecommunication
Tirana, Albania Tirana, Albania Engineering Department
arianabejleri@yahoo.com itafaj@gmail.com Tirana, Albania
a.biberaj@yahoo.com
Ermal Beqiri Julian Fejzaj
Tirana University Tirana University
Mathematics & Statistics & Applied Informatics Faculty of Natural Sciences
Department Department of Computer Science
Tirana, Albania Tirana, Albania
ermalfr@yahoo.fr Julian.fejzaj@fshn.edu.al
ABSTRACT which means that the receiver of the data flow is responsible for
This paper gives a survey in QoS Routing Architecture the reservation of resources.
implemented by Dijkstra’s algorithm. The performance of QoS Qos Routing has a higher level admission control mechanism [5]
Routing architecture is evaluated by made a comparison between in order to ensure that the selected path does not utilize the
the Shortest Path Routing and QoS one. A very important feature resources network for a long time.
in QoS routing are the conditions for elimination of starvation.
Shortest Path Forward (SPF) Routing based on number of hops
Experimentally we have evaluated the number of packets delivery
from source to destination. Often the SPF Routing leads to
from source node to destination one in QoS Routing architecture
unbalanced traffic, so it can cause the congestion of packets in
with high and low priority classes based on ns-2 simulator.
network while the QoS Routing architecture provides a better
Keywords performance in both of them during the data transmission. Traffic
QoS routing architecture, Dijkstra’s algorithm, shortest path Engineering in QoS Routing is the process of traffic flow’s
routing, starvation arrange in network by avoiding the congestion.
Constraint-based Routing (CBR) architecture includes the QoS
1. INTRODUCTION Routing architecture. Constraint-based Routing is a general
QoS Routing (Quality of Service Routing) is the architecture that definition, which combines QoS Routing ( i.e bandwidth, delay,
takes into consideration some elements such as the necessary loss) and Policy Routing. It is an extension of QoS Routing
bandwidth, delay, throughput, jitter. Based on these elements this architecture by take in consideration, QoS requirements, network
architecture selects the specified path that satisfy the Quality of policies and utilization of the network resources in order to
Service requirements. In [4] QoS Routing gets the information prevent the congestion traffic [2].
about network state and resources availability. Also it based on
some factors such as: Dynamic determination of the feasible paths The goal of CBR is to enable a new routing paradigm with special
which can accommodate the QoS requirements in data flow over properties, such as Resource Reservation-Aware and Demand-
the network, the optimization of resources uses etc. QoS helps Driven. The Information from different resources offer the
workload balancer in network to manage the resources. So it possibility of selection specified path.
should affect in performance improvements of the total The first goal in this paper is the comparison between QoS
throughput. QoS Routing has the ability to provide better Routing and Shortest Path First Routing which significantly
throughput in the network than Best Effort Routing (Internet based on the number of hops. This paper is organized as follows.
Communication). In Section II, we presents the QoS Routing architecture based on
QoS Routing finds the feasible path in order to guarantees the Dijkstra Algorithm. At this topic we theoretically examine
routing information but it cannot ensure the stability of selected stability, robustness and scalability. In Section III, we briefly
path. Resources Reservation Protocols can be used to allocate the discuss some experiments based on ns-2 simulator and benchmark
necessary resources during the data transmission in the selected tool called Httperf. This tool will compare the performance of
path. One of the most popular protocol reservation is RSVP QoS Routing with Shortest Path Routing by presenting the
(Resource Reservation Protocol). It is receiver oriented protocol, Starvation results. At the end of this paper are the conclusions and
references.
BCI’12, September 16–20, 2012, Novi Sad, Serbia. 2. ROUTING ALGORITHMS APPROACH
Copyright © 2012 by the paper’s authors. Copying permitted only for private and
academic purposes. This volume is published and copyrighted by its editors. Routing Algorithms are the basics elements in the selection of
Local Proceedings also appeared in ISBN 978-86-7031-200-5, Faculty of Sciences, necessary path. Wrong selected path causes the leak of utilization
University of Novi Sad.
63
resources and services. In our days a very important topic is through the reservation protocols. Jitter offers the variable time
utilization of services in order to give a satisfaction for every delay of packet transmitted from source to the destination.
internet user. QoS Routing Architecture is a basic constrain which In the former way [1], Additive and Concave metrics can
can implement in all kinds of Routing. The selection of a path is presented:
not easy, because there are a lot of diversity of the network
topologies. Some of them are network mobile and most of them Additive if w(P) = w(u1; u2) + w(u2; u3) + : : : + w(ul¡1; ul) (1)
haven’t any solid infrastructure (Such as Ad-Hoc Networks). Concave if w(P) = min(w(u1; u2);w(u2; u3); : : : ;w(ul¡1; ul)). (2)
Nevertheless it follows the same way for all routing
communication approaches. In figure1 we give an example of
path selection. In this figure presented a communication form Based on these features QoS put some numbers for each path
between 2 users. All the communications are supported by destination. Dijkstra’s algorithm take a decision for routing
ethernet interface with utp cat 7 technique. Also we have packets based on some numbers which are implemented for a
presented a network with two broadcasters which routes video QoS Routing. The Router device is a Forwarding Packet Core
packets stream based on Dijkstra Algorithm. As we presented in Architecture. Each packet which arrive at destination router,
this figure, there are some possibility (links) for routing packets. initially buffered, then it transmits according to Dijkstra
The Dijkstra Algorithm does check of the whole available paths Algorithm.
and finds the best one. To find the better solution it should In our example in figure 2 video packet stream from source to the
supported from two features: Number of hops and link states. destination should be transmitted by following this path:
Some different protocols are built on these approaches, i.e RIP R1-R5-R6-R4-Switch-Server Destination
(Routing Information Protocol) which is based on Number of Let’s give an algorithm for all required steps:
hops between hosts. This algorithm has a disadvantage because it
generates a lot of traffic (for every path-finder, the router sends a
full routing table to the neighbors router) . Another one is OSPF 1. R1-R5 = 2, R1-R7 = 5,. Dijkstra Algorithm utilizes the
(Open Short Path First) which is based on Link State Routing shortest distance.
information. This algorithm sends packets from source to a target 2. R5 – R6 because this is a single route to destination.
destination based on state of the link such as throughput, delay, 3. R6-R4 because there is smaller value in the path
packets drop etc. These features are depth analyzes in QoS (valuated from QoS =1)
Architecture which is built on each router in figure 1. This 4. R6-R3 is equal 3. So the final path from source user to
architecture based on 4 elements: Bandwidth which is a concave destination is: R1-R5-R6-R4.
metric. This denotes that some bandwidth should be available 5. If selected another path from R1 Router: R1-R7 (Value
(reserved) for QoS flows. This resource evaluated as min/max =5)
approach, because the request for minimum (bottleneck) 6. R7-R8 because these is the only path remained.
bandwidth on the path is necessary for transmission of packets. 7. At this point there are 2 possibility: R8-R2 and R8-R4.
The goal of QoS Routing is to find the feasible path with the Their values are 3.
maximum bandwidth [1]. 8. If R8-R2 is selected, there are 2 possibilities: R2-R1 or
R2-R3. If the first path is selected, an fatal error will
occur, because R1 is the initially router. R2 router
couldn’t sends the packets in R1 router because at the
first moment it’s routing table is updated previously
from R1. Thus there is just one possibility R2-R3.
9. Again in router R3 there are two possibilities: R3-R6
and R3-R4. As it shown in figure 2, values in R3-R6 =
3 and R3-R4=5. The small value is R3-R6. This is a
temporarily destination.
10. The only way for forwarding packets from R6 Router is
R6-R4 because routing table is previously updated from
R3 and R5 [1],[6]. The destination packet should be sent
to R4
11. R4 is previously updated from R8 Routing Table too.
12. Finally the selected path is R1-R5-R6-R4-Server
Dijkstra Algorithm is not the only algorithm for the selection of
available path. One of the interesting algorithm is Bellman – Ford.
Figure 1: Communication between two users with Dijkstra’s Both algorithms are used to assign the policy of data
algorithm. communications between source and destination. Below we are
presented the difference between those algorithms [7]:
Delay, Reliability and Jitter. The last three elements are additive
metrics. The Delay Metric causes the latency of packets which are Dijkstra's Algorithm
transmitted between source and destination over the network. For 1) Dijkstra doesn't work for negative weight edges.
delay-sensitive requests, some of the links can be pruned from the 2) Time complexity of Dijkstra is O(|E| + |V|Log|V|)
graph before selecting the path. The Reliability assigns the 3) Dijkstra's algorithm is usually the working principle algorithm
acceptable data loss rates, which previously are guaranteed which is behind link-state routing protocols, OSPF and IS-IS
64
Bellman-Ford's Algorithm We have organized some experiments with this simulator, by
1) Some kinds of Bellman–Ford algorithm is used in distance- using two algorithms: Shortest Path First algorithm, which is
vector routing protocols. based on number of hops and QoS algorithm which is based on
2) Bellman-Ford works for non negative weight edges. both: Distance Vector Routing and Link State Routing.
3) Time complexity of Bellman Ford takes O(|V||E|) time which All graphs are generated from nam tool.
can also be written as O(|V|^3) Initially, we can generate automatically by using a script in C
Some CBR challenges which are based on QoS constrains are Language up to 400 router nodes with ns2 simulator in Full Mesh
stability, robustness and scalability. topology, Full duplex link and supported by RIP version 2 policy
of routing. In this script we have assign a IP’s range of C class.
In the first constrain every node in a network must maintain local This script automatically plays similar role with DHCP (Dynamic
state information. Those information include available bandwidth, Host Control Protocol) service. We have created a network
queuing management and propagation delays. A reasonable environment by using the nam tool. This script is located in /proc
question is how frequently the Routing Table updates inside a directory of Linux CENTOS 5.5 installed in my laptop. Each
Router. High frequency of updates, increase the traffic computer takes one IP. The results of simulation are presented in
engineering and routing overhead, on the other hand if we table 1.
minimize the frequency update, we will get the inaccurate
information. To balance this tradeoff, generation of the update Table 1: The Ratio Between Network Size and CPU Time
packets can be advertised whenever there is a significant change Consuming by Using Two Algorithms
in the values of the resources [3]. There are two improvement
ways: absolute scale, which divide the range of values into Network Size CPU consuming CPU consuming
equivalence classes, and relative scale, which triggers the update (ms) in SPF (ms) in QoS
when the percentage of change since the last advertisement 50 100 230
exceeds a given threshold.
Robustness means allocation of an adaptive route. When 100 720 990
resources are sending inaccurate information in the specified
150 1080 1700
router, the QoS selection path is not the best one. Based on this
inaccurate information a fatal error can occur. The Robust path 200 1570 2500
means that the selected path offers permanent QoS application
services during the different workloads and different times. After 250 1910 3010
we commit some tests (as much as we can) we can select the
robust path which satisfy the QoS requirement. This is an 300 2000 3560
advantage in Virtual Circuit Switching Technology.
350 2060 4020
Scalability is the situation when growth and shrink of network
edge and network core do not affect directly on the network and 400 2320 4900
applications performance.
The final situation is evaluation of starvation in QoS routing As it looks in table 1 and in figure 2 SPF algorithm growth in
environment. If some packets with different priority classes shares linear form, as much as number of network size and time
the network, packet with low priority can dropped. This happen processing increases. Also the QoS algorithm has a linear curve
because each packet class has it’s own time of life. If the time for but it consumes more times than SPF algorithm. The reasons are
this packet located in buffer of any nodes exceeds, it means that that QoS algorithm should execute more values than SPF
this packet is not transmitted yet to the destination node, so the algorithm (So it can processing not only the number of hops, but
probability that packet drops, increases. In third topic we will throughput, necessary bandwidth, delays of packets too). For
study this situation by using some experiments. these reasons it causes more delay than SPF Algorithm.
Another experiment is elimination of Starvation for three packet
3.EXPERIMENTAL PHASE classes. This experiment is performed in a real application.
Initially the experiments do not belong to Dijkstra and Bellman
Ford Alogrithm, but only with QoS Routing Algorithm and the
ratio of this algorithm with Shortest Path Forward Algorithm.
Second we have analyses the Starvation in QoS Routing
Algorithm. These topic is organized in 2 phase. In the first one,
we want to test QoS Constrains depends on network size and in
the second phase we want to evaluate the necessary bandwidth for
different packet classes in order to minimize the starvation.
At first we can show briefly what kind of tools we have used in
our experiments. All simulations are organized on a host
computer.
Ns-2
Nam
Tools_Patch_Ns2_for_Graph
Figure 2: Ratio between network size and time consuming
with the two algorithms.
65
In this graph in x-axis is network size and y-axis is time and Email=1. All these priority are assigned by
consuming in network. Graph with red color is referred to QoS “Video_Tooling_4_All_TKO. Bandwidth communication
algorithm and with blue is Shortest Path First algorithm between 2 hosts is 1 Gb/sec in LAN and 5 Gb/sec in the physical
machine.
3.1 Experimental Environment For the first experiment , a benchmark, called httperf is used for
generating the packets from Client (CENTOS 5.5) to Server
There are 2 VM (Virtual Machines) above a Host (XP_OS)
Physical Machine with Win XP 32 bit (The physical From the client side we can generate randomly 6000 packets to
host parameters are the same as we mentioned above) Server destination:
Type of Virtualization: Full Virtualization (VMWare Httperf –server 192.168.1.100 –uri /TKO.html –num-con 6000 –
Workstation 7.1 ) rate=10 –timeout5
In the first VM is built XP Operating System TKO.html is a html file in Apache Web Server which is used from
In the second one is built CENTOS 5.5 Operating Video_Tooling_4_All_TKO. This method utilizes these packets
System based on our assigned priority. TKO.html randomly distributes
Both of them uses 500 MB RAM. packets classes.(An additive module is included in this benchmark
CPU 1 for each VM - This is not the study of this paper)
Core 2 for each VM From this experiment we introduced that Video Calling packet
WAMP5 1_4_7 installed on VM1 (WAMP-Windows, would generate 94% of total packets, FTP 5% and E-mail 1 %.
Apache, My SQL, Php) If we want to use Email more than 1% of time, a starvation will
Httperf benchmark occur.
Client 192.168.1.10 255.255.255.0 We can repeat the experiment for 2 physical machines with 2
Server 192.168.1.100 255.255.255.0 virtual machines above respectively. As we mentioned previously,
Video_Tooling_4_all_TKO both physical machines can communicate with twisted pair utp
cat. 7 cable. The results are:
As it look from the description, we have used 2 virtual machines Video calling packet would generate 92 % of total packets, FTP 6
which can communicate with each other as a team in LAN. The % and E-mail 2%. If we make a comparison between first
experiment is organized for 2 VM in the same computer. experiment and second one we can see that video stream packets
The experiment is repeated again with 2 physical machines which reduce from 94 % to 92%, FTP packets from 5% growth to 6 %
support respectively 2 VM. Both physical machines are connected and Email packet from 1 % up to 2 %. The reason is the
by twisted pair utp cat 7 cable. bandwidth. At the first experiment the speed of communication is
The final experiment is tested with 4 physical machines in LAN 5 Gbit/sec but in the second case it is just 1 Gbit/sec.
which are connected with switch gigabit Ethernet. All machines The final experiment shows us the situation of 4 computers which
support respectively 2 VM, as it shows in figure 3. are connected with a gigabit switch in LAN. In a computer we can
generate randomly the traffic packets with httperf benchmark. The
results change from both previously experiments. Generation of
Video calling packets reduce to 90%, FTP packets reduce to 7%
and E-mail packet reduce to 3%. We got these results because of
the switch which introduces the complexity of hardware
architecture. [6] . This situation is reflected in packets with big
sizes. So the bandwidth for small packets with low priority will
increases and the total number of these packets will increases too.
Table 2: Ratio Between Video Stream, FTP and E-mail
Packets with Different Topology
Video Stream FTP E-mail Topology
94% 5% 1% Inside
Figure 3: Four computers which are connected by gigabit
switch. Each computer has two VM. Physical
Machine
92% 6% 2% Twisted Pair
In our experiment we have used the manageable switch. The
90% 7% 3% Switch
situation is the same if we use just a simple switch. Packets are
transmitted in Layer 2 of OSI (Open System Interconnection)
model, by using the broadcast technique. Each computer has its
own gigabit Ethernet card and there are connected by utp cat 7 4. CONCLUSIONS
cable (Unshielded Twisted Pair Category 7). All computers have
As a conclusion of this paper we can show that the QoS Routing
the same architecture as there are in the first experiment. Each
Architecture is a big factor in routing technology. It asks better
computer is configured with C class IP (Internet Protocol) private.
performance than other routing architectures. As it looks from the
There are three packet classes. In the first class there are Video
experiments, if the time of processing is increases the number of
Stream packets. In the second there are generated FTP (File
network size will increases too. The evaluation of starvation is a
Transfer Protocol) packets and in the third one the Email packets.
very interesting thing which is very important in QoS architecture.
In the video stream packet we have set the priority=5. In FTP=2
For three different generated classes in server only email could be
66
hurt from the starvation. Anyway the risk of email’s starvation
reduces, because of some troubles which are induced from packets
with big size (i.e video stream packet). So the total consumed
bandwidth from video stream packet will be reduced. The remain
part of bandwidth can utilized from smaller packets (The reasons
of this situation are not study in this paper)
In the future we will verify the starvation between different
classes in order to satisfy QoS routing Architecture in Network
with different topology.
5. REFERENCES
[1] Andrew Tanenbaum, “Computer Network 4th Edition”, Chap
4 pp. 205–220, 2007
[2] Awduche, D. Malcolm, J. Agogbua, J. O’Dell, M. and Mc-
Manus, J, “Requirements for Traffic Engineering over
MPLS,” RFC 2702, 2003
[3] Apostolopoulos, G. Williams, D. Kamat, S. Guerin, R.
Orda, A. and Perzygienda, T, “QoS Routing Mechanisms
and OSPF Extensions,” RFC 2676, 2003
[4] Crawley, E. Nair, Rajagopalan, R. B. and Sandick, H,. “A
Framework for QoS-based Routing in the Internet,” RFC
2386, 1998
[5] G. Apostolopoulos, R. Guerin, S. Kamat, and S. Tripathi,
"Quality of service based routing: a performance
perspective", In Proceedings of ACM SIGCOMM’98
Conference, pp. 17–28, 1998
[6] James Curose “Network Computing”, p.188, 2009
67