In triangulation-based coverage, a group of three mobile sensor nodes (MSNs) position themselves to form an equilateral triangle. A larger area is covered with many such smaller triangles as three MSNs move from one triangle to another. Such a scheme has several applications in localization, 3D imaging and coordinated search operation. In this work, we introduce an efficient mobile traversal algorithm (MTA) that provides a triangulation-based coverage of a field that can be approximated as a rectangle. We analyze the MTA in terms of the MSNs' travel distance and time taken to complete the traversal process. The bounds derived are also useful in determining the amount of energy consumption by the MSNs.

A triangulation-based coverage scheme using mobile sensor nodes (MSNs) has several applications in localization, 3D imaging and coordinated search operation. In this work, we introduce an efficient failure-tolerant mobile traversal algorithm (FTMTA) that provides a triangulation-based coverage of a field. FTMTA employs N MSNs such that, upto N -- 3 node failures can be tolerated to complete the coverage. FTMTA achieves three objectives: (a) as N increases, the total time to cover the field decreases in the absence of a failure; (b) each MSN travels a minimum distance; (c) upon a failure, the remaining MSNs efficiently complete the coverage of the field.

A novel approach to geo-locate sensor-nodes in a Ricean fading environment is presented. For localization, this work considers autocorrelation characteristics of short term fading that are typically averaged out in traditional signal-strength based algorithms. Location attributes of the sensor nodes are determined by minimizing the squared error between the estimated autocorrelation function and its theoretical approximation. The theoretical approximation of the autocorrelation function is derived in closed form from Aulin's three-dimensional channel model. It is shown that despite noisy measurements and weak line-of-sight signal, the proposed method estimates coordinates of sensor nodes within an error of less than plusmn5% for signal-to-noise ratios higher than 20 dB.

This work presents a novel algorithm to improve energy conservation in sensor networks. The algorithm is based upon selective activation of sensor nodes using thresholding (SAT). The sensor continuously monitors the received signal and makes a binary decision to join the network if the average received signal power falls within the specified minimum and maximum threshold range. Thus, SAT divides all the receivers within the coverage range of the transmitter into sets of active and inactive nodes realizing a saving in power consumption proportional to the number of inactive nodes. The sensor life-time is enhanced by allowing the node to transmit at a power that is a constant fraction of the total residual energy. For two cases of linear and hexagonal networks considered in this work, it is shown that for each transmission, the fraction of inactive nodes may exceed by over 30% of the total number of nodes present within maximum one-hop distance of the transmitter. The cost associated with energy conservation through SAT is (a) increased sensor node density or (b) increased transmission power requirement.

This work presents an analytical approach for determining the relative coordinates of a receiver with respect to the source node. The source is assumed to be location aware. Statistics of the received signal are used to estimate the orientation and distance of the receiver with respect to the source. The received signal power is used as a distance estimator and the orientation is determined using the inphase and quadrature components of the received signal. The proposed method is applicable only in presence of line-of-sight path.

In mobile ad hoc networks, one might expect multipath routing to provide some robustness to link failures and facilitate the transmission of packets along paths that avoid regions of congestion. Consequently, one would expect an improvement in network performance in terms of the achieved throughput. We consider TCP goodput as the metric of performance. We find that, contrary to expectations, not all TCP connections enjoy the benefits of multipath routing. Specifically, we find that while long (in terms of hop-count) TCP connections seem to benefit, short connections in fact suffer a slight degradation in goodput as compared to TCP using the single shortest path. Furthermore, we find that alternate path routing, wherein packets are routed on a secondary alternate path only upon the failure of the primary path, helps achieve almost the same goodput as when the multiple paths are used simultaneously. The main benefits of currently proposed multipath routing schemes seem to be limited to improving the efficiency of route discoveries that are initiated either due to real route failures (due to mobility) or due to false failures (due to interference effects) for long TCP connections.

In this work, we study and quantify the effects of hotspots in wireless cellular networks. Hotspots are caused when the bandwidth resources available at some location in the network are not enough to sustain the needs of the users, which are then blocked or dropped. A deeper understanding of hotspots can help in conducting more realistic simulations and enable improved network design. We identify some causes for the formation of hotspots and based on them, categorize hotspots into three different types: a) capacity based, b) delay based, and c) preferential mobility based. We show how these types have different effects on network performance. We also consider the effects of hotspots from various perspectives such as the number of hotspots, the placement of hotspots, etc. We also develop a fluid flow model and an analytical model to study hotspots. The fluid flow model is surprisingly simple yet effective in helping us understand hotspots and their properties. We also describe an analytical model in which we consider a cell as an M/M/B/B queue. We use these models to substantiate some of the observations from the simulations.

In wireless sensor networks, data from sensors has to be transported to a central server or sink. Since the sensors are power-constrained devices, the data is typically fused en route, and an aggregated report of fused information is finally available at the sink. It is important that information from as many sensors as possible be fused in order to increase the credibility of the aggregated report. However, in sensor networks there may be faulty sensors or even malicious intruders that generate and report misleading information. Thus, it is important to collect and fuse enough correct reports that agree with each other; this would enable nodes that perform fusion to detect and ignore the effects of the faulty reports. In this work, we propose a protocol called corroborative aggregation protocol (CAP), in which, each sensor that detects a report from its neighbor that contradicts its own findings generates its own report to dispute the faulty report. The idea is to increase the number of correct reports so as to effectively reduce the adverse effects of faulty reports. We show by simulations that CAP is effective in maintaining the credibility of the final fused content even if approximately 30% of sensors within a detecting zone are wrong about an event.

We focus on self-contention: contention between packets of the same transport layer connection along the path from source to destination. We observe that self-contention plays an important role in degrading TCP performance in multi-hop wireless networks and that the use of the popular IEEE 802.11 MAC protocol exacerbates self-contention. We propose and study two MAC-layer approaches to alleviate self-contention. The first approach, called quick-exchange (QE), is designed with the intent of reducing the effects of inter-flow self-contention (e.g. between packets of the same connection traveling in opposite directions). The design of our second mechanism, called fast-forward (FF), is geared towards decreasing intra-flow self-contention (e.g. between packets of the same connection traveling in the same direction). We simulate and study our proposed schemes and observe that quick-exchange consistently improves net-work aggregate goodput (by as much as 20% in string topologies, 15% in random static scenarios, and 10% in random mobile scenarios). In contrast to our expectations, fast-forward causes sporadic and often negative effects on goodput for TCP connections. Upon investigation we find that while the MAC is, in some respect, operating more efficiently, as demonstrated by improved UDP throughput; interactions with TCPs congestion control mechanism cause the goodput to degrade. We analyze various effects that cause the respective behaviors with QE and FF in detail.

Spatially separating TCP sessions such that they inflict much lower interference effects on each other may provide gains in performance. We first investigate the possibilities of achieving such gains by considering a centralized, ideal, and unrealistic congestion aware routing approach. We then consider the implementation of a distributed routing protocol to achieve the aforementioned spatial separation benefits. We find that due to practicalities such as the need for the exchange of congestion state, the existence of stale congestion information and the creation of sub-optimal paths, the benefits due to spatial separation are considerably undermined. We perform both macroscopic simulations and microscopic studies of specific constructed examples to understand the reasons and quantify the various effects with both the centralized and the distributed approaches. Our studies suggest that achieving noteworthy performance gains by spatially separating TCP sessions may be extremely difficult if not impossible in ad hoc networks.

In wireless sensor networks, in-network data fusion is needed for energy-efficient information flow from a plurality of sensors to a central server or sink. As data (either raw or fused) is propagated towards the sink, multiple levels of data fusion are likely. The data fusion at various levels should be synchronized in order to fuse data effectively. It is important that information from as many sensors as possible to be fused in order to increase the credibility of the aggregated report. However, there are trade-offs between fusing a large number of sensor reports and the latency incurred in the aggregation process. The paths taken by the data towards the sink determine where data can be fused, and thus, have an effect on the efficiency of the aggregation process. In this work, we propose a methodology by which the various levels of fusion are synchronized to ensure that the aggregated report has a desired trade-off between credibility and latency, regardless of the topology of the structure created by the integration of the paths on which data traverses towards the sink.

Mobile ad hoc networks consist of nodes that are often vulnerable to failure. As such, it is important to provide redundancy in terms of providing multiple node-disjoint paths from a source to a destination. We first propose a modified version of the popular AODV protocol that allows us to discover multiple node-disjoint paths from a source to a destination. We find that very few of such paths can be found. Furthermore, as distances between sources and destinations increase, bottlenecks inevitably occur and thus, the possibility of finding multiple paths is considerably reduced. We conclude that it is necessary to place what we call reliable nodes (in terms of both being robust to failure and being secure) in the network for efficient operations. We propose a deployment strategy that determines the positions and the trajectories of these reliable nodes such that we can achieve a framework for reliably routing information. We define a notion of a reliable path which is made up of multiple segments, each of which either entirely consists of reliable nodes, or contains a preset number of multiple paths between the end points of the segment. We show that the probability of establishing a reliable path between a random source and destination pair increases considerably even with a low percentage of reliable nodes when we control their positions and trajectories in accordance with our algorithm.

The fairness and throughput of TCP suffer when it is used in mobile ad hoc networks. This is because TCP wrongly attributes packet losses due to link failures (a consequence of mobility) to congestion. The resulting overall degradation of throughput especially affects connections with a large number of hops, where link failures are more likely; thus, short connections enjoy an unfair advantage. Furthermore, if the IEEE 802.11 MAC protocol is used, the problems are exacerbated due to the protocol-induced capture effect, leading to greater unfairness and a further throughput degradation. We develop a scheme, called split TCP, which separates the TCP functions of congestion control and reliable packet delivery. For any TCP connection, certain nodes along the route take up the role of being proxies for that connection. The proxies buffer packets upon receipt and administer rate control. The buffering enables dropped packets to be recovered from the most recent proxy. The rate control helps in controlling congestion on inter-proxy segments. Thus, we emulate shorter TCP connections and can thereby achieve better parallelism in the network. Simulations show that the use of proxies improves the total throughput by as much as 30% in typical scenarios and reduces unfairness significantly. In terms of an unfairness metric that we introduce, the unfairness decreases from 0.8 to 0.2 (1.0 being the maximum unfairness). We conclude that incorporating TCP proxies is beneficial in terms of improving TCP performance in ad hoc networks.

Most of the QoS routing research in the literature attempts to increase the performance of QoS traffic without explicitly considering the performance of the best-effort traffic in the network. However, although the trend in the development and use of real-time multimedia applications is on the rise, traditional data applications are still expected to be a dominant percentage of the Internet traffic. Developing routing schemes for best-effort traffic when it coexists with QoS traffic to provide an acceptable performance to the best-effort traffic is thus critical. In this paper we study the effectiveness of the link utilization metric for routing best-effort traffic in a network that supports both QoS as well as best-effort traffic. The main contribution of this paper lies in demonstrating the feasibility of using the link utilization metric and quantifying the improvement in performance so obtained under various distributions of network load. Our results indicate that utilization based routing of best-effort traffic dynamically adapts to the distribution of the QoS traffic in the network, and demonstrates a significant improvement in the performance of best-effort traffic, when compared to the performance obtained by routing best-effort traffic using the static hop count metric.

Abstract We examine the extent to which statistical mobility information can increase the reliability of the service experienced by users in mobile networks. Interrupted or dropped calls are an aspect of reliability that stems from the mobility of users. An existing user can move to a cell where there are no resources available to support their call. A natural solution is the reservation of resources in multiple cells that the user is likely to move to. This scheme is calledselective reservationsand it relies on predicting the next move of the user. Recently, there has been some work on estimating the movement probabilities (also known as themobility profile) of the user. In this paper, we quantify the usefulness of the mobility profile to improve the reliability of the service perceived by the mobile users. We identify two parameters which characterize the profile:Accuracy and Focus. Accuracy expresses the probability that the host will move as we expect it to. Focus describes how well we can identify patterns in the movement of the users. In our simulations, we examine the effect of the quality of the predictions on the performance of the system. We show that Accuracy and Focus have great impact on the performance of selective reservations. We also show how flexibility in hand‐offs can help in decreasing the dropping probability, and how this can be facilitated by letting the users make a second try at moving in case it fails the first time. Copyright © 2001 John Wiley & Sons, Ltd.

We propose a methodology to simplify the analysis of wireless network simulations. Wireless simulation models are plagued by a vast parameter space. Consequently, performance studies are not easy to interpret or compare across different models. We reduce this parameter space by proposing a set of parameters that describe the network at a higher level of abstraction.

Performance analysis of concurrent executions in parallel systems has been recognized as a challenging problem. The aim of this research is to study approximate but efficient solution techniques for this problem. We model the structure of a parallel machine and the structure of the jobs executing on such a system. We investigate rich classes of jobs, which can be expressed by series, parallel-and, parallel-or, and probabilistic-fork. We propose an efficient performance prediction method for these classes of jobs running on a parallel environment which is modeled by a standard queueing network model. The proposed prediction method is computationally efficient, it has polynomial complexity in both time and space. The time complexity is O(C/sup 2/N/sup 2/K) and the space complexity is O(C/sup 2/N/sup 2/K), where C is the number of job classes in the system, the number of tasks in each job class is O(N), and K is the number of service centers in the queueing model. The accuracy of the approximate solution is validated via simulation.

A number of QoS routing algorithms have been proposed to address the dual objective of selecting feasible paths through the network with enough resources to satisfy a connections' QoS request, while simultaneously utilizing network resources efficiently. However, these routing algorithms and the guarantees they provide do not consider the possibility of node and link failures. The failure of a node or a link along a path can disrupt the continuity of an on-going session and potentially terminate the session. Hence the problem of QoS routing should be extended to incorporate reliability and fault-tolerance requirements. We study the impact of unreliable nodes on QoS routing. We describe a scheme to restore the flows that are disrupted due to node failures to alternate paths. Two prioritized restoration policies, one to maximize the number of disrupted flows that can be restored, and the other to maximize the disrupted demand that can be restored are also presented. We conduct extensive simulations to evaluate the routing performance in the presence of node failures and repairs, as well as the performance of the restoration scheme. Our results indicate: (i) when the availability of the nodes is beyond a certain threshold, the routing as well as the restoration performance is comparable where the number of failures in one is twice the number of failures in the other; (ii) the percentage of the disrupted flows and the percentage of the disrupted demand that can be restored successfully increase with decreasing network load; and (iii) prioritized restoration policies are effective under heavy network load conditions, and their effectiveness decreases with decreasing network load.

Palmtop computers are rapidly becoming the popular platform of choice for running personal productivity applications, but their networking capabilities are still lagging behind user expectations.Due to memory size, cost, and power considerations most palmtop computers support only limited form of point-to-point communication, namely, connection via a PSTN modem or a serial RS-232 cable.Due to wired point-to-point nature of these interfaces, satisfactory solutions for multi-point communication and direct LAN connection do not yet exist..The BlueSky project aims at providing a low-cost, lowpower, indoor RF wireless networking solution for handheld devices.Our solution consists of two components; a BlueSky wireless attachment that plugs into the standard serial port of any palmtop device, and a LAN access point that acts as a layer 213 bridge between the wireless and the wired part of the network.Palmtop devices use dialup networking software and PPP to connect via BlueSky to the network.BlueSky enables MobileIP style seamless roaming between access points without requiring any changes to the communication stack of plamtop devices.Our roaming enhancements to PPP are implemented in the PPP server, the access point, and the BlueSky attachment, all of which are completely transparent to the palmtop device.In this paper, we present our design rationale and implementation experience of building the BlueSky system.We show in what ways low cost, low power, and form factor constraints affect the choice of protocols and function placement in wireless networking systems.We use PPP based mobility solution as an example to illustrate what design adjustments and compromises one has to make to build a working solution.Based on our experience, we recommend making a slight modification to the dialup networking stack of palmtop computers.Our proposed modification offers an efficient, lower cost, and lighter-weight wireless networking solution which is particularly attractive for enabling mobility over emerging short range, low power wireless technologies, such as IrDA, HomeRF and Bluetooth.Permission Lo make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the tirst page.To copy otherWe, to republish, to post on servers or to redistribute to lists.rcquircs prior specific permission and/or a fee.

Maximizing bandwidth efficiency in dist,ributed continuous media streaming systems is the key in delivering cost-effective mult,imedia services to distributed and heterogeneous receivers.We introduce a technique based on stream multiplexing to achieve the highest possible bandwidth efficiency, while preserving stringent and deterministic quality of service guarantees.The technique accomplishes the optimal multiplexing (i.e.resulting in the lowest possible bandwidth allocation) by exploiting both the temporal and the spatial structures among a group of continuous media streams.We present a family of optimal multiplexing schedules.The adverse per-stream effects of optimal multiplexing are studied and a technique based on t,ransmission rearrangement is proposed to mitigates these effects, without sacrificing the achieved mult,iplexing optimahty.The results presented in the paper provide some fundament#al criteria and limits in the design a.nd evaluation of resource alloca.tion,admission control and &ream scheduling policies for bandwidth efficient continuous media streaming.

Quality of service (QoS) routing algorithms have become the focus of research due to their potential for increasing the utilization of an integrated services packet network (ISPN) serving requests with QoS requirements. While heuristics for determining paths for such requests have been formulated for a variety of QoS models, little attention has been given to the overall processing complexity of the QoS routing protocol. Although on-demand path computation is very attractive due to its simplicity, many believe that its processing cost will be prohibitive in environments with high request rates. We study alternatives to on-demand path computation that can reduce this processing overhead. In addition to the well known solution of path pre-computation we introduce and study path caching, an incremental modification of on-demand path computation. The simulation results show that caching is an effective alternative to path pre-computation and that both path caching and pre-computation can achieve significant processing cost savings without severely compromising the routing performance.

Unlike wired links, wireless network bandwidth is highly limited and the channel usually suffers from frequent and bursty loss due to its vulnerability to various kinds of interference. At the same time, the traditional TCP with its congestion control is well known for its poor performance over wireless links. This paper proposes a new protocol that (1) replaces TCP/IP over the wireless link by a simpler protocol with smaller headers, if the link is the last hop along a data path, (2) shifts functions needed to communicate with an Internet host using TCP/IP from the mobile host to the base station, so that the distinct wireless link is hidden from the outside Internet, and (3) exploits link-layer acknowledgments and retransmissions to quickly recover losses over the wireless link. Our simulation results show a substantial performance improvement achieved by the new protocol.

Quality of service (QoS) routing algorithms have become the focus of recent research due to their potential for increasing the utilization of an integrated services packet network (ISPN) that handles requests with QoS requirements. While heuristics for determining paths for such requests have been formulated for a variety of QoS models, little attention has been given to the overall processing complexity of the QoS routing architecture. Although on demand path computation is very attractive due to its simplicity, many believe that its processing cost will be prohibitive in environments with high request rates. In this work, we first characterize the processing cost of QoS routing algorithms that use the constrained widest-shortest path heuristic to compute QoS paths in a link state based routing environment. By simulating a variety of realistic traffic conditions we investigate the effectiveness of path pre-computation in reducing the amount of routing protocol computation. We mainly want to determine how much reduction in routing processing cost is possible before the routing performance becomes unacceptably low. Our results show that path pre-computation can significantly reduce the processing cost of on-demand path computation but with a proportional routing performance loss.

This work presents a new I/O system design and implementation targeted at applications that perform data streaming. The approach yields true zero-copy transfers between I/O devices in many instances. We give a general characterization of I/O elements and provide a framework that allows analysis of the potential for zero-copy transfers. Finally, we describe the design, implementation, and performance of a prototype I/O system in a real time, embeddable, 32-bit operating system whose design is based on the presented analysis to minimize data copying.

