Patent ID: 7433953

Claim:
A method for allocating routing resources in a data communications device, the data communications device including a plurality of egress ports having respective line data rates, the ports including (1) an unchannelized port carrying data traffic of a first logical interface having a data rate equal to the line data rate of the unchannelized port, and (2) a channelized port carrying data traffic of a plurality of second logical interfaces having respective data rates each substantially less than the line data rate of the channelized port, the routing resources including a shared bus over which the data traffic of the first logical interface and the second logical interfaces flows to respective first-in-first-out (FIFO) buffers for the respective logical interfaces, the method comprising: classifying the data traffic of the first logical interface and the plurality of second logical interfaces into respective first and second arbitration groups based on respective service levels, the service level of each arbitration group corresponding to an expected throughput of the data traffic of the individual logical interfaces of the arbitration group; computing, for each of the arbitration groups, a respective demand for the routing resources based on the expected aggregate throughput of the data traffic of each of the arbitration groups; and allocating the routing resources in a hierarchical manner in which the routing resources are first allocated among the arbitration groups in proportion to the respective demand of each of the arbitration groups and then allocated within each arbitration group among the logical interfaces of the arbitration group, wherein classifying the arbitration groups includes defining, based on a hierarchical data structure operable to enqueue and dequeue requests for router resources, a speed group layer including the arbitration groups, the service level indicative of a transmission speed corresponding to the arbitration group, and wherein the speed group layer is an intermediate layer of the hierarchical data structure, the intermediate layer being disposed between a root layer and a leaf layer, the root layer including lists of dequeue entries each pointing to a calendar of the speed group layer, the speed group layer including lists of dequeue entries each pointing to a calendar of the leaf layer, and the leaf layer including lists of dequeue entries each identifying a corresponding message received by the data communications device and a corresponding one of the logical interfaces via which the message is to be transmitted.