Supervisor: Kaisa Sere

7SIMULATION

A simulator should provide information about how the protocol performs under varying strain. The strain increases when the amount of nodes, network activity and movement of nodes increases. Many ad hoc routing protocols are designed so that increase of inactive nodes affects overall performance only marginally (reactive) in contrast to proactive protocols that maintain a route to every destination. If, on the other hand, new nodes are active, sending messages, then greater strain will be put on the network. There is also an upside to having more nodes in the network and that is improved connectivity. The second variable is a natural one, when network activity increases (more messages are sent) the routers will have to work harder to keep up. The former two variables are such that ad hoc and static networks have in common, the third one they do not have in common which is node movement. In ad hoc networks node movement is of course the main thing to resolve. In TRP node movement generates strain because old entries in routing tables have to be updated by sending new queries. As the most interesting factor in ad hoc networks is mobility, the results will be portrayed as a function of the speed. The results should at least show control message overhead, amount of packets delivered and route discovery latency during increasing speeds of nodes. Data messages (non-overhead) will be sent to randomly chosen nodes, which will result in route query (control overhead) if a route is not known, but only the data messages delivery rate will be recorded in this test. The opposite, is of course recorded in control message tests, that is, how many route queries has to be sent during increasing speeds.

7.1 A Technical Description of the Protocol Simulator

The simulator of TRP was implemented to have layered architecture, with a MAC layer and network layer. The MAC layer functions are not implemented in a realistic way (thus called Virtual MAC), but are rather a way to provide services for the routing and forwarding algorithm. These algorithms on the other hand are very realistic. All the nodes are represented by processes that cannot communicate in any other way but sockets. In the simulator, every piece of information that one node learns about another has to be exchanged like real protocols by informing the neighbors. It might seem like it would suffice to use the MAC-level information about the neighbors, but this is not always the case. Since TRP stores information about a neighbor’s treeID and depth among other things these should be informed as well. In order to minimize the amount of such messages, these are only sent when a change in some node’s state occur (i.e. depth, treeID or list of children). Thus, an entry concerning a neighbor is considered to be valid as long as neighbors remain within range, which is confirmed by the MAC-layer.

7.1.1The Virtual MAC Layer

The Virtual Medium Access Layer (VMAC) is something that was created to emulate a layer-2 MAC protocol. The only thing that the rest of the simulator expects from it, is to provide a lower-level addressing scheme with globally unique addresses and to keep the network protocol informed of which nodes are within radio contact of the node itself. The VMAC is simulated by processes that listen to a given port. Every process also "knows" its position in a coordinate system. At start-up and each time a process or node (which the process represents) moves, it will send its current coordinates to all other nodes which calculate the distance between them in order to simulate the radio range. At this point both will make note of what has happened and record the address of the other node in a table. When one moves away from the other this will be detected by the non-moving node, which tells the moving node that radio contact is lost, upon which both delete the entry in the neighbor table. In a real implementation the MAC-layer would have some sort of API to retrieve the information of neighboring nodes, but in this simulator the neighbor table is made available to the routing algorithm.

Given the time-critical properties of a routing protocol, UDP was chosen for communication between processes and a message informing movement will be sent to all possible ports where a process could reside (this was done to simplify the programming job). In fact the simulator could of course have been designed to use message passing or shared memory, even the whole layer structure could have been omitted. The reason why this was not done, was because we wanted to simulate a protocol a realistically as possible, having components that real protocols have. Another reason for the chosen structure was to make it as easy as possible to convert the simulator to a real protocol if the need for that arises. So, for the purposes of the simulator, the port that a particular process handles is the same as its MAC address (and a constant added to that, the routing layer uses another port) and all the UDP packets needed for calculating routes are sent to these.
At this layer there is no need for a timer that indicates when an entry in the neighbor table expires since a message will be received when a distance is too long. This would not be possible in reality but the focus of the simulation is on the network layer and not MAC, thus this simplification at this layer was allowed.

7.1.2The Network Layer

As mentioned before the routing messages are sent on a different port than MAC messages. Therefore, this port is used for the data and control messages. The same program module is used to dispatch routing control messages and data messages. The module is a thread that blocks if no messages arrive and loops as fast as messages arrive when neighbors are transmitting.

The simulator does also contain another important thread, namely the routing thread. Since in TRP routing is the equivalent to tree construction, this thread or algorithm decides how the node should behave in different situations. The message dispatch thread and the routing thread work together to make the node behave correctly. This is achieved by letting the dispatch thread set the state of global variables so that the routing thread can react to new information about the tree. For instance the dispatch thread might receive a hello message saying that a neighbor’s depth has changed and that it is not the shallowest neighbor anymore. This will be recorded in a table that is used for storing information about the neighbors, similar the MAC neighbor table, but more details are included, like the depth, treeID and state (is it a root). Since the routing thread evaluates the shallowest neighbor frequently it will decide to associate itself with another neighbor or if that is not possible, just increase its own depth according to its parent. Another scenario could be that the preferred neighbor’s treeID changes as the root of the tree includes itself with another tree. At this point, since the root’s state changes, it will send a hello message saying that this tree has a new ID. This will cause every child of the old root to do the same, thus spreading the news of a new root of the tree.
Before routing and forwarding decisions are made, the MAC information is checked that every node in the detailed neighbor table is in fact still a neighbor. If not, the node is just expunged making it impossible to take the node into account in the next calculation. This arrangement actually eliminated the need for many timers that would expire whenever a hello was not received on time and also reduces the amount of messages that has to be sent because unchanged information is never sent.
The updates are also dispatched by the same thread and put in a table of their own. This update table contains updates from all children and is used to assemble the node’s own update. When this new update is assembled it is checked against the old one. If they differ in any way, it is sent to the preferred neighbor (parent) which will go through the same process. These entries in the update table are also valid as long as the child that sent it remains a neighbor or an explicit un-association message is received.
The RQMs are also stored in a table, for checking purposes when a node receives a RQM that should be forwarded. Before forwarding the message, the ID, originator and hops_traversed fields are compared to every message in the table. If the message has been seen and its hops_traversed value is greater then it is not forwarded. Because the hops_traversed field is limited, the count will at some point roll over. This brings us to the only timer that TRP has, that ages the recorded message. It must "age out" the messages before a roll over has happened at another node. If this is not taken care of properly, an unseen message will falsely dropped as explained in section 5.4.1.

Download 298.62 Kb.

Share with your friends: