JP2010278777A - Overlay node and overlay network system - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To shorten a transfer delay of multicast traffic between end nodes in overlay multicast. <P>SOLUTION: An overlay node includes a capacity managing part and a reconnection managing part. The capacity managing part calculates the capacity of a self-node, and transmits a capacity notification message showing the capacity and address of the self-node to the next hop node of a downstream side. The reconnection managing part performs reconnection instruction processing in response to the capacity notification message received from an upstream side. In the reconnection instruction processing, the reconnection managing part selects an end node within the number of permissions from local end node that is currently connected to the self-node with reference to the notified capacity. Then, the reconnection managing part instructs the selected end node so as to reconnect an upstream overlay node designated by the notified address. <P>COPYRIGHT: (C)2011,JPO&INPIT

Description

  The present invention relates to an overlay network in which a multicast tree is constructed, overlay nodes constituting the overlay network, and a method of reconnecting end nodes in the multicast tree.

  An “overlay network”, which is a virtual network constructed on a physical network composed of IP routers or the like, is known. FIG. 1 is a schematic diagram showing an overlay network. The nodes constituting the overlay network are hereinafter referred to as “overlay node 100”. As shown in FIG. 1, a link that connects between overlay nodes 100 in an overlay network is called a virtual link or a logical link with respect to a physical link that actually connects nodes in a physical network.

  On the other hand, multicast has been attracting attention for a long time as a method of performing one-to-many or many-to-many communication. As a method for realizing multicast, IP multicast has been conventionally known. However, in IP multicast, since all routers on the network need to be compatible with IP multicast, the spread has not progressed. Today, “overlay multicast” which performs multicast on an overlay network is attracting attention as another implementation method (see Patent Document 1). In overlay multicast, routers on the physical network do not need to support IP multicast, so there are fewer obstacles to diffusion than IP multicast. For this reason, use in a wide range of fields such as broadcast distribution of moving image data and real-time broadcast distribution of stock information, sensor information, etc. is being studied.

  A node responsible for transmission and reception of multicast traffic in overlay multicast is hereinafter referred to as “end node 200”. The overlay node 100 constituting the overlay network transfers multicast traffic in the overlay network. The overlay multicast is generally realized by the following four steps.

(1) Construction of Overlay Network First, each overlay node 100 determines an adjacent node on the overlay network based on DHT (Distributed Hash Table), Skip Graph, etc., and creates a virtual link between the adjacent nodes. Thereby, an overlay network is constructed.

(2) Discovery and connection of overlay network by end node Next, the end node 200 discovers the overlay node 100 for connecting to the overlay network by using a bootstrap server or broadcasting a search message. To do. For example, when a bootstrap server is used, the bootstrap server maintains a list of overlay nodes 100, and some policy (random, overlay node load, physical proximity from an end node) from the list. Is selected, and the selected overlay node 100 is notified to the end node 200. When the search message is broadcast, the overlay node 100 that has received the broadcast returns a reply to the end node 200, and the end node 200 generally selects the overlay node 100 that has returned the reply the earliest.

  The end node 200 connects to the selected overlay node 100 using IP, UDP, TCP, SSL, or the like. Thereafter, the end node 200 exchanges traffic with other end nodes using the overlay network through the overlay node 100 discovered and connected in this step. The overlay node 100 to which the end node 200 is connected is hereinafter referred to as an “edge node”. Note that if the end node 200 itself has sufficient capability to process DHT or Skip Graph, the end node 200 and the edge node may be physically the same.

(3) Creation of a multicast group A multicast group is created according to a physical organization such as a company department or a local community, or a category of information of interest. The created multicast group is notified to the end node 200 through a directory server or the like together with a method for joining the multicast group.

(4) Creation of Multicast Tree The end node 200 desiring to join the multicast group transmits a request to join the multicast group to the edge node. The edge node transfers the participation request received from the end node 200 to another overlay node using the overlay network. Eventually, a multicast tree is created that connects the edge nodes of all end nodes 200 that participate in the same multicast group. The traffic transmitted toward the multicast group is transferred on the multicast tree and reaches each end node 200. Many studies have been conducted on the multicast tree method. Several examples will be described below.

  FIG. 2 is a schematic diagram showing a “sender-based” multicast tree. In FIG. 2, overlay nodes 100-A, 100-B, 100-C, 100-SE, and end nodes 200-B1, 200-C1, 200-C2, and 200-S are shown. The end node 200-B1 is connected to the overlay node 100-B. That is, the overlay node 100-B is an edge node of the end node 200-B1. The end nodes 200-C1 and 200-C2 are connected to the overlay node 100-C. That is, the overlay node 100-C is an edge node of the end nodes 200-C1 and 200-C2. The end node 200-S is a sender of multicast traffic (hereinafter referred to as “sender end node”). The sender end node 200-S is connected to the overlay node 100-SE. That is, the overlay node 100-SE is an edge node of the sender end node 200-S (hereinafter referred to as “sender edge node”).

  In the sender-based method, a sender end node 200-S of a certain multicast group broadcasts information on the multicast group to the entire overlay network. Each end node 200 receives the broadcast. The end node 200 desiring to join the multicast group transmits a join request whose destination is set to the sender end node 200-S to the overlay network (edge node). The participation request is sequentially transferred on the overlay network by the overlay node 100, and finally reaches the sender end node 200-S. When transferring the participation request, each overlay node 100 registers the immediately preceding node (that is, the transmission source of the participation request) in its own multicast routing table. At the time of forwarding multicast traffic, each overlay node 100 forwards traffic to a node registered in the multicast routing table (that is, the transmission source of the participation request). In this way, a path from the sender end node 200-S to each end node 200, that is, a multicast tree is created.

The sender base method is DVMRP (Distance Vector) originally developed by IP multicast.
Multicast Routing Protocol (see Non-Patent Document 1) is applied to overlay multicast.

  FIG. 3 is a schematic diagram showing a multicast tree of the “Rendezvous base method”. According to the rendezvous base method, any one overlay node 100 is selected as “Rendezvous node 100-RP” when a multicast group is created. Then, the end node 200 desiring to join the multicast group transmits a join request whose destination is set to the rendezvous node 100-RP to the overlay network (edge node). The participation request is sequentially transferred on the overlay network by the overlay node 100 and finally reaches the rendezvous node 100-RP. When transferring the participation request, each overlay node 100 registers the immediately preceding node (that is, the transmission source of the participation request) in its own multicast routing table.

  As shown in FIG. 3, the sender end node 200-S of the multicast group transmits traffic to the edge node 100-E. The edge node 100-E once transfers the received traffic toward the rendezvous node 100-RP. When the rendezvous node 100-RP receives the traffic, the rendezvous node 100-RP transmits the traffic toward all the other end nodes 200 participating in the same multicast group. Each overlay node 100 forwards the traffic to the node registered in the multicast routing table (that is, the transmission source of the participation request). In this way, a bidirectional path, that is, a multicast tree is created between the rendezvous node 100-RP and each end node 200.

  The rendezvous base method is disclosed in Non-Patent Document 2 and Non-Patent Document 3, for example.

JP 2004-304799 A

