Burstiness in broadband integrated networks

Since broadband integrated networks have to cope with a wide range of bit rates, the notion of burstiness which expresses the irregularity of a flow, has been recognized as a vital question for such networks. In burstiness characterization encountered in the literature, special attention is given to the squared coefficient of variation of interarrival time (Cv²) in a cell arrival process. In order to observe the impact of a bursty flow on a queue, we introduce in this paper a new class of arrival process, the n-stage Markov Modulated Bernoulli Process, MMBP_n, for short, and its peculiar case, the n-stage Hyper-Bernoulli process, denoted by HBP_n. We numerically solve the MMBP_n/D/1/K and we compute in particular the rejection probability and the mean waiting time. For that purpose, a relation between the stationary queue length distribution and arrival time distribution is established. This relation adapts the GASTA equality to the arrival process under consideration. We then discuss the relevance of Cv² for burstiness characterization through an example: the HBP₂/D/1/K queue. We show that Cv² becomes significant only when local overload occurs, i.e., when the arrival rate is momentarily greater than the server rate. The results are then applied to two basic ATM problems: traffic characterization and buffer dimensioning using bursty inputs.     

Computing steady state probabilities in λ(n)/G/1/K queue

In this paper a recursive method is developed to obtain the steady state probability distribution of the number in system at arbitrary and departure time epochs of a single server state-dependent arrival rate queue λ(n)/G/1/K in which the arrival process is Markovian with arrival rates λ(n) which depend on the number of customers n in the system and general service time distribution. It is assumed that there exists an integer K such that λ(n) > 0 for all 0 n < K and λ(n) = 0 for all n K. Numerical results have been presented for many queueing models by suitably defining the function λ(n). These include machine interference model, queues with balking, queues with finite waiting space and machine interference model with finite waiting space. These models have wide application in computer/communication networks.     

Markovian queueing systems with retrials and heterogeneous servers

The asymptotic performances of a random access and an ordered entry G/M/K/Oqueueing system with a stationary counting arrival process, K heterogeneous parallel servers, no waiting room and retrials are approximated based on a two-parameter method. In a random access system, units upon arrival are randomly assigned to one of the servers. In an ordered entry system, servers are indexed from 1 to K, and units first arrive at server i and if the server is found to be busy, those units arrive at server (i + 1), for i = 1 to K − 1. In both queueing systems, if units are not processed by one of the servers, those units are not lost, instead they retry to receive service by merging with the incoming arrival units.

To approximate the asymptotic performance of the above queueing systems, a recursive algorithm is suggested, and appropriate performance measures are presented to be used as comparison criteria at the design stage. Furthermore, numerical results are provided and approximation outcomes are compared against those from a simulation study.     

Asymptotic analysis and simple approximation of the loss probability of the GI/M/c/K queue

We consider the GI^X/M/c/K queues with partial rejection or total rejection, and find an asymptotic behavior of loss probability of the GI^X/M/c/K queue as K tends to infinity. The asymptotic loss probability is expressed only in terms of the roots of the characteristic equation and the boundary probabilities of the corresponding GI^X/M/c queue. Numerical examples show that the asymptotic loss probability is a quite accurate approximation for the loss probability of the GI^X/M/c/K queue even when the system capacity K is moderate.     

Conditioned asymptotics for tail probabilities in large multiplexers

Consider a buffer whose input is a superposition of L independent identical sources, and which is served at rate sL. Recent work has shown that, under very general circumstances, the stationary tail probabilities for the queue of unfinished work Q in the buffer have the asymptotics P[Q > Lb] ≈ e^−LI(b) for large L. Here the shape function, I, is obtained from a variational expression involving the transient log cumulant generating function of the arrival process.

In this paper, we extend this analysis to cover time-dependent asymptotics for Markov arrival processes subject to conditioning at some instant. In applications we envisage that such conditioning would arise due to knowledge of the queue at a coarse-grained level, for example of the number of current active sources. We show how such partial knowledge can be used to predict future tail probabilities by use of a time dependent, conditioned shape function. We develop some heuristics to describe the time-dependent shape function in terms of a reduced set of quantities associated with the underlying arrivals process and show how to calculate them for renewal arrivals and a class of ON-OFF arrivals. This bypasses the full variational calculation of the shape function for such models.     

