Graduate Exam Abstract

Bin Ye

M.S. Final
November 3, 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. <br> <br> 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. <br> <br> 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. <br> <br> 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: