Transcript routed - Current UG - The University of Sydney

1
Routing Architecture and
Protocols
NETS3303/3603
Week 6
The University of Sydney
2
Outline
• Intro concepts
– Issues
– Architecture
• Routing protocols:
– Distance-vector
– Link-state
• Autonomous System and Exterior
Gateway Protocol
– BGP
• Interior Gateway Protocol
– RIP1 and RIP2
– OSPF
The University of Sydney
3
Review - Internet Routing
• IP implements datagram forwarding
• Both hosts and routers
– Have an IP module
– Forward datagrams
• IP forwarding is table-driven
– Table known as routing table
The University of Sydney
4
Elements of Routing
• routing protocols that allow info to be gathered
and distributed – routers communicate with these
protocols
• routing algorithms – compute good routes based
on gathered data (like Bellman-Ford and Dijkstra)
• routing table – database of routes
The University of Sydney
5
Its Classic problem!
The University of Sydney
6
How / When Are IP
Routing Tables Built?
• Depends on size / complexity of internet
• Static routing
– Fixes routes at boot time
– Useful only for simplest cases
• Dynamic routing
– Table initialized at boot time
– Values inserted / updated by protocols that propagate
route information
– Necessary in large internets
The University of Sydney
7
Routing Tables
• Two sources of information
– Initialization (e.g., from disk)
– Update (e.g., from protocols)
• Hosts tend to freeze the routing table after
initialization
• But, routers use protocols to learn new
information and update their routing table
dynamically
The University of Sydney
8
Original Arpanet Routing
Architecture
• Small set of ‘‘core’’ routers with complete
information about all destinations
• Other routers know local destinations and use
the core as central router (default route)
• Disadvantages of original core:
– Central bottleneck for all traffic
– No shortcut routes possible
– Does not scale
The University of Sydney
9
General Idea – Better!
• Have a set of core routers know routes to all
locations
• Devise a mechanism that allows other
routers to contact the core to learn routes
(spread necessary routing information
automatically)
• Continually update routing information
The University of Sydney
10
Automatic Route
Propagation
• Two basic algorithms used by routing
update protocols
– Distance-vector
– Link-state
• Many variations in implementation details
The University of Sydney
11
Distance-Vector Algorithm
• Initialize routing table with one entry for
each directly connected network
• Periodically run a distance-vector update to
exchange information with routers that are
reachable over directly connected networks
• Each router sends list of its routes to
another
The University of Sydney
12
DV algorithm
• examples: RIP, BGP
• Its algorithm elements:
– send: every N seconds out all connected
interfaces broadcast 2-tuples : (to network X,
hop count Y) ...
– recv: if new tuple, add to routing table; if better
tuple, change existing; if “dead” tuple, remove
– timeout: if no refresh, timeout entry in N * Y
seconds
The University of Sydney
13
Example Of DV Update
• Router K received an update from router J
• (a) is existing routing table at K
• (b) incoming update (marked items cause change)
The University of Sydney
14
slow convergence/count to
infinity
• DV’s big problem!
• changes can be sent when they occur, but must
recompute a bit so convergence takes time (made
worse by possible loops)
• count to infinity problem can occur too - routing
loop until hopcount reaches impossible value
The University of Sydney
15
Count to infinity
• C crashes, B knows C crashed but hasn’t told A, but
unfortunately A talks to B first B is told by A:
– I can get to C in two hops (and note it doesn’t mention to
B that the path is thru B)
• B says AHA!, that means I can get to C in three hops
and reports that to A
• A says AHA!, it’s now four hops to B and tells B
etc...
The University of Sydney
16
split-horizon and poison
reverse fixup
• Split-horizon:
– A does not tell B that it can reach C (white lie)
– Because its through B
• Poison reverse:
– When B loses connection to C, its distance to C is
changed to infinity
– An immediate update is triggered, without wait for
regular update
• when link goes away, B will know that there is no
path to C, and tell A
• Still doesn’t work in all cases…
The University of Sydney
17
Link-State Algorithm
• Alternative to distance-vector
• Distributed computation
– Broadcast information
– Allow each router to compute shortest paths
• Avoids problem where one router can
damage the entire internet by passing
incorrect information
• Also called Shortest Path First (SPF)
The University of Sydney
18
Link-State Update
• Participating routers learn internet topology
• Think of routers as nodes in a graph, and networks
connecting them as edges or links
• Pairs of directly-connected routers periodically
– Test link between them
– Propagate (broadcast) status of link
• All routers
B
C
A
D
E
– Receive link status messages
– Recompute routes from their local copy of information
The University of Sydney
F
19
1 - Determine link-state
The University of Sydney
20
2 - Send LS-update
The University of Sydney
21
3 - Compute shortest path
The University of Sydney
22
link-state: pros/cons
• pros
– converges faster, no count to infinity problem +
router can forward LSP immediately
– more functionality; e.g., each router has map
of net, can make network debugging easier
• cons
– more compute than DV (does this matter?)
The University of Sydney
23
ROUTING:
EXTERIOR GATEWAY
PROTOCOLS AND
AUTONOMOUS
SYSTEMS (BGP)
The University of Sydney
24
General Principle for
Internet Routing
• Although it is desirable for routers to
exchange routing information, it is
impractical for all routers in an arbitrarily
large internet to participate in a single
routing update protocol
• Consequence: routers must be divided into
groups
The University of Sydney
25
A Practical Limit On Group
Size
• Up to a dozen routers to participate in a
single routing area across a WAN
• approximately five times as many can safely
participate across a set of LANs
The University of Sydney
26
Router Outside A Group
• Does not participate directly in group’s
routing information propagation algorithm
• Problems:
– Will not choose optimal routes if it uses a
member of the group for general delivery
– May not know all networks from other groups
The University of Sydney
27
The Extra Hop
Problem
• Non-participating router picks one participating router to use (e.g., R2)
• Non-participating router routes all packets to R2 across backbone
• Router R2 routes some packets back across backbone to R1
• So, a mechanism is needed that allows nonparticipating
routers to learn routes from participating routers
– so they can choose optimal routes.
The University of Sydney
28
The Hidden Networks
Problem
• Group must learn routes from nonparticipating
routers
• Example: owner of networks 1 and 3 must tell
group that there is a route to network 4
The University of Sydney
29
Autonomous System
Concept (AS)
• Group of networks under one administrative
authority
• Free to choose internal routing update
mechanism
• Connects to one or more other autonomous
systems
The University of Sydney
30
EGPs: Exterior Gateway
Protocols
• A protocol for communicating routes
between two autonomous systems
• Solves two problems
– Allows router outside a group to advertise
networks hidden in another autonomous system
– Allows router outside a group to learn
destinations in the group
The University of Sydney
31
Border Gateway Protocol
• The most popular (virtually the only) EGP
in use in the Internet
• Current version is BGP-4
• Supports CIDR (mask accompanies each
route)
• Each AS designates a border router to speak
on its behalf
• Two border routers become BGP peers
The University of Sydney
32
Key Characteristics Of BGP
•
•
•
•
•
•
•
•
Provides inter-autonomous system communication
Propagates reachability information
Follows next-hop paradigm
Provides support for policies
Sends path information
Permits incremental updates
Allows route aggregation
Allows authentication
The University of Sydney
33
Additional BGP Facts
• Uses reliable transport (i.e., TCP)
– Unusual: most routing update protocols use
connectionless transport (e.g., UDP)
• Sends keepalive messages so other end
knows connection is valid (even if no new
routing information is needed)
The University of Sydney
34
Four BGP Message Types
The University of Sydney
35
BGP Message Header
• Each BGP message starts with this header
• Marker is used by peers to indicate message
boundary => synchronisation
The University of Sydney
36
BGP Open Message
• Used to start a connection
• HOLD TIME specifies max time that can
elapse between BGP messages
The University of Sydney
37
BGP Update Message
• Sender can advertise new routes or withdraw old
routes
• Each route entry consists of address and mask
• Entry can be compressed to eliminate zero bytes
The University of Sydney
38
BGP Must Consider
Receiver’s Perspective
• Two issues are
considered:
policies and
optimal routes
• Advertise not
just
destinations
but report
reachability
too
The University of Sydney
39
Path Metric
Interpretation
• Each AS use own IGP may be with different
metric (hop count, delay, policy-based values)
• So, an exterior gateway protocol does not
communicate or interpret metrics, even if metrics
are available!
• BGP only propagates reachability information
– a receiver can implement policy constraints
– BUT cannot choose a least cost route.
The University of Sydney
40
ROUTING: INSIDE AN
AUTONOMOUS SYSTEM
(RIP, OSPF)
• Static routes
–
–
–
–
Initialized at startup
Never change
Typical for host
Sometimes used for router
• Dynamic routes
–
–
–
–
Initialized at startup
Updated by route propagation protocols
Typical for router
Sometimes used in host
The University of Sydney
Exchanging Routing
Information Within An
Autonomous System
• Mechanisms called interior gateway
protocols, IGPs
• Choice of IGP is made by autonomous
system
The University of Sydney
41
42
Example Of Two Autonomous
Systems
And the Routing Protocols Used
RIP
The University of Sydney
OSPF
43
Routing Information
Protocol (RIP)
•
•
•
•
•
•
Implemented by UNIX program routed
Uses hop count metric
Distance-vector protocol
Relies on broadcast
Assumes low-delay LAN
Uses split horizon and poison reverse techniques
to solve inconsistencies
• Current standard is RIP2
The University of Sydney
44
Two Forms Of RIP
• Active
– Form used by routers
– Broadcasts routing updates periodically
– Uses incoming messages to update routes
• Passive
– Form used by hosts
– Uses incoming messages to update routes
– Does not send updates
The University of Sydney
45
RIP Operation
• Each router sends update every 30 seconds
• Update contains pairs of
(destination address, distance)
• Distance of 16 is infinity (i.e., no route)
– This limits span of its internet to 16 hops
– Any 2 nodes have at most 15 routers between
The University of Sydney
Illustration Of Hosts
Using Passive RIP
• Host routing table initialized to:
Destination
Route
128.10.0.0
default
Direct
128.10.0.200
• Host listens for RIP broadcast and uses data to update
table
• Eliminates ICMP redirects
The University of Sydney
46
47
Changes To RIP In Version 2
• RIP1 does not include subnet mask
– Only suitable for classful or fixed-len subnets
•
•
•
•
Update includes subnet mask
Authentication supported
Explicit next-hop information
Messages can be multicast (optional)
– IP multicast address is 224.0.0.9
The University of Sydney
48
RIP2 Update Format
The University of Sydney
49
Open Shortest Path First
(OSPF)
• Developed by IETF in response to vendors’
proprietary protocols
• Uses link-state algorithm
• More powerful than most predecessors
• Permits hierarchical topology
• More complex to install and manage
The University of Sydney
50
OSPF Features
• Type of service routing – the first to offer
• Load balancing across multiple paths
• Networks partitioned into subsets called areas
– Designated router per area
• Message authentication
• Virtual network topology abstracts away details
• Can import external routing information
The University of Sydney
51
OSPF Message Header
•
•
Each message starts with same header
OSPF Message Types
–
–
–
–
–
1 Hello (used to test reachability)
2 Database description (topology)
3 Link status request
4 Link status update
5 Link status acknowledgement
The University of Sydney
52
OSPF HELLO Message Format
• Used to establish and test reachability
The University of Sydney
OSPF Database Description
Message Format
Router
Network
Summary of nets
AS boundary
• Initialises network topology database
• One serve as a Master; other slave
• Can be large => separate into different msgs
– I is 1 for first message, M is 1 for more messages
The University of Sydney
53
54
Summary
• Internet is too large for all routers to participate in one
routing update protocol
• Group of networks and routers under one administrative
authority is called Autonomous System (AS)
• EGP is used to communicate routing information between
two autonomous systems
• Each AS chooses its own interior routing update protocol
• Popular IGPs include
– RIP (distance vector algorithm)
– OSPF (link-state algorithm)
The University of Sydney