Wireless Routing Protocol

The Wireless Routing Protocol (WRP) is a proactive unicast routing protocol for mobile ad-hoc networks (MANETs). WRP uses an enhanced version of the distance-vector routing protocol, which uses the Bellman-Ford algorithm to calculate paths. Because of the mobile nature of the nodes within the MANET, the protocol introduces mechanisms which reduce route loops and ensure reliable message exchange.

The wireless routing protocol (WRP), similar to DSDV, inherits the properties of the distributed Bellman-Ford algorithm. To counter the count-to-infinity problem and to enable faster convergence, it employs a unique method of maintaining information regarding the shortest distance to every destination node in the network and the penultimate hop node on the path to every destination node. Since WRP, like DSDV, maintains an up-to-date view of the network, every node has a readily available route to every destination node in the network. It differs from DSDV in table maintenance and in the update procedures. While DSDV maintains only one topology table, WRP uses a set of tables to maintain more accurate information. The tables that are maintained by a node are the following: distance table (DT), routing table (RT), link cost table (LCT), and a message retransmission list (MRL).

The DT contains the network view of the neighbors of a node. It contains a matrix where each element contains the distance and the penultimate node reported by a neighbor for a particular destination. The RT contains the up-to-date view of the network for all known destinations. It keeps the shortest distance, the predecessor node (penultimate node), the successor node (the next node to reach the destination), and a flag indicating the status of the path. The path status may be a simple path (correct), or a loop (error), or the destination node not marked (null). The LCT contains the cost (e.g., the number of hops to reach the destination) of relaying messages through each link. The cost of a broken link is infinity. It also contains the number of update periods (intervals between two successive periodic updates) passed since the last successful update was received from that link. This is done to detect links breaks. The MRL contains an entry for every update message that is to be retransmitted and maintains a counter for each entry. This counter is decremented after every retransmission of an update message. Each update message contains a list of updates. A node also marks each node in the RT that has to acknowledge the update message it transmitted. Once the counter reaches zero, the entries in the update message for which no acknowledgments have been received are to be retransmitted and the update message is deleted. Thus, a node detects a link break by the number of update periods missed since the last successful transmission. After receiving an update message, a node not only updates the distance for transmission neighbors but also checks the other neighbors’ distance, hence convergence is much faster than DSDV.

Method

Each node implementing WRP keeps a table of routes and distances and link costs. It also maintains a 'message retransmission list' (MRL).

Routing table entries contain distance to a destination node, the previous and next nodes along the route, and is tagged to identify the route's state: whether it is a simple path, loop or invalid route. (Storing the previous and successive nodes assists in detecting loops and avoiding the counting-to-infinity problem - a shortcoming of Distance Vector Routing.)

The link cost table maintains the cost of the link to its nearest neighbors (nodes within direct transmission range), and the number of timeouts since successfully receiving a message from the neighbor.

Nodes periodically exchange routing tables with their neighbors via update messages, or whenever the link state table changes. The MRL maintains a list of which neighbors are yet to acknowledged an update message, so they can be retransmitted if necessary. Where no change in the routing table, a node is required to transmit a 'hello' message to affirm its connectivity.

When an update message is received, a node updates its distance table and reassesses the best route paths. It also carries out a consistency check with its neighbors, to help eliminate loops and speed up convergence.

bY PRAMODH M.J. SRINGERI

 Vishveshwarya Technological University
                                     Belgaum – 590018

         Technical Seminar on

    “WIRELESS ROUTING PROTOCOL ”

Submitted in partial fulfilment for the award of degree of Bachelor of Engineering 2010-2011

by

PRAMODH M.J.(1RE07CS057)

Under the Guidance

of Dr.VIJAYKUMAR B.P.

Professor,HOD, Department of CSE

 Certificate

Certified that the Technical Seminar on entitled WIRELESS ROUTING PROTOCOL carried out by PRAMODH M.J.(1RE07CS057) a bonafide student of Reva Institute of Technology & Management in partial fulfilment for the award of Bachelor of Engineering in 8th Semester of the Visvesvaraya Technological University, Belgaum, during the year 2010-2011. It is certified that all corrections/suggestions indicated for internal assessment have been incorporated in the report. The project report has been approved as it satisfies the academic requirements in the respect of seminar prescribed for the said degree.

     Project Guide	Principal

(Dr. VIJAYKUMAR B.P.) (Dr. Rana Prathap Reddy) HOD, Dept. of CSE

                                           Contents

1.Abstract 2.Introduction 3.Bellman Ford algorithm 4.Application in Routing 5.Algorithm Correctness Proof 6.Simulation of algorithm 7.Overcoming Limitations of Distance

  Vector Routing Protocol 
   Method
   Limitations 
    Example

8.Routing update information 9.Conclusions 10.References

Abstract

   We present the Wireless Routing Protocol (WRP). In WRP, routing nodes communicate the distance and secondto-last hop for each destination. WRP reduces the number of cases in which a temporary routing loop can occur, which accounts for its fast convergence properties. A detailed proof of correctness is presented and its performance is compared by simulation with the performance of the distributed Bellman-Ford Algorithm (DBF), DUAL (a loop-free distance-vector algorithm) and an Ideal Link-state Algorithm (ILS), which represent the state of the art of internet routing. 

The simulation results indicate that WRP is the most efficient of the alternatives analyzed.is required to send ACKs for each update packet received.

When no update messages have to be sent WRP periodically exchanges "HELLO" messages. When no "HELLO" message was received in a specified time period an alarm appears and it has to be checked if the link is still reachable. If the node receives a "HELLO" message from a new node, the node is added to the routing table.

WRP avoids the count-to-infinity problem by forcing each node to perform consistency check of predecessor information reported by all its neighbors.

                                  INTRODUCTION

The Wireless Routing Protocol (WRP) is a proactive unicast routing protocol for mobile ad-hoc networks (MANETs). WRP uses an enhanced version of the distance-vector routing protocol, which uses the Bellman-Ford algorithm to calculate paths. Because of the mobile nature of the nodes within the MANET, the protocol introduces mechanisms which reduce route loops and ensure reliable message exchange. The wireless routing protocol (WRP), similar to DSDV, inherits the properties of the distributed Bellman-Ford algorithm. To counter the count-to-infinity problem and to enable faster convergence, it employs a unique method of maintaining information regarding the shortest distance to every destination node in the network and the penultimate hop node on the path to every destination node. Since WRP, like DSDV, maintains an up-to-date view of the network, every node has a readily available route to every destination node in the network. It differs from DSDV in table maintenance and in the update procedures. While DSDV maintains only one topology table, WRP uses a set of tables to maintain more accurate information. The tables that are maintained by a node are the following: distance table (DT), routing table (RT), link cost table (LCT), and a message retransmission list (MRL). The DT contains the network view of the neighbors of node.Itcontains a matrix where each element contains the distance and the penultimate node reported by a neighbor for a particular destination. The RT contains the up-to-date view of the network for all known destinations. It keeps the shortest distance, the predecessor node (penultimate node), the successor node (the next node to reach the destination), and a flag indicating the status of the path. The path status may be a simple path (correct), or a loop (error), or the destination node not marked (null). The LCT contains the cost (e.g., the number of hops to reach the destination) of relaying messages through each link. The cost of a broken link is infinity. It also contains the number of update periods (intervals between two successive periodic updates) passed since the last successful update was received from that link. This is done to detect links breaks. The MRL contains an entry for every update message that is to be retransmitted and maintains a counter for each entry. This counter is decremented after every retransmission of an update message. Each update message contains a list of updates.

A node also marks each node in the RT that has to acknowledge the update message it transmitted. Once the counter reaches zero, the entries in the update message for which no acknowledgments have been received are to be retransmitted and the update message is deleted. Thus, a node detects a link break by the number of update periods missed since the last successful transmission After receiving an update message, a node not only updates the distance for transmission neighbors but also checks the other neighbors’ distance, hence convergence is much faster than DSDV. Each node implementing WRP keeps a table of routes and distances and link costs. It also maintains a 'message retransmission list' (MRL). Routing table entries contain distance to a destination node, the previous and next nodes along the route, and is tagged to identify the route's state: whether it is a simple path, loop or invalid route. (Storing the previous and successive nodes assists in detecting loops and avoiding the counting-to-infinity problem - a shortcoming of Distance Vector Routing.) The link cost table maintains the cost of the link to its nearest neighbors (nodes within direct transmission range), and the number of timeouts since successfully receiving a message from the neighbor. Nodes periodically exchange routing tables with their neighbors via update messages, or whenever the link state table changes. The MRL maintains a list of which neighbors are yet to acknowledged an update message, so they can be retransmitted if necessary. Where no change in the routing table, a node is required to transmit a 'hello' message to affirm its connectivity. When an update message is received, a node updates its distance table and reassesses the best route paths. It also carries out a consistency check with its neighbors, to help eliminate loops and speed up convergence.

