A Survey of Routing Protocols that Support QoS in Mobile Ad Hoc Networks <s> Bandwidth/Delay Estimation <s> Early simulation experience with wireless ad hoc networks suggests that their capacity can be surprisingly low, due to the requirement that nodes forward each others' packets. The achievable capacity depends on network size, traffic patterns, and detailed local radio interactions. This paper examines these factors alone and in combination, using simulation and analysis from first principles. Our results include both specific constants and general scaling relationships helpful in understanding the limitations of wireless ad hoc networks. We examine interactions of the 802.11 MAC and ad hoc forwarding and the effect on capacity for several simple configurations and traffic patterns. While 802.11 discovers reasonably good schedules, we nonetheless observe capacities markedly less than optimal for very simple chain and lattice networks with very regular traffic patterns. We validate some simulation results with experiments. We also show that the traffic pattern determines whether an ad hoc network's per node capacity will scale to large networks. In particular, we show that for total capacity to scale up with network size the average distance between source and destination nodes must remain small as the network grows. Non-local traffic-patterns in which this average distance grows with the network size result in a rapid decrease of per node capacity. Thus the question “Are large ad hoc networks feasible?” reduces to a question about the likely locality of communication in such networks. <s> BIB001 </s> A Survey of Routing Protocols that Support QoS in Mobile Ad Hoc Networks <s> Bandwidth/Delay Estimation <s> Admission control of flows is essential for providing quality of service in multihop wireless networks. In order to make an admission decision for a new flow, the expected bandwidth consumption of the flow must be correctly determined. Due to the shared nature of the wireless medium, nodes along a multihop path contend among themselves for access to the medium. This leads to intra-flow contention; contention between packets of the same flow being forwarded at different hops along a multihop path causing the actual bandwidth consumption of the flow to become a multiple of its single hop bandwidth requirement. Determining the amount of intra-flow contention is non-trivial since interfering nodes may not be able to communicate directly if they are outside each other's transmission range. In this paper, we propose two methods to determine the extent of intra-flow contention along multihop paths. The highlight of the proposed solutions is that carrier-sensing data is used to deduce information about carrier-sensing neighbors, and no high power transmissions are necessary. Analytical and simulation results show that our methods estimate intra-flow contention with low error, while significantly reducing overhead, energy consumption and latency as compared to previous approaches. <s> BIB002
The first open issue in supporting QoS-aware routing is: what is the best way to estimate available bandwidth and/or delay to maximize accuracy and minimize overhead for resource estimation? The challenge in wireless ad hoc networks is that neighboring hosts must share the bandwidth, and there is no centralized control for allocating bandwidth among the nodes. Furthermore, intermediate hosts take part in forwarding packets. Therefore, the total effective capacity achievable is not only limited by the raw channel capacity, but it is also limited by the interaction and interference among neighboring hosts. Thus, to offer bandwidth-guaranteed or delay-guaranteed routing, bandwidth/delay estimation is required, yet accurately estimating available bandwidth/maximum delay at each host is a challenging problem. As shown in Table 1 , most existing QoS-aware routing protocols assume that the available bandwidth is known. For those protocols that do include bandwidth estimation, two methods have been proposed. • Exploit the carrier-sense capability of IEEE 802.11 and measure the idle and busy time ratio (used in OLSR-based QoS routing and BEQR). • Add bandwidth consumption information to route control packets and exchange this information with neighbor hosts (used in AQOR and BEQR). The estimated available bandwidth is different than the rates of the supported flows, due to intra-flow contention. To address the intra-flow contention problem, the following have been proposed: assuming the network is well-connected, relating the approximate available bandwidth to the number of hops in the route BIB001 ; and the use of Pre-Reply Probe (PRP), and Route Request Tail (RRT) packets BIB002 . Further research is required to determine the accuracy and overhead for these bandwidth estimation and intra-flow contention estimation techniques. Only two of the surveyed routing protocols incorporate delay estimation (Table 1) . These protocols do not support a specified delay. They merely determine the shortest delay route during route discovery, and they do not take into account changes in contention levels that will impact the endto-end delay significantly after the flow is started. Also, the effect of intra-flow contention on delay has not been studied sufficiently. Unlike in wired networks, hosts in wireless networks have no knowledge about available bandwidth resources or delay at the network layer, due to the shared wireless channel. Thus, a host cannot make an accurate decision on call admission or provide feedback on the network status, based on information obtained from the network layer -a cross-layer design is key to solving this problem. All the bandwidth and delay estima-tion methods discussed in this article are associated with the capabilities of the underlying MAC protocol.