# Exercise “non-blocking 4x4 matrix switch“
contributed by <Tim Chien([e-mail])>

## Introduction
$$
Fig.1 \ The\ schmatic\ of\ a\ non-blocking\ 4X4\ matrix\ switch
$$
The schematic of the non-blocking 4X4 matrix is given above. It is composed of 8 2X2 switches. Each switch can be operated in either cross state or bar state, as shown on the upper-right of the image.
The number of overall configurations should be 4! = 24, which can be found by python.

import itertools

inputs = [1, 2, 3, 4]
all_configurations = list(itertools.permutations(inputs))
for i, config in enumerate(all_configurations):
    connections = []
    for input_port, output_port in zip(inputs, config):
        connections.append(f"IN {input_port}")
        connections.append(f"OUT {output_port}")
    
    print(f"Configuration {i+1:02d}: {', '.join(connections)}")

The result is

Configuration 01: IN 1, OUT 1, IN 2, OUT 2, IN 3, OUT 3, IN 4, OUT 4
Configuration 02: IN 1, OUT 1, IN 2, OUT 2, IN 3, OUT 4, IN 4, OUT 3
...
Configuration 23: IN 1, OUT 4, IN 2, OUT 3, IN 3, OUT 1, IN 4, OUT 2
Configuration 24: IN 1, OUT 4, IN 2, OUT 3, IN 3, OUT 2, IN 4, OUT 1

However, to find out all the switches' states corresponding to each configuration manually seems to be inefficient(since there are total $2^8 = 256$ states to be test), and only restrict to this scheme. Rather than trying to investigate the regulation, I decided to iterate through all the possibility by computer. Although there are many functions should be improved (like it can only simulate the 2X2 switch), the program provides the basic functions to tracing the light path from input node to output node.
## Data Structure
I defined each 2X2 switch as a "Node", every Node has its name, port, and state. Where the port represent the ports in 2X2 switch and the state represents whether the switch is operated in "Cross" state or "Bar" state.
The class of "Node" is

class Node:
    def __init__(self, name):
        self.name = name
        self.ports = {}
        self.state = 0 # bar=0, cross=1
    def add_port(self, port_name):
        port = Port(port_name, self)
        self.ports[port_name] = port
        return port

The `add_port` function add a new port to the Node and saved in the dictionary form. Meanwhile the class of "Port" is

class Port:
    def __init__(self, name, node):
        self.name = name
        self.node = node
        self.connections = [] 

    def set_connections(self, conn_list):
        # Set the connections of port, 
        # the first element is for the connection inside the node
        self.connections.append(conn_list)

    def get_next(self, incoming_state):
        if self.node.name.startswith("INnode"):
            incoming_state = 0
        # incoming_state: light comes from inside the node:0, outside the node:1
        return self.connections[incoming_state]

The `set_connections` function set the connection of this port, the first element is preserved for the connection inside the Node to identify the direction of light. The `get_next` function get the next port for the light to go. Note that the inputs and outputs are considered a "Node" with 2 "Ports" for implentation reasons.

$$
Fig.2 \ The\ schmatic\ of\ a\ Node
$$
And the connections are setup by, which corresponds to Fig.1

def set_intra_connection(node_dict, node_name_list):
    for node in node_name_list:
        if (node_dict[node].state == 0):
            set_port_interconnection(node_dict[node].name, "1", node_dict[node].name, "3")
            set_port_interconnection(node_dict[node].name, "2", node_dict[node].name, "4")
        else:
            set_port_interconnection(node_dict[node].name, "1", node_dict[node].name, "4")
            set_port_interconnection(node_dict[node].name, "2", node_dict[node].name, "3")
def set_inter_connection():
    set_port_interconnection("X1", "3", "X3", "1")
    set_port_interconnection("X1", "4", "X2", "2")
    set_port_interconnection("X2", "3", "X6", "4")
    set_port_interconnection("X2", "4", "X4", "2")
    set_port_interconnection("X3", "3", "X5", "1")
    set_port_interconnection("X3", "4", "X7", "3")
    set_port_interconnection("X4", "3", "outputnode2", "out3")
    set_port_interconnection("X4", "4", "outputnode2", "out4")
    set_port_interconnection("X5", "3", "outputnode1", "out4")
    set_port_interconnection("X5", "4", "outputnode1", "out3")
    set_port_interconnection("X6", "3", "X4", "1")
    set_port_interconnection("X7", "4", "X5", "2")
    set_port_interconnection("X8", "3", "X6", "1")
    set_port_interconnection("X8", "4", "X7", "2")
    set_port_interconnection("X7", "1", "X6", "2")
    set_port_interconnection("X3", "2", "X2", "1")
    set_port_interconnection("INnode1", "in1", "X1", "1")
    set_port_interconnection("INnode1", "in2", "X1", "2")
    set_port_interconnection("INnode2", "in1", "X8", "2")
    set_port_interconnection("INnode2", "in2", "X8", "1")

The flow chart of the program is shown below
$$
Fig.3 \ The\ flow\ chart\ of\ the\ program
$$
## Result
The result is shown below. Note that the defination is slightly difference from Fig.1 to improve the clearity of code

