Transcript The Future of Broadband Wireless

The Future of Broadband Wireless
(and the role of “awareness” in
wireless Internet performance)
Carey Williamson
iCORE Professor
Department of Computer Science
University of Calgary
October 16, 2002
1
Introduction
r It is an exciting time to be an Internet
researcher (or even a user!)
r The last 10 years of Internet development
have brought many advances:
m
m
m
m
m
m
World Wide Web (WWW)
Media streaming applications
“Wi-Fi” wireless LANs
Mobile computing
E-Commerce, mobile commerce
Pervasive/ubiquitous computing
October 16, 2002
2
October 16, 2002
3
The Wireless Web
r The emergence and convergence of these
technologies enable the “wireless Web”
m
m
m
the wireless classroom
the wireless workplace
the wireless home
r Holy grail: “anything, anytime, anywhere”
access to information
(when we want it, of course!)
r My iCORE mandate: design, build, test, and
evaluate wireless Web infrastructures
October 16, 2002
4
Clarification
“Wireless Communications”
(the enabler)
=
“Wireless Internet”
(the value-added service)
October 16, 2002
5
Internet Protocol Stack
r
Application: supporting network
applications and end-user services
m
r
Transport: end to end data transfer
m
r
IPv4, IPv6, BGP, RIP, routing protocols
Data Link: hop by hop frames,
channel access, flow/error control
m
r
TCP, UDP
Network: routing of datagrams
from source to destination
m
r
FTP, SMTP, HTTP, DNS, NTP
PPP, Ethernet, IEEE 802.11b
Application
Transport
Network
Data Link
Physical
001101011...
Physical: raw transmission of bits
October 16, 2002
6
Pieces of the Puzzle
r Portable computing devices: no problem
r
r
r
r
(cell phones, PDAs, notebooks, laptops…)
Wireless access: not much of a problem
(BlueTooth, IEEE 802.11, 802.11b, “WiFi”,
802.11a, Pringles…)
Security: still an issue, but being addressed
Services: the next big growth area???
Performance transparency: providing an
end-user experience that is hopefully no
worse than that in traditional wired
Internet desktop environments (my focus)
October 16, 2002
7
Research Theme
r Existing layered Internet protocol stack
does not lend itself well to providing
optimal performance for diversity of
service demands and environments
r Who should bend: users or protocols?
r Explore the role of “awareness” in Internet
protocol performance
r Identify tradeoffs, evaluate performance
October 16, 2002
8
Talk Overview
r Introduction
r Background
m Emerging Wireless Trends and Technologies
m The Future of Broadband Wireless
r The Role of “Awareness”
m
m
m
TCP 101
Motivating Examples
Our Work on CATNIP
r Concluding Remarks
October 16, 2002
9
Brief History: Cellular/Wireless
r First Generation (1G): analog
(cellular voice, AMPS, RTMS, TACS, 1980’s)
r Second Generation (2G): digital
(IS-64, GSM, ISM-95, 8-32 kbps, 1990’s)
2.5G
You are here
r Third Generation (3G): broadband multimedia
(always on, UMTS, 334 kbps-2 Mbps, 2000’s)
October 16, 2002
10
Some Interesting Reading
r Brave New Unwired World (BNUW),
by Alex Lightman and William Rojas
r In a nutshell, the authors argue that:
m
2.5G is dead
m
3G is a waste of time (and money)
m
4G is EVERYTHING!!!
October 16, 2002
11
Another Lightman Opinion
r “the success of a technology in the
marketplace is inversely proportional to
the amount of hype associated with that
technology prior to its release”
Examples:
ISDN
BlueTooth
3G
October 16, 2002
Examples:
Internet,
Web,
napster,
WiFi
12
What is 4G then?
r Culmination of wireless Internet revolution
r Convergence of key emerging technologies:
Image Generation
802.11b
GPS
Wearable Computers
New Interfaces
WIDs
IP-based Networks
Satellite
Backhaul NWs
Molecular Engineering
Wireless Services
October 16, 2002
Storage technology
Semiconductors
Microprocessors
Antenna Arrays
RF elements
NanoTech
Quantum
13
Some Challenges/Opportunities
r Ultra low-power processors:
m
pg 108: “could change the entire industry…”
r Services:
m pg 76: “extension of the Internet to mobile
devices…whole new range of Internet
services…personalized, location-sensitive
content…previously impossible or impractical”
r Awareness:
m pg 221: “Location/context-aware applications…
can determine and react to current physical
computing context of mobile users… altering
information presented to users accordingly”
October 16, 2002
14
The Future?
r Service-centric economy
r Significant shifting of economic power
r The “winner” is likely to be either Japan
(iMODE, DoCoMo) or China (Internet
growth, wireless growth)
r Reasons:
m
m
cooperation, encouragement, support from
government on a national scale
strategic alliances within and across industries
October 16, 2002
15
Talk Overview
r Introduction
r Background
m Emerging Wireless Trends and Technologies
m The Future of Broadband Wireless
r The Role of “Awareness”
m
m
m
TCP 101
Motivating Examples
Our Work on CATNIP
r Concluding Remarks
October 16, 2002
16
My iCORE Research Team
r
r
r
r
r
r
Martin Arlitt: Web performance,
Application
workload characterization
Transport
Qian Wu: TCP, ns-2 simulation
Guangwei Bai: network traffic
Network
measurement and modeling
Tianbo Kuang: wireless measurements,
Data Link
video compression, streaming media
Nayden Markatchev: technical support
Physical
Grad Students: Mingwei Gong, Yujian Li,
Kehinde Oladosu, Fang Xiao, Andreas Hirt,
Abhinav Gupta, Gwen Houtzager
October 16, 2002
17
Internet Protocol Stack
r
Application: supporting network
applications and end-user services
m
r
Transport: end to end data transfer
m
r
IPv4, IPv6, BGP, RIP, routing protocols
Data Link: hop by hop frames,
channel access, flow/error control
m
r
TCP, UDP
Network: routing of datagrams
from source to destination
m
r
FTP, SMTP, HTTP, DNS, NTP
PPP, Ethernet, IEEE 802.11b
Application
Transport
Network
Data Link
Physical
001101011...
Physical: raw transmission of bits
October 16, 2002
18
Viewpoint
r “Layered design is good;
layered implementation is bad” -Anon.
r Good:
m
m
unifying framework for describing protocols
modularity, black-boxes, “plug and play”
functionality, well-defined interfaces (good SE)
r Bad:
m increases overhead (interface boundaries)
m compromises performance (ignorance)
October 16, 2002
19
Research Theme
r Existing layered Internet protocol stack
does not lend itself well to providing
optimal performance for diversity of
service demands and environments
r Who should bend: users or protocols?
r Explore the role of “awareness” in Internet
protocol performance
r Identify tradeoffs, evaluate performance
October 16, 2002
20
Tutorial: TCP 101
r The Transmission Control Protocol (TCP) is
r
r
r
r
the protocol that sends your data reliably
Used for email, Web, ftp, telnet, …
Makes sure that data is received correctly:
right data, right order, exactly once
Detects and recovers from any problems
that occur at the IP network layer
Mechanisms for reliable data transfer:
sequence numbers, acknowledgements,
timers, retransmissions, flow control...
October 16, 2002
21
TCP 101 (Cont’d)
r TCP is a connection-oriented protocol
SYN
SYN/ACK
GET URL
ACK
YOUR DATA HERE
FIN
ACK
October 16, 2002
FIN/ACK
22
TCP 101 (Cont’d)
r TCP slow-start and congestion avoidance
ACK
October 16, 2002
23
TCP 101 (Cont’d)
r TCP slow-start and congestion avoidance
ACK
October 16, 2002
24
TCP 101 (Cont’d)
r TCP slow-start and congestion avoidance
ACK
October 16, 2002
25
TCP 101 (Cont’d)
r This (exponential growth) “slow start”
process continues until either of the
following happens:
m
m
packet loss: after a brief recovery phase, you
enter a (linear growth) “congestion avoidance”
phase based on slow-start threshold found
all done: terminate connection and go home
October 16, 2002
26
Simple Observation
r Consider a big file transfer download:
m
brief startup period to estimate network
bandwidth; most time spent sending data at the
“right rate”; small added penalty for lost packet(s)
r Consider a typical Web document transfer:
m median size about 6 KB, mean about 10 KB
m most time is spent in startup period; as soon as
you find out the network capacity, you’re done!
m if you lose a packet or two, it hurts a lot!!!
October 16, 2002
27
The Problem (Restated)
r TCP doesn’t realize this dichotomy between
optimizing throughput (the classic file
transfer model) versus optimizing transfer
time (the Web document download model)
r Wouldn’t it be nice if it did?
(i.e., how much data it was sending, and
over what type of network)
r Some research starting to explore this...
October 16, 2002
28
Motivating Example #1
r Wireless TCP Performance Problems
Low capacity,
high error rate
Wireless
Access
October 16, 2002
Wired Internet
High
capacity,
low
error
rate
29
Motivating Example #1
r Solution: “wireless-aware TCP” (I-TCP,
ProxyTCP, Snoop-TCP, ...)
October 16, 2002
30
Motivating Example #2
r Multi-hop “ad hoc” networking
Janelle
October 16, 2002
Carey
31
Motivating Example #2
r Multi-hop “ad hoc” networking
Janelle
Yannis
October 16, 2002
Carey
32
Motivating Example #2
r Multi-hop “ad hoc” networking
Janelle
Yannis
October 16, 2002
Carey
33
Motivating Example #2
r Multi-hop “ad hoc” networking
Janelle
Yannis
October 16, 2002
Carey
34
Motivating Example #2
r Two interesting subproblems:
m
m
Dynamic ad hoc routing: node movement can
disrupt the IP routing path at any time,
disrupting TCP connection; yet another way to
lose packets!!!; possible solution: Explicit Loss
Notification (ELN)
TCP flow control: the bursty nature of TCP
packet transmissions can create contention for
the shared wireless channel among forwarding
nodes; possible solution: rate-based flow control
October 16, 2002
35
Example of Our Work
r Context-Aware Transport/Network
Internet Protocol (CATNIP)
r Motivation: “Like kittens, TCP connections
are born with their eyes shut” - CLW 2002
r Research Question: How much better could
TCP perform if it knew what it was trying to
accomplish (e.g., Web document transfer)?
October 16, 2002
36
Some Key Observations (I think)
r Not all packet losses are created equal
r TCP sources have relatively little control
r IP routers have all the power!!!
October 16, 2002
37
Tutorial: TCP 201
r There is a beautiful way to plot and
visualize the dynamics of TCP behaviour
r Called a “TCP Sequence Number Plot”
r Plot packet events (data and acks) as
points in 2-D space, with time on the
horizontal axis, and sequence number on
the vertical axis
October 16, 2002
38
SeqNum
+
X
+
X
+
X
+
X
+
X
+
X
+
X
Key: X Data Packet
+ Ack Packet
X
X
X
X
X
+
X
X
+
+
+
+
+
+
Time
October 16, 2002
39
TCP 201 (Cont’d)
r What happens when a packet loss occurs?
r Quiz Time...
m Consider a 14-packet Web document
m For simplicity, consider only a single packet loss
October 16, 2002
40
SeqNum
?
Key: X Data Packet
+ Ack Packet
X
X
X
X
X
+
X
X
+
X
+
X
+
X
+
X
+
X
+
X
+
+
+
+
+
+
Time
October 16, 2002
41
SeqNum
Key: X Data Packet
+ Ack Packet
X
X
X
X
X
+
X
X
+
X
+
X
+
X
+
X
+
X
+
X
X
+
+
+
+
+
+
+
Time
October 16, 2002
42
SeqNum
Key: X Data Packet
+ Ack Packet
X
X
X
?
X
X
X
X
X
X
X
X
+
X
X
+
+
+
+
+
+
+
+
+
Time
October 16, 2002
43
SeqNum
Key: X Data Packet
+ Ack Packet
X
X
X
X
X
X
X
X
X
X
X
+
X
X
+
X
+++
+
+
+
+
+
+
+
+
+
Time
October 16, 2002
44
SeqNum
Key: X Data Packet
+ Ack Packet
?
X
+
X
+
Time
October 16, 2002
45
SeqNum
Key: X Data Packet
+ Ack Packet
X
X
X
X
X
X
X
+
+
+
+
+
X
X
X
+
+
+
+
++
X
Time
October 16, 2002
46
TCP 201 (Cont’d)
r Main observation:
m
“Not all packet losses are created equal”
r Losses early in the transfer have a huge
adverse impact on the transfer latency
r Losses near the end of the transfer always
cost at least a retransmit timeout
r Losses in the middle may or may not hurt,
depending on congestion window size at the
time of the loss
October 16, 2002
47
Relative Transfer Time
The TCP Transfer “Pain Profile”
1
SeqNum of the Single Lost Packet
October 16, 2002
N
48
Design of CATNIP
• Can we make the TCP/IP protocols “smarter” about
the specific job they are trying to do?
 Yes. Convey application-layer context
