Network detection method and controller using the method

Patent metadata

Field	Value
Publication number	US-2016337188-A1
Application number	US-201615074184-A
Country	US
Kind code	A1
Filing date	Mar 18, 2016
Priority date	May 14, 2015
Publication date	Nov 17, 2016
Grant date	—

Abstract

A network detection method links multiple nodes residing in a network topology to form multiple edges and creates snake paths through the edges using a snake algorithm. The routing frequencies of each of the snake paths is calculated, and software-defined network (SDN) policy flows to each of the nodes are produced and applied. The health and performance status, and available bandwidths, of the snake paths are dynamically detected via packet flows using a pathChirp bandwidth detection method.

First claim

What is claimed is:

1 . A network detection method, executable by a processor of a controller, the method comprising:
linking multiple network devices residing in a network topology to form multiple edges; implementing quantization to network data of the edges to obtain network state scores; converting the network state scores to check frequency levels (CFLs) corresponding to the edges; selecting a first network device comprising the maximum connected edges as a start network device; creating multiple routing paths comprise at least one first routing path, wherein the first routing path comprises multiple first network devices from the network devices and multiple first edges from the edges; calculating routing frequency of the first routing path according to first CFLs of the first edges; inferring a policy flow for the first routing path using the CFLs and applying the policy flow to the first network devices; transmitting a probe packet on the first routing path and adding timestamps to the probe packet by the first network devices; returning the probe packet to the controller via the last network device; and collecting probe packets returned along the first routing path and analyzing the probe packets to obtain health states of the first routing path for network data update.

2 . The method as claimed in claim 1 , the selecting step further comprises:
selecting a second network device comprising the maximum connected edges; selecting a second edge from the edges connected to the second network as a start edge and moving to a third network device; wherein a second CFL of the second edge is less than a specific value, wherein the second edges is added to form a second routing path; determining whether the third device comprises any edge; determining whether the total length of the second routing path is less than or equal to a first preset value when the third device comprises at least one edge; calculating CFLs of unused edges of the third network device, if the total length of the second routing path is less than or equal to the first preset value, and calculating differential values between the CFLs of the unused edges and the CFL of a selected edge connecting the third network device and the network device prior to the third network device; determining whether there is an edge with its differential value less than a second preset value for the third network; if there is a third edge with its differential value less than the second preset value for the third network, adding the third edge to the second routing path and moving to a fourth network device; and repeating the above steps until there is no edge with its differential value less than the second preset value or the total length of the second routing path is greater than the first preset value, and rendering the second routing path.

3 . The method as claimed in claim 2 , wherein the selecting step further comprises:
performing a recall process to discover a fourth network device if there is no edge for the third network; determining whether there is an edge for the fourth network; taking the fourth network device as the start network device, if there is at least one edge for the fourth network, and repeating the above steps to create a new routing path; and terminating the process if there is no edge for the fourth network.

4 . The method as claimed in claim 2 , wherein the selecting step further comprises:
rendering the second routing path if the total length of the second routing path is greater than the first preset value; and taking the current network device as the start network device and repeating the above steps to creating another routing path.

5 . The method as claimed in claim 2 , the selecting step further comprises:
rendering the second routing path if there is no edge with its differential value less than the second preset value for the third network.

6 . The method as claimed in claim 2 , further comprising:
if there are at least two edges with their differential values greater than the second preset value for the third network, randomly selecting and adding one of the edges to the second routing path.

7 . The method as claimed in claim 1 , further comprising:
implementing quantization to network data of the edges to obtain the network state scores based on multiple factors.

8 . The method as claimed in claim 1 , further comprising:
creating the routing paths of the network topology using a Snake algorithm.

9 . The method as claimed in claim 1 , wherein the bandwidth detection algorithm is the pathChrip algorithm.

10 . A controller, comprising:
at least one processor; a storage system; and one or more programs that are stored in the storage system and executed by the at least one processor, the one or more programs comprising instructions for: linking multiple network devices residing in a network topology to form multiple edges; implementing quantization to network data of the edges to obtain network state scores; converting the network state scores to check frequency levels (CFLs) corresponding to the edges; selecting a first network device comprising the maximum connected edges as a start network device and creating multiple routing paths comprise at least one first routing path, wherein the first routing path comprises multiple first network devices from the network devices and multiple first edges from the edges; calculating routing frequency of the first routing path according to first CFLs of the first edges; inferring a policy flow for the first routing path using the CFLs and applying the policy flow to the first network devices; transmitting a probe packet on the first routing path and adding timestamps to the probe packet by the first network devices; returning the probe packet to the controller via the last network device; and collecting probe packets returned along the first routing path and analyzing the probe packets to obtain health states of the first routing path for network data update.

11 . The controller as claimed in claim 10 , further comprising instructions for:
selecting a second network device comprising the maximum connected edges; selecting a second edge from the edges connected to the second network as a start edge and moving to a third network device; wherein a second CFL of the second edge is less than a specific value, wherein the second edges is added to form a second routing path; determining whether the third device comprises any edge; determining whether the total length of the second routing path is less than or equal to a first preset value when the third device comprises at least one edge; calculating CFLs of unused edges of the third network device, if the total length of the second routing path is less than or equal to the first preset value, and calculating differential values between the CFLs of the unused edges and the CFL of a selected edge connecting the third network device and the network device prior to the third network device; determining whether there is an edge with its differential value less than a second preset value for the third network; if there is a third edge with its differential value less than the second preset value for the third network, adding the third edge to the second routing path and moving to a fourth network device; and repeating the above steps until there is no edge with its differential value less than the second preset value or the total length of the second routing path is greater than the first preset value, and rendering the second routing path.

12 . The controller as claimed in claim 11 , further comprising instructions for:

Assignees

• Hon Hai Prec Ind Co Ltd

Inventors

• Yang Kai-Yu
• Shao Bo-Run
• Chung Hao-Wen

Classifications

• H04L45/56

  Routing software · CPC title

• H04L41/0893

  Assignment of logical groups to network elements · CPC title

• H04L45/26

  Route discovery packet · CPC title

• H04L41/0816 Primary

  the condition being an adaptation, e.g. in response to network events · CPC title

• H04L43/20

  the monitoring system or the monitored elements being virtualised, abstracted or software-defined entities, e.g. SDN or NFV · CPC title