A Fault-Tolerant Unicast Routing Algorithm for a Class of Recursive Data Center Networks

YI Wenwen; ZHANG Shukui; WANG Xi; LI Wenjun

doi:10.13718/j.cnki.xdzk.2021.09.020

The data center network is the main infrastructure supporting applications such as cloud services, supercomputing and social networks. The traditional tree-based data center network has some shortcomings, such as insufficient scalability and low fault tolerance. Based on completed graphs, this paper presents a kind of recursive data center network(RDCN). Compared with the traditional tree data center network, RDCN has better network bandwidth and fault-tolerant performance. It is proved that when k≥1, n≥3 and σ∈{1, n-1}, the restricted connectivity of RDCN is 2kσ+n-2, which is almost twice the RDCN's traditional connectivity. We present an improved fault-tolerant unicastrouting algorithm(XFRouting) and prove thatthe time complexity of XFRouting is O(⌈log|F|⌉k³), and furthermoreprove the maximal length of the path constructedby the algorithm in the worst case. Finally, a simulation experiment based on our algorithm is carried out, and the results show that the algorithm is better than the breadth first search algorithm and the depth first search algorithm.

HTML

近年来，随着云计算和大数据应用的飞速发展，数据中心网络(Data Center Network)作为其基础设施和下一代网络技术的创新平台，得到了学术界和工业界的广泛关注^[1-3].

数据中心网络的容错性是评估网络性能的重要因素. 连通度是度量数据中心网络容错性的一个重要参数，连通度越大，则数据中心网络的容错性能就相对越高. 数据中心网络连通度定义中，发生故障的服务器是任意的、没有限制条件的，然而实际情况往往并非如此. 仅使用连通度来评估数据中心网络的容错性，会严重低估数据中心网络的容错性能. 因此，涌现了大量在特定网络拓扑上的限制连通度问题的研究成果^[3-12].

传统的树型数据中心网络存在可扩展性不足和容错性较差等缺点，因此研究者们提出了DCell，BCube等多种递归型数据中心网络，与树型数据中心网络不同，这些结构采用递归方式构建网络拓扑，理论上可以支持百万台服务器的规模^[13-14]，且它们避免了核心层交换机带来的性能瓶颈，并使服务器之间拥有多条可用的不相交路径，其在可扩展性、容错性等多方面都有较好表现. 本文提出了一类递归型数据中心网络——RDCN，与传统树形数据中心网络相比，该网络具有更好的网络带宽和网络容错性能；研究了递归型数据中心网络的限制连通度，该结果能够更加精确地度量该网络的容错性. 本文将讨论RDCN在限制故障顶点集情形下的限制连通度，并设计和分析了相应的容错单播算法.

1. 预备知识

数据中心网络可以表示为一个简单图G=(V(G)，E(G))，其中V(G)表示顶点集，E(G)表示边集. 顶点和边分别表示数据中心网络中的服务器和连接服务器的链路，而交换机被认为是透明的网络设备^[13]. 给定图G中任意两个顶点u和v，若(u，v)∈E(G)，则u和v是邻居. 顶点u在图G的邻居集合可表示为N(G，u)={v|(u，v)∈E(G)}. 图G的连通度可表示为κ(G).

图G中两个顶点u和v之间的路径P可表示为一个顶点的序列P=(u₀=u，u₁，…，u_k=v)，P中除了u和v以外的任意两个点都是不同的. 从u_i到u_j的子路径可用Path(P，u_i，u_j)表示，其中0≤i＜j≤k. P[-1]=u_k，P^-1可表示为路径P的反转. P中所有顶点(边)的集合可表示为V(P)(E(P)). 如果V'⊆V(G)，那么G[V']表示由图G的顶点所导出的子图. 使用G-V来表示G[V(G)-V]. 对于任意的顶点v∈V(G)，如果(u，v)∈E(G)，则表示u是v的一个邻居. 定义N(G，V')={x∈V(G)|存在顶点y∈V'满足(x，y)∈E(G)}. 顶点v的邻居集合Γ(G，v)={u∈V(G)|(v，u)∈E(G)}表示v的所有相邻顶点.

