2. 清华大学 宇航中心, 北京 100084;
3. 清华大学 深圳研究生院, 北京 100084
2. Tsinghua Space Center, Tsinghua University, Beijing 100084, China;
3. Graduate School at Shenzhen, Tsinghua University, Beijing 100084, China
相比弯管式(bent-pipe)转发器,星载交换(onboard switching,OBS)技术能够通过一跳建立全互联的卫星网络,降低网络时延,提高网络的效率和灵活性[1, 2]。随着卫星链路速率的不断提高(如采用FSO(free space optical)技术已达数十Gb/s[3]),高速大容量的星载交换结构已成为制约OBS技术的瓶颈。另一方面,不同于地面交换结构,星载交换结构受各种空间辐射效应如单粒子翻转(single event upset,SEU)、 单粒子功能中断(single functional interrupt,SEFI)和单粒子功能栓锁(single event latch-up,SEL)等的影响[4, 5, 6]。空间辐射效应会造成交换结构中某些交叉点或交换单元处于故障状态。因此,需要研究高可靠大容量星载交换结构。
相比其他星载交换结构(如共享存储器、 crossbar和knock-out网络等[2, 7]),Clos网络的多通路特性能够提供更高的可靠性。文[8]分析了Clos网络在交叉点故障下的容错能力,但Clos网络在中间级后的路径是唯一的,且一个输入或输出仅连接一个交换单元,因此Clos网络无法抵抗输入或输出级的交换单元故障和中间级后的交叉点故障。
文[9]提出了一种FTC(fault tolerant Clos)网络,通过在每一级添加一个交换单元以保证每一级都存在多条通路,但增加的交换单元是所有端口共享的,仅能抵抗一个输入或输出交换单元故障。在实际设计中,多个Clos网络平面构成P-Clos(parallel Clos)网络以满足不断增长的端口速率和交换容量需求[10]。在P-Clos网络中增加备份平面即PS-Clos(parallel spare Clos)网络可实现故障隔离,如Juniper的T640路由器采用包含5个平面(其中包括1个备份平面)的PS-Clos网络。P-Clos和PS-Clos网络的各个平面间是相互隔离的,中间级后的路径是确定的,因此对中间级后的交叉点故障容错能力低,且备份平面的增加会造成实现成本增加。
本文提出了一种互连并行Clos(interconnected parallel Clos,IP-Clos)网络。通过在相邻平面间增加平面间连接,使得IP-Clos网络每一级都存在多条路径,提高了可靠性。通过理论分析和数值计算证明: IP-Clos网络显著提高了交换单元故障和交叉点故障下的可靠性。
1 故障模型空间辐射效应分为累积效应和单粒子效应(single event effects,SEE)。随着加工工艺不断进步,星载器件对累积效应的抵抗能力不断加强[5],但对SEE越来越敏感。SEE包括SEU、 SEFI和SEL等。
在一个交换单元(switching element,SE)内,任意输入和输出间的交换关系由相应的交叉点状态决定。不同SEE会对SE造成不同的故障影响范围和故障持续时间。以基于静态随机存取存储器(SRAM)的现场可编程逻辑阵列(FPGA)作为SE的实现器件为例,根据故障持续时间,SEE造成的故障分为以下4类:
1) 瞬时可恢复故障。当SEU发生在业务数据存储器上时,由于业务数据流会以用户数据速率更新存储器中的数据,该类故障的持续时间一般在一帧以内且不扩散,可通过数据传输的容错编码得到纠正。因此,该类故障造成的影响可忽略。
2) 长时可恢复交叉点故障。当SEU发生在配置存储器或发生在交叉点的控制寄存器时,故障会造相应的交叉点处于错误状态,从而造成输入输出间交换关系错误。该类故障可通过外部触发周期刷新寄存器状态得到纠正,但刷新频率要远低于数据速率,因此其故障影响无法忽略。
3) 长时可恢复交换单元故障。当SEFI发生时,器件整体处于非正常状态。该类故障通常需要对器件进行复位才能得以恢复,因此其持续时间更长及影响范围更大。
4) 永久交换单元故障。当SEL等永久性故障发生时,器件会因烧毁而处于永久失效状态。该类故障无法恢复,只能通过备份器件来抵抗。
通过以上分析,为保证交换的可靠性,星载交换结构应该在故障类型2、 3和4发生时依然具有很高的可靠性。为方便后续分析,本文将故障类型2定义为交叉点故障(crosspoint fault,CPF),将故障类型3和4定义为交换单元故障(switch element fault,SEF)。
2 互连并行Clos网络IP-Clos网络结构如图1所示。IP-Clos网络包括P个平面,依次编号为1到P。 每个平面的输入级包括k个输入模块(input module,IM),中间级包括m个的中间模块(central module,CM),输出级包括k个输出模块(output module,OM)。用输入和输出数量的乘积表示各模块的大小,平面1和P的IM的大小为n×2m,CM的大小为2k×2k,OM的大小为2m×n; 平面2到(P-1)的IM的大小为n×3m,CM的大小为3k×3k,OM的大小为3m×n。在同一平面内,相邻2级的交换单元通过平面内连接(inner-plane link)连接; 相邻两平面间,相邻2级的交换单元通过平面间连接(inter-plane link)连接。每个输入与P个平面的IM连接,每个输出与P个平面的OM连接,IP-Clos的尺寸为 N=nk。 为方便后续讨论,本文采用表1的符号表示。
符号 | 定义 |
IMi,p | 第p个平面的第i个IM, 1≤p≤P, 1≤i≤k |
GIMi,p | 第p个平面的第i个GIM, 1≤p≤P, 1≤i≤k |
CMr,p | 第p个平面的第r个CM, 1≤p≤P, 1≤r≤m |
OMj,p | 第p个平面的第j个OM, 1≤p≤P, 1≤j≤k |
GOMj,p | 第p个平面的第j个GOM, 1≤p≤P, 1≤j≤k |
Ii,g | IMi,p的第g个输入, 1≤g≤n |
Oj,h | OMj,p的第h个输出, 1≤h≤n |
IP-Clos网络的通路图见图2,输入Ii,g连接到P个平面的IM。 令Ii,g→Oj,h间存在的路径数为NPathIP-Clos,通过增加平面间链路,可得
$\begin{array}{l} {\rm{NPat}}{{\rm{h}}_{{\rm{IP - Clos}}}} = \left( {P - 2} \right) \times 3m + 2 \times 2m = \\ \left( {3P - 2} \right)m \end{array}$ | (1) |
当无平面间链路时,IP-Clos变为P-Clos,Ii,g→Oj,h间存在的路径数NPathP-Clos为
${\rm{NPat}}{{\rm{h}}_{{\rm{IP - Clos}}}} = Pm$ | (2) |
比较式(1)和(2)可得,当P > 1时,IP-Clos网络能够提供更多的路径,且每一级都存在多条通路。
3 可靠性及实现复杂度分析定义非阻塞交换结构的可靠性为故障条件下交换结构不阻塞的概率。不失一般性,对网络中的故障作如下假设:
1) 网络中同一类故障以相同的概率独立发生。
2) 不同类的故障发生是相互独立的。
3) 一个交叉点的可靠性为rCP=exp(-λCPt),λCP为交叉点的故障率; 一个交换单元的可靠性为rSE=exp(-λSEt),λSE为交换单元的故障率。
为分析IP-Clos网络的可靠性,将连接到同一CM的IM定义为一个广义输入单元(generalized input module,GIM),将连接到同一CM的OM定义为一个广义输出单元(generalized output module,GOM)。具体的,有
$\left\{ {{\rm{I}}{{\rm{M}}_{i,p'}}|\max \left( {1,p - 1} \right) \le p' \le \min \left( {p + 1,P} \right)} \right\}$ | (3) |
$\begin{array}{l} {\rm{GO}}{{\rm{M}}_{i,p}} = \\ \left\{ {{\rm{O}}{{\rm{M}}_{i,p'}}|\max \left( {1,p - 1} \right) \le p' \le \min \left( {p + 1,P} \right)} \right\} \end{array}$ | (4) |
GIMi,p、 CMr,p和GOMj,p构成第p个广义Clos(generalized Clos,G-Clos)网络平面。IP-Clos网络等效为P个G-Clos网络平面构成的多平面网络。通过等效,可利用Clos网络可靠性的结论分析G-Clos,进而分析IP-Clos网络的可靠性。
3.1 交叉点故障下的可靠性分析在第p个G-Clos网络平面中,GIM中连接相同输入和相同CM的交叉点构成一个广义输入交叉点(generalized input crosspoint,GICP); CM中连接相同GIM和相同GOM的交叉点构成一个广义中间交叉点(generalized central crosspoint,GCCP); GOM中连接相同CM和相同输出的交叉点构成一个广义输出交叉点(generalized output crosspoint,GOCP)。当且仅当1个广义交叉点包含至少1个可靠交叉点时,该广义交叉点是可靠的。具体的,一个GICP、 GCCP和GOCP的可靠性分别为
$\begin{array}{l} {r_{{\rm{GICP}}}}\left( p \right) = 1 - {\left( {1 - {r_{{\rm{CP}}}}} \right)^{\left| {GICP\left( p \right)} \right|}},\\ {r_{{\rm{GCCP}}}}\left( p \right) = 1 - {\left( {1 - {r_{{\rm{CP}}}}} \right)^{\left| {GCCP\left( p \right)} \right|}},\\ {r_{{\rm{GOCP}}}}\left( p \right) = 1 - {\left( {1 - {r_{{\rm{CP}}}}} \right)^{\left| {GOCP\left( p \right)} \right|}}. \end{array}$
其中:
$\begin{array}{l} \left| {{\rm{GICP}}\left( p \right)} \right| = \left| {{\rm{GOCP}}\left( p \right)} \right| = \left\{ \begin{array}{l} 3,\;\;1 < p < p;\\ 2,\;\;其他. \end{array} \right.\\ \left| {{\rm{GCCP}}\left( p \right)} \right| = \left\{ \begin{array}{l} 9,\;\;1 < p < P;\\ 4,\;\;其他 \end{array} \right. \end{array}$
应用文[8]得到的Clos网络对交叉点故障的容错结论,得到一个N×N的G-Clos网络能够容忍不超过(m-1)个广义输入或输出交叉点故障,或不超过(m-n)个广义中间交叉点故障。
令NGICP(p)、 NGCCP(p)和NGOCP(p)分别表示第p个G-Clos网络的广义输入、中间和输出交叉点故障个数,则第p个G-Clos网络在CPF下的可靠性上下界分别为
$\begin{array}{l} {R_{{\rm{G - Clos - CPF - upper}}}}\left( p \right) = \Pr \left\{ {\left[{{N_{{\rm{GICP}}}}\left( p \right) + {N_{{\rm{GOCP}}}}\left( p \right)} \right]} \right. \le \\ m - 1{\rm{OR}}{N_{{\rm{GCCP}}}}\left( p \right) \le \left. {m - n} \right\} = {R_1}\left( p \right){R_2}\left( p \right),\\ {R_{{\rm{G - Clos - CPF - lower}}}}\left( p \right) = \Pr \left\{ {\left[{{N_{{\rm{GICP}}}}\left( p \right) + {N_{{\rm{GOCP}}}}\left( p \right)} \right]} \right. \le \\ m - 1,{N_{{\rm{GCCP}}}}\left( p \right) \le \left. {m - n} \right\} = \\ {R_3}\left( p \right) + {R_4}\left( p \right) - {R_5}\left( p \right) \end{array}$
其中:
$\begin{array}{l} {R_1}\left( p \right) = \Pr \left\{ {\left[{{N_{{\rm{GICP}}}}\left( p \right) + {N_{{\rm{GOCP}}}}\left( p \right)} \right]} \right. \le m - \left. 1 \right\} = \\ \sum\limits_{i = 0}^{m - 1} {\sum\limits_{l = 0}^i {\left( \begin{array}{l} nmk\\ l \end{array} \right)} } {\left[{1 - {r_{_{{\rm{GICP}}}}}\left( p \right)} \right]^l}{\left[{{r_{_{{\rm{GICP}}}}}\left( p \right)} \right]^{nmk - l}} \cdot \\ \left( \begin{array}{l} nmk\\ i - 1 \end{array} \right){\left[{1 - {r_{_{{\rm{GOCP}}}}}\left( p \right)} \right]^{i - l}}{\left[{{r_{_{{\rm{GOCP}}}}}\left( p \right)} \right]^{nmk - i + l}},\\ {R_2}\left( p \right) = \Pr \left\{ {{N_{{\rm{GCCP}}}}\left( p \right)} \right. \le m - \left. N \right\} = \\ \sum\limits_{i = 0}^{m - 1} {\left( \begin{array}{l} m{k^2}\\ i \end{array} \right)} {\left[{1 - {r_{_{{\rm{GCCP}}}}}\left( p \right)} \right]^i}{\left[{{r_{_{{\rm{GCCP}}}}}\left( p \right)} \right]^{m{k^2} - i}},\\ {R_3}\left( p \right) = \Pr \left\{ {\left[{{N_{{\rm{GICP}}}}\left( p \right) + {N_{{\rm{GOCP}}}}\left( p \right)} \right]} \right. \le m - 1,\\ {N_{{\rm{GCCP}}}}\left( p \right) = \left. {\left. 0 \right]} \right\} = {R_1}\left( p \right){\left[{{r_{_{{\rm{GCCP}}}}}\left( p \right)} \right]^{m{k^2}}},\\ {R_4}\left( p \right) = \Pr \left\{ {{N_{{\rm{GICP}}}}\left( p \right)} \right. = {N_{{\rm{GOCP}}}}\left( p \right) = 0,\\ {N_{{\rm{GCCP}}}}\left( p \right) \le m - \left. n \right\} = \\ {R_2}\left( p \right){\left[{{r_{_{{\rm{GICP}}}}}\left( p \right){r_{_{{\rm{GOCP}}}}}\left( p \right)} \right]^{nmk}},\\ {R_5}\left( p \right) = \\ \Pr \left\{ {{N_{{\rm{GICP}}}}\left( p \right)} \right. = {N_{{\rm{GOCP}}}}\left( p \right) = {N_{{\rm{GCCP}}}}\left( p \right) = \left. 0 \right\} = \\ {\left[{{r_{_{{\rm{GICP}}}}}\left( p \right){r_{_{{\rm{GOCP}}}}}\left( p \right)} \right]^{nmk}}{\left[{{r_{_{{\rm{GCCP}}}}}\left( p \right)} \right]^{m{k^2}}}. \end{array}$
则CPF下IP-Clos网络的可靠性上下界分别为
$\begin{array}{l} {R_{{\rm{G - Clos - CPF - upper}}}} = \prod\limits_{1 \le p \le P} {{R_{{\rm{G - Clos - CPF - upper}}}}\left( p \right)} ,\\ {R_{{\rm{IP - Clos - CPF - lower}}}} = \prod\limits_{1 \le p \le P} {{R_{{\rm{IP - Clos - CPF - lower}}}}\left( p \right)} \end{array}$
当 $\left( {1 - {r_{{\rm{CP}}}}} \right) \ll {r_{{\rm{CP}}}}$ 时,RG-Clos-CPF-upper(p)和RG-Clos-CPF-lower(p)为广义交叉点可靠性的单调增函数。当不采用平面间连接时,G-Clos变为Clos,即|GICP(p)|=|GCCP(p)|=|GOCP(p)|=1。由于rCP < 1,则
$\begin{array}{l} {R_{{\rm{G - Clos - CPF - upper}}}}\left( p \right) > {R_{{\rm{Clos - CPF - upper}}}},\\ {R_{{\rm{G - Clos - CPF - lower}}}}\left( p \right) > {R_{{\rm{Clos - CPF - lower}}}},\\ {R_{{\rm{IP - Clos - CPF - upper}}}}\left( p \right) > {R_{{\rm{P - Clos - CPF - upper}}}},\\ {R_{{\rm{IP - Clos - CPF - lower}}}}\left( p \right) > {R_{{\rm{P - Clos - CPF - lower}}}}. \end{array}$
其中RClos-CPF-upper、 RClos-CPF-lower、 RP-Clos-CPF-upper和RP-Clos-CPF-lower分别为Clos和P-Clos网络在CPF下的可靠性的上下界。
3.2 交换单元故障下的可靠性分析在第p个G-Clos网络平面中,当且仅当1个广义交换单元包含1个可靠交换单元时该广义交换单元是可靠的。根据式(3)和(4)可得,1个GIM和GOM的可靠性分别为
$\begin{array}{l} {r_{{\rm{GIM}}}}\left( p \right) = 1 - {\left( {1 - {r_{{\rm{SE}}}}} \right)^{\left| {GIM\left( p \right)} \right|}},\\ {r_{{\rm{GOM}}}}\left( p \right) = 1 - {\left( {1 - {r_{{\rm{SE}}}}} \right)^{\left| {GOM\left( p \right)} \right|}}. \end{array}$
其中,
$\left| {{\rm{GIM}}\left( p \right)} \right| = \left| {{\rm{GOM}}\left( p \right)} \right| - \left\{ \begin{array}{l} 3,\;\;1 < p < P;\\ 2,\;\;其他. \end{array} \right.$
类似于Clos网络,一个N×N的G-Clos网络不阻塞的充要条件是m≥n[11]。令NGIM(p)、NGCM(p)和NGOM(p)分别表示第p个G-Clos网络的广义输入、中间和输出交换单元故障个数,则第p个G-Clos网络在SEF下的可靠性RG-Clos-SEF(p)为
$\begin{array}{l} {R_{{\rm{G - Clos - SEF}}}}\left( p \right) = \\ \Pr \left\{ {{N_{{\rm{GIM}}}}\left( p \right)} \right. = {N_{{\rm{GOM}}}}\left( p \right) = 0,\\ {N_{{\rm{GCM}}}}\left( p \right) \le m - \left. n \right\} = \\ \left[{{r_{{\rm{GIM}}}}\left( p \right){r_{{\rm{GOM}}}}\left( p \right)} \right]k\left( {\sum\limits_{i = 0}^{m - n} {\left( \begin{array}{l} m\\ i \end{array} \right)} r_{SE}^{\left( {m - i} \right)}{{\left( {1 - {r_{SE}}} \right)}^i}} \right) \end{array}$
则SEF下的IP-Clos网络的可靠性RIP-Clos-SEF为
${R_{{\rm{IP - Clos - SEF}}}} = \prod\limits_{1 \le p \le P} {{R_{{\rm{G - Clos - SEF}}}}\left( p \right)} .$
当不采用平面间连接时,|GIM(p)|=|GIM(p)|=1。 由于rSE < 1,则RG-Clos-SEF(p) > RClos-SEF,RIP-Clos-SEF > RP-Clos-SEF,其中RClos-SEF和RP-Clos-SEF分别为Clos和P-Clos网络在SEF下的可靠性。
3.3 实现复杂度分析本文采用SE数量和连接数量来衡量星载交换结构的实现复杂度。当SE采用相同的芯片实现时,SE数量和SE间连接数量决定了所需的芯片数量和电路板的复杂度。
IP-Clos网络的SE数量NSEIP-Clos和SE间连接数量NLinkIP-Clos分别为
$NS{F_{{\rm{IP - Clos}}}} = \left( {2k + m} \right)P = {\rm{NS}}{{\rm{E}}_{{\rm{P - Clos}}}}$ | (5) |
$\begin{array}{l} NLin{k_{{\rm{IP - Clos}}}} = 2P\left( {N + mk} \right) + 4mk\left( {P - 1} \right) = \\ NLin{k_{{\rm{P - Clos}}}} + 4mk\left( {P - 1} \right) \end{array}$ | (6) |
其中NSEP-Clos和NLinkP-Clos分别为P-Clos网络的SE数量和SE间连接数量。通过式(5)和(6)可知,平面间连接增加了IP-Clos网络需要的连接数量。
4 数值结果本节比较IP-Clos、 P-Clos和PS-Clos在CPF和SEF的可靠性、平均失效时间(mean time to failure,MTTF)和实现复杂度。其中,交换网络NET在故障F下的MTTF为MTTFNET-F=∫RNET-F(t)dt,RNET-F(t)为网络NET在故障F下的可靠性。令 n=k=4,P=4,备份平面数S=1,假设交换结构采用宇航级FPGA Virtex-4QV实现,数值分析中分别以Virtex-4QV在GEO下的SEU和SEFI的发生率分别作为CPF和SEF的故障率[5],即λCP=7.61×10-7, λSE=2.66×10-5。
图3为CPF下IP-Clos网络的可靠性。可以看出,在分析时间内,IP-Clos网络具有最高的可靠性,且RIP-Clos-CPF-upper和RIP-Clos-CPF-upper在不同m下基本重合且接近于1。当m=n+2时,不同网络的MTTF分别满足MTTFIP-Clos-CPF>2.1×105 d,MTTFP-Clos-CPF<1.73×104 d,MTTFPS-Clos-CPF<2.3×104 d。比较可得,在CPF情况下,IP-Clos网络的MTTF是其他网络的10倍。
图4为SEF下IP-Clos网络的可靠性。可以看出,在分析时间内,IP-Clos网络具有最高的可靠性。随m的增加,RIP-Clos-SEF增加明显,但RPS-Clos-SEF和RP-Clos-SEF增加不明显。当m=n+2时,不同网络的MTTF为MTTFIP-Clos-SEF=6.86×103 d,MTTFP-Clos-SEF= 1.16×103 d,MTTFPS-Clos-SEF=2.08×103 d。比较可得,在SEF情况下,IP-Clos网络的MTTF是P-Clos的5.9倍,PS-Clos的3.6倍。
图5为不同网络的实现复杂度。可以看出,P-Clos网络具有最低的实现复杂度。IP-Clos网络仅在连接数量上有所增加,交换单元数量并没有增加。PS-Clos网络在连接数量和交换单元数量2方面都有所增加。
5 结 论本文提出了一种IP-Clos网络以抵抗空间辐射环境对星载交换结构造成的交叉点故障和交换单元故障。 IP-Clos通过在相邻平面间增加平面间互连,增加了任意输入—输出间的路径数量,且使得每一级都存在多条路径到达下一级。理论分析得到了IP-Clos网络在交叉点故障和交换单元故障下具有比P-Clos更高的可靠性。数值分析表明,在采用相同器件前提下,IP-Clos网络在交叉点故障下的平均失效时间是P-Clos网络和PS-Clos网络的10倍,在交换单元故障下的平均失效时间比P-Clos网络和PS-Clos网络的提高了4.9和2.6倍。
[1] | Farserotu J, Prasad R. A survey of future broadband multimedia satellite systems, issues and trends [J]. IEEE Communications Magazine, 2000, 38(6): 128-133. |
[2] | Courville N, Bischi H, Zeng J. Critical issues of onboard switching in DVB-S/RCS broadband satellite networks [J]. IEEE Wireless Communications, 2005, 12(5): 28-36. |
[3] | Koishi Y, Suzuki Y, Takahashi T, et al. Research and development of 40Gbps optical free space communication from satellite/airplane [C]// 2011 International Conference on Space Optical Systems and Applications (ICSOS). Santa Monica, CA, USA: IEEE Press, 2011: 88-92. |
[4] | Maurer R H, Fraeman M E, Martin M N, et al. Harsh environments space radiation environment effects and mitigation [J]. Johns Hopkins APL Technical Digest, 2008, 28(1): 17-29. |
[5] | Allen G, Swift G, Carmichael C. Virtex-4 VQ static SEU characterization summary [R/OL].[2005-01-15]. http:// ntrs.nasa.gov/search.jsp?R=20080018455. |
[6] | Wirthlin M J. FPGAs operating in a radiation environment: Lessons learned from FPGAs in space [J]. Journal of Instrumentation, 2013, 8(2), C02020. |
[7] | Gilderson J, Cherkaoui J. Onboard switching for ATM via satellite [J]. IEEE Communications Magazine, 1997, 35(7): 66-70. |
[8] | Yang Y, Wang J. A fault-tolerant rearrangeable permutation network [J]. IEEE Transactions on Computers, 2004, 53(4): 414-426. |
[9] | Du D, Hung Q. Switching Networks: Recent Advances [M]. Berlin, Germany: Springer, 2001. |
[10] | Chao H J, Park J, Artan S, et al. Trueway: a highly scalable multi-plane multi-stage buffered packet switch [C]// 2005 Workshop on High Performance Switching and Routing. Hongkong, China: IEEE Press, 2005: 246-253. |
[11] | Benes V E. On rearrangeable three-stage connecting networks [J]. The Bell System Technical Journal, 1962, 41(5): 1481-1492. |