Femtocells that use co-channel allocation with macrocells can considerably increase wireless coverage and system capacity, especially for indoor and cell-edge users. However, the benefit is realized only when cross-tier interference between femtocells and macrocells is well managed. We propose a power allocation algorithm for femtocells in downlink OFDMA systems that effectively reduces cross-tier interference by considering the influence on neighboring macro mobile stations (MSs), when only limited channel information about those MSs is available. The use of the proposed scheme enables femtocells to maintain their high throughputs while significantly reducing the performance degradation of neighboring macro MSs, with only the information that is available to the femtocells in practice.

Fractional frequency reuse (FFR) has been actively studied in order to reduce inter-cell interference, especially for cell edge users in current orthogonal frequency division multiple access systems. However, the best resource block (RB) allocation to the edge users is limited by conventional FFR, which has subbands consisting of contiguous RBs. In this paper, we propose a band-distributed FFR scheme that effectively employs channel quality information (CQI) by fully exploiting frequency diversity to mitigate this limitation. In this scheme, the entire system bandwidth is divided into two classes of sub-bands that comprise non-contiguous RBs. Our analysis shows that the proposed band-distributed FFR has better performance than the conventional FFR for various environments defined in IMT-advanced models. Moreover, the gain with our scheme increases as the coherent bandwidth (Be) increases.

Game theory has been a useful tool for the analysis of random-access based wireless networks due to their decentralized operations. This paper studies one of the most widely used random access schemes, slotted Aloha, by modeling it as games. Unlike other game theoretic analyses of slotted Aloha, channel capture is assumed in this paper. Two different types of Aloha games, cooperative and non-cooperative, are considered since scenarios for behaviors of mobile terminals in slotted Aloha systems can be twofold. With analysis, a threshold strategy, quite a simple strategy characterized only by the threshold value, is shown to be a potential optimal strategy for the cooperative game, and is also shown to be the unique Bayesian Nash equilibrium (BNE) for the non-cooperative game. Numerical examples provide the threshold values for the optimal strategies and BNEs with different system configurations.

Since many random-access protocols are designed based on the assumption that all terminals follow the same medium-access-control (MAC) policy, they can be vulnerable to the selfish behavior of each terminal. This paper proposes robust random-access protocols for wireless networks in fading environments, where each terminal operates in a Nash equilibrium (NE) of a random-access game. Since any deviation of a terminal from an NE penalizes the terminal, the network with this protocol becomes more robust by preventing a selfish terminal from violating the access protocol. We model slotted ALOHA and carrier-sense multiple access (CSMA) as games and show that the strategies in symmetric equilibria of these games have the properties so that a terminal with a better channel state is more likely to access the channel. Thus, these protocols ensure multiuser diversity as well as robustness, a conclusion confirmed by numerical results.

We consider the problem of designing a network which minimizes the total cost of the switching facilities and the fiber links, by choosing the subset of nodes at which to install switching functionality and the subset of the available fiber links to employ for interconnecting nodes. This objective addresses jointly two of the most significant costs in the design of a communications network - the number of switching sites and the total linear distance of the utilized links - and results in substantial cost benefits. Since relative costs vary depending on specific circumstances, we characterize the tradeoff between the number of switching sites and the total link length. Our study is performed for a network supporting full connectivity between all nodes, rather than for a specific traffic matrix, and thus reveals fundamental properties inherent to the given topology. We address both the unprotected and the protected cases, and we present heuristic algorithms to solve the problem.

We consider the adaptive throughput optimization problem for multiple-input multiple-output (MIMO) systems in Rayleigh fading channels. With perfect channel knowledge at the transmitter (CSIT), MIMO channels can be decomposed into several sub-channels. To solve the problem of maximizing the sum throughput of all sub-channels, we take a two-step approach: allocation of power to each sub-channel and adaptive modulation at each sub-channel. By using the existing results on the optimal adaptive modulation parameters, we focus on the power allocation to sub-channels. Specifically, we propose four power allocation schemes and compare the schemes based on numerical results.

In this paper, we present a methodology to analytically compute the end-to-end throughput that can be achieved on a path between two nodes in an IEEE 802.11 multihop wireless network with homogenous data transmission rates. Knowledge of achievable end-to-end throughput is important for making routing decisions and performing admission control. Unlike a wired network where the throughput of a path after accounting for overheads is roughly equal to the lowest bandwidth along the path, the throughput of a wireless multihop path is much lower than the minimum data rate along the path because of sharing of the medium by nodes within carrier sensing range of each other. Our analysis of the achievable throughput takes into account this effect of sharing of the medium in the form of blocking and interference. We apply our analysis to several randomly generated paths, and compare the analytical results with those from simulations to validate the analysis.

We consider the traffic grooming problem in WDM/SONET rings with multiple line speeds. This is motivated by the fact that when traffic demands are non-uniform and are spread over a relatively wide range, a ring using multiple line speeds would lead to a lower cost, owing to the economy of scale seen in devices, in particular, electronic ADMs, running at higher speeds. We give novel integer linear programming (ILP) formulations for the problem. We also propose techniques that exploit the problem structure and, thereby, reduce the computation time. As a result, many problem instances can be solved exactly. For large size problems, we propose an efficient heuristic algorithm that achieves a similar cost using a fraction of the computation time. We show that, by allowing WDM/SONET rings to run at different line speeds, we can greatly reduce the ADM cost. We also study the cost benefits of traffic switching, compare UPSR and BLSR, and study the trade-offs of shortest path routing in BLSR

We consider a network consisting of N nodes and a certain number of links that could be used to interconnect these nodes. The problem we address is to determine the smallest subset of switching nodes (in which to provide optical or electronic switching capability) necessary and sufficient to provide full end- to-end connectivity among all nodes. It is shown that this selection leads to the minimum number of transceivers needed to achieve full connectivity. We then address the same problem with the additional requirement of survivability, whereby the failure of any one link does not lead to any disconnection in the network. To solve the above stated problems, we present heuristic and optimal algorithms, and we study how the number of switches varies with the number of potential links.

There are many advantages of deploying an all- optical network. Unfortunately, there are still few guidelines on how to properly design the physical topology for such a network. We propose an efficient physical topology design algorithm and we use the asymptotic growth rate of the provisioned capacity as a metric to compare various design alternatives. A higher asymptotic growth rate translates directly into higher deployment cost for large networks. Our study shows that taking fiber length into consideration can lead to lower capacity requirement. We also find that a sufficiently large fiber-to-node ratio is necessary in order to minimize the asymptotic growth in the provisioned capacity, increase capacity utilization and minimize the need for wavelength conversion. We study a real network and find that its fiber-to-node ratio is too low. As a result, large provisioned capacity is required and less than 55% of the capacity is usable. By increasing the ratio, we can reduce the provisioned capacity and achieve close to 80% utilization.

