【技术领域】
本发明涉及数据通信网络技术领域，特别是涉及一种路由通过判定及问题定位方法和装置。
背景技术：
互联网物理上是由数量庞大的网络设备和计算机通过传输介质连接而成，计算机是互联网中服务的提供者和使用者，网络设备则组成服务提供者和服务使用者之间的桥梁。互联网主要的功能可以归纳为三大类：传送、计算和存储。其中主要功能之一的传送是由网络设备完成的。由于连接到互联网中的网络设备和计算机数量都是巨大的，使得网络拓扑极其庞大，网络信息从源站点传输到目的站点可能需要经过很多个中间设备，从源站点到目的站点的可选路由可能成百上千。因此如何为互联网中的信息找到安全、高效的路由是很复杂、很困难的任务。
针对网络路由的研究已持续很长时间，而且仍将长期持续下去。积累的研究成果也很多，传统的做法是将路由生成的任务分配给网络节点设备和路由协议，由每一台网络节点设备依据路由协议、相关数据和算法得到数据包传输的下一跳。这使得网络存在过于复杂、数据包路由不确定、难以排查问题等缺点。
近期对包括路由领域在内的网络技术的研究产生了一系列确定性路由的技术，如软件定义网络，由控制器来决定数据包的转发信息表，从而决定数据包的路由，当然数据包经过每一个网络设备仍是按照转发信息表进行转发。再如业务功能链，虽然也由控制器来配置业务功能链从而决定数据包的转发路由，但数据转发不是按传统转发信息表来转发，而是按业务功能链信息转发。另一种确定性路由技术是段路由，路由信息直接嵌入到数据包中。
基于这些确定性路由技术，在数据包进入网络中就可知道数据包的传播路由，这可避免传统路由技术的诸多问题。
但是，确定性路由也会带来新的问题：由于确定性路由的网络架构和相关方法均是基于路由确定来设计和应用的，那么数据包未按指定路由传输会带来一系列后果。而网络攻击、网络节点设备出错、拓扑改变则可能会导致数据包未按指定路由传输。因此，如何能找到一种方法能快速、简便的判断数据包是否按指定路由传输，并且能点位哪些设备导致该数据包未按指定路由传输，应用上价值明显。
技术实现要素：
本发明要解决的技术问题是数据包未按指定的路由传输或路由集传输，问题定位困难，缺少一种基于少量的开销或代价，来解决上述问题的实现手段。
本发明采用如下技术方案：
第一方面，一种路由通过判定及问题定位方法，包括：
第一设备给其控制的路由设备集范围内中每个路由设备，分配素数集中的一个素数作为相应路由设备的令牌token；
在路由设备间的数据转发协议中，分配出指定长度的第一存储空间；第一存储空间存储的参数值为s，所述s初始值由1异或key得到；其中，所述第一设备预先产生一个密钥key，以及一个小于素数集允许范围内的最大素数值pmax发送给所有被控路由设备；其中，分配的第一存储空间能存储的最大值不小于pmax；
在路由路径上的每台路由设备处，以密钥key加密压缩公式重新计算s，更新数据包中第一存储空间里的参数值s；
第一设备获取到路由路径末端的路由设备计算出的s，并通过末端的路由设备计算出的s来判定数据包是否完整的无遗漏、不重复的通过对应的路由设备。
优选的，所述第一设备具体为具有控制功能的功能实体，包括：
独立的控制器、融合控制功能的网络管理系统，或嵌入到其它网络设备上的控制功能。
优选的，所述指定长度具体为：1字节、2字节、4字节或者8字节。
优选的，所述第一存储空间为能存储pmax的最小存储空间。
优选的，以密钥key加密压缩公式重新计算s，并更新数据包中第一存储空间里的参数值s，具体包括：
在指定路由集sr＝[r1,r2,……,ru]中包含有u条路由路径，数据包需要按照指定路由集sr中的指定一路由路径传输，其中，数据包需要完整、无遗漏、无重复的经过sr中所述指定一条路由路径中的所有路由设备；
第j条路由路径rj＝[d1,d2,……,dt]为目标路由路径，则在协议数据包抵达对应第j条路由上每个设备di处，以密钥key加密压缩公式重新计算s，并更新数据包中第一存储空间里的参数值s。
优选的，所述密钥key加密压缩公式，具体为：
第一存储空间里的参数值s＝(sxorkey)*tokenmodpmaxxorkey。
优选的，所述并通过末端的路由设备计算出的s来判定数据包是否完整、无遗漏、无重复的通过对应的路由，具体包括：
根据以下公式计算从末端的路由设备获取到的s：
若上述等式成立，则数据包完整、无遗漏、无重复的通过了对应的路径；否则，数据包传送异常。
优选的，在路由通过判定为异常情况下进行问题定位时，所述方法还包括：
路由设备集rj＝[d1,d2……dt]；设定x的初始值为1；
如果x>＝f，则定位结束；
如果x<f，则对于rj中任意组合的x个路由设备子集rrjx，
如果未处理的rrjx存在，从rrjx中取出集合一个集合m，并从rrjx中删除，如果等式
如果等式不成立，则返回上一步；
否则对x进行自加1后，回到上述x与f大小的判断上。
优选的，存储s的协议字段由段路由头部的tlv来定义。
第二方面，本发明还提供了一种路由通过判定及问题定位装置，用于实现第一方面所述的路由通过判定及问题定位方法，所述装置包括：
至少一个处理器；以及，与所述至少一个处理器通信连接的存储器；其中，所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述处理器执行，用于执行第一方面所述的路由通过判定及问题定位方法。
第三方面，本发明还提供了一种非易失性计算机存储介质，所述计算机存储介质存储有计算机可执行指令，该计算机可执行指令被一个或多个处理器执行，用于完成第一方面所述的路由通过判定及问题定位方法。
本发明对数据包是否按照指定路由集传输进行判定；并且，进一步的能够在数据包未按照指定路由集传输的情况下，实现问题定位，确定路由上哪些数据包没有经过哪些设备提供了可能性。
进一步的，在本发明的优选方案中，给予问题定位具体实现方案的解决方案呈现，从而既能完成目标路由路径是否匹配的判断，还能在尽可能少的资源占用情况下，实现问题路由定位的确定。
【附图说明】
为了更清楚地说明本发明实施例的技术方案，下面将对本发明实施例中所需要使用的附图作简单地介绍。显而易见地，下面所描述的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1是本发明实施例提供的一种路由通过判定及问题定位方法流程示意图；
图2是本发明实施例提供的一种路由通过判定及问题定位方法流程示意图；
图3是本发明实施例提供的一种路由通过判定及问题定位方法流程示意图；
图4是本发明实施例提供的一种数据包是否通过路由集的判定流程图；
图5是本发明实施例提供的一种实际应用的网络物理拓扑；
图6是本发明实施例提供的一种应用场景实例之一业务功能链；
图7是本发明实施例提供的一种应用场景实例之二分布式dpi系统；
图8是本发明实施例提供的一种应用场景分布式dpi系统并发处理的示例；
图9是本发明实施例提供的一种应用场景实例之三段路由；
图10是本发明实施例提供的一种应用场景段路由多路由保护的示例；
图11是本发明实施例提供的一种路由通过判定及问题定位方法流程示意图。
【具体实施方式】
为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。
在本发明的描述中，术语“内”、“外”、“纵向”、“横向”、“上”、“下”、“顶”、“底”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明而不是要求本发明必须以特定的方位构造和操作，因此不应当理解为对本发明的限制。
此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。
实施例1:
本发明实施例1提供了一种路由通过判定及问题定位方法，如图1所示，包括：
在步骤201中，第一设备给其控制的路由设备集范围内中每个路由设备，分配素数集中的一个素数作为相应路由设备的令牌token。
所述第一设备可以是融合控制功能的网络管理系统，或者是嵌入到具体路由管理设备上的控制功能。
在步骤202中，在路由设备间的数据转发协议中，分配出指定长度的第一存储空间；第一存储空间存储的参数值为s，所述s初始值由1异或key得到；其中，所述第一设备预先产生一个密钥key，以及一个小于素数集允许范围内的最大素数值pmax发送给所有被控路由设备。
其中，分配的第一存储空间能存储的最大值不小于pmax。
其中，指定长度可以是1字节、2字节、4字节或者8字节，具体根据路径中路由节点数量多少来设定，同时第一存储空间为能存储pmax的最小存储空间。本发明实施例是在协议字段定义1，2，4或者8个字节来作为令牌使用，最少的是1个字节，最长的是8个字节，因此空间复杂度为o(1)。
所述pmax的取值在于，将本发明实施例中，用于携带在协议数据包头中的参数值s的大小做有效的压缩，从而保证了基于少量的开销或代价来实现路由路径的确认过程。
在步骤203中，在路由路径上的每台路由设备处，以密钥key加密压缩公式重新计算s，更新数据包中第一存储空间里的参数值s。
在本发明实施例中，所述密钥key加密压缩公式具体表现为s＝(sxorkey)*tokenmodpmaxxorkey；其中，xor为异或操作，mod为取余操作。作为本领域技术人员，基于上述工作做的合理的衍生公式均属于本发明实施例的保护范围内。
在步骤204中，第一设备获取到路由路径末端的路由设备计算出的s，并通过末端的路由设备计算出的s来判定数据包是否完整的无遗漏、不重复的通过对应的路由设备。
本发明实施例对数据包是否按照指定路由集传输进行判定；并且，进一步的能够在数据包未按照指定路由集传输的情况下，实现问题定位，确定路由上哪些数据包没有经过哪些设备提供了可能性。
针对本发明实施例步骤203中所涉及的，以密钥key加密压缩公式重新计算s，并更新数据包中第一存储空间里的参数值s，给予了一种更为具体的技术内容展现，如图2所示，具体包括：
在步骤2031中，在指定路由集sr＝[r1,r2,……,ru]中包含有u条路由路径，数据包需要按照指定路由集sr中的指定一路由路径传输，其中，数据包需要完整、无遗漏、无重复的经过sr中所述指定一条路由路径中的所有路由设备。
在步骤2032中，第j条路由路径rj＝[d1,d2,……,dt]为目标路由路径，则在协议数据包抵达对应第j条路由上每个设备di处，以密钥key加密压缩公式重新计算s，并更新数据包中第一存储空间里的参数值s。
针对本发明实施例步骤204中所涉及的，所述并通过末端的路由设备计算出的s来判定路由路径是否为目标路由路径，给予了一种更为具体的技术内容展现，具体包括：
根据以下公式计算从末端的路由设备获取到的s：
其中，f为目标路由路径的总数量，token(i)表示对应于相应第i个路由设备的token值；
若上述等式成立，则相应的路由路径便与目标路由路径相同；否则，相应的路由路径便于目标路由路径异常。
在路由通过判定为异常情况下进行问题定位时，如图3所示，所述方法还包括：
路径中设备集rj＝[d1,d2……dt]；设定x的初始值为1；
如果x>＝f，则定位结束；
如果x<f，则对于rj中任意组合的x个路由设备子集rrjx，
如果未处理的rrjx存在，从rrjx中取出集合一个集合m，并从rrjx中删除，如果等式
如果等式不成立，则返回上述是否存在未处理的rrjx的判断过程中；
否则对x进行自加1后，回到上述x与f大小的判断上。
在本发明的上述扩展方案中，给予问题定位具体实现方案的解决方案呈现，从而既能完成目标路由路径是否匹配的判断，还能在尽可能少的资源占用情况下，实现问题路由定位的确定。
实施例2：
本发明是对实施例1中阐述方法过程，结合实例场景描述的过程，通过进一步引入各种数据集的表征，以及核心算法公式的组合，来阐述较为完整的解决方案过程。在本发明实施例中，第一设备被具体表述为控制器，受控路由设备，以及路由设备也被简单描述为受控设备和设备，如图4所示：
控制器准备素数集s1＝[p1,p2,……pr]，r是自然数，p1,p2,……,pr是素数集中不同的素数；
控制器给其负责控制的路由设备集i1＝[d1,d2,……,dn]范围内中每个路由设备分配素数集s1中的一个素数pi做为令牌token；其中，n和i是自然数，d1,d2,……,dn对应于控制器给其负责网络中的路由设备；
在路由设备间的数据转发协议中，分配出指定长度的第一存储空间，所述第一存储空间在协议包头中；第一存储空间存储的值为s，其中，所述s初始值为1异或key，所述key由所述控制器分配；其中，所述控制器预先产生一个密钥key，以及一个小于max(s)的最大素数pm发送给所有被控设备；
在指定路由集sr＝[r1,r2,……,ru]中包含有u条路由，数据包需要按照指定路由集sr中的一路由传输；rj＝[d1,d2,……,dt]表明对应第j条路由上每个设备di处，以下列公式重新计算s，并更新数据包中的s：
s＝(sxorkey)*tokenmodpmxorkey；
控制器检索在路由末端的s，如果下面等式成立则设定的路由通过判定为真，否则为假：
其中，f为目标路由路径的总数量，token(i)表示对应于相应第i个路由设备的token值；
如图3是实现本方法在路由通过判定为异常情况下的问题定位功能主要流程，该流程主要包括如下步骤：
在步骤301中，路径中设备集rj＝[d1,d2,……,dt],x＝1。
在步骤302中，如果x<f，则进行步骤303；如果x>＝f，则进入步骤305定位结束，算法异常，报告错误。
在步骤303中，对于rj中任意组合的x个设备子集rrjx，
在步骤304中，如果未处理的rrjx存在，从rrjx中取出集合一个集合m，并从rrjx中删除；如果rrjx为空，则x ，返回步骤302。
在步骤305中，对于m如果下面等式成立，则定位结束，问题设备集为m。如果等式不成立，则返回步骤304；
实施例3：
如图5所示，说明了本方法应用的网络拓扑实例，由控制器和若干网络设备组成。实际上，控制器可以由具有控制功能的任意功能实体代替，如融合了控制功能的网络管理系统、具有控制功能的网络设备、具有控制功能的中间件等。
如图6所示描述了本方法在业务功能链上的应用场景。
业务功能链是一种确定性路由实现方法，数据包需按照控制器配置后的业务链进行有序传输。如图6所示，正常情况下数据包应沿着s1-s2-s3-s4-s5的路径传输，如果没有按照这个路径传输，就是异常状态。如附图6中，数据流实际按照s1-s2-s5的路由传输的情形。
针对附图6描述的业务功能链，本方法可使用，存储s的协议字段可由业务功能链的网络业务头(networkserviceheader，简写为：nsh)中可变长上下文头来定义。
如图7所示描述了本方法在分布式深度包检测系统的应用场景。
在分布式深度包检测(dpi)中，dpi功能可能由一组子功能(图中的元引擎)，按照一定顺序依次处理，共同完成必要的dpi功能。也就是说，数据包依照指定的路径依次经过相应的子功能。如果数据包没有按照指定的路由传输，dpi功能则不能实现。
本方法也适用于此领域，可以判定数据包是否通过指定的dpi子功能。在该应用场景中，存储s的字段可设计在数据包最后的字段，也可以使用包头中不用的字段。
如图8所示，描述了本方法在针对并发分布式dpi的应用实例。并发dpi有一条或多条能完成同样dpi功能的路由构成一个路由集，如图8所示，这个路由集包含两条并发的路由：(元引擎a，元引擎d，元引擎f)和(元引擎b，元引擎e，元引擎g，元引擎f)。路由通过判定时只要是按照路由集的任一路由通过，判定都是正确的。
如图9所示，描述了本方法在段路由的应用场景。
段路由是另一种确定性路由实现方法，数据包的路由不由各个网络设备根据协议来决定，而是封装在数据包中。也就是说，数据包头上封装了数据包的路由信息。在段路由中，数据包需按照包头携带的路由信息进行有序传输。
如图9所示，，绿色箭头线表示的是正常情况下数据包按照指定的路由传输的情形，紫色箭头线表示的没有按照指定路由传输的异常状态。
本方法同样适用于如图9所示的段路由，存储s的协议字段可由段路由头部(segmentroutinghead，简写为：srh)的可选tlv(全称为：tag,length和value)来定义。
如图10所示，描述了本方法在段路由的针对路由集的实例。这个路由集包含两条用于冗余保护的路由：(d1,d2,d3)和(d1,d6,d3)。路径通过判定时只要通过的是其中之一，都是正常的。
当然，本方法也可应用于其它数据包按照指定路由传输的应用场景。
实施例4：
如图11所示，是本发明实施例的路由通过判定及问题定位装置的架构示意图。本实施例的路由通过判定及问题定位装置包括一个或多个处理器21以及存储器22。其中，如图11所示，以一个处理器21为例。
处理器21和存储器22可以通过总线或者其他方式连接，图11中以通过总线连接为例。
存储器22作为一种非易失性计算机可读存储介质，可用于存储非易失性软件程序和非易失性计算机可执行程序，如实施例1中的路由通过判定及问题定位方法。处理器21通过运行存储在存储器22中的非易失性软件程序和指令，从而执行路由通过判定及问题定位方法。
存储器22可以包括高速随机存取存储器，还可以包括非易失性存储器，例如至少一个磁盘存储器件、闪存器件、或其他非易失性固态存储器件。在一些实施例中，存储器22可选包括相对于处理器21远程设置的存储器，这些远程存储器可以通过网络连接至处理器21。上述网络的实例包括但不限于互联网、企业内部网、局域网、移动通信网及其组合。
所述程序指令/模块存储在所述存储器22中，当被所述一个或者多个处理器21执行时，执行上述实施例1中的路由通过判定及问题定位方法，例如，执行以上描述的图1-图3所示的各个步骤。
值得说明的是，上述装置和系统内的模块、单元之间的信息交互、执行过程等内容，由于与本发明的处理方法实施例基于同一构思，具体内容可参见本发明方法实施例中的叙述，此处不再赘述。
本领域普通技术人员可以理解实施例的各种方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，该程序可以存储于一计算机可读存储介质中，存储介质可以包括：只读存储器(rom，readonlymemory)、随机存取存储器(ram，randomaccessmemory)、磁盘或光盘等。
以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。
1.一种路由通过判定及问题定位方法，其特征在于，包括：
第一设备给其控制的路由设备集范围内中每个路由设备，分配素数集中的一个素数作为相应路由设备的令牌token；
在路由设备间的数据转发协议中，分配出指定长度的第一存储空间；第一存储空间存储的参数值为s，所述s初始值由1异或key得到；其中，所述第一设备预先产生一个密钥key，以及一个小于素数集允许范围内的最大素数值pmax发送给所有被控路由设备；其中，分配的第一存储空间能存储的最大值不小于pmax；
在路由路径上的每台路由设备处，以密钥key加密压缩公式重新计算s，更新数据包中第一存储空间里的参数值s；
第一设备获取到路由路径末端的路由设备计算出的s，并通过末端的路由设备计算出的s来判定数据包是否完整的无遗漏、不重复的通过对应的路由设备。
2.根据权利要求1所述的路由通过判定及问题定位方法，其特征在于，所述
具体为具有控制功能的功能实体，包括：
独立的控制器、融合控制功能的网络管理系统，或嵌入到其它网络设备上的控制功能。
3.根据权利要求1所述的路由通过判定及问题定位方法，其特征在于，所述指定长度具体为：1字节、2字节、4字节或者8字节。
4.根据权利要求1所述的路由通过判定及问题定位方法，其特征在于，所述第一存储空间为能存储pmax的最小存储空间。
5.根据权利要求1所述的路由通过判定及问题定位方法，其特征在于，以密钥key加密压缩公式重新计算s，并更新数据包中第一存储空间里的参数值s，具体包括：
在指定路由集sr＝[r1,r2,……,ru]中包含有u条路由路径，数据包需要按照指定路由集sr中的指定一路由路径传输，其中，数据包需要完整、无遗漏、无重复的经过sr中所述指定一条路由路径中的所有路由设备；
第j条路由路径rj＝[d1,d2,……,dt]为目标路由路径，则在协议数据包抵达对应第j条路由上每个设备di处，以密钥key加密压缩公式重新计算s，并更新数据包中第一存储空间里的参数值s。
6.根据权利要求1所述的路由通过判定及问题定位方法，其特征在于，所述密钥key加密压缩公式，具体为：
第一存储空间里的参数值s＝(sxorkey)*tokenmodpmaxxorkey。
7.根据权利要求6所述的路由通过判定及问题定位方法，其特征在于，所述并通过末端的路由设备计算出的s来判定数据包是否完整、无遗漏、无重复的通过对应的路由，具体包括：
根据以下公式计算从末端的路由设备获取到的s：
若上述等式成立，则数据包完整、无遗漏、无重复的通过了对应的路径；否则，数据包传送异常。
8.根据权利要求7所述的路由通过判定及问题定位方法，其特征在于，在路由通过判定为异常情况下进行问题定位时，所述方法还包括：
路由设备集rj＝[d1,d2……dt]；设定x的初始值为1；
如果x>＝f，则定位结束；
如果x<f，则对于rj中任意组合的x个路由设备子集rrjx；
如果未处理的rrjx存在，从rrjx中取出集合一个集合m，并从rrjx中删除，如果等式
如果等式不成立，则返回上一步；
否则对x进行自加1后，回到上述x与f大小的判断上。
9.根据权利要求1-8任一所述的路由通过判定及问题定位方法，其特征在于，存储s的协议字段由段路由头部的tlv来定义。
10.一种路由通过判定及问题定位装置，其特征在于，所述装置包括：
至少一个处理器；以及，与所述至少一个处理器通信连接的存储器；其中，所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述处理器执行，用于执行权利要求1-9任一所述的路由通过判定及问题定位方法。
技术总结