Transcript Towards Wireless Overlay Network Architectures

The Post-PC Era:
It’s About The Services
Randy H. Katz
Computer Science Division
Electrical Engineering and Computer Science Department
University of California, Berkeley
Berkeley, CA 94720-1776
1
Presentation Outline
•
•
•
•
•
Heterogeneity in Devices and Networks
A New Service Architecture: SAHARA
Reachability as a Service
New Directions
Summary and Conclusions
2
Presentation Outline
•
•
•
•
•
Heterogeneity in Devices and Networks
A New Service Architecture: SAHARA
Reachability as a Service
New Directions
Summary and Conclusions
3
Shape of Things Today:
Diverse Appliances
and Devices
The Old Days
Game Consoles
Personal Digital Assistants
Digital VCRs
Communicators
Smart Telephones
E-Toys
All will demand broadband
Internet connectivity
… and 10BaseT won’t be sufficient
4
Ever More Sophisticated
Mobile Phones
Nokia
Nokia 7600
7650
• Graphical UI/Joystick control
• Voice dialing, voice recognition,
voice recorder
• Integrated digital camera w/
640 x 480 res image capture
• IR + Bluetooth + Phone2Phone +
Phone2PC
• Java-support for 3rd party apps
• WAP + High-speed data over
GSM + HSCSD + GPRS
• But often you need to compute!
Screen. Keyboard. Storage
5
Promise: Ubiquitous Connectivity
Low-tier
High-tier
Local Area
Wide Area
High Mobility
Low Mobility
• Seamless data mobility among local and widearea wireless networks via Mobile IP handoff
– Two orthogonal technologies:
» High speed data over cellular for high mobility,
wide-area coverage
» Even higher speed data over WLAN hot spots for
low mobility, local area coverage
6
Network Services: Communications
7
Network Services: Access
8
Best Implementation Method:
the Internet Programming Model
• Service composition across the network
– Network-aware Distributed System architecture
• Bottlenecks near edge, not core
– Service deployment points close to where used
– Service implementation topology-aware
• Enabled by:
– Computing embedded in communications fabric:
distributed, wide-area, topology-aware
– Emerging class of programmable network elements
– Per session characterization, processing,
prioritization, monitoring, management, billing
9
Internet Connectivity and Processing
Cable
Modem
Access
Networks
Transit Net
Premisesbased
WLAN
WLAN
WLAN
Hot Spots
Operatorbased
Cell
Cell
Cell
Regional
Premisesbased
PNE
Core Networks
LAN
LAN
PNE
LAN
Private
Peering
Transit Net
PNE
Internet
Datacenter
NAP
Public
Peering
Data
PNE
Voice
Analog
Transit Net
H.323
RAS
H.323
PSTN
Data
Voice
DSLAM
PNE
Wireline
Regional
10
Composed Applications:
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
11
Challenge: Single Operator vs.
“Virtual” Composed Operator
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
12
Challenge: Multiple “Operators”
Coordination Issues
• Top-Down vs. Bottom-Up Network Deployment
– Operator vs. aggregator/virtual operator models
– Neighborhood cooperative mesh networks
• Security
–
–
–
–
Blurring of distinction between public & private networks: rogue APs
Interoperation among service/access providers
End-to-end considerations in untrusted infrastructure
Authorization and billing for multi-party services
• Resource Management
– Unlicensed but ignore coordination at the cost of performance
– Radio resource planning and allocation
• Service Creation and Personalization Platform
– Intelligent edge services: service and policy management, user
mobility and profiling, charging and billing
– Deployments enabled by edge-network programmable network
elements
13
Challenge: Agile or Fragile
Networking?
• 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.”
14
Evolution of Internet
• Diversity of devices and access networks
– Wireless overlays provide continuum of connectivity
– Increasing importance of “services” to mitigate
diversity/provide new functionality and customization
– Global services via managed composition
– Enabled by processing embedded in the network interconnect,
locally and globally
• Multiple service providers/admin domains
– No single operator deploys the global service
– But can a reliable service be deployed by multiple,
uncoordinated providers?
• Overcoming the reliability bottlenecks
15
Presentation Outline
•
•
•
•
•
Heterogeneity in Devices and Networks
A New Service Architecture: SAHARA
Reachability as a Service
New Directions
Summary and Conclusions
16
The SAHARA Project
•
•
•
•
•
•
Service
Architecture for
Heterogeneous
Access,
Resources, and
Applications
17
SAHARA Goals
• New mechanisms, techniques for end-to-end
services w/ desirable, predictable,
enforceable properties spanning potentially
distrusting service providers
• Architecture for service composition and
inter-operation across separate administrative
domains, supporting peering and brokering, and
diverse business, value-exchange, accesscontrol models
18
Exploits the New Opportunities
• New things you can do inside the network
• Connecting end-points to “services” with processing
embedded in the network fabric
• “agents” not protocols, executing inside 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
19
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
Administrative
domain
Planet-Lab
domain
Admin
domain
Admin
domain
Admin
domain
Traditional
unicast
peering
20
Layered Reference Model for
Service Composition
Middleware Services
End-to-End Network
With Desirable Properties
Enhanced Paths
(Inter-domain)
Enhanced Links
(Intra-domain)
IP Network
Connectivity
Plane
Service
Composition
Applications Services
Application
Plane
End-User Applications
Overlay
Network
“Links”
21
Presentation Outline
•
•
•
•
•
Heterogeneity in Devices and Networks
A New Service Architecture: SAHARA
Reachability as a Service
New Directions
Summary and Conclusions
22
Routing as a Composed Service
• Composable Interdomain Routing: BGP
– Complex policy interactions yield non-optimal routes
– Slow convergence to routing changes render parts of the IP address
space unreachable for tens of minutes at a time
– Vulnerabilities to malicious attacks and unintentional mistakes
• 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 Enhanced Properties
– Performance: controlled loss and bandwidth guarantees (OverQoS)
– Reliability: detect reachability failure, faster convergence
– Security: verify believability of routing advertisements
23
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
• Challenges
– Nodes not connected to congested points
– Have no control over cross-traffic
– Cannot avoid losses (reducing sending rate doesn’t help!)
• Why Overlays?
– Previous QoS architectures not deployed globally
– Overlay-model empowers third-party providers to provide some
form of QoS
Lakshmi Subramanian, Hari Balakrishnan, Ion Stoica
24
OverQoS Method
• Step 1: Aggregate Loss and Bandwidth Control
Entry
Node
N-TCP pipe
Overlay Traffic
Redundant Traffic
Exit
Node
• Step 2: Distribute b/w and loss among flows
Flow 1
Flow 2
Scheduler
Rate Ctrl
Lakshmi Subramanian, Hari Balakrishnan, Ion Stoica
25
OverQoS Method
• Step 3: Provide QoS guarantees (b/w,loss) to a
flow “bundle” by “stitching” guarantees on overlay
links
Overlay
Node
Overlay
Node
Flow 2
Overlay
Node
Flow 1
Flow 3
• Step 4: Perform QoS-routing of multiple flows
with different requirements on overlay network
• Used successfully to support Counterstrike game
Lakshmi Subramanian, Hari Balakrishnan, Ion Stoica
26
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
27
Flap Damping (RFC2439)
• Suppress routes that
change too frequently
Exponentially decayed
Suppress threshold
– For each peer, per
destination, keep penalty
value, increase for each
route change (aka “flap”)
– Exponential decay
  ( t ' t )
P(t ' )  P(t )e
• Parameters:
– Fixed: Penalty increment
– Configurable: half-life,
suppress-, reuse-threshold,
max suppressed time
Reuse threshold
Time
Morley Mao, Ramesh Govindan, George Varghese
28
Selective Route Flap Damping
• Flaps occur due to certain topologies among routers
causing triggered announcements and withdrawals
– Not toy scenarios!
• Approach: ignore flap sequences indicating path
exploration—these likely to trigger more changes in
near future
• Redefine a flap:
– “Any route change is considered a flap”  “must alter direction of
route preference value change, relative to flaps”
– Flaps due to withdrawal: increasing AS_Path lengths, route value
keeps decreasing
• Morley Mao Ph.D. dissertation (AT&T Labs)
Morley Mao, Ramesh Govindan, George Varghese
29
• 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
30
Can You Depend on Your Routes?
BGP Route Verification
• BGP is highly vulnerable!
– Allows ASes to propagate invalid routes that deviate from
actual Internet topology
– Critical implications for performance and correctness
» Misconfigured routers cause long outages
• Drop packets (“blackholes”)
• Roughly 6% of misconfigurations cause reachability
problems
» Malicious routers cause even greater damage
• Misroute or eavesdrop on traffic
• Impersonate destinations
• Collude with other nodes to make detection difficult
Lakshmi Subramanian, Ion Stoica, Volker Roth, Scott Shenker
31
“Listen” and “Whisper”
• One approach: route verification with PKI authentication
– Deployment has been difficult
– Political issues with single PKI: who controls it?
• Alternative: route consistency testing to detect
suspicious ASes
– Listen: “Passive” TCP-probing
» Modified nodes watch TCP traffic to detect reachability problems
» No modifications to BGP, incrementally deployable
» Ineffective for detecting malicious hosts: can’t distinguish between
genuine and malicious hosts
– Whisper: Advertisements sent consistent with those received
» Route advertisement invalid if AS-PATH does not match its
propagation path (Mao: true for 8% of observed paths!)
» Use redundant net connectivity to verify route consistency
Lakshmi Subramanian, Ion Stoica, Volker Roth, Scott Shenker
32
Detection Scenarios
Browser
Browser
CNN
Reuters
Browser
Browser
CNN
CNN
Internet
Browser
Malicious
Node
Browser
No detection
in this case
Alarm
Alarm and Avoid
Adversarial Router on
the Regular Path
Isolated
Adversary
Adversary Announcing
Many Invalid Routes
Lakshmi Subramanian, Ion Stoica, Volker Roth, Scott Shenker
33
Whisper (aka “Telephone”)
Verifier
Verifier
Intermediary
Intermediary
Intermediary’
Intermediary’
Advertisements
Originator
Advertisements
Originator
Route Propagation
Loop Testing
• Alternative Whisper Protocols
– Loop Whisper, (Weak/Strong) Split Whisper
– Vary in ability to detect malicious behavior given acceptable levels
of false positive rate
Lakshmi Subramanian, Ion Stoica, Volker Roth, Scott Shenker
34
Presentation Outline
•
•
•
•
•
Heterogeneity in Devices and Networks
A New Service Architecture: SAHARA
Reachability as a Service
New Directions
Summary and Conclusions
35
The OASIS Project
•
•
•
•
•
Overlays and
Active
Services for
Internetworked
Storage
36
New Opportunity:
“The Computer is the Network”
• Emergence of Programmable Network Elements
– First Gen Network Appliances, Directors
– Storage Virtualizers, Intrusion Detectors, Traffic Shapers, Server
Load Balancers, MIE accountants
– Next Gen: Third Party Programmable beyond rules
• Generalized PNE programming and control model
– Generalized “virtual machine” model for this class of devices
– Retargetable for different underlying implementations
• Apps of Interest
– Network Services: L7 switching, firewalls, intrusion and infected
machine detection, storage virtualization, network monitoring and
management, etc.
– Network storage, iSCSI support
– Streaming media transcoding/adaptation
– Billing, accounting, stream customization for Mobile Network Edge
37
Proliferation of Network
Appliances
Packeteer PacketShaper
Network Appliance NetCache F5 Networks BIG-IP LoadBalancer
Localized content delivery platform
Web server load balancer
Traffic monitor and shaper
Ingrian i225
Cisco SN 5420
SSL offload appliance
IP-SAN storage gateway
NetScreen 500
Extreme Networks SummitPx1
Firewall and VPN
L2-L7 application switch
Nortel Alteon Switched Firewall
CheckPoint firewall and L7 switch
Cisco IDS 4250-XL
Intrusion detection system
In-the-Network Processing: the Computer IS THE Network
38
OASIS Vision
• Problem
– Common programming/control environment for diverse network
elements to realize full power of “inside the network” services
and applications
• Approach
– Software toolkit and VM architecture for PNEs, with
retargetable optimized backend for diverse appliance-specific
architectures
• Current Focus
– Network health monitoring, protocol interworking and packet
translation services, iSCSI processing and performance
enhancement, intrusion and worm detection and quarantining
• Potential Impact
– Open framework for multi-platform appliances, enabling third
party service development
– Provable application properties and invariants; avoidance of
configuration and “latest patch not installed” errors
39
Generic PNE Architecture
Buffers
Buffers
CP
CP
CP
CP
Classification
Processor
Tag
Mem
CP
CP
CP
AP
Rules &
Programs
Interconnection
Fabric
Output Ports
Input Ports
Buffers
Action
Processor
40
OASIS Testbed
• Programmable Networking
Testbed
– Alteon Filter Programmable Level 7
Switches
» Next generation significantly
more third party
programmable
– 2 x Enterprise Class Routers
– (Many) 1U PCs
• In discussion
– Nortel + IBM on Blade Center
Storage Servers for UDCs
– Cisco IOS Next Generation (ION)
Programmable Packet Filters
41
Presentation Outline
•
•
•
•
•
Heterogeneity in Devices and Networks
A New Service Architecture: SAHARA
Reachability as a Service
New Directions
Summary and Conclusions
42
SAHARA
• Evolve Internet architecture better supporting multinetwork/multi-service provider model
– Dynamic environment, many 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
– Essential for successfully connecting applications endpoints in a
distributed network environment
» QoS through Overlays: loss and bandwidth guarantees
» Enhanced route reliability through fast convergence
» Security: BGP Verification/Detection + Containment
43
New Service Architecture
Integrated Communications and Processing
• Increasing diversity of interconnected devices
• Increasing importance of “services” to mitigate
diversity/provide new functionality and customization
– Refocus from performance to reliability/dependendabilty
• 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
Predictable performance and end-to-end reliability
44
The Post-PC
Era:
It’s About the
Services
Randy H. Katz
Thank You!
45
Any
Questions?
46
The Post-PC Era:
It’s About The Services
Randy H. Katz
Computer Science Division
Electrical Engineering and Computer Science Department
University of California, Berkeley
Berkeley, CA 94720-1776
47
Controlled-Loss Virtual Link (CLVL)
• Two parameters:
–
–
Statistical bound on loss rate, q (<= p; typically << p)
Capacity, c(t), possibly time-varying
• Can prove: if offered load < c(t), then loss rate < q
• How is c(t) determined?
– Given f(t) to be the redundancy factor:
c(t) = b(t)( 1- f(t))
Flow 1
Flow 2
c(t), q
Buffer mgmt &
Scheduling &
Traffic regulator
Coder
b(t), p(t)
Decoder
Flow n
OverQos Node
CLVL
control plane
48
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
49
These Relationships Matter!
• 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
50
Underlying AS Structure
• Peer-peer relationships hard to infer
20 AS’s
• Some unusually relationships
129 AS’s
– Mislabeling P-P edge as P-C does not change
valid path into invalid
– Heuristics to detect P-P edges
–
–
–
–
Siblings providing mutual transit
Backup relationship for failed connectivity
Misconfigured conventional relationships
Detect cases by analyzing “invalid” paths
897 AS’s
• Access to large path set is hard
– Exploit BGP routing tables from multiple
vantage points (10 public BGP tables)
971 AS’s
April 2001
11K ASs
24K edges
Inner Core
Transit Core
Outer Core
Regional ISPs
8898 AS’s
Customers
51
Policy Management for BGP
• Integrate BGP with 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 (Sprint ATL)
PA AS
AS PA
PA AS
AS PA
AS
PA
52
Policy Control Architecture for
InterAS Routing
Sharad Agarwal
• Tremendous growth in multi-ISP connectivity
– But slow failover & weak traffic balancing
– Bogus announcement & static peering problems
• Approach : separate policy control architecture
– BGP not designed for such issues
– Explicit negotiation, traffic & peering intelligence
– More flexibility, control, verification
• Impact : media / application service providers,
users
– Available connectivity
– Manageable congestion
53
Tomography-based Overlay
Network Monitoring
Yan Chen
• Given n end hosts on an
overlay network and O(n2)
paths, how to select a
minimal subset of paths to
monitor so that the loss
rates/latency of all other
paths can be inferred.
•
Overlay Network
Operation Center
End hosts
Approach: select a basis set of k path segments
that completely describe all O(n2) paths (k = O(n))
–
–
•
topology
Select and monitor k linearly independent paths to compute the
loss rates of basis set
Infer the loss rates of all other paths
Find > 97% lossy paths with < 5% false positive
54
Performance Characteristics of TCP
Throughput for Peer Selection in
Peer-to-Peer Networks
Weidong Cui
• Problem
– How to select the optimal peer for download from a set of
candidates
• Approach
– Evaluate performance of various probing techniques: RTTbased, size-based, time-based
– Investigate the relationship between probing parameters
and various download file sizes
• Impact
– Improve the performance of p2p networks
55
Underlay Optical Networks
Tal Lavian
• Problem
– Radical mismatch between the optical transmission world and the
electrical forwarding/routing world. Currently, a single strand of
optical fiber can transmit more bandwidth than the entire
Internet core.
– Mismatch between L3 core capabilities and disk cost. With $2M
disks (2PB) can fill the entire core internet for a year
• Approach
– Service architecture interacts with the optical control, provides
applications a dedicated, on-demand, point-to-point optical link
that is not on the public Internet
• Current Focus
– Grid Computing, OGSA, MEMs, 10GE, Optical technologies
– OmniNet testbed in Chicago, which will be connected to major
national and international optical networks
• Potential Impact
– Enabling technology for Data-Intensive applications (multi
Terabytes)
56
Estimating Shared Congestion
Among Internet Paths
Sridhar Machiraju
• Problem
– Given two paths in the Internet, estimate the fraction of
packet drops at shared points of congestion (PoCs) using
probe flows along the paths
• Approach
– Count correlated (simultaneous) packet drops of two probe
flows (UDP or TCP)
– “Inflate” the fraction using delay jitter correlation
• Applications using path diversity e.g.,
multimedia streaming, parallel downloads, etc.
57
Routing Dynamics in Simultaneous
Overlay Networks
Mukund Seshadri
• Problem: When is “greedy” overlay-level route selection
unstable/inefficient, when multiple such overlay networks
interact?
• Motivation: why will many overlay networks be deployed?
– Due to pure Overlay Network protocols (RON[3], Detour[4], ESM[5])
– Due to deployment of overlay primitives (“Path reflection”, i3-arch.)
• Model and Focus: Overlays make independent decisions; no
info. shared.
– Size: 50-100 overlay networks; 10-100 nodes each.
– App: Multimedia streams, long-lived, need bandwidth level + stability
• Impact: simple design principles to ease deployment of
multiple overlay networks
– Randomization of route selection improves stability and loss-rates.
» With high path sharing, variation in link b/w, loaded links, low crosstraffic.
– Random-subset method improves stability even more, with comparable
loss-rate, and lower measurement overhead.
58