’3 ., Jigs ”$3523: 'I_ h 132:“ ll “6. 1:55;???“ .‘ ' z. THESIS a #002 This is to certify that the dissertation entitled A QoS-aware Routing Framework for Mobile Ad Hoc Networks presented by Dmitri D. Perkins has been accepted towards fulfillment of the requirements for Doctoral degree in Computer Science & Engineering five“)- 4 Major prof or Date/7'/X’DZ' MS U is an Affirmative Action/Equal Opportunity Institution 0-12771 LIBRARY Michigan State University PLACE IN RETURN BOX to remove this checkout from your record. To AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE 52‘? 5:5 m 6/01 c:/ClRC/DatoDuo.p65-p. 15 A QOS-AWARE ROUTING FRAMEWORK FOR MOBILE AD HOC NETWORKS By Dmitri D. Perkins A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Computer Science & Engineering 2002 ABSTRACT A QOS-AWARE ROUTING FRAMEWORK FOR MOBILE AD HOC NETWORKS By Dmitri D. Perkins This dissertation is primarily concerned with the design and evaluation of a rout- ing framework for improving Quality-of-Service (QOS) support in mobile ad hoc net- works. A mobile ad hoc network is a system of mobile routers (and associated hosts) connected by wireless links. Such networks may operate autonomously or may be connected to the larger Internet. Moreover, the routers are free to move randomly and organize themselves arbitrarily. To realize the practical benefits of the mobile ad hoc networking architecture, numerous design challenges must be resolved. One such challenge involves supporting the specific performance requirements (known as Quality of Service or QOS) of realtime applications. Due to the dynamic and unpre- dictable nature of ad hoc networks, providing deterministic QOS guarantees does not appear possible. However, probablistic guarantees may be feasible given the location and Signal stability of the nodes used to route packets between a source—destination pair. In this work, we introduce a multipath routing framework for improving network layer QOS. The primary goal of the proposed framework is to reduce the excessive packet loss and delay that are caused by route failures and wireless channel effects. To realize this goal, the framework combines packet-level redundancy and a reliability- based multipath routing and path selection scheme. We refer to this framework as QoS-aware MultiPath Routing with Packet-level Redundancy (QMR/ PR). QMR/ PR consists of two functional components: (a) a Reed-Solomon (RS) Erasure coding mod- ule, and (b) a stability-based routing protocol. We describe the general structure of QMR/ PR and demonstrate its effectiveness via analysis and simulation. In addition to the prOposed QoS-aware routing framework, the contributions of this disseration include a comprehensive set of performance evaluations (via simulation and analysis) of a mobile ad hoc environment. The results from these experiments were instrumen- tal in determining the design choices for QMR/ PR. This dissertation should provide significant guidance to mobile ad hoc network designers and researchers. To Coretta and Paige Elizabeth iv ACKNOWLEDGMENTS I owe much gratitude to several individuals for the successfull completion of this dissertation. I would like to especially thank my advisor, Dr. Herman D. Hughes, for his continuous support and guidance during the course of this research. I would like to thank the members of my guidance committee: Dr. Charles Owen for his technical input, thought-provoking questions, and exhaustive editorial comments; Dr. Vince Melfi for sharing his technical input with regard to probability theory; Dr. Matt Mutka who taught me advanced computer networking and introduced me to the area of mobile ad hoc networking; and Dr. Taieb Znati for sharing his technical expertise with regard to the design of mobile ad hoc networks. I would also like to thank three of my undergraduate professors at Tuskegee University—Professor Roland Jackson, Dr. CL. Chen, and Dr. Jay Bhuyan, who taught me the fundamentals of computer science, continuously challenged me with demanding problems and provided an example of integrity. Finally, I must extend thanks to my beloved wife, Coretta, for her patience, loyalty, and generosity through the many times of hardship and frustration. Achieving this goal with her makes it all the more meaningful. I also extend thanks and appreciation to my parents, RL and Joyce Perkins, for their enduring love. Many thanks to all of my friends at Union Missionary Baptist Church for their encouragement and spiritual training. Now to our God and Father be the glory, forever and ever. Amen! TABLE OF CONTENTS LIST OF TABLES ix LIST OF FIGURES x 1 Introduction 1 1.1 Mobile Ad Hoc Networks: Issues and Challenges .............. 1 1.2 Motivation and General objectives ..................... 6 1.3 Contributions of the Dissertation ...................... 9 2 Background and Literature Review 11 2.1 Introduction .................................. 11 2.2 A QOS Service Model for Ad Hoc Networks ................ 12 2.3 QOS Routing in Mobile Ad Hoc Networks ................. 14 2.3.1 QOS Routing Classes ............................ 14 2.3.2 CEDAR: a Core-Extraction Distributed Ad Hoc Routing Algorithm . . 15 2.3.3 Ticket-based Probing ............................ 18 2.3.4 Bandwidth Routing ............................ 19 2.3.5 Quality of Service over AODV ....................... 20 2.4 QOS Signaling in Mobile Ad Hoc Networks ................. 21 2.4.1 INSIGNIA .................................. 22 2.4.2 The Dynamic QoS Concept: dRSVP ................... 24 2.5 Quality of Service MAC Protocols for MANETs .............. 25 2.5.1 Service Differentiation-based MAC Protocols ............... 26 2.5.2 MACA/PR ................................. 27 2.6 Summary ................................... 29 3 A QoS-aware Routing Framework 31 3.1 Introduction .................................. 31 3.2 Network Model ................................ 32 3.3 Motivation ................................... 33 3.4 General Structure of QMR/ PR Framework ................. 35 3.4.1 Hamework Overview ............................ 35 3.4.2 Packet-level Redundancy .......................... 37 3.4.3 The Routing Protocol ........................... 39 3.5 Analysis of QMR/ PR ............................. 42 3.5.1 Optimizing k, h, and Rfiucc(k) ....................... 44 3.5.2 Evaluating Packet Loss Probability .................... 47 3.5.3 Numerical Results ............................. 47 3.6 Simulation of QMR/ PR ........................... 51 3.6.1 Simulation Environment and Network Model .............. 51 vi 3.6.2 Results and Discussion ........................... 52 3.7 Conclusions .................................. 61 4 Summary and Future Work 63 4.1 Summary and Future Work ......................... 63 4.2 Future Work ................................. 65 4.2.1 Efficient Multipath Route Discovery ................... 65 4.2.2 Packet Loss and Delay Analysis for QoS Support in Ad Hoc Networks 66 4.2.3 QoS-based Medium Access Control .................... 66 APPENDICES 67 A Best Effort Routing in Mobile Ad Hoc Network 68 Al Introduction .................................. 68 A.2 Protocol Overview .............................. 69 A21 Ad-hoc On demand Distance Vector (AODV) .............. 69 A22 Dynamic Source Routing (DSR) ...................... 71 A.2.3 Location-Aided Routing Scheme 1 (LAR—l) ............... 72 A24 Fisheye State Routing (FSR) ....................... 74 A3 Simulation Model and Methodology ..................... 75 A31 Channel and Radio Model ......................... 76 A32 Medium Access Control Protocol ..................... 76 A33 Mobility Model ............................... 77 A34 'Itaffic Load ................................. 78 A35 Metrics ................................... 78 AA Simulation Results .............................. 79 A.4.1 Average Data Throughput ......................... 79 A.4.2 Control Overhead Ratio .......................... 81 A5 Summary and Lessons Learned ....................... 82 B Reliable Transport over Ad Hoc Networks 84 B.1 Introduction .................................. 84 B.2 Related work ................................. 85 B.3 Simulation Model and Methodology ..................... 86 B.4 Performance Metrices ............................. 88 B.5 Simulation Results .............................. 89 B5] The Effects of Path Length on TCP Throughput ............ 89 B52 The Effects of Concurrent TCP Flows on Throughput and Fairness . . 90 8.5.3 The Effect of Traffic Load and TOpology Changes ............ 93 BSA The Impact of Routing on TCP ...................... 94 B.6 Summary ................................... 95 C Factors Affecting the Performance of Ad Hoc Networks 98 Cl Introduction .................................. 98 C2 Methodology ................................. 99 vii C.2.1 Experimental Design ............................ 99 0.2.2 Factors ................................... 100 0.2.3 Performance metrics ............................ 101 0.2.4 Simulation Environment .......................... 102 0.3 Analysis and Simulation Results ....................... 102 C31 The Effects on Control Overhead ..................... 105 C32 The Effects on Average Throughput ................... 106 0.3.3 The Effects on Power Consumption .................... 107 0.3.4 Quantifying the Effects: Allocation of Variation ............. 107 0.4 Summary ................................... 108 D A 2hr Experimental Design 111 viii 1.1 2.1 A.1 3.1 B2 8.3 0.1 C.2 D.1 LIST OF TABLES Heterogeneous 'Il‘affic Behavior and (203 Requirements of Internet Appli- cations ................................... 7 Comparisons of QoS routing algorithms for ad hoc networks ....... 21 Comparisons routing algorithms for ad hoc networks ........... 75 The effect of competing TCP flows ..................... 92 The effect of competing TCP flows ..................... 92 The effect of competing; TCP flows ..................... 92 Factors examined in factorial analsys .................... 101 Percentage of variation explained by each factor .............. 109 A 2hr Experimental Design ......................... 112 LIST OF FIGURES 1.1 A traditional cell-based network ....................... 4 1.2 A mobile ad hoc networking environment .................. 5 3.1 Multiple feasible paths between a source and destination ......... 34 3.2 The QoS-aware Routing Framework ..................... 36 3.3 Multipath Routing based on (N, k)-Reed Solomon Coding ........ 37 3.4 Reed Solomon Erasure Coding Scheme operating over a mobile ad hoc network .................................. 38 3.5 Expected number of delivered packets as a function of N and e ..... 45 3.6 Maximum gain achieved via path and packet-level redundancy ...... 49 3.7 Packet loss probability after reconstruction vs. q .............. 50 3.8 Packet delivery ratio vs. path failure probability and number of paths . . 53 3.9 Packet Delivery Ratio ............................ 54 3.10 Histogram of consecutive packet losses ................... 56 3.11 Bursty packet losses for single and multipath models ........... 57 3.12 Routing overhead ratio ............................ 59 3.13 Initial route setup delay ........................... 60 A.1 Illustration of LAR scheme 1 [33] ...................... 73 A.2 average throughput for ad hoc routing protocols .............. 81 A3 control overhead ratio for ad hoc routing protocols ............ 82 B1 A mobile ad hoc network: string topology ................. 87 3.2 A mobile ad hoc network: grid topology .................. 87 8.3 The effect of path length of TCP ...................... 89 B.4 retransmission versus path length ...................... 90 B.5 TCP throughput versus traffic load and rate of topology change ..... 93 B.6 Average throughput of TCP over AODV .................. 95 B.7 Average throughput of TCP over DSR ................... 96 B.8 Average control overhead of DSR and AODV under TCP ......... 96 0.1 Average control overhead at each design point ............... 104 0.2 Average throughput at each design point .................. 104 0.3 Average power consumption at each design point ............. 105 CA Factorial design: effects on control ovehead ................. 106 C5 Factorial design: effects on average throughput .............. 107 O6 Factorial design: effects on power ...................... 108 Chapter 1 Introduction 1.1 Mobile Ad Hoc Networks: Issues and Chal- lenges This research focuses primarily on the design and evaluation of a QoS-aware multipath routing framework for mobile ad hoc networks. Associated with this framework is a comprehensive set of performance evaluations (via simulation and analysis) of ad hoc networks under various mobility and traffic conditions. AS communication devices be- come more intelligent and detached from wired networks, researchers are envisioning a truly ubiquitous computing environment that will allow users to communicate from anywhere and at anytime. Mobile ad hoc networks [10]—an emerging class of net- work architecture with several unique characteristics, are part of this vision. Ad hoc networks are self-organizing, rapidly deployable, and require no fixed infrastructure [24, 11, 56]. They are comprised of wireless nodes, which can be deployed anywhere, and must cooperate in order to dynamically establish communications using limited 1 network management and administration [17]. Nodes in an ad hoc network may be highly mobile, or stationary, and may vary widely in terms of their capabilities and uses [39, 18]. The primary objectives of this new network architecture are to achieve increased flexibility, mobility and ease of management relative to infrastructured wire— less networks. This is achieved by eliminating the need for fixed base stations (BSS) (as in cellular networks and wireless LANS); thereby, enabling instant infrastructure wherever ad hoc nodes are activated, and eliminating many of the constraints to node mobility that are imposed by a fixed network. Due to their inherent flexibility, ad hoc networks have the potential to serve as a ubiquitous wireless infrastructure, capable of interconnecting thousands of devices [64] and supporting a wide range of networking applications. It is hOped that ad hoc networks will emerge as an effective complement to infrastructured LANs (wired and wireless), and even wide-area mobile networking services, such as Personal Communication Systems (PCS). In a mobile ad hoc network environment, the transmission range of each mo- bile node is limited and variable due to numerous system and environmental factors, including transmission power, receiver sensitivity, noise and other channel effects, namely, path-loss, Shadow fading, Raleigh fading, DOppler Shift, and interference. Node mobility may exacerbate several of these capacity limiting effects. Further- more, signal range may be limited by design in order to increase system throughput by minimizing channel access contention [68], and to increase battery lifetime by min- imizing transmission power. In general, a node’s transmission range is neither fixed, nor symmetric—it demonstrates temporal and spatial variability. Consequently, the wireless links of an ad hoc network are not fixed entities—their status changes over 2 time and is dependent on the relative spatial location of the nodes, transmitter and receiver characteristics, and the Signal propagation properties of the environment. These wireless links not only represent wireless end points, as in infrastructured wire- less networks, they represent the network tOpology itself. Thus, as nodes move freely, the topology of an ad hoc network changes dynamically. A set of five (5) properties have been identified, which are the basis for the many challenges faced by the design and implementation of ad hoc networks [24]: 1. There is no centralized authority for network control, routing or administration. 2. Network devices, including user terminals, routers, and other potential service platforms are free to move rapidly and arbitrarily in time and Space. 3. All communication, user data and control information, are carried over the wireless medium. There are no wired communications links. 4. Resources, including energy, bandwidth, processing capacity and memory, that are relatively abundant in wired environments, are strictly limited and must be preserved. 5. Mobile nodes that are end points for user communications and process user applications must act cooperatively to handle network functions, mostly notably routing, without specialized routers. The challenges stemming from the properties enumerated above affect every aspect of system design and performance—from issues related to physical and MAC-layer de- A wireless channel: each mobile device assigned a distinct channel A base station A mobile/wireless device Figure 1.1: A traditional cell-based network Sign, to network-layer issues including routing, addressing and mobility management, and application layer issues. Unlike infrastructured networks which have fixed and central controllers (see Fig- ure 1.1), ad hoc networks cannot rely on dedicated base stations and routers/ switches to forward traffic across fixed network segments between mobile users. Furthermore, direct communications between all nodes is infeasible due to limited transmission range and node mobility. AS such, store-and-forward packet routing is required over multi-hop wireless paths. The mobile nodes themselves must cooperate in order to dynamically maintain routes and forward traffic on behalf of other nodes (see Fig- ure 1.2). In order to maintain communications subject to router mobility and the subsequent dynamic status of the wireless network links, the routers must imple- ment adaptive algorithms that are responsive to the changes in the network topology, without over-utilization of network resources. . Mobile Node w“) Transmission ‘-' — Flows Figure 1.2: A mobile ad hoc networking environment Traditional routing algorithms tend to exhibit their least desirable behavior under highly dynamic conditions [57]. Routing protocol overhead typically increases dra- matically with increased network dynamics. If the protocol overhead goes unchecked, it can easily overwhelm already limited network resources. Consequently, although they are well adapted to operate in environments where bandwidth is plentiful and the network links are relatively stable, the efficiency of these traditional routing tech- niques conflict with routing requirements in ad hoc networks. Consequently, much of the current research in the area of ad hoc networking has focused on the designed of new routing protocols [27, 54, 30, 57, 23, 51, 33, 49, 70] capable of adapting to frequent topology changes while maintaining low control overhead. These algorithms differ with regard to their various design choices. The following definitions present the most commonly used means of classifying routing protocols that have been designed for ad-hoc networks: Definition 1.1 Proactive Routing is defined as a strategy in which routes are con- tinuously maintained for all reachable network destinations. This approach requires periodic dissemination of routing updates to reflect the up-to-date state of the network. Definition 1.2 Reactive Routing is defined as a strategy in which routes are es- tablished and maintained on a demand basis—only if they are needed for communica- tions. This approach requires procedures to acquire new routes and to maintain routes following topology changes. Definition 1.3 Hybrid Routing is defined as a strategy which selectively applies either proactive or reactive routing techniques based upon either predefined or adaptive criteria. 1.2 Motivation and General objectives The realization of the mobile ad hoc network architecture as a substantial component in a ubiquitous computing environment will require mechanims that support hetero— geneous traffic behavior and service requirements. As Table 1.1 shows, this traffic can range from simple best-effort traffic to delay-sensitive realtime traffic. Support- ing such diverse traffic conditions requires being sensitive to various levels of service quality, typically referred to as Quality-of-Service (QOS) support. Quality of Ser- vice can be defined as a set of service requirements to be met by the network while transporting a packet flow [14]. One of the most challenging problems facing mobile ad hoc networks is the design of efficient and adaptive QoS-based routing strategies. The unique characterisctics Table 1.1: Heterogeneous 'Ii‘affic Behavior and QOS Requirements of Internet Appli- cai'i ns LlApplication Traffic Behavior QoS Requirements E—mail, FTP, Telnet small—large batch files delay and loss tolerant, low bandwidth, best ef- fort web browsing bursty transfers moderate delay and loss, low bandwidth, best effort Voice over IP (VoIP) Constant Bit Rate sensitive to loss, de- (CBR) or bursty lay jitter, predictable bandwidth, requires predictable delay and loss Video on Demand (VoD) Constant or Variable very sensitive to delay Bit Rate and jitter, high band- width, predictable de- lay and loss and challenges of mobile ad hoc networks prevent the direct use of the QOS rout- ing strategies designed for these infrastructured networks. Existing ad hoc routing protocols only provide best effort service and make no guarantees regarding specific performance requirements (i.e., packet loss, delays or available bandwidth). Thus, the design of efficient and scalable QOS routing strategies for ad hoc networks is an open research problem and is the focus of this dissertation. This work is concerned with the design and evaluation of a QoS-based routing framework for mobile ad hoc networks. The pr0posed routing framework combines multipath routing based on stability-based path selection and packet-level redun- dancy. We refer to this routing scheme as QoS-aware Multipath Routing with Packet- level Redundancy (QMR/PR). The general objectives of this research include the following: 0 Introduce the QMR/ PR framework and demonstrate its effectiveness in improv- ing network layer QOS support. 0 Evaluate the performance of QMR/ PR via analysis and simulation. Designing adaptive and efficient QOS routing strategies for mobile ad hoc networks requires a precise understanding of the tradeoffs and effects of various design choices. Moreover, the effectiveness of a. proposed QOS routing architecure will depend upon the interaction of protocols across multiple layers of the OSI model (e.g., routing, scheduling, and medium access control). Since the mobile ad hoc networking archi- tecture remains in its infancy, few studies exist [19, 13, 25, 22] which compare the overall performance of the ad hoc networking under various scenarios. To support the design and development of an effecient and effective QoS-aware routing framework, a secondary and necessary goal of this dissertation is to provide a comprehensive analysis and evaluation of the mobile ad hoc networking architecture. This includes (1) examining the effeciency of existing best-effort routing strategies; (2) investigat- ing the cross-layer interaction and performance dependencies between the transport, MAC, and routing layers; and (3) quantifying the main and joint effect of various factors which influence the overall performance of mobile ad hoc networks. These studies have guided the design choices of QMR/ PR and allowed us to address several key questions which include: 1. Which set of design choices (e.g., reactive vs. proactive routing, source vs. dis- tributed, ect.) are most suitable for supportng QOS in mobile ad hoc networks? 2. How to facilitate cross-layer interaction between the routing layer, MAC, and physical layers? 3. What is a practical strategy for measuring path or route quality? 4. How can this path stability be effectively incorporated into the routing process? 1.3 Contributions of the Dissertation The objectives listed above have been addressed throughout the course of this re- search. Our primary contributions and accomplishments include the following: 0 Designed a QoS-aware multipath routing framework referred to as QoS-aware Multipath Routing with Packet-level Redundancy (QMR/ PR). QMR/ PR is an on—demand source routing scheme which uses multiple paths simulateously to route packets from a source to a destination. A key component of QMPR is the route selection algorithm which is based on a path reliability metric. o Evaluated the performance of QMR/ PR via analysis and simulation. The design choices and tradeoffs made during the definintion of QMR/PR were motivated by a comprehensive set of performance evaluations and analysis [61, 58, 60, 62]. These investigations, which we consider secondary or supporting contributions, provided significant insight into the design of a QOS routing framework. Refer to appendices A through D for deatils. A brief statement summarizing each of the performance studies conducted during this research follows: o Evaluated the performance of various best-effort routing protocols designed for mobile ad hoc networks [58]. Each protocol represented a different set of design choices. The goal was to identify the routing strategies (i.e., appropriate de- sign choices and tradeoffs) most suitable for supporting Q08 in mobile ad hoc networks. a Investigated the effects of node mobility, topology changes, path length, traffic load, and multi-hop routing on the performance of TCP in ad hoc networks [60]. o Studied the cross-layer interaction between medium access control, reliable transport, and routing. In this study, TCP was investigated operating over two different MAC protocols and two different routing strategies [59, 60, 62]. a Used factorial design and analysis to quantify the main effects and two-way interactions of five factors, namely node speed, node pause time, network size, traffic load, and routing strategy on the performance of ad hoc networks. We considered three performance metrics: average throughput, average routing overhead, and power consumption. To our knowledge, this was the first study to actually quantify the effect of these factors on the overall performance of ad hoc networks [61]. 10 Chapter 2 Background and Literature Review 2.1 Introduction The purpose of this chapter is to provide a broad overview of the current research in the area of QOS provisioning for mobile ad hoc networks. This includes ( 1) QoS-based routing protocols [66, 7, 42, 55]; (2) resource reservation schemes [73, 6, 37, 38, 44]; and (3) medium access control (MAC) protocols [40, 67]. Generally, these components work together to achieve specific goals, which are specified by a QOS service model [5, 4, 71]. The remainder of this chapter is organized as follows. In the next section, we present an overview of the first QoS service model proposed for ad hoc networks. Recently proposed QoS routing protocols are presented in Section 2.3. Section 2.4 discusses the current work pertaining to signaling and resource reservation in ad hoc networks. QoS-based medium access control (MAC) protocols are presented in Section 2.5, followed by a summary in Section 2.6. 11 2.2 A QOS Service Model for Ad Hoc Networks Generally, a QOS model does not define specific protocols or implementation. Instead, it defines the methodology and architecture by which certain types of services (e.g., per-flow or class-based) could be provided in the network. Protocols such as routing, resource reservation/signaling, and medium access control must cooperate to achieve to achieve the goals outlined by the QOS model. Two QoS models which have been prOposed for the Internet are Integrated Services (IntServ) and Differentiated Services (DiffServ). IntServ aims to emulate a connection oriented, virtual circuit connection for each flow admitted to the network. This approach requires maintaining specific state information for every flow in every router. The actual state information could include bandwidth requirements, packet delay and loss bounds, or delay variation. The Differentiated Services (DiffServ) [4, 50] architecture is intended to provide scal- able service differentiation in the Internet without the need for maintaining per-flow state information and signaling at every router. As such, Diffserv proposes a service model and algorithms to support QOS for aggregated traffic classes. Under the Diff- Serv model, an application does not explicitly signal the network (i.e., the routers) before transmitting data. Instead, the network tries to deliver a particular kind of service based on the QOS specified by each packet. IntServ and DifiServ were pro- posed for static networks and, thus, cannot be applied directly to the mobile ad hoc environment. A QOS model designed for ad hoc networks must consider the unique features and challenges associated with mobile ad hoc networks; in particular, node mobility (dynamic topology) and time-varying link capacity. 12 The first (203 service model designed specifically for ad hoc networks is Flexible 005' Model for Mobile Ad Hoc Networks (FQMM). It is a hybrid of the Integrated (IntServ) and Differentiated (DiffServ) service models. FQMM consist of three key features: dynamic roles of nodes, hybrid provisioning and adaptive conditioning. Dynamic roles of nodes: FQMM defines three types of nodes. An ingress node is a mobile node that sends data. An interior node is a node that forwards data for other nodes. An egress node is a destination node. Since nodes are free to move resulting in topology changes, a single host may have multiple roles. Hybrid provisioning: Provisioning is used to determine and allocate needed resources at various points in the networks—these points are mobile host in ad hoc networks. The provisioning approach in FQMM consists of a hybrid per-flow (IntServ) and per-class (DiffServ) scheme where traffic of the highest priority is given per-flow treatment while other traffic is given per-class provisioning. Adaptive Conditioning: The adaptive traffic conditioner includes several com- ponents: a traffic profile, meter, marker, and dropper. The traffic conditioner, which polices the traffic according to the traffic profile and is responsible for marking the traffic streams and discarding packets, is placed at the ingress node where the traffic originates. In contrast to an absolute traffic profile, the traffic profile proposed in FQMM is defined as the relative percentage of the effective link capacity. In FQMM, bandwidth allocation is used as the relative service differentiation parameter. FQMM assumes that the larger proportion of traffic does not belong to the highest priority class; thus, preserving the per-flow granularity for a small portion of traffic in the network. Since state information is maintained only for a small portion 13 of traffic, the scalability problem of InServ is expected to improve. 2.3 QOS Routing in Mobile Ad Hoc Networks Before any connections can be made or any resources reserved, a feasible path between a source-destination pair must be established. QOS routing is as a routing mechanism under which paths for flows are determined based on some knowledge of resource availability in the network as well as the QoS requirements of the flows or connections [14]. Research addressing the Q08 routing problem in mobile ad hoc networks has been documented in [66, 7, 42, 55]. These protocols are described in the following sections. Table 2.1 presents a summative comparison of the design choices for each QOS routing protocol presented in this section. 2.3.1 QOS Routing Classes The objectives of QOS routing are threefold: 1) if one exists, find a feasible path between a source-destination pair (i.e., a path that has available resources capable of satisfying the QOS requirements); 2) optimize the use of network throughput and network resources; and 3) adapt to network congestion, providing smooth performance degradation to lower priority traffic. In order to find an Optimal or feasible path between a source and destination, the network must have knowledge (i.e., measurable metrics) about intermediate links. Finding a feasible path between a source and destination depends heavily on how state information is collected and Where the collected information is stored. Thus, QoS-based routing has two primary task: The 14 first task is to collect the state information and keep it up—to—date. The second task is to find a feasible path based on the collected state information. Based on how the state information is maintained and how the search for feasible paths is carried out, traditional routing algorithms have been classified into three categories: (1) source routing, (2) distributed routing, and (3) hierarchical routing [7]. In source routing, each node maintains global state information about the network and selects a feasible path based on the locally stored state information. A link state or distance vector algorithm must update the global network state periodically. In distributed routing (i.e., hop-by-hOp), local state information, kept at each node, is used cooperatively to determine a feasible path. Thus, each router only knows the next hop towards the destination. Hierarchical routing, which was introduced to improve scalability, consist of multiple levels-nodes are clustered into multi—level groups. Source or distributed routing can then be used at each level of the hierarchy. 2.3.2 CEDAR: a Core-Extraction Distributed Ad Hoc Rout- ing Algorithm The Core-Extraction Distributed Ad Hoc Routing Algorithm (CEDAR) [17] has been proposed as a QOS routing algorithm for small to medium Size mobile ad hoc networks consisting of tens to hundreds of nodes. CEDAR includes three key components: core extraction, link state propagation, and route computation. CEDAR proposes the use of core-based mechanisms for two primary reasons. First, due to the bandwidth and power constraints, reducing the number of nodes participating in route maintenance 15 (i.e., state propagation and path restoration) is expected to increase network perfor- mance and increase network scalability. Second, because of the hidden terminal and exposed terminal problems, local broadcast may be highly unreliable in mobile ad hoc networks. Using only a subset of nodes Should reduce the negative effects of local broadcast. Core Extraction: The core of the network is extracted by approximating a minimum dominating set (MDS) of the ad hoc network using only local computation and local state information. The MDS is the minimum subset of nodes such that every node in the network is in the MDS (i.e., is a core node) or is a neighbor of a node in the MDS. Each node in the core then establishes a unicast virtual link with other core nodes a distance of 3 or less away from it in the ad hoc network. Each node that is not in the core chooses a core neighbor as its dominator. The core nodes are responsible for collecting local topology information and per- forming routing on behalf of the nodes in theirrespective domain (or immediate neigh- borhood). Typically, routing protocols in ad hoc networks use a broadcast approach to determine routes by using a flooding-based algorithm. Flooding route request, however, has been shown to be very unreliable due to the hidden and exposed termi- nal problems [66, 69]. To help reduce the effects of these problems, CEDAR uses a unicast mechanism, the core broadcast, in which a core node tunnels the route-request to each of its core neighbors. CEDAR uses the core broadcast mechanism to find a route from the dominator of the source to the dominator of the destination. Link State Propagation: QOS routing in CEDAR is achieved by propagating the bandwidth availability information of stable links in the core subgraph. When a 16 link, (a,b), experiences a significant change (i.e., changes by some threshold value) in available bandwidth, 3 and b must inform their respective dominators. The domina- tors are responsible for propagating state information via slow-moving increase waves and fastcmoving decrease waves (i.e., messages) to all other core nodes via the core broadcast mechanism. The basic philosophy is that the information about stable links with large available bandwidths can be made known to nodes far away in the network, while information about dynamic links or low bandwidth links should remain local. Route Computation: CEDAR is an on—demand source routing algorithm and has three key phases. The first phase consist of locating the destination node and establishing a core path to the destination. The second phase consists of finding a stable route using the core path, established in phase one, as a directional guide. Using only local information about stable link, CEDAR iteratively tries to find a partial route from the source to the domain of the furthest possible intermediate node in the core path, which can satisfy the requested bandwidth. Eventually, either the shortest widest admissible route will be established or a failure is reported. The final phase involves two cooperative mechanisms that dynamically restores or re-computes the QoS-based route upon link failures or topology changes in the network. Upon the failure of a link, CEDAR initially attempts to re-compute an admissible route at the point of failure. As a long—term solution, source-initiated re—computation is used. 17 2.3.3 Ticket-based Probing A distributed (i.e., hop-by-hop) multi-path QOS routing scheme for ad hoc networks called ticket-based probing is proposed in [7]. Imprecise state information can be tolerated and multiple paths are searched simultaneously to find the most feasible path. Similar to CEDAR, ticket-based probing does not use a flooding-based route discovery technique. Instead of randomly selecting the many potential routes to search for an admissible route, ticket-based probing attempts to search only the best possible routes. Ticket-based probing is proposed as a general QOS routing approach for MAN ETs and can handle different QoS constraints (i.e., bandwidth, delay, packet loss and jitter). Ticket-based QoS routing solutions for the bandwidth and delay- constrained routing problems were presented in [7]. In this work, we present only the general ticket-based probing scheme. The basic goal of the ticket-based probing scheme is to utilize tickets to limit the number of paths searched during route discovery. A ticket is the permission to search a Single path. When a sources wishes to discover an admissible route to a destination, it issues a probe (routing message) to the destination. A probe is required to carry at least one ticket, but may consist of more (i.e. connections request with tighter requirements are issued more tickets). At an intermediate node, a probe with more than one ticket is allowed to Split into multiple ones, each searching a different downstream sub—path. Hence, when an intermediate node receives a probe, it decides, based on its available state information, whether the received probe should be split and to which neighbors the probe(s) should be forwarded. 18 In the case of route failures, ticket-based probing utilizes three mechanisms: path re—routing, three-level path redundancy and path repairing. Re-routing requires that the source node be informed of a path failure. After which, the source initiates the ticket-based algorithm to locate another admissible route. The path redundancy scheme establishes multiple routes for the same connection. For the highest level of redundancy, resources are reserved along multiple paths and every packet is routed along each path. In the second level of redundancy, resources are reserved along multiple paths; however, only one is used as the primary path while the others serve as backup. In the third level of redundancy, multiple paths are selected, but resources are only reserved on the primary path. The path-repairing mechanism tries avoid the cost of re—routing by attempting to repair the route at the point of failure. 2.3.4 Bandwidth Routing A novel QOS routing protocol for QoS support in mobile ad hoc networks is proposed [41] and is based on the destination sequenced distance vector (DSDV) routing scheme [57]. The routing protocol provides QOS support via separate end-to—end bandwidth calculation and allocation mechanisms, thus called bandwidth routing. The QOS proposed bandwidth routing scheme depends on the use of a CDMA over TDMA [35] medium access scheme where the wireless channel is time-slotted, the transmission scale is organized as frames (each containing a fixed number of time slots), and a global clock or time synchronization mechanism is utilized. That is, the entire network is synchronized on a frame and slot basis. The path bandwidth between a 19 source and destination is defined can be reduced to the number of free or available time slots between them. Bandwidth calculation requires knowledge of the available bandwidth on each link along the path as well as resolving the scheduling of free slots. This problem is NP—complete and thus, requires a heuristic approach. See [41] for details of the bandwidth calculation and slot assignment algorithms. To support fast rerouting during path failures (e.g., a topological change), the bandwidth routing protocol maintains secondary paths. When the primary path fails, the secondary route is used (i.e., becomes the primary route) and another secondary is discovered. 2.3.5 Quality of Service over AODV The Ad Hoc On-Demand Distance Vector Routing Protocol (AODV) [54] has been proposed for best effort routing in mobile ad hoc networks. When a route to a new destination is needed, the node broadcasts a Route Request (RREQ) packet to find a route to the destination. Each node that participates in the route acquisition process places in its routing table the reverse route to the source node. A Route Reply (RREP) packet, which contains the number of hops required to reach the destination node, D, and the most recently seen sequence number for the node D, can be created whenever the RREQ reaches either the destination node, or an intermediate node with an valid route to the destination. To provide QOS support, a minimal set of QOS extensions have been specified for the RREQ and REP messages [55]. Specifically, a mobile host may specify one of two services: A Maximum Delay and Minimum Bandwidth. Before a node can rebroadcast a RREQ or unicast a RREP to the source, 20 CEDAR Ticket-based Bandwidth QOS over Routing Routing AODV QOS Metric Bandwidth (Bandwidth Bandwidth Bandwidth or or delay) + delay link cost State Mainte- Local + all Local Maintains Only local, nance high band- distance in- next hop info width stable formation for link every node QOS State When band- Periodically Periodically On-demand Propagation width changes as a response by some to a RREQ threshold message Routing Class Distributed Distributed Distributed Distributed Route Com- On-demand On—demand On-demand On—demand putation Routing Non-uniform Uniform Uniform Uniform Architecture Maintains No Yes Yes N 0 Multiple Paths Table 2.1: Comparisons of QOS routing algorithms for ad hoc networks it must be capable of meeting the QoS constraints. Upon detecting that the requested QOS can no longer be maintained, a node must send an Internet control message protocol (ICMP) QOSLOST message back to the source. The specific extensions for the routing table and control packets (e.g., RREQ and RREP messages) are outlined in [55]. 2.4 QOS Signaling in Mobile Ad Hoc Networks QOS signaling (i.e., resource reservation) and QOS routing are closely related. How- 21 ever, these two protocols have distinct responsibilities and may be coupled or de- coupled in QOS architectures. QOS signaling is used to reserve resources (e.g., buffer space, bandwidth, etc.), setup and maintain virtual connections, release resources, and, finally, teardown connections in the network. On the other hand, the QoS rout- ing algorithm must first select a feasible path. The Resource ReSerVation Protocol (RSVP) [6] has been defined as a signaling protocol for the Internet. However, it is not suitable for mobile ad hoc networks because the signaling overhead is too high for mo- bile hosts in ad hoc networks and the per-flow service granularity increases the node processing requirements and limits network scalability. In this section, we present two signaling protocols protocols [37 , 38, 44] designed for mobile ad hoc networks. 2.4.1 IN SIGNIA INSIGN IA [37 , 38], an IP-based QoS framework, is the first signaling protocol for mobile ad hoc networks. Its primary goal is supporting adaptive services, which aim to provide minimum bandwidth assurances to real-time applications. INSIGNIA is constructed based on a philosophy of strict separation of routing, QoS signaling, and packet forwarding. Unlike RSVP, INSIGN IA uses in-band signaling (i.e., incorporat- ing signaling or control data into data packets). Utilizing in—band signaling prevents QOS control packets from having to compete with the data packets for access to the channel and can potentially facilitate rapid restoration of QOS requirements along a new path during topology changes. The INSIGNIA signaling protocol uses per-flow service granularity and is respon- sible for multiple operations: establishing, restoring, adapting, and tearing down 22 real-time connections. The flow restoration and adaptation algorithms are responsi- ble for responding to tOpology changes and changes in available bandwidth, respec- tively. After resources (e.g., bandwidth) are allocated via admission control, which is based on measured channel capacity and requested bandwidth, the resources are then periodically refreshed by a soft-state mechanism through the reception of data packets. Additionally, QOS reporting is used to notify source nodes of the current status of flows. Destination nodes actively monitor ongoing flows, inspecting status information (e.g., packet loss, delay, throughput, etc.) and measuring the delivered QoS (e.g., packet loss, delay, throughput, etc.). INSIGNIA has several protocol commands, which include: (1) the service mode, (2) payload type, and (3) bandwidth request. These commands are encoded in the IP option field, which avoids the need for supporting packet encapsulation. The service mode field specifies the level of assurance requested-reservation (RES) mode or best effort (BE) mode. Using the bandwidth request field , a source can specify its service request (i.e., maximum and minimum bandwidth requirements). The payload field specifies the type of packet, (208 or enhanced QOS, being transported and the bandwidth indicator field reflects the resource availability at intermediate nodes along the path between a source and destination. INSIGNIA is only one component of the Q08 architecture and does not define specific algorithms but assumes the availability of routing, packet scheduling, and medium access control protocols and is transparent to the underlying scheme. INSIGNIA has some significant advantages with respect to the rapid reestablish- ment of QOS reservations along a new path after network topology changes (i.e., node 23 movements). However, since flow state information must be maintained for every flow in each mobile router, IN SIGNIA may face scalability problems similar to RSVP. 2.4.2 The Dynamic (.208 Concept: dRSVP The Dynamic QOS concept is proposed in [44] and is a resource reservation based approach that fits into the Integrated Services model. To provide the flexibility needed in dynamic environments such as MAN ETs, the reservation requests are specified as a range of values (e.g., data rates). The network makes a commitment to provide service at a point in this range. That is, an application may state its QOS requirements by specifying the minimum level of acceptable service and the maximum level of service that it can utilize. The Dynamic QOS concept is based on the Dynamic Resource ReSerVation Pro- tocol (dRSVP) protocol, which extends the basic RSVP protocol to support dynamic Q08 in mobile ad-hoc networks. The following extensions and modifications have been made to the standard RSVP to obtain this new protocol: 1. An additional flow specification (flowspec) in RESV messages, and an additional traffic specification (tspec) in PATH messages, so that they describe ranges of traffic flows. 2. A measurement specification (mspec) is added to allow nodes to learn about downstream resource bottlenecks. 3. A reservation notification message (Restotify) is included in this protocol, which carries a “sender measurement specification” (smspec) that is used to 24 allow nodes to learn about “upstream” resource bottlenecks. 4. The admission control processing is modified to deal with bandwidth ranges. 5. A bandwidth allocation algorithm is added that divides up available bandwidth among admitted flows, taking into account the desired range for each flow as well as any upstream or downstream bottlenecks for each flow. 6. An application API is introduced to handle bandwidth ranges. The dRSVP is a flexible scheme designed to support QoS reservations in mobile ad hoc networks. It uses class-based queuing (e.g., a separate queue for each flow) and the controlled load service (specified in the IntServ model). The dRSVP uses separate control and data packets (out-of-band signaling). The separate control packets will contend for access to the transmission channel with the data packets, reducing the effective bandwidth. 2.5 Quality of Service MAC Protocols for MANETS Typically, random medium access control (MAC) protocols such as MACA [32] focus primarily on solving the well-known hidden terminal problem. The MACA protocol tackles the hidden terminal problem by requiring a sender and receiver to exchange a pair of control packets referred to as a requests-to-send (RTS) and clear-to-send (CTS) packets [69]. While a solution to the hidden-terminal problem is paramount, a QOS- based MAC protocol must also provide a channel access mechanism that considers 25 the Q08 constraints of real-time flows. Since it is typically not possible to provide upper bounds on channel access delay when using random access mechanisms, the goal is simply to reduce the channel access delay of real-time flows. To achieve any level of QOS at the medium access layer, two levels of scheduling are required. We refer to these as packet—level scheduling and node-level scheduling. Regarding packet-level scheduling, every node must define a scheduling or queuing discipline that will determine which packet should be sent during the next transmission time slot. This decision can be determine locally be each node. Node-level scheduling is a distributed problem where all the nodes belonging to a neighborhOod must cooperate to determine which node has channel access priority. For example, if a single node in a particular neighborhood wishes to transmit real-time voice data and all other nodes in the same neighborhood only need to transmit best effort packets, the node wishing to transmit real-time data Should be given access priority. However, the nodes with higher priority should not starve best-effort traffic. In the remainder of this section, we discuss some of the recent work in the area of QoS-based medium access control for ad hoc networks. The proposed schemes can be classified as either class based (e.g., service differentiation) or reservation based schemes. 2.5.1 Service Differentiation-based MAC Protocols Recently, several QoS-based medium access control protocols that have been pro- posed for ad hoc networks. Generally these protocols can be described as class-based schemes, which attempt to provide service differentiation in the ad hoc networking 26 environment. Many of these mechanisms are direct extensions of the distributed medium access control scheme in the IEEE 802.11 standard [15]. The IEEE 802.11 standard specifies the physical and MAC layers of wireless LANS. However, since the protocol is not dependent on the existence of a base station or access point, it is applicable to the ad hoc environment. The MAC protocol is called Distributed Coordination Function (DCF) and is suitable for mobile ad hoc networks. The DCF is a Carrier Sense Multiple Access with Collision Avoidance protocol based on the MACA medium access control protocol described above. The DCF uses the well known exponential backoff algorithm to resolve contention between nodes waiting to access the channel. Additionally, the standard has defined four types of Inter Frame Spaces, which can be used to provide different priorities to short control and data packets. The IEEE 802.11 standard only supports best effort service and makes no provisions for QOS support. Recent work has attempted to provide differentiated service at the MAC layer by manipulating the contention window [2] associated with the backoff algorithm. In [31], the authors proposed a modified backoff algorithm, capable of producing several service classes. The authors demonstrate their approach by using three service classes, each with different channel access priorities. 2.5.2 MACA/PR The Multihop Access Collision Avoidance with Piggyback Reservation (MACA / PR) medium access protocol uses a reservation-based mechanism to establish a QoS-based 27 connection over a single link in an ad hoc network [40]. It is combines a resource reservation protocol and a (.208 routing algorithm to provide end-to-end (i.e., source to destination) QoS capabilities in ad hoc networks. Collectively, these components are referred to as the MACA / PR architecture and are based on CSMA/ CA and TDM (e. g., time-slotted bandwidth reservations). For the remainder of this section, we only discuss the MACA/ PR medium access control protocol. For datagrams (i.e., non-real-time packets), the medium access mechanisms for MACA/ PR are equivalent to MACAW [32, 3] and IEEE 802.11 [15]. MACAW was designed to provide fast recovery from the hidden terminal problem. Thus, for non- real packets, the basic access scheme for MACA/ PR requires a request-to—send/clear— to—send (RTS-CTS) dialogue followed by the transmission of the data packet. The RTS-CTS dialogue helps avoid the hidden terminal problem. Once the data packet is received by the destination, an ACK is sent to the source, providing a timeout mechanism for fast recovery in case of packet collisions. For real-time transmissions, real-time scheduling information is carried (i.e., pig- gybacked) in the headers of data packets and ACK messages. To send the first packet, the source node initiates an RTS-CTS dialogue (but not for subsequent packets). For subsequent packets belonging to the same real-time flow, Reservation Tables (RTS), which are propagated among neighbors, are used to avoid the hidden terminal prob- lem when transmitting real-time packets as opposed to the RTS-CTS dialogue. The first data packet of the multimedia stream then makes the reservation along the se- lected path. The source node piggybacks the real-time scheduling information for the next packet transmission in the header of its current packet. The destination confirms 28 the reservation with an ACK, which contains the scheduling information for the next packet reception. Thus, any node hearing a real-time packet updates its reservation table and defers transmission for the specified time. It is important to note that MACA/ PR relies on two underlying assumptions: 1) that real-time packets arrive at constant time intervals, and 2) that communication links are symmetric (i.e., if node A can hear node B, then node B can hear node A and vice versa). These assumptions may not hold in a mobile ad hoc environment. 2.6 Summary Wireless Mobile Ad hoc networks are self-organizing, rapidly deployable, and require no fixed infrastructure. It is hOped that in the future, ad hoc networks will emerge as an effective complement to infrastructured wired and wireless LANS and even wide- area mobile networking services, such as Personal Communication Systems (PCS). In order to achieve this status, however, applications and services equivalent to those available in these environments must be made available to ad hoc network users. Quality of Service (QOS) support is a difficult but vital component to achieving this status. This chapter has presented a broad view of the current research related to providing QOS support in wireless mobile ad hoc networks. Many network mecha- nisms and protocols must cooperate to provide Q08 in ad hoc networks. For each component (i.e., signaling and resource reservation, QOS routing, and medium access control), we have given a detailed discussion of the prOposed protocols and algorithms. We also described the first attempt to define a QOS model for ad hoc networks. The 29 QoS algorithms for ad hoc networks must be scalable and capable of efficiently uti- lizing scarce network resources subject to expected high rates of topological change. However, because of the limited bandwidth in ad hoc networks, minimizing network and QOS overhead is a key objective. Many of the goals (e.g., flexibility, mobility, adaptive QoS support, and robustness) needed for the successful deployment of ad hoc networks are competing and conflicting. Thus, it appears that the best solution for providing QOS support in ad hoc network will be one that makes the best com- promise (e.g., appropriately balances protocol adaptivity and control overhead). This is the challenge for network researchers and designers. Furthermore, given that the timescales over which new routes are computed is much faster than those of tradi- tional wired or infrastructerd networks, decoupling routing and resource reservation may lead to severe performance degradation. Thus, the strict separation of various QOS components (i.e., routing and resource reservation) may not be apprOpriate for MANETS. A more suitable approach may be the integration of QoS routing and re- source management. Due to bandwidth and energy or power constraints, we believe that designing simple and lightweight (low overhead) protocols should be a primary consideration instead of designing a powerful but complex QOS system that consumes a large proportion Of bandwidth and battery power. 30 Chapter 3 A QOS-aware Routing Framework 3.1 Introduction In this chapter, we present our prOposed QoS-aware multipath routing framework designed for mobile ad hoc networks. First we define the network model considered in this research, outline our assumptions and motivate our design choices. In Section 3.4, we illustrate the general structure of the proposed framework and discuss the operational details, including a description of each of the components which make up the framework. To demonstrate the effectiveness of the proposed framework, an analytical evaluation along with numerical results are presented in Section 3.5 followed by Simulation results in Section 3.6. In Section 3.7, we conclude with a summary and discussion of lessons learned. 31 3.2 Network Model The mobile ad hoc environment is a new networking and communications architecture focused on fast deployment and increased flexibility. There are no centralized control and management mechanisms (i.e., access points, base stations). The network is modeled as a set V of nodes that are interconnected via a set E of wireless links. Nodes can join, move and leave the network at random. As such, the network topology changes over time due to node mobility and wireless channel effects. We assume each node has a unique network address and that all nodes communicate over a single shared channel. We assume that the efl'ective radio transmission range is the same for each node. We also assume the use of a CSMA/ CA medium access control layer that resolves media contention, provides reliable unicast communication, solves the well-known hidden and exposed terminal problems [69], and also provides link failure notifications to the upper layer (i.e., routing). The link failure notification mechanism is used by the routing scheme to initiate the rerouting process. One such protocol which supports these features is the 802.11 medium access control algorithm known as the distributed coordination function (DCF) [15]. DCF defines a basic access mechanism and an optional four-way handshaking technique known as the request-to- send /clear-to—send (RTS/CTS) method. Because a collision in a wireless environment is undetectable by the transmitter, a positive acknowledgment is used to notify that a frame has been successfully received. 32 3.3 Motivation Following the traditional design of QoS routing mechanisms for wired networks, cur- rent research on QoS routing for ad hoc networks has focused on providing a Single feasible path to route data between a source-destination pair. A feasible path is a path that has the necessary resources and is highly likely to satisfy the QOS constraints (e.g., bandwidth and delay bounds). An implicit assumption of this approach is that the network topology is stable (i.e., link failures rarely occur) and thus, excessive packet loss and delay due to link failures and rerouting are not relevant issues. While this strategy may provide acceptable performance in static networks (wired or wire- less), it cannot be expected to perform effectively in a dynamic environment where link failures occur frequently. Realtime connections in an ad hoc environment may fail randomly due to host mobility as well as wireless channel effects such as path- loss, shadow fading, Raleigh fading, Doppler shift, and interference. These inherent characteristics will undoubtedly result in unpredictable delays and excessive packet loss which are key obstacles to supporting realtime (i.e., QOS constrained) applica- tions. Therefore, packet loss and delay caused by link failures and rerouting must be explicitly considered when designing QoS-based routing schemes for ad hoc networks. To addess this problem, we have proposed a QoS-aware routing framework based on packet-level Reed-Solomon Erasure coding [45]. We observed that, typically, mul- tiple paths exist between a source-destination pair in an ad hoc network (see Figure 3.1). Our proposed routing framework attempts to improve QOS by utilizing these paths in such way as maximize the probability of delivering a block of data packets 33 Figure 3.1: Multiple feasible paths between a source and destination from a source to a destination. The multiple routes are selected based on path sta- bility. The use of stability-based multipath routing with packet-level redundancy in mobile ad hoc networks can be justified as follows: 1. Multipath routing has been shown to have several potential advantages [52, 36]: (a) provides load balancing; (b) reduces end-to—end delay; and (c) improves the packet delivery ratio. 2. LOSS sensitive packets have Specific QOS requirements and will require pre- dictable delay and loss rates which may not be met by implementing shortest path routing only. Stability-based path selection can provide approximations of link and path availability [46, 47] and thus will facilitate the prediction of packet loss as well as delay. 3. During the time interval between which a link fails and the source is notified, packets will continue to be transmitted, resulting in consecutive (i.e., bursty) 34 packet losses. It has been Shown that while applications can adapt to ran- dom packet loss, bursty losses will cause significant QOS degradation. AS such, bursty packet loss must be reduced in order to support both video and voice applications. As will be demonstrated, using multiple paths simultaneously and distibuting packets among the multiple paths can reduce bursty packet losses. 4. A limited amount of packet-level redundancy will also increase the packet de- livery ratio and improve the network layer reliability. 5. Using multiple paths can also reduce and sometimes avoid the rerouting delay after link failures. The proposed QoS-aware routing framework will be evaluated using analysis and simulation. 3.4 General Structure of QMR/ PR Framework 3.4.1 Framework Overview To improve packet loss and delay performance of real-time flows in ad hoc networks, we propose a new routing framework which we refer to as QoS-aware Multipath Rout- ing with Packet-level redundancy (QMR/PR). The framework consists of two func- tional components: (1) a Reed-Solomon (RSE) Erasure coding mechanism, and (2) a stability-based multipath routing and path selection scheme. The framework is based on the underlying idea of employing redundancy (i.e., multiple paths and packet-level redundancy) in order to make an unreliable network appear reliable. The overall 35 I """""""""""""""""""""""""" 1' 5 Link Availability , : l Framework Routing E 5 (Mc Donald, Znati) Table : Real-time E 5 Traffic Source : . . . : l Reliability-based 1 Destination : Multipath Routing : : 128504.10 T 5 1: Coding Module : E L Path Quality 5 Feed Back 5 Estimator : Packet Loss Rate I . I l l Figure 3.2: The QoS-aware Routing Framework objective of the prOposed scheme is to improve QOS support by reducing the effects (i.e., packet loss, delay, and delay variation) of path failures due to node mobility. The logical relationship between the QMR/ PR components and other network layer components is depicted in Figure 3.2. The general operation of QMR/ PR proceeds as follows. First, N paths are selected based on network stability. At the sender, the RSE module receives a block of k data packets d1, . . . ,dk from the upper layer and generates h = (N — k) parity packets p1, . ..,p,,. The N = (h + k) packets is referred to as the RSE code block. As illustrated in Figure 3.3, 1: paths are used to route the k data packets while the remaining (N - k) paths are used to transmit parity packets. If at least k (data or parity) of the N packets reach the destination, the RSE decoder module at the receiver can reconstruct any lost data packets. The packet overhead ratio for the 36 pN-k Figure 3.3: Multipath Routing based on (N, k)-Reed Solomon Coding RSE(N, k) scheme is given by: r = —. (3.1) In multipath routing, two key issues typically arise: (1) how to select multiple paths; and (2) how to allocate packets to each of the paths. The first issue deals with determining the path selection criteria (i.e., shortest path, minimum delay, maximally disjoint, reliability, etc.). The second issue is concerned with how to effectively dis- tribute the packets among the multiple paths. The remainder of this section addresses these issues and provides a description of each component of the prOposed framework. 3.4.2 Packet-level Redundancy To better utilize bandwidth, Foward Error Correction (FEC) mechanisms are often preferable to simple packet replication. FEC schemes are capable of detecting and correcting any character or code block that contains fewer than a predetermined number of errors. Such schemes work by transmitting original data packets along 37 Original packet RSE Code Block, stream size=N=k+h PM r—A—x grew-mm [Elli Packetlosswilloccur Traffic Sink Figure 3.4: Reed Solomon Erasure Coding Scheme Operating over a mobile ad hoc network with parity packets, which can be used to reconstruct loss data packets. With regard to quality Of service in wireless networks, FEC schemes can improve the reliability of wireless channels by reducing effective packet loss rates, thereby improving the perceived quality of realtime connections [9, 16, 34]. The routing framework proposed in this work is based on an FEC-based mech- anism called (N, k)-Reed-Solomon Erasure (RSE) coding which implements packet- level redundancy [45, 63]. The RSE(N, k) scheme works as follows. An RSE(N, k) encoder takes k data packets d,,i = 1...,k and generates h = (N — k) parity packets p,,i = 1...,h. The N = (h + k) packets d1,d2,...,dk,p1,p2,...,ph are referred to as the RSE code block. If at least k out of the N = (h + k) packets d1,d2, . . .,dk,p1,p2, . . . ,ph are received, then all k data packets d1,d2, . . .,dk can be reconstructed. The Operation of this scheme over an ad hoc network is depicted in Figure 3.4. For specific details on the construction of the parity packets see [45]. 38 3.4.3 The Routing Protocol As several adaptive routing protocols have already been designed for ad hoc networks [54, 30, 49, 33, 23, 70, 8, 20, 21, 12, 51], our goal is not to design a completely new routing protocol. Instead, the Objective of the QMR/ PR framework is to improve network-layer reliability in a mobile multihop wireless network by utilizing multi- path routing based on packet-level (N, k)-Reed Solomon Erasure coding and selecting highly stable routes. AS such, the primary function of QMR/ PR is to utilize the N paths in such a way as to maximize the probability of successfully delivering the k data packet d1, . . . , d], from the source to the destination. Based on the results Obtained in Appendices A—D, we adopted a reactive source routing approach based on the Dynamic Source Routing (DSR) protocol [30]. The primary distinctions are summarized as follows: 0 Path selection is based on path stability as Opposed to Shortest path. 0 Intermediate nodes are not allowed to respond to route request (RREQ). This increases the chances of finding multiple (preferably disjoint) routes [36]. 0 Multiple paths are used concurrently to route packets between a source- destination pair. 3.4.3.1 Route discovery algorithm To locate multiple routes, QMR/ PR uses a flooding-based route discovery mechanism Similar to DSR. When a source node S needs a route to a destination node D for which it does not already have a viable route stored in its cache, the routing module 39 initiates the route discovey process by broadcasting a route request (RREQ) packet. Upon receiving a RREQ packet, an intermediate node will append its address and rebroadcast the RREQ according to the following conditions: (1) if the hOp count does not equal zero; and (2) if it has not seen the current RREQ, previously; or (3) else if it has seen the packet before but not from the same neighbor. When the destination node D receives the RREQ packet, it constructs a route reply (RREP) packet (i.e., reverses the source route) which is unicast back to S. It is important to note that our current definition of QMR/ PR assumes symmetric links. TO support asymmetric links the destination node must also discover a route to the source. Upon receiving the RREP packet, node S can begin transmitting data packets. 3.4.3.2 Path Selection Algorithm In ad hoc networks, wireless links can be classified as stationary or transient [7]. Stationary links are those links connecting static or Slow moving nodes. Such links will have a higher probability of providing long periods of uninterrupted connectivity. 'Ifansient links are links connecting fast moving nodes and are expected to exist for only Short time periods. Clearly, selecting stationary (i.e., stable or longer-lasting) links is advantageous for supporting realtime flows since route failures will decrease, thereby increasing the likelihood of satisfying the Q08 constraints. The question is how to determine which links are stationary (reliable) and which links are transient. In [46, 47], the authors provide a theorectical framework which defines link availability as the probability that a link connecting two nodes m and n is available at time to + t, given that the link was active at time to. The link availability 40 is denoted by AW, (t) and is computed based on the relative mobility of node n and node m. As such, the path reliability Of the kth path between two nodes, m and n is given by: Blush) = H A.,,-(to + t) (3.2) (231161: N ow, let us assume a set S of k disjoint paths exist between nodes m and n. Using results from reliability theory [65], we find that the probability that at least one path belonging to S exist between node n and m at time t is given by the following system reliability function Rs (t): R3“) = 1 - H (1 — Rf...(t)) (3.3) (k)eS The QMR/ PR framework selects paths based on the above path reliability metholodology. We assume there exist a protocol such that each node has knowledge of an,,,(t). During the route discovery process, each intermediate node appends its link availability. Because of the flooding nature Of the route request, the destination can expect to receive several route requests. After receiving the first route request, the destination will wait for some Specified duration (it before sending a route reply to the source node, which contains the most stable routes. Note that although we adapt the definition of link availability as defined in [46, 47], any such link availability protocol can be used in QMR/ PR. 41 3.4.3.3 Packet Allocation Strategy A second issue that must be considered is how to distribute packets among the mul- tiple paths. QMR uses a round robin approach such that the first k paths are used to route data packets d1, . . . , dk and parity packets p1 . . . , p}, are transmitted over the remaining (N — k) paths. 3.4.3.4 Route Maintenance Due to topology changes, frequent link failures are are an inherent and performance degrading characteristic of ad hoc networks. QMR/ PR depends on the medium access control (MAC) layer to determine link failures. The IEEE 802.11 MAC protocol, which is used in this work, provides such support. When a node fails to deliver a MAC frame to the next hop node, the MAC protocol will notify the routing layer of this failure to deliver. If the route failure occurs at an intermediate node, a Route Error (RERR) message identifing the broken link is constructed and unicast to the source node. Upon receiving the RERR error message, the source node deletes all route cache entries containing the broken link. When a route failure occurs, QMR/ PR initiates the route discovery process in order to locate another route. The goal here is to maintain at least N available routes. 3.5 Analysis Of QMR/ PR The primary function Of the QMR/ PR framework is to utilize N paths in such a way as to maximize the probability chc of delivering k data packet d1, . . . , dk from the 42 source to the destination. In this section, we formally define Rum and provide an algorithm for approximating k such the the packet loss requirements are satisfied. We also provide an analysis of the packet loss probability for a random packet after reconstruction. Refer to the multihop wireless model shown in Figure 3.3. According to this model N paths are used simultaneously to route packets between a source- destination pair. We only consider two distinct events(i.e., successful packet delivery or packet loss due to path failure), and thus, a path can be in either one of two states. Let us define X,- to be a random variable which represents state of the ith path such that P(Xi = 1) = PI (34) and P(Xi = 0) = Qi (35) The value p,- is referred to as the reliability of the ith path. That is, p,- is the probability that path i successfully delivers a packet to the destination. Conversely, q,- is the probability that path i is not functioning and therefore fails to deliver the packet. To indicate the operational status of the entire multipath routing system, we define a state vector X = (X 1, . . . , X N) such that the state of the system 43(X) is define as follows: 1 if the packet loss requirement is met ¢(X) = (3-5) 0 if the packet loss requirement is violated 43 Since the RSE decoder can reconstruct the original set of data packet as long as at least k packets from the RSE code block reach the destination 1 if 2:;1 Xi Z k ¢(X) = (3-7) 0 if 2:;1 X; < ’9 As such, we can define the end-to—end reliability R,m(k) (i.e., the probability of successfully communicating the original k data blocks between a source-destination pair at time t) of the entire N path system as follows: Rgma) = P{¢(X) = 1}, where x = (x1, . . . ,XN) (3.8) For Simplicity, we assume each path is independent (i.e., disjoint) and that p,- = p for all i = 1,. . . , N, the reliability can be defined as a function of N and p. succ(k) = P{¢(X)=1} z=k i . NI. . RkuccUc) : Z )p¢(1_p)N—1 (39) 3.5.1 Optimizing k, h, and Rfiucc(k) Since ad hoc networks have limited bandwidth and power, selecting arbitrary val- ues for k and h may lead to an ineffective scheme. For example, a stable network 44 +M 30 , +N=10 N=15 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 paint error rate before reconstructim Figure 3.5: Expected number of delivered packets as a function of N and s with a low packet loss rate, will need very little redundancy. Thus, the values for k and h must be adaptive and should be based on the current state (e.g., packet loss probability, path reliability) of the path. In this section, we provide an algorithm for determining the appropriate values of k and h given the number Of paths N and the packet loss probability 5. The goal is to select a value for k such that Rfmcc(k) is maximized. Let us assume that the size N of the RSE code block is set and that the observed packet loss rate of the wireless path is given by e. As Figure 3.5 demonstrates, a suitable value of k depends on N and s. It should be noted that N (1 — 5) Should guide the selection of an appropriate value for k when adding parity packets. If N packets are transmitted over a wireless path, the expected number of losses is Ne. 45 In order to ensure no packet loss after reconstruction, the destination must receive at least I: of the N packets. In this case, the value for k is given by the following inequality: k 3 N(1 — s) (3.10) Now let us consider the case where the application specifies a packet loss rate requirement, 5‘. In this case, the appropriate value for k can be defined as follows: N if N s g N 5* k _<_ (3.11) N(1 — e +e‘) if Ne Ne‘ The above formula states that if the expected packet loss rate, 8 of the channel is less than the loss rate requirement 6" specified by the application, then no redundancy is required (i.e., the block only consists of data packets). Alternatively, if the channel loss rate 8 is higher than that requested by the user 6*, then enough parity packets must be added to satisfy the application constraints. Notice that equation 3.10 is a special case of 3.11 where 5" = O. The RSE block size, N, will affect the performance of the system and must consider the delay requirements of the upper layers. Consider the following. Before the N — k parity packets can be computed, k data packets must be available to the encoder. AS such, the delay of the system increases with N. Consequently, the delay requirements of the application will also influence the appropriate value of k. 46 3.5.2 Evaluating Packet Loss Probability As defined earlier, the P(X, = 0) = q.- for path i. If we assume that q,- = q for all i = 1, . . . , N, then the packet loss probability of a random packet (before any reconstruction) is simply q. Now, consider the following Observation. When parity packets are included, a given packet is only effectively lost if it is lost and (N — k - 1) of the remaining (N — 1) packets are lost [26]. AS such, the packet loss probability can be define as a function of N, k, and p as follows: \ N—k-l N -— 1 . _ - q‘(1 — q)”"‘1 (312) P(N,k,p)=q 1.- 2: 1:0 2 3.5.3 Numerical Results In this section, we provide some numerical results and graphs based on the analy- sis presented in the previous section. We are primarily interested in the maximum gain realized when employing path and packet redundancy. To this end, we define maximum gain as follows: Gmax(k) = Rsucc(k) — P(k) (3.13) P (k) is the probability of successfully transmitting k data packets over a Single chan- nel using no parity. Figure 3.6 shows the maximum gain Gm3(k = 7) as a function of the packet success probabilty p for a Single channel with no packet redundancy. The 47 dotted line represents P(k). Interestingly, for small values of p < 0.3, adding parity does not provide a signficant increase in reliability. Even for N = 14, which corre- sponds to simple packet replication, only about a ten percent increase in reliability can be achieved. Similarly, when p is high (i.e., when packet loss probability is low), adding redundancy results in a negligible gain. When the value of p is between 0.3 and 0.8, using multiple paths and parity packets can be very beneficial, resulting in gains approaching 30-50% even for small values of N. These results are supported by Figure 3.7 which shows the packet loss probability after reconstruction P(N, k, p) as a function of q, the packet loss probability em before reconstruction. Based on the results presented here, it is clear that the amount of redundancy should be adaptive and based on the current state of the network. Although, the analytical results are encouraging and support the use of multipath routing based on packet-level redundancy, we must also consider the overhead required to discover and maintain the multiple routes. In the next section, we explore via simulation the control overhead issues and other performance measures associated with the QMR/PR framework. 48 +N=8 p (k) , 0.9 - \/ Maximum Gain (Gm) 0 0.1 02 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 p- probabiity of success for a single path Figure 3.6: Maximum gain achieved via path and packet-level redundancy 49 packet loss probability after redundancy I l l 0.7 0.8 0.9 I l l l 0 0.1 02 0.3 0.4 0.5 0.6 q-packet 10m plobability (no redundancy) Figure 3.7: Packet loss probability after reconstruction vs. q 50 3.6 Simulation of QMR/ PR 3.6.1 Simulation Environment and Network Model In this section, we use simulation to evaluate the performance of QMR/PR. Since QMR/PR is derived from DSR we compared the performance of QMR/ PR with that of DSR for several of the studies. The simulation study was conducted using the library-based Global Mobile System Simulator (GloMoSim) [72, 43] and the discrete- event simulation capability provided by Parsec [48], a C-based parallel simulation language. Our network model included 50 mobile nodes roaming in a 1500m x 300m area. The random waypoint mobility model [43] is used in our evaluations. AS such, each node remained stationary for a specified pause time and then randomly selected a destination from the physical terrain and moved to the new destination with an average speed of 10m/s. To examine the impact of the rate of topology changes on performance, we vary the rate at which the topology changes by studying the mobility model under six different MOBILITY-WP-PAUSE time periods: 0, 25, 50, 100, 400, and 800 seconds. A pause time of zero seconds corresponds to constant movement by every node. A pause time of 800 seconds corresponds to a static network with no movement. The free space propagation model was used to determine if a node is reachable. The radio model assumes that each radio has the ability to capture a sufficiently strong signal (i.e., lock on to a strong signal despite the presence of interference). The IEEE 802.11 MAC protocol with Distributed Coordination Function (DCF) [15] was used as the MAC layer. Constant Bit Rate (CBR) traffic generators were used as 51 the traffic sources. There were twenty source nodes transmitting 1500 byte packet at one second intervals. Each simulation run was executed for 150 seconds of Simulation time. 3.6.2 Results and Discussion 3.6.2.1 Packet delivery ratio Figure 3.8 illustrates the packet delivery ratio performance of QMR/ PR as a function of the path failure probability q for several values of N, the number of paths. In this experiment, we are concerned with investigating only the impact of multipath routing on network performance. As such, we ignore the packet overhead and any negative effects generated by the initial route discovery discovery process. Furthermore, for this study k = N (i.e., no parity packet) and all paths are chosen such that they are disjoint. For N = 1 and N = 2, the packet delivery ratio approaches zero almost linearly as the path failure rate approaches one. However, as the number of paths increases, the packet delivery ratio decreases much slower. For N = 8, QMR/PR is able to maintain a packet delivery ratio greater than ninety percent for a path failure probability up to Sixty percent. The results shown in Figure 3.8 were obtained under optimal conditions. We now consider the impact of protocol interactions on the packet delivery performance QMR/ PR. We compare these results with Dynamic Source Routing (DSR). As il- lustrated by Figure 3.9, QMR/PR is able to improve the packet delivery ratio as compared to DSR. The increase, however, is not as large as expected. In fact, for ‘ 52 1.2 +1 path +2 paths 1 ‘ ‘ ‘ “ +4 paths 0 +6 paths tor +8palhs b 0 g o 0.6 '0 ti 5 g 04* 0.2 . 0 I I I I 0 0.2 0.4 0.6 0.8 1 q-paih failure probability Figure 3.8: Packet delivery ratio vs. path failure probability and number of paths 53 Packet Delivery Ratio 0.9 0.85 < 0.8 . 0.75 0.7 1 0.65 - 0.6 J 0.55 ~ 0.5 l l I I l 100 200 300 400 500 600 700 PauseTIme(sec) Figure 3.9: Packet Delivery Ratio 54 a pause time of 800 seconds (i.e., no node mobility), DSR achieves a better packet delivery ratio. The results above are primarily due to path dependence (non-disjoint paths). When a common link fails, several paths will be invalidated. Moreover, packets being routing over the same links must compete with each for channel access, resulting in increased delays and and packet losses at the medium access control (MAC) layer. To realize greater improvements from multipath routing and packet-level redundancy may require a path selection scheme that builds disjoint routes. A second option is to allow the channel to be divided into two sub-channels. One of which would be used for routing data packets and the other for communicating control information. Although, this approach will reduce the effective bandwidth for the data channel, it may provide increased performance by reducing collisions and channel contention. 3.6.2.2 Correlated packet losses We assume that link failure is the primary cause of bursty packet loss. In addition to a link failure, another factor that may contribute to the burst length is the location of the link failure relative to the source node. For example, when a link failure occurs close tO the source, the source can be notified immediately and will suspend packet transmission. On the other hand, if link failure occurs closer to the destination, it will take longer to notify the source, potentially resulting in longer delays. Both factors are considered in our simulation model and experiments. In this section, we investigate the effect that QMR/ PR has on correlated packet losses. Since using multiple paths is the primary contributor to reducing bursty packet loss, we let k = N (i.e., no parity 55 packets) for these experiments. The path failure probaility was q = 0.4 for each path. To model the delay between link failure and source notification, we assume that a link failure may occur at one of two locations: (1) near the source or (2) near the destination. This location probability P; = 0.5. 150 lipaih 1254 DSpaths l5paths 100« >. O C 8 754 O" 9 50. 25. 0] burst length Figure 3.10: Histogram of consecutive packet losses Figure 3. 10 is a histogram illustrating the frequency of burst lengths for one, three and five paths. Additional experiments showed that using greater than five paths does not significantly alter the results. Because Of the round robin packet allocation stategy proposed for QMR/ PR, bursty packet losses are reduced signficantly. Notice that burst lengths of two occur frequently (e.g., approximately eighty occurrences) 56 [J2]: failure E Consecutive packet [3 losses will occur. ( a) Link failure packet losses } distributed over a entire flow CE. 0 Figure 3.11: The effect of multipath routing on bursty packet loss: (a) consecutive losses in a single path model (b) multipath model with N paths using per packet path allocation for a single path. By utilizing three paths, the frequency of burst of length two are reduced to approximately twenty occurrences. AS can be seen by Figure 3.10, similar trends occur for other burst lengths. The effects of using multiple paths and round robin packet allocation are highlighted in figure Figure 3.11, which illustrates how multiple paths can be used to reduce the length of bursty packet losses. 57 3.6.2.3 Control Overhead Ratio Figure 3.12 shows the routing overhead ratio. The routing overhead ratio (number of control packets transmitted per data packet delivered) is an internal measure of the efficiency of a routing protocol. Since, the control and data packets use the same channel, excessive control packets may negatively affect the ability of the routing protocol to deliver data packets successfully. The control overhead ratio is a measure of the protocol’s efficiency in using control packets to deliver data packets. Note that only routing overhead packets are considered in this study. Additional overhead will exist at the other layers (e.g., MAC). As can be seen from Figure 3.12, DSR uses less control control overhead. This re- sult was expected and can be attributed to the following design issues. DSR is able to limit flooding and its negative effects (i.e., broadcast storms and collisions) by allow- ing intermediate nodes to respond to RREQ. QMR/ PR does not allow intermediate nodes to respond RREQ in hopes of finding multiple routes. Further investigations Show that the flooding-based route discovery also affects the performance at the MAC layer, resulting in increase timeouts and packet drops. These results indicate potential scalability issues with the flooding-based route discovery process. 3.6.2.4 Initial route setup delay Figure 3.13 shows the initial route setup delay. This is the time between receiving the initial connection request from the transport layer and receiving the first RREP packet from the destination node. The results in Figure 3.13 confirm the conclusions 58 control overhead ratio 3.50 3.00 250: 200: 1.50 ~ 1.00 . 0.50 I 0.00 +Dsn +QMR I 100 I I I I I 200 300 400 500 600 Pause time (sec) Figure 3.12: Routing overhead ratio 59 I 700 800 Initial route setup delay (sec W 4? I T I I I I 100 200 300 400 500 600 700 Pause time (sec) Figure 3.13: Initial route setup delay 60 from Figure 3.12. Relative to DSR, QMR/PR experiences significant route setup delay. Again, this is primarily due to the flooding-based route discovery process, which creates increased contention at the MAC layer. Such contention results in huge delays and timeouts. 3.7 Conclusions In this chapter, we have presented a routing framework called QoS-aware Multipath Routing with Packet-level Redundancy (QMR/ PR). The overall objective of QMR/ PR is to take adavantage of the multiple routes which typically exist between nodes in an ad hoc network. As such, QMR attempts to utilize the routes in such a way as to maximize packet delivery ratio. QMR/ PR uses reactive source routing strategy to build multiple routes between a source-destination pair. The framework is based on an (N, k) Reed-Solomon Erasure coding scheme such that N paths are used to route packets. k paths are used to route data packets and N — k are used to route parity packets. The analytical results suggest that QMR/PR provides a significant increase in network-layer reliability. This holds true even for a minimal degree of redundancy. Moreover, the simulation results illustrated that QMR/ PR does provide an increase in the packet deliver ratio. However, the performance increases are not as significant as illustrated via the analytical evaluations. This can be contributed to three key factors: (1) unlike in the simulation model, path are assumed independent in our analytical evaluations; (2) routing discovery overhead signficantly limits the realizable gain of 61 QMR/PR; and (3) the additional routing overhead of QMR/PR results in increased contention at the MAC layer, degrading end-to—end throughput; Due to these factors, we believe that designing a more efficient route discovery process will signficantly improve the performance of QMR/ PR. Moreover, higher priority should be given to disjoint routes. 62 Chapter 4 Summary and Future Work 4.1 Summary and Future Work Environments in which ad hoc networks are initially expected to play an important role include instant infrastructure and wireless LAN (WLAN) applications, particu- larly where mobile access to a wired network is either ineffective or impossible. How- ever, due to their inherent flexibility, ad hoc networks have the potential to serve as a ubiquitous wireless infrastructure capable of interconnecting thousands of devices [64]. In order to achieve this status, however, applications and services equivalent to those available in these environments must be made available to ad hoc network users. This includes both realtime (e.g., audio and video) and non-realtime applica- tions (e.g., FTP, email, etc). Because the ad hoc networking environment is relatively new, much work remains to be done. In the appendices of this dissertation, we provide comprehensive evaluations of the ad hoc networking architecture via detailed Simulations and analysis. With the 63 goal of identifying appropriate routing strategies (i.e., appropriate design choices and tradeoffs) for supporting Q08 in mobile ad hoc networks, we evaluated the perfor- mance of four best-effort routing protocols designed for mobile ad hoc networks [58]. The effects of node mobility, topology changes, path length, traffic load, and multi- hop routing on the performance of TCP in ad hoc networks [60] were investigated. We also studied cross-layer interactions between the medium access control, transport, and routing layers [59, 60, 62]. Furthermore, the main effects and two-way interac- tions of five factors, namely node speed, node pause time, network size, traffic load, and routing strategy were quantified using a 2" factorial design and analysis. Based on these comprehensive performance evaluations, we designed a QoS-aware multipath routing framework referred to as QoS- aware Multipath Routing with Packet- level Redundancy (QMPR/ PR) which is introduced in this dissertation. The frame- work is based on (N, k)-Reed Solomon Erasure (RSE) coding scheme and is designed to improve the network-layer reliability in ad hoc networks. This is achieved by first selecting the N most reliable routes. The routing and RSE modules work coop- eratively to utilized the N paths in such a way as to maximize the probability of successfully communicating k data packets to the destination. We outlined the general structure of QMR/ PR and evaluated its performance via analysis and detailed simulation. Analytical results Show that employing path and packet-level redundancy can provide signficant gains relative to the packet delivery ratio. Preliminary investigations via Simulation Show that the QMR/ PR can increase packet delivery ratio and reduce end-to—end delay. However, it is observed that these performance gains are significantly limited by control overhead produced during the 64 route discovery process. The increased number of control packets has several negative effects: (a) increased channel contention at the MAC layer, (b) increased initial route setup delay; (3) increased timeouts and retransmissions at the MAC layer. Despite these drawbacks, we believe that QMR/ PR is a sustainable framework capable of support QOS provisioning in mobile ad hoc networks. In particular, with the design of a more efficient route discovery process, we expect the performance QMR/ PR to realize more substantial performance gains. 4.2 Future Work 4.2.1 Efficient Multipath Route Discovery The route discovery process used in this study was based on a flooding scheme that only limits packet rebroadcast when a hop count has been exceeded. To improve overall network performance and to fully realize the benefits Of multiplath route and packet-level redundancy will require a more efficient route discovery process. Our objective is to develop an adaptive and intelligent route discovery process that that will search only paths based on some specific criteria such as location information and received signal strength. The idea is to restrict the search process to certain nodes based. Our current work concerning this issue focuses on cross-layer interaction between the routing and medium access control schemes. 65 4.2.2 Packet Loss and Delay Analysis for QOS Support in Ad Hoc Networks The analysis conducted in this work was based on a simplified model of the network layer and does consider the interaction other layers such as medium access control or transport. The objective of our future work will be to develop a detailed analytical model which encompasses the interaction of MAC and network layer as well as traffic load. 4.2.3 QoS-based Medium Access Control As observed in Appendix B, the MAC layer will influence the packet delay and loss performance at each node along a route. Scheduling strategies are needed that give precedence to real-time and control traffic while remaining fair to best effort traffic. We will approach this problem by addressing following the issues: 1. Evaluating existing MAC protocols designed for wireless environments with regard to packet-loss, delay, and throughput performance. 2. Enhancement Of existing MAC protocols by providing some scheduling and/ or resource management strategy that includes quality Of service requirements. Initially, we will approach this problem by attempting to provide probablistic delay bounds to real-time traflic by modifying the backoff counter during chan- nel contention to give real-time packets a higher probability of Obtaining the channel. This is a very difficult task in mobile ad hoc networks and will require signficant work. 66 APPENDICES 67 Appendix A Best Effort Routing in Mobile Ad Hoc Network A.1 Introduction In this study, we investigated the performance of various best effort routing protocols which have been proposed for mobile ad hoc networks. The goal was to identify the design choices (e.g., reactive vs. proactive, source vs. distributed) most suitable for supporting Q08 in mobile ad hoc networks. Maintaining seamless connectivity in an ad hoc networking environment is a very difficult challenge and requires an efficient and robust routing strategy. As such, QOS provisioning in ad hoc networks is directly linked to the performance of the underlying routing protocol. However, due to a wide range of influential factors (e.g., bandwidth and delay requirements, routing overhead, traffic patterns, mobility patterns, topology changes, wireless link characteristics), selecting the most appropriate routing strategy is non-trivial. Each 68 of these factors will affect the routing protocol’s ability to meet QOS requirements. In the following sections, we compare four routing protocols which have been proposed for ad hoc networks: Ad-hoc On demand Distance Vector (AODV) [53, 54], Dynamic Source Routing (DSR) [30, 28], Location-Aided Routing (LAR) [33], and Fisheye State Routing (FSR) [27]. Each protocol represents a different set of design choices and tradeoffs. The next section provides the Operational details of each protocol. The effectiveness and efficiency of each protocol was measured via two performance metrics: (a) network throughput, and (2) the control overhead ratio. We conducted experiments for eighteen different scenarios. A.2 Protocol Overview In this section, we provide an overview of the ad hoc routing protocols that were examined in this study. The underlying concepts and the basic operating procedures of each routing protocol are described. Table A.1 provides an summative comparison of the protocols examined in this research. A.2.1 Ad-hoc On demand Distance Vector (AODV) AODV [53, 54] is a pure reative hop-by-hOp-routing protocol derived from the Destination-Sequenced Distance Vector routing protocol (DSDV). DSDV is based on the classical Bellman-Ford routing mechanism [69]. AODV improves the performance of DSDV by minimizing the number broadcast messages required for the operation of the protocol. This is accomplished by employing on-demand route discovery as 69 opposed to the table-driven proactive sheme used by DSDV. To avoid route looping, AODV uses a destination sequence number for each route entry. The destination sequence number is created by the destination for any route information it sends to requesting nodes. Given the choice between two routes to a destination, a requesting node always selects the one with the greatest sequence number. When a route to a new destination is needed, the source node initiates the Route Discovery routine by broadcasting a Route Request (RREQ) packet to its neighbors. Each participating node of the route acquisition process places in its routing table the reverse route to the source node. A Route Reply (RREP) packet contains the number of hops required to reach the destination node and the most recently seen sequence number for the destination node. A RREP packet can be created and unicast back to the source node whenever the RREQ reaches either the destination node or an intermediate node with an unexpired route to the destination. As the RREP is forwarded along the reversed path, intermediate nodes set forward route entries in their route tables. It is important to note that since the RREP is forwarded along the path established by the RREQ, AODV only supports the use of symmtric links. Route maintenance is conducted as follows. If a source node moves, it will simple initiate the route discovery procedure. If an intermediate node moves, its upstream neighbor will realize the move and a link failure notification message will be pro- pogated to the source. Upon receiving the link notification message, the source may initiate the route discovery procedure. 70 A.2.2 Dynamic Source Routing (DSR) The Dynamic Source Routing (DSR) [30, 28] protocol uses a reactive routing strat- egy based on source routing. Source routing requires that the headers of all data packets carry an ordered list of nodes through which the packet must traverse. Thus, intermediate hops do not need to maintain up—to—date routing information since the header of each data packet contains the sequence of intermediate hops. However, a source node must determine a complete hop sequence to the destination prior to the transmission of a packet. When a route to a new destination is needed, the source node initiates the Route Discovery routine by broadcasting a Route Request (RREQ) packet to its neighbors. The RREQ packet contains the source and destination address and a unique packet identification number. Each node receiving the RREQ packet and does not have a route to destination, appends its own address to the route record of the packet and then rebroadcast the packet. The RREQ is propogated until it reaches the destination or until it reaches an intermediate node with a valid route to the destination. When the RREQ reaches a responding node (i.e., the destination or an intermedi- ate node with a route to the destination) a Route Reply (RREP) is generated. Since DSR uses source routing, the responding node must have a route to the source node in order to return the route reply. If only symmetric links are supported, the responding node can simply reverse the route in the RREQ packet. To support assymtric links, the responding node must initiate its own route request process if there is no valid route to the source stored in the its routing table. As with AODV, route maintenance 71 is accomplished via link failure notification packets. In our simulation studies, both AODV and DSR depend on the MAC layer to determine the operation or failure of a link. A.2.3 Location-Aided Routing Scheme 1 (LAR-1) Location-Aided Routing (LAR) [33] is a reactive protocol and operates similar to DSR. However, LAR utilizes lOcation information in order to reduce routing over- head. In practice, the location of each mobile node can be obtained via the Global Positioning System (GPS). LAR uses two concepts to reduce routing overhead: the expected zone and request zone. The expected zone is an estimate made by the source node, S, which determines a circular region that potentially contains the destination node, D, at a specified time. This implies that node S must have previous infor- mation (location at a previous time and average speed) about node I). Node S does not necessarily belong to the expected zone. If node S cannot determine (does not have previous information) an expected zone for node D, the entire ad hoc network is considered the expected zone. This reduces LAR to a flooding algorithm. Node S must also define a request zone for the RREQ packet. The request zone includes the expected zone and may include other regions around the expected zone. Upon receiving a RREQ packet, a node forwards the RREQ only if it belongs to the request zone. As such, the LAR protocol basically uses flooding to perform route disovery with the primary modification being that a node does not forward a Route Request packet if it does not belong to the request zone. 72 ( A(Xs, Yd+R) W Y”) B(Xd+R, YARD X . O- ---------- Q(Xd+R. Yd) “Xi. Yi) 1(Xi. Yi) O O X 800:, Ys) < C(Xd-i-R, Ys) Rogues Zone K Network Space J \ A(Xd-R, Yd-I-R) P(Xd. vow) B(Xd+R, Yd+R) Expected Zone U(Xd-R. Yd) G(Xd-R, Yd-R) To“: “4" C(Xd-l-R, Yd-R) Request Z0 e Network Space Figure A.1: Illustration of LAR scheme 1 [33] 73 The operation of LAR requires that each node determine whether it belongs to a particular request zone. The LAR protocol uses two schemes to make this deter- mination: LAR Scheme 1 (LAR-1) and LAR Scheme 2 (LAR-2). In this study, we examine only LAR-1. LAR-1 defines the request zone as the smallest rectangle that includes the current location of node S and the expected zone such that the sides of the rectangle are parallel to the X and Y axes. Node 8 determines the four corners of the rectangle in the RREQ packet. When a destination node, D, receives a route request, it builds a route reply message that includes its current location, time, and possibly current or average speed. For an illustration, refer to Figure A.1 [33]. A.2.4 Fisheye State Routing (FSR) FSR [27] is a proactive routing protocol and is based on two methodologies: the fisheye technique and global state routing (GSR). The eye of a fish captures with high detail the pixels near the focal point, but details decrease as the distance from the focal point increases. In terms Of routing, the fisheye approach is parallel to maintaining accurate and highly detail distance and path quality information about the immediate neighborhood of a node. As the distance increases, the amount of detail and accuracy of the information decreases. FSR is also based on the global state routing (GSR) routing scheme, where each node maintains a link state (LS) topology map or table similar to link state (LS) routing. In LS routing, packets are flooded into the network whenever a topology change is detected. However, FSR link state tables are based on information received from neighboring nodes only. That is, 74 AODV DSR LAR-1 FSR routing strat— reactive, dis— reactive, reactive, proactive, egy tributed source source link state path selection shortest path shortest path shortest path, Shortest path metric location supports sym— no yes yes yes metric links uses location no no yes no information loop free yes yes yes yes multiple no yes yes no routes possi- ble repuires peri- no no no yes odic updates Table A.1: Comparisons routing algorithms for ad hoc networks the entire LS topology map is periodically exchanged with a node and its neighbors only. Hence, there is no flooding. To compute the shortest paths, each node uses the link state table. A.3 Simulation Model and Methodology This simulation study was conducted using the library-based Global Mobile System Simulator (GloMoSim) [72, 43] and the discrete-event simulation capability provided by Parsec [48], a C-based parallel simulation language. The main objective of this study was to compare the ability of each routing strategy to successfully deliver packets from a source to a destination under various traffic and mobility scenarious. In this simulation study, the ad hoc network was modeled as a set of 50 wireless / mobile nodes roaming in a 1500 x 300m area. Each node had a propagation range of 250 meters. The channel capacity was 2 Mbits/sec. The model was simulated for 800 75 seconds of simulated time. Using a combination of six different pause times and three different traffic loads, each of the aforementioned protocols was evaluated under 18 different scenarios. A.3.1 Channel and Radio Model The free space propagation model was used to determine if a node was reachable. The free space model predicts received signal strength when the transmitter and receiver have a clear, unobstructed line—of-sight path between them. Received power decays at a rate of 1 / d“, where dis T—R separation distance. The radio model assume that each radio had the ability to capture a sufficiently strong signal (i.e., lock on to a strong signal despite the presence of interference). If an arriving packet’s signal strength relative to those of interfering or colliding packets was greater than some predefined threshold value, the arriving packet was received. A.3.2 Medium Access Control Protocol The IEEE 802.11 MAC protocol with Distributed Cooridination Function (DCF) [15] was used as the MAC layer. DCF is the basic access mechanism of the IEEE 802.11 standard and is essentially a Carrier Sense Multiple Access (CSMA) that incorpo- rates Collision Avoidance (CSMA/CA) and a positive acknowledge (ACK) scheme. Receipt of an ACK (from the receiving node) indicates that no collision occurred. If the sending node does not receive an ACK, it will retransmit the fragment until it gets acknowledged or discarded after a specified number of retransmissions. Optionally, a 76 mobile node can utilize the virtual carrier sense mechanism, which utilizes request-to- send (RTS) and clear-to—send (CTS) exchanges for channel reservation. Using virtual carrier sensing reduces the probability of two nodes transmitting simultaneously (col- lisions) because they cannot hear each other (i.e. hidden terminal problem). The RTS/CTS as well as virtual carrier sensing was employed in our experiments. No packet framentation was required. A.3.3 Mobility Model The random waypoint mobility model [43] was used in our evaluations. In the random waypoint model, each node remains stationary for a specified pause time and then randomly selected a destination from the physical terrain. The node then moved in the direction of the destination point at a speed uniformly chosen between a minimum and maximum speed (meters / sec). After reaching the destination, the node remained there for a MOBILITY-WP-PAUSE time period. In this study, each node randomly selected a destination point in the 1500 x 300m roaming area. The node then moves toward that destination point by selecting a speed uniformly distributed between a 1 and 20 meters resulting with an average speed of 10 meters per second. To examine the impact of the rate of topology changes on performance, we varied the rate at which the topology changes by studying the mobility model under six different MOBILITY- WP-PAUSE time periods: 0, 25, 50, 100, 400, and 800 seconds. A pause time of zero seconds corresponds to constant movement by every node. A pause time of 800 seconds corresponds to a static network with no movement. However, links may still 77 break due to wireless channel effects. A.3.4 Traffic Load Since we are only interested in investigating the impact of traffic load, as opposed to traffic types (i.e. tcp transfers, VBR, HTTP), only constant bit rate traffic sources are used. The size of the data payload at each source was 512 bytes. To investigate performance of each routing strategy under various traffic patterns, we vary the traffic loads: 15, 30, and 45 sources. Increasing the number Of sources has the affect of increasing the traffic load. Each source selects a transmission start time less than 200 seconds and then continuously transmits data packets at a rate uniformly distributed between 1 and 4 packets per second for the duration of the simulation. A.3.5 Metrics To access the performance of each routing protocol, we considered two quantitative measures: average data throughput and control overhead ratio. Average throughput provides insight into the effectiveness of the routing protocol. That is, how well does the routing protocol route packets from source to destination? Such metrics are im- portant from an external perspective in the sense that they influence the performance of other protocols or systems and, eventually, the Q08 perceived by the end user. The control overhead ratio (number of control packets transmitted per data packet delivered) can be considered an internal measure of the efficiency of a routing proto- col. Although two routing protocols may have similar performance from the external 78 perspective (end-to—end throughput and delay), they may generate significantly dif- ferent amounts of control overhead. Since, the control packets and data packets use the same channel, excessive control packets may negatively affect the ability of the routing protocol to deliver data packets successfully. The control overhead ratio is a measure of the protocol’s efficiency in using control packets to deliver data packets. Note that only routing overhead packets are considered in this study. Additional overhead will exist at the other layers (e.g., MAC). A.4 Simulation Results The results of this study are highlighted in Figures A.2 and A.3, which show a relative performance comparison of each metric for a traffic load consisting of 45 sources transmitting at a rate of 4 packets per second. Nodes moved at an average speed of 20m/s. A.4.1 Average Data Throughput Figure A.2 highlights the throughput achieved by each protocol. For each proto- col, the average throughput increases as node mobility and the number of topology changes decrease (i.e., pause time increases). However, the protocols become less ef- fective as the node mobility increases. FSR is the most sensitive to topology changes and achieves the lowest throughput at all pause times with the exception of the static network (i.e., pause — time = SOOSeconds). This is primarily because of the proac- tive strategy employed by FSR. During periods of high mobility, the routes stored 79 in the routing table become invalid before they can be used, resulting in the use of stale routes, especially to distant nodes. The proactive strategy of FSR improved significantly in less dynamic environments, as exhibited by the dramatic increase in throughput as node mobility decreases. Alternatively, the AODV, DSR, and LAR-1 protocols consistently achieve higher throughputs with the exception of the static scenario, where FSR outperforms DSR. These protocols use an on—demand (i.e.,reative) routing strategy and, thus, are able to maintain more accurate and up-tO-date routing tables. We did observe some decrease in throughput for on-demand protocols during times of increased mobility. During times of high mobility, the initial route discovered by the RREQ packet may be broken before the RREP is return to the source node. This increases the route discovery delay and the number packet drops at the source node. The performance variations among the reactive routing strategies can be contributed to the design choices and various optimizations, as outlined in section A.2. Among the on-demand schemes, AODV, which uses distributed routing, achieves the lowest throughput during the simulation. However, analysis showed that there was no statistical difference between the DSR and AODV. The highest throughput was achieved when using the LAR protocol. Both DSR and LAR are on-demand (i.e., reactive) routing schemes which use source routing to deliver packets. LAR is an improvement over DSR and attempts limit flooding during the route discovery process by using location information. Using location information, LAR is able to confine the RREQ packets to a specific area. 80 400.00 1 + AODV -|—-osn 200.004 "in LAR-1 -o--an arm T I l t V I l V o 100 200 300 400 500 600 700 800 Pause Time (see) Figure A.2: A relative comparison of average throughput (bps) for each routing pro- tocol as a function of mobility / pause time (sec) for a traffic load of 45 sources. A.4.2 Control Overhead Ratio The control overhead ratio measures the protocol’s efficiency in using control packets to deliver data packets. In this study, we only considered RREQ, RRER, and Route Update messages. As illustrated by Figure A.3, each protocol exhibits a higher control overhead ratio at higher levels of mobility. The number of control packets generated by FSR is constant regardless of the number Of topology changes since a static update interval is used for exchanging routing information. The fact that FSR has a low overhead ratio is somewhat misleading because of the static update interval, since the protocol only delivered a small number of the transmitted data packets. During times of low mobility, the on-demand protocols use control packet efficiently. However, AODV and LAR transmit two-three control packets per data packet delivered for periods of high mobility. DSR was able to achieve a lower ratio due to its aggressive 81 ,A ----- —x—Aoov Figure A.3: A relative comparison of the number Of control packet transmitted per data packet delivered for each routing protocol as a function of mobility / pause time (sec) for a traffic load of 45 sources. route caching. We also Observed that while LAR achieves the highest throughput, it also generated the largest number of control packets. A.5 Summary and Lessons Learned The goal of this work was to identify a routing strategy that was suitable for sup- porting QOS requirements. We found that such a protocol should meet several re- quirements. First, it must deliver a high percentage of data packets while producing minimal overhead. Maintaining low packet overhead in a wireless broadcast network greatly improves channel access efficiency and power consumption, increasing the probability of satisfying QOS requirments. Second, a suitable routing protocol should facilitate efficient and fast route restoration in the event of path failures. The routing 82 protocol should also perform well under a wide range of mobility and traffic scenarios. Proactive protocols are very sensitive to node mobility and route changes. As such, they have very low packet delivery rates in highly dynamic environments. On- demand protocols consistently outperformed their proactive counterpart, primarily due their ability to rapidly adapt to network changes. However, on-demand strate- gies may experience long route discovery delays, causing queue overflow at the sender. erthermore, none of the protocols were able to deliver all packets when nodes were mobile. In addition to packet overflow, several packets were loss after being trans- mitted by the source. This occurs because the source continues to transmit during the time interval between which an intermediate link failure occurs and source noti- fication. All packets sent during this interval have a high probability of being lost or dropped at the MAC layer of intermediate nodes. Excessive packet loss will obstruct any attempt to provide QOS support in ad hoc networks. An on-demand strategy appears to be the most suitable on which to build a QOS framework. While LAR achieved the highest overall throughput, we believe that it is too dependent on location information that may or may not be readily available. There is even a question of whether nodes would be willing to annouce their physical location. The use Of a single shortest path metric as done by DSR and AODV also limits the effectiveness of the protocol in dealing with route failures and does not take advantage the multiple routes that exist between a source—destination pair. In chapter 3, we present a QOS framework based on on-demand source routing and use multiple paths concurrently to reduce rerouting delays, to reduce packet loss, and to reduce bursty packet losses (i.e., the number of consecutive packet losses). 83 Appendix B Reliable Transport over Ad Hoc Networks 3.1 Introduction This study investigated the performance of the 'Itansmission Control Protocol (TCP) Operating in a mobile ad hoc network. Reliable data transfer is key a requirement for any computer network. TCP, which fulfills this requirement, is the most widely used reliable transport protocol in today’s Internet and has demonstrated its viability with respect to Internet connectivity. TCP is used to transport a significant portion of Internet traffic such as e-mail (SMTP), file transfers (FTP), and WWW (HTTP). The use of TCP in mobile ad hoc networks is clearly advantageous. Futhermore, and of particular interest in this dissertation, the connection oriented nature of TCP is very similar to that required by QOS provisioning. As such, we believe that investi- gating the performance Of TCP in ad hoc networks will assist researchers and network 84 designers in implementing adaptive, robust, and efficient QoS-based protocols for ad hoc networks. Therefore, we studied the effects of node mobility, topology changes, and multi- hop routing on the performance of TCP in ad hoc networks. First, we investigated the throughput of TCP as a function of path length, node mobility, and traffic intensity. Next, we examined the fairness of the ad hoc network with regard to the equal sharing of network bandwidth among competing TCP traffic sources. Third, we evaluated the impact of two different on-demand routing strategies (i.e., source vs. distributed) on TCP throughput. The remainder of this appendix is organized as follows. Section B.2 presents, a brief discussion of related work is presented. In section 8.3, the simulation environ- ment and methodology is described. A discussion of the performance metrics is given in Section B.4. In section B.5, the simulation results are presented, followed by the summary and concluding remarks in Section B.6. B.2 Related work TCP has been shown to have poor performance over wireless links. Thus, several studies have focused on improving TCP performance in the wireless mobile envi- ronment [1]. These include end-to—end mechanisms such as TCP-SACK and ELN and link-layer protocols such as AIRMAIL, Indirect-TCP, and TCP-SnOOp. These mechanisms and protocols were designed to work in the context of cellular-based fixed infrastructure networks. These enhancements, however, have not considered 85 the unique characteristics of ad hoc networks, namely wireless multi-hop routing and the lack of a centralized controller (e.g., base stations). Recent work has begun to evaluate the performance of TCP in context Of ad hoc networks. In [22], the authors have examined the performance of TCP over three different medium access control protocols Operating in a multi—hop wireless network. However, mobility, which is ex- pected to have a tremendous impact on network performance [58], was not considered. In [25], a new metric, expected throughput, was introduced and used to compare the achieved throughput. This work also demonstrated how the use of explicit feedback might improve TCP performance in an ad hoc environment. None of the previous work investigated the impact of routing on the performance of TCP nor quantified the effects and interactions of network factors (e.g., mobility and traffic intensity) on TCP throughput. Hence, evaluating the performance of TCP in a mobile ad hoc environment and quantifying the effects of the unique characteristics is an interesting problem and should facilitate the development of mechanisms for improving TCP as well as QOS performance in ad hoc networks. B.3 Simulation Model and Methodology This simulation study was conducted using the library-based Global Mobile System Simulator (GloMoSim) for sequential and parallel simulation of wireless networks. All results are based on the FreeBSD 2.2.2 version of TCP. The IEEE 802.11 with the Distributed Coordination Function [15] was used as the medium access control layer. Unless otherwise noted, Dynamic Source Routing (DSR) [30] was used for each 86 Figure B.1: Ad hoc network consisting of ten wireless nodes forming a string topology Figure B.2: Ad hoc network of nine wireless nodes forming a grid topology. Dotted lines denote nodes that are within transmission range of one another. experiment. The network model consisted of three different network configurations. A string topology (See Figure B.1) and grid topology (See Figure B.2) were used to study the effects of path length and concurrent TCP flows on TCP throughput. Nodes were not mobile in these configurations. The third network configuration consisted of 70 wireless / mobile nodes roaming in a 1500 x 300m area. The radio transmission range of each node was approximately 250 meters and the channel capacity was 2 Mbits/sec. The free space propagation model was used to determine node reachability. The random waypoint mobility model was used to model node movement. In this study, each node randomly selected a destination point in the 1500 x 300m roaming area. To study the effects of mobility, the pause time (0, 20, and 80 secs) and average 87 speed (10 and 20 m/s) of the nodes were varied. FTP was used as the application layer protocol in this study. File transfer is among the most frequently used TCP applications and accounts for much network traffic. Tcplib was used to generate the file transfers sizes. Each sending node selected a start time between 0 and 50 seconds and continued to transmit data until the end of the simulation. The performance of TCP was examined under different traffic loads by varying the number of concurrent TCP flows from 1 to 32. The TCP maximum segment size was 512 bytes, and the maximum window size was 16384 bytes or 32 packets. B.4 Performance Metrices Average data throughput and network fairness were used to measure the TCP per- formance in a mobile ad hoc networking environment. The network should share the available bandwidth equally among competing flows. However, competing TCP connections can have a negative impact on the equal sharing of network bandwidth. We use the following metric [29] to assign a fairness index to a set of competing flows, (1, 2, 3, ..., n) Where 2:,- represents the throughput achieved by flow i. (£2le 51702 f($1,$2,---,$n) = m (B.1) Since throughput is a nonnegative value, the fairness index will always lie between 0 and 1. If all users receive equal throughput, the fairness index is 1. If only k of the n users receive equal throughput and the remaining n - k users receive zero throughput, the fairness index is k / n. 88 Throughput (bps) o T W 1 1W 0 2 4 s 3 1o Path Length (Hops) Figure B.3: The effect of path lenth on the throughput of a single TCP connection B.5 Simulation Results B.5.1 The Effects of Path Length on TCP Throughput Using the string topology in Figure B.1, we measured the throughput of a single TCP connection path length as a function of path length. The results are presented in Figure B.3. Each measurement was averaged over three simulation runs. Notice that the throughput decreases exponentially as the path length increases. The dra- matic decrease is attributed to the increased contention over the wireless channel. For example, as the path length increases, more nodes must contend for channel ac- cess in order to tansmit data packets in the forward direction and to transmit ACK packets in the reverse direction. The increased channel contention results in several ACK timeouts and wasteful packet TCP retransmissions. To avoid or reduce packet collisions at the receiving node, the MAC layer (802.11) transmits a request-tO-send (RTS) and waits for a clear-to-send (CTS) messages from each of its neighbors. Thus, 89 Retransmissions O .I o 2 4 e a 10 Path Lenth (Hope) Figure B.4: The number retransmitted packets (includes both ACKS and data pack- ets) as a function of path length the transmitter cannot send data until it receives a CTS message from its neighbors. If the CTS message is not received by some time, t, the sending station times out and must re—enter the contention phase, resulting in significant delays and packet losses (e.g., due to buffer overflow). Figure B.4 illustrates that as the path length increases, the number retransmissions due to CTS timeouts increases linearly, limiting overall throughput. B.5.2 The Effects of Concurrent TCP Flows on Throughput and Fairness Using the grid and string topologies and three traffic configurations, we also investi- gated the effect Of traffic load on network throughput and fairness. Table 8.1 Shows the throughput of five Single hop TCP connections using the string topology. Notice that connections one and five achieve the highest throughput. This can be attributed 90 to the fact that there is less channel contention at these nodes since each node only has one competing neighbor. The achieved throughput at intermediate nodes is nearly half that of the end nodes; again, because of channel contention between multiple neighbors. The fairness index of configuration 1 is very close to 1.0 and implies that the network is fair to each TCP connection with regard to bandwidth sharing. It is important to note that the fairness index provides no information regarding the efficiency of bandwidth utilization. It simply indicates whether that the each node received an equal share of the bandwidth. For example, better utilization can be achieved by allowing disjoint nodes (i.e., connections 0-1, 4-5, and 8-9 in configu- ration 1) to have complete channel access. This would result in a throughput 30, where C is the bandwidth of a single channel. Table B.2 presents the throughput measurements for a set of eight concurrent single-hop TCP connections similar to configuration 1. However, in configuration 2, all nodes send and receive data pack- ets. The increased contention at receiving nodes and the bias (toward nodes that have successfully captured the channel in the recent past) of the back-off algorithm used by 802.11, resulted in some nodes achieving zero throughput. Table B.3 shows the throughput and fairness index for three concurrent 2—hop TCP connections in the grid topology. The effects of this configuration were similar to those observed in configuration 1. 91 Table B.1: Throughput measurements. String topology, multiple, single-hop TCP Network Configuration 1 TCPConnection Measured Throughput Fairnesslndex 0 - 1 465607 2 - 3 216716 4 - 5 282419 0.9127 6 - 7 274554 8 - 9 472119 connections; nodes will only send or receive Table B.2: Throughput measurements. String topology, multiple, single-hop TCP Network Configuration 2 TCPConnection Measured Throughput Fairnesslndex 0-1 0 680805 0 200292 236937 130463 KIQO'CANJI—t OOKIOVMOON) 191381 8-9 371144 0.5458 connections; nodes send and receive data packets Table B.3: Throughput measurements for grid topology with multiple, 2~hop TCP connections Network Configuration 3 TCPConnection Measured Throughput Fairnesslndex 0 - 3 - 6 124165 1 - 4 - 7 161448 .8288 2 - 5 - 8 341909 92 lPause—tlmeo 180000- [— lPause-timezo 160000- . BPause-timeao .1 A140000 . . 1200001 1 2 N | 40”.”, 8. 16 32 Figure B.5: Average throughput as a function of the number of concurrent TCP connections. Node speed=20m/sec. B.5.3 The Effect of Trafiic Load and Topology Changes Using the third network configuration discussed in Section B.3, we investigated the ef- fects of node movement (rate of topology change) and traffic load on network through- put. Figure B.5 shows average throughput as a function of concurrent flows and pause-time. The average speed of each node is set at 20m/s. Varying the pause-time has the effect of varying the rate of number of tOpology changes during the simula- tion run. The graph shows that as the number of flows (initiated by new sources) increases, the average throughput is less affected by topology changes. In fact, for pause-time of zero (constant node movement), we observe an increase in throughput for up to eight new sources on both graphs. Additional experiments show that this is, in part, due to the routing protocol. Since more nodes are Sharing routing infor- mation, a better picture of the topology is formed, resulting in a lower connection rerouting delay. Moreover, we Observe that the throughput is Significantly higher 93 only when a single connection is used but tends to follow the same pattern otherwise. These results suggest that node speed (rate of topology change) significantly impacts throughput, but may have less negative effects when more nodes are actively sharing routing information. These results have two key implications: 1) the type of routing algorithm used may impact the overall network performance, and 2) the routing pro- tocol may benefit from route caching and eavesdrOpping data packets intended for other nodes. We study this observation further in the next subsection. B.5.4 The Impact of Routing on TCP The results in subsection B.5.3 suggested that the interaction between the routing protocol, traffic load and node mobility may impact the performance of the transport layer protocol. In this section, we investigate the impact of two popular ad hoc routing protocols, Dynamic Source Routing (DSR) and Ad hoc On-Demand Distance Vector Routing (AODV). The average throughput of TCP is slightly greater when source routing (DSR) is used as illustrated by Figures 8.6 and B7. Our investigations show that the higher throughput achieved by DSR is a result aggressive caching of source routes (topology information). Generally, for the scenarios and network parameters used in these experiments, caching resulted in lower re-routing delays (i.e., reduced path disconnection time). However, during some scenarios (e.g., highly dynamic topologies), caching results in the selection of stale routes, resulting in poor performance. A key observation was that DSR consistently generated less control overhead than AODV. Thus, when using AODV, a larger percentage of the already 94 1200!!) 10mm 1 /"‘¥ 4 - E 00000 E g n n n u m +800“ +1600»: +mIows o v v ‘1 r v v v 0 5 1o 15 20 25 30 35 40 wmdupuMm/s) Figure B.6: Average throughput of TCP over AODV as a function of the number of concurrent TCP flows limited bandwidth will be used for transmitting control packets, further reducing the effective bandwidth (see Figure B.8). B.6 Summary In this work, we have conducted a comprehensive evaluation of TCP Operating in a mobile ad hoc network. Specifically, we have evaluated the impact of path length, node mobility, and routing on the throughput performance of TCP. We also exam- ined the fairness of multiple competing TCP flows in a mobile ad hoc network and demonstrated that the fairness of the network or the equal sharing of network band- width is very low among concurrent TCP flows, resulting in several sending stations achieving very little or no throughput. Results showed that the interaction of the MAC layer and TCP has a significant impact on the overall throughput achievable 95 120000 100000i 2 O a cocoo- 5 . A . 0 - - - - O E 40000 < "“m fu An‘ in l,— a +8110ws 20°00 ‘ +160ows +2000ws o T T Y W T I Y o 5 1o 15 20 25 30 35 40 averagenodespeodhnls) Figure B.7: Average throughput Of TCP over DSR as a function of the number of concurrent TCP flows 400 +DSR.Bflows 350‘ +DSR.16flowa —rr- DSR. 20 flows +AODV, 8 flows -a- AODV. 1 6 flows + AODV. 20 flows average control overhead (padrets) 0 5 10 15 20 25 30 35 40 average node speed (tn/s) Figure B.8: Average control overhead generated by DSR and AODV as a function of node speed. Three different sets of flows are used for each routing protocols 96 in ad hoc networks. The results show that concurrent TCP flows have a tremen- dously negative impact on network throughput, resulting from channel contention, collisions, and timeouts (MAC-layer and TCP). To address these issues requires the design of adaptive medium access control mechanisms, buffer management schemes, and distributed scheduling algorithms that are capable of some level of service dif- ferentiation. Additionally, we believe that the node speed and pause time can be combined to provide some type of probabilistic bound on throughput and perhaps end-to—end delay. Such a metric would be helpful in designing QOS mechanisms for ad hoc networks. 97 Appendix C Factors Affecting the Performance Of Ad Hoc Networks C.1 Introduction In our previous work [58, 60, 62], several factors were shown to significantly influence the performance of any protocol operating in an ad hoc network. These factors include network size, traffic load, routing strategy, rate Of topology change, etc. These fac- tors and the inherent characteristics of wireless networks will result in unpredictable network performance and degraded QOS support. While it is important to em know that certain factors do influence network performance, as demonstrated by studies conducted in appendices A and B, it is also crucial that we em quantify this impact. Such knowledge facilitates better design choices and appropriate tradeoffs. Our primary objective in this work was to evaluate and quantify the main and joint effects of various factors that may influence network performance. Specifically, 98 we use a 2" factorial design and analysis [29] to quantify the effects of five factors, namely node Speed, node pause time, network size, traffic load, and routing strategy on the performance of ad hoc networks. We consider three performance metrics: average throughput, average routing overhead, and power consumption. The remainder of this appendix is organized as follows. Section C.2 describes the simulation environment and methodology. A discussion Of the performance metrics and experimental factors is also presented in Section C.2. In Section 0.3, the sim- ulation results and design analysis are presented, followed by a summary in Section C.4. C.2 Methodology C.2.1 Experimental Design Again, the goal of these experiments was to quantify the main effect of various factors and their two-way interactions on the overall performance of an ad hoc network. To achieve this goal, we used a 2"r(k = 5, r = 4) factorial design methodology [29], which allowed us to isolate and quantify the main effect of each factor and to identify the percentage of performance variation due to each factor. The main effect of a factor is the average change in performance due to changing the factor from its “-” level to its “+” level, while holding all other factors fixed. This average is taken over all possible combinations of the other (k —- 1) factors. The two- way interaction ( or joint) effect is the difference between the average performance 99 when two factors are at the same level and the average performance when the factors are at opposite levels. Table D1 provides specific details of our experimental design. We conducted 32 separate experiments referred to as design points. Each experiment was replicated 4 times, resulting in 128 simulation runs. The factorial design model used in this work is based on a linear regression model and thus, makes the assumption that the effects of the factors are additive. Fur- ther, our model assumes that experimental errors are independent and normally dis- tributed. C.2.2 Factors To maintain consistency with factorial design terminology, we will refer to the vari- ables that affect the outcome of an experiment as factors and the actual outcomes as performance responses or metrics. Table 0.1 shows the factors and there values at each level. Each factor is examined at two different levels. The values at each level where carefully chosen to reflect realistic scenarios. For example, the speed of a node is 5 and 40 meters per second which represent walking speed and the speed of a moving vehicle (or military tank), respectively. We investigate to distinct routing strategies (source vs. distributed). Both routing protocols are on—demand protocols and, thus, do not transmit periodic routing messages. These protocols differ with regard to the method by which routes are computed. DSR uses source routing in or- der to deliver packets to any destination in a mobile ad hoc network. Source routing requires that the headers of all data packets carry an ordered list of nodes through 100 Label Factor Level 1(-) Level 2(+) 1 node speed (m/s) 5 40 2 pause-time (sec) 3 30 3 network size 50 80 4 no. of traffic sources 10 25 5 routing strategy source distributed Table 0.1: Factors examined in factorial analsys which the packet must traverse. AODV uses a distributed (e.g., hop-by-hOp) tech- nique to deliver packets and uses sequence numbers (e.g., to avoid routing lOOpS) for each route entry. C.2.3 Performance metrics The following performance metrics were considered in this study: 0 Throughput: throughput measures the effectiveness of the network in delivering data packets. That is, how well does the network deliver packets from the source to the destination? 0 Average routing overhead: the average number of control packets produced per node. Control packets include route requests, replies and error messages. 0 Average power consumption: measures the average power consumption per node. 101 C.2.4 Simulation Environment For this study, we modeled the ad hoc network as a set of nodes roaming in a rect- angular area. The radio transmission range of each node was approximately 250 meters and the channel capacity was 2 Mbits/sec. The free space propagation model was used to determine if a node is reachable. The IEEE 802.11 with DCF was used as the medium access control layer. In this study, we used constant bit rate CBR sources that continuously transmit 1024-byte data packets at a rate of 4 packets per second for the duration of the simulation. The random waypoint mobility model was used to model node mobility. Each node was placed randomly in the Simulated area (1600X400m2). After remaining at the location for a specified pause time, the node randomly selected another destination from the physical terrain. The node then moves to the new location at a speed uniformly chosen between a minimum and maxi- mum speed (meters/sec). Each experiment was executed for 200 seconds Of simulated time. C.3 Analysis and Simulation Results This section presents the main effects and two-way interaction for each factor. For brevity and convenience, each factor is denoted by its label (See Table Cl) and each two-way interaction, say 1 and 3, by (1x3). Before examining the main effects and their two factor interactions, we first observed the average performance results of the three performance metrics. Figures C.1—C.3 show the performance metrics aver- aged over four replications at each design point. By closely examining the following 102 graphs and the experimental design matrix (See Table D.1, we can make three key observations: For control overhead, there are fluctuations at each design point (one “high” fol- lowed by one “lower” value). Examining the experimental design matrix, we observe that this pattern follows the level changes of factor 1, node speed. The fluctuations become more pronounced for higher design points (i.e., 16—32) suggesting a strong interaction between node speed, routing and, potentially, network size. For throughput, the second and fourth blocks of eight design points experience significant fluctuations (one “high” followed by one “low” values), indicating a factor interaction. Looking at the design matrix, we Observe that these fluctuations corre- spond to level changes of multiple factors, namely factors one (node speed), and five (routing protocol), and, possibly, factor three (network size). For power consumption, the design points are consistently grouped in blocks of four. There are minor fluctuations (one “high” followed by one “low” values) within each block, again suggesting that node speed has significant influence on power con- sumption. The consistent groupings of four suggest some interaction among other factors. Figures C.1—C.3 and the above observations are certainly beneficial to under- standing the main effects of each factor as well as their two-way interactions, but such observations are only qualitative. To confirm the results, we must now quantify the effects. Next, we formally substantiate the observations discussed above. Figures C.4——C.6 Show the 90% confidence intervals for the expected main effects and two-way interaction on control overhead, throughput and power consumption, respectively. 103 1400.00 1200.00 : 1000.00 : 800.00 1 600.00 ~ 400.00 J Average Packet Overhead 200.00 < 0.00 A . . V‘- .. a» -..O.....-e-....«e«..-r' 3 ‘0’ O V ‘l f I I .\ ‘. n / 0 5 10 15 20 25 30 Design Points Figure C.1: Average control overhead at each design point 35000.00 . a a‘ e g Q . 0 o 0 . 0 e I g ‘0" e' e" ‘ ° . ..- .' f ' g :1 ' ‘. g 25000.00 - r ' ‘.' I I 0 g 20000.00 * g: 15000.00] 5 10000.00 4 5000.00] Dem I I T T T I 0 5 10 15 20 25 30 DesignPoint Figure C.2: Average throughput at each design point 104 Average Power Consumption O 5 1O 15 20 25 30 35 Design Poim Figure C.3: Average power consumption at each design point For control overhead and throughput, the graphs show that the main effects of fac- tors 1, 3, 4, and 5 are real (significantly different from zero) and thus impact network performance. The results also show that the main effect of factor two (pause—time) does not significantly influence either performance metric. Moreover, the two-way interactions and the main effects of factors 1 and 2 have no ”real” impact on power consumption. Additional observations and discussion are presented for each metric in the following sections. 0.3.1 The Effects on Control Overhead As shown in Figure CA, the effects of factors 1, 4, and 5 result in a significant increase of control data. Interestingly, this result suggests that using distributed routing gives rise to an increase in control overhead. Finally, we see that the amount of control overhead is negatively influenced by several two-way interactions: (1x4), (1x5), and 105 200 150 ‘r I I 0 #I# ##1#I# :_+I%I%}% -100 i .1 é L Effect Labels Effects on Cntrl data (plea/router) 8 23333 1x5 Figure CA: 90% confidence intervals for the expected main effects and two-way in- teraction effects on Control Overhead (packets/ router) (4x5). Thus, the previous observations regarding control overhead are valid. C.3.2 The Effects on Average Throughput The effects of factors 1 and 4 (and their two-way interactions) are significantly neg- ative for throughput. The effect of factor 3, network size, is positive, indicating that larger network size results in improved throughput. Notice, that the type of routing used has a negligible effect on throughput performance. Combining this fact with the results (using distributed routing results in an increase in control overhead) from the subsection C.3.l suggest that distributed routing is less efficient than source routing. Thus, source routing tends to be a “better” design choice if efficiency is the primary concern . 106 3 I—o-r #-o-r r—o—r o r—o-r .4 1 -# J. H4 I o—o—l ‘ 1 I Effect on Throughput 0w) § 1 2 3 4 5 m x3 x4 x5 2x4 21:5 3x4 3x5 4x5 Efled Niels Figure 0.5: 90% confidence intervals for the expected main effects and two-way in- teraction effects on average throughput in kbps C.3.3 The Effects on Power Consumption Power consumption is strongly influenced by two factors. The effect of factor 3, net- work size, is positive, decreasing the average power consumption as the network size is increased. The efl'ect of factor 4, number of sources, is negative, increasing the average power consumption as the number of sources increases Intuitively, this is reasonable since increasing the network size while maintaining a constant traffic load essentially increases the number of routers eligible to forward packets, resulting in a reduced load. On the other hand, increasing the number of traffic sources simply increases the routing load of each mobile host, resulting in increased power consumption. C.3.4 Quantifying the Effects: Allocation of Variation The importance of a factor can be determined by the proportion of variation in the performance metric that is explained by the factor. The proportions of variation 107 0.15 _o 8 0 ~)- L #- Eflect on Power (mWhr) -0.05 v r T *~“*“ve:22333 F F F Effect Labels 3x5 4x5 Figure 0.6: 90% confidence intervals for main effects and two-way interaction effects on power consumption in (mWhr) explained by each factor and the two-way interactions are shown in Table C.2. The last row, labeled EE, is the proportion of variation attributed to experimental error. Notice that main effect of factor 4, the number of sources, is responsible for 69 percent, 20 percent, and 34 percent of the variation in power consumption, control over, and throughput, respectively. Based on these results and analysis, it appears that factor 4 is the most influential factor, followed by node speed and network size. The two-way interaction of node speed and the number of traffic sources (1x4) is also significant. C.4 Summary This research has presented a comprehensive analysis of five factors: node speed, pause-time, network size, number of traffic sources, and type of routing (source versus distributed), that affect the routing performance of ad hoc networks. A factorial 108 Percentage of Variation Explained by Factor Factor Power Consumption Control Overhead Throughput 1 0.071 13.373 30.176 2 0.071 0.489 0.022 3 20.990 2.558 3.994 4 68.885 19.857 34.306 5 2.332 19.966 0.315 1x2 0.018 0.496 0.021 1x3 0.071 0.284 0.569 1x4 0.282 8.801 16.816 1x5 0.110 10.221 0.172 2x3 0.018 0.115 2.043 2x4 0.004 0.196 0.04 2x5 0.004 0.446 0.147 3x4 6.035 2.596 3.500 3x5 0.110 1.934 0.373 4x5 0.357 14.535 0.258 EE 0.642 4.133 7.238 Table C.2: Percentage of variation explained by each factor experimental design was used to isolate and quantify the main effects as well as the two-way interactions of these factors on three performance responses: throughput, average routing overhead, and power consumption. The main results and observations of the analysis are as follows: a For the experimental design used in this study, source routing was more efficient. That is, it achieved approximately the same performance as distributed routing but used less control overhead. 0 As the result show, the main effect of factor 4, number of traffic sources, has the strongest impact on the performance responses followed closely by node speed and network size. 109 0 increasing the network size, while maintaining the traffic load results in in- creased throughput, decreased control overhead and decreased power consump- tion. 0 Increasing traffic load and increasing the number of traffic sources may not result in the same performance results. For example, adding more traffic sources will certainly increase the control overhead, while increasing the transmission rate at a single source does not necessarily result in increased control overhead. It is important to note that, while we were very sensitive to the selection of factor levels, our results and conclusions (e.g., estimates of effects and interactions) are based upon the factor levels used in this design and may vary if different factor levels are used. To reduce the potential variations when different factor levels are used, we executed several simulations and selected the factors most appropriate. That is, we took special care not to select factors levels too far apart to provide any meaningful or useful results. Thus, we believe the results of this study will greatly contribute to the modeling and design of adaptive protocols for ad hoc networks. 110 Appendix D A 21“?" Experimental Design 111 Table D]: A 2hr d w L s t .m 0 P 5m/s 3sec 50 10 Source 40 m/s SOsec 80 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1| All 1 1 ................ a a a u . . q u . . . o c a. a a . . c . . . . . u . . . . . . . a a. q q 11114444444411111111444444441111 . u u o o o a a a o o a n a u o a o o u o a o u u a u a u c o u u o o o o a a o u c o a o n o n ..... 01234567esmnmwuwwnwwmmamma mmwwm 112 Bibliography [1] Hari Balakrishnan, Venkata N. Padmanabhan, Srinivasan Seshan, and Randy H. Katz. A comparison of mechanisms for improving tcp performance over wire- less links. ACM SICCOMM Computer Communication Review, 26(4):256—269, October 1996. [2] M. Barry, A. T. Campbell, and A. Veres. Distributed control algorithms for service differentiation in wireless packet networks. In Proceedings of IEEE IN- FOCOM, Anchorage, Alaska, 2001. [3] V. Bharghavan, A. Demers, S. Shenker, and L. Zhang. Macaw: A media access protocol for wireless lans. In Proceedings of ACM SIGCOMM, pages 212-225, 1994. [4] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W Weiss. An architec- ture for differentiated services. RFC 24 75, December 1998. [5] R. Braden, D. Clark, and S. Shenker. Integrated Services in the Internet Archi- tecture: an Overview. IETF RF01663, June 1994. [6] R. Bradena, L. Zhang, S. Berson, S. Herzog, and S. Jamin. Resource reservation protocol (rsvp)-version 1 functional specification. IETF RFC 2205, September 1997. [7] Shigang Chen and Klara Nahrstedt. Distributed quality-of-service routing in ad- hoc networks. IEEE Journal on Selected Areas in Communication, Special Issue an Ad hoc Networks, 17 (8):1—18, August 1999. [8] T-W Chen and M. Gerla. Global State Routing: A New Routing Scheme for Ad-hoc Wireless Networks. In Proc. ICC, 1998. [9] S. Cho, A. Goulart, I. F. Akyildiz, and N. Jayant. An adaptive fec with qos provisioning for real-time traffic in leo satellite networks. In Proceedings of IEEE [CC 2001, pages 2938—2942, Helsinki, Finland, June 2001. [10] M. S. Corson, J. P. Macker, and G. H. Cirincione. Internet-based mobile ad hoc networking. IEEE Internet Computing, 3(4):63—70, July/August 1999. 113 [11] S. Corson and J. Macker. Mobile Ad hoc Networking (MAN ET): Routing Pro— tocol Performance Issues and Evaluation Considerations. Internet-Draft, Oct. 1998. [12] B. Das and V. Bharghavan. Routing in Ad—Hoc Networks using Minimum Con- nected Dominating Sets. In IEEE International Conference on Communications (ICC ’97), 1997. [13] S. Das, R. Castaneda, J. Yan, and R. Sengupta. Comparative Performance Evaluation of Routing Protocols for Mobile Ad Hoc Networks. In Proceedings of 7th Annual ICCCN, Oct. 1998. [14] B. Rajagopalan E. Crawley, R. Nair. A framework for qos-based routing in the internet. RFC 2386, August 1998. [15] The editors of IEEE 802.11. Wireless lan medium access control (mac) and physical layer (phy) specifications. In IEEE Draft Version, May 1996. [16] Moncef Elaoud and Parameswaran Ramanathan. Adaptive use of error- correcting codes for real-time communication in wireless networks. In INFO- COM, pages 548—555, 1998. [17] A. Alwan et a1. Adaptive Mobile Multimedia Networks. IEEE Personal Com- munications Magazine, 3(2), Apr. 1996. [18] A. Fasbender et a1. Any Network, Any Terminal, Anywhere. IEEE Personal Communications, Apr. 1999. [19] J. Broch et al. A Performance Comparison of Multi—HOp Wireless Ad Hoc Rout- ing Protocols. In Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking, Oct. 1998. [20] P. Krishna et al. A Cluster-Based Approach for Routing in Ad—Hoc Networks. In Proceedings of the Second USENIX Symposium on Mobile and Location- Independent Computing, pages 1—10, 1995. [21] R. Dube et al. Signal Stability Based Adaptive Routing (SSA) for Ad-Hoc Networks. IEEE Personal Communications, Feb. 1997. [22] M. Gerla, K. Tang, and R. Bagrodia. Tcp performance in wireless multi-hop networks. In Proceedings of IEEE WM CSA ’99, New Orleans, LA, February 1999. [23] Z. Haas. A new routing protocol for reconfigurable wireless networks. In In Proc. of IEEE International Conf. on Universal Personal Communications (ICUPC), 1997 . [24] Z. J. Haas. ”panel report on ad-hoc networks”. Mobile Computing and Commu- nications Review, 2(1), 1997. 114 [25] Gavin Holland and N itin H. Vaidya. Analysis of TCP performance over mobile ad hoc networks. In Proceedings of IEEE/A CM M OBICOM ’99, pages 219—230, August 1999. [26] C. Huitema. The case for packet level fee. In In Proceedings of IFIP 5th Int ’1 Workshop on Protocols for High Speed Networks, pages 109-120, Sophia Antipolis France, October 1996. [27] A. Iwata, C.C. Chiang, G. Pei, M. Gerla, and T. W. Chen. Scalable routing strategies for ad hoc wireless networks. IEEE Journal on Selected Areas in Communications, 17(8):1369—1379, August 1999. [28] D. Johnson J. Broch and D. Maltz. The Dynamic Source Routing Protocol for Mobile Ad-Hoc Networks. Internet Draft, Mar. 1998. [29] R. Jain. The Art of Computer System Performance and Analysis. John Wiley and Sons, New York, 1991. [30] D. Johnson and D. Maltz. Dynamic Source Routing in Ad Hoc Wireless Net- works. In T. Imielinski and eds. H. Korth, editors, Mobile Computing. Kluwer Academic Publishers, 1996. [31] Seung-Seok Kang and Matt W. Mutka. Provisioning service differentiation in ad hoc networks by the modification of backoff algorithm. In International Confer- ence on Computer Communication and Network(ICCCN), Scottsdale, Arizona, October 2001. [32] P. Karn. Maca- a new channel access method for packet radio. In ARRl/CRRL Amateur Radio 9th Computer Networking Conference, pages 134-140, 1990. [33] Y.B. Ko and NH. Vaidya. Location-Aided Routing (LAR) in Mobile Ad—Hoc Networks. In Proc. ACM/IEEE MOBICOM, Oct. 1998. [34] Marwan Krunz and Jeong Geun Kim. Fluid analysis of delay and packet discard performance for qos support in wireless networks. IEEE Journal on Selected Areas in Communications (JSA C), 19(2):384—395, February 2001. [35] J. F. Kurose and K. W. Ross. Computer Networking: A Top-down Approach Featuring the Internet. Addison Wesley, 2001. [36] S. Lee and M. Gerla. Split multipath routing with maximally disjoint paths in ad hoc networks, 2001. [37] Seoung-Bum Lee, Ahn Gahng-Seop, Xiaowei Zhang, and Andrew T. Campbell. Evaluation of the insignia signaling system. In 8th IFIP International Conference on High Performance Networking (Networking 2000), Paris, France, May 2000. 115 [38] Seoung-Bum Lee, Ahn Gahng-Seop, Xiaowei Zhang, and Andrew T. Campbell. Insignia: An ip—based quality of service framework for mobile ad hoc networks. Journal of Parallel and Distributed Computing (Academic Press) , Special issue on Wireless and Mobile Computing and Communications, 60(4):374-406, April 2000. [39] P. Lettieri and M. Srivastav. Advances in Wireless Terminals. IEEE Personal Communications, Feb. 1999. [40] C.-R. Lin, , and M. Gerla. Asynchronous multimedia multihop wireless networks. In Proceedings of the 1997 IEEE INFOCOM, volume 1, pages 118—125, 1997. [41] Chunhung Richard Lin and J ain-Shing Liu. Bandwidth routing in ad hoc wireless networks. IEI CE Transactions on Communication, E83-B(7):1497—1508, July 2000. [42] CR. Lin and J .-S. Liu. Qos routing in ad hoc wireless networks. IEEE Journal on Special Areas in Communications, 17(8):1426—38, August 1999. [43] Mario Gerla Lokesh Bajaj, Mineo Takai, Rajat Ahuja, Rajive Bagrodia. Glo- mosim: A scalable network simulation environment. Technical Report 990027, UCLA, 13, 1999. [44] N. Schultz M. Mirhakkak and D. Thompson. Dynamic qos for mobile ad hoc networks. Technical report, The MITRE Corporation, April 2000. [45] A. J. McAuley. Reliable broadband communication using a burst erasure correct- ing code,. In Proceedings of ACM SIGCOMM; (Special Issue Computer Com- munication Review), pages 297—306, 1990. [46] A. Bruce McDonald and Taieb Znat. A path availability model for wireless ad- hoc networks. In IEEE Wireless Communications and Networking Conference 1999 (WCNC ’99), New Orleans, LA, 1999. [47] A. Bruce McDonald and Taieb Znati. A mobility-based framework for adap- tive clustering in wireless ad-hoc networks. IEEE Journal on Selected Areas in Communication, Special Issue an Ad hoc Networks, 17(8), August 1999. [48] Richard A. Meyer and Rajive Bagrodia. Parsec user manual. Technical report, UCLA Parallel Computing Laboratory, 1998. [49] S. Murthy and J .J . Garcia-Lunes-Aceves. An Efficient Routing Protocol for Wireless Networks. ACM Balzer Mobile Networks and Applications Journal, Special Issue on Routing in Mobile Communications Networks, 1996. [50] Kathleen Nichols and Steven Blake. Differiated Service Operational Model And Definitions. Internet-Draft, February 1998. 116 [51] V. D. Park and M. S. Corson. A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks. In IEEE Infocom, Apr. 1997. [52] MR. Pearlman, Z.J. Haas, P. Scholander, and SS. Tabrizi. On the impact of alternate path routing for load balancing in mobile ad hoc networks. In ACM MobiHOC, Boston, MA, August 2000. [53] C. Perkins and E. Royer. Ad Hoc On Demand Distance Vector (AODV) Routing. Internet-Draft, Nov. 1998. [54] C. Perkins and E. Royer. Ad Hoc On-Demand Distance Vector Routing. In Proceedings 2nd IEEE Workshop on Mobile Computing Systems and Applications ( WM CSA ’99), 1999. [55] C. Perkins, E. Royer, and SR. Das. Quality of Service for Ad Hoc On Demand Distance Vector (AODV) Routing. Internet-Draft, July 2000. [56] C. E. Perkins. Mobile Ad Hoc Networking Terminology. Internet Draft, Nov. 1998. [57] C. R. Perkins and P. Bhagwat. Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile Computers. In ACM SI G COMM, pages 234— 244, Oct. 1994. [58] Dmitri D. Perkins and Herman D. Hughes. Performance evaluation of routing strategies for mobile ad hoc networks. In Proceedings of the International Sympo- sium on Performance Evaluation of Computer and Telecommunication Systems, Vancouver, BC. Canada, July 2000. [59] Dmitri D. Perkins and Herman D. Hughes. Tcp over mac protocols in mobile ad hoc networks: A performance evaluation. In Proceedings of the 2001 In— ternational Conference on Advances in Infrastructure for Electronic, Business, Science, and Education on the Internet, L’Aquila, Italy, August 2001. [60] Dmitri D. Perkins and Herman D. Hughes. Tcp performance in mobile ad hoc networks. In Proceedings of the International Symposium on Performance Evalu- ation of Computer and Telecommunication Systems, Orlando, Florida, July 2001. [61] Dmitri D. Perkins and Herman D. Hughes. Factors affecting the performance of ad hoc networks. In The Proceedings of the IEEE International Conference on Communications 2002, New York, New York, April 2002. [62] Dmitri D. Perkins and Herman D. Hughes. The interaction of mac layer protocols and tcp in mobile ad hoc networks. In Proceedings of the International Sympo- sium on Performance Evaluation of Computer and Telecommunication Systems, San Diego, CA, July 2002. [63] James S. Plank. A tutorial on Reed-Solomon coding for fault-tolerance in RAID- like systems. Software Practice and Experience, 27(9):995—1012, 1997. 117 [64] R. Ramanathan and M. Steenstrup. Hierarchiically-Organized, Multihop Mobile Wireless Networks for Quality-of-Service Support. Mobile Networks and Appli- cations, 3, 1998. [65] Sheldon M. Ross. Introduction to Probability Models. Academic Press, 6 edition, 1997. [66] Raghupathy Sivakumar, Prasun Sinha, and Vaduvur Bharghavan. Cedar: Core extraction distributed ad hoc routing. IEEE Journal on Selected Areas in Com- munication, Special Issue an Ad hoc Networks, 17(8), August 1999. [67] J .L. Sobrinho and A. S. Krishnakumar. Quality-of-service in ad hoc carrier sense multiple access wireless networks. IEEE Journal on Special Areas in Communi- cations, 17(8), August 1999. [68] H. Takagi and L. Kleinrock. Optimal Transmission Ranges for Randomly Dis- tributed Packet Radio Terminals. IEEE Transactions on Communications, 32(3), Mar. 1984. [69] A. S. Tanenbaum. Computer Networks. Prentice Hall, New Jersey, third edition, 1996. [70] C-K Toh. Associativity—Based Routing for Ad-Hoc Networks. Wireless Personal Communications, 4(2), Mar. 1997. [71] Hannan Xiao, Winston K.G. Seah, Anthony Lo, and Kee Chaing Chua. A flexible quality of service model for mobile ad-hoc networks. In IEEE 5Ist Vehicular Technology Conference Proceedings 2000 (VTC-2000), volume 1, pages 445—449, Tokyo, Japan, 2000. [72] Xiang Zeng, Rajive Bagrodia, and Mario Gerla. lomosim: A library for par- allel simulation of large-scale wireless networks. In Workshop on Parallel and Distributed Simulation, pages 154—161, 1998. [73] Lixia Zhang, Stephen Deering, and Deborah Estrin. RSVP: A new resource ReSerVation protocol. IEEE network, 7(5), September 1993. 118 m[[m]]]]]]]]][]]][I