【用TCP/IP进行网际互联-卷二】IP:选路算法

lqseu

选录软件理论上可以划分为两组，其中一组用来为数据报选择正确的路由，另一组由增加，改变或者删除路由的过程组成（维护）。
一个基本原则是：应当选择能使查找路由花费最小的IP数据结构和算法，维护路由的花费则不那么重要。
1.选路表的数据结构
保存路由的主要数据结构是数组，数组中的每一个元素对应一个散列表元，并包含一个指针，指向被装入这个散列表元中的通往目的站路由记录链表。

route：
链表中一个结点的内容，包含一个可能的目的站的选路信息：
        目的地址（可能是一个网络，子网，和可能是完整的主机地址）
        与目的地址一起使用的掩码
        该路由中下一跳网关的IP，网络用来到达下一跳网关的接口

rttable:路由表，指向route结构的指针数组。
rtinfo：默认路由信息等全局数据项。

2.为数据报选择路由
rtget：给定一个目的地址，使用rtget查找，并返回一个指向相应路由表项的指针。
1）首先判断选路表是否初始化，若没有，则完成初始化工作（rtinit）
2）等待互斥信号量，以保证任何时间只有一个过程有权访问选路表。
3）计算目的地址散列值，以此作为表内查找的索引，在选路表项指向的链表内查找。
3）对于每个表项调用netmatch进行匹配，如果没有精确匹配，使用default路由。
4）检查查找到的是否为一个有效指针，如果是，该路由表项的引用计数和使用计数加1（维护软件使用这两个计数来决定如果删除与该路由相关的存储区是否安全）。计数字段提供了一种网络管理的手段，用以掌握每个表项在数据报选择路由时使用的频繁程度。

3.选路表的维护
rttimer：实现定期的表项更新任务。
rtadd：
1）调用rtnew分配新结点，初始化各字段。
2）对于非默认路由，调用rthash计算新路由的索引值。
3）遍历链表找到插入的地方，如果已存在，比较新旧路由的度量，留下较优的一个。如果不存在，直接插入新节点。
rtdel：计算散列值，搜索链表，删除，递减引用值。

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/74413/showart_1965383.html