The Internet is an extremely complex system, and it is essential that we be able to make accurate measurements in order to understand its underlying behavior or to detect improper behavior (e.g., attacks). The reality, however, is that it is impractical to fully instrument anything but relatively small networks and impossible to even partially instrument many parts of the Internet. This paper analyzes a subset of the general monitor placement problem where the goal is to maximize the coverage of the entire universe of potential communication pairs (i.e., source and destination are randomly distributed in the routable Internet address space). This issue arises, for example, when trying to detect/track a distributed attack. We present results from a simulation, seeded with data from skitter and RouteViews, that indicate we can monitor a packet with a high probability by monitoring relatively few points in the Internet. Our analysis suggests that the preferred strategy to place monitors should be to instrument one or two specific inter-AS links per AS for many ASes rather than deeply instrumenting a subset of the largest ASes.

Directional antennas offer tremendous potential for improving the performance of ad hoc networks. Harnessing this potential, however, requires new mechanisms at the medium access and network layers for intelligently and adaptively exploiting the antenna system. While recent years have seen a surge of research into such mechanisms, the problem of developing a complete ad hoc networking system, including the unique challenge of real-life prototype development and experimentation has not been addressed. In this paper, we present utilizing directional antennas for ad hoc networking (UDAAN). UDAAN is an interacting suite of modular network- and medium access control (MAC)-layer mechanisms for adaptive control of steered or switched antenna systems in an ad hoc network. UDAAN consists of several new mechanisms-a directional power-controlled MAC, neighbor discovery with beamforming, link characterization for directional antennas, proactive routing and forwarding-all working cohesively to provide the first complete systems solution. We also describe the development of a real-life ad hoc network testbed using UDAAN with switched directional antennas, and we discuss the lessons learned during field trials. High fidelity simulation results, using the same networking code as in the prototype, are also presented both for a specific scenario and using random mobility models. For the range of parameters studied, our results show that UDAAN can produce a very significant improvement in throughput over omnidirectional communications.

In this paper, we present UDAAN ("utilizing directional antennas for ad hoc networking"), which is an interacting suite of modular network- and MAC-layer mechanisms for adaptive control of steered or switched antenna systems in an ad hoc network. UDAAN consists of several new mechanisms - a directional power-controlled MAC, neighbor discovery with beamforming, link characterization with directional antennas, proactive routing and forwarding all working cohesively to provide the first complete systems solution. We describe the development of a real-life ad hoc network testbed using UDAAN with switched directional antennas, and we discuss the lessons learned during field trials. High fidelity simulation results, using the same networking code as in the prototype, are also presented. For the range of parameters studied, our results show that UDAAN can produce up to a factor-of-10 improvement in throughput over omni-directional communications.

A novel framework is presented for the study of scalability in ad hoc networks. Using this framework, the first asymptotic analysis is provided with respect to network size, mobility, and traffic for each fundamental class of ad hoc routing algorithms. Protocols studied include the following: plain flooding (PF), standard link state (SLS), dynamic source routing (DSR), hierarchical link state (HierLS), zone routing protocol (ZRP), and hazy sighted link state (HSLS). It is shown that PF and ZRP scale better with mobility, SIJS and ZRP scale better with respect to traffic, and HSLS scales better with respect to network size. The analysis provides deeper understanding of the limits and trade-offs inherent in mobile ad hoc network routing. Our analysis is complemented with a simulation experiment comparing HSLS and HierLS. An important contribution of this paper is that HSLS is an scalable, easy-to-implement, alternative to hierarchical approaches for large ad hoc networks.

In this paper, we introduce a class of approaches that attempt to scale link-state routing by limiting the scope of link state update dissemination in space and over time. We present the first fundamental analysis of this generic class, which we call "Fuzzy Sighted Link State routing". Using a novel perspective on the "overhead"of a protocol that includes not only the overhead due to control messages but also due to route sub-optimality, we formulate an analytical model whose solution automatically leads to the best algorithm in this class. This algorithm is shown to have nearly the best possible asymptotic overhead for any routing algorithm -proactive or reactive. Simulation results are presented that compare the performance or several algorithms in this class

Traditional routing protocols for MANET networks are usually designed with a particular environment in mind and fail to adapt to the wide range of environments present in a MANET network. Because of the wide diversity of the conditions that may be encountered in a MANET network it seems that it would be difficult to effectively route information by engaging a single type of protocol. Instead, a multi-mode protocol should be developed which applies the appropriate "mode" or protocol that is determined to be effective at a given point in time and for the appropriate subset of the network. In this paper, two algorithms: the limited link state (LLS) and self-organizing (SO), that adapt to any MANET network condition-from small networks with nodes with low mobility to large networks with highly mobile nodes to an heterogeneous network with different classes of users-in order to make the most efficient routing decisions are discussed. These algorithms employ new metrics that capture the mobility and traffic pattern of (subsets of) the network, along with some attributes considered in the past (e.g. link stability). Once the instantaneous structure of the network is determined, the multi-mode routing protocol may select its 'mode' of operation.

The objective of this paper is to determine the minimum system dropping rate (or, equivalently, dropping probability) induced by time division multiple access (TDMA) schemes supporting time-constrained applications with common maximum cell delay tolerance. Expressions are derived for the induced system dropping rate for various TDMA schemes with different overhead and the maximum number of users than can be admitted in the network without violating the maximum dropping rate constraint is determined. The system dropping rate achieved by suboptimal TDMA schemes is compared against the optimal (although ideal) TDMA scheme performance. The performance limiting factors associated with the suboptimal schemes are identified, and the magnitude of their (negative) impact is evaluated. Based on this information it is possible to point to performance improving modifications which should be pursued to the extent permitted by technological constraints. Finally, based on this derivations a network designer may choose the best TDMA scheme-among realizable variations of those considered here-to use in a particular situation.