Transcript ppt

15-744: Computer Networking
L-7 Routing Issues
New Routing Ideas
•
•
•
•
Border Gateway Protocol (BGP) cont.
Overlay networks
Active networks
Assigned reading
• [S+99] The End-to-End Effects of Internet Path
Selection
• [W99] Active network vision and reality: lessons
from a capsule-based system
© Srinivasan Seshan, 2002
L -7; 2-6-02
2
Outline
• Multi-Homing
• Stability Issues
• Overlay Routing
• Active Networks
© Srinivasan Seshan, 2002
L -7; 2-6-02
3
Multi-homing
• With multi-homing, a single network has
more than one connection to the Internet.
• Improves reliability and performance:
• Can accommodate link failure
• Bandwidth is sum of links to Internet
• Challenges
• Getting policy right (MED, etc..)
• Addressing
© Srinivasan Seshan, 2002
L -7; 2-6-02
4
Multi-homing to Multiple Providers
• Major issues:
• Addressing
• Aggregation
ISP3
• Customer address
space:
ISP1
• Delegated by ISP1
• Delegated by ISP2
• Delegated by ISP1 and
ISP2
• Obtained independently
© Srinivasan Seshan, 2002
ISP2
Customer
L -7; 2-6-02
5
Address Space from one ISP
• Customer uses address
space from ISP1
• ISP1 advertises /16
aggregate
• Customer advertises /24
route to ISP2
• ISP2 relays route to ISP1
and ISP3
• ISP2-3 use /24 route
• ISP1 routes directly
• Problems with traffic load?
© Srinivasan Seshan, 2002
ISP3
138.39/16
ISP1
ISP2
Customer
138.39.1/24
L -7; 2-6-02
6
Pitfalls
• ISP1 aggregates to a /19 at
border router to reduce
internal tables.
• ISP1 still announces /16.
• ISP1 hears /24 from ISP2.
• ISP1 routes packets for
customer to ISP2!
• Workaround: ISP1 must
inject /24 into I-BGP.
ISP3
138.39/16
ISP1
ISP2
138.39.0/19
Customer
138.39.1/24
© Srinivasan Seshan, 2002
L -7; 2-6-02
7
Address Space from Both ISPs
• ISP1 and ISP2 continue to
announce aggregates
• Load sharing depends on
traffic to two prefixes
• Lack of reliability: if ISP1 link
goes down, part of customer
becomes inaccessible.
• Customer may announce
prefixes to both ISPs, but
still problems with longest
match as in case 1.
© Srinivasan Seshan, 2002
L -7; 2-6-02
ISP3
ISP1
138.39.1/24
ISP2
204.70.1/24
Customer
8
Address Space Obtained Independently
• Offers the most
control, but at the cost
of aggregation.
• Still need to control
paths
• Many ISP’s ignore
advertisements of less
than /19
© Srinivasan Seshan, 2002
ISP3
ISP1
ISP2
Customer
L -7; 2-6-02
9
Outline
• Multi-Homing
• Stability Issues
• Overlay Routing
• Active Networks
© Srinivasan Seshan, 2002
L -7; 2-6-02
10
Signs of Routing Instability
• Record of BGP messages at major
exchanges
• Discovered orders of magnitude larger than
expected updates
• Bulk were duplicate withdrawals
• Stateless implementation of BGP – did not keep
track of information passed to peers
• Impact of few implementations
• Strong frequency (30/60 sec) components
• Interaction with other local routing/links etc.
© Srinivasan Seshan, 2002
L -7; 2-6-02
11
Route Flap Storm
• Overloaded routers fail to send Keep_Alive
message and marked as down
• I-BGP peers find alternate paths
• Overloaded router re-establishes peering
session
• Must send large updates
• Increased load causes more routers to fail!
© Srinivasan Seshan, 2002
L -7; 2-6-02
12
Route Flap Dampening
• Routers now give higher priority to
BGP/Keep_Alive to avoid problem
• Associate a penalty with each route
• Increase when route flaps
• Exponentially decay penalty with time
• When penalty reaches threshold, suppress
route
© Srinivasan Seshan, 2002
L -7; 2-6-02
13
BGP Limitations: Oscillations
AS 0
(*R,1R,2R)
R
AS 1
AS 2
(0R,1R,*R)
© Srinivasan Seshan, 2002
(0R,*R,2R)
L -7; 2-6-02
14
BGP Limitations: Oscillations
AS 0
(-,*1R,2R)  (*R,1R,2R)
W
R
W
W
AS 1
AS 2
(*0R,-,2R)  (0R,*R,2R)
(0R,1R,*R)  (*0R,1R,-)
© Srinivasan Seshan, 2002
L -7; 2-6-02
15
BGP Limitations: Oscillations
AS 0
(-,*1R,2R)  (-,*1R,2R)
01R
01R
R
AS 1
AS 2
(-,-,*2R) (*0R,-,2R)
(*0R,1R,-) (01R,*1R,-)
© Srinivasan Seshan, 2002
L -7; 2-6-02
16
BGP Limitations: Oscillations
AS 0
(-,-,*2R) (-,*1R,2R)
10R
R
AS 1
AS 2
(01R,*1R,-)  (*01R,10R,-)
© Srinivasan Seshan, 2002
10R
L -7; 2-6-02
(-,-,*2R) (-,-,*2R)
17
BGP Limitations: Oscillations
AS 0
(-,-,-)  (-,-,*2R)
20R
R
AS 1
AS 2
(*01R,10R,-)  (*01R,10R,-)
© Srinivasan Seshan, 2002
20R
L -7; 2-6-02
(-,-,*20R)  (-,-,*2R)
18
BGP Limitations: Oscillations
AS 0
(-,*12R,-)  (-,-,-)
12R
R
AS 1
AS 2
(*01R,10R,-) (*01R,-,-)
© Srinivasan Seshan, 2002
12R
L -7; 2-6-02
(-,-,*20R)  (-,-,*20R)
19
BGP Limitations: Oscillations
AS 0
(-,*12R,21R)  (-,*12R,-)
21R
R
AS 1
AS 2
(*01R,-,-) (*01R,-,-)
© Srinivasan Seshan, 2002
21R
L -7; 2-6-02
(-,-,-)  (-,-,*20R)
20
BGP Oscillations
• Can possible explore every possible path through
network  (n-1)! Combinations
• Limit between update messages (MinRouteAdver)
reduces exploration
• Forces router to process all outstanding messages
• Typical Internet failover times
• New/shorter link  60 seconds
• Results in simple replacement at nodes
• Down link  180 seconds
• Results in search of possible options
• Longer link  120 seconds
• Results in replacement or search based on length
© Srinivasan Seshan, 2002
L -7; 2-6-02
21
Outline
• Multi-Homing
• Stability Issues
• Overlay Routing
• Active Networks
© Srinivasan Seshan, 2002
L -7; 2-6-02
22
Overlay Routing
• Basic idea:
• Treat multiple hops through IP network as one hop in
overlay network
• Run routing protocol on overlay nodes
• Why?
• For performance – can run more clever protocol on
overlay
• For efficiency – can make core routers very simple
• For functionality – can provide new features such as
multicast, active processing, IPv6
© Srinivasan Seshan, 2002
L -7; 2-6-02
23
Overlay for Features
• How do we add new features to the network?
• Does every router need to support new feature?
• Choices
• Reprogram all routers  active networks
• Support new feature within an overlay
• Basic technique: tunnel packets
• Tunnels
• IP-in-IP encapsulation
• Poor interaction with firewalls, multi-path routers, etc.
© Srinivasan Seshan, 2002
L -7; 2-6-02
24
Examples
• IP V6 & IP Multicast
• Tunnels between routers supporting feature
• Mobile IP
• Home agent tunnels packets to mobile host’s
location
• QOS
• Needs some support from intermediate routers
© Srinivasan Seshan, 2002
L -7; 2-6-02
25
Overlay for Efficiency
• Multi-path routing
• More efficient use of links or QOS
• Need to be able to direct packets based on
more than just destination address  can be
computationally expensive
• What granularity? Per source? Per connection?
Per packet?
• Per packet  re-ordering
• Per source, per flow  coarse grain vs. fine grain
• Take advantage of relative duration of flows
• Most bytes on long flows
© Srinivasan Seshan, 2002
L -7; 2-6-02
26
Edge vs. Core Routers
• Island of routers
• Edges can perform complex computation to
classify flow
• Cores do extremely simple forwarding
• How to communicate computation results
• MPLS
• Dynamic packet state
© Srinivasan Seshan, 2002
L -7; 2-6-02
27
Overlay for Performance [S+99]
• Why would IP routing not give good
performance?
• Policy routing – limits selection/advertisement
of routes
• Early exit/hot-potato routing – local not global
incentives
• Lack of performance based metrics – AS hop
count is the wide area metric
• How bad is it really?
• Look at performance gain an overlay provides
© Srinivasan Seshan, 2002
L -7; 2-6-02
28
Quantifying Performance Loss
• Measure round trip time (RTT) and loss rate
between pairs of hosts
• ICMP rate limiting
• Alternate path characteristics
• 30-55% of hosts had lower latency
• 10% of alternate routes have 50% lower
latency
• 75-85% have lower loss rates
© Srinivasan Seshan, 2002
L -7; 2-6-02
29
Bandwidth Estimation
• RTT & loss for multi-hop path
• RTT by addition
• Loss either worst or combine of hops – why?
• Large number of flows combination of probabilities
• Small number of flows worst hop
• Bandwidth calculation
• TCP bandwidth is based primarily on loss and
RTT
• 70-80% paths have better bandwidth
• 10-20% of paths have 3x improvement
© Srinivasan Seshan, 2002
L -7; 2-6-02
30
Possible Sources of Alternate Paths
• A few really good or bad AS’s
• No, benefit of top ten hosts not great
• Better congestion or better propagation
delay?
• How to measure?
• Propagation = 10th percentile of delays
• Both contribute to improvement of performance
© Srinivasan Seshan, 2002
L -7; 2-6-02
31
Overlay Challenges
• “Routers” no longer have complete
knowledge about link they are responsible
for
• How do you build efficient overlay
• Probably don’t want all N2 links – which links to
create?
• Without direct knowledge of underlying
topology how to know what’s nearby and what
is efficient?
© Srinivasan Seshan, 2002
L -7; 2-6-02
32
Future of Overlay
• Application specific overlays
• Why should overlay nodes only do routing?
• Caching
• Intercept requests and create responses
• Transcoding
• Changing content of packets to match available
bandwidth
• Peer-to-peer applications
© Srinivasan Seshan, 2002
L -7; 2-6-02
33
Outline
• Multi-Homing
• Stability Issues
• Overlay Routing
• Active Networks
© Srinivasan Seshan, 2002
L -7; 2-6-02
34
Why Active Networks?
• Traditional networks route packets looking
only at destination
• Also, maybe source fields (e.g. multicast)
• Problem
• Rate of deployment of new protocols and
applications is too slow
• Solution
• Allow computation in routers to support new
protocol deployment
© Srinivasan Seshan, 2002
L -7; 2-6-02
35
Active Networks
• Nodes (routers) receive packets:
• Perform computation based on their internal
state and control information carried in packet
• Forward zero or more packets to end points
depending on result of the computation
• Users and apps can control behavior of the
routers
• End result: network services richer than
those by the simple IP service model
© Srinivasan Seshan, 2002
L -7; 2-6-02
36
Why not IP?
• Applications that do more than IP forwarding
•
•
•
•
•
•
•
•
Firewalls
Web proxies and caches
Transcoding services
Nomadic routers (mobile IP)
Transport gateways (snoop)
Reliable multicast (lightweight multicast, PGM)
Online auctions
Sensor data mixing and fusion
• Active networks makes such applications easy to
develop and deploy
© Srinivasan Seshan, 2002
L -7; 2-6-02
37
Variations on Active Networks
• Programmable routers
• More flexible than current configuration mechanism
• For use by administrators or privileged users
• Active control
• Forwarding code remains the same
• Useful for management/signaling/measurement of
traffic
• “Active networks”
• Computation occurring at the network (IP) layer of the
protocol stack  capsule based approach
• Programming can be done by any user
• Source of most active debate
© Srinivasan Seshan, 2002
L -7; 2-6-02
38
Case Study: MIT ANTS System
• Conventional Networks:
• All routers perform same computation
• Active Networks:
• Routers have same runtime system
• Tradeoffs between functionality,
performance and security
© Srinivasan Seshan, 2002
L -7; 2-6-02
39
System Components
• Capsules
• Active Nodes:
• Execute capsules of protocol and maintain
protocol state
• Provide capsule execution API and safety using
OS/language techniques
• Code Distribution Mechanism
• Ensure capsule processing routines
automatically/dynamically transfer to node as
needed
© Srinivasan Seshan, 2002
L -7; 2-6-02
40
Capsules
• Each user/flow programs router to handle
its own packets
• Code sent along with packets
• Code sent by reference
• Protocol:
• Capsules that share the same processing code
• May share state in the network
• Capsule ID is MD5 of code
© Srinivasan Seshan, 2002
L -7; 2-6-02
41
Capsules
Active
Node
IP
Router
Capsule
IP Header
Version
Active
Node
Capsule
Type
Previous
Address
Type Dependent
Header Files
Data
ANTS-specific header
• Capsules are forwarded past normal IP routers
© Srinivasan Seshan, 2002
L -7; 2-6-02
42
Capsules
Request for code
Active
Node 1
IP
Router
Capsule
Active
Node 2
Capsule
• When node receives capsule uses “type” to
determine code to run
• If no code at node requests code from “previous
address” node
• Likely to have code since it was recently used
© Srinivasan Seshan, 2002
L -7; 2-6-02
43
Capsules
Code Sent
Active
Node 1
IP
Router
Active
Node 2
Capsule
Capsule
• Code is transferred from previous node
• Size limited to 16KB
• Code is signed by trusted authority (e.g. IETF)
to guarantee reasonable global resource use
© Srinivasan Seshan, 2002
L -7; 2-6-02
44
Research Questions
• Execution environments
• What can capsule code access/do?
• Safety, security & resource sharing
• How isolate capsules from other flows,
resources?
• Performance
• Will active code slow the network?
• Applications
• What type of applications/protocols does this
enable?
© Srinivasan Seshan, 2002
L -7; 2-6-02
45
Functions Provided by Capsule
• Environment Access
• Querying node address, time, routing tables
• Capsule Manipulation
• Access header and payload
• Control Operations
• Create, forward and suppress capsules
• How to control creation of new capsules?
• Storage
• Soft-state cache of app-defined objects
© Srinivasan Seshan, 2002
L -7; 2-6-02
46
Safety, Resource Mgt, Support
• Safety:
• Provided by mobile code technology (e.g. Java)
• Resource Management:
• Node OS monitors capsule resource
consumption
• Support:
• If node doesn’t have capsule code, retrieve
from somewhere on path
© Srinivasan Seshan, 2002
L -7; 2-6-02
47
Applications/Protocols
• Limitations
• Expressible  limited by execution
environment
• Compact  less than 16KB
• Fast  aborted if slower than forwarding rate
• Incremental  not all nodes will be active
• Proof by example
• Host mobility, multicast, path MTU, Web cache
routing, etc.
© Srinivasan Seshan, 2002
L -7; 2-6-02
48
Discussion
• Active nodes present lots of applications
with a desirable architecture
• Key questions
• Is all this necessary at the forwarding level of
the network?
• Is ease of deploying new apps/services and
protocols a reality?
© Srinivasan Seshan, 2002
L -7; 2-6-02
49
Next Lecture: Mobile Routing
• Mobile IP
• Ad-hoc networks
• Assigned reading
• [Joh96] Scalable Support for Transparent
Mobile Host Internetworking
• [BMJ+98] A Performance Comparison of MultiHop Wireless Ad Hoc Routing Protocols
© Srinivasan Seshan, 2002
L -7; 2-6-02
50