© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
ITE PC v4.0
Chapter 1 1
Link-State Routing
Protocols
Routing Protocols and
Concepts – Chapter 10
ITE PC v4.0
Chapter 1 2© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Objectives
 Describe the basic features & concepts of link-state
routing protocols.
 List the benefits and requirements of link-state routing
protocols.
ITE PC v4.0
Chapter 1 3© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Introduction
ITE PC v4.0
Chapter 1 4© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
 Link state routing protocols
-Also known as shortest path first algorithms
-These protocols built around Dijkstra’s
SPF
ITE PC v4.0
Chapter 1 5© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
Dikjstra’s algorithm also known as the shortest path first
(SPF) algorithm
ITE PC v4.0
Chapter 1 6© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
 The shortest path to a destination is not necessarily the
path with the least number of hops
ITE PC v4.0
Chapter 1 7© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
Link-State Routing Process
 How routers using Link State Routing Protocols reach
convergence
-Each routers learns about its own directly connected networks
-Link state routers exchange hello packet to “meet” other
directly
connected link state routers.
-Each router builds its own Link State Packet (LSP) which
includes information about neighbors such as neighbor ID, link
type, & bandwidth.
-After the LSP is created the router floods it to all neighbors who
then store the information and then forward it until all routers
have the same information.
-Once all the routers have received all the LSPs, the routers
then construct a topological map of the network which is used to
determine the best routes to a destination
ITE PC v4.0
Chapter 1 8© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
 Directly Connected Networks
 Link
This is an interface on a
router
 Link state
This is the information
about the state of the
links
ITE PC v4.0
Chapter 1 9© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
Sending Hello Packets to Neighbors
 Link state routing protocols use a hello protocol
Purpose of a hello protocol:
-To discover neighbors (that use the same
link state routing protocol) on its link
ITE PC v4.0
Chapter 1 10© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
Sending Hello Packets to
Neighbors
 Connected interfaces that are using
the same link state routing protocols
will exchange hello packets.
 Once routers learn it has neighbors
they form an adjacency
-2 adjacent neighbors will
exchange hello packets
-These packets will serve as a
keep alive function
ITE PC v4.0
Chapter 1 11© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
Building the Link State Packet
 Each router builds its own
Link State Packet (LSP)
Contents of LSP:
-State of each directly
connected link
-Includes information
about neighbors such as
neighbor ID, link type, &
bandwidth.
ITE PC v4.0
Chapter 1 12© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
Flooding LSPs to Neighbors
 Once LSP are created they are forwarded out to
neighbors.
-After receiving the LSP the neighbor continues to
forward it throughout routing area.
ITE PC v4.0
Chapter 1 13© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
 LSPs are sent out under the following conditions
-Initial router start up or routing process
-When there is a change in topology
ITE PC v4.0
Chapter 1 14© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
Constructing a link state data base
 Routers use a database to construct a topology map of
the network
ITE PC v4.0
Chapter 1 15© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
ITE PC v4.0
Chapter 1 16© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
Shortest Path First (SPF) Tree
 Building a portion of the SPF tree
Process begins by examining R2’s LSP information
-R1 ignores 1st LSP
Reason: R1 already knows it’s connected to R2
ITE PC v4.0
Chapter 1 17© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
 Building a portion of the SPF tree
-R1 uses 2nd LSP
Reason: R1 can create a link from R2 to R5.
This information is added to R1’s SPF tree
ITE PC v4.0
Chapter 1 18© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
 Building a portion of the SPF tree
-R1 uses 3rd LSP
Reason: R1 learns that R2 is connected to
10.5.0.0/16.
This link is added to R1’s SPF tree.
ITE PC v4.0
Chapter 1 19© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
 Determining the shortest path
The shortest path to a destination determined by adding the
costs & finding the lowest cost
ITE PC v4.0
Chapter 1 20© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing
 Once the SPF algorithm has determined the shortest
path routes, these routes are placed in the routing
table.
ITE PC v4.0
Chapter 1 21© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing Protocols
Routing
protocol
Builds
Topological
map
Router can
independently
determine the
shortest path to
every network.
Convergence
A periodic/
event driven
routing updates
Use
of
LSP
Distance
vector
No No Slow Generally No No
Link State Yes Yes Fast Generally Yes Yes
Advantages of a Link-State Routing Protocol
ITE PC v4.0
Chapter 1 22© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing Protocols
Requirements for using a link state routing protocol
 Memory requirements
Typically link state routing protocols use more
memory
 Processing Requirements
More CPU processing is required of link state
routing protocols
 Bandwidth Requirements
Initial startup of link state routing protocols can
consume lots of bandwidth
ITE PC v4.0
Chapter 1 23© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing Protocols
 2 link state routing protocols used for routing IP
-Open Shortest Path First (OSPF)
-Intermediate System-Intermediate System (IS-IS)
ITE PC v4.0
Chapter 1 24© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Summary
 Link State Routing protocols are also known as
Shortest Path First protocols
 Summarizing the link state process
-Routers 1ST learn of directly connected networks
-Routers then say “hello” to neighbors
-Routers then build link state packets
-Routers then flood LSPs to all neighbors
-Routers use LSP database to build a network topology
map & calculate the best path to each destination
ITE PC v4.0
Chapter 1 25© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Summary
 Link
An interface on the router
 Link State
Information about an interface such as
-IP address
-Subnet mask
-Type of network
-Cost associated with link
-Neighboring routers on the link
ITE PC v4.0
Chapter 1 26© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Summary
 Link State Packets
After initial flooding, additional LSP are sent out
when a change in topology occurs
 Examples of link state routing protocols
-Open shortest path first
-IS-IS
ITE PC v4.0
Chapter 1 27© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public