M/G/c/K blocking probability models and system performance

An exact solution for the M/G/c/K model is only possible for special cases, such as exponential service, a single server, or no waiting room at all. Instead of basing the approximation on an infinite capacity queue as is often the case, an approximation based on a closed-form expression derivable from the finite capacity exponential queue is presented. Properties of the closed-form expression along with its use in approximating the blocking probability of M/G/c/K systems are discussed. Extensive experiments are provided to test and verify the efficacy of our approximate results.     

Modeling buffer utilization in cell-based networks

Variable bit rate traffic is characteristically bursty and the arrivals are highly correlated. New network technology carries such traffic in cell-based networks where the service is a discrete time, deterministic process with the service rate determined by bandwidth negotiated by the user. Managing such networks is hard, and predicting cell loss at a station with limited buffer capacity K is essential to enable the user to negotiate his quality of service requirements. We present an analysis to determine the queue length distribution and the loss probability in such circumstances. For our analysis, we use an m-phase Markov Modulated Bernoulli Process with binomial distributed batch arrivals and deterministic service and limited capacity K, i.e. a MMBP^[X]_(m)/D/1 − K queuing system. We show that the system can be analyzed using the so-called unfinished work approach. The validity of our evaluation technique is illustrated by comparing our analytical results against those obtained from an event-driven siimulation of the same system.     

Some issues in performance modeling of data teletraffic

Data teletraffic is characterized by bursty arrival processes. Performance models are characterized by a desire to know under what circumstances is the probability that an arrival finds a full input buffer very small. In this paper I examine how four models proposed in the literature perform on two data sets of local area network traffic. Among my conclusion are (1) the protocol governing the data transmission may have a substantial effect on the statistical propoerties on the packet stream, (2) approximating the probability that a finit buffer of size b overflows may not be adequately approximated by the probability that an infinite buffer has at least b packets in it, and (3) a data-based estimate of large-deviation rate-function does the best job of estimating packet loss on these data sets. This method may overestimate the loss rate by several orders of magnitude, so there is room for further refinements.     

基于改进AP选择和K最近邻法算法的室内定位技术

针对复杂的室内环境和在传统K最近邻法（KNN）算法中认为信号差相等时物理距离就相等两个问题,提出了一种新的接入点（AP）选择方法和基于缩放权重的KNN室内定位算法。首先,改进AP的选择方法,使用箱形图过滤接收信号强度（RSS）的异常值,初步建立指纹库,剔除指纹库中丢失率高的AP,使用标准偏差分析RSS的变化,选择干扰较小的前n个AP;其次,在传统的KNN算法中引入缩放权重,构建一个基于RSS的缩放权重模型;最后,计算出获得最小有效信号距离的前K个参考点坐标,得到未知位置坐标。定位仿真实验中,仅对AP选择方法进行改进的算法平均定位误差比传统的KNN算法降低了21.9%,引入缩放权重算法的平均定位误差为1.82 m,比传统KNN降低了53.6%。     

Buffer contents and cell delay in a rate adaptation buffer with Markovian arrivals

This paper investigates the performance of a rate adaptation buffer in the case that the arriving cell stream is generated by an on/off-source, where both the on-periods and the off-periods are geometrically distributed. The ratio between the input rate and the output rate takes an arbitrary integer value greater than one. Under the assumption of an infinite storage capacity, exact explicit expressions are obtained for the mean values and the tail distributions of the buffer contents and the cell delay. Furthermore, an approximation is derived for the cell loss ratio in a finite-capacity buffer. Some numerical results are presented and discussed.Scope and purposeIn communication networks a rate adaptation buffer is used at the interface between two consecutive links, when the speed of the incoming link exceeds the speed of the outgoing link, in order to avoid excessive loss of information. So far, only few papers in the literature have investigated the buffer dimensioning of a rate adapter. All of these papers assume an uncorrelated arrival process on the incoming link and/or small differences between the input and the output rates, assumptions which in practice may not always be realistic. The present paper therefore presents and analyzes a discrete-time queueing model for a rate adaptation buffer which both accounts for the presence of correlation in the arrival stream and allows (possibly) large input/output ratios.     

Efficiently enumerating results of keyword search over data graphs

Various approaches for keyword search in different settings (e.g., relational databases and XML) actually deal with the problem of enumerating K-fragments. For a given set of keywords K, a K-fragment is a subtree T of the given data graph, such that T contains all the keywords of K and no proper subtree of T has this property. There are three types of K-fragments: directed, undirected and strong. This paper describes efficient algorithms for enumerating K-fragments. Specifically, for all three types of K-fragments, algorithms are given for enumerating all K-fragments with polynomial delay and polynomial space. It is shown how these algorithms can be enhanced to enumerate K-fragments in a heuristic order. For directed K-fragments and acyclic data graphs, an algorithm is given for enumerating with polynomial delay in the order of increasing weight (i.e., the ranked order), assuming that K is of a fixed size.     

On loss probabilities in presence of redundant packets with random drop

The purpose of this paper is to study the loss probabilities of messages in an M/M/1/K queueing system where in addition to losses due to buffer overflow there are also random losses in the incoming and outgoing links. We focus on the influence of adding redundant packets to the messages (as in error correction coding, e.g. Reed–Solomon code, etc.). In the first part we use multi-dimensional probability generating functions for solving the recursions which generalize those introduced by Cidon et al. [IEEE Trans. Inform. Theory 39 (1) (1993) 98] for computing the loss probabilities and derive analytical formulae for a special case. In the second part of the paper we use combinatorial arguments and Ballot theorem results to alternatively obtain the loss probabilities. The analytical results allow us to investigate when does adding redundancy decrease the loss probabilities.     

Analysis of a tandem queue with state-dependent general blocking: A GSMP perspective

In this paper, we study a tandem queue where there is a finite number of buffer positions at each stage. The blocking scheme is general in the sense that it can model a number of classical blocking schemes, including communication, manufacturing and kanban blockings as special cases. The system considered here differs from the conventional system in two aspects: (1) departure of jobs from the system is determined by an external arrival process of another queue lying parallel to the tandem queue; (2) the control parameters of the blocking scheme are state-dependent in that they may change values depending on the state of the system.

We model this system as a generalized semi-Markov process (GSMP), we study the structural properties of its scheme, and establish monotonicity and convexity properties of event times with respect to both the clock times and the integer blocking parameters. In particular, we demonstrate that the state-dependent scheme is “better”, in certain sense, than the corresponding static scheme. Our results also recover the structural properties previously established for the classical blockings.     

Product from solutions for multiserver centres with concurrent classes of customers

The MultiServer centre with Concurrent Classes of Customers (MSCCC) is a service centre consisting of B parallel identical exponential servers. The customers requesting service at the MSCCC centre belong to K groups. Customers arriving at the MSCCC centre are queued in the order of their arrival. A customer from group k will go into service at the MSCCC centre provided that one or more of the B servers is free and that at most n − 1 other group k customers are in service at the MSCCC centre.

The MSCCC centre can be applied to model systems where customers simultaneously occupy two resources. The system resources are partitioned into K primary and B secondary resources. A customer of group k can access primary resource k if it already is in possession of a secondary resource and if at most n − 1 other group k customers are using primary resource k.

This paper defines the MSCCC centre and presents several examples of computer (sub)systems that can be modelled using the MSCCC centre. The MSCCC centre is shown to satisfy local balance: therefore a multiclass queuing network consisting of BCMP and MSCCC centres has a product form solution. The joint probability distribution (JPD) for a queuing network consisting of several BCMP centres and one MSCCC centre is derived. Aggregation techniques are next used to reduce the JPD to a computationally tractable form. A Mean Value Analysis algorithm is presented for calculating the closed and open chain performance measures at the MSCCC centre.     

Distributed selectsort sorting algorithms on broadcast communication networks

