Geographically replicating popular objects in the Internet speeds up content distribution at the cost of keeping the replicas consistent and up-to-date. The overall effectiveness of replication can be measured by the total communication cost consisting of client accesses and consistency management, both of which depend on the locations of the replicas. This paper investigates the problem of placing replicas under the widely used TTL-based consistency scheme. A polynomial-time algorithm is proposed to compute the optimal placement of a given number of replicas in a network. The new replica placement scheme is compared, using real Internet topologies and Web traces, against two existing approaches which do not consider consistency management or assume invalidation-based consistency scheme. The factors affecting their performance are identified and discussed

Distributed denial-of-service (DDoS) attacks present serious threats to servers in the Internet. They can exhaust critical resources at a target host with the help of a large number of compromised Internet hosts and hence deny services to legitimate clients. This paper studies some existing schemes for the detection and defense against TCP-based DDoS attacks. We propose a distributed scheme that can mitigate the damage caused by DDoS through a coordinated detection and response framework. This proposed scheme composes of a number of heterogeneous defense systems which cooperate with each other in protecting Internet servers. We have set up a network testbed for carrying out extensive experiments using real server machines, routers and software attack tools. Experimental results show that, compared to existing schemes, our proposed scheme can greatly improve the throughput of legitimate traffic and reduce the attack traffic during DDoS attacks. To investigate the scale-up behavior of our scheme, we have also developed a software simulator for larger-scale experiments. Simulation results show that our scheme performs consistently well even in networks with more than 3000 nodes and under high traffic load.

In this paper, we present the design, the implementation details, and the evaluation results of an intrusion detection and defense system for distributed denial-of-service (DDoS) attack. The evaluation is conducted using an experimental testbed. The system, known as intrusion detection router (IDR), is deployed on network routers to perform online detection on any DDoS attack event, and then react with defense mechanisms to mitigate the attack. The testbed is built up by a cluster of sufficient number of Linux machines to mimic a portion of the Internet. Using the testbed, we conduct real experiments to evaluate the IDR system and demonstrate that IDR is effective in protecting the network from various DDoS attacks.

A real-time wireless system using hybrid automatic repeat request to correct errors is analyzed. Packet errors are modeled by a two-state Markov chain, and batch packet arrivals are allowed. Packets are dropped at the sender if their delays exceed a time limit, possibly after a number of retransmissions. Using the delay-model approach, a closed-form expression of packet-loss probability (PLP) and an approximate formula of wireless effective bandwidth (WEB) satisfying the quality of service requirements have been derived. If Bose–Chaudhuri–Hocquengem codes are used, an expression estimating the number of correctable bits to minimize the PLP has also been obtained. Moreover, the WEB is found to be independent of the packet size, and the PLP decreases exponentially as the WEB increases.

A real-time wireless system using hybrid automatic repeat request to correct errors is analyzed. Packet errors are modeled by a two-state Markov chain, and batch packet arrivals are allowed. Packets are dropped at the sender if their delays exceed a time limit, possibly after a number of retransmissions. Using the delay-model approach, a closed-form expression of packet-loss probability (PLP) and an approximate formula of wireless effective bandwidth (WEB) satisfying the quality of service requirements have been derived. If Bose-Chaudhuri-Hocquenghem codes are used, an expression estimating the number of correctable bits to minimize the PLP has also been obtained. Moreover, the WEB is found to be independent of the packet size, and the PLP decreases exponentially as the WEB increases

Expiration-based consistency management is widely used to keep replicated contents up-to-date in the Internet. The effectiveness of replication can be characterized by the communication costs of client accesses and consistency management. Both costs depend on the locations of the replicas. This paper investigates the problem of placing replicas in a network where replica consistency is managed by the expiration-based scheme. Our objective is to minimize the total cost of client accesses and consistency management. By analyzing the communication cost of recursive validations for cascaded replicas, we prove that in the optimal placement scheme, the nodes not assigned replicas induce a connected subgraph that includes the origin server. Our results are generic in that they apply to any request arrival patterns. Based on the analysis, an O(D){\hbox{-}}{\rm{time}} algorithm is proposed to compute the optimal placement of the replicas, where D is the sum of the number of descendants over all nodes in the routing tree.

Virtual private networks (VPN) provide a cost-effective means of meeting the communication needs among several sites. The hose model for VPN configuration alleviates the scalability problem of the pipe model by reserving bandwidth for traffic aggregates instead of between every pair of endpoints. Existing studies on quality of service (QoS) guarantees in the hose model deal only with bandwidth requirements. In this paper we enhance the hose model to specify delay requirements between endpoints. Three categories of algorithms, namely the pipe mesh, the multiple source-based trees, and the shared tree approaches, are then proposed for VPN provisioning. We investigate methods of implementing the shared tree approach to meet the delay requirements with low provisioning cost and small computation overhead.

In this paper, voltage scaling strategies for scheduling aperiodic tasks under average delay constraints are studied. Dynamic voltage scaling in single processor systems is formulated as a constrained stochastic optimization problem for which the optimal solution can be obtained using a combination of Lagrange relaxation and the value iteration method. For multiprocessor systems, we present a two-phase approach. In the first phase, the speed settings and static workload distribution of the processors are optimized to minimize the total power dissipation. Dynamic voltage scaling techniques are then applied to each individual processor in the second phase. Both homogeneous and heterogeneous systems have been investigated. Based on queueing theory, the proposed algorithms guarantee conformity to the average delay constraint. Moreover, our simulation experiments have shown they are effective for minimizing power consumption.

