Open Shortest Path First Ospf

Open Shortest Path First OSPF 8th CEENet Workshop on Network Technology NATO ANW

OSPF  Link state or SPF technology  Developed by OSPF Working Group of IETF (not proprietary)  Designed for TCP/IP Internet environment  Documented in rfc 1583, rfc 2178 8th CEENet Workshop Budapest, 2002

OSPF

2

OSPF - Link State Protocol  Link 

an interface on the router

 Link state 

description of the interface and the neighboring routers  IP address, mask, type, routers connected to

 Link state database 

collection of link state advertisement for all routers and networks

8th CEENet Workshop Budapest, 2002

OSPF

3

How OSPF Works?  Each router generates link-state advertisements for its links  When no OSPF areas are configured, link-state advertisements are flooded to all routers  It is crucial that all routers have identical link state database  Shortest path three is calculated by all routers and routing tables are derived 8th CEENet Workshop Budapest, 2002

OSPF

4

Link State Advertisement (LSA)  Generated periodically or in response to any change  Contains:    

source identification sequence number link state age list of neighbors

8th CEENet Workshop Budapest, 2002

OSPF

5

A Simplified Link State LS seq. Database Example From To Link Cost num A

a 1

c 1

B

b

C

3

2

d

f 1 D

e 2

E

Link State Announcement (LSA) From A to B, Link a, Cost = 1, Ls seq. Num. = 2 8th CEENet Workshop Budapest, 2002

OSPF

A A B B B C C D D E E E

B D A C E B E A E B C D

a c a b e b f c e d d e

1 . 2 1 2 1 2 3 1 2 2 3 1 1 1 1 2 2 1 2 2 2 1 2 1 6

In Case of a Link Failure A

a 1

1

B

b 3

2

d

f 1 D

e 2

E

 A and B send the C information to all other nodes about state of link a and the connectivity is reestablished.

 In the case when network is segmented the link state database in both parts are different. 8th CEENet Workshop Budapest, 2002

OSPF

7

Segmented Network a 1

A 1

B

b 3

2

d

f 1 D

e 2

 If b breaks, A and D will not receive this C LSA and their database will be different than the one of B, C and E.

E

 When e comes up the D’s database has to become synchronized. This process is called bringing up adjacency. 8th CEENet Workshop Budapest, 2002

OSPF

8

Bringing up Adjacency  Synchronizing databases via comparison of sequence numbers 3 “Interesting records” - the sequence numbers are different or not present in database  Client-server relationship is established first

8th CEENet Workshop Budapest, 2002

OSPF

9

The Flooding Protocol  Used to securely deliver LSAs 







Every node sends the LSA on every link except the one from where it received it Very fast and very reliable, but wastes bandwidth Messages sent only when there is a change or every 45 minutes Each node compares the newly received LSA with the entry in the data base. If it is newer the database is updated

8th CEENet Workshop Budapest, 2002

OSPF

10

Securing the Map Updates  Flooding procedure includes hop-by-hop acknowledgments  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  Messages can be authenticated, e. g. by

passwords

8th CEENet Workshop Budapest, 2002

OSPF

11

Authenticated Routing Updates  Two possibilities are defined 



no authentication (configured by default) authentication  simple password authentication  message digest authentication

8th CEENet Workshop Budapest, 2002

OSPF

12

More Routers on One Network  N routers on the same network (broadcast or non-broadcast) 



N(N-1) LSA will be needed to transmit information about the same network too much overhead

8th CEENet Workshop Budapest, 2002

OSPF

13

Designated Router (DR)  Selected among more routers on the same network 



selection based on the priority assigned by the network administrator for security reason backup designated router (BDR) is also selected

 All routers in the network become adjacent to DR 

exchange routing information with DR via multicast

 DR updates all the neighbors 8th CEENet Workshop Budapest, 2002

OSPF

14

The Metrics in OSPF formula: cost = 108 /bandwidth in bps

56 Kbps serial link 64 Kbps serial link T1 (1.544 Mbps seral link) E1 (2.048 Mbps serial link) 4 Mbps token ring Ethernet 16 Mbps token ring FDDI 8th CEENet Workshop Budapest, 2002

OSPF

1758 1562 65 48 25 10 6 1 15

