We consider the problem of efficientMAC design for long-distance WiFi-based mesh networks. In such networks it is common to find long propagation delays, the use of directional antennas, and the presence of inter-link interference. Prior work has shown that these characteristics make traditional CSMA-based MACs a poor choice for long-distance mesh networks and this finding has led to several recent research efforts exploring the use of TDMA-based approaches to media access. In this paper we first identify, and then address, several shortcomings of current TDMA-based proposals. First, because they use fixed-length transmission slots, current TDMA-based solutions do not adapt to dynamic variations in traffic load leading to inefficiencies in both throughput and delay. As we show in this paper, the throughput achieved by existing solutions falls far short of the optimal achievable network throughput. Finally, due to the scheduling constraints imposed by inter-link interference, current TDMA-based solutions only apply to bipartite network topologies.

Despite the increasing number of WiFi-based Long Distance (WiLD) network deployments, there is a lack of understanding of how WiLD networks perform in practice. In this paper, we perform a systematic study to investigate the commonly cited sources of packet loss induced by the wireless channel and by the 802.11 MAC protocol. The channel induced losses that we study are external WiFi, non-WiFi and multipath interference. The protocol induced losses that we study are protocol timeouts and the breakdown of CSMA over WiLD links. Our results are based on measurements performed on two real-world WiLD deployments and a wireless channel emulator. The two deployments allow us to compare measurements across rural and urban settings. The channel emulator allows us to study each source of packet loss in isolation in a controlled environment. Based on our experiments we observe that the presence of external WiFi interference leads to significant amount of packet loss in WiLD links. In addition to identifying the sources of packet loss, we analyze the loss variability across time. We also explore the solution space and propose a range of MAC and network layer adaptation algorithms to mitigate the channel and protocol induced losses. The key lessons from this study were also used in the design of a TDMA based MAC protocol for high performance long distance multihop wireless networks [12].

Most P2P systems that provide a DHT abstraction distribute objects randomly among "peer nodes" in a way that results in some nodes having /spl theta/(log N) times as many objects as the average node. Further imbalance may result due to non-uniform distribution of objects in the identifier space and a high degree of heterogeneity in object loads and node capacities. Additionally, a node's load may vary greatly over time since the system can be expected to experience continuous insertions and deletions of objects, skewed object arrival patterns, and continuous arrival and departure of nodes. We propose an algorithm for load balancing in such heterogeneous, dynamic P2P systems. Our simulation results show that in the face of rapid arrivals and departures of objects of widely varying load, our algorithm achieves load balancing for system utilizations as high as 90% while moving only about 8% of the load that arrives into the system. Similarly, in a dynamic system where nodes arrive and depart, our algorithm moves less than 60% of the load the underlying DHT moves due to node arrivals and departures. Finally, we show that our distributed algorithm performs only negligibly worse than a similar centralized algorithm, and that node heterogeneity helps, not hurts, the scalability of our algorithm.

Attempts to generalize the Internet's point-to-point communication abstraction to provide services like multicast, anycast, and mobility have faced challenging technical problems and deployment barriers. To ease the deployment of such services, this paper proposes a general, overlay-based Internet Indirection Infrastructure (i3) that offers a rendezvous-based communication abstraction. Instead of explicitly sending a packet to a destination, each packet is associated with an identifier; this identifier is then used by the receiver to obtain delivery of the packet. This level of indirection decouples the act of sending from the act of receiving, and allows i3 to efficiently support a wide variety of fundamental communication services. To demonstrate the feasibility of this approach, we have designed and built a prototype based on the Chord lookup protocol.

Attempts to generalize the Internet's point-to-point communication abstraction to provide services like multicast, anycast, and mobility have faced challenging technical problems and deployment barriers. To ease the deployment of such services, this paper proposes an overlay-based Internet Indirection Infrastructure ( I3) that offers a rendezvous-based communication abstraction. Instead of explicitly sending a packet to a destination, each packet is associated with an identifier; this identifier is then used by the receiver to obtain delivery of the packet. This level of indirection decouples the act of sending from the act of receiving, and allows I3 to efficiently support a wide variety of fundamental communication services. To demonstrate the feasibility of this approach, we have designed and built a prototype based on the Chord lookup protocol.