Transcript Data-link Layer and Protocols

NETE0510
Data-link Layer and Protocols
Dr. Supakorn Kungpisdan
[email protected]
NETE0510: Communication Media and Data
Communications
1
Outline
 Encoding Techniques
 Data Link Layer Fundamental
 Direct-link Protocols
BSC, DDCMP, HDLC, PPP
NETE0510: Communication Media and Data
Communications
2
Signal Encoding Techniques
NETE0510: Communication Media and Data
Communications
3
Encoding Schemes
NETE0510: Communication Media and Data
Communications
4
Bit rate and Baud rate
 Bit rate or data rate: number of bits transmitted
over a period of time (bit per second)
 Baud rate: number of symbols transmitted over
a period of time (baud)
NETE0510: Communication Media and Data
Communications
5
Non-return to Zero-Level (NRZ-L)
 two different voltages for 0 and 1 bits
 voltage constant during bit interval
no transition I.e. no return to zero voltage
such as absence of voltage for zero (0 V), constant
positive voltage for one (+5V)
more often, negative voltage (-5 V) for one value and
positive (+5 V) for the other
NETE0510: Communication Media and Data
Communications
6
Problems of NRZ-L
 Long sequence of 0s or 1s signal leads to “baseline
wander”
 Receiver maintains baseline of detecting 0 or 1
 Too many 0s or 1s cause this baseline to change
 Clock synchronization
 Frequent transitions of signals are necessary to enable clock
recovery
 Every clock cycle the sender transmits a bit and the receiver
recovers a bit
 Slightly difference in clocks at either sender and receivers may
cause a problem
NETE0510: Communication Media and Data
Communications
7
Non-return to Zero Inverted (NRZI)
 nonreturn to zero inverted on ones
 constant voltage pulse for duration of bit
 data encoded as presence or absence of signal
transition at beginning of bit time
 transition (low to high or high to low) denotes binary 1
 no transition denotes binary 0
 example of differential encoding since have
 data represented by changes rather than levels
 More example of different encoding: Different Manchester
 more reliable detection of transition rather than level
 easy to lose sense of polarity
NETE0510: Communication Media and Data
Communications
8
Manchester Encoding





has transition in middle of each bit period
transition serves as clock and data  no need to send clock
low to high represents one (1), high to low represents zero (0)
used by IEEE 802.
Both 0s and 1s result in a transition to the signal, the clock
can be effectively recovered at the receiver
NETE0510: Communication Media and Data
Communications
9
Differential Manchester Encoding
 midbit transition is clocking only
 transition at start of bit period representing 0
 no transition at start of bit period representing 1
this is a differential encoding scheme
 used by IEEE 802.5 (Token Ring)
NETE0510: Communication Media and Data
Communications
10
Problems of Manchester Encoding
 Double the rate at which signal transition are
made on the link  the receiver has half the
time to detect each pulse of the signal.
Bit rate is half of baud rate  encoding is only 50%
efficient
NETE0510: Communication Media and Data
Communications
11
4B/5B
 Used together with other encoding techniques
 Used in 100Base-TX transmission
 The idea is to insert extra bits into the bit stream so as to
break up long sequences of 0s and 1s
 Every 4 bits of actual data are encoded in a 5-bit code 
4B/5B
 Each 5-bit code has no more than one leading 0s and no
more than two trailing 0s.
 No pair of 5-bit codes results in more than three
consecutive 0s  solve problem of many consecutive 0s
 Then the 5-bit codes are then transmitted using the NRZI
encoding
 NRZI already solved the problem of consecutive 1s  so 4B/5B
results in 80% efficiency
NETE0510: Communication Media and Data
Communications
12
4B/5B Encoding
 4-bit data is encoded into 5-bit
code
 “One leading 0, two trailing 0s”
rule
 16 codes used, left the other 16
codes for other purposes
 Code 00000  line is dead
 Code 1111 line is idle
 Code 00100  halt
 7 of them violates the rule
 The other 6 represent control
symbols
NETE0510: Communication Media and Data
Communications
13
Outline
 Encoding Techniques
 Data Link Layer Fundamental
 Direct-link Protocols
BSC, DDCMP, HDLC, PPP
NETE0510: Communication Media and Data
Communications
14
Data Link Layer
 Because of transmission errors, or because the receiver
may need to regulate data rate, it is necessary to have a
layer of control communication devices
 Need layer of logic above Physical to manage exchange
of data over a link
 Frame synchronization: beginning and end of each frame
must be recognizable
 Flow control: sender must not send frames at a rate faster
that the receiver can absorb them
 Error control: correct bit errors
 Addressing: identify involving communication parties
 Control and data: receiver can distinguish control
information from transmitted data
 Link management: initiation, maintenance, and termination
NETE0510: Communication Media and Data
Communications
15
Flow Control
 ensure sending entity does not overwhelm
receiving entity
by preventing buffer overflow
 influenced by:
transmission time
 time taken to emit all bits into medium
propagation time
 time for a bit to traverse the link
NETE0510: Communication Media and Data
Communications
16
Stop and Wait
 source transmits frame
 destination receives frame and replies with
acknowledgement (ACK)
 source waits for ACK before sending next
 destination can stop flow by not send ACK
 works well for a few large frames
 Stop and wait becomes inadequate if large block
of data is split into small frames
NETE0510: Communication Media and Data
Communications
17
Sliding Windows Flow Control





allows multiple numbered frames to be in transit
receiver has buffer W long
transmitter sends up to W frames without ACK
ACK includes number of next frame expected
sequence number is bounded by size of field (k)
 frames are numbered modulo 2k
 giving max window size of up to 2k - 1
 must send a normal acknowledge to resume
 Piggybacking: insert acknowledgement number field in
data frame so that a frame can contain both sequence
number and ACK numbers
NETE0510: Communication Media and Data
Communications
18
Sliding Window Diagram
NETE0510: Communication Media and Data
Communications
19
Error Control
 detection and correction of errors such as:
lost frames
damaged frames
 common techniques use:
error detection
positive acknowledgment (ACK)
retransmission after timeout
negative acknowledgement (NAK) & retransmission
NETE0510: Communication Media and Data
Communications
20
Automatic Repeat Request (ARQ)
 collective name for such error control
mechanisms, including:
 stop and wait
 go back N
 selective reject (selective retransmission)
NETE0510: Communication Media and Data
Communications
21
Stop and Wait
 source transmits single frame
 wait for ACK
 if received frame damaged, discard it
transmitter has timeout
if no ACK within timeout, retransmit
 if ACK damaged,transmitter will not recognize it
transmitter will retransmit
receive gets two copies of frame
use alternate numbering and ACK0 / ACK1
NETE0510: Communication Media and Data
Communications
22
Stop and Wait
see example with both
types of errors
 pros and cons
simple
inefficient
NETE0510: Communication Media and Data
Communications
23
Go Back N
 based on sliding window
 if no error, ACK as usual
 use window to control number of outstanding
frames
 if error, reply with rejection
discard that frame and all future frames until error frame
received correctly
transmitter must go back and retransmit that frame and
all subsequent frames
NETE0510: Communication Media and Data
Communications
24
Go Back N - Handling
 Damaged Frame
error in frame i so receiver rejects frame i
transmitter retransmits frames from i
 Lost Frame
frame i lost and either
 transmitter sends i+1 and receiver gets frame i+1 out of
seq and rejects frame i
 or transmitter times out and send ACK with P bit set which
receiver responds to with ACK i
transmitter then retransmits frames from i
NETE0510: Communication Media and Data
Communications
25
Go Back N - Handling
 Damaged Acknowledgement
receiver gets frame i, sends ack (i+1) which is lost
acks are cumulative, so next ack (i+n) may arrive before
transmitter times out on frame i
if transmitter times out, it sends ack with P bit set
can be repeated a number of times before a reset
procedure is initiated
 Damaged Rejection