D. Waitzman et al., “Distance Vector Multicast Routing Protocol”, IETF, RFC 1075, November 1988. Peter R. Pietzuch, “Hermes: A scalableevent-based middleware”, Technical Report, Number 590, UCAM-CL-TR-590, ISSN1476-2986, University of Cambridge, 2004. M. Castro et al., “SCRIBE: A large-scale and decentralized application-level multicast infrastructure”, IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 20, NO. 8, OCTOBER 2002.

  According to the prior art, the number of hops in the multicast tree constructed on the overlay network increases, and there is a possibility that the multicast traffic transfer delay between the end nodes 200 increases.

  This is because the topology of the overlay network is not considered when the edge node is selected in step (2). Conventionally, the edge node is randomly selected from the overlay node 100 or selected based on physical proximity to the end node 200. At this time, the number of hops on the overlay network between the edge node and the rendezvous node 100-RP or the sender edge node 100-SE is not considered. Therefore, there is a possibility that the selected edge node is separated from the rendezvous node 100-RP and the sender edge node 100-SE by many hops in the overlay network. As a result, a multicast tree having a large number of hops between the end nodes 200 is created, and a multicast traffic transfer delay between the end nodes 200 increases.

  One object of the present invention is to reduce the transmission delay of multicast traffic between end nodes in overlay multicast.

  A multicast tree is constructed on the overlay network. In the overlay network, the transfer direction of the participation request to the multicast group is defined as the upstream direction, and the reverse direction of the upstream direction is defined as the downstream direction. In the multicast tree, a node adjacent on the downstream side is a next hop node, and a node adjacent on the upstream side is a previous hop node. The “capacity” of a certain overlay node is a parameter corresponding to the allowable number of end nodes that can be additionally connected to the overlay node.

  In a first aspect of the present invention, an overlay node constituting an overlay network is provided. The overlay node includes a capacity management unit and a reconnection management unit. The capacity management unit calculates the capacity of the own node, and transmits a capacity notification message indicating the capacity and address of the own node to the next hop node. On the other hand, the reconnection management unit performs reconnection instruction processing in response to the capacity notification message received from the upstream side. Here, the capacity and the address indicated in the capacity notification message received from the upstream side are referred to as the notification capacity and the upstream node address, respectively. In the reconnection instruction process, the reconnection management unit refers to the notification capacity and selects an end node within the above allowable number from the local end nodes currently connected to the own node. Then, the reconnection management unit instructs the selected end node to reconnect to the upstream node that is the overlay node specified by the upstream node address.

  In a second aspect of the present invention, an overlay network system in which a multicast tree is constructed is provided. The multicast tree includes a first overlay node and a second overlay node located downstream of the first overlay node. The first overlay node calculates the capacity of the first overlay node, and transmits a capacity notification message indicating the capacity and address of the first overlay node downstream. The second overlay node refers to the capacity of the first overlay node indicated by the capacity notification message, and selects an end node within the above allowable number from the local end nodes currently connected to the second overlay node. . Further, the second overlay node transmits a reconnection instruction message indicating the address of the first overlay node to the selected end node. Upon receiving the reconnection instruction message, the selected end node transmits a reconnection request to the first overlay node, and uses the first overlay node as a new edge node instead of the second overlay node.

  In a third aspect of the present invention, a method for reconnecting end nodes in a multicast tree constructed on an overlay network is provided. The multicast tree includes a first overlay node and a second overlay node located downstream from the first overlay node. The reconnection method includes: (A) calculating a capacity of the first overlay node in the first overlay node; and (B) a capacity notification message indicating the capacity and address of the first overlay node. Transmitting downstream from the node, and (C) at the second overlay node, from the local end node currently connected to the second overlay node based on the capacity of the first overlay node indicated in the capacity notification message Selecting an end node within the above allowable number; and (D) transmitting a reconnection instruction message indicating the address of the first overlay node from the second overlay node to the selected end node; E) Responding to the reconnection instruction message And, and transmitting the reconnection request to the first overlay node from the selected end nodes, the.

  According to the present invention, it is possible to reduce a multicast traffic transfer delay between end nodes in overlay multicast.

FIG. 1 is a schematic diagram showing an overlay network. FIG. 2 is a schematic diagram showing a sender-based multicast tree constructed on the overlay network. FIG. 3 is a schematic diagram showing a rendezvous based multicast tree constructed on an overlay network. FIG. 4 is a schematic diagram for explaining the end node reconnection processing in the embodiment of the present invention. FIG. 5 is a block diagram showing a configuration of an overlay node according to the first embodiment of the present invention. FIG. 6 shows an example of the multicast routing table. FIG. 7 shows an example of communication between nodes in a multicast tree. FIG. 8 shows an example of traffic information. FIG. 9 is a block diagram showing the configuration of the end node according to the embodiment of the present invention. FIG. 10 is a schematic diagram for explaining an operation example in the first embodiment. FIG. 11 is a schematic diagram for explaining an operation example in the first embodiment. FIG. 12 is a block diagram showing a configuration of an overlay node according to the second embodiment of the present invention. FIG. 13 is a block diagram showing a configuration of an overlay node according to the third embodiment of the present invention. FIG. 14 is a schematic diagram for explaining an operation example in the third embodiment. FIG. 15 is a table summarizing the status of each overlay node and each end node in FIG. FIG. 16 is a block diagram showing a configuration of an overlay node according to the fourth embodiment of the present invention. FIG. 17 is a schematic diagram for explaining an operation example in the fourth embodiment. FIG. 18 is a table that summarizes the status of each overlay node and each end node in FIG. FIG. 19 shows an example of end node management information.

  Also in the embodiment of the present invention, an overlay network (overlay network system) as shown in FIG. 1 is constructed. Also, a multicast tree as shown in FIGS. 2 and 3 is constructed on the overlay network. First, terms used in this embodiment are defined.

  In the overlay network, the transfer direction of the request to join the multicast group is defined as the “upstream” direction (see FIGS. 2 and 3). On the other hand, the reverse direction of the upstream direction is defined as the “downstream” direction. The most upstream overlay node 100 is referred to as a base node. As shown in FIG. 2, when the multicast tree is based on a sender-based scheme, the base node is the sender edge node 100-SE. As shown in FIG. 3, when the multicast tree is based on the rendezvous base method, the base node is the rendezvous node 100-RP. In the multicast tree, the direction closer to the base node (100-SE, 100-RP) is the upstream direction, and the direction further away from the base node is the downstream direction.

  In the multicast tree, a node adjacent to the downstream side of its own node is referred to as a “next hop node”. On the other hand, in the multicast tree, a node adjacent to the upstream side of its own node is referred to as a “previous hop node”. That is, the transmission source that transmitted the participation request to the own node is the next hop node, and the transfer destination to which the own node transfers the participation request is the previous hop node. In other words, the next hop node is farther from the base node (100-SE, 100-RP) than its own node, and the previous hop node is closer to the base node than its own node. In the case of the sender-based method shown in FIG. 2, the next hop node matches the multicast traffic forwarding destination.

  However, in the case of the rendezvous base method shown in FIG. 3, the next hop node does not necessarily match the multicast traffic transfer destination. For example, in FIG. 3, the overlay node 100-E located between the sender end node 200-S and the rendezvous node 100-RP transfers the participation request to the adjacent overlay node 100-D. Therefore, the overlay node 100-D is a previous hop node of the overlay node 100-E. In the overlay multicast, the overlay node 100-E transfers the multicast traffic to the overlay node 100-D that is the previous hop node.

  An end node 200 having an overlay node 100 as an edge node is referred to as a “local end node” of the overlay node 100. A local end node 200 of an overlay node 100 is directly connected to the overlay node 100. The total number of local end nodes 200 connectable to a certain overlay node 100 is the maximum connectable number NM. The number of local end nodes 200 currently connected to the overlay node 100 is the currently connected number NC. The difference (NM−NC) between the maximum connectable number NM and the current connection number NC is the additional connection allowable number NA. The additional connection allowable number NA is an allowable number of local end nodes 200 that can be additionally connected to the overlay node 100.

  The allowable additional connection number NA depends on the remaining resource amount of the overlay node 100 and the like. The allowable additional connection number NA can be estimated based on a parameter such as the remaining resource amount of the overlay node 100. The additional connection allowable number NA and the parameters used for estimating the additional connection allowable number NA are collectively referred to as “capacity”. That is, it can be said that the capacity is a parameter corresponding to the additional connection allowable number NA. In the present embodiment, the concept of capacity is used for the overlay node 100.

  Next, an overview of the processing according to the present embodiment will be described with reference to FIG.

  FIG. 4 shows the main structure of a multicast tree related to a certain multicast group. The multicast tree includes a base node (sender edge node 100-SE or rendezvous node 100-RP), a first overlay node 100-1, a second overlay node 100-2, and an end node 200. The second overlay node 100-2 is located downstream from the first overlay node 100-1. That is, the first overlay node 100-1 is closer to the base node than the second overlay node 100-2. The upstream first overlay node 100-1 and the downstream second overlay node 100-2 do not have to be adjacent to each other.

  The end node 200 may be a sender end node or a receiver end node. The end node 200 is connected to the second overlay node 100-2 before the process according to the present embodiment (end node reconnection) is executed. That is, the second overlay node 100-2 is an edge node of the end node 200. According to the present embodiment, the following processing is executed.

  (1) The first overlay node 100-1 calculates the capacity of the own node (first overlay node 100-1).

  (2) The first overlay node 100-1 generates a “capacity notification message CMSG” indicating the capacity and address of the own node (first overlay node 100-1). Then, the first overlay node 100-1 transmits the capacity notification message CMSG in the downstream direction.

  (3) The second overlay node 100-2 receives the capacity notification message CMSG from the upstream side. The received capacity notification message CMSG indicates the capacity (notification capacity) and address (upstream node address) of the upstream first overlay node 100-1.

  (4) The second overlay node 100-2 receives the notification capacity indicated by the received capacity notification message CMSG and the state of the local end node 200 currently connected to the own node (second overlay node 100-2). And collate. Then, the second overlay node 100-2 selects from the local end node 200 the end node 200 within the allowable additional connection number NA related to the first overlay node 100-1.

  (5) The second overlay node 100-2 instructs the selected local end node 200 to “reconnect” to the first overlay node 100-1 on the more upstream side. More specifically, the second overlay node 100-2 transmits a “reconnection instruction message RMSG” to the selected local end node 200. The reconnection instruction message RMSG indicates the upstream node address included in the capacity notification message CMSG, that is, the address of the first overlay node 100-1.

  (6) The selected end node 200 receives the reconnection instruction message RMSG. The end node 200 transmits a “reconnection request RREQ” to the first overlay node 100-1 designated by the received reconnection instruction message RMSG.

  (7) The first overlay node 100-1 receives the reconnection request RREQ from the downstream end node 200 that is not the local end node. When the capacity is insufficient due to reasons such as having already accepted a request from another end node 200, the first overlay node 100-1 rejects the reconnection request RREQ. If the new local end node can be connected, the first overlay node 100-1 accepts the reconnection request RREQ.

  (8) When the reconnection request RREQ is accepted, the end node 200 transmits a request to join the multicast group to the first overlay node 100-1. As a result, the end node 200 reconnects to the first overlay node 100-1, and uses the first overlay node 100-1 as a new edge node instead of the second overlay node 100-2. That is, the edge node (connection destination) of the end node 200 is changed from the second overlay node 100-2 far from the base node (100-SE, 100-RP) to the first overlay node 100-1 closer to the base node. The Note that the end node 200 may transmit a withdrawal request to the second overlay node 100-2 that is the original edge node.

  As described above, the end node reconnection processing according to the present embodiment causes the edge node of the end node 200 to be closer to the base node from the second overlay node 100-2 far from the base node. It is changed to 100-1. As a result, the number of hops between end nodes on the overlay network is reduced. Therefore, in the overlay multicast, the transfer delay of multicast traffic between end nodes is shortened.

  Further, in the present embodiment, the local end node 200 to be reconnected is selected within the range of the allowable additional connection number NA of the first overlay node 100-1 on the upstream side. If a large number of new end nodes are unnecessarily connected to the first overlay node 100-1, the load on the first overlay node 100-1 is extremely increased, resulting in a problem that the transfer delay deteriorates. Can do. According to the present embodiment, such a problem does not occur.

  Furthermore, in this embodiment, only the connection destination (edge node) of the end node 200 is changed. There is no need to change the topology of the overlay network or multicast tree. That is, it is possible to shorten the multicast traffic transfer delay without changing the topology. It is not necessary to reconstruct the overlay network routing table and multicast routing table in accordance with the topology change.

