Transcript link-2-wb
CS3502: Data and Computer Networks DATA LINK LAYER - 2 WB version data link layer : flow and error control purpose : regulate the flow of data from sender S to receiver R, so that R is neither overwhelmed nor kept idle unnecessarily. secondary purpose may also be used to avoid swamping the network or link with traffic. technique : send control information between S and R, synchronizing on buffer space, transmission rates, etc. protocols: stop-and-wait, alternating bit sliding window (go-back-N, selective repeat/reject) performance analysis of networks attempts to determine the efficiency of a network; that is, for various traffic loads, how well the network uses its resources to meet the needs of the traffic examples stop and wait alternating bit more complex networks need the use of probability and queueing theory data link layer : stop-and -wait protocol send 1 frame, then stop, and wait for an acknowledgment before sending the next. X R data ack data data link layer : stop and wait what happens if a message is lost? to tolerate losses, must add timeouts (TO) and retransmissions what happens if data is lost? what happens if ack is lost? what is the obvious solution? alternating bit protocol:add a number to data frames, to uniquely identify; enable repeated messages to be safely discarded data link layer : stop and wait protocols what is the efficiency of this S&W protocol? i.e., of the total time spent, how much is actually spent sending the data? variables td, time spent transmitting the data tp, propagation delay tproc, processing time tack, time spent transmitting the ack. U, utilization or efficiency of the protocol performance of A-B protocol td tp tp AB protocol U = td /( td + 2 tprop), error free case or U = (1-PE)td /( td + 2 tprop, )error case link utilization of AB protocol suppose we use a satellite link, tprop = 250ms; data frame is 16K bits; transmission rate is 1 Mbps. What is U ? Assume negligible error rate. eart h how might this be improved? sliding window protocols: no error send a series of data frames, without waiting for acknowledgments 1 at a time window W : the number of frames in transit between sender and receiver (max, current) each frame numbered from 0, 1, 2, ..., w receiver may ack 1 or more frames at a time X sends up to max window, then waits for acks; R uses acks to control and maximize utilization sliding window protocol : no error suppose w = 3: frame NOTE: By Convention ack# = sequence # of next d0 d1 d2 expected by receiver ack3 sliding window protocol sequencing for w = 3: d0, d1, d2 wait for ack3 d3, d0, d1 wait for ack2 etc. exercise: show all sequences possible on timing diagram for w=3. (include 3 at a time, 2 at a time, 1 at a time) sliding window protocol : no error what is the efficiency of the protocol? ie, what is the best utilization possible? (assume no errors in the channel) sliding window: no channel errors U = W td /( td + 2 tprop ), if less than 1, U = 1, otherwise. Why sliding window protocol? for large windows, what if a message is lost? what problem do you see with this? suppose w = 63: what if d61 lost? d0 d1 d61 d62 T w ack61 d6 1 sliding window: variables, nacks standard variables NS and NR : used to keep track of sequence numbers NS : send sequence number; seq. number of the next data frame to be sent . Increments modulo Wmax +1. NR : receive sequence number; seq. number of the last (most recent) nack. frame received both are local variables of the sender current window in sender is found by subtracting the difference, NS _- NR , from maximum window size - Wcurrent = Wmax - [NS _- NR ] sliding window: variables, nacks go-back-N nacks: if a frame lost, it and all subsequent frames retransmitted nack: (1) acknowledges previous frames, and (2) rejects numbered frame and all subsequent frames. Sequence numbers convention same as acks# ie. Next frame expected. when sender gets a nack, NS must be rolled back to the value of the nack, and NR must be rolled forward to the nack examples sliding window: variables, nacks Initially, NS = NR = 0 NS incremented each time a frame sent NR updated each time a nack frame received example: suppose Wmax = 5; show values after each of following: send d0, d1, d2 receive nack1 send d1, d2, d3, d4, d5 receive nack4 send d4, d5, d0 what is current window size? Calculated modulo Wmax +1 sliding window protocol Go-back-n needlessly repeats frames sliding window: selective repeat (also called selective reject) only retransmit messages which were lost window size at most half the range of sequence numbers (why?) timing diagrams disadvantage more buffers, more complex algorithm, costs more advantage higher efficiency in noisy channels data link protocol performance go-back-N, selective repeat : no channel errors U = W td /( td + 2 tprop ),if less than 1, U = 1, otherwise. performance of data link protocols selective repeat: with errors U = 1 - P, for Wtd > td + 2 tprop = (1 - P) Wtd / td + 2 tprop , otherwise go-back-N, with errors U = (1 - P)td/(td + 2tpP), W > 2tp/td + 1, = W(1 - P)td/ (2tp + td)(1 - P + WP), O.W. see Stallings Appendix 6A HDLC: high level data link control ISO standard for a data link protocol other DL standards exist, but are very similar; e.g., PPP HDLC combines various functions of the DL layer - flow control, error control, sequencing, framing, etc. - into a single protocol standard HDLC standard is broad, covering several different cases 3 general classes: station type link configuration mode of operation HDLC station types primary P secondary S combined C types P and S are for multipoint network with polling hub polling, etc. --> master/slave network type link C for point-to-point link configurations balanced : 2 combined stations on 1 direct link unbalanced : 1 P, n S’s directly connected (e.g., bus) HDLC frame types and formats I-frame(information/data) S-frame (supervisory) U-frame (data)