Transcript Multipath Protocol for Delay-Sensitive Traffic Jennifer Rexford Princeton University

Multipath Protocol for
Delay-Sensitive Traffic
Jennifer Rexford
Princeton University
Joint work with Umar Javed, Martin Suchara, and Jiayue He
http://www.cs.princeton.edu/~jrex/papers/comsnets09.pdf
Clean-Slate Network Architecture
 Network architecture
 More than designing a single protocol
 Definition and placement of function
 Clean-slate design
 Without the constraints of today’s artifacts
 To have a stronger intellectual foundation
 And move beyond the incremental fixes
 But, how do we do clean-slate design?
Protocols as Distributed Optimizers
 Example: TCP congestion control
 Additive increase, multiplicative decrease
 Implicitly maximizes aggregate utility
 TCP variants have different utility functions
 Optimization for “forward” engineering
 Start with a central optimization problem
 Decompose to divide the computation
 … among the sources and the links
Research by Frank Kelly, Steven Low, Mung Chiang, and others
Our Focus: Delay-Sensitive Traffic
 Interactive applications
 Voice over IP (VoIP)
 Online gaming
 IP television
 Path-selection goals
 Paths with low propagation delay
 … as long as paths are not overloaded
For now, assume the network carries only delay-sensitive traffic
Strawman: Min Propagation Delay
Operator:
Sets weights to
propagation delay
3
2
1
4
3
2
2
2
Routers:
Link-state routing
But links may become congested, causing packet loss and delay…
Our Goal: Adaptive Load Balancing
 Division of functionality
 Links: feedback on network conditions
 Edge routers: balance load over paths
Distributed protocol that automatically minimizes delay
Multiple Paths With Flexible Splitting
 Multiple paths between edge nodes
 Paths with low propagation delay
 Flexible traffic-splitting ratio
 Traffic rate xi for src-dest pair i
 Traffic rate zij over path j
z1
x1 = z11 + z12 + z13
1
z21
z31
Objective: Minimize Average Delay
 Minimize average delay
 End-to-end delay on each path
 Weighted by the traffic on the path
 Delay for link l
 Propagation delay pl
 Congestion penalty f(load on link l)
ilink
i(p+
if()
Delay
l:i z
p
Summed:
Weighted:
∑for
∑
z
∑
R
R
f())
i j l lj lj l +
lj (p
l+
f())
Constraints
 Carry the offered load for each source
 ∑j zij = xi
 Avoid overloading each link
 ∑i ∑j zij Rilj ≤ cl
 Carry non-negative traffic on each path
i
0 ≤ z j
Optimization Decomposition
 Deriving source and link algorithms
 Prices: penalties for violating a constraint
 Path rates: updates driven by prices
 Example: TCP congestion control
 Link prices: packet loss or delay
 Source rates: AIMD based on prices
 Our problem is more complicated
 More complex objective, multiple paths
Example Decomposition: Link Capacity
 Capacity constraint
link load ≤ cl
 Subgradient feedback price update:
l l(t+1) = [ll(t) + stepsize*(link load – cl )]+
 Stepsize controls the granularity of reaction
 Link computes price l as feedback to sources
Source does similar update for “carry all offered load” constraint.
Path Rate Updates
 Each source i does a local optimization
 To update the path rates zij
 Based on
 The “prices” of violating constraints
 … and the objective function
 Closed-form expression
 With piecewise-linear queuing function f()
 See the paper for the exact equation
Derived by taking the Lagrangian and applying KKT conditions.
Distributed Multipath Protocol
Operator: Select function f
Tune step sizes
Edge node:
Update path rates z
Split traffic over paths
Routers:
Set up multiple paths
Measure link load
Update link prices
Theoretical Results
 Optimality and stability
 Provably optimal
 Provably converges for diminishing step sizes
 Practical limitations
 Must have well-chosen step sizes
 … to achieve fast convergence
 Matlab experiments to sweep parameters
 Good heuristics for setting (constant) step sizes
Converting to Packet-Level Protocol
 Packets rather than fluid
 Links compute load over a time interval
 Counting the sizes of the packets
 Feedback delay of round-trip time
 Multiple paths have different RTTs
 Path rate updates once per max of RTTs
 Implemented in ns-2 simulator
 For more realistic evaluation
Comparison With Shortest-Path Routing
 Shortest-path routing
 Link weights equal propagation delay
 Under low load
 The two protocols behave the same way
 Under higher load
 Our protocol gradually shifts traffic
 … to longer paths to avoid overload
 … while keeping end-to-end delay small
Convergence Under Dynamic Traffic
Multiple Classes of Traffic
 Satisfying multiple traffic classes
 Delay-sensitive: VoIP and gaming
 Throughput-sensitive: file transfers
 Running separate virtual networks
 Customized protocol for each traffic class
 Dynamic update to bandwidth shares
 Provably maximizes aggregate performance
 Derived using optimization theory
http://www.cs.princeton.edu/~jrex/papers/davinci.pdf
Conclusions
 Delay-sensitive applications
 VoIP, online gaming, IPTV…
 Customized routing protocol
 Load balancing over multiple paths
 Minimizing end-to-end delay
 Optimization decomposition
 Rigorous way to design new protocols
 With provable optimality and stability
 Ongoing work: network virtualization
Backup Slides
Protocol Dynamics
 Good heuristics for setting step size
 Converges quickly under range of settings
 Relatively fast convergence
 Small tens of seconds in worst case
 Better under more realistic settings
 Quick response to changes in load
 Fast adaptation to new traffic demands