Slide 1
1
CMPT 471
Networking
OSPF
© Janice Regan, 2006-2017
© Janice Regan, 2006-2017
2
Dynamic Routing
In very simple small networks static routing may be adequate.
As networks grow and become more complex, including multiple or redundant paths between hosts and routers static routing becomes difficult to manage
Redundant routes are only useful if they can be used immediately on failure of the original route
In a large network the reporting of failure and response by a network manager cannot be accomplished on a short enough time scale for the redundant routes to be useful
© Janice Regan, 2006-2017
3
Dynamic Routing
A routing algorithm to update the routing tables to respond to changes and failures in the network becomes a necessary component of the system
Addition of a routing algorithm does not change the forwarding algorithm used to deliver packets, segments …
© Janice Regan, 2006-2017
4
Shortcomings of RIP
Simple metric (hop count) not useful when links have different capacities (it takes longer to transmit over a lower capacity link)
Allows one route between each pair of stations, even if multiple routes with the same metric value exists (no load balancing)
Slow convergence, count to infinity problem, mitigated by using a small maximum hop count but still an issue. Looping can be caused during convergence
No authentication in RIP1, malicious user can hijack traffic by providing low cost routes. Authentication available in RIP2
Useful for small simple networks only, limited by maximum hop count, size of routing data proportional to the size of the network, and poor control of looping
© Janice Regan, 2006-2017
5
Approaches – Link-state
When router initialized and at intervals thereafter, it determines link cost on each interface (cost to each directly connected node)
Advertises set of link costs to all other nodes in topology
Each node constructs routing table containing minimum cost paths to all attached nodes ( costs and first hop to each router) using the data received from all other nodes advertisements.
Open shortest path first (OSPF) protocol uses link-state routing. (a common IRP)
Second generation routing algorithm for ARPANET
© Janice Regan, 2006-2017
6
link state methods
The count to infinity problem is solved since information is sent to all routers not just nearest neighbors. This gives rapid convergence
The size of the routing data packet is no longer proportional to the size of the network, it is determined by the number of nearest neighbors.
Each node calculates its own optimal paths, reducing probability of loops caused by old information (old due to longer propagation time across network)
© Janice Regan, 2006-2017
7
Open Shortest Path First: OSPF
IGP of Internet, supports classless addressing, subnetting, authentication, and load balancing (use of multiple equal cost paths to distribute load)
(RFC 2328) Uses a Link State Routing Algorithm. Each router
keeps a database of information based on local costs and received update packets from other routers in the AS.
Each router builds a directed graph showing topology and path costs
© Janice Regan, 2006-2017
8
Open Shortest Path First: OSPF
Uses a Link State Routing Algorithm (RFC 2328) Each router
Knows whether data originates within or outside the AS.
Can choose correct gateway to send packets through to the outside world
Uses the database and Dykstra’s algorithm to determine least cost paths for the whole AS using itself as the source node, preventing looping
Advertises its locally determined routing table periodically
© Janice Regan, 2006-2017
9
Directed Graph Network model
Models flow between routers
Vertices or nodes are routers and networks
Types of Network
Transit: data not originating in network can pass through the network, more than one router is attached to the network
Stub: data not originating in network can enter only. One router is attached to network
© Janice Regan, 2006-2017
10
Directed Graph Network model
Types of Network
Transit and Stub
Edges, associated costs at output of routers
Connect two routers with a pair of edges
Connect router to transit network with pair of edges
Connect router to stub network with single edge
© Janice Regan, 2006-2017
11
Simplest OSPF graphs: 1
AS must contain at least two routers. Simplest case is two routers connected by a point to point connection
The two routers are separated by a transit network, with three or more routers connect to the network it is known as a multi access network
R1
R2
3
5
R1
R2
3
5
R3
6
0
0
0
© Janice Regan, 2006-2017
12
Stub network, single router connects network to the AS. Does not mean no data is coming from the stub network, simply that no data is coming through the network from the other side
Flow costs can be asymmetric.
Flow costs for the path to the next router are associated with the router as the packet leaves the router
No additional cost is added for propagation from the intermediate network to the next router, all cost is associated with the path from the originating router to the transit
Simplest OSPF graphs: 2
R1
5
© Janice Regan, 2006-2017
13
From notes of Lou Hafer, after RFC1131: Sample AS
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
© Janice Regan, 2006-2017
14
RFC 1131: Sample AS: Directed Graph
© Janice Regan, 2006-2017
15
RFC 2328: Sample AS: Directed Graph
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
© Janice Regan, 2006-2017
16
Neighbor Routers
Any pair of routers attached to the same single network segment (single broadcast address) can become neighbors
To become neighbors they must agree that they are neighbors
The pair of routers negotiates this agreement using and exchange of Hello packets (more later) to assure a two way link is established
© Janice Regan, 2006-2017
17
Adjacent routers
Routers establish an adjacency if they will be exchanging LSAs.(link state announcement packets that carry routing information between routers)
A router on a particular physical segment will not necessarily be adjacent to all other routers on that segment
A router with multiple interfaces may simultaneously be adjacent to routers on more than one network segment
© Janice Regan, 2006-2017
18
Designated Routers (1)
Each multi access network will have a designated router (and a backup designated router in case the designated router fails).
The designated router will be chosen by the exchange of hello packets (more later)
Consider all possible connections between the routers connected to the network (n[n-1]/2 connections) and the n connections to the network. This gives a total of n2 connections. Each of these connections would generate one record in the routing database for the overall network
© Janice Regan, 2006-2017
19
Designated Routers
n(n-1)/2
links
© Janice Regan, 2006-2017
20
Designated Routers (2)
When a designated router is elected, one of its responsibilities is to advertize the routes for the local network segment to the other routers on the same local network segment
Adjacencies will be established from the designated router to all other routers on the network segment
we need only advertise these n-1 connections between routers on the local network segment to other routers outside of the local segment
© Janice Regan, 2006-2017
21
Designated Routers
n(n-1)/2
links
(n-1) links
will become
adjacencies
D
© Janice Regan, 2006-2017
22
Designated Routers (3)
When a designated router is elected, another of its responsibility is to advertize the routes for the local network segment to other designated routers for other segments.
Adjacencies will be established from the designated router to all other routers on other network segments accessible through the other interfaces attached to the designated router.
we need only advertise one connection from the designated router to each network’s designated router in the OSPF routing database.
© Janice Regan, 2006-2017
23
Designated Routers
n(n-1)/2
links
(n-1)
adjacencies
D
D
Local
segment
© Janice Regan, 2006-2017
24
Designated Routers
Only the designated router for each network will advertise routes to routers connected to the network. These routes are advertised by sending a network link state advertisement to all routers adjacent to the designated router. This advertisement contains a list of all routers connected to the network, the cost for the path from each of these routers to the network is 0.
All routers attached to the network will advertise a list of routes for their neighbor routers. Routes to neighbor routers
© Janice Regan, 2006-2017
25
Operation
A database corresponding to the directed graph is kept by each router.
Dijkstra’s algorithm (shortest path first SPF) and database information are used, to find the next hop on the least cost path from this router (the source) to all other routers.
Only next hop information is used to forward packets
© Janice Regan, 2006-2017
26
Operation
Link state messages (called Link state advertisements, LSAs) from other routers in the AS are used to build/update the database
A LSA includes information on path costs to nearest neighbor routers only (router R6 would have path costs to router R3 R5 and R10 in its LSA)
LSAs are flooded to all adjacent routers throughout the AS
LSAs are timestamped, the routers database is only updated when the message is newer than the last update for that node
© Janice Regan, 2006-2017
27
Designated Routers: Example
Example for network 3 with designated router R2
As designated router for N3 R2 has entries
R1 0
R2 0
R3 0
R4 0
As neighbor to other routers R2 has entries
N2 3
N3 1
Routers R1 R3 and R4 do not duplicate advertisements for N3.
© Janice Regan, 2006-2017
28
RFC 1131: Sample AS: SPF tree
© Janice Regan, 2006-2017
29
SPF Routing table for router 6
RFC1131: routing table for router 6
© Janice Regan, 2006-2017
30
Dividing an AS into Areas
Many networks are large and complex it is often useful to divide them into areas and deal with each smaller area separately
OSPF includes mechanisms for dealing with ASs partitioned into areas.
When an AS is divided into areas the areas are chosen so they can be connected by a backbone of routers
Any router which is part of an area, but also communicates with other areas, is also a part of the backbone area.
© Janice Regan, 2006-2017
31
Dividing an AS into Areas
The backbone is a special area. The information passing between all other areas travels through the backbone routers (dark ovals in diagram)
Routers in each area run their own copy of the routing process and have their own topological link-state data base. Routers in one area have no detailed knowledge of routing in other areas.
An area includes all routers with a connection to any contained network
© Janice Regan, 2006-2017
32
From notes of Lou Hafer, after RFC1131: AS divided into areas
23b
2b
1b
Includes Router 4
Includes Routers 7 and 11
Internal routers 1,2,5,6,8,9,12
Area Border routers 3,4,7,10,11
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
© Janice Regan, 2006-2017
33
Types of routers in an AS
Internal Routers: all connected networks belong to the same area or with only backbone interfaces
Area Border Routers: not internal, run one copy of routing algorithm for backbone, and one copy for each attached area
Backbone Routers: has at least one interface to the backbone. Can be an internal router if all interfaces are with the backbone. Otherwise it is an area border router
AS boundary routers: Part of the AS but also communicates with routers outside the AS using and EGP. Can be routers of an of the above types
© Janice Regan, 2006-2017
34
Inter area routing
Routing a packet between two areas through the backbone
The overall algorithm find the lowest cost sum of
The lowest cost path from the source to the AS border router in the source area
The lowest cost path through the AS backbone from the AS border router for the source area the AS border router for the destination area
The lowest cost path from the AS border router for the destination area to the destination
© Janice Regan, 2006-2017
35
From notes of Lou Hafer, after RFC1131: AS area 1
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
© Janice Regan, 2006-2017
36
From notes of Lou Hafer, after RFC1131: AS backbone
/docProps/thumbnail.jpeg