CN109361604A - The most short service path of Dominator and link determines method and apparatus in IPRAN or PTN - Google Patents
The most short service path of Dominator and link determines method and apparatus in IPRAN or PTN Download PDFInfo
- Publication number
- CN109361604A CN109361604A CN201811548378.XA CN201811548378A CN109361604A CN 109361604 A CN109361604 A CN 109361604A CN 201811548378 A CN201811548378 A CN 201811548378A CN 109361604 A CN109361604 A CN 109361604A
- Authority
- CN
- China
- Prior art keywords
- node
- dominator
- vertex set
- short service
- vertex
- 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.)
- Withdrawn
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/12—Shortest path evaluation
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
This application provides the most short service paths of Dominator in a kind of IPRAN or PTN and link to determine method and apparatus, this method comprises: being directed to present node, obtains the corresponding vertex set of the node；Determine the node number in the vertex set；If the node number in the vertex set is greater than 1, it is determined that with the presence or absence of the node in the Dominator set in the vertex set；When there are the nodes in the Dominator set in the vertex set for determination, and node number be greater than 1 when, if concentrating in the vertex set and the Dominator intersection of sets, there are the nodes of the link in the necessary link set, then corresponding node are determined as next-hop node；Determining next-hop node is stored into most short service path set, until destination node storage into shortest path collection of services, is determined that the corresponding path of node in the shortest path collection of services is most short service path.This method can be realized the determination of conditional most short service path.
Description
Technical field
The present invention relates to field of communication technology, in particular to a kind of transmission (IPRAN) or grouping based on Internet Protocol
The most short service path of Dominator and link determines method and apparatus in transmission net (PTN).
Background technique
Shortest route problem is widely used in computer science, traffic engineering, communication engineering, system engineering, operational research, letter
Cease the various fields such as opinion, control theory.
In some special cases, it may require that path by specific node or specific link.
The classic algorithm for solving shortest path is dijkstra's algorithm, but the algorithm only considered source point and place point, no
It is able to satisfy the particular/special requirement by specific node and link.
It is PTN network topology schematic diagram referring to Fig. 1, Fig. 1.Assuming that the weight in each path in Fig. 1 is identical, Dijkstra is calculated
Shortest path between the available source point S of method and place point T, such as S-A-B-T or S-C-D-T etc..If it is desired to which path must be through
Tri- nodes of A, B, D are crossed, and have to pass through the link between A and D, then dijkstra's algorithm cannot determine most under the premise of above-mentioned
Short service path.
Summary of the invention
In view of this, the application provides the most short service path determination side of Dominator and link in a kind of IPRAN or PTN
Method and device can be realized the determination of conditional most short service path.
In order to solve the above technical problems, the technical solution of the application is achieved in that
The most short service path of Dominator and link determines method in a kind of IPRAN or PTN, this method comprises:
According to most short service path Dominator to be established and link, Dominator set and necessary link set are established
It closes, and two nodes of necessary link is increased in the Dominator set；
Most short service path is begun setting up from source node；By source node storage into most short service path set；
For present node, the corresponding vertex set of the node is obtained；
Determine the node number in the vertex set；
If the node number in the vertex set is greater than 1, it is determined that whether there is the necessary section in the vertex set
Node in point set；
When there are the nodes in the Dominator set in the vertex set for determination, and node number is greater than 1, if
It is concentrated in the vertex set and the Dominator intersection of sets, there are the nodes of the link in the necessary link set, then
Corresponding node is determined as next-hop node；
Determining next-hop node is stored into most short service path set, is stored until by destination node to shortest path
In diameter collection of services, determine that the corresponding path of node in the shortest path collection of services is most short service path.
The most short service path determining device of Dominator and link in a kind of IPRAN or PTN, the device include: to establish
Unit, acquiring unit and determination unit；
It is described to establish unit, for establishing Dominator according to most short service path Dominator and link to be established
Set and necessary link set, and two nodes of necessary link are increased in the Dominator set；Source node is deposited
It stores up in most short service path set；Determining next-hop node is stored into most short service path set；
The acquiring unit, for beginning setting up most short service path from source node；For present node, the node is obtained
Corresponding vertex set；
The determination unit, the node number in vertex set for determining the acquiring unit acquisition；If the vertex
Node number in set is greater than 1, it is determined that with the presence or absence of the node in the Dominator set in the vertex set；When
It determines in the vertex set there are the node in the Dominator set, and when node number is greater than 1, if in the vertex set
It closes and is concentrated with the Dominator intersection of sets, there are the nodes of the link in the necessary link set, then by corresponding node
It is determined as next-hop node；Unit is established by destination node storage into shortest path collection of services, described in determination until described
The corresponding path of node in shortest path collection of services is most short service path.
As can be seen from the above technical solution, in the application when determining next-hop node, Dominator and necessary chain is added
The judgement on road preferentially selects Dominator and the corresponding node of necessary link as next-hop node, can be realized conditional
The determination of most short service path.
Detailed description of the invention
Fig. 1 is PTN network topology schematic diagram；
Fig. 2 is the flow diagram that most short service path is determined in the embodiment of the present application；
Fig. 3 is the apparatus structure schematic diagram for being applied to above-mentioned technology in the embodiment of the present application.
Specific embodiment
In order to make the objectives, technical solutions, and advantages of the present invention clearer, with reference to the accompanying drawings and examples,
Technical solution of the present invention is described in detail.
The most short service path determination side of Dominator and link in a kind of IPRAN or PTN is provided in the embodiment of the present application
The judgement of Dominator and necessary link is added when determining next-hop node in method, preferential to select Dominator and necessary link
Corresponding node can be realized the determination of conditional most short service path as next-hop node.
This method can be applied in PTN network and IPRAN network, and most short service path is determined in the embodiment of the present application
Device be to realize that most short service path determines the main body of method, can be a PC, or a node has acquisition
Information and judge information ability device, be collectively referred to as determining device below.
In the embodiment of the present application before the most short service path of determination, it is thus necessary to determine that the most short service path needed to meet
Condition: Dominator and necessary link；
Dominator set is established according to Dominator, according to the necessary link set of necessary link establishment, and by necessary chain
Two nodes on road increase in the Dominator set.
As required and being A, B and C through node, necessary link is link CD, then Dominator collection is combined into { A, B, C, D }, must
Collection through link is combined into { AD }.
It is repeated when existing to exist with the node in Dominator in two points of necessary link, then not by duplicate node
It is added in Dominator set, or by knot removal duplicate in Dominator set, to guarantee the node in Dominator not
It repeats.
With reference to the accompanying drawing, it is described in detail in the embodiment of the present application and realizes most short service path determination process.
Referring to fig. 2, Fig. 2 is the flow diagram that most short service path is determined in the embodiment of the present application.Specific steps are as follows:
Step 201, determining device begins setting up most short service path from source node；Most short industry is arrived into source node storage
In set of paths of being engaged in.
By taking Fig. 1 as an example, it is assumed that the most short service path condition to be met of foundation are as follows: and through node A, B and D, and through chain
Road is AD, then Dominator set M is { A, B, D }, and necessary link set N is { AD }, by taking the weight of each path is identical as an example.
Source node is node S, then most short service path set K is { S }.
Step 202, which is directed to present node, obtains the corresponding vertex set of the node.
When initial, present node is the source node of shortest path to be determined；It is later next-hop node determining every time.
Determining device can obtain the topological structure of entire PTN network in the embodiment of the present application, can be obtained each node
Vertex set, as node S vertex set be { A, C }.
After obtaining the corresponding vertex set of the node in this step, the section in the determining vertex set of step 203 is executed
Before point number, the method further includes:
If it is determined that when the vertex set and the most short service path intersection of sets are integrated not as sky, by institute in the vertex set
The knot removal in intersection is stated, then determines the node number in the vertex set.
That is determining whether there is identical node in most short service path set and the vertex set, if deposited
It is then being deleted from vertex set, in this way in order to avoid walking circuit.
Assuming that next-hop node A is determined via node S, then it is determined that when the next-hop of node A, by the vertex of node A
Gather interior joint S to delete, in case reselection is to node S as next-hop.
Step 203, which determines the node number in the vertex set.
By taking the vertex set of node S as an example, then the node number in vertex set { A, C } is 2；
With the vertex set of node A for { S, C, B, D }；Vertex set after then deleting a hop node S thereon be C, B,
D }, then the node number in the vertex set of node A is finally also determined as 3.
If the node number in the vertex set is 1, select the node as next-hop node.
When the node number in vertex set is 1, the node can only be selected as next-hop node.
Step 204, if the node number in the vertex set is greater than 1, which is determined in the vertex set
With the presence or absence of the node in the Dominator set.
When the determining device determines in the vertex set there are the node in the Dominator set, and node number
When being 1, determine that the node is next-hop node.
If the vertex set of node S is { A, C }, number is greater than 1, and node A exists in Dominator set, node C
Do not exist, it is determined that next-hop node is node A.
Step 205, when the determining device is determining, there are the nodes in the Dominator set in the vertex set, and
When node number is greater than 1, if concentrating in the vertex set and the Dominator intersection of sets, there are the necessary link sets
In link node, then corresponding node is determined as next-hop node.
If the vertex set of node A is { C, B, D }, node number is greater than 1, and node B and D be in Dominator set,
Node C does not exist, then further determines that and be AD through link in path, then select node D as next-hop node, save without selecting
Most short service path set is added as next-hop node in point B, and present most short service path collection is combined into { S, A, D }.
Vertex set for node D is { A, C, B, T }, the vertex set after node A is deleted are as follows: { C, B, T }.
Since node B is in the set of Dominator, accordingly, it is determined that the next-hop node of node D is node B.
Vertex set for node B is { A, D, T }, the top after the node A and D in most short service path set are deleted
Point set are as follows: { T }.
Accordingly, it is determined that the next-hop node of node B is node T.
When determining the node being not present in the Dominator set in the vertex set, it is determined whether there are purposes
Node, if so, selecting destination node as next-hop node；Otherwise, a section is selected according to the smallest principle of routine weight value
Point is used as next-hop node.
Assuming that destination node is also not present, then according to road there are Dominator is not present in the vertex set of a node
Diameter Weight selected selects the corresponding node in the smallest path of routine weight value as next-hop node.
Step 206, which stores determining next-hop node into most short service path set, until by mesh
Node store into shortest path collection of services, determine that the corresponding path of node in the shortest path collection of services is most
Short service path.
The most short service path collection finally determined through the above steps is combined into { S, A, D, B, T }, then shortest path are as follows: S-A-
D-B-T。
It is realized in the above embodiments of the present application and determines most short service path in the case where additional conditions.
Based on same inventive concept, Dominator and chain in a kind of IPRAN or PTN are additionally provided in the embodiment of the present application
The most short service path determining device on road.Referring to Fig. 3, Fig. 3 is the apparatus structure for being applied to above-mentioned technology in the embodiment of the present application
Schematic diagram.The device includes: to establish unit 301, acquiring unit 302 and determination unit 303；
Unit 301 is established, for establishing Dominator collection according to most short service path Dominator and link to be established
Conjunction and necessary link set, and two nodes of necessary link are increased in the Dominator set；Source node is stored
Into most short service path set；Determining next-hop node is stored into most short service path set；
Acquiring unit 302, for beginning setting up most short service path from source node；For present node, the node is obtained
Corresponding vertex set；
Determination unit 303, the node number in vertex set for determining the acquisition of acquiring unit 302；If the vertex set
Node number in conjunction is greater than 1, it is determined that with the presence or absence of the node in the Dominator set in the vertex set；When true
It is scheduled in the vertex set there are the node in the Dominator set, and when node number is greater than 1, if in the vertex set
It is concentrated with the Dominator intersection of sets, it is there are the node of the link in the necessary link set, then corresponding node is true
It is set to next-hop node；It is determining described most short until establishing unit 301 by destination node storage into shortest path collection of services
The corresponding path of node in path service set is most short service path.
Preferably,
Determination unit 303 is further used for being not present in the Dominator set in the vertex set when determining
When node, it is determined whether there are destination nodes, if so, selecting destination node as next-hop node；Otherwise, it is weighed according to path
Being worth the smallest principle selects a node as next-hop node.
Preferably,
Determination unit 303 is further used for determine that there are the sections in the Dominator set in the vertex set
Point, and node number be 1 when, determine the node be next-hop node；If it is determined that the node number in the vertex set is 1
When, select the node as next-hop node.
Preferably,
Determination unit 303, before being further used for determining the node number in the vertex set, however, it is determined that the vertex set
When integrating not with the most short service path intersection of sets as sky, by the knot removal in intersection described in the vertex set, then really
Node number in the fixed vertex set.
Preferably,
Duplicate node is not present in the Dominator set.
The unit of above-described embodiment can integrate in one, can also be deployed separately；It can be merged into a unit, it can also
To be further split into multiple subelements.
In conclusion the application is by when determining next-hop node, being added the judgement of Dominator and necessary link, it is excellent
It first selects Dominator and the corresponding node of necessary link as next-hop node, can be realized conditional most short service path
Determination.
The foregoing is merely illustrative of the preferred embodiments of the present invention, is not intended to limit the invention, all in essence of the invention
Within mind and principle, any modification, equivalent substitution, improvement and etc. done be should be included within the scope of the present invention.
Claims (10)
1. the most short industry of Dominator and link in a kind of transmission net IPRAN or Packet Transport Network PTN based on Internet Protocol
Business determining method of path, which is characterized in that this method comprises:
According to most short service path Dominator to be established and link, Dominator set and necessary link set are established, and
Two nodes of necessary link are increased in the Dominator set；
Most short service path is begun setting up from source node；By source node storage into most short service path set；
For present node, the corresponding vertex set of the node is obtained；
Determine the node number in the vertex set；
If the node number in the vertex set is greater than 1, it is determined that whether there is the Dominator collection in the vertex set
Node in conjunction；
When there are the nodes in the Dominator set in the vertex set for determination, and node number is greater than 1, if at this
Vertex set and the Dominator intersection of sets are concentrated, and there are the nodes of the link in the necessary link set, then will be right
Node is answered to be determined as next-hop node；
Determining next-hop node is stored into most short service path set, is stored until by destination node to shortest path industry
In business set, determine that the corresponding path of node in the shortest path collection of services is most short service path.
2. the method according to claim 1, wherein the method further includes:
When determining the node being not present in the Dominator set in the vertex set, it is determined whether there are purpose sections
Point, if so, selecting destination node as next-hop node；Otherwise, a node is selected according to the smallest principle of routine weight value
As next-hop node.
3. the method according to claim 1, wherein the method further includes:
When there are the nodes in the Dominator set in the vertex set for determination, and node number is 1, described in determination
Node is next-hop node；
If it is determined that selecting the node as next-hop node when the node number in the vertex set is 1.
4. the method according to claim 1, wherein after the corresponding vertex set of described acquisition node, really
Before node number in the fixed vertex set, the method further includes:
If it is determined that will be handed over described in the vertex set when vertex set and the most short service path intersection of sets are integrated not as sky
The knot removal of concentration, then determine the node number in the vertex set.
5. method according to claim 1-4, which is characterized in that
Duplicate node is not present in the Dominator set.
6. the most short industry of Dominator and link in a kind of transmission net IPRAN or Packet Transport Network PTN based on Internet Protocol
Business path determining device, which is characterized in that the device includes: to establish unit, acquiring unit and determination unit；
It is described to establish unit, for establishing Dominator set according to most short service path Dominator and link to be established
With necessary link set, and two nodes of necessary link are increased in the Dominator set；Source node storage is arrived
In most short service path set；Determining next-hop node is stored into most short service path set；
The acquiring unit, for beginning setting up most short service path from source node；For present node, it is corresponding to obtain the node
Vertex set；
The determination unit, the node number in vertex set for determining the acquiring unit acquisition；If the vertex set
In node number be greater than 1, it is determined that with the presence or absence of the node in the Dominator set in the vertex set；Work as determination
There are the node in the Dominator set in the vertex set, and when node number is greater than 1, if the vertex set with
The Dominator intersection of sets is concentrated, and there are the nodes of the link in the necessary link set, then is determined corresponding node
For next-hop node；Unit is established by destination node storage into shortest path collection of services until described, it is determining described most short
The corresponding path of node in path service set is most short service path.
7. device according to claim 6, which is characterized in that
The determination unit is further used for the node being not present in the vertex set in the Dominator set when determining
When, it is determined whether there are destination nodes, if so, selecting destination node as next-hop node；Otherwise, most according to routine weight value
Small principle selects a node as next-hop node.
8. device according to claim 6, which is characterized in that
The determination unit is further used for when determining in the vertex set there are the node in the Dominator set,
And node number be 1 when, determine the node be next-hop node；If it is determined that when the node number in the vertex set is 1, choosing
The node is selected as next-hop node.
9. device according to claim 6, which is characterized in that
The determination unit, before being further used for determining the node number in the vertex set, however, it is determined that the vertex set with
When the most short service path intersection of sets is integrated not as sky, by the knot removal in intersection described in the vertex set, then determine
Node number in the vertex set.
10. according to the described in any item devices of claim 6-9, which is characterized in that
Duplicate node is not present in the Dominator set.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811548378.XA CN109361604A (en) | 2018-12-18 | 2018-12-18 | The most short service path of Dominator and link determines method and apparatus in IPRAN or PTN |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811548378.XA CN109361604A (en) | 2018-12-18 | 2018-12-18 | The most short service path of Dominator and link determines method and apparatus in IPRAN or PTN |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN109361604A true CN109361604A (en) | 2019-02-19 |
Family
ID=65328957
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201811548378.XA Withdrawn CN109361604A (en) | 2018-12-18 | 2018-12-18 | The most short service path of Dominator and link determines method and apparatus in IPRAN or PTN |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN109361604A (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN114928569A (en) * | 2022-04-28 | 2022-08-19 | 烽火通信科技股份有限公司 | Method and system for realizing shortest path containing multiple must-pass resources |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103828296A (en) * | 2011-09-13 | 2014-05-28 | 阿尔卡特朗讯公司 | Method for shortest path bridging of multicast traffic |
| CN105141524A (en) * | 2015-09-16 | 2015-12-09 | 武汉烽火技术服务有限公司 | Topological graph optimal route algorithm with constraint conditions |
| WO2017026999A1 (en) * | 2015-08-07 | 2017-02-16 | Hewlett Packard Enterprise Development Lp | Identifying shortest paths |
-
2018
- 2018-12-18 CN CN201811548378.XA patent/CN109361604A/en not_active Withdrawn
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103828296A (en) * | 2011-09-13 | 2014-05-28 | 阿尔卡特朗讯公司 | Method for shortest path bridging of multicast traffic |
| WO2017026999A1 (en) * | 2015-08-07 | 2017-02-16 | Hewlett Packard Enterprise Development Lp | Identifying shortest paths |
| CN105141524A (en) * | 2015-09-16 | 2015-12-09 | 武汉烽火技术服务有限公司 | Topological graph optimal route algorithm with constraint conditions |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN114928569A (en) * | 2022-04-28 | 2022-08-19 | 烽火通信科技股份有限公司 | Method and system for realizing shortest path containing multiple must-pass resources |
| CN114928569B (en) * | 2022-04-28 | 2023-06-09 | 烽火通信科技股份有限公司 | Shortest path implementation method and system containing multiple necessary resources |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2793467B2 (en) | Apparatus and method for selecting an optimal route for a packet communication system | |
| JP6920533B2 (en) | Data flow transmission | |
| CN109639575A (en) | Route planning method based on link congestion coefficient | |
| CN112118181B (en) | Traffic scheduling method and device | |
| CN113242179B (en) | SDN-based SR path calculation and label stack generation method and SDN controller | |
| JP5869041B2 (en) | Method for mapping network topology request to physical network, computer program product, mobile communication system, and network configuration platform | |
| CN112702267B (en) | Distributed training routing method, system, storage medium and computer equipment | |
| US9166906B2 (en) | Routing method in asymmetric networks | |
| CN108632940A (en) | Reliable multi-path routing algorithm suitable for photoelectric sensor Wireless MESH network | |
| CN109617805B (en) | Method and device for acquiring link dynamic attribute and method and device for selecting path | |
| US8798081B2 (en) | Event delivery system, rendezvous node, broker node, load distribution method for event delivery system, load distribution method for rendezvous node, delivery route construction method for broker node, storage medium storing load distribution program, and storage medium storing delivery route construction program | |
| CN103532861B (en) | In territory based on spanning tree, Dynamic Multi-Pathing generates method | |
| WO2019141970A1 (en) | Routing mechanisms for low-power and lossy networks | |
| CN104243303B (en) | The method and apparatus for updating message are sent in a kind of autonomous system loop networking | |
| CN109361604A (en) | The most short service path of Dominator and link determines method and apparatus in IPRAN or PTN | |
| CN106817266A (en) | A kind of peer network resources method for down loading | |
| CN105763468B (en) | A kind of transmission method and device of bgp update message | |
| CN102123089B (en) | Tunnel establishing method and device | |
| CN111464440A (en) | Communication method and device | |
| CN104135423B (en) | A kind of bidirectional tunnel method for building up and device | |
| CN106936710B (en) | Mesh Group configuration method and device | |
| CN106254241B (en) | A kind of trans-regional CSPF the whole network calculating implementation method based on IGP | |
| CN106130895B (en) | The heavy route method and device of SDN network failure | |
| CN106162707A (en) | The monitoring method of aggregation node state, device and system | |
| CN106656802A (en) | End-to-end tunnel generation method |
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 | ||
| WW01 | Invention patent application withdrawn after publication |
Application publication date: 20190219 |
|
| WW01 | Invention patent application withdrawn after publication |