Recent studies provide evidence that Quality of Service (QoS) routing can provide increased network utilization compared to routing that is not sensitive to QoS requirements of traffic. However, there are still strong concerns about the increased cost of QoS routing, both in terms of more complex and frequent computations and increased routing protocol overhead. The main goals of this paper are to study these two cost components, and propose solutions that achieve good routing performance with reduced processing cost. First, we identify the parameters that determine the protocol traffic overhead, namely (a) policy for triggering updates, (b) sensitivity of this policy, and (c) clamp down timers that limit the rate of updates. Using simulation, we study the relative significance of these factors and investigate the relationship between routing performance and the amount of update traffic. In addition, we explore a range of design options to reduce the processing cost of QoS routing algorithms, and study their effect on routing performance. Based on the conclusions of these studies, we develop extensions to the basic QoS routing, that can achieve good routing performance with limited update generation rates. The paper also addresses the impact on the results of a number of secondary factors such as topology, high level admission control, and characteristics of network traffic.

We propose a simple mechanism named carry-over round robin (CORR) for scheduling cells in asynchronous transfer mode networks. We quantify the operational complexity of CORR scheduling and show that it is comparable to that of a simple round-robin scheduler. We then show that, albeit its simplicity, CORR is very competitive with much more sophisticated and significantly more complex scheduling disciplines in terms of performance. We evaluate the performance of CORR using both analysis and simulation, We derive analytical bounds on the worst case end-to-end delay achieved by a CORR scheduler for different traffic arrival patterns. Using traffic traces from MPEG video streams, we compare the delay performance of CORR with that of packet-by-packet generalized processor sharing (PGPS) and stop-and-go (SG). Our results show that, in terms of delay performance, CORR compares favorably with both PGPS and SG. We also analyze the fairness properties of CORR and show that it achieves near perfect fairness.

We present efficient scheduling schemes for transporting archived MPEG-coded video over a constant-bit-rate (CBR) channel. A video source is characterized by a time-varying traffic envelope, which constitutes an upper bound on the actual bit rate. To provide a relatively tight bound, window-based envelopes are used in which the bound is based on fixed-length segments of the movie. Using such envelopes, we show that video streams can be scheduled for transmission over the network such that the per-stream allocated bandwidth is significantly less than the source peak rate. In certain cases, a reduction of up to 85% of the source peak rate was achieved. Bandwidth gain is obtained via statistical multiplexing, while providing stringent, deterministic quality of service. Online procedures for bandwidth computation and admission control under the examined scheduling schemes are presented.

A critical functional component of quality-of-service (QoS) deployment in packet-switched networks is QoS-based routing. In this paper, we present a routing solution for guaranteed quality-of-service connections in integrated services packet networks (ISPN)-the future QoS-capable Internet proposed by the IETF. The problem is in essence a path finding problem with both end-to-end delay and per-node buffer constraints, in networks with heterogeneous intermediate switching nodes. We present a polynomial time algorithm using a capacity plane decomposition technique combined with a per-node constrained shortest path algorithm. We further propose an efficient route computation architecture, based on a novel metric-separation approach, to a slightly restricted version of the problem. The strategy is somewhat similar to "route caching", but in a new and broader sense.

We present a novel bandwidth allocation scheme for transporting variable-bit-rate MPEG traffic from a video server. Using time-varying envelopes to characterize the traffic, this scheme achieves significant bandwidth gain, via statistical multiplexing, while supporting stringent, deterministic QoS guarantees. The gain can be maximized by allowing the server to appropriately schedule the starting times of video sources, at the expense of some negligible startup delay. For homogeneous streams, we give the optimal schedule that results in the minimum allocated bandwidth. A suboptimal schedule is given in the heterogeneous case, which is shown to be asymptotically optimal. Efficient online procedures for bandwidth computation are provided. Numerical examples based on traces of MPEG-coded movies are used to demonstrate the benefits of our allocation strategy.

We present a comprehensive model for variable-bit-rate MPEG video streams. This model captures the bit-rate variations at multiple time scales. Long-term variations are captured by incorporating scene changes, which are most noticeable in the fluctuations of I frames. The size of an I frame is modeled by the sum of two random components: a scene-related component and an AR(2) component that accounts for the fluctuations within a scene. Two random processes of i.i.d. rvs are used to model the sizes of P and B frames, respectively. The complete model is then obtained by intermixing the three sub-models according to a given GOP pattern. It is shown that the composite model exhibits long-range dependence (LRD) in the sense that its autocorrelation function is non-summable. The LRD behavior is caused by the repetitive GOP pattern which induces periodic cross-correlations between different types of frames. Using standard statistical methods, we successfully fit our model to several empirical video traces. We then study the queueing performance for video traffic at a statistical multiplexer. The results show that the model is sufficiently accurate in predicting the queueing performance for real video streams.

One of the major attractions of asynchronous transfer mode (ATM) networks for transporting bursty video traffic is its ability to exploit the multiplexing gains of packet switching while providing quality of service guarantees. Unfortunately, most of the multiplexing mechanisms proposed in the literature fail to exploit the multiplexing gains of ATM. We propose a multirate service mechanism that allows a session to be served at different rates at different times. Applications generating bursty data, such as variable bit-rate (VBR) video, can take advantage of multirate service by requesting a high rate of service for brief periods of bursty arrivals and a much lower rate of service for all other times. Consequently, the applications can improve their delay performance without reserving a high bandwidth for the entire duration of the sessions. Furthermore, the scheduler can multiplex the peaks and the lulls in service rates of different sessions and improve the utilization of the system. Using MPEG video traces from a number of applications, we show that multirate servers outperform single-rate PGPS (packet-by-packet generalized processor sharing) servers and CBR (constant bit-rate) servers in terms of number of connections admitted, while providing the same level of service guarantees. We also investigate the performance of multirate service when service quality need not be guaranteed. We refer to this as predictive service. We propose a measurement-based admission control procedure for predictive service, and show that it helps increase the size of the admissible region even further.

A computation task running in distributed systems can be represented as a directed graph H(V, E) whose vertices and edges may fail with known probabilities. In this paper, we introduce a reliability measure, called the distributed task reliability, to model the reliability of such computation tasks. The distributed task reliability is defined as the probability that the task can be successfully executed. Due to the and-fork/and-join constraint, the traditional network reliability problem is a special case of the distributed task reliability problem, where the former is known to be NP-hard in general graphs. For two-terminal and–or series-parallel (AOSP) graphs, the distributed task reliability can be computed in polynomial time. We consider a graph Hk(Vˆ, Eˆ), named a k-replicated and–or series-parallel (RAOSP) graph, which is obtained from an AOSP graph H(V, E) by adding (k - 1) replications to each vertex and adding proper edges between two vertices. It can be shown that the RAOSP graphs are not AOSP graphs; thus, the existing polynomial algorithm does not apply. Previously, only exponential time algorithms as used in general graphs are known for computing the reliability of Hk(Vˆ, Eˆ). In this paper, we present a linear time algorithm with O(K(|V| + |E|)) complexity to evaluate the reliability of the graph Hk(Vˆ, Eˆ), where K = max{k222k, 23k}. © 1997 John Wiley & Sons, Inc.

NFS is a widely used remote file access protocol that has been tuned to perform well on traditional LANs which exhibit low error rates. Users migrating to mobile hosts would like continued remote file access via NFS. However, low bandwidth and high error rates degrade performance on mobile hosts using wireless links, hindering the use of NFS. We conducted experiments to study the behaviour of NFS in a wireless testbed. Based on these experiments, we incorporated modifications into the mobile NFS client. This paper presents two mechanisms which improve NFS performance over wireless links: an aggressive NFS client and link-level retransmissions. Our experiments show that these mechanisms improve response time by up to 62%, which brings the performance to within 5% of that obtained in zero error conditions.

Unlike wired networks, packets transmitted on wireless channels are often subject to burst errors which cause back to back packet losses. Most wireless LAN link layer protocols recover from packet losses by retransmitting lost segments. When the wireless channel is in a burst error state, most retransmission attempts fail thereby causing poor utilization of the wireless channel. Furthermore, in the event of multiple sessions sharing a wireless link, FIFO packet scheduling can cause the HOL blocking effect, resulting in unfair sharing of the bandwidth. This observation leads to a new class of packet dispatching methods which explicitly take the wireless channel characteristics into consideration in making packet dispatching decisions. We compare a variety of channel state dependent packet (CSDP) scheduling methods with a view towards enhancing the performance of the transport layer sessions. Our results indicate that by employing a CSDP scheduler at the wireless LAN device driver level, significant improvement in the channel utilization can be achieved in typical wireless LAN configurations.

We propose a work-conserving scheduling mechanism for providing deterministic performance guarantees in ATM networks. The most attractive feature of the proposed mechanism, which we call carry-over round robin (CORR), is its simplicity. It is an extension of weighted round robin scheduling. We have derived closed form bounds for worst case end-to-end delay when CORR is used in conjunction with the composite leaky bucket, and moving window regulators. Our results show that albeit its simplicity, CORR is very competitive with some of the more complex scheduling disciplines such as packet-by-packet generalised processor sharing and stop-and-go queueing.

We propose a multirate service mechanism that allows a network session to be served at different rates at different times. Applications generating bursty data, such as VBR video, can take advantage of multirate service by requesting a high rate of service for brief periods of bursty arrivals and a lower rate of service at other times. Consequently, an application can improve its delay performance without reserving high bandwidth for the entire duration of a session. Using MPEG video traces from a number of applications, we show that a multirate server outperforms single rate PGPS (packet-by-packet generalized processor sharing) servers in terms of number of connections admitted, while providing the same level of service guarantees. We also investigate the performance of multirate service when service quality need not be guaranteed. We refer to this as predictive service. We show that multirate servers are superior to single rate servers in providing predictive services.

Multimedia applications comprise several media streams, which are semantically synchronized at different time instants. The application behavior is stored along with the multimedia database using representation mechanisms such as OCPN (object composition Petri nets) or dynamic timed Petri nets (DTPN). It is imperative that one translates the application behavior to the corresponding schedulable entities, such as packets, so that the performance engineering of any system can be done, using the traffic model arising out of the (media related) application behavior as opposed to individual media level behavior. This requires that a function be defined, which takes the stored temporal representation as input and produces packets as output, preserving the semantic relationships among the streams. The authors propose a methodology based on probabilistic, attributed context free grammar (PACFG) to address this issue. They demonstrate the appropriateness of this methodology by applying it to the OCPN/DTPN representation of a typical multimedia application vis-a-vis orchestrated presentation.

Increasing the parallelism in transaction processing and maintaining data consistency appear to be two conflicting goals in designing distributed database systems (DDBSs). This problem is especially difficult if the DDBS is serving long-lived transactions (LLTs). A special case of LLTs, called sagas, has been introduced that addresses this problem. A DDBS with sagas provides high parallelism to transactions by allowing sagas to release their locks as early as possible. However, it is also subject to an overhead, due to the efforts needed to restore data consistency in the case of failure. We conduct a series of simulation studies to compare the performance of LLT systems with and without saga implementation in a faulty environment. The studies show that saga systems outperform their nonsaga counterparts under most of conditions, including heavy failure cases. We thus propose an analytical queuing model to investigate the performance behavior of saga systems. The development of this analytical model assists us to quantitatively study the performance penalty of a saga implementation due to the failure recovery overhead. Furthermore, the analytical solution can be used by system administrators to fine-tune the performance of a saga system. This analytical model captures the primary aspects of a saga system, namely data locking, resource contention and failure recovery. Due to the complicated nature of the analytical modeling, we solve the model approximately for various performance metrics using decomposition methods, and validate the accuracy of the analytical results via simulations.

The activity in building gigabit speed networks has led many researchers to re-examine the issue of congestion control. We describe a rate-based hop-by-hop congestion control mechanism in which the service rates of connections are dynamically adjusted at a switch, using feedback information provided by the neighboring switches. The desired service rate is computed based on a control equation that utilizes a model of the system with feedback information used to correct inaccuracies in the model. We use an analytical model to prove that the expected value of the queue occupancy and throughput of a controlled connection converge to the desired operating point. We also study the variation of the queue occupancy and throughput in steady-state as well as the transient response. The analytical results provide insights into how the parameter values chosen affect performance. We use simulations to compare the performance of the scheme with an equivalent end-to-end control scheme. Our analytical and simulation results show that the hop-by-hop scheme reacts faster to changes in the traffic intensity and, consequently, utilizes resources at the bottleneck better and loses fewer packets than the end-to-end scheme.

Management of replicated data has received considerable attention in the last few years. Several replica control schemes have been proposed which work in the presence of both node and communication link failures. However, this resiliency to failure inflicts a performance penalty in terms of the communication overhead incurred. Though the issue of performance of these schemes from the standpoint of availability of the system has been well addressed, the issue of message overhead has been limited to the analysis of worst case and best case message bounds. In this paper we derive expressions for computing the average message overhead of several well known replica control protocols and provide a comparative study of the different protocols with respect to both average message overhead and system availabilities.

k-resilient protocols are used in some parallel and distributed system applications for increased availability of resources. A protocol running on an n site system is k resilient if it could tolerate up to k failures and operate correctly. The reliability of such a protocol is defined as the probability that no more than k sites have failed. Such a k-resilient protocol is beneficial only when its reliability is greater than the reliability of a protocol running on a system with a single site. We consider k-resilient protocols and develop a general technique for approximately computing the time until which these protocols have higher reliability than protocols running on single site systems. We call this time the reliability interval. Our general techniques for computing the reliability interval can be used irrespective of the type of failure distribution (with respect to time) of the sites of the system. We use experimental results to validate our technique.>

We examine the tradeoff between message overhead and data availability that arises in the design of fault-tolerant algorithms for replicated data management in distributed systems. We propose a property called asymptotically high resiliency which is useful for evaluating the fault-tolerance of replica control algorithms and distributed mutual exclusion algorithms. We present a new algorithm for replica control that can be tailored (through a design parameter) to achieve the desired balance between low message overhead and high data availability. Further, we show that for a message overhead of O(/spl radic/(Nlog N)), our algorithm can achieve asymptotically high resiliency.

This paper proposes a traffic control scheme for integrated services ATM networks. The control strategy comprises of two components: a shaping mechanism at the network entry point and a frame based service discipline at the switches. The shaper enforces a short term peak rate, and a long term average rate. The multiplexing scheme at a switch allocates a guaranteed bandwidth to a connection. A connection may get more than the guaranteed amount, up to a connection specific maximum, if slack bandwidth is available. By imposing an upper bound on the allocated bandwidth, we secure a better handle on the delay jitter. Unlike most frame-based schemes, our scheme allows allocation of bandwidth at any arbitrary granularity. We suggest a simple admission control policy and derive deterministic bounds on end-to-end delay and jitter. An outline of a hardware realization of the scheme is also presented.>

We study resource synchronization in multiprocessor hard real-time systems. Specifically, we propose a multiprocessor resource control protocol which allows a job to simultaneously lock multiple global resources, removing a restriction from previous protocols. Allowing nested critical sections may permit a finer granularity of synchronization, increasing parallelism and throughput. All the protocols discussed belong to the class of priority inheritance protocols and rely in some fashion on priority ceilings for global semaphores. The extended protocol prevents deadlock and transitive blocking. We derive bounds for worse case blocking time, and describe sufficient conditions to guarantee that m sets of periodic tasks can be scheduled on an m multiprocessor system.

The authors examine the performance implications of providing reliability in conjunction with multicast transport over a high speed wide area network. They use a block based acknowledgement and selective retransmission protocol to evaluate the impact of the loss rate and the multicast tree topology on the achievable throughput. Their results show that even when the buffer overflow probability at switches and receivers is low, the cumulative loss probability seen by a source may be quite high. They also demonstrate that the average throughput increases significantly if the transport protocol delivers packets to the application layer out-of-sequence. They investigate the scaling properties of the error control mechanism and show that the multicast tree topology that results in minimum transfer time is not necessarily the same as the one constructed using minimal bandwidth or shortest path algorithms.>

This paper addresses the problem of guaranteed delivery of messages with hard deadlines in a DQDB network. The authors present a cyclic reservation scheme capable of allocating bandwidth with any arbitrary granularity and provide deterministic delay guarantees. They propose two implementations of the allocation scheme within the framework of DQDB medium access control protocol. The proposed implementations are very simple, incur minimal overhead and require only minor changes in the adopted standard.>

A main objective of scheduling independent jobs composed of multiple sequential tasks in shared-memory and distributed-memory multiprocessor computer systems is the assignment of these tasks to processors in a manner that ensures efficient operation of the system. Achieving this objective requires the analysis of a fundamental tradeoff between maximizing parallel execution, suggesting that the tasks of a job be spread across all system processors, and minimizing synchronization and communication overheads, suggesting that the job's tasks be executed on a single processor. The authors consider a class of scheduling policies that represent the essential aspects of this processor allocation tradeoff, and model the system as a distributed fork-join queueing system. They derive an approximation for the expected job response time, which includes the important effects of various parallel processing overheads (such as task synchronization and communication) induced by the processor allocation policy.>

Management of replicated data has received considerable attention in the last few years. Several replica control schemes have been proposed which work in the presence of both node and communication link failures. However, this resiliency to failure inflicts a performance penalty in terms of the communication overhead incurred. Though the issue of performance of these schemes, from the standpoint of availability of the system, has been well addressed, the issue of message overhead has been limited to the analysis of worst-case and best-case message bounds. In this paper, we compare several well-known replica management protocols and control schemes in terms of their average-case message overhead. We also consider the tradeoff between the message overhead and availability, and we define the system model considered. Analytical expressions are derived for five well-known replica control protocols. The results are discussed with numerical examples.>

A threshold-based dynamic allocation policy, called DQT, in which the bandwidth allocated to each class of traffic is altered based on the queue occupancy at the end of a frame is studied. Two classes of traffic with different quality of service (QOS) requirements are considered, and it is shown that the performance of the proposed scheme is better than that of a static allocation scheme. The performance of the scheme and the parameter sensitivity are studied under both stationary and nonstationary conditions, and it is indicated how parameter values can be chosen.>

We study the problem of transmitting time constrained synchronous messages in a slotted ring based local area network, carrying synchronous and asynchronous traffic. A bandwidth allocation scheme for synchronous messages is developed on top of a media access control protocol that assigns preemptive priority to synchronous traffic over asynchronous traffic. We derive sufficient conditions for schedulability of time critical synchronous messages and show that the scheme achieves high levels of schedulable utilization. A slot access protocol is proposed for synchronous streams that implements the allocation scheme with minimal additional overhead and loss of schedulable utilization. The protocol is distributed in the sense that any node can locally determine if it can use a slot, without exchanging any explicit messages with other nodes.>

Multicomputers, consisting of many processing nodes connected through a high speed interconnection network, have become an important and common platform for a large body of scientific computations. These parallel systems have traditionally executed programs in batch mode, or have at most space-shared the processors among multiple programs using a static partitioning policy. This, however, can result in relatively low system utilization and throughput for important classes of scientific applications.In this paper we consider "a class of scheduling policies that attempt to increase processor utilization and system throughput by timesharing a partition of processors among multiple programs. We compare the system performance under this multiprogramming policy with that of static partitioning for a variety of workloads via both analytic and simulation modeling. Our results show that timesharing a partition can provide significant improvements in performance, particularly at moderate to heavy loads. The performance gains of the multiprogrammed policy depend upon the inherent efficiency of the parallel programs that comprise the workload, decreasing with increasing program efficiency. Our analysis also provides the regions over which one scheduling policy outperforms the other, as a function of system load.

A protocol for a slotted-ring local area network to handle two classes of jobs in which one class has preemptive priority over the other is presented. The detailed response time distribution analysis for different classes of jobs is given. It is shown that the modeling and analysis can be extended to multiclass jobs.>

Resource allocation for a distributed system employing the primary site approach for fault tolerance is discussed. Two kinds of systems are considered. The first consists of fault-tolerant nodes where each node has many duplicated servers. One server is the primary, which serves user requests, and the rest are backup. The second does not have fault-tolerant nodes. To tolerate node failures, each node uses other nodes as backups. When a node fails, all requests initially allocated to the node are served by one of its backups. To study the resource allocation for such systems, an approximate model for each system is developed. Using these models, efficient allocation algorithms that take into account the failure/repair rates of the system and the fault-tolerant overheads are presented. Using experimental results, it is shown that the algorithms give the optimal or suboptimal allocations. The algorithms, which incur little overhead, can improve the system performance significantly over an intuitive allocation algorithm.>

Data replication is often used to increase the availability of data in a database system. Voting schemes can be used to manage this replicated data. The authors use a simple model to study the capacity of systems using voting schemes for data management. Capacity of a system is defined as the number of operations the system can perform successfully, on an average, per unit time. The capacity of a system using voting is examined and compared with the capacity of a system using a single node. It is shown that the maximum increase in capacity by the use of majority voting is bounded by 1/p, where p is the steady-state probability of a node being alive. It is also shown that for a system employing majority voting, if the reliability of nodes is high, increasing the number of nodes to more than three gives only a marginal increase in capacity. Similar analyses are performed for three other voting schemes.>

The problem of managing replicated copies of data in a distributed database is considered. Quorum consensus methods for managing replicated data require that an operation proceed only if a group of copies form a quorum. For example, in a majority voting scheme, for a write operation to proceed, a majority of the copies have to form a quorum. The authors first introduce a performance measure for measuring the performance of fault-tolerant algorithms for this problem. They then propose a quorum-based method which is highly fault tolerant and has a low message overhead. The algorithm can tradeoff fault tolerance for lower message overhead. The algorithm is compared to existing algorithms.>

In a closed, separable, queuing network model of a computer system, the number of customer classes is an input parameter. The number of classes and the class compositions are assumptions regarding the characteristics of the system's workload. Often, the number of customer classes and their associated device demands are unknown or are unmeasurable parameters of the system. However, when the system is viewed as having a single composite customer class, the aggregate single-class parameters are more easily obtainable. This paper addresses the error made when constructing a single-class model of a multi-class system. It is shown that the single-class model pessimistically bounds, the performance of the multi-class system. Thus, given a multi-class system, the corresponding single-class model can be constructed with the assurance that the actual system performance is better than that given by the single-class model. In the worst case, it is shown that the throughput given by the single-class model underestimates the actual multi-class throughput by, at most, 50%. Also, lower bounds are provided for the number of necessary customer classes, given observed device utilizations. This information is useful to clustering analysis techniques as well as to analysts who must obtain class-specific device demands.

A probabilistic clock synchronization algorithm is proposed where processors in the system exchange time stamps and synchronize to a common clock value. Most of the previous algorithms for this problem have been based on a master-slave approach where all the slave processors synchronize to the clock value of a master. These algorithms are not distributed in nature and some of the assumptions made in these algorithms may become invalid if a large number of slaves try to synchronize with a master. The only distributed algorithm that is available was earlier proposed by A. Olson and K.G. Shin (1991). It is based on finding a cyclic path connecting the processors in the system and exchanging time stamp messages through this path. For the same level of synchronization accuracy, the proposed algorithm uses a much smaller number of messages.>

The authors present an efficient routing algorithm for realizing any permutation in LIN (linear-permutation-class) on single-stage shuffle-exchange networks with k*k switching elements, where k=p is a prime number. For any positive integer number n there are N=k/sup n/ processors connected by the network. The proposed algorithm can realize LIN in 2n-1 passes; it can be implemented by using Nn processors in O(n) time. It can also be extended to the shuffle-exchange networks with (p/sup t/*p/sup t/) switching elements, where t is a positive integer number. In addition, the routing of any arbitrary permutations on the networks with any integer k>2 is discussed. Further, by using the techniques developed here, the authors present an optimal O(log n) parallel algorithm for solving a set of linear equations with a nonsingular coefficient matrix when the arithmetic is over the finite field GF(p/sup t/).>

The concept of a processor working set (PWS) as a single value parameter for characterizing the parallel program behavior is introduced. Through detailed experimental studies of different algorithms on a transputer-based multiprocessor machine, it is shown that the PWS is a robust measure for characterizing the workload of a multiprocessor system. It is shown that processor allocation strategies based on the PWS provide significantly better throughput-delay characteristics. The robustness of PWS is further demonstrated by showing that allocation policies that allocate processors more than the PWS are inferior in performance to those that never allocate more than the PWS-even at a moderately low load. Based on the results, a simple static allocation policy that allocates the PWS at low load and adaptively fragments at high load to one processor per job is proposed.>

Maruti is a testbed for the design of time-driven hard real-time systems. It uses the technique of prescheduling, where the application is scheduled prior to execution and resources required by the application are reserved, in order to ensure that deadlines are met. A description is given of the features of MPL, a language for Maruti. MPL provides constructs for expressing time constraints, precedence relations, and synchronization directly in the programs. The MPL features are designed to facilitate prescheduling.>

Since each of the levels in a hierarchical system could have various characteristics, different fault-tolerant schemes could be appropriate at different levels. A stochastic Petri net (SPN) is used to investigate various fault-tolerant schemes in this context. The basic SPN is augmented by parameterized subnet primitives to model the fault-tolerant schemes. Both centralized and distributed fault-tolerant schemes are considered. The two schemes are investigated by considering the individual levels in a hierarchical system independently. In the case of distributed fault tolerance, two different checkpointing strategies are considered. The first scheme is called the arbitrary checkpointing strategy. Each process in this scheme does its checkpointing independently; thus, the domino effect may occur. The second scheme is called the planned strategy. Here, process checkpointing is constrained to ensure no domino effect. The results show that, under certain conditions, an arbitrary checkpointing strategy can perform better than a planned strategy. The effect of integration on the fault-tolerant strategies of the various levels of a hierarchy are studied.>

Analytical models are presented that use Petri nets for fault-tolerant schemes used in distributed systems. These models are used in the quantitative evaluation and selection of good fault-tolerant schemes for specific system configurations. Several different fault-tolerant schemes that can be modeled using Petri nets are discussed in detail. These schemes include rollback recovery with checkpointing, recovery blocks, N-version programming, and conversations. After a brief review of Petri net models, extension of the Petri net models to incorporate fault-tolerant schemes is considered. A methodology for evaluating a fault-tolerant scheme for a specific system configuration and the steps involved in building a Petri net model of a fault-tolerant system are described. The subnet primitives involved in building these models are identified and an algorithm for building the models automatically is described. Examples illustrating this extended Petri net model are discussed and numerical results are presented to show the applicability of the models.>

A new scheduling problem, which is called the insert-idle-time scheduling problem, is proposed which concerns scheduling N jobs on one machine when some of the machine time is unschedulable due to pre-scheduled maintenance time, lunch time or the time devoted to the jobs with higher priority or any other activities. An best-first branch-and-bound algorithm which takes “schedule improvement” approach is presented and the experimental results are reported.

This paper presents analytical results of computation-communication issues in dynamic dataflow architectures. The study is based on a generalized architecture which encompasses all the features of the proposed dynamic dataflow architectures. Based on the idea of characterizing dataflow graphs by their average parallelism, a queueing network model of the architecture is developed. Since the queueing network violates properties required for product from solution, a few approximations have been used. These approximations yield a multi-chain closed queueing network in which the population of each chain is related to the average parallelism of the dataflow graph executed in the architecture. Based on the model, we are able to study the effect on the performance of the system due to factors such as scalability, coarse grain vs. fine grain parallelism, degree of decentralized scheduling of dataflow instructions, and locality.

Abstract This paper describes the implementation of a test bed called SAHAYOG, for evaluating dynamic load‐sharing policies in which job‐transfer decisions are based on the state of the system. The test bed is implemented on a network of AT&T 3B2 minicomputers. It provides an interactive user interface for conducting load‐sharing experiments. Based on user‐specified parameters it creates independent job streams at different nodes in the network. Jobs are transferred among the nodes by the load‐sharing algorithm being evaluated. Each node collects data about the jobs, which are used to generate statistics about the experiment. Five load‐sharing algorithms are implemented and evaluated using the test bed under different load conditions and for various parameter values. These experiments confirm some earlier results about load sharing and also provide some new insights. SAHAYOG also contains an optional fault‐tolerance feature to handle single‐node failures, and evaluates the effect of fault tolerance on the performance of different policies.

The k-way bitonic sort algorithm, a generalization of K.E. Batcher's bitonic sort algorithm (1968), is presented. This variation of the algorithm is based on a k-way decomposition instead of a two-way decomposition. It is proven that Batcher's bitonic sequence decomposition theorem still holds with this multiway decomposition. This leads to applications of sorting networks with bitonic sorters of arbitrary or mixed sizes.>

A scheme is presented that makes a remote procedure call (RPC) mechanism fault-tolerant to hardware failures. Fault tolerance is provided by replicating the procedure at a group of nodes, called a cluster. The copies in a cluster are linearly ordered. A call to a procedure is sent to the first copy in the cluster and is propagated internally to all other copies. In the event of failures, the first copy in the cluster that has not failed returns the result to the caller. The scheme is transparent to the user and supports nested procedure calls. It has been implemented on a network of Sun workstations making use of Sun's existing RPC mechanism.>

A product-form queuing network with multiple open and closed chains is considered. Some of the closed chains, which have a single customer each, require allocation of resources in the network so as to maximize a weighted throughput performance criterion. Chains with more than one customer can be decomposed into many chains of one customer each. It is proved that an optimal allocation of resources lies on a vertex (extreme points) of the set of feasible allocations. This considerably reduces the search space for an optimal allocation. Applications of this result in distributed computing are discussed.

The self-routing technique using control tags on multiple-pass perfect-shuffle networks is generalized. In particular, they show that bit-permute-complement permutations can be realized and unscrambled in (2n-1) passes or less, where n=log/sub 2/N, N being the number of terminals on either side. They also show that most of the frequently used permutations are in the intersection of omega-realizing and inverse-omega-realizing sets and can be realized and unscrambled in n passes.>

In this paper, we present a review of the issues that affect the software requirements for a local area network. We introduce protocols for the local area networks and characterize their software needs. Two approaches to operating systems are outlined and examples of each approach are presented. Various applications which use local area networks and performance issues are also discussed.

This tutorial addresses performance problems in Local Area Networks (LAN). User level performance measures are affected both by the software as well as communication bottlenecks. Techniques for modeling the key components of the performance of a LAN will be presented. Models will be presented to discuss the throughput and response time characteristics of LANs. We also present some measurement data obtained from a LAN performance experiment.

In this paper, we present a new model, finite permutation machine (FPM), to describe the permutation networks. A set of theorems are developed to capture the theory of operations for the permutation networks. Using this new framework, an interesting problem is attacked: are 2n − 1 passes of shuffle exchange necessary and sufficient to realize all permutations? where n = log2 N and N is the number of inputs and outputs interconnected by the network. We prove that to realize all permutations, 2n − 1 passes of shuffle exchange are necessary and that 3n − 3 passes are sufficient. This reduces the sufficient number of passes by 2 from the best-known result.

A globally optimal allocation for files in a local network environment is presented. The principal concern is the delays due to contention at the file servers; storage space is assumed to be adequate. A queuing network model is used to represent the file servers and the workstations. The workloads generated by the workstations are statistically identical. The model assumes that the communications medium is lightly loaded. In this case there is very little queuing, so that a message transmission requires an approximately constant average delay which can be included in the local processing time of the workstation. Under these assumptions the model can be applied to any of the various LAN technologies. It is shown that all the files of each workstation should be placed on one file server, with the workstations divided as equally as possible among the file servers.

We present a model for distributed systems with failing components. Each node may fail and during its recovery the load is distributed to other nodes that are operational. The model assumes periodic checkpointing for error recovery and testing of the status of other nodes for the distribution of load.

Most of the analysis of buffer sharing schemes has been aimed at obtaining the optimal operational parameters under stationary load situations. It is well known that in most operating environments the traffic load changes. In this paper, we address the problem of updating buffer allocation as the traffic load at a network node changes. We investigate the behavior of a complete partitioning buffer sharing scheme to gain insight into the dependency of the throughput upon system parameters. The summary of the analysis is presented in the form of a heuristic. The heuristic is shown to perform reasonably well under two different types of stress tests.

The virtual waiting time technique is introduced as a solution to the problem of a controller distributing work to servers of different speeds. The servers are considered to be part of a distributed system without feedback. The virtual waiting time technique is shown to minimize the average completion time for a job distributed by the controller. The virtual waiting time technique does not depend on any arrival distribution and is applicable to any service time distribution. The performance of the technique is examined for different arrival and service time distributions.