Reading for Lecture Oct 7

A High Throughput Path Metric for Multi-Hop Wireless Routing

The Expected Transmission Count metric (ETX) minimizes the expected number of packet transmissions (including retransmissions) requires to successfully deliver a packet to the ultimate destination, thus by which finds high-throughput paths on multi-hop wireless network. The ETX is used as a metric for DSDV and DSR protocols.

The commonly used metric by existing ad-hoc routing protocols is minimum hop-count often implicitly assumes that the links either work well or don’t work at all, which is true for wired networks but not for wireless networks. The 802.11b ACK mechanism resends lost packets locally, thus making all the worst 802.11b links appear loss-free, however the retransmissions reduce path throughput and interfere with other traffics. The ETX find paths with the fewest expected number of transmissions.

The best path between each pair of nodes was found by sending data along ten potential best paths, one at a time, and selecting the path with the highest throughput. An offline routing algorithm is used to find potential best paths using as input measurement of per-link loss ratios and with a penalty to reflect the reduction in throughput caused by interference between successive hops of multi-hop paths.

The ETX metric must account for the following issues: 1) the wide range of link loss ratios; 2) the existence of links with asymmetric loss ratio; 3) the interference between successive hops of multi-hop paths. The ETX of a link is calculated from the forward delivery ratio df, the probability that a data packet successfully arrives at the recipient, and the reverse delivery ratio dr, the probability that the ACK packet is successfully received. Thus the expected probability that a transmission is successful is df x dr then ETX = 1/ df x dr.

These delivery ratios are measured using dedicated link probe packets. Each node broadcasts link probes of a fixed size at an average period τ with jitter. Each node remembers the probes it receives in during the last w seconds, thus allowing it to calculate the delivery ratio from the sender at any time t as r(t) = count(t – w, t)/(w/τ).

The ETX only makes sense for networks with local link-layer retransmission and furthermore, ETX assumes that radios have a fixed transmit power level. ETX loss measurements do not reflect how busy a link. And 802.11b can be unfair under high load causing a node might never be able to send its probes, causing its neighbors to believe that reverse delivery ratio had become zero.

A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols

In wireless mobile ad-hoc network, each mobile node operates not only as a host but also as a router forwarding packets for other mobile nodes in the network that may not in direct wireless transmission range of each other. The ns-2 network simulator is extended to include node mobility, a realistic physical layer, radio network interfaces and IEEE802.11 MAC protocol using DCF.

The DSDV protocol requires each node to periodically broadcast routing updates. Each DSDV node maintains a routing table listing the next hop for each reachable destination. DSDV tags each route with a sequence number and considers a route R more favorable than R’ if R has a greater sequence number, or if the two routes have equal sequence numbers but R has a lower metric.

The TORA protocol is designed to discover routes on demand provide multiple routes to a destination, establish routes quickly, and minimize communication overhead by localizing algorithmic reaction to topological changes when possible. The mechanism of TORA resembles water flowing downhill towards a destination node through a network of tubes that models the routing state of the real network.

The DSR protocol consists of two mechanisms: route discovery and route maintenance. The route discovery mechanism discovers routes when a node S wishing to send a packet to node D and obtains a new route to D. The route maintenance operates by which a source S detects if the network topology has changed such that it can no longer use its route to the destination D because some two nodes in its route have moved out of each other’s range, thus disconnected. The AODV is essentially a combination of both DSR and DSDV.

The overall goal of the experiments was to measure the ability of the routing protocols to react to network topology change while continuing to successfully deliver data packets to the destination. The simulation of 50 wireless nodes forming an ad hoc network moving about over a rectangular 1500m x 100m flat space during 900 seconds. The sources send data at a constant bit rate. The metrics for comparing protocols are packet delivery ratio, routing overhead and path optimality.
The experiment tries to use sources with constant bit rate which is of often not realistic. Non-constant bit rate connections often cause more problems for wireless environment since the network cannot frequently check the status of routes in the network as well as discover new network topology.