טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentSprintson Alexander
SubjectScalable Methods for Provisioning and Restoration of QoS
Paths and Trees
DepartmentDepartment of Electrical Engineering
Supervisor Professor Ariel Orda


Abstract

The thesis provides efficient and scalable solutions for provisioning and restoration problems with Quality of Service (QoS) requirements. The general provisioning problem is to identify a suitable routing topology, that is, a path for unicast and a tree for multicast. The general restoration problem is to identify a suitable restoration topology, that is, a set of restoration paths (or trees), each protecting a component of the routing topology. Both routing and restoration topologies must satisfy certain QoS constraints, such as delay or jitter, and have minimal cost in terms of resource consumption.


The desired scalability is achieved in two ways. First, we establish algorithmic solutions whose performance is considerably less dependent on the network size than that of previous proposals. Second, in order to further enhance scalability, we employ a precomputation approach. The key idea of this approach is to effectively reduce the time required to identify a solution by performing a certain amount of computations in advance, i.e., prior to the request’s arrival.


We consider two models, which capture most practical settings of communication networks. In the first model, referred to as the basic model, each link can provide a certain QoS guarantee at a certain cost. In the second model, referred to as the extended model, each link can provide several levels of QoS guarantees at different costs. More specifically, each link is associated with a cost function that assigns a cost to each QoS value supported by the link, such that link cost is higher for tighter QoS guarantees.


This thesis makes the following contributions. First, we establish precomputation schemes for provisioning of QoS paths. Next, we investigate the general path restoration problem, focusing on additive QoS guarantees such as delay or jitter. In particular, we introduce the notion of “adjusted delay”, which allows existing path algorithms to be adapted in order to efficiently identify suitable restoration topologies.  Next, we investigate the fundamental problem of identifying trees that satisfy additive QoS constraints at minimum cost. Finally, we consider the extended network model and investigate the problem of optimal allocation of network resources along the selected topology, such that the required QoS can be guaranteed at minimum cost.  For all problems considered we provide efficient and scalable solutions, whose performance is proven through rigorous analysis.