Supertrunking for packet switching

• US 6,587,431 B1
• Filed: 12/18/1998
• Issued: 07/01/2003
• Est. Priority Date: 12/18/1998
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Vincent, John E., Chapman, Alan S. J., Almulhem, Abdulaziz S.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Elallam, Ahmed
• Application Number:
  US09/215,262
• Time in Patent Office: 1,656 Days
• Field of Search: 370/229, 370/230-232, 370/235, 370/237, 370/351, 370/355, 370/389, 370/392, 370/394, 370/395.1, 370/395.3, 370/395.52, 370/400, 370/401, 370/902, 709/105
• US Class Current: 370/229
• 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/24 Multipath
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 370/902 Packet switching

Abstract

A packet routing system is disclosed that allows for efficient transfers of IP streams from router to router with use of supertrunking. The router that receives an IP stream set for transmission on a supertrunk, individually inputs the IP packets, determines the logical output port corresponding to the IP stream, assigns each IP packet to a physical output port within the logical output port with use of a load balancing function, encapsulates each IP packet within a supertrunk header comprising an IP stream identifier and a packet sequence identifier and an IP header that has identical source and destination addresses as the original IP packet, and forwards the encapsulated packets to the receiving router via a plurality of physical links. The router that receives the encapsulated IP packets then re-orders the packets into the proper order with use of a sorting algorithm, removes the IP and supertrunk headers, and outputs an IP stream similar to that input to the original router.

Claims

1. A forwarding node capable of operation within a router that transfers digital data with a plurality of other routers within a packet routing system, the forwarding node comprising:

a load balancing device that, when input with individual packets of a data stream, reads a logical output port corresponding to the data stream, assigns each of the individual packets of the data stream to a physical output port within the logical output port based upon physical link criteria, encapsulates the individual packets with a first routing header that comprises a data stream identifier, a packet sequence identifier, and a physical output port identifier, and outputs the packets to their assigned physical output ports; and

a packet sorting device that, when input with encapsulated packets, re-orders the packets into the proper order with use of a sorting algorithm utilizing the packet sequence identifiers and outputs a data stream corresponding to the re-ordered packets.

2. A forwarding node according to claim 1, wherein the first routing header is a packet forwarding header combined with a rotator information unit header;

and

wherein the packet forwarding header comprises the data stream identifier and the packet sequence identifier, and the rotator information unit header comprises the physical output port identifier.

3. A forwarding node according to claim 1 further comprising a de-encapsulation device that, when input with the data stream corresponding to the re-ordered packets, removes the first routing header from each of the encapsulated packets.

4. A forwarding node according to claim 1 further comprising an encapsulation device that, when input with packets from the load balancing device, removes the first routing header from each of the packets, encapsulates each of the individual packets with a second routing header that comprises a data stream identifier and a packet sequence identifier and outputs the encapsulated packets to transmission apparatuses.

5. A forwarding node according to claim 4, wherein the second routing header is a supertrunk header combined with an Internet Protocol (IP) header;

wherein the supertrunk header comprises the data stream identifier and the packet sequence identifier; and

wherein each of the encapsulated packets is an IP datagram with the supertrunk header and the original packet corresponding to a data section within the IP datagram.

6. A forwarding node according to claim 5, wherein the data streams are Internet Protocol (IP) streams and the individual packets of the data streams are IP packets;

and

wherein the IP header of the second routing header comprises source and destination addresses that are identical to source and destination addresses within an IP header of the particular IP packet.

7. A forwarding node according to claim 4 further comprising a de-encapsulation device that, when input with the data stream corresponding to the re-ordered packets, removes the second routing header from each of the encapsulated packets.

8. A forwarding node according to claim 1, wherein the data streams are Internet Protocol (IP) streams and the individual packets of the data streams are IP packets.

9. A forwarding node according to claim 8, wherein the load balancing device reads the logical output port corresponding to the data streams with use of IP headers attached to the individual IP packets.

10. A forwarding node according to claim 1, wherein the physical link criteria are load link factors calculated for each of the available physical output ports, the load link factors equalling a link speed factor representative of the speed of the particular physical output port multiplied by a queue size representative of the packets already queued within the particular physical output port.

