网络通信与OSI_5

1、第四章回顾l停等应答协议l连续应答协议l数据流控制lHDLCInternet中的数据链路层l数据链路层是对物理层传输的原始比特加以编码和控制，以便为网络层提供一条无错、有序和透明的链路。n网络层主要功能：支持网络连接的实现和向传输层提供各种服务。 、路径选择和中继功能 、网络连接的建立、支持和释放功能 、多路复用 、数据单元的交换 、其它功能第五章、网络层及PDN主要内容n路径和路径选择n拥挤控制和死锁n公用数据网络n数据报和虚电路的实现nhttp:/ 7个城市组成，各城市节点分别由下列航空、铁路和公路组成交通网：1、航空：AC 、ED2、铁路：AB、 BC、 CD 3、公路：AF、 FE、

2、EC 、CD 、E-G、 E-Hn问题1：请绘制该城市的交通网拓扑图,注意标出线路运行方向。n问题2：请找出从A到达D的交通线路。n问题3：请找出从A到达D的最佳交通线路。n问题3：请问G节点是否可达？n问题4：请问H节点是否可达？路径选择算法的基本要求n算法必须是正确稳定和公平的 n算法应该尽量简单 n算法能够适应网络拓扑和通信量的变化n算法应该是最佳的 算法涉及的主要参数 n跳数（hop count） 分组从源结点到达目的结点经过的路由器的个数(tracert)n带宽（bandwidth） 链路的传输速率n延时（delay） 分组从源结点到达目的结点花费的时间(ping)n负载（load）

3、 通过路由器或线路的单位时间通信量n可靠性（reliability） 传输过程中的误码率n开销（overhead） 传输过程中的耗费，与所使用的链 路带宽相关分组交付方式 n直接交付：如果目的主机与源主机 A 是连接在同一个网络上.n间接交付：如果目的主机与源主机 A 不是连接在同一个网络上，则由路由器按照转发表指出的路由将数据报转发给下一个路由器.直接交付 间接交付 典型的路由器的结构 路由选择路由选择处理机路由选择协议路由表3输入端口3交换结构输入端口输出端口分组转发转发表分组处理输出端口11133122223网络层2数据链路层1物理层路由选择模块与路由表n在每个路由器接收到一个IP分组时

4、，路由选择模块必须进行路由查询；n路由器查询的顺序是： 第一步是判断该IP分组是不是直接转发。如果不是直接转发 第二步确定是不是特定主机转发。如果不是特定主机转发 第三步确定是不是特定网络转发。如果不是特定网络转发，最后就要确定是不是默认转发。路由动画路径选择算法的分类n两大类：静态路由选择算法和动态路由选择算法 非适应性 适应性n简单路径选择算法:n 随机路径n 扩散路径(站计数法)n 静态路径 (第一次登录法)n 孤立路径路径选择算法的分类适应路径选择算法n集中路径n分布路径n综合路径区域 R2网 1区域 R9R7R6R5R4R3R1网 8网 6网 3网 2网

5、7区域 网 4网 5R8CC二、拥挤控制n定义：子网内由于出现过量信息包而引起网络性能（向主机递交的信息包数）下降的现象称为拥挤。产生拥挤的原因n节点执行各种管理操作，使接收速度跟不上发送速度。n节点输出信息包的能力小于输入能力引起信息包在缓存器排长队，甚至占满了缓存器，使新到的信息包由于得不到缓存器而丢失。n根本原因：缓冲器的安排不当合理分配缓冲器拥挤控制缓冲器预定算法n适合于虚电路传输子网n方法：在建立虚电路过程，可在呼叫信息包经过的节点上登记路径选择表出入口，同时预定缓冲器，缓冲器的数量同滑容窗尺寸。n特点：降低缓冲器和电路利用率。拥挤控制分配缓冲器算法n（）每一根输入线分

