CN115379318A

CN115379318A - BENES network route speculative solution method and device

Info

Publication number: CN115379318A
Application number: CN202210929411.3A
Authority: CN
Inventors: 秦梦远; 郝沁汾
Original assignee: Wuxi Core Optical Interconnect Technology Research Institute Co ltd
Current assignee: Wuxi Core Optical Interconnect Technology Research Institute Co ltd
Priority date: 2022-08-03
Filing date: 2022-08-03
Publication date: 2022-11-22
Anticipated expiration: 2042-08-03
Also published as: CN115379318B

Abstract

The invention discloses a BENES network route speculative solving method and a device thereof, wherein the method comprises the following steps: s1: constructing an N multiplied by N BENES network simulation array, wherein the BENES network simulation array has the same topology as the currently controlled BENES network; s2: manufacturing N different input signals, wherein each input signal is correspondingly connected with one input port of the BENES network simulation array; s3: observing signals flowing through each 2x2 switch of the BENES network emulation array; s4: searching a 2x2 switch, wherein two input ports of the 2x2 switch respectively receive input signals from input ports of two input and output links to be exchanged; s5: and changing the state of the 2x2 optical switch at the position corresponding to the 2x2 switch found in the step S4 in the BENES network to complete reconstruction. The invention avoids specific route solving, directly obtains a route result, further reduces the solving time required by the current optimal route solving hardware to tens of nanoseconds or even lower, and ensures that the BENES optical network can be really used in a production environment.

Description

BENES network route speculative solution method and device

Technical Field

The invention relates to the field of routing computation, in particular to a BENES network routing speculative solving method and device.

Background

A network switch is a network device for electrical/optical signal forwarding that can provide a path for any two accessed network switching nodes. The network switching architecture is divided into a limited blocking type, a rearrangement non-blocking type and a strict non-blocking type, and the number of the switch units used by the three architectures, including the number of stages, is increased. The Benes network belongs to a rearrangement non-blocking type architecture, namely when a new input-output port connection is established, all paths need to be re-planned, and the states of the switch units can meet all connection requirements after being re-planned. Compared with a strict non-blocking network architecture, the Benes network has smaller scale and passes through fewer stages during routing. The device has low loss and small size due to the Benes network architecture, and is widely applied to the optical switching network structure, but the path switching algorithm under the network architecture is complex, so that important attention needs to be paid.

A problem with BENES networks is that the routing solution is difficult and the best existing hardware implementations still require a solution time of 100ns (for 16x16 BENES networks) which is too slow compared to the switching time of optical switches of a few ns.

The algorithm for solving the BENES network route in a short period cannot be improved by breakthrough, the best hardware implementation method can be used for losing the potential, and the method for further reducing the solving time can only depend on advanced processes and higher running frequency.

In the prior art, a method and a device for low-complexity obstacle avoidance routing for a Benes network are disclosed, and for the Benes network, the connection priority of a subnet is determined by a fault unit; constructing an incidence relation among an input layer input port, an output layer output port and a subnet connection priority according to the connection condition of the input and output ports; determining the on-off states of the input layer and the output layer according to the incidence relation; updating the connection condition of the input and output ports in the subnet according to the switch state; when the connection condition of the input and output ports reaches the middle level, determining the state of a middle level switch unit and ending the process; otherwise, taking the secondary edge level as the latest edge level, and analyzing the fault unit again. The low-complexity obstacle avoidance routing method can realize low-blocking-rate routing under the conditions of any scale of Benes network structures and any port configuration and realize optimization of resource utilization of the switch unit in view of the conditions that the design of the switch unit is not ideal and the matched control circuit and the electric package are not communicated. The solution cannot further reduce the route solving time of the BENES network.

Disclosure of Invention

The invention aims to provide a BENES network route speculative solving method, which is used for rapidly obtaining a solution of a target route and matching with a proper route decision strategy, and after the speculative method is applied, the average solving time can be reduced to tens of nanoseconds.

A further object of the present invention is to provide a BENES network route speculative solver.

