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