大三《网络协议栈分析与设计》课程作业,小组合作完成,由我完成了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后,在本地路由缓存中缓存路由信息。
路由维护
路由维护会在以下情况下启动:
- 当源节点向目的节点发送数据时,需要对当前路由的可用情况进行监控
- 当网络拓扑变化导致路由故障时,切换到另一条路由或者重新发起路由发现过程
通过逐跳验证机制来判断路由错误信息,从而删除失效的路由:
- 如果数据分组被重发了最大次数仍然没有收到下一跳的确认,则节点向源端发送路由错误信息,并指明中断的链路,源端将该路由从路由缓存中删除
- 如果源端路由缓存中存在另一条到目的节点的路由,则使用该路由重发分组,否则重新开始路由发现过程。
数据结构
DSR选项头
在dsr-opt.h
文件中定义了DSR选项头的信息:
1 | struct dsr_opt_hdr { |
- 第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 | struct dsr_rreq_opt { |
- 第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 | struct dsr_rrep_opt { |
- 第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 | struct dsr_rerr_opt { |
- 第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 | struct dsr_srt_opt { |
- 第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 | struct dsr_pkt { |
第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
8struct 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 | struct rreq_tbl_entry { |
- 第3行
int state;
:表示路由请求的状态 - 第4行
struct in_addr node_addr;
:路由请求的目的地址 - 第8行
struct timeval last_used;
:从上次被使用,到现在的时间间隔
函数分析
流程图
路由发现
生成数据包
在dsr-pkt.c
中实现了生成数据包的功能:
1 | struct dsr_pkt *dsr_pkt_alloc(struct sk_buff *skb) |
- 第6-11行,先为数据包申请需要的内存空间,然后将内容全部置零
- 第13-51行,如果传入的
skb
指针不为空,则数据包会根据skb
所指向的内容进行初始化 - 第52行,函数返回指向这个数据包的指针
为DSR选项首部分配内存
在dsr-opt.c
中实现了生成选项首部的功能
1 | struct dsr_opt_hdr *dsr_opt_hdr_add(char *buf, unsigned int len, |
- 第5-6行,判断缓冲区的长度能否放下DSR选项首部,若不能,则返回空指针
- 第8-13行,对选项首部信息进行初始化操作
- 第15行,函数返回指向这个首部的指针
DSR协议处理数据包
每个节点都需要与其他节点进行数据包的交互,这就涉及到了对于接收和发送数据包的处理,这两部分功能的实现定义在了dsr-io.c
中
接收数据包
1 | int NSCLASS dsr_recv(struct dsr_pkt *dp) |
- 第18-24行,根据选项中的信息,如果数据包是空、丢失、错误,则返回错误信息,并释放该数据包的空间
- 第34-52行,如果是转发的数据包,我们会对数据包的TTL进行判断:如果TTL为0,需要输出信息,并且释放掉该数据包的空间,不再进行转发操作;否则,我们输出其源IP地址、目的IP地址及下一跳IP地址,并执行
XMIT()
操作(后文介绍),传输数据包。 - 第86行,如果都不满足的话,就说明这个数据包的选项信息是未知的,我们只需要释放掉这个数据包即可
发送数据包
1 | void NSCLASS dsr_start_xmit(struct dsr_pkt *dp) |
- 第10行,执行
dsr_rtc_find()
功能,根据数据包来寻找是否存在到达目的节点的源路由 - 第12-22行,如果有,则在添加源路由成功的条件下,执行
XMIT()
操作(后文介绍),发送数据包 - 第24-40行,如果没有,则将这个数据包添加到发送队列中,并去进行路由发现
DSR处理源路由请求
在知道路由路径的情况下,就需要将数据包发送到目标地址,我们先看一下如何处理源路由选项。
在dsr-srt.c
中实现了对源路由选项的处理功能。
添加源路由选项
1 | struct dsr_srt_opt *dsr_srt_opt_add(char *buf, int len, int flags, |
- 第6-7行,判断缓冲区的空间是否足够添加该选项
- 第9-17行,若足够,则为该选项在内存中分配空间,然后初始化相关属性,包括:类型、长度等
- 第19行,复制地址列表
- 第21行,返回指向该选型的指针
路由缩减
路由缩减,即缩短路由路径,当节点监听到一个数据包,但该数据包的下一跳不是它自己时,节点就会在这个数据包的剩余源路由中搜索是否有自身的IP地址,若存在,则意味着路由可以缩减。
1 | int NSCLASS dsr_srt_opt_recv(struct dsr_pkt *dp, struct dsr_srt_opt *srt_opt) |
- 第15-17行,对路由缩减的条件进行判断:如果下一跳的地址不是当前地址,且源路由中存在当前地址且其不在缩减列表中,则可以进行路由缩减。
- 第43-45行,在路由缩减列表中添加本次路由,并且发送一个路由回复用于通知新的路由变更。
- 第67行,如果不能进行路由缩减,则转发数据包。
生成路由请求
路由发现请求
当一个节点不知道应该如何到达目的节点时,就会采用路由发现来寻找路由。在dsr-rreq.c
中得以实现:
1 | int NSCLASS dsr_rreq_route_discovery(struct in_addr target) |
- 第11行,调用
__tbl_find()
函数(后文介绍),在路由请求表中寻找是否已经有相同目的地址的路由请求 - 第13-19行,如果没有相同的路由请求,就调用
__rreq_tbl_add()
(后文介绍)把该请求添加到路由请求表中;如果有,则调用__tbl_detach()
删除原先的路由请求,并调用__tbl_add_tail()
把新的路由请求添加到路由请求表的末尾 - 第38-41行,设置该路由请求选项的TTL,一旦TTL为0,则取消该路由请求
- 第46-47行,设置失效时间
expires
查询路由请求表
在dsr-rreq.c
和tbl.h
中,有:
1 | typedef int (*criteria_t) (void *elm, void *data); |
- 第1行,
criteria_t
是参数为两个void类型的指针、返回值为int类型的指针 - 第2-10行,
crit_addr()
函数用于判断路由请求表项的目的地址和传进来参数的地址是否匹配 - 第11-19行,
__tbl_find
用于遍历整个路由请求表,寻找是否有和参数id相同的地址,若存在则返回指向匹配元素的指针,不存在则返回NULL
添加路由请求表项
在dsr-rreq.c
中得以实现:
1 | struct rreq_tbl_entry *NSCLASS __rreq_tbl_entry_create(struct in_addr node_addr) |
- 第24行,当我们调用
__rreq_tbl_add()
函数的时候,首先会调用__rreq_tbl_entry_create()
- 第1-21行,给表项分配一段内存,并对表项内容进行初始化操作
- 第26-35行,查看请求表的情况,看是否已满,若为满,则将请求表中的第一个表项删除
- 第36行,把路由请求添加到请求表的结尾处
发送路由请求
1 | int NSCLASS dsr_rreq_send(struct in_addr target, int ttl) |
###发送路由请求
添加路由请求选项
在dsr-rreq.c
中得以实现:
1 | static struct dsr_rreq_opt *dsr_rreq_opt_add(char *buf, unsigned int len, |
- 与添加DSR选项首部类似,判断缓冲区空间是否足够,如果足够,就把选项指针指向缓冲区,并初始化id、长度、目的地址
发送路由请求
在dsr-rreq.c
中得以实现:
1 | int NSCLASS dsr_rreq_send(struct in_addr target, int ttl) |
- 第7行,为该DSR数据包分配内存地址
- 第13-15行,将数据包的目的地址、下一跳的地址均设置为广播地址,将源地址设置为自身地址
- 第24-25行,构造数据包的IP首部,包括源地址、目的地址、协议类型和负载长度等
- 第30行,对DSR选项首部的构造
- 第40行,调用
dsr_rreq_opt_add()
函数,添加路由请求选项 - 第54行,调用
XMIT()
函数(分析见后),将数据包传输出去
发送数据包
XMIT()
是dsr_dev_xmit()
的宏定义,在dsr-dev.c
中实现:
1 | int dsr_dev_xmit(struct dsr_pkt *dp) |
- 第17行,根据DSR数据包的数据创建一个
sk_buff
数据包 - 第33-45行,完成MAC首部的封装
- 第48行,调用
dev_queue_xmit()
将数据包发送出去 - 第54-55行,统计发送的数据包信息
- 第59行,如果中间某个过程产生错误,则释放该数据包的空间
接收路由请求
当一个节点收到的数据包中包含路由发现请求时,这个节点必须通过以下步骤处理:
- 如果路由请求的目的地址与该结点的IP地址一致,则这个节点就需要发送一个路由回复给路由请求的发起者
- 如果路由请求的目的地址与该结点的IP地址不一致,则这个节点就需要在自己的已接收路由请求缓存中搜索是否已经发出过相同的请求。如果已经发出过,则必须丢弃该数据包防止重复转发
- 如果没有发送过:
- 该几点在已接收路由请求缓存中添加这个请求
- 将自己的IP地址添加到路由请求选项的Addrs[]中,并更改选项中length的值
- 在自己的路由缓存中搜索是否有到达目的节点的路由,若有,则发送“缓存路由回复”给源地址;若没有,则以链路层广播的形式将这个修改后的数据包发送出去
产生路由回复的功能在dsr-rreq.c
中得以实现:
1 | int NSCLASS dsr_rreq_opt_recv(struct dsr_pkt *dp, struct dsr_rreq_opt *rreq_opt) |
- 第25-28行,判断该路由请求是否已经存在于缓存中,若存在,则丢弃该包;若不存在,则在路由请求表里面添加这个请求
- 第44行,根据该数据包的源路由建立逆向源路由,以便发送路由回复
- 第66-81行,如果路由请求的目的地址与该节点自身地址一致,就发送路由回复,选项为路由回复选项
- 第95行,如果路由请求的目的地址与自身地址不同,则在该节点的路由缓冲中搜索是否有到目的节点的路由
- 第125行,发送路由回复请求
- 第133-153行,如果没有发现,就为DSR选项分配更多的内存,然后将自身的IP地址添加到路由请求选项中,更新IP首部信息
- 第155行,进行转发
路由维护
处理确认请求选项
确认请求(ACK Request)选项,DSR使用确认请求选项来判断邻居节点是否存活。当给一个邻居节点重发多次ACK请求却仍然没有收到回复的话,该节点就会认为其到邻居节点的链路已经被破坏,从而从路由缓存中删除这条路由,并且给上一次收到ACK之后在这条链路上发送过数据包的节点发送路由错误
dsr-ack.c
实现了对接收到的带确认请求选项的数据包回复ACK的功能。
1 | int NSCLASS dsr_ack_req_opt_recv(struct dsr_pkt *dp, struct dsr_ack_req_opt *ack_req_opt) |
处理确认选项
当数据包顺利送达目标节点之后,就会产生一个确认(ACK)选项,而源节点收到这个选项后,就从维护缓存中删除发送给ACK源端的数据包。
在dsr-ack.c
中实现:
1 | int NSCLASS dsr_ack_opt_recv(struct dsr_ack_opt *ack) |
生成路由错误选项
&emsp当发生路由错误时,比如网络拓扑结构发生变化,数据包无法送达,节点需要生成并发送错误通知给数据包的源节点。
&emsp在dsr-rerr.c
中得以实现:
1 | int NSCLASS dsr_rerr_send(struct dsr_pkt *dp_trigg, struct in_addr unr_addr) |
- 第24行,申请一个DSR数据包
- 第31行,建立一条到达数据包源端的路由,以便发送错误
- 第89-91行,添加路由错误的选项
- 第132行,调用
XMIT()
函数,发送数据包
处理路由错误选项
&emsp在dsr-rerr.c
中实现了处理路由错误选项的功能:
1 | int NSCLASS dsr_rerr_opt_recv(struct dsr_pkt *dp, struct dsr_rerr_opt *rerr_opt) |
- 第11-29行,若收到“节点不可达”的错误,则节点会在自己的路由缓存中删除这条路由
- 第30-35行,其他类型的错误,会输出错误的类型