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.     

依托站点状态的两级轮询控制系统时延特性分析

基于区分业务优先级和提高系统时延性能的网络需求,提出了依托站点状态的两级轮询控制系统.系统在混合服务两级轮询模型的基础上,根据站点缓冲区状态采用并行调度方式仅对有数据分组的活动站点提供服务.该模型既能满足区分站点优先级的需求又能避免空闲查询,从而提高系统利用率、降低等待时延.采用嵌入式马尔科夫链和概率母函数的方法对该系统建立数学模型,对系统平均等待时延特性进行了精确解析.通过理论计算与仿真实验结果的对比验证了理论分析的正确性,与已有两级轮询系统相比,具有更好的时延性能.     

TRAP: a high performance protocol for wireless local area networks

The fixed number of available random addresses for randomly addressed polling (RAP) poses a significant problem in terms of scalability in case of many active stations. In such cases, the protocol's performance is significantly degraded. In this paper, we propose a TDMA-based randomly addressed polling (TRAP) protocol. The protocol employs a variable-length TDMA-based contention stage with the length based on the number of active stations. At the beginning of each polling cycle, the base station invites all active mobile stations to register their intention to transmit via transmission of a short pulse. The base station uses the aggregate received pulse in order to obtain an estimate of the number of contending stations and schedules the contention stage to comprise an adequate number of time slots for these stations to successfully register their intention to transmit. Then it transmits a READY message carrying the number of time slots P. Each mobile station calculates a random address in the interval [0…P−1], transmits its registration request in the respective time slot and then the base station polls according to the received random addresses. Simulation results are presented that reveal the superiority of TRAP against the RAP protocol in case of medium and high offered loads. Furthermore, the implementation of the proposed protocol is much simpler than that of CDMA-based versions of RAP, since no extra hardware is needed for the orthogonal reception of the random addresses.     

An efficient quality-of-service MAC protocol for infrastructure WLANs

In this paper, we propose a new efficient MAC protocol, named quality-of-service MAC (QMAC), which is an integrated solution for providing QoS guarantees to real-time multimedia applications in infrastructure WLANs. In addition, QMAC has the following attractive features: (i) its reservation scheme ensures that real-time stations enter the polling list in bounded time, (ii) it supports multiple priority levels and guarantees that high-priority stations always join the polling list earlier than low-priority stations, (iii) it employs the distributed pre-check technique such that the access point can admit as many newly flows as possible, while not violating admitted flows' guarantees, (iv) its dynamic bandwidth allocation scheme provides real-time traffic transmission with per-flow probabilistic bandwidth assurances, and (v) it uses a multipoll frame to poll all stations on the polling list at a time, therefore, the bandwidth can be utilized more efficient. Through simulations, we demonstrate the advantage of our QMAC.     

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.     

An analysis of symmetric polling systems with two priority classes

A cyclic multiqueue system consists of several stations in which messages are enqueued for transmission, and which are served sequentially in cyclic order by a single server. The arrivals at each queue are independent Poisson processes, and the transmission times are generally distributed. Moreover, there is a nonzero switchover time from one station to the next, which is also generally distributed. Messages can be at either of two priority levels: priority 1 (low) or priority 2 (high), and polling occurs either at low priority, in which case both priority 1 and priority 2 messages can be transmitted, or at high priority, in which case only priority 2 messages are transmitted. The service disciplines considered are the exhaustive service discipline and the gated service discipline. In both cases the performance, as measured by the expected delay for high- and for low-priority messages, is evaluated. Part of the analysis is approximate, and simulation results are presented to validate the approximation.     

一种轮询协议中心站的性能分析

在基本轮询协议的基础上介绍了已有的排队优先权站点耗尽型轮询协议的操作原则,该协议可以优化中心站的延迟特性。通过嵌入马尔科夫链和构造队列母函数的方法,求解出了平衡状态下中心站的队列长度,并通过仿真进行了验证,同时通过仿真方法获得了系统的延迟特性。仿真结果表明,该协议在系统业务量强度较大时,中心站也具有良好的延迟特性。     

On the analysis of a symmetric polling system with single-message buffers

