Dynamic packet routing network

A digital data communications apparatus comprising

• A. first and second processing groups, each said group including a plurality of processing cells connected by an associated bus means for transferring signals representative of information packets therebetween,
• each processing cell
• i) having allocated thereto zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced
• ii) including CCU means for at least one of generating and receiving signals representative of an information packet including a descriptor of a datum subject to reference,
• iii) wherein each such descriptor has a value that is independent of a processing cell in which the corresponding datum is allocated and that is independent of the allocation of other data to that same processing cell,
• B. first level transfer means for transferring information packets between said first and second processing groups, said first level transfer means including
• i) first input means, coupled to the bus means of said first processing group, for receiving an information packet therefrom,
• ii) first output means, coupled to the bus means of said first processing group, for selectively outputting an information packet thereto,
• iii) second output means, coupled to the bus means of said second processing group, for selectively outputting an information packet thereto,
• C. said first level transfer means including routing control means, connected to said first input means and to said first and second output means, for routing an information packet received by that input means to a selected one of those output means based upon correspondence between the descriptor in that information packet and data allocated to, or requested for allocation by, one or more processing cells of said first processing group.

A routing switch apparatus for digital information packets, comprising

• A. first input means for receiving an information packet from a first processing group,
• B. first and second output means for transferring said information packet to a respective one of said first processing group and a second processing group,
• each said processing group comprising a plurality of processing cells coupled by an associated bus means,
• said first input and output means being coupled to the bus means associated with said first processing group, said second output means being coupled to the bus means associated with said second processing group,
• each processing cell
• i) having allocated thereto zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,
• ii) including CCU means for at least one of generating and receiving signals representative of an information packet including a descriptor of a datum subject to reference,
• ii) wherein each such descriptor has a value that is independent of a processing cell in which the corresponding datum is allocated and that is independent of the allocation of other data to that processing cell,
• C. first level transfer means for transferring information packets between said first and second processing groups, said first level transfer means including routing control means, connected to said first input means and to said first and second output means, for routing an information packet received by that input means to a selected one of those output means based upon correspondence between the descriptor in that information packet and the datum allocated to, or requested for allocation by, one or more processing cells in said first processing group.

A digital data communications apparatus comprising

• A. (n) packet transfer levels, each respectively designated level(k), where (k) represents successive integers between (0) and (n-1), inclusive,
• B. each packet transfer level including a plurality of segments, where the number of segments in each packet transfer level(k), except packet transfer level(0), is less than the number of segments in packet transfer level(k-1), and where packet transfer level(n-1) includes only one such segment, each segment including
• i) zero, one or more processing cells, each having
• zero, one or more data, or copies thereof, allocated thereto, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,
• CCU means for at least one of generating and receiving signals representative of an information packet including a descriptor of a datum subject to reference,
• wherein each such descriptor has a value that is independent of a processing cell in which the corresponding datum is allocated and that is independent of the allocation of other data to that processing cell,
• ii) bus means for carrying information packets within that segment,
• C. each segment of packet transfer level(k), for (k) between (1) and (n-1), inclusive, being referred to as a level(k) segment and including plural first level transfer means for selectively transferring information packets between that level(k) segment and one or more level(k-1) segments associated therewith, said first level transfer means including
• first input means, coupled to the bus means of that level(k) segment, for receiving an information packet therefrom,
• first output means, also coupled to the bus means of that level(k) segment, for selectively outputting an information packet thereto,
• second input means, coupled to the bus means of an associated level(k-1) segment, for receiving an information packet thereto,
• second output means, coupled to the bus means of that associated level(k-1) segment, for selectively outputting an information packet thereto,
• where each such associated level(k-1) segment, as well as each descendant thereof, if any, is termed a descendant of that level(k) segment, where the processing cells associated with descendants of a level(k) segment are referred to as a first group of processing cells and said processing cells other than those associated with a descendant of a level(k) segment are referred to as a second group of processing cells, and
• D. at least one said first level transfer means including routing control means, connected to said first and second input means and to said first and second output means, for routing an information packet received by any of those input means to a selected one of those output means based upon correspondence between the descriptor in that information packet and data allocated to one or more processing cells of the first processing group.

A digital data communications apparatus comprising

• A. (n) packet transfer levels, each respectively designated level(k), where (k) represents successive integers between (0) and (n-1), inclusive,
• B. each packet transfer level including a plurality of segments, where the number of segments in each packet transfer level(k), except packet transfer level(0), is less than the number of segments in packet transfer level (k-1), and where packet transfer level(n-1) includes only one such segment, each segment including
• i) zero, one or more processing cells, each having zero, one or more data, or copies thereof, allocated thereto, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,
• each processing cell further having means for generating a signal representative of an information packet, said information packet including one of at least a request packet having a descriptor corresponding to a datum to be allocated, and a response packet comprising a response to a request packet,
• ii) bus means for carrying information packets within that level(k) segment,
• C. CCU means coupled to said processing cells for selectively deallocating a datum allocated to a first cell and concurrently allocating that datum exclusively to a second cell,
• D. each level(k) segment, for (k) between (1) and (n-1), inclusive, including plural routing cells, each connected to the bus means of that segment and to the bus means of an associated level(k-1) segment for selectively transferring information packets between those segments, where each such associated level(k-1) segment, as well as each descendant thereof, is termed a descendant of that level(k) segment, and
• E. each said routing cell including means for selecting a request packet for transfer between associated level(k) and level(k-1) segments based upon correspondence of the descriptor in that request packet and a datum allocated to a processing cell in a descendant of that level(k) segment.

An improved method for digital data communications comprising the steps of

• A. providing first and second processing groups, each including a plurality of processing cells interconnected by an associated bus means for carrying information packet-representative signals,
• each processing cell having allocated thereto zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,
• wherein each such descriptor has a value that is independent of a processing cell in which the corresponding datum is allocated and that is independent of the allocation of other data to that same processing cell,
• B. generating within one or more of said processing cells signals representative of information packets, each including a descriptor of a datum subject to reference, and selectively transferring one or more of those information packet-representative signal to the bus means associated with said one or more processing cells which generated them, and
• C. selectively routing said information packets between the bus means associated with each of said first and second processing groups based upon prior routings, if any, of the data, or requests therefor, referenced by the descriptors in those packets between said first and second processing groups.

An improved method for digital data communications comprising the steps of

• A. providing first and second processing groups, each including a plurality of processing cells interconnected by an associated bus means for carrying information packet-representative signals,
• each processing cell having allocated thereto zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,
• wherein each such descriptor has a value that is independent of a processing cell in which the corresponding datum is allocated and that is independent of the allocation of other data to that same processing cell,
• B. generating within one or more of said processing cells signals representative of information packets, each including a descriptor of a datum subject to reference, and selectively transferring one or more of those information packet-representative signal to the bus means associated with said one or more processing cells which generated them, and
• C. selectively routing said information packets between the bus means associated with each of said first and second processing groups based upon correspondence between the descriptor in that information packet and the data allocated to, or requested for allocation by, one or more processing cells of said first processing group.

An improved method of digital information packet switching comprising the steps of

• A. receiving an information packet from a first processing group including a plurality of processing cells interconnected by an associated bus means for carrying information packet-representative signals,
• each processing cell having allocated thereto zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,
• wherein each such descriptor has a value that is independent of a processing cell in which the corresponding datum is allocated and that is independent of the allocation of other data to that same processing cell, and
• B. selectively routing said information packet to a respective one of said first processing group and a second processing group based upon correspondence between the descriptor in that information packet and the datum allocated to one or more processing cells of said first processing group,
• said second processing group including a plurality of processing cells interconnected by an associated bus means for carrying information packet-representative signals,
• each processing cell having allocated thereto zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,
• wherein each such descriptor has a value that is independent of a processing cell in which the corresponding datum is allocated and that is independent of the allocation of that corresponding datum with respect to other data, if any, allocated to that same processing cell.

A digital data communications apparatus comprising,

• A. first and second processing groups, each said group including a plurality of processing cells, the processing cells within each of said processing groups being connected by an associated bus means for transferring signals representative of information packets therebetween, each processing cell
• i) having allocated thereto zero, one or more data or copies thereof, each such datum or copy thereof corresponding to a unique descriptor by which that datum or copy thereof is referenced,
• ii) including CCU means for at least one of generating and receiving signals representative of an information packet including a descriptor of a datum or copy subject to reference,
• B. first level transfer means for transferring information packets between said first and second processing groups, said first level transfer means including,
• first input means, coupled to the bus means of said first processing group, for receiving an information packet therefrom,
• first output means, coupled to the bus means of said first processing group, for selectively outputting an information packet thereto,
• second output means, coupled to the bus means of said second processing group, for selectively outputting an information packet thereto,
• C. said first level transfer means including routing control means, connected to said first input means and to said first and second output means,
• said routing means including directory means for storing signals representative of descriptors corresponding with at least selected data or copies thereof allocated to said first processing group, said routing means providing for routing an information packet received on said first input means to a selected one of first and second output means based upon correspondence between a descriptor referenced in that information packet and a signal representative of that descriptor in said directory means.