Datalink – Framing, SwitchingFrom Signals to PacketsDatalink FunctionsEncodingWhy Do We Need Encoding?EncodingNon-Return to Zero (NRZ) Non-Return to Zero Inverted (NRZI) Ethernet Manchester Encoding 4B/5B Encoding4B/5B EncodingOther EncodingsError CodingBasic Concept: Hamming DistanceCyclic Redundancy Codes (CRC)FramingCharacter and Bit StuffingExample: Ethernet FramingBaud Rate, Bandwidth, Clock Rate, Bit RateOther Issues Impacting PerformanceLink Flow Control and Error ControlA Naïve ProtocolAdding Flow ControlWindow Flow ControlDealing with Errors Stop and Wait CaseIssues with Window-based ProtocolBandwidth-Delay ProductPhysical and Data LinkDatalink ArchitecturesMedia Access ControlRepeaters Building Larger LANs: BridgesTransparent BridgesFrame ForwardingFrame Forwarding 2Address LearningAddress Learning 2ExampleDanger of LoopsSpanning TreesEthernet SwitchesStructure of A Generic Communication SwitchWhat Are the Issues of Bridging? Long Distance Transmission Synchronous Data TransferThe SONET Signal HierarchySONET Can Be A NetworkSelf-Healing SONET RingsSONET Network as Physical LayerAddressing and Look-upDatalink – Framing, SwitchingFrom Signals to PacketsAnalog Signal“Digital” SignalBit Stream0 0 1 0 1 1 1 0 0 0 1Packets0100010101011100101010101011101110000001111010101110101010101101011010111001Header/BodyHeader/BodyHeader/BodyReceiverSenderPacketTransmissionDatalink Functions• Framing: encapsulating a network layer datagram into a bit stream.• Add header, mark and detect frame boundaries• Media access: controlling which frame should be sent over the link next.• Error control: error detection and correction to deal with bit errors.• May also include other reliability support, e.g. retransmission• Flow control: avoid that the sender outruns the receiver• Hubbing, bridging: extend the size of the networkEncodingMapping bits into signalAdaptorAdaptorAdaptorAdaptorSignalAdaptor: convert bits into physical signal and physical signal back into bitsWhy Do We Need Encoding?• Meet certain electrical constraints.• Receiver needs enough “transitions” to keep track of the transmit clock• Avoid receiver saturation• 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 very complex, e.g. wireless.Encoding• We use two discrete signals, high and low, to encode 0 and 1• The transmission is synchronous, i.e., there is a clock used to sample the signal• In general, the duration of one bit is equal to one or two clock ticksNon-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’sV0.85-.85000110101Non-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.V0.85-.85000110101Ethernet 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 propertiesV0.85-.850110.1μs4B/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 NRI to encode the 5 code bits• Each valid symbol has at least two 1s: get dense transitions.• 16 data symbols, 8 control symbols • Data symbols: 4 data bits• Control symbols: idle, begin frame, etc.• Example: FDDI.4B/5B Encoding000000010010001101000101011001111111001001101001010101010010110111001111Data Code100010011010101111001101111011111001010011101101011111010110111110011101Data CodeOther Encodings• 8B/10B: Fiber Channel and Gigabit Ethernet• DC balance• 64B/66B: 10 Gbit Ethernet• B8ZS: T1 signaling (bit stuffing)Error Coding• Transmission process may introduce errors into a message.• Single bit errors versus burst errors• Detection:• Requires a convention that some messages are invalid• Hence requires extra bits• An (n,k) code has codewords of n bits with k data bits and r = (n-k) redundant check bits• Correction• Forward error correction: many related code words map to the same data word• Detect errors and retry transmissionBasic Concept:Hamming Distance• Hamming distance of two bit strings = number of bit positions in which they differ.• If the valid words of a code have minimum Hamming distance D, then D-1 bit errors can be detected.• If the valid words of a code have minimum Hamming distance D, then [(D-1)/2] bit errors1 0 1 1 01 1 0 1 0HD=2HD=3Cyclic Redundancy Codes(CRC)• Commonly used codes that have good error detection properties.• Can catch many error combinations with a small number or redundant bits• Based on division of polynomials.• Errors can be viewed as adding terms to the polynomial• Should be unlikely that the division will still work• Can be implemented very efficiently in hardware.• Examples:• CRC-32: Ethernet• CRC-8, CRC-10, CRC-32: ATMFraming• A link layer function, defining which bits have which function.• Minimal functionality: mark the beginning and end of packets (or frames).• Some techniques:• out of band delimiters (e.g. FDDI 4B/5B control symbols)• frame delimiter characters with character stuffing• frame delimiter codes with bit stuffing• synchronous transmission (e.g. SONET)Character 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 containing this sequence can be transmitted• example: suppose 11111111 is a special sequence.• transmitter inserts a 0 when this appears in the data:• 11111111 -> 111111101• must stuff a zero any time seven 1s appear:• 11111110 -> 111111100• receiver unstuffs.Example: Ethernet Framing• Preamble is 7 bytes of 10101010 (5 MHz square wave) followed by one byte of 10101011• Allows receivers to recognize start of transmission after idle
View Full Document
Unlocking...