Shortest Path Algorithm  Places the router at the root of the tree  In each iteration adds the router that is closest to it (smallest cumulative metric of the path)  Finished when all routers are added and the shortest path tree is generated 8th CEENet Workshop Budapest, 2002

OSPF

16

Representation of routers and networks in R1 a table N3 R3

8

6

R8

R6

From R3 R6 To R3 6 R6 8 Point-to-point network 8th CEENet Workshop Budapest, 2002

R3 4

N7

From R8

To R8 N7 4

Stub network OSPF

R2

R4

From R1 R2 R3 R4 N3 R1 0 R2 0 To R3 0 R4 0 N3 1 1 1 1 Broadcast or NBMA network 17

N1 N2

R1

R4

N12 N13 N14

N3

Example of an AS

R5

R2 R6

R3 N4

N12

N11 R9 R5 and R7 are border routers

R11

N8

R10

N9

N15 N6 R8

R12

N10 8th CEENet Workshop Budapest, 2002

R7

N7 OSPF

18

R1 R2 R3 R4 R5 R6 R7 R8 R9R10R11R12 N3 N6 N8 N9 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11 R12 N1 3 N2 N3 1 N4 N6 N7 N8 N9 N10 N11 N12 N13 N14 N15

0 0 0 0

6 8 8 8

6

6

7 6

5 0 0 0 7

3 1

1 2

0

1 1

1 4

1 3 1

2 1

1 2

3 8 8 8

8th CEENet Workshop Budapest, 2002

2 9 OSPF

0 0

0 0

The Resulting Directed Graph Networks and routers are represented by vertices. An edge of cost X connects Vertex A to Vertex B if the intersection of Column A and Row B is marked with the cost of the interface. 19

R5

R6

N12N13 N14 N4

R3R10 N3

R4 R 2 N2 N11

N6

N8

R1

R11

N1

N9

R9

Shortest Path Tree and Routing Table for R6 R8 N12 N15 N7

R12 N10

8th CEENet Workshop Budapest, 2002

R7

OSPF

Dest. N1 N2 N3 N4 N6 N7 N8 N9 N10 N11 RT5 RT7

Next Hop

Cost

R3 R3 R3 R3 R10 R10 R10 R10 R10 R10

10 10 7 8 8 12 10 11 13 14

RT5 RT10

6 8

20

Load Balancing by Multiple Path equal or R2

proportional cost multiple paths path 1

N1

N2 path 2

R1

R3

R4 8th CEENet Workshop Budapest, 2002

OSPF

21

Hierarchical Structure  Introduced to put a boundary on the explosion of link-state updates  Every area is connected to the backbone area

Backbone Area #0

Area #1 8th CEENet Workshop Budapest, 2002

Area #2

OSPF

Area #3 22

Multiple Areas IR  Group of contiguous hosts and networks Area 2  One LS database to other AS per area  Backbone area ASBR (contiguous) Area 4  Virtual links  Inter-area routing

Area 3 IR/BR area 0

Area 1

Virtual link

8th CEENet Workshop Budapest, 2002

OSPF

23

OSPF Areas  The border area is OSPF area 0  all routers belonging to the same area have identical database  SPF calculations are performed separately for each area  LSA flooding is bounded by area

8th CEENet Workshop Budapest, 2002

OSPF

24

Area Link State Database  Link state database for every area is different  Area database is composed of    

router links advertisements network links advertisements summary links advertisements AS external advertisements

8th CEENet Workshop Budapest, 2002

OSPF

25

Scaling OSPF  Rule of thumb 

no more than 150 routers /area

 Reality 

no more than 500 routers/area

 Backbone area is an area that glue all the other areas 

always marked as area 0

 proper use of areas reduces bandwidth  

summarized routes instability is limited within the area 8th CEENet Workshop Budapest, 2002

OSPF

26

Route Redistribution RIP Domain OSPF Domain

 UNIX host running routed 8th CEENet Workshop Budapest, 2002

• the router redistributes RIP into OSPF and vice versa OSPF

27

OSPF Advanatages  No limitation on hop count  Supports classless routing  Routing updates sent only when there is a change or very rarely  Faster convergence  Better load balancing  Logical definition of areas  Authentication and external routes tagging 8th CEENet Workshop Budapest, 2002

OSPF

28

The Link State Header

 LS age 

31

0

options LS type

LS age

 

Advertising Router

LS checksum

8th CEENet Workshop Budapest, 2002

length

ET

options

Link State ID

LS sequence number

time since the LS record was first advertised 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)

OSPF

29

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

0

8th CEENet Workshop Budapest, 2002

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

OSPF

30

The Network Links 0

31 Network mask Attached router --Attached router

 advertised by designated routers 8th CEENet Workshop Budapest, 2002

OSPF

31

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 8th CEENet Workshop Budapest, 2002

OSPF

32

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 8th CEENet Workshop Budapest, 2002

OSPF

 advertised by border routers  required by EGPs  E indicates that TOS is not comparable with that of internal routes

33

Protocols within OSPF  Common header  Hello protocol  Exchange protocol  Flooding protocol

8th CEENet Workshop Budapest, 2002

OSPF

34

The Common Header 0

31 version (1)

type (1)

packet length (2)

Router ID (4) Area ID (4) Checksum (2)

autype (2) Authentication (4)

8th CEENet Workshop Budapest, 2002

OSPF

35

The Hello Protocol 0

31

OSPF packet header, type = 1 (hello) Network mask Hello interval Options

Priority

Dead interval Designated router Backup designated router Neighbour ---Neighbour 8th CEENet Workshop Budapest, 2002

OSPF

36

The Exchange Protocol 0 31  Uses database OSPF packet header, type = 2 (dd) description packets 0 0 options 0I M MS  Asymmetric protocol (master-slave) DD sequence number  Master sends database Link state type description packets Link State ID  Slave sends the Advertising router acknowledgments Link State sequence number LS checksum

LS age

---8th CEENet Workshop Budapest, 2002

OSPF

37

The Exchange Protocol 2 0

31

OSPF packet header, type = 3 (rq)

 Request records 

Link state type Link State ID Advertising router



----

8th CEENet Workshop Budapest, 2002

OSPF

send in case when sequence number of the LS is smaller the other router will answer with a LS update 38

The Flooding Protocol 0

31

 When a link OSPF packet header, type = 4 (upd) changes state Number of advertisements



Link State advertisements ---0

31

OSPF packet header, type = 5 (ack) Link State advertisements headers ---8th CEENet Workshop Budapest, 2002

OSPF



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 39

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

8th CEENet Workshop Budapest, 2002

OSPF

40

Conclusions  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 8th CEENet Workshop Budapest, 2002

OSPF

41

IP Routing Configuration

8th CEENet Workshop Budapest, 2002

OSPF

42

IP Routing Configuration Tasks • Global configuration Select routing protocol(s)

Network 172.16.0.0

IGRP, RIP, OSPF

Specify network(s)

Network 160.89.0.0

Network 172.30.0.0

8th CEENet Workshop Budapest, 2002

OSPF

43

IP Routing Configuration Tasks Network 172.16.0.0

• Global configuration Select routing protocol(s) Specify network(s)

• Interface configuration Verify address/subnet mask

8th CEENet Workshop Budapest, 2002

OSPF IGRP, RIP, OSPF

Network 160.89.0.0

OSPF Network 172.30.0.0

OSPF

44

Dynamic Routing Configuration Router (config) #

router protocol

[ keyword ]

 Defines an IP routing protocol

Router (config-router) #

network network-number

• The network subcommand is a mandatory configuration command for each IP routing process 8th CEENet Workshop Budapest, 2002

OSPF

45

OSPF Basic Configuration Commands Router (config) #

router ospf process-id

 Enables an OSPF routing process Router (config-router) #

network address wildcard-mask area area-id

•

Selects participating interfaces

8th CEENet Workshop Budapest, 2002

OSPF

46

OSPF Basic Configuration Example 172.16.5.3 192.168.10.5

Area 1

E2

172.16.1.1

Token Ring

T0

E1 E0

172.16.3.2

Area 0 router ospf 63 network 172.16.5.3 0.0.0.0. area 1 network 172.16.0.0 0.0.255.255 area 0 network 192.168.10.5 0.0.0.0 area 1 8th CEENet Workshop Budapest, 2002

