Mean value and tail distribution of the message delay in statistical multiplexers with correlated train arrivals

In this paper, we study a statistical multiplexer which is modelled as a discrete-time single-server infinite-capacity queueing system. This multiplexer is fed by messages generated by an unbounded population of users. Each message consists of a generally distributed number of fixed-length packets.

We assume the packet arrival process to exhibit simultaneously the following two types of correlation. First, the messages arrive to the multiplexer at the rate of one packet per slot, which results in what we call a primary correlation in the packet arrival process. Also, on a higher level, the arrival process contains an additional secondary correlation, resulting from the fact that the behaviour of the user population is governed by a two-state Markovian environment. Specifically, the state of this user environment in a particular slot determines the distribution of the number of newly generated messages in that slot.

In previous work on this model, we provided analytical results for the moments and the tail distribution of the system contents. Using these results, we now concentrate on the message delay performance of this system, under the important assumption of a first-come-first-served queueing discipline for packets, whereby packets that arrive during the same slot are stored in random order. Closed-form expressions are derived for the mean value of both the total delay and the transmission time of an arbitrary message. Additionally, we provide a reasonably tight upper and lower bound for the tail probabilities of the message delay. By means of some numerical examples, we discuss the influence of the environment parameters on the delay performance.     

Performance evaluation of CAI and RAI transmission modes in a GI-G-1 queue

In this paper, a discrete-time single-server queue is considered with an uncorrelated message arrival process and an uncorrelated server interruption process. The length of the messages is modeled as a series of positive i.i.d. random variables and two operation modes are considered. In continue after interruption mode (CAI) the processing of an interrupted message resumes with the next packet of this message. In repeat after interruption mode (RAI), the complete message is reprocessed after a server interruption. Using a generating-functions approach, explicit expressions for the mean and variance of buffer occupancy and message delay are derived for both operation modes. For illustration purposes, a discrete-time Pois-Geo-1 system is then evaluated.Scope and purposeDiscrete-time queueing theory has gained a lot of interest recently to describe queueing related phenomena in an environment where time is slotted, such as various digital computer and communication systems including mobile and B-ISDN networks based on asynchronous transfer mode technology. This work focuses on a discrete-time queueing system with server interruptions, which can occur when several users have to share a common resource, or when this resource is temporarily unavailable due to external causes such as maintenance or system failures. The contribution of this paper mainly lies in the model that is considered, the solution method that is applied, as well as the results that are generated. First, we want to introduce a model with an interrupted service process that allows us to compare an environment where interrupted messages must be retransmitted with the situation where this is not the case. Second, we will show that a generating-functions approach is extremely suitable for solving such a queueing model. And finally, we want to establish closed-form formulas in terms of the system parameters that enable us to assess the system performance for the two transmission modes that are considered.     

The message delay in mobile ad hoc networks

A stochastic model is introduced that accurately models the message delay in mobile ad hoc networks where nodes relay messages and the networks are sparsely populated. The model has only two input parameters: the number of nodes and the parameter of an exponential distribution which describes the time until two random mobiles come within communication range of one another. Closed-form expressions are obtained for the Laplace–Stieltjes transform of the message delay, defined as the time needed to transfer a message between a source and a destination. From this we derive both a closed-form expression and an asymptotic approximation (as a function of the number of nodes) of the expected message delay. As an additional result, the probability distribution function is obtained for the number of copies of the message at the time the message is delivered. These calculations are carried out for two protocols: the two-hop multicopy and the unrestricted multicopy protocols. It is shown that despite its simplicity, the model accurately predicts the message delay for both relay strategies for a number of mobility models (the random waypoint, random direction and the random walker mobility models).     

基于聚类分析的抗时延抖动时隙分配算法

信息传输的实时性是战术数据链的突出特征,要求数据链通信不仅有较好的时延特性,还要具备可靠的时延抖动特性。随机报文流的产生具有随机性、突发性的特点,需按照需求动态地分配时隙,对算法的实时性要求较高。因此,提出基于聚类分析的抗时延抖动时隙分配算法,应用聚类的方法将空闲时隙划分成时隙簇,简化了时隙分配的分析过程。实验仿真表明:该算法分配的时隙能够满足时延抖动的要求,而且算法的复杂度小,可以有效处理周期性随机报文流的时隙分配问题。     

一种通用的移动智能网SCF排队网络模型

在分析移动智能网SCF（Service Control Function）软件功能模型的基础上，提出了一种通用的SCF排队网络模型．然后以移动智能网中的预付费业务和短消息业务为例，使用具有反馈的M／G／1排队系统分析了业务消息的时延与消息到达率之间的关系，同时通过仿真对结果进行验证．仿真和分析结果的一致性表明，该排队网络模型是一个有效的数学模型，能用于快速地预测SCP（Service Control Point）系统的性能．     

Performance analysis of Markovian polling systems with single buffers

In this paper, we analyze the Markovian polling system with single buffers, asymmetric arrival rates, service times, and switchover times. A virtual buffer model is introduced to derive the relationship of the joint generating function for the queue length of each station at a polling instant. The Laplace-Stieltjes transforms of the cycle time and the intervisit time are obtained from the marginal generating function. We analyze the cyclic, load-oriented-priority, and symmetric random polling schemes which are classified by adjusting the transition probabilities, and compare the merits and demerits of each scheme for the performance measures. In particular, we prove that the mean queue lengths at the polling instants are the same for all stations in case of the load-oriented-priority polling scheme for the buffer relaxation system in which a new message is stored as soon as the transmission of the message currently in the buffer is initiated.     

基于通用即插即用协议服务发现的随机服务系统模型

在智能家居网络设备自动发现过程中,网络设备端随机独立地选择延时发送服务响应消息,通常出现严重的消息拥塞现象。为解决智能家居网络中服务响应消息拥塞问题,以智能家居标准协议——通用即插即用(UPnP)进行自动发现设备为例,考虑不同应用场景中对服务发现过程的可靠性和实时性有不同要求,提出一种基于UPnP服务发现的随机服务系统模型。设计了集成系统响应指标和等待指标的通信损益函数,推导得到了最佳缓存队列长度与损益系数之间的关系。通过对比不同缓存队列长度中响应消息的到达时间、离开时间、等待时间和停留时间,验证了设计损益指标的必要性和随机服务系统模型的可行性。     

Mean message waiting times in symmetric multi-queue systems with cyclic service

A new performance analysis is provided for a cyclic service system consisting of statistically identical stations where at most one message is served for any station in a cycle. We assume that the time is slotted and that the number of message arrivals at each station in any slot is independent and generally distributed. The switch-over time and message service time (integral multiples of the slot size) are also generally distributed. For this system (called limited service system) we find the mean message waiting time explicitly. In the case of Poisson arrivals we show that our mean message waiting time is greater than that for the gated service system which is greater than that for the exhaustive service system. We also summarize the corresponding results for the three types of services in continuous-time systems.     

Power and delay optimisation in multi-hop wireless networks

In this paper, we study the optimisation problem of transmission power and delay in a multi-hop wireless network consisting of multiple nodes. The goal is to determine the optimal policy of transmission rates at various buffer and channel states in order to minimise the power consumption and the queueing delay of the whole network. With the assumptions of interference-free links and independently and identically distributed (i.i.d.) channel states, we formulate this problem using a semi-open Jackson network model for data transmission and a Markov model for channel states transition. We derive a difference equation of the system performance under any two different policies. The necessary and sufficient condition of optimal policy is obtained. We also prove that the system performance is monotonic with respect to (w.r.t.) the transmission rate and the optimal transmission rate can be either maximal or minimal. That is, the ‘bang-bang’ control is an optimal control. This optimality structure greatly reduces the problem complexity. Furthermore, we develop an iterative algorithm to find the optimal solution. Finally, we conduct the simulation experiments to demonstrate the effectiveness of our approach. We hope our work can shed some insights on solving this complicated optimisation problem.     

Analysis of an infinite buffer system with random server interruptions

An infinite buffer with general arrival process, synchronous transmission, one single output channel and random server interruptions is considered.As opposed to previous analyses the interruption process of the output line is kept rather general, i.e. the server is assumed to be in one of two states, “available” or “blocked”, where the sojourn time of the blocked state is arbitrarily distributed and the sojourn time of the available state has a density function which is a mixture of a finite number of geometric densities. For this general case the probability generating function of the buffer occupancy at various time instants is derived.The results of the study are applied to the case where the server interruptions are due to the presence of speech at the input of the transmission channel of an integrated voice-data system. Some considerable deviations from earlier results are found.     

Stepwise fair-share buffering for gossip-based peer-to-peer data dissemination

We consider buffer management in support of large-scale gossip-based peer-to-peer data dissemination protocols. Coupled with an efficient buffering mechanism, system-wide buffer usage can be optimized while providing reliability and scalability in such protocols. We propose a novel approach, stepwise fair-share buffering, that provides uniform load distribution and reduces the overall buffer usage where every peer has a partial view of the system. We report and discuss the comparative performance results with existing buffering approaches as well as random buffering which serves as a benchmark. We present separate evaluations of bufferer selection and gossip-based data dissemination. Reliability, content dissemination time, message delay, buffering delay, and minimum buffer requirements are considered as the key metrics investigated through simulations. The performance of our approach in the case of multiple senders, link failures with multiple bufferers, and scalability to larger networks are investigated. Several power-law and hierarchical overlay topologies are considered. Analytical bounds for reliability of dissemination are also provided.     

基于优先级的TDMA动态时隙分配算法

根据帧结构的不同对现有的时隙分配算法进行分类,分析其特点及综合性能。根据二叉树块内均分法,提出一种改进的时分多址动态时隙分配算法,地面主控站可根据用户的紧急或优先级高低的预约请求进行实时分配,能满足用户占用时隙块发送较长报文的需求。仿真结果表明,该算法能减少报文的平均延误时间,适合突发应急报文的传输需要。     

Portable and Scalable Algorithm for Irregular All-to-All Communication

In irregular all-to-all communication, messages are exchanged between every pair of processors. The message sizes vary from processor to processor and are known only at run time. This is a fundamental communication primitive in parallelizing irregularly structured scientific computations. Our algorithm reduces the total number of message start-ups. It also reduces node contention by smoothing out the lengths of the messages communicated. As compared to the earlier approaches, our algorithm provides deterministic performance and also reduces the buffer space at the nodes during message passing. The performance of the algorithm is characterised using a simple communication model of high-performance computing (HPC) platforms. We show the implementation on T3D and SP2 using C and the message passing interface standard. These can be easily ported to other HPC platforms. The results show the effectiveness of the proposed technique as well as the interplay among the machine size, the variance in message length, and the network interface.     

Interruptions in the wild: portraying the handling of interruptions in manufacturing from a distributed cognition lens

This paper presents a study examining interruptions in the wild by portraying the handling of interruptions in manufacturing from a distributed cognition lens. By studying how interruptions occur and are handled in the daily activities of a work team at a large foundry for casting heavy diesel engines, we highlight situations when the propagation, transformation, and representation of information are not supported by prescribed work processes and propose recommendations for how this can be amended. The study was conducted by several visits to the aforementioned factory with cognitive ethnography as the basis for the data collection. The focus was on identifying interruptions and analysing these through a distributed cognition framework as an initial step towards studying interruptions in a manufacturing environment. The key findings include the identification of three, previously undefined, types of interruptions and the conclusion that interruptions do indeed affect the distributed workload of the socio-technical system and thus the overall production performance at the casting line.

     

基于多队列缓冲池的紧急消息推送方法

消息推送系统作为一种主动的、定制化的消息送达形式,能够从用户的兴趣出发,主动向用户呈现所需要的信息,正在逐渐改变互联网的信息传播方式。现有消息推送系统主要针对弱实时场景设计,资讯、娱乐类消息是其主要的推送内容,不能满足一些高可靠、低时延场景的消息推送需求。针对于此,本文提出一种多队列消息池缓存策略和二级紧急消息调度方法,提高了消息的到达率水平,同时减小了紧急消息的到达时延。实验结果表明,该方法能够有效提高消息系统的可靠性和推送效率。      

一种面向机会网络路由的最优停止决策方法

投递延迟是机会网络的一个重要指标,给定节点缓存和消息副本数目限制,如何选择合适的节点复制消息成为一个关键问题.提出一种基于最优停止理论的路由决策方法（OSDR）.OSDR 将每个时隙上所遇节点和目标节点的平均相遇时间看做一个随机变量,根据该随机变量的统计特性得到一个停止观察、复制消息的规则,该规则呈现简单的阈值结构,即当某个时隙上所遇节点和目标节点的平均相遇时间小于给定阈值时即复制消息. OSDR 可以在较小的相遇间隔和等待成本之间进行折衷,实现数学期望意义上的最小消息投递延迟.介绍了OSDR 的网络模型、最优停止规则的存在性证明过程以及计算方法.模拟实验结果表明,OSDR 相对其他方法,在投递成功率、投递延迟等方面具有明显优势.     

Port partitioning and dynamic queueing for IP forwarding

With the increase of internet protocol (IP) packets the performance of routers became an important issue in internet/working. In this paper we examine the matching algorithm in gigabit router which has input queue with virtual output queueing. Dynamic queue scheduling is also proposed to reduce the packet delay and packet loss probability. Port partitioning is employed to reduce the computational burden of the scheduler in a switch which matches the input and output ports for fast packet switching. Each port is divided into two groups such that the matching algorithm is implemented within each pair of groups in parallel. The matching is performed by exchanging the pair of groups at every time slot. Two algorithms, maximal weight matching by port partitioning (MPP) and modified maximal weight matching by port partitioning (MMPP) are presented. In dynamic queue scheduling, a popup decision rule for each delay critical packet is made to reduce both the delay of the delay critical packet and the loss probability of loss critical packet. Computational results show that MMPP has the lowest delay and requires the least buffer size. The throughput is illustrated to be linear to the packet arrival rate, which can be achieved under highly efficient matching algorithm. The dynamic queue scheduling is illustrated to be highly effective when the occupancy of the input buffer is relatively high.Scope and purposeTo cope with the increasing internet traffic, it is necessary to improve the performance of routers. To accelerate the switching from input ports to output in the router partitioning of ports and dynamic queueing are proposed. Input and output ports are partitioned into two groups A/B and a/b, respectively. The matching for the packet switching is performed between group pairs (A, a) and (B, b) in parallel at one time slot and (A, b) and (B, a) at the next time slot. Dynamic queueing is proposed at each input port to reduce the packet delay and packet loss probability by employing the popup decision rule and applying it to each delay critical packet.The partitioning of ports is illustrated to be highly effective in view of delay, required buffer size and throughput. The dynamic queueing also demonstrates good performance when the traffic volume is high.     

Smooth Control of Adaptive Media Playout for Video Streaming

Client-side data buffering is a common technique to deal with media playout interruptions of streaming video caused by network jitters and packet losses of best-effort networks. However, stronger playout interruption protection inevitably amounts to larger data buffering and results in more memory requirements and longer playout delay. Adaptive media playout (AMP), also a client-side technique, can reduce the buffer requirement and avoid buffer outage but at the expense of visual quality degradation because of the fluctuation of playout speed. In this paper, we propose a novel AMP scheme to keep the video playout as smooth as possible while adapting to the channel condition. The triggering of the playout control is based on buffer variation rather than buffer fullness. Experimental results show that our AMP scheme surpasses conventional schemes in unfriendly network conditions. Unlike previous schemes that are tuned for a specific range of packet loss and network instability, the proposed AMP scheme maintains consistent performance across a wide range of network conditions.     

基于交叉点缓存状态的CICQ调度算法

针对现有的联合输入交叉点排队(CICQ)调度算法在设计时未充分利用交叉点缓存状态信息的问题,提出一种CICQ状态堆调度算法。该算法分布式地运行于CICQ结构的各个输入端口和输出端口。仿真结果表明,在均匀或非均匀流量模型下,基于该算法的CICQ结构都能获得与输出排队结构相当的性能,且具有较高的时延。     

Transaction Scheduling in Distributed Real-Time Systems

Inthis paper, we study the performance of using optimistic approachto concurrency control in distributed real-time database systems(RTDBS). The traditional optimistic approach suffers from theproblem of unnecessary restarts. Transaction restarts can significantlyincrease the system workload and intensify resource and datacontention. In distributed environments, the complexity of thesystem and the high communication overhead exacerbate the problem.Therefore, the number of unnecessary restarts is the determinantfactor that affects the performance of optimistic approach indistributed RTDBS. When optimistic approach is extended to distributedenvironments, a number of issues resulting from the increasedcomplexity and communication overhead have to be resolved. Inthis paper, a new real-time distributed optimistic concurrencycontrol (DOCC) protocol with dynamic adjustment of serializationorder (DASO), called DOCC-DA is proposed. This protocol can avoidunnecessary transaction restarts by dynamically adjusting theserialization order of the conflicting transactions. Therefore,resources can be saved and more transactions can meet their deadlines.In the DOCC-DA protocol, a new distributed circular validationscheme is included to facilitate transaction validation in distributedenvironments. The performance of the DOCC-DA protocol has beenexamined in detail by simulation. The results showed that theperformance of the DOCC-DA protocol is consistently better thanthat of other protocols.