An Efficient Implementation of a Hierarchical Weighted Fair Queue Packet Scheduler

The technical developments in computer networks in recent years have spawned the possibility of merging di erent services into a single Integrated Service Packet Network (ISPN). The types of service quality required by each of the individual services in an ISPN often di er greatly. Thus, the packet scheduling algorithms used in such networks must be exible enough to allocate the available link shares according to the service quality requirements of the di erent services. In this thesis we propose an ecient implementation of a link sharing algorithm for an Integrated Services Packet Switch (ISPS). The sharing algorithm guarantees to each customer a percentage of the link share no less than the portion of the bandwidth he owns. A customer can split its link share among di erent services whose link shares may in turn be split among child-services. The link sharing is hierarchical; each service gets its link share from that of its parent service. Because of the complex nature of the link sharing the algorithm provides, the run time of its implementation can b e large. However, in order to bene t from the fast links of networks like ATM, it is desirable to have reasonably short packet processing delays. The implementation presented here maps the hierarchical sharing into an equivalent single level sharing which resulted in a speed up of the packet processing executor by a factor of 10.

The algorithm accepts service requests according to the present load of the network and the service requirements it has promised to the already accepted services. See reference [2] for more details on the admission control algorithm. The nature of the promise made to a service depends on the type of the service. There are three type of services: Guaranteed, Predicted and Shared. In this paper we will focus our attention on the shared services. As the name suggests, the shared services share the link bandwidth according 9to the arbitrary portion of the bandwidth that each one owns. As in every sharing environment, fairness needs to b e addressed here. The sharing is considered fair if the amount of bandwidth owned by any service is available to it regardless of the behavior of other services in the network. To insure fairness, packets are scheduled using a Weighted Fair Queuing (WFQ) scheme, where the weights are the link shares. In the next paragraphs we will justify the choice of WFQ for the queueing discipline and then present its basic mechanism. Queueing algorithms can be thought of as mechanisms that allocate three quantities: bandwidth (which packets get transmitted), promptness (when will these packets leave) and bu er space (which packets get dropped) ([5]). The most currently used queueing discipline is rst-in- rst-out (FIFO). In FIFO queueing, the rate at which a source sends packets relative to the other sources in the network essentially determines the amounts of the three quantities allocated to it. Since packets are being serviced in their order of arrival, the faster a source generate packets the more likely its packets will arrive rst at a gateway, thus its packets will be serviced more often. This implies that the service quality that a session gets from the network is partly dictated by the behavior of its source. Thus, FIFO is not adequate for fairness in the sense that it does not guarantee service quality to a particular service; a more e ective queueing mechanism is needed. Following a similar line of reasoning, Nagle [10,11] proposed a fair queueing (FQ) algorithm in which separate queues were maintained for packets from each source. The queues are serviced in round-robin manner. His algorithm was e ective in providing fairness in terms of the numb er of packets serviced for each session. If a source attempts to get over by sending packets at a faster rate, it will simply over ow its queue and hence su er packet drop but won’t get more packets sent than other sources in the network. However, because packets can be of varying length, round-robin does not guarantee fair share of the bandwidth. In FQ, sessions with long packets will be allocated a greater portion of the bandwidth. Furthermore, even with xed packet 10length, round-robin is not exible since it attempts to treat each session or packet equally. In integrated services networks, since the di erent services have di erent requirements, one needs a mechanism that can treat the di erent services in di erent ways. Thus, in integrated networks a more attractive queueing discipline is needed. Weighted Fair Queue (WFQ), presented by Parekh and Gallager in [8], which also works for non uniformly weighted shares, provides fairness in the allocation of the bandwidth. Here a weight can b e thought as the percentage of a link bandwidth allocated to a given service.

Free download research paper