CMPE 150 Winter 2009 Lecture 6 Januaryy 22 2009 P E Mantey CMPE 150 Introduction to Computer Networks Instructor Patrick Mantey mantey soe ucsc edu htt http www soe ucsc edu mantey d t Office Engr 2 Room 595J Office hours Tuesday 3 5 PM TA Anselm Kia akia soe ucsc edu Web site http www soe ucsc edu classes cmpe150 Winter09 Text Tannenbaum Computer p Networks 4th edition available in bookstore etc Syllabus Assignment 3 Available on the web site http www soe ucsc edu classes cmpe150 Winter09 Due Thursday January 29 2009 Today s Agenda Link Layer Services Framing kind seq ack info Error Control CRC Flow Control Protocols Standards Data Link Layer Design Issues Provide Services to Network Layer y Framing 2 Error E C Controll 3 Flow Control 1 Cyclic Redundancy Check Cyclic l Redundancy d d Check h k Cyclic Redundancy Check At Transmitter with M 1 1 1 0 1 1 compute 2rM M 1 1 1 0 1 1 0 0 0 with G 1 1 0 1 T 2rM R note G starts and ends with 1 Transmit R 111 T 1 1 1 0 1 1 1 1 1 Cyclic Redundancy Check At the Receiver compute Note remainder 0 no errors detected Polynomial Code M 111011 G 1101 x5 x4 x3 x 1 M x x3 x3 1 G x R x remainder of 2 3 M x G x recall r 3 T x 23 M x R x Error Detecting g Codes Calculation of the polynomial code checksum Ref Tannenbaum Fig 3 8 CRC Codes CRC 12 G x x12 x11 x3 x2 x 1 CRC 15 CRC 15 G x x16 x15 x2 1 CRC CCITT CRC 32 G x x16 x12 x5 1 G x x32 x26 x23 x22 x16 x12 x11 x100 x8 x7 x5 x4 x2 x 1 CRC Performance Errors go through undetected only if divisible by G x With suitably chosen G x CRC code detects All single bit i l bit errors All double bit errors as long as G x has at least three 1s Any odd number of error error as long as G x has a factor x 1 Any burst error for which the length of the burst is less than the length of the G x i e r Most larger burst errors For equally probable errors with burst of length r 1 r1 probability b bilit off an undetected d t t d error is i 1 2r 1 r For longer burst probability of undetected error is 1 2 adapted from Stallings Chapter 7 page 205 Logic implementation of Polynomial Encoder Decoder Ref Stallings Fig 7 6 Ref Stallings Fig 7 6 Data Link Connects to adjacent computers connected by a wire or equivalent Serial Bits delivered in order sent Data Link Layer Functions Provide service interface to the network layer Dealing with transmission errors Regulating data flow Slow receivers not swamped by fast senders Data Link Layer Functions Relationship between packets and frames Services Provided to Network Layer a Virtual Vi t l communication i ti b Actual communication Link Layer Services Unacknowledged Connectionless Service Acknowledged Connectionless Service Acknowledged g Connection oriented Service Link Layer Services Unacknowledged Connectionless Service Sender just sends sends no acknowledgments No attempt to resend lost frames Acknowledged Connectionless Service Acknowledged Connection oriented Service Link Layer Services Unacknowledged Connectionless Service Sender jjust sends no acknowledgments g No attempt to resend lost frames Used for Real time traffic voice voice video Highly reliable LANS When error control is done at higher layers e g TCP Acknowledged Connectionless Service Acknowledged Connection oriented Service Link Layer Services Unacknowledged Connectionless Service Sender jjust sends no acknowledgments g Acknowledged Connectionless Service No logical connection Frames individually acknowledged Tannenbaum says an option not a requirement BUT Acknowledged Connection Connection oriented oriented Service Link Layer Services Unacknowledged Connectionless Service Sender jjust sends no acknowledgments g Acknowledged Connectionless Service No logical connection Frames individually acknowledged Tannenbaum says an option not a requirement BUT large packets become multiple fixed size frames Some frames get through others lost then resend of packet is very inefficient vs resend of lost frames Acknowledged Connection oriented Service Link Layer Services Unacknowledged Connectionless Service Acknowledged Connectionless Service Acknowledged Connection oriented Service Connection established before data sent Each frame numbered Data link guarantees error free delivery Each frame received once and only once vs connectionless where a packet can be received several time if errors or timeouts occur Provides reliable bit stream to Network Layer Connection Oriented Service Protocol steps 1 establish connection 1 2 reliably deliver data stream Number frames Acknowledgments 3 free 3 ee tthe e co connection ect o Link Layer Connection of Routers in WAN Using Connection ConnectionOriented Service Ref Tannenbaum Fig 3 3 Framing a A frame delimited byy flagg bytes y b Four examples of byte sequences Ref Tannenbaum Fig 3 5 before and after stuffing Framing Bit Stuffing Bit stuffing a The original data b The data as they appear on the line c The data as they are stored in receiver s memory after destuffing Ref Tannenbaum Fig 3 6 Elementary Data Link Protocols Manage data flow at Link Layer An Unrestricted A U t i t d Simplex Si l Protocol P t l A Simplex p Stop and Wait p Protocol A Simplex Protocol for a Noisy Channel Protocol Definitions Continued Some definitions needed in the protocols to follow follow These are located in the file protocol h Protocol Definitions ctd Some definitions needed d d in i the h protocols to follow These are located in the file protocol h Unrestricted Simplex Protocol From Stallings Data and Computer Communications Stop and Wait Stop and Wait Simplest form of flow control control Transmitter sends frame and waits Receiver receives frame and sends ACK Transmitter gets ACK sends other frame and d waits it until til no more fframes tto send d Good when few frames Problem inefficient link utilization In the case of high data rates or long propagation delays Simplex St Stop andd Wait Protocol Animations http media pearsoncmg com aw aw kurose network 2 applets goback n go back n html http www humboldt edu 7Eaeb3 telecom SlidingWindow html http netbook cs purdue edu othrpags page15 htm From Stallings Data and Computer Communications A Simplex Protocol for a Noisy Ch Channel l A positi positivee acknowledgement with retransmission protocol Continued A Simplex Protocol for a Noisy Channel ctd A positive acknowledgement with retransmission protocol Sliding Window Protocols Sliding Window Protocols Supports bi directional data transfer Full Full duplex duplex piggy backing of acks Sliding Window Protocols A One
View Full Document
Unlocking...