Network system (Internetworking II) Notes

 Page 1


10/20/08?
1?
P561: Network Systems 
Week 4: Internetworking II 
Tom Anderson 
Ratul Mahajan 
TA: Colin Dixon 
Today 
Internet routing (BGP) 
Tunneling and MPLS 
Wireless routing 
Wireless handoffs 
2 
Internet today 
3 
Key goals for Internet routing 
Scalability 
Support arbitrary policies 
•? Finding “optimal” paths was less important 
(Supporting arbitrary topologies) 
4 
Internet routing overview 
Two-level hierarchy for scalability 
•? Intra-domain: within an ISP (OSPF, MPLS) 
•? Inter-domain: across ISPs (BGP) 
Path vector protocol between Ases 
•? Can support many policies 
•? Fewer messages in response to small changes 
•? Only impacted routers are informed 
5 
Path vector routing 
Similar to distance vector routing info includes  
entire paths 
6 
192.4.23, [7] 
192.4.23, [3, 7] 
Page 2


10/20/08?
1?
P561: Network Systems 
Week 4: Internetworking II 
Tom Anderson 
Ratul Mahajan 
TA: Colin Dixon 
Today 
Internet routing (BGP) 
Tunneling and MPLS 
Wireless routing 
Wireless handoffs 
2 
Internet today 
3 
Key goals for Internet routing 
Scalability 
Support arbitrary policies 
•? Finding “optimal” paths was less important 
(Supporting arbitrary topologies) 
4 
Internet routing overview 
Two-level hierarchy for scalability 
•? Intra-domain: within an ISP (OSPF, MPLS) 
•? Inter-domain: across ISPs (BGP) 
Path vector protocol between Ases 
•? Can support many policies 
•? Fewer messages in response to small changes 
•? Only impacted routers are informed 
5 
Path vector routing 
Similar to distance vector routing info includes  
entire paths 
6 
192.4.23, [7] 
192.4.23, [3, 7] 
10/20/08?
2?
Policy knobs 
1. Selecting one of the multiple offered paths 
2. Deciding who to offer paths 
7 
AS 1 
AS 2 
AS 3 
192.168.1.3/24, [2, 4] 
AS 4 
192.168.1.3/24, [3, 4] 
AS 1 
AS 2 
AS 3 
192.168.1.3/24, [4, 1] 
AS 4 
192.168.1.3/24, [4, 1] 
Path vector vs. link state vis-à-vis policy 
With path vector, implementing the policy above 
requires only local knowledge at AS3 
With link state, AS3 would need to know the 
policies of other ASes as well 
8 
3 
1 
2 
0 AS3 preferences 
    [31o] 
    [320] 
    [3210] 
    [3120] 
D 
Typical routing policies 
Driven by business considerations 
Two common types of relationships between ASes 
•? Customer-provider: customer pays provider 
•? Peering: no monetary exchange 
When selecting routes: customer > peer > provider 
When exporting routes: do not export provider or peer 
routes to other  
providers and peers 
Prefer routes with shorter AS paths 
9 
Peer or 
provider 
Peer or 
provider 
X
Customer Customer 
BGP at router level 
10 
BGP limitations 
Path quality 
Scale 
Convergence 
Security 
11 
Path quality with BGP 
Combination of local policies may not be globally 
good 
•? Longer paths, asymmetric paths 
•? Shorter “detours” are often available 
Example:  
hot potato routing 
12 
B
A
Page 3


