动态源路由(DSR)协议代码分析

动态源路由(DSR)协议代码分析

大三《网络协议栈分析与设计》课程作业,小组合作完成,由我完成了3.2路由发现部分。

源代码地址

基本原理

DSR协议简介

  DSR协议(Dynamic Source Routing),即动态源路由协议,是在多跳Ad Hoc无线网络上面使用的,一种简洁而高效的路由协议。而且该协议也是一种经典的按需路由协议,换言之,只有当一个节点需要发送数据包时,才会进行“路由发现”和“路由维护”过程。

DSR协议组成

  DSR协议主要由“路由发现”及“路由维护”两部分组成,允许节点能够发现及维护到自组织网络中的任意节点。
  DSR路由协议的所有状态都是“软状态”,即任何节点的加入或者离开对整个网络的影响都非常小,任何状态的丢失都不会影响DSR路由协议的正确操作,所有状态在丢失之后能够很容易迅速恢复。

路由发现

  当某些节点产生了一个新的数据包,想要发送给目的节点时,源节点会将源路由放在数据包的头部,给出该数据包到目的节点所遵循的有序跳数。
  通常情况下,发送方会从自己的路由缓存中获得一个合适的源路由;如果没有在缓存中找到路由,它就会启动路由发现协议动态地找到一个到达目的节点的新路由。
  具体过程如下:

  • 路由请求:源节点向邻居节点广播路由请求(RREQ),请求到达目的节点的路由;
  • 路由记录:记录从源节点到目的节点中的中间节点请求ID,中间节点接收RREQ后,将自己的地址附在路由记录中,由addrs[0]数据维护源路由路径;
  • 中间节点处理:中间节点维护序列对列表:<源节点地址,请求ID>;
  • 重复RREQ检测:如果检测到重复的RREQ,则中间节点丢弃该消息;
  • 路由应答:目的节点收到RREQ后,给源节点返回路由应答(RREP)信息,拷贝RREQ消息中的路由记录并反向存入addrs[]数组,源节点收到RREP后,在本地路由缓存中缓存路由信息。

路由维护

  • 路由维护会在以下情况下启动:

    1. 当源节点向目的节点发送数据时,需要对当前路由的可用情况进行监控
    2. 当网络拓扑变化导致路由故障时,切换到另一条路由或者重新发起路由发现过程
  • 通过逐跳验证机制来判断路由错误信息,从而删除失效的路由:

    1. 如果数据分组被重发了最大次数仍然没有收到下一跳的确认,则节点向源端发送路由错误信息,并指明中断的链路,源端将该路由从路由缓存中删除
    2. 如果源端路由缓存中存在另一条到目的节点的路由,则使用该路由重发分组,否则重新开始路由发现过程。

数据结构

DSR选项头

  在dsr-opt.h文件中定义了DSR选项头的信息:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct dsr_opt_hdr {
u_int8_t nh;
#if defined(__LITTLE_ENDIAN_BITFIELD)

u_int8_t res:7;
u_int8_t f:1;
#elif defined (__BIG_ENDIAN_BITFIELD)
u_int8_t f:1;
u_int8_t res:7;
#else
#error "Please fix <asm/byteorder.h>"
#endif
u_int16_t p_len; /* payload length */
#ifdef NS2
static int offset_;

inline static int &offset() {
return offset_;
}
inline static dsr_opt_hdr *access(const Packet * p) {
return (dsr_opt_hdr *) p->access(offset_);
}

int size() {
return ntohs(p_len) + sizeof(struct dsr_opt_hdr);
}
#endif /* NS2 */
struct dsr_opt option[0];
};
  • 第2行 u_int8_t nh;:Next Header,下一个头部,与IP首部中的协议字段取值相同
  • 第5行 u_int8_t res:7;:Reserved,保留位,占7位,置为0
  • 第6行u_int8_t f:1;:Flag,标志位,占1位,在DSR流状态首部中置为1
  • 第13行u_int16_t p_len;:Payload Length,负载长度,所有DSR选项的总长度
  • 第28行struct dsr_opt option[0];:Option,DSR选项,以type-length-value的形式编码,记录不同DSR选项的控制信息

DSR路由请求选项

  当进行路由发现时,发起端需要把路由请求选项添加到DSR选项首部。
  在dsr-rreq.h中定义了路由请求选项:

1
2
3
4
5
6
7
struct dsr_rreq_opt {
u_int8_t type;
u_int8_t length;
u_int16_t id;
u_int32_t target;
u_int32_t addrs[0];
};
  • 第2行u_int8_t type;:选项类型
  • 第3行u_int8_t length;:选项长度
  • 第4行u_int16_t id;:路由ID号,是发起路由请求时源节点产生的ID号,且每发起一次新的路由请求就会产生一个新的id号,而且id号都是唯一的。如果节点在路由缓存中检测到相同的id号,那么它将直接丢弃这个数据包,防止多次转发;如果没有发现相同的id,则转发该数据包并把ID记录到缓存中的路由请求表中
  • 第5行u_int32_ target;:目的地址,路由请求想要到达的目标节点的地址
  • 第6行u_int32_t addrs[0];:记录路由信息,当数据报到达第i个节点时,会在数组的第i项addrs[i]中记录对应的路由信息。

DSR路由回复选项

  当路由发现发现目的节点之后,需要发送路由回复选项用于告诉路由请求的发起者到达目的节点的路由。
  在dsr-rrep.h中定义了路由回复选项:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct dsr_rrep_opt {
u_int8_t type;
u_int8_t length;
#if defined(__LITTLE_ENDIAN_BITFIELD)
u_int8_t res:7;
u_int8_t l:1;
#elif defined (__BIG_ENDIAN_BITFIELD)
u_int8_t l:1;
u_int8_t res:7;
#else
#error "Please fix <asm/byteorder.h>"
#endif
u_int32_t addrs[0];
};
  • 第5行u_int8_t res:7;:Reserved,保留位,占7位,置为0
  • 第6行u_int8_t l:1;:Last Hop External,置0表示最后一跳节点在DSR网络内部,置1表示最后一跳在DSR外部。在选取路由时应当遵循以下原则:尽量选取仅利用本网络内部节点就可以到达目的节点的路由,而不经过外部网络。即在路由缓存中优先选择l标志位置0的路由。
  • 第13行u_int32_t addrs[0];:记录路由回复信息,从源节点到目标节点顺序排列

DSR路由错误选项

  路由错误选项用于通知路由的错误。
  在dsr-rerr.h中定义了路由错误选项:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct dsr_rerr_opt {
u_int8_t type;
u_int8_t length;
u_int8_t err_type;
#if defined(__LITTLE_ENDIAN_BITFIELD)
u_int8_t res:4;
u_int8_t salv:4;
#elif defined (__BIG_ENDIAN_BITFIELD)
u_int8_t res:4;
u_int8_t salv:4;
#else
#error "Please fix <asm/byteorder.h>"
#endif
u_int32_t err_src;
u_int32_t err_dst;
char info[0];
};
  • 第4行u_int8_t err_type;:Error Type,错误类型
  • 第6行u_int8_t res:4;:Reserved,保留位,占4位,置为0
  • 第7行u_int8_t salv:4;:Salvage,占4位,表示该数据包重新发送的次数,根据这个数值来决定该数据包是否应该被丢弃
  • 第14行u_int32_t err_src;:Error Source,路由错误的源地址
  • 第15行u_int32_t err_dst;:Error Destination,路由错误的目的地址
  • 第16行char info[0];:Information,记录路由错误信息

DSR路由维护选项

  路由维护选项,也称作源路由选项。当一个节点想到达某一目的节点时,会从路由缓存中取得路由,并将源路由选项加入DSR选项头,具体存入数组addrs[]中,利用其中的路由信息到达目的节点。
  在dsr-srt.h中定义了路由维护选项:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct dsr_srt_opt {
u_int8_t type;
u_int8_t length;
#if defined(__LITTLE_ENDIAN_BITFIELD)
/* TODO: Fix bit/byte order */
u_int16_t f:1;
u_int16_t l:1;
u_int16_t res:4;
u_int16_t salv:4;
u_int16_t sleft:6;
#elif defined (__BIG_ENDIAN_BITFIELD)
u_int16_t f:1;
u_int16_t l:1;
u_int16_t res:4;
u_int16_t salv:4;
u_int16_t sleft:6;
#else
#error "Please fix <asm/byteorder.h>"
#endif
u_int32_t addrs[0];
};
  • 第6行u_int16_t f:1;:First Hop External,置0表示第一跳节点在DSR网络内部,置1表示第一跳在DSR外部。
  • 第7行u_int16_t l:1;:Last Hop External,置0表示最后一跳节点在DSR网络内部,置1表示最后一跳在DSR外部。
  • 第10行u_int16_t sleft:6;:Segments Left,路由剩余的跳数
  • 第20行u_int32_t addrs[0];:维护的源路由路径

DSR数据包

  在dsr-pkt.h中定义了DSR协议中数据包的结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
struct dsr_pkt {
struct in_addr src; /* IP level data */
struct in_addr dst;
struct in_addr nxt_hop;
struct in_addr prv_hop;
int flags;
int salvage;
#ifdef NS2
union {
struct hdr_mac *ethh;
unsigned char *raw;
} mac;
struct hdr_ip ip_data;
union {
struct hdr_ip *iph;
char *raw;
} nh;
#else
union {
struct ethhdr *ethh;
char *raw;
} mac;
union {
struct iphdr *iph;
char *raw;
} nh;
char ip_data[60];
#endif
struct {
union {
struct dsr_opt_hdr *opth;
char *raw;
};
char *tail, *end;
} dh;

int num_rrep_opts, num_rerr_opts, num_rreq_opts, num_ack_opts;
struct dsr_srt_opt *srt_opt;
struct dsr_rreq_opt *rreq_opt; /* Can only be one */
struct dsr_rrep_opt *rrep_opt[MAX_RREP_OPTS];
struct dsr_rerr_opt *rerr_opt[MAX_RERR_OPTS];
struct dsr_ack_opt *ack_opt[MAX_ACK_OPTS];
struct dsr_ack_req_opt *ack_req_opt;
struct dsr_srt *srt; /* Source route */

int payload_len;
#ifdef NS2
AppData *payload;
Packet *p;
#else
char *payload;
struct sk_buff *skb;
#endif

};
  • 第2行struct in_addr src;:Source,源端IP地址

  • 第3行struct in_addr dst;:Destination,目的端IP地址

  • 第4行struct in_addr nxt_hop;:Next Hop,下一跳IP地址

  • 第5行struct in_addr prv_hop;:Previous Hop,上一跳IP地址

  • 第9-12行union{}mac;:指向以太网帧首部,联合体使我们可以以结构体的方式访问以太网帧首部,或者直接读取以太网帧首部的数据

  • 第13行struct hdr_ip ip_data;:IP数据报中的数据

  • 第14-17行union{}nh;:指向IP首部,联合体使我们可以以结构体的方式访问IP首部,或者直接读取IP首部的数据

  • 第29-35行struct{}dh;:指向DSR首部,联合体使我们可以以结构体的方式访问DSR首部,或者直接读取DSR首部的数据

  • 第46行int payload_len;:负载长度

  • 第52行char *payload;:负载

  • 第53行struct sk_buff *skb;:分片结构体。其中struct sk_buff是Linux网络系统中的核心结构体,所有数据包的封装及解封都是在这个结构体的基础上进行的

    源路由结构

      源路由是指发送的数据包沿途经过的节点,也就是路由的路径。
      在dsr-srt.h 中定义了源路由的结构

    1
    2
    3
    4
    5
    6
    7
    8
    struct dsr_srt {
    struct in_addr src;
    struct in_addr dst;
    unsigned short flags;
    unsigned short index;
    unsigned int laddrs; /* length in bytes if addrs */
    struct in_addr addrs[0]; /* Intermediate nodes */
    };
  • 第6行unsigned int laddrs;:Length of Address,地址总长度

  • 第7行struct in_addr addrs[0];:存放中间经过的节点

路由请求表

  在dsr-rreq.c中定义了路由请求表的结构。

1
2
3
4
5
6
7
8
9
10
11
12
struct rreq_tbl_entry {
list_t l;
int state;
struct in_addr node_addr;
int ttl;
DSRUUTimer *timer;
struct timeval tx_time;
struct timeval last_used;
usecs_t timeout;
unsigned int num_rexmts;
struct tbl rreq_id_tbl;
};
  • 第3行int state;:表示路由请求的状态
  • 第4行struct in_addr node_addr;:路由请求的目的地址
  • 第8行struct timeval last_used;:从上次被使用,到现在的时间间隔

函数分析

流程图

流程图

路由发现

生成数据包

  在dsr-pkt.c中实现了生成数据包的功能:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
struct dsr_pkt *dsr_pkt_alloc(struct sk_buff *skb)
{
struct dsr_pkt *dp;
int dsr_opts_len = 0;

dp = (struct dsr_pkt *)MALLOC(sizeof(struct dsr_pkt), GFP_ATOMIC);

if (!dp)
return NULL;

memset(dp, 0, sizeof(struct dsr_pkt));

if (skb) {
/* skb_unlink(skb); */

dp->skb = skb;

dp->mac.raw = skb->mac.raw;
dp->nh.iph = skb->nh.iph;

dp->src.s_addr = skb->nh.iph->saddr;
dp->dst.s_addr = skb->nh.iph->daddr;

if (dp->nh.iph->protocol == IPPROTO_DSR) {
struct dsr_opt_hdr *opth;
int n;

opth = (struct dsr_opt_hdr *)(dp->nh.raw + (dp->nh.iph->ihl << 2));
dsr_opts_len = ntohs(opth->p_len) + DSR_OPT_HDR_LEN;

if (!dsr_pkt_alloc_opts(dp, dsr_opts_len)) {
FREE(dp);
return NULL;
}

memcpy(dp->dh.raw, (char *)opth, dsr_opts_len);

n = dsr_opt_parse(dp);

DEBUG("Packet has %d DSR option(s)\n", n);
}

dp->payload = dp->nh.raw +
(dp->nh.iph->ihl << 2) + dsr_opts_len;

dp->payload_len = ntohs(dp->nh.iph->tot_len) -
(dp->nh.iph->ihl << 2) - dsr_opts_len;

if (dp->payload_len)
dp->flags |= PKT_REQUEST_ACK;
}
return dp;
}

  • 第6-11行,先为数据包申请需要的内存空间,然后将内容全部置零
  • 第13-51行,如果传入的skb指针不为空,则数据包会根据skb所指向的内容进行初始化
  • 第52行,函数返回指向这个数据包的指针

为DSR选项首部分配内存

  在dsr-opt.c中实现了生成选项首部的功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct dsr_opt_hdr *dsr_opt_hdr_add(char *buf, unsigned int len, 
unsigned int protocol)
{
struct dsr_opt_hdr *opt_hdr;

if (len < DSR_OPT_HDR_LEN)
return NULL;

opt_hdr = (struct dsr_opt_hdr *)buf;

opt_hdr->nh = protocol;
opt_hdr->f = 0;
opt_hdr->res = 0;
opt_hdr->p_len = htons(len - DSR_OPT_HDR_LEN);

return opt_hdr;
}
  • 第5-6行,判断缓冲区的长度能否放下DSR选项首部,若不能,则返回空指针
  • 第8-13行,对选项首部信息进行初始化操作
  • 第15行,函数返回指向这个首部的指针

DSR协议处理数据包

  每个节点都需要与其他节点进行数据包的交互,这就涉及到了对于接收和发送数据包的处理,这两部分功能的实现定义在了dsr-io.c

接收数据包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
int NSCLASS dsr_recv(struct dsr_pkt *dp)
{
int i = 0, action;
int mask = DSR_PKT_NONE;

/* Process DSR Options */
action = dsr_opt_recv(dp);

/* Add mac address of previous hop to the neighbor table */

if (dp->flags & PKT_PROMISC_RECV) {
dsr_pkt_free(dp);
return 0;
}
for (i = 0; i < DSR_PKT_ACTION_LAST; i++) {

switch (action & mask) {
case DSR_PKT_NONE:
break;
case DSR_PKT_DROP:
case DSR_PKT_ERROR:
DEBUG("DSR_PKT_DROP or DSR_PKT_ERROR\n");
dsr_pkt_free(dp);
return 0;
case DSR_PKT_SEND_ACK:
/* Moved to dsr-ack.c */
break;
case DSR_PKT_SRT_REMOVE:
//DEBUG("Remove source route\n");
// Hmm, we remove the DSR options when we deliver a
//packet
//dsr_opt_remove(dp);
break;
case DSR_PKT_FORWARD:

#ifdef NS2
if (dp->nh.iph->ttl() < 1)
#else
if (dp->nh.iph->ttl < 1)
#endif
{
DEBUG("ttl=0, dropping!\n");
dsr_pkt_free(dp);
return 0;
} else {
DEBUG("Forwarding %s %s nh %s\n",
print_ip(dp->src),
print_ip(dp->dst), print_ip(dp->nxt_hop));
XMIT(dp);
return 0;
}
break;
case DSR_PKT_FORWARD_RREQ:
XMIT(dp);
return 0;
case DSR_PKT_SEND_RREP:
/* In dsr-rrep.c */
break;
case DSR_PKT_SEND_ICMP:
DEBUG("Send ICMP\n");
break;
case DSR_PKT_SEND_BUFFERED:
if (dp->rrep_opt) {
struct in_addr rrep_srt_dst;
int i;

for (i = 0; i < dp->num_rrep_opts; i++) {
rrep_srt_dst.s_addr = dp->rrep_opt[i]->addrs[DSR_RREP_ADDRS_LEN(dp->rrep_opt[i]) / sizeof(struct in_addr)];

send_buf_set_verdict(SEND_BUF_SEND, rrep_srt_dst);
}
}
break;
case DSR_PKT_DELIVER:
DEBUG("Deliver to DSR device\n");
DELIVER(dp);
return 0;
case 0:
break;
default:
DEBUG("Unknown pkt action\n");
}
mask = (mask << 1);
}

dsr_pkt_free(dp);

return 0;
}
  • 第18-24行,根据选项中的信息,如果数据包是空、丢失、错误,则返回错误信息,并释放该数据包的空间
  • 第34-52行,如果是转发的数据包,我们会对数据包的TTL进行判断:如果TTL为0,需要输出信息,并且释放掉该数据包的空间,不再进行转发操作;否则,我们输出其源IP地址、目的IP地址及下一跳IP地址,并执行XMIT()操作(后文介绍),传输数据包。
  • 第86行,如果都不满足的话,就说明这个数据包的选项信息是未知的,我们只需要释放掉这个数据包即可

发送数据包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void NSCLASS dsr_start_xmit(struct dsr_pkt *dp)
{
int res;

if (!dp) {
DEBUG("Could not allocate DSR packet\n");
return;
}

dp->srt = dsr_rtc_find(dp->src, dp->dst);

if (dp->srt) {

if (dsr_srt_add(dp) < 0) {
DEBUG("Could not add source route\n");
goto out;
}
/* Send packet */

XMIT(dp);

return;

} else {
#ifdef NS2
res = send_buf_enqueue_packet(dp, &DSRUU::ns_xmit);
#else
res = send_buf_enqueue_packet(dp, &dsr_dev_xmit);
#endif
if (res < 0) {
DEBUG("Queueing failed!\n");
goto out;
}
res = dsr_rreq_route_discovery(dp->dst);

if (res < 0)
DEBUG("RREQ Transmission failed...");

return;
}
out:
dsr_pkt_free(dp);
}
  • 第10行,执行dsr_rtc_find()功能,根据数据包来寻找是否存在到达目的节点的源路由
  • 第12-22行,如果有,则在添加源路由成功的条件下,执行XMIT()操作(后文介绍),发送数据包
  • 第24-40行,如果没有,则将这个数据包添加到发送队列中,并去进行路由发现

DSR处理源路由请求

  在知道路由路径的情况下,就需要将数据包发送到目标地址,我们先看一下如何处理源路由选项。
  在dsr-srt.c中实现了对源路由选项的处理功能。

添加源路由选项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct dsr_srt_opt *dsr_srt_opt_add(char *buf, int len, int flags, 
int salvage, struct dsr_srt *srt)
{
struct dsr_srt_opt *srt_opt;

if (len < (int)DSR_SRT_OPT_LEN(srt))
return NULL;

srt_opt = (struct dsr_srt_opt *)buf;

srt_opt->type = DSR_OPT_SRT;
srt_opt->length = srt->laddrs + 2;
srt_opt->f = (flags & SRT_FIRST_HOP_EXT) ? 1 : 0;
srt_opt->l = (flags & SRT_LAST_HOP_EXT) ? 1 : 0;
srt_opt->res = 0;
srt_opt->salv = salvage;
srt_opt->sleft = (srt->laddrs / sizeof(struct in_addr));

memcpy(srt_opt->addrs, srt->addrs, srt->laddrs);

return srt_opt;
}
  • 第6-7行,判断缓冲区的空间是否足够添加该选项
  • 第9-17行,若足够,则为该选项在内存中分配空间,然后初始化相关属性,包括:类型、长度等
  • 第19行,复制地址列表
  • 第21行,返回指向该选型的指针

路由缩减

  路由缩减,即缩短路由路径,当节点监听到一个数据包,但该数据包的下一跳不是它自己时,节点就会在这个数据包的剩余源路由中搜索是否有自身的IP地址,若存在,则意味着路由可以缩减。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
int NSCLASS dsr_srt_opt_recv(struct dsr_pkt *dp, struct dsr_srt_opt *srt_opt)
{
struct in_addr next_hop_intended;
struct in_addr myaddr = my_addr();
int n;

if (!dp || !srt_opt)
return DSR_PKT_ERROR;

dp->srt_opt = srt_opt;

/* Automatic route shortening - Check if this node is the
* intended next hop. If not, is it part of the remaining
* source route? */
if (next_hop_intended.s_addr != myaddr.s_addr &&
dsr_srt_find_addr(dp->srt, myaddr, srt_opt->sleft) &&
!grat_rrep_tbl_find(dp->src, dp->prv_hop)) {
struct dsr_srt *srt, *srt_cut;

/* Send Grat RREP */
DEBUG("Send Gratuitous RREP to %s\n", print_ip(dp->src));

srt_cut = dsr_srt_shortcut(dp->srt, dp->prv_hop, myaddr);

if (!srt_cut)
return DSR_PKT_DROP;

DEBUG("shortcut: %s\n", print_srt(srt_cut));

/* srt = dsr_rtc_find(myaddr, dp->src); */
if (srt_cut->laddrs / sizeof(struct in_addr) == 0)
srt = dsr_srt_new_rev(srt_cut);
else
srt = dsr_srt_new_split_rev(srt_cut, myaddr);

if (!srt) {
DEBUG("No route to %s\n", print_ip(dp->src));
FREE(srt_cut);
return DSR_PKT_DROP;
}
DEBUG("my srt: %s\n", print_srt(srt));

grat_rrep_tbl_add(dp->src, dp->prv_hop);

dsr_rrep_send(srt, srt_cut);

FREE(srt_cut);
FREE(srt);
}

if (dp->flags & PKT_PROMISC_RECV)
return DSR_PKT_DROP;

if (srt_opt->sleft == 0)
return DSR_PKT_SRT_REMOVE;

if (srt_opt->sleft > n) {
// Send ICMP parameter error
return DSR_PKT_SEND_ICMP;
}

srt_opt->sleft--;

/* TODO: check for multicast address in next hop or dst */
/* TODO: check MTU and compare to pkt size */

return DSR_PKT_FORWARD;
}
  • 第15-17行,对路由缩减的条件进行判断:如果下一跳的地址不是当前地址,且源路由中存在当前地址且其不在缩减列表中,则可以进行路由缩减。
  • 第43-45行,在路由缩减列表中添加本次路由,并且发送一个路由回复用于通知新的路由变更。
  • 第67行,如果不能进行路由缩减,则转发数据包。

生成路由请求

路由发现请求

  当一个节点不知道应该如何到达目的节点时,就会采用路由发现来寻找路由。在dsr-rreq.c中得以实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
int NSCLASS dsr_rreq_route_discovery(struct in_addr target)
{
struct rreq_tbl_entry *e;
int ttl, res = 0;
struct timeval expires;

#define TTL_START 1

DSR_WRITE_LOCK(&rreq_tbl.lock);

e = (struct rreq_tbl_entry *)__tbl_find(&rreq_tbl, &target, crit_addr);

if (!e)
e = __rreq_tbl_add(target);
else {
/* Put it last in the table */
__tbl_detach(&rreq_tbl, &e->l);
__tbl_add_tail(&rreq_tbl, &e->l);
}

if (!e) {
res = -ENOMEM;
goto out;
}

if (e->state == STATE_IN_ROUTE_DISC) {
DEBUG("Route discovery for %s already in progress\n",
print_ip(target));
goto out;
}
DEBUG("Route discovery for %s\n", print_ip(target));

gettime(&e->last_used);
e->ttl = ttl = TTL_START;
/* The draft does not actually specify how these Request Timeout values
* should be used... ??? I am just guessing here. */

if (e->ttl == 1)
e->timeout = ConfValToUsecs(NonpropRequestTimeout);
else
e->timeout = ConfValToUsecs(RequestPeriod);

e->state = STATE_IN_ROUTE_DISC;
e->num_rexmts = 0;

expires = e->last_used;
timeval_add_usecs(&expires, e->timeout);

set_timer(e->timer, &expires);

DSR_WRITE_UNLOCK(&rreq_tbl.lock);

dsr_rreq_send(target, ttl);

return 1;
out:
DSR_WRITE_UNLOCK(&rreq_tbl.lock);

return res;
}
  • 第11行,调用__tbl_find()函数(后文介绍),在路由请求表中寻找是否已经有相同目的地址的路由请求
  • 第13-19行,如果没有相同的路由请求,就调用__rreq_tbl_add()(后文介绍)把该请求添加到路由请求表中;如果有,则调用__tbl_detach()删除原先的路由请求,并调用__tbl_add_tail()把新的路由请求添加到路由请求表的末尾
  • 第38-41行,设置该路由请求选项的TTL,一旦TTL为0,则取消该路由请求
  • 第46-47行,设置失效时间expires

查询路由请求表

  在dsr-rreq.ctbl.h中,有:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef int (*criteria_t) (void *elm, void *data);
static inline int crit_addr(void *pos, void *data)
{
struct rreq_tbl_entry *e = (struct rreq_tbl_entry *)pos;
struct in_addr *a = (struct in_addr *)data;

if (e->node_addr.s_addr == a->s_addr)
return 1;
return 0;
}
static inline void *__tbl_find(struct tbl *t, void *id, criteria_t crit)
{
list_t *pos;

list_for_each(pos, &t->head) {
if (crit(pos, id))
return pos;
}
return NULL;
}
  • 第1行,criteria_t是参数为两个void类型的指针、返回值为int类型的指针
  • 第2-10行,crit_addr()函数用于判断路由请求表项的目的地址和传进来参数的地址是否匹配
  • 第11-19行,__tbl_find用于遍历整个路由请求表,寻找是否有和参数id相同的地址,若存在则返回指向匹配元素的指针,不存在则返回NULL

添加路由请求表项

  在dsr-rreq.c中得以实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
struct rreq_tbl_entry *NSCLASS __rreq_tbl_entry_create(struct in_addr node_addr)
{
struct rreq_tbl_entry *e;

e = (struct rreq_tbl_entry *)MALLOC(sizeof(struct rreq_tbl_entry),
GFP_ATOMIC);

if (!e)
return NULL;

e->state = STATE_IDLE;
e->node_addr = node_addr;
e->ttl = 0;
memset(&e->tx_time, 0, sizeof(struct timeval));;
e->num_rexmts = 0;
#ifdef NS2
e->timer = new DSRUUTimer(this, "RREQTblTimer");
#else
e->timer = MALLOC(sizeof(DSRUUTimer), GFP_ATOMIC);
#endif

if (!e->timer) {
FREE(e);
return NULL;
}

init_timer(e->timer);

e->timer->function = &NSCLASS rreq_tbl_timeout;
e->timer->data = (unsigned long)e;

INIT_TBL(&e->rreq_id_tbl, ConfVal(RequestTableIds));

return e;
}

struct rreq_tbl_entry *NSCLASS __rreq_tbl_add(struct in_addr node_addr)
{
struct rreq_tbl_entry *e;

e = __rreq_tbl_entry_create(node_addr);

if (!e)
return NULL;

if (TBL_FULL(&rreq_tbl)) {
struct rreq_tbl_entry *f;

f = (struct rreq_tbl_entry *)TBL_FIRST(&rreq_tbl);

__tbl_detach(&rreq_tbl, &f->l);

del_timer_sync(f->timer);
#ifdef NS2
delete f->timer;
#else
FREE(f->timer);
#endif
tbl_flush(&f->rreq_id_tbl, NULL);

FREE(f);
}
__tbl_add_tail(&rreq_tbl, &e->l);

return e;
}
  • 第24行,当我们调用__rreq_tbl_add()函数的时候,首先会调用__rreq_tbl_entry_create()
  • 第1-21行,给表项分配一段内存,并对表项内容进行初始化操作
  • 第26-35行,查看请求表的情况,看是否已满,若为满,则将请求表中的第一个表项删除
  • 第36行,把路由请求添加到请求表的结尾处

发送路由请求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
int NSCLASS dsr_rreq_send(struct in_addr target, int ttl)
{
struct dsr_pkt *dp;
char *buf;
int len = DSR_OPT_HDR_LEN + DSR_RREQ_HDR_LEN;

dp = dsr_pkt_alloc(NULL);

if (!dp) {
DEBUG("Could not allocate DSR packet\n");
return -1;
}
dp->dst.s_addr = DSR_BROADCAST;
dp->nxt_hop.s_addr = DSR_BROADCAST;
dp->src = my_addr();

buf = dsr_pkt_alloc_opts(dp, len);


if (!buf)
goto out_err;

dp->nh.iph =
dsr_build_ip(dp, dp->src, dp->dst, IP_HDR_LEN, IP_HDR_LEN + len,
IPPROTO_DSR, ttl);

if (!dp->nh.iph)
goto out_err;

dp->dh.opth = dsr_opt_hdr_add(buf, len, DSR_NO_NEXT_HDR_TYPE);

if (!dp->dh.opth) {
DEBUG("Could not create DSR opt header\n");
goto out_err;
}

buf += DSR_OPT_HDR_LEN;
len -= DSR_OPT_HDR_LEN;

dp->rreq_opt = dsr_rreq_opt_add(buf, len, target, ++rreq_seqno);

if (!dp->rreq_opt) {
DEBUG("Could not create RREQ opt\n");
goto out_err;
}
#ifdef NS2
DEBUG("Sending RREQ src=%s dst=%s target=%s ttl=%d iph->saddr()=%d\n",
print_ip(dp->src), print_ip(dp->dst), print_ip(target), ttl,
dp->nh.iph->saddr());
#endif

dp->flags |= PKT_XMIT_JITTER;

XMIT(dp);

return 0;

out_err:
dsr_pkt_free(dp);

return -1;
}

###发送路由请求

添加路由请求选项

  在dsr-rreq.c中得以实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static struct dsr_rreq_opt *dsr_rreq_opt_add(char *buf, unsigned int len,
struct in_addr target,
unsigned int seqno)
{
struct dsr_rreq_opt *rreq_opt;

if (!buf || len < DSR_RREQ_HDR_LEN)
return NULL;

rreq_opt = (struct dsr_rreq_opt *)buf;

rreq_opt->type = DSR_OPT_RREQ;
rreq_opt->length = 6;
rreq_opt->id = htons(seqno);
rreq_opt->target = target.s_addr;

return rreq_opt;
}
  • 与添加DSR选项首部类似,判断缓冲区空间是否足够,如果足够,就把选项指针指向缓冲区,并初始化id、长度、目的地址

发送路由请求

  在dsr-rreq.c中得以实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
int NSCLASS dsr_rreq_send(struct in_addr target, int ttl)
{
struct dsr_pkt *dp;
char *buf;
int len = DSR_OPT_HDR_LEN + DSR_RREQ_HDR_LEN;

dp = dsr_pkt_alloc(NULL);

if (!dp) {
DEBUG("Could not allocate DSR packet\n");
return -1;
}
dp->dst.s_addr = DSR_BROADCAST;
dp->nxt_hop.s_addr = DSR_BROADCAST;
dp->src = my_addr();

buf = dsr_pkt_alloc_opts(dp, len);


if (!buf)
goto out_err;

dp->nh.iph =
dsr_build_ip(dp, dp->src, dp->dst, IP_HDR_LEN, IP_HDR_LEN + len,
IPPROTO_DSR, ttl);

if (!dp->nh.iph)
goto out_err;

dp->dh.opth = dsr_opt_hdr_add(buf, len, DSR_NO_NEXT_HDR_TYPE);

if (!dp->dh.opth) {
DEBUG("Could not create DSR opt header\n");
goto out_err;
}

buf += DSR_OPT_HDR_LEN;
len -= DSR_OPT_HDR_LEN;

dp->rreq_opt = dsr_rreq_opt_add(buf, len, target, ++rreq_seqno);

if (!dp->rreq_opt) {
DEBUG("Could not create RREQ opt\n");
goto out_err;
}
#ifdef NS2
DEBUG("Sending RREQ src=%s dst=%s target=%s ttl=%d iph->saddr()=%d\n",
print_ip(dp->src), print_ip(dp->dst), print_ip(target), ttl,
dp->nh.iph->saddr());
#endif

dp->flags |= PKT_XMIT_JITTER;

XMIT(dp);

return 0;

out_err:
dsr_pkt_free(dp);

return -1;
}

  • 第7行,为该DSR数据包分配内存地址
  • 第13-15行,将数据包的目的地址、下一跳的地址均设置为广播地址,将源地址设置为自身地址
  • 第24-25行,构造数据包的IP首部,包括源地址、目的地址、协议类型和负载长度等
  • 第30行,对DSR选项首部的构造
  • 第40行,调用dsr_rreq_opt_add()函数,添加路由请求选项
  • 第54行,调用XMIT()函数(分析见后),将数据包传输出去

发送数据包

XMIT()dsr_dev_xmit()的宏定义,在dsr-dev.c中实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
int dsr_dev_xmit(struct dsr_pkt *dp)
{
struct sk_buff *skb;
struct net_device *slave_dev;
struct in_addr dst;
int res = -1;
int len = 0;

if (!dp)
return -1;

if (dp->flags & PKT_REQUEST_ACK)
maint_buf_add(dp);

dsr_node_lock(dsr_node);

if (dsr_node->slave_dev)
slave_dev = dsr_node->slave_dev;
else {
dsr_node_unlock(dsr_node);
goto out_err;
}
dsr_node_unlock(dsr_node);

skb = dsr_skb_create(dp, slave_dev);

if (!skb) {
DEBUG("Could not create skb!\n");
goto out_err;
}

/* Create hardware header */
if (dsr_hw_header_create(dp, skb) < 0) {
DEBUG("Could not create hardware header\n");
dev_kfree_skb_any(skb);
goto out_err;
}

len = skb->len;
dst.s_addr = skb->nh.iph->daddr;

DEBUG("Sending %d bytes data_len=%d %s : %s\n",
len, skb->data_len,
print_eth(skb->mac.raw),
print_ip(dst));

/* TODO: Should consider using ip_finish_output instead */
res = dev_queue_xmit(skb);

if (res < 0)
goto out_err;

dsr_node_lock(dsr_node);
dsr_node->stats.tx_packets++;
dsr_node->stats.tx_bytes += len;
dsr_node_unlock(dsr_node);

out_err:
dsr_pkt_free(dp);

return res;
}
  • 第17行,根据DSR数据包的数据创建一个sk_buff数据包
  • 第33-45行,完成MAC首部的封装
  • 第48行,调用dev_queue_xmit()将数据包发送出去
  • 第54-55行,统计发送的数据包信息
  • 第59行,如果中间某个过程产生错误,则释放该数据包的空间

接收路由请求

  当一个节点收到的数据包中包含路由发现请求时,这个节点必须通过以下步骤处理:

  • 如果路由请求的目的地址与该结点的IP地址一致,则这个节点就需要发送一个路由回复给路由请求的发起者
  • 如果路由请求的目的地址与该结点的IP地址不一致,则这个节点就需要在自己的已接收路由请求缓存中搜索是否已经发出过相同的请求。如果已经发出过,则必须丢弃该数据包防止重复转发
  • 如果没有发送过:
    1. 该几点在已接收路由请求缓存中添加这个请求
    2. 将自己的IP地址添加到路由请求选项的Addrs[]中,并更改选项中length的值
    3. 在自己的路由缓存中搜索是否有到达目的节点的路由,若有,则发送“缓存路由回复”给源地址;若没有,则以链路层广播的形式将这个修改后的数据包发送出去

  产生路由回复的功能在dsr-rreq.c中得以实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
int NSCLASS dsr_rreq_opt_recv(struct dsr_pkt *dp, struct dsr_rreq_opt *rreq_opt)
{
struct in_addr myaddr;
struct in_addr trg;
struct dsr_srt *srt_rev, *srt_rc;
int action = DSR_PKT_NONE;
int i, n;

if (!dp || !rreq_opt || dp->flags & PKT_PROMISC_RECV)
return DSR_PKT_DROP;

dp->num_rreq_opts++;

if (dp->num_rreq_opts > 1) {
DEBUG("More than one RREQ opt!!! - Ignoring\n");
return DSR_PKT_ERROR;
}

dp->rreq_opt = rreq_opt;

myaddr = my_addr();

trg.s_addr = rreq_opt->target;

if (dsr_rreq_duplicate(dp->src, trg, ntohs(rreq_opt->id))) {
DEBUG("Duplicate RREQ from %s\n", print_ip(dp->src));
return DSR_PKT_DROP;
}

rreq_tbl_add_id(dp->src, trg, ntohs(rreq_opt->id));

dp->srt = dsr_srt_new(dp->src, myaddr, DSR_RREQ_ADDRS_LEN(rreq_opt),
(char *)rreq_opt->addrs);

if (!dp->srt) {
DEBUG("Could not extract source route\n");
return DSR_PKT_ERROR;
}
DEBUG("RREQ target=%s src=%s dst=%s laddrs=%d\n",
print_ip(trg), print_ip(dp->src),
print_ip(dp->dst), DSR_RREQ_ADDRS_LEN(rreq_opt));

/* Add reversed source route */
srt_rev = dsr_srt_new_rev(dp->srt);

if (!srt_rev) {
DEBUG("Could not reverse source route\n");
return DSR_PKT_ERROR;
}
DEBUG("srt: %s\n", print_srt(dp->srt));
DEBUG("srt_rev: %s\n", print_srt(srt_rev));

dsr_rtc_add(srt_rev, ConfValToUsecs(RouteCacheTimeout), 0);

/* Set previous hop */
if (srt_rev->laddrs > 0)
dp->prv_hop = srt_rev->addrs[0];
else
dp->prv_hop = srt_rev->dst;

neigh_tbl_add(dp->prv_hop, dp->mac.ethh);

/* Send buffered packets */
send_buf_set_verdict(SEND_BUF_SEND, srt_rev->dst);

if (rreq_opt->target == myaddr.s_addr) {

DEBUG("RREQ OPT for me - Send RREP\n");

/* According to the draft, the dest addr in the IP header must
* be updated with the target address */
#ifdef NS2
dp->nh.iph->daddr() = (nsaddr_t) rreq_opt->target;
#else
dp->nh.iph->daddr = rreq_opt->target;
#endif
dsr_rrep_send(srt_rev, dp->srt);

action = DSR_PKT_NONE;
goto out;
}

n = DSR_RREQ_ADDRS_LEN(rreq_opt) / sizeof(struct in_addr);

if (dp->srt->src.s_addr == myaddr.s_addr)
return DSR_PKT_DROP;

for (i = 0; i < n; i++)
if (dp->srt->addrs[i].s_addr == myaddr.s_addr) {
action = DSR_PKT_DROP;
goto out;
}

/* TODO: Check Blacklist */
srt_rc = lc_srt_find(myaddr, trg);

if (srt_rc) {
struct dsr_srt *srt_cat;
/* Send cached route reply */

DEBUG("Send cached RREP\n");

srt_cat = dsr_srt_concatenate(dp->srt, srt_rc);

FREE(srt_rc);

if (!srt_cat) {
DEBUG("Could not concatenate\n");
goto rreq_forward;
}

DEBUG("srt_cat: %s\n", print_srt(srt_cat));

if (dsr_srt_check_duplicate(srt_cat) > 0) {
DEBUG("Duplicate address in source route!!!\n");
FREE(srt_cat);
goto rreq_forward;
}
#ifdef NS2
dp->nh.iph->daddr() = (nsaddr_t) rreq_opt->target;
#else
dp->nh.iph->daddr = rreq_opt->target;
#endif
DEBUG("Sending cached RREP to %s\n", print_ip(dp->src));
dsr_rrep_send(srt_rev, srt_cat);

action = DSR_PKT_NONE;

FREE(srt_cat);
} else {

rreq_forward:
dsr_pkt_alloc_opts_expand(dp, sizeof(struct in_addr));

if (!DSR_LAST_OPT(dp, rreq_opt)) {
char *to, *from;
to = (char *)rreq_opt + rreq_opt->length + 2 +
sizeof(struct in_addr);
from = (char *)rreq_opt + rreq_opt->length + 2;

memmove(to, from, sizeof(struct in_addr));
}
rreq_opt->addrs[n] = myaddr.s_addr;
rreq_opt->length += sizeof(struct in_addr);

dp->dh.opth->p_len = htons(ntohs(dp->dh.opth->p_len) +
sizeof(struct in_addr));
#ifdef __KERNEL__
dsr_build_ip(dp, dp->src, dp->dst, IP_HDR_LEN,
ntohs(dp->nh.iph->tot_len) +
sizeof(struct in_addr), IPPROTO_DSR,
dp->nh.iph->ttl);
#endif
/* Forward RREQ */
action = DSR_PKT_FORWARD_RREQ;
}
out:
FREE(srt_rev);
return action;
}
  • 第25-28行,判断该路由请求是否已经存在于缓存中,若存在,则丢弃该包;若不存在,则在路由请求表里面添加这个请求
  • 第44行,根据该数据包的源路由建立逆向源路由,以便发送路由回复
  • 第66-81行,如果路由请求的目的地址与该节点自身地址一致,就发送路由回复,选项为路由回复选项
  • 第95行,如果路由请求的目的地址与自身地址不同,则在该节点的路由缓冲中搜索是否有到目的节点的路由
  • 第125行,发送路由回复请求
  • 第133-153行,如果没有发现,就为DSR选项分配更多的内存,然后将自身的IP地址添加到路由请求选项中,更新IP首部信息
  • 第155行,进行转发

路由维护

处理确认请求选项

  确认请求(ACK Request)选项,DSR使用确认请求选项来判断邻居节点是否存活。当给一个邻居节点重发多次ACK请求却仍然没有收到回复的话,该节点就会认为其到邻居节点的链路已经被破坏,从而从路由缓存中删除这条路由,并且给上一次收到ACK之后在这条链路上发送过数据包的节点发送路由错误
  dsr-ack.c实现了对接收到的带确认请求选项的数据包回复ACK的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int NSCLASS dsr_ack_req_opt_recv(struct dsr_pkt *dp, struct dsr_ack_req_opt *ack_req_opt)
{
unsigned short id;

if (!ack_req_opt || !dp || dp->flags & PKT_PROMISC_RECV)
return DSR_PKT_ERROR;

dp->ack_req_opt = ack_req_opt;

id = ntohs(ack_req_opt->id);

if (!dp->srt_opt)
dp->prv_hop = dp->src;

DEBUG("src=%s prv=%s id=%u\n",
print_ip(dp->src), print_ip(dp->prv_hop), id);

dsr_ack_send(dp->prv_hop, id);

return DSR_PKT_NONE;
}

处理确认选项

  当数据包顺利送达目标节点之后,就会产生一个确认(ACK)选项,而源节点收到这个选项后,就从维护缓存中删除发送给ACK源端的数据包。
  在dsr-ack.c中实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int NSCLASS dsr_ack_opt_recv(struct dsr_ack_opt *ack)
{
unsigned short id;
struct in_addr dst, src, myaddr;
int n;

if (!ack)
return DSR_PKT_ERROR;

myaddr = my_addr();

dst.s_addr = ack->dst;
src.s_addr = ack->src;
id = ntohs(ack->id);

DEBUG("ACK dst=%s src=%s id=%u\n", print_ip(dst), print_ip(src), id);

if (dst.s_addr != myaddr.s_addr)
return DSR_PKT_ERROR;

/* Purge packets buffered for this next hop */
n = maint_buf_del_all_id(src, id);

DEBUG("Removed %d packets from maint buf\n", n);

return DSR_PKT_NONE;
}

生成路由错误选项

 &emsp当发生路由错误时,比如网络拓扑结构发生变化,数据包无法送达,节点需要生成并发送错误通知给数据包的源节点。
 &emsp在dsr-rerr.c中得以实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
int NSCLASS dsr_rerr_send(struct dsr_pkt *dp_trigg, struct in_addr unr_addr)
{
struct dsr_pkt *dp;
struct dsr_rerr_opt *rerr_opt;
struct in_addr dst, err_src, err_dst, myaddr;
char *buf;
int n, len, i;

myaddr = my_addr();

if (!dp_trigg || dp_trigg->src.s_addr == myaddr.s_addr)
return -1;

if (!dp_trigg->srt_opt) {
DEBUG("Could not find source route option\n");
return -1;
}

if (dp_trigg->srt_opt->salv == 0)
dst = dp_trigg->src;
else
dst.s_addr = dp_trigg->srt_opt->addrs[1];

dp = dsr_pkt_alloc(NULL);

if (!dp) {
DEBUG("Could not allocate DSR packet\n");
return -1;
}

dp->srt = dsr_rtc_find(myaddr, dst);

if (!dp->srt) {
DEBUG("No source route to %s\n", print_ip(dst));
return -1;
}

len = DSR_OPT_HDR_LEN + DSR_SRT_OPT_LEN(dp->srt) +
(DSR_RERR_HDR_LEN + 4) +
DSR_ACK_HDR_LEN * dp_trigg->num_ack_opts;

/* Also count in RERR opts in trigger packet */
for (i = 0; i < dp_trigg->num_rerr_opts; i++) {
if (dp_trigg->rerr_opt[i]->salv > ConfVal(MAX_SALVAGE_COUNT))
break;

len += (dp_trigg->rerr_opt[i]->length + 2);
}

DEBUG("opt_len=%d SR: %s\n", len, print_srt(dp->srt));
n = dp->srt->laddrs / sizeof(struct in_addr);
dp->src = myaddr;
dp->dst = dst;
dp->nxt_hop = dsr_srt_next_hop(dp->srt, n);

dp->nh.iph = dsr_build_ip(dp, dp->src, dp->dst, IP_HDR_LEN,
IP_HDR_LEN + len, IPPROTO_DSR, IPDEFTTL);

if (!dp->nh.iph) {
DEBUG("Could not create IP header\n");
goto out_err;
}

buf = dsr_pkt_alloc_opts(dp, len);

if (!buf)
goto out_err;

dp->dh.opth = dsr_opt_hdr_add(buf, len, DSR_NO_NEXT_HDR_TYPE);

if (!dp->dh.opth) {
DEBUG("Could not create DSR options header\n");
goto out_err;
}

buf += DSR_OPT_HDR_LEN;
len -= DSR_OPT_HDR_LEN;

dp->srt_opt = dsr_srt_opt_add(buf, len, 0, 0, dp->srt);

if (!dp->srt_opt) {
DEBUG("Could not create Source Route option header\n");
goto out_err;
}

buf += DSR_SRT_OPT_LEN(dp->srt);
len -= DSR_SRT_OPT_LEN(dp->srt);

rerr_opt = dsr_rerr_opt_add(buf, len, NODE_UNREACHABLE, dp->src,
dp->dst, unr_addr,
dp_trigg->srt_opt->salv);

if (!rerr_opt)
goto out_err;

buf += (rerr_opt->length + 2);
len -= (rerr_opt->length + 2);

/* Add old RERR options */
for (i = 0; i < dp_trigg->num_rerr_opts; i++) {

if (dp_trigg->rerr_opt[i]->salv > ConfVal(MAX_SALVAGE_COUNT))
break;

memcpy(buf, dp_trigg->rerr_opt[i],
dp_trigg->rerr_opt[i]->length + 2);

len -= (dp_trigg->rerr_opt[i]->length + 2);
buf += (dp_trigg->rerr_opt[i]->length + 2);
}

/* TODO: Must preserve order of RERR and ACK options from triggering
* packet */

/* Add old ACK options */
for (i = 0; i < dp_trigg->num_ack_opts; i++) {
memcpy(buf, dp_trigg->ack_opt[i],
dp_trigg->ack_opt[i]->length + 2);

len -= (dp_trigg->ack_opt[i]->length + 2);
buf += (dp_trigg->ack_opt[i]->length + 2);
}

err_src.s_addr = rerr_opt->err_src;
err_dst.s_addr = rerr_opt->err_dst;

DEBUG("Send RERR err_src %s err_dst %s unr_dst %s\n",
print_ip(err_src),
print_ip(err_dst),
print_ip(*((struct in_addr *)rerr_opt->info)));

XMIT(dp);

return 0;

out_err:

dsr_pkt_free(dp);

return -1;

}
  • 第24行,申请一个DSR数据包
  • 第31行,建立一条到达数据包源端的路由,以便发送错误
  • 第89-91行,添加路由错误的选项
  • 第132行,调用XMIT()函数,发送数据包

处理路由错误选项

 &emsp在dsr-rerr.c中实现了处理路由错误选项的功能:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int NSCLASS dsr_rerr_opt_recv(struct dsr_pkt *dp, struct dsr_rerr_opt *rerr_opt)
{
struct in_addr err_src, err_dst, unr_addr;

if (!rerr_opt)
return -1;

dp->rerr_opt[dp->num_rerr_opts++] = rerr_opt;

switch (rerr_opt->err_type) {
case NODE_UNREACHABLE:
err_src.s_addr = rerr_opt->err_src;
err_dst.s_addr = rerr_opt->err_dst;

memcpy(&unr_addr, rerr_opt->info, sizeof(struct in_addr));

DEBUG("NODE_UNREACHABLE err_src=%s err_dst=%s unr=%s\n",
print_ip(err_src), print_ip(err_dst), print_ip(unr_addr));

/* For now we drop all unacked packets... should probably
* salvage */
maint_buf_del_all(err_dst);

/* Remove broken link from cache */
lc_link_del(err_src, unr_addr);

/* TODO: Check options following the RERR option */
/* dsr_rtc_del(my_addr(), err_dst); */
break;
case FLOW_STATE_NOT_SUPPORTED:
DEBUG("FLOW_STATE_NOT_SUPPORTED\n");
break;
case OPTION_NOT_SUPPORTED:
DEBUG("OPTION_NOT_SUPPORTED\n");
break;
}

return 0;
}
  • 第11-29行,若收到“节点不可达”的错误,则节点会在自己的路由缓存中删除这条路由
  • 第30-35行,其他类型的错误,会输出错误的类型