Transcript research - Zoo

Some Current Research/Challenges
04/23/2008
Admin.
 Multimedia applications and QoS slides are
linked on the schedule page
 Programming assignment 3

Due on May 5
 Office hours during break
 please send email to Antonis and me for
appointments
Objectives
 A brief introduction to some computer
networking projects we are working on here
at Yale

disclaimer: some projects I describe are not Yale
projects
 More importantly, focus on perspectives that
challenge what we have covered in class 
Objectives of Networking Research
 Faster
 More efficient
 More reliable
 More ubiquitous
 Safer
Faster
Rising Content Distribution Demand
Some speculation
“Within five years, all
media will be delivered
across the Internet.”
- Steve Ballmer, CEO
Microsoft, D5 Conference,
June 2007

The Internet is
increasingly being used
for content and media
delivery
Rising Bandwidth Demand
http://dynamic.abc.go.com/streaming/landing?lid=ABCCOMGlobalMenu&lpos=FEP
 “Desperate Housewives”
 210MB/hour
for 320x240 H.264
Video iTunes image
 assume 10,000,000
households downloads
 How long will that take to download?
 3 days @ 64Gbps non-stop !
 HD video is 7~10 times larger than non-HD video
 AT&T predicts 50-fold increase in broadband to
2015 (75% per year)
http://www.pbs.org/cringely/pulpit/pulpit20060302.html
Internet Bandwidth Growth
Source: TeleGeograph Research
What Determines Transmission Rate?
 Service: transmit a bit stream from a sender
to a receiver
sender
input
bit stream
Encoding
receiver
channel
Decoding
output
bit stream
Question to be addressed: how much can we send through the channel ?
Basic Theory: Channel Capacity
 The maximum number of bits that can be
transmitted per second (bps) by a physical
media is:
W log 2 (1  )
S
N
where W is the frequency range, S/N is the
signal noise ratio. We assume Gaussian noise.
Fourier Transform
 Suppose the period of a data unit is f (=1/T),
then the data unit can be represented as the
sum of many harmonics (sin(), cos()) with
frequencies f, 2f, 3f, 4f, …
 A reasonably behaved periodic function g(t),
with minimal period T, can be constructed as
the sum of a series of sines and cosines:


n 1
n 1
g (t )  12 c   an sin( 2nft )   bn cos( 2nft )
 f  1/ T

T
2
c 
T  g (t )dt

0


T

2
an  T  g (t ) sin( 2nft )dt
0

T

bn  T2  g (t ) cos( 2nft )dt

0

char “b”
rmsn  an  bn
Signal Attenuation
W log 2 (1  NS )
 The quality of signal will degrade when it travels
 loss, frequency passing
Frequency Dependent Attenuation
 The received signal will be distorted even when
there is no interference and the transmitted signal
is “perfect” square waveform
Example: Voltageattenuation magnitude
ratios of Category 5
cable. For example, 500
feet of cable
attenuates a 10-MHz,
1-V signal to 0.32 V,
which corresponds to
about –9.90 dB
Example
V.34 (33.6kbps Dialup Modem)
channel
sender modem
input
bit stream
3Khz
Modem
bandwidth
Modulation
(add
white noise)
(digit->analog)
telephone network
Analog to Digital
quantization
for transmitting through
the digital telephone
backbone
ISP modem
ISP
demodulation
output
bit stream
Example: W=3000Hz, S/N  4000
max bandwidth  3000 log 2 (1  4000)  36kbps
Example: ADSL
 Spectrum allocation:
divided into a total of
256 downstream and
32 upstream tones, where
each tone is a standard
4kHz voice channel
 During initial negotiation, a tone is used only
if the S/N is above 6 db (4)
down  256 * 4000 log 2 (1  4)  2.4 Mbps
up  32 * 4000 log 2 (1  4)  297kbps
The Wire: Fiber
 A look at a fiber
A graded index fiber
 How it works?
The Wire: Fiber
 Wide spectrum at low loss:
~0.3db/km
(c.f. copper ~190db/km @100Mhz),
30-100km without repeater
 bit error rate 10-15
(c.f. copper 10-4-10-8)
 bandwidth of a single fiber
 commercial: 1.6Tbps using 169 channels
 lab: 10 Tbps
 theoretical: 100-200Tbps
http://www.trnmag.com/Stories/080101/Study_shows_fiber_has_room_to_
grow_080101.html
 Lightweight: 33 tons of copper to transmit the same
amount of information carried by ¼ pound of optical
fiber
Advantages of Fibers
How to Do Switching?
 Optical-Electrical-Optical
 Optical switch: optical micro-electro-mechanical systems (MEMS)
