计算机网络 第五章网络层.ppt

第五章 网络层,网络层设计的有关问题 路由选择算法 拥塞控制算法 网络互联 因特网上的网络层,网络层端到端数据传输的最低层,网络层负责把源计算机发出的信息分组经过适当的路径送到目的计算机。 网络层需要了解通信子网的拓扑结构，选择合适的传输路径。 网络层要预防和控制通信子网中超量的信息分组造成的拥塞。 网络层还要处理不同网络中源端和目的端之间的差异。,§5.1 网络层设计的有关问题,对网络层所提供的服务存在着两种观点： 面向连接的服务，复杂的功能放在通信子网中。 无连接服务，复杂的功能放在两端主机中。,网络层的内部结构,网络层提供的服务是否可靠与有无连接并没有关系。理论上存在四种组合，但最重要的只是其中的两种组合： 可靠的面向连接服务。 不可靠的无连接服务。 针对两种服务，网络层有两种不同的工作方式： 虚电路（virtual circuit）方式。当建立连接时，从信源到信宿的路由就作为连接建立的一部分加以保存，此路由用于传输连接上的所有数据，当释放连接时，虚电路也随之撤消。 数据报（datagrams）方式。不预先选择路由，发出的每个分组所选择的路由独立于其前面发出的分组，后续的分组可以走不同的路由，比虚电路方式更健壮，更容易处理传送失败和拥塞。,虚电路与数据报的比较,§5.2 路由选择算法,路由选择是网络层的主要功能，负责为分组选择合适的转发路径。 路由选择算法应具有以下几种特征：正确性（correctness）、简单性（simplicity）、健壮性（robustness）、稳定性（stability）、公平性（fairness）和最优性（optimality）。 一个好的路由选择算法是兼顾某几种重要的性能指标。,路由选择算法的分类,分为两大类： 非自适应算法（non-adaptive algorithm）：也叫静态路由选择（static routing），预先离线计算好路由表，在网络启动时装入到路由器中，在网络运行过程中不会根据网络流量和拓扑结构的变化而改变。简单。 自适应算法（adaptive algorithm）：也叫动态路由选择（dynamic routing），根据当前网络流量和拓扑结构的变化，动态在线地计算网络的路由。复杂、健壮，网络负担重。,最佳原理和接收树,当计算两点之间的最佳路由时，存在一个最佳原理（optimality principle）：如果J位于I到K的最佳路由上，则J到K的最佳路由也必定落在该路由上。可通过反证求得。 根据最佳原理可以推出，所有源节点到一个给定目的节点的最佳路由的集合组成一棵以该目的节点为根的树，称为该目的节点的接收树（sink tree）。接收树并不是唯一的。所有的路由算法都是要试图找出各个目的节点的接收树，并利用这些接收树来转发数据。,最短通路路由选择算法,最短通路（shortest path）路由选择算法属于自适应路由算法。它将一个通信子网抽象成一张图，图中的顶点代表网络节点（路由器），弧线代表通信线路，弧线上的权代表相邻顶点间的“距离”（可为物理上的距离，或指分组在其间的传输时间，也可指线路上的通信费用等）。任意一对顶点之间的最小权值即为它们的最短通路。 求任意一对顶点之间的最短通路可有很多方法，其中迪杰斯特拉（Dijkstra）提出了按通路长度递增的次序产生最短通路的算法，基本思想为： 首先从起始点出发，找出距起始点最近的结点，然后以此结点为基础找出距起始点次近的结点，如此每次都找出比前一次短的通路，直至某个通路到达给定的目的，这时所得到的通路就是源到目的的最短通路。 具体可采用标记方法。,利用Dijkstra算法求A到D的最短通路,扩散法（flooding）,扩散法为静态算法，也称洪泛式。基本思想：路由器将收到的每个分组，从除了分组到来的线路外的所有输出线路上发出。 可靠性高，但容易造成网络拥塞，改进办法有： 在每个分组头中增加一个站点计数器（hop counter）：每经过一个站点，计数器减1，当计数器减为0时，就扔掉分组。计数器的值可设置为源到目的的长度或子网的直径。 记下分组扩散的路径，确保分组只转发一次。可以让源路由器对来自主机的每个分组设置一个序号，每个路由器对应于每个源路由器都有一张表，用来记录已转发过的分组（源路由器和序号）。 选择扩散法（flood selectively）：只转发到与正确方向接近的那些线路上。 适用于负荷轻的小规模网络以及特别强调健壮性的网络。,基于流量（flow-based）的路由选择,一种既考虑拓扑结构又兼顾载荷的静态路由选择算法。 基本思想：利用已知的载荷平均流量，计算出该线路上的平均分组延迟；由所有线路的平均延迟，计算出整个网络的平均分组延迟，从而找出具有网络最小延迟的最优路由选择算法。 采用这种技术必须预知的几种信息： 网络的拓扑结构 给出通信量矩阵Fij 各线路容量的矩阵Cij 选定一种路由选择算法,从源端 i 到目的端 j 的项表示从 I 到 j的通信路由和从 i 送到 j 每秒钟的分组数量。,基于流量路由选择的示例,线上的数值表示各方向的容量Ci，单位为bps。,通信量的 数学分析,计算每条线路总通信量i ，例： 1=AB=9+4+1=14。 设分组平均长度为1/（在这里假定为800位），则每条线路上分组的容量为Ci，单位为分组/s。例：C1=20kbps，则C1=20k/800=25分组/s。 由队列原理导出每条线路的平均延迟（包括排队时间和服务时间）： Ti=(Ci-i)-1 如：T1=(25-14 )-1=91ms 设每条线路的权值i= i/i ，即在总通信量中使用该线路的比例。如： 1= 14/(14+12+6+11+13+8+10+8)=14/82=0.171 则整个网络的平均延迟时间为i·Ti，即所有线路的加权延迟和。本例中为86ms。,距离矢量路由选择,距离矢量路由选择（distance vector routing）算法是现代计算机网络两个最常使用的动态路由选择算法之一。 最初用于ARPAnet；DECnet、Novell的IPX以及Internet的一种内部网关协议（IGP，Interior Gateway Protocol）都使用了称作RIP（Route Information Protocol）的距离矢量路由选择算法；Cisco则开发了一种改进的协议，叫作IGRP（Interior Gateway Routing Protocol）。 基本思想：每个路由器维护一张（矢量）表，表中给出到每个目的节点已知的最佳距离和路径；每个路由器还不断测试到达相邻路由器的距离；相邻的路由器之间也不断地相互交换矢量信息；这样每个路由器将测试出的到达相邻路由器的距离加上相邻路由器给出的矢量信息，就可得知通过相邻路由器到达每个目的节点的距离，选择最佳路径更新表的信息。,距离矢量路由选择示例,无穷计算(count-to-infinity)的问题,DVR算法收敛慢，其时间复杂度为O(n3)。特别是它对好消息的反应迅速，但对坏消息却反应迟钝。 其对坏消息的反应迟钝，会造成相互交换的矢量信息错误，最终导致无穷计算的后果。 在实际使用中，可通过设置距离的最大值（如设置为网络最长路由加1）来扼制这种无限的增长。,X,链路状态路由选择,链路状态路由选择（link state routing）算法1979年出现在ARPAnet上，作为一种用来取代DVR的动态路由选择算法，之后得到了广泛的应用。 基本思想：通过各个节点之间的路由信息交换，每个节点都可获得关于全网的拓扑信息，即所有的节点、各节点间的链路连接和链路的代价（时延或费用等），可将这些拓扑信息抽象成一张带权无向图，然后利用最短通路路由选择算法计算出到各个目的节点的最短通路。,链路状态路由选择算法的步骤,找出所有可达的相邻节点及它们的网络地址； 测定到这些相邻节点的代价； 将以上信息构成链路状态分组（link state packet）； 向网上所有节点发送链路状态分组； 利用收到的链路状态分组计算到各目的节点的最短通路。,1. 了解相邻节点 每个路由器启动后，首先在所有与之相连的点-点线路上发送一个特殊的询问分组（HELLO分组），线路另一端的路由器收到后必须发回一个响应来告知它是谁（其网络地址）。 2. 测量线路代价（cost） 路由器在链路上发送一个要求对方立即响应的特殊回声（ECHO）分组，将回声分组的来回时间除以2即得到该链路的延迟时间（代价）。一般重复若干次，取平均值。,3. 构造链路状态分组 每个链路状态分组包括源节点的网络地址、分组的序号和寿命，然后是一系列相邻节点的网络地址和去往该节点的链路代价。 决定何时创建链路状态分组一般有两种方法： 定期创建链路状态分组。 探测到网络连接发生变化时再创建链路状态分组。,4. 发送链路状态分组 通过改进的扩散法（记录分组扩散路径：每个路由器维护一张带有源节点和最大分组序号的表，对来自于同一个源节点的重复分组（分组序号表中序号）不转发）向网上所有其它节点发送链路状态分组。 所有的链路状态分组都要应答。当线路空闲时，从缓冲区中选择发送一个分组或应答。 为了保证高效可靠地发送链路状态分组，需采取如下一些措施： 将分组序号长度设为32位可防止序号重叠太快，若每隔1秒发送一个分组，可发137年不重复。 为每个分组规定一个寿命，分组在路由器中时，其寿命每隔1秒就减1，直到减为0被抛弃。可解决路由器崩溃及分组序号传输出错等造成新旧分组不分的问题。,前图中路由器B的分组缓冲区，包含新近到达还未处理完毕的分组。,5. 计算新的路由 当一个路由器收集齐了所有的链路状态分组后，便可构造出整个网络的拓扑带权图； 通过最短通路路由选择算法就可确定到达所有其它节点的最短路径； 将此结果存入路由选择表中达到更新目的。,链路状态路由选择算法的总结,优点： 可靠性极高：因为构造网络拓扑的信息来自于各个节点亲自的探测。 最佳的路由：根据当前整网的拓扑信息计算出的。 缺点： 每个节点需要大的存储空间来存放其它所有节点发来的链路状态分组。 路由计算时间较长。 以上两点特别在网络规模很大时更加突出。 链路状态路由选择算法在实际网络中运行得很好，使用非常广泛 Internet上广泛使用的OSPF（Open Shortest Path First）协议 为DECnet设计的，后被ISO采纳的IS-IS（Intermediate System to Intermediate System）协议,分级路由选择（hierarchical routing）,将网络分成一些区域，每个区域内的路由器只负责本区域内的分组转发，而不管其它区域的情况，目的地址不在本区域内的分组都发给指定的区域路由器去处理。 当网络规模很大时，往往需要分成多级。 路由信息的交换只在本区域内进行，路由器内部需存储的路由信息大大减少。节省了路由器的存储空间和网络带宽。 缺点是选择的路由可能不是最佳的。,分级路由示例,移动主机（mobile host）的路由选择,移动用户（mobile user）都有一个不变的永久性主方位（home location），用一个永久性的主地址（如手机号码）来确定。 用主地址作为动态用户在系统中的路由选择目标，在找到用户后，再将分组发送到用户所在的任何地方。,移动主机的定位,世界按地理位置被分成许多小单元（通常是一个LAN或无线单元），称作区域，包含有： 一个或多个外地代理（foreign agent），用来管理所有来到当地的动态用户。 一个本地代理（home agent），用来管理原本属本区域，但当时正在外地的用户。 当一个移动用户进入某区域时： 移动主机和外地代理通过广播分组取得联系，移动主机向外地代理登记注册，给出其原来所在地的地址、当前数据链路层地址以及一些安全性信息。 外地代理与移动主机的本地代理取得联系，发出诸如外地代理的网络地址、安全信息等信息。 本地代理检查安全信息，验证通过后应答外地代理。 外地代理得到本地代理确认后，在其表中开设一个表项，通知移动主机已经登录注册。 当一个移动用户离开某区域时，应退出登录,移动主机的分组路由传递,广播（broadcast）路由选择,将分组同时发往所有节点称作广播（broadcasting）。有多种方法实现广播发送： 发送站给每个目的站点都单独发送一个分组，浪费带宽。 采用扩散法，产生太多的分组，消耗太大的带宽。 多目的路由选择算法，每个分组携带一个欲去往的目的地址列表，每个路由器根据目的地址列表确定一组输出线路，修改目的地址列表转发分组副本。在一条输出线路上只有一个分组，节省带宽。 使用以发送站为根的生成树来转发分组。分组副本最少，占用带宽最小。但需每个路由器了解全网的拓扑结构并构造出生成树。,逆向路径转发的广播路由,逆向路径转发（reverse path forwarding）的思想：当一个广播分组到达时，路由器检查其源地址和输入线路，若输入线路是从该路由器去往源地址的最佳路径，则将该分组在除输入线路以外的所有输出线路上转发出去；否则将其丢弃。 相比前四种方法，既合理有效，又易于实现。,多点播送（multicast）路由选择,向处于网络中不同位置的一组（部分）用户广播，称为多点播送或组播。 需要路由器知道哪些用户加入哪些组以及用户何时加入或离开这个组。 路由器通过计算得到覆盖整个子网的生成树，再根据组的成员修剪出各组的生成树，多点播送分组仅沿相应生成树转发。,(a) 一个子网 (b) 最左边路由器的生成树 (c) 小组1的多点播送树 (d) 小组2的多点播送树,§5.3 拥塞控制,拥塞 当大量分组进入通信子网，超出了网络的处理能力时，就会引起网络局部或整体性能下降，这种现象称为拥塞。 拥塞不加控制地发展下去，最终导致网络通信停顿（有效吞吐量为零），即阻塞。 拥塞产生的原因 短时间内进入网络的分组数量过多； 局部问题导致性能下降（多个输入对应一个输出，慢速处理器，低带宽线路）。 解决办法 针对某个因素的解决方案，只能对提高网络性能起到一点点好处，甚至可能仅仅是转移了影响性能的瓶颈； 需要全面考虑各个因素。,拥塞控制,拥塞控制与流量控制的差别 拥塞控制（congestion control）需要确保通信子网能够承载用户提交的通信量，是一个全局性问题，涉及主机、路由器等很多因素； 流量控制（flow control）与点到点的通信量有关，主要解决快速发送方与慢速接收方的问题，是局部问题，一般都是基于反馈进行控制的。,拥塞引起网络性能下降,拥塞控制的基本原理,根据控制论，拥塞控制方法分为两类 开环控制（拥塞预防） 通过好的设计来解决问题，避免拥塞发生； 拥塞控制时，不考虑网络当前状态； 闭环控制（拥塞解决） 基于反馈机制； 工作过程 监控系统，发现何时何地发生拥塞； 把发生拥塞的消息传给能采取动作的站点； 调整系统操作，解决问题。,拥塞控制的基本原理,衡量网络是否拥塞的参数 缺乏缓冲区造成的丢包率； 平均队列长度； 超时重传的包的数目； 平均包延迟； 包延迟变化（Jitter）。 反馈方法 向负载发生源发送一个告警包； 包结构中保留一个位或域用来表示发生拥塞，一旦发生拥塞，路由器将所有的输出包置位，向邻居告警； 主机或路由器主动地、周期性地发送探报（probe），查询是否发生拥塞。,拥塞控制算法,拥塞预防策略 开环控制 影响拥塞的网络设计策略,通信量整形和通信量管制,通信量整形（traffic shaping）：迫使分组按预定的速率进入网中，避免突发性的大通信量造成网络瞬间过载。广泛用于面向连接的工作方式（如ATM）。 通信量管制（traffic policing）：网络对用户的通信量进行监视，对遵守约定的用户，保证其要求的服务；对违反协议的数据采取惩罚措施，如丢弃、降低优先级、不保证服务质量等。 以上方法一般用于以虚电路方式工作的网络层，在建立虚电路的时候由双方协商而定。在数据报子网上实现比较困难，但可应用于传输层的连接中。,漏桶（leaky bucket）算法,在主机和网络之间接入一个“漏桶”（固定长度的分组队列），无论主机以多大的速率发送分组，“漏桶”中的分组总是以恒定的速率注入网中。若主机发送过快，当“漏桶”满了以后，多余的分组即被丢弃。,令牌桶（token bucket）算法,令牌桶算法能较快地响应突发数据的到来，且不会丢失数据。 令牌桶中每隔定长的时间产生出一个令牌（计数器），当桶装满后，随后产生的令牌就被丢弃。分组在桶外的缓冲区中等待发送，桶中有多少令牌就允许发送多少个分组，每个令牌用后即销毁，当桶中没有令牌时必须停止发送。 为了平滑大量突发数据的出现，可在令牌桶后面增加一个漏桶，使得漏桶的速率大于令牌桶但小于网络的峰值速率,(a) 漏桶的输入 (b) 漏桶的输出 (c) (e) 一个具有250KB、500KB和750KB容量的令牌桶的输出 (f) 一个500KB令牌桶接一个10MB/s漏桶后的输出,流说明,流说明用于描述通信量的注入模式和服务质量的衡量标准。 流说明既可适用于虚电路上传送的分组，也适用于从源端到目的端传送的数据报序列。 流说明的例子：,拥塞的解决,虚电路子网中采用许可控制（admission control）的三种策略： 一旦出现拥塞的信号，就不再创建任何虚电路，直至拥塞解除。 允许建立新的虚电路，但要仔细选择路由，以便所有新的虚电路绕过拥塞的区域。 在虚电路建立时，子网与主机对所需服务质量进行协商。若不能满足主机最低要求，则拒绝建立连接；否则就保留连接所需的多种资源，避免拥塞发生。,抑制分组（choke packet）： 每个路由器监视本节点的资源利用情况，若某个方向的资源利用率超过一定的门限，则该路由器向有关源节点发送抑制分组，源节点相应减少发往该方向的数据量，直至该方向的拥塞解除。 为了公平合理地控制引起拥塞的源节点的行为，可采用加权公平队列（weighted fair queuing）。,在（高速的）WAN中为了及时解脱拥塞，可以上游使用更多的缓存为代价，这种方法称为站到站抑制分组。 (a)一个仅影响源端的抑制分组。 (b)一个影响沿途所有站点的抑制分组。,负载丢弃（load shedding）： 在没有办法消除拥塞时，只能采取极端措施，即丢弃部分的分组来解决拥塞。 为了使网络能合理地丢弃分组，应用程序应对各分组标注优先级别，以便有选择依据。 延时差控制： 为满足音频或视频数据流传输时对延时变化的敏感性，需要对传输延迟进行控制，以保证可接受的最大延时差。 通过在沿途经过的路由器中计算分组传输的延迟，与预期的传输平均延迟之差决定其在输出队列中的优先次序，能够有效的减小传输延迟差。,多点播送的拥塞控制： 多点播送要实现多个源端到多个目的端的分组传输流，其拥塞控制必须适应目的端的不断变换，加入不同的多点播送组造成的带宽需求变化。 RSVP资源重复利用协议：根据接收者向上传送至发送者的带宽保留消息，沿途设置从源到目的的多点播送树的带宽预留，接收者可同时声明一个或多个想接收的源并在其中自由切换。各个路由器利用这些信息来优化整体带宽使用计划。,(a) 一个网络；,(b) 主机1的多点播送生成树；,(c) 主机2的多点播送生成树。,(a) 主机3申请一条到主机1的通道；,(b) 主机3申请又一条通道，到主机2；,(c) 主机5申请一条到主机1的通道。,§5.4 网络互联,各种不同标准、不同拓扑、不同体系结构、不同协议的异型网络的互联。 连接不同网络的设备统称“网关”（gateway），用来在不同网络之间对数据进行转换。,网络互联设备,根据其工作层次的不同，分别称为： 中继器（repeater）：在物理层上再生放大物理信号。 网桥（bridge）：在数据链路层上，采用存储-转发方式对数据帧进行传递。 多协议路由器（multiprotocol router）：类似网桥，但工作在网络层，转发分组时要进行路由选择，对连接的不同网络还要进行不同协议的转换。 传输网关（transport gateway）：用来建立两个网络间的传输连接。 应用网关（application gateway）：在应用层上进行协议转换。,半网关,网关可从中间分成两部分，每个部分称为一个半网关，每个网络都拥有和管理一个半网关，半网关之间用无源的导线相连，两个半网关的接口处使用相同的中间协议进行网络互连。,网络的差异造成互联的问题,不同类型的网络，其差异可能表现在许多方面，完全消除这些差异是不可能的，网络互联只能尽力而为。,网络互联的两种形式,面向连接的级联虚电路（Concatenated Virtual Circuits） 无连接网络互联（Connectionless Internetworking）,级联虚电路,从信源到信宿的虚电路穿越沿途各网络及网关。其建立方式同普通虚电路一样，只是对连接不同协议网络的多协议路由器要求进行协议转换。,无连接网络互联,网络层只提供最简单、最基本的数据报传输服务：无连接、独立路由、不可靠、无序。,隧道（Tunneling）,实际上要转换两种不同协议的网络是很困难的，甚至不可能。 有一种特殊情况：当信源和信宿都处在同一类型的网络中，而这两个网络又通过另一种类型的网络进行互联。可采用挖隧道方式简单巧妙地解决协议的转换。 在挖隧道方式中，实际并没有进行任何的协议转换，只是将被传输的数据分组作为中间网络分组承载的数据，穿越过去。,互联网络的路由选择,互联网络的路由选择分成两个层次： 单个网络内部的路由选择。其路由选择算法称为内部网关协议IGP （Interior Gateway Protocol）。每个网络都是一个独立的自治系统AS（Autonomous System），可使用不同的路由算法。 网络间的路由选择。其路由选择算法称为外部网关协议EGP（Exterior Gateway Protocol），可能涉及到不同网络协议的转换，需要时使用隧道技术。另外在费用、业务类型、服务质量，甚至政治因素等方面都较为复杂。,分段（fragmentation）,不同的网络的分组长度是不一样的，当一个大分组穿越分组定义较小的网络时，网关必须将一个大分组划分成若干个小的段（fragment），把各段作为单独的分组进行发送。 透明分段：在中间网络进出时分别进行分段和重组工作。每个小分组须含有计数字段或分组结束标志以便出口网关重组，所有分组必须经同一网关发出。 不透明分段：中间网关不重组各分段，每个分段的分组都作为单独原始的分组独立传递，最后在目的地主机上进行重组。,分组的重组（reassembly）,分段的编号,头中包含：分组编号；分组中首分段的编号；分组结束标志位。,防火墙（firewall）,防火墙设有过滤分组的网关，只有检查合格的数据才能进出网络。 由两部分组成：两个用作进出分组过滤的路由器和一个用于对数据内容进行检查的应用网关。,§5.5 因特网上的网络层,因特网：在网络层，可以看作是一组由主干连接在一起的多个自治系统（autonomous system）子网。,IP协议是连接因特网的网络层协议,IP（Internet protocol）分组的头：,INTERNET网络层协议,IP头包括20个字节的固定部分和变长（最长40字节）的可选部分，从左到右传输； 版本域（version）； IHL：IP包头长度，最小为5，最大为15，单位为32-bit word； 服务类型域（Type of Service） 3个优先级位； 3个标志位：D（Delay）、T（Throughput）、R（Reliability）； 2个保留位； 目前，很多路由器都忽略服务类型域。 总长度域（Total length） 标识域（Identification） DF：Dont Fragment；所有机器必须能够接收小于等于576字节的段。 MF：More Fragments；除最后一个段外的所有段都要置MF位。,INTERNET网络层协议,段偏移量（Fragment offset） 除最后一个段外的所有段的长度必须是8字节（基本段长）的倍数。,One large datagram becomes several smaller datagrams,INTERNET网络层协议,生存期（Time to live） 实际实现中，IP包每经过一个路由器TTL减1，为0则丢弃，并给源主机发送一个告警包。 协议域（Protocol）：上层为哪种传输协议，TCP、UDP 头校验和（Header checksum） 只对IP包头做校验； 算法：每16位求反，循环相加（进位加在末尾），和再求反。 源地址（Source address）和目的地址（Destination address）,INTERNET网络层协议,选项（Options） 变长，长度为4字节的倍数，不够则填充，最长为40字节；,IP地址,一些特殊的IP地址,IP子网,子网掩码（ subnet mask ）：将IP地址分为子网地址和主机ID两部分。例如：掩码 255.255.252.0使得一个B类地址包含64个子网，每个子网最多容纳1022个主机。 130.50.4.1130.50.7.254 130.50.8.1130.50.11.254 130.50.64.1130.50.67.254,因特网控制协议,因特网控制消息协议ICMP（Internet Control Message Protocol） 地址解析协议ARP（Address Resolution Protocol） 反向地址解析协议RARP（Reverse Address Resolution Protocol）,因特网控制消息协议ICMP,ICMP用来报告和检测因特网的运行情况，每个ICMP消息类型封装在IP分组中。,地址解析协议ARP,数据链路层只能识别MAC地址，不能识别分组地址。 ARP用来实现IP地址到MAC地址的映射。数据链路层根据映射关系使用MAC地址传送分组数据。,反向地址解析协议RARP,RARP用来实现MAC 地址到IP地址的映射。当一台无盘工作站启动时，仅知道自己的MAC地址时，可利用RARP广播其MAC地址，请求RARP服务器返回他的IP地址。 但RARP广播仅在数据链路层，路由器不会转发，因此每个局域网上都要设置RARP服务器。 后来发明的BOOTP协议可在网络层上使用UDP分组广播，实现MAC地址到IP地址、默认网关地址和子网掩码的映射。,内部网关路由选择协议,因特网由大量自治系统（ autonomous system ）所组成，各自治系统内部可使用不同的路由选择算法。自治系统内的路由选择算法统称为内部网关协议。 最初的因特网内部网关协议采用基于Bellman-Ford的距离矢量算法，称为路由信息协议RIP（Routing Information Protocol）。随着自治系统变得越来越大，RIP协议难以应付庞大的路由信息和网络拓扑的变化，由于无限计算问题造成收敛太慢，需要更好的内部网关协议取代它。,开放最短路径优先OSPF,后来出现的开放最短路径优先OSPF（Open Shortest Path First）内部网关协议采用了链路状态路由选择算法，逐渐成为主要的因特网内部网关协议。它具有： 开放的算法（公开发表） 支持各种距离度量（跳数、延迟、开销等） 动态，能快速适应拓扑结构的变化 支持多种服务类型 支持负载平衡，将负荷分流到多条线路上 支持分级网络 提供安全措施 支持IP隧道,OSPF中自治系统、主干和区域间的关系,外部网关路由选择协议,外部网关协议普遍设计成能提供多种用于自治系统间通信的路由策略，例如边界网关协议BGP（Border Gateway Protocol）。 路由策略基于政治、安全和经济等方面的考虑。为确保路由是适合的，一般由手工配置到每个路由器中。 BGP基本上是一个距离矢量协议，与RIP不同的是每个BGP路由器记录所使用的确切路由，而不是每个目的地的开销，并向邻居说明正在使用的确切路由。,注意：这里没有无穷计算问题，因为每个路由器记录所使用的确切路由。,第五章习题,7，9，14，27，28，29，39，40，49，50,