Transcript NewSaharaMSR - BNRG - University of California, Berkeley

The SAHARA Project:
Composition and Cooperation
in the New Internet
Randy H. Katz, Anthony Joseph, Ion Stoica
Computer Science Division
Electrical Engineering and Computer Science Department
University of California, Berkeley
Berkeley, CA 94720-1776
Presentation Outline
•
•
•
•
Service Architecture Opportunity
SAHARA Project and Architecture
Routing as Service Composition
Summary and Conclusions
Presentation Outline
•
•
•
•
Service Architecture Opportunity
SAHARA Project and Architecture
Routing as Service Composition
Summary and Conclusions
The New Opportunity
• New things you can do inside the network
• Connecting end-points to “services” with processing
embedded in the network fabric
• Not protocols but “agents,” executing in places in
the network
• Location-aware, data format aware
• Controlled violation of layering necessary!
• Distributed architecture aware of network topology
• No single technical architecture likely to dominate:
think overlays, system of systems
Services in Converged Networks
Services in Converged Networks
Presentation Outline
•
•
•
•
Service Architecture Opportunity
SAHARA Project and Architecture
Routing as a Service Composition
Summary and Conclusions
The SAHARA Project
•
•
•
•
•
•
Service
Architecture for
Heterogeneous
Access,
Resources, and
Applications
Composition Scenario:
Universal In-box
– Message type (phone,
email, fax)
– Access network (data,
telephone, pager)
– Terminal device
(computer, phone,
pager, fax)
– User preferences &
rules
– Message translation &
storage
Separate end device and
network from end-to-end
communications service:
indirection via composition
of translators with access
SAHARA Focus
• New mechanisms, techniques for end-to-end services
w/ desirable, predictable, enforceable properties
spanning potentially distrusting service providers
– Tech architecture for service composition & inter-operation
across separate admin domains, supporting peering &
brokering, and diverse business, value-exchange, accesscontrol models
– Functional elements
•
•
•
•
•
•
Service discovery
Service-level agreements
Service composition under constraints
Redirection to a service instance
Performance measurement infrastructure
Constraints based on performance, access control,
accounting/billing/settlements
• Service modeling and verification
“The Network Effect”
• Creation and deployment of new services
– Achieving desirable end-to-end properties,
e.g., by controlling the end-to-end path
– Deploying computation and storage INSIDE the network
• BUT new networks are expensive; evolving existing
networks virtually impossible
– E.g., Cost of 3G licenses and networks
– “Even if I had $1 billion and set up 1000s of locations, I
could never in my network have a completely ubiquitous
footprint.”—Sky Dayton, founder of Boingo
– QoS: IntServ, DiffServ; New Function: Multicast, …
• Approaches:
– Composition, Overlays, Peering
– Cooperation, Brokering
Internet Connectivity and Processing
Cable
Modem
Premisesbased
Access
Networks
Core Networks
WLAN
Transit Net
WLAN
Operatorbased
Cell
Cell
Cell
Regional
LAN
Transit Net
Premisesbased
WLAN
LAN
Internet
Datacenter
NAP
Public
Peering
Data
Voice
Analog
Transit Net
H.323
RAS
H.323
PSTN
LAN
Private
Peering
DSLAM
Data
Voice
Wireline
Regional
Interconnected World:
Agile or Fragile?
• Baltimore Tunnel Fire, 18 July 2001
– “… The fire also damaged fiber optic cables, slowing Internet service
across the country, …”
– “… Keynote Systems … says the July 19 Internet slowdown was not
caused by the spreading of Code Red. Rather, a train wreck in a
Baltimore tunnel that knocked out a major UUNet cable caused it.”
– “PSINet, Verizon, WorldCom and AboveNet were some of the bigger
communications companies reporting service problems related to
‘peering,’ methods used by Internet service providers to hand traffic
off to others in the Web's infrastructure. Traffic slowdowns were
also seen in Seattle, Los Angeles and Atlanta, possibly resulting from
re-routing around the affected backbones.”
– “The fire severed two OC-192 links between Vienna, VA and New
York, NY as well as an OC-48 link from, D.C. to Chicago. … Metromedia
routed traffic around the fiber break, relying heavily on switching
centers in Chicago, Dallas, and D.C.”
Internet Routing Realities
• Provider-customer vs. peer-to-peer
• Relationships established by BGP protocol
• Charging based on traffic volumes
ISP A
Peering
Point
Hot Potato
Routing
ISP B
Peering
Point
Mobile Virtual Network Operator:
Composition and Cooperation
InterCall
one2one
Competition
one2one
1-to-1 Relationship
M-to-N Relationships
Peering
Policy-Based Routing
• Multi-homing
– Reliability of network connectivity
– Traffic discrimination
Primary
Transit
Network
Berkeley
Dorm
Campus
End Network
Traffic
Alternative
New Primary
Transit
Research
Transit
Fail-over
Network
Traffic
Peer
Peer
CalREN
Peer
Network
Network
Networks
Network
Overlays
Creating New Interdomain Services
• Deploy new services above the routing layer
– E.g., interdomain multicast management and peering
– E.g., alternative connectivity for performance, resilience
Isolated
Intra-cloud
service
Administrative
domain
Admin
domain
Admin
domain
Administrative
domain
Admin
domain
Traditional
unicast
peering
Steve McCanne
Wireless ISP Composition
VPN Operator, Client-Software
WISP Aggregator
Private Brand Net
Operator (MVNO)
Single Sign-on
Unified Billing
Billing, ECommerce
Authentication
Inter-site Mobility
SLN Aggregator
Single Location
Network Operator
Single Location(SLN)
Network Operator
Single Location
(SLN)
Network Operator Cooperative
(SLN)
Networking
Revenue
Sharing
Full Service
Network
Full Service
Operator
Network
Full Service
Premises-based
Operator
Network
Operator
Access
Layered Reference Model
for Service Composition
• Connectivity Plane
– End-to-end network with desirable properties composed
on top of commodity IP network
– Enhanced Links & Paths: QoS and protocol verification
within and between connectivity service providers
• Applications Plane
– Services strategically placed and actively managed within
the network topology
– Applications and Middleware Services: end-client
oriented vs. infrastructure oriented
Layered Reference Model for
Service Composition
Middleware Services
End-to-End Network
With Desirable Properties
Enhanced Paths
Enhanced Links
IP Network
Connectivity
Plane
Service
Composition
Applications Services
Application
Plane
End-User Applications
Presentation Outline
•
•
•
•
Service Architecture Opportunity
SAHARA Project and Architecture
Routing as Service Composition
Summary and Conclusions
Routing as a Composed Service
• Routing as a Reachability “Service”
– Implementing paths between composed service instances,
e.g., “links” within an overlay network
– Multi-provider environment, no centralized control
• Desirable Properties
– Trust: verify believability of routing advertisements
– Agility: converge quickly in response to global routing changes
to retain good reachability “performance” (e.g., latency)?
– Reliability: detect service composition path failures quickly
to enable fast recomposition to maintain reachability
– Scalability and Interoperability: Adapt protocols via processing
at “impedance” matching points between administrative domains
Characterizing the Internet Hierarchy
from Multiple Vantage Points
• Customer-Provider Relationships
– Customer pays provider for Internet access
– AS exports customer’s routes to all neighbors
– AS exports provider’s routes only to its customers
• Peer-to-Peer Relationships
– Peers exchange traffic between their customers
– Free of charge (assumption of even traffic load)
– AS exports a peer’s routes only to its customers
Sharad Agarwal. Lakshmi Subramanian, Jennifer Rexford
Knowing These Relationships
Matters!
• Useful for:
–
–
–
–
–
Placement of servers for content distribution
Selection of new peers or providers for an AS
Analyzing convergence properties of BGP
Installing route filters to protect against misconfiguration
Understanding basic structure of the Internet
–
–
–
–
Interdomain routing is not shortest-path routing
Some paths not allowed (e.g., transit through a peer)
Local preference of paths (e.g., prefer customer path)
Node degree does not define the Internet hierarchy
• Knowing the AS graph is Not Enough
• Need to Know Relationship between AS Pairs
Revealed Structure
April 2001
• Peer-peer relationships hard to infer
– Mislabeling peer-peer edge as
provider-customer does not change
valid path into invalid
– Heuristics to detect peer-peer edges
• Some AS pairs unusually related
– Siblings providing mutual transit
– Backup relationship for connectivity
under failure
– Misconfiguration of conventional
relationship
– Detect such cases by analyzing
“invalid” paths
20 AS’s
129 AS’s
897 AS’s
971 AS’s
• Access to large path set is hard
– Exploit BGP routing tables from
multiple vantage points
(10 public BGP tables)
8898 AS’s
11K ASs
24K edges
Policy Management for BGP
• Integrate BGP with a new Policy
Agent control plane
– Improved BGP convergence
through explicit fail over policies
– Constrained routing for
performance or trust reasons
– Traffic discrimination, low quality
vs. high quality connectivity or fair
use issues
– Load balancing outbound and
inbound flows for multi-homed ASs
– Sharad Agarwal’s Ph.D. thesis,
currently interning at Sprint ATL
Agility in Response to Route Changes:
Internet Converges Slowly
• Convergence Times [Labovitz et al.]
– Theory: O(n!) (n: number of ASes)
– Practice: linear with the longest backup path length
– Measurement: up to 15 minutes
• Why so slow?
– BGP protocol effects: path exploration
– Route flap damping!?
• Delay convergence of relatively stable routes
• Unexpected interaction between flap damping and convergence
Morley Mao, Ramesh Govindan, George Varghese
How Does Flap Damping Work?
RFC2439:
•
Exponentially decayed
Suppress threshold
•
•
For each peer, per destination,
keep penalty value, increase it
for each flap
Flap is a route change
Penalty decays exponentially
P(t ' )  P(t )e  (t 't )
•
Parameters:
– Fixed: Penalty increment
– Configurable: half-life,
suppress-, reusethreshold, max suppressed
time
Reuse threshold
Time
A Better Way:
Selective Route Flap Damping
• Flaps happen because of certain topologies among
routers, causing triggered announcements and
withdrawals—these are not toy scenarios
• Approach: ignore flap sequences indicating path
exploration—these are likely to trigger more changes
in near future
• In essence, we redefine what constitutes a flap:
– From “any route change is considered a flap” to “must alter
direction of route preference value change, relative to flaps”
– Flaps due to withdrawal: increasing ASPath lengths, route
value keeps decreasing
• Morley Mao Ph.D. dissertation, currently interning at
AT&T Labs
• Stability achieved through flap damping [RFC2439]
• BUT unexpected:flap damping delays
convergence!
Topology:
clique of
routers

