Packet routing switch

• US 5,226,039 A
• Filed: 05/18/1990
• Issued: 07/06/1993
• Est. Priority Date: 12/22/1987
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Kendall Square Research Corp.
• Inventors: Kelly, Dana R., Frank, Steven J., Burkhardt, Henry III, Epstein, David I., Morss, Stephen W., Binder, Paul A., Rothnie, James B.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): KIZOU, HASSAN
• Application Number:
  US07/526,396
• Time in Patent Office: 1,145 Days
• Field of Search: 370/60, 370/60.1, 370/94.1, 370/94.3, 370/85.14, 370/85.15, 370/85.5, 370/85.12, 370/85.13, 370/91, 370/92, 340/825.5, 340/825.51
• US Class Current: 370/405
• CPC Class Codes: G06F 11/004 Error avoidance G06F11/07 and subgroups take precedence
• CPC Class Codes: G06F 11/0724 in a multiprocessor or a multi-core unit multiprocessors per se G06F15/80
• CPC Class Codes: G06F 11/073 in a memory management context, e.g. virtual memory or cache management memory management G06F12/00; testing of static memory units G11C29/00
• CPC Class Codes: G06F 11/0772 Means for error signaling, e.g. using interrupts, exception flags, dedicated error registers
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0817 using directory methods
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 15/17337 Direct connection machines, e.g. completely connected computers, point to point communication networks coupling between buses G06F13/4004
• CPC Class Codes: G06F 2212/272 Cache only memory architecture [COMA]
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3856 Reordering of instructions, e.g. using queues or age tags
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory
• CPC Class Codes: G06F 9/3865 using deferred exception handling, e.g. exception flags
• CPC Class Codes: G06F 9/468 Specific access rights for resources, e.g. using capability register
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: H04L 12/433 : with asynchronous transmission, e.g. token ring, register insertion
• CPC Class Codes: H04L 12/4637 : Interconnected ring systems
• CPC Class Codes: H04L 12/5601 : Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5605 : Fibre
• CPC Class Codes: H04L 2012/562 : Routing
• CPC Class Codes: H04L 45/00 : Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/04 : Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 49/107 : using shared medium
• CPC Class Codes: H04L 49/256 : Routing or path finding in ATM switching fabrics

Abstract

A switch is provided for selectively routing digital information packets received from at least first and second external sources to at least first and second external destinations. At least one of the first sources generates an information packet including a datum, or a request therefore, and a corresponding descriptor. First and second routing interconnects have inputs for receiving packets from respective sources and outputs for transmitting packets to respective destinations. The interconnects are also coupled for transferring packets between one another. Directories within the interconnects store descriptors corresponding to data associated with the first destination, as well as requests routed from the other interconnect. A controller routes packets based on the correspondence, or lack thereof, between the descriptor in that packet and an entry signal allocated to corresponding directory.

Claims

1. A switch for selectively routing digital information packets received from at least first and second external sources to at least first and second external destinations,

at least said first external destination having associated therewith zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy is referenced,

at least one of said first and second external sources including means for generating information packets comprising one or more signals representative of a datum or copy thereof or request therefor and further comprising at least a signal representative of a descriptor,

said routing switch comprising:

A. first and second routing interconnect elements, each including

i) a first input means for receiving an information packet from a respective one of said first and second external sources,

ii) a first output means for transmitting an information packet to a respective one of said first and second external destinations,

iii) second input means for receiving an information packet from the other of said routing interconnect elements, and

iv) second output means for transmitting an information packet to the other of said routing interconnect element,

B. each of said routing interconnect elements including directory means having allocated therein zero, one or more entry signals respectively representative of descriptors corresponding to at least one of

i) said zero, one or more data or copies thereof associated with said first external destination,

ii) zero, one or more data or copies thereof requested in information packets received by the second input means of that routing interconnect element and routed for transmission by the first output means of that routing interconnect element, and

C, each of said routing interconnect elements further including control means for selectively transferring an information packet received by at least one of the first and second input means of the associated routing interconnect element to at least one of the first and second output means of that routing interconnect element based on correspondence, or lack thereof, between the descriptor in that information packet and an entry signal allocated to that directory means.

2. A switch according to claim 1, wherein said control means of the first routing interconnect element includes at least one of

A. means responsive to receipt, at the second input means of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that corresponds to an entry signal allocated to the directory means of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that second input means to the first output means of that routing interconnect element, and

B. means responsive to receipt, at the second input means of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that does not correspond to a valid entry signal allocated to the directory means of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that second input means to the second output means of that routing interconnect element.

3. A switch according to claim 2, wherein said control means includes means selectively responsive to transfer of packet including a datum or copy thereof from at least one of

i) the first input means to the second output means of the associated routing interconnect element, and

ii) the second input means to the first output means of the associated routing interconnect element

for at least one of allocating, deallocating or modifying an entry signal in the directory means of that element.

4. A switch according to claim 3, wherein said control means includes means selectively responsive to transfer of a packet including a request for a datum or copy thereof from the second input means to the first output means of the associated routing interconnect element for at least one of allocating, deallocating and modifying an entry signal in the directory means of that element.

5. A switch according to claim 4, wherein said first and second routing interconnect elements are disposed physically remotely from one another.

6. A switch according to claim 5, wherein at least one information packet generated by said first and second external sources includes a requester-ID signal associated with an external destination to which that packet is directed, at least one of said routing interconnect elements comprising at least one of

A. means responsive to receipt on any of the first and second input means of that routing interconnect element of at least a selected packet including a requester-ID signal associated with the external destination to which the first output means transmits information packets for routing that selected packet to that first output means, and

B. means responsive to receipt on any of the first and second input means of that routing interconnect element of at least a selected packet including a requester-ID signal that is not associated with the external destination to which the first output means transmits information packets for routing that selected packet to the second output means of that routing interconnect element.

12. A switch according to any of claims 1-11, wherein said control means of the first routing interconnect element includes at least one of

A. means responsive to receipt, at the first input means of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that corresponds to an entry signal allocated to the directory means of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that first input means to the first output means of that routing interconnect element, and

B. means responsive to receipt, at the first input means of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that does not correspond to an entry signal allocated to the directory means of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that first input means to the second output means of that routing interconnect element.

13. A switch according to any of claims 1-11, wherein said control means of the second routing interconnect element includes at least one of

A. means responsive to receipt, at the first input means of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that does not correspond to an entry signal allocated to the directory means of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that first input means to the first output means of that routing interconnect element, and

B. means responsive to receipt, at the first input means of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that corresponds to a entry signal allocated to the directory means of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that first input means to the second output means of that routing interconnect element.

16. A switch according to any of claims 1-11, wherein at least on of said routing interconnect elements includes means selectively responsive to receipt at said first input means of a packet including a response to a request packet previously routed from the second input means to the first output means of that routing interconnect element for routing that packet from that first input means to the second output means of that routing interconnect element.

17. A switch according to claim 16, wherein at least said second routing interconnect element includes means selectively responsive to receipt at said first input means of a packet including a datum or copy thereof for which at least one of

i) a read-only request has previously been transferred from the second input means of that routing interconnect element to the first output means of that routing interconnect element, and

ii) an invalid copy is associated with said first external destination, for generating a duplicate packet including a copy of that datum and for transferring that duplicate packet to said second output means.

18. A switch according to claim 16, wherein at least said second routing interconnect element includes means selectively responsive to receipt at said first input means of a packet including a datum or copy thereof for which any of an ownership request and an atomic request packet has been transferred from the second input means to the first output means of that routing interconnect element for transferring that packet received at said first input means to the second output means of that routing interconnect element.

19. A switch according to any of claims 1-11, wherein the directory means of at least one of said routing interconnect elements includes means for storing association state-defining information for at least selected data, or copies thereof, associated with said first external destination, said association state-defining information including at least one of

i) an invalid association state for an invalid datum associated with said first external destination,

ii) a read-only association state for a copy of a datum associated with and subject to read-only access within said first external destination, no copy of which datum is modifiable within said first external destination,

iii) a nonexclusive ownership association state for a datum associated with an d modifiable within said first external destination, one or more read-only copies of which datum are associated with at least one of said first and second external destinations, and

iv) an exclusive ownership association state for a datum exclusively associated with and modifiable within said first external destination, no read-only copies of which datum are associated with either of said first and second external destinations.

20. A switch according to claim 19, wherein the directory means of at least one of said routing interconnect elements includes means for storing pending state-defining information for at least selected data for which requests are pending state-defining information including at least one of

i) a none-pending pending state for a datum for which no requests are pending,

ii) a read-only pending state for a datum for which a read-only association request is pending,

iii) an ownership pending state for a datum for which an ownership association request is pending, or for which an invalidation request is pending, and

iv) a reissue pending state for a datum for which a request is pending and for which a response other than one generated in response to that request has issued, which response was not routed from the first input means to the second output means of that routing interconnect element.

21. A switch according to any of claims 1-11, wherein at least one of said routing interconnect elements includes multiple request-handling means selectively responsive to receipt, at the second input means of that routing interconnect element, of multiple information packets requesting a datum for transferring an initial one of those request packets to the first output means of that routing interconnect element and for modifying later received ones of such request packets to indicate that a responder is busy and transferring those modified packets to the second output means of that routing interconnect element.

22. A switch according to claim 21, wherein said multiple request-handling means includes at least one of

A. means selectively responsive to receipt, at the second input means of the associated routing interconnect element, of multiple information packets requesting read-only allocation of a datum for transferring an initial one of those request packets to the first output means of that associated routing interconnect element and for modifying later received ones of such request packets to indicate that a responder is busy and transferring those modified packets to the second output means of that associated routing interconnect element, and

B. means selectively responsive to receipt, at the second input means of the associated routing interconnect element, of one or more information packets requesting ownership allocation or invalidation of a datum for transferring those packets to the first output means of that associated routing interconnect element.

23. A switch according to claim 21, wherein said multiple request-handling means includes at least one of

A. means selectively responsive to receipt, at the second input means of that routing interconnect element, of multiple information packets requesting read-only allocation of a datum for transferring an initial one of those request packets to the first output means of that associated routing interconnect element and for modifying later received ones of such request packets to indicate that a responder is busy and transferring those modified packets to the second output means of that associated routing interconnect element,

B. means selectively responsive to receipt, at the second input means of the associated routing interconnect element, of multiple information packets requesting exclusive ownership of a datum for transferring an initial one of those request packets to the first output means of that associated routing interconnect element and for modifying later received ones of such request packets to indicate that a responder is busy and transferring those modified packets to the second output means of that associated routing interconnect element,

C. means selectively responsive to receipt, at the second input means of the associated routing interconnect element, of multiple information packets requesting, without wait, atomic ownership of a datum for transferring an initial one of those request packets to the first output means of that associated routing interconnect element and for modifying later received ones of such request packets to indicate that the requested datum is atomically owned and transferring those modified packets to the second output means of that associated routing interconnect element,

D. means selectively responsive to receipt, at the second input means of the associated routing interconnect element, of multiple information packets requesting, with wait, atomic ownership of a datum for transferring an initial one of those request packets to the first output means of that associated routing interconnect element and for modifying subsequently received ones of such request packets, as well as to subsequently received packets requesting atomic ownership without wait, to indicate that the requested datum is atomically owned and transferring those modified packets to the second output means of that associated routing interconnect element, and

E. reissue means selectively responsive to receipt, at the second input means of the associated routing interconnect element, of an unresolved information packet requesting a datum, which information packet was previously issued by said multiple request-handling means, for modifying that packet to indicate that a responder is busy and transferring that modified packets to the second output means of that associated routing interconnect element.

