Distance-vector routing protocol

Last updated

A distance-vector routing protocol in data networks determines the best route for data packets based on distance. Distance-vector routing protocols measure the distance by the number of routers a packet has to pass; one router counts as one hop. Some distance-vector protocols also take into account network latency and other factors that influence traffic on a given route. To determine the best route across a network, routers using a distance-vector protocol exchange information with one another, usually routing tables plus hop counts for destination networks and possibly other traffic information. Distance-vector routing protocols also require that a router inform its neighbours of network topology changes periodically.

Contents

Distance-vector routing protocols use the Bellman–Ford algorithm to calculate the best route. Another way of calculating the best route across a network is based on link cost, and is implemented through link-state routing protocols.

The term distance vector refers to the fact that the protocol manipulates vectors (arrays) of distances to other nodes in the network. The distance vector algorithm was the original ARPANET routing algorithm and was implemented more widely in local area networks with the Routing Information Protocol (RIP).

Overview

Distance-vector routing protocols use the Bellman–Ford algorithm. In these protocols, each router does not possess information about the full network topology. It advertises its distance value (DV) calculated to other routers and receives similar advertisements from other routers unless changes are done in the local network or by neighbours (routers). Using these routing advertisements each router populates its routing table. In the next advertisement cycle, a router advertises updated information from its routing table. This process continues until the routing tables of each router converge to stable values.

Some of these protocols have the disadvantage of slow convergence.

Examples of distance-vector routing protocols:

Methodology

Routers that use distance-vector protocol determine the distance between themselves and a destination. The best route for Internet Protocol packets that carry data across a data network is measured in terms of the numbers of routers (hops) a packet has to pass to reach its destination network. Additionally some distance-vector protocols take into account other traffic information, such as network latency. To establish the best route, routers regularly exchange information with neighbouring routers, usually their routing table, hop count for a destination network and possibly other traffic related information. Routers that implement distance-vector protocol rely purely on the information provided to them by other routers, and do not assess the network topology. [1]

Distance-vector protocols update the routing tables of routers and determine the route on which a packet will be sent by the next hop which is the exit interface of the router and the IP address of the interface of the receiving router. Distance is a measure of the cost to reach a certain node. The least cost route between any two nodes is the route with minimum distance.

Updates are performed periodically in a distance-vector protocol where all or part of a router's routing table is sent to all its neighbours that are configured to use the same 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 neighbours of the changes. This process has been described as ‘routing by rumour’ 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.

Development of distance-vector routing

The oldest routing protocol, and the oldest distance-vector protocol, is version 1 of the Routing Information Protocol (RIPv1). RIPv1 was formally standardised in 1988. [2] It establishes the shortest path across a network purely on the basis of the hops, that is numbers of routers that need to be passed to reach the destination network. RIP is an interior gateway protocol, so it can be used in local area networks (LANs) on interior or border routers. Routers with RIPv1 implementation exchange their routing tables with neighbouring routers by broadcasting a RIPv1 packet every 30 second into all connected networks. RIPv1 is not suitable for large networks as it limits the number of hops to 15. This hop limit was introduced to avoid routing loops, but also means that networks that are connected through more than 15 routers are unreachable. [3]

The distance-vector protocol designed for use in wide area networks (WANs) is the Border Gateway Protocol (BGP). BGP is an exterior gateway protocol and therefore implemented on border and exterior routers on the Internet. It exchanges information between routers through a Transmission Control Protocol (TCP) session. Routers with BGP implementation determine the shortest path across a network based on a range of factors other than hops. BGP can also be configured by administrators so that certain routes are preferred or avoided. BGP is used by internet service providers (ISPs) and telecommunication companies. [4]

Among the distance-vector protocols that have been described as a hybrid, because it uses routing methods associated with link-state routing protocols, is the proprietary Enhanced Interior Gateway Routing Protocol (EIGRP). It was developed by Cisco in the 1980s and was designed to offer better convergence and cause less network traffic between routers than the link-state routing protocol Open Shortest Path First (OSPF). [5]

Another example of a distance-vector routing protocol is Babel.

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, imagine a subnet connected like 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). Since B doesn't know that the path from C to A is through itself (B), it updates its table with the new value "B to A = 2 + 1". Later on, B forwards the update to C and due to the fact that A is reachable through B (From C's point of view), C decides to update its table to "C to A = 3 + 1". This slowly propagates through the network until it becomes infinity (in which case the algorithm corrects itself, due to the relaxation property of Bellman-Ford).

Workarounds and solutions

RIP uses the 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. [6] 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.

