Scalable parallel packet router

• US 6,044,080 A
• Filed: 11/19/1996
• Issued: 03/28/2000
• Est. Priority Date: 11/19/1996
• Status: Expired due to Term

• Current Assignee: Parity Networks LLC
• Original Assignee: Pluris, Inc
• Inventors: Antonov, Vadim
• Primary Examiner(s): Patel, Ajit
• Assistant Examiner(s): SLAVITT, MITCHELL R
• Application Number:
  US08/752,479
• Time in Patent Office: 1,225 Days
• Field of Search: 370/400, 370/366, 370/382, 370/384, 370/401, 370/398, 370/402, 370/403, 370/405, 370/411, 370/413, 370/389, 370/227, 370/235, 370/370, 395/200.7, 395/200.74, 395/200.51, 395/200.55, 395/800.13, 395/800.18, 714/7
• US Class Current: 370/401
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 2012/5645 Connectionless
• CPC Class Codes: H04L 2012/565 Sequence integrity
• CPC Class Codes: H04L 2012/5672 Multiplexing, e.g. coding, scrambling
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A scalable parallel packet router comprises a massively parallel computer 10 and a plurality of multiplexers 15, and is controlled by a disclosed packet routing algorithm, and a method of very high-speed packet routing. The method includes selection of an destination node by computing a hash function from source and destination addresses of a packet, so the ordering of packets is preserved.

Claims

1. A device for routing data packets between high-speed communication lines, comprising:

a data interconnect circuit;

a first processing node that receives data packets from a first high-speed communication line and is adapted to forward data packets via said data interconnect circuit;

second and third processing nodes each adapted to receive data packets from said first processing node via said data interconnect circuit;

first and second low-speed communication lines respectively coupled to said second and third processing nodes; and

a multiplexer having at least two input ports, said multiplexer being adapted to send data packets over a second high-speed communication line, said sent data packets being received via said at least two input ports, said first and second low-speed communication lines being respectively coupled to said at least two input ports,

said first, second, and third processing nodes being operative such that a first stream of data packets having a plurality of different sources and destinations are routed from said first high-speed communication line to said second high-speed communication line via a uniform distribution of said first and second low-speed communication lines, while a second stream of data packets each having the same source and destination are routed from said first high-speed communication line to said second high-speed communication line via only one of said first and second low-speed communication lines.

2. A device as defined in claim 1, wherein said first processing node determines which of said second and third processing nodes to forward data packets to in accordance with a hash algorithm performed using said sources and destinations.

3. A device as defined in claim 1, wherein said first and second low-speed communication lines have an aggregate capacity greater than or equal to a capacity of said second high-speed communication line.

4. A device as defined in claim 1, wherein said data interconnect circuit is linearly scalable in accordance with a total number of processing nodes coupled thereto.

5. A device as defined in claim 1, wherein said sources and destinations are derived from source and destination addresses of said data packets.

6. A device as defined in claim 1, wherein said sources and destinations are derived from source and destination addresses and source and destination ports of said data packets.

7. A device as defined in claim 1, further comprising:

third and fourth low-speed communication lines respectively coupled to said second and third processing nodes; and

a second multiplexer having at least two second input ports, said second multiplexer being adapted to send data packets over a third high-speed communication line, said sent data packets being received via said at least two second input ports, said third and fourth low-speed communication lines being respectively coupled to said at least two second input ports,

said first, second, and third processing nodes being operative such that a third stream of data packets having a plurality of different sources and destinations are routed from said first high-speed communication line to said third high-speed communication line via a uniform distribution of said third and fourth low-speed communication lines, while a fourth stream of data packets each having the same source and destination are routed from said first high-speed communication line to said third high-speed communication line via only one of said third and fourth low-speed communication lines.

8. A device as defined in claim 1, further comprising:

fourth and fifth processing nodes each adapted to receive data packets from said first processing node via said data interconnect circuit;

third and fourth low-speed communication lines respectively coupled to said fourth and fifth processing nodes; and

a second multiplexer having at least two second input ports, said second multiplexer being adapted to send data packets over said second high-speed communication line, said sent data packets being received via said at least two second input ports, said third and fourth low-speed communication lines being respectively coupled to said at least two second input ports,

said first, second, third and fourth processing nodes being operative such that a third stream of data packets having a plurality of different sources and destinations are routed from said first high-speed communication line to said second high-speed communication line via a uniform distribution of said first, second, third and fourth low-speed communication lines, while a fourth stream of data packets each having the same source and destination are routed from said first high-speed communication line to said second high-speed communication line via only one of said first, second, third and fourth low-speed communication lines.

9. A device for routing data packets between first and second high-speed communication lines, comprising:

a first multiplexer having at least two output ports, said first multiplexer being adapted to receive data packets from said first high-speed communication line, and to send said received data packets via said at least two output ports;

first and second low-speed communication lines respectively coupled to said at least two output ports;

first and second processing nodes respectively coupled to said first and second low-speed communication lines;

a data interconnect circuit;

third and fourth processing nodes each adapted to receive data packets from said first and second processing nodes via said data interconnect circuit;

third and fourth low-speed communication lines respectively coupled to said third and fourth processing nodes; and

a second multiplexer having at least two input ports, said second multiplexer being adapted to send packets over said second high-speed communication line, said sent data packets being received via said at least two input ports, said third and fourth low-speed communication lines being respectively coupled to said at least two input ports,

said first and second multiplexers and said first, second, third and fourth processing nodes being operative such that a first stream of data packets having a plurality of different sources and destinations are routed from said first high-speed communication line to said second high-speed communication line via a uniform distribution of said first, second, third and fourth low-speed communication lines, while a second stream of data packets each having the same source and destination are routed from said first high-speed communication line to said second high-speed communication line via only one of said third and fourth processing nodes.

10. A method for routing data packets between a plurality of high-speed communication lines in a data packet routing device, said method comprising:

receiving a data packet from a source high-speed communication line at a source multiplexer;

sending the data packet from the source multiplexer to a source network interface via a source low-speed communication line;

receiving the data packet at a source processing node;

determining from a destination address of the data packet a destination high-speed communication line and a destination multiplexer;

determining a number of multiplexer ports associated with the destination multiplexer;

selecting a destination multiplexer port, wherein the selecting step comprises the step of computing a function from a plurality of arguments comprising a source address of the data packet and the destination address of the data packet;

determining a destination processing node and a destination network interface associated with the destination processing node, wherein the destination network interface is connected to the selected destination multiplexer port by a low-speed communication line;

forwarding the data packet to the destination processing node; and

sending the data packet to the destination high-speed communication line via the destination network interface, the low-speed communication line, and the destination multiplexer.

11. A method as defined in claim 10, wherein the function computing step comprises:

determining from the destination address of the data packet the destination high-speed communication line and the destination multiplexer;

calculating a value based on the source address and the destination address; and

converting the value to a destination port number within a range of values corresponding to the number of ports of the multiplexer.

12. A method as defined in claim 11, wherein the calculating step comprises evaluating a hash function.

13. A method as defined in claim 11, wherein the value is calculated additionally based on a source port number of the data packet and a destination port number of the data packet.

14. A method as defined in claim 10, further comprising:

forwarding the data packet directly to the destination network interface if the determined destination processing node is the same as the source processing node.

15. A method as defined in claim 10, wherein the forwarding step comprises passing the data packet through a data interconnect circuit.

16. A method of forwarding packets between high-speed communication lines in a packet router device, said packet router device comprising a linearly scalable data interconnect circuit, a first processing node that receives data packets from a first high-speed communication line and is adapted to forward received data packets via said data interconnect circuit, a plurality of second processing nodes each adapted to receive data packets from said first processing node via said data interconnect circuit, a plurality of multiplexers respectively adapted to send data packets over a plurality of second high-speed communication lines, and a plurality of low-speed communication lines coupled between said second processing nodes and said multiplexers, said method comprising:

receiving a data packet from said first high-speed communication line at said first processing node;

determining from a destination address of said data packet a destination one of said second high-speed communication lines and a destination one of said multiplexers;

computing a function from a plurality of arguments including a source address of said data packet and said destination address of said data packet, said function returning a first value equal to a value returned for another source address and another destination address when said source and destination addresses are the same as said another source and destination addresses, said function returning a second value different than said first value when said source and destination addresses are different than said another source and destination addresses;

determining a destination one of said processing nodes connected to said destination multiplexer by one of said low-speed communication lines based on a returned value of said function;

forwarding said data packet to said destination processing node via said data interconnect circuit; and

sending said data packet to said destination high-speed communication line via said connected low-speed communication line and said destination multiplexer.

17. A method as defined in claim 16, wherein said function computing step comprises:

determining a number of said low-speed communication lines connected to said destination multiplexer;

calculating a value based on said source address and said destination address of said data packet; and

converting said value to said returned value, said returned value being within a range corresponding to said number of said low-speed communication lines.

18. A method as defined in claim 17, wherein said destination processing node determining step includes:

identifying connected ones of said processing nodes associated with said number of said low-speed communication lines; and

selecting one of said connected ones of said processing nodes based on said returned value.

19. A method as defined in claim 16, wherein said function computing step comprises evaluating a hash function.

20. A method as defined in claim 16, wherein said plurality of arguments further includes a source port number of said data packet and a destination port number of said data packet.

21. A method as defined in claim 16, wherein said packet router device further includes an ingress multiplexer adapted to receive data packets from said first high-speed communication line, a plurality of ingress low-speed communication lines, said ingress multiplexer being adapted to send said data packets to processing nodes via said ingress low-speed communication lines, said first processing node being coupled to said ingress multiplexer via one said ingress low-speed communication lines, said method further comprising:

receiving ingress data packets at said ingress multiplexer;

uniformly distributing said ingress data packets among said ingress low-speed communication lines.

22. A method as defined in claim 16, further comprising:

adjusting the throughput of said packet router device, said adjusting step including;

identifying a present throughput of said packet router device; and

adding or removing second processing nodes while connecting or removing corresponding low-speed communication lines between said added or removed second processing nodes and said multiplexer until said present throughput equals or exceeds a desired throughput.