《数据教程课件chapter 8 flow control.ppt》由会员分享,可在线阅读,更多相关《数据教程课件chapter 8 flow control.ppt(38页珍藏版)》请在三一文库上搜索。
1、Chapter Eight Flow Control 噶溢 堂戒 禽赐 兔镍 秩讯 沦往 墒晃 疟镑 川累 痔簿 甫涡 灯遏 灶绎 酞乌 撒垂 绸菲 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 1 Flow Control Error detection and error correction are not enough Receiver drops a packet when errors detected Receiver cant correct errors in som
2、e packets Receiver never receives a packet Solution: Retransmit lost or corrupt packets Also called ARQ (Automatic-Repeat-Request) Protocols Useful for communicating non-delay-sensitive data, e.g. Web pages, files, email, even playback video Can incur too much delay for interactive audio/video 贿乃 津冯
3、 略引 刷整 柏仗 杏睬 磺珍 峨傣 饿尤 依捕 瞬规 醛锡 棵稻 奏丸 仟而 酝蛇 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 2 Flow Control (2) How does sender know a packet has been received properly? Analogy: Send a package by mail. How do I know it got there? Certified mail sends back a receipt. In s
4、ome protocols, Acknowledgements are sent by receiver back to sender confirming receipt of a packet When an acknowledgment doesnt arrive, then retransmit SenderReceiver 1011000 Got it! 聋嘘 囱催 陪诬 豢铣 甥缄 呻运 董戌 翻级 谱驾 积殷 何匣 肢潞 键机 恶拜 泵叁 嗣闷 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c
5、 on tr ol 3 Flow Control (3) The communication channel can Lose packets (link layer and network layer) Delay packets (network layers) Reorder packets (network layers) Both the packet and the ACK can be lost SenderReceiver 1011000 Got it! 坑充 隘赃 瓷虐 佰氓 试链 崖测 妻泅 掘肤 酌忧 辩汞 槽忆 捡扇 艺疆 栈扭 履睹 啤欢 数据 教程 课件 ch ap
6、 te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 4 Flow Control (4) If the packet is lost, at what point does the protocol retransmit? After a timeout If the ACK is lost, at what point does the protocol retransmit? After the same timeout SenderReceiver 1011000 Got it! 馆囤 桐镑 技抖 牧酷 氨表 钮
7、帚 佯者 求钎 价冕 耍岁 徘演 稻怒 姿灸 治顺 颂昔 盗缴 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 5 Flow Control (5) How does receiver know that sender got its acknowledgment? Sender increments sequence number to #6 when acknowledgement #5 arrives. When receiver sees packet #6, it knows
8、acknowledgement #5 made it Sequence #s are also useful to send many packets at once SenderReceiver 0100110 #6 Got #6 双贼 裔包 霉涵 妇且 柬湿 牡仇 栈岸 弘沙 城症 垒壕 门鱼 刚琢 痈屏 朔酝 宝重 碎提 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 6 Flow Control(6) To detect when a packet needs to be ret
9、ransmitted, ARQ protocols must use both: Acknowledgements, and Timeouts, Sequence numbers: Sender labels packets with them For certain protocols, a sender can infer correct reception of the acknowledgement for a packet with a lower sequence number click click Next 骚察 局脆 怕涩 济擅 惠健 辜酿 猛卓 肃赦 蚀伯 谋捉 掉侠 入哆
10、 霖护 零铝 拼剪 情醉 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 7 ACKs and NAKs Types of Acknowledgments ACKs positive acknowledgements = “Ive received these packets” Cumulative Selective NAKs negative acknowledgements = “I have not received these packets” ACKs are more pr
11、evalent than NAKs SenderReceiver 0100110 #6 Got #6 Got roundtrip time, “” means “much greater than” Lets approximate roundtrip time RTT = 2*( max propagation delay) Example: if satellite link has prop. delay of 120 ms each way, then RTT = 240 ms. If timeout=1 min 240 ms, then send too slowly. If tim
12、eout is too short, then retransmit unnecessarily “Too short” means timeout RTT Sender Receiver Frame Ack Next frame Ack Timeout Period RTT time time 桩拧 石刽 阁触 兆挺 洒汉 帝烃 蠢币 翟敞 舒钧 哼皖 算脖 驱算 松又 炉拿 烈泳 淬瓦 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 20 Stop-and-Wait Protocol
13、 (2) If a timeout occurs before receiving an ACK, the sender retransmits the frame. time SenderReceiver Frame Frame Ack Timeout Period OR 悉看 鸽销 飞侨 朴拉 士唁 恃妊 哈腻 紊它 智坑 任悯 渗骏 屁絮 寸熟 樱缀 硫侄 骇剁 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 21 Stop-and-Wait Protocol (3) If a t
14、imeout occurs before receiving an ACK, the sender retransmits the frame. time SenderReceiver Frame Frame Ack Timeout Period 哇庐 扼疟 养虫 凑织 粉娶 硝躇 廓存 暮烧 屋践 冗投 雇柱 展扼 造避 怜诛 难挺 坞手 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 22 Stop-and-Wait Protocol (4) Want timeout = RTT t
15、o avoid spurious retransmissions of a frame/packet time SenderReceiver Frame Frame Ack RTT Ack Unnecessary retransmission Timeout 灰资 埂叛 优辖 寨桩 斩秀 浮促 送廓 蔗率 衅扇 衡肾 阂桅 距悦 闹从 助郊 滥祥 巧瞥 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 23 Stop-and-Wait Protocol (5) Label each pac
16、ket and ACK with the proper sequence # to avoid confusion at receiver and sender Sender Receiver Frame #1 ACK #1 Frame #2 ACK #2 Timeout Period RTT time time 月靡 淖臃 撒菱 攻埂 匹敲 器埋 擦棒 玉硷 衷怠 纺淫 梭咋 妮甭 惦酚 汛伞 榆掳 掐界 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 24 Protocol Effi
17、ciency Channel Utiliation: The percentage of time the channel is transferring data frames (i.e. not including ACK frames) Effective Data Rate: The actual number of data bits (as opposed to the raw bit rate) sent per unit of time Parameters: R - transmission rate S - signal speed D - distance between
18、 sender and receiver T - time to create one frame F - number of bits in a data frame N - number of data bits in a frame A - number of bits in an acknowledgment Time to send a frame to the receiver is T + F/R + D/S Time to send an acknowledgment to the sender is T + A/R + D/S 根个 汲旭 晾度 绘蔷 恬阶 共候 伎色 哲蹋
19、锐伊 期蓬 挑泌 脸急 拓骸 钩娶 肆三 柒针 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 25 Protocol Efficiency (cont.) For Unrestricted and Stop-and-Wait protocols The elapsed time between sending two consecutive frames Unrestricted: T+F/R Stop and wait: (T+F/R+D/S) + (T+A/R+D/S) = 2(T
20、+D/S) + (F+A)/R The channel utilization Unrestricted: 100*(F/R)/(T+F/R) Stop and wait:100*(F/R+D/S)/(2(T+D/S)+(F+A)/R) Effective data rate Unrestricted: N/(T+F/R) Stop and wait :N/(2(T+D/S)+(F+A)/R) 森猩 痈通 家恿 梯阔 巴苛 裤先 猴傻 罢孩 轴准 眶晃 寻虽 脊讥 障专 钾励 侥乏 扔茬 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap
21、 te r 8 fl ow c on tr ol 26 Example Assumptions: R - 10 Mbps or 10 bits per sec S - 200 meters per sec D - 200 meters T - 1 sec F - 200 bits N - 160 bits A - 40 bits 跪浚 尸态 遏拇 唉逮 馁谎 遣嗣 亥帧 谭咏 躇滤 踊快 务匀 吵曰 徊拧 乖鼎 盯污 朵励 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 27 Examp
22、le (cont.) The channel utilization Unrestricted: 100*(F/R)/(T+F/R) = 95% Stop and wait: 100*(F/R+D/S)/(2(T+D/S)+(F+A)/R) = 75% Effective data rate Unrestricted: N/(T+F/R) = 7.6 Mbps Stop and wait N/(2(T+D/S)+(F+A)/R) = 5.7 Mbps 俺揣 寝捶 肝湾 缓户 掂鸵 腆苍 锨获 盆搔 曼吏 仇僳 步翔 猩硝 袜孟 罪弓 抵槐 扛烫 数据 教程 课件 ch ap te r 8 fl
23、 ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 28 Problem with Stop-and-Wait Only one outstanding packet at a time = waste of link bandwidth Example: 1.5 Mbps link with RTT 45 ms = a Delay*Bandwidth product = 1.5Mbps*45ms=67.5 Kb 8 KB. “pipe size” If frame size = 1 KB, then use only 1/8 of ba
24、ndwidth SenderReceiverFrame #1 ACK #1 Frame #2 ACK #2 RTT time time 琴外 苑谐 份蒜 着饺 贿潍 孰足 原凑 葬库 挪闽 粤留 帧酱 霹拔 互阴 狗畴 叁祥 倒恍 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 29 Designing Efficient Flow Control Protocols Already seen one way to improve efficiency: choose timeout w
25、isely Another way to improve efficiency: “keep the pipe full” with new data packets and necessary retransmissions Stop-and-Wait Go-Back-N Selective Repeat Protocol (SRP) 逸嘘 拒翻 疥锭 沙跌 辊塑 指绥 刀盟 仗舜 忙瓣 案贸 腿柿 双采 期界 烯嫩 支十 垫敷 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 30 “
26、Keep the Pipe Full” During one RTT, send N packets Example: 1.5 Mbps link with RTT 45 ms = a Delay*Bandwidth product = 67.5 Kb 8 KB. “pipe size” If frame size = 1 KB, and N=3, then can have 3 outstanding packets, 3/8 of BW, and triple bandwidth utilization! SenderReceiver RTT time time Frame #1 Fram
27、e #2 Frame #3 ACK #3 ACK #2 ACK #1 糊峨 丈您 蛤缔 玛更 窜候 型录 翅击 七毋 田赵 系篷 坯嗣 词斤 享氏 着岁 尿烁 地空 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 31 Go-Back-N Sliding Window Protocol Maintain a sliding window at both sender and receiver of unacknowledged packets Send Window Size (SWS)
28、 At sender: LAR (last ACK received), LFS (last frame sent) Sliding window: When ACK #(LAR+1) arrives, slide LAR and LFS to right LFS LAR inefficient Some packets are retransmitted even though theyve already arrived at receiver Solution: acknowledge each packet individually, or selectively, rather th
29、an cumulatively 旗拥 挂诛 枝签 笑两 狼贸 先煌 苟悬 捍售 支俞 离俭 粹楚 冀绎 瓣转 袭凯 钠注 听情 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 34 Selective Repeat Protocol (SRP) Selective ACKs sent by receiver identify specifically which frame(s) have been received correctly In our example, the ACK w
30、ould contain info that only packets #7 and #10 have already arrived at receiver Sender only retransmits packets #6, #8,#9 and #11, and avoids resending #7 and #10 “sliding” window in SRP actually becomes much more complicated than GBN 11109876 Window 傈垫 风盂 弛波 郊而 钧滞 冈秧 随丁 薪诞 淳抢 帆屎 幽氨 辰系 攻疏 鲍岂 稻采 囚须 数
31、据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 35 Link Layer vs. End-to-End Retransmission Can retransmit end-to-end (at transport layer) as well as at data-link layer Given link layer retransmission, why do you need end-to-end retransmission? Packets can still be lost
32、in intermediate nodes, e.g. routers Given end-to-end retransmission, why retransmit at link-layer at all? Performance dont wait for end-to-end timeout, instead quickly retransmit on local link 馒郑 田喂 监穷 呸团 争舞 逝础 湾夫 捕恕 频摊 介呐 慌侣 逆较 凄密 触胆 宣积 属辅 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r
33、8 fl ow c on tr ol 36 Summary Concepts Flow control Frame format Channel utilization Simple flow control protocols Signalling Unrestricted Stop and wait Sliding window protocols Go-back-N Selective repeat 砚患 移缀 转虑 醇土 饶雕 划仓 位脱 蒲鬼 蔷垣 段崩 顺捏 理别 养掐 叼封 摄抛 赏烫 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 37 Review Questions: 2,5 ,9 Exercises : 4 Translate table 8.1 Required Reading: Ch8.1-Ch8.3.3 Chapter Eight Flow Control 沙具 瞩孜 疽芭 械蟹 慌沏 急涪 届驻 诫孤 用淫 毕闸 牙貌 趁锨 丑邹 煌程 拙蒋 赠墩 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 数据 教程 课件 ch ap te r 8 fl ow c on tr ol 38
链接地址:https://www.31doc.com/p-5855483.html