CN117135106A - Routing path planning method, routing request processing method, equipment and medium - Google Patents
Routing path planning method, routing request processing method, equipment and medium Download PDFInfo
- Publication number
- CN117135106A CN117135106A CN202311390582.4A CN202311390582A CN117135106A CN 117135106 A CN117135106 A CN 117135106A CN 202311390582 A CN202311390582 A CN 202311390582A CN 117135106 A CN117135106 A CN 117135106A
- Authority
- CN
- China
- Prior art keywords
- routing
- node
- code
- equal
- routing node
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
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/02—Topology update or discovery
-
- 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/14—Routing performance; Theoretical aspects
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D30/00—Reducing energy consumption in communication networks
- Y02D30/70—Reducing energy consumption in communication networks in wireless communication networks
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The present invention relates to the field of communications technologies, and in particular, to a routing path planning method, a routing request processing method, a device, and a medium. The routing path planning method comprises the following steps: respectively acquiring binary codes corresponding to terminal serial numbers of a source terminal node and a destination terminal node in a route request in a network topology to obtain a first code and a second code, wherein the network topology comprises at least one path ring; performing bit-wise exclusive OR operation on the remaining bits of the first code and the second code except the respective least significant bit to generate an initial third code; sequentially changing bits equal to one in the initial third codes into zero according to a preset sequence in response to at least one bit equal to one in the initial third codes to sequentially generate a plurality of third codes until only one bit in the generated third codes is equal to one; and generating a planning path according to the source terminal node, the destination terminal node and all third codes. The scheme of the invention can avoid the deadlock phenomenon, and improve the stability and communication efficiency of the network.
Description
Technical Field
The present invention relates to the field of communications technologies, and in particular, to a routing path planning method, a routing request processing method, a device, and a medium.
Background
With the rapid popularization and development of the internet and the continuous deployment of satellite internet constellation plans, more user terminals access to the network, the internet application including all fields of people production and living is derived, and the traffic in the internet has shown an explosive growth trend. The development and application of optical fiber technology and inter-satellite laser communication technology have led to the bottleneck of information transmission networks being transferred to switching devices, such as switches and routers, of switching nodes in the internet. The core technology of the switching devices is a switching technology, and the switching technology comprises two aspects of a switching network and a scheduling algorithm. In order to improve the performance of the information exchange network and meet the new application and service requirements which are continuously emerging nowadays, a higher-capacity and better-performance exchange network and a high-performance scheduling algorithm matched with the exchange network need to be researched.
With the improvement of the performance requirements of the switching network, the network topology is more complicated, the occurrence of deadlock, which is a condition that more than two data packets are blocked at an intermediate routing node and circulation waiting occurs between the release of network resources and requests, is avoided, and the communication efficiency is greatly reduced, so that the improvement of the routing algorithm is needed to avoid the occurrence of deadlock.
Disclosure of Invention
In view of the foregoing, it is desirable to provide a routing path planning method, a routing request processing method, a routing path planning apparatus, a device, and a medium.
According to a first aspect of the present invention, there is provided a routing path planning method comprising:
respectively acquiring binary codes corresponding to terminal serial numbers of a source terminal node and a destination terminal node in a route request in a network topology to obtain a first code and a second code, wherein the network topology comprises at least one path ring;
performing bitwise exclusive OR operation on the remaining bits of the first code and the second code except the respective least significant bit to generate an initial third code;
sequentially changing bits equal to one in the initial third codes into zero according to a preset sequence in response to at least one bit equal to one in the initial third codes to sequentially generate a plurality of third codes until only one bit in the generated third codes is equal to one;
and generating a planning path according to the source terminal node, the destination terminal node and all third codes.
In some embodiments, the step of generating a planned path from the source terminal node, the destination terminal node, and all third codes includes:
The route nodes where the source terminal node and the destination terminal node are located are respectively used as a first route node and a last route node, and an intermediate route node is determined according to the first route node and all third codes;
and combining the source terminal node, the destination terminal node, the first routing node, the intermediate routing node and the last routing node to obtain a planned path.
In some embodiments, the step of sequentially changing the bits equal to one in the initial third codes to zero in a preset order to sequentially generate a plurality of third codes includes:
taking the initial third code as the current third code;
changing the first bit equal to one from the lowest bit of the current third code to zero to obtain the next third code;
determining whether a bit equal to one in a subsequent third code is greater than one;
in response to the bit equal to one in the next third code being greater than one, the next third code is taken as the current third code, and the step of changing the first bit equal to one to zero from the lowest bit of the current third code is performed.
In some embodiments, the step of sequentially changing the bits equal to one in the initial third codes to zero in a preset order to sequentially generate a plurality of third codes includes:
Taking the initial third code as the current third code;
changing the first bit equal to one from the highest bit of the current third code to zero to obtain the next third code;
judging whether the number of bits equal to one in the next third code is greater than one;
in response to the number of bits equal to one in the next third code being greater than one, the next third code is taken as the current third code, and the step of changing the first equal bit to one from the highest bit of the current third code to zero is performed.
In some embodiments, the step of determining an intermediate routing node from the first routing node, all third encodings, comprises:
sequentially performing bit exclusive OR operation on two adjacent third codes from the first third code to generate a fourth code with sequence;
taking a binary code corresponding to the first routing node as a target code;
selecting a fourth code and the target code according to the sequence from front to back to perform bit-wise exclusive-or operation, and taking the result of the bit-wise exclusive-or operation as a binary code corresponding to the sequence number of an intermediate routing node;
taking the binary code corresponding to the latest generated intermediate routing node sequence number as a new target code, and returning to execute the step of selecting the fourth code and the target code from front to back in sequence to perform bitwise exclusive OR operation until all the fourth codes are traversed.
In some embodiments, the step of combining the source terminal node, the destination terminal node, the first routing node, the intermediate routing node, and the last routing node to obtain a planned path includes:
respectively taking a source terminal node and the destination terminal node as a starting point and an ending point of a planned path;
and placing the first routing node and the intermediate routing nodes which are sequentially generated between the starting point and the ending point to generate a planned path.
In some embodiments, the routing path planning method further comprises:
and in response to all bits in the initial third code being equal to zero, confirming that the source terminal node and the destination terminal node are in the same routing node.
In some embodiments, the routing path planning method further comprises:
and setting the planned paths of the source terminal node and the destination terminal node to take the source terminal node as a starting point, the same routing node as an intermediate routing node and the destination terminal node as an ending point.
In some embodiments, the routing path planning method further comprises:
determining first route information from the source terminal node to a first route node in the planned route according to the last bit of the first code; and
And determining second routing information from the last routing node to the destination terminal node in the planned path according to the last bit of the second code.
In some embodiments, the network topology includes at least four routing nodes, wherein each routing node connects two end nodes, and two end node serial numbers connected to the same routing node are equal to two times the connected routing node serial number and two times the connected routing node serial number plus one, respectively.
In some embodiments, the path loops in the network topology are each comprised of four routing nodes.
In some embodiments, the network topology includes eight routing nodes with routing node numbers 0 through 7;
the connection relation of the routing nodes in the network topology comprises the following steps:
the routing node with the routing node serial number equal to 0 is respectively communicated with the routing nodes with the routing node serial numbers equal to 1, 2 and 4 in two directions;
the routing node with the routing node serial number equal to 1 is respectively communicated with the routing nodes with the routing node serial numbers equal to 3 and 5 in a two-way mode;
the routing node with the routing node serial number equal to 2 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 3 and 6;
the routing node with the routing node serial number equal to 3 is also respectively and bidirectionally communicated with the routing node serial number equal to 7;
The routing node with the routing node serial number equal to 4 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 5 and 6;
the routing nodes with the routing node serial numbers equal to 5 and 6 are respectively communicated with the routing nodes with the routing node serial number equal to 7 in a two-way mode.
In some embodiments, the network topology includes four routing nodes with routing node numbers 8-11;
the connection relation of the routing nodes in the network topology further comprises:
the routing node with the routing node serial number equal to 8 is respectively communicated with the routing nodes with the routing node serial numbers equal to 0, 9 and 10 in a two-way manner;
the routing node with the routing node serial number equal to 9 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 1 and 11;
the routing node with the routing node serial number equal to 10 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 2 and 11;
the routing nodes with the routing node serial numbers equal to 11 are respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 3.
In some embodiments, the network topology includes four routing nodes with routing node numbers 12-15;
the connection relation of the routing nodes in the network topology further comprises:
the routing node with the routing node serial number equal to 12 is respectively communicated with the routing nodes with the routing node serial numbers equal to 4, 8, 13 and 14 in a two-way manner;
The routing node with the routing node serial number equal to 13 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 5, 9 and 15;
the routing node with the routing node serial number equal to 14 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers 6, 10 and 15;
the routing nodes with the routing node serial numbers equal to 15 are respectively communicated with the routing nodes with the routing node serial numbers equal to 7 in a two-way mode.
According to a second aspect of the present invention, there is provided a route request processing method, the route request processing method further comprising:
and in response to the existence of the unexecuted first routing request and the receipt of the second routing request, determining a planned path for the second routing request through the routing path planning method.
In some embodiments, the routing request processing method further includes:
and responding to the concurrent generation of a plurality of third routing requests, and respectively determining a planned path for each third routing request through the routing path planning method.
According to a third aspect of the present invention, there is provided a routing path planning apparatus, the apparatus comprising:
the acquisition module is configured to acquire binary codes corresponding to terminal serial numbers of a source terminal node and a destination terminal node in a route request in a network topology respectively so as to acquire a first code and a second code, wherein the network topology comprises at least one path ring;
An operation module configured to perform a bitwise exclusive-or operation on remaining bits of the first code and the second code except for respective least significant bits to generate an initial third code;
a changing module, configured to respond to at least one bit in the initial third code being equal to one, and sequentially change the bit equal to one in the initial third code to zero according to a preset sequence to sequentially generate a plurality of third codes until only one bit in the generated third codes is equal to one;
and the generation module is configured to generate a planning path according to the source terminal node, the destination terminal node and all third codes.
According to a fourth aspect of the present invention, there is also provided an electronic device including:
at least one processor; and
and the memory stores a computer program which can be run on a processor, and the processor executes the routing path planning method when executing the program.
According to a fifth aspect of the present invention there is also provided a computer readable storage medium storing a computer program which when executed by a processor performs the aforementioned routing path planning method.
According to the route path planning method, partial bit exclusive OR operation is carried out according to the first code and the second code corresponding to the source terminal serial number and the destination terminal serial number of the route request to generate the third code, a change mode is designated for the third code to generate the third code with sequence, and finally, a unique planning path from the source terminal node to the destination terminal node is generated according to the first code, the second code and all the third codes.
In addition, the invention also provides a routing request processing method, a routing path planning device, an electronic device and a computer readable storage medium, which can also realize the technical effects and are not repeated here.
Drawings
In order to more clearly illustrate the embodiments of the invention or the technical solutions in the prior art, the drawings that are necessary for the description of the embodiments or the prior art will be briefly described, it being obvious that the drawings in the following description are only some embodiments of the invention and that other embodiments may be obtained according to these drawings without inventive effort for a person skilled in the art.
Fig. 1 is a flowchart of a routing path planning method according to an embodiment of the present invention;
FIG. 2 is a diagram of a unidirectional 32-port button network topology according to one embodiment of the present invention;
FIG. 3 is a schematic diagram of a topology of the batterfly network of FIG. 3 according to an embodiment of the present invention;
FIG. 4 is an equivalent schematic diagram of the network topology shown in FIG. 3;
FIG. 5 is a schematic view of the path ring taken from FIG. 4;
FIG. 6 is a schematic diagram of four requests producing a deadlock clockwise;
FIG. 7 is a schematic diagram of four requests creating a deadlock counter-clockwise;
FIG. 8 is a schematic diagram of a "1-2-4-8" routing algorithm according to one embodiment of the present invention;
FIG. 9 is a routing path of routing nodes 2 through 7 through a "1-2-4-8" routing algorithm;
FIG. 10 is a routing path of routing nodes 3 through 6 through a "1-2-4-8" routing algorithm;
FIG. 11 is a routing path of routing nodes 7 through 2 through a "1-2-4-8" routing algorithm;
FIG. 12 is a routing path of routing nodes 6 through 3 through a "1-2-4-8" routing algorithm;
fig. 13 is a schematic structural diagram of a routing path planning apparatus according to another embodiment of the present invention;
FIG. 14 is an internal block diagram of an electronic device in accordance with another embodiment of the present invention;
Fig. 15 is a block diagram of a computer readable storage medium according to another embodiment of the present invention.
Detailed Description
In order to make the objects, technical solutions and advantages of the present invention more apparent, the following embodiments of the present invention will be further described in detail with reference to the accompanying drawings.
It should be noted that, in the embodiments of the present invention, all the expressions "first" and "second" are used to distinguish two entities with the same name but different entities or different parameters, and it is noted that the "first" and "second" are only used for convenience of expression, and should not be construed as limiting the embodiments of the present invention, and the following embodiments are not described one by one.
In one embodiment, referring to fig. 1, the present invention provides a routing path planning method 100, specifically, the routing path planning method includes the following steps:
step 101, respectively obtaining binary codes corresponding to terminal serial numbers of a source terminal node and a destination terminal node in a route request in a network topology to obtain a first code and a second code, wherein the network topology comprises at least one path ring;
in this embodiment, the routing request refers to a communication request of two terminal nodes, and it is not necessary to assume that when the terminal node 0 needs to send data to the terminal node 3 in a certain scenario, the routing request is generated to plan a routing node that the terminal node 3 passes through to the terminal node 3, it is to be noted that the routing request is directional, the terminal node sending the data packet is a source terminal node, the terminal node receiving the data packet is a destination terminal node, and the terminal node 3 may also send the data packet to the terminal node 0, and the request is generated to plan a routing node that the terminal node 3 passes through to the terminal node 0. It should be noted that, in the routing request related to this embodiment, the number of the terminal node is only used for illustration, and should not be construed as limiting the scheme of the present invention, and in the specific implementation process, the needs of the source terminal node and the destination terminal node may be flexibly changed according to the specific service scenario.
In this implementation process, the network topology may be any existing switching network topology, for example, a button network topology, a fat tree network topology, etc., where each routing node and each terminal node in the network topology have their corresponding sequence numbers. The path rings are ring-changing structures formed by sequentially connecting at least three routing nodes, and it is to be noted that the number of the path rings and the number of the routing nodes included in each path ring are used as examples, and can be set according to requirements in the implementation process, and the method is not to be construed as limiting the scheme of the invention.
102, performing bit-wise exclusive OR operation on the residual bits except the respective least significant bits of the first code and the second code to generate an initial third code;
in this embodiment, the number of bits of the first code and the second code is equal to the number of binary digits of the maximum terminal node number in the network topology, for example, the number of binary digits includes 32 terminal nodes, the maximum terminal node number is equal to 31, and 31 needs 5 binary digits to represent each terminal node number, which is not limited to the case that the source terminal node terminal number is equal to 2 and the destination terminal node number is equal to 31, and the first code is denoted as "00010" and the second code is denoted as "11111". It should be noted that, the number of bits of the first code and the second code is set according to the number of nodes included in the network topology, for example, if a certain network topology includes only 16 terminal nodes, the first code and the second code can be represented by using four-bit binary system at this time, and at this time, 5-bit binary system representation is not necessary.
In this embodiment, the rightmost one of the binary codes of the lowest digit does not participate in the operation in the third code calculation, and the portion of the first code participating in the operation is represented as "0001" and the portion of the second code participating in the operation is represented as "1111" by way of example. The bitwise exclusive-or operation means that the numerical values of the corresponding bits of the first code and the second code are subjected to exclusive-or rules such as: the corresponding bit value in the third code is generated to be 0 if the values of the corresponding bits are the same, the corresponding bit value on the third code is generated to be 1 if the values of the corresponding bits are different, and the third code generated by bitwise exclusive or of 0001 and 1111 is expressed as 1110 according to the calculation rule.
Step 103, in response to at least one bit in the initial third codes being equal to one, sequentially changing the bit equal to one in the initial third codes to zero according to a preset sequence to sequentially generate a plurality of third codes until only one bit in the generated third codes is equal to one;
in this embodiment, the preset sequence is a preset sequence of changing the bits of the third code equal to one, for example, the sequence may be preset from the low order to the high order or from the low order to the high order, or may be any sequence, for example, the sequence may be preset from the middle to the left side and then from the middle to the right side.
Continuing with the example, if the third code "1110" is changed in the order from low to high, new third codes "1100" and "1000" are sequentially obtained after the change, and if the new third codes are changed in the order from high to low, the new third codes are "0110" and "0010" are sequentially obtained.
And 104, generating a planned path according to the source terminal node, the destination terminal node and all third codes.
According to the route path planning method, partial bit exclusive OR operation is carried out according to the first code and the second code corresponding to the source terminal serial number and the destination terminal serial number of the route request to generate a third code, a change mode is designated for the third code to generate a third code with sequence, and finally, a unique planning path from the source terminal node to the destination terminal node is generated according to the first code, the second code and all the third codes.
In some embodiments, the foregoing step 104 of generating a planned path according to the source terminal node, the destination terminal node, and all third codes includes:
The route nodes where the source terminal node and the destination terminal node are located are respectively used as a first route node and a last route node, and an intermediate route node is determined according to the first route node and all third codes;
and combining the source terminal node, the destination terminal node, the first routing node, the intermediate routing node and the last routing node to obtain a planned path.
According to the path planning method, the source terminal node and the destination terminal node determine the first two routing nodes of the planned path, the changed third codes are utilized to determine the middle routing nodes of the planned path, and the planned paths formed by all the determined routing nodes are combined according to the sequence, so that the shortest planned path can be ensured, the path is unique, the algorithm is simple, and the path planning is accurate.
In some embodiments, in the foregoing step 103, sequentially changing the bits equal to one in the initial third codes to zero according to a preset sequence to sequentially generate a plurality of third codes includes:
taking the initial third code as the current third code;
changing the first bit equal to one from the lowest bit of the current third code to zero to obtain the next third code;
Determining whether a bit equal to one in a subsequent third code is greater than one;
in response to the bit equal to one in the next third code being greater than one, the next third code is taken as the current third code, and the step of changing the first bit equal to one to zero from the lowest bit of the current third code is performed.
According to the routing path planning method, the third coding conversion sequence is designated as the sequence from low order to high order, so that the third coding with the sequence is generated, the third coding can be used for indicating the intermediate routing nodes required to pass through in the path, the deadlock phenomenon can be avoided, and the stability and the communication efficiency of the network are greatly improved.
In some embodiments, in the foregoing step 103, the sequentially changing the bits equal to one in the initial third codes to zero according to a preset sequence to sequentially generate a plurality of third codes includes:
taking the initial third code as the current third code;
changing the first bit equal to one from the highest bit of the current third code to zero to obtain the next third code;
judging whether the number of bits equal to one in the next third code is greater than one;
In response to the number of bits equal to one in the next third code being greater than one, the next third code is taken as the current third code, and the step of changing the first equal bit to one from the highest bit of the current third code to zero is performed.
According to the routing path planning method, the third coding conversion sequence is designated as the sequence from high order to low order, so that the third coding with the sequence is generated, the third coding can be used for indicating the intermediate routing nodes required to pass through in the path, the deadlock phenomenon can be avoided, and the stability and the communication efficiency of the network are greatly improved.
In some embodiments, the step of determining an intermediate routing node from the first routing node, all third encodings, comprises:
sequentially performing bit exclusive OR operation on two adjacent third codes from the first third code to generate a fourth code with sequence;
taking a binary code corresponding to the first routing node as a target code;
selecting a fourth code and the target code according to the sequence from front to back to perform bit-wise exclusive-or operation, and taking the result of the bit-wise exclusive-or operation as a binary code corresponding to the sequence number of an intermediate routing node;
Taking the binary code corresponding to the latest generated intermediate routing node sequence number as a new target code, and returning to execute the step of selecting the fourth code and the target code from front to back in sequence to perform bitwise exclusive OR operation until all the fourth codes are traversed.
According to the path planning method, the third codes generated in sequence are operated to generate the fourth codes with the sequence, and the intermediate routing nodes with the sequence are found by utilizing the fourth codes with the sequence and the first routing node, so that a unique planning path is accurately obtained, and the accuracy is high.
In some embodiments, the step of combining the source terminal node, the destination terminal node, the first routing node, the intermediate routing node, and the last routing node to obtain a planned path includes:
respectively taking a source terminal node and the destination terminal node as a starting point and an ending point of a planned path;
and placing the first routing node and the intermediate routing nodes which are sequentially generated between the starting point and the ending point to generate a planned path.
A path planning method of the embodiment gives a specific combination sequence to all the determined routing nodes, specifically takes the routing node of the source terminal node as a starting point, takes the routing node of the destination terminal node as an ending point, and inserts the routing node between the starting point and the ending point according to the determined generation sequence of the intermediate routing node.
In some embodiments, the routing path planning method further comprises:
and in response to all bits in the initial third code being equal to zero, confirming that the source terminal node and the destination terminal node are in the same routing node.
In some embodiments, the routing path planning method further comprises:
and setting the planned paths of the source terminal node and the destination terminal node to take the source terminal node as a starting point, the same routing node as an intermediate point and the destination terminal node as an ending point.
In some embodiments, the routing path planning method further comprises:
determining first route information from the source terminal node to a first route node in the planned route according to the last bit of the first code; and
and determining second routing information from the last routing node to the destination terminal node in the planned path according to the last bit of the second code.
In some embodiments, the network topology includes at least four routing nodes, wherein each routing node connects two end nodes, and two end node serial numbers connected to the same routing node are equal to two times the connected routing node serial number and two times the connected routing node serial number plus one, respectively.
In some embodiments, the path loops in the network topology are each comprised of four routing nodes.
In some embodiments, the network topology includes eight routing nodes with routing node numbers 0 through 7;
the connection relation of the routing nodes in the network topology comprises the following steps:
the routing node with the routing node serial number equal to 0 is respectively communicated with the routing nodes with the routing node serial numbers equal to 1, 2 and 4 in two directions;
the routing node with the routing node serial number equal to 1 is respectively communicated with the routing nodes with the routing node serial numbers equal to 3 and 5 in a two-way mode;
the routing node with the routing node serial number equal to 2 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 3 and 6;
the routing node with the routing node serial number equal to 3 is also respectively and bidirectionally communicated with the routing node serial number equal to 7;
the routing node with the routing node serial number equal to 4 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 5 and 6;
the routing nodes with the routing node serial numbers equal to 5 and 6 are respectively communicated with the routing nodes with the routing node serial number equal to 7 in a two-way mode.
In some embodiments, the network topology includes four routing nodes with routing node numbers 8-11;
the connection relation of the routing nodes in the network topology further comprises:
The routing node with the routing node serial number equal to 8 is respectively communicated with the routing nodes with the routing node serial numbers equal to 0, 9 and 10 in a two-way manner;
the routing node with the routing node serial number equal to 9 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 1 and 11;
the routing node with the routing node serial number equal to 10 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 2 and 11;
the routing nodes with the routing node serial numbers equal to 11 are respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 3.
In some embodiments, the network topology includes four routing nodes with routing node numbers 12-15;
the connection relation of the routing nodes in the network topology further comprises:
the routing node with the routing node serial number equal to 12 is respectively communicated with the routing nodes with the routing node serial numbers equal to 4, 8, 13 and 14 in a two-way manner;
the routing node with the routing node serial number equal to 13 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 5, 9 and 15;
the routing node with the routing node serial number equal to 14 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers 6, 10 and 15;
the routing nodes with the routing node serial numbers equal to 15 are respectively communicated with the routing nodes with the routing node serial numbers equal to 7 in a two-way mode.
The routing path planning method is suitable for the network topology with the path loops, particularly suitable for the network topology with a plurality of complex and crossed path loops, capable of solving the problem of multi-deadlock caused by the fact that the path loops are crossed with each other, and high in flexibility and universality.
In order to facilitate understanding of the scheme of the present invention, taking a topology structure applied to a button network as an example, the following describes in detail the routing path planning method of the present invention, the implementation principle is based on the topology structure of the flattened button network, and a routing manner for avoiding deadlock is provided, and the specific implementation process is as follows:
from fig. 2, which shows a modified butterfly topology, the number of routing nodes in each layer is the same, and path uniqueness and load imbalance are main reasons for limiting the development of the topology. Path uniqueness causes it to be prone to blocking.
Fig. 3 is a flattened butterfly network structure 200, fig. 3 is a terminal node 201, a routing node 202, and several layers of routing nodes at the same position are combined, so that the number of routing nodes is effectively reduced. And solves the problem of the uniqueness of the button path. The network structure diagram shown in fig. 3 is subjected to certain topology planning to form a network topology diagram shown in fig. 4. Each routing node 202 links two end nodes 201, only a portion of the end nodes 201 being shown for ease of illustration. The number of the routing nodes is greatly reduced, the number of links is twice that of a butterfly network, and the network diameter is the same as that of the butterfly network. It can be seen from fig. 4 that the flattened butterfly solves the problem of the uniqueness of the butterfly path, but is prone to deadlock because its network topology contains "loops". To avoid deadlock, the routing algorithm may limit its routing path, causing the problem of its path uniqueness to reappear.
Traditional routing algorithms:
for a total of 32 end nodes in fig. 3, we use 5 bits to represent each end node, such as: 00000 represents terminal node 0, 00001 represents terminal node 1, … …,11110 represents terminal node 30, 11111 represents terminal node 31; fig. 4 shows a total of 16 routing nodes, where the first 4 bits of 5 bits are denoted routing node 0, e.g. 0000_routing node 0, 0001_routing node 1, … …, 1110_routing node 14, 1111_routing node 15.
Assuming that the source terminal node is S and the destination terminal node is D, a routing algorithm is described below:
the first step: the source terminal node S and the destination terminal node D are exclusive-ored according to the bits, and the result is recorded as I;
and a second step of: checking the first 4 bits of the I, if the first 4 bits are all 0, proving that the source terminal node S and the destination terminal node D are in the same routing node, and directly routing in the routing node. For example, assuming that the source terminal node S is 00110 (6), the destination terminal node D is 00111 (7), bitwise exclusive or is followed by I being 00001, and the first 4 bits are all 0, these two terminal nodes are on one routing node (i.e., on routing node 3), then routing can be performed directly inside the routing node 3.
If the first 4 bits of I are not all 0, the first 4 bits containing k represent that k+1 nodes need to pass from the source terminal node S to the destination terminal node D. For example, assuming that the source terminal node S is 00010 (2), the destination terminal node D is 11111 (31), bitwise exclusive or is followed by I being 11101, the first 4 bits contain 3 1S, then from the source terminal node S:00010 (0) to destination terminal node D:11111 (31) 4 routing nodes are required.
And a third step of: a method for determining routing nodes. Still further, as an example of the second step, source end node S is 00010 (2) at routing node 1. Sup. St. Route node 0001. Sup. Nd end node D is 11111 (31) at routing node 15. Sup. St route node 1111. Sup. Nd. The first 3 bits in the I are 1, the information of the first 3 bits of the 1 st routing node 0001_is changed in sequence according to a random mode (the first 3 bits are changed into 1 if the first 3 bits are 0 and are changed into 0 if the first 3 bits are 1), each bit of the routing node is changed, the 1 in the corresponding bits in the I is also changed into 0, the routing between the routing nodes is finished until all bits in the I are 0, and the routing information is routed to the terminal node according to the last bit of the D. In a random manner, the routing may have the following result:
0001_(I:1110_)->0011_(I:1100_)->0111_(I:1000_)->1111_(I:0000_)
0001_(I:1110_)->0011_(I:1100_)->1011_(I:0100_)->1111_(I:0000_)
0001_(I:1110_)->0101_(I:1010_)->0111_(I:1000_)->1111_(I:0000_)
0001_(I:1110_)->0101_(I:1010_)->1101_(I:1000_)->1111_(I:0000_)
0001_(I:1110_)->1001_(I:0110_)->1011_(I:0100_)->1111_(I:0000_)
0001_(I:1110_)->1001_(I:0110_)->1101_(I:0010_)->1111_(I:0000_)
in the third step, the random routing mode is simple to implement, but when the ring topology exists in the flattening of the button, a deadlock phenomenon can occur in some extreme scenes, so that the problem of deadlock needs to be solved in some scenes.
Referring to FIG. 5, FIG. 5 is a ring taken from FIG. 4, and the generation of deadlock will be described in connection with the ring:
for fig. 5, which is a ring topology, deadlock is easily created. For example, suppose there are four routing requests simultaneously: request 1: routing node 2 to routing node 7; request 2: routing node 3 to routing node 6; request 3: routing node 7 to routing node 2; request 4: a deadlock occurs when all four route requests need to pass through one route node and all route clockwise and all occupy intermediate route nodes, as in fig. 6, from route node 6 to route node 3. If instead all counter-clockwise routes are selected and all intermediate routing nodes are already occupied, a deadlock will also occur, as in fig. 7.
Once the deadlock occurs, the internet is fully paralyzed, so a routing algorithm for avoiding the deadlock must be found. Therefore, the invention improves the traditional routing algorithm and provides a routing algorithm which is suitable for flattening the button and can avoid deadlock.
Improved routing algorithm:
the reason for the deadlock is that because there is a "ring" in the topology and there is no restriction on the routing paths, we have restricted the routing paths and we propose a "1-2-4-8" routing algorithm:
For example, assuming that the source terminal node S is 00010 (2), the destination terminal node D is 11111 (31), bitwise exclusive or is followed by I being 11101, we consider only the first 4 bits of I to be 1110_; as shown in fig. 8, according to our proposed "1-2-4-8" routing algorithm, 1 of "1-2-4-8" of I is changed to 0 in turn:
the routing results are as follows:
0001_(I:1110_)->0011_(I:1100_)->0111_(I:1000_)->1111_(I:0000_)
still taking the four routing requests described above as an example: request 1: routing node 2 to routing node 7; request 2: routing node 3 to routing node 6; request 3: routing node 7 to routing node 2; request 4: routing node 6 to routing node 3.
Referring to fig. 9, request 1: routing node 2 to routing node 7; s is 0010_, D is 0111_, I is 0101_ after bit exclusive OR, and the routing result is as follows:
0010_(I:0101_)->0011_(I:0100_)->0111_(I:0000_)
referring to fig. 10, request 2: routing node 3 to routing node 6; s is 0011_, D is 0110_, I is 0101_ after bit exclusive OR, and the routing result is as follows:
0011_(I:0101_)->0010_(I:0100_)->0110_(I:0000_)
referring to fig. 11, request 3: routing node 7 to routing node 2; s is 0111_, D is 0010_, I is 0101_ after bit exclusive OR, and the routing result is as follows:
0111_(I:0101_)->0110_(I:0100_)->0010_(I:0000_)
please refer to fig. 12, request 4: routing node 6 to routing node 3; s is 0110_, D is 0011_, I is 0101_ after bit exclusive OR, and the routing result is as follows:
0110_(I:0101_)->0111_(I:0100_)->0011_(I:0000_)
Although the topology in which requests 1-4 are located has loops and the possibility of deadlock of routing requests as well (fig. 6 and 7), it can be seen from fig. 9-12 that the generation of deadlock is avoided by the "1-2-4-8" routing algorithm.
The following describes in detail a path planning procedure from a source terminal node to a destination terminal node by way of example:
the first step: the source terminal node S and the destination terminal node D are exclusive-ored according to the bits, and the result is recorded as I;
and a second step of: checking the first 4 bits of the I, if the first 4 bits are all 0, proving that the source terminal node S and the destination terminal node D are in the same routing node, and directly routing in the routing node. For example, assuming that the source terminal node S is 00110 (6), the destination terminal node D is 00111 (7), the bit exclusive or is followed by I being 00001, and the first 4 bits are all 0, these two terminal nodes are on one routing node (routing node 7), then the routing is performed directly inside.
If the first 4 bits of I are not all 0, the first 4 bits containing k represent that k+1 nodes need to pass from the source terminal node S to the destination terminal node D. For example, assuming that the source terminal node S is 00010 (2), the destination terminal node D is 11111 (31), bitwise exclusive or is followed by I being 11101, the first 4 bits contain 3 1S, then from the source terminal node S:00010 (0) to destination terminal node D:11111 (31) 4 routing nodes are required.
And a third step of: a method for determining routing nodes. Still further, as an example of the second step, source end node S is 00010 (2) at routing node 1. Sup. St. Route node 0001. Sup. Nd end node D is 11111 (31) at routing node 15. Sup. St route node 1111. Sup. Nd. The first 3 bits in I are 1, the routing is carried out according to the sequence of 1-2-4-8, the information of the first 3 bits of the 1 st routing node 0001_is changed in sequence (the first 3 bits are changed to 1 if 0 and are changed to 0 if 1 is changed to 0), the information of each bit of the routing node is changed to 0 if the corresponding bits in I are changed to 0, the routing between the routing nodes is finished until all bits in I are 0, and the routing information is routed to the terminal node according to the last bit of D. Routing is carried out according to the sequence of 1-2-4-8, and the routing result is as follows:
0001_(I:1110_)->0011_(I:1100_)->0111_(I:1000_)->1111_(I:0000_)
instead of changing from six paths to one path, more than the above example, only one path remains for all routing requests, i.e., the routing path is unique.
The routing path planning method applied to the button network topology of the embodiment provides a routing algorithm for avoiding deadlock, the routing algorithm limits the routing path, the routing algorithm is simple, and the routing path is unique.
According to another aspect of the present invention, the present invention also provides a routing request processing method, including:
And in response to the existence of the unexecuted first routing request and the receipt of the second routing request, determining a planned path for the second routing request through the routing path planning method described in the above embodiment.
In this embodiment, the first routing request may use any existing routing algorithm to plan a path, for example, a random algorithm, where the first routing request is performed completely, that is, the first routing request uses the planned path to perform data transmission, and there is a situation that routing nodes in the planned path are occupied.
According to the route request processing method, the execution state of the route request is combined, and the route path is generated for the route request which possibly causes node conflict by adopting the route planning mode of the scheme, so that on one hand, the route path can not be limited under the condition that the request quantity is not large or the nodes are not occupied, on the other hand, the occurrence of deadlock phenomenon can be avoided, and the communication stability is improved.
In some embodiments, the routing request processing method further includes:
and in response to the concurrent generation of a plurality of third routing requests, determining a planned path for each of the third routing requests by the routing path planning method described in the above embodiment.
According to the route request processing method, aiming at concurrent route requests, the route path planning method is directly adopted to generate a unique path for each concurrent route request, so that concurrent route requests can be timely handled, deadlock phenomenon is avoided, and communication stability is further improved.
In some embodiments, referring to fig. 13, the present invention further provides a routing path planning apparatus 300, which includes:
an obtaining module 301, configured to obtain binary codes corresponding to terminal serial numbers of a source terminal node and a destination terminal node in a route request respectively in a network topology, so as to obtain a first code and a second code, where the network topology includes at least one path ring;
an operation module 302 configured to perform a bitwise exclusive-or operation on remaining bits of the first code and the second code except for respective least significant bits to generate an initial third code;
a changing module 303, configured to sequentially change bits equal to one in the initial third codes to zero according to a preset sequence in response to at least one bit equal to one in the initial third codes, so as to sequentially generate a plurality of third codes until only one bit in the generated third codes is equal to one;
A generating module 304, configured to generate a planned path according to the source terminal node, the destination terminal node and all third codes.
According to the route path planning device, partial bit exclusive OR operation is carried out according to the first code and the second code corresponding to the source terminal serial number and the destination terminal serial number of the route request to generate a third code, a change mode is designated for the third code to generate a third code with sequence, and finally, a unique planning path from the source terminal node to the destination terminal node is generated according to the first code, the second code and all the third codes.
It should be noted that, for specific limitation of the routing path planning apparatus, reference may be made to the limitation of the routing path planning method in the above description, and no further description is given here. The various modules in the routing path planning apparatus described above may be implemented in whole or in part by software, hardware, and combinations thereof. The above modules may be embedded in hardware or independent of a processor in the electronic device, or may be stored in software in a memory in the electronic device, so that the processor may call and execute operations corresponding to the above modules.
According to another aspect of the present invention, there is provided an electronic device, which may be a server, and an internal structure thereof is shown in fig. 14. The electronic device includes a processor, a memory, a network interface, and a database connected by a system bus. Wherein the processor of the electronic device is configured to provide computing and control capabilities. The memory of the electronic device includes a nonvolatile storage medium and an internal memory. The non-volatile storage medium stores an operating system, computer programs, and a database. The internal memory provides an environment for the operation of the operating system and computer programs in the non-volatile storage media. The database of the electronic device is for storing data. The network interface of the electronic device is used for communicating with an external terminal through a network connection. The computer program when executed by a processor implements the above-described routing path planning method or the above-described routing request processing method, specifically, the routing path planning method includes the steps of:
respectively acquiring binary codes corresponding to terminal serial numbers of a source terminal node and a destination terminal node in a route request in a network topology to obtain a first code and a second code, wherein the network topology comprises at least one path ring;
Performing bitwise exclusive OR operation on the remaining bits of the first code and the second code except the respective least significant bit to generate an initial third code;
sequentially changing bits equal to one in the initial third codes into zero according to a preset sequence in response to at least one bit equal to one in the initial third codes to sequentially generate a plurality of third codes until only one bit in the generated third codes is equal to one;
generating a planning path according to the source terminal node, the destination terminal node and all third codes;
the routing request processing method comprises the following steps:
and in response to the existence of the unexecuted first routing request and the receipt of the second routing request, determining a planned path for the second routing request through the routing path planning method.
According to still another aspect of the present invention, there is provided a computer readable storage medium, as shown in fig. 15, having a computer program stored thereon, the computer program when executed by a processor implementing the above-mentioned routing path planning method or the above-mentioned routing request processing method, specifically, the routing path planning method includes the steps of:
Respectively acquiring binary codes corresponding to terminal serial numbers of a source terminal node and a destination terminal node in a route request in a network topology to obtain a first code and a second code, wherein the network topology comprises at least one path ring;
performing bitwise exclusive OR operation on the remaining bits of the first code and the second code except the respective least significant bit to generate an initial third code;
sequentially changing bits equal to one in the initial third codes into zero according to a preset sequence in response to at least one bit equal to one in the initial third codes to sequentially generate a plurality of third codes until only one bit in the generated third codes is equal to one;
generating a planning path according to the source terminal node, the destination terminal node and all third codes;
the routing request processing method comprises the following steps:
and in response to the existence of the unexecuted first routing request and the receipt of the second routing request, determining a planned path for the second routing request through the routing path planning method.
Those skilled in the art will appreciate that implementing all or part of the above described methods may be accomplished by way of a computer program stored on a non-transitory computer readable storage medium, which when executed, may comprise the steps of the embodiments of the methods described above. Any reference to memory, storage, database, or other medium used in embodiments provided herein may include non-volatile and/or volatile memory. The nonvolatile memory can include Read Only Memory (ROM), programmable ROM (PROM), electrically Programmable ROM (EPROM), electrically Erasable Programmable ROM (EEPROM), or flash memory. Volatile memory can include Random Access Memory (RAM) or external cache memory. By way of illustration and not limitation, RAM is available in a variety of forms such as Static RAM (SRAM), dynamic RAM (DRAM), synchronous DRAM (SDRAM), double Data Rate SDRAM (DDRSDRAM), enhanced SDRAM (ESDRAM), synchronous Link DRAM (SLDRAM), memory bus direct RAM (RDRAM), direct memory bus dynamic RAM (DRDRAM), and memory bus dynamic RAM (RDRAM), among others.
The technical features of the above embodiments may be arbitrarily combined, and all possible combinations of the technical features in the above embodiments are not described for brevity of description, however, as long as there is no contradiction between the combinations of the technical features, they should be considered as the scope of the description.
The above examples illustrate only a few embodiments of the application, which are described in detail and are not to be construed as limiting the scope of the application. It should be noted that it will be apparent to those skilled in the art that several variations and modifications can be made without departing from the spirit of the application, which are all within the scope of the application. Accordingly, the scope of protection of the present application is to be determined by the appended claims.
Claims (19)
1. A routing path planning method, characterized in that the routing path planning method comprises:
respectively acquiring binary codes corresponding to terminal serial numbers of a source terminal node and a destination terminal node in a route request in a network topology to obtain a first code and a second code, wherein the network topology comprises at least one path ring;
performing bitwise exclusive OR operation on the remaining bits of the first code and the second code except the respective least significant bit to generate an initial third code;
Sequentially changing bits equal to one in the initial third codes into zero according to a preset sequence in response to at least one bit equal to one in the initial third codes to sequentially generate a plurality of third codes until only one bit in the generated third codes is equal to one;
and generating a planning path according to the source terminal node, the destination terminal node and all third codes.
2. The routing path planning method of claim 1, wherein the step of generating a planned path from the source end node, the destination end node, and all third codes comprises:
the route nodes where the source terminal node and the destination terminal node are located are respectively used as a first route node and a last route node, and an intermediate route node is determined according to the first route node and all third codes;
and combining the source terminal node, the destination terminal node, the first routing node, the intermediate routing node and the last routing node to obtain a planned path.
3. The routing path planning method according to claim 1, wherein the step of sequentially changing the bits equal to one in the initial third codes to zero in a preset order to sequentially generate a plurality of third codes includes:
Taking the initial third code as the current third code;
changing the first bit equal to one from the lowest bit of the current third code to zero to obtain the next third code;
judging whether a bit equal to one in the latter third code is greater than one;
and in response to the bit equal to one in the next third code being greater than one, taking the next third code as the current third code, and returning to the step of changing the first bit equal to one to zero from the lowest bit of the current third code.
4. The routing path planning method according to claim 1, wherein the step of sequentially changing the bits equal to one in the initial third codes to zero in a preset order to sequentially generate a plurality of third codes includes:
taking the initial third code as the current third code;
changing the first bit equal to one from the highest bit of the current third code to zero to obtain the next third code;
judging whether the number of bits equal to one in the latter third code is greater than one;
and in response to the number of bits equal to one in the next third code being greater than one, taking the next third code as the current third code, and returning to the step of performing the step of changing the first bit equal to one to zero starting from the highest bit of the current third code.
5. The routing path planning method of claim 2, wherein the step of determining an intermediate routing node from the first routing node, all third encodings, comprises:
sequentially performing bit exclusive OR operation on two adjacent third codes from the first third code to generate a fourth code with sequence;
taking a binary code corresponding to the first routing node as a target code;
selecting a fourth code and the target code according to the sequence from front to back to perform bit-wise exclusive-or operation, and taking the result of the bit-wise exclusive-or operation as a binary code corresponding to the sequence number of an intermediate routing node;
taking the binary code corresponding to the latest generated intermediate routing node sequence number as a new target code, and returning to execute the step of selecting the fourth code and the target code from front to back in sequence to perform bitwise exclusive OR operation until all the fourth codes are traversed.
6. The routing path planning method of claim 5, wherein the step of combining the source terminal node, the destination terminal node, the first routing node, the intermediate routing node, and the last routing node to obtain a planned path comprises:
Respectively taking a source terminal node and the destination terminal node as a starting point and an ending point of a planned path;
and placing the first routing node and the intermediate routing nodes which are sequentially generated between the starting point and the ending point to generate a planned path.
7. The routing path planning method of claim 1, further comprising:
and in response to all bits in the initial third code being equal to zero, confirming that the source terminal node and the destination terminal node are in the same routing node.
8. The routing path planning method of claim 7, further comprising:
and setting the planned paths of the source terminal node and the destination terminal node to take the source terminal node as a starting point, the same routing node as an intermediate routing node and the destination terminal node as an ending point.
9. The routing path planning method of claim 1, further comprising:
determining first route information from the source terminal node to a first route node in the planned route according to the last bit of the first code; and
And determining second routing information from the last routing node to the destination terminal node in the planned path according to the last bit of the second code.
10. The routing path planning method of claim 1, wherein the network topology comprises a minimum of four routing nodes, wherein each routing node connects two end nodes, and two end node serial numbers connected to the same routing node are equal to two times the serial number of the connected routing node and two times the serial number of the connected routing node plus one, respectively.
11. The routing path planning method of claim 10, wherein path loops in the network topology are each comprised of four routing nodes.
12. The routing path planning method of claim 11, wherein the network topology comprises eight routing nodes with routing node numbers 0 to 7;
the connection relation of the routing nodes in the network topology comprises the following steps:
the routing node with the routing node serial number equal to 0 is respectively communicated with the routing nodes with the routing node serial numbers equal to 1, 2 and 4 in two directions;
the routing node with the routing node serial number equal to 1 is respectively communicated with the routing nodes with the routing node serial numbers equal to 3 and 5 in a two-way mode;
The routing node with the routing node serial number equal to 2 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 3 and 6;
the routing node with the routing node serial number equal to 3 is also respectively and bidirectionally communicated with the routing node serial number equal to 7;
the routing node with the routing node serial number equal to 4 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 5 and 6;
the routing nodes with the routing node serial numbers equal to 5 and 6 are respectively communicated with the routing nodes with the routing node serial number equal to 7 in a two-way mode.
13. The routing path planning method of claim 12, wherein the network topology further comprises four routing nodes with routing node numbers 8-11;
the connection relation of the routing nodes in the network topology further comprises:
the routing node with the routing node serial number equal to 8 is respectively communicated with the routing nodes with the routing node serial numbers equal to 0, 9 and 10 in a two-way manner;
the routing node with the routing node serial number equal to 9 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 1 and 11;
the routing node with the routing node serial number equal to 10 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 2 and 11;
the routing nodes with the routing node serial numbers equal to 11 are respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 3.
14. The routing path planning method of claim 13, wherein the network topology further comprises four routing nodes with routing node numbers 12-15;
the connection relation of the routing nodes in the network topology further comprises:
the routing node with the routing node serial number equal to 12 is respectively communicated with the routing nodes with the routing node serial numbers equal to 4, 8, 13 and 14 in a two-way manner;
the routing node with the routing node serial number equal to 13 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers equal to 5, 9 and 15;
the routing node with the routing node serial number equal to 14 is also respectively and bidirectionally communicated with the routing nodes with the routing node serial numbers 6, 10 and 15;
the routing nodes with the routing node serial numbers equal to 15 are respectively communicated with the routing nodes with the routing node serial numbers equal to 7 in a two-way mode.
15. A routing request processing method, characterized in that the routing request processing method comprises:
in response to the presence of an unexecuted first routing request and receipt of a second routing request, determining a planned path for the second routing request by the routing path planning method of any of claims 1-14.
16. The routing request processing method according to claim 15, wherein the routing request processing method further comprises:
A plurality of third routing requests are generated in response to the concurrency, and a planned path is determined for each of the third routing requests by the routing path planning method of any one of claims 1-14, respectively.
17. A routing path planning apparatus, the apparatus comprising:
the acquisition module is configured to acquire binary codes corresponding to terminal serial numbers of a source terminal node and a destination terminal node in a route request in a network topology respectively so as to acquire a first code and a second code, wherein the network topology comprises at least one path ring;
an operation module configured to perform a bitwise exclusive-or operation on remaining bits of the first code and the second code except for respective least significant bits to generate an initial third code;
a changing module, configured to respond to at least one bit in the initial third code being equal to one, and sequentially change the bit equal to one in the initial third code to zero according to a preset sequence to sequentially generate a plurality of third codes until only one bit in the generated third codes is equal to one;
and the generation module is configured to generate a planning path according to the source terminal node, the destination terminal node and all third codes.
18. An electronic device, comprising:
at least one processor; and
a memory storing a computer program executable in the processor, the processor executing the program to perform the routing path planning method of any one of claims 1-14 or the routing request processing method of any one of claims 15 to 16.
19. A computer readable storage medium storing a computer program, wherein the computer program when executed by a processor performs the route path planning method of any one of claims 1-14 or the route request processing method of any one of claims 15 to 16.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202311390582.4A CN117135106B (en) | 2023-10-25 | 2023-10-25 | Routing path planning method, routing request processing method, equipment and medium |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202311390582.4A CN117135106B (en) | 2023-10-25 | 2023-10-25 | Routing path planning method, routing request processing method, equipment and medium |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN117135106A true CN117135106A (en) | 2023-11-28 |
| CN117135106B CN117135106B (en) | 2024-02-13 |
Family
ID=88860335
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202311390582.4A Active CN117135106B (en) | 2023-10-25 | 2023-10-25 | Routing path planning method, routing request processing method, equipment and medium |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN117135106B (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN117354230A (en) * | 2023-11-30 | 2024-01-05 | 苏州元脑智能科技有限公司 | Routing path determining method, device, equipment and medium of bidirectional topological network |
| CN118282927A (en) * | 2024-06-03 | 2024-07-02 | 山东云海国创云计算装备产业创新中心有限公司 | Routing path planning method, device, equipment and medium |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5477536A (en) * | 1993-01-26 | 1995-12-19 | Picard; Jean L. | Method and system for routing information between nodes in a communication network |
| CN113424500A (en) * | 2019-02-12 | 2021-09-21 | 赫思曼自动化控制有限公司 | Method for routing in time-sensitive networks |
| CN116232985A (en) * | 2022-12-23 | 2023-06-06 | 中国联合网络通信集团有限公司 | A routing planning method, device and storage medium |
-
2023
- 2023-10-25 CN CN202311390582.4A patent/CN117135106B/en active Active
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5477536A (en) * | 1993-01-26 | 1995-12-19 | Picard; Jean L. | Method and system for routing information between nodes in a communication network |
| CN113424500A (en) * | 2019-02-12 | 2021-09-21 | 赫思曼自动化控制有限公司 | Method for routing in time-sensitive networks |
| CN116232985A (en) * | 2022-12-23 | 2023-06-06 | 中国联合网络通信集团有限公司 | A routing planning method, device and storage medium |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN117354230A (en) * | 2023-11-30 | 2024-01-05 | 苏州元脑智能科技有限公司 | Routing path determining method, device, equipment and medium of bidirectional topological network |
| CN117354230B (en) * | 2023-11-30 | 2024-02-27 | 苏州元脑智能科技有限公司 | Routing path determining method, device, equipment and medium of bidirectional topological network |
| CN118282927A (en) * | 2024-06-03 | 2024-07-02 | 山东云海国创云计算装备产业创新中心有限公司 | Routing path planning method, device, equipment and medium |
| CN118282927B (en) * | 2024-06-03 | 2024-12-24 | 山东云海国创云计算装备产业创新中心有限公司 | Routing path planning method, device, equipment and medium |
Also Published As
| Publication number | Publication date |
|---|---|
| CN117135106B (en) | 2024-02-13 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN117135108B (en) | Routing path planning method, routing request processing method, equipment and medium | |
| CN117135106B (en) | Routing path planning method, routing request processing method, equipment and medium | |
| US11403284B2 (en) | System for data sharing platform based on distributed data sharing environment based on block chain, method of searching for data in the system, and method of providing search index in the system | |
| CN118282927B (en) | Routing path planning method, device, equipment and medium | |
| CN117354230B (en) | Routing path determining method, device, equipment and medium of bidirectional topological network | |
| WO2022012576A1 (en) | Path planning method and apparatus, path planning device, and storage medium | |
| KR101942194B1 (en) | Network topology system and building methods for topologies and routing tables thereof | |
| CN108429679B (en) | Topological structure of extended interconnection network and routing method thereof | |
| CN117241337B (en) | Routing method, device, equipment and storage medium of dual-path wireless mesh network | |
| WO2003007557A1 (en) | Method for routing in telecommunications networks | |
| CN114298431A (en) | Network path selection method, device, equipment and storage medium | |
| Biswas et al. | A novel leader election algorithm based on resources for ring networks | |
| CN118890306B (en) | Computer network communication method, computer equipment, storage medium and program product | |
| CN117811993A (en) | Three-dimensional hypercube network, routing method, device, equipment and medium thereof | |
| US9166888B1 (en) | Configuration data | |
| CN111866069B (en) | Data processing method and device | |
| CN117176638A (en) | Routing path determining method and related components | |
| Bouchard et al. | Want to gather? no need to chatter! | |
| CN119052100A (en) | Node coding method of double-ring topology and routing method based on double-ring topology | |
| CN117811996A (en) | Routing method, device, equipment and medium for dual-path three-dimensional hypercube network | |
| KR20230099844A (en) | Method for generating and managing three-dimensional coordinate system based on transmission delay having o(n) overhead | |
| CN113822423B (en) | Scheduling method, device, computer equipment, network on chip and storage medium | |
| CN112491580A (en) | Routing passing judgment and problem positioning method and device | |
| CN118921317B (en) | A routing method, communication network construction method, device, medium and product | |
| CN118984294B (en) | A routing method, communication network construction method, device, medium and product |
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 |