3.4 负载均衡机的表和算法设计数据包的分发有很多算法，本文对数据包的分发采用了两种方式，一种是hash函数散列法，一种是通过在表中建立数据包和检测机的映射关系。 3.4.1 Hash函数介绍哈希函数又叫散列函数，它是一种能把关键字映射成记录存贮地址的函数 。 1)散列函数的构造方法
散列函数的选择有两条标准：简单和均匀。 简单指散列函数的计算简单快速；均匀指对于关键字集合中的任一关键字，散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说，散列函数能将子集K随机均匀地分布在表的地址集{0，1，…，m-1}上。
2)常用散列函数 1平方取中法 具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。
2除余法
该方法是最为简单常用的一种方法。它是以表长m来除关键字，取其余数作为散列地址，即 h(key)=key％m。该方法的关键是选取m。选取的m应使得散列函数值尽可能与关键字的各位相关。m最好为素数。
3相乘取整法
该方法包括两个步骤：首先用关键字key乘上某个常数A(0<A<1)，并抽取出key.A的小数部分；然后用m乘以该小数后取整。即：
该方法最大的优点是选取m不再像除余法那样关键。比如，完全可选择它是2的整数次幂。虽然该方法对任何A的值都适用，但对某些值效果会更好。Knuth建议选取 A≈ )/2=0.61603398 87…
该函数的C代码为：
int Hash(int key){
double d=key *A； //不妨设A和m已有定义
return (int)(m*(d-(int)d))；//(int)表示强制转换后面的表达式为整数
}
4随机数法
选择一个随机函数，取关键字的随机函数值为它的散列地址，即h(key)=random(key)其中random为伪随机函数，但要保证函数值是在0到m-1之间。
5数字分析法
设有n个d位数，每一位可能有 r 种不同的符号。这 r 种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布均匀些，每种符号出现的几率均等; 在某些位上分布不均匀，只有某几种符号经常出现。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。
6基数转换法
将关键码值看成另一种进制的数再转换成原来进制的数，然后选其中几位作为散列地址。
7折叠法
有时关键码所含的位数很多，采用平方取中法计算太复杂，则可将关键码分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列地址，这方法称为折叠法。
8ELFhash字符串散列函数
ELFhash函数在UNIX系统V 版本4中的“可执行链接格式”( Executable and Linking Format，即ELF )中会用到，ELF文件格式用于存储可执行文件与目标文件。ELFhash函数是对字符串的散列。它对于长字符串和短字符串都很有效，字符串中每个字符都有同样的作用，它巧妙地对字符的ASCII编码值进行计算，ELFhash函数对于能够比较均匀地把字符串分布在散列表中。 3.4.2 散列法与其他查找方法的区别除散列法外，其他查找方法有共同特征为：均是建立在比较关键字的基础上。其中顺序查找是对无序集合的查找，每次关键字的比较结果为"="或"!="两种可能，其平均时间为O(n)，表的查找就是这种方法；其余的查找均是对有序集合的查找，每次关键字的比较有"="、"<"和">"三种可能，且每次比较后均能缩小下次的查找范围，故查找速度更快，其平均时间为O(lgn)。而散列法是根据关键字直接求出地址的查找方法，其查找的期望时间为O(1)。 由此可得知，散列法和表映射法，相比较而言，散列法查找的效率高，所以说，本文对数据分流所采取的是一散列法为主，表映射法为辅，一般情况下用散列法对数据流进行分发，特殊情况下如检测机负载较重的情况下建立表映射，用表映射法对数据流进行分发。散列法本文采用的是除余法。 3.4.3 负载均衡机中表的算法负载均衡功能由TCP负载均衡机和UDP负载均衡机完成，两种负载均衡机由于接收的数据包不一样，算法也略有不同，但两者都要维持同样的两个表，数据流向表（表3.2）和检测模块状态表（表3.3）。 3.4.3.1 数据流向表的TTL值更新表3.2 数据流向表 | 六元组（四元组） | 直接输出检测机号 | 生存周期(TTL) | 在网络中，由于各种原因，可能存在不完整的TCP连接会话和UDP流，这些空连接会话和无效的UDP包头在数据流向表中会增加查找表的时间，因此我们引入了生存周期（TTL），TTL初始值是3 。规定若TTL<0，则认为此TCP连接是不完整TCP连接，无效的UDP数据流，将在表2中删除此记录。以时间间隔 进行更新表的算法，算法如下： for(第一条记录;没有到表结尾;移至下一条记录) { TTL的值减去 ； if（TTL的值<0） 删除该记录； } 3.4.3.2 数据流向表六元组的hash函数传统上采用五元组定义流:协议、源IP（32bit）（SIP）、目的IP（32bit）（DIP）、源端口(16bit)(SPT)、目的端口(16bit)(DPT),由于网络中70%以上的流量为TCP流量，协议字段中信息量很小，因此本文不考虑将协议字段作为哈希算法的输入参数，两个IP字段分成前16bit源IP（BSIP）、后16bit源IP（ASIP）、前16bit源IP(BDIP)和后16bit目的IP(ADIP),研究一个哈希算法H，哈希算法以16bit串的六元组为输入，一个16bit串的哈希位(hashID)为输出.16bit的伪随机哈希位可以保证抽样精度达到 | 
