Analysis of a tripartite entanglement distribution switch

Queueing Systems - We study a quantum switch that distributes tripartite entangled states to sets of users. The entanglement switching process requires two steps: First, each user attempts to...     

Call admission control schemes under generalized processor sharing scheduling

Provision of Quality‐of‐Service (QoS) guarantees is an important and challenging issue in the design of integrated‐services packet networks. Call admission control is an integral part of the challenge and is closely related to other aspects of networks such as service models, scheduling disciplines, traffic characterization and QoS specification. In this paper we provide a theoretical framework within which call admission control schemes with multiple statistical QoS guarantees can be constructed for the Generalized Processor Sharing (GPS) scheduling discipline. Using this framework, we present several admission control schemes for both session‐based and class‐based service models. The theoretical framework is based on recent results in the statistical analysis of the GPS scheduling discipline and the theory of effective bandwidths. Both optimal schemes and suboptimal schemes requiring less computational effort are studied under these service models. The QoS metric considered is loss probability. This revised version was published online in June 2006 with corrections to the Cover Date.     

Multicast-based inference of network-internal delay distributions

Packet delay greatly influences the overall performance of network applications. It is therefore important to identify causes and locations of delay performance degradation within a network. Existing techniques, largely based on end-to-end delay measurements of unicast traffic, are well suited to monitor and characterize the behavior of particular end-to-end paths. Within these approaches, however, it is not clear how to apportion the variable component of end-to-end delay as queueing delay at each link along a path. Moreover, there are issues of scalability for large networks. In this paper, we show how end-to-end measurements of multicast traffic can be used to infer the packet delay distribution and utilization on each link of a logical multicast tree. The idea, recently introduced in Caceres et al. (1999), is to exploit the inherent correlation between multicast observations to infer performance of paths between branch points in a tree spanning a multicast source and its receivers. The method does not depend on cooperation from intervening network elements; because of the bandwidth efficiency of multicast traffic, it is suitable for large-scale measurements of both end-to-end and internal network dynamics. We establish desirable statistical properties of the estimator, namely consistency and asymptotic normality. We evaluate the estimator through simulation and observe that it is robust with respect to moderate violations of the underlying model.     

The monitoring and early detection of Internet worms

After many Internet-scale worm incidents in recent years, it is clear that a simple self-propagating worm can quickly spread across the Internet and cause severe damage to our society. Facing this great security threat, we need to build an early detection system that can detect the presence of a worm in the Internet as quickly as possible in order to give people accurate early warning information and possible reaction time for counteractions. This paper first presents an Internet worm monitoring system. Then, based on the idea of "detecting the trend, not the burst" of monitored illegitimate traffic, we present a "trend detection" methodology to detect a worm at its early propagation stage by using Kalman filter estimation, which is robust to background noise in the monitored data. In addition, for uniform-scan worms such as Code Red, we can effectively predict the overall vulnerable population size, and estimate accurately how many computers are really infected in the global Internet based on the biased monitored data. For monitoring a nonuniform scan worm, especially a sequential-scan worm such as Blaster, we show that it is crucial for the address space covered by the worm monitoring system to be as distributed as possible.     

Detection Probability Estimation of Directional Antennas and Omni-Directional Antennas

This paper studies the problem of detection of directional antennas and omni-directional antennas by hostile detection systems. We present a model for calculating the probability of detecting a transmitter at arbitrary location around the transmitter. Our study shows that, if a directional antenna employs the same transmit power as an omni-directional antenna, the directional antenna can not decrease the probability of being detected. In some scenarios, a directional antenna is more likely to be detected than an omni-directional antenna. However, if a directional antenna provides the same Effective Isotropic Radiated Power in the direction of the receiver as an omni-directional antenna, the transmit power needed by a directional antenna to send data is much less than that of an omni-directional antenna. In this scenario, the probability of detecting a directional antenna is reduced by over 90%. This reveals that directional antennas can be used to build a secure path to send data at low probability of being detected by adversaries.     

On optimal polling policies

In a single-server polling system, the server visits the queues according to a routing policy and while at a queue, serves some or all of the customers there according to a service policy. A polling (or scheduling) policy is a sequence of decisions on whether to serve a customer, idle the server, or switch the server to another queue. The goal of this paper is to find polling policies that stochastically minimize the unfinished work and the number of customers in the system at all times. This optimization problem is decomposed into three subproblems: determine the optimal action (i.e., serve, switch, idle) when the server is at a nonempty queue; determine the optimal action (i.e., switch, idle) when the server empties a queue; determine the optimal routing (i.e., choice of the queue) when the server decides to switch. Under fairly general assumptions, we show for the first subproblem that optimal policies are greedy and exhaustive, i.e., the server should neither idle nor switch when it is at a nonempty queue. For the second subproblem, we prove that in symmetric polling systems patient policies are optimal, i.e., the server should stay idling at the last visited queue whenever the system is empty. When the system is slotted, we further prove that non-idling and impatient policies are optimal. For the third subproblem, we establish that in symmetric polling systems optimal policies belong to the class of Stochastically Largest Queue (SLQ) policies. An SLQ policy is one that never routes the server to a queue known to have a queue length that is stochastically smaller than that of another queue. This result implies, in particular, that the policy that routes the server to the queue with the largest queue length is optimal when all queue lengths are known and that the cyclic routing policy is optimal in the case that the only information available is the previous decisions.This work was supported in part by NSF under Contract ASC-8802764.     

Theories and models for Internet quality of service

We survey advances in theories and models for Internet quality of service (QoS). We start with the theory of network calculus, which lays the foundation for support of deterministic performance guarantees in networks, and illustrate its applications to integrated services, differentiated services, and streaming media playback delays. We also present mechanisms and architecture for scalable support of guaranteed services in the Internet, based on the concept of a stateless core. Methods for scalable control operations are also discussed. We then turn our attention to statistical performance guarantees and describe several new probabilistic results that can be used for a statistical dimensioning of differentiated services. Lastly, we review proposals and results in supporting performance guarantees in a best effort context. These include models for elastic throughput guarantees based on TCP performance modeling, techniques for some QoS differentiation without access control, and methods that allow an application to control the performance it receives, in the absence of network support     

Computational aspects of the workload distribution in the MMPP/GI/1queue

We show how the analysis of Markov modulated rate processes can be used to address the problem of computing the distribution of W, the stationary workload in the MMPP/GI/1 queue. Using the results of papers by Anick et al. (1982); Mitra (1988); and Elwalid et al. (1991), we present the decomposition properties of the Laplace transform of W and efficient computational algorithms for computing its distribution. The techniques are also applied to compute the bounds on the distribution of W developed by Liu et al. (see JACM, vol.44, no.2, p.366-94, 1997). Numerical results illustrating the usefulness of the methods are given for the case of the superposition of independent, nonidentical sources     

Optimal multicast smoothing of streaming video over the Internet

A set of applications such as Internet video broadcasts, corporate telecasts, and distance learning require the simultaneous streaming of video to a large population of viewers across the Internet. The high bandwidth requirements and the multi-timescale burstiness of compressed video make it a challenging problem to provision network resources for streaming multimedia. For such applications to become affordable and ubiquitous, it is necessary to develop scalable techniques to efficiently stream video to a large number of disparate clients across a heterogeneous Internet. In this paper, we propose to multicast smoothed video over an application-level overlay network of proxies, and to differentially cache the video at the intermediate nodes (proxies) in the distribution tree, in order to reduce the network bandwidth requirements of video dissemination. We formulate the multicast smoothing problem as an optimization problem, and develop an algorithm for computing the set of transmission schedules for the tree that minimize the peak rate and rate variability, given buffer constraints at different nodes in the tree. We also develop an algorithm to compute the minimum buffer allocation in the entire tree, such that feasible transmission to all the clients is possible, when the tree has heterogeneous rate constraints. We show through trace-driven simulations that substantial benefits are possible from multicast smoothing and differential caching, and that these gains can be realized even with modest proxy caches.     

The impact of multicast layering on network fairness

Many definitions of fairness for multicast networks assume that sessions are single rate, requiring that each multicast session transmits data to all of its receivers at the same rate. These definitions do not account for multirate approaches, such as layering, that permit receiving rates within a session to be chosen independently. We identify four desirable fairness properties for multicast networks, derived from properties that hold within the max-min fair allocations of unicast networks. We extend the definition of multicast max-min fairness to networks that contain multirate sessions, and show that all four fairness properties hold in a multirate max-min fair allocation, but need not hold in a single-rate max-min fair allocation. We then show that multirate max-min fair rate allocations can be achieved via intra-session coordinated joins and leaves of multicast groups. However, in the absence of coordination, the resulting max-min fair rate allocation uses link bandwidth inefficiently, and does not exhibit some of the desirable fairness properties. We evaluate this inefficiency for several layered multirate congestion control schemes, and find that, in a protocol where the sender coordinates joins, this inefficiency has minimal impact on desirable fairness properties. Our results indicate that sender-coordinated layered protocols show promise for achieving desirable fairness properties for allocations in large-scale multicast networks