Fundamental Complexity of Optical Systems Hadas Kogan, Isaac Keslassy



Yüklə 480 b.
tarix18.05.2018
ölçüsü480 b.
#50778


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)



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!



Yüklə 480 b.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin