Apparatus and method for scalable and dynamic traffic engineering in a data communication network

• US 7,453,884 B2
• Filed: 10/04/2004
• Issued: 11/18/2008
• Est. Priority Date: 04/25/2000
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Ma, Qingming
• Primary Examiner(s): Pham; Chi H.
• Assistant Examiner(s): MEW, KEVIN D
• Application Number:
  US10/958,920
• Publication Number:
  US 20050083936A1
• Time in Patent Office: 1,506 Days
• Field of Search: 370/238, 370/392, 370/401, 370/475, 370/395.32, 370/393, 370/389, 370/397, 370/399, 370/395.31, 370/400, 709238-244, 711202-205, 711213-214, 711/217, 711220-221
• US Class Current: 370/395.32
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits

Abstract

A global path identifier is assigned to each explicit route through a data communication network. The global path identifier is inserted into each packet as the packet enters a network and is used in selecting the next hop. When encountering a new selected path, an ingress router sends an explicit object to downstream nodes of the path to set up explicit routes by caching the next hop in an Explicit Forwarding Information Base (“EFIB”) table. Ingress routers maintain an Explicit Route Table (“ERT”) that tracks the global path identifier associated with each flow through the network. Multiple flows using the same path can be implemented by sharing the same global path identifier. In case of sudden network load changes, rerouting can be performed by changing the global path identifier associated with those flows that need to be rerouted and by then transmitting a new path object to downstream nodes.

Claims

1. A method for routing a data packet through an explicit path in a data communication network, the data packet having an incoming global path identifier corresponding to the explicit path, the data communication network comprising a plurality of network nodes, each of the plurality of network nodes including a network device, the explicit path comprising a plurality of hops including a prior hop, a current hop, and a next hop, each of the plurality of hops being associated with one of the plurality of network nodes, the method comprising:

receiving the data packet from the prior hop at the current hop in the network device;

performing a look-up function into a forwarding table using an index based on the incoming global path identifier to determine a forwarding table entry related to the next hop to which the data packet should be forwarded;

extracting an outgoing global path identifier for the data packet from the forwarding table entry, wherein the outgoing global path identifier for the data packet has been pre-calculated as a function of (1) the incoming global path identifier and (2) an identifier of the network device receiving the data packet at the current hop;

replacing the incoming global path identifier with the outgoing global path identifier in the data packet; and

forwarding the data packet to the next hop.

2. The method as defined in claim 1, wherein there are two explicit paths that merge at a network node and share a single same entry in the forwarding table in all downstream network nodes.

3. The method as defined in claim 2, wherein the network device has assigned to it an Internet Protocol (“

IP”

) address as the identifier of the network device and the outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on the incoming global path identifier and the IP address.

4. The method as defined in claim 2, wherein the outgoing global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for the data packet.

5. The method as defined in claim 4, wherein the network device has assigned to it an IP address as the identifier of the network device and the outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on the incoming global path identifier and the IP address.

6. The method as defined in claim 1, wherein the network device has assigned to it an Internet Protocol (“

IP”

) address as the identifier of the network device and the outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on the incoming global path identifier and the IP address.

7. The method as defined in claim 1, wherein the outgoing global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for the data packet.

8. The method as defined in claim 7, wherein the network device has assigned to it an IP address as the identifier of the network device and the outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on the incoming global path identifier and the IP address.

9. An apparatus for routing a data packet through an explicit path in a data communication network, the data packet having an incoming global path identifier corresponding to the explicit path, the data communication network comprising a plurality of network nodes, each of the plurality of network nodes including a network device, the explicit path comprising a plurality of hops including a prior hop, a current hop, and a next hop, each of the plurality of hops being associated with one of the plurality of network nodes, the apparatus comprising:

means for receiving the data packet from the prior hop at the current hop in the network device;

means for performing a look-up function into a forwarding table using an index based on the incoming global path identifier to determine a forwarding table entry related to the next hop to which the data packet should be forwarded;

means for extracting an outgoing global path identifier for the data packet from the forwarding table entry, wherein the outgoing global path identifier for the data packet has been pre-calculated as a function of (1) the incoming global path identifier and (2) an identifier of the network device receiving the data packet at the current hop;

means for replacing the incoming global path identifier with the outgoing global path identifier in the data packet; and

means for forwarding the data packet to the next hop.

