Transcript Powerpoint presentation

WebTP
A New Transport Architecture
for the Web
Rajarshi Gupta
Wilson So
UCB EECS
Team Members
FACULTY
Venkat Anantharam
Steven McCanne
David Tse
Pravin Varaiya
Jean Walrand
STUDENTS
 Ye Xia
 Wilson So
 Rajarshi Gupta
 Yogesh Bhumralkar
 Jeng Lung
 Richard La
Post Doc
 David Starobinski
Motivation
World Wide Web today is vast and vital
Mostly runs Web transport (http) over TCP
TCP and UDP sub-optimal for many applications
Attempts at incremental improvements
Need a comprehensive solution, without trying to
“fit in” with TCP/HTTP
Web Applications important enough to motivate
new cross-layer architecture
WebTP is the answer ?
WebTP Project Work Items
 User utility characterization
 WebTP architecture and protocol
(motivation & design)
 Active research areas
WebTP Project Work Items
 User utility characterization
 WebTP architecture and protocol
(motivation & design)
 Active research areas
Conceptual View
interaction
Server
Network
Document
Resources
Client
Display
Satisfaction
User Rules
Utility
Function
S = f (D , C , N , U)
S = User Satisfaction
D = Document Descriptor
C = Client Set of Rules
N = Observed Network State
U = Utility Function
Document
D
Client
Rules
C
Document
D’
Network
State
User
Preferences
Satisfaction
Utility Function
U
Measure of utility generated by the
objects on the page
 O[ j ].size
T (i) 
S   O[i].value.1T (i)  O[i].delay
R
i
M
j 1
i 1
M
S   O[i].value.1T (i)  B(i)
i 1
B(i )     O[ j ].browse

Simple additive form, or more complicated
Utility depends on Arrival, Browse Time
Experimental work to characterize utility
i 1
j 1
WebTP Transfer
Given
a set of objects to transfer
current network state
We find an Optimal Transfer Schedule
Optimal order of transfer
Optimal subset of objects (dynamic programming)
Universal delay constraint
Browse time constraint
Optimal ?
Maximizes user utility
Experimental Setup
Sample page (CNN
Digest)
 www.path.berkeley.edu/~guptar/
SAMPLE/index.html
WebTP
Normal
Quantitative metric for
comparison of utilities
Comparison of transfers
in terms of utilities
WebTP vs Normal Web Transfer (example)
WebTP Project Work Items
 User utility characterization
 WebTP Architecture & Protocol
(motivation & design)
 Active research areas of WebTP
WebTP Design Philosophy
Consider the web
browsing process as a
whole.
Bring the user into
the loop of decision.
USER
APP
PROTOCOL
NETWORK
Today’s Focus: Transport
Requirements of the
transport protocol
Overview of WebTP
transport architecture
USER
APP
PROTOCOL
(TRANSPORT)
NETWORK
Assumptions
For Today’s discussions, we assume:
Network provides best-effort service only
Optimize at end-hosts, not within the network
Design a new transport, but leave the network
layer (IP) intact
Transport Requirements
Scenario #1:
browsing a static web
page composed of
text, graphics, and
pictures.
What are the
requirements of the
transport layer
imposed by this
application?
Transport Requirements
Application specify
the download order
of different objects
Allow progressive
delivery of objects
(e.g. progressive
JPEGs)
Send data in small
chunks (a paragraph
or 1 scan of an img)
3
1
2
Transport Requirements
Scenario #2:
User browses through
supplementary
information while
watching a video
stream
Transport Requirements
Allow user/application
to decide how to
allocate the available
bandwidth to
different connections
Notify application of
the currently available
bandwidth
28.8 Kbps
leftover
Transport Requirements
Summary
Data should be transferred in small
chunks that can be processed & displayed
independently (Application Data Units)
App specifies transfer order of ADUs
within a connection and bandwidth
allocation among different connections
Transport informs each app of how much
bandwidth it gets; each app decides how
to best use it
Transport Requirements
from RUTS BOF ‘98
Quoted from Requirements of Unicast Transport
Sessions (RUTS) BOF from Orlando IETF, Dec
1998:
Quick connection establishments
Application Level Framing
Congestion control
App control over reliability
TCP Slow-start/slow restart hit for interactive traffic
Preliminary Design
App 1
Connections
Pipe
(to IP A)
App 2
Connections
Pipe
(to IP B)
Preliminary Design
ADUs: each object is composed of ADUs
Connections: light-weight objects
corresponding to an application-level
conversation. Should be able to open one
connection per object transfer.
Pipes: one pipe per destination; multiple
connections to the same destination (IP) are
muxed onto a single pipe.
Why Separate Connections
and Pipes?
Connections
low overhead: app
can open as many
connections as it
wants
allow fine-grained
reliability control on a
per ADU basis
allow app-controlled
bandwidth allocation
Pipes
Integrated Congestion
Management
Architecture proposed
by Hari Balakrishnan
et al.
allow connections to
cooperate to find out
the available
bandwidth
WebTP Architecture
•ADU fragmentation &
reassembly
•Reliability Control
•Flow Control
Connection
Management
•Min buffering in WebTP
•Mux/Demux packets
•Bandwidth allocation
Bandwidth
Management
•Loss detection/Ack
•Congestion control
•Network monitoring
Congestion
Management
WebTP Protocol Example
1. Server listens on a well-known port
2. Client opens a new connection
3. Client side transport opens a new
pipe because none exists yet
4. Client side initiates 3-way handshake
5. Handshake finishes, client sends ADU
6. Client opens another connection to
the same server
7. The existing pipe is reused
WebTP Packet Header
0
1
2
3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
Packet number
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
Acknowledgment number
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
Acknowledged Amount
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
ADU number
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
Segment Number
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
WebTP Transport Header
|
Source Port
|U|A|R|S|F|R|E|F|
|
|R|C|S|Y|I|E|N|A|
|
|G|K|T|N|N|L|D|S|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
Destination Port
| C |
|
|
| L |
RES |
|
| A |
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Data |
|
|
| Offset| RES |
Window
|
|
|
|
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
Checksum
|
Options
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
Options
|
Padding
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
data
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
WebTP Project Work Items
 User utility characterization
 WebTP architecture and protocol
(motivation & design)
 Active research areas
ACK Scheme
•Some ADUs are
reliable; some are not
•Lost packets of reliable
ADUs should be
retransmitted
automatically
•But all pkts are
muxed onto the same
pipe
•Problem: Cumulative
ACKs doesn’t work!
Ack Scheme
1
2
3
4
5
6
 TCP style cum-ack doesn’t work for reliable/unreliable
mix!!
 Assume 1,2 belongs to reliable ADU X; 3,4 belongs to
unreliable ADU Y; 5,6 belongs to reliable ADU Z
 Packet 3 & 4 are lost
 Receiver doesn’t know if 3,4 are unreliable, so it can
only ack 2 upon receiving 5 and 6 using Cum-Ack
Ack Scheme
 Solution #1: Use separate sequence number spaces for reliable and
unreliable packets.
Use cumulative acks for reliable packets
Use selective acks to ack the last consecutive run of unreliable
pkts received
1
2
3
4
5
6
E.g. ack sequence (1,1) , (1,2), (5,5), (5,6)
Disadv: 2 logically separate ack stream => can’t easily infer loss
from another ack stream
 Solution #2: Use a bit vector to selective ack both reliable and
unreliable packets
 Disadv: high speed long haul links => long vector (large window)
Fast WebTP
SYN
SYN-ACK
RTT Pipe setup
delay
ACK
Data
For interactive traffic, pipe setup delay can be
annoying. Can we get rid of the 3-way
handshake for setting up a pipe?
Yes, BUT we might get duplicate data from
previous incarnation of a pipe.
Fast WebTP
If application can detect duplicate ADUs, or if
duplicate ADUs doesn’t do any harm, 3-way
handshake is redundant!
E.g. Duplicate HTTP requests for static objects
doesn’t adversely affect the client or the server.
Problem: how to seamlessly integrate the
regular WebTP(w/ handshake) and Fast
WebTP(w/o handshake) protocol?
Fast WebTP Example
Client
1. Client sends
FAST ADU
Server
(accepts Fast
WebTP)
SYN+data
SYN-ACK
3. Sends ACK
ACK
Data-ACK
6. Sends more new
data
Data
2(a). Data delivered to app;
continues handshake
2(b). App chooses to
accept data
4. Handshake finishes
5. Acks data
Fast WebTP Example
Client
1. Client sends
FAST ADU
Server
(rejects Fast
WebTP)
SYN+data
SYN-ACK
3. Sends ACK
ACK
2(a). Data delivered to app;
continues handshake
2(b). App chooses to
REJECT data
4. Handshake finishes
5. Don’t ACK data
(or explicitly reject)
6. Ack timeout;
Resend 1st ADU
Data
Traffic Classification
Web-related traffic can be roughly classified as
one of the following categories:
Interactive: bursty traffic, delay sensitive
Bulk: high volume traffic, delay insensitive, reliable
Realtime streams: multimedia streams, extremely
sensitive to delay and jitter, tolerate loss
Buffered streams: multimedia streams playback,
less delay sensitive, tolerate loss
Bandwidth Allocation
Long-term bandwidth allocation is
dependent on user’s specification of rates.
APIs are available for querying available
rate, current rate, and for setting
preferred rate.
Short-term bandwidth assignment is
dependent on traffic classes.
Bandwidth Allocation and
Window Size
Connections
Pipe
TCP-style congestion control gives us a time
varying congestion window size per pipe
How do we allocate this window among
different connections of different classes?
Flexible Software Arch.
How to build a
flexible software
framework so we
can easily
experiment with
different kinds of
control algorithms in
our transport
protocol?
Connection
Management
Bandwidth
Management
Congestion
Management
Conclusion
Most important idea: allow user
preferences to determine how to best use
the available bandwidth
Look at the web browsing process as a
whole, design a transport protocol that
caters to the needs of the user/application
Leads to the design of connections muxed
on top of pipes
Conclusion
Although muxing isn’t entirely novel, the
explicit separation of congestion and
reliability control is.
Decision to allow flexible reliability control
on a per ADU basis and the addition of
Fast WebTP introduce many new
challenging research problems
The need to experiment w/ different algs
requires a flexible software framework