11. A forwarding node according to claim 10, wherein the load balancing device assigns each of the individual packets of the data stream to the physical output port that at the particular time has the lowest load link factor.

12. A forwarding node according to claim 1, wherein the packet sequence identifier is a binary number corresponding to the relative position within the data stream of the particular packet.

13. A forwarding node according to claim 1, wherein the packet sequence identifier is a time stamp corresponding to the relative time that the particular packet was input to the load balancing device.

14. A forwarding node according to claim 1, wherein the data stream identifier is generated by the load balancing device when a packet of a new data stream is detected;

and

wherein all the packets of the data stream are assigned the same data stream identifier with use of a look-up table.

15. A forwarding node according to claim 14, wherein a new data stream is detected with use of an egress context identifier determined with a look-up table.

16. A forwarding node according to claim 1, wherein the sorting algorithm, input with an individual packet of a particular data stream, comprises the steps of:

identifying the particular data stream of the inputted packet with use of the data stream identifier;

determining if the packet is the first packet of the particular data stream to be input to the sorting algorithm;

initializing a buffer memory for the particular data stream, if the packet is the first packet, by placing the packet within a minimum address and setting a minimum variable to the packet sequence identifier of the packet; and

updating the memory buffer for the particular data stream, if the packet is not the first packet, by placing the packet in an address relative to the minimum address based upon the difference between the packet sequence identifier of the packet and the minimum variable, and if the packet sequence identifier of the packet is less than the minimum variable, setting the minimum address to the address of the packet and setting the minimum variable to the packet sequence identifier of the packet.

17. A forwarding node according to claim 16, wherein, if a packet is at the minimum address and a predetermined hold time expires, the packet at the minimum address is output from the packet sorting device, the minimum address is incremented by one, and the predetermined hold time is reset.

18. A forwarding node according to claim 17, wherein, if no packet is at the minimum address and the predetermined hold time expires, the predetermined hold time is reset.

19. A forwarding node according to claim 1 comprising an ingress block that is arranged to input packets from a transmission device and comprises the load balancing device, an egress block that is arranged to output packets to the transmission device and comprises the packet sorting apparatus, and a switch interface, coupled to both the ingress and egress blocks, that is arranged to be coupled to a switch apparatus.

20. A forwarding node according to claim 19, wherein the ingress block comprises an ingress processor coupled in series with an ingress filter and mapper and an ingress port controller that is further coupled to the switch interface, and the egress block comprises an egress queuer coupled to the switch interface and further coupled in series with an egress scheduler and an egress processor;

wherein the ingress port controller comprises the load balancing device and the egress queuer comprises the packet sorting device.

21. A forwarding node according to claim 20, wherein the egress processor comprises an encapsulation device that, when input with packets from the load balancing device, removes the first routing header from each of the packets, encapsulates each of the individual packets with a second routing header that comprises a data stream identifier and a packet sequence identifier and outputs the encapsulated packets to transmission apparatuses.

22. A forwarding node according to claim 21, wherein the egress processor further comprises a de-encapsulation device that, when input with the data stream corresponding to the re-ordered packets, removes the second routing header from each of the encapsulated packets.

23. A router capable of operation within a packet routing system that transfers digital data between a plurality of the routers, the router comprising:

a route controller;

a rotator space switch;

at least one first forwarding node, coupled to both the route controller and the rotator space switch, comprising a load balancing device that, when input with individual packets of a data stream, reads a logical output port corresponding to the data stream, assigns each of the individual packets of the data stream to a physical output port within the logical output port based upon physical link criteria, encapsulates the individual packets with a first routing header that comprises a data stream identifier, a packet sequence identifier, and a physical output port identifier, and outputs the packets to their assigned physical output ports;

at least one second forwarding node, coupled to both the route controller and the rotator space switch, that is arranged to operate as a physical output port for outputting encapsulated packets to at least one transmission apparatus;

at least one third forwarding node, coupled to both the route controller and the rotator space switch, that is arranged to operate as a physical input port for receiving encapsulated packets from at least one transmission apparatus; and

