Inter-domain multicast routing.

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Industrial application field]

In a computer network, the information distributed using a routing protocol determines how data packets and messages are sent from any point in the network to a destination of interest. Data packets and messages are often sent from a single source or sender to a single receiver. This is generally called unicasting. Today's computer networks have sophisticated routing protocols to support and ensure the secure, fast, and reliable execution of these unicast transmissions. However, if data packets or messages must be sent from a single sender source to a group of multiple receiver stations in the network (commonly referred to as multicasting), relying on traditional unicast routing protocols can be a good idea. It is possible but very inefficient. The present invention provides a solution to this point. The present invention relates to multicasting, and more particularly to a message multicasting method in a complex network that originally has only equipment for unicast transmission.

【0002】

[Conventional technology]

In order to better understand the present invention, a method of multicasting a message in another network environment and a conventional method used in an internetwork environment will be described.

【0003】

Local Area Network (LAN) LAN is a very special type of subnetwork in that it has a broadcast function that allows a single message to be easily distributed to all nodes. Therefore, the most common method of multicasting on a LAN is to broadcast messages, and messages that are not needed by local users are separated by the connected computer. An example of this appears in "Multicast Routing in Datagram Internetworks and Extended LANs" by SE Deering and DR Cheriton (ACM Transaction on Computer Systems, Vol.8, No.2, pp85-110, ACM, May 1990). However, as mentioned above, such a method seems unsuitable for large-scale interconnects. It should also be mentioned that basically the same considerations apply to the Metropolitan Area Network (MAN).

【0004】

When multiple LAN segments are connected by a bridge, LAN messages can be selected, so broadcast communication is performed only to the segment that has at least one node as the multicast destination. These protocols work as follows (see Deering and Cheriton's work above for examples of variations of the basic algorithms described here):

【0005】

1. Group members broadcast that they are on the LAN to which they are connected. These broadcasts are transmitted by the bridge to all LAN segments so that the bridge can know the location of the group members. 2. When a multicast packet to a group is received, the packet is forwarded only by bridges on the path to one or more members in that group. Therefore, it is possible to prevent each multicast from flowing into all LAN segments.

【0006】

The limitation of such LAN-based multicasting is that the topology of the network must not have a loop shape. That is, for a bridge between any two LAN stations, there must be no multiple paths through it. This condition is required, if it is not met, due to the simple transmission method adopted by the LAN bridge, packets will continue to be broadcast permanently through any loop. Because it ends up. Such a method is not suitable for multicast within a large-scale interconnect. This is because all communications are forced to follow the same path within the interconnect, which creates an unacceptable load on the links associated with it. There are algorithms that allow loops in the LAN topology, but they choose a set of bridges to form a loopless spanning tree for multicast transmission. Therefore, in the end, all multicast communications are restricted to one path along a branch of the spanning tree.

【0007】

Multicast on the internet There are multicasting algorithms that work with the routing protocols used in Internet Protocol (IP) networks. IP networks are packets (called datagrams) for networks of common topology, including LANs, point-to-point links, and even subnetworks like the X25. Provides routing and relay. One IP network consists of a set of sub-networks connected by an IP routing program.

【0008】

All of the routing protocols used in IP networks shown below are based on the distance vector (sometimes called path vector) routing method used in IDRP.

【0009】

Routing Information Protocol (RIP) described in "Routing Information Protocol" by CL Hedrik (RFC 1058 (Request for Comments), NIC (Network Information Center), June 1988). Hello Routing Protocol disclosed in "Experimental Multiple Path Routing Algorithm" by DLMills (RCF 981, NIC, March 1986). Border Gateway Protocol (BGP) described in "Border Gateway Protocol (BGP)" (RCF 1163, NIC, June 1990) by K. Lougheed and Y. Rekhter. Gateway-Gateway Protocol (GGP) disclosed in "DARPA Internet Gateway" (RCF 823, NIC, September 1982) by RM Hinden and A. Sheltzer.

【0010】

As will be revealed later, the present invention provides a directly applicable solution for all of the above-mentioned (and equivalent) routing protocols and call-based networks.

【0011】

The IP multicast algorithm was originally developed for use with the Routing Information Protocol by CLHedrik described above, but it can also be used with other distance vector routing algorithms. IP Multicast Algorithms (see below for examples; already cited by SE Deering and DR Cheriton; "Host Extensions for IP Multicasting" by SE Deering (RFC 1112, NIC, August 1988); L. Hughes and P. Thomlinson "A Multicast Internetwork Routing Algorithm" (IFIP WG 6.4Conference on High Speed Networking, March 18-22, 1991, minutes of Berlin, pp183-200); "Distance Vector" by D. Waitzman, C. Partridge and SE Deering. Multicast "Protocol" (RCF 1075, NIC, August 1988)) is all "Reverse Path Forwarding of Broadcast Packets" (Communications of the ACM, Vol.21, No.12, pp1040-1048, ACM, 1978) by YKDalal and RMMetcalfe. This is a modification of the reverse path broadcast communication algorithm shown in (December). This algorithm is similar to the LAN multicast algorithm. In the LAN multicast algorithm, the spanning tree is used to distribute multicast packets, but it also has the feature of solving some of the problems associated with LAN multicasting. Briefly, this algorithm works as follows (see the previously cited SEDeering and DR Cheriton writings for more information):

【0012】

1. Multicast packets are first broadcast to all subnetworks within the interconnect. Packets are broadcast through a spanning tree that has the lowest cost. The routing program receives a multicast packet from a node "S". The routing table shows that it reaches node "S" at less cost than any other routing program attached to a subnetworks (this information is in the regular IP routing table). If (shown), it recognizes that the routing program is on the multicast spanning tree originating from S. In this case, the routing program sends the multicast packet to the subnet network in question. As demonstrated by SEDeering and DR Cheriton above, this algorithm allows multicast packets to be sent to subnetworks within the Internet at minimal cost.

【0013】

A clear improvement over the LAN multicasting scheme is that the multicast spanning tree is fixed for one source but the same for all sources. The point is that it is not. As a result, the multicast flow will be transmitted through a number of different paths within the network.

【0014】

The following method is adopted to avoid broadcasting multicast packets to sub-networks that do not have members belonging to the specified group. A routing program that receives a multicast for a particular group truncates the received multicast if it is not on a branch of the multicast tree that leads to any member of the particular group ( Obviously there is no need to send it). It then reports to the routing program that precedes itself on the multicast tree that this branch is pruned. This process begins with a routing program attached to the "leaf subnetworks (subnetworks at the ends of individual branches on the tree)", climbing the branches as much as possible, and multicasting. Limit distribution to where it is needed.

【0015】

This IP multicast method has the following drawbacks. Multicast from a source to a group must first be broadcast to the entire Internet unless the multicast tree between the source and destination has been pruned. In this scheme, the information used to mow the multicast tree must be discarded later so that new members joining the branches of the already mowed tree can begin receiving multicast. As a result, the multicast tree is continuously rebuilt and pruned, resulting in enormous overhead on its network links and processing nodes. A multicast tree exists for each pair of source and multicast groups. That is, there is a separate logical multicast tree for each of the different sources that multicast to a group. Therefore, the routing node must maintain a very large database of pruned multicast trees.

【0016】

For this reason, the protocols and algorithms described so far are not suitable for MPTN (Multiprotocol Transport Network) and similar architectures. In order to be a useful algorithm, it must be possible to take advantage of the routing capabilities of gateways that do not have multicast capabilities.

【0017】

More specifically, the following object of the present invention can be raised as a necessary condition for providing the multicast service.

【0018】

1. Multicast packets must not be broadcast to all subnetworks. And it must be restricted to be sent only to subnetworks that have multicast group members. 2. Each multicast packet must be sent only once to each destination subnetwork (that is, no duplicate multicast packet must be generated). 3. This protocol does not require a centralized element. It should be completely distributed. 4. This protocol does not require the spanning tree to be calculated from a centralized database. 5. The routing of multicast packets must be flexible. For example, it is unacceptable to distribute all multicast through a fixed spanning tree. 6. The number of packets to be distributed must be minimized. In particular, it is not permissible to generate individual unicast packets for each destination. 7. The cost of distributing multicast packets must be minimized. Therefore, the appropriate path from the multicast source to each destination must be selected.

【0019】

[Problems to be Solved by the Invention]

Current top-level routing protocols such as the Inter-Domain Routing Protocol (IDRP) (eg, ISO "Information Processing Systems -Telecommunications and Information Exchange between Systems- Protocol for the Exchange Inter-Domain Routing Information Among" "Intermediate Systems to Support Forwarding of ISO8473 PDUs", ISO / DIS CD 10747, 1991, which is the International Standards Organization. (Standardized by Organization, ISO) provides a framework for routing unicast packets, that is, packets sent to a single destination. An important requirement of computer networks in general, especially of the applicant's Multiprotocol Transport Network (MPTN), is the multicasting of data packets sent from a particular source to multiple destination groups. To admit. Generally speaking, the present invention provides methods and systems that use a new set of protocols in combination with current routing protocols (eg, IDRP) to support multicasting in computer networks of all sizes and topologies. , Meets the above requirements. The present invention has properties that can be adapted to an environment not found in any current multicasting protocol.

【0020】

The object of the present invention will be described in more detail below. However, the present invention is not limited to use only in the types of networks described below. Yet another example is described elsewhere herein.

【0021】

A widely used set of protocols, such as IBM's Multi-Protocol Transport Network (MPTN), allows computer applications to combine regardless of the type of network they come with. .. Therefore, as shown in Figure 1, two applications attached to different subnetworks within the same MPTN11 can communicate. In FIG. 1, the client application 12 attached to the first subnetwork 13, such as the NetBIOS subnetworks (which is also the applicant's registered trademark), is, for example, System Network Architecture (SNA, also the applicant's registered trademark). It can communicate with the compatible server application 14 attached to the second subnetwork 15. MPTN gateways 16 and 17 are required to combine three different networks 13, 15 and 18 into one logical network (MPTN). This gateway is, for example, Transmission Control Program / Internet It is coupled via a third subnetworks such as Protocol (TCP / IP).

【0022】

The main function of MPTN gateways 16 and 17 is to route a message from its source (eg client application 12) to its destination (eg server application 14). This is difficult for the following reasons.

【0023】

--You must find a path between the source and destination that meets your application's requirements (safety, speed, reliability, etc.). --MPTN can be very large with many subnetworks and gateways. This results in a very complex network topology, which requires complex routing at the gateway. --A failure of links and nodes or the installation of new equipment will change the topology, and therefore the accurate routing, in real time.

【0024】

In order to solve such a problem, the MPTN gateway uses the above-mentioned routing protocol standardized by the International Standards Organization, the interdomain routing protocol (IDRP). IDRP defines protocol formats and procedures for routing from one source to one destination in networks of all topologies and sizes. However, IDRP does not support multicasting, that is, sending messages from one source to multiple destinations. Multicasting, on the other hand, is basic to MPTN for several reasons. First, some subnetworks support multicasting, and applications running on those subnetworks take advantage of the features of multicasting. Multicasting must be supported within the interconnected environment to allow binding to such applications. Second, there are also some MPTN control protocols that are based on multicasting. As an example, a resource locating protocol requires that a resource be searched for all gateways attached to potential subnetworks.

【0025】

Some examples of problems related to multicasting in the internetwork will be described with reference to the simple MPTN shown in Figure 2. In this example, an application in the subnet W (21) must initiate a multicast and send it to destinations in the subnets X (22) and Z (24). There is no destination within subnet Y (23). The problem is related to the following behavior.

【0026】

--It is not possible to generate separate (ie unicast) messages for all destinations. This is because it imposes an unnecessary load on the resources of MPTN. For example, in Figure 2, this unicast method requires only one multicast message, but one message for each destination between gateway A (25) and gateway B (26). Link will be sent. --Multicasting messages to all subnetworks within MPTN is not allowed. For example, the subnet Y (23) does not need to receive the multicast, which is intended to be sent only to the nodes in the subnets X (22) and Z (24). Although not shown in this example, this method of flooding communications is clearly unacceptable for large MPTNs with many subnetworks and many different multicast groups. --- A packet should be multicast to a subnetwork only once. In the network shown in the example, there are two paths from gateway B (26) to subnetwork X (22), one is a path through gateway D (28) and the other is a path directly from gateway C (29). However, the subnet X (22) only receives one copy of the multicast from the source in the subnet W (21). This rule must be adhered to regardless of the number of gateways attached to subnetworks X (22) and the number of paths that exist between a source and a particular destination subnetworks. It is important to minimize the load on the subnetwork due to the traffic of multicast and to avoid duplication of packet transmission, which requires an error recovery protocol for some applications.

【0027】

[Means for solving problems]

Briefly, the present invention provides methods and systems for multicasting messages from one sending station to multiple receiving stations within a traditional unicast message transmission network using traditional protocols. It has achieved the above-mentioned purpose. The method is to keep a table of subnetworks containing multicast receiving stations or a table of multicast receiving stations on at least some nodes of the network, and appropriate routing information in the header of the multicast message. Is to be included. Still other contents are defined in the claims.

【0028】

The solution presented in the present invention can support multicasting within a large interconnect when used with a routing protocol using distance vectors. ISO "Information Technology -Telecommunications and InformationExchange between Systems-Intermediate System to Intermediate System Intra-Domain Routing Protocol for Usein Conjunction with the Protocol for Providing the Connection" (ISO / DIS 10589, 1990) There are standard OSI IDRP routing protocols disclosed in (Year) and other similar protocols used in IP networks already mentioned for reference. The solution of the present invention is OSPF developed for IP networks ("OSPF" by J. Moy. Link-state routes such as Version 2 , RCF 1247, NIC, July 1991) and OSI IS-IS protocol (see ISO / DIS 10589 above). It can also be used with a specified protocol. Therefore, it can be applied to a wide range of interconnection environments. The present invention provides three new protocols:

【0029】

1. A protocol for distributing routing information based on the network topology and the location of multicast group members, and for generating routing tables using this information. 2. A protocol for efficiently sending multicast packets to all members of a multicast group, given the routing information from the first step above. 3. A protocol for enabling the multicast protocol in an MPTN environment.

【0030】

Details and examples will be described below with reference to the figures.

【0031】

[Example]

The following part of the example is divided into four parts. The first chapter, entitled "Route Designation Information", describes the route specification information to be distributed and the table generated for routing of multicast packets. The second chapter, entitled "Multicast Packet Transmission," describes the procedure for routing multicast packets using the generated table. The third chapter, entitled "Multicast with Reduced Routing Information," describes how the amount of routing information required by multicasting protocols can be reduced. The final fourth chapter, entitled "Using Multicast in MPTNs", provides an example of how MPTNs use the protocols described in the present invention.

【0032】

Route specification information For a better understanding of the present invention, the interdomain routing protocol (IDRP) will be briefly described. Details can be found in ISO / DIS 10589 already referenced.

【0033】

IDRP distributes routing information among gateways in the form of update PDUs (Update Protocol Data Units). The update PDU contains the following fields related to the present invention:

【0034】

1. Reachability Information: This field specifies resources that can be reached along the path specified in this update PDU. This can be the address of a particular end system or a prefix common to addresses used by multiple end system pairs. Since all systems with addresses that include that prefix belong to the same subnetworks, that prefix can uniquely define that subnetworks. The type field defined in this reachability information indicates that the reachability information in question is an address prefix (type = 0). Therefore, different types of reachability information can be distributed by redefining the new type code. 2. Quality of Service: This field specifies characteristics such as cost, delay, and security when using the routing information contained in the update PDU. 3. Path: Route specification information that specifies how to reach the end system specified by the prefix in the reachability information.

【0035】

The gateway creates a routing table called Forwarding Infomation Bases (FIBs) based on the received update PDU. For each destination (the destination is prefixed in the received update PDU and is a node or a set of nodes), the next gateway on the path to that destination (which is: (Determined from the path field in the update PDU) is stored. For each prefix, one path is stored for its own set of quality of service parameters. This path is the best path to guarantee the quality of service specified.

【0036】

The present invention defines a new type of reachability information called a group identifier. Group identifiers are used to address a group of end systems that are supposed to receive a particular set of multicasts. This group identifier is chosen from the common subnetwork address space, but is included in the destination address of the multicast packet to identify the correct group of end systems. The end system, addressed by a particular group identifier, does not have to be located within a common subnet. Choosing group identifiers from the standard address space ensures that they represent valid reachability information even for gateways that do not implement multicast enhancements as shown below. Because.

【0037】

To support unicast interdomain routing, subnetworks report to the gateway the address prefix shared by that node. Using these prefixes, an update PDU is created as described above. In the present invention, the sub-network also reports all group identifiers reachable to the sub-network.

【0038】

Figure 3 shows an example. In this figure, the subnetworks prefixed with X (32) and the subnetworks prefixed with Z (34) also have end systems in group G. Therefore, these subnetworks report prefixes and group identifiers to local gateways C (39) and E (37). Subnetworks W (31) and Y (33) do not have a group identifier to report, so they only report their own prefix. Some subnetworks report multiple group identifiers and prefixes (not shown).

【0039】

The IDRP update PDU is constructed as follows. Update PDUs that do not contain a group identifier are constructed as specified on ISO / DIS CD 10747 above. The update PDU used to signal reachability to the group identifier must contain the following information:

【0040】

--Subnetwork address prefix, and-one or more group identifiers for that subnetwork.

【0041】

Reachability information in the update PDU, including the group identifier, includes the group identifier and an address prefix (or one of multiple prefixes) unique to the end system in the subnet that reports the group identifier. It is composed of. In this way, all gateways will know the relationship between the prefix of the subnetwork and the group identifier that can reach that network.

【0042】

The update PDU constructed as described above, together with the reachability information field, is distributed to all gateways according to the currently used protocol. It should be noted that the construction of this update PDU is permitted by the IDRP standard and there are no other required changes in the construction or distribution of the update PDU.

【0043】

In the example shown in Figure 3, gateway C (39) generates an update PDU with reachability information such as: prefix = X, groupid = G. Similarly, gateway E (37) generates an update PDU with the information prefix = Z, groupid = G. Both of these update PDUs will be distributed to all other gateways, depending on the IDRP protocol, to signal the association between Group G and subnetworks X and Z.

【0044】

When reachability information changes (for example, the prefix changes, or the group identifier is added or removed), the change is reported to the local gateway using the normal IDRP routing protocol. , Update all MPTN gateway information.

【0045】

By constructing the update PDU described above, the gateway is made to create an additional routing table called a multicast routing table or MURT (Multicast Routing Table). This MURT contains, for each group identifier, a list of subnetwork prefixes that contain members of that group. This is the information obtained from the update PDU, including the group identifier. How to use this MURT for routing will be explained in the next chapter.

【0046】

In the system of FIG. 3, following the distribution of the update PDU described above, each gateway provides a MURT entry for the group identifier G, identifying X and Z as prefixes of the subnetwork in which the group members are located.

【0047】

The remaining IDRP routing tables (eg, FIB above) are built according to current IDRP specifications. In particular, path information associated with all reachability information (including group identifiers) is stored in the FIB.

【0048】

So far, the procedure for constructing MURT using the OSI IDRP routing protocol has been described. A similar procedure can be followed for any distance vector routing protocol (see below, for example; "Routing Information Protocol" by CL Hedrick, RCF 1058, NIC, June 1988; by RMHinden and A. Sheltzer, supra. Can be used in conjunction with the work of K. Lougheed and Y. Rekhter described above; the work of DLMills described above). In all of these protocols, update PDUs are distributed to an address or address prefix. Gives reachability information. By associating a group identifier with each address prefix, a MURT is created as described above.

【0049】

MURTs can also be created using the link-state routing protocols described in the aforementioned ISO / DIS 10589 (1990) and J. Moy's writings. In these protocols, each gateway distributes reachability information in the form of link-state PDUs. The link-state PDU provides information about the state of each link adjacent to the gateway, as well as all of the address prefixes that are directly reachable from that gateway. These link-state PDUs are sent unmodified to all other gateways in the system. Therefore, by including the list of group identifiers in the link-state PDU, you can also create a MURT that associates the group with the list of address prefixes of the subnetwork to which the group members belong. Both FIBs created by the distance vector routing protocol or the link state routing protocol are basically equivalent to those created by IDRP. Therefore, it is possible to apply the multicast transmission algorithm described in the next chapter to these environments.

【0050】

Send multicast packets Conceptually, once the MURT is built, as mentioned in the previous chapter, routing multicast packets is very easy. MURT will identify the subnetwork in which the multicast group is located. In addition, IDRP FIB can be used to route packets to each of these subnetworks. A copy of each multicast packet can also be simply routed to each of these subnetworks. However, considering the limitation on the number of packets to be distributed due to the conditions required for MPTN specified in "Means for Solving Problems", the methods and algorithms clarified in this chapter can be said to be the basic part of the present invention.

【0051】

For routing multicast packets within MPTN, the present invention also defines the Multicast Spanning Tree Algorithm (MSTA). MSTA can also be used in other networks that provide routing information similar to the routing information clarified in the previous chapter.

【0052】

To help the reader understand, I'll give an example of MSTA before going into the details of the algorithm.

【0053】

Figure 3 shows the topology of the network used in this example. Using the protocol from the previous chapter, the following routing table is created at each MPTN gateway.

【0054】

At gateway A (35) FIB (prefix: next hop on shortest path) address prefix W: addresses with this prefix are located in the local subnet (31) X: the next gateway on the path to the subnet containing addresseswith this prefix is Gateway B. Y: gateway B Z: gateway B G: gateway B MURT (grouid: associated prefixes) groupid G: the prefixes associated with this groupid are X, Z At gateway B (36) FIB (prefix: next hop on shortest path) W: the next gateway on the path to the subnet containing addresseswith this prefix is Gateway A. X: gateway C Y: gateway D Z: gateway E G: gateway E MURT (grouid: associated prefixes) groupid G: the prefixes associated with this groupid are X, Z At gateway C (39) FIB (prefix: next hop on shortest path) address prefix X: addresses with this prefix are located in the local subnet (32) W: the next gateway on the path to the subnet containing addresseswith this prefix is Gateway B. Y: gateway D Z: gateway B G: local subnet (32) MURT (grouid: associated prefixes) groupid G: the prefixes associated with this groupid are X, Z At gateway D (38) FIB (prefix: next hop on shortest path) address prefix Y: addresses with this prefix are located in the local subnet (33) W: the next gateway on the path to the subnet containing addresseswith this prefix is Gateway B. X: gateway C Z: gateway B G: gateway C MURT (grouid: associated prefixes) groupid G: the prefixes associated with this groupid are X, Z At gateway E (37) FIB (prefix: next hop on shortest path) address prefix Z: addresses with this prefix are located in the local subnet (34) W: the next gateway on the path to the subnet containing addresseswith this prefix is Gateway B. X: gateway B Y: gateway B G: localsubnet (34) MURT (grouid: associated prefixes) groupid G: the prefixes associated with this groupid are X, Z [0055]

The basic layout is shown in Figure 3. In this example, G is the group identifier of the multicast group that has members in subnetworks X (32) and Z (34). The source node in the subnet W (31) sends a multicast to the group identifier G.

【0056】

MPTN gateway A (35) receives a multicast packet addressed to group identifier G from subnetwork W (31). The MURT entry indicates that the multicast should be sent to a subnetwork prefixed with X (32) and Z (34). From that FIB, gateway A (35) determines that the next hop is gateway B (36) for both X and Z. Therefore, gateway A (35) sends an MPTN multicast packet to gateway B (36) with the following fields.

【0057】

destination = G target subnetoworks = X, Z data as specified in the original multicast packet [0058] [0058]

Note that the target subnetworks field specifies all destinations unique to this multicast on a path. Since both subnetworks X (32) and Z (34) are reached through gateway B (36), packets are sent from gateway A (35) to gateway B (36) to perform this multicast. You only need to send one.

【0059】

Gateway B (36) receives the multicast packet described above. Since the target subnetworks are specified, there is no need to use MURT. This fact means that only gateways attached to nodes that can be sources of multicast need to hold MURTs. All other gateways do not need to create this table. Gateway B uses its FIB to determine that the next hop to subnet X is gateway C (39) and for subnet Z (34) is gateway E (37). Therefore, gateway B sends an MPTN multicast packet to gateway C with the following fields:

【0060】

destination = G target subnetoworks = X data as specified in the original multicast packet [0061]

Note that the target subnetworks field only contains subnetworks on this path. Subnet Z (34) is reached via a different path, so Z is not included in the multicast to gateway C (39).

【0062】

Similarly, gateway B (36) sends an MPTN multicast packet to gateway E (37) with the following fields:

【0063】

destination = G target subnetoworks = Z data as specified in the original multicast packet [0064]

Gateway C (39) receives a multicast assigned to the subnet X (32) to which it is installed. Then, the packet is multicast to the group identifier G in the subnetwork X. Similarly, gateway E (37) multicasts packets in subnetwork Z (34) to all members of group identifier G. Thus, this multicast is sent to all members of the part loop identifier G. This algorithm meets all the requirements of MPTN for efficient multicast.

【0065】

1. Packets are only multicast to subnetworks where multicast group members reside (X and Z. Y are not included in the example shown). MURT defines the destination subnetworks. 2. Each multicast packet is sent to each subnetwork exactly once. Purpose of MPTN Multicast Use the subnetwork field to ensure that each subnetwork receives exactly one copy of the multicast. 3. There is no centralized element. The creation of MURTs and the routing of multicast packets are completely distributed. 4. This algorithm does not need to calculate the spanning tree from the topology database. Five. This multicast routing has all the flexibility of regular MPTN routing. Route the multicast packet using the regular IDRP FIB, as shown in the example. This means that different routes may be used for different multicast packets due to different quality of service requirements and / or changes in network state (topology or load). .. 6. The number of packets sent is minimized. Multicast packets to several destinations (X and Z in the example) are sent as separate packets only if the routes to different destinations are not the same. In the example shown, only one packet is sent from gateway A to gateway B, but individual packets are sent from gateway B to gateways C and E. 7. Multicast packets are sent to each destination through the optimal route according to the IDRP FIB. A unicast packet to one of a destination follows the path that the multicast packet to that destination takes.

【0066】

It is also important that only one MURT entry is generated per multicast group. The multicast algorithm for the Internet Protocol described in "Conventional Techniques" herein required the node to create a multicast table with an entry for each set of source groups (and therefore). The number of entries is double the total number of sources when compared to the MPTN method).

【0067】

Now that we have briefly described the MPTN multicast packet transmission algorithm, we will clarify the details of the multicasting procedure. First, one procedure is specified for the MPTN that receives the multicast packet from the subnetwork (Listing A), and then one is specified for the intermediate MPTN gateway that sends the multicast received from the other gateway (Listing B). ).

【0068】

Listing A-Procedure: Initiating MPTN Multicast This procedure is used by MPTN gateways that receive multicast packets from subnetworks. Input: Subnetwork multicast packet that specifies the destination group identifier, quality of service, and data to be multicast. output: An MPTN multicast packet to the next gateway on the path to the destination, or a direct multicast to the target subnetworks that are directly connected to that gateway. Using the group identifier specified in MURT as a key gives a list of prefixes for the subnetworks that contain members of that group. For each prefix in the list The prefix and the quality of service specified, IDRP Used as a key to the FIB to determine the next hop gateway on the path to its subnetworks. Add that prefix to the list for the next hop. For each of the following hop lists created as described above, set the destination subnetworks to the list of prefixes associated with the next hop. Sends an MPTN multicast containing the group identifier (groupid), the target subnetwork (target_subnetwork), the quality of service, and the data to the next hop. Note that the subnet of interest may be directly connected to this gateway, in which case the multicast will be sent directly to that subnet. Listing B-Procedure: Sending MPTN Multicast This procedure is used by MPTN gateways to send multicast packets received from other MPTN gateways. Input: MPTN Multicast, including the destination group identifier, quality of service, and data created by the MPTN Multicast start procedure. output: An MPTN multicast packet to the next gateway on the path to the destination, or a direct multicast to the target subnetworks that are directly connected to that gateway. For each prefix of the received purpose subnetwork list The prefix and the quality of service specified are used as a key to the IDRP FIB to determine the next hop gateway on the path to its subnetworks. Add that prefix to the list for the next hop. For each of the following hop lists created as described above, set the destination subnetworks to the list of prefixes associated with the next hop. Sends an MPTN multicast containing the group identifier (groupid), the target subnetwork (target_subnetwork), the quality of service, and the data to the next hop. Note that the subnet of interest may be directly connected to this gateway, in which case the multicast will be sent directly to that subnet.

【0069】

Multicast with reduced routing information The multicasting scheme described in the previous chapter requires a group of MURT entries for all gateways attached to nodes that can be sources of multicast for that group. This is not desirable for large MPTNs with large groups. Therefore, this chapter describes another method. In that scheme, MURT entries for a particular multicast group need to be retained only at gateways attached to subnetworks that contain members belonging to that group (other gateways optionally have these MURT entries). May be retained). As will be described later, this method potentially reduces the amount of storage required to support multicasting, at the expense of optimal routing. The methods described in this chapter are an integral part of the present invention and can be used with or in place of conventional methods.

