CN114301827A - Method and apparatus for searching optical cable route - Google Patents
Method and apparatus for searching optical cable route Download PDFInfo
- Publication number
- CN114301827A CN114301827A CN202011009146.4A CN202011009146A CN114301827A CN 114301827 A CN114301827 A CN 114301827A CN 202011009146 A CN202011009146 A CN 202011009146A CN 114301827 A CN114301827 A CN 114301827A
- Authority
- CN
- China
- Prior art keywords
- route
- node
- optical cable
- path
- access
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 230000003287 optical effect Effects 0.000 title claims abstract description 111
- 238000000034 method Methods 0.000 title claims abstract description 59
- 235000008694 Humulus lupulus Nutrition 0.000 claims abstract description 13
- 230000002457 bidirectional effect Effects 0.000 claims abstract description 8
- 239000000835 fiber Substances 0.000 claims description 26
- 230000015654 memory Effects 0.000 claims description 14
- 238000003860 storage Methods 0.000 claims description 10
- 238000004891 communication Methods 0.000 description 9
- 238000013461 design Methods 0.000 description 6
- 238000010586 diagram Methods 0.000 description 3
- 238000005457 optimization Methods 0.000 description 3
- 238000010845 search algorithm Methods 0.000 description 3
- 230000002776 aggregation Effects 0.000 description 2
- 238000004220 aggregation Methods 0.000 description 2
- 238000010276 construction Methods 0.000 description 2
- 238000013500 data storage Methods 0.000 description 2
- 238000005516 engineering process Methods 0.000 description 2
- 230000014509 gene expression Effects 0.000 description 2
- 238000007726 management method Methods 0.000 description 2
- 230000008569 process Effects 0.000 description 2
- 238000012545 processing Methods 0.000 description 2
- 239000007787 solid Substances 0.000 description 2
- 230000004931 aggregating effect Effects 0.000 description 1
- 238000003491 array Methods 0.000 description 1
- 239000000969 carrier Substances 0.000 description 1
- 230000010267 cellular communication Effects 0.000 description 1
- 238000013499 data model Methods 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 238000009826 distribution Methods 0.000 description 1
- 238000005315 distribution function Methods 0.000 description 1
- 230000007717 exclusion Effects 0.000 description 1
- 238000009434 installation Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 239000013307 optical fiber Substances 0.000 description 1
- 230000002093 peripheral effect Effects 0.000 description 1
- VYMDGNCVAMGZFE-UHFFFAOYSA-N phenylbutazonum Chemical compound O=C1C(CCCC)C(=O)N(C=2C=CC=CC=2)N1C1=CC=CC=C1 VYMDGNCVAMGZFE-UHFFFAOYSA-N 0.000 description 1
- 238000012216 screening Methods 0.000 description 1
- 230000003068 static effect Effects 0.000 description 1
- 238000000547 structure data Methods 0.000 description 1
- 238000012795 verification Methods 0.000 description 1
Images
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The present disclosure provides a method and apparatus for searching for an optical cable route. The method comprises the following steps: acquiring user parameters, wherein the user parameters comprise an initial node and a termination node of an optical cable route; acquiring a network model of the optical cable, wherein the network model comprises nodes and links among the nodes; judging whether the optical cable comprises a section according to the user parameters, wherein links among nodes in the section are bidirectional; wherein if the optical cable includes a block section, the method further comprises: based on a network model, on the principle that the number of hops is as small as possible, searching a route between a first node as a starting point of a block and a second node as an end point of the block by using a block algorithm to obtain a block route, wherein if the optical cable only comprises the block, the block route is the optical cable route.
Description
Technical Field
The present disclosure relates to the field of communication network computer management (IT) technology, and in particular, to a method and apparatus for searching for an optical cable route.
Background
Optical cable networks for telecommunications carriers are extremely complex in structure, connectivity, and even more complex than traffic networks. In the scheduling and reasonable utilization of optical path service resources, how to rapidly and reasonably configure optical path routes to realize safe and efficient opening of service routes, and the method has great influence on both internal network construction optimization and government and enterprise service opening. This is also one of the core technical difficulties to be solved in the automatic service provisioning.
For a long time, the optical path routing design in the optical cable network resource scheduling completely depends on manual operation, the workload is large, and the requirements on the skill of personnel and the network familiarity are extremely high. In addition, the routing design of manual operation lacks an automatic inquiry means for judging whether the cable resource can reach a service site, and lacks effective management for the utilization efficiency of fiber core resources. These problems may cause problems of inefficient scheduling, repeated network construction, inconsistent network and resource system data, etc.
On the other hand, the existing optical path routing search technology uses search algorithms with breadth-first, depth-first and shortest path, and the search algorithms have the defects of inconsistency with the actual optical network structure and service scene, low search efficiency and the like.
Therefore, there is a need for an optical path route search method capable of solving the above-described problems.
Disclosure of Invention
According to a first aspect of the present disclosure, there is provided a method for searching for an optical cable route, comprising: acquiring user parameters, wherein the user parameters comprise an initial node and a termination node of an optical cable route; acquiring a network model of the optical cable, wherein the network model comprises nodes and links among the nodes; judging whether the optical cable comprises a section according to the user parameters, wherein links among nodes in the section are bidirectional; wherein if the optical cable includes a block section, the method further comprises: based on a network model, on the principle that the number of hops is as small as possible, searching a route between a first node as a starting point of a block and a second node as an end point of the block by using a block algorithm to obtain a block route, wherein if the optical cable only comprises the block, the block route is the optical cable route.
According to a second aspect of the present disclosure, there is provided a non-transitory computer readable storage medium for searching for optical cable routes, having a program stored thereon, which when executed by a computer, causes the computer to perform the method according to the first aspect of the present disclosure.
According to a third aspect of the present disclosure, there is provided a computing device for searching for optical cable routes, comprising a memory communicatively coupled to a processor and a processor, the memory having stored therein a program which, when executed by the processor, causes the processor to perform the method according to the first aspect of the present disclosure.
According to a fourth aspect of the present disclosure, there is provided an apparatus for searching for optical cable routes, comprising means for performing the method according to the first aspect of the present disclosure.
The method and the device can realize an automatic algorithm scheme of a plurality of shortest paths, the algorithm can quickly and accurately calculate a plurality of optimal paths, the route design efficiency and the route design configuration reliability are obviously improved, and the problem of route search of light paths between offices is solved.
Other features of the present disclosure and advantages thereof will become more apparent from the following detailed description of exemplary embodiments thereof, which proceeds with reference to the accompanying drawings.
Drawings
The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate embodiments of the disclosure and together with the description, serve to explain the principles of the disclosure.
The present disclosure may be understood more clearly and in accordance with the following detailed description, taken with reference to the accompanying drawings,
wherein:
figure 1 is a schematic diagram of an optical network topology according to an embodiment of the present disclosure.
Fig. 2 is a flow chart of a method for searching for cable routes according to an embodiment of the present disclosure.
Fig. 3 is a flow chart of a method for searching for cable routes according to an embodiment of the present disclosure.
Fig. 4 is a schematic diagram of an exemplary computing device that may be used to implement a method of searching for fiber optic cable routes according to embodiments of the present disclosure.
For convenience of understanding, the positions, sizes, ranges, and the like of the respective structures shown in the drawings and the like do not sometimes indicate actual positions, sizes, ranges, and the like. Therefore, the present disclosure is not limited to the positions, dimensions, ranges, and the like disclosed in the drawings and the like.
Detailed Description
Various exemplary embodiments of the present disclosure will be described in detail below with reference to the accompanying drawings. It should be noted that: the relative arrangement of the components and steps, the numerical expressions, and numerical values set forth in these embodiments do not limit the scope of the present disclosure unless specifically stated otherwise.
The following description of at least one exemplary embodiment is merely illustrative in nature and is in no way intended to limit the disclosure, its application, or uses. That is, the structures and methods herein are shown by way of example to illustrate different embodiments of the structures and methods of the present disclosure. Those skilled in the art will understand, however, that they are merely illustrative of exemplary ways in which the disclosure may be practiced and not exhaustive. Furthermore, the figures are not necessarily to scale, some features may be exaggerated to show details of particular components.
Techniques, methods, and apparatus known to those of ordinary skill in the relevant art may not be discussed in detail but are intended to be part of the specification where appropriate.
Figure 1 is a schematic diagram of an optical network topology according to an embodiment of the present disclosure. The network model of the optical cable may include nodes, which may represent telecommunication cable cross-connect (optical cross-connect) facilities, and links, which may represent optical cables connecting the respective nodes. The network model shown in fig. 1 may include nodes C, D, E, F and G. The network model shown in FIG. 1 may also include links between adjacent nodes, such as D-E between node D and node E, G-H between node G and node H, and so on.
In embodiments according to the present disclosure, the links between adjacent nodes may be bidirectional. For example, the network model shown in FIG. 1 may include links E-D and D-E for neighboring nodes D and E. Links between nodes may also be unidirectional in embodiments consistent with the present disclosure. For example, the network model shown in FIG. 1 may include only links E-D and not links D-E.
In embodiments according to the present disclosure, the link between adjacent nodes may be a single link, i.e. only one optical cable connection between two adjacent cross-connect facilities. In embodiments according to the present disclosure, the links between adjacent nodes may not be a single link, i.e., there may be multiple fiber optic cable connections between two adjacent cross-connect facilities.
The network structure of the optical communication cable may include a plurality of different segments, such as access segments and block segments. The access segment may be a portion of the fiber optic cable from the subscriber side to the office side and the block segment may be a portion of the fiber optic cable between the office stations, including portions of the fiber optic cable within a zone and portions of the fiber optic cable between different zones. The portion of the cable between the stations is also sometimes referred to in the art as a block section, where the portion of the cable within a zone is referred to as an intra-zone section and the portion of the cable between zones is referred to as a block section. The present disclosure takes the former expression that the portion of the fiber optic cable between the office stations is referred to as a block section, which may include portions of the fiber optic cable within a zone and portions of the fiber optic cable between different zones. The corresponding network structure may differ according to the type of the different segments. For example, the links in the access segment may be unidirectional, both in the direction away from the subscriber side and towards the office station; the links between adjacent nodes in the block section may be bidirectional, e.g., the link between office station a and office station B may include both a-B and B-a. Also, fiber optic cables according to embodiments of the present disclosure may include a variety of different configurations. For example, the optical cable may include: access segment only; only the segment; an access segment and a block segment; the device comprises two access sections and a section of interval section, wherein the two access sections are respectively connected to two ends of the interval section. The above listed constitutions are only examples, and the constitution scheme of the optical cable is not limited thereto.
Fig. 2 is a flow chart of a method for searching for cable routes according to an embodiment of the present disclosure.
At S201, user parameters may be acquired. The subscriber parameters may include at least an originating node and a terminating node of the cable route. In embodiments according to the present disclosure, the user parameters may also include a routing scenario, an originating facility, an ending facility, a must-pass facility, an avoidance facility, a number of cores, a number of solutions, and the like.
At S202, a parameter check may be performed. The parameter check may include checking whether the parameters introduced by the user are legal, missing, etc. If the parameter verification fails, ending the optical cable route search; if the parameter check is passed, it proceeds to S203.
At S203, a network model of the fiber optic cable may be obtained. The network model may include nodes and links between nodes.
When the network model is obtained, the network model can be processed and analyzed, and unavailable nodes and links, aggregated nodes and links and the like are removed.
In an embodiment according to the present disclosure, when obtaining a network model of an optical cable, multiple devices in the same area may be aggregated into one node. For example, the communication nodes may include an outdoor general node and an indoor node. Outdoor nodes, i.e., common outdoor boxes, such as optical network boxes, optical cross-connect boxes, etc.; the indoor nodes have the affiliation placing relationship, such as a rack, an ODF (optical distribution function), an indoor optical fiber distribution box and the like, and are stored in a local station machine room or placing points such as an outdoor installation address and the like. In the network model aggregation, indoor nodes may be aggregated into one node, and optical cables connected to the indoor nodes are all adjusted to be connected to the aggregation node. For example, if the equipment Frame001 in the office station ST1 is connected to the trunk cable Fiber001 and the equipment ODF001 is connected to the trunk cable Fiber002, it can be aggregated in the network model as a node ST1 connected to the cables Fiber001 and Fiber 002.
In embodiments according to the present disclosure, the user parameters may further include a lowest core count, and links having a core count lower than the lowest core count may be removed when obtaining the network model of the optical cable.
In embodiments according to the present disclosure, due to the non-directional nature of the cable network, the data may be placed into the model with a decision to repeat and then to place in both directions. For example, for node ST1 and node ST2, the links put into the data model may include: ST1-ST2 and ST2-ST 1.
After the network model is obtained, the network model data may be cached. For example, it may be stored in a data structure as follows:
TABLE 1 network model data Structure
Next, at S204, it may be determined whether the fiber optic cable includes a block section based on the subscriber parameter.
In an embodiment according to the present disclosure, the user parameter may further include a scene. The scene may include a normal scene including an access segment and a section segment, and an H-main light path/H-sub light path scene including only the access segment.
If the scene in the user parameter is a common scene, further judgment can be carried out according to the starting node and the ending node. For example, if both the start node and the end node in the user parameter are in the block section, the fiber optic cable includes only the block section; if the starting node and the terminating node in the user parameters are both in the access section, the optical cable comprises a section and two sections of access sections; if the starting node and the terminating node in the subscriber parameters are one in the access segment and one in the block segment, the fiber optic cable includes the block segment and a segment of the access segment.
If the scene in the user parameter is an H main optical path/H sub optical path scene, it may be determined that the optical cable only includes the access segment.
If the fiber optic cable includes a block segment, at S205, a block segment route may be obtained using a block segment algorithm. The block section algorithm will be described in detail below.
Next, at S206, it may be determined whether the optical cable includes an access segment based on the subscriber parameters.
If the optical cable does not comprise the access section, the optical cable only comprises the section, and the obtained route of the section is the optical cable route.
If the optical cable comprises an access segment, the optical cable comprises a block segment and an access segment, an access segment route is obtained by using an access segment algorithm at S210, and then splicing of the access segment route and the block segment route is carried out at S211 to obtain the optical cable route. The access segment algorithm and route splicing will be described in detail below.
If the fiber optic cable does not include a segment section, at S208, it may be determined whether the fiber optic cable includes an access segment based on the subscriber parameters. If the optical cable includes an access segment, an access segment algorithm may be utilized to obtain an access segment route at S209, where the access segment route is an optical cable route; otherwise, ending the route searching process.
After the cable route is obtained, routing node refinement may be performed at S207. If the link entering the area and the link leaving the area are respectively connected to different devices in the area, the route between the different devices in the area is obtained by using a block-segment algorithm and is spliced into the route between the starting node and the ending node. Examples of situations where routing node refinement is required may include: after the H main light path or the H sub light path returns, the target node and the light path connecting node are not in the same machine room; and in the interval search, the machine rooms connected with the incoming optical cables and the outgoing optical cables are different. Under the conditions, an optimal scheme can be searched through an algorithm according to the network structure data of the machine room in the bureau and spliced into the existing route.
1) Access segment algorithm
Because the access segment has no obvious hierarchical relation, the access segment algorithm can search the route between the initial node and the final node of the access segment by adopting a mesh node recursive divergence non-ring search algorithm.
According to the service requirement, the next node can be searched recursively from each path node on the principle that the number of the jumpers is as small as possible, whether the node is a destination node or not is judged, and the recursion is quitted when the destination node meeting the condition is reached. The check in the recursion cannot loop every path to avoid causing infinite loops.
2) Interval section algorithm
The interval algorithm is based on Yen's algorithm, and the distance weight in the original algorithm is changed to the principle of reducing the number of jumpers as much as possible.
In the structure of the network model, paths among nodes in the interval section can be bidirectional, and optimization exclusion routing is looped; the path between the nodes of the block section may have a plurality of paths; and corresponding restrictions on the nodes and links in the block section, for example, the node parameters may be restricted to "office stations" or "access points", the links may be restricted to "trunk cables", and only available cable network data may be grabbed.
In an embodiment according to the present disclosure, the user parameter may further include a number of solutions, where the number of solutions is the number of solutions of the route that the user wishes to finally obtain.
The section algorithm for calculating a route between the first node and the second node satisfying the number of schemes may include:
s1: calculating the shortest route between the first node and the second node as the current route, and adding the current route into the first route set;
s2: taking each node except the second node in the current route as an offset node, calculating the shortest route between the offset node and the second node, and splicing the shortest route with the route from the first node to the offset node in the current route to obtain the offset route;
s3: the offset routes of all nodes except the second node in the current route form a second route set, the offset route with the least number of hops in the second route set is selected as the current route, added into the first route set and removed from the second route set;
s4: repeating S2 and S3 until the number of routes in the first set of routes, which are segment routes, is greater than or equal to the number of plans.
Taking the network structure shown in fig. 1 as an example, the number of schemes in the user parameter is 10. Based on a network structure, on the principle that the number of hops is as small as possible, searching a segment route between a node C serving as a segment starting point and a node H serving as a segment ending point by using a segment algorithm can specifically include the following steps, wherein the Dijkstra algorithm is an algorithm for calculating a shortest path between two points, the cost is the number of hops, and the shortest path is a path with the minimum number of hops:
step 1, calculating by utilizing Dijkstra algorithm to obtain the shortest path A ^ 1: C-E-G-H, wherein the expense is 3, a [1] ═ C-E-G-H.
Step 2, taking A [1] as an iteration path, and performing 1 st iteration:
2.1, in a partial iteration path (A [1]) C-E-G path, taking a G point as a deviation point, setting a weight value between G-H paths to be infinite, and calculating by utilizing a Dijkstra algorithm to obtain a path A ^ 2-1: C-E-G-F-H, costing 4, adding A ^2-1 to the off-path set;
2.2, in the partial iteration path (A [1]) C-E path, taking the E point as a deviation point, setting the weight value between the E-G paths to be infinite, and calculating by utilizing a Dijkstra algorithm to obtain a path A ^ 2-2: C-E-F-H, cost 3, add A ^2-2 to the off-path set;
2.3, in the partial iteration path (A [1]) C path, taking the C point as an offset point, setting the weight value between the C-E paths to be infinite, and calculating by utilizing a Dijkstra algorithm to obtain a path A ^ 2-3: C-D-F-H, cost 3, add A ^2-3 to the off-path set;
the iteration is completed, and there are 3 paths in the deviated path set: C-E-G-F-H, C-E-F-H, C-D-F-H; and selecting the least expensive deviated path C-E-F-H, and removing the deviated path set when A [2] ═ C-E-F-H.
Step 3, taking A [2] as an iteration path, and performing 2 nd iteration:
3.1, in the partial iteration path (A2) C-E-F path, taking the F point as a deviation point, setting the weight value between the F-H paths to be infinite, and calculating by utilizing a Dijkstra algorithm to obtain a path A ^ 3-1: C-E-F-G-H, costing 4, adding A ^3-1 to the off-path set;
3.2, in the partial iteration path (A [2]) C-E path, taking the E point as the offset point, setting the weight value between the E-F, E-G paths to infinity (note that the weight values of the two paths are set here because the two paths exist in A [1] and A [2], respectively), calculating by using Dijkstra algorithm to obtain the path A ^ 3-2: C-E-D-F-H, costing 4, adding A ^3-2 to the off-path set;
3.3, in the partial iteration path (A2) C path, taking the point C as an offset point, and setting the weight value between the paths C-E to be infinite, wherein the path is subjected to iteration query, so that the query is not carried out any more;
the iteration is completed, and there are 4 paths in the deviated path set: C-E-G-F-H, C-D-F-H, C-E-F-G-H, C-E-D-F-H; and selecting the least expensive deviated path C-D-F-H, and removing the deviated path set when A [3] ═ C-D-F-H.
Step 4, taking A [3] as an iteration path, and performing 3 rd iteration:
4.1, in the partial iteration path (A3) C-D-F path, taking the F point as a deviation point, setting the weight value between the F-H paths to be infinite, and calculating by utilizing a Dijkstra algorithm to obtain a path A ^ 4-1: C-D-F-G-H, costing 4, adding A ^4-1 to the off-path set;
4.2, in the partial iteration path (A3) C-D path, taking the D point as a deviation point, setting the weight value between the D-F paths to be infinite, and calculating by utilizing a Dijkstra algorithm to obtain a path A ^ 4-2: C-D-E-G-H, costing 4, adding A ^4-2 to the off-path set;
4.3, in the partial iteration path (A3) C path, taking the C point as an offset point, setting the weight values between the C-D and C-E paths to be infinite, and having no offset path;
the iteration is completed, and 5 paths in the deviated path set are: C-E-G-F-H, C-E-F-G-H, C-E-D-F-H, C-D-F-G-H, C-D-E-G-H; and selecting the least expensive deviated path C-E-G-F-H, and removing the deviated path set, wherein A [4] ═ C-E-G-F-H.
Step 5, taking A [4] as an iteration path, and performing 4 th iteration:
5.1, in a partial iteration path (A4) C-E-G-F path, taking an F point as an offset point, setting a weight value between the F-H paths to be infinite, and avoiding an offset path;
5.2, in the partial iteration path (A4) C-E-G path, taking the G point as a deviation point, setting the weight value between the G-F paths to be infinite, and calculating by utilizing a Dijkstra algorithm to obtain a path A ^ 5-2: C-E-G-H, but the set of off-set paths already exists for that path, so there is no new off-set path;
5.3, in the partial iteration path (A4) C-E path, taking the E point as a deviation point, setting the weight values between the E-G and E-F paths to be infinite, and calculating by utilizing a Dijkstra algorithm to obtain a path A ^ 5-3: C-E-D-F-H, but the set of off-set paths already exists for that path, so there is no new off-set path;
5.4, in the partial iteration path (A4) C path, taking the point C as an offset point, setting the weight values between the paths C-E and C-D to be infinite, and having no offset path;
the iteration is completed, and there are 4 paths in the deviated path set: C-E-F-G-H, C-E-D-F-H, C-D-F-G-H, C-D-E-G-H; and selecting the least expensive deviated path C-E-D-F-H, and removing the deviated path set, wherein A [5] ═ C-E-D-F-H.
Step 6, taking A [5] as an iteration path, and performing 5 th iteration:
6.1, in the partial iteration path (A [5]) C-E-D-F path, taking the F point as a deviation point, setting the weight value between the F-H paths to be infinite, and calculating by utilizing a Dijkstra algorithm to obtain a path A ^ 6-1: C-E-D-F-G-H, costing 5, adding A ^6-1 to the off-path set;
6.2, in the partial iteration path (A5) C-E-D path, taking a D point as an offset point, setting a weight value between the D-F paths to be infinite, and avoiding an offset path;
6.3, in the partial iteration path (A5) C-E path, taking the E point as an offset point, setting the weighted values among the paths E-D, E-G and E-F to be infinite, and avoiding the offset path;
6.4, in the partial iteration path (A5) C path, taking the point C as an offset point, setting the weight values between the paths C-E and C-D to be infinite, and having no offset path;
the iteration is completed, and there are 4 paths in the deviated path set: C-E-F-G-H, C-D-F-G-H, C-D-E-G-H, C-E-D-F-G-H; and selecting the least expensive deviated path C-D-E-G-H, and removing the deviated path set, wherein A [6] ═ C-D-E-G-H.
And 7, taking A [6] as an iteration path, and performing the 6 th iteration:
7.1, in the partial iteration path (A6) C-D-E-G path, taking the G point as a deviation point, setting the weight value between G-H paths to be infinite, and calculating by utilizing a Dijkstra algorithm to obtain a path A ^ 7-1: C-D-E-G-F-H, costing 5, adding A ^7-1 to the off-path set;
7.2, in the partial iteration path (A [6]) C-D-E path, taking the E point as a deviation point, setting the weight value between the E-G paths to be infinite, and calculating by utilizing a Dijkstra algorithm to obtain a path A ^ 7-2: C-D-E-F-H, costing 4, adding A ^7-2 to the off-path set;
7.3, in the partial iteration path (A6) C-D path, taking the D point as an offset point, setting the weight values between the D-E and D-F paths to be infinite, and having no offset path;
7.4, in the partial iteration path (A6) C path, taking the point C as an offset point, setting the weight values between the paths C-E and C-D to be infinite, and having no offset path;
the iteration is completed, and 5 paths in the deviated path set are: C-E-F-G-H, C-D-F-G-H, C-E-D-F-G-H, C-D-E-G-F-H, C-D-E-F-H; and selecting the least expensive deviated path C-D-F-G-H, and removing the deviated path set when A [7] ═ C-D-F-G-H.
Step 8, taking A [7] as an iteration path, and performing 7 th iteration:
8.1, in the partial iteration path (A7) C-D-F-G path, taking a G point as an offset point, setting a weight value between G-H paths to be infinite, and avoiding an offset path;
8.2, in the partial iteration path (A7) C-D-F path, taking the F point as a deviation point, setting the weight values between the F-G and F-H paths to be infinite, and calculating by utilizing a Dijkstra algorithm to obtain a path A ^ 8-2: C-D-F-E-G-H, costing 5, adding A ^8-2 to the off-path set;
8.3, in the partial iteration path (A7) C-D path, taking the D point as a deviation point, setting the weight value between the D-F paths to be infinite, and calculating by utilizing a Dijkstra algorithm to obtain a path A ^ 8-3: C-D-E-F-H, but the set of off-set paths already exists for that path, so there is no new off-set path;
8.4, in the partial iteration path (A7) C path, taking the C point as an offset point, setting the weight values between the C-E and C-D paths to be infinite, and having no offset path;
the iteration is completed, and 5 paths in the deviated path set are: C-E-F-G-H, C-E-D-F-G-H, C-D-E-G-F-H, C-D-E-F-H, C-D-F-E-G-H; and selecting the least expensive deviated path C-E-F-G-H, and removing the deviated path set, wherein A [8] ═ C-E-F-G-H.
And 9, taking A [8] as an iteration path, and performing 8 th iteration:
9.1, in the partial iteration path (A8) C-E-F-G path, taking a G point as an offset point, setting a weight value between G-H paths to be infinite, and avoiding an offset path;
9.2, in the partial iteration path (A8) C-E-F path, taking the F point as an offset point, setting the weight values between the F-G and F-H paths to be infinite, and avoiding the offset path;
9.3, in the partial iteration path (A8) C-E path, taking the E point as an offset point, setting the weight values among the paths E-F, E-G and E-D to be infinite, and avoiding the offset path;
9.4, in the partial iteration path (A8) C path, taking the point C as an offset point, setting the weight values between the paths C-E and C-D to be infinite, and having no offset path;
the iteration is completed, and there are 4 paths in the deviated path set: C-E-D-F-G-H, C-D-E-G-F-H, C-D-E-F-H, C-D-F-E-G-H; and selecting the minimum deviation path C-D-E-F-H, wherein A [9] ═ C-D-E-F-H, and removing the deviation path set.
Step 10, taking A [9] as an iteration path, and performing 9 th iteration:
10.1, in the partial iteration path (A [9]) C-D-E-F path, taking the F point as a deviation point, setting the weight value between the F-H paths to be infinite, and calculating by utilizing a Dijkstra algorithm to obtain a path A ^ 10-1: C-D-E-F-G-H, costing 5, adding A ^10-1 to the off-path set;
10.2, in the partial iteration path (A9) C-D-E path, taking the E point as an offset point, setting the weight values between the E-F and E-G paths to be infinite, and avoiding the offset path;
10.3, in the C-D path of the partial iteration path (A9), taking a D point as an offset point, setting the weight values between the D-E and D-F paths to be infinite, and avoiding the offset path;
10.4, in the partial iteration path (A9) C path, taking the point C as an offset point, setting the weight values between the paths C-E and C-D to be infinite, and having no offset path;
the iteration is completed, and there are 4 paths in the deviated path set: C-E-D-F-G-H, C-D-E-G-F-H, C-D-F-E-G-H, C-D-E-F-G-H; and selecting the minimum deviation path C-E-D-F-G-H, wherein A [10] ═ C-E-D-F-G-H, and removing the deviation path set.
In summary, 10 paths requested by the user are obtained, including: C-E-G-H, C-E-F-H, C-D-F-H, C-E-G-F-H, C-E-D-F-H, C-D-E-G-H, C-D-F-G-H, C-E-F-G-H, C-D-E-F-H and C-E-D-F-G-H.
In an embodiment according to the present disclosure, the segment section algorithm may further include: obtaining the maximum hop count of the routes in the first route set; searching for an additional route between the first node and the second node, the additional route not being included in the first set of routes and having a hop count not greater than the maximum hop count plus one; and adding the additional route into the first route set to obtain the block section route.
Also taking the network structure shown in fig. 1 as an example, the number of schemes in the user parameter is 10, and 10 paths have been obtained in the foregoing, where the maximum number of hops is 5, then the process may further include the following steps:
and 11, after the subsequent logic has no offset path, acquiring 10 schemes of parameters, and amplifying one hop to continuously capture data in the offset path set due to optimization and modification of the algorithm.
That is, in the embodiment according to the present disclosure, other paths with a hop count not greater than 6 that are not included may also be included therein for subsequent processing and screening, that is, 13 schemes may be finally obtained, including: C-E-G-H, C-E-F-H, C-D-F-H, C-E-G-F-H, C-E-D-F-H, C-D-E-G-H, C-D-F-G-H, C-E-F-G-H, C-D-E-F-H, C-E-D-F-G-H, C-D-F-E-G-H, C-D-E-F-G-H, and C-D-E-G-F-H.
After a number of routes greater than the required number of solutions are obtained, the routes may be sorted by weight and a number of routes equal to the number of solutions may be selected according to the order of weights to obtain a final cable route.
3) Route stitching
Route splicing can be used for splicing the access segment route and the block segment route to obtain the optical cable route. This procedure can be skipped in case only the access segment is involved or the user incoming parameters are directly searched for the segment. For example, the starting node and the terminating node of the optical cable route are A, H points respectively, and the result of the access segment algorithm is: A-B, A-C, A-D, the result of the interval slice algorithm is: B-H, D-E-H, D-F-H, the spliced optical cable has the following route: A-B-H, A-D-E-H, A-D-F-H.
In an embodiment according to the present disclosure, if the optical cable includes two access segments and one block segment at both ends, a first node in the block segment algorithm is a first access node from the first access segment to the block segment, a second node in the block segment algorithm is a second access node from the block segment to the second access segment, and the method of searching for the optical cable route may further include: based on the network model, searching a route between a starting node of the optical cable and a first access node by using an access section algorithm to obtain a first access section route; based on the network model, searching a route between a second access node and a termination node by using an access segment algorithm to obtain a second access segment route; and splicing the first access section route, the interval section route and the second access section route to obtain the optical cable route.
In an embodiment according to the present disclosure, if the optical cable includes only the segment section, no splicing is required, and the method of searching for the optical cable route may include: based on a network model, on the principle that the number of hops is as small as possible, a routing between a first node and a second node is searched by using a block interval algorithm to obtain an optical cable routing, wherein the first node and the second node are respectively a starting node and a terminating node of the optical cable routing.
In an embodiment according to the present disclosure, the user parameter further includes a scenario number, and if the optical cable only includes the access segment, splicing is not required, and the method for searching for the optical cable route may include: and based on the network model, searching the route between the starting node and the terminating node by using an access segment algorithm to obtain the optical cable route meeting the scheme number.
Fig. 3 is a flow chart of a method for searching for cable routes according to an embodiment of the present disclosure. The method may comprise the steps of:
at S301, user parameters are obtained, where the user parameters include a start node and a stop node of an optical cable route;
at S302, obtaining a network model of the optical cable, the network model including nodes and links between the nodes; and
at S303, determining whether the optical cable includes a segment, according to the user parameter, the link between the nodes in the segment being bidirectional;
if the optical cable includes a block section, the method further includes, at S304: based on a network model, on the principle that the number of hops is as small as possible, a routing between a first node serving as a starting point of a segment and a second node serving as an end point of the segment is searched by using a segment algorithm to obtain a segment routing.
Fig. 4 illustrates an exemplary computing device that may be used to implement a method of searching for fiber optic cable routes according to embodiments of the present disclosure. As shown in fig. 4, computing device 400 may include one or more processors 402. The one or more processors 402 may be any kind of processor and may include, but are not limited to, one or more general purpose processors or special purpose processors (such as special purpose processing chips).
The processor 402 and/or the storage device 404 may be connected to or communicate with the bus 406 via one or more interfaces. Bus 406 may include, but is not limited to, an Industry Standard Architecture (ISA) bus, a Micro Channel Architecture (MCA) bus, an enhanced ISA (eisa) bus, a Video Electronics Standards Association (VESA) local bus, a Peripheral Component Interconnect (PCI) bus, and the like.
I/O device 408 may be any device that enables a user to interact with computing device 400. Examples of I/O devices 408 may include, but are not limited to, a keyboard, a touchpad, a mouse, a joystick or other pointing device, a microphone, a speaker, and a display.
The I/O devices 408 and/or the network interface 410 may also be communicatively coupled to the processor 402 and/or the storage device 404 via the bus 406.
Various aspects, embodiments, implementations, or features of the foregoing embodiments may be used alone or in any combination. Various aspects of the foregoing embodiments may be implemented by software, hardware, or a combination of hardware and software.
For example, the foregoing embodiments may be embodied as computer readable code on a computer readable medium. The computer readable medium is any data storage device that can store data which can thereafter be read by a computer system. Examples of a computer readable medium include read-only memory, random-access memory, CD-ROMs, DVDs, magnetic tape, hard drives, solid state drives, and optical data storage devices. The computer readable medium can also be distributed over network coupled computer systems so that the computer readable code is stored and executed in a distributed fashion.
For example, the foregoing embodiments may take the form of hardware circuitry. Hardware circuitry may include any combination of combinational logic circuitry, clocked storage devices (such as floppy disks, flip-flops, latches, etc.), finite state machines, memories such as static random access memories or embedded dynamic random access memories, custom designed circuits, programmable logic arrays, etc.
In one embodiment, a hardware circuit according to the present disclosure may be implemented by encoding and designing one or more integrated circuits in a Hardware Description Language (HDL) such as Verilog or VHDL, or by using discrete circuits in combination.
Compared with the prior art, the method and the device can realize simplified and effective modeling of the complex communication network, and realize automatic routing search of the shortest paths according to the actual optical network structure and the service scene under the topological logic of the complex communication network. The algorithm is designed and optimized according to the communication network environment in a layered mode, and the memory is calculated quickly, so that the intelligent recommendation of the quick route is realized, and the route design efficiency and the route design configuration reliability are improved remarkably.
In summary, according to a first aspect of the present disclosure, there is provided a method for searching for an optical cable route, comprising: acquiring user parameters, wherein the user parameters comprise an initial node and a termination node of an optical cable route; acquiring a network model of the optical cable, wherein the network model comprises nodes and links among the nodes; judging whether the optical cable comprises a section according to the user parameters, wherein links among nodes in the section are bidirectional; wherein if the optical cable includes a block section, the method further comprises: based on a network model, on the principle that the number of hops is as small as possible, searching a route between a first node as a starting point of a block and a second node as an end point of the block by using a block algorithm to obtain a block route, wherein if the optical cable only comprises the block, the block route is the optical cable route.
In some embodiments, the method further comprises: judging whether the optical cable comprises an access section, wherein a link between nodes in the access section is unidirectional; wherein if the optical cable includes two access segments and includes a block segment, the first node is a first access node from the first access segment to the block segment, the second node is a second access node from the block segment to the second access segment, and the method further comprises: based on the network model, searching a route between the starting node and the first access node by using an access segment algorithm to obtain a first access segment route; based on the network model, searching a route between a second access node and a termination node by using an access segment algorithm to obtain a second access segment route; and splicing the first access section route, the interval section route and the second access section route to obtain the optical cable route.
In some embodiments, the user parameters further include a number of plans, the block section algorithm including: s1: calculating the shortest route between the first node and the second node as the current route, and adding the current route into the first route set; s2: taking each node except the second node in the current route as an offset node, calculating the shortest route between the offset node and the second node, and splicing the shortest route with the route from the first node to the offset node in the current route to obtain the offset route; s3: the offset routes of all nodes except the second node in the current route form a second route set, the offset route with the least number of hops in the second route set is selected as the current route, added into the first route set and removed from the second route set; s4: repeating S2 and S3 until the number of routes in the first set of routes, which are segment routes, is greater than or equal to the number of plans.
In some embodiments, the block section algorithm further comprises: obtaining the maximum hop count of the routes in the first route set; searching for an additional route between the first node and the second node, the additional route not being included in the first set of routes and having a hop count not greater than a maximum hop count plus one; and adding the additional route into the first route set to obtain the block section route.
In some embodiments, the method further comprises: and sorting the routes between the starting node and the terminating node according to the weights, and selecting the routes with the number equal to the scheme number according to the weight sequence to obtain the optical cable routes.
In some embodiments, the user parameters further include a scenario number, and if the optical cable includes only an access segment, the method further includes: and based on the network model, searching the route between the starting node and the terminating node by using an access segment algorithm to obtain the optical cable route meeting the scheme number.
In some embodiments, the access segment algorithm includes recursively searching access segment routes.
In some embodiments, when obtaining the network model of the optical cable, aggregating a plurality of devices in the same area into one node; and if the link entering the area and the link leaving the area are respectively connected to different devices in the area, obtaining the route between the different devices in the area by using a block-section algorithm, and splicing the route between the starting node and the ending node.
In some embodiments, the user parameters further include a lowest core count, and links having a core count lower than the lowest core count are removed when obtaining the network model of the fiber optic cable.
In some embodiments, there are multiple links between adjacent nodes.
According to a second aspect of the present disclosure, there is provided a non-transitory computer readable storage medium for searching for optical cable routes, having a program stored thereon, which when executed by a computer, causes the computer to perform the method according to the first aspect of the present disclosure.
According to a third aspect of the present disclosure, there is provided a computing device for searching for optical cable routes, comprising a memory communicatively coupled to a processor and a processor, the memory having stored therein a program which, when executed by the processor, causes the processor to perform the method according to the first aspect of the present disclosure.
According to a fourth aspect of the present disclosure, there is provided an apparatus for searching for optical cable routes, comprising means for performing the method according to the first aspect of the present disclosure.
While some specific embodiments of the present disclosure have been shown in detail by way of example, it should be understood by those skilled in the art that the foregoing examples are intended to be illustrative only and are not limiting upon the scope of the present disclosure. It should be appreciated that some of the steps of the foregoing methods need not be performed in the order illustrated, but rather they may be performed simultaneously, in a different order, or in an overlapping manner. In addition, one skilled in the art may add some steps or omit some steps as desired. Some of the components in the foregoing systems need not be arranged as shown, and those skilled in the art may add or omit some components as desired. It will be appreciated by those skilled in the art that the above-described embodiments may be modified without departing from the scope and spirit of the disclosure. The scope of the present disclosure is defined by the appended claims.
Claims (13)
1. A method for searching fiber optic cable routes, comprising:
acquiring user parameters, wherein the user parameters comprise a starting node and a terminating node of an optical cable route;
acquiring a network model of the optical cable, wherein the network model comprises nodes and links among the nodes; and
judging whether the optical cable comprises a block section or not according to user parameters, wherein links among nodes in the block section are bidirectional;
wherein if the fiber optic cable includes a block section, the method further comprises:
based on the network model, on the principle of reducing the number of hops as much as possible, searching the route between a first node as the starting point of the interval and a second node as the ending point of the interval by using an interval algorithm to obtain the interval route,
wherein if the optical cable includes only the block section, the block section route is an optical cable route.
2. The method of claim 1, further comprising:
judging whether the optical cable comprises an access section, wherein links among nodes in the access section are unidirectional;
wherein if the fiber optic cable includes two access segments and includes a block segment, the first node is a first access node from the first access segment to the block segment, the second node is a second access node from the block segment to the second access segment, and the method further comprises:
based on the network model, searching a route between the starting node and the first access node by using an access segment algorithm to obtain a first access segment route;
based on the network model, searching a route between a second access node and a termination node by using an access segment algorithm to obtain a second access segment route; and
and splicing the first access section route, the interval section route and the second access section route to obtain the optical cable route.
3. The method of claim 1 or 2, wherein the user parameters further include a number of scenarios, the block section algorithm comprising:
s1: calculating the shortest route between the first node and the second node as the current route, and adding the current route into the first route set;
s2: taking each node except the second node in the current route as an offset node, calculating the shortest route between the offset node and the second node, and splicing the shortest route with the route from the first node to the offset node in the current route to obtain the offset route;
s3: the offset routes of all nodes except the second node in the current route form a second route set, the offset route with the least number of hops in the second route set is selected as the current route, added into the first route set and removed from the second route set;
s4: repeating S2 and S3 until the number of routes in the first set of routes is greater than or equal to the scheme number, the routes in the first set of routes being block segment routes.
4. The method of claim 3, wherein the block section algorithm further comprises:
obtaining the maximum hop count of the routes in the first route set;
searching for an additional route between the first node and the second node, the additional route not being included in the first set of routes and having a hop count not greater than the maximum hop count plus one; and
and adding the additional route into the first route set to obtain the block section route.
5. The method of claim 4, further comprising:
and sorting the routes between the starting node and the terminating node according to the weights, and selecting the routes with the number equal to the scheme number according to the weight sequence to obtain the optical cable routes.
6. The method of claim 2, wherein the user parameters further include a scenario number, and if the fiber optic cable includes only an access segment, the method further comprises:
and based on the network model, searching the route between the starting node and the terminating node by using an access segment algorithm to obtain the optical cable route meeting the scheme number.
7. The method of claim 2 or 6, wherein the access segment algorithm comprises a recursive search access segment route.
8. The method of claim 1, 2 or 6, wherein, in obtaining the network model of the optical cable, a plurality of devices in the same area are aggregated into one node; and
if the link entering the area and the link leaving the area are respectively connected to different devices in the area, the route between the different devices in the area is obtained by using a block-segment algorithm and is spliced into the route between the starting node and the ending node.
9. The method of claim 1, 2 or 6, wherein the user parameters further comprise a lowest core count, and links with a core count lower than the lowest core count are removed when obtaining the network model of the optical cable.
10. The method of claim 1, wherein there are multiple links between adjacent nodes.
11. A non-transitory computer-readable storage medium for searching for optical cable routes, having a program stored thereon, which when executed by a computer, causes the computer to perform the method according to any one of claims 1 to 10.
12. A computing device for searching for optical cable routes, comprising a memory communicatively coupled with the processor and a processor, the memory having stored therein a program that, when executed by the processor, causes the processor to perform the method of any of claims 1 to 10.
13. An apparatus for searching for fiber optic cable routes, comprising means for performing the method of any of claims 1-10.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202011009146.4A CN114301827B (en) | 2020-09-23 | 2020-09-23 | Method and apparatus for searching for optical cable routes |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202011009146.4A CN114301827B (en) | 2020-09-23 | 2020-09-23 | Method and apparatus for searching for optical cable routes |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN114301827A true CN114301827A (en) | 2022-04-08 |
| CN114301827B CN114301827B (en) | 2023-07-18 |
Family
ID=80964100
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202011009146.4A Active CN114301827B (en) | 2020-09-23 | 2020-09-23 | Method and apparatus for searching for optical cable routes |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN114301827B (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN119697097A (en) * | 2024-12-11 | 2025-03-25 | 国家电网有限公司信息通信分公司 | Routing path acquisition method and device |
Citations (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1943784A1 (en) * | 2005-08-08 | 2008-07-16 | Pirelli & C. S.p.A. | Method for configuring an optical network |
| CN107248952A (en) * | 2017-07-24 | 2017-10-13 | 华信咨询设计研究院有限公司 | A kind of business substitutes route determining methods and system |
| US20180309659A1 (en) * | 2017-04-21 | 2018-10-25 | Mediatek Inc. | Symmetric route establishment with bidirectional links for wireless mesh networks |
| US20180343191A1 (en) * | 2017-05-25 | 2018-11-29 | Fang Hao | Hop constrained widest path for segment routing |
| CN109194577A (en) * | 2018-10-23 | 2019-01-11 | 清华大学 | A kind of traffic engineering method and device of the Segment routing network based on partial deployment |
| CN110932973A (en) * | 2018-09-19 | 2020-03-27 | 中国移动通信集团广东有限公司 | A kind of optimal route calculation method and device for optical cable network point-to-point |
| CN111464888A (en) * | 2020-03-13 | 2020-07-28 | 深圳市前海信息通信发展有限公司 | High-efficiency communication network light path scheduling method |
| CN111683010A (en) * | 2020-05-26 | 2020-09-18 | 广东省电信规划设计院有限公司 | Method and device for generating dual routing based on optical cable network optical path |
-
2020
- 2020-09-23 CN CN202011009146.4A patent/CN114301827B/en active Active
Patent Citations (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1943784A1 (en) * | 2005-08-08 | 2008-07-16 | Pirelli & C. S.p.A. | Method for configuring an optical network |
| US20180309659A1 (en) * | 2017-04-21 | 2018-10-25 | Mediatek Inc. | Symmetric route establishment with bidirectional links for wireless mesh networks |
| US20180343191A1 (en) * | 2017-05-25 | 2018-11-29 | Fang Hao | Hop constrained widest path for segment routing |
| CN107248952A (en) * | 2017-07-24 | 2017-10-13 | 华信咨询设计研究院有限公司 | A kind of business substitutes route determining methods and system |
| CN110932973A (en) * | 2018-09-19 | 2020-03-27 | 中国移动通信集团广东有限公司 | A kind of optimal route calculation method and device for optical cable network point-to-point |
| CN109194577A (en) * | 2018-10-23 | 2019-01-11 | 清华大学 | A kind of traffic engineering method and device of the Segment routing network based on partial deployment |
| CN111464888A (en) * | 2020-03-13 | 2020-07-28 | 深圳市前海信息通信发展有限公司 | High-efficiency communication network light path scheduling method |
| CN111683010A (en) * | 2020-05-26 | 2020-09-18 | 广东省电信规划设计院有限公司 | Method and device for generating dual routing based on optical cable network optical path |
Non-Patent Citations (2)
| Title |
|---|
| 王璇;: "基于GIS的光接安全入网主干光缆路由优化模型和算法研究", 网络安全技术与应用 * |
| 陈若宾;王兴伟;马连博;黄敏;: "绿色主干网络中一种高效的节能路由算法", 计算机学报 * |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN119697097A (en) * | 2024-12-11 | 2025-03-25 | 国家电网有限公司信息通信分公司 | Routing path acquisition method and device |
Also Published As
| Publication number | Publication date |
|---|---|
| CN114301827B (en) | 2023-07-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US8027260B2 (en) | Mixed integer programming model for minimizing leased access network costs | |
| US5233604A (en) | Methods and apparatus for optimum path selection in packet transmission networks | |
| JP2002199005A (en) | Method for designing interconnect fabric | |
| Tsai et al. | An adaptive hierarchical routing protocol | |
| CN114301793B (en) | Path generation method and device in optical transmission network | |
| CN107196858A (en) | A kind of k solving the shortest path methods for considering polymorphic type constraint | |
| CN113193996B (en) | Power optical transmission network optimization method, device, equipment and storage medium | |
| CN1167554A (en) | Routing in Communication Networks | |
| CN109194468A (en) | Dispositions method, device and the equipment of relay node, computer readable storage medium | |
| CN118612140B (en) | Data transmission method, apparatus, computer device, storage medium and program product | |
| CN106533966A (en) | Network service resource arranging method and apparatus | |
| CN113872784A (en) | Network configuration verification method and device | |
| US7308494B1 (en) | Reprovisioning technique for an interconnect fabric design | |
| CN113747277A (en) | Path determination method and device | |
| CN114301827A (en) | Method and apparatus for searching optical cable route | |
| CN109639578B (en) | Method and device for selecting virtual network function | |
| CN115499861A (en) | Service same-route detection method, device, equipment and storage medium | |
| CN113794600B (en) | Method and device for searching transmission circuit route | |
| CN117493638A (en) | Node clustering method and device, electronic equipment and storage medium | |
| CN104753795B (en) | A kind of random network topology structure generation method and device | |
| CN114338427A (en) | Network hidden danger analysis method and device, electronic equipment and storage medium | |
| US9785738B1 (en) | System and method for evaluating spanning trees | |
| CN119697090B (en) | A method, apparatus, electronic device, and storage medium for determining the shortest path. | |
| CN105634943B (en) | Route computing method and device | |
| CN102143089B (en) | Routing method and routing device for multilevel transport network |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |