To increase network capacity, it may not be sufficient to just increase the capacity of the networks. It may be necessary to reduce the network overhead bits, to leave more room for the data bits, to increase the network capacity. As network functions become more complicated, more elaborate protocols become necessary to manage the networks. Without a proper and fundamental understanding of the overheads resulting from protocol bits, we may have protocols with huge overheads, which diminish the network efficiency, resulting in high cost and low value networks. Most effort has been dedicated to finding higher capacity links to carry more data. Little, or no effort has been spent to define a framework and analyze the overheads in the networks with the aim of understanding their behavior and thus reducing them. In this thesis, we give some perspectives on quantifying network overheads and some policies to reduce them. In a fixed network example, we show that, one can provide a lower bound on the number of bits needed to encode each message, exchanged by a node with its neighbors, to know the connectivity information of the node to others, i.e. its network neighborhood. The lower bound also provides insights into the dynamics of protocol information and its connection to the link statistics. We then examine the overheads arising out of the network's effort to keep track of a user, equivalent to knowing the connectivity information in fixed networks, in the case of two-tier hierarchical networks in general, and cellular and peer-to-peer networks in particular. We find that there exists an optimal threshold-based announcing policy of the user, about its location, which minimizes the network overheads. Clustering of users is also found to be a good strategy, in two-tier hierarchical networks, to minimize user tracking overheads. We find the optimal clustering which minimizes the tracking overhead, and that the optimal clustering is crucial to finding the aforementioned optimal announcing policy. As a next strategy, we show that clustering of user location information can reduce the number of bits needed to represent the information. The location information updates can be sent periodically, and the necessary bits needed to un-cluster the information can be fetched on a requirement basis. Based on the location statistics of the user, one can find a clustering of the location information, such that, given the clustered information, the number of bits that need to be fetched is minimized. Bandwidth is a very important attribute of a network, which if not allocated optimally, can be an "overhead" in terms of reduced network efficiency and high service costs. We take the viewpoint that, the optimal allocation should be based on users' behavior, who are the final consumers of the bandwidth. We study the user's psychology for media and its connection to bandwidth, and show a way to optimize bandwidth allocation. The conclusions from the optimal allocation, lead us to an architecture of a low cost, high value, and fast Internet access solution.
EPFL2004
