引言从1969年ARPANet投入运行开始计算，互联网在短短40年内渗入全球各个角落.随着结点数急剧增加，网络结构不断繁杂化，导致了以IPv4为核心的协议簇出现很多问题：尤为紧迫的是地址空间濒临枯竭——尽管已有NAT、CIDR等策略，但无法从根本上解决问题，其它如配置复杂、没有好的服务质量机制、在安全性和移动性等方面的不足都迫切要求开发更好的取代协议.1993年提出的IPng标准经过几年的修订,最终于1998年制订了较为完善的IPv6规范,较好地解决了这些问题.但直到现在仍在推广阶段,难以普及应用,主要是因为由IPv4过渡到IPv6需要投入大量的资金和设备,同时,相关技术尚待完善也是一个原因.1邻居发现协议存在的问题IPv6的邻居发现协议（Neighbor Discovery Protocol, ND）主要用于取代ARP/RARP、路由器发现和重定向等协议，并增加了邻居可达性检测机制［1］.邻居发现协议使用ICMPv6来交换报文，同时ICMPv6还是SNMPv6的下层协议，所以，ND对网络管理，特别是SNMPv6网络管理起着重要作用［2］.由于取消了ARP协议，在IPv6网络中,目前严重困扰着用户和网络管理员的ARP攻击导致LAN接入用户不能正常连接Internet问题有望彻底解决.但是,该协议仍有不足之处:大量频繁的ICMP广播包可能导致网络拥塞,增加超时重传的比例,而广播这一机制可能会被攻击者利用,再次制造类似ARP攻击机制的病毒［3］.使用Network Coding原理改进广播机制对避免这一不足有着很大优势［4］.2Ipv6邻居发现协议IPv6协议取消了位于Internet层下部的ARP/RARP协议和IGMP协议,取而代之的是位于IP层上部的ICMPv6及使用其提供服务的邻居发现协议ND和多播侦听者发现协议（Multicast Listener Discovery, MLD）［5］.底层和高层协议并没有质的改变（这是分层体系结构的优势）.使用路由器请求、路由器公告、邻居请求、邻居公告和重定向共五种报文,通过邻居缓存、目的缓存、前缀列表、默认路由器列表等数据实现了地址解析、邻居可达性检测、路由器和前缀发现及重定向四个主要功能.对于路由器和前缀发现及重定向两个功能,由于涉及到与路由协议的协同工作（如重定向功能时,应先假设路由选择算法已经有效避免了环路）,本文不作详细讨论.地址解析和可达性检测是邻居发现的重要功能,而且相互影响［6］.地址解析经七次报文交互完成：发送邻居请求→接收邻居请求→发送请求邻居公告→接收邻居请求公告，发送邻居非请求公告，任播非请求邻居公告，代理邻居公告（在使用代理时使用）.其流程如图 1所示.图1中处理邻居缓存条目、更新可达性处理流程可用图 2所示的状态转换图表示［7］.图1邻居发现处理流程
Fig.1Process of Neighbor Discovery

图2邻居可达性检测状态转换图
Fig.2State transition diagram of Neighbor reachability detecting3Network Coding思想Network Coding是Rudolf Ahlswede、蔡宁、李硕彦、杨伟豪［8］在2000年提出的一种突破性编码理论，其基本思想是：在网络发送端Sender只发送信息的相关证据（evidence about the message）而不是整个信息本身，而接收者Receiver收到证据后，对其进行重组以还原信息，提高网络的容量和效率［9］.其最大的优势在于多播网络中，一个发送源多个接收者时，数据包在网络中会有很多路径并重复传输，对于某几个特定的结点来说，要接收到所有数据包可能需要一定时间的排队［10］.典型地，对于如图 3的网络［11］, 假设每一跳的传输能力均为1，数据包经过一跳所需时间为t，若发送端S要发送两个等长（设为L）的数据包给R1和R2，如果按传统的传输模式，最优的方案如图 4所示，数据包和在到达节点N3时，不能立即被转发，而是需要排队，假设以的顺序排队发送，则发送两个包所需的总时间为，到达N4后，也需要按相同的方案排队发送，所以，S把两个包分别发送到R1和R2所需的最短时间是6 t，如果结点N4具有智能选择功能，在N4→R1线路上按顺序发送两个包，在N4→R2线路上按顺序发送，则两个接收结点可以忽略后一个已有的包，则时间缩短为.同时，这一模式还有一个问题存在：结点R1两次收到数据包，结点R2两次收到数据包，这给线路传输量增加了压力，同时，R1和R2还需要判定这两个包是经由不同路径达到的同一个包，还是重传的包，甚至是重放攻击的包［12］.第5期张金刚，等：运用Network Coding改进IPv6网络的邻居发现协议
武汉工程大学学报第32卷
如果采用Network Coding理论对上述网络传输过程进行改造，当数据包到达N3之后，对其进行异或运算，得到等长的c=ab，并把它转发给N4，N4再分别转发给R1和R2.如图 5所示，由于在N3→N4, N4→R1, N4→R2三条链路中传输的数据包只有一个，所以每跳所需的时间只为t.R1收到两个数据包后，进行运算a（ab），R2运算b（ab）=a，即可恢复出原数据包.所以，两个结点都收到了a，b两个包，传输任务成功完成.在结点N3和R处进行的只是简单的异或运算，所需时间相对于传输时间来说可以忽略不计，即所需的传输总时间为4t，比传统模式节省了2t，若按上述假设N4有智能时，节省时间，节省比例最小为14=25%，同时，整个网络中数据传输量合计为9个包（传统模式合计为12个包），节省了13［8］.图3网络结构图
Fig.3Network structure图4传统传输模式
Fig.4Classic Transfer mode由此可见，Network Coding对于广播包的发送能显著地提高效率，降低网络传输流量，节省网络带宽，而付出的代价主要是在节点中完成简单的异或运算，而对于目前的计算能力来说，异或运算的延迟可以达到只有一位.然而，在复杂的网络结构中，需特殊设计和规划适合于Network Coding传输模式的拓扑结构，以避免收到包后无法恢复出所需数据包的情况［13］.图5Network Coding传输模式
Fig.5Netcod Transfer mode4改进策略在IPv6网络的邻居发现协议中，存在大量的广播包，这些广播包的接收者是所有拥有相应广播地址的结点，可能是路由器，也可能是主机：对于邻居请求报文，最终接收者是主机，但可能需要路由器转发；对于路由器请求报文，接收者只是路由器，主机不对其进行处理；邻居公告报文和路由器公告报文都有单播和多播两种情况［14］.以一次完整的地址解析→可达性检测→数据发送过程为例，若网络结构如图 6所示，且所有结点都拥有具备多播能力的多播地址，算法流程为：（1）结点H0有两个目的地址分别为IPH3和IPH4的数据包需要发送，但在其邻居缓存中，没有该结点的相关信息，于是其创建一个“不完整条目”，并发送多播邻居请求a=NSM(IPH3‖MACH0)和b=NSM(IPH4‖MACH0).（2）路由器收到该多播包后，不断转发，若最终到达H3和H4，并经验证为合法，则返回单播包给H0，地址解析成功，H0修改两个邻居的状态为“可达”；否则转（3）.（3）H0重发该请求，若重发被成功响应，转（2），否则等待再次解析.（4）H3和H4发送多播非请求邻居公告c=NAM(IPH4‖MACH4)和d=NAM(IPH3‖MACH3)，宣布自己的存在，被多播给所有结点，H0, H1,和H2收到后，各自修改自己的邻居缓存状态，若H3，H4成功收到所有邻居的确认包，则修改到这些结点的状态为“可达”；否则，分别处理各个队列.（5）H0对H3，H4进行可达性探测，成功则发送数据包，否则转（3）.图6邻居发现协议网络结构
Fig.6Network structure of NDP该过程中，两次进行了多播广播，尽管实质上，这些多播包需要单个地进行处理，但是，如果在网络中采用单独传输的方法，则网络中会产生大量重复发送的包，同时也增加了传输延迟.若采用Network Coding传输模式，则上述广播流程可表示如图 7所示.图7中a=NSM（IPH3‖MACH0），b=NSM(IPH4‖MACH0)，实线箭头表示a和b包，虚线表示ab包，由于a和b两个包要广播给所有的结点，所以ab包可能有多条路由路径达到H1和H2，本示例假定路由器R0不进行数据包合并，结合路由协议，可以避免由R5→R1和R6→R2的包传送（因为这两个包实质上没有用），此时，不计主机与直连路由器的传输链路开销，总传输时间为4t，总传输量为9个包.对于第二次广播，传输方法与此类似.而此次广播若采用传统传输模式，其传输时间和传输量与第三节中的模型相同，可见，对于类似广播，采用Network Coding模式具有很大优势.图7多播邻居请求的Network Coding传输模式
Fig.7Netcod Transfer mode of Multicast5结语在IPv4网络中，广播机制被广泛应用，但通过子网隔离广播、ARP协议等机制，抑制了广播风暴的大量发生.对于IPv6网络，为了更好地支持灵活性与移动性，取消了子网划分机制，而类似于ARP协议、对拓扑发现、网络管理起着重要作用的邻居发现协议却大量使用了多播包（还有其它一些协议），大量的广播容易引起网络拥塞、增加延迟，降低了链路的传输效率.Network Coding思想，既可对邻居发现协议进行改进，还可用于其它广泛使用多播包的协议中，如P2P应用，路由信息交换等等［15］.本方案的前提是路由器具有编码能力即网络能支持Network Coding机制，目前还没有相关硬件的报道，本文仅就此思想提出一个思路，相关数据均为理论值，由于IPv6环境的特殊性，深入实验和仿真是下一步研究方向.