Main

WP 4

WP4: Packet buffering and scheduling (partners P1, P2, P3, INT1, INT3).

In various subsystems of communication networks (such as multiplexers, switching elements, traffic shapers, routers, gateways, rate adapters, …), buffers are used to absorb a (temporary) oversupply of information units (or packets) awaiting a later transmission opportunity. These buffers are nothing but a special kind of queueing systems, where the packets to be transmitted are the customers, where the channels over which the packets are sent are the servers, and where the transmission of packets from the buffer corresponds to the servicing of customers. In digital communication networks, “synchronous transmission” is used. This means that the time axis is segmented into intervals (“slots”) of fixed length and that the successive transmissions of packets are synchronized to the slot boundaries. As the slot boundaries constitute a discrete sequence of time points, discrete time queueing theory is the preeminent tool to study the behavior of the buffers mentioned above. The performance of a buffer system is related to the buffer occupancy and measured by the loss probability or loss ratio, and the waiting time or delay of the packets. A queueing model uses stochastic characterizations for the supply of packets to the buffer (arrival process) and the removal of packets from the buffer (service process). Other important elements in the model are the storage capacity of the buffer, the packet rejection rule (buffer management technique) in case of (nearly) full buffers, and the order of service (scheduling discipline or queueing discipline). If we restrict ourselves to discrete time models, uncorrelated arrivals from slot to slot, constant service times of one slot each, and first-come-first-served (FCFS) scheduling are the simplest imaginable assumptions. A non-exhaustive list of extensions, generalizations or complications to be dealt with in the project is discussed below.

SWP4.1: Buffers with generalized source models and arrival models.

This SWP deals with the development of new techniques of analysis for buffer systems fed by traffic generated by the more realistic source models developed in SWP2.3 and abstracted into suitable macro models in SWP1.2. Although there has been a vast volume of research on this topic during the past two decades, investigating such (macro) models as Markov-modulated arrivals, on/off-sources, train arrivals, batch renewal arrivals, etc., it is our conviction that it must be possible to arrive at yet more powerful, realistic, versatile and analytically tractable macro-models than available today. Also, the combination of these macro arrival models with the use of (H)ARQ for the recovery of erroneous packets sent from the buffer (discussed in SWP3.1) has not been studied well yet. Some lines that will be explored in this project are the following:

Buffers with D-BMAP arrivals.

A Discrete-Batch Markovian Arrival Process (D-BMAP) is a (parameterized macro) source model whereby one or more sources inject packets into a buffer ([Kim2010], [Lee2005], [Bae2004], [Avr2008], [Ste2011]). Each source can find itself in a finite number of possible source states, transitions between source states are (first-order) Markovian from slot to slot, and the number of packets generated by a source in any given slot may depend both on the current state (during this slot) and the previous state (one slot earlier) of the source. Various well-known source models, such as on/off-sources, interrupted Bernoulli arrivals, Markov-modulated Bernoulli/Poisson arrivals etc., are in fact special cases of the D-BMAP model. In this project we intend to derive generic results valid for the most general types of D-BMAP arrival processes. Some topics are:

  • homogeneous (identical) and heterogeneous (non-identical) sources;
  • periodic traffic sources as special D-BMAP’s;
  • constant-length packets or variable-length packets;
  • class-independent or class-dependent packet lengths (in case of heterogeneous sources);
  • derivation of computationally efficient formulas and algorithms to compute both global and per-class buffer occupancy, packet delay, loss ratio, etc.

Buffers with session-based arrival streams.

A session-based arrival model ([Hof2010], [Wal2009]) assumes that packets entering a buffer are generated by some (finite or infinite) user population, where each user is capable of starting and ending finite-length sessions during which they are active and generate traffic. For instance, in a web server on the Internet ([Hof2008], [Wal2009], [Liu2001], [Mei2001]), a session could correspond to a file download by a user. Session-based arrival models are, in fact, macro source models related to train arrival models ([Kam2006], [Vuy2002]), in that packets are typically generated by the users in bursts that may last for multiple slots. In the most general session-based arrival models, however, the traffic generated by the users is not uniform in every time slot, but can vary (e.g. in a periodic or an on/off manner) during a session. A non-exhaustive list of possible assumptions that will be dealt with in this project is as follows:

  • number of new starting sessions (generated by the aggregated user population) independent or first-order Markovian (with 2 - or more - states) from slot to slot;
  • number of packets generated per session geometrically distributed (i.e., memoryless) or deterministic or more general;
  • session-length (in slots) geometrically distributed or deterministic or more general;
  • number of packets generated per slot during an active session deterministic or independent from slot to slot;
  • time between successive packets during a session deterministic, geometric or more general;
  • on/off-periods with deterministic, geometric or generally distributed lengths, during a session.

Performance analysis of various specific applications of these new macro-models (such as web servers, cell-based mobile communications, layered communication protocols) will be emphasized.

SWP4.2: Buffers with generalized scheduling disciplines and packet rejection rules.

When more than one packet is waiting in a buffer, the next packet to be transmitted is determined by the queueing discipline or scheduling discipline applied in the system ([Kle1975], [Bru1993], [Kim2011], [Sho2010]). In this SWP, we intend to study more general mechanisms than the classical first-come-first-served (FCFS) rule. We make a distinction between single-class systems, where all packets are treated equivalently, and multiclass systems, where differential treatment of packets depending on the class or type they belong to (e.g. data, video, voice) is possible. In single-class systems, the term “queueing discipline” refers to a rule that determines the order - and possibly also the way - in which packets are being served. In multiclass queueing systems, there is an additional dimension associated with the service process, in that some rule must decide which packet class is to be served next. We refer to this aspect of the service mechanism with the term “scheduling discipline”. In a general multiclass system, there may be both a scheduling algorithm, determining how the servers are shared among the different traffic classes, and a number of queueing disciplines (one for each class) describing the rules according to which individual packets are being served within each class. It is clear that scheduling and queueing disciplines can be used to implement (class) differentiation in the delay characteristics of buffers ([Nag2009]. In order to do this properly (i.e., in accordance with the delay requirements of the various traffic classes), the relationship between the parameters of the scheduling discipline and the resulting delay characteristics must be revealed, which is a very challenging task. On the other hand, different packet rejection rules (also known as buffer management techniques) can be used to achieve loss differentiation in buffers ([Bie2011], [Mah2011], [Arg2010], [Avr2010], [Dem2011]). In this case, packets of different classes are treated differently with respect to their admittance to the buffer, when the buffer occupancy is close to the storage capacity. Here again, fundamental analysis is required to reveal the impact of different rejection rules on the resulting loss characteristics, such as the loss probabilities of each traffic class, the loss periods and the lossless periods, the numbers of consecutive losses, the conditional loss probability given that loss occurs, etc.

Although there has been reported a lot of research work in the literature on scheduling disciplines and packet rejection rules, we do foresee to contribute to this area in the framework of this project. One reason for this is that much of the known results are related to continuous-time rather than discrete-time models. Another factor is that we wish to combine non-FCFS disciplines with various types of generalized arrival and source models (as described in SWP2.3 and SWP4.1 of this proposal) and with the use of (H)ARQ protocols for the recovery of erroneous packets sent from the buffer (as discussed in SWP3.1).

Some of the envisaged scheduling disciplines and packet rejection rules are:

  • dynamic priority scheduling, where different traffic classes have different (delay or loss) priorities that may vary in time, e.g. as a consequence of priority jumps (see e.g. [Xie2009], [Mae2009], [Cho2001]) ;
  • reservation schemes, where high-priority customers are given access to (favorable) reserved spaces spread around in the buffer (see e.g. [Bur2000], [Vuy2008a], [Vuy2008b]) ;
  • push-out mechanisms, where high-priority packets have the right to take the place of (“push out”) low-priority packets in the buffer (see e.g. [Avr2005], [Yan2011]) ;
  • partial buffer sharing techniques, where low-priority packets are denied access to the buffer once the buffer occupancy has exceeded a given threshold (see e.g. [Dem2011], [Jol2010]) ;
  • combined scheduling and packet rejection rules (see e.g. [Jol2010]).

SWP4.3: Spectrum management and opportunistic scheduling in cognitive radio networks.

With opportunistic scheduling in a cognitive radio setting, as discussed in WP2 and WP3, the goal is to accommodate SUs on a set of frequency channels without disrupting the communications of the PUs on those channels ([Aky2008]).

One factor that stands in the way of further development and market acceptance of cognitive systems is the currently limited understanding of their expected performance and achievable gains. If we consider the transmission of SU packets by a cognitive device, at least two features make traditional queueing models unfit for performance predictions: the fact that packets are sent over one of N available channels only during periods of limited PU activity, and the overhead resulting from the cognitive functions (sensing, learning, handover, cooperation) that guide this process. Both will impact the SU throughput and queueing behavior in a non-trivial way ([Sri2007]). We therefore will propose and study models making realistic assumptions with regard to:

  • the PU activity profile on the available channels, i.e., the stochastic process that determines where and when the spectral holes occur; so far, mainly single-channel models with Markov on/off or M/G/1 PU activity have been considered ([Su2008]), while we intend to look explicitly at interactions between the channels ([Pla2011]) and develop suitable parameterized macro-models for the PU activity, based on this;
  • the SU cognitive functionalities such as spectrum sensing and handover; the time in which sensing and handover are performed is far from negligible and the outcome of these functions is not always perfect, nor unique ([Kim2008]); also, by cooperating, SUs can improve their performance but a certain amount of signalling will be required and both will affect throughput and delay;
  • external processes such as the traffic demand, the error statistics and the error control mechanisms (e.g. HARQ, as discussed in SWP3.1) that will also influence the SU throughput and delay.