进一步，对于顶点集合V'⊆V(G)，定义V'的邻居集合为Γ(G，V')=∪_x∈V'Γ(G，x)/V'. 明显地，Γ(G，V')=N(G，V')/V'.

定义1  给定图G，令F⊂V(G)表示G中一个故障顶点集合，如果u∈F，那么u是G中一个故障顶点；否则，u是G中一个无故障顶点. 若G中每个顶点至少有一个无故障邻居，则基于该条件下G的限制连通度可表示为κ'(G). 另外，基于故障顶点无限制的G的连通度可表示为κ(G).

对于任意整数n≥3和k≥1，部署于n-口交换机上的k-维递归完全图网络可以表示为一个图X_k，n. X_k，n的基图是一个有n个顶点的完全图，t_k，n表示X_k，n的顶点个数，e(u，v)表示顶点u到顶点v的边，σ表示图中任意顶点与同维度其他子图相连接的边数，其中σ∈{1，n-1}，s表示X_k，n中子图的个数. X_k，n的顶点u表示为[u_k，u_k-1，…，u_i，…，u₀]，其中0≤u₀≤n-1，0≤u_i≤s_i且i≥1，可用(u)_i表示u中的第i个元素u_i.

定义2  当k≥0，n≥3且σ∈{1，n-1}时，X_k，n的递归定义如下：

(1) 当k=0时，X_k，n是一个具有n个顶点的完全图.

(2) 当k≥1时，X_k，n是由s个互不相交的子图X_k-1，n¹，X_k-1，n²，…，X_k-1，n^s相互连接而成的(n+kσ-1)-正则图，其中当σ=1时，s=t_k-1，n+1；当σ=n-1时，s=n.

(2.1)当σ=1时，X_k-1，n^u_k中顶点u=[u_k，u_k-1，…，u₀]与X_k-1，n^v_k中v=[v_k，v_k-1，…，v₀]是相邻的当且仅当${u_k} = {v_0} + \sum\limits_{j = 1}^{k - 1} {({v_j}{t_{j - 1, n}})} $且${v_k} = {u_0} + \sum\limits_{j = 1}^{k - 1} {({u_j}{t_{j - 1, n}}) + 1} $.

(2.2)当σ=n-1时，X_k-1，n^u_k中顶点u=[u_k，u_k-1，…，u₀]与X_k-1，n^v_k中v=[v_k，v_k-1，…，v₀]是相邻的当且仅当u_k≠v_k且u_i=v_i(i=0，…，k-1).

根据文献[13]和文献[14]，可得出X_k，n网络的基本性质如下.

定理1  X_k，n是一个(n+kσ-1)-正则图.

定理2  κ(X_k，n)=λ(X_k，n)=n+kσ-1.

定理3  $ {t_{k, n}} = \left\{ {\begin{array}{*{20}{l}} {{t_{k - 1, n}}({t_{k - 1, n}} + 1) \ge {{\left( {n + \frac{1}{2}} \right)}^{{2^k}}} - \frac{1}{2}}&{若 \sigma = 1, }\\ {n{t_{k - 1, n}} = {n^{k + 1}}}&{若 \sigma = n - 1} \end{array}} \right.. $

本文将RDCN与几种典型的数据中心网络进行对比(如表 1所示)，其中N表示服务器数量，n表示交换机端口数量，比较的指标包括：顶点的度、连通度和网络直径. 其中数据中心网络中顶点的度越小则表示其顶点间网络连接越少，从而构建网络的成本越低；数据中心网络的连通度越高，则表示其具有更好的容错性；数据中心网络的直径越小则表示它的实时响应路由所花费的时间越少.

与RDCN相比，Tree和Fat-Tree的扩展规模在理论上受限于核心交换机的端口数目，不利于数据中心网络规模的快速扩张，且它们的容错性受到核心交换设备影响较大，对核心交换设备的故障非常敏感. 同时，Tree和Fat-Tree的拓扑结构的特点决定了其不能很好支持一对多、广播和全交换等网络通信模式. 另外，与RDCN相比，FiConn网络的容错性较差，网络直径较大. 因此与上述数据中心网络相比，RDCN具有较高的网络带宽、较好的容错性. 特别的，σ=n-1时的RDCN比σ=1时的RDCN具有更高的网络带宽和容错性能.

2. 递归型数据中心网络的限制连通度

本文用F表示故障顶点集合，令I_0，n={0，1，…，n-1}且I_j，n={0，1，…，s}(1≤j≤k). 若σ=1时，s=t_k-1，n+1；若σ=n-1时，s=n. 对于任意整数i∈I_k，n，令F_i=F∩V(X_k-1，nⁱ)且f_i=|F_i|. 令I={i∈I_k，n|f_i≥n+kσ-2}，I=I_k，n\I，F_I=∪_i∈IF_i，F_I=∪_i∈IF_i，X_k-1，n^I=X_k，n[∪_i∈IV(X_k-1，nⁱ)].

对于任意的整数1≤l≤k，令V_k，n^l={[u_k，u_k-1，…，u_l]|u_i∈I_i，n且l≤i≤k}. 对于任意的α∈V_k，n^l，我们用X_l-1，n^α表示X_l-1，n中每个顶点标号前添加α作为前缀后生成的图. 显然X_l-1，n$ \cong $X_l-1，n^α.

根据定义2，可以证明下述引理成立.

引理1  对于任意两个整数i，j∈I_k，n且i≠j，X_k，n中的子图X_k-1，nⁱ和X_k-1，n^j存在h条不相交的连接路径，表示为集合P(X_k-1，nⁱ，X_k-1，n^j)，其中当σ=1时h=t_k-1，n，当σ=n-1时h=(n-1)t_k-1，n.

证  对于任意的r∈I_k，n{i，j}，令e(X_k-1，nⁱ，X_k-1，n^j)表示子图X_k-1，nⁱ到子图X_k-1，n^j的一条边，令(u_r，x_r)=e(X_k-1，nⁱ，X_k-1，n^r)且(y_r，v_r)=e(X_k-1，n^r，X_k-1，n^j). 因为X_k-1，n^r是连通的，所以x_r到y_r存在一条路径Q_r. 令P_i=e(X_k-1，nⁱ，X_k-1，n^j)，当r∈I_k，n且r≠j时，可以验证P₀，P₁，…，P_r，…，P_s是连接X_k-1，nⁱ和X_k-1，n^j的h条不交路径，当σ=1时，h=t_k-1，n，当σ=n-1时，h=(n-1)t_k-1，n.

引理2  令F表示X_k，n上所有故障顶点的集合. 存在任意整数k≥1，n≥3且σ∈{1，n-1}，若|F|≤2(kσ-1)+n，则X_k-1，n^I-F是连通的.

证  首先证明|I|≤2. 假设|I|≥3，根据前面给出的I的定义，则有|F|≥3(n+kσ-2)≥2(kσ-1)+n+1＞2(kσ-1)+n，矛盾. 此外，对于任意整数i∈I，由于κ(X_k-1，nⁱ)=n+k-2且f_i≤n+k-3，故X_k-1，nⁱ-F_i是连通的.

接下来证明X_k-1，n^I-F_I是连通的. 对于任意两个不同整数i，j∈I，任意的整数k≥1，n≥3且σ∈{1，n-1}，根据引理1和定理3可以得出

因此，对于任意两个不相等的整数i，j∈I，X_k-1，n^I-F_I上至少存在一条路径Q连接X_k-1，nⁱ和X_k-1，n^j，其中Q∈P(X_k-1，nⁱ，X_k-1，n^j)，故X_k-1，n^I-F_I是连通的.

引理3^[15]  对于任意的整数k≥1，n≥3且σ∈{1，n-1}，X_k，n上存在长度为3的圈.

引理4^[15]  对于任意的整数k≥1，n≥3，σ∈{1，n-1}，X_k，n中存在相邻的两个顶点u=u_ku_k-1…u₀和v=v_kv_k-1…v₀，边(u，v)∈E(X_k，n)，令leftIdx(u，v)表示为u和v从左侧开始最先不同的下标，则有

引理5  对于任意的整数k≥1，n≥3且σ∈{1，n-1}，网络中的故障顶点集合F⊂V(X_k，n)且|F|≤2kσ+n-3，若X_k，n中每个无故障顶点都至少存在一个无故障邻居，则X_k，n-F是连通的.

证  要证明上述情况成立需要证明下述断言成立.

断言. 对于任意两个不同的顶点u，v∈V(X_k，n-F)，在X_k，n-F中存在一条连接u和v的路径.

当k=1时，该断言显然成立.

令α=(u)_k，β=(v)_k，当k＞1时，可以分两种情形讨论.

情形1  α=β. 令G₀=X_k-1，n^α-F_α且G₁=X_k，n-V(X_k-1，n^α)-(F/F_α)，则：

1) 若f_α≤n+kσ-3，则G₀是连通的，因此G₀中存在u和v的路径连接；

2) 若f_α≥n+kσ-2，且u，v在同一个连通分支，则G₀中存在u和v的连接路径；

