Transcript i-2 routing scalability

i-4 routing scalability
Taekyoung Kwon
Some slides are from Geoff Huston, Michalis Faloutsos,
Paul Barford, Jim Kurose, Paul Francis, and Jennifer Rexford
outline
• What is routing?
• Current Internet routing
– Focus on BGP
• Routing scalability
• A case study in IP routing: ViAggre
• What is the design space?
What is routing
routing
• How do packets get from A to B in the
Internet?
Internet
A
B
One example
• Connectionless forwarding
– Each router (switch) makes a LOCAL decision
to forward the packet towards B
R1
R4
R7
R6
A
R2
B
R8
R3
R5
Routing is…
• How does each router know the correct
local forwarding decision for any
possible destination address?
– Through info of the network topology
– This info is maintained by a routing protocol
• Information
– Table size * update rate
Routing taxonomy
• Distributed* vs. centralized
• Static vs. dynamic*
– # of hops vs. traffic load
• Intra-domain vs. inter-domain
Current Internet routing
Goals of internet routing
•
•
•
•
•
Inter-connection
Fault-tolerant
Scalability
performance
….
Internet routing: two levels
• Autonomous system (AS) level
– Inter-domain
– BGP
• Router level
– Intra-domain
– RIP, OSPF,…
Internet structure
Original idea
Backbone service provider
“ Consumer” ISP
Small
corporation
Large corporation
“Consumer”ISP
“Consumer ” ISP
Small
corporation
Small
corporation
“Consumer ” ISP
Small
corporation
Internet structure
• The reality is…
* Why peering?
Source: Arbor Networks
Internet structure
• And many tiers
local
ISP
Tier 3
ISP
Tier-2 ISP
local
ISP
local
ISP
local
ISP
Tier-2 ISP
Tier 1 ISP
Tier 1 ISP
Tier-2 ISP
local
local
ISP
ISP
Tier 1 ISP
Tier-2 ISP
local
ISP
Tier-2 ISP
local
ISP
Internet routing
• Prefix is advertised across ASs
Path: 6, 5, 4, 3, 2, 1
4
3
5
2
1
Client
7
6
SNU
147.46.0.0/16
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 reachability information to all ASinternal routers.
3. Determine “good” routes to subnets based on
reachability information and policy.
• allows subnet to advertise its existence to
rest of Internet: “I am here”
BGP basics
• pairs of routers (BGP peers) exchange routing
info over semi-permanent TCP connections: BGP
sessions
• when AS1 advertises a prefix of AS2 to AS3:
– AS1 promises it will forward datagrams towards
that prefix.
– AS1 can aggregate prefixes in its advertisement
eBGP session
3c
3a
3b
AS3
2.0.0.0/8
2.3.4.0/24
1a
AS1
iBGP session
2a
1c
1d
2c
AS2
1b
2.3.0.0/16
2b
Distributing reachability info
• using eBGP session between 3a and 1c, AS3
sends prefix reachability info to AS1.
– 1c can then use iBGP do distribute new prefix
info to all routers in AS1
– 1b can then re-advertise new reachability info to
AS2 over 1b-to-2a eBGP session
• when router learns of new prefix, it creates
entry for prefix in its forwarding table.
eBGP session
3c
3a
3b
AS3
1a
AS1
iBGP session
2a
1c
1d
2c
AS2
1b
2b
Path attributes & BGP routes
• advertised prefix includes BGP attributes.
– prefix + attributes = “route”
• two important attributes:
– AS-PATH: contains ASs through which prefix advertisement has
passed: e.g. AS 6431, AS 7018
– NEXT-HOP: indicates specific internal-AS router to next-hop AS.
(may be multiple links from current AS to next-hop-AS)
• when gateway router receives route advertisement, uses
import policy to accept/decline.
BGP route selection
•
•
router may learn about more than 1 route
to some prefix. Router must select a route.
elimination rules:
1.
2.
3.
4.
local preference value attribute: policy decision
shortest AS-PATH
closest NEXT-HOP router: hot potato routing
additional criteria
Network Layer
4-17
BGP messages
• BGP messages exchanged using TCP.
• BGP messages:
– OPEN: opens TCP connection to peer and
authenticates sender
– UPDATE: advertises new path (or withdraws old)
– KEEPALIVE keeps connection alive in absence of
UPDATES; also ACKs OPEN request
– NOTIFICATION: reports errors in previous msg; also
used to close connection
Network Layer
4-18
BGP routing policy (1/2)
legend:
B
W
X
A
provider
network
customer
network:
C
Y
 A,B,C are provider networks
 X,W,Y are customers (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

Network Layer
4-19
BGP routing policy (2/2)
legend:
B
W
X
A
provider
network
customer
network:
C
Y
 A advertises path AW to B
 B advertises path BAW to X
 Should B advertise path BAW to C?
 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!
Network Layer
4-20
Why Intra- and Inter-AS routing different?
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
Network Layer
4-21
Routing scalability
Routing table (RT) growth
• Multi-homing
• Traffic engineering
• Non-aggregatable prefix allocation
routing message updates
• BGP update messages
ViAggre
Why routing scalability matters?
• FIB is expensive
Virtual aggregation (ViAggre)
ViAggre: Basic Idea
ViAggre: Basic Idea
ViAggre: Control Plane
More practically,…
Data plane operations
Route stretch
Ingress -> aggregation point
Aggregation point -> egress (1/3)
Aggregation point -> egress (2/3)
Aggregation point -> egress (3/3)
Design Space
now
• We will consider general routing design
space
– IP is just one of the possibilities
– But IP networking environments had better
be considered as much as possible
Design goal of routing
1. Scalability (memory): e.g. sublinear RT size scaling
2. Quality (stretch): the length of a chosen path by a
routing scheme compared to shortest path
3. Reliability: fast convergence upon topology changes
while minimizing communication costs to maintain
coherent non-local knowledge about network
topology
4. Name-independent routing: accommodate node
addresses/labels assigned independently of the
topology (otherwise need to split locator and ID
parts in addressing architecture)
5. Message overhead
Issue 1: Addressing and routing
• Rekhter’s Law: “Addressing can follow topology
or topology can follow addressing. Choose one.”
00
10
20
30
01
11
21
31
02
12
13
22
23
32
2
03
6
3
33
10
5
13
8
16
11
15
1
12
4
9
7
14
Name-dependent routing
Name-independent routing
Issue 2: state vs. stretch
We want small state!!
We want small stretch!!
routing
debate
• State: the routing table size describing the network topology
• Stretch:
path length found by the routing algorithm
optimal path length
≥1
More general trade-off
Triangle of trade-offs:
• Adaptation costs = convergence measures (e.g.
number of messages per topology change)
• Memory space = routing table size
• Stretch = path length inflation