In order to solve the technical problems, the technical scheme of the invention is as follows:

a method for speculatively solving routing in a BENES network is characterized in that a 2x2 optical switch in the BENES network is searched, so that the reconstruction can be completed by changing the state of the 2x2 optical switch when only two input/output links are exchanged in the BENES network reconstruction each time, and the method for speculatively solving routing comprises the following steps:

s1: constructing an N multiplied by N BENES network simulation array, wherein the BENES network simulation array has the same topology as the currently controlled BENES network;

s2: manufacturing N different input signals, wherein each input signal is correspondingly connected with one input port of the BENES network simulation array;

s3: observing signals flowing through each 2x2 switch of the BENES network emulation array;

s4: searching a 2x2 switch, wherein two input ports of the 2x2 switch respectively receive input signals from input ports of two input and output links to be exchanged;

s5: and changing the state of the 2x2 optical switch at the position corresponding to the 2x2 switch found in the step S4 in the BENES network to complete reconstruction.

Preferably, N different input signals are manufactured in step S2, specifically:

and the manufactured input data is the number corresponding to the input port of the BENES network simulation array corresponding to the input data, and the value is 1 to N.

Preferably, in the step S3, a signal flowing through each 2 × 2 switch of the BENES network simulation array is observed, specifically:

and leading out two paths of input signals of each 2x2 switch of the BENES network simulation array and connecting the two paths of input signals into an observation module for observation.

Preferably, a 2 × 2 switch is searched in step S4:

let the input ports of the two input and output links of the exchange be A and B, and generate a binary group (A, B);

and matching the generated binary group (A, B) with the input signal of each 2x2 switch of the BENES network simulation array, wherein the successfully matched 2x2 switch is the 2x2 switch to be searched.

Preferably, the step S5 specifically includes:

outputting the serial number of the 2x2 switch found in the step S4, changing the state of the optical switch corresponding to the serial number after the BENES network receives the serial number, and changing the state of the optical switch into parallel if the state of the optical switch is crossed; if the optical switches are in a parallel state, they cross each other.

Preferably, a traditional BENES network solving algorithm is used for synchronously carrying out the bottom-guaranteeing operation to obtain a bottom-guaranteeing operation result, if the speculative solving method is hit, the operation result of the speculative solving method is adopted, and the bottom-guaranteeing operation result is abandoned; and if the speculative solution method is not hit, waiting for a bottom-guaranteeing operation result and executing.

A BENES network route speculative solving device comprises an analog data input excitation module, a BENES network solving array module, an observation module and a state splicer, wherein:

the analog data input excitation module constantly provides N paths of different signals and drives an input port corresponding to the analog BENES array, and input excitation is provided for the BENES network solving array module;

an N multiplied by N BENES network simulation array is arranged in the BENES network solving array module, the topology of the BENES network simulation array is completely the same as that of the BENES network which is controlled currently, and the analog data input excitation module provides N different signals which are respectively connected with N input ports of the BENES network simulation array;

the observation module receives a route solving input, is connected with the input port of each 2x2 switch of the BENES network simulation array, and outputs the serial numbers of the 2x2 switches of which the two input ports respectively receive input signals from the input ports of the two input and output links to be exchanged to the state splicer;

the state splicer stores a state set for bearing the current BENES optical switch array, receives an optical switch number needing state change, internally changes a corresponding optical switch state storage value and splices the optical switch state storage value with the rest optical switch states, and outputs a complete optical switch state sequence.

Preferably, the analog data input excitation module constantly provides N different signals, which are numbers corresponding to the input ports of the BENES network simulation array corresponding to the input data, and values of the numbers are 1 to N.

Preferably, the observation module outputs the serial numbers of the 2x2 switches, of which the two input ports respectively receive the input signals from the input ports of the two input and output links to be exchanged, to the state splicer, specifically:

and matching the generated binary group (A, B) with the input signal of each 2x2 switch of the BENES network simulation array, wherein the successfully matched 2x2 switch is the 2x2 switch to be searched, and outputting the serial number of the 2x2 switch to a state splicer.

Preferably, a BENES solver and a route solver collector are further included, wherein:

the BENES solver receives a route solving input, and synchronously carries out a bottom-preserving operation by using a traditional BENES network solving algorithm to obtain a bottom-preserving operation result and outputs the bottom-preserving operation result to a route solving collector;

and the route solving collector simultaneously receives the bottom-preserving operation result of the BENES solver and the output result of the state splicer, and selects the output with the highest solving speed to output.

Compared with the prior art, the technical scheme of the invention has the beneficial effects that:

the inventive speculative method avoids specific route solving, directly obtains route result, and further reduces solving time required by current optimal route solving hardware to tens of nanoseconds or even lower, so that BENES optical network can be really used in production environment.

Drawings

FIG. 1 is a schematic flow chart of the method of the present invention.

Fig. 2 is an example 8x8BENES optical switch configured for specific routing, provided by an embodiment.

Fig. 3 shows an example of the speculative algorithm provided by the embodiment.

FIG. 4 is a schematic view of the apparatus of the present invention.

Fig. 5 is a relational diagram of a BENES network simulation array, an observation module, and a BENES optical switch array according to an embodiment.

FIG. 6 is a structure of a switch simulator inside a BENES network simulation array.

Detailed Description

The drawings are for illustrative purposes only and are not to be construed as limiting the patent;

for the purpose of better illustrating the embodiments, certain features of the drawings may be omitted, enlarged or reduced, and do not represent the size of an actual product;

it will be understood by those skilled in the art that certain well-known structures in the drawings and descriptions thereof may be omitted.

The technical solution of the present invention is further described below with reference to the accompanying drawings and examples.

Example 1

This embodiment provides a method for speculatively solving route of a BENES network, as shown in fig. 1, where the method searches for a 2x2 optical switch in the BENES network, so that each time a BENES network reconfiguration only exchanges two input/output links, the state of the 2x2 optical switch is changed, and the reconfiguration can be completed, and the method for speculatively solving includes the following steps:

s1: constructing an N multiplied by N BENES network simulation array, wherein the topology of the BENES network simulation array is completely the same as that of a currently controlled BENES network, and the BENES network simulation array is simulated by using a circuit;

When only two input-output links are exchanged per reconfiguration, there is a possibility to change the state of only one 2x2 optical switch in the network to complete the reconfiguration. This application will refer to the algorithm that seeks such a possibility as a speculative algorithm.

In the step S2, N different input signals are manufactured, specifically:

and manufacturing input data which are numbers corresponding to the input ports of the BENES network simulation array corresponding to the input data, wherein the values of the numbers are 1 to N.

In the step S3, a signal flowing through each 2 × 2 switch of the BENES network simulation array is observed, specifically:

In step S4, a 2 × 2 switch is searched:

and matching the generated doublet (A, B) with the input signal of each 2x2 switch of the BENES network simulation array, wherein the successfully matched one is the 2x2 switch to be searched.

The step S5 specifically includes:

outputting the serial number of the 2x2 switch found in the step S4, changing the state of the optical switch corresponding to the serial number after the BENES network receives the serial number, and if the state of the optical switch is crossed, changing the state of the optical switch into parallel; if the optical switches are in a parallel state, they cross each other.

In the specific implementation process, the solution content of the speculative algorithm is as follows: on the premise of only exchanging the contents of two output ports, the requirement can be completed by judging whether a 2x2 switch exists or not and changing the state of the switch. Thus, an output sequence [ N ] is defined as the sequence of the numbering of each entry. For example, as shown in fig. 2, the BENES network of 8 × 8, where [ N ] may be {7,8,1,2,6,3,4,5}, where the pairing is performed according to the implicit input sequence (because the input sequence does not change), results in 1 → 7,2 → 8,3 → 1,4 → 2,5 → 6,6 → 3,7 → 4,8 → 5, i.e.: data entering input port 1 will flow out of output port 7 and data entering input port 2 will flow out of 82308230, 8230, from output port 8.

