流量工程技术介绍

高级计算机网络课程讲义,Traffic Engineering 流量工程技术,内容,概述 传统集成方法 策略路由 量度流量工程 ECMP 传统覆盖型网络 IP/ATM方法 MPLS流量工程系统 光网络流量工程,1.概述,概念 目标 方法 系统,传统路由的鱼型问题,图1所示的网络拓扑形状如一条鱼，节点G代表鱼头，A和B代表鱼尾，数据流从A和B流向G。 从鱼尾到鱼头有CDF和CEF两条路径。如果CDF比CEF短，则路由协议将选择CDF作为最短路由，A和B的业务流都将沿着CDF走，结果造成CDF负载沉重而CEF却被闲置的情形。 从这个例子我们可以发现，路由协议实际上很“傻”。,传统路由的弊端,基于目的地选路。 目的地址相同的数据包在被转发时，选择的下一跳也相同。所以，在路由表中，到达某目的地的路径只有一条（除非有多条成本相同的路径存在）。这样，网络中可用的其他链路就无法被利用起来，流量分布很难预测，实现均衡更不可能。 局部优化。 每个节点都独自选择路径，相互之间缺乏协调合作，故整个网络的路径选择无法得到优化。如在图1中，很多节点都独立地选择CDF，结果导致最短路径成了最拥挤的路径，较长的路径反而可能是更好的选择。为了优化网络总体资源利用率，路由决策应该从全局观点出发，把整个网络视为一个对象考虑。 在极端的情况下，最短路径算法还可能导致路由振荡。 假如某节点在某时刻根据路由协议选择CDF作为从C到F的最短路径，当所有业务流都经过时，该路径就变得异常拥塞，而另一条CEF则很空闲。下一次路由更新时，假如路由协议把CEF选为最短路径，则此改变就会将原来CDF的流量转移到CEF上。结果呢，情况倒置，CEF拥塞，而CDF却变得空闲。每次路由更新都会引起路径选择的翻转。,流量工程方法,当存在多条并行或备选路径时，就存在如何有效地使用集成的网络带宽的问题。这就是流量工程问题。 流量工程是一个强有力的工具，通过它可以在网络中不同的链路、路由器和交换机之间平衡业务负荷，使所有这些成分既不会过度使用，也不会未充分使用。这样，就可以有效利用整个网络所提供的带宽资源。 流量工程应当被看成是路由结构中的一个辅助部分 。是对路由功能的控制与优化，使流量以最有效的方式通过网络。,流量工程,A,B,C,D,Traffic engineering 是将流量向网络拓扑映射的过程,Demand,Network Topology,充分路由网络资源 利于实现QoS 网络流量分摊到多个链路，减少单点故障 满足策略需求,Traffic engineering key to optimizing cost/performance,流量工程方法,传统集成方法(Integrated) 策略路由 量度流量工程 ECMP 传统覆盖型网络(Overlay) IP/ATM方法 MPLS的流量工程,流量工程与网络工程,Network Engineering（网络规划） 构造静态拓扑的物理网络，保持一定时期稳定。 为长期的流量增长进行规划。为流量提供资源。 Establishing capacity where the traffic needs it. Traffic Engineering 是为了优化利用网络资源，是基于固定网络拓扑的优化。适应短期的流量波动。把流量放在有资源的对方。Putting traffic where the capacity is。 TE是下一次NE之前的有效补充措施，业务分布的优化。 TE 与网络规划的充足容量,流量工程与流量定向,Traffic Directing：选择信息服务器 根据客户的位置 服务器利用率 网络性能 属于应用层功能,流量工程 满足一定约束，包括QoS等：客户/ISP 网络利用最优化: ISP QoS路由 给定flow的QoS要求: 客户,流量工程的最优化目标,容量管理（capacity management ） 容量规划 路由控制 网络资源管理： link bandwidth, buffer space, computational resources. 流量管理（traffic management ） 节点流量控制功能： 流量调节，队列管理，调度 。 控制数据流经网络的路径，使不同报文或不同流访问不同的网络资源 。,流量工程的控制行为,控制模式 pro-active：采取预防措施，避免不良网络状态出现，或促成良好网络状态出现。 reactive：正确响应和适应发生的网络事件。 控制时间尺度 容量规划 路由控制 转发,2.集成方法,策略路由 量度流量工程 ECMP,2.1策略路由,192.1.1.12,s0 150.1.1.1 s1 151.1.1.1,s0 150.1.1.2 s1 151.1.1.2,e0 192.1.1.16,A,B,C,Access-list 1 permit 192.1.1.11 Access-list 2 permit 192.1.1.12 Router-map map1 permit 10 Match ip address 1 Set default interface serrial 0 Router-map map1 permit 20 Match ip address 2 Set default interface serrial 1,152.1.1.1,192.1.1.11,2.2基于量度的流量工程,基于量度设置的流量工程,在早期基于路由器的核心网中，流量工程技术是通过简单地使用路由量度值(Metric)来实现的。因为那时无论从路由器数量、链接数及业务流量来讲，Internet骨干网都是非常小的，所以，基于度量的控制在那时是足以胜任的。 同时，在万维网普遍流行之前，Internet拓扑层次也强制业务通过网络中较为确定的路径，不会产生临时的热点。,基于量度设置的流量工程的局限性,不具有可扩展性 当IP网络变得具有更多的链接时，这种情况下很难保证对网络某个部分量度的调整而不致在网络的其它部分引起问题。 不具有动态性 IGP并不发布类似于带宽可用性和业务特征等信息。这就意味着，当IGP计算其转发表时并不考虑网络上的业务负载。 无法负载平衡 业务不能在网络连接中平均分配，导致昂贵的网络资源未能被有效使用。一些链路可能发生阻塞的同时，另一些链路未被充分利用。,2.3ECMP：Equal-Cost Multipath,OSPF流量工程 :等价多路径 BGP流量工程 RIP也可实现 关键算法,OSPF等价多路径示例,多路径的影响,Variable Latencies 不同路径时延不同。 Packet 重排序对TCP的影响。 调试问题 ping 和 traceroute 更加不可靠。 组播路由问题 组播路由协议基于源或核构造转发树，避免环的方法是假设到达树根的下一跳唯一。 安全 多路径使下一跳不确定，网络DoS攻击相对困难。,主要算法,round-robin 最简单, the least recently used next-hop is chosen. Modulo-N Hash 对可标识流的报文字段进行操作，例如CRC值。 Hash-Threshold 首先对可标识流的报文字段进行hash操作。在hash函数的输出空间，不同的下一跳有不同的区间.。 Highest Random Weight (HRW) 路由器首先基于下一跳地址和可标识流的报文字段计算一个关键字 ， 选择关键字最大的下一跳。减少next-hop 增减对流的影响。,算法评价标准,性能（performance）：运行算法的计算代价。 平衡（Balancing）： 负载均衡。 偏离（ disruption ）：next-hop增减受影响的流。,算法disruption,区 3 删除： 1/4 of region 2 is now in region 1 1/2 (2/4) of region 3 is in region 2, 1/2 of region 3 is in region 4 ， 1/4 of region 4 is in region 5. Since each of the original regions represent 1/5 of the flows disruption = 1/5*(1/4 + 1/2 + 1/2 + 1/4) =3/10.,方法评价：小结,只是选择最短路径，在两个结点之间沿着最短路径上的路由器和链路可能发生了拥塞，而沿较长路径的路由器和链路却是空闲的。 link weight(metric)方法可能与最优解相差较远。 OSPF的等价多路径(ECMP)选项以及IS-IS在给多个最短路径分配负载时是有用的，但如果只存在一条最短路径，ECMP也是无能为力的。对于简单网络，可以让网络管理员手工配置链路，均匀地分发流量。但对于复杂网络，就只能使用自动化的流量工程了。,3.传统叠加方法,流量工程技术发展历史 90年代初使用T1/T3链路，路由器少，易于配置； 90年代中，ATM速率高，交换快，而路由器太慢，采用IP/ATM； 90年代末，路由器速率快，软件丰富，接口高速，采用MPLS；,3.1 IP/ATM叠加方法,IP/ATM ATM和IP定义不同的地址结构和路由协议。 ATM端点使用ATM地址和IP地址二者标识，ATM网络在核心。 在ATM网络，所有交换机使用ATM路由协议为IP分组选择路由，需要将IP地址映射为ATM地址。,叠加方法示例,A和C之间有四条路径：AGHC、AFHC、AGFHC、AFGHC。假设AGHC是从A到C的最短路径，则最短路径算法会选择AGHC，但覆盖方法比最短路径算法要灵活得多，它可以使用四条路径中的任意一条，并根据两个节点之间的流量做出选择。,叠加方法示例,IP/ATM流量工程优点,PVC覆盖的物理路径通常通过离线配置计算获得的,基于链接容量和历史业务参数配置的算法对其进行整体优化。在完成PVC结网的整体优化计算后，配置将被下载到路由器和ATM交换机以提供全闭合结网的逻辑拓扑。 一个基于ATM的核心网完全支持流量工程，因为它可以对PVC进行明确的路由。PVC的路由是通过在网络底层的物理拓扑上提供任意的虚拟拓扑来实现的，而在网络底层的物理拓扑上，可以通过对PVC进行路由以使业务分配到所有链路上去，使链路平均使用。这种实现避免了业务全部汇集到低花费路由上去，从而避免了链路的过分使用或未充分使用。 另外，由ATM交换机提供的每条PVC的统计信息，简化了监测用于优化PVC布局及管理的业务参数的过程。,IP over ATM模型的局限性,需要对两个不同的网络进行管理 ATM基础结构网和逻辑的IP覆盖网。 路由和流量工程分别在不同的系统上来完成 路由在路由器上执行，流量工程则在ATM交换机上完成，因此，将流量工程完全与路由集成在一起将是非常困难的。 ATM路由器接口未能跟上光学带宽的最新发展 IP协议在ATM结构上运行时，有20的ATM消耗用于组帧。OC-192浪费1.99G.最快622M，OC-48难生产。 配置难以自动更新 扩展性差 配置全闭合ATM PVC的网络将产生传统的“N2”问题。 5 router, 1 router added, 10 PVC created.,4.MPLS,MPLS概念 Label 封装 LSP建立 MPLS流量工程设施 MPLS流量工程方法,MPLS流量工程优点, 在上的节点或链路出现故障时，自动迂回或切换到新的上，保证网络业务的不中断。在IP over DWDM 系统中由于不再使用SDH传输设备，在出现光缆被割断时如何实现快速自愈恢复成为一个问题。利用MPLS有可在第三层实现快速自愈恢复（50 ms）。 流量工程（） 通过设置有关节点，通过流量的检测，决定有关流量分流的情况。根据如何决定分流链路的方法，可以区分松散、精确的指定。 虚拟专网（） 通过公用网络实现一个单位内部的网络。由于业务流量和网络覆盖的关系，早期网络通过专线来实现，缺乏灵活性。 由于的封装性，可以实现专线特性，保证安全性，而不需要实现复杂的加密算法，并具有极好的灵活性和可扩展性。 通过对设定有关特性来实现，并和有机结合。,MPLS 概念,LDP: Label Distribution Protocol LSP: Label Switched Path 入口出口节点之间的路径。 FEC: Forwarding Equivalence Class LSR: Label Switching Router LER: Label Edge Router,（1）Label 封装,ATM,FR,Ethernet,PPP,VPI,VCI,DLCI,“Shim Label”,L2,Label,MPLS intended to be “multi-protocol” below as well as above.,IP Payload,下层多样性,Ethernet,PPP (SONET, DS-3 etc.),ATM,Frame Relay,MPLS is “multiprotocol” below (link layer) as well as above (network layer) Provides for consistent operations, engineering across multiple technologies,MPLS positioned as end-to-end forwarding paradigm,（2）MPLS Domain,Ingress LSR,MPLS Domain,Core LSRs,Egress LSR,Congested link,Uncongested link,出口进行标准IP转发,入口加标记,（3）Forwarding Equivalence Classes,在路由器上处理行为相同的所有报文”.传统路由，报文在每跳指定FEC (i.e. L3 look-up) 到达特定接口的流量 符合分类标准的流量：IP地址，端口信息 具有一定优先级的流量 某接口以一定波长到达的流量 一天中的某段时间到达的流量,去往不同目的地的报文可以共享相同路径,LSR,LSR,LER,LER,LSP,STANDARD IP 转发,47.1,47.2,47.3,1,2,3,1,2,1,2,3,Destination based forwarding tables as built by OSPF, IS-IS, RIP, etc.,逐跳IP转发,47.1,47.2,47.3,1,2,3,1,2,1,2,3,IP 47.1.1.1,IP 47.1.1.1,IP 47.1.1.1,LSP（标记交换路径）是源到目标地址单向树的一部分。 LDP 基于IP的转发表各种树。,（4）LABEL SWITCHED PATH,MPLS 标签发布,47.1,47.2,47.3,1,2,3,1,2,1,2,3,3,标签交换路径 (LSP),47.1,47.2,47.3,1,2,3,1,2,1,2,3,3,ER( Explicit Routing) 建立 LSP 是一种 source routed. MPLS ER并不要求每个报文携带路由，TE有效。,A,B,C,显式路由LSP：ER-LSP,47.1,47.2,47.3,1,2,3,1,2,1,2,3,3,显式路由LSP：ER-LSP,叠加模型与集成模型,流量工程 光网络,叠加模型,集成模型,Ingress LSR,MPLS Domain,Core LSRs,Egress LSR,Congested link,Uncongested link,出口进行标准IP转发,入口加标记,Overlay vs. Integrated,Overlay ATM和IP定义不同的地址结构和路由协议。 ATM端点使用ATM地址和IP地址二者标识，ATM网络在核心。 在ATM网络，所有交换机使用ATM路由协议为IP分组选择路由，需要将IP地址映射为ATM地址。 Integrated 不使用第二层信令与路由协议，通过一定的机制使用IP协议控制第二层交换。 ATM端点只是使用IP地址标识，ATM网络使用的是现有的网络层路由协议(OSPF等)为IP分组选择路由，建立连接时不使用ATM信令。 增加了ATM交换机的复杂性，使ATM交换机看起来更像一个多协议路由器。,客户服务者（Overlay）模型,UNI,光网络路由,对等（peer）模型,光网络路由,4.MPLS与流量工程,MPLS概念 Label 封装 LSP建立 MPLS流量工程设施 MPLS流量工程方法,Traffic Trunk,LSP内部的同类聚合流。 流量主干向LSP映射称为实例化。 可以从一个LSP转移到其他LSP。 给定拓扑下最多Trunk是从每个入口到每个出口路由器每个流量类别一个： (N * (N-1) * C) trunks.,MPLS流量工程基本问题,通过LSP，将流量主干向物理网络拓扑映射： 将MPLS图向基本网络拓扑图映射。 物理网络拓扑图G = (V, E, c) V 为网络节点， E 为链路，参数c是 E和V 的容量或其他属性。 MPLS导出图 H = (U, F, d) U 为 LSR集合 ， F是LSP集合，参数d是F的需求或约束。,MPLS导出图,NE1,NE2,NE3,物理网络,MPLS流量工程设施,路由：Explicit Routing（ERLSP） 路由：Enhanced OSPF/IS-IS/BGP 增加 LSA types 传递流量工程信息 Extra metrics 路由计算方法修改 提供信息，构造TE拓扑。 信令 协议：TE-RSVP ， CR-LDP,1) 了解链路属性的拓扑数据库.,2) 标记分发协议,z,m,y,x,MPLS流量工程设施,流量工程信息,节点TE参数 对流量设置优先级 traffic prioritization, 配置接口端口 ability to provision bandwidth on interfaces, 支持 CSPF算法 对 automatic protection switching 的支持等。 链路TE参数 可用带宽 可靠性 color assigned to the link, 带宽使用代价 Shared Risk Link Group (SRLG) 的成员关系等 数据结构 TELSA TE-LSDB 由 TE nodes 和 TE links组成,基于约束的路由计算(1),Constrained-based routing CSPF是一种改进的最短路径优先算法，在计算通过网络的最短路径时，将特定的约束(比如，带宽需求，最大跳转数，和管理策略需求等)考虑进去。 路由计算 为源于本节点的流量主干计算路径 首先去掉不能满足约束需求的资源，然后选优。,基于约束的路由计算(2),路由表 通往TE隧道尾节点的流量，由TE隧道传输。 通往TE隧道尾节点下游的流量，由TE隧道传输。 如果有多个 TE隧道在通往目标节点X的路上， 选择尾节点离X 最近的隧道。,TE-RSVP/CR-LDP支持MPLS流量工程,标记请求、映射和管理 QoS and Traffic Parameters 作为 opaque data 传递给流量管理单元 Failure Notification LSP建立失败或LSP发生故障时发送故障通知 Failure Recovery 在数据传输中断前重新路由（make before break ） Path Re-optimization 基于流量模式和网络状态 Path Preemption 终止现存LSP,以便建立更高优先级隧道,USE: (links with sufficient resources) AND (links of type “someColor”) AND (links that have delay less than 200 ms),CR-LDP,示例,示例,configure terminal interface tunnel1 tunnel destination 17.17.17.17 mpls traffic-eng path-option 1 dynamic interface tunnel2 tunnel destination 17.17.17.17 tunnel mpls traffic-eng path-option 1 explicit identifier 1 configure terminal ip explicit-path identifier 1 next-address 131.0.0.1 next-address 135.0.0.1 next-address 136.0.0.1 next-address 133.0.0.1,示例,LSP强占,traffic trunk( “A”)剥夺“B”的LSP： (I)A 的优先级高于B； (ii) A竞争B使用的资源；(iii)资源不能被A和B同时使用； (iv) A是 preemptor enabled； (v) B是 preemptable. 在区分服务模型下是必备属性。尤其是在未来光网络，为了减小成本，将光层的保护和恢复功能上移到标记交换路由器， 剥夺策略可以在故障情况下减少高优先级流量主干的恢复时间。,10M free,10M free,20M LSP,0M free,0M free,MATE: Multipath Adaptive Traffic Engineering,已在Ingree Node和Egress Node之间建立多个LSP Ingree Node的任务：将流量向多个LSP映射，实现负载平衡，避免拥塞。,Filtering Distribution,Traffic Engineering,LSP1,LSP2,LSP3,LSPs,Measurement and Analysis,Probe Packets,分为N个BIN。 如果LSP1可用带宽是LSP2的M倍，则接收的流量是M倍。,入口LER的MATE功能,模型,分割流量，代价最小化 入口-出口节点对 s: 输入速率 as 路径集合 Ps = 流量划分向量,Cost 平均时延和丢包率的函数。,网络达到最佳操作点 通过迭代，将流量从最大偏差的路径向最小偏差路径转移。,路由计算模式,离线方式 离线实施可能需要花费几个小时来完成，它提供全局计算，比较每个计算的结果，然后为网络选出一个全局性的最佳方案。离线计算的输出是一系列优化了网络资源使用的LSP。在离线方式中，所有路由在改变之后都要进行重新优化，所以，网络路由结果更佳。 在线方式 路由计算模块只为新需求计算最佳路由，当