Multichannel bandwidth allocation in a broadband packet switch

The problem of bandwidth allocation in a packet switch supporting broadband services is addressed. To reduce the performance constraints imposed by limiting a data link to a single broadband packet channel, the author introduces the concept of channel group as a set of broadband packet channels that is viewed as a single data-link connection by routing entities. He uses a two-step bandwidth allocation scheme. At connection setup time, a call is allocated to a channel group. At transmission time, specific channels of a group are optimally allocated to the packets destined to the group. Because of the statistical smoothing of the large number of sources served by a channel group, the traffic performance of the switch is improved. This scheme also allows super-rate switching, i.e., the support of services with peak bandwidth exceeding the capacity of a single packet channel. The author shows the feasibility of this scheme in a Batcher-banyan switch, by implementing in hardware the bandwidth allocation at transmission time. Performance improvements obtained by this scheme are also provided in different traffic environments     

Resource allocation in communication networks using abstraction and constraint satisfaction

The fundamental issue of quality-of-service (QoS) routing has triggered a lot of research during the last few years. However, the proposed algorithms attempt to route communication demands only on a call by call basis, without taking into account future traffic. There are nonetheless cases where the traffic profile is known. In this paper, we address this related problem to QoS routing, more specifically, the off-line planning of bandwidth allocation to demands known in advance. Shortest-path routing is the traditional technique applied to this problem. However, this can lead to poor network utilization and even congestion. We show how an abstraction technique combined with systematic search algorithms and heuristics derived from artificial intelligence make it possible to solve this problem more efficiently and in much tighter networks, in terms of bandwidth usage. In addition, this abstraction technique also allows to explain during search why some allocation problems are indeed infeasible. Then, the network regions between which bandwidth must be added are then identified.     

Modelling and analysis of routing and resource allocation techniques in multi‐service networks

In this paper a novel call level model based on the extension of the classical Erlang multi‐rate model for broadband integrated services networks is proposed. We use the model to study routing strategies in multi‐service networks where service classes with/without QoS guarantees coexist. Examples for such networks include ATM and IP‐based integrated networks. In ATM, the CBR and VBR service classes provide QoS guarantees, while the ABR and UBR service classes are of the best effort type. In IP, traditional TCP/IP traffic is of the best effort type, while new protocols like the RSVP or the differentiated services with central resource handling attempt to support QoS parameters. The coexistence of guaranteed and best effort traffic gives rise to new challenging problems since for a given elastic (best effort) connection the bottleneck link determines the available bandwidth and thereby puts constraints on the bandwidth at the other links along the connection's path. Since the available bandwidth fluctuates in time following the load on the links, routing and link allocation in this environment together with blocking probability calculations and fairness issues need to be studied. By means of our proposed model we are able to conduct a survey of various routing and link allocation techniques as well as to develop a modified shortest path routing algorithm which, according to the numerical examples, performs well in this environment. Copyright © 1999 John Wiley & Sons, Ltd.     

Cost-Effective Deployment of Bandwidth Partitioning in Broadband Networks

We consider the issue of bandwidth partitioning in a multi-rate broadband network. Requests for a number of different types of connection are offered to the network. For the purposes of connection admission and resource allocation, we assume that it is possible to allocate an effective bandwidth to a single connection of each type. The network manager has the problem of implementing an admission control scheme to maximise the profit earned from the network. Our focus here is the extent to which it is a good idea to partition the bandwidth on the physical links to form reserved end-to-end logical links corresponding to the origin–destination pairs. It is clear that implementation of such partitioning will lead to a loss of multiplexing opportunities. However, in a network with end-to-end logical links, costs related to overhead such as route selection, admission control and signalling may be much reduced. This effect may outweigh the loss of revenue due to missing out on multiplexing opportunities. We investigate the nature of this trade-off, by designing optimal or near-optimal partitioned networks using efficient algorithms for finding routes and allocating bandwidth to end-to-end logical links on a fixed underlying physical network. We then calculate the net rate of earning profit under each of the schemes as a function of the ratio of overhead costs to call revenue. Our conclusion is that it is cost-effective to partition bandwidth under a variety of realistic assumptions about revenue rates and overhead costs.     

