Data packet router

Claim 2

In a router for connecting, to a plurality of data destinations, a plurality of data sources bidding for connection to identified ones of said destinations, respective sets of connections being made during each of a succession of intervals using a matrix of crosspoint switch elements; a process for allocating the switch elements to possible connections which comprises: providing, in correspondence with said switch element matrix, a data array having a number of data elements corresponding to the number of said switch elements; generating for each interval, first and second pseudo-random shuffle patterns, the respective shuffle patterns generated for each interval being the current shuffle patterns for the respective interval; assigning, in accordance with said first current pseudo-random shuffle pattern, a respective source to each of said data elements; assigning, in accordance with said second current pseudo-random shuffle pattern, a respective destination to each of said data elements; performing an incremental testing across the array, of the sources and destinations assigned to each data element to locate matches of bidding sources and destinations not previously allocated and successively allocating each match to the switch element corresponding to the respective data element; and after testing the complete array, operating the switch elements during a subsequent interval in accordance with the allocations made.

Claim 3

A process as set forth in claim 1 wherein, for each source, a respective bid queue is maintained for each destination.

Claim 4

A process as set forth in claim 2 wherein a data cell can be transmitted during each interval and wherein said bid queues are at least three cells long.

Claim 5

A process as set forth in claim 2 wherein each destination maintains an output buffer for each source and wherein each destination can disable waiting messages in the queue of a source for which the destination's respective output buffer has reached a preselected capacity.

Claim 6

A process as set forth in claim 1 wherein a source communicates bids to said process during a first one of said intervals; wherein said allocations occur during a second one of said intervals; wherein the allocation is communicated to the allocated sources and destinations are during a third one of said intervals; and wherein data transfer between correspondingly allocated sources and destinations occurs during a forth interval.

Claim 7

A process as set forth in claim 5 wherein each source maintains a bid queue for each destination and wherein said queues are at least three elements long so that it is possible for a source to transfer data cells during consecutive intervals.

Claim 8

In a router for connecting, to a plurality of data destinations, a plurality of data sources bidding for connection to identified ones of said destinations, respective sets of connections being made during each of a succession of intervals using a matrix of crosspoint switch elements, said sources including sources of at least first and second priority levels, said first priority level being of higher priority than the second, a process for allocating the switch elements to possible connections which comprises: providing, in correspondence with said switch element matrix, a data array having a number of data elements corresponding to the number of said switch elements; generating for each interval, first and second pseudo-random shuffle patterns, the respective shuffle patterns generated for each interval being the current shuffle patterns for the respective interval; assigning, in accordance with said first current pseudo-random shuffle pattern, a respective source to each of said data elements; assigning, in accordance with said second current pseudo-random shuffle pattern, a respective destination to each of said data elements; performing an incremental testing across the array, of the sources and destinations assigned to each data element to locate matches of bidding sources and destinations not previously allocated and successively allocating each match to the switch element corresponding to the respective data element, said first shuffle pattern being biased to place sources of said first priority level closer to the start of said incremental testing; and after testing the complete array, operating the switch elements during a subsequent interval in accordance with the allocations made.

Claim 9

In a router for connecting, to a plurality of data destinations, a plurality of data sources bidding for connection to identified ones of said destinations, respective sets of connections being made during each of a succession of intervals using a matrix of crosspoint switch elements, said sources including sources of at least first and second priority levels, said first priority level being of higher priority than the second, a process for allocating the switch elements to possible connections which comprises: providing, in correspondence with said switch element matrix, a data array having a number of data elements corresponding to the number of said switch elements; generating for each interval, first and second pseudo-random shuffle patterns, the respective shuffle patterns generated for each interval being the current shuffle patterns for the respective interval; assigning, in accordance with said first current pseudo-random shuffle pattern, a respective source to each of said data elements; assigning, in accordance with said second current pseudo-random shuffle pattern, a respective destination to each of said data elements; performing an incremental testing across the array, of the sources and destinations assigned to each data element to locate matches of bidding sources and destinations not previously allocated and successively allocating each match to the switch element corresponding to the respective data element, said first shuffle pattern being biased to place sources of said first priority level closer to the start of said incremental testing; and after testing the complete array, operating the switch elements during a subsequent interval in accordance with the allocations made.

