发起一个TCP连接,4元组是必须的,即源IP,源端口,目标IP,目标端口。目标IP和端口都是确定的,源IP根据路由选择或者bind也可以确定,基本上最终的源IP都是本机的IP地址,然而通过IP_TRANSPARENT参数可以bind一个不属于本机的IP地址。唯一麻烦的就是源端口的确定。 在继续深入源端口选择算法之前,必须要认识到一个大的前提,也算是源端口选择算法的一个大的目标,那就是“必须保证TCP四元组的唯一性”!有了这个前提以及终极目标,TCP源端口的选择算法就非常容易理解了。在以下的情况下需要算法来选择一个源端口: 1.调用bind,但是bind的端口是0的时候; 2.没有调用bind,直接调用connect的时候。 这两种情况使不同的,因为在第一种情况下,4元组中的目标IP和目标端口是不确定的,而在第二种情况下,除了源端口,其它的都是知道的。所以两种情况的端口分配算法是不同的。 1.bind情形的列维搜索算法对于bind的情形,由于缺失信息,需要采用非常严格的方式选择源端口,即要做到:只要有可能四元组冲突,就不能分配。比如已经有一个连接的四元组为:Tuple1(IPsrc,PORTsrc,IPdst,PORTdst),现在为一个新建立的套接字bind一个源端口,其不bind任何确定的IP地址,那么它就不能使用PORTsrc这个端口作为源端口,因为它可能和Tuple1冲突,虽然仅仅是可能而已!如下是算法的实现:[plain] view plaincopy
可以看到,算法从一个随机计算出的值为基准端口,然后通过一系列的判断来得到该端口是否可用的信息,一共是两层的判断,如果外层简单判断发现不可用,则递增端口数值重新判断,如果内层复杂判断该端口不可用,则重新计算随机基准端口重新开始。使用这个算法可以很快定位到一个可用的端口。通过算法可以看得出,它符合列维模型,即在更近的局部细致扫描,然后飞跃到一个更远的地方继续列维查找。 实际生活中,这种搜索是很高效的,深夜找宾馆,到一个陌生的城市找工作,警察搜山...信天翁觅食...都是列维搜索! 2.connect情形的精确判定模式connect的时候,四元组中的三元组已经确定,因此可以精确匹配了,和bind时的端口选择相反,此时只要有一个元组不同即可成功,记住我们的目标,即保证TCP四元组的唯一性!确定性的查找不需要列维搜索,而是大家都可以根据顺序递增加简单冲突判定的方式进行端口选择,最合常理的方式就是,每一个三元组(源IP,目标IP,目标端口)都可以有一个65534个端口可供选择,每次递增即可。但是这样的话需要为每一个端口维护一个计数器,Linux使用了更加巧妙的方法,可以采用为每一个三元组用哈希计算一个确定的基准端口,全局维护一个递增的计数器,根据这个计数器与基准端口之和和端口空间大小做模运算,这样的一个取模操作可以确定一个offset,加上最小端口确定一个候选端口,这样就保证了候选端口和三元组的线性关系,也就是说,每一个三元组独立选择端口。 这么做的好处在于,对每一个三元组而言,都是从基准端口开始顺序分配的,相同三元组的端口都集中在一起,因为我们正是要和相同三元组的那些已经确定的端口来比较,以判断有没有冲突,通过这种方式,将相同三元组的已经分配的端口集中在了一起,省去了维护链表的麻烦,只需要从计算出的候选端口开始线性搜索整个端口空间即可,由于全局计数器是递增的,所以除非使用bind占据了某个端口,一般都会很快找到可用端口号,最多搜索几个就能找到。算法如下所示: [plain] view plaincopy
关键点在于,三元组已经确定,剩下的就是根据不同的三元组独立递增端口,效果就是同样三元组的端口都聚集在一起,在无需链表的情况下高效判断! 附:关于列维搜索列维模型其实是一种概率分布模型,和泊松分布大大不同!它更多的体现在一种“生长,聚集”效应上。通俗来讲就是,首先随机确定一个点,然后在该点附近进行遍历搜索,成功后则加入,达到阀值后依然没有找到则退出,再次随机生成一个点,在该点附近搜索,以此类推。这种模型有很精确的数学证明。如果对数学望而却步,可以从生活中体会。刚毕业不久的人,可能会留在一个城市工作,两三年内换了N份工作,接下来突然到达一个陌生的城市,从新开始...这就是列维模型!本质上讲,整个人类文明都是遵循列维模型,一开始原始人从来不知道哪里适合居住,也不知道自己要到哪里去,只是漂泊荡漾,但是过了千百万年以后,我们发现人类的分布并不是平均的,也就是说,有些地方发展成了大都市,有些地方依然没有人烟,这难道说发展成都市的地方自然条件优于没有人烟的地方吗?非也!列维模型在起作用,它正如莫菲法则一样是个真理!列维模型一直都在主宰着我们,并且工作的很好,由于列维模型,我们现在拥有了典型的几个不错的国际化大都市...列维模型正如磁石一样在发挥着作用。它本质上就是要把同类同质的东西聚集在一起!Linux在bind的时候分配端口正是使用这种列维搜索方式。列维模型天生具备一个阀值,即,在由于列维模型聚集在一起的东西超过阀值后,将不再聚集,而是选择“长跳”,即随机到达一个比较远的地方重新开始聚集!列维模型总结起来就是,局部搜索,达到范围阀值后,到一个很远但是随机的地方重新开始局部搜索!如下图所示: |
|