6、配一个缓冲器n（）限制一条输出线的信息包队列长度n平分法：某节点有个缓冲器，根输出线、输入线L，每根输出线的缓冲器则（-L）/拥挤控制分配缓冲器算法n最大分配法：令：max是最大队列长则：Ni为队列i的信息包数一般取 如10个缓冲器,3根输入线和3根输出线则3个缓冲器用于输入线 max0BNiLKNiNLKB/ )(max3/ )310(maxB拥挤控制分配缓冲器算法n最小分配法使每根输出线的缓冲器不少于Bmin 特点:避免吞吐量退化,不公平性和直接存贮转发死锁.拥挤控制许可证算法n思想：向网络发放适量的许可证，每个要发送的信息包必须得到一个许可证方可发送n特点： 1、可保证全局性拥挤，但不完

7、全消除局部拥挤； 2、网内许可证会随系统软件故障而减少，降低吞吐量。拥挤控制阻塞包算法n设计思想：拥挤控制只有在拥挤时起作用，否则不起作用。设变量u、f u输出线的近期利用率 0u1 f输出线的瞬时利用率 f:0,1 令： u=au+(1-a)f u=af+(1-a)u a为u的修改速度拥挤控制阻塞包算法n拥挤控制方法（设U0为一阈，即拥挤）1、信息包到达时,检查UU0否?若是,转22、发阻塞包给源点,在信息包上记阻塞包标志.3、源节点若收到阻塞包,减少X%发送信息量速度4、若再收到阻塞包,再减少X%，若在定时内无阻塞包,增加X%拥挤控制限制使用输入缓冲器法n 区分进入节点的信息包是从主机来的

8、还是转发的信息包,限制输入缓冲器的使用。三、死锁n定义：死锁是指两个节点相互等待，无法发送和接收信息包。n类型：存贮转发死锁重排序死锁重装配死锁死锁存贮转发死锁n(a)直接存贮转发死锁n(b)间接存贮转发死锁死锁存贮转发死锁n解决方法:缓冲器分级结构和信息包定向传输法。设信息包传送最大路径数为存贮送给本地主机每个缓冲器的状态存贮待转发信息死锁重排序死锁n原因：在虚电路服务子网中采用不按顺序缓冲的流水线协议时，n如：传.解决方法：丢弃目的节点未按顺序排列的信息包分配足够缓冲器死锁重装配死锁n传输层送给网络层的长信息（类似上一情况）拥挤控制和流控制的差异n拥挤控制必须确保通信子网能传送该传送的数据

9、，这是全局性的问题。涉及到所有主机，所有通信节点及节点中存贮转发处理的行为，以及所有将导致削减通信子网负荷能力的其它因素。拥挤控制和流控制的差异n流控制只与某发送者与接收者之间的点到点通信具有关系，它的任务是确保快速发送者不能比接收者能承受的速率更高速度传数据，流控制几乎总是涉及到接收者告诉发送者另一端情况如何的一些直接反馈。四、公用数据网络（）(*)n定义:向计算机用户提供公共的数据通信服务的计算机网络,它由转接结点机和网络中心等组成.公用数据网络（）nPSTN与PDN的关系:大多数PDN采用PSTN,通过调制解调器,将结点机,网络控制中心和用户入网设备互连起来进行数据通信。1、为提供信道资

10、源2、通过开辟更为广阔的应用领域。公用数据网的特性n协议标准：公用数据网是由接受的国际标准，主要包括系列和系列的通信标准及用户数据速率和用户接口的标准。n类型：分组交换数据网络（）和电路交换数据网络（）。n协议模型：涉及参考模型的低三层。n特性：为传输层以上各层提供透明的数据传输服务。公用数据网电路交换()n定义:通过直接切换通信线路，进行数据交换的方式称为电路交换。公用数据网电路交换()特点：信道固定：速率固定，传播延迟长公用数据网分组交换 (P)n定义：在源端把分组信息进行编址（源和目的地址），发往转接节点，并存贮，待有空的输出线再转发，直至目的机。公用数据网分组交换 (P)特点：不需占用

11、整个通信信道，传输速率可变。公用数据网分组交换和电路交换的比较不提供差错控制及流控制提供差错控制及流控制提供的服务种类较多数据报和虚电路n提供两类服务：数据报和虚电路n数据报服务：在数据报服务控制下，子网接收源节点来的独立信息包，经全称编址后，独自地传输到目的节点，服务质量：无序，无差错控制。n虚电路服务：虚电路是网络内一对数据终端之间的逻辑连接，数据交换前，要先建立一虚电路，确定数据交换的路径。服务质量：有序、无错数据报和虚电路n虚电路与逻辑信道的不同点：1、虚电路是动态建立，动态清除，而逻辑信道即是始终存在的。2、虚电路是端一端的，而逻辑信道只具有本地特性。数据报和虚电路n子网内数据服务的

12、实现：每一节点保存一输出线选择表n子网内虚电路服务的实现：子网的每一节点保存一张虚电路的输入输出表，一一对应。虚电路的实现H1ADCT1H2AFEDT2H3FEDCT1第五章、网络层第五节、互联网的常用路由协议有关路由选择协议的几个基本概念内部网关协议 RIP内部网关协议 OSPFn主讲：蔡伟鸿计算机网络与通信5.5.1 有关路由选择协议的几个基本概念1. 理想的路由算法n算法必须是正确的和完整的。 n算法在计算上应简单。 n算法应能适应通信量和网络拓扑的变化，这就是说，要有自适应性。 n算法应具有稳定性。 n算法应是公平的。 n算法应是最佳的。 2.关于“最佳路由” n不存在一种绝对的最佳路

13、由算法。n所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。n实际的路由选择算法，应尽可能接近于理想的算法。 n路由选择是个非常复杂的问题n它是网络中的所有结点共同协调工作的结果。n路由选择的环境往往是不断变化的，而这种变化有时无法事先知道。 3.路由算法的自适应性w静态路由是由网络管理员在系统安装时根据网络的配置情况预先设定，网络结构发生变化后由网络管理员手工修改路由表。w动态路由是随网络运行情况的变化而变化，路由器根据路由协议提供的功能自动计算数据传输的最佳路径，由此得到动态路由表。4.自治系统 AS（Autonomous System) w自治系统（AS):一个自治系统就

14、是处于一个管理机构控制之下的路由器和网络群组。它可以是一个路由器直接连接到一个LAN上，同时也连到Internet上；它可以是一个由企业骨干网互连的多个局域网。在一个自治系统中的所有路由器必须相互连接，运行相同的路由协议，同时分配同一个自治系统编号。w自治系统内部使用的内部网关协议IGP（IRP）：RIP ，HELLO，OSPF等w自治系统之间使用的外部网关协议EGP（ERP）：BGP自治系统自治系统C C自治系统自治系统A A自治系统自治系统B B图示图示H1H2H1H1A1A1A4A4A3B1B2A3B1B2H2自治系统自治系统A A的路由协议的路由协议RIPRIP自治系统自治系统B B的

15、选路协议的选路协议OSPFOSPF自治自治系统系统间的间的路由路由协议协议BGPBGPC1A2C2C3B3B4A15、内部IP路由协议和类型路由协议路由协议类型类型RIPV1（路由信息协议V1 ）距离向量RIPV2 （路由信息协议V2 ）距离向量IGRP（内部网关路由选择协议 ）距离向量EIGRP（加强型内部网关路由协议 ）距离向量OSPF（优先开放最短路径 ）链路状态 按路由算法方式的不同又可将内部路由协议分为距离向量路由协议和链路状态路由协议两种。 距离向量路由协议主要以已知网络中路由器间的距离（跳数）更新路由表。 链路状态路由协议则主要是以相邻路由器的状态更新路由表。 5.5.2 内部网

16、关协议 RIP (Routing Information Protocol)1. 工作原理nRIP 是一种分布式的基于距离向量的路由选择协议。nRIP 协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录。n路由信息协议 RIP 是内部网关协议 IGP中最先得到广泛使用的协议。“距离”的定义 n从一路由器到直接连接的网络的距离定义为 1。n从一个路由器到非直接连接的网络的距离定义为所经过的路由器数加 1。nRIP 协议中的“距离”也称为“跳数”(hop count)，因为每经过一个路由器，跳数就加 1。n这里的“距离”实际上指的是“最短距离”， “距离”的定义 nRIP

17、认为一个好的路由就是它通过的路由器的数目少，即“距离短”。nRIP 允许一条路径最多只能包含 15 个路由器。n“距离”的最大值为16 时即相当于不可达。可见 RIP 只适用于小型互联网。nRIP 不能在两个网络之间同时使用多条路由。RIP 选择一个具有最少路由器的路由（即最短路由），哪怕还存在另一条高速(低时延)但路由器较多的路由。 RIP 协议的三个要点 n仅和相邻路由器交换信息。 n交换的信息是当前本路由器所知道的全部信息，即自己的路由表。 n按固定的时间间隔交换路由信息，例如，每隔 30 秒。 路由表的建立 n路由器在刚刚开始工作时，只知道到直接连接的网络的距离（此距离定义为1）。n以

18、后，每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息。n经过若干次更新后，所有的路由器最终都会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器的地址。nRIP 协议的收敛(convergence)过程较快，即在自治系统中所有的结点都得到正确的路由选择信息的过程。 2. 距离向量算法收到相邻路由器（其地址为 X）的一个 RIP 报文：(1) 先修改此 RIP 报文中的所有项目：把“下一跳”字段中的地址都改为 X，并把所有的“距离”字段的值加 1。(2) 对修改后的 RIP 报文中的每一个项目，重复以下步骤：若项目中的目的网络不在路由表中，则把该项目加到路由表中。 否则 若下一

19、跳字段给出的路由器地址是同样的，则把收到的项目替换原路由表中的项目。 否则 若收到项目中的距离小于路由表中的距离，则进行更新，否则，什么也不做。(3) 若 3 分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器记为不可达路由器，即将距离置为16（距离为16表示不可达）。(4) 返回。路由器之间交换信息 nRIP协议让互联网中的所有路由器都和自己的相邻路由器不断交换路由信息，并不断更新其路由表，使得从每一个路由器到每一个目的网络的路由都是最短的（即跳数最少）。n虽然所有的路由器最终都拥有了整个自治系统的全局路由信息，但由于每一个路由器的位置不同，它们的路由表当然也应当是不同的。 RIP (R

20、outing Information Protocol) Destination Network Next Router Num. of hops to dest. wA2yB2 zB3x-1.wxyzACDB路由器D中的路由表图例图例网网网3网4RR2R3R2中的路由表中的路由表R1中的路由表中的路由表R3中的路由表中的路由表目的主机的网络号下一站路由器距离10-120-1目的主机的网络号下一站路由器距离20-130-1目的主机

21、的网络号下一站路由器距离30-140-1目的主机的网络号下一站路由器距离20-130-1102402目的主机的网络号下一站路由器距离30-140-1103202目的主机的网络号下一站路由器距离10-120-1302403 4 字节RIP 报文3. RIP2 协议的报文格式 路由信息（20 字节/路由）可重复出现最多 25 个IP 数据报路由标记网络地址地址族标识符距离 (1-16) IP 首部UDP 首部首部路由部分必为 0版本命令 4 字节子网掩码下一跳路由器地址UDP 用户数据报课堂交流与互动n

22、 假定网络中的路由器B的路由表右表的项目，现在B收到从相邻路由器C发来的信息（这两列分别为目的网络和距离）nN24nN38nN64nN84nN95n试求出路由器B更新后的路由表目的网络距离下一跳路由器N17AN22CN65FN84EN94F路由器B的路由表方式：2-4位同学交流 时间：2分钟 提交：黑板填写课堂交流与互动n 假定网络中的路由器B的路由表右表的项目，现在B收到从相邻路由器C发来的信息（这两列分别为目的网络和距离）nN24nN38nN64nN84nN95n试求出路由器B更新后的路由表目的网络距离下一跳路由器N17AN22CN39CN65CN83CN94F更新后路由器B的路由表4.R

23、IP 协议的优缺点 nRIP 存在的一个问题是当网络出现故障时，要经过比较长的时间才能将此信息传送到所有的路由器。n RIP 协议最大的优点就是实现简单，开销较小。nRIP 限制了网络的规模，它能使用的最大距离为 15（16 表示不可达）。n路由器之间交换的路由信息是路由器中的完整路由表，因而随着网络规模的扩大，开销也就增加。 R2R1网 1网 3网 2正常情况1 1 1 2 R1R1 说：“我到网 1 的距离是 1，是直接交付。”“1”表示“从本路由器到网 1”“1”表示“距离是 1”“ ”表示“直接交付”R2R1网 1网 3网 2正常情况1 1 1 2 R1R2 说：“我到网 1 的距离是

