Multiplex communications – Pathfinding or routing – Store and forward
Reexamination Certificate
1999-11-29
2003-07-22
Yao, Kwang Bin (Department: 2664)
Multiplex communications
Pathfinding or routing
Store and forward
C370S432000
Reexamination Certificate
active
06597703
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to communication systems, and more particularly to reducing multicast forwarding states in a multicast communication system.
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 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 a number of multicast routers. For convenience, the path through the various multicast routers is referred to as the “multicast distribution tree” for the (S,G) pair. The multicast routers utilize various multicast routing protocols, such as Multicast Open Shortest-Path First (MOSPF), Distance Vector Multicast Routing Protocol (DVMRP), Protocol Independent Multicast (PIM), or Multicast Border Gateway Protocol (MBGP), in order to determine the multicast distribution tree for the (S,G) pair.
More specifically, a router runs multicast routing protocols in order to determine multicast routing information. The router maintains the multicast routing information in a routing table called a Multicast Routing Information Base (MRIB). The DVMRP routing table and the-MBGP routing table are examples of a MRIB. For multicast routing protocols such as MOSPF and PIM that do not inherently utilize a multicast routing table, the unicast routing table is used as the MRIB. Each interface may have a separate MRIB.
Using the multicast routing information in the MRIB(s), the router sets up multicast forwarding states that define how the router forwards multicast packets. These multicast forwarding states are maintained by a Multicast Table Manager (MTM) in a multicast forwarding table. Each multicast forwarding entry in the multicast forwarding table corresponds to a particular (S,G) pair, and defines the inbound and outbound interfaces for the (S,G) pair.
Some multicast routing protocols, such as PIM, allow the router to forward multicast packets from any multicast source to a particular multicast group G. Such a multicast forwarding state is designated a (*,G) forwarding state. As with any other (S,G) pair, the MTM maintains a multicast forwarding entry for the (*,G) forwarding state. For convenience, a multicast forwarding entry for the (*,G) state is referred to hereinafter as a “default” multicast forwarding entry, while other multicast forwarding entries are referred to hereinafter as “non-default” multicast forwarding entries.
Each multicast forwarding entry includes, among other things, an inbound list indicating the accepted (preferred) and rejected inbound interfaces for the (S,G) pair and an outbound list indicating the outbound interfaces for the (S,G) pair. If a particular (S,G) pair has multiple accepted (preferred) inbound interfaces, particularly due to different multicast routing protocols running on different interfaces, the MTM determines a most-preferred inbound interface from among the accepted (preferred) inbound interfaces. In order to support certain multicast routing protocols, such as PIM, each outbound interface in the outbound list may be associated with a source list indicating the multicast sources that are associated with the outbound interface.
When the router receives a multicast packet for (S,G) from a particular interface, the router searches the multicast forwarding table for a corresponding multicast forwarding entry and processes the multicast packet accordingly. In a typical multicast communication network, it is common for a multicast forwarding table to have a large number of multicast forwarding entries. The large number of multicast forwarding entries makes the multicast forwarding table very large, and also makes searching the multicast forwarding table for the multicast forwarding entry a relatively time-consuming operation.
Thus, a need has remained for a technique that reduces the number of multicast forwarding states in a multicast routing device, and more particularly for a technique that reduces the number of multicast forwarding entries in the multicast forwarding table.
SUMMARY OF THE INVENTION
In accordance with one aspect of the invention, forwarding states are maintained in such a way that all non-default forwarding states are non-overlapping.
In accordance with another aspect of the invention, a prefix is assigned to each forwarding state. The source address S and the prefix together define the source address range for the forwarding state. The prefix is assigned in such a way that the source address range defined by S/prefix does not overlap with the source address ranges of any other non-default forwarding state.
In accordance with yet another aspect of the invention, a non-overlapping prefix is determined by finding an enclosing range for S (the matching range) that contains a number of more-specific enclosing ranges, where each enclosing range is characterized by a lower boundary and an upper boundary; determining a maximum upper boundary within the matching range that is less than or equal to S; determining a minimum lower boundary within the matching range that is greater than or equal to S; and determining the minimum prefix such that the lower boundary of the source address range defined by S/prefix is greater than or equal to the maximum upper boundary and the upper boundary of the source address range defined by S/prefix is less than or equal to the minimum lower boundary.
In accordance with still another aspect of the invention, a the source address range of a fowarding state is adjusted when a new route is detected or an existing route changes or is aged.
REFERENCES:
patent: 5517494 (1996-05-01), Green
patent: 5959989 (1999-09-01), Gleeson et al.
patent: 6331983 (2001-12-01), Haggerty et al.
Deering, et al., “A taxonomy of multicast security issues”, The Internet Engineering Task Force(www.ietf.org), Internet-Draft, Jun. 7, 1999.
Estrin, et al., “Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification.” The Internet Engineering Task Force(www.ietf.org), Request for Comments, Jun. 1998.
Li Yunzhou
Shieh Shuching
Nortel Networks Limited
Steubing McGuinness & Manaras LLP
Yao Kwang Bin
LandOfFree
System, device, and method for reducing multicast forwarding... 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 multicast forwarding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, device, and method for reducing multicast forwarding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3078042