计算机网络自顶向下方法第四章讲义资料优秀PPT.ppt

《计算机网络自顶向下方法第四章讲义资料优秀PPT.ppt》由会员分享，可在线阅读，更多相关《计算机网络自顶向下方法第四章讲义资料优秀PPT.ppt（126页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计 算 机 网 络20142014年年9 9月月国防科技学院国防科技学院第第4 4章章 网络层网络层第第4 4章章 网络层网络层计算机网络2第第4 4章章 网络层网络层本章目的:理解网络层服务依赖的原理:u选路(路径选择)u处理扩展性u路由器工作原理u先进主题:IPv6,NAT因特网中的实例和实现 第4章 网络层3第第4 4章章 网络层网络层4.1 概述概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP:网际协议4.5 选路算法4.6 互联网中选路4.7 广播和多播选路4第第4 4章章 网络层网络层从发送主机到接收主机传输段网络层协议在每台主机、路由器中当IP数据报通过路由器时，路

2、由器检查所有数据报首部字段networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical网络层数据链路物理层applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical 网络层5第第4 4章章 网络层网络层转发

3、（forwarding）:将分组从路由器的输入移动到适当的路由器输出选路（routing）:决定分组从源到目的地所采用的路由u选路算法类比:r选路:规划从源到目的地路径的过程r转发:通过单个立交桥的过程 转发与选路(网络层功能)6第第4 4章章 网络层网络层1230111到达分组首部的值选路算法本地转发表首部值输出链路01000101011110013221 选路和转发相互影响7第第4 4章章 网络层网络层它是在某些网络体系结构中第三个重要的功能:uATM,帧中继,X.25在数据报流动之前，两台主机和其间的路由器创建虚拟连接u需要路由器参与网络层和运输层的连接服务:u网络层:在两台主机之间u运

4、输层:在两个进程之间 连接建立(网络层功能)8第第4 4章章 网络层网络层问题：对从发送方到接收方“隧道”化传输数据报，其服务模型 是什么?对单个数据报的例子服务:确保交付以少于40毫秒时延确保交付对数据报流的例子服务:按序数据报交付对流确保最小带宽对分组间间隔变化的限制（确保最大时延抖动）网络服务模型9第第4 4章章 网络层网络层4.1 概述4.2 虚电路和数据报网络虚电路和数据报网络4.3 路由器的构成4.4 IP:网际协议4.5 选路算法4.6 互联网中选路4.7 广播和多播选路10第第4 4章章 网络层网络层 虚电路与数据报网络层为接在网络上的主机所提供的服务可以有两大类u无连接的网络

5、服务（数据报服务）u面向连接的网络服务（虚电路服务）11第第4 4章章 网络层网络层数据传输前，需建立连接，一个连接被称为一条虚电路VC虚电路由VC号来标识和区分虚电路连接的状态需要维持（路径上的交换节点都参与）虚电路连接涉及资源预留问题“源到目的地路径与电话电路行为非常相似”u性能明确u沿着源到目的地路径的网络动作 虚电路12第第4 4章章 网络层网络层H1H5H2H4H3ACDBH6E分组交换网H1 要和 H5 通信虚电路H1 向 H5 发送的所有分组都沿此虚电路传送。虚电路建立连接13第第4 4章章 网络层网络层H1H5H2H4H3ACDBH6E分组交换网同理，H2 与 H6通信也要建立

6、虚电路 虚电路建立连接14第第4 4章章 网络层网络层122232132VC号接口号 入接口 入VC#出接口 出VC#1 12 2 222 63 1 18 3 7 2 171 97 3 87 西北路由器中的转发表:路由器维护连接状态信息!VC号与转发表VC号局部的，而非全网的，以简化虚电路的连接建立。15第第4 4章章 网络层网络层虚电路建立（信令协议控制）数据传输虚电路拆除（信令协议控制）应用运输网络数据链路物理应用运输网络数据链路物理1.发起呼叫2.入呼叫3.接受呼叫4.呼叫已连接5.数据流开始6.接收数据 虚电路的三个阶段16第第4 4章章 网络层网络层在网络层无呼叫建立路由器：没有端到

7、端连接的状态u无网络级“连接”的概念分组使用目的主机地址转发u在相同源和目的对可能采用不同的路径应用运输网络数据链路物理应用运输网络数据链路物理1.发送数据2.接收数据 数据报网络17第第4 4章章 网络层网络层 数据报网络H1H5H2H4H3ACDBH6E分组交换网H1 向 H5 发送分组H2 向 H6 发送分组路径可能变化18第第4 4章章 网络层网络层 目的地址范围 链路接口 11001000 00010111 00010000 00000000 到 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 0000

8、0000 到 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 到 2 11001000 00010111 00011111 11111111 其他 340亿可能的项 转发表19第第4 4章章 网络层网络层 前缀匹配 链路接口 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 otherwise 3目的地址:11001000 00010111 00011000 10101010 例子目的

9、地址:11001000 00010111 00010110 10100001 哪个接口?哪个接口?最长前缀匹配20第第4 4章章 网络层网络层 数据报和虚电路比较对比的方面 虚电路服务 数据报服务 思路 可靠通信应当 可靠通信应当 由网络来保证 由用户主机来保证连接的建立 必须有 不要分组的转发 属于同一条虚电路 每个分组独立选择 的分组均按照同一 路由进行转发 路由进行转发当节点出 所有通过出故障的 故障结点可能丢失 故障时 结点的虚电路 分组，一些路由 均不能工作 可能会发生变化分组的顺序 总是按发送顺序 到达目的站时不一定 到达目的站 按发送顺序21第第4 4章章 网络层网络层4.1 概

10、述4.2 虚电路和数据报网络4.3 路由器的构成路由器的构成4.4 IP:网际协议4.5 选路算法4.6 互联网中选路4.7 广播和多播选路22第第4 4章章 网络层网络层思科(Cisco)公司创始人列昂纳德波萨克 和桑德拉勒纳 第一台路由器及其开发者23第第4 4章章 网络层网络层 路由器图示（华为）24第第4 4章章 网络层网络层路由器的主要功能u运行路由算法以得到转发表u根据转发表对IP分组进行转发u提供多种网络类型接口，完成不同网络的互联 路由器功能概要25第第4 4章章 网络层网络层 路由器体系结构路由器一般由以下部分组成u输入/输出端口u交换结构u选路处理器26第第4 4章章 网络

11、层网络层数据链路层剥去帧首部和尾部后，将分组送到网络层的队列中排队等待处理。这会产生一定的时延。输入端口处理物理层处理数据链路层处理网络层处理 分组排队 交换结构 输入端口的处理从线路接收分组查表和转发27第第4 4章章 网络层网络层当交换结构传送过来的分组先进行缓存。数据链路层处理模块将分组加上链路层的首部和尾部，交给物理层后发送到外部线路。输出端口处理物理层处理数据链路层处理网络层处理 分组排队 输出端口的处理向线路发送分组缓存管理交换结构28第第4 4章章 网络层网络层内存总线纵横制 交换结构（典型三种）29第第4 4章章 网络层网络层第一代路由器:具有交换功能的传统计算机，在CPU的直

12、接控制下分组拷贝到系统的内存速率受内存带宽限制(每数据报跨越两次总线)输入端口输入端口输出端口输出端口内存内存系统总线系统总线 经内存交换30第第4 4章章 网络层网络层数据报从输入端口到输出端口内存经一个共享的总线（总线芯片），总线速度快于内存读取速度总线竞争:任何时刻，总线仅能连通1个输入和1个输出，数据转发速率受总线带宽限制1 Gbps总线,Cisco 1900:用于接入和企业(非区域或主干)路由器的充足速率 经总线交换31第第4 4章章 网络层网络层克服了总线带宽限制Crossbar一般同时满足多个输入和输出连通一般是路由交换机 Cisco 12000:通过互联网络交换提供60Gbps

13、crossbarswitching fabric 经互联网络的交换32第第4 4章章 网络层网络层4.1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP:网际协议网际协议4.5 选路算法4.6 互联网中选路4.7 广播和多播选路33第第4 4章章 网络层网络层 网络层与IP协议各种应用层协议 网络接口层(TELNET,FTP,SMTP 等)物理硬件运输层TCP,UDP应用层ICMPIPRARPARP与各种网络接口网络层IGMP互联网的IP服务被定义成不可靠的、尽力而为、无连接不可靠的、尽力而为、无连接分组交付系统。34第第4 4章章 网络层网络层固定部分可变部分04816192

14、431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分数 据 部 分首 部传送IP 数据报首部 IP数据报格式35第第4 4章章 网络层网络层可变部分首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分数 据 部 分首 部传送IP 数据报固定部分36第第4 4章章 网络层网络层首部04816192431版 本标志生

15、存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分数 据 部 分首 部传送IP 数据报固定部分可变部分37第第4 4章章 网络层网络层首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）首部长度数 据 部 分固定部分可变部分版本占 4 bit，指IP协议的版本目前的 IP 协议版本号为 4(即 IPv4)38第第4 4章章 网络层网络层首部048161924

16、31版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分固定部分可变部分首部长度占 4 bit，可表示的最大数值是 15 个单位(一个单位为 4 字节)因此 IP 的首部长度的最大值是60字节。39第第4 4章章 网络层网络层首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度01234567DTRC未用优 先 级数 据 部 分比特固

17、定部分可变部分服务类型占 8 bit，用来获得更好的服务这个字段以前一直没有被人们使用 40第第4 4章章 网络层网络层首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分固定部分可变部分总长度占 16 bit，指首部和数据之和的长度，单位为字节，因此数据报的最大长度为 65535 字节。总长度必须不超过最大传送单元 MTU。41第第4 4章章 网络层网络层首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片

18、 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分固定部分可变部分标识、标志、片偏移：用于IP分片功能。42第第4 4章章 网络层网络层首部版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）首部长度数 据 部 分固定部分可变部分协议(8 bit)字段指出此数据报携带的数据使用何种协议以便目的主机的 IP 层将数据部分上交给哪个处理过程TCP：6 UDP：1704816192431比特43第第4 4章章 网络层网络层首部04816

19、192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分固定部分可变部分首部检验和(16 bit)字段只检验数据报的首部不包括数据部分。44第第4 4章章 网络层网络层首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分固定部分可变部分源地址和目的地址都各占 4 字节45第第4 4章章 网络层网络层网络链路有MT

20、U(最大传输长度)最大可能的链路级帧u不同的链路类型及MTU在网络中，大IP 数据报被分割(“分段”)u一个数据报 变为几个数据报u“重新装配”仅在最后目的地uIP首部比特用于标识、排序相关段reassembly IP分片和重新组装46第第4 4章章 网络层网络层ID=x偏移=0段标识=0长度=4000ID=x偏移=0段标识=1长度=1500ID=x偏移=185段标识=1长度=1500ID=x偏移=370段标识=0长度=1040一个大数据报 变为几个较小的数据报例子4000字节数据报MTU=1500字节在数据字段1480 字节偏移=1480/8 IP分片和重新组装47第第4 4章章 网络层网络

21、层IP地址:对主机、路由器接口的32-bit 标识符 接口:在主机/路由器和物理链路之间的连接u路由器通常具有多个接口u主机可能具有多个接口uIP编址与每个接口相联系223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27223.1.1.1=11011111 00000001 00000001 00000001223111 IP编址:概述点分十进制记法48第第4 4章章 网络层网络层两级IP地址:u子网部分，网络号，网络前缀(高阶比特)u主机部分，主机号(低阶比特)什么

22、是子网?uIP地址具有相同的子网部分的设备接口（具有共同的IP地址前缀）u无需通过路由器就能够物理上互相到达223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27网络由3个子网组成LAN 子网49第第4 4章章 网络层网络层223.1.1.0/24223.1.2.0/24223.1.3.0/24判断方法为了决定子网，从其主机或路由器分离每个接口，生成孤立网络的岛。每个孤立的网络被称为一个子网子网掩码:/24子网的表示方法：1、子网掩码：子网掩码：用从最高位开用从最高位

23、开始的连续始的连续1表示表示IP地址中的子网地址中的子网号部分号部分 2、前缀前缀/长度：长度：223.1.1.0/24，表示前表示前24位为子网号部分位为子网号部分 子网50第第4 4章章 网络层网络层多少个子网?223.1.1.1223.1.1.3223.1.1.4223.1.2.2223.1.2.1223.1.2.6223.1.3.2223.1.3.1223.1.3.27223.1.1.2223.1.7.0223.1.7.1223.1.8.0223.1.8.1223.1.9.1223.1.9.2 子网51第第4 4章章 网络层网络层 分类IP编址net-id24 bithost-id24

24、 bitnet-id16 bitnet-id8 bit0A 类地址host-id16 bitB 类地址C 类地址01 1host-id8 bitD 类地址 1 1 1 0多 播 地 址E 类地址保 留 为 今 后 使 用1 1 1 1 00152第第4 4章章 网络层网络层 分类IP编址网络数uA类：27-2；B类：214；C类：221u网络号不能为全0；127.X.X.X为循环测试保留地址主机数uA类：224-2；B类：216-2；C类：28-2u主机号全0代表网络本身；主机号全1代表本子网的广播地址地址范围（包括网络地址本身，广播地址，私有地址等）uA类：1.0.0.0 127.255.2

25、55.255uB类：128.0.0.0 191.255.255.255uC类：192.0.0.0 223.255.255.255uD类：224.0.0.0 239.255.255.255uE类：240.0.0.0 247.255.255.25553第第4 4章章 网络层网络层 私有地址私有地址：在互联网中不使用，仅在局域网中使用的IP地址u10.X.X.X(A类)u172.16.0.0172.31.255.255(B类)u192.168.X.X(C类)54第第4 4章章 网络层网络层无类型域间选路(Classless InterDomain Routing,CIDR)u子网为连续地址的地址块u

26、由网络前缀（如/25）确定网络部分的比特长度u（地址块，主机地址）格式:a.b.c.d/x11001000 00010111 00010000 00000000子网部分主机部分200.23.16.0/23 CIDR(无类域间路由)-不分类编址55第第4 4章章 网络层网络层 地址块描述的例子某地址块为200.23.16.0/23，则其u子网掩码为：255.255.254.0 或 /23u网络地址为：200.23.16.0(主机比特全0)u可用主机地址为：200.23.16.1200.23.17.254u广播地址为：200.23.17.255(主机比特全1)某地址块为200.23.16.0/25

27、，则其u子网掩码为：255.255.255.128 或 /25u网络地址为：200.23.16.0u可用主机地址为：200.23.16.1200.23.16.126u广播地址为：200.23.16.12756第第4 4章章 网络层网络层问题：主机怎样得到IP地址?由系统管理员配置静态地址动态主机配置协议(Dynamic Host Configuration Protocol DHCP):动态地从服务器得到地址（“即插即用”）uDHCP服务器发现：0.0.0.0255.255.255.255uDHCP服务器提供：a.b.c.d255.255.255.255uDHCP请求uDHCP ACK IP编

