Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-10-28
2004-09-14
Olms, Douglas (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
Reexamination Certificate
active
06791980
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to communication systems, and more particularly to reducing the number of multicast routes maintained by a multicast routing device in a multicast communication network.
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 fore multicast packets addressed to the multicast group.
In order to distribute multicast packets from a particular multicast source S to the multicast clients for a particular multicast group G, the multicast packet is routed through the communication network by a number of routers. The communication network may include multiple routing domains, and therefore the multicast packet may traverse multiple routing domains. Each router runs various routing protocols to determine, among other things, a “next hop” for each packet based upon address information in the packets. Such routing information is used to establish a multicast distribution tree, and is maintained by each router in one or more routing tables (often referred to as a “routing information base”). In particular, each router maintains a unicast routing information base (URIB) that is used to determine the “next hop” for unicast packets. Also, each multicast router maintains a multicast routing information base (MREB) that is used to determine the “next hop” for multicast packets.
One well-known protocol for routing multicast packets within a multicast routing domain is known as Protocol Independent Multicast (PIM). PIM is so named because it is not dependent upon any particular unicast routing protocol for setting up a multicast distribution tree within the multicast routing domain. PIM has two modes of operation, specifically a sparse mode and a dense mode. PIM Sparse Mode (PIM-SM) 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. PIM Dense Mode (PIM-DM) is described in an Internet Draft of the Internet Engineering Task Force (IETF) entitled
Protocol Independent Multicast Version
2
Dense Mode Specification
, document draft-ietf-pim-v2-dm-03.txt (Jun. 7, 1999), hereby incorporated by reference in its entirety
In accordance with the PIM protocol, the various routers within a particular PIM 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 domain. The router receives the PIM Bootstrap Message either from a Bootstrap Router (BSR), which sends the PIM Bootstrap Message to all routers in the PIM 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.
The PIM domain may have a number of source networks that belong to the PIM domain itself. Multicast packets that originate within such intradomain source networks are not routed to other PIM domains. The routes associated with such intradomain source networks (referred to hereinafter as intra-source routes) are distributed by a unicast routing protocol and maintained in the URIB.
In order to route the multicast packet between PIM domains, border routers in each PIM domain (each referred to hereinafter as a Multicast Border Gateway Protocol or MBGP router) determine interdomain routes (referred to hereinafter as MBGP routes) for the (source, group) pair. The MBGP router is typically a Multicast Source Discovery Protocol (MSDP) router or a PIM Multicast Border Router (PMBR) that functions as a Border Gateway Protocol (BGP) router to receive and install MBGP routes. MSDP, PMBR, and BGP are described in IETF documents and are well-known in the art.
A multicast communication network may have a large number of multicast routes. Within a particular multicast router, the number of multicast routes affects the size of the MRIB (i.e., the amount of memory consumed by the MRIB), which in turn affects the time required to search the MREB for a particular multicast route. The number of multicast routes also affects the inter-router communication overhead required to distribute multicast routes among the various routers.
Thus, a need has remained for a technique that reduces the number of multicast routes maintained in the MRIB.
SUMMARY OF THE INVENTION
In accordance with one aspect of the invention, a single policy route is installed in the MRIB in place of multiple multicast routes. The policy route may be an aggregation of multicast routes that do not have a next hop device, or the policy route may be an aggregation of multicast routes for which the next hop device can be determined from the corresponding unicast routes. The policy route includes an indicator indicating whether the policy route is an aggregation of multicast routes that do not have a next hop device, in which case the policy route is designated a rejected policy route, or an aggregation of multicast routes for which the next hop device can be determined from the corresponding unicast routes, in which case the policy route is designated an accepted policy route.
In accordance with another aspect of the invention, a bootstrap router (BSR) collects policy routes and distributes the policy routes using a bootstrap message. In a preferred embodiment, the BSR router periodically sends a bootstrap message including all policy routes, and also sends a bootstrap message including only changed policy routes whenever the BSR router detects a policy route change. The bootstrap messages are propagated to all PIM routers in the PIM domain.
In accordance with another aspect of the invention, a router that receives a bootstrap message installs the policy routes in its MRIB.
In accordance with another aspect of the invention, the router finds the best, most-specific multicast route in the MREB for a source address, and uses the corresponding unicast route to determine the next hop device for the source address if the most-specific multicast route is an accepted policy route.
In accordance with another aspect of the invention, the router finds the best, mostspecific multicast route in the MRIB for a source address, and determines that there is no
Nortel Networks Ltd
Olms Douglas
Steubing McGuinness & Manaras LLP
Wilson Robert W.
LandOfFree
System, device, and method for reducing the number of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System, device, and method for reducing the number of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, device, and method for reducing the number of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3227156