1	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
2	Contributions 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
3	Related Work in QoS Routing 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
4	Description of OLSR 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
5	OLSR QoS Limitations 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)
6	QoS Modifications 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)
7	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
8	Routing Table Calculation 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
9	Evaluation of QoS OLSR 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
10	Performance Metrics 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
11	Experimental Results
12	Conclusions 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
13	Future Work 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