Abstract:
The invention provides a method and system for multicast group routing using unidirectional links. A set of uplink routers and a set of downlink routers provide a primary unidirectional distribution path from a set of sources to a set of destinations. A relatively smaller reverse communication channel is provided between the destinations and the sources. When a destination desires to add itself to, or take itself off, a multicast distribution group, one of the downlink routers acts as a proxy for that destination and so informs the relevant source. The selection of the proxy reporter for downlink routers or the querier for uplink routers does not require bi-directional communication between either of them, respectively.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates to multicast packet routing. 
     2. Related Art 
     In a computer network, it is often desirable to transmit messages from a single source to a selected plurality of destinations. This activity is often referred to as “multicast routing.” It is further desirable for the plurality of destinations to be capable of self-selection, so as to add themselves to, or to take themselves off, multicast distribution groups. 
     One method in the known art is the IGMP (Internet Group Management Protocol), in which messages are transmitted from a single source to a plurality of destinations, and in which destination devices can add themselves to, or take themselves off, multicast distribution groups. One problem with IGMP is that it uses bi-directional communication between routing devices (that receive messages from the source device) and the destination devices, so that routing devices intermediate between the source and destinations can determine how to route multicast messages. IGMP is not well suited when a primary communication path between the source and the destinations is unidirectional, such as in distribution systems using satellite communication. 
     Accordingly, it would be desirable to provide a method and system for multicast group routing using unidirectional links. This advantage is achieved in an embodiment of the invention in which a set of uplink routers and a set of downlink routers provide a unidirectional distribution path from a set of sources to a set of destinations, and in which some (but not all) downlink routers act as proxies for others to inform uplink routers whether distribution should occur over that unidirectional distribution path. 
     SUMMARY OF THE INVENTION 
     The invention provides a method and system for multicast group routing using unidirectional links. A set of uplink routers and a set of downlink routers provide a primary unidirectional distribution path from a set of sources to a set of destinations. A relatively smaller reverse communication channel is provided between the destinations and the sources. When a destination desires to add itself to, or take itself off, a multicast distribution group, one of the downlink routers acts as a proxy for that destination and so informs the relevant source. The selection of the proxy does not require bi-directional communication between either uplink routers or downlink routers. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows a block diagram of a system for multicast group routing using unidirectional links. 
     FIG. 2 shows a process flow diagram for a method of operating a system for multicast group routing using unidirectional links. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     In the following description, a preferred embodiment of the invention is described with regard to preferred process steps and data structures. Those skilled in the art would recognize after perusal of this application that embodiments of the invention can be implemented using circuits adapted to particular process steps and data structures described herein, and that implementation of the process steps and data structures described herein would not require undue experimentation or further invention. 
     System Elements 
     FIG. 1 shows a block diagram of a system for multicast group routing using unidirectional links. 
     A system  100  includes a set of source devices  110 , a set of uplink routers  120 , a unidirectional communication pathway  130 , a set of downlink routers  140 , a set of destination devices  150 , and a reverse communication channel  160 . 
     As used herein, a “source device” includes any device taking on the role of a source in a multicast environment. There is no particular requirement that the source devices  110  must be individual devices; they can each be a single device, a set of cooperating devices, a portion of a device, or some combination thereof. 
     Similarly, as used herein, a “destination device” includes any device taking on the role of a destination in a multicast environment, such as using IGMP or a similar protocol. There is no particular requirement that the destination devices  150  must be individual devices; they can each be a single device, a set of cooperating devices, a portion of a device, or some combination thereof. 
     Each source device  110  is coupled to an uplink router  120  using a communication pathway  111 , such as a direct communication link, a LAN (local area network), a WAN (wide area network), a network using IP (such as the internet), or some combination thereof. Each source device  110  is associated with an uplink router  120 , and is disposed for bi-directional communication with its associated uplink router  120 . 
     Each uplink router  120  is coupled to the unidirectional communication pathway  130  and is disposed for transmitting messages using the unidirectional communication pathway  130 . Each uplink router  120  is also disposed for receiving messages using the reverse communication channel  160  or using a (relatively limited) reverse communication capability of the unidirectional communication pathway  130 . 
     An uplink router  120  can be coupled to more than one unidirectional communication pathway  130  if the system  100  includes more than one unidirectional communication pathway  130 . In this case, the uplink router  120  identifies multicast messages sent using one of the unidirectional communication pathways  130  to indicate which uplink router  120  and which unidirectional communication pathway  130  is being used. 
     An uplink router  120  can also perform a unicast communication protocol that doe s not require bi-directional communication, using the unidirectional communication pathway  130 . 
     The unidirectional communication pathway  130  is disposed for communicating messages from uplink routers  120  to downlink routers  140 . 
     In a preferred embodiment, the unidirectional communication pathway  130  comprises a satellite communication system, the uplink routers  120  comprise uplink transmitters in the satellite communication system, and the downlink routers  140  comprise downlink transmitters in the satellite communication system. Thus, each uplink transmitter is disposed for transmitting, but not necessarily for receiving; similarly, each downlink transmitter is disposed for receiving, but not necessarily for transmitting. 
     Each downlink router  140  is coupled to the unidirectional communication pathway  130  and is disposed for receiving messages using the unidirectional communication pathway  130 . 
     The unidirectional communication pathway  130  is described herein as being disposed for communicating messages from uplink routers  120  to downlink routers  140 , and the invention does not rely on any other capability of the unidirectional communication pathway  130 . However, there is no particular requirement that the unidirectional communication pathway  130  is limited to that capability. For example, the unidirectional communication pathway  130  can have a relatively limited capability for communication in a reverse direction, and thus serve as part of or in cooperation with the reverse communication channel  160 . 
     For example, in an embodiment where the unidirectional communication pathway  130  comprises a satellite communication system, it is possible for uplink routers  120  and downlink routers  140  to be co-located or logically coupled, so that a single device can have both capabilities and possibly perform both functions. Similarly, it is possible for some of the source devices  110  and some of the destination devices  150  to be co-located or logically coupled, so that  3  single device can have both capabilities and possibly perform both functions. 
     Each destination device  150  is coupled to a downlink router  140  using a communication pathway  151  similar to the communication pathway  111 . Each destination device  150  is similarly associated with a downlink router  140 , and is disposed for bi-directional communication with its associated downlink router  140 . 
     A reverse communication channel  160  couples each downlink router  140  to each uplink router  120 , so that the downlink routers  140  can send messages to the uplink routers  120 . In a preferred embodiment, the reverse communication channel  160  is similar to the communication pathway  111 . 
     The reverse communication channel  160  can also be unidirectional (in the reverse of the unidirectional communication pathway  130 ), but there is no particular requirement that the reverse communication channel  160  be either bi-directional or unidirectional. 
     The reverse communication channel  160  need not have a particularly wide bandwidth, as the number, frequency, and size of messages to be transmitted using the reverse communication channel  160  is expected to be relatively minor. However, there is no particular requirement that the reverse communication channel  160  be either fast or slow, or wide bandwidth or narrow bandwidth. 
     Method of Operation 
     FIG. 2 shows a process flow diagram for a method of operating a system for multicast group routing using unidirectional links. 
     A method  200  is performed by the system  100 , including the source devices  110 , the uplink routers  120 , the unidirectional communication pathway  130 , the downlink routers  140 , the destination devices  150 , and the reverse communication channel  160 . 
     Transmitting Multicast Messages 
     At a flow point  210 , one of the source devices  110  is ready to send multicast messages to selected destination devices  150 . 
     At a step  211 , one of the source devices  110  sends a message to its associated uplink router  120  for multicast distribution. 
     At a step  212 , the associated uplink router  120  determines if there are any destination devices  150  that are group members associated with the group that is the target for the message and coupled to associated downlink routers  140 . If so, the associated uplink router  120  transmits the message using the unidirectional communication pathway  130 . 
     At a step  213 , the downlink routers  140  receive the multicast message using the unidirectional communication pathway  130 . Each particular downlink router  140  determines if there are any destination devices  150  that are group members associated with the group that is the target for the message, and associated with that particular downlink router  140 . Each particular downlink router  140  discards the message if it does not have any such associated destination devices  150 . 
     At a step  214 , each downlink router  140  determines if it has one or more associated destination devices  150  that are selected for receipt of the multicast message. 
     At a step  215 , each downlink router  140 , forwards the multicast message to those associated destination devices  150  selected for receipt, if any. 
     At a flow point  220 , the multicast messages have been delivered to selected destination devices  150 . 
     Adding Destinations to Multicast Groups 
     At a flow point  230 , one particular destination device  150  is ready to add itself to a multicast group. 
     At a step  231 , the destination device  150  sends an IGMP Report message (that is, a request to be added to a multicast group), to its associated downlink router  140 . 
     At a step  232 , the associated downlink router  140  adds the particular destination device  150  to its distribution list for that group. 
     At a step  233 , the associated downlink router  140  determines if there is any reason for it to report the addition to the multicast group. There is no reason for the associated downlink router  140  to make any report for either of the following conditions: 
     The uplink router  120  is already transmitting multicast message for the indicated group. or 
     The downlink router  140  is already receiving and distributing multicast messages for the indicated group. 
     These two conditions are functionally the same. There is also no reason for the associated downlink router  140  to report the addition if another downlink router  140  is already a proxy reporter for the indicated multicast group. 
     In any of these cases where no action is required, the associated downlink router  140  takes no further action, and the method  200  proceeds with the flow point  240 . If not, the method  200  proceeds with the next step. 
     At a step  234 , the associated downlink router  140  sends an IGMP Report message to the uplink router  120  associated with that multicast group, using the reverse communication channel  160 . 
     In a preferred embodiment, the downlink router  140  sending the IGMP Report message uses an IP address for the uplink router  120  as the destination IP address for the uplink router  120 . The destination IP address is not equal to the IP address for the interface the uplink router  120  has to the unidirectional communication pathway  130 . Thus, the IGMP Report message is transmitted using the reverse communication channel  160 . In the IGMP Report message, the downlink router  140  includes its own IP address for the unidirectional communication pathway  130  as the source IP address for the IGMP Report message. 
     In a preferred embodiment, the uplink router  120  should be configured so that all downlink routers  140  coupled thereto using the unidirectional communication pathway  130  are on the same subnet. 
     At a step  235 , the associated uplink router  120  receives the IGMP Report message and adds the interface the uplink router  120  has to the unidirectional communication pathway  130  to its distribution list for the multicast group. The uplink router  120  can determine which such interface to a unidirectional communication pathway  130  to use in response to the source IP address in the IGMP Report message. Thereafter, the uplink router  120  receives and distributes messages for that multicast group using the unidirectional communication pathway  130 . 
     At a step  236 , the associated uplink router  120  transmits the IGMP Report message using the unidirectional communication pathway  130 . All downlink routers  140  thus receive a copy of the IGMP Report message. 
     At a step  237 , each downlink router  140  note that the downlink router  140  that initiated the IGMP Report message is the proxy reporter for all IGMP Report messages for that multicast group. 
     At a flow point  240 , the particular destination device  150  has been added to the multicast group. 
     Removing Destinations from Multicast Groups 
     At a flow point  250 , one particular destination device  150  is ready to leave a multicast group. 
     At a step  251 , the destination device  150  sends an IGMP Leave message (that is, a request to leave a multicast group), to its associated downlink router  140 . 
     At a step  252 , the associated downlink router  140  removes the output interface associated with the particular destination device  150  from its distribution list for that group if there are no more group members associated with that output interface. If not, the associated downlink router  140  takes no further action, and the method  200  proceeds with the flow point  260 . If so, the method  200  proceeds with the next step. 
     At a step  253 , the associated downlink router  140  determines if another downlink router  140  is already a proxy reporter for the indicated multicast group. If so, the downlink router  140  takes no further action, and the method  200  proceeds with the flow point  260 . If not, the method  200  proceeds with the next step. 
     At a step  254 , the associated downlink router  140  sends an IGMP Leave message to the uplink router  120  associated with that multicast group, using the reverse communication channel  160 . 
     At a step  255 , the uplink router  120  associated with that multicast group, after a (relatively small) period of time, removes the unidirectional interface if no other downlink router  140  sends an IGMP Report message (thus becoming a new proxy reporter). 
     At a step  256 , the uplink router  120  transmits the IGMP Leave message using the unidirectional communication pathway  130 . All downlink routers  140  thus receive a copy of the IGMP Leave message. 
     At a step  257 , each downlink router  140  determines that the proxy reporter for that multicast group is no longer performing that function. As a consequence, another one of the downlink routers  140  is selected as a proxy reporter. This occurs when the next downlink router  140  sends an IGMP Report message. It is expected that the next downlink router  140  to be selected as the proxy reporter will be randomly distributed among the downlink routers  140 . 
     At a flow point  260 , the particular destination device  150  has left the indicated multicast group. 
     IGMP Query Messages 
     At a flow point  270 , the uplink routers  120  are ready to send IGMP Query messages. 
     At a step  271 , each uplink router  120  sends an IGMP Query message, using the unidirectional communication pathway  130 . Each uplink router  120  does not receive the IGMP Query messages sent by each other uplink router  120 . 
     At a step  272 , each downlink router  140  receives the IGMP Query message, and notes the status of a single elected uplink querier. 
     At a step  273 , each downlink router  140  sets its RPF interface, for all sources, in response to the IGMP Query message sent by the elected uplink querier. However, the unicast interface is not Necessarily the same interface as the multicast interface between each particular downlink router  140  and each particular uplink router  120 . 
     At a step  274 , each downlink router  140  selects one of the uplink routers  120  as the destination for IGMP helpered reports. 
     In a preferred embodiment, each downlink router  140  selects the uplink routers  120  with the lowest IP address as the elected uplink querier. However, in alternative embodiments, other techniques could be used that each downlink router  140  can determine individually and that result in consensus among the downlink routers  140  as to which uplink router  120  should be the elected uplink querier. 
     At a step  275 , when the downlink routers  140  each determine that any uplink router  120  is no longer sending IGMP Query messages (such as due to a service interruption or configuration charge), each such downlink router  140  selects a new elected uplink querier for each multicast group. 
     At a flow point  280 , the IGMP Query messages have been processed. 
     Alternative Embodiments 
     Although preferred embodiments are disclosed herein, many variations are possible which remain within the concept, scope, and spirit of the invention, and these variations would become clear to those skilled in the art after perusal of this application.