CN114301827B - Method and apparatus for searching for optical cable routes - Google Patents
Method and apparatus for searching for optical cable routes Download PDFInfo
- Publication number
- CN114301827B CN114301827B CN202011009146.4A CN202011009146A CN114301827B CN 114301827 B CN114301827 B CN 114301827B CN 202011009146 A CN202011009146 A CN 202011009146A CN 114301827 B CN114301827 B CN 114301827B
- Authority
- CN
- China
- Prior art keywords
- route
- node
- section
- 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.)
- Active
Links
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The present disclosure provides a method and apparatus for searching for a fiber optic cable route. The method comprises the following steps: 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 an optical cable, wherein the network model comprises nodes and links between the nodes; judging whether the optical cable comprises a section according to the user parameters, wherein links between nodes in the section are bidirectional; wherein if the fiber optic cable includes a span, the method further comprises: based on a network model, searching a route between a first node serving as a section starting point and a second node serving as a section ending point by using a section algorithm on the principle that the number of hops is as small as possible so as to obtain a section route, wherein if the optical cable only comprises a section, the section route is the optical cable route.
Description
Technical Field
The present disclosure relates to the field of communications network computer management (IT) technology, and in particular, to a method and apparatus for searching for optical cable routes.
Background
The optical cable network structure and connection of the communication carrier are extremely complex and even more complex than the traffic road network. In the dispatching and reasonable utilization of the light path service resources, how to quickly and reasonably configure the light path route, the safe and efficient opening of the service route is realized, and the method has great influence on the construction optimization of an internal network and the opening of government and enterprise services. This is also one of the core technical difficulties to be solved in the automatic service opening.
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 personnel skills and network familiarity are extremely high. And, the routing design of manual operation lacks automatic inquiry means to judge whether the optical fiber resource can reach the service site, and lacks effective management to the utilization efficiency of the fiber core resource. These problems may lead to problems of low scheduling efficiency, repeated network construction, inconsistent network and resource system data, etc.
On the other hand, the existing optical path route searching technology uses breadth-first, depth-first and shortest path searching algorithms, and the searching algorithms have the defects of inconsistent actual optical network structure and service scene, low searching efficiency and the like.
Accordingly, 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 a cable route, 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 an optical cable, wherein the network model comprises nodes and links between the nodes; judging whether the optical cable comprises a section according to the user parameters, wherein links between nodes in the section are bidirectional; wherein if the fiber optic cable includes a span, the method further comprises: based on a network model, searching a route between a first node serving as a section start point and a second node serving as a section end point by using a section algorithm on the principle that the number of hops is as small as possible so as to obtain a section route, wherein if the optical cable only comprises a section, the section 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 stored thereon a program 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 routing, comprising a memory and a processor, the memory being communicatively coupled to the processor, the memory having stored therein a program which, when executed by the processor, causes the processor to perform a 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 a cable routing, comprising means for performing the method according to the first aspect of the present disclosure.
The method and the device can realize a plurality of shortest path automation algorithm schemes, the algorithm can rapidly and accurately calculate a plurality of optimal paths, the efficiency of route design and the reliability of route design configuration are obviously improved, and the problem of searching the inter-office optical path route is solved.
Other features of the present disclosure and its advantages will become more apparent from the following detailed description of exemplary embodiments of the disclosure, 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 disclosure will be understood more clearly from the following detailed description, with reference to the accompanying drawings,
wherein:
fig. 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 fiber optic cable routes according to an embodiment of the present disclosure.
Fig. 3 is a flow chart of a method for searching for fiber optic 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 ease of understanding, the positions, dimensions, ranges, etc. of the respective structures shown in the drawings and the like may not represent actual positions, dimensions, ranges, etc. Accordingly, the present disclosure is not limited to the disclosed positions, dimensions, ranges, etc. as illustrated in the accompanying drawings.
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, numerical expressions and numerical values set forth in these embodiments do not limit the scope of the present disclosure unless it is 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 in this disclosure. However, those skilled in the art will appreciate that they are merely illustrative of the exemplary ways in which the disclosure may be practiced, and not exhaustive. Moreover, the figures are not necessarily to scale, some features may be exaggerated to show details of particular components.
Techniques, methods, and apparatus known to one of ordinary skill in the relevant art may not be discussed in detail, but should be considered part of the specification where appropriate.
Fig. 1 is a schematic diagram of an optical network topology according to an embodiment of the present disclosure. The network model of the fiber optic cable may include nodes, which may represent communication cable cross-over (optical cross-over) facilities, and links, which may represent fiber optic 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, links between neighboring nodes may be bi-directional. For example, the network model shown in FIG. 1 may include links E-D and D-E for adjacent nodes D and E. In embodiments according to the present disclosure, the links between nodes may also be unidirectional. 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 fiber optic cable connection between two adjacent handover 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 handover facilities.
The network structure of the communication cable may comprise a plurality of different segments, such as an access segment and an interval segment. The access section may be a portion of the optical cable from the subscriber side to the office side, and the interval section may be a portion of the optical cable between the office stations, including a portion of the optical cable within an area and a portion of the optical cable between different areas. The portions of the cable between the stations are sometimes referred to in the art as interoffice segments, with the portions of the cable within the zones being referred to as intra-zone segments and the portions of the cable between the zones being referred to as inter-zone segments. The present disclosure takes the former statement that the portion of the fiber optic cable between the office stations is referred to as a block, which may include the portion of the fiber optic cable within an area and the portion of the fiber optic cable between different areas. The corresponding network structure may be different depending on the type of the different segments. For example, links in the access segment may be unidirectional, the links all being in a direction away from the user side and toward the office station; links between adjacent nodes in the interval segment may be bidirectional, e.g., links between station ase:Sub>A and station B may include both ase:Sub>A-B and B-ase:Sub>A. Also, fiber optic cables according to embodiments of the present disclosure may include a variety of different configurations. For example, the fiber optic cable may include: only the access segment; only interval sections; an access section and an interval section; two access sections and a section, wherein, two access sections are connected at the both ends of section respectively. The above listed configurations are merely examples, and the configuration scheme of the optical cable is not limited thereto.
Fig. 2 is a flow chart of a method for searching for fiber optic cable routes according to an embodiment of the present disclosure.
At S201, user parameters may be acquired. The user parameters may include at least a start node and a termination node of the cable route. In embodiments according to the present disclosure, the user parameters may also include route design scenarios, start-up facilities, end-stop facilities, must-via facilities, avoidance facilities, core numbers, plan numbers, and the like.
At S202, a parameter check may be performed. Parameter verification may include verifying whether a parameter entered by a user is legitimate, missing, etc. If the parameter check is not passed, ending the optical cable route search; if the parameter check passes, it proceeds to S203.
At S203, a network model of the fiber optic cable may be acquired. The network model may include nodes and links between nodes.
When the network model is acquired, the network model can be processed and analyzed to remove unavailable nodes and links, aggregate nodes and links, and the like.
In embodiments according to the present disclosure, multiple devices within the same area may be aggregated into one node when obtaining a network model of a fiber optic cable. For example, the communication nodes may include an outdoor general node and an indoor node. The outdoor nodes are common outdoor boxes, such as an optical network box, an optical distribution box and the like; the indoor nodes have attribution placement relations, such as a rack, an ODF, an indoor optical fiber distribution box and the like, and are stored in a machine room of a local station or in placement points such as an outdoor installation address. In performing network model aggregation, indoor nodes may be aggregated to one node, and the fiber optic cables connected to the indoor nodes are all tuned to connect to the aggregated node. For example, if the device Frame001 in the office station ST1 is connected to the Fiber001 of the relay optical cable, and the device ODF001 is connected to the Fiber002 of the relay optical cable, it may be aggregated in the network model that the node ST1 is connected to the Fiber001 and the Fiber002 of the relay optical cable.
In embodiments according to the present disclosure, the user parameters may also include a minimum number of cores, and links having a number of cores below the minimum number of cores may be removed when obtaining the network model of the fiber optic cable.
In embodiments according to the present disclosure, duplication may be judged first and then put bi-directionally when data is put into the model due to the anisotropy of the fiber optic cable network. For example, for nodes ST1 and ST2, the links put into the data model may include: ST1-ST2 and ST2-ST1.
After the network model is acquired, the network model data may be cached. For example, it may be stored in the following data structure:
table 1 network model data structure
Next, at S204, it may be determined whether the optical cable includes a section based on the user parameters.
In embodiments according to the present disclosure, the user parameters may also include a scenario. The scenes may include a normal scene including an access section and an interval section and an H main optical path/H sub optical path scene including only the access section.
If the scene in the user parameters is a common scene, further judgment can be performed according to the starting node and the ending node. For example, if the start node and the end node in the user parameter are both in a span, the fiber optic cable includes only the span; if the starting node and the ending node in the user parameters are both in the access section, the optical cable comprises an interval section and two access sections; if the originating node and the terminating node in the user parameters are one in the access segment and one in the span segment, the fiber optic cable includes the span segment and a segment of the access segment.
If the scene in the user parameter is the H main light path/H sub light path scene, the optical cable can be judged to only comprise the access section.
If the fiber optic cable includes a span, then at S205 a span route may be obtained using a span algorithm. The interval algorithm will be described in detail below.
Next, at S206, it may be determined whether the fiber optic cable includes an access segment based on the user parameters.
If the optical cable does not comprise the access section, the optical cable only comprises the section, and the obtained section route is the optical cable route.
If the cable includes an access segment, the cable includes a section segment and an access segment, the access segment route is obtained using an access segment algorithm at S210, and then splicing of the access segment route and the section segment route is performed at S211 to obtain the cable route. The access segment algorithm and route concatenation will be described in more detail below.
If the fiber optic cable does not include a span segment, at S208, a determination may be made as to whether the fiber optic cable includes an access segment based on the user parameters. If the optical cable includes an access segment, the access segment route can be obtained by using an access segment algorithm at S209, where the access segment route is the optical cable route; otherwise, the route searching process is ended.
After the cable routing is obtained, at S207, routing node refinement may be performed. If the links entering the area and the links leaving the area are respectively connected to different devices in the area, the routes among the different devices in the area are obtained by using an interval algorithm and spliced into the routes between the starting node and the ending node. Examples of situations where route node refinement is required may include: after the H main optical path or the H sub optical path is returned to the office, the target node and the optical path connecting node are not in the same machine room; and in the section search, the machine room to which the incoming and outgoing optical cables are connected is different. Under these circumstances, an optimal scheme can be searched by an algorithm according to the network structure data of the machine room in the office, and spliced into the existing route.
1) Access segment algorithm
Because the access segment has no obvious hierarchical relationship, the access segment algorithm can adopt a mesh node recursion divergence non-looping search algorithm to search the route between the start node and the end node of the access segment.
According to the service requirement, the next node is searched recursively from each path node by taking the hop number as small as possible, whether the next node is a destination node is judged, and the recursion is exited when the destination node meeting the condition is reached. Each path is verified in the recursion not being looped to avoid creating infinite loops.
2) Interval segment algorithm
The interval algorithm is based on the Yen's algorithm, and the distance weight in the original algorithm is changed into the principle that the number of hops is as small as possible.
In the structure of the network model, paths between nodes of the interval section can be bidirectional, and the optimization exclusion route is looped; multiple paths may exist for paths between nodes of an interval segment; and, corresponding restrictions are placed on the nodes and links of the interval, for example, the node parameters may be restricted to "office stations" or "access points", the links may be restricted to "relay cables", and only the available cable network data may be grasped.
In an embodiment according to the present disclosure, the user parameter may further include a number of schemes, that is, a number of schemes of a route that the user wants to finally acquire.
The interval section algorithm for calculating the route between the first node and the second node satisfying the number of schemes may include:
s1: calculating a shortest route between the first node and the second node as a current route and joining 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 between the first node in the current route and the offset node to obtain an offset route;
s3: offset routes of all nodes except the second node in the current route form a second route set, and 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 route set is greater than or equal to the scheme number, wherein the routes in the first route set are interval section routes.
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, searching for a section route between a node C serving as a section start point and a node H serving as a section end point by using a section algorithm based on the principle of the minimum number of hops, wherein the Dijkstra algorithm is an algorithm for calculating the shortest path between the two points, the cost is the number of hops, and the shortest path is the path with the minimum number of hops:
Step 1, calculating to obtain a shortest path A≡1 by using Dijkstra algorithm: C-E-G-H, wherein, the cost is 3, A1 = C-E-G-H.
Step 2, taking A1 as an iteration path, and carrying out the 1 st iteration:
2.1, in the partial iterative path (A1) C-E-G path, using G point as offset point, setting the weight value between G-H paths as infinity, and calculating to obtain path A2-1 by Dijkstra algorithm: C-E-G-F-H, spending 4, adding A2-1 to the set of offset paths;
2.2, in the partial iterative path (A1) C-E path, E point is used as offset point, the weight value between E-G paths is set to infinity, and the path A2-2 is calculated by Dijkstra algorithm: C-E-F-H, spending 3, adding A2-2 to the set of offset paths;
2.3, in the partial iterative path (A1) C path, C point is used as offset point, the weight value between C-E paths is set to infinity, and the path A2-3 is calculated by Dijkstra algorithm: C-D-F-H, spending 3, adding A2-3 to the set of offset paths;
the iteration is completed, and 3 paths exist in the offset path set: C-E-G-F-H, C-E-F-H, C-D-F-H; the least expensive off-set path C-E-F-H is selected, A < 2 > = C-E-F-H, and the off-set path set is shifted out.
Step 3, taking A2 as iteration path, and carrying out the 2 nd iteration:
3.1, in the partial iterative path (A2) C-E-F path, F point is used as offset point, the weight value between F-H paths is set to infinity, and the path A≡3-1 is calculated by Dijkstra algorithm: C-E-F-G-H, spending 4, adding A3-1 to the set of offset paths;
3.2, in the partial iterative path (A2) C-E path, the E point is used as the offset point, the weight value between E-F, E-G paths is set to infinity (note that the weight values of two paths are set here because the two paths exist in A1 and A2 respectively), and the path A [ 3-2 ] is calculated by using Dijkstra algorithm: C-E-D-F-H, spending 4, adding A3-2 to the set of offset paths;
3.3, in the partial iterative path (A2) C path, using C point as offset point, setting the weight value between C-E paths as infinity, and making said path implement iterative inquiry so as to make no inquiry;
the iteration is completed, and 4 paths exist in the offset path set: C-E-G-F-H, C-D-F-H, C-E-F-G-H, C-E-D-F-H; the least expensive off-set path C-D-F-H is selected, A [3] = C-D-F-H, and the off-set path set is shifted out.
And 4, taking A3 as an iteration path, and carrying out the 3 rd iteration:
4.1, in the partial iterative path (A3) C-D-F path, F point is used as offset point, the weight value between F-H paths is set to infinity, and the path A≡4-1 is calculated by Dijkstra algorithm: C-D-F-G-H, spending 4, adding A4-1 to the set of offset paths;
4.2, in the partial iterative path (A3) C-D path, D point is used as offset point, the weight value between D-F paths is set to infinity, and the path A≡4-2 is calculated by Dijkstra algorithm: C-D-E-G-H, spending 4, adding A-4-2 to the set of offset paths;
4.3, using C point as offset point in partial iterative path (A3) C path, setting the weight value between C-D and C-E paths as infinity, and no offset path exists;
the iteration is completed, and 5 paths exist in the offset path set: 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; the least expensive offset path C-E-G-F-H, A [4] = C-E-G-F-H, is selected, and the offset path set is shifted out.
Step 5, taking A4 as an iteration path, and carrying out the 4 th iteration:
5.1, in the partial iterative path (A4) C-E-G-F path, F point is used as offset point, the weight value between F-H paths is set to infinity, and no offset path exists;
5.2, in the partial iterative path (A4) C-E-G path, using G point as offset point, setting the weight value between G-F paths as infinity, using Dijkstra algorithm to calculate path A≡5-2: C-E-G-H, but the offset path set already has the path, so there is no new offset path;
5.3, in the partial iterative path (A4) C-E path, E point is used as offset point, the weight value between E-G, E-F paths is set to infinity, and the path A≡5-3 is calculated by Dijkstra algorithm: C-E-D-F-H, but the offset path set already has the path, so there is no new offset path;
5.4, using C point as offset point in partial iterative path (A4) C path, setting the weight value between C-E and C-D paths as infinity, and no offset path exists;
the iteration is completed, and 4 paths exist in the offset path set: C-E-F-G-H, C-E-D-F-H, C-D-F-G-H, C-D-E-G-H; the least expensive offset path C-E-D-F-H, A [5] = C-E-D-F-H, is selected, and the offset path set is shifted out.
And step 6, taking A5 as an iteration path, and carrying out the 5 th iteration:
6.1, in the partial iterative path (A5) C-E-D-F path, F point is used as offset point, the weight value between F-H paths is set to infinity, and the path A-6-1 is calculated by Dijkstra algorithm: C-E-D-F-G-H, spending 5, adding A-6-1 to the set of offset paths;
6.2, in the partial iterative path (A5) C-E-D path, using D point as offset point, setting the weight value between D-F paths as infinity, and no offset path exists;
6.3, in the partial iterative path (A5) C-E path, using E point as offset point, setting the weight value between E-D, E-G and E-F paths as infinity, and no offset path exists;
6.4, using C point as offset point in partial iterative path (A5) C path, setting the weight value between C-E and C-D paths as infinity, and no offset path exists;
the iteration is completed, and 4 paths exist in the offset path set: C-E-F-G-H, C-D-F-G-H, C-D-E-G-H, C-E-D-F-G-H; the least expensive offset path C-D-E-G-H, A [6] = C-D-E-G-H, is selected, and the offset path set is shifted out.
And 7, taking A6 as an iteration path, and carrying out the 6 th iteration:
7.1, in the partial iterative path (A6) C-D-E-G path, using G point as offset point, setting the weight value between G-H paths as infinity, using Dijkstra algorithm to calculate and obtain path A7-1: C-D-E-G-F-H, spending 5, adding A7-1 to the set of offset paths;
7.2, in the partial iterative path (A6) C-D-E path, E point is used as offset point, the weight value between E-G paths is set to infinity, and the path A7-2 is calculated by Dijkstra algorithm: C-D-E-F-H, spending 4, adding A7-2 to the set of offset paths;
7.3, using D point as offset point in partial iterative path (A6) C-D path, setting the weight value between D-E and D-F paths as infinity, and no offset path exists;
7.4, in the partial iterative path (A6) C path, using C point as offset point, setting the weight value between C-E and C-D paths as infinity, and no offset path exists;
the iteration is completed, and 5 paths exist in the offset path set: 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; the least expensive offset path C-D-F-G-H, A [7] = C-D-F-G-H, is selected, and the offset path set is shifted out.
Step 8, taking A7 as an iteration path, and carrying out the 7 th iteration:
8.1, in the partial iterative path (A7) C-D-F-G path, using G point as offset point, setting the weight value between G-H paths as infinity, and no offset path exists;
8.2, in the partial iterative path (A7) C-D-F path, F point is used as offset point, the weight value between F-G and F-H paths is set as infinity, and the path A-8-2 is calculated by Dijkstra algorithm: C-D-F-E-G-H, spending 5, adding A≡8-2 to the off-path set;
8.3, in the partial iterative path (A7) C-D path, D point is used as offset point, the weight value between D-F paths is set to infinity, and the path A≡8-3 is calculated by Dijkstra algorithm: C-D-E-F-H, but the offset path set already has the path, so there is no new offset path;
8.4, using C point as offset point in partial iterative path (A7) C path, setting the weight value between C-E and C-D paths as infinity, and no offset path exists;
the iteration is completed, and 5 paths exist in the offset path set: 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; the least expensive offset path C-E-F-G-H, A [8] = C-E-F-G-H, is selected, and the offset path set is shifted out.
Step 9, taking A8 as an iteration path, and carrying out the 8 th iteration:
9.1, in the partial iterative path (A8) C-E-F-G path, using G point as offset point, setting the weight value between G-H paths as infinity, and no offset path exists;
9.2, in the partial iterative path (A8) C-E-F path, using F point as offset point, setting the weight value between F-G and F-H paths as infinity, and no offset path exists;
9.3, in the partial iterative path (A8) C-E path, using E point as offset point, setting the weight value between E-F, E-G and E-D paths as infinity, and no offset path exists;
9.4, in the partial iterative path (A8) C path, using C point as offset point, setting the weight value between C-E and C-D paths as infinity, and no offset path exists;
The iteration is completed, and 4 paths exist in the offset 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; the minimum deviation path C-D-E-F-H, A [9] = C-D-E-F-H, is selected, and the deviation path set is removed.
Step 10, taking A9 as an iteration path, and carrying out the 9 th iteration:
10.1, in the partial iterative path (A9) C-D-E-F path, F point is used as offset point, the weight value between F-H paths is set to infinity, and the path A10-1 is calculated by Dijkstra algorithm: C-D-E-F-G-H, spending 5, adding A10-1 to the set of offset paths;
10.2, in the partial iterative path (A9) C-D-E path, E point is used as offset point, the weight value between E-F and E-G paths is set to infinity, and no offset path exists;
10.3, in the partial iterative path (A9) C-D path, D point is used as offset point, the weight value between D-E and D-F paths is set to infinity, and no offset path exists;
10.4, in the partial iterative path (A9) C path, taking C point as offset point, setting the weight value between C-E and C-D paths as infinity, and no offset path exists;
the iteration is completed, and 4 paths exist in the offset 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; the minimum deviation path C-E-D-F-G-H, A [10] = C-E-D-F-G-H, is selected, and the deviation path set is removed.
In summary, 10 paths required 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 interval 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 route set and the number of hops of the additional route being not greater than the maximum number of hops plus one; the additional route is added to the first route set to obtain the interval 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 above, where the maximum number of hops is 5, the process may further include the following steps:
and 11, after the follow-up logic has no offset path and 10 schemes of parameters are acquired, amplifying one hop to continuously grasp data in the offset path set due to optimization and modification of an algorithm.
That is, in the embodiment according to the present disclosure, other paths not including a hop count of no more than 6 may be also included 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 obtaining a number of routes greater than the number of schemes required, the routes may be ordered by weight and a number of routes equal to the number of schemes selected according to the order of weights to obtain the final cable route.
3) Route concatenation
The route splicing can be used for splicing the access section route and the interval section route to obtain the optical cable route. This procedure may be skipped in case the section search is performed directly with access section only or user incoming parameters. For example, the starting node and the ending node of the optical cable route are A, H two points respectively, and the result of the access segment algorithm is: A-B, A-C, A-D, the result of the interval algorithm is: B-H, D-E-H, D-F-H, the spliced optical cable route is as follows: three schemes 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 section segment at both ends, a first node in the section algorithm is a first access node from the first access segment to the section segment, a second node in the section algorithm is a second access node from the section segment to the second access segment, and the method of searching for an optical cable route may further include: searching a route between an initial node and a first access node of the optical cable by using an access segment algorithm based on a network model to obtain a first access segment route; searching a route between a second access node and a termination node by using an access segment algorithm based on the network model 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 a section, no splicing is required, and the method of searching for an optical cable route may include: based on a network model, searching a route between a first node and a second node by using a section algorithm based on the principle of the minimum number of hops to obtain an optical cable route, wherein the first node and the second node are respectively a starting node and a terminating node of the optical cable route.
In an embodiment according to the present disclosure, the user parameters further include a scenario number, if the optical cable includes only an access segment, no splicing is required, and the method of searching for an optical cable route may include: based on the network model, searching the route between the starting node and the ending node by using an access segment algorithm to obtain the optical cable route meeting the number of schemes.
Fig. 3 is a flow chart of a method for searching for fiber optic cable routes according to an embodiment of the present disclosure. The method may comprise the steps of:
at S301, obtaining user parameters including a start node and a termination node of an optical cable route;
at S302, a network model of the fiber optic cable is acquired, the network model comprising nodes and links between the nodes; and
at S303, determining, based on the user parameters, whether the optical cable includes a section in which links between nodes are bidirectional;
If the fiber optic cable includes a span, the method further includes, at S304: based on a network model, searching a route between a first node serving as a section start point and a second node serving as a section end point by using a section algorithm on the principle that the number of hops is as small as possible so as to obtain a section route.
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).
Computing device 400 may also include or be connected to a non-transitory storage device 404, which non-transitory storage device 404 may be any storage device that is non-transitory and that may enable data storage, and may include, but is not limited to, disk drives, optical storage devices, solid state memory, floppy disks, flexible disks, hard disks, magnetic tape, or any other magnetic medium, compact disk or any other optical medium, cache memory and/or any other memory chip or module, and/or any other medium from which a computer may read data, instructions, and/or code.
The processor 402 and/or the storage device 404 may connect or communicate with the bus 406 via one or more interfaces. Bus 406 may include, but is not limited to, an industry standard architecture (IndustryStandard Architecture, ISA) bus, a Micro channel architecture (Micro ChannelArchitecture, MCA) bus, an Enhanced ISA (EISA) bus, a Video Electronics Standards Association (VESA) local bus, and a Peripheral Component Interconnect (PCI) bus.
I/O device 408 can 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 touch pad, a mouse, a joystick or other pointing device, a microphone, speakers, and a display, among others.
Computing device 400 may also include a network interface 410. Network interface 410 may be any kind of device or system capable of enabling communication with external apparatuses and/or networks and may include, but is not limited to, modems, network cards, infrared communication devices, wireless communication devices, and/or chipsets (such as bluetooth (TM) devices, wiFi devices, wiMax devices, cellular communication facilities, etc.).
I/O devices 408 and/or network interfaces 410 may also be communicatively coupled with processor 402 and/or storage 404 via bus 406.
The various aspects, embodiments, implementations, or features of the foregoing embodiments may be used singly or in any combination. The 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. The hardware circuitry may include any combination of combinational logic circuits, clock storage devices (such as floppy disks, flip-flops, latches, etc.), finite state machines, memory such as static random access memory or embedded dynamic random access memory, 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 in combination with the use of discrete circuits.
Compared with the prior art, the method and the device can be used for simplifying and effectively modeling a complex communication network, and realizing multiple shortest path automatic route searching according to an actual optical network structure and a service scene under the topology logic of the complex communication network. The algorithm is designed and optimized in a layering mode according to the communication network environment, and the memory is calculated rapidly, so that the intelligent recommendation of the rapid route is realized, and the efficiency of the route design and the reliability of the route design configuration are improved remarkably.
In summary, according to a first aspect of the present disclosure, there is provided a method for searching for a cable route, 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 an optical cable, wherein the network model comprises nodes and links between the nodes; judging whether the optical cable comprises a section according to the user parameters, wherein links between nodes in the section are bidirectional; wherein if the fiber optic cable includes a span, the method further comprises: based on a network model, searching a route between a first node serving as a section start point and a second node serving as a section end point by using a section algorithm on the principle that the number of hops is as small as possible so as to obtain a section route, wherein if the optical cable only comprises a section, the section route is the optical cable route.
In some embodiments, the method further comprises: 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 comprises two access segments and comprises a span, the first node is a first access node from the first access segment to the span, the second node is a second access node from the span to the second access segment, and the method further comprises: searching a route between a starting node and a first access node by using an access segment algorithm based on a network model to obtain a first access segment route; searching a route between a second access node and a termination node by using an access segment algorithm based on the network model 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 schemes, and the interval algorithm includes: s1: calculating a shortest route between the first node and the second node as a current route and joining 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 between the first node in the current route and the offset node to obtain an offset route; s3: offset routes of all nodes except the second node in the current route form a second route set, and 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 route set is greater than or equal to the scheme number, wherein the routes in the first route set are interval section routes.
In some embodiments, the interval 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 route set and the number of hops of the additional route being not greater than the maximum number of hops plus one; and adding the additional route to the first route set to obtain the interval route.
In some embodiments, the method further comprises: the routes between the starting node and the ending node are ordered according to the weights, and the routes with the number equal to the number of schemes are selected according to the order of the weights, so that the optical cable route is obtained.
In some embodiments, the user parameters further include a number of schemes, and if the fiber optic cable includes only access segments, the method further includes: based on the network model, searching the route between the starting node and the ending node by using an access segment algorithm to obtain the optical cable route meeting the number of schemes.
In some embodiments, the access segment algorithm includes a recursive search for access segment routes.
In some embodiments, when obtaining a network model of the fiber optic cable, aggregating multiple devices within the same area into one node; and if the links entering the area and the links leaving the area are respectively connected to different devices in the area, obtaining routes between the different devices in the area by using an interval segment algorithm, and splicing the routes into the routes between the starting node and the ending node.
In some embodiments, the user parameters further include a minimum core number, and links having a core number below the minimum core number are removed when the network model of the fiber optic cable is acquired.
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 stored thereon a program 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 routing, comprising a memory and a processor, the memory being communicatively coupled to the processor, the memory having stored therein a program which, when executed by the processor, causes the processor to perform a 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 a cable routing, comprising means for performing the method according to the first aspect of the present disclosure.
While certain specific embodiments of the present disclosure have been described in detail by way of example, it will be appreciated by those skilled in the art that the above examples are intended to be illustrative only and not to limit the scope of the present disclosure. It should be appreciated that some of the steps in the foregoing methods are not necessarily performed in the order illustrated, but they may be performed simultaneously, in a different order, or in an overlapping manner. Furthermore, one skilled in the art may add some steps or omit some steps as desired. Some of the components in the foregoing systems are not necessarily arranged as shown, and one skilled in the art may add some components 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 for a fiber optic cable route, 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 an optical cable, wherein the network model comprises nodes and links between the nodes; and
judging whether the optical cable comprises a section according to the user parameters, wherein links between nodes in the section are bidirectional;
wherein if the fiber optic cable includes a span, the method further comprises:
based on the network model, searching the route between the first node serving as the start point of the section and the second node serving as the end point of the section by using the section algorithm on the principle of the minimum number of hops to obtain the section route,
wherein, if the optical cable only comprises a section, the section route is an optical cable route;
the interval algorithm comprises the following steps:
s1: calculating a shortest route between the first node and the second node as a current route and joining 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 an offset route;
S3: offset routes of all nodes except the second node in the current route form a second route set, and 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, wherein the route in the first route set is interval section 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 comprises two access segments and comprises a span, the first node is a first access node from the first access segment to the span, the second node is a second access node from the span to the second access segment, and the method further comprises:
searching a route between a starting node and a first access node by using an access segment algorithm based on a network model to obtain a first access segment route;
searching a route between a second access node and a termination node by using an access segment algorithm based on the network model 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 according to claim 1 or 2, wherein the user parameters further comprise a number of schemes, and the S4 comprises:
repeating S2 and S3 until the number of routes in the first route set is greater than or equal to the scheme number, wherein the routes in the first route set are interval section routes.
4. A method according to claim 3, wherein the interval 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 the number of hops of the additional route being not greater than the maximum number of hops plus one; and
and adding the additional route into the first route set to obtain the interval section route.
5. The method of claim 4, further comprising:
the routes between the starting node and the ending node are ordered according to the weights, and the routes with the number equal to the number of schemes are selected according to the order of the weights, so that the optical cable route is obtained.
6. The method of claim 2, wherein the user parameters further comprise a number of schemes, the method further comprising, if the fiber optic cable includes only access segments:
Based on the network model, searching the route between the starting node and the ending node by using an access segment algorithm to obtain the optical cable route meeting the number of schemes.
7. The method of claim 2 or 6, wherein the access segment algorithm comprises a recursive search of access segment routes.
8. The method of claim 1, 2 or 6, wherein a plurality of devices within the same area are aggregated into one node when acquiring a network model of the fiber optic cable; and
if the links entering the area and the links leaving the area are respectively connected to different devices in the area, the routes among the different devices in the area are obtained by using an interval algorithm, and are spliced into the routes between the starting node and the ending node.
9. The method of claim 1, 2 or 6, wherein the user parameters further comprise a minimum number of cores, and links having a number of cores below the minimum number of cores are removed when obtaining the network model of the fiber optic 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 stored thereon a program which, when executed by a computer, causes the computer to perform the method of any of claims 1 to 10.
12. A computing device for searching for fiber optic cable routes, comprising a memory and a processor, the memory being communicatively coupled to the 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-10.
13. An apparatus for searching for fiber optic cable routing, comprising means for performing the method of any one of claims 1 to 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 CN114301827A (en) | 2022-04-08 |
| CN114301827B true 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) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN119697097A (en) * | 2024-12-11 | 2025-03-25 | 国家电网有限公司信息通信分公司 | Routing path acquisition method and device |
Citations (6)
| 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 |
| 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 |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US10505836B2 (en) * | 2017-04-21 | 2019-12-10 | 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 |
-
2020
- 2020-09-23 CN CN202011009146.4A patent/CN114301827B/en active Active
Patent Citations (6)
| 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 |
| 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的光接安全入网主干光缆路由优化模型和算法研究;王璇;;网络安全技术与应用(第01期);全文 * |
| 绿色主干网络中一种高效的节能路由算法;陈若宾;王兴伟;马连博;黄敏;;计算机学报(第11期);全文 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN114301827A (en) | 2022-04-08 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5233604A (en) | Methods and apparatus for optimum path selection in packet transmission networks | |
| CN109194468B (en) | Deployment method, apparatus and device of relay node, and computer-readable storage medium | |
| JP2002199005A (en) | Method for designing interconnect fabric | |
| WO2017045578A1 (en) | Topological graph optimal path algorithm with constraint conditions | |
| CN113193996B (en) | Power optical transmission network optimization method, device, equipment and storage medium | |
| CN109639575A (en) | Route planning method based on link congestion coefficient | |
| CN107196858A (en) | A kind of k solving the shortest path methods for considering polymorphic type constraint | |
| CN114417572B (en) | Optical cable routing planning method, device, terminal equipment and storage medium | |
| CN104348691B (en) | A kind of fiber link dispatching method, equipment and system | |
| CN102413050A (en) | Optical fiber scheduling method and device | |
| CN114301793A (en) | Path generation method and device in optical transport network | |
| CN106059696B (en) | A kind of configuration method and device of synchronous net | |
| CN114301827B (en) | Method and apparatus for searching for optical cable routes | |
| CN115882998A (en) | Service channel automatic configuration method and device, electronic equipment and storage medium | |
| CN109962801B (en) | Communication quality abnormity positioning method, device, equipment and medium | |
| Hayashi et al. | Evaluating reliability of telecommunications networks using traffic path information | |
| CN112019436B (en) | Transmission path selection method, device, equipment and medium | |
| CN109639578B (en) | Method and device for selecting virtual network function | |
| CN105553719A (en) | Optical cable path planning method oriented to telecom resource business field | |
| CN103188148B (en) | The distribution method of a kind of upper wireless link and system | |
| CN119110176B (en) | Optical link optimization method, device, electronic device and non-volatile storage medium | |
| US9785738B1 (en) | System and method for evaluating spanning trees | |
| CN109981313B (en) | Assessment method and device for carrier-class application cloud deployment | |
| WO2017059733A1 (en) | Method and apparatus for avoiding traffic storm caused by network sharing ring protection | |
| CN113806270B (en) | Path planning method and device for rapidIO network, electronic equipment and storage medium |
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 |