Packet network route selection method and apparatus using a bidding algorithm

• US 6,487,172 B1
• Filed: 12/29/1998
• Issued: 11/26/2002
• Est. Priority Date: 08/21/1998
• Status: Expired due to Term

• Current Assignee: Avaya Management L.P. (Avaya Incorporated), Clontech Laboratories Incorporated (Ningbo Junsheng Investment Group Co., Ltd.)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Zonoun, Mohammad Reza
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Yin, Lu
• Application Number:
  US09/222,481
• Time in Patent Office: 1,428 Days
• Field of Search: 370/238, 370/396, 370/432, 370/412, 370/400, 370/449
• US Class Current: 370/238
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation

Abstract

A technique for providing a method and apparatus for selecting a route to a destination for a data packet based on routing metrics received in response to a bid broadcast on a network.

Claims

1. A method of selecting a route to a destination for a data packet comprising:

broadcasting a request for a bid to transfer the data packet on a network where there are more than one path to the destination;

receiving at least one bid in response to the broadcast request, the bid including a routing metric associated with the transfer of the packet to the destination through a particular path;

selecting a desired path to the destination based on the received routing metric.

2. The method of claim 1 wherein the receiving of the routing metric includes a cost value which specifies a cost of transporting the packet to the destination.

3. The method of claim 1 wherein the receiving of the routing metric includes a delay value which specifies a time duration required for transporting the packet to the destination.

4. The method of claim 1 wherein the receiving of the routing metric includes a cost value which specifies a cost in monetary terms of transporting the packet to the destination and a delay value which specifies a time duration required for transporting the packet to the destination, and the selecting of the desired path is based on the cost and delay values for a type of data packet being transferred.

5. The method of claim 1 wherein the broadcasting of the request for the bid is for transferring a plurality of packets.

6. The method of claim 1 further comprises the resolving of a contention for the packet when more than one bid is received, wherein the received routing metrics are analyzed based on established parameters for the selecting of a winning bid for the desired path to the destination.

7. A method of selecting a route to a destination for a data packet comprising:

broadcasting a request for a bid to transfer the data packet on a network where there are multiple paths to the destination through multiple systems on the network for transporting the packet;

receiving bids in response to the broadcast request, each bid including a routing metric associated with the transfer of the packet to the destination through a particular path;

analyzing the received routing metric using established routing parameters;

selecting a desired path to the destination based on the analysis of the received routing metric.

8. The method of claim 7 wherein the receiving of the routing metric includes a cost value which specifies a cost of transporting the packet to the destination.

9. The method of claim 7 wherein the receiving of the routing metric includes a delay value which specifies a time duration required for transporting the packet to the destination.

10. The method of claim 7 wherein the receiving of the routing metric includes a cost value which specifies a cost in monetary tom of transporting the packet to the destination and a delay value which specifies a time duration required for transporting the packet to the destination, and the selecting of the desired path is based on the cost and delay values for a type of data packet being transferred.

11. The method of claim 7 wherein the broadcasting of the request for the bid is for transferring a plurality of packets.

12. The method of claim 7 further comprises the resolving of a contention for the packet by multiple bids, wherein the analyzing of the received routing metrics is based on the type of data packet being transferred.

13. The method of claim 7 wherein the network is a member of the group consisting of IP, ATM, ETHERNET and SONET.

14. A method of submitting a bid by a border gate on a network for routing of a data packet through the border gate to a destination comprising:

receiving a request for a bid to transfer the data packet through a path which includes the border gate,

determining a routing metric associated with the transfer of the packet to the destination through the border gate;

submitting a bid which includes the routing metric to a sander of the request for a bid.

15. The method of claim 14 wherein the determining of the routing metric includes a cost value which specifies a cost in monetary terms of transporting the packet to the destination.

16. The method of claim 14 wherein the determining of the routing metric includes a delay value which specifies a time duration required for transporting the packet to the destination.

17. The method of claim 14 further comprises the incrementing of the routing metric to a downstream routing metric received from a downstream border gate before submitting the bid upstream.

18. A method of submitting a bid by a border gate on a network for routing of a data packet through the border gate to a destination comprising:

receiving a request for a bid from a requester upstream to transfer the data packet through a path which includes the border gate;

rebroadcasting the request for a bid downstream towards the destination if another border gate resides in the path prior to reaching the destination;

determining a routing metric associated with the transfer of the packet from up to the border gate;

receiving a downstream bid, which includes a downstream routing metric, from a downstream gateway;

incrementing the routing metric to the downstream routing metric received;

submitting a bid based on the routing metric or a cumulative of the routing metric and the downstream routing metric to an upstream sender of the request for the bid.

19. The method of claim 18 wherein the determining of the routing metric and the downstream routing metric if there is one, includes a cost value in monetary terms which specifies a cost of transporting the packet to the destination.

20. The method of claim 18 wherein the determining of the routing metric and the downstream routing metric if there is one, includes a delay value which specifies a time duration required for transporting the packet to the destination.

21. The method of claim 18 wherein the receiving of the request for the bid is for transferring a plurality of packets.

22. A machine readable medium having resident thereon programmed instructions for selecting a route to a destination for a data packet on a network, the instructions when executed by a processor, causes the processor to perform comprising:

broadcasting a request for a bid to transfer the data packet on the network where there are more than one path to the destination;

receiving at least one bid in response to the broadcast request, the bid including a routing metric associated with the transfer of the packet to the destination through a particular path;

selecting a desired path to the destination based on the received routing metric.

23. The machine readable medium of claim 22 wherein the receiving of the routing metric includes a cost value in monetary terms which specifies a cost of transporting the packet to the destination.

24. The machine readable medium of claim 22 wherein the receiving of the routing metric includes a delay value which specifies a time duration required for transporting the packet to the destination.

25. The machine readable medium of claim 22 wherein the receiving of the routing metric includes a cost value which specifies a cost of transporting the packet to the destination and a delay value which specifies a time duration required for transporting the packet to the destination, and the selecting of the desired path is based on the cost and delay values for a type of data packet being transferred.

26. The machine readable medium of claim 22 wherein the broadcasting of the request for the bid is for transferring a plurality of packets.

27. The machine readable medium of claim 22 further comprises the resolving of a contention for the packet when more than one bid is received, wherein the received routing metrics are analyzed based on established parameters for the selecting of a winning bid for the desired path to the destination.

28. A machine readable medium having resident thereon programmed instructions for submitting a bid by a border gate on a network for routing of a data packet through the border gate to a destination, the instructions when executed by a processor, causes the processor to perform comprising:

receiving a request for a bid to transfer the data packet through a path which includes the border gate;

determining a routing metric associated with the transfer of the packet to the destination through the border gate;

submitting a bid which includes the routing metric to a sender of the request for a bid.

29. The machine readable medium of claim 28 wherein the determining of the routing metric includes a cost value in monetary terms which specifies a cost of transporting the packet to the destination.

30. The machine readable medium of claim 28 wherein the determining of the routing metric includes a delay value which specifies a time duration required for transporting the packet to the destination.

31. The machine readable medium of claim 28 further comprises the incrementing of the routing metric to a downstream routing metric received from a downstream border gate before submitting the bid upstream.

32. An apparatus for selecting a route to a destination for a data packet comprising:

a processor;

a table in memory for storing a metric value, said memory coupled to said processor,

said processor broadcasting a request for a bid to transfer the data packet on a network where there are more than one path to the destination and receiving at least one bid in response to the broadcast request, the bid including the routing metric associated with the transfer of the packet to the destination through a particular path, in which the routing metric is stored in said table;

said processor selecting a desired path to the destination based on the received routing metric.

33. The apparatus of claim 32 wherein the routing metric includes a cost value in monetary terms which specifies a cost of transporting the packet to the destination.

34. The apparatus of claim 32 wherein the routing metric includes a delay value which specifies a time duration required for transporting the packet to the destination.

35. The apparatus of claim 32 wherein said processor further resolves a contention for packet when more than one bid is received, wherein the received routing metrics are analyzed based on established parameters in order for said processor to select a winning bid for the desired path to the destination.

36. A border gate for submitting a bid on a network for routing of a data packet to a destination comprising:

a processor;

a table in memory for storing a metric value, said memory coupled to said processor;

said processor receiving a request for a bid transfer the data packet through a path which includes the border gate and determining its routing metric associated with the transfer of the packet to the destination through the border gate;

said processor weaving a downstream routing metric from a downstream border gate and storing the downstream routing metric in said table;

said processor incrementing its routing metric to the stored downstream routing metric and submitting an incremented result as a bid upstream to a sender of the request for a bid.

37. The border gate of claim 36 when the routing metric includes a cost value in monetary terms which specifies a cost of transporting the packet to the destination.

38. The border gate of claim 36 wherein the determining of the routing metric includes a delay value which specifies a time duration required for transporting the packet to the destination.

39. The border gate of claim 36 in which the submitted bid is in response to a request for transferring a plurality of packets.