Quality-of-Service Routing in Ad-Hoc Networks Using OLSR
| Ying Ge, Thomas Kunz, Louise Lamont | |
| CRC Carleton University CRC | |
| http://kunz-pc.sce.carleton.ca/ | |
| tkunz@sce.carleton.ca |
| Introduce QoS routing into OLSR | |
| Develop three heuristics to enhance OLSR | |
| Evaluate heuristics | |
| Prove the optimality of two of the heuristics in static network case |
| QoS Route Information | ||
| Using traditional best-effort Ad-Hoc routing algorithms | ||
| Piggybacking QoS information in control messages | ||
| Useful for call admission control | ||
| QoS Routing Computation | ||
| Ticket-based probing | ||
| CEDAR | ||
| Hierarchically structured multi-clustered organizations | ||
| Selects MPR to cover 2-hop neighbors | |
| Exchanges neighbor/MPR information in Hello message | |
| Generates and relays TC message to broadcast topology information | |
| Reduces control overhead by limiting MPR set | |
| In the graph, B selects C as MPR |
| Same topology as before, numbers along edges indicate available bandwidth | |
| OLSR: node B will select C as its MPR | |
| So all the other nodes know that they can reach B via C | |
| When D is building its routing table, for destination B, it will select the route D-C-B, whose bottleneck bandwidth is 3, the worst among all the possible routes | |
| Optimal route (i.e., path with maximum bottleneck bandwidth: D-F-B (bottleneck bandwidth of 10) |
| Change MPR selection | ||
| Limited by neighbour knowledge: direct neighbours and two-hop neighbours | ||
| Assume bandwidth to neighbours and between 1-hop and 2-hop neighbours is known | ||
| Change route table calculation, based on TC messages (which contain information about MPR selection) | ||
| OLSR_R1: similar to OLSR (i.e., choose 1-hop neighbours that cover maximum number of 2-hop neighbours), tie-breaker now maximum bandwidth | |
| OLSR_R2: select the best bandwidth neighbors as MPRs until all the 2-hop neighbors are covered. | |
| OLSR_R3: selects the MPRs in a way such that all the 2-hop neighbors have the maximum bottleneck bandwidth path through the MPRs to the current node |
| Take bandwidth into account: | ||
| Maximum spanning tree (in paper) | ||
| Extended Bellman-Ford (BF) shortest path | ||
| Same complexity, second algorithm guarantees that we find shortest route as well | ||
| Proof that algorithms indeed correctly find maximum bandwidth path | ||
| If complete knowledge, proof by contradiction | ||
| Can show that TC messages have enough (i.e., the important) information | ||
| Simulation: generate networks, run OLSR algorithms, compare results against paths calculated by Link-State algorithm (i.e., complete knowledge, all-pair shortest path) | |
| Network area: 1000 M ´ 1000 M | |
| Number of nodes: 100 | |
| Transmission range: 100 M, 200 M, 300 M | |
| Bandwidth: assigned randomly | |
| Results are averaged over 100 randomly generated networks |
| Error rate: percentage of routes with non-optimal bandwidth | |
| Average difference: for routes with non-optimal bandwidth, how far off the optimal bandwidth are we | |
| Overhead: the average number of control messages transmitted per node | |
| MPR count: average number of MPRs in the network |
| OLSR_R1: simple change, with little additional overhead, but already significant improvement (mostly due to change to routing table calculation) | |
| OLSR_R2 and OLSR_R3 seem to be perfect, paper contains proof that both MPR selection criteria allow to reliably detect optimal path | |
| OLSR_R2 selects fewer MPRs, less overhead, therefore preferred | |
| Transmission range has important impact: higher range means denser network but not necessarily higher overhead or error rate |
| Implement OLSR_R2 in OPNET and study performance in dynamic environment (currently under way) | ||
| Trigger TC messages not only when topology changes, but also when significant bandwidth changes | ||
| QoS OLSR overhead will compete with data traffic for fixed bandwidth, if overhead too high, best bandwidth route may well have less available bandwidth than non-optimal best-effort OLSR route | ||
| Compare QoS routing to QoS signaling in MANET such as dRSVP, INSIGNIA, SWAN | ||
| Combine QoS OLSR with SWAN | ||