Transcript Value Flows: Inter-domain Routing Over Contract Links

Value Flows: Inter-domain Routing
Over Contract Links
Hasan T Karaoglu,
Murat Yuksel
University of Nevada, Reno
FutureNet III, Miami
December 2010
Motivation
• Current Architectural Problems of the Internet
– Economics is not reflected inherently on routing
• Keeping up with “Value” and “Network Economics”
– Commoditized IP, wholesale transit
– “Success of bundling, higher value services“, Labovitz et. al.
– Transition to a content-oriented Internet, on-demand
infrastructure, applications, services with Cloud
– Strain on Routing Functions and Dynamics
• Traffic Engineering, Rich Policy Requirements
– e.g., Stringent bandwidth and reliability requirements with
VoD, VoIP, IPTV and mobility
2
Motivation
• Structural Inflexibilities
– Limited User Choice:
• Value Expression
– Rigid SLA Mechanism
• Long Contract Terms,
• Establishment Process
– Prefix-based Point-to-Anywhere
• e.g., ISP as a “node”.
Recognizing the “Tussle”:
Mechanisms for establishing Negotiation Base
3
Outline
•
•
•
•
•
•
•
•
Motivation
Challenge
Our Solution: Contract Switching Architecture
Problem Definition
Link State Contract Routing
Implementation
Evaluation
Conclusion
4
Contract Switching
• Defining “contracts” as building blocks.
– Single domain, edge-to-edge, service
advertisements
• Recognizing the “value” in traffic
– Allow user to express its choice beyond access ISP
– Value expression over contracts
• Routing as a service
– Compose customized paths for value flows by
stitching single-domain contracts.
5
Value Flows
• Flow Aggregation
– Manage traffic as flows
at core, aggregation
– Keep packet at edge for
innovation
• Recognizing “value”
– Source-routing
– Flow definition
– Service customization
6
Edge-to-Edge Service
• An ISP is abstracted as a set of
“contract links”
• Contract link: an advertisable
contract
– between peering/edge points i and
j of an ISP
– with flexibility of advertising
different prices and capabilities for
edge-to-edge (g2g) intra-domain
paths
Contract Abstraction
 Contract components
 performance component, e.g., capacity
 financial component, e.g., price
 time component, e.g., term
8
Problem Definition
• Between Packet vs. Circuit Switching
– Flow State, Dedicated Resources
– How quickly should one switch?
• Contract Term, Time Scale
• Routing Characteristics
– Convergence on multi-metrics (with also price?)
– Reachability challenge?
• Transition path to Contract Switching?
9
Link State Contract Routing
• Link State “Like”
– State?
• Not actual conditions, but service definition
– Source-routing
• Reservation Signaling on Contract Links
– Route Dissemination
• Synchronization, Policy Filters
– Route Calculation
• Multiple-metric, Diverse Objectives
• Widest-Cheapest Path
10
Link State Contract Routing
Most costefficient route
2
User X
1
ISP
A
Link
QoS
Term
Offered
After
Price
($/term)
A
1-2
10Mb/s
2hrs
1hr
$10
A
1-3
40Mb/s
5hrs
15mins
$80
B
2-4
100Mb/s
3hrs
2hrs
$110
C
3-5
20Mb/s
1hr
30mins
$8
C
4-5
60Mb/s
1day
2hrs
$250
ISP
B
4
3
Max QoS route
Owner
ISP
ISP
C
5
11
Link State Contract Routing
12
Link State Contract Routing
Network Elements
• Contract Routers
• Network Coordinators
Messaging
• Contract Links
• Transit, Sink
• Reservation Messages
13
Implementation
• “Overlay” Approach
– BGP and OSPF implementation of SSFNet
– Packet level simulation
– RSVP “like” signaling protocol
• Strategy: Economic Model, Routing Objectives
– Access provider and transit ISP
– Non-linear, congestion aware pricing
– Congestion aware service provisioning
14
Evaluation
• Topology
– Tradeoff between scale and being realistic
– Inter-domain Level:
• BRITE: 15 ISPs, BA method
– Intra-domain Topology:
• Embedded 6 Rocketfuel Maps
• BFS Based Bandwidth Estimation: Higher Core Capacity
• Traffic Matrix
– Gravity Model: Node Locations, City Populations
15
Network Model
• Realistic Simulation requires
– Realistic ISP Topology
•
•
•
•
•
Adjacency Matrix (Given by Rocketfuel Data)
Link Delays & Weights (Given by Rocketfuel Data)
Link Capacities (We have to model)
Edge and Backbone Router Classification (We have to model)
Routing Matrix (Path calculated by Shortest Path Algorithms,
as OSPF does)
– Realistic Traffic Model
• Traffic Matrix Estimation(We have to model)
Network Model
BFS Based Link Capacity Estimation
1) Select Most Connected Router
2) Initiate a BFS
3) Assign higher capacity to links
closer to center
•DC. BFS Dist =
2
•Atlanta BFS Dist = 3
1
2
3
4
5
6
7
40
gbps
10
gbps
2.5
gbps
640
mbps
155
mbps
45
mbps
10
mbps
Network Model
Gravity Model
Traffic ~ Pop. 1 X Pop. 2
Seattle 6K
2X
Chicago 3M
24X
NY 8M
Gravity Model Based Traffic Estimation
1) Determine Degree and BFS Distance Thresholds
2) Classify Edge / Backbone Routers
3) Associate Area Population with Edge Routers
4) Use Gravity Model to estimate traffic size
Evaluation
• QoS
Single-path vs. Multi-path Routing
Increasing stability with longer timescales
19
Evaluation
• Reachability
Decreasing reachability with longer lease terms
QoS vs Reachability tradeoff
20
Evaluation
• Price Convergence
Prices stabilization achieved at different paces
21
Evaluation
• Path Stretch
Path Stretch improves with longer contract term
22
Evaluation
• Messaging Cost
Messaging cost improves with longer contract terms
23
Conclusion
• Contract Abstraction and Edge-to-Edge Design
• Initial model to analyze
– Contract Routing Behavior
– Contract Term Impact on Routing Performance
and Network Dynamics
– Overlay Implementation and Transition Path
• Future Work
– Developing methods to extend scale
– Economic models and Game Theory
24
Questions?
Thank You
25
Net Neutrality
• Incremental Deployment Scenario:
– Initial Phase: Complimentary market to packet
switched Internet (i.e., contracts operating on leftover bandwidth capacities)
– Second Phase: Emergence of pure CS
infrastructure owners and service providers
• Innovation driven at both edge and backbone
• Analogy: co-existence of express and regular
mail
26
End-to-end Connectivity
• MPLS labels / GRE / IP-to-IP tunnels for edgeto-edge
– Minimal configuration burden on intra-domain
• Label Sharing / VPN / Tunneling at edge
routers
• Establishing these states at edge routers and
concatenation of edge-to-edge links to an
end-to-end path through reservation
27
Literature
• Negotiation-based Routing
• NIRA: User choice, Hierarchy, Addressing,
Multi-hop negotiation
• Pathlet Routing: Economics?, Routing Protocol
Emulation on Pathlets
• MIRO: Multi-path Routing
• Path Splicing: Focus on reliability?
• IPSphere, OpenFlow, Routing As a Service
28