US 2002/0159397 A1 · 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 2N+1−1 nodes. A respective ith set of nodes comprises 2i−1 nodes, 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 2N leaf 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.

Claims6

Dependent claims

For use with a digital communication system in which a terminal serving a plurality of circuits, from which requests for transmission of one or more digital information packets awaiting transmission over a serialized data path may be supplied, a method of controllably interfacing packets awaiting transmission from ports associated with said plurality of circuits with said serialized data path, said method comprising the steps of:

(a) providing a binary decision tree-based transmission assignment network having a root node associated with said serialized data path, a plurality of leaf nodes associated with respective ports of said plurality of circuits, and intermediate branch nodes that define a binary decision tree-structure between said root node and said plurality of leaf nodes;
(b) storing for each node of said network, other than said leaf nodes, a pointer to whichever of its two adjacent downstream nodes effectively points to a leaf node whose associated circuit currently has highest transmission priority, thereby providing said root node with a pointer to the circuit currently having highest transmission priority;
and
(c) coupling, to said serialized data path, a packet from the circuit whose leaf node is pointed to by said root node.

1 more element

For use with a digital communication system in which a terminal serving a plurality of circuits, from which requests for transmission over a serialized data path may be supplied of one or more digital information packets, a method of controllably interfacing packets awaiting transmission from communication ports associated with said plurality of circuits with said serialized data path, said method comprising the steps of:

(a) providing a binary decision tree-based transmission assignment network having N+1 sets of nodes containing 2N+1−1 nodes that define a binary decision tree-structure between a first port adapted to be coupled to said serialized data path, and 2N communication ports, that are adapted to be coupled to said plurality of communication circuits, wherein 2N is equal to or greater than the number of said communication circuits, said N+1 sets of nodes including a first, root node associated with said first port and 2N leaf nodes, respectively associated with said 2N communication ports, a respective ith set of nodes comprising 2i−1 nodes, wherein i is greater than or equal to 1, and less than or equal to N+1;
(b) storing, for each of said 2N leaf nodes of said network, first information representative of priority of transmission of a packet that may be awaiting transmission from an associated communication port over said serialized data path;
(c) storing, for a respective node of an ith set of nodes, a pointer to that node of an (i+1)th set of nodes that is associated with a leaf node having a relatively higher transmission priority;
and
(d) coupling, to said serialized data path, a packet from the circuit whose leaf node is pointed to by said root node.

2 more elements

A communications controller for a digital communication network having a serialized digital communication link, through which a network coupled to a first end of the link may transmit and receive digital telecommunication packets with respect to a plurality of communication ports associated with customer premises equipments served by a remote termination site at an opposite end of the link, said communications controller being installable in said remote termination site and being operative to execute a packet transmission control mechanism for handling packet transmission requests from virtual circuits coupled with said plurality of communication ports and associated with said customer equipments, and thereby selectively granting transmission to a packet over said serialized digital communication link by executing the following steps:

(a) providing a binary decision tree-based transmission assignment network having N+1 sets of nodes containing 2N+1−1 nodes that define a binary decision tree-structure between a first node associated with a port adapted to be coupled to said serialized digital communication link, and 2N leaf nodes respective ones of which are associated with respective ones of said communication ports, wherein 2N is equal to or greater than the number of communication ports, said N+1 sets of nodes including a first, root node associated with said first port, a respective ith set of nodes comprising 2i−1 nodes, wherein i is greater than or equal to 1, and less than or equal to N+1;
(b) storing, for each of said 2N leaf nodes of said network, first information representative of priority of transmission of a packet that may be awaiting transmission from an associated communication port over said serialized digital communication link;
(c) storing, for a respective node of an ith set of nodes, a pointer to that node of an (i+1)th set of nodes that is associated with a leaf node having a relatively higher transmission priority;
and
(d) coupling, to said serialized digital communication link, a packet from the circuit whose leaf node is pointed to by said root node.

2 more elements

Dependencies are inferred from the claim text.

Binary decision tree-based arbitrator for packetized communications

Life of this patent

Binary decision tree-based arbitrator for packetized communications

Life of this patent

Abstract

Claims6