Unix/Linux编程：网际协议(IP)的选路表和选路算法

超、凢脫俗 2022-10-07 10:51 416阅读 0赞

# 路由维护和查找 #

选路软件在理论上可以划分为两组。其中一组由那些用来为数据报选择正确路由的过程组成，另一组由增加、改变或删除路由的过程组成。

因为网关必须为自己所处理的每个数据报判定路由，所以**路由查找程序代码决定了网关的整体性能**。因此，通常将查找程序代码优化，以期达到最高速度。

\*路由的插入、改变或者删除的速率通常比为数据报选择路由的速率要低得多。计算新路由的程序需要与其他设备通信以建立其可达性。它们在重定向之前花任意长的时间。因此，路由更新过程不需要像查找操作那样被优化。其基本观点是：

> 应当选择能使路由花费最小的IP数据结构和算法，维护路由的花费并不那么重要

虽然在早期的TCP/IP软件中，选路表的查找经常采用线性查找，但现在大多数系统利用一张散列表，使之能够快速查找任意大小的选路表

# 选路表 #

## 选路表结构 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]  
如上，保存路由的主要数据结构是数组。数组中的每一个元素对应一个散列表元，并包含一个指针，指向被装入这个散列表中的通往目的站的路由记录链表。表中的每一个记录包含一个IP目的地址、子网掩码、下一跳地址、用于向下一跳地址发送数据的网络接口，以及其他在路由管理中使用的信息。

## 选路表数据结构 ##

route 结构定义了链表中一个节点的内容，并包含一个可能的目的站的选路信息

*  字段rt\_net指出其目的地址(可能是一个网络、子网或者完整的主机地址)
 *  字段rt\_mask指出与此目的站一起使用的32位掩码。
 *  字段rt\_wg指出该路由中下一跳网关的IP地址
 *  字段rt\_metric给出网关距离，以跳(hop)为单位
 *  字段rt\_ifnum给出这条路由使用的网络接口的内部编码(即网络用来到达下一跳网关的接口)

剩下的几个字段供IP软件使用

*  字段rt\_key是一个排序关键字，在向链表中插入结点时使用
 *  字段rt\_refcnt包含一个进程的引用计数器，用于保存指向路由的指针
 *  字段rt\_usecnt记录该路由被使用的次数
 *  字段rt\_next包含一个指针，指向链表的下一个结点(链表的最后结点中此值为NULL)

/* route.h - RTFREE */
    
    /* 路由表条目 : */
    struct route {
        
    	IPaddr	rt_net;		/* 此路由的网络地址 	*/
    	IPaddr	rt_mask;	/* 此路由的掩码 			*/
    	IPaddr	rt_gw;		/* 下一跳 				*/
    	u_short	rt_metric;	/* 距离度量 		*/
    	u_short	rt_ifnum;	/* 接口号 			*/
    	short	rt_key;		/* 排序键 			*/
    	short	rt_ttl;		/* 生存时间（秒） 	*/
    	struct	route *rt_next;	/* 此哈希值的下一个条目 	*/
    /* stats */
    	int	rt_refcnt;	/* 当前引用计数 	*/
    	int	rt_usecnt;	/* 迄今为止的总使用次数  */
    };
    
    /* 路由表全局数据 : */
    struct rtinfo {
        
    	struct	route	*ri_default;
    	int		ri_bpool;
    	Bool		ri_valid;
    	int		ri_mutex;
    };
    
    #define	RT_DEFAULT ip_anyaddr	/* 默认网络 		*/
    #define	RT_LOOPBACK ip_loopback	/* 环回网 		*/
    #define	RT_TSIZE	512	/* these are pointers; it's cheap	*/
    #define	RT_INF		999	/* 此路由不超时 		*/
    
    #define	RTM_INF		16	/* 无限度量 	*/
    
    /* rtget() 的第二个参数...  */
    
    #define	RTF_REMOTE	0	/* 流量来自远程主机 	*/
    #define	RTF_LOCAL	1	/* 流量是本地产生的 	*/
    
    #define	RT_BPSIZE	100	/* 最大路由数 		*/
    
    /* RTFREE - 删除路由引用（假设 ri_mutex HELD） 		*/
    
    #define	RTFREE(prt)					\
    	if (--prt->rt_refcnt <= 0) {
          			\
    		freebuf(prt);				\
    	}
    
    extern	struct	rtinfo	Route;
    extern	struct	route	*rttable[];
    
    int rtadd(IPaddr, IPaddr, IPaddr, unsigned, unsigned, unsigned);
    int rtdel(IPaddr, IPaddr), rthash(IPaddr), rtfree(struct route *);
    struct route *rtget(IPaddr, Bool);
    void rtinit(void);
    void ipredirect(struct ep *, unsigned, struct route *);
    void ipdbc(unsigned, struct ep *, struct route *);

