Implementing Network Level Quality of Service for
Dynamic Source Routing
Project Report
15-824: Mobile and Wireless Networking
Tung Fai Chan, Annie Cheng, Howard Mak, Igor Pevac
Carnegie Mellon University
{tungfai, ahcheng, hmak, ipevac}@andrew.cmu.edu
Abstract
The DSR protocol at present time provides best effort service. An important addition to it would be implementation of quality of service. In particular, we choose on providing a network level quality of service. At this level, the goal specifically is preservation of scarce resources. For our study the resource we focused on was battery power. Starting with the assumption that avoiding routes with nodes of low battery power can shift the burden of traffic to those with abundant source of power, we modified the original DSR protocol to do exactly that. We examined the performance using two models of battery power consumption. The results that we obtain is the idle and receive states dominate the use of battery power. Even with minimizing sending through bottleneck resources, does not generate enough change to be effective.
1. Introduction
An ad hoc network is a collection of wireless mobile hosts forming a temporary network without the aid of any established infrastructure or centralized administration [1]. Dynamic Source Routing (DSR) [1][2] is a routing protocol designed for such networks. Although the original DSR did not offer any provisions for Quality of Service (QoS) guarantees, extensions have been suggested. Our project focuses on implementing QoS services for DSR in the ns-2 simulator environment. The quality of service provided improves the network state. In particular there is a preservation of scarce resources. As a basis for comparison, regular DSR will be simulated with the same simulation inputs.
Specific network mechanisms must be implemented in order to provide QoS support in a DSR network. The DSR IETF draft [2] suggests the use of path and flow states as such items. The path-state is a fundamental unit of routing information. It consists of the information needed to route packets along a path (i.e. all the hops of a source route) as well as information about the carrying capacity of a path. Once a path-state is established, DSR packet headers no longer need to explicitly specify the variable length source route, but can instead use refer to the path-state to reduce packet overhead.
In addition to the reduction of packet overhead, the path metrics mechanism was implemented as well [2]. Due to the added information about the state of paths our improvements to DSR are able to discriminate against paths that contain nodes of low power, while preferring the paths with nodes of abundant battery power. Multiple formulas are used for assigning metric to a path, each with its benefits and shortcomings.
Upon final analysis of the simulation results, we find that DSR with QoS makes a slight difference in overall battery preservation, but is overshadowed by the sheer impact of idle and receiving times.
.
2. Design
In this section, we describe the structural and protocol level changes necessary to implement a mechanism for the source node to obtain metric information of a path and methods to wisely select an optimal path to use based on information observed Since we uses battery power as path metric, we also describe the algorithm on battery measurement in the MAC layer here.
2.1 Supporting Data Structures
In order to facilitate network level QoS services, a route selection protocol needs more knowledge of its surrounding environment than simple routing paths to make better route selection. In our simulation, we use battery power as metric for path selection. We measure the metric information along with path using the packet option structure, and we stored the final metric measurement of each path using the path and metric storages defined in each node.
2.1.1 Packet Options
In our modified version of DSR, we have implemented two packet header options, Identifier and Path-Metric option, as suggested in [2]. Identifier Option is used to reduce the overhead of carrying source route in each outgoing packet. Path-Metric option is used to carry metrics information. Both options are processed in hop by hop basis. Identifier option has three fields: option type, option length, and path identifier. Option type and option length fields store the same information as specified in the Identifier Option Section in [2]. The source address and path identifier combination forms a unique key referring to a specific route from source to destination node. Path Metrics has four fields, option types, option length, type, and metrics. Option type and option length fields store the same information as specified in the Path-Metric Section in [2]. Type field is used to indicate whether the option is a metric measurement or a metric reply. Metrics field stores metrics type and data value [2].
2.1.2 Path and Metric Storages
In addition, we have defined three different path and metric storage structures in each node. They are Path ID Cache, Metric Cache, and Path ID Routing Table. In the Path ID Cache, each source node stores information regarding the currently selected path to reach a destination node. Each Path ID Cache entry is unique by its destination. The protocol ensures only one path to a destination to be stored in Path ID Cache at any time instance. Alternatively, all available routes to the destination that are found during the route discovery phase, along with the metric measurement associated with each route, are stored in the Metric Cache in each source node.
Lastly, in order to implement route optimization feature and eliminate the need to carry source route in each packet header, Path ID Routing Table is implemented in each intermediate node. Path ID Routing Table stores previous hop and next hop of the route identified uniquely by source and path identifier (PathID) pair.
2.2 Protocol Modification
The existing DSR does not provide sufficient framework to allow path metric measurement. Therefore, we implement three extensions upon existing DSR protocol. They are piggy-backing path measurement with route discovery, path optimization, and path measurement
2.2.1 Route Discovery
Route discovery is a mechanism used by DSR to dynamically discover routes to a destination node through the MAC layer broadcast. In the modified version, when the source node wants to send out a packet but does not have a route in its cache to reach the destination, the source node attaches the Path-Metric option onto the route discovery packet header before broadcasting the packet to the neighboring nodes. Upon receiving a packet with Path-Metric option attached, the intermediate node measures its metrics locally and updates the measurement in the packet header as the packet gets propagated to the destination node. When a node receives a route discovery packet and is able to find a route to the specified destination in its cache, the route will be retrieved from the cache. However, differ from “Reply from Cache” mechanism stated in [2], instead of sending the Route Reply directly back to the source node, the intermediate node forward the route discovery as an unicast packet along the rest of the nodes specified in the path. This modification is made so that the metrics can be updated or measured along the rest of the nodes in the path. When the destination node receives the route discovery packet, the route is reversed and placed in the newly created route reply packet as the original DSR. In addition, the metrics measured along the path from the source node is also inserted with the reversed route and being sent back to the source.
To further optimize the protocol and fully make use of the battery information observed, the path metrics along with the reversed path back to the source will be inserted into the Metric Cache at the destination node as a route to the source node. Similar to the destination node, during the ongoing Route Discovery process, the intermediate node also inserts the reverse route and the metric measured so fart into its cache as a route from itself to the source node.
2.2.2 Path Optimization
As mentioned in [2], the primary goal of path optimization is to reduce the overhead generated by having to carry the full source route in the data packet header. There are two mechanisms to handle such optimization in the source node.
First, when there is no specific route associated with the destination requested, a route will be selected from the Metric Cache using the Route Select Method described in section 2.3. The selected route along with a uniquely assigned PathID will be inserted into the packet header and send out to the next hop according to the source route. The intermediate node receiving the full route with the identifier attached will be added into the PID Routing table as <source, PathID, previous node, next node> pair. Second, when there is PathID already associated with the route to the destination node, the packet will be forward to the next hop along with the attached PathID in the header. The intermediate node receiving only the PathID in the header will look up the next hop for the route in its PathID Routing Table and forward the packet to the next node. If the identifier cannot be found in the Route Table, the packet will be redirected back to the source node using the previous hop information stored in the Routing Table. Upon receiving the redirected packet, the source node will retransmit the packet with full route and path identifier such that the intermediate nodes can update their PathID Routing Table accordingly. Path Metric Refreshment Reply and Route Error packet both make use of the previous hop information associated with PathID and then return to the source node.
We have made a trade-off here as we only insert previous and next node in the Routing Table of intermediate nodes instead of the full route. The advantage is improving storage efficiency by eliminating redundant data in intermediate nodes. However, one drawback is whenever PathID is not found in a node, the packet has to re-route all the way back to source and prompt for full route. On the contrary, if full route is stored inside the routing table of each node along the path, any node can retransmit the redirected packet with full route before it reaches the source. Here, we clearly trade the bandwidth for storage space because from simulation, such error is infrequent.
2.2.3 Path Measurement
Path Measurement mechanism is done by attaching the Path Metric option into the packet header. When the intermediate node detects the path measurement option in the header, the metric is measured and the accumulated calculation of metric formula will be stored back to the packet header. There are three metric formulas that express the different characteristic of a path. They are minimum, product, and average-derivation.
Selecting the minimum as the measure for the route is very effective in identifying the bottleneck. However it fails to compare two routes with the same minimum. Product on the other hand takes into account all the nodes along the path, including a bias for paths of shorter length. Average minus the mean deviation likewise takes into account the whole path. The effect of bottle necks if felt in both areas. It will bring the average down and also the mean deviation will increase further bringing down the measure.
To find out the battery level of the node that has minimum battery level in a path, the source node initialize the value in the packet header to maximum, which represents 100% battery power. Then, the intermediate node compares its own battery level against the battery level indicated in the packet header. If the intermediate node has lower battery level than the battery level indicated in the packet header, the intermediate node will replace the value in the packet header with is own value. The value indicated in the packet header is the lowest battery level that the packet has encountered so far. When the packet arrives at the destination, the minimum battery level along the path is found.
To find out the product of battery power for all nodes in the path, the source node initialize the value in the packet header to 1. Then, the intermediate node multiplies its own battery level with the battery level indicated in the packet header and store the product back into the packet header before forwarding it on to the next node. When the packet arrives at the destination, the product of all battery level along the path is found.
To find out the average-derivation of battery power for all nodes in the path, the source node initialize the average value to 1, and deviation value to 0 in the packet header. Then, the following formulas are used for the intermediate nodes to calculate both average and deviation:
Hop count = C
Old Average = AVGold
Old Deviation = DEVold
Mean Deviation =
Current Power Level = Pcurr
[Formula 1]
Hop count = C
Old Average = AVGold
New Average = AVGnew
Current Power Level = Pcurr
[Formula 2]
When the packet arrives at the destination, the average-deviation is calculated as average minus deviation.
After the destination node detects the path measurement option in the header, it returns this accumulated measurement back to the source node as Measurement Reply, and the source node will update its cache accordingly. As mentioned in the previous section, to enhance optimization, destination node also updates its cache in order to keep most up-to-dated values for future usage.
2.3 Route Selection Method
Threshold is a minimum acceptable battery level for each node that our protocol aimed to maintain. In our simulation, a threshold can be set as criteria to select a route. The route selection method is used when a source node selects a route to reach the destination. In our protocol, the process of finding a path to destination can be stated in “good state” or “bad state. The process is in a “good state” when the selection method is able to find a path with battery level metric that is greater than the threshold defined. The process is in a “bad state” when the selection method is not able to find a path with battery level metric that is greater than the threshold defined. The “good state” and “bad state” mechanism is associated with each source and destination pair. A state diagram is shown in Figure 1.