WRP has the same advantage as that of DSDV. In addition, it has faster convergence and involves fewer table updates. But the complexity of maintenance of multiple tables demands a larger memory and greater processing power from nodes in the ad hoc wireless network. At high mobility, the control overhead involved in updating table entries is almost the same as that of DSDV and hence is not suitable for highly dynamic and also for a very large ad hoc wireless network. WRP requires large memory storage and resources in maintaining its tables. The protocol is not suitable for large mobile ad hoc networks as it suffers from limited scalability. WRP WRP is a distance vector routing protocol. Each node maintains 4 tables: • Distance table • Routing table • Link cost table • Message Retransmission List table (MRL) The MRL contains the sequence number of the update message, a retransmission counter (how often a message is retransmitted before the connection is rebuild) and a list of updates sent in the update message.

Bellman–Ford algorithm

The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph. For graphs with only non-negative edge weights, the faster Dijkstra's algorithm also solves the problem. Thus, Bellman–Ford is used primarily for graphs with negative edge weights. The algorithm is named after its developers, Richard Bellman and Lester Ford, Jr.

If a graph contains a "negative cycle", i.e., a cycle whose edges sum to a negative value, then walks of arbitrarily low weight can be constructed, i.e., there may be no shortest path. Bellman-Ford can detect negative cycles and report their existence, but it cannot produce a correct answer if a negative cycle is reachable from the source. According to Robert Sedgewick, "Negative weights are not merely a mathematical curiosity; [...] [they] arise in a natural way when we reduce other problems to shortest-paths problems". Let G be a graph containing a negative cycle. One NP-Complete variant of the shortest-path problem asks for the shortest path in G (containing a negative cycle) such that no edge is repeated. Sedgewick gives a reduction from the Hamiltonian path problem to this variant of the problem. The Bellman-Ford distance-vector routing algorithm is used by routers on internetworks to exchange routing information about the current status of the network and how to route packets to their destinations. The algorithm basically merges routing information provided by different routers into lookup tables. It is well defined and used on a number of popular networks. It also provides reasonable performance on small- to medium-sized networks, but on larger networks the algorithm is slow at calculating updates to the network topology. In some cases, looping occurs, in which a packet goes through the same node more than once. In general, most DVR (distance-vector routing) algorithms are not suitable for larger networks that have thousands of nodes, or if the network configuration changes often. In the latter case, the routing algorithm must be able to dynamically update the routing tables quickly to accommodate changes. A more efficient routing protocol is OSPF (Open Shortest Path First).

Applications in routing A distributed variant of the Bellman–Ford algorithm is used in distance-vector routing protocols, for example the Routing Information Protocol (RIP). The algorithm is distributed because it involves a number of nodes (routers) within an Autonomous system, a collection of IP networks typically owned by an ISP. It consists of the following steps: 1. Each node calculates the distances between itself and all other nodes within the AS and stores this information as a table. 2. Each node sends its table to all neighboring nodes. 3. When a node receives distance tables from its neighbors, it calculates the shortest routes to all other nodes and updates its own table to reflect any changes. The main disadvantages of the Bellman–Ford algorithm in this setting are as follows: • It does not scale well. • Changes in network topology are not reflected quickly since updates are spread node-by-node. • Count to infinity (if link or node failures render a node unreachable from some set of other nodes, those nodes may spend forever gradually increasing their estimates of the distance to it, and in the meantime there may be routing loops).

