Binary tree arbitration system and method using embedded logic structure for controlling flag direction in multi-level arbiter node
US7007123B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 28, 2002 |
| Grant date | Feb 28, 2006 |
| Priority date | — |
| Expiry date | Dec 16, 2023 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L47/623
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A binary-tree-based arbitration system and methodology with attributes that approximate a Generalized Processor Sharing (GPS) scheme for rendering fairer service grants in an environment having a plurality of competing entities. Arbitration based on probabilistic control of arbiter nodes' behavior is set forth for alleviating the inherent unfairness of a binary tree arbiter (BTA). In one implementation, BTA flag direction probabilities are computed based on composite weighted functions that assign relative weights or priorities to such factors as queue sizes, queue ages, and service class parameters. Within this general framework, techniques for desynchronizing a binary tree's root node, shuffling techniques for mapping incoming service requests to the BTA's inputs, and multi-level embedded trees are described.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.