Today’s software development landscape has witnessed a shift towards microservices based architectures. Using this approach, large software systems are implemented by combining loosely-coupled services, each responsible for specific task and defined with separate scaling properties. Auto-scaling is a primary capability of cloud computing which allows systems to adapt to fluctuating traffic loads by dynamically increasing (scale-up) and decreasing (scale-down) the number of resources used.We observe that when microservices which utilize separate auto-scaling mechanisms operate in tandem to process traffic, they may perform ineffectively, especially under overload conditions, due to DDoS attacks. This can result in throttling (Denial of service - DoS) and over-provisioning of resources (Economic Denial of Sustainability - EDoS).This paper demonstrates how an attacker can exploit the tandem behavior of microservices with different auto-scaling mechanisms to create an attack we denote as the Tandem Attack. We demonstrate the attack on a typical Serverless architecture and analyze its economical and performance damages. One intriguing finding is that some attacks may make a cloud customer paying for service denied requests.We conclude that independent scaling of loosely coupled components might form an inherent difficulty and end-to-end controls might be needed.

Deployment of anti-virus software is a common strategy for preventing and controlling the propagation of computer viruses and worms over a computer network. As the deployment of such programs is often limited due to monetary or operational costs, devising optimal strategies for their allocation and deployment can be of high value to the operation, performance, and resilience of the target networks.We study the effects of anti-virus deployment (i.e., “vaccination”) strategies on the ability of a network to block the spread of a virus. Such ability is obtained when the network reaches “Herd Immunity”, achieved when a large fraction of the network entities is immune to the infection, which provides protection even for entities which are not immune. We use a model that explicitly accounts for the inherent heterogeneity of network nodes activity and derive optimal strategies for anti-virus deployment.

Geographically distributed cloud networks are used by a variety of applications and services worldwide. As the demand for these services increases, their data centers form an attractive target for malicious attackers, aiming at harming the services. In this study we address sophisticated attackers who aim at causing maximal-damage to the service. A worst-case (damage-maximizing) attack is an attack which minimizes the revenue of the system operator, due to disrupting the users from being served. A sophisticated attacker needs to decide how many attacking agents should be launched at each of the systems regions, in order to inflict maximal damage. We characterize and analyze damage-maximization strategies for a number of attacks including deterministic attack, concur-rent stochastic agents attack, approximation of a virus-spread attack and over-size binomial attack. We also address user-migration defense, allowing to dynamically migrate demands among regions, and we provide efficient algorithms for deriving worst-case attacks given a system with arbitrary placement and demands. The results form a basis for devising resource allocation strategies aiming at minimizing attack damages.

We investigate cellular networks supported by on-street parked vehicles, termed as Vehicular Relay Nodes (VeRN), which have been proposed to boost performance and scale the network to varying demands. We study the problems of Call Admission and Call Assignment, which are key to efficient operation. To achieve an efficient and practical solution, we propose to decouple this problem and solve it via two weakly-coupled algorithms. For Admission, we formulate a non-trivial Markov Decision Process, introducing a dynamic operator that stochastically accounts for the possible assignments. For the Assignment problem, we derive a local Deep Reinforcement Learning algorithm using Imitation Learning, while introducing several novel improvements. Performance evaluation shows that these strategies offer a significant improvement over baselines.

We investigate the performance of a new deployment concept in cellular networks, in which on-street parked vehicles, termed Vehicular Relay Nodes (VeRN), are opportunistically activated to become a Relay Node (RN) in the cellular infrastructure, and boost the overall deployment performance. Analyzing the performance of such network, versus traditional stationary cellular deployment, is challenging, due to the dynamic nature of vehicles. We examine the gain of VeRNs for various user locations in a cellular deployment. We provide an exact analysis of the VeRN expected gain that incorporates the dynamic behavior of the parked vehicle network. We further provide a closed-form approximation of this gain. Our results show that under the well-known WINNER-II channel model the gains are very significant (125 -300% gain in throughput). Simulation results show that our approximation closely follows actual network performance, and the positive influence of VeRN on network capacity.

We consider the problem of how to place and efficiently utilize resources in network environments. The setting consists of a regionally organized system which must satisfy regionally varying demands for various resources. The operator aims at placing resources in the regions as to minimize the cost of providing the demands. Examples of systems falling under this paradigm are 1) A peer supported Video on Demand service where the problem is how to place various video movies, and 2) A cloud-based system consisting of regional server-farms, where the problem is where to place various contents or end-user services. The main challenge posed by this paradigm is the need to deal with an arbitrary multi-dimensional (high-dimensionality) stochastic demand. We show that, despite this complexity, one can optimize the system operation while accounting for the full demand distribution. We provide algorithms for conducting this optimization and show that their complexity is pretty small, implying they can handle very large systems. The algorithms can be used for: 1) Exact system optimization, 2) deriving lower bounds for heuristic based analysis, and 3) Sensitivity analysis. The importance of the model is demonstrated by showing that an alternative analysis which is based on the demand means only, may, in certain cases, achieve performance that is drastically worse than the optimal one.

In recent years, we have experienced a wave of DDoS attacks threatening the welfare of the internet. These are launched by malicious users whose only incentive is to degrade the performance of other, innocent, users. The traditional systems turn out to be quite vulnerable to these attacks. The objective of this work is to take a first step to close this fundamental gap, aiming at laying a foundation that can be used in future computer/network designs taking into account the malicious users. Our approach is based on proposing a metric that evaluates the vulnerability of a system. We then use our vulnerability metric to evaluate a data structure which is commonly used in network mechanisms-the Hash table data structure. We show that Closed Hash is much more vulnerable to DDoS attacks than Open Hash, even though the two systems are considered to be equivalent by traditional performance evaluation. We also apply the metric to queuing mechanisms common to computer and communications systems. Furthermore, we apply it to the practical case of a hash table whose requests are controlled by a queue, showing that even after the attack has ended, the regular users still suffer from performance degradation or even a total denial of service.

Channel aware schedulers of modern wireless networks - such as the popular Proportional Fairness Scheduler (PFS) - improve throughput performance by exploiting channel fluctuations while maintaining fairness among the users. In order to simplify the analysis, PFS was introduced and vastly investigated in a model where frame losses do not occur, which is of course not the case in practical wireless networks. Recent studies focused on the efficiency of various implementations of PFS in a realistic model where frame losses can occur. In this work we show that the common straight forward adaptation of PFS to frame losses exposes the system to a malicious attack (which can alternatively be caused by malfunctioning user equipment) that can drastically degrade the performance of innocent users. We analyze the factors behind the vulnerability of the system and propose a modification of PFS designed for the frame loss model which is resilient to such malicious attack while maintaining the fairness properties of original PFS.

Channel-aware scheduling strategies - such as the CDF Scheduler (CS) algorithm for the CDMA/HDR systems - provide an effective mechanism for utilizing the channel data rate for improving throughput performance in wireless data networks by exploiting channel fluctuations. A highly desired property of such a scheduling strategy is that its algorithm will be stable, in the sense that no user has incentive "cheating" the algorithm in order to increase his/her channel share (on the account of others). We present a scheme by which coordination allows a group of users to gain permanent increase in both their time slot share and in their throughput, on the expense of others, by misreporting their rates. We show that for large populations consisting of regular and coordinated users in equal numbers, the ratio of allocated time slots between a coordinated user and a regular one converges to e - 1 ap 1.7. Our scheme targets the very fundamental principle of CS (as opposed to just attacking implementation aspects), which bases its scheduling decisions on the cumulative distribution function (CDF) of the channel rates reported by users. Our scheme works both for the continuous channel spectrum and the discrete channel spectrum versions of the problem.

Mobile wireless network research focuses on scenarios at the extremes of the network connectivity continuum where the probability of all nodes being connected is either close to unity, assuming connected paths between all nodes (mobile ad hoc networks), or it is close to zero, assuming no multi-hop paths exist at all (delay-tolerant networks). In this paper, we argue that a sizable fraction of networks lies between these extremes and is characterized by the existence of partial paths, i.e., multi-hop path segments that allow forwarding data closer to the destination even when no end-to-end path is available. A fundamental issue in such networks is dealing with disruptions of end-to-end paths. Under a stochastic model, we compare the performance of the established end-to-end retransmission (ignoring partial paths), against a forwarding mechanism that leverages partial paths to forward data closer to the destination even during disruption periods. Perhaps surprisingly, the alternative mechanism is not necessarily superior. However, under a stochastic monotonicity condition between current vs. future path length, which we demonstrate to hold in typical network models, we manage to prove superiority of the alternative mechanism in stochastic dominance terms. We believe that this study could serve as a foundation to design more efficient data transfer protocols for partially-connected networks, which could potentially help reducing the gap between applications that can be supported over disconnected networks and those requiring full connectivity.

The design of computer and communication systems has been based, for decades, on the fundamental assumption that the objective of all users is to improve their own performance. In recent years we have experienced a wave of DDoS attacks threatening the welfare of the Internet. These are launched by malicious users whose pure incentive is to degrade the performance of other, innocent, users. The traditional systems turn out to be quite vulnerable to these attacks. The objective of this work is to take a first step to close this fundamental gap, aiming at laying a foundation that can be used in future computer/network designs taking into account the malicious users. Our approach is based on proposing a metric that evaluates the vulnerability of a system. We then evaluate the commonly used data structure in network mechanisms, the hash data structure, using our vulnerability metric. We show that a Closed Hash is much more vulnerable than an Open Hash to DDoS attacks, even though the two systems are considered to be equivalent via traditional performance evaluation. We also apply the metric to queueing mechanisms common to computer and communications systems. Lastly we apply it to the practical case of a hash table whose requests are controlled by a queue, showing that even after the attack has ended, the regular users still suffer from performance degradation or even a total denial of service.

Network routing may be required, under certain applications, to avoid certain areas (or nodes). These areas can be of potential security threat, possess poor quality or have other undesired characteristics. Thus, protocols that can perform area avoidance routing can be beneficial for many objectives. Such routing is particularly challenging in distance-vector networks, where only the shortest-distance information is available to the nodes. We address this challenge by algorithms that retrieve distance-vector information from other nodes in the network, referred to as reference nodes, and exploit it for computing guaranteed area-avoiding paths. Having these paths, the source can direct the packets using loose source routing towards the destination. We lay out the model for area avoidance routing and study several algorithms for calculating area-avoiding paths. In addition, we address the problem of dynamically selecting reference nodes. We show, through analysis and extensive simulation, that in many cases a small number of reference nodes are sufficient for area avoidance routing.

Traditional network routing uses the single (shortest) path paradigm. This paradigm exposes sessions to various attacks along this path, such as eavesdropping, DoS attacks etc. As a result, certain nodes or network regions may pose security threats and it is desired to consider node routing schemes which avoid them. The task of node avoidance routing is particularly challenging in distance-vector networks, where only shortest-distance information is available to the nodes. We address this problem by proposing a new routing paradigm in which the forwarding mechanism exploits the distance-vector information towards several nodes and utilizes it to forward network traffic on non-shortest paths routes; in particular on node-avoiding routes aiming at bypassing security-suspected nodes. We study this paradigm, propose a routing algorithm based on it and establish their properties. Extensive evaluation of the algorithm in general situations is conducted via simulation.

Abstract — Traditional network routing uses the single (shortest) path paradigm. This paradigm leaves the session vulnerable to a variety of security threats, such as eavesdropping. We propose to overcome this via dispersive routing, conducted over multiple paths. This increases significantly the costs inflicted on an attacker who wishes to eavesdrop sessions by hijacking network links (or routers). We formulate the Security Traffic Manager (STM) problem (route session fragments 1, over multiple paths, so that protection against an attacker, with a known hijacking budget, is guaranteed) and the attacker problem (find the cheapest hijacking strategy). The problems are analyzed for cases in which the attacker must eavesdrop all the fragments as well for cases in which it must eavesdrop only a fraction of them. We analyze the theoretical complexity of these problems and offer algorithms for finding dispersive routes that guarantee security. Though some theoretical cases of the problem are shown to be NP-Hard, typical practical cases can be solved by polynomial time algorithms. We extend the STM problem to more practical situations where the goal of the STM is to guarantee privacy, using minimal number of limited-length paths. The algorithms are tested through simulation and shown to be efficient in many scenarios. The model and algorithms offered in this study can be used for deploying a “session enhanced security ” service in packet networks 2. Keywords-component; traffic dipersion, security, eavesdrop, multi-path routing I.

In this paper a new mechanism called aggressiveness protective queuing (APQ), is described to control traffic in network devices. The method is based on the principles of the WFQ scheme and which uses dynamic weights for its operation. APQ uses a simple mechanism for tracking the resource usage by the flows and uses this accounting to properly and dynamically control the weights of WFQ. Also analytic results and simulation results are provided to demonstrate the effectiveness of APQ in controlling bursty traffic

A new approach for filtering spoofed IP packets, called spoofing prevention method (SPM), is proposed. The method enables routers closer to the destination of a packet to verify the authenticity of the source address of the packet. This stands in contrast to standard ingress filtering which is effective mostly at routers next to the source and is ineffective otherwise. In the proposed method a unique temporal key is associated with each ordered pair of source destination networks (AS's, autonomous systems). Each packet leaving a source network S is tagged with the key K(S, D), associated with (S, D), where D is the destination network. Upon arrival at the destination network the key is verified and removed. Thus the method verifies the authenticity of packets carrying the address s which belongs to network S. An efficient implementation of the method, ensuring not to overload the routers, is presented. The major benefits of the method are the strong incentive it provides to network operators to implement it, and the fact that the method lends itself to stepwise deployment, since it benefits networks deploying the method even if it is implemented only on parts of the Internet. These two properties, not shared by alternative approaches, make it an attractive and viable solution to the packet spoofing problem.

This work aims at studying the fairness of multi-queue and multi-server queueing systems. We deal with the issues of queue-multiplicity, queue joining policy and queue jockeying and use a quantitative measure (RAQFM) to evaluate them. Our results yield the relative fairness of the mechanisms as a function of the system configuration and parameters. Practitioners can use these results to quantitatively account for system fairness and to weigh efficiency aspects versus fairness aspects in designing and controlling their queueing systems. In particular, we quantitatively demonstrate that: 1) Joining the shortest queue increases fairness, 2) A single "combined" queue system is more fair than "separate" (multi) queue system and 3) Jockeying from the head of a queue is more fair than jockeying from its tail.

Next generation networks (NGN) and the migration towards IP networks is likely to make the IP technology the main vehicle for earning voice and video calls on modern networks. Packet dispersion is a mechanism by which the packets of a certain session are dispersed over multiple paths, in contrast to the traditional approach by which they follow a single path most of the time. In this work we examine the quality of voice over IP (VoIP) applications and the effects of packet dispersion on it. We focus on the effect of the network loss on the applications, where we propose to use noticeable loss rate (NLR) as a measure correlated with the voice quality. We analyze the NLR for various packet dispersion strategies over paths experiencing memory-less (Bernoulli) or bursty (Gilbert model) losses, and compare them to each other. Our analysis reveals, that in many situations, in particular for most cases where losses are bursty, the use of packet dispersion reduces the NLR and thus improves session quality. The results suggest that the use of packet dispersion can be quite beneficial for these applications.

No abstract available.

Fairness is a major issue in the operation of queues, perhaps it is the reason why queues were formed in the first place. Recent studies show that the fairness of a queueing system is important to customers not less than the actual delay they experience. Despite this observation little research has been conducted to study fairness in queues, and no commonly agreed upon measure of queue fairness exists. Two recent research exceptions are Avi-Itzhak and Levy [1], where a fairness measure is proposed, and Wierman and Harchol-Balter [18] (this conference, 2003), where a criterion is proposed for classifying service policies as fair or unfair; the criterion focuses on customer service requirement and deals with fairness with respect to service times.In this work we recognize that the inherent behavior of a queueing system is governed by two major factors: Job seniority (arrival times) and job service requirement (service time). Thus, it is desired that a queueing fairness measure would account for both. To this end we propose a Resource Allocation Queueing Fairness Measure, (RAQFM), that accounts for both relative job seniority and relative service time. The measure allows accounting for individual job discrimination as well as system unfairness. The system measure forms a full scale that can be used to evaluate the level of unfairness under various queueing disciplines. We present several basic properties of the measure. We derive the individual measure as well as the system measure for an M/M/1 queue under five fundamental service policies: Processor Sharing (PS), First Come First Served (FCFS), Non-Preemptive Last Come First Served (NP-LCFS), Preemptive Last Come First Served (P-LCFS), and Random Order of Service (ROS). The results of RAQFM are then compared to those of Wierman and Harchol-Balter [18], and the quite intriguing observed differences are discussed.

Web caches have become an integral component contributing to the improvement of the performance observed by Web clients. Cache satellite distribution systems (CSDSs) have emerged as a technology for feeding the caches with the information clients are expected to request, ahead of time. In such a system, the participating proxies periodically report to a central station about requests received from their clients. The central station selects a collection of Web documents, which are "pushed" via a satellite broadcast to the participating proxies, so that upon a future local request for the documents, they will already reside in the local cache, and will not need to be fetched from the terrestrial network. In this paper, our aim is addressing the issues of how to operate the CSDS, how to design it, and how to estimate its effect. Questions of interest are: 1) what Web documents should be transmitted by the central station and 2) what is the benefit of adding a particular proxy into a CSDS? We offer a model for CSDS that accounts for the request streams addressed to the proxies and which captures the intricate interaction between the proxy caches. Unlike models that are based only on the access frequency of the various documents, this model captures both their frequency and their locality of reference. We provide an analysis that is based on the stochastic properties of the traffic streams that can be derived from HTTP logs, examine it on real traffic, and demonstrate its applicability in selecting a set of proxies into a CSDS.

One of the major problems faced in operating large networks is the enormous amount of processing and communications overhead required for setting up and tearing down the large number of connections maintained by the network. ATM and MPLS aim at solving these problems via the Virtual Path (VP) mechanism which is used to group together the connections. When a need for setting up a connection rises, the request and its resource allocation are processed by the VP agent and not by the network, thus reducing the processing cost significantly. An important question in the design of these networks is the amount of network resources to be dynamically allocated to and held by the VP agents; too high allocation will result with bandwidth resource waste, while too low allocation will result with heavy connection set-up and tear-down processing load. In this paper we deal with this problem, and at deriving simple operational rules to determine the amount of bandwidth resources to be held by the various VP agents, while balancing between bandwidth waste and connection processing overhead. We formulate the resource allocation problem by accounting both for bandwidth utilization and for connection processing constraints. Recognizing the complexity of the problem, we use a decomposition approach in which we first analyze the single link problem and then propose to use this solution as a building block in constructing algorithms for the whole network. For the single link problem we realize that the pure problem is too complex and thus formulate an approximate model and derive the optimal allocation for it. The optimal rule is expressed as a closed-form square-root allocation. Extensive numerical examination shows that the rule proposed yields very efficient allocations. For the full network problem, we propose to capitalize on the closed form structure of the single link problem solution and use it in devising algorithms for the whole network.

Web caches have become an integral component contributing to the improvement of the performance observed by Web clients. Content Distribution Networks (CDN) and Cache Satellite Distribution Systems (CSDS) have emerged as technologies for feeding the caches with the information clients are expected to request, ahead of time. In a Cache Satellite Distribution System (CSDS), the proxies participating in the CSDS periodically report to a central station about the requests they are receiving from their clients. The central station processes this information and selects a collection of Web documents (or "Web pages"), which it then "pushes" via a satellite broadcast to all, or some, of the participating proxies, hoping most of them will request most documents in the near future. The result is that upon such request, the documents will reside in the local cache, and will not need to be fetched. In this paper we aim at addressing the issues of how to operate the CSDS, how to design it, and how to estimate its effect. Questions of interest are 1) what classes of Web documents should be transmitted by the central station, and how they are characterized, and 2) what is the benefit of adding a particular proxy into a CSDS. We offer a model of this system that accounts for the request streams addressed to the proxies and which captures the intricate interaction between the proxy caches. Unlike models that are based only on the access frequency of the various documents, this model captures both their frequency and their locality of reference. We provide an analysis of this system that is based on the stochastic properties of the traffic streams that can be derived from HTTP logs. The model and analysis can serve as a basis for the design and efficient operation of the system.

A multiple access protocol that is particularly suitable for cellular Internet access and satellite-based networks with on-board processing is developed. The basic idea is that when a user wishes to send a message, it transmits with a probability p/sub access/ that depends on the load on the channel. Under conditions of low load, the probability p/sub access/ approaches 1, while at high load p/sub access/ is relatively low. This media access control protocol guarantees high channel utilization at high load, as well as low delay at low load periods. Using the statistical usage of the shared channel, the load is estimated with certain uncertainty. Our analysis shows that using the statistical usage of the shared channel, the optimal access probability can be well estimated for a broad class of load distribution patterns. In addition, we propose to use a central station to broadcast the value of p/sub access/ in networks with poor collision detection capability, or long feedback delay. The proposed method is particularly suitable for shared channels with poor collision detection capability, under conditions of bursty traffic and a large number of users. Examples for such channels are the reservation channel in satellite-based networks with on-board processing, and the control channel in cellular networks. Hence, the proposed method can be used for cellular Internet access and for accessing public satellite-based networks. The broadcast mechanism that already exists in such networks can be used to inform the users the dynamic access probability.

One of the major problems faced by large networks is the enormous amount of processing required for setting up and tearing down the large number of connections maintained by the network. ATM aims at solving these problems via the virtual path (VP) mechanism which is used to group together the virtual connections (VC). When a need for setting up a VC arises the request and its resource allocation are processed by the VP authority and not by the network, thus reducing the processing cost significantly. An important question in the design of these networks is the amount of network resources to be allocated to and held by the VP authorities; too high an allocation will result in resource waste, while too low an allocation will result in heavy connection set-up and tear-down processing load. In this paper we deal with this problem, aiming at deriving simple operational rules to determine the amount of bandwidth resources to be held by the various VP authorities. We formulate the resource allocation problem by accounting both for bandwidth utilization and for connection processing constraints. For a single link network we realize that the pure problem is too complex and thus formulate an approximate model and derive the optimal allocation for it. The optimal rule is expressed as a closed-form square root allocation. Extensive numerical examination shows that the algorithms proposed yield very efficient allocations. The single link model is then generalized to a general network model and an algorithm based on the single link allocation is proposed; that analysis is however beyond the scope of this paper.

Location management is a crucial issue in wireless networks. The problem of tracking mobile users has been addressed by several studies, many of which attempt to reduce the wireless cost of users tracking. The basic idea shared by most of these works is that users update their location based on a pre-defined criterion. Unfortunately, some of these strategies require the use of information, such as the distance traveled from the last known location, that is not generally available to the user. For this reason, both the implementation of some of these strategies and the performance comparison to existing strategies is not clear. We propose to use cell identification codes (CIC) for tracking mobile users. Each cell periodically broadcasts a short message which identifies the cell and its orientation relatively to other cells in the network. This information is used by the users to efficiently update their location. We propose several cell identification encoding schemes, which are used to implement different tracking strategies. The best performance is achieved by a four-bit CIC, used to implement a distance-based tracking strategy in a two dimensional system. In addition, we propose a combination of timer and movement tracking strategy, based on either a one-bit or a two-bit CIC, depending on system topology and user mobility. An important property of our framework is that the overall performance cost, and hence its comparison to existing methods, is evaluated for each tracking strategy. The CIC-based strategies are shown to outperform the timer-based method over a wide range of parameters.

This paper deals with the sizing of end buffers in ATM networks for sessions subject to constant bit rate (CBR) traffic. Our objective is to predict the cell-loss rate at the end buffer as a function of the system parameters. We introduce the D+G/D/1 queue as a generic model to represent exit buffers in telecommunications networks under constant rate traffic, and use it to model the end buffer. This is a queue whose arrival rate is equal to its service rate and whose arrivals are generated at regular intervals and materialize after a generally distributed random amount of time. We reveal that under the infinite buffer assumption, the system possesses rather intriguing properties: on the one hand, the system is unstable in the sense that the buffer content is monotonically nondecreasing as a function of time. On the other hand, the likelihood that the buffer contents will exceed certain level B by time t diminishes with B. Improper simulation of such systems may therefore lead to false results. We turn to analyze this system under finite buffer assumption and derive bounds on the cell-loss rates. The bounds are expressed in terms of simple formulae of the system parameters. We carry out the analysis for two major types of networks: (1) datagram networks, where the packets (cells) traverse the network via independent paths and (2) virtual circuit networks, where all cells of a connection traverse the same path. Numerical, examination of ATM-like examples show that the bounds are very good for practical prediction of cell loss and the selection of buffer size.

Mobile user tracking is a major issue. We propose a novel approach for user tracking, in which the tracking activity is adapted to both user and system activity. The basic idea is to make the user-location update-rate dependent not only on the user activity (such as the call profile and mobility pattern). Rather, it is also made dependent on the signaling load, which reflects the actual cost of the update operation. Thus, at low-signaling load locations, the users are to transmit location update messages more frequently. To carry out this approach, we propose a load-adaptive threshold scheme (LATS): the network determines for each cell a registration threshold level (which depends on the cell load) and announces it, as a broadcast message, to the users. The user computes its own registration priority and then transmits a registration message only if its priority exceeds the announced threshold level. Thus, whenever the local load on the cell is low, the registration activity increases, while in loaded cells the registration activity decreases. Our analysis shows that the LATS reduces the paging cost, in comparison with other dynamic methods, without increasing the wireless cost of registration. Moreover, if higher user density is coupled with less mobility (e.g., consider vehicles), then the LATS strategy offers further performance improvement. The load-adaptive strategy can be used in addition to any other dynamic tracking strategy. Furthermore, the computational complexity imposed on the user is identical to that required by an equivalent load-insensitive scheme.

This paper deals with the sizing of end buffers in ATM networks for sessions subject to constant bit rate (CBR) traffic. Our objective is to predict the cell loss rate at the end buffer as a function of the system parameters. We introduce the D+G/D/1 queue as a generic model to represent exit buffers in telecommunications networks under constant rate traffic and use it to model the end buffer. This is a queue whose arrival rate is equal to its service rate and whose arrivals are generated at regular intervals and materialize after generally distributed random amount of time. We reveal that under the infinite buffer assumption the system possesses rather intriguing properties. On the one hand it is unstable, so that the "steady state" contents of the buffer may exceed any value. On the other hand, in practice, the likelihood of the buffer exceeding even small values is very small. Improper simulation of such systems may therefore lead to false results. We analyze this system under finite buffer assumption and derive bounds on the cell loss rates. The bounds are expressed in terms of simple formulae of the system parameters. We carry out the analysis for two major types of networks: (1) datagram networks, where the packets (cells) traverse the network via independent paths, and (2) virtual circuit networks, where all cells of a connection traverse the same path. Numerical examination of ATM-like examples show that the bounds are very good for practical prediction of cell loss and the selection of buffer size.

Mobile user tracking is a major issue in wireless networks. Previous studies and traditional approaches dealt only with tracking algorithms which adapt themselves to the user activity. In this

Given N request streams and L/spl les/N LRU caches, the cache assignment problem asks to which cache each stream should be assigned in order to minimize the overall miss rate. An efficient solution to this problem is provided, based on characterizing each stream using the stack reference model and characterizing the interaction of the streams using a bursty stream model. It is shown that for Bernoulli (purely random) mixing of streams, the optimal cache assignment is to have one cache per stream. In practice streams are mixed in a way that is much "burstier" than can be represented by the Bernoulli model. Therefore a method is presented for superposition of bursty streams. The performance of the methods developed for bursty stream superposition and cache assignment are tested using trace data obtained from the database system DB2. The resulting cache assignment recommendations are then applied to the DB2 system, and considerable performance improvement is found to result.

Time limits are the major mechanisms used for controlling a large variety of multistation single-medium computer-communication systems like the FDDI network and the IEEE 802.4 Token Bus. The proper use of these mechanisms is still not understood and rules for efficient system operation are not available. The authors' objective is the derivation of such rules. They use a cyclic polling model with different service limits (k-limited service) at the different queues, thus emulating time limits. They are interested in determining these k-limit values so as to minimize the mean waiting cost of messages in the system. A simple approximative approach is proposed for two major problems: one in which a limit is set on the token rotation time and one in which no limits are imposed. The approach is tested for a variety of cases and is shown to be very effective.>

We present an exact analysis of the superposition of address streams into a cache buffer which is managed according to a least recently used (LRU) replacement policy. Each of the streams is characterized by a stack depth distribution, and we seek the cache hit ratio for each stream, when the combined, or superposed, stream is applied to a shared LRU cache. The combining process is taken to be a Bernoulli switching process. This problem arises in a number of branches of computer science, particularly in database systems and processor architecture. Previously, a number of approximation techniques of various complexities have been proposed for the solution of this problem. The main contribution of the paper is the description of an exact technique. We evaluate the performance of the exact and an approximate technique on realistic data, both in a lab environment and a large database installation. The results allow comparisons of the techniques, and provide insight into the validity of the Bernoulli switching assumption.>

Polling systems have been used to model a large variety of applications and much research has been devoted to the derivation of efficient algorithms for computing the delay measures in these systems. Recent research efforts in this area, which have focused on the optimization of these systems, have raised the need for very efficient such algorithms. This work develops the descendant set approach as a general efficient algorithm for deriving all moments of customer delay (in particular, mean delay) in these systems. The method is applied to a very large variety of model variations, including: 1) The exhaustive and gated service policies, 2) Fractional service policies, 3) The cyclic visit order, 4) Arbitrary periodic visit orders (polling tables), and 5) Customer routing. For most of these variations the method significantly outperforms the algorithms commonly used today.>

Pseudocyclic algorithms that can prioritize the various stations by dynamically changing their service order but maintain fairness by visiting each station exactly once in a cycle re considered. The waiting time performance of systems operated under cycle-time guided algorithms in semi-dynamic polling models is studied. In fully symmetric systems the waiting times of all pseudocyclic policies are bounded by stochastic dominance. This dominance is quantified by the analysis of a fluid approximation model and simulations of the general polling model.>

A large variety of computer communications systems, in particular the token ring network, are modeled and analyzed as polling systems. The authors present the descendant set approach as a general efficient algorithm for deriving all moments of packet delay (in particular, mean delay) in these systems. The method can apply to a very large variety of model variations including: the exhaustive, gated, and fractional service policies; the cyclic visit order; arbitrary periodic visit orders, (polling tables); random polling orders; and customer routing. For most variations the method significantly outperforms the algorithms commonly used.>

A class of computer systems whose primary task is the massive processing of batch transitions and which are called transaction-driven computer systems (TDCSs) is modeled and analyzed. A generic queuing model for transaction-driven computer systems is presented, and the mean sojourn time experienced by the different transactions is calculated. The approach is to model a TDCS by a cyclic polling system with bulk arrivals, deterministic service times, limited-one service, and zero switch-over periods. Since the performance analysis of this polling model has not been provided before, the emphasis is on deriving mean delay approximations for it. The analysis is carried out for models with general switch-over periods, and a special case of it (zero switch-over periods) is suitable for analyzing a TDCS.< >

The binomial-gated service, designed for cyclic polling systems, is proposed as a new service method. The important properties of this method are: (1) it allows one to prioritize the system queues using a set of priorities, and (2) it is mathematically analyzable. The method can be implemented in the token ring network and in many other communications systems. The nonsymmetric cyclic-polling system with binomial-gated service is analyzed and equation sets are derived from which the expected delay figures can be calculated numerically. A pseudoconservation law for nonsymmetric systems and a closed-form mean-delay expression for fully symmetric systems are derived as well. The effect of the priority parameters on the system performance is demonstrated in numerical examples.>

The authors analyze polling systems with multiple types of simultaneous arrivals, namely, batches of customers may arrive at the different queues at an arrival epoch. The authors consider cyclic polling systems with N queues, general service time distribution in each queue, and general switchover times. For both the exhaustive and the gated service disciplines the authors derive the necessary equations for computing the N expected waiting time figures. A pseudo conservation law for these system is also derived. The authors compare several special cases of the correlated arrivals polling system, discuss the computational aspects of the numerical method, and examine the applicability of the analysis to other polling systems.>

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

The cyclic polling model, its enhancement by customer routing, and the replacement of a fixed polling order by a random polling order are reviewed. Modeling of polling systems, performance improvement, and system optimization issues are discussed. Examples are given that include token rings, ARQ and time-sharing schemes, random-access protocols, robotics and manufacturing systems. Emphasis is not on the analytical derivations of polling systems but rather on the description of the capabilities and limitations of the different polling models.>

An analysis is made of polling systems with correlated arrivals, namely, systems in which the arrival processes of customers to the queues are not assumed to be independent. The authors consider cyclic polling systems with N queues, general service time distribution in each queue, and general switch-over times. For both the exhaustive and the gated service disciplines they derive the necessary equations for computing the N expected waiting time figures. A 'pseudo' conservation law for these systems is also derived. The analysis approach can be applied to other polling systems with correlated arrivals.>

Consideration is given to the problem of dynamically controlling a computer communication network consisting of N stations that compete for the use of a single channel. The channel is needed by the stations in order to transfer the packetized information they got from independent sources to a central storage device. The stations, which have some local storage capacity, are modeled as finite queues fed by independent Poisson streams and the channel as a single exponential server. The performance objective is to avoid situations in which any of the queues is fully (blocking). The authors also consider systems in which the queues are fed by the server and the objective is to avoid situations in which any of the queues is empty (starvation), and a hybrid system, consisting of both types of queue. Many computer and communication systems fall within the framework of these models. The goal is to get a good control policy for these systems. The authors first prove certain structural properties of the optimal solution for the case N=2. These properties lead them to conclude that it is unlikely that a closed-form expression for the optimal policy could be found, but at the same time guide the derivation of a heuristic decision rule.>