Algorithm procedure BellmanFord(list vertices, list edges, vertex source)

  // This implementation takes in a graph, represented as lists of vertices
  // and edges, and modifies the vertices so that their distance and
  // predecessor attributes store the shortest paths.

  // Step 1: initialize graph
  for each vertex v in vertices:
      if v is source then v.distance := 0
      else v.distance := infinity
      v.predecessor := null

  // Step 2: relax edges repeatedly
  for i from 1 to size(vertices)-1:
      for each edge uv in edges: // uv is the edge from u to v
          u := uv.source
          v := uv.destination
          if u.distance + uv.weight < v.distance:
              v.distance := u.distance + uv.weight
              v.predecessor := u

  // Step 3: check for negative-weight cycles
  for each edge uv in edges:
      u := uv.source
      v := uv.destination
      if u.distance + uv.weight < v.distance:
          error "Graph contains a negative-weight cycle"

Proof of correctness The correctness of the algorithm can be shown by induction. The precise statement shown by induction is: Lemma. After i repetitions of for cycle: • If Distance(u) is not infinity, it is equal to the length of some path from s to u; • If there is a path from s to u with at most i edges, then Distance(u) is at most the length of the shortest path from s to u with at most i edges. Proof. For the base case of induction, consider i=0 and the moment before for cycle is executed for the first time. Then, for the source vertex, source. distance = 0, which is correct. For other vertices u, u.distance = infinity, which is also correct because there is no path from source to u with 0 edges. For the inductive case, we first prove the first part. Consider a moment when a vertex's distance is updated by v.distance := u.distance + uv.weight. By inductive assumption, u.distance is the length of some path from source to u. Then u.distance + uv.weight is the length of the path from source to v that follows the path from source to u and then goes to v. For the second part, consider the shortest path from source to u with at most i edges. Let v be the last vertex before u on this path. Then, the part of the path from source to v is the shortest path from source to v with at most i-1 edges. By inductive assumption, v.distance after i−1 cycles is at most the length of this path. Therefore, uv.weight + v.distance is at most the length of the path from s to u. In the ith cycle, u.distance gets compared with uv.weight + v.distance, and is set equal to it if uv.weight + v.distance was smaller. Therefore, after i cycles, u.distance is at most the length of the shortest path from source to u that uses at most i edges. If there are no negative-weight cycles, then every shortest path visits each vertex at most once, so at step 3 no further improvements can be made. Conversely, suppose no improvement can be made. Then for any cycle with vertices v[0], ..., v[k−1], v[i].distance <= v[(i-1) mod k].distance + v[(i-1) mod k]v[i].weight Summing around the cycle, the v[i].distance terms and the v[i−1 (mod k)] distance terms cancel, leaving 0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight I.e., every cycle has nonnegative weight.

Simulation of Bellman Ford Routing algorithm with 7 nodes. Possible node Routing Diagrams Step 1 : red arrows point to nodes reachable (immeidate neighbour) within 1 hop from the inspected node (Blue node). The distance from the start node to: b=1, c=1, e=1, f=1. Node b has the minimum distance. Any other path to b visits another red node, and will be longer than 1. Node b will be colored orange to indicate 1 is the length of the shortest path to b.

Step 2: Red arrows point to neighbour nodes that reachable from neighbour of inspected node that already have a final distance. The distance to: c=1, e=1, f=1. Node c has the minimum distance. There are no other arrows coming in to c. Node c will be colored orange to indicate 1 is the length of the shortest path to c.

Step 3: Red arrows point to neighbour nodes that reachable from neighbour of inspected node that already have a final distance. The distance to: e=1, f=1. Node e has the minimum distance. There are no other arrows coming in to e. Node e will be colored orange to indicate 1 is the length of the shortest path to e.

Step 4: Red arrows point to neighbour nodes that reachable from neighbour of inspected node that already have a final distance. The distance to: f=1. Since this node forms a 'bridge' to the remaining nodes, all other paths to this node will be longer. Node f will be colored orange to indicate 1 is the length of the shortest path to f. Distance-vector routing protocol Working In computer communication theory relating to packet-switched networks, a distance-vector routing protocol is one of the two major classes of routing protocols, the other major class being the link-state protocol. Distance-vector routing protocols use the Bellman-Ford algorithm, Ford Fulkerson algorithm, or DUAL to calculate paths. A distance-vector routing protocol requires that a router informs its neighbors of topology changes periodically and, in some cases, when a change is detected in the topology of a network. Compared to link-state protocols, which require a router to inform all the nodes in a network of topology changes, distance-vector routing protocols have less computational complexity and message overhead.[citation needed] Distance Vector means that Routers are advertised as vector of distance and direction. 'Direction' is represented by next hop address and exit interface, whereas 'Distance' uses metrics such as hop count. Routers using distance vector protocol do not have knowledge of the entire path to a destination. Instead DV uses two methods: 1. Direction in which or interface to which a packet should be forwarded. 2. Distance from its destination. Examples of distance-vector routing protocols include Routing Information Protocol Version 1 & 2, RIPv1 and RIPv2 and IGRP. EGP and BGP are not pure distance-vector routing protocols because a distance-vector protocol calculates routes based only on link costs whereas in BGP, for example, the local route preference value takes priority over the link cost. Method