10. The apparatus as defined in claim 9, wherein there are two explicit paths that merge at a network node and share a single same entry in the forwarding table in all downstream network nodes.

11. The apparatus as defined in claim 10, wherein the network device has assigned to it an Internet Protocol (“

IP”

) address as the identifier of the network device and the outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on the incoming global path identifier and the IP address.

12. The apparatus as defined in claim 10, wherein the outgoing global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for the data packet.

13. The apparatus as defined in claim 12, wherein the network device has assigned to it an IP address as the identifier of the network device and the outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on the incoming global path identifier and the IP address.

14. The apparatus as defined in claim 9, wherein the network device has assigned to it an Internet Protocol (“

IP”

) address as the identifier of the network device and the outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on the incoming global path identifier and the IP address.

15. The apparatus as defined in claim 9, wherein the outgoing global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for the data packet.

16. The apparatus as defined in claim 15, wherein the network device has assigned to it an IP address as the identifier of the network device and the outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on the incoming global path identifier and the IP address.

17. An apparatus for routing a data packet through an explicit path in a data communication network, the data packet having an incoming global path identifier corresponding to the explicit path, the data communication network comprising a plurality of network nodes, each of the plurality of network nodes including a network device, the explicit path comprising a plurality of hops including a prior hop, a current hop, and a next hop, each of the plurality of hops being associated with one of the plurality of network nodes, the apparatus comprising:

an input interface for receiving the data packet from the prior hop at the current hop in the network device;

table search logic for performing a look-up function into a forwarding table using an index based on the incoming global path identifier to determine a forwarding table entry related to the next hop to which the data packet should be forwarded;

path identifier assignment logic which extracts an outgoing global path identifier for the data packet from the forwarding table entry, wherein the outgoing global path identifier for the data packet has been pre-calculated as a function of (1) the incoming global path identifier and (2) an identifier of the network device receiving the data packet at the current hop;

path identifier insertion logic which replaces the incoming global path identifier with the outgoing global path identifier in the data packet; and

packet forwarding logic for forwarding the data packet to the next hop.

18. The apparatus as defined in claim 17, wherein there are two explicit paths that merge at a network node and share a single same entry in the forwarding table in all downstream network nodes.

19. The apparatus as defined in claim 18, wherein the network device has assigned to it an Internet Protocol (“

IP”

) address as the identifier of the network device and the outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on the incoming global path identifier and the IP address.

20. The apparatus as defined in claim 18, wherein the outgoing global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for the data packet.

21. The apparatus as defined in claim 20, wherein the network device has assigned to it an IP address as the identifier of the network device and the outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on the incoming global path identifier and the IP address.

22. The apparatus as defined in claim 17, wherein the network device has assigned to it an Internet Protocol (“

IP”

) address as the identifier of the network device and the outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on the incoming global path identifier and the IP address.

23. The apparatus as defined in claim 17, wherein the outgoing global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for the data packet.

24. The apparatus as defined in claim 23, wherein the network device has assigned to it an IP address as the identifier of the network device and the outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on the incoming global path identifier and the IP address.

25. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method of routing a data packet through an explicit path in a data communication network, the data packet having an incoming global path identifier corresponding to the explicit path, the data communication network comprising a plurality of network nodes, each of the plurality of network nodes including a network device, the explicit path comprising a plurality of hops including a prior hop, a current hop, and a next hop, each of the plurality of hops being associated with one of the plurality of network nodes, the method comprising:

receiving the data packet from the prior hop at the current hop in the network device;

performing a look-up function into a forwarding table using an index based on the incoming global path identifier to determine a forwarding table entry related to the next hop to which the data packet should be forwarded;

extracting an outgoing global path identifier for the data packet from the forwarding table entry, wherein the outgoing global path identifier for the data packet has been pre-calculated as a function of (1) the incoming global path identifier and (2) an identifier of the network device receiving the data packet at the current hop;

replacing the incoming global path identifier with the outgoing global path identifier in the data packet; and

forwarding the data packet to the next hop.

26. A method for routing a data packet through at least one explicit path in a data communication network, the data packet having a source/destination data pair, the at least one explicit path having specified a plurality of network nodes that form a route from a source network node to a destination network node, the data communication network comprising a plurality of network nodes, the method comprising:

receiving the data packet having the source/destination data pair;