28、址:如何得到一个地址?57第第4 4章章 网络层网络层问题：网络怎样得到IP地址的子网部分?回答:从它的ISP的地址空间得到分配的部分ISPs block 11001000 00010111 00010000 00000000 200.23.16.0/20 Organization 0 11001000 00010111 00010000 00000000 200.23.16.0/23 Organization 1 11001000 00010111 00010010 00000000 200.23.18.0/23 Organization 2 11001000 00010111 000101

29、00 00000000 200.23.20.0/23 .Organization 7 11001000 00010111 00011110 00000000 200.23.30.0/23 IP编址:如何得到一个地址?58第第4 4章章 网络层网络层“向我发送地址始于200.23.16.0/20的任何分组”200.23.16.0/23200.23.18.0/23200.23.30.0/23Fly-By-Night-ISP组织 0组织 7因特网组织 1ISPs-R-Us“向我发送地址始于199.31.0.0/16的任何分组”200.23.20.0/23组织 2.等级编址允许有效的通告选路信息:等级

30、编址:路由聚合59第第4 4章章 网络层网络层ISPs-R-Us具有更为特定的路由到组织 1“向我发送地址始于200.23.16.0/20的任何分组”200.23.16.0/23200.23.18.0/23200.23.30.0/23Fly-By-Night-ISP组织 0组织 7因特网组织 1ISPs-R-Us“向我发送地址始于199.31.0.0/16或200.23.18.0/23的任何分组”200.23.20.0/23组织 2.等级编址:更为特定的路由60第第4 4章章 网络层网络层某单位申请了一段某单位申请了一段IP地址：地址：200.23.16.0/23。单位。单位内由内由4个部门个