The impact of interference on the throughput of a multihop path in a wireless network is studied in this paper. Interference is caused due to packets of the same end-to-end flow (intra-path), as well as packets of different flows (inter-path), as packets are transmitted over multiple hops in the network. We show how much throughput is lost due to such interference, and how much is lost due to other factors like the media access scheme, maximum transmission power limit, or overhead at various networking layers. The MAC is considered to be that of IEEE 802.11, while the physical layer is chosen to be that specified in IEEE 802.11a. The simulations are performed with careful representation of wireless channel characteristics, receiver performance, and IEEE 802.11 MAC layer parameters, such as the signal level that causes a device to be blocked (energy detect (ED) threshold). Sensitivity of the throughput of a multihop path, to parameters like transmission power, data rate and ED threshold is studied, and the throughput achievable by optimizing these parameters is evaluated for environments with different propagation characteristics. The limiting factors are identified in different cases, by contrasting the throughput of a multihop path with that of a single hop path and an optimally scheduled multihop path. The results are revealing in terms of the amount of throughput lost due to various factors. The paper also provides a good understanding with regards to the tuning of various parameters to improve the throughput of multihop paths in a wireless network.

In this paper, we present an approach to routing critical data in multihop wireless networks over the most reliable links in the network. We present the concept of a maximum SNR spanning tree (MSST) in multihop wireless networks, a spanning tree with the maximum sum of signal to noise ratios of links that form the tree. We show that such a backbone has certain properties that would be of interest in multihop wireless network deployments where reliability of links over which data is routed is of critical concern. The minimum SNR along the path on the MSST between any pair of nodes is the highest among all paths between the pair of nodes. Also, the minimum value of SNR among the SNRs of links that form the MSST is the highest among all spanning trees of the network.

In this paper we characterize an IEEE 802.11a receiver using measurements in an indoor environment. While there have been a number of studies measuring path loss in indoor environments, there is little work on measurements regarding receiver synchronization, and packet error rate (PER) for IEEE 802.11a. This study allows better modeling of wireless reception in simulators, while also providing insights on wireless link performance. To study these characteristics, measurement tools were developed to capture relevant data pertaining to each stage of packet reception at the receiver. For the receiver considered, we find synchronization to be a critical component of packet reception. If synchronization is achieved, there are almost no data errors for 6 to 24 Mbps, resulting in almost identical PER performance of these data rates. For higher data rates, fluctuations in SNR are found to have a huge impact on PER, even for high average SNR values. The measurements bring out some factors which are normally not considered in PER models and the design of rate adaptation schemes. It also provides insights on the sensitivity of performance to various parameters, allowing better wireless network deployment.

In this paper, we consider optimization of CSMA/CA based wireless networks such as IEEE 802.11 Wireless LANs. A fundamental component of the MAC layer functionality in such networks is the binary exponential backoff (BEB) of contending nodes which serves as a means of arbitrating distributed channel access. In this paper, we show that the joint optimization of initial contention window (CWmin) and the number of backoff stages in BEB yields, interestingly, no additional gains over a simple CWmin optimization that is performed by considering that BEB is absent. Thus, BEB has negligible impact once CWmin is optimized. While this result holds only for an ideal WLAN, in the presence of channel errors, BEB penalizes performance even when CWmin is optimized. Finally, disabling BEB and optimizing CWmin not only improves short-term fairness significantly but it also stabilizes the system even when there are asymptotically large number of saturated users contending.

Most current deployments of IEEE 802.11 based wireless LANs suffer from various inefficiencies arising from the interactions of MAC and Physical layers. These inefficiencies often limit network users from reaping the full potential of the high physical data rates in these systems. We consider optimizing these systems to mitigate, the following forms of inefficiencies: (i) selfish users exploiting the dependency of DCF channel share achieved on the transmission strategies used, leading to inefficient operating points (Nash Equilibria) (ii) Automatic rate adaptation enabled devices reducing the system throughput even for moderate loads, and, (iii) low data rate users limiting the throughput of high data rate users. In the companion paper, we have proposed adapting CWmin and disabling Exponential Backoff as a simple paradigm of operating CSMA/CA. We show that such a technique is effective in reducing the penalty due to selfish link adaptation and auto rate adaptation. Finally, we propose using multiple channels to improve the throughput of high data rate users. We show that the system throughput can increase super-linearly with the number of channels, with increased benefit when OFDM based IEEE 802.11g high rate users co-exist with low rate IEEE 802.11b users.

We consider the following two views of an IEEE 802.11 based Wireless LAN: (i) as seen by the WLAN medium and (ii) as seen by a user. In the system centric view, we model the WLAN medium as a server that allocates its resources to users in a round Robin manner. This resource sharing model not only provides a simple model for the system, it also enables us to derive the channel service rate and the total delay incurred in transmitting a packet. For Poisson arrivals, the resource sharing model takes the form of an M/G/1/PS system with the mean delay being the same as that in an equivalent M/M/1 system. We then take a user centric view and model each user's queue as a separate G/G/1 queue. We derive the probability distributions for the different delay sources, i.e., random back-off time, random number of collisions and random number of successful transmissions from other users. This user centric model can provide insights into understanding access and queuing delays in 802.11 DCF. Finally, we discuss the utility of these models for functions such as capacity analysis, admission control and QoS enforcement.

WDM/SONET provides a natural migration path to support traffic growth. In WDM/SONET, each wavelength is a separate SONET ring and each ring can be set to one of several line speeds. The line speed should be high if there is enough traffic to realize the economy of scale, otherwise, it should be low to reduce the cost. Despite of the advantages, there are no general tools and methodologies available to help network designers enjoy the benefits of multiple line speeds. For the first time, we propose a comprehensive approach to solve the traffic grooming problem, which includes both novel, complete ILP formulations that can be used to solve small size problems exactly and an efficient heuristic algorithm that can be used to solve large problems quickly. Using the tools we developed, we study the trade-offs of shortest path routing, study the cost benefits of traffic switching, compare UPSR and BLSR, and show that multiple line speeds can significantly reduce cost

In this paper, we present a simple analytical framework for computing the throughput of IEEE 802.11 based wireless LANs. We show that a notion of average cycle time exists in DCF access where by all stations, on average, successfully transmit one packet in a cycle. We provide explicit expressions for the average cycle time and the system throughput. Our approach readily depicts that the average cycle time, and hence the throughput, is the same for different users regardless of the differences in their physical data rates. It thus serves as a simple and accurate re-derivation of the well known equal throughput property of DCF seen in multi-rate WLANs. Our analytical results are compared against extensive simulations and are shown to be in very good agreement

In this paper we study the ability of an IEEE 802.11g WLAN to support video-conferencing and data applications. We evaluate the number of simultaneous video-conference calls that can be supported, subject to user perception-based quality requirements, and compare the performance of two MAC protocols: the default distributed coordination function (DCF) protocol and the enhanced distributed channel access (EDCA) protocol. We also assess the effect of the presence of data traffic generated by Web browsing and file transfer applications and the physical size of the network on the number of video conference calls that can be supported. The analysis of the network is carried out by means of simulation; great care is taken to accurately represent the applications and the network, requiring several modifications and additions to the widely-used ns-2 network simulator. At the application layer, traffic is generated using realistic models or real traces, and user perception-based quality metrics (for example, the mean opinion score for voice) are used to assess the network's performance. Within the network, we use accurate representations of the MAC protocols, and use a wireless channel model which incorporates the effect of frequency-selective fading. We find that the presence of data traffic does not reduce the number of video-conference calls that can be supported when EDCA is used; this is not the case with DCF, Furthermore, the performance of both data applications considered is slightly improved by the use of EDCA.

