MECH 590: Directed Studies with Dr. Gerard McLean
B. Cameron Lesiuk, B. Eng.
December 16, 1998
Department of Mechanical Engineering
University of Victoria, Victoria, BC, Canada
Preamble:
This report was written in partial fulfillment of a MECH 590 Directed Studie s course with my supervisor, Dr. Ged McLean. This report was written in Frame Bu ilder and later translated into HTML form.
Click here to return to my home page.
A packet-level network simulator was developed to simulate the operation of DSR. Investigations previously done by Johnson were repeated using this simulator, and a comparrison of the results made. In the end, due to time constraints, only a small subset of Johnson’s original simulations were repeated and the results analyzed.
Figure 2.1: A packet being source routed from node 9 to node 5.
Figure
3.1: An ad hoc network illustrating use of the route cache.
Figure
3.2: Node 4 notices the route can be shortened.
Figure
4.1: Comparison of simulation results to Johnson [3].
Figure
4.2: Network topology resulting in more than three-hop routes.
This report is divided into three main components. An overview of ad hoc networks of mobile hosts is presented in the remainder of this introduction. A description of the Dynamic Source Routing protocol is presented in Sections 2 and 3. Finally, a description of the network simulator, simulation environment, and simulation results with commentary are provided in Section 4.
Figure 1.1 illustrates an ad hoc network with four wireless mobile nodes. In this example, each node is within transmission range of two neighboring nodes (indicated by the circles around each node), but is out of range of a third. If two nodes which are not within range of each other wish to exchange information, they must enlist the aid of intermediary nodes to forward information on their behalf. In Figure 1.1, if node 1 sends a packet to node 4, it must send it first to node 2 (or 3). Node 2 can then forward the packet on to node 4.
Each time a packet is transmitted to a neighboring node, it is said to have made a hop. In the above example, when node 1 sends a packet to node 4, the packet makes two hops: first from node 1 to node 2, and second from node 2 to node 4.
Sometimes in a network of mobile nodes, parts of the network may become isolated and separate. This effect is called network partitioning and is illustrated in Figure 1.2. When network partitioning occurs, nodes can continue to exchange information within the same partition, but it is impossible for information to flow between partitions.
Figure 1.2: Ad hoc network partitioned into two separate
networks.
Another situation found in wireless networks is illustrated in Figure 1.3. In this example, node 1 has a large enough range to transmit packets directly to node 3. However, node 3 has a much smaller range and must enlist the help of node 2 in order to return packets to node 1. This makes the link between node 1 and node 3 appear as a one-way or unidirectional link.
In summary, routing protocols for ad hoc networks face several challenges. Ad hoc networks require multi-hop forwarding to facilitate information exchange. Wireless links are nonuniform and can cause unidirectional links. By their very nature, mobile nodes tend to "wander around", changing their network location and link status on a regular basis, sometimes partitioning the network. Furthermore, new nodes may unexpectedly join the network or existing nodes may leave or be turned off. It is the goal of ad hoc routing protocols to provide network connectivity despite these challenges.
Figure 2.1: A packet being source routed from node 9 to node
5.
DSR is broken down into three functional components: routing, route discovery and route maintenance. Routing has already been described above and is relatively trivial. Route discovery is the mechanism by which a node wishing to send a packet to a destination obtains a path to the destination. Route maintenance is the mechanism by which a node detects a break in its source route and obtains a corrected route.
To prevent route request packets from being broadcast around in loops, nodes will not forward route requests if they are already listed as a hop in the route. To reduce congestion and duplication, each node maintains a small cache of recently received route request < sequence numbers / source address > pairs and does not propagate copies of a route request packet after the first.
All source routes learned by a node are kept (memory permitting) in a route cache, which is used to further reduce the cost of route discovery. A node may learn of routes from virtually any packet the node forwards or overhears. When a node wishes to send a packet, it examines its own route cache and performs route discovery only if no suitable source route is found.
Further, when a node receives a route request for which it has a route in its cache, it does not propagate the route request, but instead returns a route reply to the source node. The route reply contains the full concatenation of the route from the source (from the request packet), and the route leading to the destination (from the route cache).
If a node along the path of a packet detects an error, the node returns a route error packet to the sender. The route error packet contains the address of the node at both ends of the hop in error. When a route error packet is received or overheard, the hop in error is removed from any route caches; all routes which contain this hop must be truncated at that point.
There are many methods of returning a route error packet to the sender. The easiest of these, which is only applicable in networks which only use bidirectional links, is to simply reverse the route contained in the packet from the original node. If unidirectional links are used in the network, the DSR protocol in [1] presents several alternative methods of returning route error packets to the sender.
Route maintenance can also be performed using end-to-end acknowledgments rather than the hop-by-hop acknowledgments described above. As long as some route exists by which the two end nodes can communicate, route maintenance is possible. In this case, existing transport or application level replies or acknowledgments, or explicitly requested network level acknowledgments, may be used to indicate the status of the node’s route to the other node.
Figure 3.1: An ad hoc network illustrating use of the route
cache.
Since nodes 2 and 3 are on the route to 4, node 1 also learns the route to both of these nodes from its route discovery for 4. If 1 later performs a route discovery and learns the route to 6 through 2 and 3, it can represent this in its route cache with the addition of the single new hop from 3 to 6. Consequently, if node 1 learns it can reach 3 in a single hop, it can use this new route to shorten both routes leading to 4 and 6 in its route cache.
A node can add entries to its route cache any time it learns a new route. In particular, when a node forwards a data packet as an intermediate hop in the packet’s path, the node is able to observe the entire route in the packet. Thus, for example, when node 2 forwards packets from node 1 to 4, node 2 can add the route information from that packet to its own route cache. In this case, node 2 learns of routes to node 1, 3, and 4. If a node forwards a route request or reply packet, it can also add the route information from the route record in the packet to its own cache. Finally, since all wireless network transmissions are inherently broadcast, a node may be able to configure its network interface into promiscuous receive mode, and can then add to its route cache the route information from any packet it overhears.
A node may use its route cache to avoid propagating a route request packet received from another node. Suppose a node receives a route request packet for a target for which the node has a cached source route entry; the node may append this cached route to the accumulated route record in the packet, and may return this route in a route reply packet to the initiator without propagating (re-broadcasting) the route request.
An improvement to this method is possible if nodes operate their network interfaces in promiscuous receive mode. Suppose somewhere in the forwarding of a packet, mobile node 2 transmits a packet to node 3, with node 4 being the next hop after 3 in the route in the packet, as illustrated in Figure 3.2. If 4 receives this packet, it can examine the packet header to see that the packet reached it from 2 in one hop rather than two as intended by the route in the packet. In this case, 4 may infer the route may be shortened to exclude the intermediate hop through 3. Node 4 then sends an unsolicited route reply packet to the original sender of the packet, informing it that it can now reach 4 in one hop from 2. As with other route reply packets, other nodes which receive this route reply may also incorporate this change into their route caches.
Another optimization possible to improve the handling of errors is to use promiscuous receive mode to allow nodes to eavesdrop on route error packets being sent to other nodes. Since a route error packet names both ends of the route hop causing the error, any node receiving the error packet can update its route cache to reflect the fact that the two nodes indicated in the packet can no longer directly communicate. A node receiving a route error packet can simply search its route cache for any routes using this hop, and for each such route found, the route is truncated at this hop. All nodes on the route before this hop are still reachable on this route, but subsequent nodes are not.
In [3], Johnson describes their simulation environment, assumptions, and results. One of the difficulties in analyzing and objectively comparing ad hoc routing protocols is the complete lack of standard metrics. Therefore, to facilitate a meaningful comparison of results to those found in the literature, the simulator, assumptions, and simulation scenarios of Johnson were to be repeated. This not only facilitates confirmation of results from this investigation, but would also serve to support Johnson’s findings.
Section 4.1 describes the simulation environment developed and the assumptions made. Section 4.2 presents the results of simulations and discusses them in comparison to Johnson’s work.
The basic simulation parameters were chosen to model an ad hoc network consisting of a collection of mobile nodes moving around in a medium-sized room. The area in which the nodes move is square, 9 meters on a side. Each node moves with a velocity between 0.3 and 0.7 meters per second (somewhere between a slow walk and a quick stroll), and each transceiver has a range of 3 meters. These parameters could represent, for example, a group of nodes using diffuse infrared transceivers, or since the parameters are related and can be scaled linearly, they could also represent a number of cars with radio-equipped portables driving (very quickly) around an area of 1 square kilometer.
Each node is initially placed at a random position within the simulation area. As the simulation progresses, each node pauses at its current location for a period called the pause time. After this pause time has expired, each node randomly chooses a new location to move to and a velocity between 0.3 and 0.7 meters per second at which to move there. Each node continues this behavior, alternately pausing and moving to a new location, for the duration of the simulation. Using this model, nodes appear to wander through the room with their restlessness determined by the pause time constant.
Whenever a node transmits a packet, some method must be used to determine which of the surrounding nodes will receive a copy of the packet. While the simulation’s transmission model is simple, it still estimates the basic performance of a wireless medium with a collision-avoiding link layer protocol (though collisions are still possible due to node movement). Furthermore, nodes are given relatively equal access to the shared bandwidth and small packet transmission delays (jitter) are introduced to avoid synchronization problems.
In the simulation, each node can be the originator of up to three simultaneous conversations with other nodes, with the other participant in the conversation chosen randomly from among the other nodes. While a node is the initiator of less than three conversations, it initiates a new conversation with a randomly chosen partner after an average period of 15 seconds. Each conversation lasts for a predetermined number of packets, the number being chosen at random from between 500 and 1500 packets.
During a conversation, packets are sent to the partner at a random rate between 2 and 5 packets per second. Packet lengths are chosen with a distribution such that 70% of the packets are long packets (1000 bytes) and the remainder are short packets (32 bytes). On top of this payload, protocol overhead adds to the overall packet size and varies according to protocol requirements (such as the length of the source route). To give the appearance of a two way conversation, the partner sends a return packet back to the originator for every packet it receives. These return packets have the same length distribution as the originator’s packets.
Packet transmission in the simulator is based on a network using link level acknowledgments at each hop, although acknowledgments are not provided for broadcast packets. Transmissions to a node that is out of range always fail while transmissions to a node in range fail with a probability of 5%. The data link layer in the simulator will make up to 2 retransmission attempts if the first transmission fails. Each time a sender transmits a packet, the other nodes in range of the sender each have a 95% chance of overhearing the packet. The bandwidth for transmitting data is 100 KBytes per second.
There are a number of parameters such as timeouts and holdoff periods which must be configured within the protocol. The values used in the simulator are shown in Table 1. As far as the author can tell, these values are comparable to those used in [3].
| Parameter | Value |
|---|---|
| Nonpropagating (1-hop) route request time out | 100 ms |
| Route request (multi-hop) time out | 500 ms |
| Maximum route request period (after backoff) | 10 s |
| Packet forwarding jitter | 1-2 ms |
Nonpropagating route request time out: When a node initiates route discovery, the first packet transmitted is a route request packet with a hop limit of 1. This queries the local neighbors of the node and saves the expense of a full network-wide route request should the destination be found to be a neighbor. The nonpropagating route request time out is the time the initiating node will wait, after transmission of the limited route request packet, before a multi-hop route request packet is transmitted.
Route request time out: If, after a route request packet is transmitted, no reply is received in this amount of time, the node will retransmit the route request packet. Note, however, to avoid excessive congestion in the event of a network partition, each route request timeout becomes progressively longer (backoff) to a maximum limit.
Maximum route request period: Assuming a node performing route discovery consistently receives no route reply packets, it will backoff from retransmitting the route request packet. This value is the maximum timeout before another route request packet is sent; the node will not backoff beyond this value.
Packet forwarding jitter: When a node receives a packet which it is to be retransmitted to either another hop in the network or simply rebroadcast, it delays transmission of the packet this random time to introduce artificial jitter. This avoids transmission synchronization in the simulation which can result in uniform transmission patterns and skewed results.
The simulator does not attempt to model channel contention. Given a suitable data link layer protocol such as GAMA-PS [7], the chance of data being lost to collision during periods of channel contention grows small, although at the expense of more delay in packet sending and receipt as each node waits for its turn to use the bandwidth. Therefore, while the model in this investigation should accurately show the number of packets that will be received, the latency of any individual packet exchange cannot be determined.
The simulator also does not model unidirectional links. This choice is necessarily implied by the requirement of implementing the DSR protocol on top of a data link layer with link level acknowledgments.
A final minor limitation of the simulator is the environment is assumed to be devoid of obstacles to transmission or movement. Further, transmission failures are assumed to be uniformly distributed and independent. This does not take into account spatially localized failures due to noise or interference such as from microwave ovens (for radio) or windows and reflections (for infrared).
It was the aim of this investigation to repeat these same simulation executions using an independently constructed simulator. Unfortunately, this goal has proved unattainable at this time. The primary cause was the extended amount of time dedicated to the construction of the simulator itself. Coding and validation of the separate application and physical layers, followed by the complete implementation of the DSR protocol required substantially more time than initially expected. Furthermore, the complexity of the task of implementing a full blown routing protocol was also more than expected. Finally, it was very apparent the simulation had to run fault-free (or at least fault-tolerant) so that the simulator did not crash halfway through a simulation; a regular application can be restarted where it left off, but a simulation has to start all over (I will include state preservation capabilities in future network simulators). Thus the time spent debugging the simulator was also increased. These simulator production problems left little time in which actual simulations could be performed.
The computation time required to run simulations presented the second major hurdle. It was found the simulator required approximately two seconds of execution time to execute one second of simulated time per node. Thus a simulation with 6 nodes requires approximately 12 seconds of execution time for every 1 second of simulation time. For the simulations to match those of Johnson in [3], simulation execution times of between 12 and 48 hours or more per scenario would be required. To duplicate the entire suite of scenarios as performed by Johnson, nearly four straight computing months would be required (assuming the simulator never crashed). On the limited computing facilities of the author (two somewhat-obsolete Linux machines) this proved to be a limiting factor in the size and diversity of the simulations which could be performed. In the end, only seven simulations were completed in the time available for this project. Five tests were run with 6 nodes, for 1000 seconds (unlike Johnson’s 4000). Two tests were run with 12 nodes, one for 158 seconds and another for 762 seconds.
These limited simulations could still be analyzed and compared with the findings of Johnson, albeit with little statistical validity. These comparisons are made in Figure 4.1. Note Johnson’s simulation results are the average response of 20 simulations for each scenario, whereas Lesiuk’s results are single simulation results.
Figure 4.1: Comparison of simulation results to Johnson [3].
The discrepancy between the simulation results is considerable. It should be noted all of Johnson’s simulations ran for a full 4000 seconds, whereas the simulations in this investigation ran for 1000 (or less, in the case of the 12-node simulations). Consequently, anomalous activity at the beginning of the simulation is amplified. Without more controlled conditions, the effects of the unimplemented optimizations in the DSR protocol cannot be factored out either. Finally, the 6-node simulations represent a worst-case scenario of all of the simulations due to the frequent network partitioning, especially during simulations with high node mobility.
An interesting and unexpected result of the simulations showed, in both 6 and 12-node simulations, networks with lower pause time effectively became unable to route any packets requiring more than one hop. Unfortunately, Johnson does not provide hop count statistics to support this claim. However, it appears as though, for high node mobility, the routing protocol may operate equivalently if all packets were simply broadcast to the first-hop neighbors, with no multi-hop propagation of packets.
After construction of the network simulator, and intimate analysis of DSR and the simulation scenarios, the entire simulation context was found to be lacking. First of all, the simulation’s physical dimensions are very small. With a node transmission radius of 3 meters and a square environment with 9 meters a side, the theoretical maximum number of simultaneous transmissions is 4. For practical purposes, this is generally limited to only one or two nodes being able to transmit at a time.
Secondly, the only way for a route’s hop count to go above 3 in this environment is for simulations where nodes happen to form into long thin networks weaving around the environment, as illustrated in Figure 4.2. In this event, network partitions are more likely to form than long network chains. Although hop counts as long as 7 were observed in a simulation with 12 nodes, hop counts over 3 represented less than 6% of all routes used. The vast majority (68%) of routes consisted of only 1 hop. This is in start contrast to the simulations by Broch et al [2] where hop counts of 1, 2, and 3 hops formed 32%, 24%, and 19% of routes respectively.
.
Figure 4.2: Network topology resulting in more than three-hop
routes.
A packet layer network simulator was created according to the model described by Johnson in [3]. Originally, all of Johnson’s simulations were planned to be repeated. However, time constraints and computing facilities permitted only 7 token simulations to be performed.
The investigations performed in this exercise have effectively provided both insight and experience into the development, implementation, operation and limitations of the DSR protocol. Experience was also gained in the development and analysis of a network simulator.
[2] Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, Jorjeta Jetcheva, A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols, Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom ‘98), October 25, 1998.
[3] David Johnson, Dynamic Source Routing in Ad Hoc Wireless Networks, Mobile Computing, Kluwer Academic Publishers, pp 153-181, 1996.
[4] David B. Johnson, Routing in Ad Hoc Networks of Mobile Hosts, Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, pp 158-163, December, 1994.
[5] David Johnsom, David Maltz, Protocols for Adaptive Wireless and Mobile Networking, IEEE Personal Communications, Volume 3 Issue 1, February, 1996.
[6] B. Cameron Lesiuk, Routing in Ad Hoc Networks of Mobile Hosts, Mech590 Report, University of Victoria, December 2, 1998.
[7] Andrew Muir, J. J. Garcia-Luna-Aceves, An Efficient Packet Sensing MAC protocol for wireless networks, Mobile Networks and Applications, Vol 3, pp 221-234, 1998.
ad hoc For the scope of this paper, ad hoc means unplanned and/or established for one specific reason or occasion.
ad hoc network A network which is formed without a priori knowledge or planning. Nodes belonging to an ad hoc network do not share any central authority or support structure.
broadcast A packet which is broadcast is received by every and all nodes within transmission range of the sender.
hop Each time a packet is transmitted, it is said to have performed one hop. Multi-hop networks require nodes in the network to enlist the aid of neighboring nodes to forward packets towards a destination node.
link A communication channel by which a node can send packets to another node.
loop Some protocols, when they have not converged, can set up routing loops. A loop is formed when two nodes do not agree on the shortest path to a destination. For example, suppose node A routes a packet to node B, but B subsequently routes the packet back to A. In this example, the packet will be routed between nodes A and B ad infinitum, or until their routing logic is synchronized and the routing protocol converges.
mobile node A node which is willing and able to physically move location, resulting in network topology changes.
partition Sometimes, in an ad hoc network, the network can break apart and groups of nodes can be out of range of other groups of nodes. When this happens, the network is said to be partitioned. Each group is called a network partition.
router A node willing to forward and route packets on behalf of other nodes. In ad hoc networks, typically every node acts as a router.
source routing In source routing, a node wishing to send a node will completely describe the path packets should take to a destination. In some networks, such as ATM, source routing is accomplished based on a complete knowledge of the network topology. In ad hoc networks, source routing usually requires special route discovery procedures.
topology The graph representing node positions and their links to other nodes. The topology is said to change when links change state (are either created or destroyed) or nodes change state (are appear, disappear, or move).