| Program | Fig.1 |
| -------- | -------- |
| INnode1 | X1 |
| INnode2 | X8 |
| outputnode1 | X5 |
| outputnode2 | X4 |
| INnode1.in1 | in1 |
| INnode1.in2 | in2 |
| INnode2.in1 | in3 |
| INnode2.in2 | in4 |
| outputnode1.out3 | out1 |
| outputnode1.out4 | out2 |
| outputnode2.out3 | out3 |
| outputnode2.out4 | out4 |

$$
Table.1 \ The\ name\ relation\ between\ schematic\ and\ the\ program
$$
:::spoiler result

state = (X1, X2, X3, X4, X5, X6, X7, X8) bar = 0, cross = 1
=== Configuration 1  state = (0, 0, 0, 0, 0, 0, 0, 0) ===
('INnode1.in1->outputnode1.out4', 'INnode1.in2->outputnode2.out4', 
'INnode2.in1->outputnode1.out3', 'INnode2.in2->outputnode2.out3')

=== Configuration 2  state = (0, 0, 0, 0, 0, 0, 0, 1) ===
('INnode1.in1->outputnode1.out4', 'INnode1.in2->outputnode2.out4', 
'INnode2.in1->outputnode2.out3', 'INnode2.in2->outputnode1.out3')

=== Configuration 3  state = (0, 0, 0, 0, 1, 0, 0, 0) ===
('INnode1.in1->outputnode1.out3', 'INnode1.in2->outputnode2.out4', 
'INnode2.in1->outputnode1.out4', 'INnode2.in2->outputnode2.out3')

=== Configuration 4  state = (0, 0, 0, 0, 1, 0, 0, 1) ===
('INnode1.in1->outputnode1.out3', 'INnode1.in2->outputnode2.out4', 
'INnode2.in1->outputnode2.out3', 'INnode2.in2->outputnode1.out4')

=== Configuration 5  state = (0, 0, 0, 1, 0, 0, 0, 0) ===
('INnode1.in1->outputnode1.out4', 'INnode1.in2->outputnode2.out3', 
'INnode2.in1->outputnode1.out3', 'INnode2.in2->outputnode2.out4')

=== Configuration 6  state = (0, 0, 0, 1, 0, 0, 0, 1) ===
('INnode1.in1->outputnode1.out4', 'INnode1.in2->outputnode2.out3', 
'INnode2.in1->outputnode2.out4', 'INnode2.in2->outputnode1.out3')

=== Configuration 7  state = (0, 0, 0, 1, 1, 0, 0, 0) ===
('INnode1.in1->outputnode1.out3', 'INnode1.in2->outputnode2.out3', 
'INnode2.in1->outputnode1.out4', 'INnode2.in2->outputnode2.out4')

=== Configuration 8  state = (0, 0, 0, 1, 1, 0, 0, 1) ===
('INnode1.in1->outputnode1.out3', 'INnode1.in2->outputnode2.out3',
'INnode2.in1->outputnode2.out4', 'INnode2.in2->outputnode1.out4')

=== Configuration 9  state = (0, 0, 1, 0, 0, 1, 0, 0) ===
('INnode1.in1->outputnode2.out3', 'INnode1.in2->outputnode2.out4', 
'INnode2.in1->outputnode1.out3', 'INnode2.in2->outputnode1.out4')

=== Configuration 10  state = (0, 0, 1, 0, 0, 1, 0, 1) ===
('INnode1.in1->outputnode2.out3', 'INnode1.in2->outputnode2.out4', 
'INnode2.in1->outputnode1.out4', 'INnode2.in2->outputnode1.out3')

=== Configuration 11  state = (0, 0, 1, 1, 0, 1, 0, 0) ===
('INnode1.in1->outputnode2.out4', 'INnode1.in2->outputnode2.out3',
'INnode2.in1->outputnode1.out3', 'INnode2.in2->outputnode1.out4')

=== Configuration 12  state = (0, 0, 1, 1, 0, 1, 0, 1) ===
('INnode1.in1->outputnode2.out4', 'INnode1.in2->outputnode2.out3', 
'INnode2.in1->outputnode1.out4', 'INnode2.in2->outputnode1.out3')

=== Configuration 13  state = (0, 1, 0, 0, 0, 0, 1, 0) ===
('INnode1.in1->outputnode1.out4', 'INnode1.in2->outputnode1.out3', 
'INnode2.in1->outputnode2.out4', 'INnode2.in2->outputnode2.out3')

=== Configuration 14  state = (0, 1, 0, 0, 0, 0, 1, 1) ===
('INnode1.in1->outputnode1.out4', 'INnode1.in2->outputnode1.out3', 
'INnode2.in1->outputnode2.out3', 'INnode2.in2->outputnode2.out4')

=== Configuration 15  state = (0, 1, 0, 0, 1, 0, 1, 0) ===
('INnode1.in1->outputnode1.out3', 'INnode1.in2->outputnode1.out4', 
'INnode2.in1->outputnode2.out4', 'INnode2.in2->outputnode2.out3')

=== Configuration 16  state = (0, 1, 0, 0, 1, 0, 1, 1) ===
('INnode1.in1->outputnode1.out3', 'INnode1.in2->outputnode1.out4', 
'INnode2.in1->outputnode2.out3', 'INnode2.in2->outputnode2.out4')

