Link state advertisements specifying dynamic routing metrics and associated variation metrics and selective distribution thereof

• US 7,567,577 B2
• Filed: 06/28/2005
• Issued: 07/28/2009
• Est. Priority Date: 06/28/2005
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Ribiere, Vincent Jean, Thubert, Pascal, Wetterwald, Patrick, Levy-Abegnoli, Eric M.
• Primary Examiner(s): Shah; Chirag G
• Assistant Examiner(s): Rivas; Salvador E
• Application Number:
  US11/167,239
• Publication Number:
  US 20060291485A1
• Time in Patent Office: 1,491 Days
• Field of Search: 370/401, 709/238
• US Class Current: 370/401
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04W 40/248 Connectivity information update

Abstract

Each router in a network is configured for executing a link state routing protocol based on outputting a corresponding first link state advertisement message describing a connected link of the router and that specifies a first dynamic routing metric identifying a first cost of the connected link, and a corresponding variation metric identifying a statistical variation of the dynamic routing metric. Each router also is configured for selectively outputting a corresponding second link state advertisement message describing the connected link and that specifies the corresponding variation metric and an updated dynamic routing metric identifying an updated cost of the connected link relative to the first cost, the second link state advertisement message selectively output based on the updated dynamic routing metric differing from the first dynamic routing metric by more than the variation metric, or the router having received another link state advertisement from another router in the network.

Claims

1. A method in a router configured for executing a prescribed link state routing protocol, the method including:

originating and outputting by the router a first link state advertisement message describing a connected link of the router in a network,

the first link state advertisement message specifying a first dynamic routing metric and a corresponding variation metric identifying a statistical variation of the first dynamic routing metric, the first dynamic routing metric identifying a first cost of the connected link;

selectively originating and outputting a second link state advertisement message describing the connected link and that specifies an updated dynamic routing metric and the corresponding variation metric, the updated dynamic routing metric identifying an updated cost of the connected link relative to the first cost, the second link state advertisement message selectively output by the router in response to one of;

(1) the updated dynamic routing metric differing from the first dynamic routing metric by more than the variation metric, or (2) the router having received another link state advertisement message from another router in the network.

2. The method of claim 1, wherein the first dynamic routing metric and the updated dynamic routing metric specify a corresponding statistical normalization of the first cost and the updated cost, respectively.

3. The method of claim 2, wherein the first cost and the updated cost identify at least one of available bandwidth, utilized bandwidth, link congestion, or round trip link delay.

4. The method of claim 2, wherein the statistical normalization is one of a mean or a median of the corresponding cost relative to a prescribed distribution.

5. The method of claim 4, wherein the statistical normalization is based on an independent variable within the network, the statistical normalization providing a graph of the prescribed distribution relative to the independent variable.

6. The method of claim 5, wherein the variation metric specifies one of a percentage deviation or a standard deviation value relative to the statistical normalization.

7. The method of claim 1, wherein the selectively outputting includes outputting the second link state advertisement message only in response to said one of (1) the updated dynamic routing metric differing from the first dynamic routing metric by more than the variation metric, or (2) the router having received another link state advertisement message from another router in the network, the method further comprising:

periodically outputting a hello message to the another router; and

recalculating stored routes in response to the another link state advertisement message.

8. The method of claim 1, further comprising selecting a path for a received packet based on a cost value derived from the updated dynamic routing metric and the corresponding variation metric.

36. The method of claim 1, wherein the selectively originating includes the router not outputting the second link state advertisement message if the updated routing metric differs from the first dynamic metric by less than the variation metric and the router has not received said another link state advertisement message.

9. A router in a network, the router comprising:

a plurality of network interfaces, each configured for outputting, via a corresponding connected link, first and second link state advertisement messages having been generated by the router, at least one of the network interfaces configured for receiving a third link state advertisement message from another router in the network; and

a routing resource configured for executing a prescribed link state routing protocol, the routing resource configured for originating and supplying, to the network interfaces, the first link state advertisement message describing a corresponding one of the connected links and specifying a first dynamic routing metric and a corresponding variation metric identifying a statistical variation of the first dynamic routing metric, the first dynamic routing metric identifying a first cost of the corresponding one connected link;

