Patent ID: 7007123

Claim:
A system for arbitrating among N competing entities, each entity operating to generate a service request, said system comprising: a tree structure having (N−1) arbiter nodes organized into K levels, where N=2 K and said levels are designated Level- 1 through Level-K; each Level- 1 arbiter nods operating to select between two competing service requests, and at least one arbiter node at a higher level, designated as a Level-i node, is operable to select between two competing outputs generated by two lower level arbiter nodes (designated as Level-(i- 1 ) nodes) coupled thereto, said competing service requests and said competing outputs being collectively referred to as competing links; each arbiter node having a direction indicator associated therewith, said direction indicator for indicating a particular link that said each arbiter node will pick out of a pair of competing links; and a logic structure for determining a probability value associated with said direction indicator based on a set of predetermined factors relating to said pair of competing links, wherein said probability value associated with said direction indicator is determined based on a composite weighted function having at least a queue size factor relating to each of said pair of competing links; and wherein, for each particular link of said pair of competing links coupled to said Level-i node, said queue size factor is derived based on an averaging function of queue size factors corresponding to a sub-tree that supports said each particular link.