Study of Intra and Inter Flow Contentions In Manet

To support reliable transport service and hence fully exploit the potential of mobile ad hoc networks (MANET), efficient congestion control is of paramount importance to make MANET viable for many applications in battlefield, disaster rescue and conventions. However, medium contention in the shared channel environment of MANET offers a great challenge to traditional TCP congestion control mechanism and make TCP traffic suffer poor performance in MANET ( [1]-[7] and reference therein). Most of the current work on TCP performance in MANET, such as [6]-[14], focus on end-to-end congestion control mechanism of TCP with or without network layer feedback. To our best knowledge, in recent studies, only [15] comprehensively discussed hop-by-hop congestion control for MANET. However, their system model did not completely describe the characteristics of MANET. It only considered the channel sharing for those nodes with the same flows passing through, and did not consider other medium contention among nodes which are in the sensing range or interference range of each other. Their studies focused on the theoretical part and did not give a scheme based upon the widely employed 802.11 MAC protocol [16]. They concluded that hop by hop congestion control will get the same end-to-end throughput as end-to-end congestion control. In this paper, we will show that hop-by-hop congestion control can help TCP traffic get higher throughput by greatly decreasing medium contentions based upon a well designed scheme over the 802.11 MAC protocol. Combined with our previous work in [17], which showed hop-by-hop congestion control could gracefully decrease the impact of irresponsible UDP traffic, significantly improve the maximum end-to-end throughput and reduce the end-to-end delay, our studies of TCP performance in this paper demonstrate that hop-by-hop congestion control is a necessary component to support reliable and stable service for MANET. To well address the impact of medium contention on the performance of TCP traffic, we characterize the interaction between the congestion of traffic flows and the MAC layer contentions as intra-flow contention and inter-flow contention. Notice that, in MANET, nodes are cooperative to forward each other's packets through the networks. Due to the contention for the shared channel, the throughput of each single node is limited not only by the raw channel capacity, but also by the transmissions in its neighborhood. Thus, each multi-hop flow encounters contentions not only from other flows which pass through the neighborhood, i.e., the inter-flow contention, but also from the transmissions of itself because the transmission at each hop has to contend the channel with upstream and downstream nodes, i.e., the intra-flow contention. These two kinds of flow contentions could result in severe collisions and congestion, and seriously limit the performance of multihop ad hoc networks [1], [6], [18]-[20]. The MAC protocol itself could not solve the congestion problem and it often aggravates the congestion due to the contentions in the shared channel environment. Fang and McDonald [21] studied how throughput and delay can be affected by path coupling, i.e., the MAC layer contention among the nodes distributed along the node-disjoint paths, which is the inter-flow contention. The results demonstrated the need for the control and design of cross-layer interactions and optimization. To the best of our knowledge, there are no comprehensive studies and good solutions to the interaction problem between traffic congestion and MAC contention in multihop ad hoc networks. Moreover, the scalability issue of 802.11 have not been well addressed and the performance of throughput and end- to-end delay degrades severely in the multihop environment. In this paper, we present a framework of hop-by-hop flow control and medium access control to address the

Based on this framework, a multihop packet scheduling algorithm is incorporated into the IEEE 802.11 MAC protocol. Our framework consists of multiple mechanisms to provide effective hop-by-hop congestion control. The fast relay assigns high priority of channel access to the downstream nodes when they

control gives transmission opportunity to a congested node and prevents its upstream nodes from further transmissions. This could not only dramatically reduce contentions in the congested area, but also quickly eliminate the congestion. It is also a quick method to notify the source to reduce the sending rate by exploiting the RTS/CTS operations in the IEEE 802.11 MAC protocol. The receiver-initiated transmission scheme uses a three- way handshake to resume the blocked flow at the upstream nodes when the congestion is cleared. It is a timely and economical approach with even less control overhead than the normal four-way handshake transmission in the IEEE 802.11 protocol. The rest of this paper is organized as follows. Section II details the impacts of MAC layer contentions on traffic flows and the resulting problems. Section III describes our scheme and the implementation based on the IEEE 802.11 MAC protocol. In Section IV the performance of our scheme is evaluated for TCP

Fig. 1. Chain topology

traffic through extensive simulations. Finally, we conclude the paper in section V.

