An efficient distributed knot detection algorithm

A distributed knot detection algorithm for general graphs is presented. The knot detection algorithm uses at most O(n log n+m) messages and O(m+n log n) bits of memory to detect all knots' nodes in the network (where n is the number of nodes and m is the number of links). This is compared to O(n²) messages needed in the best algorithm previously published. The knot detection algorithm makes use of efficient cycle detection and clustering techniques. Various applications for the knot detection algorithms are presented. In particular, its importance to deadlock detection in store and forward communication networks and in transaction systems is demonstrated     

Efficient handoff rerouting algorithms: a competitive on-line algorithmic approach

This paper considers the design of handoff rerouting algorithms for reducing the overall session cost in personal communication systems (PCS). Most modern communication systems that are used as an infrastructure for PCS networks are based on connection-based technologies. In these systems, the session cost is composed of two components. The setup cost represents the cost associated with the handoff operations, and the hold cost determines the expense related to the use of network resources held by the connection. This work introduces for the first time, rerouting algorithms for general graphs which are cost effective in terms of their worst-case analysis. The algorithms are analyzed using a competitive analysis approach, and it is proved that the competitive ratio of the proposed algorithms is a small constant of which the precise value depends on the ratio between the setup costs and the hold costs of the links. We also prove a lower bound of 2 on the competitive ratio of any online algorithm, which means that the proposed algorithms are close in terms of worst case behavior to the best possible rerouting algorithm. In addition, experimental results also show that the proposed algorithms indeed balance between the session setup cost and the hold cost, yielding overall lower cost when compared to other algorithms described in the literature.     

The ballot theorem strikes again: packet loss process distribution

The probability distribution of the number of lost packets within a block of consecutive packet arrivals into a finite buffer is an important quantity in various networking problems. In a previous paper, Cidon, Khamisy and Sidi (1993) introduced a recursive scheme to derive this distribution. In this paper, we derive explicit expressions for this distribution using various versions of the powerful ballot theorem. The expressions are derived for a single source M/M/1/K queue     

MetaRing-a full-duplex ring with fairness and spatial reuse

The design principles of a ring network with spatial bandwidth reuse are described. A distributed fairness mechanism for this architecture, which uses low latency hardware control signals, is presented. The basic fairness mechanism can be extended for implementing multiple priority levels and integration of asynchronous with synchronous traffic. The ring is full-duplex and has two basic modes of operation: buffer insertion mode for variable-size packets and slotted mode for fixed-size packets or cells. Concurrent access and spatial reuse allow simultaneous transmissions over disjoint segments of a bidirectional ring and can increase the effective throughput by a factor of four or more. The combination of a full-duplex ring, spatial reuse, a reliable fairness mechanism, and the exploitation of advent in fiber-optic technology are the basis for the MetaRing network architecture     

The layout of virtual paths in ATM networks

We study the problem of designing a layout of virtual paths (VPs) on a given ATM network. We first define a mathematical model that captures the characteristics of virtual paths. In this model, we define the general VP layout problem, and a more restricted case; while the general case layout should cater connections between any pair of nodes in the network, the restricted case layout should only cater connections between a specific node to the other nodes. For the latter case, we present an algorithm that finds a layout by decomposing the network into subnetworks and operating on each subnetwork, recursively; we prove an upper bound on the optimality of the resulting layout and a matching lower bound for the problem, that are tight under certain realistic assumptions. Finally, we show how the solution for the restricted case is used as a building block in various solutions to more general cases (trees, meshes, K-separable networks, and general topology networks) and prove a lower bound for some of our results. The results exhibit a tradeoff between the efficiency of the call setup and both the utilization of the VP routing tables and the overhead during recovery from link disconnections     

A distributed control architecture of high-speed networks

A control architecture for a high-speed packet-switched network is described. The architecture was designed and implemented as part of the PARIS (subsequently plaNET and BBNS) networking project at IBM. This high bandwidth network for integrated communication (data, voice, video) is currently operational as a laboratory prototype. It will also be deployed within the AURORA Testbed that is part of the NSF/DARPA gigabit networking program. The high bandwidth dictates the need for specialized hardware to support faster packet handling for both point-to-point and multicast connections. A faster and more efficient network control is also required in order to support the increased number of connections and their changing requirements with time. The new network control architecture presented exploits specialized hardware, thereby enabling tasks to be performed faster and with less computation overhead. In particular, since control information can be distributed quickly using hardware packet handling mechanisms, decisions can be made based upon more complete and accurate information. In some respects, this has the effect of having the benefits of centralized control (e.g., easier bandwidth resource allocation to connections), while retaining the fault tolerance and scalability of a distributed architecture     

MaGMA: mobility and group management architecture for real‐time collaborative applications

We introduce MaGMA, a mobility and group management architecture, enabling real‐time collaborative group applications such as push‐to‐talk (PTT) for mobile users. MaGMA provides, for the first time, a comprehensive and scalable solution for group management, seamless mobility, and quality‐of‐service (QoS). MaGMA is a distributed IP‐based architecture consisting of an overlay server network deployed as part of the service infrastructure. MaGMA's architecture consists of a collection of mobile group managers (MGMs), which manage group membership and may also implement a multicast overlay for data delivery. The architecture is very flexible, and can co‐exist with current as well as emerging wireless network technologies. We see such services as essential components in beyond‐3G (B3G) networks. We propose two group management approaches in the context of MaGMA. We devise protocols for both approaches, evaluate both solutions using simulations, and validate the results through mathematical analysis. Finally, we present a proof‐of‐concept prototype implementation. Copyright © 2005 John Wiley & Sons, Ltd.     

A local fairness algorithm for gigabit LAN's/MAN's with spatialreuse

The authors present an algorithm to provide local fairness for ring and bus networks with spatial bandwidth reuse. Spatial bandwidth reuse can significantly increase the effective throughput delivered by the network. The proposed algorithm can be applied to any dual ring or bus architecture such as MetaRing. In the dual bus configuration, when transporting ATM cells, the local fairness algorithm can be implemented using two generic flow control (GFC) bits in the ATM cell header. In the performance it is shown that this local fairness algorithm can exploit the throughput advantage offered by spatial bandwidth reuse better than a global fairness algorithm. This is accomplished because it ensures fair use of network resources among nodes that are competing for the same subset of links, while permitting free access to noncongested parts of the network. The performance advantage of the local fairness scheme is demonstrated by simulating the system under various traffic scenarios and comparing the results to that of the MetaRing SAT-based global fairness algorithm. It is also shown that under certain traffic patterns, the performance of this algorithm achieves the optimal throughput result predicted by the known Max-Min fairness definition     

On protective buffer policies

Studies buffering policies which provide different loss priorities to packets/cells, while preserving packet ordering (space priority disciplines). These policies are motivated by the possible presence, within the same connection, of packets with different loss probability requirements or guarantees, e.g., voice and video coders or rate control mechanisms. The main contribution of the paper is the identification and evaluation of buffering policies which preserve packet ordering and guarantee high priority packets performance (loss probability), irrespective of the traffic intensity and arrival patterns of low priority packets. Such policies are termed protective policies. The need for such policies arises from the difficulty to accurately characterize and size low priority traffic, which can generate large and unpredictable traffic variations over short periods of time. The authors review previously proposed buffer admission policies and determine if they satisfy such “protection” requirements. Furthermore, they also identify and design new policies, which for a given level of protection maximize low priority throughput