Optimal Measurement-based Pricing for an M/M/1 Queue

In this paper, we consider a system modelled as an M/M/1 queue. Jobs corresponding to different classes are sent to the queue and are characterized by a delay cost per unit of time and a demand function. Our goal is to design an optimal pricing scheme for the queue, where the total charge depends on both the mean delay at the queue and arrival rate of each customer. We also assume that those two values have to be (statistically) measured, introducing errors on the total charge that might avert jobs from using the system, and then decrease demand. This model can be applied in telecommunication networks, where pricing can be used to control congestion, and the network can be characterized by a single bottleneck queue; the throughput of each class would be determined through passive measurements while the delay would be determined through active measurements.     

Stable Scheduling Policies for Maximizing Throughput in Generalized Constrained Queueing Systems

We consider a class of queueing networks referred to as "generalized constrained queueing networks" which form the basis of several different communication networks and information systems. These networks consist of a collection of queues such that only certain sets of queues can be concurrently served. Whenever a queue is served, the system receives a certain reward. Different rewards are obtained for serving different queues, and furthermore, the reward obtained for serving a queue depends on the set of concurrently served queues. We demonstrate that the dependence of the rewards on the schedules alter fundamental relations between performance metrics like throughput and stability. Specifically, maximizing the throughput is no longer equivalent to maximizing the stability region; we therefore need to maximize one subject to certain constraints on the other. Since stability is critical for bounding packet delays and buffer overflow, we focus on maximizing the throughput subject to stabilizing the system. We design provably optimal scheduling strategies that attain this goal by scheduling the queues for service based on the queue lengths and the rewards provided by different selections. The proposed scheduling strategies are however computationally complex. We subsequently develop techniques to reduce the complexity and yet attain the same throughput and stability region. We demonstrate that our framework is general enough to accommodate random rewards and random scheduling constraints.     

An efficient implementation of bypass queue under bursty traffic

In this paper we present a new bypass queue scheme for an input buffered nonblocking packet switch operating under bursty traffic. The proposed scheme uses first-in-first-out (FIFO) queues and is thus more efficient for implementation as compared to other schemes which use first-in-random-out (FIRO) queues. Maximum throughput comparison of the proposed scheme with the conventional scheme shows significant improvement.     

基于讨价还价能力的双渠道供应链定价模式选择

针对由网络直销渠道和电子零售渠道组成的双渠道供应链进行研究。基于制造商和零售商之间的谈判能力对比, 通过博弈建模分析了三种零售价定价模式下供应链成员的价格决策和物流服务水平决策。研究表明, 在制造商谈判能力较弱的情况下, 制造商统一定价模式是最优模式; 在制造商谈判能力较强的情况下, 以直销价格为协商基础的分别定价模式是最优模式; 在最优模式下, 制造商和供应链的利润都显著占优, 电子零售商提供的物流服务水平也相应最高, 但电子零售商的利润受定价模式的影响不显著, 最优模式也是双方接受的均衡策略。     

Performance evaluation for DRED discrete-time queueing network analytical model

Due to the rapid development in computer networks, congestion becomes a critical issue. Congestion usually occurs when the connection demands on network resources, i.e. buffer spaces, exceed the available ones. We propose in this paper a new discrete-time queueing network analytical model based on dynamic random early drop (DRED) algorithm to control the congestion in early stages. We apply our analytical model on two-queue nodes queueing network. Furthermore, we compare between the proposed analytical model and three known active queue management (AQM) algorithms, including DRED, random early detection (RED) and adaptive RED, in order to figure out which of them offers better quality of service (QoS). We also experimentally compare the queue nodes of the proposed analytical model and the three AQM methods in terms of different performance measures, including, average queue length, average queueing delay, throughput, packet loss probability, etc., aiming to determine the queue node that offers better performance.     

Analysis of a rate-based feedback control strategy for long haul data transport