Different from the wired networks where the links are independent of each other, the wireless links may share the same channel resource. Thus the MAC layer contentions come into play when the traffic flows travel through the networks. Considering the fact that the contentions are from the transmission attempts of packets at different nodes, which are generated by various traffic flows, it is natural to exploit the flow control to schedule the packet transmissions to reduce the collisions and congestion. Before presenting our scheme, we first discuss the intra-flow contention and inter- flow contention problems. The intra-flow contention here means the MAC layer contentions for the shared channel among nodes which are in each other's interference range along the path of the same flow. Li et al. has observed that the IEEE 802.11 protocol fails to achieve the optimum chain scheduling [18]. Nodes in a chain experience different amount of competitions as shown in Fig. 1, where the small circle denotes a node's valid transmission range, and the large circle denotes a node's interference range. Thus, the transmission of node 0 in a 7-node chain experiences interference from three subsequent nodes, while the transmission of node 2 is interfered by five other nodes. This implies that node 0, i.e., the source, could actually inject more packets into the chain than the subsequent nodes can forward. These packets are eventually dropped at the two subsequent nodes. We call this problem as the intra-flow contention problem. Fig.2 demonstrate that TCP traffic introduce a great number of packet collisions. Fig. 3 illustrates more detail why this could happen. Actually, as illustrated in the previous paragraph, node 3, 4 and 5 in a 9-node chain encounter more medium contention than node 1 and 2, thus packet cumulate at these nodes, and keeping them contending for channel access. This results in severe medium collision and a lot of dropped packets. Here, the simulation settings are the same with those of section IV-A, and different number of TCP flows travel from node 1 to node 9 in a 9- node chain topology. Besides above contentions inside a multi-hop flow, the contentions between flows could also seriously decrease the network throughput. If two or more flows pass through the same region, the forwarding nodes of each flow encounter contentions not only from its own flow but also from other flows. Thus the previous hops of these flows could actually inject more packets into the region than the nodes in the region can forward. These packets are eventually dropped by the congested nodes. As shown in Fig. 4, where there are two flows, one is from 0 to 6 and the other is from 7 to 12. Obviously node 3 encounters the most frequent contentions and has few chance to successfully transmit packets to its downstream nodes. The packets will accumulate at and be dropped by node 3, 9, 2, 8 and 1. We call this problem as the inter-flow contention problem.

Fig. 2. TCP Performance in Chain topology

Fig. 3. Average queue length in Chain topology with 6 TCP flows

In the shared channel environments in multihop ad hoc networks, these two kinds of contentions are widespread and result in congestion at some nodes, where packets continuously accumulate, which then aggravates the contentions and finally results in packet dropping. This not only greatly decreases the end-to-end throughput but also increases the end-to-end delay due to the long queueing delay. The intuitive solution to the above problems is to allow the downstream nodes and the congested ones to transmit packets while keeping others silent, and hence smoothly forward each packet to the destination without encountering severe collisions or excessive delay at the forwarding nodes. This motivates us to develop our scheme presented in the next section.

We now evaluate the performance of our scheme OPET and compare it with the IEEE 802.11 scheme. The simulation tool is one of the widely used network simulation tools - ns-2. We use pre-computed shortest path and there is no routing overhead. The propagation model is two-ray ground model and the channel bandwidth is 2 Mbps. The transmission range is about 250 meters and the sensing range is about 550 meters. In what follows, our scheme will be referred to as the Optimum Packet Scheduling for Each Flow (OPET), and the IEEE 802.11 protocol without the packet scheduling algorithm will be referred to as the Basic scheme.

We first investigate how well our scheme performs in the 9-node chain topology with different number of TCP flows. The nodes are separated by 200 meters in the chain. The TCP flows starts from the beginning of the chain, i.e, node 1, to the end of the chain, i.e., node 9. Fig. 10 shows that our scheme OPET can reduce the packet collision by about 40% for both RTS and ACK frames. And the number of dropped TCP packets is also reduced by about 80%. This verifies that the hop-by-hop congestion control can effectively reduce a lot of medium contention and collision. Fig. 11 demonstrates that OPET can improve the aggregate throughput of TCP flows by about 5%. And the fairness is even better than the Basic scheme. Here, the fairness index is calculated by the Jain's index, i.e., where xi denotes the end-to-end throughput of the ith flow. Actually, the above two figure shows that our scheme is much more energy efficient than Basic scheme because OPET can deliver higher throughput but with much less collided packets in the air.

Fig. 10. Collisions of TCP traffic in chain topology

Fig. 11. Throughput and fairness of TCP traffic in chain topology

Fig. 12 illustrates the necessity for TCP source to reduce the sending rate when it observes that the outgoing queue builds up. This demonstrates that the hop-by-hop congestion control could notify the source of the congestion status by a very simple and easily measured metric, i.e., queue length at the source node. Thus, if some adaptive mechanism is adopted for TCP source to adjust the sending rate according to the queue length at source node, we will hopefully observe much better performance, such as much less medium collisions, higher throughput, and short delay, although such kind of mechanism is out of the scope of this paper.

In this subsection, we will investigate the performance of OPET in a larger network with grid topology, where inter-flow contention is a common phenomenon. The grid topology is shown in Fig. 13, where there are total 100 nodes, and one-hop distance is set as 200 meters. 16 TCP flows with 8 horizontal ones and 8 vertical ones, as shown in Fig. 13, run for 300 seconds in the simulation. Table I shows the simulation result which demonstrates that OPET improves the aggregate end-to- end throughput by about 10% with about 26% less collided RTS packets. This further verifies that OPET can perform much better than the Basic scheme when the intra-flow and inter-flow contention coexist.

