# A Fair Scheduling Scheme for HCF
## A Fair Scheduling Scheme for HCF

Qiang Ni, Pierre Ansel, Thierry Turletti

► To cite this version:

Qiang Ni, Pierre Ansel, Thierry Turletti. A Fair Scheduling Scheme for HCF A Fair Scheduling Scheme for HCF. 2003. hal-04650183

HAL Id: hal-04650183

https://inria.hal.science/hal-04650183v1

Submitted on 16 Jul 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Fair Scheduling Scheme for HCF

Qiang Ni, Pierre Ansel, Thierry Turletti

Qiang.Ni@Sophia.inria.fr

Thierry.Turletti@Sophia.inria.fr

INRIA Sophia Antipolis, France
# INTRODUCTION

* There is a simple round-robin scheduler in 802.11e D4.2 for HCF controlled channel access mechanism

* We have implemented 802.11e D4.2 HCF (HCCA and EDCF) in *ns* (network simulator)

* From simulation we found such a HCF scheduler is good for periodic CBR (Constant Bit Rate) traffic, but not good for VBR (Variable Bit Rate) traffic (such as Poisson, bursty traffic)
<figure><img src="image_2.png" /><figcaption>Simulation Topology 1: 6 QSTAs send three kinds of flow to QAP</figcaption></figure>
Simulation Parameters

* PHY layer: 802.11a rate 36Mbps

* Beacon interval: 500ms

* Audio: On-Off traffic, mean burst time: 400ms, mean idle time: 600ms

* VBR video: The VBR flows have been traced from the VIC video conferencing tool using H.261coding and QCIF format for typical “header and shoulder” video sequences (mean sending rate belongs to a window of 80Kb/s around the mean value of 200Kb/s, packet sizes of these flows belong to a large range of values between 20 and 1024bytes, and mean packet size is between 600bytes and 700bytes)

* CBR video: We increase the HCF load by increasing the packet size of CBR MPEG4 traffic from 600bytes (2.4Mb/s) to 1000bytes (4Mb/s)

<table><thead><tr><td>Application</td><td>Inter-arrival period (ms)</td><td>Packet size (bytes)</td><td>Sending rate (Kb/s)</td><td>Traffic Stream/User Priority</td><td>Maximal SI (ms)</td></tr></thead><tbody><tr><td>Audio</td><td>4.7</td><td>160</td><td>64</td><td>TS6/UP6</td><td>50</td></tr><tr><td>VBR video</td><td>≈26</td><td>≈ 660</td><td>≈ 200</td><td>TS5/UP5</td><td>100</td></tr><tr><td>CBR video</td><td>2</td><td>600-> 1000</td><td>2400->4000</td><td>TS4/UP4</td><td>100</td></tr></tbody></table>
<figure><img src="image_3.png" /></figure>

The mean delay of HCF audio is almost 20ms, and that of EDCF is much smaller
<figure><img src="image_4.png" /></figure>

The mean delay of HCF VBR traffic is very high (about 300ms), and that EDCF remains smaller
<figure><img src="image_5.png" /></figure>

The mean delay of HCF CBR traffic is almost 60ms, and that of EDCF increase according to the rate
Why HCF scheduler is good for periodic CBR (Variable Bit Rate) traffic, but not good for VBR (Variable Bit Rate)?

* Current scheduler computes the number of packets arriving in the TS queue *j* of QSTA *i* during a SI:

$$N_i^j = \left\lceil \frac{\rho_i^j \times SI}{M_i^j} \right\rceil, \text{where } \rho_i^j \text{ is the mean data sending rate}$$

* However, for VBR traffic, the sending rate and packet size are varying, some packets may not be transmitted during the TXOP due to a higher sending rate than that specified in the TSPEC, in this case, latency of these packets can not be controlled by the QAP and some packets maybe dropped
## Our solution

* First we derived a mathematic relationship between maximum delay, SI and queue length:

$$D_i = SI - T_i + \frac{q_i^e M_i}{\rho_i} \text{, where } q_i^e \text{ is the queue length at the end}$$

of TXOP $T_i$, if $q_i^e = 0$, $D_i$ can be almost equal to SI since $T_i \ll SI$

* The QAP computes the estimated queue length at the beginning of the next SI and the ideal queue length which provides $q_i^e = 0$

<figure><img src="image_6.png" /><figcaption>Fig. Queue length evolution for A TS: (0) ideal queue length; (1) $q_i^{est} > q_i^{ideal}$; (2) $q_i^{est} < q_i^{ideal}$</figcaption></figure>
## Our solution

* Based on the difference between ideal queue length and estimated queue length the QAP calculates the additional time (positive or negative) to add to the TXOP

* The node scheduler recalculates the TXOP for each TS

<figure><img src="image_7.png" /></figure>
<figure><img src="image_8.png" /><figcaption>Simulation results</figcaption></figure>
<figure><img src="image_9.png" /><figcaption>Simulation Topology 2</figcaption></figure>
Simulation Parameters

<table><thead><tr><td>Application</td><td>Inter-arrival period (ms)</td><td>Packet size (bytes)</td><td>Sending rate (Kb/s)</td><td>Maximal SI (ms)</td></tr></thead><tbody><tr><td>Audio</td><td>4.7</td><td>160</td><td>64</td><td>50</td></tr><tr><td>VBR video</td><td>≈26</td><td>≈ 660</td><td>≈ 200</td><td>100</td></tr><tr><td>CBR video</td><td>2</td><td>800</td><td>3200</td><td>100</td></tr></tbody></table>
<figure><img src="image_10.png" /><figcaption>Simulation results</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>Number of lost packets</figcaption></figure>

<table><thead><tr><th></th><th>Audio</th><th>VBR</th><th>CBR</th></tr></thead><tbody><tr><th>FHCF</th><td>0</td><td>0</td><td>204</td></tr><tr><th>HCF</th><td>0</td><td>513</td><td>204</td></tr><tr><th>EDCF</th><td>1</td><td>3</td><td>8443</td></tr></tbody></table>

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>
<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /></figure>
Conclusion

* HCF simple scheduler is good for periodic CBR (Constant Bit Rate) traffic, but not good for VBR (Variable Bit Rate) traffic (such as Poisson, bursty traffic)

* We proposed a fair scheduler which uses queue length estimations to tune its time allocations to stations

* Simulation results show that fair scheduler provides good fairness while supporting bandwidth and delay requirements for a large of network loads