【摘要】 本发明公开了一种主干路由系统的三色环网络结构设计及维护方法，属于计算机应用技术领域。目的是解决同一行政区下代表各个子行政区的主干路由节点群之间的网络路由问题。其原理是网络结构设计使用“三角元”的地图着色技术对主干路由节点网的路由节点进行分类，构建三色环网络结构；路由策略设计是为各路由节点增加色环次序编号，并为每个路由节点建立两张中行路由表，使用“环、星结合，以环为主”的思路；并为网络路由系统的维护提供了新节点的加入和链路断路时的纠错方法。本发明避开了直接对路由节点分类将会遇到的诸多麻烦，将复杂问题简单化，节省了路由寻址时间，提高了网络的稳定性，并且易于管理和维护。 【专利类型】发明授权 【申请人】北京理工大学 【申请人类型】学校 【申请人地址】100081 北京市海淀区中关村南大街5号 【申请人地区】中国 【申请人城市】北京市 【申请人区县】海淀区 【申请号】CN200810227549.9 【申请日】2008-11-27 【申请年份】2008 【公开公告号】CN101414980B 【公开公告日】2010-12-22 【公开公告年份】2010 【授权公告号】CN101414980B 【授权公告日】2010-12-22 【授权公告年份】2010.0 【IPC分类号】H04L12/56; H04L12/24; H04L12/721 【发明人】偰赓; 樊秀梅; 廖乐健 【主权项内容】一种主干路由系统的三色环网络结构设计方法，其特征在于包括以下几个步骤：步骤一、网络拓扑设计用基于“三角元”的地图着色技术对主干路由节点网的路由节点进行分类，构建出三色环网络结构；用红、绿、黄三种颜色分别对构成三角形顶点的三个节点进行着色，具体包括以下步骤：首先用“就近添加辅助边”的方法对“主干路由节点网的邻接图”做一些修改，在保证图中任意两条边不相交的基础上，将三角形作为图的最小分解图形单元；其次，利用“三角元”法，对修改后的“邻接图”进行上色，采用三角网孔“两点决定第三点”的策略，允许出现相邻两个节点着色相同的情形；最后，分别用红、绿、黄三色线将相同颜色的节点按照地理位置顺次连接起来组成闭合的色环；如果同色节点本身相连，则沿用它们之间的边；步骤二、路由策略设计首先为各色环路由节点编号，方法是按照每个色环节点的连接顺序，从某个节点开始逆时针依次编号；其次为每个路由节点建立中行路由表，记录节点本层各个端口与相邻节点之间的对应情况、三个色环上所有已知节点的次序编号和这些节点本层编码之间的对应情况；再次，制定具体的路由策略，具体包括以下步骤：第一步，当收到数据包时，当前节点根据本层编码判断数据包的目的地址是否在其所辖网络域中，如果在，则按照基于行政区划的分层网络结构下行路由策略进行路由；第二步，如果目的地址不在当前节点所辖网络域中，而在相邻节点的网络域中，查找当前节点的路由表并将数据包发往相应的节点；第三步，如果目的地址既不在当前节点所辖网络域中，也不在相邻节点的网络域中，则查找当前节点的路由表，查看目的地址的本层编码属于哪个色环上的节点；分为下列两种情况：情况1：如果目的地址的本层编码属于当前节点所在色环上的节点B，设节点B的次序编号为b，当前节点的次序编号为a，当前节点所属色环的总节点数为N；若0＜b‑a≤N/2或b‑a≤‑N/2，则把数据包发往逆时针方向的同色节点；否则发往顺时针方向的同色节点；情况2：如果数据包目的地址的本层编码属于其它色环上的节点D，设节点D的次序编号为d，D所属色环的总结点数为M；在当前节点的相邻节点中，与D同色的节点表示为C1、C2、C3、…，它们的次序编号分别为c[1]、c[2]、c[3]、…；分别求|d‑c[i]|和M‑|d‑c[i]|的值，其中i＝1，2，3…，然后把数据包发往最小值所对应的相邻节点，若出现等值最小，则根据链路状况选择其一；第四步，若在当前节点的路由表中找不到相应表项，将数据包发往当前节点逆时针方向的相邻同色节点，以遍历当前节点所在色环的方式来查找；如果在该色环节点X的路由表中找到相应表项，就按步骤一至三中的路由策略将数据包发往本层节点；同时节点X需把该数据包本层目的节点的所属色环及次序编号信息反馈给本色环上缺失该信息的各节点；如果是节点A第一个收到第四步中本层目的节点信息不明的数据包，那么节点A须给该数据包打上信息不明标记；之后收到该数据包的节点，不打标记；根据信息不明标记提示，如果数据包环绕节点A所在色环一周后仍未找到其本层目的节点B，就将该数据包在节点A处缓存起来，然后用已有技术OSPF协议探路建立临时路由路径再传输的方法发送数据包；一旦节点B收到数据包并返回信息给节点A，就将这条临时路由路径从节点A的路由表中删除。 【当前权利人】北京理工大学 【当前专利权人地址】北京市海淀区中关村南大街5号 【统一社会信用代码】12100000400009127B 【引证次数】4.0 【他引次数】4.0 【家族引证次数】4.0 【家族被引证次数】5