information to the TCP and IP layers
Application
Document Size
Transport
Packet Priority
October 16, 2002
Network
49
Design of CATNIP (Cont’d)
• Q: What could a TCP source do differently?
• A: If it knew how much data it had to send, and
how far along it was already, then maybe…
 Rate-Based Pacing of the Last Window
(RBPLW)
 Early Congestion Avoidance (ECA)
 Selective Packet Marking (SPM):
Use the reserved high-order bit in the TCP
header to convey packet priority information
(high priority for the really crucial packets)
October 16, 2002
50
Design of CATNIP (Cont’d)
• Q: What could an IP router do differently?
• A: If it knew which packets were the “painful”
ones to lose, then the router could…
 CATNIP-Good: give them preferential
treatment, and avoid throwing them away
(if possible) when congested
 CATNIP-Bad: throw them away
October 16, 2002
51
Simulation Evaluation
• Network model:
Client 1
Server 1
Client 2
1.5 Mbps, 5 ms
Server 2
RouterS
RouterC
Client 99
Server 10
October 16, 2002
Client 100
52
Simulation Evaluation (Cont’d)
• Web workload model:
 100 clients, 10 different Web pages
 Use empirically-observed distribution to determine
the size, and the number of embedded images
October 16, 2002
53
Simulation Evaluation (Cont’d)
• Factors and Levels:
Factor
Levels
TCP
Reno, RBPLW, ECA, ECA+RBPLW, SPM
IP
DropTail, RED, CATNIP-Good, CATNIP-Bad,
CATNIP-RED
• Performance metrics:
 transfer time for each Web page
 packet loss ratio
