We consider dynamic routing and power allocation for a wireless network with time-varying channels. The network consists of power constrained nodes that transmit over wireless links with adaptive transmission rates. Packets randomly enter the system at each node and wait in output queues to be transmitted through the network to their destinations. We establish the capacity region of all rate matrices (/spl lambda//sub ij/) that the system can stably support-where /spl lambda//sub ij/ represents the rate of traffic originating at node i and destined for node j. A joint routing and power allocation policy is developed that stabilizes the system and provides bounded average delay guarantees whenever the input rates are within this capacity region. Such performance holds for general arrival and channel state processes, even if these processes are unknown to the network controller. We then apply this control algorithm to an ad hoc wireless network, where channel variations are due to user mobility. Centralized and decentralized implementations are compared, and the stability region of the decentralized algorithm is shown to contain that of the mobile relay strategy developed by Grossglauser and Tse (2002).

In this correspondence, we analyze feedforward tree networks of queues serving fixed-length packets. Using sample path conservation properties and stochastic coupling techniques, we analyze these systems without making any assumptions about the nature of the underlying input processes. In the case when the server rate is the same for all queues, the exact packet occupancy distribution in any queue of a multistage network is obtained in terms of a reduced two-stage equivalent model. Simple and exact expressions for occupancy mean and variance are derived from this result, and the network is shown to exhibit a natural traffic smoothing property, where preliminary stages act to smooth or improve traffic for downstream nodes. In the case of heterogeneous server rates, a similar type of smoothing is demonstrated, and upper bounds on the backlog distribution are derived. These bounds hold for general input streams and are tighter than currently known bounds for leaky bucket and stochastically bounded bursty traffic.

We study the provision of deterministic rate guarantees over single crossbar switches. Birkhoff decomposition yields a general approach for this problem, but the required complexity can be very high and the quality of service can be unsatisfactory for practical traffic sources. We develop a method called rate quantization which works with any resource speedup greater than 1 to convert the set of desired rates into a certain discrete set in such a way that the complexity and the quality of service guarantees can be greatly improved over a Birkhoff switch. Moreover, quantization enables us to develop a Slepian-Duguid-like algorithm that enables the switch to both adapt to dynamically varying traffic and simplify switch scheduling significantly.

We consider dynamic routing and power allocation for a wireless network with time varying channels. The network consists of power constrained nodes which transmit over wireless links with adaptive transmission rates. Packets randomly enter the system at each node and wait in output queues to be transmitted through the network to their destinations. We establish the capacity region of all rate matrices (/spl lambda//sub ij/) that the system can stably support - where (/spl lambda//sub ij/) represents the rate of traffic originating at node i and destined for node j. A joint routing and power allocation policy is developed which stabilizes the system and provides bounded average delay guarantees whenever the input rates are within this capacity region. Such performance holds for general arrival and channel state processes, even if these processes are unknown to the network controller. We then apply this control algorithm to an ad-hoc wireless network where channel variations are due to user mobility, and compare its performance with the Grossglauser-Tse (2001) relay model.

The output-queued (OQ) switch is often considered an ideal packet switching architecture for providing quality-of-service guarantees. Unfortunately, the high-speed memory requirements of the OQ switch prevent its use for large-scale devices. A previous result indicates that a crossbar switch fabric combined with lower speed input and output memory and two times speedup can exactly emulate an OQ switch; however, the complexity of the proposed centralized scheduling algorithms prevents scalability. This paper examines switch fabrics with limited memory and their ability to exactly emulate an OQ switch. The switch architecture of interest contains input queueing, fabric queueing, flow-control between the limited fabric buffers and the inputs, and output queueing. We present sufficient conditions that enable this combined input/fabric/output-queued switch with two times speedup to emulate a broad class of scheduling algorithms operating an OQ switch. Novel scheduling algorithms are then presented for the scalable buffered crossbar fabric. It is demonstrated that the addition of a small amount of memory at the crosspoints allows for distributed scheduling and significantly reduces scheduling complexity when compared with the memoryless crossbar fabric. We argue that a buffered crossbar system performing OQ switch emulation is feasible for OQ switch schedulers such as first-in-first-out, strict priority and earliest deadline first, and provides an attractive alternative to both crossbar switch fabrics and to the OQ switch architecture.

We consider power and server allocation in a multibeam satellite downlink which transmits data to N different ground locations over N time-varying channels. Packets destined for each ground location are stored in separate queues and the server rate for each queue, i, depends on the power, p/sub i/(t), allocated to that server and the channel state, c/sub i/(t), according to a concave rate-power curve /spl mu//sub i/(p/sub i/,c/sub i/). We establish the capacity region of all arrival rate vectors (/spl lambda//sub 1/,...,/spl lambda//sub N/) which admit a stabilizable system. We then develop a power-allocation policy which stabilizes the system whenever the rate vector lies within the capacity region. Such stability is guaranteed even if the channel model and the specific arrival rates are unknown. Furthermore, the algorithm is shown to be robust to arbitrary variations in the input rates and a bound on average delay is established. As a special case, this analysis verifies stability and provides a performance bound for the choose-the-K-largest-connected-queues policy when channels can be in one of two states (ON or OFF ) and K servers are allocated at every timestep (K

We consider power and server allocation in a multi-beam satellite downlink which transmits data to N different ground locations over N time-varying channels. Packets destined for each ground location are stored in separate queues, and the server rate for each queue i depends on the power p/sub i/(t) allocated to that server and the channel state c/sub i/(t) according to a concave rate-power curve /spl mu//sub i/(p/sub i/, c/sub i/). We establish the capacity region of all arrival rate vectors which admit a stabilizable system. For the case when channel states and arrivals are iid from timeslot to timeslot, we develop a particular power allocation policy which stabilizes the system whenever the rate vector lies within the capacity region. Such stability is guaranteed even if the channel model and the specific arrival rates are unknown. As a special case, this analysis verifies the stability of the "choose-the-K-largest-connected-queues" policy when channels can be in one of two states (ON or OFF) and K servers are allocated at every timestep (K

Theory and experiments show that as the per-flow product of bandwidth and latency increases, TCP becomes inefficient and prone to instability, regardless of the queuing scheme. This failing becomes increasingly important as the Internet evolves to incorporate very high-bandwidth optical links and more large-delay satellite links.To address this problem, we develop a novel approach to Internet congestion control that outperforms TCP in conventional environments, and remains efficient, fair, scalable, and stable as the bandwidth-delay product increases. This new eXplicit Control Protocol, XCP, generalizes the Explicit Congestion Notification proposal (ECN). In addition, XCP introduces the new concept of decoupling utilization control from fairness control. This allows a more flexible and analytically tractable protocol design and opens new avenues for service differentiation.Using a control theory framework, we model XCP and demonstrate it is stable and efficient regardless of the link capacity, the round trip delay, and the number of sources. Extensive packet-level simulations show that XCP outperforms TCP in both conventional and high bandwidth-delay environments. Further, XCP achieves fair bandwidth allocation, high utilization, small standing queue size, and near-zero packet drops, with both steady and highly varying traffic. Additionally, the new protocol does not maintain any per-flow state in routers and requires few CPU cycles per packet, which makes it implementable in high-speed routers.

This paper examines congestion control for explicit rate data networks. The available bit rate (ABR) service category of asynchronous transfer mode (ATM) networks serves as an example system for this paper, however the results of this paper are applicable to other explicit rate systems as well. After a plant model is established, an adaptive control strategy is presented and compared to other strategies. Two algorithm enhancements are then introduced. These enhancements reduce the convergence time and improve queue depth management. This work differentiates itself from the other contributions in the area of rate-based congestion control in its balanced approach of retaining enough complexity as to afford attractive performance properties, but not so much complexity as to make implementation prohibitively expensive.

One of the more challenging and yet unresolved issues which is paramount to the success of ATM networks is that of congestion control for available bit rate (ABR) traffic. Unlike other ATM service categories, ABR provides a feedback mechanism, allowing interior nodes to dictate source rates. Previous work has demonstrated how linear adaptive control theory can be utilized to create a stable and efficient control system for the purposes of ATM ABR congestion control. This paper investigates our previously proposed adaptive controller that uses a finite impulse response (FIR) filter to approximately invert the FIR plant. Specifically, convergence issues are addressed in depth. In doing so, a proof is provided for the convergence of the normalized least mean square (NLMS) adaptive algorithm employing a DC tap (drift tap), allowing the proof to extend beyond the (often-assumed) zero-mean case. Using a set of reasonable assumptions, parameter convergence in the mean and mean square is proven. Other issues pertaining to the stability of this controller are presented.

In this paper we examine the queuing behavior of a multi-stage multiplexer with fixed length packets flowing through the stages. The system consists of two components: a front end multi-input, multi-output device as a preliminary stage, and a single-server, deterministic service time queue system (multiplexer) as a final stage. We treat arbitrary exogenous arrival patterns and examine sample path characteristics of packet occupancy in the system. Under identical inputs, we compare the multi-stage system to the corresponding single-stage system without the front end. Treating both the infinite buffer (unlimited capacity) and finite buffer (fixed capacity) cases, we prove a two-part MultiStage Multiplexing Theorem. From the first part, we conclude that any type of multi-staging is "sub-optimal." However, from the second part we find that deterministic service time queues-if they need to be installed as front ends for a larger network-actually improve upon or smooth the data traffic for downstream nodes.

Rate-based feedback congestion control has been proposed as a form of traffic management for available bit rate traffic in ATM networks. This paper discusses applying linear control theory to these algorithms. A congestion control scheme for simple networks is designed and analyzed using the tools of classical control theory. This allows an insight into the trade-offs in such schemes and suggests approaches to larger networks.

In discrete multitone a cyclic prefix (CP) is inserted between symbols to ensure that samples from one symbol do not interfere with the samples of another symbol. The CP length is determined by the impulse response length of the effective physical channel. The cyclic prefix reduces the throughput of the transceiver. When the transceiver is used in a full-duplex environment the portion of the receive signal arising from echo must be reduced through the use of echo cancellation, the complexity of which is directly related to the length of the echo path impulse response. To alleviate both problems a short time-domain FIR filter can be used to shorten both the effective channel and echo impulse responses. This paper explores a joint optimal algorithm for determining the coefficients of this time-domain filter, resulting in reduced ISI and echo canceller complexity. For the simulations a configuration is chosen which is representative of that encountered by the remote terminal in the asymmetrical digital subscriber lines (ADSL) environment.

In discrete multitone (DMT) transceivers an intelligent guard time sequence, called a cyclic prefix (CP), is inserted between symbols to ensure that samples from one symbol do not interfere with the samples of another symbol. The length of the CP is determined by the length of the impulse response of the effective physical channel. Using a long CP reduces the throughput of the transceiver, To avoid using a long CP, a short time-domain finite impulse response (FIR) filter is used to shorten the effective channels impulse response. This paper explores various methods of determining the coefficients for this time-domain filter. An optimal shortening and a least-squares (LS) approach are developed for shortening the channel's impulse response. To provide a computationally efficient algorithm a variation of the LS approach is explored. In full-duplex transceivers the length of the effective echo path impacts the computational requirements of the transceiver. A new paradigm of joint shortening is introduced and three methods are developed to jointly shorten the channel and the echo impulse responses in order to reduce the length of the CP and reduce computational requirements for the echo canceller.

In the past, the nonlinear effects of quantization in differential speech coders either were modeled as additive white Gaussian noise or were ignored in analysis and quantified experimentally. Describing functions are used to model the nonlinear quantizer effects of coarsely quantized difference signals found primarily in adaptive predictive coding (APC) systems. The analysis predicts marginal instabilities in APC encoders. The marginal instabilities result in ringing distortions in the reconstructed signal which, in the past, may have been attributed to pitch and spectral predictor mismatches. Adaptive order prediction is introduced, analyzed, and offered as a method for increasing the robustness of APC encoders.

A three stage packet switch architecture that uses a two stage, self-routing memoryless interconnection network to interconnect a third stage of smaller packet switches has been proposed by K. Y. Eng et al. (1988) and M. J. Karol and Chih-Lin I. (1989). The authors propose a new routing algorithm for this architecture that facilitates the multicasting of packets. Packets are duplicated as near to the switch's outputs as possible. The authors also analyze the switch's multicast performance, finding an overbound on the packet loss probability. The resulting overbound shows that a small increase in the expansion factor is sufficient to maintain a multicast packet loss probability that is equivalent to that obtained in the non-multicast case.>

An analysis is presented of the bias produced in the composite regressor algorithm. This study contains what the authors believe is the first analytical demonstration that there is bias in the output error algorithm when the algorithm is used with a small but nonvanishing adaptation step size. The analysis provides insight into general bias properties of infinite-impulse-response adaptive filtering algorithms.>

Adaptive echo cancellation is being used on shorter telephone circuits. However, while echo cancelers do tend to be effective on the shorter circuits, a new (and undesirable) phenomena called bursting has been observed. Bursting is characterized by long periods of successful echo attenuation alternating with short periods of wildly oscillating signals. The authors studied bursting by constructing a pair of simplified models of adaptive hybrid systems. The models are analyzed when they are excited by various DC and sinusoidal inputs, and the results are related back to the systems of interest, providing insight into the fundamental sources of the bursting problem-an imbalance of excitation and the enclosure of an adaptive filter in a feedback loop. Simulations providing corroborating evidence are discussed.>

A relation between equation error and output-error adaptive algorithms is presented. It leads to a clarified view of output-error bias and stability. It is shown that a tradeoff between desirable stability and bias characteristics can be achieved in output error by manipulation of the adaptive gain. The composite regressor algorithm (CRA) is introduced as a means of affecting this tradeoff, independent of the gain. Output error is shown to a special case of CRA. A stability constraint for CRA is developed in a theorem, and the bias properties of this algorithm are discussed.>

Adaptive filtering techniques have been successfully applied to attenuate echoes in long-distance telephone communications. Recently, with the increased ability to process signals cheaply, adaptive echo cancellation is being utilized on shorter telephone circuits. To avoid the possibility of entrapment in an echo-canceller initialization that causes singing, doubletalk detectors cannot be used aggressively on such highly variable short connections. While echo cancelers tend to be effective on the shorter circuits, in the absence of doubletalk detectors a novel (and undesirable) phenomenon called bursting has been observed in real-time laboratory tests of such applications. Bursting is characterized by long periods of successful echo attenuation alternating with short periods of wildly oscillating signals. By analyzing a simplified abstraction of this problem, a theoretical explanation is presented of the kernel of the bursting problem: an imbalanced excitation combination. The structural source of the problem is the use of an adaptive filter in a feedback loop.>

Adaptive recursive algorithms using output error have some very attractive properties for both adaptive recursive filtering and system identification. However, their use has been severely restricted by the need to satisfy the so-called SPR condition. In this paper we demonstrate on the well known HARF algorithm that the use of large gains can essentially eliminate the need for the SPR condition. This should allow for more widespread use of adaptive recursive filtering and output error system identification.

It has been shown by example that the often used sign-sign variant of the LMS can be unstable and produce unbounded parameter estimates. In this paper a modified sufficient excitation condition on the regressor vector for the sign-sign variant is introduced. Satisfaction of the excitation condition guarantees that there exists a sufficiently small step size to produce parameter estimates which converge exponentially to within a region of the correct parameters. The counter example to stability of sign-sign algorithms is reexamined in light of the new excitation condition and it is shown that the excitation condition correctly predicts when instability will occur in this example.