Methods and apparatus for shaping queued packets using a two-dimensional RAM-based search engine
US6370144B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 4, 1998 |
| Grant date | Apr 9, 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 two (2) dimensional shaper uses a hierarchical searching technique to find the first memory location of the 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 needed to address any bit at a level l may be expressed as: In this way, the search time depends on the number L of levels. Such a scheduler can schedule large numbers of flows to be placed on a high-speed data link (that is, with a small time slot).
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.