Patent Publication Number: US-8976788-B2

Title: Data plane independent assert election

Description:
CROSS REFERENCE TO OTHER APPLICATIONS 
     This application is a continuation of co-pending U.S. patent application Ser. No. 11/496,995, entitled DATA PLANE INDEPENDENT ASSERT ELECTION filed Jul. 31, 2006 which is incorporated herein by reference for all purposes. 
    
    
     BACKGROUND OF THE INVENTION 
     Multicast routing protocols, such as the Protocol Independent Multicast-Sparse Mode (PIM-SM) protocol, are used to distribute multicast traffic efficiently. PIM-SM is designed to route multicast packets to widely distributed and sparsely populated multicast groups efficiently via transmission paths that include Ethernet-based segments such as local area networks (LANs), wide area networks (WANs), and RFC 2547 and/or other virtual private networks and similar services that provide LAN or LAN-like connectivity across provider or other networks. Routers that desire to receive multicast traffic associated with a multicast group subscribe to the group. In PIM-SM, a router that receives a request to subscribe to a multicast group sends to an upstream router nearer the source a “join” message, to let the upstream router know that the downstream router needs to receive multicast traffic associated with the group. The join message is sent as a link-local multicast packet but the message specifies an upstream neighbor to which the request is directed. Per the PIM-SM protocol specification, only the router specified in the join request processes the request. If other routers wishing to join the same multicast group also have chosen the same upstream neighbor for that group, then such routers suppress their own joins upon seeing a Join on the LAN. On the other hand, if a router wishing to join the same multicast group has chosen a different upstream neighbor for that group, then such a router will have to send a join request explicitly on the LAN. 
     To avoid the inefficiency of multiple routers forwarding the same multicast traffic on the same LAN or similar segment, PIM-SM and similar protocols provide for routers that detect when duplicate traffic is being sent and perform an “assert” election to determine which of them will forward the multicast traffic via the LAN. Existing mechanisms for detecting that an assert election should be performed require that the PIM-SM router detect that multicast traffic for a group is being received on an interface via which the router is forwarding multicast traffic for the group, i.e., the multicast traffic is received on what the router considers to be an outbound interface for the group. This typically requires either special logic and/or circuitry at the interface or more commonly that multicast traffic received at a LAN or similar interface (part of the data traffic “forwarding plane”) be sent to the control plane for a determination to be made, e.g., by a control processor, as to whether the traffic comprises multicast traffic that is being received on an outbound interface for the multicast group with which the traffic is associated. This interaction between the forwarding plane and control plane consumes control plane resources, can lead to delay, and results in at least some duplicate forwarding of multicast traffic until the condition can be detected and an assert election initiated and completed. Therefore, there is a need for a better way to process multicast traffic. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Various embodiments of the invention are disclosed in the following detailed description and the accompanying drawings. 
         FIG. 1  is a block diagram illustrating an embodiment of a network through which multicast traffic may be distributed. 
         FIG. 2  is a flow chart illustrating an embodiment of a typical prior art process for routing received multicast traffic to a control plane and/or module. 
         FIG. 3  is a flow chart illustrating an embodiment of a typical prior art process for determining whether multicast traffic has been received on an outbound interface. 
         FIG. 4  is a flow chart illustrating an embodiment of a process for triggering a PIM-SM or similar assert election. 
         FIG. 5  is a flow chart illustrating an embodiment of a process for processing received multicast packets. 
     
    
    
     DETAILED DESCRIPTION 
     The invention can be implemented in numerous ways, including as a process, an apparatus, a system, a composition of matter, a computer readable medium such as a computer readable storage medium or a computer network wherein program instructions are sent over optical or communication links. In this specification, these implementations, or any other form that the invention may take, may be referred to as techniques. A component such as a processor or a memory described as being configured to perform a task includes both a general component that is temporarily configured to perform the task at a given time or a specific component that is manufactured to perform the task. In general, the order of the steps of disclosed processes may be altered within the scope of the invention. 
     A detailed description of one or more embodiments of the invention is provided below along with accompanying figures that illustrate the principles of the invention. The invention is described in connection with such embodiments, but the invention is not limited to any embodiment. The scope of the invention is limited only by the claims and the invention encompasses numerous alternatives, modifications and equivalents. Numerous specific details are set forth in the following description in order to provide a thorough understanding of the invention. These details are provided for the purpose of example and the invention may be practiced according to the claims without some or all of these specific details. For the purpose of clarity, technical material that is known in the technical fields related to the invention has not been described in detail so that the invention is not unnecessarily obscured. 
     Initiating an assert election in response to a join message to a peer is disclosed. A join message directed to a peer is received. It is determined whether the join message relates to a multicast group with respect to which an assert election would be triggered if the peer to which the join is directed were to accept and process the join and subsequently forward in the direction of a sender of the join multicast traffic associated with the group. If so, an assert election is initiated in response to the received join message directed to the peer, without waiting for duplicate multicast traffic to be noticed on the outbound interface. 
       FIG. 1  is a block diagram illustrating an embodiment of a network through which multicast traffic may be distributed. In the example shown, network  100  includes a multicast source  102 . In various embodiments, multicast source  102  comprises one or more of the following: a source of multicast traffic, a PIM-SM rendezvous point (RP), and an upstream PIM-SIM or other multicast protocol router common to routers  104  and  106 . Routers R 1 , R 2 , R 3 , and R 4 , also labeled  110 ,  112 ,  104 , and  106 , respectively, comprise PIM-SM routers configured to forward multicast traffic to downstream nodes, e.g., other routers and/or end consumers of the multicast traffic. In the example shown in  FIG. 1 , assume router R 1  has received an indication that one or more downstream nodes desire to receive from router R 1  multicast traffic for a group with which source  102  is associated and R 2  likewise has received an indication that one or more downstream nodes desire to receive from router R 2  multicast traffic for the same group. Under the PIM-SM protocol, each of routers R 1  and R 2  would send, independently of one another, a join message to an upstream neighbor identified by the router (R 1  or R 2 , as applicable), e.g., based on routing table information, as the best or otherwise selected node from which multicast traffic associated with the group should be obtained. Suppose, for example, that router R 1  sent a join to router R 3  and router R 2  subsequently (or previously or at the same time) sent a join to router R 4 . Under PIM-SM, each respective join would be sent via LAN  108  to a multicast address, so that each of routers R 3  and R 4  would “see” each of the two join messages, but only R 3  would process the join request from R 1  and only R 4  would process the join request from R 2 , based on information included in the join message by the sending router indicating which upstream router should process the join. In the example shown, R 3  would arrange to receive from source  102  any multicast traffic for the group identified in the join (if necessary, i.e., if it has not already done so to be able to forward multicast traffic associated with the group to one or more other downstream nodes, other than R 1 , e.g., in response to previously received join requests received from such other nodes) and would configure itself to forward to router R 1 , via an outbound interface to router R 1  via LAN  108 , any multicast traffic for the group received from source  102 . R 4  likewise would arrange (if necessary) to receive multicast traffic for the group from source  102 , and would configure itself to forward such traffic to router R 2  via LAN  108 . 
     In the above example, if source  102  were to begin sending multicast traffic associated with the group identified in the above-described join messages from routers R 1  and R 2 , both router R 3  and router R 4  would forward the multicast traffic onto LAN  108 . Router R 3  would receive via LAN  108  the multicast traffic as forwarded onto LAN  108  by router R 4  and router R 4  likewise would receive via LAN  108  the multicast traffic as forwarded onto LAN  108  by router R 3 . As noted above, under the PIM-SM protocol, each of routers R 3  and R 4  typically would be configured to detect such duplicative forwarding of multicast traffic by determining that multicast traffic is being received by the router on an interface that is an outbound interface for that router with respect to a group with which the multicast traffic is associated, i.e., the router is itself configured to forward the very same multicast traffic via the interface on which it received the traffic. However, as noted above, typically the forwarding plane components (e.g., input/output modules and/or switching elements) are not configured and/or optimized to make such evaluations. Instead, typically at least a portion (e.g., a rate or otherwise limited sample) of received multicast traffic is sent to the control plane to determine whether it constitutes multicast traffic received on an outbound interface. This approach consumes control plane resources, which typically are not equipped to process high volumes of data traffic, and tolerates (even requires) duplicative forwarding of multicast traffic during the detection and assert election periods. 
       FIG. 2  is a flow chart illustrating an embodiment of a typical prior art process for routing received multicast traffic to a control plane and/or module. In some typical prior art approaches, the process of  FIG. 2  would be implemented on a PIM-SM router, such as router R 3  and/or router R 4  of  FIG. 1 . In the example shown, LAN interfaces are monitored ( 202 ). If a multicast packet is received on the upstream (RPF) interface, then such a packet is forwarded to all downstream interfaces. Otherwise ( 204 ), the packet is forwarded to a control processor and/or module ( 206 ). The control processor determines assert election (see  FIG. 3  and accompanying text below). Even after the assert election, the monitoring continues and packets continue to be forwarded to the control processor ( 202 ) as long as the multicast stream is active ( 208 ). In some approaches,  206  includes additional logic, such as rate limiting, to limit the volume of traffic sent to the control plane for evaluation. 
       FIG. 3  is a flow chart illustrating an embodiment of a typical prior art process for determining whether multicast traffic has been received on an outbound interface. In some typical prior art approaches, the process of  FIG. 3  would be implemented on a control processor or module. A multicast packet is received from the forwarding plane ( 302 ). It is determined whether the packet was received on an interface that is for the receiving router an outbound interface for a multicast group with which the packet is associated ( 304 ). If so, an assert election is initiated ( 306 ). Otherwise, the process of  FIG. 3  ends. 
     The details of a PIM-SM assert election are set forth in the PIM-SM protocol specification and are beyond the scope of this disclosure. 
     Initiating an assert election other than based on receipt of multicast traffic on an interface that is for the receiving router an outbound interface with respect to a multicast group with which the traffic is associated is disclosed. 
       FIG. 4  is a flow chart illustrating an embodiment of a process for triggering a PIM-SM or similar assert election. In some embodiments, the process of  FIG. 4  is implemented on a PIM-SM router, such as router R 3  and/or router R 4  of  FIG. 1 . If a PIM-SM or other “join” message directed to a peer router is received ( 402 ), it is determined whether the join message relates to a multicast group (or set of groups, source, etc.) with respect to which the router on which the process of  FIG. 4  is being executed received and processed a prior “join” message directed to it ( 404 ). If the router that observed the join message to a peer has not previously received and processed a join message for the same group, such that if the router had received multicast traffic on an outbound interface for the group an assert election would be triggered under the PIM-SM protocol, the router ignores the join message ( 406 ) and monitoring for join messages to peers continues until done ( 410 ). If the router has received and processed a join message for the same group, as determined for example by checking a multicast routing table or other data store for entries relating to the group, an assert election is initiated ( 408 ), after which monitoring for join messages to peers continues until done ( 410 ). 
     In the approach illustrated by  FIG. 4  and disclosed herein, an assert election is triggered and likely would be resolved prior to any multicast traffic being sent, thereby avoiding or at least minimizing duplicative forwarding of multicast traffic. In addition, PIM-SM routers would not be required to be configured to forward data traffic to the control plane, and the control plane would not be burdened with processing data traffic to detect receipt of multicast traffic on an outbound interface. Note that in the prior art approach even once an assert election has been resolved the router that is not elected, and indeed other PIM-SM routers on the LAN that were never part of the election, would continue to receive and be required to forward to and process at the control plane multicast traffic associated with the group. Using the approach described herein, data traffic would not be required to be forwarded to or processed by the control plane, and duplicative forwarding of multicast traffic, and concomitant congestion of the LAN, are avoided. 
       FIG. 5  is a flow chart illustrating an embodiment of a process for processing received multicast packets.  FIG. 5  reflect the processing that occurs in the forwarding plane in some embodiments in which the process of  FIG. 4  is used to avoid duplicative forwarding of multicast packets. When a multicast packet is received ( 502 ), it is determined whether the packet was received on an RPF interface ( 504 ). If so, the packet is forwarded to all downstream interfaces ( 506 ); if not, the packet is dropped ( 508 ). 
     In PIM-SM, multicast traffic can be forwarded due to received PIM join messages or due to received IGMP report messages. PIM join messages can be of the following types: Join(S,G), Join(*,G) and Join(*,*,RP). IGMP reports can be of the following types: (S,G) or (*,G). Join(S,G) implies that the router wishes to receive traffic forwarded by source S to group G. Join(*,G) implies that the router wishes to receive traffic forwarded by any source to group G. Join(*,*,RP) implies that the router wishes to receive all traffic forwarded by the rendezvous point RP. 
     Different downstream routers could be sending any of the different PIM join messages or IGMP report messages that can result in duplicate traffic to be forwarded for the same flow. The solution presented here can be applied to any of these combinations of joins and report messages to trigger assert election. 
     The approaches disclosed herein are described in detail in connection with the PIM-SM protocol, but they apply as well to other protocols that depend on the detection of duplicative forwarding of multicast traffic to trigger an “assert” or equivalent election. 
     Although the foregoing embodiments have been described in some detail for purposes of clarity of understanding, the invention is not limited to the details provided. There are many alternative ways of implementing the invention. The disclosed embodiments are illustrative and not restrictive.