10/20/08?
1?
P561: Network Systems 
Week 4: Internetworking II 
Tom Anderson 
Ratul Mahajan 
TA: Colin Dixon 
Today 
Internet routing (BGP) 
Tunneling and MPLS 
Wireless routing 
Wireless handoffs 
2 
Internet today 
3 
Key goals for Internet routing 
Scalability 
Support arbitrary policies 
•? Finding “optimal” paths was less important 
(Supporting arbitrary topologies) 
4 
Internet routing overview 
Two-level hierarchy for scalability 
•? Intra-domain: within an ISP (OSPF, MPLS) 
•? Inter-domain: across ISPs (BGP) 
Path vector protocol between Ases 
•? Can support many policies 
•? Fewer messages in response to small changes 
•? Only impacted routers are informed 
5 
Path vector routing 
Similar to distance vector routing info includes  
entire paths 
6 
192.4.23, [7] 
192.4.23, [3, 7] 
10/20/08?
2?
Policy knobs 
1. Selecting one of the multiple offered paths 
2. Deciding who to offer paths 
7 
AS 1 
AS 2 
AS 3 
192.168.1.3/24, [2, 4] 
AS 4 
192.168.1.3/24, [3, 4] 
AS 1 
AS 2 
AS 3 
192.168.1.3/24, [4, 1] 
AS 4 
192.168.1.3/24, [4, 1] 
Path vector vs. link state vis-à-vis policy 
With path vector, implementing the policy above 
requires only local knowledge at AS3 
With link state, AS3 would need to know the 
policies of other ASes as well 
8 
3 
1 
2 
0 AS3 preferences 
    [31o] 
    [320] 
    [3210] 
    [3120] 
D 
Typical routing policies 
Driven by business considerations 
Two common types of relationships between ASes 
•? Customer-provider: customer pays provider 
•? Peering: no monetary exchange 
When selecting routes: customer > peer > provider 
When exporting routes: do not export provider or peer 
routes to other  
providers and peers 
Prefer routes with shorter AS paths 
9 
Peer or 
provider 
Peer or 
provider 
X
Customer Customer 
BGP at router level 
10 
BGP limitations 
Path quality 
Scale 
Convergence 
Security 
11 
Path quality with BGP 
Combination of local policies may not be globally 
good 
•? Longer paths, asymmetric paths 
•? Shorter “detours” are often available 
Example:  
hot potato routing 
12 
B
A
10/20/08?
3?
Scaling pressures on BGP 
Too many prefixes (currently ~280K) 
Major factors behind growth: multi-homing and 
traffic engineering 
13 
Provider Customer 
Provider 1 
Provider 2 
Customer 
192.168.0.0/16 
192.168.0.0/16 
192.168.0.0/17 
192.168.0.0/16 
192.168.128.0/17 
BGP convergence (1/4) 
Temporary loops during path exploration 
Differentiating between failure and policy-based 
retraction can help but not completely 
14 
1 
0 
2 
D 3 
BGP convergence (2/4) 
Persistent loops can also form in BGP 
Fundamentally, the combination of local policies 
may not have a unique global solution 
15 
To get to D, X prefers  
   [X, (X+1) mod 3] 
   [X] 
   Others 
0 1 
2 
D 
BGP convergence (3/4) 
Several other issues have been uncovered 
•? Interaction with intra-domain routing 
•? Interaction with traffic engineering extensions 
•? Interaction with scalability extensions 
16 
BGP convergence (4/4) 
Q: What saves us in practice? 
A: Policy! (No guarantees, however) 
17 
0 1 
2 
D 
1 
0 
2 
D 3 
Policy reduces the 
number of valid paths 
Policy makes some 
preferences rare 
BGP security 
Extreme vulnerability to attacks and misconfigurations 
•? An AS can announce reachability to any prefix 
•? An AS can announce connectivity to other Ases 
Many known incidents 
•? AS7007 brought down the whole internet in 1997 
•? 75% of new route adverts are due to misconfigs [SIGCOMM 2002] 
•? Commonly used for spamming 
Technical solutions exist but none even close to deployment 
•? Incentives and deployability (Week 10) 
18 
Page 4


