CN1316783C - Data restoring method for application layer group broadcast - Google Patents

Abstract

The invention relates to the technical field of data communication, in particular to a data recovery method for application layer multicast. 1) Utilize the existing application layer multicast protocol to construct a data transmission tree in the terminal host of group communication; 2) determine the format of the control packet that needs to be sent to find the data recovery point; 3) modify the application layer multicast protocol, Enable each node to send and process the control packet for data recovery point and the control packet for data recovery point authentication and selection; 4) Modify the application layer multicast protocol so that each node sends data recovery data to the data recovery point after detecting packet loss. Click Send Request and receive recovery data. The invention avoids data loss and improves transmission reliability by finding potential nodes for each member in the sending tree as data recovery points, and using the recovery points to provide recovery data to group members in the event of data loss. The present invention is suitable to be realized in the application that utilizes the application layer or the terminal host to perform multicast data transmission service.

Description

A data recovery method for application layer multicast

technical field

The invention relates to the technical field of data communication, in particular to a data recovery method for application layer multicast.

Background technique

Providing group communication services on the next generation Internet is an inevitable trend of network development. Applications in this area include video/audio conferencing, distance education, Internet TV, online games and so on. Although the first proposed IP (Internet Protocol) multicast technology can reduce the load of the data sending source and effectively utilize network resources, it cannot be distributed in the network because the router needs to save the state for each multicast address, and there is no good transmission control mechanism. Large-scale configuration. The application layer multicast uses the terminal host to support group communication, and puts the management of multicast members, the replication of multicast data and other related functions at the application layer or the terminal host to complete. Existing routers do not need to make any changes, and can use the existing TCP (Transmission Control Protocol) or UDP (User Datagram Protocol) to transmit data, which is easy to deploy and implement, so it is likely to become the standard of future group communication technology.

However, there are still some problems to be solved in application layer multicast. The biggest problem is that the topology of application layer multicast changes very frequently. When a group member leaves the multicast group due to a system crash, other members will lose multicast data. Therefore, how to provide recovery data to group members becomes an urgent problem to be solved in application layer multicast. The application-layer multicast protocols that have been proposed so far have not been able to solve this problem well.

Contents of the invention

The purpose of the present invention is to provide a data recovery method for application layer multicast. Steps include:

By looking for possible data recovery points for each group member during data transmission, identifying the possible data recovery points found and selecting the appropriate data recovery point, and using the data recovery point to send data to the group in case of data loss. The group members with lost data transmit the lost data to achieve the purpose of reliable data transmission in the network.

Finding possible data recovery points for each group member is a random walk in the sending tree, each node generates a pair of random numbers u and v, first walks u hops in the direction close to the data source, and then moves away The direction of the data source goes down v hops. When going downstream, two strategies can be adopted. Randomly select one of several children as the next hop node, or designate the child with the slowest data forwarding speed as the next hop node. .

Identify the found nodes and select the appropriate data recovery point, using the globally unique application layer group number, and judge according to the difference in the number of the data received by the requesting node and the found node, only when the difference in the number is greater than zero, the found Nodes are qualified as recovery nodes, and the method of selecting the final recovery point from several candidate nodes that can be used as recovery points can select a more suitable recovery point according to the requirements of different services. For file transfer services, select the serial number The point with the largest difference, select the point with the smallest sequence number difference for streaming media transmission.

In the case of data loss, use the data recovery point to transmit the lost data to the group members who lost the data. Two different data recovery strategies can be used. If you need to reduce the redundant data in the network, you can only let the children of the failed node Nodes perform data recovery, and these nodes transmit recovery data to other affected nodes, and if you want to speed up recovery data and improve recovery data

The present invention is established on a network composed of computers, and is a process of performing point-to-multipoint or multipoint-to-multipoint group communication by using a terminal host or an application layer through a computer network. The group members and nodes mentioned in the invention are all computer , the invention is accomplished by these computers communicating with each other. The invention provides a data recovery method for application layer multicast. The purpose is to solve the problem that other related group members lose data when some group members fail during the application layer multicast data transmission. During data transmission, it judges the progress of each group member receiving data in the group, finds a suitable data recovery point for each group member, and quickly sends a request to the data recovery point after sensing data loss. Recovery points provide recovery data, thereby solving the data loss problem that occurs in application layer multicast.

The present invention finds a potential node for each member in the data transmission tree as a data recovery point, and uses the recovery point to provide recovery data to group members in the event of data loss, so as to avoid data loss and provide transmission reliability . The feature of the present invention is that each group member independently searches for a potential data recovery point, and the ability of the data recovery point is confirmed through the application layer group sequence number to enhance the possibility of finding the data recovery point, and different data recovery points can be selected according to the needs of different applications. Data recovery point, after data loss occurs, group members can independently recover data from different recovery points, and finally achieve the purpose of effectively recovering lost data.