=== Configuration 17  state = (1, 0, 0, 0, 0, 0, 0, 0) ===
('INnode1.in1->outputnode2.out4', 'INnode1.in2->outputnode1.out4', 
'INnode2.in1->outputnode1.out3', 'INnode2.in2->outputnode2.out3')

=== Configuration 18  state = (1, 0, 0, 0, 0, 0, 0, 1) ===
('INnode1.in1->outputnode2.out4', 'INnode1.in2->outputnode1.out4', 
'INnode2.in1->outputnode2.out3', 'INnode2.in2->outputnode1.out3')

=== Configuration 19  state = (1, 0, 0, 0, 1, 0, 0, 0) ===
('INnode1.in1->outputnode2.out4', 'INnode1.in2->outputnode1.out3', 
'INnode2.in1->outputnode1.out4', 'INnode2.in2->outputnode2.out3')

=== Configuration 20  state = (1, 0, 0, 0, 1, 0, 0, 1) ===
('INnode1.in1->outputnode2.out4', 'INnode1.in2->outputnode1.out3', 
'INnode2.in1->outputnode2.out3', 'INnode2.in2->outputnode1.out4')

=== Configuration 21  state = (1, 0, 0, 1, 0, 0, 0, 0) ===
('INnode1.in1->outputnode2.out3', 'INnode1.in2->outputnode1.out4', 
'INnode2.in1->outputnode1.out3', 'INnode2.in2->outputnode2.out4')

=== Configuration 22  state = (1, 0, 0, 1, 0, 0, 0, 1) ===
('INnode1.in1->outputnode2.out3', 'INnode1.in2->outputnode1.out4', 
'INnode2.in1->outputnode2.out4', 'INnode2.in2->outputnode1.out3')

=== Configuration 23  state = (1, 0, 0, 1, 1, 0, 0, 0) ===
('INnode1.in1->outputnode2.out3', 'INnode1.in2->outputnode1.out3', 
'INnode2.in1->outputnode1.out4', 'INnode2.in2->outputnode2.out4')

=== Configuration 24  state = (1, 0, 0, 1, 1, 0, 0, 1) ===
('INnode1.in1->outputnode2.out3', 'INnode1.in2->outputnode1.out3', 
'INnode2.in1->outputnode2.out4', 'INnode2.in2->outputnode1.out4')

:::
Moreover, the light path under each state can be printed out

=== Configuration 23  state = (1, 0, 0, 1, 1, 0, 0, 0) ===
['Current:INnode1 in1 -> Next: X1 1', 'Current:X1 1 -> Next: X1 4', 
'Current:X1 4 -> Next: X2 2', 'Current:X2 2 -> Next: X2 4', 
'Current:X2 4 -> Next: X4 2', 'Current:X4 2 -> Next: X4 3', 
'Current:X4 3 -> Next: outputnode2 out3']

['Current:INnode1 in2 -> Next: X1 2', 'Current:X1 2 -> Next: X1 3', 
'Current:X1 3 -> Next: X3 1', 'Current:X3 1 -> Next: X3 3', 
'Current:X3 3 -> Next: X5 1', 'Current:X5 1 -> Next: X5 4', 
'Current:X5 4 -> Next: outputnode1 out3']

['Current:INnode2 in1 -> Next: X8 2', 'Current:X8 2 -> Next: X8 4', 
'Current:X8 4 -> Next: X7 2', 'Current:X7 2 -> Next: X7 4', 
'Current:X7 4 -> Next: X5 2', 'Current:X5 2 -> Next: X5 3', 
'Current:X5 3 -> Next: outputnode1 out4']

['Current:INnode2 in2 -> Next: X8 1', 'Current:X8 1 -> Next: X8 3', 
'Current:X8 3 -> Next: X6 1', 'Current:X6 1 -> Next: X6 3', 
'Current:X6 3 -> Next: X4 1', 'Current:X4 1 -> Next: X4 4', 
'Current:X4 4 -> Next: outputnode2 out4']
-----

## The Benes Network
The optimization of finding the routing of a NXN nonblocking switch is actually been investigated to fulfill the requirements of telecommunications and parallel computing, etc.[1]

The schemes for this solution is called the Benes Network. It comes up with the structure like Fig.4 (4X4 non-blocking switch). For a NXN non-blocking switch, it requires $2log_2N - 1$ switch layers with each layer has $\frac{N}{2}$ 2X2 switch. So the minimum component requirement for a 4X4 non-blocking switch is 6 components.

Moreover, algorithms are developed to find the states for each node corresponding to the input-output connections (I am still working on this). Besides fiberoptics, some routings for PIC circuits has been developed using 6 switches.[2]
$$
Fig.3 \ The\ Benes\ Network
$$
By changing the connections in the program to the schematic in Fig.3, we can get all the configurations in this scheme.

