Optimal routing and rate allocation problems in packet networks with QoS support

Abstract

This thesis explores some of the issues that arise in the provisioning of Quality of Service (QoS) guarantees to applications in the Internet. In order to meet the QoS requirements of connections, the Internet needs to be equipped with various QoS mechanisms. A QoS routing mechanism is required to select a suitable unicast path (or a multicast tree) for the packets of a connection. Once a path is selected, a resource allocation mechanism is needed to provide QoS guarantees by allocating resources such as bandwidth and buffer space on the network elements (NEs) along the path of the connection. A scheduling mechanism is also required to schedule the packets of concurrent connections at each link in the network. This thesis studies issues related to some of these mechanisms. The first problem investigated concerns the resource allocation mechanism. We consider the Guaranteed (G) Service class, which is intended for real-time applications with stringent delay requirements, such as certain interactive audio and video applications that use playback buffers and are intolerant of any packets arriving after their playback time. Specifically, the G Service provides a guaranteed level of bandwidth, a firm end-to-end delay bound, and no queuing loss for packets of a compliant data flow admitted into the network. A data flow is required to declare its flow characteristics at the time of connection setup, and only those packets that conform to the declared characteristics are guaranteed the QoS requirements. In this work, we focus on the problem of optimal allocation of rates that guarantee the requirements of a flow. We assume there is no limitation on the reservable buffer space at each NE. A cost function is associated with the allocation of a rate at each hop. The problem is to map the QoS requirements (i.e., throughput and end-to-end delay) of a flow to rates on the links along the path in such a way that the total cost of rate allocation is minimized. The prevalent approach in the literature is based on allocating an identical rate at each hop. However, the Identical Rates policy has the following drawbacks: 1. It does not always minimize the total cost. 2. It does not consider extra available resources while computing the rate. That is, if the rate is not available on some links, it might still be possible to admit the connection by assigning higher rates on the non-bottleneck links. Under this scenario, we devise the General Rates policy for optimal rate allocation. We also investigate, through simulations, the usefulness of the Identical Rates policy and the General Rates policy in a dynamic setting where connections arrive and depart at random. The second problem investigated concerns the QoS routing mechanism. We consider the QoS routing problem in the context of a rate-based multi-class network. In this model, a connection request belongs to one of several pre-specified classes, each characterized by a rate that may depend on route parameters. Upon arrival, a connection requests the establishment of a route between its source and destination such that the required rate is available on this route during the connection holding time. We call this the Routing and Rate Allocation (RRA) problem. On connection arrival, an RRA algorithm selects a path according to some policy and allocates a rate on that path for the duration of the connection. If the RRA algorithm cannot find a suitable path, it blocks the connection request. Many RRA algorithms have been proposed in the literature to improve network performance. However, it is not known whether any of these algorithms extract the best performance from the network, simply because the best possible network performance is not known. In this work, we derive an upper bound on the maximum value of the minimum weighted carried traffic in a rate-based multi-class network. This upper bound can be computed by solving a linear program (LP). We study properties of the upper bound in a useful asymptotic regime, in which the offered load and the link capacities grow in proportion. We devise a Partitioning RRA algorithm that achieves the upper bound under this asymptotic regime, proving that the LP upper bound is asymptotically tight. Though the Partitioning RRA is asymptotically optimal, it performs poorly at low load. Therefore, we devise two improved asymptotically optimal RRA algorithms: the Improved Partitioning RRA, and the Hybrid RRA.