Lecture 6 Datalink – Framing, SwitchingFrom Signals to PacketsDatalink FunctionsDatalink LecturesFramingCharacter and Bit StuffingExample: Ethernet FramingSONETStandardization HistoryA Word about Data RatesSynchronous Data TransferSONET FramingHow Do We Support Lower Rates?How Do We Support Higher Rates?The SONET Signal HierarchyUsing SONET in NetworksSelf-Healing SONET RingsSONET as Physical LayerError CodingBasic Concept: Hamming DistanceExamplesCyclic Redundancy Codes (CRC)Datalink ArchitecturesMedia Access ControlA Switch-based NetworkSwitching IntroductionAn Inter-networkInternetworking OptionsSwitch ArchitecturePacket Forwarding: Address LookupLink Flow Control and Error ControlA Naïve ProtocolAdding Flow ControlWindow Flow ControlBandwidth-Delay ProductDealing with Errors Stop and Wait CaseWhat is Used in Practice?Datalink Layer ArchitecturesMultiple Access ProtocolsFiber Distributed Data Interface (FDDI)Other “Taking Turn” Protocols1Lecture 6Datalink – Framing, SwitchingDavid AndersenDepartment of Computer ScienceCarnegie Mellon University15-441 Networking, Spring 2005http://www.cs.cmu.edu/~srini/15-441/S05/2From Signals to PacketsAnalog Signal“Digital” SignalBit Stream0 0 1 0 1 1 1 0 0 0 1Packets0100010101011100101010101011101110000001111010101110101010101101011010111001Header/BodyHeader/BodyHeader/BodyReceiverSenderPacketTransmission3Datalink FunctionsFraming: 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.»Easy for point-to-point links; half versus full duplex»Harder for multi-access links: who gets to send?Error control: error detection and correction to deal with bit errors.»May also include other reliability support, e.g. retransmissionFlow control: avoid that the sender outruns the receiver.4Datalink LecturesFraming and error coding.Datalink architectures.Switch-based networks.»Packet forwarding»Flow and error controlTaking turn protocols.Contention-based networks: basic Ethernet.Ethernet bridging and switching.Connectivity to the home.Circuit-based communication5FramingA 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)6Character and Bit StuffingMark 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.7Example: Ethernet FramingPreamble is 7 bytes of 10101010 (5 MHz square wave) followed by one byte of 10101011Allows receivers to recognize start of transmission after idle channelpreamblepreambledatagramdatagramlengthlengthmore stuffmore stuff8SONETSONET is the Synchronous Optical Network standard for data transport over optical fiber.One of the design goals was to be backwards compatible with many older telco standards.Beside minimal framing functionality, it provides many other functions:»operation, administration and maintenance (OAM) communications»synchronization»multiplexing of lower rate signals»multiplexing for higher rates9Standardization HistoryProcess was started by divestiture in 1984.»Multiple telephone companies building their own infrastructureSONET concepts originally developed by Bellcore.First standardized by ANSI T1X1 group for the US.Later picked up by CCITT and developed its own version.SONET/SDH standards approved in 1988.10A Word about Data RatesBandwidth of telephone channel is under 4KHz, so when digitizing: 8000 samples/sec * 8 bits = 64Kbits/secondCommon data rates supported by telcos in North America:»Modem: rate improved over the years»T1/DS1: 24 voice channels plus 1 bit per sample (24 * 8 + 1) * 8000 = 1.544 Mbits/second»T3/DS3: 28 T1 channels: 7 * 4 * 1.544 = 44.736 Mbits/second11Synchronous Data TransferSender and receiver are always synchronized.»Frame boundaries are recognized based on the clock»No need to continuously look for special bit sequencesSONET frames contain room for control and data.»Data frame multiplexes bytes from many users»Control provides information on data, management, …3 colstransportoverhead87 cols payload capacity9 rows12SONET FramingBase channel is STS-1 (Synchronous Transport System).»Takes 125 sec and corresponds to 51.84 Mbps»1 byte/frame corresponds to a 64 Kbs channel (voice)»Also called OC-1 = optical carrierStandard ways of supporting slower and faster channels.»Support both old standards and future (higher) data ratesActual payload frame ”floats” in the synchronous frame.»Clocks on individual links do not have to be synchronized3 colstransportoverhead87 cols payload capacity,including 1 col path overhead9 rows13How Do We Support Lower Rates?1 Byte in every consecutive frame corresponds to a 64 Kbit/second channel.»1 voice call.Higher bandwidth channels hold more bytes per frame.»Multiples of 64 Kbit/secondChannels have a “telecom” flavor.»Fixed bandwidth»Just data – no headers»SONET multiplexers remember how bytes on one link should be mapped to bytes on the next link 125 sec125 sec125 sec14How Do We SupportHigher Rates?Send multiple frames in a 125 sec time slot.The properties of a channel using a single byte/ST-1 frame are maintained!»Constant 64 Kbit/second rate»Nice spacing of the byte samplesRates typically go up by a factor of 4.Two ways of doing interleaving.»Frame interleaving»Column interleaving–concatenated version, i.e. OC-3c125 sec125 sec125 sec15The SONET Signal HierarchySignal TypeSignal TypeOC-1OC-1line rateline rate# of DS0# of DS051.84 Mbs51.84 Mbs672672OC-3OC-3155 Mbs155 Mbs2,0162,016OC-12OC-12622 Mbs622 Mbs8,0648,064STS-48STS-482.49 Gbs2.49 Gbs32,25632,256STS-192STS-1929.95 Gbs9.95
View Full Document