KR20020051396A - Multicast structure and its method using ring structure - Google Patents

Abstract

PURPOSE: A multicast structure and method using a ring structure is provided to secure reliability and real-time character required for a real-time communication system and to give an efficient and stable extensibility in the real-time communication system. CONSTITUTION: A multicast structure consists of a sender(300) and rings(310-340). The sender(300) transmits leader tokens and general tokens to the nodes(311-341) of the rings(310-340). Among the nodes that belong to the rings(310-340), nodes(311,324,321,331,341) form another ring(350). The token sites(311-341), the nodes(311-341) which receive the leader tokens or the general tokens from the sender(300), transmit the received tokens to their respective neighboring nodes(312-342) so that the tokens can be transmitted to their respective rings(310-340).

Description

Multicast structure and method using ring structure {MULTICAST STRUCTURE AND ITS METHOD USING RING STRUCTURE}

The present invention relates to a multicast structure and method using a ring structure, and more particularly, to a multicast using a ring structure that improves reliability and efficiency of real-time communication by configuring a ring composed of one or more nodes and another ring composed of nodes of the rings. It relates to a structure and a method.

Multicast method is a method of transmitting a packet or a token only to nodes (eg, terminals) included in a specific multicast group, and is not included in the multicast group. Nodes can drop the packets or tokens at the point where most nodes can determine the network layer address or the network layer address. Therefore, the nodes can be dropped compared to the broadcast method. This significantly reduces the load on unrelated nodes. In order to ensure reliability in the multicast scheme, an acknowledgment / negative acknowledgment (Ack / Nak) is introduced.

1A illustrates a schematic diagram of a sender-initiation protocol according to the prior art, which includes a sender 10; It consists of a receiver set (11). The receiver set 11 is composed of nodes 11a to 11d. The sender 10 transmits a packet or token to the mode nodes 11a to 11d of the receiver set 11, receives an Ack or Nak from each of the nodes 11a to 11d, and receives the packet. Or check whether the token is sent. In the sender-initiation protocol, an Ack or Nak congestion occurs instantaneously from the nodes 11a to 11d.

FIG. 1B shows a schematic diagram of a receiver-initiated protocol according to the prior art, the receiver-initiated protocol comprising a sender 10; Receiver set 12. The receiver set 12 is composed of nodes 12a to 12d. The receiver-initiated protocol transmits only Nak only when the nodes 12a to 12d do not receive a packet or token from the sender 10 within a predetermined time or when there is a problem with the transmitted packet or token. That's the way. The receiver-initiated protocol can prevent Ack congestion, but may cause Nak congestion and cannot be used in the case of a communication system that does not depend on the predetermined time.

Figure 2a shows a schematic diagram of a tree-based protocol according to the prior art, wherein the tree-based protocol comprises a sender 20; It consists of a Local Group 21. The local group 21 includes a group leader node 21a, 21b; It consists of leaf nodes 22a-22d. The sender 20 transmits a packet or token to the group leader nodes 21a and 21b, and each of the group leader nodes 21a and 21b is sent to the leaf nodes 22a to 22d. The leaf nodes 22a and 22b transmit local Ack or Nak to the group leader node 21a, and the leaf nodes 22c and 22d transmit local Ack to the group leader node 21b. Alternatively, by sending Nak, the sender 20 receives two Ack or Nak from the group leader nodes 21a and 21b and processes them, thereby reducing the processing load and reducing the total number of nodes. Regardless, it can handle Ack or Nak. That is, partly, after receiving two Ack from the lower node, the Ack is transmitted to the upper node. Also, if the Ack is not transmitted or the Nak is transmitted after the time-out, the packet or token is transmitted. It is assumed that this was not transmitted correctly and retransmission is performed. Therefore, all the nodes (including group leader nodes 21a, 21b and leaf nodes 22a through 22d) must have information about all nodes registered in the same local group as themselves. It should be possible to determine its own child node and its parent node in the tree composed of. Although the tree-based protocol has significant advantages in scalability, as the level of the tree increases, the possibility of temporary errors due to delay and complexity of the structure (e.g., one node goes down) In this case, recovery takes time, and errors occur due to a topology that is difficult to recover during this time.

Figure 2b shows a schematic diagram of a ring-based protocol according to the prior art, which ring-based protocol comprises a sender 20; It consists of a ring 23. The ring (23) comprises: a token site (23a) for receiving packets or tokens from the center; Nodes 23b to 23e. The sender 20 sends the packet or token to the token site 23a, and after the token site 23a confirms that it has received the packet or token, the next node 23b on the ring 23 ) Transmits the packet or token, and if the packet or token is not received, transmits Nak to the sender 20 to request retransmission. After receiving the packet or token, the node 23b also confirms that it has received the packet or token, and then sends it to the next node 23c on the ring 23, and if the packet or token is not received, the token site 23a. Send Nak to request retransmission. When the packet or token is purified in the above manner and finally returned to the token site 23a, the token site 23a transmits an Ack to the sender 20 so that the transmitted packet or token is correctly transmitted. You will be notified. The ring-based protocol is superior to the tree-based protocol in terms of reliability, but when the number of nodes is large, there is a disadvantage in that the real time is considerably degraded.

The present invention has been made to solve the above problems, and an object of the present invention is to provide a structure and method for securing the reliability and real-time required for a real-time communication system. Another object of the present invention is to provide efficient and stable scalability in the real time communication system.

1A is a schematic diagram of a sender-initiated protocol according to the prior art.

1B is a schematic diagram of a receiver-initiated protocol according to the prior art.

2A is a schematic diagram of a Tree-Based Protocol according to the prior art.

2B is a schematic diagram of a ring-based protocol according to the prior art.

3 is a schematic diagram of a multicast structure according to the present invention;

4A is a schematic diagram illustrating one embodiment of the multicast structure of FIG.

4B is a schematic diagram illustrating token transmission in one embodiment of FIG. 4A.

5 is a flowchart illustrating a multicast method according to the present invention.

*** Explanation of symbols on main parts of drawing ***

300: Sender 310, 320, 330, 340: Ring

311, 321, 331, 341: Token Site

312, 313, 314: nodes

Multicast structure using the ring structure of the present invention is one sender; One or more rings of one or more nodes, including a token site that is a node receiving a token from the sender, one or more of the nodes of each ring forms a different ring, multicast using a ring structure The method includes the node receiving a token in the above structure; A first judging step of judging whether the node has sent the token to the sender; A second judging step of judging whether the node receiving the token is a token site; The token site sending a confirmation response to the sender.

3 is a schematic diagram of a multicast structure according to the present invention, which includes a sender 300; Ring 310; 320; 330; 340. The sender 300 sends a leader token and a general token to the nodes 311; 321; 331; 341 of the rings 310; 320; 330; 340 (hereinafter, the leader token or general purpose token). Each node receiving the token is transmitted to the token site (311; 321; 331; 341). Among the nodes belonging to the rings 310; 320; 330; 340, nodes 311; 324; 321; 331; 341 form another ring 350. The token sites 311; 321; 331; 341 transmit the received tokens to neighboring nodes 312; 322; 332; 342 of the same ring, respectively, to the rings 310; 320; 330; 340. Allow the token to be sent.

Token sites 311 and 331 receiving the leader token are circulated in the leader tokens in the rings 310 and 330 to which they belong, so that each node 312; 313; 314, 332, 333 Check whether the leader token is correctly received, and if the node that has not received the leader token or receives the wrong token sends Nak, retransmitting the leader token is performed in the same manner as in the conventional ring structure. In addition, the token site (311; 331) is the leader after confirming that all the nodes (312; 313; 314), (332; 333) in the interior of the ring (310), 330 received the leader token correctly A token is sent to nodes 324 and 341 of neighboring rings on the ring 350, respectively. The receiving node does not necessarily need to be a token site, which means that every node in the ring 310; 320; 330; 340 knows which node the token site is, and also sends the leader token to the token site. It is because it has a function to transmit. As such, when the sender 300 transmits the token for all rings 310; 320; 330; 340, some of the token sites designated by the sender 300 may be inoperable or may already have rings 310; 320. 330; 340 may not be present inside, i.e., because the sender 300 is not sure whether the token site targeted by the sender 300 is operating normally and can process the token normally, Since it is pointless to send information about the token site in the token, if there is a problem with the target token site, the token site is designated as another node of the ring to which the token site belongs. The token site 311; 331 sends an Ack for the leader token to the sender 300 upon receiving the leader token from the previous ring 320; 340 on the ring 350.

