Transcript Communication - Princeton University

Building a Strong Foundation
for a Future Internet
Jennifer Rexford
Princeton University
http://www.cs.princeton.edu/~jrex
The Internet: A Remarkable Story
• Tremendous success
– A research experiment that truly
escaped from the lab
• The brilliance of under-specifying
– Best-effort packet-delivery service
– Key functionality at programmable end hosts
• Enabled massive growth and innovation
– Ease of adding new services (Web, P2P, VoIP, …)
– Ease of adding hosts and links, and new technologies
2
Rethinking the Network Architecture
• But, the Internet is showing signs of age
– Security, mobility, availability, manageability, …
• Challenges rooted in early design decisions
– Weak notions of identity, tying address to location, …
– Not a simple matter of redesigning a single protocol
• Revisiting the definition and placement of function
– What are the types of nodes in the system?
– What are their powers and limitations?
– What information do they exchange?
3
Clean-Slate Network Architecture
• Clean-slate architecture
– Without constraints of today’s artifacts
– To have a stronger intellectual foundation
– And move beyond the incremental fixes
• Still, some constraints inevitably remain
– Ignore today’s artifacts, but not necessarily all reality
• Such as…
– Resource limitations (CPU, memory, bandwidth)
– Time delays between nodes
– Independent economic entities
– Malicious parties
– The need to evolve over time
4
A Big Research Challenge
Evolvable Protocols
(under-specified, programmable)
?
Decentralized Control
X-ities
(autonomous parties, with
different economic objectives)
(stability, scalability, reliability,
security, managability, …)
Can we have all three? Under what conditions?
5
A Real Need for a Theory of Networks
• Formal definitions of network architecture
– Can the theory community do for network architecture
what it did for, e.g., cryptography and machine learning?
• Programmabillity
– What are good programming models that strike the
right balance been flexibility and restraint?
• Incentives
– How much should we rely on economic incentives to
ensure key system properties?
• System properties
– What are the fundamental trade-offs and bounds?
6
Example: Internet Routing
• Seemingly a simple matter
– Computing paths on graphs
• Many, many design goals
– Global connectivity
– Flexible local policies
– Fast recovery from changes
– Good end-to-end paths
– Low protocol overhead
– Security, scalability, …
– <your wish list here>
• Perhaps we cannot satisfy all of these goals
– No matter how hard we try…
7
Four Example Problems in Routing
• Policy-based interdomain routing
– Programmable routing policies in each network
– While ensuring global stability, efficiency, …
– #1: Can economic incentives ensure global stability?
– #2: How should a distributed network realize its policy?
• End-to-end traffic management
– Adapting the flow of traffic over each path
– While ensuring good aggregate performance
– #3: What should hosts, routers, and operators do?
– #4: How to support diverse application requirements?
Getting a distributed set of nodes to do the right thing.
8
Policy-Based Interdomain Routing
+ $$$ = ???
What is an Internet?
• A “network of networks”
– Networks run by different institutions
• Autonomous System (AS)
– Collection of routers run by a single institution
– With a clearly defined routing policy
• ASes have different goals
– Different views of which paths are good
• Interdomain routing is what reconciles those views
– To compute end-to-end paths through the Internet
Wonderful problem setting for game theory and mechanism design 10
Autonomous Systems (ASes)
Path: 6, 5, 4, 3, 2, 1
4
3
5
2
7
1
6
Web server
Client
Around 30,000 ASes today…
11
Border Gateway Protocol (BGP)
• ASes exchange reachability information
–Destination: block of IP addresses
–AS path: sequence of ASes along the path
• Policies “programmed” by network operators
–Path selection: which path to use?
–Path export: which neighbors to tell?
“I can reach d via AS 1”
“I can reach d”
2
1
data traffic
d
3
data traffic
12
Stable Paths Problem (SPP) Model
• Model of routing policy
– Each AS has a ranking of the permissible paths
• Model of path selection
– Pick the highest-ranked path consistent with neighbors
12d
1d
1
• Flexibility is not free
2
23d
2d
3
31d
3d
d
– Global system converges slowly, or not at all
– Depending on the way the ASes rank their paths
13
Ways to Achieve Global Stability
• Detect conflicting rankings of paths?
– Computationally intractable (NP-hard)
– Requires global coordination
• Restrict the policy programming languages?
– In what way? How to require this globally?
– What if the world should change, and the protocol can’t?
• Rely on economic incentives?
– Policies typically driven by business relationships
– E.g., customer-provider and peer-peer relationships
– Sufficient conditions to guarantee unique, stable solution
14
Bilateral Business Relationships
• Provider-Customer
– Customer pays provider for access to the Internet
• Peer-Peer
– Peers carry traffic between their respective customers
Valid paths: “6
“1 4
23
d”d”
and
and
“7“8
d”5 d”
Invalid
Invalidpaths:
path: “5
“6 85 d”
d” and “1 4 3 d”
1
4
3
2
d
5
6
Provider-Customer
Peer-Peer
7
8
15
Act Locally, Prove Globally
• Route export
– Do not export routes learned from a peer or provider
– … to another peer or provider
• Route selection
– Prefer routes through customers
– … over routes through peers and providers
• Global topology
– Provider-customer relationship graph is acyclic
– E.g., my customer’s customer is not my provider
• Guaranteed to converge to unique, stable solution
16
Rough Sketch of the Proof
• Two phases
– Walking up the customer-provider hierarchy
– Walking down the provider-customer hierarchy
1
4
3
2
d
5
6
Provider-Customer
Peer-Peer
7
8
17
Trade-offs Between Assumptions
• Three kinds of assumptions
– Route export, route selection, and global topology
• Trade-offs
– Relax one assumption, need to tighten the other two
• Are these assumptions reasonable?
– Could business practices change over time?
– What if nodes are dishonest about their choices?
• What if the protocol changes
– What if the protocol allows multiple paths?
18
An Incomplete Understanding…
• Desirable global properties
– Convergence to a unique route assignment
– Fast convergence after topology changes
– Honest announcement of AS paths
– Forwarding data packets along chosen paths
• And how they relate to
– Topology, policies, path verification, revenue models, …
• With basic questions about economic incentives
– When are they enough? What else do we need?
• Where do the economic issues really belong?
– In the protocol? In the policies? In routes themselves?
19
An AS is Really a Network
• How should the nodes inside an AS behave?
– To correctly realize the AS’s routing policy
– To satisfy the expectations of
neighboring ASes
– To minimize protocol
overhead within the AS
• Different problem than
interdomain routing
– Not about reconciling
(possibly conflicting) policies
– But instead about correctly
realizing a single policy
20
The Route Assignment Problem
{ r1
r2
r3
… rn } = R
n
rn
1
2
Route Assignment
(based on policy)
data
traffic
3
e1
…
e2
en
from R
…
e3=rn
from R
21
An Incomplete Understanding…
• How to define and model an AS
– To design and analyze interdomain routing
– … without regard to the intra-AS details
• How to propagate routing information within an AS
– So the routers can realize the policy “correctly”
– … without introducing excessive overhead
• What are the overhead-flexibility trade-offs?
– How much information must the routers exchange
– … and how does it depend on the programming model
• How to program the policies
– Intuitive programming language, rather than path ranking
– … without sacrificing too much flexibility
22
End-to-End Traffic Management
Traffic Management Today
• How much traffic should traverse each path?
Operator:
Traffic Engineering
End hosts:
Congestion Control
Routers:
Routing Protocols
24
Models and Algorithms for Each Part
• End hosts: congestion control
–Maximizing aggregate utility over all users
–Additive increase, multiplicative decrease
• Routers: routing protocols
–Minimizing path cost as sum of link weights
–Bellman-Ford and Dijkstra’s algorithms
• Operators: traffic engineering
–Minimizing load on the network links
–Local-search algorithms for tuning link weights
But, is the whole more than the sum of its parts?
25
Shortcoming of Today’s Architecture
• Ignores protocol interactions
–Congestion control assumes routing is fixed
–Traffic engineering assumes traffic is inelastic
• Inefficiency of traffic engineering
–Tuning link weights in shortest-path routing
–Cannot achieve optimal flow, and is NP-hard
–… and is typically performed on long timescale
• Only limited use of multiple paths
–Missed opportunity for better performance
What would a clean-slate redesign look like?
26
Distributed Traffic Management Problem
• Should have a clearly-stated problem
– Objectives: maximizing aggregate user utility
– Constraints: link load staying below capacity
• And solutions with well-understood properties
– Optimality, convergence, reasonable overhead, …
• Distributed load-balancing algorithms
s
s
s
Edge nodes:
Update path rates z
Rate limit incoming traffic
Routers:
Set up multiple paths
Measure link load
Update link prices 27
s
An Incomplete Understanding…
• Promising initial results
– Using optimization theory, game theory, control theory…
• Simple tuning of the system
– Algorithms that are robust across a range of settings?
– Self-tuning load-balancing algorithms?
• Trade-offs in the number of paths
– How many paths are really necessary?
– How should these paths be computed?
• Implicit vs. explicit feedback
– Most solutions require feedback from network links
– Can edge nodes adapt based on path-level metrics?
– Robustness to adversaries trying to bias measurements?
28
Supporting Multiple Classes of Traffic
vs.
file
Different Strokes for Different Folks
• Applications have different requirements
– High throughput: bulk file transfers
– Low delay/jitter: VoIP and gaming
• Could design protocols for each traffic class
– Using application-specific objective functions
• But, how should these applications co-exist?
– Multiple customized traffic-management protocols
– On a shared underlying network
– To maximize the aggregate utility of the users
30
Virtualization to the Rescue
• Multiple customized architectures in parallel
– Multiple virtual nodes on a single physical node
– Isolation of resources, like CPU and bandwidth
– Programmability for customizing each “virtual network”
31
An Incomplete Understanding
• How important are customized architectures?
– Quantifying the inefficiencies of “one size fits all”
– Understanding gains and overheads of customization
• How to balance isolation and efficiency?
– Allowing multiple architectures to run in parallel
– Without requiring static resource partitioning
• How to support other application requirements?
– Security/privacy, scalability trade-offs, …
– With appropriate support in the underlying substrate
• What kind of programming model on the nodes?
– To enable creation of new networked services
– Without compromising efficiency, security, …
32
Virtualization for Economic Refactoring
Today’s Internet
Competing ISPs
with different goals
must coordinate
Virtualized Internet
Single service
provider controls
end-to-end path
• Infrastructure providers: Maintain routers, links, data
centers, and other physical infrastructure
• Service providers: Offer end-to-end services to users
Economics play out vertically on a coarser timescale.
33
Conclusions
• These are just a few examples
– In the context of Internet routing
• Meant to illustrate a larger question
– Programmability, incentives, and global properties
• And importance of theoretical disciplines
– In putting network architecture on a sound foundation
• Great opportunities for interdisciplinary research
– Grappling with problem formulations and solutions
• And for significant practical impact
– Adding clarity to our understanding of today’s Internet
– And leading to a future Internet worthy of society’s trust
34