A novel distributed algorithm for constructing random overlay networks that are composed of d Hamilton cycles is presented. The protocol is completely decentralized as no globally-known server is required. The constructed topologies are expanders with O(log/sub d/ n) diameter with high probability. Our construction is highly scalable because both the processing and the space requirements at each node grow logarithmically with the network size. A new node can join the network in O(log/sub d/ n) time with O(d log/sub d/ n) messages. A node can leave in O(1) time with O(d) messages. The protocol is robust against an offline adversary selecting the sequence of the join and leave operations. We also discuss a layered construction of the random expander networks in which any node can be located in O(log n) time. The random expander networks have applications in community discovery, distributed lookup service, and dynamic connectivity.

We analyze and compare the error performance of a dual-rate direct-sequence code-division multiple-access (DS-CDMA) system using multicode (MCD) and variable-spreading gain (VSG) transmission in the uplink. Specifically, we present two sets of results. First, we consider an ideal additive white Gaussian noise channel. We show that the bit-error rate (BER) of VSG users is slightly lower than that of MCD users if the number of low-rate interferers is smaller than a specific threshold. Otherwise, they exhibit similar error performance. Second, we look at multipath fading channels. We show that with diversity RAKE reception, the VSG user suffers from a larger interference power than the MCD user if the channel delay spread is small. The reverse is true for a large delay spread. However, a larger interference power in this case does not necessarily lead to higher error probability. Essentially, our results for both cases show that: 1) in addition to the signal-to-interference ratio (SIR), the difference in error performance between the two systems strongly depends on the distributions of multiple-access and multipath interference; 2) for practical cellular communications, performances for both systems are expected to be similar most of the time.

We study the benefit of reconfigurability for wavelength division multiplexed (WDM) ring networks with dynamic single-hubbed traffic. We show that the ability to reconfigure wavelength add-drop multiplexers helps to reduce the number of expensive line terminating equipment (LTEs) by a factor of W, where W is the number of wavelengths in the network. In addition, we show that for a general class of traffic, optical networks using reconfigurable wavelength add-drop multiplexers guarantee to be almost as bandwidth efficient as full wavelength add-drop networks, that is, opaque networks. For such traffic, we introduce several fast algorithms that achieve or approximate the optimal performance guarantees. The comparison between reconfigurable networks and opaque networks is quantified using a performance metric called capacity ratio, which captures the relative throughput performance of a reconfigurable network compared to the opaque network.

We establish some lower bounds on the speedup required to achieve throughput for some classes of switching algorithms in a input-queued switch with virtual output queues (VOQs). We use a weak notion of throughput, which will only strengthen the results, since an algorithm that cannot achieve weak throughput cannot achieve stronger notions of throughput. We focus on priority switching algorithms, i.e., algorithms that assign priorities to VOQs and forward packets of high priority first. We show a lower bound on the speedup for two fairly general classes of priority switching algorithms: input priority switching algorithms and output priority switching algorithms. An input priority scheme prioritizes the VOQs based on the state of the input queues, while an output priority scheme prioritizes the VOQs based on their output ports. We first show that, for output priority switching algorithms, a speedup S/spl ges/2 is required to achieve weak throughput. From this, we deduce that both maximal and maximum size matching switching algorithms do not imply weak throughput unless S/spl ges/2. The bound of S/spl ges/2 is tight in all cases above, based on a result in Dai et al. Finally, we show that a speedup S/spl ges/3/2 is required for the class of input priority switching algorithms to achieve weak throughput.

We address the problem of scheduling unsplittable flows using a number of switches in parallel. This has applications in optical switching and eliminates the need for re-sequencing in traditional packet switching. The use of parallel switches is becoming increasingly popular since it provides a way of building a high-speed switch while overcoming the speedup requirement imposed on the switch. Unlike packet switching however, we will assume that flows cannot be split across switches. This constraint adds a new dimension to the problem: various questions such as obtaining the best schedule, i.e. the schedule with the maximum throughput possible, become NP hard. Our problem is a special case of the general unsplittable flow problem, where in a directed capacitated graph containing a number of commodities with demands, the goal is to obtain a flow that does not violate capacity and in which all demands are satisfied and every commodity flows along a single path. In this paper, we are not going to address the general problem. Rather, we will study the special case of scheduling unsplittable flows using parallel switches, and present some simple approximation algorithms to various aspects of the problem with no speedup. We also define a speedup version of the problem and discuss under what speedup we can fully schedule an admissible set of flows.

We introduce a dual-mode multiuser detector that dynamically switches its detection mode between matched-filter and decorrelator operations based on the channel characteristics. This detector significantly reduces the overall computational requirement while maintaining similar performance as that of the decorrelator. The switching mechanism of our dual-mode detector is designed by exploiting the performance-complexity tradeoff between the decorrelator and the matched-filter. Extensions of this idea to other types of multiuser detectors are also proposed.

