Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Intra-domain multipath generating method based on spanning tree

A multi-path and spanning tree technology, applied in the Internet field, can solve problems such as high algorithm time complexity, increase algorithm complexity, increase communication overhead, etc., and achieve high reliability

Active Publication Date: 2014-04-30
TSINGHUA UNIV
View PDF8 Cites 4 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

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

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Intra-domain multipath generating method based on spanning tree
  • Intra-domain multipath generating method based on spanning tree
  • Intra-domain multipath generating method based on spanning tree

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0039] In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings.

[0040] In order to make up for the deficiencies of the existing methods, the present invention proposes a method for generating intra-domain multipaths based on spanning trees. In order to ensure that the path from a source node to the destination node calculated by this method is loop-free, all nodes in the network must maintain consistent calculation information, but all nodes in the network are distributed calculations , so in order to get consistent computing information, each node must perform the same computing or exchange information through neighbors.

[0041] In OSPF, each node constructs SPT with itself as the root node. Although the SPT constructed by each node is different, the minimum cost calculated by each node to the destination node is the same, s...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

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...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Applications(China)
IPC IPC(8): H04L12/721H04L12/753
Inventor 尹霞施新刚耿海军王之梁
Owner TSINGHUA UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products