Assume that in the current state, the contents of output port 3 and output port 6 need to be exchanged, i.e., 5 → 3,6 → 6: data entering input port 5 will flow out of output port 3 and data entering input port 6 will flow out of output port 6.

The speculative algorithm will make 8 different inputs and observe whether there is a 2x2 switch on which both the data at input port 5 and the data at input port 6 are carried. Generally, the manufactured input data is the number corresponding to the input port, that is, the input data of the port with the number 1 is also 1, so that the corresponding data path can be easily judged according to the data content. The speculative algorithm solver internally uses circuitry to simulate a BENES array whose state is identical to the state of the current optical switch array. Because the inside adopts circuit simulation, each simulated switch does not need to have two paths of outputs like a real optical switch, but each path of input is divided into two paths, one path is used for simulating a real optical path, and the other path is used for an observation module to carry out data path observation.

The observation module receives a route solving input and converts the route solving input into an output port corresponding to which input port of the two routes is specifically switched. Because the solution limits can only exchange two paths of input, and therefore, if the two paths of input are exchanged, the speculative solution refuses to be executed, and the solution fails to be returned. After finding the number of the corresponding two input ports, a binary group (A, B) is generated inside the observation module, wherein A and B respectively represent the number of one input port. Because the observation module is connected with the input results of all the analog switches, the switches which simultaneously bear two paths of input can be found only by matching the generated binary group with the input of each analog switch. Obviously, changing the state of this switch (cross-over to parallel, or parallel to cross-over) achieves the target route.

If the switch exists, the corresponding route solution can be obtained only by changing the state of the switch (from parallel to cross or from cross to parallel) and keeping the states of the other switches unchanged. To complete the solution, the observer module attempts to find a compliant 2x2 optical switch, i.e., an optical switch that carries both

data

5 and 6, as shown in fig. 3. In this example, the observation module has found the optical switch, which has been outlined with a dashed line. After changing the switch state to parallel, the solution objective is achieved. The changed data is marked with a prime.

Only the optical switch which needs to change the state is found, and only half of the solution content is completed. Next, the states of the remaining optical switches need to be spliced with the new state of the optical switch that needs to be changed to implement complete routing output. And numbering the optical switches needing to change the state, internally changing corresponding optical switch state storage values, splicing the optical switch state storage values with the other optical switches, and outputting a complete optical switch state sequence.

The advantages are that: 1. the method is extremely fast, has no data dependence, can be fully parallelized and is completed in one hardware clock cycle.

2. In the speculative algorithm hit solution, only 1 optical switch state is changed, so that only two data links are affected, and the rest data links are still normally available in the reconstruction execution stage, so that the link interruption problem cannot occur.

Example 2

This example discloses the following on the basis of example 1:

the speculative algorithm of example 1 has the following drawbacks:

the number of switches is limited and below the solution space described above, so there is a certain probability of failing to hit. At 8x8BENES the average hit rate was 20/28=5/7, at 16x16 BENES the average hit rate dropped to 56/120=7/15. The hit rate of larger BENES networks is significantly reduced.

And (4) compensation measures: synchronously performing bottom-guaranteeing operation by using a traditional BENES network solving algorithm, adopting a speculative algorithm result when the speculative algorithm is hit, and abandoning the bottom-guaranteeing operation result; otherwise, waiting for the bottom-preserving operation result and executing. The route solution is synchronously sent to a traditional BENES solver and a speculative algorithm solver. Since the solution success rate of the traditional BENES solver is 100%, the traditional BENES solver can always complete the route solution within a limited time. The solution speed of the speculative algorithm solver is far faster than that of the traditional BENES solver, so that if the speculative algorithm is hit, the speculative algorithm solver can always output the solution result more quickly. Because certain probability cannot be solved, a route solving collector is arranged, the device receives the output results of the traditional BENES solver and the speculative algorithm solver, and selects the fastest outward output to achieve the purpose of solving and accelerating.

Example 3

The present embodiment provides a BENES network route speculative solution device, as shown in fig. 4 to 6, including an analog data input excitation module, a BENES network solution array module, an observation module, and a state splicer, where:

