15-441 Lecture 6Last TimeToday (& Tomorrow)From Signals to PacketsHow Encode?Why Encode?Non-Return to Zero (NRZ)Why Do We Need Encoding?Non-Return to Zero Inverted (NRZI)Ethernet Manchester EncodingSlide 114B/5B EncodingSlide 13Other EncodingsWhere we areSlide 16FramingSlide 18Out-of-band: E.g., 802.5Sentinal based: E.g., BISYNCCharacter and Bit StuffingEthernet FramingClock Based Framing: SONETStandardization HistoryA Word about Data RatesSynchronous Data TransferHow avoid clock skew?SONET FramingHow Do We Support Lower Rates?How Do We Support Higher Rates?The SONET Signal HierarchyUsing SONET in NetworksSelf-Healing SONET RingsSONET as Physical LayerDatalink FunctionsError CodingTwo basic approachesBasic Concept: Hamming DistanceSlide 39ExamplesInternet ChecksumCyclic Redundancy Codes (CRC)CRC: Basic ideaLink Flow Control and Error ControlSlide 45A Naïve ProtocolAdding Flow ControlWindow Flow ControlBandwidth-Delay ProductDealing with Errors Stop and Wait CaseWhat is Used in Practice?So far …Slide 53Datalink ArchitecturesMedia Access ControlDatalink ClassificationSwitchingA Switch-based NetworkSwitch ArchitectureConnections or Not?ConnectionlessVirtual Circuit SwitchingSetup, assign VCIsPacket Forwarding: Address LookupSlide 65What we coveredLecture 6 15-441 © 200815-441 Lecture 6Physical Layer (Cont) &Data Link LayerCopyright © Seth Goldstein, 2008Based on slides from previous 441 lectures1Last Time•Physical Layer–Modulation–Bandwidth–Nyquist/Shannon–Multiplexing–MediaApplicationApplicationPresentationPresentationSessionSessionTransportTransportNetworkNetworkDatalinkDatalinkPhysicalPhysicalToday (& Tomorrow)1.Physical layer.(Encoding)2.Datalink layer introduction, framing, error coding, MAC, switched networks.3.Broadcast-networks, home networking.ApplicationApplicationPresentationPresentationSessionSessionTransportTransportNetworkNetworkDatalinkDatalinkPhysicalPhysicalFrom Signals to PacketsAnalog Signal“Digital” SignalBit Stream0 0 1 0 1 1 1 0 0 0 1Packets0100010101011100101010101011101110000001111010101110101010101101011010111001Header/BodyHeader/BodyHeader/BodyReceiverSenderPacketTransmissionLecture 6 15-441 © 2008 4How Encode?•Seems obvious, why take time with this?Lecture 6 15-441 © 2008V 0.85-.850 0 0 11 0 1 015Why Encode?Lecture 6 15-441 © 20080 1 0 1 How many more ones?6Non-Return to Zero (NRZ) •1 -> high signal; 0 -> low signal•Long sequences of 1’s or 0’s can cause problems:–Sensitive to clock skew, i.e. hard to recover clock–Difficult to interpret 0’s and 1’sV 0.85-.850 0 0 11 0 1 01Lecture 6 15-441 © 2008 7Why Do We Need Encoding?•Keep receiver synchronized with sender.•Create control symbols, besides regular data symbols.–E.g. start or end of frame, escape, ...•Error detection or error corrections.–Some codes are illegal so receiver can detect certain classes of errors–Minor errors can be corrected by having multiple adjacent signals mapped to the same data symbol•Encoding can be done one bit at a time or in multi-bit blocks, e.g., 4 or 8 bits.•Encoding can be very complex, e.g. wireless.Lecture 6 15-441 © 2008 8Non-Return to Zero Inverted (NRZI) •1 make transition; 0 signal stays the same•Solves the problem for long sequences of 1’s, but not for 0’s.V 0.85-.850 0 0 11 0 1 01Lecture 6 15-441 © 2008 9Ethernet Manchester Encoding •Positive transition for 0, negative for 1•Transition every cycle communicates clockV 0.85-.850 1 1 0.1sLecture 6 15-441 © 2008 10Ethernet Manchester Encoding •Positive transition for 0, negative for 1•Transition every cycle communicates clock(but need 2 transition times per bit)•DC balance has good electrical propertiesV 0.85-.850 1 1 0.1sLecture 6 15-441 © 2008 114B/5B Encoding•Data coded as symbols of 5 line bits 4 data bits, so 100 Mbps uses 125 MHz.–Uses less frequency space than Manchester encoding•Uses NRZI to encode the 5 code bits•Each valid symbol has at least two 1s–So never get three 0s in a row–(Why don’t we care about 3 ones in a row?)•16 data symbols, 8 control symbols –Data symbols: 4 data bits–Control symbols: idle, begin frame, etc.•Example: FDDI.Lecture 6 15-441 © 2008 124B/5B Encoding000000010010001101000101011001111111001001101001010101010010110111001111Data Code100010011010101111001101111011111001010011101101011111010110111110011101Data CodeLecture 6 15-441 © 2008 13Other Encodings•8B/10B: Fiber Channel and Gigabit Ethernet•64B/66B: 10 Gbit Ethernet•B8ZS: T1 signaling (bit stuffing)•Encoding necessary for clocking•Lots of approaches•Rule of thumb:–Little bandwidth complex encoding–Lots of bandwidth simple encodingLecture 6 15-441 © 2008Things to Remember14Where we are•We can send strings of bits•We can keep the transmitter and receiver clock synchronized•What next?•Why?Lecture 6 15-441 © 2008 15Where we are•We can send strings of bits•We can keep the transmitter and receiver clock synchronized•What next?–Datalink layer•Logical link control•Media access control–Framing–Error detection/correction–Flow control–AccessLecture 6 15-441 © 2008 16Framing•How do we differentiate the stream of bits into frames?Lecture 6 15-441 © 2008010001010101110010101010101110111000000111101010111010101010110101101011100117Framing•A link layer function, defining which bits have which function.•Minimal functionality: mark the beginning and end of frames.•Some techniques:–Out-of-band: delimiters (e.g. 4B/5B control symbols)–In-band:•frame delimiter characters with char stuffing•frame delimiter codes with bit stuffing–Clock based: (e.g. SONET)Lecture 6 15-441 © 2008 18Out-of-band: E.g., 802.5•802.5/token ring uses 4b/5b•Start delim & end delim are “illegal” codesLecture 6 15-441 © 2008StartdelimAccessctrlBody checksumFramectrlDestadrSrcadrEnddelimFramestatus19Sentinal based: E.g., BISYNC•SYN: sync character•SOH: start of header•STX: start of text•ETX: end of text•What happens when ETX is in Body?Lecture 6 15-441 © 2008SYN SYN SOH Header STX Body ETX CRC20Character and Bit Stuffing•Mark frames with special character.–What happens when the user sends this character?–Use escape character when controls appear in data: *abc*def -> *abc\*def–Very common on serial lines, in editors, etc.•Mark frames with special bit sequence–must ensure data
View Full Document