Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

A General Framework for Flow Control in Wireless Networks

Minghua Chen

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-194
December 22, 2006

http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-194.pdf

Flow control, including congestion control for data transmission, and rate control for multimedia streaming, is an important issue in information transmission for both wired and wireless networks. Proper flow control allows users to fairly and fully utilize available bandwidth without the possibility of congestion collapse. Failure to apply proper flow control may result in serious performance degradation in a network. Although the problem of flow control has been successfully addressed in wired networks, it is still open in wireless networks. Current widely accepted solutions, such as 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. We show that this often results in bandwidth underutilization in wireless networks. This problem is becoming increasingly more serious as wireless data and multimedia services are being rapidly deployed commercially on carries throughout the world with data rates of up to one Mbps. In this thesis, we first formulate flow control in wireless networks as a convex optimization problem. 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 loss. Our solution differs from all existing schemes introduced in the past decade in the following ways: First, it is theoretically guaranteed to be optimal, stable and scalable. Practically, in a network with arbitrary topology, arbitrary number of users, and arbitrary initial source rates, our proposed schemes guarantee all users' source rates to globally exponentially converge to an equilibrium. This convergence guarantees no congestion collapse in the network. At the equilibrium, all bottlenecks are fully utilized and users are fair to each other. Furthermore, proposed schemes are fair to TCP/TFRC protocols, and are therefore amenable to incremental deployment in the current Internet where TCP is dominant. Second, our proposed schemes are end-to-end and require modifications to neither infrastructure nor transport protocol stack, making it easy to deploy in practice. Based on this approach, we have designed practical schemes for data transmission over wireless networks, and characterized their performance using simulations and actual experiments over the Verizon Wireless 1xRTT and EVDO CDMA data networks. This work implicitly provides a general framework for flow control. In this framework, both users' rates and the number of connections they open are properly controlled to pursue equilibrium in the network. We show it is sufficient to control users' rates and their number of connections independently in two separate timescales, in order to guarantee convergence to the desired equilibrium. This two timescale approach allows modification of the control law in one timescale without affecting the one in the other timescale, or the system's convergence. This framework is general in the sense that its usage is not limited to the problem we study in this thesis, which serves as an ideal platform to demonstrate the power of this approach.

Advisor: Avideh Zakhor


BibTeX citation:

@phdthesis{Chen:EECS-2006-194,
    Author = {Chen, Minghua},
    Title = {A General Framework for Flow Control in Wireless Networks},
    School = {EECS Department, University of California, Berkeley},
    Year = {2006},
    Month = {Dec},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-194.html},
    Number = {UCB/EECS-2006-194},
    Abstract = {Flow control, including congestion control for data transmission, and rate control for multimedia streaming, is an important issue in information transmission for both wired and wireless networks. Proper flow control allows users to fairly and fully utilize available bandwidth without the possibility of congestion collapse. Failure to apply proper flow control may result in serious performance degradation in a network.

Although the problem of flow control has been successfully addressed in wired networks, it is still open in wireless networks. Current widely accepted solutions, such as 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. We show that this often results in bandwidth underutilization in wireless networks. This problem is becoming increasingly more serious as wireless data and multimedia services are being rapidly deployed commercially on carries throughout the world with data rates of up to one Mbps.

In this thesis, we first formulate flow control in wireless networks as a convex optimization problem. 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 loss. Our solution differs from all existing schemes introduced in the past decade in the following ways:
First, it is theoretically guaranteed to be optimal, stable and scalable. Practically, in a network with arbitrary topology, arbitrary number of users, and arbitrary initial source rates, our proposed schemes guarantee all users' source rates to globally exponentially converge to an equilibrium. This convergence guarantees no congestion collapse in the network. At the equilibrium, all bottlenecks are fully utilized and users are fair to each other. Furthermore, proposed schemes are fair to TCP/TFRC protocols, and are therefore amenable to incremental deployment in the current Internet where TCP is dominant. 

Second,  our proposed schemes are end-to-end and require modifications to neither infrastructure nor transport protocol stack, making it easy to deploy in practice.

Based on this approach, we have designed practical schemes for data transmission over wireless networks, and characterized their performance using simulations and actual experiments over the Verizon Wireless 1xRTT and EVDO CDMA data networks.

This work implicitly provides a general framework for flow control. In this framework, both users' rates and the number of connections they open are properly controlled to pursue equilibrium in the network. We show it is sufficient to control users' rates and their number of connections independently in two separate timescales, in order to guarantee convergence to the desired equilibrium. This two timescale approach allows modification of the control law in one timescale without affecting the one in the other timescale, or the system's convergence. This framework is general in the sense that its usage is not limited to the problem we study in this thesis, which serves as an ideal platform to demonstrate the power of this approach.}
}

EndNote citation:

%0 Thesis
%A Chen, Minghua
%T A General Framework for Flow Control in Wireless Networks
%I EECS Department, University of California, Berkeley
%D 2006
%8 December 22
%@ UCB/EECS-2006-194
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-194.html
%F Chen:EECS-2006-194