【0070】

In this scheme, the subnetworks report the group identifier and address prefix to the adjacent gateway, as described in the chapter entitled Routing Information. These gateways must make a MURT entry for the specified group identifier. You must also create an IDRP update PDU. However, gateways that are not attached to a subnetwork that contains members of a particular group identifier are not forced to retain a MURT entry for that group identifier.

【0071】

The transmission of the packet addressed to a certain group identifier is performed as follows.

【0072】

--If the packet sent has a set of target subnet fields from the previous MPTN gateway, it will be sent according to the algorithm in Listing B. This is done by all gateways. This algorithm does not require MURT (destination prefix is specified in the destination subnetwork field). --If the packet sent does not have a set of destination subnet fields and its destination address is the group identifier that holds the MURT entry at this gateway, it follows the procedure for initiating MPTN multicast in Listing A. --If the packet being sent does not have a set of target subnet fields and no MURT entry is held for its destination address, the packet will be point-to-point based on the IDRP FIB entry for that address. -to-point) Sent to the expression.

【0073】

If only gateways attached to a subnet to which a member of a group belongs have a MURT entry for that group identifier, the packet is point-to-point routed to one of those gateways. .. By doing so, the packet is multicast to the remaining gateways.

【0074】

An example of the algorithm for routing with the reduced information described above will be described again with reference to the network shown in FIG. Using the protocol clarified in this chapter, the following routing table is created at each MPTN gateway.