In this paper, a distributed selectsort algorithm and a parameterized selectsort algorithm are presented to be applied on distributed systems for cases when N P where N is the number of elements to be sorted and P is the number of processors in the system. The distributed system considered in this paper uses a broadcasting channel for communication between processors. We show that the number of messages required for the parameterized selectsort algorithm is independent of N and is of complexity O(P), which is optimal in a distributed system with P processors. Furthermore, the amount of communication required in terms of elements is N + O(P³) and the computation time complexity is O((N/P)lgN + P²lg(N/P)). Hence, when N P³, the computation time complexity is O((N/P)lgN), which is optimal using P processors. In addition, this parameterized algorithm provides us with a parameter K such that by choosing the value of K allows us to trade among processing requirement, memory requirement, and communication requirement. It is shown that this parameterized algorithm can reduce the communication requirements significantly while only slightly increasing the computation requirements.     

基于动态选择启发值的改进TD-FTT算法

针对时间依赖路网中的K近邻（KNN）查询TD-FTT算法查询点发起时间与到达时间在同一时段的限制和预处理阶段计算时间代价大的问题,提出基于动态选择启发值改进的TD-FTT （ITD-FTT）算法。首先,在预处理阶段,根据各时段各边时间函数的最小值构建最小路网G_min;然后,在路网G_min中利用网络泰森图（NVD）并行计算节点最近邻来减少预处理阶段的计算时间;最后,在查找阶段通过计算节点到达时间所在时段,动态选择启发值来解除时间段的限制。实验结果显示,在预处理阶段ITD-FTT算法比TD-FTT算法计算时间减少了70.12%;在查询阶段ITD-FTT比TD-INE算法和TD-A算法在遍历节点个数上分别减少了46.52%和16.63%,响应时间比TD-INE算法和TD-A算法分别降低47.46%和18.24%。实验结果表明,ITD-FTT算法减少了查询扩展的节点数,降低了查找K近邻的时间,提高了查找效率。     

Parallel clustering algorithms

Clustering techniques play an important role in exploratory pattern analysis, unsupervised learning and image segmentation applications. Many clustering algorithms, both partitional clustering and hierarchical clustering, require intensive computation, even for a modest number of patterns. This paper presents two parallel clustering algorithms. For a clustering problem with N = 2ⁿ patterns and M = 2^m features, the time complexity of the traditional partitional clustering algorithm on a single processor computer is O(MNK), where K is the number of clusters. The proposed algorithm on anSIMD computer with MN processors has a time complexity O(K(n + m)). The time complexity of the proposed single-link hierarchical clustering algorithm is reduced from O(MN²) of the uniprocessor algorithm to O(nN) with MN processors.     

Arrival process-controlled adaptive media playout with multiple thresholds for video streaming

To improve the playout quality of video streaming services, an arrival process-controlled adaptive media playout (AMP) mechanism is designed in this study. The proposed AMP scheme sets three threshold values, denoted by P _n , L and H, for the playout controller to start playback and dynamically adjust the playout rate based on the buffer fullness. In the preroll period, the playout can start only when the buffer fullness n is not less than the dynamic playback threshold P _n ,?which is determined by the jitters of incoming video frames. In the playback period, if the buffer fullness is below L or over H,?the playout rate will slow down or speed up in a quadratic manner. Otherwise, the playback speed depends on the instantaneous frame arrival rate, which is estimated by the proposed arrival process tracking algorithm. We employ computer simulations to demonstrate the performance of the proposed AMP scheme, and compare it with several conventional AMP mechanisms. Numerical results show that our AMP design can shorten the playout delay and reduce both buffer underflow and overflow probabilities. In addition, our proposed AMP also outperforms traditional AMP schemes in terms of the variance of distortion of playout and the playout curve. Hence, the proposed arrival process-controlled AMP is really an outstanding design.     

Analysis of MAP/M/2/K queueing model with infinite resequencing buffer

We consider a MAP/M/2/K queueing model in which messages should leave the system in the order in which they entered into the system. In the case of infinite resequencing buffer, the steady-state probability vector is shown to be of matrix-geometric type. The total sojourn time of an admitted message into the system is shown to be of phase type. Efficient algorithmic procedures for computing various performance measures are given, and some interesting numerical examples are discussed.