A practical controller for explicit rate congestion control

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, 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. Several algorithm enhancements are then introduced. These enhancements reduce convergence time, improve queue depth management, and reduce parameter bias. 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     

Dynamic power allocation and routing for time-varying wireless networks

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).     

Output-queued switch emulation by fabrics with limited memory

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.     

Robustness of continuous-time adaptive control algorithms in the presence of unmodeled dynamics

This paper examines the robustness properties of existing adaptive control algorithms to unmodeled plant high-frequency dynamics and unmeasurable output disturbances. It is demonstrated thai there exist two infinite-gain operators in the nonlinear dynamic system which determines the time-evolution of output and parameter errors. The pragmatic implication of the existence of such infinite-gain operators is that 1) sinusoidal reference inputs at specific frequencies and/or 2) sinusoidal output disturbances at any frequency (including dc), can cause the loop gain to increase without bound, thereby exciting the unmodeled high-frequency dynamics, and yielding an unstable control system. Hence, it is concluded that existing adaptive control algorithms as they are presented in the literature referenced in this paper, cannot be used with confidence in practical designs where the plant contains unmodeled dynamics because instability is likely to result. Further understanding is required to ascertain how the currently implemented adaptive systems differ from the theoretical systems studied here and how further theoretical development can improve the robustness of adaptive controllers.     

Some design guidelines for discrete-time adaptive controllers

There have been many algorithms proposed for adaptive control which will provide globally asymptotically stable controllers if some stringent conditions on the plant are met. The conditions on the plant cannot be met in practice as all plants will contain high frequency unmodeled dynamics. This paper uses a linearization analysis of a nonlinear adaptive controller to demonstrate analytically some design guidelines which alleviate some of the problems associated with adaptive control in the presence of unmodeled dynamics. The points made are further demonstrated by simulation results.     

An adaptive inverse controller for explicit rate congestion control with guaranteed stability and fairness

This paper examines explicit rate congestion control for data networks. The available bit rate (ABR) service category of asynchronous transfer mode (ATM) networks serves as an example explicit rate system. However, the results of this paper are applicable to other systems as well. After a plant model is established, a control strategy based on approximate inverse concepts is introduced. The control process includes a linear digital filter (with a DC or drift tap) that uses normalized least mean square (NLMS) adaptation. The convergence, stability and fairness properties of this control scheme are discussed. 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, analytically-proven performance properties, but not so much complexity as to make implementation prohibitively expensive.     

The composite regressor algorithm for IIR adaptive systems

An adaptive IIR algorithm called the composite regressor algorithm (CRA) is developed. The algorithm is a generalization of the common equation error, a priori output error, and a posteriori output error adaptive IIR algorithms. The CRA is analyzed for convergence in a noiseless environment and for bias in a stochastic setting. It is determined that, by using a parameter called the regressor composition parameter, a tradeoff can be obtained between the automatic convergence but large bias results of the equation error algorithm and the difficult convergence condition but small bias results of the output error algorithms. In proving results for the CRA, it is shown that the a posteriori output error algorithm produces estimates with nonzero bias when the adaptive gain is small but bounded away from zero. A convergence condition for the a priori output error algorithm is derived for the first time     

Noise cancellation with improved residuals

An effective adaptive scheme for noise cancellation when the signal to be recovered has known autocorrelation is presented. Two algorithms that exploit a special form of prior information are investigated. In this approach the desired signal is removed from the output feedback by linear prediction: the prior information used is the desired signal's autocorrelation. Knowing this, one can find a filter that whitens the desired signal. Screening the error feedback through this filter removes most of the desired signal energy, reducing its interference with the coefficient update. This is the basis for the first algorithm discussed, namely, the least-mean-square algorithm with augmented predictor (LMS-AP) proposed by Orgren et al. (1986). In many applications the whitening filter may not be strictly positive real (SPR). In such cases a different algorithm is needed; one which is assuredly convergent regardless of the satisfaction of the SPR condition. A modified LMS algorithm with augmented predictor (MLMS-AP) which provides such an alternative is proposed     

Equivalent models for queueing analysis of deterministic service time tree networks

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.     

Impulse response shortening for discrete multitone transceivers

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