A performance analysis is provided for a polling system consisting of statistically identical stations with single-message buffers and Poisson arrival streams. Switchover and message service times are assumed to be generally distributed. Some errors in the past analysis are pointed out. We express such performance measures as the mean polling cycle time, the mean message response time, and the mean number of messages at an arbitrary time in terms of the mean number of massages served in a polling cycle. Our mean message response time reduces to that for an FCFS M/G/1//N queue (machine interference model) in the limit of zero switchover time.     

Optimal polling in communication networks

Polling is the process in which an issuing node of a communication network (polling station) broadcasts a query to every other node in the network and waits to receive a unique response from each of them. Polling can be thought of as a combination of broadcasting and gathering and finds wide applications in the control of distributed systems. In this paper, we consider the problem of polling in minimum time. We give a general lower bound on the minimum number of time units to accomplish polling in any network and we present optimal polling algorithms for several classes of graphs, including hypercubes and recursively decomposable Cayley graphs     

Orthogonal signaling-based queue status investigation method in IEEE 802.11

IEEE 802.11 specifies four different medium access control (MAC) protocols to coordinate multiple access in a wireless local area network (WLAN). Since several tens of stations can operate in a WLAN, the performance of MAC protocols is important for overall network efficiency. It has been observed that the IEEE 802.11 MAC protocols can be improved by knowing which station has a non-empty queue, i.e., queue status. The point coordination function (PCF) can use this information to avoid polling a station that has no pending data. The HCF controlled channel access can adapt polling parameters based on queue status information, especially when scheduling a bursty and variable bit-rate traffic. Previously suggested methods are rather limited in terms of accuracy and efficiency.In this paper, we propose a novel method to investigate the queue status of multiple stations by exploiting orthogonal signaling. With synchronous transmission of orthogonal codes and symbol level signal processing, the method allows all of the associated stations to report their queue status at the same time. Challenges that can arise in the implementation of the proposed method are identified, and their solutions are suggested. The feasibility of detecting orthogonal signals is thoroughly tested on a realistic channel model. To demonstrate the performance improvement of a MAC protocol, we applied the proposed method to PCF. Both analysis and simulation show that the modified PCF significantly outperforms not only the original PCF but also other previously suggested PCF enhancements.     

Real-time network monitoring scheme based on SNMP for dynamic information

An efficient and automated network management is required in large and complex networks since it is very difficult to manage them only with human effort. In response to this need, the Simple Network Management Protocol (SNMP) has been developed and adopted as the de facto standard. Some management information changes with time and the management station needs to monitor its value in real time. In such a case, polling is generally used in the SNMP because the management station can query agents periodically. However, the polling scheme needs both request and response messages for management information every time, which results in network traffic increase. In this paper, we suggest a real-time network monitoring method for dynamic information to reduce the network traffic in SNMP-based network management. In the proposed strategy, each agent first decides its own monitoring period. Then, the manager collects them and approves each agent's period without modification or adjusts it based on the total traffic generated by monitoring messages. After receiving a response message containing the monitoring period from the management station, each agent sends management information periodically without the request of management station. To evaluate the performance of the proposed real-time monitoring method, we implemented it and compared the network traffic and monitoring quality of the proposed scheme with the general polling method.     

连续时间完全服务与门限服务两级轮询系统性能研究

在信息分组以连续时间规律到达系统的基础上，对于轮询系统中不同优先级的业务问题，提出区分优先级的两级轮询服务模型。首先，在该模型中，低优先级站点采用门限服务，高优先级站点采用完全服务；然后，在高优先级转低优先级时，将传输服务与转移查询并行处理来降低服务器在查询转换期间所耗费的时间，提高轮询系统的效率；最后，运用马尔可夫链和概率母函数的方法建立了系统的数学模型，通过对数学模型精确解析，得到了连续时间两级服务系统每个站点的平均排队队长和平均等待时间的表达式，精确解析出平均排队队长和平均等待时间的值。仿真实验结果表明：理论计算值与实验仿真值近似相等，说明理论分析正确合理。该模型既能保障低优先级站点服务质量，又能为高优先级站点提供优质服务。     

DeviceNet现场总线中轮询协议的性能研究

基于DeviceNet协议生产者/消费者通信模型特点构建了其轮询通讯方式模型,轮询命令报文由主站广播至生产从站,轮询响应报文由生产从站通过主站周期地轮询每个生产从站广播至所有消费从站;文章采用Petri网的过程变迁TPN混合方法对DeviceNet总线协议进行了分析和研究,对其轮询通讯方式进行了模拟,讨论了响应时间、吞吐量等参数,分析了性能差异和响应快慢,根据文章的结论,现场总线的设计者可以很好的选择和设计满足自己需要的设计方案.     

