Ad hoc networks are self-configuring networks of mobile nodes, connected by wireless links. If a destination node is beyond the transmission range of an origin node, then the nodes must cooperate to provide a multi-hop route. Any node can act as a sender, receiver or transit node. It is in a node's interest to be a sender or receiver, but it is less clear what the value is of forwarding traffic on behalf of other nodes. The nodes should therefore be given incentives to act as transit nodes, because otherwise the network would fail to function. A way to do so is by introducing for each node a credit balance, where nodes use credits to pay for the costs of sending their own traffic, and earn credits by forwarding traffic from other nodes.

Optimal bandwidth utilisation together with resilience and recovery from failure are two key drivers for traffic engineering (TE) which have been widely addressed by the IP community. Most current IGP routing protocols deployed in the Internet and the extensions proposed to adapt these protocols for TE are concerned either with optimality or with resilience. This leads to a duplication of routing protocols and algorithms where each of these objectives (optimality, resilience) is addressed by its own protocol or algorithm. The interactions among these protocols introduce additional complexities which do not necessarily translate into equivalent performance gains. This paper aims at the integration of these two objectives into a unified network resource controller. At random time instants the NRC computes bandwidth prices which are used in an automated scheme to dynamically adjust the bandwidths of the network paths in response to the traffic and network equipment conditions. The distinguishing features of the NRC are that it works without centralised control and thus scales to large networks, and that rather than using TE to move network flows to where the network bandwidth is located, the NRC uses network engineering (NE) to move network bandwidth to where the network flows are located. We next present an efficient heuristic to find diversely routed backup paths and to provision the network links with the least amount of backup (spare) bandwidth in order to be able to deploy equivalent recovery paths for any failure scenario which leaves the network connected. Simulation results are presented which show that the reallocation scheme provides prompt bandwidth provisioning both for random traffic fluctuations during normal operating conditions, and when provisioning recovery routes in the event of network failure.

Flow-based routing algorithms using a priori knowledge of the ingress-egress pairs to reduce LSP rejection in MPLS networks have recently been proposed as improvements to the destination-based routing model currently deployed in the Internet. These traffic-aware algorithms incur additional complexity which does not necessarily translate into equivalent performance gains. This paper presents a new routing scheme referred to as least interference optimization (LIO) where the online routing process uses the current bandwidth availability and the traffic flow distribution to achieve traffic engineering in IP networks. A least interference optimization algorithm (LIOA) is presented which reduces the interference among competing flows by balancing the number and quantity of flows carried by a link to achieve efficient routing of MPLS bandwidth-guaranteed LSPs. Initial simulation results show that LIOA performs better than several well known routing algorithms such as the minimum hop algorithm (MHA), open shortest path first (OSPF), constraint shortest path first (CSPF) and minimum interference routing algorithm (MIRA) in terms of several performance parameters including the LSP rejection upon congestion, the successful re-routing of LSPs upon single link failure and the ease of implementation.

Presents an efficient algorithm to compute an optimal service-separated virtual path connection network (VPCN) consisting of several logical subnetworks, one for each service class. The algorithm implements a bandwidth market where each VPC computes the prices at which it is willing to buy and sell bandwidth. These prices determine the allocation of bandwidth to virtual path connections (VPCs) in a series of transactions. After each transaction, the VPCN is adjusted, bandwidth supplies and prices are adjusted, and the algorithm computes the next bandwidth transaction. We apply our algorithm and another method to design an optimal service-separated VPCN for a small network consisting of 10 nodes and two service classes. Both methods yield near-identical revenues, though our algorithm requires a fraction of the computational resources required by the other method. We next apply our algorithm to compute optimal service-separated VPCNs for two larger networks of 20 and 55 nodes, each with six service classes.

Modern communication networks can cross connect traffic flows to form logical end-to-end connections between all origin-destination pairs and thus create fully meshed logical networks upon sparse physical networks. Such logical connections are known as virtual path connections (VPCs) and a logical network formed by VPCs is known as a VPC network (VPCN). We present an efficient algorithm called XFG to compute optimal configurations for VPCNs carrying multiservice traffic. We compare the features of the XFG algorithm and the characteristics of standard nonlinear programming solvers. We present a model where a sequence of busy period multiservice traffic is offered to a network. The XFG algorithm is used to compute an optimal VPCN design for each busy period. We compare the grade of service attained by VPCN redesign, dynamic alternative routing (DAR), and a combination of VPCN redesign, call queueing and DAR.