OSPF

47

OSPF Route Summarization Area 0 Backbone Summarization ABRs Area 1

x  Minimizes routing table entries  Localizes impact of a topology change 8th CEENet Workshop Budapest, 2002

OSPF

48

Route Summarization (cont.) Area 1 A

Routing Table for B O 131.108.4.0 O 131.108.8.0 O 131.108.12.0 O 131.108.16.0 O 131.108.20.0 O 131.108.24.0 O 131.108.28.0

ABR

Area 0

B

C

Summarization

255.255.252.0 255.255.252.0 255.255.252.0 255.255.252.0 255.255.252.0 255.255.252.0 255.255.252.0

Routing Table for C IA 131.108.16.0 255.255.240.0

 Inter-area (IA) summary link carries mask  One entry can represent several subnets 8th CEENet Workshop Budapest, 2002

OSPF

49

Route Summarization Issue Existing Subnet 131.108.12.0

255.255.252.0

Mask = 252 Address = 12

255.255.240.0

Mask = 240 Address = 12

1111 11 00 0000 11 00

Valid 3rd Subnet

Summary Route 131.108.12.0

1111 0000

0000 1100

Invalid Subnet Zero

 Some addresses may need reallocating

8th CEENet Workshop Budapest, 2002

OSPF

50

Route Summarization Commands Router (config-router) #

area area-id range address mask

 Consolidates IA routes on an ABR Router (config-router) #

summary-address address mask

•

Consolidates external routes on an ASBR 8th CEENet Workshop Budapest, 2002

OSPF

51

Route Summarization Example Area 0

Interface Addresses

172.16.96.0 - 172.16.127.0 255.255.255.0 172.16.127.1 172.16.96.1

Interface Addresses

(255.255.255.0 mask)

172.16.32.1

R2 R1

R2

172.16.32.0 - 172.16.63.0 255.255.255.0

8th CEENet Workshop Budapest, 2002

0.0.31.255 area 1 0.0.31.255 area 0 255.255.224.0 255.255.224.0

172.16.64.1 172.16.64.0 - 172.16.95.0 255.255.255.0

Area 2

Area 1 R1# router ospf 100 network 172.16.32.0 network 172.16.96.0 area 0 range 172.16.96.0 area 1 range 172.16.32.0

(255.255.255.0 mask)

R2# router ospf 100 network 172.16.64.0 0.0.31.255 area 2 network 172.16.96.0 0.0.31.255 area 0 area 0 range 172.16.96.0 255.255.224.0 area 2 range 172.16.64.0 255.255.224.0 OSPF

52

OSPF Route Redistribution OSPF RIP IGRP Enhanced IGRP IS-IS

BGP EGP

 Allows routing-information exchange between OSPF and other routing protocols 8th CEENet Workshop Budapest, 2002

OSPF

53

OSPF Redistribution Command Router (config-router) #

redistribute protocol [ process-id ] [ metric value ] [ metric-type value ] [ subnets ]

 Redistributes routes from OSPF into other routing protocols (and vice versa) 8th CEENet Workshop Budapest, 2002

OSPF

54

OSPF Redistribution Example 1 Redistribution between RIP and OSPF OSPF Area 0

RIP

S0 172.16.62.1

172.16.9.1 R1 172.16.8.1

8th CEENet Workshop Budapest, 2002

S1 172.16.63.1

OSPF

55

OSPF Redistribution Example 1 router ospf 109 network 172.16.62.0 0.0.0.255 area 0 network 172.16.63.0 0.0.0.255 area 0 redistribute rip subnets metric-type 1 metric 20 router rip network 172.16.0.0 passive-interface serial 0 passive-interface serial 1 default-metric 10 redistribute ospf 109 match internal external 1 external 2

8th CEENet Workshop Budapest, 2002

OSPF

56

Redistribution Example 2 Avoiding Loops

RIP

RIP

172.16.9.1

OSPF Area 0 R1

R3

172.16.8.1 R2 R2

RIP

8th CEENet Workshop Budapest, 2002

OSPF

"Back door" creates potential loop

57