A Novel Probability-Based Handoff Strategy for Multimedia LEO Satellite Communications

A novel bandwidth allocation strategy and a connection admission control technique arc proposed to improve the utilization of network resource and provide the network with better quality of service （QoS） guarantees in multimedia low earth orbit （LEO） satellite networks. Our connection admission control scheme, we call the probability based dynamic channel reservation strategy （PDR）, dynamically reserves bandwidth for real-time services based on their handoff probability. And the reserved bandwidth for real-time handoff connection can also be used by new connections under a certain probability determined by the mobility characteristics and bandwidth usage of the system. Simulation results show that our scheme not only lowers the call dropping probability （CDP） for Class I real-time service but also maintains the call blocking probability （CBP） to certain degree. Consequently, the scheme can offer very low CDP for rcal-time connections while keeping resource utilization high.     

A Bidding Algorithm for Optimized Utility-Based Resource Allocation in Ad Hoc Networks

This article proposes a scheme for bandwidth allocation in wireless ad hoc networks. The quality of service (QoS) levels for each end-to-end flow are expressed using resource-utility functions, and our algorithms aim to maximize aggregated utility. The shared channel is modeled as bandwidth resources defined by maximal cliques of mutual interfering links. We propose an entirely novel resource allocation algorithm that employs auction mechanisms where flows are bidding for resources. The bids depend both on the flow's utility function and the intrinsically derived shadow prices. Then we combine it with a utility-aware on-demand shortest path routing algorithm where shadow prices are used as a natural distance metric. We also show that the problem can be formulated as a linear programming problem. Thus we can compare the performance of our scheme to the centralized optimal LP solution, registering results very close to the optimum. We isolate the performance of the price-based routing and show its advantages in hotspot scenarios, and also propose an asynchronous version that is more feasible for ad hoc environments. Experimental results of a comparison with the state-of-the-art approach based on Kelly's utility maximization framework show that our approach exhibits superior performance for networks with both increased mobility or increased allocation period.     

An End-to-End Bandwidth Allocation Algorithm for Ad Hoc Networks

Bandwidth-guaranteed QoS service in ad hoc networks is a challenging task due to several factors such as the absence of the central control, the dynamic network topology, the hidden terminal problem and the multihop routing property. An end-to-end bandwidth allocation algorithm was proposed in [Lin and Liu, 15] to support the QoS service in ad hoc networks. However, without exploring the global resource information along the route, the performance of that algorithm is quite limited. In addition, it also incurs significant control overhead. We develop a new algorithm for end-to-end bandwidth calculation and assignment in ad hoc networks which utilizes the global resource information along the route to determine the available end-to-end bandwidth. Our method also employs the topology-transparent scheduling technology to reduce the control overhead. The proposed algorithm can be efficiently utilized in a distributed manner. Both theoretical analysis and simulation results show that our end-to-end bandwidth allocation scheme can significantly improve the network capacity compared with the existing method.     

A resource‐tuned QoS multicast routing protocol

This paper presents a novel framework for quality‐of‐service (QoS) multicast routing with resource allocation that represents QoS parameters, jitter delay, and reliability, as functions of adjustable network resources, bandwidth, and buffer, rather than static metrics. The particular functional form of QoS parameters depends on rate‐based service disciplines used in the routers. This allows intelligent tuning of QoS parameters as functions of allocated resources during the multicast tree search process, rather than decoupling the tree search from resource allocation. The proposed framework minimizes the network resource utilization while keeping jitter delay, reliability, and bandwidth bounded. This definition makes the proposed QoS multicast routing with resource allocation problem more general than the classical minimum Steiner tree problem. As an application of our general framework, we formulate the QoS multicast routing with resource allocation problem for a network consisting of generalized processor sharing nodes as a mixed‐integer quadratic program and find the optimal multicast tree with allocated resources to satisfy the QoS constraints. We then present a polynomial‐time greedy heuristic for the QoS multicast routing with resource allocation problem and compare its performance with the optimal solution of the mixed‐integer quadratic program. The simulation results reveal that the proposed heuristic finds near‐optimal QoS multicast trees along with important insights into the interdependency of QoS parameters and resources.     