Persistent connections are increasingly being used in Web retrieval due to wide adoption of HTTP/1.1 standards. With persistent connections, the request allocation algorithm used by Web clusters is often session-grained. This article studies the caching performance of Web clusters under session-grained request allocation. It is shown that although content-based algorithms considerably improve caching performance over content-blind algorithms at the request-grained level, most performance gain is offset by the allocation dependency that arises when the requests are allocated at the session-grained level. The performance loss increases with cluster size and connection holding time. An optimization problem is then formulated for improving the caching effectiveness of session-grained allocation. The problem is proven to be NP-complete. Based on a heuristic approach, a session-affinity aware algorithm is presented that makes use of the correlation between the requests in a session. The new algorithm is shown to significantly outperform the content-based algorithm under session-grained allocation. It is also shown that optimizing session-grained allocation cannot fully compensate for the performance loss caused by allocation dependency.

This paper presents an automatic test generation and minimization method for testing interoperability of communication protocols such as the asynchronous transfer mode/broadband integrated services digital network (ATM/B-ISDN) signaling protocol and the transmission control protocol (TCP). The method is based on a technique of composing finite-state machines (FSMs). Traditionally, the generation of inputs utilizing FSM was mostly based on sequential test scripting languages and often done manually. Each input is processed on a one-at-a-time basis, which did not allow generating complex scenarios of simultaneous inputs on several interfaces of the system under test (SUT). In practice, there exists the possibility that additional inputs have to be sent to the SUT, while the previous input is still being processed, and/or multiple inputs need to be sent to different interfaces of the SUT at the same time. Our method generates interoperability test cases dealing with these more complex situations. Moreover, it minimizes the number of increased test cases due to the multiple stimuli without jeopardizing transition coverage. Experimental results have shown that compared with the conventional methods, our test generation method generates more interoperability test cases resulting in higher transition coverage (26% higher for TCP and 12% higher for ATM signaling protocol). Also, our test minimization method reduces the interoperability test cases by about 94% in the case of the ATM signaling protocol with the same transition coverage.

As mobile computing is getting popular, there is a growing need for techniques that minimize energy consumption on battery-powered mobile devices. Processor voltage scheduling can effectively reduce processor energy consumption by lowering the processor speed. In this paper, we study voltage scheduling for real-time periodic tasks with non-preemptible sections. Three schemes are proposed: The static speed algorithm derives the minimum static feasible speed based on the stack resource policy. Due to blocking, this static speed is usually higher than the speed required for scheduling fully preemptible tasks (called the utilization speed). Two dynamic speed algorithms are then introduced to further reduce energy consumption. The novel dual speed algorithm operates the processor at the utilization speed whenever possible and switches to the higher static speed only when blocking occurs. The dual speed dynamic reclaiming algorithm reserves time budget for each job, reclaims the unused time budget from completed jobs and redistributes it to subsequent jobs so they can run at a lower speed whenever possible. Feasibility conditions for real-time task sets have been derived and proved mathematically. Simulation results show that the proposed voltage scheduling algorithms dramatically reduce processor energy consumption over non-power-aware scheduling algorithms. Furthermore, the two dynamic speed algorithms consistently outperform the static speed scheme in a wide range of system and workload conditions.

The expiration-based scheme is widely used to manage the consistency of cached and replicated contents such as Web objects. In this approach, each replica is associated with an expiration time beyond which the replica has to be validated. While the expiration-based scheme has been investigated in the context of a single replica, not much work has been done on its behaviors with respect to multiple replicas. To allow for efficient consistency management, it is desirable to organize the replicas into a distribution tree where a lower level replica seeks validation with a higher level replica when its lifetime expires. This paper investigates the construction of a distribution tree for a given set of replicas with the objective of minimizing the total communication cost of consistency management. This is formulated as an optimization problem and is proven to be NP-complete. The optimal distribution tree is identified in some special cases and several heuristic algorithms are proposed for the general problem. The performance of the heuristic algorithms is experimentally evaluated against two classical graph-theoretic algorithms of tree construction: the shortest-paths tree and the minimum spanning tree.

Dynamic Web contents are generated by running application programs on base data which often change frequently. Geographically replicating the applications that construct these contents (including the programs and the related data they access) is an effective approach to improve their access latency. To maintain the freshness of an object replica, the new version of the object either has to be fetched from remote servers or be reconstructed locally when the origin copy is updated. We present a theoretical study on geographical replication of dynamic Web contents with the objective of minimizing the consistency management costs in terms of update transfers and object reconstruction. The dependencies among dynamic objects and base data are modeled as a directed acyclic graph. We formulate the minimum cost replication problem under a flat framework of update delivery. The problem is solved by first transforming it into a minimum cut problem in a flow network. A polynomial-time algorithm is then proposed to compute the optimal replication strategy which designates where each object should be replicated and how to keep the replicas up-to-date.

