Source: https://patents.google.com/patent/US7792991
Timestamp: 2018-03-20 10:18:00
Document Index: 446341257

Matched Legal Cases: ['application No. 2004311004', 'application No. 2004311004', 'application No. 2', 'Application No. 2509359', 'application No. 2', 'application No. 2004311004', 'application No. 200480033007', 'Application No. 04795045', 'Application No. 05749440', 'Application No. 05749440', 'Application No. 04795045', 'Application No. 05749440', 'application No. 200480033007']

US7792991B2 - Method and apparatus for advertising a link cost in a data communications network - Google Patents
Method and apparatus for advertising a link cost in a data communications network
US7792991B2
US7792991B2 US10323358 US32335802A US7792991B2 US 7792991 B2 US7792991 B2 US 7792991B2 US 10323358 US10323358 US 10323358 US 32335802 A US32335802 A US 32335802A US 7792991 B2 US7792991 B2 US 7792991B2
US10323358
US20040117251A1 (en )
Ian Michael Charles Shand
A method is described of advertising a link cost in a data communication network having as components nodes and links. A node detects a change of state of an adjacent component. The change of state can be between an activated and a deactivated state or vice versa. The node varies an associated link cost by an incremental value and advertises the varied cost.
The present invention generally relates to link costs in a data communications network. The invention relates more specifically to a method and apparatus for advertising a link cost in a data communications network.
state database (LSDB) which is a map of the entire network topology and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example a shortest path first (SPF) algorithm. As a result a “spanning tree” is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. Because each node has a common LSDB (other than when advertised changes are propagating around the network) any node is able to compute the spanning tree rooted at any other node.
It will be noted, therefore, that each node decides, irrespective of the node from which it received a packet, the next node to which the packet should be forwarded. In some instances this can give rise to a “loop”. In particular this can occur when the databases (and corresponding forwarding information) are temporarily de-synchronized during a routing transition, that is, where because of a change in the network, a new LSP is propagated. As an example if node A sends a packet to node Z via node B, comprising the optimum route according to its SPF, a situation can arise where node B, according to its SPF determines that the best route to node Z is via node A and sends the packet back. This can continue indefinitely although usually the packet will have a maximum hop count after which it will be discarded. Such a loop can be a direct loop between two nodes or an indirect loop around a circuit of nodes.
In conventional systems, when a link fails this is identified by an adjacent node in a medium specific manner. This instigates a routing transition whereby the neighboring node advertises the link failure to the remainder of the network. This can be done by simply removing the link from the LSP or, in some circumstances, setting its cost to an integral value high enough to direct all traffic around the failed link. This value is often termed “infinity” and it will be seen that the approaches are effectively the same.
A simple network is shown designed generally 10 and including nodes A, B, D, X, Y reference numerals 12, 14, 16, 18, 20 respectively. The nodes are joined by links in a circuit running ABDYXA, a link 22 joining nodes A and B. All of the links have a cost 1 except for a link 24 joining nodes Y and D which has a cost 5. When all of the links are operating, a packet arriving at node X and destined for node D will take the route XABD with a cost of 3, as opposed to the route XYD which has a cost of 6. Similarly, a packet arriving at node Y destined for node D will take route YXABD with a cost of 4 rather than YD with a cost of 5. If the link 22 between nodes A and B fails then node A advertises the failure by sending out an LSP effectively setting the cost for link 22 to “infinity”. At some point this LSP will have reached X allowing it to update its LSDB but will not yet have arrived at node Y. As a result a packet now arriving at node X destined for node D will be forwarded towards Y as part of the route XYD at a cost 6 as opposed to the route XABD at a cost infinity. However when that packet reaches node Y, as node Y still records the cost of the link 22 between nodes A and B as 1, according to its SPF the lowest cost route is still via XABD at a cost 4. Accordingly the packet is returned to node X which again tries to send it to node Y and so forth. It will be seen that a loop of this nature can be a direct loop between two nodes or an indirect loop around a circuit of nodes.
One proposed solution to advertising link failure is described in Paolo Narvaez, Kai-Yeung Siu and Hong-Yi Tzeng, “Fault-Tolerant Routing in the Internet without Flooding”, proceedings of the 1999 IEEE Workshop on Fault-Tolerant Parallel and Distributed Systems, San Juan, Puerto Rico, April 1999. According to this solution when a link fails, rather than flooding the network with LSPs only those nodes on the shortest or all “restoration paths” around the failed link are notified and each of those nodes updates its routing table only in relation to the set of destinations affected by the link failure. As a result packets are forced along a restoration path. However this approach requires significant perturbation of the routing protocols at each node involved, and temporary loops may be formed.
A method and apparatus for advertising a link cost on a data communication network is described. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.
The method can be further understood with reference once again to the embodiments shown in FIG. 1, which depicts an illustrative network diagram showing a potential route configuration. A data communication network comprises nodes A, B, D, X, Y and links 22, 24, 26. Network 10 comprises for example the Internet or a sub-network such as a routing domain or a virtual network. Each link 22, 24, 26 is labeled with an associated link cost, such as “1,” “5,” etc., which is stored in a routing database at each node in association with information identifying the links. Each node A, B, D, X, Y comprises one or more hardware or software elements that individually or collectively implement the processes described herein.
For example, with reference to FIG. 1, a first node A is communicatively coupled to an adjacent second node B by link 22, and a third node X is coupled to node A by link 28. When node X needs to forward a packet to node A, in normal operation X will forward the packet using link 28, because the cost of link 28 is “1” whereas the cost of following links 26, 24, 23, 22 to node A is “8.” When the adjacent component comprising link 22 fails or is deactivated in any other manner such as planned downtime or diverting around a congested link, node A advertises this, incrementally increasing the associated link cost 1 in its routing database, waits for the advertisement to propagate and then increments the associated link cost again. As a result, after the first advertised increment has reached node X then node X will forward the packet to node A as this is still the lowest cost route. The packet is lost but this is preferable to setting up a bandwidth consumed loop as higher level reliable transport protocols will cause node X to resend the packet to node A.
Once the first increment has reached all of the nodes, then as nodes X and Y “see” the same cost for link 22 the link cost can be incremented again and advertised.
cost from X to D via A, B cost from X to D via Y, and
cost from Y to D not via X cost from Y to D via XAB.
This can be represented mathematically:
x+i L+y and
y L+x.
In the more general case still there may be multiple failures. In a first case, where m “additive” increments occur in a common path, then the condition for freedom from loops is:
One instance where this can take place is if a node fails as this will cause the simultaneous failure of all links to it. In a case where the node only has two links then the normal condition applies for the minimum increment, i.e., m=1, as the failures are not “additive,” i.e., they do not lie in the same path (which is broken by the failed node). Where there are more than two links to a node then it is possible for additive increments to take place but the maximum value of m is m=2 as no more than two links can lie in a common path through the failed node. As a result in a network having m concurrent link failures and n concurrent node failures (assuming that they must be additive as the worst case scenario, the inequality to avoid loops is (m+2n) i less than 2L.
As a further optimization it will be recognized that any increments in a failed link cost will only affect links lying on a common path with the failed link. Thus, rather than identifying the smallest link cost on the network, only the smallest link cost in the reverse spanning tree rooted at the far end of the failed link, and which traverses the failed link, is considered. The “reverse spanning tree”, sometimes termed a “sink tree,” shows the optimum route for each node from which the node is reachable. Accordingly, as shown in block 324, optionally a reverse spanning tree is computed before a link cost increment is computed in block 312. Yet a further optimization is to recompute the reverse spanning tree, and hence the maximum permissible next increment, after each increment. Accordingly, control may transfer to block 324 from block 320, as shown in FIG. 3B, rather than directly from block 320 to block 314. This may result in the previous lowest cost link being excluded as a result of which the maximum increment can be increased. Also, for successive recalculation it is likely that the reverse spanning tree will shrink as less and less lowest cost routes include the increasing cost of the failed link.
Referring again to the test of block 318, it will be recognized that as a further optimization it is not necessary to continue to increment the link cost to infinity especially as the true value which represents infinity can be very high. In fact it is only necessary to increment the cost until a threshold cost at which the cost of the link is such that no nodes in the network will compute a route using it. In the case of link failure this is guaranteed to have occurred when the cost of the AB link has been incrementally increased to the point where it is greater than the minimum cost path from A to B not passing over the link AB. At that point the cost of a failed link can be increased to “infinity” in one final jump. In the case of failure of a node B the link cost is incremented until it is greater than, for all nodes X, the cost of AX via the shortest alternative path less the cost BX, where the values can be easily computed by running an SPF routed at A.
Although the above discussion relates to incremental increases in a link cost when a network component fails or is otherwise taken out of service, the approach can be applied equally in the case where a network component is introduced into service. In conventional systems this would effectively be achieved by advertising a link cost change to the new cost in a single jump down from “infinity” which once again can give rise to loops. In that case, according to the present method, the link cost is first advertised at the upper bound discussed above, i.e. the link cost of the minimum cost path not traversing the new component. This cost is then incrementally decreased, using the same increments and time intervals as for incrementally increasing costs until it reaches the configured value for the link cost. However the node advertising the costs can treat the link throughout as having its final configured cost which can cause data traffic to pass through the link sooner than would otherwise be the case.
In the first instance the change of state of a component such as component failure is detected at the node in any appropriate manner which can be, for example, medium specific. Alternatively a planned component activation or deactivation may be taking place—in either case a link cost advertisement as set out above can be implemented. The amount of the increment and the interval between increments can be calculated as discussed above. To the extent that computation is required based, for example, on network topology, this is in the present example done on-the-fly rather than use up computing time prior to the event making use of the network information in the LSDB at the node although this is an alternative. In the case where the link cost is incrementally increased, once the cost reaches infinity, or in an optimization, an upper bound value as discussed above the node can increase the cost to “infinity” taking the component out of service. Similar considerations apply to bringing a component into service.
The network link typically provides data communication through one or more networks to other data devices. For example, the network link may provide a connection through a local network to a host computer or to data equipment operated by an Internet Service Provider (ISP). The ISP in turn provides data communication services through the worldwide packet data communication network now commonly referred to as the “Internet”. The local network and the Internet both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on the network link and through interface 99, which carry the digital data to and from computer system 80, are exemplary forms of carrier waves transporting the information.
The method steps set out can be carried out in any appropriate order and aspects from the examples and embodiments described juxtaposed or interchanged as appropriate. It will be appreciated that any appropriate routing protocol can be used such as Intermediate System—Intermediate System (IS-IS) or Open Shortest Path First (OSPF). Similarly any appropriate network can provide the platform for implementation of the method.
US10323358 2002-12-17 2002-12-17 Method and apparatus for advertising a link cost in a data communications network Active 2028-03-02 US7792991B2 (en)
US10323358 US7792991B2 (en) 2002-12-17 2002-12-17 Method and apparatus for advertising a link cost in a data communications network
PCT/US2003/034672 WO2004062208B1 (en) 2002-12-17 2003-10-30 Method and apparatus for advertising a link cost in a data communications network
EP20030814616 EP1573987B1 (en) 2002-12-17 2003-10-30 Method and apparatus for advertising a link cost in a data communications network
CN 200380106520 CN100444575C (en) 2002-12-17 2003-10-30 Method and apparatus for advertising a link cost in a data communications network
CA 2509359 CA2509359A1 (en) 2002-12-17 2003-10-30 Method and apparatus for advertising a link cost in a data communications network
US20040117251A1 true US20040117251A1 (en) 2004-06-17
US7792991B2 true US7792991B2 (en) 2010-09-07
ID=32507313
US10323358 Active 2028-03-02 US7792991B2 (en) 2002-12-17 2002-12-17 Method and apparatus for advertising a link cost in a data communications network
US (1) US7792991B2 (en)
CN (1) CN100444575C (en)
CA (1) CA2509359A1 (en)
EP (1) EP1573987B1 (en)
WO (1) WO2004062208B1 (en)
US20120063323A1 (en) * 2005-08-12 2012-03-15 Microsoft Corporation Distributed network management
US20130138764A1 (en) * 2011-11-30 2013-05-30 Soumendu S. Satapathy Method and system for virtual machine data migration
US9628371B2 (en) 2013-04-23 2017-04-18 Cisco Technology, Inc. Controlling routing during scheduled node downtime
US7308506B1 (en) 2003-01-14 2007-12-11 Cisco Technology, Inc. Method and apparatus for processing data traffic across a data communication network
US7580360B2 (en) * 2003-10-14 2009-08-25 Cisco Technology, Inc. Method and apparatus for generating routing information in a data communications network
US7848240B2 (en) * 2004-06-01 2010-12-07 Cisco Technology, Inc. Method and apparatus for forwarding data in a data communications network
US7986640B2 (en) * 2006-07-05 2011-07-26 Cisco Technology, Inc. Technique for efficiently determining acceptable link-based loop free alternates in a computer network
EP2043306B1 (en) * 2007-09-28 2015-04-15 Unify GmbH & Co. KG Method for organising network nodes in a packet-oriented network
US8203938B2 (en) * 2008-05-22 2012-06-19 Level 3 Communications, Llc Multi-router IGP fate sharing
CN101651600B (en) 2008-08-14 2011-11-16 中国移动通信集团设计院有限公司 Method and device for updating link cost in grid network
CN102487352B (en) * 2010-12-02 2014-09-10 中兴通讯股份有限公司 Service distributing method and device
CN103023783B (en) * 2012-12-03 2016-06-29 杭州华三通信技术有限公司 Based data transmission method and apparatus of dvpn
US20170180210A1 (en) * 2015-12-22 2017-06-22 Amazon Technologies, Inc. Shifting network traffic from a network device
US5243592A (en) 1990-10-15 1993-09-07 Digital Equipment Corporation Method and apparatus for distance vector routing on datagram point-to-point links
US5999286A (en) 1997-01-09 1999-12-07 Alcatel Method and system for restoring a distributed telecommunications network
US6321271B1 (en) 1998-12-22 2001-11-20 Lucent Technologies Inc. Constrained shortest path routing method
WO2002006918A2 (en) 2000-07-14 2002-01-24 Telcordia Technologies, Inc. A method, system, and product for preventing data loss and forwarding loops when conducting a scheduled change to the topology of a link-state routing protocol network
WO2002023832A2 (en) 2000-09-12 2002-03-21 Sri International 1002em and method for disseminating topology and link-state information to routing nodes in a mobile ad hoc network
US20020093954A1 (en) 2000-07-05 2002-07-18 Jon Weil Failure protection in a communications network
US6449279B1 (en) 1996-06-03 2002-09-10 Enterasys Networks, Inc. Aggregation of data flows over a pre-established path to reduce connections
US20020136223A1 (en) 2000-12-19 2002-09-26 Ho Ka K. Method and apparatus for interworking PNNI with the signalling and routing protocols used in MPLS networks
US20020171886A1 (en) 2001-03-07 2002-11-21 Quansheng Wu Automatic control plane recovery for agile optical networks
US6507577B1 (en) 1998-11-12 2003-01-14 Nortel Networks Limited Voice over internet protocol network architecture
US6535481B1 (en) 1999-08-20 2003-03-18 Nortel Networks Limited Network data routing protection cycles for automatic protection switching
US20030063613A1 (en) 2001-09-28 2003-04-03 Carpini Walter Joseph Label switched communication network and system and method for path restoration
US20030161338A1 (en) 2002-02-27 2003-08-28 Ng David D. Network path selection based on bandwidth
CN1440159A (en) 2003-03-31 2003-09-03 中国科学院计算机网络信息中心 Control method for layered switching network node region
US20040001508A1 (en) 2002-06-28 2004-01-01 Haihong Zheng Method and system for transmitting data in a packet based communication network
US20040001497A1 (en) 2002-06-27 2004-01-01 Nokia, Inc. Dynamic routing over secure networks
US6690671B1 (en) 1998-08-17 2004-02-10 Marconi Communications, Inc. Load balanced UBR routing in ATM networks
US20040071089A1 (en) 2000-11-21 2004-04-15 Daniel Bauer Costs in data networks
US20040088429A1 (en) 2002-11-02 2004-05-06 Xianlong Luo Constrained path algoritm for transmission network
US20040085894A1 (en) 2002-10-31 2004-05-06 Linghsiao Wang Apparatus for link failure detection on high availability Ethernet backplane
US6744727B2 (en) 2000-08-10 2004-06-01 The University Of Pittsburgh Apparatus and method for spare capacity allocation
US20040190454A1 (en) 2002-12-19 2004-09-30 Anritsu Corporation Mesh network bridges making operable spanning tree protocol and line fault backup protocol in optimized forwarding environment
US20050007950A1 (en) 2003-07-07 2005-01-13 Liu Hua Autumn Methods and devices for creating an alternate path for a bi-directional LSP
US20050031339A1 (en) 2003-07-11 2005-02-10 Chumning Qiao Efficient trap avoidance and shared protection method in survivable networks with shared risk link groups and a survivable network
US6944131B2 (en) 1999-09-27 2005-09-13 Nortel Networks Limited State information and routing table updates in large scale data networks
US20050201273A1 (en) 2004-03-09 2005-09-15 Nec Corporation Label-switched path network with alternate routing control
US6982951B2 (en) 2000-12-21 2006-01-03 At&T Corp. Method for selecting a restoration path in a mesh network
US6993593B2 (en) 2000-10-18 2006-01-31 Nec Corporation Interdomain routing system
US20060031482A1 (en) 2004-05-25 2006-02-09 Nortel Networks Limited Connectivity fault notification
US20060050630A1 (en) 2004-09-09 2006-03-09 Emiko Kobayashi Storage network management server, storage network managing method, storage network managing program, and storage network management system
US20060092941A1 (en) 2004-11-01 2006-05-04 Kazuhiro Kusama Communication path monitoring system and communication network system
US7065059B1 (en) 2001-08-09 2006-06-20 Cisco Technology, Inc. Technique for restoring adjacencies in OSPF in a non-stop forwarding intermediate node of a computer network
US20070011284A1 (en) 2002-02-21 2007-01-11 France Telecom Sa Dynamic distributed method for local protection of a label switching path
US20070038767A1 (en) 2003-01-09 2007-02-15 Miles Kevin G Method and apparatus for constructing a backup route in a data communications network
US7248579B1 (en) 2002-10-15 2007-07-24 Cisco Technology, Inc. System and method for providing a link state database (LSDB) snapshot for neighbor synchronization
US7349427B1 (en) 2001-12-21 2008-03-25 Nortel Networks Limited Routing method and apparatus for optimising auto-tunnelling in a heterogeneous network
US7344607B2 (en) * 1999-07-08 2008-03-18 Ge Betz, Inc. Non-chromate conversion coating treatment for metals
CN2508474Y (en) * 2001-12-03 2002-08-28 成都鼎天计算机数据设备有限公司 Wide band edge router
KR100472952B1 (en) * 2002-10-30 2005-03-10 한국전자통신연구원 A SIP(Session Initiation Protocol) Load Balancing Apparatus and Method
US20020116669A1 (en) 2001-02-12 2002-08-22 Maple Optical Systems, Inc. System and method for fault notification in a data communication network
AU Examiner's First Report for foreign patent application No. 2004311004 dated Jun. 23, 2008 (1 pg).
AU Examiner's Second Report for foreign patent application No. 2004311004 dated Aug. 18, 2008 (1 pg).
Canadian Intellectual Property Office, Office Action, foreign application No. 2,509,359, 3 pages.
Canadian Intellectual Property Office. Requisition. Method and Apparatus For Advertising a Link Cost In a Data Communications Network. Application No. 2509359. Mar. 26, 2008, pp. 1-3.
Claims, application No. 2,509,359, 3 pages.
Claims, application No. EP 04795045, 4 pages.
Current claims for AU foreign patent application No. 2004311004 (6 pgs).
Current claims for CN foreign patent application No. 200480033007.8 (6 pgs).
Current Claims, Application No. 04795045.6-2416, 5 pages.
Current Claims, PCT/US04/33827, 6 pages.
Current Claims-Application No. 05749440.3 dated Jan. 2010 (3 pages).
Current Claims—Application No. 05749440.3 dated Jan. 2010 (3 pages).
European Patent Office, "Communication pursuant to Article 94(3) EPC", Application No. 04795045.6-2416, dated Sep. 7, 2009, 5 pages.
European Patent Office, "Supplementary European Search Report", application No. EP 04795045, May 27, 2009, 4 pages.
European Search Report in Application No. 05749440.3 dated Dec. 4, 2009 (3 pages).
Fei Dai et al., "On Independently Finding Converging Paths in Internet," 2001, pp. 1-13.
International Searching Authority, International Search Report, PCT/US04/33827, dated Mar. 28, 2005, 8 pages.
ISO/IEC 10589: "Information technology-Telecommunications and information exchange between systems-Intermediate System to Intermediate System intra-domain routeing information exchange protocol for use in conjunction with the protocol for providing the connectionless-mode network service", (ISO 8473), Second edition, Nov. 15, 2002, 208 pages.
ISO/IEC 10589: "Information technology—Telecommunications and information exchange between systems—Intermediate System to Intermediate System intra-domain routeing information exchange protocol for use in conjunction with the protocol for providing the connectionless-mode network service", (ISO 8473), Second edition, Nov. 15, 2002, 208 pages.
Jie Wu et al., "An Extended Fault-Tolerant Link-State Routing Protocol in the Internet," 2001, 7 pages.
Mikkel Thorup, "Fortifying OSPF/IS-IS against link-failure," Sep. 7, 2001, pp. 01-10. *
Mikkel Thorup, "Fortifying OSPF/IS-IS against link-failure," Sep. 7, 2001, pp. 1-10.
Office Action from CN for foreign application No. 200480033007.8 dated Apr. 11, 2008 (10 pgs) with English translation (11 pgs).
Paolo Narváez et al., "Fault-Tolerant Routing in the Internet without Flooding," 1998, pp. 1-13.
Paolo Narváez et al., "Local Restoration Algorithm for Link-State Routing Protocols," 1998, 6 pages.
Raju et al., "A New Approach to On-Demand Loop-Free Multipath Routing", Computer Communications and Networks, 1999, IEEE, Oct. 1999, XP010359531, ISBN: 978-0-7803-5794-5, 6 pages.
Takuya Yoshihiro, "Design and Analysis of Routing Algorithms toward the Next Generation Internet," Dec. 2002, 98 pages.
Wang, Zheng et al., "Shortest Path First with Emergency Exits," ACM 089791-405-8/90/0009/0166, 1990, pp. 166-176.
Zheng Wang et al., "Shortest Path First with Emergency Exists," ACM 089791-405-8/90/0009/0166, 1990, pp. 166-176. *
US7969890B2 (en) * 2003-10-01 2011-06-28 Genband Us Llc Methods, systems, and computer program products for load balanced and symmetric path computations for VoIP traffic engineering
US8649380B2 (en) * 2005-08-12 2014-02-11 Microsoft Corporation Distributed network management
CN100444575C (en) 2008-12-17 grant
US20040117251A1 (en) 2004-06-17 application
EP1573987A1 (en) 2005-09-14 application
EP1573987B1 (en) 2016-10-19 grant
WO2004062208A1 (en) 2004-07-22 application
CA2509359A1 (en) 2004-07-22 application
WO2004062208B1 (en) 2005-01-06 application
CN1736064A (en) 2006-02-15 application
Shand et al. 2010 IP fast reroute framework
US6671819B1 (en) 2003-12-30 System and methods routing packets on alterate paths
US6973023B1 (en) 2005-12-06 Method for routing information over a network employing centralized control
US7002917B1 (en) 2006-02-21 Method for path selection in a network
US7423995B1 (en) 2008-09-09 Criteria for tearing down network links
US20060253561A1 (en) 2006-11-09 Method and apparatus for fast re-configuration of a network topology
US20060171331A1 (en) 2006-08-03 System and methods for network path detection
US20070214280A1 (en) 2007-09-13 Backup BGP paths for non-multipath BGP fast convergence
US7417947B1 (en) 2008-08-26 Routing protocol failover between control units within a network router
US20020172157A1 (en) 2002-11-21 Method and system for fast computation of routes under multiple network states with communication continuation
US6871235B1 (en) 2005-03-22 Fast path forwarding of link state advertisements using reverse path forwarding
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:SHAND, IAN MICHAEL CHARLES;REEL/FRAME:013609/0722