Optical path
One optical switch
http://www.qwest.com/largebusiness/enterprisesolutions/networkMaps/preloader.swf
Example: MEMS Optical Switch
 Using mirrors, e.g. Lambda Router
Implications
 Fine-grained switching may not be feasible
 What is the architecture of optical networks:
packet switching, circuit switching, or
others?
Higher Efficiency
Integrating P2P into Internet Content Distribution
 Initially
standalone applications
 rogue technology (e.g., copyright issues)

 Recent development
 becomes part of content delivery infrastructure
 integrated P2P + servers solutions
 some projects
• BBC's iPlayer (tremendously popular), Joost, Pando and
NBC, MSN video
• Verizon P2P, Thomson/Telephonica nanoData Center
P2P Efficiency
Traditional content
distribution
P2P, e.g., BT
Internet Transit
Regional Routers
Edge Network
More Viewers =
Worse performance
Higher cost
- Network oblivious peering
-> scattered traffic
- Higher financial cost
- Inefficiency
P2P Problem I: Bandwidth Usage
Cache Logic Research: Internet Protocol Breakdown 1993 - 2006
P2P Problem II: Increased Operational Costs
provider
provider to
customer

provider
customer
Violating Internet economics (bypass BGP): relay
traffic between providers

increased network operational costs
P2P Problem III: Inefficient Interactions
 An iterative process between two sets of
adaptation:
 ISP: traffic engineering to change routing
to shift traffic away from higher utilized
links
• current traffic pattern  new routing matrix

P2P: direct traffic to better performing
peers
• current routing matrix  new traffic pattern
ISP Traffic Engineering+ P2P Latency Optimizer
- red: P2P adjust alone; fixed ISP routing
- blue: ISP traffic engineering adapt alone; fixed P2P communications
ISP optimizer interacts poorly with P2P.
Attempts to Address P2P Efficiency Problems
ISPs Address P2P
• upgrade network
infrastructure
• deploy P2P caching devices
• terminate user connectivity
• rate-limit P2P traffic
• ...
P2P Countermeasures
• use random ports
• encrypt traffic
• ...
Network neutrality argument
The Fundamental Problem
 Traditional Internet architectural feedback
to application efficiency is limited:
routing (hidden)
 rate control through coarse-grained TCP
congestion feedback

 To achieve better efficiency, needs explicit
communications between network resource
providers and applications

a network resource provider can be a traditional
ISP (AT&T, Verizon) or a content distribution ISP
such as Akamai, or a caching provider
P4P Objective
 Design a framework to enable better providers and
applications cooperation
 ISP perspective:
 guide applications to achieve more efficient resource usage
 avoid undesirable (expensive/limited capacity) links to more
desirable (inexpensive/available capacity) links
 Resource providers such as caching, CDN providers
perspective

provide applications with better, on-demand
resources/quality
 P2P perspective:
 better performance for users
 decrease incentives for ISPs to “manage” applications
P4P Framework – Design Goals
 Performance improvement
 Scalability and extensibility: support diverse
ISP objectives and applications scenarios in
large networks
 Privacy preservation
 Ease of implementation
 Open standard: any ISP, provider,
applications can easily implement it
The P4P Framework
 Data plane
 control plane
 iTracker: a portal for each network service
provider
 iTracker of a provider can be identified in multiple
ways
• e.g., through DNS SRV records
 An
iTracker provides multiple interfaces so that
others can interact
•
•
each provider decides the interfaces it provides
each interface is encoded in Web Service Definition Language (WSDL)
for extensibility
Control Path Interfaces
 provider capabilities interface: request QoS,
CoS, servers participation in content
distributions
 topology interface: topology and connectivity
 ISP policy and guideline interface: e.g.,
traffic balance ratio for inter-AS peering
links, time of day preference
…
P4P Control Path : Request Capability
pTracker/content provider pTracker
requests ISP capabilities to
accelerate content
distribution.
iTracker
A
a
ISP A
iTracker
B
b
1: pTracker [content provider] requests ISP B’s participation in content
distribution
2: Provider B allocates servers to accelerate content distribution
3: pTracker includes ISP B’s servers in returned peering sets to peers
ISP B
The Virtual Topology Interface
 An interface to guide peer selection
 An interface as an optimization decomposition
interface
 guidance
through “virtual costs”
Background: Peer Selection
HTTP GET MYFILE.torrent
MYFILE.torrent
webserver
user
“register”
pTracker
BitTorrent as an example
list of peers
ID1 169.237.234.1:6881
ID2 190.50.34.6:5692
ID3 34.275.89.143:4545
…
ID50 231.456.31.95:6882
…
Peer 40
Peer 2
Peer 1
Control Path: Virtual Topology Interface
pTracker
2
iTracker
3
1
peer
4
ISP A
Information flow:
1. peer queries
pTracker
2. pTracker asks
iTracker for
guidance
(occasionally)
3. iTracker returns
high-level peering
suggestions
4. pTracker selects and
returns a set of
active peers,
according to the
suggestions
iTracker can be run by
trusted third parties, P2P
network, or ISPs for
security/privacy
The Virtual Topology Interface: Network
 PID: set of Points
of Presence (PoP)
 E: set of links
connecting PoPs
 ce: the link capacity of link e
 Ie(i, j): indicator if link e is on the route from
PoP i to PoP j
 be: amount of background traffic on link e
The Virtual Topology Interface: P2P
 Assume K applications running inside the ISP

we call each running P2P application a swarm
 Let Tk be the set of acceptable demands for
swarm k
 tk
in Tk specifies traffic demand tkij from each
pair of source-destination PoPs (i,j)
The Virtual Topology Interface
 Consider an example: ISP wants to minimize
utilization of the highest utilized link

the utilization of the highest utilized link is called
the Maximum Link Utilization (MLU)
min max (be   t I (i, j )) / ce
eE
i j
k
s.t. k : t  T
k
k
k
ij e
ISP MLU: Transformation
min
s.t.

e : be   t I (i, j )  ce
k
k
ij e
i j
k : t  T
k
k
ISP MLU: Dual
 Introducing pe (≥ 0) for the inequality of each
link e
D(pe )  mink k    pe (be   t  ce )
k
e
 ;k :t T
e
 To make the dual finite, need
p c
e e
e
1
k
ISP MLU: Dual
 Then the dual is
k
D(pe )  min
p
(
b

t
)


e
e
e
k
k
k :t T
  pebe   min
pt
k
k
e
e
k
e
t T
k
e e
k
  pebe   min
pt
k
k
e
k
e
k
t T
k
e e
e
k
  pebe   min
p
t
ij ij
k
k
t T
i j
where pij is the sum of pe along the path from
PoP i to PoP j
ISP MLU Dual : Interpretation
D(pe )   pebe   min
pt
k
k
e
k
t T
i j
k
ij ij
 Each swarm k chooses tk in Tk to minimize
weighted sum of tij
 The interface between a swarm and the ISP
is the “shadow prices” {pij}
Topology with Costs (Illustration)
PID1
70
PID2
30
10
PID6
PID5
60
20
PID3
Each PID has:
• IP “prefix”
PID4
Each link has
•“Price”
Prices are directional
ISP Update
 At update m+1,
calculates
pe (m  1)  [ pe (m  1)   (m) (m)]S
 : step size
 : supergradi ent of D({p e })
[]S : projection to set S
S : {p e :  pe ce  1; pe  0}
e
P2P Operations
 Each swarm optimizes its own performance,
then picks ISP-friendly peering
 For example, selects
where  is tolerance, say 80%.
Example: Multihoming
Multihoming
ISP 1
User
ISP 2
ISP K

Internet
A common way of
connecting to Internet
Smart routing
Intelligently distribute
traffic among multiple
external links
 Improve performance
 Improve reliability
 Reduce cost

Interdomain Topo
PID1
70
Cost?
PID2
30
Provider1
20
Cost?
10
PID6
PID3
Cost?
PID5
60
PID4
Provider 3
Provider 2
Integrating Cost Min with P4P
min
s.t.

e  E0 : be   t I (i, j )  ce
k
i j
k
ij e
e  Ee : be   t I (i, j )  ve
k
i j
k
k
ij e
k : t  T
k
Field-Tests
 So far integrated with
BitTorrent on PlanetLab
 Pando: a P2P software (18 million downloads)
 Maze: about 5 million users

 Run iTrackers
 Verizon at Yale
 Telephonica at its own location
 Collect data from Feb. 21 to March 2
ISP Perspective: Overall
Traffic within Verizon
Average Hop Each Bit Traverses
 Why less than 1: many transfers are in the
same metro-area; also same metro-area peers
are utilized more by tit-for-tat.
P2P Perspective: Download Rates
Current Status
 P4P-WG
 Next step
 wider integration
 IETF standard