10/20/08?
1?
P561: Network Systems 
Week 4: Internetworking II 
Tom Anderson 
Ratul Mahajan 
TA: Colin Dixon 
Today 
Internet routing (BGP) 
Tunneling and MPLS 
Wireless routing 
Wireless handoffs 
2 
Internet today 
3 
Key goals for Internet routing 
Scalability 
Support arbitrary policies 
•? Finding “optimal” paths was less important 
(Supporting arbitrary topologies) 
4 
Internet routing overview 
Two-level hierarchy for scalability 
•? Intra-domain: within an ISP (OSPF, MPLS) 
•? Inter-domain: across ISPs (BGP) 
Path vector protocol between Ases 
•? Can support many policies 
•? Fewer messages in response to small changes 
•? Only impacted routers are informed 
5 
Path vector routing 
Similar to distance vector routing info includes  
entire paths 
6 
192.4.23, [7] 
192.4.23, [3, 7] 
10/20/08?
2?
Policy knobs 
1. Selecting one of the multiple offered paths 
2. Deciding who to offer paths 
7 
AS 1 
AS 2 
AS 3 
192.168.1.3/24, [2, 4] 
AS 4 
192.168.1.3/24, [3, 4] 
AS 1 
AS 2 
AS 3 
192.168.1.3/24, [4, 1] 
AS 4 
192.168.1.3/24, [4, 1] 
Path vector vs. link state vis-à-vis policy 
With path vector, implementing the policy above 
requires only local knowledge at AS3 
With link state, AS3 would need to know the 
policies of other ASes as well 
8 
3 
1 
2 
0 AS3 preferences 
    [31o] 
    [320] 
    [3210] 
    [3120] 
D 
Typical routing policies 
Driven by business considerations 
Two common types of relationships between ASes 
•? Customer-provider: customer pays provider 
•? Peering: no monetary exchange 
When selecting routes: customer > peer > provider 
When exporting routes: do not export provider or peer 
routes to other  
providers and peers 
Prefer routes with shorter AS paths 
9 
Peer or 
provider 
Peer or 
provider 
X
Customer Customer 
BGP at router level 
10 
BGP limitations 
Path quality 
Scale 
Convergence 
Security 
11 
Path quality with BGP 
Combination of local policies may not be globally 
good 
•? Longer paths, asymmetric paths 
•? Shorter “detours” are often available 
Example:  
hot potato routing 
12 
B
A
10/20/08?
3?
Scaling pressures on BGP 
Too many prefixes (currently ~280K) 
Major factors behind growth: multi-homing and 
traffic engineering 
13 
Provider Customer 
Provider 1 
Provider 2 
Customer 
192.168.0.0/16 
192.168.0.0/16 
192.168.0.0/17 
192.168.0.0/16 
192.168.128.0/17 
BGP convergence (1/4) 
Temporary loops during path exploration 
Differentiating between failure and policy-based 
retraction can help but not completely 
14 
1 
0 
2 
D 3 
BGP convergence (2/4) 
Persistent loops can also form in BGP 
Fundamentally, the combination of local policies 
may not have a unique global solution 
15 
To get to D, X prefers  
   [X, (X+1) mod 3] 
   [X] 
   Others 
0 1 
2 
D 
BGP convergence (3/4) 
Several other issues have been uncovered 
•? Interaction with intra-domain routing 
•? Interaction with traffic engineering extensions 
•? Interaction with scalability extensions 
16 
BGP convergence (4/4) 
Q: What saves us in practice? 
A: Policy! (No guarantees, however) 
17 
0 1 
2 
D 
1 
0 
2 
D 3 
Policy reduces the 
number of valid paths 
Policy makes some 
preferences rare 
BGP security 
Extreme vulnerability to attacks and misconfigurations 
•? An AS can announce reachability to any prefix 
•? An AS can announce connectivity to other Ases 
Many known incidents 
•? AS7007 brought down the whole internet in 1997 
•? 75% of new route adverts are due to misconfigs [SIGCOMM 2002] 
•? Commonly used for spamming 
Technical solutions exist but none even close to deployment 
•? Incentives and deployability (Week 10) 
18 
10/20/08?
4?
Tunneling 
Encapsulating one protocol within another 
The blue sources, destinations, networks are 
oblivious to tunneling 
The yellow network does not care if it carries blue 
(or green) packets 
19 
Tun 
Src 
Tun 
Dst 
Src Dst 
Tunneling is broadly useful technique 
Used widely today 
•? Secure access to remote networks (VPNs) 
•? Your laptop to corporate networks 
•? Between different sites of a company 
•? MPLS 
•? 6to4 
•? GRE 
•? SSH tunnels 
•? …. 
Think of it as a generalization of traditional layering 
20 
MPLS 
21 
LER 
LER 
LER 
LER 
LSR 
LSR 
LSR 
LSR 
LSR 
Benefits of MPLS (1/3) 
LSRs do not understand or maintain state for IP 
•? Can yield higher performance 
•? Without n
2
 pair-wise tunnels
 