the routing resource further configured for selectively originating and outputting, to the network interfaces, a second link state advertisement message describing the corresponding one connected link and that specifies an updated dynamic routing metric and the corresponding variation metric, the updated dynamic routing metric identifying an updated cost of the corresponding one connected link relative to the first cost, the second link state advertisement message selectively generated by the routing resource in response to one of;

(1) the routing resource having determined that the updated dynamic routing metric differs from the first dynamic routing metric by more than the variation metric, or (2) the routing resource having received the third link state advertisement message.

10. The router of claim 9, wherein the first dynamic routing metric and the updated dynamic routing metric specify a corresponding statistical normalization of the first cost and the updated cost, respectively.

11. The router of claim 10, wherein the first cost and the updated cost identify at least one of available bandwidth, utilized bandwidth, link congestion, or round trip link delay.

12. The router of claim 10, wherein the statistical normalization is one of a mean or a median of the corresponding cost relative to a prescribed distribution.

13. The router of claim 12, wherein the statistical normalization is based on an independent variable within the network, the statistical normalization providing a graph of the prescribed distribution relative to the independent variable.

14. The router of claim 13, wherein the variation metric specifies one of a percentage deviation or a standard deviation value relative to the statistical normalization.

15. The router of claim 9, wherein the routing resource is configured for selectively outputting the second link state advertisement message only in response to said one of (1) the updated dynamic routing metric differing from the first dynamic routing metric by more than the variation metric, or (2) the router having received another link state advertisement message from another router in the network, the routing resource further configured for:

periodically outputting a hello message to the another router; and

recalculating stored routes in response to the third link state advertisement message.

16. The router of claim 9, wherein the routing resource is configured for selecting a path for a received packet based on a cost value derived from the updated dynamic routing metric and the corresponding variation metric.

37. The router of claim 9, wherein the routing resource is configured for not outputting the second link state advertisement message if the updated routing metric differs from the first dynamic metric by less than the variation metric, and if the routing resource has not received the third link state advertisement message.

17. A network comprising:

a plurality of routers, each router comprising;

(1) a plurality of network interfaces, each configured for outputting, via a corresponding connected link, first and second link state advertisement messages having been generated by the router, at least one of the network interfaces configured for receiving a third link state advertisement message from another one of the routers in the network; and

(2) a routing resource configured for executing a prescribed link state routing protocol, the routing resource configured for originating and supplying, to the network interfaces, the first link state advertisement message describing a corresponding one of the connected links and specifying a first dynamic routing metric and a corresponding variation metric identifying a statistical variation of the first dynamic routing metric, the first dynamic routing metric identifying a first cost of the corresponding one connected link, the routing resource of said each router further configured for selectively originating and outputting, to the network interfaces of said each router, a second link state advertisement message describing the corresponding one connected link and that specifies an updated dynamic routing metric and the corresponding variation metric, the updated dynamic routing metric identifying an updated cost of the corresponding one connected link relative to the first cost, the second link state advertisement message selectively generated by the routing resource in response to one of;

(1) the routing resource having determined that the updated dynamic routing metric differs from the first dynamic routing metric by more than the variation metric, or (2) the routing resource having received the third link state advertisement message.

18. The network of claim 17, wherein the first dynamic routing metric and the updated dynamic routing metric specify a corresponding statistical normalization of the first cost and the updated cost, respectively.

19. The network of claim 18, wherein the first cost and the updated cost identify at least one of available bandwidth, utilized bandwidth, link congestion, or round trip link delay.

20. The network of claim 18, wherein the statistical normalization is one of a mean or a median of the corresponding cost relative to a prescribed distribution.

21. The network of claim 20, wherein the statistical normalization is based on an independent variable within the network, the statistical normalization providing a graph of the prescribed distribution relative to the independent variable.

22. The network of claim 21, wherein the variation metric specifies one of a percentage deviation or a standard deviation value relative to the statistical normalization.

23. The network of claim 17, wherein the routing resource is configured for selectively outputting the second link state advertisement message only in response to said one of (1) the updated dynamic routing metric differing from the first dynamic routing metric by more than the variation metric, or (2) the router having received another link state advertisement message from another router in the network, the routing resource further configured for:

periodically outputting a hello message to the another router; and

recalculating stored routes in response to the third link state advertisement message.

24. The router of claim 17, wherein the routing resource is configured for selecting a path for a received packet based on a cost value derived from the updated dynamic routing metric and the corresponding variation metric.

