Date: April 23, 1998
Speaker: Bruce Maggs, Carnegie Mellon University
Adventures in Asymmetric Networking
Abstract:
This talk will begin by briefly describing a wireless asymmetric network that the speaker has deployed at Carnegie Mellon to provide internet access to students living in neighborhoods surrounding the campus. It will then present a study of network traffic traces indicating that network usage is asymmetric in a variety of networking environments, whether or not the underlying medium is asymmetric. The talk will conclude by examining the following problem inspired by the asymmetric networking project. Suppose that a client and a server are connected by an asymmetric communication channel where the transmission bandwidth from the server to the client greatly exceeds the bandwidth from the client to the server. Suppose further that the client wishes to communicate an n-bit data item to the server, where the data is drawn from a distribution D that is known to the server but not to the client. Can the bandwidth from the server to the client be used to reduce the number of bits transmitted by the client? We show that the answer is yes. In particular, we present protocols in which the expected number of bits transmitted by the server and client are O(n) and O(H(D)), respectively, where H(D) is the entropy of D. In the simplest of these protocols, the expected number of rounds of communication is O(H(D)). We also give a protocol for which the expected number of rounds is only O(1), but which requires more computational effort on the part of the server. These protocols are complemented by lower bounds and impossibility results. We show that all of the protocols are existentially optimal in terms of the number of bits sent by the server. In addition, we show that there is no protocol that is optimal for every distribution, because this problem is undecidable.
Joint work with Micah Adler and Chris Hobbs.
SDI / LCS Seminar Questions?
Karen Lindenfelser, 86716, or visit www.pdl.cmu.edu/SDI/