Background technology
Multicasting technology is meant realizes that between sender and each recipient point-to-point configuration connects.If a sender transmits identical data for simultaneously a plurality of recipients, also only need duplicate a identical data packet, improved data-transmission efficiency like this, reduce backbone network and congested possibility occurred.Because multicast can effectively reduce network and main frame expense, than clean culture and broadcasting its unique superiority is arranged, therefore, multicast has obtained using widely, main as real-time video conferencing system, teleeducation system, remote demonstration system and video on-demand system (VOD) or the like.
According to the distribution of multicast member in the network, generally speaking multicast routing protocol can be divided into following two kinds of fundamental types.First kind of hypothesis multicast member is distributed in the network thick and fast, that is to say, the most subnet of network all comprises a multicast member at least, and the network bandwidth is enough big, this being known as " dense mode " (Dense-Mode), this pattern-dependent " pushes away " routers all in network in the technology of flooding with data.The dense mode Routing Protocol comprises DVMRP, MOSPF and PIM-DM agreement etc.Second type be sparse mode, and its hypothesis multicast member is sparse dispersion in network, and network can not provide enough transmission bandwidths.So the sparse mode multicast routing protocol must depend on the technology with routing capability and set up and keep multicast tree.Sparse mode protocol mainly contains PIM-SM and CBT agreement.
Each above-mentioned multicast routing protocol all has its excellent, the shortcoming and scope of application separately.Multicast router is in actual applications realized multiple multicast routing protocol simultaneously in order to support various application widely, and this greatly increases the expense of multicast router on software and hardware.
Along with going deep into to network multicast research, industry is generally recognized and is only relied on the standard multicast business model can't support all multicast application well, and a large amount of foreseeable multicast application are application that source node is determined, have proposed to adopt the model of single source multicast service thus.The SSM architecture that IETF proposes promptly is based on single source multicast thought.This business model has following advantage: the restriction scheme that provides multicast to insert; Routing Protocol is realized simplifying; The management of multicast group does not need the group address administrative mechanism of whole network by source node management and coordination.
In recent years, some have also occurred above-mentioned several multicast routing protocols have been carried out improved research work.For example M λ T agreement and QoSMIC agreement all are the research to the multicast routing protocol of supporting QoS.And RALM agreement and TRAM agreement then are in order to realize reliable multicast.In addition, along with the continuous development of wireless network, multicast path is by also having obtained certain development in field of wireless.
But these technology all are based on the datagram structure, therefore can not solve safe, resist and ruin and problem such as guarantee service quality.Traditional multicast is almost not too many research aspect survivability, more is to rely on unicast technique.Traditional multicast is when link failure occurring, and all nodes all will recomputate route, and amount of calculation is big, and convergence time is long, and multicasting survivability is poor.
Summary of the invention
The objective of the invention is to overcome the deficiencies in the prior art, a kind of method that strengthens multicasting survivability is provided.
For achieving the above object, the present invention strengthens the method for multicasting survivability, it is characterized in that, may further comprise the steps:
(1), initialization participates in all nodes of multicast, the multicast source node calculates extension information source tree sequence, has comprised backup path in the extension information source tree sequence;
(2), the multicast source node obtains the multicast tree sequence according to extension information source tree sequence;
(3), the multicast source node sends multicast packet according to the multicast tree sequence to multicast member;
(4), the node of participating in multicast sends inquiry message every the time T downstream neighbor, sees down whether adjacent trip node exists, if step (3) is then returned in existence, if there is no, then this node breaks down;
(5) if certain node failure, the upstream neighbor node of this node is to multicast source node report fault message, if when having backup path to use, source node is directly enabled backup path and is sent multicast packet to multicast member;
(6) can't not repair the damage path if there is backup path can use or enable backup path, source node recomputates extension information source tree sequence, calculate the multicast tree sequence according to new extension information source tree sequence, source node continues to send data to multicast member according to new multicast tree sequence.
Goal of the invention of the present invention is achieved in that
The present invention is directed to multicasting technology and proposed the new anti-technology of ruining, at first when generating extension information source tree sequence, write down backup path, break down at a certain node like this, if the path has backup path to enable backup path when damaging, and need not recomputate the route of all nodes, multicast can recover in the shortest time, has strengthened multicasting survivability.Next node that participates in multicast sends inquiry message every the time T downstream neighbor, see whether downstream neighbor exists, if there is no, then this node breaks down, the path is damaged, and the upstream neighbor node of passing through this node can be found path damage information like this to multicast source node report fault message in very short time, compare with the discovery network failure of prior art, find that than legacy network the time of fault is shorter.And inquiry message only transmits between multicast node, can not increase offered load.At last, backup path can be used or enable even without backup path and the situation of damaging the path can't be repaired, because, the present invention adopts according to extension information source tree sequence and obtains the multicast tree sequence, the time of amount of calculation and reparation network all is significantly less than existing multicast network, and the survivability of multicast also is enhanced.
Embodiment
Below in conjunction with accompanying drawing the specific embodiment of the present invention is described, so that those skilled in the art understands the present invention better.What need point out especially is that in the following description, when perhaps the detailed description of known function and design can desalinate main contents of the present invention, these were described in here and will be left in the basket.
Embodiment
Fig. 1 is a kind of specific implementation method flow chart of method that the present invention strengthens multicasting survivability.
As shown in Figure 1, the present invention's method of strengthening multicasting survivability may further comprise the steps:
Step ST1: initialization participates in all nodes of multicast, and the multicast source node calculates extension information source tree sequence, has comprised backup path in the extension information source tree sequence;
Step ST2: the multicast source node obtains the multicast tree sequence according to extension information source tree sequence;
Step ST3: the multicast source node sends multicast packet according to the multicast tree sequence;
Step ST401: the node of participating in multicast sends inquiry message every the time T downstream neighbor, sees whether downstream neighbor exists; Step ST402: if exist, then return step ST3, if there is no, then this node breaks down;
Step ST501: if certain node failure, the upstream neighbor node of this node is to multicast source node report fault message; Step ST502: judged whether backup path; Step ST503: if when having backup path to use, source node is directly enabled backup path, step ST504: judge whether to start successfully, if enable, then return step ST3: send multicast packet;
Step ST6: can't not repair the damage path if there is backup path can use or enable backup path, source node recomputates extension information source tree sequence, calculate the multicast tree sequence according to new extension information source tree sequence, then return step ST3: source node continues to send data according to new multicast tree sequence to multicast member.
In the present embodiment, participate in the node of multicast, send inquiry message every time T to its downstream neighbor, its downstream neighbor receives that back answer upstream neighbor node shows that the path can reach, and downstream neighbor exists; If the overtime answer message of not receiving of upstream neighbor node, then upstream neighbor node thinks that downstream neighbor does not exist, and the path that arrives this downstream neighbor is damaged.
Upstream neighbor node is reported fault message to source node, after source node is received fault message, by checking that the multicast sequence sees if there is the multicast member that backup path can arrive the malfunctioning node influence, then enable backup path if any the backup path existence, if not having backup path can use, then source node begins the reconstruct multicast tree, promptly recomputate extension information source tree sequence, calculate the multicast tree sequence according to new extension information source tree sequence, source node continues multicast for all multicast members after finding best reachable path.
In the present embodiment, if a plurality of node failure is repaired from the near fault of source node earlier, repair again from source node fault far away.
Fig. 2 is a kind of concrete computational methods schematic diagram that multicast source node shown in Figure 1 calculates extension information source tree sequence.
In the present embodiment, the computational methods of extension information source tree sequence, as shown in Figure 2, each node is represented a router, and each node is represented a router among the figure, and for example: node 0 is represented router 0, and node 1 is represented router one.
For the ease of storage and application, we are the sequence of each node and left and right sides bracket with the information source tree representation, and the information source that is expanded is set sequence, and extension information source is set sequence replacement routing table.1), get source node v in the present embodiment, a kind of concrete computational methods of calculating extension information source tree sequence are:
s(the v of branch
s, v
1... v
m); 2), if branches greater than 0, with each child node v of branch
iSubstitute (v with its branch
i, v
1... v
n); 3), the branch of all child nodes is repeated 2), be 0 up to the branches that obtains child node, promptly all become leaf node, finish the information source that is expanded tree sequence; At last to all backup path (v
i, v
j), at the v of extension information source tree sequence
iThe side's of adding left bracket before the node is at v
jThe side's of adding right parenthesis behind the node, backup path just is included in the extension information source tree sequence like this.
As Fig. 2,5 paths that two same weights are arranged from node 2 to node, one is that 5, one of node 2-node 4-nodes are node 2-node 5, conventional router is in the process that generates routing table, 2 of nodes can write down an optimal path, in the present invention, and two optimal paths of router records, wherein one is labeled as backup path, in the present embodiment, node 2-node 5 is a backup path, v
sWhen generating extended source information source tree at V
2Preceding mark left square bracket is at V
5The right-hand bracket of back mark.
In the present embodiment, the middle extension information source tree sequence that obtains Fig. 1 according to top method is: V
0(V
1([V
2V
3(V
4V
5] V
6))) ([V
7(V
8V
9]) V
10V
11)) V
12, the sequence in its bracket is represented the component source tree.
By this sequence, can conveniently find out optimal path and multicast tree.Compare with routing table, the storage volume that information source tree sequence is occupied is little, only slightly many than the space that stores each node address summation, be about half of routing table, when considering mask, be about 1/4th of routing table, but but comprised much more important information than routing table, i.e. intermediate node information, and need not the information source tree further transformed and form routing table.Because memory space reduces greatly, solved the problem that routing table constantly expands, accelerated the speed of data forwarding, so this method makes multicast have good expandability, can be applied on the large-scale network.Traditional router only keeps source node, next-hop node and the destination node of each bar optimal path, and all the other intermediate nodes then are dropped.And the information of these intermediate nodes is very useful, especially under the situation of route self-healing recovery.The basis of new routing infrastructure has strengthened route self-healing recovery ability owing to stored intermediate node information.
Fig. 3 is the schematic diagram that is obtained the multicast tree sequence by extension information source tree sequence.
In the present embodiment, it is as follows to obtain the method for multicast tree sequence by extension information source tree sequence: from multicast source node V
SScan extension information source tree sequence to last one purpose node, by the following method the content of selecting put into the multicast tree sequence:
A. put into multicast source node V earlier
S, put into first left bracket and the postjunction thereof that run into again;
B. whenever to a right parenthesis, the content of just having put into is taken out; Just put into to left bracket and postjunction thereof whenever,, put into up to the purpose node that runs into;
C. after this put into the right parenthesis that runs into,, put into up to left bracket that runs into and postjunction thereof;
D. repeat b. and c. and run into last purpose node, put into up to b.; After this put into the adjacent right parenthesis that runs into, finish.
In the present embodiment, as shown in Figure 3, node 0 is the multicast source node, and multicast member is node 5 and node 11, according to said method, from extension information source tree sequence: V
0(V
1([V
2V
3(V
4V
5] V
6))) ([V
7(V
8V
9]) V
10V
11)) V
12Obtain multicast tree sequence: V
0(V
1(V
2(V
4V
5)) (V
7V
11))
Fig. 4 is the form of the inquiry message that regularly sends to its downstream neighbor of the node of participating in multicast.In the present embodiment, Router ID is the ID of upstream neighbor node, Interval is the time interval that sends inquiry message, this time interval can stipulate voluntarily according to the type of network, RouterDeadInterval is the out-of-service time, also do not receive the message of downstream node loopback then think that downstream neighbor lost efficacy that Neighbor is the ID of downstream node if surpass the out-of-service time upstream neighbor node.
Although above the illustrative embodiment of the present invention is described; so that the technical staff of present technique neck understands the present invention; but should be clear; the invention is not restricted to the scope of embodiment; to those skilled in the art; as long as various variations appended claim limit and the spirit and scope of the present invention determined in, these variations are conspicuous, all utilize innovation and creation that the present invention conceives all at the row of protection.