目錄
六、面向連接配接傳輸協定TCP
1、TCP可靠資料傳輸 2、TCP流量控制 3、TCP連接配接管理
七、擁塞控制原理
1、擁塞的成因和代價 2、擁塞控制的方法
八、TCP擁塞控制
1、TCP擁塞控制 2、TCP性能分析
六、面向連接配接傳輸協定TCP
TCP（RFCs-793, 1122, 1323, 2018, 2581）的特點：點對點，一個發送方，一個接收方。可靠的、按序的位元組流。流水線機制，TCP擁塞控制和流量控制機制動态設定視窗尺寸。發送方/接收方緩存。面向連接配接，通信雙方在發送資料之前必須建立連接配接；連接配接狀态隻在連接配接的兩端中維護，在沿途節點中并不維護狀态；TCP連接配接包括兩台主機上的緩存、連接配接狀态變量、socket等；全雙工（full-duplex），同一連接配接中能夠傳輸雙向資料流。
序列号：序列号指的是segment中第一個位元組的編号，而不是segment的編号。建立TCP連接配接時，雙方随機選擇序列号。
ACKs：希望接收到的下一個位元組的序列号。累計确認，該序列号之前的所有位元組均已被正确接收到。
接收方如何處理亂序到達的Segment，TCP規範中沒有規定，由TCP的實作者做出決策。
1、TCP可靠資料傳輸
TCP在IP層提供的不可靠服務基礎上實作可靠資料傳輸服務，流水線機制、累積确認、使用單一重傳定時器。觸發重傳的事件逾時或收到重複ACK。暫不考慮重複ACK、流量控制和擁塞控制。
（1）逾時時間
逾時時間過短，不必要的重傳；過長，對段丢失時間反應慢。設定定時器的逾時時間，大于RTT但RTT是變化的，如何估計RTT？SampleRTT，測量從段發出去到收到ACK的時間，忽略重傳。測量多個SampleRTT，求平均值，形成RTT的估計值EstimatedRTT。指數權重移動平均，典型值0.125。
EstimatedRTT = (1-α)*EstimatedRTT +α*SampleRTT
定時器逾時時間的設定，EstimatedRTT+“安全邊界”，EstimatedRTT變化大則設定較大的邊界（與網絡狀況有關）。測量RTT的變化值，SampleRTT與EstimatedRTT的內插補點。
DevRTT = (1-β)*DevRTT + β*|SampleRTT-EstimatedRTT| (typically,β= 0.25)
TimeoutInterval = EstimatedRTT + 4*DevRTT
（2）TCP發送方
從應用層收到資料，建立Segment，序列号是Segment第一個位元組的編号。開啟計時器， 設定逾時時間TimeOutInterval。
逾時，重傳引起逾時的Segment，重新開機定時器。
收到ACK，如果确認此前未确認的Segment，更新SendBase。如果視窗中還有未被确認的分組，重新啟動定時器。
// TCP發送端程式
NextSeqNum = InitialSeqNum
SendBase = InitialSeqNum
loop (forever) {
switch(event)
event: data received from application above
create TCP segment with sequence number NextSeqNum
if (timer currently not running)
start timer
pass segment to IP
NextSeqNum = NextSeqNum + length(data)
event: timer timeout
retransmit not-yet-acknowledged segment with
smallest sequence number
start timer
event: ACK received, with ACK field value of y
if (y > SendBase) {
SendBase = y
if (there are currently not-yet-acknowledged segments)
start timer
}
} /* end of loop forever */
（3）TCP接收方（RFC1122, 2581）
（4）快速重傳機制
TCP的實作中，如果發生逾時，逾時時間間隔将重新設定，将逾時時間間隔加倍，導緻其很大，重發丢失的分組之前要等待很長時間。Sender會背靠背地發送多個分組，如果某個分組丢失，可能會引發多個重複的ACK，通過重複ACK檢測分組丢失。
如果Sender收到對同一資料的3個ACK，則假定該資料之後的段已經丢失。快速重傳，即在定時器逾時之前進行重傳。
// 快速重傳算法
event: ACK received, with ACK field value of y
if (y > SendBase) {
SendBase = y
if (there are currently not-yet-acknowledged segments)
start timer
} else { // a duplicate ACK for already ACKed segment
increment count of dup ACKs received for y
if (count of dup ACKs received for y = 3) {
resend segment with sequence number y // fast retransmit
}
}
2、TCP流量控制
接收方為TCP連接配接配置設定buffer，上層應用可能處理buffer中資料的速度較慢。流量控制（flow control）指發送方不會傳輸的太多、太快以至于淹沒接收方，導緻buffer溢出，是一種速度比對機制。
假定TCP receiver丢棄亂序的segments，Buffer中的可用空間（spare room） RcvWindow= RcvBuffer-[LastByteRcvd - LastByteRead]。Receiver通過在Segment的頭部字段将RcvWindow告訴Sender，Sender限制自己已經發送的但還未收到ACK的資料不超過接收方的空閑RcvWindow尺寸。
Receiver告知Sender RcvWindow=0，發送方仍可以發送一個很小的段，得到新的RcvWindow資訊，避免RcvWindow為0時即使之後有空閑發送方也不知道。
3、TCP連接配接管理
TCP sender和receiver在傳輸資料前需要建立連接配接，初始化TCP變量（Seq.#、Buffer和流量控制資訊）。通常連接配接發起者是Client，Server等待客戶連接配接請求。
Socket clientSocket = new Socket("hostname","port number");
Socket connectionSocket = welcomeSocket.accept();
TCP連接配接建立過程中采用“三次握手機制（Three way handshake）”。Step 1: client host sends TCP SYN segment to server, specifies initial seq #, no data（SYN标志位置為1表示要建立連接配接、初始序列号）. Step 2: server host receives SYN, replies with SYNACK segment. server allocates buffers, specifies server initial seq. #（配置設定緩存、選擇初始序列号告知用戶端、ACK）.Step 3: client receives SYNACK, replies with ACK segment, which may contain data（與伺服器确認收到了同意建立連接配接的封包段）.
在握手的第二步，伺服器配置設定資源，假如第三次握手的ACK沒有發送至伺服器，伺服器的資源會保留一段時間再釋放。網絡攻擊。
TCP連接配接的關閉Closing a connection，一般由客戶機發起關閉的請求clientSocket.close();。client向server發送TCP FIN控制segment；server收到FIN，回複ACK關閉連接配接，發送FIN；client收到FIN，回複ACK，進入“等待”，如果重複收到FIN，會重新發送ACK；server收到ACK，連接配接關閉。
七、擁塞控制原理
擁塞（Congestion），非正式定義“太多發送主機發送了太多資料或者發送速度太快，以至于網絡無法處理”，表現為分組丢失（路由器緩存溢出）或分組延遲過大（在路由器緩存中排隊）。A top-10 problem。擁塞控制（網絡）vs.流量控制（發送方和接收方）。
1、擁塞的成因和代價
場景一：兩個senders，兩個receivers，A->C，B->D，共享一個路由器。假定鍊路帶寬C，路由器有無限緩存，分組不會丢失沒有重傳。λin發送資料的速率，λout接收資料的速率。
場景二：一個路由器，有限緩存，Sender重傳分組。λ’in原始需要發送的資料加重傳資料，比λin大。
情況a：假設Sender能夠通過某種機制獲知路由器buffer資訊，有空閑才發，不會丢包。λin=λ’in=λout（goodput）。
情況b：丢失後才重發，λ’in>λout。
情況c：分組丢失和定時器逾時後都重發，λ’in變得更大。
擁塞的代價：對給定的“goodput”，要做更多的工作（重傳），造成資源的浪費。
場景三：四個發送方，四個接收方，A->C，C->A，B->D，D->B，四個路由器。多跳，逾時/重傳。
擁塞的另一個代價：多跳網絡中，當分組被drop時，任何用于該分組的“上遊”傳輸能力全都被浪費掉。
2、擁塞控制的方法
端到端擁塞控制：網絡層不需要顯式的提供支援，端系統通過觀察loss、delay等網絡行為判斷是否發生擁塞。TCP采取這種方法。
網絡輔助的擁塞控制：路由器向發送方顯式地回報網絡擁塞資訊，簡單的擁塞訓示（1bit）SNA, DECbit, TCP/IP ECN, ATM，訓示發送方應該采取何種速率。
案例ATM ABR擁塞控制：提供ABR（available bit rate）“彈性服務”，如果發送方路徑負載低（underloaded），使用可用帶寬，如果發送方路徑擁塞，将發送速率降到最低保障速率。發送方發送若幹Data cells發一個RM（resource management）cells，網絡裝置交換機設定RM cell位（網絡輔助），NI bit rate不許增長，CI bit擁塞訓示，RM cells由接收方傳回給發送方。
在RM cell中有顯式的速率（ER）字段，兩個位元組，擁塞的交換機可以将ER置為更低的值（定量），發送方獲知路徑所能支援的最小速率。
資料cell中的EFCI位，擁塞的交換機将其設為1，如果RM cell前面的data cell的EFCI位被設為1，那麼發送方在傳回的RM cell中置CI位。
八、TCP擁塞控制
1、TCP擁塞控制
Sender限制發送速率LastByteSent-LastByteAcked <= CongWin（擁塞視窗）。CongWin根據所感覺到的網絡擁塞，動态調整以改變發送速率，限定已發送但未确認的資料的量。
rate ≈ CongWin/RTT（Bytes/sec）
感覺網絡擁塞：Loss事件（timeout或3個重複ACK），發生Loss事件後，發送方降低速率。
（1）合理地調整發送速率：
加性增-乘性減（AIMD），擁塞避免。逐漸增加發送速率，謹慎探測可用帶寬，直到發生Loss。Additive Increase，每個RTT将CongWin增大一個MSS（最大段長度），擁塞避免；Multiplicative Decrease，發生Loss後将CongWin減半。
慢啟動（SS）。TCP連接配接建立時，CongWin=1，例MSS=500byte，RTT=200msec，初始速率=20k bps，可用帶寬可能遠遠高于初始，希望速率快速增長。當連接配接開始時，指數型增長，每個RTT收到每個ACK将CongWin翻倍。
// Slowstart algorithm
initialize:Congwin=1
for (each segment ACKed)
Congwin++
until (loss event OR CongWin>threshold)
Threshold變量。當CongWin達到Loss事件前值的1/2時，将指數型增長切換為線性增長（擁塞避免）。Loss事件發生時，變量Threshold被設為Loss事件前CongWin值的1/2。
3個重複ACKs，CongWin切到一半，然後線性增長。Timeout事件，CongWin直接設為1個MSS，然後指數增長，達到threshold後再線性增長。3個重複ACKs表示網絡還能夠傳輸一些 segments，timeout事件表明擁塞更為嚴重。
（2）總結
When CongWin is below Threshold, sender in slow-start phase, window grows exponentially. When CongWin is above Threshold, sender is in congestion-avoidance phase, window grows linearly.
When a triple duplicate ACK occurs, Threshold set to CongWin/2 and CongWin set to Threshold. When timeout occurs, Threshold set to CongWin/2 and CongWin is set to 1 MSS.
（3）TCP擁塞控制算法
Th = ? // 設定一個合适的值
CongWin = 1 MSS
/* slow start or exponential increase */
While (No Packet Loss and CongWin < Th) {
send CongWin TCP segments
for each ACK increase CongWin by 1
}
/* congestion avoidance or linear increase */
While (No Packet Loss) {
send CongWin TCP segments
for CongWin ACKs, increase CongWin by 1
}
Th = CongWin/2
If (3 Dup ACKs) CongWin = Th;
If (timeout) CongWin=1;
（4）例題
一個TCP連接配接總是以1 KB的最大段長發送TCP段，發送方有足夠多的資料要發送。當擁塞視窗為16 KB時發生了逾時，如果接下來的4個RTT（往返時間）時間内的TCP段的傳輸都是成功的，那麼當第4個RTT時間内發送的所有TCP段都得到肯定應答時，擁塞視窗大小是多少？
解：threshold=16/2=8 KB，CongWin=1 KB，1個RTT後，CongWin=2 KB，2個RTT後， CongWin=4 KB，3個RTT後，CongWin=8 KB，Slowstart is over；4個RTT後，CongWin=9 KB。
2、TCP性能分析
（1）TCP throughput（吞吐率）
給定擁塞視窗大小和RTT，忽略Slow start，TCP的平均吞吐率是多少？假定發生逾時時CongWin的大小為W，吞吐率是W/RTT；逾時後，CongWin=W/2，吞吐率是W/2RTT。
平均吞吐率為0.75W/RTT。
（2）未來的TCP
假設每個Segment有1500個byte，RTT是100ms，希望獲得10Gbps的吞吐率。throughput = W*MSS*8/RTT, 則W=throughput*RTT/(MSS*8)=83,333。視窗大小為83,333。
吞吐率與丢包率（loss rate, L）的關系：CongWin從W/2增加至W時出現第一個丢包，那麼一共發送的分組數為W/2+(W/2+1)+(W/2+2)+….+W=3W2/8+3W/4。W很大時，3W2/8>>3W/4，是以L≈8/(3W2)=2·10-10。
高速網絡下需要設計新的TCP。
（3）TCP的公平性
公平性指如果K個TCP Session共享相同的瓶頸帶寬R，那麼每個Session的平均速率為R/K。TCP具有公平性。
公平性與UDP：多媒體應用通常不使用TCP，以免被擁塞控制機制限制速率。使用UDP以恒定速率發送，能夠容忍丢失，産生了不公平。研究TCP friendly。
公平性與并發TCP連接配接：某些應用（如Web浏覽器）會打開多個并發連接配接，産生公平性問題。如鍊路速率為R，已有9個連接配接，新來的應用請求1個TCP，獲得R/10的速率，新來的應用請求11個TCP，獲得R/2的速率。