3) 若f_α≥n+kσ-2，且u，v不在同一个连通分支，假定x是u的一个无故障邻居顶点，y是v的一个无故障邻居顶点. 令γ=(x)_k且δ=(y)_k，接下来可以分为以下3种子情形.

情形1.1  α≠δ且α≠γ. 对于任意整数i∈I_k，n{α}，有f_i≤|F|-f_α≤(2kσ+n-3)-(n+kσ-2)=kσ-1≤n+kσ-3. 根据引理2，G₁是连通的，G₁中存在路径Q连接x和y. 因此X_k，n-F中存在路径(u，x，Q，y，v)连接u和v.

情形1.2  α≠δ且α=γ. 令u₁，u₂，…，u_n+kσ-4，u_n+kσ-3分别表示u在X_k-1，n^α中的除x外的n+kσ-3个邻居，令x₁，x₂，…，x_n+kσ-4，x_n+kσ-3分别表示x在X_k-1，n^α中的除u外的n+kσ-3个邻居，令u'₁，u'₂，…，u'_n+kσ-3，u'_n+kσ-2分别表示u₁，u₂，…，u_n+kσ-4，u_n+kσ-3，x在X_k，n-V(X_k-1，n^α)中的n+kσ-2个邻居，令x'₁，x'₂，…，x'_n+kσ-3，x'_n+kσ-2分别表示x₁，x₂，…，x_n+kσ-4，x_n+kσ-3，u在X_k，n-V(X_k-1，n^α)中的n+kσ-2个邻居，其中σ∈{1，n-1}. 根据引理3和引理4有

