Survivability and quality of service issues in high-speed networks.

摘要

High-speed networks have been widely deployed to provide high bandwidth and low latency for various central or distributed real-time applications. The growing use of the communication networks in both the public and private sector has led to an increased focus on reliability and survivability. With the popularity of the Internet, a variety of network failures has surfaced in the recent years. It is clear that fault tolerant schemes will grow in importance for the foreseeable future. Meanwhile, with increasing widespread use of applications such as multimedia with stringent performance requirements, there is a need to engineer networks and to design services in which quality of service (QoS) guarantees can be made to individual users.;Therefore, two key issues should be taken into consideration when provisioning connections in high-speed networks. First, survivability should be provided for the network connections. When any physical failure happens, protection and restoration schemes should be provided to guarantee that the affected connections will be fully recovered efficiently. Second, quality of service guarantee for the connections should be considered. With the quality of service guarantee, the provided connections can transmit the signal, consequently the carried information, correctly and effectively.;In the first part of the dissertation, the survivability issue in high-speed networks is studied. Using the redundant trees recovery scheme, several fast algorithms are presented to construct the redundant trees for single link failure recovery in 2-edge connected networks and for single node failure recovery in 2-connected networks with quality of protection and quality of service considerations. The second part focuses on the connection provisioning problem in translucent WDM networks under multiple signal quality constraints. With the consideration of multiple optical signal constraints, both the dynamic and the static connection provisioning problems are studied. Using a novel graph transformation scheme and a careful edge cost assignment strategy, an optimal solution for the dynamic active path provisioning problem is presented. The survivable connection provisioning problems, both for the dynamic case and for the static case, are also addressed in this part. The third part studies a fundamental problem in quality of service routing, multi-constrained path (MCP) problem where one seeks a path that satisfy multiple QoS constraints, such as cost and delay. Both the decision version and an optimization version of the multi-constrained path problem are studied. For the optimization version of the MCP problem (OMCP), first a simple greedy algorithm is presented for computing an approximate solution. Then the greedy algorithm is extended to an exact algorithm for the DMCP problem. For the decision version of the MCP (DMCP) problem, a scheme named necessary condition check is presented to improve the efficiency of finding a feasible solution. Based on the proposed scheme, a framework is presented for solving the DMCP problem.