Technical solutions

In order to further illustrate the innovation of the present invention, the basic concepts related to the present invention are firstly introduced. Members participating in group communication need to use the application layer multicast protocol to construct a data transmission tree for data transmission, and the data source is the root node. Each node (group member) on the sending tree has a parent node and zero to many child nodes. Nodes that have no children are called leaf nodes. Each node receives the data sent by the data source from the parent node and then forwards the data to the child nodes. In Figure 1 (a, b, c), pm is the parent node of m, pn is the parent node of n, and m and n are the child nodes of pm and pn respectively, and both m and n are leaf nodes. The nodes in the tree can be divided as follows according to their different roles in the invention. A node that can provide lost data to other nodes is called a recovery node, and the recovery node needs to have a spare degree. The nodes looking for recovery nodes are called request nodes, the nodes encountered during the search process are intermediate nodes, and the nodes that may be used as recovery nodes are called candidate nodes. In Figure 1 (a, b, c), m is the request node, pm and pn are intermediate nodes, o and n are candidate nodes, and n is the recovery node.

The packet sent by the data source has an application layer packet sequence number, which can uniquely identify a packet in the entire group. The progress (speed) of the node receiving data can be judged according to the application layer sequence number of the node receiving the packet.

specific plan:

1) Utilize the existing application layer multicast protocol to construct a data transmission tree in the terminal hosts that need to perform group communication;

2) Determine the format of the control packet that needs to be sent to find the data recovery point, and the format of the control packet that authenticates and selects the data recovery point;

3) Modify the application layer multicast protocol, so that each node can send and process the control packets for finding data recovery points and the control packets for authenticating and selecting data recovery points;

4) Modify the application layer multicast protocol so that each node can send a request to the data recovery point and receive the recovery data after detecting the packet loss.

Concrete method steps of the present invention are as follows:

The steps to be performed as a requesting node are:

1) Request node m to generate a control packet in the format of type 1, and send the control packet to the parent node; the control packet of type 1 contains a pair of random numbers (u, v); u means to go up from the node along the sending tree (closer to the data source) the number of hops that need to be passed, and v represents the number of hops that start to go downward (away from the data source) after the u-step backtracking.

2) After m receives the control packet of type 2, it sends a control packet of type 3. The characteristic of the type 3 control packet is that it carries the application layer packet sequence number seq1 received by m from the data source at the current moment;

3) After m receives the control packets of type 4 fed back from different nodes, select the most suitable node as the data recovery node for m; there are two strategies for selecting the recovery node. First, select the node with the largest sequence number difference seq1-seq2 As a recovery node, the recovery node selected in this way has the strongest ability to provide recovery data to m, which is suitable for file transmission; secondly, the node with the smallest sequence number difference seq1-seq2 is selected as the recovery node, and the recovery node selected in this way provides recovery data when The shortest delay is suitable for streaming media transmission;

4) Select n as the recovery node, and m sends a heartbeat message to n to ensure that n is in the sending tree and has the ability to be the recovery node of m;

5) If m does not receive a type 4 control packet from any node, or does not receive a heartbeat message sent by the recovery node n within a period of time, m restarts from step 2;

6) When m perceives the data loss, start the data recovery mechanism; the data recovery mechanism has two strategies, if you expect to reduce the redundant data in the network, then perform step 7, if you expect more nodes to get the restored data, Then perform step 8;

7) Node m checks whether its parent node works normally, if its parent node works normally, then m does not start the data recovery mechanism. In the entire sending tree, only the child nodes of the crashed node implement the data recovery mechanism. They send recovery requests to their respective recovery nodes. After receiving the recovery data, the requesting node forwards the recovery data to the child nodes;

8) Each node that perceives the data loss starts the data recovery mechanism separately, and requests data from the respective recovery nodes. After the request node receives the recovery data, it forwards the recovery data to the child node. If a node receives duplicate recovery data from its parent node, it sends a suppression message to the parent node. After the parent node receives the suppression message, it no longer Forward recovery data to child nodes. The steps to be performed as an intermediate node are:

1) Use the application layer group number to track the progress of its child nodes receiving data, and record the slowest child node receiving data;

2) After receiving the control packet of type 1, make the following judgment: if u>0, and this node is not the root node, then u is reduced by one, and the control packet is forwarded to the parent node; if u=0 or this node is already the root node node, then u=0, send the control packet to the child node; if u=0, v>0, and this node is not a leaf node, then v minus one, and forward the control packet to the child node; if u=0, v = 0 or this node is already a leaf node, then v is equal to 0, and the forwarding work of the control packet is completed and reaches node n. There are two strategies for forwarding control packets to child nodes. One strategy is a random method, that is, randomly select one of all child nodes as the next hop node for control packet forwarding. The other method is to forward the control packet to the step The slowest child node recorded in 1; the steps to be performed as a candidate node are:

1) The candidate node checks whether it has the necessary conditions as a data recovery point, that is, whether it has spare degrees to connect to a new node. If there is no spare degree, the node will no longer do any work. If there is, the node needs to send a type 2 control packet to m, and the type 2 control packet contains the address of the candidate node;

2) After the candidate node receives the control packet of type 3, it compares the relationship between the packet sequence number seq2 and seq1 it received from the data source, if seq2<seq1, then the candidate node sends a control packet of type 4 to m, otherwise The candidate node does not do anything, and the type 4 control packet contains the packet sequence number difference seq1-seq2; the steps to be performed as a recovery node are:

1) Send a heartbeat message to the requesting node;

2) After receiving the data recovery request from the requesting node, send the recovery data to the requesting node;

The present invention has the following advantages: first, it greatly alleviates the problem of data loss of descendant group members caused by the collapse of a certain group member in the network. Secondly, the task of data recovery is undertaken by many nodes in the sending tree, which prevents all group members who lost data from requesting data recovery from the data source together, causing the problem of too much load on the data source and network congestion. The third group member who lost data can The recovered data is obtained independently from different recovery nodes, thereby solving the problem of lost data correlation and speeding up the recovery of lost data. Finally, the algorithm adopts different data recovery strategies, which can meet the different requirements of different applications in data recovery.

The invention relates to using terminal host or application layer to provide multicast data transmission service, and is a method for improving the reliability of application layer multicast data transmission. The present invention is suitable to be realized in the application that utilizes the application layer or the terminal host to perform multicast data transmission service.

Description of drawings

Fig. 1 shows the process diagram of node m looking for recovery point n and recovering data in the case of data loss.

Fig. 1a shows the process diagram of sending random walk control packets to node m in the sending tree.

Fig. 1b is a diagram illustrating the process of node m performing qualification authentication on node n and node o by using the application layer packet sequence number.

Figure 1c shows the process diagram of data recovery by m using n after the parent node of node m fails.

Figure 2 illustrates the steps that nodes with different roles need to execute in the invention.

Detailed ways

Fig. 1 schematically shows the node m in the sending tree, and uses the method in the present invention to search for the recovery point and the whole process diagram of data recovery

Figure 1a shows the process of node m using the random walk strategy to find a possible recovery node n. Node m sends a random walk control packet (u=2, v=2), reaches node o, and sends a random walk control packet (u= 2, v=3), reach node n.

Figure 1b shows the process of node m using the application layer group number to authenticate node o and node n, that is, node m confirms which node can be used as the data recovery point, and finally selects the data recovery point as n.

Figure 1c shows the process of data recovery by m using n after the parent node of node m fails.

Figure 2 illustrates the workflow of nodes with different roles in the invention, request nodes, intermediate nodes, selected nodes, and recovery nodes.

The invention is a method for improving the reliability of multicast data transmission at the application layer. The invention avoids data loss and improves transmission reliability by finding potential nodes for each member in the sending tree as data recovery points, and using the recovery points to provide recovery data to group members in the event of data loss. The present invention is suitable to be realized in the application that utilizes the application layer or the terminal host to perform multicast data transmission service.

Claims (6)

1, a kind of method of the business that adopts end host to carry out group communication being carried out the data recovery, step comprises: during sending in data, for each group membership seeks possible data recovery point, the possible data recovery point that finds is carried out discriminated union select the suitable data recovery point, and occurring under the situation of loss of data, utilize the data recovery point to transmit obliterated data, reach the purpose of reliable transmitting data in network to the group membership of obliterated data;

Describedly seek possible data recovery point for each group membership, it is a kind of mode of random walk in sending tree, each node produces pair of random numbers u and v, at first jump to walking u near the direction of data source, jump to the v that is directed downwards away more subsequently away from data source, can take two kinds of strategies in the time of migration downwards, select one at random as next-hop node from several children, perhaps the slowest child of specific data forwarding speed is as next-hop node;

Describedly the node that finds is carried out discriminated union select the suitable data recovery point, utilized overall unique application layer packet sequence number, judge according to requesting node and the sequence number difference that the node that finds receives data, have only when the sequence number difference greater than zero the time, the node that finds just possesses the qualification as recovery nodes, and from can be used as the alternative node of recovery point, several select the method for final recovery point, can choose more suitably recovery point according to the requirement of different business, for the file transfer business, select the point of sequence number difference maximum, the point of sequence number difference minimum is selected in transmission for Streaming Media;

Describedly occurring utilizing the data recovery point to transmit obliterated data under the situation of loss of data to the group membership of obliterated data, can adopt two kinds of different data recovery policies, reduce the redundant data that occurs in the network if desired, then can only allow the child nodes of failure node carry out the data recovery, and by these nodes to other affected nodes transmission restore data, and if accelerate the speed of restore data and improve the probability of restore data, then can allow each affected node independently carry out the data recovery.

2, the method that the business that adopts end host to carry out group communication is carried out the data recovery according to claim 1, its step is as follows:

1) utilizes existing application layer multicast protocol, carry out at needs that construction data sends tree in the end host of group communication;

2) form of the controlling packet of the searching data recovery point that determine to need sends, and the form of the controlling packet that the data recovery point is authenticated and selects;

3) revise the application layer multicast agreement, make each node can send and handle the controlling packet of seeking the data recovery point and the controlling packet that the data recovery point is authenticated and selects;

4) revise the application layer multicast agreement, make each node after detecting packet loss, can send request, and receive restore data to the data recovery point.

3, the method that the business that adopts end host to carry out group communication is carried out the data recovery according to claim 1, the step that need carry out as a requesting node is:

1) requesting node m generation form is the controlling packet of Class1, and this controlling packet is sent to father node; The controlling packet of Class1 comprise pair of random numbers (u, v);

2) after m received the controlling packet of type 2, transmission types was 3 controlling packet, and the characteristics of type 3 controlling packet are to carry the application layer packet sequence number seq1 from data source that current time m receives;

3) m receives from the data recovery nodes of therefrom selecting optimal node as m after the controlling packet of different node type of feedback 4;

4) selected n is as recovery nodes, and m sends heartbeat message to n and sending in the tree and capable recovery nodes as m to guarantee n;

5) if m does not receive the controlling packet of type 4 from any node, perhaps in a period of time, do not receive the heartbeat message that recovery nodes n sends, m restarts from step 2;

6) after m perceives loss of data, the log-on data Restoration Mechanism; Time data recovery mechanism has two kinds of strategies, if expectation reduces the redundant data that occurs in the network, execution in step 7 so, if expect to have the more node data that are restored, execution in step 8 so;

7) if the node m father node operate as normal whether of checking it is its father node operate as normal, then m log-on data Restoration Mechanism not; Otherwise node is carried out time data recovery mechanism, to recovery nodes transmission recovery request separately, after requesting node is received restore data, transmits restore data to child nodes;

8) each perceives the node difference log-on data Restoration Mechanism of loss of data, to recovery nodes request msg separately, after requesting node is received restore data, transmit restore data to child nodes, if certain node is received the restore data of repetition from its father node, then send to father node and suppress message, father node is no longer transmitted restore data to child node after receiving and suppressing message.

4, the method that the business that adopts end host to carry out group communication is carried out the data recovery according to claim 1, the step that need carry out as an intermediate node is:

1) child nodes of utilizing the application layer packet sequence number to follow the trail of it receives the progress of data, the child nodes that the recorder data are the slowest;

2) receive the controlling packet of Class1 after, make the following judgment: if u＞0, and this node is not root node, and u subtracts one so, and controlling packet is transmitted to father node; If u=0 or this node have been root nodes, u=0 sends to child nodes to controlling packet so; If u=0, v＞0, and this node is not leaf node, v subtracts one so, and controlling packet is transmitted to child nodes; If u=0, v=0 or this node have been leaf nodes, v equals 0 so, controlling packet is transmitted end-of-job, arrives node n, transmits control to child nodes and is surrounded by two kinds of strategies, a kind of strategy is a random fashion, promptly select one at random from all child nodes, as the next-hop node that controlling packet is transmitted, another mode then is the slowest child nodes that controlling packet is transmitted to record in the step 1.

5, the method that the business that adopts end host to carry out group communication is carried out the data recovery according to claim 1, the step that need carry out as an alternative node is:

1) alternative node inspection it whether possess necessary condition as the data recovery point, be whether it is free remaining number to connect new node, if there are not the vacant number of degrees, node does not remake any work so, if have, node need send the controlling packet that form is a type 2 to m, and the controlling packet of type 2 comprises alternative address of node;

2) after alternative node is received the controlling packet of type 3, relatively its grouping serial number seq2 that receives from data source and the relation of seq1, if seq2＜seq1, so alternative node is 4 controlling packet to the m transmission types, otherwise alternative node is not done anything, and type 4 controlling packet comprise grouping serial number difference seq1-seq2.

6, the method that the business that adopts end host to carry out group communication is carried out the data recovery according to claim 1, the step that need carry out as a recovery nodes is:

1) sends heartbeat message to requesting node;

2) receive the data recovery request of requesting node after, send restore data to requesting node.

Images