1. 1. First embodiment 1-1. Overlay node 100
FIG. 5 is a block diagram illustrating a configuration of the overlay node 100 according to the first embodiment. The overlay node 100 includes a storage unit 110, a communication unit 120, a participation request transfer unit 130, a traffic transfer unit 140, an end node management unit 150, a capacity management unit 160, and a reconnection management unit 170. Hereinafter, the function of each part will be described in detail.

(Storage unit 110)
The storage unit 110 is a storage device including a RAM and an HDD. The storage unit 110 stores various types of information necessary for processing according to the present embodiment. For example, the storage unit 110 stores a multicast routing table RTN, traffic information TFC, and end node management information END, which will be described later.

(Communication unit 120)
The communication unit 120 establishes a virtual link to other adjacent overlay nodes 100 on the overlay network, and communicates with these adjacent nodes. Each unit described below receives information from the outside through the communication unit 120 and transmits information to the outside.

(Participation request transfer unit 130)
The participation request transfer unit 130 transfers a request to join a multicast group and a request to leave the multicast group. Further, the participation request transfer unit 130 updates the multicast routing table RTN stored in the storage unit 110 (entry registration / deletion).

  Specifically, the participation request transfer unit 130 receives a participation request or a withdrawal request from the next hop node (that is, the local end node 200 or another overlay node 100). The participation request and withdrawal request describe the ID of the multicast group and the address of the next hop node (next hop address). When the participation request is received, the participation request transfer unit 130 registers the multicast group ID and the next hop address as new entries in the multicast routing table RTN. When receiving the withdrawal request, the participation request transfer unit 130 deletes the entry indicating the next hop address of the multicast group ID from the multicast routing table RTN. Thereafter, the participation request transfer unit 130 transmits a participation request or a withdrawal request in which the address of the own node is described to the previous hop node. Note that if the own node is a base node (sender edge node 100-SE or rendezvous node 100-RP), forwarding is not performed.

  FIG. 6 shows an example of the multicast routing table RTN. In the multicast routing table RTN, a multicast group ID and a next hop address (that is, a node to which multicast traffic is transferred) are registered. For example, when the overlay node 100 receives multicast traffic addressed to the multicast group Group-A, the multicast traffic is transferred to the overlay nodes 100-10 and 100-15 and the local end nodes 200-1 and 200-2.

(Traffic forwarding unit 140)
When the traffic forwarding unit 140 receives multicast traffic from another node, the traffic forwarding unit 140 refers to the multicast routing table RTN and forwards the multicast traffic. The traffic transfer unit 140 generates / updates the traffic information TFC based on the multicast traffic transfer process. The traffic information TFC is information indicating the state of multicast traffic processed by the own node, and is stored in the storage unit 110.

  FIG. 7 shows an example of the state of multicast traffic being processed by the overlay node 100-B. It is assumed that the overlay node 100-B is connected to the multicast trees of the two multicast groups X and Y. In FIG. 7, the virtual link and communication regarding the multicast group X are indicated by solid lines, and the virtual link and communication regarding the multicast group Y are indicated by broken lines. Overlay nodes 100-A, 100-C, 100-P, 100-Q, and end nodes (local end nodes) 200-a to 200-c are connected to the overlay node 100-B. The end node 200-b is a sender end node, and the end nodes 200-a and 200-c are receiver end nodes.

  FIG. 8 shows an example of the traffic information TFC included in the overlay node 100-B shown in FIG. The traffic information TFC indicates a traffic ID, reception / transmission, and average traffic volume. In FIG. 8, traffic ID: TR_ [M]-[N] [L] means multicast traffic of the multicast group [M] flowing from the node [N] to the node [L].

(End node management unit 150)
The end node management unit 150 manages the state of the end node 200. The end node management unit 150 includes a local end node monitoring unit 151.

(Local end node monitoring unit 151)
The local end node monitoring unit 151 monitors the state of the local end node 200 connected to the local node. Here, the state of the local end node includes the number of local end nodes 200, the amount of traffic transmitted to the local end node 200, the amount of traffic received from the local end node 200, and the like. In the case of the example shown in FIGS. 7 and 8, “the number of local end nodes = 3, the amount of traffic sent to 200-a = 10 Mbps, the amount of traffic received from 200-b = 5 Mbps, the traffic sent to 200-c” Amount = 5 Mbps ". The local end node monitoring unit 151 describes the state of these local end nodes in the end node management information END stored in the storage unit 110.

(Capacity management unit 160)
The capacity management unit 160 calculates the capacity of the own node and transmits a capacity notification message CMSG to the next hop node. More specifically, the capacity management unit 160 includes a capacity calculation unit 161, a capacity distribution unit 162, and a notification message generation unit 163.

(Capacity calculation unit 161)
The capacity calculation unit 161 calculates (estimates) the capacity of the own node. Specifically, the capacity calculation unit 161 calculates the resource remaining amount of the own node. Further, when possible, the capacity calculation unit 161 may further calculate the allowable additional connection number NA from the resource remaining amount. The capacity includes the remaining resource amount and / or the additional connection allowable number NA.

<Calculation of remaining resource amount>
Examples of resources include traffic reception / transmission capability, CPU usage rate, and memory usage. For example, in the case of the traffic reception / transmission capability, the capacity calculation unit 161 can calculate the remaining amount of the traffic reception / transmission capability by referring to the above-described traffic information TFC. Hereinafter, the remaining amount of traffic reception / transmission capability in the case of the example shown in FIGS. 7 and 8 will be described.

  As shown in FIG. 8, the average received traffic amount of the overlay node 100-B is 15 Mbps (TR_X-AB + TR_X-bB) for the multicast group X, and 5 Mbps (TR_Y-PB) for the multicast group Y, for a total of 20 Mbps. It is. The average transmission traffic amount of the overlay node 100-B is 25 Mbps (TR_X-BA + TR_X-BC + TR_X-Ba) for the multicast group X and 10 Mbps (TR_Y-BQ + TR_Y-Bc) for the multicast group Y, which is 35 Mbps in total. . Here, it is assumed that the overlay node 100-B is connected to a link having a bandwidth of 100 Mbps full duplex. In this case, the traffic reception capability and traffic transmission capability remaining in the overlay node 100-B are 80 Mbps and 65 Mbps, respectively. These are the resource residual amount (reception / transmission traffic residual amount) of the overlay node 100-B.

