计网第五章-网络层

第五章 网络层

1. 网络层的主要功能：交换和路由

2. 距离向量路由算法：在距离向量路由中，每个路由器周期性的将自己关于整个网络的信息发送给他的邻居

   • 每个路由都保存关于整个网络的信息
   • 仅仅和邻居交换网络信息
   • 信息的交换是通过有规律的时间间隔来进行的

3. 链路状态路由算法：链路状态路由中，每个路由器和互联网络中的所有其他路由器共享关于其邻居的信息

   • 共享关于邻居的信息
   • 共享的信息发送给所有的路由器
   • 信息的共享在有规律的时间间隔内进行

4. 链路状态数据库

   • $Dijkstra$算法：从路由器到网络的链路的费用才有效，而从网络到路由器的链路的费用总是0

     • 每个路由器在使用$Dijkstra$算法时，根据下面四个步骤来形成自己的最短路径树（最小支撑树）

       ①选择自己作为根的结点，并将根标记为永久性结点。算法接着从根出发连接其所有邻居结点。这种结点是临时性的

       ②算法比较所有的临时连接，找出费用最小的路径，该路径上的所有弧和结点被标记为最短路径树上的永久部分

       ③算法考察链路状态数据库，找出从这个选定的最短路径向外延伸所能连接的所有非永久性结点，将这些结点临时性地加到最短路径树上

       ④如果所有的结点已经成为最短路径树上的永久部分，则算法结束，去掉非永久性的弧。否则，转步骤②继续执行。

   • $Dijkstra$算法总结

     ①初始化：设$N$表示网络结点集合，先令$N={1}$，对所有不在$N$中的结点写出：

     $S(V)= \begin{cases} L(1,V) & \text {;若结点V与结点1相邻} \\ \infty & \text {;若结点V与结点1不相邻} \end{cases}$

     ②找出一个不在$N$中的结点W，使$S(W)$值为最小，把$W$加入$N$中，然后对所有不在$N$中的结点按下式更新：

     $S(V) \leftarrow min[S(V),S(W)+L(W,V)]$

     ③重复步骤②，直到所有的网络结点都在$N$中为止