Link-State Routing
Protocols
Routing Protocols and Concepts – Chapter 10
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
ITE PC v4.0
Chapter 1
1
Objectives
 Describe the basic features & conce
p
ts of link-state
p
routing protocols.
– Distance vector routing protocols are like road signs
because routers must make preferred path decisions based
because

routers

must

make

preferred

path

decisions

based

on a distance or metric to a network.
– Link-state routing protocols are more like a road map
because they create a topological map of the network and
because

they

create

a

topological

map

of

the

network

and

each router uses this map to determine the shortest path to
each network.
The ultimate objective is that every router receives all of the
–
The

ultimate


objective

is

that

every

router

receives

all

of

the

link-state information about all other routers in the routing
area. With this link-state information, each router can create
its own topological map of the network and independently
its

own

topological

map


of

the

network

and

independently

calculate the shortest path to every network.
 List the benefits and requirements of link-state routing
ITE PC v4.0
Chapter 1
2
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
protocols.
Link-State Routing

Link state routing protocols

Link

state

routing

protocols
-Also known as shortest path first algorithms
-These protocols built around Dijkstra’s SPF

OSPF ill b di d i Ch t 11 d IS
IS ill b di d i CCNP
ITE PC v4.0
Chapter 1
3
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
OSPF
w
ill

b
e
di
scusse
d

i
n
Ch
ap
t
er
11
, an
d

IS
-
IS
w

ill

b
e
di
scusse
d

i
n
CCNP
.
Link-State Routing
 Dikjstra’s algorithm also known as the shortest path first
(SPF) algorithm
Thi l ith l t t l h th f
–
Thi
s a
l
gor
ith
m accumu
l
a
t
es cos
t
s a
l

ong eac
h
pa
th
,
f
rom
source to destination.
ITE PC v4.0
Chapter 1
4
© 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
5
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing Process
 How routers using Link State Routing Protocols reach convergence
1
Each routers learns about its own directly connected networks
1
.
Each

routers

learns


about

its

own

directly

connected

networks
– interface is in the up state
2. Each router is responsible for meeting its neighbors on directly
td t k
connec
t
e
d
ne
t
wor
k
s
– exchange hello packet to other directly connected link state routers.
3. Each router builds a Link-State Packet
(
LSP
)
containin

g
the state of
() g
each directly connected link
– recording all the pertinent information about each neighbor, including
neighbor ID, link type, and bandwidth.
4. Each router floods the LSP to all neighbors, who then store all LSPs
received in a database.
– Each router stores a copy of each LSP received from its neighbors in
a local database
a

local

database
.
5. Each router uses the database to construct a complete map of the
topology and computes the best path to each destination network.
Th SPF l ith i d t t t th f th t l d
ITE PC v4.0
Chapter 1
6
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
–
Th
e
SPF
a
l
gor

ith
m
i
s use
d

t
o cons
t
ruc
t

th
e map o
f

th
e
t
opo
l
ogy an
d

to determine the best path to each network.
Link-State Routing:
Step 1 – Learn about directly connected Networks
 Link
Thi
s

i
s

a
n in
te
rf
ace

o
n
a

ssa teaceo a
router

Link state
Link

state
This is the information
about the state of the
about

the

state

of


the

links
ITE PC v4.0
Chapter 1
7
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link
-
State Routing:
Link
-
State

Routing:

step 2 - Sending Hello Packets to Neighbors

Link state routing protocols use a hello protocol

Link

state

routing

protocols

use


a

hello

