Multi-core processors are increasingly popular because they yield higher performance, but they also present new challenges for hard real-time systems in that they make it much more difficult to estimate a task's worst-case execution time (WCET). Partitioned cache architecture is being used to ease the problem by providing an isolated execution environment for each thread. Although simple to implement and use, this method may be sub-optimal with respect to both energy consumption and performance since it prevents taking advantage of information shared across threads for both instructions and data. This work presents a new cache architecture termed SPACE (Semi-Partitioned CachE) that makes it possible to leverage information sharing, yielding in turn a tighter WCET. The SPACE architecture together with our new WCET algorithm can be used to maintain the predictability of the execution time of the parallel threads while reducing the overall energy consumption of the system. The new proposed cache architecture was implemented using Verilog and deployed on a Xilinx MicroBlaze multi-core design for testing, validation and measurements. The application level experiments were conducted using the Chronos tool for estimation and the Wattch/SimpleScalar simulator for execution. Using three real-time programs-a radar tracker, a DES encryption algorithm, and an FM radio-we showed that SPACE together with the enhanced WCET algorithm reduce the average system WCET of these applications by 31 percent and reduce the actual energy consumption by 18 percent in comparison with other cache architectures.

We introduce a novel heterogeneous NoC router architecture, supporting different link bandwidths and different number of virtual channels (VCs) per unidirectional port. The NoC router is based on shared-buffer architecture and has the advantages of ingress and egress bandwidth decoupling, and better performance as compared with input-buffer router architecture. We present the challenges facing the design of such heterogeneous NoC router, and describe how this router architecture addresses them. We introduce and formally prove a novel approach that reduces the number of required middle shared-buffers without affecting the performance of the router. In comparison with an optimal input-buffer homogeneous router, our NoC router improves saturation throughput by 6-47 percent for standard traffic patterns. The router achieves significant run-time improvement for NoC-based CMP running PARSEC benchmarks. It offers better scalability, area, and power reduction of 15-60 percent, for NoC based CMPs of size 4 × 4 up to 16 × 16, as compared with optimal input-buffer homogeneous and heterogeneous routers.

Networks-on-Chip (NoCs) form an emerging paradigm for communications within chips. In particular, bufferless NoCs require significantly less area and power consumption, but also pose novel major scheduling problems to achieve full capacity. In this paper, we provide first insights on the capacity of bufferless NoCs. In particular, we present optimal periodic schedules for several bufferless NoCs with a complete-exchange traffic pattern. These schedules particularly fit distributed-programming models and network congestion-control mechanisms. In addition, for general traffic patterns, we also introduce efficient greedy scheduling algorithms, that often outperform simple greedy online algorithms and cannot have deadlocks. Finally, using network simulations, we quantify the speedup of our suggested algorithms, and show how they improve throughput by up to 35 percent on a torus network.

In this paper, we present PACK (Predictive ACKs), a novel end-to-end traffic redundancy elimination (TRE) system, designed for cloud computing customers. Cloud-based TRE needs to apply a judicious use of cloud resources so that the bandwidth cost reduction combined with the additional cost of TRE computation and storage would be optimized. PACK's main advantage is its capability of offloading the cloud-server TRE effort to end-clients, thus minimizing the processing costs induced by the TRE algorithm. Unlike previous solutions, PACK does not require the server to continuously maintain clients' status. This makes PACK very suitable for pervasive computation environments that combine client mobility and server migration to maintain cloud elasticity. PACK is based on a novel TRE technique, which allows the client to use newly received chunks to identify previously received chunk chains, which in turn can be used as reliable predictors to future transmitted chunks. We present a fully functional PACK implementation, transparent to all TCP-based applications and network devices. Finally, we analyze PACK benefits for cloud users, using traffic traces from various sources.

Hierarchical topologies are frequently proposed for large Networks-on-Chip (NoCs). Hierarchical architectures utilize, at the upper levels, long links of the order of the die size. RC delays of long links might reach dozens of clock cycles in advanced technology nodes, if delay reduction techniques (e.g. wire sizing and repeater insertion) are not applied. Some proposals assume that long links can be adjusted to satisfy timing requirements but lack a deep evaluation of the tradeoffs and costs. Other proposals assume that long links must be pipelined, but do not provide a comprehensive justification. In this paper we evaluate the efficiency and the system costs of wire sizing and repeater insertion as methods to reduce link delays in hierarchical NoCs. We present a unified interconnect cost function that accounts for power and wiring overheads of these methods. Then, we quantify the costs of modifying long links in typical hierarchical NoCs for different target clock frequencies and technology nodes. Although long links might undergo aggressive adjustments, we find these overall costs to be low at the system level for many typical cases, taking into account that there are only a few long links in most proposed hierarchical NoC architectures.

As the number of modules grows, performance scalability of planar topology Networks-on-Chip (NoCs) becomes limited due to the increasing hop-distances. The growing hop-distance affects both end-to-end network latency and overall network saturation. Hierarchical topologies provide better traffic hop distance and therefore are more adequate for large systems. However, the introduction of hierarchical NoCs offers new challenges. In particular, how to distribute the traffic among the hierarchy levels to effectively utilize the hierarchical structure. In this paper we propose a dynamic traffic distribution scheme that adapts traffic distribution among the hierarchy levels to the changing traffic conditions. We evaluate our scheme with packet-accurate simulations and show that it enables to realize the potential of hierarchical NoCs in latency reduction under both light and heavy traffic loads.

Similar to off-chip networks, current NoC architectures are based on the store and forward of uncoordinated end-to-end packet transmissions through autonomous buffered routers. However, the monolithic nature and the small physical dimensions of on chip networks open up the opportunity for much more tightly controlled architectures. We present GANA, a new Global Arbiter NoC Architecture. In GANA, the transmission of end-to-end data is timed by a global arbiter in a way that avoids any queuing in the network. The arbitration takes into account the complete transfer of the end-to-end packets through the entire network path, avoiding any intermediate queuing and hop-by-hop packet arbitration. Consequently, buffers and arbiters are no longer required in the routers, resulting in smaller area and low power consumption. It is demonstrated through detailed design and synthesis that the additional area of the central arbiter and the control path are negligible in comparison to the provided area saving. For example, an 8× 8 GANA consumes only 16% of the area of an equivalent autonomous NoC while providing a better end-to-end throughput. The end-to-end performance of GANA at high network loads is typically much better than in a distributed-control NOC, because resource contention and queuing in the network are avoided. This comes at the cost of a few percentage increase in latency at light loads due to the additional arbitration phase. GANA architecture combines the inherent benefits of a network (parallelism and spatial reuse of links) with the inherent benefits of high integration (global view of the system state, central control, and synchronization). The scalability of GANA is evaluated analytically, showing that it can be superior to fully-distributed networks in systems up to a size of about 100 modules manufactured in 45nm technology, which can be used today as well as in the foreseeable future.

Network-on-Chip (NoC) is an evolving interconnection architecture addressing the rising complexity of system-on-chips (SoCs). We present a model for the cost of a NoC for a multiple use-case SoC, i.e., a system with distinct modes of operation, each having a unique traffic pattern. Specifically, we formulate an optimization problem capturing the fact that different use-cases can share capacity. We evaluate the proposed scheme using synthetic and real-life traffic, showing a substantial reduction of up to 27% in the required NoC resources, both when using a new algorithm we present and when using (a somewhat heavier) simulated-annealing procedure.