24. A switch according to any of claims 1-11, wherein the directory means of at least one of said routing interconnect elements includes means for storing pending state-defining information for at least selected data for which requests are pending to the associated external destination, said pending state-defining information including at least one of

i) a none-pending pending state for a datum for which no requests are pending,

ii) a read-only pending state for a datum for which a read-only association request is pending,

iii) an exclusive ownership pending state for a datum for which an exclusive ownership association request is pending,

iv) an ownership invalidate pending state for a datum for which an invalidate request is pending;

v) a GET pending state for a datum for which an atomic ownership request, without wait, is pending,

vi) a GETW pending state for a datum for which an atomic ownership request, with wait, is pending, and

vii) an atomic pending state for a datum for which an atomic ownership request, with wait, is pending, which datum is previously associated with said atomic state in one of said first and second external destinations, and

iv) a reissue pending state for a datum for which a request is pending and for which a response other than one generated in response to that request has issued, which response was not routed from the first input means to the second output means of that routing interconnect element.

25. A switch according to any of claims 1-11, wherein at least one of said first and second routing interconnect elements include

A. multiple request-handling means selectively responsive to receipt, at the second input means of the associated routing interconnect element, of multiple information packets requesting allocation of a datum for transferring an initial one of those request packets to the first output means of that associated routing interconnect elements and for deleting later received ones of said request packets, and

B. said multiple request-handling means including merge means for associating a merged-state signal with a datum for which such later received ones of said requests have been deleted.

26. A switch according to claim 25, wherein said multiple request means includes means responsive to a packet including a datum associated with said merged-state signal for modifying that packet to include a merged-response signal indicating that a requester to which that response packet is directed should not delete that packet.

27. A switch according to claim 25, wherein

A. multiple request-handling means selectively responsive to receipt, at the second input means of the associated routing interconnect element, of multiple information packets requesting like access to a datum for transferring an initial one of those request packets to the first output means of that associated routing interconnect elements and for deleting later received ones of said request packets, and

B. said multiple request-handling means including merge means for associating a merged-state signal with a datum for which such later received ones of such like requests have been deleted.

28. A switch according to claim 25, wherein the directory means of at least one of said routing interconnect elements includes means for storing pending state-defining information for at least selected data for which requests are pending to the associated external destination, said pending state-defining information including at least one of

i) a none-pending pending state for a datum for which no requests are pending,

ii) a wait pending state for a datum for which a request packet is pending and for which a response has previously issued, which request packet is to be emptied upon receipt thereof by the routing interconnect element,

iii) a wait-merge-read-only pending state for a datum for which multiple information packets requesting read-only association have been received and for which a single read-only request packet is pending, which single read-only request packet is to be emptied upon receipt thereof by the routing interconnect element,

iv) a wait-merge-exclusive pending state for a datum for which multiple information packets requesting exclusive ownership association have been received and for which a single exclusive ownership request packet is pending, which single exclusive ownership request packet is to be emptied upon receipt thereof by the routing interconnect element,

v) a wait-merge-atomic pending state for a datum for which multiple information packets requesting atomic ownership association have been received and for which a single atomic ownership request packet is pending, which single atomic ownership request packet is to be emptied upon receipt thereof by the routing interconnect element,

vi) a reissue pending state for a datum for which a read request packet is pending, which read request packet is to be reissued upon receipt thereof by the routing interconnect element,

vii) a reissue-merge-read-only pending state for a datum for which multiple information packets requesting read-only association have been received by the routing interconnect element, and for which a single read-only request packet is pending, which single read-only request packet request is to be reissued upon receipt thereof by the routing interconnect element,

viii) a reissue-merge-exclusive pending state for a datum for which multiple information packets requesting exclusive ownership association have been received by the routing interconnect element, and for which a single exclusive ownership request packet is pending, which single exclusive ownership request packet is to be reissued upon receipt thereof by the routing interconnect element,

ix) a reissue-merge-atomic pending state for a datum for which multiple information packets requesting atomic ownership association have been received by the routing interconnect element, and for which a single atomic ownership request packet is pending, which single atomic ownership request packet is to be reissued upon receipt thereof by the routing interconnect element,

x) a read-only pending state for a datum for which a read-only association request packet is pending,

xi) a read-only-merge pending state for a datum for which multiple information packets requesting read-only association have been received and for which a single read-only request packet is pending, which single read-only request packet is to be marked as merged upon receipt thereof by the routing interconnect element,

xii) an exclusive ownership pending state for a datum for which an exclusive ownership association request packet is pending,

xiii) an exclusive-merge pending state for a datum for which an exclusive ownership request packet was pending upon receipt by the routing interconnect element of a further request for that datum, which exclusive ownership request packet is to be marked as merged upon receipt thereof by the routing interconnect element,

xiv) an atomic pending state for which an atomic ownership request packet is pending,

xv) an atomic-merge pending state for a datum for which an atomic ownership request packet was pending upon receipt by the routing interconnect element of a further request for that datum, which atomic-ownership request packet is to be marked as merged upon receipt thereof by the routing interconnect element,

xvi) a recombine pending state for a packet including a datum for which a recombine association packet is pending in an external destination, and

xvii) a merged response pending state for a datum for which a response packet marked as merged is pending and for which a further request has been received by the routing interconnect element.

29. A switch according to any of claims 1-11, wherein the control means of at least one of said routing interconnect elements includes routing directory unit means connected with the directory means of that routing interconnect element for generating an association-based routing signal indicative of a packet routing based on correspondence, or lack thereof, between the descriptor in an information packet received at any of said first and second input means of that routing interconnect element and an entry signal allocated to that directory means.

30. A switch according to any of claims 1-11, wherein

A. the first input means and the first output means of said first routing interconnect element are arranged together to form a first terminal pair, and

