Transcript RIP/OSPF

RIP - OSPF
CST 415
4/9/2015
CST 415 - Computer Networks
1
Topics
• Definitions
• RIP
• OSPF
4/9/2015
CST 415 - Computer Networks
2
Definitions
BGP – Boundary Gateway Protocol
IGP – Interior Gateway Protocol
RIP – Routing Information Protocol
OSPF – Open Shortest Path First
RIP and OSPF are both IGPs
4/9/2015
CST 415 - Computer Networks
3
Definitions
In the above diagram:
BGP is used for inter-autonomous system communication.
IGP is used for intra-autonomous system communication.
IGP can be any number of different protocols (RIP, OSPF, etc.)
4/9/2015
CST 415 - Computer Networks
4
Definitions
• There are many IGP protocols.
• The specific protocol a specific router
depends on
– The router manufacturer
» e.g. Cisco may have a proprietary protocol
that relies on a specific hardware
implementation.
– The generation of the router
» IGPs continued to be refined from router
generation to generation.
4/9/2015
CST 415 - Computer Networks
5
RIP
RIP (Routing Information Protocol)
originated in a variant of UNIX
– BSD standard UNIX
– Original incarnation was called routed
– RIP became widely used through the
distribution of 4BSD
– RIP was widely adopted as an IGP well
before a standard existed
4/9/2015
CST 415 - Computer Networks
6
RIP
• RIP is an application layer protocol.
• Therefore RIP uses well defined ports
for communication.
– Port 520
– This is a UDP port (e.g. send it and forget
it) as opposed to BGP using a TCP port
(guaranteed delivery)
4/9/2015
CST 415 - Computer Networks
7
RIP
RIP Operation
• Uses simple distance-vector routing
• Partitions participants into
– Active: advertises routes to other
participants
– Silent: only listen to routes. Do not
advertise route tables
4/9/2015
CST 415 - Computer Networks
8
RIP
Distance Vector Routing
• Each node knows the direct distance cost to
each of it’s neighbor nodes.
• Every node sends it’s distance vector table
to it’s neighbor nodes.
• When a node receives a distance vector
update, it will update it’s own distance
vector table with new information of cost
and next hops for all nodes in network.
• Send new information along.
• Repeat until no new information is added.
4/9/2015
CST 415 - Computer Networks
9
RIP
Distance Vector Routing - Formalized
– X : Source Node
– Y : Destination Node
– Z : Intermediate Node between X and Y
– Dx(Y,Z) : Distance at X from Y to Z
– c(X,Z) : Cost in Distance of the direct hop
from Y to Z
4/9/2015
CST 415 - Computer Networks
10
RIP – General Routing Idea
c(X,Z) = 3
X
3
Z
2
Y
Dx(Y,Z) = 2
Dx(Y,Z) = c(X,Z) + minw{Dz(Y,w)} The minw is taken over all the
distances given to Y in Z's route update (e.g. Z could have
multiple routes to Y).
When a packet needs to be sent from X to Y, X simply sends it to the route
is has computed as the shortest.
4/9/2015
CST 415 - Computer Networks
11
RIP – Table Format
Destination
Next hop
Distance
Timers
Flags
4/9/2015
– The network address of the destination network.
– IP address of the next packet destination.
– The distance in hops to the ultimate destination.
– Different times for route aging.
– Possible conditional flags associated with the route.
CST 415 - Computer Networks
12
RIP
c(X,Z) = 1
X
Z
Intermediary
Network
Dz(Y,w) = (2,4,8,3)
w-set of network routes
Dx(Y,Z) = c(X,Z) + minw{Dz(Y,w)}
= 1 + min(2,4,8,3)
= 3
Y
What is the
necessary
topology of the
Intermediary
Network?
Note: Z will really never have a list of routes to Y through the intermediary
network. It will maintain “it’s” shortest route information. Backward
propagation of shortest route information will select the “min”.
4/9/2015
CST 415 - Computer Networks
13
RIP
• RIP uses “hop count” as the metric to
measure distance.
– Fewer hops may not result in the shortest
latency.
• Active routers broadcast route update every
30 seconds.
• A Route will only stay active for 180
seconds.
– Stale routes (e.g. haven’t been updated in 180
seconds) will be removed from the routing
table.
4/9/2015
CST 415 - Computer Networks
14
RIP
• RIP defines a maximum hop count for
a valid route to be 16.
– This helps avoid the propagation of
circular routes.
4/9/2015
CST 415 - Computer Networks
15
RIP
Slow convergence
occurs because route
updates take a time to
propagate across the
network.
4/9/2015
CST 415 - Computer Networks
16
RIP – Message Format
4/9/2015
CST 415 - Computer Networks
17
RIP – Message Format
Command
Meaning
1
Request routing information
2
Response containing network-distance pairs from
senders routing tables.
Version
– 1 or 2 (2 handles subnet and supernetting)
Family of Net – See BSD4 Network Family Mumbers
(AF_INET for IP or 2).
4/9/2015
CST 415 - Computer Networks
18
OSPF
Open Shortest Path First
OSPF uses a different algorithm to perform
routing decisions.
OSPF working group was organized in
1988 because RIP had several
shortcomings when dealing with interior
routing in a large heterogeneous network.
4/9/2015
CST 415 - Computer Networks
19
OSPF
• Based on Bolt, Beranek, and Newman's
(BBN's) SPF algorithm developed in 1978
for the ARPANET.
• Unlike RIP, OSPF can operate within a
hierarchy.
– The largest entity within the hierarchy is the
autonomous system (AS).
– OSPF is an intra-AS (interior gateway) routing
protocol, capable of receiving routes from and
sending routes to other ASs.
4/9/2015
CST 415 - Computer Networks
20
OSPF
• Autonomous Systems
are broken down into
Areas.
• Areas communicate
through Area Border
Routers.
• The backbone network
connects areas together.
• A Area Border Router
maintains topological
information about
networks it is in charge
of bridging.
4/9/2015
CST 415 - Computer Networks
21
OSPF – Shortest Path
Find the shortest path starting a vertex “x” and
ending at vertex “y”.
2
2
R0
Example:
Shortest path
from R5 to R3.
R1
1
1
2
R2
R3
R4
7
5
3
R5
4/9/2015
CST 415 - Computer Networks
22
OSPF – Shortest Path
Shortest path from R5 to R3.
To do this, we will use the
“greedy method”
developed by Dijkstra.
Basically:
1. Start at the destination.
2. Choose the shortest path
back
3. traverse to that vertex.
4. Repeat until the source is
reached.
2
2
R0
R1
1
1
2
R2
R3
R4
7
5
3
R5
4/9/2015
CST 415 - Computer Networks
23
OSPF – Shortest Path
Shortest path from R5 to R3.
Basically:
1. Start at the destination.
2. Choose the shortest path
back
3. traverse to that vertex.
4. Repeat until the source is
reached.
2
2
R0
R1
1
1
2
R2
R3
R4
7
R3
5
3
R5
4/9/2015
CST 415 - Computer Networks
24
OSPF – Shortest Path
Shortest path from R5 to R3.
Basically:
1. Start at the destination.
2. Choose the shortest path
back
3. traverse to that vertex.
4. Repeat until the source is
reached.
2
2
R0
R1
1
1
2
R2
R3
R4
7
R3, R0
5
3
R5
4/9/2015
CST 415 - Computer Networks
25
OSPF – Shortest Path
Shortest path from R5 to R3.
Basically:
1. Start at the destination.
2. Choose the shortest path
back
3. traverse to that vertex.
4. Repeat until the source is
reached.
2
2
R0
R1
1
1
2
R2
R3
R4
7
R3, R0, R1
5
3
R5
4/9/2015
CST 415 - Computer Networks
26
OSPF – Shortest Path
Shortest path from R5 to R3.
Basically:
1. Start at the destination.
2. Choose the shortest path
back
3. traverse to that vertex.
4. Repeat until the source is
reached.
2
2
R0
R1
1
1
2
R2
R3
R4
7
R3, R0, R1,
R4,
5
3
R5
4/9/2015
CST 415 - Computer Networks
27
OSPF – Shortest Path
Shortest path from R5 to R3.
Basically:
1. Start at the destination.
2. Choose the shortest path
back
3. traverse to that vertex.
4. Repeat until the source is
reached.
2
2
R0
R1
1
1
2
R2
R3
R4
7
R3, R0, R1,
R4, R5 = 7
5
3
R5
4/9/2015
CST 415 - Computer Networks
28
OSPF – Shortest Path
• The algorithm described above is a
simplified version of Dijkstras
algorithm.
• The BBN algorithm is a further
refinement dealing with path priority.
• BBN is based on a graph structure and
a tree structure.
4/9/2015
CST 415 - Computer Networks
29
OSPF – Shortest Path
• To effect this shortest path calculation
– Each Area Border Router must maintain
information related to it’s managed area
topology.
– As routers adjust routes, the new information is
exchanged with neighbor routers.
– When new information arrives, the routers must
re-calculate their shortest path tables.
4/9/2015
CST 415 - Computer Networks
30
OSPF – Message Format
• OSPF messages have two parts
– The message header
– The Payload
»Hello Message
»Database Description Message
»Link Status Request Message
»Link Status Update Message
»Link Status Acknowledge Message
4/9/2015
CST 415 - Computer Networks
31
OSPF – Message Format : Header
•
•
Version number—Identifies the OSPF version used.
Type—Identifies the OSPF packet type as one of the following:
–
–
–
–
–
4/9/2015
Hello—Establishes and maintains neighbor relationships. Value - 1
Database description—Describes the contents of the topological database. These messages are
exchanged when an adjacency is initialized. Value - 2
Link-state request—Requests pieces of the topological database from neighbor routers. These
messages are exchanged after a router discovers (by examining database-description packets) that
parts of its topological database are outdated. Value - 3
Link-state update—Responds to a link-state request packet. These messages also are used for the
regular dispersal of LSAs. Several LSAs can be included within a single link-state update packet.
Value - 4
Link-state acknowledgment—Acknowledges link-state update packets. Value - 5
CST 415 - Computer Networks
32
OSPF – Message Format : Header
•
•
•
•
•
•
•
Message length—Specifies the packet length, including the OSPF header, in bytes.
Source Router IP Address—Identifies the source of the packet.
Area ID—Identifies the area to which the packet belongs. All OSPF packets are associated
with a single area.
Checksum—Checks the entire packet contents for any damage suffered in transit.
Authentication type—Contains the authentication type. All OSPF protocol exchanges are
authenticated. The authentication type is configurable on per-area basis.
Authentication—Contains authentication information.
Data—Contains encapsulated upper-layer information.
4/9/2015
CST 415 - Computer Networks
33