טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentLorenz Dean H.
SubjectQoS Routing and Partitioning in Networks with Per-Link
Performance-Dependent Costs
DepartmentDepartment of Electrical Engineering
Supervisor Professor Ariel Orda


Abstract

We study problems related to supporting unicast and multicast connections with Quality-of-Service (QoS) requirements. We investigate the problem of optimal routing and resource allocation for end-to-end QoS requirements in the context of per-link performance-dependent costs. In this context, each network element can offer a variety of QoS guarantees, and is associated with a cost function that increases with the severity of the performance guarantee. The goal is to find the optimal route and to partition the end-to-end QoS into local requirements along the route, such that the connection’s QoS constraints are satisfied and the overall cost is minimized.

This framework is a natural extension to the commonly used bi-criteria model, where each link is associated with a delay-cost pair. It is simple, yet strong enough to model many practical interesting networking problems. The per-link costs may represent different aspects, such as price, cost of resources, revenue loss due to blocking, or even parameter uncertainty.

We study several problems under our framework, with different connection settings (e.g., multicast, multiple-connections) and different QoS constraints (e.g., heterogeneous, all-to-all). As we show, these problems are NP-hard for general cost functions; therefore, we establish pseudo-polynomial exact solutions and fully-polynomial-approximation-schemes (FPASs). We provide exact polynomial-time algorithms for certain types of cost functions (e.g., weakly-convex) and faster algorithms for specific functions. Our algorithms can be used in a dynamic context, and can be implemented in a distributed fashion.

In summary, we present a new, more expressive QoS framework, and tools to solve fundamental networking problems under it.