protocol
Purpose of a hello protocol:
Tdi ihb (tht th
-
T
o
di
scover ne
i
g
hb
ors
(th
a
t
use
th
e same
link state routing protocol) on its link
ITE PC v4.0
Chapter 1
8
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link
-
State Routing:


Connected interfaces that are
Link
-
State

Routing:

step 2 - Sending Hello Packets to Neighbors

Connected

interfaces

that

are

using the same link state
routing protocols will exchange
routing

protocols

will

exchange

hello packets.


Once routers learn it has

Once

routers

learn

it

has

neighbors they form an
adjace
n
cy
adjace cy
– 2 adjacent neighbors will
exchange hello packets
– These packets will serve as a
keep alive function
ITE PC v4.0
Chapter 1
9
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link
-
State Routing:

Contents of LSP:

Link
-
State

Routing:

step 3 - Building the Link State Packet (LSP)

Contents

of

LSP:
– State of each directly connected link
– Includes information about
neighbors such as neighbor ID link
neighbors

such

as

neighbor

ID
,
link

type, & bandwidth.
 A simplified version of the LSPs from

R1 is:
1. R1; Ethernet network 10.1.0.0/16;
Cost 2
2. R1 -> R2; Serial point-to-point
network; 10.2.0.0/16; Cost 20
3. R1 -> R3; Serial point-to-point
network; 10.3.0.0/16; Cost 5
4. R1 -> R4; Serial point-to-point
/C
ITE PC v4.0
Chapter 1
10
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
network; 10.4.0.0
/
16;
C
ost 20
Link
-
State Routing:

Once LSP are created they are
Link
-
State

Routing:

step 4 - Flooding LSPs to Neighbors


Once

LSP

are

created

they

are

forwarded out to neighbors.
–
E
ac
h r
ou
t
e
r fl
oods
it
s
link-
s
t
a
t

e

ac ou e oods s
sae
information to all other link-state
routers in the routing area.
Whenever a router receives an LSP
–
Whenever

a

router

receives

an

LSP

from a neighboring router, it
immediately sends that LSP out all
other interfaces except the interface
other

interfaces

except

the


interface

that received the LSP.
–
This
p
rocess creates a floodin
g
effect
pg
of LSPs from all routers throughout
the routing area.
ITE PC v4.0
Chapter 1
11
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link
-
State Routing:
LSP t t d th f ll i diti
Link
-
State

Routing:

step 4 - Flooding LSPs to Neighbors

LSP

s are sen
t
ou
t
un
d
er
th
e
f
o
ll
ow
i
ng con
diti
ons
– Initial router start up or routing process
Wh th i h i t l
–
Wh
en
th
ere
i
s a c
h
ange
i
n

t
opo
l
ogy
• including a link going down or coming up, or a neighbor
ad
j
acenc
y
bein
g
established or broken
jyg
ITE PC v4.0
Chapter 1
12
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link
-
State Routing:

Routers use a database to
Link
-
State

Routing:

step 5 - Constructing a link state data base


Routers

use

a

database

to

construct a topology map of the
network
–After each router has propagated its
own LSPs using the link-state
flooding process each router will
flooding

process
,
each

router

will

then have an LSP from every link-
state router in the routing area.
–
These LSPs are stored in the link-
state database.

–
Each router in the routing area can
Each

router

in

the

routing

area

can

now use the SPF algorithm to
construct the SPF trees that you saw
earlier
ITE PC v4.0
Chapter 1
13
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
earlier
.
Link
-
State Routing:
Link
-

State

Routing:

step 5 - Constructing a link state data base
router R1 has learned the link-state
information for each router in its
r
out
in
g

a
r
ea
.
routing

area.

With a com
p
lete link-state database, R1
p
can now use the database and the
shortest path first (SPF) algorithm to
calculate the preferred path or shortest
p
ath to each network.
p

ITE PC v4.0
Chapter 1
14
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link
-
State Routing:

Process begins by examining R2
’
s LSP information
Link
-
State

Routing:

Example - How R1 constructs its SPF tree.
Process

begins

by

examining

R2 s

LSP


information
–R1 can ignore the first LSP, because R1 already knows that it is
connected to R2 on network 10.2.0.0/16 with a cost of 20.
R1 th d LSP d t li k f R2 t th
–
R1
can use
th
e secon
d

LSP
an
d
crea
t
e a
li
n
k

f
rom
R2

t
o ano
th
er
router, R5, with the network 10.9.0.0/16 and a cost of 10. This

information is added to the SPF tree.
Using the third LSP R1 has learned that R2 has a network
–
Using

the

third

LSP
,
R1

has

learned

that

R2

has

a

network

10.5.0.0/16 with a cost of 2 and with no neighbors. This link is
added to R1's SPF tree.
ITE PC v4.0

Chapter 1
15
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link
-
State Routing:

Process begins by examining R3
’
s LSP information
Link
-
State

Routing:

Example - How R1 constructs its SPF tree.
Process

begins

by

examining

R3 s

LSP

information

–R1 can ignore the first LSP, because R1 already knows that it is
connected to R3 on network 10.3.0.0/16 with a cost of 5.
R1 th d LSP d t li k f R3 t th
–
R1
can use
th
e secon
d

LSP
an
d
crea
t
e a
li
n
k

f
rom
R3

t
o
th
e
router R4, with the network 10.7.0.0/16 and a cost of 10. This
information is added to the SPF tree.

Using the third LSP R1 has learned that R3 has a network
–
Using

the

third

LSP
,
R1

has

learned

that

R3

has

a

network

10.6.0.0/16 with a cost of 2 and with no neighbors. This link is
added to R1's SPF tree.
ITE PC v4.0
Chapter 1

16
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link
-
State Routing:

Process begins by examining R4
’
s LSP information
Link
-
State

Routing:

Example - How R1 constructs its SPF tree.
Process

begins

by

examining

R4 s

LSP

information
–R1 can ignore the first LSP because R1 already knows that it is

connected to R4 on network 10.4.0.0/16 with a cost of 20.
–
R1 can also ignore the second LSP because SPF has already learned
R1

can

also

ignore

the

second

LSP

because

SPF

has

already

learned

about the network 10.6.0.0/16 with a cost of 10 from R3.
–However, R1 can use the third LSP to create a link from R4 to the router
R5, with the network 10.10.0.0/16 and a cost of 10. This information is

dd d t th SPF t
a
dd
e
d

t
o
th
e
SPF

t
ree.
–Using the fourth LSP, R1 learns that R4 has a network 10.8.0.0/16 with a
cost of 2 and with no neighbors. This link is added to R1's SPF tree.
ITE PC v4.0
Chapter 1
17
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link
-
State Routing:

Process begins by examining R5
’
s LSP information
Link
-
State


Routing:

Example - How R1 constructs its SPF tree.
Process

begins

by

examining

R5 s

LSP

information
–R1 can ignore the first two LSPs (for the networks 10.9.0.0/16 and
10.10.0.0/16), because SPF has already learned about these links
and added them to the SPF tree.
–R1 can process the third LSP learning that R5 has a network
10.11.0.0/16 with a cost of 2 and with no neighbors. This link is
added to the SPF tree for R1.
ITE PC v4.0
Chapter 1
18
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing

Determining the shortest path

Determining

the

shortest

path
–The shortest path to a destination
determined by adding the costs & finding the
lowest cost
•Network 10.5.0.0/16 via R2 serial 0/0/0
at a cost of 22
•Network 10.6.0.0/16 via R3 serial 0/0/1
at a cost of 7
at

a

cost

of

7
•Network 10.7.0.0/16 via R3 serial 0/0/1
at a cost of 15
•Network 10.8.0.0/16 via R3 serial 0/0/1
at a cost of 17
•Network 10.9.0.0/16 via R2 serial 0/0/0
at a cost of 30
N t k101000/16 i R3 i l0/0/1

•
N
e
t
wor
k

10
.
10
.
0
.
0/16
v
i
a
R3
ser
i
a
l

0/0/1

at a cost of 25
•Network 10.11.0.0/16 via R3 serial 0/0/1
at a cost of 27
Only the LANs are shown in
the table, but SPF can also be

used to determine the
ITE PC v4.0
Chapter 1
19
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
used

to

determine

the

shortest path to each WAN
link network.
Link-State Routing
O th SPF l ith h

O
nce
th
e
SPF
a
l
gor
ith
m
h
as

determined the shortest path
routes, these routes are placed in
routes,

these

routes

are

placed

in

the routing table.

The routing table will also include
The

routing

table

will

also

include

all directly connected networks

and routes from any other
sources, such as static routes.
Packets will now be forwarded
according to these entries in the
according

to

these

entries

in

the

routing table.
ITE PC v4.0
Chapter 1
20
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing Protocols
Advantages of a Link
State Routing Protocol
Advantages

of

a


Link
-
State

Routing

Protocol
Routing
protocol
Builds
Topological
map
Router can
independently
determine the
shortest path
Convergence
Event driven
routing
updates
Use
of
LSP
to every
network.
Distance
No
No
Slow
Generally No

No
Distance

vector
No
No
Slow
Generally

No
No
Link State Yes Yes Fast Generally Yes Yes
ITE PC v4.0
Chapter 1
21
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing Protocols
 There are several advantages of link-state routing protocols compared to distance vector routing
tl
pro
t
oco
l
s.
 Builds a Topological Map
• Link-state routing protocols create a topological map, or SPF tree of the network topology.
•
Using the SPF tree each router can independently determine the shortest path to every network
Using


the

SPF

tree
,
each

router

can

independently

determine

the

shortest

path

to

every

network
.
• Distance vector routing protocols do not have a topological map of the network.
•Routers implementing a distance vector routing protocol only have a list of networks, which includes

the cost (distance) and next-hop routers (direction) to those networks.
 Fast Convergence
• When receiving a Link-state Packet (LSP), link-state routing protocols immediately flood the LSP out all
interfaces except for the interface from which the LSP was received.
• A router using a distance vector routing protocol needs to process each routing update and update its
ti t bl b f fl di th t th i t f ith t i d d t
rou
ti
ng
t
a
bl
e
b
e
f
ore
fl
oo
di
ng
th
em ou
t
o
th
er
i
n
t

er
f
aces, even w
ith

t
r
i
ggere
d
up
d
a
t
es.
 Event-driven Updates
• After the initial flooding of LSPs, link-state routing protocols only send out an LSP when there is a change
in the topology. The LSP contains only the information regarding the affected link.
• Unlike some distance vector routing protocols, link-state routing protocols do not send periodic updates.
 Hierarchical Design
• Link-state routing protocols such as OSPF and IS-IS use the concept of areas. Multiple areas create a
hierarchical design to networks allowing for better route aggregation (summarization) and the isolation of
ITE PC v4.0
Chapter 1
22
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
hierarchical

design


to

networks
,
allowing

for

better

route

aggregation

(summarization)

and

the

isolation

of

routing issues within an area.
Link-State Routing Protocols
Ri tf i liktt ti tl
R
equ
i

remen
t
s
f
or us
i
ng a
li
n
k
s
t
a
t
e rou
ti
ng pro
t
oco
l
 Memory requirements
T i ll li k t t ti t l
–
T
yp
i
ca
ll
y
li

n
k
s
t
a
t
e rou
ti
ng pro
t
oco
l
s use more memory
 Processing Requirements
MCPU ii idfliktt ti
–
M
ore
CPU
process
i
ng
i
s requ
i
re
d
o
f


li
n
k
s
t
a
t
e rou
ti
ng
protocols
 Bandwidth Re
q
uirements
q
– Initial startup of link state routing protocols can consume lots
of bandwidth
This should only occur during initial startup of routers but can
–
This

should

only

occur

during

initial


startup

of

routers
,
but

can

also be an issue on unstable networks.
ITE PC v4.0
Chapter 1
23
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
Link-State Routing Protocols
 Modern link-state routing protocols are designed to
ii i h ff CPU d
m
i
n
i
m
i
ze t
h
e e
ff
ects on memory,

CPU
, an
d

bandwidth.
• The use and configuration of multiple areas can reduce
the size of the link
-
state databases. Multiple areas can
the

size

of

the

link
state

databases.

Multiple

areas

can

also limit the amount of link-state information flooding in
a routing domain and send LSPs only to those routers

that need them.
•
For example when there is a change in the topology
For

example
,
when

there

is

a

change

in

the

topology
,
only those routers in the affected area receive the LSP
and run the SPF algorithm.
• This can help isolate an unstable link to a specific area
in the routing domain
in

the


routing

domain
.
 In the figure, If a network in Area 51 goes down, the
LSP with the information about this downed link is
only flooded to other routers in that area.
only

flooded

to

other

routers

in

that

area.

• Routers in other areas will learn that this route is down,
but this will be done with a type of link-state packet that
does not cause them to rerun their SPF algorithm.
Note: Multiple areas
with OSPF and IS-IS
ITE PC v4.0

Chapter 1
24
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public
are discussed in
CCNP
Link-State Routing Protocols

2 link state routing protocols used for routing IP

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
25
© 2007 Cisco Systems, Inc. All rights reserved. Cisco Public