您现在的位置: 首页 > 技术转让 > 一种基于胖树结构的动态容错方法和系统
一种基于胖树结构的动态容错方法和系统

一种基于胖树结构的动态容错方法和系统

  • 专利类型:发明专利
  • 有效期:不限
  • 发布日期:2021-07-15
  • 技术成熟度:详情咨询
交易价格: ¥面议
  • 法律状态核实
  • 签署交易协议
  • 代办官方过户
  • 交易成功

专利推荐

  • 技术(专利)类型 发明专利
  • 申请号/专利号 CN201010290544.8 
  • 技术(专利)名称 一种基于胖树结构的动态容错方法和系统 
  • 项目单位 中国科学院计算技术研究所
  • 发明人 胡农达;王达伟;安学军;孙凝晖 
  • 行业类别 电学
  • 技术成熟度 详情咨询
  • 交易价格 ¥面议
  • 联系人 李志文
  • 发布时间 2021-07-15  
  • 01

    项目简介

    本发明公开了一种基于胖树结构的动态容错方法和系统。所述方法,包括下列步骤:配置胖树网络;所述胖树网络中的交换机周期性地查看端口状态,当发现某端口失效时,向其他交换机发送链路失效消息;根据所述链路失效信息,实现动态容错路由。
    展开
  • 02

    说明书


    1.一种基于胖树结构的动态容错方法,其特征在于,所述方法,包括下列步骤:步骤100.配置胖树网络;步骤200.所述胖树网络中的交换机周期性地查看端口状态,当发现某端口失效时,向其他交换机发送链路失效消息;步骤300.根据所述链路失效信息,实现容错路由;所述步骤300,包括下列步骤:步骤310.源处理节点P发送数据包,数据包的目标处理节点是P’,其中所述p=pn-1pn-2…p1p0,所述p’=p’n-1p’n-2…p’1p’0;步骤320.收到所述数据包的交换机判断该数据包是否来自上端口或l≥lanc,若是,则通过SW<l,cn-2cn-3…c1c0>的下端口pl向下路由数据包,并完成路由;否则,执行步骤330,其中所述lanc是源处理节点和目的处理节点的最近公共祖先交换机的层号,lanc=max{i|pi≠p’i,i=0,1,…,n-1};步骤330.收到所述数据包的交换机检查自己的每个上端口k的状态PSk<l,f>,如果PSk
    .f为1且PSk
    .l<lanc,则将该端口从待选择的上端口的集合中排除;步骤340.收到所述数据包的交换机检查自身链路失效表中的链路失效条目LFE<c’n-2c’n-3…c’1c’0,f’m/2-1f’m/2-2……f’1f’0>,并判断条目所相关联的交换机SW<l1,c’n-2c’n-3…c’1c’0>是否为目的节点P’的祖先,若是,则检查f’i,i=0,1,..,m/2-1是否为1,若f’i为1,则将上端口i+m/2从待选择的上端口的集合中排除,如果f’i不为1,则不排除对应的上端口;否则,不排除任何上端口,所有链路失效条目的检查被同时执行;其中,所述链路失效条目LFE指示了对应的交换机SW<l1,cn-2cn-3…c1c0>的上端口链路LK<l1,cn-2cn-3…c1c0>m-1,LK<l1,cn-2cn-3…c1c0>m-2,…,LK<l1,cn-2cn-3…c1c0>m/2是否失效,l1为保存链路失效条目的交换机层号,cn-2cn-3…c1c0为条目中信息,fi表示链路LK<l1,cn-2cn-3…c1c0>m/2+i是否失效;步骤350.收到所述数据包的交换机检查上端口p’l是否在待选择的上端口的集合中;如果是,从上端口p’l对数据包进行路由;否则,选择下一个在待选择的上端口的集合中的端口进行路由;如果待选择的上端口的集合为空,则表明不存在健康的路径能够路由该数据包,该数据包被丢弃;其中m为胖树网络中交换机的端口数目,n为胖树的层数,l是交换机的层号,c和c’为交换机的坐标信息,f和f’为失效标识,i为下标变量,SW为交换机。
    2.根据权利要求1所述的基于胖树结构的动态容错方法,其特征在于,所述步骤100,包括下列步骤:由处理节点向其相连交换机发送位置配置消息来发起配置,接着获得位置配置消息的交换机通过向其邻居交换机发送位置配置消息对它们进行配置,然后被配置的邻居交换机再对它们的邻居交换机进行配置,直至网络中所有交换机都被配置。
    3.根据权利要求1所述的基于胖树结构的动态容错方法,其特征在于,所述步骤100,包括下列步骤:步骤111.处理器节点p向其相连交换机发送配置消息LCM<n,l2,c>,其中p=00..0,n是胖树的层数,l2是所连交换机的层号,c是交换机的坐标;步骤112.所述交换机利用收到的配置消息将自身配置为SW<l2,c>,并且,如果消息来自上端口,则向其下端口k’发送配置消息LCM<n,l2-1,cn-2cn-3…clk’cl-2…c1c0>,如果消息来自下端口,则向其上端口k发送配置消息LCM<n,l2+1,cn-2cn-3…cl+1(k-m/2)cl-1…c1c0>,向其下端口k’发送配置消息LCM<n,l2-1,cn-2cn-3…clk’cl-2…c1c0>;步骤113.收到交换机发来的配置消息的其他交换机重复步骤112,直至网络中所有交换机都被配置;步骤114.配置处理节点。
    4.根据权利要求2或3所述的基于胖树结构的动态容错方法,其特征在于,当交换机成功接收配置消息并配置后,会向消息来源端口回应一个确认信息,发出配置消息的交换机,如果没有收到确认消息,会超时重传配置消息,重传次数的上限是预设值。
    5.根据权利要求3所述的基于胖树结构的动态容错方法,其特征在于,所述处理节点的位置信息P在交换机完成配置后,由处理节点主动向与其相连的交换机请求获得节点的位置信息。
    6.根据权利要求1所述的基于胖树结构的动态容错方法,其特征在于,所述步骤200,包括下列步骤:步骤210.失效链路的侦测;步骤220.链路失效信息的传播。
    7.根据权利要求6所述的基于胖树结构的动态容错方法,其特征在于,所述步骤210,包括下列步骤:步骤211.所述胖树网络中的交换机周期性地向与其相连交换机发送侦测包对其链路进行侦测;步骤212.所述交换机的邻居交换机收到侦测包后,回应一个应答包,表示链路正常;步骤213.所述交换机判断从某端口发出的侦测包在一定时间内是否得到应答包,若是,则返回步骤211;否则,执行步骤214;步骤214.判断发送侦测包的次数是否超过一阈值,若是,则执行步骤215;否则,所述交换机重发侦测包,返回步骤213;步骤215.所述端口的链路被认为已经失效,相应的端口状态被设置为失效。
    8.根据权利要求7所述的基于胖树结构的动态容错方法,其特征在于,所述步骤214中,如果重发次数达到固定值时,仍旧没有收到应答包,则该端口的链路被认为已经失效,相应的端口状态被设置为失效;上端口状态用二元组PS<l3,f>表示,此处的l3是与失效链路有关的层号,f是失效标识;下端口状态仅用失效标识为f表示。
    9.根据权利要求6所述的基于胖树结构的动态容错方法,其特征在于,所述步骤220,包括下列步骤:步骤221.交换机侦测到其某下端口失效,则向除所述失效端口以外的所有端口发送上行链路失效消息ULFM<l,cn-2cn-3…c1c0,k>;步骤222.收到ULFM的交换机判断自己的层号是否等于l,若是,则执行步骤224;否则,执行步骤223;步骤223.判断所述ULFM是否来自上端口,若是,则所述交换机向其所有下端口转发ULFM;否则,所述交换机向除来源端口以外的所有端口转发ULFM;步骤224.收到所述ULFM的交换机将ULFM信息记录在交换机内的链路失效表的链路失效条目LFE<cn-2cn-3…c1c0,fm/2-1fm/2-2…f1f0>中;步骤225.判断交换机的链路失效表中是否存在某一链路失效条目LFE<cn-2cn-3…c1c0,fm/2-1fm/2-2…f1f0>的fm/2-1fm/2-2…f1f0为全1,若是,则该交换机向其所有下端口发送上行链路失效消息ULFM<l-1,cn-2cn-3…clicl-2…c1c0,m/2+cl-1>,其中l是交换机所在层号,i=0,1,…,m/2-1,返回步骤222;否则,执行步骤226;步骤226.判断交换机的链路失效表中是否存在某一链路失效条目LFE<cn-2cn-3…c1c0,fm/2-1fm/2-2…f1f0>的fm/2-1fm/2-2…f1f0不是全1,但fm/2-1fm/2-2…f1f0与交换机的所有上端口的状态二元组中失效标志PSm-1
    .f PSm-2
    .f…PSm/2
    .f按位或后,为全1并且所述交换机与条目所指示的交换机的SW<l,cn-2cn-3…c1c0>的最近公共祖先所在层号大于所有失效上端口的状态中的层号的最大值时,交换机向其所有下端口发送上行链路失效消息ULFM<l-1,cn-2cn-3…clicl-2…c1c0,m/2+cl-1>,其中l是交换机所在层号,i=0,1,…,m/2-1,返回步骤222;否则,不发送上行链路失效消息,其中所述最大值表示为max{PSi
    .l|PSi
    .f为1,i=m/2,m/2+1,…,m-1}。
    10.根据权利要求9所述的基于胖树结构的动态容错方法,其特征在于,所述链路失效条目LFE<cn-2cn-3…c1c0,fm/2-1fm/2-2…f1f0>,同一交换机的所有上端口的链路的失效信息被保存在同一条目中。
    11.根据权利要求8所述的基于胖树结构的动态容错方法,其特征在于,当一个交换机的所有上端口的状态二元组中的失效标志为1时,交换机向其所有下端口发送下行链路失效消息DLFM<l>,其中l是所有上端口状态二元组中层号的最大值,所述最大值表示为max{PSi
    .l|PSi
    .f为1,i=m/2,m/2+1,…,m-1}。
    12.一种基于胖树结构的动态容错系统,其特征在于,所述系统,包括:网络配置模块,用于配置胖树网络;链路失效检测模块,用于所述胖树网络中的交换机周期性地查看端口状态,当发现某端口失效时,向其他交换机发送链路失效消息;容错路由模块,用于根据所述链路失效信息实现容错路由;所述容错路由模块,包括:源端口判断模块.用于在收到所述数据包的交换机判断该数据包是否来自上端口或l≥lanc,若是,则通过SW<l,cn-2cn-3…c1c0>的下端口pl向下路由数据包,并完成路由;否则,触发筛选模块,其中所述lanc是源处理节点和目的处理节点的最近公共祖先交换机的层号;筛选模块,用于收到所述数据包的交换机检查自己的每个上端口k的状态PSk<l,f>,如果PSk
    .f为1且PSk
    .l<lanc,则将该端口从待选择的上端口的集合中排除;节点祖先判断模块,用于在收到所述数据包的交换机检查自身链路失效表中的链路失效条目LFE<c’n-2c’n-3…c’1c’0,f’m/2-1f’m/2-2……f’1f’0>,并判断条目所相关联的交换机SW<l1,c’n-2c’n-3…c’1c’0>是否为目的节点P’的祖先,若是,则检查f’i,i=0,1,..,m/2-1是否为1,若f’i为1,则将上端口i+m/2从待选择的上端口的集合中排除,如果f’i不为1,则不排除对应的上端口;否则,不排除任何上端口,所有链路失效条目的检查被同时执行,其中所述p’=p’n-1p’n-2…p’1p’0;其中,所述链路失效条目LFE指示了对应的交换机SW<l1,cn-2cn-3…c1c0>的上端口链路LK<l1,cn-2cn-3…c1c0>m-1,LK<l1,cn-2cn-3…c1c0>m-2,…,LK<l1,cn-2cn-3…c1c0>m/2是否失效,l1为保存链路失效条目的交换机层号,cn-2cn-3…c1c0为条目中信息,fi表示链路LK<l1,cn-2cn-3…c1c0>m/2+i是否失效;路由模块,用于收到所述数据包的交换机检查上端口p’l是否在待选择的上端口的集合中,如果是,从上端口p’l对数据包进行路由;否则,选择下一个在待选择的上端口的集合中的端口进行路由;如果待选择的上端口的集合为空,则表明不存在健康的路径能够路由该数据包,该数据包被丢弃;其中m为胖树网络中交换机的端口数目,n为胖树的层数,l是交换机的层号,c和c’为交换机的坐标信息,f和f’为失效标识,i为下标变量,SW为交换机。
    13.根据权利要求12所述基于胖树结构的动态容错系统,其特征在于,所述网络配置模块,包括:处理器节点触发模块,用于使处理器节点p向其相连交换机发送配置消息LCM<n,l2,c>,其中n是胖树的层数,l2是所连交换机的层号,c是交换机的坐标,其中(p=00..0);配置模块,用于使交换机利用收到的配置消息将自身配置为SW<l2,c>,并且,如果消息来自上端口,则向其每个下端口k’发送配置消息LCM<n,l2-1,cn-2cn-3…clk’cl-2…c1c0>,如果消息来自下端口,则其向其每个上端口k发送配置消息LCM<n,l2+1,cn-2cn-3…cl+1(k-m/2)cl-1…c1c0>,向其每个下端口k’发送配置消息LCM<n,l2-1,cn-2cn-3…clk’cl-2…c1c0>;处理节点配置模块,用于配置处理节点;重传模块,用于当交换机成功接收配置消息并配置后,向消息来源端口回应一个确认信息;当发出配置消息的交换机,如果没有收到确认消息时,超时重传配置消息,重传次数的上限是预设值。
    14.根据权利要求12所述基于胖树结构的动态容错系统,其特征在于,所述链路失效检测模块,包括:链路侦测模块,用于失效链路的侦测;失效信息传播模块,用于链路失效信息的传播。
    15.根据权利要求14所述基于胖树结构的动态容错系统,其特征在于,所述链路侦测模块,包括:侦测包发送模块.用于使交换机周期性地向与其相连交换机发送侦测包对其链路进行侦测;应答包发送模块,用于所述交换机的邻居交换机收到侦测包后,回应一个应答包,表示链路正常;判断模块,用于交换机判断从某端口发出的侦测包在一定时间内是否得到应答包,若是,则触发侦测包发送模块;否则,触发超时判断模块;超时判断模块,用于判断发送侦测包的次数是否超过一阈值,若是,则触发失效设置模块;否则,所述交换机重发侦测包,触发判断模块;失效设置模块,用于在所述端口的链路被认为已经失效时,将相应的端口状态被设置为失效。
    16.根据权利要求15所述基于胖树结构的动态容错系统,其特征在于,所述超时判断模块,如果重发次数达到固定值时,仍旧没有收到应答包,则该端口的链路被认为已经失效,相应的端口状态被设置为失效;上端口状态用二元组PS<l3,f>表示,此处的l3是与失效链路有关的层号,f是失效标识;下端口状态仅用失效标识为f表示。
    17.根据权利要求14所述基于胖树结构的动态容错系统,其特征在于,所述失效信息传播模块,包括:上行链路失效消息发送模块,用于交换机侦测到其某下端口失效,则向除所述失效端口以外的所有端口发送上行链路失效消息ULFM<l,cn-2cn-3…c1c0,k>;层号判断模块,收到ULFM的交换机判断自己的层号是否等于l,若是,则执行记录模块;否则,触发端口判断模块;端口判断模块.判断所述ULFM是否来自上端口,若是,则所述交换机向其所有下端口转发ULFM;否则,所述交换机向除来源端口以外的所有端口转发ULFM;记录模块,用于收到所述ULFM的交换机将ULFM信息记录在交换机内的链路失效表的链路失效条目LFE<cn-2cn-3…c1c0,fm/2-1fm/2-2…f1f0>中;判断子模块,用于判断是否存在交换机,其链路失效表的某一链路失效条目LFE<cn-2cn-3…c1c0,fm/2-1fm/2-2…f1f0>的fm/2-1fm/2-2…f1f0为全1,若是,则该交换机向其所有下端口发送上行链路失效消息ULFM<l-1,cn-2cn-3…clicl-2…c1c0,m/2+cl-1>,其中l是交换机所在层号,i=0,1,…,m/2-1,触发层号判断模块;否则,触发状态判断模块;状态判断模块.用于判断交换机的链路失效表中是否存在某一链路失效条目LFE<cn-2cn-3…c1c0,fm/2-1fm/2-2…f1f0>的fm/2-1fm/2-2…f1f0不是全1,但fm/2-1fm/2-2…f1f0与交换机的所有上端口的状态二元组中失效标志PSm-1
    .fPSm-2
    .f…PSm/2
    .f按位或后,为全1并且所述的交换机与条目所指示的交换机的SW<l,cn-2cn-3…c1c0>的最近公共祖先所在层号大于所有失效上端口的状态中的层号的最大值时,交换机向其所有下端口发送上行链路失效消息ULFM<l-1,cn-2cn-3…clicl-2…c1c0,m/2+cl-1>,其中l是交换机所在层号,i=0,1,…,m/2-1,触发层号判断模块;否则,不发送上行链路失效消息,所述最大值表示为max{PSi
    .l|PSi
    .f为1,i=m/2,m/2+1,…,m-1}。
    18.根据权利要求17所述基于胖树结构的动态容错系统,其特征在于,所述链路失效条目LFE<cn-2cn-3…c1c0,fm/2-1fm/2-2…f1f0>,同一交换机的所有上端口的链路的失效信息被保存在同一条目中。
    19.根据权利要求17所述基于胖树结构的动态容错系统,其特征在于,当一个交换机的所有上端口的状态二元组中的失效标志为1时,交换机向其所有下端口发送下行链路失效消息DLFM<l>,其中l是所有上端口状态二元组中层号的最大值,所述最大值表示为max{PSi
    .l|PSi
    .f为1,i=m/2,m/2+1,…,m-1}。
    展开

专利技术附图

< >

服务流程

过户资料

  • 买卖双方需提供资料
  • 平台提供
  • 过户后您将获得
  • 买家
  • 卖家
  • 公司
  • 企业营业执照
  • 企业营业执照

    专利注册证原件

  • 个人
  • 身份证

    个体户营业执照

  • 身份证

    专利注册证原件

  • 专利代理委托书

    转让申请书

    转让协议

  • 手续合格通知书

    专利证书

    专利利登记簿副本

安全保障

  • 品类齐全

    海量资源库,平台整合几十万闲置资源。
  • 交易保障

    完善的资金保障体系确保买卖双方资金安全。
  • 专人跟进

    专业交易顾问全程服跟进,确保交易流畅。
  • 快速响应

    专业在线/电话客服服务,快速响应贴心服务。
  • 售后无忧

    资质过硬,国内大知识产权服务平台。

在线客服

在线咨询

010-83278899

返回顶部