We present a set of protocols for creating a secure processing tree used for completing a task without divulging critical information. We analyze the information that is exchanged during the protocols and the effect of compromising participants.

This paper introduces techniques that help proving the safety of cooperative driving applications. Most automotive applications are evaluated by means of simulations and test tracks, which cannot provide the degree of confidence that is demanded by the driving public. We introduce probability verification as an evaluation tool that provides greater degree of confidence over safety. This technique is applicable to systems with large state spaces that cannot be exhaustively verified by other model checking techniques. We present a protocol that assists drivers in merging between other vehicles. The protocol is built on a multiple stack architecture that partitions the system into smaller manageable components that can be tested and verified individually. A module is verified assuming that the modules that it depends on have been verified. The modules in different vehicles use synchronized clocks to reduce the number of states needed to be examined in the composite protocols that describe their interactions. We are able to show that system failures will occur with a sufficiently small probability. Since probabilistic verification is also used to verify the operation of the modules that provide services, the residual probability of failure of these modules must be considered in the probabilistic verification of any module.

This paper presents a broadcast protocol that makes cooperative driving applications safer. Collaborative driving is a rapidly evolving trend in intelligent transportation system. Current communication services provided by vehicular ad-hoc network (VANET) cannot guarantee fail-safe operation. We present a fail safe broadcast protocol (FSBP) that resides between the cooperative driving applications and VANET to make the cooperative driving applications work in a safer way. The protocol uses synchronized clocks with the help of GPS to schedule the broadcast transmissions of the participants. Electing not to transmit at a scheduled time is a unique message that cannot be lost because of a noisy or lost communication channel. This message is used to abort a collaborative operation and revert to an autonomous driving mode, similar to the current generation of intelligent vehicles, in which a vehicle protects itself. We describe a particular, simple protocol that uses a token passing mechanism. We specify the protocol as a finite state machine and use probabilistic verification to verify the protocol. This is the first formal verification of a multi-party broadcast protocol.

We present a general architecture for intelligent vehicles, especially collaborative driving applications. Intelligent vehicles are similar to communication networks as both types of systems interact with physical world using devices that are rapidly evolving, while intelligent vehicles are more complicated than communication network because they interact with the physical world in not only, one but several ways, and because many of the interactions have severe time constraints. The proposed architecture adopts multiple layered stack structures to address the issues. We also present a collaborative merge protocol as an instantiation of the proposed architecture, and discuss the advantage of the architecture in terms of the feasibility of model checking and conformance testing.

We propose an efficient encoding algorithm that considers multiple neighbors as next hop candidates for a packet, while searching for an optimal packet combination to transmit. Our algorithm, based on bipartite graphs, lets a node exhaustively search its queue to identify the maximum set of packets that can be combined in a single transmission. This algorithm can be easily integrated with a routing scheme in which a node considers multiple neighbors before choosing to forward a packet to one of them. We demonstrate this by integrating our algorithm with delta routing. Throughput benefit offered due to network coding is often hampered by congested nodes in a network. Delta routing improves throughput of a network by helping packets circumnavigate congestion. We demonstrate how our packet encoding algorithm can be coupled with such a routing mechanism in order to leverage the benefits offered by an efficient encoding scheme and enhanced routing both.

Vehicle automation has progressed from systems that monitor the operation of a vehicle and assist a driver, with functions such as antilock braking and cruise control, to systems that detect the operation of adjacent vehicles, to implement emergency braking and intelligent cruise control. The next generation of systems will share sensor readings and collaborate to control braking operations by looking several cars ahead or by creating safe gaps for merging vehicles. The rules that control the interaction between automobiles are protocols.

We promote the idea of deflecting packets in a structured wireless mesh deployment. In any wireless network, upon arrival of new packets when the sources and destinations are selected uniformly the majority of traffic goes through the center of the network, while the edges are underutilized. This situation becomes more apparent in a structured mesh deployment. We demonstrate that the throughput could be improved by deflecting packets away from the congested part of the network and towards the underutilized parts. We develop a simple routing protocol that allows network nodes to deflect packets. We demonstrate that the performance of deflection routing improves as the network size increases. Our extensive simulations show that despite of its simplicity deflection routing not only outperforms conventional shortest path routing but newly developed and complex opportunistic routing mechanisms as well. Our simulations show that for a moderate size network, deflection routing gives 51% higher throughput than the conventional routing mechanism, when a newly arrived packet selects its source and destination uniformly.

