• 每个节点维护一张路由表,根据这张路由表为传输到网络中任何其他节点的数据提供路由
    • 路由表是根据本地链路信息库和拓扑集合中的信息计算出来的
    • 因此，若其中任何一个集合发生了变化，则必须重新计算路由表，更新到达网络中每个目的节点的路由信息
    • 路由表中记录的路由条目的格式如下:

    image.png

    • 路由表中记录的每个路由条目(即一条路由)包含：
      • R_dest_addr( 目的节点地址)
      • R_next_addr(到达R_dest_addr 的下一跳节点的接口地址)
      • R_dist(本地节点与R_dest_addr 之间的跳数距离)
      • R_iface_addr (本地接口地址)四个元素
    • 每个路由条目说明以下三层意义
      • ①由地址R_dest_addr确定的目的节点估计离本节点的距离为R_dist 跳
      • ②具有接口地址R_next_addr 的对称相邻节点是到达R_dest_addr 的下一跳节点
      • ③这个相邻节点通过R_face_addr可达
    • 在路由表中为网络中每个已知到达路由的目的节点记录相应的路由条目
    • 凡是其到达路由中断或者不完全知道的目的节点则不记录在路由表中
    • 更加确切地说，每当检测出以下变化之一时就更新路由表
      • ①链路集合变化
      • ②相邻节点集合变化
      • ③二跳相邻节点集合变化
      • ④拓扑集合变化
      • ⑤多接口关联信息库变化
    • 或者更加确切地说，每当发生以下情况之一时，则重新计算路由表
      • ①出现或者丢失一个相邻节点
      • ②建立或者删除个二跳相邻节点数组
      • ③建立或者删除一个拓扑数组
      • ④多接口关联信息库发生变化
    • 这种路由信息更新既不会产生或者触发任何消息被发送到整个网络中

    • 也不会产生或者触发任何消息被发送到一跳相邻区域内

    • 为了建立节点X的路由表，需要在一张定向图上运行最短路径算法

    • 定向图包含以下三条弧线

      • ①弧X➡Y,Y是节点x的任一对称相邻节点(其相邻节点类型为SYM)
      • ②弧Y➡Z,节点Y是一个愿意域设置不等于WILL NEVER (从不愿意为其他节点转发信息)的相邻节点，二跳相邻节点集合中存在一个条目将节点Y作为Nneighbor_main addr 地址，和将节点Z作为N_2hop_addr地址
      • ③弧U➡V,拓扑集合中存在一个条目将节点V作为T_dest _addr地址和将节点U作为T_last_addr地址

    • 下面以一个计算(或者重新计算)路由表的例子给出路由表计算的规程:

    • 第一，将路由表中全部条目删除。
    • 第二，给路由表中添加新的路由条目：
      • 从将对称相邻节点(h=1) 作为目的节点开始添加。
      • 因此，对于相邻节点集合中其状态N_tatus=SYM 的每个相邻节点数组(存在一条对称链路到达该相邻节点)，以及对于该相邻节点的每个关联链路数组，其L_time ≥current time,则在路由表中记录一个新的路由条目:
        • R_dest_addr= 该关联链路数组的L_neighbor_iface_addr
        • R_next_addr= 该关联链路数组的L_neighbor_iface_addr
        • R_dist=1 (跳)
        • R_iface_addr= 该关联链路数组的L_local_iface_addr
      • 假如上面不存在等于该相邻节点的主地址的R_dest_addr 地址,则必须在路由表中再添加一个新的路由条目:
        • R_dest_addr=该相邻节点的主地址
        • Rnext_addr=一个L_time≥current time的关联链路数组的L_neighbor_iface addr
        • R_dist=1 (跳)
        • R_iface_addr =该关联链路数组的L_local_iface_addr
    • 第三，对于集合N2中的每个节点，即一个既不是相邻节点也不是节点本身的二跳柜邻节点，二跳相邻节点集合中至少存在一个条目
      • 其N_neighbor_main_addr 地址等于一个其愿意域设置不等于WILL_NEVER (从不愿意为其他节点转发信息)的相邻节点，则选择一个二跳相邻节点数组，并在路由表中建立一个路由条目:
        • R_dest_addr=该二跳相邻节点的主地址
        • Rnextaddr=R_nextaddr(路由表中R_dest_addr=该二跳相邻节点数组的N_neighbor_main_addr 的路由条目的R next addr)
        • R_dist=2 (跳)
        • Riface_addr=R_iface_addr(路由表中R_dest_addr=该二跳相邻节点数组的N_neighbor_main_addr 的路由条目的R iface_addr)
    • 第四，将h+1跳的目的节点的新路由条目记录在路由表中
      • 从h=2开始，必须对1的每个取值执行如下计算规程
      • 每执行一次，则将h加1
      • 假如在计算规程重复执行过程中没有新的路由条目需要记录，则停止计算规程的执行
      • (1)对于拓扑表中的每个条目，若其T_dest_addr不等于路由表中任何条目的R_dest_addr，并且其T_last__addr 等于某个R_dist 等于h的路由条目的R_dest_addr, 则必须给路由表中添加一个新的路由条目(假如还不存在的话):
        • R_dest_addr= T_dest_addr
        • R_next_addr= R_next_addr（一个已记录的R_dest_addr= T_last_addr的路由条目的)
        • R_dist=h+1 (跳)
        • R_iface_addr=R_iface_addr (一个已记录的R_dest_addr = T_last_addr的路由条目的)
      • (2) 可能需要使用若干个拓扑条目为可达目的节点R_dest_addr 选择其下一跳节点R_next_addr，当h=1时,应该做出选择，以便优先选择MPR选择器和愿意域设置最高的节点作为下一跳节点
    • 第五，对于多接口关联信息库中的每个条目
      • 若存在一个R_dest_addr = 该多接口关联条目的I_main_addr的路由条目
      • 并且不存在R_dest_addr = I_iface_addr的路由条目,则在路由表中添加一个新的路由条目:
        • R_dest_addr=该多接口关联条目的I_iface_addr
        • R_next_addr=已记录的一个路由条目的R_next_addr
        • R_dist=已记录的一个路由条目的R_dist
        • R_iface_addr=已记录的一个路由条目的R_iface_addr