Things to Remember about Link State Routing
- Link state protocols advertise a large amount of topological information about the network (tells what every metric is for every link in the network)
- Routers must calculate the metric (using Shortest path First Algorithm)
- Routers perform CPU intensive computations on the data.
- Discover neighbors before exchanging information.
|Process of Learning Routes:|
1. Each router discovers its neighbors on each interface, list kept in neighbors table.
2. Each router uses a reliable protocol to exchange topology information in its topology database.
3. Each router places the learned topology information in its topology database.
4. Each router then runs the SPF algorithm against its own topology database to calculate the best routes to each subnet in the database.
5. Each router finally places the best route to each subnet in the IP routing table.
OSPF Topology Database: Consists of lists of subnet numbers (links), list of routers (and links they are connected to).
- -> Uniquely identifier each router in this database using OSPF Router ID (RID)
- To select the RID
- The router first checks for any loopback interfaces that are up, and chooses the highest numeric IP address of those.
- If no loopback exists, router chooses highest IP address from interfaces that are up and up.
*Note: loopback interface is a virtual interface, configured with
interface loopback [interface #]
Each Router chooses RID when OSPY is initialized (during initial loading of IOS). If other interfaces come up after this, not used unless clear ip ospf process is issued.
Meeting OSPF Neighbors: Once router has assigned itself a RID, and some of its interfaces are up, the router is ready to meet its neighbors (connected routers).
- Can become neighbors if connected to same subnet
- Router multicasts OSPF Hello packets out each interface
- Hello message follows IP packet header (port = 89)
- Hello packets sent to 220.127.116.11 (all OSPF speaking routers)
- Routers learn several things from Hello Packets:
- RID, Area ID, Hello Interval, Dead Interval, router priority, designated router, backup designated router, and a list of neighbors sending router already knew about.
- To confirm that a Hello Packet was received, next Hello Message will include the sender’s RID within the list of neighbors.
-> Once router sees its RID included, two-way state achieved, and more detailed information can be exchanged.
|The following must match before routers become neighbors:|
|1. Subnet mask|
|2. Hello Interval|
|3. OSPF Area ID|
|4. Dead Interval|
|5. Subnet number (derived using the mask applied to the IP)|
Reducing Overhead Using Designated Routers
Sometimes Designated Routers (DR) are required before sending Database Description (DD) packets.
- DR’s always required on a LAN
- Sometimes required with Frame Relay/ATM (depending on topology/config)
After DR is elected, all updates flow through the Designated Router (DR). This means that the DR collects and distributes the routing updates to alleviate OSPF update congestion.
|Router decides if it needs to elect a DR depending on the network type.|
|* Point-to-point DOES NOT need a DR|
|* Broadcast (for LANs), always needs a DR|
- Non-broadcast Multiaccess (NBMA), for frame relay, sometimes needs DR, sometimes doesn’t. Has 5 different variations, configured with ip ospf network [type] command
** Since DR’s are so important, loss of one could cause delay in convergence, so Backup DR (BDR) is also needed. **
|Electing The Designated Router|
|To elect, neighboring routers hold an election, and look at two fields in the Hello Packet:|
|* Router that sends the highest OSPF priority becomes DR|
|* If there is a tie, the highest RID wins.|
|* To elect BDR, typically the second highest priority is used. *|
|* Priority setting of 0 means router will never be DR|
|* Range of valid priority values is 1-255 (to become a DR)|
|* If DR is elected, then another router comes online with a higher priority, this router will not become DR until both the DR and BDR fail.|
Once DR/BDR is elected:
1. Non-DR send updates to 18.104.22.168 (All OSPF DRs)
2. DR relays these messages to 22.214.171.124 (BDR does not forward, only receives)
3. Once router has exchanged its entire link state database, transition to Full State
Steady-State Operation: If Hello Interval is not received for [dead interval] amount of time, the router believes the neighbor has failed.
- Default dead timer is 4 times the hello interval
(10 second hello, 40 second dead timer)
- Router marks as "down" in its neighbor table
- Runs the dijkstra algorithm to calculate new routes, floods to inform other routers of failed link
|Loop Avoidance: Link state does not use SPF algorithm, but rather it relies on router broadcasting downed link immediately. This is the main reason for fast convergence time (distance vector uses hold time, split horizon, etc, while link state does not).|
Scaling OSPF: If network has many routers (~50 or more, a few hundred subnets), would result in:
* Slow convergence time
* Memory shortages/processor overloading
Scalability Solutions Include:
* OSPF Areas: Break up the network so that routers in one area know less topology information about the subnets in the other area, and don’t know about other routers at all.
* Border Router: OSPF Area Border Router (ABR), border between 2 different areas (sits in both areas).
* Makes other routers in same area view network as if it had fewer routers.
* Area 0 defined as backbone, OSPF designs hierarchical
** Note: doesn’t change of subnets know, just decrease of bytes/require memory to process updates **
Summary of Distance Vector and Link State
|Feature||Link State||Distance Vector|
|Convergence Time||Fast||Slow (loop avoidance features)|
|Loop avoidance||Built into protocol||Extra features such as route poisoning, split horizon|
|Memory/CPU||Can be large; good design can minimize||Low|
|Requires design effort for large networks||Yes||No|
|Public/Proprietary?||OSPF = public||RIP = public|
IGRP = Cisco proprietary
Balanced Hybrid Routing Protocol/EIGRP Concepts
EIGRP has some features that act like distance vector protocols, and some that act like link-state protocols.
Feature Comparison with IGRP:
|Both Cisco proprietary||EIGRP converges faster|
|Same logic for equal-cost paths||EIGRP sends routing info once to neighbor, then again only when update occurs.|
IGRP sends every 90 seconds.
|Metric’s identical (EIGRP just scales by multiplying by 256)||EIGRP can exchange for Novel IPX and AppleTalk, as well as IP|
EIGRP Processes and Tables: Follows three general steps to be able to add routes to routing table:
|1. EIGRP neighbor table: Routers discover other EIGRP routers that are attached to same subnet, form a neighbor relationship and keep a list in this table.|
a. show ip eigrp neighbor
|2. EIGRP topology table: Exchange of network topology information with known neighbors.|
a. show ip eigrp topology
|3. IP routing table: EIGRP analyzes topology information, puts lowest metric routes in this table.|
a. show ip route -or- show ip route eigrp
** EIGRP could have up to 9 tables, since it supports IP, IPX, and AppleTalk **
Hello Messages: Used to perform neighbor discovery, continually sent to notice when connectivity has failed.
- Interval determines how frequently it is sent
- LANs/Point-to-point connections = 5 seconds
- Multipoint WANS like Frame Relay = 60 seconds
Update Messages: Conveys topology information to neighbors.
- Sent out multicast address 126.96.36.199 if updating multiple routers
- Sent out Unicast address if single router updated
- Reliable messages sent out Reliable Transport Protocol (RTP)
Updating the Routing Table while Avoiding Loops
EIGRP keeps basic topological information (but not full information)
- Routes with feasible successor can be used immediately after route fails
- Routes without on require EIGRP to perform Query and Response process to confirm that no loop exists.
|Successors are in topology table, and are the best route (the route with lowest metric, which is also in routing table).|
Feasible Successors are in topology table, and are placed when the neighbor has a lower metric for its route.
Diffusing Update Algorithm (DUAL) is used in query and reply process, when both successor and feasible successor fail. Sends query to confirm route exists, reply verifies route.
|Discovers neighbors before exchanging routing information||Y||N||Y|
|Builds topology table in addition to routing table||Y||N||Y|
|Sends full routing table during update||N||Y||N|
|Requires distance vector loop avoidance features||N||Y||N|
|Uses DUAL Algorithm||Y||N||N|
IP Configuration Commands
|router ospf process-id||Global|
|network [ip address][wildcard mask] area [area id]||Router subcommand|
|ip ospf cost interface cost||Sets cost associated with interface|
|bandwidth [bandwidth]||Sets interface bandwidth|
|auto-cost reference bandwidth [number]||Router subcommand that sets the numerator in formula to calculate cost.|
|ip ospf hello [number]||Interface subcommand that sets Hello interval, and sets dead interval to 4 times this number.|
|ip ospf network [type]||Interface subcommand that defines the OSPF network type.|
IP OSPF Exec Commands
|show ip route [ip address]||Shows entire routing table, or subset if parameters entered.|
|show ip protocols||Shows routing protocol parameters and current timer values.|
|show ip ospf interface||List the area in which the router resides, and adjacent neighbors.|
|show ip ospf neighbor||Lists neighbors and current status with neighbors, per interface.|
|show ip route ospf||Lists routes in routing table learned by ospf.|
|debug ip ospf events||Issues log messages for each OSPF packet.|
|debug ip ospf packet||Issues log messages describing the contents of all OSPF packets.|
|debug ip ospf hello||Issues log messages describing Hellos and Hello failures.|
|OSPF Single-Area Configuration|
interface Ethernet 0/0
ip address 10.1.1.1 255.255.255.0
interface serial 0/0
ip address 10.1.4.1 255.255.255.0
router ospf 1
network 10.0.0.0 0.255.255.255 area 0
Network : What interfaces you want to include in OSPF configuration . Here 10.0.0.0
Wildcard Mask: If bit set to 1, "don’t care" bit (and 0 = include) . Here 0.255.255.255
Area : What area this router is in. Here area 0
OSPF Configuration with Multiple Areas
If router has interfaces in multiple areas:
router ospf 1
network 10.1.1.1 0.0.0.0 area 0
network 10.1.4.1 0.0.0.0 area 1
network 10.1.6.1 0.0.0.0 area 0
show ip ospf interface ->Details IP address, area , Router ID, Hello/Dead Interval, etc. for all interfaces
show ip route -> Shows all routes known by the router (C – Connected, O – OSPF)
show ip ospf neighbor -> Shows the routers ospf neighbors
Remember that the RID is that router’s highest IP address on a physical interface when OSPF starts running. Alternatively, if a loopback interface has been configured, OSPF uses the highest IP address on a loopback interface for the RID, even if that IP address is lower than some physical interface’s IP address.
|Mismatched Hello Intervals:|
* View neighbors:
show ip ospf neighbor ->Output doesn’t show neighbors
* Run debugging:
debug ip ospf hello -> Output shows mismatched Hello interval
* To identify the interface:
show ip ospf interface [interface] -> Will give you the hello interval
* To change hello interval for that interface:
ip ospf hello [count]
Configured exactly like IGRP, just switch "igrp" with "eigrp" in commands.
IP EIGRP Exec Commands
|show ip route [ip address]||Shows entire routing table.|
|show ip eigrp neighbors||Lists EIGRP neighbors and status.|
|show ip eigrp topology||Lists RIGRP topology table, including feasible successors/successors.|
|show ip route eigrp||Lists only EIGRP-learned routes|
|show ip eigrp traffic||Lists traffic statistics about EIGRP|
Other Key Points
- Letter "D" signifies EIGRP-learned routes
- All routers must be in same AS number (network x.x.x.x [AS number])
IGRP to EIGRP Migration
Feature of EIGRP called Automatic Redistribution
- Border router must be configured for both IGRP and EIGRP
- Both must use same AS number