We consider the traffic grooming problem in WDM/SONET UPSR rings with multiple line speeds. This is motivated by the fact that when traffic demands are non-uniform and are spread over a relatively wide range, a ring using multiple line speeds would lead to a lower cost, owing to the economy of scale seen in devices, in particular, electronic ADMs, running at higher speeds. We give a novel integer linear programming (ILP) formulation for the problem. We also propose two techniques to exploit the symmetric problem structure resulting from the equivalency in the line speed assignments and the color assignments for wavelengths. The techniques reduce computation time, thus, allow many problem instances to be solved exactly. For large size problems, we propose efficient heuristic algorithms that achieve a similar cost using a fraction of the computation time. We show that, by allowing WDM/SONET rings to run at different line speeds, we can greatly reduce the ADM cost. We also show that allowing nodes to switch traffic can help to reduce the cost further.

We investigate the quality of voice communication over IEEE 802.11a WLANs taking realistic channel models into account. We show that the assessment of VoIP performance is overly optimistic if fading is ignored when compared with systems where fading is taken into account. Via simulation, we derive the distribution of VoIP performance (in terms of mean opinion score-MOS) for all the data rates specified in the IEEE 802.11a standard and a range of typical signal-to-noise ratio values. We use a measure for assessing VoIP performance that includes a target level of user-satisfaction and a bound on the probability of not achieving this target. The impact of retransmissions and channel estimation errors on VoIP performance is also discussed.

In this paper we evaluate the capacity of an IEEE 802.11b network carrying voice calls in a wide range of scenarios, including varying delay constraints, channel conditions and voice call quality requirements. We consider both G.711 and G.729 voice encoding schemes and a range of voice packet sizes. We first present an analytical upper bound and, using simulation, show it to be tight in scenarios where channel quality is good and delay constraints are weak or absent. We then use simulation to show that capacity is highly sensitive to the delay budget allocated to packetization and wireless network delays. We also show how channel conditions and voice quality requirements affect the capacity. Selecting the optimum amount of voice data per packet is shown to be a trade-off between throughput and delay constraints: by selecting the packet size appropriately given the delay budget and channel conditions, the capacity can be maximized. Unless a very high voice quality requirement precludes its use, G.729 is shown to allow a capacity greater than or equal to that when G.711 is used, for a given quality requirement.

SONET rings remain the dominant optical transport architecture in the metropolitan area. To support traffic growth on these rings, WDM technology is used to provide multiple SONET rings on the same fiber, each SONET ring running on a separate wavelength. Traffic grooming refers to intelligently arranging low speed traffic streams onto different SONET rings and selecting the proper line speed for each wavelength so as to minimize certain cost objective, such as the total cost of electronic Add-Drop Multiplexer (ADM) equipments used. The problem can be formulated as an Integer Linear Programming (ILP) problem by generalizing the formulation in [1] [2] to support multiple line speeds. Unfortunately, solving the ILP directly could be very computation intensive. In this paper, we propose a non-linear formulation instead, and then solve it by decomposing it into several smaller ILP subproblems, each can be solved separately by an ILP solver. Decomposition allows us to exploit the symmetry in the problem structure, and cut down the solution space dramatically, therefore, reducing the computation time to solve a problem. Even if we may have to terminate the computation early for large size problems, decomposition allows us to explore a larger portion of the solution space in a given amount of time, therefore, obtain better results.

With the recent explosion in wireless mobile communication, a great deal of work is taking place to solve the problem of handling mobile users in the Internet. This problem encompasses the design of schemes for tracking and routing to mobile users in various networks and subnetworks that make up the Internet infrastructure. Switched LANs today employ the transparent learning protocol which allows switches to learn about the location of users by promiscuously listening to the traffic emitted by the users. Unfortunately, as this paper shows, fast moving users render the transparent learning protocol inefficient so that high bandwidth consumption and even packet loss may occur. To prevent packets from being mis-routed or even lost, one can employ a lightweight control-based mechanism for user tracking, based on an existing LAN-protocol known as the generic attribute registration protocol (GARP). However, this solution can lead to large databases at the switches, which can in turn significantly increase the cost of the Internet infrastructure. In this paper, we propose to combine and tune the transparent learning protocol and the GARP protocol in an efficient way as to jointly minimize packet loss, bandwidth consumption and the size of the tracking databases in a large switched network. Our optimization is shown to be effective for a wide range of mobility speeds and application characteristics, and consistent with the state of technology.

To support latency sensitive traffic such as voice, network providers can either use service differentiation to prioritize such traffic or provision their network with enough bandwidth so that all traffic meets the most stringent delay requirements. In the context of wide-area Internet backbones, two factors make overprovisioning an attractive approach. First, the high link speeds and large volumes of traffic make service differentiation complex and potentially costly to deploy. Second, given the degree of aggregation and resulting traffic characteristics, the amount of overprovisioning necessary may not be very large. This study develops a methodology to compute the amount of overprovisioning required to support a given delay requirement. We first develop a model for backbone traffic which is needed to compute the end-to-end delay through the network. The model is validated using 331 one-hour traffic measurements collected from the Sprint IP network. We then develop a procedure which uses this model to find the amount of bandwidth needed on each link in the network so that an end-to-end delay requirement is satisfied. Applying this procedure to the Sprint network, we find that satisfying end-to-end delay requirements as low as 3 ms requires only 15% extra bandwidth above the average data rate of the traffic.

As the Internet becomes the medium of choice for transporting integrated data, voice and video traffic, it is crucial that the quality of service approaches the level seen in networks traditionally employed for carrying these various traffic types. For example, the quality of voice communication in the Internet should approach the toll-quality levels experienced in the public switched telephone network (PSTN). Mobile wireless users have become a common sight across the world, and have motivated the need for further evolving the Internet protocols and infrastructures, originally intended for fixed users, into new realizations capable of supporting portable and even mobile users at various speeds and across many geographical areas [10]. In particular, with mobile users comes the need for user tracking protocols that work seamlessly for all roaming needs and application characteristics.In this paper, we show that existing explicit and implicit schemes for user tracking in packet networks with mobile users can lead to poor quality of voice streaming applications. Implicit tracking schemes, such as the transparent learning protocol employed by layer-2 switches employ timeout-based caches which can lead to voice clips and/or echo and other delay impairments for interactive applications such as packet voice. Explicit tracking schemes such as binding updates employed by Mobile IP [9] or the tracking protocol used in HAWAII [8] are plagued by control overhead, delayed updates and large tracking databases which also degrade voice call quality and increase the cost of the network.To resolve these challenges we propose a number of techniques to improve user tracking in packet networks with the goal of attaining toll-quality. First, we propose an optimization which limits the propagation of explicit tracking information to entities that can receive them in a timely manner. Second, the lifetime value used by the implicit protocol is jointly tuned to account not only for the user mobility rate but also for the impact of packet loss on voice call performance. Finally, an adaptive tracking strategy is proposed that dynamically alternates between explicit and implicit tracking according to the load in the network. While other hybrid implicit and explicit protocols have been proposed in the past, this work is the first to target packet voice traffic. We demonstrate the benefits of these techniques by simulating a large network carrying many packet voice calls and measuring the user perceived quality of the voice calls.

