Turing
GBN的原理與實現
原理:
GBN是屬於傳輸層的協議,它負責接收應用層傳來的數據,將應用層的數據報發送到目標IP和端口
滑動窗口: 假設在序號空間內，劃分一個長度為N的子區間，這個區間內包含了已經被髮送但未收到確認的分組的序號以及可以被立即發送的分組的序號，這個區間的長度就被稱為窗口長度。（隨著發送方方對ACK的接收，窗口不斷的向前移動，並且窗口的大小是可變的）
GBN一個分組的發送格式是 Base(1Byte) + seq(1Byte) + data(max 1024Byte)
GBN協議的傳送流程是: 從上層應用層獲得到一個完整的數據報,將這個數據報進行拆分(一個GBN數據幀最大傳輸的數據大小限制為1024B,因為在以太網中，數據幀的MTU為1500字節，所以UDP數據報的數據部分應小於1472字節（除去IP頭部20字節與UDP頭的8字節）),如果發送方的滑動窗口中,如果窗口內已經被髮送但未收到確認的分組數目未達到窗口長度,就將窗口剩餘的分組全部用來發送新構造好的數據,剩餘未能發送的數據進行緩存。發送完窗口大小的數據分組後,開始等待接收從接收方發來的確定信息(ACK),GBN協議採取了累積確認，當發送方收到一個對分組n的ACK的時候，即表明接收方對於分組n以及分組n之前的分組全部都收到了。對於已經確認的分組,就將窗口滑動到未確認的分組位置(窗口又有空閒位置,可以發送剩餘分組了),對於未確認的分組,如果計時器超時,就需要重新發送,直到收到接收方的ACK為止。
對於超時的觸發，GBN協議會將當前所有已發送但未被確認的分組重傳，即如果當前窗口內都是已發送但未被確認的分組，一旦定時器發現窗口內的第一個分組超時，則窗口內所有分組都要被重傳。每次當發送方收到一個ACK的時候，定時器都會被重置。
接收方只需要按序接收分組，對於比當前分組序號還要大的分組則直接丟棄。假設接收方正在等待接收分組n，而分組n＋1卻已經到達了，於是，分組n＋1被直接丟棄，所以發送方並不會出現在連續發送分組n，分組n＋1之後，而分組n＋1的ACK卻比分組n的ACK更早到達發送方的情況。
實現:
發送方:
首先定義窗口大小,起始 base 的值, 窗口採用鏈表的數據結構存儲
private int WindowSize = 16;
private long base = 0;
進入一個循環,循環結束條件是所有需要傳送的數據都已經發送完成,並且窗口中的分組都已經全部確認。
在這個循環中,如果窗口內有空餘,就開始發送分組,直到窗口被佔滿,計時器開始計時,之後進入接收ACK的狀態,收到ACK之後,更新滑動窗口的位置,之後如果計時器超時,就將窗口內所有的分組全部重發一次。之後開始下一次循環。
接收方:
不需要有緩存,只需要記錄一個seq值,每成功接收一個數據幀,seq+1,開始循環順序接收數據幀,對於seq不是目標值得數據幀直接丟棄,如果是符合要求的數據幀,就給發送方發送一個ACK=seq的確認數據幀,直到發送方沒有數據傳來為止。
GBN的實現就完成了。
SR協議的原理與實現:
SR協議的原理:
SR協議是在GBN協議的基礎上進行的改進。
對於SR協議來說，發送方需要做到：
為每一個已發送但未被確認的分組都需要設置一個定時器，當定時器超時的時候只發送它對應的分組。
當發送方收到ACK的時候，如果是窗口內的第一個分組，則窗口需要一直移動到已發送但未未確認的分組序號。
對於接收方,需要設置一個窗口大小的緩存,即使是亂序到達的數據幀也進行緩存,併發送相應序號的ACK, 並及時更新窗口的位置,窗口的更新原則同發送方。
SR協議實現:
發送方:
在GBN發送方的基礎上,增加一個基於鏈表數據結構的計時器,對每一個未被確認的分組進行計時。在每次判斷是否超時時,需要對鏈表中所有的計時進行判斷,與GBN重傳不同的是,SR只對超時的那一個分組進行重傳。
發送方完整代碼見gitbub項目中 SR.java中的void send(byte[] content) 函數
接收方:
需要增加一個同發送方的對分組的緩存,用於緩存亂序到達的分組,同樣使用鏈表數據結構。
List datagramBuffer = new LinkedList<>();
首先進入一個循環, 一次循環需要進行如下工作:
接收分組,將分組的數據緩存到datagramBuffer對應的位置(因為到達的數據可能是亂序的)
然後發送數據分組對應seq的ACK,告知發送方自己已經成功接收。 之後更新滑動窗口的位置,更新的規則同發送方一樣。之後進行下一次循環。
直到發送方沒有新的數據傳來,超過接收方設定的最大時間,就結束循環,將接收到的數據拼接成一個完整的Byte數組,傳給應用層。
接收方的完整代碼見github項目中 SR.java中的 ByteArrayOutputStream receive() 函數
SR協議的實現就完成了。
雙向傳輸的實現:
發送方發送數據需要佔用一個固定的端口,而接收方也需要一個固定的端口來向發送方發送 ACK,所以就可以封裝一個完整的協議類,類似於TCP的有連接傳輸一樣,發送方和接收方之間在兩個固定的ip和端口之間進行數據的傳輸,直到雙方的傳輸結束。發送方在使用send()函數進行發送時,也可以同時使用receive()函數進行接收,兩個過程並不衝突,可以同時進行。如果要同時收發,就需要同時開一個發送線程和一個接收線程,兩個線程獨立運行,沒有衝突,這樣就可以實現雙向數據傳輸了。
所以我構造了一個SR class,其中包含的成員變量有:
private InetAddress host;
private int targetPort, ownPort;
private int WindowSize = 16;
private final int sendMaxTime = 2, receiveMaxTime = 4; // max time for one datagram
private long base = 0;
private final int virtualLossRemainder = 17; // this value is used to simulate the loss of the datagram as a remainder
1
2
3
4
5
6
包含的函數有兩個:
void send(byte[] content) // 負責數據的發送
ByteArrayOutputStream receive() // 負責數據的接收
private ByteArrayOutputStream getBytes(List<bytearrayoutputstream> buffer, long max) //負責將接收到的數據分組拼接成一個完整的數據報/<bytearrayoutputstream>
private boolean checkWindow(List<integer> timers) 負責判斷當前的窗口是否可以移動/<integer>
1
2
3
4
詳細的代碼見github項目中SR.java
在Client 主函數中先使用SR協議發送一張圖片, 在Server 主函數中使用SR協議接收這張圖片,並保存。然後向Client發送另一張圖片, Client由發送變成接收。
這有就可以實現雙向文件的發送和接收了。
詳細的代碼見github項目中 Client.java 中 main函數和Server.java中的main函數
模擬丟包
在接收端,設立一個計數變量count, 然後每次收到數據幀就加一,如果count 對一個數取餘=0就不發送ACK,模擬這一分組丟失的情況,然後測試發送方會不會重新發送丟失的分組。
這一部分的代碼實現詳見github項目中 SR.java中 receive中 count這個變量。