at least one fourth forwarding node, coupled to both the route controller and the rotator space switch, comprising a packet sorting device that, when input with encapsulated packets, re-orders the packets into the proper order with use of a sorting algorithm utilizing the packet sequence identifiers and outputs a data stream corresponding to the re-ordered packets.

24. A router according to claim 23, wherein at least two of the first, second, third, and fourth forwarding nodes are the same forwarding node.

25. A router according to claim 23, wherein the first routing header is a packet forwarding header combined with a rotator information unit header;

and

wherein the packet forwarding header comprises the data stream identifier and the packet sequence identifier, and the rotator information unit header comprises the physical output port identifier.

26. A router according to claim 23, wherein the fourth forwarding node further comprises a de-encapsulation device that, when input with the data stream corresponding to the re-ordered packets, removes the first routing header from each of the encapsulated packets.

27. A router according to claim 23, wherein the second forwarding node comprises an encapsulation device that, when input with packets from the load balancing device, removes the first routing header from each of the packets, encapsulates each of the individual packets with a second routing header that comprises a data stream identifier and a packet sequence identifier and outputs the encapsulated packets to transmission apparatuses.

28. A router according to claim 27, wherein the fourth forwarding node further comprises a de-encapsulation device that, when input with the data stream corresponding to the re-ordered packets, removes the second routing header from each of the encapsulated packets.

29. A router according to claim 27, wherein the third forwarding node comprises a de-encapsulation device that removes the second routing header from each of the encapsulated packets and attaches a third routing header that comprises a data stream identifier, a packet sequence identifier, and a fourth forwarding node identifier.

30. A router according to claim 29, wherein the third routing header is a packet forwarding header combined with a rotator information unit header;

and

wherein the packet forwarding header comprises the data stream identifier and the packet sequence identifier, and the rotator information unit header comprises the fourth forwarding node identifier.

31. A router according to claim 27, wherein the second routing header is a supertrunk header combined with an Internet Protocol (IP) header;

wherein the supertrunk header comprises the data stream identifier and the packet sequence identifier; and

wherein each of the encapsulated packets is an IP datagram with the supertrunk header and the original packet corresponding to a data section within the IP datagram.

32. A packet routing system that transfers digital data between at least one first router and at least one second router, the packet routing system comprising:

the first router comprising;

a first route controller;

a first rotator space switch;

at least one first forwarding node, coupled to both the first route controller and the first rotator space switch, comprising a load balancing device that, when input with individual packets of a data stream, reads a logical output port corresponding to the data stream, assigns each of the individual packets of the data stream to a physical output port within the logical output port based upon physical link criteria, encapsulates the individual packets with a first routing header that comprises a data stream identifier, a packet sequence identifier, and a physical output port identifier, and outputs the packets to their assigned physical output ports;

at least one second forwarding node, coupled to both the first route controller and the first rotator space switch, that is arranged to operate as a physical output port for outputting encapsulated packets to at least one transmission apparatus;

a plurality of transmission apparatuses coupled between the first and second routers; and

the second router comprising;

a second route controller;

a second rotator space switch;

at least one third forwarding node, coupled to both the second route controller and the second rotator space switch, that is arranged to operate as a physical input port for receiving encapsulated packets from at least one transmission apparatus; and

at least one fourth forwarding node, coupled to both the second route controller and the second rotator space switch, comprising a packet sorting device that, when input with encapsulated packets, re-orders the packets into the proper order with use of a sorting algorithm utilizing the packet sequence identifiers and outputs a data stream corresponding to the re-ordered packets.

33. In a packet routing system comprising a plurality of routers, a method of transferring digital data between the routers comprising the steps of:

inputting individual packets of a data stream into a first router;

reading a logical output port corresponding to the data stream of the individual packets;

assigning each of the individual packets of the data stream to a physical output port within the logical output port based upon physical link criteria;

encapsulating each of the individual packets with a first routing header that comprises a data stream identifier, a packet sequence identifier, and a physical output port identifier corresponding to the assigned physical output port;

transmitting each of the encapsulated packets, via their assigned physical output port, to a second router;

re-ordering the resulting packets into the proper order with use of a sorting algorithm utilizing the packet sequence identifiers; and

outputting a data stream corresponding to the re-ordered