除router外，还定义了选路表rttable，如上图所示，rttable是指向route结构的指针数组

除选路表之外，IP还需要其他几个数据项，它们保存在全局结构rtinfo中。比如，

*  系统提供唯一的“默认路由”，任何不想选路表中的目的站都可以使用。字段ri\_default指向一个route结构，在这个router中包含的是默认路由的下一跳地址
 *  字段ri\_valid是一个bool变量，如果此路由的数据结构已经被初始化，则它的值为TRUE

# 路由的生成源及保存时间 #

选路表中的信息有几个来源。通常，当系统启动时，初始化程序从部分存储器中获得一组初始路由，并将它们安装到选路表中。在执行过程中，传入的报文会导致ICMP或者选路协议软件改变现有的路由或者建立新路由。最后，网络管理员也可以增加路由或者重定向

选路表项的易失性与它的来源有关。比如，初始路由被认为是简单估计的，只要有其他地方发来的路由信息，它就应该被替换。然而，网络管理员必须能够推翻任何路由并建立不可变的永久性路由，以使它们能够排除网络中的路由问题，而无需路由协议的干涉。

为了适应路由的灵活性，每个选路表项中的rt\_ttl(寿命)字段指出此表项还能保持多少时间。当rt\_ttl达到0-时，路由失效并被丢弃。由选路协议建立的路由，其寿命根据协议规则计算得到，而管理员能够建立寿命无限长的路由，以保证它们不会被删除。

# 为数据报选择路由 #

## 实用过程 ##

一些实用过程提供了选择路由时用到的功能。过程netnum利用地址类别确定在地址字段中哪些八位组包含的是网络部分，哪些八位组是主机部分，从而提取出IP地址中的网络部分。它返回给出的地址，但这时其主机地址字节为全0

/* netnum.c - netnum */
    
    #include <conf.h>
    #include <kernel.h>
    #include <network.h>
    
    /*------------------------------------------------------------------------
     *  netnum  -  compute the network portion of a given IP address
     *------------------------------------------------------------------------
     */
    IPaddr netnum(IPaddr ipa)
    {
        
    	IPaddr	mask = ~0;
    
    	if (IP_CLASSA(ipa)) mask = hl2net(0xff000000);
    	if (IP_CLASSB(ipa)) mask = hl2net(0xffff0000);
    	if (IP_CLASSC(ipa)) mask = hl2net(0xffffff00);
    	return ipa & mask;
    }

在为数据报选择路由时，IP使用过程netmatch，将目的(主机)地址与选路表项中的地址进行比较，选路表中包含了子网掩码和给定网络的IP地址。netmatch使用子网掩码来屏蔽目的地址中的主机位，并将结果与表项中的网络地址相比较，如果1它们相符，netmatch返回TRUE，否则返回FALSE。

广播是一种特殊情况，因为要采取何种动作取决于数据报的来源。来自网络接口的广播数据报必须经由伪网络接口发送给本地机器，而本地生成的广播数据报必须被发送到适当的网络接口。为了区分这两种情况，软件使用了一个特定主机路由(全“1”的掩码)为来自网络的广播数据报选择路由，并用特定网络路由(掩码仅屏蔽网络部分)为向外发送的广播选择路由。这样netmatch明确的判定一个广播数据报的来源，并使用IP原地址来决定此广播是否与给定路由相符。

/* netmatch.c - netmatch */
    
    #include <conf.h>
    #include <kernel.h>
    #include <network.h>
    
    /*------------------------------------------------------------------------
     *  netmatch  -  Is "dst" on "net"?
     *------------------------------------------------------------------------
     */
    Bool netmatch(IPaddr dst, IPaddr net, IPaddr mask, Bool islocal)
    {
        
    	if ((dst & mask) != (net & mask))
    		return FALSE;
    	/*
    	 * local srcs should only match unicast addresses (host routes)
    	 */
    	if (islocal)
    		if (isbrc(dst) || IP_CLASSD(dst))
    			return mask != ip_maskall;
    	return TRUE;
    }

要为一个数据报选择路由，IP必须查看它是否认识该数据报目的地址的有效子网掩码。要做到这一点，IP调用过程netmask

/* netmask.c - netmask */
    
    #include <conf.h>
    #include <kernel.h>
    #include <network.h>
    
    IPaddr netnum(IPaddr);
    
    /*------------------------------------------------------------------------
     *  netmask  -  set the default mask for the given net
     *------------------------------------------------------------------------
     */
    IPaddr netmask(IPaddr net)
    {
        
    	IPaddr	netpart;
    	int	i;
    
    	if (net == 0)
    		return net;
    	/* check for net match (for subnets) */
    
    	netpart = netnum(net);
    	for (i=0; i<Net.nif; ++i)
    		if (nif[i].ni_svalid && nif[i].ni_ivalid &&
    		    nif[i].ni_net == netpart)
    			return nif[i].ni_mask;
    	if (IP_CLASSA(net)) return hl2net(0xff000000);
    	if (IP_CLASSB(net)) return hl2net(0xffff0000);
    	if (IP_CLASSC(net)) return hl2net(0xffffff00);
    	return ~0;
    }

netmask把IP地址当中参数，然后检查几种情况。根据约定，如果目的地址全为“0”，则意味着使用默认路由，因此netmask返回全“0”的子网掩码。对其他类型的目的站，netmask调用netnum从目的地址提取出网络部分1，然后检测每个与本机直接相连接的网络，如果有任何与人地直接连接的网络地址与目的地址的网络部分相符，netmask从和此网络接口结构中提取出子网掩码，然后将其返回调用者。最后，如果IP找不到有关这个目的地址的子网掩码的信息，它就根据地址类别是A、B、还是C来设置屏蔽地址网络部分的子网掩码。

选路函数调用使用过程rthash计算目的地网络地址的散列值

/* rthash.c - rthash */
    
    #include <conf.h>
    #include <kernel.h>
    #include <network.h>
    
    /*------------------------------------------------------------------------
     *  rthash  -  compute the hash for "net"
     *------------------------------------------------------------------------
     */
    int rthash(IPaddr net)
    {
        
    	int		bc = IP_ALEN;	/* # bytes to count	*/
    	unsigned int	hv = 0;		/* hash value		*/
    
    	if (IP_CLASSA(net)) bc = 1;
    	else if (IP_CLASSB(net)) bc = 2;
    	else if (IP_CLASSC(net)) bc = 3;
    	else if (IP_CLASSD(net))
    		return ((net>>24) & 0xf0) % RT_TSIZE;
    	while (bc--)
    		hv += ((char *)&net)[bc] & 0xff;
    	return hv % RT_TSIZE;
    }

散列函数是一个简单有效的函数。对于A、B或者C类地址，rthash将网络地址的每个八位组相加，所得的和除以散列表长度，最后返回余数。对于D类地址，rthash将网络地址的前4为比特数乘以16，所得的值除以散列表长度，最后返回余数。

## 获得一个路由 ##

给定一个目的地址，过程rtget在选路表中查找，并返回一个指针，指向找到的路由的表现

/* rtget.c - rtget */
    
    #include <conf.h>
    #include <kernel.h>
    #include <network.h>
    
    /*------------------------------------------------------------------------
     *  rtget  -  get the route for a given IP destination
     *------------------------------------------------------------------------
     */
    struct route * rtget(IPaddr dest, Bool local)
    {
        
    	struct	route	*prt;
    	int		hv;
    
      
    	if (!Route.ri_valid)     // 全局变量Route.ri_valid指出选路表是否已经被初始化了
    		rtinit();           // 路由表还没有被初始化， 调用rtinit()
    	wait(Route.ri_mutex);
    	hv = rthash(dest);
    	for (prt=rttable[hv]; prt; prt=prt->rt_next) {
        
    		if (prt->rt_ttl <= 0)
    			continue;		/* route has expired */
    		if (netmatch(dest, prt->rt_net, prt->rt_mask, local))
    			if (prt->rt_metric < RTM_INF)
    				break;
    	}
    	if (prt == 0)
    		prt = Route.ri_default;	/* may be NULL too... */
    	if (prt != 0 && prt->rt_metric >= RTM_INF)
    		prt = 0;
    	if (prt) {
        
    		prt->rt_refcnt++;
    		prt->rt_usecnt++;
    	}
    	signal(Route.ri_mutex);
    	return prt;
    }