reject for damaged frame is lost
handled as for lost frame when transmitter times out
NETE0510: Communication Media and Data
Communications
26
Selective Reject
 also called selective retransmission
 only rejected frames are retransmitted
 subsequent frames are accepted by the receiver and
buffered
 minimizes retransmission
 receiver must maintain large enough buffer
 more complex logic in transmitter
 hence less widely used
 useful for satellite links with long propagation delays
NETE0510: Communication Media and Data
Communications
27
Go Back N vs
Selective
Reject
NETE0510: Communication Media and Data
Communications
28
Error Detection
 Two-dimensional parity
 Internet checksum
 Cyclic Redundancy Check
NETE0510: Communication Media and Data
Communications
29
Internet Checksum
 Not used in the link layer
 checksum for the internet protocol:
 Sum 16-bit data blocks
 Take one complement of the result to produce the checksum
 E.g. calculate checksum of 5 and 3
 5 (0101) + 3 (0011) = 8 (1000)
 Checksum = -8 (0111)
 Send 5, 3, -8 to receiver  send 010100110111
 Calculate 5+3+(-8)
0101
0011
0111
1111
NETE0510: Communication Media and Data
Communications
30
Outline
 Encoding Techniques
 Data Link Layer Fundamental
 Direct-link Protocols
BSC, DDCMP, HDLC, PPP
NETE0510: Communication Media and Data
Communications
31
BSC (or BISYNC) Protocol
 Binary Synchronous Communication
 Byte-oriented approach: view each frame as a collection
of bytes (characters) rather than a collection of bits
 Support a particular character set: ASCII, EBCDIC, and
IBM’s 6-bit Transcode
NETE0510: Communication Media and Data
Communications
32
Problem of BISYNC
 ETX character may appear in the body of a
frame
 Solved by “character stuffing”  insert a special
character called DLE (data-link-escape)
character whenever it appears in the body
NETE0510: Communication Media and Data
Communications
33
Point-to-point (PPP) Protocol
 Designed to encapsulate IP inter-network data
 Commonly run over dial-up modem links, but can be
used on any leased line for point-to-point connections
not supported by FR or ATM.
 Have character stuffing
 Several of the field sizes are negotiated rather than fixed
 using LCP (Link Control Protocol)
 Two sub protocols: LCP (Link Control Protocol) and NCP
(Network Control Protocol) to negotiate options for a
network-layer protocol running on top of PPP
 IPCP (Internet Protocol Control Protocol) for IP
 IPXCP for IPX, ATCP for AppleTalk
NETE0510: Communication Media and Data
Communications
34
PPP Frame Format




Flag: 011111110
Protocol: identify high-level protocol e.g. IP or IPX
Payload: size is negotiated, default at 150 bytes
Checksum: 2-4 bytes long
NETE0510: Communication Media and Data
Communications
35
LCP
 Negotiation of payload size is conducted by LCP
 Frame payload size can be negotiated, 1500 byte by default
 LCP sends control messages encapsulated in PPP frames
 Such messages are denoted by an LCP identifier in the PPP
Protocol field
 Sizes are changed based on the information contained in those
control messages
NETE0510: Communication Media and Data
Communications
36
PPP (cont’d)
 PPP tends to be reserved for dialup or a mixedvendor environment, whereas HDLC is the default
for T1 serial connections
NETE0510: Communication Media and Data
Communications
37
DECNET’s DDCMP
 Byte-Counting Approach: include number of bytes
contained in a frame as a field in the frame header
 Transmission error can corrupt the COUNT field 
framing error
NETE0510: Communication Media and Data
Communications
38
High-level Data Link Control (HDLC)
 Previously known as Synchronous Data Link Control
(SDLC) protocol
 Most popular data link control (L2) protocol
 Form the basis of ISDN and FR protocols and services
 specified as ISO 33009, ISO 4335
 station types:
 Primary - controls operation of link
 Frames issued are called “commands”
 Secondary - under control of primary station
 Frames issued are called “responses”
 Combined - issues commands and responses
 link configurations
 Unbalanced - 1 primary, multiple secondary
 Balanced - 2 combined stations
