From Signals to Packets

Analog Signal
Lecture 6
Datalink – Framing, Switching “Digital” Signal

David Andersen
Bit Stream 0 0 1 0 1 1 1 0 0 0 1
Department of Computer Science
Carnegie Mellon University 0100010101011100101010101011101110000001111010101110101010101101011010111001
Packets
(perpetrated by Dave Eckhardt) Header/Body Header/Body Header/Body

15-441 Networking, Fall 2006 Packet

Transmission Sender Receiver
http://www.cs.cmu.edu/~srini/15-441/S05/
1 2

Datalink Functions Datalink Lectures

 Framing and error coding.

 Framing: encapsulating a network layer
datagram into a bit stream.  Datalink architectures.
» Add header, mark and detect frame boundaries, …  Switch-based networks.
 Media access: controlling which frame should » Packet forwarding
be sent over the link next. » Flow and error control
» Easy for point-to-point links; half versus full duplex  Taking turn protocols.
» Harder for multi-access links: who gets to send?
 Error control: error detection and correction  Contention-based networks: basic Ethernet.
to deal with bit errors.
» May also include other reliability support, e.g.  Ethernet bridging and switching.
retransmission  Connectivity to the home.
 Flow control: avoid that the sender outruns
the receiver.
 Circuit-based communication
3 4

Framing Character and Bit Stuffing

 Mark frames with special character.

 A link layer function, defining which bits have » What happens when the user sends this character?
which function. » Use escape character when controls appear in data:
 Minimal functionality: mark the beginning and *abc*def -> *abc\*def
» Very common on serial lines, in editors, etc.
end of packets (or frames).
 Mark frames with special bit sequence
 Some techniques: » must ensure data containing this sequence can be
» out of band delimiters (e.g. FDDI 4B/5B control symbols) transmitted
» frame delimiter characters with character stuffing » example: suppose 11111111 is a special sequence.
» frame delimiter codes with bit stuffing » transmitter inserts a 0 when this appears in the data:
» synchronous transmission (e.g. SONET) » 11111111 -> 111111101
» must stuff a zero any time seven 1s appear:
» 11111110 -> 111111100
» receiver unstuffs.

5 6

1
 Example: Ethernet Framing SONET

 SONET is the Synchronous Optical Network

standard for data transport over optical fiber.
preamble datagram length more stuff
 One of the design goals was to be backwards
compatible with many older telco standards.
 Preamble is 7 bytes of 10101010 (5 MHz  Beside minimal framing functionality, it
square wave) followed by one byte of provides many other functions:
» operation, administration and maintenance (OAM)
10101011 communications
 Allows receivers to recognize start of » synchronization
transmission after idle channel » multiplexing of lower rate signals
» multiplexing for higher rates

7 8

Standardization History A Word about Data Rates

 Process was started by divestiture in 1984.  Bandwidth of telephone channel is under

» Multiple telephone companies building their own 4KHz, so when digitizing:
infrastructure
8000 samples/sec * 8 bits = 64Kbits/second
 SONET concepts originally developed by
Bellcore.  Common data rates supported by telcos in
North America:
 First standardized by ANSI T1X1 group for the » Modem: rate improved over the years
US. » T1/DS1: 24 voice channels plus 1 bit per sample
 Later picked up by CCITT and developed its (24 * 8 + 1) * 8000 = 1.544 Mbits/second
own version. » T3/DS3: 28 T1 channels:
 SONET/SDH standards approved in 1988. 7 * 4 * 1.544 = 44.736 Mbits/second

9 10

Synchronous Data Transfer SONET Framing

 Sender and receiver are always synchronized.  Base channel is STS-1 (Synchronous Transport System).
» Frame boundaries are recognized based on the clock » Takes 125 µsec and corresponds to 51.84 Mbps
» No need to continuously look for special bit sequences » 1 byte/frame corresponds to a 64 Kbs channel (voice)
» Transmitted on an OC-1 optical carrier (fiber link)
 SONET frames contain room for control and data.
» Data frame multiplexes bytes from many users  Standard ways of supporting slower and faster channels.
» Control provides information on data, management, … » Support both old standards and future (higher) data rates
 Actual payload frame “floats” in the synchronous frame.
» Clocks on individual links do not have to be synchronized
3 cols 3 cols 87 cols payload capacity,
transport 87 cols payload capacity transport including 1 col path overhead
overhead overhead

9 rows 9 rows

11 12

2
 How Do We Support How Do We Support
Lower Rates? Higher Rates?

 1 Byte in every consecutive  Send multiple frames in a 125

frame corresponds to a 64 µsec time slot.

125 µsec

125 µsec
Kbit/second channel.  The properties of a channel
» 1 voice call. using a single byte/ST-1
 Higher bandwidth channels frame are maintained!
hold more bytes per frame. » Constant 64 Kbit/second rate

125 µsec
» Nice spacing of the byte samples

125 µsec
» Multiples of 64 Kbit/second
 Channels have a “telecom”  Rates typically go up by a
