Proceedings - IEEE INFOCOM

The vision of ad-hoc networking with Bluetooth includes the concept of devices participating in multiple "piconets" and thereby forming a "scatternet". However, the details of scatternet support for Bluetooth are not specified yet. This paper presents a scheme for Bluetooth scatternet operation that adapts to varying traffic patterns. Being based on sniff mode, it does not require substantial modification of the current Bluetooth specification and may thus be incorporated into currently available Bluetooth products. We present simulation results that confirm the applicability of our approach to realistic scenarios.

While the advantages of multicast delivery over multiple unicast deliveries is undeniable, the deployment of the IP multicast protocol has been limited to "islands" of network domains under single administrative control. Deployment of inter-domain multicast delivery has been slow due to both technical and administrative reasons. In this paper we propose a Host Multicast Tree Protocol (HMTP) that (1) automates the interconnection of IP-multicast enabled islands and (2) provides multicast delivery to end hosts where IP multicast is not available. With HMTP, end-hosts and proxy gateways of IP multicast-enabled islands can dynamically create shared multicast trees across different islands. Members of an HMTP multicast group self-organize into an efficient, scalable and robust multicast tree. The tree structure is adjusted periodically to accommodate changes in group membership and network topology. Simulation results show that the multicast tree has low cost, and data delivered over it experiences moderately low latency.

This paper deals with the performance modeling of the various MAC states as defined by the cdma2000 protocol. Our method uses a composite performance metric which has the capability of proportionally combining three basic parameters: channel utilization, waiting time and the saving in the signalling overhead. The scheduler at the base station is not only responsible for admitting new services into the system but also for switching the MAC states of a service depending on its activity. Since the true nature of the wireless data traffic is yet unknown, we use a mix of Poisson-distributed voice packets and Pareto-distributed data packets. We derive analytical expressions and also conduct simulation experiments to study the nature of the performance curve and thus compute the optimal values of expiration timers at which the MAC states should be switched such that the system performance is maximized. We show how our model can be made suitable for different systems by tuning the scaling functions (or weights) for each of the three performance parameters considered.

Forcing all IP packets to carry correct source addresses can greatly help network security, attack tracing, and network problem debugging. However, due to asymmetries in today's Internet routing, routers do not have readily available information to verify the correctness of the source address for each incoming packet. In this paper we describe a new protocol, named SAVE, that can provide routers with the information needed for source address validation. SAVE messages propagate valid source address information from the source location to all destinations, allowing each router along the way to build an incoming table that associates each incoming interface of the router with a set of valid source address blocks. This paper presents the protocol design and evaluates its correctness and performance by simulation experiments. The paper also discusses the issues of protocol security, the effectiveness of partial SAVE deployment, and the handling of unconventional forms of network routing, such as mobile IP and tunneling.

Gupta and Kumar (see IEEE Transactions an Information Theory, vol.46, no.2, p.388-404, 2000) determined the capacity of wireless networks under certain assumptions, among them point-to-point coding, which excludes for example multi-access and broadcast codes. We consider essentially the same physical model of a wireless network under a different traffic pattern, namely the relay traffic pattern, but we allow for arbitrarily complex network coding. In our model, there is only one active source/destination pair, while all other nodes assist this transmission. We show code constructions leading to achievable rates and derive upper bounds from the max-flow min-cut theorem. It is shown that lower and upper bounds meet asymptotically as the number of nodes in the network goes to infinity, thus proving that the capacity of the wireless network with n nodes under the relay traffic pattern behaves like log n bits per second. This demonstrates also that network coding is essential: under the point-to-point coding assumption considered by Gupta et al., the achievable rate is constant, independent of the number of nodes. Moreover, the result of this paper has implications' and extensions to fading channels and to sensor networks.

In this paper, we demonstrate the energy-efficient point coordination function (PCF) operation of IEEE 802.11a wireless LAN (WLAN) via both transmit power control (TPC) and physical layer (PHY) rate adaptation. First, we derive the energy-consumption performance analytically for uplink data transmissions under the PCF. From the evaluation results, we observe that significant energy savings can be achieved by combining TPC with adaptive PHY rate selection. A key requirement for a transmitter to select the most energy-efficient combination of transmit power level and PHY rate is the knowledge of the path loss between the receiver and itself. We present a novel scheme for accurate path loss estimation in 802.11 WLAN. Results and conclusions presented in this paper can serve as a valuable guidance or reference for the design of future 5 GHz 802.11 WLAN systems.

Cache pre-filling is emerging as a new concept for increasing the availability of popular Web items in cache servers. According to this concept, Web items are sent by a "push-server" to the proxy cache servers, usually through a broadcast-based or a multicast-based distribution mechanism. One of the most difficult challenges is to design the scheduling algorithm of the push-server. This algorithm needs to determine the "broadcast scheduling map", namely which Web items to broadcast and when. In this paper we study the approach where every constant period of time each proxy cache analyzes the requests it has received in the past and determines which Web item it prefers to receive by broadcast and when. We formalize a related problem, called the "cache pre-filing push" (CPFP) problem, analyze its computational complexity, and describe efficient algorithms to solve it.

Optical burst switching (OBS) is an experimental network technology that enables the construction of very high capacity routers, using optical data paths and electronic control. In this paper, we study two designs for wavelength converting switches that are suitable for use in optical burst switching systems and evaluate their performance. Both designs use tunable lasers to implement wavelength conversion. One is a strictly nonblocking design, that also requires optical crossbars. The second substitutes wavelength grating routers (WGR) for the optical crossbars, reducing cost, but introducing some potential for blocking. We show how the routing problem for the WGR-based switches can be formulated as a combinatorial puzzle or game, in which the design of the game board corresponds to the pattern of interconnections used to join the input sections of the switch to the output sections. We use this to show how the interconnection pattern affects the performance of the switch, and to facilitate the design of interconnection patterns that yield the best performance. Our results show that for a typical switch configuration, the WGR-based design can deliver more than 87% of the throughput of a fully nonblocking switch.

In this paper, a new preemption policy is proposed and complemented with an adaptive scheme that aims to minimize rerouting. The preemption policy combines the three main optimization criteria: number of LSP to be preempted, priority of LSP to be preempted, and amount of bandwidth to be preempted. The preemption policy is complemented by an adaptive scheme that selects LSP with lower priority and reduces their rate in order to accommodate the new high-priority LSP setup request. Heuristics for both preemption and adaptive preemption policies are derived. Simulation results show the heuristics' accuracy. Performance comparisons of a non-preemptive approach, our preemption policy, the adaptive rate policy, and the policy in use by commercial routers are included.

High-aggregate bandwidth switches are those whose port count multiplied by the operating line rate is very high; for example, a 30 port switch operating at 40 Gbps or a 1000 port switch operating at 1 Gbps. Designing high-performance schedulers for such switches is challenging for the following reasons: (i) high performance requires finding good matchings; (ii) good matchings take time to find; (iii) in high-aggregate bandwidth switches there is either too little time (due to high line rates) or there is too much work to do (due to a high port count). We exploit the following features of the switching problem to devise simple-to-implement, high-performance schedulers: (a) the state of the switch (carried in the lengths of its queues) changes slowly with time, implying that heavy matchings will likely stay heavy over a period of time; (b) observing arriving packets conveys useful information about the state of the switch. These features are exploited using hardware parallelism and randomization to yield three scheduling algorithms for IQ (input-queued) switches - APSARA, LAURA and SERENA. These algorithms are shown to achieve 100% throughput and simulations show that their delay performance is quite competitive with respect to the maximum weight matching. The stability proof involves a derandomization procedure and uses methods which may have wider applicability.