31、部门(A,B,C,D)组成，每个部门的主机数组成，每个部门的主机数量分别是：量分别是：200(A),100(B),50(C),40(D)。试将单。试将单位的总地址块位的总地址块200.23.16.0/23划分为划分为4个子网分配个子网分配各各4个部门。个部门。u1.写出每个子网（地址块）写出每个子网（地址块）u2.每个子网的网络前缀？子网掩码？每个子网的网络前缀？子网掩码？u3.每个子网的广播地址？主机可用地址范围？每个子网的广播地址？主机可用地址范围？练习(注：注：200.23.16.0/23的二的二进进制表示制表示 11001000 00010111 00010000 00000000）6

32、1第第4 4章章 网络层网络层 网络地址转换NAT问题：IPv4的IP地址共有多少个？够用吗？解决办法：下一代的IPv6，增加IP地址位数（彻底解决）NAT技术（地址代理技术），提供内部私有地址与共有地址的转换，支持内网与公网的通信62第第4 4章章 网络层网络层10.0.0.110.0.0.210.0.0.310.0.0.4138.76.29.7本地网络(如归属网络)10.0.0/24因特网其他部分具有该网源或目的的数据报都有10.0.0/24的地址(照常)所有数据报本地离开本地网络具有相同的单一源NAT IP地址:138.76.29.7,不同的源端口号 网络地址转换NAT63第第4 4章章

33、 网络层网络层10.0.0.110.0.0.210.0.0.3S:10.0.0.1,3345D:128.119.40.186,80110.0.0.4138.76.29.71:主机10.0.0.1 发送数据报到128.119.40,80NAT 转换表WAN 侧地址 LAN 侧地址138.76.29.7,5001 10.0.0.1,3345 S:128.119.40.186,80 D:10.0.0.1,33454S:138.76.29.7,5001D:128.119.40.186,8022:NAT路由器改变数据报源地址从10.0.0.1,3345 到138.76.29.7,5001,更新表S:12

34、8.119.40.186,80 D:138.76.29.7,500133:回答到达的目的地址:138.76.29.7,50014:NAT 路由器改变数据报目的地址从138.76.29.7,5001到10.0.0.1,3345 外网IP地址与端口号转换内网IP地址与端口号 网络地址转换NAT64第第4 4章章 网络层网络层16-bit 端口号字段:u用一个LAN侧地址支持60,000 并行连接!NAT 引起争议:u路由器的处理上升为第三层u违反了端到端原则u应用设计者必须要考虑 NAT可能性，如 P2P应用程序u地址短缺应当由IPv6来解决 网络地址转换NAT65第第4 4章章 网络层网络层由主

35、机和路由器用于网络级信息的通信u差错报告：不可达主机，网络，端口,协议u回声请求/回答(由 ping使用)与IP的关系:类型 编码 描述0 0 回声回答(ping)3 0 目的网络不可达3 1 目的主机不可达3 2 目的协议不可达3 3 目的端口不可达3 6 目的网络未知3 7 目的主机未知4 0 源抑制(拥塞控制未使用）8 0 回声请求(ping)9 0 路由通告10 0 路由器发现11 0 TTL过期12 0 坏的IP首部 互联网控制报文协议ICMPIP网络是尽力而为（不可靠）的，ICMP通过差错报文和询问报文来辅助IP网络的功能IP首部首部IP数据区数据区ICMP首部首部ICMP数据数据

36、66第第4 4章章 网络层网络层源向目的地发送一系列UDP段u第一个 TTL=1u第二个 TTL=2,等u不可能的端口号当第n个数据报 到达第n和路由器:u路由器丢弃数据报u并向源发送一个ICMP报文(类型 11,编码0)u报文包括路由器的名字和IP地址当ICMP报文到达，源计算 RTTTraceroute执行上述过程3次停止规则UDP段最终到达目的地主机目的地返回ICMP“端口不可达”分组(类型3,编码3)当源得到该ICMP,停止 Traceroute和ICMP67第第4 4章章 网络层网络层初始动机:32bit地址空间耗尽IPv6的特点:u大地址空间，地址128bitu更简洁的报文头u更好

37、的QoS支持u更好的安全性 3.410385.981024千克 5.691010个/克 下一代IP协议：IPv668第第4 4章章 网络层网络层 IPv6首部基本首部 扩展首部 1 扩展首部 N 数 据 部 分选项IPv6 数据报有效载荷041631版 本位目 的 地 址源 地 址下 一 个 首 部流 标 号12业务类型（128 位）（128 位）有 效 载 荷 长 度跳 数 限 制24有效载荷（扩展首部/数据）IPv6 的基本首部（40 B）IPv6 的有效载荷（至 64 KB）69第第4 4章章 网络层网络层041631版 本位目 的 地 址源 地 址下 一 个 首 部流 标 号12业务类

38、型（128 位）（128 位）有 效 载 荷 长 度跳 数 限 制24IPv6的基本首部40 B业务类型，流标号：提供QoS区分与支持70第第4 4章章 网络层网络层并非所有的路由器能被同时更新u无“标志日”uIPv4和IPv6路由器混合将如何运行?隧道:在IPv路由器之间IPv6数据报作为IPv4数据报的负载 从IPv4到IPv6的迁移71第第4 4章章 网络层网络层ABEFIPv6IPv6IPv6IPv6隧道逻辑视图:物理视图:ABEFIPv6IPv6IPv6IPv6CDIPv4IPv4流:X源:A目的:F数据流:X源:A目的:F数据流:X源:A目的:F数据源:B目的:E流:X源:A目的:

39、F数据源:B目的:EA-to-B:IPv6E-to-F:IPv6B-to-C:IPv6 在IPv4中B-to-C:IPv6 在IPv4中 隧道72第第4 4章章 网络层网络层4.1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP:网际协议4.5 选路算法选路算法4.6 互联网中选路4.7 广播和多播选路73第第4 4章章 网络层网络层选路算法的图论抽象:图中的节点是路由器图中的边是物理链路u链路代价:时延，费用或拥塞等级目的：决定从源到目的地通过网络的“好的路径”(路由器序列)选路 协议AEDCBF2213112535r“好的”路径:m通常意味着最小费用的路径m其他定义也是可能

40、的 选路74第第4 4章章 网络层网络层全局的或分散的信息?分散的:路由器知道物理相连的邻居，到邻居的链路费用计算的迭代过程，与邻居交换信息“距离矢量”算法全局的:所有路由器具有完全的拓扑、链路费用信息“链路状态”算法s静态的或动态的?静态:路由随时间缓慢变化动态:路由更快地变化u周期的更新u适应链路费用变化 选路算法分类75第第4 4章章 网络层网络层Dijkstra算法所有节点知道网络拓扑、链路费用u经“链路状态广播”完成u所有节点具有相同信息从一个节点(源)到所有其他节点计算最低费用路径u给出对这些节点的转发表迭代:k次迭代后，得知到k个目的地的最低费用路径概念:c(x,y):从节点x到

41、y的链路费用;=如果不是直接邻居D(v):从源到目的地v路径费用的当前值p(v):从源到v沿路径的前任节点N:已知在最小费用路径中的节点集合Dijkstra 迪杰斯特拉 链路状态算法76第第4 4章章 网络层网络层1 初始化初始化:2 N=u 3 对所有节点v 4 if v 临近 u 5 then D(v)=c(u,v)6 else D(v)=7 8 Loop 9 找出w不在N中使得D(w)最小 10 将w加入N 11 对于所有v临近w并不在N中，更新D(v):12 D(v)=min(D(v),D(w)+c(w,v)13 /*到v的新费用或是到v的老费用或到w加上从w到v的已知最短路费用*/1

42、5 until 所有节点在所有节点在 N中中 Dijsktra算法77第第4 4章章 网络层网络层步骤012345NuuxuxyuxyvuxyvwuxyvwzD(v),p(v)2,u2,u2,uD(w),p(w)5,u4,x3,y3,yD(x),p(x)1,uD(y),p(y)2,xD(z),p(z)4,y4,y4,yu uyxwvz2213112535 Dijkstra算法:例子78第第4 4章章 网络层网络层算法复杂性:n个节点每次迭代:需要检查所有节点w,不在N中n(n+1)/2 对比:O(n2)更有效的实现是可能的:O(nlogn)可能振荡:如链路费用=承载流量的量wzyx11+ee0

43、e1100wzyx2+e0001+e 1wzyx02+e1+e10 0wzyx2+e0e01+e 1最初 重计算选路 重计算重计算e11e11e11 Dijkstra算法,讨论79第第4 4章章 网络层网络层Bellman-Ford方程(动态规划)定义dx(y):=从x到y最低费用路径的费用则dx(y)=min c(x,v)+dv(y)其中min对x的所有邻居 距离矢量算法80第第4 4章章 网络层网络层u uyxwvz2213112535Clearly,dv(z)=5,dx(z)=3,dw(z)=3du(z)=min c(u,v)+dv(z),c(u,x)+dx(z),c(u,w)+dw(z

44、)=min 2+5,1+3,5+3 =4取最小的节点是在最短路中的下一跳转发表B-F equation says:Bellman-Ford 例子81第第4 4章章 网络层网络层基本思想:每个节点周期性的发送它自己的距离矢量估计到其邻居当节点x接收到来自邻居的新DV估计，它使用B-F方程更新其自己的DV:Dx(y)minvc(x,v)+Dv(y)for each node y N在规模较小、正常的条件下，估计值Dx(y)收敛在实际最小费用 dx(y)距离矢量算法82第第4 4章章 网络层网络层迭代、异步:每次本地迭代由下列引起:本地链路费用改变DV从邻居更新报文分布式:每个节点仅当其DV改变时通

45、知邻居u如果必要，邻居则通知它们的邻居等待(来自邻居本地费用报文的变化)重新计算 估计值如果到任何目的地的DV已经变化,通知 邻居 每个节点:距离矢量算法83第第4 4章章 网络层网络层链路费用变化:好消息传播得快坏消息传播得慢“计数到无穷”问题!在算法稳定前，迭代44 次:参见课文xz1450y60 距离矢量:链路费用变化84第第4 4章章 网络层网络层报文复杂性LS:对n个节点，E条链路,发送O(nE)报文 DV:仅在邻居之间交换u收敛时间变化收敛速度LS:O(n2)算法要求 O(nE)报文u可能具有振荡DV:收敛时间变化u可能有选路环路u计数到无穷问题健壮性:如果路由器异常，将发生什么现

46、象?LS:u节点可能通告不正确的链路费用u每个节点仅计算它自己的表DV:uDV节点通告不正确的路径费用u每个节点表能由其他人使用u差错通过网络传播 LS和DV算法的比较85第第4 4章章 网络层网络层规模:具有2亿个目的地:在选路表中不能存储所有的目的地!选路表交换将堵塞链路!管理自治互联网=网络的网络每个网络管理员可能要控制他自己网络中的选路我们的选路研究至此是理想的r所有路由器是等同的r网络“扁平”实践中并不真实 等级选路86第第4 4章章 网络层网络层出于管理和扩展的目的，因特网可以被分割成许多不同的自治系统(autonomous system，AS)，换句话说，因特网是由很多自治系统汇

47、集而成的从选路的角度来说，自治系统是指使用统一内部路由协议的一组网络u自治系统内的选路协议(intra-AS)u自治系统间的选路协议(inter-AS)自治系统具有唯一的AS号（全球已分配几千个AS号，活跃的接近一千个）自治系统87第第4 4章章 网络层网络层3b1d3a1c2aAS3AS1AS21a2c2b1bAS内部选路 算法AS之间选路 算法转发表3c转发表由AS内部和AS之间的选路算法所配置uAS内部设置内部目的地表项uAS之间和AS内部对外部目的地设置表项 互联的AS88第第4 4章章 网络层网络层3b1d3a1c2aAS3AS1AS21a2c2b1b3c假定在AS1中的路由器接收目

48、的地是AS1外部的数据报u路由器应当将分组朝着网关路由器转发，但哪个呢？AS1需要:1.知道通过AS2可到达哪些目的地，通过AS3到达哪些2.传播这些可达信息到AS1中所有路由器AS间选路的工作!AS间的任务89第第4 4章章 网络层网络层4.1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP:网际协议4.5 选路算法4.6 互联网中选路互联网中选路4.7 广播和多播选路90第第4 4章章 网络层网络层用于自治系统内部的路由协议称为“内部网关协议”，简称 IGP(Interior Gateway Protocol)uRIPuOSPFuEIGRP用于自治系统间接口上的路由协议称为

49、“外部网关协议”，简称EGP(Exterior Gateway Protocol)uBGP-4 选路协议91第第4 4章章 网络层网络层路由信息协议 RIP 是内部网关协议 IGP中最先得到广泛使用的协议。RIP 是一种分布式的基于距离向量的路由选择协议。路由信息协议RIP92第第4 4章章 网络层网络层从一路由器到直接连接的网络的距离定义为 1。从一个路由器到非直接连接的网络的距离定义为所经过的路由器数加 1。RIP 协议中的“距离”也称为“跳数”(hop count)，因为每经过一个路由器，跳数就加 1。RIP认为一个好的路由就是它通过的路由器的数目少，即“距离短”。RIP允许一条路径最多

50、只能包含 15 个路由器，“距离”的最大值为16 时即相当于不可达。“距离”的定义 93第第4 4章章 网络层网络层仅和相邻路由器交换信息。交换的信息是当前本路由器所知道的全部信息，即自己的路由表。按固定的时间间隔交换路由信息，例如，每隔 30 秒。RIP协议的三个要点 94第第4 4章章 网络层网络层路由器在刚刚开始工作时，只知道到直接连接的网络的距离（此距离定义为1）。以后，每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息。经过若干次更新后，所有的路由器最终都会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器的地址。路由表的建立 95第第4 4章章 网络层网络层收到相邻