Disaggregated memory (DM) architectures decouple compute servers (CSs) from memory servers (MSs) and rely on RDMA to provide low-latency access to remote memory. Building an efficient distributed B+Tree index for DM key–value (KV) stores is challenging: insert, delete, and update (IDU) operations must be highly concurrent without overloading MS CPUs, while structural modification operations (SMOs) such as splits and merges still require careful coordination. FAUNUS is a distributed B+Tree for RDMA-based DM KV-stores whose IDU fast path is non-blocking: IDU operations that do not trigger an SMO complete without acquiring locks, using only RDMA reads, writes, and atomics on compact KV-blocks that store a fingerprint and a pointer to an out-of-place KV-item. Conflicting IDUs on the same KV-block synchronize through RDMA compare-and-swap, allowing up to$C$concurrent non-conflicting IDUs per leaf, where$C$is the leaf capacity, while avoiding deadlocks due to failed or slow clients. SMOs are handled on a separate, infrequent slow path, where FAUNUS uses locks on internal nodes and leaves to safely perform structural changes. We evaluate FAUNUS with a detailed simulation-based analysis against state-of-the-art RDMA B+Tree designs such as Sherman and Marlin. FAUNUS reduces IDU latency, the number of RDMA operations, and RDMA atomic operations per IDU, while keeping SMOs rare under a wide range of workloads. As a result, overall performance is dominated by the non-blocking IDU fast path.

We propose PB-FS (Postcard-Based Fast Start), a rate initialization scheme that uses direct feedback from the switches to quickly correct the rates of new datacenter flows that begin at the line rate and cause congestion. PB-FS is designed to easily integrate into any datacenter congestion control protocol. We evaluate PB-FS in two datacenter environments: a lossless network that runs RoCE, and a lossy network that uses RDMA with selective repeat. We show that PB-FS significantly reduces tail latency of short flows while maintaining throughput, in both lossless and lossy datacenters.

QUIC is an emerging transport protocol, offering multiple advantages over TCP. We propose a novel 0-RTT-aware load balancing scheme for QUIC. The proposed scheme is scalable, resilient to 0 -RTT replay attacks, and guarantees perfect forward secrecy. It requires no modifications to the QUIC standard and it is QUIC version independent. 0-RTT is crucial for web performance, particularly on mobile networks. Our experiments show that it reduces the time-to-first-byte by half and the server load by 40% compared to 1-RTT, regardless of the network latency. Using both synthetic and real-world traffic traces, we show that the proposed load balancer guarantees near-optimal load balancing performance. It also guarantees faster time-to-first-byte and faster completion time compared to other load balancing schemes, such as least loaded, power-of-two-choices, and maximum session affinity.

SYN flooding is a simple and effective denial-of-service attack. In this attack, many TCP SYN requests are sent to the targeted server, in an attempt to consume its resources and make it unresponsive to legitimate traffic. While SYN attacks have traditionally targeted web servers, they are also known to be very harmful to intermediate cloud devices, and in particular to stateful load balancers (LBs). Fighting against a SYN attack without negatively affecting legitimate connections is not easy, especially if the LB needs to perform frequent server pool updates during the attack, which is very likely since attacks can often last for many hours or even days. This paper is the first to propose LB schemes that guarantee high throughput of one million connections per second, while supporting a high pool update rate without breaking connections and fighting against a high rate SYN attack. Using an analysis and a proof of concept, we show that the LB can handle up to 10 million fake SYNs per second when the RTT is 10ms, and up to 5 million fake SYNs per second when the RTT is 20ms.

A high performance Layer-4 load balancer (LB) is one of the most important components of a cloud service infrastructure. Such an LB uses network and transport layer information for deciding how to distribute client requests across a group of servers. A crucial requirement for a stateful LB is per connection consistency (PCC); namely, that all the packets of the same connection will be forwarded to the same server, as long as the server is alive, even if the pool of servers or the assignment function changes. The challenge is in designing a high throughput, low latency solution that is also scalable. This paper proposes a highly scalable LB, called Prism, implemented using a programmable switch ASIC. As far as we know, Prism is the first reported stateful LB that can process millions of connections per second and hundreds of millions connections in total, while ensuring PCC. This is due to the fact that Prism forwards all the packets in hardware, even during server pool changes,while avoiding the need to maintain a hardware state per every active connection. We implemented a prototype of the proposed architecture and showed that Prism can scale to 100 million simultaneous connections, and can accommodate more than one pool update per second.

SYN flooding is a simple and effective denial-of-service attack, in which an attacker sends many SYN requests to a target's server in an attempt to consume server resources and make it unresponsive to legitimate traffic. While SYN attacks have traditionally targeted web servers, they are also known to be very harmful to intermediate cloud devices, and in particular to stateful load balancers (LBs). We propose LB schemes that guarantee high throughput of one million connections per second, while supporting a high pool update rate without breaking connections, and fighting against a high rate SYN attack, of up to 10 million fake SYNs per second.

Inter-datacenter transfers of non-interactive but timely large flows over a private (managed) network is an important problem faced by many cloud service providers. The considered flows are non-interactive because they do not explicitly target the end users. However, most of them must be performed on a timely basis and are associated with a deadline. We propose to schedule these flows by a centralized controller, which determines when to transmit each flow and which path to use. Two scheduling models are presented in this paper. In the first, the controller also determines the rate of each flow, while in the second bandwidth is assigned by the network according to the TCP rules. We develop scheduling algorithms for both models and compare their complexity and performance.

In this paper, we consider the simultaneous connectivity of primary and secondary networks forming a cognitive model. It is assumed that the cognitive model includes guard zones that prevent the nodes of the secondary network from being active in the vicinity of primary nodes to limit interference. Under these assumptions, we characterize the region of densities, the transmission radii of the nodes in each of the networks, and the guard zones for which the two networks have a unique unbounded connected component. We prove that this model is feasible, that is, there exists simultaneous connectivity with the unique unbounded connected component in each of the networks. We also provide necessary and sufficient conditions for the simultaneous connectivity of this cognitive model.

Recent works have shown that it would be beneficial for nodes in wireless networks with very dynamic topology to maintain a list of 2-hop neighbors, namely, the neighbors of its neighbors. This is important, for example, for routing, clustering, and message dissemination to all the nodes in a given geographic vicinity. In this paper, we propose a scheme that uses Bloom filters for maintaining 2-hop neighborship information. Furthermore, we developed a novel 2-hop broadcast algorithm making use of the specific nature of our Bloom filter encoded neighbor information. We particularly focus on the Vehicular Ad Hoc Networks (VANETs) application scenario. Here, beaconing is a periodic broadcast of awareness messages by each vehicle to its immediate neighbors. A na€ıve approach would be to include all 2-hop neighbors in each beacon message, which, however, would work only for small or sparse scenarios. We show that our approach significantly reduces the length of the beacon messages, thereby keeping channel load and collision probability considerably lower than in the na€ıve scheme. We further demonstrate the application of our Bloom filter based 2-hop neighbor table for developing higher layer protocols and introduce a multi-hop broadcast protocol called Bloom Hopping.

Cardinality estimation algorithms receive a stream of elements, with possible repetitions, and return the number of distinct elements in the stream. Such algorithms seek to minimize the required memory and CPU resource consumption at the price of inaccuracy in their output. In computer networks, cardinality estimation algorithms are mainly used for counting the number of distinct flows, and they are divided into two categories: sketching algorithms and sampling algorithms. Sketching algorithms require the processing of all packets, and they are therefore usually implemented by dedicated hardware. Sampling algorithms do not require processing of all packets, but they are known for their inaccuracy. In this work we identify one of the major drawbacks of sampling-based cardinality estimation algorithms: their inability to adapt to changes in flow size distribution. To address this problem, we propose a new sampling-based adaptive cardinality estimation framework, which uses online machine learning. We evaluate our framework using real traffic traces, and show significantly better accuracy compared to the best known sampling-based algorithms, for the same fraction of processed packets.

Sampling is an expensive network resource, because switches and routers are able to sample only a small fraction of the traffic they receive. Modern switches and routers perform uniform packet sampling, which has several major drawbacks: 1) the same flow might be unnecessarily sampled multiple times in different switches; 2) all the flows traversing a switch whose sampling module is activated are sampled at the same rate; and 3) the sampling rate is fixed, even if the volume of the traffic changes. For the first time, we propose a sampling-on-demand monitoring framework. The proposed framework, presented as a component of software defined network (SDN), adds a sampling management module to the SDN controller. This module allows the controller to determine the sampling rate of each flow at each switch, according to the monitoring goals of the network operator, while taking into account the monitoring capabilities of the switch. As part of the proposed framework, the paper defines a new optimization problem called sampling allocation problem, which has to be solved by the sampling management module in order to maximize the total sampling utility. The paper presents online and offline algorithms for solving this problem. It also presents three real network management applications, executed over Mininet, which are shown to significantly benefit from the proposed framework.

A major building block of Vehicular Ad Hoc Networks (VANETs) is broadcasting: the use of wireless communication for sharing information among vehicles, or between the vehicles and infrastructure. Dozens of broadcast protocols have been developed in recent years, including protocols for 1-hop broadcasting of vehicle status information (beaconing) and for geocasting-based applications. However, most of these protocols were designed for one application and cannot co-exist, nor can one broadcast solution meet the demands of all applications. These observations motivated our effort to develop a holistic network layer for VANETs. We identify the need for making VANET broadcast context-aware, and for supporting four different classes of broadcast protocols, each with its own properties. These classes are not only able to co-exist on the same network layer, but also to complement one another's functionality. Thus, large applications as well as more holistic Transport protocols can be designed by combining two or more broadcast classes. We discuss the specific characteristics of these classes and design candidate protocols for each class.

In recent years there has been a growing interest in developing "streaming algorithms" for efficient processing and querying of continuous data streams. These algorithms seek to provide accurate results while minimizing the required storage and the processing time, at the price of a small inaccuracy in their output. A fundamental query of interest is the intersection size of two big data streams. This problem arises in many different application areas, such as network monitoring, database systems, data integration and information retrieval. In this paper we develop a new algorithm for this problem, based on the Maximum Likelihood (ML) method. We show that this algorithm outperforms all known schemes in terms of the estimation's quality (lower variance) and that it asymptotically achieves the optimal variance.

In this paper we analyze the connectivity of cognitive radio ad-hoc networks. Contrary to previous works, we pursue the connectivity of both the primary and secondary networks, a state we call “simultaneous connectivity”. We determine that if the networks are simultaneously connected then their infinite connected components are unique. In addition, we characterize the region of densities in which both the primary and secondary networks have a unique infinite connected component.

The construction of a logical network on top of a physical (optical) infrastructure involves two intertwined tasks: logical link selection-deciding which pairs of routers will be connected by logical links (lightpaths); and logical link routing-deciding how to route each logical link across the optical network. The operator of such networks is often required to maximize the available throughput while guaranteeing its restorability. This paper is the first to combine these seemingly conflicting goals into one optimization criterion: maximizing the restorable throughput of the end-to-end paths. We address this problem in three cases: when the operator has no knowledge of the future bandwidth demands, when it has partial knowledge, and when it has full knowledge. We present efficient algorithms for each of these cases and use extensive simulations to compare their performance.

In modern broadband cellular networks, the omnidirectional antenna at each cell is replaced by three or six directional antennas, one in every sector. While every sector can run its own scheduling algorithm, bandwidth utilization can be significantly increased if a joint scheduler makes these decisions for all the sectors. This gives rise to a new problem, referred to as “joint scheduling,” addressed in this paper for the first time. The problem is proven to be NP-hard, but we propose efficient algorithms with a worst-case performance guarantee for solving it. We then show that the proposed algorithms indeed substantially increase the network throughput.

Advanced wireless technologies such as multiple-input-multiple-output (MIMO) require each mobile station (MS) to send a lot of feedback to the base station. This periodic feedback consumes much of the uplink bandwidth. This expensive bandwidth is very often viewed as a major obstacle to the deployment of MIMO and other advanced closed-loop wireless technologies. This paper is the first to propose a framework for efficient allocation of periodic feedback channels to the nodes of a wireless network. Several relevant optimization problems are defined and efficient algorithms for solving them are presented. A scheme for deciding when the base station (BS) should invoke each algorithm is also proposed and shown through simulations to perform very well.

LTE Advanced and other 4G cellular standards allow relay nodes (RNs) to be deployed as a substitute for base stations (BSs). Unlike a BS, an RN is not directly connected to the backbone. Rather, each RN is associated with a donor BS, to which it is connected through the OFDMA wireless link. A very important task in the operation of a wireless network is packet scheduling. In a network with RNs, such scheduling decisions must be made in each cell not only for the BS, but also for the RNs. Because the scheduler in a network with RNs must take into account the transmission resources of the BS and the RNs, it needs to find a feasible schedule that does not exceed the resources of a multidimensional resource pool. This makes the scheduling problem computationally harder than in a network without RNs. In this paper, we define and study the packet-level scheduling problem for a network with RNs. This problem is not only NP-hard, but also admits no efficient polynomial-time approximation scheme. To solve it, we propose an efficient algorithm with a performance guarantee and a simple water-filling heuristic. To the best of our knowledge, our algorithm is the first packet-level scheduling algorithm that provides a performance guarantee for a network with RNs. Using simulations, we evaluate our new algorithms and show that they perform very well.

In many modern networks, such as datacenters, optical networks, and multiprotocol label switching (MPLS), the delivery of a traffic flow with a certain bandwidth demand over a single network path is either not possible or not cost-effective. In these cases, it is very often possible to improve the network's bandwidth utilization by splitting the traffic flow over multiple efficient paths. While using multiple paths for the same traffic flow increases the efficiency of the network, it consumes expensive forwarding resources from the network nodes, such as TCAM entries of Ethernet/MPLS switches and wavelengths/lightpaths of optical switches. In this paper, we define several problems related to splitting a traffic flow over multiple paths while minimizing the consumption of forwarding resources, and present efficient algorithms for solving these problems.

Communication networks are vulnerable to natural disasters, such as earthquakes or floods, as well as to physical attacks, such as an Electromagnetic Pulse (EMP) attack. Such real-world events happen at specific geographical locations and disrupt specific parts of the network. Therefore, the geographical layout of the network determines the impact of such events on the network's connectivity. Recent works focused on assessing the vulnerability of a deterministic (geographical) network to such events. Here, we focus on assessing the vulnerability of (geographical) random networks to such disasters and identifying the most vulnerable parts of a network where only partial (probabilistic) information about its geographical layout is given. We consider stochastic models in which nodes and links are probabilistically distributed geographically on a plane, and model the disaster event as a circular cut that destroys any node or link within or intersecting the circle. We develop algorithms for assessing the damage of such attacks and determining which attack locations have the most disruptive impact on the network. Our novel approach allows identifying locations which require additional protection efforts (e.g., equipment shielding). Overall, the paper demonstrates that using stochastic modeling and geometric probability techniques can significantly contribute to our understanding of network survivability and resilience.

LTE-advanced and other 4G cellular standards allow relay nodes (RNs) to be deployed as a substitute for base stations (BSs). Unlike a BS, an RN is not directly connected to the backbone. Rather, each RN is associated with a donor BS, to which it is connected through the OFDMA wireless link. A very important task in the operation of a wireless network is packet scheduling. In a network with RNs, such scheduling decisions must be made in each cell not only for the BS, but also for the RNs. Because the scheduler in a network with RNs must take into account the transmission resources of the BS and the RNs, it needs to find a feasible schedule that does not exceed the resources of a multi-dimensional resource pool. This makes the scheduling problem computationally harder than in a network without RNs. In this paper we define and study for the first time the packet-level scheduling problem for a network with RNs. This problem is shown to be not only NP-hard, but also very hard to approximate. To solve it, we propose an approximation with a performance guarantee, and a simple water-filling heuristic. Using simulations, we evaluate our new algorithms and show that they perform very well.

The construction of a logical network on top of a physical (optical) infrastructure involves two intertwined tasks: logical link selection - deciding which pairs of routers will be connected by logical links (lightpaths), and logical link routing - deciding how to route each logical link across the optical network. The operator of such networks is often required to maximize the available throughput while guaranteeing its restorability. This paper is the first to combine these seemingly conflicting goals into one optimization criterion: maximizing the restorable throughput of the end-to-end paths. We address this problem in three cases: when the operator has no knowledge of the future bandwidth demands, when it has partial knowledge, and when it has full knowledge. We present efficient algorithms for each of these cases and use extensive simulations to compare their performance.

We consider scheduling mechanisms for downlink multicasting of critical messages across cellular wireless systems. We study the robustness of such schemes following the failure of a macro base station (MBS) node. We determine whether the additional deployment of micro base station (mBS) nodes can enhance the system's performance. We assume MBS and mBS nodes to coordinate their multicast transmissions by using TDMA or FDMA (rather than an MBSFN-based) adaptive rate and power scheduling algorithms. Neighboring mBS and MBS nodes coordinate their operations to optimally configure their transmission schedules and spectral and/or temporal resources and transmit code rate and power levels. We show that, under low intersite distance (ISD) values, each identifying the distance between neighboring MBS nodes, the use of deployed mBS nodes does not enhance the system's attainable multicast spectral efficiency. Under intermediate ISD levels, the deployment of a backup mBS node that is located near the MBS node limits the post-failure degradation of throughput capacity rate to less than 10%. In turn, under longer ISD range levels, the combined use of a backup mBS and of neighboring mBS nodes, which adjust their code rate levels to reach mobiles located in the failed cell, leads to significant performance improvement.

In this paper, we define and study a new problem, referred to as the Dependent Unsplittable Flow Problem (D-UFP). We present and discuss this problem in the context of large-scale powerful (radar/camera) sensor networks, but we believe it has important applications on the admission of large flows in other networks as well. In order to optimize the selection of flows transmitted to the gateway, D-UFP takes into account possible dependencies between flows. We show that D-UFP is more difficult than NP-hard problems for which no good approximation is known. Then, we address two special cases of this problem: the case where all the sensors have a shared channel and the case where the sensors form a mesh and route to the gateway over a spanning tree.

Efficient multicasting of critical messages is of essential importance in public safety and commercial multimedia cellular networks. We study the effectiveness of using relay stations to enhance the spectral efficiency of multicast distribution in a mobile wireless networks. Coloring oriented adaptive rate scheduling algorithms are considered, including such that temporally employ TDMA schedules with reuse levels of 1, 3, 4 and 7 over a cellular arrangement. These schemes are used to regulate multicast transmissions executed by base station and (when employed) relay station nodes. We examine the utility of using in each cell single and double levels of placed relay stations. When the latter are employed, 2-hop and 3-hop relaying paths are considered. We also examine a cellular system that has experienced the failure of base stations, and identify the adaptive rate coloring-based scheduling mechanism that should be used when a failover operation is pursued. For both pre-failure and post-failure scenarios, we show that when the inter site distance (ISD), identifying the range between macro base stations, is lower than certain threshold levels, it is most effective to employ schedules that are based on direct (1-hop) multicast transmissions by base stations (BSs) to associated mobile station (MS) clients. In turn, under longer ISD ranges (e.g., as employed in less dense cellular layouts), the spectral efficiency of the system can be significantly enhanced by using a joint scheduling and routing scheme that makes use of multihop relaying.

Efficient multicasting of critical messages is of essential importance in public safety and commercial multimedia cellular networks. We study the effectiveness of using the aid of micro base stations (mBSs) to enhance the spectral efficiency of multicast distribution in a wireless cellular network. Coloring oriented adaptive rate scheduling algorithms are considered, including such that temporally employ TDMA schedules with reuse levels of 1, 3, 4 and 7 over a cellular arrangement. These schemes are used to regulate multicast transmissions executed by macro base stations (MBSs) and to jointly schedule macro and micro base stations (mBSs). We examine the utility of using the aid of mBSs in potentially improving multicasting performance. We also examine a cellular system that has experienced the failure of some MBSs, and identify the adaptive rate coloring-based scheduling mechanism that should be used when a failover operation is pursued. For both pre-failure and post-failure scenarios, we show the schemes with that are aided by mBSs to achieve higher system throughput levels. We also show that when the inter site distance (ISD), identifying the range between MBSs, is lower than a threshold level, reuse-3 scheduling schemes (with or without employing mBSs) yield better performance than reuse-1 schemes. In turn, under longer ISD ranges (e.g., as employed in less dense cellular layouts), the spectral efficiency of the system can be significantly enhanced by using a joint scheduling and routing scheme that makes use of reuse-1 scheme with the aid of mBSs.

An important trend in the evolution of cellular networks is the introduction of cost efficient small cells. However, most of these cells will have only wireless connectivity to the backbone. Consequently, handovers will be needed much more frequently and the bandwidth between neighboring cells will become a scarce resource. Both problems are likely to affect one of the most fast growing cellular applications: adaptive TCP video streaming. While the high handover rate is likely to have a negative impact on TCP streaming due to packet loss during handovers, solutions that forward packets from the old cell to the new one must limit the amount of wireless bandwidth they use. This trade-off is addressed in the following paper.

In this paper we define and study a new problem, referred to as the Dependent Unsplittable Flow Problem (D-UFP). We present and discuss this problem in the context of large-scale powerful (radar/camera) sensor networks, but we believe it has important applications on the admission of large flows in other networks as well. In order to optimize the selection of flows transmitted to the gateway, D-UFP takes into account possible dependencies between flows. We show that D-UFP is more difficult than NP-hard problems for which no good approximation is known. Then, we address two special cases of this problem: the case where all the sensors have a shared channel and the case where the sensors form a mesh and route to the gateway over a spanning tree.

This paper deals with efficient location-based decision-supporting content distribution to mobile groups. We consider the case where a set of information dissemination devices (IDDs) broadcast a limited amount of location-based information to passing mobile nodes that are moving along well-defined paths. We develop a novel model that captures the main aspects of the problem and define a new optimization problem we call Maximum Benefit Message Assignment Problem (MBMAP). We study several variants of this problem in the case where the IDDs are cooperative and in the case where they are not. We develop new approximation algorithms for these variants and then focus on the practical effects of using them in realistic networking scenarios.

In an OFDMA network, the modulation and coding scheme (MCS) of the messages sent to the mobile stations (MSs) varies according to channel condition. To determine the appropriate MCS level, the base station (BS) allocates to every active MS a CQI (Channel Quality Information) channel. The CQI bandwidth is a scarce resource whose allocation must be adjusted to the actual needs of the MSs. However, allocations and deallocations of CQI channels require expensive signaling messages between the BS and the MSs, and therefore should be minimized. In this paper we propose a framework for the management of the CQI bandwidth by the BS. We identify three related optimization problems and propose efficient algorithms for solving them.

This paper studies the problem of energy efficient routing in a sensor network with multiple gateways. Due to the complexity of this problem, we divide it into two sub-problems: the problem of constructing efficient routing trees and the problem of wake-up frequency assignment in a network with multiple routing trees. For the first problem we present an optimal algorithm and an approximation algorithm that achieves very close performance but can be more easily implemented. We prove that the second problem is NP-hard and propose a polynomial time approximation algorithm.

In response to the high throughput needs of grid and cloud computing applications, several production networks have recently started to support advance reservation of dedicated circuits. An important open problem within this context is to devise advance reservation algorithms that can provide provable throughput performance guarantees independently of the specific network topology and arrival pattern of reservation requests. In this paper, we first show that the throughput performance of greedy approaches, which return the earliest possible completion time for each incoming request, can be arbitrarily worse than optimal. Next, we introduce two new online, polynomial-time algorithms for advance reservation, called BatchAll and BatchLim. Both algorithms are shown to be throughput-optimal through the derivation of delay bounds for 1 + ε bandwidth augmented networks. The BatchLim algorithm has the advantage of returning the completion time of a connection immediately as a request is placed, but at the expense of looser delay performance than BatchAll. We then propose a simple approach that limits path dispersion, i.e., the number of parallel paths used by the algorithms, while provably bounding the maximum reduction factor in the transmission throughput. We prove that the number of paths needed to approximate any flow is quite small and never exceeds the total number of edges in the network. Through simulation for various topologies and traffic parameters, we show that the proposed algorithms achieve reasonable delay performance, even at request arrival rates close to capacity bounds, and that three to five parallel paths are sufficient to achieve near-optimal performance.

In most sensor networks, the nodes are static. Nevertheless, node connectivity is subject to changes because of disruptions in wireless communication, transmission power changes, or loss of synchronization between neighboring nodes. Hence, even after a sensor is aware of its immediate neighbors, it must continuously maintain its view, a process we call continuous neighbor discovery. In this work, we distinguish between neighbor discovery during sensor network initialization and continuous neighbor discovery. We focus on the latter and view it as a joint task of all the nodes in every connected segment. Each sensor employs a simple protocol in a coordinate effort to reduce power consumption without increasing the time required to detect hidden sensors.

Communication networks are vulnerable to natural disasters, such as earthquakes or floods, as well as to physical attacks, such as an electromagnetic pulse (EMP) attack. Such real-world events happen in specific geographical locations and disrupt specific parts of the network. Therefore, the geographical layout of the network determines the impact of such events on the network's connectivity. In this paper, we focus on assessing the vulnerability of (geographical) networks to such disasters. In particular, we aim to identify the most vulnerable parts of the network. That is, the locations of disasters that would have the maximum disruptive effect on the network in terms of capacity and connectivity. We consider graph models in which nodes and links are geographically located on a plane. First, we consider a simplistic bipartite graph model and present a polynomial-time algorithm for finding a worst-case vertical line segment cut. We then generalize the network model to graphs with nodes at arbitrary locations. We model the disaster event as a line segment or a disk and develop polynomial-time algorithms that find a worst-case line segment cut and a worst-case circular cut. Finally, we obtain numerical results for a specific backbone network, thereby demonstrating the applicability of our algorithms to real-world networks. Our novel approach provides a promising new direction for network design to avert geographical disasters or attacks.

We consider a huge hierarchical sensor network consisting of millions of sensors arranged in clusters for scalability and cost-performance. We address the problem of how a centralized gateway can estimate the number of sensors affected by a certain event. We propose a scheme for solving this problem in the most efficient way in terms of communication cost, and a complete mathematical analysis of the estimation error. We show that the error of the new scheme is very small even if the number of sensors experiencing an event is several million.

In this paper, we define and address a new problem that arises when a base station in a broadband wireless network wishes to multicast information to a large group of nodes and to guarantee some level of reliability using Application-layer forward error correction (FEC) codes. Every data block to be multicast is translated into a sequence of packets, from which every receiver must receive at least in order to correctly decode the block. The new problem is to determine which PHY-layer modulation and coding scheme (MCS) the base station should use for each packet. We present several variants of this problem, which differ in the number of automatic repeat request (ARQ) rounds during which the delivery of a data block must be completed. Most of these variants are shown to be NP-hard. However, we present optimal solutions for practical instances, where the number of MCSs is small, and efficient approximations and heuristics for the general case of each variant.

The paper deals with efficient distribution of timely information to flows of mobile devices. We consider the case where a set of information dissemination devices (IDDs) broadcast a limited amount of information to passing mobile nodes that are moving along well-defined paths. This is the case, for example, in intelligent transportation systems. We develop a novel model that captures the main aspects of the problem, and define a new optimization problem we call MBMAP (maximum benefit message assignment problem). We study the computational complexity of this problem in the global and local cases, and provide new approximation algorithms.

In this paper we define and address a new problem that arises when a base station in a broadband wireless network wishes to multicast information to a large group of nodes and to guarantee some level of reliability using Application layer FEC codes. Every data block to be multicast is translated into a sequence of K + n packets, from which every receiver must receive at least K in order to correctly decode the block. The new problem is to determine which PHY layer MCS (Modulation and Coding Scheme) the base station should use for each packet. We present several variants of this problem, which differ in the number of ARQ (Automatic Repeat reQuest) rounds during which the delivery of a data block must be completed. Most of these variants are shown to be NP-hard. However, we present optimal solutions for practical instances, where the number of MCSs is small, and efficient approximations and heuristics for the general case of each variant.

We present a generic scheme for estimating the size of a group of nodes affected by the same event in a large-scale network, such as a grid, a sensor network or a wireless broadband access network, while receiving only a small number of feedback messages from this group. Using the proposed scheme, a centralized gateway analyzes the transmission times of these feedback messages, defines a likelihood function for them, and then uses the Newton-Raphson method to find the number of affected nodes for which this function is maximized. We present complete mathematical analysis for the precision of the proposed algorithm and provide tight upper and lower bounds for the estimation error. These bounds allow us to improve the precision of our estimation, and to bring the error very close to 0.

Communication networks are vulnerable to natural disasters, such as earthquakes or floods, as well as to physical attacks, such as an Electromagnetic Pulse (EMP) attack. Such real- world events happen in specific geographical locations and disrupt specific parts of the network. Therefore, the geographical layout of the network determines the impact of such events on the network's connectivity. In this paper, we focus on assessing the vulnerability of (geographical) networks to such disasters. In particular, we aim to identify the most vulnerable parts of the network. That is, the locations of disasters that would have the maximum disruptive effect on the network in terms of capacity and connectivity. We consider graph models in which nodes and links are geographically located on a plane, and model the disaster event as a line segment or a circular cut. We develop algorithms that find a worst- case line segment cut and a worst-case circular cut. Then, we obtain numerical results for a specific backbone network, thereby demonstrating the applicability of our algorithms to real-world networks. Our novel approach provides a promising new direction for network design to avert geographical disasters or attacks.

We propose a new cross-layer mechanism, referred to as route-control, for mobile ad-hoc networks (MANETs). This mechanism, which works in the network and transport layers, aims at enhancing the performance of MANETs' reliable transport protocols. The main idea behind the proposed mechanism is to notify the sender when the packets of a Transport layer flow change their route. We show that the sender can benefit from this information when deciding whether to retransmit a missing segment or to wait, when estimating the RTT (Round Trip Time), and when deciding whether to change the congestion window.

OFDMA is one of the most important modulation and access methods for the future mobile networks. Before transmitting a frame on the downlink, an OFDMA base station has to invoke an algorithm that determines which of the pending packets will be transmitted, what modulation should be used for each of them, and how to construct the complex OFDMA frame matrix as a collection of rectangles that fit into a single matrix with fixed dimensions. We propose efficient, and theoretically best possible, algorithms that solves this intricate OFDMA scheduling problem by breaking it down into two sub-problems, referred to as macro and micro scheduling. We analyze the computational complexity of these sub-problems and develop efficient algorithms for solving them.

MPLS recovery mechanisms are increasing in popularity because they can guarantee fast restoration and high QoS assurance. Their main advantage is that their backup paths are established in advance, before a failure event takes place. Most research on the establishment of primary and backup paths has focused on minimizing the added capacity required by the backup paths in the network. However, this so-called spare capacity allocation (SCA) metric is less practical for network operators who have a fixed capacitated network and want to maximize their revenues. In this paper we present a comprehensive study on restorable throughput maximization in MPLS networks. We present the first polynomial-time algorithms for the splittable version of the problem. For the unsplittable version, we provide a lower bound for the approximation ratio. We present efficient heuristics which are shown to have excellent performance. One of our most important conclusions is that when one seeks to maximize revenue, local recovery should be the recovery scheme of choice.

In most sensor networks the nodes are static. Nevertheless, the node connectivity is subject to changes because of disruptions in wireless connectivity, transmission power changes, or loss of synchronization between neighboring nodes. Hence, even after a sensor is aware of its immediate neighbors, it must continuously maintain its view, a process we call topology maintenance. This work is the first to distinguish between neighbor discovery during sensor network initialization and topology maintenance. Whereas many works focus on the former task, we focus on the latter. We view topology maintenance as a joint task of all the connected sensors. Each sensor employs a simple protocol in a coordinate effort to reduce power consumption without increasing the time required to detect hidden sensors.

A number of recent studies concern algorithms for distributed control and coordination in systems of autonomous mobile robots. The common theoretical model adopted in these studies assumes that the positional input of the robots is obtained by perfectly accurate visual sensors, that robot movements are accurate, and that internal calculations performed by the robots on (real) coordinates are perfectly accurate as well. The current paper concentrates on the effect of weakening this rather strong set of assumptions and replacing it with the more realistic assumption that the robot sensors, movement, and internal calculations may have slight inaccuracies. Specifically, the paper concentrates on the ability of robot systems with inaccurate sensors, movements, and calculations to carry out the task of convergence. The paper presents several impossibility theorems, limiting the inaccuracy levels that still allow convergence, and prohibiting a general algorithm for gathering, namely, meeting at a point, in a finite number of steps. The main positive result is an algorithm for convergence under bounded measurement, movement, and calculation errors.

A finite automaton, simply referred to as a robot , has to explore a graph, that is, visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph, nor of its size. It is known that for any k -state robot, there exists a graph of maximum degree 3 that the robot cannot explore. This article considers the effects of allowing the system designer to add short labels to the graph nodes in a preprocessing stage, for helping the exploration by the robot. We describe an exploration algorithm that, given appropriate 2-bit labels (in fact, only 3-valued labels), allows a robot to explore all graphs. Furthermore, we describe a suitable labeling algorithm for generating the required labels in linear time. We also show how to modify our labeling scheme so that a robot can explore all graphs of bounded degree, given appropriate 1-bit labels. In other words, although there is no robot able to explore all graphs of maximum degree 3, there is a robot R, and a way to color in black or white the nodes of any bounded-degree graph G , so that R can explore the colored graph G . Finally, we give impossibility results regarding graph exploration by a robot with no internal memory (i.e., a single-state automaton).

In this paper we define a new problem that has not been addressed in the past: the trade-off between energy efficiency and throughput for multicast services in 802.16e or similar mobile networks. In such networks, the mobile host can reduce its energy consumption by entering the sleep mode when it is not supposed to receive or transmit information. For unicast applications the trade-off between delay and energy efficiency has been extensively researched. However, for mobile hosts running multicast (usually push- ased) applications, it is much more difficult to determine when data should be transmitted by the base-station and when each host should enter the sleep mode. In order to maximize the channel throughput while limiting energy consumption, a group of hosts needing similar data items should be active during the same time intervals. We define this as an optimization problem, and present several algorithms for it. We show that the most efficient solution is the one that employs cross-layer optimization by dividing the hosts into groups according to the quality of their downlink PHY channels.

Wireless Sensor Networks (WSNs) provide an important means of monitoring the physical world, but their limitations present challenges to fundamental network services such as routing. In this work we utilize an abstraction of WSNs based on the theory of identifying codes. This abstraction has been useful in recent literature for a number of important monitoring problems, such as localization and contamination detection. In our case, we use it to provide a joint infrastructure for efficient and robust monitoring and routing in WSNs. Specifically, we provide an efficient and distributed algorithm for generating robust identifying codes with a logarithmic performance guarantee based on a novel reduction to the set k-multicover problem; to the best of our knowledge, this is the first such guarantee for the robust identifying codes problem, which is known to be NP-hard. We also show how this same identifying-code infrastructure provides a natural labeling that can be used for near-optimal routing with very small routing tables. We provide experimental results for various topologies that illustrate the superior performance of our approximation algorithms over previous identifying code heuristics.

This paper presents an algorithm for maximizing the lifetime of a sensor network while guaranteeing an upper bound on the end-to-end delay. We prove that the proposed algorithm is optimal, and that it requires simple computing operations that can be implemented by simple devices. To the best of our knowledge, this is the first paper to propose a sensor wake-up frequency that depends on the sensor's location in the routing paths. Using simulations, we show that the proposed algorithm significantly increases the lifetime of the network, while guaranteeing maximum end-to-end delay.

Network services are provided by means of dedicated service gateways, through which traffic flows are directed. Existing work on service gateway placement has been primarily focused on minimizing the length of the routes through these gateways. Only limited attention has been paid to the effect these routes have on overall network performance. We propose a novel approach for the service placement problem, which takes into account traffic engineering considerations. Rather than trying to minimize the length of the traffic flow routes, we take advantage of these routes in order to enhance the overall network performance. We divide the problem into two sub-problems: finding the best location for each service gateway, and selecting the best service gateway for each flow. We propose efficient algorithms for both problems and study their performance. Our main contribution is showing that placement and selection of network services can be used as effective tools for traffic engineering.

We introduce a new algorithmic framework for advanced channel reservation in ultra high speed networks, called Graded Channel Reservation (GCR). GCR allows users to specify minimum bandwidth and duration requirements for their connections. GCR returns the highest graded path, selected according to a general, multi-criteria optimization objective. In particular, if the optimization criterion is delay, we prove that GCR returns the earliest time available to establish the connection. The computational complexity is polynomial in the size of the graph and the number of pending requests. We introduce a number of variants to GCR, including one that that provides the capability to switch between different paths during a connection. We present practical methods for minimizing or limiting the number of path switches. Through extensive simulations, we evaluate the performance of GCR and its variants under various topological settings and applications workload. Our results show that, for certain traffic parameters, optimized path selection combined with path switching can reduce the average delay of requests by an order of magnitude and increase the saturation throughput by as much as 50%. I.

In this paper we define a new problem that has not been addressed in the past: the trade-off between energy efficiency and throughput for multicast services in 802.16e or similar mobile networks. In such networks, the mobile host can reduce its energy consumption by entering the sleep mode when it is not supposed to receive or transmit information. For unicast applications the trade-off between delay and energy efficiency has been extensively researched. However, for mobile hosts running multicast (usually push-based) applications, it is much more difficult to determine when data should be transmitted by the base-station and when each host should enter the sleep mode. In order to maximize the channel throughput while limiting energy consumption, a group of hosts needing similar data items should be active during the same time intervals. We define this as an optimization problem, and present several algorithms for it. We show that the most efficient solution is the one that employs cross-layer optimization by dividing the hosts into groups according to the quality of their downlink PHY channels.

This paper considers the convergence problem in autonomous mobile robot systems. A natural algorithm for the problem requires the robots to move towards their center of gravity. This paper proves the correctness of the gravitational algorithm in the fully asynchronous model. It also analyzes its convergence rate and establishes its convergence in the presence of crash faults.

We present a scheme for allocating unsolicited grants to the end hosts of synchronous applications of a wireless access network, in accordance with the condition of the channel, the importance of each packet and the specific loss recovery mechanism employed in the channel. The proposed scheme is generic in the sense that it maximizes the effectiveness of the channel under various conditions and it can he used along with every FEC-based or retransmission-based error recovery strategy

In this paper we study the computational complexity and effectiveness of a concept, we term "N-hub shortest-path routing" in IP networks. N-hub shortest-path routing allows the ingress node of a routing domain to determine up to N intermediate nodes ("hubs") through which a packet will traverse before reaching its final destination. This facilitates better utilization of the network resources, while allowing the network routers to continue to employ the simple and well-known shortest-path routing paradigm. This concept has been suggested in the past but this paper is the first to offer an in-depth investigation of it. We apply this concept to the routing problem of minimizing the maximum load in the network. We show that the resulting routing problem is a difficult (NP-complete) problem and that it is also hard to approximate. However, we propose efficient algorithms for solving this problem both in the online and the offline contexts. Our results show that N-hub shortest-path routing can increase the network utilization significantly even for N=1. Hence, this routing paradigm should be considered as a powerful mechanism for the future datagram routing in the Internet.

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.

The paper proposes local and global optimization schemes for efficient TCP buffer allocation in an HTTP server. The proposed local optimization scheme dynamically adjusts the TCP send-buffer size to the connection and server characteristics. The global optimization scheme divides a certain amount of buffer space among all active TCP connections. These schemes are of increasing importance due to the large scale of TCP connection characteristics. The schemes are compared to the static allocation policy employed by a typical HTTP server and shown to achieve considerable improvement to server performance and better utilization of its resources. The schemes require only minor code changes and only at the server.

Network layer multicast is know as the most efficient way to support multicast sessions. However, for security, QoS and other considerations, most of the real-time application protocols can be better served by upper layer (transport or application) multicast. We propose a scheme called M-RTP for multicast RTP sessions. The idea behind this scheme is to set up the multicast RTP session over a set of unicast RTP sessions, established between the various participants (source and destinations) of the multicast session. We then address the issue of finding a set of paths with maximum bottleneck for an M-RTP session. We show that this problem is NP-complete, and propose several heuristics to solve it.

We propose a framework for the creation and maintenance of multicast trees in hierarchical ATM networks. This framework aims at coping with an inherent difficulty of topology aggregation in such networks. The main idea of the proposed framework is to distribute the tree topology information among a set of hierarchical multicast group servers (MGS) nominated for each multicast tree, while keeping regions that do not have a member in the multicast group unaware of the tree. The framework can be employed with every multicast routing algorithm designed for non-hierarchical networks.

TCP suffers from low performance over asynchronous transfer mode (ATM) networks. This is mainly because during phases of congestion, ATM drops cells without taking into account the effect this has on the upper layer protocols. Two main algorithms, called PPD and EPD, were proposed in the past for improving TCP performance. However they address one aspect of the problem, that has only small effect on the final performance. In this paper we propose an enhanced method for packet discard, called balanced packet discard (BPD), that improves TCP performance dramatically on congested networks and guarantees fairness among multiple connections. We show that BPD increases TCP throughput by more than 25% compared to EPD/PPD.

A virtual private network (VPN) is a private data network that uses a nonprivate data network to carry traffic between remote sites. An "Intranet VPN" establishes network layer connectivity between remote Intranet sites by creating an IP overlay network over the nonprivate network, using various tunneling mechanisms. There are two approaches for establishing such tunnels: a "CPE-based approach" and a "network-based approach." In the first approach, tunnels are established only between the CPE devices, whereas in the second approach tunnels are also established between the routers of the core nonprivate network. In this paper we address the problem of determining a CPE-based and a network-based layout of VPN tunnels while taking into account two factors: the cost of the links over which the VPN tunnels are established and the cost of the core routers that serve as end points for the VPN. We define related graph algorithm problems, analyze their complexity, and present heuristics for solving these problems efficiently.

When an ATM node discovers that it cannot continue the setup of a virtual channel under the requested QoS, it initiates a back-tracking procedure called "crankback". We propose a novel scheme, referred to as crankback prediction, that decreases the crankback overhead. Under the proposed scheme, nodes check during the connection admission control procedure whether the establishment of a virtual channel has a good chance to be admitted over the entire designated route. If this is not the ease, crankback is initiated even before a certain QoS parameter is exceeded.

One of the proposed solutions for increasing the speed of Internet access is to connect the home user to a direct satellite channel, at a speed 20 times faster than that of an average telephone modem. Communication over satellite links is often characterized by sporadic high bit-error rates and burst losses. This is especially true when working in the Ka band, where weather conditions greatly affect link availability. Under such conditions, the TCP protocol that is predominantly used by data applications degrades dramatically in performance. Using simulations, this paper studies the performance of TCP under different network conditions. Several modifications, that take advantage of the special properties of the satellite channel, are proposed, and a new sender algorithm which can efficiently handle burst losses is presented. The main attractiveness of the proposed new sender algorithm is that it can be implemented only at the satellite ground station, rather than at every server in the world.

ATM private network-to-network interface (PNNI) is a hierarchical and dynamic link-state routing protocol, designed to scale to the largest possible ATM networks, encompassing thousands of nodes. This paper investigates the route computation load imposed by the PNNI routing scheme, and shows that this load is unevenly distributed among the network nodes. More specifically, the routing computation load associated with the setup of a single virtual path grows exponentially with the hierarchy level. As a result, some of the network nodes-mainly those that function as border nodes of high levels-may be overloaded with route computation, while other nodes are rarely involved in this process. This paper also proposes a possible scheme for spreading the route computation burden more evenly. According to this scheme, heavily loaded nodes transfer route computation tasks to lightly loaded nodes.

The paper proposes local and global optimization schemes for efficient TCP buffer allocation in an HTTP server. The proposed local optimization scheme dynamically adjusts the TCP send-buffer size to the connection and server characteristics. The global optimization scheme divides a certain amount of buffer space among all active TCP connections. These schemes are of increasing importance due to the large scale of TCP connection characteristics. The schemes are compared to the static allocation policy employed by a typical HTTP server and shown to achieve considerable improvement to server performance and better utilization of its resources. The schemes require only minor code changes and only at the server.

The paper addresses the problem of designing efficient scheduling policies for the transmission of control messages by hierarchical network protocols. Such protocols encounter a tradeoff between the desire to forward a control message across the tree as soon, as it is received, and the desire to reduce control traffic. Scheduling problems that arise in this context are defined and discussed. The paper mainly concentrates on minimizing the average extra delay encountered by the control messages under an upper bound on the number of outgoing messages a node can send during a fixed period of time. A polynomial-time algorithm is presented for the off-line version of the problem, and then several efficient on-line heuristics are presented and compared.

The paper addresses the issue of minimizing the number of nodes involved in routing over a multicast tree and in the maintenance of such a tree in a datagram network. It presents a scheme where the tree routing and maintenance burden is laid only upon the source node and the destination nodes associated with the multicast tree. The main concept behind this scheme is to view each multicast tree as a collection of unicast paths and to locate only the multicast source and destination nodes on the junctions of their multicast tree. The paper shows that despite this restriction, the cost of the created multicast trees is not necessarily higher than the cost of the trees created by other algorithms that do not impose the restriction and therefore require all nodes along the data path of a tree to participate in routing over the tree and in the maintenance of the tree.

Motivated by the phenomenal growth of the Internet in recent years, a number of cable operators are in the process of upgrading their cable networks to offer data services to residential subscribers, providing them direct access to a variety of community content as well as to the Internet. Using cable modems that implement sophisticated modulation-demodulation circuitry, these services promise to offer a several hundredfold increase in access speeds to the home compared to conventional telephone modems. Initial experiences indicate that cable networks are susceptible to a variety of radio-frequency (RF) impairments that can result in significant packet loss during data communication. In the face of such losses, the transmission control protocol (TCP) that is predominantly used by data applications degrades dramatically in performance. Consequently, subscribers of broad-band data services may not perceive the projected hundredfold increase in performance. We analyze the performance of TCP under different network conditions using simulations and propose simple modifications that can offer up to threefold increase in performance in access networks that are prone to losses. These modifications require only minor changes to TCP implementations at the local network servers alone (and not at subscribers' PCs).

The paper addresses the issue of minimizing the number of nodes involved in the routing over a multicast tree and in the maintenance of such a tree in a datagram network. It presents a scheme where the tree routing and maintenance burden is laid only upon the source node and the destination nodes associated with the multicast tree. The main concepts behind this scheme is to view each multicast tree as a collection of unicast paths, and to locate only the multicast source and destination nodes on the junctions of their multicast tree. The paper shows that despite of this restriction, the cost of the created multicast trees is not necessarily higher than the cost of the trees created by other algorithms that do not impose the restriction and therefore require all the nodes along the data path of a tree to participate in the routing over the tree and in the maintenance of the tree.

SSCOP is a new data link control protocol designed for ATM networks. To achieve high throughput, SSCOP uses the selective repeat retransmission policy, enforced using the exchange of POLL and STAT control frames between the sender and the receiver. To avoid unnecessary retransmission of information frames (I-frames), SSCOP uses the "checkpoint concept" where every POLL has a sequence number and every outstanding I-frame is associated in the sender buffers with the sequence number of the POLL sent before the last transmission of that I-frame. Using these sequence numbers, the sender knows to ignore unnecessary retransmission requests. The paper proposes an improved scheme for avoiding unnecessary retransmission of I-frames. The new scheme significantly reduces the memory needed for storing control information of the protocol at the sender interface. Compared with the SSCOP, the only potential drawback of the proposed scheme is that under certain circumstances the retransmission of lost I-frames may be delayed. However, the paper analyzes the sequence of events that must take place in such a case, and concludes that the probability for such a sequence is negligible and that the new protocol performs as well as the SSCOP.

A video-on-demand (VoD) system provides a service which enables a user of the system to request in real time the transmission of a video stream from a collection of available video material. This paper suggests a conceptual model that subclassifies the VoD control and management procedures into three management levels: session, call, and connection. The session management is represented by a finite state machine (FSM) that translates user commands into call layer activities. The states in the session FSM represent active calls between the set-top boxes (STBs) and other entities, whereas the arcs represent distributed protocols for set-up and take-down of calls. This model is used in order to analyze the relationship between the procedures in the various management levels and to discuss the options and trade-offs involved in the design of a VoD session.

Asynchronous transfer mode (ATM) is a connection-oriented technology in which all communication is based on virtual connections established prior to the transfer of data. It is expected that the bulk of traffic carried by the ATM network will be data traffic, e.g., local area network (LAN) internetwork traffic. Hence, a major issue regarding ATM is the support for connectionless (datagram) traffic. A scheme for the efficient support for connectionless traffic in ATM LANs based on trees of virtual connections is proposed. In this scheme, a sink tree is built for every switch in the LAN. Each tree provides an efficient means of routing connectionless traffic from any switch in the network to the sink switch (root) of the tree. The sink tree solution may also be used to broadcast connectionless messages in the reverse direction. The trees can easily be updated to adapt to topological changes or congestion in the network. A protocol for refreshing the tree structure using the ATM switch routing tables is described. An adaptive rate control solution, in conjunction with fast back pressure at the ATM layer, is presented. It is shown that this scheme achieves high utilization of available bandwidth for connectionless traffic, has low cell loss probability, and small overhead.

This paper presents a new source routing technique for ring and multi-ring networks, which uses short address labels. The main objectives for having this new method are that in case of one or more failures a frame will be guaranteed: (1) to be removed from the ring-termination property, and (2) to be copied at most once and only by its destinations-safety property. The scheme is based on dividing the label address space of each ring into subspaces, such that the address subspaces are physically disjoint. More specifically, each ring, in a multi-ring network, is divided into two or more parts such that adjacent address subspaces are disjoint. The route of each frame is described by a sequence of short address labels in the frame's header. The current route of a frame is determined by the first address label in its header, and it can be used for routing over at most one subspace of the ring.>

Traditional communication networks reroute connections following link or node failures. This can be regarded as forced rerouting. The next generation ATM networks are supposed to be more intelligent and to offer more services than existing networks. An intelligent network may sometimes decide to reroute a connection whose virtual channel is still alive. This can be regarded as intentional rerouting. The present paper deals with intentional rerouting of ATM connections. It shows that intentional rerouting can ensure cell FIFO and integrity. Then several possible applications of intentional rerouting are suggested and discussed.>

In computer networks there is usually a trade-off between the performance and implementation complexity of the routing protocol, and those of the protocol for reliable transmission of data. Often, the routing protocol can perform better if it is not required to retain the FIFO order of the routed data units. However, in such a case the protocol for reliable transmission of data has to maintain many logical timers and to have an accurate estimate of the round trip delay. The paper introduces a new notion: semi-FIFO service, which means that the routing layer retains the FIFO order in part. The paper shows that sometimes a non-FIFO routing layer may easily provide for a semi-FIFO service, without changing the routing concept. Then, at proposes a new protocol for reliable transmission of data over an unreliable semi-FIFO routing layer. The protocol uses only one logical timer and does not require an estimate of the round trip delay in order to operate with maximum capacity. Therefore, the contribution of the paper is eliminating the deficiencies associated with a non-FIFO routing layer that may offer a semi-FIFO service.>

ATM is a connection-oriented technology in which all communication is based on virtual connections established prior to the transfer of data. Initially, it is expected that the bulk of traffic carried by the ATM network will be data traffic. Hence, a major issue regarding ATM is the support for connectionless (datagram) traffic. A scheme for the efficient support for connectionless traffic in ATM LANs based on trees of virtual connections is proposed. In this scheme a sink tree is built for every switch in the LAN. Each tree provides an efficient means of routing connectionless traffic from any switch in the network to the sink switch (root) of the tree. The sink tree solution may also be used to broadcast connectionless messages in the reverse direction. The trees can easily be updated to adapt to topological changes or congestion in the network. A protocol for refreshing the tree structure using the ATM switch routing tables is described.>

In ATM networks, two levels of connections are defined: virtual path connections and virtual channel connections. Virtual paths are the building blocks of the virtual channels. This hierarchy, known as "the virtual path concept", provides considerable advantages in the design of high-speed networks. In the paper the authors show that this concept has the advantage of providing a means of improving the survivability of virtual channels. To this end, they present a simple rerouting protocol, which can be invoked upon the failure of an intermediate link or node of a virtual path. This protocol reroutes all the affected virtual channels to an alternative virtual path. Due to the simplicity of the protocol, it can be completed rapidly, thus fulfilling an essential requirement of any rerouting scheme.>

Source routing requires that the source station knows a route to the destination. The paper presents a new bridge protocol for route discovery in multiple-ring networks, where several token-rings are connected by bridges. The protocol gives to the source station an indication of the availability of a route to the destination. If such a route exists, the source is supplied with a description/spl mdash/a list of ring and bridge identities/spl mdash/of the route that is fastest at the time of protocol execution. The main advantage of the new route discovery protocol over the existing one is its communication efficiency: the number of frames used is the sum of the number of rings and number of bridges in the network, as opposed to the exponential function required in the existing protocol. Another advantage of the new protocol is its option that allows determining routes to multiple destinations, thus supporting efficient multicast source routing.>

A new MAC protocol for route discovery in multiple-ring network, called the FTRD-protocol, was introduced in Part I. The present paper shows how the FTRD-protocol can find a description of a tree that spans a group of destinations. By placing such a description in the header of its frame, a source station can efficiently multicast the frame to the destination group. This requires no change in the operation of the source routing bridges. Another issue addressed in the paper is the recovery of the FTRD-protocol from error and failure conditions. When a bridge or the source suspects that the protocol is dead-locked, it initiates an independent recovery protocol that clears the network and prepares it for a new execution of the FTRD-protocol. The last issue addressed in the paper is the execution of the FTRD-protocol in a network with high-speed rings. The problem in such a network is that the bridges do not have sufficient time, after recognizing the route identity, to look in the local table and decide whether the relevant fields in the received frame need to be altered.>

Describes a new media access control protocol, the multiple-token protocol, for high-speed ring networks. The purpose of this protocol is to increase the throughput of a token-ring under heavy load, and to decrease the access delay under light load. The protocol maintains several logical token-rings in the single physical ring. The number of logical rings can be changed dynamically by the ring stations according to the ring load. Each logical ring has its own token, and its operation is close to a token ring with early-token-release and destination removal. Multiple tokens enable multiple simultaneous transmissions of new frames by different stations and decrease the waiting for a token delay. However, the integration of several token rings in a single media is not straightforward since they interfere with the operation of each other. The present protocol is not the first to enable multiple simultaneous transmissions of frames to a ring network. However, unlike previous protocols, that use the buffer insertion concept combined with some fairness mechanism, the new one uses tokens in order to regulate the access to the ring and to ensure fairness. Unlike buffer insertion rings where data-frames may experience a delay of one data-frame at every intermediate station, in the new protocol the delay in the intermediate stations does not depend on the number of such stations. Moreover, this delay can be reduced even to 0, if needed. The new protocol ensures the removal of a data-frame even if both the destination and the source of the frame fail to remove it from the ring.>

In a token-ring local area network it is important to have minimum delay at each station. One-bit-delay is the minimum possible delay a ring station may have. It can be achieved only if every received bit is transmitted with no change or its outgoing value is determined independently of its incoming value and the incoming values of subsequent bits. The paper introduces the distributed priority mechanism for token-rings as approved by the IEEE-802.5 standard. In this scheme, the token is accompanied by a priority field P and a reservation field R, that work together in an attempt to match the service priority of the ring to that of the most urgent waiting message. It is shown that due to the computation restrictions imposed by the one-bit-delay requirements, the scheme may require up to 7 round-trips in order to reduce P to R. This may lead to loss of bandwidth and starvation at stations with low priority data. The paper presents a new priority mechanism and proves its correctness. The new mechanism retains the desired properties of the standard protocol: it ensures fairness and can be executed by the stations with one-bit-delay. In the new mechanism at most one round-trip is required in order to reduce P to R. This increases the ring throughput and enables low-priority PDUs to get service when PDUs with higher priorities do not exist.>

The paper introduces a new approach, called session swapping, for bandwidth sharing of circuit switched channels in a ring network. This approach enables to divide a single channel among several sessions in a fair manner, with no loss of bandwidth. According to this approach, packets are removed from the ring before reaching their destination, and retransmitted later. The paper proves that any protocol that shares a single channel among several sessions without using session swapping would waste some of the channel bandwidth. Then, it presents a protocol that uses session swapping and yields optimal and fair sharing of a single channel among several sessions. Finally, the paper shows that session swapping can be extended to handle a more general case, where a single channel should be shared among N sessions unevenly, based on some allocation key.>

In networks that use label swapping routing, like ATM, inconsistent routing tables, due to either incorrect setups or memory failures, may result in infinite looping of packets. This work proposes and analyzes a method for ensuring self-termination in such networks. The method is based on imposing linear order on the labels chosen by the stations along the route during connection setup, and on a simple on-line check performed by every station upon making routing decisions. We then analyze the probability of connection setup failure due to the linear order constraint, and show that it is very small.>

In networks that use label swapping routing, like asynchronous transfer mode (ATM), inconsistent routing tables, due to either incorrect setups or memory failures, can result in infinite looping of packets. A method for ensuring self-termination in such networks is proposed and analyzed. The method is based on imposing linear order on the labels chosen by the stations along the route during connection setup, and on a simple online check performed by every station upon taking routing decisions. the self-termination method along a simple route is then extended to routing over multicast trees.>

A media access control protocol, called the multiple token protocol, for high-speed ring networks is described. Its purpose is to increase the throughput under a heavy load and to decrease the access delay under a light load of the token-ring protocol. The protocol maintains several logical token rings in the single physical ring. The number of logical rings can be changed dynamically by the ring stations according to the actual ring load. Each logical ring has its own token, and its operation is close to a token ring with early-token-release and destination removal. Multiple tokens enable multiple simultaneous transmissions of new frames by different stations and decrease the waiting for a token delay.>

In local area networks (LANs) with ring topologies, it is important to have minimum delay at the stations. It is explained why one-bit delay is the minimum possible delay at each station. It is shown that the stations delay depends on the medium access control (MAC) protocol executed in the ring. As an example, a recently published MAC protocol for rings is considered. It is explained why this protocol cannot be implemented with one-bit delay shown how a small modification in the slot format enables the implementation of the protocol with one-bit delay without affecting its properties.>

A hierarchical structure for the MAC layer of high-speed LANs with a ring topology is suggested. The lower part of this layer consists of high-speed dedicated hardware, called the interface, that sits on the data-path and is responsible for those operations that should be performed in the link transmission speed: getting access-control, removing frames, and accepting frames. The upper part, called the MAC manager can be an all-purpose microprocessor. It is responsible for all the other operations associated with the MAC layer. When short labels are used as addresses, the interface algorithm can be based on two small switching tables, whose contents are determined by the MAC manager.>

The paper deals with the issue of station delay in token-ring networks. It explains why one-bit-delay is the minimum possible delay at every station and shows that the station delay depends on the distributed computations performed in the ring. Then, the paper introduces the distributed priority mechanism for token-rings, as approved by the IEEE-802.5 standard. This mechanism attaches to the token, that circulates around the ring and controls the access to the shared medium, a priority field P and a reservation field R. These two fields work together in an attempt to match the service priority of the ring to the highest priority message that is waiting to be sent.It is shown that due to the computation restrictions imposed by the one-bit-delay requirements, this priority mechanism has a grave deficiency as follows. When the token priority is higher than the maximum reservation (P > R), the token should make up to P round-trips, where P is the number of priority levels, before P is reduced to R. During this time period, no station may seize the token and send a message. This leads to loss of bandwidth.The paper presents a new priority mechanism that retains the desired properties of the standard. However, in the new protocol when P > R holds, P is reduced to R in at most 1 round-trip rather than in up to P round-trips.

A new scheme is presented that allows dynamic maintenance, allocation, and release of the isochronous bandwidth in integrated rings. The scheme is flexible since it permits the stations to bundle together several low-speed isochronous channels to form one high-speed isochronous channel. Acquiring isochronous channels by ring stations and releasing them are decentralized, cheap, fast, and simple processes. The overhead bandwidth required by the scheme is negligible. The allocation rate is not affected by the actual load in the ring. The main principle behind the new scheme is to divide the isochronous bandwidth into fixed length slots and to maintain the available channels in each slot as a linked list.>

The problem of slotted- and token-ring recovery from livelocks and deadlocks induced by transmission errors and station failures is discussed. The RE-protocol, an access protocol for slotted-rings that recovers from any combination of transmission errors and station failures in at most five ring revolutions, is presented. It is shown that the protocol requires no information about the current topology of the ring, like the number of stations or the ring revolution propagation time, it uses only two frame bits for access control, and it achieves minimum delay at the ring stations.>

The issue of routing in multiple-ring networks is considered. A new bridge protocol for route determination in a multiple-ring network is introduced. Its main advantage is its communication efficiency: the number of frames used is the number of rings plus the number of bridges in the network, as opposed to the exponential function needed by the existing protocol. Some extensions of the protocol are given. The correctness proof for the new protocol is presented.>