CN114978982B - Method and device for determining multicast path - Google Patents
Method and device for determining multicast path Download PDFInfo
- Publication number
- CN114978982B CN114978982B CN202210332813.5A CN202210332813A CN114978982B CN 114978982 B CN114978982 B CN 114978982B CN 202210332813 A CN202210332813 A CN 202210332813A CN 114978982 B CN114978982 B CN 114978982B
- Authority
- CN
- China
- Prior art keywords
- path
- multicast
- paths
- sets
- path set
- 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
- 238000000034 method Methods 0.000 title claims abstract description 59
- 238000012216 screening Methods 0.000 claims abstract description 42
- 238000001914 filtration Methods 0.000 claims abstract description 29
- 238000004364 calculation method Methods 0.000 claims abstract description 15
- 238000012163 sequencing technique Methods 0.000 claims abstract description 6
- 238000010276 construction Methods 0.000 claims description 7
- 230000001934 delay Effects 0.000 claims description 4
- 238000004590 computer program Methods 0.000 claims 2
- 238000010586 diagram Methods 0.000 description 3
- 238000005516 engineering process Methods 0.000 description 3
- 238000012423 maintenance Methods 0.000 description 2
- 238000005259 measurement Methods 0.000 description 2
- 230000003287 optical effect Effects 0.000 description 2
- 230000010076 replication Effects 0.000 description 2
- 235000008694 Humulus lupulus Nutrition 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000002457 bidirectional effect Effects 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 238000013480 data collection Methods 0.000 description 1
- 230000006870 function Effects 0.000 description 1
- 238000012545 processing Methods 0.000 description 1
- 238000000926 separation method Methods 0.000 description 1
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/16—Multipoint routing
-
- 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
- H04L45/121—Shortest path evaluation by minimising delays
-
- 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
- H04L45/123—Evaluation of link metrics
-
- 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
- H04L45/124—Shortest path evaluation using a combination of metrics
-
- 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
- H04L45/125—Shortest path evaluation based on throughput or bandwidth
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The invention discloses a method and a device for determining a multicast path, wherein the method for determining the multicast path comprises the following steps: obtaining topology information of a current network and network performance indexes; calculating a path set between all (S, G) according to the topology information and the network performance index; filtering path sets between the (S, G) according to constraint conditions, and screening out the path sets meeting the constraint conditions; traversing and combining the screened (S, G) path sets according to the same source to obtain a plurality of multicast tree path sets; sequencing the multicast tree path sets according to the total number of the passed links, and screening the multicast tree paths with the minimum number of the links to determine the optimal multicast path; the determination method ensures that the multicast path calculation is highly controllable, and can flexibly define the equivalent indexes of the bandwidth, the time delay, the hop count, the unnecessary link and the unnecessary network element avoidance of the multicast path.
Description
Technical Field
The present invention relates to the field of communications, and in particular, to a method and an apparatus for determining a multicast path in an SDN scenario.
Background
In conventional multicast technology, a multicast forwarding tree needs to be established for each multicast traffic, and a shortest path from a multicast source to a receiver, also called SPT (Shortest Path Tree ), is used. Multicast users need to join the distribution tree hop by hop, each node needs to keep the multicast stream state, and the receiving node joining or leaving can cause the re-convergence of the multicast state tree, and the maintenance of the multicast state is complex.
To meet the large-scale multicast traffic demands, a multicast network is constructed using BIER technique (Bit Index Explicit Replication, explicit replication based on bit index). By designating the receiving node by the head node, the BIER solves the problem of complex maintenance of the traditional multicast state. However, the BIER forwarding table is controlled and generated based on the IGP protocol, so that the multicast traffic forwarding path cannot be controlled, and the multicast requirement meeting SLA (Service Level Agreement) cannot be provided according to the user requirement or the actual network operation condition.
A Software Defined Network (SDN) is a novel network innovation architecture, provides a network control plane and forwarding plane separation idea, and for better satisfying service SLAs, the control plane can extract from the control functions of routers or switches, and according to the service SLA requirements, directly control forwarding table entries through the control plane, guide service traffic forwarding, and complete control of the whole network.
Unlike traditional multicast path calculation method, multicast service has different SLA requirements, such as bandwidth, time delay, hop count, and the like, when planning, one or a combination of several constraint conditions such as network elements must be passed or excluded. How to combine SDN technology, provide and meet the demand of differentiated SLA, have high controllable, low-load multicast route calculation method, in order to apply to new multicast scene such as BIER, etc. is a urgent problem that needs to be solved.
Disclosure of Invention
In order to solve the problems, the invention provides a method and a device for determining a multicast path, which can reasonably plan and flexibly control the multicast path according to network performance measurement indexes.
In order to achieve the above object, an aspect of the present invention provides a method for determining a multicast path, including:
obtaining topology information of a current network and network performance indexes;
calculating a path set between all (S, G) according to the topology information and the network performance index;
filtering path sets between the (S, G) according to constraint conditions, and screening out the path sets meeting the constraint conditions;
Traversing and combining the screened (S, G) path sets according to the same source to obtain a plurality of multicast tree path sets;
and sequencing the multicast tree path sets according to the total number of the passed links, and screening the multicast tree paths with the minimum total number of the passed links to determine the optimal multicast path.
As a preferable technical solution, the network performance index includes a delay of a link and a traffic of an interface.
As a preferred technical solution, calculating a set of paths between all (S, G) according to the topology information and the network performance index, further includes: constructing a path calculation directed graph according to the topology information; and reconstructing a path directed graph by taking the value of the network performance index as the weight of the edge in the directed weighted graph.
As a preferable technical solution, constructing a path-oriented graph according to the topology information, further includes: and taking the nodes in the topology information as points of the path directional weighted graph, and taking the links in the topology information as edges of the path directional weighted graph to construct the path directional graph.
As a preferable technical scheme, the constraint condition is one or more of a bandwidth constraint value, a time delay constraint value, a network element and a link, and a network element and a link.
As a preferred technical solution, filtering a path set between (S, G) according to constraint conditions, and screening a path set satisfying constraint conditions, further including:
When the constraint condition is a bandwidth constraint value, screening out paths with residual bandwidths of each section of links in the path set between the (S, G) more than or equal to a preset bandwidth constraint value to obtain a path set meeting the constraint condition;
when the constraint condition is a time delay constraint value, screening out paths of which the sum of link time delays of the end-to-end paths in the path set between the (S, G) is smaller than or equal to a preset time delay constraint value to obtain a path set meeting the constraint condition.
And when the constraint condition is that the network element and the link are necessary, screening out a path set end-to-end path between the (S, G) and the path set end-to-end path comprises all paths which are necessary to pass through the network element and the link and are required to meet the constraint condition.
And when the constraint condition is that the network elements and the links are necessary to be avoided, screening out the end-to-end paths in the path set between the (S, G) to exclude all the path sets which are necessary to be avoided and the network elements and the links to be met the constraint condition.
Based on the above technical solution, preferably, when a path is strictly specified, each hop of the computed path must correspond to each hop of the strictly path one by one.
In another aspect, the present invention further provides a device for determining a multicast path, including:
The acquisition unit is used for acquiring topology information and network performance indexes of the current network;
A calculation unit for calculating a set of paths between all (S, G) according to the topology information and the network performance index;
a first screening unit, configured to filter a path set between (S, G) according to a constraint condition, and screen a path set that satisfies the constraint condition;
The second screening unit is used for traversing and combining the screened (S, G) path sets according to the same source to obtain a plurality of multicast tree path sets;
And the determining unit is used for sequencing the multicast tree path sets according to the total number of the passed links, and screening the multicast tree paths with the minimum total number of the passed links so as to determine the optimal multicast path.
Compared with the prior art, the invention has the beneficial effects that: the method utilizes topology information and network performance indexes to construct a path directed graph, and then screens a path set of the path directed graph through screening conditions, so that the multicast path calculation is highly controllable, and the equivalent indexes of bandwidth, time delay, hop count, necessary links and necessary network elements of the multicast path can be flexibly defined.
Drawings
Fig. 1 is a flowchart of a method for determining a multicast path according to an embodiment of the present invention;
FIG. 2 is a flow chart of computing a set of paths between all (S, G) S provided by an embodiment of the present invention;
FIG. 3 is a flow chart of a screening path set provided by an embodiment of the present invention;
Fig. 4 is a block diagram of a multicast path determining apparatus according to an embodiment of the present invention;
FIG. 5 is a block diagram of a computing unit provided by an embodiment of the present invention;
fig. 6 is a block diagram of a first filtering unit according to an embodiment of the present invention.
Detailed Description
The following description of the embodiments of the present invention will be made clearly and fully with reference to the accompanying drawings, in which it is evident that the embodiments described are only some, but not all embodiments of the invention. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without making any inventive effort, are intended to be within the scope of the invention.
Referring to fig. 1, the present embodiment provides a method for determining a multicast path, and it should be noted that the method is applied to an SDN network, and the entire method is implemented by using an SDN controller as an operation entity, and includes the following steps:
S10: obtaining topology information of a current network and network performance indexes;
Topology information is key information of a network, and there are various ways to obtain the network topology in the field, and in this embodiment, BGP-LS (BGP Link-state) is used to collect the topology in IGP (Interior Gateway Protocol).
In addition, the network performance index includes the delay of the link and the traffic of the interface, and in this embodiment, TWAMP (Two-WAY ACTIVE Measurement Protocol ) is used to count the delay of the link. Traffic for the interface is counted using TELEMETRY (a remote, high-speed data collection technology from physical or virtual devices).
S20: calculating a path set between all (S, G) according to the topology information and the network performance index;
It should be understood that the set of paths between (S, G) refers to the set of paths between the multicast source and the multicast group, and how the set of paths between (S, G) is calculated from topology information and network performance metrics is described in detail below in connection with fig. 2.
Referring to fig. 2, the step specifically includes S201: firstly, constructing a path calculation directed graph according to the topology information; specifically, in this embodiment, a bidirectional graph is defined by using class DirectedWeightedMultigraph of Jgrapht (a graph library supporting mathematical graph theory and algorithm), using method addVertex to take nodes of the topology as points of the directed weighted graph, using method addEdge to take links of the topology as edges of the directed weighted graph, thereby constructing a path-oriented graph, which is a preliminary path-oriented graph, and then needs to be optimized.
S202, reconstructing a path directed graph according to the value of the network performance index as the weight of the edge in the directed weighted graph.
Specifically, the step is to optimize the preliminary path-calculation directed graph formed in step S201, in this embodiment, TELEMETRY transmits data through gRPC (Google Remote Procedure Call Protocol) protocol, after receiving the related data, the controller finds the corresponding link, updates its performance index, and uses the method SETEDGEWEIGHT to take the delay value or the flow value of the link as the weight on the directed weighted graph side;
S203, using the method getPaths of class KShortestSimplePaths of Jgrapht (a graphic library supporting mathematical graph theory and algorithms), determine the k shortest set of simple paths [ (S, G11), (S, G12) ] in order of increasing weight, the paths can be constrained by the maximum number and the maximum number of hops.
After the path set between (S, G) is calculated, it is also necessary to filter the path set, so step S30 is necessary, and step S30 is as follows:
S30: filtering path sets between the (S, G) according to constraint conditions, and screening out the path sets meeting the constraint conditions;
it should be noted that the constraint condition may be set according to the need, and the constraint condition may be one or more of a bandwidth constraint value, a delay constraint value, a network element and a link, and a network element and a link, which are specifically described below for screening of constraint adjustment.
Referring to fig. 3, step S30 specifically includes the steps of:
S301: when the constraint condition is a bandwidth constraint value, filtering the path set between all (S, G) calculated in step S20, and only when the residual bandwidth (the total bandwidth of the links-the current bandwidth used by the links) of each link on the path is greater than or equal to the bandwidth constraint value specified by the user, conforming to the constraint condition, otherwise filtering, and if the bandwidth constraint value is not specified by the user, not filtering.
S302: when the constraint condition is a time delay constraint value, the path set filtered in the filtering step S301 accords with the constraint condition only when the link time delay sum of the end-to-end paths is smaller than or equal to a preset time delay constraint value, otherwise, the path set is filtered, and if the time delay constraint value is not specified by the user, the path set is not filtered.
S303: when the constraint condition is that the network element and the link are necessary, the path set filtered in the filtering step S302 accords with the constraint condition when the end-to-end path contains all the network elements and the link, otherwise, the constraint condition is filtered, and if the time delay constraint value is not specified by the user, the constraint condition is not filtered.
In addition, if a path is strictly specified, each hop of the computed path must correspond to each hop of the strictly path. For example, a strict assignment of paths 1-2-3-4, then during screening, when the end-to-end path is 1-2-4-3, or 1-3-2-4, is also not satisfactory, filtering is required. If the path is not strictly specified, the end-to-end path is eligible as long as it contains 1, 2,3, 4.
S304: when the constraint condition is that the network elements and links need to be avoided, the path set filtered in the filtering step S303 is filtered, when the end-to-end path excludes all the network elements and links which need to be avoided, if the user does not specify the constraint which need to be avoided, the filtering is finished.
In addition, it should be noted that, in the above screening process, although the input data of the next screening step is the output data of the previous step, the protection scope of the present invention is not limited to this, and the result set obtained after screening the data of each input screening step is also within the protection scope of the present invention, for example, the input of the screening delay constraint value may be the result set obtained after screening the bandwidth constraint value, the result set obtained after screening the network element and the link, and other similar matters.
S40: traversing and combining the screened (S, G) path sets according to the same source to obtain a plurality of multicast tree path sets;
Specifically, the path sets screened in the step S30 are selected to form [ (S, G 1)],[(S,G2)]...[(S,Gi)]…[(S,Gn) ] path set groups by selecting the same multicast source S and the path sets of different multicast groups G, wherein (S, G i) represents the path set, i is a positive integer greater than 0 and less than n, and n represents the number of multicast groups of the current network;
Then traversing and combining the path set groups according to different groups G of the photographic source S to obtain m multicast tree path sets, specifically, multiplying the total number of paths in the path sets by a result count [1 ]. Count [2 ]. Count [ n ], and obtaining the following structure:
Wherein S is a multicast source, G ij represents a specific multicast group path, i, j is a positive integer greater than 0 and less than n, and n represents the number of multicast groups of the current network.
After obtaining a plurality of multicast tree path sets, an optimal multicast path needs to be determined, and the specific steps are as follows:
S50: and sequencing the multicast tree path sets according to the total number of the passed links, and screening the multicast tree paths with the minimum number of the links to determine the optimal multicast path.
Specifically, a plurality of multicast tree path sets are taken as input, repeated links are filtered, the multicast tree path sets are ordered according to the total number of the passed links, and the multicast tree paths with the minimum total number of the passed links are screened; and finally, carrying out the steps on different multicast sources S to finally finish the construction of the optimal path tree of the whole multicast service.
The method utilizes topology information and network performance indexes to construct a path directed graph, and then screens a path set of the path directed graph through screening conditions, so that the multicast path calculation is highly controllable, and the equivalent indexes of bandwidth, time delay, hop count, necessary links and necessary network elements of the multicast path can be flexibly defined.
Referring to fig. 4, this embodiment further provides a device for determining a multicast path, including:
An obtaining unit 10, configured to obtain topology information and network performance indexes of a current network; it should be noted that, since the specific acquisition manner and the procedure are already described in detail in the step S10 of the multicast path determining method described in the above embodiment, the description thereof is omitted here.
A calculation unit 20 for calculating a set of paths between all (S, G) based on the topology information and network performance metrics; it should be noted that, since the specific calculation method and the procedure are already described in detail in step S20 of the multicast path determining method described in the above embodiment, the detailed description is omitted here.
A first filtering unit 30, configured to filter a path set between (S, G) according to a constraint condition, and filter a path set that satisfies the constraint condition; it should be noted that, since the specific screening method and the procedure are already described in detail in the step S30 of the method for determining a multicast path described in the above embodiment, the description thereof is omitted here.
A second screening unit 40, configured to traverse and combine the screened (S, G) path sets according to the same source to obtain a plurality of multicast tree path sets; it should be noted that, since the specific screening method and the procedure are already described in detail in step S40 of the method for determining a multicast path described in the above embodiments, the detailed description is omitted here.
A determining unit 50, configured to sort the multiple multicast tree path sets according to the total number of the links passing through, and screen the multicast tree path with the minimum number of links to determine an optimal multicast path; it should be noted that, since the specific determination manner and the procedure are already described in detail in the step S50 of the multicast path determination method described in the above embodiment, the description thereof is omitted here.
In other embodiments, as shown in fig. 5, the computing unit 20 further includes a first construction module 201, configured to construct a road map according to the topology information; it should be noted that, since the specific construction manner and the procedure are already described in detail in the step S201 of the multicast path determining method described in the above embodiment, the description thereof is omitted here.
A second construction module 202, configured to reconstruct a path directed graph according to the value of the network performance index as the weight of the edge in the directed weighted graph; since the specific construction manner and the procedure are already described in detail in step S202 of the multicast path determining method described in the above embodiments, the description thereof is omitted here.
In other embodiments, as shown in fig. 6, the first filtering unit 30 further includes a first filtering module 301, configured to filter paths with a remaining bandwidth of each segment of links in the path set between (S, G) being greater than or equal to a preset bandwidth constraint value to obtain a path set that satisfies the constraint condition; since the specific filtering manner and the procedure are described in detail in step S301 of the method for determining a multicast path in the above embodiments, the details are not described herein.
A second filtering module 302, configured to filter paths with a sum of link delays of end-to-end paths in the path set between (S, G) being less than or equal to a preset delay constraint value to obtain a path set satisfying the constraint condition; since the specific filtering manner and the procedure are described in detail in step S302 of the method for determining a multicast path in the above embodiments, the details are not described herein.
A third filtering module 303, configured to filter that the end-to-end paths in the path set between (S, G) includes all paths that have to pass through the network element and the link to obtain a path set that satisfies the constraint condition; since the specific filtering manner and the procedure are described in detail in step S303 of the method for determining a multicast path in the above embodiments, the details are not described herein.
A fourth filtering module 304, configured to filter the end-to-end path set between (S, G) to exclude all path sets that have to avoid network elements and links to meet constraint conditions; since the specific filtering manner and the procedure are described in detail in step S304 of the method for determining a multicast path in the above embodiments, the details are not described herein.
In addition, an embodiment of the present invention further provides a computer readable storage medium, where the computer readable storage medium may store a program, where the program when executed includes some or all steps of any one of the multicast path determining methods described in the foregoing method embodiments.
In addition, each functional unit in the embodiments of the present invention may be integrated in one processing unit, or each unit may exist alone physically, or two or more units may be integrated in one unit. The integrated units may be implemented in hardware or in software functional units.
The integrated units, if implemented in the form of software functional units and sold or used as stand-alone products, may be stored in a computer readable memory. Based on this understanding, the technical solution of the present invention may be embodied essentially or partly in the form of a software product, or all or part of the technical solution, which is stored in a memory, and includes several instructions for causing a computer device (which may be a personal computer, a server, a network device, or the like) to perform all or part of the steps of the method according to the embodiments of the present invention. And the aforementioned memory includes: a usb disk, a Read-Only Memory (ROM), a random access Memory (RAM, random Access Memory), a removable hard disk, a magnetic disk, or an optical disk, or other various media capable of storing program codes.
Those of ordinary skill in the art will appreciate that all or a portion of the steps in the various methods of the above embodiments may be implemented by a program that instructs associated hardware, and the program may be stored in a computer readable memory, which may include: flash disk, read-Only Memory (ROM), random access Memory (Random Access Memory, RAM), magnetic disk or optical disk.
Exemplary flowcharts for determining a multicast path according to embodiments of the present invention are described above with reference to the accompanying drawings. It should be noted that the numerous details included in the above description are merely illustrative of the invention and not limiting of the invention. In other embodiments of the invention, the method may have more, fewer, or different steps, and the order, inclusion, functional relationship between steps may be different than that described and illustrated.
Claims (11)
1. A method for determining a multicast path, comprising:
obtaining topology information of a current network and network performance indexes;
calculating a path set between all (S, G) according to the topology information and the network performance index;
filtering path sets between the (S, G) according to constraint conditions, and screening out the path sets meeting the constraint conditions;
Traversing and combining the screened (S, G) path sets according to the same source to obtain a plurality of multicast tree path sets, wherein the method comprises the following steps: selecting the same multicast source S and path sets of different multicast groups G to form a path set group; traversing and combining the path set groups according to different groups G of the photographic source S, and obtaining m multicast tree path sets by multiplying all the path numbers in the path set;
and sequencing the multicast tree path sets according to the total number of the passed links, and screening the multicast tree paths with the minimum total number of the passed links to determine the optimal multicast path.
2. A determination method according to claim 1, characterized in that: the network performance index includes a delay of a link and traffic of an interface.
3. A determination method according to claim 1, characterized in that: calculating a set of paths between all (S, G) based on the topology information and network performance metrics, further comprising:
constructing a path calculation directed graph according to the topology information;
and reconstructing a path directed graph by taking the value of the network performance index as the weight of the edge in the directed weighted graph.
4. A determination method according to claim 3, wherein constructing a road map from the topology information further comprises:
and taking the nodes in the topology information as points of the path directional weighted graph, and taking the links in the topology information as edges of the path directional weighted graph to construct the path directional graph.
5. A determination method according to claim 1, characterized in that: the constraint condition is one or more of a bandwidth constraint value, a time delay constraint value, a necessary network element and a link, and a necessary network element and a link.
6. The determination method according to claim 5, wherein: filtering the path set between the (S, G) according to the constraint condition, screening out the path set meeting the constraint condition, and further comprising:
When the constraint condition is a bandwidth constraint value, screening out paths with residual bandwidths of each section of links in the path set between the (S, G) being greater than or equal to a preset bandwidth constraint value, and obtaining a path set meeting the constraint condition;
When the constraint condition is a time delay constraint value, screening out paths of which the sum of link time delays of the end-to-end paths in the path set between the (S, G) is smaller than or equal to a preset time delay constraint value, and obtaining a path set meeting the constraint condition;
When the constraint condition is that the network element and the link are needed to pass through, the end-to-end paths in the path set between the (S, G) are screened out, and all paths needed to pass through the network element and the link are contained, so that a path set meeting the constraint condition is obtained;
when the constraint condition is that the network elements and the links are necessary to be avoided, the end-to-end paths among the paths between the (S, G) are screened out, all the network elements and the links are eliminated, and the path set meeting the constraint condition is obtained.
7. The determination method according to claim 6, wherein: when a path is strictly specified, each hop of the computed path corresponds to each hop of the strictly path one by one.
8. A multicast path determining apparatus, comprising:
The acquisition unit is used for acquiring topology information and network performance indexes of the current network;
a calculation unit for calculating a set of paths between all (S, G) according to the topology information and the network performance index;
a first screening unit, configured to filter a path set between (S, G) according to a constraint condition, and screen a path set that satisfies the constraint condition;
the second screening unit is configured to traverse and combine the screened (S, G) path sets according to the same source to obtain a plurality of multicast tree path sets, and includes: selecting the same multicast source S and path sets of different multicast groups G to form a path set group; traversing and combining the path set groups according to different groups G of the photographic source S, and obtaining m multicast tree path sets by multiplying all the path numbers in the path set;
And the determining unit is used for sequencing the multicast tree path sets according to the total number of the passed links, and screening the multicast tree paths with the minimum total number of the passed links so as to determine the optimal multicast path.
9. The determination apparatus according to claim 8, wherein the calculation unit includes:
The first construction module is used for constructing a path-calculation directed graph according to the topology information;
and the second construction module is used for reconstructing the path directed graph by taking the value of the network performance index as the weight of the edge in the directed weighted graph.
10. The determining apparatus according to claim 8, wherein: the first screening unit includes:
The first filtering module is used for screening out paths with the residual bandwidth of each section of link in the path set between the (S, G) being greater than or equal to a preset bandwidth constraint value to obtain a path set meeting constraint conditions;
The second filtering module is used for screening out paths of which the sum of link delays of the end-to-end paths among the paths between the (S, G) is smaller than or equal to a preset time delay constraint value to obtain a path set meeting constraint conditions;
The third filtering module is used for screening out that the end-to-end paths in the path set between the (S, G) comprise all path sets which are required to be met by the paths of the network elements and the links; and the fourth filtering module is used for screening out the end-to-end paths in the path set between the (S, G) to exclude all the path sets which are needed to avoid network elements and links and meet the constraint condition.
11. A computer readable storage medium storing a computer program, characterized in that the computer program when executed by a processor implements the steps of a method of determining a multicast path according to any of claims 1 to 7.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210332813.5A CN114978982B (en) | 2022-03-30 | 2022-03-30 | Method and device for determining multicast path |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210332813.5A CN114978982B (en) | 2022-03-30 | 2022-03-30 | Method and device for determining multicast path |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN114978982A CN114978982A (en) | 2022-08-30 |
| CN114978982B true CN114978982B (en) | 2024-06-18 |
Family
ID=82975857
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202210332813.5A Active CN114978982B (en) | 2022-03-30 | 2022-03-30 | Method and device for determining multicast path |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN114978982B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115914047B (en) * | 2022-12-07 | 2024-07-02 | 中盈优创资讯科技有限公司 | Network quality testing method and device of TWAMP-based power calculation network |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110266600A (en) * | 2019-05-29 | 2019-09-20 | 西南电子技术研究所（中国电子科技集团公司第十研究所） | Bandwidth constraint multicast routing optimization method |
| CN112448886A (en) * | 2019-08-30 | 2021-03-05 | 中兴通讯股份有限公司 | Shortest path calculation method, route acquisition device and server |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106209622A (en) * | 2016-06-23 | 2016-12-07 | 广州海格通信集团股份有限公司 | A kind of method of multicasting based on SDN |
| US11664874B2 (en) * | 2019-02-15 | 2023-05-30 | Apple Inc. | System and method for dynamically configuring user equipment sounding reference signal (SRS) resources |
-
2022
- 2022-03-30 CN CN202210332813.5A patent/CN114978982B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110266600A (en) * | 2019-05-29 | 2019-09-20 | 西南电子技术研究所（中国电子科技集团公司第十研究所） | Bandwidth constraint multicast routing optimization method |
| CN112448886A (en) * | 2019-08-30 | 2021-03-05 | 中兴通讯股份有限公司 | Shortest path calculation method, route acquisition device and server |
Also Published As
| Publication number | Publication date |
|---|---|
| CN114978982A (en) | 2022-08-30 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN109194577B (en) | Traffic engineering method and device of segmented routing network based on partial deployment | |
| CN109922004B (en) | Traffic engineering method and device of IPv6 network based on partially deployed segmented routing | |
| Abuzaid et al. | Contracting wide-area network topologies to solve flow problems quickly | |
| CN107317697B (en) | Route configuration method of OSPF (open shortest Path first) and SDN (software defined network) hybrid network | |
| US10404576B2 (en) | Constrained shortest path determination in a network | |
| US9049145B2 (en) | Method and apparatus for calculating MPLS traffic engineering paths | |
| CN111147370A (en) | Method and control device for determining forwarding path | |
| CN103001892B (en) | Based on network resource allocation method and the system of cloud computing | |
| WO2021243585A1 (en) | Method and system for generating network configurations using graph neural network | |
| CN114978982B (en) | Method and device for determining multicast path | |
| CN115277429B (en) | Power communication service resource allocation method and device based on flexible Ethernet | |
| WO2023019604A1 (en) | Minimum network energy consumption optimization method and system based on traffic grooming | |
| EP3298735A1 (en) | Method and apparatus for self-tuned adaptive routing | |
| WO2023078150A1 (en) | Path calculation method, route calculation device, electronic device, and computer storage medium | |
| Doshi et al. | Multi-constraint QoS disjoint multipath routing in SDN | |
| El-Alfy et al. | A Pareto-based hybrid multiobjective evolutionary approach for constrained multipath traffic engineering optimization in MPLS/GMPLS networks | |
| CN110581806B (en) | Method, device and equipment for automatically segmenting network and storage medium | |
| CN105917621B (en) | Method and system for data routing | |
| US20060036762A1 (en) | System and method for automatic path generation in a computer network | |
| JP5723806B2 (en) | Communication system, path control device, path control method, and path control program | |
| Sheu et al. | Efficient unicast routing algorithms in Software-Defined Networking | |
| Callebaut et al. | Preprocessing for segment routing optimization | |
| Chooprateep et al. | Video path selection for traffic engineering in SDN | |
| Aibin | Deep learning for cloud resources allocation: Long-short term memory in EONs | |
| Markowski | Algorithms for deadline-driven dynamic multicast scheduling problem in elastic optical networks |
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 |