With recent advances in network technologies and computing power, multimedia systems have become a popular means for information delivery. However, testing of these systems is difficult. Due to incomplete control of their runtime and communication environment, precise temporal properties of multimedia systems are nonreproducible. Traditional software testing, which mainly deals with functional correctness, cannot be directly applied to testing temporal properties. Furthermore, time points are hard to be measured exactly, and in this sense are nondeterministic and nonreproducible. To address this problem, we propose a framework for testing the generic temporal properties of media objects in distributed multimedia software systems (DMSS). The timing properties are based on Allen's basic binary temporal relations between two objects, which can be extended to cover multiple objects. We have developed techniques for test case generation, and test result analysis based on a distributed tester architecture. Test templates are used in test case generation to reduce the possibility of human error, and the entire testing procedure can be automated. A prototype system has been built to test a DEC HPAS multimedia presentation system, which is a multimedia system supporting W3C's SMIL standard. Detailed discussions on practical issues illustrated with a number of actual tests are given. Experimental results have shown that our framework is effective in detecting errors in temporal properties. Furthermore, ways to reduce the test effort have been discussed, and guidelines for coming up with criteria for verdict computation based on the real-time requirements of the applications have been suggested.

In this paper we present a generalized scheme for quality of service routing with both delay and bandwidth constraints using a delay weighted flow approach. The objective is to minimize call blocking probability. A request is routed along the path capable of supporting the required quality of service and which most preserves the routing ability of the network for future requests. A general mathematical model has been formulated to solve this problem. Simulation results show that the proposed scheme outperforms existing schemes.

Large-scale content delivery systems such as the Web often deploy multiple caches at different locations to reduce access latency and network traffic. These caches are usually organized in a cascaded fashion where requests not hitting a lower level cache are forwarded to a higher level cache. The performance of cascaded caching depends on how the cache contents are managed, including object placement and replacement schemes. We present a general analytical framework for coordinated management of cascaded caches. The object placement problem is formulated as an optimization problem and the optimal locations for caching objects are computed by a dynamic programming algorithm. Based on the framework, we propose a novel caching scheme that incorporates both object placement and replacement strategies. The proposed scheme makes caching decisions for the set of caches lying on the delivery path of a request in a coordinated fashion. Simulation experiments based on real traces from Web caches have been conducted under two different cascaded caching architectures: enroute caching and hierarchical caching. The results show that for both architectures, the proposed scheme significantly outperforms existing schemes that consider object placement or replacement at individual caches only.

Multimedia applications over the Internet are becoming increasingly popular. The soft real-time constraints of this type of application have given rise to interesting issues for scheduling in the network as well as the end systems. The paper presents a rate-based task scheduling framework for the receiving hosts. As multimedia streams are expected to be played back at constant rate, the proposed scheme tries to maintain the specified output frame rate by assigning proper deadlines to the frames. A multimedia stream that falls behind can catch up by skipping some frames. Interference among tasks is prevented using rate-controlled servers (RCS). The performance of these schemes has been analyzed mathematically and evaluated by simulations.

Energy efficient transmission is an important issue for mobile communication devices. In this paper, we study throughput and value-based packet scheduling over a wireless link under time and energy constraints. A mobile node is required to deliver multiple data streams to multiple receivers. These data streams may have different importance and incur different energy costs. In this research, point-to-point wireless data transmission is studied. The objective is to develop schemes that selectively transmit data streams at certain power levels so that the data throughput or the value of data delivery is maximized without violating the energy and time constraints. Exploiting the special properties of the throughput maximization problem, we propose an iterative algorithm that yields the optimal transmission schedule. The value maximization problem is formulated as a convex optimization problem and the optimal results can be obtained by solving the Kuhn-Tucker conditions. When time and transmission power are allocated at discrete slots and levels, respectively, a dynamic programming approach is proposed to find the optimal value.

Streaming media is expected to become one of the most popular types of Web content in the future. Due to increasing variety of client devices and the range of access speeds to the Internet, multimedia contents may be required to be transcoded to match the client's capability. With transcoding, both the network and the proxy CPU are potential bottlenecks for streaming media delivery. This paper discusses and compares various caching algorithms designed for transcoding proxies. In particular we propose a new adaptive algorithm that dynamically selects an appropriate metric for adjusting the management policy. Experimental results show that the proposed algorithm significantly outperforms those that cache only untranscoded or only transcoded objects. Moreover motivated by the characteristics of many video compression algorithms, we investigate partitioning a video object into sections based on frame type and handling them individually for proxy caching. It is found that partitioning improves performance when CPU power rather than network bandwidth is the limiting resource, particularly when the reference pattern is not highly skewed.

As mobile computing becomes more popular, there is increasing interest in techniques that can minimize energy consumption and prolong the battery life of mobile devices. Processor voltage scheduling is an effective way of reducing energy dissipation by reducing processor speed. We study voltage scheduling for real-time periodic tasks with non-preemptible sections. Three schemes are proposed to address this problem. The static speed algorithm derives a static feasible speed based on the stack resource policy (SRP). As worst-case blocking does not always occur, the novel dual speed algorithm switches processor speed to a lower value whenever possible. The dynamic reclaiming algorithm deploys a reservation-based approach to reclaim unused run time for redistribution. It effectively decreases processor idle time and further reduces processor speed Feasibility conditions are given and proved. Simulation results show that the two dynamic algorithms can reduce processor energy consumption by up to 80 percent over the static speed scheme.

Web caching is an important technique for reducing Internet access latency, network traffic, and server load. This paper investigates cache management strategies for the en-route web caching environment, where caches are associated with routing nodes in the network. We propose a novel caching scheme that integrates both object placement and replacement policies and which makes caching decisions on all candidate sites in a coordinated fashion. In our scheme, cache status information along the routing path of a request is used in dynamically determining where to cache the requested object and what to replace if there is not enough space. The object placement problem is formulated as an optimization problem and the optimal locations to cache the object are obtained using a low-cost dynamic programming algorithm. Extensive simulation experiments have been performed to evaluate the proposed scheme in terms of a wide range of performance metrics. The results show that the proposed scheme significantly outperforms existing algorithms which consider either object placement or replacement at individual caches only.

