林楠•可路由协议一旦选择一条路径后，用来在路由器之间传送用户的数据报。举例：IP路由选择路由算法路由协议RIP、OSPF、BGP单播与组播路由选择路由选择要求一台主机或路由器具有一个路由表(routingtable)。路由表中的每条记录都包含一目的IP地址和下一跳结点地址。任何一个路由器中都没有到达目的地址的完整路由信息。当一台主机要发送一个数据报，或者一台路由器接收到一个数据报转发时，就会查看路由表，找出与目的地址匹配的记录，然后按照记录中下一跳地址将数据报转发出去。为了提高查询路由表的效率，使得路由表的大小易于管理，并解决安全问题，目前有几种路由选择技术：1）下一跳路由选择2）特定网络路由选择3）特定主机路由选择4）默认路由选择路由选择路由算法路由协议RIP、OSPF、BGP单播与组播路由选择连接成本c(x,x’)例如：c(w,z)=5（成本一般为1，可以根据不同网络带宽与拥塞情况而改变）跳数:数据报到达目的地，所必须通过的路由器的总数。Hopcount越少，该路由线路就越好。带宽:连接的速度。100Mbps的速度优于64Kbps的专线。延迟:把数据报从发送主机传送到接收主机所需要的时间。负载:路由器或网络上数据流通的数量。可靠性:每条网络连接上的差错率。等等……常用路由算法：最短路径算法Dijkstra静态的方法（给定网络的拓扑结构，路由变化很少）扩散法flooding静态的方法距离向量算法D-V动态的方法（网络拓扑结构有变化，路由变化较多）链路状态算法L-S动态的方法最短路径算法Dijkstra（1959）：静态的方法以边的权值为距离来度量最短路径，即权值和最小的路径。经过边数最少的路径不一定是最短路径。最短路径算法采用的数据结构集合S：尚未找到最短路径的结点集合；数组R：记录路径，R[i]为指定源点到结点i的路径上结点i的前一个结点；数组D：D[i]为从指定源点到结点i的最短距离。算法初始化初始化集合S：为除源点外的所有结点；初始化数组R：如果从源点到结点v存在连接，则R(v)=源点，否则为0；初始化数组D：如果从源点到结点v存在连接，则D(v)=该边的权值，否则为无穷大。S路由算法扩散法flooding：不计算路径，有路就走。例如：5到1/2；2到3/6；3到6/4；6到3/7；7到4。存在问题：数据报重复到达某一结点。如3/6数据报循环往复发送。解决方法：1）在数据报头设一计数器，每经过一个结点自动加1，达到规定值时，丢弃数据报；2）在每个结点上建立一个登记表，则数据报再次经过时丢弃。缺点：重复数据报多，浪费带宽。优点：可靠性高，路径最短，常用与军事网络。路由算法距离向量法（D-VDistanceVectorRouting）：分散:每台路由器只了解到达邻近路由器的链路成本，通过迭代计算与相邻路由器交换信息。动态、分布式算法、在RIP协议中使用，应用于较小的系统。实现算法三步骤：1）测量、2）更新邻结点距离向量、3）计算。工作原理：每个路由器用两个向量DiSi来表示该点到网上所有结点的路径距离及其下一跳结点。（如果网络中有n个路由器，则向量DiSi有n个分量；Di表示到第i个结点的最短路径，Si表示按此最短路径到达第i个结点的下一跳。一个数据来了，根据Di找最短路径，根据Si找下一个跳结点。）相邻路由器之间交换路径信息(即交换向量Di)；各结点根据路径信息更新自己的路由表。以J结点为例子路由算法链路状态算法“linkstate”动态算法；在OSPF协议中使用，应用于较大系统。全局:每台路由器都具有整个网络的拓扑图，具有所有链路成本信息。与其他所有路由器共享信息，当有变化时共享变化信息基本工作思想:1）发现它的邻结点，并得到其网络地址；当一个路由器启动后，向每个端口发送hello数据报，另一端的路由器发回一个应答来说明它是谁；因此得知它有多少邻居。2）测量它到各邻结点的延迟或开销；发送一个echo数据报要求对方立即响应，通过测量一个来回时间再除以2，就可以得到一个延迟估计值，想要更精确，可重复这一过程，取平均值。基本工作思想:3）组装一个数据报以告知它刚知道的所有信息；基本工作思想:4）将这个数据报发给所有其他路由器；（与距离向量法不同）用扩散法（向邻接的结点）发布链路状态数据报。每个结点中有个表，记录已经收到过的数据报，不再重复转发。例如：结点B的邻结点有A，C，F；所以有A/C/F三个发送和ACK标志。发送标志=0：从该结点收到数据报；ACK=1向该结点发一个应答。