Intra-Domain Multipath Generation Method Based on Spanning Tree

Abstract

The invention discloses an intra-domain multipath generating method based on a spanning tree. The method comprises the steps of adding nodes into an established priority queue according to a priority structure; judging whether the priority queue is empty, and if not, selecting and deleting a queue header element of the priority queue; having access to all neighbor nodes of the queue header element, judging whether access to the nodes are had, if not, then updating node information and adding updated information to the priority queue, otherwise, calculating the next single hop from a root node to the queue header element and the next hop from the root node to the current neighbor node; if having access to all the neighbor nodes, returning to the step of judging whether the priority queue is empty. According to the intra-domain multipath generating method based on the spanning tree, a plurality of paths without circles can be calculated for the operation algorithm from a certain node to a target node, and it is only necessary to maintain one multipath tree for the nodes of the operation algorithm, so that complexity is reduced.

Description

technical field [0001] The invention belongs to the technical field of the Internet, and relates to a method for generating intra-domain routes, in particular to a method for generating multi-paths in a domain based on spanning trees. Background technique [0002] The Internet is composed of tens of thousands of autonomous systems AS (Autonomous System) that are independently operated and maintained. [0003] Intra-domain link state routing protocols (OSPF and ISIS) control the packet forwarding path inside the AS, but OSPF and ISIS do not make good use of the inherent path diversity in the network, and can only calculate A shortest path, so the reliability and security of the network are relatively poor. The multi-path routing algorithm makes good use of the inherent path diversity in the network, and can calculate multiple paths from the source node to the destination node, thus greatly improving the reliability and security of the network, and is very Easy to achieve lo...

AI Technical Summary

Problems solved by technology

There are two ways to get the minimum cost from all neighbor nodes of the node to the destination node. The first method is to construct an SPT with the neighbor node as the root on the node, but this method increases the complexity of the algorithm degree, another method is that the neighbor node transmits the calculated minimum cost to the destination node to the node, and this method increases the communication overhead

Recently, IETF has proposed multi-topology routing (Multi-topology routing). This method is characterized by pre-assuming that some links fail, and calculating the shortest path in the network topology diagram where the failed links are removed. This method also requires Calculate multiple SPTs, so the time complexity of the algorithm is relatively high

Images