Transcript Link State Protocols - Origins

LINK STATE PROTOCOLS
(contents)
• Disadvantages of the distance
vector protocols
• Link state protocols
• Why is a link state protocol better?
• The design of OSPF
• OSPF versus RIP
• Other link-state protocols
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
1
Disadvantages of the
Distance Vector Protocols
•
•
•
•
Slow convergence
Counting to infinity problem
Lack of variety of metrics
No possibility of hierarchical
routing
• Bad performance in large
networks
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
2
Link State Protocols
• developed to overcome the
disadvantages of the distance vector
protocols
• centralized database describes the
topology of the whole network
• calculation and routing are still
distributed
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
3
Characteristics
• information about adjacencies sent to
all routers only when there is a change
• each router maintains an identical
database
• a “shortest path” algorithm is used to
find the best route
• converge as quickly as databases can
be updated
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
4
Link State Database
A
1
B
2
C
4
3
5
D
6
E
Link State Announcement (LSA)
From A to B, link 1, distance = 1
number = 2
CEENet Workshop
Zagreb, 1997
From
A
A
B
B
B
C
C
D
D
E
E
E
To
B
D
A
C
E
B
E
A
E
B
C
D
Link Cost
1
1
3
1
1
1
2
1
4
1
2
1
5
1
3
1
6
1
4
1
5
1
6
1
Iskra Djonova-Popova
LS
seq.
num.
2
2
2
1
2
1
1
2
1
2
1
1
5
The Sequence Numbers
• modulo N numbering is used to avoid
very large numbers
• The sequence numbers vary between
1-N and N-2, where N = 231
– numbers -N and N-1 are not used
– at start, router uses the negative number 1-N
– when N-2 is reached, the next value will be 0
– the numbers will continue to cycle in the positive
segment of the sequence space
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
6
The Sequence Numbers 2
• the lollipop analogy is implemented
-N+1
N-2
0
N/2
• comparison of numbers
– if at least one number is negative - direct
– if both numbers are positive - cyclic
• if the difference is smaller than half a cycle, than the
bigger number is newer, otherwise the smaller
number is newer
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
7
The Flooding Protocol
• every node sends the message on
every link except the one from where
it received the message
• very fast and very reliable, but wastes
bandwidth
• used for ordinary traffic in military networks
• messages are sent only when there is a change or
every 45 minutes
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
8
The Flooding Protocol 2
A
B
XXX
2
C
4
3
link 1 breaks
5
D
6
E
• When a link breaks, A and B send the information to
all other nodes about state of link 1.
• Each node compares this entry in the data base, if it is
newer than the received message it ignores the
message, otherwise it updates the entry.
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
9
Bringing up Adjacency
A
B
XXX
2
C
4
5
3
D
XXX
E
link 1 and link 6 are down
and during that time link 2
breaks
When link 6 comes up it has
no information about link 2
• synchronizing databases via
comparison of sequence numbers
• “interesting records” - the sequence
numbers are different or not present in
database
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
10
Securing the Map Updates
• the flooding procedure includes hop-by-hop
acknowledgments
• the database description packets are
transmitted in a secure fashion
• each link state record is protected by a timer
and is removed from the database if a
refreshing packet does not arrive in due time
• all records are protected by checksum
• the messages can be authenticated, e. g. by
passwords
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
11
Shortest Path Routing
Algorithms
Determine the shortest path tree at
each node

Dijkstra’s algorithm
• complexity (MlogM)

Bellman-Ford algorithm
• complexity (MN)
CEENet Workshop
Zagreb, 1997
M - number of links
N - number of nodes
Iskra Djonova-Popova
12
Dijkstra’s Algorithm
A
1
B
2
C
4
3
5
D
6
Step
Initial
1
2
3
4
CEENet Workshop
Zagreb, 1997
E
N
{A}
{A, B}
{A, B, D}
{A, B, C, D}
{A, B, C, D, E}
Average time needed to compute the
routing table is about 200ms for
a 200 node network on a typical
router.
d(B)
1
1
1
1
1
d(C)

2
2
2
2
d(D)
1
1
1
1
1
d(E)