Several automobile manufacturers are offering assisted driving systems that use sensors to automatically brake automobiles to avoid collisions. Before extensively deploying these systems, we should determine how they will affect highway capacity. The goal of this paper is to compare the highway capacity when using sensors alone and when using sensors and vehicle-to-vehicle communication. To achieve this goal, the rules for using both technologies to prevent collisions are proposed, and highway capacity is estimated based on these rules. We show that both technologies can increase highway capacity. The increase in capacity is a function of the fraction of the vehicles that use a technology. If all of the vehicles use sensors alone, the increase in highway capacity is about 43%. While if all of the vehicles use both sensors and vehicle-to-vehicle communication, the increase is about 273%.

In this paper, we extends bandwidth balancing technique in wired networks to operate in mobile ad hoc networks (MANETs). In bandwidth balancing in Distributed-Queue-Dual-Bus (DQDB), different nodes occupy the same channel, and information about the bandwidth is transferred between nodes in the unused bandwidth. Similarly, in wireless networks, the capacity on a channel is shared by several sources at different nodes and the bandwidth information can be monitored on the shared medium. Using the bandwidth balancing technique, we introduce a flow control scheme for MANETs that limits each flow at each node in a transmission region to take only a fraction of the remaining capacity. Extensive simulations demonstrate that our flow control scheme is effective and can provide Quality of Service (QoS) guarantees for flows in MANETs.

We propose Polar Coordinate Routing (PCR) to create multiple paths between a source and a destination in wireless networks. Our scheme creates paths that are circular segments of different radii connecting a source and a destination. We propose a non-euclidean distance metric that allows messages to travel along these paths. Using PCR it is possible to maintain a known separation among the paths, which reduces the interference between the nodes belonging to two separate routes. Our extensive simulations show that while PCR achieves a known separation between the routes, it does so with a small increase in overall hop count. Moreover, we demonstrate that the variances of average separation and hop count are lower for the paths created using PCR compared to existing schemes, indicating a more reliable system. Existing multi-path routing schemes in wireless networks do not perform well in areas with obstacles or low node density. To overcome adverse areas in a network, we integrate PCR with simple robotic routing, which lets a message circumnavigate an obstacle and follow the trajectory to the destination as soon as the obstacle is passed.

In a dense sensor network, sensors are randomly placed at a density high enough that over-sampling of a physical field occurs. Depending upon the application, very often some regions contain more information than the rest. For optimal energy efficiency, the amount of compression and hence the sensing accuracy should vary with the relative significance of different sub-regions. To achieve this goal, we propose a progressive data collection scheme. First, the more significant low-frequency components, which give a crude profile of the signal, are extracted and forwarded to the destination. Then, based on the rough profile, an application may identify some strategic areas and request additional details, i.e. components of higher frequencies, from them until the desired resolution is reached. This process of sensing a phenomenon is like making observations through a telescope: starting with a panoramic view of low resolution, then gradually zooming into a target region to reveal finer details. Noise in data can also be effectively removed during the process by applying digital low-pass filtering locally within sensor clusters. Simulation results based on the temperature distribution of a fire in one of the engineering buildings on the Columbia campus generated by the NIST Fire Dynamics Simulator show that with a sensor density of 1.2 /m2and a SNR of 6 dB, using a simple Gaussian low-pass filter for local compression, an average overall improvement of 4.4 dB can be obtained while collecting only 4.8% of the raw data traffic at the processing center, resulting in a reconstructed field deemed accurate enough for extracting crucial information about a fire.

