法律状态公告日
法律状态信息
法律状态
2017-04-19
授权
授权
2014-12-24
实质审查的生效 IPC(主分类):H04L12/701 申请日:20140831
实质审查的生效
2014-11-26
公开
公开
技术领域
本发明属于通信技术领域，更进一步涉及多个软件定义网络(Software Defined Network SDN)互联技术领域中的一种大规模软件定义网络(Software Defined Network SDN)中满足多约束参数的路由方法。本发明可以在软件定义网络(Software Defined Network SDN)中获取一条具有服务质量(Quality of Service QoS)保障的 域内和域间路由。
背景技术
随着互联网的高速发展，出现了各种非传统数据应用。例如IP语音以及视频会 议等，这种新的应用对网络的服务质量(Quality of Service QoS)提出了更高的要求， 传统的尽力而为的网络服务已不能满足新型业务的要求。互联网工程任务组(Internet Engineering Task Force IETF)为支持服务质量(Quality of Service QoS)需求，提出 了多种服务模型和机制。其中服务质量(Quality of Service QoS)路由是解决服务质 量问题的一项关键技术。现有网络架构的互联网在提供给用户服务质量方面存在着各 种重大缺陷。例如，综合业务模型和区分业务模型两种方法。对于前者，每个路由器 都要参与决策，导致复杂度过高和路由器负担太重：对于后者，流的控制粒度过于粗 放和不精细，导致端到端的控制效果不佳，所以也没用实用的价值。在软件定义网络 中，这一情况得到了根本的改变。软件定义网络将控制逻辑集中在了中央控制器，普 通的路由器结点只保留转发逻辑。这种集中控制架构正适合实现控制逻辑较为复杂的 服务质量控制。软件定义网络中若要解决服务质量问题，其中服务质量(Quality of Service QoS)路由则是一项关键技术。
Hilmi Enes Egilmez等人在其论文“A distributed QoS routing architecture for scalable video streaming over multi-domain OpenFlow networks”(Image Processing,201219th IEEE International Conference on)中公开了一种网络虚拟化的 方法。该方法利用各个域控制器来把本域网络虚拟化，通过和其他域控制器间交互这 些信息来获得全网的虚拟拓扑信息。再通过基于拉格朗日松弛的服务质量(Lagrange Relaxation Based Method for the QoS Routing Problem LARAC)路由算法，获得源端 到目的端的满足多约束路由。该方法存在的不足是，每个域网络的控制器都需要收集 全网虚拟后的网络拓扑信息，并且需要保证这些信息的实时性和准确性，这样就导致 网络的负载过重。
西安电子科技大学拥有的专利技术“用于支持端到端时延保证的动态资源分配 系统及分配方法”(申请号CN 201010013728.X，授权号CN 101729430)公开了一 种用于支持端到端时延保证的动态资源分配方法。该方法根据边界路由器发送的业务 请求信息中的时延上限要求，结合网络负载信息中的链路负载度和各段链路端口处各 PHB的时延估计值，计算端到端传输路径各段链路上的时延分配值，在相关的核心路 由器上，根据本地的可用资源状态，通过时延分配值和带宽要求的匹配，动态选择最 佳PHB进行资源配置和分组转发。该方法存在的不足是，首先，它不能解决多约束 条件下的服务质量问题。其次，核心路由器负担重，容易成为整个系统性能的瓶颈。
南京邮电大学申请的专利“基于选择探测的多约束QoS路由方法”(公开号CN 101969406，申请号CN 201010527712.0)公开了一种传统网络中获取满足多约束QoS 的路由方法。该方法利用选择性向网络中发送探测包来探测可行性路径，整个路由方 法分为路由探测和路由确认两个过程，在探测过程中，每个节点重新计算约束参数， 降低参数计算复杂度，然后依据新参数继续探测符合约束参数要求的可行路由；在确 认过程选取可行路由并在各个节点上进行资源预留，从而建立符合约束要求的可达路 由。该方法存在的不足是，首先，探测过程中有路径重复探测的问题，造成网络中有 大量探测包，网络开销大。其次，该方法仅仅考虑了时延和带宽因素，并没有考虑抖 动和丢包率对服务质量的影响，所以并不是真正意义上多约束条件下的服务质量问 题。
发明内容
本发明的目的在于克服上述现有技术的不足，提出了一种大规模软件定义网络 中满足多约束参数的路由方法。本发明采用了启发式基于多约束的最优路径算法 (Heuristic Multi-Constrained Optimal Path H_MCOP)和探测法相结合的一种方法，并 且也结合了资源预留技术。在域内网络运用启发式基于多约束的最优路径H_MCOP 的算法求出最优路径，在域间网络中有选择的发送探测包，最终源主机所在的控制器 能够获得到目的网络中满足多约束服务质量参数的可行性路径。由于探测包所走的路 径大部分都是转发器和控制器间的控制路径，故不会占用网络中数据链路的带宽资 源，同时只在域间网络中有选择发送探测包。这样做能够有效地减少网络中探测包的 个数，减低网络中数据链路带宽的消耗，同时可以解决软件定义网络中寻找满足多约 束参数路由的问题。
本发明实现上述目的的具体思路是：源主机所在网络的域网络控制器生成探测 包，向其他软件定义网络进行选择性发送探测包。在探测过程中不断判定子路径上累 加起来的服务质量参数是否满足约束，若满足，则将探测包继续向下游网络发送，否 则，直接丢弃探测包。待目的主机所在网络的控制器收到后，生成确认包，同时沿包 中的路径信息反向发送确认包。源主机所在网络的控制器从收集多条路径中选取一条 最优路径，并且预留链路的网络资源。能够解决软件定义网络中寻找满足多约束参 数路由的问题。
本发明实现上述目的的步骤包括如下：
(1)初始化探测报文：
(1a)域网络控制器接受源主机发送的路由请求，路由请求信息中包括源主机地 址、目的主机地址、时延、带宽、丢包率和抖动的服务质量参数值；
(1b)将探测包中路由请求服务质量值字段和域内约束值字段，均标记为服务质 量参数值；
(1c)将探测包中的类型字段标记为探测包类型；将路由请求标示符字段标记为 源主机地址、目的主机地址和控制器生成的随机数；将路径记录字段和子路径服务质 量累加值字段标记为零；
(1d)域网络控制器启动定时器，将定时器的时间值设为路由请求信息要求时延 的2倍；
(2)生成探测报文：
(2a)域网络控制器运行启发式基于多约束的最优路径H_MCOP的算法，将探 测包中域内约束值字段内容作为该算法的参数，得到从域网络入口转发器到所有域网 络边界出口转发器之间的域内最优路径；
(2b)将域内最优路径和与出口转发器相连的域间路径连接成新子路径；
(2c)判定新子路径的服务质量参数和探测包中子路径服务质量累加值字段的累 加和是否小于探测包要求的服务质量参数值，若是，则执行步骤(2d)；否则，删除 该新子路径，执行步骤(2g)；
(2d)运用探测包记录方法，在域网络控制器中记录探测包信息；
(2e)在域网络控制器中预留域内网络带宽资源，其预留时间设为路由请求信息 要求时延的2倍；
(2f)域网络控制器生成一个探测包副本，运用探测包修改方法，修改探测包的 内容；
(2g)判定所有新子路径是否都处理完毕，若是，则执行步骤(3)；否则，执行 步骤(2c)；
(3)探测路径：
(3a)计算探测包在域网络控制器上的等待时间Δt；
(3b)域网络控制器在等待时间Δt过后，将探测包发送到探测包标记的网络中；
(3c)判定域网络入口转发器之前是否收到过同样路由请求标示符的探测包，若 是，则执行步骤(3d)；否则，执行步骤(4)；
(3d)运用探测包记录方法，将探测包信息记录到域网络控制器中，作为待拼接 子路径，丢弃探测包，继续执行步骤(3c)；
(4)域网络控制器判断探测包是否到达目的主机所在网络，若是，则执行步骤 (5)；否则，转向步骤(2)；
(5)生成完整路径：
(5a)域网络控制器通过启发式基于多约束的最优路径H_MCOP的算法，得到 域网络入口转发器到域网络出口转发器之间的域内最优路径；
(5b)判定域内最优路径的服务质量参数和探测包中子路径服务质量累加值字段 的累加和是否小于探测包要求的服务质量参数，若是，则执行步骤(5c)；否则，丢 弃探测包，继续执行步骤(5a)；
(5c)运用探测包记录方法，在域网络控制器中记录探测包信息；
(5d)将探测包中子路径服务质量累加值字段标记为域内最优路径的服务质量参 数和探测包中子路径服务质量累加值字段的累加和，将域网络控制器在全网中的序号 添加到探测包中路径记录字段；
(5e)将探测包中的类型字段标记为确认包类型；
(6)发送确认包：
(6a)域网络控制器判定确认包是否到达源主机所在网络，若是，执行步骤(6h)； 否则，执行步骤(6b)；
(6b)域网络控制器通过读取确认包中路径记录字段信息，得出确认包在本域网 络中的出口转发器信息；
(6c)在控制器中对应的出口转发器位置，判定是否有与确认包中路由请求标示 符相同的待拼接子路径，若有，则执行步骤(6d)；否则，执行步骤(6g)；
(6d)将确认包路径记录字段中控制器序号集合与保存在控制器的路径记录中控 制器序号集合做差集运算，得出后续子路径，域网络控制器将后续子路径和待拼接子 路径连接成新完整路径；
(6e)判定新完整路径的服务质量参数值是否小于或者等于确认包中要求的服务 质量参数值，若是，则执行步骤(6f)；否则，删除该新完整路径，继续执行步骤(6e)；
(6f)域网络控制器生成新完整路径对应的确认包；
(6g)依据确认包中路径记录字段的信息，域网络控制器发送确认包到上游域网 络控制器，执行步骤(6a)；
(6h)域网络控制器保存确认包中携带的路径信息，丢弃确认包；
(6i)当步骤(1d)启动的定时器到时后，执行步骤(7)；
(7)选取最优路径：
(7a)运用最优路径选择方法，域网络控制器从探测到的多条路径中选取最优路 径；
(7b)将最优路径对应确认包中的类型字段修改为选路类型，得到选路报文；
(7c)域网络控制器启动一个选路定时器，该选路定时器的时间设为路由请求信 息要求时延的2倍；
(8)判定域间路径是否满足约束：
对于域网络控制器和选路包中标记的下游域网络控制器之间的域间路径，判定其 服务质量参数值是否小于或者等于记录在域网络入口转发器中保存的域间路径服务 质量参数值，若是，则执行步骤(9)；否则，将选路报文中类型字段标记为失败类型， 执行步骤(11)；
(9)确认最优路径：
(9a)域网络控制器下发流表到域内最优路径经过的域网络转发器中，预留域内 最优路径和域间路径的带宽资源；
(9b)沿选路包路径记录字段中的路径，域网络控制器发送选路包到下游域网络 控制器；
(10)判定选路包是否到达目的主机所在网络，若是，则执行步骤(15)；否则， 执行步骤(8)；
(11)发送失败包；
沿失败包路径记录字段中的路径，域网络控制器反向发送该失败包到上游域网络 控制器；
(12)判定失败包是否到达源主机所在网络，若是，从域网络控制器中删除最优 路径和选路定时器，执行步骤(7)；否则，执行步骤(13)；
(13)释放预留资源：
(13a)域网络控制器删除下发到域内最优路径上域网络转发器中的流表，释放 域内最优路径和域间路径的带宽资源；
(13b)沿失败包路径记录字段中的路径，域网络控制器反向发送该失败包到上 游域网络控制器；
(14)判定失败报文是否到达源主机所在网络，若是，从域网络控制器中删除最 优路径和选路定时器，执行步骤(7)；否则，执行步骤(13)；
(15)探测过程结束：
当步骤(7c)启动的选路定时器到时后，选路成功。
与现有技术相比，本发明具有以下优点：
第一、本发明采用了探测包记录方法，克服了现有技术中探测包过多带来开销大 的问题，使得本发明具有在软件定义网络中，通过发送少量探测包就能够获取路径信 息的优点。
第二、本发明采用了计算探测包在域网络控制器上的等待时间Δt的方法，克服 了现有技术中路径重复探测的问题，使得本发明具有探测效率高的优点。
第三、本发明采用了源路由策略和分布式路由策略相结合的方法，克服了现有 技术中域网络控制器收集全网拓扑信息，带来网络开销大的问题，使得本发明具有 网络开销小的优点。
第四、本发明采用了域内直接计算和域间探测相结合的方法，克服了现有技术 中不能解决大规模软件定义网络中寻中满足多个服务质量参数约束的路径问题，使 得本发明具有能够在软件定义网络中，寻找满足多个服务质量参数约束最优路径的 优点。
附图说明
图1是本发明的流程图；
图2是本发明的实施例图。
具体实施方式
下面结合附图对本发明作进一步详细描述。
参照附图1，本发明的具体步骤详细描述如下。
步骤1，初始化探测报文。
(1a)域网络控制器接受源主机发送的路由请求，路由请求信息中包括源主机地 址、目的主机地址、时延、带宽、丢包率和抖动的服务质量参数值。
(1b)将探测包中路由请求服务质量值字段和域内约束值字段，均标记为服务质 量参数值。
(1c)将探测包中的类型字段标记为探测包类型；将路由请求标示符字段标记为 源主机地址、目的主机地址和控制器生成的随机数；将路径记录字段和子路径服务质 量累加值字段标记为零。
(1d)域网络控制器启动定时器，将定时器的时间值设为路由请求信息要求时延 的2倍。
步骤2，生成探测报文。
(2a)域网络控制器运行启发式基于多约束的最优路径H_MCOP的算法，将探 测包中域内约束值字段内容作为该算法的参数，得到从域网络入口转发器到所有域网 络边界出口转发器之间的域内最优路径。
启发式基于多约束的最优路径H_MCOP算法是一种能解决NP完全问题的启发 式算法。它首先假设网络的实际状态对于每个节点都是可以利用的，然后利用每个节 点的信息来计算点到点的路径。
设p为一条从源节点到目的节点的路径，称
其中λ≥1，c1、c2…cK是给定的K个约束值，他们存储在探测包中域内约束值 字段中，w1(p)、w2(p)…wK(p)是路径p对应的K个服务质量参数值，为非线性代 价函数。
每个域网络转发器的节点信息主要包括：
s：源节点
t：目的节点
r[u]、从u到t的最短路径
RK[u]、从t到u的每个权重的累积值
πr[u]、从t到u在节点u以前所选的所有点
g[u]、从s到u非线性函数的值
Gk[u]、从s到u每个权重代价函数的累积值
πg[u]、从s到u在节点u以前所选的所有点
c[u]、从s到u代价函数。
在以上域网络转发器节点信息形成后，算法开始运行，算法主要由两部分组成。 这两个部分也可以说成是两个方向，即正向和反向。
第一部分：这部分是有t到s的反向寻路过程。这部分主要是以λ＝1时的非线性 函数为度量函数来寻找最短路径，应用的是Dijkstra算法。当λ＝1时，若能找到最短 路径，则可能存在满足多约束条件的路径，但是并不一定存在，若不能找到最短路径， 则一定不存在满足多约束条件的路径，更谈不上最优路径。所以，这部分寻路过程目 的并不是寻找最理想的路径，而是要检测出在网络中有么有符合多约束条件的路径存 在。这部分应用的节点信息包括r[u]、RK[u]和πr[u]。
第二部分：这部分是由s到t的正向寻路过程。这部分主要是以λ＞1时的非线性 函数为度量来寻找最短路径，应用的也是最基本的Dijkstra算法。这部分寻路过程就 是在反向寻路成功后，寻找理想路径的寻路过程。若寻到理想路径则返回该路径，若 没有寻找理想路径，则这个网络中没有可行性路径。寻路失败。这部分应用的节点信 息包括g[u]、Gk[u]、πg[u]和c[u]。
该算法按下列步骤进行：
第一步，从目的主机到源主机的反向寻路，将系数λ＝1时的非线性函数作为迪 杰斯特拉Dijkstra的参数，通过迪杰斯特拉Dijkstra算法，得出反向寻路最短路径。
第二步，判定反向寻路最短路径的线性函数值是否大于服务质量参数的个数，若 是，返回给域控制器一个寻路失败信息，执行第五步；否则，执行第三步。
第三步，从源主机到目的主机的正向寻路，将系数λ＞1时的非线性函数作为迪 杰斯特拉Dijkstra的参数，通过迪杰斯特拉Dijkstra算法，得出正向寻路最短路径。
第四步，判定正向寻路最短路径的服务质量参数是否小于或者等于路径请求信息 中的服务质量参数值，若是，则返回给域控制器正向寻路最短路径的信息；否则，返 回给域控制器一个寻路失败信息。
第五步，结束启发式基于多约束的最优路径H_MCOP算法。
(2b)将域内最优路径和与出口转发器相连的域间路径连接成新子路径。
(2c)判定新子路径的服务质量参数和探测包中子路径服务质量累加值字段的累 加和是否小于探测包要求的服务质量参数值，若是，则执行步骤(2d)；否则，删除 该新子路径，执行步骤(2g)。
(2d)运用探测包记录方法，在域网络控制器中记录探测包信息，探测包记录方 法按下列步骤进行。
第一步，在域网络控制器的信息表中找见探测包的入口转发器位置。
第二步，根据探测包中内容，在入口转发器位置记录以下信息：入口转发器号、 路由请求标示符、路径记录、子路径服务质量参数值、域内路径记录、下一跳和域间 路径服务质量参数值。
第三步，再在入口转发器位置的路径记录字段，添加本网络中域控制器的序号。
(2e)在域网络控制器中预留域内网络带宽资源，其预留时间设为路由请求信息 要求时延的2倍。
(2f)域网络控制器生成一个探测包副本，运用探测包修改方法，修改探测包的 内容，探测包修改方法按下列步骤进行：
第一步，将探测包中子路径服务质量累加值字段标记为新子路径的服务质量参数 和探测包中子路径服务质量累加值字段的累加和。
第二步，将探测包中域内约束值字段标记为原有值与新子路径的服务质量参数 之差。
第三步，将域网络控制器在全网中的序号添加到探测包中路径记录字段。
(2g)判定所有新子路径是否都处理完毕，若是，则执行步骤3；否则，执行步 骤(2c)。
步骤3，探测路径。
(3a)计算探测包在域网络控制器上的等待时间Δt。
一对源和目的控制器间任意两条不重合路径，如果探测包在探测路径上传输时 间加上在控制器节点中停留时间与实际数据链路的合成服务质量参数值成固定比例 c，则最先到目的网络的探测包中携带的路径信息是最有可能满足路由请求约束。因 为该路径信息的合成服务质量参数值最小。在计算这个等待时间Δt时，将n个服务 质量加性参数d1(p)、d2(p)…dn(p)合成一个值，记为d(p)。
其中，D1、D2…Dn为路由请求的n个约束服务质量参数值。例如，有两条从 源网络控制器s到目的网络控制器t的不重合路径，p1(s,...,i,...,t)，p2(s,...,k,...,t)， d(p1)＜d(p2),如果则t1＜t2。在需要确定探测包在控制器中 额外停留时间Δt和比例c，其中tij是入口转发器到控制器i的时间、包 在控制器i中正常处理时间、控制器i到出口转发的器时间和到控制器j域间链路传 播时延的累加值，dij是对应于前者的入口转发器到出口转发器以及域间链路的合成 服务质量参数。在选择Δt和比例c，Δt＞0,如果能找见合适的c值，则一定 能保证Δt＞0。c值的计算如下：由于网络建立之初，网络中两相邻控制器之间的传 输时间在网络设计之时就可以确定的，而两转发器之间最小合成服务质量参数值也 可以计算出来的。所以每个域网络控制器先计算出本域的c值，再和相邻控制器交 互这些信息并且取较大的c值，待收敛后，每个控制器都取得同一个c值。然后再利 用Δt＝c*dij-tij计算出在该控制器中的等待时间Δt，该控制器中的等待时间就是该 标示符类型探测包在沿路径转发出去之前需要在该控制器中等待的时间。
等待时间Δt按照下列步骤得到。
第一步，按照下式，计算域网络控制器常数c值：
其中，c表示域网络控制器常数，txy表示域网络入口转发器x到域网络控制器传 播时延、探测包在域网络控制器处理时间、域网络控制器到域网络出口转发器y传播 时延和与域网络出口转发器相连域间链路传播时延的累加值，dxy表示域网络入口转 发器x到域网络出口转发器y的最短路径和域间链路的合成服务质量参数值。
第二步，域网络控制器与其他域网络控制器通过发送消息的方式，获得对方的域 网络控制器常数c值。
第三步，每个域网络控制器域，从网络控制器常数c值中选择其最大值作为最终 域网络控制器的常数c1值。
第四步，按照下式，计算探测包等待时间Δt值：
Δt＝c1*dij-tij
其中，Δt表示探测包等待时间，c1表示最终域网络控制器的常数，dij表示域网 络入口转发器到域网络出口转发器的最优路径以及域间链路的合成服务质量参数值， tij表示域网络入口转发器到域网络控制器i传播时延、探测包在域网络控制器i中正 常处理时间、域网络控制器i到域网络出口转发器传播时延和与域网络控制器j相连 域间链路传播时延的累加值。
(3b)域网络控制器在等待时间Δt过后，将探测包发送到探测包标记的网络中。
(3c)判定域网络入口转发器之前是否收到过同样路由请求标示符的探测包，若 是，则执行步骤(3d)；否则，执行步骤4。
(3d)运用探测包记录方法，将探测包信息记录到域网络控制器中，作为待拼接 子路径，丢弃探测包，继续执行步骤(3c)，其中探测包记录方法和步骤(2d)中一 样。
步骤4，域网络控制器判断探测包是否到达目的主机所在网络，若是，则执行步 骤5；否则，转向步骤2。
步骤5，生成完整路径。
(5a)域网络控制器通过启发式基于多约束的最优路径H_MCOP的算法，得到 域网络入口转发器到域网络出口转发器之间的域内最优路径，其中启发式基于多约束 的最优路径H_MCOP的算法和步骤(2a)中的一样。
(5b)判定域内最优路径的服务质量参数和探测包中子路径服务质量累加值字段 的累加和是否小于探测包要求的服务质量参数，若是，则执行步骤(5c)；否则，丢 弃探测包，继续执行步骤(5a)。
(5c)运用探测包记录方法，在域网络控制器中记录探测包信息，其中探测包记 录方法和步骤(2d)中一样。
(5d)将探测包中子路径服务质量累加值字段标记为域内最优路径的服务质量参 数和探测包中子路径服务质量累加值字段的累加和，将域网络控制器在全网中的序号 添加到探测包中路径记录字段。
(5e)将探测包中的类型字段标记为确认包类型。
步骤6，发送确认包。
(6a)域网络控制器判定确认包是否到达源主机所在网络，若是，执行步骤(6h)； 否则，执行步骤(6b)。
(6b)域网络控制器通过读取确认包中路径记录字段信息，得出确认包在本域网 络中的出口转发器信息。
(6c)在控制器中对应的出口转发器位置，判定是否有与确认包中路由请求标示 符相同的待拼接子路径，若有，则执行步骤(6d)；否则，执行步骤(6g)。
(6d)将确认包路径记录字段中控制器序号集合与保存在控制器的路径记录中控 制器序号集合做差集运算，得出后续子路径，域网络控制器将后续子路径和待拼接子 路径连接成新完整路径。
(6e)判定新完整路径的服务质量参数值是否小于或者等于确认包中要求的服务 质量参数值，若是，则执行步骤(6f)；否则，删除该新完整路径，继续执行步骤(6e)。
(6f)域网络控制器生成新完整路径对应的确认包。
(6g)依据确认包中路径记录字段的信息，域网络控制器发送确认包到上游域网 络控制器，执行步骤(6a)。
(6h)域网络控制器保存确认包中携带的路径信息，丢弃确认包。
(6i)当步骤(1d)启动的定时器到时后，执行步骤7。
步骤7，选取最优路径。
(7a)运用最优路径选择方法，域网络控制器从探测到的多条路径中选取最优路 径。
(7b)将最优路径对应确认包中的类型字段修改为选路类型，得到选路报文。
(7c)域网络控制器启动一个选路定时器，该选路定时器的时间设为路由请求信 息要求时延的2倍。
步骤8，判定域间路径是否满足约束。
对于域网络控制器和选路包中标记的下游域网络控制器之间的域间路径，判定其 服务质量参数值是否小于或者等于记录在域网络入口转发器中保存的域间路径服务 质量参数值，若是，则执行步骤9；否则，将选路报文中类型字段标记为失败类型， 执行步骤11。
步骤9，确认最优路径。
域网络控制器下发流表到域内最优路径经过的域网络转发器中，预留域内最优路 径和域间路径的带宽资源。
沿选路包路径记录字段中的路径，域网络控制器发送选路包到下游域网络控制 器。
步骤10，判定选路包是否到达目的主机所在网络，若是，则执行步骤15；否则， 执行步骤8。
步骤11，发送失败包。
沿失败包路径记录字段中的路径，域网络控制器反向发送该失败包到上游域网络 控制器。
步骤12，判定失败包是否到达源主机所在网络，若是，从域网络控制器中删除 最优路径和选路定时器，执行步骤7；否则，执行步骤13。
步骤13，释放预留资源。
域网络控制器删除下发到域内最优路径上域网络转发器中的流表，释放域内最优 路径和域间路径的带宽资源。
沿失败包路径记录字段中的路径，域网络控制器反向发送该失败包到上游域网络 控制器。
步骤14，判定失败报文是否到达源主机所在网络，若是，从域网络控制器中删 除最优路径和选路定时器，执行步骤7；否则，执行步骤13。
步骤15，探测过程结束。
当步骤(7c)启动的选路定时器到时后，选路成功。
下面结合实施例对本发明的寻找路径过程进行详细说明。
实施例参照图2。图2中的CE1、CE2…CE7分别标记为各个软件定义网络中的 控制器，s和t分别标记为源主机和目的主机，线段标记为链路，线段上数字标记为 该链路的服务质量参数值，小空心圆圈标记为转发器，小空心圆圈中数字标记为转发 器的序号。
步骤1，初始化探测报文。
在CE1控制器控制的软件定义网络中，源主机s经过与其直连的转发器1向控制 器CE1发送一个路由请求消息，路由请求信息中包括源主机地址ip1、目的主机地址 ip2和服务质量参数值(19,17)。其中服务质量参数分别是时延和抖动。为了便于说明， 故仅考虑两个可加性服务质量参数且取值均为正整数的情况。对于带宽，控制器可以 在收到探测包后，立即检测链路可用带宽是否满足约束；对于丢包率，则可以采用对 数法，使其变成加性服务质量参数来考虑。所以，该方法可以应用于多个服务质量参 数的路由问题。控制器CE1接受源主机发送的路由请求后，生成一个探测报文，其中 类型字段标记为探测类型；路由请求标示符字段标记为一个三元组<ip1,ip2,id1>，其 中id1是系统随机生成数；路径记录字段和子路径服务质量累加值字段均标记为零； 路由请求服务质量值字段和域内约束值字段均标记为(19,17)。控制器CE1启动一个路 由请求标示符为<ip1,ip2,id1>的定时器，初值是该源端请求时延的2倍，即2*19＝38。
步骤2，生成探测报文。
控制器CE1运用启发式基于多约束的最优路径H_MCOP的算法，以探测包中的 域内约束字段(19,17)为算法参数，得出入口转发器1到所有出口转发器的最优路径和 服务质量参数值。因为到转发器3的情况和到转发器2的情况类似，故只对到转发器 2的路径加以说明。得出的到转发器2的域内最优路径为转发器1、转发器2，记为 1-2。域内最优路径的服务质量值为(2,3)。由于边界转发器2连接了CE2控制器的网 络和CE3控制器的网络，故分别判定域内服务质量参数为(2,3)和域间(1,1)、(6,6)累加 后是否小于或者等于路由请求服务质量参数值，累加后子路径服务质量参数分别为 (3,4)与(8,9)。均小于路由请求要求的(19,17)，故两个新子路径都满足约束条件。
对于第一条新子路径而言，运行探测包记录方法，控制器CE1中记录探测包信息， 记录如下表：
对于第二条新子路径的也在控制器中记录探测包中信息，如上表所示。控制器 CE1预留域内链路1-2上的网络带宽资源，其预留时间设为路由请求信息要求时延的 2倍。
对于到控制器CE2的新子路径，控制器CE1生成一个探测包副本，运用探测包修 改方法，修改探测包中以下字段，将路径记录字段标记为CE1，子路径服务质量累加 值字段标记为(3,4)，域内约束值字段标记为(16,13)。
对于到控制器CE3的新子路径，控制器CE1也生成一个探测包副本，运用探测包 修改方法，修改探测包中以下字段，将路径记录字段标记为CE1，子路径服务质量累 加值字段标记为(8,9)，域内约束值字段标记为(11,8)。
步骤3，探测路径。
在CE1控制器的网络中，控制器CE1分别计算两个探测包需要在控制器中的等 待时间Δt1和Δt2。由于每个控制器的常数c值是已知的，故只需知道路径合成度量 值就可以计算出等待时间Δt。由
对于先发送出去到控制器CE2中的探测包而言，控制器CE2判定入口转发器3 之前没有收到过过标识符为<ip1,ip2,id1>的探测包，执行步骤4。
步骤4，CE2控制器判定探测包没有到达目的主机所在网络，进而在CE2控制器 中继续执行步骤2。各个域网络控制器处理过程如下。
在控制器CE2控制的软件定义网络中，控制器CE2运行启发式基于多约束的最 优路径H_MCOP算法，得出从该域中转发器3到其他所有边界转发器的最优路径。由 于到其它出口转发器的情况与到转发器4的情况类似，故只说明到转发器4的情况。 计算出的域内最优路径为转发器3-1-2-4。其服务质量值为(4,3)。把该段路径(4,3)和 其相应的域间路径(2,4)以及探测包中子路径服务质量累加值字段相加，结果为(9,11)。 小于路由请求(19,17)，故满足约束。然后控制器CE2运用探测包记录方法，在域网络 控制器中记录探测包信息，同时预留域内链路3-1-2-4的带宽资源。控制器CE2生成 一个探测包副本，运用探测包修改方法，修改探测包的内容如下：将探测包中路径记 录字段标记为CE1、CE2；将子路径服务质量值字段标记为(9,11)；将域内约束值字 段标记为(10,6)；计算在控制器中等待的时间，最后发送到CE4控制器的网络中，等 待时间的计算方法类似于CE1网络中的计算。故不再作说明。
在控制器CE3控制的软件定义网络中，处理类似于控制器CE2控制的软件定义 网络。处理结果为：控制器CE3启发式基于多约束的最优路径H_MCOP的算法，得出 从转发器1到所有边界转发器的最优路径，只说明到边界转发器3的情况，其他边界 转发器的情况与其类似。其域内最优路径为转发器1-2-3，服务质量值为(3,2)，因为 此时的边界转发器3可以到两个网络，故把探测包中的子路径服务质量累加值字段 (8,9)、域内服务质量值(3,2)和域间服务质量值(3,2)、(1,2)分别累加，结果为(14,13)与 (12,13)。均小于约束(19,17)。对于前者，即新子路径服务质量参数值为(14,13)。控制 器CE3运用探测包记录方法，在控制器中记录探测包中信息，同时预留域内链路1-2-3 的带宽资源。控制器CE3生成一个探测包副本，运用探测包修改方法，修改探测包的 内容如下：将路径记录字段标记为CE1、CE3；将子路径服务质量累加值字段标记为 (14,13)；将域内约束值字段标记为(5,4)。计算在控制器中等待的时间，最后发送到 CE4控制器的网络中，等待时间的计算方法类似于CE1网络中的计算。故不再作说明。 对于后者，即新子路径服务质量参数值为(12,13)。处理类似前者，故也不再说明。
在控制器CE4控制的软件定义网络中，在入口转发器1处将收到两个探测包，其 包内的子路径服务质量累加值字段的值分别为(9,11)与(14,13)。所以前者的探测包先 到，对先到的探测包的处理类似于控制器CE2控制的软件定义网络。故不再说明。对 后者探测包的处理过程如下：判定入口转发器1之前收到过路由请求标示符为 <ip1,ip2,id1>的探测包，控制器CE4运用探测包记录方法，将探测包信息记录到域网 络控制器中，作为待拼接子路径，丢弃探测包。
在控制器CE6、CE7控制的软件定义网络中，其处理流程类似于上面。故不再 重复说明。
步骤5，生成完整路径。
在控制器CE5控制的软件定义网络中，有两个入口边界转发器。对于边界入口转 发器1而言，其要收到三个路由请求标示符为<ip1,ip2,id1>的探测包，这些探测包中 子路径服务质量累加值字段分别为(12,16)、(11,12)、(15,15)。可知中间这个探测包最 先到达，其他两个探测包的处理都是在控制器中记录子路径信息，作为待拼接子路径， 然后丢弃探测包。对中间这个探测包的处理如下：利用启发式基于多约束的最优路径 H_MCOP的算法，得出从入口转发器1到目的转发器3的最优路径为转发器1-3，其服 务质量值为(2,1)。然后把包中的子路径服务质量累加值字段(11,12)和该(2,1)累加，结 果为(13,13)。小于约束(19,17)，所以在控制器中记录相关信息，同时修改探测中的路 径记录字段为CE1、CE2、CE4、CE5，子路径服务质量累加值字段为(13,13)。最后 修改该包类型字段为确认类型。
对于边界入口转发器2而言，情况比较简单，其服务质量累加值最后为(11,18)， 不满足约束(19,17)。故丢弃该包。
步骤6，发送确认包。
控制器CE5判定确认包没有到达源主机所在的网络，查看入口转发器1处记录的 子路径信息，拼接成新的两条完整路径，其累加后的服务质量值分别为(14,17)与 (17,16)，均满足约束。故生成相应的两个确认包，依据确认包中路径记录字段的信息， 控制器CE5发送确认包到上游域网络控制器，上游网络控制器有CE4、CE6和CE7。 由于其他上游网络控制器的处理过程与控制器CE4控制的软件定义网络中的处理过 程类似，故只对控制器CE4控制的软件定义网络中的处理过程说明。
在控制器CE4控制的软件定义网络中，当控制器CE4收到来自于控制器CE5的 确认包后，判定确认包还没有到达源主机所在网络，再查看确认包的出口转发器1中 有待拼接的子路径，其路径p为CE1、CE3、CE4。子路径服务质量值为(14,13)。同 时在控制器中也可看出确认包中携带路径的子路径在该控制器出的子路径服务质量 值为(9,11)，而确认包中的路径服务质量累加值为(14,17)，所以后续子路径的务质量 值为(5,6)，拼接后的路径的服务质量值为(14,13)累加上(5,6)，即为(19,19)。由于其不 能满足约束(19,17)，故丢弃该拼接后形成的完整路径。对于来自控制器CE5的确认包。 依据确认包中路径记录字段的信息，控制器CE4继续发送确认包到上游域网络。
而控制器CE2、CE7和CE6控制的软件定义网络中，对确认包的处理类型，都 是没有子路径信息，故都是继续沿确认包中的路径反向发送。直到源控制器CE1。
在控制器CE1控制器的软件定义网络中，控制器CE1收到确认包后，就把包中携 带的路径信息保存在该控制器中，丢弃确认包。控制器CE1在定时器到时间后，执行 步骤7。
步骤7，选取最优路径。
源主机所在域网络中，控制器CE1把收到的标示符为<ip1,ip2,id1>的路径信息按 其跨域的软件定义网络数目来升序排列，源控制器CE1收到了3个确认包，即3条路 径。其路径记录排序后分别为：路径CE1、CE6、CE5，其服务质量值为(13,13)；路 径CE1、CE2、CE4、CE5，其服务质量值为(14,17)；路径CE1、CE3、CE7、CE5， 其服务质量值为(17,16)。选取跨域软件定义网络数目最小的路径，即路径CE1、CE6、 CE5，其服务质量值为(13,13)。生成该路径对应选路包。
控制器CE1启动一个选路定时器，该选路定时器的时间设为路由请求信息要求时 延的2倍。
步骤8，判定域间路径是否满足约束。
对于域网络控制器CE1和选路包中标记的下游域网络控制器CE6之间的域间路 径，判定其服务质量参数值小于记录在域网络入口转发器中保存的域间路径服务质量 参数值。执行步骤9。
步骤9，确认最优路径。
控制器CE1下发流表到域内最优路径经过的域网络转发器1、3中，预留域内最 优路径和域间路径的带宽资源；沿选路包路径记录字段中的路径，控制器CE1发送选 路包到下游域网络控制器CE6；
步骤10，判定选路包没有到达目的主机所在网络。继续执行步骤8，直到选路包 到达控制器CE5。
步骤11，探测过程结束。
在标示符为<ip1,ip2,id1>的选路定时器到时后，则选路成功。之后各个域网络中 的转发器就可以根据流表来转发相应的流。
由于实施例图中数据的特殊性，故权利要求书中的步骤11、12、13和14,，没 有被执行。
机译： 用于使用具有非符号边界的掩码搜索树并在大规模并行路由器中泛洪默认路由的设备和方法
机译： 用于使用具有非符号边界的掩码搜索树并在大规模并行路由器中泛洪默认路由的设备和方法
机译： 软件定义网络中的路由控制方法及OpenFlow控制器
