This dissertation is a study on the design and analysis of novel, optimal routing and rate control algorithms in wireless, mobile communication networks. Congestion control and routing algorithms upto now have been designed and optimized for wired or wireless mesh networks. In those networks, optimal algorithms (optimal in the sense that either the throughput is maximized or delay is minimized, or the network operation cost is minimized) can be engineered based on the classic time scale decomposition assumption that the dynamics of the network are either fast enough so that these algorithms essentially see the average or slow enough that any changes can be tracked to allow the algorithms to adapt over time. However, as technological advancements enable integration of ever more mobile nodes into communication networks, any rate control or routing algorithms based, for example, on averaging out the capacity of the wireless mobile link or tracking the instantaneous capacity will perform poorly. The common element in our solution to engineering efficient routing and rate control algorithms for mobile wireless networks is to make the wireless mobile links seem as if they are wired or wireless links to all but few nodes that directly see the mobile links (either the mobiles or nodes that can transmit to or receive from the mobiles) through an appropriate use of queuing structures at these selected nodes. This approach allows us to design end-to-end rate control or routing algorithms for wireless mobile networks so that neither averaging nor instantaneous tracking is necessary.
There is a considerable body of literature @cite_67 @cite_55 on modeling the TCP window process in the presence of active queue management (AQM) systems, especially random early detection (RED) @cite_33 . @cite_55 presents a weak limit of the window size process by proving a weak convergence of triangular arrays. @cite_78 presents a fluid limit of the TCP window process, as the number of concurrent flows sharing a link goes to infinity, and the authors show that the deterministic limiting system provides a good approximation for the average queue size and total throughput. None of the previous works mentioned above treats the situation when the loss rate can not be tracked due mismatch between the channel change time-scale and the RTT time-scale.
@cite_55 @cite_67 @cite_33 @cite_78
2117068155 2145942024 2158733823
We consider a discrete-time stochastic model of an ECN RED gateway where competing TCP sources share the link capacity. As the number of competing flows becomes large, the asymptotic queue behavior (normalized by the number of flows) at the gateway can be described by a simple recursion and the throughput behavior of individual TCP flows becomes asymptotically independent. A Central Limit Theorem complement is also presented, yielding a more accurate characterization of the asymptotic queue size. These results suggest a scalable yet accurate model of this complex large-scale stochastic feedback system, and crisply reveal the sources of queue fluctuations. In this paper we study a previously developed linearized model of TCP and active queue management (AQM). We use classical control system techniques to develop controllers well suited for the application. The controllers are shown to have better theoretical properties than the well known RED controller. We present guidelines for designing stable controllers subject to network parameters like load level propagation delay etc. We also present simple implementation techniques which require a minimal change to RED implementations. The performance of the controllers are verified and compared with RED using ns simulations. The second of our designs, the proportional integral (PI) controller is shown to outperform RED significantly. The authors present random early detection (RED) gateways for congestion avoidance in packet-switched networks. The gateway detects incipient congestion by computing the average queue size. The gateway could notify connections of congestion either by dropping packets arriving at the gateway or by setting a bit in packet headers. When the average queue size exceeds a present threshold, the gateway drops or marks each arriving packet with a certain probability, where the exact probability is a function of the average queue size. RED gateways keep the average queue size low while allowing occasional bursts of packets in the queue. During congestion, the probability that the gateway notifies a particular connection to reduce its window is roughly proportional to that connection's share of the bandwidth through the gateway. RED gateways are designed to accompany a transport-layer congestion control protocol such as TCP. The RED gateway has no bias against bursty traffic and avoids the global synchronization of many connections decreasing their window at the same time. Simulations of a TCP IP network are used to illustrate the performance of RED gateways. >