Transcript PPTX

CS 5565
Network Architecture and
Protocols
Lecture 20
Godmar Back
Announcements
• Project 2B due in 2 parts:
• Extra Credit Opportunities:
– Expand simulator (and your implementation)
to introduce multiple link failures and link
resurrection
CS 5565 Spring 2012
Routing Algorithms
Roadmap
• Done
– Discussed forwarding vs routing
– Discussed theory behind two major routing
algorithms:
• Link-state routing
• Distance Vector routing
– Discuss theory behind hierarchical routing
– Discuss application in Internet
• IPv4 addressing
• Next
• Routing in the Internet
CS 5565 Spring 2012
Hierarchical Addressing:
Route Aggregation
Hierarchical addressing allows efficient advertisement of
routing information:
Organization 0
200.23.16.0/23
Organization 1
200.23.18.0/23
Organization 2
200.23.20.0/23
Organization 7
.
.
.
.
.
.
Fly-By-Night-ISP
“Send me anything
with addresses
beginning
200.23.16.0/20”
Internet
200.23.30.0/23
ISPs-R-Us
CS 5565 Spring 2012
“Send me anything
with addresses
beginning
199.31.0.0/16”
Hierarchical Addressing:
More Specific Routes
ISPs-R-Us has a more specific route to Organization 1
Organization 0
200.23.16.0/23
Organization 2
200.23.20.0/23
Organization 7
.
.
.
.
.
.
Fly-By-Night-ISP
“Send me anything
with addresses
beginning
200.23.16.0/20”
Internet
200.23.30.0/23
ISPs-R-Us
Organization 1
200.23.18.0/23
CS 5565 Spring 2012
“Send me anything
with addresses
beginning 199.31.0.0/16
or 200.23.18.0/23”
Intra-AS vs Inter-AS Routing
• In Internet:
– Intra-AS known as Interior Gateway Protocols
(IGP)
– Most common Intra-AS routing protocols:
• RIP: Routing Information Protocol (original protocol,
now rarely used)
• OSPF: Open Shortest Path First
• IGRP/EIGRP: (Enhanced) Interior Gateway Routing
Protocol
– Inter-AS known as Border Gateway Protocols:
• BGP4: Only protocol used
CS 5565 Spring 2012
RIP (Routing Information Protocol)
• Distance vector algorithm
– Included in BSD-UNIX Distribution in 1982
• Distance metric: # of hops (max = 15 hops)
• Distance vectors: exchanged among neighbors every 30
sec via Response Message (also called advertisement)
• Each advertisement: list of up to 25 destination nets
within AS
u
v
A
z
C
B
D
w
x
y
CS 5565 Spring 2012
destination hops
u
1
v
2
w
2
x
3
y
3
z
2
A’s routing table
RIP: Example
z
w
A
x
D
B
C
Destination Network
y
Routing table in D
Next Router
Num. of hops to dest.
w
y
z
x
A
B
B
--
2
2
7
1
….
….
....
CS 5565 Spring 2012
RIP: Example
Dest
w
x
z
….
w
Next hops
- - C 4
… ...
A
Advertisement
from A to D
z
x
Destination Network
w
y
z
x
….
y
D
B
C
Routing table in D
Next Router
A
B
BA
-….
Num. of hops to dest.
2
2
75
1
....
CS 5565 Spring 2012
RIP: Link Failure and Recovery
If no advertisement heard after 180 sec →
neighbor/link declared dead
– routes via neighbor invalidated
– new advertisements sent to neighbors
– neighbors in turn send out new advertisements
(if tables changed)
– poison reverse used to prevent ping-pong loops
(infinite distance = 16 hops)
CS 5565 Spring 2012
RIP Table processing
• RIP routing tables managed by application-level
process called route-d (daemon)
• advertisements sent in UDP packets, periodically
repeated
routed
routed
Transprt
(UDP)
network
(IP)
Transprt
(UDP)
forwarding
table
link
forwarding
table
network
(IP)
link
physical
physical
CS 5565 Spring 2012
EIGRP
• Cisco proprietary
– See [Cisco Whitepaper], [Malhotra 2002]
• Distance Vector Protocol with enhancements
– Explicit Signaling (HELLO packets)
• DUAL “diffusing update algorithm”
– “feasible successor” concept guarantees loop
freedom
• Intuition: rather than count to infinity, trigger route
recomputation unless another loop-free path is
known
– Optimize this by keeping track of all advertised
routes, not just best one
CS 5565 Spring 2012
OSPF (Open Shortest Path First)
• “open”: publicly available protocol (not
proprietary)
• Uses Link State algorithm
– LS packet dissemination
– Topology map at each node
– Route computation using Dijkstra’s algorithm
• OSPF advertisement carries one entry per
neighbor router
– Advertisements have age field to allow for expiration
• Advertisements disseminated to entire AS (via
flooding)
– Carried in OSPF messages directly over IP (rather
than TCP or UDP)
CS 5565 Spring 2012
OSPF “advanced” features (not in RIP)
• Security: all OSPF messages authenticated (to
prevent malicious intrusion)
• Multiple same-cost paths allowed (only one path
in RIP)
• For each link, multiple cost metrics for different
TOS (e.g., satellite link cost set “low” for best
effort; high for real time)
• Integrated uni- and multicast support:
– Multicast OSPF (MOSPF) uses same
topology data base as OSPF
• Hierarchical OSPF in large domains.
CS 5565 Spring 2012
Hierarchical OSPF
CS 5565 Spring 2012
Hierarchical OSPF
• Two-level hierarchy: local area, backbone.
– link-state advertisements only in same area
– each nodes has detailed area topology; only
know direction (shortest path) to nets in other
areas.
• Area border routers: “summarize” distances to
nets in own area, advertise to other Area Border
routers.
• Backbone routers: run OSPF routing limited to
backbone.
• Boundary routers: connect to other AS’s.
CS 5565 Spring 2012
Internet Inter-AS routing: BGP
• BGP (Border Gateway Protocol): the de facto
standard
• BGP provides each AS a means to:
1. Obtain subnet reachability information from
neighboring ASs.
2. Propagate the reachability information to all routers
internal to the AS.
3. Determine “good” routes to subnets based on
reachability information and policy.
• Allows a subnet to advertise its existence to rest
of the Internet: “I am here”
CS 5565 Spring 2012
BGP Basics
• Pairs of routers (BGP peers) exchange routing info
over semi-permanent TCP conctns: BGP sessions
• Note that BGP sessions do not always correspond to
physical links.
• When AS2 advertises a prefix to AS1, AS2 is
promising it will forward any datagrams destined to
that prefix towards the prefix.
– AS2 can aggregate prefixes in its advertisement
3c
3a
3b
AS3
1a
AS1
2a
1c
1d
1b
2c
AS2
2b
eBGP session
iBGP session
CS 5565 Spring 2012
Distributing Reachability Info
• With eBGP session between 3a and 1c, AS3 sends prefix
reachability info to AS1.
• 1c can then use iBGP do distribute this new prefix reach info to
all routers in AS1
• 1b can then re-advertise the new reach info to AS2 over the 1bto-2a eBGP session
• When router learns about a new prefix, it creates an entry for the
prefix in its forwarding table.
3c
3a
3b
AS3
1a
AS1
2a
1c
1d
1b
2c
AS2
2b
eBGP session
iBGP session
CS 5565 Spring 2012
Path Attributes & BGP Routes
• When advertising a prefix, advert includes BGP
attributes.
– prefix + attributes = “route”
• Two important attributes:
– AS-PATH: contains the ASs through which the advert
for the prefix passed: AS 67 AS 17
– NEXT-HOP: Indicates the specific internal-AS router
to next-hop AS. (There may be multiple links from
current AS to next-hop-AS.)
• When gateway router receives route advert,
uses import policy to accept/decline.
CS 5565 Spring 2012
BGP Route Selection
• Router may learn about more than 1
route to some prefix. Router must select
route.
• Elimination rules:
1. Local preference value attribute: policy
decision
2. Shortest AS-PATH (like DV routing, except
with more information!)
3. Closest NEXT-HOP router: hot potato routing
4. Additional criteria
CS 5565 Spring 2012
Path Vector Routing in BGP
• Accomplished via AS-PATH attributes
– Each node is entire AS!
CS 5565 Spring 2012
BGP routing policy
legend:
B
W
provider
network
X
A
customer
network:
C
Y
Figure 4.5-BGPnew: a simple BGP scenario
• A,B,C are provider networks
• X,W,Y are customer (of provider networks)
• X is dual-homed: attached to two networks
– X does not want to route from B via X to C
– .. so X will not advertise to B a route to C
CS 5565 Spring 2012
BGP routing policy (2)
legend:
B
W
provider
network
X
A
customer
network:
C
Y
Figure 4.5-BGPnew: a simple BGP scenario
• A advertises
to B the path AW
• B advertises to X the path BAW
• Should B advertise to C the path BAW?
– No way! B gets no “revenue” for routing CBAW since neither W
nor C are B’s customers
– B wants to force C to route to w via A
– B wants to route only to/from its customers!
CS 5565 Spring 2012
Relationship between OSPF&BGP
• OSPF hierarchy
is intra-AS
• BGP connects
ASs
CS 5565 Spring 2012
Motivation for different Intra/Inter Protocols
Policy:
• Inter-AS: admin wants control over how its traffic
routed, who routes through its net.
• Intra-AS: single admin, so no policy decisions
needed
Scale:
• hierarchical routing saves table size, reduced
update traffic
Performance:
• Intra-AS: can focus on performance
• Inter-AS: policy may dominate over performance
CS 5565 Spring 2012
Usage of Routing Protocols
EBGP
Sessions
IntraInter-
1,490
13,830
OSPF
9,624
1,161
IGP
EIGRP
RIP
12,741
1,342
156
161
Total
22,521
2,664
• Sample obtained by reverse-engineering
router config files
• Source David Maltz et al:
– Routing Design in Operational Networks – A
Look from the inside, [SIGCOMM 2004]
CS 5565 Spring 2012
Summary
• IP
– Addressing, subnets
•
•
•
•
ICMP
RIP
OSPF
BGP
CS 5565 Spring 2012