The area covered by a mobile ad hoc network consists of obstacles that inhibit transmission and areas where communications can take place. Physical structures, such as buildings, that block transmission, or lakes, where forwarding nodes cannot be located, are permanent obstacles. Temporary obstacles are created as mobile nodes enter or leave an area. Our hypothesis is that the spaces between nearby obstacles are bottlenecks that inhibit the flows in the network. We partition the network into areas that are encompassed by obstacles and bottlenecks. All of the nodes in an area are treated as a single super node, and the bottlenecks between areas are the links between the super nodes. As individual nodes move, the flows and paths in the model change more slowly than the paths and flows between the individual nodes. We apply flow control algorithms to the model and perform admission control within a super node based on the flows that are assigned by the flow control algorithm. We apply the model to the Columbia University campus, and use max-min, fair bottleneck flow control to assign the flows. Our hypothesis is verified for this example.

Position-based routing protocols in ad hoc networks combine a forwarding strategy with a recovery algorithm. The former fails when there are void regions or physical obstacles that prevent transmission. Then, the recovery algorithm is used to detour the obstacles. To explore the obstacles and find a path around them, the earlier recovery approaches construct a planar graph to avoid routing loops. Distributed algorithms that find planar graphs require accurate knowledge on the location of nodes. The number of nodes on a recovery path increases as the node density increases. Our novel recovery technique operates on a grid model of a network. Obstacles are approximated by adjacent grid elements. We adopt the right-hand rule, which is common in robotics, to follow the perimeter of the discretized obstacle. We do not construct a planar graph. The grid structure reduces the positional accuracy required for nodes, and the recovery path length is independent of the node density.

This paper proposes a new measure for network performance evaluation called topology lifetime. The measure provides insight into which one of a set of topologies is likely to last the longest before more capacity must be installed. The lifetime measure is not single valued, but considers growth as a function of a set of demand shifts (perturbation). One network may be better able to support a uniform growth in the traffic, while another may support more growth when unexpected shifts in the load occur. The ability of a network to support unexpected changes in load is becoming more important because of: 1) current practices for installing fiber optics cables; 2) recent advances in dense wavelength division multiplexing; and 3) the increasing popularity of the Internet. The lifetime measure is applied to several topologies; a dual ring, a chordal ring, a Manhattan Street network and an hierarchical network. We also apply the measure to a realistic US IP Backbone network. In this paper, our objective is to show how to apply the measure to different networks, and to explain certain implications for comparisons between networks. We expect this measure to be useful both in the construction of new networks and in selecting between new links that may be added to an existing network.

Our objective is to analyze and minimize the amount of energy needed to transmit packets in a multihop wireless network, such as a sensor network or an ad hoc network. The total energy consumed to transmit a packet from a source to a destination is a function of the number of hops along the path and the energy needed to successfully transmit a packet in one hop. Given a path, the number of hops needed depends on the transmission range. The energy consumed for a successful transmission in a hop depends on not only the transmission range but also the medium access strategy. In this paper, we generalize the analysis of the energy consumption on packet transmission in multihop wireless networks. The analysis is applicable to a range of multiaccess schemes from TDM to random access schemes. The results show that typically, there is a transmission range that results in the minimum energy. However, a smaller transmission range does not always lead to less energy consumed by packet transmission. The optimum energy consumption is the result of balancing several factors, including: 1) the ratio of an overhead packet length to a data packet length, where overhead packets refer to the control packets used to reserve the media or the data packets involved in collisions; 2) the number of transmissions of the overhead packets; 3) the number of hops along a path; and 4) the transmission range.

Active routing permits individual customers, network managers, or network owners to control the paths that their data takes through the network. The objective is to allow routing mechanisms that provide quality of service (QoS), mobility, etc., to be quickly deployed, without waiting for standards, and to allow different routing mechanisms, that provide similar services, to compete. The current work on label switching (MPLS) can also be used to give high level customers, such as virtual private networks (VPNs), more control over their paths. We show how active routing can extend the capabilities of MPLS. We address several implementation issues, including pricing and distributed sandboxes. Pricing or policing must be used to limit the resources that customers acquire, in order to encourage them to use network resources economically. Sandboxes must be used to limit the resources that the participants acquire, in order to limit the harm that they can inflict on other participants. Active routing creates a free market system where network providers compete to sell their resources and implementers compete to sell their active routing programs. We establish a framework to quantitatively compare networks and service providers. As an example, we route Internet protocol (IP) telephony over combinations of circuit and packet networks.

