Fair access of multi-priority traffic to distributed-queue dual-bus networks

Claim 1

A method for allocating transmission capacity in a network having a data bus that passes through network nodes 1 to N of said network in ascending order and a request bus that passes from network nodes N to 1 in descending order, where transmission capacity on said data bus is divided into slots and where each slot on said data bus contains a data field and a header field that includes a busy subfield and a request subfield, and where each node j, where j is an integer between 1 and N, accepts data with an associated priority level from a user port of said node, for transmission to a node K on said network where j<k≦N, and controls the injection of said data into said data bus in accordance with a procedure comprising the steps of: each node determining an effective spare capacity available to itself on said data bus based on the presence of request bits in the request subfield of slots on the request bus, and the busy bits in the request subfield of slots on the data bus; and each node throttling its rate of injecting of data into said data bus to a fraction of the effective spare capacity, where said fraction is related to the priority of the data presented to the node.

Claim 2

A method for allocating transmission capacity in a network having a data bus that passes through network nodes 1 to N of said network in ascending order and a request bus that passes from network nodes N to 1 in descending order, where transmission capacity on said data bus is divided into slots and where each slot on said data bus contains a data field and a header field that includes a busy subfield and a request subfield, and where each node j, where j is an integer between 1 and N, accepts data with an associated priority level from a user port of said node, for transmission to a node K on said network where j<k≦N, and controls the injection of said data into said data bus in accordance with a procedure comprising the steps of: each node determining an effective spare capacity available to itself on said data bus based on the presence of request bits in the request subfield of slots on the request bus, and the busy bits in the request subfield of slots on the data bus; and each node throttling its rate of injecting of data into said data bus to a fraction of the effective spare capacity, where said fraction is related to the priority of the data presented to the node.

Claim 14

A method for allocating transmission capacity in a slotted network having a data bus that passes through network nodes 1 to N of said network in ascending order and a request bus that passes from network nodes N to 1 in descending order, where transmission capacity on said data bus is divided into slots and where each slot on said data bus contains a data field and a header field that includes a busy subfield and a request subfield, and where each node j, where j is an integer between 1 and N, accepts data with an associated priority level from a user port for transmission to a node k on said network where j<k≦N, which data comprises packets of information, and controls the injection of said data into said data bus in accordance with a procedure comprising the steps of: accumulating requests from nodes m, where m>j, in a queue, when there is no local request from node j and data is available at node j, accumulating a local request in said queue, and returning to said step of accumulating request, in parallel with said accumulating of request, when the top request in said queue is a request from a node m and a non-busy slot appears at said node j on said data bus, satisfying that top request by passing said slot to succeeding nodes without alteration and removing the satisfied request from the queue, in parallel with said accumulating of requests, when the top request in said queue is said local request from node j and a non-busy slot appears at said data bus entering said node j, when a bandwidth balancing indication is set, satisfying said local request by populating said slot with a data packet, and when a bandwidth balancing indication is unset, passing said slot to succeeding nodes without alteration and setting said bandwidth balancing indication; wherein said bandwidth balancing indication is unset in accordance with the priority level of said data.

Claim 15

A method for allocating transmission capacity in a slotted network having a data bus that passes through network nodes 1 to N of said network in ascending order and a request bus that passes from network nodes N to 1 in descending order, where transmission capacity on said data bus is divided into slots and where each slot on said data bus contains a data field and a header field that includes a busy subfield and a request subfield, and where each node j, where j is an integer between 1 and N, accepts data with an associated priority level from a user port for transmission to a node k on said network where j<k≦N, which data comprises packets of information, and controls the injection of said data into said data bus in accordance with a procedure comprising the steps of: accumulating requests from nodes m, where m>j, in a queue, when there is no local request from node j and data is available at node j, accumulating a local request in said queue, and returning to said step of accumulating request, in parallel with said accumulating of request, when the top request in said queue is a request from a node m and a non-busy slot appears at said node j on said data bus, satisfying that top request by passing said slot to succeeding nodes without alteration and removing the satisfied request from the queue, in parallel with said accumulating of requests, when the top request in said queue is said local request from node j and a non-busy slot appears at said data bus entering said node j, when a bandwidth balancing indication is set, satisfying said local request by populating said slot with a data packet, and when a bandwidth balancing indication is unset, passing said slot to succeeding nodes without alteration and setting said bandwidth balancing indication; wherein said bandwidth balancing indication is unset in accordance with the priority level of said data.

