Part I [1] introduced three performance metrics based on “power”, namely individual power P i , sum of individual powers P sum , and average power P avg , and analyzed their optimization in multi-flow queueing systems under two extreme scheduling disciplines, specifically the least discriminatory First-Come, First-Served (FCFS) and the most discriminatory Head-of-the-Line (HOL) preemptive resume priority discipline. Building on that foundation, this follow-up study provides the designer greater flexibility to range the flow priority discrimination continuously from FCFS to HOL by introducing families of queueing disciplines to accommodate the designers’ mixed workloads with diverse SLO in their systems. We examine two such continuous families—the delay-dependent system and our newly created beta-priority system —each spanning the full spectrum from minimal to maximal flow priority discrimination. These systems provide a continuous control mechanism, enabling power metric optimization beyond the constraints of fixed-discipline analysis. These two are examples of the many possible families that exist, and each has its unique trajectory from one extreme discipline to the other. We focus on selecting the flow utilization to optimize individual power P i and sum of individual powers P sum , respectively (we leave out average power in this study since its optimal value is invariant across the queueing disciplines, as shown in [1] ). We begin with the two-flow case to compare both full spectrum systems. While both systems exhibit similar patterns in individual power optimization, they differ in their outcomes for sum of individual powers optimization. For an arbitrary number of flows n , we focus on the beta-priority system due to its analytical tractability. We derive closed-form solutions for the optimal utilization of lowest-priority flows, and use numerical methods to compute equilibrium outcomes. In particular, we observe an increase in both system utilization and the maximal total powers as the level of discrimination increases in optimizing sum of individual powers, highlighting the efficiency gains achievable through prioritization in multi-flow systems.

With the rapid expansion of networks and increasing traffic, optimizing network performance has become increasingly important, especially in balancing two competing objectives: increasing throughput and decreasing delay. This paper adopts the Power metric to address this tradeoff, extending the analysis to a general multi-flow model and examining the influence of different queueing disciplines. We introduce three forms of power metrics– individual power , sum of powers , and average power –to capture performance in a multi-flow context. Individual power optimizes each flow’s end-to-end performance, while sum of powers and average power provide a system-wide perspective. These three power metrics are analyzed and optimized under an M/M/1 queueing systems setting, considering two extreme flow discrimination priority disciplines–First-Come, First-Served (FCFS) and Head-of-Line (HOL)–to capture their discriminatory effect on response time while maintaining power optimization. This work is a first step in examining the tradeoff of throughput and delay in queueing systems from various perspectives and across different priority group disciplines. The optimization results aim to provide theoretical insights and guidance for system designers in performance optimization.

Accompanied by improving accessibility of data and storage and the invention of the blockchain economy, advantages of the peer-to-peer network in privacy and efficiency over server-client systems have become more significant recently. One of the most popular applications of peer-to-peer networks is file transferring, where each peer stores a partial segment of a file and the requester can aggregate each piece into a single file when downloading it. To optimize the performance of file transmission, one goal is to increase the searching speed for the file location over the network. In this paper, we analyze the server-mediated peer-to-peer networks, which is an uncommon architecture mentioned in previous works but can potentially improve the search speed, and minimize the average number of hops during flooding search.

Due to a poor understanding of the interactions among transmitters, wireless networks using carrier sense multiple access with collision avoidance (CSMA/CA) have been commonly stigmatized as unpredictable in nature. Even elementary questions regarding the throughput limitations of these networks cannot be answered in general. In this paper, we investigate the behavior of wireless CSMA/CA networks to understand how the transmissions of a particular node affect the medium access, and ultimately the throughput, of other nodes in the network. We introduce a theory which accurately models the behavior of these networks and show that, contrary to popular belief, their performance is predictable and can be described by a system of equations. Using the proposed theory, we provide the analytical expressions necessary to fully characterize the capacity region of any wireless CSMA/CA network. We show that this region is nonconvex in general and agnostic to the probability distributions of all network parameters, depending only on their expected values. Our theory is also shown to extend naturally to time division multiple access (TDMA) networks and to predict how the network responds to infeasible input rates.

The great French writer, historian and philosopher Voltaire once asked, "Is there anyone so wise as to learn by the experience of others?" In celebration of the 20th MobiCom conference, join us for a thought provoking discussion between pioneers of our field on the lessons they have learned over their illustrious career paths that accelerated the pace of technology adoption and enabled world-wide societal impact. Learn from our heroes as they share with us gems of wisdom on how to choose a great problem, what to avoid and how to be successful as you build your own remarkable careers.

A number of interesting problems that I have addressed over the years which yielded surprisingly simple results will be presented. Many of these had intuitively pleasing interpretations or especially simple proofs and/or insights.

Due to a poor understanding of the interactions among transmitters, wireless multihop networks have commonly been stigmatized as unpredictable in nature. Even elementary questions regarding the throughput limitations of these networks cannot be answered in general. In this paper we investigate the behavior of wireless multihop networks using carrier sense multiple access with collision avoidance (CSMA/CA). Our goal is to understand how the transmissions of a particular node affect the medium access, and ultimately the throughput, of other nodes in the network. We introduce a theory which accurately models the behavior of these networks and show that, contrary to popular belief, their performance is easily predictable and can be described by a system of equations. Using the proposed theory, we provide the analytical expressions necessary to fully characterize the capacity region of any wireless CSMA/CA multihop network. We show that this region is nonconvex in general and entirely agnostic to the probability distributions of all network parameters, depending only on their expected values.

Edge network operators have limited tools to control activities on their networks. This paper examines network dissuasion, a new approach to edge network control, based on controlling the fundamental parameters of the network, such as loss rate, delay, and jitter, with the intention of making particular uses of a network intolerable, while providing acceptable services for approved network uses. We investigate using this technique to prevent use of Voice Over IP (VoIP), while allowing other services. We designed network controls to achieve this goal and performed experiments using both measurements and subjective testing with human beings. We report on the degree of success and discuss the general promise of network dissuasion.

In this paper we present a new routing paradigm for wireless multihop networks. In plasma routing, each packet is delivered over the best available path to one of the gateways. The choice of the path and gateway for each packet is not made beforehand by the source node, but rather on-the-fly by the mesh routers as the packet traverses the network. We propose a distributed routing algorithm to jointly optimize the transmission rate and the set of gateways each node should use. A load balancing technique is also proposed to disperse the network traffic among multiple gateways. We validate our proposal with simulations and show that plasma routing outperforms the state-of-the-art multirate anypath routing paradigm, with a 98% throughput gain and a 2.2x delay decrease. Finally, we also show that the load can be evenly distributed among gateways with a similar routing cost, resulting in a further 63% throughput gain.

In this paper, we present a new routing paradigm that generalizes opportunistic routing for wireless multihop networks. In multirate anypath routing, each node uses both a set of next-hops and a selected transmission rate to reach a destination. Using this rate, a packet is broadcast to the nodes in the set, and one of them forwards the packet on to the destination. To date, there is no theory capable of jointly optimizing both the set of next-hops and the transmission rate used by each node. We solve this by introducing two polynomial-time routing algorithms and provide the proof of their optimality. The proposed algorithms have roughly the same running time as regular shortest-path algorithms and are therefore suitable for deployment in routing protocols. We conducted measurements in an 802.11b testbed network, and our trace-driven analysis shows that multirate anypath routing is on average 80% better than 11-Mbps anypath routing, with a factor of 6.4 improvement in the best case. If the rate is fixed at 1 Mbps instead, performance improves by a factor of 5.4 on average.

