Fundamental Complexity of Optical Systems Hadas Kogan, Isaac Keslassy

Fundamental Complexity of Optical Systems

• Hadas Kogan, Isaac Keslassy

• Technion (Israel)

Router – schematic representation

• Problem - electronic routers do not scale to optical speeds:

• Access to electronic memory is slow and power consuming.

• Data conversions are power consuming as well.

Power consumption per chassis

How about an optical router?

• No electronic memory bottleneck

• No O/E/O conversions

• BUT:

• An optical router is thought to be too complex.

• Is it?

Optical router complexity

• Objective: quantify the fundamental complexity of an optical router

• Two types of fundamental complexity:

• Construction complexity: number of basic optical components needed (e.g., 2x2 optical switches)

• Control complexity: frequency of optical switch reconfigurations

Main contributions

• Define fundamental complexity in general optical constructions:

• Control complexity
• Construction complexity

• Find lower and upper bounds on these costs.

• Construct optical router with minimum complexity.

Outline

• Background

• Control complexity (# switch reconfigurations)

• Definition
• Bounds

• Construction complexity (# switches)

• Definition
• Optimally constructed constructions

Two possible ways to “store” light

• To slow/stop light.

• BUT: requires gas environments with tight temperature and pressure constraints, and currently seems impractical.

• Use optical switches and fiber delay lines.

• .

A naive optical queue with buffer B

What we want: an ideal router

• An output-queued push-in-first-out (OQ-PIFO) switch.

• OQ - Arriving packets are placed immediately in the queue of size B at their destination output.

• PIFO – packets departure ordering is according to their priority.

What we want: an ideal router

• Why it is ideal:

• OQ: Work conserving implies best throughput and minimal delay.
• PIFO: Enables FIFO, strict priorities, WFQ…

• But – up to N packets destined to the same output:

• Speed-up for switch
• Speed-up for queue
• PIFO is hard to implement.

How do we do it in optics?

• If packets are destined to different outputs:

• Switching: optical switch NxN with O(NlnN) 2x2 optical switches ([Shannon ’49], [Benes ’67]).

• Buffering: optical PIFO queue B 2x2 optical switches ([Sarwate & Anantharam ’04]).

Control complexity

Generalization to systems

• An optical system - a network element that has input links, output links and inner states, and is built with optical 2x2 switches and FDLs.

• Inner states - the different settings of the system elements. External states – distinguishable possible system outputs.

Definition

• Control complexity – a measure of the minimal expected number of switch reconfigurations.

• Example:

• 4 inputs, 4 outputs,

• 3 external states:

• What is the control complexity of an optical system with these states?

Link to coding

• Source symbols:
• A1 – w.p. 0.5
• A2 – w.p. 0.25
• A3 – w.p. 0.25
• A 2x2 switch A binary digit
• State entropy Source entropy
• ??? Minimizing expected code length
• Coding results should apply also to switching!

Definitions

• A super switch:

• Passive and active controls – for each state, a control is called passive if its value is irrelevant for setting that state. Otherwise, it is called active.

Definition – control complexity

• Definition: the control complexity of an optical system is its minimal expected number of active controls,

• T – states space, - number of active controls per state

Link to coding

• Source symbols:
• A1 – w.p. 0.5
• A2 – w.p. 0.25
• A3 – w.p. 0.25
• A 2x2 switch A binary digit.
• States entropy Source entropy
• Minimized expected code length

Lower bound

• Theorem: The control complexity is lower

• bounded by the entropy of the states:

• Proof: Similar to the

• proof of expected code

• length lower bound

An upper bound on the control complexity

• Theorem: The control complexity is upper bounded as follows:

• Stages of proof:

• Generate Huffman coding (expected code length ≤ H+1) .

• There exists a construction (using multiplexers and distributers) of a memoryless system such that the active controls for each state are the Huffman coding of that state

• A system with memory can be composed from a memoryless system using a time-space transformation.

Construction complexity

Definition

• Construction complexity: the minimal possible number of 2x2 switches in the construction.

• Examples:

• An NxN switch:
• N! states, O(NlnN) switches [Shannon, ‘49], [Benes, ‘65].
• A Time Slot Interchange (TSI) with time frame N:
• N! states - O(lnN) switches [Jordan et. al., ‘94].

Construction complexity

• Intuition: With C 2x2 switches during T time slots, the possible number of resulting states K is upper bounded by 2CT.

• Therefore: to get K states in state duration T, a lower bound on the construction complexity is given by:

Optimally-constructed constructions

• A construction algorithm is optimally constructed if its number of 2x2 switches is equal in growth to the construction complexity.

• Examples:

• An NxN switch:
• A TSI:

Conclusion – construction complexity of optical routers

• The construction complexity of an OQ-PIFO switch is Θ(Nln(N))+Θ(Nln(B)) = Θ(Nln(NB))

Thank you!