Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Routing data updating
Reexamination Certificate
1999-02-25
2003-10-07
Najjar, Saleh (Department: 2157)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Routing data updating
C709S235000, C709S239000, C709S240000, C709S241000, C709S243000, C370S254000, C370S408000
Reexamination Certificate
active
06631420
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to communication systems, and more particularly to reducing reconvergence time by a Protocol Independent Multicast (PIM) router.
BACKGROUND OF THE INVENTION
In today's information age, communication networks are often used for transporting information from an information provider to one or more information consumers.
One technique for transporting information from an information provider to a group of information consumers over the communication network is known as “multicasting.” Multicasting allows the information provider (referred to hereinafter as a “multicast source”) to transmit a single unit of multicast information (referred to hereinafter as a “multicast packet”) simultaneously to all information consumers (referred to hereinafter individually as a “multicast client” and collectively as “multicast clients”) in the multicast group, specifically by addressing the multicast packet to the multicast group using a multicast address. The multicast clients monitor the communication network for multicast packets addressed to the multicast group.
In order to transport a multicast packet from the multicast source to the multicast clients, the multicast packet is routed through the communication network by a number of multicast routers. The multicast routers utilize a specific multicast routing protocol to determine a multicast distribution tree by which the multicast packet is distributed.
One such multicast routing protocol is the Protocol Independent Multicast—Sparse Mode (PIM-SM) protocol, which is described in the document Internet Engineering Task Force (IETF) Request For Comments (RFC) 2362 entitled
Protocol Independent Multicast—Sparse Mode
(
PIM
-
SM
):
Protocol Specification
and published in June 1998, hereby incorporated by reference in its entirety. In accordance with the PIM-SM protocol, the various routers within a particular PIM-SM domain establish a default multicast distribution tree, referred to as a “shared tree,” for each multicast group. Each shared tree is rooted at a Rendezvous Point (RP) router that acts as the distribution point of all multicast packets for the multicast group. Before a router can join the shared tree for a particular multicast group, the router must learn the identity of the multicast group RP router. A router learns the identity of the multicast group RP router by receiving a PIM Bootstrap Message including a list of all RP routers in the PIM-SM domain. The router receives the PIM Bootstrap Message either from a Bootstrap Router, which sends the PIM Bootstrap Message to all routers in the PIM-SM domain at predetermined intervals (typically every 60 seconds), or from a neighboring router, which sends the PIM Bootstrap Message to the router if and only if the neighboring router has lost contact with the router for a predetermined period of time (typically 105 seconds). Upon learning the identity of the multicast group RP router, or at any time thereafter, each router that supports a downstream multicast group member (i.e., multicast client) joins the shared tree by sending a PIM Join/Prune Message hop-by-hop toward the multicast group RP router. Each intermediate router that receives the PIM Join/Prune Message from a downstream router also joins the shared tree by forwarding the PIM Join/Prune Message toward the multicast group RP router.
In order to distribute multicast packets for a particular multicast group, each multicast source sends multicast packets to the corresponding multicast group RP router, which in turn forwards the multicast packets according to the shared tree. Each router that receives the multicast packets, including the multicast group RP router, forwards the multicast packets to any and all neighboring routers from which it received the PIM Join/Prune Message. In this way, the multicast packets are only distributed to routers that support a downstream multicast group member.
In order to maintain the shared tree, each router sends a PIM Hello message to its neighboring router(s) at predetermined intervals (typically every 30 seconds). The PIM Hello messages allow a particular router to determine whether or not a particular neighboring router is operational. If a particular router fails to receive a PIM Hello message from a particular neighboring router within a predetermined period of time (typically 105 seconds), then the neighboring router is considered to have failed.
When a router in the shared tree reboots, it can take a substantial amount of time for the rebooted router to reconverge such that it resumes forwarding multicast packets for the multicast group. This is because the rebooted router must at least learn the identity of the multicast group RP router before it can forward any multicast packets over the shared tree. In a typical PIM-SM implementation, a Bootstrap Router in the PIM-SM domain sends a PIM Bootstrap Message identifying each RP router in the PIM-SM domain every 60 seconds, so it can take up to 60 seconds for the rebooted router to learn the identity of the multicast group RP router. After learning the identity of the multicast group RP router, the rebooted router may then need to learn the forwarding states for any downstream multicast group members (i.e., the rebooted router needs to create the appropriate routing entries for forwarding multicast packets to any downstream multicast group members). In a typical PIM-SM implementation, each neighboring router that supports a downstream multicast group member sends a PIM Join/Prune Message every 60 seconds, so it can take up to 60 second for the rebooted router to learn the forwarding states for any downstream multicast group members after learning the identity of the multicast group RP router. Therefore, in a worst case scenario, it can take up to 120 seconds for the rebooted router to reconverge, during which time all multicast packets received by the rebooted router are dropped. Additionally, in most cases, the neighboring router(s) will consider the rebooted router to be operational, since the rebooted router typically becomes operational and resumes sending PIM Hello messages before the neighboring router(s) detect the failure (i.e., within 105 seconds).
Thus, a technique for reducing reconvergence time following a router reboot is needed.
SUMMARY OF THE INVENTION
In accordance with one aspect of the invention, a reconverging router in a PIM-SM domain sends to a neighboring router a reconvergence message including a reconvergence indicator. The reconvergence message is preferably a PIM Hello Message, and the reconvergence indicator is preferably a randomly selected Generation Identifier value that is included in a novel Generation Identifier Option field within the PIM Hello Message. The reconverging router receives from the neighboring router a PIM Bootstrap Message identifying the Rendezvous Point routers in the PIM-SM domain. Additionally, the reconverging router sends to the neighboring router a PIM Join/Prune Message for each multicast group for which the reconverging router supports a directly connection multicast group member.
In accordance with another aspect of the invention, a neighboring router in a PIM-SM domain receives from a reconverging router a reconvergence message including a reconvergence indicator. The reconvergence message is preferably a PIM Hello Message, and the reconvergence indicator is preferably a randomly selected Generation Identifier value that is included in a novel Generation Identifier Option field within the PIM Hello Message. The neighboring router sends to the reconverging router a PIM Bootstrap Message identifying the, Rendezvous Point routers in the PIM-SM domain. Additionally, the neighboring router sends to the reconverging router a PIM Join/Prune Message for each multicast group for which the neighboring router supports a downstream multicast group member.
REFERENCES:
patent: 5361256 (1994-11-01), Doeringer et al.
patent: 5574860 (1996-11-01), Perlman et al.
patent: 5946316 (1999-08-01), Chen et al.
patent: 5963540 (1999-10-01
Li Yunzhou
Ng Billy
Najjar Saleh
Nortel Networks Limited
Steubing McGuinness & Manaras LLP
LandOfFree
Reducing convergence time by a protocol independent... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reducing convergence time by a protocol independent..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reducing convergence time by a protocol independent... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3170282