Digital communication has become fast enough so that the speed of light has become a bottleneck. For example, the round trip transcontinental [USA] delay through a fiber link is approximately 0.04 s; at 150 Megabit/s, a source needs to transmit approximately 8,000,000 bits during one round trip time to utilize the bandwidth fully. As the service rates of queues get large, the time scales of congestion in those queues decrease relative to the round trip time, making the dual goals of keeping buffers small and utilizations high even more difficult to achieve. In this paper we analyze a class of delayed feedback schemes that achieve these goals despite propagation delays and regardless of network rates. We analyze the delayed feedback schemes as a system of delay-differential equations, in which we model the queue-length process and the rate at which a source transmits data as fluids. We assume that a stream of acknowledgements carries information about the state of a bottleneck queue back to the source, which adapts its transmission rate according to any monotone function of that state. We show stability for this class of schemes, in that their rate of transmission and queue length rapidly converge to a small neighborhood of the designed operating point. We identify the appropriate scaling of the model's parameters, as a function of network speed, for the system to perform optimally: with a deterministic service rate of μ at the bottleneck queue, the steady state utilization of the queue is and steady state delay is . We also describe the transient of behavior of the system as another source suddenly starts competing for the bandwidth resources at the bottleneck queue. This work directly applies to the adaptive control of Frame Relay and ATM networks, both of which provide feedback to users on congestion.     

Approximate analysis of a discrete-time tandem network of cut-through queues with blocking and bursty traffic

A discrete-time tandem network of cut-through queues is presented. The model allows finite capacity queues, blocking, and bursty traffic. A new bursty arrival process, IBK(k), for cut-through traffic is introduced. The tandem network is analyzed using single-node decomposition. Each queue is analyzed numerically in isolation assuming that its arrival and service processes are known. The parameters of the arrival and service processes of the queues are obtained using an iterative scheme. The results obtained are approximate and validation tests have shown that the model has good accuracy. Using this model, the packet loss, throughput, and queue length distributions were obtained for different traffic parameters and queue sizes.     

Packet video transport in ATM networks with single-bit feedback

The promise of a broadband integrated service digital network has led to the design of mechanisms for efficient transport of real-time compressed video in packet switching networks. We examine feedback control for video transport in ATM networks where the available feedback is a single bit of information carried in the cell header. We investigate the performance of three single-bit schemes for source rate adaptation. Two were originally for congestion control of bursty data traffic and are modified to control video traffic. The third scheme conveys more information about the state of queue(s) at the bottleneck. The simulation results show that all three schemes for feedback control of VBR video streams work remarkably well. During severe network congestion, the signal quality degrades gracefully, but not uniformly across all connections. Based on insights from the initial simulations, we propose a scheme to improve the fairness of service and demonstrate its effectiveness.     

Modeling and performance analysis for IPv6 traffic with multiple QoS classes

This paper focuses on the modeling and performance analysis for IPv6 traffic with multi-class QoS in virtual private networks (VPN). The multi-class QoS is implemented on differentiated service basis using priority scheme of 4 bits defined in the packet header of IPv6. A VPN-enabled IP router is modeled as a tandem queuing system in which each output link consists of two parallel priority output queues. The high-priority queue is used to carry the delay sensitive traffic while the low-priority queue is used to carry the delay insensitive traffic. On the other hand, multiple thresholds are implemented in each queue, respectively, for packet loss priority control. The performance analysis is done using fluid flow techniques. The numerical results obtained from the analysis show that the differentiated service based on the priority schemes defined in IPv6 is able to effectively satisfy the multi-class QoS requirement for supporting multimedia services in VPN. The performance trade-off between the delay sensitive traffic and delay insensitive traffic in terms of traffic throughput, packet loss probability and end-to-end delay in VPN networks is presented.     

A survey of pricing for integrated service networks

Advances in technology have greatly increased the demand for a single integrated service network that can provide multiple service classes for different user requirements. For such a multiple-service network, congestion control is one of the key issues to be addressed. However, without an appropriate mechanism to encourage end users to use the network properly, over-utilization and congestion are unavoidable. For this problem, it is widely accepted that pricing is a proper tool to manage congestion, encourage network growth, and allocate resource to users in a fair manner. However, how to charge for the traffic and at what price is still under study. In this paper, we first briefly review the state of the art and technological growth of congestion control for integrated service networks (ISN). Subsequently, we present a summary of the recent developments on various pricing policies and different charging and billing schemes that have been proposed for ATM and Internet Differentiated Services. Some architecture and implementation issues are also discussed. Finally, some future trends are identified.     

QoS-aware downlink packet scheduling for LTE networks

Scheduling for flows has been studied before. However, applying the previous schemes directly for LTE networks may not achieve good performance. To have good performance, both frequency domain allocations and time domain allocations for LTE resource blocks are suggested. Our method is suitable for real-time services and it consists of three phases. In frequency domain we design our method to utilize the RBs effectively. In time domain we first manage queues for different applications and propose a mechanism for predicting the packet delays. We introduce the concept of virtual queue to predict the behavior of future incoming packets based on the packets in the current queue. Then based on the calculated results, we introduce a cut-in process to rearrange the transmission order and discard those packets which cannot meet their delay requirements. We compare our scheduling mechanism with maximum throughput, proportional fair, modified largest delay first and exponential proportional fair. Simulation results show our scheduling method can achieve better performance than other schemes.     