24、 2，是经过 R1。”“1”表示“从本路由器到网 1”“2”表示“距离是 2”“R1”表示经过 R1R2R1网 1网 3网 2R2R1网 1网 3网 2网 1出了故障正常情况1 1 1 16 1 2 R11 2 R1R1 说：“我到网 1 的距离是 16 （表示无法到达）， 是直接交付。”但 R2 在收到 R1 的更新报文之前，还发送原来的报文，因为这时 R2 并不知道 R1 出了故障。R2R1网 1网 3网 2R2R1网 1网 3网 2网 1出了故障正常情况1 1 1 16 1 2 R11 2 R1R1 收到 R2 的更新报文后，误认为可经过 R2 到达网1，于是更新自己的路由表，说：“我到

25、网 1 的距离是 3，下一跳经过 R2”。然后将此更新信息发送给 R2。1 3 R2R2R1网 1网 3网 2R2R1网 1网 3网 2网 1出了故障正常情况1 1 1 16 1 2 R11 2 R1R2 以后又更新自己的路由表为“1, 4, R1”，表明 “我到网 1 距离是 4，下一跳经过 R1”。 1 3 R21 4 R1R2R1网 1网 3网 2R2R1网 1网 3网 2网 1出了故障正常情况1 1 1 16 1 3 R21 5 R21 16 R21 2 R11 2 R11 4 R11 16 R1这样不断更新下去，直到 R1 和 R2 到网 1 的距离都增大到 16 时，R1 和 R2

26、 才知道网 1 是不可达的。 这就是好消息传播得快，而坏消息传播得慢。网络出故障的传播时间往往需要较长的时间(例如数分钟)。这是 RIP 的一个主要缺点。 5.5.3 内部网关协议 OSPF (Open Shortest Path First)1. OSPF 协议的4个基本特点n“开放”表明 OSPF 协议不是受某一家厂商控制，而是公开发表的。n“最短路径优先”是因为使用了 Dijkstra（狄克斯特拉 ）提出的最短路径算法SPFnOSPF 只是一个协议的名字，它并不表示其他的路由选择协议不是“最短路径优先”。n是分布式的链路状态协议。 三个要点 n向本自治系统中所有路由器发送信息，这里使用的

27、方法是洪泛法。n发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。n“链路状态”就是说明本路由器都和哪些路由器相邻，以及该链路的“度量”(metric)。n只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息。 链路状态数据库(link-state database) n由于各路由器之间频繁地交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据库。n这个数据库实际上就是全网的拓扑结构图，它在全网范围内是一致的（这称为链路状态数据库的同步）。nOSPF 的链路状态数据库能较快地进行更新，使各个路由器能及时更新其路由表。OSPF 的更新过程收

28、敛得快是其重要优点。 OSPF 的区域(area) n为了使 OSPF 能够用于规模很大的网络，OSPF 将一个自治系统再划分为若干个更小的范围，叫作区域。n每一个区域都有一个 32 位的区域标识符（用点分十进制表示）。n区域也不能太大，在一个区域内的路由器最好不超过 200 个。 自治系统 ASOSPF 划分为两种不同的区域 区域 区域 主干区域 至其他自治系统R9R7R6R5R4R3R2R1网 8网 6网 3网 2网 1网 7区域 网 4网 5R8划分区域的特点n划分区域的好处就是将利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治系统，这就减少了整个网络上的通信量。n在一个区域内部的路由器只知道本区域的完整网络拓扑，而不知道其他区域的网络拓扑的情况。nOSPF 使用层次结构的区域划分。在上层的区域叫作主干区域(backbone area)。主干区域的标识符规定为。主干区域的作用是用来连通其他在下层的区域。 自治系统 AS主干路由器区域 区域 主干区域 至其他自治系统