Redistribution Example 2 cont router ospf 109 network 172.16.62.0 0.0.0.255 area 0 network 172.16.63.0 0.0.0.255 area 0 redistribute rip subnets metric-type 1 metric 20 distribute-list 11 out rip access-list 11 permit 172.16.8.0 0.0.7.255

8th CEENet Workshop Budapest, 2002

OSPF

58

VERIFYING OSPF OPERATION

8th CEENet Workshop Budapest, 2002

OSPF

59

show ip ospf interface Command Router# show ip ospf interface e0 Ethernet0 is up, line protocol is up Internet Address 203.250.14.1 255.255.255.0, Area 0.0.0.0 Process ID 10, Router ID 203.250.13.41, Network Type BROADCAST, Cost: 10 Transmit Delay is 1 sec, State BDR, Priority 1 Designated Router (ID) 203.250.15.1, Interface address 203.250.14.2 Backup Designated router (ID) 203.250.13.41, Interface address 203.250.14.1 Timer intervals configured, Hello 10, Dead 40, Wait 40, Retransmit 5 Hello due in 0:00:02 Neighbor Count is 3, Adjacent neighbor count is 3 Adjacent with neighbor 203.250.15.1 (Designated Router) Loopback0 is up, line protocol is up Internet Address 203.250.13.41 255.255.255.255, Area 1 Process ID 10, Router ID 203.250.13.41, Network Type LOOPBACK, Cost: 1 Loopback interface is treated as a stub Host

 Verifies interfaces are in correct areas 8th CEENet Workshop Budapest, 2002

OSPF

60

show ip ospf Command Router # show ip ospf Routing Process "ospf 1" with ID 2.2.2.2 Supports only single TOS (TOS0) routes SPF schedule delay 5 secs, Hold time between two SPFs 10 secs Number of areas in this router is 1 Area 23 Number of interfaces in this area is 3 Area has no authentication SPF algorithm executed 19 times Area ranges are Link State Update Interval is 0:30:00 and due in 0:04:55 Link State Age Interval is 0:20:00 and due in 0:04:55

 Displays general information about the OSPF routing process 8th CEENet Workshop Budapest, 2002

OSPF

61

show ip ospf database Command Router# show ip ospf database OSPF Router with ID (3.3.3.3) (Process ID 1) Router Link States (Area 23) Link ID 3.3.3.3 4.4.4.4 2.2.2.2 1.1.1.1

ADV Age Router 3.3.3.3 78 4.4.4.4 1691 2.2.2.2 1693 1.1.1.1 1696

Seq#

Checksum

0x80000032 0x8000002B 0x80000030 0x80000026

0x80B6 0xE11C 0xE35E 0x80A1

Link count 5 1 5 1

Net Link States (Area 23) Link ID 150.100.4.2 150.100.1.2

8th CEENet Workshop Budapest, 2002

ADV Router 4.4.4.4 2.2.2.2

Age 1691 1693

Seq# 0x80000030 0x80000024

OSPF

Checksum 0x2FCE 0xFB29

62

show ip protocol Command Router> show ip protocol Routing Protocol is “ospf 300” Sending updates every 0 seconds Invalid after 0 seconds, hold down 0, flushed after 0 Outgoing update filter list for all interfaces is not set Incoming update filter list for all interfaces is not set Redistributing: ospf 300 Routing for Networks: 183.8.0.0/0.0.255.255 144.253.100.0/0.0.0.255 Routing Information Sources: Gateway Distance Last Update 144.253.100.0 110 6d21 183.8.128.12 110 0:17:32 192.3.63.192 110 0:17:33 192.3.63.194 110 0:17:33 183.8.128.0 110 6d21 153.50.192.0 110 0:17:33 153.50.193.1 110 0:17:33 183.8.64.130 110 6d19 183.8.64.128 110 0:17:33 133.3.4.0 110 0:17:33 131.108.100.3 110 0:17:33 Distance: (default is 110) - - More - -

8th CEENet Workshop Budapest, 2002

OSPF

63

Other OSPF show Commands Router #

show ip ospf virtual-links  Displays parameters about OSPF virtual links Router #

show ip ospf neighbor detail

• Displays neighbor information per interface Router #

show ip ospf border-routers

• Displays routes to the ABR and ASBR 8th CEENet Workshop Budapest, 2002

OSPF

64