High-speed packet switching apparatus and method

• US 5,335,325 A
• Filed: 03/26/1990
• Issued: 08/02/1994
• 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: Mann, William F., Frank, Steven J., Burkhardt, Henry III, Rothnie, James B.
• Primary Examiner(s): Rudolph, Rebecca L.
• Application Number:
  US07/499,182
• Time in Patent Office: 1,590 Days
• Field of Search: 395/200, 395/400, 395/800, 395/425, 370/94.1
• US Class Current: 711/163
• 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/0766 Error or fault reporting or storing
• 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 2212/272 Cache only memory architecture [COMA]
• CPC Class Codes: G06F 9/30003 Arrangements for executing specific machine instructions
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30047 Prefetch instructions; cache control instructions
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• 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/3851 from multiple instruction streams, e.g. multistreaming
• 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/3867 using instruction pipelines
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• 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/4637 : Interconnected ring systems
• CPC Class Codes: H04L 12/5601 : Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5681 : Buffer or queue management
• 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/309 : Header conversion, routing tables or routing tags

Abstract

An improved digital packet switching apparatus enabling enhanced packet transmission and high bandwidth packet transfer. The digital packet switching methods and apparatus permit selectively switching digital signal packet between a set of nodes. The invention includes multiple processing cells, each having a processor coupled to an associated content-addressable memory element. Packet processors, electrically coupled to the memory elements, selectively receive packets from the nodes and transmit the packets into at least one of the plural memory elements; or receive packets from the memory elements and transmit the packets to at least one of the nodes.

Claims

1. Digital packet switching apparatus for selectively switching digital signal packets between a set of nodes, said digital signal packets being configured in accordance with a selected protocol, the apparatus comprising

A. plural processing cells, each being associated with at least one of said nodes, and each including

a processing unit coupled to an associated memory element for storing information-representative signals, including digital signal packets, or portions thereof,

packet processing means, coupled to at least one of the nodes associated with that processing cell and to at least the memory element of that processing cell, for at least one of

(i) receiving a digital signal packet from that node and transmitting at least a portion of that digital signal packet for storage in that memory element, or

(ii) receiving at least a portion of a digital signal packet from that memory element and transmitting a digital signal packet, including at least that portion, to that node,

B. memory management means coupled to the memory elements of said plural processing cells for accessing one or more of said information-representative signals stored therein,

C. at least a requesting one of said processing units including access request means for generating an access-request signal representative of a request for access to an information-representative signal stored in any of said memory elements, said access request means including means for selectively generating said access-request signal to include an ownership-request signal representative of a request for priority access to the requested information-representative signal, wherein said requested information-representative signal can comprise a digital signal packet, or portion thereof, at least the memory element associated with the requesting processing unit including control means for selectively transmitting said access-request signal to said memory management means,

D. said memory management means including memory coherence means responsive to selected ones of said ownership-request signals for

allocating, only within the memory element associated with the requesting processing unit, physical storage space for the requested information-representative signal, wherein that space is the exclusive storage space for the requested information-representative signal with respect to all of said memory elements, and for storing that requested information-representative signal in that exclusive physical storage space.

2. Digital packet switching apparatus according to claim 1, wherein the processing unit of said at one processing cell further comprises

A. means for executing a first sequence of instructions, a first instruction of which comprises a PREFETCH instruction, for

(i) generating a PREFETCH signal representative of a request for transfer of an information-representative signal, or copy thereof, to the memory element associated with that processing unit,

(ii) commencing execution of the remaining instructions of said first sequence,

(iii) selectively transmitting said PREFETCH signal to said memory management element, and

B. said memory management element includes means for responding to said PREFETCH signal for transferring the requested information-representative signal, or a copy thereof, to the memory element associated with the requesting processing unit asynchronously with respect to the execution of the remaining instructions of said sequence by said requesting processing unit.

3. Digital packet switching apparatus according to claim 1, wherein the processing unit of at least one processing cell further comprises

A. means for generating a POST-STORE signal representative of a request for transfer of a copy of an information-representative signal stored in the associated memory element to the memory elements of said other processing cells, and transmitting that POST-STORE signal to said memory management element,

B. said memory management means includes means for responding to said POST-STORE signal for transferring a copy of said selected information-representative signal to said other processing cells for storage in the physical storage space allocated therein for said selected information-representative signal.

8. Digital packet switching apparatus according to any of claims 1 or 4 or 5 or 6 or 7, wherein

A. said plurality of processing cells includes at least a remote processing cell including its owns respective packet processing means coupled to at least one node associated with that cell, and

B. said remote cell further including remote interface means coupled to at least one other said cell for transferring signals between that remote cell and said at least one other said processing cell.

9. Digital packet switching apparatus according to claim 8, wherein

A. said remote cell resides at a point physically remote from others of said plurality of processing cells, and wherein

B. said interface means includes means for transmitting said information-representative signal between said physically remote point and said at least one other processing cell.

10. Digital packet switching apparatus according to claim 9, wherein said remote interface means includes fiber optic transmission media for carrying information-representative signals between said remote cell and said at least one other processing cell.

11. Digital packet switching apparatus according to any of claims 1 or 4 or 5 or 6 or 7, wherein said packet processing means of at least a selected one of said processing cells comprises

A. packet receive means, in communication with at least one of said nodes associated with that processing cell, for receiving said digital signal packets therefrom,

B. packet splitter means, in communication with said packet receive means, for splitting each said digital signal packet received from at least one of said nodes into a header portion and a data portion,

C. packet receive buffer means, including a buffer element in electrical communication with said packet splitter means, for storing at least portions of said digital signal packets split by said packet splitter means, and

D. frame processing means, in communication with said packet receive buffer means and said plurality of memory elements, for retrieving at least portions of said digital signal packets from said packet receive buffer means, executing selected processing on at least those portions of said digital signal packets, and transmitting at least those portions of said digital signal packets to said memory element of at least one of said plurality of processing cells.

12. Digital packet switching apparatus according to claim 11, wherein said packet processing means further comprises error checking means for checking said received digital signal packets for errors, and for storing results of said checking operation with said header portions of said received digital signal packets.

13. Digital packet switching apparatus according to claim 11, wherein at least one selected processing cell comprises

A. receive queue means for storing in the memory element of at least one of said plurality of processing cells at least one receive queue, said at least one receive queue comprising a data structure including at least portions of digital signal packets received from said packet processing means,

B. transmit queue means for storing in said the memory element at least one of said plurality of processing cells a transmit queue, said at least one transmit queue comprising a data structure including at least portions of digital signal packets to be transmitted to at least a selected one of said nodes, said at least one transmit queue corresponding to at least one of said nodes, and

C. receive queue packet transfer means, in communication with said receive queue means and said transmit queue means, for selectively transferring at least portions of selected digital signal packets from said at least one receive queue to at least a selected transmit queue, responsive to control signals generated by said plurality of processing units, and

D. said frame processing means further comprises means for loading at least portions of selected ones of said digital signal packets into said at least one receive queue.

14. Digital packet switching apparatus according to claim 13, wherein said at least one selected processing cell comprises

A. application service queue means for storing an application service queue, said application service queue comprising a data structure including at least portions of digital signal packets to be serviced by ones of said plurality of processing cells in accordance with at least one application program, and

B. means for loading at least portions of selected ones of said digital signal packets from said at least one receive queue into said at least one application service queue, responsive to control signals generated by ones of said plurality of processing units in accordance with said at least one application program.

15. Digital packet switching apparatus according to claim 14, wherein said at least one selected processing cell further comprises

A. application completion queue means for storing an application completion queue, said application complete queue comprising a data structure including at least portions of digital signal packets generated by ones of said plurality of processing cells in accordance with said at least one application program, and

B. means for loading at least portions of selected ones of said digital signal packets from said application completion queue into said at least one transmit queue.

16. Digital packet switching apparatus according to claim 13, wherein said at least one selected processing cell comprises means for enabling any of said plurality of processing units to retrieve at least one selected digital signal packet from said at least one receive queue for processing.

17. Digital packet switching apparatus according to claim 13, wherein

A. said frame processing means further comprises means, in communication with said transmit queue means, for retrieving at least portions of digital signal packets from said at least one transmit queue, responsive to said header portion of said digital signal packets, and

B. said packet processing means further comprises packet transmit buffer means, including a buffer element in communication with said frame processing means, for storing at least portions of said digital signal packets retrieved by said frame processing means, and

C. packet transmit means, in communication with said packet transmit buffer means and at least one of said nodes, for transmitting said digital signal packets stored in said packet buffer means to at least one of said nodes.

18. Digital packet switching apparatus according to claim 11, wherein said at least one selected processing cell comprises

A. transmit queue means for storing in said plurality of memory elements at least one transmit queue, said at least one transmit queue comprising a data structure including at least portions of digital signal packets to be transmitted to at least a selected one of said nodes, said at least one transmit queue corresponding to at least one of said nodes, and