The methods used to calculate the best path for a network are different between different routing protocols but the fundamental features of distance-vector algorithms are the same across all DV based protocols. Distance Vector means that Routers are advertised as vector of distance and Direction. Direction is simply next hop address and exit interface and Distance means hop count. Routers using distance vector protocol do not have knowledge of the entire path to a destination. Instead DV uses two methods: 1. Direction in which or interface to which a packet should be forwarded. 2. Distance from its destination. As the name suggests the DV protocol is based on calculating the direction and distance to any link in a network. The cost of reaching a destination is calculated using various route metrics. RIP uses the hop count of the destination whereas IGRP takes into account other information such as node delay and available bandwidth. Updates are performed periodically in a distance-vector protocol where all or part of a router's routing table is sent to all its neighbors that are configured to use the same distance-vector routing protocol. RIP supports cross-platform distance vector routing whereas IGRP is a Cisco Systems proprietary distance vector routing protocol. Once a router has this information it is able to amend its own routing table to reflect the changes and then inform its neighbors of the changes. This process has been described as ‘routing by rumor’ because routers are relying on the information they receive from other routers and cannot determine if the information is actually valid and true. There are a number of features which can be used to help with instability and inaccurate routing information.

Limitations Count-to-infinity problem The Bellman-Ford algorithm does not prevent routing loops from happening and suffers from the count-to-infinity problem. The core of the count-to-infinity problem is that if A tells B that it has a path somewhere, there is no way for B to know if the path has B as a part of it. To see the problem clearly, imagine a subnet connected like as A-B-C-D-E-F, and let the metric between the routers be "number of jumps". Now suppose that A is taken offline. In the vector-update-process B notices that the route to A, which was distance 1, is down - B does not receive the vector update from A. The problem is, B also gets an update from C, and C is still not aware of the fact that A is down - so it tells B that A is only two jumps from C (C to B to A) , which is false. This slowly propagates through the network until it reaches infinity (in which case the algorithm corrects itself, due to the "Relax property" of Bellman Ford). [edit] Partial solutions RIP uses Split Horizon with Poison Reverse technique to reduce the chance of forming loops and uses a maximum number of hops to counter the 'count-to-infinity' problem. These measures avoid the formation of routing loops in some, but not all, cases. The addition of a hold time (refusing route updates for a few minutes after a route retraction) avoids loop formation in virtually all cases, but causes a significant increase in convergence times. A number of loop-free distance vector protocols, such as EIGRP and DSDV, have been developed. These avoid loop formation in all cases, but suffer from increased complexity, and their deployment has been slowed down by the success of link-state routing protocols such as OSPF.

Example

In this network we have 4 routers We shall mark the current time (or iteration) in the algorithm with T, and shall begin (at time 0, or T=0) by creating distance matrices for each router to its immediate neighbors. As we build the routing tables below, the shortest path is highlighted with the color green, a new shortest path is highlighted with the color yellow.

T=0 from A via A via B via C via D to A to B 3 to C 23 to D from B via A via B via C via D to A 3 to B to C 2 to D from C via A via B via C via D to A 23 to B 2 to C to D 5 from D via A via B via C via D to A to B to C 5 to D

At this point, all the routers (A,B,C,D) have new "shortest-paths" for their DV (the list of distances that are from them to another router via a neighbor). They each broadcast this new DV to all their neighbors: A to B and C, B to C and A, C to A, B, and D, and D to C. As each of these neighbors receives this information, they now recalculate the shortest path using it.

