TCP会话重组.doc

TCP 重组数据包分析
参照TCP/IP详解第二卷24~29章，详细论述了TCP协议的实现，大概总结一下TCP如何向应用层保证数据包的正确性、可靠性，即TCP如何实现对数据报文的重组。
首先要设计两个报文队列，一个存放正常来到的报文，一个存放失序到来的报文。
比如正常报文队列最后一个报文数据如下：
报文数据段第一字节的序号
数据报长度
seq1=100
len1=100

下一个来到的报文可能有多种情况，现依次分析如下：
1）正常报文
seq2=200
len2=200
seq2 = seq1+len1
由此报文的seq可知，这个报文携带数据序号200~399，正是上一个报文的预期后续报文，将此报文追加到正常报文队列。
2）完全重复报文
seq2=100
len2=100
seq2 ==seq1 而且len2==len1
这个报文携带数据序号100~199，与上一个报文携带的数据序号100~199完全一样，即完全重复，所以应该丢弃这个报文。
3）重复子报文
seq2=100
len2=50
seq2 ==seq1 而且len2<len1
这个报文携带数据序号100~149，说明这是上一个报文的一部分，所以应该丢弃这个报文。
注：第二、三这两种情况可以合并，即seq2 ==seq1 而且len2<=len1，这里分别列出只是为了说明各种不同情况。
4）部分重复报文情况一
seq2=150
len2=30
seq2>seq1而且seq2<seq1+len1而且seq2+len2<=seq1+len1
即这个报文携带序号150~179，这个序号段被包含在上一个报文段中（100~199），所以应该丢弃这个报文。
5）部分重复报文情况二
seq2=150
len2=100
seq2>seq1而且seq2<seq1+len1而且seq2+len2>seq1+len1
即这个报文携带序号150~249，这个序号段前一部分150~199被包含在上一个报文段（100~199）中，后一部分200~249是新的数据，此时应该对这个报文作如下处理：
A. 计算重复字节数
(seq1+len1) - Seq2= 100+100-150 = 50
即这个报文段前50个字节是重复的。
B. 截取报文段新数据
丢弃这个报文段的前50字节，截取后面的新数据，即只保留字节序号段200~249。
C. 重新设置这个报文段的seq
seq2 = seq2+50 = 150+50 = 200
D. 重新设置这个报文段的数据长度
len2 = len2-50 =100-50=50
E. 重新设置后报文段如下
seq2=200
len2=50
即现在这个报文段携带数据序号200~249，正好是上一个报文的后续报文，现在可以将其作为正常报文追加到正常报文队列。
6）提前到达的报文
seq2=300
len2=100
seq2>seq1+len1
这个报文段携带序号300~399的数据，即不是上一个报文100~199的后续报文，而是提前到来的报文，此时应该将这个报文放置到失序报文队列存储起来，以备后续重组使用。
这样直到tcp断开这个socket的链接（FIN=1），此时将正常报文队列和失序报文队列中的数据合并起来，完成重组。
如何判断一个TCP会话结束：
count计数器：表示当前链表中的所有tcp数据段数据部分的长度之和。每当在该链表中加入一个新tcp数据段时，将count累加上该tcp数据段的数据部分的长度。
syn_seq：表示本次tcp连接的第一个数据包的顺序号，也就是建立tcp连接时的第一次握手的SYN包的顺序号。
fin_seq：表示本次tcp连接的最后一个数据包的顺序号，也就是关闭tcp连接时的第二个FIN包的顺序号。
判断：当(fin_seq - syn_seq)与count相等时，就说明tcp数据段已经到齐，否则就是没有到齐。

在以太网络环境中, 任意时刻可能同时存在成百上千的TCP连接. 对于一个新到达的报文, 必须尽可能快地定位并交付给对应的链接. 由于TCP链接数量过多,若采用线性遍历的方式会在定位TCP链接时浪费大量的时间, 无法满足高流量的网络环境的应用. 因此,我们使用哈希表对TCP链接节点进行管理. 对于任意一个TCP链接, 都存在一个唯一的四元组: <源IP地址,目的IP地址,源端口,目的端口>,以其作为参数构造hash函数。
Hash函数的构造是关键，下面是参考的设计方案：
Hash表采用线性最近访问优先表来处理冲突.
由于TCP流重组要求属于同一个TCP连接的数据包必须映射到同一表项.

四元组标识<SIP,DIP,SPT,DPT>.

以上只是如何在成千上万个TCP会话中找到特定的一个TCP会话，详细流程如下：

找到一个特定的TCP会话之后，就要对单个TCP会话进行重组了。

如果采用HASH表来管理多个TCP会话，其处理冲突的方式采用的是链表，对于那些失序到来的数据包，只需根据数据包的序列号在链表中进行插入处理，但对于重复的数据包（包括全部重复和部分重复的数据包），就需要根据序列号和数据段的长度进行数据包相应字段的抛弃。

论文《数据流重组中Hash-Splay查找算法》中比较了网络数据包重组中可应用的查找算法，并提出一种Hash-Splay查找算法，按照论文中的说法，该算法的整体效率最高，这种算法和上述所讲的算法差别在于对特定会话的TCP数据段的组织不同，一个是采用链表来处理HASH冲突，一个是采用Splay树来处理HASH冲突。