Internet课程3-第三层交换

1、第七章 第三层交换交换的基本功能：线速转发业务流，将输入端口与输出端口对应起来。交换技术本地转发：根据分组中携带的信息确定输出端口（目的地址、源路由向量、连接标签等）；通路控制：为转发而建立和维护相关控制信息（地址学习、生成树、广播和发现、链路状态选路、显示信令）。路由的基本功能：路由处理，转发业务流。第三层交换：利用交换技术加速网络层（IP）分组转发的机制和协议。分类：报文到报文：每一个报文都经过第三层的路由处理；能够适应网络拓扑变化；只应用于基于帧的网络。流交换：第一个报文经过第三层路由，后续报文直接交换；路由处理开销小、可应用于帧和信元结构的网络；但对网络拓扑变化适应慢。 与第三层交换技

2、术有密切联系的相关技术：虚拟局域网VLAN、下一跳地址解析协议NHRP、资源预留RSVP、IP组播等。基本概念第七章 第三层交换7.1 报文到报文处理方法传统路由器 功能齐全，但中转速度慢。改进策略削减支持的协议（只对IP）；只完成路由和交换；使用ASIC实现更多的功能。路由式交换机 功能有限，速度快。特性：限制处理的协议（IP、以太网）；仅支持个别路由协议（RIP、OSPF）；监听ARP，建立IP到MAC的映射表；用ASIC降低路由代价、提高路由性能为目标。业务流分类器业务流控制器队列管理器交换/路由/流管理管理控制策略内存管理RMON输入端口输出端口交换式路由器（现代Internet路由器

3、） 高效率线速路由与控制。特性：只针对IP；将尽可能多的功能构造到硬件（查表、匹配计算等）；报文不退回到慢速通道处理（即便是处理失败）；路由表足够大。难题与挑战：网络功能的增加和更新速度远大于硬件设计和更新速度。第七章 第三层交换7.2 流交换方法特点：路由一次、随后交换，在源和目的之间建立交换捷径或直通路径。端系统驱动的流交换 不更改网络的交换设施，只增加端系统的软件。网络中心式的流交换 网络中的骨干交换节点增加路由映射功能，协同操作，建立捷径。7.2.1 驱动方式第七章 第三层交换7.2.2 NHRP用途：当通信终端不在同一广播域时，由源端来决定合适的下一跳IP地址和MAC地址，使得同一非

4、广播多接入网络NBMA的端系统能够建立直通路径。NBMA网络：指在一个物理网络上叠加多个独立逻辑IP子网的网络系统。NHS：NHRP的服务器，维护一个IP地址到MAC地址的映射表，响应NHRP请求。每个子网中至少有一个NHS。NHC：NHRP的客户端，向NHS登记和发起NHRP请求，并保存NHS返回的IP地址到MAC地址的映射。NHC-ANHC-B子网1子网2子网3子网4NHS1/2NHS2/3NHS3/4路由器1路由器2路由器3NHRP请求注册注册IP路由NHRP请求IP路由NHRP响应IP路由NHRP响应第七章 第三层交换7.2.3 Fast-IP7.2.4 NetFlowNHRP请求NH

5、RP请求A和BMAC封装NHRP响应A和BMAC封装NHRP响应NFFC：NetFlow特征卡，保存IP到MAC的映射表；RSM：IP路由转发模块；SE：交换引擎。RSMNFFCSE7.3 多协议标记交换MPLS7.3.1 标记交换的概念第七章 第三层交换标记交换：在分组进入网络时，将其划分某个FEC，用该FEC的编码对分组“标记”；随后的各跳中，不再进行网络层报头解析，只根据“标记”查表、转发。IP网络中标记交换的特点是面向无连接业务。选择下一跳1)将以相同方式转发的分组划分为“转 发等效类FEC”；2)将每个转发等效类映射到一个下一 跳（输出端口）。MPLS的优点：当网络拓扑变化时，与传统

6、的IP路由方式比，MPLS能够提供更快和更可预测的保护能力和恢复能力，即MPLS保护。支持流量工程（Traffic Engineering）、虚拟私有网VPNs、第二层传输服务、多层覆盖网络等应用。标记交换IPv6IPv4IPXAppleTalkEthernetFDDIATMFRSDHADSL第七章 第三层交换7.3.2 标记交换的功能组件转发部件： 1）从分组中抽取标记； 2）在转发信息库FIB中检索匹配的信息； 3）根据对应数据记录的出口信息进行转发。控制部件： 1）捆绑标记和转发等效类； 2）发布捆绑信息给其他标记交换路由器； 3）根据捆绑和发布结果以及路由协议构造FIB。FIB：入口标

7、记 出口标记 地址前缀 输出端口 控制部件完成标记交换路径LSP的建立过程，类似于路由器的路由算法工作过程；而转发部件类似于路由器的选路转发工作过程。链路层PIC 标签 网络层PCI 数据标记/标签：Label(20bits) Exp(3bits) S(1bit) TTL(8bits） 第七章 第三层交换转发等效类FEC的映射： MPLS在边缘路由器上完成分组到FEC的映射。映射过程既是对流的分类处理过程，也是划分业务流传输粒度的过程。标记栈/分层交换： 标记分组可以承载多个标记，通过一个后进先出的栈组织起来。LSR总是遵循最顶层的标记优先处理的步骤。第七章 第三层交换7.3.3 标记交换路径

8、LSP点到点交换路径：用于发布单播数据传输业务。多点到点交换路径：多个入口对应一个出口，适用于尽力而为的数据传输业务。点到多点交换路径：用于发布组播数据传输业务。多点到多点交换路径：用于基于共享树的组播数据传输业务。路由选择逐跳路由：与IP路由方式相同，每个LSR独立选路。显式路由：一个LSR在一条LSP中明确指明后续的全部或者部分LSR，需要在标记分配时由LSR指定。显式路由的主要用途：在策略路由、流量工程中优化流量分布等。第七章 第三层交换显式标记交换路径LSP建立 MPLS中显式路径的建立也就是标记分配的过程，也就是路由器内特定标签L与某个转发等效类F绑定，形成转发信息库FIB的过程。标

9、记9；前缀128.80.0.0/16标记4；前缀128.80.0.0/16 step3： 入口x；出口4； 前缀：128.80.0.0/16标记分配的方式下游自主分配：下游LSR根据自己的状态，进行L与F的绑定，并将绑定消息通知给上游的LSR。在LSR接入网络时，与其它LSR交互控制信息来触发捆绑的建立和释放。下游按需分配：下游LSR收到上游LSR的分配请求后，进行L与F的捆绑。当业务流到达时，才触发捆绑进程。捆绑更新快，占用标记较少，但对LSR的处理速度要求高。128.80.0.0/16 step1： 入口9；出口x； 前缀：128.80.0.0/16 step2： 入口4；出口9； 前缀：

10、128.80.0.0/16转发信息库FIB条目生成方式独立控制：每个LSR独自确定对当前特定的FEC使用的标记号L。有序控制：LSR等待下游通知出口的标记号，串行建立FIB条目。标记分配驱动方式拓扑驱动：依靠路由协议控制信息流驱动标记分配，建立交换路径。请求控制驱动：由请求控制业务发起标记分配，如RSVP。业务流驱动：在业务流到达时，临时发起分配，建立交换路径。第七章 第三层交换标记发布 标记捆绑后可通过两种方法传递给相关的LSR。由路由消息携带：可简化系统操作。标记发布协议LDP：专用的标记发布协议LDP。标记发布协议LDP消息：1）发现消息，用于声明和维护标记交换MPLS网络中一个标记交换

11、路由器LSR的存在；2）会话消息，用于建立、维护和终止标记发布协议LDP中对等实体间的会话；3）公布消息，用于生成、改变和删除转发等效类FEC与标记交换路径LSP的捆绑关系； 4）通知消息，用于信息提示和错误通知。标记交换协议LDP的运行1）发现阶段：一是基本发现机制，通过UDP周期性地发送“Hello”通知邻节点建立对等关系；二是扩展发现机制，周期地发送特定IP地址的“Hello”包建立联系。2）会话建立阶段。首先，在两个LSR之间建立TCP连接；然后，交互LDP初始化信息来协商会话参数（版本号、标记发布方式、定时器值、标签范围等）。3）会话维持和删除。LSR为每个会话维持一个定时器，收到一

12、个该会话的PDU则刷新定时器；否则，超时则认为传输中断或对等失效，关闭运输层连接，终止会话。 标记保持模式（标记信息的保存方法）保守保持模式：只记录下一跳LSR发布的标记信息。自由保持模式：记录所有对等LSR发布的标记信息。交换环路控制减轻环路影响：利用TTL将循环的分组在一定时间内 丢弃。检测环路：在路径变化时，沿新路经向目的地发送环 路检测控制包。防止环路：在标记发布的捆绑和请求消息中加入路径 向量。第七章 第三层交换7.3.4 MPLS对区分服务的支持 增加了区分服务的LSR要在原有标记基础上，引入区分服务路由器的功能，即根据区分服务信息确定PHB，进而决定分组优先级队列和丢弃概率。 区

13、分服务信息包括：服务分类和丢弃概率。 利用在LSR上建立标记到服务类的映射表，服务分类可由分组标记得到。 利用MPLS标记中的Exp来指定所对应的PHB，从而确定调度和丢弃策略。区分服务标记交换路由器的转发模式 输入PHB确定；输出PHB确定； 标记转发；区分服务编码封装。第七章 第三层交换7.3.5 MPLS应用于流量工程 流量工程主要是指对运行网络的性能优化过程，其中的一项中心任务就是对带宽资源进行有效管理，即拥塞的最小化。 对于资源不足导致的拥塞，通常有：速率控制、窗口控制、队列管理等技术；对于资源分配的不合理导致的拥塞，可以用流量工程来解决。 基于最短路径算法的内部网关路由协议是造成网

14、络中自治系统发生拥塞的主要原因，利用MPLS的显式路由来进行负载均衡是一种直接、有效的解决方法。约束路由 路由计算中如果考虑比网络拓扑更多的因素，就可以找到轻负载（可能较长）的路径，使得网络流量分布得更均匀。在线约束路由：可以随时为标记交换路径进行路由选择计算。离线约束路由：在离线的服务周期为标记交换路径进行路由选择计算。增强链路状态的IGP 为建立满足约束的标记交换路径，内部路由协议除了传递链路状态信息外，还必须传递链路属性（保留带宽、优先级、亲密度、适应性等）。基于MPLS的流量工程 首先，设置每天链路的最大保留带宽；然后，设置每条LSP需要的带宽，约束路由能够自动避免在一条链路上分配太多

15、的LSP。其次，在多路经的源和目的对之间配置多条LSP，设定负载比例来实现流量分流。目标：1）为每个接纳的QoS业务请求找到满足要求的可行路径。2）优化资源利用率，平衡网络负载，将网络QoS接纳能力最大化。 QoS路由是指：根据网络上可利用的资源和流（Flow）的QoS需求决定流的传输路径的机制。 其研究内容：一是不断更新信息；二是利用信息选择合适的可行路径。第八章 QoS路由和多径路由8.1 QoS路由8.1.1 网络模型与QoS度量有权图模型 有向图G=(V,E)中，令eE具有一组(w1, w2, wk)属性，则称G为有权图， (w1, w2, wk)为e的权，属性=带宽、延时、费用等。Q

16、oS度量 对图G中的路径P= (v1, v2, vs) ，设ei,i+1的第j个属性为wji,i+1,整个路径P的第j个属性为wjp，有：若 ，则属性j为可加性度量，如延时、抖动、跳数等。若 ，则属性j为可乘性度量，如分组丢失率。若 ，则属性j为最小性度量，如路径瓶颈带宽。不同类型的QoS度量，其计算代价也不同。多重最小性度量组合可以在多项式时间求解，而多重可加性度量组合通常不能在多项式时间求解。第八章 QoS路由和多径路由8.1.2 QoS路由面对的问题 IETF提出的QoS路由结构也分为两层：域内QoS路由和域间QoS路由。状态信息：本地状态：节点和直接链路所具有的状态信息。全局状态：网络

17、中各个节点本地状态的组合。聚集状态：层次结构中底层压缩聚集后的全局状态信息。交互 状态信息交互可以按周期方式、触发方式、触发周期结合方式。路由方式与QoS计算源路由：对大型网络需维护的全局状态开销太大；分布式路由：处理复杂，对设计基于QoS的多约束启发式算法难度大；层次化路由：如何聚集状态信息还有待进一步研究。基本问题最优化：寻找对应QoS度量的最优路径。性能界约束：寻找大于或小于对应QoS度量的路径，即在满足性能界限要求的集合中选择解。多约束优化与NP计算 QoS路由计算往往需要在多约束目标下选择最优化路径，其中大多数计算无法在多项式时间内完成，故计算复杂度属于NP完全或NP难度问题。 多项

18、式时间求解问题： NP完全问题：链路约束与链路优化问题组合； 路径约束与路径优化问题组合；链路约束与路径优化问题组合； 多路径约束问题。链路约束与路径约束问题组合；链路优化与路径约束问题组合；多链路约束问题。第八章 QoS路由和多径路由8.1.3 IP单播QoS路由基本问题涉及：链路优化、链路约束、路径优化、路径约束。 这4种问题可以由Dijkstra或Bellmen-Ford算法求解。QoS单播问题大都可由这4种问题演化而来，例如，带宽约束最小延时问题是链路约束与路径优化问题的组合。最短路径算法 源到目的节点所选路径的链路权值之和最小，可用来解决路径约束问题。多路搜索路由算法 以平衡流量分布

19、为主要目标。PNNI利用回绕来依次所搜多条路径是否满足约束；并行多路路由向多条路径发出请求，沿途建立资源预留，最好的一条路径被选中。基于调度策略的路由算法 基于WFQ，将端到端延时、抖动、队长作为带宽的函数，通过扩展BF算法求解源路由。该算法将网络低层的分组调度机制引入到路由算法中，有效地平衡了网络资源。启发式路由算法 可以降低计算复杂度，但不能保证一定能够发现可行路径。扩展BF算法：源到目的的路径P，如果对于其它路径Q 有 ，则P为一条最优路径。粒度约束的方法中，对于多条属性值相同的最优路径只保存一条路径；路径约束的方法中，在加入新的最优路径前，判断是否已达到最大路径总数的限制。随机选择多路

20、经约束算法：先剪去所有不满足条件的路径，然后，在剩余路径中随机选择一条搜索其可行性。基于拉格朗日松弛的算法：首先构造路径花费函数 ；然后，以 为关键字用Dijkstra算法计算最短路径P；0且P 满足延时约束，则P为最优解；否则，增大，求满足延时约束的P。第八章 QoS路由和多径路由8.1.3 IP组播QoS路由基本问题涉及：链路约束、多链路约束、树约束、多树约束、链路优化、树优化。其中，多树约束和树优化问题属于NP完全问题。 多项式时间求解问题： NP完全问题：链路约束与树约束问题组合； 链路优化与树约束问题组合；树约束与链路优化问题组合。 链路约束与树优化问题组合； 树约束与树优化问题组合

21、； 链路约束与多树约束问题组合。最短路径树算法 多播树上源到接收节点每条路径上链路权值之和最小，可用来解决树约束问题。最小生成树算法 覆盖所有组成员并且树权值之和最小的树，可用来解决树优化问题。Steiner树算法 求解总代价最小的多播树，属NP完全问题。启发式KMB算法求解基于时间约束的Steiner树路由选择：先计算图的最小生成树，然后搜索树，删去不属于必须连接的叶节点和边。该算法只能找到局部最优解，难以找到全局最优解。MCMST算法：先用Dijkstra k最短路径算法计算出每对节点满足时延约束的路径集合，再从集合中满足抖动约束的有效路径集合。约束Steiner树算法 Steiner树问

22、题可扩展为包括其它链路约束。BSMA算法：求解时延约束的树优化问题。先计算给定源的最小时延树，再基于时延约束寻找代价更小的超边，直到代价不再减少。KPP算法：在代价最小和时延最小间平衡。先计算时延约束闭合图，用Prim计算最小生成树；再用源图中的边进行替代。SPH算法：求解度数约束的Steiner树。从源节点开始，每次寻找一个满足度数约束且最近的接收节点加入树，直到所有接收节点加入树中。Jia分布式算法：解决时延约束的树优化问题。从源开始，选择最靠近树且满足时延约束的节点，将其到树的最短路径加入，直至所有接收节点加入。最大带宽树算法 解决链路优化问题。用Dijkstra算法计算出源到所有接收节

23、点的最大可用带宽树，确定每个接收者从源接收数据的预期接收率，再在最大带宽树上分配相应的链路带宽。第八章 QoS路由和多径路由8.1.4 不确定信息的QoS路由 网络状态不确定的原因：网络的动态性；状态信息的聚集；不精确的测量；近似计算；被隐藏的信息。容忍不确定信息的QoS路由算法 为了减少网络动态性产生的不确定信息对网络性能的影响，采取（周期或阈值法）状态信息刷新来使网络节点保持信息的一致性。基于安全的路由：适合基于阈值的状态刷新机制。首先确定状态值的分布范围，给出分布函数；然后，选择满足QoS的路径。8.1.4.1 基于不确定信息的单播QoS路由随机路由：使用状态值的概率分布函数寻求安全路径

24、。首先删除不满足带宽约束的路径；然后，可行路径集中随机挑选一条路径。多路经路由：通过向多条路径发送探测包（带有特殊标签），如果到达目的则寻找到满足条件的路径。若有多条路径，则随机选择。局部优化路由：基于本地信息动态地在多条路径上按比例传输业务。运用虚容量模型解决多路经共享链路的干扰问题；采用自抑止策略避免备用路由可能带来的多米诺骨牌效应。静态多路经路由：先求出相同的预计算路径集合，在用与局部优化算法相同的方法确定路由。基于状态信息概率分布的QoS路由算法 通过对网络业务流模型的分析，利用检测机制和基于测量的统计分析方法，使用概率分布函数来描述链路状态的变化。 约束分离启发式方法：先利用Bell

25、men-Ford确定不同链路跳数下延时最小的备选路径；再从中选择最可能满足要求的路径。代价函数方法：将链路延时概率分布函数转换为代价函数，将求解一条以最大概率满足时延约束概率的最佳分段问题，转换为求解路径上各条链路满足本地时延约束概率的乘积最大。近似计算方法：先也进行代价函数转换，再将路由问题分解为选路和划分；根据最小时延划分粒度，将两节点的路径扩充为具有不同时延值的链路集，然后求最小代价的近似解。实际的网络状态概率难以确定，概率模型只能近似描述网络特性；基于状态概率的路由问题复杂度高，增加较多的网络资源额外开销。因此，必须在路由的有效性和计算代价之间寻求平衡点。第八章 QoS路由和多径路由8

26、.1.4.2 基于不确定信息的组播QoS路由ISIMR-GA算法：通过初始群体的筛选和自适应惩罚函数的运用，加上启发式交叉变异，提高算法的搜索能力和收敛速度。ISI算法：仅需要了解网络的不确定状态，不必选择多播树的中心节点，通过节点间消息传递解决组成员动态加入；但算法没有考虑链路传播时延的不确定性。QMRGA算法：也是基于遗传算法的路由机制，可以在几次迭代内求出最优解或近似最优解。DMIQ算法：用改进的BF算法搜索路径，以WFQ为调度机制，能在状态不确定且带宽、时延、丢包率满足约束的条件下，确定具有最小跳数和开销的动态多播路由。8.1.4.3 可能的研究突破点在路由有效性和计算复杂性之间选取合

27、适的折中。确定链路状态信息的概率模型。基于理论模型的QoS路由算法研究。基于不确定信息的多约束条件QoS路由算法研究。第八章 QoS路由和多径路由8.2 多路经路由目标：在保证网络拥塞几率最小、资源利用率最大的前提下，完成路径的选择和流量分配。优点：多经路由能够聚集多条路径的网络资源，减少网络拥塞，支持更高的传输速率，并且增强传输的可靠性。主要研究：集中在扩展内部网关IGP路由机制，其实现算法包括：开环路径计算和这些路径间的流量分割。8.2.1 概述8.2.2 关键问题流量均衡：指节点流入负载与流出负载之间的平衡。GFEDACB均衡方式：有增加可用资源的横向扩展和限制资源 使用的纵向抑止。优化指标：资源利用率、吞吐量、时延、丢包率等。全局/局部优化：依据网络状态的全局视图或本地视图 进行优化决策。流量分割粒度：基于每个流的细粒度和基于源-目对的 粗粒度。流量分布比例：基于优化目标确定各条路径上的负载 分配比例。流量分割：N-Hash法、Hash门限法、加权随机分发法。第八章 QoS路由和多径路由 该问题也就是选择哪几条路径和选择多少条路径的问题。路径独立性：指路径的连接性和相关性。aefdcb路径回路：集合中的各条路径之间不构成路由环路。动态路由：需解决IP流量负载敏感路由机制的计算效率和稳定