全局变量Route.ri\_valid指出选路表是否已经被初始化了，如果没有则调用rtinit初始化选路表。一旦选路表以及相关的数据结构已经被初始化，rtget等待互斥信号量，以保证任何时间只有一个过程有权访问选路表。然后它计算目的地址值的散列值，以此作为表内查找的索引，并在选路表表项指向的链表内查找。

对于每一个路由表项，rtget调用netmatch，检查其入口参数给出的目的地址是否能与表项中的地址匹配。

*  如果在查找中没有发现精确的匹配，rtget使用Route.ri\_default默认路由。
 *  如果既没有精确匹配，又没有默认路由。那么，当完成路由查找工作之后，rtget还必须继续检测它找到的是否是一个有效指针
 *  如果是有效指针，rtget在返回调用者之前，要给路由表项中的引用计数值和使用计数值字段加1
    
     *  维护软件利用**引用计数**字段来决定如果删除与该路由相关的存储区是否安全。只要调用rtget的过程还需要这个路由表，则该表项中的引用计数值就不为0.
     *  **使用计数**字段提供了管理网络的一种手段，用以掌握每个表项在数据报选择路由时使用的频繁程度

## 数据结构初始化 ##

过程rtinit初始化选路表和默认路由，生成互斥信号量，为路由链表中的节点分配存储区并将存储区链接成一个空闲列表：

/* rtinit.c - rtinit */
    
    #include <conf.h>
    #include <kernel.h>
    #include <sleep.h>
    #include <network.h>
    
    struct	rtinfo	Route;
    struct	route	*rttable[RT_TSIZE];
    
    /*------------------------------------------------------------------------
     *  rtinit  -  initialize the routing table
     *------------------------------------------------------------------------
     */
    void rtinit(void)
    {
        
    	int i;
    
    	for (i=0; i<RT_TSIZE; ++i)
    		rttable[i] = 0;
    	Route.ri_bpool = mkpool(sizeof(struct route), RT_BPSIZE);
    	Route.ri_valid = TRUE;
    	Route.ri_mutex = screate(1);
    	Route.ri_default = NULL;
    }

# 选路表的定期维护 #

系统定期发起清理选路表的行动，它递减选路表中所有表项的寿命字段值，如果某个寿命字段超时，则丢弃对应的路由。过程rttimer用来实现这项定期性的表项更新任务

/* rttimer.c - rttimer */
    
    #include <conf.h>
    #include <kernel.h>
    #include <proc.h>
    #include <network.h>
    
    extern	Bool	dorip;		/* TRUE if we're running RIP output	*/
    extern	int	rippid;		/* RIP output pid, if running		*/
    
    /*------------------------------------------------------------------------
     * rttimer - update ttls and delete expired routes
     *------------------------------------------------------------------------
     */
    void rttimer(unsigned int delta)
    {
        
    	struct	route	*prt, *prev;
    	Bool		ripnotify;
    	int		i;
    
    	if (!Route.ri_valid)
    		return;
    	wait(Route.ri_mutex);
    	
    	ripnotify = FALSE;
    	for (i=0; i<RT_TSIZE; ++i) {
        
    		if (rttable[i] == 0)
    			continue;
    		for (prev = NULL, prt = rttable[i]; prt != NULL;) {
        
    			if (prt->rt_ttl != RT_INF)
    				prt->rt_ttl -= delta;
    			if (prt->rt_ttl <= 0) {
        
    #ifdef	RIP
    				if (dorip && prt->rt_metric < RTM_INF) {
        
    					prt->rt_metric = RTM_INF;
    					prt->rt_ttl = RIPZTIME;
    					ripnotify = TRUE;
    					continue;
    				}
    #endif	/* RIP */
    				if (prev) {
        
    					prev->rt_next = prt->rt_next;
    					RTFREE(prt);
    					prt = prev->rt_next;
    				} else {
        
    					rttable[i] = prt->rt_next;
    					RTFREE(prt);
    					prt = rttable[i];
    				}
    				continue;
    			}
    			prev = prt;
    			prt = prt->rt_next;
    		}
    	}
    	prt = Route.ri_default;
    	if (prt && (prt->rt_ttl<RT_INF) && (prt->rt_ttl -= delta) <= 0) {
        
    #ifdef	RIP
    		if (dorip && prt->rt_metric < RTM_INF) {
        
    			prt->rt_metric = RTM_INF;
    			prt->rt_ttl = RIPZTIME;
    		} else
    #endif	/* RIP */
    		{
        
    			RTFREE(Route.ri_default);
    			Route.ri_default = 0;
    		}
    	}
    	signal(Route.ri_mutex);
    #ifdef	RIP
    	if (dorip && ripnotify)
    		send(rippid, 0);	/* send anything but TIMEOUT	*/
    #endif	/* RIP */
    	return;
    }

定时进程大约每秒调用一次rttimer，利用入口参数delta，提供上次调用与这次调用之间的间隔时间。在等待互斥信号量之后，rttimer循环遍历选路表。对每个表项来说，它遍历并查看各个路由链表。对正常的路由，rttimer递减寿命字段计数值，如果计数值为0，从链表中删除该节点。然而，如果网关运行RIP，则rttimer将超时路由标记为费用无穷大，这样它就无法将其作为数据报的有效路由，同时又使得这些超时路由在表中短暂的保留一段时间。最后，rttimer递减默认路由中的寿命计数值。

## 增加路由 ##

网络管理软件和选路信息协议都可调用那些用来增加、删除或重定向的函数。比如，过程rtadd向表中曾一个新路由

/* rtadd.c - rtadd */
    
    #include <conf.h>
    #include <kernel.h>
    #include <proc.h>
    #include <network.h>
    
    struct	route *rtnew(IPaddr, IPaddr, IPaddr, unsigned,unsigned,unsigned);
    void rtinit(void);
    int rthash(IPaddr);
    
    /*------------------------------------------------------------------------
     *  rtadd  -  add a route to the routing table
     *------------------------------------------------------------------------
     */
    int rtadd(IPaddr net, IPaddr mask, IPaddr gw, unsigned metric,
    	unsigned intf, unsigned ttl)
    {
        
    	struct	route	*prt, *srt, *prev;
    	Bool		isdup;
    	int		hv, i;
    
    	if (!Route.ri_valid)
    		rtinit();
    
    	prt = rtnew(net, mask, gw, metric, intf, ttl);  // rtnew分配一个新节点
    	if (prt == (struct route *)SYSERR)
    		return SYSERR;
    
    	/* compute the queue sort key for this route */
    	prt->rt_key = 0;
    	for (i=0; i<32; ++i)
    		prt->rt_key += (mask >> i) & 1;
    	wait(Route.ri_mutex);
    
    	/* special case for default routes */
    	if (net == RT_DEFAULT) {
        
    		if (Route.ri_default)
    			RTFREE(Route.ri_default);
    		Route.ri_default = prt;
    		signal(Route.ri_mutex);
    		return OK;
    	}
    	prev = NULL;
    	hv = rthash(net);
    	isdup = FALSE;
    	for (srt=rttable[hv]; srt; srt = srt->rt_next) {
        
    		if (prt->rt_key > srt->rt_key)
    			break;
    		if (srt->rt_net == prt->rt_net &&
    	    	    srt->rt_mask == prt->rt_mask) {
        
    			isdup = TRUE;
    			break;
    		}
    		prev = srt;
    	}
    	if (isdup) {
        
    		struct	route	*tmprt;
    
    		if (srt->rt_gw == prt->rt_gw) {
        
    			/* just update the existing route */
    #ifdef	RIP
    			if (dorip) {
        
    				srt->rt_ttl = ttl;
    				if (srt->rt_metric != metric) {
        
    					if (metric == RTM_INF)
    						srt->rt_ttl = RIPZTIME;
    					send(rippid, 0);
    				}
    			}
    #endif	/* RIP */
    			srt->rt_metric = metric;
    			RTFREE(prt);
    			signal(Route.ri_mutex);
    			return OK;
    		}
    		/* else, someone else has a route there... */
    		if (srt->rt_metric <= prt->rt_metric) {
        
    			/* no better off to change; drop the new one */
    
    			RTFREE(prt);
    			signal(Route.ri_mutex);
    			return OK;
    		}
    #ifdef	RIP
    		else if (dorip)
    			send(rippid, 0);
    #endif	/* RIP */
    		tmprt = srt;
    		srt = srt->rt_next;
    		RTFREE(tmprt);
    	}
    #ifdef	RIP
    	else if (dorip)
    		send(rippid, 0);
    #endif	/* RIP */
    	prt->rt_next = srt;
    	if (prev)
    		prev->rt_next = prt;
    	else
    		rttable[hv] = prt;
    	signal(Route.ri_mutex);
    	return OK;
    }

rtadd调用过程rtnew来分配一个新节点，并初始化它的各个字段。然后将默认路由当中特殊情况对待。对于非默认路由，tradd利用rthash计算新路由在路由表中的索引值，并遍历该表象中的路由链表。一旦它在链表中找到新路由应该被插入的地方，就查看链表是否包含一个具有相同目的站的已有路由。如果有，rtadd比较旧路由和新路由的度量，是否新路由更好。如果不是，就丢弃新路由。最后，rtadd或者在链表中插入一个新节点，或者将信息复制到具有同样地址的已有节点中。

过程rtnew分配并初始化一个新路由表项。它调用getbuf来为新节点分配存储器，然后填写首部信息

/* rtnew.c - rtnew */
    
    #include <conf.h>
    #include <kernel.h>
    #include <network.h>
    
    /*------------------------------------------------------------------------
     *  rtnew  -  create a route structure
     *------------------------------------------------------------------------
     */
    struct route * rtnew(IPaddr net, IPaddr mask, IPaddr gw, unsigned metric,
    	unsigned ifnum, unsigned ttl)
    {
        
    	struct	route *prt;
    
    	prt = (struct route *)getbuf(Route.ri_bpool);
    	if (prt == (struct route *)SYSERR) {
        
    		IpRoutingDiscards++;
    		return (struct route *)SYSERR;
    	}
    
    	prt->rt_net = net;
    	prt->rt_mask = mask;
    	prt->rt_gw = gw;
    	prt->rt_metric = metric;
    	prt->rt_ifnum = ifnum;
    	prt->rt_ttl = ttl;
    	prt->rt_refcnt = 1;	/* our caller */
    	prt->rt_usecnt = 0;
    	prt->rt_next = NULL;
    	return prt;
    }

## 删除路由 ##

过程rtdel以一个目的地址作为入口参数，并通过从选路表中移走节点并删除路由

/* rtdel.c - rtdel */
    
    #include <conf.h>
    #include <kernel.h>
    #include <network.h>
    
    /*------------------------------------------------------------------------
     *  rtdel  -  delete the route with the given net, mask
     *------------------------------------------------------------------------
     */
    int rtdel(IPaddr net, IPaddr mask)
    {
        
    	struct	route	*prt, *prev;
    	int		hv, i;
    
    	if (!Route.ri_valid)
    		return SYSERR;
    	wait(Route.ri_mutex);
    	if (Route.ri_default &&
    	    net == Route.ri_default->rt_net) {
        
    		RTFREE(Route.ri_default);
    		Route.ri_default = 0;
    		signal(Route.ri_mutex);
    		return OK;
    	}
    	hv = rthash(net);
    
    	prev = NULL;
    	for (prt = rttable[hv]; prt; prt = prt->rt_next) {
        
    		if (net == prt->rt_net &&
    		    mask == prt->rt_mask)
    			break;
    		prev = prt;
    	}
    	if (prt == NULL) {
        
    		signal(Route.ri_mutex);
    		return SYSERR;
    	}
    	if (prev)
    		prev->rt_next = prt->rt_next;
    	else
    		rttable[hv] = prt->rt_next;
    	RTFREE(prt);
    	signal(Route.ri_mutex);
    	return OK;
    }

像往常那样，程序代码查看并以特殊情况对待默认路由。如果没有找到匹配表项，rtdel计算目的地址的散列值，并在路由链表中搜索。一旦它找到正确的路由，rtdel将该节点从链表中删除，并利用宏RTFREE来递减引用计数值。如果引用计数值到达0，RTFREE就将该节点返回空闲节点表。如果引用计算值扔为正值，表示肯定还有一个或者几个进程正在使用该节点。只有当最后一个进程将引用计数值减少到0时，此节点才被释放回空闲节点表

宏RTFREE假设正在执行中的进程已经获得了单独访问选路表的权利，因此它可以在诸如rtdel之类的过程中使用。任意一个需要递减选路表中引用计算值的过程都可以调用rtfree。当rtfree被唤醒后，首先它等待互斥信号量，然后唤醒宏RTFREE，最后释放信号量

/* rtfree.c - rtfree */
    
    #include <conf.h>
    #include <kernel.h>
    #include <network.h>
    
    /*------------------------------------------------------------------------
     *  rtfree  -  remove one reference to a route
     *------------------------------------------------------------------------
     */
    int rtfree(struct route *prt)
    {
        
    	if (!Route.ri_valid)
    		return SYSERR;
    	wait(Route.ri_mutex);
    	RTFREE(prt);
    	signal(Route.ri_mutex);
    	return OK;
    }

# IP选项处理 #

IP支持一组选项，用来控制IP如何处理主机和网关中的数据报。为了使例程代码简洁易懂，我们决定忽略对选项的处理。虽然如此，我们还是在程序代码中包括了两个实例程序的框架，用于死锁IP首部中的选项。网关调用过程ipdoopts，它仅仅返回调用者，使得网关在前送数据报时，并没有对选项做任何处理

/* ipdoopts.c - ipdoopts */
    
    #include <conf.h>
    #include <kernel.h>
    #include <network.h>
    
    /*------------------------------------------------------------------------
     *  ipdoopts - do gateway handling of IP options
     *------------------------------------------------------------------------
     */
    int ipdoopts(struct netif *pni, struct ep *pep)
    {
        
    	return OK;	/* not implemented yet */
    }

主机调用过程ipdstopts来处理到达主机的数据报的选项。虽然我们在过程中并没有真正实现选项的处理，但它分析了IP首部中选项长度的八位组的信息，并将选项字段从IP首部中删除

/* ipdstopts.c - ipdstopts */
    
    #include <conf.h>
    #include <kernel.h>
    #include <network.h>
    
    /*------------------------------------------------------------------------
     *  ipdstopts - do host handling of IP options
     *------------------------------------------------------------------------
     */
    int ipdstopts(struct netif *pni, struct ep *pep)
    {
        
    	struct	ip	*pip = (struct ip *)pep->ep_data;
    	u_char		*popt, *popend;
    	int		len;
    
    	if (IP_HLEN(pip) == IPMHLEN)
    		return OK;
    	popt = pip->ip_data;
    	popend = (u_char *)&pep->ep_data[IP_HLEN(pip)];
    
    	/* NOTE: options not implemented yet */
    
    	/* delete the options */
    	len = pip->ip_len-IP_HLEN(pip);	/* data length	*/
    	if (len)
    		memcpy(pip->ip_data, &pep->ep_data[IP_HLEN(pip)], len);
    	pip->ip_len = IPMHLEN + len;
    	pip->ip_verlen = (pip->ip_verlen&0xf0) | IP_MINHLEN;
    	return OK;
    }

# 总结 #

IP选路表是一个至关重要的数据结构。当为数据报选择路由时，IP进程利用该选路表，在表中查找数据报目的站的下一跳路由。由于路由查找的频繁使用，因此选路表在其组织结构上尽量考虑提高查找的效率。同时，掌握新的路由信息的高层协议软件还要在选路表中插入、删除或更改路由

本节描述了负责选路表的查找和维护的过程。从中可以了解到选路表怎样利用桶散列结构提高效率，以及当进程正在删除选路路由时引用计数器怎样运行另一进程继续使用该路由。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20221005/0120f36c62104af59aa075e1916bd2ea.png