Resource allocation in computer networks: Fundamental principles and practical strategies

Fairness in the allocation of resources in a network shared among multiple flows of traffic is an intuitively desirable property with many practical benefits. Fairness in traffic management can improve the isolation between traffic streams, offer a more predictable performance, eliminate certain kinds of transient bottlenecks and may serve as a critical component of a strategy to achieve certain guaranteed services such as delay bounds and minimum bandwidths. Fairness in bandwidth allocation over a shared link has been extensively researched over the last decade. However, as flows of traffic traverse the computer network, they share not only bandwidth resources, but also multiple other types of resources such as processor, buffer, and power in mobile systems. If the network is not fair in allocating any of the shared resources, denial of service attacks based on an excessive use of this resource becomes possible. Therefore, the desired eventual goal is overall fairness in the use of all the resources in the network.; This dissertation is concerned with achieving fairness in the joint allocation of multiple heterogeneous resources. We consider resources as either prioritized (such as bandwidth and buffer resources) or essential (such as processing and bandwidth resources). For each type of these systems, we present a simple but powerful general principle for defining fairness in such systems based on any of the classic notions of fairness such as max-min fairness, proportional fairness and utility max-min fairness defined for a single resource. Using max-min fairness as an example, we apply the principles to a system with a shared buffer and a shared link, and a system with a shared processor and a shared link, and propose practical and provably fair algorithms for the joint allocation of buffer and bandwidth resources, and the joint allocation of processing and bandwidth resources. We demonstrate the fairness achieved by our algorithms through simulation results using both synthetic traffic and real traffic traces. The principles and the algorithms detailed in this dissertation may also be applied in a variety of other contexts involving resource sharing.