A Throughput Optimizing Routing Protocol for Wireless Mesh Networks

A Throughput Optimizing Routing Protocol for Wireless Mesh Networks Seminar ID: 1582 A Technical Seminar Report submitted for fulfillment of the requirements for the Degree of Bachelor of Technology Under Biju Pattnaik University of Technology Submitted By NISHANT KUMAR Roll No. # CSE 201010340 March- 2013 Under the guidance of Prof. Jaydip Sen NATIONAL INSTITUTE OF SCIENCE & TECHNOLOGY PALUR HILLS, BERHAMPUR, ODISHA –761008, INDIA ABSTRACT Wireless mesh networks (WMNs) are evolving as a key technology for nextgeneration wireless networks showing raid progress and numerous applications. These networks have the potential to provide robust and high throughput data delivery to wireless users. In a WMN, high speed routers equipped with advanced antennas, communicate with each other in a multi-hop fashion over wireless channels and form a broadband backhaul. However the throughput of a WMN may be severely degraded due to presence of some selfish routers that avoid forwarding packets for other nodes even as they send their own traffic through the network. This report presents an algorithm for detection of selfish nodes in a WMN. It uses statistical theory of inference for reliable clustering of the nodes and is based on local observations by the nodes. Simulation results show that the algorithm has a high detection rate while having a low rate of false positives. i ACKNOWLEDGEMENT I would like to express my sincere gratitude to Prof. Jaydip Sen, Faculty Advisor, for his valuable advice and constant support throught the period of my seminar and mini project preparation. I owe special thanks to Mr. Ranjit Kumar Behera technical Seminar co-ordinator for giving his valuable suggestion for this event. We thank Prof. Sangram Mudali, for his continued drive for better quality in everything that happens at NIST and we thank our Placement Director, Prof. Geetika Mudali for her constant encouragement. This report is a small contribution towards the greater goal. Last but not the least, I express my heartfelt gratitude to my parents for their support and effort in making what I am and to my friends whose help was always available whenever I needed it. NISHANT KUMAR ROLL NO-201010340 BRANCH-CSE ii TABLE OF CONTENT ABSTRACT .................................................................................................................... i ACKNOWLEDGEMENT .............................................................................................ii TABLE OF CONTENT ................................................................................................iii LIST OF FIGURES ...................................................................................................... iv 1. INTRODUCTION ..................................................................................................... 1 2. RELATED WORK .................................................................................................... 3 3. WMN ROUTING CHALLENGES ........................................................................... 5 4. THE PROPOSED ROUTING PROTOCOL ............................................................. 8 4.1. Estimating reliability of routing paths................................................................. 8 4.2. Use of multi-point relay nodes ............................................................................ 8 4.3. Estimating available network bandwidth ............................................................ 9 4.4. Routing through the fixed network ..................................................................... 9 5. SIMULATION RESULTS ...................................................................................... 11 5.1. Control Overhead .............................................................................................. 12 5.2. Network throughput .......................................................................................... 13 6. CONCLUSION ........................................................................................................ 15 REFERENCES ............................................................................................................ 16 iii LIST OF FIGURES Figure 3.1. The Architecture of a WMN........................................................................ 5 Figure 5.1 Control overhead (bytes) vs. number of data source nodes (50 nodes in the network) ..................................................................................................... 12 Figure 5.2 Control overhead (bytes) vs. number of data source nodes (75 nodes in the network) ..................................................................................................... 13 Figure 5.3. Network throughput (Bps) vs. number of data source nodes (50 nodes in the network) ............................................................................................... 14 Figure 5.4. Network throughput (Bps) vs. number of data source nodes (75 nodes in the network) ............................................................................................... 14 iv 1. INTRODUCTION Wireless mesh networking has emerged as a promising concept to meet the challenges in next generation networks such as providing flexible, adaptive, and reconfigurable architecture while offering cost-effective solutions to the service providers. Unlike traditional Wi-Fi networks, where each access point (AP) is connected to a wired network, in WMNs only a subset of the APs are required to be connected to a wired network. The APs that are connected to the wired network are called the Internet gateways (IGWs), while the APs that do not have wired connections are called the mesh routers (MRs). The MRs are connected to the IGWs using multi-hop communication. Due to the recent research advances in WMNs, these networks have been used in numerous applications such as in home networking, community and neighborhood monitoring, security surveillance systems, disaster management and rescue operations etc. In a community-based WMN, a group of MRs managed by different operators form an access network to provide last-mile connectivity to the Internet. As with any enduser supported infrastructure, ubiquitous cooperative behavior in these networks cannot be assumed a priori. Preserving scarce access bandwidth and power, as well as security concerns may induce some selfish users to avoid forwarding data for other nodes, even as they send their own traffic through the network. The selfish behavior of an MR increases the latency in packet delivery and packet drops and decreases the network throughput in a WMN. To address the issue of detection of selfish nodes in a WMN, this report presents a scheme that is based on local observations in the nodes. The scheme is applicable for on-demand protocols like AODV, and uses statistical theory of inference and clustering techniques to make a robust and reliable classification of the nodes. To increase the detection accuracy, the scheme also introduces some additional fields in the headers of the AODV packets. The rest of the report is organized as follows. 1 Section 2 presents some existing related work in the literature. Section 3 gives a brief background of the AODV protocol and a finite state machine model of a node. Section 4 discusses the proposed scheme. Section 5 presents simulations results. Section 6 identifies some future work and concludes the report 2 2. RELATED WORK Although significant amount of work has been done on routing in wireless networks, very little work has been done for WMNs. Most of the routing protocols for MANETs such as AODV and DSR use hop-count as the routing metric. However, this is not well-suited for WMNs. The basic idea in minimizing the hop count is that it reduces delay and maximizes the throughput. But the assumption here is that the links in the path are either perfect or do not work at all, and all links are of equal bandwidth. A routing scheme that uses the hop-count metric does not take link quality into consideration. A minimum hop-count path has, on the average, longer links between the nodes present in the path compared to a higher hop-count path. This reduces the signal strength received by the nodes in that path and thereby increases the loss ratio at each link [2]. Hence, it is always possible that a two-hop path with a good link quality provides higher throughput than a one-hop path with a poor link quality. Moreover, wireless links usually have asymmetric loss rate [3]. Hence, new routing metrics based on link quality are proposed such expected transmission count (ETX),per-hop round-trip time (RTT), and per-hop packet pair. Different approaches have been suggested by researchers for designing routing protocols for WMNs. In [4],a QoS routing over OLSR protocol has been proposed that takes into account metrics such as bandwidth and delay where the source node proactively changes a flow’s next hop in response to the change in available bandwidth on its path. In [5],the authors have proposed a link quality source routing (LQSR) protocol. It is based on DSR and uses ETX as the routing metric. A new routing protocol called multi-radio link quality source routing (MR-LQSR) is proposed in [6]. The process of neighbour node discovery and propagation of link metric are same as those in DSR. However, assignment of link weight and computation of the path weight is different. A QoS enabling routing algorithm for mesh based wireless LAN architecture has been proposed in [7] where the wireless users form an ad hoc peer-to peer network. The authors also have proposed a protocol for MANET called ad hoc QoS on-demand routing (AQOR) [8]. In [9], the authors have shown that if a weighted cumulative expected transmission time [6] is used in a link state routing protocol, it does not satisfy the isotonicity property of the routing protocol and leads to formation of routing loops. To avoid routing loops, an algorithm is proposed that uses metric of 3 interference and channel switching (MIC) as the routing metric. The Mesh Cluster architecture [10 ] addresses important issues in WMNs such as auto configuration of mesh and client nodes, routing and load balancing in the infrastructure. The routing is performed via AODV-ST, a protocol that proactively maintains spanning trees rooted at the gateways. The mobility of the clients is managed by DHCP protocol. In contrast to the above approaches, the proposed protocol performs an on-demand route discovery using multiple metrics like bandwidth, delay, and reliability of the links and provides a routing framework that can support high network throughput with a minimum control overhead. 4 3. WMN ROUTING CHALLENGES This section first presents the generic architecture of a WMN and then discusses some specific challenges in designing routing algorithms for such networks. Figure 3.1. The Architecture of a WMN The architecture of a hierarchical WMN consists of three layers as shown in Figure 3.1. At the top layers are the Internet gateways (IGWs) that are connected to the wired Internet. They form the backbone infrastructure for providing Internet connectivity to the elements in the second level. The entities at the second level are called wireless mesh routers (MRs) that eliminate the need for wired infrastructure at every MR and forward their traffic in a multi-hop fashion towards the IGW. At the lowest level are the mesh clients (MCs) which are the wireless devices of the users. Internet connectivity and peer-to-peer communications inside the mesh are two important applications for a WMN. Therefore design of an efficient and low-overhead routing protocol that avoids unreliable routes, and accurately estimate the end-to-end delay of 5 a flow along the path from the source to the destination is a major challenge. In particular, measuring link reliability, estimating the end-to-end delay of a path and reducing control overhead are three important challenges in design of routing protocols for WMNs. These are briefly discussed below. Measuring link reliability: It has been observed that in wireless ad hoc networks nodes receiving broadcast messages introduce communication gray zones [11]. In such zones, data messages cannot be exchanged although the hello messages reach the neighbours. This leads to a disruption in communication among the nodes. Since the routing protocols such as AODV and WMR [7] rely on control packets like RREQ, these protocols are highly unreliable for estimating the quality of wireless links. Due to communication gray zone problem, nodes that are able to send and receive bidirectional RREQ packets sometimes cannot Send/receive data packets at high rate. These fragile links trigger link repairs resulting in high control overhead for routing protocols. Therefore, designing a robust and reliable link quality estimator is crucial for reducing the control overhead. End-to-end delay estimation: An important issue in a routing protocol is end-to-end delay estimation. Current protocols estimate end-to-end delay by measuring the time taken to route RREQ and RREP packets along the given path. However, RREQ and RREP are different from normal data packets and hence they are unlikely to experience the same levels of delay and loss as data packets. It has been observed through simulation that a RREP-based estimator overestimates while a hop-count-based estimator underestimates the actual delay experienced by the data packets [12]. The reason for the significant deviation of a RREP-based estimator from the actual end-to-end delay is interference of signals. The RREQ packets are flooded in the network resulting in a heavy burst of traffic. This heavy traffic causes inter-flow interference in the paths. The unicast data packets do not cause such events. Moreover, as a stream of packets traverse along a route, due to the broadcast nature of wireless links, different packets in the same flow interfere with each other resulting in per-packet delays. Since the control packets do not experience per-packet delay, the estimate based on control packet delay deviate widely from the actual delay experienced by the data packets. Computing a reliable estimate of the end-to-end delay is, therefore, another challenge in design of a routing protocol for WMNs. 6 Reduction of control overhead: Since the effective bandwidth of wireless channels vary continuously, reduction of control overhead is important in order to maximize throughput in the network. Protocols like reactive protocols like AODV and DSR use flooding of RREQ packets for route discovery. This consumes a high proportion of the network bandwidth and reduces the effective throughput. An efficient routing protocol should avoid using flooding as far as possible. 7 4. THE PROPOSED ROUTING PROTOCOL The goal of the proposed routing protocol is to establish a route from the source to the destination that allows traffic flow within a guaranteed end-to-end latency using the minimum control overhead. The salient features of the proposed algorithm are now discussed in the following subsections. 4.1. Estimating reliability of routing paths Every node estimates the reliability of each of its wireless links to its one-hop neighbour nodes. For computing the reliability of a link, the number of control packets that a node receives in a given time window is used as a base parameter. An exponentially weighted moving average (EWMA) method is used to update the link reliability estimate. Every node maintains estimates the reliability of each of its links with its neighbours in a link reliability table. The reliability for an end-to-end routing path is computed by taking the average of the reliability values of all the links on the path. The use of path with the highest reliability reduces the overhead of route repair. The paths with reliability values less than 0.5are never selected for routing. 4.2. Use of multi-point relay nodes The proposed routing protocol uses the multi-point relay (MPR) nodes like the optimized link state routing (OLSR) protocol [13] in order to reduce the control overhead in routing. In order to under the concept of MPR let us consider Figure 4.1. The control messages sent by an IGW, called GW_INFO messages are never flooded throughout the entire WMN; they are transmitted inside the corresponding subnet only if the neighbour which forwarded it has been validated as bi-directional (i.e., the sender is reachable by the receiver via the reverse link). The bi-directionality of a link is determined by appending the list of neighbours in the periodic hello messages. In this way, if a node finds itself in the list of neighbours advertised by its own neighbour, the link is considered bi-directional. This additional list of neighbours in the hello messages is used to compute the MPR of a node. The objective of identifying the MPRs is to minimize control packet overhead. When MPRs are used, 8 it is not necessary to send a message to all the nodes in a network when that message is required to reach all the nodes. If we visualize the WMN as a connected graph, the objective is to find the minimum subset of nodes which covers the whole graph. With a denser network, the benefits of using MPRs are more [1]. The proposed protocol exploits the advantages of MRPs in order to reduce the control overheads of RREQ messages. 4.3. Estimating available network bandwidth In addition to computation of path reliability and use of MPRs, it is also necessary that the effective bandwidth in a routing path is reliably estimated. This is extremely important to support real-time applications since these applications require a guarantee for a minimum available bandwidth. In the proposed protocol the available bandwidth for a wireless link is estimated using its end-to-end delay and loss of packets due to congestion. The packet-loss due to congestion in the link is estimated as follows. In a wireless link packet loss may happen due to two reasons: (i) loss due to faulty wireless links and (ii) loss due to network congestion. The radio link control (RLC) layer segments an IP packet into several RLC frames before transmission and reassembles them into an IP packet at the receiver side. An IP packet loss occurs when any RLC frame belonging to an IP packet fails to be delivered. When this happens, the receiver knows the RLC frames reassembly has failed and the IP packet has been lost due to wireless error. Meanwhile, the sender detects retransmission time out (RTO) of the frame and discards all the RLC frames belonging to the IP packet. This enables the sender to compute packet drop rate in the wireless links. Moreover, using the sequence numbers of the IP packets received at the receiver, it possible to differentiate the packet loss due to link error and packet loss due to congestion [14]. 4.4. Routing through the fixed network In the proposed algorithm, the routing efficiency is further enhanced by occasional routing of packets through the fixed wired network backbone. Since the wired 9 network backbone provides higher available bandwidth with more reliable links, it is advantageously exploited for intra-mesh message communication. Since the IGWs (Figure 4.1) periodically announce their presence in the network through beacon messages, every mesh client knows the hop count from itself to its selected gateway. In the proposed protocol, the RREQ messages include this hop information. When the destination receives the RREQ, since it also knows its distance from its gateway, it checks whether it is better (in terms of number of hops) to route the packet through the wireless nodes (mesh) or through the fixed network. In case the destination node finds that the better route is through the fixed network, the proposed routing algorithm routes the RREP message through the wired network using the default route. Therefore, in such situations, the forward route is established between the source and the destination through the wired network, while the reverse route is set up through the WMN. This approach is known as CIRCULAR routing [1].This approach, improves the performance of bi-directional flows between a source and destination pair (as in a TCP connection) since the nodes in the forward and in the reverse routes are on node-disjoint paths and do not contend for access of the wireless medium. 10 5. SIMULATION RESULTS The proposed protocol has been implemented in the network simulator ns2 version 2.29 [15]. The simulated network consists of 50 and 75 static nodes randomly distributed in the simulation area forming a dense WMN. Four IGWs are placed at locations (100,100), (100, 900), (900, 100) and (900, 900). The simulation parameters are presented in Table 1. The MAC protocol used is IEEE 802.11b CSMA/CA protocol. The performance of the proposed protocol is compared with the protocol presented in [1]. Two important metrics- control overhead and network throughput are studied in the simulation. Table 1. The simulation parameters Pararmeter Values Simulation area 1000 m * 1000 m Propagation channel frequency 2.4 GHz Raw channel bandwidth 2 Mbps Simulation duration 600 s Traffic type CBR UDP Packet size 512 bytes Data rate in the network 32 Kbps IGW hello packet broadcast interval 200 ms No. of source nodes 15, 25, 35 IP queue scheduler Strict priority Propagation model Two ray ground Wired network bandwidth 100 mbps Delay in wired links 1.8 ms 11 5.1. Control Overhead For studying the control overhead, four algorithms are considered. The DYNMOUM algorithm in [16], the DYNMOUM with MPR, in [1] DYNMOUM with MPR and circular routing (CR) [1] and the proposed algorithm compared with respect to their control overhead in routing. The number of data source nodes is varied from 15 to 35 and the control overhead in bytes is studied for 50 nodes and 70 nodes networks respectively. The results are presented in Figure 2 and Figure 4. It may be easily observed that the proposed protocol has the least control overhead among all the four protocols. The reason for the less control overhead in the proposed protocol is due to the fact that there are much less number of route errors and route repairs due the reliable link quality estimation and bandwidth estimation technique used in the protocol, which were absent in the other three protocols. In addition, it exploits the advantages of using MPRs and the circular routing. The MPRs reduce the overhead by controlled flooding and the circular routing reduces the overhead by routing some of the RREPs through the fixed network. The results clearly show that the proposed protocol will be very much suitable in dense mesh networks with high number of data sources. Figure 5.1 Control overhead (bytes) vs. number of data source nodes (50 nodes in the network) 12 Figure 5.2 Control overhead (bytes) vs. number of data source nodes (75 nodes in the network) 5.2. Network throughput The performance of the protocol is also studied with respect to its ability to enhance network throughput. It may be intuitively clear that the reduction in control overhead should lead to a corresponding increase in the network throughput. Figure 4 and Figure 5 represent the data throughput in the network under varying number of source nodes with total number of nodes in the network being 50 and 70 respectively. It may be observed that the proposed protocol produces maximum network throughput among all the four protocol studied. There are various factors that contribute to the enhanced throughput with the proposed protocol. First, the network throughput significantly increases when MPRs are used due to reduced number of collision in the wireless medium resulting in fewer numbers of retransmissions required. Therefore wireless bandwidth is used much more efficiently. Moreover, circular routing improves the performance further due to use of fixed network that has higher effective bandwidth and lower latency. Accurate estimate of link quality also contributes to higher throughput, since packets are always forwarded through the link that has the highest effective bandwidth. Finally, efficient bandwidth estimation ensures that there will be minimum packet retransmission required. 13 Figure 5.3. Network throughput (Bps) vs. number of data source nodes (50 nodes in the network) Figure 5.4. Network throughput (Bps) vs. number of data source nodes (75 nodes in the network) 14 6. CONCLUSION WMNs present a promising technology for providing low cost last mile broadband Internet connectivity through multi-hop communications. Designing an efficient and reliable routing protocol for WMNs is a challenging issue. This report has presented an efficient routing protocol that has very low control overhead and high network throughput when the number of source nodes in a WMN is large. By robust estimation wireless link quality and the available bandwidth in the wireless route and exploiting the benefits of using MPRs and circular routing technique, the protocol is able to sustain a high level of throughput while reducing the control overhead. Simulation results have shown that the proposed protocol is more efficient than some of the current routing protocols for WMNs. 15 REFERENCES [1] F. J. Ros, P.M. Ruiz, “A low overhead architecture for infrastructure-based wireless mesh networks”, in Proc. of Qshine’06, August 2006, Waterloo, Ontario, Canada. [2] D.D. Couto, D. Aguqayo, J. Bricket, R. Morris, “A high-throughput path metric for multi-hop wireless routing”, in Proceedings of ACM MOBICOM, pp. 134-146, 2003. [3] D. Aguayo, J. Bicket, S. Biswas, G. Judd, G., R. Morris, “Link-level measurements from an 802.11b mesh network”, in Proceedings of ACM SIGCOMM, pp. 121-132, 2004. [4] H. Badis, I. Gawedzki, K. Al Agha, “QoS routing in ad hoc networks using QOLSR with no need of explicit reservation”, in Proceedings of IEEE VTC, September 2004. [5] R. Draves, J. Padhya, B. Zill, “Comparison of routing metrics for static multihop wireless networks”, in Proceedings of ACM SIGCOMM, pp. 133-144, 2004. [6] R. Draves, J. Padhye, B. Zill, “Routing in multi-radio, multi-hop wireless mesh networks”, in Proceedings of ACM MOBICOM, pp. 114-128, 2004. [7] Q. Xue, A. Ganz, “QoS routing for mesh-based wireless LANs”, International Journal of Wireless Information Networks, 9(3), pp. 179-190, 2002. [8] Q. Xue, A. Ganz, “Ad hoc QoS on-demand routing (AQOR) in mobile ad hoc networks”, Journal of Parallel and Distributed Computing, 63(2), pp. 154165, 2003. [9] Y. Yang, J. Wang, R. Kravets, Interference-Aware Load Balancing for MultiHop Wireless Networks, Technical Report UIUCDCS-R-2005-2526, Dept. of Comp. Sc., University of Illinois at Urbana-Champaign, 2005. [10] K. Ramachandran, M. Buddhikot, G. Chandranmenon,S. Miller, E. BeldingRoyer, K. Almeroth, “On the design and implementation of infrastructure mesh networks”, in Proc. of WiMesh’05, October 2005. [11] H. Lundgren, E. Nordstrom, C. Tschudin, “The gray zone problem in IEEE 802.11b based ad hoc networks” MC2R, 6(3), pp. 104-105, 2002. 16 [12] V. Kone, S. Das, B.Y. Zhao, H. Zheng, “Quorum: quality of service in wireless mesh networks”, Journal of Mobile Networks and Applications, 12(5), 358-369, 2007. [13] T. Clausen, P. Jacquet, “Optimized link state routing protocol (OLSR), IETF RFC 3626, October 2003. [14] F. Yang, Q. Zhang, W. Zhu, Y-Q. Zhang, “End-to-end TCP-friendly streaming protocol and bit allocation for scalable video over wireless Internet”, IEEE Journal onSelected Areas in Communications, 22(22), pp. 777-790, 2004. [15] NS-2 simulator. URL: http://www.isi.edu/nsnam/ns. [16] F. Ros, Dymoum implementation. [17] URL:http//masimum.dif.um.es/?Software:DYMOUM. 17