SIP协议实现中消息解析的研究

在满足SIP协议被设计为可灵活扩展的文本协议的要求的基础上,分析了传统SIP消息解析器中基于字符串比较操作来判断消息头字段类型对整体SIP消息解析性能的影响。结合SIP协议栈实现过程中的对可维护性和可扩展性要求,深入研究了逐行解析消息头字段的基本流程和静态查找表的基本工作原理,提出了借助开源工具Gperf自动化构建高效静态查找表以实现头字段类型查询的方法,并实现了SIP消息头类型的快速匹配的目的。该方法改善了SIP消息解析器的性能和扩展性。

一种自适应二级散列算法

计算机70%以上的时间在进行查找工作。传统散列算法[1]具有很好的平均时间复杂性,但最坏时间复杂性为O(k),(k为关键字总数)。完美散列算法查找的时间复杂性一般较小,但插入后解决冲突的最坏时间复杂性均在O(k2)以上。本文结合完美散列算法gperf[2],传统散列算法、平衡树[1]等的优点,提出一种自适应二级散列算法,其查找、插入和删除的最坏时间复杂性远低于O(log2k),接近常数,其最坏空间复杂性为O(k).