Source: http://www.google.com/patents/US20080192762?dq=6,304,975
Timestamp: 2017-12-14 03:04:34
Document Index: 737935273

Matched Legal Cases: ['§ 119', '§ 112', '§ 1', '§ 1', '§ 1', '§ 1', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4']

Patent US20080192762 - Graceful restart for use in nodes employing label switched path signaling ... - Google Patents
When a node has to restart its control component, or a (e.g., label-switched path signaling) part of its control component, if that node can preserve its forwarding information across the restart, the effects of such restarts on label switched path(s) the include the restarting node are minimized. A...http://www.google.com/patents/US20080192762?utm_source=gb-gplus-sharePatent US20080192762 - Graceful restart for use in nodes employing label switched path signaling protocols
Publication number US20080192762 A1
Application number US 12/101,245
Also published as US7359377, US7903651, US8693471, US20110128968
Publication number 101245, 12101245, US 2008/0192762 A1, US 2008/192762 A1, US 20080192762 A1, US 20080192762A1, US 2008192762 A1, US 2008192762A1, US-A1-20080192762, US-A1-2008192762, US2008/0192762A1, US2008/192762A1, US20080192762 A1, US20080192762A1, US2008192762 A1, US2008192762A1
Inventors Kireeti Kompella, Manoj Leelanivas, Ping Pan, Yakov Rekhter
Original Assignee Kireeti Kompella, Manoj Leelanivas, Ping Pan, Yakov Rekhter
Patent Citations (28), Referenced by (58), Classifications (5), Legal Events (2)
US 20080192762 A1
1. A computer-implemented method for use in a data forwarding node including stored label information, a control component for generating and maintaining forwarding information based on the stored label information, and a forwarding component for forwarding information along a switched path based, at least in part, on the forwarding information, wherein the data forwarding node can preserve forwarding information across the restart of the control component, and can belong to a switched path, the computer-implemented method comprising advertising the fact that the data forwarding node can preserve forwarding information across the restart of the control component to at least one other node that belongs to the switched path.
tracking, using a timer, a time that the data forwarding node will keep and use any preserved forwarding information after the restart of the control component.
deleting any entries in the forwarding information that are indicated as being preserved across the restart of the control component if the timer expires.
4. The computer-implemented method of claim 1 wherein the switched path is a label-switched path, and wherein the forwarding information includes entries, each of the entries including an IN label and one of (a) an OUT label and (b) an address, the computer-implemented further comprising:
7. The computer-implemented method of claim 1 wherein the switched path is a label-switched path, and wherein the forwarding information includes entries, each of the entries including an IN label and one of (a) an OUT label and (b) an address, the computer-implemented method further comprising:
10. The computer-implemented method of claim 1 wherein the switched path is a label-switched path, and wherein the forwarding information includes entries, each of the entries including an IN label and one of (a) an OUT label and (b) an address, the computer-implemented method further comprising:
creating a new entry, including the accepted label, to the forwarding information in a previously unallocated entry; any
11. A computer-implemented method for use in a data forwarding node which is a part of a switched path including a second data forwarding node, the second data forwarding node including a control component for generating and maintaining forwarding information, and being able to preserve forwarding information across the restart of the control component, the computer-implemented method comprising:
accepting an advertisement from the second data forwarding node, the advertisement communicating the fact that the second data forwarding node is capable of preserving forwarding information across the restart of the control component;
if it is determined that the control component of the second data forwarding node is down, then
deleting any entries in the forwarding information that are indicated as being provided before the restart of the control component of the second data forwarding node if the first timer expires.
14. The computer-implemented method of claim 13 wherein the second timer is selected to be a shorter one of (A) a predetermined value, and (B) a restart time advertised by the second data forwarding node.
deleting any entries in the forwarding information that are indicated as being provided before the restart of the control component of the second data forwarding node if it was determined that the second data forwarding node was not able to preserve its forwarding information across the restart of its control component.
if a matching label is found, indicating that the entry should not be deleted upon expiration of the first timer, and
17. For use in a data forwarding node including a forwarding component for forwarding information along a switched path based, at least in part, on forwarding information, a control component for generating and maintaining the forwarding information based on the stored label information, wherein the data forwarding node can preserve forwarding information across the restart of the control component, and can belong to a switched path, the control component comprising:
2) processor-executable instructions which, when executed by the one or more processors, perform a method comprising advertising the fact that the data forwarding node can preserve forwarding information across the restart of the control component to at least one other node that belongs to the switched path.
18. The control component of claim 17 wherein the one or more storage devices further store processor-executable instructions which, when executed by the one or more processors, perform a method further comprising:
19. The control component of claim 18 wherein the one or more storage devices further store processor-executable instructions which, when executed by the one or more processors, perform a method further comprising:
20. Apparatus for use in a data forwarding node which is a part of a switched path including a second data forwarding node, the second data forwarding node including a control component for generating and maintaining forwarding information, and being able to preserve forwarding information across the restart of the control component, the apparatus comprising:
5) accepting an advertisement from the second data forwarding node, the advertisement communicating the fact that the second data forwarding node is capable of preserving forwarding information across the restart of the control component;
6) if it is determined that the control component of the second data forwarding node is down, then
This application is a continuation of U.S. patent application Ser. No. 10/095,000, titled “GRACEFUL RESTART FOR USE IN NODES EMPLOYING LABEL SWITCHED PATH SIGNALING PROTOCOLS,” filed on Mar. 11, 2002, and listing Kireeti KOMPELLA, Manoj LEELANIVAS, Ping PAN, and Yakov REKHTER as the inventors, which application claims benefit, under 35 U.S.C. § 119(e)(1), to the filing dates of: (i) provisional patent application Ser. No. 60/299,813, entitled “GRACEFUL RESTART MECHANISM FOR RSVP-TE”, filed on Jun. 19, 2001 and listing Ping Pan, Yakov Rekhter, and Kireeti Kompella as the inventors; (ii) provisional patent application Ser. No. 60/325,099, entitled “GRACEFUL RESTART MECHANISM FOR LDP”, filed on Sep. 25, 2001, and listing Manoj Leelanivas and Yakov Rekhter as the inventors; and (iii) provisional patent application Ser. No. 60/327,402, entitled “GRACEFUL RESTART MECHANISM FOR BGP WITH MPLS”, filed on Oct. 4, 2001, and listing Yakov Rekhter and Manoj Leelanivas as inventors, for any inventions disclosed in the manner provided by 35 U.S.C. § 112, ¶ 1. The utility application and the three provisional applications are expressly incorporated herein by reference. However, any limiting statements made in the provisions are directed to the specific embodiments described in those provisional applications, and not necessarily to the present invention. Rather, these provisional applications should be considered to describe exemplary embodiments of the invention.
The description of art in this section is not, and should not be interpreted to be, an admission that such art is prior art to the present invention. Although one skilled in the art will be familiar with networking, circuit switching, packet switching, label switched paths, and protocols such as BGP, RSVP, MPLS, and LDP, each is briefly introduced below for the convenience of the less experienced reader. More specifically, circuit switched and packet switched networks are introduced in § 1.2.1. The need for label switched paths, as well as their operation and establishment, are introduced in §§ 1.2.2-1.2.4 below. Finally, “failures” in a label switched path, as well as typical failure responses, are introduced in § 1.2.5 below.
In the MPLS domain, the label-switching routers (LSRs) 220 ignore the packet's network layer header and simply forward the packet using label-swapping. More specifically, when a labeled packet arrives at a label-switching router (LSR), the input port number and the label are used as lookup keys into an MPLS forwarding table. (See, e.g., FIG. 5. Note that column 550 of FIG. 5 is a novel aspect of the present invention, and is therefore not provided in conventional tables.) When a match is found, the forwarding component retrieves the associated outgoing label, the outgoing interface (or port), and the next hop address from the forwarding table. The incoming label is replaced with the outgoing label and the packet is directed to the outgoing interface for transmission to the next hop in the label-switched path. FIG. 2 illustrates such label-switching by label-switching routers (LSRs) 220 a and 220 b.
When the labeled packet arrives at the egress label-switching router, if the next hop is not a label-switching router, the egress label-switching router discards (“pops”) the label and forwards the packet using conventional longest-match IP forwarding. FIG. 2 illustrates such label discarding and IP forwarding by egress label-switching router 240.
§ 1.2.5 Responding to “Failures” in a Label Switched Path
Sometimes, a control component part of a router in a label switch path, or a part of the control component, will restart. Such a restart may be caused, for example, by upgrading software and/or hardware of the control components, the control component receiving unexpected (path signaling) messages from its neighbor(s), the control component failing to receive expected (path signaling) messages from its neighbor(s), etc. Whatever the cause of the restart, the restarting node will typically purge its forwarding information (Recall, e.g., 320 of FIG. 3.), and will typically lose label information (Recall, e.g., 330 of FIG. 3.). For example, referring back to FIG. 3, if the control component 330 b of node 220 b′ restarts, it will purge stored forwarding information 320 b and will lose label information 340 b. Furthermore, this restart affects other routers in the label-switched paths. For example, when nodes 220 a′ and 240′ learn that the node 220 b′ is restarting, they will purge forwarding information 320 a/320 c related to the path through node 220 b′.
This scenario has at least two disadvantages. First, as shown in FIG. 3, some routers have forwarding components that can, at least theoretically, continue forwarding packets even when their control component, or a part thereof, is restarting. (For example, routers from Juniper Networks Inc. of Sunnyvale, Calif. have a packet forwarding engine and a routing engine.) Second, after the restart is complete, the node and its neighbors need to repopulate their forwarding information. During this period, the label switched path(s) through node 220 b′ cannot be used.
In the following, exemplary environments in which the present invention may operate is described in § 4.1. Then high-level operations that may be performed by the present invention are introduced in § 4.2. Thereafter, exemplary apparatus, methods and data structures that may be used to effect those high-level operations are described in § 4.3. Finally, some conclusions regarding the present invention are set forth in § 4.4.
§ 4.2 High-Level Operations that may be Performed by the Present Invention
§ 4.3 Methods, Data Structures, and Apparatus
In the following, exemplary methods and data structures for effecting the operations summarized in § 4.2 are described in § 4.3.1 for a general case, in § 4.3.2 for a case where BGP is used as a signaling protocol, in § 4.3.3 for a case where LDP is used as a signaling protocol, and in § 4.3.4 for a case where RSVP is used as a signaling protocol. The specific cases may depart from the general case in some instances. Then, exemplary apparatus that may be used to effect the functions summarized in § 4.2 are described in §
§ 4.3.1 General Case
Two alternative embodiments are described. In a first, described in § 4.3.1.1, stale forwarding state information is refreshed based on information received from peer node(s) during a certain time period and the stale forwarding state information itself, after which any remaining stale (not refreshed) information is deleted. In a second, alternative, embodiment, described in § 4.3.1.2, stale forwarding state information is used during a certain time period, after which it is deleted. During that time period, new, possibly redundant forwarding state information may have been determined from label binding information received from peer node(s) and the stale forwarding state information itself, and stored, along with the “stale” information. Thus, the first alternative may be thought of as refreshing stale forwarding state information, while the second alternative may be thought of as storing redundant (stale and new) forwarding state information, permitting the use stale (or new) forwarding state information for a certain period of time, after which only new forwarding state information may be used.
§ 4.3.1.1 First Alternative
Regarding the first and second timers, as shown in FIG. 8, note that the first timer 855 can expire after the second timer 880 a, or before the second timer 880 b.
As can be appreciated, in this first alternative, stale (label and related) forwarding information is refreshed by information received from peer node(s) during a certain time period, after which any remaining stale (not refreshed) information is deleted. The second, alternative, embodiment is now described in § 4.3.1.2 below. In that second alternative embodiment, stale (label and related) forwarding information is used during a certain time period, after which it is deleted. During that time period, new, possibly redundant (label and) forwarding information may have been received from peer node(s) and stored, along with the “stale” information.
§ 4.3.1.2 Second Alternative
FIG. 9 is a flow diagram of another graceful restart method 468 a″ that may be effected by a restarting node. Before restart is ever initiated, a node may advertise its capability to preserve forwarding information across a restart as indicated by block 905. Again, a capability to preserve forwarding information across a restart is not a guarantee that it will do so successfully. If the node doesn't restart, it may periodically resend its restart capacity (though this isn't necessary) as indicated by decision branch point 910. When the node restarts, the method 468 a″ continues to 915 where various conditions are monitored for the occurrence of an event or events that are used to trigger further acts by the method 468 a′.
If the restart of the node's control component (or part of the control component related to label-switched paths) is completed, the node will determine whether it was able to preserve its forwarding state as indicated by conditional branch point 920. If not, this fact may be advertised to peer node(s) as indicated by block 922, and the node will rebuild (repopulate) its forwarding state in a normal (i.e., non-graceful) way, as indicated by block 925, before the method 468 a″ is left via RETURN node 990. If, on the other hand, the node was able to preserve its forwarding state across the restart, it may start a forwarding state holding timer, as indicated by block 929, may advertise that it was able to preserve its forwarding state, as indicated by block 932, and may advertise the present value of its forwarding state holding timer as a recovery time, as indicated by block 934, before the method 468 a″ returns to 915. Note that either act 922, act 932, or both may be provided. In the event that only the fact that forwarding state information was not preserved is advertised, peer nodes could infer that such forwarding state information was preserved in the absence of such a message. On the other hand, in the event that only the fact that forwarding state information was preserved is advertised, peer nodes could infer that such forwarding state information was not preserved in the absence of such a message.
§ 4.3.2 Border Gateway Protocol (BGP) Used to Signal Labels
§ 4.3.2.1 First Alternative Embodiment for Use with Border Gateway Protocol (BGP)
§ 4.3.2.2 Second Alternative Embodiment for Use with Border Gateway Protocol (BGP)
§ 4.3.3 Label Distribution Protocol (LDP) Used to Signal Labels
§ 4.3.3.1 First Alternative Embodiment for Use with Label Distribution Protocol (LDP)
§ 4.3.3.2 Second Alternative Embodiment for Use with Label Distribution Protocol (LDP)
§ 4.3.4 Reservation Protocol (RSVP) Used to Signal Labels
US20020163906 * May 4, 2001 Nov 7, 2002 John Diachina Emergency packet data service
US8339942 * Oct 15, 2009 Dec 25, 2012 Telefonaktiebolaget L M Ericsson (Publ) RSVP-TE graceful restart under fast re-route conditions
US8848712 * Aug 10, 2009 Sep 30, 2014 Infinera Corporation Distributed RSVP-TE in a multi-chassis node architecture
US8953437 * Jan 4, 2012 Feb 10, 2015 Juniper Networks, Inc. Graceful restart for label distribution protocol downstream on demand
US20080317045 * Aug 17, 2006 Dec 25, 2008 Gang Chen Method and System for Providing Differentiated Service
US20100284268 * May 7, 2009 Nov 11, 2010 Shan Zhu Node State Recovery for a Communication Network
US20100284269 * May 7, 2009 Nov 11, 2010 Shan Zhu Multi-Node State Recovery for a Communication Network
US20110032938 * Aug 10, 2009 Feb 10, 2011 Infinera Corporation Distributed rsvp-te in a multi-chassis node architecture
US20110090786 * Oct 15, 2009 Apr 21, 2011 Telefonaktiebolaget L M Ericsson Rsvp-te graceful restart under fast re-route conditions
EP2686990A1 * Mar 14, 2012 Jan 22, 2014 Hangzhou H3C Technologies Co., Ltd. Switching to a backup traffic path by a label switching router in a multi-protocol label switching network
EP2686990A4 * Mar 14, 2012 Aug 13, 2014 Hangzhou H3C Tech Co Ltd Switching to a backup traffic path by a label switching router in a multi-protocol label switching network
WO2012122936A1 Mar 14, 2012 Sep 20, 2012 Hangzhou H3C Technologies Co., Ltd Switching to a backup traffic path by a label switching router in a multi-protocol label switching network
Cooperative Classification H04L45/50
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:KOMPELLA, KIREETI;LEELANIVAS, MANOJ;PAN, PING;AND OTHERS;SIGNING DATES FROM 20020212 TO 20020222;REEL/FRAME:036679/0869