Bypassing topological restrictions with tunnels

Not Applicable

Not Applicable

The present invention is related to communications in a computer network, and particularly to bypassing topological restrictions such as multicast group domains by employing tunnels.

Multicast protocols such as Distance Vector Multicast Routing Protocol (“DVMRP”), Multicast Open Shortest Path First (“MOSPF”), Core Based Trees (“CBT”), and Protocol Independent Multicast (“PIM”) that are employed to manage multicast communications among members of a multicast group are known. However, known multicast protocols can consume large amounts of network resources. DVMRP operates by flooding data which consumes network bandwidth. MOSPF requires routers to store records for all of the multicast groups that a device might possibly join. The number of records that must be stored becomes excessive in the case of devices that are connected with an extensive network such as the Internet. CBT and PIM employ a tree which consists of paths between member devices and a core device. The routers that reside along each path are required to maintain records that describe the path. Hence, the number of records that must be maintained is excessive along paths that employ a large number of routers.

Two types of multicast distribution trees are known. In unidirectional trees, which are illustrated in Prior Art FIG. 1, all links in the tree carry all data in only one direction. Therefore, in a unidirectional shared tree a member M other than the core C unicasts a packet to the Core C and then the packet is distributed along the tree. In contrast, in a bidirectional tree, as illustrated in Prior Art FIG. 2, any member M on the tree can inject the packet into the tree by transmitting on all of its ports that are associated with the tree, and any device on the tree that receives the packet on any of its ports that are associated with the tree forwards the packet onto all of its ports that are associated with the tree (except the port on which the packet was received).

It is known to limit the amount of resources that a multicast group consumes by imposing bounds on the group. For example, it is known to prevent the multicast group from extending beyond a predetermined “domain.” Resources are conserved because only the routers that reside within the domain are required to maintain information about the group. Further, data is not flooded outside of the domain so that the multicast address of the domain can also be used by other, non-overlapping bounded domains. For example, if the domain boundaries were the countries Sweden and Denmark, there could be a multicast group with address A in Sweden and another multicast group with address A in Denmark. However, one problem associated with a bounded multicast group is that nodes outside the domain cannot join the multicast group. It would therefore be desirable to be able to bypass topological restrictions such as multicast group domains.

In accordance with the present invention, data units are tunneled to avoid topological or domain restrictions between a first network device and a second network device. In the case of a bounded multicast group, a remote network device that resides outside of the domain of the multicast group obtains access to the multicast group via a proxy device that resides within the domain. The proxy device functions as a member of the multicast group on behalf of the remote network device. Data units transmitted from the remote network device to the proxy device are tunneled to the multicast group via the proxy device. Data units transmitted from the multicast group to the proxy device are tunneled to the remote network device via the proxy device.

Use of the tunnel to obtain remote access to a multicast group advantageously permits remote access without compromising the efficiency provided by the bounded domain. Router devices that reside along the tunnel between the proxy and the remote device are not required to maintain state information. Further, single data units can be tunneled to a designated remote router device and then multicast to a group of remote network devices.

Tunnels can also be employed to facilitate communication in multicast groups in which some routers do not support bidirectional trees. Multicast groups can be represented with a tree structure that is stored in routers that reside in communication paths that are employed by members of the multicast group. A single, bidirectional tree requires less memory to store than a plurality of unidirectional trees. However, some network devices do not support establishment of bidirectional trees. Tunnels are employed to bypass the network devices that do not support bidirectional trees. For example, a bidirectional tunnel can be established from a first device that supports bidirectional trees, through a device that does not support bidirectional trees, to a second device that supports bidirectional trees to bypass the device that does not support bidirectional trees.

The foregoing features of this invention, as well as the invention itself, may be more fully understood from the following Detailed Description of the Invention, and Drawing, of which:

FIG. 1 is a block diagram that illustrates unidirectional trees employed in a manner that is known in the art;

FIG. 2 is a block diagram that illustrates bidirectional trees employed in a manner that is known in the art;

FIG. 3 is a block diagram of a portion of a computer network that illustrates a remote network device that is affiliated with a bounded multicast group in a manner that is consistent with the present invention;

FIG. 4 is a block diagram of a portion of a computer network that illustrates a remote network device that is affiliated with a bounded multicast group via a remote router device in a manner that is consistent with the present invention;

FIG. 5 is a block diagram of a portion of a computer network that illustrates a group of two remote network devices that are affiliated with a bounded multicast group via a remote router device in a manner that is consistent with the present invention;

FIG. 6 is a block diagram of a portion of a multicast group that illustrates use of tunnels in a manner that is consistent with the present invention;

FIG. 7 illustrates operation of the multicast group of FIG. 6 when additional member devices are added; and

FIG. 8 is a block diagram of a portion of a multicast group that illustrates formation of new multicast group in a remote domain.

Referring to FIG. 3, an illustrative multicast group includes a plurality of member devices 12 and a core device 14 , each of which resides within a predetermined domain 10 . Intermediate network devices such as routers may reside in the paths between a core device 14 and the member devices 12 . To transmit to the members of the multicast group, an individual member transmits a multicast data unit on all of its ports which are associated with a multicast tree. In the case of a bidirectional tree, each device that receives the multicast data unit transmits the multicast data unit on all of its ports which are associated with the multicast tree, except the port on which the data unit was received. In the case of a unidirectional tree where the member that initiates the data unit is not the core, the member unicasts the data unit to the core, which then multicasts the data unit to the group.

The multicast group is typically bounded by the associated domain 10 . The intermediate network devices that reside along the paths between the core device 14 and ones of the members 12 of the multicast group maintain state information that facilitates delivery of the copies of the multicast data unit. The collection of paths between the core device and the intermediate network devices forms a “tree,” and the intermediate network devices maintain multicast address information that describes the topology of the tree to facilitate locating the members of the multicast group. The amount of resources that the multicast group consumes with requirements such as the maintenance of state information is limited by imposing bounds on the group. In particular, the tree is not permitted to extend beyond the domain 10 .

A remote network device 16 that resides outside of the domain 10 can obtain access to the multicast group via a proxy device that resides within the domain 10 . In the illustrated example, the core device 14 serves as the proxy device. The proxy device 14 functions as a member of the multicast group on behalf of the remote network device 16 . Data units transmitted from the remote network device 16 to the proxy device 14 are forwarded to the members of the multicast group via the proxy device. Data units transmitted from the members of the multicast group to the proxy device are forwarded to the remote network device via the proxy device. In the case of Core Based Trees (“CBT”) and Protocol Independent Multicast (“PIM”) multicast protocols, the logical choice for the proxy device is the core device, although other member devices could be employed. Further, the proxy device could be a nonmember device that becomes a member of the multicast group when prompted by the remote device 16 .

Data units that are transmitted along a path 18 between the remote network device 16 and the proxy device are tunneled along at least a portion of the path 18 . In particular, a tunnel 20 is established at least through the boundary defined by the domain 10 . Each multicast data unit that is transmitted from a member of the multicast group includes a header and an information field. The header includes a multicast address that is employed to direct the data unit toward members of the group. The proxy device prepares the multicast data unit for unicast transmission to the remote device 16 by adding information such as the destination address of the remote device to the header. The added information may be included in an “envelope” that is appended to the data unit. The envelope is removed following transmission through the tunnel 20 .

Data units that are transmitted from the remote device 16 to the multicast group are also tunneled along at least a portion of the path 18 . In particular, the data units are transmitted via tunnel 20 . The header portion of a data unit that is unicast from the remote device 16 to the proxy device specifies the destination address of the proxy device in an envelope. The proxy device prepares the unicast data unit for multicast transmission to the members of the multicast group by removing the envelope. The proxy device then multicasts the data unit toward the members of the group.

A join request data unit may be employed by the remote device 16 to initiate access to the multicast group. In particular, the remote device transmits the join request data unit to the core device 14 . The address of the remote device is provided to the core device to facilitate establishment of communication. If the remote device 16 is affiliated with a remote domain, the address or name of the remote domain name may also be provided to the core device 14 .

Referring to FIG. 4, a remote router device 22 may be employed to facilitate access to the multicast group. The remote router device 22 is affiliated with a remote domain 24 in which the remote device 16 resides. The remote router device 22 functions as a gateway for devices within the domain 24 by managing traffic with proxy device 14 . In particular, the remote router 22 reroutes data units that are received from the remote device 16 to the proxy device 14 , and reroutes data units that are received from the proxy device 14 to the remote device 22 . The data units are tunneled through at least a portion of the path between the remote router 22 and the proxy device 14 .

As illustrated in FIG. 5, multiple pathways between the remote domain 24 and the multicast group can be consolidated via the remote device 22 . In particular, when a second remote device 28 attempts to join the multicast group via a separate pathway 30 , transmissions between the second remote device 28 and the proxy 14 are consolidated into the path 18 between the remote device 22 and the proxy 14 . Remote devices may be required to indicate membership in a domain when requesting membership in the multicast group via the proxy to facilitate consolidation. The proxy device can then search for a remote member device that resides in the same domain as the requesting device and, if multiple remote devices reside in the same domain, inform the remote devices to consolidate. Alternatively, if the proxy device is employing multiple tunnels to the same remote domain, the proxy device can request that the remote devices that reside in that remote domain form a remote multicast group. A single remote device in the remote multicast group can be designated to connect the two multicast groups through a single tunnel.

