Diffusing update algorithm

Last updated

The diffusing update algorithm (DUAL) is the algorithm used by Cisco's EIGRP [1] 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 (DUAL FSM). 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.

Algorithm An unambiguous specification of how to solve a class of problems

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems. Algorithms can perform calculation, data processing, automated reasoning, and other tasks.

SRI International United States research institute

SRI International (SRI) is an American nonprofit scientific research institute and organization headquartered in Menlo Park, California. The trustees of Stanford University established SRI in 1946 as a center of innovation to support economic development in the region.

Finite-state machine mathematical model of computation; abstract machine that can be in exactly one of a finite number of states at any given time

A finite-state machine (FSM) or finite-state automaton, finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some external inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the conditions for each transition. Finite state machines are of two types – deterministic finite state machines and non-deterministic finite state machines. A deterministic finite-state machine can be constructed equivalent to any non-deterministic one.

Contents

EIGRP uses a feasibility condition to ensure that only loop-free routes are ever selected. The feasibility condition is conservative: when the condition is true, no loops can occur, but the condition might under some circumstances reject all routes to a destination although some are loop-free.

When no feasible route to a destination is available, the DUAL algorithm [2] invokes a diffusing computation [3] to ensure that all traces of the problematic route are eliminated from the network. At which point the normal Bellman–Ford algorithm is used to recover a new route.

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers. The algorithm was first proposed by Alfonso Shimbel (1955), but is instead named after Richard Bellman and Lester Ford, Jr., who published it in 1958 and 1956, respectively. Edward F. Moore also published the same algorithm in 1957, and for this reason it is also sometimes called the Bellman–Ford–Moore algorithm.

Operation

DUAL uses three separate tables for the route calculation. These tables are created using information exchanged between the EIGRP routers. The information is different than that exchanged by link-state routing protocols. In EIGRP, the information exchanged includes the routes, the "metric" or cost of each route, and the information required to form a neighbor relationship (such as AS number, timers, and K values). The three tables and their functions in detail are as follows:

Link-state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the other 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).

Router metrics are metrics used by a router to make routing decisions. A metric is typically one of many fields in a routing table. Router metrics help the router choose the best route among multiple feasible routes to a destination. The route will go in the direction of the gateway with the lowest metric.

A network packet is a formatted unit of data carried by a packet-switched network. A packet consists of control information and user data, which is also known as the payload. Control information provides data for delivering the payload, for example: source and destination network addresses, error detection codes, and sequencing information. Typically, control information is found in packet headers and trailers.

"FD (Feasible Distance)": The calculated metric of a route to a destination within the autonomous system.
"RD (Reported Distance)": The metric to a destination as advertised by a neighboring router. RD is used to calculate the FD, and to determine if the route meets the "feasibility condition".
Route Status: A route is marked either "active" or "passive". "Passive" routes are stable and can be used for data transmission. "Active" routes are being recalculated, and/or not available.

DUAL evaluates the data received from other routers in the topology table and calculates the primary (successor) and secondary (feasible successor) routes. The primary path is usually the path with the lowest metric to reach the destination, and the redundant path is the path with the second lowest cost (if it meets the feasibility condition). There may be multiple successors and multiple feasible successors. Both successors and feasible successors are maintained in the topology table, but only the successors are added to the routing table and used to route packets.

For a route to become a feasible successor, its RD must be smaller than the FD of the successor. If this feasibility condition is met, there is no way that adding this route to the routing table could cause a loop.

If all the successor routes to a destination fail, the feasible successor becomes the successor and is immediately added to the routing table. If there is no feasible successor in the topology table, a query process is initiated to look for a new route.

Example

Legend:

+ = Router
− or | = Link
(X) = Metric of link
     A    (2)    B    (1)    C      + - - - - - + - - - - - +                  |           |               (2)|           | (3)                  |           |                  + - - - - - +                  D    (1)    E

Now a client on router E wants to talk to a client on router A. That means a route between router A and router E must be available. This route is calculated as follows:

The immediate neighbours of router E are router C and router D. DUAL in router E asks for the reported distance (RD) from routers C and D respectively to router A. The following are the results:

Destination: Router A
via D: RD(4)
via C: RD(3)

The route via C is therefore in the lowest cost. In the next step, the distance from router E to the neighbours are added to the reported distance to get the feasible distance (FD):

Destination: Router A
via D: RD(4), FD(5)
via C: RD(3), FD(6)

DUAL therefore finds that the route via D has the least total cost. Then the route via D will be marked as "successor", equipped with passive status and registered in the routing table. The route via C is kept as a "feasible successor", because its RD is less than the FD of the successor:

Destination: Router A
via D: RD(4), FD(5) successor
via C: RD(3), FD(6) feasible successor

Related Research Articles

Interior Gateway Routing Protocol (IGRP) is a distance vector interior gateway protocol (IGP) developed by Cisco. It is used by routers to exchange routing data within an autonomous system.

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.

Open Shortest Path First (OSPF) is a routing protocol for Internet Protocol (IP) networks. It uses a link state routing (LSR) algorithm and falls into the group of interior gateway protocols (IGPs), operating within a single autonomous system (AS). It is defined as OSPF Version 2 in RFC 2328 (1998) for IPv4. The updates for IPv6 are specified as OSPF Version 3 in RFC 5340 (2008). OSPF supports the Classless Inter-Domain Routing (CIDR) addressing model.

The Routing Information Protocol ('RIP') is one of the oldest distance-vector routing protocols which employ 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.

Dijkstras algorithm graph search algorithm

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

In computer networking a routing table, or routing information base (RIB), is a data table stored in a router or a networked computer that lists the routes to particular network destinations, and in some cases, metrics (distances) associated with those routes. The routing table contains information about the topology of the network immediately around it. The construction of routing tables is the primary goal of routing protocols. Static routes are entries made in a routing table by non-automatic means and which are fixed rather than being the result of some network topology "discovery" procedure.

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. Partial functionality of EIGRP was converted to an open standard in 2013 and was published with informational status as RFC 7868 in 2016.

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, on which a distance-vector protocol is implemented, 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 informs its neighbours of network topology changes periodically.

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.

Dynamic routing, also called adaptive routing, is a process where a router can forward data via a different route or 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, so long as other path choices are available. Dynamic routing allows as many routes as possible to remain valid in response to the change.

Protocol-dependent modules (PDMs) are used by the routing protocol EIGRP to make decisions about adding routes learned from other sources; for example other routers or routing protocols to the routing table. In fact EIGRP has the capability for routing several different protocols including IPv4 and IPv6 using protocol-dependent modules (PDMs). The PDM is also capable of carrying information from the routing table to the topology table. EIGRP offers support for various routed protocols, and has added support for Service Routing (SAF) PDMs. The only other routing protocol that comes with support for multiple network layer protocols is Intermediate System-to-Intermediate System (IS-IS).

Geographic routing

Geographic routing is a routing principle that relies on geographic position information. It is mainly proposed for wireless networks and based on the idea that the source sends a message to the geographic location of the destination instead of using the network address. The idea of using position information for routing was first proposed in the 1980s in the area of packet radio networks and interconnection networks. Geographic routing requires that each node can determine its own location and that the source is aware of the location of the destination. With this information a message can be routed to the destination without knowledge of the network topology or a prior route discovery.

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, distributing information that enables them to select routes between any two 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 data lines and computers and route data around obstructions is what gives the Internet its survivability and reliability.

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

IP routing is the field of routing methodologies of Internet Protocol (IP) packets within and across 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 status information 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) is a type of protocol used for exchanging routing information between gateways within an autonomous system. This routing information can then be used to route network-layer protocols like IP.

References

  1. ↑ Cisco EIGRP official white paper, Sep 09, 2005
  2. ↑ J.J. Garcia-Lunes-Aceves, "Loop-Free Routing Using Diffusing Computations" IEEE/ACM Transactions on Networking, vol. 1, no, 1, pp. 130–141 Feb. 1993
  3. ↑ E. W. Dijkstra and C. S. Scholten. “Termination detection for diffusing computations,” Inform. Process. Lett., vol. 11, no, 1, pp. 1–4, Aug. 1980 and EWD687a
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.