Method and apparatus for automatically optimizing routing operations at the edge of a network

• US 8,073,968 B1
• Filed: 11/03/2004
• Issued: 12/06/2011
• Est. Priority Date: 11/03/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Blair, Dana, Jacobs, Philip C., Shah, Pritam, Valluri, Vamsidhar, Nguyen, Kathleen
• Primary Examiner(s): Pwu, Jeffrey
• Assistant Examiner(s): Taha, Shaq
• Application Number:
  US10/980,550
• Time in Patent Office: 2,589 Days
• Field of Search: 709/238
• US Class Current: 709/238
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/0864 Round trip delays
• 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/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 49/20 Support for services

Abstract

An Optimized Edge Routing (OER) technique provides efficiently data routing at the edge of a network or subnetwork. The technique employs a Master node that manages a set of border nodes located at the edge of the network or subnetwork. The Master node may be a stand-alone network management node or may be incorporated into a network node, such as a border node. Unlike prior implementations, the Master node instructs the border nodes to dynamically acquire (“learn”) prefixes of incoming and outgoing data flows and to selectively filter a set of learned address prefixes whose corresponding data flows match a predetermined set of criteria. The criteria may be based on routing metrics other than, or in addition to, conventional cost-based or distance-based metrics. Further, the criteria may include a set of filtering parameters that may be reconfigured, e.g., by the Master node, from time to time. Using the learned prefixes filtered by the border nodes, the Master node can distribute network traffic and utilize network bandwidth more efficiently than conventionally done.

Claims

1. A Master node interconnected with one or more border nodes located at an edge of a computer network, the Master node comprising:

a processor,

a memory storing instructions which are executable by the processor, at least a portion of the instructions for implementing an optimized edge routing (OER) process configured to;

generate a message that instructs at least one of the border nodes to dynamically acquire (“

learn”

) address prefixes of a plurality of data flows entering or exiting the network through the border nodes, the learned address prefixes corresponding to data flows matching a predetermined set of criteria that specify a known set of packet-header field values; and

,

receive the learned address prefixes matching the predetermined set of criteria that specify a known set of packet-header values at the Master node from the at least one of the border nodes.

3. The Master node of claim 1, wherein the predetermined set of criteria also specifies a type of data-flow statistic to measure for each learned address prefix.

4. The Master node of claim 3, wherein the data-flow statistic is based on a data throughput measurement.

5. The Master node of claim 3, wherein the data-flow statistic is based on a roundtrip delay time measurement.

6. The Master node of claim 3, wherein the data-flow statistic is based on a packet loss measurement.

7. The Master node of claim 1, wherein the message includes the predetermined set of criteria, a learning interval indicating a duration of time for which the at least one border node learns address prefixes and a periodic interval indicating a duration of time between successive learning intervals.

8. The Master node of claim 7, wherein the message further includes a periodic interval indicating duration of time between successive learning intervals.

9. The Master node of claim 1, the message further includes at least one why-learnt indicator value associated with a corresponding learned address prefix, the why learnt indicator value indicating a reason its corresponding learned address prefix was filtered by the predetermined set of criteria.

10. The Master node of claim 1, wherein the computer network is an autonomous system.

2. The Master node wherein the OER process is further configured to:

adjust routing operations at the border nodes based on which learned address prefixes are received.

11. A border node located at an edge of a computer network, the border node being in communication with a Master optimized edge routing (OER) process executing in the computer network, the border node comprising:

a processor;

one or more line cards adapted to send and receive data packets to the Master OER process; and

a memory adapted to store instructions which are executable by the processor, at least a portion of the instructions for implementing an OER process configured to;

dynamically acquire (“

learn”

) address prefixes of a source or a destination of a plurality of data flows received at the line cards;

selectively filter the learned address prefixes so as to identify a set of learned address prefixes whose corresponding data flows match a predetermined set of criteria that specify a known set of packet-header field values; and

forward the filtered set of learned address prefixes to the Master OER process.

12. The border node of claim 11, wherein the Master OER process executes in a Master node located in the computer network.

13. The border node of claim 11, wherein the OER process executing in the border node is distributed on one or more of the line cards.

14. The border node of claim 11, wherein the OER process executing in the border node is further configured to associate at least one why-learnt indicator value with a corresponding learned address prefix, the why-learnt indicator value indicating a reason its corresponding learned address prefix was filtered by the predetermined set of criteria.

15. The border node of claim 11, wherein the OER process executing in the border node is further configured to:

measure network statistics associated with the plurality of data flows; and

aggregate measured statistics for those data flows that were (i) selectively filtered using the predetermined set of criteria and (ii) have the same address prefix.

16. The border node of claim 15, wherein the OER process executing in the border node is further configured to:

sort the aggregated statistics and generate a list of sorted learned prefixes; and

forward the list of sorted learned prefixes to the Master OER process.

17. The Master node of claim 11, wherein the computer network is an autonomous system.

18. An autonomous system, comprising:

one or more border nodes situated at the edge of the autonomous system, each border node being adapted to dynamically acquire (“

learn”

) address prefixes of a plurality of data flows entering or exiting the autonomous system through the border nodes, and further adapted to selectively filter the learned address prefixes so as to identify a set of learned address prefixes whose corresponding data flows match a predetermined set of criteria that specify a known set of packet-header field values; and

a Master node adapted to receive the set of learned address prefixes identified by the border nodes and to control distribution of data flows at the border nodes based on the set of learned address prefixes.

19. The autonomous system of claim 18, wherein the Master node is one of the border nodes.

20. The autonomous system of claim 18, wherein the Master node disseminates the predetermined set of criteria to the border nodes.

21. The autonomous system of claim 18, wherein the Master node multicasts a start learning request containing the predetermined set of criteria.

22. The autonomous system of claim 18, wherein the border nodes sort the filtered set of prefixes based on measured statistics associated with the filtered set of prefixes.

23. The autonomous system of claim 22, wherein the prefixes are sorted based on aggregated data throughput measurements associated with the filtered set of prefixes.

24. The autonomous system of claim 22, wherein the prefixes are sorted based on aggregated round-trip packet delay measurements associated with the filtered set of prefixes.

25. A method for a Master node in an autonomous system to optimize routing operations at one or more border nodes situated at the edge of the autonomous system, the method comprising:

generating a message containing a predetermined set of criteria at the Master node, the predetermined set of criteria to include a set of one or more packet-header field values;

forwarding the message from the Master node to a border node to instruct the border node to configure a learn filter using the predetermined set of criteria that include a set of one or more packet-header field values; and

receiving at the Master node a set of learned address prefixes of a source or a destination of a plurality of data flows entering or exiting the network through the border node that were dynamically acquired (“

learned”

) at the border node.

26. The method of claim 25, further comprising:

adjusting routing operations at the one or more border nodes based on the contents of the received set of learned address prefixes.

27. A method for a border node located at an edge of an autonomous system to optimize its routing operations, the border node being in communication with a Master optimized edge routing (OER) process executing in the autonomous system, the method comprising:

receiving a message containing a predetermined set of criteria that include a set of one or more packet-header field values and a learning interval,

configuring, in response to receiving the message, at least one learn filter using the predetermined set of criteria that include a set of one or more packet-header field values;

dynamically acquiring (“

learning”

) address prefixes of a plurality of data flows, and statistics for the plurality of data flows for the duration of the learning interval, and

filtering learned address prefixes using the learn filter.

28. The method of claim 27, further comprising:

aggregating statistics associated with each filtered address prefix, and

sorting the filtered address prefixes based on their aggregated statistics.

29. The method of claim 27, further comprising:

forwarding a set of sorted address prefixes to the Master OER process.

30. The method of claim 27, further comprising:

waiting a duration of a periodic interval before learning new address prefixes and statistics.