In this paper, we consider an integrated service system, providing multirate guaranteed services and homogeneous best-effort services. The total system capacity is shared by both service types, while the guaranteed service customers are treated as high priority and are allocated fixed data rate bandwidth units. The best-effort service customers are supported by the remaining capacity leftover by the guaranteed services, in a processor-sharing manner. Admission control on the best-effort service customers is adopted to provide a certain level of quality of service (not guaranteed) to avoid the effect of repeated attempts. The best-effort customer blocking probability is an important metric for network dimensioning. In this integrated service system, we observe that the blocking probability of the best-effort customers is not insensitive to the shapes of their flow-size distributions and the guaranteed customers' holding-time distributions. We obtain here by light computation, for the best-effort customers, blocking probability bounds, and approximations, which possess the insensitivity property. Considering that the distributions for customers' holding times and flow sizes may be unknown, the proposed insensitive bounds and approximations will facilitate system design and network dimensioning with predictable and acceptable performance.

We study the problem of stochastic job assignment in a server farm comprising multiple processor-sharing servers with various speeds and finite buffer sizes. We consider two types of assignment policies: without jockeying, where an arriving job is assigned only once to an available server, and with jockeying, where a job may be reassigned at any time. We also require that the underlying Markov process under each policy is insensitive. Namely, the stationary distribution of the number of jobs in the system is independent of the job size distribution except for its mean. For the case without jockeying, we derive two insensitive heuristic policies: One aims at maximizing job throughput, and the other trades off job throughput for energy efficiency. For the case with jockeying, we formulate the optimal assignment problem as a semi-Markov decision process and derive optimal policies with respect to various optimization criteria. We further derive two simple insensitive heuristic policies with jockeying: One maximizes job throughput, and the other aims at maximizing energy efficiency. Numerical examples demonstrate that, under a wide range of system parameters, the latter policy performs very close to the optimal policy. Numerical examples also demonstrate energy/throughput tradeoffs for the various policies and, in the case with jockeying, they show a potential of substantial energy savings relative to a policy that optimizes throughput.

Distributed Coordinate Functions (DCF) is the mandatory medium access method for IEEE 802.11 Wireless Local Area Networks (WLANs), which is designed for infrastructure WLANs where all end users connect with Access Point (AP) with single-hop links. DCF doubles its Contention Window (CW) before each retransmission. However, in multi-hops WLANs, a node may encounter different kinds of transmission failures from different transmission directions. In this paper, we will point out that, in some situations doubling CW before retransmitting makes DCF exploit the medium inefficiently. We also propose a method to resolve this problem by employing different backoff mechanisms for different transmission directions. NS-2 simulations demonstrate a significant throughput improvement of our enhanced MAC over the native MAC.

The major objective of an admission control in wireless mesh networks is to prevent excessive real-time traffic from over-utilizing the bandwidth resources. A key component of an admission control is an accurate estimator of the bandwidth available at each node and of the actual bandwidth (including the MAC overhead) required by a new flow. This estimation problem is particularly difficult when node localization information is not available. We propose a novel admission control based on active neighbor bandwidth reservation (AC-ANBR), by which active neighbors periodically broadcast bandwidth reservation information and flow setup requests carry their bandwidth reservation states. Our proposed AC-ANBR accurately estimates the available bandwidth at each node, as well as the bandwidth required by each new flow. The effectiveness of AC-ANBR in multi-hop wireless networks is demonstrated by NS-2 simulations.

To enable ubiquitous end-to-end quality of service over IP networks expanding to rural areas, we examine resource allocation problems of a MAC layer for an OFDM MIMO wireless base station (BS) using multiuser beamforming. We compare two linear beamforming techniques, zero-forcing (ZF-BF) and minimum mean square error (MMSE-BF). To guarantee minimum bandwidth and low packet delay in an environment where the number of users is much larger than the number of BS antennas, one needs to partition the users into several sets and combine space division multiple access (SDMA) with time division multiple access (TDMA). We study the impact on the optimal transmission power resulting from selecting the following design parameters: (i) ZF-BF vs. MMSE-BF; (ii) the number of user sets multiplexed by TDMA; and (iii) the number of BS antennas. Two notable results are observed: (1) power wise, ZF-BF is far more superior to MMSE-ZF; (2) substantial power can be saved by increasing the number of BS antennas; however, only by large increments, e.g., from 6 to 9 and further to 21.

