Large-scale wireless networks are projected to dominate the information technology sector in the future, giving rise to a new set of research problems on scalability. The main goal of this project is to develop an essential understanding of the impact of large scales on the performance of wireless networks. In particular, the project examines how the finiteness of resources (memory, computational power, etc.) at individual nodes affects the overall network performance. The developed understanding is then used to design a set of algorithms that support efficient operation of large-scale networks of nodes with very limited resources. The algorithmic aspect is particularly important given that some of widely considered algorithms require excessive resources at individual nodes and, hence, are not scalable. However, the project demonstrates the existence of algorithms that require only negligible resources but achieve comparable performance. Furthermore, the study reveals that completely new protocols are needed to support operation of large-scales wireless networks.
In contrast to the majority of earlier studies that examined either large networks with unlimited node resources or small networks with limited node resources, the focus of this project is on relationship between the network size and node resources. Most of the considered problems are impractical to be addressed experimentally due to a considerable cost of building large-scale prototypes. Moreover, even simulating such systems is often very difficult because of computational limitations. Thus, a comprehensive research agenda is based on an analytical framework that overcomes the difficulties imposed by large scales.
The growth of modern communication infrastructures, such as the Internet and various wireless networks, over the last two decades has surpassed the expectations of everyone. Indeed, going back in time to the origins of these networks, it would have been hard to imagine the importance and scale to which these networks have developed. Projecting into the future, it is expected that this growth trend will only continue, if not accelerate. Hence, the communication devices and protocols of today must be capable of operating with the same efficiency in the very large-scale networks of the future. One of the basic concerns in building large-scale networks is that minor inefficiencies, which can be well tolerated in small networks, can accumulate and become dominant factors in large networks. Data networks are elaborate systems with multiple protocols governing their operation. For example, different algorithms deal with routing of information and scheduling of data packets for transmission. Thus, the project consisted of multiple sub-projects that dealt with specific aspects of algorithmic scalability (properties of the physical layer are governed by the fundamental laws of physics). Our main findings indicate that, while some well-known algorithms might not perform well in large-scale networks, there exist algorithms that can overcome issues imposed by large scales. For example, the shortest-path algorithm is not scalable in certain networks due to the fact that it can require excessively large amounts of information at individual nodes. However, there exist alternative algorithms that do not require large routing tables (the size of routing tables remains bounded). In general, scalable algorithms are distributed in their nature, but require network node cooperation. For example, in a network of nodes with limited buffer storage, distributed storage of information can be implemented in order to eliminate buffer bottlenecks. Moreover, randomized algorithms and algorithms with special data structures can be utilized to achieve desirable performance in the absence of full information on network states and/or system parameters. Such algorithms are preferred, since large-scale networks are often operating in time-varying environments. The high-level finding of the project is that, in many cases, scalability can be achieved by designing algorithms based on careful analyses of network models as their size increases.