performing a look-up fraction into a forwarding table using an index based on the source/destination data pair to determine a forwarding table entry related to a next network node along the route to which the data packet should be forwarded;

extracting a global path identifier for the data packet from the forwarding table entry, wherein the global path identifier for the data packet has been pre-calculated for the at least one explicit path through the data communication network;

inserting the global path identifier into the data packet; and

forwarding the data packet to the next network node.

27. The method as defined in claim 26, wherein the global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for the data packet.

28. The method as defined in claim 27, wherein each of the plurality of network nodes has assigned to it an IP address and the global path identifier is calculated by performing a bit-wise Exclusive-Or function on the IP addresses of the plurality of network nodes comprising the at least one explicit path.

29. The method as defined in claim 26, wherein each of the plurality of network nodes has assigned to it an Internet Protocol (“

IP”

) address and the global path identifier is calculated by performing a bit-wise Exclusive-Or function on the IP addresses of the plurality of network nodes comprising the at least one explicit path.

30. An apparatus for routing a data packet through at least one explicit path in a data communication network, the data packet having a source/destination data pair, the at least one explicit path having specified a plurality of network nodes that form a route from a source network node to a destination network node, the data communication network comprising a plurality of network nodes, the apparatus comprising:

means for receiving the data packet having the source/destination data pair;

means for performing a look-up function into a forwarding table using an index based on the source/destination data pair to determine a forwarding table entry related to a next network node along the route to which the data packet should be forwarded;

means for extracting a global path identifier for the data packet from the forwarding table entry, wherein the global path identifier for the data packet has been pre-calculated for the at least one explicit path through the data communication network;

means for inserting the global path identifier into the data packet; and

means for forwarding the data packet to the next network node.

31. The apparatus as defined in claim 30, wherein the global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for the data packet.

32. The apparatus as defined in claim 31, wherein each of the plurality of network nodes has assigned to it an IP address and the global path identifier is calculated by performing a bit-wise Exclusive-Or function on the IP addresses of the plurality of network nodes comprising the at least one explicit path.

33. The apparatus as defined in claim 30, wherein each of the plurality of network nodes has assigned to it an Internet Protocol (“

IP”

) address and the global path identifier is calculated by performing a bit-wise Exclusive-Or function on the IP addresses of the plurality of network nodes comprising the at least one explicit path.

34. An apparatus for routing a data packet through at least one explicit path in a data communication network, the data packet having a source/destination data pair, the at least one explicit path having specified a plurality of network nodes that form a route from a source network node to a destination network node, the data communication network comprising a plurality of network nodes, the apparatus comprising:

an input interface for receiving the data packet having the source/destination data pair;

table search logic for performing a look-up function into a forwarding table using an index based on the source/destination data pair to determine a forwarding table entry related to a next network node along the route to which the data packet should be forwarded;

global path identifier assignment logic which extracts a global path identifier for the data packet from the forwarding table entry, wherein the global path identifier for the data packet has been pre-calculated for the at least one explicit path through the data communication network;

global path identifier insertion circuitry for inserting the global path identifier into the data packet; and

packet forwarding logic for forwarding the data packet to the next network node.

35. The apparatus as defined in claim 34, wherein the global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for the data packet.

36. The apparatus as defined in claim 35, wherein each of the plurality of network nodes has assigned to it an IP address and the global path identifier is calculated by performing a bit-wise Exclusive-Or function on the IP addresses of the plurality of network nodes comprising the at least one explicit path.

37. The apparatus as defined in claim 34, wherein each of the plurality of network nodes has assigned to it an Internet Protocol (“

IP”

) address and the global path identifier is calculated by performing a bit-wise Exclusive-Or function on the IP addresses of the plurality of network nodes comprising the at least one explicit path.

38. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for routing a data packet through at least one explicit path in a data communication network, the data packet having a source/destination data pair, the at least one explicit path having specified a plurality of network nodes that form a route from a source network node to a destination network node, the data communication network comprising a plurality of network nodes, the method comprising:

receiving the data packet having the source/destination data pair;

performing a look-up function into a forwarding table using an index based on the source/destination data pair to determine a forwarding table entry related to a next network node along the route to which the data packet should be forwarded;

extracting a global path identifier for the data packet from the forwarding table entry, wherein the global path identifier for the data packet has been pre-calculated for the at least one explicit path through the data communication network;

inserting the global path identifier into the data packet; and

forwarding the data packet to the next network node.