Traditional broadcast protocols are inappropriate for the high-speed networks of the future. Such protocols are limited by the speed of software processing, which becomes a bottleneck as network speeds increase. This paper presents broadcast protocols that are appropriate for high-speed networks, and are tolerant of failures involving the loss of messages. The protocols are based primarily on the simple hardware functions present in a high-speed network node. This leads to message delivery at hardware speeds. In the unlikely event of a failure, software intervention is required to guarantee the timely termination of the protocol; however, this software processing does not interfere with message delivery.

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

An essential function for achieving security in computer networks is reliable authentication of communicating parties and network components. Such authentication typically relies on exchanges of cryptographic messages between the involved parties, which in turn implies that these parties be able to acquire shared secret keys or certified public keys. Provision of authentication and key distribution functions in the primitive and resource-constrained environments of low-function networking mechanisms, portable, or wireless devices presents challenges in terms of resource usage, system management, ease of use, efficiency, and flexibility that are beyond the capabilities of previous designs such as Kerberos or X.509. This paper presents a family of light-weight authentication and key distribution protocols suitable for use in the low layers of network architectures. All the protocols are built around a common two-way authentication protocol. The paper argues that key distribution may require substantially different approaches in different network environments and shows that the proposed family of protocols offers a flexible palette of compatible solutions addressing many different networking scenarios. The mechanisms are minimal in cryptographic processing and message size, yet they are strong enough to meet the needs of secure key distribution for network entity authentication. The protocols presented have been implemented as part of comprehensive security subsystem prototype called KryptoKnight.>

Article Free Access Share on Multimedia networking: applications and challenges Author: Inder Gopal IBM T. J. Watson Research Center, Yorktown Heights, NY IBM T. J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims PODC '94: Proceedings of the thirteenth annual ACM symposium on Principles of distributed computingAugust 1994 Pages 9–12https://doi.org/10.1145/197917.197934Published:14 August 1994Publication History 1citation449DownloadsMetricsTotal Citations1Total Downloads449Last 12 Months52Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In computer networks with decentralized control, it is necessary to provide a distributed query mechanism, whereby a node can dynamically discover the location of a remote resource. The authors propose a query mechanism based on flooding with feedback, which uses no more than two messages over any link. They examine the fault tolerant aspects of this distributed query mechanism, operating in a network where links and nodes may fail and show that, under certain conditions, the resource is indeed found. They then construct enhancements to this mechanism, where the conditions under which the resource is found are substantially relaxed, at the cost of some increase in message complexity.>

Multicasting is a communication mode in which a given source communicates with a subset of the entire network user population. Previous work in this area concentrated on the multicast problem of a single source that always communicates with the same destination group. In this paper we investigate a more natural case of multicast communication where a single source communicates with several different destination groups. Specially, we focus on the design and analysis of multicast data link protocols for this environment. Straightforward implementations of such protocols are inappropriate in the case of a large destination population, as a source will have to store a large amount of state information even if it maintains only a single variable per destination. In most typical applications, though. The total destination population is large, the number of destinations that any given source is in conversation with, is typically small. We propose a framework for adapting protocols so that memory requirement does not grow with the total destination population but depends upon the number of destinations actually in communication with the source. The savings in memory are achieved by slightly increasing the amount of communication. We address the performance of such a protocol in an environment of a broadcast channel. We analyze several strategies and control techniques and demonstrate the tradeoff between throughput and the amount of memory.>

Fast packet-switching has been chosen as the basis for future high speed, "universal" networks. The successful deployment of such networks will clearly depend on a wide range of factors such as cost and technology, but the authors believe that foremost among all is how well they will support existing and future applications. Emphasizing an application oriented perspective is one of the main motivation of the paper. The authors denote by "transparency" the ability of a network to transport application information while altering or manipulating it as little as possible, and believe it will be key to the acceptance of high-speed networks. While the concept is clearly not new, they articulate the need for it and illustrate its feasibility and the advantages it affords through the example of the plaNET network. In particular, they argue that a "transparent" data transfer mechanism can be provided that is both compatible with current standard proposals such as ATM and frame relay, and offers applications the choice of the data transfer mode that best meet their needs. A number of examples are used to illustrate these claims.>

Most existing designs for two-way cryptographic authentication protocols suffer from one or more limitations. Among other things, they require synchronization of local clocks, they are subject to export restrictions because of the way they use cryptographic functions, and they are not amenable to use in lower layers of network protocols because of the size and complexity of messages they use. Designing suitable cryptographic protocols that cater to large and dynamic network communities but do not suffer from these problems presents substantial problems. It is shown how a few simple protocols, including one proposed by ISO, can easily be broken, and properties that authentication protocols should exhibit are derived. A methodology for systematically building and testing the security of a family of cryptographic two-way authentication protocols that are as simple as possible yet resistant to a wide class of attacks, efficient, easy to implement and use, and amenable to many different networking environments is described. Examples of protocols of that family that presents various advantages in specific distributed system scenarios are discussed.>

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

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

AURORA is one of five US testbeds charged with exploring applications of, and technologies necessary for, networks operating at gigabit per second or higher bandwidths. The authors provide an overview of the goals and methodologies employed in AURORA and report preliminary results from the first year of research. AURORA is an experiment in collaboration, where government support has spurred interaction among centers of excellence in industry, academia, and government. The emphasis of the AURORA testbed is research into the supporting technologies for gigabit networking. The targets include new software architectures, network abstractions, hardware technologies, and applications. The AURORA testbed will provide a platform in which researchers can explore business and scientific applications of gigabit networks, while evolving the network architecture to meet the needs of these emerging applications.>

The authors address the problem of preempting ongoing calls in a communication network in order to accommodate new calls. They investigate some problems that relate to making the best decision on which (if any) call to preempt. It is shown that versions of the problem are computationally intractable, and simple and efficient heuristics to approximate the optimal strategy are provided. The authors study the problem from the online perspective, and characterize what can be done under different circumstances.>

Asynchronous transfer mode (ATM) is being suggested as the basis for future high speed, universal networks. A key requirement for future ATM networks will be transparency, i.e. for the network to alter or manipulate the user information as little as possible. A transparent transport mechanism, plaNET, based on extensions of the current ATM standard and IBM's earlier PARIS technology, is proposed. It is shown how plaNET can satisfy the universal transport requirement of ATM, while avoiding some demonstrated deficiencies. In fact, plaNET could be viewed as an enhanced version of ATM that may be more suitable for the late 1990s than the current standard.>

a software search is required to determine whether or not to forward the message.With increasing network speed, this search becomes a bottleneck.There are two approaches to overcoming this bottleneck.The first approach is to implement the search described above directly in very high speed hardware; unfortunately, such a solution may not be cost-effective.The second approach, the one we have chosen, is to devise a new broadcast protocol that does not require such a search.This paper presents a ~asf distributed broadcast protocol for a high speed, arbitrary topology, point-to-point network.The protocol uses simple hardware switching functions to perform a,

The heterogeneous traffic in this environment can be categorized into a rapidly changing type composed of packet switched data traffic and a relatively static type composed of circuit switched voice traffic. From the time-slot assignment viewpoint, the problem is to construct an efficient TDMA frame that permits the static voice traffic to be transmitted and, then, on a frame-by-frame basis to attempt to insert the data packets into the slots that are unused by the voice traffic. It is proved that the problem is NP-complete, even for very simple traffic configurations. Several suboptimal fast heuristic algorithms are presented and empirically compared by experiments on randomly generated traffic patterns. The experiments reveal that, on the average, the algorithms give close to the optimal performance.>

The current trend in network technology is to implement as much of the switching function as possible directly in specialized high-speed hardware. A broadcast algorithm for such a network that is tolerant of failures in the form of message loss is presented. The model used is based on the one introduced by Cidon et al. (see Proc. of Seventh Annual ACM Symp. on Principles of Distributed Comput., Toronto, Canada. P.75-89, 1988); the hardware functions assumed are simple enough to be implemented in high-speed logic. The basic idea is to forward broadcast messages directly in hardware, thereby avoiding software-introduced delays. Software intervention (possible only after the broadcasted message has already been forwarded) is required only to ensure termination in case of failures. With high probability, the broadcast will terminate in time O(n tau /sub max/), where n is the number of nodes and tau /sub max/ is an upper bound on (variable) message delivery time across a link.>

A family of automatic repeat request (ARQ) protocols that can be implemented through relatively simple hardware (one or more first in, first out, or FIFO, buffers and some limited state information) is considered. With a single FIFO buffer, the protocol is identical to a regular go-back-N. By increasing the number of FIFO buffers, a full selective repeat can be reached. The main result is to show that, for typical error rates, performance close to selective repeat can be obtained with two or three FIFO buffers. The family of protocols is described in detail, and the throughput is analyzed. For the two-buffer case, a closed-form solution is obtained, while for other cases, simulation results are given.>

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

In computer networks with decentralized control, it is necessary to provide a directory service which enables users to discover dynamically the location of other users. The authors examine the protocols for maintaining consistent directory information for casually connected users that can connect and disconnect from the network at will. They propose protocols for both hierarchical and nonhierarchical directory systems. The protocols do not rely on sequence numbers and consequently do not require 'safe store' at the user.>

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

In this paper we consider the problem of dynamically assigning addresses to stations attached to a broadcast network. We present a distributed protocol which guarantees that a new station will eventually be assigned an address if one is free, and furthermore, that no two stations on the network will have the same address. We show how the protocol can be simplified in certain specific environments.

Much previous work has been done on the prevention of store-and-forward deadlock in computer networks using buffer reservation. The emphasis has been on reducing the number of reserved buffers necessary in each node. In this paper, we propose a scheme that, for most networks, will guarantee deadlock freedom for any arbitrary routing with a third fewer reserved buffers than the best previously proposed scheme.

In this paper, we investigate the problem of constructing a TDMA frame for a multibeam satellite system. Our objective is to permit the transmission of a given pattern of traffic, while ensuring that the number of times that the on-board switch needs to be reconfigured is minimized. We find that the underlying optimization problem is computationally intractable, but go on to suggest an efficient heuristic algorithm which we validate through experiments on randomly generated traffic patterns.

In this paper we study some link control protocols for use in point-to-multipoint communication over broadcast links. We concentrate on automatic repeat request protocols of the go-back-Ntype and define, analyze, and compare three such protocols. A major contribution of this paper is a relatively simple protocol which is easy to implement and performs very well under a wide range of conditions. Our analytical models show that this protocol performs considerably better than the other go-back-Nprotocols, particularly in environments with a large number of receivers.

In this paper we consider the problem of local wiring in a VLSI chip. The problem is one of interconnecting two sets of terminals, one set on each side of a wiring channel, in accordance with a given interconnection pattern, and to accomplish this while minimizing some objective function. We make the further assumption that the terminals are not rigidly positioned and can be "moved" provided that this does not change the structural intent of the circuit. Several objective functions are considered-channel width, channel length, channel area, channel perimeter, number of via holes, as well as some constrained objective functions. For some of these objective functions, we are able to find polynomial time optimal algorithms while, for others, we prove NP-completeness and suggest efficient heuristics.

In this paper we study the traffic scheduling problem in an SS/TDMA system with interfering beams. We investigate a twostep approach, the first step being the assignment of orthogonal polarization to reduce the interference, and the second step being the scheduling of traffic, taking into account the "resultant" interference. The first step we show can be solved in polynomial time in most cases, while the second step we prove to be NP-complete, even for very simple interference patterns. We suggest several suboptimal algorithms for this second step and, by experimental trials on randomly generated traffic patterns, show that on the average they produce close to optimal solutions.

In this paper we consider an SS/TDMA system withMuplink beams andNdownlink beams, where uplink beamihas bandwidth βiand downlink beamjhas bandwidth αj. The maximum traffic which can be handled by the satellite (in any given time slot) is assumed to beK. Multiplexing and demuitiplexing are also assumed. An optimal time slot assignment algorithm to minimize the total transmission time for any given traffic demand matrix is proposed and analyzed. Other system configurations of interest are also discussed.

In this paper, we examine the problem of time-slot assignment in an SS/TDMA system operating in a packet-switched environment. We seek to assign time slots in order to minimize average packet waiting time and in order to maximize transponder utilization. We show that an assignment which achieves both objectives exists and develop a branch-and-bound algorithm to find it. In addition, we suggest several heuristics which require much less computational effort and give very close to optimal results. We derive theoretical bounds on the performance of these heuristics and perform simulation trials to show that, on average, the heuristics are very much better than their bounds suggest, and are, in fact, extremely close to optimal.