More recently, a number of loop-free distance vector protocols have been developed — notable examples are EIGRP, DSDV and Babel. 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 A, B, C and D:

Networkabcd.svg

We mark the current time (or iteration) in the algorithm with T, and begin (at time 0, or T=0) by creating distance matrices for each router to its immediate neighbours. As we build the routing tables below, the shortest path is highlighted in green, and a new shortest path is highlighted in yellow. Grey columns indicate nodes that are not neighbors of the current node, and are therefore not considered as a valid direction in its table. Red indicates invalid entries in the table since they refer to distances from a node to itself, or via itself.

T=0
from Avia Avia Bvia Cvia D
to A
to B3
to C23
to D
from Bvia Avia Bvia Cvia D
to A3
to B
to C2
to D
from Cvia Avia Bvia Cvia D
to A23
to B2
to C
to D5
from Dvia Avia Bvia Cvia D
to A
to B
to C5
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 Avia Avia Bvia Cvia D
to A
to B325
to C523
to D28
from Bvia Avia Bvia Cvia D
to A325
to B
to C262
to D7
from Cvia Avia Bvia Cvia D
to A235
to B262
to C
to D5
from Dvia Avia Bvia Cvia D
to A28
to B7
to C5
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 Avia Avia Bvia Cvia D
to A
to B325
to C523
to D1028
from Bvia Avia Bvia Cvia D
to A37
to B
to C82
to D317
from Cvia Avia Bvia Cvia D
to A23533
to B26212
to C
to D5195
from Dvia Avia Bvia Cvia D
to A10
to B7
to C5
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 Avia Avia Bvia Cvia D
to A
to B325
to C523
to D1028
from Bvia Avia Bvia Cvia D
to A37
to B
to C82
to D137
from Cvia Avia Bvia Cvia D
to A23515
to B26212
to C
to D3395
from Dvia Avia Bvia Cvia D
to A10
to B7
to C5
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. The algorithm comes to a stop.

Related Research Articles

Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone network (PSTN), and computer networks, such as the Internet.

Heuristic routing is a system used to describe how deliveries are made when problems in a network topology arise. Heuristic is an adjective used in relation to methods of learning, discovery, or problem solving. Routing is the process of selecting paths to specific destinations. Heuristic routing is used for traffic in the telecommunications networks and transport networks of the world.

The Routing Information Protocol (RIP) is one of the oldest distance-vector routing protocols which employs the hop count as a routing metric. RIP prevents routing loops by implementing a limit on the number of hops allowed in a path from source to destination. The largest number of hops allowed for RIP is 15, which limits the size of networks that RIP can support.

Enhanced Interior Gateway Routing Protocol (EIGRP) is an advanced distance-vector routing protocol that is used on a computer network for automating routing decisions and configuration. The protocol was designed by Cisco Systems as a proprietary protocol, available only on Cisco routers. In 2013, Cisco permitted other vendors to freely implement a limited version of EIGRP with some of its associated features such as High Availability (HA), while withholding other EIGRP features such as EIGRP stub, needed for DMVPN and large-scale campus deployment. Information needed for implementation was published with informational status as RFC 7868 in 2016, which did not advance to Internet Standards Track level, and allowed Cisco to retain control of the EIGRP protocol.

Link-state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the others being distance-vector routing protocols. Examples of link-state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS).

In computer networking, split-horizon route advertisement is a method of preventing routing loops in distance-vector routing protocols by prohibiting a router from advertising a route back onto the interface from which it was learned.

<span class="mw-page-title-main">Anycast</span> Network addressing and routing methodology

Anycast is a network addressing and routing methodology in which a single IP address is shared by devices in multiple locations. Routers direct packets addressed to this destination to the location nearest the sender, using their normal decision-making algorithms, typically the lowest number of BGP network hops. Anycast routing is widely used by content delivery networks such as web and name servers, to bring their content closer to end users.

Dynamic routing, also called adaptive routing, is a process where a router can forward data via a different route for a given destination based on the current conditions of the communication circuits within a system. The term is most commonly associated with data networking to describe the capability of a network to 'route around' damage, such as loss of a node or a connection between nodes, as long as other path choices are available. Dynamic routing allows as many routes as possible to remain valid in response to the change.

The diffusing update algorithm (DUAL) is the algorithm used by Cisco's EIGRP routing protocol to ensure that a given route is recalculated globally whenever it might cause a routing loop. It was developed by J.J. Garcia-Luna-Aceves at SRI International. The full name of the algorithm is DUAL finite-state machine. EIGRP is responsible for the routing within an autonomous system, and DUAL responds to changes in the routing topology and dynamically adjusts the routing tables of the router automatically.