There is growing evidence that a new generation of potentially high-revenue applications are emerging that can benefit from widespread multicast support in large IP networks. These applications, such as streaming video and interactive games, have inherent quality of service (QoS) requirements. Current methods of QoS provisioning have either scalability concerns or cannot guarantee end-to-end delay with acceptable packet loss unless bandwidth is over-provisioned. While low jitter guarantee is sufficient for streaming applications, maximum end-to-end delay is also required for interactive games. Previously, we presented a new holistic architecture for end-to-end QoS guarantee for unicast flows only in the core network based on several novel combined rate and end-to-end delay control algorithms. We also demonstrated the viability of this architecture and its advantage over Differentiated Services by implementing it in edge and core routers and monitoring the rate, end-to-end delay and packet loss of all flows in a six-node core network with long delay links. Here, we extend the architecture to include multicast flows and demonstrate that network operators can tune the architectural configuration parameters so as to fairly share the excess bandwidth between multicast and unicast flows.

Growing demand for streaming, voice and interactive gaming applications emphasize the importance of quality of service (QoS) provisioning in the Internet, particularly the need for maximum end-to-end delay guarantee. Current methods of QoS provisioning have either scalability concerns or cannot guarantee end-to-end delay with acceptable packet loss unless bandwidth is over-provisioned. While low jitter guarantee is required for streaming applications, maximum end-to-end delay is also required for VoIP and interactive games. We propose, analyze the stability and demonstrate the viability of three combined rate and end-to-end delay controls. The stability analysis is done on a fluid network model with greedy flows showing that all controls are globally asymptotically stable without information time lags and one of them is also globally asymptotically stable with arbitrary time lags; however it substantivally under-utilizes the network. Another control, which numerically demonstrates stability with arbitrary time lags, is implemented in edge and core routers of our WAN-in-Lab with long haul links. The prototype implementation confirms its viability and its advantage over the differentiated service architecture. The viability of the two other controls is shown by detailed NS2 packet-based simulations of an eight-node real core network.

A common application of unattended sensor networks (WSN) is low data rate streaming from many scattered sensors to one or more sink nodes. To meet the stringent requirement of prolonged WSN lifetime, we introduce a new notion of statistical reliability for data streaming applications and propose several variants of stop-and-wait hop-by-hop ARQ with explicit and implicit ACKs. The energy-efficiency of the protocols are mathematically analyzed and compared. The analysis reveals that implicit ACKs should be applied with caution to prevent an "avalanche" of implicit ACK transmissions. It is further shown that a simple combined implicit/explicit ACK resolves the "avalanche" problem. Our proposal is further validated by simulation.

There is growing evidence that a new generation of potentially high-revenue applications requiring quality of service (QoS) guarantee are emerging. Current methods of QoS provisioning have scalability concerns and cannot guarantee end-to-end delay. For a theoretical fluid model, we derive four distributed rate and delay controls accounting for their bandwidth and end-to-end delay requirements while also allowing for multiple flow priorities. We show that two of them are globally stable in the presence of arbitrary information time lags and two are globally stable without time lags. The global stability in the presence of time lags of the later two is studied numerically. Under all controls, the stable flow rates attain the end-to-end delay requirements. We also show that by enhancing the network with bandwidth reservation and admission control, minimum rate is also guaranteed by our controls. By guaranteeing end- to-end delays, our controls facilitate router buffer sizing that prevent buffer overflow in the fluid model. The distributed rate- delay combined control algorithms provide a scalable theoretical foundation for a QoS-guarantee control plane in current and in "clean slate" IP networks. To translate the theory into practice, we describe a control plane protocol facilitating our controls in the edge routers. The stability and performance of discrete time versions of our controls are demonstrated numerically in a widely spanned real network topology.

