IPv6协议转发实验

实验目的

通过前面的实验,我们已经深入了解了 IPv6 协议的分组接收和发送处理流程。本实验需要将实验模块的角色定位从通信两端的主机转移到作为中间节点的路由器上,在 IPv6 分组收发处理的基础上,实现分组的路由转发功能。

网络层协议最为关注的是如何将 IPv6 分组从源主机通过网络送达目的主机,这个任务就是由路由器中的 IPv6协议模块所承担。路由器根据自身所获得的路由信息,将收到的 IPv6分组转发给正确的下一跳路由器。如此逐跳地对分组进行转发,直至该分组抵达目的主机。 IPv6 分组转发路由器最为重要的功能

本实验设计实现路由器中的 IPv6 协议,可以在原有 IPv6 分组收发实验的基础上,增加 IPv6 分组的转发功能。对网络的观察视角由主机转移到路由器中,了解路由器是如何为分组选择路由,并逐跳地将分组发送到目的端的。 大家在本实验中也会初步接触路由表这一重要的数据结构,认识路由器是如何根据路由表对分组进行转发的。

实验具体任务

对于每一个到达本机的 IPv6 分组,根据其目的 IPv6 地址查找本机的路由表,对该分组进行如下的几类操作:

  • 丢弃查不到路由的分组;
  • 上层协议上交目的地址为本机地址的分组
  • 根据路由查找结果,向相应接口转发其余的分组。

实验内容

实验内容主要包括:

  • 设计路由表数据结构:设计路由表所采用的数据结构。要求能够根据 IPv6 地址来确定分组处理行为(丢弃、 上交或转发),转发情况下需获得下一跳的 IPv6 地址。路由表的数据结构和查找算法会极大的影响路由器的转发性能,有兴趣的同学可以深入思考和探索。
  • IPv6 分组的接收和发送:对前面实验中所完成的代码进行修改,在路由器协议栈的 IPv6 模块中能够正确完成分组的接收和发送处理。具体要求不做改变,参见IPv6 分组收发实验。
  • IPv6 分组的转发:对于需要转发的分组进行处理,获得下一跳的 IP 地址,然后调用发送接口函数进一步处理。

实验过程:

程序整体设计流程

程序运行流程

实验流程如图1所示,在下层接收接口函数stud_ipv6_fwd_deal( )中(图1接口函数1),实现 分组接收处理。其主要功能是根据分组中目的 IPv6 地址查找路由表,根据路由表查找结果进行后续处理。

  • 分组需要上交,则调用接口函数ipv6_fwd_LocalRcv( )(图 5.1 中接口函数2);
  • 需要丢弃,则调用函数 ipv6_fwd_DiscardPkt( )(图 5.1 中函数5);
  • 需要转发,则进行转发操作。转发操作的实现要点包括:
    • Hop Limit 值减 1,然后调用发送接口函数 ipv6_fwd_SendtoLower( )(图 5.1 中接口函数 4)将分组发送出去。
    • 接口函数ipv6_fwd_SendtoLower( )比前面实验增加了一个参数nexthop,要求 在调用时传入下一跳的 IPv6 地址,此地址是通过查找路由表得到的。
  • 另外,本实验增加了一个路由表配置的接口(图1中函数6),要求能够根据系统所给信息来设定本机路由表。实验中只需要简单地设置静态路由信息,以作为分组接收和发送处理的判断依据。

路由表数据结构设计及路由查找过程

在本实验的实现过程中,我的路由表数据结构是采用链表进行实现的,路由查找时顺序遍历链表比对掩码和目的地址,并记录当前最长匹配结果。路由的掩码匹配做法是先将IPv6地址转换为128bit的位数组,然后比对掩码长度位,具体如下:

  • 转换为bitset[128]位数组
1
2
3
4
5
6
7
8
9
bitset<128> trans_bit_addr(ipv6_addr addr) {
bitset<128> bit_ipv6;

for (int i = 0; i < 4; ++i) {
bit_ipv6 = bit_ipv6 | (bitset<128> (addr.dwAddr[3-i]) ) << (32 * i);
// 按位或将ipv6_addr的四个long型数据转换为对应的位数组,左移96,64,32,0位
}
return bit_ipv6;
}
  • 路由查找
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
list<stud_ipv6_route_msg>::iterator router;
bool match = false;
// 是否找到匹配项
int MAX_LENGTH = 0;
// 标记当前最长匹配

// 利用bitset将目的ip地址转换为128位数组
bitset<128> dest_ipv6 = trans_bit_addr(*dest_addr);
ipv6_addr next;

for(router = router_tables.begin(); router != router_tables.end(); ++router) {
// 遍历路由表
if (router -> masklen < MAX_LENGTH) {
// 短于当前已匹配路由表
continue;
}

// 将路由表中目的ip地址换算为bit表示的数组
bitset<128> router_dest = trans_bit_addr(router -> dest);

bool local_match = true;
for(int i = 0; i < router -> masklen; ++i) {
if (router_dest[i] != dest_ipv6[i]) {
local_match = false;
break;
}
}

if (local_match) {
match = true;
// 匹配则更新masklen, 更新路由地址
next = router -> nexthop;
MAX_LENGTH = router -> masklen;
}
}

优化措施

这样的设计其实效率是比较低的,可以进一步完成的优化是:在插入新的路由信息至路由链表时,按照掩码从大到小的顺序插入,这样在遍历查找路由信息时,查找到第一个匹配的记录即可停止遍历。

更进一步的优化是采用二叉树的形式进行构建。

下层分组接收函数 stud_ipv6_fwd_deal( )

本函数是 IPv6 协议接收流程的下层接口函数,实验系统从网络中接收到分组后
会调用本函数。调用该函数之前已完成 IPv6 分组的合法性检查,因此本函数应该考虑实现 如下功能:

  • 判定是否为发给本机的分组,如果是,则调用 ipv6_fwd_LocalRcv().

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    // a. 查找是否是发向本机
    // 先获取目的地址,第192bit起为目的ip,故偏移24Byte
    ipv6_addr *dest_addr = (ipv6_addr*) (pBuffer + 24);
    ipv6_addr *local_addr = new ipv6_addr();
    // 本地IPv6地址
    getIpv6Address(local_addr);

    bool is_lcoal = true;
    for(int i = 0; i <16; ++i) {
    if(dest_addr->bAddr[i] != local_addr->bAddr[i]) {
    // 分组不是本地
    is_lcoal = false;
    break;
    }
    }
    if(is_lcoal) {
    // 是本机接收分组,直接上交
    ipv6_fwd_LocalRcv(pBuffer, length);
    return 0;
    }
  • 按照最长匹配原则查找路由表,获取下一跳 IPv6 地址。查找失败,则调用 ipv6_fwd_DiscardPkt().

    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
    // b. 按照最长匹配查找路由表获取下一跳,查找失败则调用ipv6_fwd_DiscardPkt( );∂
    list<stud_ipv6_route_msg>::iterator router;
    bool match = false;
    // 是否找到匹配项
    int MAX_LENGTH = 0;
    // 标记当前最长匹配

    // 利用bitset将目的ip地址转换为128位数组
    bitset<128> dest_ipv6 = trans_bit_addr(*dest_addr);
    ipv6_addr next;

    for(router = router_tables.begin(); router != router_tables.end(); ++router) {
    // 遍历路由表
    if (router -> masklen < MAX_LENGTH) {
    // 短于当前已匹配路由表
    continue;
    }

    // 将路由表中目的ip地址换算为bit表示的数组
    bitset<128> router_dest = trans_bit_addr(router -> dest);

    bool local_match = true;
    for(int i = 0; i < router -> masklen; ++i) {
    if (router_dest[i] != dest_ipv6[i]) {
    local_match = false;
    break;
    }
    }

    if (local_match) {
    match = true;
    // 匹配则更新masklen, 更新路由地址
    next = router -> nexthop;
    MAX_LENGTH = router -> masklen;
    }
    }
  • 查找成功,则调用 ipv6_fwd_SendtoLower(),完成分组发送。

  • 转发过程中注意对 Hop Limit 的处理。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    // c. 需要转发,hop limit - 1 ,调用 ipv6_fwd_SendtoLower( )完成报文发送
    if(match) {
    // 获取hop limit,注意转换为本地字节序
    char HopLimit = *(char *)(pBuffer + 7);
    HopLimit -= 1;

    memcpy(pBuffer + 7, &(HopLimit), sizeof(char));

    if(HopLimit == 1) {
    // 直接发向目的地址
    ipv6_fwd_SendtoLower(pBuffer, length, dest_addr);
    return 0;
    }
    if(HopLimit > 1) {
    ipv6_fwd_SendtoLower(pBuffer, length, &next);
    return 0;
    }
    }

实验结果分析

分析传输的报文,处理正确

实验结果

遇到的问题及解决

  • 掩码的比对问题,由于IPV6地址是128位长,其实际存储结构为
1
2
3
4
5
6
typedef union
{
char bAddr[16];
unsigned short wAddr[8];
long dwAddr[4];
}ipv6_addr;
  • 其掩码比对无法像IPV4地址那样直接简单地进行移位操作,因此,我想到的一个解决方法是将其转换为长度为128的位数组,进一步依次进行比较。

  • 处理IPV6数据包时的网络字节序和本机字节序问题,网络字节序是大端模式,而本机字节序一般是小端模式,因此需要注意其字节序的转换,在本实验的实现过程中,IPv6地址的比较是采用按位比对的模式,由于计算机底层硬件bit序并不受解析模式的影响,因此不需要考虑字节序转换问题,而解析hop limit时,由于是直接截取的char类型(8 bit),也不会受字节序的影响,也没有必要进行字节序的转换。

思考题:实验指导书的思考题(2)

IPv6和IPv4地址长度存在显著差别,考虑路由查找过程中各自采用什么样的数据结构和算法有助于提高查找效率

答: IPV4的地址为32位长,不考虑空间占用的话,实际上最快的一种数据结构应该是二叉树,即根据目的地址的比特串构建二叉树即可,这样搜索时最多需要32步,可以说是可以极大的减小查询时间,当然这样的空间占用会比较高,通常会做出压缩的优化以及其他优化,可以说IPv4的路由查询可以做到非常高效的查询。

而IPv6地址长度为128位,是不可能像IPv4那样建一个二叉比特树的,查阅相关资料,有如下解决方案:
已有IPv6路由表的统计结果和地址分配策略表明,长度大于48比特的前缀比例很低,仅为5%左右,因此可对IPv6地址的高48位采用多分支trie进行查找,剩余的16比特直接采用hash查找。根据IPv6地址前缀的分布特点,构造查找步宽为24-8-8-8-16的五层多分支TrieC树,限制最坏情况下路由查找的访存次数。

通过这样的方式可以极大地加快IPV6的路由查询。

总结

本次实验实现了IPV6分组的转发,通过本次实验,我更加清晰地认识了网络原理课程中的IPv6数据 包转发的过程,对最长匹配原则也有了一个清晰的理解,对网络字节序和本机字节序有了更深入的理解。感谢助教的热心帮助。

打赏