Selective flap damping
–
–
Duplicate suppression: ignore flaps caused
by transient convergence instability
Eliminates undesired interaction without
sacrificing stability
Trusting the Routing Infrastructure
BGP Route Verification
• BGP protocol vulnerable
– Single misconfigured router can cause long outages
– Malicious routers can cause larger damage
• Pretend to be a genuine end-host!!!
• Misroute or sniff on traffic
• Potential collusion with other malicious nodes?
• Verify BGP routes without PKI-based authentication?
– Secure-BGP, tier-1 ISP proposal, yet to be deployed
• Assumed an Internet wide PKI with ICANN as root!
Approach:
Detection and Containment
• Misconfiguration affects reachability
– Roughly 6% of misconfigurations cause reachability
problems [Mahajan02]
– “Passive” TCP-probing: modified nodes watch TCP traffic
to detect reachability problems
• No modifications to BGP, incrementally deployable, but
ineffective for detecting malicious hosts
• Contain malicious nodes
– Without authentication, can’t distinguish between
genuine and malicious hosts
• Two BGP enhancements--hash chains, loop-testing
• Avoid routes through nodes (misconfigured/malicious)
affecting routes to multiple destinations
• Lakshmi Subramanian Ph.D. Dissertation
Overlay Approach for Achieving
Desirable Performance: OverQoS
• Embed QoS functionality in Internet via overlays
– Overlay nodes implement QoS functions
– No support needed from IP routers
• Virtual Links
– Underlying path between two OverQoS routers
– Characterized by three time-varying parameters
• Available bandwidth, b(t), using fairness criterion
(e.g., N TCP flows) or by explicit SLA with ISP
• Loss rate, p(t)
• Delay, d(t)
• Challenges
– Nodes not connected to congested points, have no control
on cross-traffic, cannot avoid losses (reducing sending
rate doesn’t help!)
Lakshmi Subramanian, Hari Balakrishnan, Ion Stoica
Architecture
AS
AS
IP
IP
IP
IP
AS
AS
Virtual links
AS
AS
AS
OverQoS routers
Controlled-Loss Virtual Link (CLVL)
• Control losses if you can’t avoid them
–
–
–
Aggregate a set of flows along a virtual link in a bundle
Protect the bundle’s traffic against losses
Redistribute b/w and loss across flows in a bundle at entry node
–
–
Statistical bound on loss rate, q (<= p; typically << p)
Capacity, c(t), possibly time-varying
–
–
Implicit: b is bundle’s bandwidth; c is some part of b
Explicit: via provisioning in underlying Internet path
• Two parameters:
• Can prove: if offered load < c(t), then loss rate < q
• c provided in two ways:
Flow 1
Flow 2
Buffer mgmt & c(t), q
Scheduling &
Traffic regulator
Coder
Flow n
OverQos Node
CLVL
control plane
b(t), p(t)
Decoder
Text
to
audio
Text
to
audio
Text Source
Reliability in Wide-Area
Service Composition
• Wide-area/multi-provider composition
• Fast recovery improves service availability
Text Source
• Detect & recover from
failures via service replicas
• Aggressive heartbeat msgs:
– Quick detection (~2 s)
– Scalable messaging for
recovery (1000s of clients)
• Load balancing + slack
service provisioning to handle
fast path fall-over
• > 15 s outage
• BGP recovery much worse!
[Labovitz’00]
• End-to-end recovery in 3.6 s:
2 s detect, ~600 ms signaling,
~1 s state restoration
Wide-area Experiment: UCB, Berk. (Cable), SF (DSL),
Stan., CMU, UCSD, UNSW (Aus), TU-Berlin (Germany)
Bhasker Raman
Scalability and Interoperability:
Multicast Broadcast Federation
Broadcast
Domains
• Compose non-interoperable
m/c domains to provide
e2e m/c service
– IP and App-layer protocols
• Overlays of Broadcast
Gateways (BGs)
– Peering between domains
– Internal m/c inside domain
– Clustered gateways for
scalability across domains
– Independent data flows and
control flow
Source
CDN
IP Mul
SSM
Clients
BG
Data
Peering
• Implementation :
– Linux/C++ event-driven program
– Customizable interface to local
multicast (~700 lines)
– 1 Gbps BG thruput with 6 nodes
– 2500 sessions with 6 nodes
Mukund Seshadri, Yatin Chawathe
Presentation Outline
•
•
•
•
Service Architecture Opportunity
SAHARA Project and Architecture
Routing as Service Composition
Summary and Conclusions
SAHARA Project
• Evolve Internet architecture to better support multinetwork/multi-service provider model
– Dynamic environment, large numbers of service providers &
service instances
– Achieve desirable properties across multiple, potentially
distrusting (Internet) service providers
– Exploit PlanetLab infrastructure to construct wide-area
prototype
• Routing as a composed service
–
–
–
–
–
–
Trust: BGP Verification/Detection + Containment
Agility: Fast Convergence
Reliability: Keep-Alive Messaging
Scalability: Clustered Gateways
Interoperability: M/C Protocol Transformation
New Policy/Control Planes
New Service Architecture
Integrated Communications and Processing
• Increasing diversity of interconnected devices
• Increasing importance of “services” to mitigate
diversity/provide new functionality and customization
• Enabled by processing embedded in the network
interconnect, locally and globally
– “Active networking” is real
• Global services via managed composition
– Role of multiple service providers and administrative domains
– Separation of services from connectivity via overlays
– No single operator deploys the global service
The SAHARA
Project:
Composition and
Cooperation
in the New
Internet
Randy H. Katz
Thank You!