Impact of network state information on protocol performance

Abstract

Communication protocols require network state information. Generally, communication devices are geographically dispersed, and the states (e.g., traffic states, channel states) of the devices are unknown to each other. Therefore, state information needs to be exchanged among the devices, such that the actions of the devices are coordinated and various network functions such as scheduling and routing may be completed. Since the available state information directly affects the actions of the devices and thus the network performance, it is crucial to understand this impact. Moreover, as transmitting state information occupies bandwidth resources, which results in less bandwidth for data transmissions, it is important to design resource allocation schemes to balance the state information acquisition and data transmission. Two key problems should be solved: First, what is the relationship between the available state information and network performance? Second, how should network bandwidth resource be allocated to maximize the overall resource utilization efficiency of the network?

In this thesis, we address the above two problems from three different aspects. First, we consider the relationship between information quantity and network performance. We establish a general framework to study the relationship between the amount of acquired network state information and network protocol performance, based on which the optimal resource allocation scheme could be designed. The framework serves as the foundation of this thesis to study the impact of state information in various protocols. A traffic scheduling protocol and Carrier Sense Multiple Access (CSMA) protocol are used for illustration and the optimal resource allocation schemes are obtained.

After that, we apply the framework to a specific class of protocols – Multiple Access Communication (MAC) protocols, and study the minimum amount of information required to resolve traffic conflicts. We provide an upper bound of this minimum, which is shown to be close to the existing lower bound and asymptotically optimal in terms of the average amount of information required per unit traffic. The amount of state information acquired in existing protocols (e.g., the splitting algorithm and slotted-ALOHA protocol) for conflict resolution is determined and compared with the theoretic bound, and the relation between the pattern of state information acquisition and network performance is observed.

Finally, by noticing that the collected state information is usually subject to delay in networks, we further extend the framework to analyze the impact of delayed information, and discuss the optimal resource allocation scheme under this condition. A multiuser scheduling problem is analyzed to illustrate the application of our framework, and some general guidelines of state information acquisition in time-varying networks are suggested.