We propose an efficient parallel switching architecture that requires no speedup and guarantees bounded delay. Our architecture consists of k input-output-queued switches with first-in-first-out queues, operating at the line speed in parallel under the control of a single scheduler, with k being independent of the number N of inputs and outputs. Arriving traffic is demultiplexed (spread) over the k identical switches, switched to the correct output, and multiplexed (combined) before departing from the parallel switch. We show that by using an appropriate demultiplexing strategy at the inputs and by applying the same matching at each of the k parallel switches during each cell slot, our scheme guarantees a way for cells of a flow to be read in order from the output queues of the switches, thus, eliminating the need for cell resequencing. Further, by allowing the scheduler to examine the state of only the first of the k parallel switches, our scheme also reduces considerably the amount of state information required by the scheduler. The switching algorithms that we develop are based on existing practical switching algorithms for input-queued switches, and have an additional communication complexity that is optimal up to a constant factor.

A Bluetooth ad hoc network can be formed by interconnecting piconets into scatternets. The constraints and properties of Bluetooth scatternets present special challenges in forming an ad hoc network efficiently. We present and analyse a new randomized distributed algorithm for Bluetooth scatternet formation. We prove that our algorithm achieves O(log n) time complexity and O(n) message complexity. We show that: (1) in the scatternet formed by our algorithm, any device is a member of at most two piconets; (2) the number of piconets is close to being minimal.

Link-state protocols such as open shortest path first (OSPF) are the dominant routing technology in IP networks. Previous work has addressed the ability of OSPF to make smart routing decisions based on network configuration and bandwidth demand. Traffic engineered networks that make use of this enhanced routing will experience loops in the case of link failure. This paper presents an algorithm that solves the loop problem in the event of a link failure or a severely congested link. Upon a link failure, the algorithm will build a restoration path that will reroute traffic as well as notify neighboring routers of the link failure. The informed routers will make intelligent forwarding decisions based on past and present arc weights. All routers will be informed of the failure, building a restoration network and leading to the new network topology and arc weights.

A Bluetooth ad hoc network can be formed by interconnecting piconets into scatternets. The constraints and properties of Bluetooth scatternets present special challegnes in forming an ad hoc network efficiently. In this paper, we evaluate the performance of a new randomized distributed Bluetooth scatternet formation protocol. Our simulations validate the theoretical results that our scatternet formation protocol runs in O(log n) time and sends O(n) messages. The scatternets formed have the following properties: 1) any device is a member of at most two piconets, and 2) the number of piconets is close to be optimal. These properties can avoid overloading of any single device and lead to low interference between piconets. In addition, the simulations show that the scatternets formed have O(log n) diameter. As an essential part of the scatternet formation protocol, we study the problem of device discovery: establishing multiple connecitons with many masters and slaves in parallel. We investigate the collision rate and time requirement of the inquiry and page processes. Deducing from the simulation results of scatternet formation and device discovery, we can verify that the total number of packets sent is O(n) and demonstrate that the maximum number of packets sent by any single device is O(log n). At last, we give estimates of the total time requirement of the protocol and suggest further improvements

We analyze and compare the error performances of two multirate transmission schemes in W-CDMA: multicode (MCD) and variable spreading gain (VSG). First, we show that in an AWGN channel, the VSG data user performs better than the MCD user if the number of in-cell voice users are low and the background noise is weak. However, as the noise power or the number of voice subscribers increases, the performances of the two schemes become similar. We then show that in a multipath fading channel, the two schemes achieve very similar error performances as long as their receivers are able to track all resolvable signal paths. However, when the receiver can only track multipath components within the current symbol interval, the VSG user yields a much worse error probability than the MCD user. This is because the VSG data user has a much shorter symbol interval. Simulation results are illustrated to support the analysis.

This paper presents a new protocol for statistical multiplexing of bursty data traffic in the forward (base-to-mobile) link of a wireless wideband code division multiple access (W-CDMA) system using orthogonal variable spreading factor (OVSF) codes. At the heart of the protocol is an efficient scheduling algorithm that dynamically assigns an OVSF code to a mobile user on a timeslot-by-timeslot basis and allows many users with bursty traffic to share a limited set of OVSF codes. An important feature of our protocol is that it can provide a heterogeneous data rate guarantee to each mobile user and fully utilize the system capacity. Moreover, the unreserved bandwidth of the network can be shared fairly among competing mobile users.

A key functionality in today's widely used interior gateway routing protocols such as OSPF and IS-IS involves the computation of a shortest path tree (SPT). In many existing commercial routers, the computation of an SPT is done from scratch following changes in the link states of the network. As there may coexist multiple SPTs in a network with a set of given link states, such recomputation of an entire SPT not only is inefficient but also causes frequent unnecessary changes in the topology of an existing SPT and creates routing instability. This paper presents a new dynamic SPT algorithm that makes use of the structure of the previously computed SPT. Our algorithm is derived by recasting the SPT problem into an optimization problem in a dual linear programming framework, which can also be interpreted using a ball-and-string model. In this model, the increase (or decrease) of an edge weight in the tree corresponds to the lengthening (or shortening) of a string. By stretching the strings until each node is attached to a tight string, the resulting topology of the model defines an (or multiple) SPT(s). By emulating the dynamics of the ball-and-string model, we can derive an efficient algorithm that propagates changes in distances to all affected nodes in a natural order and in a most economical way. Compared with existing results, our algorithm has the best-known performance in terms of computational complexity as well as minimum changes made to the topology of an SPT. Rigorous proofs for correctness of our algorithm and simulation results illustrating its complexity are also presented.

