Quality of service routing and traffic regulation for distributed multimedia systems

In this research, we focus on three main challenges in multimedia networks: network modeling, traffic smoothing, and QoS routing with resource allocation. We start by proposing a low-level network model called the jitter graph model, which captures the dynamic QoS characteristics of a data network while preserving the topological information necessary for routing. The proposed model captures the QoS characteristics as functions or regions, rather than static numerical values and incorporates the interrelationships between the different QoS parameters and the allocated resources. The second research task is to design a lossless, light-weight, flexible, service-discipline-independent traffic reshaping regulator, which we call the Initial Delay Regulator (IDR). The objective of the IDR is to smooth out the burstiness of the traffic inside the network without relying on per-packet tagging. The third research task is to address the problems of QoS routing and resource allocation. The jitter graph model allows combining the problems of QoS routing and resource allocation in a single framework. We start by re-defining the problem of resource allocation on a given path. The objective is to satisfy the QoS requirement along this path. Then we define the problem of QoS routing with resource allocation. The new definition incorporates QoS routing and resource allocation in the same framework and allows trading off different QoS parameters. We propose a dynamic programming algorithm that, under certain conditions, finds a network route between a source and destination nodes and decides the amount of resources needed along the path so that the QoS requirements are satisfied. After proving the correctness of the proposed algorithm, we present a worst-case analysis of jitter and droppage under insufficient resources conditions for some of the well known service disciplines. The analysis provides deterministic relations between the QoS parameters and the resources for networks that employ these service disciplines. Having this analysis, we apply the formulation of the problem of QoS routing with resource allocation and the proposed algorithm dynamic programming algorithm to networks that employ these service disciplines to solve the problem of QoS routing with resource allocation in polynomial time