Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


Research Projects

A Uniform Two Timescale Framework for Flow Control in Wireless Networks


Alessandro Abate, Minghua Chen, Ryusuke Fujita, S. Shankar Sastry and Avideh Zakhor

Flow control, including congestion control for data transmission, and rate control for multimedia streaming, is an important issue in information transmission in both wired and wireless networks. It allows distributed users to fairly and fully utilize available bandwidth without collapsing the network. Failure to apply flow control may result in serious performance degradation. Although the problem of flow control has been successfully addressed in wired networks, it is still an open problem in wireless networks. Current widely accepted solutions, e.g., TCP, assume that congestion is the only cause of packet loss, and as such, are not applicable to wireless networks in which the bulk of packet loss is due to errors at the physical layer. This often results in underutilization of wireless bandwidth. This problem is becoming more and more serious as wireless data and multimedia services are rapidly emerging, e.g., commercial cellular service providers now support data service up to several Mbps. In this project, we first formulate flow control in wireless networks as a convex optimization problem, of which Kelly's wired one is merely an extreme case. We then propose a new class of solutions that properly adjust the number of connections of a user, to fully utilize wireless bandwidth and minimize end-to-end packet losses. Our solution differs from all existing schemes in the past decade, since TCP's performance degradation in wireless network was first observed in 1994, as the following. First, it has been theoretically guaranteed to be optimal, stable and scalable. Practically, these results infer that in a network with arbitrary topology, arbitrary number of users, and arbitrary initial source rates, applying proposed schemes guarantees all users' source rates globally exponentially converge to an equilibrium. This convergence guarantees no congestion collapse in the network. Furthermore, at the equilibrium, all bottlenecks are fully utilized and users are fair to each other. This claim is true in the case that proposed schemes coexist with TCP/TFRC, which encourage incremental deployment of proposed schemes in the current Internet where TCP is dominant. Second, it is an end-to-end solution and requires no modifications in neither infrastructure nor transport protocol, making it easy to deploy in practice. We have applied the results to design practical schemes for data and multimedia transmissions over wireless networks. Their performance is characterized using simulations and actual experiments over the Verizon Wireless 1xRTT and EVDO CDMA data network. From a high level point of view, this work implicitly follows a uniform two timescale framework for flow control. In this framework, both sending rate and the number of connections of an application are allowed to dynamically change. Any flow control problem is interpreted as pursuing an equilibrium users' rates. If sending rates' dynamics change in a timescale much faster than that of the number of connections, and dynamics in both timescales are exponentially stable, then the sending rates are guaranteed to converge to the desired equilibrium globally exponentially. The separation into fast and slow timescales also allows substitution of control laws within one timescale without affecting the other, and without affecting the general convergence properties.

M. Chen, "A Uniform Two Timescale Framework for Flow Control in Wireless Networks," PhD thesis, UC Berkeley.
M. Chen, A. Zakhor, and R. Fujita, "Flow Control in Wireless Networks," IEEE Trans. Networking (submitted).
M. Chen and A. Zakhor, "Flow Control over Wireless Network and Application Layer Implementation," Proc. Infocom, Barcelona, Spain, April 2006.
M. Chen and A. Zakhor, "Multiple TFRC Connections Based Rate Control for Wireless Networks," IEEE Trans. Multimedia, October 2006.
A. Abate, M. Chen, S. Sastry, and A. Zakhor, "New Congestion Control Schemes over Wireless Networks: Stability and Delay Sensitive Considerations," IEEE Trans. Automatic Control (submitted).