Distance vector: RIP v1&2, IGRP, EIGRP, DEC’s DNA Phase IV, Appletalk RTMP
Common characteristics: Periodic updates (except EIGRP), neighbors, b/c updates (except RIPv2 and EIGRP), Full table
Link State: OSPF, ISIS, DEC’s DNA Phase V, NLSP. Uses Hello packets.
- LSA (not full routing table) use Seq and ACK #s.
Sequencing Algorithms:
Linear -> 1—————- X (where X is a very large #). Issue: router restart will reinitialize sequencing. Soln: Neighbor on receipt of a lower seq # sends its LSA (contains the last seq#) to that router. ISIS
Circular Sequencing. Eliminates need for neighbor to send an LSA to reinitialize sequencing. Cyclic 0 to n. Uses: if a>b; a-b < or = n/2 => a is latest. If a<b, b-a > n/2 => a is latest.
Lollipop Shaped: hybrid. (-N+1) to 0 : Linear, 0 to (N-2) is circular. OSPFv1
Current version of OSPF(v2) uses a Linear model (-N+1)——–0——-(N-2)
Aging: Set to 1 when LSA is created and incremented as a function of time at each router. It defines the MaxAgeDiff. If 2 LSAs with same seq# are received and if the difference in their ages is greater than MaxAgeDiff, the newer one is added.
Link State Database = Router Link Information + Stub n/w information
Dijkstra’s Algorithm: Database Tree <- Candidate <- Link state
- Router builds a SPF tree by first adding itself as a root node.
- It then creates a list of all directly connected neighbors and associated costs.
- Lowest cost link to a neighbor becomes a branch.
- This router’s neighbors are then added to the list
- The list is checked for duplicates and higher cost paths to dupes are dropped
- The lowest cost router is added to the tree and its neighbors are added to the list
- Process is repeated
Stub info is then added and the route is injected into the routing table.
Link State Routing Protocol Concerns: High CPU, B/w, memory – mitigated by areas.
EGPs: BGP, EGP, ISO’s IDRP, NLSP Level3 Routing.
