Multicast support in multi-chip centralized schedulers in Input Queued switches

IQ switches store packets at input ports to avoid the memory speedup required by OQ switches. However, packet schedulers are needed to determine an I/O (input/output) interconnection pattern that avoids conflicts among packets at output ports. Today, centralized, single-chip, scheduler implementation are largely dominant. In the near future, the multi-chip scheduler implementation will be needed to reduce the hardware scheduler complexity in very large, high-speed, switches. However, the multi-chip implementation implies introducing a non-negligible delay among input and output selectors used to determine the I/O interconnection pattern at each time slot. This delay, mainly due to inter-chip latency, requires modifications to traditional scheduling algorithms, which normally rely on the hypothesis that information exchange among selectors can be performed with negligible delay. We propose a novel multicast scheduler, named IMRR, an extension of a previously proposed multicast scheduling algorithm named mRRM, making it suitable to a multi-chip implementation, and examine its performance by simulation.     

Consistent proportional delay differentiation: A fuzzy control approach

Proportional delay differentiation (PDD) is an important service model for providing relative differentiated services on the Internet. It aims to maintain pre-specified packet queueing-delay ratios between different classes of traffic at each hop. Existing rate-allocation approaches for PDD services assume the average queueing delay of a class is inversely proportional to its service rate. This assumption is not necessarily valid when the system is not heavily loaded. To provide consistent PDD services under various load conditions, in this paper, we propose a novel rate-allocation approach that applies fuzzy control theory to capture the nonlinear relationship between the queueing delay and the service rate. In the approach, a class’s service rate is adjusted according to a set of fuzzy control rules defined over its error (the difference between the target delay ratio and the achieved one), the change of error, and the change of service rate. We prove that the fuzzy control system is stable and the service rate of a class converges to its equilibrium point at steady state. Simulation results demonstrate that, in comparison with other rate-allocation approaches, the fuzzy control approach is able to provide consistent PDD services under wide range load conditions. It is also shown robust under various system conditions, including with multiple classes, changing target delay ratios, changing load conditions, and different traffic patterns.     

A QoS-enhanced intelligent stochastic real-time packet scheduler for multimedia IP traffic

A re-configurable, QoS-enhanced intelligent stochastic real-time optimal fair packet scheduler, QUEST, for IP routers is proposed and investigated. The objective is to maximize the system QoS subject to the constraint that the processor utilization is kept at 100%. All past work on router schedulers for multimedia traffic were of earlier generation, in that they focused on maximizing utilization whereas being QoS-aware but without explicitly maximizing the QoS. Keeping utilization fixed at nearly 100%, QoS is dynamically maximized, thus moving to the next generation. QUEST’s other unique advantages are three-fold. First, it solves the challenging problem of starvation for low priority processes; second, it solves the major bottleneck of Earliest Deadline First scheduler’s failure at heavy traffic loads. Finally, QUEST offers the benefit of arbitrarily pre-programming the process utilization ratio. Three classes of multimedia IP traffic, namely, VoIP, IPTV and HTTP have been considered. Two most important QoS metrics, namely, packet loss rate (PLR) and mean waiting time, are addressed. All claims are supported by discrete event and Monte Carlo simulations. The proposed scheduler outperforms benchmark schedulers and offers 37% improvement in packet loss rate and 23% improvement in mean waiting time over the best competing current scheduler Accuracy-aware EDF. The proposed scheduler was validated in a test-bed platform of a NetFPGA® router and results were observed with Paessler® PRTG network monitor.

     

Delivering relative differentiated services in future high-speed networks using hierarchical dynamic deficit round robin

With the increasing deployment of real-time audio/video services over the Internet, provision of quality of service (QoS) has attracted much attention. When the line rate of future networks upgrades to multi-terabits per second, if routers/switches intend to deliver differentiated services through packet scheduling, the reduction of computational overhead and elimination of bottleneck resulting from memory latency will both become important factors. In addition, the decrease of average queueing delay and provision of small delays for short packets are two further critical factors influencing the delivery of better QoS for real-time applications. The advanced waiting time priority (AWTP) is a timestamp-based packet scheduler which is enhanced from the well-known WTP. Although AWTP considers the effect of packet size, the latency resulting from timestamp access and a great quantity of computational overhead may result in bottlenecks for AWTP being deployed over high-speed links. Many existing schedulers have the same problems. We propose a multi-level hierarchical dynamic deficit round-robin (MLHDDRR) scheduling scheme which is enhanced from the existing dynamic deficit round-robin scheduler. The new scheme can resolve these issues and efficiently provide relative differentiated services under a variety of load conditions. Besides, MLHDDRR can also protect the highest priority traffic from significant performance degradation due to bursts of low-priority traffic. We compare the performance of AWTP with the proposed scheme. Extensive simulation results and complexity analysis are presented to illustrate the effectiveness and efficiency of MLHDDRR.     