Claim 10

A process as set forth in claim 7 wherein a source communicates bids to said process during a first one of said intervals; wherein said allocations occur during a second one of said intervals; wherein the allocation is communicated to the allocated sources and destinations are during a third one of said intervals; and wherein data transfer between correspondingly allocated sources and destinations occurs during a forth interval.

Claim 11

A process as set forth in claim 8 wherein each source maintains a bid queue for each destination and wherein said queues are at least three elements long so that it is possible for a source to transfer data cells during consecutive intervals.

Claim 12

In a router for connecting, to a plurality of data destinations, a plurality of data sources bidding for connection to identified ones of said destinations, respective sets of connections being made during each of a succession of intervals using a matrix of crosspoint switch elements; a process for allocating the switch elements to possible connections which comprises: providing, in correspondence with said switch element matrix, a two dimensional data array having a number of data elements corresponding to the number of said switch elements; generating for each interval, first and second pseudo-random shuffle patterns, the respective shuffle patterns generated for each interval being the current shuffle patterns for the respective interval; assigning a respective source to each of said data elements, the assigning of a respective source to each of said data elements being in accordance with said first current pseudo-random shuffle pattern; assigning a respective destination to each of said data elements, the assigning of a respective destination to each of said data elements being in accordance with said second current pseudo-random shuffle pattern; starting at one corner of said array, performing a testing of successively progressing diagonal regions across the array of the sources and destinations assigned to each array element to locate matches of bidding sources and destinations not previously allocated and successively allocating each match to the switch element corresponding to the respective data element; and after testing the complete array, operating the switch elements during a subsequent interval in accordance with the allocations made.

Claim 13

In a router for connecting, to a plurality of data destinations, a plurality of data sources bidding for connection to identified ones of said destinations, respective sets of connections being made during each of a succession of intervals using a matrix of crosspoint switch elements; a process for allocating the switch elements to possible connections which comprises: providing, in correspondence with said switch element matrix, a two dimensional data array having a number of data elements corresponding to the number of said switch elements; generating for each interval, first and second pseudo-random shuffle patterns, the respective shuffle patterns generated for each interval being the current shuffle patterns for the respective interval; assigning a respective source to each of said data elements, the assigning of a respective source to each of said data elements being in accordance with said first current pseudo-random shuffle pattern; assigning a respective destination to each of said data elements, the assigning of a respective destination to each of said data elements being in accordance with said second current pseudo-random shuffle pattern; starting at one corner of said array, performing a testing of successively progressing diagonal regions across the array of the sources and destinations assigned to each array element to locate matches of bidding sources and destinations not previously allocated and successively allocating each match to the switch element corresponding to the respective data element; and after testing the complete array, operating the switch elements during a subsequent interval in accordance with the allocations made.

Claim 14

A process as set forth in claim 10 wherein each source maintains a message buffer having a respective queue for each destination and wherein each destination maintains an output buffer for each source and wherein each destination can disable waiting messages in the queue of a source for which the destination's respective output buffer has reached a preselected capacity.

Claim 15

A process as set forth in claim 10 wherein a source communicates bids to said process during a first one of said intervals; wherein said allocations occur during a second one of said intervals; wherein the allocation is communicated to the allocated sources and destinations are during a third one of said intervals; and wherein data transfer between correspondingly allocated sources and destinations occurs during a forth interval.

Claim 16

In a router for connecting, to a plurality of data destinations, a plurality of data sources bidding for connection to identified ones of said destinations, respective sets of connections being made during each of a succession of intervals using a matrix of crosspoint switch elements; a system for allocating the switch elements to possible connections which comprises: for each source, a message buffer having a respective queue for each destination; for each destination, an output buffer for each source; a respective means associated with each destination for disabling waiting messages in the queue of a source for which the destination's respective output buffer has reached a preselected capacity; means for providing, in correspondence with said switch element matrix, a data array having a number of data elements corresponding to the number of said switch elements; assigning a respective source to each of said data elements; assigning a respective destination to each of said data elements; performing an incremental testing across the array, of the sources and destinations assigned to each array element to locate matches of bidding sources and destinations not previously allocated and successively allocating each match to the switch element corresponding to the respective data element; and after testing the complete array, operating the switch elements during a subsequent interval in accordance with the allocations made.