NETE0510: Communication Media and Data
Communications
39
HDLC Transfer Modes
 Normal Response Mode (NRM)
 unbalanced config, primary initiates transfer, secondary may
only transmit data in response to a command
 used on multi-drop lines, e.g. host + terminals
 Asynchronous Balanced Mode (ABM)
 balanced config, either station initiates transmission, has no
polling overhead, widely used
 Asynchronous Response Mode (ARM)
 unbalanced config, secondary may initiate transmit without
permission from primary, rarely used
NETE0510: Communication Media and Data
Communications
40
HDLC Frame Structure
 synchronous transmission of frames (no startstop bits required)
 single frame format used
trailer
header
NETE0510: Communication Media and Data
Communications
41
Flag Fields and Bit Stuffing
 delimit frame at both ends with 01111110 sequence
 The sequence is transmitted any time that the link is idle
to keep clock synchronized
 “bit stuffing” used to avoid confusion with data
containing flag sequence 01111110
 0 inserted after every sequence of five 1s
 if receiver detects five 1s it checks next bit
 if next bit is 0, it is deleted (was stuffed bit)
 if next bit is 1 and seventh bit is 0, accept as the end-of-frame
flag
 if sixth and seventh bits 1, sender is indicating abort (error
occurred)
NETE0510: Communication Media and Data
Communications
42
Flag Fields and Bit Stuffing (cont’d)
 In both bit stuff and character stuffing, the size of a frame
is dependent on the data being sent in the payload.
 Not possible to make all the frames exactly the same
size
NETE0510: Communication Media and Data
Communications
43
Address Field
 identifies secondary station that sent or will receive frame
 usually 8 bits long
 may be extended to multiples of 7 bits
 LSB indicates if is the last octet (1) or not (0)
 not needed for point-to-point link
 all ones address 11111111 is broadcast
 Allow primary station to broadcast a frame for reception by all
secondaries
NETE0510: Communication Media and Data
Communications
44
Control Field
 different for different frame type
 Information (I-) frame - data transmitted to user (next layer
up)
 Flow and error control piggybacked on information frames
 Supervisory (S-) frame - ARQ when piggyback not used
 Unnumbered (U-) frame - supplementary link control
 first 1-2 bits of control field identify frame type
NETE0510: Communication Media and Data
Communications
45
Control Field (cont’d)
 use of Poll/Final bit depends on context
 in command frame is P bit set to1 to solicit (poll)
response from peer
 in response frame is F bit set to 1 to indicate response
to soliciting command
 Sequence number in S- and I-frames usually 3 bits
 can extend to 8 bits as shown below
NETE0510: Communication Media and Data
Communications
46
Information & FCS Fields
 Information Field
in information and some unnumbered frames
must contain integral number of octets
variable length
 Frame Check Sequence Field (FCS)
used for error detection
either 16 bit CRC or 32 bit CRC
NETE0510: Communication Media and Data
Communications
47
HDLC Operation
 consists of exchange of information, supervisory
and unnumbered frames
 have three phases
initialization
 by either side, set mode & seq
data transfer
Selective reject
 with flow and error control
 using both I & S-frames (RR, RNR, REJ, SREJ)
disconnect
 when ready or fault noted
NETE0510: Communication Media and Data
Communications
Go Back N reject
48
HDLC
Commands
and
Responses
NETE0510: Communication Media and Data
Communications
49
HDLC Operation Example
Set sync
balanced mode
Send seq no
Receive seq no
busy
A must
respond with
RR or RNR
Unnumbered
acknowledgement
Return from
busy condition
Disconnect
NETE0510: Communication Media and Data
Communications
50
HDLC Operation Example
NETE0510: Communication Media and Data
Communications
51
Questions?
Next Lecture
LANs and Hi-speed LANs
NETE0510: Communication Media and Data
Communications
52