DSDV
bibliography:
- references.bib
Destination-Sequenced Distanced-Vector (DSDV) is a table-driven routing protocol based on Bellman-Ford algorithm. The protocol is implemented as a term project and the objective of this report is to explain the implementation details and certain performance observations of the DSDV protocol. "DsdvService" class is designed to realize the DSDV protocol, and a network topology is created to validate the design together with observing the performance of the protocol. Stability of the routing tables and the network congestion are considered as main performance criteria of the protocol. The observations indicate that certain parameters and conditions should be selected carefully in order not to expose excessive network congestion and instability. After obtaining these results, the methods used to overcome the performance problem in implementation in accordance with the suggestions from the developers of the protocol, are explained in detail. The performance of the protocol was improved drastically after applying these methods.
An ad-hoc network is a wireless network which has a capability of communication between nodes without using a centralized access point or direct access to each node in the network. Routing protocols have been discovered to achieve the communication between ad-hoc nodes. These protocols rely on different approaches to the problem. The protocols which are proposed based on these approaches, exhibit different performance in terms of several criteria such as space complexity, network traffic, stability and so on. The puzzling question is which of these protocols should be choosen to implement an ad-hoc network.
One of the solutions to the problem is a table-driven approach. The table-driven protocols are proactive solutions which aim to keep up-to-date routing information in a table. Destination-Sequenced Distanced-Vector (DSDV) is one of the well-known protocols based on this approach. However, the performance of the protocol should be examined carefully before choosing the DSDV protocol to implement an ad-hoc network.
The performance criteria of a protocol or algorithm can be different since the application and purpose of the protocol may differ. This report mainly focuses on stability and network congestion as the primary performance criteria. DSDV protocol tries to maintain up-to-date routing information which results in excessive message traffic as the other table-driven protocols. Certain conditions and parameters should be handled carefully to overcome the negative result of the approach. These parameters and conditions are the key points of the implementation and discussed in the "Results and Discussions" section of the report.
In this section of the report, DSDV protocol is explained to understand the implementation of the protocol. As mentioned in the previous section, DSDV is a table-driven protocol aiming to keep up-to-date routing information in a table. Every node in the network should form a table which holds information about the network topology. Each entry in the table should contain information of "Destination Node", "Next Hop", "Metric" and "Sequence Number". Metric is the distance to the destination in terms of hop count, and the Sequence Number is the information received regarding the destination, as originally stamped by the destination [@perkins].
The DSDV protocol requires each mobile station to advertise, to each of its current neighbors, its own routing table [@perkins]. Since the DSDV is a proactive protocol, the routing tables should be advertised periodically to maintain consistency between nodes. However, any significant change in the network topology results in an immediate advertisement.
Two types of update messages can be employed: full dump and incremental. A full dump sends the entire routing table to the neighbors. Incremental updates are smaller and are used to transmit those entries from the routing table which have changed since the last full dump update. When a network is stable, incremental updates are forwarded and full dump messages are usually infrequent. On the other hand, full dumps would be more frequent in a fast-moving network [@elsevier]. Routes with more recent sequence numbers are always preferred as the basis for making forwarding decisions, but not necessarily advertised. Of the paths with the same sequence number, those with the smallest metric would be used [@perkins].
The protocol is implemented in a class named as "DsdvService" which inherits the "ComponentModel" class given in the base project. DsdvService uses the "Up" and "Down" connector types, and "send_up and "send_down" methods of the ComponentModel class to be suitable for a hierarchical layered architecture. The designed class overrides the "on_message_from_bottom" and "on_message_from_top" methods to process messages coming from higher and lower layer as well.
In the design, a timer thread class is implemented to be able to send messages periodically or schedule a send after specified number of seconds. In addition, update message types and the information at the columns of the routing table are defined in separate classes to ease process of the design. The DsdvService class can be divided into two logical parts: Data Plane, Control Plane. Each plane is explained separately in the following sections.
The protocol aims to maintain up-to-date routing information in a table as well as the other table-driven routing algorithms. Therefore, a self-routing table is initialized to keep up-to-date information at the initialization of the class. Moreover, instances of the timer thread class are defined in the initialization function for periodic update messages or scheduling a task. The first entry which carries the self-routing information is added to routing table at the initialization process as well. In Figure 1{reference-type="ref" reference="fig:initFunction"} initialization function of the DsdvService class is shown.
{#fig:initFunction}
The main objective of the data plane is to carry data packets between layers and forward the packets to one of the neighbors if necessary. The data plane of the DsdvService component receives data packets from link layer and hands them to the application layer if the destination address of the packet is component itself. If the packet destination address is not matched, the packet will be forwarded to one of the neighbors with the help of the link layer. The data plane of the DsdvService also receives data packets from application layer and forwards them to one the neighbors with the help of the link layer. The routing decision is made by control plane by using self-routing table.
The control plane of the DsdvService component implements the DSDV protocol. The component creates update messages and broadcasts the messages to the neighbors. The update messages are processed at this plane of the component as well. The control plane can be divided into two in a logical manner.
Update messages are created and broadcasted periodically with the help of a timer thread. However, in case of any change in the network topology, update messages are broadcasted without waiting the period. The messages are sent to the neighbors only, which means link layer broadcast method is used.
The period of the messages is not restricted in the protocol. In this design, the period is decided to be ten seconds, but it could be adapted according to the number of nodes. Moreover, changes in the topology are not directly broadcasted. To prevent congestion and fluctuations in the network, the immediate messages are delayed certain amount of time. Delaying these immediate update messages increases efficiency of the system drastically. This property is achieved by constructing a scheduling system with the help of the timer thread.
Two different types of update messages can be created in the design: "Full Dump Update", "Incremental Update". Full Dump Update messages broadcast the entire self-routing table of the node. In Figure 2{reference-type="ref" reference="fig:sendFullDumpUpdate"} the function which sends the Full Dump Update messages is shown. Incremental Update messages broadcast only the single entry in the self-routing table of the node.In Figure 3{reference-type="ref" reference="fig:sendIncrementalUpdate"} the function which sends the Full Dump Update messages is shown
{#fig:sendFullDumpUpdate}
{#fig:sendIncrementalUpdate}
The incoming update messages are directed to different methods for two different types of messages. Figure 4{reference-type="ref" reference="fig:onMessageFromBottom"} shows the function handles to messages received from the lower layer. This function overrides the function defined in super class.
{#fig:onMessageFromBottom}
Full Dump Update Message: The method processes the Full Dump Update messages, divides incoming routing table into entries (rows), and processes each entry separately. After processing the entire message, the number of changed entries in the self-routing table will determine which message type is scheduled to send. If none of the entry is changed in the self-routing table, there is no need to send a message. If single entry is changed in the self-routing table, sending Incremental Update message is scheduled with the help of the timer as mentioned in the previous section. Change in more than one entry will schedule the Full Dump Update. In Figure 5{reference-type="ref" reference="fig:processFullDumpUpdate"} the function processes the Full Dump Update messages is shown.
{#fig:processFullDumpUpdate}
Incremental Update Message: Since Incremental Update messages contain single entry, this single entry will be processed. After processing the entry in the message, possible change in the routing table will schedule the Incremental Update message. In Figure 6{reference-type="ref" reference="fig:processIncrementalUpdate"} the function processes the Incremental Update messages is shown.
{#fig:processIncrementalUpdate}
The scheduling process introduces certain complicated aspects to the design. What if a Full Dump Update is required after an Incremental Update is scheduled but not send. Then, Incremental Update is not required since the Full Dump Update message covers the information of the incremental update. The design will handle these edge cases after processing of the incoming routing table.
Two different message types are handled in two different methods, however both methods use the processing single entry method. The method is designed according to the DSDV protocol rules for decision of whether updating self-routing table or not.
The entry will be processed if the information in the entry is not about the node itself. Before processing the entry in the update message, the entry has a same destination node information which should be obtained from the self-routing table. There is a method employed for this task. Then, these two entries will be compared to decide whether updating the self-routing table or not. The information in the self-routing table will be updated under these two following conditions:
-
The entry which has newer information, which means has a higher sequence number, is preferred
-
If the sequence numbers are equal, the entry which has a lower metric value is preferred
The key point in the implementation is deciding which updates in the routing table are important and should be advertised immediately. This method distinguishes crucial changes in the self-routing table as well. Any change on the next hop or metric information is considered as important. However, the change in the entry is only sequence number, this information is broadcasted with the periodic updates. In Figure 7{reference-type="ref" reference="fig:processSingleEntry"} the function processes the single entry in the routing table is shown.
{#fig:processSingleEntry}
An ad-hoc node model is created to test DsdvService class. This model has three hierarchical layers, and each layer has a single component. Each component gets service from the lower layer component and provides service to the higher layer component. In Figure 8{reference-type="ref" reference="fig:adhocNode"}, ad-hoc node class is shown
Bottom Layer: The component at the bottom layer is created from a LinkLayer class which is given in the base project. This component receives the messages from the higher layer and hands them to the connector of the node which is connected to a channel. The component receives messages from the bottom of the node and hands them to the higher layer as well.
Middle Layer: The component at the middle layer implements the DSDV protocol. This component, named as DsdvService, includes all the futures mentioned in the "Implementation of the DSDV Protocol" section of the report. The bottom of the component is connected to upper connector of the LinkLayer component. The upper connector of this component is connected to the bottom of the higher layer component.
Top Layer: The highest layer of the node is called as application layer. At this layer, a component is created to send and receive data packets. The bottom of this component is connected to the upper connector of the DsdvService component.
{#fig:adhocNode}
The described ad-hoc node model is used to create a topology in order to simulate an ad-hoc node network. Firstly, small network topologies (generally 5 nodes) are used to validate the DSDV protocol. After the validation, the performance of the protocol is tested by observing the congestion in the network and stability. In the design, congestion in the network may refer to the number of control messages between two periodic update messages. The stability may refer to the difference in the number of control messages between two periodic updates over time.
The performance tests are conducted with different number of nodes and degree of connectivity. Number of nodes is selected five as lower limit and fifty as higher limit. The probability of connectivity of the nodes is selected 0.3 as the lower limit and 0.8 as the higher limit.
The first iteration of the test process is validating the DsdvService class. Random network topologies are created and routing tables of the individual nodes are examined to validate the design. Figure 9{reference-type="ref" reference="fig:simpleNetworkTopo"} shows one of the random network topologies used for validating the design. As a result, in Figure [fig:routingTableNode1]{reference-type="ref" reference="fig:routingTableNode1"} and in Figure [fig:routingTableNode3]{reference-type="ref" reference="fig:routingTableNode3"} the routing tables of the Node1 and Node3 is shown, respectively
{#fig:simpleNetworkTopo}
{width=".93\linewidth"} []{#fig:routingTableNode1 label="fig:routingTableNode1"}
{width="1.03\linewidth"} []{#fig:routingTableNode3 label="fig:routingTableNode3"}
Figure 10{reference-type="ref" reference="fig:ex2NetworkTopo"} shows another random network topology used for validating the design. As a result, in Figure [fig:routingTableNode0]{reference-type="ref" reference="fig:routingTableNode0"} and in Figure [fig:routingTableNode4]{reference-type="ref" reference="fig:routingTableNode4"} the routing tables of the Node1 and Node3 is shown, respectively
{#fig:ex2NetworkTopo}
{width=".93\linewidth"} []{#fig:routingTableNode0 label="fig:routingTableNode0"}
{width="1.18\linewidth"} []{#fig:routingTableNode4 label="fig:routingTableNode4"}
After the validation, the performance of the protocol is observed with different number of nodes. In the first iteration of the design process, changes in the routing tables are immediately advertised. It is observed that the protocol handles small number of nodes easily. However, as the number of node increases, the number of messages increases drastically. Above a certain number of nodes, the number of messages will not decay, and the routing tables do not stabilize. In the figures below, the number of messages sent at the second periodic update are shown. Figure 11{reference-type="ref" reference="fig:5_Nodes_0.5_probability"} shows the result of the network topology created by 5 nodes with 0.5 connection probability. Figure 12{reference-type="ref" reference="fig:10_Nodes_0.5_probability"} shows the result of the network topology created by 10 nodes with 0.5 connection probability. As can be understood from the figures, high network congestion is observed even with the 10 nodes.
{#fig:5_Nodes_0.5_probability}
{#fig:10_Nodes_0.5_probability}
The developers of the protocol foresee these results and offer two solutions. The first solution is not broadcasting changes in the topology immediately. The changes will be broadcasted after certain amount of time, and this delaying helps the broadcast different changes in a single broadcast message. The second solution is broadcasting only the important changes before the periodic update. Both solutions are applied to design as a second iteration of the design process. Any changes in the routing table will be broadcasted after a few seconds and the changes that has no significant effect on the routing path will not be broadcasted immediately. The critical point here is the decision of message importance. The changes on the next hop or the metric information are considered as important. If the only change in the routing table entries is the sequence number, this information will be broadcasted in periodic update messages. After the second iteration, the performance of the protocol has improved remarkably, and the routing table has settled after a few seconds. In the figures below, the number of messages sent at the second periodic update are shown. Figure 13{reference-type="ref" reference="fig:_5_Nodes_0.5_probability"}, Figure 14{reference-type="ref" reference="fig:20_Nodes_0.5_probability"}, Figure 15{reference-type="ref" reference="fig:50_Nodes_0.5_probability"} show the result of the network topology created by 5, 20 and 50 nodes with 0.5 connection probability, respectively.
{#fig:_5_Nodes_0.5_probability}
{#fig:20_Nodes_0.5_probability}
{#fig:50_Nodes_0.5_probability}
Validation tests are repeated after the second iteration of the design as well. The results shown in Figure [fig:routingTableNode1]{reference-type="ref" reference="fig:routingTableNode1"} and in Figure [fig:routingTableNode3]{reference-type="ref" reference="fig:routingTableNode3"} obtained after the second iteration of the design.
The performance of the DSDV protocol is strictly dependent on the parameters and the conditions selected by the user. Moreover, the optimum parameters may change depending on the network topology. The parameters and conditions such as the interval of the periodic messages, the selection of which change in the network topology considered to be important, the delaying time to broadcast these changes are crucial for the design. The designer should be careful about these conditions, otherwise the protocol can easily fall into instability region.
Table-driven protocols are not suitable for highly dynamic networks because of extra control messages to maintain routing tables up-to-date. The developers of the DSDV protocol have improved the protocol, and introduced a new protocol called "Ad-hoc on-demand distance vector" (AODV). AODV aims to reduce the number of broadcast messages forwarded throughout the network by discovering routes on-demand instead of keeping a complete up-to-date route information [@elsevier]. It is recommended that examining the performance of the AODV protocol before using DSDV.
The DSDV protocol is implemented as a term project and the performance of the protocol is observed under different circumstances. Two different criteria are considered: Network congestion and stability. The performance tests show that huge amount of network traffic may be observed if certain conditions are not selected properly. Moreover, some parameters of the protocol should be adapted to network topology such as the interval of the periodic messages. After considering these conditions, a drastic increase in the performance of the protocol is achieved.