Methods and apparatus for fairly scheduling queued packets using a ram-based search engine
US6389031B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 4, 1998 |
| Grant date | May 14, 2002 |
| Priority date | — |
| Expiry date | Nov 4, 2018 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L2012/5683
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A hierarchical searching technique is used to find the first memory location of a calendar queue with a validity bit of “1” (that is, the lowest time stamp). The bit string at any level l (l≠0) can be stored in a RAM of size glMl−1. The string at the highest level in the hierarchy (l=0) can be stored in an M0 bit register. The number of address bits need to address any bit at a level l may be expressed as: Equation (11) illustrates a method of the present invention for addressing in a hierarchical search. That is, m0 most significant bits of the time stamp address should be used at level 0. Then, at level l, the complete address used at upper level (l−1) will be used to locate the proper gl bit word in its glMl−1 memory. Another log2gl bits following the previous ml−1 bits is extracted from the time stamp address and used to locate the proper bit in the gl bit word that has just been identified. In this way, the search time depends on the number L of levels. Thus, a scheduler based on the present invention can schedule large numbers of flows to be placed on a high speed data link (i.e., with a small time slot). A two (2) dimensional shaper …
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.