Design and analysis of a bandwidth management framework forATM-based broadband ISDN

When designing and configuring an ATM-based B-ISDN, it remains difficult to guarantee the quality of service (QoS) for different service classes, while still allowing enough statistical sharing of bandwidth so that the network is efficiently utilized. These two goals are often conflicting. Guaranteeing QoS requires traffic isolation, as well as allocation of enough network resources (e.g., buffer space and bandwidth) to each call. However, statistical bandwidth sharing means the network resources should be occupied on demand, leading to less traffic isolation and minimal resource allocation. The authors address this problem by proposing and evaluating a network-wide bandwidth management framework in which an appropriate compromise between the two conflicting goals is achieved. Specifically, the bandwidth management framework consists of a network model and a network-wide bandwidth allocation and sharing strategy. Implementation issues related to the framework are discussed. For real-time applications the authors obtain maximum queuing delay and queue length, which are important in buffer design and VP (virtual path) routing     

Dynamic routing of restorable bandwidth-guaranteed tunnels using aggregated network resource usage information

The paper presents new algorithms for dynamic routing of restorable bandwidth-guaranteed paths. We assume that connections are requested one-by-one and there is no prior knowledge of future arrivals. In order to guarantee restorability an alternate link (node) disjoint backup (restoration) path has to be determined, as well as an active path, when the connection is initiated. This joint on-line routing problem is particularly important in optical networks and in MPLS networks for dynamic provisioning of bandwidth-guaranteed or wavelength paths. A simple solution is to find two disjoint paths, but this results in excessive resource usage. Backup path bandwidth usage can be reduced by judicious sharing of backup paths amongst certain active paths while still maintaining restorability. The best sharing performance is achieved if the routing of every path in progress in the network is known to the routing algorithm at the time of a new path setup. We give a new integer programming formulation for this problem. Complete path routing knowledge is a reasonable assumption for a centralized routing algorithm, but is not often desirable, particularly when distributed routing is preferred. We show that a suitably developed algorithm which uses only aggregated information, and not per-path information, is able to perform almost as well as one using complete information. Disseminating this aggregate information is feasible using proposed traffic engineering extensions to routing protocols. We formulate the dynamic restorable bandwidth routing problem in this aggregate information scenario and develop efficient routing algorithms. The performance of our algorithm is close to the complete information bound.     

Connection splitting: an efficient way of reducing call blocking inATM

In this paper, we propose a technique for reducing asynchronous transfer mode (ATM) call blocking which is achieved by splitting wide-band connections into multiple low-bandwidth subconnections and routing them independently through the network. The essence of the mechanism is to use fragmented network bandwidth for supporting calls which are otherwise blocked by conventional routing. ATM bandwidth fragmentation may take place in a situation when a connection occupies a part of a link bandwidth and the rest of it is not sufficient for another connection. The unused bandwidth becomes fragmented. We provide a detailed cell-level design for the split-scheduling algorithms, which use a special type of ATM resource management cell for maintaining cell ordering. The analysis and simulation of the scheduling algorithms show that connection splitting is capable of delivering acceptable cell-level quality of service to multiple traffic classes. We also deliver a solution for implementing splitting without requiring any protocol changes within the network. We show that it is sufficient to modify the data and control plane protocols only within the end stations. Finally, a set of routing-level simulations for splitting demonstrates that splitting can reduce blocking by up to 45% for high-bandwidth calls in a moderately loaded network. Considering that it does not incur any network expenses or protocol changes, we propose splitting as an efficient means for reducing connection blocking     

Novel schemes for traffic engineering in access domains

In this paper, our approach to tackling the problem of traffic engineering in access domains is discussed. The complete solution would take into account bandwidth management, allocation, de‐allocation, protection and restoration. In this work, we focus on one part of the problem, i.e. constrained routing in the MPLS access domains. We define all categories of traffic in an access domain and use CF (conjunction factor) as a figure of merit for performance evaluation of constrained routing schemes and present algorithms that control and limit CF value. The results of conducting simulations using various constrained routing algorithms are presented and conclusions are outlined. Copyright © 2006 John Wiley & Sons, Ltd.     

Routing, wavelength and time-slot-assignment algorithms for wavelength-routed optical WDM/TDM networks

This paper studies the connection-assignment problem for a time-division-multiplexed (TDM) wavelength-routed (WR) optical wavelength-division-multiplexing (WDM) network. In a conventional WR network, an entire wavelength is assigned to a given connection (or session). This can lead to lower channel utilization when individual sessions do not need the entire channel bandwidth. This paper considers a TDM-based approach to reduce this inefficiency, where multiple connections are multiplexed onto each wavelength channel. The resultant network is a TDM-based WR network (TWRN), where the wavelength bandwidth is partitioned into fixed-length time slots organized as a fixed-length frame. Provisioning a connection in such a network involves determining a time-slot assignment, in addition to the route and wavelength. This problem is defined as the routing, wavelength, and time-slot-assignment (RWTA) problem. In this paper, we present a family of RWTA algorithms and study the resulting blocking performance. For routing, we use the existing shortest path routing algorithm with a new link cost function called least resistance weight (LRW) function, which incorporates wavelength-utilization information. For wavelength assignment, we employ the existing least loaded (LL) wavelength selection; and for time-slot allocation, we present the LL time-slot (LLT) algorithm with different variations. Simulation-based analyses are used to compare the proposed TDM architecture to traditional WR networks, both with and without wavelength conversion. The objective is to compare the benefits of TDM and wavelength conversion, relative to WR networks, towards improving performance. The results show that the use of TDM provides substantial gains, especially for multifiber networks.     

Queue-aware uplink bandwidth allocation and rate control for polling service in IEEE 802.16 broadband wireless networks

IEEE 802.16 standard defines the air interface specifications for broadband access in wireless metropolitan area networks. Although the medium access control signaling has been well-defined in the IEEE 802.16 specifications, resource management and scheduling, which are crucial components to guarantee quality of service performances, still remain as open issues. In this paper, we propose adaptive queue-aware uplink bandwidth allocation and rate control mechanisms in a subscriber station for polling service in IEEE 802.16 broadband wireless networks. While the bandwidth allocation mechanism adaptively allocates bandwidth for polling service in the presence of higher priority unsolicited grant service, the rate control mechanism dynamically limits the transmission rate for the connections under polling service. Both of these schemes exploit the queue status information to guarantee the desired quality of service (QoS) performance for polling service. We present a queuing analytical framework to analyze the proposed resource management model from which various performance measures for polling service in both steady and transient states can be obtained. We also analyze the performance of best-effort service in the presence of unsolicited grant service and polling service. The proposed analytical model would be useful for performance evaluation and engineering of radio resource management alternatives in a subscriber station so that the desired quality of service performances for polling service can be achieved. Analytical results are validated by simulations and typical numerical results are presented.     

Energy-Efficient Routing for Connection-Oriented Traffic in Wireless Ad-Hoc Networks

We address the problem of routing connection-oriented traffic in wireless ad-hoc networks with energy efficiency. We outline the trade-offs that arise by the flexibility of wireless nodes to transmit at different power levels and define a framework for formulating the problem of session routing from the perspective of energy expenditure. A set of heuristics are developed for determining end-to-end unicast paths with sufficient bandwidth and transceiver resources, in which nodes use local information in order to select their transmission power and bandwidth allocation. We propose a set of metrics that associate each link transmission with a cost and consider both the cases of plentiful and limited bandwidth resources, the latter jointly with a set of channel allocation algorithms. Performance is measured through call blocking probability and average energy consumption and our detailed simulation model is used to evaluate the algorithms for a variety of networks.     

An overview of quality of service routing for next-generationhigh-speed networks: problems and solutions

The upcoming gigabit-per-second high-speed networks are expected to support a wide range of communication-intensive real-time multimedia applications. The requirement for timely delivery of digitized audio-visual information raises new challenges for next-generation integrated services broadband networks. One of the key issues is QoS routing. It selects network routes with sufficient resources for the requested QoS parameters. The goal of routing solutions is twofold: (1) satisfying the QoS requirements for every admitted connection, and (2) achieving global efficiency in resource utilization. Many unicast/multicast QoS routing algorithms have been published, and they work with a variety of QoS requirements and resource constraints. Overall, they can be partitioned into three broad classes: (1) source routing, (2) distributed routing, and (3) hierarchical routing algorithms. We give an overview of the QoS routing problem as well as the existing solutions. We present the strengths and weaknesses of different routing strategies, and outline the challenges. We also discuss the basic algorithms in each class, classify and compare them, and point out possible future directions in the QoS routing area     

QoS routing in ad hoc wireless networks

The emergence of nomadic applications have generated much interest in wireless network infrastructures that support real-time communications. We propose a bandwidth routing protocol for quality-of-service (QoS) support in a multihop mobile network. The QoS routing feature is important for a mobile network to interconnect wired networks with QoS support (e.g., ATM, Internet, etc.). The QoS routing protocol can also work in a stand-alone multihop mobile network for real-time applications. This QoS routing protocol contains end-to-end bandwidth calculation and bandwidth allocation. Under such a routing protocol, the source (or the ATM gateway) is informed of the bandwidth and QoS available to any destination in the mobile network. This knowledge enables the establishment of QoS connections within the mobile network and the efficient support of real-time applications. In addition, it enables more efficient call admission control. In the case of ATM interconnection, the bandwidth information can be used to carry out intelligent handoff between ATM gateways and/or to extend the ATM virtual circuit (VC) service to the mobile network with possible renegotiation of QoS parameters at the gateway. We examine the system performance in various QoS traffic flows and mobility environments via simulation. Simulation results suggest distinct performance advantages of our protocol that calculates the bandwidth information. It is particularly useful in call admission control. Furthermore, “standby” routing enhances the performance in the mobile environment. Simulation experiments show this improvement     

Dynamic allocation of resources to virtual path agents

One of the major problems faced in operating large networks is the enormous amount of processing and communications overhead required for setting up and tearing down the large number of connections maintained by the network. ATM and MPLS aim at solving these problems via the Virtual Path (VP) mechanism which is used to group together the connections. When a need for setting up a connection rises, the request and its resource allocation are processed by the VP agent and not by the network, thus reducing the processing cost significantly. An important question in the design of these networks is the amount of network resources to be dynamically allocated to and held by the VP agents; too high allocation will result with bandwidth resource waste, while too low allocation will result with heavy connection set-up and tear-down processing load. In this paper we deal with this problem, and at deriving simple operational rules to determine the amount of bandwidth resources to be held by the various VP agents, while balancing between bandwidth waste and connection processing overhead. We formulate the resource allocation problem by accounting both for bandwidth utilization and for connection processing constraints. Recognizing the complexity of the problem, we use a decomposition approach in which we first analyze the single link problem and then propose to use this solution as a building block in constructing algorithms for the whole network. For the single link problem we realize that the pure problem is too complex and thus formulate an approximate model and derive the optimal allocation for it. The optimal rule is expressed as a closed-form square-root allocation. Extensive numerical examination shows that the rule proposed yields very efficient allocations. For the full network problem, we propose to capitalize on the closed form structure of the single link problem solution and use it in devising algorithms for the whole network.     

Network resource management for enterprise wide multimedia services

The support of broadband multimedia applications over an enterprise network poses a broad range of networking challenges for efficient resource management, intelligent switching, and access control for distributed information. We propose two server-based scheduling algorithms, with low computational complexity, to guarantee multimedia information synchronization at the destination, with minimum presentation delays and buffer requirements. We outline a communication framework, highlighting the issues and challenges faced by today's enterprise networks to support multimedia services. We describe the proposed connection establishment and resource allocation schemes in resource-constrained enterprise networks. The objective is to manage the limited resources of the network for maximum utilization. Towards this end we present a dynamic capacity allocation scheme to support connections for multiple users. Specifically, we show that the channel capacity allocation problem can be formulated as a quadratic programming problem. This allocation scheme is implemented at each intermediate switch to dynamically determine the capacity allocation. The effects of interswitch rate mismatch and network delay offset scheduling have also been incorporated in the management framework. In addition, we introduce the concept of route selection based on the requested network quality of service