MPLS流量工程,显式路径,LSP的路由选择

MPLS流量工程显式路径LSP的路由选择1、背景介绍2、目前流行的一些路由算法特征3、本文选择的算法机制4、实验分析5、总结20142821201461403班孙守刚1、背景介绍MPLS(Multi_ProtocolLabelSwitch)为多协议标签交换，是下一代网络用于骨干网的一种先进的转发机制；该机制引入标记交换的概念，每个节点收到数据包后不再需要对包头中的地址进行分析和确定路由，而是通过预先建立的标记交换表进行选路和标记交换。MPLS主要设计来解决网路问题，如网路速度，可扩展性，服务质量（QoS）管理和流量工程，同时也为下一代IP中枢网络解决宽带管理及服务请求问题。MPLS的价值在于其能够在一个无连接的网络中引入连接模式的特性，即先把选路和转发分开，生成一个标记交换面，由标记来规定一个分组通过网络的路径，分组在转发至后面多跳之前被贴上标记，所有转发都按标记进行。MPLS提供更好的端到端服务，特别是它可以根据网络的流量特性（如网络拥塞或服务质量要求）来规定转发路径，故MPLS能减小网络复杂性，从而使网络成本降低50%。MPLS的基本工作过程：LSP(LabelSwitchPath)标记交换路径，是业务流经过网络的节点和次序列表；是MPLS预先通过某种策略或选路算法确定的；可以看作一个转发等价类在MPLS网络中经过的路径；LSP在功能上是从入口到出口的一个单向路径。标签交换路径LSP分为静态LSP和动态LSP两种，静态LSP由管理员手工配置，动态LSP则利用路由协议和标签发布协议动态产生。LSP隧道的建立：在Ingress上依据所配置的约束，通过特定的路由算法计算得出LSP隧道所要经过的路径；IngressLSR产生携带相应带宽预留信息和路径信息的Path消息，依据计算的路径向EgressLSR方向发送，Path消息经过的LSR，都依据Path消息生成路径状态；EgressLSR收到Path消息后，产生携带预留信息和标签的Resv消息，沿Path消息发送的相反路径逐跳返回IngressLSR，同时，Resv消息在沿途的LSR上预留资源，并生成预留状态，生成标签交换路径；当IngressLSR收到Resv消息时，LSP建立成功。流量工程：传统路由问题：路由器根据传统路由协议计算出的最短路径转发流量，即使某条路径发生拥塞，也不会将流量切换到其他的路径上，如上图所示：如图所示,假设每条链路的Metric值相同，则从RouterA到RouterH的最短路径为RouterA－RouterC－RouterG－RouterF－RouterH；尽管存在RouterC－RouterD－RouterE－RouterF－RouterH这条路径，但是流量转发只会从最短路径RouterA－RouterC－RouterG－RouterF－RouterH上经过，这样就有可能形成一条路径RouterA－RouterC－RouterG－RouterF－RouterH过载，一条链路RouterA－RouterC－RouterD－RouterE－RouterF－RouterH闲置的现象。在网络流量比较小的情况下，该问题不是很严重，但是随着网络多媒体的发展，传统的最短路径优先的路由问题暴露出来。流量工程的解决方式：通过流量工程，可以精确地控制流量流经的路径，从而可以避开拥塞的节点，解决一部分路径过载，另一部路径空闲的问题，使现有的带宽资源得到充分利用；如图所示，从RouterA到RouterH存在两条路径：RouterA－RouterC－RouterG－RouterF－RouterH和RouterA－RouterC－RouterD－RouterE－RouterF－RouterH，前者的带宽为40M，后者的带宽为100M。流量工程可以根据带宽等因素合理地分配流量，从而有效地避免链路拥塞；例如，RouterA到RouterH存在两种业务，流量分别为40M和70M，流量工程可以把前者分配到带宽为40M的路径上，将后者分配到带宽为100M的路径上。由于MPLS流量工程的目标是优化网络资源和保证网络服务质量(QoS)，显式LSP的建立可以对IP实时性业务提供服务质量支持，并且能够通过对LSP的合理部署，优化网络资源，提高网络性能，故，显式路径LSP的选路问题成为流量工程的关键性问题。2、目前流行的一些路由算法特征如何建立具有带宽保证的显式路径问题？带宽保证：如果网络中两节点间的不同业务要求不同的带宽保证，可以通过部署到同一目的地的多条LSP隧道，实现为每种业务提供独立的带宽保证。从Ingress到Egress存在两条链路，在低延迟链路上建立Tunnel2，在另一链路上建立Tunnel1；在Ingress和Egress之间存在数据和语音两种业务，从Ingress到Egress上的语音业务流量通过Tunnel2上传输，在Tunnel1上实现数据流量的传输；通过建立LSP隧道分别为两种业务提供服务，为语音业务提供带宽保证，让数据业务通过其他路径转发，避免数据与语音经过相同的路径造成拥塞。目前流行的算法有以下几类：约束最短路径优先(CSPF)：通过特定的约束参数如带宽需求、最大跳转数等计算网络的最短路径，该方法只能保证单个业务的服务质量，不能从全网范围内考虑网络流量分配和性能优化问题。最宽最短路径(WSP)：选择跳数最少的最短可行路径，同时保证可用带宽最多；该方法利用链路状态信息和辅助的容量信息，但其只关心单条链路的当前可用带宽和对路由业务的带宽需求，不管其对其他节点对的业务影响，使得网络容易产生瓶颈效应。最小干扰路由(MIRA)：在源和目的节点对之间选择一条对未来业务产生最小干扰的路径，引入关键链路概念，该方法的目标是选择包含尽可能少的关键链路的路径；该方法在建立每条路由时，都要采用最大流计算所有节点对之间的最大流，从而确定关键链路，使得计算复杂度大大增加；该方法没有考虑路由跳数和链路的影响，使得建立LSP出现问题。3、本文选择的算法机制POOA(PathOptimalOrderingAlgorithm)：路径最优排序算法，通过计算最佳路由优先顺序来确定最佳转发路径。该方法不仅仅努力寻找最佳路径，而是按照一定的原则对所有可行路径进行排序，优先选择排在前面的路径。算法特征：（1）学习机制LM(LearningMachine)路径的优先性：为LSP隧道建立优先级，并保持优先级，将优先级数字化，也即赋予其一定的值，数值越大，其优先级越高；当需要建立多个LSP隧道的情况下，建立优先级高的LSP隧道优先占有资源、优先建立；当带宽等资源不够时，保持优先级低的、已建立的LSP隧道的带宽资源可能被一个建立优先级高的并且资源不够的LSP隧道抢占。本算法的学习机制也就是建立一个多条路径优先性排序的过程。学习机制根据随机网络环境提供的信息自动学习，为任意节点对之间的每一条可行路径赋予一个值来决定该路径的优先性；LM按照某种原则进行路径选择，同时增加该路径的选择概率，更新排序。入节点出节点r条路径A={a1,a2,…,ar}r条路径奖赏值S={s1,s2,…,sr}根据环境信息按照反馈原则选择路径，被选中的路径相应奖赏值增加，然后按照值对路径排序，在任意时刻t，LM输出为r条路径对应的排序Π(t)，当t→∞时，Π(t)收敛至Π∗，Π∗即为LM通过自动学习机制得到的最佳顺序。（2）关键链路KeyLink该算法在收敛过程中主要基于关键链路的概念，关键链路是指网络中某些特定的链路，当在该链路上建立LSP预留带宽时，会导致某个或多个入口、出口节点对之间的最大流减少；也即当建立显式路径时会影响链路带宽，那么就无法满足建立具有带宽保证的显式路径问题这一目标；算法引入关键链路，目的是最大程度上避开那些负载较重的关键链路，减少未来路由请求被拒绝的可能。如图所示，按照最短时延、最短路径算法，链路：RouterA－RouterC－RouterE－RouterG将可能出现过载现象，建立显式LSP路径就应尽量避开该特定的链路；其实质是对关键节点或链路进行保护，实现对通过关键节点的流量的保护目的。算法中关键链路的确定基于两个概念：最大流、最小割；根据最大流-最小割定理，任意一个流网络的最大流量等于该网络的最小割的容量；方法建立的LSP应避免经过关键链路。（3）反馈机制根据算法学习机制，需要一种环境反馈机制来推断路径的最佳顺序，该机制基于环境的一些关键的信息，如路径所含关键链路的数量和路径最大剩余带宽；易知路径所含关键链路越少，路径优先值越高，剩余带宽表示该路径可以提供给数据流的最大带宽，带宽越大，表示该路径通信能力越强，那么该路径优先值越高。算法给出环境反馈公式：β(i)=R(i)C(i)R(i)表示路径最大剩余带宽，C(i)表示路径所含关键链路的数量，β(i)表示环境反馈给该路径的优先值。该公式的目的是最小化路径所含关键链路的数量，同时保证所选路径具有相当的剩余带宽，提供给数据流使用。算法步骤：离线阶段：在线阶段：4、实验分析使用网络拓扑如图所示IngressEgressEgressIngressIngressLSR路由LSR路由LSR路由在3个入口节点分别建立多个LSP请求，每个请求的带宽为400KB，同时模拟CSPF和MIRA算法，比较在建立LSP时的请求拒绝数目：上图中，在第十个请求后，三者都出现了拒绝请求的行为，但是拒绝次数最少的是POOA算法，这说明在同等业务流的情况下，POOA算法能够选出合适路径，使得更多的路由负载均衡的通过网络，提高了网络资源的利用率。5、总结针对MPLS流量工程网络中的路径选择问题，有带宽保证的路径最优排序算法POOA考虑关键链路和链路剩余带宽的影响，充分提高了网络资源的利用率，并且引入自动学习的机制更新路径优先值表，使得路由对随机环境有了更好的适应力。