flavor. factor of 4.
» Fixed bandwidth  Two ways of doing
interleaving.

125 µsec

125 µsec
» Just data – no headers
» SONET multiplexers remember » Frame interleaving
how bytes on one link should be » Column interleaving
mapped to bytes on the next link
– concatenated version, i.e.
– Byte 33 on incoming link 1 is OC-3c
byte 97 on outgoing link 7
13 14

The SONET Signal Hierarchy Using SONET in Networks

Add-drop capability allows soft configuration of networks,
usually managed manually.
Signal Type line rate # of DS0

DS0 (POTS) 64 Kbs 1

OC-48 mux
DS1 1.544 Mbs 24
STS-1 carries DS3 44.736 Mbs 672 DS1
one DS-3 plus
OC-1 51.84 Mbs 672 mux
overhead OC-3c
OC-3 155 Mbs 2,016
OC-12 622 Mbs 8,064 OC-12c
STS-48 2.49 Gbs 32,256
mux
STS-192 9.95 Gbs 129,024
STS-768 39.8 Gbs 516,096

15 16

Self-Healing SONET Rings SONET as Physical Layer

OC3/12 OC3/12
OC3/12 Access CO CO Access
OC-48
Access CO OC12/48
mux mux OC12/48 Metro
Metro CO
POP
CO
POP WDM Backbone OC3/12
OC48/192 Access
OC3/12
Access
DS1 POP

mux mux
OC-3c OC3/12 OC12/48 OC3/12
CO CO
OC-12c
Access Metro Access
17 18

3
 Basic Concept:
Error Coding Hamming Distance

 Hamming distance of two

 Transmission process may introduce errors bit strings = number of bit 1 0 1 1 0 HD=2
into a message. 1 1 0 1 0
positions in which they
» Single bit errors versus burst errors
differ.
 Detection: HD=3
 If the valid words of a code
» Requires a convention that some messages are invalid
have minimum Hamming
» Hence requires extra bits
distance D, then D-1 bit
» An (n,k) code has codewords of n bits with k data bits
and r = (n-k) redundant check bits
errors can be detected.
 Correction  If the valid words of a code
» Forward error correction: many related code words map
have minimum Hamming
to the same data word distance D, then [(D-1)/2] bit
» Detect errors and retry transmission errors can be corrected.

19 20

Cyclic Redundancy Codes

Examples (CRC)

 A (4,3) parity code has D=2:  Commonly used codes that have good error
0001 0010 0100 0111 1000 1011 1101 1110 detection properties.
(last bit is binary sum of previous 3, inverted - “odd parity”) » Can catch many error combinations with a small number or
redundant bits
 A (7,4) code with D=3 (2ED, 1EC):
0000000 0001101 0010111 0011010
 Based on division of polynomials.
0100011 0101110 0110100 0111001 » Errors can be viewed as adding terms to the polynomial
1000110 1001011 1010001 1011100 » Should be unlikely that the division will still work
1100101 1101000 1110010 1111111  Can be implemented very efficiently in
 1001111 corrects to 1001011 hardware.
 Note the inherent risk in correction; consider  Examples:
a 2-bit error resulting in 1001011 -> 1111011. » CRC-32: Ethernet
» CRC-8, CRC-10, CRC-32: ATM
 There are formulas to calculate the number of
extra bits that are needed for a certain D.
21 22

Datalink Architectures Media Access Control

 How do we transfer packets between two hosts

connected to the same network?
 Switches connected by point-to-point links --
store-and-forward.
» Used in WAN, LAN, and for home connections
» Conceptually similar to “routing”
– But at the datalink layer instead of the network layer
» Today
 Multiple access networks -- contention based.
 Packet forwarding.  Media access » Multiple hosts are sharing the same transmission medium
 Error and flow control. control. » Used in LANs and wireless
 Scalability. » Need to control access to the medium
» Mostly Thursday lecture

23 24

4
 A Switch-based Network Switching Introduction

 Switches are connected by point-point links.

 Packets are forwarded hop-by-hop by the switches  Idea: forward units of data based on address in
towards the destination. header.
» Forwarding is based on the address
 Many data-link technologies use switching.
 How does a switch work? » Virtual circuits: Frame Relay, ATM, X.25, ..
 How do nodes exchange packets over a link? » Packets: Ethernet, MPLS, …
 How is the destination addressed?  “Switching” also happens at the network layer.
» Layer 3: Internet protocol
Point-Point
Switch link » In this case, address is an IP address
PCs at » IP over SONET, IP over ATM, ..
Work PC at » Otherwise, operation is very similar
Home
 Switching is different from SONET mux/demux.
» SONET channels statically configured - no addresses

25 26

An Inter-network Internetworking Options

Host Host 7 7 7 7
6 6 6 6
5 5 5 5
Host Host 4 4 4 4
Wireless data link
Host 3 3 3 3
2 physical 2 2 2 2
1 1 1 1 1 1 1
Ethernet Host repeater Switching/bridging
Host Ethernet Framerelay
(e.g. 802 MAC)

