搜索
1第7章网络层协议2主要内容（1）7.1网络层概述7.2路由算法7.2.1最优化原则7.2.2最短路径路由算法7.2.3洪泛算法7.2.4基于流量的路由算法7.2.5距离向量路由算法7.2.6链路状态路由算法7.2.7分层路由7.2.8移动主机的路由3主要内容（2）7.3拥塞控制算法7.3.1拥塞控制的基本原理7.3.2拥塞控制算法7.4网络互连7.4.1级联虚电路7.4.2无连接网络互连7.4.3隧道技术7.4.4互联网路由7.4.5分段7.4.6防火墙4主要内容（3）7.5INTERNET网络层协议7.5.1IP协议7.5.2Internet控制协议7.5.3内部网关路由协议：OSPF7.5.4外部网关路由协议：BGP7.6路由器体系结构和关键技术57.1网络层概述（1）ISO定义-网络层为一个网络连接的两个传送实体间交换网络服务数据单元提供功能和规程的方法，它使传送实体独立于路由选择和交换的方式。网络层是处理端到端传输的最低层。网络层要解决的关键问题是了解通信子网的拓扑结构，选择路由。67.1网络层概述（2）网络层设计的有关问题-为传输层提供服务•面向连接服务传统电信的观点：通信子网应该提供可靠的、面向连接的服务。•无连接服务Internet的观点：通信子网无论怎么设计都是不可靠的，因此网络层只需提供无连接服务。•IP/ATM787.1网络层概述（3）-网络层的内部组织•虚电路（virtualcircuit）•数据报（datagram）-虚电路子网与数据报子网的比较•路由器内存空间与带宽的权衡虚电路方式，路由器需要维护虚电路的状态信息；数据报方式，每个数据报都携带完整的目的/源地址，浪费带宽97.1网络层概述（4）•连接建立时间与地址查找时间的权衡虚电路需要在建立连接时花费时间数据报则在每次路由时过程复杂•服务质量与可靠性的权衡虚电路方式很容易保证服务质量QoS(QualityofService)，适用于实时操作，但比较脆弱。数据报不太容易保证服务质量，但是对于通信线路的故障，适应性很强。107.1网络层概述（5）网络层为传输层提供的服务-面向连接服务：将复杂的功能放在网络层(通信子网)。-无连接服务：将复杂的功能放在传输层。-通信子网提供的服务（面向连接或无连接）与通信子网结构（虚电路或数据报）没有必然联系。-服务与子网结构的不同组合的例子111213小结（1）网络层的地位-位于数据链路层和传输层之间，使用数据链路层提供的服务，为传输层提供服务；-通信子网的最高层；-处理端到端传输的最低层。网络层的作用-屏蔽各种不同类型网络之间的差异，实现互连-了解通信子网的拓扑结构，选择路由，实现报文的网络传输14小结（2）网络层的两种实现方式：数据报和虚电路-都属于分组交换，采用存储转发机制。-数据报(datagram)：每个分组被单独路由，分组带有全网唯一的地址-虚电路(virtualcircuit)：先在源端和目的端之间建立一条虚电路，所有分组沿虚电路按次序存储转发，最后拆除虚电路。在虚电路中，每个分组无须进行路径选择。网络层提供的服务-面向连接的服务和无连接的服务。157.2路由算法（1）路由算法是网络层软件的一部分-通信子网采用数据报分组交换方式，每个包都要做路由选择；-通信子网采用虚电路分组交换方式，只需在建立连接时做一次路由选择。路由算法应具有的特性-正确性（correctness）-简单性（simplicity）-健壮性（robustness）-稳定性（stability）-公平性（fairness）-最优性（optimality）167.2路由算法（2）路由算法分类-非自适应算法，静态路由算法-自适应算法，动态路由算法7.2.1最优化原则最优化原则（optimalityprinciple）-如果路由器J在路由器I到K的最优路由上，那么从J到K的最优路由会落在同一路由上。177.2路由算法（3）汇集树（sinktree）-从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为汇集树；-路由算法的目的是找出并使用汇集树。187.2路由算法（4）7.2.2最短路径路由算法（ShortestPathRouting）属于静态路由算法基本思想-构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。测量路径长度的方法-结点数量-地理距离-传输延迟-距离、信道带宽等参数的加权函数197.2路由算法（5）Dijkstra算法-每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注-初始时，所有结点都为临时性标注，标注为无穷大；-将源结点标注为0，且为永久性标注，并令其为工作结点；-检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点207.2路由算法（6）-在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点；-重复第四、五步，直到目的结点成为工作结点。-算法实现，程序与算法的区别是：从目的结点开始。2122237.2路由算法（7）7.2.3洪泛算法（Flooding）属于静态路由算法基本思想-把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。主要问题-洪泛要产生大量重复包。解决措施-每个包头包含站点计数器，每经过一站计数器减1，为0时则丢弃该包；-记录包经过的路径247.2路由算法（8）选择性洪泛算法（selectiveflooding）-洪泛法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上。应用情况-对路由器和线路的资源过于浪费，实际很少直接采用；-具有极好的健壮性，可用于军事应用；-作为衡量标准评价其它路由算法。257.2路由算法（11）7.2.5距离向量路由算法（DistanceVectorRouting）属于动态路由算法,也称Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于ARPANET，被RIP协议采用。基本思想-每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与相邻路由器交换距离信息来更新表；-以子网中其它路由器为表的索引，表项包括两部分：到达目的结点的最佳输出线路，和到达目的结点所需时间或距离；267.2路由算法（12）-每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表；-邻居结点X发来的表中，X到路由器i的距离为Xi，本路由器到X的距离为m，则路由器经过X到i的距离为Xi+m。根据不同邻居发来的信息，计算Xi+m，并取最小值，更新本路由器的路由表；-注意：本路由器中的老路由表在计算中不被使用27287.2路由算法（13）无限计算问题-算法的缺陷：对好消息反应迅速,对坏消息反应迟钝；297.2路由算法（14）水平分裂算法-工作过程与距离向量算法相同，区别在于到X的距离不向真正通向X的邻居结点报告，使得坏消息传播的也快。-虽然广泛使用，但有时候会失败。307.2路由算法（15）7.2.6链路状态路由算法（LinkStateRouting）距离向量路由算法的主要问题-选择路由时，没有考虑线路带宽；-路由收敛速度慢。链路状态路由算法-发现邻居结点，并学习它们的网络地址；•路由器启动后，通过发送HELLO包发现邻居结点；•两个或多个路由器连在一个LAN时,引入人工结点；31327.2路由算法（16）-测量到每个邻居结点的延迟或开销；•一种直接的方法是：发送一个要对方立即响应的ECHO包，来回时间除以2即为延迟。-将所有学习到的内容封装成一个包；•包以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表；•列表中对应每个邻居结点，都有发送方到它们的延迟或开销；•链路状态包定期创建或发生重大事件时创建。33347.2路由算法（17）-将这个包发送给所有其它路由器；•基本思想：洪泛链路状态包，为控制洪泛，每个包包含一个序号，每次发送新包时加1。路由器记录信息对(源路由器，序号)，当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃；•改进序号循环使用会混淆，解决办法：使用32位序号；路由器崩溃后，序号重置；序号出错；357.2路由算法（18）第二、三问题的解决办法：增加年龄（age）域，每秒钟年龄减1，为零则丢弃。链路状态包到达后，延迟一段时间，并与其它已到达的来自同一路由器的链路状态包比较序号，丢弃重复包，保留新包；链路状态包需要应答；-计算到每个其它路由器的最短路径。•根据Dijkstra算法计算最短路径；实用协议-OSPF-IS-IS367.2路由算法（19）链路状态算法（LS）和距离向量算法（DV）的比较-路由信息的复杂性•LS路由信息向全网发送N节点，E个连接的情况下，每个节点发送O(nE)的报文•DV仅在邻居节点之间交换377.2路由算法（20）-收敛（Convergence）速度•LS可能存在路由振荡（oscillations）387.2路由算法（22）•DV收敛时间不定可能会出现路由循环count-to-infinity问题397.2路由算法（23）-健壮性:如果路由器不能正常工作会发生什么?•LS结点会广播错误的链路开销每个结点只计算自己的路由表•DV结点会广播错误的路径开销每个结点的路由表被别的结点使用，错误会传播到全网407.2路由算法（24）7.2.7分层路由（HierarchicalRouting）网络规模增长带来的问题-路由器中的路由表增大；-路由器为选择路由而占用的内存、CPU时间和网络带宽增大。分层路由-分而治之的思想；-根据需要，将路由器分成区域（regions）、聚类（clusters）、区（zones）和组（groups）…-Fig.5-17，路由表由17项减为7项。分层路由带来的问题-路由表中的路由不一定是最优路由。41427.2路由算法（25）7.2.8移动主机的路由需要解决的问题-为了能够将数据包转发给移动主机，网络必须首先要找到移动的主机。网络结构示意图437.2路由算法（26）一些基本概念-移动用户（mobileusers）：包括位置发生变化，通过固定方式或移动方式与网络连接的两类用户-家乡位置（homelocation）：所有用户都有一个永久的家乡位置，用一个地址来标识；-外部代理（foreignagent）：每个区域（一个LAN或一个wirelesscell）有一个或多个外部代理，它们记录正在访问该区域的移动用户；-家乡代理（homeagent）：每个区域有一个家乡代理，负责记录家乡在该区域，但是目前正在访问其它区域的用户。447.2路由算法（27）移动用户进入一个新区域时，必须首先向外部代理注册-外部代理定期广播声明自己的存在和地址的包，新到达的移动主机接收该信息；若移动用户未能收到该信息，则移动主机广播包，询问外部代理的地址-移动主机向外部代理注册，告知其家乡地址、目前的数据链路层地址和一些安全信息；-外部代理与移动主机的家乡代理联系，告知移动主机的目前位置、自己的网络地址和一些安全信息；-家乡代理检查安全信息，通过，则给外部代理确认-外部代理收到确认后，在登记表中加入一项，并通知移动主机注册成功。457.2路由算法（28）移动用户的路由转发过程-当一个包发给移动用户时，首先被转发到用户的家乡局域网；-该包到达用户的家乡局域网后，被家乡代理接收，家乡代理查询移动用户的新位置和与其对应的外部代理的地址；-家乡代理采用隧道技术，将收到的包作为净荷封装到一个新包中，发给外部代理；-家乡代理告诉发送方，发给移动用户的后续包作为净荷封装成包直接发给外部代理；-外部代理收到包后，将净荷封装成数据链路帧发给移动用户。4647小结（