• AT&T
• Bezeq Intl
• BitTorrent
• CacheLogic
• Cisco Systems
• Grid Networks
• Joost
• LimeWire
• Manatt
• Oversi
• Pando Networks
• PeerApp
• Telefonica Group
• VeriSign
• Verizon
• Vuze
• Univ of Washington
• Yale University
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Abacast
AHT Intl
Akamai
Alcatel Lucent
CableLabs
Cablevision
Comcast
Cox Comm
Juniper Networks
Microsoft
MPAA
NBC Universal
Nokia
RawFlow
Solid State Networks
Thomson
Time Warner Cable
Turner Broadcasting
Higher Reliability
Is the Internet Reliable?
 A key design objective
of the “Internet” (i.e.,
packet-switched
networks) is robustness
 Does the Internet
infrastructure achieve
the target reliability
objective of a highly
reliable system
(99.999%)?
Perspective
 911 Phone service (1993 NRIC report +)
29 minutes per year per line
 99.994% availability

 Std. Phone service (various sources)
 53+ minutes per line per year
 99.99+% availability
 …what about the Internet?
 Various
studies: about 99.5%
 Need to reduce down time by 500 times to
achieve five nines; 50 times to match phone
service
Threats to Internet Availability:
Operator Errors
- 80% IT budget spent on
maintaining status quo
- human configuration errors
account for about 60% of all
network outages.
Zeus Kerravala, Yankee Group
Shadow Configurations as a
Network Management Primitive
Shadow Configurations as a
Network Management Primitive
Threats to Internet Availability: Accidents
Oroville
Stockton
Rialto
El Paso
Sprint Backbone: Jan. 9, 2006
- 675,000 excavation accidents
Reliability as an Interdomain Service
 ISPs pool resources to form an “insurance”
pool

implications?
 Resilient routing reconfiguration
Threats to Internet Availability: Natural
Disasters
Unreachable Networks: 10 days
Internet Disaster Recovery Response
 Why slow response?


the cable repairing is slow: not until 21 days
after quake
BGP is not designed to create business
relationship
 Objective
 a meta-BGP to facilitate discovery and creation
of BGP business relationship
More Ubiquitous Connectivity
Goal of Network Access
“People and their machines should be able to
access information and communicate with
each other easily and securely, in any
medium or combination of media – voice,
data, image, video, or multimedia – any time,
anywhere, in a timely, cost-effective way.”
Dr. G. H. Heilmeier, Oct 1992
Network Access: Ubiquitous Access
 Goals

be connected whenever possible via the “best”
available network
• ubiquitous
• location-aware, e.g.
– what services (e.g., printers) are available “here”?
– where is the “nearest” database/cache?
– where is the “nearest” ATM?



handle multiple network interfaces
• may operate at the same time
support the application’s graceful
adaptation to the available
bandwidth and latency
transparent handoff of user sessions
among different devices/networks
 Example: wireless overlay

may take off if we can combine
cellular and WLAN
Motorola CN 620
Access: Build an Access Network Fast: Ad-Hoc Networks
Faster Wireless
Recap: Traditional Routing
 So far, all routing protocols in wireless also
use the framework of traditional Internet
routing we covered in class

a graph representation of underlying network
• point-to-point graph edges with costs
select a lowest-cost route for a src-dest pair
 commit to a specific route before forwarding

A Simple Motivating Scenario
 Assumes independent loss
 Internet architecture computes routing with one pre-
committed route
Implications?
How about Using Multiple Paths?
Traditional Routing
3 forwarders
4 links
Opportunistic:
7 forwarders
18 links
Opportunistic Coding
Motivating Scenario
 A sends 1 packet to B; B sends packet 3 to A
A
R
B
 If R has both packets 1 and 3, it can
combine them and explore coding and
broadcast nature of wireless
Faster Wireless: Summary
 Both approaches dispose the point-to-point
Internet link abstraction
 Both approaches take advantage of
opportunities and leverage broadcast nature
of wireless medium to its advantage
New Access: Connecting the Physical World
 Mark Weiser from Xerox:
transparent computing is the ultimate goal

computers should disappear into the
background
Network Access: Sensors
 COTS sensors
embedded microprocessor
 RF transceiver

• 916MHz, ~20m range, 4800 bps
week fully active, 2 yr @1%
 recharge by solar, wind, …
N
W
E
S
2 Axis Magnetic
Sensor
2 Axis Accelerometer
1
Light Intensity
Sensor
Humidity Sensor
Pressure Sensor
Temperature Sensor
Course Summary
 The field is moving fast, broad and not well-defined !
 Driven by Technology, Infrastructure, Applications,
and Understanding:

technology
• e.g., wireless/optical communication technologies and device
miniaturization (sensors)

infrastructure
• e.g., global infrastructure

applications
• e.g., P2P, content distribution, sensing, grid computing, VoIP,
IPTV

understanding
• e.g., resource sharing principle, routing principles, mechanism
design, and randomized access