分类: LINUX
2010-03-08 15:26:25
TCP窗口和拥塞控制实现机制
TCP数据包格式
|
Destination port | ||
Sequence Number | |||
Acknowledgement Number | |||
Length |
Reserved |
Control Flags |
Window Size |
Check sum |
Urgent Pointer | ||
Options | |||
DATA | |||
注:校验和是对所有数据包进行计算的。
TCP包的处理流程
接收:
ip_local_deliver
↓
tcp_v4_rcv() (tcp_ipv4.c)→_tcp_v4_lookup()
↓
tcp_v4_do_rcv(tcp_ipv4.c)→tcp_rcv_state_process (OTHER STATES)
↓Established
tcp_rcv_established(tcp_in→tcp_ack_snd_check,(tcp_data_snd_check,tcp_ack (tcp_input.c)
↓ ↓ ↓ ↓
tcp_data tcp_send_ack tcp_write_xmit
↓ (slow) ↓(Fast) ↓
tcp_data_queue tcp_transmit_skb
↓ ↓ ↓
sk->data_ready (应用层) ip_queque_xmit
发送:
send
↓
tcp_sendmsg
↓
__tcp_push_pending_frames tcp_write_timer
↓ ↓
tcp_ retransmit_skb
↓
tcp_transmit_skb
↓
ip_queue_xmit
TCP段的接收
_tcp_v4_lookup()用于在活动套接字的散列表中搜索套接字或SOCK结构体。
tcp_ack (tcp_input.c)用于处理确认包或具有有效ACK号的数据包的接受所涉及的所有任务:
调整接受窗口(tcp_ack_update_window())
删除重新传输队列中已确认的数据包(tcp_clean_rtx_queue())
对零窗口探测确认进行检查
调整拥塞窗口(tcp_may_raise_cwnd())
重新传输数据包并更新重新传输计时器
tcp_event_data_recv()用于处理载荷接受所需的所有管理工作,包括最大段大小的更新,时间戳的更新,延迟计时器的更新。
tcp_data_snd_check(sk)检查数据是否准备完毕并在传输队列中等待,且它会启动传输过程(如果滑动窗口机制的传输窗口和拥塞控制窗口允许的话),实际传输过程由tcp_write_xmit()启动的。(这里进行流量控制和拥塞控制)
tcp_ack_snd_check()用于检查可以发送确认的各种情形,同样它会检查确认的类型(它应该是快速的还是应该被延迟的)。
tcp_fast_parse_options(sk,th,tp)用于处理TCP数据包报头中的Timestamp选项。
tcp_rcv_state_process()用于在TCP连接不处在ESTABLISHED状态的时候处理输入段。它主要用于处理该连接的状态变换和管理工作。
Tcp_sequence()通过使用序列号来检查所到达的数据包是否是无序的。如果它是一个无序的数据包,测激活QuickAck模式,以尽可能快地将确认发送出去。
Tcp_reset()用来重置连接,且会释放套接字缓冲区。
TCP段的发送
tcp_sendmsg()(TCP.C)用于将用户地址空间中的载荷拷贝至内核中并开始以TCP段形式发送数据。在发送启动前,它会检查连接是否已经建立及它是否处于TCP_ESTABLISHED状态,如果还没有建立连接,那么系统调用会在wait_for_tcp_connect()一直等待直至有一个连接存在。
tcp_select_window() 用来进行窗口的选择计算,以此进行流量控制。
tcp_send_skb()(tcp_output.c)用来将套接字缓冲区SKB添加到套接字传输队列(sk->write_queue)并决定传输是否可以启动或者它必须在队列中等待。它通过tcp_snd_test()例程来作出决定。如果结果是负的,那么套接字缓冲区就仍留在传输队列中; 如果传输成功的话,自动传输的计时器会在tcp_reset_xmit_timer()中自动启动,如果某一特定时间后无该数据包的确认到达,那么计时器就会启动。(尚未找到调用之处)(只有在发送FIN包时才会调用此函数,其它情况下都不会调用此函数2007,06,15)
tcp_snd_test()(tcp.h) 它用于检查TCP段SKB是否可以在调用时发送。
tcp_write_xmit()(tcp_output.c)它调用tcp_transmit_skb()函数来进行包的发送,它首先要查看此时TCP是否处于CLOSE状态,如果不是此状态则可以发送包.进入循环,从SKB_BUF中取包,测试是否可以发送包(),接下来查看是否要分片,分片完后调用tcp_transmit_skb()函数进行包的发送,直到发生拥塞则跳出循环,然后更新拥塞窗口.
tcp_transmits_skb()(TCP_OUTPUT.C)负责完备套接字缓冲区SKB中的TCP段以及随后通过Internet协议将其发送。并且会在此函数中添加TCP报头,最后调用tp->af_specific->queue_xmit)发送TCP包.
tcp_push_pending_frames()用于检查是否存在传输准备完毕而在常规传输尝试期间无法发送的段。如果是这样的情况,则由tcp_write_xmit()启动这些段的传输过程。
TCP实例的数据结构
Struct tcp_opt sock.h
包含了用于TCP连接的TCP算法的所有变量。主要由以下部分算法或协议机制的变量组成:
序列和确认号
流控制信息
数据包往返时间
计时器
数据包头中的TCP选项
自动和选择性数据包重传
TCP状态机
tcp_rcv_state_process()主要处理状态转变和连接的管理工作,接到数据报的时候不同状态会有不同的动作。
tcp_urg()负责对紧急数据进行处理
建立连接
tcp_v4_init_sock()(tcp_ipv4.c)用于运行各种初始化动作:初始化队列和计时器,初始化慢速启动和最大段大小的变量,设定恰当的状态以及设定特定于PF_INET的例程的指针。
tcp_setsockopt()(tcp.c)该函数用于设定TCP协议的服务用户所选定的选项:TCP_MAXSEG,TCP_NODELAY, TCP_CORK, TCP_KEEPIDLE, TCP_KEEPINTVL, TCP_KEEPCNT, TCP_SYNCNT, TCP_LINGER2, TCP_DEFER_ACCEPT和TCP_WINDOW_CLAMP.
tcp_connect()(tcp_output.c)该函数用于初始化输出连接:它为sk_buff结构体中的数据单元报头预留存储空间,初始化滑动窗口变量,设定最大段长度,设定TCP报头,设定合适的TCP状态,为重新初始化计时器和控制变量,最后,将一份初始化段的拷贝传递给tcp_transmit_skb()例程,以便进行连接建立段的重新传输发送并设定计时器。
从发送方和接收方角度看字节序列域
如下图示:
snd_una snd_nxt snd_una+snd+wnd rcv_wup rcv_nxt rcv_wup+rcv_wnd 数据以经确认 数据尚未确认 剩余传输窗口 右窗口边界 数据以经确认 数据尚未确认 剩余传输窗口
流控制
流控制用于预防接受方TCP实例的接受缓冲区溢出。为了实现流控制,TCP协议使用了滑动窗口机制。该机制以由接受方所进行的显式传输资信分配为基础。
滑动窗口机制提供的三项重要作业:
分段并发送于若干数据包中的数据集初始顺序可以在接收方恢复。
可以通过数据包的排序来识别丢失的或重复的数据包。
两个TCP实例之间的数据流可以通过传输资信赋值来加以控制。
Tcp_select_window()
当发送一个TCP段用以指定传输资信大小的时候就会在tcp_transmit_skb()方法中调用tcp_select_window()。当前通告窗口的大小最初是由tcp_receive_window()指定的。随后通过tcp_select_window()函数来查看该计算机中还有多少可用缓冲空间。这就够成了哪个提供给伙伴实例的新传输资信的决定基础。
一旦已经计算出新的通告窗口,就会将该资信(窗口信息)存储在该连接的tcp_opt结构体(tp->rcv_wnd)中。同样,tp->rcv_wup也会得到调整;它会在计算和发送新的资信的时候存储tp->rcv_nxt变量的当前值,这也就是通常所说的窗口更新。这是因为,在通告窗口已发送之后到达的每一个数据包都必须冲销其被授予的资信(窗口信息)。
另外,该方法中还使用另一种TCP算法,即通常所说的窗口缩放算法。为了能够使得传输和接收窗口的16位数字运作起来有意义,就必须引入该算法。基于这个原因,我们引入了一个缩放因子:它指定了用以将窗口大小移至左边的比特数目,利用值Fin tp->rcv_wscale, 这就相当于因子为
Tcp_receive_window()(tcp.c)用于计算在最后一段中所授予的传输资信还有多少剩余,并将自那时起接收到的数据数量考虑进去。
Tcp_select_window()(tcp_output.c)用于检查该连接有多少存储空间可以用于接收缓冲区以及可以为接收窗口选择多大的尺寸。
Tcp_space()确定可用缓冲区存储空间有多大。在所确定的缓冲区空间进行一些调整后,它最后检查是否有足够的缓冲区空间用于最大尺寸的TCP段。如果不是这样,则意味着已经出现了痴呆窗口综合症(SWS)。为了避免SWS的出现,在这种情形下所授予的资信就不会小于协议最大段。
如果可用缓冲区空间大于最大段大小,则继续计算新的接收窗口。该窗口变量被设定为最后授予的那个资信的值(tcp->rcv_wnd)。如果旧的资信大于或小于多个段大小的数量,则窗口被设定为空闲缓冲区空间最大段大小的下一个更小的倍数。以这种方式计算的窗口值是作为新接收资信的参考而返回的。
()(tcp_timer.c)是零窗口探测计时器的处理例程。它首先检查同位体在一段较长期间上是否曾提供了一个有意义的传输窗口。如果有若干个窗口探测发送失败,则输出一个错误消息以宣布该TCP连接中存在严重并通过tcp_done()关闭该连接。主要是用来对方通告窗口为0,则每隔定时间探测通告窗口是否有效.
如果还未达到该最大窗口探测数目,则由tcp_send_probe0()发送一个没有载荷的TCP段,且确认段此后将授予一个大于NULL的资信。
Tcp_send_probe0()(tcp_output.c)利用tcp_write_wakeup(sk)来生成并发送零窗口探测数据包。如果不在需要探测计时器,或者当前仍旧存在途中数据包且它们的ACK不含有新的资信,那么它就不会得到重新启动,且probes_out和backoff 参数会得到重置。
否则,在已经发送一个探测数据包后这些参数会被增量,且零窗口探测计时器会得到重新启动,这样它在某一时间后会再次到期。
Tcp_write_wakeup()(tcp_output.c)用于检查传输窗口是否具有NULL大小以及SKB中数据段的开头是否仍旧位于传输窗口范围以内。到目前为止所讨论的零窗口问题的情形中,传输窗口具有NULL大小,所以tcp_xmit_probe_skb()会在else分支中得到调用。它会生成所需的零窗口探测数据包。如果满足以上条件,且如果该传输队列中至少存在一个传输窗口范围以内的数据包,则我们很可能就碰到了痴呆综合症的情况。和当前传输窗口的要求对应的数据包是由tcp_transmit_skb()生成并发送的。
Tcp_xmit_probe_skb(sk,urgent)(tcp_output.c)会创建一个没有载荷的TCP段,因为传输窗口大小NULL,且当前不得传输数据。Alloc_skb()会取得一个具有长度MAX_TCP_HEADER的套接字缓冲区。如前所述,将无载荷发送,且数据包仅仅由该数据包报头组成。
Tcp_ack_probe() (tcp_input.c) 当接收到一个ACK标记已设定的TCP段且如果怀疑它是对某一零窗口探测段的应答的时候,就会在tcp_ack()调用tcp_ack_probe()。根据该段是否开启了接受窗口,由tcp_clear_xmit_timer()停止该零窗口探测计时器或者由tcp_reset_xmit_timer()重新起用该计时器。
拥塞检测、回避和处理
流控制确保了发送到接受方TCP实例的数据数量是该实例能够容纳的,以避免数据包在接收方端系统中丢失。然而,该转发系统中可能会出现缓冲区益处——具体来说,是在Internet 协议的队列中,当它们清空的速度不够快且到达的数据多于能够通过网络适配器得到发送的数据量的时候,这种情况称为拥塞。
TCP拥塞控制是通过控制一些重要参数的改变而实现的。TCP用于拥塞控制的参数主要有:
(1) 拥塞窗口(cwnd):拥塞控制的关键参数,它描述源端在拥塞控制情况下一次最多能发送的数据包的数量。
(2) 通告窗口(awin):接收端给源端预设的发送窗口大小,它只在TCP连接建立的初始阶段发挥作用。
(3) 发送窗口(win):源端每次实际发送数据的窗口大小。
(4) 慢启动阈值(ssthresh):拥塞控制中慢启动阶段和拥塞避免阶段的分界点。初始值通常设为65535byte。
(5) 回路响应时间(RTT):一个TCP数据包从源端发送到接收端,源端收到接收端确认的时间间隔。
(6) 超时重传计数器(RTO):描述数据包从发送到失效的时间间隔,是判断数据包丢失与否及网络是否拥塞的重要参数。通常设为2RTT或5RTT。
(7) 快速重传阈值(tcprexmtthresh)::能触发快速重传的源端收到重复确认包ACK的个数。当此个数超过tcprexmtthresh时,网络就进入快速重传阶段。tcprexmtthresh缺省值为3。
四个阶段
1.慢启动阶段
旧的TCP在启动一个连接时会向网络发送许多数据包,由于一些路由器必须对数据包进行排队,因此有可能耗尽存储空间,从而导致TCP连接的吞吐量(throughput)急剧下降。避免这种情况发生的算法就是慢启动。当建立新的TCP连接时,拥塞窗口被初始化为一个数据包大小(一个数据包缺省值为536或512byte)。源端按cwnd大小发送数据,每收到一个ACK确认,cwnd就增加一个数据包发送量。显然,cwnd的增长将随RTT呈指数级(exponential)增长:1个、2个、4个、8个……。源端向网络中发送的数据量将急剧增加。
2.拥塞避免阶段
当发现超时或收到3个相同ACK确认帧时,网络即发生拥塞(这一假定是基于由传输引起的数据包损坏和丢失的概率小于1%)。此时就进入拥塞避免阶段。慢启动阈值被设置为当前cwnd的一半;超时时,cwnd被置为1。如果cwnd≤ssthresh,则TCP重新进入慢启动过程;如果cwnd>ssthresh,则TCP执行拥塞避免算法,cwnd在每次收到一个ACK时只增加1/cwnd个数据包(这里将数据包大小segsize假定为1)。
3.快速重传和恢复阶段
当数据包超时时,cwnd被设置为1,重新进入慢启动,这会导致过大地减小发送窗口尺寸,降低TCP连接的吞吐量。因此快速重传和恢复就是在源端收到3个或3个以上重复ACK时,就断定数据包已经被丢失,并重传数据包,同时将ssthresh设置为当前cwnd的一半,而不必等到RTO超时。图2和图3反映了拥塞控制窗口随时间在四个阶段的变化情况。
TCP用来检测拥塞的机制的算法:
1、 超时。
一旦某个数据包已经发送,重传计时器就会等待一个确认一段时间,如果没有确认到达,就认为某一拥塞导致了该数据包的丢失。对丢失的数据包的初始响应是慢速启动阶段,它从某个特定点起会被拥塞回避算法替代。
2、 重复确认
重复确认的接受表示某个数据段的丢失,因为,虽然随后的段到达了,但基于累积ACK段的原因它们却不能得到确认,。在这种情形下,通常认为没有出现严重的拥塞问题,因为随后的段实际上是接收到了。基于这个原因,更为新近的TCP版本对经由慢速启动阶段的丢失问题并不响应,而是对经由快速传输和快速恢复方法的丢失作出反应。
慢速启动和拥塞回避
Tcp_cong_avoid() (tcp_input.c)用于在慢速启动和拥塞回避算法中实现拥塞窗口增长。当某个具有有效确认ACK的输入TCP段在tcp_ack()中进行处理时就会调用tcp_cong_avoid()
首先,会检查该TCP连接是否仍旧处于慢速启动阶段,或者已经处于拥塞回避阶段:
在慢速启动阶段拥塞窗口会增加一个单位。但是,它不得超过上限值,这就意味着,在这一阶段,伴随每一输入确认,拥塞窗口都会增加一个单位。在实践中,这意味着可以发送的数据量每次都会加倍。
在拥塞回避阶段,只有先前已经接收到N个确认的时候拥塞窗口才会增加一个单位,其中N等于当前拥塞窗口值。要实现这一行为就需要引入补充变量tp->snd_cwnd_cnt;伴随每一输入确认,它都会增量一个单位。下一步,当达到拥塞窗口值tp->snd_cwnd的时候,tp->snd_cwnd就会最终增加一个单位,且tp->snd_cwnd_cnt得到重置。通过这一方法就能完成线形增长。
总结:拥塞窗口最初有一个指数增长,但是,一旦达到阈值,就存在线形增长了。
Tcp_enter_loss(sk,how) (tcp_input.c)是在重传计时器的处理例程中进行调用的,只有重传超时期满时所传输的数据段还未得到确认,该计时器就会启动。这里假定该数据段或它的确认已丢失。在除了无线网络的现代网络中,数据包丢失仅仅出现在拥塞情形中,且为了处理缓冲区溢出的问题将不得不在转发系统中丢弃数据包。重传定时器定时到时调用,用来计算CWND和阈值重传丢失数据,并且进入慢启动状态.
Tcp_recal_ssthresh() (tcp.h)一旦检测到了某个拥塞情形,就会在tcp_recalc_ssthresh(tp)中重新计算慢速启动阶段中指数增长的阈值。因此,一旦检测到该拥塞,当前拥塞窗口tp->snd_cwnd的大小就会被减半,并作为新的阈值被返回。该阈值不小于2。
快速重传和快速恢复
TCP协议中集成可快速重传算法以快速检测出单个数据包的丢失。先前检测数据包丢失的唯一依据是重传计时器的到期,且TCP通过减少慢速启动阶段中的传输速率来响应这一问题。新的快速重传算法使得TCP能够在重传计时器到期之前检测出数据包丢失,这也就是说,当一连串众多段中某一段丢失的时候。接收方通过发送重复确认的方法来响应有一个段丢失的输入数据段。
LINUX内核的TCP实例中两个算法的协作方式:
▉ 当接收到了三个确认复本时,变量tp->snd_ssthresh就会被设定为当前传办理窗口的一半.丢失的段会得到重传,且拥塞窗口tp->snd_cwnd会取值tp->ssthresh+3*MSS,其中MSS表示最大段大小.
▉ 每接收到一个重复确认,拥塞窗口tp->snd_cwnd 就会增加一个最大段大小的值,且会发送一个附加段(如果传输窗口大小允许的话)
▉ 当新数据的第一个确认到达时,此时tp->snd_cwnd就会取tp->snd_ssthresh的原如值,它存储在tp->prior_ssthresh中.这一确认应该对最初丢失的那个数据段进行确认.另外还应该确认所有在丢失数据包和第三个确认复本之间发送的段.
TCP中的计时器管理
Struct timer_list
{ struct timer_head list;
unsigned long expires;
unsigned long data;
void (*function) (unsighed long);
volatile int running;
}
tcp_init_xmit_timers()(tcp_timer.c)用于初始化一组不同的计时器。Timer_list会被挂钩进来,且函数指针被转换到相应的行为函数。
Tcp_clear_xmit_timer()(tcp.h)用于删除timer_list结构体链表中某个连接的所有计时器组。
Tcp_reset_xmit_timer(sk,what,when)(tcp.h)用于设定在what到时间when中指定的计时器。
TCP数据发送流程具体流程应该是这样的:
tcp_sendmsg()----->tcp_push_one()/tcp_push()----
| |
| \|/
|--------------->__tcp_push_pending_frames()
|
\|/
tcp_write_xmit()
|
\|/
tcp_transmit_skb()
tcp_sendmsg()-->__tcp_push_pending_frames() --> tcp_write_xmit()-->tcp_transmit_skb()
write_queue 是发送队列,包括已经发送的但还未确认的和还从未发送的,send_head指向其中的从未发送之第一个skb。 另外,仔细看了看tcp_sendmsg(),觉得它还是希望来一个skb 就发送一个skb,即尽快发送的策略。
有两种情况,
一,mss > tp->max_window/2,则forced_push()总为真,这样, 每来一个skb,就调用__tcp_push_pending_frames(),争取发送。
二,mss < tp->max_window/2,因此一开始forced_push()为假, 但由于一开始send_head==NULL,因此会调用tcp_push_one(), 而它也是调用__tcp_push_pending_frames(),如果此时网络情况 良好,数据会顺利发出,并很快确认,从而send_head又为NULL,这样下一次数据拷贝时,又可以顺利发出。这就是说, 在网络情况好时,tcp_sendmsg()会来一个skb就发送一个skb。
只有当网络情况出现拥塞或延迟,send_head不能及时发出, 从而不能走tcp_push_one()这条线,才会看数据的积累,此时, 每当数据积累到tp->max_window/2时,就尝试push一下。
而当拷贝数据的总量很少时,上述两种情况都可能不会满足,
这样,在循环结束时会调用一次tcp_push(),即每次用户的完整
一次发送会有一次push。
TCP包接收器(tcp_v4_rcv)将TCP包投递到目的套接字进行接收处理. 当套接字正被用户锁定, TCP包将暂时排入该套接字的后备队列(sk_add_backlog). 这时如果某一用户线程企图锁定该套接字(lock_sock), 该线程被排入套接字的后备处理等待队列(sk->lock.wq). 当用户释放上锁的套接字时(release_sock), 后备队列中的TCP包被立即注入TCP包处理器(tcp_v4_do_rcv)进行处理, 然后唤醒等待队列中最先的一个用户来获得其锁定权. 如果套接字未被上锁, 当用户正在读取该套接字时, TCP包将被排入套接字的预备队列(tcp_prequeue), 将其传递到该用户线程上下文中进行处理.
TCP定时器(TCP/IP详解2)
TCP为每条连接建立七个定时器:
1、 连接建立定时器在发送SYN报文段建立一条新连接时启动。如果没有在75秒内收到响 应,连接建立将中止。
当TCP实例将其状态从LISTEN更改为SYN_RECV的时侯就会使用这一计时器.服务端的TCP实例最初会等待一个ACK三秒钟.如果在这一段时间没有ACK到达,则认为该连接请求是过期的.
2、 重传定时器在TCP发送数据时设定.如果定时器已超时而对端的确认还未到达,TCP将重传数据.重传定时器的值(即TCP等待对端确认的时间)是动态计算的,取决于TCP为该 连接测量的往返时间和该报文段已重传几次.
3、 延迟ACK定时器在TCP收到必须被确认但无需马上发出确认的数据时设定.TCP等 待时间200MS后发送确认响应.如果,在这200MS内,有数据要在该连接上发送,延迟的ACK响应就可随着数据一起发送回对端,称为稍带确认.
4、 持续定时器在连接对端通告接收窗口为0,阻止TCP继续发送数据时设定.由于连接对端发送的窗口通告不可靠,允许TCP继续发送数据的后续窗口更新有可能丢失.因此,如果TCP有数据要发送,但对端通告接收窗口为0,则持续定时器启动,超时后向对端发送1字节的数据,判定对端接收窗口是否已打开.与重传定时器类似,持续定时器的值也是动态计算的,取决于连接的往返时间,在5秒到60秒之间取值.
5、 保活定时器在应用进程选取了插口的SO_KEEPALIVE选项时生效.如果连接的连续空闲时间超过2小时,保活定时器超时,向对端发送连接探测报文段,强迫对端响应.如果收到了期待的响应,TCP确定对端主机工作正常,在该连接再次空闲超过2小时之前,TCP不会再进行保活测试,.如果收到的是其它响应,TCP确定对端主要已重启.如果连纽若干次保活测试都未收到响应,TCP就假定对端主机已崩溃,尽管它无法区分是主机帮障还是连接故障.
6、 FIN_WAIT-2定时器,当某个连接从FIN_WAIT-1状态变迁到FIN_WAIN_2状态,并且不能再接收任何数据时,FIN_WAIT_2定时器启动,设为10分钟,定时器超时后,重新设为75秒,第二次超时后连接被关闭,加入这个定时器的目的为了避免如果对端一直不发送FIN,某个连接会永远滞留在FIN_WAIT_2状态.
7、 TIME_WAIT定时器,一般也称为2MSL定时器.2MS指两倍MSL.当连接转移到TIME_WAIT状态,即连接主动关闭时,定时器启动.连接进入TIME_WAIT状态时,定时器设定为1分钟,超时后,TCP控制块和INTERNET PCB被删除,端口号可重新使用.
TCP包含两个定时器函数:一个函数每200MS调用一次(快速定时器);另一个函数每500MS调用一次.延迟定时器与其它6个定时器有所不同;如果某个连接上设定了延迟ACK定时器,那么下一次200MS定时器超时后,延迟的ACK必须被发送.其它的定时器每500MS递减一次,计数器减为0时,就触发相应的动作.