A novel self-tuning feedback controller for active queue management supporting TCP flows

Wireless access points act as bridges between wireless and wired networks. Since the actually available bandwidth in wireless networks is much smaller than that in wired networks, there is a bandwidth disparity in channel capacity which makes the access point a significant network congestion point. The recently proposed active queue management (AQM) is an effective method used in wired network and wired-wireless network routers for congestion control, and to achieve a tradeoff between channel utilization and delay. The de facto standard, the random early detection (RED) AQM scheme, and most of its variants use average queue length as a congestion indicator to trigger packet dropping. In this paper, we propose a Novel autonomous Proportional and Differential RED algorithm, called NPD-RED, as an extension of RED. NPD-RED is based on a self-tuning feedback proportional and differential controller, which not only considers the instantaneous queue length at the current time point, but also takes into consideration the ratio of the current differential error signal to the buffer size. Furthermore, we give theoretical analysis of the system stability and give guidelines for the selection of feedback gains for the TCP/RED system to stabilize the instantaneous queue length at a desirable level. Extensive simulations have been conducted with ns2. The simulation results have demonstrated that the proposed NPD-RED algorithm outperforms the existing AQM schemes in terms of average queue length, average throughput, and stability.     

Congestion control based dynamic routing in ATM networks

In this paper we describe briefly a dynamic multi-path algorithm that has been considered for connection oriented asynchronous transfer mode (ATM) networks. Our scheme takes advantage of a cell multiplexing capability that has particular advantage in networks supporting variable bit rate (VBR) traffic. The fundamental objective of the scheme is to propose a congestion control based scheme that bridges the gap between routing and congestion control as the network becomes congested. The proposed routing scheme works as a shortest path first algorithm under light traffic conditions. However, as the shortest path becomes congested under unbalanced heavy traffic, the source uses multiple paths when and if available to distribute the calls and reduce cell loss. This mechanism will provide good Quality of Service for clients within the given constraints. We compare the performance of the proposed scheme with other competitive schemes. The throughput and cell loss performance are compared via simulations. These have been carried out concentrating on a five node network, each with varying traffic patterns, with the intention of gaining insight into the strengths and weaknesses of the various schemes.     

Optimal anticipative scheduling with asynchronous transmissionopportunities

Service is provided to a set of parallel queues by a single server. The service of queue i may be initiated only at certain time instances {t_nⁱ}_n=1^∞ that constitute the connectivity instances for queue i. The service of different customers cannot overlap. Scheduling is required to resolve potential contention of services initiated at closely spaced, closer than the service time, connectivity instances. At any time t, the future connectivity instances are available for scheduling. An anticipative policy is given, which at time t schedules the transmissions until a certain future time t+h. The length of the scheduling horizon h is selected based on the backlog at t. The allocation of the server in the interval [t, t+h], is done in accordance to the backlogs of the individual queues at t. The throughput region of the system is characterized, and it is shown that the policy we propose achieves maximum throughput. The policy has a low implementation complexity which is bounded for all the achievable throughput vectors. The average delay and the scheduling complexity are studied by simulation, and the trade-off between the two is demonstrated. The above scheduling problem arises in the access layer of the cross-links of a satellite network     

An approximate MVA algorithm for exponential, class-dependent multiple servers

Mean value analysis (MVA) is an efficient algorithm for determining the mean sojourn time, the mean queue length, and the throughput in a closed multiclass queueing network. It provides exact results for the class of product-form networks. Often different classes have different service requirements in FCFS queues, but such networks are not of product form. There are several possibilities to compute performance measure for such nodes and networks. In this paper we present an approximation formula for multiple-server FCFS queues with class-dependent service times as a Norton flow equivalent product node, where the departure rate of any class depends on the number of customers of all classes in the queue. We will use this approximation in the sojourn time formula of some exact and approximate MVA algorithms.     

Asymptotic bounds of throughput in series-parallel queueing networks