def set_inter_connection():
    set_port_interconnection("X1", "3", "X3", "1")
    set_port_interconnection("X1", "4", "X4", "1")
    set_port_interconnection("X2", "3", "X3", "2")
    set_port_interconnection("X2", "4", "X4", "2")
    set_port_interconnection("X3", "3", "X5", "1")
    set_port_interconnection("X3", "4", "X6", "1")
    set_port_interconnection("X4", "3", "X5", "2")
    set_port_interconnection("X4", "4", "X6", "2")
    set_port_interconnection("X5", "3", "OUTnode1", "out3")
    set_port_interconnection("X5", "4", "OUTnode1", "out4")
    set_port_interconnection("X6", "3", "OUTnode2", "out3")
    set_port_interconnection("X6", "4", "OUTnode2", "out4")
    set_port_interconnection("INnode1", "in1", "X1", "1")
    set_port_interconnection("INnode1", "in2", "X1", "2")
    set_port_interconnection("INnode2", "in1", "X2", "1")
    set_port_interconnection("INnode2", "in2", "X2", "2")

The result is shown below, note that the comparison table for names is shown in Table 1 above.
:::spoiler result

state = (X1, X2, X3, X4, X5, X6) bar = 0, cross = 1
=== Configuration 1  state = (0, 0, 0, 0, 0, 0) ===
('INnode1.in1->OUTnode1.out3', 'INnode1.in2->OUTnode1.out4', 
'INnode2.in1->OUTnode2.out3', 'INnode2.in2->OUTnode2.out4')

=== Configuration 2  state = (0, 0, 0, 0, 0, 1) ===
('INnode1.in1->OUTnode1.out3', 'INnode1.in2->OUTnode1.out4', 
'INnode2.in1->OUTnode2.out4', 'INnode2.in2->OUTnode2.out3')

=== Configuration 3  state = (0, 0, 0, 0, 1, 0) ===
('INnode1.in1->OUTnode1.out4', 'INnode1.in2->OUTnode1.out3', 
'INnode2.in1->OUTnode2.out3', 'INnode2.in2->OUTnode2.out4')

=== Configuration 4  state = (0, 0, 0, 0, 1, 1) ===
('INnode1.in1->OUTnode1.out4', 'INnode1.in2->OUTnode1.out3', 
'INnode2.in1->OUTnode2.out4', 'INnode2.in2->OUTnode2.out3')

=== Configuration 5  state = (0, 0, 0, 1, 0, 0) ===
('INnode1.in1->OUTnode1.out3', 'INnode1.in2->OUTnode2.out4', 
'INnode2.in1->OUTnode2.out3', 'INnode2.in2->OUTnode1.out4')

=== Configuration 6  state = (0, 0, 0, 1, 0, 1) ===
('INnode1.in1->OUTnode1.out3', 'INnode1.in2->OUTnode2.out3', 
'INnode2.in1->OUTnode2.out4', 'INnode2.in2->OUTnode1.out4')

=== Configuration 7  state = (0, 0, 0, 1, 1, 0) ===
('INnode1.in1->OUTnode1.out4', 'INnode1.in2->OUTnode2.out4', 
'INnode2.in1->OUTnode2.out3', 'INnode2.in2->OUTnode1.out3')

=== Configuration 8  state = (0, 0, 0, 1, 1, 1) ===
('INnode1.in1->OUTnode1.out4', 'INnode1.in2->OUTnode2.out3', 
'INnode2.in1->OUTnode2.out4', 'INnode2.in2->OUTnode1.out3')

=== Configuration 9  state = (0, 0, 1, 0, 0, 0) ===
('INnode1.in1->OUTnode2.out3', 'INnode1.in2->OUTnode1.out4', 
'INnode2.in1->OUTnode1.out3', 'INnode2.in2->OUTnode2.out4')

=== Configuration 10  state = (0, 0, 1, 0, 0, 1) ===
('INnode1.in1->OUTnode2.out4', 'INnode1.in2->OUTnode1.out4', 
'INnode2.in1->OUTnode1.out3', 'INnode2.in2->OUTnode2.out3')

=== Configuration 11  state = (0, 0, 1, 0, 1, 0) ===
('INnode1.in1->OUTnode2.out3', 'INnode1.in2->OUTnode1.out3', 
'INnode2.in1->OUTnode1.out4', 'INnode2.in2->OUTnode2.out4')

=== Configuration 12  state = (0, 0, 1, 0, 1, 1) ===
('INnode1.in1->OUTnode2.out4', 'INnode1.in2->OUTnode1.out3', 
'INnode2.in1->OUTnode1.out4', 'INnode2.in2->OUTnode2.out3')

=== Configuration 13  state = (0, 0, 1, 1, 0, 0) ===
('INnode1.in1->OUTnode2.out3', 'INnode1.in2->OUTnode2.out4', 
'INnode2.in1->OUTnode1.out3', 'INnode2.in2->OUTnode1.out4')

=== Configuration 14  state = (0, 0, 1, 1, 0, 1) ===
('INnode1.in1->OUTnode2.out4', 'INnode1.in2->OUTnode2.out3', 
'INnode2.in1->OUTnode1.out3', 'INnode2.in2->OUTnode1.out4')

=== Configuration 15  state = (0, 0, 1, 1, 1, 0) ===
('INnode1.in1->OUTnode2.out3', 'INnode1.in2->OUTnode2.out4', 
'INnode2.in1->OUTnode1.out4', 'INnode2.in2->OUTnode1.out3')