B. said first terminal pair comprises a bus connecting said first external source to said first external destination.

31. A switch according to claim 30, wherein

A. the first input means and the first output means of said second routing interconnect element are arranged together to form a second terminal pair, and

B. said second terminal pair comprises a bus connecting said second external source to said second external destination.

32. A switch according to claim 31, wherein at least one of said first and second terminal pairs comprise a plurality of shift register stages each for sequentially and successively transferring at least a portion of an information packet.

33. A switch according to claim 29, wherein at least one of said interconnect elements comprise

A. extract buffer means connected to said first input means and to said second output means of that routing interconnect element for buffering information packets transferred therebetween, and

B. insert buffer means connected to said second input means and to said first output means of that routing interconnect element for buffering information packets transferred therebetween.

34. A switch according to claim 33, wherein

A. the control means of at least one of said routing interconnect elements includes routing command means connected to said routing directory means and responsive to said association-based routing signal for selectively generating a push signal indicating that an information packet received at the first input means of that routing interconnect element is to be copied to the extract buffer means of that routing interconnect element, and

B. said first input means of at least one of said routing interconnect elements includes means connected to said routing command means of that routing interconnect element for responding to said push signal for generating a signal representing a copy of an information packet received at said first input means of that routing interconnect element and for transferring that signal to the extract buffer of that routing interconnect element.

35. A switch according to claim 33, wherein

A. the control means of at least one of said interconnect elements includes routing command means connected to said routing directory means and responsive to said association-based routing signal for selectively generating a pop signal indicating that an information packet buffered in said insert buffer means of that routing interconnect element is to be transferred to said first output means of that routing interconnect element, and

B. said insert buffer of at least one of said routing interconnect element includes means connected to said routing command means of that routing interconnect element for responding to said pop signal for transferring an information packet buffered therein to said first output means of that routing interconnect element.

36. A switch according to claim 33, wherein

A. the control means of at least one of said routing interconnect elements includes routing command means connected to said routing directory means of that routing interconnect element and responsive to said association-based routing signal for selectively generating a pass signal indicating that an information packet received at said first input means of that routing interconnect element is to be passed to said first output means of that routing interconnect element,

B. said first input means of at least one of said routing interconnect elements includes means connected to said routing command means of that routing interconnect element for responding to said pass signal for transferring an information packet received at said first input means of that routing interconnect element to said first output means of that routing interconnect element.

37. A switch according to claim 33, wherein

A. the control means of at least one of said routing interconnect elements includes routing command means connected to said routing directory means of that routing interconnect element and responsive to said associated-based routing signals for selectively generating an empty signal indicating that an information packet received at said first input means of that routing interconnect element is to be emptied, and

B. said first input means of at least one of said routing interconnect elements includes means connected to said routing command means of that routing interconnect element for responding to said empty signal for modifying an information packet received at said first input means of that routing interconnect element to indicate that it is empty.

38. A switch according to claim 33, wherein

A. the control means of at least one of said routing interconnect elements includes extract buffer management means connected to aid extract buffer means of that routing interconnect element for generating a buffer-region signal representative of a number of packets buffered therein,

B. said routing directory means of that control means includes means for selectively generating an extract signal indicating that an information packet received at said first input means of that routing interconnect element is to be transferred to said extract buffer means of that routing interconnect element, and

C. said control means further includes routing command means connected to aid routing directory means of that routing interconnect element and to said extract buffer management means of that routing interconnect element for generating a routing signal indicative of a packet routing based upon said extract signal and said buffer-region signal.

39. A switch according to claim 38, wherein said routing command means of at least one of said routing interconnect elements includes extract-all means responsive to assertion of said extract signal and to a buffer-region signal representative of a number less than a first threshold value for transferring all information packets received at said first input means of the routing interconnect element to said extract buffer means of that routing interconnect element.

40. A switch according to claim 38, wherein said routing command means of at least one of said routing interconnect elements includes extract-nonoptional means responsive to assertion of said extract signal and to a buffer-region signal representative of a number greater than said first threshold value and less than a second, higher threshold value for selectively transferring information packets received at said first input means of the routing interconnect element to said extract buffer means of that routing interconnect element or, alternatively, transferring one or more such packets to said first output means of that routing interconnect element.

41. A switch according to claim 40, wherein said extract-nonoptional means of at least one of said routing interconnect elements includes means for selecting for transfer to said first output means of that routing interconnect element an information packet including any of

i) a read-only copy of a datum received at the first input means of that routing interconnect element, no read-only copy of which datum is associated with said first external destination;

and

ii) a datum subject to ownership access received at the first input means of the second routing interconnect element, no copy of which datum subject to ownership access is associated with said first external destination.

42. A switch according to claim 38, wherein said routing command means of at least one of said routing interconnect elements includes extract-pending means responsive to assertion of said extract signal and to a buffer-region signal representative of a number greater than said second threshold value and less than a third, highest threshold for selectively transferring a packet received at the first input means of said routing interconnect element to said extract buffer means of that routing interconnect element or, alternatively, transferring that packet to said first output means of that routing connect element.

43. A switch according to claim 42, wherein said extract-pending means of at least one of said routing interconnect elements includes means for selecting for transfer to said first output means of that routing interconnect element an information packet including any of

i) a read-only copy of a datum received at the first input means of the second routing interconnect element, no read-only copy of which datum is associated with said first external destination,

ii) a datum subject to ownership access received at the first input means of the second routing interconnect element, no copy of which datum subject to ownership access is associated with said first external destination, and

iii) a response packet received at the first input means of the first routing interconnect element to a request packet previously received at the first input means of the second routing interconnect element.

44. A switch according to claim 38, wherein said routing command means of at least one of said routing interconnect elements includes extract-full means responsive to a buffer-region signal representative of a number greater than said third threshold for preventing the transfer of an information packet to said extract buffer means of that routing interconnect element.

45. A switch according to any of claims 1-11, wherein the second output of at least one of said routing interconnect elements includes outgoing buffer means for buffering information packets transferred from the corresponding extract buffer means to the second output means of that routing interconnect element.

46. A switch according to claim 45, wherein the second output of said at least one interconnect elements includes ring packet queue means connected in parallel between the extract buffer means of that routing interconnect element and outgoing buffer means of that routing interconnect element for at least one of

i) buffering overflow packets transferred therebetween,

ii) buffering packets for which acknowledgement of transfer is pending transferred between the corresponding outgoing buffer means and the second input means of the other interconnect element.

47. A switch according to claim 45, wherein said ring packet queue means comprises a circular queue.

48. A switch according to any of claims 1-11, wherein the second output means of at least one of said routing interconnect elements includes error queue means of storing one or more packets in which an error is detected.

49. A switch according to claim 48, wherein said error queue means includes means for storing, along with each packet in which an error is detected, a signal representative of an error associated with that packet.

50. A switch according to any of claims 1-11, wherein the second input means of at least one of said routing interconnect element includes incoming buffer means for buffering packets received at the second input means of that routing interconnect element.

7. A switch or selectively routing digital information packets received from at least first and second external sources to at least first and second external destinations,

at least said first external destination having associated therewith zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy is referenced,

at least one of said first and second external sources including means for generating information packets comprising one or more signals representative of a datum or copy thereof or request therefor and further comprising at least a signal representative of a descriptor,

said routing switch comprising:

A. first and second routing interconnect elements, each including

i) a first input means for receiving an information packet from a respective one of said first and second external sources,

ii) a first output means for transmitting an information packet to a respective one of said first and second external destinations,

iii) second input means for receiving an information packet from the other of said routing interconnect elements, and

iv) second output means for transmitting an information packet to the other of said routing interconnect element,

B. each of said routing interconnect elements including directory means having allocated therein zero, one or more entry signals respectively representative of descriptors corresponding to at least one of

i) said zero, one or more data or copies thereof associated with said first external destination,

ii) zero, one or more data or copies thereof requested in information packets received by the second input means of that routing interconnect element and routed for transmission by the first output means of that routing interconnect element,

C. each of said routing interconnect elements further including control means for selectively transferring an information packet received by at least one of the first and second input means of the associated routing interconnect element to at least one of the first and second output means of that routing interconnect element based on correspondence, or lack thereof, between the descriptor in that information packet and an entry signal allocated to that directory means, and

D. said control means of the second routing interconnect element includes at least one of

i) means responsive to receipt, at the second input means of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that does not correspond to an entry signal allocated to the directory means of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that second input means to the first output means of that routing interconnect element, and

ii) means responsive to receipt, at the second input means of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that corresponds to a valid entry signal allocated to the directory means of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that second input means to the second output means of that routing interconnect element.

8. A switch according to claim 7, wherein said control means includes means selectively responsive to transfer of packet including a datum or copy thereof from at least one of

i) the first input means to the second output means of the associated routing interconnect element, and

ii) the second input means to the first output means of the associated routing interconnect element

for at least one of allocating, deallocating or modifying an entry signal int eh directory means of that element.

9. A switch according to claim 8, wherein said control means includes means selectively responsive to transfer of a packet including a request for a datum or copy thereof from the second input means to the first output means of the associated routing interconnect element for at least one of allocating, deallocating and modifying an entry signal in the directory means of that interconnect element.

10. A switch according to claim 9, wherein said first and second routing interconnect elements are disposed physically remotely from one another.

11. A switch according to claim 10, wherein at least one information packet generated by said first and second external sources includes a requester-ID signal associated with an external destination to which that packet is directed, at least one of said routing interconnect elements comprising at least one of

A. means responsive to receipt on any of the first and second input means of that routing interconnect element of at least a selected packet including a requester-ID signal associated with the external destination to which the first output means transmits information packets for routing that selected packet to that first output means, and

B. means responsive to receipt on any of the first and second input means of that routing interconnect element of at least a selected packet including a requester-ID signal that is not associated with the external destination to which the first output means transmits information packets for routing that selected packet to the second output means of that routing interconnect element.

14. A switch according to any of claims 5, 6, 10, or 11, wherein at least one of said first and second routing interconnect elements includes remote interface means for at least one of

A. transmitting information packets from the second output means of that routing interconnect element to the remotely disposed second input means of the other of said routing interconnect elements, and

B. receiving information packets at the second input means of that routing interconnect element transmitted from the remotely disposed second output means of the other of said routing interconnect elements.

15. A switch according to claim 14, wherein said remote interface means includes fiber optic transmission media for carrying signals representative of said information packets between said at least one remotely disposed second input means and second output means of said routing interconnect elements.

51. A method for routing digital information packets received from at least first and second external sources to at least first and second external destinations,

at least said first external destination having associated therewith zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy is referenced,

at least one of said first and second external sources including means for generating information packets comprising one or more signals representative of a datum or copy thereof or request therefor and further comprising at least a signal representative of a descriptor,

said method comprising:

A. providing first and second routing interconnect elements, each including

i) a first input for receiving an information packet from a respective one of said first and second external sources,

ii) a first output for transmitting an information packet to a respective one of said first and second external destinations,

iii) second input for receiving an information packet from the other of said routing interconnect elements, and

iv) second output for transmitting an information packet to the other of said routing interconnect element,

B. allocating in a directory of each of said routing interconnect elements zero, one or more entry signals respectively representative of descriptors corresponding to at least one of

i) said zero, one or data or copies thereof associated with said first external destination,

ii) zero, one or more data or copies thereof requested in information packets received by the second input of that routing interconnect element and routed for transmission by the first output of that routing interconnect element, and

C. selectively transferring an information packet received by at least one of the first and second input of each of said routing interconnect elements to at least one of the first and second output of that routing interconnect element based on correspondence, or lack thereof, between the descriptor in that information packet and an entry signal allocated to that directory.

52. A method according to claim 51, comprising

A. responding within the first interconnect element to receipt, at the second input of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that corresponds to an entry signal allocated to the directory of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that second input to the first output of that routing interconnect element, and

B. responding within the first interconnect element to receipt, at the second input of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that does not correspond to a valid entry signal allocated to the directory of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that second input to the second output of that routing interconnect element.

53. A method according to claim 52, comprising selectively responding within at least one of said first and second routing interconnect elements to at least one of

i) the transfer of a packet including a datum or copy thereof from the first input to the second output of the associated routing interconnect element, and

ii) the transfer of a packet including a datum or copy thereof from the second input to the first output of the associated routing interconnect element

for at least one of allocating, deallocating or modifying an entry signal in the directory of that routing interconnect element.

54. A method according to claim 53, comprising selectively responding within at least one of said first and second routing interconnect elements to transfer of a packet including a request for a datum or copy thereof from the second input to the first output of that routing interconnect element for at least one of allocating, deallocating and modifying an entry signal in the directory of that element.

55. A method according to claim 54, comprising disposing said first and second routing interconnect elements physically remotely from one another.

56. A method according to claim 55, wherein at least one information packet generated by said first and second external sources includes a requester-ID signal associated with an external destination to which that packet is directed, said method comprising

A. responding within at least one of said first and second routing interconnect elements to receipt on any of the first and second inputs of that routing interconnect element of at least a selected packet including a requester-ID signal associated with the external destination to which the first output transmits information packets for routing that selected packet to that first output, and

B. responding within at least one of said first and second routing interconnect elements to receipt on any of the first and second inputs of that routing interconnect element of at least a selected packet including a requester-ID signal that is not associated with the external destination to which the first output transmits information packets for routing that selected packet to the second output of that routing interconnect element.

62. A method according to any of claims 51-61, comprising

A. responding within the first routing interconnect element to receipt, at the first input of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that corresponds to an entry signal allocated to the directory of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that first input to the first output of that routing interconnect element, and

B. responding within the first routing interconnect element to receipt, at the first input of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that does not correspond to an entry signal allocated to the directory of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that first input to the second output of that routing interconnect element.

63. A method according to any of claims 51-61, comprising

A. responding within the second routing interconnect element to receipt, at the first input of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that does not correspond to an entry signal allocated to the directory of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that first input to the first output of that routing interconnect element, and

B. responding within the second routing interconnect element to receipt, at the first input of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that corresponds to a entry signal allocated to the directory of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that first input to the second output of that routing interconnect element.

64. A method according to any of claims 55, 56, 60, or 61, comprising

A. transmitting within a least one of said first and second routing interconnect elements information packets from the second output of that routing interconnect element to the remotely disposed second input of the other of said routing interconnect elements, and

B. receiving information packets at the second input of that routing interconnect element transmitted from the remotely disposed second output of the other of said routing interconnect elements.

65. A method according to claim 64, comprising carrying on a fiber optic media signals representative of said information packets between said at least one remotely disposed second input and second output of said routing interconnect elements.

66. A method according to any of claims 51-61, comprising selectively responding within at least one of said routing interconnect elements to receipt at said first input of a packet including a response to a request packet previously routed from the second input to the first output of that routing interconnect element for routing that packet from that first input to the second output of that routing interconnect element.

67. A method according to claim 66, comprising selectively responding within at least said second routing interconnect element to receipt at said first input of a packet including a datum or copy thereof for which at least one of

i) a read-only request has previously been transferred from the second input of that routing interconnect element to the first output of that routing interconnect element, and

ii) an invalid copy is associated with said first external destination, for generating a duplicate information packet including a copy of that datum and for transferring that duplicate packet to said second output.

68. A method according to claim 66, comprising selectively responding within at least said second routing interconnect element to receipt at said first input of a packet including datum or copy thereof for which any of an ownership request and an atomic request packet has been transferred from the second input to the first output of that routing interconnect element for transferring that packet received at said first input to the second output of that routing interconnect element.

69. A method according to any of claims 51-61, comprising storing within the directory of at least one of said routing interconnect elements association state-defining information for at least selected data, or copies thereof, associated with said first external destination, said association state-defining information including at least one of

i) an invalid association state for an invalid datum associated with said first external destination,

ii) a read-only association state for a copy of a datum associated with and subject to read-only access within said first external destination, no copy of which datum is modifiable within said first external destination,

iii) a nonexclusive ownership association state for a datum associated with and modifiable within said first external destination, one or more read-only copies of which datum are associated with at least one of said first and second external destinations, and

iv) an exclusive association state for a datum exclusively associated with and modifiable within said first external destination, no read-only copies of which datum are associated with either of said first and second external destinations.

70. A method according to any of claims 51-61, comprising storing in the directory of at least one of said routing interconnect elements pending state-defining information for at least selected data for which requests are pending to the associated external destination, said pending state-defining information including at least one of

i) a none-pending pending state for a datum for which no requests are pending,

ii) a read-only pending state for a datum for which a read-only association request is pending,

iii) an ownership pending state for a datum for which an ownership association request is pending, or for which an invalidation request is pending, and

iv) a reissue pending state for a datum for which a request is pending and for which a response other than one generated in response to that request has issued, which response was not routed from the first input to the second output of that routing interconnect element.

71. A method according to any of claims 51-61, comprising selectively responding, within at least one of said routing interconnect elements, to receipt, at the second input of that routing interconnect element, of multiple information packets requesting a datum for transferring an initial one of those request packets to the first output of that routing interconnect element and for modifying later received ones of such request packets to indicate that a responder is busy and transferring those modified packets to the second output of that routing interconnect element.

72. A method according to claim 71, comprising

A. selectively responding, within said at least one routing interconnect element, to receipt, at the second input of that routing interconnect element, of multiple information packets requesting read-only allocation of a datum for transferring an initial one of those request packets to the first output of that associated routing interconnect element and for modifying later received ones of such request packets to indicate that a responder is busy and transferring those modified packets to the second output of that associated routing interconnect element, and

B. selectively responding, within said at least one routing interconnect element, to receipt, at the second input of that routing interconnect element, of one or more information packets requesting ownership allocation or invalidation of a datum for transferring those packets to the to the first output of that associated routing interconnect element.

73. A method according to claim 72, comprising

A. selectively responding, within said at least one routing interconnect element, to receipt, at the second input of that routing interconnect element, of multiple information packets requesting read-only allocation of a datum for transferring an initial one of those request packets to the first output of that associated routing interconnect element and for modifying later received ones of such request packets to indicate that a responder is busy and transferring those modified packets to the second output of that associated routing interconnect element,

B. selectively responding, within said at least one routing interconnect element, to receipt, at the second input of that routing interconnect element, of multiple information packets requesting exclusive ownership of a datum for transferring an initial one of those request packets to the first output of that associated routing interconnect element and for modifying later received ones of such request packets to indicate that a responder is busy and transferring those modified packets to the second output of that associated routing interconnect element,

C. selectively responding, within said at least one routing interconnect element, to receipt, at the second input of that routing interconnect element, of multiple information packets requesting, without wait, atomic ownership of a datum for transferring an initial one of those request packets to the first output of that associated routing interconnect element an for modifying later received ones of such request packets to indicate that the requested datum is atomically owned and transferring those modified packets to the second output of that associated routing interconnect element,

D. selectively responding, within said at least one routing interconnect element, to receipt, at the second input of that routing interconnect element, of multiple information packets requesting, with wait, atomic ownership of a datum for transferring an initial one of those request packets to the first output of that associated routing interconnect element and for modifying subsequently received ones of such request packets, as well as subsequently received packets requesting atomic ownership without wait, to indicate that the requested datum is atomically owned and transferring those modified packets to the second output of that associated routing interconnect element, and

E. selectively responding, within said at least one routing interconnect element, to receipt, at the second input of that routing interconnect element, of an unresolved information packet requesting a datum for modifying that packet to indicate that a responder is busy and transferring that modified packets to the second output of that associated routing interconnect element.

74. A method according to any of claims 71, comprising storing within the directory of at least one of said routing interconnect elements pending state-defining information for at least selected data for which requests are pending to the associated external destination, said pending state-defining information including at least one of

i) a none-pending pending state for a datum for which no requests are pending,

ii) a read-only pending state for a datum for which a read-only association request is pending,

iii) an exclusive ownership pending state for a datum for which an exclusive ownership association request is pending,

iv) an ownership invalidate pending state for a datum for which an invalidate request is pending;

v) an GET pending state for a datum for which an atomic ownership request, without wait, is pending,

vi) a GETW pending state for a datum for which an atomic ownership request, with wait, is pending, and

vii) an atomic pending state for a datum for which an atomic ownership request, with wait, is pending, which data is previously associated with said atomic state in one of said first and second external destinations, and

iv) a reissue pending state for a datum for which a request is pending and for which a response other than one generated in response to that request has issued, which response was not routed from the first input to the second output of that routing interconnect element.

75. A method according to any of claims 51-61, comprising

A. selectively responding, within said at least one routing interconnect element, to receipt, at the second input of that routing interconnect element, to multiple information packets requesting allocation of a datum for transferring an initial one of those request packets to the first output of that associated routing interconnect element and for deleting later received ones of said request packets, and

B. associating a merged-state signal with a datum for which such later received ones of said requests have been deleted.

76. A method according to claim 75, comprising selectively responding, within said at least one routing interconnect elements, to receipt, at the second input of that routing interconnect element, of a packet including a datum associated with said merged-state signal for modifying that packet to include a merged-response signal indicating that a requestor to which that response packet is directed should not delete that packet.

77. A method according to claim 75, comprising:

A. selectively responding, within said at least one routing interconnect element, to receipt, at the second input of that routing interconnect element, of multiple information packets requesting like allocation of a datum for transferring an initial one of those packets to the first output of that associated routing interconnect elements and for deleting later received ones of those packets, and

B. associating a merged-state signal with a datum for which such later received ones of such like request have been deleted.

78. A method according to claim 75, comprising storing within the directory of at least one of said routing interconnect elements pending state-defining information for at last selected data for which request are pending to the associated external destination, said pending state-defining information including at least one of

i) a none-pending pending state for a datum for which no requests are pending,

ii) a wait pending state for a datum for which a request packet is pending and for which a response has previously issued, which request packet is to be emptied upon receipt thereof by the routing interconnect element,

iii) a wait-merge-read-only pending state for a datum for which multiple information packets requesting read-only association have been received and for which a single read-only request packet is pending, which single read-only request packet is to be emptied upon receipt thereof by the routing interconnect element,

iv) a wait-merge-exclusive pending state for a datum for which multiple information packets requesting exclusive ownership association have been received and or which a single exclusive ownership request packet is pending, which single exclusive ownership request packet is to be emptied upon receipt thereof by the routing interconnect element,

v) a wait-merge-atomic pending state for a datum for which multiple information packets requesting atomic ownership association have been received and for which as ingle atomic ownership request packet is pending, which single atomic ownership request packet is to be emptied upon receipt thereof by the routing interconnect element,

vi) a reissue pending state for a datum for which a read request packet is pending, which read request packet is to be reissued upon receipt thereof by the routing interconnect element,

vii) a reissue-merge-read-only pending state for a datum for which multiple information packets requesting read-only association have been received by the routing interconnect element, and for which a single read-only request packet is pending, which single read-only request packet request is to be reissued upon receipt thereof by the routing interconnect element,

viii) a reissue-merge-exclusive pending state for a datum for which multiple information packets requesting exclusive ownership association have been received by the routing interconnect element, and for which a single exclusive ownership request packet is pending, which single exclusive ownership request packet is to be reissued upon receipt thereof by the routing interconnect element,

ix) a reissue-merge-atomic pending state for a datum for which multiple information packets requesting atomic ownership association have been received by the routing interconnect element, and for which a single atomic ownership request packet is pending, which single atomic ownership request packet is to be reissued upon receipt thereof by the routing interconnect element,

x) a read-only pending state for a datum for which a read-only association request packet is pending,

xi) a read-only-merge pending state for a datum for which multiple information packets requesting read-only association have been received and for which a single read-only request packet is pending, which single read-only request packet is to be marked as merged upon receipt thereof by the routing interconnect element,

xii) an exclusive ownership pending state for a datum for which an exclusive ownership association request packet is pending,

xiii) an exclusive-merge pending state for a datum for which an exclusive ownership request packet was pending upon receipt by the routing interconnect element of a further request for that datum, which exclusive ownership request packet is to be marked as merged upon receipt thereof by the routing interconnect element,

xiv) an atomic pending state for which an atomic ownership request packet is pending,

xv) an atomic-merge pending state for a datum for which an atomic ownership request packet was pending upon receipt by the routing interconnect element of a further request for that datum, which atomic-ownership request packet is to be marked as merged upon receipt thereof by the routing interconnect element,

xvi) a recombine pending state for a packet including a datum for which a recombine association packet is pending in an external destination, and

xvii) a merged response pending state for a datum for which a response packet marked as merged is pending and for which a further request has been received by the routing interconnect element.

79. A method according to any of claims 51-61, comprising generating within at least one of said routing interconnect elements an association-based routing signal indicative of a packet routing based on correspondence, or lack thereof, between the descriptor in an information packet received at any of said first and second input of that routing interconnect element and an entry signal allocated to that directory.

80. A method according to any of claims 51-61, comprising

A. buffering within an extract buffer of at least one of said first and second routing interconnect elements information packets transferred between the first input and the second output of that routing interconnect element, and

B. buffering within an insert buffer of at least one of said first and second routing interconnect elements information packets transferred between said second input and the first output of that routing interconnect element.

81. A method according to any of claims 51-61, comprising buffering information packets transferred from the extract buffer to the second output of at least one of said routing interconnect elements.

82. A method according to any of claims 51-61, comprising storing in an error queue in at least one of said routing interconnect elements one or more packets in which an error is detected.

83. A method according to any of claims 51-61, comprising buffering in an incoming buffer packet received at the second input of at least one of said routing interconnect elements.

57. A method for routing digital information packets received from at least first and second external sources to at lest first and second external destinations,

at least said first external destination having associated therewith zero, one or more data or copies thereof, each datum or copy thereof corresponding to a unique descriptor by which that datum or copy is referenced,

at least one of said first and second external sources including means for generating information packets comprising one or more signals representative of a datum or copy thereof or request therefor and further comprising at least a signal representative of a descriptor,

said method comprising:

A. providing first and second routing interconnect elements, each including

i) a first input for receiving an information packet from a respective one of said first and second external sources,

ii) a first output for transmitting an information packet to a respective one of said first and second external destinations,

iii) second input for receiving an information packet from the other of said routing interconnect elements, and

iv) second output for transmitting an information packet to the other of said routing interconnect element,

B. allocating in a directory of each of said routing interconnect elements zero, one or more entry signals respectively representative of descriptors corresponding to at least one of

i) said zero, one or more data or copies thereof associated with said first external destination,

ii) zero, one or more data or copies thereof requested in information packets received by the second input of that routing interconnect element and routed for transmission by the first output of that routing interconnect element, and

C. selectively transferring an information packet received by at least one of the first and second input of each of said routing interconnect elements to at least one of the first and second output of that routing interconnect element based on correspondence, or lack thereof, between the descriptor in that information packet and an entry signal allocated to that directory,

D. said selectively transferring step including the steps of

i) responding to receipt, at the second input of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that does not correspond to an entry signal allocated to the directory of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that second input to the first output of that routing interconnect element, and

ii) responding to receipt, at the second input of that routing interconnect element, of a packet including a request for a datum or copy thereof referenced by a descriptor that corresponds to a valid entry signal allocated to the directory of that routing interconnect element for a datum or copy thereof associated with said first external destination for routing that packet from that second input to the second output of that routing interconnect element.

58. A method according to claim 57, comprising selectively responding within at least one of said first and second routing interconnect elements to at least one of

i) the transfer of a packet including a datum or copy thereof from the first input to the second output of the associated routing interconnect element, and

ii) the transfer of a packet including a datum or copy thereof from the second input to the first output of the associated routing interconnect element

for at least one of allocating, deallocating or modifying an entry signal in the directory of that routing interconnect element.

59. A method according to claim 58, comprising selectively responding within at lest one of said first and second routing interconnect elements to transfer of a packet including a request for a datum or copy thereof from the second input to the first output of that routing interconnect element for at least one of allocating, deallocating and modifying an entry signal in the directory of that element.

60. A method according to claim 59, comprising disposing said first and second routing interconnect elements physically remotely from one another.

61. A method according to claim 60, wherein at least one information packet generated by said first and second external sources includes a requester-ID signal associated with an external destination to which that packet is directed, said method comprising

A. responding within at least one of said first and second routing interconnect elements to receipt on any of the first and second inputs of that routing interconnect element of at least a selected packet including a requester-ID signal associated with the external destination to which the first output transmits information packets for routing that selected packet to that first output, and

B. responding within at least one of said first and second routing interconnect elements to receipt on any of the first and second inputs of that routing interconnect element of at least a selected packet including a requester-ID signal that is not associated with the external destination to which the first output transmits information packets for routing that selected packet to the second output of that routing interconnect element.