Walter Scott, Jr. College of Engineering

Graduate Exam Abstract

Bin Ye
M.S. Final
Nov 03, 2006, 1:00pm-3:00pm
Forestry 107
Measurement and Evaluation of Packet Reordering over the Internet
Abstract: Packet reordering has been shown to be an ever increasing phenomenon on the
Internet and therefore will have an increased impact on performance of
applications. The increase in reordering is mainly due to the rise in
processing parallelism within switches and link level parallelism in networks.
Packet reordering, if unchecked, can have a significant degrading effect on
the performance of Internet applications whether they are based on TCP or UDP.
At the same time, the resources required to handle reordering could grow
dramatically. Therefore, an understanding of the nature of packet reordering
and its variation is crucial for the characterization and accurate prediction
of the end-to-end network performance.
Driven by the need for observing packet reordering in the Internet over long
time periods, this work proposes several singleton packets reordering metrics
derived from reorder density (RD) to monitor and capture the long term
variation of packet reordering. These singleton reordering metrics are:
percentage of late packets, percentage of early packets, mean displacement of
packets, mean displacement of late packets, mean displacement of early packets
and reorder entropy. Each of these singleton metrics captures the nature of
packet reordering from a certain angle. The daily and weekly measurements on 6
paths over Internet were performed over 336 hours, and the results analyzed.
Some paths show clear weekly and daily trends in the amount of reordering,
while others show no such trends. The data sets have also been made available
to the Internet research community.
To further analyze the reordering over the Internet quantitatively, an
end-to-end connection is treated as a cascade of subnets. The convolution
based relationship between the constituent subnet reorder responses and the
end-to-end reorder response is verified for end-to-end paths over the
Internet. Reorder properties of a cascade of n similar subnets (CNSS) are
evaluated. A general expression for RD of CNSS is developed and an estimate
for reorder entropy is derived. A comparison based on simulation and
theoretical calculations indicates that the estimate is reasonable.
The relationship between the end-to-end delay, the inter packet gap and packet
reordering is investigated via simulation. The simulations show that higher
standard deviation of end-to-end packet delay results in a higher level of
packet reordering. For the same packet delay distribution, the level of packet
reordering decreases with the increase in Inter Packet Gap.
Adviser: Professor Anura P. Jayasumana
Non-ECE Member: Professor Daniel Massey (CS department)
Member 3: Professor Anura P. Jayasumana (ECE)
Addional Members:
Program of Study: