On the Inadequacy of MANET Routing to Efficiently Use the Wireless Capacity
| Thomas Kunz | |
| Systems and Computer Engineering | |
| Carleton University | |
| tkunz@sce.carleton.ca |
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? | ||
Uneven Use of Network Capacity: DSR
End-to-End Bandwidth: Analytical Bounds
| Idea: model problem as multi-commodity flow problem, add interference constraints, and solve with Linear Solver |
| 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. |
| 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. | ||
Lower Bounds I: 50 nodes, 1 km2
Lower Bounds I: 50 nodes, 1 km2
Performance of Routing Protocols: NS2
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 | ||
| 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 | ||
| 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 | ||