發(fā)起一個TCP連接，4元組是必須的，即源IP，源端口，目標IP，目標端口。目標IP和端口都是確定的，源IP根據(jù)路由選擇或者bind也可以確定，基本上最終的源IP都是本機的IP地址，然而通過IP_TRANSPARENT參數(shù)可以bind一個不屬于本機的IP地址。唯一麻煩的就是源端口的確定。
在繼續(xù)深入源端口選擇算法之前，必須要認識到一個大的前提，也算是源端口選擇算法的一個大的目標，那就是“必須保證TCP四元組的唯一性”！有了這個前提以及終極目標，TCP源端口的選擇算法就非常容易理解了。在以下的情況下需要算法來選擇一個源端口：
1.調(diào)用bind，但是bind的端口是0的時候；
2.沒有調(diào)用bind，直接調(diào)用connect的時候。
這兩種情況使不同的，因為在第一種情況下，4元組中的目標IP和目標端口是不確定的，而在第二種情況下，除了源端口，其它的都是知道的。所以兩種情況的端口分配算法是不同的。

1.bind情形的列維搜索算法

對于bind的情形，由于缺失信息，需要采用非常嚴格的方式選擇源端口，即要做到：只要有可能四元組沖突，就不能分配。比如已經(jīng)有一個連接的四元組為：Tuple1(IPsrc,PORTsrc,IPdst,PORTdst)，現(xiàn)在為一個新建立的套接字bind一個源端口，其不bind任何確定的IP地址，那么它就不能使用PORTsrc這個端口作為源端口，因為它可能和Tuple1沖突，雖然僅僅是可能而已！如下是算法的實現(xiàn)：
#include <stdio.h> #include <stdlib.h> #include <pthread.h>#define LOW 10000 #define HIGH 65535//端口分配函數(shù) //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;//判斷該端口是否可用，由于四元組唯一性現(xiàn)在由于信息不全無法判斷，先檢查最容易匹配的：//端口沒有處在TW狀態(tài)，非LISTEN狀態(tài)，可用//此處要保證的是，聚集者要越往外越少。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; }//分配端口函數(shù) void func() {while(1) {int port = get_local_port(0);printf(" %d \n", port);sleep(1);} }//main函數(shù) int main(int argc, char **argv) {func();return 0; }
可以看到，算法從一個隨機計算出的值為基準端口，然后通過一系列的判斷來得到該端口是否可用的信息，一共是兩層的判斷，如果外層簡單判斷發(fā)現(xiàn)不可用，則遞增端口數(shù)值重新判斷，如果內(nèi)層復雜判斷該端口不可用，則重新計算隨機基準端口重新開始。使用這個算法可以很快定位到一個可用的端口。通過算法可以看得出，它符合列維模型，即在更近的局部細致掃描，然后飛躍到一個更遠的地方繼續(xù)列維查找。
實際生活中，這種搜索是很高效的，深夜找賓館，到一個陌生的城市找工作，警察搜山...信天翁覓食...都是列維搜索！

2.connect情形的精確判定模式