B. said frame processing means further comprises direct packet transfer means, in communication with said packet receive buffer means, and responsive to said header portion of said digital packets, for transferring at least portions of selected digital signal packets from said packet receive buffer means to said at least one transmit queue.

4. Digital packet switching apparatus for selectively switching digital signal packets between a set of nodes, said digital signal packets being configured in accordance with a selected protocol, the apparatus comprising

A. a plurality of information transfer domains each including one or more segments, said plurality of information transfer domains including a first information transfer domain having a plurality of domain(0) segments, each including an associated bus element and a first plurality of processing cells connected to said bus element for transferring information-representative signals therebetween,

B. each of said processing cells being associated with at least one of said nodes, and including

a processing unit and an associated memory element for storing information-representative signals, said information-representative signals, including digital signal packets, or portions thereof,

means for identifying each said information-representative signal stored in the associated memory with a corresponding SVA identifier,

packet processing means, coupled to at least one of the nodes associated with that processing cell and to at least the memory element of that processing cell, for at least one of

(i) receiving a digital signal packet from that node and transmitting at least a portion of that digital signal packet for storage in that memory element, or

(ii) receiving at least a portion of a digital signal packet from that memory element and transmitting a digital signal packet, including at least that portion, to that node,

C. at least a requesting one of said processing units including means for generating an access-request signal representative of a request for access to an information-representative signal stored in a memory element of any other of said processing cells, wherein said requested information-representative signal can comprise a digital signal packet, or portion thereof, and said access-request signal including an identifier component representative of the SVA identifier of the requested information-representative signal, said requesting processing cell including means for transmitting that access-request signal on the associated domain(0) bus element,

D. said plurality of information transfer domains further including a second information transfer domain having a domain(1) segment comprising an associated bus element and a plurality of routing elements, each said routing element being connected to the bus element associated with the domain(1) segment and to the bus element associated with one of said domain(0) segments for transferring signals therebetween, and

E. each said routing element including directory means for storing SVA identifier signals of information-representative signals stored in memory elements of the processing cells of the associated domain(0) segment, and further including means for receiving an access-request signal transferred along any one of the bus element of the domain(1) segment and the bus element of the associated domain(0) segment for selectively transmitting that access-request signal along the bus element associated with the other of those bus elements based on a comparison of the identifier component of that access-request signal with said SVA identifier signals in said directory element.

5. Digital packet switching apparatus for selectively switching digital signal packets between a set of nodes, said digital signal packets being configured in accordance with a selected protocol, the apparatus comprising

A. a plurality of interconnected processing cells, each associated with at least one of said nodes, and each including storage means for storing instructions and data, said storage means including

a first instruction source for storing instructions and for generating an instruction stream including a plurality of said instructions,

a memory element for storing information-representative signals, including digital signal packets or portions thereof,

a processing unit, coupled to at least said first instruction source for normally processing the instruction stream generated thereby,

B. at least one of said processing units including packet processing means, coupled to at least one of the nodes associated with that processing cell and to at least the memory element of that processing cell, for at least one of

(i) receiving a digital signal packet from that node and transmitting at least a portion of that digital signal packet for storage in that memory element, or

(ii) receiving at least a portion of a digital signal packet from that memory element and transmitting a digital signal packet, including at least that portion, to that node,

C. said packet processing means including insert means for generating control instructions and for applying those control instructions to said processing unit to be processed thereby to at least one of

(i) initiate the transfer of at least portions of digital signal packets from that packet processing means to the memory element of the associated processing cell,

(ii) initiate the transfer of at least portions of digital signal packets from the memory element of the associated processing cell to that packet processing means,

(iii) transfer at least portions of digital signal packets between the memory element of the associated processing cell and the memory element of another processing cell,

D. said control instructions being processed by said processing unit in the same manner as, and without affecting processing sequence of, the instructions from the first instruction source.

6. Digital packet switching apparatus for selectively switching digital signal packets between a set of nodes, said digital signal packets being configured in accordance with a selected protocol, the apparatus comprising

A. plural processing cells, each being associated with at least one of said nodes, and including

a processing unit coupled to an associated memory element for storing information-representative signals, including digital signal packets, or portions thereof, said information-representative signals being arranged in data subpages, plural ones of which data subpages comprise a data page

packet processing means, coupled to at least one of the nodes associated with that processing cell and to at least the memory element of that processing cell, for at least one of

(i) receiving a digital signal packet from that node and transmitting at least a portion of that digital signal packet for storage in that memory element, or

(ii) receiving at least a portion of a digital signal packet from that memory element and transmitting a digital signal packet, including at least that portion, to that node,

B. at least one of said processing units including access request means for generating an access-request signal representative of a request for access to a data subpage stored in one or more of said memory elements, wherein said requested data subpage can comprise a digital signal packet, or portion thereof, at least the memory element of the requesting processing unit including control means for selectively transmitting said access-request signal to a memory management means,

C. said memory management means, being coupled to said processing cells, for accessing information-representative signals stored in said memory elements there of, said memory management means including means responsive to at least selected ones of said access-request signals for

allocating, only within the memory element associated with the requesting processing unit, physical storage space for the data page associated with the requested data subpage, wherein that space is the exclusive physical storage space for that data page with respect to all of said memory elements, and for

storing the requested data subpage in that allocated physical storage space.

7. Digital packet switching apparatus for selectively switching digital signal packets between a set of nodes, said digital signal packets being configured in accordance with a selected protocol, the apparatus comprising

A. a plurality of information transfer domains each including one or more segments, said plurality of information transfer domains including a first information transfer domain having a plurality of domain(0) segments, each including an associated bus element and a first plurality of processing cells connected to said bus element for transferring information-representative signals therebetween,

B. each of said processing cells being associated with at least one of said nodes, and each including storage means for storing instructions and data, said storage means including

a first instruction source for storing instructions and for generating an instruction stream including a plurality of said instructions,

a memory element for storing information-representative signals, including digital signal packets or portions thereof,

a processing unit, coupled to at least said first instruction source, for normally processing the instruction stream generated thereby, packet processing means, coupled to at least one of the nodes associated with that processing cell and to at least the memory element of that processing cell, for at least one of

(i) receiving a digital signal packet from that node and transmitting at least a portion of that digital signal packet for storage in that memory element, or

(ii) receiving at least a portion of a digital signal packet from that memory element and transmitting a digital signal packet, including at least that portion, to that node,

C. said packet processing means including insert means for generating control instructions and for applying those control instructions to said processing unit to be processed thereby to at least one of

(i) initiate the transfer of at least portions of digital signal packets from the packet processing means to the memory element of the associated processing cell,

(ii) initiate the transfer of at least portions of digital signal packets from the memory element of the associated processing cell to that packet processing means,

(iii) generating an access-request signal representative of a request for transfer of an information-representative signal stored in the memory element of the associated processing cell with the memory element of another said processing cells, wherein the information-representative signal requested for transfer can comprise a digital signal packet, or portion thereof,

D. said control instructions being processed by said processing unit in the same manner as, and without affecting processing sequence of, the instructions from the first instruction source, and

E. said requesting processing cell including means for transmitting that access-request signal on the associated domain(0) bus element, said plurality of information transfer domains further including a second information transfer domain having a domain(1) segment comprising an associated bus element and a plurality of routing elements, each said routing element being connected to the bus element associated with the domain(1) segment and to the bus element associated with one of said domain(0) segments for transferring signals therebetween.

19. A method of operating a digital packet switching apparatus for selectively switching digital signal packets between a set of nodes, said digital signal packets being configured in accordance with a selected protocol, said method including the steps of

A. providing plural processing cells, each being associated with at least one of said nodes and each including a processing unit coupled to an associated memory element for storing information-representative signals, including digital signal packets, or portions thereof,

B. selectively executing, within at least one of said processing cells, any of

(i) receiving a digital signal packet from a node associated with that processing cell and transmitting at least a portion of that digital signal packet for storage in the memory element of that processing cell, or

(ii) receiving at least a portion of a digital signal packet from the memory element of that processing cell and transmitting a digital signal packet, including at least that portion, to at least one of said nodes associated with that cell,

C. generating within a requesting one of said processing units an ownership-request signal representative of a request for priority access to an information-representative signal stored in the memory element of any of said processing cells, wherein said requested information-representative signal can comprise a digital signal packet, or portion thereof,

D. determining whether the requested information-representative signal is stored within a memory element other than one associated with the requesting processing unit, and responding to a determination that the requested information-representative signal is stored in a memory element other than the one associated with the requesting processing unit for

allocating, only within the memory element associated with the requesting processing unit, physical storage space for the requested information-representative signal, wherein that space is the exclusive physical storage space for the requested information-representative signal with respect to all of said memory elements, and

storing the requested information-representative signal in that exclusive physical storage space.