具有服务质量保障的片上网络路由仲裁控制

片上网络(Network on Chip,NoC)通过仲裁机制控制各个端口间的数据交换。经典的RR(Round-Robin)算法保障了各端口间的公平性,但却难以为时延敏感业务提供具有低数据交换等待时延的QoS保障。为此,提出一种区分优先级并行调度RR(PP-RR)算法,其根据端口数据负载提供区分优先级服务,高优先级端口数据享有更多仲裁成功机会。采用并行调度两级轮控制模型实现了对PP-RR仲裁算法的数学建模,获得了时延性能的数学解析。     

Algorithms for scheduling jobs on two serial duplicate stations

In automated assembly or production lines, some stations are duplicated due to their long cycle times. Material handling considerations may require these stations to be arranged in series rather than in parallel. Each job needs to be processed on any one of the duplicate stations. This study deals with scheduling of n available jobs on two serial duplicate stations in an automated production line. The performance measures considered are mean flowtime, makespan, and station idle time. After the problem is formulated, two algorithms are developed to determine the optimal schedules with respect to the performance measures.     

Voting from the Home or Office? Don't Hold Your Breath

This article describes the challenges of Internet voting defined here as casting an electronic national or state direct election ballot from a location other than a polling station. The widely used terms "electronic voting" or "e-voting" represent the highly publicized (and controversial) use of special electronic devices at polling stations. Our interest here is the next step in governance - remote voting via the Internet, without having to physically go to a polling place.     

Stability conditions for multisequence systems with cyclic service

The conditions under which several multiqueue systems with cyclic service (also referred to as polling systems) will be stable are investigated. The stability conditions established are more general than those established by other authors. In particular, both station stability and system stability are considered for polling systems for which an exact analysis has been obtained and for those for which an exact analysis has not yet been obtained     

A new method for assembly line balancing having stochastic work elements

The main feature of the method suggested in this paper is the assignment of priority to elements and priority elements are preferred to non-priority elements when assigning elements to stations. It accepts element times from known or unknown symmetrical distributions, minimizes the variation within a station and allows assignments of elements to stations such that each station time does not exceed the probability confidence levels set by management.     

A probabilistic approach to estimate the mean waiting times in the earliest deadline first polling

In queueing system, the mean waiting times of messages are important measures to characterize the quality of service (QoS) under various requirements. In a time-critical system, message transactions which cannot meet deadline constraints might lead to catastrophic consequences. Currently, the waiting time estimations using the first-come-first-served (FCFS) and priority (PRI) strategies are already well developed. However, in the case of multi-queue dynamic environments, these quantities are more difficult to analyze due to multiple classes of messages are considered. In this paper, we aim to consider a polling system consisting of a number of parallel infinite-capacity single-server queues. We propose a probabilistic approach to derive the waiting times for different classes of messages by using non-preemptive earliest deadline first (EDF) polling policy. The resulting formula can also lead to the FCFS polling and PRI polling by altering the relative deadlines. Moreover, the bounds of waiting times are discussed. The accuracy of the proposed algorithm is established by comparisons with simulation results. The runtime results are in very good convergence with the theoretical predictions made by our formulas, in terms of prediction accuracies of waiting times and untimely service ratios of messages under various scenarios and timing constraints.     

Evaluation of automated guided vehicle systems by simulation

An experimental study was conducted in this research to evaluate the design of Automated Guided Vehicle (AGV) systems using discrete event simulation. Given the layout of work stations and several types of jobs to be processed in the system, the constituent elements of the AGV system, including the number of AGVs, the speed of the vehicles, the number of machines at each station, the number of load and unload stations, rules for selection of AGV, routing criteria, and track intersection priorities, were defined in a SIMAN model. Pilot runs were performed first to determine the values of the system parameters which may affect the performance of the AGV systems. A factorial design was then used to generate simulation experiments. Finally, a number of simulation runs were executed under different experimental conditions to obtain preliminary statistics on the following performance measures: utilization of AGVs, average number of jobs waiting in the queue for an AGV, average system throughput time, average waiting time in intersections and total waiting time in queues.