Binary decision tree-based arbitrator for packetized communications

Abstract

A binary decision tree-based arbitration scheme executable by a control processor of a time division multiplex (TDM)-based communication system is operative to select the next packet to be transmitted from a plurality of virtual circuits, any number of which may have one or more packets awaiting transmission over a serialized digital communication link. The transmission priority scheme contains N+1 sets of nodes containing 2−1 nodes. A respective ith set of nodes comprises 2nodes, wherein i is greater than or equal to 1, and less than or equal to N+1. The nodes of a given set are connected to those of an adjacent set by binary-split branches. For each of the 2leaf nodes of the decision tree, information is stored representative of the transmission priority of a packet awaiting transmission from its associated communication port. In addition, associated with each node branching to respective pairs of downstream nodes (toward the virtual circuit ports) is a 'pointer' code that points to whichever one of its two branched nodes is associated with a higher packet transmission priority. As one traverses the decision tree along sequentially split branch paths from the highest priority leaf node toward the root node, the pointer code of the next immediately adjacent upstream node will always point to the node-branch path leading to the highest priority leaf node. Thus, the root node will point to the leaf node having the highest transmission priority.