Method of routing packet

• US 7,697,438 B2
• Filed: 05/12/2004
• Issued: 04/13/2010
• Est. Priority Date: 05/12/2004
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Porter, George M., Ji, Minwen
• Primary Examiner(s): Moe; Aung S
• Assistant Examiner(s): Mered; Habte
• Application Number:
  US10/844,902
• Publication Number:
  US 20050267985A1
• Time in Patent Office: 2,162 Days
• Field of Search: 370/230, 370/231, 370254-256, 370/468, 370/235, 370/237, 370/238, 370351-356, 709/222, 709238-241
• US Class Current: 370/238
• 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/121 by minimising delays
• CPC Class Codes: H04L 45/38 Flow based routing

Abstract

An embodiment of a method of routing a packet between nodes of a network begins with a step of determining that a route of an external network from a source node to a network node provides an expected near minimum transmission time for transmission of the packet from the source node to a destination node. The method continues with a step of determining that a packet queue for a network link at a source node exceeds a threshold. The method concludes with a step of routing the packet to the destination node via the external network and the network node.

Claims

1. A method of routing a packet between nodes of a network comprising the steps of:

determining a base routing transmission time between each of a plurality of nodes and a destination node, the base routing transmission times being for routes within a restricted access network;

using a computer-based source node to identify, as candidate nodes, nodes having base routing transmission times that are shorter than a routing transmission time of the source node;

collecting external routing transmission times for routes through a shared access external network, the shared access external network being connected to the restricted access network;

using the computer-based source node to, for each candidate node, sum its base routing transmission time with a corresponding external routing transmission time to identify a particular network node that provides an expected near minimum transmission time for transmission of the packet from the source node to the destination node;

determining that a packet queue for a network link at the source node exceeds a threshold; and

routing the packet to the destination node via the shared access external network and the particular network node if the threshold is exceeded.

2. The method of claim 1 wherein the route of the shared access external network by which the packet is routed comprises a local tunnel.

3. The method of claim 2 wherein the step of routing the packet to the destination node comprises routing the packet via the local tunnel and a base route from the particular network node to the destination node.

4. The method of claim 1 wherein the network and the shared access external network comprise a hybrid network.

5. The method of claim 1 wherein the packet comprises a particular packet of a 2 stream of packets.

6. The method of claim 5 wherein the step of routing the packet to the destination node via the shared access external network and the particular network node further comprises routing one or more other packets of the stream of packets via the shared access external network and the particular network node.

7. The method of claim 1 wherein the restricted access network comprises an intranet.

8. The method of claim 1 wherein the restricted access network comprises a private network.

9. The method of claim 1 wherein the expected near minimum transmission time comprises an expectation based upon a delay at the source node.

10. The method of claim 1 wherein the expected near minimum transmission time comprises an expectation based upon a loss of the packet at the source node.

11. The method of claim 1 wherein the particular network node comprises the destination node.

12. The method of claim 1 wherein the step of collecting external routing transmission times comprises occasionally measuring transmission times from the source node to candidate nodes.

13. The method of claim 1 wherein the step of routing the packet further comprises routing additional packets to the destination node via the shared access external network and the particular network node.

14. The method of claim 1 wherein the step of routing the packet to the destination node via the shared access external network and the particular network node comprises avoiding congestion on the network link.

15. The method of claim 14 further comprising the step of determining that communication traffic along a downstream network link exceeds a bandwidth threshold.

16. The method of claim 15 further comprising the step of avoiding the downstream network link.

17. The method of claim 14 wherein the step of routing the packet to the destination 2 node via the shared access external network and the particular network node further comprises making use of available bandwidth for the network beyond the congestion.

18. The method of claim 1 wherein the network comprises gateway nodes that couple the network to the shared access external network.

19. The method of claim 18 wherein the gateway nodes include the source node and the particular network node.

20. The method of claim 18 wherein the shared access external network comprises an Internet.

21. The method of claim 20 wherein the step of routing the packet to the destination node via the shared access external network and the particular network node uses a secure tunnel from the source node to the particular network node.

22. The method of claim 21 wherein the secure tunnel utilizes encryption.

23. The method of claim 21 wherein the secure tunnel utilizes authentication.

24. The method of claim 1 wherein the packet comprises at least a portion of a non-critical communication.

25. A method of routing a packet between nodes of a network comprising the steps of:

determining a base routing transmission time between each of a plurality of nodes and a destination node, the base routing transmission times being for routes within a restricted access network;

using a computer-based source node to identify, as candidate nodes, nodes having base routing transmission times that are shorter than a routing transmission time of the source node;

determining that a downstream network link not connected to the source node exceeds a bandwidth threshold;

collecting external routing transmission times for routes through a shared access external network, the shared access external network being connected to the restricted access network;

using the computer-based source node to, for each candidate node, sum its base routing transmission time with a corresponding external routing transmission time to identify a particular network node that provides an expected near minimum transmission time for transmission of the packet from the source node to the destination node and that avoids the downstream network link;

determining that a packet queue for a network link at the source node exceeds a threshold; and

routing the packet to the destination node via the shared access external network and the particular network node if the threshold is exceeded at the source node.

26. The method of claim 25 wherein the network comprises gateway nodes that couple the network to the external network.

27. The method of claim 25 wherein the step of routing the packet to the destination node via the external network and the particular network node uses a secure tunnel from the source node to the particular network node.

28. The method of claim 25 further comprising a step of avoiding the downstream network link by eliminating from consideration any candidate node for which the network link is in corresponding route within the restricted access network.

29. A computer readable memory having stored thereon computer code which when executed implements a method of routing a packet between nodes of a network, the method of routing the packet comprising the steps of:

determining a base routing transmission time between each of a plurality of nodes and a destination node, the base routing transmission times being for routes within a restricted access network;

identifying, as candidate nodes, nodes having base routing transmission times that are shorter than a routing transmission time of a source node;

collecting external routing transmission times for routes through a shared access external network, the shared access external network being connected to the restricted access network;

for each candidate node, summing its base routing transmission time with a corresponding external routing transmission time to identify a particular network node that provides an expected near minimum transmission time for transmission of the packet from the source node to the destination node;

determining that a packet queue for a network link at the source node exceeds a threshold; and

routing the packet to the destination node via the shared access external network and the particular network node if the threshold is exceeded.

30. A computer readable memory having stored thereon computer code which when executed implements a method of routing a packet between nodes of a network, the method of routing the packet comprising the steps of:

determining a base routing transmission time between each of a plurality of nodes and a destination node, the base routing transmission times being for routes within a restricted access network;

identifying, as candidate nodes, nodes having base routing transmission times that are shorter than a routing transmission time of a source node;

determining that a downstream network link not connected to the source node exceeds a bandwidth threshold;

collecting external routing transmission times for routes through a shared access external network, the shared access external network being connected to the restricted access network;

for each candidate node, summing its base routing transmission time with a corresponding external routing transmission time to identify a particular network node that provides an expected near minimum transmission time for transmission of the packet from the source node to the destination node and that avoids the downstream network link;

determining that a packet queue for a network link at the source node exceeds a threshold; and

routing the packet to the destination node via the external network and the particular network node if the threshold is exceeded at the source node.