We derive two new energy efficient reliable data transport protocols for overcoming the negative impact of asymmetric radio links in wireless sensor networks. The energy efficiency of these algorithms is explicitly derived using our theoretical model, and validated by results obtained from simulations and field trials. The analytical, simulation and field trials demonstrate that our proposed protocols perform well in networks with asymmetric links and can save energy of up to 27% compared to conventional ARQ schemes.

The paper introduces a new algorithm for rate allocation in a multi-service Internet. The algorithm meets delay requirements of different services and provides fairness and congestion control. A performance comparison with other leading protocols is also carried out.

This paper studies the blocking performance of optical burst switching (OBS) networks using a sequential office control (SOC) state-independent deflection routing policy. We show that unprotected deflection routing may destabilize OBS resulting in higher blocking probabilities than if bursts were not deflected but simply blocked. This study was motivated by the well-known destabilizing effect that alternative routing has on circuit switching in classical telephony networks. We propose two forms of protection to guard against destabilization: 1) wavelength reservation, which is analogous to trunk reservation in circuit switching; and, 2) preemptive priority, which is a new form of protection where bursts that have not been deflected are given preemptive priority over bursts that have been deflected. Our main contribution is a one-moment reduced-load approximation to evaluate the blocking performance of OBS networks using deflection routing protected by either wavelength reservation or preemptive priority. Our reduced-load approximation relies on the usual assumptions of link independence and Poisson distributed link arrivals. We quantify the error admitted in making these two assumptions via simulation. Using our reduced-load approximation, we evaluate the blocking performance of protected and unprotected deflection routing in several randomly generated networks. The chief conclusion of our study is that deflection routing in OBS should be given some form of protection to avoid destabilization resulting from upward load variations, and in terms of blocking performance, preemptive priority is the best form of protection for OBS. We use simulation to verify that our conclusions remain valid for a realistic traffic scenario.

The optimal transmitter power control policy in an interleave division multiple access (IDMA) spread spectrum uplink channel is derived. The policy is applied to an IDMA channel with repetition code and a chip-by-chip maximum-likelihood decoder whose sum-rate is compared to the capacity of a linear minimum mean square error multiuser detector and to the Cover-Wyner capacity

This paper proposes a new optical burst switching (OBS) paradigm known as dynamic two-way reservation OBS (DTWR/OBS), in which the burst length is dynamically determined at an ingress router, according to the minimum length reservation period available on each wavelength channel within a lightpath, from the ingress router to the egress router. The dynamic nature of DTWR/OBS ensures the packet transmission rate is controlled at the ingress routers, based on the level of network congestion. This increases network utilization and eliminates burst blocking due to wavelength contention. An analytical model for a single isolated optical cross-connect (OXC) is derived to determine the waiting time distribution of an arbitrary IP packet at the ingress router using the proposed DTWR/OBS. The accuracy of the analytical model is confirmed by simulations.

We consider a simple model for distributed video on demand (VoD) systems. The model is analyzed by the Erlang fixed point (EFP) approximation and by a new method referred to as overflow priority classification (OPC). The OPC method imposes a preemptive priority regime in a non-priority system to capture the traffic load dependence among VoD servers. Comparison between OPC and EFP reveals that OPC is more accurate. The comparison is made with respect to two quality of service (QoS) measures, the loss probability and the probability that a video request is not served by the preferred VoD server given that it is not lost.

An asymptotically combined optimal transmission power and rate control policy is derived for a DS-CDMA time varying fading channel with multiple user classes, random spreading codes and a linear MMSE multiuser detector. The rigorous optimization problem is presented as a non-convex constrained program explicitly solved in a closed-form given by a function of a single Lagrangian multiplier. The optimal multiplier is derived by a low number of independent bisection searches for a zero, where each search is done in a single-valued function. The optimal control policy is demonstrated by an application, where the transmission power is adapted to the channel fade variations, and the transmission rates are adapted to the tier in which the mobile is located. The effect of the number of tiers on the optimal transmission rate is presented in an environment with lognormal and Rayleigh fading.

Limited wavelength conversion and deflection routing are considered as viable methods to reduce the burst blocking probability in optical burst switched (OBS) networks. The question of which of the two methods is most effective has yet to be resolved. In this paper, an analytical model is derived that provides an accurate and quick means to evaluate and compare the effectiveness of limited wavelength conversion and deflection routing. First, an overflow load fixed point approximation model is derived for a single link in isolation. Then the single link model is integrated into a reduced load fixed point approximation model for a general network topology with deflection routing. The accuracy of the analytical model is verified through simulation.

We derive two types of optimal uplink transmission power control in synchronous and asynchronous CDMA time varying fading channel with multiple user classes, random spreading sequences and MMSE multiuser detector. One optimal policy minimizes the outage probability subject to maximum average power budget and maximum transmission power constraints. The other minimizes the average power budget subject to maximum outage probability and maximum transmission power constraints. We show that for a system with a large number of users and a proportionally large processing gain, both optimal policies are threshold cut-off policies. We express the policies explicitly and show how to compute their outage probabilities.

Methods to resolve wavelength contention are needed to improve the performance of optical burst switched (OBS) networks. Network simulations and Markovian queuing models for nodes in isolation have suggested that deflection routing (alternate routing) may be a viable method to resolve wavelength contention. However, we show that deflection routing may destabilise OBS networks operating at high loads. To prevent the destabilising effect of deflection routing, we propose and analyse a technique called wavelength reservation to intentionally limit the amount of deflection at high loads. Wavelength reservation is analogous to trunk reservation in circuit switched networks. This paper is the first to present a new reduced load Erlang fixed point analysis of OBS networks with deflection routing and wavelength reservation. We apply the new analysis to evaluate the benefit of deploying deflection routing and wavelength reservation in a sample OBS network.

In this paper we provide an analytical framework for studying the performance of optical burst switching (OBS) networks using burst segmentation. We first consider a single link model to evaluate the blocking probability of OBS using burst segmentation and confirm it by simulation. We use this analysis to demonstrate the benefit of burst segmentation over the well-known just-enough-time (JET) policy for the single link case. We then extend these models to a network scenario using a reduced load fixed point approximation to evaluate blocking probabilities and to show the advantages provided by burst segmentation for OBS networks.

This paper provides a framework for analysis and performance evaluation of Optical Burst Switching (OBS) networks. In particular, a new reduced load fixed point approximation model to evaluate blocking probabilities in OBS networks is introduced. The model is versatile enough to cover known OBS reservation policies such as Just-Enough-Time (JET), Just-In-Time (JIT), Burst Segmentation and Route-dependent Priorities. The accuracy of the model is confirmed by simulation and the various policies are compared.

This paper provides a scalable framework for analysis and performance evaluation of optical burst-switching (OBS) networks. In particular, a new reduced load fixed point approximation model to evaluate blocking probabilities in OBS networks is introduced. The model is versatile enough to cover known OBS reservation policies such as just-enough-time, just-in-time, burst segmentation, and route-dependent priorities. The accuracy of the model is confirmed by simulation and the various policies are compared.

We study the mobile admission control problem in a cellular PCS network where transmitter powers are constrained and controlled by a distributed constrained power control (DCPC) algorithm. Receivers are subject to nonnegligible noise, and the DCPC attempts to bring each receiver's CIR (carrier-to-interference ratio) above a given quality target. Two classes of distributed admission control are considered. One is a noninteractive admission control (N-IAC), where an admission decision is instantaneously made based on the system state. The other is an interactive admission control (IAC), under which the new mobile is permitted to interact with one or more potential channels before a decision is made. The algorithms are evaluated with respect to their execution time and their decision errors. Two types of errors are examined: type I error, where a new mobile is erroneously accepted and results in outage; and type II error, where a new mobile is erroneously rejected and results in blocking. The algorithms in the N-IAC class accept a new mobile if and only if the uplink and the downlink interferences are below certain corresponding thresholds. These algorithms are subject to errors of type I and type II. In the IAC class, we derive a soft and safe (SAS) admission algorithm, which is type I and type II error free, and protects the CIR's of all active links at any moment of time. A fast-SAS version, which is only type I error-free, is proposed for practical implementation, and is evaluated in several case studies.

