Binary tree arbitration system and method using embedded...

Details Binary tree arbitration system and method using embedded... Binary tree arbitration system and method using embedded...

2006-02-28

2006-02-28

Myers, Paul R. (Department: 2111)

Electrical computers and digital data processing systems: input/

Access arbitrating

Hierarchical or multilevel arbitrating

C710S111000, C710S113000, C710S120000

Reexamination Certificate

active

07007123

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.

REFERENCES:
patent: 5301333 (1994-04-01), Lee
patent: 5519837 (1996-05-01), Tran
patent: 5870629 (1999-02-01), Borden et al.
patent: 6032218 (2000-02-01), Lewin et al.
patent: 6160812 (2000-12-01), Bauman et al.
patent: 6420901 (2002-07-01), Liu et al.
patent: 6516369 (2003-02-01), Bredin
patent: 6757246 (2004-06-01), Alasti et al.
patent: 1137316 (2001-09-01), None
Journal of High Speed Networks 8; “A terabit IP switch router using optoelectronic technology”; H. Jonathan Chao, Xiaolei Guo, Cheuk-Hung Lam and Ti-Shiang Wang; pp. 35-57; 1999.
Scalable High-Speed Switches/Routers with QoS Support; “Saturn: A Terabit Packet Switch Using Dual Round-Robin”; Jonathan Chao, Polytechnic University; pp. 78-84; Dec. 2000.
“A Binary-Tree Architecture for Scheduling Real-Time Systems with Hard and Soft Tasks”; A. Garcia, S. Saez, J. Vila and A. Craspo; Integrated Circuits and Systems Design; pp. 78-81; 1999.
“Scalable Hardware Priority Queue Architectures for High-Speed Packet Switches”; Sung-Whan Moon, J. Rexford and K.G. Shin; Computers, IEEE Transaction on vol. 49, Issue 11; pp. 1215-1227; Nov. 2002.
“A Fast Arbitration Scheme for Terabit Packet Switches”; H.J. Chao, C.H. Lam and X. Guo; Global Telecommunications Conference, GLOBECOM 99, vol. 2; pp. 1236-1243; 1999.
“Quality of Service in the Internet: Fact, Fiction, or Compromise?”; Paul Ferguson and Geoff Huston; pp. 1-20; Jul. 1998.

Affiliated with

Also associated with

Rating

Binary tree arbitration system and method using embedded... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Binary tree arbitration system and method using embedded..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Binary tree arbitration system and method using embedded... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3694637