4.10.1基于局部信息的模型 算法举例(cont'd) 1. 由于0101的第3维链接出现错误， 节点0101将发送(1，[3]，m,0000)到01014=1101。 2. 然而，由于1101的第3维的链接出现错误， 节点1101将使用第1维（标记=0100，标记记下了要 绕道时的首选维度)，并发送消息(2，[3,1]，， 0101)到1100。 1100 1000 0100 00a0 101g 0110 00 0中1 1111 011 oos
4.10.1 基于局部信息的模型 算法举例（cont'd） 1. 由于0101的第3维链接出现错误， 节点0101将发送(1, [3], m, 0000)到01014=1101。 2. 然而，由于1101的第3维的链接出现错误， 节点1101将使用第1维（标记=0100，标记记下了要 绕道时的首选维度），并发送消息(2, [3, 1] , m, 0101)到1100
4.10.1基于局部信息的模型 算法举例(cont'd) 5. 1100依次将发送(1，[1]，m,0101)到1000。 6. 随后，节点1000的第一个链接又出现错误。这时将使用 第2维（此时标记=0101)，(2，[1,2]，m,0111)被路由到 1010. 7. 之后，消息将经过1011到达目标1001。 结果路径的长度 是8。 1100 1000 0100 0030 11t0 1019 0110 00 1101 1111
4.10.1 基于局部信息的模型 算法举例（cont'd） 5. 1100依次将发送(1, [1], m, 0101)到1000。 6. 随后，节点1000的第一个链接又出现错误。这时将使用 第2维（此时标记=0101）, (2, [1, 2], m, 0111)被路由到 1010。 7. 之后，消息将经过1011到达目标1001。结果路径的长度 是8
4.10.2基于有限全局信息的模型： 安全等级（定义） 。考虑具有节点故障的超立方中的有效路由 。每个节点的有限全局信息使用安全等级来标记。 从根本上说，安全等级就是每个节点周围邻居中失效节 点的大致数目。 定义： 设s(a)=k是节点a的安全等级，则称a是k-安全的： 。一个失效节点是0-安全的，即最低的安全等级， 一个-安全的节点（也叫安全节点）安全级别最高 若kn,那么一个k-安全的节点就是不安全的
4.10.2 基于有限全局信息的模型： 安全等级（定义） ⚫ 考虑具有节点故障的超立方中的有效路由 ⚫ 每个节点的有限全局信息使用安全等级来标记。 ⚫ 从根本上说，安全等级就是每个节点周围邻居中失效节 点的大致数目。 ⚫ 定义： 设s(a)=k是节点a的安全等级，则称a是k-安全的； ⚫ 一个失效节点是0-安全的，即最低的安全等级， ⚫ 一个n-安全的节点（也叫安全节点）安全级别最高 ⚫ 若k≠n，那么一个k-安全的节点就是不安全的
安全等级的计算算法 ·下述算法决定了每个节点的状态。 每个节点a()都保存它所有邻居节点的非递减安全状态序列 开始，所有非出错节点都是-安全的，所有出错节点都是0- 安全的。 该算法需要n-1次重复达到稳定状态。 g1obal-status:=(n-1)儿P(0lP(1)月P(2)…lP(2-1月 P(i)::=determine a nondecreasing status sequence (So,S1,S2,...,Sn-1) of neighboring nodes; [(S0,S1,S2,,Sn-1)≥(0,1,2，，n-1) -+S(a(i)=n 口(S0,S1,S2,,Sk-1）≥(0,1,2，k-1)A(Sk-1=k-1) S(a(i))=k
安全等级的计算算法 ⚫ 下述算法决定了每个节点的状态。 ⚫ 每个节点a(i)都保存它所有邻居节点的非递减安全状态序列 ⚫ 开始，所有非出错节点都是n-安全的，所有出错节点都是0- 安全的。 ⚫ 该算法需要n-1次重复达到稳定状态
安全等级举例 出错节点0011,0100,0110和1001是0-安全的（黑色） 节点0001,0010,0111和1011是1-安全的（棕色），因为每个都有两个出 错节点，非递减序列为0,0,2,2或{0,0,2,4}或0,0,4,4}，k=1 >0} 节点0000和0101是2-安全的（紫色）。 非递减序列为：{0,1,1,4}，k=2>0,1} 1000,1010,1100,1101,1110和1111是安全的（蓝色） 非递减序列为：{0,4,4,4}或1,1,4,4}或0,2,4,4}>0,1,2.3} 1300 1000 0100 0000 T小0 00 01t0 00E0 1101 H 1l11 0111 00
安全等级举例 出错节点0011, 0100, 0110和1001是0-安全的（黑色） 节点0001, 0010, 0111和1011是1-安全的（棕色），因为每个都有两个出 错节点，非递减序列为{0,0,2,2}或{0,0,2,4}或{0,0,4,4},k=1 节点0000和0101是2-安全的（紫色）。 非递减序列为：{0,1,1,4},k=2 1000, 1010, 1100, 1101, 1110和1111是安全的（蓝色） 非递减序列为：{0,4,4,4}或{1,1,4,4}或{0,2,4,4} >{0} >{0,1} >{0,1,2,3}