22 
LER 
LER 
LER 
LER 
LSR 
LSR 
LSR 
LSR 
LSR 
Benefits of MPLS (2/3) 
Traffic engineering (load balancing)
 
23 
LER 
LER 
LER 
LER 
LSR 
LSR 
LSR 
LSR 
LSR 
Benefits of MPLS (3/3) 
Separation of traffic for security or for QoS 
24 
LER 
LER 
LER 
LER 
LSR 
LSR 
LSR 
LSR 
LSR 
Page 5


10/20/08?
1?
P561: Network Systems 
Week 4: Internetworking II 
Tom Anderson 
Ratul Mahajan 
TA: Colin Dixon 
Today 
Internet routing (BGP) 
Tunneling and MPLS 
Wireless routing 
Wireless handoffs 
2 
Internet today 
3 
Key goals for Internet routing 
Scalability 
Support arbitrary policies 
•? Finding “optimal” paths was less important 
(Supporting arbitrary topologies) 
4 
Internet routing overview 
Two-level hierarchy for scalability 
•? Intra-domain: within an ISP (OSPF, MPLS) 
•? Inter-domain: across ISPs (BGP) 
Path vector protocol between Ases 
•? Can support many policies 
•? Fewer messages in response to small changes 
•? Only impacted routers are informed 
5 
Path vector routing 
Similar to distance vector routing info includes  
entire paths 
6 
192.4.23, [7] 
192.4.23, [3, 7] 
10/20/08?
2?
Policy knobs 
1. Selecting one of the multiple offered paths 
2. Deciding who to offer paths 
7 
AS 1 
AS 2 
AS 3 
192.168.1.3/24, [2, 4] 
AS 4 
192.168.1.3/24, [3, 4] 
AS 1 
AS 2 
AS 3 
192.168.1.3/24, [4, 1] 
AS 4 
192.168.1.3/24, [4, 1] 
Path vector vs. link state vis-à-vis policy 
With path vector, implementing the policy above 
requires only local knowledge at AS3 
With link state, AS3 would need to know the 
policies of other ASes as well 
8 
3 
1 
2 
0 AS3 preferences 
    [31o] 
    [320] 
    [3210] 
    [3120] 
D 
Typical routing policies 
Driven by business considerations 
Two common types of relationships between ASes 
•? Customer-provider: customer pays provider 
•? Peering: no monetary exchange 
When selecting routes: customer > peer > provider 
When exporting routes: do not export provider or peer 
routes to other  
providers and peers 
Prefer routes with shorter AS paths 
9 
Peer or 
provider 
Peer or 
provider 
X
Customer Customer 
BGP at router level 
10 
BGP limitations 
Path quality 
Scale 
Convergence 
Security 
11 
Path quality with BGP 
Combination of local policies may not be globally 
good 
•? Longer paths, asymmetric paths 
•? Shorter “detours” are often available 
Example:  
hot potato routing 
12 
B
A
10/20/08?
3?
Scaling pressures on BGP 
Too many prefixes (currently ~280K) 
Major factors behind growth: multi-homing and 
traffic engineering 
13 
Provider Customer 
Provider 1 
Provider 2 
Customer 
192.168.0.0/16 
192.168.0.0/16 
192.168.0.0/17 
192.168.0.0/16 
192.168.128.0/17 
BGP convergence (1/4) 
Temporary loops during path exploration 
Differentiating between failure and policy-based 
retraction can help but not completely 
14 
1 
0 
2 
D 3 
BGP convergence (2/4) 
Persistent loops can also form in BGP 
Fundamentally, the combination of local policies 
may not have a unique global solution 
15 
To get to D, X prefers  
   [X, (X+1) mod 3] 
   [X] 
   Others 
0 1 
2 
D 
BGP convergence (3/4) 
Several other issues have been uncovered 
•? Interaction with intra-domain routing 
•? Interaction with traffic engineering extensions 
•? Interaction with scalability extensions 
16 
BGP convergence (4/4) 
Q: What saves us in practice? 
A: Policy! (No guarantees, however) 
17 
0 1 
2 
D 
1 
0 
2 
D 3 
Policy reduces the 
number of valid paths 
Policy makes some 
preferences rare 
BGP security 
Extreme vulnerability to attacks and misconfigurations 
•? An AS can announce reachability to any prefix 
•? An AS can announce connectivity to other Ases 
Many known incidents 
•? AS7007 brought down the whole internet in 1997 
•? 75% of new route adverts are due to misconfigs [SIGCOMM 2002] 
•? Commonly used for spamming 
Technical solutions exist but none even close to deployment 
•? Incentives and deployability (Week 10) 
18 
10/20/08?
4?
Tunneling 
Encapsulating one protocol within another 
The blue sources, destinations, networks are 
oblivious to tunneling 
The yellow network does not care if it carries blue 
(or green) packets 
19 
Tun 
Src 
Tun 
Dst 
Src Dst 
Tunneling is broadly useful technique 
Used widely today 
•? Secure access to remote networks (VPNs) 
•? Your laptop to corporate networks 
•? Between different sites of a company 
•? MPLS 
•? 6to4 
•? GRE 
•? SSH tunnels 
•? …. 
Think of it as a generalization of traditional layering 
20 
MPLS 
21 
LER 
LER 
LER 
LER 
LSR 
LSR 
LSR 
LSR 
LSR 
Benefits of MPLS (1/3) 
LSRs do not understand or maintain state for IP 
•? Can yield higher performance 
•? Without n
2
 pair-wise tunnels
 
22 
LER 
LER 
LER 
LER 
LSR 
LSR 
LSR 
LSR 
LSR 
Benefits of MPLS (2/3) 
Traffic engineering (load balancing)
 
23 
LER 
LER 
LER 
LER 
LSR 
LSR 
LSR 
LSR 
LSR 
Benefits of MPLS (3/3) 
Separation of traffic for security or for QoS 
24 
LER 
LER 
LER 
LER 
LSR 
LSR 
LSR 
LSR 
LSR 
10/20/08?
5?
Downsides of MPLS 
Unnecessary overhead 
•? If all you want is IP forwarding 
•? If link state routing can provide effective traffic engineering 
Robustness to failures 
•? Setting up a complete virtual circuit takes time 
•? Fast reroute works only for a handful for failures 
Opacity 
•? Traditional diagnosis tools do not work 
Complexity 
•? Requires more configuration at routers 
25 
MPLS adoption 
Pretty widespread 
•? Almost all tier-1 ISPs have deployed MPLS 
It offers tools that network admins badly need 
•? Practical concerns trumped purist views 
26 
Why is wireless routing different? 
Mobility and fast changing conditions 
Packet losses 
Interference 
27 
First generation of protocols 
Focus on mobility and changing conditions 
•? Used hop count as the quality metric 
•? Reactive route computation was more popular 
•? To avoid unnecessary topology maintenance overhead 
Examples: DSR, AODV 
28 
Hop count limitations 
It minimizes the number of hops and thus prefers 
longer links 
But longer links tend to have more loss 
•? Need more retransmissions for successful reception 
Retransmissions can consume more spectrum 
resources than using shorter hops 
•? Need to balance hops and losses 
29 
All links are not the same 
MIT’s indoor testbed