Some depression cells with heights lower than their surrounding cells may often be found in Grid-based digital elevation models (DEM) dataset due to sampling errors.The depression-filling algorithm presented by Planch...Some depression cells with heights lower than their surrounding cells may often be found in Grid-based digital elevation models (DEM) dataset due to sampling errors.The depression-filling algorithm presented by Planchon and Darboux works very quickly compared to other published methods.Despite its simplicity and deli-cacy,this algorithm remains difficult to understand due to its three complex subroutines and its recursive execution.Another fast algorithm is presented in this article.The main idea of this new algorithm is as follows:first,the DEM dataset is viewed as an island and the outer space as an ocean;when the ocean level increases,the DEM cells on the island's boundary will be inundated;when a cell is inundated for the first time,its elevation is increased to the ocean level at that moment;after the ocean has inun-dated the entire DEM,all of the depressions are filled.The depression-removing processing is performed using a priority queue.Theoretically,this new algorithm is a fast algorithm despite the fact that it runs more slowly than Planchon and Darboux's method.Its time-complexity in both the worst case and in an average case is O(8nlog 2 (m)),which is close to O(n).The running speed of this algorithm depends mainly on the insertion operation of the priority queue.As shown by the tests,the depres-sion-filling effects of this algorithm are correct and valid,and the overall time consumption of this algorithm is less than twice the time consumed by Planchon & Darboux's method for handling a DEM smaller than 2500×2500 cells.More importantly,this new algorithm is simpler and easier to understand than Planchon and Darboux's method This advantage allows the correct program code to be written quickly.展开更多
We prove a heavy traffic limit theorem to justify diffusion approximations for multiclass queueing networks under preemptive priority service discipline and provide effective stochastic dynamical models for the system...We prove a heavy traffic limit theorem to justify diffusion approximations for multiclass queueing networks under preemptive priority service discipline and provide effective stochastic dynamical models for the systems. Such queueing networks appear typically in high-speed integrated services packet networks about telecommunication system. In the network, there is a number of packet traffic types. Each type needs a number of job classes （stages） of processing and each type of jobs is assigned the same priority rank at every station where it possibly receives service. Moreover, there is no inter-routing among different traffic types throughout the entire network.展开更多
In this paper exhaustive-service priority-M/G/1 queueing systems with multiple vacations, single vacation and setup times are studied under the nonpreemptive and preemptive resume priority disciplines. For each of the...In this paper exhaustive-service priority-M/G/1 queueing systems with multiple vacations, single vacation and setup times are studied under the nonpreemptive and preemptive resume priority disciplines. For each of the six models analysed, the Laplace-Stieltjes transform of the virtual waiting time Wk(t) at time t of class k is derived by the method of collective marks. A sufficient condition for , where U has the standard normal distribution, is also given.展开更多
We study a vacation queueing system with a single server simultaneously dealing with an M/G/1 and an M/D/1 queue. Two classes of units, priority and non-priority, arrive at the system in two independent Poisson stream...We study a vacation queueing system with a single server simultaneously dealing with an M/G/1 and an M/D/1 queue. Two classes of units, priority and non-priority, arrive at the system in two independent Poisson streams. Under a non-preemptive priority rule, the server provides a general service to the priority units and a deterministic service to the non-priority units. We further assume that the server may take a vacation of random length just after serving the last priority unit present in the system. We obtain steady state queue size distribution at a random epoch. Corresponding results for some special cases, including the known results of the M/G/1 and the M/D/1 queues, have been derived.展开更多
Weighted priority queueing is a modification of priority queueing that eliminates the possibility of blocking lower priority traffic. The weights assigned to priority classes determine the fractions of the bandwith th...Weighted priority queueing is a modification of priority queueing that eliminates the possibility of blocking lower priority traffic. The weights assigned to priority classes determine the fractions of the bandwith that are guaranteed for individual traffic classes, similarly as in weighted fair queueing. The paper describes a timed Petri net model of weighted priority queueing and uses discrete-event simulation of this model to obtain performance characteristics of simple queueing systems. The model is also used to analyze the effects of finite queue capacity on the performance of queueing systems.展开更多
This paper presents a Dynamic Cross-layer Data Queue Management approach (DC-DQM) based on priority to address the priority deviation problem in Delay-Tolerant Mobile Sensor Networks (DT-MSNs). Receiver-driven data de...This paper presents a Dynamic Cross-layer Data Queue Management approach (DC-DQM) based on priority to address the priority deviation problem in Delay-Tolerant Mobile Sensor Networks (DT-MSNs). Receiver-driven data delivery scheme is used for fast response to data transfers, and a priority based interaction model is adopted to identify the data priority. Three interactive parameters are introduced to prioritize and dynamically manage data queue. The experimental results show that it can ameliorate data delivery ratio and achieve good performance in terms of average delay.展开更多
This paper considers an efficient priority service model with two-level-polling scheme which the message packets conform to the discrete-time Geom/G/1 queue with multiple vacations and bulk arrival. By the embedded Ma...This paper considers an efficient priority service model with two-level-polling scheme which the message packets conform to the discrete-time Geom/G/1 queue with multiple vacations and bulk arrival. By the embedded Markov chain theory and the probability generating function method, we set up the mathematics functions and give closed form expressions for obtaining the mean cyclic period （MCP）, the mean queue length （MQL） and the mean waiting time （MWT） characteristics, the analytical results are also verified through extensive computer simulations. The performance analysis reveals that this priority polling scheme can gives better efficiency as well as impartiality in terms of system characteristics, and it can be used for differentiating priority service to guarantee better QoS and system stability in design and improvement of MAC protocol.展开更多
In multimedia cellular networks, when a Mobile Host requests multimedia services, it may experience hand-offs to several cells before the request is completely served. If a target cell cannot provide adequate bandwidt...In multimedia cellular networks, when a Mobile Host requests multimedia services, it may experience hand-offs to several cells before the request is completely served. If a target cell cannot provide adequate bandwidth for a service request, instead of directly dropping the request, the MH is put into the handoff queue and hopefully the requested bandwidth can be satisfied by later released bandwidth. Obviously, it is important to properly assign priorities for queued handoff of MHs based on their inborn dynamics to avoid unnecessary dropping. In this paper, we present a dynamic handoff priority adjustment scheme which applied a handoff queuing scheme to dynamically adjust handoff priority based on receiving signal strength, service class, and mobility of Mobile Hosts. In addition, idle bandwidth reserved by inactive MHs is reallocated to urgent handoff MHs to reduce the call dropping probability. The goal of the proposed dynamic handoff priority adjustment scheme is to further reduce call dropping probability while still maintaining high bandwidth utilization and acceptable call blocking probability on multimedia cellular networks.展开更多
We consider a real time data acquisition and processing multiserver system with identical servers (such as unmanned aerial vehicles, machine controllers, overhearing devices, medical monitoring devices, etc.) which ca...We consider a real time data acquisition and processing multiserver system with identical servers (such as unmanned aerial vehicles, machine controllers, overhearing devices, medical monitoring devices, etc.) which can be maintained/programmed for different kinds of activities (e.g. passive or active). This system provides a service for real time tasks arriving via several channels (such as surveillance regions, assembly lines, communication channels, etc.) and involves maintenance. We focus on the worst case analysis of the system with ample maintenance facilities exponentially distributed time to failure and maintenance times. We consider two kinds of models (with and without nonpreemptive priorities) and provide balance equations for steady state probabilities and various performance measures, when both operation and maintenance times are exponentially distributed.展开更多
Recently, there has been a rapid growing interest in new applications requiring quality of service (QoS) guarantees through wireless local area networks (WLAN). These demands have led to the introduction of new 802.11...Recently, there has been a rapid growing interest in new applications requiring quality of service (QoS) guarantees through wireless local area networks (WLAN). These demands have led to the introduction of new 802.11 standard series to enhance access medium supporting QoS for multimedia applications. However, some applications such as variable bit rate (VBR) traffic address some challenges in the hybrid coordination function (HCF) nominated to provide QoS. This paper presents a novel priority queuing model to analyze a medium access in the HCF controlled channel access (HCCA) mode. This model makes use of a MAP (Markovian Arrival Process)/PH (Phase Type)/1 queue with two types of jobs which are suitable to support VBR traffic. Using a MAP for traffic arrival process and PH distribution for service process, the inclusion of vacation period makes our analysis very general and comprehensive to support various types of practical traffic streams. The proposed priority queuing model is very useful to evaluate and enhance the performance of the scheduler and the admission controller in the HCCA mechanism.展开更多
In this paper, we consider a tandem of two head-of-line (HOL) non-preemptive priority queuing systems, each with a single server and a deterministic service-time. Two classes of traffic are considered, namely high pri...In this paper, we consider a tandem of two head-of-line (HOL) non-preemptive priority queuing systems, each with a single server and a deterministic service-time. Two classes of traffic are considered, namely high priority and low priority traffic. By means of a generating function approach, we present a technique to derive closed-form expressions for the mean buffer occupancy at each node and mean delay. Finally, we illustrate our solution technique with some numerical examples, whereby we illustrate the starvation impact of the HOL priority scheduling discipline on the performance of the low-priority traffic stream. Our research highlights the important fact that the unfairness of the HOL priority scheduling becomes even more noticeable at the network level. Thus this priority mechanism should be used with caution.展开更多
软件定义网络(Software Defined Network,SDN)技术通过控制平面与数据平面解耦,为通信网络优化提供了新思路。分析SDN关键技术特征,探讨传统通信网络在性能、安全和标准化等方面面临的挑战。从架构、技术及安全3个层面提出优化策略,通...软件定义网络(Software Defined Network,SDN)技术通过控制平面与数据平面解耦,为通信网络优化提供了新思路。分析SDN关键技术特征,探讨传统通信网络在性能、安全和标准化等方面面临的挑战。从架构、技术及安全3个层面提出优化策略,通过设计扁平化网络架构提高资源利用效率,提出基于OpenFlow的高效转发机制和软件定义的多队列优先级调度算法,构建纵深信任域安全架构。实验结果表明,该优化方案在高负载条件下的端到端时延降低约59.5%,网络吞吐量提升约33.0%,分布式拒绝服务(Distributed Denial of Service,DDoS)攻击检测时延降低75.9%,显著提升了网络性能。展开更多
针对星载路由设备的发展趋势,即交互速率提升、带宽增加以及设计轻量化,本文提出了一种基于改进轮询的星载高速交换算法的设计方案。该方案采用基于改进RR(Round Robin,轮询)调度算法和PBPW(Priority-based Bandwidth Privilege with We...针对星载路由设备的发展趋势,即交互速率提升、带宽增加以及设计轻量化,本文提出了一种基于改进轮询的星载高速交换算法的设计方案。该方案采用基于改进RR(Round Robin,轮询)调度算法和PBPW(Priority-based Bandwidth Privilege with Weighting,基于优先级并带权重的带宽特权)算法相结合的二级队列调度算法。在第一级调度中,引入优先级轮询调度,确保高优先级的数据帧能够优先转发,同时开放了缓存共享机制,一定程度上避免了拥塞和资源的浪费;在第二级调度中,为每条链路分配了阈值,从而避免了某些链路因“饥饿”而无法得到服务,同时防止了其他链路的拥塞问题。与传统的基于FIFO(First In First Out,先进先出)的简单队列调度算法相比,这种改进的轮询调度机制显著提高了星载路由器的转发速率,并降低了转发时延。此外,通过轮询方式实现了对高优先级数据帧的优先转发,进一步优化了路由器的性能。展开更多
基金financially supported by the National Basic Research Program of China (Grant No.2006CB400502)the Promotion of 100 Young Talent Scientist Project of the Chinese Acad-emy of Sciences (8-057493)the Special Meteorology Project(GYHY(QX)2007-6-1)
文摘Some depression cells with heights lower than their surrounding cells may often be found in Grid-based digital elevation models (DEM) dataset due to sampling errors.The depression-filling algorithm presented by Planchon and Darboux works very quickly compared to other published methods.Despite its simplicity and deli-cacy,this algorithm remains difficult to understand due to its three complex subroutines and its recursive execution.Another fast algorithm is presented in this article.The main idea of this new algorithm is as follows:first,the DEM dataset is viewed as an island and the outer space as an ocean;when the ocean level increases,the DEM cells on the island's boundary will be inundated;when a cell is inundated for the first time,its elevation is increased to the ocean level at that moment;after the ocean has inun-dated the entire DEM,all of the depressions are filled.The depression-removing processing is performed using a priority queue.Theoretically,this new algorithm is a fast algorithm despite the fact that it runs more slowly than Planchon and Darboux's method.Its time-complexity in both the worst case and in an average case is O(8nlog 2 (m)),which is close to O(n).The running speed of this algorithm depends mainly on the insertion operation of the priority queue.As shown by the tests,the depres-sion-filling effects of this algorithm are correct and valid,and the overall time consumption of this algorithm is less than twice the time consumed by Planchon & Darboux's method for handling a DEM smaller than 2500×2500 cells.More importantly,this new algorithm is simpler and easier to understand than Planchon and Darboux's method This advantage allows the correct program code to be written quickly.
基金the National Natural Science Foundation of China(No.10371053)
文摘We prove a heavy traffic limit theorem to justify diffusion approximations for multiclass queueing networks under preemptive priority service discipline and provide effective stochastic dynamical models for the systems. Such queueing networks appear typically in high-speed integrated services packet networks about telecommunication system. In the network, there is a number of packet traffic types. Each type needs a number of job classes （stages） of processing and each type of jobs is assigned the same priority rank at every station where it possibly receives service. Moreover, there is no inter-routing among different traffic types throughout the entire network.
文摘In this paper exhaustive-service priority-M/G/1 queueing systems with multiple vacations, single vacation and setup times are studied under the nonpreemptive and preemptive resume priority disciplines. For each of the six models analysed, the Laplace-Stieltjes transform of the virtual waiting time Wk(t) at time t of class k is derived by the method of collective marks. A sufficient condition for , where U has the standard normal distribution, is also given.
文摘We study a vacation queueing system with a single server simultaneously dealing with an M/G/1 and an M/D/1 queue. Two classes of units, priority and non-priority, arrive at the system in two independent Poisson streams. Under a non-preemptive priority rule, the server provides a general service to the priority units and a deterministic service to the non-priority units. We further assume that the server may take a vacation of random length just after serving the last priority unit present in the system. We obtain steady state queue size distribution at a random epoch. Corresponding results for some special cases, including the known results of the M/G/1 and the M/D/1 queues, have been derived.
文摘Weighted priority queueing is a modification of priority queueing that eliminates the possibility of blocking lower priority traffic. The weights assigned to priority classes determine the fractions of the bandwith that are guaranteed for individual traffic classes, similarly as in weighted fair queueing. The paper describes a timed Petri net model of weighted priority queueing and uses discrete-event simulation of this model to obtain performance characteristics of simple queueing systems. The model is also used to analyze the effects of finite queue capacity on the performance of queueing systems.
基金Supported by the Anhui Provincial Natural Science Foundation (No. 2012AKZR0330)Postdoctoral Science Foundation of China (No. 2012M521247)the Fundamental Research Funds for the Central Universities
文摘This paper presents a Dynamic Cross-layer Data Queue Management approach (DC-DQM) based on priority to address the priority deviation problem in Delay-Tolerant Mobile Sensor Networks (DT-MSNs). Receiver-driven data delivery scheme is used for fast response to data transfers, and a priority based interaction model is adopted to identify the data priority. Three interactive parameters are introduced to prioritize and dynamically manage data queue. The experimental results show that it can ameliorate data delivery ratio and achieve good performance in terms of average delay.
基金Supported by the National Natural Science Foundation of China （No. 69862001, F0424104, 60362001 and 61072079）.
文摘This paper considers an efficient priority service model with two-level-polling scheme which the message packets conform to the discrete-time Geom/G/1 queue with multiple vacations and bulk arrival. By the embedded Markov chain theory and the probability generating function method, we set up the mathematics functions and give closed form expressions for obtaining the mean cyclic period （MCP）, the mean queue length （MQL） and the mean waiting time （MWT） characteristics, the analytical results are also verified through extensive computer simulations. The performance analysis reveals that this priority polling scheme can gives better efficiency as well as impartiality in terms of system characteristics, and it can be used for differentiating priority service to guarantee better QoS and system stability in design and improvement of MAC protocol.
文摘In multimedia cellular networks, when a Mobile Host requests multimedia services, it may experience hand-offs to several cells before the request is completely served. If a target cell cannot provide adequate bandwidth for a service request, instead of directly dropping the request, the MH is put into the handoff queue and hopefully the requested bandwidth can be satisfied by later released bandwidth. Obviously, it is important to properly assign priorities for queued handoff of MHs based on their inborn dynamics to avoid unnecessary dropping. In this paper, we present a dynamic handoff priority adjustment scheme which applied a handoff queuing scheme to dynamically adjust handoff priority based on receiving signal strength, service class, and mobility of Mobile Hosts. In addition, idle bandwidth reserved by inactive MHs is reallocated to urgent handoff MHs to reduce the call dropping probability. The goal of the proposed dynamic handoff priority adjustment scheme is to further reduce call dropping probability while still maintaining high bandwidth utilization and acceptable call blocking probability on multimedia cellular networks.
文摘We consider a real time data acquisition and processing multiserver system with identical servers (such as unmanned aerial vehicles, machine controllers, overhearing devices, medical monitoring devices, etc.) which can be maintained/programmed for different kinds of activities (e.g. passive or active). This system provides a service for real time tasks arriving via several channels (such as surveillance regions, assembly lines, communication channels, etc.) and involves maintenance. We focus on the worst case analysis of the system with ample maintenance facilities exponentially distributed time to failure and maintenance times. We consider two kinds of models (with and without nonpreemptive priorities) and provide balance equations for steady state probabilities and various performance measures, when both operation and maintenance times are exponentially distributed.
文摘Recently, there has been a rapid growing interest in new applications requiring quality of service (QoS) guarantees through wireless local area networks (WLAN). These demands have led to the introduction of new 802.11 standard series to enhance access medium supporting QoS for multimedia applications. However, some applications such as variable bit rate (VBR) traffic address some challenges in the hybrid coordination function (HCF) nominated to provide QoS. This paper presents a novel priority queuing model to analyze a medium access in the HCF controlled channel access (HCCA) mode. This model makes use of a MAP (Markovian Arrival Process)/PH (Phase Type)/1 queue with two types of jobs which are suitable to support VBR traffic. Using a MAP for traffic arrival process and PH distribution for service process, the inclusion of vacation period makes our analysis very general and comprehensive to support various types of practical traffic streams. The proposed priority queuing model is very useful to evaluate and enhance the performance of the scheduler and the admission controller in the HCCA mechanism.
文摘In this paper, we consider a tandem of two head-of-line (HOL) non-preemptive priority queuing systems, each with a single server and a deterministic service-time. Two classes of traffic are considered, namely high priority and low priority traffic. By means of a generating function approach, we present a technique to derive closed-form expressions for the mean buffer occupancy at each node and mean delay. Finally, we illustrate our solution technique with some numerical examples, whereby we illustrate the starvation impact of the HOL priority scheduling discipline on the performance of the low-priority traffic stream. Our research highlights the important fact that the unfairness of the HOL priority scheduling becomes even more noticeable at the network level. Thus this priority mechanism should be used with caution.
文摘软件定义网络(Software Defined Network,SDN)技术通过控制平面与数据平面解耦,为通信网络优化提供了新思路。分析SDN关键技术特征,探讨传统通信网络在性能、安全和标准化等方面面临的挑战。从架构、技术及安全3个层面提出优化策略,通过设计扁平化网络架构提高资源利用效率,提出基于OpenFlow的高效转发机制和软件定义的多队列优先级调度算法,构建纵深信任域安全架构。实验结果表明,该优化方案在高负载条件下的端到端时延降低约59.5%,网络吞吐量提升约33.0%,分布式拒绝服务(Distributed Denial of Service,DDoS)攻击检测时延降低75.9%,显著提升了网络性能。
文摘针对星载路由设备的发展趋势,即交互速率提升、带宽增加以及设计轻量化,本文提出了一种基于改进轮询的星载高速交换算法的设计方案。该方案采用基于改进RR(Round Robin,轮询)调度算法和PBPW(Priority-based Bandwidth Privilege with Weighting,基于优先级并带权重的带宽特权)算法相结合的二级队列调度算法。在第一级调度中,引入优先级轮询调度,确保高优先级的数据帧能够优先转发,同时开放了缓存共享机制,一定程度上避免了拥塞和资源的浪费;在第二级调度中,为每条链路分配了阈值,从而避免了某些链路因“饥饿”而无法得到服务,同时防止了其他链路的拥塞问题。与传统的基于FIFO(First In First Out,先进先出)的简单队列调度算法相比,这种改进的轮询调度机制显著提高了星载路由器的转发速率,并降低了转发时延。此外,通过轮询方式实现了对高优先级数据帧的优先转发,进一步优化了路由器的性能。
