Extending router functionality to report static group membership

BACKGROUND

This invention relates to multicast routing.

Multicast routing enables a host to transmit a stream of data packets to a group of hosts on a wide area network (WAN). Each multicast data packet has a multicast group address, which functions like a radio channel. Hosts tune into the multicast packet by joining the associated multicast group address. While a host belongs to the multicast group, the host receives each data packet transmitted to the multicast group address.

A multicast router records memberships to multicast group addresses by hosts of the local area network (LAN's) to which the multicast router connects. From these memberships, a multicast router determines whether to transmit received multicast packets to LAN's to which the router connects.

A multicast router may dynamically update memberships so that hosts can join and quit multicast group addresses. Dynamically updating enables hosts to tune in and out of multicast data traffic.

The Internet Group Management Protocol (IGMP) provides one process for dynamically updating memberships to multicast group addresses. The IGMP process entails making regular queries to LAN hosts supporting the IGMP protocol. An IGMP querying router queries a LAN to which it connects at regular intervals, e.g., once a minute. In response to a query, an IGMP host transmits one or more messages reporting its memberships to multicast group addresses.

The routing algorithm determines the detailed routing of multicast data packets. One routing algorithm uses the link state routing protocol. To perform the link state routing protocol, routers regularly collect delay or cost data for sending packets to adjacent routers. From the collected data, the routers construct packets with local routing data. The local routing data includes memberships to multicast group addresses. The routers flood the packet with the local routing data to other routers of the network. To implement flooding, each router transmits an incoming packet to every outgoing line of the router except the line on which the packet arrived. The routers receive similar packets from the other routers and use the received packets to calculate future routings for data packets, e.g., multicast data packets.

Routing protocols use hierarchical organization to improve performance of the link state routing algorithm on large networks. One such routing protocol is the open shortest path first (OSPF) protocol. In the OSPF protocol, a special set of routers, i.e., designated routers (DR), collect and disseminate the local routing data to the OSPF routers. Limiting these activities to DR routers reduces network traffic and calculations for determining future routings.

SUMMARY

In a first aspect, the invention provides an apparatus. The apparatus includes a router configured with a static membership to a multicast group address. The router is capable of transmitting a message reporting the static membership to another router.

In a second aspect, the invention provides a method of propagating memberships to multicast group addresses. The method includes transmitting a message reporting one or more static memberships to multicast group addresses. The message is transmitted from a first multicast router configured with the one or more static memberships to a second multicast router.

Various embodiments propagate memberships to multicast group addresses of statically configured routers. Corresponding multicast data packet traffic is received by local area networks connected to such routers.

BRIEF DESCRIPTION OF THE DRAWINGS

Other objects, features, and advantages of the invention will be apparent from the following description, taken together with the drawings in which:

FIG. 1 shows an IGMP router configured with a static membership to one or more multicast group addresses;

FIGS. 2A-2C show processes for determining and propagating multicast memberships of a LAN;

FIG. 3 shows a IGMP querying router configured with one or more static memberships to multicast group addresses;

FIG. 4 shows a process for querying multicast memberships of a LAN shown in FIG. 3;

FIG. 5 shows a process for propagating multicast memberships of the LAN of FIG. 3; and

FIG. 6 shows a router which is both an IGMP querying router and a MOSPF DR router.

DESCRIPTION

Referring to FIG. 1, a multicast OSPF (MOSPF) router <b>10</b> configured with one or more static memberships to multicast group addresses is shown. The static memberships are entries of a table <b>11</b> stored in a memory storage device <b>12</b>. The memory storage device <b>12</b> also stores an executable process <b>12</b><i>a </i>for responding to IGMP protocol messages. The MOSPF router <b>10</b> responds to IGMP query messages like IGMP hosts <b>13</b>, <b>14</b>.

The MOSPF router <b>10</b> connects to a LAN <b>15</b> that belongs to a wide area network (WAN) <b>16</b>. The WAN <b>16</b> includes an MOSPF designated (DR) router <b>18</b> that is responsible for propagating memberships to multicast group addresses for the LAN <b>15</b> to other MOSPF networks <b>17</b>. The MOSPF DR router <b>18</b> propagates local routing data on the LAN <b>15</b> by regularly flooding routing data to MOSPF routers <b>20</b>, <b>21</b> connected to the other MOSPF networks <b>17</b>. The flooded routing data includes the memberships to multicast group addresses for the LAN <b>15</b> that are known to the MOSPF DR router <b>18</b>.

The LAN <b>15</b> also connects to an IGMP multicast router <b>22</b> that also supports the MOSPF protocol. The IGMP router <b>22</b> performs IGMP querying for memberships to multicast group addresses of the LAN <b>15</b>. The IGMP router <b>22</b> may be the IGMP querier that resulted from an arbitration between routers having IGMP interfaces with the LAN <b>15</b>, e.g., based on Internet Protocol (IP) addresses. Thus, the identity of the IGMP querying router may be unknown before the routers are installed in the WAN <b>16</b>. The IGMP querying router <b>22</b> dynamically determines memberships to multicast group address of the LAN <b>15</b>.

The MOSPF DR router <b>18</b> propagates data on memberships to multicast group addresses, which are known to itself, to the other MOSPF networks <b>17</b>. The data on memberships is propagated to all MOSPF routers <b>20</b>, <b>21</b>. To ensure propagation of the memberships of the LAN <b>15</b>, the MOSPF DR router <b>18</b> is informed of the memberships of both hosts <b>13</b>, <b>14</b> and of the router <b>10</b>. The propagation of data on those memberships ensures that the LAN <b>15</b> will receive the associated streams of multicast data packets through its MOSPF routers <b>10</b>, <b>18</b>, <b>22</b>.

Referring to FIG. 2A, a process <b>30</b> to dynamically propagate memberships to multicast group addresses of the LAN <b>15</b> of FIG. 1 is shown. The IGMP router <b>22</b> transmits <b>32</b> an IGMP query message to the LAN. The query message is a multicast message for either a general query or a specific query of memberships to multicast group addresses, e.g., IP multicast addresses. The hosts <b>13</b>, <b>14</b>, whose processes request membership to the multicast group addresses, transmit <b>34</b> IGMP multicast messages to the LAN. Each IGMP message reports one of the multicast group addresses to which the transmitting host <b>13</b>, <b>14</b> requests membership. Both, the IGMP querying and MOSPF DR routers <b>22</b>, <b>18</b> monitor for the IGMP messages reporting multicast memberships, because both routers <b>18</b>, <b>22</b> are multicast routers connected to the LAN <b>15</b>. The MOSPF DR router <b>18</b> reads <b>36</b> the IGMP messages from the hosts <b>13</b>, <b>14</b> that report memberships to multicast group addresses. The MOSPF DR router <b>18</b> writes <b>38</b> membership data obtained from the IGMP messages reporting memberships to a table <b>24</b> of an internal memory storage device <b>25</b>.

Referring to FIG. 2B, a process <b>40</b> by which the MOSPF router <b>10</b> with a static membership responds to the query message from the IGMP querying router <b>22</b> is shown. Since the MOSPF router <b>10</b> supports the IGMP protocol, the MOSPF router <b>10</b> recognizes <b>42</b> the IGMP query on the LAN <b>15</b>. In response to the query, the MOSPF router <b>10</b> determines <b>44</b> whether there are static memberships to multicast group addresses. Since static memberships are recorded in the table <b>11</b>, determining <b>44</b> can include a lookup in the table <b>11</b>. If no static memberships are found, the MOSPF router <b>10</b> ignores the IGMP query message. If a static membership found, the MOSPF router <b>10</b> starts <b>46</b> a countdown of a random delay time on a software timer <b>19</b> for each static membership. Each random delay time is less than a preselected maximum time. At the expiration of each random time, the router <b>10</b> sends <b>48</b> an IGMP multicast message reporting the associated static membership to the LAN <b>15</b>. By waiting for random number delay times prior to responding, unnecessary IGMP messages reporting memberships to multicast groups, i.e., duplicates, are surpressed. The MOSPF router <b>10</b> monitors for messages from the hosts <b>13</b>, <b>14</b>, which report memberships, and stops a timer and ignores the corresponding static membership in response to observing the same membership in a message from one of the hosts <b>13</b>, <b>14</b>. Since the MOSPF DR router <b>18</b> monitors for multicast messages, the MOSPF DR router <b>18</b> recognizes <b>50</b> the IGMP messages reporting memberships that originate from the MOSPF router <b>10</b>. The MOSPF DR router <b>18</b> writes <b>52</b> memberships reported in the messages to the table <b>24</b> in the memory storage device <b>25</b>. These memberships may include static memberships.

Referring to FIG. 2C, a process <b>54</b> for propagating multicast memberships from the LAN <b>15</b> to the other MOSPF networks <b>17</b> is shown. The MOSPF DR router <b>18</b> monitors <b>56</b> the LAN <b>15</b> to collect multicast membership data and collects cost or delay data for routing messages to adjacent MOSPF routers <b>20</b>, <b>21</b>. At the end of a predetermined interval, the MOSPF DR router <b>18</b> disseminates <b>58</b>, e.g., by flooding, packets with the collected data to the other MOSPF routers <b>20</b>, <b>21</b> of the MOSPF networks <b>17</b>. The adjacent MOSPF routers <b>20</b>, <b>21</b> update <b>60</b> entries for the MOSPF DR router <b>18</b> in their own multicast routing tables using the flooded data.

Referring again to FIG. 1, the MOSPF router <b>10</b> with the static membership to multicast group addresses may send an initial unsolicited IGMP message reporting multicast memberships in response to booting up. Such a message communicates static memberships without the unknown delay associated with waiting for the next IGMP query for messages reporting multicast memberships of the LAN <b>15</b>. These initial messages may be repeated once or twice to reduce the risk that the messages were not received.

Since conventional routers do not respond to IGMP queries, their static memberships to multicast groups are not communicated to MOSPF DR routers connected to the same LAN. Unless a host of the same LAN has a membership to the same multicast group address, other MOSPF routers cannot learn of the static memberships and will not route multicast packet traffic to the multicast routers of a LAN based on such memberships.

Conventional flood and prune routing protocols, such as DVMRP, do not need to propagate memberships to multicast group addresses between routers. Instead, routers running these multicast routing protocols decide whether to prune themselves from received multicast streams of data packet based on their own multicast memberships. With such protocols, multicast data packets would flow into LAN's based on non-propagating static memberships. But, flood and prune protocols have disadvantages not encountered in the MOSPF routing protocol.

Referring to FIG. 3, an IGMP router <b>10</b>′ having a static membership to one or more multicast group addresses is shown. The IGMP router <b>10</b>′ is also the IGMP querying for the LAN <b>15</b>. The querying router of the LAN <b>15</b> is determined by an arbitration based on IP address. The querying router <b>10</b>′ has a higher IP address than the other IGMP routers <b>18</b>, <b>22</b> connected to the LAN <b>15</b>.

The MOSPF DR router <b>18</b> propagates multicast memberships of the LAN <b>15</b> to the other MOSPF routers <b>20</b>, <b>21</b> of a WAN <b>16</b>′. Since the other routers <b>10</b>′, <b>22</b> are not DR routers, these routers <b>10</b>′, <b>22</b> do not propagate such memberships. Thus, propagating the multicast memberships through the MOSPF DR router <b>18</b> enables all the MOSPF routers <b>10</b>′, <b>18</b>, <b>22</b> of the LAN <b>15</b> to receive streams of multicast packets from the other MOSPF networks <b>17</b>.

The router <b>10</b>′ stores executable software <b>12</b><i>b </i>for the IGMP protocol in the memory storage device <b>12</b>. The software <b>12</b><i>b </i>supports an IGMP querying process that announces static memberships to multicast group addresses from the table <b>11</b> known to the MOSPF DR router <b>18</b>.

Referring to FIG. 4 a process <b>70</b> by which the IGMP router <b>10</b>′ queries memberships of the LAN <b>15</b>′ to multicast group addresses is shown. The IGMP querying router <b>10</b>′ transmits <b>72</b> an IGMP query message to the LAN <b>15</b>′. In response to receiving the query message, the hosts <b>13</b>, <b>14</b> transmit IGMP messages to the LAN <b>15</b>′. These IGMP messages report the host memberships to multicast group addresses, e.g., IP multicast addresses.

Lower level protocols ensure that the IGMP querying router <b>10</b>′ does not receive its own query message. Thus, the IGMP querying router <b>10</b>′ automatically communicates its own static multicast memberships in response to transmitting the IGMP query message. The IGMP querying router <b>10</b>′ checks whether the internal table <b>11</b> records <b>74</b> any static memberships to multicast group addresses. For each static membership discovered, the IGMP querying router <b>10</b>′ starts <b>76</b> a separate software timer <b>19</b> to countdown a random delay time. Each delay time is less than a preselected upper bound. To avoid duplicates, the router <b>10</b>′ stops a timer <b>19</b> and ignores the corresponding static membership if the same membership, i.e., the same multicast group address, is identified in an IGMP message received from one of the hosts <b>13</b>, <b>14</b>. At the expiration of each delay time, the IGMP querying router <b>10</b>′ transmits <b>78</b> to the LAN <b>15</b>′ an IGMP message with a membership report in a fashion similar to that of the IGMP hosts <b>13</b>, <b>14</b>. These messages report the corresponding static memberships to multicast group addresses. The random transmission of the messages identifying static memberships reduces the probability that such messages will overload the bandwidth of the LAN <b>15</b>′.

Conventional IGMP querying routers do not communicate internal static memberships to multicast group addresses to other devices connected to the same LAN. Thus, the static memberships of a conventional IGMP querying router would not be known by a MOSPF DR router connected to the same LAN and would not be propagated to other MOSPF networks unless other hosts on the same LAN communicate the same multicast memberships. This lack of communication of static memberships results in conventional IGMP querying routers not receiving multicast traffic addressed to the multicast group addresses of their internal static memberships.

Referring to FIG. 5, a process <b>80</b> by which the MOSPF DR router <b>18</b> propagates the memberships of the LAN <b>15</b>′ to multicast group addresses is shown. Since the MOSPF DR router <b>18</b> recognizes IGMP messages, the MOSPF DR router <b>18</b> reads <b>82</b> the IGMP messages on the LAN <b>15</b>′ that report multicast memberships. The read messages include messages reporting multicast memberships from both hosts <b>13</b>, <b>14</b> and the IGMP querying router <b>10</b>′. The MOSPF DR router <b>18</b> writes <b>84</b> multicast membership data obtained from the message reports in the table <b>24</b> located in the internal memory storage device <b>25</b>. The MOSPF DR router <b>18</b> constructs a data packet having the data on multicast memberships, e.g., the associated IP multicast addresses, from the entries of the table <b>24</b> and disseminates, e.g., by flooding, the data packet to the other MOSPF routers <b>20</b>, <b>21</b>. The data from this data packet updates multicast routing data in the MOSPF routers <b>20</b>, <b>21</b> so that multicast data packets from the MOSPF networks <b>17</b> can flow into the MOSPF routers <b>10</b>′, <b>18</b>, <b>22</b>′ of the LAN <b>15</b>′.

Referring to FIG. 6, a MOSPF router <b>18</b>′, which is both a DR router and the IGMP querying router for the LAN is″, is shown. The selection of the router <b>18</b>′ as the IGMP querying router results from arbitration among routers <b>10</b>′, <b>22</b>′, <b>18</b>′ connected to the LAN <b>15</b>″.

The MOSPF DR router <b>18</b>′ obtains both static memberships of the router <b>10</b>′ and dynamic memberships of the hosts <b>13</b>, <b>14</b> from the IGMP report messages responding to its own IGMP queries. The router <b>18</b>′ both performs the queries for determining multicast memberships, e.g., IP multicast addresses, of the LAN <b>15</b>″ and propagates data on the memberships to the other MOSPF networks <b>17</b> of WAN <b>16</b>″.

In some embodiments, routers have a memory device encoding executable processes to determine whether the routers are querying routers, MOSPF DR router, and/or configured with static multicast memberships. If the process determines that the associated router has a static membership but is not a querying router, the router behaves like the router <b>10</b> of FIG. <b>1</b>. If the process determines that the associated router queries but is not a DR router and does not have static memberships, the router behaves like the router <b>22</b> of FIG. <b>1</b>. If a process determines that the associated router is a querying router with a static membership, the router behaves like the router <b>10</b>′ of FIG. <b>3</b>. If the process determines that the associated router is both a querying and a DR router, the router behaves like the router <b>18</b>′ of FIG. <b>6</b>.

While the invention has been described in conjunction with the detailed description, the foregoing description is intended to illustrate and not to limit the scope of the invention. The scope of the invention is defined by the appended claims. Other aspects, advantages, and modifications are within the scope of the following claims.