Reducing Control Overheads in Wireless Networks

Network control mechanisms are used to regulate the flow of traffic and ensure effective data transport in communication networks. Examples of network control tasks include scheduling and resource allocation, routing, and flow control. Typically, network control actions are taken in response to changes in the network state. Therefore, network control tasks necessitate the exchange of information regarding the network state, which we refer to as control information or protocol information. Examples of such control information include source and destination addresses, CTS/RTS messages, queue length information (QLI), channel state information (CSI), and packet loss rates. Understanding the role of protocol information in effective network control is important because it directly impacts network performance, and often leads to significant overheads.

Among the earliest works on protocol information in networks is Gallager’s seminal paper in 1976, where lower bounds on the amount of protocol information needed to keep track of source and destination addresses and message starting and stopping times are derived. Since then, communication networks have evolved greatly and acquired immense importance in our daily lives. However, the design of protocols and control policies has largely been dictated by practical heuristics, rather than sound theory. In this project, we revisit the topic of protocol information in networks from a modern viewpoint of network control, to aid in the design of more efficient network control algorithms with reduced protocol overheads.

At a high level, the network has relevant network state information (NSI) that varies over time. The network needs to convey control information (protocol information) about this state to the controller so that the controller can make efficient decisions. Thus, there is a tradeoff in the amount of control information sent to the controller (as overhead) and the performance of the network control algorithms. This applies to a wide range of network control problems, such as opportunistic scheduling, congestion-based flow control, link state routing and back pressure routing. Based on this framework, we investigate the tradeoff through several sub-problems:

(*) Fundamental Limits of Protocol Overhead: To begin, we develop a theoretical framework for assessing the impact of degraded network state information on the performance of network control. In this vein, the problem of transmitting control information is modeled as a rate distortion problem, where low distortion in network state information corresponds to high network performance. This framework yields bounds to quantify the minimum control overhead needed to reach a certain performance level.

(*) Infrequent NSI Updates: Next, we investigate network control algorithms which limit the amount and frequency of NSI updates. Such a restriction directly reduces the amount of protocol overhead in the network, but potentially results in a reduced network performance. The first approach is to characterize the loss of performance due to infrequent NSI updates. An understanding of this tradeoff yields practically important insights on how much resources one needs to invest in NSI updates for obtaining a desired performance. An additional approach for reducing the control overheads is to obtain updates from only a subset of the network. We characterize the tradeoff between the size of this subset and the corresponding network performance, as well as determine the optimal subset of the information to obtain at each time.

(*) Distributed Control and Protocol Information: In a distributed network control setting, the control decisions are made cooperatively by the nodes using locally exchanged information, in contrast to the centralized network control setting, where a network controller makes all of the decisions. In centralized schemes, accumulating NSI may be costly in large networks, and this information may be delayed as it propagates through the network. Thus, distributed control algorithms offer an alternative in which less protocol information is required, at a cost to performance. We investigate the design of distributed algorithms with respect to protocol information, and investigate the tradeoff between the performance of these algorithms and the locality and amount of protocol information exchanged.