Apparatus and method for forwarding encapsulated data packets on a network having multiple links between nodes

• US 20040090919A1
• Filed: 11/04/2003
• Published: 05/13/2004
• Est. Priority Date: 11/24/1999
• Status: Active Grant

• Current Assignee: Parity Networks LLC
• Original Assignee: Sherwood Partners Incorporated
• Inventors: Callon, Ross W., Renwick, John K.
• Granted Patent: US 7,468,978 B2
• Time in Patent Office: Days
• US Class Current: 370/237
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols

Abstract

An apparatus and method for encapsulating and forwarding packets on a network are disclosed. The network can include a first subnetwork such as a virtual private network connected to a larger public network such as the Internet. An encapsulating header is attached to a packet to be transferred across the public network from a source node on the private network to a destination node on the private network, such that the packet can be transferred across the public network. The encapsulating header includes a value which is derived from the private header on the packet used to transfer the packet along the private network. The value is therefore associated with a source/destination pair within the private network. The value can be derived by performing a hash operation on the private network header. After the public network header containing the value derived from the private network header is attached to the packet, it can be forwarded across the public network. A logical operation such as a hash operation can be performed on the public network header to select one of a plurality of possible paths on the public network to forward the packet. As a result, each source/destination pair within the private network will be associated with a path within the public network. Traffic from the private network can therefore be distributed over multiple paths in the public network, thus reducing or eliminating traffic congestion and overload.

Claims

1. A method of transferring a packet of data on a network, said network including a first subnetwork and a second subnetwork, said packet of data being transferred from a source node on the first subnetwork to a destination node on the first subnetwork, the first subnetwork being connected to the second subnetwork such that the packet of data is transferred across the second subnetwork between the source and destination nodes on the first subnetwork, said packet of data having a first header portion which is associated with the source and destination nodes on the first subnetwork, said method comprising:

generating a value derived from the first header portion such that said value is also associated with the source and destination nodes on the first subnetwork;

providing the packet of data with a second header portion, the second header portion including the value derived from the first header portion; and

using the second header portion, selecting one of a plurality of paths on the second subnetwork for forwarding of the packet.

2. The method of claim 1 wherein the first subnetwork is a virtual private network.

3. The method of claim 2 wherein the second subnetwork is a portion of the Internet.

4. The method of claim 1 wherein the second subnetwork is a portion of the Internet.

5. The method of claim 1 wherein the first header portion is an Internet protocol (1P) packet header.

6. The method of claim 5 wherein the second header portion is an IP packet header.

7. The method of claim 1 wherein the first header portion is an Ethernet packet header.

8. The method of claim 7 wherein the second header portion is an IP packet header.

9. The method of claim 1 wherein the second header portion is an IP packet header.

10. The method of claim 1 wherein the value is derived by performing a hash operation on the first header portion.

11. The method of claim 10 wherein the hash operation is performed on information in the first header portion related to addresses of the source and destination nodes.

12. The method of claim 10 wherein the hash operation is performed on a protocol field in the first header portion.

13. The method of claim 10 wherein the hash operation is performed on IP source and destination addresses of the source and destination nodes, respectively.

14. The method of claim 10 wherein the hash operation comprises performing a division on the first header portion.

15. The method of claim 14 wherein the value is related to a remainder generated by the division.

16. The method of claim 10 wherein the hash operation comprises a cyclic redundancy check.

17. The method of claim 10 wherein the hash operation comprises a checksum operation.

18. The method of claim 1 wherein the selecting step comprises performing a hash operation on the second header portion.

19. An apparatus for transferring a packet of data on a network, said network including a first subnetwork and a second subnetwork, said packet of data being transferred from a source node on the first subnetwork to a destination node on the first subnetwork, the first subnetwork being connected to the second subnetwork such that the packet of data is transferred across the second subnetwork between the source and destination nodes on the first subnetwork, said packet of data having a first header portion which is associated with the source and destination nodes on the first subnetwork, said apparatus comprising a processing device for (i) generating a value derived from the first header portion such that said value is also associated with the source and destination nodes on the first subnetwork, (ii) providing the packet of data with a second header portion, the second header portion including the value derived from the first header portion, and, (iii) using the second header portion, selecting one of a plurality of paths on the second subnetwork for forwarding of the packet.

20. The apparatus of claim 19 wherein the processing device is located within a network node between the first subnetwork and the second subnetwork.

21. The apparatus of claim 19 wherein the first subnetwork is a virtual private network.

22. The apparatus of claim 21 wherein the second subnetwork is a portion of the Internet.

23. The apparatus of claim 22 wherein the second subnetwork is a portion of the Internet.

24. The apparatus of claim 19 wherein the first header portion is an Internet protocol (IP) packet header.

25. The apparatus of claim 24 wherein the second header portion is an IP packet header.

26. The apparatus of claim 19 wherein the first header portion is an Ethernet packet header.

27. The apparatus of claim 26 wherein the second header portion is an IP packet header.

28. The apparatus of claim 19 wherein the second header portion is an IP packet header.

29. The apparatus of claim 19 wherein the processing device derives the value by performing a hash operation on the first header portion.

30. The apparatus of claim 29 wherein the hash operation is performed on information in the first header portion related to addresses of the source and destination nodes.

31. The apparatus of claim 29 wherein the hash operation is performed on a protocol field in the first header portion.

32. The apparatus of claim 29 wherein the hash operation is performed on IP source and destination addresses of the source and destination nodes, respectively.

33. The apparatus of claim 29 wherein the hash operation comprises performing a division on the first header portion.

34. The apparatus of claim 33 wherein the value is related to a remainder generated by the division.

35. The apparatus of claim 29 wherein the hash operation comprises a cyclic redundancy check.

36. The apparatus of claim 29 wherein the hash operation comprises a checksum operation.

37. The apparatus of claim 19 wherein, in selecting one of the plurality of paths, the processing device performs a hash operation on the second header portion.