令

对c'求导则有

显然有min(c')=n+2kσ-2. 不失一般性，假设x₁=u₁，x₂=u₂，…，x_c=u_c，则有{u_c+1，u_c+2，…，u_n+kσ-3}∩{x_c+1，x_c+2，…，x_n+kσ-3}=Ø.

根据定义2有{u'_c+1，u'_c+2，…，u'_n+kσ-3}∩{x'_c+1，x'_c+2，…，x'_n+kσ-3}=Ø.

因此，从X_k-1，n^α到X_k，n-V(X_k-1，n^α)可得c'条不交路：Q₁=(u，u₁，u'₁)，Q₂=(u，u₂，u'₂)，…=…，Q_n+kσ-3=(u，u_n+kσ-3，u'_n+kσ-3)，Q_n+kσ-2=(u，x，u'_n+kσ-2)，Q_n+kσ-1=(u，x，x_c+1，x'_c+1)，Q_n+kσ=(u，x，x_c+2，x'_c+2)，…，Q_c'-1=(u，x，x_n+kσ-3，x'_n+kσ-3)，Q_c'=(u，x'_n+kσ-2).

因为|F|≤2kσ+n-3＜c'，所以c'条不相交的路径Q₁，Q₂，…，Q_c'中至少存在一条路径Q_r满足条件，其中1≤r≤c'. 令c″=n+kσ-2-(c'-r)=n+kσ-2-c'+r，则有

和

根据情形1.1中讨论，G₁中存在一条路径P连接z和y. 因此，X_k，n-F中存在一条路径(Q，P，v)连接u和v.

情形1.3  α=δ. 证明与情形1.2类似，不再赘述.

情形2  α≠β. 不失一般性，假设f_α≤f_β，则有$ {f_\alpha } \le \frac{{\left| F \right|}}{2} \le \frac{{2k\sigma + n - 3}}{2} \le n + k\sigma - 2 $.

若f_α=n+kσ-2则f_β≤|F|-f_α≤(2kσ+n-3)-(kσ+n-2)=kσ-1≤n+kσ-3，与f_α≤f_β矛盾. 因此f_α≤n+kσ-3. 接下来，分以下两种情形讨论.

情形2.1  f_β≤n+kσ-3，f_α，f_β∈I. 根据引理2，X_k-1，n^I-F是连通的. 从而X_k-1，n^I-F中存在一条路径连接u和v.

情形2.2  f_β≥n+kσ-2. 令G₀=X_k-1，n^β-F_β，G₁=X_k，n-V(X_k-1，n^β)-(F\F_β). 类似于情形1.2中的证明，X_k，n-F中存在一条路径P连接v和x，其中x∈V(G₁). 我们有f_i≤|F|-f_β≤(2kσ+n-3)-(kσ+n-2)≤n+kσ-3. 其中i∈I_k，n\{β}.

根据引理2，可得G₁是连通的，故G₁中存在一条路径Q连接u和x. 从而路径(Q，P^-1)是X_k，n-F中连接u和v的一条路径.

综上所述，对于任意的u，v∈V(X_k，n-F)且u≠v，X_k，n-F中存在一条连接u和v的路径，因此X_k，n-F是连通的，证毕.

定理4  对于任意整数k≥1，n≥3且σ∈{1，n-1}，κ'(X_k，n)=2κ(X_k，n)-n=2kσ+n-2κ'(X_k，n)=2κ(X_k，n)-n=2kσ+n-2.

证  通过引理5可得κ'(X_k，n)≥2kσ+n-2κ'(X_k，n)≥2kσ+n-2. 下面将证明κ'(X_k，n)≤2kσ+n-2成立.

对于任意的整数k≥1，n≥3且σ∈{1，n-1}，如果X_k，n中每个顶点都至少有一个无故障邻居，则存在一条边(u，v)∈E(X_k，n)，使得|Γ(X_k，n，{u，v})|=2kσ+n-2且X_k，n-Γ(X_k，n，{u，v})有且仅有两个连通分支：其中一个连通分支为X_k，n[{u，v}]，另外一个连通分支为X_k，n-N(X_k，n[{u，v}]).

首先证明当n=3，k=1时该结论成立. 当n=3，k=1时，分为两种情况：σ=1或σ=n-1.

当n=3，k=1，σ=1时，选择一条边(00，01)，令故障集合为Γ(X_1，3，{00，01})={02，10，20}. 明显的|Γ(X_1，3，{00，01})|=3=2×1×1+3-2. 容易验证X_1，3-Γ(X_1，3，{00，01})有且仅有两个连通分支：其中一个连通分支为X_1，3[{00，01}]，另外一个连通分支为X_1，3-N(X_1，3，{00，01}).

当n=3，k=1，σ=n-1时，选择一条边(00，01)，令故障集合为Γ(X_1，3，{00，01})={02，10，11，20，21}. 明显的|Γ(X_1，3，{00，01})|=5=2×1×(3-1)+3-2. 容易验证X_1，3-Γ(X_1，3，{00，01})有且仅有两个连通分支：其中一个连通分支为X_1，3[{00，01}]，另外一个连通分支为X_1，3-N(X_1，3，{00，01}).

接下来，我们将n视作一个常量，假设该结论在k=τ-1(τ≥2)时成立. 当k=τ时，通过归纳假设，证明存在一条边(u，v)∈E(X_k-1，n^α)，使得在X_k-1，n^α中，|Γ(X_k-1，n^α，{u，v})|=2(τ-1)σ+n-2，并且X_τ-1，n^α-N(X_τ-1，n^α，{u，v})有且仅有两个连通分支：其中一个连通分支为X_τ-1，n^α[{u，v}]，另外一个连通分支为X_τ-1，n^α-N(X_τ-1，n^α，{u，v}). 其中0≤α≤s，根据定义2，当σ=1时s=t_k-1，n+1，当σ=n-1时，s=n.

令G₀=X_τ-1，n^α-N(X_τ-1，n^α，{u，v})-{u，v}，G₁=X_τ，n-X_τ-1，n^α-N((X_τ，n-X_τ-1，n^α)，{u，v}).

令F₁=N((X_τ，n-X_τ-1，n⁰)，{u，v})表示{u，v}在X_τ-1，n^α外的邻居，根据定义2有|F₁|=2σ. 令f_β=max{f_i|0≤i≤m，i≠α}，则有f_β＜|F₁|=2σ≤2(τ-1)σ+n-2，因此G₁是连通的. 根据定义2可知G₀中至少存在一个点连接到G₁. 则X_τ，n-Γ(X_τ，n，{u，v})有且仅有两个连通分支：其中一个连通分支为X_τ，n[{u，v}]，另一个连通分支为X_τ，n-N(X_τ，n，{u，v}).

通过上述过程知κ'(X_τ，n)≤2τσ+n-2成立.

综上所述，当n≥3，k≥1，σ∈{1，n-1}时，κ'(X_k，n)=2kσ+n-2，证毕.

3. 递归型数据中心网络基于限制故障集的单播算法

定理4  证明了递归型通用网络上限制连通度的精确值，本节将提出网络上基于限制故障顶点集合的单播算法XFRouting.

Algorithm：XFRouting

Input：A network X_k，n，a global variable σ∈{1，n-1}，a faulty node set F⊂V(X_k，n) with |F|≤2kσ+n-3，and two nodesu，v∈V(X_k，n).

Output：A path fromutov in X_k，n-F.

Let σ to be a global variable；

print (XFR(X_k，n，F，u，v))；

function XFR(X_k，n，F，u，v，k)

1. if (u，v)∈E(X_k，n) or k=0 then

2. return (u，v)；

3. else if |F|≥2kσ+n-2 then

4. return (BFS(X_k，n-F，u，v))；

5. else if F=Ø then

6. if σ=1 then

7. return DCellRouting (X_k，n，u，v)；

8. else if σ=n-1

9. then return BCubeRouting (X_k，n，u，v)；

10. end if

11. end if

12. Let m Fas the first index of the subsets with the minimal number of fault nodes

13. Let α←(u)_k，β←(v)_k；

14. if α=β then

15. if α∈mF then return (XFR(X_k-1，n^α，F_α，u，v，k-1))；

16. else if α∉mF then

17. for i in mF then

18. P←XMapping(u，X_k，n，X_k-1，nⁱ，F，mF)；

19. Q←XMapping(v，X_k，n，X_k-1，nⁱ，F，mF)；

20. break；

21. end for

22. if V(P)∩V(Q)=Ø then

23. S←XFR(X_k-1，nⁱ，F，P[-1]，Q[-1]，k-1)；

24. end if

25. return (P，S，Q^-1)；

26. Find the 1st common node x from P and Q；

27. return (Path(P，u，x)，Path(Q^-1，x，v))；

28. end if

29. else if α≠β then

30. if α∈mF then

31. Q←XMapping(v，X_k，n，X_k-1，n^α，F，mF)；

32. if u∈V(Q) then return (Path(Q，u，v))；

33. end if

34. return (XFR(X_k-1，n^α，F，u，Q[-1]，k-1)，Q)；

35. else if β∈mF then

36. P←XMapping(u，X_k，n，X_k-1，n^β，F，mF)；

37. if v∈V(P) then return (Path(P，u，v))；

38. end if

39. return(P，XFR(X_k-1，n^β，F，P[-1]，v，k-1))；

40. else then

41. for i in mF then

42. P←XMapping(u，X_k，n，X_k-1，nⁱ，F，mF)；

43. Q←XMapping(v，X_k，n，X_k-1，nⁱ，F，mF)；

44. break；

45. end for

46. if V(P)∩V(Q)=Ø then

47. S←XFR(X_k-1，nⁱ，F，P[-1]，Q[-1]，k-1)；

48. end if

49. return (P，S，Q^-1)；

50. Find the 1st node x from P and Q；

51. return (Path(P， u，x)，Path(Q^-1，x，v))；

52. end if

53. end function

function XMapping(u，G₀，G₁，F，mF)

1. for v in N(G₀-F，u) and v in mF then return (u，v)；

2. end for

3. for v in N(G₀-F，u) then

4. for x in N(G₁-F，v) and v in mF then

5. return (u，v，x)；

6. end for

7. end for

8. for v in N(G₀-F，u) then

9. for x in N(G₀-F，v) then

10. for y in N(G₁-F，x) and y in mF then

11. return (u，v，x，y)；

12. end for

13. end for

14. end for

18. end function

接下来，定理5将给出XFRouting算法的设计思路和执行过程，并分析其时间复杂度.

定理5  当k≥1，n≥3且σ∈{1，n-1}时，对于任意的顶点集合F⊂V(X_k，n)且|F|≤2kσ+n-3，算法XFRouting可以构造出X_k，n-F中任意两个不同顶点间的一条无故障路径，时间复杂度为O(k)≤O(⌈log_s|F|⌉k³).

证  当k≥1，n≥3且σ∈{1，n-1}时，故障集合F⊂V(X_k，n)且满足|F|≤2kσ+n-3，XFRouting算法可以构造出X_k，n-F中任意两个不同顶点u到v的一条无故障路径. XFRouting算法中包括4个函数：XFR，XMapping，DCellRouting^[12]和BcubeRouting^[13]. 其中实现函数XMapping构造出从G₀中的顶点u到G₁-F的一条无故障路径，函数DCellRouting构造出当σ=1时X_k，n中u到v的一条路径，函数BcubeRouting构造出当σ=n-1时X_k，n中u到v的一条路径. 函数XFR将构造的路径以一个向量的形式保存，向量中的顶点采用长度为k+1的字符串表示.

函数XFR第1-2行，如果u和v存在边，则直接返回边(u，v). 函数XFR第3-4行，如果条件满足|F|≥2kσ+n-2，则采用广度优先算法(BFS)构造一条无故障路径，在最坏情形下时间复杂度为O((t_k，n)²). 函数XFR第5-11行，当无故障顶点且σ=1时函数DCellRouting构造一条无故障路径，时间复杂度为O(k)，当无故障顶点且σ=n-1时调用函数BcubeRouting构造一条无故障路径，时间复杂度为O(k). 函数XFR第12行，计算最小故障子集，时间复杂度为O(k).

接下来分5种情况讨论函数XFR的时间复杂度，令R=n+kσ-1，mF表示故障数最小的子图前缀，s表示子集的个数，其中当σ=1时，s=t_k-1，n+1，当σ=n-1时，s=n. 函数XFR第14-15行，当α=β且α∈mF时，T(k)≤T(k-1)+O(R)；函数XFR第16-28行，当α=β且α∉mF时，则有T(k)≤T(k-1)+O(R³)；函数XFR第29-34行，当α≠β且α∈mF时，则有T(k)≤T(k-1)+O(R³)；函数XFR第35-39行，当α≠β且β∈mF时，则有T(k)≤T(k-1)+O(R³)；函数XFR第40-52行，当α≠β，α∉mF且β∉mF时则有T(k)≤T(k-1)+O(R³).

因此可得：

即O(k)≤O(log_s|F|k³)，证毕.

接下来，定理6分析XFRouting算法构造的路径长度的最大值.

定理6  当k≥1，n≥3且σ∈{1，n-1}时，对于任意的顶点集合F⊂V(X_k，n)且|F|≤2kσ+n-3，XFRouting算法可以构造出X_k，n-F中任意两个不同顶点间的一条无故障路径，其路径长度的上界为

证  令L(k)表示XFRouting算法构造得到的路径的长度. 当|F|=0时，令D(X_k，n)表示图X_k，n的直径，根据文献[12]和文献[13]，则有

当0＜|F|≤2kσ+n-3时，分为以下情形讨论：

函数XFR第14-15行，L(k)=L(k-1)；函数XFR第16-28行，L(k)≤L(k-1)+6；函数XFR第29-34行，L(k)≤L(k-1)+3；函数XFR第35-39行，L(k)≤L(k-1)+3；函数XFR第40-52行，L(k)≤L(k-1)+6.

令

则有

当σ=1时s=t_k-1，n+1$ \gg $|F|，则d=log_s|F|＜1. 因此有

证毕.

综上所述，本文提出的时间复杂度为O(log_s|F|k³)的算法XFR与采用时间复杂度为O((t_k，n)²)的广度优先搜索算法相比，具有明显的优越性.

5. 结论

数据中心网络的容错性是评估其网络性能的重要因素，如果用连通度来评估其容错性能，会低估数据中心网络的容错性能. 基于每个顶点都至少有一个无故障邻居这一条件下的限制连通度，能够更加精确地度量数据中心网络的容错性. 本文提出了一类递归型数据中心网络(RDCN)，与传统树形数据中心网络相比，该网络具有更好的网络带宽和网络容错性能. 证明了当k≥1，n≥3且σ∈{1，n-1}时，其限制连通度为2kσ+n-2，这一结果近于其连通度的2倍；接着提出了该情形下时间复杂度为O(^「log_s|F|⌉k³)的容错单播路由算法，证明了在最坏情况下构造出容错单播路由最长路径长度的上界. 仿真实验结果表明XFRouting算法在执行效率上优于广度优先搜索算法和深度优先搜索算法.

Figure (2) Table (1) Reference (15)

Name
	Name cannot be empty!
E-mail
	Mailbox cannot be empty! Mailbox cannot be empty!
Telephone
	Mobile number cannot be empty! Please enter a valid mobile number!
Title

Content
Verification Code

[1]	李文信, 齐恒, 徐仁海, 等. 数据中心网络流量调度的研究进展与趋势[J]. 计算机学报, 2020, 43(4): 600-617. Google Scholar
[2]	陆菲菲, 谢向辉, 郭得科, 等. 一种构建超大规模数据中心的模块化网络结构[J]. 软件学报, 2017, 28(8): 2196-2213. Google Scholar
[3]	GU M M, HAO R X, ZHOU S M. Fault Diagnosability of Data Center Networks[J]. Theoretical Computer Science, 2019, 776: 138-147. doi: 10.1016/j.tcs.2019.01.020 CrossRef Google Scholar
[4]	HARARY F. Conditional Connectivity[J]. Networks, 1983, 13(3): 347-357. doi: 10.1002/net.3230130303 CrossRef Google Scholar
[5]	ESFAHANIAN A H. Generalized Measures of Fault Tolerance with Application to N-Cube Networks[J]. IEEE Transactions on Computers, 1989, 38(11): 1586-1591. doi: 10.1109/12.42131 CrossRef Google Scholar
[6]	OH A D, CHOI H A. Generalized Measures of Fault Tolerance in N-Cube Networks[J]. IEEE Transactions on Parallel and Distributed Systems, 1993, 4(6): 702-703. doi: 10.1109/71.242153 CrossRef Google Scholar
[7]	WANG X, FAN J X, ZHOU J Y, et al. The Restricted H-Connectivity of the Data Center Network DCell[J]. Discrete Applied Mathematics, 2016, 203: 144-157. doi: 10.1016/j.dam.2015.09.002 CrossRef Google Scholar
[8]	王喜, 何福男, 张书奎. 交错立方体上限制容错单播算法的研究[J]. 西南师范大学学报(自然科学版), 2018, 43(9): 51-59. Google Scholar
[9]	WEI C C, HSIEH S Y. H-Restricted Connectivity of Locally Twisted Cubes[J]. Discrete Applied Mathematics, 2017, 217: 330-339. doi: 10.1016/j.dam.2016.08.012 CrossRef Google Scholar
[10]	NING W T. The H-Connectivity of Exchanged Crossed Cube[J]. Theoretical Computer Science, 2017, 696: 65-68. doi: 10.1016/j.tcs.2017.07.023 CrossRef Google Scholar
[11]	LI Z H, YANG Y Y. RRect: a Novel Server-Centric Data Center Network with High Power Efficiency and Availability[J]. IEEE Transactions on Cloud Computing, 2020, 8(3): 914-927. Google Scholar
[12]	ZHANG Z, DENG Y H, MIN G Y, et al. HSDC: a Highly Scalable Data Center Network Architecture for Greater Incremental Scalability[J]. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(5): 1105-1119. doi: 10.1109/TPDS.2018.2874659 CrossRef Google Scholar
[13]	GUO C X, WU H T, TAN K, et al. Dcell: a Scalable and Fault-Tolerant Network Structure for Data Centers[C] //Proceedings of the ACM SIGCOMM 2008 conference on Data communication-SIGCOMM '08. New York: ACM Press, 2008: 75-86. Google Scholar
[14]	GUO C, LU G, LI D, et al. BCube: a High Performance, Server-Centric Network Architecture for Modular Data Centers[C] //Proceedings of Special Interest Group on Data Communication (SIGCOMM). New York: IEEE Press, 2009. Google Scholar
[15]	王喜. DCell网络上的路径覆盖和限制连通性研究[D]. 苏州: 苏州大学, 2015. Google Scholar

Message Board

A Fault-Tolerant Unicast Routing Algorithm for a Class of Recursive Data Center Networks

Abstract

References

Access History

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Access History

Other Articles By Authors