Method and apparatus for pipeline sorting of ordered streams of data items
US6757284B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Mar 7, 2000 |
| Grant date | Jun 29, 2004 |
| Priority date | — |
| Expiry date | Mar 7, 2020 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L49/3027
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
According to the invention, resequencers are used to sort one or more sets of a plurality of streams of ordered data items. In certain implementations, these data items represent packets within a packet switch. Additionally, in some packet switch implementations, jitter buffers are distributed within a packet switch (e.g., at each switching stage) to reduce packet burstiness within the packet switch. Typically, a pipeline of sorting stages is used to order the one or more sets of streams of data items. Data items from the first set of streams is loaded into input registers or queues of the first stage. These data items are partitioned into groups which are each evaluated by a comparitor with the winning entry (e.g., a smallest or largest value when being sorted in ordered value) placed in a second stage input queue. Each comparitor of the second stage evaluates the data items at its inputs and forwards its respective winning entry. In the case of more than one comparitor in the second stage, then the winning entries are passed to a third stage, and so on. The sorting at each stage continues in parallel to efficiently produce a stream of ordered data items from the first set of stre…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.