As the number of applications and programmable units in CMPs and MPSoCs increases, the Network-on-Chip (NoC) encounters unpredictable, heterogeneous and time dependent traffic loads. This motivates the introduction of adaptive routing mechanisms that balance the NoC's loads and achieve higher throughput compared with traditional oblivious routing schemes. An effective adaptive routing scheme should be based on a global view of the network state. However, most current adaptive routing schemes, following off-chip networks, are based on distributed reactions to local congestion. In this paper we leverage the unique on-chip capabilities and introduce a novel paradigm of NoC centralized adaptive routing. Our scheme continuously monitors the global traffic load in the network and modifies the routing of packets to improve load balancing accordingly. We present a specific design for the case of mesh topology, where XY or YX routes are adaptively selected for each source-destination pair. We show that while our implementation is lightweight and scalable in hardware costs, it outperforms oblivious and distributed adaptive routing schemes in terms of load balancing and average packet delay.

We introduce a novel evaluation methodology to analyze the delay of a wormhole routing based NoC with variable link capacities and a variable number of virtual channels per link. This methodology can be utilized to analyze different heterogeneous NoC architectures and traffic scenarios for which no analysis framework has been developed before. In particular, it can replace computationally-extensive simulations at the inner-loop of the link capacities and virtual channels allocation steps of the NoC topology optimization process. Our analysis introduces a set of implicit equations which can be efficiently solved iteratively. We demonstrate the accuracy of our approximation by comparing the analysis results to a simulation model for several use-cases and synthetic examples. In addition, we compare the analysis with simulation results for a chip-multi-processor (CMP) using SPLASH-2 and PARSEC traces for both homogeneous and heterogeneous NoC configurations.

As chip density keeps doubling every process generation, the use of Network-on-Chip becomes the prevalent architecture of SoC, MPSoC and large scale CMP designs. To that end, diverse NoC solutions are developed by the industry and the research community in order to meet heterogeneous on-chip communication requirements. Consequently, there is a growing need to rely on a simulation tools in order to explore, evaluate and optimize these new NoC architectures and topologies. The simulation platform is based on OMNeT++. It provides an open-source, modular, scalable, extendible and fully parameterizable framework for modeling NoC. In this demo we describe the structure of this framework.

In this paper we present PACK (Predictive ACKs), a novel end-to-end Traffic Redundancy Elimination (TRE) system, designed for cloud computing customers.

In this paper, we examine the design process of a Network on-Chip (NoC) for a high-end commercial System on-Chip (SoC) application. We present several design choices and focus on the power optimization of the NoC while achieving the required performance. Our design steps include module mapping and allocation of customized capacities to links. Unlike previous studies, in which point-to-point, per-flow timing constraints were used, we demonstrate the importance of using the application end-to-end traversal latency requirements during the optimization process. In order to evaluate the different alternatives, we report the synthesis results of a design that meets the actual throughput and timing requirements of the commercial SoC. According to our findings, the proposed technique offers up to 40% savings in the total router area and a reduction of up to 49% in the inter-router wiring area.

Network on-Chip (NoC) is being adopted by chip architects as a means to improve design productivity. As the number of modules connected to a bus increase, its physical implementation becomes very complex, and achieving the desired throughput and latency requires time consuming custom modifications. Conversely, NoCs are designed separately from the functional units of the system to handle all foreseen inter-module communication needs. Their inherent scalable architecture facilitates the integration of the system and shortens the time-to-market of complex products. In this work, we discuss and evaluate the design process of a NoC for a state-of-the-art system on-chip (SoC). More specifically, we describe our experience in designing a cost optimized NoC interconnect for a high-performance, power constrained 4G wireless modem. We focus on the power and performance aspects of various module mapping schemes, looking for a tradeoff that is characterized by a minimal power consumption that still meets the timing requirements of all targeted applications. Using a simulated annealing based mapping process, we place the system's modules on a grid, minimizing the dynamic energy consumed by the transmission of packets over the NoC. In many of the studies where network latency was used as a performance goal (either as the optimized cost function or as a constraint), the average delay of all packets over all communicating pairs was considered. However, in a practical SoC, different streams of communication may require different delays and therefore the overall average latency is an inappropriate measure. Consequently, the individual per-flow, point-to-point (source-destination) latencies should be accounted for to get better results. In this paper, we go further to suggest a third, improved approach: knowing the application that is to be used in the SoC, we utilize its functional timing requirements, which are defined by the application end-to-end latency constraints. Each of those end-to-end traversal delay requirements is composed of the cumulative requirement of a sequence (or a "chain") of point-to- point flows. For example, the application may require that a block of data which is generated by module A is sent to module B, and then to module C. By observing that the performance of the application is subject to the total time it would take the data to get from module A to module C, we can use this delay as the targeted performance measure, rather than specifying the two separate latency constraints (for the flow from module A to module B and from module B to module C). Since pair-wise delays may be traded, the timing constraints are relaxed and the optimization program can use more freedom in its operation. To the best of our knowledge, this paper is the first to discuss and quantify the benefits of specifying the end-to-end traversal requirements during the design process.In order to quantify and evaluate different alternatives, we report the actual throughput and timing requirements of the commercial SoC as well as the synthesis results. We evaluate three mapping schemes: a power optimized mapping; a power optimized mapping with point-to-point timing requirements; and a power optimized mapping with end-to-end timing requirements. For each of these mappings, we use simulations to find a uniform assignment of link capacities so that the run-time latency requirements of all flows are met. We then further optimize the network by tuning the capacity of links, reducing the bandwidth of links that operate faster than necessary. Synthesis results reveal that considering end-to-end requirements during the mapping phase of the design results in an improved implementation, even if only a limited number of discrete port configurations and link bandwidths are supported. According to our findings, the proposed mapping and link tuning techniques offer up to 40% savings in the total router area and a reduction of up to 49% in the inter-router wiring area. As part of this work, we present the bandwidth and timing requirement of the high-performance, state-of- the-art 4G application we examine. This information can be used by the NoC community as a benchmark for future research.

While NoCs are efficient in delivering high throughput point-to-point traffic, their multi-hop operation is too slow for latency sensitive signals. In addition, NoCS are inefficient for multicast operations. Consequently, although NoCs outperform busses in terms of scalability, they may not facilitate all the needs of future SoCs. In this paper, the benefit of adding a global, low latency, low power shared bus as an integral part of the NoC architecture is explored. The Bus-enhanced NoC (BENoC) is equipped with a specialized bus that has low and predictable latency and performs broadcast and multicast. We introduce and analyze MetaBus, a custom bus optimized for such low-latency low power and multicast operations. We demonstrate its potential benefits using an analytical comparison of latency and energy consumption of a BENoC based on MetaBus versus a standard NoC. Then, simulation is used to evaluate BENoC in a dynamic non-uniform cache access (DNUCA) multiprocessor system.

In this article, we show that keeping track of history enables significant improvements in the communication complexity of dynamic network protocols. We present a communication optimal maintenance of a spanning tree in a dynamic network. The amortized (on the number of topological changes) message complexity is O ( V ), where V is the number of nodes in the network. The message size used by the algorithm is O (log |ID|) where |ID| is the size of the name space of the nodes. Typically, log |ID| = O (log V ). Previous algorithms that adapt to dynamic networks involved Ω ( E ) messages per topological change—inherently paying for re-computation of the tree from scratch. Spanning trees are essential components in many distributed algorithms. Some examples include broadcast (dissemination of messages to all network nodes), multicast, reset (general adaptation of static algorithms to dynamic networks), routing, termination detection , and more. Thus, our efficient maintenance of a spanning tree implies the improvement of algorithms for these tasks. Our results are obtained using a novel technique to save communication. A node uses information received in the past in order to deduce present information from the fact that certain messages were NOT sent by the node's neighbor. This technique is one of our main contributions.

The perception of future wireless mesh network (WMN) deployment and usage is rapidly evolving. WMNs are now being envisaged to provide citywide "last-mile" access for numerous mobile devices running media-rich applications with stringent quality of service (QoS) requirements. Consequently, some current-day conceptions underlying application support in WMNs need to be revisited. In particular, in a large WMN, the dynamic assignment of users to Internet gateways will become a complex traffic engineering problem that will need to consider load peaks, user mobility, and handoff penalties. We propose QMesh, a framework for user-gateway assignment that runs inside the WMN, and is oblivious to underlying routing protocols. It solves the handoff management problem in a scalable distributed manner. We evaluate QMesh through an extensive simulation (mostly of VoIP), in two settings: (1) a real campus network, with user mobility traces from the public CRAWDAD dataset, and (2) a large-scale urban WMN. Simulation results demonstrate that QMesh achieves significant QoS improvements and network capacity increases compared to traditional handoff policies, and illustrate the need for intelligent gateway assignment within the mesh.

The majority of current network on chip (NoC) architectures employ mesh topology and use simple static routing, to reduce power and area. However, regular mesh topology is unrealistic due to variations in module sizes and shapes, and is not suitable for application-specific NoCs. Consequently, simplistic routing techniques such as XY routing are inadequate, raising the need for low cost alternatives which can work in irregular mesh networks. In this paper we present a novel technique for reducing the total hardware cost of routing tables for both source and distributed routing approaches. The proposed technique is based on applying a fixed routing function combined with minimal deviation tables that are used only when the routing decisions for a given destination deviate from the predefined routing function. We apply this methodology to compare three hardware efficient routing methods for irregular mesh topology NoCs. For each method, we develop path selection algorithms that minimize the overall cost of routing tables. Finally, we demonstrate by simulations on random and specific real application network instances a significant cost saving compared to standard solutions, and examine the scaling of cost savings with growing NoC size

MANs and backbone networks are shared by "users" that can be individuals, organizations as well as communication service providers. Such users produce concurrently a variety of traffic patterns from multiple network locations. Traditional fairness definitions allocate bandwidth to individual source to destination flows. These individual flow fairness definitions generally allocate more bandwidth to users with a larger number of flows, thus creating unfairness at the user level. This paper explores alternative user level fairness criteria. We examine several extensions of the max-min fairness that allocate bandwidth fairly to users. We require the new criteria to be based on a max-min definition, to be backward compatible with the traditional max-min fairness (when each user has a single flow) and not to allocate zero bandwidth to any individual flow. We describe three different criteria for fair bandwidth allocation to users. The first is a weighted max-min criteria, achieving user fairness by the weights assigned to each flow; The second attempts to balance the user allocation separately over each link; Finally, we introduce a novel scheme termed the redefined vector-space fairness that is based on a lexicographical maximization of both user and individual flows. This paper evaluates the three fairness definitions both behaviorally and numerically. The simulation results show a clear advantage for the redefined vector-space fairness both in terms of user fairness and overall throughput.

The paper introduces network-on-chip (NoC) design methodology and low cost mechanisms for supporting efficient cache access and cache coherency in future high-performance chip multi processors (CMPs). We address previously proposed CMP architectures based on non uniform cache architecture (NUCA) over NoC, analyze basic memory transactions and translate them into a set of network transactions. We first show how a simple, generic NoC which is equipped with needed module interface functionalities can provide infrastructure for the coherent access of both static and dynamic NUCA. Then we show how several low cost mechanisms incorporated into such a vanilla NoC can facilitate CMP and boost performance of a cache coherent NUCA CMP. The basic mechanism is based on priority support embedded in the NoC, which differentiates between short control signals and long data messages to achieve a major reduction in cache access delay. The low cost priority-based NoC is extremely useful for increasing performance of almost any other CMP transaction. Priority-based NoC along with the discussed NoC interfaces are evaluated in detail using CMP-NoC simulations across several SPLASH-2 benchmarks and static Web content serving benchmarks showing substantial L2 cache access delay reduction and overall program speedup

Summary form only given. The concept of a communication network emerged, many times in the past, for connecting a large number of systems, replacing dedicated point-to-point connection and other small-scale interconnection mechanisms. Each network needs to provide a cost effective solution for a large number of possibly conflicting requirements such as flexibility, scalability, reliability and performance. Therefore, the task of network architects and designers is to solve multiple instances of a complex constrained optimization problem resulting in numerous and diverse network solutions. For example, there are different standards and architectures associated with interconnection networks, home networks, LANs, MANs, WANs and wireless networks. In this paper, we map the common lessons and concepts from the networking research to the emerging NoC field. We argue that the NoC optimization problem consists of several distinguished types that should lead to multiple diverse solutions. NoC network layer architectures pose new challenges in exploring solutions to traditional networking problems such as routing, quality-of-service, flow and congestion control and reliability. The unique characteristics of silicon chips require new solutions to these classical problems, and define a new set of NoC specific problems, such as automatic network design process, power and area optimization and specialized system functionalities. We speculate which class of solutions is likely to fit the different NoC types

An asynchronous router for quality-of service NoC is presented. It combines multiple service levels (SL) with multiple equal-priority virtual channels (VC) within each level. The VCs are assigned dynamically per each link A different number of VCs may be assigned to each SL and per each link The router employs fast arbitration schemes to minimize latency

We present a novel network-on-chip-based architecture for future programmable chips (FPGAs). A key challenge for FPGA design is supporting numerous highly variable design instances with good performance and low cost. Our architecture minimizes the cost of supporting a wide range of design instances with given throughput requirements by balancing the amount of efficient hard-coded NoC infrastructure and the allocation of "soft" networking resources at configuration time. Although traffic patterns are design-specific, the physical link infrastructure is a performance bottleneck, and hence should be hard-coded. It is therefore important to employ routing schemes that allow for high flexibility to efficiently accommodate different traffic patterns during configuration. We examine the required capacity allocation for supporting a collection of typical traffic patterns on such chips under a number of routing schemes. We propose a new routing scheme, weighted ordered toggle (WOT), and show that it allows high design flexibility with low infrastructure cost. Moreover, WOT utilizes simple, small-area, on-chip routers, and has low memory demands

Network on chip (NoC) may be the primary interconnect mechanism for future systems-on-chip (SoC). Real-life SoCs typically include hot-modules such as DRAM controller or floating point unit, which are bandwidth limited and in high demand by other units. In this paper we demonstrate that the mere existence of one or more hot-modules in a wormhole-based NoC dramatically reduces network efficiency and causes an unfair allocation of system resources. We demonstrate that a single hot-module destroys the performance of the entire SoC, even if network resources are over-provisioned. In order to resolve the hot-module effect, we introduce a novel low-cost credit based distributed access regulation technique that fairly allocates access rights to the hot-module. Unlike other methods, this technique directly addresses the root cause of network buffer congestion phenomena. Using simulation, we show the effectiveness of the suggested mechanism in various NoC scenarios

We consider the problem of dynamically assigning application sessions of mobile users or user groups to service points. Such assignments must balance the trade-off between two conflicting goals. On the one hand, we would like to connect a user to the closest server in order to reduce network costs and service latencies. On the other hand, we would like to minimize the number of costly session migrations, or handoffs, between service points. We tackle this problem using two approaches. First, we employ algorithmic online optimization to obtain algorithms whose worst-case performance is within a factor of the optimal. Next, we extend them with opportunistic heuristics that achieve near-optimal practical average performance and scalability. We conduct case studies of two settings where such algorithms are required: wireless mesh networks with mobile users and wide-area groupware applications with or without mobility.

This paper addresses the allocation of link capacities in the automated design process of a network-on-chip based system. Communication resource costs are minimized under quality-of-service timing constraints. First, we introduce a novel analytical delay model for virtual channeled wormhole networks with non-uniform link capacities that eliminates costly simulations at the inner-loop of the optimization process. Second, we present an efficient capacity allocation algorithm that assigns link capacities such that packet delays requirements for each flow are satisfied. We demonstrate the benefit of capacity allocation for a typical system on chip, where the traffic is heterogeneous and delay requirements may largely vary, in comparison with the standard approach which assumes uniform-capacity links

Abstract — We consider the novel problem of dynamically assigning application sessions of mobile users or user groups to service points. Such assignments must balance the tradeoff between two conflicting goals. On the one hand, we would like to connect a user to the closest server, in order to reduce network costs and service latencies. On the other hand, we would like to minimize the number of costly session migrations, or handoffs, between service points. We tackle this problem using two approaches. First, we employ algorithmic online optimization to obtain algorithms whose worst-case performance is within a factor of the optimal. Next, we extend them with opportunistic versions that achieve excellent practical average performance and scalability. We conduct case studies of two settings where such algorithms are required: wireless mesh networks with mobile users, and wide-area groupware applications with or without mobility. I.

The emergence of network convergence emphasizes the need to support distributed synchronous servers such as TDMoIP (pseudo-wire) and 3G cellular gateways over a packet switched infrastructure. Conse-quently, we formalize the problem of network wide clock frequency synchronization and introduce novel and efficient algorithms to synchronize the frequency among all the clocks in the network with respect to a single frequency. The common thread of our solutions is that they take a network-wide view that accounts for all the clocks in the network and measurements taken over all links to estimate the frequency difference of each clock with respect to the reference clock. The various presented algorithms introduce different trade-offs between the accuracy and the computation complexity. While all our schemes are global, they employ simple pair-wise measurements between neighboring nodes. Consequently, all the algorithms presented in the paper, are simple, easy to implement and require a modest amount of measurement and control traffic. I.

We present a novel approach for the estimation of one-way delays between network nodes without any time synchronization in the network. It is based on conducting multiple and simple one-way measurements among pairs of nodes, and estimating the one-way delays by optimizing the value of a global objective function that is affected by the overall network topology and not just by individual measurements. We examine two objective functions. The first intuitive choice is the least square error (LSE). Using a novel concept of delay-induced link probabilities, we develop a second objective function that is based on the maximum-entropy (ME) principle. Extensive numerical experiments show that both functions considerably outperform the common method of halving the round-trip delays. They also show that ME outperforms the commonly used LSE.

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.

Time synchronization is critical in distributed environments. A variety of network protocols, middleware and business applications rely on proper time synchronization across the computational infrastructure and depend on the clock accuracy. The ''network time protocol" (NTP) is the current widely accepted standard for synchronizing clocks over the Internet. NTP uses a hierarchical scheme in order to synchronize the clocks in the network. In this paper we present a novel non-hierarchical peer-to-peer approach for tune synchronization termed CTP - classless time protocol. This approach exploits convex optimization theory in order to evaluate the impact of each clock offset on the overall objective function. We define the clock offset problem as an optimization problem and derive its optimal solution. Based on the solution we develop a distributed protocol that can be implemented over a communication network and prove its convergence to the optimal clock offsets. For compatibility, the CTP may use the exact format and number of messages used by NTP. We also present methodology and numerical results for evaluating and comparing the accuracy of time synchronization schemes. We show that the CTP substantially outperforms hierarchical schemes such as NTP in the sense of clock accuracy with respect to a universal clock, without increasing complexity.

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.

Personal communication systems (PCS) maintain a location management mechanism for tracking the location of their mobile users. The increasing population of mobile users leads to congestion problems in these systems, and motivates the development of more efficient management schemes. This work presents a new mobility management scheme that integrates the location area approach with the location prediction idea. It is based on results from traffic flow theory and it is first that uses the concept of moving location areas. Traffic flow theory suggests that people tend to reside in specific places for long periods of time. Occasionally, they move to new locations and try to minimize the travel time using highways as much as possible. The scheme uses two complementary sets of location areas that overlap each other. The first set contains small location areas and is designated for locating mobile users in a quasi-static state. The second set covers the highways and it is designated to track mobile users while they are traveling from place to place, where each highway is covered by a single location area. The dual set design enables tracking mobile users at a high degree of accuracy with low update cost while they are quasi-static state, and reduces the amount of update operations when they travel. For tracing mobile users on a highway, the scheme uses a system of moving location areas. A moving location area (MLA) is a small location area that defines the location of a group of mobile users, which are geographically concentrated and move in the same direction. The scheme guarantees low rate of update and search operations at each cell of the system and efficiently utilizes the radio spectrum and the network resources with low computational overhead. These advantages are also backed by simulation results.

The delivery of large files to single users, such as application programs for some versions of the envisioned network computer, or movies, is expected by many to be one of the main requirements of communication networks. This requires expensive high bandwidth capacity as well as fast and high storage servers. This motivates multimedia providers to optimize the delivery distances, as well as the electronic content allocation. A hierarchical architecture for providing the multimedia content was introduced by Nussbaumer, Patel, Schaffa, and Sternbenz (1994). They also introduced the trade-off between bandwidth and storage requirements for the placement of the content servers on the hierarchy tree. They found the best level of the hierarchy for the server location to minimize the total of the costs of communication and storage. Their algorithm is centralized. We solve the more general ease where servers can be located at different levels of the hierarchy. Our algorithm is distributed, and each node requires a limited memory capacity and computational power. Results for related approaches to caching design are of higher complexity. Results for related classic operations research problems are for centralized algorithms, mostly linear programming, that are not easy to convert into distributed algorithms. Instead, we observe that the use of dynamic programming is more natural for distributed implementations. For the specific problem at hand, we also managed to find a natural function (a generalization of the problem) that simplifies the combination operation used in dynamic programming. We also show how to map such contemporary problems to the area of classical plant location problems in operations research.

This work presents a simple mobility scheme for IP-based networks, termed the "anchor chain" scheme. The scheme combines pointer forwarding and caching methods. Every mobile host (MH) is associated with a chain of anchors that connects it to its home agent. Each anchor defines the location of the MH at a certain degree of accuracy. The accuracy is increased along the chain until the attachment point of the MH is reached. We develop distributed procedures for updating the anchor chain (binding operation) with MH movements and for delivering messages to a MH (delivery operation). In terms of worst-case performance, the total cost of the binding operations is O(MovelogMove), where Move is the total geographic distance that the MH has traveled since its activation. The total length of the MH's pointer path is linear with the distance between the MH and its home network, and the delivery cost is near-optimal. In addition, the anchor chain of a MH is determined dynamically with no need for preliminary definitions of static anchors or regions. Our simulation results show that the anchor chain scheme also yields lower average overheads for both the binding and the delivery operations than other methods that are described in the literature, including the current home approach. We believe that the proposed scheme is scalable, fairly easy to implement and therefore attractive for supporting MH.

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. Using an efficient handoff rerouting algorithm is important for the efficient management of PCS networks. 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 whose precise value depends on the ratio between the setup costs and the hold costs of the links. We also prove that the competitive ratio of the best online algorithm is at least 2, 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 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.

Most of the web traffic today uses the HyperText Transfer Protocol (HTTP), with Transmission Control Protocol (TCP) as the underlying transport protocol. Unfortunately, TCP is poorly suited for the short conversations that comprise a significant component of web traffic. The overhead of setting up and tearing down TCP state amortizes poorly for these small connections. Moreover, emerging modern web server systems employ HTTP redirection for server load-balancing and content distribution; such schemes require setting up (and tearing down) multiple TCP connections for servicing a single client request. We have designed and analyzed a hybrid scheme to address these issues. The scheme uses either TCP, or the User Datagram Protocol (UDP) as the underlying transport protocol for carrying web traffic. UDP is used for short transfers (including HTTP redirection), while TCP is used for all other transfers. In this manner, we avoid the extra TCP overhead for short connections, but still benefit from the reliable delivery and congestion control that TCP provides. We ran trace-based simulations to quantify the effects of various network parameters (i.e., packet loss rates) on the performance of the hybrid scheme. We observed performance gains exceeding 20-25% with HTTP/1.1-style persistent connections, and over 40-50% without persistent connections. These gains can be improved with further performance optimizations that we describe.

In connection-oriented networks, resource reservations must be made before data can be sent along a route. For short or bursty connections, a selected route must have the required resources to ensure appropriate communication with regard to desired quality-of-service (QoS). For example, in ATM networks, the route setup process considers only links with sufficient resources and reserves these resources while it advances toward the destination. The same concern for QoS routing appears in datagram networks such as the Internet, when applications with QoS requirements need to reserve resources along pinned routes. In this paper, we analyze the performance of multi-path routing algorithms and compare them to single-path reservation that might be persistent, i.e., retry after a failure. The analysis assumes that the routing process reserves resources while it advances toward the destination, thus there is a penalty associated with a reservation that cannot be used. Our analysis shows that while multi-path reservation algorithms perform comparably to single-path reservation algorithms, either persistent or not, the connection-establishment time for multi-path reservation is significantly lower. Thus, multi-path reservation becomes an attractive alternative for interactive applications such as World Wide Web browsing.

ATM networks are moving to a state where large production networks are deployed and require a universal, open and efficient ATM network control platform (NCP). The emerging PNNI (Private Network to Network Interface) standard introduces an internetworking architecture which can also be used as an intranetwork interface. However, PNNI fails in the latter due to performance limitations, limited functionality and the lack of open interfaces for functional extensions. OPENET is an open high-performance NCP based on performance and functional enhancements to PNNI. It addresses the issues of scalability, high performance and functionality. OPENET focuses on intranetworking and is fully compatible with PNNI in the internetwork environment. The major novelties of the OPENET architecture compared to PNNI is its focus on network control performance. A particular emphasis is given to the increase of the overall rate of connection handling, to the reduction of the call establishment latency and to the efficient utilization of the network resources. These performance enhancements are achieved by the use of a native ATM distribution tree for utilization updates, lightweight signalling and extensive use of caching and pre-calculation of routes. OPENET also extends PNNI functionality. It utilizes a new signalling paradigm that better supports fast reservation and multicast services, a control communication infrastructure which enables the development of augmented services such as directory, hand-off, billing, security etc. OPENET was implemented by the High-Speed Networking group at Sun Labs and is under operational tests.

Efficient routing has been one of the most challenging topics in the communication networks field. Collecting the topology and network state information to every node has become a popular approach (termed a link state protocol). Applying this technique introduces a problem of a large amount of data and information updates. In large networks it leads to hierarchical division of the network into smaller clusters. Our solution takes a different direction. It defines a vicinity around each node that is updated with the local node and link information. Outside the vicinity an hierarchical yet flexible structure of the border node is defined. The route is calculated up to the nearest border and from this point a new calculation is made. This new architecture eliminates the need of dividing the network into clusters, in particular solving the inefficiency when such a partition is done manually.

This paper introduces a novel method, called the mobilizer, of executing synchronous communication protocols in a cellular mobile environment. First, we present a distributed protocol, called mobile propagation of information (MPI), for broadcasting over a mobile environment. Then, we present the mobile propagation of information with feedback (MPIF) protocol, which can be used to implement this mobilizer, that is, enable synchronous protocols to run over distributed networks with mobile users. The additional message complexity overhead, induced due to the mobilizer, is linear with the number of users' movements.

Personal Communication Systems (PCS) enable people to communicate independent of their location.For tracking the location of mobtie users the system must maintain a Location Management mechanism, which maps user ad-&ases to their current location.The increasing population of mobfle users leads to congestion problems in these systems, and motivatw the development of more ficient management sdemw.This work pr=ents a novel hierarchical Location Management scheme, in which every level of the hierarchy reprwents a partition to geographic regions.Within each level of the hierarchy the system records the location of every mobile user to a c@ain degree of accuracy.The degree of accuracy is incre=ed as we go down the levek until we reach the node to which the mobile user is attached.We develop distributed procedures for locating the mobile users (termed the Sear& operation) and updating the system location records (termed the Update operation) with user movements.The proposed scheme guarantew upper bound on the procedures costs: The amortized compltity of the mobile user update operations is O(Move.log Move), where Move is the total geographic distance that the mobile user has traveled.The upper bound of a search operation is ~mear with the distance between the search originator and the target node.These upper bounds do not depend on the network size.Therefore, the proposed scheme is attractive for the next generation of PCS.The management system is &o suitable for supporting anycaat and territory rwtricted users.

No abstract available.

This work is concerned with the problem of broadcasting a large message efficiently when each processor has partial prior knowledge about the contents of the broadcast message. The partial information held by the processors might be out of date or otherwise erroneous, and consequently, different processors may hold conflicting information. Tight bounds are established for broadcast under such conditions, and applications of the broadcast protocol to other distributed computing problems are discussed.

We present a new network design problem that is applicable for designing virtual paths (VPs) in an asynchronous transfer mode (ATM) network to efficiently support client/server applications. We present several alternatives for the solution, compare their properties, and focus on a novel "greedy" solution, which we prove to optimize certain important criteria (namely, the network overhead for a request/response and the utilization of bandwidth and routing table resources). We also present simulation results that demonstrate the performance and scalability of our solution. In addition, we propose a new efficient bandwidth allocation scheme which is tailored for client/server applications over ATM networks.

Current high-speed packet switching systems, ATM in particular, have large port buffering requirements. The use of highly integrated ASIC technology for implementing high-degree and high-speed switch fabrics is facing a technology mismatch in the sense that today's chip technology does not allow to integrate on-chip the high-speed switching fabric with the large buffering requirements. Consequently, many designs are based on the principles of queueing displacement, i.e., they attempt to move the queueing point off-chip. This is usually done by considerably speeding-up the on-chip switch output ports and placing a second external stage of buffering between the switch fabric and the outgoing link circuitry. Such designs are very popular and are used by many current ATM switch vendors. While such schemes are widely used, no rigourous analysis has so far been offered to evaluate the design trade-offs and to quantify the design points. The model we use to analyze the performance of the above system is a two-node tandem queueing system. The first node in the tandem corresponds to the internal buffer while the second node in the tandem corresponds to the external buffer. It is assumed that the internal buffer is able to transfer c/sub 1/ cells per time unit to the external buffer, while the external buffer is served at a lower rate of c/sub 2/ cells per time unit.

In high-speed networks it is desirable to interleave routing and resource (such as bandwidth) reservation. The PNNI standard for private ATM networks is an example of an algorithm that does this using a sequential crank-back mechanism. We suggest the implementation of resource reservation along several routes in parallel. We present an analytical model that demonstrates that when there are several routes to the destination it pays to attempt reservation along more than a single route. Following this analytic observation, we present a family of algorithms that route and reserve resources along parallel subroutes. The algorithms of the family represent different trade-offs between the speed and the quality of the established route. The presented algorithms are simulated against several legacy algorithms, including the PNNI crank-back, and exhibit higher network utilization and faster connection set-up time.

Ring network architectures that employ spatial reuse permit concurrent transmissions of messages over different links. While spatial reuse increases network throughput, it may also cause starvation of nodes. To alleviate this problem, various policies have been suggested in the literature. In this paper, we concentrate on a class of such policies that achieves fairness by allocating transmission quotas to nodes. For such policies, we provide mechanisms for improving delays and increasing overall throughput without compromising fairness.

We present a new network design problem that arises when designing virtual paths in an ATM network to properly support client/server applications. We present several alternatives for the solution, discuss their pros and cons, and focus on a novel "greedy" solution, which we prove to optimize certain important criteria (namely, the network overhead for a request/response and the utilization of bandwidth and routing table resources). In addition, we propose a new, efficient bandwidth allocation scheme which is tailored for client/server applications over ATM networks. The results in this work imply the importance of ATM switches that switch both VPs and VCs.

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.

Addresses the problem of designing optimal buffer management policies in shared memory switches when packets already accepted in the switch can be dropped (pushed-out). The goal is to maximize the overall throughput, or equivalently to minimize the overall loss probability in the system. For a system with two output ports, the authors prove that the optimal policy is of pushout with threshold type (POT). The same result holds if the optimality criterion is the weighted sum of the port loss probabilities. For this system, the authors also give an approximate method for the calculation of the optimal threshold, which they conjecture to be asymptotically correct. For the N-ported system, the optimal policy is not known in general, but it is shown that for a symmetric system (equal traffic on all ports) it consists of always accepting arrivals when the buffer is not full, and dropping one from the longest queue to accommodate the new arrival when the buffer is full. Numerical investigations show that under the optimal POT policy the loss probability of a port is insensitive to traffic fluctuations in the other port.

We address the problem of designing optimal buffer management policies in shared memory switches when packets already accepted in the switch can be dropped (pushed-out). Our goal is to maximize the overall throughput, or equivalently to minimize the overall loss probability in the system. For a system with two output ports, we prove that the optimal policy is of push-out with threshold type (POT). The same result holds if the optimality criterion is the weighted sum of the port loss probabilities. For this system, we also give an approximate method for the calculation of the optimal threshold, which we conjecture to be asymptotically correct. For the N-ported system, the optimal policy is not known in general, but we show that for a symmetric system (equal traffic on all ports) it consists of always accepting arrivals when the buffer is not full, and dropping one from the longest queue to accommodate the new arrival when the buffer is full. Numerical results are provided which reveal an interesting and somewhat unexpected phenomenon. While the overall improvement in loss probability of the optimal POT policy over the optimal coordinate-convex policy is not very significant, the loss probability of an individual output port remains approximately constant as the load on the other port varies and the optimal POT policy is applied, a property not shared by the optimal coordinate-convex policy.>

Scheduling packets to be forwarded over a link is an important subtask of the routing process in both parallel computing and in communication networks. This paper investigates the simple class of greedy scheduling algorithms, namely, algorithms that always forward a packet if they can. It is first proved that for various “natural” classes of routes, the time required to complete the transmission of a set of packets is bounded by the number of packets, k, and the maximal route length, d, for any greedy algorithm (including the arbitrary scheduling policy). Next, tight time bounds of $d+k-1$ are proved for a specific greedy algorithm on the class of shortest paths in n-vertex networks. Finally, it is shown that when the routes are arbitrary, the time achieved by various “natural” greedy algorithms can be as bad as $\Omega (d \sqrt {k} + k)$, for any k, and even for $d = \Omega (n)$.

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.>

In future networks, transmission and switching capacity will dominate processing capacity. The authors investigate the way in which distributed algorithms should be changed in order to operate efficiently in this new environment. They introduce a class of new models for distributed algorithms which make explicit the difference between switching and processing. Based on these new models they define new message and time complexity measures which, they believe, capture the costs in many high-speed networks more accurately then traditional measures. In order to explore the consequences of the new models, they examine three problems in distributed computation. For the problem of maintaining network topology they devise a broadcast algorithm which takes O(n) messages and O(log n) time for a single broadcast in the new measure. For the problem of leader election they present a simple algorithm that uses O(n) messages and O(n) time. The third problem, distributed computation of a "globally sensitive" function, demonstrates some important features and tradeoffs in the new models and emphasizes and differences with the traditional network model. The results of the present paper influenced later research, as well as the design of IBM Networking Broadband Services (NBBS).>

Ring network architectures that employ spatial reuse permit concurrent transmissions of messages over different links. While spatial reuse increases network throughput, it may also cause starvation of nodes. To alleviate this problem, various policies have been suggested in the literature. In the paper the authors concentrate on a class of such policies that achieve fairness by allocating transmission quotas to nodes. For such policies, they provide mechanisms for improving delays and increasing overall throughput without compromising fairness.>

The authors study discrete-time, single server queueing systems, with messages that consist of blocks of consecutive cells. They focus on the model of dispersed cell generation processes which naturally arises in packet switched networks such as ATM. Several important performance measures are considered. These are the message delay process, the maximum delay of a cell in a message and the number of cells in a message whose delays exceed a pre-specified time threshold. The latter two quantities are important for proper design of playback algorithms and time-out mechanisms. They present a new analytical approach that yields efficient recursions for the computation of the probability distribution of each quantity. Numerical examples are provided to compare this distribution with the distribution obtained by using an independence assumption on the cell delays. These examples show that the correlation between cell delays of the same message has a strong effect on each of these quantities.>

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.>

Buffering policies that provide different loss priorities to packets/cells with no change in packet ordering (space priority disciplines) are studied. These policies are motivated by the possible presence, within the same connection, of packets with different loss probability requirements or guarantees. Examples of such applications are voice and video coders that generate information of unequal importance, and rate control mechanisms that mark excess traffic with a low priority rate violation tag. The focus is on the identification and evaluation of buffering policies that can guarantee performance, i.e. loss probability, to high priority packets irrespective of the traffic intensity and arrival patterns of low priority packets, while preserving the original ordering among packets. Such policies are termed protective policies.>

A family of queues for which the service time B/sub n/ of customer n depends on the interarrival time I/sub n/ between customers n-1 and n and the random variables I/sub n/ and B/sub n/ exhibit a proportionality relation is studied. In particular, the focus is on dependencies that arise naturally in communication systems, where the finite speed of the communication links constrains the amount of data that can be received in a given time interval. The simple case of a deterministic proportionality relation between the service time of a customer and its preceding interarrival time is considered and extended to allow the addition of an independent, generally distributed overhead to the service time. Several models that capture the on-off behavior of communication links in packet networks are then addressed. In all cases, expressions for the delay experienced by a packet in the system and illustrative numerical examples are provided.>

A family of queuing systems in which the interarrival time I/sub n+1/ between customers n and n+1 depends on the service time B/sub n/ of customer n is considered. Specifically, cases where the dependency between I/sub n+1/ and B/sub n/ is a proportionally relation and B/sub n/ is an exponentially distributed random variable is considered. Such dependencies arise in the context of packet-switched networks from employing rate policing functions which regulate the amount of data that can arrive at a link within any given time interval. The models developed and the associated solutions are, however, of independent interest and potentially applicable to other environments. Several scenarios that consist of adding an independent random variable to the interarrival time, allowing the proportionality to be random, and the combination of the two are considered. Numerical results are compared to those for an equivalent system without dependencies.>

The authors study the message queuing delays in a node of a communication system, where a message consists of a block of consecutive packets. Two types of message generation process are distinguished. The message can be generated as a batch or it can be dispersed over time. The authors focus on the dispersed generation model. The main difficulty in the analysis is due to the correlation between the system states observed by different packets of the same message. A technique for analyzing the message delay in such systems for different arrival models is introduced, and it is shown that the correlation has a strong effect on the performance of the system. For an M/M/1 system with variable size messages, an explicit expression for the Laplace-Stieltjes transform (LST) of the message delay is obtained. It is shown that the commonly used independence assumption can lead to wrong conclusions.>

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.>

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.>

An approach to congestion control based on open-loop regulation of the input is investigated. The input rate regulation schemes are studied from the viewpoint of their smoothing and regulating effects on the incoming traffic. The smoothing effect is characterized by the variance of the interdeparture time of the packet departure process from the input rate regulation mechanism. Under the assumption of Poisson arrivals the characteristics of this departure process are explicitly derived in terms of the particular scheme's parameters, and the tradeoff between the smoothness of the departure process and packet waiting time is studied. Results for both finite- and infinite-buffer pool sizes are presented.>

A family of queues is studied for which the service time B/sub n/ of customer n and the interarrival time I/sub n/ between customers n-1 and n exhibit some sort of proportionality. The focus is on dependencies that arise naturally in the context of communication systems, where the finite speed of the communication links constrains the amount of data that can be received in a given time interval. The simple case of a deterministic proportionality relation between the service time of a customer and its preceding interarrival time is considered. This is extended to allow the addition of an independent, generally distributed overhead to the service time of each customer. Several models that capture the ON-OFF behavior of communication links in packet networks are considered. In all cases, expressions for the delay experienced by a packet in the system are provided. Numerical examples illustrate the impact of dependencies through comparison with less accurate models. The results should be of relevance to environments other than communication as well.>

The packet loss process in a single-server queueing system with a finite buffer capacity is analyzed. The model used addresses the packet loss probabilities for packets within a block of a consecutive sequence of packets. An analytical approach is presented that yields efficient recursions for the computation of the distribution of the number of lost packets within a block of packets of fixed or variable size for several arrival models and several numbers of sessions. Numerical examples are provided to compare the distribution obtained with that obtained using the independence assumption to compute the loss probabilities of packets within a block. The results show that forward error correction schemes become less efficient due to the bursty nature of the packet loss processes; real-time traffic might be more sensitive to network congestion than was previously assumed; and the retransmission probability of ATM messages has been overestimated by the use of the independence assumption.>

Protocols for establishing, maintaining, and terminating connections in packet-switched networks have been studied, and numerous standards have been developed to address this problem. The authors reexamine connection establishment in the context of a high-speed packet network, introduce a protocol for connection establishment/takedown that is appropriate for such a network, and explain its advantages over previously proposed protocols. The main features of the proposed protocol are: fast bandwidth reservation in order to avoid as much as possible reservation conflicts, guaranteed release of the reserved bandwidth even under modal and link failures, and soft recovery from processor failures, which allows the maintenance of existing connections under processor failure provided the switch and links do not fail. The underlying model that is used is the PARIS/plaNET network, but the protocol can be adapted to other fast packet networking architectures as well.>

Considers a slotted ring in which simultaneous transmission of messages by different stations is allowed, a property referred to as spatial reuse. Ring networks with spatial reuse can achieve significantly higher throughput than standard token rings but they also introduce the possibility of starvation for some nodes on the ring. To alleviate this problem, various policies have been suggested in the literature. The present objective is to characterize the node throughputs achievable by general transmission policies in ring networks with spatial reuse and then to evaluate the throughput trade-off for a class of policies that has been proposed in the literature in order to avoid starvation. Specifically, the authors study a policy that is based on the idea of allocating transmission quotas to the nodes. Each node is guaranteed transmission of his quota within a specified interval. The authors show that by appropriately allocating the quotas, policies that satisfy general optimality criteria-in particular criteria related to fairness-can be designed. They also study the asymptotic behavior of the quota policy when either the quotas or the number of nodes increase.>

An efficient recursive computation methodology is introduced to obtain the exact distribution of the number of lost packets in a block of packet arrivals of a given size for different arrival models and a different number of sessions. The exact distribution is compared with the distribution obtained from an independence assumption on the loss probability of packets. Numerical examples are provided to show that the exact distribution may be worse than the distribution obtained under the independence assumption for applications such as forward error correction or better for applications such as straight message retransmission.>

This work concerns the problem of broadcasting a large message efficiently when each processor has partial prior knowledge tocol to other distributed computing problems are discussed.

It is shown that keeping track of history allows significant improvements in the realistic model of communication complexity of dynamic network protocols. The communication complexity for solving an arbitrary graph problem is improved from Theta (E) to Theta (V), thus achieving the lower bound. Moreover, O(V) is also the amortized complexity of solving an arbitrary function (not only graph functions) defined on the local inputs of the nodes. As a corollary, it is found that amortized communication complexity, i.e. incremental cost of adapting to a single topology change, can be smaller than the communication complexity of solving the problem from scratch. The first stage in the solution is a communication-optimal maintenance of a spanning tree in a dynamic network. The second stage is the optimal maintenance of replicas of databases. An important example of this task is the problem of updating the description of the network's topology at every node. For this problem the message complexity is improved from O(EV) to Theta (V). The improvement for a general database is even larger if the size of the database is larger than E.>

The authors suggest and investigate a general input congestion control scheme that takes into account a broad spectrum of network issues. As a preventive congestion control strategy, a leaky-bucket-type scheme operating on a session basis that limits the session's average rate and the burstiness is proposed. This restrictive control is combined with an optimistic bandwidth usage scheme which works by marking packets into two different colors, green and red. The packets are marked so that the average green packet rate entering the network is at the reserved average rate. The average red packet rate represents traffic in excess of this guaranteed average rate and is sent to further utilize unused bandwidth in the network. Both types of packets are further filtered by a spacer which limits the peak rate at which the packets enter the network. The marked packets are then sent into the network, where they are treated according to their color, using at each intermediate node a simple threshold policy.>

The design principles of a ring network with spatial reuse are described. The goal is to provide the same functions as designs that do not permit spatial reuse and concurrent transmission. A distributed fairness mechanism for this architecture is presented. The basic fairness mechanism can be extended for implementing multiple priority levels and integrating asynchronous with synchronous traffic. The ring is full-duplex and has two basic modes of operation: a buffer insertion mode for variable-size packets and a slotted mode for fixed-size packets. As a result, this architecture is suitable for a wide range of applications and environments. Concurrent access and spatial reuse permit simultaneous transmissions over disjoint segments of a bidirectional ring and, therefore, can increase the effective throughput by a factor of four or more. The efficiency of this architecture does not degrade as the bandwidth and physical size of the system increase. The combination of a full-duplex ring, spatial reuse, a reliable fairness mechanism, and the exploitation of recent advances in fiber-optic technology are the basis for the Metaring network architecture.>

IntroductionWe describe the control protocols of the PARIS experimental network.This high bandwidth network for integrated communication (data, voice, video) ia 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 of specialized hardware to support faster packet handling and control protocols.A new network control architecture is presented which exploits the specialized hardware in order to support the expected real time needs of future traffic.In particular, since control information can be distributed quickly, 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.

Protocols for establishing, maintaining and terminating connections in packet switched networks have been studied in the literature and numerous standards have been developed to address this problem. In this paper, we reexamine connection establishment in the context of a fast packet network with an integrated traffic load, explain why previously proposed solutions are inadequate and develop a protocol for connection establishment/takedown that is appropriate for such a network. The underlying model that we use is the recently developed PARIS network, though our ideas are sufficiently general to cover many other fast packet networking architectures.

An efficient way to synchronize an asynchronous network with a bounded delay message delivery is presented. Two types of synchronization algorithm are presented. Both types require an initializing phase that costs mod E mod messages (where mod E mod is the number of links). The first requires an additional bit in every message and increases the time complexity by a factor of 2. The second does not require any additional bits but increases the time complexity by a factor of 3. How to overcome differences in nodal timer rates is explained.>

Recursive formulas are derived for computing the state probabilities in priority queuing systems (preemptive and nonpreemptive). The derivation is based only on the general structure of the generating function involved, and thus is similar and more general than previous methods. Also discussed are the applications of the method to other queuing systems.>

New distributed dynamic channel assignment algorithms for a multihop packet radio network are introduced. The algorithms ensure conflict-free transmissions by the nodes of the network. The basic idea of the algorithms is to split the shared channel into a control segment and a transmission segment. The control segment is used to avoid conflicts among nodes and to increase the utilization of the transmission segment. It is shown how these algorithms can be used in order to determine time-division multiple access (TDMA) cycles with spatial reuse of the channel.>

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/sup 2/) 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.>

Distributed dynamic channel assignment algorithms for a multihop packet radio network are introduced. The algorithms ensure conflict-free transmissions by the nodes of the network. The basic idea of the algorithms is to split the shared channel into a control segment and a transmission segment. The control segment is used to avoid conflicts among the nodes and to increase the utilization of the transmission segment. It is shown how these algorithms can be used to determine time-division multiaccess cycles with spatial reuse of the channel.>

No abstract available.

The authors model the internal structure of a packet-switching node in a real-time system and characterize the tradeoff between throughput, delay, and packet loss as a function of the buffer size, switching speed, etc. They assume a simple shared-single-path switch fabric, though the analysis can be generalized to a wider class of switch fabrics. They show that with a small number of buffers the node will provide a guaranteed delay bound for high-priority traffic, a low average delay for low-priority traffic, no loss of packets at the input and low probability of packet loss at output.>

Multiple-access algorithms that handle erasures as well as captures are introduced. The algorithms are evaluated according to the maximal throughput that they can support for a Poisson arrival process. An example is given which shows that, in practice, the positive effect of captures compensates the negative effect of erasures. An approach that effectively utilizes the capture phenomena is introduced. This approach incorporates a random power-level-selection scheme that allows each node to choose randomly to transmit in one of several allowable levels of power. Design issues such as number of levels, selection schemes, etc. are discussed.>

The standard model of a multiple-access channel with ternary feedback is considered. When packets of a batch of k nodes initially collide, it is assumed that no a priori statistical information about k is available. An algorithm is presented and analyzed that enables the nodes to compute a statistical estimate of k. Combining the estimation procedure with tree algorithms leads to batch-resolution algorithms that resolve conflicts more efficiently than any other reported to date. Both complete-resolution and partial-resolution algorithms are presented.>

Distributed algorithms for the detection and resolution of deadlocks in store-and-forward computer communication networks are presented and validated. The algorithms use a fixed amount of storage at each node (that is independent of the size of the network). The detection algorithm is simple but requires network-wide coordination. The resolution algorithm is based on earlier approaches, but uses the network-wide coordination to address certain synchronization problems. When the detection and resolution algorithms are merged, it is guaranteed that packets will arrive at their destinations in finite time.

End-to-end protocols in computer networks in which the topology changes with time are investigated. A protocol that delivers all packets ordered, without duplication, and which uses a window is presented. Using a precise model of the network correctness of the protocol is proven. The use of the window for flow control is also addressed.

A system with many nodes accessing a common receiver is considered. The forward channel is a time-slotted collision-type common radio channel. Due to a nonreliable forward channel, the receiver may misinterpret the actual event of a slot. For instance, an idle or a success slot can be interpreted as a conflict and a conflict or a success slot can be interpreted as an idle slot. The former kind of error is called a noise error, while the latter is called an erasure. Splitting multiple-access algorithms are introduced that can handle erasures as well as noise errors. A remarkable feature of the algorithms is that they ensure that, under stable operation, all packets are eventually successfully transmitted, including the erased packets (those packets that were involved in an erasure). The property that is exploited in devising these algorithms is that nodes whose packets were erased can detect that situation as they transmit and acknowledge that the slot was idle. Consequently, they can either retransmit immediately or wait until some agreed point in time (such as the end of a collision resolution interval) and then transmit. The performances of the proposed algorithms are evaluated according to the maximal throughput they can support for Poisson arrival process. The performance degradation due to erasures and noise errors is quantified.

A distributed algorithm for the detection of deadlocks in store-and-forward communication networks is presented. At first, we focus on a static environment and develop an efficient knot detection algorithm for general graphs. The knot detection algorithm uses at most O(n2+ m) messages and O(log (n)) bits of memory to detect all deadlocked nodes in the static network. Using the knot detection algorithm as a building block, a deadlock detection algorithm in a dynamic environment is developed. This algorithm has the following properties: It detects all the nodes which cause the deadlock. The algorithm is triggered only when there is a potential for deadlock and only those nodes which are potentially deadlocked perform the algorithm. The algorithm does not affect other processes at the nodes.

A distributed algorithm for the detection of deadlocks in store-and-forward communication networks is presented. At first, we focus on a static environment and develop an efficient knot detection algorithm for general graphs. The knot detection algorithm uses at most Ο(n2 + m) messages and Ο(log(n)) bits of memory to detect all deadlocked nodes in the static network. Using the knot detection algorithm as a building block, a deadlock detection algorithm in a dynamic environment is developed. This algorithm has the following properties: It detects all the nodes which cause the deadlock. The algorithm is triggered only when there is a potential for deadlock and only those nodes which are potentially deadlocked perform the algorithm. The algorithm does not affect other processes at the nodes.

In many communication systems, the stronger of two or more overlapping packets might capture the receiver and thus be received without error. The effect of capture on collision-resolution algorithms in a slotted ALOHA type broadcasting network is investigated here. Extensions to the algorithms are suggested for both the situations in which the receiver can or cannot distinguish between success slots and capture slots. In particular, we present a class of retransmission schemes for packets that have been transmitted during capture slots but have not been received correctly. The performance analysis is confined to a simplified model in which the nodes of the network are divided into two groups and only packets sent by the nodes of one of them might be captured. For this simplified model and for each extended algorithm, explicit recursive equations are given, from which the average conditional collision-resolution interval length, as well as the maximal throughput, can be determined. As expected, we show that in the presence of capture, the performance of the network is improved and the maximal attainable throughput is increased. Extensions of the simplified model such as dividing the nodes intoKgroups instead of two, or considering the situation that capture depends on relative distances and transmission powers, are also discussed. For the latter situation we give simulation results.

The effect of capture on splitting-type protocols in a slotted ALOHA broadcasting network is investigated. At first, it is assumed that the nodes of the network are divided into two groups, and only packets sent by nodes of one of the groups might be captured. The situation in which the receiver can distinguish between success slots and capture slots and that in which it cannot are both considered. For each of these situations, splitting-type multiple access protocols are described and their performance in terms of achievable throughputs is evaluated. Extensions of these protocols to a general capture model are also discussed.