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

• US 7,123,620 B1
• Filed: 04/25/2000
• Issued: 10/17/2006
• Est. Priority Date: 04/25/2000
• Status: Expired due to Fees

• Current Assignee: Cisco Systems, Inc.
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Ma, Qingming
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): MEW, KEVIN D
• Application Number:
  US09/558,693
• Time in Patent Office: 2,366 Days
• Field of Search: 370/238, 370/400, 370/389, 370/392, 370/393, 370/401, 370/397, 370/399, 370/395.31, 370/395.32, 370/475, 709238-244, 711202-205, 711213-214, 711/217, 711/220, 711/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, said data packet having an incoming global path identifier corresponding to said explicit path, said data communication network comprising a plurality of network nodes, each of said plurality of network nodes including a network device, said explicit path comprising a plurality of hops including a prior hop, a current hop, and a next hop, each of said plurality of hops being associated with one of said plurality of network nodes, the method comprising the steps of:

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

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

calculating an outgoing global path identifier for said data packet as a function of (1) said incoming global path identifier and (2) an identifier of said network device receiving said data packet at said current hop; and

forwarding said data packet to said next hop.

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

3. The method according to claim 1, wherein said outgoing global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for said data packet.

4. The method according to claim 2, wherein said outgoing global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for said data packet.

5. The method according to claim 1, wherein said network device has assigned to it an Internet Protocol address as said identifier of said network device and said outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on said incoming global path identifier and said Internet Protocol address.

6. The method according to claim 2, wherein said network device has assigned to it an Internet Protocol address as said identifier of said network device and said outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on said incoming global path identifier and said Internet Protocol address.

7. The method according to claim 3, wherein said network device has assigned to it an Internet Protocol address as said identifier of said network device and said outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on said incoming global path identifier and said Internet Protocol address addresses.

8. The method according to claim 4, wherein said network device has assigned to it an Internet Protocol address as said identifier of said network device and said outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on said incoming global path identifier and said Internet Protocol address addreses.

9. A method for routing a data packet through at least one explicit path in a data communication network, said data packet having a source/destination data pair, said 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, said data communication network comprising a plurality of network nodes, the method comprising:

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

calculating a global path identifier for said at least one explicit path through said data communication network;

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

inserting said global path identifier into said data packet; and

forwarding said data packet to said next network node.

10. The method according to claim 9, wherein said global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for said data packet.

11. The method according to claim 9, wherein each of said plurality of network nodes has assigned to it an Internet Protocol address and said global path identifier is calculated by performing a bit-wise Exclusive-Or function on said Internet Protocol addresses of said plurality of network nodes comprising said at least one explicit path.

12. The method according to claim 10, wherein each of said plurality of network nodes has assigned to it an Internet Protocol address and said global path identifier is calculated by performing a bit-wise Exclusive-Or function on said Internet Protocol addresses of said plurality of network nodes comprising said at least one explicit path.

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

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

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

means for calculating an outgoing global path identifier for said data packet as a function of (1) said incoming global path identifier and (2) an identifier of said network device receiving said data packet at said current hop; and

means for forwarding said data packet to said next hop.

14. The apparatus according to claim 13, wherein there are two explicit paths that merge at a network node and share a single same entry in said forwarding table in all downstream network nodes.

15. The apparatus according to claim 13, wherein said outgoing global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for said data packet.

16. The apparatus according to claim 14, wherein said outgoing global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for said data packet.

17. The apparatus according to claim 13, wherein said network device has assigned to it an Internet Protocol address as said identifier of said network device and said outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on said incoming global path identifier and said Internet Protocol address.

18. The apparatus according to claim 14, wherein said network device has assigned to it an Internet Protocol address as said identifier of said network device and said outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on said incoming global path identifier and said Internet Protocol address.

19. The apparatus according to claim 15, wherein said network device has assigned to it an Internet Protocol address as said identifier of said network device and said outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on said incoming global path identifier and said Internet Protocol address.

20. The apparatus according to claim 16, wherein said network device has assigned to it an Internet Protocol address as said identifier of said network device and said outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on said incoming global path identifier and said Internet Protocol address.

21. An apparatus for routing a data packet through at least one explicit path in a data communication network, said data packet having a source/destination data pair, said 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, said data communication network comprising a plurality of network nodes, the apparatus comprising:

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

means for calculating a global path identifier for said at least one explicit path through said data communication network;

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

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

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

22. The apparatus according to claim 21, wherein said global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for said data packet.

23. The apparatus according to claim 21, wherein each of said plurality of network nodes has assigned to it an Internet Protocol address and said global path identifier is calculated by performing a bit-wise Exclusive-Or function on said Internet Protocol addresses of said plurality of network nodes comprising said at least one explicit path.

24. The apparatus according to claim 22, wherein each of said plurality of network nodes has assigned to it an Internet Protocol address and said global path identifier is calculated by performing a bit-wise Exclusive-Or function on said Internet Protocol addresses of said plurality of network nodes comprising said at least one explicit path.

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

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

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

path identifier assignment logic which calculates an outgoing global path identifier for said data packet as a function of (1) said incoming global path identifier and (2) an identifier of said network device receiving said data packet at said current hop; and

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

26. The apparatus according to claim 25, wherein there are two explicit paths that merge at a network node and share a single same entry in said forwarding table in all downstream network nodes.

27. The apparatus according to claim 25, wherein said outgoing global path identifier into an optional field of an Internet Protocol (“

IP”

) packet header for said data packet.

28. The apparatus according to claim 26, wherein said outgoing global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for said data packet.

29. The apparatus according to claim 25, wherein said network device has assigned to it an Internet Protocol address as said identifier of said network device and said outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on said incoming global path identifier and said Internet Protocol address.

30. The apparatus according to claim 26, wherein said network device has assigned to it an Internet Protocol address as said identifier of said network device and said outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on said incoming global path identifier and said Internet Protocol address.

31. The apparatus according to claim 27, wherein said network device has assigned to it an Internet Protocol address as said identifier of said network device and said outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on said incoming global path identifier and said Internet Protocol address.

32. The apparatus according to claim 28, wherein said network device has assigned to it an Internet Protocol address as said identifier of said network device and said outgoing global path identifier is calculated by performing a bit-wise Exclusive-Or function on said incoming global path identifier and said Internet Protocol address.

33. An apparatus for routing a data packet through at least one explicit path in a data communication network, said data packet having a source/destination data pair, said 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, said data communication network comprising a plurality of network nodes, the apparatus comprising:

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

global path identifier circuitry for calculating a global path identifier for said at least one explicit path through said data communication network;

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

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

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

34. The apparatus according to claim 33, wherein said global path identifier is inserted into an optional field of an Internet Protocol (“

IP”

) packet header for said data packet.

35. The apparatus according to claim 33, wherein each of said plurality of network nodes has assigned to it an Internet Protocol address and said global path identifier is calculated by performing a bit-wise Exclusive-Or function on said Internet Protocol addresses of said plurality of network nodes comprising said at least one explicit path.

36. The apparatus according to claim 34, wherein each of said plurality of network nodes has assigned to it an Internet Protocol address and said global path identifier is calculated by performing a bit-wise Exclusive-Or function on said Internet Protocol addresses of said plurality of network nodes comprising said at least one explicit path.

37. 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 an explicit path in a data communication network, said data packet having an incoming global path identifier corresponding to said explicit path, said data communication network comprising a plurality of network nodes, each of said plurality of network nodes including a network device, said explicit path comprising a plurality of hops including a prior hop, a current hop, and a next hop, each of said plurality of hops being associated with one of said plurality of network nodes, the method comprising:

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

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

calculating an outgoing global path identifier for said data packet as a function of (1) said incoming global path identifier and (2) an identifier of said network device receiving said data packet at said current hop; and

forwarding said data packet to said next hop.

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, said data packet having a source/destination data pair, said 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, said data communication network comprising a plurality of network nodes, the method comprising:

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

calculating a global path identifier for said at least one explicit path through said data communication network;

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

inserting said global path identifier into said data packet; and

forwarding said data packet to said next network node.