We are moving toward an international, 24-hour, distributed, electronic stock exchange. The exchange will use the global Internet, or internet technology. This system is a natural application of multicast because there are a large number of receivers that should receive the same information simultaneously. The data requirements for the stock exchange are discussed. The current multicast protocols lack the reliability, fairness, and scalability needed in this application. We describe a distributed architecture and a timed reliable multicast protocol, TRMP, that has the appropriate characteristics. We consider three applications: (1) A unified stock ticker of the transactions that are being conducted on the various physical and electronic exchanges. Our objective is to deliver the same combined ticker reliability and simultaneously to all receivers, anywhere in the world. (2) A unified sequence of buy and sell offers that are delivered to a single exchange or a collection of exchanges. Our objective is to give all traders the same fair access to an exchange independent of their relative distances to the exchange or delay and loss characteristics of the international network. (3) A distributed, electronic trading floor that can replace the current exchanges. This application has the fairness attributes of the first two applications and uses TRMP to conduct irrefutable, distributed trades.

This paper proposes a new measure for network performance evaluation called topology lifetime. The measure provides insight into which one of a set of topologies is likely to last the longest before more capacity must be installed. The lifetime measure is not single valued, but considers growth as a function of a set of demand shifts. The lifetime measure is applied to several topologies: a dual ring, a chordal ring, a Manhattan Street network and an hierarchical network.

We have proposed earlier watermarking text documents by slightly shifting certain text lines. Such a text line represents a noisy channel, and marking represents the transmission of a signal through this channel. The power of the signal represents the size of the shift and must be small for the marks to be imperceptible. We formulate the channel capacity under a constraint or individual signal power. We show that to achieve the capacity, the shifts should be normally distributed, have maximum power, and adjacent shifts should be negatively correlated.

Each copy of a text document can be made different in a nearly invisible way by repositioning or modifying the appearance of different elements of text, i.e., lines, words, or characters. A unique copy can be registered with its recipient, so that subsequent unauthorized copies that are retrieved can be traced back to the original owner. In this paper we describe and compare several mechanisms for marking documents and several other mechanisms for decoding the marks after documents have been subjected to common types of distortion. The marks are intended to protect documents of limited value that are owned by individuals who would rather possess a legal than an illegal copy if they can be distinguished. We describe attacks that remove the marks and countermeasures to those attacks. An architecture is described for distributing a large number of copies without burdening the publisher with creating and transmitting the unique documents. The architecture also allows the publisher to determine the identity of a recipient who has illegally redistributed the document, without compromising the privacy of individuals who are not operating illegally. Two experimental systems are described. One was used to distribute an issue of the IEEE Journal on Selected Areas in Communications, and the second was used to mark copies of company private memoranda.

Movable slot TDM (MSTDM) is a variant of the Ethernet protocol that provides quality of service guarantees for voice. The protocol has been applied to LANs and CATV networks. However cellular networks are different. (1) Each cell has a base station: when mobile units communicate through the base station, frequency reuse increases and collisions are detected. (2) The objective is to connect mobile units to the communication infrastructure: communications between units is only used to share the channel. (3) The base station broadcasts packets from the communications infrastructure to the mobile units: this channel can also provide timing and control. Rapid contention resolution techniques make it unnecessary to transmit voice during silent intervals. Taking advantage of the cellular characteristics and TASI increases the number of voice connections by a factor of 8.

A text document typically consists of a collection of regular structures such as words, lines, and paragraphs, a slight movement of which seems less perceptible than, say, dithering of the document image. We exploit this property to watermark formatted text documents by shifting slightly certain lines and words in order to discourage illicit distribution. We analyze two methods for reliable document identification in the presence of severe distortions introduced by photocopying, facsimile transmission, and other processing. The correlation method uses document profiles directly for detection. To eliminate the effect of certain distortions, the centroid method bases its decision on the distances between the centroids of adjacent profile blocks. We present the maximum likelihood detectors for both methods and evaluate their relative performance. Our analysis indicates that line-shift generally has a smaller error than word-shift detection, and that the correlation detector outperforms the centroid detector provided certain distortions can be accurately compensated for before detection is attempted. These results have been applied to implement a marking and identification system and preliminary experimental results have been very promising.