Future broadband networks may provide very high bandwidth on demand for certain applications e.g. downloading of a gigabyte file to a high-performance workstation. Motivated by such applications, we study the performance of TCP under the scenario where there is long network latency and rapidly changing bandwidth. We show that existing TCP cannot utilize the bandwidth effectively under such network dynamics. We propose a modification of TCP that would separate the flow control from the loss recovery mechanisms, allowing the efficient use of the available bandwidth over a network that has a high bandwidth-delay product and in which the bandwidth can vary by orders of magnitude over a short period of time. We present simulation results demonstrating the significant performance gain of our new approach.

In a single-cell DS-CDMA system, linear MMSE detectors has been shown to significantly outperform conventional detectors in terms of spectral efficiency. Furthermore, simulation shows that the spectral efficiency of asynchronous CDMA systems using MMSE detection and random spreading codes can reach four times that of orthogonal CDMA. In the case of universal frequency reuse, however, this is not necessarily true because of the presence of strong inter-cell interference (ICI). This paper analyzes the reason for the superior performance of MMSE detection in single-cell asynchronous CDMA systems and investigates the potential for performance enhancement using MMSE detection in multi-cell environment with sectorization and a higher frequency reuse factor. Our results indicate that, with sectorization and reduced frequency reuse efficiency, using the MMSE detector can still significantly improve the overall system throughput surpassing that of CDMA systems using conventional detection with universal frequency reuse.

This paper presents new research results of the DARPA-funded ONRAMP consortium on the next generation Internet to study efficient WDM-based network architectures and protocols for supporting broadband services in regional access networks. In particular, we present new efficient scheduling algorithms for bandwidth sharing in WDM distribution networks. The current ONRAMP distribution network architecture has a tree topology with each leaf node (e.g., a router or workstation) sharing access to the root node of the tree, which corresponds to an access node in the feeder network. Our model allows a leaf node to use one or more fixed-tuned or tunable transceivers; moreover, different leaf nodes can support different subsets of wavelengths depending on their expected traffic volumes. An important goal of ONRAMP is to support bandwidth-on-demand services with QoS guarantee over WDM. As a first step toward this goal, we have developed several fast scheduling algorithms for flexible bandwidth reservations in a WDM distribution network. The scheduling algorithms can provably guarantee any bandwidth reservations pattern that does not overbook network resources, i.e., bandwidth reservation (throughput) up to 100% network capacity can be supported.

We present new theoretical results on the performance limits of online routing and wavelength assignment (RWA) algorithms in a single-hub wavelength division multiplexing (WDM) ring network architecture. A routing and wavelength assignment (RWA) algorithm is said to be online if at each point in time, the algorithm assigns a route and a color to the current connection request based only on past information, without knowledge of future requests. We study the throughput performance of deterministic online RWA algorithms in terms of competitive ratio, i.e., the maximum ratio of the throughput of an optimal off-line algorithm to that of an online algorithm over any satisfiable sequence of requests. We show that the competitive ratio for the min-hop algorithm is exactly 2. When there are sufficient wavelengths, smaller competitive ratio W/(W+1-N) can be achieved by the greedy-complete algorithm for infinite-duration requests, and by the pair-complete algorithm for uniform-duration requests, where W is the number of wavelengths and N is the number of nodes. In the general case where requests can have arbitrary durations, we prove that a natural deterministic online algorithm can achieve a competitive ratio of 1+2g, where g>1 is the ratio of the longest duration of any request to the shortest duration of any request. These results exhibit the performance tradeoffs among the number of nodes, the number of wavelengths, and the range of request durations.

This paper presents an optimal dynamic code assignment (DCA) scheme using orthogonal variable-spreading-factor (OVSF) codes. The objective of dynamic code assignment is to enhance statistical multiplexing and spectral efficiency of W-CDMA systems supporting variable user data rates. Our scheme is optimal in the sense that it minimizes the number of OVSF codes that must be reassigned to support a new call. By admitting calls that would normally be blocked without code reassignments, the spectral efficiency of the system is also maximized. Simulation results are presented to show the performance gain of dynamic code assignment compared to a static assignment scheme in terms of call blocking rate and spectral efficiency. We also discuss various signaling techniques of implementing our proposed DCA scheme in third-generation wideband CDMA systems.

The open shortest path first (OSPF) and IS-IS routing protocols widely used in today's Internet compute a shortest path tree (SPT) from each router to other routers in a routing area. Many existing commercial routers recompute an SPT from scratch following changes in the link states of the network. Such recomputation of an entire SPT is inefficient and may consume a considerable amount of CPU time. Moreover, as there may coexist multiple SPTs in a network with a set of given link states, recomputation from scratch causes frequent unnecessary changes in the topology of an existing SPT and may lead to routing instability. We present new dynamic SPT algorithms that make use of the structure of the previously computed SPT. Besides efficiency, our algorithm design objective is to achieve routing stability by making minimum changes to the topology of an existing SPT (while maintaining shortest path property) when some link states in the network have changed. We establish an algorithmic framework that allows us to characterize a variety of dynamic SPT algorithms including dynamic versions of the well-known Dijkstra, Bellman-Ford, D'Esopo-Pape algorithms, and to establish proofs of correctness for these algorithms in a unified way. The theoretical asymptotic complexity of our new dynamic algorithms matches the best known results in the literature.

Link-state protocols such as OSPF are the dominant routing technology in today's Internet. Despite their many advantages, these protocols require the flooding of new information across the entire routing area after changes in any link state (e.g., link failures). As the routing area grows or the frequency of link-state changes increases, the overhead (in terms of bandwidth and processing cost) of flooding becomes prohibitive. Furthermore, such flooding over a large area will cause temporary inconsistency of link states among many routers, potentially creating many transient routing loops that can last for a long time. This limits the scalability of the routing protocols to large routing areas. To overcome such problems, we present in this paper a novel algorithm that minimizes the amount of information distributed by link-state routing protocols. Upon a link failure, our algorithm will distribute the link-state changes to the minimum number of routers that are needed to ensure loop-free routing. Moreover, implementing our algorithm requires only a simple extension to any existing link-state protocol.

A general framework and architecture called differentiated services (Diffserv) has been proposed by the IETF to support service differentiation among different IP flows traversing a network. The key idea in Diffserv is to achieve scalability through handling aggregates of traffic instead of individual flows. More specifically, at the ingress edge router, each flow is shaped and classified into one of few service classes. Based on these service classes, packets are then forwarded and discarded (if necessary) with different priorities in network core routers/switches. As many network service providers today employ ATM in their backbone networks, there is tremendous interest in supporting IP Diffserv in an ATM environment. This paper presents a study on using ATM ABR service to support IP Diffserv. The idea is to use the flow control mechanism in ABR to eliminate the need for discarding packets inside the ATM network, while service differentiation among different IP flows can simply be supported by proper packet scheduling and/or discarding mechanisms at the ingress edge routers/switches. Scalability is achieved by setting up an ABR virtual circuit (VC) between each pair of ingress and egress routers rather than on a per-flow basis. A simulation study of this Diffserv framework over ATM using the Opnet simulation tool is presented to validate our idea.

This paper presents a distributed scheduling algorithm for the support of QoS in multiaccess networks. Unlike most contention-based multiaccess protocols which offer no QoS guarantee and suffer the problems of fairness and low throughput at high load, our algorithm provides fairness and bandwidth reservation in an integrated services environment and at the same time achieves high throughput. Moreover, while most reservation-based multiaccess protocols require a centralized scheduler and a separate channel for arbitration, our algorithm is truly distributed in the sense that network nodes coordinate their transmissions only via headers in the packets. We derive theoretical bounds illustrating how our distributed algorithm approximates the optimal centralized algorithm. Simulation results are also presented to justify our claims.

A key functionality in today's widely used interior gateway routing protocols such as OSPF and IS-IS involves the computation of a shortest path tree (SPT). In many existing commercial routers, the computation of an SPT is done from scratch following changes in the link states of the network. As there may coexist multiple SPTs in a network with a set of given link states, such recomputation of an entire SPT not only is inefficient but also causes frequent unnecessary changes in the topology of an existing SPT and creates routing instability. This paper presents a new dynamic SPT algorithm that makes use of the structure of the previously computed SPT. This algorithm is derived by recasting the SPT problem into an optimization problem in a dual linear programming framework, which can also be interpreted using a ball-and-string model. In this model, the increase (or decrease) of an edge weight in the tree corresponds to the lengthening (or shortening) of a string. By stretching the strings until each node is attached to a tight string, the resulting topology of the model defines an (or multiple) SPT(s). By emulating the dynamics of the ball-and-string model, we can derive an efficient algorithm that propagates changes in distances to all affected nodes in a natural order and in a most economical way. Compared with existing results, our algorithm has the best-known performance in terms of computational complexity as well as minimum changes made to the topology of an SPT. Rigorous proofs for correctness of our algorithm and simulation results illustrating its complexity are also presented.

A source coding algorithm minimizing the battery power needed for RF transmission is presented. Digital RF transmitters in portable devices consume energy only when high bits are sent and virtually no energy is consumed when low bits are sent. Therefore, energy consumption can be minimized by devising a source coding algorithm that minimizes the occurrence of high bits in transmitting information. In this paper, we first formulate the minimum energy source coding problem for RF transmission. We then derive the optimal memoryless coding algorithm from the source statistics. Finally, we improve the memoryless coding performance via a novel technique that utilizes a simple memory mechanism. Overall, we take a first step towards a novel energy saving wireless communication protocol.

We present several fast, practical linear-complexity scheduling algorithms that enable provision of various quality-of-service (QoS) guarantees in an input-queued switch with no speedup. Specifically, our algorithms provide per-virtual-circuit transmission rate and cell delay guarantees using a credit-based bandwidth reservation scheme. Our algorithms also provide approximate max-min fair sharing of unreserved switch capacity. The novelties of our algorithms derive from judicious choices of edge weights in a bipartite matching problem. The edge weights are certain functions of the amount and waiting times of queued cells and credits received by a virtual circuit. By using a linear-complexity variation of the well-known stable-marriage matching algorithm, we present theoretical proofs and demonstrate by simulations that the edge weights are bounded. This implies various QoS guarantees or contracts about bandwidth allocations and cell delays. Network management can then provide these contracts to the clients. We present several different algorithms of varied complexity and performance (as measured by the usefulness of each algorithm's contract). While most of this paper is devoted to the study of "soft" guarantees, a few "hard" guarantees can also be proved rigorously for some of our algorithms. As can be expected, the provable guarantees are weaker than the observed performance bounds in simulations. Although our algorithms are designed for switches with no speedup, we also derive upper bounds on the minimal buffer requirement in the output queues necessary to prevent buffer overflow when our algorithms are used in switches with speedup larger than one.

We present several fast, practical linear-complexity scheduling algorithms that enable provision of various quality-of-service (QoS) guarantees in an input-queued switch with no speedup. Specifically, our algorithms provide per-virtual-circuit transmission rate and cell delay guarantees using a credit-based bandwidth reservation scheme. The novelties of our algorithms derive from judicious choices of edge weights in a bipartite matching problem. The edge weights are certain functions of the amount and waiting times of queued cells and credits received by a virtual circuit. By using a linear-complexity variation of the well-known stable marriage matching algorithm, we demonstrate by simulations that the edge weights are bounded. This implies various QoS guarantees or contracts about rate and cell delays. Network management can then provide these contracts to the clients. We present several different algorithms of differing complexity and power (as measured by the usefulness of each algorithm's contract). While most of this paper is devoted to the "soft" guarantees demonstrated by simulations, we also list a few "hard" theoretical guarantees for some of our algorithms (proved in our full report). As can be expected, the provable guarantees are weaker than the observed performance bounds in simulations.

We study a typical network environment where TCP traffic is generated from a source connected to a LAN (e.g. Ethernet) aggregated through an IP edge router to an access network (e.g. ATM, frame relay). Congestion at the edge router occurs when the bandwidth available in the access network cannot support the aggregated traffic generated from the LAN. This paper presents a novel approach to reduce router congestion and improve TCP performance. In particular, we propose new techniques that regulate TCP acknowledgments at the edge router without changing existing TCP implementations at the end systems. Our techniques minimize buffer requirement at network edges while maximizing the throughput. Analytical and simulation results are presented in the's paper to substantiate our claims.

Most existing wavelength-division multiplexed (WDM) networks employ circuit switching, typically with one session having exclusive use of one entire wavelength. Consequently, they are not suitable for data applications involving bursty traffic patterns. The All-Optical Network (AON) Consortium has developed an all-optical LAN/MAN test bed which provides time-slotted WDM service. We explore extensions of this service to achieve fine-grained statistical multiplexing with different virtual circuits time sharing the wavelengths in a fair manner. We develop a very fast, best effort time-slotted WDM network protocol with very good fairness and throughput characteristics. As an additional design feature, our protocol supports the assignment of guaranteed bandwidths (GBW) to selected sessions. This feature acts as a first step toward supporting integrated services at the optical layer in WDM networks.

Efficient support for scalable multipoint-to-multipoint (mpt-mpt) communication in ATM has recently become a hot topic of discussion at the ATM Forum. Previously, we presented a new class of efficient switch algorithms for point-to-multipoint (pt-mpt) ABR service that deliver high performance in terms of fairness and link utilization and are significantly simpler to implement than other proposed protocols. However, the more challenging problem of providing bidirectional mpt-mpt ABR service has not been addressed before. While a number of key issues have been resolved in unidirectional pt-mpt ABR service, no satisfactory solution for multipoint-point (mpt-pt) ABR service is known. In this paper, we propose new efficient mpt-pt ABR mechanisms that can interoperate with existing standards for ABR service and provide a truly transparent and scalable solution to multipoint communication in ATM. We present simulation results to illustrate that our proposed ABR schemes provide high link utilization and fair bandwidth allocation in a mpt-pt connection for heterogeneous sources with different data rates.

The efficient support of data traffic over ATM networks requires congestion control, whose objectives include maximizing throughput, minimizing switch buffer requirement, and attaining a fair bandwidth allocation. With available bit rate (ABR) service in ATM, congestion control is achieved by requiring data sources to adjust their rates based on the feedback from the network. The difficulties in providing effective ABR service are caused by the burstiness of data traffic, the dynamic nature of the available bandwidth, as well as the feedback delay. Using a new design methodology described in our previous paper, we present here a congestion control algorithm that is provably stable and is optimal in the sense that it has the shortest possible transient response time. Moreover, our algorithm achieves fair bandwidth allocation among contending connections and maximizes network throughput. It also delivers good performance for switches that use a FIFO queuing discipline. Essentially, the algorithm implicitly measures the round-trip delay using resource enhancement cells, and establishes an observer (in the control theoretic sense) to control the flow of data in the network. Rigorous analysis as well as simulation results are presented to substantiate our claims.

It is known that TCP throughput can degrade significantly over UBR service in a congested ATM network, and the early packet discard (EPD) technique has been proposed to improve the performance. However, recent studies show that EPD cannot ensure fairness among competing VCs in a congested network, but the degree of fairness can be improved using various forms of fair buffer allocation techniques. Based upon the work by H.Y. Tzeng and K.Y. Siu (1996), we propose an improved scheme that utilizes only a single shared FIFO queue for all VCs and admits simple implementation for high speed ATM networks. Our scheme achieves nearly perfect fairness of throughput among multiple TCP connections, comparable to the expensive per-VC queuing technique. Analytical and simulation results are presented to show the validity of this new scheme and significant improvement in performance as compared with existing fair buffer allocation techniques for TCP over ATM.

In the ATM Forum activities, considerable efforts have focused on the congestion control of point-to-point available bit rate (ABR) service. We present a novel approach that extends existing point-to-point (unicast) congestion control protocols to a point-to-multipoint (multicast) environment. In particular, we establish a unified framework to derive a multicast congestion control protocol for an ABR service from a given rate-based unicast protocol. We generalize a known necessary and sufficient condition on the max-min fairness of unicast rate allocation for a multicast service. Using this condition, we show that the resulting multicast protocol derived using our framework preserves the fairness characteristics of the underlying unicast protocol. The practical significance of our approach is illustrated by extending a standard congestion control mechanism for an ABR service to a multicast environment. The performance of the resulting multicast protocol is examined using benchmark network configurations suggested by the traffic management subworking group at the ATM Forum, and simulation results are presented to substantiate our claims.

We present a simulation study of the TCP performance in ATM networks with available bit rate (ABR) service and unspecified bit rate (UBR) service with early packet discard (EPD) schemes. We focus our study in a LAN environment using some benchmark network configurations proposed in the ATM Forum. Our simulation results show the following: (1) with UBR service and EPD schemes, TCP suffers significant performance degradation in terms of fairness and requires relatively large switch buffer even with a small number of active virtual connections over a LAN configuration, and (2) for the same set of network configurations and with ABR service using explicit rate feedback schemes, TCP achieves a good performance in terms of fairness and link utilization, and requires a relatively small switch buffer.

Prefix computation is a basic operation at the core of many important applications, e.g., some of the Grand Challenge problems, circuit design, digital signal processing, graph optimizations, and computational geometry. In this paper, we present new and strict time-optimal parallel schedules for prefix computation with resource constraints under the concurrent-read-exclusive-write (CREW) parallel random access machine (PRAM) model. For prefix of N elements on p processors (p independent of N) when N>p(p+1)/2, we derive Harmonic Schedules that achieve the strict optimal time (steps), [2(N-1)/(p+1)]. We also derive Pipelined Schedules that have better program-space efficiency than the Harmonic Schedule, yet only require a small constant number of steps more than the optimal time achieved by the Harmonic Schedule, Both the Harmonic Schedules and the Pipelined Schedules are simple and easy to implement. For prefix of N elements on p processors (p independent of N) where N/spl les/p(p+1)/2, the Harmonic Schedules are not time-optimal. For these cases, we establish an optimization method for determining key parameters of time-optimal schedules, based on connections between the structure of parallel prefix and Pascal's triangle. Using the derived parameters, we devise an algorithm to construct such schedules. For a restricted class of values of N and p, we prove that the constructed schedules are strictly time-optimal. We also give strong empirical evidence that our algorithm constructs strict time optimal schedules for all cases where N/spl les/p(p+1)/2.

Many large-scale scientific and engineering computations, e.g., some of the Grand Challenge problems, spend a major portion of execution time in their core loops computing band linear recurrences (BLRs). Conventional compiler parallelization techniques cannot generate scalable parallel code for this type of computation because they respect loop-carried dependences (LCDs) in programs, and there is a limited amount of parallelism in a BLR with respect to LCDs. For many applications, using library routines to replace the core BLR requires the separation of BLR from its dependent computation, which usually incurs significant overhead. In this paper, we present a new scalable algorithm called the Regular Schedule, for parallel evaluation of BLRs. We describe our implementation of the Regular Schedule and discuss how to obtain maximum memory throughput in implementing the schedule on vector supercomputers. We also illustrate our approach, based on our Regular Schedule, to parallelizing programs containing BLR and other kinds of code. Significant improvements in CPU performance for a range of programs containing BLR implemented using the Regular Schedule in C over the same programs implemented using highly optimized coded-in-assembly BLAS routines [11] are demonstrated on Convex C240. Our approach can be used both at the user level in parallel programming code containing BLRs, and in compiler parallelization of such programs combined with recurrence recognition techniques for vector supercomputers.

To establish secure network communications, a common practice requires that users authenticate one another and establish a temporary session key based on their passwords. Since users often use passwords that are easy to remember, attackers can correctly guess the passwords simply by searching through a relatively small space of "weak" passwords. In this paper, we present a new set of efficient protocols that can establish secure communications while protecting passwords from any feasible guessing and replay attacks. Our protocols avoid the use of timestamps altogether and minimize the use of nonces (random numbers). We examine some common attacks to existing protocols, and show how our protocols can be secure against such attacks. Our protocols apply to both secure peer-to-peer and multicast communications.

We formalize the notions of latency, effective throughput, fairness, and transient period in a complexity theoretic framework. This new framework allows us to prove the first known complexity results and tight bounds on the latency in a client/server distributed computing system. Using this formal complexity model, we study a general class of fair and maximally efficient control algorithms that maximizes the effective throughput and minimizes the transient period. We show that any fair and maximally efficient algorithm will result in at least cNlogN+O(N) latency, where N is the number of greedy clients in the network and the constant c is a parameter of the chosen algorithm. This lower bound is also shown to be tight.

This paper presents a fundamental study on the message and time complexity of reliable broadcast/multicast protocols in point-to-point networks subject to omission failures. We assume a weakly synchronous model in which there is a known upper bound on the delay in delivering a message from one process to another. A faulty process may omit sending or receiving messages; this characterizes a common faulty behavior in networking applications. We focus our study on the number of messages and the maximum amount of time required of any fault-tolerant protocol in failure-free executions. We present protocols that, in an n-process network subject to at most t faulty processes, guarantee the delivery of a message from any process to all other nonfaulty processes. In particular, when no failure occurs in the network, our protocols require (n+t-1) messages and at most (n-1+upper bound [log/sub 2/(t+1)])/spl middot//spl delta/ units of time, where /spl delta/ is the maximum time required to deliver a message from a process to another. Moreover, we show that our protocols are optimal with respect to message and time complexity. The new insights provided by the lower bound proofs yield a graph-theoretic characterization of all message and time optimal reliable broadcast/multicast protocols in failure-free executions. We further discuss the implications of our results on the support of multicast services in high-speed switching networks such as ATM.>

An essential feature in any fault tolerant design of distributed systems is a mechanism by which a process can reliably broadcast information to other processes in the presence of failures. The paper studies the message complexity of fault tolerant broadcast protocols in weakly synchronous and totally asynchronous distributed systems with point to point communication links, where the system failures are caused by the processes but the communication links are completely reliable. We focus on the number of messages required of any fault tolerant protocol in failure free executions. Our motivation is that one should incur the cost of handling failures only when they actually occur. We present protocols that, in an n-process system subject to at most t crash failures where 1/spl les/t>

Learning and convergence properties of linear threshold elements or perceptrons are well understood for the case where the input vectors (or the training sets) to the perceptron are linearly separable. Little is known, however, about the behavior of the perceptron learning algorithm when the training sets are linearly nonseparable. We present the first known results on the structure of linearly nonseparable training sets and on the behavior of perceptrons when the set of input vectors is linearly nonseparable. More precisely, we show that using the well known perceptron learning algorithm, a linear threshold element can learn the input vectors that are provably learnable, and identify those vectors that cannot be learned without committing errors. We also show how a linear threshold element can be used to learn large linearly separable subsets of any given nonseparable training set. In order to develop our results, we first establish formal characterizations of linearly nonseparable training sets and define learnable structures for such patterns. We also prove computational complexity results for the related learning problems. Next, based on such characterizations, we show that a perceptron does the best one can expect for linearly nonseparable sets of input vectors and learns as much as is theoretically possible.

Let $\widehat{LT}_d $ denote the class of functions that can be computed by depth-d threshold circuits with polynomial size and polynomially bounded integer weights. Using the results in [M. Goldman, J. Håstad, and A. Razborov, in Proc. 7th Annual Conference on Structure in Complexity Theory], [M. Goldman and M. Karpinski, Constructing depth$d+1$majority circuits that simulate depth d threshold circuits, unpublished] we show that multiple sum is in $\widehat{LT}_2 $, and multiplication and division are in $\widehat{LT}_3 $. Moreover, it follows from the lower-bound results in [A. Hajnal et al., IEEE Sympos. Foundations of Comput. Sci., 28 (1987), pp. 99–110], [T. Hofmeister and P. Pudlák, Forschungbericht Nr. 477 Uni Dortmund, 1992] that these threshold circuits are optimal in circuit depth. The authors also indicate that these techniques can be applied to construct polynomial-size depth-3 threshold circuits for powering and depth-4 threshold circuits for multiple product.

Using communication complexity concepts and techniques, we derive linear (/spl Omega/(n)) and almost-linear (/spl Omega/(n/logn)) lower bounds on the size of circuits implementing certain functions. Our approach utilizes only basic features of the gates used, hence the bounds hold for general families of gates of which the symmetric and threshold gates are special cases. Each of the bounds derived is shown to be tight for some functions and some applications to threshold circuit complexity are indicated. The results generalize and in some cases strengthen recent results.>

Artificial neural networks are comprised of an interconnected collection of certain nonlinear devices; examples of commonly used devices include linear threshold elements, sigmoidal elements, and radial-basis elements. We employ results from harmonic analysis and the theory of rational approximation to obtain almost tight lower bounds on the size (i.e., number of elements) of neural networks. The class of neural networks to which our techniques can be applied is quite general it includes any feedforward network in which each element can be piecewise approximated by a low degree rational function. For example, we prove that any depth-d+1 network of sigmoidal units or linear threshold elements computing the parity function of n variables must have R(dn/sup 1//d-/spl epsiv/) size, for any fixed /spl epsiv/>0. In addition, we prove that this lower bound is almost tight by showing that the parity function can be computed with O(dn/sup 1/d/) sigmoidal units or linear threshold elements in a depth-(d+1) network. These almost tight bounds are the first known complexity results on the size of neural networks with depth more than two. Our lower bound techniques yield a unified approach to the complexity analysis of various models of neural networks with feedforward structures. Moreover, our results indicate that the in the context of computing highly oscillating symmetric Boolean functions, networks of continuous-output units such as sigmoidal elements do not offer significant reduction in size compared with networks of linear threshold elements of binary outputs.>

We present a new technique for the high-level synthesis of scalable^1 MCM-based architectures implementing infinite-impulse response(IIR) filters. Our technique is based on the regular schedules, a class of parallel schedules for computing mth-order IIR filters. The simplicity of the regular schedules facilitates characterization of their inter-processor communications, which is generally difficult to express for parallel algorithms. The characterization of inter-processor communications of the regular schedules enables us to generate instruction-level behavior of the design that can be easily mapped onto MCM-based architectures. We illustrate this mapping of the regular schedules onto an MCM-based architecture by designing a special-purpose processor for the fifth-order elliptic wave filter. Our design yields a scalable performance measured in the filter's sample rate, which is not known to have been achieved by previously published designs. This work differs significantly from "traditional" high-level synthesis techniques in its emphasis on synthesizing scalable, high-performance multichip designs.

An artificial neural network (ANN) is commonly modeled by a threshold circuit, a network of interconnected processing units called linear threshold gates. It is shown that ANNs can be much more powerful than traditional logic circuits, assuming that each threshold gate can be built with a cost that is comparable to that of AND/OR logic gates. In particular, the main results indicate that powering and division can be computed by polynomial-size ANNs of depth 4, and multiple product can be computed by polynomial-size ANNs of depth 5. Moreover, using the techniques developed, a previous result can be improved by showing that the sorting of n n-bit numbers can be carried out in a depth-3 polynomial-size ANN. Furthermore, it is shown that the sorting network is optimal in depth.>

Linear threshold elements (LTEs) are the basic processing elements in artificial neural networks. An LTE computes a function that is a sign of a weighted sum of the input variables. The weights are arbitrary integers; actually, they can be very big integers—exponential in the number of input variables. However, in practice, it is very difficult to implement big weights. So the natural question that may be asked is whether there is an efficient way to simulate a network of LTEs with big weights by a network of LTEs with small weights. The following results are proved: (1) every LTE with big weights can be simulated by a depth-3, polynomial size network of LTEs with small weights; and (2) every depth-d, polynomial size network of LTEs with big weights can be simulated by a depth-$( 2d + 1 )$, polynomial size network of LTEs with small weights. To prove these results, tools from harmonic analysis of Boolean functions are used. The technique is quite general; it provides insights to some other problems. For example, the best known results on the depth of a network of threshold elements that computes the COMPARISON, ADDITION, and PRODUCT of two n-bits numbers, and the MAXIMUM and the SORTING of nn-bit numbers are improved.

The tradeoffs between the depth (i.e., the time for parallel computation) and the size (i.e., the number of threshold gates) in neural networks are studied. The authors focus the study on the neural computations of symmetric Boolean functions and some arithmetic functions. It is shown that a significant reduction in the size is possible for symmetric functions and some arithmetic functions, at the expense of a small constant increase in depth. In the process, several neural networks which have the minimum size among all the known constructions have been developed. Results on implementing symmetric functions can be used to improve results about arbitrary Boolean functions. In particular, it is shown that any Boolean function can be computed in a depth-3 neural network with O(2/sup n/ /sup 2/) threshold gates; it is also proven that at least Omega (2/sup n/ /sup 3/) threshold gates are required.>