Method and apparatus for improved routing in connectionless networks

• US 7,398,438 B2
• Filed: 03/30/2006
• Issued: 07/08/2008
• Est. Priority Date: 03/30/2006
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Agarwal, Sugam, Kodialam, Muralidharan Sampath, Lakshman, Tirunell V.
• Primary Examiner(s): Ton; David
• Application Number:
  US11/394,356
• Publication Number:
  US 20070263592A1
• Time in Patent Office: 831 Days
• Field of Search: 379/221.06, 370/409, 370/248, 370/396, 370/331, 370/338, 370/254, 370/255, 714/717
• US Class Current: 714/717
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/42 Centralised routing

Abstract

The invention includes a method and apparatus for determining a routing table for use in a network comprising a plurality of type-one nodes and a plurality of type-two nodes where the type-two nodes use respective type-two routing tables having one next-hop node associated with each of a plurality of destination nodes of the network. The method includes obtaining, from the type-one nodes and the type-two nodes, link status information associated with each of a plurality of links of the network, obtaining traffic measurement information from the type-one nodes and the type-two nodes, and determining, using the link status and traffic measurement information, type-one routing tables for the respective type-one nodes. The type-one routing tables are determined as a group in a substantially coordinated manner, and each type one routing table includes a plurality of next-hop nodes associated with each of the destination nodes.

Claims

1. A method for determining a routing table for use in a network comprising a plurality of type-one nodes and a plurality of type-two nodes, the type-two nodes using respective type-two routing tables comprising one next-hop node associated with each of a plurality of destination nodes, comprising:

obtaining link status information associated with each of a plurality of links of the network from the type-one nodes and the type-two nodes;

obtaining traffic measurement information from the type-one nodes and the type-two nodes; and

determining, using the link status and traffic measurement information, a plurality of type-one routing tables for the respective type-one nodes, the type-one routing tables being determined for the type-one nodes as a group in a substantially coordinated manner, each type one routing table comprising a plurality of next-hop nodes associated with each of the destination nodes.

2. The method of claim 1, wherein the link status information comprises link weight information and link capacity information.

3. The method of claim 1, wherein the traffic measurement information comprises link utilization information, injected traffic information, and one of controllable traffic information or uncontrollable traffic information.

4. The method of claim 1, wherein determining each of the type-one routing tables comprises:

determining an injected traffic value comprising an amount of traffic injected by the type-one node for each combination of the type-one node and at least one destination node from said plurality of type-two nodes;

determining an uncontrollable traffic value for each of at least one link coupled to the type-one node; and

determining the type-one routing table using the injected traffic values and the uncontrollable traffic values.

5. The method of claim 4, wherein determining the injected traffic value for each combination of the type-one node and the at least one destination node, comprises:

determining a traversed traffic value for each combination of the type-one node and the at least one destination node, each traversed traffic value comprising an amount of traffic destined for the at least one destination node which traverses the type-one node; and

determining the injected traffic values using the traversed traffic values.

6. The method of claim 5, wherein each traversed traffic value is determined by the type-one node using at least one traffic measurement.

7. The method of claim 4, wherein determining the injected traffic value for each combination of the type-one node and the at least one destination node, comprises:

determining a traversed traffic value for each combination of the type-one node and the at least one destination node;

determining a first unit flow fraction comprising a fraction of a unit flow from the type-one node to the at least one destination node that traverses an intermediate node; and

determining the injected traffic values using the traversed traffic values and the first unit flow fraction.

8. The method of claim 4, wherein determining the uncontrollable traffic value for each of at least one link coupled to the type-one node, comprises:

determining a total flow for each of the at least one link;

determining a second unit flow fraction for each of the at least one link; and

determining the uncontrollable traffic value using the total flow, the second unit flow fraction, and the injected traffic values.

9. The method of claim 8, wherein determining the total flow for each of the at least one link, comprising:

obtaining topology information from each of the plurality of nodes;

obtaining link weight information associated with each of the at least one link; and

determining the total flow for each of the at least one link using the topology information and the link weight information associated with each of the at least one link.

10. The method of claim 1, further comprising:

obtaining other traffic measurement information from another plurality of type-one nodes; and

determining, using the link status and other traffic measurement information, another plurality of type-one routing tables for the respective other type-one nodes, the other type-one routing tables being determined for the other type-one nodes as another group in a substantially coordinated manner, each other type one routing table comprising a plurality of next-hop nodes associated with each of the destination nodes.