Claim 23

A method for allocating transmission capacity in a slotted network having a data bus that passes through network nodes 1 to N of said network in ascending order and a request bus that passes from network nodes N to 1 in descending order, where transmission capacity on said data bus is divided into slots and where each slot on said data bus contains a data field and a header field that includes a busy subfield and a request subfield, and where each node j, where j is an integer between 1 and N, accepts data with an associated priority level from a user port for transmission to a node k on said network where j<k≦N, which data comprises packets of information, and controls the injection of said data into said data bus in accordance with a procedure comprising the steps of: determining the number of unsatisfied requests received from the request bus; satisfying the unsatisfied requests by allowing empty slots to pass unpopulated; and populating less than all of the remaining empty slots with said data by passing an empty slot unpopulated for every selected number of empty slots that are populated, where the selected number is related to said associated priority level of said data.

Claim 24

A method for allocating transmission capacity in a slotted network having a data bus that passes through network nodes 1 to N of said network in ascending order and a request bus that passes from network nodes N to 1 in descending order, where transmission capacity on said data bus is divided into slots and where each slot on said data bus contains a data field and a header field that includes a busy subfield and a request subfield, and where each node j, where j is an integer between 1 and N, accepts data with an associated priority level from a user port for transmission to a node k on said network where j<k≦N, which data comprises packets of information, and controls the injection of said data into said data bus in accordance with a procedure comprising the steps of: determining the number of unsatisfied requests received from the request bus; satisfying the unsatisfied requests by allowing empty slots to pass unpopulated; and populating less than all of the remaining empty slots with said data by passing an empty slot unpopulated for every selected number of empty slots that are populated, where the selected number is related to said associated priority level of said data.

Claim 26

A method for allocating transmission capacity in a network having a data bus that passes through network nodes 1 to N of said network in ascending order and a request bus that passes from network nodes N to 1 in descending order, where transmission capacity on said data bus is divided into slots and where each slot on said data bus contains a data field and a header field that includes a busy subfield and a request subfield, and where each node j, where j is an integer between 1 and N, receives a parcel with an associated priority level from a user port of said node, for transmission to a node k on said network downstream from node j<k≦M, where said parcel is composed of data packets that are small enough to fit within the data fields of said slots, and where said node j controls the injection of said data packets into said data bus in accordance with a procedure comprising the steps of: satisfying accumulated requests, injecting a data packet when an empty slot appears on the data bus and the accumulated requests are satisfied, for every given number of injected data packets, allowing an empty slot to pass unpopulated, and returning to the step of satisfying accumulated requests; where a measure of said accumulated requests is the number, Q, which equals the number of request bits received by node j on said request bus, from downstream nodes j+1 to N, minus the number of empty slots passed unpopulated through node j on said data bus to node j+1, in response to said request bits, from the most recent execution of said step of injecting a data packet; said step of satisfying accumulated requests allows Q empty slots to pass unpopulated; and said given number is related to said priority level associated with said parcel received from said user port.

Claim 27

A method for allocating transmission capacity in a network having a data bus that passes through network nodes 1 to N of said network in ascending order and a request bus that passes from network nodes N to 1 in descending order, where transmission capacity on said data bus is divided into slots and where each slot on said data bus contains a data field and a header field that includes a busy subfield and a request subfield, and where each node j, where j is an integer between 1 and N, receives a parcel with an associated priority level from a user port of said node, for transmission to a node k on said network downstream from node j<k≦M, where said parcel is composed of data packets that are small enough to fit within the data fields of said slots, and where said node j controls the injection of said data packets into said data bus in accordance with a procedure comprising the steps of: satisfying accumulated requests, injecting a data packet when an empty slot appears on the data bus and the accumulated requests are satisfied, for every given number of injected data packets, allowing an empty slot to pass unpopulated, and returning to the step of satisfying accumulated requests; where a measure of said accumulated requests is the number, Q, which equals the number of request bits received by node j on said request bus, from downstream nodes j+1 to N, minus the number of empty slots passed unpopulated through node j on said data bus to node j+1, in response to said request bits, from the most recent execution of said step of injecting a data packet; said step of satisfying accumulated requests allows Q empty slots to pass unpopulated; and said given number is related to said priority level associated with said parcel received from said user port.