4.10.1基于局部信息的模型 等位序列定义 定义：等位序列[d1,d2,,d] 为当前节点与目标节点不同的所有维度（也叫首选维 度，preferred dimension) 例如： 当前节点：0010 目标节点：0111 。注意： 等位序列是[1,3] 。为表示一个消息的目标，等位序列要和消息一起传送 。因当前节点会随着消息的传递而变化，故等位序列也随着变 化
4.10.1 基于局部信息的模型 等位序列定义 ⚫ 定义：等位序列[d1 , d2 , …, dk ] 为当前节点与目标节点不同的所有维度（也叫首选维 度，preferred dimension） ⚫ 注意： ⚫ 为表示一个消息的目标，等位序列要和消息一起传送 ⚫ 因当前节点会随着消息的传递而变化，故等位序列也随着变 化 例如： 当前节点：0 0 1 0 目标节点：0 1 1 1 等位序列是[1,3]
4.10.1基于局部信息的模型 消息的表示 。每个消息都有一个位的向量标志，用以保存“空余 维度(spare dimensions)”。 可以用这些维度来绕过出错组件。 注意： 空余维度就是那些没有在最初的等位序列中出现的维度 源节点发起路由时，标志中的所有位都将清零。 消息的表示： (k,[d1,d2,.,d,消息，标记)。 k为剩余路径长度，k会在消息的发往过程中不断更新 当k变为0时，消息就到达目标了
4.10.1 基于局部信息的模型 消息的表示 ⚫ 每个消息都有一个n位的向量标志，用以保存“空余 维度(spare dimensions)”。 ⚫ 可以用这些维度来绕过出错组件。 ⚫ 注意： 空余维度就是那些没有在最初的等位序列中出现的维度 ⚫ 源节点发起路由时，标志中的所有位都将清零。 ⚫ 消息的表示： (k, [d1 , d2 , …, dk ], 消息, 标记)。 ⚫ k为剩余路径长度， k会在消息的发往过程中不断更新 ⚫ 当k变为0时，消息就到达目标了
4.10.1基于局部信息的模型 算法描述 当节点收到一个消息时，检查k的值以判断自身 是否为消息的目标 若不是，节点将尝试按照剩下的等位序列中指定的维 度发送消息 每个节点都将努力沿着最短路径发送消息。 然而，若通往最短路径的维度的那些连接出错，这个 节点将使用空余维度通过另外的路径发送消息
4.10.1 基于局部信息的模型 算法描述 ⚫ 当节点收到一个消息时，检查k的值以判断自身 是否为消息的目标 ⚫ 若不是，节点将尝试按照剩下的等位序列中指定的维 度发送消息 ⚫ 每个节点都将努力沿着最短路径发送消息。 ⚫ 然而，若通往最短路径的维度的那些连接出错，这个 节点将使用空余维度通过另外的路径发送消息
4.10.1基于局部信息的模型 算法的描述 初始，等位序列为由源和目标地 址异或得到的所有首选维度， P(u)::=[initiate-routing-process 空余维度的所有位清零。 send ([di,d2,...,d,m,0)to P(u) 口receive(k,d,2,,d],message,tag）+ k =0-save (message) ok≠O→intermediate-node intermediate-node::= 每个节点努力沿着最短路径传送 [The djth(1≤j≤k)link and neighbor are both healthy→ [send(k-1,[d,…,d-1,d+1,,d4k], message,tag)to u(d;) 注意：u0)表示沿着 维度i的u的邻居。 No link and neighbor are both healthy [V1≤i≤x \tag(di）:=1: tag(h)=l,where h=min{i:tag(i)=0,1≤t≤n}: send (k +1,[di.d2,...,d,h],message,tag)to u(h) ]
4.10.1 基于局部信息的模型 算法的描述 注意：u (i)表示沿着 维度i的u的邻居。 初始，等位序列为由源和目标地 址异或得到的所有首选维度， 空余维度的所有位清零。 每个节点努力沿着最短路径传送
4.10.1基于局部信息的模型 算法举例 假设消息m从u=0110→w=1001。 最初消息是(4，[1,2,3,4]，m,0000) 按照上述算法， 1. 节点0110将(3，[2,3,4]，m,0000)发送给01101=0111， 2. 随后0111将(2，[3,4]，m,0000)发送给01112=0101。 1l00 1000 0100 00a0 1110 1010 0110 010 m 1111 011 oos
4.10.1 基于局部信息的模型 算法举例 ⚫ 假设消息m从u=0110 → w=1001。 最初消息是(4, [1, 2, 3, 4], m, 0000) ⚫ 按照上述算法， 1. 节点0110将(3, [2 ,3 ,4], m, 0000)发送给01101=0111， 2. 随后0111将(2, [3, 4], m, 0000)发送给01112=0101