We study the transmission power control in a cellular network where users' mobility results in a time varying gain matrix. A framework for evaluating the channel quality is specified, and an asymptotic representation of the link gain evolution in time is obtained. Then, a time variant distributed constrained power control (TVPC) which copes with user mobility is derived. The algorithm is compared to a classical distributed constrained power control (DCPC), as well as to a constant-received power control and constant-transmitted power. The comparison reveals that the classical DCPC exhibits an outage probability close to one, unless some counter-measures are taken. The TVPC algorithm however, copes well with users' mobility and provides a close to optimal scale up factor for the signal to interference ratio (SIR) target.

Formulates, analyzes, and compares several connection multiplexing algorithms for a multiplexer residing in the equivalent terminal of the asynchronous transfer mode (ATM) layer at the user premise. The primary goal is to find an algorithm that efficiently combats the cell delay variation (CDV) introduced by the multiplexer. Several performance criteria are examined, one of which is unique to ATM networks. This one is the proportion of arriving cells that do not conform to the traffic contract of the connection. The conformance is being tracked by a generic cell rate algorithm (GCRA) recommended (but not mandatory) by CCITT. Other criteria are the classical buffer requirements and the cell delay. Service fairness among connections is also evaluated with respect to each performance criterion. The impact of the following five multiplexing policies on the performance criteria are evaluated for constant bit rate (CBR) traffic sources. The policies are first in, first out (FIFO), round robin (RR), least time to reach bound (LTRB), most behind expected arrival (MBEA), and golden ratio (GR). Extensive numerical examples reveal that there is no single policy that is best across all criteria. With respect to cell conformance, most behind expected arrival (MBEA) emerges as the preferred one. FIFO is best with respect to cell delay, except for high utilizations where RR dominates. The LTRB is marginally better than all other policies with respect to buffer requirements.

In this paper we study the mobile removal problem in a cellular PCS network where transmitter powers are constrained and controlled by a distributed constrained power control (DCPC) algorithm. Due to transmitter mobility and random signal propagation, there are system states where not all transmitters can be supported, even under the optimal power control. Thus, some of them should be removed. It can be shown that finding the optimal removal set is an NP-complete problem, and therefore gives rise to heuristic algorithms. In this paper we study and compare among three classes of transmitter removal algorithms, one-by-one removals, multiple removals and power control with removals combined. All removal algorithms are compared with respect to their outage probabilities and their time to convergence to a steady state. The power control with removals combined algorithm emerges as the best approach with respect to both criteria.

Consider a switching component in a packet-switching network, where messages from several incoming channels arrive and are routed to appropriate outgoing ports according to a service policy. One requirement in the design of such a system is to determine the buffer storage necessary at the input of each channel and the policy for serving these buffers that will prevent buffer overflow and the corresponding loss of messages. In this paper, a class of buffer service policies, called Least Time to Reach Bound (LTRB), is introduced that guarantees no overflow, and for which the buffer size required at each input channel is independent of the number of channels and their relative speeds. Further, the storage requirement is only twice the maximal length of a message in all cases, and as a consequence the class is shown to be optimal in the sense that any nonoverflowing policy requires at least as much storage as LTRB.

Consider a circuit switched broadband ISDN network that support a variety of traffic classes (e.g., data, voice, video, facsimile), each of which has its own traffic requirement and reward function. We address the problem of dynamically allocating the capacity of each circuit among the traffic classes. As an optimal allocation policy is extremely hard to find, we apply a different methodology by which we bound from above the optimal expected reward, and propose a specific threshold policy-the restricted complete sharing (RCS)-that yields a reward sufficiently close to this bound. The initial parameters of the threshold policy are found with the aid of our bounding technique, and are improved by two iterative procedures. The quality of our policy is demonstrated by several numerical examples.>

A selective-repeat automatic-repeat request (SR ARQ) system model in which packets arrive at the transmitter according to a general renewal process is analyzed. The overall delay of a packet in a system that operates under the SR ARQ protocol consists of the queuing delay at the transmitter and the resequencing delay at the receiver. The joint distribution of the buffer occupancies at the transmitter and at the receiver is derived, and the tow types of delay are compared using numerical examples.>

A multistation packet radio network with m stations and a finite number of nodes n that uses a conflict-free protocol to access the backbone network of stations through a shared channel is discussed. The goal is to derive an allocation of the channel time slots (time-division multiplexing cycle), so that all transmissions will be conflict-free and some measure of performance (e.g., the expected total weighted throughput, the expected weighted holding cost) will be optimized. The methodology that is used is to bound the performance and to allocate the slots according to the golden ratio policy.>

Consider a communication network that regulates retransmissions of erroneous packets by a selective-repeat (SR) automatic repeat request (ARQ) protocol. Packets are assigned consecutive integers, and the transmitter continuously transmits them in order until a negative acknowledgement or a time-out is observed. The receiver, upon receipt of a packet, checks for errors and returns positive/negative acknowledgement (ACK/NACK) accordingly. Only packets for which either NACK or time-out have been observed are retransmitted. Under SR ARQ, the receiver accepts packets that are out of order and must store them temporarily if it has to deliver them in sequence. The resequencing buffer requirements and the resulting packet delay constitute major factors in overall system considerations. The authors derive the distributions of the buffer occupancy and the resequencing delay at the receiver under a heavy traffic situation. This enables the network designer to determine how much buffer capacity at the receiver guarantees certain specified performance measures.>

Consider n transmission stations sharing a single communication channel. Packets arrive at the stations according tonindependent renewal processes, possibly with different rates. The transmitters are assumed to be able to store an unlimited number of packets in their buffers. The stations transmit packets during time slots allocated to them according to a given {\em conflict-free distributed protocol.} The cost criterion according to which protocols are evaluated is the long-run weighted average buffer occupancies. (The average waiting time is a special case of such a weighting.) A lower bound to the cost criterion under time division multiplexing (TDM) protocols is given, and the costs of two protocols are analyzed. The first protocol is the {\em random-control} policy, and the second is the {\em golden ratio} policy which is shown to achieve a cost close to the lower bound for realistic parameters.

Considernexponential transmission channels which transmit information with different rates. Every channel has a buffer which is capable of storing an unlimited number of messages. A new message first arrives at the controller, which immediately routes it to one of the channels according to an infinite deterministic routing sequence. A cost per unit of staying time is charged in each of the channels (channel dependent cost), and the long-run average staying cost is taken as the cost criterion. For everynand a Poisson arrival process, a lower bound to the cost is found and a new routing policy, the golden ratio policy, is presented and its cost is evaluated. It is shown that for a variety of system parameters, the golden ratio routing policy has a cost close to the lower bound.

A computer system is modeled by an exponential queueing network with different classes of customers and a general class of service policies. The mean cost per unit time is taken as the loss function. Three lower bounds of the loss function under the whole class of service policies, as well as an upper bound of the minimal loss, are derived. The loss function is expressed in a convenient form from which we derive a simple heuristic service policy so called "Klimov policy." This policy is applied to several examples of computer systems and is evaluated by the bounds. The examples recommend using "Klimov policy" in any case; so we have a first rule for deciding how to provide service capacity to different customers in a network of queues.

This paper deals with a single server serving N priority classes ( N being finite or infinite) and working under an FB z regime, namely, one in which the waiting line consists of infinitely many separate queues obeying the FIFO rule. Each priority class is assigned to one of the queues. A customer from the k th priority class (“ k -customer”) in the n th queue is eligible for θ n,k time units of service, at the end of which he either departs, because his requirement is satisfied, or joins the tail of the ( n + 1)-th queue. When a quantum of service is completed, the server turns to the first customer in the lowest index (highest priority) nonempty queue. The arrival process of k -customers is assumed to be homogeneous Poisson, and their service requirements are independent, generally distributed, random variable. A set of recursive linear equations is derived for the expected flow time of a k -customer whose service requirement is known, and some examples are discussed and presented graphically. This paper corrects some errors in an earlier paper by the second author.