基于单向并行多链表的流管理

NetFlow Based on Parallel Single Multi-linked Lists

高速条件下数据访存是流管理的瓶颈,传统表项操作"读-处理-写"模式效率仅为36%,读写转换和读写延时是制约效率的重要因素。针对这个问题,提出了连续读写法处理表项,通过合并读写时延和复用读写转换的方式使表项操作效率超过90%;并在此基础上提出了单向并行多链表法。通过多个链表的交替操作,使连续读写法应用于处理不活动超时流。理论分析和实验表明,单向并行多链表法能够适用于OC-768(40Gbps)链路下管理千万条表项明显优于辅助存储法和双向链表法的OC-192(10Gbps)下百万条表项的管理能力。

In the high speed network, the bottleneck of NetFlow is the memory access. The efficiency of traditional list item operation ＂read-process-write＂ mode is only 36%, and the important factors which restrict the efficiency are read and Write conversion as well as read and write delay. To solve this problem, continuous reading and writing method was proposed. It makes the efficiency of traditional list item operation increase to 90% or more by merging multi-delay and multiplexing read and write conversion. We proposed the parallel single multi-linked list method to handle with the inac- tive timeout flows. Continuous reading and writing method is applied to deal with the inactivity timeout flow through multiple list alternating operation. Theoretical analysis and experimental results show that the parallel single multi- linked list method can be applied in the link OC-768（40Gbps）to manage tens of millions of list items,which is signifi- cantly superior to the management ability of auxiliary storage method and doubly linked list method in the link OC-192 （10Gbps） to manage millions of list items.