【0075】

At gateway A (35) FIB (prefix: next hop on shortest path) address prefix W: addresses with this prefix are located in the local subnet (31) X: the next gateway on the path to the subnet containing addresseswith this prefix is Gateway B. Y: gateway B Z: gateway B G: gateway B At gateway B (36) FIB (prefix: next hop on shortest path) W: the next gateway on the path to the subnet containing addresseswith this prefix is Gateway A. X: gateway C Y: gateway D Z: gateway E G: gateway E At gateway C (39) FIB (prefix: next hop on shortest path) address prefix X: addresses with this prefix are located in the local subnet (32) W: the next gateway on the path to the subnet containing addresseswith this prefix is Gateway B. Y: gateway D Z: gateway B G: local subnet (32) MURT (grouid: associated prefixes) groupid G: the prefixes associated with this groupid are X, Z At gateway D (38) FIB (prefix: next hop on shortest path) address prefix Y: addresses with this prefix are located in the local subnet (33) W: the next gateway on the path to the subnet containing addresseswith this prefix is Gateway B. X: gateway C Z: gateway B G: gateway C At gateway E (37) FIB (prefix: next hop on shortest path) address prefix Z: addresses with this prefix are located in the local subnet (34) W: the next gateway on the path to the subnet containing addresseswith this prefix is Gateway B. X: gateway B Y: gateway B G: localsubnet (34) MURT (grouid: associated prefixes) groupid G: the prefixes associated with this groupid are X, Z [0076]

In this example, "G" is the group identifier of the multicast group to which the members belong within the subnet X (32) and Z (34). Then assume that only gateways C (39) and E (37) hold the MURT entry for group identifier G. Therefore, all other gateways treat G like a unicast address (currently following the IDRP procedure) and keep one entry for G in each FIB. The fact that multiple gateways (gateways C and E in the example) are notifying G of one path is not a problem. This is because IDRP recognizes this. However, the gateway only stores (in the FIB) route information about the best path for a prefix. For example, gateway B (36) has a FIB entry for gateway E (37) rather than gateway C (39) in relation to G. E and C can be reversed, but in any case only one of the paths is stored in the FIB.

【0077】

MPTN gateway A (35) receives a multicast packet addressed to G from subnetwork W (31). Since gateway A does not have a MURT entry for G, the packet is routed based on the FIB entry for G with the following fields.

【0078】

destination = G target subnetoworks = not set data as specified in the original multicast packet [0079]

The target subnet field is not set because there is no MURT entry for G.

【0080】

When the gateway B (36) receives the packet, since there is no MURT entry for G, the gateway B (36) routes the packet to the gateway E (37) with the following fields based on the FIB entry for G.

【0081】

destination = G target subnetoworks = not set data as specified in the original multicast packet [0082]

Gateway E (37) is attached to the subnet Z to which the members of group G belong, so there is a MURT entry for G. MURT indicates that the packet should be multicast to a subnetwork prefixed with X and Z. Since the subnet network Z (34) is connected, the gateway E multicasts the packet to the subnet network Z. Since the FIB entry for subnet X (32) is gateway B (36), MPTN multicast packets are sent to gateway B with the following fields:

【0083】

destination = G target subnetoworks = X data as specified in the original multicast packet [0084]

Now that the target subnetwork field is set, gateway B (36) sends the packet based on the above field (the routing made here contrasts with the routing at gateway B above. ). Then, since the FIB entry for the subnet X (32) becomes the gateway C (39), the MPTN multicast packet is sent to the gateway C together with the following fields.

【0085】

destination = G target subnetoworks = X data as specified in the original multicast packet [0086]

Finally, gateway C (39) multicasts the example packet to the group identifier G in the subnetwork X (32) to which it is attached.

【0087】

Note that in this example, the packet is routed through gateway B (36) twice. The first time, the target subnet field was not set. It was set again. Thus, saving storage capacity by not holding MURT entries at gateways A, B, and D (35, 36, and 38) comes at the expense of near-optimal routing behavior for multicast packets. ..

【0088】

Use of multicast in MPTN As mentioned above, MPTN relies on multicasting to support multicast by applications using MPTN and to support MPTN control algorithms. This chapter describes the problems in this case and their solutions.

【0089】

Current routing protocols require that all nodes with common prefixes be located within a single subnetworks. In this way, the prefix uniquely defines a subnetwork, and operations on nodes with a prefix can be performed entirely within that subnetwork. This is shown in FIG.

【0090】

MPTN allows nodes in different subnetworks to have the same address prefix. As such, such prefixes do not uniquely define a particular subnetworks. Also, actions related to nodes with this prefix must be distributed to multiple subnetworks. This is shown in FIG. This is called a "split net id". "Net id" is synonymous with address prefix, and "split" means that a node with a net id is split between different subnetworks. The subnetwork containing the nodes of the split net id is called the "island" of that split net id. Figure 5 shows a split net id with three islands. Supporting such split net ids includes MPTN behavior such as:

【0091】

1. Multicasting of packets by MPTN users to nodes with split net ids must be distributed to all subnetworks including those nodes. 2. In order to route the join of the split net id to the node and unicast the datagram, the MPTN gateway must first determine which island of the split net id the destination is located on. .. 3. The subnetwork protocol, which guarantees that the addresses used within the subnetwork are unique, must be extended to all islands of the split net id. This is because nodes with the same address exist on those islands because they use the same address prefix.

【0092】

To support split net ids, the multicast protocol described herein is used. In particular, the address prefix common to the nodes of the split net id is treated like a group identifier, and this group identifier is registered in all MPTN gateways adjacent to all islands of the split net id. Therefore, its group identifier defines a group of all islands with a split net id. Received user datagrams and requests for joins specify a destination address that begins with the split net id prefix (ie, the group identifier). This is because the user wants to communicate with the resource in the split net id. MPTN control packets are addressed to their group identifier to communicate with a single gateway attached to each island of the split net id. Like other groups, each group member (that is, each island) also requires its own prefix associated with the group identifier in the MURT. This is obtained as follows.

【0093】

