【小凡实验室】TCP源端口选择算法与列维模型

小凡实验室

【小凡实验室】TCP源端口选择算法与列维模型

　发起一个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冲突，虽然仅仅是可能而已！如下是算法的实现：
　　#include <stdio.h>
　　#include <stdlib.h>
　　#include <pthread.h>
　　#define LOW     10000
　　#define HIGH    65535
　　//端口分配函数
　　//base:一个（源IP,目标IP,目标端口）三元组的hash值
　　int get_local_port（int base ）
　　{
　　unsigned int i,j,port, remaining;
　　again:
　　remaining = （HIGH - LOW） + 1;
　　//采用随机的方式更容易找到空闲端口
　　port = LOW + random（）%remaining;
　　for （i = 1; i <= remaining; i++） {
　　int port_ok = 0;
　　//判断该端口是否可用，由于四元组唯一性现在由于信息不全无法判断，先检查最容易匹配的：
　　//端口没有处在TW状态，非LISTEN状态，可用
　　//此处要保证的是，聚集者要越往外越少。
　　port_ok = 1;
　　if （port_ok） {
　　goto check_inner;
　　}
　　//如果不合适就以port为基准，递增
　　port ++;
　　}
　　check_inner:
　　{
　　//更深层次，但更耗时的判断
　　int port_inner_ok;
　　port_inner_ok = 1;
　　if （！port_inner_ok） {
　　goto again;
　　}
　　}
　　return port;
　　}
　　//分配端口函数
　　void func（）
　　{
　　while（1） {
　　int port = get_local_port（0）；
　　printf（" %d \n", port）；
　　sleep（1）；
　　}
　　}
　　//main函数
　　int main（int argc, char **argv）
　　{
　　func（）；
　　return 0;
　　}
　　可以看到，算法从一个随机计算出的值为基准端口，然后通过一系列的判断来得到该端口是否可用的信息，一共是两层的判断，如果外层简单判断发现不可用，则递增端口数值重新判断，如果内层复杂判断该端口不可用，则重新计算随机基准端口重新开始。使用这个算法可以很快定位到一个可用的端口。通过算法可以看得出，它符合列维模型，即在更近的局部细致扫描，然后飞跃到一个更远的地方继续列维查找。
　　实际生活中，这种搜索是很高效的，深夜找宾馆，到一个陌生的城市找工作，警察搜山…信天翁觅食…都是列维搜索！


电 话：010-52402129
客服：2209293110
客服QQ1：105878346
客服QQ2：2209293110
QQ群：167067529