HASH GAME - Online Skill Game GET 300

　　HASH技术在SIP服务器中的应用 曹晨 （重庆邮电大学通信与信息工程学院 重庆 400065） 摘要：本文简要介绍了SIP产生的背景以及SIP网络服务器的功能，引出了服务器需要快速查找用户信息的需求，提出了引进HASH技术来解决的两种方案，除留余数法构造HASH函数和二维数组构造HASH函数，通过性能的比较，二维数组构造HASH函数通过空间换时间的方法更能提高服务器的性能。 关键词：SIP，HASH， 除留余数法，二维数组 引言 在目前固网运营商的众多业务中，语音业务毫无疑问是“最大的一块蛋糕”，sip协议作为下一代网络（NGN）的重要协议，基于sip的Voip必定成为新兴运营商抢占语音市场的利器，随着voip技术的普及，sip用户的增加，提高sip网络服务器在大量的数据中查找所需用户信息的速度成为了亟待解决的问题。 网络服务器 为了保证代理服务器能够找到用户位置，SIP用户代理（UA）必须注册到注册服务器(Register Server)上，注册服务器接受来自UA的注册消息，取出其中的位置信息（IP地址、端口和用户名），存储到定位服务器（Location Server）。定位服务器的目的是映射电话号码到IP地址。定位服务器供代理服务器(Proxy Server)使用。当代理服务器接收一个邀请，它将查询定位数据库，找到被叫的IP地址和端口，发送给主叫方,流程如图2-1所示。 图2-1 网络服务器功能模型 REGISTER消息发送到注册服务器，注册成功以后，将发送200 OK应答给电话，表明注册已经成功。每个注册都有一个生命期，超时头字段expire决定注册消息的有效时间。用户代理必须定期刷新注册信息，否则超时以后，注册记录将不可用。 HASH技术的引入 注册服务器各进程在处理REGISTER消息时，要在定位服务器中申请注册用户数据区，将用户数据存储在数据库中，并按索引值id从小到大的顺序依次排列。由于各进程对用户数据的处理是异步过程，就需要根据用户逻辑账号快速查找到该注册用户数据区的索引值，从而定位此注册用户的数据区。 查找的效率直接影响服务器的性能。现有的方法是，对收到的REGISTER消息的后续相关消息进行解码后，以用户逻辑账号为关键字对全部用户数据区进行逐个匹配，即通过将关键字与数据区的各项进行直接比较而达到查找目的，这种处理方法在实时性要求很高的通信系统中显得效率低下。 本文引入HASH技术进行查找，通过对关键字做某种运算后直接确定所要查找的数据区索引值，即以用户的逻辑账号作为关键字，通过HASH函数的运算得到HASH表地址，然后找到对应的注册用户数据区索引值。 HASH方案的设计与实现 HASH函数的构造方法有很多种，但针对具体应用构造HASH函数时，要考虑三个方面的因素：HASH函数的计算要简单，各关键字尽可能均匀地分布在HASH表中，解决不可避免的HASH冲突。 4.1 除留余数法构造HASH函数 本文以1000个数据区为例，用户的逻辑账号是一个十进制的电话号码，采用除留余数法来构造HASH函数，由于注册用户数据区的最大个数是1000，因此需要设定HASH表长m为1000，关键字key对某个不大于m的数p取余后即为HASH地址，为了减少HASH冲突，这里的p也取1000，只有当账号的后3位相同时，才会发生冲突，计算公式如下： 采用链地址法处理HASH冲突，具体的查找原理如图4-1所示。 图4-1 链地址法处理冲突时的哈希表 以查找用户逻辑账号68001的注册用户数据区索引值为例。首先，68001经HASH函数运算后的HASH地址为1，查找相应的HASH表项后，得到第一个注册用户数据区索引值166，比较逻辑账号，正好是68001，否则将继续向下查询，比较372，582的数据区，直到找到逻辑账号为68001的注册用户数据区，否则查找失败。 事实上，在sip注册服务器的实现中，如果用户的逻辑号码不是均匀分布，可以由用户的逻辑账号和REGISTER消息中的全局唯一的CALL-ID值经过某种运算而获得，从而可以减低冲突发生的概率。 4.2 构造新的哈希函数 随着技术的发展，存储空间的容量已经不存在问题，为了进一步提高查找速度，避免冲突，提高sip服务器的性能，可以用空间换时间。以10000个数据区为例，假设用户的逻辑账号即用户名是10000以内的十进制数字，用户名不重复，此处假设只是为了阐释思想，实际情况不以此为限制，但思想是雷同的。 用二维数组作为存放索引值的哈希表，构造两个哈希函数分别是和。N就是哈希表的行数或者列数中较大者，INT（number）是求不大于number的最大整数,FX(X)的作用是求行地址，FY(Y) 的作用是取余数作为列地址。假如在二维数组中查找给定值345，只需要通过,就知道45存放在二维数组中下标为的位置。这样我们就可以不需要进行任何的比较就能在表中找到相应的数据，这种方法可以解决自然数在存储时出现的冲突问题。 用户向OpenSER sip服务器注册，在opensips数据库location表中提取出部分用户注册信息,见表4.1所示,设定表中有10000个数据。 表4.1 OpenSER中用户注册信息列表 id username expires contact … 1 1100 2009-10-10 21:21:57 sip:.141.143:23534 … 2 2505 2009-10-10 20:17:58 sip:.141.2:23534 … 3 302 2009-10-10 22:23:59 sip:.140. 43:23534 … … … … … … 25 504 2009-10-10 21:22:07 sip:.141.25:23534 … 26 3948 2009-10-10 21:20:23 sip:.141.150:23534 … … … … … … 945 8758 2009-10-10 21:21:28 sip:.140.88:23534 … … … … … … 由于有10000个数据，我们可以建立一个的二维表，哈希函数为：和，可以算出如表4.2所示的用户名转地址表。 表4.2 用户名转地址表 id username FX(username)的值 FY(username) 的值 1 1100 11 0 2 2505 25 5 3 302 3 2 … … … … 25 504 5 4 26 3948 39 48 … … … … 345 8758 87 58 … … … … 那么可以建立的二维表如表4.3所示。 表4.3 二维表部分 这个表建立以后，以查询username为504的用户信息为例来阐述查找过程。和，就可以在表中查找下标为（5，4）的数据，找到id为25，这样就可以在location表中找到id为25，username为504的用户信息，查找成功。可见这个哈希表是用来存储关键字所在数据表location中的地址，起了映射的作用，有利于提高服务器的运行速度。 性能分析 对于含有N个记录的表，查找成功时的平均查找长度为 其中为查找表中第i个记录的概率,且，为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字的个数。用此哈希表来查找数据，假设对每个sip用户的查找是等概率的，则为,因为在查找过程中无需与任何关键字进行比较，从而理论上为0，但实际上计算哈希函数需要时间，所以假定为常数C，那么，当N越大，则ASL越小，从而得出此哈希表查找的性能会随着数据量的增加而增加，这对于其他HASH函数是最大的优势。 结束语 本文针对SIP网络服务器需要快速查找用户信息的需求，提出了除留余数法构造HASH函数和二维数组构造HASH函数两种方案，通过性能的比较，二维数组构造HASH函数通过空间换时间的方法更能提高服务器的性能，并且可