ALL OPTICAL BATCHER BANYAN SWITCH, BATCHER SWITCH, BANYAN SWITCH AND CONTENTION MANAGER

Field of the invention The present invention relates to all optical Batcher Banyan switches, all optical Batcher switches, all optical Banyan switches and all optical contention managers.

Background of the invention Electronic Batcher Banyan networks are known.

A Banyan network is a self routing one - i.e. a packet sent across the Banyan network reaches its correct, desired destination without the need for an additional controller. Each signal that is input to the Banyan network contains sufficient information, e.g. contained in a header, to be able to route the signal to its desired destination by analysis of the information at component switches within the Banyan network.

Referring to Figure 1 (prior art), a 2 x 2 Banyan switch 10 is shown - i.e. it has 2 inputs and 2 outputs. The switch reads the relevant bit, e.g. the most significant bit (MSB) in a destination tag contained in a header of a packet being sent across a Banyan network having the switch 10 as a component switch. When the packet is being processed through the switch, if the MSB is 0, it is routed to a first output, and if the MSB, is 1 it is routed to a second output.

An n x n Banyan network can be constructed from log ₂ n layers of switches and so a packet sent through an n x n Banyan network should have log ₂ n bits in its destination tag. The switch reads the relevant bit in the destination tag. For example, this may be the MSB in a first stage of the n x n Banyan network followed by the (MSB - 1) at the next stage and so on.

A problem associated with component switches within a Banyan network is that two packets having the same relevant bit, e.g. MSB can overlap at a particular component switch, e.g. by arriving at the inputs of the switch at the same time. The switch will try to send both packets to the same output and a collision occurs. As a result data can be lost. It is known to pre-sort packets prior to processing through a Banyan network. The packets are pre-sorted according to their destination tag information.

This pre-sorting can be carried out by a Batcher network (electronic Batcher networks are known). A Batcher network comprises component switches (see Figure 2), which interrogate the destination tag of, say, 2 incoming packets and compare them. A packet having a higher value tag is routed to a first output and a packet having a relatively low value tag is routed to a second output.

When a Batcher network is employed to sort packets prior to a Banyan network, the networks are usually both of the same size, e.g. a 4 x 4 Batcher network will precede a 4 x 4 Banyan network.

The Batcher network will sort the data packets into an order, which avoids collisions as the packets are processed through the Banyan network. Thus a Batcher Banyan network is provided.

Summary of the Invention

According to an aspect of the invention there is provided a Batcher Banyan network, Batcher switch, Banyan switch or contention manager as claimed.

Brief description of the drawings

Embodiments of the present invention will now be described, by way of example only, with reference to the accompanying drawings, in which:

Figure 1 schematically shows a prior art Banyan switch;

Figure 2 schematically shows a prior art Batcher switch;

Figure 3 is an overview of an optical logical comparator for comparing two N-bit words, where N is greater than 1 ;

Figure 4 is a schematic illustration of an optical gate that can be used as a building block to implement the comparator of Figure 3;

Figure 5 is a detailed view of an embodiment of an optical circuit in accordance with the first aspect of the invention which functions in accordance with the overview of Figure 3;

Figure 6 is a truth table for the logic gate of Figure 4;

Figure 7 illustrates a representative set of output patterns obtained from the circuit of Figure 3 together with the input words A and B used;

Figure 8 plots Q factor against received peak power for A>B and A<B compared with the Q factor of the inputs A and B,

Figure 9 shows an N-bit photonic comparator logic circuit;

Figure 10 shows a 1-bit photonic comparator logic circuit;

Figure 11 is a schematic diagram of a Batcher Banyan network according to an embodiment of this invention;

Figure 12 shows a Batcher switch used in the network of figure 11 ;

Figure 13 shows a contention manager used in the network of figure 11 , and

Figure 14 shows a Banyan switch used in the network of figure 11.

Specific Description

An all optical N-bit comparator is shown in Figure 3. The comparator receives as its input a pair of N-bit words A and B. The comparator comprises a combination of optical logic gates and delay lines which together provide as an output the logical functions A>B, A<B and A=B.

The first stage of the optical circuit is an XOR gate to which each pair of corresponding bits Ak, Bk, k=l ...N, of the signals A, B are passed in sequence. By this we mean that at a first instance the most significant bits Al and Bl are input to the comparator to give a first output C l , then the next bits A2, B2 to give and output C2 and so on until the least significant bits Ak=N, Bk=N are passed to the XOR gate to give an output Ck=N. There will therefore be N results Ck (where k=l to N) produced in a sequence at the output of the XOR gate.

