Fundamental Complexity of Optical Systems Hadas Kogan, Isaac Keslassy

Sizin üçün oyun:

tarix 18.05.2018 ölçüsü 480 b.

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.
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?
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
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) Construction complexity (# switches)
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
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?
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 bounded by the entropy of the states: Proof: Similar to the proof of expected code
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:
Conclusion – construction complexity of optical routers The construction complexity of an OQ-PIFO switch is Θ(Nln(N))+Θ(Nln(B)) = Θ(Nln(NB))
Thank you!
Dostları ilə paylaş:

Orklarla döyüş: