INT计算机网络.ppt

计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 计算机网络 图们因特 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 计算机网络 1、定义 以相互共享资源（硬件、软件和数据） 为目的，通过通信链路连接起来，且各 自具有独立功能的计算机系统之集合 i计算机网络通常由三部分组成:资源子 网、通信子网和通信协议 i用作通信链路的介质主要有：双绞线、 同轴电缆、光缆、微波和通信卫星等 i根据计算机网络覆盖的范围可分为局域 网、城域网、广域网等 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 2、网络连接设备 i网络连接设备包括： 网络接口卡（Network Interface Card,NIC ） 中继器(Repeater)，主要用来连接网段，其 作用是对信号进行整形，使得信号不至于因 为电路衰减而出错 调制解调器(Modem)，用于数字信号和模拟 信号的相互转换 集线器(HUB)，一种特殊的中继，用于网络 电缆的中间转接 交换器(Switch)是用来连接多网段和中等规 模优势的局域网的一种网络连接设备 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 网络接口卡NIC 网卡起到物理接口作用，计算机通过网卡接入局域网。 网卡的ROM上固化有控制通信软件，可实现如下功能： 控制数据传送的功能。一方面负责接收网络上的数据包，解包后将数据传 输给本地计算机；另一方面将本地计算机上的数据打包后送入网络。 串并转换功能。由于计算机内部的数据是并行数据，而一般在网上传输 的是串行比特流信息。 为防止数据在传输中出现丢失的情况，在网卡上还需要有数据缓冲器，以 实现不同设备间的缓冲。 网卡上一般有微处理器、控制设备、编码电路、解码电 路、ROM、RAM以及手工开关等，这些开关和跳线用来设 定各种接口参数的配置，例如对网卡硬件中断级的设置 和I/O地址的设置等。 网卡的接口类型有三种不同的接头：粗缆AUI接头、细缆 BNC接头和双绞线RJ45接头。 按照网卡的工作速度它又可分为10Mb/s、100Mb/s、 10/100Mb/s 自适应和1000Mb/s几种网卡 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 Ethernet实现方法 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 Ethernet网卡结构 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 Ethernet物理地址(MAC地址格式) iEthernet地址 = Manufacture ID + NIC ID 公司： Cisco 00-00-0c Novell 00-00-1B 00-00-D8 3Com 00-20-AF 00-60-8C IBM 08-00-5A i典型的Ethernet地址 ： 00-60-8C-01-28-12 000000001010000010001100 000000010010100000010010 iEthernet地址具有惟一性，取决于你所使用的网卡。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 集线器 又称HUB，是一种特殊的中继器。中继的主要作用是对 接收到的信号进行再生放大，以扩大网络的传输距离。 集线器是把来自不同的计算机网络设备的电缆集中配置 于一体，它是多个网络电缆的中间转接设备，是对网络 进行集中管理的主要设备。 集线器能自动指示有故障的工作站，并切除其与网络的 通信，有利于故障的检测和提高网络的可靠性。 集线器的工作方式是从一个端口接收到数据信号后，将 该信号放大，转发到其他所有处于工作状态的端口，每 一个端口相连的计算机都能收到数据，但仅有与目的地 址相符的工作站才接收该数据。 集线器某个端口一旦被选中，该端口完全独占全部带宽 并与集线器某端口的连接设备进行通信。这时与其它端 口相连的计算机即使有信息要传输也必须要等待 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 集线器的分类 独立式HUB 这是最早使用于局域网络的集线器, 它具有价格低、容易查找 故障等特点，适于小型网络，一般支持8-24个工作站。 叠加式HUB 多个集线器通过一条高速链路叠加起来，它仅支持一种局域网 标准（如以太网络，或令牌环网络），不能同时支持多种局域 网。这类集线器一般都有少量的容错能力和网络管理功能，可 以方便地实现网络的扩充。 智能模块化集线器 这种集线器采用模块化结构，由机柜、电源、主干面板、插卡 和管理模块等组成。它利用高速主干线连起来，可插入 Ethernet 、Token ring 、FDDI或ATM模块，另外还有网管模块 、路由模块等。它一般用于大型网络的主干集线器。这类智能 模块化集线器与交换机之间的差别现在越来越小。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 单一集线器结构 多集线器级联结构 堆叠式集线器结构 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 3、网络的拓扑结构 i局域网中的不同连接方式构成了网络拓扑结构 （Topology） i网络拓扑既与节点间的物理连接有关，又关系 到节点间进行通信的方式和处理冲突的方式 星型 总线型 环型 此外，还有其它一些类型的拓扑结构，如树型、混合 型等 Common LAN Topologies Star（星型结构） 网络有一个中央节点，它与所有其它节点直接相连 优点： 由于每个设备都用一根线路 和中心结点相连，如果这根线 路损坏，或与之相连的工作站 出现故障时，不会对整个网络 造成大的影响，而仅会影响该 工作站； 网络的扩展容易； 控制和诊断方便； 访问协议简单； 缺点： 过分依赖中心结点； 成本高 Common LAN Topologies Ring（环型结构） 网络中所有的节点用公共传输电缆组成一个闭环，用令牌 传递的方法进行访问 优点： 路由选择控制简单。信息流 沿着固定的一个方向流动，两 个站点仅有一条通路； 电缆长度短； 适用于光纤。光纤传输速度 高，而环型拓扑是单方向传输 ，适用于光纤介质。 缺点： 结点故障引起整个网络瘫痪 。 诊断故障困难。具体确定哪 一个结点出现故障非常困难， 需要对每个结点进行检测。 Common LAN Topologies Bus（总线型结构） 网络中所有的节点和工作站都连在一条公共的电缆线上 发送报文的传送方向总是从发送 站点开始向两端扩散，在总线网络 上的每个站点都会把自己的地址与 这个报文的目的地址相比较,只有与 该报文目的地址相同的工作站才会 接收报文。 总线型拓扑结构的介质访问控制 方式是叫CSMA/CD（载波监听多路访 问/冲突检测）。 拓扑结构可靠性高。 易于扩充，增加新的站点容易。 故障隔离困难。如站点发生故障 ，需将该站点从总线上拆除，如介 质故障，则这段总线要切断。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 图1-9 树状结构网络 图1-10 树状拓扑结构 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 网状拓扑结构 CERNET主干网拓扑结构 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 广域网的硬件组成 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 计算机网络的性能指标 1. 速率 i 比特（bit）是计算机中数据量的单位，也是 信息论中使用的信息量的单位。 i Bit 来源于 binary digit，意思是一个“二进 制数字”，因此一个比特就是二进制数字中的 一个 1 或 0。 i 速率即数据率(data rate)或比特率(bit rate)是计算机网络中最重要的一个性能指标 。速率的单位是 b/s，或kb/s, Mb/s, Gb/s ，Tb/s等 i 速率往往是指额定速率或标称速率。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 2. 带宽 i“带宽”(bandwidth)本来是指信号具有 的频带宽度，单位是赫（或千赫、兆赫 、吉赫等）。 i现在“带宽”是数字信道所能传送的“最 高数据率”的同义语，单位是“比特每秒” ，或 b/s (bit/s)。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 i常用的带宽单位是 千比每秒，即 kb/s（103 b/s） 兆比每秒，即 Mb/s（106 b/s） 吉比每秒，即 Gb/s（109 b/s） 太比每秒，即 Tb/s（1012 b/s） i在计算机界 K = 210 = 1024 M = 220 G = 230 T = 240。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 3. 吞吐量 i吞吐量(throughput)表示在单位时间内通 过某个网络（或信道、接口）的数据量。 i吞吐量更经常地用于对现实世界中的网络 的一种测量，以便知道实际上到底有多少 数据量能够通过网络。 i吞吐量受网络的带宽或网络的额定速率的 限制。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 4. 时延(delay 或 latency) i传输时延（发送时延 ） 发送数据时 ，数据块从结点进入到传输媒体所需要 的时间。 i也就是从发送数据帧的第一个比特算起 ，到该帧的最后一个比特发送完毕所需 的时间。 发送时延 = 数据块长度（比特） 信道带宽（比特/秒） 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 i传播时延 电磁波在信道中需要传播一 定的距离而花费的时间。 i信号传输速率（即发送速率）和信号在 信道上的传播速率是完全不同的概念。 传播时延 = 信道长度（米） 信号在信道上的传播速率（米/秒） 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 i处理时延 交换结点为存储转发而进行 一些必要的处理所花费的时间。 i排队时延 结点缓存队列中分组排队所 经历的时延。 i排队时延的长短往往取决于网络中当时 的通信量。 i数据经历的总时延就是发送时延、传播 时延、处理时延和排队时延之和： 总时延 = 发送时延+传播时延+处理时延+处理时延 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 四种时延所产生的地方 1 0 1 1 0 0 1 发送器 队列 在链路上产生 传播时延 结点 B 结点 A 在发送器产生传输时延 (即发送时延) 在结点 A 中产生 处理时延和排队时延 数据 从结点 A 向结点 B 发送数据 链路 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 （传播）时延 链路 带宽 时延带宽积 = 传播时延 带宽 5. 时延带宽积 i链路的时延带宽积又称为以比特为单位的 链路长度。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 6. 利用率 i信道利用率指出某信道有百分之几的时 间是被利用的（有数据通过）。完全空 闲的信道的利用率是零。 i网络利用率则是全网络的信道利用率的 加权平均值。 i信道利用率并非越高越好。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 时延与网络利用率的关系 i根据排队论的理论，当某信道的利用率增 大时，该信道引起的时延也就迅速增加。 i若令 D0 表示网络空闲时的时延，D 表示 网络当前的时延，则在适当的假定条件下 ，可以用下面的简单公式表示 D 和 D0之 间的关系： U 是网络的利用率，数值在 0 到 1 之间。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 时延 D 利用率 U 1 0 D0 时延 急剧 增大 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 计算机网络的非性能特征 i费用 i质量 i标准化 i可靠性 i可扩展性和可升级性 i易于管理和维护 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 计算机网络体系结构 i计算机网络是由多种计算机和各类终端通过通信 线路连接起来的复合系统。由于计算机型号不一 ，终端类型各异，加之线路类型、连接方式、同 步方式、通信方式的不同，在不同计算机系统之 间，真正以协同方式进行通信的任务是十分复杂 的。为了分析设计这样复杂的计算机网络，人们 提出了分层的方法。“分层”可将庞大而复杂的问 题，转化为若干较小的易于研究和处理的局部问 题 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 i1974年，美国的IBM公司宣布了它研制的系统网络 体系结构SNA（System Network Architecture） i为了使不同体系结构的计算机网络都能互连，国 际标准化组织（ISO）于1977年成立了一个专门的 机构（TC97-SC16）来研究该问题并提出一个标准 框架，即开放系统互连参考模型OSI（Open Systems Interconnection Reference Model） v1984年SC16解散，由SC6和SC21进行研究 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 iOSI将整个网络的通信功能划分成七个层次， 每个层次完成不同的功能。 各层之间是独立的。某一层并不需要知道其它层是 如何实现的，而仅仅需要知道该层间的接口（即界 面）所提供的服务。由于每一层只实现一种相对独 立的功能，因而可使整个问题的复杂程度下降了 灵活性好。当任何一层发生变化时（例如技术的变 化），只要层间接口关系保持不变，则该层以上或 以下各层均不受影响 各层都可以采用最合适的技术来实现 易于实现和维护（因为整个的系统已被分解为若干 个相对独立的子系统） 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 1物理层、2数据链路层、3网络层 （通信子网） 4运输层、5会话层、6表示层、7应用层 （资源子网） 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 OSI参考模型中的数据传输 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 物理层 物理层提供为建立、维护和拆除物理链路 所需要的机械的、电气的、功能的和规程 的特性。物理层主要关心的是在连接各种 计算机的传输媒体上传输数据的bit流。 i机械特性 指明接口所用接线器的形状和 尺寸、引线数目和排列、固定和锁定装置 等等。 i电气特性 指明在接口电缆的各条线上出 现的电压的范围。 i功能特性 指明某条线上出现的某一电平 的电压表示何种意义。 i过程特性 指明对于不同功能的各种可能 事件的出现顺序。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 物理层向数据链路层提供服务，主要功能是： 物理连接的建立、维护与释放。 物理层在设计时涉及的主要问题有： 用多大的电压代表“1”或“0”，以及在接收端如何识 别出是 “1” 或“0” 确定连接电缆材质、引线的数目及定义、电缆接头 的几何尺寸、锁紧装置等 指出一个bit占用多长时间？采用什么样的传输方 式？初始连接如何建立？当双方结束通信如何拆除 连接等 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 数据链路层 数据链路层传输数据的单位是帧，数据帧的格 式中包括的信息有：地址信息、控制信息、数 据、校验信息 数据链路层的主要作用是通过数据链路层协议 （即链路控制规程）在不可靠的物理链路上实 现高可靠的数据传输 数据链路层把一条有可能出差错的实际链路， 转变成为让网络层向下看起来好象是一条不出 差错的链路 在数据链路层还要控制发送方的发送速率(使接 收方来得及接收)，即在数据链路层要解决流量 控制的问题 网卡是数据链路层的设备 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 数据链路层的两个子层 i为了使数据链路层能更好地适应多种局域网标准 ，802 委员会就将局域网的数据链路层拆成两个 子层： 逻辑链路控制 LLC (Logical Link Control) 子层 媒体接入控制 MAC (Medium Access Control) 子层。 i与接入到传输媒体有关的内容都放在 MAC子层， 而 LLC 子层则与传输媒体无关，不管采用何种 协议的局域网对 LLC 子层来说都是透明的 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 计算机通过适配器和局域网进行通信 硬件地址 至局域网 适配器 （网卡） 串行通信 CPU 和 存储器 生成发送的数据 处理收到的数据 把帧发送到局域网 从局域网接收帧 计算机 IP 地址 并行 通信 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 i最初的以太网是将许多计算机都连接到一根总 线上。当初认为这样的连接方法既简单又可靠 ，因为总线上没有有源器件。 载波监听多点接入/碰撞检测 CSMA/CD B向 D 发送数据 C D A E 匹配电阻（用来吸收总线上传播的信号）匹配电阻 不接受不接受不接受 接受 B 只有 D 接受 B 发送的数据 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 i总线上的每一个工作的计算机都能检测到 B 发送的数据信号。 i由于只有计算机 D 的地址与数据帧首部 写入的地址一致，因此只有 D 才接收这 个数据帧。 i其他所有的计算机（A, C 和 E）都检测 到不是发送给它们的数据帧，因此就丢弃 这个数据帧而不能够收下来。 i具有广播特性的总线上实现了一对一的通 信。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 iCSMA/CD 表示 Carrier Sense Multiple Access with Collision Detection。 i“多点接入”表示许多计算机以多点接入的 方式连接在一根总线上。 i“载波监听”是指每一个站在发送数据之前 先要检测一下总线上是否有其他计算机在 发送数据，如果有，则暂时不要发送数据 ，以免发生碰撞。 i总线上并没有什么“载波”。因此， “载波 监听”就是用电子技术检测总线上有没有 其他计算机发送的数据信号。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 i“碰撞检测”就是计算机边发送数据边检测 信道上的信号电压大小。 i当几个站同时在总线上发送数据时，总线 上的信号电压摆动值将会增大（互相叠加 ）。 i当一个站检测到的信号电压摆动值超过一 定的门限值时，就认为总线上至少有两个 站同时在发送数据，表明产生了碰撞。 i所谓“碰撞”就是发生了冲突。因此“碰撞 检测”也称为“冲突检测”。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 i在发生碰撞时，总线上传输的信号产生了严重的 失真，无法从中恢复出有用的信息来。 i每一个正在发送数据的站，一旦发现总线上出现 了碰撞，就要立即停止发送，免得继续浪费网络 资源，然后等待一段随机时间后再次发送。 i当某个站监听到总线是空闲时，也可能总线并非 真正是空闲的。 iA 向 B 发出的信息，要经过一定的时间后才能 传送到 B。 iB 若在 A 发送的信息到达 B 之前发送自己的帧 (因为这时 B 的载波监听检测不到 A 所发送的 信息)，则必然要在某个时间和 A 发送的帧发生 碰撞。 i碰撞的结果是两个帧都变得无用。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 1 km AB t 碰撞 t = B 检测到信道空闲 发送数据 t = / 2 发生碰撞 t = 2 A 检测到发生碰 撞 t = B 发送数据 B 检测到发生碰撞 t = A B AB AB t = 0 A 检测到 信道空闲 发送数据 AB t = 0 t = B 检测到发生碰撞 停止发送 STOP t = 2 A 检测到 发生碰撞 STOP A B 单程端到端 传播时延记为 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 i使用 CSMA/CD 协议的以太网不能进行全双工通 信而只能进行双向交替通信（半双工通信）。 i每个站在发送数据之后的一小段时间内，存在着 遭遇碰撞的可能性。 i这种发送的不确定性使整个以太网的平均通信量 远小于以太网的最高数据率。 i最先发送数据帧的站，在发送数据帧后至多经过 时间 2 （两倍的端到端往返时延）就可知道发 送的数据帧是否遭受了碰撞。 i以太网的端到端往返时延 2 称为争用期，或碰 撞窗口。 i经过争用期这段时间还没有检测到碰撞，才能肯 定这次发送不会发生碰撞。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 二进制指数类型退避算法 (truncated binary exponential type) i发生碰撞的站在停止发送数据后，要推迟（退避 ）一个随机时间才能再发送数据。 确定基本退避时间，一般是取为争用期 2。 i二进制指数类型退避算法的思路是： 发生第1次冲突，等待0-（21-1）个时间片； 发生第2次冲突，等待0-（22-1）个时间片； 。 发生第n 次冲突，等待0-（2n-1）个时间片； i当重传达 16 次仍不能成功时即丢弃该帧，并向 高层报告。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 争用期的长度 i以太网取 51.2 s 为争用期的长度。 i对于 10 Mb/s 以太网，在争用期内可发送512 bit，即 64 字节。 i以太网在发送数据时，如果发生冲突，就一定是 在发送的前 64 字节之内。若前 64 字节没有发 生冲突，则后续的数据就不会发生冲突。 i由于一检测到冲突就立即中止发送，这时已经发 送出去的数据一定小于 64 字节。 i以太网规定了最短有效帧长为 64 字节，凡长度 小于 64 字节的帧都是由于冲突而异常中止的无 效帧。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 i当发送数据的站一旦发现发生了碰撞时： 立即停止发送数据； 再继续发送若干比特的人为干扰信号(jamming signal)，以便让所有用户都知道现在已经发 生了碰撞。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 数据帧 干扰信号 TJ AB TB t B 发送数据 A 检测 到冲突 开始冲突 信 道 占 用 时 间 A 发送数据 B 也能够检测到冲突，并立即停止发送数据帧，接 着就发送干扰信号。这里为了简单起见，只画出 A 发送干扰信号的情况。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 数据链路和帧 i链路(link)是一条无源的点到点的物理线 路段，中间没有任何其他的交换结点。 一条链路只是一条通路的一个组成部分。 i数据链路(data link) 除了物理线路外，还必须 有通信协议来控制这些数据的传输。若把实现这 些协议的硬件和软件加到链路上，就构成了数据 链路。 现在最常用的方法是使用适配器（即网卡）来实现这 些协议的硬件和软件。 一般的适配器都包括了数据链路层和物理层这两层的 功能。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 IP 数据报 1010 0110 帧 取出 数据 链路层 网络层 链路 结点 A结点 B 物理层 数据 链路层 结点 A结点 B 帧 (a) (b) 发送 帧 接收 链路 IP 数据报 1010 0110 帧 装入 数据链路层传送的是帧 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 封装成帧 i封装成帧(framing)就是在一段数据的前后分 别添加首部和尾部，然后就构成了一个帧。确 定帧的界限。 i首部和尾部的一个重要作用就是进行帧定界。 帧结束 帧首部 IP 数据报 帧的数据部分帧尾部 MTU 数据链路层的帧长 开始 发送 帧开始 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 SOH 装在帧中的数据部分 帧 帧开始符帧结束符 发送在前 EOT 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 网络层 i网络层概述 i路由算法 最优化原则 最短路径路由算法 洪泛算法 基于流量的路由算法 距离向量路由算法 链路状态路由算法 分级路由 i拥塞控制算法 iInternet网络层协议 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 i网络层的地位 网络层利用数据链路层提供的服务，为传 输层提供服务。 网络层需要解决的问题是确定分组从源地 址到目的地址是如何路由的。 在广播网络中，路由选择很简单，所以网 络层也很薄，甚至不存在。而在大型网络 中，分组不得不跨越若干个网络到达目的 地址，这其中的路由问题就需要由网络层 来解决。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 i网络层为了选择路由，需要解决以下问题： 屏蔽各种不同类型网络之间的差异 需要统一数据格式 需要统一网络地址 实现全网的数据传输 建立跨越网络的虚电路 网络之间实现分组的寻址和转发 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 路由算法 i路由算法是网络层软件的一部分 子网采用数据报方式，每个分组都要做路由选择。 子网采用虚电路方式，只需在建立连接时做一次路由 选择。 i路由算法应具有的特性 正确性(correctness)、简单性(simplicity)、健壮 性(robustness)、稳定性(stability)、公平性 (fairness)、最优性(optimality) i路由算法分类 非自适应算法(静态路由算法)：按照预先计算好的 (off-line)信息进行路由。 自适应算法(动态路由算法)：根据网络拓扑结构，通 信量等的变化来改变路由。 i最优化原则(optimality principle) 如果路由器 J 在路由器 I 到 K 的最优路由上，那 么从J到K的最优路由会落在同一路由上。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 路径选择技术 i分类 决定论法统计推断法 全路发送扩散式 几路发送选择扩散式 单路发送固定式 适应式孤立法 分布法 随机式 分类1 分类2 方式 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 固定式 对应于接收节点预先（即静态地）规定一条发 送路径，算法简单，但不适应网络结构和信息 流量的变化。 后继 节点 当前节点 123456 接 收 节 点 111133/4 221224 3311/633 4441/664 535565 63/44666 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 适应式 i在每个节点根据节点和线路的当前状态动态地决定报文分 组的传送路径，选择的判定依据通常是使延迟时间最小。 这是现在多数报文分组网络采用的方法。 i每个节点有一路径表，说明从该节点到达其余节点所需传 输时间的当前最好估值。下图示意由节点j的延迟时间表 Tj（左），生成相应的路径选择表Rj（右），I为收信节 点标识， ln为节点J的出口。 i根据有关网络和信息状态改变路径选择表。 0.20.10.30.4 0.10.30.70.5 0.60.40.90.2 A I N L1 L2 L3 L4 L2(0.1) L1(0.1) L4(0.2) A I N R(I)=min Tj (I, ln) ln 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 各种路径选择算法比较 选择方 式 效果价 格 传送时 间 网络 安全性 对通信 量的适 应性 通信容 量 算法 复杂性 扩散式很低一般很高无很小简单 固定式高一般低无大简单 随机式低长高无小简单 适应式高一般高强中一般 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 几种常见的路由算法 i静态路由算法 最短路径选择(Shortest Path Routing) 洪泛算法(Flooding Routing) 基于流量的路由算法(Flow-Based Routing) i动态路由算法 距离向量路由算法(Distance Vector Routing) 链路状态路由算法(Link State Routing) 分级路由(Hierarchical Routing) 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 最短路径路由算法 i基本思想 构建子网的拓扑图，图中的每个结点代表一个路由 器，每条弧代表一条通信线路。 目的是构建两个路由器间的路由，算法是在子网拓 扑图中找出最短路径。 i得到最短路径，有不同的测量 路径长度的方法： 计算结点数量 计算地理距离 计算传输延迟 计算距离、信道带宽等参数的加权函数 Dijkstra算法是其中的一种计算最短路径的算法。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 Dijkstra算法 每个结点用从源结点沿已知最佳路径到本结点的距离 来标注，标注分为临时性标注和永久性标注。开始时 ，所有结点都为临时性标注，标注为无穷大。 源结点标注为0，且为永久性标注，令其为工作结点。 检查与工作结点相邻的临时性结点，若该结点到工作 结点的距离与工作结点的标注之和小于该结点的标注 ，则用新计算得到的和重新标注该结点。 在整个图中查找具有最小值的临时性标注结点，将其 变为永久性结点，并成为下一轮检查的工作结点。 重复第三、四步，直到目的结点成为工作结点。 Dijkstra算法的图例: 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 Dijkstra算法图例 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 例：09年全国硕士研究生入学考试计算机 统考试题 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 解 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 洪泛算法 i基本思想:把收到的每一个分组，向除了该分 组到来的线路外的所有输出线路发送。 i主要问题:洪泛要产生大量重复分组。 i解决措施 每个报头包含站点计数器，每经过一站计数器减1 ，为0时则丢弃该分组。 记录下分组扩展的路径，防止它第二次扩散到已经 扩散过的路径中。 i较实用的方法选择性洪泛算法(selective flooding) 洪泛法的一种改进：将进来的每个分组仅发送到与 正确方向接近的线路上。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 i应用情况 洪泛算法由于过于浪费路由器和线路的资源，在实 际应用中很难被直接采用，但还是有一些用处的。 在军事领域中，由于需要极好的健壮性，扩散法可 以一展身手。 在分布式数据库中，有时需要并行地更新所有数据 库，这时洪泛算法也是最佳方案。 因为洪泛算法总是能够选择最短的路径，可以产生 一个最短的延迟。洪泛算法可以作为一种尺度衡量 标准来评价其它路由算法。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 距离向量路由算法 i属于动态路由算法，最初用于ARPANET,DECnet等网络。 i基本思想：每个路由器维护一张表，表中有每个目的地址 的最佳距离和线路，并与邻居结点交换信息来更新表。 i表(路由表)的构成：包括到达目的结点的最佳输出线路， 和到达目的结点所需时间或距离。 i路由器到邻居结点的“距离”，所用的度量标准可以为站点 、估计的时间延迟等。 i路由器定时向所有邻居结点发送它到每个目的结点的距离 表，同时也接收每个邻居结点发来的距离表。 i根据不同邻居发来的信息，更新本路由器的表。 i缺陷是存在无穷计算问题 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 距离向量路由算法图例 i 路由器J计算到 达路由器C的最 新路由 JAC=8+25=33ms JIC=10+18=28ms JHC=12+19=31ms JKC=6+36=42ms i 其中JIC是最好 的。因此在路由 器J的新路由表 中填上C的延迟 为28ms，经过路 由器I。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 链路状态路由算法 i距离向量路由算法的主要问题 由于延迟度量仅仅是队列长度，在选择路由时没有考 虑线路带宽。 路由收敛速度慢。 i在1979年前，ARPANET上都采用距离向量路由算 法，但是后来为链路状态路由算法所替代。 i链路状态路由算法的简单步骤 发现邻居结点，并获取它们的网络地址。 测量到每个邻居结点的延迟或开销。 将所有获取的内容封装成一个分组。 将这个分组发送给所有其它路由器。 计算到每个其它路由器的最短路径。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 步骤1：发现邻居结点 i发现邻居结点，并学习它们的网络地址。 路由器启动后，通过发送HELLO分组，并得 到邻居路由器的响应来发现邻居结点。 当两个或多个路由器连在一个LAN时，引入 人工结点。图例。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 步骤2/3：测量线路开销和封装分组 i测量到每个邻居结点的延迟或开销，一种直接的方法是： 发送一个要对方立即响应的ECHO分组，来回时间除以2即 为延迟时间。 i将所有获取的内容封装成一个分组，即在信息收集完毕后 ，构造一个包含所有数据的分组。该分组的结构为：发送 方的标识符、序号、年龄、邻居结点列表（邻居结点标识 符，线路开销值）。 i创建状态分组的时机:定期创建;发生重大事件后创建。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 步骤4：发布链路状态分组 i发布算法的基本思想是洪泛链路状态分组。 为控制洪泛，每个分组增加一个序号域，每次 发送新分组时加1（为了避免序号重复，使用32 位的序号）。 当一个链路状态分组到达时，若是新的则分发 ；若是重复的，则丢弃。 路由器崩溃后，所有的序号丢失（从0开始记） ，以后新到分组都可能被当作重复分组而被拒 绝。解决序号丢失和出错的方法是增加年龄 (age)域，每秒钟年龄减1，至零则丢弃。 序号在发送出去后会出现错误，为防止链路出 错，所有的链路状态分组都需要应答。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 步骤5：计算新路由 i在路由器积累了一整套网络的链路状态分组后 ，就可以通过计算得到整个网络的结构。可以 利用Dijkstra算法计算得到每个其它路由器的 最短路径。 i基于链路状态的路由协议 Open Shortest Path First (OSPF) Intermediate System-Intermediate System (IS- IS) 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 分级路由 i网络规模增长带来的问题 路由器中的路由表增大。 路由器为选择路由而占用的内存、CPU时间和网络带宽 增大。 i解决办法 分级路由 对于大型网络分而治之，每个路由器只知道自己所在 子网的路由信息，而不去了解其他子网的内部结构。 根据需要，可以分成区域(regions)、聚类(clusters) 、区(zones)和组(groups) 图例。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 分级路由图例 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 小结 路由算法 i最短路径路由算法 在子网拓扑图中找出 最短路径。Dijkstra 算法 i洪泛算法 把收到的每一个分组 ，向除了该分组到来 的线路外的所有输出 线路发送 i基于流量的路由算法 根据网络带宽和平均 流量，得出平均延迟 i距离向量路由算法 根据两个结点间的队列 长度来完成路由选择， 问题是存在无穷计算 i链路状态路由算法 i分级路由 对于大型网络分而治之 ，每个路由器只知道自 己所在子网的路由信息 ，而不去了解其他子网 的内部结构 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 拥塞的基本概念 i 拥塞(congestion)：网络中存在过多分组的时候，网络性能降低 ，这种情况被称为拥塞。 i 报文装配死锁：收信机的缓冲器被占满，任何报文都装配不起来 ，形成既无法交付报文，后续分组也进不来的情况 i存储转发死锁：中继缓冲区装满后，造成“输不进，出不去”的局面 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 i造成拥塞的原因 多个输入对应一个输出 慢速处理器 低带宽线路 i拥塞控制(congestion control)与流量控制 (flow control) 拥塞控制需要确保通信子网能够承载用户提交的通 信量，是一个全局性问题，涉及主机、路由器等很 多因素。 流量控制与点到点的通信量有关，主要解决快速发 送方与慢速接收方的问题，一般都是基于反馈进行 控制的。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 拥塞控制的分类 i根据控制论，拥塞控制可分为两类。 i开环控制(防患于未然) 通过良好的设计解决问题，以避免拥塞发生。 进行开环控制需要决定何时接收新的分组、何时丢 弃分组、丢弃哪些分组。利用开环进行拥塞控制时 ，所有这些操作都不会考虑网络的当前状态。 i闭环控制(因地制宜) 基于反馈机制。其工作过程为： 监控系统，发现何时何地发生拥塞。 把发生拥塞的消息传给能采取动作的站点。 调整系统操作，解决拥塞问题。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 开环控制 通信量整形 i通信量整形(Traffic Shaping)的基本思想 网络上，突发的通信量是造成拥塞的主要原因。 强迫分组以某种可以预见的速率传送，减少拥塞，这 种方法被称为通信量整形。 漏桶算法和令牌桶算法都可以实现通信量整形。 i漏桶算法(The Leaky Bucket Algorithm) 基本原理：图例。 在计算机中的使用 漏桶有限内部队列；水 通信量，需要发送的分组。 分组到达队列时，队列满，分组被丢弃；队列空，分组放置在 队尾。 效果 将用户发出的不平滑的分组流转变成网络中平滑的分组流。 漏桶算法既可以用于分组长度固定的协议（如ATM使用分组计 数），也可用于可变长分组的协议（如IP使用字节计数）。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 无论水流进桶的速度为多少，只要桶中有水，水从桶中外 漏的速度是恒定的。桶空了，速度为零。桶满了，水外泄。 漏桶算法 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 令牌桶算法 i由于漏桶算法不够 灵活，因此加入令 牌机制。 i令牌桶算法 基本思想：漏 桶存放令牌， 每T秒产生一 个令牌，分组 发送之前必须 获得一个令牌 ，传输之后删 除该令牌。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 漏桶和令牌桶算法的比较 i通信量整形策略不同 漏桶算法不允许空闲主机积累发送权。 令牌桶算法允许空闲主机积累发送权，以便以后发 送大的突发数据，最大为桶的大小。 i桶中存放的内容不同 漏桶中存放的是数据，桶满了丢弃数据。 令牌桶中存放的是令牌，桶满了丢弃令牌，不丢弃 数据。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 闭环控制 i闭环控制需要完成：何为拥塞、如何反馈和如何解决。 i何为拥塞 衡量网络拥塞的参数 缺乏缓冲区造成的丢包率 平均队列长度 超时重传的分组数目 平均分组延迟 分组延迟变化(Jitter) i如何反馈 反馈方法 向负载发生源发送一个报警分组，这同时加强了拥塞。 在分组结构中保留一个位或域来表示发生拥塞，一旦发 生拥塞，路由器将所有输出分组的拥塞位填充，报警。 主机或路由器主动地、周期性地发送探报(probe)，查 询是否发生拥塞。 i如何解决 利用拥塞控制算法 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 闭环控制 虚电路子网中的拥塞控制 i方法一:许可控制(admission control),一旦发生拥塞， 就不允许再建立新的虚电路，直到拥塞解除为止。 i方法二:在发生拥塞后可以建立新的虚电路，但要绕开发 生拥塞的地区。 i方法三:资源预留：建立虚电路时，主机与子网达成协议 ，子网根据协议在虚电路上为此连接预留资源。 计 算 机 网 络 华中 科技 大学 武昌 分校 网 络 教 程 闭环控制 抑制分组 i抑制分组(Choke Packets) 路由器监控输出线路及其它资源的利用情况，超过某 个阈值，则此资源进入警戒状态。 每个新分组到来，检查它的输出线路是否处于警戒状 态。若是，向源主机发送抑制分组，分组中指出发生 拥塞的目的地址。同时将源分组打上标记(为了以后 不再产生抑制分组)后，正常转发。 源主机收到抑制分组后，按一定比例减少发向特定目 的地的通信量，并在固定时间间隔内忽略指示同一目 的地的抑制分组。然后开始监听，若此线路仍然拥塞 ，则主机在固定时间内减轻负载、忽略抑制分组；若 在监听周期内没有收到抑制分组，则增加通信量。 通常采用的通信量增减策略是： 减少时按一定比例减少，保证快速解除拥塞。 增加时以常量增加，防止很快导致拥塞。 计 算 机 网 络 华中 科技