Challenges to network
heterogeneously broughtby wireless
Katsushi Kobayashi
ikob@acm.org

Outline•••

Exposing Network Properties Underlying Paths•

i-Path: Network Transparency•

End-point Adaptation

Network architecture to support various Latency
Requirements•

Architecture•

SchedulerConclusion
4•

NICT/Japan Funded Project 2008-2011“i-Path: Network Transparency Project”•

NSF-NICT Joint Project 2010 - 2012
“Accommodating Network Evolution and Heterogeneity by Improving
Network Transparency” NSF #1032226•

Japanese personnel:
Prof. Shigeki Goto, Waseda Univ.
Katsushi Kobayashi, AIST
Ichiro Murase, Waseda Univ., MRI
Akihiro Shimoda, Waseda Univ.
Dai Mochinaga, MRI•USA personnel:
Prof. Srinivasan Seshan, CMU
Athula Balachandran, CMU
Dongsu Han, CMU

3

Transparency inside Internet
No visibility mechanism, i.e., end-to-endprinciple•

Transport stack ”estimates” inside network.

••••

Bandwidth difference from 54Kbps to 10Gbps.
Frequently changing network condition in mobile.
Corruption loss in wireless is not negligible.

P2P peer selection, CDN server selection.

••

Not to mitigate traffic demand for backbone.

Unable to inspect provisioned path••Just acknowledgement from control plane
5

Network paradigms: Who should besmart ?
•Internet: Dumb minimal network with smart terminal, i.e., e2e.

•Telephone: Smart network with dumb terminal•

QoS provisioning: smarter network with Internet
end expects network to do something••

i-Path is another network paradigms, network exposes inside.
end asks what network can do•➡ Router has rich information•

300K+ prefixes and its attributes, link BW, link utilization, corruption,congestion, MAC states, calendar clock, location, temperature, i/fdescription, CPU load, operator’s contact, configuration, feature set....
6

i-Path: component•Router•

End system•

Disclosure policy

7i-Path: Router•

Expose network information•

In-band cross-layer designed for transport•

Jack up approach with shim layer middle of IP and transport•••

ETEN: focuses on satellite
PTP: Header growth with prepending data at each router hop
Congestion control with more network support•XCP, TCP-QS, RCP, ...

SIRENS: one packet collects one router’s data8

i-Path: End System
Application specifies what,System
whereHostinfo.
is expected.

Application• Application accesses info

with socket API:
•Socket i/f
Operating Systemsetsockopt(),getsockopt()

TCP

SIRENS

NIC

IP

MAC

Device Driver

BUS

BW utilization, length ofqueue, corrupted loss

CPU + memory• what: link BW, geolocation,• where: TTL range

9i-Path: Disclosure Policy•

Follow disclosure policies among ends, and ISPs., e.g.
•

User does not want to show privacy sensitive info. as geo. location•ISP does not want to show infrastructure info.

end-to-end Internet

Disclose Everything

Alice

ISP policy
Alice

ISPBob
ISP policy

Bob10

Selective Disclosure•

Policy:•••Alice & Bob allow to disclose
beyond 3rd hop routers.

Implementation:•

Alice does not send req. forneighbor & next neighborrouters, i.e.,1st & 2nd hop.

•Bob does not send back res.
as Alice, i.e., 6th & 7th hop.

Result:•Alice obtains 3-5 hops’ data.

•Bob obtains 3-7 hops’ data11

What i-Path brings for ?
•Enhancing transport performance•

Optimal peer/server selection in P2P/CDN•

Offer optimal rate encoding in VoD service•

Better service with geographical location•Region control in contents distribution using
node location•

Input your ideas !
12

i-Path:visualize link capacities

TTL=60TTL=64

TTL=61TTL=62TTL=6315

i-Path: Geo-trace

14

i-Path: Current status
Implementation:•

i-Path router and end-system

•••

•
•

FreeBSD/MacOS X/Linux(incl. Android)
Windows : postponed

http://i-path.goto.info.waseda.ac.jp/trac/i-Path/
Socket API C, C++, Python, Java (JNI)

Deployment:••

6 routers in JGN2+, 12 in Lab.

13

Outline•••

Exposing Network Properties Underlying Paths•

i-Path:Network Transparency•

End-point Adaptation

Network architecture to support various Latency
Requirements•Architecture•

SchedulerConclusion
4

TCP Variants•••

TCP proposals for …
•TCP for wireless / mobile•

TCP for data centers•

TCP for high delay-BW product paths•

TCP for small latency

Solutions either…
•Assume that are working only in target environment•

Are limited in their techniques because of generality/backward
compatibility

i-Path can provide information of underlying paths, TCP stack isable to optimize behavior not with estimations.
22Streaming Video•••

Rate adaptation•

Need to choose encoding rate•

Adapt quickly to changes in fair-share of network bandwidth•

End-point based probing tends to be error-prone and high overhead

Reliability•

Not enough time to perform ARQ-based loss recovery•

FEC-based schemes often incur high overhead•

i-Path can help identify router support

Scaling•

Multicast and overlays are complex
17

Outline•••

Exposing Network Properties Underlying Paths•

i-Path•End-point Adaptation

Network architecture to support various Latency
Requirements•

Architecture•

SchedulerConclusion4Latency requirements fromapplications•

HFT (High Frequency Trading)Competing < μs•

Data Center
Tight job deadlines for interactive services•VoIP
150ms one-way delay (ITU-T G-114)

Dedicated / Provisioned•

e-Commerce< 4s rule for keeping customer attention•

On-line games> 50ms latency makes significant eﬀects in FPS•

Interactive Web services

Best Eﬀort

Latency in detail
Cause of latency in case of VoIP* :1. Processing (Coder)• Variable delays arise from queuing delays in the egress trunk buffers on the serial port connected to
2. Packetization3.

the WAN. These buffers create variable delays, called jitter, across the network. Variable delays areSerialization
handled through the de−jitter buffer at the receiving router/gateway. The de−jitter buffer is describedin the De−jitter Delay (”n) section of this document.

4. Queueing / Buffering
5.

Figure 5−1 identifies all the fixed and variable delay sources in the network. Each source is described in detail
NetworkSwitching (Propagation + Switching)in this document.

6. De-jitter
Figure 5−1: Delay Sources(Processing)
DelayCISCO, CoderUnderstanding
Delay inPacket Voice Networks,
http://www.cisco.com/c/en/us/support/docs/voice/voice-quality/5125-delay-details.html
Coder delay is the time *CISCO
taken by the: digital
signal processorDelay(DSP) toincompressof PCM
samples. ThisUnderstanding
Packeta block
VoiceNetworks

Simple best-effort•

Major and primary traffic on InternetPros: Minimal technical and economic demands
Cons: No-QoS, congestion control required, DDoSrisk•

Can achieve rough “flow-Rate fairness” by TCP
congestion control•Packet loss as a congestion signal•

End systems reactions to packet losses

S. Floyd and M. Allman, “Comments on the Usefulness of Simple Best-Eﬀort Traﬃc”, RFC5290

“Flow-rate fairness” andlatency support simultaneously•

Should work :•with neither per-flow state (IntServ),
more than one queue (DiffServ)•

without admission control for inter-ISP deployment.

•

coexisting with existing best-effort•

incremental deployability•

with minimum modifications

LAWIN : Architecture andProtocol•

Applications specify per-packet latency-limit
according their requirements••

e.g. IP option, flow label

Routers schedule packets with taking
advantages of per-packet indications•Latency-aware scheduler to replace FCFS/DropTailOutline•••

Exposing Network Properties Underlying Paths•

i-Path•End-point Adaptation

Network architecture to support various LatencyRequirements•

Architecture•

SchedulerConclusion
4

Earliest Deadline First (EDF)with reneging••

EDFR is a latency aware scheduler better thansimple EDF•

EDF is blocked by elapsed data•

EDFR drops packets if elapsed their deadlines

Similar property to FCFS in terms of packet loss rate•

EDFR imposes fair loss-rate to all flows
regardless of their deadline requirements as FCFS•

Loss-rates rely on average deadline, and is same
as corresponding capacity’s FCFS

Loss property ofEDFR scheduler•

Steep Cliffs : can beavoidable•

Corresponds block rates whena new arrival deadline is toosmall

1e−01
1e−02

Loss-rates rely on averagedeadline, and is same ascorresponding capacity’s FCFS

1e−03

•

Fair loss-rate to all flows
regardless of their deadline
requirements as FCFS

10EDF w Reneging, M/M/1
ρ = 0.98, D:U(1,B), U(5,B)
1030503050100100150
D = 200, U(5,B)

150
D = 200, U(1,B)

System total by Theory*≈ (1-ρ)/(1-ρ^(N+1))ρ^N
Blocking rate in M/M/1/N

1e−04

•

1e+00

Flat Bottoms : similar toFCFSFraction of Renege•0100

200300400Deadline*L. Kruk,J. Lehoczky,K. Ramanan,and S. Shreve. “Heavy traffic analysis for EDF queues with reneging”, The Annals of Applied
Probability, 21(2):484–545, 2011

EDF with Reneging Later arrivals (EDFRL)- Preliminary EDFRL provides loss-rate bias with deadline

Can be realized just to replace priority queue sub-scheduler in EDFR byFCFS•

On managed networks :To provide higher priority to shorter deadlines replacing FCFS with LCFS

100

0100

200
Latency limit(A) EDFR

30040030

D = 200

50
100

1e−04

1e−04

1e−04

D = 200

150

1e−02

50

Fraction of drop

150

30
1e−02

100

Fraction of drop

50

1e−02

30

1e+00

•

1e+00

On best-effort networks :To impose higher loss to shorter DL; incentive for applications to choose
longer

1e+00•

Fraction of drop

•0100

200

300

400

Latency limit(B) EDFRL(slot width = 1)

0100200

150

D = 200300400Latency limit(C) EDFRL(slot width = 10)

Figure 2: Fraction of drop dependency on latency limit on EDFR and EDFRL with M/M/1.

Calendar Queue*•O(1) scheduler, if dequeue from only top of bin•

Event Simulator (NS2)•Packet pacing / Traffic shaper

2132
1015
12112625
23

38
3634

0

1

23 ……..

13Tn bins

Calendar Queue*Brown, Randy. "Calendar queues: a fast 0 (1) priority queue implementation for the simulation event set problem."Communications of the ACM 31.10 (1988): 1220-1227.Outline•••

Exposing Network Properties Underlying Paths•i-Path•End-point Adaptation

Network architecture to support various Latency
Requirements•Architecture•

SchedulerConclusion
4

Conclusion•

Exposing Network Properties Underlying Paths•

Network architecture to support various Latency
Requirements4