1	On the Inadequacy of MANET Routing to Efficiently Use the Wireless Capacity Thomas Kunz Systems and Computer Engineering Carleton University tkunz@sce.carleton.ca
2	MANET: Characteristics and Challenges Ad-Hoc Networks, radio communication, multi-hop connections Routing protocols (AODV, DSR, OLSR) typically find shortest path (minimum hop count), though a range of other metrics (ETX, maximum throughput, minimum energy consumption, etc.) have been explored as well Network bandwidth is scarce: Limited by wireless technology Self-interference of single-radio multi-hop communication reduces end-to-end bandwidth for single flows All nodes share common media: interference, collisions, back-offs Question: how well do routing protocols utilize scarce wireless bandwidth?
3	Uneven Use of Network Capacity: DSR
4	End-to-End Bandwidth: Analytical Bounds Idea: model problem as multi-commodity flow problem, add interference constraints, and solve with Linear Solver
5	Sample Linear Program max: Z_A Z_A: flow from A to C Flow Balance constraints (per node): X_I,J: flow over link from I to J X_A,B = Z_A + X_B,A X_B,A + X_B,C = X_A,B + X_C,B Flow Balance Constraint: as much X_C,B + Z_A = X_B,C flows into each node as out Capacity Constraints (per link) Capacity Constraint: no link can X_A,B <= LINK_BW exceed link bandwidth X_B,A <= LINK_BW X_B,C <= LINK_BW Solution: Z_A = X_A,B = X_B,C = 1 (assuming LINK_BW=2) X_C,B <= LINK_BW X_B,A = X_C,B = 0 L1 = L3 = 0.5, L2 = L4 = 0 Scheduling Constraints Scheduling Constraints: model L1 + L2 + L3 + L4 <= 1 interference. Idea is based on X_A,B <= LINK_BW * L1 scheduling transmission over non- X_B,A <= LINK_BW * L2 interfering links by determining X_B,C <= LINK_BW * L3 maximum sets of non-interfering X_C,B <= LINK_BW * L4 links.
6	More Complex Networks Determining all independent link sets is NP-complete, so heuristically determine a few (will generate lower bound on network capacity) Can modify LP to account for different radio models, rate-adaptive MACs, etc. Straightforward to extend to multiple flows For N nodes, S flows, and M independent sets, the maximum number of variables will be (N-1)(N-1)S + S + M, and N*S + M + 1 constraints To model actual network, numbers depend on topology: 100 nodes in a 1500 m x 1500 m area and 50 flows, attempting to find 10,000 independent scheduling sets: the maximum number of variables is 500,100, with 15,001 constraints. Using randomly generated static topologies, we counted between 46,000 to 70,000 variables and around 5,200-5,700 constraints.
7	Lower Bounds I: 50 nodes, 1 km²
8	Lower Bounds I: 50 nodes, 1 km²
9	Performance of Routing Protocols: NS2
10	Relating Simulation and LP Results Maximum AODV throughput: 178 kbps (for 15 sender/flows) LP: Maximum throughput 1.2 – 1.8 times LINK_BW (2 Mbps), depending on node distribution and min flow constraint Naïve Interpretation: Huge Gap (7.5 % of LP result) More Detailed Analysis: MAC Overhead (analytical results): saturation throughput only 40% of LINK_BW for packet size, number of neighbors Accounting for routing protocol overhead (50% of all MAC transmission) Lost packets also consume network resources: 15 sender generate aggregate of 300 kbps, only 178 kbps received. If packets are, on average, dropped midway, corresponds to 61 kbps of end-to-end traffic
11	Bringing it All Together For nonuniform node distribution with minimum flow constraints: lower bound on achievable end-to-end throughput is 1.016 Mbps (2 Mbps * 1.27 * 0.4) Simulation Results for Maximum End-to-End Throughput: Delivered CBR traffic: 178 kbps Lost CBR traffic: 61 kbps Control Packets: (178 + 61) kbps Sum total: 478 kpbs or 46% of analytical lower bound 54% of available capacity not utilized
12	Conclusions and Future Work Existing MANET routing protocols ignore/underutilize available network capacity Current and Future Work on MANET Routing Protocol: Currently working on new routing algorithm, TB, that finds routes through less loaded areas of network (similar to DSR): higher PDR, lower latency TB uses medium usage (collected at MAC) to determine network load, need to study other metrics Apply TB to MESH networks to balance traffic load to APs/Gateways Future Work on Linear Programming: LP implicitly finds routes as well – can we use or approximate those? LP does not adequately capture effects of packet loss (senders inject “just right” amount of traffic to achieve max. performance) or routing protocol LP is computational complex and does not deal with dynamic scenarios