计算机网络-第五章-网络层.pptVIP

计算机网络 第五章 网络层 本章讨论的互连网络环境 主要内容 转发（Forwarding） 路由（Routing） 拥塞控制 网络互联 因特网的网际层 路由器 1. 转发 两种基本的分组转发策略： 数据报方式：依据分组的目的地址进行转发 虚电路方式：依据分组的连接标识进行转发 两种网络层服务： 无连接服务（或称数据报服务） 面向连接服务（或称虚电路服务） 两种通信子网: 数据报网络 虚电路网络 数据报方式 每个分组是一个独立的传输单位，携带完整的目的地址，在每个路由器上被独立转发。 每个路由器中包含转发表，用于转发决策。转发表是根据路由表生成的、便于快速查找的数据结构，路由表由路由模块负责生成和维护。 分组在传输前不需要预先确定一条从源节点到目的节点的路径，因而这种转发方式也称为无连接方式。 由于每个分组被独立转发，数据报网络无法保证分组传输的顺序，也很难察觉分组的丢失。 数据报方式中的转发表 虚电路方式 相互通信的两个端系统间首先建立一条网络连接，即选择一条从源节点到目的节点的传输通路。（也称面向连接的方式） 每个分组携带一个连接标识，在路由器中按连接标识被转发，其结果是沿着建立起来的路径传输。（保证传输顺序） 数据传输结束后，拆除网络连接。 虚电路的原理 每一条物理信道被看成是由多条逻辑信道组成，逻辑信道在节点内部使用逻辑信道号进行区分。 逻辑信道与网络连接一一对应，因而在节点内部可用逻辑信道号区分不同的网络连接。 从源节点到目的节点的网络连接由它所经过的各条物理信道中的对应逻辑信道组成，这条逻辑通路称为虚电路。虚电路中各条逻辑信道的编号可能不同。 节点内部要记录每条经过它的网络连接所使用的物理线路和逻辑信道，这就是虚电路表。 虚电路的建立与分组转发 虚电路的建立： 源节点发送一个连接建立分组，携带完整的源地址和目的地址，以及源节点与源路由器之间线路上的一个虚电路号。 每个中间节点根据目的地址查找路由表，选择一条合适的输出线路，在输出线路上选择一个当前未用的虚电路号，替换分组头中的虚电路号，并在节点的虚电路表中记录下这条连接 输入线路，输入虚电路号，输出线路，输出虚电路号，然后从输出线路上转发分组。 该过程不断重复直至到达目的节点，目的节点发送一个连接确认分组，分组沿相反路径返回源节点，全双工的虚电路就建立起来了。 分组转发： 每个分组携带相应的虚电路号，中间节点用输入线路和输入虚电路号查找虚电路表，用输出虚电路号替换分组头中的虚电路号，并从输出线路上转发分组，该过程不断重复直至到达目的节点。 虚电路建立示例 虚电路与数据报的比较 2. 路由 路由表是由路由算法建立起来的一张表，通常包含了从目的地址到分组转发路径上下一跳（next hop）地址的映射。 路由问题描述为：给定一组路由器和连接路由器的一组链路，寻找一条从源路由器到目的路由器的最佳路径。 最佳路径：从源路由器到目的路由器代价最小的路径。 路由算法分类 全局路由算法和分布式路由算法 全局路由算法：使用全局状态信息，易于获得较优路径，状态交换需要消耗较多的带宽。 分布式路由算法：使用局部状态信息，一般不容易获得最佳路径，但状态交换消耗的带宽较少。 静态（非自适应）路由算法与动态（自适应）路由算法： 静态路由算法：预先计算好路由表，下载到路由器中，此后不再改变。算法简单，适应性差。 动态路由算法：根据网络当前的拓扑结构和流量计算路由表。适应性强，算法复杂，实现难度大，易引起路由循环和路由振荡。 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算法。 用一个图表示的网络 DV算法思想 每个节点估计到邻居节点之间的“距离”（代价）。 每个节点维护一张路由表，网络中每个节点在表中占据一个表项并作为该表项的索引，每个表项包括：去往该目的节点的输出线路，到该目的节点的估算距离。 每个节点定期和邻居节点交换路由表中的距离矢量部分。 若某个节点x与邻居p的距离为m（即c(x,p)），p发布的距离矢量中py表示节点p与y之间的距离(即dp(y))，则x判断自己通过p到达y的距离为 m+py。利用每个邻居节点发来的距离矢量进行同样计算，x可以找到到达y的最佳输出线路。同