October 16, 2002
54
Simulation Results for DropTail Routers
Mean and Standard Deviation of Transfer Times
Reno/
RBPLW
Reno
October 16, 2002
ECA
ECA/RBPLW
55
Simulation Results for CATNIP-Good Routers
Mean and Standard Deviation of Transfer Times
Reno/DropTail
SPM/Good
October 16, 2002
56
Observations
r Sources have relatively little control
r IP routers have all the power
r Adding context-awareness at the IP
routers improves both mean and standard
deviation of Web page transfer times
r SPM and CATNIP-Good provide most of
the benefit
r Advantages of CATNIP are most prominent
at low levels of IP packet loss (1-5%)
October 16, 2002
57
Summary
r There seem to be performance advantages
to bending the rules regarding the
Internet protocol stack layered model
r The general notion of “awareness” needs to
explored in a variety of contexts
m
wireless networks, ad hoc routing, TCP/IP,
Web caching, mobile computing,
adaptive applications, …
r Many exciting issues to explore!!
October 16, 2002
58
The Next Steps
r Putting it all together: Web + Wireless
r Wireless Internet Performance Lab (UofC)
r Experimental Laboratory for Internet
Systems and Applications (UofS/UofC,CFI)
r Research Collaborations:
m UofC, UofS, UofA, TRLabs, CS/ECE
m Nortel? HP? Cisco? Agilent? Telus Mobility?
October 16, 2002
59
The End: Question Time!
r For more information:
m Email: [email protected]
m URL: www.cpsc.ucalgary.ca/~carey
r Many thanks to my research team and the
TeleSim Research Group at the U of C
r Special thanks to iCORE, NSERC, CFI,
andTelus Mobility
October 16, 2002
60