DATA LINK LAYER PROTOCOLS
Combination of Flow and Error Control
Copyright By PowCoder代写 加微信 powcoder
• Flowcontrolrequirestheuseoftwobuffers,oneatthe sender site and the other at the receiver site
• Errorcontrolrequirestheuseofsequenceand acknowledgment numbers by both sides
• Thesetworequirementscanbecombinedifweusetwo numbered buffers, one at the sender, one at the receiver
Combination of Flow and Error Control
• Atthesender,whenapacketispreparedtobesent,we use the number of the next free location, x, in the buffer as the sequence number of the packet;
– a copy is stored at memory location x, awaiting the acknowledgment from the other end
– When an acknowledgment related to a sent packet arrives, the packet is purged and the memory location becomes free
Combination of Flow and Error Control
• Atthereceiver,whenapacketwithsequencenumbery arrives, it is stored at the memory location y until the application layer is ready to receive it.
– An acknowledgment can be sent to announce the arrival of packet y.
Combination of Flow and Error Control
• Thebufferisrepresentedasasetofslices,calledthe sliding window, or circular buffer of size 2m , m is the number of bits used in sequence number
• Atthesendersite,whenapacketissent,the corresponding slice is marked as valid. When all the slices are marked, it means that the buffer is full. When an acknowledgment arrives, the corresponding slice is unmarked, i.e. become free.
Sliding Window
• Theslidingwindowisanabstraction;threevariables define its size and location at any time. We call these variables
– Sf : the first outstanding packet,
– Sn : the next packet to be sent,
– Ssize : send window size – fixed for now 2m – 1
Sliding Window
• Theslidingwindowisanabstraction;threevariables define its size and location at any time. We call these variables
– Sf : the first outstanding packet,
– Sn : the next packet to be sent,
– Ssize : send window size – 2m-1 in the figure below
Data Link Protocols
• Traditionallyfourprotocolshavebeendefinedforthe data-link layer to deal with flow and error control:
– Stop-and-Wait, – Go-Back-N, and – Selective-Repeat
• Although the first two protocols still are used at the data-link layer, the last two have disappeared (moved to transport layer!)
Simple Protocol – FSM
• simple protocol neither support flow nor error control
– assumethatthereceivercanimmediatelyhandle any frame it receives
Simple Protocol – Example
• example of communication using this protocol. It is very simple. The sender sends frames one after another without even thinking about the receiver
Stop-and-Wait Protocol
• Stop-and-Waitprotocolusesbothflowanderrorcontrol
• the sender sends one frame at a time and waits for an acknowledgment before sending the next one
• Todetectcorruptedframes,weneedtoaddaCRCto each data frame
• Whenaframearrivesatthereceiversite,itischecked. If its CRC is incorrect, the frame is corrupted and silently discarded. The silence of the receiver is a signal for the sender that a frame was either corrupted or lost
• Also caller Stop-and-Wait Automatic Repeat Request (ARQ)
Stop-and-Wait Protocol
Everytimethesendersendsaframe,itstartsatimer. If an acknowledgment arrives before the timer expires, the timer is stopped and the sender sends the next frame (if it has one to send). If the timer expires, the sender resends the previous frame, assuming that the frame was either lost or corrupted
the sender needs to keep a copy of the frame until its acknowledgment arrives
Sender FSM
• Ready State: When the sender is in this state, it is only
waiting for a packet from the network layer
• Blocking State: When the sender is in this state, three events can occur:
1. Ifatime-outoccurs,thesenderresendsthesaved copy of the frame and restarts the timer.
2. IfacorruptedACKarrives,itisdiscarded.
3. Ifanerror-freeACKarrives,thesenderstopsthe timer and discards the saved copy of the frame. It then moves to the ready state
Receiver FSM
• Thereceiverisalwaysinthereadystate. • Twoeventsmayoccur:
1. Ifanerror-freeframearrives,themessageinthe frame is delivered to the network layer and an ACK is sent.
2. Ifacorruptedframearrives,theframeisdiscarded
Notice duplicate frame received But not detected
Using Sequence & Ack Numbers
there is a problem with the previous scheme. The network layer at the receiver site receives two copies of the third packet, which is not right.
WecanchangetheFSMtoincludethesequenceand acknowledgment numbers to be able to detect duplicate frames – see figure
• Assumethat,inaStop-and-Waitsystem,thebandwidth of the line is 1 Mbps, and 1 bit takes 20 milliseconds to make a round trip. What is the bandwidth-delay product? If the system data packets are 1,000 bits in length, what is the utilization percentage of the link?
• Solution: The bandwidth-delay product is (1 × 106) × (20 × 10−3) = 20,000 bits.
• Assumethat,inaStop-and-Waitsystem,thebandwidth of the line is 1 Mbps, and 1 bit takes 20 milliseconds to make a round trip. What is the bandwidth-delay product? If the system data packets are 1,000 bits in length, what is the utilization percentage of the link?
• Solution: The system can send 20,000 bits during the time it takes for the data to go from the sender to the receiver and the acknowledgment to come back. However, the system sends only 1,000 bits. We can say that the link utilization is only 1,000/20,000 = 5%
• A link with a high bandwidth or long delay using Stop-and-Wait wastes the capacity of the link.
Pipelining
• Innetworkingandinotherareas,ataskisoftenbegun before the previous task has ended. This is known as pipelining.
• ThereisnopipeliningintheStop-and-Waitprotocol because a sender must wait for a packet to reach the destination and be acknowledged before the next packet can be sent.
• Pipeliningdoesapplytoournexttwoprotocolsbecause several packets can be sent before a sender receives feedback about the previous packets.
• Pipeliningimprovestheefficiencyofthetransmission
Go-Back-N Protocol (GBN)
• Toimprovetheefficiencyoftransmission(tofillthe pipe), multiple packets must be in transition while the sender is waiting for acknowledgment.
• ThekeytoGo-Back-N(GBN)(therationaleforthe name will become clear later) is that we can send several packets before receiving acknowledgments, but the receiver can only buffer one packet.
• Wekeepacopyofthesentpacketsuntilthe acknowledgments arrive.
Go-Back-N Protocol (GBN)
• Notethatseveraldatapacketsandacknowledgments can be in the channel at the same time
Sequence & Acknowledgment Numbers
• The sequence numbers are modulo 2m, where m is the size of the sequence number field in bits
• acknowledgmentnumberinthisprotocoliscumulative and defines the sequence number of the next packet expected.
– If the acknowledgment number (ackNo) is 7, it means all packets with sequence number up to 6 have arrived, safe and sound, and the receiver is expecting the packet with sequence number 7.
Send Window
• Thesendwindowisanimaginaryboxcoveringthe sequence numbers of the data packets that can be in transit or can be sent
• Ineachwindowposition,someofthesesequence numbers define the packets that have been sent; others define those that can be sent.
• The maximum size of the window is 2m -1
Send Window
Send Window
• Thewindowitselfisanabstraction;threevariables define its size and location at any time. We call these variables
– Sf : the first outstanding packet,
– Sn : the next packet to be sent,
– Ssize : send window size – fixed for now 2m – 1
Sliding Window
• Thesendwindowcanslideoneormoreslotswhenan error-free ACK with ackNo greater than or equal to Sf and less than Sn (in modular arithmetic) arrives
Receive Window
• Thereceivewindowmakessurethatthecorrectdata packets are received and that the correct acknowledgments are sent.
• InGo-Back-N,thesizeofthereceivewindowisalways 1. The receiver is always looking for the arrival of a specific packet
• Thewindowslideswhenacorrectpackethasarrived; sliding occurs one slot at a time
Resending packets
• Whenthetimerexpires,thesenderresendsall outstanding packets
Send Window Size – max 2m-1
• Wecannowshowwhythesizeofthesendwindow must be less than 2m. As an example, we choose m = 2, which means the size of the window can be 2m − 1, or 3.
Send Window Size – max 2m-1
Send Window Size – max 2m-1
• Ifthesizeofthewindowis3(lessthan2m)andall three acknowledgments are lost, the only timer expires and all three packets are resent. The receiver is now expecting packet 3, not packet 0, so the duplicate packet is correctly discarded.
• ifthesizeofthewindowis4(equalto22)andall acknowledgments are lost, the sender will send a duplicate of packet 0. However, this time the window of the receiver expects to receive packet 0 (in the next cycle), so it accepts packet 0, not as a duplicate, but as the first packet in the next cycle. This is an error
Cumulative Acknowledgments
• anexampleofacasewheretheforwardchannelis reliable, but the reverse is not. No data packets are lost, but some ACKs are delayed and one is lost. The example also shows how cumulative acknowledgments can help if acknowledgments are delayed or lost.
• whathappenswhenapacketislost.Packets0,1,2, and 3 are sent. However, packet 1 is lost. The receiver receives packets 2 and 3, but they are discarded because they are received out of order (packet 1 is expected). When the receiver receives packets 2 and 3, it sends ACK1 to show that it expects to receive packet 1. However, these ACKs are not useful for the sender because the ackNo is equal to Sf, not greater than Sf. So the sender discards them. When the time-out occurs, the sender resends packets 1, 2, and 3, which are acknowledged
Go-Back-N protocol issue
• TheGo-Back-Nprotocolsimplifiestheprocessatthe receiver. The receiver keeps track of only one variable, and there is no need to buffer out-of-order packets; they are simply discarded. However, this protocol is inefficient if the underlying network protocol loses a lot of packets.
• Eachtimeasinglepacketislostorcorrupted,the sender resends all outstanding packets, even though some of these packets may have been received safe and sound but out of order.
Selective-Repeat Protocol
• Selective-Repeat(SR)protocol,asthenameimplies, resends only selective packets, those that are actually lost. The outline of this protocol is as shown:
Selective-Repeat Protocol
• TheSelective-Repeatprotocolalsousestwowindows:a send window and a receive window.
• Themaximumsizeofthesendwindowismuchsmaller; it is 2m−1, or 1⁄2 2m, much smaller than Go-Back-N protocol.
– For example, if m = 4, the sequence numbers go from 0 to 15, but the maximum size of the window is just 8 (it is 15 in the Go-Back-N Protocol)
• Allthepacketsinthesendpacketcanarriveoutof order and be stored until they can be delivered
• A reliable protocol the receiver never delivers packets out of order to the application layer
Selective-Repeat Protocol
• TheSelective-Repeatprotocolalsousestwowindows:a send window and a receive window.
• Thereceivewindowisthesamesizeasthesend window
• ThereceivewindowinSelective-Repeatistotally different from the one in Go-Back-N.
• TheSelective-Repeatprotocolallowsasmanypackets as the size of the receive window to arrive out of order and be kept until there is a set of consecutive packets to be delivered to the application layer
• A reliable protocol the receiver never delivers packets out of order to the application layer
• Theoretically,Selective-Repeatusesonetimerforeach outstanding packet. When a timer expires, only the corresponding packet is resent.
• Go-Back-Ntreatsoutstandingpacketsasagroup;
• Selective-Repeattreatsthemindividually.
• Mosttransport-layerprotocolsthatimplementSRuse only a single timer. For this reason, we use only one timer
Acknowledgments
• InGo-Back-NanackNoiscumulative;itdefinesthe sequence number of the next packet expected, confirming that all previous packets have been received safe and sound.
• ThesemanticsofacknowledgmentisdifferentinSR.In SR, an ackNo defines the sequence number of a single packet that is received safe and sound; there is no feedback for any other
• ThisexampleissimilartoapreviousExampleinwhich packet 1 is lost. We show how Selective-Repeat behaves in this case.
Window Sizes
• Wecannowshowwhythesizeofthesenderand receiver windows can be at most one-half of 2m. For an example, we choose m = 2, which means the size of the window is 2m/2 or 2(m−1) = 2. The Figure compares a window size of 2 with a window size of 3
Window Sizes
Window Sizes
• Ifthesizeofthewindowis2andallacknowledgments are lost, the timer for packet 0 expires and packet 0 is resent. However, the window of the receiver is now expecting packet 2, not packet 0, so this duplicate packet is correctly discarded (the sequence number 0 is not in the window).
• Whenthesizeofthewindowis3andall acknowledgments are lost, the sender sends a duplicate of packet 0. However, this time, the window of the receiver expects to receive packet 0 (0 is part of the window), so it accepts packet 0, not as a duplicate, but as a packet in the next cycle. This is clearly an error
Bidirectional Protocols: Piggybacking
• Inreallife,datapacketsarenormallyflowinginboth directions: from client to server and from server to client.
• Thismeansthatacknowledgmentsalsoneedtoflowin both directions.
• Atechniquecalledpiggybackingisusedtoimprove the efficiency of the bidirectional protocols.
• WhenapacketiscarryingdatafromAtoB,itcanalso carry acknowledgment feedback about arrived packets from B; when a packet is carrying data from B to A, it can also carry acknowledgment feedback about the arrived packets from A.
References
• DataCommunicationsandNetworking5thedition– 2013, Behrouz A. Forouzan; Chapter 23
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com