Fig. 12. Queue length for TCP traffic in chain topology

Fig. 13. Grid Topology with 16 TCP flows

In summary, our scheme could reduce a lot of medium contention in MANET and hence improve the aggregate end-to-end throughput of TCP traffic. Energy efficiency is also improved by delivering higher throughput with less packet collisions.

In this paper, we focus on the interaction between medium contention and traffic congestion for TCP traffic in MANET. We first present our observation that the poor performance of the IEEE 802.11 is attributed to the intra-flow contention and inter-flow contention in multihop ad hoc networks. In order to reduce these two kinds of contentions, we have built a framework for distributed hop-by-hop flow control and media access control, based on which a multihop packet scheduling algorithm, i.e., OPET, is proposed for the 802.11 based multihop wireless ad hoc networks.

TABLE I : Simulation Results for TCP Flows in Grid Topology

Extensive simulations verify that our scheme OPET could greatly mitigate collisions at the MAC layer and has a much better multihop packet scheduling than the IEEE 802.11 protocol. Thus it can always achieve stable and high throughput with much less packet collisions and higher energy efficiency. Combined with our previous studies for UDP traffic in [17], the studies in this paper demonstrate that hop-by-hop congestion control with careful design over the IEEE 802.11 MAC protocol can not only significantly alleviate the impact of irresponsible UDP flows, but also well support the reliable service over TCP flows by significantly improving the end-to-end throughput and reducing the medium collisions.

1. S. Xu and T. Safadawi, "Does the IEEE 802.11 MAC Protocol Work Well in Multihop Wireless Ad Hoc Networks?" IEEE Communications Magazine, pp. 130-137, June 2001. 2. X. Chen, H. Zhai, J. Wang and Y. Fang. TCP performance over mobile ad hoc networks. Accepted for

Computers and Communications, Italy, July 2002 4. M. Gerla, R. Bagrodia, L. Zhang, K. Tang, and L. Wang. TCP over Wireless Multihop Protocols Simulation and Experiments. in Proc. of IEEE ICC 1999, Vancouver, Canada, Jun. 1999.

WMCSA '99, New Orleans, LA, Feb. 1999. 6. Z. Fu, P. Zerfos, H. Luo, S. Lu, L. Zhang, M. Gerla, "The Impact of Multihop Wireless Channel on TCP Throughput and Loss," Proc. IEEE INFOCOMM'2003, March 2003. 7. K. Chen, Y. Xue, and K. Nahrstedt. On setting TCP's congestion window limit in mobile ad hoc networks in Proc. of IEEE ICC 2003, May, 2003. 8. K. Chandran, S. Raghunathan, S. Venkatesan, and R. Prakash, "A feedback-based scheme for improving TCP performance in ad hoc wireless networks," IEEE Personal communications, 8 (1):34-39, February 2001.

MOBICOM'99, Seattle, August 1999.

2000

11. J. Liu and S. Singh, "ATCP: TCP for mobile ad hoc networks," IEEE JSAC. Vol.19 No.7, July 2001. 12. T. D. Dyer and R. V. Boppana, "A comparison of TCP performance over three routing protocols for mobile ad hoc networks," ACM Mobihoc, October 2001. 13. F. Wang and Y. Zhang, "Improving TCP performance over mobile ad-hoc networks with out-of-order detection and response," ACM MobiHoc'02, pp. 217-225, Lausanne, Switzerland, Jun 2002. 14. K. Xu, M. Gerla, L. Qi, and Y. Shu, Enhancing TCP fairness in ad hoc wireless networks using neighborhood RED. in Proc. of ACM MobiCom 2003, Sep. 2003. 15. Y. Yi and S. Shakkottai. Hop-by-hop congestion control over a wireless multi-hop network. to appear in Proc. of IEEE INFOCOM, 2004.

17. H. Zhai, J. Wang, and Y. Fang. Distributed Packet Scheduling for Multihop Flows in Ad Hoc Networks. in Proc. of IEEE WCNC'04, Atlanta, March, 2004 18. J. Li, C. Blake, D. S. J. De Couto, H. I. Lee and R. Morris, "Capacity of Ad Hoc Wireless Network," in Proc. of ACM MobiCom 2001, July 2001. 19. J. Broch, D.A. Maltz, D.B. Johnson, Y. Hu, and J. Jetcheva, "A performance Comparison of Multihop

Computing and Networking (MobiCom'98), pp. 85-97, Oct. 1998. 20. C. Perkins, E.M. Royer, S.R. Das, and M.K. Marina, "Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks," IEEE Personal Communications, pp. 16-28, Feb. 2001. 21. Y. Fang and A.B. McDonald, "Cross-layer performance effects of path coupling in wireless ad hoc

Performance, Computing, and Communications Conference, April 2002