The token sites 321 and 341 receiving the universal token perform token transmission in a conventional ring structure such as the token sites 311 and 331, and the difference from the token sites 311 and 331 is different from the token sites. Sites 321 and 341 may be configured after the universal token has cycled through the interior of the ring 320; 340 (ie, at all nodes 322; 323; 324, 342; 343; 344). Even if it is normally transmitted, the Ack is not transmitted to the sender 300, and the received universal token is destroyed without being transmitted to the neighboring ring on the ring 350. Also, if the token site 321; 341 receives the leader token transmitted from the neighboring ring on the ring 350, if the universal token received by the token site 321; 341 has expired, the leader immediately Sends a token to a node in a neighboring ring of the ring 350, and if the universal token is being circulated inside the rings 320, 340 or if normal transmission has not yet been performed, the universal token is not circulated. And retains the leader token until normal transmission is performed, i.e. until the universal token is destroyed.

Therefore, if the sender 300 receives only the Ack from the token site (311; 331) to check the accuracy of the token transmission, and only responsible for transmitting the token to the token site (311; 321; 331; 341) Will be.

4A and 4B show schematic diagrams showing one embodiment of the multicast structure of FIG. In FIG. 4A, the sender 300 transmits leader tokens 1 and 2 to the token sites 311 and 331, respectively, and sends a universal token 1 to the token sites 321 and 341. ) And (2) respectively. If the token site (311; 321; 331; 341) examines the received token and determines that the token is received correctly, the token site (311; 321; 331; 341) receives the token to the neighboring nodes (312), (322), (332), and (342), respectively. And circulate within the rings 310, 320, 330, 340. For example, if the leader token 1 circulated in the ring 310 was not correctly transmitted from the node 313, the node 313 sends Nak to the token site 311 to send the token site. 311 causes the leader token 1 to be retransmitted. The token sites 311 and 331 cycle through the rings 310 and 330 and check whether the transmitted leader tokens 1 and 2 are tokens previously transmitted from the sender 300. If the previously received tokens are the same, the leader tokens 1 and 2 are transmitted to nodes of the rings 320 and 340 adjacent to each other on the ring 350. The token sites 321 and 341 cycle through the rings 320 and 340 and hold the universal tokens 1 and 2 transmitted for a predetermined time, and the nodes 322; 323; 324) and (342; 343; 344), if no Nak is sent, the universal token (1), (2) is destroyed. The node 324 receiving the leader token 1 transmits the leader token 1 to the token site 321 of the ring 320.

In FIG. 4B, the token sites 321 and 341 transmit the received leader tokens 1 and 2 back to the token sites 331 and 311, respectively. The token sites 331 and 311 recognize that the leader tokens 1 and 2 are not transmitted from the sender 300 and do not purify them into the rings 330 and 310. Send Ack to 300). The sender 300 determines that the transmission of the leader tokens 1 and 2 is made correctly when the Ack becomes equal to the number of the leader tokens 1 and 2.

5 is a flowchart illustrating a multicast method according to the present invention, in which all nodes except the sender 300 process tokens received according to the method. In step S500, the multicast structure of FIG. 3 is set, and in step S501, each node receives the transmitted data to determine whether it is a token, and stores the data when the data is not a token. (Step S502) If it is a token, it is determined whether the sender 300 transmits the token in step S503. In step S503, if the sender 300 transmits the token, the node that receives the token is set to a token site (step S504), and transmits the received token to a neighbor node of the same ring. (Step S507). If the sender of the token is not the sender 300 and the node of the same ring (step S505), it is determined whether the node that receives the token is a token site (step S506). If it is not a token site, the token is transmitted to a neighbor node of the same ring (step S507). If it is a token site, it is determined whether the token is a leader token (step S508), if it is a universal token, the token is destroyed (step S510), and if it is a leader token, step S512 is performed. If a node of the same ring did not transmit the token (step S505), it is determined whether the node that received the token is a token site (step S509). If the node is not a token site, the token is transmitted to the token site (step S511). If the node is a token site, the process proceeds to step S512. In step S512, the node determines whether the token site has previously received the leader token, and if it receives the leader token, determines whether the token is the previously received leader token (step S513), If it is not a previously received token, Ack is transmitted to the sender 300 (step S514). If the node is not a token site that has previously received a leader token (step S512), or if the token has previously received a leader token (step S513), then the token is transferred to another ring 350. Transmit to the node of the ring (step S515). The token site receiving the universal token from the sender 300 in step S515 further includes holding the received leader token before destroying the universal token in step S510.

