Diffusing update algorithm - Revision history

Gregbo: fixed broken link

2019-04-02T01:49:42Z

fixed broken link

← Previous revision		Revision as of 01:49, 2 April 2019
Line 3:		Line 3:
	EIGRP uses a [[Enhanced Interior Gateway Routing Protocol#Feasibility condition\|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.		EIGRP uses a [[Enhanced Interior Gateway Routing Protocol#Feasibility condition\|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 <ref>[~~http~~://~~www~~.~~soe.ucsc.edu~~/~~research~~/~~ccrg~~/~~publications/jj.dual.ton93.pdf~~ 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]</ref> invokes a diffusing computation <ref>[http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD687a.PDF 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]</ref> 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.		When no feasible route to a destination is available, the DUAL algorithm <ref>[https://escholarship.org/uc/item/0j73185m 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]</ref> invokes a diffusing computation <ref>[http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD687a.PDF 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]</ref> 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.

	==Operation==		==Operation==

JHunterJ: clean up

2018-07-17T18:35:06Z

clean up

← Previous revision		Revision as of 18:35, 17 July 2018
Line 1:		Line 1:
	'''~~DUAL''',~~ ~~the~~ '''~~D'''iffusing~~ '''U'''~~pdate '''AL'''gorithm,~~ is the [[algorithm]] used by [[Cisco]]'s [[EIGRP]]<ref>[http://www.cisco.com/c/en/us/support/docs/ip/enhanced-interior-gateway-routing-protocol-eigrp/16406-eigrp-toc.html Cisco EIGRP official white paper, Sep 09, 2005]</ref> 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]]. ~~According to Cisco, the~~ full name of the algorithm is DUAL [[finite-state machine]] (DUAL FSM). EIGRP is responsible for the routing within an [[~~Autonomous_system_~~(Internet)\|autonomous system]] and DUAL responds to changes in the routing topology and dynamically adjusts the routing tables of the router automatically.		The '''diffusing update algorithm''' ('''DUAL''') is the [[algorithm]] used by [[Cisco]]'s [[EIGRP]]<ref>[http://www.cisco.com/c/en/us/support/docs/ip/enhanced-interior-gateway-routing-protocol-eigrp/16406-eigrp-toc.html Cisco EIGRP official white paper, Sep 09, 2005]</ref> 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 (Internet)\|autonomous system]], and DUAL responds to changes in the routing topology and dynamically adjusts the routing tables of the router automatically.

	EIGRP uses a [[~~Enhanced_Interior_Gateway_Routing_Protocol~~#~~Feasibility_condition~~\|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.		EIGRP uses a [[Enhanced Interior Gateway Routing Protocol#Feasibility condition\|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 <ref>[http://www.soe.ucsc.edu/research/ccrg/publications/jj.dual.ton93.pdf 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]</ref> invokes a diffusing computation <ref>[http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD687a.PDF 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]</ref> 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.		When no feasible route to a destination is available, the DUAL algorithm <ref>[http://www.soe.ucsc.edu/research/ccrg/publications/jj.dual.ton93.pdf 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]</ref> invokes a diffusing computation <ref>[http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD687a.PDF 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]</ref> 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.

Dough34: fix capitalization

2018-02-04T16:34:26Z

fix capitalization

← Previous revision		Revision as of 16:34, 4 February 2018
Line 3:		Line 3:
	EIGRP uses a [[Enhanced_Interior_Gateway_Routing_Protocol#Feasibility_condition\|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.		EIGRP uses a [[Enhanced_Interior_Gateway_Routing_Protocol#Feasibility_condition\|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 <ref>[http://www.soe.ucsc.edu/research/ccrg/publications/jj.dual.ton93.pdf 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]</ref> invokes a ~~Diffusing~~ ~~Computation~~ <ref>[http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD687a.PDF 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]</ref> 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.		When no feasible route to a destination is available, the DUAL algorithm <ref>[http://www.soe.ucsc.edu/research/ccrg/publications/jj.dual.ton93.pdf 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]</ref> invokes a diffusing computation <ref>[http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD687a.PDF 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]</ref> 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.

	==Operation==		==Operation==

L8 ManeValidus: added internal links with Autonomous_system_(Internet) & Enhanced_Interior_Gateway_Routing_Protocol#Feasibility_condition & Link-state_routing_protocol & Metrics_(networking) & Network_packet

2017-04-06T00:18:30Z

added internal links with Autonomous_system_(Internet) & Enhanced_Interior_Gateway_Routing_Protocol#Feasibility_condition & Link-state_routing_protocol & Metrics_(networking) & Network_packet

← Previous revision		Revision as of 00:18, 6 April 2017
Line 1:		Line 1:
	'''DUAL''', the '''D'''iffusing '''U'''pdate '''AL'''gorithm, is the [[algorithm]] used by [[Cisco]]'s [[EIGRP]]<ref>[http://www.cisco.com/c/en/us/support/docs/ip/enhanced-interior-gateway-routing-protocol-eigrp/16406-eigrp-toc.html Cisco EIGRP official white paper, Sep 09, 2005]</ref> 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]]. According to Cisco, 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.		'''DUAL''', the '''D'''iffusing '''U'''pdate '''AL'''gorithm, is the [[algorithm]] used by [[Cisco]]'s [[EIGRP]]<ref>[http://www.cisco.com/c/en/us/support/docs/ip/enhanced-interior-gateway-routing-protocol-eigrp/16406-eigrp-toc.html Cisco EIGRP official white paper, Sep 09, 2005]</ref> 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]]. According to Cisco, the full name of the algorithm is DUAL [[finite-state machine]] (DUAL FSM). EIGRP is responsible for the routing within an [[Autonomous_system_(Internet)\|autonomous system]] and DUAL responds to changes in the routing topology and dynamically adjusts the routing tables of the router automatically.

	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.		EIGRP uses a [[Enhanced_Interior_Gateway_Routing_Protocol#Feasibility_condition\|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 <ref>[http://www.soe.ucsc.edu/research/ccrg/publications/jj.dual.ton93.pdf 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]</ref> invokes a Diffusing Computation <ref>[http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD687a.PDF 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]</ref> 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.		When no feasible route to a destination is available, the DUAL algorithm <ref>[http://www.soe.ucsc.edu/research/ccrg/publications/jj.dual.ton93.pdf 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]</ref> invokes a Diffusing Computation <ref>[http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD687a.PDF 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]</ref> 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.

	==Operation==		==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:		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_protocol\|link-state routing protocols]]. In EIGRP, the information exchanged includes the routes, the "[[Metrics_(networking)\|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:

	* '''Neighbor table''' contains information on all other directly connected routers. A separate table exists for each supported protocol (IP, IPX, etc.). Each entry corresponds to a neighbour with the description of network interface and address. In addition, a timer is initialized to trigger the periodic detection of whether the connection is alive. This is achieved through "Hello" packets. If a "Hello" packet is not received from a neighbor for a specified time period, the router is assumed down and removed from the neighbor table.		* '''Neighbor table''' contains information on all other directly connected routers. A separate table exists for each supported protocol (IP, IPX, etc.). Each entry corresponds to a neighbour with the description of network interface and address. In addition, a timer is initialized to trigger the periodic detection of whether the connection is alive. This is achieved through "Hello" [[Network_packet\|packets]]. If a "Hello" packet is not received from a neighbor for a specified time period, the router is assumed down and removed from the neighbor table.
	* '''Topology table''' contains the metric (cost information) of all routes to any destination within the autonomous system. This information is received from neighboring routers contained in the Neighbor table. The primary (successor) and secondary (feasible successor) routes to a destination will be determined with the information in the topology table. Among other things, each entry in the topology table contains the following:		* '''Topology table''' contains the metric (cost information) of all routes to any destination within the autonomous system. This information is received from neighboring routers contained in the Neighbor table. The primary (successor) and secondary (feasible successor) routes to a destination will be determined with the information in the topology table. Among other things, each entry in the topology table contains the following:
	:"FD (Feasible Distance)": The calculated metric of a route to a destination within the autonomous system.		:"FD (Feasible Distance)": The calculated metric of a route to a destination within the autonomous system.

JanmanX: Added abbreviation RD to example.

2015-10-01T12:35:03Z

Added abbreviation RD to example.

← Previous revision		Revision as of 12:35, 1 October 2015
Line 37:		Line 37:
	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:		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 from routers C and D respectively to router A. The following are the results:		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		:Destination: Router A
	:via D: RD(4)		:via D: RD(4)

Lbparker40 at 14:23, 18 June 2014

2014-06-18T14:23:22Z

← Previous revision		Revision as of 14:23, 18 June 2014
Line 1:		Line 1:
	'''DUAL''', the '''D'''iffusing '''U'''pdate '''AL'''gorithm, is the [[algorithm]] used by [[Cisco]]'s [[EIGRP]]<ref>[http://www.cisco.com/c/en/us/support/docs/ip/enhanced-interior-gateway-routing-protocol-eigrp/16406-eigrp-toc.html, Cisco EIGRP official white paper, Sep 09, 2005]</ref> 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]]. According to Cisco, 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.		'''DUAL''', the '''D'''iffusing '''U'''pdate '''AL'''gorithm, is the [[algorithm]] used by [[Cisco]]'s [[EIGRP]]<ref>[http://www.cisco.com/c/en/us/support/docs/ip/enhanced-interior-gateway-routing-protocol-eigrp/16406-eigrp-toc.html Cisco EIGRP official white paper, Sep 09, 2005]</ref> 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]]. According to Cisco, 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.

	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.		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.

Lbparker40 at 14:21, 18 June 2014

2014-06-18T14:21:07Z

← Previous revision		Revision as of 14:21, 18 June 2014
Line 1:		Line 1:
	'''DUAL''', the '''D'''iffusing '''U'''pdate '''AL'''gorithm, 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]]. According to Cisco, 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.		'''DUAL''', the '''D'''iffusing '''U'''pdate '''AL'''gorithm, is the [[algorithm]] used by [[Cisco]]'s [[EIGRP]]<ref>[http://www.cisco.com/c/en/us/support/docs/ip/enhanced-interior-gateway-routing-protocol-eigrp/16406-eigrp-toc.html, Cisco EIGRP official white paper, Sep 09, 2005]</ref> 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]]. According to Cisco, 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.

	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.		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.

198.200.181.195 at 00:50, 13 November 2013

2013-11-13T00:50:06Z

← Previous revision		Revision as of 00:50, 13 November 2013
Line 1:		Line 1:
	'''DUAL''', the '''D'''iffusing '''U'''pdate '''AL'''gorithm, 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~~]] and [[Robert Johnson~~]] at [[SRI International]]. According to Cisco, 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.		'''DUAL''', the '''D'''iffusing '''U'''pdate '''AL'''gorithm, 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]]. According to Cisco, 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.

	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.		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.

198.200.181.195 at 00:48, 13 November 2013

2013-11-13T00:48:17Z

← Previous revision		Revision as of 00:48, 13 November 2013
Line 1:		Line 1:
	'''DUAL''', the '''D'''iffusing '''U'''pdate '''AL'''gorithm, 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]]. According to Cisco, 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.		'''DUAL''', the '''D'''iffusing '''U'''pdate '''AL'''gorithm, 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]] and [[Robert Johnson]] at [[SRI International]]. According to Cisco, 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.

	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.		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.

Michael Hardy: page ranges require an en-dash, not a hyphen; see WP:MOS; similarly "Bellman–Ford" requires an en-dash.

2013-07-21T15:21:20Z

page ranges require an en-dash, not a hyphen; see WP:MOS; similarly "Bellman–Ford" requires an en-dash.

← Previous revision		Revision as of 15:21, 21 July 2013
Line 3:		Line 3:
	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.		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 <ref>[http://www.soe.ucsc.edu/research/ccrg/publications/jj.dual.ton93.pdf 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]</ref> invokes a Diffusing Computation <ref>[http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD687a.PDF 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]</ref> 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.		When no feasible route to a destination is available, the DUAL algorithm <ref>[http://www.soe.ucsc.edu/research/ccrg/publications/jj.dual.ton93.pdf 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]</ref> invokes a Diffusing Computation <ref>[http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD687a.PDF 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]</ref> 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.

	==Operation==		==Operation==
Line 24:		Line 24:
	''Legend:''		''Legend:''
	:+ = Router		:+ = Router
	:- or \| = Link		:− or \| = Link
	:(X) = Metric of link		:(X) = Metric of link