=== Configuration 16  state = (0, 0, 1, 1, 1, 1) ===
('INnode1.in1->OUTnode2.out4', 'INnode1.in2->OUTnode2.out3', 
'INnode2.in1->OUTnode1.out4', 'INnode2.in2->OUTnode1.out3')

=== Configuration 17  state = (0, 1, 0, 1, 0, 0) ===
('INnode1.in1->OUTnode1.out3', 'INnode1.in2->OUTnode2.out4', 
'INnode2.in1->OUTnode1.out4', 'INnode2.in2->OUTnode2.out3')

=== Configuration 18  state = (0, 1, 0, 1, 0, 1) ===
('INnode1.in1->OUTnode1.out3', 'INnode1.in2->OUTnode2.out3', 
'INnode2.in1->OUTnode1.out4', 'INnode2.in2->OUTnode2.out4')

=== Configuration 19  state = (0, 1, 0, 1, 1, 0) ===
('INnode1.in1->OUTnode1.out4', 'INnode1.in2->OUTnode2.out4', 
'INnode2.in1->OUTnode1.out3', 'INnode2.in2->OUTnode2.out3')

=== Configuration 20  state = (0, 1, 0, 1, 1, 1) ===
('INnode1.in1->OUTnode1.out4', 'INnode1.in2->OUTnode2.out3', 
'INnode2.in1->OUTnode1.out3', 'INnode2.in2->OUTnode2.out4')

=== Configuration 21  state = (0, 1, 1, 0, 0, 0) ===
('INnode1.in1->OUTnode2.out3', 'INnode1.in2->OUTnode1.out4', 
'INnode2.in1->OUTnode2.out4', 'INnode2.in2->OUTnode1.out3')

=== Configuration 22  state = (0, 1, 1, 0, 0, 1) ===
('INnode1.in1->OUTnode2.out4', 'INnode1.in2->OUTnode1.out4', 
'INnode2.in1->OUTnode2.out3', 'INnode2.in2->OUTnode1.out3')

=== Configuration 23  state = (0, 1, 1, 0, 1, 0) ===
('INnode1.in1->OUTnode2.out3', 'INnode1.in2->OUTnode1.out3', 
'INnode2.in1->OUTnode2.out4', 'INnode2.in2->OUTnode1.out4')

=== Configuration 24  state = (0, 1, 1, 0, 1, 1) ===
('INnode1.in1->OUTnode2.out4', 'INnode1.in2->OUTnode1.out3', 
'INnode2.in1->OUTnode2.out3', 'INnode2.in2->OUTnode1.out4')

:::
With some example light paths

=== Configuration 24  state = (0, 1, 1, 0, 1, 1) ===
['Current:INnode1 in1 -> Next: X1 1', 'Current:X1 1 -> Next: X1 3', 
'Current:X1 3 -> Next: X3 1', 'Current:X3 1 -> Next: X3 4', 
'Current:X3 4 -> Next: X6 1', 'Current:X6 1 -> Next: X6 4', 
'Current:X6 4 -> Next: OUTnode2 out4']
['Current:INnode1 in2 -> Next: X1 2', 'Current:X1 2 -> Next: X1 4', 
'Current:X1 4 -> Next: X4 1', 'Current:X4 1 -> Next: X4 3', 
'Current:X4 3 -> Next: X5 2', 'Current:X5 2 -> Next: X5 3', 
'Current:X5 3 -> Next: OUTnode1 out3']
['Current:INnode2 in1 -> Next: X2 1', 'Current:X2 1 -> Next: X2 4', 
'Current:X2 4 -> Next: X4 2', 'Current:X4 2 -> Next: X4 4', 
'Current:X4 4 -> Next: X6 2', 'Current:X6 2 -> Next: X6 3', 
'Current:X6 3 -> Next: OUTnode2 out3']
['Current:INnode2 in2 -> Next: X2 2', 'Current:X2 2 -> Next: X2 3', 
'Current:X2 3 -> Next: X3 2', 'Current:X3 2 -> Next: X3 3', 
'Current:X3 3 -> Next: X5 1', 'Current:X5 1 -> Next: X5 4', 
'Current:X5 4 -> Next: OUTnode1 out4']
-----

Furthermore, the program can be used to simulate all the possible light path in a 8X8 non-blocking switch, as indicated below, there are indeed 8! = 40320 comfigurations. However, the time complexity of the exhaustive program is in $O(2^{nodes} * N_{inputs})$, which is obviously not pratical in bigger structure(like 16X16 etc.). In fact, in practice, the 8X8 results took me about 10 minutes to compute, compare to within a second in 4X4 cases.
Hence studies in finding the states of each configurations by algorithm is necessarily.

:::spoiler code

def set_inter_connection():
    set_port_interconnection("X1", "3", "X5", "1")
    set_port_interconnection("X1", "4", "X7", "1")
    set_port_interconnection("X2", "3", "X5", "2")
    set_port_interconnection("X2", "4", "X7", "2")
    set_port_interconnection("X3", "3", "X6", "1")
    set_port_interconnection("X3", "4", "X8", "1")
    set_port_interconnection("X4", "3", "X6", "2")
    set_port_interconnection("X4", "4", "X8", "2")

    set_port_interconnection("X5", "3", "X9", "1")
    set_port_interconnection("X5", "4", "X10", "1")
    set_port_interconnection("X6", "3", "X9", "2")
    set_port_interconnection("X6", "4", "X10", "2")
    set_port_interconnection("X7", "3", "X11", "1")
    set_port_interconnection("X7", "4", "X12", "1")
    set_port_interconnection("X8", "3", "X11", "2")
    set_port_interconnection("X8", "4", "X12", "2")

    set_port_interconnection("X9", "3", "X13", "1")
    set_port_interconnection("X9", "4", "X14", "1")
    set_port_interconnection("X10", "3", "X13", "2")
    set_port_interconnection("X10", "4", "X14", "2")
    set_port_interconnection("X11", "3", "X15", "1")
    set_port_interconnection("X11", "4", "X16", "1")
    set_port_interconnection("X12", "3", "X15", "2")
    set_port_interconnection("X12", "4", "X16", "2")

    set_port_interconnection("X13", "3", "X17", "1")
    set_port_interconnection("X13", "4", "X18", "1")
    set_port_interconnection("X14", "3", "X19", "1")
    set_port_interconnection("X14", "4", "X20", "1")
    set_port_interconnection("X15", "3", "X17", "2")
    set_port_interconnection("X15", "4", "X18", "2")
    set_port_interconnection("X16", "3", "X19", "2")
    set_port_interconnection("X16", "4", "X20", "2")

    set_port_interconnection("X17", "3", "OUTnode1", "out3")
    set_port_interconnection("X17", "4", "OUTnode1", "out4")
    set_port_interconnection("X18", "3", "OUTnode2", "out3")
    set_port_interconnection("X18", "4", "OUTnode2", "out4")
    set_port_interconnection("X19", "3", "OUTnode3", "out3")
    set_port_interconnection("X19", "4", "OUTnode3", "out4")
    set_port_interconnection("X20", "3", "OUTnode4", "out3")
    set_port_interconnection("X20", "4", "OUTnode4", "out4")

    set_port_interconnection("INnode1", "in1", "X1", "1")
    set_port_interconnection("INnode1", "in2", "X1", "2")
    set_port_interconnection("INnode2", "in1", "X2", "1")
    set_port_interconnection("INnode2", "in2", "X2", "2")
    set_port_interconnection("INnode3", "in1", "X3", "1")
    set_port_interconnection("INnode3", "in2", "X3", "2")
    set_port_interconnection("INnode4", "in1", "X4", "1")
    set_port_interconnection("INnode4", "in2", "X4", "2")

:::

:::spoiler result

...
=== Configuration 40314  state = (0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1) ===
('INnode1.in1->OUTnode4.out4', 'INnode1.in2->OUTnode2.out4', 
'INnode2.in1->OUTnode4.out3', 'INnode2.in2->OUTnode1.out4',
'INnode3.in1->OUTnode1.out3', 'INnode3.in2->OUTnode3.out3', 
'INnode4.in1->OUTnode3.out4', 'INnode4.in2->OUTnode2.out3')

=== Configuration 40315  state = (0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0) ===
('INnode1.in1->OUTnode4.out3', 'INnode1.in2->OUTnode2.out4', 
'INnode2.in1->OUTnode4.out4', 'INnode2.in2->OUTnode1.out4', 
'INnode3.in1->OUTnode1.out3', 'INnode3.in2->OUTnode3.out4', 
'INnode4.in1->OUTnode3.out3', 'INnode4.in2->OUTnode2.out3')

=== Configuration 40316  state = (0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1) ===
('INnode1.in1->OUTnode4.out4', 'INnode1.in2->OUTnode2.out4', 
'INnode2.in1->OUTnode4.out3', 'INnode2.in2->OUTnode1.out4', 
'INnode3.in1->OUTnode1.out3', 'INnode3.in2->OUTnode3.out4', 
'INnode4.in1->OUTnode3.out3', 
'INnode4.in2->OUTnode2.out3')

=== Configuration 40317  state = (0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0) ===
('INnode1.in1->OUTnode4.out3', 'INnode1.in2->OUTnode2.out3', 
'INnode2.in1->OUTnode4.out4', 'INnode2.in2->OUTnode1.out4', 
'INnode3.in1->OUTnode1.out3', 'INnode3.in2->OUTnode3.out3', 
'INnode4.in1->OUTnode3.out4', 'INnode4.in2->OUTnode2.out4')

=== Configuration 40318  state = (0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1) ===
('INnode1.in1->OUTnode4.out4', 'INnode1.in2->OUTnode2.out3', 
'INnode2.in1->OUTnode4.out3', 'INnode2.in2->OUTnode1.out4', 
'INnode3.in1->OUTnode1.out3', 'INnode3.in2->OUTnode3.out3', 
'INnode4.in1->OUTnode3.out4', 'INnode4.in2->OUTnode2.out4')

=== Configuration 40319  state = (0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0) ===
('INnode1.in1->OUTnode4.out3', 'INnode1.in2->OUTnode2.out3',
'INnode2.in1->OUTnode4.out4', 'INnode2.in2->OUTnode1.out4', 
'INnode3.in1->OUTnode1.out3', 'INnode3.in2->OUTnode3.out4', 
'INnode4.in1->OUTnode3.out3', 'INnode4.in2->OUTnode2.out4')

=== Configuration 40320  state = (0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1) ===
('INnode1.in1->OUTnode4.out4', 'INnode1.in2->OUTnode2.out3', 
'INnode2.in1->OUTnode4.out3', 'INnode2.in2->OUTnode1.out4', 
'INnode3.in1->OUTnode1.out3', 'INnode3.in2->OUTnode3.out4', 
'INnode4.in1->OUTnode3.out3', 'INnode4.in2->OUTnode2.out4')

:::
## Benes Network without crossing
In a traditional Benes network, the number of nodes is minimized; however, some connections between nodes involve crossovers, which are sometimes acceptable in platforms such as PICs. R.A. Spanke and V.E. Benes. [3] proposed a schematic that uses more nodes
$\frac{N(N-1)}{2}$than a traditional Benes network, but achieves a non-crossover configuration. This design can also be extended to an N×N switch.
Again, the schematic can be demonstrated by the program

TODO:Apply the algorithm of Benes Network to this schematic
 Using graph theory to find if there are others possible solutions


:::spoiler code

def set_inter_connection():
    set_port_interconnection("X1", "3", "X3", "2")
    set_port_interconnection("X1", "4", "X4", "2")
    set_port_interconnection("X2", "3", "X5", "1")
    set_port_interconnection("X2", "4", "X3", "1")

    set_port_interconnection("X3", "3", "X5", "2")
    set_port_interconnection("X3", "4", "X4", "1")

    set_port_interconnection("X4", "3", "X6", "2")
    set_port_interconnection("X4", "4", "OUTnode2", "out4")
    set_port_interconnection("X5", "3", "OUTnode1", "out3")
    set_port_interconnection("X5", "4", "X6", "1")

    set_port_interconnection("X6", "3", "OUTnode1", "out4")
    set_port_interconnection("X6", "4", "OUTnode2", "out3")

    set_port_interconnection("INnode1", "in1", "X2", "1")
    set_port_interconnection("INnode1", "in2", "X2", "2")
    set_port_interconnection("INnode2", "in1", "X1", "1")
    set_port_interconnection("INnode2", "in2", "X1", "2")

:::
:::spoiler result
=== Configuration 1 state = (0, 0, 0, 0, 0, 0) ===
('INnode1.in1->OUTnode1.out3', 'INnode1.in2->OUTnode1.out4', 'INnode2.in1->OUTnode2.out3', 'INnode2.in2->OUTnode2.out4')

=== Configuration 2 state = (0, 0, 0, 0, 0, 1) ===
('INnode1.in1->OUTnode1.out3', 'INnode1.in2->OUTnode2.out3', 'INnode2.in1->OUTnode1.out4', 'INnode2.in2->OUTnode2.out4')

=== Configuration 3 state = (0, 0, 0, 0, 1, 0) ===
('INnode1.in1->OUTnode1.out4', 'INnode1.in2->OUTnode1.out3', 'INnode2.in1->OUTnode2.out3', 'INnode2.in2->OUTnode2.out4')

=== Configuration 4 state = (0, 0, 0, 0, 1, 1) ===
('INnode1.in1->OUTnode2.out3', 'INnode1.in2->OUTnode1.out3', 'INnode2.in1->OUTnode1.out4', 'INnode2.in2->OUTnode2.out4')

=== Configuration 5 state = (0, 0, 0, 1, 0, 0) ===
('INnode1.in1->OUTnode1.out3', 'INnode1.in2->OUTnode1.out4', 'INnode2.in1->OUTnode2.out4', 'INnode2.in2->OUTnode2.out3')

=== Configuration 6 state = (0, 0, 0, 1, 0, 1) ===
('INnode1.in1->OUTnode1.out3', 'INnode1.in2->OUTnode2.out3', 'INnode2.in1->OUTnode2.out4', 'INnode2.in2->OUTnode1.out4')

=== Configuration 7 state = (0, 0, 0, 1, 1, 0) ===
('INnode1.in1->OUTnode1.out4', 'INnode1.in2->OUTnode1.out3', 'INnode2.in1->OUTnode2.out4', 'INnode2.in2->OUTnode2.out3')

=== Configuration 8 state = (0, 0, 0, 1, 1, 1) ===
('INnode1.in1->OUTnode2.out3', 'INnode1.in2->OUTnode1.out3', 'INnode2.in1->OUTnode2.out4', 'INnode2.in2->OUTnode1.out4')

=== Configuration 9 state = (0, 0, 1, 0, 1, 0) ===
('INnode1.in1->OUTnode1.out4', 'INnode1.in2->OUTnode2.out3', 'INnode2.in1->OUTnode1.out3', 'INnode2.in2->OUTnode2.out4')

=== Configuration 10 state = (0, 0, 1, 0, 1, 1) ===
('INnode1.in1->OUTnode2.out3', 'INnode1.in2->OUTnode1.out4', 'INnode2.in1->OUTnode1.out3', 'INnode2.in2->OUTnode2.out4')

=== Configuration 11 state = (0, 0, 1, 1, 0, 0) ===
('INnode1.in1->OUTnode1.out3', 'INnode1.in2->OUTnode2.out4', 'INnode2.in1->OUTnode1.out4', 'INnode2.in2->OUTnode2.out3')

=== Configuration 12 state = (0, 0, 1, 1, 0, 1) ===
('INnode1.in1->OUTnode1.out3', 'INnode1.in2->OUTnode2.out4', 'INnode2.in1->OUTnode2.out3', 'INnode2.in2->OUTnode1.out4')

=== Configuration 13 state = (0, 0, 1, 1, 1, 0) ===
('INnode1.in1->OUTnode1.out4', 'INnode1.in2->OUTnode2.out4', 'INnode2.in1->OUTnode1.out3', 'INnode2.in2->OUTnode2.out3')

=== Configuration 14 state = (0, 0, 1, 1, 1, 1) ===
('INnode1.in1->OUTnode2.out3', 'INnode1.in2->OUTnode2.out4', 'INnode2.in1->OUTnode1.out3', 'INnode2.in2->OUTnode1.out4')

=== Configuration 15 state = (0, 1, 1, 1, 0, 0) ===
('INnode1.in1->OUTnode2.out4', 'INnode1.in2->OUTnode1.out3', 'INnode2.in1->OUTnode1.out4', 'INnode2.in2->OUTnode2.out3')

=== Configuration 16 state = (0, 1, 1, 1, 0, 1) ===
('INnode1.in1->OUTnode2.out4', 'INnode1.in2->OUTnode1.out3', 'INnode2.in1->OUTnode2.out3', 'INnode2.in2->OUTnode1.out4')

=== Configuration 17 state = (0, 1, 1, 1, 1, 0) ===
('INnode1.in1->OUTnode2.out4', 'INnode1.in2->OUTnode1.out4', 'INnode2.in1->OUTnode1.out3', 'INnode2.in2->OUTnode2.out3')

=== Configuration 18 state = (0, 1, 1, 1, 1, 1) ===
('INnode1.in1->OUTnode2.out4', 'INnode1.in2->OUTnode2.out3', 'INnode2.in1->OUTnode1.out3', 'INnode2.in2->OUTnode1.out4')

=== Configuration 19 state = (1, 0, 1, 0, 1, 0) ===
('INnode1.in1->OUTnode1.out4', 'INnode1.in2->OUTnode2.out3', 'INnode2.in1->OUTnode2.out4', 'INnode2.in2->OUTnode1.out3')

=== Configuration 20 state = (1, 0, 1, 0, 1, 1) ===
('INnode1.in1->OUTnode2.out3', 'INnode1.in2->OUTnode1.out4', 'INnode2.in1->OUTnode2.out4', 'INnode2.in2->OUTnode1.out3')

=== Configuration 21 state = (1, 0, 1, 1, 1, 0) ===
('INnode1.in1->OUTnode1.out4', 'INnode1.in2->OUTnode2.out4', 'INnode2.in1->OUTnode2.out3', 'INnode2.in2->OUTnode1.out3')

=== Configuration 22 state = (1, 0, 1, 1, 1, 1) ===
('INnode1.in1->OUTnode2.out3', 'INnode1.in2->OUTnode2.out4', 'INnode2.in1->OUTnode1.out4', 'INnode2.in2->OUTnode1.out3')

=== Configuration 23 state = (1, 1, 1, 1, 1, 0) ===
('INnode1.in1->OUTnode2.out4', 'INnode1.in2->OUTnode1.out4', 'INnode2.in1->OUTnode2.out3', 'INnode2.in2->OUTnode1.out3')

=== Configuration 24 state = (1, 1, 1, 1, 1, 1) ===
('INnode1.in1->OUTnode2.out4', 'INnode1.in2->OUTnode2.out3', 'INnode2.in1->OUTnode1.out4', 'INnode2.in2->OUTnode1.out3')
:::
A example of the 8X8 nonblocking switch with $\frac{8 * 7}{2} = 28$ nodes using this schematic is

with the simulation setup as below, however, the time rasie expoentially since $\frac{2^{28}}{2^{20}} = 256$ will take more than 2560 miniutes. A revise is needed for the program.
## GUI
A GUI is designed (by Gemini) to simulate a 4X4 switch. The function is limited to setup the connection of 6 2X2 switches right now, but it could be potential useful if we can add more nodes on it (still needed to be investigate).
The whole program is published on github
[nonblkswitch](https://github.com/timchien-prog/nonblkswitch.git)

## Reference
[1] Karimi, A., Aghakhani, K., Manavi, S. E., Zarafshan, F., & Al-Haddad, S. A. R. (2014). Introduction and analysis of optimal routing algorithm in Benes networks. Procedia Computer Science, 42, 313–319.
[2] Yang, M., Green, W. M. J., Assefa, S., Van Campenhout, J., Lee, B. G., Jahnes, C. V., Doany, F. E., Schow, C. L., Kash, J. A., & Vlasov, Y. A. (2011). Non-blocking 4x4 electro-optic silicon switch for on-chip photonic networks. Optics Express, 19(1), 47–54.
[3] Spanke, R. A., & Benes, V. E. (1987). N-stage planar optical permutation network. Applied Optics, 26(7), 1226–1229.