搜索
第1页共2页20×25=500网络层之转发与路由选择转发：当一个分组到达路由器的一条输入链路时，路由器必须将该分组移动到适当的输出链路。在因特网中，每个端系统都具有一个称为IP地址的地址，当源主机要向目的端系统发送一个分组时，源主机在该分组的首部包含了目的地的IP地址。这就像邮政地址那样，既有寄件人地址，也有收件人地址。当一个分组到达网络中的路由器时，路由器检查该分组的一部分，并向一台相邻路由器转发该分组。而每台路由器都有一个转发表（forwardingtable），用于将目的地址或目的地址的一部分映射成为输出链路。而路由选择就是当某分组到达路由器时，路由器检查该地址，并用这个目的地址搜索其转发表，以发现适当的出链路。路由器则将分组导向该出链路。端到端选路过程与一个人要去一个从未去过的地方类似，比如说A从0市要去一个位于1市2区3街4号的目的地，他先驾车到附近的加油站询问怎样才能到达1市2区3街4号，加油站的服务员从该地址中抽取了1市这个部分，告诉A他需要上XX高速公路，在该公路上行驶时有一个邻近分岔路口的加油站，问路后服务员从地址中抽取了2区部分，告诉他他需要走YY公路，一段时间后，在路边时他向一个当地人问路，当地人抽取了地址中的3街，给他指了路，A越来越接近目的地了，最后他很容易的在3街得知了如何到达4号，他最后成功抵达。在上述类比中，被问路的人相当于路由器。每个路由器具有一张转发表，路由器通过检查到达分组的首部字段的值来转发分组，然后使用该值在该路由器的转发表中索引查询，存储在转发表项中的该首部的值指出了该分组将被转发的路由器的输出链路接口。见下图：一个首部字段值为B的分组到达路由器后，将被转发到接口2.而路由器的转发表又是从何而来、如何配置的呢？这是一个关键的问题，它提示了路由选择和转发间的重要的相互作用关系。转发表需由路由选择算法确定。路由选择算法是计算出一条从发送方到接收方通过路由器网络的好路径的算法，通常一条好路径指具有最低费用的路径(least-costpath)。还有最短路径，即在源和目的地之间的具有最少链路数量的路径。我们可以用图来形式化地描述路由选择问题，见下图：第2页共2页20×25=500图中的结点表示路由器，这是做出分组转发决定的点，连接这些结点的边表示这些路由器之间的物理链路。每条边的近旁还标有一个值来表示它的费用。若以R1为源结点，R5为目的结点，则很显然，它们之间最低费用路径是(R1,R4,R5),同时它也是最短路径。一旦选定一条路径，就可以计算出它的总费用和所经链路数量。对路由选择算法的一种广义分类方法是根据该算法是全局式的还是分散式的来加以区分：(1)全局式路由选择算法：用完整的、全局性的网络知识计算出从源到目的地之间的最低费用路径。也就是说，该算法以所有结点之间的连通性和所有链路的费用为输入，这就要求算法在真正开始之前，要以某种方式获得这些信息。实践中，具有全局状态信息的算法常被称作链路状态算法(LinkState,LS)。上页的图例即为此种算法。(2)分散式路由选择算法：没有结点拥有关于所有网络链路费用的完整信息，而每个结点仅有与其直接相连链路的费用知识即可开始工作，再通过迭代计算与相邻结点交换信息，以迭代、分布式的方式计算出最低费用路径。距离向量算法即为分散式。