In this paper, we present a new routing paradigm that generalizes opportunistic routing in wireless mesh networks. In multirate anypath routing, each node uses both a set of next hops and a selected transmission rate to reach a destination. Using this rate, a packet is broadcast to the nodes in the set and one of them forwards the packet on to the destination. To date, there is no theory capable of jointly optimizing both the set of next hops and the transmission rate used by each node. We bridge this gap by introducing a polynomial-time algorithm to this problem and provide the proof of its optimality. The proposed algorithm runs in the same running time as regular shortest-path algorithms and is therefore suitable for deployment in link-state routing protocols. We conducted experiments in a 802.11b testbed network, and our results show that multirate anypath routing performs on average 80% and up to 6.4 times better than anypath routing with a fixed rate of 11 Mbps. If the rate is fixed at 1 Mbps instead, performance improves by up to one order of magnitude.

Ensuring spontaneous ad hoc interoperation in decentralized ubiquitous computing environments is challenging, because of heterogeneous resources and divergent policies. Centralized cross-domain service access agreements can be made with a priori knowledge of the interacting entities' policies, but privacy concerns make this approach impractical. Environments should not be too rigid nor too open in their interactions, and should support varying contexts and scenarios. We describe the modeling, design, and implementation of a general purpose negotiation protocol for cross-domain service access agreements between entities that do not share trust agreements or application level protocols. This protocol resolves the constraints and needs of the participants, described in the form of declarative logical policies, in a fully distributed manner, avoiding the need for a third party. We describe how we tested the system and show how negotiation performance was evaluated against an optimal case computed by a centralized oracle.

Peer-to-peer live video streaming over the Internet has been measured to support over 100,000 concurrent users. While the approach is very attractive, established providers need to understand the performance of such a system before deploying such a system as a frequent loss in quality would jeopardize their reputation. This paper provides an analytical model to inform the design of BitTorrent-based live video streaming solutions. While, given the current broadband deployment scenario, a pure peer- to-peer solution can support only limited streaming rates, our analysis shows that the addition of a well-designed peer-to-peer solution to existing server-based streaming infrastructures can allow substantially higher streaming rates. The efficiency of a BitTorrent-like peer-to-peer solution depends on the peer group size and the number of fragments available for sharing at any given time. Our analysis suggests that the efficiency of the peer- to-peer solution is not sensitive to the size of the peer group for groups larger than 15-20 users. A similar threshold exists for the number of fragments available for sharing at any given time. For live streaming scenarios, this threshold dictates that the fragment size be substantially smaller than the default fragment size in BitTorrent to ensure that the stream latency is small.

This paper derives the optimal search time and the optimal search cost that can be achieved in unstructured peer-to-peer networks when the demand pattern exhibits clustering (i.e. file popularities vary across the set of nodes in the network). Clustering in file popularity patterns is evident from measurements on deployed peer-to-peer file sharing networks. In this paper, we provide mechanisms for modeling clustering in file popularity distributions and the consequent non-uniform distribution of file replicas. We derive relations that show the effect of the number of replicas of a file on the search time and on the search cost for a search for that file for the clustered demands case in such networks for both random walk and flooding search mechanisms. The derived relations are used to obtain the optimal search performance for the case of flooding search mechanisms. The potential performance benefit that clustering in demand patterns affords is captured by our results. Interestingly, the performance gains are shown to be independent of whether the search network topology reflects the clustering in file popularity (the optimal file replica distribution to obtain these performance gains, however, does depend on the search network topology).

One of the most important sources of revenue for big Internet-based companies are advertisements. With vehicular networks poised to become part of the Internet, this new "edge" of the Internet represents the next frontier that advertising companies will be striving to reach. In this paper we investigate the design parameters for AdTorrent, an integrated system for search, ranking and content delivery in Digital Billboards, a scalable "push" model architecture for targeted dissemination of ad content in a car network. We present an analytical model to estimate the performance impact of key design parameters such as the scope of the query flooding on the query hit ratio in epidemic query dissemination.

The increasing ease of self-expression and web-publishing has resulted in an explosion in the amount of content being generated in the current Internet. Besides traditional sources such as news portals, regular users are documenting their lives and thoughts and other people are subscribing, downloading and viewing this content. A lot of content therefore is being generated at the edge and consumed by the edge. Traditional client-server architectures are known to be in-effective in handling large correlated bursts of user demands. However, with RSS becoming more popular, such flash crowd scenarios will be more and more commonplace due to automated polling and downloads. Peer to peer protocols such as BitTorrent provide an attractive solution for such scenarios. BitTorrent networks are scalable, and the expected download time is independent of the arrival rate of peers (content consumers). However, the base performance of a BitTorrent network may not be fast enough from a user or content publisher's perspective. Besides, BitTorrent gives poor results towards the end of a flash crowd when most of the large burst of arrivals have downloaded and left, and there are not too many peers online. We motivate the need for a content delivery network with well connected servers to participate in BitTorrent delivery streams. The servers are dynamically added and function as cushions to handle increase in demand as well as bolster a delivery stream when there is a paucity of users.

This paper derives the optimal search time and the optimal search cost that can be achieved in unstructured peer-to-peer networks when the demand pattern exhibits clustering (i.e. file popularities vary from region to region in the network). Previous work in this area had assumed a uniform distribution of file replicas throughout the network with an implicit or explicit assumption of uniform file popularity distribution whereas in reality, there is clear evidence of clustering in file popularity patterns. The potential performance benefit that the clustering in demand patterns affords is captured by our results. Interestingly, the performance gains are shown to be independent of whether the search network topology reflects the clustering in file popularity. We also provide the relation between the query-processing load and the number of replicas of each file for the clustered demands case showing that flooding searches may have lower query-processing load than random walk searches in the clustered demands case.

We recently showed for peer-to-peer networks, that having the number of replicas of each object proportional to the request rate for these objects has many per-node advantages. In this paper we complement those results to show that this distribution has network-wide advantages as well. Given these benefits of proportional replication, the next issue is achieving proportional replication in a decentralized manner. We show that local storage management algorithms like LRU automatically achieve near-proportional replication and that the system performance with the replica distribution achieved by LRU is very close to optimal. We also show that the LRU responds to a change in user access pattern quickly (the number of accesses taken to reach the new steady-state replica distribution with LRU is close to the minimum possible with any cache replacement algorithm). Analytical models are provided for computing the steady-state network-wide replica distribution and the transient period for LRU.

Search time as a function of the number of replicas of a queried object provides a key component to understanding system behavior in peer-to-peer networks. The analytical work in this area so far has assumed a uniform distribution of file replicas throughout the network with an implicit or explicit assumption of uniform file popularity distribution whereas, in reality, there is clear evidence of clustering in file popularity patterns. In this paper, we provide mechanisms for modeling clustering in file popularity distributions and the consequent non-uniform distribution of file replicas. We provide results for the search time in such networks for both random walk and flooding search mechanisms.

This paper investigates the effect of the number of file replicas on search performance in unstructured peer-to-peer networks. We observe that for a search network with a random graph topology where file replicas are uniformly distributed, the hop distance to a replica of a file is logarithmic in the number of replicas. Using this observation we show that flooding-based search is optimized when the number of replicas is proportional to the file request rates. This replica distribution is also optimal for download time and since flooding has logarithmically better search time than random walk under its optimal replica distribution, we investigate the query-processing load using this distribution.

Sensor networks are distributed networks made up of small sensing devices equipped with processors, memory, and short-range wireless communication. They differ from the conventional computer networks in that they have severe energy constraints, redundant low-rate data, and a plethora of information flows. Many aspects of sensor networks, such as routing, preservation of battery power, adaptive self-configuration, etc., have already been studied in previous papers, e.g., [(W. Heinzelman, J. Kulik, and H Balakrishnan, 1999), (N. Bulusu, D. Estrin, L. Girod, and J. Heidelann, 20001), (D. Estrin, 2001)]. However, to the best knowledge of the authors, the area of sensor network quality of service (QoS) remains largely open. This is a rich area because sensor deaths and sensor replenishments make it difficult to specify the optimum number of sensors (this being the service quality that we address in this paper) that should be sending information at any given time. In this paper we present an amalgamation of QoS feedback and sensor networks. We use the idea of following the base station to communicate QoS information to each of the sensors using a broadcast channel and we use the mathematical paradigm of the Gur Game to dynamically adjust to the optimum number of sensors. The result is a robust sensor network that allows the base station to dynamically adjust the resolution of the QoS it receives from the sensors, depending on varying circumstances.

The rapid growth and increasing pervasiveness of wireless networks raises serious security concerns. Client devices will migrate between numerous diverse wireless environments, bringing with them software vulnerabilities and possibly malicious code. Techniques are needed to protect wireless client devices and the next generation wireless infrastructure. We propose QED, a new security model for wireless networks that enables wireless environments to quarantine devices and then analyze and potentially update or "decontaminate" client nodes. The QED paradigm is presented here, as well as the design of a practical prototype.

Video smoothing is a promising technique for reducing the bandwidth variability of video in order to improve network efficiency. This paper presents a general optimal video smoothing algorithm based on the concept of dynamic programming. The algorithm generates the optimum transmission schedule for different requirements by setting the constraints and the cost function accordingly. It can be used to study the smoothing of both stored video and real time video. In particular, for stored video, we show how the number of rate changes in the smoothed video is affected by the renegotiation cost and buffer size, assuming that the transmission rate is allowed to be lower than the reserved rate. For the real time system, we study the impact of various system parameters, including playout delay, client buffer site, and server buffer size, on the performance of video smoothing.

In this paper, we present an adaptive prefetch scheme for network use, in which we download files that will very likely be requested in the near future, based on the user access history and the network conditions. Our prefetch scheme consists of two parts: a prediction module and a threshold module. In the prediction module, we estimate the probability with which each file will be requested in the near future. In the threshold module, we compute the prefetch threshold for each related server, the idea being that the access probability is compared to the prefetch threshold. An important contribution of this paper is that we derive a formula for the prefetch threshold to determine its value dynamically based on system load, capacity, and the cost of time and system resources to the user. We also show that by prefetching those files whose access probability is greater than or equal to its server's prefetch threshold, a lower average cost can always be achieved. As an example, we present a prediction algorithm for web browsing. Simulations of this prediction algorithm show that, by using access information from the client, we can achieve high successful prediction rates, while using that from the server generally results in more hits.

Previously, we proposed and analyzed a timeout scheme to alleviate network congestion and thus improve the throughput for a wormhole routing network in local area network (LAN) environments. This timeout scheme was proved to be effective, but the optimal timeout value varies with packet size, propagation delay, and other network parameters. To tune the timeout value automatically, two dynamic timeout methods are presented in this paper. The first method, called "immediate timeout or wait" (ITOW), compares the costs for timeout and waiting. Thus, it decides to reject a worm immediately or to allow the worm to wait until the timeout occurs. The second method, called "cost equilibrium point" (CEP), sets the timeout value to the point where the timeout and waiting costs are the same, thereby determining the timeout value automatically. From simulation, the results show that the first method simplifies the choice of the timeout value and the second method performs well if a cost factor for timeout is given properly. Both methods improve the network throughput significantly.

In this paper, we study prefetch techniques in the WWW, in which we predict which files will be needed in the near future and download some of them before they are requested by the user. Our prefetch scheme includes two algorithms: the prediction algorithm and the threshold algorithm. The prediction algorithm estimates the probability with which each file will be requested in the near future. The threshold algorithm computes the prefetch threshold for each server. An important contribution of this paper is a formula we derived to determine the prefetch threshold dynamically based on the system load capacity and the cost of time and system resources to the user. Simulations driven by trace files show that using access information from the client can achieve high successful prediction rates, while using that from the server can result in more hits in general. We have also developed a prefetch program at the client site which assists users in browsing faster and more efficiently.

Multistage interconnection networks (MINs) are very popular in ATM switching since they can achieve high-performance switching and are easy to implement and expand due to their modular design. In this paper we present and describe in detail a high-performance buffered-Banyan switch which encompasses multiple input-queueing as its buffering strategy. We call this switching architecture Dual-Banyan switch. Simulation results are given to demonstrate its throughput, mean waiting time and cell-loss performance considering different switch and buffer sizes. We further compare it to the simple, single-queue buffered Banyan network, assuming, for reasons of fairness, the same total buffer capacity with respect to uniform and non-uniform traffic patterns.

Wormhole routing is a simple, low-cost switching scheme often used for supercomputer interconnections. It also has been applied to high-speed local area networks to support applications demanding high-data-rate communications, such as cluster computing. The drawback of wormhole routing is its low link efficiency caused by worm blocking. To overcome this blocking problem a timeout scheme was investigated by Hu and Kleinrock (see Proceedings of the 4th International Conference on Computer Communications and Networks, p. 584-93, Las Vegas, NV, 1995) using analytical modeling. We present timeout simulation results, showing the effect of packet size, propagation delay, and network size. Furthermore, a simple deflection scheme, which we call host deflection, is introduced and tested. This simple host deflection scheme requires only small modifications to the protocol and very little processing power from the switches, it improves the network throughput significantly.

A simple game provides a framework within which agents can spontaneously self-organize. In this paper, we present this game, and develop basic theory underlying a robust method for distributed coordination based on this game. This method makes use of finite state automata-one associated with each agent-which guide the agents. We give a new, general method of analysis of these systems, which previously had been studied only in limited cases. We also provide a physical example, which should hint at the type of problems resolvable using this method.

In this paper, we propose an analytical model for wormhole routing with the use of a timeout reset mechanism. This model is based on an M/G/1 queueing system with impatient customers and feedback. Some approximations are proposed and verified by simulation. By comparing our analytical results to simulation, we show that the proposed model successfully captures the performance characteristics of wormhole routing with a timeout reset mechanism.

In this paper; we describe an advanced simulation environment which is used to examine, validate, andpredict the performance of mobile wireless network systems.This simulation environment overcomes many of the limitations found with analytical models, experimentation, and other commercial network simulators available on the market today We identify a set of components which make up mobile wireless systems and describe a set offlexible modules which can be used to model the various components and their integration.These models are developed using the Maisie simulation language.By modeling the various components and their integration, this simulation environment is able to accurately predict the performance bottlenecks of a multimedia wireless network system being developed at UCLA, determine the trade-offpoint between the various bottlenecks, andprovide performance measurements and validation of algorithms which are not possible through experimentation and too complexfor analysis.

The distributed system is becoming increasingly popular, and this produces the need for more sophisticated distributed control techniques. The authors present a method for distributed control using simple finite state automata. Each of the distributed entities is 'controlled' by its associated automaton, in the sense that the entity examines the state of the automaton to determine its behavior. The result of the collective behavior of all of the entities is fed back to the automata, which change their state as a result of this feedback. They give a new method of analysis which derives the steady state behavior of this system as a whole, by decomposing it into two parts: describing and solving an imbedding auxiliary Markov chain, and analyzing the behavior of the system within each of the states of this auxiliary chain.>