A Multiclass Queueing Network model (MQN) is partitioned into a set of disjoint subnetworks. Population constraints are applied to each subnetwork such that within each subnetwork each population chain is either subject to an individual population constraint, or a group of chains may be subject to a common (shared) population constraint. Such population constraints are necessary in order to model multiprogramming level constraints in mainframe computer systems and window flow control mechanisms in computer communication networks. A computationally efficient approximate solution method is developed for solving MQN's with population constraints. Each subnetwork is reduced to a single approximately flow equivalent composite centre by assuming that the effect of other chains on a given chain can be adequately represented by their average customer populations. The accuracy of the population constraint approximation is compared against previous techniques by applying it to a set of test cases for which simulation solutions have previously been reported. The accuracy of the approximation technique is found to be good and in general is an improvement over previously published concurrency constraint approximations.

The Lineariser is an MVA-based technique developed for the approximate solution of large multiclass product form queueing networks. The Lineariser is capable of computing accurate solutions for networks of fixed rate centres. However, problems arise when the Lineariser is applied to networks containing centres with queue dependent service rates. Thus networks exist which seem well suited (a large number of lightly loaded centres, large numbers of customers in each closed chain) for Lineariser solution but whose queue dependent centres cannot be solved accurately by the Lineariser method. Examples have also been found where the Lineariser computes accurate values for the queue lengths, waiting times and throughputs though the values computed for the queue length distributions are totally in error.

A Mean Value Analysis (MVA) approximation is presented for computing the average performance measures of closed-, open-, and mixed-type multiclass queuing networks containing Preemptive Resume (PR) and nonpreemptive Head-Of-Line (HOL) priority service centers.The approximation has essentially the same storage and computational requirements as MVA, thus allowing computationally efficient solutions of large priority queuing networks.The accuracy of the MVA approximation is systematically investigated and presented.It is shown that the approximation can compute the average performance measures of priority networks to within an accuracy of 5 percent for a large range of network parameter values.Accuracy of the method is shown to be superior to that of Sevcik's shadow approximation.

A Mean Value Analysis (MVA) approximation is presented for computing the average performance measures of closed multiclass queueing networks containing non pre-emptive Head Of Line (HOL) and Pre-empt Resume (PR) priority centers. The approximation has the same storage and computational requirements as MVA thus allowing computationally efficient solutions of large priority queueing networks. The accuracy of the MVA PR approximation is systematically investigated and presented in terms of error contour diagrams. The contour diagrams reveal that the approximation can compute the average performance measures of priority networks to within an accuracy of 5 percent for a large range of network parameter values. Accuracy of the method is also compared to Sevcik's shadow approximation and another MVA approximation recently proposed by Chandy and Lakshmi.

A queuing analysis of a preemptive, priority-driven, time-sliced dispatcher algorithm, typical of those found in many time-sharing systems, is presented. A distinctive feature of the system being modeled is that a preempted task, when readmitted to the dispatcher, is reallocated a full time slice rather than the residual. The combination of preemption, time-slice renewal and class-dependent arrival and service rates places the analysis beyond that of the well-known FBN algorithms. The model is used to predict the behavior of the dispatcher algorithm under various workloads. The model reveals that, at high arrival rates, the time-slice renewal policy prevents processor bound tasks from being relegated to the lower priority queues, thereby severely degrading the throughput of tasks with short processor requirements.

Multiclass queuing network models of multiprogramming computer systems are frequently used to predict the performance of computing systems as a function of user workload and hardware configuration. This paper examines three different methods for incorporating operating system overhead in multiclass queuing network models. The goal of the resultant model is to provide an accurate account of the processing performance and the system CPU overhead of each of the several different types of jobs (batch, timesharing, transaction processing, etc.) that together make up the multiprogramming workload. The first method introduces an operating sysbtm workload consisting of a fixed number of jobs to represent system CPU overhead processing. The second method extends the jobs' CPU service requests to include explicitly the CPU overhead necessary for system processing. The third method employs a communicating set of user and system job classes so that the CPU overhead can be modeled by switching jobs from user to system class whenever they require system CPU service. The capabilities and accuracy of the three methods are assessed and compared against performance and overhead data measured on a Univac 1110 computer.