Graduate Exam Abstract

Raghunandan Mandyam Narasiodeyar

M.S. Final
January 31, 2011, 3:00 PM
Engineering B105

Abstract: Packet reordering in Internet has become an unavoidable phenomenon wherein packets get displaced during transmission resulting in out of order packets at the destination. Resequencing buffers are used at the end nodes to recover from packet reordering. This thesis presents analytical estimation methods for “Reorder Density” (RD) and “Reorder Buffer occupancy Density” (RBD) that are metrics of packet reordering, of packet sequences as they traverse through resequencing nodes with limited buffers. During the analysis, a “Lowest First ResequencingAlgorithm” is defined and used in individual nodes to resequence packets back into order. The results areobtained by studying the patterns of sequences as they traversed through resequencing nodes. The estimations of RD and RBD are found to vary for sequences containing different types of packet reordering patterns such as Independent Reordering, Embedded Reordering and Overlapped Reordering. Therefore, multiple estimations in the form of theorems catering to different reordering patterns are presented. The proposed estimation models assist in the allocation of resources across intermediate network elements to mitigate the effect of packet reordering. Theorems to derive RBD from RD when only RD is available,are also presented. Just like the resequencing estimation models, effective RBD for a given RD are also found to vary for different packet reordering patterns, therefore, multiple theorems catering to different patterns are presented. Such RBD estimations would be useful for allocating resources based on certain QoS criteria wherein one of the metrics is RD. Simulations driven by Internet measurement traces and random sequences are used to verify the analytical results. Since high degree of packet reordering is known to affect the quality of applications using TCP and UDP on the Internet, this study has broad applicability in the area of mobile communication and networks.

Adviser: Dr. Anura. P. Jayasumana
Co-Adviser: N/A
Non-ECE Member: Dr. Yashwant. K. Malaiya, CS
Member 3: Dr. Sudeep Pasricha, ECE
Addional Members: N/A,N/A


Program of Study:
CS 530
ECE 450
ECE 451
ECE 554
ECE 658
GRAD 510
ECE 699
MGT 668