A way to discourage illicit reproduction of copyrighted or sensitive documents is to watermark each copy before distribution. A unique mark is embedded in the text whose recipient is registered. The mark can be extracted from a possibly noisy illicit copy, identifying the registered recipient. Most image marking techniques are vulnerable to binarization attack and, hence, not suitable for text marking. We propose a different approach where a text document is marked by shifting certain text lines slightly up or down or words slightly left or right from their original positions. The shifting pattern constitutes the mark and is different on different copies. In this paper we develop and evaluate a method to detect such minute shifts. We describe a marking and identification prototype that implements the proposed method. We present preliminary experimental results which suggest that centroid detection performs remarkably well on line shifts even in the presence of severe distortions introduced by printing, photocopying, scanning, and facsimile transmission.

The Internet is being used to carry voice conversations. Sometimes the quality is acceptable, and at other times the voice is unintelligible. In this paper, we describe the results of a set of measurements on intrastate, cross country, and international Internet connections. The measurements are used to determine the relationships between the delay that is inserted to compensate for the variation in network delay, the strategy that is used to restore lost packets, and the "quality" of the voice connection. The "quality" of a connection is defined as the fraction of the time that a channel is free of distortion for intervals that are long enough to transmit active speech segments. We also examine the sensitivity of our quality measure to modifying the required length of the distortion free intervals. We have found that, with the proper combination of packet restoration, receiver delay and patience on the part of users, connections can be established that provide reasonably good voice connections, even during the busy period on the worse channel. Patience is required because a certain fraction of the connections are very bad. In which case the best strategy is to try again later. It is noted that the quality of international connections is not as good as cross country connections, which is not as good as the quality of intrastate connections. This indicates that Internet voice is better suited for local bypass than its current role as a replacement for long distance connections.

Summary form only given. Electronic documents are more easily copied and redistributed than paper documents. This is a major impediment to electronic publishing. Illegal redistribution can be discouraged by placing unique marks in each copy and registering the copy with the original recipient. If an illegal copy is discovered, the original recipient can be identified. We describe several invisible techniques for encoding information in text documents. We also describe a marking system, for electronic publishing, that is scalable to large numbers of users.

In this paper we describe a protocol that improves the quality of multicast video or audio transmissions by recovering lost packets. The protocol is applied to a corporate intranet, and measurements indicate that significant improvements in audio/video quality are achieved. A unique characteristic of this protocol is that it can be used on current MBone sessions without changing the operation of the source or receivers. The improvement in quality can be restricted to a subset of the receivers, so that a service provider, that does not necessarily generate content, can use the protocol to improve reception for its own customers. A second unique characteristic is that only a small fraction of the receivers that obtain the benefits of the protocol are active participants. As a result the problems associated with large multicast groups, such as the number of control messages, is reduced. Finally, because of the differences between data and voice or video communications, many of the network parameters that vary between or during connections are changed rather than predicted. This is a much simpler operation.

In earlier work we have formulated a collusion problem that determines whether it is possible for a set of colluders to collectively discover a target set of information, starting from their initial knowledge, and have presented a complete solution for a special case of the problem. In this paper we present an algorithm that solves the general case. Given a collusion problem the algorithm determines whether it has a solution, and if it does, computes one. A solution to the collusion problem is a method with which the colluders can uncover the hidden information. Communications protocols that employ cryptographic techniques are increasingly used to protect privacy as well as to communicate. A cryptographic protocol defines a process by which information is transferred among some users while hidden from others. The algorithm presented can be used to determine whether a subset of protocol users can discover, during or after the protocol's execution, the information that is designed to be hidden from them.

The Internet is being used to distribute video programming to small, widely distributed audiences over a multicast backbone (Mbone). This type of service can be used to deliver specialized programming to the general population. As the service becomes more widely used, conserving the required transmission facilities becomes more important. We define the problem of designing multicast networks for video distribution. The problem is related to the Steiner tree problem, with an interesting twist. The line costs are not constant. An heuristic is developed to solve the problem and the new heuristic is related to and compared with heuristics, developed for the Steiner tree problem and algorithms to design minimum depth and minimum spanning trees.

Communications networks are traditionally used to bring information together. They can also be used to keep information apart in order to protect personal privacy. A cryptographic protocol specifies a process by which some information is transferred among some users and hidden from others. We show how to implement anonymous credit cards using simple cryptographic protocols. We pose, and solve, a collusion problem which determines whether it is possible for a subset of users to discover information that is designed to be hidden from them during or after execution of the anonymous credit card protocol.

Modern computer networks make it possible to distribute documents quickly and economically by electronic means rather than by conventional paper means. However, the widespread adoption of electronic distribution of copyrighted material is currently impeded by the ease of unauthorized copying and dissemination. In this paper we propose techniques that discourage unauthorized distribution by embedding each document with a unique codeword. Our encoding techniques are indiscernible by readers, yet enable us to identify the sanctioned recipient of a document by examination of a recovered document. We propose three coding methods, describe one in detail, and present experimental results showing that our identification techniques are highly reliable, even after documents have been photocopied.>

This paper describes a communications networking technique for funds transfer which combines the privacy of cash transactions with the security, record-keeping and charging mechanisms of credit cards. The scheme uses a communications network and cryptographic protocols to separate information. The company that extends credit to the individual and collects the bill does not have access to the specific purchases, and the shop that sells the merchandise is convinced that it will be paid without learning the individual's identity.

A major impediment to the widespread adoption of services for electronic distribution of copyrighted material is the ease with which illicit copies can be made and disseminated. In this paper, we describe feature coding techniques to mark document images with codes that are indiscernible by readers but can be decoded by document feature analysis techniques. These codes can be used to trace the source of errant documents. We propose three coding methods: line-shift coding, word-shift coding, and character coding. We describe how the coding features are found, inserted, and decoded. Finally, we show preliminary experimental results indicating robustness of the line-shift coding method where decoding can be performed even from images of up to ten generations of photocopying.

Modern computer networks make it possible to distribute documents quickly and economically by electronic means rather than by conventional paper means. However, the widespread adoption of electronic distribution of copyrighted material is currently impeded by the ease of illicit copying and dissemination. The authors propose techniques that discourage illicit distribution by embedding each document with a unique codeword. The encoding techniques are indiscernible by readers, yet enable one to identify the sanctioned recipient of a document by examination of a recovered document. The authors propose three coding methods, describe one in detail, and present experimental results showing that their identification techniques are highly reliable, even after documents have been photocopied.>

The performance and reliability comparison of two networks that have been proposed for use as high-speed metropolitan area networks (MANs)-the Manhattan street network (MS Net) and the distributed-queue dual-bus (DQDB) network-are compared. Both networks use slotted access protocols and have the same number of links, transmitters, and receivers per node. It is shown that the MS Net provides a much higher network throughput for a variety of traffic patterns, both uniform and nonuniform. It is shown that the MS Net can survive more failures than the DQDB network and that failures cause a lesser performance degradation in the MS Net. It is also shown that higher-level mechanisms are required in the DQDB network to recover from link failures, whereas deflection routing is sufficient in the MS Net.>

Dispersity routing is defined. It is combined with random access and fast circuit set-up and tear-down to put bursty data on an asynchronous transfer mode (ATM) network. This approach makes the storage in the network independent of the message length. This approach is evaluated assuming that the propagation delay may be more than the message transmission time. It is shown that the efficiency improves as the number of channels on each path increases, and that dispersity routing makes it reasonable to use the strategy on networks with a small number of channels per path. Dispersity routing requires networks with multiple paths between many of the nodes. This characteristic is also required for many adaptive routing strategies. A class of networks is proposed in which the fraction of nodes with multiple paths, and the number of multiple paths between nodes, can be controlled. These networks provide a platform for evaluating multiple path strategies.>

The authors make a performance and reliability comparison of two networks that have been proposed for use as high-speed metropolitan area networks (MANs)-the Manhattan street network (MSNet) and the distributed queue dual bus (DQDB) network. Both networks use slotted access protocols and have the same number of links, transmitters, and receivers per node. The DQDB network has been adopted by the IEEE 802.6 committee as the metropolitan area network (MAN) standard. The authors demonstrate the relative superiority of the MSNet over the DQDB network. They show that the MSNet provides a much higher network throughput for a variety of traffic patterns-uniform and nonuniform. They also look at the reliability of both networks and show that the MSNet can survive more failures than the DQDB network and that failures cause a lesser performance degradation in the MSNet. It is also shown that higher-level mechanisms are required in the DQDB network to recover from link failures whereas deflection routing is sufficient in the MSNet.>

It is explained why long distributed queue dual bus (DQDB) networks without bandwidth balancing can have fairness problems when several nodes are performing large file transfers. The problems arise because the network control information is subject to propagation delays that are much longer than the transmission time of a data segment. Bandwidth balancing is then presented as a simple solution. By constraining each node to take only a certain fraction of the transmission opportunities offered to it by the basic DQDB protocol, bandwidth balancing gradually achieves a fair allocation of bandwidth among simultaneous file transfers. Two ways to extend this procedure effectively to multipriority traffic are proposed.>

Bandwidth balancing is a procedure that gradually achieves a fair allocation of bandwidth among simultaneous file transfers on a distributed-queue dual-bus (DQDB) network. Bandwidth balancing was originally designed for traffic of a single priority level. Three ways are demonstrated to extend this procedure to multi-priority traffic.>

The fairness problems suffered by distributed-queue-dual-bus (DQDB) networks that span metropolitan areas are examined in detail. The problems arise because the network control information is subject to propagation delays that are much longer than the transmission time of a data segment. A rate control procedure is proposed that requires only a minor modification of the current DQDB protocol. In order to guarantee that a node acquires only 90% of the available slots, every time it inserts nine data segments into its local queue it inserts one extra request slot into its transmission queue. This lets an extra idle slot go by that was not requested by any downstream node.>

The routing and flow control techniques developed for wide-area, local-area, and metropolitan-area networks are surveyed. A classification that shows the characteristics that are desirable for high-speed wide-area networks is developed. On the basis of the classification, techniques that should and should not be considered for future high-speed networks are identified. In particular, an attempt is made to determine the effect of increasing transmission rates on the routing and flow control algorithms that are used in packet-switched networks.>

The Manhattan Street Network (MS-Net) and Shuffle-Exchange Network (SX-Net) are two-connected networks with significantly different topologies. Fixed-size packets are transmitted between nodes in these networks. The nodes are synchronized so that all of the packets that are received by a node within a slot transmission time arrive at a switching point simultaneously. Instead of storing large numbers of packets at intermediate nodes, a deflection strategy similar to hot-potato routing is used. There are characteristics of the MS-Net that make it well suited for deflection routing. With no buffer, 55-70% of the throughput with an infinite number of buffers has been obtained; with a single buffer per node, the throughput increases to 80-90%. With uniform load the throughput does not decrease significantly as the network utilization increases. Therefore, additional flow control mechanisms are not required to achieve the highest network throughput. The SX-Net does not have the above characteristics of the MS-Net. However, deflection routing still provides a significant portion of the available throughput. In the SX-Net, more buffers are required than in the MS-Net, and a flow control mechanism must be used to achieve the greatest throughput.>

A simple technique is described for operating slotted loop or mesh networks with independent, and slightly different clocks at every node. The technique eliminates the need to designate one node as the master clock in these networks. The technique can also be used to transfer synchronous samples from a voice source. If the slots correspond to time-division multiplexed (TDM) frames of voice samples, the TDM frames from all of the input lines arrive at a switching point in the node simultaneously, and the samples can be interchanged by standard telephone switching techniques.>

We present two protocols for information exchange between multiple identical senders and a single receiver. At each instant, every sender sends one bit, and the bits from all of senders are or-ed together into one bit before being received by the receiver. If a sender has a data message to send, it sends the message bits one by one; otherwise it sends zero bits. Clearly, if the sending of two messages by two senders overlap, then the resulting “collision” can result in a corrupted message, i.e., one that was not sent by either sender. The function of the protocol is to deliver those and only those messages that are not corrupted by collision. (In other words, the receiver acts as a discriminating seine that catches and delivers only uncorrupted messages; hence the title.) The two protocols presented here are based on Manchester codes and general balanced codes, respectively.

