Overview

People

Publications

Sponsors

To support Quality of Service (QoS) in the Next Generation Internet, new algorithms are needed for many network components, such as routing, scheduling and admission control. QoS routing, which identifies paths that have sufficient resources to satisfy the QoS requirement of a connection and selects a path for that connection, is one of the most important components for QoS provision. Although many QoS routing algorithms have been proposed, a number of theoretical and practical issues remain to be addressed to achieve efficient QoS routing in large scale networks, that is, scalable QoS routing. This research will attempt to address the following issues.

• Network topology aggregation. For a large network, a common approach to achieve scalable routing is to reduce the size of global network state by aggregating information according to the hierarchical structure of the network. This approach has been adopted by the ATM private network-network interface (PNNI) standard. However, when multiple QoS metrics are involved, precisely aggregating information of a domain may not be feasible since it requires memory space that grows exponentially with respect to the size of the domain. In this research, we design various topology aggregation schemes, study the trade-offs of the schemes between the amount of space needed and the effectiveness in summarizing the domain information, investigate the QoS routing performance with different topology aggregation schemes, and determine the topology aggregation schemes that are effective in practice for QoS routing with multiple QoS metrics.
• QoS routing in the presence of imprecise global network state information. In large scale networks, maintaining precise global state information requires link states to be distributed frequently, which results in large protocol overheads along multiple dimensions including bandwidth, storage, update processing, and the associated context switching. To control the protocol overhead, the link state update frequency may be reduced, which results in the imprecise global state information. The imprecision caused by the infrequent link state updates is random in the sense that a router cannot estimate the accurate global network state. Thus, a practical QoS routing algorithm must be able to perform effective routing using the imprecise global network state information. In this research, we investigate routing schemes that perform effective routing in the presence of imprecise global state information.
• Interaction between resource reservation and QoS routing. Most current QoS routing algorithms assume a separate protocol to perform resource reservation. However, in the future large scale high speed networks, it is desirable to combine resource reservation with QoS routing. Combining resource reservation with QoS routing may have negative impacts on the routing performance, especially for large networks. This research will try to understand the impact of resource reservation on various QoS routing schemes and develop techniques to achieve effective routing in the presence of resource reservation traffic.
• Multi-constrained QoS routing and generic QoS routing algorithms. Multi-constrained QoS routing finds a path that satisfies multiple independent QoS constraints. This problem is NP-hard. However, distributed applications such as the Internet phone and distributed games have very diverse QoS requirements on delay, cost, delay jitter, loss ratio, bandwidth, etc. To support such applications, practical multi-constrained QoS routing algorithms must be developed. Furthermore, due to the complexity of multi-constrained QoS routing, existing QoS routing algorithms are very restrictive on the types and the number of QoS constraints, which implies that different QoS routing algorithms will be needed for different applications. In the future networks, it is desirable to use a generic QoS routing algorithm that can efficiently handle different QoS requirements. In this research, we will study the heuristic algorithms that solve the multi-constrained routing problem effectively in practice and develop a generic algorithm that performs well regardless of the number and the types of QoS requirements.

People