We propose a piece-wise linear upper bound on the throughput rate from a network of series-parallel queues where arrivals occur through a single infinite queue. This bound is tight and is observed to be extremely accurate in forecasting the actual throughput rate. We also describe the monotonicity of throughput as a function of the arrival rate and specify a condition under which the upper bound may be computed. We approximate analytically the throughput measured as a function of the arrival rate for two tandem exponential queues, where the first queue has an infinite buffer while the second queue has a finite buffer. We extend this analysis to elementary split and merge queueing networks. We demonstrate the generality and robustness of this asymptotic property, for larger series-parallel networks with general service times and specify the set up of a single simulation experiment which can be used to retrieve the throughput for any arrival rate, as well as other networks performance measures.     

基于LAA-WiFi智慧医疗的网络优化拥塞控制方法

为了对无线异构共存网络进行优化并对拥塞进行控制,通过授权辅助接入和无线保真对网络优化模型进行了设计,并以马尔科夫链来辅助建模。为了解决吞吐量问题,对不同公平约束下的最大吞吐量进行了问题优化,并引入了虚拟队列来对拥塞进行控制。实验结果显示,LAA-WiFi模型下共存网络总吞吐量的仿真值最大值为0.99。虚拟队列方法下吞吐量的最大值约为317,最小值约为108。LAA-WiFi模型可以对网络拥塞问题进行缓解,且其引入的虚拟队列方法可以对吞吐量下降问题进行解决。研究结果可以扩展到其他的领域,给不同场景的无线异构共存网络的优化和拥塞控制提供借鉴。     

Design and Analysis of a Multiscale Active Queue Management Scheme

Since Internet is dominated by TCP-based applications, active queue management （AQM） is considered as an effective way for congestion control. However, most AQM schemes suffer obvious performance degradation with dynamic traffic. Extensive measurements found that Internet traffic is extremely bursty and possibly self-similar. We propose in this paper a new AQM scheme called multiscale controller （MSC） based on the understanding of traffic burstiness in multiple time scale. Different from most of other AQM schemes, MSC combines rate-based and queue-based control in two time scales. While the rate-based dropping on burst level （large time scales） determines the packet drop aggressiveness and is responsible for low and stable queuing delay, good robustness and responsiveness, the queue-based modulation of the packet drop probability on packet level （small time scales） will bring low loss and high throughput. Stability analysis is performed based on a fluid-flow model of the TCP/MSC congestion control system and simulation results show that MSC outperforms many of the current AQM schemes.     

Fuzzy-Based Dynamic Distributed Queue Scheduling for Packet Switched Networks

Addressing the problem of queue scheduling for the packet-switched system is a vital aspect of congestion control. In this paper, the fuzzy logic based decision method is adopted for queue scheduling in order to enforce some level of control for traffic of different quality of service requirements using predetermined values. The fuzzy scheduler proposed in this paper takes into account the dynamic nature of the Internet traffic with respect to its time-varying packet arrival process that affects the network states and performance. Three queues are defined, viz low, medium and high priority queues. The choice of prioritizing packets influences how queues are served. The fuzzy scheduler not only utilizes queue priority in the queue scheduling scheme, but also considers packet drop susceptibility and queue limit. Through simulation it is shown that the fuzzy scheduler is more appropriate for the dynamic nature of Internet traffic in a packet-switched system as compared with some existing queue scheduling methods. Results show that the scheduling strategy of the proposed fuzzy scheduler reduces packet drop, provides good link utilization and minimizes queue delay as compared with the priority queuing (PQ), first-in-first-out (FIFO), and weighted fair queuing (WFQ).     

Path-wise performance in a tree-type network: Per-stream loss probability,delay, and delay variance analyses

This paper deals with path-wise performance analysis rather than a nodal one to enrich results previously obtained in the literature under simple but unsatisfactory assumptions, e.g., Poisson processes. First deriving the per-stream loss probability, delay, and delay variance of an isolated queue with multi-class input streams modeled by heterogeneous two-state Markov-modulated Poisson processes (MMPPs), we then propose simple and novel decomposition schemes working together with an input parameter modification scheme to (approximately) extract the per-stream output process for a lossy queue receiving MMPPs under a general service time distribution. The novelty of the decompositions is that they can be easily implemented based on a lossless queueing model. Through numerical experiments, we show that the accuracy in estimating the per-stream output process using such schemes is good. These decomposition schemes together with the input parameter modification scheme and a moment-based fitting algorithm used to fit the per-stream output as a two-state MMPP make analysis of path-wise performance viable by virtually treating each node in isolation along a path to get performance measures sequentially from the source node en route to the destination node.