协议栈并行加速技术综述
西安电子科技大学计算机学院 权义宁
2015.01.03
1. 传统内核协议栈存在的问题
随着网络带宽快速提高到10G甚至是100Gbps，传统的协议栈结构已经不能适应超高速网络对数据转发和处理的要求，传统协议栈存在的问题如下：
传统网络协议栈一般是作为操作系统内核的一部分来设计与实现的，这样内核协议栈运行在高特权级，能保证其安全性。典型的内核协议栈包括Linux内核协议栈、FreeBSD内核协议栈等，二者均是TCP/IP协议栈实现的优秀典范。内核协议栈通过Socket API向上层应用程序提供服务，应用程序通过Socket API调用内核系统调用由用户态切换到内核态，并享用协议处理服务，系统调用执行完毕之后，由内核态切换回用户态。
在网络流量较小以及多核处理器技术尚未发达的时期，内核协议栈能够有效应对网络服务需求，并且运行良好。然而，随着网络技术的不断发展，人们对网络服务提出了更高的需求，应对大规模的网络流量以及高速网络带宽的情形下，内核协议栈由于其自身固有的弊端，以及其整体设计框架不适应多核处理器架构难于利用多核硬件进行并行处理等，使得操作系统内核协议栈已经成为影响网络传输性能的主要瓶颈。美国霍普金斯大学的Alexander Szalay教授在他的测试报告中指出，采用10G bps的网络，把150TB的大数据从霍普金斯大学传输到橡树岭国家实验室（Oak Ridge National Laboratory，ORNL）差不多需要10天时间，如图1所示。
为什么会出现这么严重情况？我们以传统协议栈接收数据包的基本流程为例，对其主要性能开销进行分析。
操作系统内核协议栈，数据包处理的基本过程如图2所示。
（1）网卡捕获到网络上的数据包后，将数据包从网卡的硬件缓存拷贝到内核态内存，并通过硬件中断通知内核，该过程主要由网卡驱动程序完成。
（2）内核收到数据包后，交由协议栈各层处理程序对数据包进行解析、校验等操作，提取出需要递交给上层用户态应用程序的数据。
（3）用户态应用程序需要处理网络数据时，通过系统调用陷入内核态，将数据拷贝到用户态缓冲区，之后通过切换特权级退出内核态。
从中可以得出，传统内核协议栈的包处理过程的主要性能开销为系统调用、内存拷贝、协议处理以及中断操作这几方面。
第一、系统调用作为应用程序享用操作系统内核提供服务的接口，以函数的形式供上层应用程序调用。网络应用程序正是通过socket系统调用，来获取内核协议栈的服务。通过软中断的方式，网络应用程序可以执行系统调用获取相应的功能。然而系统调用执行于内核空间，应用程序调用系统调用必定会进行特权级切换，会带来额外的上下文切换开销，系统调用前要对应用程序上下文进行保护，系统调用执行完之后，要恢复之前的进程上下文。频繁的上下文切换占用了大量的CPU资源，在万兆以上级别的网络带宽情况下，这种开销更加明显，会严重影响系统性能。
第二、内存拷贝开销。应用程序与硬件网卡之间的数据包传递通路，包括两次内存拷贝过程：从网卡到内核空间DMA缓冲区的复制；再从内核空间DMA缓冲区复制到用户空间。在网络数据发送与接收的整个流程中，涉及了多次内存数据复制，每次拷贝过程都需要CPU的参与，消耗了大量的系统资源。
第三、中断处理开销。网络协议处理中引入硬件中断是由于考虑到网络数据包的突发性以及其传输时延的不确定性等，网卡在接收到数据包后通过硬件中断方式通知内核进行处理，这种异步通信方式能够更加有效，特别是在网络流量较小的时候，硬件中断相比于轮询等方式能极大地降低CPU的占用率，提高CPU的整体利用率。然而，当网络带宽增大、网络数据量急速增加时，会频繁地产生硬件中断，由于硬件中断的高优先级，CPU会陷入无限的硬件中断处理中无法进行协议处理等其他操作，导致系统一直处于收包然后丢包的恶性循环中，CPU持续做无用功，资源大量浪费。关于CPU主频和网卡速率的发展关系如图3所示。
图3 CPU主频和网卡速率的发展关系
从图中可以看出，CPU的主频从2005年以后由于发热问题无法解决，一直停留在大约4.3GHz左右，但是网卡的带宽却是高歌猛进，已经达到了10Gbps左右，这说明在单核CPU框架下的传统协议栈已根本不能满足当前网络的高速发展需要，必须并行加速。
2. 国内外现状
在网络协议栈开发早期，就通过引入数据包并行的方案来提高协议栈的性能，但是其难点在1989年被提出[1]。因为无状态连接数据包之间的独立性比较高，数据包之间没有明显的逻辑关系，其使用数据包并行方案可以有效利用并行方法提升性能。但是对于有状态的协议栈，由于数据包之间的耦合度比较高，使用数据包并行方法来处理数据包比较困难。
在国外，Bjorkman在其发表的文章中详细分析了锁对并行协议栈的影响[2]。文章采用共享内存来保存状态，采用加锁的办法来保证数据的一致性。最终得出结论，加锁耗费的时间是影响并行协议栈性能的一个重要因子。对于无状态的协议栈，例如UDP/IP，加锁耗费的时间比较少，对并行化协议栈性能没多大影响。但对于有状态的协议，例如TCP/IP，由于其具有复杂的连接状态，每个线程会频繁访问这些状态，导致加锁的时间比较多，非常影响并行协议栈的性能。
麻省大学的Nahum, Yates等四位学者在x-kernel的基础上研究了UDP和TCP的性能[3]。当采用2个处理器时，UDP的性能呈线性增长，提升大约1.8倍。对于TCP，使用2个处理器，并采用数据包并行方案，其性能几乎没有提升，原因在于加锁耗费过多的资源。当使用4个处理器时，并采用数据包并行方案，其性能可提升1.8倍。当采用连接级的并行方案时，采用2个处理单元，TCP性能也可提升1.8倍。总的来说，采用连接级的并行方案可同时提升TCP、UDP的性能，原因在于连接级并行方案中，各个连接的状态比较独立，可大大减少锁数据的过程。采用数据包并行方案，UDP性能提升很大，TCP几乎没有提升，原因在于数据包并行方案中TCP状态加锁非常耗时。
上述这些研究，主要集中在通过数据包并行来提升单连接性能，还有其它一些研究集中在通过多个连接并行来提高性能。例如GridFTP[4]，其采用多个连接同时收发数据来提升吞吐量，其中每一个连接都运行在独立的处理器上。数据在传给协议栈之前会被分割成好多块，然后传递给指定的处理器上并发送。在接收方，GridFTP对数据包进行重组。BitTorrent协议中客户端也是通过从同一组中的多个peer获取数据，然后进行重组[5]。最终其吞吐量等于每个连接吞吐量之和，有显著提升。但是连接级并行方案存在一些问题，第一，由于多个连接并行访问，这些连接之间会同时竞争网络资源，所以必须提出一种策略来保证公平性。第二，由于数据在发送前后需要进行分片重组，各个连接在访问共享的数据时，必须对数据进行加锁，比较耗费时间。第三，上层应用必须维护各个连接的状态以及采用合理的调度算法来保证连接的并行，最终应用程序的负担会大大增大，稳定性下降。
在国内，北京邮电大学网络技术研究院在用户态上实现基于代理的并行化TCP/IP协议栈[6]。该协议栈只是对代理功能进行裁剪和优化。服务器主要进行数据包的转发，所以在TCP层去除了拥塞控制、流量控制等复杂的处理流程。转发功能使用无锁的Session Table来减少加锁保护，避免了竞争带来的性能下降。并且使用了TCP Splicing机制转发不同连接上的数据包，来避免Socket API带来的冗余TCP协议处理流程，且减少了内存消耗。
清华大学网络技术研究所夏高等人实现了用于高速网络入侵检测系统的并行TCP/IP协议栈[7]。TCP连接表查找函数采用universal Hash函数，并利用SSE指令集中的并行指令来提高计算速度；采用Bloom过滤器减少TCP连接表中的无效连接，提高查找效率；协议栈采用动态库的形式进行实现，通过多次加载动态库可以将单线程程序转换为多线程程序，提高吞吐率。
随着网络技术的不断发展，协议栈加速研究也从没有停止过。尤其高速网络的到来，网络需求也随着表现为高带宽、低延迟、低的主机开销、高吞吐量等特点。但传统协议栈存在上述一些问题，不能满足现有需求，下面详细介绍了有关协议栈加速技术的研究成果。
零拷贝技术可以减少数据复制和共享总线操作的次数，避免了通信数据在存储器之间不必要的中间复制过程，有效地提高通信效率，是设计高速接口通道、实现高速服务器和路由器的关键技术之一[8]。数据复制受制于传统的操作系统或通信协议，限制了通信性能，传统协议栈收发数据包时，都要进行多次复制才能到达链路上或用户空间[9]。采用零拷贝技术，可减少数据复制次数，简化协议处理的层次，在应用和网络间提供更快的数据通路。最终，可以有效地降低通信延迟，增加网络吞吐率。
零拷贝技术在实现的时候，主要使用了内存映射[10]和DMA技术[11]。通常情况下，操作系统是直接可以访问用户态空间的数据；但操作系统内核为了保证其安全性和稳定性，用户态程序是无法直接访问内核空间的数据。一般应用程序需要通过系统调用接口来获取用户态空间的数据。调用相应的系统调用接口，操作系统会临时赋予当前线程最高权限，这是就可以直接访问内核数据，当用户线程的系统调用执行完毕后，会撤销对应的权限。在Linux系统中，其提供了另外一种机制来实现用户程序和内核的内存共享，即内存映射技术。
内存映射有两种方法，第一种方法是将用户空间的内存地址空间映射到内核中，这种方法需要用户程序提前申请一大块地址空间，然后通过内核模块映射到内核态，提供给设备DMA使用。但是这种方式存在一个问题，由于用户态地址是一个虚拟地址，而DMA使用的地址是一个真实物理地址，两者之间存在地址转换问题。当DMA操作内存的时候，必须提供一个映射表供驱动程序将数据填充到用户态所申请的地址空间上。这种方式的好处也显而易见，用户态申请地址的大小不受物理地址的限制，只与虚拟地址空间有关系，所以能申请到一块很大的内存地址空间。
第二种方法是将内核内存地址空间映射到用户态中，这种方式需要内核启动的时候预留一块连续的物理内存空间，供DMA设备使用。然后将这块内存空间通过内核加载模块程序映射到用户程序中。这样就DMA就不需要内存映射表，直接可将数据放入对应的内存地址上。其不足之处则是申请的共享内存大小受限于实际物理内存空间的大小。
LyraNet是基于零拷贝技术实现的一个是网络协议栈，其将用户空间的内存地址映射到内核态中[12]。sk_buff结构如图2.4所示，其描述了数据包大于1460字节时的情况，Linux是将用户数据复制到sk_buff的payload中；而LyraNet是将sk_buff结构体的数据指针直接指向用户空间。最终，LyraNet收发时间只使用了Linux协议栈所需时间的77.64%，性能有所提升。
协议栈硬件加速主要采用了TOE（TCP/IP Offload Engine）技术，即将协议栈的工作卸载到硬件中执行[13]。这种技术利用的硬件执行速度块的优点，将主机CPU解放出来，可以有效减少数据复制、中断操作、协议处理所带来的主机开销，解决了服务器处理瓶颈问题。TOE技术分为部分卸载和完全卸载。
部分卸载是将协议栈的部分工作卸载到硬件中执行。部分卸载不会影响操作系统内核管理机制，其只是完成了协议栈中的某一部分功能，但核心流程还需要主机CPU进行处理，例如TCP建立连接、关闭连接等、状态机的维护等。最常见的部分卸载TOE技术是TCP/IP Checksum Offload，将TCP、IP数据包的校验工作放在物理网卡上进行。接收端可以利用TOE技术将数据包的重组工作交给网卡，让网卡提前将将数据包进行重组，然后再交给协议栈，这样可以减少协议栈中的重组开销，实验表明，在1Gbps网络环境中，可以节省2-7%的CPU开销；在10Gpbs环境中，可以节省20%的CPU开销[14]。
完全卸载将协议栈的所有工作都交给硬件执行，其在实现的时候涉内核对用户线程的管理机制，需要解决TOE网卡对用户地址空间的访问和CPU对用户地址访问的冲突，以及虚拟地址和物理地址的转换问题。而且在实现的时候，需要在网卡驱动和用户层实现一个接口层，以供应用程序调用。完全卸载的性能肯定优于部分卸载方式。但实现难度较大，它涉及内核的线程管理、存储管理等机制的改动，风险较高。
Infiniband技术[15]、RoCE技术[16]以及iWARP技术[17]都采用了TOE技术，都是物理网卡上实现了相应的协议栈。iWARP技术如图2.5所示，将传统的TCP/IP协议栈的所有实现都移到了网卡上，具有以下3个特点[18]:
（1）协议栈加速，通过网卡的处理单元完成了协议栈的所有功能；
（2）避免了数据多次拷贝，其采用了RDMA技术，可直接将数据递交给应用程序线程；
（3）绕过操作系统，减少了系统调用所带来的开销。
虽然TOE技术对协议栈性能有很大帮助，但也存在一些弱点。第一，硬件特殊，需要特定的可编程物理网卡才能实现此技术；第二，价格贵，一般带有TOE的网卡都要比普通网卡贵10倍以上，短时间不能被普通用户接受；第三，扩展性差，由于TOE技术实现的协议栈完全绕过了操作系统内核协议栈，所以扩展性不如软件解决方案，他不支持复杂的防火墙规则、QoS过滤器等；第四，多样性差，TOE实现时候只能采用一种协议栈，常见的是TCP/IP，限制了用户使用。
有关Infiniband、iWARP和RoCE的基本概念可以参看附件中的PPT文档。
由于传统协议栈处理是在内核中进行，多次拷贝以及多次系统调用严重影响协议栈的性能。与TOE方法不同，许多研究开始尝试将协议栈处理提升到用户空间进行。在用户态实现协议栈有以下几点优势[19]。
（1）系统调用次数减少
在传统BSD协议栈中，用户采用系统调用的方式进行相关协议栈的相关操作，系统调用采用软件中断的方式进入内核，每一次调用都伴随着一次用户态与内核态之间的上下文切换，这样频繁切换会带来比较大的开销。在用户态中实现协议栈，可以从根本上解决这一问题，因为协议栈位于用户线程内，不需要进行过多的系统调用。
（2）数据包复制次数减少
在传统内核协议栈中，数据包要从链路上到达用户态需要多次的复制，即数据包从网卡复制到内核空间内，然后数据包经过一系列的协议处理流程，最终数据包将从内核态的缓冲区复制到用户态中的缓冲区。在用户态实现协议栈，可以采用零拷贝技术、可直接将数据包从网卡上拿到用户态中，减少了一次复制次数，在高速网络环境中可以显著降低CPU的开销。
（3）扩展性比较强，易于定制
传统BSD协议栈在设计的时候，主要以稳定性高、通用性强的特点进行设计。但是在特定的需求和环境下，对传统协议栈进行定制，则难度非常大，因为传统协议栈在内核中实现，各个模块之间的耦合度比较高，而且定制的时候，调试、编译工作非常不便。在用户态中实现协议栈，可以很方便的根据用户自己的需求进行扩展和定制，调试编译工作也方便了很多。
Glenford Mapp等人实现了用户空间传输协议A1[20]，不同于TCP协议的字节流传输，A1主要基于块传输，采用选择性重传的数据包传输策略，进行显式的往返时间RTT的测量，其流控是采用端到端的方法，并且支持组播。实验表明，相对于传统TCP的实现，Al的吞吐量有明显的提升。
OpenOnload是Solarflare公司开发的一个在Linux操作系统下开源的、高效的用户态协议栈，其结构如图2.6所示，他在用户态中实现了IP、TCP、UDP等协议，并采用标准的Socket API接口供用户使用，用户可以在不改变现有程序的基础上使用OpenOnload。而且在实现用户态协议栈的时候，采用了专用的网卡及网卡驱动程序，使得是数据包可以很快的到达用户态。OpenOnload具有低延迟、高吞吐量、高速率、低CPU使用率等特点，是一款优秀的用户态协议栈[21]。
4. 一个特例
在2012年6月的USENIX年度技术会议上，意大利比萨大学（Universit`a di Pisa）的Luigi Rizzo教授提出了一种叫做netmap[23]的新高速分组传输方案。针对10Gb/s的高速网卡，在不改动普通的硬件和应用程序的情况下，只需改动少量的FreeBSD代码，在单核900MHz频率下，该方案就能够实现每秒14.88Mpps（packet per second，每个分组64字节）的数据传输速度，也就是7.6Gb/s，其传输速度是普通传输方案的20倍[7]。Rizzo教授的主要贡献是减少或者取消分组在操作系统内部处理的开销，基本思路是：取消每个分组动态分配内存的开销、系统调用开销和内存拷贝大的开销，通过预分配资源、大批处理和零拷贝思想减少了开销，提高了分组在系统内存的周转效率，从而减少延迟，提高了传输速度。这是一个惊人的结果，说明在端系统中数据传输的效率非常低下。具体可以参考附件中Luigi Rizzo教授的文章。
5. 小结
综上所述，可以看出协议栈并发存在的主要问题是处理TCP的连接状态问题，目前的方法都存在缺陷，都一定程度上会降低并发的效率。第二个问题是在核心态并发还是用户态并发，前者相对复杂，设计到操作系统的内核的修改，只能针对开源系统，而后者相对容易。从未来发展的趋势上看，摈弃掉TCP协议和使用TOE技术是主要发展方向，但这需要一个长期的过程。
参考文献
[1] Giarrizzo D, Kaiserswerth M, Wicki T, et al. High-speed parallel protocol implementation.Proceedings of the 1st International Workshop on High-Speed Networks. 1989: 165-180.
[2] Bjorkman M, Gunningberg P. Locking effects in multiprocessor implementations of protocols. Conference proceedings on Communications architectures, protocols and applications. 1993, 13(17): 74-83.
[3] E. M. Nahum, D. J. Yates, J. F. Kurose, and D. Towsley. Performance issues in parallelized network protocols. In Proceedings of the First Symposium on Operating Systems Design and Implementation, November 1994.
[4] Allcock W, Bester J, Bresnahan J, et al. GridFTP: Protocol extensions to FTP for the Grid[J]. Global Grid ForumGFD-RP, 2003, 20.
[5] Cohen B. The BitTorrent protocol specification[J]. 2008.
[6] 张惠慧. 用户态并行化 TCP/IP 协议栈设计与实现[J]. 2010. http://www.paper.edu.cn/index.php/default/releasepaper/content/201011.17
[7] 夏高, 刘斌. 用于高速网络入侵检测系统的并行 TCP/IP 协议栈[J]. 清华大学学报: 自然科学版, 2011, 51(7): 942-948.
[8] 张宇雷, 黄皓. 基于网络处理器的零拷贝技术[J]. 计算机应用研究, 2007, 24(1): 288-290.
[9] 可向民, 龚正虎, 夏建东. 零拷贝技术及其实现的研究[J]. 计算机工程与科学, 2000, 22(5): 17-24.
[10] Jacob B.Mudge T Software-managed address translation,1997.
[11] 刘锋.Linux环境下基于Intel千兆网卡的高速数据包捕获平台的研究[D]．厦门大学硕士学位论文.2008:47-50.
[12] Li Y C, Chiang M L. LyraNET: A zero-copy TCP/IP protocol stack for em[ant]bedded operating systems[C],em[ant]bedded and Real-Time Computing Systems and Applications, 2005. Proceedings. 11th IEEE International Conference on. IEEE, 2005: 123-128.
[13] Yeh E, Chao H, Mannem V, et al. Introduction to TCP/IP offload engine (TOE)[J]. 10 Gigabit Ethernet Alliance (10GEA), 2002.
[14] Makineni S, Iyer R, Sarangam P, et al. Receive side coalescing for accelerating TCP/IP processing[M],High Performance Computing-HiPC 2006. Springer Berlin Heidelberg, 2006: 289-300.
[15] InfiniBand Trade Association. InfiniBand Architecture Specification: Release 1.0[M]. InfiniBand Trade Association, 2000.
[16] RDMA over Converged Ethernet.
[17] http://en.wikipedia.org/wiki/RDMA_over_Converged_Ethernet
[18] Rashti M J, Grant R E, Afsahi A, et al. iWARP redefined: Scalable connectionless communication over high-speed Ethernet[C],High Performance Computing (HiPC), 2010 International Conference on. IEEE, 2010: 1-10.
[19] Optimizing HPC clusters with 10 Gigabit Ethernet iWARP technology.
[20] http://www.intelethernet-dell.com/optimizing-hpc-clusters-with-10-gigabit-ethernet-iwarp-technology/
[21] Thekkath C A, Nguyen T D, Moy E, et al. Implementing network protocols at user level[J]. IEEE/ACM Transactions on Networking (TON), 1993, 1(5): 554-565.
[22] OpenOnload. http://www.openonload.org/
[23] Luigi Rizzo. netmap: a novel fr[ant]amework for fast packet I/O, Proceedings of the 2012 USENIX Annual Technical Conference, June 2012.
https://www.usenix.org/conference/atc12/
[24]