It should be noted that a device other than the remote network device may send the join request data unit to the proxy device in order to establish the tunnel. An intermediate device such as the remote router 22 could be employed to determine when and how to obtain remote access to the multicast group. Further, multiple tunnels may be employed in the path between the proxy device and the remote device.

Referring to FIG. 6, tunnels can also be employed to provide an improved multicast tree structure by bypassing devices that do not support bidirectional trees. The multicast tree structure requires considerably less memory to store when a single, bidirectional tree is employed rather than a plurality of unidirectional trees. Tunnels are employed to bypass network devices such as routers that do not support bidirectional trees. In the illustrated example, data units are transmitted in a bidirectional pathway 32 established between member device M 1 and router R 1 , and in a bidirectional pathway 34 established between router R 1 and router R 2 . Data units are also transmitted in a bidirectional tunnel 36 that is established between router R 2 and a core device C. The bidirectional tunnel 36 bypasses non-bidirectional router R 3 .

FIG. 7 illustrates multicast communication in the network portion of FIG. 6 when a member device M 2 is coupled to router R 2 , a member device M 3 is coupled to router R 3 , and a member device M 4 is coupled to router R 4 in the multicast group. Member device M 2 is coupled to router R 2 via a path 38 . Member device M 3 is coupled to router R 3 via a path 40 and to core C via tunnel 48 because router R 3 does not support bidirectional paths. Member device M 4 is coupled to router R 4 via a path 46 .

When member device M 1 transmits a data unit to the other members of the multicast group, one copy of the data unit is provided to member device M 2 via paths 32 , 34 and 38 . Another copy of the data unit is provided to the core C via path 32 , path 34 , and tunnel 36 . From the core, the data unit is provided to member device M 3 via paths 42 , 44 and 40 , and to member device M 4 via path 42 and path 46 .

When member device M 2 transmits a data unit to the other members of the multicast group, one copy of the data unit is provided to member device M 1 via paths 38 , 34 and 32 . Another copy of the data unit is provided to the core C via path 38 and tunnel 36 . From the core, the data unit is provided to member device M 3 via paths 42 , 44 and 40 , and to member device M 4 via path 42 and path 46 .

When member device M 3 transmits a data unit to the other members of the multicast group, the data unit is tunneled to the core C via tunnel 48 . From the core, the data unit is provided to member device M 3 via path 42 , path 44 and path 40 , to member device M 2 via tunnel 36 and path 38 , and to member deice M 1 via tunnel 36 and paths 34 and 32 .

When member device M 4 transmits a data unit to the other members of the multicast group, a copy of the data unit is provided to member device M 3 via paths 46 , 44 and 40 . Another copy of the data unit is provided to the core C via paths 46 and 42 . From the core, the data unit is provided to member device M 2 via tunnel 36 and path 38 , and to member deice M 1 via tunnel 36 and paths 34 and 32 .

Referring to FIG. 8, a selected device such as router R 11 in a remote domain 50 serves as a gateway to other devices and domains. In particular, each device within the bounds of remote domain 50 employs device R 11 to obtain access to devices that are outside of remote domain 50 when such access is desired. In the illustrated example, a tunnel 52 is established between device R 11 and member device M 10 . A plurality of tunnels 51 , 53 , 55 may be established between device R 11 and devices outside of the remote domain 50 .

To facilitate operation when a plurality of devices within remote domain 50 are employing one of the interfacing tunnels, such as tunnel 51 , a new multicast group is formed within the remote domain. In the illustrated example, formation of the new multicast group is initiated by device R 11 . Tunnels augment performance of the new multicast group. For example, when member device M 13 and member device M 12 both become members of the group that is affiliated with tunnel 51 , a tunnel 56 is established between device R 11 and device R 12 and a second tunnel 58 is established between device R 12 and device R 13 to carry the data units. Device R 13 multicasts the data units from tunnel 58 to member devices M 12 and M 13 , and transmits data units from member devices M 12 and M 13 via the tunnel 58 . The tunnels augment performance by obviating the need for separate tunnels between each member device and device R 11 .

Having described the embodiments consistent with the present invention, other embodiments and variations consistent with the present invention will be apparent to those skilled in the art. Therefore, the invention should not be viewed as limited to the disclosed embodiments but rather should be viewed as limited only by the spirit and scope of the appended claims.