基于LWIP协议栈对路由缓存数据结构实现改进设计
lwip（light weight internet protoco1）是瑞士计算机科学院（swedish institute of computer science）adamdunkels等人开发的一套用于嵌入式系统的开放源代码tcp／ip协议栈。lwip的含义是light weight（轻型）ip协议。lwip可以移植到操作系统上，也可以在无操作系统的情况下独立运行。lwip tcp／ip实现的重点是在保持tcp协议主要功能的基础上减少对ram的占用。一般它只需要几十kb的ram和40 kb左右的rom就可以运行，这使lwip协议栈适合在小型嵌入式系统中使用。比如，武汉大学的陈杰等把lwip移植到了一个车辆监控终端系统当中，它可以实时采集车辆信息，在gis地图上显示出车辆的位置，并根据需要对车辆进行调度；南京大学的方怀东等将lwip移植到了dsp系统中，这个嵌入式系统用于视频的采集、处理与通信；astechnix研究院的jani monoses将lwip移植到了redhats ecos；f1orian schtdze则宣称他将lwip移植到了djgpp／ms—dos系统以及visual c++6．o／win32平台。
1 lwip设计思路
与许多其他的tcp／ip实现一样，lwip也是以分层的协议为参照来设计实现tcp／ip。大部分的tcp／ip实现在应用层和底层协议层之间进行了严格的划分，底层协议之间可以进行或多或少的交叉存取；而lwip在应用层与低层协议则使用了内存共享这种比较松散的通信机制。每一个协议作为一个模块被实现。lwip采取将所有协议驻留在同一个进程的方式，以便独立于操作系统内核之外。应用程序既可以驻留在lwip的进程中，也可以使用一个单独的进程。应用程序与tcp／ip协议栈通信可以采用两种方法：一种是函数调用，适用于应用程序与lwip使用同一个进程的情况；另一种是使用更抽象的api。整个协议栈框图如图1所示。
由于在传输层udp比tcp协议要简单得多，故仅以tcp为例。
在接收数据方面，链路层的ethernetifinpuit（）函数在收到数据包后，将ip包交付ip_input（）函数，arp包交付 etharp_arp_input（）函数处理。ip_input（）则负责拆解ip包，将icmp包交付icmp_input（）函数处理，将tcp包交付tcp_input处理。tcp_input（）负责收到的tcp包，完成tcp头部验证，放入相应的状态链，并交付tcp_process（）处理。tcp_process完成tcp无限状态机的处理。tcp_receive（）将收到的包放在接收队列中，这些接收队列中的数据最终被应用程序使用。
在发送数据方面，tcp_write（）检查是否允许发送数据，当允许发送时，就调用tcp_enqueue（）进行发送。tcp_enqueue（）将数据放入发送队列。tcp_output（）发送数据并在可能时捎带确认。ip_output_if（）在接到数据后，填充ip头，交付netif 一》output，即etharp_output（）处理。etharp_output（）判断是单播地址后，交付etharp_query（）。 etharp_query（）填入源、目标mac地址，并最终交付low_level_output（）发送。
2 icmp层的不足
lwip在icmp层的处理流程如图2所示。
icmp模块仅实现了echo_reply包的回应处理，显得过于简单。对小型的协议栈而言，其所在的网络环境相对简单，因而在大多数情况下都是适用的。
lwip一般使用在终端设备上。终端设备所在的情形可作如下的划分：一是单网卡、单网关的情形；二是单网卡、多网关的情形；三是多网卡、多网关的情形。单网卡、单网关的情形是lwip最适合的情形。因为lwip本身没有实现路由缓存，单网关的情形恰好不需要路由缓存，因为此情形下网关总是唯一的，下一跳总是不变的。多网卡、多网关的情形可以看成是单网卡、多网关的特殊情形。
在单网卡、多网关的情形下，如果默认网关的下一跳不是最优下一跳，那么终端会收到一个路由重定向icmp消息，告诉终端去往这个方向上，这个下一跳不是最优的，并给出最优下一跳。这就是所谓的路由重定向。如果终端一直不采用这个最优下一跳，那么每一个发出的非最优下一跳ip包都会收到路由器发来的一个重定向包。lwip由于没有实现路由缓存，不能记录下网关发来的最优下一跳，故对此消息的处理是忽略。忽略的结果是lwip源源不断地收到重定向包，这个包会经过数据链路层、ip层，最终在icmp层被丢弃，引起不必要的开销。
3 改进思路
改进的思路是在多网关情况下，处理icmp包；但lwip并没有路由缓存功能，所以需要引入路由缓存功能，将此重定向的路由记录下来，以使得下次可使用。为降低内存开销，可以在收到icmp重定向包的情况下（此时表明是多网关情形，下一跳非最优），再开启缓存，缓存这个下一跳地址。如果一段时间不用这个缓存，则清理出去。当最后一条缓存也被清理后，就关闭缓存功能。这相当于一个自适应功能的路由缓存。在没有重定向消息时，使用原有的lwip工作方式，不会引起额外的开销；在收到重定向消息时，开启这个缓存功能，以避免重定向消息引起的额
对路由缓存的更新，可采用一种类似于lfu（leastfrequently used）的算法。为此引入一个计数器，跟踪当前条目被使用的情况，定义max_ca_count表示已经过期，o～max_ca_count之间的数字表示当前计数值，同时每隔一段时间增加这个计数值。当这个计数值增至max_ca_count时，认为这个条目已经过时。同时在插入条目时，可利用这个计数器，总是选用这个数值最大的条目作为被替换对象（lfu算法）。
考虑到lwip是个小型协议栈，不应设置过于复杂的数据结构及针对此种数据结构的操作，把路由缓存的数据结构定义为结构体数组。数组的条目也不宜过多，以免占用过多资源；另外作为终端设备，在一小段既定的时间内，与其通信的对端具有一定的确定性，一般来说比较少，重定向的条目也比较少，这也为使用较小的数组提供了一个理由。
4 实现
对icmp层改进的实现代码主要集中于3处。
第一处位于icmp模块的icmp_input（）函数，针对icmp的消息处理机制，增加了路由重定向的处理。整个函数的处理流程如图3所示。其中虚线框起来的部分为我们增加的功能。首先检查是不是重定向包，然后检验包的完整性和有效性。在这些检查都通过以后，判断缓存功能是否启用。启用与否由一个全局变量控制，默认是关闭的。如果没有启用缓存，则对重定向包进行计数，当达到上限后，启用缓存功能。重定向计数器应当定时归零，这样在一段时间内没有收到足够的重定向包，缓存功能仍然不会开启。这可以把这个重定向计数器加入其他需要定时执行的函数中来实现（比如arp_timer（）函数）。开启缓存后，初始化缓存表，将每个条目的老化计数器置为最大，表示已过期，即所有条目都是空闲可用状态。然后启用定时老化功能。lwip提供 sys_timeout（interval，func_handler，arg）函数，用于每隔interval时间后，执行函数 func_handler（arg）。定向老化功能可以将函数实现后，向这个sys_timeout（）注册来实现。如果缓存已经开启，那么缓存这个收到的重定向包，总是把它插入老化计数器最大的条目，以实现lfu算法。
第二处改进仍然位于icmp模块，但添加了一个函数rou_cache_timer（）。它是一个定时老化路由缓存的函数，用于老化、清理缓存条目，并再次向sys_timeout（）注册自己。其函数流程如图4所示。
在所有缓存条目都已过图4定时老化、清理路由缓存期后，应当关闭缓存功能，同时注销定时老化函数。这些功能由rou_cache_timer（）来完成。
第三处改进位于数据链路层的etharp_output（）函数内。这个函数负责将下一跳的ip地址对应的mac地址填入。
显然，路由缓存的使用正在于此。在它使用默认网关地址前，应当查询一下缓存中是否已将此路由重定向了。如果确实重定向了，那么在此下一跳ip被使用前，应该替换已重定向的ip。整个函数的流程如图5所示。虚线框起来的部分是加入的功能。
结语
本设计针对lwip在多网关情况下不处理重定向ic—mp消息而作出了改进。这种改进包括接收这个icmp消息并缓存路由信息，为此加入了自适应路由缓存的功能，即只在有重定向消息的时候自动开启缓存，在缓存全部老化后又自动关闭缓存。路由缓存在比较完整的tcp／ip协议栈上都得到实现，但复杂度较高。这里使用一种较简单的路由缓存结构以降低代码量及资源使用开销。本文提出的思路不仅适用于lwip，在其他的小型协议栈上也适用。
4G LTE迎来机遇，几大挑战将门槛抬高
带滤波器的RJ45网口连接器
组织研磨仪的使用说明以及使用效果的介绍
华为推出高端显示器 世界最大AI处理器升级7nm工艺
51单片机时序及延时分析
基于LWIP协议栈对路由缓存数据结构实现改进设计
三星GalaxyS8工程图曝光，后置摄像头仅凸出0.2毫米
工信部将加大新材料、新一代信息技术、高端装备等培育支持力度
如何保障消费者在移动设备端进行各类金融业务的安全和便捷？
芯片价格飙涨5倍，这到底是怎么造成的
卫星数据链开发平台设计方案：522-基于AD9988的四通道1G带宽卫星数据链开发平台
波峰焊在电路板工艺上的应用有多重要
合宙迷你DAPLink开发板：高速下载，软硬件全开源！
小米概念新机曝光 陶瓷机身+2300W+“白菜价”
赢合科技中标宁德时代设备总金额为14．4亿元
苹果云iCloud优缺点共存
光棒放大电路图及原理
英特尔创新模式全面提升医疗信息系统效能
智能手表的未来形态：Pebble意在打造“可穿戴网络”
智能车库控制系统的射频识别模块与液晶显示模块介绍
1 lwip设计思路
与许多其他的tcp／ip实现一样，lwip也是以分层的协议为参照来设计实现tcp／ip。大部分的tcp／ip实现在应用层和底层协议层之间进行了严格的划分，底层协议之间可以进行或多或少的交叉存取；而lwip在应用层与低层协议则使用了内存共享这种比较松散的通信机制。每一个协议作为一个模块被实现。lwip采取将所有协议驻留在同一个进程的方式，以便独立于操作系统内核之外。应用程序既可以驻留在lwip的进程中，也可以使用一个单独的进程。应用程序与tcp／ip协议栈通信可以采用两种方法：一种是函数调用，适用于应用程序与lwip使用同一个进程的情况；另一种是使用更抽象的api。整个协议栈框图如图1所示。
由于在传输层udp比tcp协议要简单得多，故仅以tcp为例。
在接收数据方面，链路层的ethernetifinpuit（）函数在收到数据包后，将ip包交付ip_input（）函数，arp包交付 etharp_arp_input（）函数处理。ip_input（）则负责拆解ip包，将icmp包交付icmp_input（）函数处理，将tcp包交付tcp_input处理。tcp_input（）负责收到的tcp包，完成tcp头部验证，放入相应的状态链，并交付tcp_process（）处理。tcp_process完成tcp无限状态机的处理。tcp_receive（）将收到的包放在接收队列中，这些接收队列中的数据最终被应用程序使用。
在发送数据方面，tcp_write（）检查是否允许发送数据，当允许发送时，就调用tcp_enqueue（）进行发送。tcp_enqueue（）将数据放入发送队列。tcp_output（）发送数据并在可能时捎带确认。ip_output_if（）在接到数据后，填充ip头，交付netif 一》output，即etharp_output（）处理。etharp_output（）判断是单播地址后，交付etharp_query（）。 etharp_query（）填入源、目标mac地址，并最终交付low_level_output（）发送。
2 icmp层的不足
lwip在icmp层的处理流程如图2所示。
icmp模块仅实现了echo_reply包的回应处理，显得过于简单。对小型的协议栈而言，其所在的网络环境相对简单，因而在大多数情况下都是适用的。
lwip一般使用在终端设备上。终端设备所在的情形可作如下的划分：一是单网卡、单网关的情形；二是单网卡、多网关的情形；三是多网卡、多网关的情形。单网卡、单网关的情形是lwip最适合的情形。因为lwip本身没有实现路由缓存，单网关的情形恰好不需要路由缓存，因为此情形下网关总是唯一的，下一跳总是不变的。多网卡、多网关的情形可以看成是单网卡、多网关的特殊情形。
在单网卡、多网关的情形下，如果默认网关的下一跳不是最优下一跳，那么终端会收到一个路由重定向icmp消息，告诉终端去往这个方向上，这个下一跳不是最优的，并给出最优下一跳。这就是所谓的路由重定向。如果终端一直不采用这个最优下一跳，那么每一个发出的非最优下一跳ip包都会收到路由器发来的一个重定向包。lwip由于没有实现路由缓存，不能记录下网关发来的最优下一跳，故对此消息的处理是忽略。忽略的结果是lwip源源不断地收到重定向包，这个包会经过数据链路层、ip层，最终在icmp层被丢弃，引起不必要的开销。
3 改进思路
改进的思路是在多网关情况下，处理icmp包；但lwip并没有路由缓存功能，所以需要引入路由缓存功能，将此重定向的路由记录下来，以使得下次可使用。为降低内存开销，可以在收到icmp重定向包的情况下（此时表明是多网关情形，下一跳非最优），再开启缓存，缓存这个下一跳地址。如果一段时间不用这个缓存，则清理出去。当最后一条缓存也被清理后，就关闭缓存功能。这相当于一个自适应功能的路由缓存。在没有重定向消息时，使用原有的lwip工作方式，不会引起额外的开销；在收到重定向消息时，开启这个缓存功能，以避免重定向消息引起的额
对路由缓存的更新，可采用一种类似于lfu（leastfrequently used）的算法。为此引入一个计数器，跟踪当前条目被使用的情况，定义max_ca_count表示已经过期，o～max_ca_count之间的数字表示当前计数值，同时每隔一段时间增加这个计数值。当这个计数值增至max_ca_count时，认为这个条目已经过时。同时在插入条目时，可利用这个计数器，总是选用这个数值最大的条目作为被替换对象（lfu算法）。
考虑到lwip是个小型协议栈，不应设置过于复杂的数据结构及针对此种数据结构的操作，把路由缓存的数据结构定义为结构体数组。数组的条目也不宜过多，以免占用过多资源；另外作为终端设备，在一小段既定的时间内，与其通信的对端具有一定的确定性，一般来说比较少，重定向的条目也比较少，这也为使用较小的数组提供了一个理由。
4 实现
对icmp层改进的实现代码主要集中于3处。
第一处位于icmp模块的icmp_input（）函数，针对icmp的消息处理机制，增加了路由重定向的处理。整个函数的处理流程如图3所示。其中虚线框起来的部分为我们增加的功能。首先检查是不是重定向包，然后检验包的完整性和有效性。在这些检查都通过以后，判断缓存功能是否启用。启用与否由一个全局变量控制，默认是关闭的。如果没有启用缓存，则对重定向包进行计数，当达到上限后，启用缓存功能。重定向计数器应当定时归零，这样在一段时间内没有收到足够的重定向包，缓存功能仍然不会开启。这可以把这个重定向计数器加入其他需要定时执行的函数中来实现（比如arp_timer（）函数）。开启缓存后，初始化缓存表，将每个条目的老化计数器置为最大，表示已过期，即所有条目都是空闲可用状态。然后启用定时老化功能。lwip提供 sys_timeout（interval，func_handler，arg）函数，用于每隔interval时间后，执行函数 func_handler（arg）。定向老化功能可以将函数实现后，向这个sys_timeout（）注册来实现。如果缓存已经开启，那么缓存这个收到的重定向包，总是把它插入老化计数器最大的条目，以实现lfu算法。
第二处改进仍然位于icmp模块，但添加了一个函数rou_cache_timer（）。它是一个定时老化路由缓存的函数，用于老化、清理缓存条目，并再次向sys_timeout（）注册自己。其函数流程如图4所示。
在所有缓存条目都已过图4定时老化、清理路由缓存期后，应当关闭缓存功能，同时注销定时老化函数。这些功能由rou_cache_timer（）来完成。
第三处改进位于数据链路层的etharp_output（）函数内。这个函数负责将下一跳的ip地址对应的mac地址填入。
显然，路由缓存的使用正在于此。在它使用默认网关地址前，应当查询一下缓存中是否已将此路由重定向了。如果确实重定向了，那么在此下一跳ip被使用前，应该替换已重定向的ip。整个函数的流程如图5所示。虚线框起来的部分是加入的功能。
结语
本设计针对lwip在多网关情况下不处理重定向ic—mp消息而作出了改进。这种改进包括接收这个icmp消息并缓存路由信息，为此加入了自适应路由缓存的功能，即只在有重定向消息的时候自动开启缓存，在缓存全部老化后又自动关闭缓存。路由缓存在比较完整的tcp／ip协议栈上都得到实现，但复杂度较高。这里使用一种较简单的路由缓存结构以降低代码量及资源使用开销。本文提出的思路不仅适用于lwip，在其他的小型协议栈上也适用。
4G LTE迎来机遇，几大挑战将门槛抬高
带滤波器的RJ45网口连接器
组织研磨仪的使用说明以及使用效果的介绍
华为推出高端显示器 世界最大AI处理器升级7nm工艺
51单片机时序及延时分析
基于LWIP协议栈对路由缓存数据结构实现改进设计
三星GalaxyS8工程图曝光，后置摄像头仅凸出0.2毫米
工信部将加大新材料、新一代信息技术、高端装备等培育支持力度
如何保障消费者在移动设备端进行各类金融业务的安全和便捷？
芯片价格飙涨5倍，这到底是怎么造成的
卫星数据链开发平台设计方案：522-基于AD9988的四通道1G带宽卫星数据链开发平台
波峰焊在电路板工艺上的应用有多重要
合宙迷你DAPLink开发板：高速下载，软硬件全开源！
小米概念新机曝光 陶瓷机身+2300W+“白菜价”
赢合科技中标宁德时代设备总金额为14．4亿元
苹果云iCloud优缺点共存
光棒放大电路图及原理
英特尔创新模式全面提升医疗信息系统效能
智能手表的未来形态：Pebble意在打造“可穿戴网络”
智能车库控制系统的射频识别模块与液晶显示模块介绍