《计算机网络自顶向下方法讲义资料.pptx》由会员分享，可在线阅读，更多相关《计算机网络自顶向下方法讲义资料.pptx（126页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1第4章 网络层计算机网络第1页/共126页2本章目的:理解网络层服务依赖的原理:选路(路径选择)处理扩展性路由器工作原理先进主题:IPv6,NAT因特网中的实例和实现 第4章 网络层第2页/共126页34.1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP:网际协议4.5 选路算法4.6 互联网中选路4.7 广播和多播选路第3页/共126页4从发送主机到接收主机传输段网络层协议在每台主机、路由器中当IP数据报通过路由器时，路由器检查所有数据报首部字段networkdata linkphysicalnetworkdata linkphysicalnetworkdata link
2、physicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical网络层数据链路物理层applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical 网络层第4页/共126页5转发（forwarding）:将分组从路由器的输入移动到适当的路由器输出选路（routing）:决定分组从源到目的地所采用的路由选路算法类比:r选路:规划从源到目的地路
3、径的过程r转发:通过单个立交桥的过程 转发与选路(网络层功能)第5页/共126页61230111到达分组首部的值选路算法本地转发表首部值输出链路01000101011110013221 选路和转发相互影响第6页/共126页7它是在某些网络体系结构中第三个重要的功能:ATM,帧中继,X.25在数据报流动之前，两台主机和其间的路由器创建虚拟连接需要路由器参与网络层和运输层的连接服务:网络层:在两台主机之间运输层:在两个进程之间 连接建立(网络层功能)第7页/共126页8问题：对从发送方到接收方“隧道”化传输数据报，其服务模型 是什么?对单个数据报的例子服务:确保交付以少于40毫秒时延确保交付对数据
4、报流的例子服务:按序数据报交付对流确保最小带宽对分组间间隔变化的限制（确保最大时延抖动）网络服务模型第8页/共126页94.1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP:网际协议4.5 选路算法4.6 互联网中选路4.7 广播和多播选路第9页/共126页10 虚电路与数据报网络层为接在网络上的主机所提供的服务可以有两大类u无连接的网络服务（数据报服务）u面向连接的网络服务（虚电路服务）第10页/共126页11数据传输前，需建立连接，一个连接被称为一条虚电路VC虚电路由VC号来标识和区分虚电路连接的状态需要维持（路径上的交换节点都参与）虚电路连接涉及资源预留问题“源到目的地
5、路径与电话电路行为非常相似”性能明确沿着源到目的地路径的网络动作 虚电路第11页/共126页12H1H5H2H4H3ACDBH6E分组交换网H1 要和 H5 通信虚电路H1 向 H5 发送的所有分组都沿此虚电路传送。虚电路建立连接第12页/共126页13H1H5H2H4H3ACDBH6E分组交换网同理，H2 与 H6通信也要建立虚电路 虚电路建立连接第13页/共126页14122232132VC号接口号 入接口 入VC#出接口 出VC#1 12 2 222 63 1 18 3 7 2 171 97 3 87 西北路由器中的转发表:路由器维护连接状态信息!VC号与转发表VC号局部的，而非全网的，
6、以简化虚电路的连接建立。第14页/共126页15虚电路建立（信令协议控制）数据传输虚电路拆除（信令协议控制）应用运输网络数据链路物理应用运输网络数据链路物理1.发起呼叫2.入呼叫3.接受呼叫4.呼叫已连接5.数据流开始6.接收数据 虚电路的三个阶段第15页/共126页16在网络层无呼叫建立路由器：没有端到端连接的状态无网络级“连接”的概念分组使用目的主机地址转发在相同源和目的对可能采用不同的路径应用运输网络数据链路物理应用运输网络数据链路物理1.发送数据2.接收数据 数据报网络第16页/共126页17 数据报网络H1H5H2H4H3ACDBH6E分组交换网H1 向 H5 发送分组H2 向 H6
7、 发送分组路径可能变化第17页/共126页18 目的地址范围 链路接口 11001000 00010111 00010000 00000000 到 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 到 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 到 2 11001000 00010111 00011111 11111111 其他 340亿可能的项 转发表第18页/共126页19 前缀匹配 链路接
8、口 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 otherwise 3目的地址:11001000 00010111 00011000 10101010 例子目的地址:11001000 00010111 00010110 10100001 哪个接口?哪个接口?最长前缀匹配第19页/共126页20 数据报和虚电路比较对比的方面 虚电路服务 数据报服务 思路 可靠通信应当 可靠通信应当 由网络来保证 由用户主机来保证连接的建立 必须有 不要分组的转发 属于同一条虚电路 每个分组独立选
9、择 的分组均按照同一 路由进行转发 路由进行转发当节点出 所有通过出故障的 故障结点可能丢失 故障时 结点的虚电路 分组，一些路由 均不能工作 可能会发生变化分组的顺序 总是按发送顺序 到达目的站时不一定 到达目的站 按发送顺序第20页/共126页214.1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP:网际协议4.5 选路算法4.6 互联网中选路4.7 广播和多播选路第21页/共126页22思科(Cisco)公司创始人列昂纳德波萨克 和桑德拉勒纳 第一台路由器及其开发者第22页/共126页23 路由器图示（华为）第23页/共126页24路由器的主要功能运行路由算法以得到转发
10、表根据转发表对IP分组进行转发提供多种网络类型接口，完成不同网络的互联 路由器功能概要第24页/共126页25 路由器体系结构路由器一般由以下部分组成u输入/输出端口u交换结构u选路处理器第25页/共126页26数据链路层剥去帧首部和尾部后，将分组送到网络层的队列中排队等待处理。这会产生一定的时延。输入端口处理物理层处理数据链路层处理网络层处理 分组排队 交换结构 输入端口的处理从线路接收分组查表和转发第26页/共126页27当交换结构传送过来的分组先进行缓存。数据链路层处理模块将分组加上链路层的首部和尾部，交给物理层后发送到外部线路。输出端口处理物理层处理数据链路层处理网络层处理 分组排队
11、输出端口的处理向线路发送分组缓存管理交换结构第27页/共126页28内存总线纵横制 交换结构（典型三种）第28页/共126页29第一代路由器:具有交换功能的传统计算机，在CPU的直接控制下分组拷贝到系统的内存速率受内存带宽限制(每数据报跨越两次总线)输入端口输出端口内存系统总线 经内存交换第29页/共126页30数据报从输入端口到输出端口内存经一个共享的总线（总线芯片），总线速度快于内存读取速度总线竞争:任何时刻，总线仅能连通1个输入和1个输出，数据转发速率受总线带宽限制1 Gbps总线,Cisco 1900:用于接入和企业(非区域或主干)路由器的充足速率 经总线交换第30页/共126页31克
12、服了总线带宽限制Crossbar一般同时满足多个输入和输出连通一般是路由交换机 Cisco 12000:通过互联网络交换提供60Gbpscrossbarswitching fabric 经互联网络的交换第31页/共126页324.1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP:网际协议4.5 选路算法4.6 互联网中选路4.7 广播和多播选路第32页/共126页33 网络层与IP协议各种应用层协议 网络接口层(TELNET,FTP,SMTP 等)物理硬件运输层TCP,UDP应用层ICMPIPRARPARP与各种网络接口网络层IGMP互联网的IP服务被定义成不可靠的、尽力而为
13、、无连接不可靠的、尽力而为、无连接分组交付系统。第33页/共126页34固定部分可变部分04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分数 据 部 分首 部传送IP 数据报首部 IP数据报格式第34页/共126页35可变部分首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分数 据 部 分首 部
14、传送IP 数据报固定部分第35页/共126页36首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分数 据 部 分首 部传送IP 数据报固定部分可变部分第36页/共126页37首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）首部长度数 据 部 分固定部分可变部分版本占 4 bit，指IP协议的版本目前的 IP 协议版
15、本号为 4(即 IPv4)第37页/共126页38首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分固定部分可变部分首部长度占 4 bit，可表示的最大数值是 15 个单位(一个单位为 4 字节)因此 IP 的首部长度的最大值是60字节。第38页/共126页39首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首
16、部长度01234567DTRC未用优 先 级数 据 部 分比特固定部分可变部分服务类型占 8 bit，用来获得更好的服务这个字段以前一直没有被人们使用 第39页/共126页40首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分固定部分可变部分总长度占 16 bit，指首部和数据之和的长度，单位为字节，因此数据报的最大长度为 65535 字节。总长度必须不超过最大传送单元 MTU。第40页/共126页41首部04816192431版 本标志生
17、存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分固定部分可变部分标识、标志、片偏移：用于IP分片功能。第41页/共126页42首部版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）首部长度数 据 部 分固定部分可变部分协议(8 bit)字段指出此数据报携带的数据使用何种协议以便目的主机的 IP 层将数据部分上交给哪个处理过程TCP：6 UDP：1704816192431比特第42
18、页/共126页43首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分固定部分可变部分首部检验和(16 bit)字段只检验数据报的首部不包括数据部分。第43页/共126页44首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分固定部分可变部分源地址和目的地址都各占 4 字节第44页/共126页4
19、5网络链路有MTU(最大传输长度)最大可能的链路级帧不同的链路类型及MTU在网络中，大IP 数据报被分割(“分段”)一个数据报 变为几个数据报“重新装配”仅在最后目的地IP首部比特用于标识、排序相关段reassembly IP分片和重新组装第45页/共126页46ID=x偏移=0段标识=0长度=4000ID=x偏移=0段标识=1长度=1500ID=x偏移=185段标识=1长度=1500ID=x偏移=370段标识=0长度=1040一个大数据报 变为几个较小的数据报例子4000字节数据报MTU=1500字节在数据字段1480 字节偏移=1480/8 IP分片和重新组装第46页/共126页47IP地
20、址:对主机、路由器接口的32-bit 标识符 接口:在主机/路由器和物理链路之间的连接路由器通常具有多个接口主机可能具有多个接口IP编址与每个接口相联系223.1.1.2223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27223111 IP编址:概述点分十进制记法第47页/共126页48两级IP地址:子网部分，网络号，网络前缀(高阶比特)主机部分，主机号(低阶比特)什么是子网?IP地址具有相同的子网部分的设备接口（具有共同的IP地址前缀）无需通过路由器就能够物理上互相到达网络由3个子网组成LAN 子网第48页/共126页49223.1.1.0/24223
21、.1.2.0/24223.1.3.0/24判断方法为了决定子网，从其主机或路由器分离每个接口，生成孤立网络的岛。每个孤立的网络被称为一个子网子网掩码:/24子网的表示方法：1、子网掩码：用从最高位开始的连续1表示IP地址中的子网号部分 2、前缀/长度：，表示前24位为子网号部分 子网第49页/共126页50多少个子网?子网第50页/共126页51 分类IP编址net-id24 bithost-id24 bitnet-id16 bitnet-id8 bit0A 类地址host-id16 bitB 类地址C 类地址01 1host-id8 bitD 类地址 1 1 1 0多 播 地 址E 类地址保
22、 留 为 今 后 使 用1 1 1 1 001第51页/共126页52 分类IP编址网络数uA类：27-2；B类：214；C类：221u网络号不能为全0；为循环测试保留地址主机数uA类：224-2；B类：216-2；C类：28-2u主机号全0代表网络本身；主机号全1代表本子网的广播地址地址范围（包括网络地址本身，广播地址，私有地址等）uA类：1uB类：128uC类：192uD类：224uE类：240第52页/共126页53 私有地址私有地址：在互联网中不使用，仅在局域网中使用的IP地址u类)u类)u类)第53页/共126页54无类型域间选路(Classless InterDomain Rout
23、ing,CIDR)子网为连续地址的地址块由网络前缀（如/25）确定网络部分的比特长度（地址块，主机地址）格式:11001000 00010111 00010000 00000000子网部分主机部分200.23.16.0/23 CIDR(无类域间路由)-不分类编址第54页/共126页55 地址块描述的例子某地址块为，则其u子网掩码为：或 /23u网络地址为：主机比特全0)u可用主机地址为：u广播地址为：主机比特全1)某地址块为，则其u子网掩码为：或 /25u网络地址为：u可用主机地址为：u广播地址为：第55页/共126页56问题：主机怎样得到IP地址?由系统管理员配置静态地址动态主机配置协议(D
24、ynamic Host Configuration Protocol DHCP):动态地从服务器得到地址（“即插即用”）DHCP服务器发现：DHCP服务器提供：DHCP请求DHCP ACK IP编址:如何得到一个地址?第56页/共126页57问题：网络怎样得到IP地址的子网部分?回答:从它的ISP的地址空间得到分配的部分ISPs block 11001000 00010111 0001Organization 0 11001000 00010111 0001000Organization 1 11001000 00010111 0001001Organization 2 11001000 00
25、010111 0001010 .Organization 7 11001000 00010111 0001111 IP编址:如何得到一个地址?第57页/共126页58“向我发送地址始于的任何分组”200.23.16.0/23200.23.18.0/23200.23.30.0/23Fly-By-Night-ISP组织 0组织 7因特网组织 1ISPs-R-Us“向我发送地址始于的任何分组”200.23.20.0/23组织 2.等级编址允许有效的通告选路信息:等级编址:路由聚合第58页/共126页59ISPs-R-Us具有更为特定的路由到组织 1“向我发送地址始于的任何分组”200.23.16.0
26、/23200.23.18.0/23200.23.30.0/23Fly-By-Night-ISP组织 0组织 7因特网组织 1ISPs-R-Us“向我发送地址始于或的任何分组”200.23.20.0/23组织 2.等级编址:更为特定的路由第59页/共126页60某单位申请了一段IP地址：。单位内由4个部门(A,B,C,D)组成，每个部门的主机数量分别是：200(A),100(B),50(C),40(D)。试将单位的总地址块划分为4个子网分配各4个部门。1.写出每个子网（地址块）2.每个子网的网络前缀？子网掩码？3.每个子网的广播地址？主机可用地址范围？练习(注：的二进制表示 11001000 0
27、0010111 00010000 00000000）第60页/共126页61 网络地址转换NAT问题：IPv4的IP地址共有多少个？够用吗？解决办法：下一代的IPv6，增加IP地址位数（彻底解决）NAT技术（地址代理技术），提供内部私有地址与共有地址的转换，支持内网与公网的通信第61页/共126页62本地网络(如归属网络)因特网其他部分具有该网源或目的的数据报都有的地址(照常)所有数据报本地离开本地网络具有相同的单一源NAT IP地址不同的源端口号 网络地址转换NAT第62页/共126页63S:10.0.0.1,3345D:128.119.40.186,8011:主机10.0.0.1 发送数据
28、报到128.119.40,80NAT 转换表WAN 侧地址 LAN 侧地址 S:128.119.40.186,80 D:10.0.0.1,33454S:138.76.29.7,5001D:128.119.40.186,8022:NAT路由器改变数据报源地址从到更新表S:128.119.40.186,80 D:138.76.29.7,500133:回答到达的目的地址:4:NAT 路由器改变数据报目的地址从到 外网IP地址与端口号转换内网IP地址与端口号 网络地址转换NAT第63页/共126页6416-bit 端口号字段:用一个LAN侧地址支持60,000 并行连接!NAT 引起争议:路由器的处理
29、上升为第三层违反了端到端原则应用设计者必须要考虑 NAT可能性，如 P2P应用程序地址短缺应当由IPv6来解决 网络地址转换NAT第64页/共126页65由主机和路由器用于网络级信息的通信差错报告：不可达主机，网络，端口,协议回声请求/回答(由 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首部 互联网控制报文
30、协议ICMPIP网络是尽力而为（不可靠）的，ICMP通过差错报文和询问报文来辅助IP网络的功能IP首部IP数据区ICMP首部ICMP数据第65页/共126页66源向目的地发送一系列UDP段第一个 TTL=1第二个 TTL=2,等不可能的端口号当第n个数据报 到达第n和路由器:路由器丢弃数据报并向源发送一个ICMP报文(类型 11,编码0)报文包括路由器的名字和IP地址当ICMP报文到达，源计算 RTTTraceroute执行上述过程3次停止规则UDP段最终到达目的地主机目的地返回ICMP“端口不可达”分组(类型3,编码3)当源得到该ICMP,停止 Traceroute和ICMP第66页/共12
31、6页67初始动机:32bit地址空间耗尽IPv6的特点:大地址空间，地址128bit更简洁的报文头更好的QoS支持更好的安全性 3.410385.981024千克 5.691010个/克 下一代IP协议：IPv6第67页/共126页68 IPv6首部基本首部 扩展首部 1 扩展首部 N 数 据 部 分选项IPv6 数据报有效载荷041631版 本位目 的 地 址源 地 址下 一 个 首 部流 标 号12业务类型（128 位）（128 位）有 效 载 荷 长 度跳 数 限 制24有效载荷（扩展首部/数据）IPv6 的基本首部（40 B）IPv6 的有效载荷（至 64 KB）第68页/共126页6
32、9041631版 本位目 的 地 址源 地 址下 一 个 首 部流 标 号12业务类型（128 位）（128 位）有 效 载 荷 长 度跳 数 限 制24IPv6的基本首部40 B业务类型，流标号：提供QoS区分与支持第69页/共126页70并非所有的路由器能被同时更新无“标志日”IPv4和IPv6路由器混合将如何运行?隧道:在IPv路由器之间IPv6数据报作为IPv4数据报的负载 从IPv4到IPv6的迁移第70页/共126页71ABEFIPv6IPv6IPv6IPv6隧道逻辑视图:物理视图:ABEFIPv6IPv6IPv6IPv6CDIPv4IPv4流:X源:A目的:F数据流:X源:A目的
33、:F数据流:X源:A目的:F数据源:B目的:E流:X源:A目的:F数据源:B目的:EA-to-B:IPv6E-to-F:IPv6B-to-C:IPv6 在IPv4中B-to-C:IPv6 在IPv4中 隧道第71页/共126页724.1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP:网际协议4.5 选路算法4.6 互联网中选路4.7 广播和多播选路第72页/共126页73选路算法的图论抽象:图中的节点是路由器图中的边是物理链路链路代价:时延，费用或拥塞等级目的：决定从源到目的地通过网络的“好的路径”(路由器序列)选路 协议AEDCBF2213112535r“好的”路径:m通常
34、意味着最小费用的路径m其他定义也是可能的 选路第73页/共126页74全局的或分散的信息?分散的:路由器知道物理相连的邻居，到邻居的链路费用计算的迭代过程，与邻居交换信息“距离矢量”算法全局的:所有路由器具有完全的拓扑、链路费用信息“链路状态”算法s静态的或动态的?静态:路由随时间缓慢变化动态:路由更快地变化周期的更新适应链路费用变化 选路算法分类第74页/共126页75Dijkstra算法所有节点知道网络拓扑、链路费用经“链路状态广播”完成所有节点具有相同信息从一个节点(源)到所有其他节点计算最低费用路径给出对这些节点的转发表迭代:k次迭代后，得知到k个目的地的最低费用路径概念:c(x,y)
35、:从节点x到y的链路费用;=如果不是直接邻居D(v):从源到目的地v路径费用的当前值p(v):从源到v沿路径的前任节点N:已知在最小费用路径中的节点集合Dijkstra 迪杰斯特拉 链路状态算法第75页/共126页761 初始化: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的已知最短路费用*/15
36、 until 所有节点在 N中 Dijsktra算法第76页/共126页77步骤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算法:例子第77页/共126页78算法复杂性:n个节点每次迭代:需要检查所有节点w,不在N中n(n+1)/2 对比:O(n2)更有效的实现是可能的:O(nlogn)可能振荡:如链路费用=承载流量的量wzyx11+ee0e1100wzyx2+e000
37、1+e 1wzyx02+e1+e10 0wzyx2+e0e01+e 1最初 重计算选路 重计算重计算e11e11e11 Dijkstra算法,讨论第78页/共126页79Bellman-Ford方程(动态规划)定义dx(y):=从x到y最低费用路径的费用则dx(y)=min c(x,v)+dv(y)其中min对x的所有邻居 距离矢量算法第79页/共126页80u 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)=min 2+5,1+3,5+3 =4取最小
38、的节点是在最短路中的下一跳转发表B-F equation says:Bellman-Ford 例子第80页/共126页81基本思想:每个节点周期性的发送它自己的距离矢量估计到其邻居当节点x接收到来自邻居的新DV估计，它使用B-F方程更新其自己的DV:Dx(y)minvc(x,v)+Dv(y)for each node y N在规模较小、正常的条件下，估计值Dx(y)收敛在实际最小费用 dx(y)距离矢量算法第81页/共126页82迭代、异步:每次本地迭代由下列引起:本地链路费用改变DV从邻居更新报文分布式:每个节点仅当其DV改变时通知邻居如果必要，邻居则通知它们的邻居等待(来自邻居本地费用报文
39、的变化)重新计算 估计值如果到任何目的地的DV已经变化,通知 邻居 每个节点:距离矢量算法第82页/共126页83链路费用变化:好消息传播得快坏消息传播得慢“计数到无穷”问题!在算法稳定前，迭代44 次:参见课文xz1450y60 距离矢量:链路费用变化第83页/共126页84报文复杂性LS:对n个节点，E条链路,发送O(nE)报文 DV:仅在邻居之间交换收敛时间变化收敛速度LS:O(n2)算法要求 O(nE)报文可能具有振荡DV:收敛时间变化可能有选路环路计数到无穷问题健壮性:如果路由器异常，将发生什么现象?LS:节点可能通告不正确的链路费用每个节点仅计算它自己的表DV:DV节点通告不正确的
40、路径费用每个节点表能由其他人使用差错通过网络传播 LS和DV算法的比较第84页/共126页85规模:具有2亿个目的地:在选路表中不能存储所有的目的地!选路表交换将堵塞链路!管理自治互联网=网络的网络每个网络管理员可能要控制他自己网络中的选路我们的选路研究至此是理想的r所有路由器是等同的r网络“扁平”实践中并不真实 等级选路第85页/共126页86出于管理和扩展的目的，因特网可以被分割成许多不同的自治系统(autonomous system，AS)，换句话说，因特网是由很多自治系统汇集而成的从选路的角度来说，自治系统是指使用统一内部路由协议的一组网络自治系统内的选路协议(intra-AS)自治系
41、统间的选路协议(inter-AS)自治系统具有唯一的AS号（全球已分配几千个AS号，活跃的接近一千个）自治系统第86页/共126页873b1d3a1c2aAS3AS1AS21a2c2b1bAS内部选路 算法AS之间选路 算法转发表3c转发表由AS内部和AS之间的选路算法所配置AS内部设置内部目的地表项AS之间和AS内部对外部目的地设置表项 互联的AS第87页/共126页883b1d3a1c2aAS3AS1AS21a2c2b1b3c假定在AS1中的路由器接收目的地是AS1外部的数据报路由器应当将分组朝着网关路由器转发，但哪个呢？AS1需要:1.知道通过AS2可到达哪些目的地，通过AS3到达哪些2
42、.传播这些可达信息到AS1中所有路由器AS间选路的工作!AS间的任务第88页/共126页894.1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP:网际协议4.5 选路算法4.6 互联网中选路4.7 广播和多播选路第89页/共126页90用于自治系统内部的路由协议称为“内部网关协议”，简称 IGP(Interior Gateway Protocol)RIPOSPFEIGRP用于自治系统间接口上的路由协议称为“外部网关协议”，简称EGP(Exterior Gateway Protocol)BGP-4 选路协议第90页/共126页91路由信息协议 RIP 是内部网关协议 IGP中最
43、先得到广泛使用的协议。RIP 是一种分布式的基于距离向量的路由选择协议。路由信息协议RIP第91页/共126页92从一路由器到直接连接的网络的距离定义为 1。从一个路由器到非直接连接的网络的距离定义为所经过的路由器数加 1。RIP 协议中的“距离”也称为“跳数”(hop count)，因为每经过一个路由器，跳数就加 1。RIP认为一个好的路由就是它通过的路由器的数目少，即“距离短”。RIP允许一条路径最多只能包含 15 个路由器，“距离”的最大值为16 时即相当于不可达。“距离”的定义 第92页/共126页93仅和相邻路由器交换信息。交换的信息是当前本路由器所知道的全部信息，即自己的路由表。按
44、固定的时间间隔交换路由信息，例如，每隔 30 秒。RIP协议的三个要点 第93页/共126页94路由器在刚刚开始工作时，只知道到直接连接的网络的距离（此距离定义为1）。以后，每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息。经过若干次更新后，所有的路由器最终都会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器的地址。路由表的建立 第94页/共126页95收到相邻路由器（其地址为 X）的一个 RIP 报文：(1)先修改此 RIP 报文中的所有项目：将“下一跳”字段中的地址都改为 X，并将所有的“距离”字段的值加 1。(2)对修改后的 RIP 报文中的每一个项目，重复以下步骤：
45、若项目中的目的网络不在路由表中，则将该项目加到路由表中。否则 若下一跳字段给出的路由器地址是同样的，则将收到的项目替换原路由表中的项目。否则 若收到项目中的距离小于路由表中的距离，则进行更新，否则，什么也不做。(3)若 3 分钟还没有收到相邻路由器的更新路由表，则将此相邻路由器记为不可达的路由器，即将距离置为16（距离为16表示不可达）。(4)返回。距离向量算法 第95页/共126页961 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 一开始，各路由表只有到相邻路由器的信息网 3网 2网 4网 6网 5网 1“4”表示“从本路由
46、器到网 4”“1”表示“距离是 1”“”表示“直接交付”第96页/共126页971 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器 B 收到相邻路由器 A 和 C 的路由表网 3网 2网 4网 6网 5网 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后A 说：“我到网 1 的距离是 1。”因此 B 现在也可以到网 1，距离是 2，经过 A。”第97页/共126页981 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5
47、1 路由器 B 收到相邻路由器 A 和 C 的路由表网 3网 2网 4网 6网 5网 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后A 说：“我到网 2 的距离是 1。”因此 B 现在也可以到网 2，距离是 2，经过 A。”第98页/共126页991 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器 B 收到相邻路由器 A 和 C 的路由表网 3网 2网 4网 6网 5网 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后A 说：“我
48、到网 3 的距离是 1。”但 B 没有必要绕道经过路由器 A再到达网 3，因此这一项目不变。第99页/共126页1001 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器 B 收到相邻路由器 A 和 C 的路由表网 3网 2网 4网 6网 5网 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后C 说：“我到网 4 的距离是 1。”但 B 没有必要绕道经过路由器 C再到达网 4，因此这一项目不变。第100页/共126页1011 1 2 1 3 1 FEDCBA5 1 6 1 2 1
49、 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器 B 收到相邻路由器 A 和 C 的路由表网 3网 2网 4网 6网 5网 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后C 说：“我到网 6 的距离是 1。”因此 B 现在也可以到网 6，距离是 2，经过 C。”第101页/共126页102最终所有的路由器的路由表都更新了FEDCBA1 1 2 1 3 1 4 2 B5 2 E6 3 B1 1 2 2 A3 2 A4 3 A5 1 6 2 F1 2 E2 2 D3 3 C4 2 C5 1 6 1 1 3 B2 3 B3 2 B4 1
50、 5 2 F6 1 网 2网 6网 5网 1网 3网 41 2 A2 1 3 2 A4 3 A5 1 6 2 F1 2 A2 2 A3 1 4 1 5 3 C6 2 C第102页/共126页103假设网络中的路由器D中的转发表如左图 练习现在，路由器D收到来自B的RIP通告右图。试给出路由器D更新后的转发表。第103页/共126页104 4 字节RIP 报文路由信息（20 字节/路由）可重复出现最多 25 个IP 数据报路由标记网络地址地址族标识符距离(1-16)IP 首部UDP 首部首部路由部分必为 0版本命令 4 字节子网掩码下一跳路由器地址UDP 用户数据报 RIP2协议的报文格式 RI