We help IT Professionals succeed at work.

Routing algorithms

I am confused on what algorithms each Routing protocol uses?

Can someone summarize it for me?

RIP is a distance vector and uses Dijikstra and is a IGP

EIGRP is a hybrid protocol and uses DUAL and Dijikstra and is a IGP

OSPF is a link state protocol and uses SPF and Dijikstra  and is a IGP

BGP is a distance path and is a EGP ????

Where does Bellman Ford fit in?
Comment
Watch Question

Top Expert 2010
Commented:
>RIP is a distance vector and uses Dijikstra and is a IGP
RIP is a distance vector routing protocol that uses the Bellman-ford algorithm which operates in a very simple manner; routing by rumor: a router only knows what its neighbor tells it but does not know whether that information is valid and true. Yes, it is a IGP.


>EIGRP is a hybrid protocol and uses DUAL and Dijikstra and is a IGP
EIGRP is considered an advanced distance vector routing protocol that uses only DUAL and is Cisco proprietary.  The description that EIGRP is a hybrid is not correct from a principal point of view; yes, It has features of both distance vector & link state protocol, but does not operate nothing like a link state routing protocol; Cisco had used the hybrid terminology as a marketing term. Basically, in simple terms, DUAL allows a router to find an alternate paths without waiting on updates from other routers. yes, it is a IGP.


>OSPF is a link state protocol and uses SPF and Dijikstra  and is a IGP
OSPF is a link state protocol that uses the Dijkstra Shortest Path First Algorithm and is an IGP . The algorithm by itself is quite complicated; Simply put, the algorithm functions by constructing a shortest-path tree from a source node to all other nodes in the tree and then updates the routing table with the best path. Yes, it is a IGP


>BGP is a distance path and is a EGP ????
BGP is a path vector routing protocol because it tracks paths through autonomous systems and not paths through routers. The BGP path vector routing algorithm is somewhat similar to the distance vector algorithm in the sense that each router advertises the destinations it can reach to its neighboring router. However, instead of advertising networks in terms of a destination and the distance (Hence distance vector) to that destination, networks are advertised as destination addresses and path descriptions to reach those destinations.Yes, it is a EGP

Hope this helps
Billy
Commented:
A concepts to bear in mind with these protocols.

Vector protocols use split-horizon to prevent routing-loops because the do not "build" a complete picture of the entire network, while link-state protocols are not.

Author

Commented:
thanks rfc1180 and nazsky,

I don't hear J. J. Garcia-Aceves Luna's name much but that is who developed dual for EIGRP?

EIGRP's Dual can also do unequal cost load balancing because it uses the feasible distance<advertised distance to select loop free paths. And it is my understanding that EIGRP is the only protocol that can do unequal cost load balance without causing loops.
Top Expert 2010
Commented:
J. J. Garcia-Aceves Luna's is the individual that develeoped DUAL, I believe it was at SRI International.

>And it is my understanding that EIGRP is the only protocol that can do unequal cost load balance without >causing loops.
Correct: http://www.cisco.com/en/US/tech/tk365/technologies_tech_note09186a008009437d.shtml


Billy

Author

Commented:
I am trying to get the terminology down but it is not yet clear to me.

Maybe I don't have the right column names.



Routing       Algorithm       Type of protocol            Developers
Protocol

EIGRP         DUAL             Adv Distance Vector       J.J. Garcia-Aceves Luna/SRI

OSPF         SPF                 Link State                       Dijikstra

BGP            Dist. Vector   Path Vector                    Dijikstra

RIP              Dist. Vector   Distance Vector             Bellman-Ford

Author

Commented:
   
Routing       Algorithm       Type of protocol            Developers
Protocol

EIGRP         DUAL             Adv Distance Vector       J.J. Garcia-Aceves Luna/SRI

OSPF         SPF                 Link State                       Dijikstra

BGP           BGP                 Path Vector                    * See below

RIP             Bellman-Ford   Distance Vector             Bellman-Ford


*  Kirk Lougheed of Cisco systems developed a proprietary version of BGP for Cisco router equipment.

    * Jeff Honig from Cornell University and Dennis Ferguson from the University of Toronto developed a BGP version called gated to run on Unix computers, enabling Unix machines to become BGP routers, and then put the code in the public domain for others to use.

    * Yakov Rekhter from the IBM Thomas J. Watson Research Center wrote a BGP version for the NSFNET backbone.

Author

Commented:
Routing       Algorithm       Type of protocol            Developers
Protocol

EIGRP         DUAL              Adv Distance Vector       J.J. Garcia-Aceves Luna/SRI

OSPF         SPF                  Link State                       Dijikstra

BGP           Path Selection  Path Vector                    * See below

RIP             Bellman-Ford   Distance Vector             Bellman-Ford


*  Kirk Lougheed of Cisco systems developed a proprietary version of BGP for Cisco router equipment.

    * Jeff Honig from Cornell University and Dennis Ferguson from the University of Toronto developed a BGP version called gated to run on Unix computers, enabling Unix machines to become BGP routers, and then put the code in the public domain for others to use.

    * Yakov Rekhter from the IBM Thomas J. Watson Research Center wrote a BGP version for the NSFNET backbone.