2
2
2
2
Iskra Djonova-Popova
13
Why Is a Link State protocol
Better?
• fast loop less convergence
• support of precise metrics and, if
needed multiple metrics
• support of a multiple paths to a
destination
• splitting very large networks in
areas
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
14
Link State Protocols
Disadvantages
• more memory required
– the link state database is needed in
addition to the routing tables
• much more complex procedure
– higher probability for a bug in the program
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
15
OSPF
• link state or SPF technology
• developed by OSPF Working Group
of IETF (not proprietary)
• designed for TCP/IP Internet
environment
• documented in rfc 1247
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
16
The Design of OSPF
• Strict separation of hosts and routers
• Broadcast networks such as Ethernet
or FDDI
• Non broadcast networks as X.25 or
ATM
• Splitting very large networks in areas
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
17
OSPF - Advantages
•
•
•
•
•
•
fast convergence
load balancing
low bandwidth utilization
optimal path utilization
authenticated routing updates
external routes
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
18
Fast convergence
R2
detection of failure
+
LSA/SPF
alternate path
N1
XXX
R1
N2
R3
primary path
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
19
Load Balancing by Multiple Path
equal or
proportional cost
multiple paths
R2
path 1
N1
N2
path 2
R1
R3
R4
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
20
Low Bandwidth Utilization
FDDI
Dual Ring
LSA
LSA
XXX
CEENet Workshop
Zagreb, 1997
• only changes propagated
• multicast on multi-access
broadcast network
• database synchronization
Iskra Djonova-Popova
21
Support of Multiple Metrics
Type of metrics : The algorithm requires:
•
•
•
•
throughput
delay
cost
reliability
CEENet Workshop
Zagreb, 1997
• several metrics for
each link
• different routing
tables for each link
• presenting selected
metric in the packet
Iskra Djonova-Popova
22
Optimal Path Utilization
Cost = 1
N2
FDDI
Dual Ring
FDDI
Dual Ring
N3
Cost = 1
R2
N1
Cost = 10
CEENet Workshop
Zagreb, 1997
R1
R3
Optimal path is determined
by the sum of the interface cost
R4
Cost = 10
N4
N5
Cost = 10
Iskra Djonova-Popova
23
Optimality Depends on Metric
R2
64Kbs/20ms
64 Kbs/20ms
min. delay
R1
1.5 Mbs / 295ms
max. throughput
R3
1.5 Mbs / 295ms
1.5 Mbs / 295ms
R4
CEENet Workshop
Zagreb, 1997
R5
Iskra Djonova-Popova
24
The Cost and The Bandwidth
formula: cost = 108 /bandwidth in bps
56 Kbps serial link
1758 Ethernet
64 Kbps serial link
1562 16 Mbps token ring 6
T1 (1.544 Mbps seral link)
65 FDDI
E1 (2.048 Mbps serial link)
48
4 Mbps token ring
25
CEENet Workshop
Zagreb, 1997
10
1
Iskra Djonova-Popova
25
Authenticated Routing
Updates
• Two possibilities are defined
– no authentication
– simple authentication using passwords
• network administrator can configure a different
password for each “network”, e. g. for each
point-to-point connection or each Ethernet
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
26
IP Subnetting Support
• Network number
• Variable length subnet mask
(VLSM)
• Discontiguous subnets
• Supernets/subnet prefixes
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
27
Route Summarization
Network
1
Next hop
R1
Network
Without
1, A
summarization
1, B
1, C
1,A; 1,B; 1,C
are stub networks
Next hop
R1
R1
R1
With
summarization
CEENet Workshop
Zagreb, 1997
R2
FDDI
Dual Ring
R1
1,A
1,B
Iskra Djonova-Popova
1,C
28
Route Summarization Benefit
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
29
Route Tagging
A
C
B
• Autonomous System B wants to
– propagate routes from A --> D, but not
propagate from C --> D
D
• OSPF tags routes with AS input
– the information can be used when
redistributing routs
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
30
TOS - Based Routing
• IP header supports 3 bit priority field
• IP header supports 4 special type of
services
– bandwidth
– delay
– reliability
– cost
• currently only TOS 0 is supported
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
31
External Routes
• one gateway (router) to external word
– only advertise default route
• several gateways
– pick one that is closest
– pick one that carry data more efficiently
• external routes are added to the
database as “gateway link state
records”
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
32
Broadcast Media Problems
• N neighbors - N(N-1)/2 adjacencies
• Not optimal
• Wasted bandwidth
• does not scale
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
33
Designated Router
• One per multi-access network
– generates network links advertisements
– assists in database synchronization
Designated router
CEENet Workshop
Zagreb, 1997
Backup designated router
Iskra Djonova-Popova
34
Broadcast Media
• select a designated router (DR)
• all routers become adjacent to DR
• exchange routing information with DR
via multicast
• DR updates all the neighbors
• less routing traffic generated
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
35
Non Broadcast Networks
• for N routers N(N-1)/2 virtual circuits
are needed to have full connectivity
– may be costly (does not scale)
• designated router plays the same roll
as in broadcast media
• instead of multicast the LSA’s are sent
point-to-point between the designated
router and all the others
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
36
Multiple Areas
• network increases => increase in
– link state database
– route computation
– volume of messages
• the solution to these problems
– split network into areas and the backbone
– the size of the routing proportional to the
size of the area, not the whole network
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
37
Hierarchical Structure
• backbone area needed to
connect all the other areas
Backbone
Area #0
Area #1
CEENet Workshop
Zagreb, 1997
Area #2
Area #3
Iskra Djonova-Popova
38
OSPF Areas
• group of
contiguous hosts
and networks
• one database per
area
• backbone area
(contiguous)
• virtual links
• inter-area routing
CEENet Workshop
Zagreb, 1997
Area 3
Area 2
area 0
Area 4
Area 1
Iskra Djonova-Popova
39
OSPF Areas 2
• a router has separate LS database
for each area that it belongs
• all routers belonging to the same
area have identical database
• SPF calculations are performed
separately for each area
• LSA flooding is bounded by area
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
40
Area Link State Database
• area database is composed of
– router links advertisements
– network links advertisements
– summary links advertisements
– AS external advertisements
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
41
Classification of Routers
IR
Area 2
area 0
IR/BR
to other AS
CEENet Workshop
Zagreb, 1997
ASBR
• IR - internal router
• ABR - area border
Area 3
router
• BR - backbone
router
ABR/BR
• ASBR autonomous
Area 1
system border
router
Iskra Djonova-Popova
42
OSPF Area Mapping
• area can be one or more networks
• area can be one or more subnets
• any combination of networks and
subnets possible (but bad in practice)
• for summarization subnets must be
grouped
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
43
The Link State• LS age
Header
– time since the LS record
31
0
LS age
options
•
options
LS type
Link State ID
Advertising Router
LS sequence number
LS checksum
CEENet Workshop
Zagreb, 1997
was first advertised
length
ET
– E - external links
– T - TOS (type 0 doesn’t
support any TOS
• LS type(router link,
network link, summary
link (IP network, summary
link, to a border router,
external link)
Iskra Djonova-Popova
44
The Router Links
0
..0….EB
..0..
31
number of links
Link ID
Link data
Type #TOS TOS 0 metric
TOS =x
0
TOS x metric
--TOS =z
CEENet Workshop
Zagreb, 1997
0
TOS z metric
• summarizes all
links that start
from the router
• bits 6 and 7 of
the first word
indicate the type
of the router
Iskra Djonova-Popova
45
The Network Links
0
31
Network mask
Attached router
--Attached router
• advertised by designated routers
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
46
The Summary Links
TOS
TOS =x
network mask
0
TOS 0 metric
0
TOS x metric
---
TOS =z
0
TOS z metric
• advertised by area-border routers
• the network mask is followed by a
set of metrics
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
47
The External Links
network mask
E, TOS
0
TOS 0 metric
external route tag 0
E,TOS =x
0
TOS x metric
external route tag x
-------
E,TOS =z
0
TOS z metric
external route tag z
CEENet Workshop
Zagreb, 1997
• advertised by
border routers
• required by
EGPs
• E indicates that
TOS is not
comparable with
that of internal
routes
Iskra Djonova-Popova
48
Protocols within OSPF
• common header
• hello protocol
• exchange protocol
• flooding protocol
• aging link state record
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
49
The Common Header
0
31
version (1)
type (1)
packet length (2)
Router ID (4)
Area ID (4)
Checksum (2)
autype (2)
Authentication (4)
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
50
0
The Hello Protocol
31
OSPF packet header, type = 1 (hello)
Network mask
Hello interval
Options
Dead interval
Priority
Designated router
Backup designated router
Neighbour
---Neighbour
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
51
The Exchange Protocol
0
31 • uses database
OSPF packet header, type = 2 (dd)
0
0
options 0I M MS
DD sequence number
Link state type
Link State ID
Advertising router
Link State sequence number
LS checksum
LS age
description packets
• asymmetric protocol
(master-slave)
• master sends
database description
packets
• slave sends the
acknowledgments
---CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
52
The Exchange Protocol 2
0
31
OSPF packet header, type = 3 (rq)
Link state type
Link State ID
Advertising router
----
CEENet Workshop
Zagreb, 1997
• request records
– send in case when
sequence number of
the LS is smaller
– the other router will
answer with a LS
update
Iskra Djonova-Popova
53
The Flooding Protocol
0
31
OSPF packet header, type = 4 (upd)
Number of advertisements
• when a link
changes state
Link State advertisements
---0
31
OSPF packet header, type = 5 (ack)
Link State advertisements
headers
---CEENet Workshop
Zagreb, 1997
– a router responsible for
that link issues a new
version of the link state
– the update is
retransmitted in regular
interval until an
acknowledgment is
received
Iskra Djonova-Popova
54
Aging Link State Records
• old or stale records need to be
removed from the link state database
• the procedure needs to be
synchronized
– the age is set to 0 when the record is first issued
– it is incremented on each hop and by 1 every sec.
– when it reaches “maxAge”, the router needs to
remove it
– the neighbors have to be informed about this
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
55
Scaling OSPF
• Rule of thumb
– no more than 150 routers /area
• Reality
– no more than 500 routers/area
• Backbone area is an area
– always marked as area 0
• proper use of areas reduces bandwidth
– summarized routes
– instability is limited within the area
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
56
Route Redistribution
RIP
Domain
OSPF Domain
• UNIX host
ruining
routed
CEENet Workshop
Zagreb, 1997
• the router redistributes RIP
into OSPF and vice versa
Iskra Djonova-Popova
57
Conclusions
• more complex than RIP
– the documentation is five times thicker
– the management needs more information
– the implementation needs more code
• why design such complex procedure?
– routing is important
– requires less “signalization” messages
– compute better routes
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
58
Conclusions 2
• OSPF is not a perfect protocol
• IETF keeps making it better
– “O” in OSPF stands for Open
• OSPF is not the only link state protocol
– IS-IS protocol is part of OSI routing framework for
CLNP
• similar in design to OSPF
• uses different terminology
CEENet Workshop
Zagreb, 1997
Iskra Djonova-Popova
59