当前位置 博文首页 > Optics_css：Birkhoff-von Neumann Crossbar 光交换网络的调度方
? This is a summary aimed at looking for "high performance novel scheduling algorithm for fast optical switch in data center network"
? 主要基于 [1~6]，也包含一些对 optical data center network 相关技术的理解，并且拿了一个自以为蛮漂亮的调度算法做为了例子( ?? ω ?? )?，ゲームをする！
? 这里首先对 optical data center network 的目标优势与挑战进行一些概述 [1]，而后介绍这一技术中占据较重要地位的光交换机 (我有时也很随意地直接叫它光开关) 技术
? 光数据中心网络 (optical data center networks, optical DCNs) 是被用以符合高容量，低延迟，细粒度的 DCN 需求的一种架构，它有望弥补下面列举的几条传统电子方案的缺陷 [1.1]
- In hierarchical tree-like topology based on electronic switch, the scaling issues of ball grid array (BGA) package causing bandwidth limited by application-specific integrated circuits (ASICs) input/output (I/O) bandwidth
- Electronic switch achieves higher bandwidth by stacking ASICs in multitier structure, which leads to larger latency and higher cost;
- Electronic circuit-based solution is facing a difficulties when large interconnectivity and fast reconfiguration are required;
- Storing and transmitting properties of electronic switch have significant power dissipation, and the optical/electronic/optical (O/E/O) conversions and format-dependent interfaces will perform lower power/cost efficiency.
? 这就成为了故事的开端，可以发现这些困境大体是电子器件的一些内禀性质 (fermion... ... 好麻烦... ...) 所导致的，有一些甚至是不可避免的
? 另一方面，从下面的表格就可以看出光子学解决方案的“显著”优势，它几乎覆盖了人们对于未来 DCN 的所有幻想，这样，各种光交换机与一些调度算法或许能在这里拥有自己的一片天空... ...
| Requirements | Optical Solution |
|---|---|
| Capacity <bandwidth for more inter-rack & intra-cluster communication> |
<wavelength division multiplex (WDM) to provide power per unit bandwidth> |
| Latency <switch latency from buffering & routing algorithm & arbitration> |
<optical packet/burst switching (OBS, OPS) based on fast optical circuit switching (OCS)> |
| Interconnectivity <support concurrent flows & bandwidth ultilization & service delivery> |
<(high-capacity) optical interconnection technology> |
| Scalability <scale nodes number for future capacity & cost> |
<photonic integration may provide scaling without loss of capacity and power/cost> |
| Flexibility <manage servise delivery & adapt to changing needs> |
<software-defined networking (SDN) is used to facilitate highly flexible provisioning> |
| Power/Cost Efficiency <reduce cost & scale bandwidth> |
<data traffic in optical domain, no O/E/O power consumption> |
? 顺带一提，里面涉及到的 OPS/OBS，光分组交换/光突发交换技术能借由突发流的统计复用实现亚波长的带宽粒度，其中，OPS 网络在相同信道中同时/先后传输包头 (package header) 与数据包 (package, \(\it10^2\rm\ ns\sim\it10^2\rm\ ms\))，不需要提前预留连接，也有很好的 bandwidth efficiency，适合于 DC 较小数据量的传输，OBS 则借助于大量的突发 (burst, \(\it10\sim10^3\rm\ ms\)) 与先于其在 (物理上的) 分离信道中发送的块控制数据头 (block control header, BCH) 实现资源预留，保留 OPS 的 flexibility 以及 efficiency 的同时降低了对光交换机和光缓存的要求，因为一般光交换机的 reconfiguration time 需要远小于包/突发的时长
? 作为 optical DCNs 架构的实例，可以参考 Opsquare: A flat DCN architecture based on flow-controlled optical packet switches [4] 以及 Torus-topology Data Center Network based on Optical Packet/Agile Circuit Switching with Intelligent Flow Management [5] 这两种基于 OPS 的架构，它们在当前 (\(\it2020\pm\)) 各种架构中拥有相对较优的性能，都有将 electronic buffer (EB) 设置在网络连接部分，从而起到在冲突中重传数据包或等待调度指令的作用。两个网络分别是基于 OPS 与 OCS 的 Torus (同时使用了 Deflection, ODL 和 EB) 以及基于 OPS 的 OPSquare，顺带一提，它们在 scalability, flexibility 以及 power/cost 方面也都有不错的表现
? 由上所述，optical DCNs 的性能很大程度上受制于光交换机的性能。下面是一些比较常用，且有可能 (有些已经具备了商业化的能力甚至已经进入市场) 被用于集成的光交换机，它们的 switching time 基本都控制在 \(\it1\rm\ ns\sim\it10\rm\ \mu s\) 的范围内 [1.1]
| Switch Type | Switching Time | Scale | Loss |
|---|---|---|---|
| Mach-Zehnder interferometer (MZI, thermo-optic) | \(\sim\it10\rm\ \mu s\) | \(\it32\times32\) | High |
| micro-ring resonator (MRR, thermo-optic) | \(\sim\it10\rm\ \mu s\) | \(\it8\times8\) | Fair |
| PLZT MZI | \(\sim\it10\rm\ ns\) | \(\it8\times8\) | High |
| InP MZI | \(\sim\it2.5\rm\ ns\) | \(\it8\times8\) | High |
| LiNbO3 MZI | \(\sim\it1\rm\ ns\) | \(\it32\times32\) | High |
| MZI + electro-absorption modulator (EAM) | \(<\it10\rm\ ns\) | \(\it8\times8\) | Fair |
| tunable wavelength converters (TWCs) + arrayed waveguide grating router (AWGR) | \(\sim\it10s\rm\ ns\) | \(\it10s\times10s\) | Fair |
| tunable lasers (TLs) + AWGR | \(\sim\it10s\rm\ ns\) | \(\it100s\times100s\) | Low |
| semiconductor optical amplifier (SOA) multistage | \(<\it10\rm\ ns\) | \(\it16\times16\) | Fair |
? 稍慢一些的光交换机如基于微机电系统 (microelectromechanical system, MEMS) 的光交换机没有列在上面，这些光交换机大体可以 (依据其构造原理) 分为如下几类 [1.2]
Microelectromechanical system optical switch (基于控制微镜的运动控制，大体分为利用反射机制改变光的传播方向以及利用干涉衍射机制改变光的相位两类，前者易于进行批量制造)
特征数值 \(T=50\rm\ ms,IL=3.5\ dB\)；
Beam-steering-based optical switch (通过 2D piezoelectric actuators 将束流引导至对应的 \(\varphi,\theta\) 位置，并由 integrated position sensor 探测光束指导反馈对束流的优化，具备软件定义网络 (software-defined networking, SDN) 的特性)
Liquid crystal optical switch (利用电压控制液晶 (liquid crystal, LC) 中分子取向实现极化或折射率的变更，有些设计涉及到了双折射及 Liquid crystal on silicon (LCoS) 的技术，受限于 polarization-dependent loss (PDL) 以及较高的串扰)
Electro-optic optical switch (基于电光效应 (electro-optic effect, EO effect，外加电场改变材料折射率，具备 \(\rm ns\) 级的超快响应)，结合相位调制和干涉机制设计，采用 LiNbO3，PLZT 等材料，较高的插损限制了 scalability)
Semiconductor optical amplifier-based switch (这个原理类似于一种开关器件，有外加电流的情况下，入射光就成功引发受激辐射光放大，没有的话也就没有了出射光，之后通过 broadcast-and-select 架构将其排列为光交换机的阵列，但是批量生产时这种设计需要 \(N^2\) 个 SOA)
Thermo-optic optical switch (电流控制电极温度，进而影响材料的折射率，这样就能制造一些耦合器件作为开关使用，但是需要一些热光系数高且热导率低的材料，其优势在于不依赖于波长与偏振)
下面表格对这几类光交换机的性能给出了更加详细的评价 [1.2]
| Characteristics | MEMS based | Beam-Steering | Liquid crystal | Electro-optic | SOA based | Thermo-optic |
|---|---|---|---|---|---|---|
| Switching speed | \(\it10\sim20\rm\ ms\) | \(\it25\rm\ ms\) | \(\it100\rm\ ms\) | \(\mathbf{\sim\ ns}\) | \(\mathbf{\sim\ ns}\) | \(\it5\sim10\rm\ ms\) |
| Insertion loss | Medium | Low | High | High | Low | Low |
| Power efficiency | Medium | Low | High | High | Low | Low |
| Scalability | Large (\(\it320\times320\)) |
Large (\(\it384\times384\)) |
Medium (\(\it1\times20\)) |
Medium (\(\it32\times32\)) |
Medium (\(\it16\times16\)) |
Small (\(\it8\times8\)) |
| Reliability | Low | Low | High | High | Medium | High |
| Implementation cost | Medium | Medium | Low | High | High | Low |
? 由于当前缺少有效的光记忆器件，DC 中重要的冲突解决 (contention resolution) 功能不易实现，作为解决方案，fixed fiber delay line (FDL) 可以在时域暂存冲突包/突发，wavelength conversion 方法能够在频域将冲突转发到其它信道，deflection routing 提供在空域将冲突转发到其它端口的方案，但是它们都不可避免地引入了路由控制 (routing control) 以及包同步的问题。另一方面，未来 DCN 对于光交换机的高速切换以及一些相应的系统控制机制提出了更高的要求，当前的 optical DCNs 在 scaling 方面也受制于光交换机的端口数目，要想在这方面既避免使用层次结构，又保留不错的缓冲控制机制，或许得期待 photonic integration 的后续发展了
? 这些问题的解决方案更多来自于硬件方面如光器件的性能，但也并非不能考虑从一些调度算法 (scheduling algorithm) 的软件方面入手寻找思路，关于这一方面，可以直接转到后面的 scheduling algorithm，那里会有一些介绍性的内容，如果想看一个比较完整的算法，请移步 crossbar switches as example (●'?'●)
? 下面将重点放在了关于高速交换技术的一些基础知识，当然也涉及到了一些相关的调度算法
? 设计一个交换网络 (基于转发表 (forwarding table)，注意交换和路由是不同的，前者是对于特定网络节点而言，而后者关注大规模网络中节点间的信息传递)，需要考虑“输出冲突 (output contention)”、“出入端口连接的建立速度 (最好能够具备 self-routing 的能力)”的问题。在这里，首先我们需要一些定义来描述冲突，关于这点，有内部阻塞以及输出冲突两种类型，分别称作 blocking 和 output contention，与此同时，一些无阻塞的交换网络也是存在的，如 crossbar switch
? 在以上基础上，定义描述交换网络性能的两个物理量 throughput \(X\propto\mathbb{E}[C_{\rm input}]/\mathbb{E}[\tau_{\rm output}]\) 以及 speedup \(S=T_{\rm input}/T_{\rm forwarding}\)，更高的 speedup 说明网络具备更强的冲突化解能力，对应着更高的 throughput
? 交换架构可以分为如下几类：
Packet switches ├── Time division switching (TDS) │ ├── Shared medium │ └── Shared memory └── Space division switching (SDS) ├── Single path │ ├── Crossbar │ ├── Fully interconnected │ └── Banyan └── Multipath ├── Augmented banyan ├── Clos ├── Multiplane └── Recirculation? 其中，TDS 需要内部的通信带宽大于所有输入端口聚集的带宽，但能够轻松支持多播/广播，shared memory type 相比于 shared medium type 有更高的内存利用率但需要双倍内存速度；SDS 中，crossbar (更多信息见后面的 Crossbar Switches as Example) 是 fully interconnected type 的拓扑学等价，二者具备差不多的特性 (如 \(N^2\) 复杂度和非阻塞结构)；而 banyan-based 交换机 (包含 Delta-Omega-Banyan 这三类同构的拓扑) 中，每条信息需经 \(\log N\) 的节点以到达终点；Multipath 相比于 single path 具备了更强的容错能力，其中的 multiplane type，recirculation type 还能增大 throughput，但 recirculation 有时会导致信息的顺序错乱
? 数据缓冲策略有如下几类：
Buffering strategy ├── Shared-memory queuing ├── Output queuing (OQ) ├── Input queuing ├── Virtual output queuing (VOQ) └── Combined input and output queuing (CIOQ) .(Crosspoint queuing? place incoming cells in crosspoing buffer (XB))? 其中，shared-memory queuing structure 通过输出端对于内存的共享实现了内存的最大利用率，但面临尺寸的限制；而 OQ 在以上缺点的基础上，又失去了内存利用率的优势 ε=ε=ε=┏(゜ロ゜;)┛，在服务质量 (Quality of Service, QoS) 的控制上有了一些提高；相比于这两个， input queuing 不受限于尺寸，但带来了线段阻塞 (head-of-line blocking, HOL blocking，尽管输出端口空闲，数据却被堵在了输入队列) 的问题，这使得它的 throughput 稍低一些 (\(\it58.6\%\))；为解决 HOL blocking，VOQ 中的每个输入缓冲被分成 \(N\) 份，这个可能是当下的研究热点 (\(\it 2020\pm\))，其调度算法比前几个要复杂；CIOQ 则是另一种用于解决 HOL 的策略，它通过交换结构的 speedup 换取更高的 throughput
? 大规模 (多模块) 交换结构分为如下两种类型
Large-scale switch ├── Single-stage switch │ └── Parallel packet switch (PPS) └── Multistage switch ├── Partially connected multistage network │ └── Banyan-based switch └── Fully connected multistage network └── Clos-network switch? 其中，PPS 有最大的 throughput，其性能随 speedup 的大小而变化，但是 single-stage 难免无法支持庞大的端口数目；banyan-based network 和 Clos network 作为 multistage 则避免了上述缺陷，banyan network (\(N\times N\) network, \(\log_bN\) stages, \(b\times b\) switching elements) 也支持 self-routing，但会带来内部阻塞，交换机数目的增大将导致其性能骤减；Clos network (\(N\times N\) network, \(\it3\) stages, \(n\) input lines, \(\it m\geq2n-1\) middle-stage switch modules, maximum number of crosspoints \(N_x=O(N^{\it3/2})\)) 尽管内部全连通，但需要相应 (复杂) 的调整才可使网络具备非阻塞性质，但即便如此也无法避免内部阻塞的发生，解决方案一般只能是粗暴地增加内部连接数目和带宽了... ...
Performance Analysis
? 了解了一些基本交换结构后，下面利用一点基础的排队论知识给出 input-buffered switches, output-buffered switches 以及 completely shared-buffer switches 这三种交换策略的性能分析 [2]
? 注意，这里采用的交通源模型是上图所示的几何分布流，于是负载 \(\rho\) 就是每个时间间隔内信源处于激活状态的占比
\[\begin{equation} \begin{split} \rho=\frac{\beta=E[X]}{\beta=E[X]+\alpha=E[Y]}=\frac{\sum_{i=1}^\infty i{\rm Pr}\{X=i\}}{\sum_{i=1}^\infty i{\rm Pr}\{X=i\}+\sum_{j=1}^\infty j{\rm Pr}\{Y=j\}}=\frac{q}{q+p-pq}, \end{split} \end{equation} \]Input-Buffered Switches
? 在有 HOL blocking 存在的情形下，总是会有信息传输延迟，因而这种方案无法获得 \(\it100\%\) throughput，假若将信源定为无记忆型 (Markov)，每个端口就相当于一个 \(\it M/D/1\) 排队模型，稳态下应有每段时间内传输的信息单元数 \(\bar{F}\) 与目标为 \(i\) 端口的，每段时间后仍滞留的信息单元数 \(\bar{B}^i\) 满足如下关系
\[\begin{equation} \begin{split} \bar{F}=\sum_{i=1}^N\bar{B}^i, \end{split} \end{equation} \]? 又注意到 \(\bar{B}^i=\rho_0^2/[2(1-\rho_0)]\)，\(\rho_0\) 是归一化 throughput，可以由上式得到 \(\bar{B}^i\) 的另一种表示方式
\[\begin{equation} \begin{split} \bar{B}^i=\frac1N\sum_{i=1}^N\bar{B}^i=1-\frac{\bar{F}}{N}=1-\rho_0=\frac{\rho_0^2}{2(1-\rho_0)}, \end{split} \end{equation} \]? 由此可得 \(\rho_0=(2-\sqrt2)\approx0.586\)，这也就是 input-buffered switches 在这种信源下的渐进吞吐量了，换句话说，一旦输入速率大于这个值，系统就会饱和
? 下面借由基于上述几何分布的 \(\it Geom/G/1\) 模型考察这种调度方式的等待时间，但是需要首先接受“到达每个端口的信息单元遵循独同分布以及拥有相同概率 \(p\)”以及“每个单位有相同几率选取任意输出端口为目标”这两个假设，再借助 \(\it Geom/G/1\) 模型的结论，就可以知道平均等待时间为 (用到了服务时间 \(S\)，对于每段时间而言是一个随机变量)
\[\begin{equation} \begin{split} \overline{W}=\frac{p\overline{S(S-1)}}{2(1-p\bar{S})}+\bar{S}-1, \end{split} \end{equation} \]? 显然，它的渐进形式还是蛮可怜的，随着 \(N\to\infty\)，它也以一个很快的速率趋近于 \(\infty\) [2]
Output-Buffered Switches
? 这里 \(N\to\infty\) 将导致信息单元到达输出端口的数目遵循指数分布 \(p^ke^{-p}/k!\)，其中的 \(p\) 即为输入负载，由此可以立刻得到所谓信息单元丢失率 (若服务率/吞吐量无法满足输入负载的需求，则在输出端口的信息累积会导致溢出 output buffer 而丢失) 为 \(1-\rho_0/p\)，举个例子，对于 \(\it80\%\) 的负载，需要 buffer 大小大于 \(\it28\) 才能保证几乎无丢失
? 我们可以运用 little's law 来求得平均等待时间，也即，平均到达数 \(\bar{Q}\) 等于平均等待时间 \(\overline{W}\) 乘以服务率 \(\rho_0\)，对于 \(N\to\infty,b\to\infty\)，有
\[\begin{equation} \begin{split} \overline{W}=\frac{p}{2(1-p)}, \end{split} \end{equation} \]Completely Shared-Buffered Switches
? 这里的所有信息单元都储存在同一个 buffer 中，也就是说输入与输出共享 buffer，它的性能显然会稍高于前两种方案，但是似乎只能靠一些数值模拟的方式获知它的具体的表现，与 output-buffered switches 不同的是，其丢失率随 buffer 大小变化呈现非线性 (buffer 越大，丢失率以越大的斜率迅速减小)，而前者是呈 (近似) 线性的恒定速率减小的，也就是说这里可以使用较小的 buffer 达到
下一篇：没有了