If two bits Ak, Bk passed to the XOR gate at any sampling interval are the same, then the output Ck of the XOR gate will be logic 0. It will be logic 1 if they are different. For any given pair of N bit numbers there will therefore be a corresponding N bit number C produced with a 1 for each pair of bits that do not match and a 0 for each pair that do match. It should be noted that this number C does not provide any information indicative of which of the words A, B is largest.

The next stage of the comparator circuit is an AND gate, which is provided with N inputs. The first input to the AND gate is connected to the output of the XOR gate. The second input is also connected to the output of the AND

gate but this time through an inverter and a delay line giving a delay equal to the time between values of C being output from the XOR gate. The third input is connected to the output of the XOR gate also through an inverter and a delay line, but this time the delay is twice that used for the second input. This pattern is repeated for each input to the AND gate until the Nth input is connected to the output of the XOR gate through a delay line equal to N-I times the first delay time.

Thus, as the first output bit C l of the XOR gate is produced it is passed to the first input of the AND gate. At this time no signals are applied to the other inputs to the AND gate (since there are no previous delayed signals to be presented) so the output of the AND gate will be equal to the first bit

Cl . As the next output C2 is provided from the XOR gate it is applied to the first input to the AND gate, and by this time the first bit Cl will have rippled through to the second input of the AND gate. Because one of the inputs is inverted and the other not, the output of the AND gate will be 1 if

Cl is 0 and C2 is 1 and 0 otherwise. This process is then repeated for each of the N samples Ck, giving N output signals Dk (k=l to N) from the AND gate. Note that as soon as one pair of inputs to the XOR gate do not match then the output of the AND gate is 1. For all subsequent samples it will be

0.

The output of the AND gate will therefore be an N-bit word D where, starting with the most significant bit of the word D, it will contain zeros until the value of Ck is 1.

To determine whether A>B, each output from the AND gate is next coupled to a second AND gate with the current bit of A (i.e. for output Dk where k=m, bit Ak where k=m) will be fed to the AND gate. If the current bit of A is 1 , and the output of the first AND gate is 1 , then this indicates that A>B. If they do not match, then A is either equal to B or less than B.

To determine whether A<B, each output from the AND gate is next coupled to a third AND gate with the current bit of B (i.e. for output Dk where k=m, bit Bk where k=m) will be fed to the AND gate. If the current bit of B is 1 , and the output of the first AND gate is 1 , then this indicates that A<B. If they do not match, then A is either equal to B or greater than B.

Having determined both A<B and A>B the outputs of the second and third AND gates can then be coupled through an OR gate to determine whether A=B.

Note that in place of the first and second AND gates, a gate performing the function X AND NOT Y can be used if the Y input is previously inverted.

A practical embodiment of the comparator of Figure 3 can be realised using a set of semiconductor optical amplifiers configured to provide logical building blocks or logic gates. A suitable gate which provides the functionality A and NOT B is shown in Figure 4. As will become apparent the applicant has appreciated that this can be used to give the function XOR and AND as required.

Each gate comprises a single semiconductor optical amplifier (SOA) having a first input at one end and a second input at the other. The output from the amplifier is taken to be the signal that passes out of the second end of the amplifier. A characteristic of SOA's is that a gain is applied to an input signal which is influenced by the power of the signals input to the amplifier. As the input power increases the gain eventually starts to decrease. A further characteristic is that SOA's are non-linear devices, a signal at one wavelength being able to modulate a signal at another through the well known process of cross gain modulation (XGM).

Coupled to the first end of the amplifier is a continuous wave signal CW of relatively high power and a first, lower power, input signal Lp. Coupled to

the second end is a second, high power, input signal Hp. The two input signals have the same wavelength but the CW is at a different wavelength.

The two counter-propagating input signals interact in the SOA so that the low power signal Lp experiences the gain modulation induced by the stronger second input signal Hp. The CW allows keeping the gain saturation high, thus reducing the SOA recovery time. In effect this means that with no high power signal applied (Hp=O) the output will be 1 when Lp=I and O when Lp=O. On the other hand, when the high power signal Hp=I is applied, the low power signal Lp experiences a strongly reduced SOA gain, giving an output at all times on 0. The output from the gate therefore corresponds to the function (Lp AND NOT Hp). This is shown in the truth table of Figure 6 of the accompanying drawings.

Turning to Figure 5, six gates as shown in Figure 4 can be connected into a circuit which takes the two N-bit numbers as its input and provides outputs for A>B, A<B and NOT A=B. The gates can be identical which eases the design burden.

The first part of the circuit of Figure 3 - the XOR gate- is implemented by passing signals A and B to the first and second inputs of a first gate (gate 1) to give an output corresponding to the logical function (A and NOT B). The same signals are also fed the other way round (to the second and first inputs respectively) to a second gate (gate 2) to give an output corresponding to the function (B and NOT A). The output of the two gates are then combined using a fibre coupler tail (to give an OR function) so as to provide the function (A and NOT B) OR (B and NOT A) which is the same as the function (A XOR B).

The output of the fibre coupler tail is next fed to the first input of a third gate (gate 3) and a delayed version of the same output fed to the second input of the third gate. In fact, for an N-bit word there will be N-I delayed

versions fed to the second input, each delayed by one or more samples. Only one delayed input is shown in Figure 5 for clarity. The output of the third gate will therefore represent the first AND gate function of the circuit of Figure 3. Note that no additional inverters are needed in this case since the function of gate 3 inherently provides the required inversion of the second input.

The output from gate 3 is then passed to the second input of another gate, gate 4. A pulse train synchronised to the sample rate is fed to the first input of gate 4, so that the output of gate 4 is an inverted version of the signal fed to the second input of gate 4 (it is an inverted version of the signal out of gate 3).

The signal output from gate 4 is fed to the second input of gates 5 and 6 respectively. The first input of gate 5 is provided with An as its input and thus this gate gives as its output an indication of A>B. The first input of gate 6 is provided with Bn as its input and thus this gate gives as its output an indication of A<B.

The output from each gate can be passed though an amplifier as required before being fed to a subsequent gate, and may also be passed through a bandpass filter.

In an experimental arrangement to verify the operation of the circuit of Figure 5, N bit signals A and B of wavelength 1556.55nm were used with a continuous wave signal applied to each SOA of 1540nm. Bandpass filters of 0.6nm bandwidth were used to filter the outputs from each gate.

Figure 7 shows the output patterns A>B and A<B together with the corresponding input patterns B and A. The guard bit between two patterns is labelled as g. If A and B are matched, the output is 00 both for A>B and

A<B. If A is higher than B, the output A>B becomes 1 as the first

mismatch occurs. The other bit is 0. A correct behaviour is observed also for A<B, thus demonstrating the scheme works properly.

The extinction ratio is higher than 4.6 dB for A>B and higher than 6 dB for A<B. Since the extinction ratio for the input patterns A and B is higher than 6.3 dB, the penalty introduced by the 2-bit comparator is 1.7 dB for A>B and 0.3 dB for A<B. The different penalties are mostly due to the different characteristics of the SOAs in GATE5 and GATE6.

Figure 8 summarises the performance in terms of Q-factor as a function of the received peak power for the output signals A>B and A<B, compared with the Q-factor of the input patterns A and B. The Q-factor is calculated by the statistics of the noise on the one and the zero level taken with a 50 GHz-bandwidth oscilloscope. The receiver is a pre-amplified receiver. The penalty with respect to the back-to-back, measured at Q=6, is negligible both for A>B and A<B. The penalty of the signal A ₌ B is expected to be comparable, being this signal obtained directly from A>B and A<B (see Figure 3). While the extinction ratio degradation should be dominated by the degradation induced by A>B.

There is therefore provided a specific scalable circuit for comparing two N- bit words (Boolean numbers) which uses 6 identical optical gates and a set of N-I delay lines) Each gate uses one SOA with counter-propagating signals exploiting cross gain modulation. From this scalable circuit the above architecture is achieved as described.

The N-bit photonic comparator can also be represented diagrammatically as shown in figure 9.

Referring to figure 10 a 1-bit photonic comparator is illustrated and made according to the same underlying SOA architecture for equivalent logic gates. It will be appreciated that the 1 bit comparator comprises a simpler

circuit since no delay lines need to be present in order to process information from different bits as with the previously described N-bit comparator.

In an embodiment of this invention there is provided a Batcher network which uses the comparators shown in figures 9 and 10. In another embodiment of the invention there is provided a Banyan network which uses the comparator shown in figure 10. In a further embodiment there is provided a contention manager (whose purpose is described in further detail below) which uses the comparators of figures 9 and 10.

In a further embodiment there is provided a Batcher Banyan switch network which combines the above mentioned Batcher network, contention manager and Banyan network.

Referring to figure 11 , there is shown a Batcher Banyan switch network 90 according to this invention and which comprises four inputs and four outputs. Inputs to the Batcher Banyan switch network are optical signals, as are the output signals. All processing within the Batcher Banyan network is all optical.

The first stage of the Batcher Banyan network 90 is a Batcher sorting network 92. The Batcher sorting network is arranged to sort incoming optical signals into ascending order. In other embodiments the Batcher sorting network may be arranged to sort incoming optical signals into descending order.