Analytic models for computer network performance evaluation are surveyed. The basics of network analysis are presented, the network design procedure is discussed, and some of the fundamentals of network control are introduced. Some of the issues surrounding the design and behavior of gigabit networks are discussed.>

The performance of job scheduling is studied in a large parallel processing system where a job is modeled as a concatenation of two stages which must be processed in sequence. P/sub i/ is the number of processors required by stage P as the total number of processors in the system. A large parallel computing system is considered where Max(P/sub 1/, P/sub 2/)>or=P>>1 and Max(P/sub 1/, P/sub 2/)>>Min(P/sub 1/, P/sub 2/). For such systems, exact expressions for the mean system delay are obtained for various job models and disciplines. The results show that the priority should be given to jobs working on the stage which requires fewer processors. The large parallel system (i.e. P>>1) condition is then relaxed to obtain the mean system time for two job models when the priority is given to the second stage. Moreover, a scale-up rule is introduced to obtain the approximated delay performance when the system provides more processors than the maximum number of processors required by both stages (i.e. P>Max(P/sub 1/, P/sub 2/)). An approximation model is given for jobs with more than two stages.>

It is suggested that if the large numbers of idle computers and workstations in distributed systems could be used then considerable computing power could be harnessed at low cost. Such systems are analyzed using Brownian motion with drift to model the execution of a program distributed over the idle computers in a network of idle and busy processors. The ways in which the use of these transient processors affects a program's execution time is determined. The probability density of a program's finishing time on both single and multiple transient processors is found. These results are explored for qualitative insight. Some approximations for the finishing time probability density are suggested.>

The authors model a job in a parallel processing system as a sequence of stages, each of which requires a certain integral number of processors for a certain interval of time. They derive the speedup of the system for two cases: systems with no arrivals, and systems with arrivals. In the case with no arrivals, their speedup result is a generalization of Amdahl's law (G.M. Amdahl, 1967). They extend the notion of power as previously applied to general queuing and computer-communication systems to their case of parallel processing systems. They find the optimal job input and the optimal number of processors to use so that power is maximized. Many of the results for the case of arrivals are the same as for the case of no arrivals. It is found that the average number of jobs in the system with arrivals equals unity when power is maximized. They also model a job in such a way that the number of processors required continuously varies over time. The same performance indices and parameters studied in the discrete model are evaluated for this continuous model.>

In this paper we examine dynamic load sharing in limited access distributed systems. In this class of distributed systems all servers are not accessible to all sources, and there exist many different accessibility topologies. We focus our attention on the ring topology and provide an analytic model to derive the approximate mean waiting time (our metric of performance). We then consider other limited access topologies and find that rather different interconnection patterns give similar performance measurements. We conjecture that the number of servers accessible to a source is the parameter with the greatest performance impact, in a limited access topology with load sharing. We also introduce another variable called diversity that is indicative of the degree of load sharing and speculate that performance is reasonably insensitive to diversity so long as it is non-zero. Using these conjectures we show how a reasonable estimate of the mean waiting time can be analytically derived in many limited access topologies.

We present an analytical model for evaluating the performance of finite-buffered packet switching multistage interconnection networks using blocking switches under any general traffic pattern. Most of the previous research work has assumed unbuffered, single buffer or infinite buffer cases, and all of them assumed that every processing element had the same traffic pattern (either a uniform traffic pattern or a specific hot spot pattern). However, their models cannot be applied very generally. There is a need for an analytical model to evaluate the performance under more general conditions.We first present a description of a decomposition & iteration model which we propose for a specific hot spot pattern. This model is then extended to handle more general traffic patterns using a transformation method. For an even more general traffic condition where each processing element can have its own traffic pattern, we propose a superposition method to be used with the iteration model and the transformation method. We can extend the model to account for processing elements having different input rates by adding weighting factors in the analytical model.An approximation method is also proposed to refine the analytical model to account for the memory characteristic of a blocking switch which causes persistent blocking of packets contending for the same output ports. The analytical model is used to evaluate the uniform traffic pattern and a very general traffic pattern " EFOS". Comparison with simulation indicates that the analytical model is very accurate.

The author evaluates the effect of ISDN (integrated services digital network) on the field of data networks, anticipates future directions for this technology, and discusses how the user should view these developments. It is emphasized that broadband ISDN (BISDN) is a service that has identified capabilities that are truly exciting and could very well dominate data networking in this decade. It is noted that the success of BISDN will depend strongly on the rollout of products, the ubiquity of its presence, and the tariffing of its services.>

The very fast bidirectional bus system (LAN) is analyzed. In contrast to previous studies, the assumptions that the bus is very fast is inherently embedded in the system model. The maximum throughput which can be achieved in the system, neglecting the randomized behavior of the system inputs, is calculated and bounds for the system efficiency under several conditions are derived. The system behavior is investigated under the assumption of stochastic arrivals. The model used is similar to the models used in the analysis of slotted ALOHA and CSMA; however, in contrast to those models, this model captures the correlation between events occurring in the system. The results of the analysis show that, in contrast to previously studied shared-channel systems, this system is very stable and the system throughput increases with the offered load.>

Distributed systems having large numbers of idle computers and workstations are analyzed using a very simple model of a distributed program (a fixed amount of work) to see how the use of transient processors affects the program's service time. The probability density of the length of time it takes to finish a fixed amount of work is determined. An equation is given for the main result for an M-processor network. Simulations confirm that Brownian motion with drift is an accurate model of system performance. With large programs that run for a long time relative to the length of available and nonavailable periods, the central limit-theorem applies, and the Brownian-motion-with-drift model remains good regardless of the distributions of the available and the nonavailable periods. Under these assumptions, the distribution of finishing time is very tight about its mean and well approximated by a normal distribution.>

The design, implementation, and use of a distributed processing environment on a network of IBM PCs running DOS is described. Temporarily unused PCs can be accessed by other users on the network to perform distributed computations. An owner of a PC need not be aware that the machine is being used during idle times; the machine is immediately returned when the owner begins to work again. Some degree of computation resiliency is provided in this unreliable environment; if a PC is part of a distributed algorithm and is reclaimed by its owner, the system finds a replacement node (if possible), resends the affected code to the processor, and restarts it. Thus, a distributed computation is able to proceed despite a set of transient processors. System performance, distributed applications, and fault tolerance are discussed. Performance improvements are demonstrated by applications like parallel merge sort and a distributed search solution to the eight puzzle.>

Multihop packet radio networks present many challenging problems to the network analyst and designer. The communication channel, which must be shared by all of the network users, is the critical system resource. In order to make efficient use of this shared resource, a variety of channel access protocols to promote organized sharing have been investigated. Sharing can occur in three domains: frequency, time, and space. This paper is mostly concerned with sharing and channel reuse in the spatial domain. A survey of results on approaches to topological design and associated channel access protocols that attempt to optimize system performance by spatial reuse of the communication channel is presented.

The paper addresses ways in which one can use "broadcast communication" in distributed algorithms and the relevant issues of design and complexity. We present an algorithm for merging k sorted lists of n/k elements using k processors and prove its worst case complexity to be 2n, regardless of the number of processors, while neglecting the cost arising from possible conflicts on the broadcast channel. We also show that this algorithm is optimal under single-channel broadcast communication. In a variation of the algorithm, we show that by using an extra local memory of O(k) the number of broadcasts is reduced to n. When the algorithm is used for sorting n elements with k processors, where each processor sorts its own list first and then merging, it has a complexity of O(n/k log(n/k) + n), and is thus asymptotically optimal for large n. We also discuss the cost incurred by the channel access scheme and prove that resolving conflicts whenever k processors are involved introduces a cost factor of at least log k.

The processes consisting of the packet interdeparture times for contention-type packet broadcasting systems in a hidden-user, singlehop environment are studied under the heavy-traffic assumption. The channel access protocols considered include pure ALOHA and unslotted nonpersistent carrier-sense-multiple-access (CSMA). The theory of superposition of independent renewal processes is applied to approximate the distribution of the duration of each unsuccessful transmission period in channel state. Our analysis results for the channel throughput and the coefficient of variation for the packet interdeparture time in symmetric configurations are shown to be in good agreement with simulation results over a wide range of offered channel traffic.

A new carrier sense multiple access (CSMA) algorithm, called virtual time CSMA, is described and analyzed. This algorithm uses a novel approach to granting access to the shared broadcast channel based on variable-rate clocks. Unlike other CSMA algorithms, the operation of virtual time CSMA reduces to the ideal case in the zero propagation time limit: a work-conserving, first-come first-servedM/G/1queueing system. The algorithm does not appear to be difficult to implement, but offers better throughput-delay performance than existing CSMA algorithms. A simple closed form technique for estimating the mean message delay is presented. This technique is of independent interest because of its applicability to certain "sliding window" tree conflict resolution algorithms. Extensive numerical results for the algorithm are presented, including comparisons with simulation and with other CSMA algorithms.

In this paper, we define a two-parameter family of protocols designed for multihop packet radio networks. We call these protocols rude-CSMA because under certain circumstances, maximum throughput is obtained when nodes, even after sensing a busy channel, transmit packets anyway with a nonzero rate. The performance of these protocols is analyzed for various special and random topologies.

In this paper we define a broadcast channel access protocol called spatial TDMA, which is designed specifically to operate in a multihop packet radio environment where the location of the nodes of the network is assumed to be fixed. The defined protocol assigns transmission rights to nodes in the network in a local TDMA fashion and is collisionfree. Methods for determining slot allocations are developed, and an approximate solution is given for determining the assignment of capacities for the links of the network that minimizes the average delay of messages in the system.

The channel throughput for a finite number of packet broadcasting users is analyzed for random access protocols, including slotted persistent carrier sense multiple access (CSMA) with and without collision detection and unslotted persistent CSMA with and without collision detection. We consider bothp- and 1-persistent CSMA. Our results can be extended to infinite population cases (by taking the proper limit), where they agree with the known throughput expressions when available.

We consider a system of two users of slotted CSMA-CD (carrier-sense multiple-access with collision detection). The two users are assumed to have independent identical packet arrival streams, the identical randomizing policy for retransmission, and an infinite capacity for storing queued packets. The mean packet delay (including the queueing and retransmission delays) is derived explicitly.

The processes consisting of the packet interdeparture times in contention-type packet broadcasting systems are studied under the heavy-traffic assumption. The channel access protocols considered include slotted and unslotted ALOHA and carrier-sense-multiple-access (CSMA) with and without collision detection. Through analysis of the Channel activity cycle, the distribution, mean, and coefficient of variation of the packet interdeparture times are explicitly derived. Taking the reciprocal of the mean interdeparture time, we obtain the channel throughput. Cases with dissimilar users are mainly considered, and systems of statistically identical users are treated as special cases.

A Markovian model is formulated to find the throughputdelay performance for slotted-ALOHA multihop packet radio networks with a fixed configuration of packet radio units (terminals and repeaters) and fixed source-to-link paths for packets. Improvements in performance which are obtained by the adjustment of transmission parameters (suppression/acceleration) according to the states of nearby units and/or by having repeaters equipped with multiple buffers are demonstrated.

The general problem of allocating the capacity of a communication channel to a population of geographically distributed terminals is considered. The main locus is on the queueing problems that arise in the analysis of random access resolution algorithms. The performance measures of interest are the channel efficiency and the mean response time. The nature of known solutions for various random access schemes is discussed and a lower bound for the mean response time is conjectured.

We consider a distributed communication network with many terminals which are distributed in space and wish to communicate with each other using a common radio channel. Choosing the transmission range in such a network involves the following tradeoff: a long range enables messages to reach their destinations in a few hops, but increases the amount of traffic competing for the channel at every point. We give a simple model for the per-hop delay in random access networks, analyze this tradeoff, and give the optimal transmission range. When choosing this optimal range, as a function of specified traffic and delay parameters, networks demonstrate an important self-adjusting capability. This capability to adjust to traffic makes heavily loaded networks far better than centralized systems (in which all messages must reach one common destination). Dividing a terminal population into power groups can improve any random access system, especially when the traffic is split between groups in an appropriate way, which we demonstrate. But since networks are hurt by destructive interference less than centralized systems, it is harder to improve them. Using power groups can significantly improve centralized systems, but will lead to a smaller relative improvement in networks. Decomposing the system into a hierarchy of ALOHA levels, with only a small population contending at the top level, can improve centralized systems but does not improve networks.

In this paper we determine throughput equations for a packet radio network where terminals are randomly distributed on the plane, are able to capture transmitted signals, and use slotted ALOHA to access the channel. We find that the throughput of the network is a strictly increasing function of the receiver's ability to capture signals, and depends on the transmission range of the terminals and their probability of transmitting packets. Under ideal circumstances, we show the expected fraction of terminals in the network that are engaged in successful traffic in any slot does not exceed 21 percent.

In multihop packet radio networks with randomly distributed terminals, the optimal transmission radii to maximize the expected progress of packets in desired directions are determined with a variety of transmission protocols and network configurations. It is shown that the FM capture phenomenon with slotted ALOHA greatly improves the expected progress over the system without capture due to the more limited area of possibly interfering terminals around the receiver. The (mini)slotted nonpersistent carrier-sense-multiple-access (CSMA) only slightly outperforms ALOHA, unlike the single-hop case (where a large improvement is available), because of a large area of "hidden" terminals and the long vulnerable period generated by them. As an example of an inhomogeneous terminal distribution, the effect of a gap in an otherwise randomly distributed terminal population on the expected progress of packets crossing the gap is considered. In this case, the disadvantage of using a large transmission radius is demonstrated.

A mobile stationless multi-hop packet radio network consists of a set of mobile and geographically distributed nodes (e.g., computers, terminals, etc., equipped with radio units), called packet radio units (PRUs), which communicate using a shared broadcast radio channel without a central station control. In this paper we consider the routing in highly mobile stationless multi-hop packet radio networks, We provide a validation of the use of the tier-ring architecture, and we present a scheme for handling mobile packet radio units in stationless environment by the use of a link-traversal approach when a node (packet radio unit) is no longer in possession of an outgoing link to communicate with the rest of the network.

In this paper we investigate the capacity of networks with a regular structure operating under the slotted ALOHA access protocol. We first consider circular (loop) and linear (bus) networks and then proceed to two-dimensional networks. For one-dimensional networks we find that the capacity is basically independent of the network average degree and is almost constant with respect to network size. For two-dimensional networks we find that the capacity grows in proportion to the square root of the number of nodes in the network provided that the average degree is kept small. Furthermore, we find that reducing the average degree (with certain connectivity restrictions) allows a higher throughput to be achieved. We also investigate some of the peculiarities of routing in these networks.

In this paper we formulate a general model of the capacity of single-hop slotted ALOHA networks. We find that the capacity can be expressed as a function of the nodal degree (i.e., number of nodes within range of a transmitter). We than evaluate this model for various traffic matrices. In order to satisfy the requirements of a given traffic matrix, the transmission power is selected accordingly and this determines the degree of the nodes and, hence, the network performance. Finally we compare our results to simulation studies.

In this paper we consider the problem of sending a stream of data (speech, for example) through a packet-switched network which introduces variable source-to-destination delays for different packets of the stream. Ideally, this delay difference should be smoothed so as to preserve the continuity of the stream. We investigate an adaptive destination buffering scheme which may be used to achieve the smoothing of the output stream. The scheme uses delay information, measured for previous streams, in order to compute destination buffering information. Specifically, of the lastmpacket delays, one discards the largestkand then the range of this partial sample is used for the destination wait timeD. We obtain a rule of thumb for choosingmandk, and demonstrate its applicability on some empirical delay distributions from ARPANET measurements. It is, in general, necessary to deal with discontinuities which occur even after smoothing. To this end, we consider two possible playback schemes: methodE(time expanded in order to preserve information) and methodI(late data ignored in order to preserve timing). The two methods are at opposite ends of a continuum of possible playback schemes. We study the implication of methodsEandIon the choice of smoothing parameters and establish a foundation for evaluating all schemes in this continuum.

The problem of fmdlng those optimum scheduling algorithms for time-shared systems that mlmmize a cost function that depends on waiting time and required service time IS considered An optimality condmon which sometimes leads to infeasible algorithms is established The procedure is unproved upon by use of a mathematical programming technique but still does not always generate feasible algorithms.These results are used as upper bounds on the performance of known feasible algorithms so that it is possible to evaluate how close to optimal the present algorithms come.

Abstract Large packet switching computer networks on the order of hundreds or thousands of nodes will soon emerge to handle the fast‐growing demands in data communication and resource sharing among various information processing systems around the world. The network topology design problem has long been recognized as extremely complex and very quickly becomes unmanageable as the size of the network increases. Existing heuristic design procedures are quite efficient for the design of small to moderate‐sized networks (25–75 nodes); however, they become very costly and even prohibitive when dealing with large networks. A design methodology based on the hierarchical clustering of the network nodes is presented in this paper in order to alleviate the computational cost involved in the design. More specifically, the emphasis is on the determination of a clustering structure which minimizes the computational cost of the design. Such a cost is assumed to have a polynomial growth with the number of nodes in the subnet to be designed. We present optimum results both for the number of clusters, number of superclusters, etc., and for the number of hierarchical levels. An expression for the average delay of a message in such a hierarchical network is also provided in terms of the average delays in the subnets composing the network. This decomposition leads to the design of smaller subnetworks for which we can utilize present design strategies.

This paper is concerned with a comparison study of three switching techniques used in computer-based communication networks: circuit switching, message (packet) switching, and cut-through switching. Our comparison is based on the delay performance as obtained through analytic models of these techniques. For circuit switching, the model reflects the phenomenon of channel reservation through which it can be shown that when circuit switching is used, data communication networks saturate rapidly. Through numerical examples, it is shown that the boundary between the areas of relative effectiveness of these switching techniques depends very much on the network topology (more precisely the path length of communication), the message length, and the useful utilization.

Packet switching offers attractive advantages over the more eonventional circuit-switched scheme, namely, flexibility in setting up user connections and more efficient use of resources after the connection is established. However, if user demands are allowed to exceed the system capacity, unpleasant congestion effects occur which rapidly neutralize the delay and efficiency advantages. Congestion can be eliminated by using an appropriate set of traffic monitoring and control procedures called flow control procedures. Flow control can be exercised at various levels in a packet network. The following levels are identified and discussed in this paper: hop level, entry-to-exit level, network access level, and transport level. For each level, the most representative techniques are surveyed and compared. Furthermore, the interaction between the different levels is discussed.

Nodal storage limitations in a store and forward computer network lead to blocking; this results in degradation of network performance due to the loss or retransmission of blocked messages. In this paper, we consider several schemes for sharing a pool of buffers among a set of communication channels emanating from a given node in a network environment so as to make effective use of storage in a variety of applications. Five sharing schemes are examined, analyzed, and displayed in a fashion which permits one to establish the tradeoffs among blocking probability, utilization, throughput, and delay. The key to the analysis lies in the observation that the equilibrium joint probability distribution of the buffer occupancy obeys the well-known product form solution for networks of queues. The study indicates advantages and pitfalls of each of the sharing schemes. We observe, in general, that sharing with appropriate restrictions on the contention for space is very much desirable.

In a recent paper we presented an analysis of flow control in store-and-forward computer communication networks using a token mechanism. The analysis assumed equilibrium conditions for a selected set of system parameters which were not dynamically adjusted to stochastic fluctuations in the system load; this mechanism was referred to as "static flow control." In this paper we study a "dynamic flow control" in which parameters of the system are dynamically adjusted to match the availability of resources in the network. Based on Markov decision theory, an optimal policy to dynamically select the number of tokens is formulated. Because an exact solution to the problem is extremely difficult, an effective heuristic solution to the problem is presented. Numerical results are given and it is shown that the throughput-delay performance of a network is better with dynamic control than with static control.

In this paper we develop an analytic model for end-to-end communication protocols and study the window mechanism for flow control in store-and-forward (in particular message-switching) computerbased communication networks. We develop a static flow control model in which the parameters of the system are not dynamically adjusted to the stochastic fluctuation of the system load. Numerical results are presented and it is shown that the throughput-delay performance of a network can be improved by proper selection of the design parameters, such as the window size, the timeout period, etc.

We study new access schemes for a population of geographically distributed data users who communicate with each other and/or with a central station over a multiple-access broadcast ground radio packet-switching channel. We introduce and analyze alternating priorities (AP), round robin (RR), and random order (RO) as new conflict-free methods for multiplexing buffered users without control from a central station. These methods are effective when the number of users is not too large; as the number grows, a large overhead leads to a performance degradation. To reduce this degradation, we consider a natural extension of AP, called minislotted alternating priorities (MSAP) which reduces the overhead and is superior to fixed assignment, polling, and known random access schemes under heavy traffic conditions. At light input loads, only random access schemes outperform MSAP when we have a large population of users. In addition, and of major importance, is the fact that MSAP does not require control from a central station.

A conventional ALOHA satellite link uses a transponder which blindly echoes all up-channel traffic on the down-channel. An ALOHA channel can never be fully utilized, so an intelligent satellite could statistically multiplex the successful packets from several slotted ALOHA up-channels onto a single down-channel to conserve bandwidth, and hence reduce cost. We refer to this as a concentrated ALOHA system. Throughput, delay and stability effects are considered, varying the number of up-channels per down-channel and the satellite buffer size. Up- and down-channel bandwidths are assigned independent linear costs, and all performance comparisons are between constant cost systems. It is shown that the marginal increase in system performance drops off so quickly that a small number of up-channels maximizes throughput if up-channel bandwidth has a non-zero cost. This small number is a function of the buffer size and the relative cost of up- to down-channel bandwidth. It is also shown that, even if satellite buffer space is free, a small buffer minimizes average delay for some previously studied protocols of this type. A new protocol which improves performance and allows a large buffer to be used effectively is introduced and analyzed. Solving for throughput and delay in concentrated ALOHA systems provides new analytic and numeric results for the G/D/I queue with rest period equal to the service time.

We extend the study of access schemes for packet-switched radio channels as an alternative to conventional wire communications for data transmission among users. Among the various multiple access schemes previously implemented or proposed, ALOHA presents many advantages, especially for a large population of bursty users. However, more than 60% of the ALOHA channel capacity is wasted. In this paper we introduce a separate large carrier-sensing user who "steals" slots which remain unused by the background of ALOHA users. This leads to a new multiple-access scheme: the Mixed ALOHA Carrier Sense (MACS) access scheme, whose performance We analyze. The total channel utilization is significantly increased with MACS, and the delaythroughput performance of both the large user and the background of ALOHA users is shown to be better with MACS than with a "split channel" mode in which the large user and the ALOHA users are each permanently assigned a portion of the channel.

We consider a population of terminals communicating with each other or with a central station over a packet-switched multiple access radio channel. To ensure the integrity of the transmitted data over the multi-access channel, we consider a reliable method using an error detecting block code in conjunction with a positive acknowledgment of each correct message. In this paper, we study the effect on channel capacity of the overhead created by the error-control traffic for both slotted ALOHA [1] and carrier sense multiple access (CSMA) [2]. For this we consider several implementation schemes for the two channel configurations: the common-channel configuration (a single channel for both information traffic and error-control traffic); and the split-channel configuration. The packet delay analysis will be treated in a forthcoming companion paper.

S-ALOHA channels are intrinsically unstable and must be equipped with proper controls. The function of the controls is to dynamically adjust the ALOHA channel transmission gates in accordance with the dynamic load fluctuations. The purpose of the controls is to protect the channel from unstable behavior while optimizing channel efficiency and performance during normal operating conditions. Two control algorithms are proposed: the Closed Loop Control-Collision Detect (CLC-CD) algorithm, which assumes the capability of distinguishing collision slots from empty slots at the receiving station; and the Closed Loop Control-Collision Non-Detect (CLC-CND) algorithm, which does not require such capability. The control implementation is distributed among all stations. Channel stability and efficiency is a-chieved by driving the total transmission and retransmission rate to unity, using a feedback, closed loop control approach. A family of simulation runs was made to evaluate and compare the performance of the CLC schemes with that of other schemes in a variety of traffic conditions. Simulation results show that the controlled systems converge to near optimality at steady state. Futhermore, the performance of the CLC-CND algorithms is about equivalent to that of the CLC-CD algorithm, thus indicating that the requirement of distinguishing collisions from empty slots is not critical for the performance of closed loop controls. The stability properties of the CLC algorithms and their superiority over other schemes for varying load patterns are demonstrated in a series of experiments involving cyclic traffic patZerns and pulse patterns. The CLC scheme displays better performance than the uncontrolled schemes as well as the previously proposed control schemes (namely, the Control Limit scheme and the Retransmission Control scheme) even when the latter are specifically tuned to handle the traffic pattern under consideration (the CLC scheme does not require any prior setting of the parameters). I.

The problem of data transmission in a network environment involves the design of a communication subnetwork. Recently, significant progress has been made in this technology, and in this article we survey the modeling, analysis, and design of such computercommunication networks. Most of the design methodology presented has been developed with the packet-switched Advanced Research Projects Agency Network (ARPANET) in mind, although the principles extend to more general networks. We state the general design problem, decompose it into simpler subproblems, discuss the solutions to these subproblems, and then suggest a heuristic topological design procedure as a solution to the original problem.

The speed at which large files can travel across a computer network is an important performance measure of that network. In this paper we examine the achievable sustained throughput in the ARPANET. Our point of departure is to describe the procedures used for controlling the flow of long messages (multipacket messages) and to identify the limitations that these procedures place on the throughput. We then present the quantitative results of experiments which measured the maximum throughput as a function of topological distance in the ARPANET. We observed a throughput of approximately 38 kbit/s at short distances. This throughput falls off at longer distances in a fashion which depends upon which particular version of the flow control procedure is in use; for example, at a distance of 9 hops, an October 1974 measurement gave 30 kbit/s, whereas a May 1975 experiment gave 27 kbit/s. The two different flow control procedures for these experiments are described, and the sources of throughput degradation at longer distances are identified, a major cause being due to a poor movement of critical limiting resources around in the network (this we call "phasing"). We conclude that flow control is a tricky business, but in spite of this, the ARPANET throughput is respectably high.

In two companion papers a method for multiplexing a population of terminals communicating with a central station over a packet-switched radio channel was introduced; this method is known as Carrier Sense Multiple Access (CSMA). CSMA, as with ALOHA multiaccess broadcast channels, has the unfortunate property that the throughput falls to zero as the channel load increases beyond a critical value. The dynamic behavior and stability of slotted ALOHA channels have been studied extensively and have led to a definition of stability. In this paper, similar techniques are used to analyze CSMA, which is shown to have a behavior not unlike that of ALOHA. However, contrary to ALOHA channels where steady-state performance is badly degraded when true stability is to be guaranteed, hence requiring dynamic control, we find that CSMA provides excellent stable performance even with as large a population as 1000 terminals. Furthermore, we study a simple adaptive retransmission control procedure which provides a significantly improved channel performance which is insensitive to the population size.

Data communications has come of age. In this paper, we highlight some of the principal events that led up to the revolution in communications among information processing systems. Perhaps the most important event was the technological development of packet switching in the form of the ARPANET. We devote most of this presentation to a brief summary of the ARPANET experience, emphasizing the description, functions, analysis, design and performance measurement of packet-switching networks. We also discuss some recent advances in radio packet switching for long-haul (i.e., satellite) and terminal-access communications.

Here we continue the analytic study of packet switching in radio channels which we reported upon m our two previous papers [1], [2] Again we consider a population of terminals communicating with a central station over a packet-switched radio channel. The allocation of bandwidth among the contending terminals can be fixed [e.g., time-division multiple access (TDMA) or frequency-division multiple access (FDMA)], random [e.g., ALOHA or carrier sense multiple access (CSMA)] or centrally controlled (e.g., polling or reservation). In this paper we show that with a large population of bursty users, (as expected) random access is superior to both fixed assignment and polling. We also introduce and analyze a dynamic reservation technique which we call split-channel reservation multiple access (SRMA) which is interesting in that it is both simple and efficient over a large range of system parameters.

In this paper, the rationale and some advantages for multiaccess broadcast packet communication using satellite and ground radio channels are discussed. A mathematical model is formulated for a "slotted ALOHA" random access system. Using this model, a theory is put forth which gives a coherent qualitative interpretation of the system stability behavior which leads to the definition of a stability measure. Quantitative estimates for the relative instability of unstable channels are obtained. Numerical results are shown illustrating the trading relations among channel stability, throughput, and delay. These results provide tools for the performance evaluation and design of an uncontrolled slotted ALOHA system. Adaptive channel control schemes are studied in a companion paper.

Absfract-Radio communication is considered as a method for providing remote terminal access to computers. Digital byte streams from each terminal are partitioned into packets (blocks) and trans-mitted in a burst mode over a shared radio channel. When many terminals operate in this fashion, transmissions may conflict with and destroy each other. A means for controlling this is for the termi-nal to sense the presence of other transmissions; this leads to a new method for multiplexing in a packet radio environment: carrier sense multiple access (CSMA). Two protocols are described for CSMA and their throughput-delay characteristics are given. These results show the large advantage CSMA provides as compared to the random ALOHA access modes. L I.

In a companion paper [1], the rationale for multiaccess broadcast packet communication using satellite and ground radio channels has been discussed. Analytic tools for the performance evaluation and design of uncontrolled slotted ALOHA systems have been presented. In this paper, a Markovian decision model is formulated for the dynamic control of unstable slotted ALOHA systems and optimum decision rules are found. Numerical results on the performance of controlled channels are shown for three specific dynamic channel control procedures. Several practical control schemes are also proposed and their performance compared through simulation. These dynamic control procedures have been found to be not only capable of preventing channel saturation for unstable channels but also capable of achieving a throughput-delay channel performance close to the theoretical optimum.

We consider a population of terminals communicating with a central station over a packet-switched multiple-access radio channel. The performance of carrier sense multiple access (CSMA) [1] used as a method for multiplexing these terminals is highly dependent on the ability of each terminal to sense the carrier of any other transmission on the channel. Many situations exist in which some terminals are "hidden" from each other (either because they are out-of-sight or out-of-range). In this paper we show that the existence of hidden terminals significantly degrades the performance of CSMA. Furthermore, we introduce and analyze the busy-tone multiple-access (BTMA) mode as a natural extension of CSMA to eliminate the hidden-terminal problem. Numerical results giving the bandwidth utilization and packet delays are shown, illustrating that BTMA with hidden terminals performs almost as well as CSMA without hidden terminals.

Abstract Two problems relevant to the design of a store‐and‐forward communication network (the message routing problem and the channel capacity assignment problem) are formulated and are recognized to be essentially non‐linear, unconstrained multicommodity (m.c.) flow problems. A “Flow Deviation” (FD) method for the solution of these non‐linear, unconstrained m.c. flow problems is described which is quite similar to the gradient method for functions of continuous variables; here the concept of gradient is replaced by the concept of “shortest route” flow. As in the gradient method, the application of successive flow deviations leads to local minima. Finally, two interesting applications of the FD method to the design of the ARPA Computer Network are discussed.

Scheduling algorithms for time shared computing facilities are considered in terms of a queueing theory model.The extremely useful limit of "processor sharing" is adopted, wherein the quantum of service shrinks to zero; this approach greatly simplifies the problem.A class of algorithms is studied for which the scheduling discipline may change for a given job as a function of the amount of service received by that job.These multilevel disciplines form a natural extension to many of the disciplines previously considered.The average response time for jobs conditioned on their service requirement is solved for.Explicit solutions are given for the system M/G/1 in which levels may be first come first served (FCFS), feedback (FB), or round-robin (RR) in any order.The service time distribution is restricted to be a polynomial times an exponential for the case of RR.Examples are described for which the average response time is plotted.These examples display the great versatility of the results and demonstrate the flexibility available for the intelligent design of discriminatory treatment among jobs (in favor of short jobs and against long iobs) in time shared computer systems.

Abstract The design of the ARPA Computer Network brought together many individuals with diverse backgrounds and philosophies. In this paper, we review the methods used in the design of the Network from the vantage of over two years' experience in its development. The design variables, system constraints, and performance criteria for the network are discussed along with an evaluation of the tools used to design an efficient and reliable system. The design procedures and the conclusions reached about the network's properties appear to be generally applicable to message switched networks. Consequently, the results of this paper should be useful in the design and study of other store‐and‐forward computer communication networks.

Abstract We consider a model which is applicable to time‐multi‐plexed systems, such as multiplexed communication channels and time‐shared computing facilities. In this (processor‐sharing) queueing model, all jobs currently in the system share equally the processing capability of the server. In this paper, we investigate the processor‐sharing model for the case of bulk arrivals. The mean response time of the system as a function of required service time is derived. An example is given to show the effect of bulk arrivals versus single arrivals for a constant utilization.

Solved for is the expected swap time expended for those customers in the system of queues in general models of time- shared systems. This quantity is expressed in terms of the expected queueing time conditioned on required service time and is applied to a number of examples of interest.

Time-shared processing systems (e.g. communication or computer systems) are studied by considering priority disciplines operating in a stochastic queueing environment. Results are obtained for the average time spent in the system, conditioned on the length of required service (e.g. message lenght or number of computations). No chage is made for swap time, and the results hold only for Markov assumptions for the arrival and service processes. Two distinct feedback models with a single quantum-controlled service are considered. The first is a round-robin (RR) system in which the service facility processes each customer for a maximum of q sec. If the customer's service is completed during this quantum, he leaves the system; otherwise he returns to the end of the queue to await another quantum of service. The second is a feedback (FB N ) system with N queues in which a new arrival joins the tail of the first queue. The server gives service to a customer from the n th queue only if all lower numbered queues are empty. When taken from the n th queue, a customer is given q sec of service. If this completes his processing requirement he leaves the system; otherwise he joins the tail of the ( n + 1)-st queue ( n = 1, 2, · · ·, N - 1). The limiting case of N → ∞ is also treated. Both models are therefore quantum-controlled, and involve feedback to the tail of some queue, thus providing rapid service for customers with short service-time requirements. The interesting limiting case in which q → 0 (a “processor-shared” model) is also examined. Comparison is made with the first-come-first-served system and also the shortest-job-first discipline. Finally the FB ∞ system is generalized to include (priority) inputs at each of the queues in the system.

Time-shared computer (or processing) facilities are treated as stochastic queueing systems under priority service disciplines, and the performance measure of these systems is taken to be the average time spent in the system. Models are analyzed in which time-shared computer usage is obtained by giving each request a fixed quantum Q of time on the processor, after which the request is placed at the end of a queue of other requests; the queue of requests is constantly cycled, giving each user Q seconds on the machine per cycle. The case for which Q → 0 (a processor-shared model) is then analyzed using methods from queueing theory. A general time-shared facility is then considered in which priority groups are introduced. Specifically, the p th priority group is given g p Q seconds in the processor each time around. Letting Q → 0 gives results for the priority processor-shared system. These disciplines are compared with the first-come-first-served disciplines. The systems considered provide the two basic features desired in any time-shared system, namely, rapid service for short jobs and the virtual appearance of a (fractional capacity) processor available on a full-time basis. No charge is made for swap time, thus providing results for “ideal” systems. The results hold only for Poisson arrivals and geometric (or exponential) service time distributions.

Results are obtained for a model of many processors operating in series. The results are obtained directly by recognizing that a sequential processing may be viewed as a cyclic queue. Exact results are given for two sequential processing stages with a buffer storage of arbitrary size between the stages, and approximate results for the case of 2 M ( M an integer) stages. The analysis is good only for exponentially distributed computation times.

A new procedure is described for determining that frequency at which the spectrum of a signal has its absolute peak. The salient feature of the procedure is that it does not explicitly involve the estimation of the spectrum of the signal itself. Specifically, it is shown that the limit of the iterated normalized auto-correlation [see (8) and (9)] of a function,f(t), is a pure cosine wave whose frequency corresponds to the location of the peak of the spectrum off(t). Furthermore, if one is willing to accept an estimated peak frequency of maximum energy to within a given finite spectral resolution, then the procedure terminates after a specified finite number of iterations. Results from a computer simulation of the procedure are described. The areas of application of this procedure are discussed, and the results indicate that this method of detecting a signal (i.e., by the peak of its spectrum) merits further consideration. It is important to note that the consideration of random processes has not been undertaken in this initial study; the results apply to the spectral peak of a deterministic signal only.