In this work we study two fundamental job scheduling problems arising in network systems.;We first consider networks with aggregated links, that is networks in which physical link segments between two connected devices are grouped into a single logical link. A collaborative use of multiple links scales the bandwidth between the two devices, provides load balancing and improves system's fault-tolerance. It also presents new design challenges. One of these challenges is designing appropriate scheduling mechanisms to eliminate packet reordering which increases with parallelism of the system. Reordering of packets is undesirable, as it may negatively influence the performance of transmission protocols.;The goal of scheduling algorithms, apart from eliminating the reordering, is also to provide high quality service to the users. This quality may be measured in many ways and in this work we concentrate on optimizing the maximum flow time of the schedule which is defined as the maximum time a packet spends in device queue.;We also consider scheduling of network packets under overload conditions, i.e., when the traffic exceeds the capacity of a link. We focus on a model called buffer management with bounded delay, for which we give the first known online algorithm that is better than 2-competitive.
展开▼
