搜索
计算机网络第五章网络层本章讨论的互连网络环境图5-1互连网络环境主要内容转发（Forwarding）路由（Routing）拥塞控制网络互联因特网的网际层路由器1.转发两种基本的分组转发策略：数据报方式：依据分组的目的地址进行转发虚电路方式：依据分组的连接标识进行转发两种网络层服务：无连接服务（或称数据报服务）面向连接服务（或称虚电路服务）两种通信子网:数据报网络虚电路网络数据报方式每个分组是一个独立的传输单位，携带完整的目的地址，在每个路由器上被独立转发。每个路由器中包含转发表，用于转发决策。转发表是根据路由表生成的、便于快速查找的数据结构，路由表由路由模块负责生成和维护。分组在传输前不需要预先确定一条从源节点到目的节点的路径，因而这种转发方式也称为无连接方式。由于每个分组被独立转发，数据报网络无法保证分组传输的顺序，也很难察觉分组的丢失。数据报方式中的转发表ABCDEF(a)目目目目目目目目BBCDEFCCEE目目A目目目目目(b)目5-2(a)目目目目(b)目目A目目目目虚电路方式相互通信的两个端系统间首先建立一条网络连接，即选择一条从源节点到目的节点的传输通路。（也称面向连接的方式）每个分组携带一个连接标识，在路由器中按连接标识被转发，其结果是沿着建立起来的路径传输。（保证传输顺序）数据传输结束后，拆除网络连接。虚电路的原理每一条物理信道被看成是由多条逻辑信道组成，逻辑信道在节点内部使用逻辑信道号进行区分。逻辑信道与网络连接一一对应，因而在节点内部可用逻辑信道号区分不同的网络连接。从源节点到目的节点的网络连接由它所经过的各条物理信道中的对应逻辑信道组成，这条逻辑通路称为虚电路。虚电路中各条逻辑信道的编号可能不同。节点内部要记录每条经过它的网络连接所使用的物理线路和逻辑信道，这就是虚电路表。虚电路的建立与分组转发虚电路的建立：源节点发送一个连接建立分组，携带完整的源地址和目的地址，以及源节点与源路由器之间线路上的一个虚电路号。每个中间节点根据目的地址查找路由表，选择一条合适的输出线路，在输出线路上选择一个当前未用的虚电路号，替换分组头中的虚电路号，并在节点的虚电路表中记录下这条连接输入线路，输入虚电路号，输出线路，输出虚电路号，然后从输出线路上转发分组。该过程不断重复直至到达目的节点，目的节点发送一个连接确认分组，分组沿相反路径返回源节点，全双工的虚电路就建立起来了。分组转发：每个分组携带相应的虚电路号，中间节点用输入线路和输入虚电路号查找虚电路表，用输出虚电路号替换分组头中的虚电路号，并从输出线路上转发分组，该过程不断重复直至到达目的节点。虚电路建立示例ABCDEFHHHHHH目目目目(a)目目目目HHBH0112BCEE0001目目目目AHHH0012CCAF0110CCCF0120HHHH0123BAB001DDD012AAF011HFH001EB00DE01AEBCD目目目目目目目目1－ABCD2－ACD3－BCD4－BAE5－AEFD6－BFEF(b)(b)目目目目目目目虚电路与数据报的比较问题数据报网络虚电路网络电路建立不需要需要寻址每个分组携带完整的源和目的地址每个分组携带一个很短的虚电路号状态信息路由器不保留关于连接的状态信息路由器需要记录每条虚电路的状态路由每个分组独立路由在建立虚电路时选择路由，此后所有分组使用该路由路由器失效的影响除了在路由器崩溃时正在传输的分组丢失以外，没有其它影响经过失效路由器的所有虚电路都中断服务质量提供困难如果能提前为每条虚电路预留足够的资源，较容易拥塞控制困难如果能提前为每条虚电路预留足够的资源，较容易2.路由路由表是由路由算法建立起来的一张表，通常包含了从目的地址到分组转发路径上下一跳（nexthop）地址的映射。路由问题描述为：给定一组路由器和连接路由器的一组链路，寻找一条从源路由器到目的路由器的最佳路径。最佳路径：从源路由器到目的路由器代价最小的路径。路由算法分类全局路由算法和分布式路由算法全局路由算法：使用全局状态信息，易于获得较优路径，状态交换需要消耗较多的带宽。分布式路由算法：使用局部状态信息，一般不容易获得最佳路径，但状态交换消耗的带宽较少。静态（非自适应）路由算法与动态（自适应）路由算法：静态路由算法：预先计算好路由表，下载到路由器中，此后不再改变。算法简单，适应性差。动态路由算法：根据网络当前的拓扑结构和流量计算路由表。适应性强，算法复杂，实现难度大，易引起路由循环和路由振荡。2.1距离矢量路由算法路由问题本质上是图论中的一个问题：找出任意两个节点之间代价最小的路径。对于源节点x来说，即是寻找一个直接邻居p，满足：dx(y)=minp{c(x,p)+dp(y)}，p∈N(x)（Bellman-Ford方程）其中，y是目的节点，N(x)是x的邻居集合，dx(y)为从x到y的最小代价路径的代价，c(x,p)为x到其直接邻居p的链路代价。距离矢量（DV）算法采用Bellman-Ford方程求解任意两个节点之间代价最小的路径，因此DV算法也称为分布式Bellman-Ford算法。用一个图表示的网络BBBBBB21312561目5-4目目目目目目目目目DV算法思想每个节点估计到邻居节点之间的“距离”（代价）。每个节点维护一张路由表，网络中每个节点在表中占据一个表项并作为该表项的索引，每个表项包括：去往该目的节点的输出线路，到该目的节点的估算距离。每个节点定期和邻居节点交换路由表中的距离矢量部分。若某个节点x与邻居p的距离为m（即c(x,p)），p发布的距离矢量中py表示节点p与y之间的距离(即dp(y))，则x判断自己通过p到达y的距离为m+py。利用每个邻居节点发来的距离矢量进行同样计算，x可以找到到达y的最佳输出线路。同样可以找到到达所有其它节点的最佳输出线路，更新路由表。DV算法举例ABCDEFGHLKJI目目(a)0AB122540142318172192429CDEFGHIJKL203119830196014722921283624224031192210098202820173018121006152436182772031200112233AAIHIIHHI目KK(b)AIHKJA=8JI=10JH=12JK=6目目目目目目目目目目目目5-5(a)目目目目(b)J目A目I目H目K目目目目目目目(c)J目目目目目(c)计数到无穷问题ABCD∞∞∞∞∞∞111122233目目目目目目目目目目目目目ABCD123332335544655目目目767767∞∞∞(a)(b)目5-6目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目目2.2链路状态路由算法基本思想：每个节点利用可靠方法获得全网拓扑信息，抽象成一张带权图，利用图论的方法求到各个目的节点的最短路径。链路状态（LS）路由算法包括以下五个部分：发现邻居，获知邻居的网络地址；测量到每个邻居的延时；将以上信息构造成链路状态分组；向所有节点发送链路状态分组；计算到每个节点的最短路径。链路状态路由算法（续）发现邻居每个节点定期在与之相连的每条输出线路上发送特殊的询问分组，要求线路另一端的节点用自己的网络地址进行响应。测量链路代价每个节点估算与之相连链路的代价。构造链路状态分组在收集了全部的邻居信息及链路代价后，构造链路状态分组。发送链路状态分组采用扩散法发送，并使用序号及寿命限制分组的无限转发。计算新路由在收集到全部的链路状态信息后，建立通信子网图，运行Dijkstra算法求到各目的顶点的最短路径，更新路由表。链路状态分组格式ACBDFE51423786(a)Seq.AAgeB4E5Seq.BAgeA4C2Seq.CAgeB2D3Seq.DAgeC3F7Seq.EAgeA5C1Seq.FAgeB6D7F6E1F8E8(b)目5-7(a)目目目目目目(b)目目目目目目目目目目LS算法的优缺点每个节点只发布与它直接相连的链路的状态，可靠性高。每个节点在计算路由时依据的是全局状态信息，易于得到最佳路由。需要较大的存储空间存放所有节点发来的链路状态分组，路由计算时间长，不适用于大规模网络。2.3层次路由将路由器划分到不同的区域中，各区域内的路由器只负责本区域内的分组转发，目的地址不在本区域内的分组交给指定的区域路由器处理。一个两级网络的例子。划分区域的一种很自然的方法是按管理域（也称自治域，AS）进行划分。一个两级网络的示例1A1B1C3A3B4A4B4C5A5B5C2B2A2C2D5D5E目目1目目2目目3目目4目目5(a)目目1B11C11B21B31B31B41C31C21C31C41C41C41C51B51C61C5目目目目目目目目1A1B1C2A2B2C2D3A3B4A4B4C5A5B5C5D5E(b)目目1B11C11B21C21C31C4目目目目目目目目1A1B1C2345(c)目5-8(a)目目目目目目(b)目目目1A目目目目目(c)目目目目目目1A目目目目自治域分区对于较大的自治域，还可以进一步将自治域划分成区（area），区是从管理上配置成相互交换路由信息的路由器的集合。目1目0目3目2R9R8R7R1R2R3R4R6R5目5-9目目目目目目目域间路由域间路由的复杂性：因特网规模庞大且结构复杂；每个域可运行自己的内部路由协议，并使用自己的代价计算方案；一个域可能不信任来自某个域的路由信息；一个域可能不愿意为其它域转发分组。域间路由只能是找到一条可达的路径，找到最优路径是不可能的。域间路由以AS枚举列表的形式通知到达某个特定网络的完全路径，以防止建立带环的路径。一个域间路由的例子目目目目目目A目AS2目目目目目目目B(AS3)目目P(AS4)目目目目AS1目目目Q目AS5目目目R目AS6目目目S目AS7目128.96192.4.153192.4.32192.4.3192.12.69192.4.54192.4.23目5-10目目目目BGP目目目目目目分级路由的利与弊分级路由可显著减小路由表的大小，减少由路由信息交换带来的通信量，但选择的路由可能不是最佳的。分级路由实际上是在路由的可扩展性以及路由选择优化之间进行权衡。在大型网络中，可扩展性永远比最优化重要得多。2.4广播路由实现广播发送的方法：N次单播：向每一个目的主机单独发送。实现简单，但浪费带宽，而且要求源主机知道所有目的主机。扩散法：可靠性高，但会产生较多分组拷贝，需要有限制扩散的措施。多目的路由：当多个目的地址使用同一条输出线路时，只在线路上发送一个分组拷贝。节省带宽，但仍要求源主机知道所有目的主机。使用以源节点为根的生成树：生成的分组拷贝最少，但要求路由器知道通信子网的拓扑结构。反向路径转发：只使用节点的单播路由表转发广播分组，不需要生成树的知识，也不需要知道所有的目的主机。反向路径转发基本思想：当广播分组到达路由器时，路由器检查分组的源地址与输入线路；若输入线路与单播路由表中去往该地址的输出线路相同，扩散该分组，否则丢弃分组。优点：算法合理、有效、易于实现且开销不大。反向路径转发的例子ABCDEFGJONMLHI(a)ABCDEFGJONMLHI(b)IFHJNAGEDKOMECBOGALMNDKKKLB(c)目5-11(a)目目目目(b)I目目目目(c)目目目目目目目目目2.5互联网中的多播传输基本思想：所有欲接收相同分组的节点构成一个多播组，每个组分配一个唯一的多播地址，发往该组的分组均以该多播地址为目的地址。任何一个主机可以选择加入或离开这个组，组管理协议负责建立、维护和删除多播组。多播路由协议负责为每个组建立多播转发树（可到达该组所有成员主机的路径树）。当多播分