Hash routing is an effective approach for coordinating a collection of Web proxies. In this paper, we present a comprehensive analytical model for hash routing which takes into consideration a number of factors: the original request distribution, the object allocation strategy, the speeds of the proxies and cache hit ratios. Based on this model, the optimal hash routing problems for static and dynamic client configurations are investigated. Two schemes, OBJ-OPT (OBJect OPTimization) and OBJ/DNS-OPT (OBJect and Domain Name Server OPTimization), are proposed to reduce the response times of Web requests. OBJ-OPT optimizes object allocation under a static client configuration, and OBJ/DNS-OPT optimizes both object and DNS allocations under a dynamic client configuration. Extensive trace-driven simulations have been conducted to evaluate the proposed schemes. The results show that they significantly outperform the intuitive scheme based only on the speeds of the proxies.

In this paper we present bandwidth-delay constrained routing algorithms that use knowledge of the ingress-egress node pairs in the network in reducing the rejection rates for setting up new paths. Simulation is used to evaluate the algorithms and compare their performance against some existing algorithms for bandwidth constraints that have been modified to handle delay constraints. The results show that the proposed algorithms outperform all others under a wide range of workload, topology and system parameters.

While multimedia software applications are becoming popular, few studies exist on testing this important class of software, especially with respect to its temporal properties. Traditional software testing techniques mainly deal with functional correctness and cannot be directly applied to testing timing properties. The authors present a framework for testing the generic temporal relations of media objects in distributed multimedia software systems (DMSS). The temporal relations are based on J.F. Allen's (1983) basic binary temporal relations between two objects and extended to cover multiple number of objects in different streams. We have developed techniques for test case generation and test result analysis based on a distributed tester architecture. A prototype system has been built to test a DEC HPAS multimedia presentation system which is a typical multimedia system supporting W3C's SMIL standard. A detailed discussion on practical issues and illustration with a number of actual tests are given. Experimental results have shown that our framework is effective in detecting timing errors. The techniques and methodology are general and can be applied to other DMSS with only minor modification.

The popularity of handheld mobile devices and deployment of the public key infrastructure in many parts of the world have led to the development of electronic commerce on mobile devices. For the current version of mobile phones, the main challenge is the limited computing capacity on these devices for PKI-based end-to-end secure transactions. This paper presents a new architecture and protocol for authentication and key exchange as well as the supporting infrastructure that is suitable for the mobile phone environment.

This paper investigates dynamic load balancing issues in the multidomain environment where local area networks (LANs) are interconnected by the Internet. Because of the much slower Internet communication speed and limited bandwidth, existing load balancing algorithms for LANs are unsuitable for the multidomain environment. New issues such as lag time in updating load information and network cost of transferring jobs must be addressed. To tackle these problems, the conventional least load scheduler is extended to the multidomain environment by employing a hierarchical structure, and several quick update techniques are proposed. Also, a heuristic taking both the machine load and the network cost into consideration is developed to evaluate the benefits of sending jobs to computers in different domains. A set of experiments conducted on the BALANCE testbed showed that the proposed techniques provide significant performance improvement over existing algorithms.

This paper investigates static job scheduling schemes that distribute workload in a network of computers with different speeds. Static schemes involve very low overhead and complexity compared to dynamic schemes, but can still provide significant performance improvement over the case of no load balancing. Optimization techniques are proposed for workload allocation and job dispatching. Workload allocation is modeled as a non-linear optimization problem and solved mathematically. It is shown that allocating a disproportionately high percentage of jobs to the more powerful computers improves system performance. The proposed job dispatching algorithm is an extension of the traditional round-robin scheme. The objective is to reduce burstiness in the job arrival stream to each computer The schemes are evaluated by simulation experiments. Performance results verify their effectiveness in terms of mean response time, mean response ratio, and fairness. The Optimized Round-Robin (ORR) strategy which combines both techniques outperforms other static scheduling algorithms examined.

In protocol conformance testing, there is an important class of errors, namely coordination loss that cannot be anticipated because some source of error is external to both the tester and the implementation under test, (IUT). Furthermore, it is not possible to simulate their occurrence exhaustively in the test environment. Therefore they are very difficult to catch in the testing phase. In this paper we propose use self-stabilization as a design principle of design for testability (DFT) to overcome this testing problem. This will improve the reliability of protocol implementations derived from self-stabilizing protocol specifications. We present a novel algorithm and the corresponding design principles to design self-stabilizing protocols, and give an example of a self-stabilizing protocol.

We propose a superimposition algorithm than can be employed by a substrate to change its behavior according to current conditions or properties of the mobile environment. The algorithm has some interesting features such as it is completely distributed, works on-line, does not generate extra messages, and is based on unstable predicates. The algorithm proposed can be used by multiple local controllers that use information only from the subset of the participating mobile units. This is certainly an advantage over a centralized approach that is likely to be more expensive than distributed decisions since there are delays in the communication and the cost of sending extra messages.

This paper reports a joint work between the Hong Kong University of Science and Technology and the Brandenburg Technical University of Cottbus, Germany, in developing a global video conferencing framework called OCTOPUS that interconnects local conferencing systems over long distances. The system makes use of both high level information provided by the participants (to decide which videos are more important to them) as well as low level adaptive mechanisms to perform media scaling as the network and the processor intensities change. It is possible to provide a customized service to each conference participant according to his/her needs and the resources available at each site. OCTOPUS itself makes no assumption on the architecture of the local video conference systems. The paper presents the architecture and the design philosophy of the OCTOPUS framework.

This paper presents a hydrodynamic framework to solving the dynamic load balancing problem in heterogeneous distributed systems. In this approach, each processor is viewed as a liquid cylinder where the cross-sectional area corresponds to the capacity of the processor, the communication links are modeled as liquid channels between the cylinders, the workload is represented by liquid, and the load balancing algorithm manages the flow of the liquid. It is proven that all algorithms under this framework converge geometrically to the state of equilibrium, in which the heights of the liquid columns are the same in all the cylinders. In this way, each processor obtains an amount of workload proportional to its capacity. A hydrodynamic algorithm is presented and its performance is evaluated. The algorithm is applied to solve several practical applications to demonstrate the applicability of the framework.

This paper is concerned with performance and quality of service (QoS) guarantees for wireless networks that support multiple types of traffic. QoS is maintained by a distributed adaptive event-based admission control scheme. We compare the case where cell capacity is completely shared by the calls to the case where the cell capacity is partitioned for different types of traffic. Complete capacity sharing networks may give higher system utilization due to statistical multiplexing gain, but need to adopt the tightest QoS bound among all traffic types. Partitioning will result in a less complex management system which provides independent QoS controls for different traffic types at the expense of possible lower overall utilization. The analytic results are verified by simulation experiments.

A novel call admission control (CAC) scheme based on dynamic channel allocation (DCA) is proposed for cellular networks. The scheme combines the advantage of high channel availability of DCA with quality of service guarantees of CAC. Our scheme uses statistical bandwidth reservation for handoff events. A new call is rejected if the probability of the required bandwidth exceeds the available bandwidth by a given threshold in any cell within the interference region. The proposed scheme is evaluated analytically and by simulations. The results show marked improvement over fixed channel allocation with admission control as well as DCA without admission control for a wide range of traffic intensities.

This paper extends the logical inference of Horn clauses in Petri net models to cover a large class of non-Horn clauses. Based on four-valued logic and the conflict transition concept, we show how the Petri net model for this class of non-Horn clauses can be constructed. The clause inference is solved by the T-invariant method or the fixpoint of markings. Both forward and backward inference can be used in our model. It is further shown that these techniques are efficient for the common classes of monotonic reasoning. © 1998 John Wiley & Sons, Inc.

The IEEE 802.14 standard committee is currently working on a project to find a cost-effective means of providing access to integrated networks for people to enjoy multimedia programs and to work at home. An advanced system based on the CATV system called hybrid fiber coax (HFC) is being studied. Since some properties of the HFC system preclude the possibility of directly using existing medium access control protocols for its data link layer, a MAC scheme based on time division is discussed in this paper.

With the increased popularity of ATM technology and the high demand for multimedia applications in wireless systems, the interconnection between wireless systems and wired ATM networks becomes important to support multimedia applications. This paper presents an AAL3/4-based architecture for the interconnection between wireless and ATM networks. The main advantage of this architecture is that modification or additional functions are not necessary to the ATM layer to support mobility, and the ATM part of the connection is totally transparent to the mobiles so that the existing wireless protocols can be used without any change.

In this paper a new distributed adaptive admission control algorithm for wireless cellular networks with heterogeneous traffic is proposed. The resources needed for handoff calls are estimated by calculating the probability of visiting particular cells during the call lifetime based on the call duration and residence time statistics. This information is then communicated to the base stations in the S surrounding rings. The amount of reserved resources is updated at handoffs and call termination which involves simple arithmetic operations only. The admission algorithm also maintains the tuning parameters by which hard constraints on handoff dropping probabilities can be met. We have also derived the QoS bounds for homogeneous traffic.

The paper investigates the use of group communication to improve the efficiency of load balancing in interconnected LANs. Conventional load balancing techniques usually assume point-to-point connections among the computers and typically work on a single LAN only. This may waste network bandwidth and lengthen the load balancing time in LANs that support group communication such as the Ethernet. To tackle this problem a two level algorithm is proposed. At the LAN level, all computers in a LAN maintain loading information in the entire LAN using a globally ordered group channel. The workload in the different LANs is balanced by moving load from the overloaded LANs to the underloaded ones. It is proved that the proposed algorithm converges to the state of global balance geometrically. Experimental results show that the algorithm reduces load balancing time and network utilization significantly, compared to the single level algorithm without group communication.

We propose charging schemes for ATM networks based on the concept of virtual effective bandwidths (VEB). The VEBs were initially developed by the authors to support real-time connection admission control (CAC) in a framework where traffic sources with different quality of service (QoS) requirements are multiplexed into the same finite length queue. The VEBs allow different QoS requirements to be related which is important for charging purposes. We propose three charging schemes which can be included in real-time CAC: the first one depends solely on the resource requirements of the call; the second is dependent on resource as well as QoS requirements of the call; and the third is dependent on the current traffic intensity of the other connections also.

This paper presents the design philosophy and implementation of the BALANCE system. BALANCE is a flexible, network independent and computer architecture independent load balancing system which allows the building of reusable parallel and distributed applications. By implementing related services as bi generic servers with their connection endpoints registered in BALANCE, the clients can easily access the servers by server system calls. To demonstrate the flexibility of BALANCE, several widely different applications have been implemented and evaluated, including system servers, parallel and distributed applications and a scheduling testbed. The use of generic servers to improve system modularity and code reuse is also discussed. © 1997 John Wiley & Sons, Ltd.

An evolution is happening in the way that operating systems support the real-time requirements of their applications. The need to run real-time applications such as multimedia in the same environment as complex non-real-time servers and applications has motivated much interest in restructuring existing operating systems. Many issues related to thread scheduling and synchronization have been investigated. However, little consideration has been given to the flexibility and modularity required in the support of application-level scheduling needs, although it is well known that application requirements are diverse. In this paper, we describe a real-time scheduling abstraction which provides modularity and flexibility to the scheduling support of operating systems. Our design has been implemented using the Mach 3.0 kernel and a locally developed multiprocessor kernel (the r-kernel) as development platforms. © 1997 John Wiley & Sons, Ltd.

The problem of allocating task interaction graphs (TIGs) to heterogeneous computing systems to minimize job completion time is investigated. The only restriction is that the interprocessor communication cost is the same for any pair of processors. This is suitable for local area network based systems, such as Ethernet, as well as fully interconnected multiprocessor systems. An optimal polynomial solution exists if sufficient homogeneous processors and communication capacity are available. This solution is generalized to obtain two faster heuristics, one for the case of homogeneous processors and the other for heterogeneous processors. The heuristics were tested extensively with 60,900 systematically generated random TIGs and shown to be stable independent of the size of the TIG. A performance model is also proposed to predict the performance of the heuristic algorithms, and it is successful in explaining the experimental results qualitatively.

In this paper, we describe the design, implementation, and modeling of a runtime kernel to support the processor farm paradigm on multicomputers. We present a general topology-independent framework for obtaining performance models to predict the performance of the start-up, steady-state, and wind-down phases of a processor farm. An algorithm is described, which for any interconnection network determines a tree-structured subnetwork that optimizes farm performance. The analysis technique is applied to the important case of k-ary tree topologies. The models are compared with the measured performance on a variety of topologies using both constant and varied task sizes.

The design philosophy and implementation of the BALANCE system is described. BALANCE is a flexible, network independent and computer architecture independent load balancing system which is designed to support a wide range of software, including parallel and distributed applications as well as schedulers. The generic server and server system call structures are used as bases to enhance flexibility and to build complex services. BALANCE is not tied to a particular scheduling algorithm, rather the users are allowed to build their own schedulers. To demonstrate the flexibility and power of BALANCE, a set of system services and scheduling algorithms has been implemented and evaluated. A new delay scheduling algorithm which postpones the execution of jobs in high load situation is proposed. It is shown that this algorithm effectively improves system throughput and yet bounds the response times for the console commands.

A new technique is developed to analyze the cell loss behavior of individual connections in finite intervals for ATM networks. The technique is applied to partial buffer sharing (PBS) in deriving formulae for calculating cell loss rate and queue length distributions for each cell class in a single connection in finite intervals. To maximize network utilization, a new and more flexible cell loss control mechanism called threshold-based loss balancing (TLB) is proposed which restricts the violation probability of each cell class. Comparisons of TLB and PBS on selected operating conditions reveal that TLB can accept more connections under the same workload conditions. PBS is shown to be a special case of TLB.

With the advent of high speed networks, the future communication environment is expected to comprise a variety of networks with widely varying characteristics. The next generation multimedia applications require transfer of a wide variety of data such as voice, video, graphics, and text which have widely varying access patterns such as interactive, bulk transfer, and real-time guarantees. Traditional protocol architectures have difficulty in supporting multimedia applications and high-speed networks because they are neither designed nor implemented for such a diverse communication environment. In this paper, we analyze the drawbacks of traditional protocol architectures and propose two alternative architectures for the next generation high-speed network environment: Direct Application Association and Integrated Layered Logical Multiplexing. We implement sample protocol stacks for each of the above models using the most widely used protocol stack (TCP/UDP-IP-Ethernet) in the context of the x-kernel. The performance of these protocol architectures is shown to be comparable to that of a traditional protocol architecture. They win by enabling the key requirements (Application specific Quality of Service) and optimizations (Integrated Layer Processing) necessary for future communication environments.

This paper presents a framework for modeling and analyzing ATM admission control using Stochastic High Level Petri Net (SHLPN). SHLPN is chosen because it is a powerful graphical and mathematical modeling tool that is able to handle concurrent, asynchronous, nondeterministic and stochastic events. In addition, there exists a set of well-developed performance analysis techniques for SHLPN. This paper uses a hierarchical modeling technique to specify complex ATM network mechanisms using a top-down approach. However, in analyzing the performance of the network, a bottom-up approach is adopted. To tackle the state space explosion problem, a SHLPN model is decomposed into submodels. These subnets are independently evaluated with all possible population which are then substituted by transitions with approximate equivalent performance in the original model. The technique is illustrated by modeling and evaluating a specific connection admission control policy.

In this paper, an automatic protocol test case generator that generates both test sequence and test data is presented. The underlying model is an extended finite state machine (EFSM) and Estelle is used as the formal description language. First, test sequences are generated using a combined control and data flow testing method. A set of path conditions associated with each test sequence is obtained using symbolic execution techniques. By solving the path conditions as a group of constraints, test data are then automatically generated. A prototype system implementing the above procedures has been built. The system has been used to generate test cases for real protocols such as TP0, FDDI and LAPB, and has been integrated in the UBC protocol testing environment.>

This paper proposes an approach to modeling and evaluating the performance of communication protocols based on formal specifications. A combined extended finite state machine (EFSM) and queueing network model is presented which is more sophisticated than either technique alone. Furthermore, the model avoids the state space explosion problem which may arise by the use of reachability analysis on an EFSM. The approach is illustrated using a simple sliding window protocol written in the formal description technique Estelle.>

The authors present an approach that combines control flow and data flow analysis techniques to generate unified test sequences (UTSs) for testing protocols modeled as an extended finite-state machine (EFSM). The UTS has the same fault detection capability as the characterizing sequence (UIO, DS, or W) methods for the control part, and at the same time covers all paths that connect variable definitions and uses (all du-paths) for data flow testing. A transition dependence graph is proposed to represent the dependence relations between transitions needed to construct the test sequences. The executable UTS is then selected using constraint satisfaction problem (CSP) solution techniques and transition loop analysis.>

A concurrency model is presented, and concurrent events, concurrency blocks, global states, concurrency measures, communication deadlocks, and data races are defined based on the model. The model allows high-level abstractions to be used for understanding concurrent behaviors. Using the concept of concurrency blocks, it is shown how to compute concurrency measures efficiently. The results are applied to the formal description techniques Estelle and LOTOS to reason about and classify their concurrency behaviors.>

Communication software is an implementation of the communication protocols involved in a distributed system. In this paper we examine the important factors related to protocol design that affect testing and testability of communication software.>

A vital role of real-time kernels is to help applications meet real-time requirements. The common approach in existing kernel design methodology has been to replace the scheduler in the kernel according to the needs of the application. As new real-time applications with unconventional scheduling requirements continue to emerge, constantly changing the kernel results in it becoming less stable and less maintainable. We discuss the modularity problems associated with this adhoc approach. We propose a kernel design which solves many of the problems by providing a common real-time task model for all real-time applications. This model allows for much more flexibility in the implementation of application-level schedulers and at the same time encourages modularity in kernel and application design. The model has been implemented using the Mach 3.0 kernel as a development platform. The flexibility of our solution is illustrated by considering the demands placed on the kernel by a modern multimedia application.>

Abstract The paper describes a new performance monitoring tool, calledTmon, that has been developed to help application programmers understand the run‐time behavior of a parallel system and tune the performance of their programs. Tmon measures resource utilization and traces process activities transparently during execution. A global interrupt technique used by Tmon allows measurement tasks to be executed simultaneously on different processors and an accurate global clock to be maintained with minimal overhead. Experimental results indicate that both the accuracy and the overhead of the monitor are well within an acceptable range. We introduce a performance model from which it is possible to derive several different parallel programming metrics. A weighted critical path analysis tool is also presented that focusses the user's attention on those parts of the program whose modification would most improve performance. An example in which the tool is used successfully to improve the performance of a parallel application is also presented. Tmon is currently implemented on top of the Trollius Operating System and runs on a 74‐node transputer‐based multicomputer.

Group communication permits a single sender to communicate with multiple receivers. A nested group permits one or more of the receivers to be itself a group. Nested groups are particularly useful for reducing communication traffic on internetwork links and supporting subnetwork autonomy. A name graph model is used to characterize nested groups and formalize the problems of loops and duplications. The authors design and analyze a spanning shadow tree algorithm that detects potential loops and duplication. The algorithm is considered static because loops and duplicates are detected at the time of group membership modification rather than at the time a message is sent. The algorithm changes the system-level representation of the name graph in a transparent manner to avoid infinite loops and to suppress duplicated messages. The worst-case message complexity of name graph update operations is on the order of O( mod N mod /sup 2/), where mod N mod is the number of groups in the system. The complexity of updates can be justified, since run-time overhead for actual message communication is reduced.>

An efficient execution model for tree structured computations is presented. A general framework for analyzing the performance of this type of computation for any given topology is discussed. The framework is used to derive models for two widely used parallel programming strategies: processor farms and divide and conquer. The models were validated on a large multicomputer, and it was shown that their accuracy is such that they can be used to predict the performance of applications that use the above strategies. The use of these models to evaluate performance and to restructure the application to improve performance is discussed.>

A study on scheduling mixed real-time and nonreal-time traffic is presented. The work is motivated by the need to provide satisfactory performance tradeoffs in a dynamic load condition where the arrival rates and proportions of the real-time and nonreal-time packets vary with time. The authors first examine two threshold-based schemes, queue length threshold and minimum early threshold, and propose the corresponding adaptive schemes based on results from approximate analysis and simulation. The idea is to improve performance by adjusting tradeoff points adaptively as the arrival rates change. The authors further discuss the idea of integrating the two thresholds. The new algorithm ADP, is evaluated by simulation under various load conditions and compared with other common scheduling disciplines as well as an optimal offline algorithm. It is concluded that, by setting appropriate threshold functions in accordance with the requirements of applications, one can achieve satisfactory bounded loss ratio for real-time packets and acceptably low average delay for nonreal-time packets in a wide range of workload conditions.>

Relaxation of the strict consistency requirements usually found in distributed server architectures is advocated, with emphasis placed instead on the inherent ability of the applications implemented by clients and servers to tolerate inconsistency in the state or deal with the inconsistency in an application dependent manner. For example, inconsistency in name binding information may be detected by a client on attempting to access the named object and corrected by a customized protocol. With such a relaxed consistency, operations on the server state often do not require strict coordination among the group members, and may be realized with weak ordering constraints on group messages. Thus a high degree of concurrency and efficiency is possible without compromising correctness. Sample applications are described to illustrate the use of relaxed consistency in designing distributed servers.>

This paper generalizes group communications into nested groups for the internet environment. By using a name graph model, two problems in nested group name resolution are identified — resolution loops and resolution duplications. Existing approaches of solving these problems are surveyed and their shortcomings analyzed. The research contribution of this paper is the design and analysis of an algorithm which uses statically saved topology information of the name graph to detect and handle resolution and duplication loops at the time when group membership and/or group structure change. While preserving some necessary properties of loops, the algorithm transforms the name graph into one which avoids resolution loops and controls duplications. The communication complexity of the algorithm has an upper bound of Ο(|A|) in the worst case, where |A| is the number of arcs in the name graph.

A framework is presented for the design of application level store-and-forward message transfer systems. Flow control and congestion control issues in the message handling environment are discussed. A new model for message transport, the message stream, is proposed as a basis of the flow and congestion control functionality. Important design aspects, including message fragmentation and management of transit and recipient buffers, are addressed.>

The authors' premise is that applications have the ability to tolerate certain types of failures under certain situations. This may, in turn, relax the top-level constraint on failure recovery algorithms in the interprocess communication (IPC) layer and allow exploitation of the inherent tolerance of applications to failures in a systematic way to simplify failure recovery. Using this application-driven approach, the authors present a model of a distributed program based on the well-known client-server relationship among the processes of the program. The model reflects certain generic properties of the application layer that can be exploited by the IPC layer during failure recovery. New techniques as to how the properties can be used for recovery are outlined. The authors use remote procedure call and shared variable as communication abstractions for the client and the server processes in the program to communicate with one another. The simplicity and generality of the failure recovery renders the application-driven approach particularly useful in contemporary distributed systems which are large and heterogeneous and hence have complex failure modes.>

Application level message transfer systems, primarily used to transport electronic mail, have several unique characteristics that make using existing methods of dealing with deadlock impractical. The special requirements for the efficient transport of application level messages are discussed and a description of a hierarchical scheme that meets these requirements is given. For networks consisting of interconnected clusters of computers, the structured buffer pool technique can be combined with other deadlock-free message transport schemes to form a network-wide, deadlock-free message transport facility. A properly chosen hierarchical system has the advantages of the individual schemes while lessening the impact of their disadvantages. The hierarchical scheme is also applicable to packet-switched and datagram-based networks.

A model of remote procedure call (RPC) which reflects certain generic properties of the application layer that can be exploited by the RPC layer during failure recovery is presented. A technique of adopting orphans caused by failures, which is based on the model, is described. The technique minimizes the rollback which may be required in orphan-killing techniques. Algorithmic details of the adoption technique are described, and a quantitative analysis is presented. The model is implemented as a prototype on a local area network. The simplicity and generality of the failure recovery renders the RPC model useful in distributed systems, particularly those that are large and heterogeneous and hence have complex failure modes.>

The design and implementation of a reliable group communication mechanism is presented. The mechanism guarantees a form of atomicity in that the messages are received by all operational members of the group or by none of them. Since the overhead in enforcing the order of messages is nontrivial, the mechanism provides two types of message transmission: one guarantees delivery of the messages in the same order to all members of a group, and the other guarantees only atomicity with messages delivered in some arbitrary order. The message-ordering property can be used to simplify distributed database and distributed processing algorithms. The mechanism can survive despite process, host, and communication failures.>

The authors examine the design and performance of LNTP, a connection-orientated transport-level protocol for local area networks (LANs) in the 4.2 BSD Unix operating system. Various measurements are taken, and LNTP's performance is compared to that of TCP/IP (ARPAnet's Transmission Control Protocol), a LHN protocol which is often used in LAN environments. The optimum values of various LNTP parameters are determined, some theoretically and others empirically. The theoretical results are compared to the experimentally observed values. It is concluded that LNTP does indeed outperform TCP/IP. However, due to the overhead of the non-LNTP specific protocol layers, this improvement is not as great as it might be. Nonetheless, LNTP proves itself to be a viable replacement for TCP/IP.>

Abstract This paper presents a methodology in generating space‐efficient code for BCPL and BCPL‐like programming languages. An intermediate language called ICE was designed which, while preserving those program features salient to translation, also tries to minimize the number of instructions generated. This internal representation is then realized as an actual machine. The encoding scheme (called ES0) is based on usage frequencies of instructions and other real world constraints on machines such as word size and addressing space. Using a large sample of BCPL programs, it is shown that BCODE, which is a realization of OCODE (the intermediate language currently used for BCPL program translation), takes up an average of 32 per cent more space as compared to ICE/ES0.

This paper presents, using queuing theory and optimization techniques, an approach for estimating the optimal capacities and speeds of the memory levels in a memory hierarchy operating in the multiprogrammed environment. Optimality is defined with respect to mean system response time under a fixed cost constraint. It is assumed that the number of levels in the hierarchy as well as the capacity of the lowest level are known. The effect of the storage management strategy is characterized by the miss ratio function which, together with the device technology cost functions, is assumed to be representable by power functions. It is shown that as the arrival rate of processes and/or the number of active processes in the system increase, the optimal solution deviates considerably from that under a uniprogrammed environment. It is also shown that the solution obtained is the global optimum.