Twelve random-access strategies that do not constrain the distance or transmission rate of a network, and can use the capabilities of fiber-optic components, are described and compared. The twelve strategies consist of three protocols, each of which can use two timing arrangements and two network-access devices. The three protocols are the standard ALOHA protocol, LCSMA, and LCSMA/CD. The last two protocols operate on linear-unidirectional networks and use local information at the transmitter to increase the throughput of the system. The networks considered have a common point that all transmitted signals pass through before being received. This makes two timing arrangements possible; a slotted system or an unslotted system. The taps on the network can be either passive or active.>

The Manhattan Street Network is a regular, two-connected network, designed for packet communications in a local or metropolitan area. It operates as a slotted system, similar to conventional loop networks. Unlike loop networks, routing decisions must be made at every node in this network. In this paper, several distributed routing rules are investigated that take advantage of the regular structure of the network. In an operational network, irregularities occur in the structure because of the addressing mechanisms, adding single nodes, and failures. A fractional addressing scheme is described that makes it possible to add new rows or columns to the network without changing the addresses of existing nodes. A technique is described for adding one node at a time to the network, while changing only two existing links. Finally, two procedures are described that allow the network to adapt to node or link failures. The effect that irregularities have on routing mechanisms designed for a regular structure is investigated.

In the literature on diagnosable multiprocessor systems, regular testing structures which isolate up to t1 faulty processors to within a set of t1 processors have been studied. These structures are called D(n, t0, X) systems and are said to be t1/t1-diagnosable. In this correspondence, the problem of designing regular testing structures which isolate the largest number of faulty processors is shown to be equivalent to determining full-difference triangles. These triangles have been used to design error-correcting convolutional codes and transmission systems without third-order intermodulation interference, and have been studied extensively. Recognizing this relationship allows results from these areas to be applied directly to the design of diagnosable systems. A list of the best-known systems is given.

A technique for transmitting voice and data on a conventional subsplit CATV network is described. The technique uses a variation on the carrier sense multiple access/collision detection protocol used in local area networks. A variation on this protocol, called movable slot TDM allows periodic voice Sources to share this network without distorting the voice signal. A scheme for sharing frequency spectrum and space is outlined that removes the distance and transmission rate constraints associated with such networks. A transmission strategy is described which allows these protocols to be used on a subsplit CATV system. The system is thus a candidate for local/metropolitan area networks Which support digital voice and data services along with analog (mostly one-way) video.

A reliable broadcast protocol for an unreliable broadcast network is described.The protocol operates between the application programs and the broadcast network.It isolates the application programs from the unreliable characteristics of the communication network.The protocol guarantees that all of the broadcast messages are received at all of the operational receivers in a broadcast group.In addition, the sequence of messages is the same at each of the receivers and a total ordering exists among all broadcast messages.This unique message sequencing can be used to simplify distributed database systems and distributed processing algorithms.The protocol can operate with as few as one acknowledgment message per broadcast message, instead of one acknowledgment from each receiver per broadcast message.The protocol continues to operate when sites in the broadcast group fail.

Two techniques for separating a composite NTSC signal into luminance and chrominance components are developed and compared. In the first technique, fixed filters, which are based upon minimum mean square error estimators, are designed. It is shown that, when samples from successive lines are used, these filters have a comb structure in the region of the frequency spectrum in which the luminance and chrominance signals overlap. In the second technique, the composite signal is filtered by several filters, and the outputs of the filters are selected dependent upon the local characteristics of the picture. Both recursive and nonrecursive filters are considered, the criterion for selecting between filters is investigated and the effect of delayed decisions is determined. The various filters are compared using subjective criterion and a number of quantitative criterion. The relationships between the quantitative and qualitative criterion are stated.

In this paper a relationship between difference triangles and third order intermodulation interference is demonstrated, and two applications of this relationship are developed. In the first application, the relationship allows us to find intermodulation-free channel assignments where such arrangements are possible. The second application concerns cases where this is not possible. In the second application, arguments connected with difference triangles are used to bound, from below, the total intermodulation interference and the maximum interference falling on any assigned channel for the optimum channel assignment. To determine the tightness of this bound, a random coding type argument is used to bound the total intermoduiation for the optimum channel assignment from above, and an upper bound on the maximum intermod is established using previously performed computer experiments.