38. The network of claim 17, wherein the routing resource is configured for not outputting the second link state advertisement message if the updated routing metric differs from the first dynamic metric by less than the variation metric, and if the routing resource has not received the third link state advertisement message.

25. A router in a network, the router comprising:

a plurality of network interfaces, each configured for outputting, via a corresponding connected link, first and second link state advertisement messages having been generated by the router, at least one of the network interfaces configured for receiving a third link state advertisement message from another router in the network; and

means for executing a prescribed link state routing protocol, the means for executing configured for originating and supplying, to the network interfaces, the first link state advertisement message describing a corresponding one of the connected links and specifying a first dynamic routing metric and a corresponding variation metric identifying a statistical variation of the first dynamic routing metric, the first dynamic routing metric identifying a first cost of the corresponding one connected link;

the means for executing selectively originating and outputting, to the network interfaces, a second link state advertisement message describing the corresponding one connected link and that specifies an updated dynamic routing metric and the corresponding variation metric, the updated dynamic routing metric identifying an updated cost of the corresponding one connected link relative to the first cost, the second link state advertisement message selectively generated by the means for executing in response to one of;

(1) the means for executing having determined that the updated dynamic routing metric differs from the first dynamic routing metric by more than the variation metric, or (2) the means for executing having received the third link state advertisement message.

26. The router of claim 25, wherein the first dynamic routing metric and the updated dynamic routing metric specify a corresponding statistical normalization of the first cost and the updated cost, respectively.

27. The router of claim 26, wherein the first cost and the updated cost identify at least one of available bandwidth, utilized bandwidth, link congestion, or round trip link delay.

28. The router of claim 26, wherein the statistical normalization is one of a mean or a median of the corresponding cost relative to a prescribed distribution.

29. The router of claim 28, wherein the statistical normalization is based on an independent variable within the network, the statistical normalization providing a graph of the prescribed distribution relative to the independent variable.

30. The router of claim 29, wherein the variation metric specifies one of a percentage deviation or a standard deviation value relative to the statistical normalization.

31. The router of claim 25, wherein the means for executing is configured for selectively outputting the second link state advertisement message only in response to said one of (1) the updated dynamic routing metric differing from the first dynamic routing metric by more than the variation metric, or (2) the router having received another link state advertisement message from another router in the network, the means for executing further configured for:

periodically outputting a hello message to the another router; and

recalculating stored routes in response to the third link state advertisement message.

32. The router of claim 25, wherein the means for executing is configured for selecting a path for a received packet based on a cost value derived from the updated dynamic routing metric and the corresponding variation metric.

39. The router of claim 25, wherein the means for executing is configured for not outputting the second link state advertisement message if the updated routing metric differs from the first dynamic metric by less than the variation metric, and if the routing resource has not received the third link state advertisement message.

33. A computer readable medium having stored thereon sequences of instructions for a router executing a prescribed link state routing protocol in a network, the sequences of instructions including instructions for:

originating and outputting by the router a first link state advertisement message describing a connected link of the router in the network, the first link state advertisement message specifying a first dynamic routing metric and a corresponding variation metric identifying a statistical variation of the first dynamic routing metric, the first dynamic routing metric identifying a first cost of the connected link;

selectively originating and outputting a second link state advertisement message describing the connected link and that specifies an updated dynamic routing metric and the corresponding variation metric, the updated dynamic routing metric identifying an updated cost of the connected link relative to the first cost, the second link state advertisement message selectively output by the router in response to one of;

(1) the updated dynamic routing metric differing from the first dynamic routing metric by more than the variation metric, or (2) the router having received another link state advertisement message from another router in the network.

34. The medium of claim 33, wherein the first dynamic routing metric and the updated dynamic routing metric specify a corresponding statistical normalization of the first cost and the updated cost, respectively.

35. The medium of claim 33, wherein the selectively outputting includes outputting the second link state advertisement message only in response to said one of (1) the updated dynamic routing metric differing from the first dynamic routing metric by more than the variation metric, or (2) the router having received another link state advertisement message from another router in the network, the medium further comprising instructions for:

periodically outputting a hello message to the another router; and

recalculating stored routes in response to the another link state advertisement message.

40. The medium of claim 33, wherein the selectively originating includes the router not outputting the second link state advertisement message if the updated routing metric differs from the first dynamic metric by less than the variation metric and the router has not received said another link state advertisement message.