Distributed quality-of-service system

Abstract

A distributed quality-of-service system makes use of a distributed architecture to achieve very high throughput and availability in which a number of separate processors are loosely coupled in a scalable communication architecture. The computational load required to implement an approach that is similar to that of Floyd and Jacobson is distributed among the processors without requiring the processors to be tightly coupled. A high data rate flow is split so that each processor receives a portion of the traffic passing through the system. The processors implement separate class-based queuing and link fairness algorithms. The output flows of each of the processors are combined to form the overall output flow. The processors exchange data from time to time in order to achieve an approximate link fairness on the overall output flow without requiring the separate algorithms implemented on each of the processors to be tightly coupled.

1 . A computer-based method for scheduling network packet traffic for transmission according to a class-based queuing hierarchy, comprising: 
 creating a matrix having a fixed size, one dimension of the matrix representing a plurality of class priorities, another dimension of the matrix representing a plurality of levels corresponding to levels of the hierarchy, and cells in the matrix including collections of references to nodes in the hierarchy;    accepting a collection of class-based queues containing a plurality of packets awaiting transmission;    scheduling for transmission a next packet among the plurality of packets, the scheduling including searching cells of the matrix for a reference to a next class in the hierarchy, the next class being associated with the next packet, such that the worst-case time of the searching is bounded by a finite time dependent on the fixed size of the matrix.