connect的時候，四元組中的三元組已經(jīng)確定，因此可以精確匹配了，和bind時的端口選擇相反，此時只要有一個元組不同即可成功，記住我們的目標，即保證TCP四元組的唯一性！
確定性的查找不需要列維搜索，而是大家都可以根據(jù)順序遞增加簡單沖突判定的方式進行端口選擇，最合常理的方式就是，每一個三元組(源IP，目標IP，目標端口)都可以有一個65534個端口可供選擇，每次遞增即可。但是這樣的話需要為每一個端口維護一個計數(shù)器，Linux使用了更加巧妙的方法，可以采用為每一個三元組用哈希計算一個確定的基準端口，全局維護一個遞增的計數(shù)器，根據(jù)這個計數(shù)器與基準端口之和和端口空間大小做模運算，這樣的一個取模操作可以確定一個offset，加上最小端口確定一個候選端口，這樣就保證了候選端口和三元組的線性關(guān)系，也就是說，每一個三元組獨立選擇端口。
這么做的好處在于，對每一個三元組而言，都是從基準端口開始順序分配的，相同三元組的端口都集中在一起，因為我們正是要和相同三元組的那些已經(jīng)確定的端口來比較，以判斷有沒有沖突，通過這種方式，將相同三元組的已經(jīng)分配的端口集中在了一起，省去了維護鏈表的麻煩，只需要從計算出的候選端口開始線性搜索整個端口空間即可，由于全局計數(shù)器是遞增的，所以除非使用bind占據(jù)了某個端口，一般都會很快找到可用端口號，最多搜索幾個就能找到。算法如下所示：
#include <stdio.h> #include <stdlib.h> #include <pthread.h>#define LOW 10000 #define HIGH 65535static unsigned int hint = 0;//端口分配函數(shù) //base：一個(源IP,目標IP,目標端口)三元組的hash值 int get_local_port(int base ) {unsigned int i,j,port, remaining;unsigned int offset = hint + base;remaining = (HIGH - LOW) + 1;for (i = 1; i <= remaining; i++) {int port_ok = 0;port = LOW + (i + offset) % remaining;//判斷該端口是否可用，由于僅四元組唯一即可接受，現(xiàn)在假設(shè)：//所有的端口均已經(jīng)安全釋放。port_ok = 1;if (port_ok) {break;}}//越過你排除的那幾個(那些！)hint += i;return port; }//hint遞增函數(shù) int inc_hint(int value) {hint += value; }//分配端口線程 void *func(void *arg) {while(1) {int port = get_local_port(0);printf(" %d \n", port);sleep(1);} }//hint遞增線程 void *func_others(void *arg) {while (1) {int rnd = random();//其它的線程選擇源端口的時候，由于使用不同的(源IP，目標IP，目標端口)//不會有任何沖突，因此只模擬遞增hint即可。inc_hint (1);sleep(1);} }//main函數(shù) int main(int argc, char **argv) {pthread_t id[20] = {0};int i = 0, ret = 0;//一個線程不斷分配端口ret = pthread_create(&id[0], NULL, (void*)func, NULL);if (ret) {printf("Create pthread error!/n");return 1;}//N個線程模擬其它的端口分配，僅僅遞增hintfor (i = 1; i < 20; i++) {ret = pthread_create(&id[i], NULL, (void*)func_others, NULL);if (ret) {printf("Create pthread error!/n");return 1;}}for (i = 0; i < 20; i++) {pthread_join(id[i], NULL);}return 0; }
關(guān)鍵點在于，三元組已經(jīng)確定，剩下的就是根據(jù)不同的三元組獨立遞增端口，效果就是同樣三元組的端口都聚集在一起，在無需鏈表的情況下高效判斷！

附：關(guān)于列維搜索

列維模型其實是一種概率分布模型，和泊松分布大大不同！它更多的體現(xiàn)在一種“生長，聚集”效應(yīng)上。通俗來講就是，首先隨機確定一個點，然后在該點附近進行遍歷搜索，成功后則加入，達到閥值后依然沒有找到則退出，再次隨機生成一個點，在該點附近搜索，以此類推。這種模型有很精確的數(shù)學證明。如果對數(shù)學望而卻步，可以從生活中體會。剛畢業(yè)不久的人，可能會留在一個城市工作，兩三年內(nèi)換了N份工作，接下來突然到達一個陌生的城市，從新開始...這就是列維模型！本質(zhì)上講，整個人類文明都是遵循列維模型，一開始原始人從來不知道哪里適合居住，也不知道自己要到哪里去，只是漂泊蕩漾，但是過了千百萬年以后，我們發(fā)現(xiàn)人類的分布并不是平均的，也就是說，有些地方發(fā)展成了大都市，有些地方依然沒有人煙，這難道說發(fā)展成都市的地方自然條件優(yōu)于沒有人煙的地方嗎？非也！列維模型在起作用，它正如莫菲法則一樣是個真理！

列維模型一直都在主宰著我們，并且工作的很好，由于列維模型，我們現(xiàn)在擁有了典型的幾個不錯的國際化大都市...列維模型正如磁石一樣在發(fā)揮著作用。它本質(zhì)上就是要把同類同質(zhì)的東西聚集在一起！Linux在bind的時候分配端口正是使用這種列維搜索方式。列維模型天生具備一個閥值，即，在由于列維模型聚集在一起的東西超過閥值后，將不再聚集，而是選擇“長跳”，即隨機到達一個比較遠的地方重新開始聚集！列維模型總結(jié)起來就是，局部搜索，達到范圍閥值后，到一個很遠但是隨機的地方重新開始局部搜索！如下圖所示：

本文轉(zhuǎn)自 dog250 51CTO博客，原文鏈接:http://blog.51cto.com/dog250/1318982

總結(jié)

以上是生活随笔為你收集整理的TCP源端口选择算法与列维模型的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。