清華大學(xué)計算機(jī)網(wǎng)絡(luò)ch-在線瀏覽
2025-03-08 08:52本頁面
【正文】 正（ 6） 校驗和計算算法 設(shè) G(x)為 r 階，在 幀的末尾加 r 個 0，使幀為 m + r位，相應(yīng)多項式為 xrM(x)； 按模 2除法用對應(yīng)于 G(x)的位串去除對應(yīng)于 xrM(x)的位串； 按模 2減法從對應(yīng)于 xrM(x)的位串中減去余數(shù)（等于或小于 r位），結(jié)果就是要傳送的帶校驗和的多項式 T(x)。 錯誤檢測和糾正（ 7） 如果只有單比特錯，即 E(x) = xi，而 G(x)中至少有兩項， 余數(shù) (E(x) / G(x)) ? 0，所以可以查出單比特錯； 如果發(fā)生兩個孤立單比特錯，即 E(x) = xi + xj = xj (xij + 1)，假定G(x)不能被 x整除，那么能夠發(fā)現(xiàn)兩個比特錯的充分條件是： xk + 1不能被 G(x)整除 (k ? i j)； 如果有奇數(shù)個比特錯，即 E(x)包括奇數(shù)個項， G(x)選 (x + 1)的倍數(shù)就能查出奇數(shù)個比特錯； 具有 r個校驗位的多項式能檢查出所有長度 ? r 的差錯。 如果突發(fā)差錯長度為 r + 1，當(dāng)且僅當(dāng)突發(fā)差錯和 G(x)一樣時， E(x) / G(x) = 0，概率為 1/2r1。 錯誤檢測和糾正（ 8） 三個多項式已成為國際標(biāo)準(zhǔn) CRC12 = x12 + x11 + x3 + x2 + x + 1 CRC16 = x16 + x15 + x2 + 1 CRCCCITT = x16 + x12 + x5 + 1 CRC32 硬件實(shí)現(xiàn) CRC校驗。 解決辦法：接收方每收到一個幀后，給發(fā)送方回送一個響應(yīng)。 Fig. 310 基本的數(shù)據(jù)鏈路層協(xié)議（ 3） 有噪聲信道的單工協(xié)議（ A Simplex Protocol for a Noisy Channel） 增加約束條件：信道（線路）有差錯，信息幀可能損壞或丟失。 帶來的問題： 什么時候重傳 —— 定時 響應(yīng)幀損壞怎么辦（重復(fù)幀） —— 發(fā)送幀頭中放入序號 為了使幀頭精簡，序號取多少位 —— 1位 發(fā)方在發(fā)下一個幀之前等待一個肯定確認(rèn)的協(xié)議叫做 PAR（ Positive Acknowledgement with Retransmission）或ARQ（ Automatic Repeat reQuest） 基本的數(shù)據(jù)鏈路層協(xié)議（ 4） 工作過程 Fig. 311 注意協(xié)議 3的漏洞 由于確認(rèn)幀中沒有序號，超時時間不能太短，否則協(xié)議失敗。 Fig. 311（與教材不同）的實(shí)現(xiàn)是正確的，確認(rèn)幀有序號 發(fā) 送 接 收 0 0 1 ACK ACK ? 滑動窗口協(xié)議（ 1） 單工 —— 全雙工 捎帶 /載答（ piggybacking）：暫時延遲待發(fā)確認(rèn)，以便附加在下一個待發(fā)數(shù)據(jù)幀的技術(shù)。 本節(jié)的三個協(xié)議統(tǒng)稱滑動窗口協(xié)議，都能在實(shí)際（非理想）環(huán)境下正常工作，區(qū)別僅在于效率、復(fù)雜性和對緩沖區(qū)的要求。發(fā)送窗口的上界表示要發(fā)送的下一個幀的序號，下界表示未得到確認(rèn)的幀的最小編號。接收窗口的上界表示允許接收的序號最大的幀，下界表示希望接收的幀； 接收窗口表示允許接收的信息幀，落在窗口外的幀均被丟棄。接收窗口大小不變。 滑動窗口協(xié)議（ 4） 退后 n幀協(xié)議（ A Protocol Using Go Back n） 為提高傳輸效率而設(shè)計 例： 衛(wèi)星信道傳輸速率 50kbps，往返傳輸延遲 500ms，若傳 1000bit的幀，使用協(xié)議 4，則傳輸一個幀所需時間為： 發(fā)送時間 + 信息信道延遲 + 確認(rèn)信道延遲（確認(rèn)幀很短，忽略發(fā)送時間） = 1000bit / 50kbps + 250ms + 250ms = 520ms 信道利用率 = 20 / 520 ? 4% 一般情況 信道帶寬 b比特 /秒，幀長度 l比特，往返傳輸延遲 R秒，則信道利用率為 (l/b) / (l/b + R) = l / (l + Rb) 結(jié)論 傳輸延遲大，信道帶寬高，幀短時，信道利用率低。 帶來的問題 信道誤碼率高時，對損壞幀和非損壞幀的重傳非常多。 Fig. 315(a) 滑動窗口協(xié)議（ 6） 選擇重傳（ selective repeat） 接收窗口大于 1，先暫存出錯幀的后繼幀； 只重傳壞幀； 對最高序號的幀進(jìn)行確認(rèn)； 接收窗口較大時，需較大緩沖區(qū)。 問題：第二次發(fā)送的 8 個幀成功了還是丟失了？ 退后 n幀重發(fā)； 由于有多個未確認(rèn)幀，設(shè)多個計時器。若一個方向負(fù)載重，另一個方向負(fù)載輕，則協(xié)議阻塞。 基本原理 發(fā)送窗口大小： MaxSeq，接收窗口大?。?(MaxSeq + 1) / 2 保證接收窗口前移后與原窗口沒有重疊； 設(shè) MaxSeq = 7, 若接收窗口 = 7 發(fā)方發(fā) 幀 0 ~ 6，收方全部收到，接收窗口前移（ 7 ~ 5），確認(rèn)幀丟失，發(fā)方重傳幀 0，收方作為新幀接收，并對幀 6確認(rèn)，發(fā)方發(fā)新幀 7 ~ 5，收方已收過幀 0，丟棄新幀 0，協(xié)議出錯。 工作過程 Fig. 318 協(xié)議說明與驗證（ 1） 協(xié)議工程與協(xié)議的形式化描述技術(shù) 協(xié)議工程： 協(xié)議說明（ Protocol Specification） 協(xié)議驗證（ Protocol Verification） 協(xié)議實(shí)現(xiàn)（ Protocol Implementation） 協(xié)議測試（ Protocol Testing） 一致性測試（ Conformance Testing） 互操作性測試（ Interoperability Testing） 性能測試（ Performance Testing） 協(xié)議說明 必須既定義一個協(xié)議實(shí)體提供給它的用戶的服務(wù)，又定義該協(xié)議實(shí)體的內(nèi)部操作。 協(xié)議實(shí)現(xiàn) 用硬件和 /或軟件實(shí)現(xiàn)協(xié)議說明中規(guī)定的功能。 在協(xié)議的說明、驗證、實(shí)現(xiàn)和測試過程中使用形式化描述技術(shù)，不僅可以比較容易地理解協(xié)議，而且可以使協(xié)議描述更加精確，大大簡化了協(xié)議的研究工作。但是目前大多數(shù)協(xié)議還是采用自然語言描述。 形式化描述技術(shù) FDT（ Formal Description Technique） /形式化方法 FM（ Formal Method）廣泛應(yīng)用于協(xié)議工程研究中 協(xié)議說明與驗證（ 4） 一種形式化方法總是以一種形式體系為基礎(chǔ)，只是在具體應(yīng)用時，大都做了便于描述的改進(jìn)和擴(kuò)充。 通信協(xié)議建模 基本出發(fā)點(diǎn)：認(rèn)為通信協(xié)議主要是由響應(yīng)多個“事件”的相對簡單的處理過程組成； 事件 命令（來自用戶） 信息到達(dá)（來自低層） 內(nèi)部超時 協(xié)議說明與驗證（ 6） 優(yōu)點(diǎn)：簡單明了，比較精確； 缺點(diǎn)：對許多復(fù)雜的協(xié)議，事件數(shù)和狀態(tài)數(shù)會劇增，處理困難。 初始狀態(tài)為（ 000） 半雙工信道 Fig. 320 全雙工信道 Fig. 321 協(xié)議說明與驗證（ 7） 協(xié)議驗證 驗證協(xié)議說明是否完整正確，以協(xié)議說明為基礎(chǔ)，涉及邏輯證明。原則上驗證涉及協(xié)議所有可能的狀態(tài)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1