Optical signals, once they have been sorted by the Batcher network 92, are passed to inputs of a contention manager 94. A contention manager 94 is arranged to deal with possible contentions (i.e. undesired signal routing which may lead to collisions in the subsequent, Banyan network). Output

signals from the contention manager 94 are passed to a Banyan network 96 which is arranged to route the optical signals to a desired output.

In this embodiment, an optical signal 98 which is required to be processed comprises a bit payload and a label (or tag) 100. The label/tag 100 comprises a priority bit (P) which provides an indication of whether the signal 98 is to have priority over other signals, a two bit address (A) which provides information on the desired end output address and a packet recognition bit (PR).

Together, the priority bit (P), the address bit (A) and the packet recognition bit (PR) form the destination tag or label 100 comprising destination information that can be processed by the individual components of the Batcher Banyan switch network 90 for correct routing of the optical signal 98. in other embodiments the label 100 may comprise only some of these components or may contain additional components.

In this embodiment, the Batcher sorting network 92 is a series of 3 by 2 (3 x 2) (i.e. a total of 6) Batcher sorting switches 102. Each switch 102 has two inputs and two outputs.

The contention manager has four inputs and four outputs. Therefore there are two Batcher switches 102 immediately preceding the contention manager 94. The Banyan network comprises a 2 x 2 array of Banyan switches 104. Each Banyan switch 104 comprises two inputs and two outputs and so there are two Banyan switches 104 immediately following the contention manager.

Referring to figure 12, a Batcher switch 102 is shown in more detail.

The logic functions which are depicted in figures 12 to 14 are readily achievable using SOA modules and circuits as described in detail above.

The Batcher switch 102 receives two input signals, Ini and In ₂ . The input signals are initially sent to a label extraction means 106. Within the label extraction means, the destination label 100 is interrogated such that the priorities, Pi and P ₂ of the input signals Ini and In ₂ are compared; the addresses, Ai and A ₂ of the input signals are compared; and the packet recognition bits PRi and PR ₂ of the input signals are compared. In the label extraction means 106 the relevant bits are extracted and separated.

When comparing the priority bits, Pi and P ₂ , the separated priority bits, Pi and P ₂ are passed into the two inputs of a one bit photonic comparator (as shown in figure 10). In this way it is determined whether or not Pi is greater than P ₂ , Pi is less than P ₂ or Pi equals P ₂ .

Similarly, the address bits, Ai and A ₂ , from the two signals are passed to the two inputs of a 2-bit photonic comparator (i.e. the photonic comparator of figure 9 where N equals 2). It is thus determined whether or not Ai equals A ₂ (i.e. whether the desired destination addresses are the same), or whether the destination addresses are different.

If it is found that the destination addresses are different, i.e. Ai does not equal A ₂ , then each signal, In ₁ , In ₂ is passed to its correct, desired output via an optical gate generator 108 and switching fabric 110. The optical gate generator 108 can generate an optical gate for as long as is required in the optical domain. The switching fabric 110 can switch to a different output, Outi or Out ₂ as required. For example if Ai contains destination information indicating that Ai is greater than A ₂ , then in this embodiment Outi is designated as being greater than Out ₂ , i.e. higher value addresses are routed to it such that when Ai is greater than A ₂ , Ai is routed to Outi and A ₂ is routed to Out ₂ . There is no conflict.

In the scenario where there is a conflict, i.e. the address comparison determines that Ai equals A ₂ , then the priority comparison becomes determinative. In this scenario, the higher priority signal will be routed to the correct, desired output, whilst the other, relatively lower priority signal will be routed to the remaining output. Therefore if Ai equals A ₂ but Pi is greater than P ₂ then Ai will be routed to Outi and In ₂ will be routed to Out ₂ .

In the scenario where Ai equals A ₂ and Pi equals P ₂ , there is a default position in which Ini is sent to Outi and In ₂ is therefore sent to Out ₂ . This determination is made simply on the basis of the input port, Ini taking precedent over the input port, In ₂ .

The Batcher switch 102 compares addresses A ₁ , A ₂ of input signals Ini and In ₂ respectively to determine whether address Ai is greater than address A ₂ or whether address Ai is less than A ₂ or whether Ai equals A ₂ . The output port, Outi and Out ₂ are designated for outputting relatively high or low address signals. Therefore the Batcher sorting network 92 will sort incoming signals into ascending/descending order. All processing is carried out entirely in the optical domain and so very efficient processing is provided. There is no time delay/distortion which arises as a result of undesirable conversion of optical signals into electrical signals.