<Calculation of additional connection allowable number NA>
In order to calculate the additional connection allowable number NA, it is necessary to know how much the capacity consumption (that is, the resource usage) increases due to the additional connection of the local end node 200. For example, when considering the traffic reception / transmission capability as a resource, it is sufficient to know how much the reception / transmission traffic amount is increased by the additional connection of the local end node 200. The reception / transmission traffic amount (capacity consumption amount) of each local end node 200 that is already connected is described in the above-mentioned end node management information END. Therefore, it is possible to calculate (estimate) the allowable additional connection number NA by referring to the end node management information END.

  In the example shown in FIG. 7 and FIG. 8, the amount of traffic to be sent to the receiver end node 200-a of the multicast group X is 10 Mbps. The amount of traffic received from the sender end node 200-b of the multicast group X is 5 Mbps. The amount of traffic sent to the receiver end node 200-c of the multicast group Y is 5 Mbps. These parameters indicated by the end node management information END are the capacity consumption of each local end node 200.

  The additional connection allowable number NA related to the receiver end node is as follows. In the case of multicast group X, the amount of traffic sent to receiver end node 200-a is 10 Mbps, and in the case of multicast group Y, the amount of traffic sent to receiver end node 200-c is 5 Mbps. Further, the traffic transmission capability remaining in the overlay node 100-B is 65 Mbps. Accordingly, in the case of the multicast group X, the allowable additional connection number NA is six, and in the case of the multicast group Y, the additional connection allowable number NA is 13.

  The calculation of the additional connection allowable number NA related to the sender end node is more complicated. This is because when the sender end node is additionally connected, the overlay node 100 not only receives traffic from the sender end node but also further transmits the received traffic to the adjacent node. That is, when the sender end node is additionally connected, not only the received traffic volume but also the outgoing traffic volume increases.

  In the example shown in FIGS. 7 and 8, the amount of traffic received from the sender end node 200-b of the multicast group X is 5 Mbps. Also, upon receiving traffic of multicast group X, overlay node 100-B forwards the traffic to three nodes 100-A, 100-C, and 200-a (traffic ID = TR_X-BA, TR_X-BC). , TR_X-Ba). That is, when one additional sender end node is connected, the received traffic volume of the overlay node 100-B increases by 5 Mbps, and the outgoing traffic volume increases by 15 Mbps (= 5 Mbps × 3). Since the traffic reception capability and traffic transmission capability remaining in the overlay node 100-B are 80 Mbps and 65 Mbps, respectively, the additional connection allowable number NA of the sender end node is four.

  Thus, in order to calculate the additional connection allowable number NA related to the sender end node, it is necessary to know the number of transfer destinations of received traffic in addition to the traffic amount transmitted by the sender end node. These parameters used for calculating the allowable additional connection number NA are also included in the “capacity”. It should be noted that all sender end nodes may be managed by a server or the like, and the amount of outgoing traffic of the sender end node to be additionally connected by inquiring to the server or the like may be grasped.

(Capacity apportioning part 162)
The capacity apportioning unit 162 divides (apportions) the capacity as necessary. As a case where division is necessary, there are a case where the own node participates in a plurality of multicast groups, and a case where there are a plurality of next hop nodes of the same multicast group.

<When the local node participates in multiple multicast groups>
For example, in the example shown in FIGS. 7 and 8, the overlay node 100-B participates in two multicast groups X and Y. The remaining amount of outgoing traffic is 65 Mbps. In this case, for example, the capacity apportioning unit 162 allocates 45 Mbps (equivalent to NA = 4) to the multicast group X and allocates 20 Mbps (equivalent to NA = 4) to the multicast group Y. However, the division ratio is arbitrary.

<When there are multiple next hop nodes in the same multicast group>
This case is equivalent when a plurality of next hop addresses are registered for the same multicast group ID in the multicast routing table RTN (see FIG. 6). In this case, the capacity apportioning unit 162 divides the capacity allocated to the multicast group among the plurality of next hop nodes. For example, the capacity apportioning unit 162 divides the capacity equally among a plurality of next hop nodes. However, the division ratio is arbitrary.

(Notification message generator 163)
The notification message generation unit 163 generates a capacity notification message CMSG. The capacity notification message CMSG indicates the own node capacity and the address of the own node (connection information to the own node) regarding the corresponding multicast group. When the capacity is divided among the multicast groups, a capacity notification message CMSG is created for each multicast group. When the capacity is divided between the next hop nodes, a capacity notification message CMSG is created for each next hop node.

  The notification message generator 163 refers to the multicast routing table RTN and transmits a capacity notification message CMSG to the next hop node. When a plurality of capacity notification messages CMSG are created by dividing the capacity, the notification message generating unit 163 transmits each of the plurality of capacity notification messages CMSG to the corresponding next hop node. In the following description, a capacity notification message CMSG transmitted downstream from a certain overlay node 100 may be referred to as a “capacity notification message CMSG-DN”.

(Reconnection manager 170)
The overlay node 100 may be in a position to receive the capacity notification message CMSG transmitted from the previous hop node. In the following description, a capacity notification message CMSG received by an overlay node 100 from upstream may be referred to as a “capacity notification message CMSG-UP”.

  The reconnection manager 170 processes the capacity notification message CMSG-UP. The reconnection management unit 170 includes an end node selection unit 171 and an instruction unit 172. In response to the capacity notification message CMSG-UP, the reconnection management unit 170 performs “reconnection instruction processing” described below.

(End node selection unit 171)
The end node selection unit 171 selects a reconnection instruction target from the local end nodes 200 currently connected to the own node. In this selection process, the end node selection unit 171 refers to the capacity (notification capacity) of the upstream node indicated by the capacity notification message CMSG-UP. Then, the end node selection unit 171 selects the local end node 200 such that the total capacity consumption of the selected local end node 200 is equal to or less than the notification capacity. That is, the end node selection unit 171 selects the local end node 200 within the additional connection allowable number NA related to the upstream node.

  For example, consider the case where the notification capacity is the resource residual amount (for example, the reception / transmission traffic residual amount) of the upstream node. In this case, the end node selection unit 171 refers to the above-described end node management information END and grasps the resource usage amount (for example, reception / transmission traffic amount) of each local end node 200. Then, the end node selection unit 171 selects the local end node 200 so that the total resource usage amount of the selected local end node 200 is equal to or less than the resource remaining amount. This corresponds to selecting the local end node 200 within the allowable additional connection number NA obtained by the method described in the above <Calculation of allowable additional connection number NA>.

  When the notification capacity is the additional connection allowable number NA of the upstream node itself, the end node selection unit 171 can immediately select the local end node 200 within the additional connection allowable number NA. In this case, the total number of selected local end nodes 200 corresponds to the total capacity consumption.

(Instruction unit 172)
The instruction unit 172 instructs the local end node 200 selected by the end node selection unit 171 to “reconnect to the upstream node”. More specifically, the instruction unit 172 transmits a reconnection instruction message RMSG to the selected local end node 200. The reconnection instruction message RMSG indicates an address (upstream node address) and a multicast group included in the capacity notification message CMSG-UP.

1-2. End node 200
FIG. 9 is a block diagram showing a configuration of end node 200 according to the present embodiment. The end node 200 includes a participation request transmission unit 210, a traffic transmission / reception unit 220, and a reconnection processing unit 230.

  The participation request transmission unit 210 creates a request to join the multicast group or a request to leave the multicast group. Then, the participation request transmission unit 210 transmits a participation request or withdrawal request to the designated overlay node 100 (edge node or upstream node designated by the reconnection instruction message RMSG).

  The traffic transmission / reception unit 220 transmits multicast traffic addressed to a specific multicast group to the edge node 100. The traffic transmission / reception unit 220 receives multicast traffic from a specific multicast group from the edge node 100.

  The reconnection processing unit 230 receives the above-described reconnection instruction message RMSG from the current edge node. The reconnection instruction message RMSG includes an upstream node address designating the upstream node. The reconnection processing unit 230 refers to the upstream node address and transmits a reconnection request RREQ to the upstream node. When the upstream node accepts the reconnection request RREQ, the reconnection processing unit 230 instructs the participation request transmission unit 210 to transmit a participation request to the corresponding multicast group to the upstream node. As a result, the edge node is changed to an upstream node closer to the base node. At this time, a withdrawal request may be transmitted to the original edge node.

1-3. Operation Example Next, an operation example of the overlay multicast system according to the present embodiment will be described with reference to FIGS. 10 and 11. 10 and 11 show a part of a multicast tree of a certain multicast group. The overlay node 100-A is a previous hop node of the overlay node 100-B. Both overlay nodes 100-C and 100-E are next hop nodes of overlay node 100-B. The overlay node 100-D is the next hop node of the overlay node 100-C. End nodes 200-Bx, 200-By, and 200-Bz are connected to the overlay node 100-B. An end node 200-Cx is connected to the overlay node 100-C. An end node 200-Ex is connected to the overlay node 100-E.

  Hereinafter, the case where the overlay node 100-B receives the capacity notification message CMSG-UP and the case where the overlay node 100-B transmits the capacity notification message CMSG-DN will be described separately. In the following description, all end nodes 200 are receiver end nodes.

1-3-1. Operation Upon Receiving Capacity Notification Message As shown in FIG. 10, the overlay node 100-B receives the capacity notification message CMSG-UP from the overlay node 100-A. The capacity notification message CMSG-UP indicates the capacity and address of the overlay node 100-A. The reconnection management unit 170 refers to the notification capacity and selects a reconnection instruction target from the local end nodes 200-Bx, 200-By, and 200-Bz.

  As an example, let us consider a case where the capacity notification message CMSG-UP indicates “additional allowable connection number NA = 2 for the receiver end node”. In this case, the reconnection manager 170 selects up to two local end nodes 200 as targets. The target may be arbitrarily selected or may be selected according to a predetermined policy. For example, there may be a policy of preferentially selecting from those that have been connected to the overlay node 100-B for a long time, or preferentially selecting from those having a large traffic transmission amount from the overlay node 100-B. . Such a policy may be set in the reconnection management unit 170 in advance, or may be described in the capacity notification message CMSG-UP.

  As another example, consider a case where the capacity notification message CMSG-UP indicates “transmission remaining traffic amount (resource remaining amount) of overlay node 100-A = 60 Mbps”. Further, it is assumed that the traffic volume (resource usage amount) to each of the local end nodes 200-Bx, 200-By, and 200-Bz is 20 Mbps, 30 Mbps, and 30 Mbps. In this case, the reconnection management unit 170 selects the local end node 200 so that the total resource usage is 60 Mbps or less. For example, two local end nodes 200-By and 200-Bz are selected. As described above, the target may be arbitrarily selected or may be selected according to a predetermined policy.

  Furthermore, the reconnection management unit 170 transmits a reconnection instruction message RMSG to the selected local end node 200. The reconnection instruction message RMSG indicates the address (upstream node address) of the overlay node 100-A.

  For example, the end node 200-By receives the reconnection instruction message RMSG. The end node 200-By transmits a reconnection request RREQ to the overlay node 100-A. The overlay node 100-A accepts the reconnection request RREQ. Then, the end node 200-By transmits a withdrawal request to the overlay node 100-B, and transmits a participation request to the overlay node 100-A. As a result, the end node 200-By reconnects to the overlay node 100-A, and uses the overlay node 100-A as a new edge node instead of the overlay node 100-B. That is, the edge node (connection destination) of the end node 200-By is changed from the overlay node 100-B far from the base node to the overlay node 100-A closer to the base node.

1-3-2. Operation when Capacity Notification Message is Transmitted A case where the overlay node 100-B transmits a capacity notification message CMSG-DN will be described with reference to FIG. The capacity management unit 160 of the overlay node 100-B acquires the capacity of the own node. The timing for acquiring the capacity may be (1) when a certain time has elapsed since the previous capacity acquisition, or (2) when the reconnection process shown in FIG. 10 is completed.

  Furthermore, the capacity management unit 160 refers to the multicast routing table RTN and recognizes that there are two next hop nodes 100-C and 100-E. In this case, the capacity management unit 160 divides the acquired capacity between the two next hop nodes 100-C and 100-E.

  The capacity management unit 160 creates two types of capacity notification messages CMSG-DN-C and CMSG-DN-E. The capacity notification message CMSG-DN-C indicates the capacity allocated to the next hop node 100-C and the address of the overlay node 100-B. On the other hand, the capacity notification message CMSG-DN-E indicates the capacity allocated to the next hop node 100-E and the address of the overlay node 100-B. Then, the capacity management unit 160 refers to the multicast routing table RTN and transmits capacity notification messages CMSG-DN-C and CMSG-DN-E to the overlay nodes 100-C and 100-E, respectively.

  The overlay node 100-C transmits a reconnection instruction message RMSG to the end node 200-Cx, and the end node 200-Cx transmits a reconnection request RREQ to the overlay node 100-B. The overlay node 100-B accepts the reconnection request RREQ from the end node 200-Cx. The end node 200-Cx transmits a participation request to the overlay node 100-B. The participation request transfer unit 130 of the overlay node 100-B updates the multicast routing table RTN (adds the end node 200-Cx to the entry), and transfers the participation request to the overlay node 100-A. Thereafter, when the overlay node 100-B receives the multicast traffic addressed to the multicast group, the traffic transfer unit 140 transfers the multicast traffic to at least the end node 200-Cx.

  The overlay node 100-E transmits a reconnection instruction message RMSG to the end node 200-Ex, and the end node 200-Ex transmits a reconnection request RREQ to the overlay node 100-B. At this time, it is assumed that the overlay node 100-B rejects the reconnection request RREQ from the end node 200-Ex due to insufficient capacity. In this case, reconnection of the end node 200-Ex is not performed.

1-4. Effect As described above, according to the present embodiment, the edge node of the end node 200 is changed to the overlay node 100 closer to the base node. As a result, the number of hops between end nodes on the overlay network is reduced. Therefore, in the overlay multicast, the transfer delay of multicast traffic between end nodes is shortened.

  Further, in the present embodiment, the local end node 200 that is the reconnection instruction target is selected within the range of the additional connection allowable number NA of the upstream node 100. If a large number of new end nodes are unnecessarily connected to the upstream node 100, the load on the upstream node 100 may increase extremely and the transfer delay may be worsened. According to the present embodiment, such a problem does not occur.

  Furthermore, in this embodiment, only the connection destination (edge node) of the end node 200 is changed. There is no need to change the topology of the overlay network or multicast tree. That is, it is possible to shorten the multicast traffic transfer delay without changing the topology. It is not necessary to reconstruct the overlay network routing table and multicast routing table in accordance with the topology change.

2. Second Embodiment In the first embodiment, only the capacity of the adjacent previous hop node is described in the capacity notification message CMSG-UP received from upstream. Therefore, the reconnection destination candidate of the local end node 200 is only the previous hop node. In this case, in order to reconnect the local end node 200 to the overlay node 100 upstream of two or more hops, it is necessary to repeat the reconnection process for the number of hops.

  In the second embodiment, not only the capacity of the own node but also the capacity of the overlay node 100 upstream from the own node is described in the capacity notification message CMSG-DN sent downstream. As a result, the reconnection destination candidate of the local end node 200 is extended not only to the previous hop node but also to the overlay node 100 further upstream than the previous hop node. In this case, the local end node 200 can be easily reconnected to the overlay node 100 closer to the base node. Further, it is not necessary to repeat the reconnection process for that purpose, so that the processing time is shortened.

  FIG. 12 is a block diagram illustrating a configuration of the overlay node 100 according to the second embodiment. Compared to the first embodiment, the reconnection management unit 170 according to the present embodiment further includes an upstream capacity recalculation unit 173. The description overlapping with the first embodiment is omitted as appropriate.

(Upstream capacity recalculation unit 173)
Similar to the first embodiment, the reconnection management unit 170 (the end node selection unit 171 and the instruction unit 172) executes the reconnection instruction process in response to the capacity notification message CMSG-UP received from the upstream. . After the reconnection instruction process, there is a possibility that the capacity of the upstream node is still sufficient. Therefore, the upstream capacity recalculation unit 173 recalculates the capacity of the upstream node after the reconnection instruction process.

  The capacity (notification capacity) of the upstream node indicated by the capacity notification message CMSG-UP is set to Cup. Further, the total capacity consumption of the local end node 200 selected by the end node selection unit 171 is defined as Cc. At this time, the upstream capacity recalculation unit 173 calculates the residual capacity Cup ′ = Cup−Cc. The capacity recalculation unit 173 then sends the remaining capacity notification message CMSG-UP ′ indicating the remaining capacity Cup ′ and the upstream node address (the address indicated by the capacity notification message CMSG-UP) to the capacity management unit. 160.

  For example, in the example shown in FIG. 10, the capacity notification message CMSG-UP received by the overlay node 100-B indicates “transmission remaining traffic amount of overlay node 100-A = 60 Mbps”. Here, it is assumed that the reconnection management unit 170 instructs the local end node 200-By (reception traffic volume = 30 Mbps) to reconnect to the overlay node 100-A. In this case, the upstream capacity recalculation unit 173 calculates the residual capacity Cup ′ as 30 Mbps, and sends a residual capacity notification message CMSG-UP ′ indicating “transmission remaining traffic amount of overlay node 100-A = 30 Mbps”. The data is sent to the capacity management unit 160.

(Capacity management unit 160)
The capacity management unit 160 incorporates the remaining capacity notification message CMSG-UP ′ into the capacity notification message CMSG-DN. That is, the capacity notification message CMSG-DN sent downstream includes the remaining capacity and upstream node address of the upstream node in addition to the capacity and address of the own node. Note that the capacity apportioning unit 162 may divide the capacities of the own node and the upstream node as in the first embodiment.

(Reconnection manager 170)
The reconnection management unit 170 receives the capacity notification message CMSG-UP from upstream. The capacity notification message CMSG-UP may indicate the capacity and address of each of the plurality of upstream nodes. That is, there may be a plurality of reconnection destination candidates for the local end node 200. In that case, the end node selection unit 171 also selects a candidate for reconnecting the local end node 200.

  As an example, let us consider a case in which the transmission traffic residual amount of the overlay node 100-A is 60 Mbps, and the transmission traffic residual amount of the overlay node 100-X upstream of the overlay node 100-A is 30 Mbps. In this case, for example, the reconnection management unit 170 instructs the local end node 200-By (reception traffic amount = 30 Mbps) to reconnect to the overlay node 100-X, and the local end node 200-Bz (reception traffic). (Amount = 30 Mbps) is instructed to reconnect to the overlay node 100-A. Thereafter, the upstream capacity recalculation unit 173 recalculates the capacity of the upstream node.

  Note that the end node selection unit 171 may randomly select a reconnection destination candidate, or may preferentially select a candidate having a large capacity. Alternatively, the end node selection unit 171 may select a reconnection destination candidate that is closer to the base node. This can be realized by each overlay node 100 describing the number of hops from the base node of its own node in the capacity notification message CMSG-DN. The number of hops from the base node can be grasped as follows, for example. When the base node transmits data to the multicast tree, a field for recording the number of transfers is provided in the data. Each overlay node 100 increases the value of the field by 1 at the time of data transfer. Each overlay node 100 can grasp the number of hops from the base node by referring to the field of the received data.

  According to the present embodiment, the same effect as in the first embodiment can be obtained. Furthermore, it becomes easy to reconnect the end node 200 to the overlay node 100 closer to the base node. In addition, the processing time required to reconnect the end node 200 to the overlay node 100 closer to the base node is shortened.

3. Third Embodiment In the example shown in FIG. 11, the overlay node 100-B is located at the branch point of the multicast tree and has two next-hop nodes 100-C and 100-E. . In this case, the overlay node 100-B divides the capacity by the two next hop nodes 100-C and 100-E, and creates two capacity notification messages CMSG-DN-C and CMSG-DN-E. Here, the capacity division ratio may be arbitrary. However, if the overlay node 100-B recognizes the state of each branch destination end node 200, it is more appropriate for each branch destination. A large amount of capacity can be distributed. Therefore, in the third embodiment, capacity division is performed in consideration of the state (number and resource usage) of the end node 200 beyond the next hop.

  FIG. 13 is a block diagram illustrating a configuration of the overlay node 100 according to the third embodiment. Compared to the first embodiment, the end node management unit 150 according to the present embodiment further includes a notification message processing unit 152. The description overlapping with the first embodiment is omitted as appropriate.

(Notification message processing unit 152)
As described above, the local end node monitoring unit 151 monitors the state of the local end node 200 connected to the local node, and describes the state of the local end node 200 in the end node management information END. The state of the local end node 200 includes the number of local end nodes 200 and capacity consumption (transmission / reception traffic amount, etc.).

  The notification message processing unit 152 creates an “end node state notification message EMSG” indicating information described in the end node management information END. Then, the notification message processing unit 152 transmits an end node state notification message EMSG to the previous hop node. An end node state notification message EMSG transmitted upstream from a certain overlay node 100 may be referred to as an “end node state notification message EMSG-UP”.

  Further, the notification message processing unit 152 receives the end node state notification message EMSG transmitted from the next hop node. The end node state notification message EMSG received from the downstream side may be referred to as an “end node state notification message EMSG-DN”. Upon receiving the end node state notification message EMSG-DN, the notification message processing unit 152 adds information included in the end node state notification message EMSG-DN to the end node management information END. As a result, in the end node management information END, not only the local end node connected to the own node but also the state of the end node (remote end node) connected to the downstream node is described. Note that such updating of the end node management information END may be performed only by the overlay node 100 located at the branch point.

  Thereafter, the notification message processing unit 152 updates the end node state notification message EMSG and transmits it to the upstream hop node further upstream. That is, when receiving the end node state notification message EMSG-DN from the next hop node, the notification message processing unit 152 adds the state of its own local end node 200 to the previous hop node as the end node state notification message EMSG-UP. Forward further to the node. In this way, the state of the end node 200 is cumulatively notified in the upstream direction.

  Next, an example of processing according to the present embodiment will be described with reference to FIGS. 14 and 15.

  FIG. 14 shows a part of a multicast tree of a certain multicast group. The overlay node 100-A is a previous hop node of the overlay node 100-B. Both overlay nodes 100-C and 100-E are next hop nodes of overlay node 100-B. The overlay node 100-D is the next hop node of the overlay node 100-C. The end node 200-A1 is a local end node of the overlay node 100-A. The end nodes 200-B1 and 200-B2 are local end nodes of the overlay node 100-B. The end nodes 200-C1, 200-C2, and 200-C3 are local end nodes of the overlay node 100-C. The end nodes 200-D1 and 200-D2 are local end nodes of the overlay node 100-D. The end node 200-E1 is a local end node of the overlay node 100-E. FIG. 15 shows the amount of traffic sent to each end node 200 and the amount of traffic received from each end node 200.

  For example, the following information is described in the end node state notification message EMSG-UP created by the overlay node 100-C in FIG.

<Example 1> State is described for each overlay node [Overlay node 100-C]
(A) Number of end nodes Transmission end node = 2 units, reception end node = 1 unit (B) Transmission traffic amount to each end node, reception traffic amount from each end node 200-C1: transmission = 10 Mbps, reception = 0Mbps
200-C2: Transmission = 0 Mbps, Reception = 15 Mbps
200-C3: transmission = 0 Mbps, reception = 20 Mbps
(C) Total traffic volume (sending and receiving)
Total outgoing traffic = 10 Mbps
Total received traffic = 35 Mbps
[Overlay node 100-D]
(A) Number of end nodes Transmission end node = 1 unit, reception end node = 1 unit (B) Transmission traffic amount to each end node, reception traffic amount from each end node 200-D1: transmission = 15 Mbps, reception = 0Mbps
200-D2: transmission = 0 Mbps, reception = 10 Mbps
(C) Total traffic volume (sending and receiving)
Total outgoing traffic = 15 Mbps
Total received traffic = 10 Mbps

<Example 2> Summed and described (A) Number of end nodes Transmission end node = 3 units, reception end node = 2 units (C) Total traffic volume (transmission and reception)
Total outgoing traffic = 25 Mbps
Total received traffic = 45 Mbps

Further, the following information is described in the end node state notification message EMSG-UP created by the overlay node 100-E in FIG.
[Overlay node 100-E]
(A) Number of end nodes Transmission end node = 1 unit, reception end node = 1 unit (B) Transmission traffic amount to each end node, reception traffic amount from each end node 200-E1: transmission = 10 Mbps, reception = 10Mbps
(C) Total traffic volume (sending and receiving)
Total outgoing traffic = 10 Mbps
Total received traffic = 10 Mbps

  The overlay node 100-B receives the end node state notification message EMSG-DN as described above from each of the two next hop nodes 100-C and 100-E. Then, the end node management unit 150 of the overlay node 100-B calculates the total capacity consumption beyond the next hop node with reference to the received end node state notification message EMSG-DN. The total capacity consumption beyond the next hop node is hereinafter referred to as “subsequent capacity consumption”. The end node management unit 150 calculates the subsequent capacity consumption for each next hop node, and records the calculation result in the end node management information END. In this example, the subsequent capacity consumption for each of the next hop nodes 100-C and 100-E is as follows.