Host
7 7 7 7
ATM IP/SONET 6 6 6 6
Host 5 5 5 5
4 network 4 4
... 4
3 3 3 3 3 3 3
Host Ethernet Host 802.X Host 2 2 2 2 2 2 2 2
Host 1 1 1 1 1 1 1 1

router gateway
Host Host
27 28

Packet Forwarding:
Switch Architecture Address Lookup
Switch
 Takes in packets in one
interface and has to forward Control
them to an output interface Processor
based on the address.
Input Output
» A big intersection Port Port
» Same idea for bridges, switches,
routers: address look up differs Output Input
Port Port
 Control processor manages Switch
the switch and executes Fabric Address Next Hop Info
higher level protocols. Output Output Address from header.
» E.g. routing, management, ..
Port Port B31123812508 3 13 
» Absolute address (e.g. Ethernet)
Input Input 3 - » (IP address for routers)
 The switch fabric directs the Port Port
38913C3C2137

traffic to the right output port. » (VC identifier, e.g. ATM))

 The input and output ports

A21023C90590 0 -  Next hop: output port for packet.
deal with transmission and  Info: priority, VC id, ..
reception of packets.  Table is filled in by routing protocol.
128.2.15.3 1 (2,34)
29 30

5
 Link Flow Control and
Error Control A Naïve Protocol

 Naïve protocol.  Sender simply sends to the receiver whenever it has

 Dealing with receiver overflow: flow control. packets.
 Dealing with packet loss and corruption: error control.  Potential problem: sender can outrun the receiver.
» Receiver too slow, buffer overflow, ..
 Meta-comment: these issues are relevant at many
layers.  Not always a problem: receiver might be fast enough.
» Link layer: sender and receiver attached to the same “wire”
» End-to-end: transmission control protocol (TCP) - sender and
receiver are the end points of a connection
 How can we implement flow control?
» “You may send” (windows, stop-and-wait, etc.)
» “Please shut up” (source quench, 802.3x pause frames, etc.)
» Where are each of these appropriate? Sender Receiver

31 32

Adding Flow Control Window Flow Control

 Stop and wait flow control: sender waits to send the  Stop and wait flow control results in poor throughput
next packet until the previous packet has been for long-delay paths: packet size/ roundtrip-time.
acknowledged by the receiver.  Solution: receiver provides sender with a window that
» Receiver can pace the receiver it can fill with packets.
» The window is backed up by buffer space on receiver
 Drawbacks: adds overheads, slowdown for long links.
» Receiver acknowledges the a packet every time a packet is
consumed and a buffer is freed

Sender Receiver Sender Receiver

33 34

Dealing with Errors

Bandwidth-Delay Product Stop and Wait Case
RTT  Packets can get lost, corrupted, or duplicated.
Sender » Error detection or correction turns corrupted packet in lost or
correct packet
 Duplicate packet: use sequence numbers.
 Lost packet: time outs and acknowledgements.
» Positive versus negative acknowledgements
» Sender side versus receiver side timeouts
 Window based flow control: more aggressive use of
sequence numbers (see transport lectures).
Receiver
Time

Window Size
Max Throughput = Sender Receiver
Roundtrip Time

35 36

6
 What is Used in Practice? Datalink Layer Architectures

 No flow or error control.

» E.g. regular Ethernet, just uses CRC for error detection
 Flow control only.
» E.g. Gigabit Ethernet
 Flow and error control.
» E.g. X.25 (older connection-based service at 64 Kbs that
guarantees reliable in order delivery of data)
 Packet forwarding.  Media access
 Error and flow control. control.
 Scalability.

37 38

Fiber Distributed Data Interface

Multiple Access Protocols (FDDI)
 One token holder may send,
 Prevent two or more nodes from transmitting with a time limit.
» known upper bound on delay.
at the same time over a broadcast channel.
» If they do, we have a collision, and receivers will not be  Optical version of 802.5
able to interpret the signal token ring, but multiple
packets may travel in train:
 Several classes of multiple access protocols. token released at end of
» Partitioning the channel, e.g. frequency-division or time frame.
division multiplexing
– With fixed partitioning of bandwidth – not flexible
 100 Mbps, 100km.
» Taking turns, e.g. token-based, reservation-based  Optional dual ring for fault
protocols, polling based tolerance.
» Contention based protocols, e.g. Aloha, Ethernet  CDDI: FDDI over unshielded
twisted pair, shorter range

39 40

Other “Taking Turn”

Protocols

 Central entity polls stations, inviting them to

transmit.
» Simple design – no conflicts
» Not very efficient – overhead of polling operation
 Stations reserve a slot for transmission.
» For example, break up the transmission time in
contention-based and reservation based slots
– Contention based slots can be used for short
messages or to reserve time
– Communication in reservation based slots only
allowed after a reservation is made
» Issues: fairness, efficiency

41