Quantum-Based Earliest Deadline First Scheduling for Multiservices

Latency-rate (LR) schedulers have shown their ability in providing fair and weighted sharing of bandwidth with an upper bound on delivery latency of packets while earliest departure first (EDF) schedulers have shown their ability in providing LR-decoupled service whereby the delivery latency of packets is not bounded by the reserved rate. However, EDF schedulers require traffic shapers to ensure flow protection. We propose quantum-based earliest deadline first scheduling (QEDF), a quantum-based scheduler that provides flow protection, throughput guarantee and delay bound guarantee for flows that require LR-coupled and LR-decoupled types of reservations. It classifies flows into time-critical (TC), jitter-sensitive (JS), and rate-based (RB) classes and uses a quality-of-service forwarding rule to determine the next packet to be serviced by the scheduler. It provides nonpreemptive priority service to TC queues. This allows LR-decoupled reservation for flows that have a low rate and intolerable delay. Packets from JS queues can be delayed by other packets if forwarding the latter will not result in the former missing its deadline. As a quantum-based scheduler, the QEDF scheduler provides throughput guarantees for RB queues. We present both analytical and simulation results of QEDF, whereby we evaluated QEDF in its deployment as a single-class as well as a multiservice scheduler     

A Comparison of Mamdani and Sugeno Fuzzy Based Packet Scheduler for MANET with a Realistic Wireless Propagation Model

 The mobile nature of the nodes in a wireless mobile ad-hoc network (MANET) and the error prone link connectivity between nodes pose many challenges. These include frequent route changes, high packet loss, etc. Such problems increase the end-toend delay and decrease the throughput. This paper proposes two adaptive priority packet scheduling algorithms for MANET based on Mamdani and Sugeno fuzzy inference system. The fuzzy systems consist of three input variables: data rate, signal-to-noise ratio (SNR) and queue size. The fuzzy decision system has been optimised to improve its efficiency. Both fuzzy systems were verified using the Matlab fuzzy toolbox and the performance of both algorithms were evaluated using the riverbed modeler (formally known as OPNET modeler). The results were compared to an existing fuzzy scheduler under various network loads, for constant-bit-rate (CBR) and variable-bit-rate (VBR) traffic. The measuring metrics which form the basis for performance evaluation are end-to-end delay, throughput and packet delivery ratio. The proposed Mamdani and Sugeno scheduler perform better than the existing scheduler for CBR traffic. The end-to-end delay for Mamdani and Sugeno scheduler was reduced by an average of 52% and 54%, respectively. The performance of the throughput and packet delivery ratio for CBR traffic are very similar to the existing scheduler because of the characteristic of the traffic. The network was also at full capacity. The proposed schedulers also showed a better performance for VBR traffic. The end-to-end delay was reduced by an average of 38% and 52%, respectively. Both the throughput and packet delivery ratio (PDR) increased by an average of 53% and 47%, respectively. The Mamdani scheduler is more computationally complex than the Sugeno scheduler, even though they both showed similar network performance. Thus, the Sugeno scheduler is more suitable for real-time applications.     

Providing QoS with the Deficit Table Scheduler

A key component for networks with Quality of Service (QoS) support is the egress link scheduling algorithm. An ideal scheduling algorithm implemented in a high-performance network with QoS support should satisfy two main properties: good end-to-end delay and implementation simplicity. Table-based schedulers try to offer a simple implementation and good latency bounds. Some of the latest proposals of network technologies, like Advanced Switching and InfiniBand, include in their specifications one of these schedulers. However, these table-based schedulers do not work properly with variable packet sizes, as is usually the case in current network technologies. We have proposed a new table-based scheduler, which we have called Deficit Table (DTable) scheduler, that works properly with variable packet sizes. Moreover, we have proposed a methodology to configure this table-based scheduler in such a way that it permits us to decouple the bounding between the bandwidth and latency assignments. In this paper, we thoroughly review the provision of QoS with the DTable scheduler and our configuration methodology, and evaluate the performance of our proposals in a multimedia scenario. Simulation results show that our proposals are able to provide a similar latency performance than more complex scheduling algorithms. Moreover, we show the advantages of our decoupling configuration methodology over the usual ways of configuring this kind of table-based schedulers.     

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.     

