通信网理论基础(第三章).ppt

2019 12 20 1 通信网理论基础第三章Internet的路由 拥塞控制和管理朱骏 2019 12 20 2 一 路由和路由协议 路由 因特网中分组的路径 称为路由 它由路由器决定 路由器 路由器是一种具有多个输入端口和多个输出端口的专用计算机 它的任务是转发分组 即将路由器某个输入端口收到的分组 按照其目的地址 目的网络和主机地址 将该分组由每个合适的输出端口转发给下一跳路由器 下一跳路由器也按照同样的方法处理分组 直到分组到达目的地为止 2019 12 20 3 典型的路由器的结构 图中的数字1 2 3表示相应层次的构件 2019 12 20 4 路由器在计算机网络中的作用 完成路由选择 并把分组发往所选择的相应的链路 2019 12 20 5 路由器的结构 路由器可以分为两个部分 即路由选择和分组转发部分 路由选择部分是控制部分 其核心构件是路由选择处理机 路由选择处理机的任务是根据所选定的路由选择协议构造出路由表 同时经常或定期地和相邻地路由器交换路由信息 更新和维护路由表 分组转发部分 由三部分组成 交换结构 一组 输入端口 一组 输出端口 2019 12 20 6 交换结构 又称为交换组织 其作用是根据转发表 forwardingtable 对分组进行处理 将某个输入端口进入地分组 选择一个合适地输出端口发送出去 路由器地输入端和输出端中地1 2 3 表示物理层 数据链路层和网络层的处理模块 2019 12 20 7 物理层 负责数据比特的接收 数据链路层 按照链路层的协议接收分组的帧 将帧的头部和尾部剥去之后 分组送入网络层的处理模块 2019 12 20 8 网络层 数据链路层发来的分组 分为两类 分组是路由器之间交换路由信息的信息 如路由信息协议RIP或开放最短通路优先OSPF分组 则将这种信息送路由选择处理机 分组是数据 则按照分组首部中的目的地址查找转发表 根据找出的结果 分组经过交换结构到达还是的输出端口 2019 12 20 9 由上面的分析可以看出 路由器的工作原理并不复杂 但是要求的工作速度非常高 例如线路的传送速度是2 5Gb S 分组长度为256字节 分组 这时路由器需要处理分组的速度 2 5 10000000000 256 8 1000000 分组 这个速度称为线速 是非常大的 这个数字也称为Mpps 百万分组每秒 说明路由器对接收的分组的处理速率 是路由器的重要指标 2019 12 20 10 其次 当一个分组在查找转发表时 也就是路由器在处理第一个分组时 输入端又会收到另一个分组 这个分组就必须在输入端口中排队等待 造成了路由器对于分组的延迟 即时延 2019 12 20 11 路由器的输出端从交换结构接收分组 然后将它们发送到路由器输出端连接的线路上 2019 12 20 12 当交换结构送来的分组的速率超过输出链路发送的速率时 来不及发送的分组就必须暂时存放在缓存中排队 等待发送 数据链路层给分组加上链路层的首部和尾部 交给物理层发送出去 2019 12 20 13 路由器的交换结构 交换结构是路由器的关键部件 其任务是将分组从每一个输入口转移到选定的输出端口 实现路由器的交换功能的方法有多种 例如 通过存储器 通过总线 通过互联网络都可以实现 2019 12 20 14 2019 12 20 15 通过存储器的交换方法 路由器的每个输入端口收到一个分组时 将完成以下的动作 用中断方式通知路由选择处理机 分组从输入端口复制到存储器中 路由器从分组的首部提取目的地址 查找路由表 选定输出端口 分组送到输出端口的缓存 2019 12 20 16 此时路由器的转发速度 交换速率 取决于存储器的读写时间 称为存储器的带宽 例如CISCO的Catalyst8500 BayNetwor的Accelar1200系列就是采用存储器转发的 2019 12 20 17 通过总线的交换方法 路由器的每个输入端口收到一个分组时 路由选择处理机即从分组中提取其首部地址 然后把分组直接发送到选定的输出端口去 由于总线是共享的 同一时刻只允许一个分组在总线上传送 所以路由器的转发带宽受到总线速率的限制 例如CISCO的Catalyst1900系列是通过总线转发的 2019 12 20 18 通过互连 连接 网络的交换方法 网络有2N条总线 其中水平方向和垂直方向个有N条总线 并且彼此分别连接 路由器接收到的分组经目的地址的提取 分别送到相应的水平总线 与相应的垂直总线相连 如果垂直总线空闲 则分组转发 否则等待 例如CISCOCatalyst12000 使用的互联网的带宽可以高达60Gb S 2019 12 20 19 因特网的网际协议IP TCP IP协议即传输控制协议 网际协议 TCP IP与OSI体系结构的比较 2019 12 20 20 互联网协议的组成 2019 12 20 21 与IP协议配套使用的四个协议 地址解析协议ARP AddressResolutionProtocol 逆地址解析协议RARP ReverseAddressResolutionProtocol 因特网控制报文协议ICMP InternetControlMessageProtocol 因特网组管理协议IGMP InternetGroupManagementProtocol 2019 12 20 22 TCP IP协议中 IP协议负责网络互连的网络层的核心协议 TCP协议则是与IP协议配套使用的运输层的一个协议 严格说来 TCP协议与网络互连并没有直接的关系 但是TCP协议对保证互联网络中端到端的可靠传输起到非常重要的作用 2019 12 20 23 互联网的IP地址 IPv4协议是给因特网上每一个主机分配一个唯一的 独享的32位 bit 的地址标识 以便在因特网上方便地寻址 IP地址由ICANN InternetCorporationAssignetandNumbers 负责分配 国内的用户地址由APNIC AsiaPasificNetworkInformationCenter 分配 2019 12 20 24 IP地址的编址方法 经历了三个阶段 1 分类的IP地址 1981年通过标准协议 2 子网的划分 对方法1的改进 1985年通过标准协议 3 构成超网 比较新的无分类编址方法 1993年以后很快得到应用 2019 12 20 25 网络的设备 都有 域名 这是表示某一个网络设备的名称 中英文皆可 但是这不是地址 如同南京邮电大学是名称 域名 而新模范马路66号则是地址 当然这两者都是唯一的 不应该有重复的 但是一个域名可以有几个地址 如三牌楼校区和仙林校区 也可以连接不同的网络 此时应该分配不同网络的IP地址 如南邮目前连接的两个路由 CERNET和CHINANET 2019 12 20 26 1 分类的IP地址 将IP地址划分位若干固定的类 每一类地址都由两个固定的长度的字段 网号net id和主机号host id 组成 其中网号标志主机和路由器连接的网络主机号标志该主机 有了这两个信息 任何一个主机在网络上的位置就确定了 2019 12 20 27 分类的IP地址结构 2019 12 20 28 路由器在转发分组而查找转发表时 只需要提取其中的网络地址 及网号即可 不必过问主机号 这样可以提高速度 节省时间 只有到达目的地址的网络后 才由该网络转发给相应的主机 这时才需要提取主机号以便交付该主机 2019 12 20 29 为了便于使用32位 bit 的IP地址 往往采用 点分十进制记法 dotteddecimalnotation 2019 12 20 30 IP地址的使用范围 2019 12 20 31 A类地址 net id7位 可供使用的网络号128 2 126个 原因是IP地址中的全0表示 this 意思为 本网络 00000000为保留地址 可以用作源地址 但是不得用作目的地址 此外 全1 即01111111用作本地软件的环回测试 loopbacktest 本主机用 此时后三个字节的二进制数字可以是全0和全1以外的任何数 2019 12 20 32 每个网络中最大的主机数 应该是主机号位数的容量 2 这是因为主机号全0表示IP地址是本主机所连接到的单个网络 而全1表示all即广播该网络上的所有主机 2019 12 20 33 B类和C类地址中net id没有 2的问题 因为此时整个net id字段是10 B类 或110 C类 开头 不可能是全1或全0 一般不使用的特殊的IP地址 A 2019 12 20 34 IP地址与硬件地址 硬件地址也称物理地址 它是数据链路层和物理层使用的地址 IP地址则是网络层及以上各层使用的地址 2019 12 20 35 由上图可见 IP地址是放在IP数据包的首部 而硬件地址则是放在数据链路层中MAC帧的首部 当IP数据报放入数据链路层的MAC帧中以后 整个的IP数据报就成为MAC帧的数据 所以在数据链路层是看不到数据包的IP地址的 2019 12 20 36 计算机网络的通信示例 2019 12 20 37 下表中不同层次 不同区间的源地址和目的地址 说明IP地址和硬件地址的不同及使用 2019 12 20 38 注意 1 在整个因特网中 IP的数据包 其首部中的源地址和目的地址始终是IP1和IP2 网络中数据包尽管要经过多个路由器转发 但是与这些路由器的IP地址无关 2 路由器只根据IP数据包的目的地址的网络号进行路由选择 2019 12 20 39 3 具体传送IP数据包的物理网络 在其数据链路层只能看见MAC帧 IP数据包被封装在MAC帧中 MAC帧在传送过程中 在不同的MAC帧中的硬件地址是不断变化的 以完成从一个路由器向下一个路由器的转发 2019 12 20 40 4 数据包的IP地址和网络的硬件地址是两套体系 但是由于因特网的IP层屏蔽了下层的硬件地址 使得我们在讨论许多问题时可以把问题放在网络层之上 可以使用统一的 抽象的IP地址研究网络 主机和路由器之间的通信 从而使得问题大大简化 2019 12 20 41 从上面的分析可以看出 实际上在网络上传送数据包时 使用的是主机的硬件地址 它根据IP地址引导IP包的传送 由此可见 IP地址有以下几个特点 1 分级的地址结构 2 IP地址表示主机 路由器与链路的接口 3 网桥 转发器连接 在同一个网络 网号相同 4 网络是平等的 不论是A B C类网络 2019 12 20 42 IP地址和邮件地址 但是 硬件地址是随着主机 路由器等设备的情况而变化的 例如新的主机的加入 原有主机的调整 更换网卡等都会使得网络设备硬件地址的改变 那么硬件地址和IP地址时如何联系的呢 2019 12 20 43 IP地址是32位的 硬件地址则是48位的 这两者的联系是在网络的主机中存放一个从IP地址到硬件地址的映射表 由因特网的地址解析协议ARP解决 首先 每个主机中都有一个ARP高速缓存 ARPcache ARP高速缓存中存有所在局域网上各主机和路由器的IP地址到硬件地址的映射表 2019 12 20 44 主机A欲向本局域网上另一个主机B发送数据包时 就先在其ARP高速缓存中查找主机B的IP地址 并且查出其对应的硬件地址 把它写入MAC帧 通过局域网将该MAC帧发往主机B的硬件地址 2019 12 20 45 如果在主机A的高速缓存中查不到主机B的IP地址 则主机A可以按照以下的步骤进行 ARP进程在本局域网上发送一个ARP请求分组 其内容是 我的IP地址是209 0 0 5 硬件地址是00 00 C0 15 AD 18 我想要知道IP地址为209 0 0 6的主机的硬件地址 本局域网上所有的主机上运行的ARP进程都可以收到此请求 2019 12 20 46 主机B在ARP请求分组中看到自己的IP地址 即向主机A发送ARP相应分组 并且写入自己的硬件地址通知A 即回答 我的IP地址是206 0 0 6 硬件地址是08 00 2B 00 EE 0A 而局域网上其他的主机对此请求分组不予理睬 主机A收到主机B的响应分组以后 在其ARP高速缓存中写入主机B的IP地址到硬件地址的映射 2019 12 20 47 2019 12 20 48 如果所要找的主机和主机A不在同一个局域网上 此时不在同一个局域网上的两个主机不需要使用ARP协议 而是主机A将数据包发送到与该主机A在同一个局域网上的路由器 而该路由器又与下一个局域网的路由器相连 这两个路由器可以使用ARP协议解析其硬件地址 2019 12 20 49 另外 如果不使用IP地址 直接使用硬件地址 可否进行计算机网络的通信呢 答案是否定的 因为网络太大 设备太多 网络的调整 主机的变化又非常频繁 如果只使用硬件地址 就非常复杂 但是 引入IP地址之后 在传输上使用硬件地址 在管理上使用IP地址 由计算机自动转换 就非常方便 2019 12 20 50 由以上的分析可见 在物理层和数据链路层 网络对于数据包的传送 是使用的硬件地址 但是这是由主机 路由器等硬件设备自动处理的 在网络层以上 即用户和维护人员介入的层面 网络使用便于分析 应用的IP地址 非常方便 而这两者之间的联系和转换 则由地址解析协议ARP完成 这就如同我们在使用计算机时 内存 缓存 硬盘等的地址 都是二进制管理的 但是用户介入的则是地址代码 两者之间由操作系统负责管理 道理都是一样的 在计算机和网络的其他系统 使用中 类似的例子还很多 2019 12 20 51 IPv4 2019 12 20 52 IP层转发分组的流程和算法 IP层转发分组流程 下图为路由表和分组转发的过程 图中有4个A类网络 通过3台路由器连接 2019 12 20 53 由于是A类网络 故每个网络上的主机 可能多达上万台 每台主机均有其IP地址 所以路由表极大 如果按照主机所在的网络地址来制作路由表 由于只有4个网络 所以每台路由器只需要判断目的地址主机在哪一个网络即可决定该分组的交付地址 故路由器的判断内容只有4个 2019 12 20 54 以路由器R2为例 可得R2的路由表为图 a 所示 由于R2直接连接在网络2和网络3上 所以所有目的地址为网络2和网络3的分组 均可直接交付 而目的地址为网络1和网络4的分组 可以选择下一跳的路由器为R1和R3 2019 12 20 55 上述路由器连接的网络可以简化为下图 图 b 将网络简化 2019 12 20 56 所以 不是按照主机地址 而是按照网络地址来制作路由表 网络及其寻址将变得非常简单 路由表也非常简单 在路由表中 每一条路由的内容主要是 目的网络地址 下一跳地址 2019 12 20 57 由此 根据分组的目的网络地址寻找和确定下一跳路由器的方法 1 IP数据包首先确定目的主机所在目的网络的路由器 间接交付 2 分组到达最后一个路由器 即目的主机所在网络连接的路由器时 将直接交付 2019 12 20 58 基于分组目的网络的地址的IP层的分组转发算法为 1 从数据报的首部提取目的地址D 得出其目的网络地址N 2 若N就是此路由器直接连接的网络 为直接交付 不需要在转发到其他路由器 通过该网络将数据报交付给目的站D 否则是间接交付 执行 3 2019 12 20 59 3 若路由表中有目的地址D的特定主机的路由 将数据报传送给路由表所指明的下一跳路由器 否则执行 4 4 若路由器中有到达网络N的路由 将数据报传送给路由表中所指明的下一跳路由器 否则执行 5 5 若路由器中有一个默认路由 则将数据报传送给路由表中指明的默认路由器 否则执 6 6 报告转发分组出错 2019 12 20 60 2 划分子网 分类的IP地址是基本的编址和使用方法 使用方便 有很多优越性 但是也有不少缺点 IP地址空间的利用率有时很低 原因是A类地址 主机号host id有24位 可以容纳的数量超过1000万 B类地址的容量也超过6万 host id有16位 但是一般的网络从实际使用量和网络允许的节点数而言 根本达不到这样的数量 造成IP地址的资源浪费和紧张 2019 12 20 61 例如 使用B类地址的因特网 原来对网上节点的数量的限制 也就在1024台左右 这样对于6万多个地址 使用率还不到2 而其他用户的局域网又不可能使用这些地址 而许多用户考虑到网络的发展 又不肯使用C类地址 资料报道 半数以上的B类网络其主机数量还不到50台 可见浪费之大 另一个原因 同一个局域网上按照大量的主机 数万 十万 百万以上时 网络管理难度很大 也会造成网络内部的阻塞 吞吐量的下降 2019 12 20 62 给每一个物理网络分配一个网络号 会因为路由表太大 使得网络的性能变坏 因为每一个路由器都需要从路由表中查出如何到达其他网络的下一跳的路由器 所以 互联网中的网络数越多 路由器中路由表的项目数也越多 这样即使我们拥有足够多的IP地址资源可以给每一个物理网络分配一个网络号 也会导致路由表过分复杂和查找费时 使得路由器和整个网络的性能大大下降 2019 12 20 63 两级IP地址不够灵活 因为一个新的网络的连接 其先决条件是申请到新的IP地址 即使这个网络所在的单位可能已经拥有一个网络 也就是说 一个单位不可能随时随地灵活地增加本单位的网络 而不必事先到因特网管理部门去申请新的网络号 2019 12 20 64 为了解决上述问题 1985年起 在IP地址中增加了 子网号网段 使得两级的IP地址结构变成三级的IP地址结构 这种子法就是 划分子网 subneting 也称为 子网寻址 子网路由选择 2019 12 20 65 基本思路 一个单位可以把自己的物理网络划分为若干子网 subnet 子网的划分只对单位内部有意义 与网络以外没有关系 划分子网的方法是 从网络的主机号借用若干比特作为子网号 因为子网的划分是对内 不对外的 所以只能从主机号借用 此时主机号将减少相应的比特数 因此 原来两级的IP地址在本单位内部就变成了三级的IP地址 IP地址 网络号 子网号 主机号 2019 12 20 66 从外部网络发来的IP数据包 仍然根据IP数据包的网络号net id寻址 直到本单位网络上的路由器 该路由器收到数据包以后 按照net id和subnet id寻址目的网络的子网 再将IP数据包交付给目的主机 2019 12 20 67 下图为某B类网络的寻址过程 没有划分子网 2019 12 20 68 将上图网络划分为三个子网时的寻址过程 将上图的网络分为三个子网 但对外仍是一个网络 2019 12 20 69 对划分子网的改进 对IP网络划分子网以后 遇到的问题是子网上的主机和路由器在通信时都必须通过主网的路由器 R1 这种方式效率很低 同时 若干单位不可能各自使用子网 再组成一个主网 为此还需要解决子网独立自主连接到因特网 使得子网上的主机通过本子网上的路由器直接和外界通信 这种方式的实质 是把子网直接连接到因特网 并且完成在因特网上的寻址和通信 需要完成的任务是 如何把子网反映或者是映射到因特网上去 2019 12 20 70 解决的办法 是提出和采用 子网掩码 的概念和方法 在两级IP地址的方法中 32位的二进制的IP地址 可以分为网络号 net id 和主机号 host id 两个部分 在A B C几类不同的地址中 网络号和主机号部分所占的长度各不相同 但是其位数的和是32位 子网号 subnet id 是从主机号中借用若干位来的 现在的问题是 已有的地址位数中无法识别子网号究竟是那几位 子网号长度是多少 为了解决这个问题 提出了 子网掩码 的概念 2019 12 20 71 子网掩码 是32位的二进制数字 其特点是 对应于各类IP地址中网络号 net id 和子网号 subnet id 部分皆为1 余下的主机号 host id 部分为0 或者说 网络号字段为1 主机号字段为0的二进制数 就是 子网掩码 2019 12 20 72 子网掩码 如何解决提示子网号 subnet id 的问题呢 把 子网掩码 与某IP地址相 与 相应各位作二进制数的与运算 即AND运算 其结果必然是 网络号部分 含网络号 子网号 为该IP地址的网络部分数字 含借用的主机号用作子网号的部分 余下的主机号部分为0 2019 12 20 73 2019 12 20 74 使用了子网号的IP地址就变成 三级IP地址 使用子网掩码的好处是 不管网络有没有划分子网 也不管网络字段net id的长度是几个字节 对应不同的A B C类地址 只要将子网掩码和IP地址进行逐位的 与 AND 运算 就立即可以得出网络地址来 于是就解决了路由器处理接收到的分组时可以立即得出网络号和子网号 2019 12 20 75 目前 因特网的标准已经规定 所有的网络都必须有一个子网掩码 同时在路由器的路由表中也必须有子网掩码这一栏 如果一个网络不划分子网 则该网络的子网掩码就使用 默认子网掩码 默认子网掩码 中1比特的位置和IP地址中的网络号字段是相对应的 这样 子网掩码 也可以用于不划分子网的网络 而很方便的取出其网络号 并且判明是哪一类地址 2019 12 20 76 2019 12 20 77 显然 A类地址的默认子网掩码是255 0 0 0 或FF000000 B类地址的默认子网掩码是255 255 0 0 或FFFF0000 C类地址的默认子网掩码是255 255 255 0或FFFFFF00 子网掩码是一个网络或子网的重要的属性 2019 12 20 78 关于子网掩码的使用 一台路由器在和相邻的路由器交换路由信息时 必须将自己所在网络 或子网 的子网掩码告诉相邻的路由器 在路由器的路由表中 需要给出目的网络的地址 以及该网络的子网掩码 如果一个路由器连接在两个子网上 就必须拥有两个网络地址和两个子网掩码 2019 12 20 79 子网划分的方法 并无限制 子网所占比特数多 则主机数占比特数就少 此时可以划分子网的数目就多 但是每个子网可以容纳的主机数量就少 反之 子网所占比特数少 则主机数占比特数就多 此时可以划分子网的说明就少 但是每个子网可以容纳的主机数量就多 2019 12 20 80 由于子网划分时 可以任意选择其位数 所以通常子网有多种划分的方法 但是 采用固定长度子网时 所划分出的所有的子网 其子网掩码是相同的 2019 12 20 81 下表为B类地址的子网划分选择 2019 12 20 82 使用子网掩码的分组转发过程 在使用子网掩码的情况下 从数据包的IP地址中无法唯一的确定其网络地址 原因是数据包的首部例并没有提供子网掩码的信息 为此 需要制定新的寻址算法 2019 12 20 83 2019 12 20 84 从图中的地址表示和路由表可以看出 使用子网掩码后 路由表中每行信息的内容 包括 目的网络地址 子网掩码 下一跳地址 图中有3个子网 即子网1 子网2 子网3 每个子网上有两台主机 其中一台分别是H1 H2 H3 2019 12 20 85 若某一主机H1要向另一个主机发送分组 首先主机H1应判断该分组的目的地址与H1是否在同一个子网内 如果在同一子网内 则H1可以将该分组直接交付目的主机 这称为直接交付 如果目的地址与H1不在同一子网内 则H1应该将该分组交给本子网上连接的一个路由器转发 这称为间接交付 2019 12 20 86 如何判断待发的分组与H1是否在同一个子网上呢 方法是将分组的目的地址与主机H1自己的子网掩码逐比特相 与 若结果等于H1的网络地址 说明目的地址与H1在同一个子网上 否则 两者不在同一个子网上 2019 12 20 87 例 上图中 主机H1 网络地址 128 30 33 0 子网掩码 255 255 255 128 要向主机H2 IP地址 128 30 33 138 网络地址 128 30 33 128 子网掩码 255 255 255 128 发一个分组 2019 12 20 88 主机H1操作 将本子网的子网掩码255 255 255 128与目的主机H2的IP地址128 30 33 138逐位相 与 即 11111111111111111111111110000000与10000000000111100010000110001010相与 得 10000000000111100010000110000000 即128 30 33 128 与H1的网络地址不同 所以 不能直接交付 需要通过子网上的默认路由器R1 由R1转发 2019 12 20 89 路由器在收到一个分组以后 如何查找路由 路由器R1收到的分组目的地址 128 30 33 138 路由器查找路由表 先查路由表第一行的子网掩码 255 255 255 128 两数相与 1000000000111100010000110001010 11111111111111111111111110000000 结果为 1000000000111100010000110000000 为128 30 33 128 与路由表第一行目的网络地址不同 说明子网1不是该分组的目的地址 2019 12 20 90 次查路由表第二行的子网掩码 255 255 255 128 相与 结果为 128 30 33 128 与第二行的目的地址相匹配 说明子网2就是该分组的目的地址 则路由器R1从其输出口将分组直接交付主机H2 2019 12 20 91 小结 划分子网的情况下 路由器转发分组算法 1 从收到的IP数据包的首部提取目的地址D 由D的分析可以得出目的网络的地址N 2 先判断分组是否直接交付 即分组的目的地址是否就是本路由器连接的主机 方法 将路由表中各网络子网掩码和D逐比特相 与 结果与该网络的网络地址是否匹配 若匹配 目的地址是本网络 该分组直接交付 将网络地址D转换成物理地址 否则是间接交付 转下步 2019 12 20 92 3 若路由表中有目的地址为D的特定的主机路由 则将数据报传送给路由表中指明的下一跳路由器 否则转下一步 4 4 对路由表中的每一行 目的网络地址 子网掩码 下一跳地址 将其中的子网掩码和D逐比特相 与 结果若与该行目的网络地址匹配 则将分组传送给该行指明的下一跳路由器 否则转 5 2019 12 20 93 5 若路由表中有一个默认路由 则将该数据报传送给路由表指明的默认路由器 否则转 6 6 报告转发分组出错 2019 12 20 94 由上可见 分组在每个路由器中的处理 如果分组的目的地址不是本网络 那么就应该根据其目的地址的指向转交下一跳路由器 这需要查找路由表 路由表将指示送达一定方向的分组归属哪一个路由器 其过程 2019 12 20 95 本路由器根据分组中的目的IP地址 查找出相应的下一跳路由器 不一定是目的地址所属的路由器 的IP地址 启动下层网络接口软件 网络接口软件将下一跳路由器的IP地址 用地址解析协议ARP转换成硬件地址 并且将该硬件地址送入数据链路层MAC帧的首部 在由该硬件地址寻找下一跳路由器 路由器就是反复地进行这样地工作 需要注意地是 路由器完成这样的工作 是需要时间的 也就是说需要一定的开销 2019 12 20 96 3 构造超网 划分子网可以提高IP地址的利用率 但是并没有从根本上解决IP地址的资源短缺和利用率不高的问题 为此采取的措施是 使用变长子网掩码VLSM VariableLengthSubnetMask 无分类编址法 无分类域间路由选择CIDRClasslessInter DomainRouting 2019 12 20 97 无分类编址法CIDR 1 无分类编址法取消了A B C的地址分类和子网的划分 而是使用变长的 网络前缀 network prefix 代替原来的网络号和子网号 使得对于IP地址的长度的使用更加灵活 避免了浪费 2019 12 20 98 2 CIDR把网络前缀相同的 连续的IP地址组成 CIDR地址块 一个CIDR地址块可以表示很多地址 这些地址是连续的 更重要的是 下一跳路由器 是相同的 这样就可以把组成CIDR地址块的这些地址组成一个 路由聚合 这样就可以使得原来在路由表中分别表示的一组 比较多 例如数千个 的IP地址 用一个路由聚合就可以表示了 这样就大大简化了路由表 2019 12 20 99 路由聚合就是 构成超网 因为这时一个CIDR地址块形成的地址簇 实际上是众多的网络地址 2019 12 20 100 超网的表示法 CIDR不再使用子网的概念和划分 也不再使用子网掩码的方法 为了区分起见 使用CIDR的网络采用 斜线记法 slashnotation 表示超网 IP地址 网络前缀 主机号 这样 IP地址的划分 从使用子网掩码的三级编址 简化为两级编址 2019 12 20 101 为了与使用子网掩码的三级编址区分 CIDR在IP地址的后面加上斜线 其后注明网络前缀所占的比特数 即网络号使用的地址位的长度 例如 128 14 46 30 20即表示 IP地址32位 其中前20位表示网络前缀 后12位为主机号 2019 12 20 102 由于超网中网络前缀表示的网络号的长度不是固定的 所以在超网中 如果仍然采用点分十进制的记法 有时反而看不清网络号和主机号 此时可将IP地址用二进制表示 如128 14 46 34 20即表示 10000000000011100010111000100010 这里 前20位即网络前缀 后12位为主机号 2019 12 20 103 CIDR地址块的表示 CIDR地址块用地址块的起始地址 地址个数表示 上述的加斜线的点分十进制记法 就可以表示地址块 例如 128 14 32 0 20表示 该地址块的网络号有20位 主机号的长度为12位 可以容纳122个地址 2019 12 20 104 路由协议 Internet体系结构 与交换网类似 Internet的通信主体是终端 协助完成通信的还有网络节点 交换网中网络节点 就是交换机 Internet网中是主机 即节点机 网络节点的作用是完成通信设备的接入和交换 在Internet中是完成数据包的转发 完成数据包的转发 显然是要确定目的地址 或者是明确数据包转发的方向 即路由 2019 12 20 105 Internet中节点设备包括节点计算机 完成本地终端的接入 信息的传送 路由器 完成途经本地的数据包的转发 因此 整个Internet网络实际上是由路由器互相连接起来的 但是每个路由器又需要与本地网络节点的计算机主机相连接 以完成本地终端的接入 信息的接收 发送和终端设备的管理 Internet是一个基于路由器的数据通信网络 2019 12 20 106 Internet网络的结构特点 2019 12 20 107 从网络的协议层次来看 Internet网络执行TCP IP协议 特点是 网络层以下为了实现不同物理介质 接口 信号之间的连接 是以IP包的形式来屏蔽各个终端差异的 这种方法适宜异种网络之间的互连 但是协议是不可靠的 网络层则是决定传输分组的路由的转发 网络层以上则并不涉及 2019 12 20 108 2019 12 20 109 由上可见 路由器实际上是把网络节点中执行分组数据包的地址解析 选择路由 完成转发的作用独立出来 让节点机只完成终端的接入 信息的接收 发送和终端设备的管理 以减轻节点机的负担 路由器完成分组的转发 是根据路由表进行的 路由表实际上是把路由器收到的分组按照不同的方向进行转发的方向路径的描述 2019 12 20 110 一般的理解 路由器的工作包括 设置路由表 明确指出本路由器收到的分组 按照不同的目的地址 应该向网络的哪个节点转发 即路由表的建立 完成路由表的查找 路由表的维护和更新 2019 12 20 111 由6个网络组成的系统 2019 12 20 112 例 上图为Internet路由表的组织某网络一主机的IP地址 166 111 81 16 0 xa66f5110 网号为 166 111 64 0 0 xa66f4000 高19位 为其网络地址 由6个网络组成的系统 图 a 路由器G1的路由表 图 b 2019 12 20 113 分组到该网络地址所指定的网络时 将视为到达终点的目的地址 将寻找向Internet后一个路由器时 为到达目的地址 之前的所有的路由器只关心处于高位的网络地址 只有这个路由器才关心其中的主机地址 并且利用ARP地址解析协议把目的地址转化为物理地址 把IP分组发送给目的地址的主机 所以路由表的表项只需要保留目的主机的网络地址 而不是主机的IP地址 这样可以使得路由表的规模小一些 查表的速度加快 2019 12 20 114 最长前缀匹配 路由器在查找路由表时 查找的网络号 也称为 网络前缀 由 网络前缀 可以确定 下一跳地址 路由器在查找路由表时 可能会得到多个匹配的结果 最后的 下一跳地址 应该如何确定呢 答案是应该从匹配结果中选择具有最长网络前缀的路由 即最长前缀匹配 Longest prefixmatching 2019 12 20 115 最长前缀匹配 原因是网络前缀越长 其地址快就越小 路由就越具体 more specific 最长前缀匹配又称为最长匹配或最佳匹配 例 假定某大学所属的四系 希望ISP 因特网服务提供者 将发给四系的数据报直接发四系 而不经过大学的路由器 但是又不愿意改变自己原来使用的IP地址块 2019 12 20 116 最长前缀匹配 为此 在ISP的路由器的路由表中 需要分别设置大学和四系两个项目 以便具体操作 例如设置 大学 206 0 68 0 22 四系 206 0 71 128 25 若ISP收到一个数据报 其目的地址为 D 206 0 71 130 2019 12 20 117 最长前缀匹配 将D 206 0 71 130和路由表中这两个项目的掩码逐比特相与 结果为 大学 11111111111111111111110000000000四系 11111111111111111111111110000000结果 大学 206 0 68 0 22 四系 206 0 71 128 25 2019 12 20 118 最长前缀匹配 于是 同一个IP地址D可以在路由表中找到两个目的网络 即大学和四系的网络地址与其相匹配 根据最长前缀匹配的原理 应该选择具有25位网络前缀的四系的网络地址作目的地址 这也是一个道理 网络前缀越长 其地址块就越小 路由就越具体 2019 12 20 119 最长前缀匹配的应用 根据以上的原理 如果IP地址的分配一开始就采用CIDR 那么就可以按照网络所在地地理位置来分配地址块 这样就可以大大减少路由表中的项目 例如 可以将世界划分为四大地区 某一个地区分配一个CIDR地址块 194 7 194 0 0 0 195 255 255 255 分配给欧洲198 7 198 0 0 0 199 255 255 255 给北美洲200 7 200 0 0 0 201 255 255 255 给中南美202 7 202 0 0 0 203 255 255 255 给亚太地区 2019 12 20 120 最长前缀匹配 以上每个地址块约包含3200万个地址 这种分配方法使得IP地址与地理位置相关联 好处是可以大大压缩路由表中的项目数 例如从中国发往北美的数据报 地址是198 7 中的任何一个 都可以先送往美国的一个路由器 有它转发 而不必了解这一地址究竟在何处 于是路由表中的内容被大大压缩 2019 12 20 121 路由表的查找 路由表的查找 主要是减少查表的次数 也就减少查找的时间 无分类编址的路由表通常存放在一种层次的数据结构中 然后自下而上 按层次查找 最长用的方法是 二叉线索 法 2019 12 20 122 理想的路由算法 理想的路由算法应该具有以下的特点 1 算法必须是正确的 完善的 分组沿着路由表所指示的路由 一定可以最终到达目的网络和目的主机 2 算法在计算上应该简单 路由的计算会增加路由器的工作量 增加额外的开销 需要使用网络其他路由器发来的大量额状态信息 必然导致分组的时延 2019 12 20 123 3 算法应该能适应通信量和网络拓扑的变化 即有自适应性 当网络中的通信量发生变化时 算法应该能够自适应地改变路由 以均衡各个链路地负载 当某个或某些节点 链路发生故障不能工作时 或者经维护以后 再次投入工作时 算法能够即时改变路由 这也称为算法的稳健性 2019 12 20 124 4 算法应该具有稳定性 在网络通信量和网络拓扑相对稳定的情况下 路由算法应收敛于一个可以接受的解 而不应该使得指出的路由不停地变化 5 算法应该是公平的 算法对于所有的用户 出极少数优先级高的用户 都是平等的 例如使某一对用户的端到端时延最小时 不应该影响到其他的用户端 2019 12 20 125 6 算法应该是最佳的 即以最低的代价实现路由算法 这里的大家 可以是成本费用 也可以是综合性的 如链路长度 数据率 链路容量 是否需要保密 传播时延到 还可以是某一特定时间内的通信量 节点的缓存杯占用的程度 链路的差错率等 由此可见 实际上 所谓 最佳路由 只能是相对于某一特定要求下得出的较为合理的选择 2019 12 20 126 二 Internet的路由结构 自治系统的概念 源地址发出的和路由器转发的分组 只要指名下一跳的路由器的地址即可 这样即可采取 步步逼近 的方法 最终到达目的地址 2019 12 20 127 例如 从南邮发出的分组 只要判明是1 到南邮的 不必出校园网 网内转交 2 到其他高校的 送SERNET 到达东大以后 根据目的地址 可以分送上海 北京等地 去其他城市的 可以经北京转发 3 到其他地址的 送电信的INTERNET 即CHINANET 2019 12 20 128 到达电信网 则根据目的地址 可以送相应的大区 省会 省辖市 国外 但是由于电信的因特网连接的网址很多 因此 在电信网上的路由分配和转发是比较复杂的 2019 12 20 129 例如 南京电信 路由有 南京 北京 上海 沈阳 西安 成都 广州 武汉 八大一级交换中心的骨干网专线 南京 合肥 杭州 南昌 济南 郑州等附近省会城市的骨干网专线 南京 苏州 无锡 常州 镇江 扬州 泰州 南通 淮安 盐城 宿迁 徐州 连云港等其他12个省辖市的省内骨干网专线 2019 12 20 130 路由举例 南京有南京电信与南京网通 南京联通 南京移动 CERNET 教育科研网 南京广电等其他运营商的网络连接 南京有市内各个政府部门的信息系统 社会团体门户 各种网站 企事业单位的局域网等的连接 2019 12 20 131 在这种情况下 当南京电信收到一个分组 需要转发时 可能有很多种路由可以选择 作为南京电信的网络 就应该从其中选出一个最好的路由 即计算出哪一条路由最理想 显然南京电信的网管必须了解整个网络的结构和各种参数 并且给出恰当的路由 2019 12 20 132 每一个分组到下一跳以后 也是按照基本的传送方向 进行转发即可 原因是 每一个IP分组都会经过若干路由器转发 每一个路由器不必关心其他路由器的工作状况 2019 12 20 133 1 这个世界的IP网络地址太多 一个路由器实在是不可能装得下所有的IP地址的 2 每一个路由器都会根据流量的情况 独立的处理IP分组 各个IP分组即使目的地址相同 其到达的路径可能也是不一样的 2019 12 20 134 3 整个网络的结构随时随地都在变化 路由器的信息会需要随时更新 4 网络 包括设备和链路 的故障随时都会发生 路由表必须适应网络 设备和链路的情况调整路由 它是不可能一成不变的 2019 12 20 135 Internet最初是由ARPANET发展起来的 Internet发展的初期 ARPANET已经投入使用 其结果就是ARPANET必然作为Iternet的主干 本地的Internet作为局域网通过网关接入ARPANET 构成因特网 连接本地网络与ARPANET的网关称为核心网关 核心网关需要不断地交换各自地路由信息 以保证整个Internet路由地一致性 2019 12 20 136 2019 12 20 137 问题 随着核心网关的增多 主干网上路由更新的信息增多 开销增大 难以继续扩展 一是网络规模极大 明确因特网上的路由器已经有数百万之多 所有的路由器都交换路由信息 这种路由信息本身就使得网络的流量饱和 二是许多单位并不愿意外界了解其网络的布局和路由信息 这样 把因特网分成许多较小的自治系统 这种自治系统有权自主地决定在本系统内采用何种路由协议 2019 12 20 138 自治系统 AS AutonomousSystem 包括多个网络和网关 称为非核心网关 AS通过唯一核心网关与主干网相连 组成自治系统 通常一个自治系统内所有地网络及其设备都属于同一个行政单位管辖 并且一个自治系统内地所有地路由器在本自治系统内都是联通的 2019 12 20 139 非核心网关在本地自行管理 可以使得本地网关具有极大的灵活性 减轻了核心网关上管理中心的负担 核心网关由INOC Internet网络操作中心 统一管理 可以保证极高的可靠性 可以相互交换路由信息 保证整个Internet路由的一致性 2019 12 20 140 好处 在自治系统内部 各个非核心网关管理本地的路由器 共同完成本地路由 某一分组如果其目的地址位于其他自治系统时 本地网关将通过默认的路径将分组发往与之相连的核心网关 进入核心主干网 通过相应的核心网关的协调 进入目的地址所在的核心网关 再进入相应的自治系统 经某一非核心网关到达该自治系统 最后到达目的主机 2019 12 20 141 Internet的树型结构 各网关通过路由协议来交换路由信息时 可能有三种情况 1 核心网关之间 对应的路由协议GGP GatewayGatewayProtocol 2019 12 20 142 2 自治系统内部网关之间 对应的路由协议 内部网关协议IGP InteriorGatewayProtocol 如RIP IGRP HELLO OSPF等 3 自治系统与核心网关之间 对应的路由协议 外部网关协议 EGP ExteriorGatewayProtocol 如EGP BGP等 2019 12 20 143 2019 12 20 144 2019 12 20 145 三 路由算法 路由算法的分类 分类主要是根据网络中的信息流量和拓扑结构的变化 是否跟随调整而区分 静态 非自适应调整 路由不随网络实际传输量和拓扑变化而调整 只是按照原先设计好的路径传送 具体算法有扩散式 随机式 固定式等 2019 12 20 146 动态 自适应调整 路由根据当前网络的流量和拓扑而动态警醒 可以较好地适应网络通信量和拓扑的变化 具体算法有集中式 孤立式 分布式 混合式 分层式等 2019 12 20 147 自适应分布式路由算法举例 向量 距离法 Vector Distance 也称为Ford Fulkerson Bellman Ford Bellman法