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.
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.
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.
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.
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.
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.
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.
#include <oskit/hpfq.h>
oskit_error_t pfq_sff_create_root(oskit_netio_t *link, pfq_sched_t **out_sched);
Creates a root PFQ node implementing the Smallest Finish time First (SFF) scheduling policy.
This can be then used with future pfq_sched methods to add children, etc.
Returns 0 on success, or an error code specified in <oskit/error.h>, on error.
#include <oskit/hpfq.h>
oskit_error_t pfq_ssf_create_root(oskit_netio_t *link, pfq_sched_t **out_sched);
Creates a root PFQ node implementing the Smallest Start time First (SSF) scheduling policy.
This can be then used with future pfq_sched methods to add children, etc.
Returns 0 on success, or an error code specified in <oskit/error.h>, on error.
Creates an intermediate PFQ node implementing the Smallest Finish time First (SFF) scheduling policy.
This can be then used with future pfq_sched methods to add children, etc.
Returns 0 on success, or an error code specified in <oskit/error.h>, on error.
Creates an intermediate PFQ node implementing the Smallest Start time First (SSF) scheduling policy.
This can be then used with future pfq_sched methods to add children, etc.
Returns 0 on success, or an error code specified in <oskit/error.h>, on error.
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.
This can be then used with future pfq_leaf methods to set the share value, etc.
Returns 0 on success, or an error code specified in <oskit/error.h>, on error.
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:
#include <oskit/hpfq.h>
oskit_error_t pfq_sched_add_child(pfq_sched_t *sched, pfq_sched_t *child, float share);
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.
Returns 0 on success, or an error code specified in <oskit/error.h>, on error.
#include <oskit/hpfq.h>
oskit_error_t pfq_sched_remove_child(pfq_sched_t *sched, pfq_sched_t *child);
This method removes a child from a parent pfq_sched object.
Returns 0 on success, or an error code specified in <oskit/error.h>, on error.
#include <oskit/hpfq.h>
oskit_error_t pfq_sched_set_share(pfq_sched_t *sched, pfq_sched_t *child, float share);
This method adjusts the share value of a pfq_sched object. See Section 41.3 for details on share values.
Returns 0 on success, or an error code specified in <oskit/error.h>, on error.
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:
Note that since pfq_leaf inherits from pfq_sched, it may be used in place of a pfq_sched object when suitably cast.
#include <oskit/hpfq.h>
oskit_error_t pfq_leaf_add_child(pfq_leaf_t *sched, pfq_sched_t *child, float share);
This does not make sense for leaf nodes and is thus not implemented.
Returns 0 on success, or an error code specified in <oskit/error.h>, on error.
This does not make sense for leaf nodes and is thus not implemented.
#include <oskit/hpfq.h>
oskit_error_t pfq_leaf_set_share(pfq_leaf_t *sched, pfq_sched_t *child, float share);
This does not make sense for leaf nodes and is thus not implemented.
#include <oskit/hpfq.h>
oskit_error_t pfq_leaf_get_netio(pfq_leaf_t *leaf, oskit_netio_t **out_netio);
Retrieves a pointer to an oskit_netio that can be used to send data by the session corresponding to this leaf.
Returns 0 on success, or an error code specified in <oskit/error.h>, on error.