The address within its subnetwork of each gateway connected to a split net id is unique and unique overall (this overall uniqueness is the subnetwork protocol). Guaranteed by). If this gateway is the only gateway connected to the island with its split net id, it will use its address in the subnetwork as its own prefix for that island. be able to. All of the classes of routing protocols relevant to the present invention (eg IDRP, IP, OSPF, OSI IS-IS) require gateways to communicate and exchange routing information, so split net id Automatically contact all gateways connected to the same island (all gateways that exchange routing information over their subnetworks). Therefore, if multiple gateways are connected to the same island with a split net id, or if there is an addition or removal to a set of gateways connected to an island with a split net id, that will be recognized by the gateway. To.

【0094】

Here's how to choose a unique prefix associated with an island with a split net id: [0095]

1. When a gateway is first activated, its address shall be used as a unique prefix to the island of split net ids to which it is connected. 2. Whenever a gateway recognizes the existence of other gateways connected to the same island, it checks the addresses of all those gateways and gives the smallest address (which may be its own). Use it as your own address for that split net id. Since all gateways are running this algorithm, they focus on using the same address as the prefix that uniquely defines the island.

【0096】

This step must be repeated whenever there is an addition or removal to or from a set of gateways connected to the island of the local split net id.

【0097】

This method is effective for split net id islands when two or more disjointed islands are combined into one island, or when one island is dynamically divided into several islands. Given a unique prefix. This algorithm is fully distributed and guarantees that gateways connected to islands with split net ids will be correctly assigned their own prefixes.

【0098】

The unique address prefix associated with the split net id is called the "derived net id". This is shown in Fig. 6.

【0099】

In Figure 6, two nodes with the address prefix X are located within this different subnetworks. The split net idX is a gateway connected to these sub-networks and is registered as a group identifier. Gateway G (62) is the only gateway connected to the island above the split net idX. Therefore, use its local address, X.7, as its own prefix associated with the group identifier X. Gateways H (63) and I (64) are connected to the island below this split net id. Since the address of gateway H is smaller than the address of gateway I (X.8 is smaller than X.9), both gateways use X.8 as their own prefix associated with the group identifier X. To do. Using the protocol of the invention, gateway F (61) creates an entry associated with the address prefix X in the FIB and MURT tables shown in the figure.

【0100】

It is possible to support split net ids in MPTNs using the multicast protocol in the previous chapter and the procedure for mapping split net ids to group identifiers and derived net ids in this chapter.

【0101】

If the MPTN user packet is multicast to all nodes prefixed with X, then the packet is distributed across the islands of the split net id using the procedure in the previous chapter, since X is an entry for MURT. Similarly, the flow of communication that is part of the subnetwork name management protocol is multicast across the split net id.

【0102】

If a join or unicast datagram is sent to a single node prefixed with X (such as X.3 in the example in Figure 6), additional protocols that form another part of the invention are needed. Ru. MPTN gateways required to route unicast packets and joins based on the address prefix shown on the MURT use this procedure.

【0103】

1. Using the multicast scheme described in the present invention, the LOCATE request is distributed to one of the MPTN gateways connected to each island of the split net id. The LOCATE parameter is the specific address that was originally the purpose of the unicast packet (the resource to be allocated). In this example, gateway F (61) multicasts LOCATE to gateways G (62) and H (63) to locate resource X.3. 2. Each gateway that receives this LOCATE request searches for a connected subnetwork (using the native protocol of that subnetwork, or MPTN protocol), and the target resource is in the island of the split net id. Determine if it is located in. As an example, gateway G (62) finds it in a subnetwork to which X.3 is connected, but gateway h (63) cannot find the location of X.3. 3. All gateways that receive this LOCATE request return to the MPTN gateway that initiated this search a response containing the responder's own prefix and a flag indicating whether the resource was found. In the example, gateway G (62) returns to gateway F (61) a response containing its own address prefix X.7 and a flag indicating that the resource was found. Gateway H (63) returns a result indicating that the resource was not found. 4. Upon receiving a positive response to this search, Gateway F (61) can route the unicast message or join to the correct destination. The header of this request must indicate to which gateway the request is routed (X.7 in the example) so that all gateways can send the request. The header must also include the address (X.3) to which the request should be sent so that the last gateway can route the request to the subnet containing the destination.

【0104】

It is important that a gateway that fails to locate a resource sends a negative response to LOCATE Yokyu. Otherwise, if the desired resource does not exist (in the example, if the user uses it to send a message to a non-existent X.5), the gateway that routes the request will wait forever for a response. I will continue. If you receive a negative response from each gateway, you know that the resource is unreachable and you can remove the request.

【0105】

[Effect of the invention]

The protocol provided by the present invention enables efficient multicasting of messages in a complex network that originally has only equipment for unicast transmission.

[Simple explanation of drawings]

[Figure 1]

It is a figure of a multi-protocol transmission network (MPTN) composed of three sub-networks.

[Figure 2]

It is a figure which shows the example of another MPTN.

[Fig. 3]

It is a figure which shows the example of the information obtained from the sub-network where the gateway is attached.

[Fig. 4]

It is a figure which shows the detail of a certain sub-network. All nodes in this subnet have a common address prefix.

[Fig. 5]

It is a figure which shows that the node which has a certain common address prefix is divided among different subnetworks.

[Fig. 6]

It is a figure which shows that the split net id is supported in MPTN.

[Explanation of symbols]

12 Client application 13 NetBIOS subnetwork 14 Server application 15 SNA Subnetwork 16 MPTN gateway 17 MPTN gateway 18 TCP / IP Subnetwork 21 Multicast Source Subnetwork W 22 Multicast Destination Subnetwork X 23 Subnetwork Y 24 Multicast Destination Subnetwork Z