1 引言
讨论选择路由的细节，选路表的结构，以及实现算法，路由如何使用子网掩码，如何区分网络路由子网路由以及主机路由
2 路由维护和查找
应当选择能使查找路由花费最小的IP数据结构和算法，维护路由的花费则并不那么重要
利用桶散列（bucket hashing）迅速找到正确的散列表元
3 选路表结构
保存路由的主要数据结构是数组。数组的每个元素对应一个散列表元，并包含一个指针，指向被装入这个散列表元中的通主目的站的路由记录链表。表中每个记录包含一个IP目的地址，子网掩码，下一跳地址，用于向下一跳地址发送数据的网络接口，以及其他的路由管理中使用的信息。由于IP预先并不知道子网掩码，它公使用IP目的地址的网络部分计算散列函数，在一个链表中查找表项时，使用的是完整的目的地址来进行比较。
4 选路表数据结构
/* route.h – RTFREE */
/* 路由表项 */
struct route {
IPaddr rt_net; /* 路由的目的地址 */
IPaddr rt_mask; /* 路由的掩码 */
IPaddr rt_gw; /* 下一跳的IP */
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; /* 结点的地址??? Route.ri_bpool = mkpool(sizeof(struct route), RT_BPSIZE) 现在还不太明白 */
Bool ri_valid; /* 此路由的数据结构是否被初始化 */
int ri_mutex; /* 互斥信号 */
};
#define RT_DEFAULT ip_anyaddr /* 默认的网络地址 全0 */
#define RT_LOOPBACK ip_loopback /* 回环地址 */
#define RT_TSIZE 512 /* 散列表长度??-these are pointers; it’s cheap */
#define RT_INF 999 /* 路由永不超时 */
#define RTM_INF 16 /* 一个最大距离度量 – an infinite metric */
/* rtget（）的第二个参数… */
#define RTF_REMOTE 0 /* 远程主机产生的通信 */
#define RTF_LOCAL 1 /* 本地产生的通信 */
#define RT_BPSIZE 100 /* 路由的最大数量 */
/* RTFREE – 删除一个路由引用（假定持有ri_mutex） */
#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 *);
5 路由的生成源及保持时间
选路表项的易失性与它的来源有关(从备份存储器中得到,ICMP或选路协议,网络管理员手动操作),但为了排除网络中的路由问题,管理员可以推翻任何路由并建立不可改变的永久的路由
6 为数据报选择路由
6.1 实用过程
/* netnum.c - netnum */
#include
#include
#include
/*————————————————————————
* netnum – 计算一个给定IP 地址的网络部分
*————————————————————————
*/
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; /* 返回一个主机地址字节为全0的地址*/
}
/* netmatch.c – netmatch */
#include
#include
#include
/*————————————————————————
* netmatch – 是否是这个网络上的地址?
*————————————————————————
*/
Bool
netmatch(IPaddr dst, IPaddr net, IPaddr mask, Bool islocal)
{
if ((dst & mask) != (net & mask)) /* 目的地址与选路表中地址比较*/
return FALSE;
/*
* 源地址为本地可以只匹配单播地址 (主机为路由)
*/
if (islocal) /* 如果是本地*/
if (isbrc(dst) || IP_CLASSD(dst)) /* 如果目的地址不是广播地址,或不是D类*/
return mask != ip_maskall; /* 并且掩码不为全1,则返回真,否则为假*/
return TRUE;
}
/* netmask.c – netmask */
#include
#include
#include
IPaddr netnum(IPaddr);
/*————————————————————————
* netmask – 为给定网络设定默认掩码
*————————————————————————
*/
IPaddr
netmask(IPaddr net)
{
IPaddr netpart;
int i;
if (net == 0) /* 目的地址为全0,则使用默认路由,返回全0掩码*/
return net;
/* 网络匹配检查 (子网) */
netpart = netnum(net); /* 提取出网络部分*/
for (i=0; i
#include
#include
/*————————————————————————
* rthash – 计算网络的哈希值
*————————————————————————
*/
int
rthash(IPaddr net)
{
int bc = IP_ALEN; /* # 字节数 */
unsigned int hv = 0; /* 哈希值 */
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; /* D类前4比特乘16再与散列表长度取余数*/
while (bc–)
hv += ((char *)&net)[bc] & 0xff; /* 每8位相加*/
return hv % RT_TSIZE; /* 返回除以散列长度后的余数*/
}
6.2 获得一个路由
/* rtget.c – rtget */
#include
#include
#include
/*————————————————————————
* rtget – 获得一个给定的IP地址的路由
*————————————————————————
*/
struct route *
rtget(IPaddr dest, Bool local)
{
struct route *prt;
int hv;
if (!Route.ri_valid) /* 如果路由的数据结构没被初始化则应该先初始化*/
rtinit();
wait(Route.ri_mutex); /* 等待信号互斥量*/
hv = rthash(dest); /* 计算哈希值*/
for (prt=rttable[hv]; prt; prt=prt->rt_next) {
if (prt->rt_ttl <= 0)
continue; /* 路由过期 */
if (netmatch(dest, prt->rt_net, prt->rt_mask, local)) /* 如果网络地址匹配*/
if (prt->rt_metric < RTM_INF) /* 并且距离量度小于最大的量度*/
break; /* 则退出for循环*/
}
if (prt == 0) /* 如果没有找到匹配的网络地址*/
prt = Route.ri_default; /* 使用默认路由 */
if (prt != 0 && prt->rt_metric >= RTM_INF) /*如果找到匹配且路离量度大于最大的量度*/
prt = 0; /* prt指向0*/
if (prt) {
prt->rt_refcnt++; /* 引用计数加1*/
prt->rt_usecnt++; /* 统计计数加1*/
}
signal(Route.ri_mutex); /* 释放互斥量*/
return prt;
}
6.3 数据结构初始化
/* rtinit.c – rtinit */
#include
#include
#include
#include
struct rtinfo Route;
struct route *rttable[RT_TSIZE];
/*————————————————————————
* rtinit – 初始化路由表
*————————————————————————
*/
void
rtinit(void)
{
int i;
for (i=0; i
#include
#include
extern Bool dorip; /* TRUE 如果我们正在运行的RIP输出 */
extern int rippid; /* 输出的RIP的pid，如果运行 */
/*————————————————————————
* rttimer – 更新TTLS及删除过期路由
*————————————————————————
*/
void
rttimer(unsigned int delta)
{
struct route *prt, *prev;
Bool ripnotify;
int i;
if (!Route.ri_valid) /* 路由未被初始化则返回*/
return;
wait(Route.ri_mutex); /* 等待互斥量*/
ripnotify = FALSE; /* RIP通知关闭*/
for (i=0; i
prt->rt_ttl -= delta; /* 生存时间减去相应的时间*/
if (prt->rt_ttl <= 0) { /* 如果生存时间小于等于0*/
#ifdef RIP /* 条件编译,当打开RIP时*/
if (dorip && prt->rt_metric < RTM_INF) { /*RIP打开且距离小于最大距离*/
prt->rt_metric = RTM_INF; /* 设置距离为最大距离*/
prt->rt_ttl = RIPZTIME; /* 生存时间为无穷*/
ripnotify = TRUE; /* 打开RIP通知*/
continue;
}
#endif /* RIP */
if (prev) { /*如果prev不为空,删除prt指向的表项*/
prev->rt_next = prt->rt_next;
RTFREE(prt);
prt = prev->rt_next;
} else { /*否则说明prt就是第一个表项*/
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
prt->rt_ttl = RIPZTIME; /* 生存时间为无穷*/
} else
#endif /* RIP */
{
RTFREE(Route.ri_default); /* 释放默认路由 */
Route.ri_default = 0; /* 清除默认路由指针*/
}
}
signal(Route.ri_mutex); /* 释放互斥量*/
#ifdef RIP
if (dorip && ripnotify) /* RIP打开并且RIP通知打开*/
send(rippid, 0); /* 发送任何东西，但超时 */
#endif /* RIP */
return;
}
7.1 增加路由
/* rtadd.c – rtadd */
#include
#include
#include
struct route *rtnew(IPaddr, IPaddr, IPaddr, unsigned,unsigned,unsigned);
void rtinit(void);
int rthash(IPaddr);
/*————————————————————————
* rtadd – 添加一个路由到路由表
*————————————————————————
*/
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); /* 建立新的结点*/
if (prt == (struct route *)SYSERR) /* 分配失败则返回错误*/
return SYSERR;
/* 计算，路由在队列中的键 */
prt->rt_key = 0;
for (i=0; i<32; ++i)
prt->rt_key += (mask >> i) & 1;
wait(Route.ri_mutex); /* 等待互斥量*/
/* 默认路由的特殊情况 */
if (net == RT_DEFAULT) { /* 如果网络地址为任意,全0*/
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) { /*srt 为空则退出for*/
if (prt->rt_key > srt->rt_key) /* */
break;
if (srt->rt_net == prt->rt_net && /* 网络地址和掩码均相同,找到相同的地址的路由*/
srt->rt_mask == prt->rt_mask) {
isdup = TRUE; /* isdup为真*/
break;
}
prev = srt;
}
if (isdup) { /* isdup为真,说明有相同的路由表项*/
struct route *tmprt;
if (srt->rt_gw == prt->rt_gw) { /* 源路由表与新路由表的下一跳相同 */
/* 更新新由表 */
#ifdef RIP /* 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); /* 释放prt*/
signal(Route.ri_mutex); /* 释放互斥量*/
return OK;
}
/* else, someone else has a route there… */
if (srt->rt_metric <= prt->rt_metric) { /* 源路由比新路由具有更小的距离并且下一跳地址不同*/
/* 没有更好的路由线路,放弃新的路由 */
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;
}
建立新的结点,很简单不多说了
/* rtnew.c – rtnew */
#include
#include
#include
/*————————————————————————
* rtnew – 创建一个路由结构
*————————————————————————
*/
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;
}
7.2 删除路由
/* rtdel.c – rtdel */
#include
#include
#include
/*————————————————————————
* rtdel – 删除给定网络的路由和掩码
*————————————————————————
*/
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参数与之相同,则删除默认路由*/
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不为空,说明匹配的路由在链表中间,并删除结点*/
prev->rt_next = prt->rt_next;
else /* 路由在链表开头*/
rttable[hv] = prt->rt_next;
RTFREE(prt); /* 释放结点*/
signal(Route.ri_mutex); /* 释放互斥量*/
return OK;
}
释放结点用的,没什么可说的,就是使用互斥量,调用一个宏
/* rtfree.c – rtfree */
#include
#include
#include
/*————————————————————————
* 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;
}
8. IP选项处理
没做什么工做,只是分析了一下IP首部中选面长度八位组的信息
/* ipdoopts.c – ipdoopts */
#include
#include
#include
/*————————————————————————
* ipdoopts – do gateway handling of IP options
*————————————————————————
*/
int
ipdoopts(struct netif *pni, struct ep *pep)
{
return OK; /* not implemented yet */
}
/* ipdstopts.c – ipdstopts */
#include
#include
#include
/*————————————————————————
* 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;
}
问题:rtdel调用rtfree而不是使用宏 RTFREE,结果会怎么样? 会发生死锁
