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

Intra-domain dynamic multipath generating method based on generating 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 the effect of reducing complexity and high reliability

Active Publication Date: 2014-01-22
TSINGHUA UNIV
View PDF2 Cites 8 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 node c to node d. The first method is to construct an SPT with the neighbor node as the root on node c, but this method increases the complexity of the algorithm. complexity, another method is that the neighbor node transmits the calculated minimum cost to node d to node c, and this method increases the communication overhead
Recently, the IETF proposed 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 needs to calculate multiple SPTs on one node. Therefore, 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 dynamic multipath generating method based on generating tree
  • Intra-domain dynamic multipath generating method based on generating tree
  • Intra-domain dynamic multipath generating method based on generating tree

Examples

Experimental program
Comparison scheme
Effect test

no. 1 example

[0058] figure 1 is a schematic flowchart of a spanning tree-based intra-domain dynamic multi-path generation method according to the first embodiment of the present invention. This embodiment is a multi-path generation method in a static situation. Refer to figure 1 To explain in detail the steps of constructing an SPT rooted at a certain node. Multiple next hops from the root node to all other nodes can be calculated during the construction of the SPT. And the construction of SPT is an iterative process, each time a node is selected to join the SPT.

[0059] Step S110, initializing node information of all nodes in a network.

[0060] Specifically, the initialized node information includes the cost of each node, the parent node, the descendant node, and the visited flag attribute (visited). Define an access flag attribute for each node, set the initial value to unvisited false, when the node is added to the SPT, set the access flag attribute to visited true.

[0061] More ...

no. 2 example

[0085] Figure 6 It is a schematic flow chart of a spanning tree-based intra-domain dynamic multi-path generation method according to the second embodiment of the present invention. This embodiment is a dynamic multi-path generation method when the link state changes. Refer to Figure 6 to describe each step in detail.

[0086] For the convenience of description, we assume the minimum cost C from root node c to node s c (s) ≥ the minimum cost C from root node c to node e c (e).

[0087] Step S210, analyze the cost change of the link (edge) L(s, e), when the cost of the edge L(s, e) increases, execute step S220, otherwise execute step S230.

[0088] Step S220, judging whether the structure of the statically constructed shortest path tree SPT with respect to the root node c has changed.

[0089] Specifically, if the judgment result is negative, that is, when the edge is not on the SPT, the next hops from the root node c to nodes s and e will be affected. There are two situa...

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 dynamic multipath generating method based on a generating tree. The method comprises the following steps: adding root nodes into a created priority queue according to a priority structure; judging whether the priority queue is empty or not, if not, selecting a first queue element of the priority queue, and deleting the first queue element; accessing all neighbor nodes of the first queue element, judging whether each node is accessed or not, if not, updating node information, adding updated information into the priority queue, otherwise, calculating a next hop from the root nodes to the first queue element and a next hop from the root nodes to a current neighbor node according to a set rule; after all neighbor nodes are accessed, returning to the step for judging whether the priority queue is empty or not. When a chain state changes, a generated shortest path tree is adjusted dynamically, and a next hop is updated without recalculation. According to the method, a plurality of loop-free paths are calculated from the root nodes to all destination nodes; meanwhile, the complexity of an algorithm is lowered.

Description

technical field [0001] The invention belongs to the technical field of the Internet, and in particular relates to an intra-domain routing algorithm, in particular to a spanning tree-based intra-domain dynamic multi-path generation method. 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 protocols do not make good use of the inherent path diversity in the network, and can only calculate from node c to node d Therefore, the reliability and security of the network are relatively poor. However, the multipath routing algorithm makes good use of the diversity of paths in the network, and can calculate multiple paths from node c to node d, so it is easy to achieve load balancing. [0004] Many solutions for multipath routing have...

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
IPC IPC(8): H04L12/753H04L12/733H04L45/122
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