the observation module receives route solving input, is connected with the input port of each 2x2 switch of the BENES network simulation array, and outputs the serial numbers of the 2x2 switches of the input signals of the input ports of the two input and output links to be exchanged, which are respectively received by the two input ports, to the state splicer;

The analog data input excitation module constantly provides N paths of different signals which are respectively the numbers corresponding to the input ports of the BENES network simulation array corresponding to the input data, and the values are from 1 to N.

The observation module outputs the serial numbers of the 2x2 switches of which the two input ports respectively receive the input signals from the input ports of the two input and output links to be exchanged to the state splicer, and the method specifically comprises the following steps:

Also included are a BENES solver and a route solver collector, wherein:

the BENES solver receives a route solving input, and the BENES solver synchronously carries out bottom-preserving operation by using a traditional BENES network solving algorithm to obtain a bottom-preserving operation result and outputs the bottom-preserving operation result to a route solving collector;

The same or similar reference numerals correspond to the same or similar parts;

the terms describing positional relationships in the drawings are for illustrative purposes only and are not to be construed as limiting the patent;

it should be understood that the above-described embodiments of the present invention are merely examples for clearly illustrating the present invention and are not intended to limit the embodiments of the present invention. Other variations and modifications will be apparent to persons skilled in the art in light of the above description. And are neither required nor exhaustive of all embodiments. Any modification, equivalent replacement, and improvement made within the spirit and principle of the present invention should be included in the protection scope of the claims of the present invention.

Claims

1. A method for speculatively solving routing in a BENES network is characterized in that the method searches for a 2x2 optical switch in the BENES network, so that reconstruction can be completed by changing the state of the 2x2 optical switch when only two input/output links are exchanged for each time of the BENES network reconstruction, and the method for speculatively solving routing comprises the following steps:

2. The BENES network route speculation solution of claim 1, wherein N different input signals are manufactured in step S2, specifically:

the manufactured input data is the number corresponding to the input port of the BENES network simulation array corresponding to the input data.

3. The BENES network routing speculative solution method of claim 1, wherein the signals flowing through each 2x2 switch of the BENES network simulation array are observed in step S3, and specifically:

4. The BENES network route speculation solution method of claim 1, wherein a 2x2 switch is found in step S4, specifically:

5. The BENES network route speculation solution method of claim 1, wherein the step S5 specifically is:

outputting the serial number of the 2x2 switch found in the step S4, changing the state of the optical switch corresponding to the serial number after the BENES network receives the serial number, and if the state of the optical switch is crossed, changing the state of the optical switch into parallel; if the optical switches are in parallel, they cross.

6. The BENES network route speculative solution method of any of claims 1 to 5, wherein a traditional BENES network solution algorithm is used to synchronously perform a guaranteed-bottom operation to obtain a guaranteed-bottom operation result, and if the speculative solution method is hit, the operation result of the speculative solution method is adopted, and the guaranteed-bottom operation result is discarded; and if the speculative solution method is not hit, waiting for a bottom-guaranteeing operation result and executing.

7. The device for speculatively solving the routing of the BENES network is characterized by comprising an analog data input excitation module, a BENES network solution array module, an observation module and a state splicer, wherein:

the state splicer stores a state set for bearing the current BENES optical switch array, receives the optical switch number needing state change, internally changes the corresponding optical switch state storage value and splices the optical switch state storage value with the other optical switch states, and outputs a complete optical switch state sequence.

8. The BENES network routing speculative solution device of claim 7, wherein the analog data input excitation module constantly provides N different signals, which are respectively the numbers corresponding to the input ports of the BENES network simulation array corresponding to the input data and take values from 1 to N.

9. The BENES network routing speculation solution apparatus of claim 8, wherein the observation module outputs to the state splicer serial numbers of 2x2 switches whose two input ports respectively receive input signals from input ports of two input/output links to be exchanged, specifically:

10. The BENES network route speculation resolution device of claim 9, further comprising a BENES solver and a route solution collector, wherein: