Ph.D Thesis

Ph.D StudentNaaman Nir
SubjectScheduling and Packing Problems in Centralized Access
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROFESSOR EMERITUS Raphael Rom


The thesis provides analysis of different problems related to scheduling in access networks such as data over cable, Broadband Wireless Access (BWA), satellite, and Passive Optical Networks (PON). The general problem we consider is that of scheduling flows with different Quality of Service (QoS) requirements over a slotted TDMA channel. We first analyze the problem of scheduling real-time traffic. Real-time flows, such as those used by multimedia applications, have QoS requirements that include bandwidth, delay and delay jitter. The scheduler should construct an efficient schedule while  maintaining the QoS requirements of every admitted flow. The analysis we present covers scheduling on both a single channel and multiple channels. We then analyze the problem of scheduling non real-time traffic in the presence of real-time flows. Since real-time packets have higher priority, non real-time packets must be scheduled between allocations reserved for real-time packets. In such a setting the scheduling problem has several unique attributes such as the capability to fragment packets, or modify the location of real-time packets in a constrained manner.

When analyzing these scheduling problems we found that they can be transformed into new, as yet unstudied, variants of the bin packing problem. We develop new, bin packing based, scheduling algorithms focusing on low complexity algorithms that can be used in fast communication networks. The performance of the scheduling algorithms we propose is investigated through competitive analysis of both the worst case and the average case. The thesis contains contributions to the fields of both scheduling and bin packing. We present a new approach of analyzing scheduling problems and introduce novel analysis techniques.