An 802.11e HCCA scheduler with an end-to-end quality aware territory method

In this paper we present a solution for the IEEE 802.11e HCCA (Hybrid coordination function Controlled Channel Access) mechanism which aims both at supporting strict real-time traffic requirements and, simultaneously, at handling TCP applications efficiently. Our proposal combines a packet scheduler and a dynamic resource allocation algorithm. The scheduling discipline is based on the Monolithic Shaper-Scheduler, which is a modification of a General Processor Sharing (GPS) related scheduler. It supports minimum-bandwidth and delay guarantees and, at the same time, it achieves the optimal latency of all the GPS-related schedulers. In addition, our innovative resource allocation procedure, called the territory method, aims at prioritizing real time services and at improving the performance of TCP applications. For this purpose, it splits the wireless channel capacity (in terms of transmission opportunities) into different territories for the different types of traffic, taking into account the end-to-end network dynamics. In order to give support to the desired applications, we consider the following traffic classes: conversational, streaming, interactive and best-effort. The so called territories shrink or expand depending on the current quality experienced by the corresponding traffic class. We evaluated the performance of our solution through extensive simulations in a heterogeneous wired-cum-wireless scenario under different traffic conditions. Additionally, we compare our proposal to other HCCA scheduling algorithms, the HCCA reference scheduler and Fair Hybrid Coordination Function (FHCF). The results show that the combination of the MSS and the territory method obtains higher system capacity for VoIP traffic (up to 32 users) in the simulated scenario, compared to FHCF and the HCCA reference scheduler (13 users). In addition, the MSS with the territory method also improves the throughput of TCP sources (one FTP application achieves between 6.1 Mbps without VoIP traffic and 2.1 Mbps with 20 VoIP users) compared to the reference scheduler (at most 388 kbps) and FHCF (with a maximum FTP throughput of 4.8 Mbps).     

Minimum delay load-balancing via nonparametric regression and no-regret algorithms

In the current network scenario, where traffic is increasingly dynamic and resource demanding, Dynamic Load-Balancing (DLB) has been shown to be an excellent Traffic Engineering tool. In particular, we are interested in the problem of minimum delay load-balancing. That is to say, we assume that the queueing delay of a link is given by a function of its load. The objective is then to adjust the traffic distribution over paths so that, for the current traffic demand, the addition of these functions times the load is minimized. The contribution of our article is twofold. Firstly, we analyze the possibility of using so-called no-regret algorithms to perform the load balancing. As opposed to other distributed optimization algorithms (such as the classical gradient descent) the algorithm we discuss requires no fine-tuning of any speed-controlling parameter. Secondly, we present a framework that does not assume any particular model for the queueing delay function, and instead learns it from measurements. This way, the resulting mean delay of optimizing with this learnt function is an excellent approximation of the real minimum delay traffic distribution. The whole framework is illustrated by several packet and flow level simulations.     

A robust packet scheduling algorithm for proportional delay differentiation services

Proportional delay differentiation (PDD) model is an important approach to relative differentiated services provisioning on the Internet. It aims to maintain pre-specified packet queueing-delay ratios between different classes of traffic at each hop. Existing PDD packet scheduling algorithms are able to achieve the goal in long time-scales when the system is highly utilized. This paper presents a new PDD scheduling algorithm, called Little’s average delay (LAD), based on a proof of Little’s Law. It monitors the arrival rate of the packets in each traffic class and the cumulative delays of the packets and schedules the packet according to their transient queueing properties in order to achieve the desired class delay ratios in both short and long time-scales. Simulation results show that LAD is able to provide predictable and controllable services in various system conditions and that such services, whenever feasible, can be guaranteed, independent of the distributions of packet arrivals and sizes. In comparison with other PDD scheduling algorithms, LAD can provide the same level of service quality in long time-scales and more accurate and robust control over the delay ratio in short time-scales. In particular, LAD outperforms its main competitors significantly when the desired delay ratio is large.     

Anchored opportunity queueing: a low-latency scheduler for fair arbitration among virtual channels

Many wormhole interconnection networks for parallel systems, and more recently system area networks, implement virtual channels to provide a number of services including improved link utilization and lower latencies. The forwarding of flits from the virtual channels on to the physical channel is typically accomplished using flit-based round-robin (FBRR) scheduling. This paper presents a novel scheduling strategy, anchored opportunity queueing (AOQ), which preserves the throughput and fairness characteristics of FBRR while significantly reducing the average delay experienced by packets. The AOQ scheduler achieves lower average latencies by trying, as far as possible, to complete the transmission of a complete packet before beginning the transmission of flits from another packet. The AOQ scheduler achieves provable fairness in the number of opportunities it offers to each of the virtual channels for transmissions of flits over the physical channel. We prove this by showing that the relative fairness bound, a popular measure of fairness, is a small finite constant in the case of the AOQ scheduler. Finally, we present simulation results comparing the delay characteristics of AOQ with other schedulers for virtual channels. The AOQ scheduler is simple to implement in hardware, and also offers a practical solution in other contexts such as in scheduling ATM cells in Internet backbone switches.     

A Garch-based adaptive playout delay algorithm for VoIP

Network delay, packet loss and network delay variability (jitter) are important factors that impact on perceived voice quality in VoIP networks. An adaptive playout buffer is used in a VoIP terminal to overcome jitter. Such a buffer-control must operate a trade-off between the buffer-induced delay and any additional packet loss rate. In this paper, a Garch-based adaptive playout algorithm is proposed which is capable of operating in both inter-talkspurt and intra-talkspurt modes. The proposed new model is based on a Garch model approach; an ARMA model is used to model changes in the mean and the variance. In addition, a parameter estimation procedure is proposed, termed Direct Garch whose cost function is designed to implement a desired packet loss rate whilst minimising the probability of consecutive packet losses occurring. Simulations were carried out to evaluate the performance of the proposed algorithm using recorded VoIP traces. The main result is as follows; given a target Packet Loss Rate (PLR) the Direct Garch algorithm produces parameter estimates which result in a PLR closer than other algorithms. In addition, the proposed Direct Garch algorithm offers the best trade-off between additional buffering delay and Packet Loss Rate (PLR) compared with other traditional algorithms.     

Delay-constrained routing problems: Accurate scheduling models and admission control

As shown in [1], the problem of routing a flow subject to a worst-case end-to-end delay constraint in a packed-based network can be formulated as a Mixed-Integer Second-Order Cone Program, and solved with general-p‘urpose tools in real time on realistic instances. However, that result only holds for one particular class of packet schedulers, Strictly Rate-Proportional ones, and implicitly considering each link to be fully loaded, so that the reserved rate of a flow coincides with its guaranteed rate. These assumptions make latency expressions simpler, and enforce perfect isolation between flows, i.e., admitting a new flow cannot increase the delay of existing ones. Other commonplace schedulers both yield more complex latency formulæ and do not enforce flow isolation. Furthermore, the delay actually depends on the guaranteed rate of the flow, which can be significantly larger than the reserved rate if the network is unloaded. In this paper we extend the result to other classes of schedulers and to a more accurate representation of the latency, showing that, even when admission control needs to be factored in, the problem is still efficiently solvable for realistic instances, provided that the right modeling choices are made.     

Partition oriented frame based fair scheduler

Proportionate fair schedulers provide an effective methodology for scheduling recurrent real-time tasks on multiprocessors. However, a drawback in these schedulers is that they ignore a task’s affinity towards the processor where it was executed last, causing frequent inter-processor task migrations which ultimately results in increased execution times. This paper presents Partition Oriented Frame Based Fair Scheduler (POFBFS), an efficient proportional fair scheduler for periodic firm and soft real-time tasks that ensures a bounded number of task migrations. Experimental results reveal that POFBFS can achieve 3 to 100 times reduction in the number of migrations suffered with respect to the General-ERfair algorithm (for a set of 25 to 100 tasks running on 2 to 8 processors) while simultaneously maintaining high fairness accuracy.     

Harmonic proportional bandwidth allocation and scheduling for service differentiation on streaming servers

To provide ubiquitous access to the proliferating rich media on the Internet, scalable streaming servers must be able to provide differentiated services to various client requests. Recent advances of transcoding technology make network-I/O bandwidth usages at the server communication ports controllable by request schedulers on the fly. In this article, we propose a transcoding-enabled bandwidth allocation scheme for service differentiation on streaming servers. It aims to deliver high bit rate streams to high priority request classes without overcompromising low priority request classes. We investigate the problem of providing differentiated streaming services at application level in two aspects: stream bandwidth allocation and request scheduling. We formulate the bandwidth allocation problem as an optimization of a harmonic utility function of the stream quality factors and derive the optimal streaming bit rates for requests of different classes under various server load conditions. We prove that the optimal allocation, referred to as harmonic proportional allocation, not only maximizes the system utility function, but also guarantees proportional fair sharing between classes with different prespecified differentiation weights. We evaluate the allocation scheme, in combination with two popular request scheduling approaches, via extensive simulations and compare it with an absolute differentiation strategy and a proportional-share strategy tailored from relative differentiation in networking. Simulation results show that the harmonic proportional allocation scheme can meet the objective of relative differentiation in both short and long timescales and greatly enhance the service availability and maintain low queueing delay when the streaming system is highly loaded.     