11. An apparatus for determining a routing table for use in a network comprising a plurality of type-one nodes and a plurality of type-two nodes, the type-two nodes using respective type-two routing tables comprising one next-hop node associated with each of a plurality of destination nodes, comprising:

means for obtaining link status information associated with each of a plurality of links of the network from the type-one node and the type-two nodes;

means for obtaining traffic measurement information from the type-one nodes and the type-two nodes; and

means for determining, using the link status and traffic measurement information, a plurality of type-one routing tables for the respective type-one nodes, the type-one routing tables being determined for the type-one nodes as a group in a substantially coordinated manner, each type one routing table comprising a plurality of next-hop nodes associated with each of the destination nodes.

12. A method for routing traffic at one of a plurality of type-one nodes in a network comprising the type-one nodes and a plurality of type-two nodes, the type-two nodes using respective type-two routing tables comprising one next-hop node associated with each of a plurality of destination nodes, comprising:

routing traffic at the one of the type-one nodes using an associated type-one routing table comprising a plurality of next-hop nodes associated with each of the destination nodes;

wherein a plurality of type-one routing tables including the type-one routing table associated with the one of the type-one nodes is determined using link status information and traffic measurement information from the type-one nodes and the type-two nodes, the type-one routing tables being determined for the type-one nodes as a group in a substantially coordinated manner.

13. The method of claim 12, wherein the link status information comprises link weight information and link capacity information.

14. The method of claim 12, wherein the traffic measurement information comprises link utilization information, injected traffic information, and one of controllable traffic information of uncontrollable traffic information.

15. The method of claim 12, wherein each of the type-one routing tables is determined using a method comprising:

determining an injected traffic value comprising an amount of traffic injected by the type-one node for each combination of the type-one node and at least one destination node from said plurality of type-two nodes;

determining an uncontrollable traffic value for each of at least one link coupled to the type-one node; and

determining the type-one routing table using the injected traffic values and the uncontrollable traffic values.

16. The method of claim 15, wherein determining the injected traffic value for each combination of the type-one node and the at least one destination node, comprises:

determining a traversed traffic value for each combination of the type-one node and the at least one destination node, each traversed traffic value comprising an amount of traffic destined for the at least one destination node which traverses the type-one node; and

determining the injected traffic values using the traversed traffic values.

17. The method of claim 16, wherein each traversed traffic value is determined by the type-one node using at least one traffic measurement.

18. The method of claim 15, wherein determining the injected traffic value for each combination of the type-one node and the at least one destination node, comprises:

determining a traversed traffic value for each combination of the type-one node and the at least one destination node;

determining a first unit flow fraction comprising a fraction of a unit flow from the type-one node to the at least one destination node that traverses an intermediate node; and

determining the injected traffic values using the traversed traffic values and the first unit flow fraction.

19. The method of claim 15, wherein determining the uncontrollable traffic value for each of at least one link coupled to the type-one node, comprises:

determining a total flow for each of the at least one link;

determining a second unit flow fraction for each of the at least one link; and

determining the uncontrollable traffic value using the total flow, the second unit flow fraction, and the injected traffic values.

20. The method of claim 19, wherein determining the total flow for each of the at least one link, comprising:

obtaining topology information from each of the plurality of nodes;

obtaining link weight information associated with each of the at least one link; and

determining the total flow for each of the at least one link using the topology information and the link weight information associated with each of the at least one link.

21. A system for manipulating traffic within a network, comprising:

a plurality of type-one nodes using respective type-one routing tables, each type-one routing table comprising a plurality of next-hop nodes associated with each of a plurality of destination nodes;

a plurality of type-two nodes using respective type-two routing tables, each type-two routing table comprising one next-hop node associated with each of the destination nodes; and

a controller in communication with the type-one and type-two nodes, the controller adapted for determining the type-one routing tables using link status information and traffic measurement information obtained from the type-one nodes and the type-two nodes, the controller adapted for determining the type-one routing tables for the type-one nodes as a group in a substantially coordinated manner.

22. A method for determining a routing table for use in a network comprising a type-one node and a plurality of type-two nodes, the type-two nodes using respective type-two routing tables comprising one next-hop node associated with each of a plurality of destination nodes, comprising:

obtaining status information from the type-one node and the type-two nodes; and

determining, using the status information, a type-one routing table for the type-one node comprising a plurality of next-hop nodes associated with each of the destination nodes.