According to the present invention of the above configuration, there is an effect to improve the real-time and expandability in the centralized system in the real-time communication system. That is, by using the token site and the ring 350 to receive and send the sender's burden, by reducing the number of Ack received and the total amount of tokens transmitted, tokens can be quickly transmitted to the entire system. It is possible to improve the real-time so that the real-time, and to increase the node of the system to which the token is transmitted to improve the scalability to maintain the real-time.

Claims (15)

With one sender; A ring structure comprising one or more rings including one or more nodes, including a token site, a node receiving a token from the sender, wherein one or more nodes of the nodes of each ring form another ring; Multicast structure used. The method of claim 1, The token is a multicast structure using a ring structure, characterized in that one of the leader token and the general purpose token. The method of claim 2, And the token site transmits the token to neighboring nodes of the token site so that all of the tokens are transmitted to other nodes in the ring including the token site. The method of claim 3, wherein The token site receiving the leader token receives the acknowledgment from all nodes of the ring, and then transmits the leader token to a node of a neighboring ring. The method of claim 3, wherein And the token site receiving the universal token destroys the received universal token after receiving the acknowledgment from all nodes of the ring. The method according to claim 3 or 4, If the node receiving the leader token from a ring adjacent to the ring contains the token site receiving the leader token, the receiving node sends the leader token to the token site, and the token site acknowledges the sender. Multicast structure using a ring structure, characterized in that for transmitting and destroying the leader token. The method according to claim 3 or 4, And transmitting the leader token to a neighboring node of the ring if the node receiving the leader token from a ring adjacent to the ring includes a token site receiving the universal token. With one sender; A multicast structure comprising one or more rings of one or more nodes, including a token site, a node receiving a token from the sender, wherein one or more of the nodes of each ring form another ring The node receiving a token; A first judging step of judging whether the node has sent the token to the sender; A second judging step of judging whether the node receiving the token is a token site; And sending, by the token site, an acknowledgment to the sender. The method of claim 8, The token is a multicast method using a ring structure, characterized in that one of the leader token and universal token. The method according to claim 8 or 9, And receiving the token comprises storing the received node if the token is not a token but a message. The method according to claim 8 or 9, And the first determining step includes transmitting the token to a neighboring node in the same ring when the sender transmits the token. The method according to claim 8 or 9, Where the token is transmitted in the first determination step is a node in the same ring, and if the node is not a token site in the second determination step, the token is transmitted to a neighboring node, and in the first determination step, the token is transmitted. Sending the token to the token site of the ring to which the node belongs, if the node is a node of another ring where the token is sent, and the node is not a token site in the second judging step; Multicast method using a ring structure, characterized in that. The method according to claim 8 or 9, In the second determination step, if the node is the token site that has received the leader token, the token is the leader token, and if the leader token is the leader token transmitted by the token site, the leader token is transmitted to a node of another ring. And if the leader token is not a leader token transmitted by the token site, transmitting the acknowledgment to the sender. The method according to claim 8 or 9, In the second determination step, the node is a token site that has received the universal token, and if the token is a leader token, sends the leader token to a node of another ring, and if the token is a universal token, destroys the universal token. Multicast method using a ring structure, characterized in that it further comprises the step of. The method of claim 14, And if the leader token is transmitted before the universal token in the ring to which the token site belongs is extinguished, retaining the leader token until the universal token is extinguished.