IP OSPF Routing and Network Architectures
1
Computer Networks Architectures and
Protocol
s
Shortest-Path Routing
and IP
OSPF Routing
Departamento de Informática da
FCT/UNL
2
Lecture Outline
•
What is routing, shortest-path routing
•
One
routing protocol example
–
Link state: Open Shortest Path First (OSPF)
3
Why Does Routing Matter?
•
End-to-end performance
–
Quality of the path affects user performance
–
Propagation delay, throughput, and packet loss
•
Transient disruptions during changes
–
Failures, maintenance, and load balancing
–
Limiting packet loss and delay during changes
•
Use of network resources
–
Balance of the traffic over the routers and links
–
Avoiding congestion by directing traffic to lightly-
loaded links
4
Some Routing Facets
•
Static versus dynamic routing
–
Static routing: when routing decisions are seldom or
never changed
–
Dynamic routing: when routing decisions are
evaluated periodically or when a network modification
takes place
•
Criteria for routing
–
Shortest-path routing
–
Network usage
maxi
mi
s
ation (load distribution,
traffic engineering, ...)
–
Policy routing (e.g. Inter-AS routing, BGP, routing
based on the origin of packets, ...)
5
Forwarding v
ersus
Routing
•
Forwarding:
data plane
–
Directing a data packet to an outgoing link
–
Individual router
using
a forwarding table
•
Routing:
control plane
–
Computing paths the packets will follow
–
Routers talking amongst themselves
–
Individual router
creating
a forwarding table
6
Forwarding v
ersus
Routing
7
Static Routing
!
!
hostname R1
!
ip route 10.1.5.0
255.255.255.0
10.1.3.253
!
!
This kind of configuration is only used to enter
specific and static routes in the routing table.
Entering a default route is an example of such
usage:
ip route 0.0.0.0 0.0.0.0 10.1.2.100
10.1.5.0/24
10.1.3.253
10.1.5.254
10.1.3.0/24
10.1.2.0/24
10.1.4.0/24
10.1.3.254
10.1.4.254
10.1.2.254
R2
R1
R3
8
Open Shortest-Path Protocol
9
Modelling a Network as a Graph
10
Dijkstra Algorithm: Shortest-Paths Tree
11
Link-State Routing
•
Each router keeps track of its incident links
–
Whether the link is up or down
–
The cost on the link
•
Each router broadcasts the link state (LSA)
–
To give every router a complete view of the graph
•
Each router runs Dijkstra’s algorithm
–
To compute the shortest paths
–
… and constructs the forwarding table
•
Example protocols
–
Open Shortest Path First (OSPF)
–
Intermediate System – Intermediate System (IS-IS)
12
Detecting Topology Changes
13
Broadcasting the Link State
•
Reliable flooding
–
Ensure all nodes receive link-state information
–
… and that they use the latest version
•
Challenges
–
Packet loss
–
Out-of-order arrival
–
Crash and quickly rebooting a router
•
Solutions
–
Acknowledgments and retransmissions
–
Sequence numbers
–
Time-to-live for each packet
14
When to Initiate Flooding
•
Topology change
–
Link or node failure
–
Link or node recovery
•
Configuration change
–
Link cost change
•
Periodically
–
Refresh the link-state information
–
Typically (say) 30 minutes
–
Corrects for possible corruption of the data
15
Convergence
•
Getting consistent routing information to
all nodes
–
E.g., all nodes having the same link-state
database
•
Consistent forwarding after convergence
–
All nodes have the same link-state database
–
All nodes forward packets on shortest paths
–
The next router on the path forwards to the
next hop
16
Transient Disruptions
•
Detection delay
–
A node does not detect a failed link
immediately
–
… and forwards data packets into a “blackhole”
–
Depends on timeout for detecting lost hellos
–
Some routers know about failure before
others
–
The shortest paths are no longer consistent
–
Can cause transient forwarding loops
Inconsistency Example
17
18
Convergence Delay
•
Sources of convergence delay
–
Detection latency
–
Flooding of link-state information
–
Shortest-path computation
–
Creating the forwarding table
•
Performance during convergence period
–
Lost packets due to blackholes and TTL expiry
–
Looping packets consuming resources
–
Out-of-order packets reaching the destination
•
Very bad for VoIP, online gaming, and video
19
Reducing Convergence Delay
•
Faster detection
–
Smaller hello timers
–
Link-layer technologies that can detect failures
•
Faster flooding
–
Flooding immediately
–
Sending link-state packets with high-priority
•
Faster computation
–
Faster processors on the routers
–
Incremental Dijkstra algorithm
•
Faster forwarding-table update
–
Data structures supporting incremental updates
Paper
P. François, C. Filsfils, J. Evans and O. Bonaventure,
“Achieving Sub-Second IGP Convergence in Large IP
Networks,” in Computer Communications Review, Volume
35, Number 2, July 2005, pp.s 35 - 44
20
21
Hierarchical OSPF and OSPF Areas
22
•
Two level hierarchy:
local areas and backbone area
•
Link-state announcements are only flooded in one area
•
Other areas are not known in detail but their list of
networks.
•
Area border routers:
announce network summaries from
one area to the other
•
Backbone routers:
these are the routers of area 0
•
Boundary routers:
are connected to other Ass
•
Therefore, besides link-state announcements, there are
also network summaries announcements
Hierarchical OSPF
23
OSPF Route Types
Intra-area route —
a route to a network of the
same area
Inter-area route —
a route to a network of
another area; its cost includes all link costs up to
a area border router, and from there up to the
destination
External route —
a route leading to a network
external to the ospf domain
24
Designated Router
•
Designated Router
— if a certain number of
different OSPF routers are connected to the
same broadcast network, one is in charge of all
the locally reachable networks
•
The
Designated Router is elected
by the way
of a manually set priority
–
ip ospf priority number
•
To avoid partitions, there is a
Backup
Designated Router
announcing the same
networks
25
OSPF Database Exchanges
•
OSPF “database state exchanges”
take place among adjacent OSPF
routers
•
These are known as LSAs or
“Link State Announcements”
•
The header of these packets has the following information:
sequence number, router ID of the sender router, type,
announcement ID, authentication information, ...
•
The exchange transaction begins with an
exchange proposal
. If the
receiver does not know the announcement ID, or has one with an
older sequence number, it sends a
link-state request,
otherwise it
declines the update
•
The answer is a
link-state update
which must be acknowledge by a
link-state acknowledgement
26
Route Aggregation Summaries
•
To avoid the explosion of route propagation information,
routes should be aggregated as much as possible
— this
allows shorter route announcements
•
Routers can try to perform automatic route aggregation
which is a computationally intensive task. Another way
consists in doing aggregation by hand, which can be
error prone
•
Aggregation efficiency can be improved by carefully
choosing network numbers
— for example all “totally-
stubby areas” (areas only connecting to the backbone
area) should have, as much as possible, networks sharing
the same prefix
•
This is yet another example of the
interactions of
routing scalability and network addressing
27
Link flapping
•
If an interface goes up and down too frequently, this will constantly
flood the network with new link-state announcements, and will
require, a new computation of the new shortest paths (SPF
algorithm) per each link-state announcement (LS) received
•
The command:
show ip ospf
shows the number of times the
algorithm has been executed recently
•
By default, the SPF algorithm is only executed 5 seconds after
a LS announcement arrives, and at least 10 seconds should
separate each SPF execution
•
The command
ospf timers
allows the modification of these values
router ospf
timers spf <schedule delay in seconds>
<hold-time in seconds
28
Conclusions
•
Routing may be treated by a distributed
algorithm
–
React to changes in the topology
–
Compute the shortest paths
•
Two main shortest-path algorithms
–
Dijkstra
→
link-state routing (e.g., OSPF and IS-IS)
–
Bellman-Ford
→
distance vector routing (e.g., RIP)
•
Convergence process
–
Changing from one topology to another
–
Transient periods of inconsistency across routers
–
Big problem if the convergence process is slow
29
Written assignment
Each student must
deliver
a written report of at
most 5 pages (12 dots, double spaced) on the
subject of the following paper:
–
P. François, C. Filsfils, J. Evans and O. Bonaventure, “Achieving
Sub-Second IGP Convergence in Large IP Networks,” in
Computer Communications Review, Volume 35, Number 2, July
2005, pp.s 35 - 44
Deliver date:
5
th
of April 2018
This content covers the importance of routing in computer networks, focusing on shortest-path routing and IP OSPF routing. Topics include routing protocols, end-to-end performance, routing facets (static vs dynamic), and the distinction between forwarding and routing.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Computer Networks Architectures and Protocols Shortest-Path Routing and IP OSPF Routing Departamento de Inform tica da FCT/UNL 1
Lecture Outline What is routing, shortest-path routing One routing protocol example Link state: Open Shortest Path First (OSPF) 2
Why Does Routing Matter? End-to-end performance Quality of the path affects user performance Propagation delay, throughput, and packet loss Transient disruptions during changes Failures, maintenance, and load balancing Limiting packet loss and delay during changes Use of network resources Balance of the traffic over the routers and links Avoiding congestion by directing traffic to lightly- loaded links 3
Some Routing Facets Static versus dynamic routing Static routing: when routing decisions are seldom or never changed Dynamic routing: when routing decisions are evaluated periodically or when a network modification takes place Criteria for routing Shortest-path routing Network usage maximisation (load distribution, traffic engineering, ...) Policy routing (e.g. Inter-AS routing, BGP, routing based on the origin of packets, ...) 4
Forwarding versus Routing Forwarding: data plane Directing a data packet to an outgoing link Individual router using a forwarding table Routing: control plane Computing paths the packets will follow Routers talking amongst themselves Individual router creating a forwarding table 5
Forwarding versus Routing FIB - Forwarding Information Base Int 1 Int 2 Int 8 Destino Dist ncia Interface (dire o) a 100 Int 8 ... ... ... Int 7 Int 3 e 10 Int 2 f 1000 Int 1 Int 4 RIB - Routing Information Base Int 5 Int 6 Informa es sobre o estado da rede 6
Static Routing ! ! hostname R1 10.1.2.0/24 ! 10.1.2.254 ip route 10.1.5.0 255.255.255.0 10.1.3.253 R1 10.1.3.254 10.1.4.254 ! ! 10.1.3.0/24 10.1.3.253 10.1.4.0/24 This kind of configuration is only used to enter specific and static routes in the routing table. Entering a default route is an example of such usage: R2 R3 10.1.5.254 10.1.5.0/24 ip route 0.0.0.0 0.0.0.0 10.1.2.100 7
Modelling a Network as a Graph b a 10 Mbps 20 5 5 100 Mbps 100 Mbps c 100 Mbps d 5 10 Mbps 20 10 Mbps 20 1 Gbps 50 Mbps 2 8 e f 10 Mbps 20 (a) - Rede (b) - Modelo 9
Link-State Routing Each router keeps track of its incident links Whether the link is up or down The cost on the link Each router broadcasts the link state (LSA) To give every router a complete view of the graph Each router runs Dijkstra s algorithm To compute the shortest paths and constructs the forwarding table Example protocols Open Shortest Path First (OSPF) Intermediate System Intermediate System (IS-IS) 11
Detecting Topology Changes Hello message b a 100 Mbps 12
Broadcasting the Link State Reliable flooding Ensure all nodes receive link-state information and that they use the latest version Challenges Packet loss Out-of-order arrival Crash and quickly rebooting a router Solutions Acknowledgments and retransmissions Sequence numbers Time-to-live for each packet 13
When to Initiate Flooding Topology change Link or node failure Link or node recovery Configuration change Link cost change Periodically Refresh the link-state information Typically (say) 30 minutes Corrects for possible corruption of the data 14
Convergence Getting consistent routing information to all nodes E.g., all nodes having the same link-state database Consistent forwarding after convergence All nodes have the same link-state database All nodes forward packets on shortest paths The next router on the path forwards to the next hop 15
Transient Disruptions Detection delay A node does not detect a failed link immediately and forwards data packets into a blackhole Depends on timeout for detecting lost hellos Some routers know about failure before others The shortest paths are no longer consistent Can cause transient forwarding loops 16
Inconsistency Example 1000 1000 a b a b 10 10 10 10 c d c d d d 1000 1000 1000 1000 infinito 10 20 20 1 1 1000 1000 e e f f (a) - Rede sem avarias (b) - Rede ap s a avaria 17
Convergence Delay Sources of convergence delay Detection latency Flooding of link-state information Shortest-path computation Creating the forwarding table Performance during convergence period Lost packets due to blackholes and TTL expiry Looping packets consuming resources Out-of-order packets reaching the destination Very bad for VoIP, online gaming, and video 18
Reducing Convergence Delay Faster detection Smaller hello timers Link-layer technologies that can detect failures Faster flooding Flooding immediately Sending link-state packets with high-priority Faster computation Faster processors on the routers Incremental Dijkstra algorithm Faster forwarding-table update Data structures supporting incremental updates 19
Paper P. Fran ois, C. Filsfils, J. Evans and O. Bonaventure, Achieving Sub-Second IGP Convergence in Large IP Networks, in Computer Communications Review, Volume 35, Number 2, July 2005, pp.s 35 - 44 20
Hierarchical OSPF Two level hierarchy: local areas and backbone area Link-state announcements are only flooded in one area Other areas are not known in detail but their list of networks. Area border routers: announce network summaries from one area to the other Backbone routers: these are the routers of area 0 Boundary routers: are connected to other Ass Therefore, besides link-state announcements, there are also network summaries announcements 22
OSPF Route Types Intra-area route a route to a network of the same area Inter-area route a route to a network of another area; its cost includes all link costs up to a area border router, and from there up to the destination External route a route leading to a network external to the ospf domain 23
Designated Router Designated Router if a certain number of different OSPF routers are connected to the same broadcast network, one is in charge of all the locally reachable networks The Designated Router is elected by the way of a manually set priority ip ospf priority number To avoid partitions, there is a Backup Designated Router announcing the same networks 24
OSPF Database Exchanges OSPF database state exchanges take place among adjacent OSPF routers These are known as LSAs or Link State Announcements The header of these packets has the following information: sequence number, router ID of the sender router, type, announcement ID, authentication information, ... The exchange transaction begins with an exchange proposal. If the receiver does not know the announcement ID, or has one with an older sequence number, it sends a link-state request, otherwise it declines the update The answer is a link-state update which must be acknowledge by a link-state acknowledgement 25
Route Aggregation Summaries To avoid the explosion of route propagation information, routes should be aggregated as much as possible this allows shorter route announcements Routers can try to perform automatic route aggregation which is a computationally intensive task. Another way consists in doing aggregation by hand, which can be error prone Aggregation efficiency can be improved by carefully choosing network numbers for example all totally- stubby areas (areas only connecting to the backbone area) should have, as much as possible, networks sharing the same prefix This is yet another example of the interactions of routing scalability and network addressing 26
Link flapping If an interface goes up and down too frequently, this will constantly flood the network with new link-state announcements, and will require, a new computation of the new shortest paths (SPF algorithm) per each link-state announcement (LS) received The command: show ip ospf shows the number of times the algorithm has been executed recently By default, the SPF algorithm is only executed 5 seconds after a LS announcement arrives, and at least 10 seconds should separate each SPF execution The command ospf timers allows the modification of these values router ospf timers spf <schedule delay in seconds> <hold-time in seconds 27
Conclusions Routing may be treated by a distributed algorithm React to changes in the topology Compute the shortest paths Two main shortest-path algorithms Dijkstra link-state routing (e.g., OSPF and IS-IS) Bellman-Ford distance vector routing (e.g., RIP) Convergence process Changing from one topology to another Transient periods of inconsistency across routers Big problem if the convergence process is slow 28
Written assignment Each student must deliver a written report of at most 5 pages (12 dots, double spaced) on the subject of the following paper: P. Fran ois, C. Filsfils, J. Evans and O. Bonaventure, Achieving Sub-Second IGP Convergence in Large IP Networks, in Computer Communications Review, Volume 35, Number 2, July 2005, pp.s 35 - 44 Deliver date: 5thof April 2018 29