[Next hop node 100-C]
Subsequent capacity consumption: transmission = 25 Mbps, reception = 45 Mbps
[Next hop node 100-E]
Subsequent capacity consumption: sending = 10 Mbps, receiving = 10 Mbps

  In this case, the creation of the capacity notification message CMSG-DN in the overlay node 100-B is as follows. The capacity management unit 160 (capacity apportioning unit 162) of the overlay node 100-B divides the capacity between the two next hop nodes 100-C and 100-E. At this time, the capacity management unit 160 refers to the end node management information END, and divides the capacity based on the subsequent capacity consumption regarding each next hop node. For example, the capacity management unit 160 sets the ratio of each subsequent capacity consumption as the capacity division ratio. As a result, an appropriate amount of capacity according to the subsequent capacity consumption is allocated to each next hop node.

  Alternatively, a capacity that eliminates an imbalance in which one next hop node is allocated excess capacity that exceeds the subsequent capacity consumption, while another next hop node is allocated capacity that is less than the subsequent capacity consumption. City splitting is also possible. Typically, such an imbalance may occur when the sum of subsequent capacity consumption of all next hop nodes exceeds the allocatable capacity. In that case, the capacity management unit 160 divides the capacity so that there is no next hop node in which the capacity division amount (allocation amount) exceeds the subsequent capacity consumption amount. This corresponds to eliminating unnecessary capacity allocation and reducing waste as much as possible. As a result, the aforementioned imbalance is improved.

  For example, in the example shown in FIG. 14 and FIG. 15, a case is considered where the transmission traffic residual amount of the overlay node 100-B is 30 Mbps. As described above, the subsequent capacity consumption (sending) for the next hop node 100-C is 25 Mbps, and the subsequent capacity consumption (sending) for the next hop node 100-E is 10 Mbps. Accordingly, a capacity of 25 Mbps or less is allocated to the next hop node 100-C side, and a capacity of 10 Mbps or less is allocated to the next hop node 100-E side.

  As a comparison, let us consider a case in which the transmission traffic residual amount of 30 Mbps is divided by the next hop nodes 100-C and 100-E. In this case, the next hop node 100-C can only be allocated a capacity less than the subsequent capacity consumption (= 25 Mbps), but the next hop node 100-E has a surplus exceeding the subsequent capacity consumption (= 10 Mbps). Capacity is allocated. This is inefficient. In this embodiment, such inefficiency is avoided.

  According to the present embodiment, the same effect as in the first embodiment can be obtained. Furthermore, a more appropriate amount of capacity can be distributed to each branch destination at the branch point of the multicast tree. Since inefficient capacity distribution is prevented, reconnection of end nodes is facilitated and preferable. It is also possible to combine the present embodiment and the second embodiment. In that case, the same effect as the second embodiment can be obtained.

4). Fourth Embodiment In the fourth embodiment, “priority” is given to each end node 200. Then, reconnection processing is performed preferentially from the end node 200 having a high priority.

  FIG. 16 is a block diagram illustrating a configuration of the overlay node 100 according to the fourth embodiment. Compared to the first embodiment, the end node management unit 150 further includes a notification message processing unit 152, and the reconnection management unit 170 further includes an upstream capacity recalculation unit 173. The description overlapping with the above-described embodiment is omitted as appropriate.

  The upstream capacity recalculation unit 173 is the same as that described in the second embodiment. That is, the upstream capacity recalculation unit 173 calculates the remaining capacity of the upstream node after the reconnection instruction process, and sends the remaining capacity notification message CMSG-UP ′ to the capacity management unit 160.

  The notification message processing unit 152 is the same as that described in the third embodiment, and processes the end node state notification message EMSG. However, in the present embodiment, the end node state notification message EMSG includes the “priority” of the end node 200 in addition to the number of end nodes 200 and the capacity consumption (transmission / reception traffic amount, etc.). . Further, the notification message processing unit 152 refers to the end node state notification message EMSG-DN, calculates the subsequent capacity consumption for each priority, and records the calculation result in the end node management information END.

  Next, an example of processing according to the present embodiment will be described with reference to FIGS.

  FIG. 17 shows a part of a multicast tree of a certain multicast group. In FIG. 17, overlay nodes 100-A, 100-B, 100-C, 100-D, and 100-E are connected in order from upstream to downstream. The end nodes 200-C1, 200-C2, and 200-C3 are local end nodes of the overlay node 100-C. The end nodes 200-D1, 200-D2, and 200-D3 are local end nodes of the overlay node 100-D. The end nodes 200-E1, 200-E2, and 200-E3 are local end nodes of the overlay node 100-E.

  FIG. 18 shows the amount of traffic sent to each end node 200 and the priority of each end node 200. As shown in FIG. 18, each of the end nodes 200 is assigned one of three levels of priority “1” to “3”. Here, the priority “1” is the highest and the priority “3” is the lowest.

  FIG. 19 shows the subsequent capacity consumption indicated by the end node management information END of the overlay node 100-C. The subsequent capacity consumption in the overlay node 100-C is the sum of the capacity consumption of all the end nodes 200 connected to the downstream overlay nodes 100-D and 100-E. As illustrated in FIG. 19, the notification message processing unit 152 of the overlay node 100-C calculates the subsequent capacity consumption for each priority.

  The reconnection instruction process is performed in the order of “priority”. Hereinafter, the reconnection instruction processing when the reconnection management unit 170 of the overlay node 100-C receives the capacity notification message CMSG-UP will be described.

  It is assumed that the capacity notification message CMSG-UP received by the overlay node 100-C indicates “transmission remaining traffic amount of overlay node 100-A = 30 Mbps, remaining transmission traffic amount of overlay node 100-B = 50 Mbps”. When receiving the capacity notification message CMSG-UP, the reconnection management unit 170 substitutes the respective remaining traffic volumes (capacities) for the temporary capacities TC-A and TC-B. As a result, TC-A = 30 Mbps and TC-B = 50 Mbps.

<Priority = 1>
First, a reconnection instruction process is performed for the highest priority “1”. The reconnection management unit 170 refers to the end node management information END, and adds up the capacity consumption (= 20 Mbps) and the subsequent capacity consumption (= 15 Mbps) of the local end node 200-C1 with the priority “1”. Calculate the value. Then, the reconnection management unit 170 subtracts the total value from the temporary capacity. For the end node 200 with the priority “1”, not only the local end node 200-C1 but also the capacity allocated to the remote end nodes 200-D1 and 200-E1 located beyond the next hop node is secured in advance. It is equivalent to keeping.

  When a plurality of temporary capacities are prepared, it is preferable to preferentially subtract the sum from the temporary capacity of the overlay node 100 farther from the own node (that is, the overlay node 100 closer to the base node). is there. In this example, since the overlay node 100-A is located on the upstream side, the total value (= 35 Mbps) is subtracted from the temporary capacity TC-A (= 30 Mbps). Here, since the temporary capacity TC-A is insufficient by 5 Mbps, the amount is subtracted from the next temporary capacity TC-B (= 50 Mbps). As a result, TC-A = -5 Mbps and TC-B = 45 Mbps.

  Thereafter, the reconnection management unit 170 executes the reconnection instruction process for the priority “1” by the same method as that of the above-described embodiment. That is, the reconnection management unit 170 selects the local end node 200-C1 having the priority “1”, and instructs the local end node 200-C1 to reconnect upstream. The reconnection destination is the overlay node 100-A that has been divided from the temporary capacity.

<Priority = 2>
The priority is lowered by one level and set to “2”. The reconnection management unit 170 refers to the end node management information END, and adds up the capacity consumption (= 10 Mbps) and the subsequent capacity consumption (= 15 Mbps) of the local end node 200-C2 with the priority “2”. Calculate the value. Since the temporary capacity TC-A has already been used up, the reconnection management unit 170 subtracts the total value (= 25 Mbps) from the temporary capacity TC-B. As a result, TC-A = -5 Mbps and TC-B = 20 Mbps. Thereafter, the reconnection management unit 170 selects the local end node 200-C2 having the priority “2”, and instructs the local end node 200-C2 to reconnect to the overlay node 100-B.

<Priority = 3>
The priority is dropped by one level and set to “3”. The reconnection management unit 170 refers to the end node management information END, and adds up the capacity consumption (= 10 Mbps) and the subsequent capacity consumption (= 15 Mbps) of the local end node 200-C3 with the priority “3”. Calculate the value. The reconnection management unit 170 subtracts the total value (= 25 Mbps) from the temporary capacity TC-B. As a result, TC-A = -5 Mbps and TC-B = -5 Mbps. Thereafter, the reconnection management unit 170 selects the local end node 200-C3 having the priority “3”, and instructs the local end node 200-C3 to reconnect to the overlay node 100-B.

  In this way, the local end node 200-C1 having the priority “1” is reconnected to the overlay node 100-A, and the local end nodes 200-C2 and C3 having the priorities “2” and “3” are reconnected to the overlay node 100. Reconnected to -B. That is, the end node 200 having a higher priority is reconnected to the overlay node 100 closer to the base node.

  After the reconnection instruction process, the upstream capacity recalculation unit 173 calculates the remaining capacity of the upstream node. In this example, the residual capacity of the overlay node 100-A is 10 Mbps (= 30 Mbps-20 Mbps), and the residual capacity of the overlay node 100-B is 30 Mbps (= 50 Mbps-10 Mbps-10 Mbps). Thus, the capacity of the overlay node 100-A still remains. Therefore, the capacity of the overlay node 100-A can be used in the reconnection instruction process in the next hop node 100-D. The upstream capacity recalculation unit 173 sends a residual capacity notification message CMSG-UP ′ indicating the residual capacity to the capacity management unit 160, and the capacity management unit 160 sends the capacity notification message CMSG-DN to the next hop. Transmit to node 100-D.

  As a result of the reconnection instruction processing in the overlay node 100-D, the local end node 200-D1 (10 Mbps) having the priority “1” is reconnected to the overlay node 100-A that still has a margin. This is because the capacity allocated to the end node 200-D1 having a high priority is secured in advance in the preceding process. Thus, according to the present embodiment, it is possible to reconnect the end node 200 having a high priority to the upstream side preferentially.

  According to the present embodiment, the same effect as the above-described embodiment can be obtained. Furthermore, by assigning a priority to each end node 200, it becomes possible to reconnect the desired end node 200 preferentially to the upstream side.

  The embodiments of the present invention have been described above with reference to the accompanying drawings. However, the present invention is not limited to the above-described embodiments, and can be appropriately changed by those skilled in the art without departing from the scope of the invention.

100 overlay node 100-SE sender edge node 100-RP rendezvous node 110 storage unit 120 communication unit 130 participation request transfer unit 140 traffic transfer unit 150 end node management unit 151 local end node monitoring unit 152 notification message processing unit 160 capacity management Unit 161 capacity calculation unit 162 capacity apportioning unit 163 notification message generation unit 170 reconnection management unit 171 end node selection unit 172 instruction unit 173 upstream capacity recalculation unit 200 end node 200-S sender end node 210 participation request transmission Unit 220 traffic transmission / reception unit 230 reconnection processing unit RTN multicast routing table TFC traffic information END end node management information CMSG capacity notification Message RMSG reconnection instruction message RREQ reconnection request EMSG end node status notification message

Claims (10)

An overlay node constituting an overlay network,
A multicast tree is constructed on the overlay network,
In the overlay network, a transfer direction of a request to join a multicast group is defined as an upstream direction, and a reverse direction of the upstream direction is defined as a downstream direction,
In the multicast tree, a node adjacent to the downstream side is a next hop node, a node adjacent to the upstream side is a previous hop node,
The capacity of an overlay node is a parameter corresponding to the allowable number of end nodes that can be additionally connected to the overlay node,
The overlay node is
A capacity management unit that calculates the capacity of the own node and transmits a capacity notification message indicating the capacity and address of the own node to the next hop node;
A reconnection management unit for performing reconnection instruction processing in response to the capacity notification message received from the upstream side,
The capacity and the address indicated in the capacity notification message received from the upstream side are the notification capacity and the upstream node address, respectively.
In the reconnection instruction process,
The reconnection manager refers to the notification capacity, selects an end node within the allowable number from local end nodes currently connected to the own node, and
The reconnection management unit instructs the selected end node to reconnect to an upstream node that is an overlay node specified by the upstream node address. The overlay node according to claim 1, comprising:
After the reconnection instruction process, the reconnection management unit recalculates the capacity of the upstream node,
The capacity notification message transmitted by the capacity management unit indicates the capacity and the upstream node address of the upstream node in addition to the capacity and the address of the own node. The overlay node according to claim 1 or 2, wherein
When there are a plurality of the next hop nodes, the capacity management unit divides the capacity among the plurality of next hop nodes, and transmits the capacity notification message for each of the plurality of next hop nodes. . An overlay node according to any one of claims 1 to 3,
An end node management unit;
The capacity consumption of a certain end node is the amount of the capacity consumed by communication with the certain end node,
The end node management unit monitors the capacity consumption of the local end node,
The reconnection management unit selects an end node within the allowable number based on the notification capacity and the calculated capacity consumption overlay node. The overlay node according to claim 4, wherein
The end node management unit transmits an end node state notification message indicating the capacity consumption of the local end node to the previous hop node;
When receiving the end node status notification message from the downstream side, the end node management unit adds the capacity consumption of the local end node to the end node status notification message, and then transmits the end node status notification message. An overlay node that forwards to the previous hop node. The overlay node according to claim 5, comprising:
The sum of the capacity consumption of all end nodes connected to the overlay node beyond the next hop node is the subsequent capacity consumption.
When there are a plurality of the next hop nodes, the end node management unit calculates the subsequent capacity consumption for each of the plurality of next hop nodes with reference to the end node state notification message received from the downstream side. ,
Further, the capacity management unit divides the capacity among the plurality of next hop nodes based on the subsequent capacity consumption of the plurality of next hop nodes, and the capacity management unit An overlay node that sends capacity notification messages. The overlay node according to claim 6, comprising:
The capacity management unit divides the capacity among the plurality of next hop nodes so that there is no next hop node in which the capacity division amount exceeds the subsequent capacity consumption amount. The overlay node according to claim 5, comprising:
The end node management unit describes the priority of the local end node together with the capacity consumption in the end node status notification message,
The sum of the capacity consumption of all end nodes connected to the overlay node beyond the next hop node is the subsequent capacity consumption.
The reconnection management unit refers to the end node state notification message received from the downstream side, calculates the subsequent capacity consumption for each priority,
The reconnection management unit performs the reconnection instruction processing in the priority order,
In the reconnection instruction process with a certain priority, the reconnection management unit reserves in advance the capacity allocated to the end node with the current priority located beyond the next hop node. An overlay network system in which a multicast tree is constructed,
The transfer direction of the request to join the multicast group is defined as the upstream direction, the reverse direction of the upstream direction is defined as the downstream direction,
The capacity of an overlay node is a parameter corresponding to the allowable number of end nodes that can be additionally connected to the overlay node,
The multicast tree is
A first overlay node;
A second overlay node located downstream from the first overlay node, and
The first overlay node calculates the capacity of the first overlay node and sends a capacity notification message indicating the capacity and address of the first overlay node downstream;
The second overlay node refers to the capacity of the first overlay node indicated by the capacity notification message, and ends within the allowable number from a local end node currently connected to the second overlay node. Selecting a node, and sending a reconnection indication message indicating the address of the first overlay node to the selected end node;
When the selected end node receives the reconnection instruction message, the selected end node transmits a reconnection request to the first overlay node, and replaces the first overlay node with the new edge node instead of the second overlay node. And overlay network system. An end node reconnection method in a multicast tree constructed on an overlay network, comprising:
The transfer direction of the request to join the multicast group is defined as the upstream direction, the reverse direction of the upstream direction is defined as the downstream direction,
The capacity of an overlay node is a parameter corresponding to the allowable number of end nodes that can be additionally connected to the overlay node,
The multicast tree is
A first overlay node;
A second overlay node located downstream from the first overlay node, and
The reconnection method is:
Calculating the capacity of the first overlay node at the first overlay node;
Transmitting a capacity notification message indicating the capacity and address of the first overlay node downstream from the first overlay node;
In the second overlay node, based on the capacity of the first overlay node indicated in the capacity notification message, end nodes within the allowable number from a local end node currently connected to the second overlay node A step of selecting
Sending a reconnection indication message indicating the address of the first overlay node from the second overlay node to the selected end node;
Transmitting a reconnection request from the selected end node to the first overlay node in response to the reconnection instruction message.

Images