Claim 17

In a router for connecting, to a plurality of data destinations, a plurality of data sources bidding for connection to identified ones of said destinations, respective sets of connections being made during each of a succession of intervals using a matrix of crosspoint switch elements; a system for allocating the switch elements to possible connections which comprises: for each source, a message buffer having a respective queue for each destination; for each destination, an output buffer for each source; a respective means associated with each destination for disabling waiting messages in the queue of a source for which the destination's respective output buffer has reached a preselected capacity; means for providing, in correspondence with said switch element matrix, a data array having a number of data elements corresponding to the number of said switch elements; assigning a respective source to each of said data elements; assigning a respective destination to each of said data elements; performing an incremental testing across the array, of the sources and destinations assigned to each array element to locate matches of bidding sources and destinations not previously allocated and successively allocating each match to the switch element corresponding to the respective data element; and after testing the complete array, operating the switch elements during a subsequent interval in accordance with the allocations made.

Claim 18

In a router for connecting, to a plurality of data destinations, a plurality of data sources bidding for connection to identified ones of said destinations, respective sets of connections being made during each of a succession of intervals using a matrix of crosspoint switch elements; a process for allocating the switch elements to possible connections which comprises: providing, in correspondence with said switch element matrix, a data array having a number of data elements corresponding to the number of said switch elements, said array being divisible into a plurality of regions corresponding to subgroupings of said data elements; generating for each interval, first and second pseudo-random shuffle patterns, the respective shuffle patterns generated for each interval being the current shuffle patterns for the respective interval; assigning, in accordance with said first current pseudo-random shuffle pattern, a respective source to each of said data elements; assigning, in accordance with said second current pseudo-random shuffle pattern, a respective destination to each of said data elements; starting at one corner of said array, performing a testing of successively progressing diagonal grouping of regions across the array of the sources and destinations assigned to each array region to locate matches of bidding sources and destinations not previously allocated and successively allocating each match to the switch element corresponding to the respective data element; and after testing the complete array, operating the switch elements during a subsequent interval in accordance with the allocations made.

Claim 19

In a router for connecting, to a plurality of data destinations, a plurality of data sources bidding for connection to identified ones of said destinations, respective sets of connections being made during each of a succession of intervals using a matrix of crosspoint switch elements; a process for allocating the switch elements to possible connections which comprises: providing, in correspondence with said switch element matrix, a data array having a number of data elements corresponding to the number of said switch elements, said array being divisible into a plurality of regions corresponding to subgroupings of said data elements; generating for each interval, first and second pseudo-random shuffle patterns, the respective shuffle patterns generated for each interval being the current shuffle patterns for the respective interval; assigning, in accordance with said first current pseudo-random shuffle pattern, a respective source to each of said data elements; assigning, in accordance with said second current pseudo-random shuffle pattern, a respective destination to each of said data elements; starting at one corner of said array, performing a testing of successively progressing diagonal grouping of regions across the array of the sources and destinations assigned to each array region to locate matches of bidding sources and destinations not previously allocated and successively allocating each match to the switch element corresponding to the respective data element; and after testing the complete array, operating the switch elements during a subsequent interval in accordance with the allocations made.

Claim 20

A process as set forth in claim 14 wherein a source communicates bids to said process during a first one of said intervals; wherein said allocations occur during a second one of said intervals; wherein the allocation is communicated to the allocated sources and destinations are during a third one of said intervals; and wherein data transfer between correspondingly allocated sources and destinations occurs during a forth interval.

Claim 21

A process as set forth in claim 15 wherein each source maintains a message buffer having a queue for each destination and wherein said queues are at least three elements long so that it is possible for a source to transfer data cells during consecutive intervals.