A path-vector routing protocol is a network routing protocol which maintains the path information that gets updated dynamically. Updates that have looped through the network and returned to the same node are easily detected and discarded. This algorithm is sometimes used in Bellman–Ford routing algorithms to avoid "Count to Infinity" problems.

Route poisoning is a method to prevent a router from sending packets through a route that has become invalid within computer networks. Distance-vector routing protocols in computer networks use route poisoning to indicate to other routers that a route is no longer reachable and should not be considered from their routing tables. Unlike the split horizon with poison reverse, route poisoning provides for sending updates with unreachable hop counts immediately to all the nodes in the network.

Destination-Sequenced Distance-Vector Routing (DSDV) is a table-driven routing scheme for ad hoc mobile networks based on the Bellman–Ford algorithm. It was developed by C. Perkins and P. Bhagwat in 1994. The main contribution of the algorithm was to solve the routing loop problem. Each entry in the routing table contains a sequence number, the sequence numbers are generally even if a link is present; else, an odd number is used. The number is generated by the destination, and the emitter needs to send out the next update with this number. Routing information is distributed between nodes by sending full dumps infrequently and smaller incremental updates more frequently.

A routing loop is a common problem with various types of networks, particularly computer networks. They are formed when an error occurs in the operation of the routing algorithm, and as a result, in a group of nodes, the path to a particular destination forms a loop.

A routing protocol specifies how routers communicate with each other to distribute information that enables them to select paths between nodes on a computer network. Routers perform the traffic directing functions on the Internet; data packets are forwarded through the networks of the internet from router to router until they reach their destination computer. Routing algorithms determine the specific choice of route. Each router has a prior knowledge only of networks attached to it directly. A routing protocol shares this information first among immediate neighbors, and then throughout the network. This way, routers gain knowledge of the topology of the network. The ability of routing protocols to dynamically adjust to changing conditions such as disabled connections and components and route data around obstructions is what gives the Internet its fault tolerance and high availability.

The Wireless Routing Protocol (WRP) is a proactive unicast routing protocol for mobile ad hoc networks (MANETs).

In wired computer networking, including the Internet, a hop occurs when a packet is passed from one network segment to the next. Data packets pass through routers as they travel between source and destination. The hop count refers to the number of network devices through which data passes from source to destination.

IP routing is the application of routing methodologies to IP networks. This involves not only protocols and technologies but includes the policies of the worldwide organization and configuration of Internet infrastructure. In each IP network node, IP routing involves the determination of a suitable path for a network packet from a source to its destination in an IP network. The process uses static configuration rules or dynamically obtained from routing protocols to select specific packet forwarding methods to direct traffic to the next available intermediate network node one hop closer to the desired final destination, a total path potentially spanning multiple computer networks.

An interior gateway protocol (IGP) or Interior routing protocol is a type of routing protocol used for exchanging routing table information between gateways within an autonomous system. This routing information can then be used to route network-layer protocols like IP.

Fisheye State Routing (FSR) is a proposal for an implicit hierarchical routing protocol targeted to ad hoc networks. The basic principles of FSR are shared with other proactive, link-state routing protocols. In proactive link-state protocols every network node constantly updates a topology map that makes it possible to compute the shortest path to any destination in the network. The originality of FSR is inspired by the "fisheye" technique to reduce the size of information required to represent graphical data: The eye of a fish captures with high detail the pixels near the focal point, while the detail decreases as the distance from the focal point increases.

In a router, route redistribution allows a network that uses one routing protocol to route traffic dynamically based on information learned from another routing protocol.

References

  1. ↑ Tamara Dean (2009). Network+ Guide to Networks . Cengage Learning. pp.  274. ISBN   9781423902454.
  2. ↑ C. Hedrick (June 1988). Routing Information Protocol. Network Working Group. doi: 10.17487/RFC1058 . RFC 1058.Historic. Updated by RFC  1388 and 1723.
  3. ↑ Tamara Dean (2009). Network+ Guide to Networks . Cengage Learning. pp.  274. ISBN   9781423902454.
  4. ↑ Tamara Dean (2009). Network+ Guide to Networks . Cengage Learning. pp.  274–275. ISBN   9781423902454.
  5. ↑ Tamara Dean (2009). Network+ Guide to Networks . Cengage Learning. pp.  275. ISBN   9781423902454.
  6. ↑ C. Hedrick (June 1988). Routing Information Protocol. Network Working Group. doi: 10.17487/RFC1058 . RFC 1058.Historic. sec. 2.2.2. Updated by RFC  1388 and 1723.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.