域间路由系统的失效恢复方法和装置.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN107438026A(43)申请公布日2017.12.05(21)申请号201610363674.7(22)申请日2016.05.27(71)申请人任子行网络技术股份有限公司地址518057广东省深圳市南山区高新区科技中2路软件园2栋6楼(72)发明人景晓军沈智杰刘永强郭毅段海新魏克(74)专利代理机构深圳市顺天达专利商标代理有限公司44217代理人郭伟刚(51)Int.Cl.H04L12/703(2013.01)H04L12/715(2013.01)权利要求书2页说明书9页附图4页(54)发明名称域间路由系统的失效恢复方法和装置(57)摘要本发明公开了一种域间路由系统的失效恢复方法和装置。所述方法包括：根据预设的级联失效模型和预设的判断条件，在域间路由系统中，统计影响系统整体连通性的关键节点；在域间路由系统中，选取除关键节点和叶子节点外的节点，作为待选节点；统计待选节点的邻接节点，并根据预设规则计算待选节点对应的邻接节点的所有邻边的权重值；统计待选节点的所有邻接节点中非关键节点的剩余邻接节点；保留剩余邻接节点中，每个节点对应的邻边中权重值最大的邻边，并删除剩余邻接节点的其他邻边，生成相应的备份子图。本发明的方法只要域间路由系统的底层链接没有断开，可以通过备份子图，快速恢复关键节点的数据转发功能，实现域间路由系统失效的快速恢复。CN107438026ACN107438026A权利要求书1/2页1.一种域间路由系统的失效恢复方法，其特征在于，包括：根据预设的级联失效模型和预设的判断条件，在所述域间路由系统中，统计影响系统整体连通性的关键节点；在所述域间路由系统中，选取除所述关键节点和叶子节点外的节点，作为待选节点；统计所述待选节点的邻接节点，并根据预设规则计算所述待选节点对应的邻接节点的所有邻边的权重值；统计所述待选节点的所有邻接节点中非关键节点的剩余邻接节点；保留所述剩余邻接节点中，每个节点对应的邻边中权重值最大的邻边，并删除所述剩余邻接节点的其他邻边，生成相应的备份子图，所述备份子图用于在关键节点失效时，为失效的关键节点提供数据转发路径。2.根据权利要求1所述的方法，其特征在于，所述预设的级联失效模型，包括：当所述域间路由系统中，节点i失效后，节点i的邻接节点j通过如下公式进行负载重分配：ilj(t+1)＝(lj(t)+Δlj)；其中，Γi表示节点i所有邻接节点的集合；节点k为节点i所有邻接节点的集合中任一个节点；li(0)、lj(0)、lk(0)分别表示节点i、节点j、节点k的原始负载；d表示节点的度，即该节点所i有邻接节点的数量；α、β为初始负载参数，且均大于零；Δlj为节点i失效后分配给节点j的新增负载；lj(t)为负载重分配前的时刻t时，节点j上的负载；lj(t+1)为重新分配负载后，节点j在时刻t+1重启时的负载。3.根据权利要求2所述的方法，其特征在于，所述预设的判断条件，包括：选取对所述域间路由系统整体连通性影响排名前预设比例的节点，作为关键节点。4.根据权利要求1所述的方法，其特征在于，所述根据预设规则计算所述待选节点对应的邻接节点的所有邻边的权重值，包括：根据节点通过邻边单位时间内转发数据流量所属的范围区间，赋予邻边相应的权重值。5.根据权利要求1-4任一项所述的方法，其特征在于，所述方法还包括：判断生成的多个备份子图中所有叶子节点集合是否与所述域间路由系统中所有节点的集合相同，如果不相同，则继续选取待选节点，并生成相应的备份子图；如果相同，则停止生成备份子图。6.一种域间路由系统的失效恢复装置，其特征在于，包括：统计模块，用于根据预设的级联失效模型和预设的判断条件，在所述域间路由系统中，统计影响系统整体连通性的关键节点；选取模块，用于在所述域间路由系统中，选取除所述关键节点和叶子节点外的节点，作为待选节点；处理模块，用于统计所述待选节点的邻接节点，并根据预设规则计算所述待选节点对2CN107438026A权利要求书2/2页应的邻接节点的所有邻边的权重值；统计模块，还用于统计所述待选节点的所有邻接节点中非关键节点的剩余邻接节点；生成模块，用于保留所述剩余邻接节点中，每个节点对应的邻边中权重值最大的邻边，并删除所述剩余邻接节点的其他邻边，生成相应的备份子图，所述备份子图用于在关键节点失效时，为失效的关键节点提供数据转发路径。7.根据权利要求6所述的装置，其特征在于，所述预设的级联失效模型，包括：当所述域间路由系统中，节点i失效后，节点i的邻接节点j通过如下公式进行负载重分配：ilj(t+1)＝(lj(t)+Δlj)；其中，Γi表示节点i所有邻接节点的集合；节点k为节点i所有邻接节点的集合中任一个节点；li(0)、lj(0)、lk(0