Transcript Chapter 16

Routing: In an Autonomous
System
Chapter 16
Introduction
• How does a router in an Autonomous System learn
about other networks within its AS?
– In an internet like the one shown in Figure 16.1, only
one path exists between any two points
– What happens when an additional router is added as in
Figure 16.2?
• An alternate path is introduced
– When alternate paths exist, one is usually chosen as the primary
path
– If routers along the primary path fail, the alternate path is chosen
– So what could be the problem with having alternate paths?
Introduction
• Routers within an autonomous system are interior
to each other
– To keep network reachability information accurate,
interior routers exchange routing information
– When the reachability information has been assembled
for the AS, using an Interior Gateway Protocol (IGP),
that information can be distributed to other AS’s using
an Exterior Gateway Protocol
• Thus a router would use both and Exterior and an Interior GP
• No single protocol has emerged as an IGP
– Possibly due to the diversity of topologies and technologies used
within AS’s
Routing Information Protocol
(RIP)
• RIP is a widely used IGP
– also known as routed, designed at UC Berkeley to
provide routing and reachability information on local
networks
– uses physical network broadcasts to exchange routing
messages quickly
– RIP is somewhat riding on the coattails of BSD UNIX
since routed was distributed along with it
– RIP was built and widely adopted before a formal
standard was written
Routing Information Protocol
(RIP)
• RIP uses distance-vector routing for local
networks and participants are:
– Active - advertise routes to others
• Routers are active
• Updates are taken from the router’s current table and are
broadcast every 30 seconds
– set of pairs (IP address, hop count)
– a router is defined as one hop from a directly connected network
– managers are allowed to configure artificial hops for slow nets
– Passive - listen to RIP messages and update their tables
• Hosts are passive
Routing Information Protocol
(RIP)
• What will the routing tables be for Figure 16.2?
• RIP rules:
– A route is not replaced with an equal cost route hysteresis
– Routes learned from RIP are timed, if message is not
received again in 180 seconds, update is not recorded
– RIP must handle 3 errors:
• Assume trusted participants or detect routing loops
• Use a low count for maximum possible distance - RIP uses 16
• RIP can create slow convergence because of slow propagation
Routing Information Protocol
(RIP)
• See Figure 16.4 for slow convergence example
• R1 has a connection and advertises distance 1
• R2 has learned from R1 and advertises distance 2
• R3 has learned from R2 and advertises distance 3
– When R1 loses its connection to network 1, it updates
its table to make the distance 16
– If R2 advertises before R1 does, R1 might update its
table, thinking that R2 has a better path
– Each router would increase its distance by one as
updates arrive...until infinity?
Solving Slow Convergence
• Split Horizon Update
– A router does not propagate information about a route
back over the same interface from which it arrived
• In our example, R2 would not advertise about network 1 to R1
• If R1 loses connectivity with network 1, it must stop
advertising
• Hold Down
– A router that is told that a network is unreachable must
wait for a period of time (60 seconds) after it receives a
message that the network is unreachable
• Wait long enough for routers to receive bad news
Solving Slow Convergence
• Poison Reverse
– When a connection is lost, the router includes an
infinite cost in its broadcasts
– It also uses triggered updates which force a router to
send an immediate broadcast when receiving bad news
• It does not wait for next broadcast interval
• Router minimizes the time it is vulnerable to believing bad
news
• Each solution introduces its own problems
• RIP is generally inefficient in a wide area network
RIP1 Message Format
• Two types of RIP messages
– Routing information messages
– Information request messages
RIP1 Message Format
• Figure 16.5 shows the header of a version 1 RIP
message, followed by (network IP, distance) pairs
– Command Field
•
•
•
•
•
•
•
1 Request for partial or full routing information
2 Network-distance pairs from sender’s routing table
3/4 Obsolete trace mode commands
5 Reserved for Sun Microsystems
9 Update request
10 Update response
11 Update acknowledge
– Version of RIP
RIP1 Address Conventions
• Network addresses reported by RIP can have an
address of up to 14 octets
– The zeroes insured 32 bit alignment
• RIP1 used classful addressing, no subnet masks
RIP2
• Version 2 of RIP included space for a subnet
mask, and a next hop IP address to get to each
network as shown in Figure 16.6
• The 16-bit Route Tag can propagate an AS’s
number which helps determine the origin of a
route
Transmitting RIP messages
• RIP messages are transmitted using UDP
• UDP is relied upon to hold the message length
• UDP port 512 is used for RIP
Disadvantage of RIP Hop Counts
• Two disadvantages
– Routing is restricted to hop counts
– The hop count value for infinity is 16 and restricts the
size of an internet using it
• At most 15 routers between any two hosts
• Hop counts do not always yield routes with least
delay or highest capacity
• Routing becomes static in that routes cannot be
changed due to changes in the network
The Hello Protocol
• Now obsolete, used on original NSFNET
• Used a metric of delay
• Hello provided two functions:
– synchronize clocks among a set of machines
– allow machines to compute shortest delay paths to
destinations
The Hello Protocol
• Each machine maintained a table of best estimate
of clocks in its neighbor’s machines
• Before transmitting a packet, a machine adds its
timestamp from its current clock value
• When the packet arrived at the receiver, an
estimate of delay was computed
– Timestamp - local estimate on receiver’s clock
• Therefore, when computing routes the metric used
was this delay
Delay Metrics and Oscillation
• Hello worked well
• However, delay is not used as a metric in most
protocols because:
– protocols that change routes quickly can become
unstable
– oscillation may occur when traffic switches back and
forth between two alternate paths
Delay Metrics and Oscillation
• To avoid oscillation:
– hold down time to prevent quick changes to tables
– round measurements or implement threshold values
– keep an average of recent values rather than individual
delays
• Delay depends heavily on traffic - see page 306
– What about different transmission media such as
satellite and low capacity serial lines?
Combining RIP, Hello and BGP
• A single router may use both an EGP and an IGP
• Perhaps a single piece of software could do both
• IGP products typically update routing tables with
information from routers within an AS
– advertising information from the local routing table
– changing local routing table when updates are received
• RIP trusts routers within its own AS to pass
correct data
Combining RIP, Hello and BGP
• However, exterior protocols like BGP do not trust
routers in other AS’s
– Why?
• Thus, EGPs do not advertise all possible routes
from the local routing table
Inter-Autonomous System
Routing
• Perhaps groups of AS’s might have more trust if
they are in the same “company”
– if they share administrative ties
• Grouping AS’s calls for metric transformations
– Paths within a group have lower cost than those paths
that cross group boundaries
– Adjusting for distances outside of an AS
gated
• gated is a mechanism that understands both IGPs
and BGP
• gated can:
– accept RIP messages and modify the local routing table
– advertise routes from within its AS using BGP
– be used between AS’s and between groups of routers
using an IGP
• Using gated, a system administrator could specify
– which networks could be advertised
– and how to report distances to those networks
The Open SPF Protocol (OSPF)
• What does OSPF provide?
– It is an open standard that anyone may use without
paying a license fee
– Type of service
– Load balancing
– A site may partition its networks and routers into areas
– Authentication of exchanges between routers (so that
only trusted routers propagate routing information
– An extended SPF algorithm
OSPF Message Format
• A 24-octet header contains
–
–
–
–
–
–
Version (8 bits)
Type (8 bits)
Message Length (16 bits)
IP address of the sender
Area ID
Authentication type
• 0 is none
• 1 indicates a password is used
– 8 octets for password
OSPF Hello Message Format
• Hello messages are sent periodically to test
neighbor reachability
• Message fields
–
–
–
–
–
–
Network mask
Dead timer, nonresponding neighbor is considered dead
Hello interval, normal period between Hello messages
Router priority
Designated and backup routers
IP addresses of neighbors from which Hello messages
have been received
Database Description Messages
• Messages which initialize the network topology
database
• Remember that OSPF is a link state protocol
• Messages have:
– Sequence number
– For each link in the network topology, there is
• link type
• link ID
• Advertising Router, link sequence number, checksum and age
Link Status Request/Update
Messages
• Link Status Request Message
– If a router discovers that parts of its database are out of
date, it can request an update from a neighbor
– The neighbor responds with current information
• Link Status Update Message
– Routers broadcast the status of links periodically
– Updates consist of a list of advertisements as in the
database description messages shown in Figure 16.12
Routing with Partial Information
• Not all routers have complete information
• Most AS’s have a router that connects the AS to
other AS’s
– If connecting to the Internet, at least one router
connects to an ISP
– Routers within the AS know about destinations in the
AS, but use a default route to send traffic to the ISP
• Routers at the center of the Internet have a
complete set of routes learned from the arbiter and
do not use default routing themselves
Routing with Partial Information
• Consequences of using default routes for routers
– Local routing errors can go undetected
• Something sent out incorrectly would come back into the AS
– Routing update messages are smaller than messages
which require complete information
Summary
• Routers under the control of a single manager run
an IGP to exchange routing information
• Three IGPs
– RIP - distance vector protocol, designed for local networks
• uses split horizon, hold down and poison reverse to eliminate
routing loops and count to infinity
– Hello - distance vector protocol which used delay as metric
– OSPF - link state protocol
• gated
– provides an interface between an IGP like RIP and an EGP like
BGP by gathering and advertising routes
For Next Time
• Exam #2
• Read Chapter 17
• Meet with group and turn in planning document