Transcript realistic traffic shaping in dummynet link emulator

REALISTIC PACKET REORDERING
FOR NETWORK EMULATION AND SIMULATION
Aisha Syed, Robert Ricci
University of Utah
1
Introduction
 Packet

reordering common in real networks
Retransmissions due to loss, multipath forwarding,
load balancing within routers, etc.
 Performance
 Streaming
affected by reordering*
media, VoIP, IPTV, etc
Mashtizadeh ‘14, Narasiodeyar ‘13, Lelarge ’08, Piratla ’08,
Jaiswal ‘07, Laor ‘02, Bennett ‘99
*
2
Introduction

Need reordering for realistic simulation/emulation

Emulating cause won’t result in precise or
repeatable results

Goal is precise, repeatable, controlled reordering

Users may want to test their apps/protocols in high
reordering networks
3
Reorder Density (RD) Metric
 Reorder

Captures reordering by measuring displacements of
packets from original positions
 RD


calculation algorithm
Packet trace  RD
 RD

Density (RD) [Piratla ’05]
sequence regeneration algorithm
RD  Packet trace with reordering applied
Will be used while simulating/emulating reordering
 RD
 Emulator  Reordered packet trace
4
Contributions
 Algorithm
for sequence regeneration from the
RD reordering metric
 Dummynet emulator extension to support
reordering
5

RD calculation example
Send:
1 2 3
Receive:
2 3 1
Displacements
Counts
2
-1
1
2
RD Histogram
6
Sequence Regeneration Algorithm
Displacements
-3
-2
0
1
2
Counts
1
1
1
1
2
4
1
5
2
3
6
Output Sequence
Input RD Histogram
7
Sequence Regeneration Algorithm
 Use
max flow –like approach with additional
components for constraints
1.
Create graph to represent permutations of
displacements in input histogram
1.
Use greedy search with backtracking

Find paths that represents output permutation
8
N = 4 packets
super-source
sub-sources
(# of displacements)
2
Solution:
Displacements Counts
1
2
1
-1
-2
Space complexity
1
1
1
1
3
1
4
2
1
2
• O(numUniqueDisplacements * numPackets)
-1
• numUniqueDisplacements usually
small
-1
-2
-2
Time complexity
• O(numUniqueDisplacements2 * numPackets)
• Worst-case rare in practice
bipartite graphs
supersink
sub-sinks (N)
9
Evaluation
1.
Real Internet traces from the literature
 Algorithm
2.
correctness, and performance on real traces
Synthetic traces
 Algorithm
scalability with respect to amount of reordering
 Algorithm scalability with respect to number of packets
3.
Datapath evaluation
 Evaluated
our Dummynet extension to see if it was causing
any unnecessary overhead
10
1. Real traces

145 hours of TCP traffic consisting of long-lived connections
from Colorado to 6 destinations around the world
Algorithm worked correctly
• Got EXACTLY the same RD
11
2. Synthetic traces

Runtime (sec) on log scale

Effect of amount of reordering on algorithm runtime
Number of packets kept constant (1K)
100
Real traces
10
1
0.1
0.01
0.001
0
10
20
30
40
50
60
70
Percentage of reordering (%)
80
90
100
12
Conclusion
 Contributions


RD sequence regeneration algorithm
Reordering support added in Dummynet
 Evaluated
algorithm correctness and scalability, and
Dummynet extension for any unnecessary overhead

Works correctly and fast enough for realistic traces
Thank You
13
Thank You


Effect of number of packets on algorithm runtime
Amount of reordering kept constant to RD seen on real trace
15
16
Experimenter Workflow
Input
RD(s)
Sequence Regen.
Algorithm
Reorder
config.
Other
optional
config.
Reordering
extension
S
123456…
Delay/bandwidth/loss
emulation
Dummynet
321654…
D
References










[1] Dummynet references from Citeseer. http://citeseerx.ist.psu.edu/viewdoc/
summary?doi=10.1.1.57.2969, 1:401–414, 2013.
[2] Packet reordering trace.
http://www.cnrl.colostate.edu/Projects/PacketReordering/ Trace/packet
reordering trace.htm, pages 401–414, 2013.
[3] T. Banka. Metrics for degree of reordering in packet sequences. Proc. 27th
IEEE Conference on Local Computer Networks, 1:333–342, November 2002.
[4] J. C. R. Bennett. Packet reordering in not pathological network behavior.
IEEE/ACM Trans. Netw., 7:789–798, 1999.
[5] P. E. Black. Fisher-Yates shuffle. Dictionary of Algorithms and Data
Structures [online], US National Institute of Standards and Technology, 2005.
[6] M. Carbone. Dummynet revisited. SIGCOMM Comput. Commun. 2010.
[7] B. Chun. PlanetLab: an overlay testbed for broad-coverage services.
SIGCOMM Comput. Commun. Rev., 33(3):3–12, 2003.
[8] S. Jaiswal. Measurement and classification of out-of-sequence packets in a
tier-1 IP backbone. IEEE/ACM Transactions on Networking (ToN), 2007.
[9] A. P. Jayasumana. Improved packet reordering metrics. RFC 5236, 1:401–
414, June 2008.
[10] M. Laor. The effect of packet reordering in a backbone link on application
through- put. IEEE Network, 16(5):28–36, 2002.
17
References










[11] M. Lelarge. Packet reordering in networks with heavy-tailed delays.
Mathematical Methods of Operations Research, 67(2):341–371, 2008.
[12] A. Morton. Packet reordering metrics. RFC 4737, 1:401–414, November 2006.
[13] A. Morton. Packet reordering metrics. IETF internet-standard: RFC4737, 2006.
[14] V. Paxson. End-to-End Internet packet dynamics. Proc. ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer
Communication, 1:401–414, 1997.
[15] N. M. Piratla. On reorder density and its application to characterization of
packet reordering. Proc. 30th IEEE Local Computer Networks (LCN) Conference,
Sydney, Australia, 1:401–414, November 2005.
[16] N. M. Piratla. Rd: A formal, comprehensive metric for packet reordering. Proc.
IFIP Networking Conference, Ontario, Canada, LNCS 3462:78–79, May 2005.
[17] N. M. Piratla. Reordering of packets due to multipath forwarding – An analysis.
Proc. IEEE International Conference on Communications, 1:401–414, June 2006.
[18] N. M. Piratla. Metrics for packet reordering – A comparative analysis.
International Journal of Communication Systems, 21:99–113, 2008.
[19] J. Sommers. Improving accuracy in end-to-end packet loss measurement.
ACM SIGCOMM Computer Communication Review, 35:157–168, August 2005.
[20] B. White. An integrated experimental environment for distributed systems and
networks. Proc. of the Fifth Symposium on Operating Systems Design and Implementation, Boston, MA, 1:255–270, December 2002.
18
Sequence Regeneration Algorithm
 Sophisticated
algorithm needed because have to solve a
constraint problem

Naïve approach wouldn’t work
 Need
a specific permutation that meets constraints
Displacements
Counts
-3
-2
1
1
0
1
2
1
1
2
Output sequence:
4
1
5
2
3
6
RD Histogram
19

RD generated from Internet
packet trace

145 hours of packet data
from the host in USA to one
in India

Source: Colorado State
University
Displacements
-5
-4
-3
-2
-1
0
1
2
3
4
5
Counts
8
5
10
10
16
136626
32
16
9
5
11
20
Evaluation
 Plan

followed
Take traces
 software



generated and from real datasets
Calculate reordering metrics
Feed those metrics into my implementation
Measure metrics on the resulting stream, and show they
are very close to the ones calculated in Step 2
21
Input file
containing
RD for
emulation
Sequence Regen.
Algorithm
Reordering
config. file
Reordering scheduler
Reordered packet stream
Optional
config. file
for delay,
loss, etc
Delay/bandwidth/loss
emulation
21346578
…
Destination
Dummynet
Source
22
23
Input
RD
Sequence Regen.
Algorithm
Reorder
config.
Other
optional
config.
Reordering
scheduler
S
12345…
Delay/bandwidth/loss
emulation
Dummynet
54321…
D
 Workflow:
Take packet trace -> calculate RD
-> sequence regeneration algorithm
-> feed it to dummynet -> emulation
Input file
containing
RD for
emulation
Sequence Regen.
Algorithm
Reordering
config. file
Reordering scheduler
Reordered packet stream
Optional
config. file
for delay,
loss, etc
Delay/bandwidth/loss
emulation
21346578 …
Destination
Dummynet
Source
24



Destination host in Cape Town
N = ~ 130K
Runtime = ~1s
25
Summary
 Reordering



Prevalent network phenomenon
Increasingly becoming important to pay attention to
Sophisticated metrics needed
 Hence


Important to include as a feature in emulators
Implement support for RD
 Currently
most sophisticated metric available
 Incomplete without sequence regen algorithm
26
Output packets 
Input packets 
Finite queue
representing
router buffer
Scheduler
Pipe representing a
communications link,
has an associated delay
and bandwidth
27
Reorder Density (RD)
• Measures displacements of packets from
their original positions in a sequence
– Considers both early and late packet arrival
– Relatively very comprehensive metric
28