For example: A receives a DV from C that tells A there is a path via C to D, with a distance (or cost) of 5. Since the current "shortest-path" to C is 23, then A knows it has a path to D that costs 23+5=28. As there are no other shorter paths that A knows about, it puts this as its current estimate for the shortest-path from itself (A) to D, via C.

T=1 from A via A via B via C via D to A to B 3 25 to C 5 23 to D 28 from B via A via B via C via D to A 3 25 to B to C 26 2 to D 7 from C via A via B via C via D to A 23 5 to B 26 2 to C to D 5 from D via A via B via C via D to A 28 to B 7 to C 5 to D

Again, all the routers have gained in the last iteration (at T=1) new "shortest-paths", so they all broadcast their DVs to their neighbors; This prompts each neighbor to re-calculate their shortest distances again.

For instance: A receives a DV from B that tells A there is a path via B to D, with a distance (or cost) of 7. Since the current "shortest-path" to B is 3, then A knows it has a path to D that costs 7+3=10. This path to D of length 10 (via B) is shorter than the existing "shortest-path" to D of length 28 (via C), so it becomes the new "shortest-path" to D.

T=2 from A via A via B via C via D to A to B 3 25 to C 5 23 to D 10 28 from B via A via B via C via D to A 3 25 to B to C 26 2 to D 31 7 from C via A via B via C via D to A 23 5 33 to B 26 2 12 to C to D 33 9 5 from D via A via B via C via D to A 10 to B 7 to C 5 to D

This time, only routers A and D have new shortest-paths for their DVs. So they broadcast their new DVs to their neighbors: A broadcasts to B and C, and D broadcasts to C. This causes each of the neighbors receiving the new DVs to re-calculate their shortest paths. However, since the information from the DVs doesn't yield any shorter paths than they already have in their routing tables, then there are no changes to the routing tables.

T=3 from A via A via B via C via D to A to B 3 25 to C 5 23 to D 10 28 from B via A via B via C via D to A 3 7 to B to C 8 2 to D 31 7 from C via A via B via C via D to A 23 5 15 to B 26 2 12 to C to D 33 9 5 from D via A via B via C via D to A 10 to B 7 to C 5 to D

None of the routers have any new shortest-paths to broadcast. Therefore, none of the routers receive any new information that might change their routing tables. So the algorithm comes to a stop.

Routing Update Information As soon as topology changes are perceived, only the path-vector tuples (destination, distance) that reflects the update are sent. To improve reliability in delivering update messages, every neighbor is required to send ACKs for each update packet received. When no update messages have to be sent WRP periodically exchanges "HELLO" messages. When no "HELLO" message was received in a specified time period an alarm appears and it has to be checked if the link is still reachable. If the node receives a "HELLO" message from a new node, the node is added to the routing table. WRP avoids the count-to-infinity problem by forcing each node to perform consistency check of predecessor information reported by all its neighbors.

Conclusion The wireless routing protocol (WRP), similar to DSDV, inherits the properties of the distributed Bellman-Ford algorithm. To counter the count-to-infinity problem and to enable faster convergence, it employs a unique method of maintaining information regarding the shortest distance to every destination node in the network and the penultimate hop node on the path to every destination node. Since WRP, like DSDV, maintains an up-to-date view of the network, every node has a readily available route to every destination node in the network. It differs from DSDV in table maintenance and in the update procedures.

REFERENCES:

• Murthy, Shree; Garcia-Luna-Aceves, J. J. (1996-10-01), "An efficient routing protocol for wireless networks", Mobile Networks and Applications (Hingham, MA: Kluwer Academic Publishers) 1 (2): 183–197, doi:10.1007/BF01193336 • .Wikipedia • Compter networks by Nader F Mir. • Google.

Shortcomings

WRP has the same advantage as that of DSDV. In addition, it has faster convergence and involves fewer table updates. But the complexity of maintenance of multiple tables demands a larger memory and greater processing power from nodes in the ad hoc wireless network. At high mobility, the control overhead involved in updating table entries is almost the same as that of DSDV and hence is not suitable for highly dynamic and also for a very large ad hoc wireless network.

WRP requires large memory storage and resources in maintaining its tables. The protocol is not suitable for large mobile ad hoc networks as it suffers from limited scalability.