Analysis of transmission delay for a structured-priority packet-switching system

We consider a priority-based packet-switching system with three phases of the packet transmission time. Each packet belongs to one of several priority classes, and the packets of each class arrive at a switch in a Poisson process. The switch transmits queued packets on a priority basis with three phases of preemption mechanism. Namely, the transmission time of each packet consists of a preemptive-repeat part for the header, a preemptive-resume part for the information field, and a nonpreemptive part for the trailer. By an exact analysis of the associated queueing model, we obtain the Laplace-Stieltjes transform of the distribution function for the delay, i.e., the time from arrival to transmission completion, of a packet for each class. We derive a set of equations that calculates the mean response time for each class recursively. Based on this result, we plot the numerical values of the mean response times for several parameter settings. The probability generating function and the mean for the number of packets of each class present in the system at an arbitrary time are also given.     

Design of a crossbar VOQ real-time switch with clock-driven scheduling for a guaranteed delay bound

Most commercial network switches are designed to achieve good average throughput and delay needed for Internet traffic, whereas hard real-time applications demand a bounded delay. Our real-time switch combines clearance-time-optimal switching with clock-based scheduling on a crossbar switching fabric. We use real-time virtual machine tasks to serve both periodic and aperiodic traffic, which simplifies analysis and provides isolation from other system operations. We can then show that any feasible traffic will be switched in two clock periods. This delay bound is enabled by introducing one-shot traffic, which can be constructed at the cost of a fixed delay of one clock period. We carry out simulation to compare our switch with the popular iSLIP crossbar switch scheduler. Our switch has a larger schedulability region, a bounded lower end-to-end switching delay, and a shorter clearance time which is the time required to serve every packet in the system.     

Enhanced bulk scheduling for supporting delay sensitive streaming applications

Providing end-to-end delay guarantees for delay sensitive applications is an important packet scheduling issue with routers. In this paper, to support end-to-end delay requirements, we propose a novel network scheduling scheme, called the bulk scheduling scheme (BSS), which is built on top of existing schedulers of intermediate nodes without modifying transmission protocols on either the sender or receiver sides. By inserting special control packets, which called TED (Traffic Specification with End-to-end Deadline) packets, into packet flows at the ingress router periodically, the BSS schedulers of the intermediate nodes can dynamically allocate the necessary bandwidth to each flow to enforce the end-to-end delay, according to the information in the TED packets. The introduction of TED packets incurs less overhead than the per-packet marking approaches. Three flow bandwidth estimation methods are presented, and their performance properties are analyzed. BSS also provides a dropping policy for discarding late packets and a feedback mechanism for discovering and resolving bottlenecks. The simulation results show that BSS performs efficiently as expected.     

General packet induced queueing schemes for reducing packet delays in ADSL routers with peer-to-peer file sharing applications

This paper proposes a class of queueing schemes named general packet induced queueing schemes (GPIQS) in ADSL routers to reduce the queueing delays of non-P2P packets. The objective of the proposed queueing schemes is to send out the general packets first as well as P2P packets are able to be sent in a bounded queueing delay. The proposed queueing schemes use the general packet to induce the transmission of P2P packets which are from the same client and arrived at the ADSL router before the general packet. The outbound order of the packets transmitted from a specific client is not altered in the proposed schemes. Two queueing schemes named general packet induced queueing scheme with single P2P queue (GPIQS-SQ) and general packet induced queueing scheme with multiple P2P queues (GPIQS-MQ) are proposed. The two proposed queueing schemes differ in the number of P2P queues. In order to prevent the unlimited waiting time of P2P packets, we introduced a variable called the largest number of preempting packets to send out the P2P packets in a bounded time. Simulation results show that the proposed queueing schemes may send out the packets from ADSL router efficiently and the average queueing delay is smaller than the common used first-come first-served algorithm. Specifically, the GPIQS-MQ performs better than the GPIQS-SQ method in terms of average queueing delay of non-P2P packets. We also found that the increased average queueing delay of P2P packets is small. Finally, the values of the largest number of preempting packets are discussed.