In order to cost-effectively accommodate a large number of titles in a video system, a hierarchical storage system can be used. In this system, not-so-popular video files are stored in a tertiary level such as a disk/tape library. These files are transferred, or "staged," to a secondary level composed of magnetic disks before being streamed to the users. This system overcomes the current limitations in using disk/tape libraries to stream videos and resolves the bandwidth difference between staging and streaming. We present, via analysis, a model of the system and determine the minimum storage and bandwidth required, at each level, to meet a given user delay goal. We also analyze a number of system operations pertaining to whether or not a file is played while it is being staged (i.e., stage-streaming) and whether or not the displayed segments are deleted (i.e., trail-deletion). We show that stage-streaming and trail-deletion can achieve substantially lower bandwidth and storage requirements. In order to further increase the streaming and storage scalability, a distributed storage system can be used where multiple local servers are put close to user pools and get their files from one of the libraries through a network. We extend the models developed to such a system and specify the resource requirements to meet a given delay goal.

As the Internet evolves into a ubiquitous communication infrastructure and provides various services including telephony, it will be expected to meet the quality standards achieved in the public switched telephone network. Our objective in this paper is to assess to what extent today's Internet meets this expectation. Our assessment is based on delay and loss measurements taken over wide-area backbone networks and uses subjective voice quality measures capturing the various impairments incurred. First, we compile the results of various studies into a single model for assessing the voice-over-IP (VoIP) quality. Then, we identify different types of typical Internet paths and study their VoIP performance. For each type of path, we identify those characteristics that affect the VoIP perceived quality. Such characteristics include the network loss and the delay variability that should be appropriately handled by the playout scheduling at the receiver. Our findings indicate that although voice services can be adequately provided by some ISPs, a significant number of Internet backbone paths lead to poor performance.

As the Internet evolves into a ubiquitous communication infrastructure and provides various services including telephony, it has to stand up to the toll quality standards set by traditional telephone companies. Our objective is to assess to what extent today's Internet meets this expectation. Our assessment is based on delay and loss measurements taken over wide-area backbone networks, considers realistic VoIP scenarios and uses quality measures appropriate for voice. Our findings indicate that although voice services can be adequately provided by some ISPs, a significant number of paths lead to poor performance even for excellent VoIP end-systems. This makes a strong case for special handling of voice traffic on those paths. Even on the good paths, rare loss events can occasionally cause perceptible degradation of voice quality. Finally, the appropriate choice of the playout buffer scheme for each path was found to be of critical importance for the perceived quality.

Interactive TCP applications, such as Telnet and the Web, are particularly sensitive to network congestion. Indeed, congestion-induced queuing and packet loss can be a significant cause of large delays and variability, thereby decreasing user-perceived quality. We consider addressing these effects using service differentiation, by giving priority to interactive applications' traffic in the network. We study different packet marking schemes and handling mechanisms (packet dropping and scheduling) in the network. For marking packets, two approaches are considered. First, we look into application-based marking, and show how the protection of Telnet traffic against loss can eliminate large echo delays caused by retransmit timeouts, and how, by limiting packet loss for Web page downloads, their delays can be significantly reduced, resulting in enhanced interactivity. Second, we consider differentiation based on TCP state, where we present a marking algorithm that prioritizes packets at the source, based on each connection's window size. In addition, we describe the shaping mechanisms required for conformance to agreements with the network. We show how this marking results in good response times for short transfers, which are characteristic of interactive applications, without significantly affecting longer ones.

We measure and analyze the single-hop packet delay through operational routers in a backbone IP network. First we present our delay measurements through a single router. Then we identify step-by-step the factors contributing to single-hop delay. In addition to packet processing, transmission, and queueing delays, we identify the presence of very large delays due to non-work-conserving router behavior. We use a simple output queue model to separate those delay components. Our step-by-step methodology used to ohtain the pure queueing delay is easily applicable to any single-hop delay measurements. After obtaining the queueing delay, we analyze the tail of its distribution, and find that it is long tailed and fits a Weihull distrihution with the scale parameter, a = 0.5, and the shape parameter, b = 0.58 to 0.6. The measured average queueing delay is larger than predicted by M/M/l, M/G/l, and FBM models when the link utilization is below 70%, but its absolute value is quite small.

In the future, voice communication is expected to migrate from the public switched telephone network (PSTN) to the Internet. Because of the particular characteristics (low volume and burstiness) and stringent delay and loss requirements of voice traffic, it is important to separate voice traffic from other traffic in the network by providing it with a separate queue. In this study, we conduct a thorough assessment of voice delay in this context. We conclude that priority queuing is the most appropriate scheduling scheme for the handling of voice traffic, while preemption of non-voice packets is strongly recommended for sub-10 Mbit/s links. We also find that per-connection custom packetization is in most cases futile, i.e. one packet size allows a good compromise between an adequate end-to-end delay and an efficient bandwidth utilization for voice traffic.

In a near video-on-demand (near-VOD) system, requests for a movie arriving in a period of time are grouped (or "batched") together and served with a single multicast stream. We consider providing near-VOD services when there is a cost associated with using a network multicast channel. We address the tradeoff between system profit, given by the total pay-per-view collected minus the total channel cost, and user delay or user loss (due to reneging). We first analyze and compare the tradeoff of two traditional "basic" schemes, namely, the window-based schemes in which a maximum user delay can be guaranteed, and the batch-size based scheme in which system profit can be guaranteed. By combining these basic schemes, we present a scheme which can adaptively balance system profit and user delay when the underlying request rate fluctuates. We then consider the case in which delayed users may renege and determine how system profit can be maximized by sizing the batching period given user's reneging behavior. We show that maximizing profit can lead to excessively high user loss rate, especially when the channel cost is high and users are not very patient. Therefore, a shorter suboptimal batching period should be used for this case in reality. We finally introduce schemes which are able to offer high profit or low user loss when the underlying arrival rate fluctuates.

In an on-demand video system, the video repository generally has limited streaming capacities and may be far from the users. In order to achieve higher user capacity and lower network transmission cost, distributed servers architecture can be used, in which multiple local servers are placed close to user pools and, according to their local demands, dynamically cache the contents streamed from the repository. We study a number of caching schemes as applied in the local servers depending on whether the repository is able to multicast movie contents to the local servers or not, and whether the local servers can exchange their cached contents among themselves or not. Our caching schemes keep a circular buffer of data for the movie requested, and hence movies are partially cached. By adjusting the size of the buffer, such caching is able to achieve better tradeoff between network channels and local storage as compared to the traditional caching in which a movie is treated as an entity. For each caching scheme, we study the tradeoff between the local storage and the network channels, and address how the total cost of the system can be minimized by appropriately sizing the buffer. As compared to a number of traditional operations (request batching and multicasting, true-VOD, etc.), we show that distributed servers architecture is able to achieve much lower system cost to offer on-demand video services.

A buffer management scheme destined to be deployed in Internet routers should provide an adequate handling of all traffic types, including UDP and TCP traffic as well as fairness among competing flows. In core routers, keeping per-flow state and taking per-flow actions is strongly discouraged, because of the scalability issues that ensue. Consequently, core-stateless fair queuing (CSFQ) adopts a distributed architecture, and uses rate information to provide fairness in core routers. However, we show that CSFQ is sensitive to the setting of its parameters and often leads to a reduction in aggregate throughput. We present rate and queue controlled random drop (RQRD), a buffer management scheme which is based on CSFQ's distributed architecture, but adds queue size information, as in RED, and provides two drop precedences to achieve all the objectives above. We show that RQRD provides an adequate service in the context of both the present and the future Internet.

