Chapter 41
HPFQ: Hierarchical Network Link Sharing: liboskit_hpfq.a

41.1 Introduction

This short section outlines the Hierarchical Packet Fair Queuing (H-PFQ) network link-sharing implementation in the OSKit. The actual H-PFQ algorithm implemented is called H-WF2Q and is described in the SIGCOMM96 paper by Bennet and Zhang. A working understanding of this paper would be useful in understanding the use of this library.

Be aware that this is a first-cut implementation and is not thoroughly tested nor tuned.

This library allows the user to hierarchically schedule outgoing traffic from different sessions through a single link. Each session is guaranteed a percentage of its parent’s bandwidth, relative to its siblings. This is done by creating a scheduling tree where interior nodes correspond to one-level PFQ schedulers, and leaf nodes corresond to oskit_netio objects for the sessions they represent (see Section 7.5). The root node corresponds to the physical link being shared. The definition of session is up to the user, who controls what is sent to the leaf node oskit_netio’s. Typical session types are real-time traffic, traffic from different organizations, or protocol types. Note, however, that this more general issue of packet classification is not part of this library.

Currently, only one link can be managed at a time, because of the oskit_pfq_root global variable. This will be fixed in a future version.

41.2 Configuration

The H-PFQ library depends on certain modifications to the OSKit Linux device driver set (Section 43) that are enabled only when the OSKit is configured with the --enable-hpfq configure option. This configure option enables H-PFQ-specific code in the Linux driver set.

This library will not work correctly with an improperly configured Linux driver set. Similarly, a Linux driver set configured with --enable-hpfq will only work correctly for non-H-PFQ applications if oskit_pfq_root is NULL.

41.3 Usage

The basic procedure of using this library is to first create a scheduling hierarchy according to the user’s needs, and then to retrieve the oskit_netio’s from the leaf nodes for use by the various sessions. The sessions can then send on these oskit_netio’s and the data will flow to the root according to the policies and allocations in place.

There are no restrictions on the format of the data sent to the leaf oskit_netio’s, but it must be what the oskit_netio corresponding to the root expects. In the common case of oskit_netio’s created by the Linux driver library, this data will simply be Ethernet frames.

The creation of the hierarchy is done by first creating a root node and setting the global variables oskit_pfq_root and oskit_pfq_reset_path appropriately (see Section 41.4). Then various intermediate and/or leaf nodes are created and attached to the root with appropriate share values. This process is then repeated as needed for the children of any intermediate nodes.

In this library, share values are floating point numbers that represent a percentage of the parent’s bandwidth allocated to the child. For example, a child with share value 0.45 is guaranteed 45% of the parent’s bandwidth when the child has data to send, assuming the parent has not over-subscribed its bandwidth.

On a given level of the hierarchy, only the relative differences between share values is important, however for simplicity it is recommended that share values on a given level add up to 1.

A more subtle implication of this relative-differences fact, is that parents can over-subscribe their bandwidth to their children. More specifically, there is no guarantee that a session with a share value of, say 50% will actually receive that amount of the parent’s bandwidth. To see this, consider the case of an intermediate node with two children, each allocated 50% of the bandwidth. Another child may be added with a share value of 50%, but it will in reality only receive 33%. This is more generally termed a problem of admission control, and is not currently dealt with in this library.

41.4 API reference

The following sections describe the functions exported by the H-PFQ library in detail. All of these functions, as well as the types necessary to use them, are declared in the header file <oskit/hpfq.h>.

This API reference is split into two parts. The first part describes the external requirements for the library and the actual functions exported, which are basically constructors for pfq_sched and pfq_leaf objects. The second part describes the pfq_sched and pfq_leaf COM interfaces.

41.5 External Requirements and Constructors

This section describes the external requirements of the library and the actual functions exported, which consist of “constructor” functions to create pfq_sched and pfq_leaf COM objects.

41.5.1 oskit_pfq_root: the root node scheduler

SYNOPSIS

#include <oskit/hpfq.h>

extern pfq_sched_t *oskit_pfq_root;

DESCRIPTION

This variable is not directly used by the H-PFQ library but is used to communicate between the Linux driver set and the program using the H-PFQ library.

The client of the H-PFQ library is responsible for setting this variable to point to the root node of its scheduling hierarchy before any sessions attempt to send to their respective leaf oskit_netio objects.

If this variable is set to the NULL value, then the Linux driver library will not call back to the H-PFQ code and thus will behave like a Linux driver set not configured for H-PFQ.

Note that this implies that only one link can be managed at a time. This will be fixed in a future version.

41.5.2 oskit_pfq_reset_path: pointer to the reset_path function

SYNOPSIS

#include <oskit/hpfq.h>

extern void (*oskit_pfq_reset_path)(pfq_sched_t *);

DESCRIPTION

This variable is not directly used by the H-PFQ library but is used to communicate between the Linux driver set and the program using the H-PFQ library.

The client of the H-PFQ library is responsible for setting this variable to point to the pfq_reset_path function before any sessions attempt to send to their respective leaf oskit_netio objects.

41.5.3 pfq_sff_create_root: create a root node implementing SFF

SYNOPSIS

#include <oskit/hpfq.h>

oskit_error_t pfq_sff_create_root(oskit_netio_t *link, pfq_sched_t **out_sched);

DESCRIPTION

Creates a root PFQ node implementing the Smallest Finish time First (SFF) scheduling policy.

PARAMETERS
link:
The link that the scheduling tree intends to manage.
out_sched:
A pointer to the pfq_sched object representing the root of the hierarchy.

This can be then used with future pfq_sched methods to add children, etc.

RETURNS

Returns 0 on success, or an error code specified in <oskit/error.h>, on error.

41.5.4 pfq_ssf_create_root: create a root node implementing SSF

SYNOPSIS

#include <oskit/hpfq.h>

oskit_error_t pfq_ssf_create_root(oskit_netio_t *link, pfq_sched_t **out_sched);

DESCRIPTION

Creates a root PFQ node implementing the Smallest Start time First (SSF) scheduling policy.

PARAMETERS
link:
The link that the scheduling tree intends to manage.
out_sched:
A pointer to the pfq_sched object representing the root of the hierarchy.

This can be then used with future pfq_sched methods to add children, etc.

RETURNS

Returns 0 on success, or an error code specified in <oskit/error.h>, on error.

41.5.5 pfq_sff_create: create an intermediate node implementing SFF

SYNOPSIS

#include <oskit/hpfq.h>

oskit_error_t pfq_sff_create(pfq_sched_t **out_sched);

DESCRIPTION

Creates an intermediate PFQ node implementing the Smallest Finish time First (SFF) scheduling policy.

PARAMETERS
out_sched:
A pointer to the pfq_sched object representing the the created intermediate node.

This can be then used with future pfq_sched methods to add children, etc.

RETURNS

Returns 0 on success, or an error code specified in <oskit/error.h>, on error.

41.5.6 pfq_ssf_create: create an intermediate node implementing SSF

SYNOPSIS

#include <oskit/hpfq.h>

oskit_error_t pfq_ssf_create(pfq_sched_t **out_sched);

DESCRIPTION

Creates an intermediate PFQ node implementing the Smallest Start time First (SSF) scheduling policy.

PARAMETERS
out_sched:
A pointer to the pfq_sched object representing the the created intermediate node.

This can be then used with future pfq_sched methods to add children, etc.

RETURNS

Returns 0 on success, or an error code specified in <oskit/error.h>, on error.

41.5.7 pfq_leaf_create: create a leaf node

SYNOPSIS

#include <oskit/hpfq.h>

oskit_error_t pfq_leaf_create(pfq_leaf_t **out_leaf);

DESCRIPTION

Create a leaf PFQ node.

The oskit_netio that can be used by the session corresponding to this leaf can be retreived by calling pfq_leaf_get_netio, described elsewhere in this document.

PARAMETERS
out_leaf :
A pointer to the pfq_leaf object representing the the created intermediate node.

This can be then used with future pfq_leaf methods to set the share value, etc.

RETURNS

Returns 0 on success, or an error code specified in <oskit/error.h>, on error.

41.6 pfq_sched: Interface to PFQ Schedulers

This section describes the pfq_sched COM interface to PFQ scheduler objects. Note that the child parameter to these methods is declared as a pfq_sched. However, pfq_leaf inherits from pfq_sched and thus may be used as a child parameter when suitably cast.

The pfq_sched interface inherits from IUnknown and has the following additional methods:

add_child:
Add a child to this node
remove_child:
Remove a child from this node
set_share:
Set the bandwidth share given to this node

41.6.1 pfq_sched_add_child: add a child to a root or intermediate node

SYNOPSIS

#include <oskit/hpfq.h>

oskit_error_t pfq_sched_add_child(pfq_sched_t *sched, pfq_sched_t *child, float share);

DESCRIPTION

This method attaches a child pfq_sched object to a parent and assigns it an initial share of the parent. The share can be later adjusted with the set_share method if needed.

PARAMETERS
sched:
The parent pfq_sched object.
child:
The child being added.
share:
The initial share value of the child. See Section 41.3 for details on share values.
RETURNS

Returns 0 on success, or an error code specified in <oskit/error.h>, on error.

41.6.2 pfq_sched_remove_child: remove a child from a root or intermediate node

SYNOPSIS

#include <oskit/hpfq.h>

oskit_error_t pfq_sched_remove_child(pfq_sched_t *sched, pfq_sched_t *child);

DESCRIPTION

This method removes a child from a parent pfq_sched object.

PARAMETERS
sched:
The parent pfq_sched object losing a child.
child:
The child to be orphaned.
RETURNS

Returns 0 on success, or an error code specified in <oskit/error.h>, on error.

41.6.3 pfq_sched_set_share: allocate a percentage of the parent’s bandwidth

SYNOPSIS

#include <oskit/hpfq.h>

oskit_error_t pfq_sched_set_share(pfq_sched_t *sched, pfq_sched_t *child, float share);

DESCRIPTION

This method adjusts the share value of a pfq_sched object. See Section 41.3 for details on share values.

PARAMETERS
sched:
The parent pfq_sched object.
child:
The child getting their share adjusted.
share:
The new share value of the child.
RETURNS

Returns 0 on success, or an error code specified in <oskit/error.h>, on error.

41.7 pfq_leaf: Interface to PFQ Leaf Nodes

This section describes the pfq_leaf COM interface to PFQ leaf objects.

The pfq_leaf interface inherits from pfq_sched and the following additional method:

get_netio:
Get the oskit_netio corresponding to this leaf

Note that since pfq_leaf inherits from pfq_sched, it may be used in place of a pfq_sched object when suitably cast.

41.7.1 pfq_leaf_add_child: add a child to a root or intermediate node

SYNOPSIS

#include <oskit/hpfq.h>

oskit_error_t pfq_leaf_add_child(pfq_leaf_t *sched, pfq_sched_t *child, float share);

DESCRIPTION

This does not make sense for leaf nodes and is thus not implemented.

RETURNS

Returns 0 on success, or an error code specified in <oskit/error.h>, on error.

41.7.2 pfq_leaf_remove_child: remove a child from a root or intermediate node

SYNOPSIS

#include <oskit/hpfq.h>

oskit_error_t pfq_leaf_remove_child(pfq_leaf_t *sched, pfq_sched_t *child);

DESCRIPTION

This does not make sense for leaf nodes and is thus not implemented.

41.7.3 pfq_leaf_set_share: allocate a percentage of the parent’s bandwidth

SYNOPSIS

#include <oskit/hpfq.h>

oskit_error_t pfq_leaf_set_share(pfq_leaf_t *sched, pfq_sched_t *child, float share);

DESCRIPTION

This does not make sense for leaf nodes and is thus not implemented.

41.7.4 pfq_leaf_get_netio: get the oskit_netio corresonding to this leaf

SYNOPSIS

#include <oskit/hpfq.h>

oskit_error_t pfq_leaf_get_netio(pfq_leaf_t *leaf, oskit_netio_t **out_netio);

DESCRIPTION

Retrieves a pointer to an oskit_netio that can be used to send data by the session corresponding to this leaf.

PARAMETERS
leaf :
The leaf who’s oskit_netio is of interest.
out_netio:
A pointer to the oskit_netio object that can be used to send data by the session corresponding to this leaf.
RETURNS

Returns 0 on success, or an error code specified in <oskit/error.h>, on error.