The contention manager 94 comprises four inputs, In ₁ , In ₂ , In ₃ and In ₄ for receiving optical signals after they have been sorted by the Batcher network 92. The incoming signals will be in ascending order in this embodiment. The contention manager comprises a contention management means 120. The contention management means 120 compares priority bits, P ₁ , P ₂ , P ₃ and P ₄ from the four input signals. The contention management means 120 also compares addresses, A ₁ , A ₂ , A ₃ , A ₄ of the input signals. It is only necessary to compare adjacent input signals, i.e. Ini with In ₂ and In ₂ with In ₃ and In ₃ with In ₄ . Therefore only three comparisons need to be made in

this example. This is because the signals are already in ascending order since they have been pre-sorted by the Batcher network.

Once again, when comparing priorities, the one bit photonic comparator of figure 10 is used. When comparing addresses, the two bit photonic comparator (where N equals 2 in the figure 9 comparator) is used.

If it is determined that there is contention, i.e. more than one signal input desires to go to the same output (Outi, OUt ₂ , Out3 or OUt ₄ ) then the contention must be resolved. In this contention manager 94, the contention is resolved by a packet eraser 122. It is determined which signals have the highest priority and for any signals requiring to go to the same output address, any lower priority signals are erased by the packet eraser 122. If both the desired destination address and priority are identical for two input signals, then the determining factor for deciding which signal should be erased by the packet eraser 122 is the identity of the input port (similarly to the resolution in the Batcher switch where the incoming signal at input port 1 will be chosen over the input signal at any of the other input ports for example).

Considering an example in which a packet is erased from Out ₂ in this embodiment, the result of the signals passing through the contention manager is that there is an output at Outi, an output at Out3 and an output at Out ₄ but no output at Out ₂ . It is known that it is not desirable to have an input to the Banyan network 96 which includes a gap within the output (the gap being at Out ₂ ). It is more desirable to have a group of outputs which are grouped together without any gaps (if there must be one gap, then it is desirable that it is at one of the edges, either Outi or Out ₄ ). Therefore the contention manager 94 includes a packet concentrator 124 preceding the four output ports. The packet concentrator 124 is arranged to reorganise the packets once any contentions have been resolved so that they are output at output ports which are adjacent to each other without any gaps. This

avoids any unnecessary undesirable behaviour in the Banyan network caused by interference due to having gaps within the arrangement of output signals from the contention manager 94.

All processing within the contention manager 94 is entirely in the optical domain. There is no conversion, at any point, of the optical signals into the electrical domain.

Referring to figure 14, a switch 104 of the Banyan switching network 96 is shown. The Banyan switch 104 initially comprises an address extraction module 126 which is arranged to organise the address of the incoming signals into order by extracting the most significant bit (MSB), then the most significant bit minus 1 , then the most significant bit minus 2.... etc.

This is achieved by a delay line as described above. The delay line in this embodiment effectively comprises making the part of the signal to be delayed travel an extra distance relative to the part of the signal which is not required to be delayed.

The bits to be compared, (e.g. the most significant bit) Ai and A ₂ from each signal are passed to the input of a one bit photonic comparator (as shown in figure 10) in order to determine which is larger than the other. This is done in the successive stages for all of the bits within the addresses A ₁ , A ₂ such that the desired destination address can be reached. The signals are then passed through an optical gate generator 128 and switching fabric 130 to route them to their desired outputs, Outi or Out ₂ . Prior to the Banyan network 96, the signals have been ordered and any contentions resolved as described above so that there is no contention in the Banyan network 96.

The processing within the Banyan network switches 104 is entirely optical. There is no conversion of any signal at any stage into the electrical domain.

Accordingly in this embodiment, there is provided a highly modular architecture of an all optical interconnection network capable of forwarding fixed length optical packets up to 160Gb/s. It consists of different configurations of a single discrete element exploiting cross gain modulation in semi conductor optical amplifiers. The solution which has been proposed is suitable for implementation as an integrated all optical chip.

Various modifications may be made to the present invention without departing from its scope. For example different dimensions of Batcher, Banyan and contention manager and Batcher Banyan networks may be provided using the principles of this invention. For example in the contention manager, it will be appreciated that (X - 1) photonic comparisons are required to compare X incoming input signals. In the N bit photonic comparator of figure 9, as N increases and larger addresses need to be compared, there is no requirement for additional, complex component architecture. Advantageously the present invention provides for a system where extra delay lines simply need to be built into the comparator of figure 9. These are easily provided, for example by making an optical signal travel a further distance, a suitable delay line can be provided.

Therefore it will be appreciated that the system described above is efficiently and easily scalable.