In today's Internet, various traffic types having different characteristics and requirements (e.g., voice, video, best effort) share the same resources. In order to provide services that an appropriate to each, both the IETF and IEEE 802 have proposed a support for traffic differentiation. In both cases, service classes corresponding to separate queues an identified, and packets an marked according to their class, which in turn defines the treatment they will get at each hop in the network. Using realistic models to represent each of the various traffic types, we identify those that can be mixed in the same queue without bearing a significant loss in throughput; correspondingly, we make recommendations on how to map different traffic types to the available service classes.

In near video-on-demand, requests for the same movie arriving within a period of time are grouped together (i.e., batched) and served with a single multicast stream; thereby reducing the bandwidth requirement compared with the unbatched case. We consider here that the use of a multicast channel comes with a cost. Since delayed users may cancel their requests while being batched, this uncollected revenue has to be appropriately balanced with the channel usage cost in order to achieve maximum profit. We address profit issues for a number of batching schemes. In the window-based schemes, users are batched for a fixed period of time before they are served; in the batch-size based scheme, users are served once a certain number of them are collected. We study the system profit in terms of user reneging behavior, movie popularity, and multicast channel cost. By combining the advantages of the window-based and the batch-size based schemes, we introduce a scheme which adapts to the fluctuating request rate to achieve high profit.

In an on-demand video system, the repository servers storing all the video contents generally have limited streaming capacities and may not be co-located with the users. To achieve higher user capacity and lower network transmission cost, the distributed servers architecture can be used. In such a system, multiple local servers are placed close to the user pools and, according to their local demands, the servers dynamically cache the contents streamed from the repository. We study in this paper a number of caching schemes by considering whether the local servers can exchange their cached contents among themselves or not. All the caching schemes keep a sliding window worth of data for each video being displayed; hence a video can be partially stored. We study the trade-off between the storage capacity required and the network channel used in each scheme, and address how the system cost can be minimised by appropriately sizing the window. We also show the cost advantage in using such a system over a system of request batching and multicasting in providing distributed video services.

In an on-demand video system, requests for a video file arriving within a period of time can be batched together and served with a single multicast stream; thereby reducing the bandwidth requirement compared with the unbatched case. We study various batching schemes to meet delay and profitability requirements-in the window-size based and moving-average schemes, maximum and average user delay respectively are guaranteed; in the batch-size based scheme, minimal profitability is maintained; in the adaptive scheme, both the delay and profitability can be balanced. We analyse and compare these schemes in terms of the delay experienced by the users, and their profitability (the number of users in a batch, the number of concurrent streams, etc.).

In this paper, we present the performance of asynchronous transfer mode (ATM) networks supporting audio/video traffic. The performance evaluation is done by means of a computer simulation model driven by real video traffic generated by encoding video sequences. We examine the glitching that occurs when the video information is not delivered on time at the receiver; we characterize various glitching quantities, such as the glitch duration, total number of macroblocks unavailable per glitch, and the maximum unavailable area per glitch. For various types of video contents, we compare the maximum number of constant bit-rate (CBR) and constant-quality variable bit-rate (CQ-VBR) video streams that can be supported by the network while meeting the same end-to-end delay constraint, the same level of encoded video quality, and the same glitch rate constraint. We show that when the video content is highly variable, many more CQ-VBR streams than CBR streams can be supported under given quality and delay constraints, while for relatively uniform video contents (as in a videoconferencing session), the number of CBR and CQ-VBR streams supportable is about the same. We also compare the results with those obtained for a 100Base-T Ethernet segment. We then consider heterogeneous traffic scenarios, and show that when video streams with different content, encoding scheme, and encoder control schemes are mixed, the results are at intermediate points compared to the homogeneous cases, and the maximum number of supportable streams of a given type can be determined in the presence of other types of video traffic by considering an "effective bandwidth" for each of the stream types. We consider multihop ATM network scenarios as well, and show that the number of video streams that can be supported on a given network node is very weakly dependent on the number of hops that the video streams traverse. Finally, we also consider scenarios with mixtures of video streams and bursty traffic, and determine the effect of bursty traffic load and burst size on the video performance.

The performance of 10Base-T and 100Base-T Ethernet segments carrying audio/video traffic is presented. End-to-end delay requirements suitable for a wide range of multimedia applications are considered (ranging from 20-500 ms). Given the specific nature of the network considered and the maximum latency requirement, some data is lost. Data loss at the receiver causes quality degradations in the displayed video in the form of discontinuities, referred to as glitches. We define various quantities characterizing the glitches, namely, the total amount of information lost in glitches, their duration, and the rate at which glitches occur. We study these quantities for various network and traffic scenarios, using a computer simulation model driven by real video traffic generated by encoding video sequences. We also determine the maximum number of video streams that can be supported for given maximum delay requirement and glitch rate. We consider various types of video contents (video conferencing, motion pictures, commercials), two encoding schemes (H.261 and MPEG-1), and two encoder control schemes [constant bit rate (CBR) and constant-quality variable bit rate (CQ-VBR)] and compare their results. Furthermore, we consider scenarios with mixtures of video and data traffic (with various degrees of burstiness), and determine the effect of one traffic type over the other.

Applications with diverse performance objectives must be supported on a single packet-switched network. The efficiency of such networks can be greatly improved through the use of sophisticated scheduling and dropping algorithms within the queues that form at the network access points and in switches throughout the network. In the present approach, arbitrary performance objectives are expressed in the form of cost functions, which map the queueing delay experienced by each packet to a cost incurred. The heuristic algorithms, cost-based scheduling (CBS) and cost-based dropping (CBD), then attempt to optimize network performance as perceived by the applications by minimizing the total cost incurred by all packets. Appropriate cost functions are presented for common applications. Scheduling and dropping algorithms are defined from these cost functions. It is demonstrated that network performance is better when these algorithms are used as opposed to the common alternatives. Also, contrary to conventional wisdom, some evidence is presented indicating that sophisticated scheduling may be preferable to sophisticated dropping as a means of adjusting loss rates.

Multimedia applications integrate a variety of media, namely, audio, video, images, graphics, text, and data. These media have different bandwidth, delay, and loss requirements. Data traffic is predominantly bursty and it requires reliable service from the network, but it can tolerate delay. In contrast, audio and video traffic is stream-oriented, it can tolerate some loss of data, but it requires delivery within a bounded delay. To support multimedia communications, it is desirable to use existing network infrastructures, which are designed specifically for data applications. In such existing network infrastructures, Ethernet is the most popular LAN scheme used. The authors have simulated 10Base-T and 100Base-T Ethernet segments carrying constant bit rate audio/video streams and data traffic (bursty and non-bursty). Given the stream rate, stream delay and loss constraints, as well as the date load and burst size, they have determined the number of streams supportable.>

The authors show that the problem of optimally routing multicast streams can be formulated as an integer programming problem. They propose an efficient solution technique, composed of two parts: (i) an extension to the decomposition principle, to speed up the linear relaxation of the problem, and (ii) enhanced value-fixing rules, to prune the search space for the integer problem. They characterize the reduction in run time gained using these techniques. Finally, they compare the run times for the optimum multicast routing algorithm and for existing heuristic algorithms.>

The demand for integrated services local area networks is increasing at a rapid pace with the advent of many new and exciting applications: office and factory automation, distributed computing, and multimedia communications. To support these new applications, it is imperative to integrate traffic with diverse statistical characteristics and differing delay requirements on the same network. An attractive approach for integrating traffic has been adopted in two token passing local area network standards, the IEEE 802.4 token bus standard and FDDI. The idea is to control the transmissions of each station based on a distributed timing algorithm, so as to achieve the following goals: (i) to limit the token cycles so that time-critical traffic can be accommodated, and (ii) to allocate pre-specified bandwidths to different stations when the network is overloaded. We have investigated the analysis and design of this protocol previously (see Pang and Tobagi, 1989). In this paper, we generalize the transmission control algorithm used with that protocol. The major advantages of the generalization over the original protocol are: (i) it provides a much expanded design space, (ii) it guarantees convergent behavior, and (iii) it gives meaningful insights into the dynamics of the basic control algorithm.>

The paper analyzes the fault tolerance of a class of double-loop networks referred to as forward-loop backward-hop (FLBH), in which each node is connected via unidirectional links to the node one hop in front of it and to the node S hops in back of it for some S. A new measure of fault tolerance is described, along with techniques based on Markov chains to calculate upper and lower bounds on the fault tolerance of this network topology quickly and efficiently. The results of these calculations provide a more precise description of network fault tolerance than has been achieved with previously published techniques.>

The characteristics of digital video files and traffic differ substantially from those encountered with data applications: (i) video files are much larger than data files, and (ii) video traffic is continuous in nature while data traffic is bursty, with the data rate of a video stream much higher than the mean rate of a data traffic source.Accordingly, conventional file servers and associated storage systems are not well suited to support video services over local area networks; instead, new servers capable of handling the specific characteristics of video files and traffic are needed.In this paper, we describe a video applications server software called StarWorks ™ , focusing primarily on its underlying storage management system.The latter manages an array of Winchester disks, and uses a disk access algorithm particularly suitable for video streaming, and is thus referred to as "Streaming RAID".We also characterize the performance of the system by determining the number of streams that can be supported for a given memory size and a given start-up latency requirement.

The authors propose a burst level bandwidth reservation scheme which is appropriate for an asynchronous transfer mode (ATM) network that supports the transfer of high-speed burst traffic. The proposed scheme utilizes multiple links and multiple paths in a network to transfer individual bursts, thereby increasing network efficiency. As the link and path selection is implemented on a burst-by-burst basis, instead of the cell-by-cell basis used in the conventional multilink approach, the proposed scheme does not require a cell-by-cell distributor and out-of-order cell delivery is avoided, which was the disadvantage of the conventional cell-by-cell multilink approach. Performance evaluation showed that the delay and blocking probability characteristics are greatly improved, as the number of links between each pair of adjacent nodes and the number of source-destination paths increase. For example, around 40% link utilizations are achieved with 16 multiple links, while the conventional single-link schemes yield only to 1% link utilization to guarantee the same quality requirements. It is shown that the proposed scheme works well if the round-trip propagation delay is less than about 10% of the burst duration.>

H. Masuyama and T. Ichimori (see IEEE Trans. Comput., vol.38, no.5, p.738-41, 1989) quantitatively evaluated the ability of a class of double-loop networks called forward-loop-backward-hop (FLBH) networks to tolerate node failures. Their approach was based on the enumeration of all possible sets of failures. The authors prove that their results are incorrect and demonstrate that it is difficult to solve this problem using an approach based on the enumeration of failure sets, suggesting that other approaches may be preferable.>

Heuristic scheduling and dropping algorithms are presented for improving the efficiency of single packet-switched networks with diverse traffic. In the authors approach, arbitrary performance objectives are defined in the form of cost functions, which map the queueing delay experienced by each packet to a cost incurred. The algorithms, cost-based scheduling (CBS) and cost-based dropping (CBD), then attempt to optimize network performance as perceived by the applications by minimizing the total cost incurred by all packets. Cost functions are presented that are appropriate for the most common applications. Scheduling and dropping algorithms are defined based on these cost functions. It is demonstrated that network performance is better when these heuristic algorithms are used as opposed to the common alternatives. The relative importance of scheduling and dropping is also considered.>

A new space-division switch architecture based on Banyan interconnection networks, called the Tandem Banyan Switching Fabric, is introduced. It consists of placing Banyan networks in tandem, offering multiple paths from each input to each output, thus overcoming in a very simple way the effect of blocking encountered in Banyan networks and achieving output buffering. The simplicity of the architecture stems from the fact that it consists of several instances of only two chips, one implementing the Banyan network and the other implementing the output buffer function.>

A self-routing space-division fast packet switch architecture is proposed which achieves output queuing with a reduced number of internal paths (O(N)). The switch architecture is a multi-level binary tree in which each branch constitutes a group of paths that are shared by all the packets destined to a subset of output ports. The reduction in the number of internal paths is obtained by interleaving the packet distribution and packet concentration functions throughout the switch fabric. Packet loss may occur at each level of the tree and is dependent on the degree of concentration exercised at that level. Owing to the binary tree structure of the switching fabric, a simple mathematical analysis is performed in order to determine the concentration parameters appropriate for each level. Several implementation architectures based on sorting networks are described.>

The authors propose a new space-division fast packet switch architecture based on banyan interconnection networks, called the tandem banyan switching fabric (TBSF). It consists of placing banyan networks in tandem, offering multiple paths from each input to each output, thus overcoming in a very simple way the effect of conflicts among packets (to which banyan networks are prone) and achieving output buffering. From a hardware implementation perspective, this architecture is simple in that it consists of several instances of only two VLSI chips, one implementing the banyan network and the other implementing the output buffer function. The basic structure and operation of the tandem banyan switching fabric are described, and its performance is discussed. The authors propose a modification to the basic structure which decreases the hardware complexity of the switch while maintaining its performance. An implementation of the banyan network using a high-performance BiCMOS sea-of-gates on 0.8- mu m technology is reported.>

An analysis is made of the fault tolerance of a class of double-loop networks referred to as forward-loop backward-hop (FLBH) networks, in which each node is connected by unidirectional links to the node one hop in front of it and to the node S hops in back of it for some S. A measure of fault tolerance is described along with techniques based on Markov chains to calculate quickly and efficiently the upper and lower bounds on the fault tolerance of this network topology. The results of the calculations provide a more precise description of network fault tolerance than has been achieved with previously published techniques. >

Background information on networking and switching is provided, and the various architectures that have been considered for fast packet switches are described. The focus is solely on switches designed to be implemented electronically. A set of definitions and a brief description of the functionality required of fast packet switches are given. Three basic types of packet switches are identified: the shared-memory, shared-medium, and space-division types. Each of these is described, and examples are given.>

A very large class of access control strategies is proposed and studied for token passing systems, generalized from the timer-based approach. The idea is to assign transmission quotas dependent on past service times to control the token cycles dynamically while utilizing the token channel efficiently. The dynamics inherent in the control scheme are identified as an important issue and, under heavy load and a few other assumptions, it is shown that the proposed strategies have stable dynamics. Furthermore, the ability of the proposed strategies to control the token cycles is demonstrated. Theoretical results are derived, followed by a thorough discussion on the crucial properties of the new strategies.>

Using simulation, a network-independent framework compares the performance of contention-based Ethernet and two contention-free round-robin schemes, namely Expressnet and the IEEE 802.4 token bus. Two priority mechanisms for voice/data traffic on round-robin networks are studied: the alternating-rounds mechanism of the Expressnet, and the token rotation timer mechanism of the token bus, which restricts access rights based on the time taken for a token to make one round. It is shown that the deterministic schemes almost always perform better than the contention-based scheme. Design issues such as the choice of minimum voice packet length, priority parameters, and voice encoding rate are investigated. An important aspect that is noted is the accurate characterization of performance over a wide region of the design space of voice/data networks.>

An analysis is presented of the throughput performance of some recently proposed token-passing local area network (LAN) protocols under a heavy load assumption. The IEEE 802.4 token bus standard which uses a cycle-dependent timing mechanism to control station access to the channel, is studied. It is shown that the cycle-dependent timing mechanism limits the token circulation times properly. Moreover, priority among different access classes is being implemented. Analytic results for computations of throughputs and cycle lengths are derived. These results provide insights into the cycle-dependent timing mechanism and also guidelines for design. Using the results derived, examples concerning the throughput behavior under different heavy load configurations, the sensitivity to parameters, system optimization with delay and bandwidth constraints, and comparison with the other integrated access schemes are studied.>

A spread-spectrum multiple-access (SSMA) packet radio network model is presented. The topology is a fully connected network with identical message generation processes at all radios. Packet lengths are exponentially distributed, and packets are generated from a Poisson process, resulting in a Markovian model. This network model accounts for the availability of idle receivers in a finite population network. The model also allows the performance of the radio channel to be specified in detail. The channel considered is a BPSK (binary phase-shift keying) direct-sequence SSMA radio channel with hard-decision Viterbi decoding. An analysis of the Viterbi decoder leads to a bound on its performance which is valid for a system with a varying probability of error, as is the case for the network under consideration. The approximate analysis yields lower bounds on throughput and probability of successful packet transmission. Results are given which show the effects on throughput of the received energy-to-noise density ratio, the number of chips per symbol, and the number of radios, as well as the improvement due to error control coding.>

The author presents the topological design space of single-hop interconnection among multitransceiver stations (no intermediate switches and no forwarding). They explore a class of such interconnections for which the throughput with a uniform traffic pattern is proportional to the square of the number of transceivers per station. These interconnections consist of a collection of buses, each of which interconnects a proper subset of the stations, and are referred to as selective-broadcast interconnections. They are compared with a multiple-broadcast-bus interconnection in terms of station hardware, throughput, delay, and power budget.>

To support real-time applications on a local area network, some recently proposed standards, such as the IEEE 802.4 token bus standard and FDDI, use timers to control station access of the channel in addition to a basic token-passing protocol. The major reason for incorporating the timing mechanism is to avoid excessively long cycles in token-passing that can disrupt real-time services for packetized voice and real-time control. Nevertheless, the timing mechanism is flexible enough to provide priority among non-real-time traffic as well. The authors present an analysis of the throughput performance of the timer-controlled token-passing protocol under heavy load and a few other assumptions. The analysis not only reveals the priority structure of the protocol but also some salient features that render the protocol more favorable than other cycle-limiting schemes (e.g., fixed-maximum channel access per cycle).>

A simulation study is presented in several distributions of stations on a linear-bus Ethernet. Aggregate performance is shown to depend on the distribution of stations. Individual station performance varies with the location of the station. Unbalanced distributions can lead to large performance differences between individual stations, with isolated stations achieving relatively poor performance compared to the average. The effects of access protocol parameters such as the number of buffers per station and the retransmission algorithm are examined. A modification of the standard retransmission algorithm is presented that enables a higher throughput to be achieved at high load. The results are compared to the predictions of theoretical models, and the applicability of the models to finite-population Ethernets is examined.>

In the past few years, local area networks have come into widespread use for the interconnection of computers. Together with the trend towards digital transmission in voice telephony, this has spurred interest in integrated voice/data networks. The Expressnet, an implicit-token round-robin scheme using unidirectional busses, achieves high performance even at bandwidths of 100 Mb/s. Other features that make the protocol attractive for voice/data traffic are bounded delays and priorities. The latter is achieved by devoting alternate rounds to one or the other of the two traffic types. By the use of accurate simulation, the performance of the Expressnet with voice/data traffic is characterized. It is shown that the Expressnet satisfies the real-time constraints of voice traffic adequately even at bandwidths of 100 Mb/s. Data traffic is able to effectively utilize bandwidth unused by voice traffic. The trade-offs in the alternating round priority mechanism are quantified. Loss of voice samples under overload is shown to occur regularly in small, frequent clips, subjectively preferable to irregular clips. In a comparison of the Expressnet, the contention-based Ethernet and the round-robin Token Bus protocols, the two round-robin protocols are found to perform better than the Ethernet under heavy load owing to the more deterministic mode of operation. The comparison of the two round-robin protocols highlights the importance of minimizing scheduling overhead at high bandwidths.

Provides an overview of the technical articles and features presented in this issue.

There are many design choices that must be made in the development of a packet radio network. There is usually no single correct choice, and the decisions are dependent on the environment that the network must work in, the requirements for performance and other functionalities, and the cost and other limitations, in addition, as new hardware and software technologies become available, the parameters governing the decisions change and often result in different selections. This paper outlines a number of design issues and choices available. The intent is to provide an overview of the design decisions that must be made so as to provide a context for the decisions made in a number of existing and developing packet radio networks. It is hoped that this will allow future designs to take advantage of both the wealth of experience available as well as new technologies. Three areas of design decisions are identified. The first area deals with the physical aspects of the network and concentrates on the radio connectivity and channel sharing. The second area deals with the automated management of the network and concentrates on issues such as link management and routing. The third area deals with the interface of the network to the users and some practical aspects of operating and maintaining a network.

The design of packet radio networks involves a large number of issues which interact in a very complex fashion. Many of these pertain to the RF channel and its use, others pertain to the operational protocols. Clearly, no single model can be formulated which incorporates all the necessary parameters and leads to the optimum solution. The one essential element which complicates matters is that, contrary to point-to-point networks in which each channel is utilized by a single pair of nodes, the radio channel in packet radio networks is a multiaccess broadcast resource: i) in a given locality determined by radio connectivity, the channel is shared by many contending users, hence the need for channel access protocols; ii) radio is a broadcast medium and thus the action taken by a node has an effect on the actions taken by neighboring nodes and their outcome. Despite the complexity of the problem, there has been significant progress worth reporting on. The work accomplished so far has been either the analysis of specific examples of networks or an attempt to create models that would be useful in the design of general networks. The purpose of this paper is to survey the various modeling techniques that have been used for the performance analysis of packet radio networks, and to discuss the assumptions underlying these models, their scope of applicability, and some of the results obtained.

We consider two styles of executing a single job or an algorithm: either the job is subdivided into tasks, each of which is executed. on a separate processor, or the entire job is executed on a single processor, that has the same capacity as the sum of the processors in the earlier case. The algorithm is abstracted as consisting of a number of tasks with dependencies among them. Our model of dependencies among tasks allows sequential execution, parallel execution, synchronization, and spawning of tasks. The model assumes that the dependencies are known before the job begins, and a task in not preempted after its execution begins. With the usual assumptions such as exponential distribution of task execution times, and Poisson arrival of input data, we are able to show that the centralized execution completes the job faster than the decentralized execution only for a certain range of parameters of algorithms. We also give counterexamples that show that, contrary to popular belief, the reverse is true for some values of parameters of algorithms.

In this paper, we propose a combined voice/data protocol suitable for multiple access broadcast networks that provide round robin service to the stations. Such networks are well suited to the integration of voice and data since they guarantee bounded delay and provide high utilization even for high bandwidth channels. Using one such network proposal-namely Expressnet-as a representative scheme, we examine the characteristics of the service that voice traffic experiences under the voice/data protocol. We show that the access protocol is able to utilize the channel efficiently to support a large population of voice sources while maintaining low packet delay and guaranteeing some prespecified minimum bandwidth for data traffic. In addition, we show the advantages of silence suppression, i.e., discarding speech that constitutes silent periods, and we examine the cost of overloading the network in terms of the amount of speech discarded.

A number of fiber optic configurations for a new class of demand assignment multiple-access local area networks requiring a physical ordering among stations are proposed. In such networks, the data transmission and linear-ordering functions may be distinguished and be provided by separate data and control subnetworks. The configurations proposed for the data subnetwork are based on the linear, star, and tree topologies. To provide the linear-ordering function, the control subnetwork must always have a linear unidirectional bus structure. Due to the reciprocity and excess loss of optical couplers, the number of stations that can be accommodated on a linear fiber optic bus is severely limited. Two techniques are proposed to overcome this limitation. For each of the data and control subnetwork configurations, the maximum number of stations as a function of the power margin, for both reciprocal and nonreciprocal couplers, is computed.

Local area communications networks based on packet broadcasting techniques provide simple architectures and efficient and flexible operation. Various ring systems and CSMA contention bus systems have been in operation for several years. More recently, a number of distributed demand assignment multiple access (DAMA) schemes suitable for broadcast bus networks have emerged which provide conflict-free broadcast communications by means of various scheduling techniques. Among these schemes, the Token-Passing Bus Access method uses explicit tokens, i.e., control messages, to provide the required scheduling. Others use implicit tokens, whereby stations in the network rely on information deduced from the activity on the bus to schedule their transmissions. In this paper we present many implicit-token DAMA schemes in a unified manner grouped according to their basic access mechanisms, and compare them in terms of performance and other important attributes.

Expressnet is a local area communication network comprising an inbound channel and an outbound channel to which the stations are connected. Stations transmit on the outbound channel and receive on the inbound channel. The inbound channel is connected to the outbound channel so that all signals transmitted on the outbound channel are duplicated on the inbound channel, thus achieving broadcast communication among the stations. In order to transmit on the bus, the stations utilize a distributed access protocol which achieves a conflict-free round-robin scheduling. This protocol is more efficient than existing round-robin Schemes as the time required to switch control from one active user to the next in a round is minimized (on the order of a carrier detection time), and is independent of the end-to-end network propagation delay. This improvement is particularly significant when the channel data rate is so high, or the end-to-end propagation delay is so large, Or the packet size is so small as to render the end-to-end propagation delay a significant fraction of, or larger than, the transmission time of a packet. Moreover, some features of Expressnet make it particularly suitable for voice applications. In view of integrating voice and data, a simple access protocol is described which meets the bandwidth requirement and maximum packet delay constraint for voice communication at all times, while guaranteeing a minimum bandwidth requirement for data traffic. Finally, it is noted that the voice/data access protocol constitutes a highly adaptive allocation scheme of channel bandwidth, which allows data users to recover the bandwidth unused by the voice application. It can be easily extended to accommodate any number of applications, each with its specific requirements.

Local area communication networks based on packet broadcasting techniques provide simple architectures and flexible and efficient operation. Unidirectional broadcast systems use a unidirectional transmission medium which, due to their physical ordering on the medium, users can access according to some efficient distributed conflict-free round-robin algorithm. Two systems of this type have been presented in the literature: Expressnet and Fasnet. In this paper we briefly describe these two. We identify three different service disciplines achievable by these systems and discuss and compare the performance of each. These systems overcome some of the performance limitations of existing random-access schemes, making them particularly well suited to the high bandwidth requirements Of an integrated services digital local network.

Packet communication systems of the multiaccess/broadcast type, in which all communicating devices share a common channel that is multiaecessed in some random fashion, are considered.Among the various muhraecess schemes known, two prominent ones are considered: slotted ALOHA and Carrier Sense Multiple Access (CSMA).Existing analysis of these schemes has led to the determination of the average channel performance m terms of average throughput and average packet delay.This was achieved by formulating Markovian models for these channels with finite populations of users, each with a single packet buffer.Unfortunately, average performance is not adequate when designing communication systems intended for real-tune applicauons, such as digitized speech, or when analyzing multihop packet radio networks, and the analysis has to be extended so as to provide delay distributions.Using the same Markovian models, the distributions of packet delay and interdeparture time for slotted ALOHA and CSMA channels are derived, and expressions for their moments are given.

Among the various random access schemes known, carrier sense multiple access (CSMA) has been shown to be highly efficient for environments where the propagation delay is short compared to the transmission time of a packet on the channel. In this paper, the authors describe a new version of CSMA which incorporates message-based priority functions, referred to as prioritized CSMA (P-CSMA). The scheme is based on the principle that access right to the channel is exclusively granted to ready messages of the current highest priority level. It can be made preemptive or nonpreemptive, and is suitable to fully connected broadcast networks with or without the collision detection feature. They analyze thep-persistent protocol of P-CSMA with two priority levels and derive the throughput-delay characteristics for each priority class. Finally, they discuss numerical results obtained from the analysis and from simulation, and thus evaluate the effect of priority functions and preemption on the throughput-delay characteristics for each class.

The design of packet radio systems involves a large number of design variables that interact in a very complex fashion. As this design problem in its general form is quite complex, a viable approach is to analyze some simple but typical configurations in an attempt to understand the behavior of these systems. In this paper, a two-hop centralized configuration is considered in which traffic originates at terminals, is destined to a central station, and requires for its transport the relaying of packets by store-and-forward repeaters. The through-put-delay performance is derived, and its dependence on such key system variables as the network topology, the transmission protocol, and the repeaters' storage capacities, is given. In this part, devices are assumed to be utilizing the slotted ALOHA access mode. Carrier sense multiple access is treated in Part II of this series [1].

We continue in this paper our study of two-hop centralized packet radio networks in view of understanding the behavior of these systems. Traffic originates at terminals, is destined to a central station, and requires for its transport the relaying of packets by store-and-forward repeaters. We consider here that all devices employ the nonpersistent carrier sense multiple-access mode. System capacity and through-put-delay tradeoffs are derived and compared to those obtained for slotted ALOHA in Part I [l].

The need for multiaccess protocols arises whenever a resource is shared by many independent contending users. Two major factors contribute to such a situation: the need to share expensive resources in order to achieve their efficient utilization, or the need to provide a high degree of connectivity for communication among independent subscribers (or both). In data transmission systems, the communication bandwidth is often the prime resource, and it is with respect to this resource that we view multiaccess protocols here. We give in this paper a unified presentation of the various multiaccess techniques which we group into five categories: 1) fixed assignment techniques, 2) random access techniques, 3) centrally controlled demand assignment techniques, 4) demand assignment techniques with distributed control, and 5) mixed strategies. We discuss their applicability to different enivironments, namely, satellite channels, local area communication networks and multihop store-and-forward broadcast networks, and their applicability to different types of data traffic, namely stream traffic and bursty traffic. We also present the performance of many of the multiaccess protocols in terms of bandwidth utilization and message delay.

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.

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.

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.

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.

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.