1) Character count: • This framing method uses a field in the header to specify the number of characters in the frame
Computer and Data Networks, 3 Date Link Layer Framing – Character count (b) Four examples of byte sequences before and after stuffing
Computer Communication Networks Lecture No 6 Computer Network Lectures 1- Data link Layer:- For example, if the character count of 5 in the second
24 jui 2021 · 1 Implementing the data link layer framing methods i Character count 2 Character Stuffing and destuffing 3 Bit Stuffing
When the data link layer at the destination sees the character count, it knows how many characters follow and hence where the end of the frame is This
To provide service to the network layer, the data link layer must use the service example, if the character count of 5 in the second frame of Fig
The trouble with this algorithm is that the count can be garbled by a transmission error For example, if the character count of 5 in the second frame of fig (b)
If ETX appears in the data introduce a special character DLE (Data No bit or byte stuffing ? Example: ? Synchronous Optical Network (SONET)
23 nov 2021 · Include the character count in the header of the frame Example: the byte-oriented Digital Data Communications
Character count with some other mechanisms 4 Physical Layer Coding Violation A Flag Byte or Byte Stuffing: Examples ® “To stop input please enter X and
Computer Network Lectures To provide service to the network layer, the data link layer must use the For example, if the character count of 5 in the second
Computer and Data Networks, 3 Date Link Layer 1 Framing – Character count A character (b) Four examples of byte sequences before and after stuffing
COMPUTER NETWORKS FOURTH (b) Four examples of byte sequences before and after stuffing embedding the character code length in the framing
CSE 123: Computer Networks Same as bit stuffing, except at byte (character) level ♢ Kind of like Phy-layer signaling: sample at specific intervals ♢
PDF document for free
- PDF document for free
43798_3cdn_slides_3.pdf
Computer and Data Networks, 3. Date Link Layer
1
©Dr.Z.Sun
3. The Data link layer
Computer and Data Networks, 3. Date Link Layer
2
©Dr.Z.Sun
Outline
n
Link layer services
n
Framing
n
Error correction and detection codes
n
Error and flow control: Slide window protocols
n HDLC n
SLIP and PPP
Computer and Data Networks, 3. Date Link Layer
3
©Dr.Z.Sun
Functions of the Data Link Layer
Relationship between packets and frames.
Computer and Data Networks, 3. Date Link Layer
4
©Dr.Z.Sun
Link layer services
n
Unacknowledged connectionless
n
Acknowledged connectionless
n
Acknowledged connection-oriented
n
Framing
n
Error control
n
Flow control
Computer and Data Networks, 3. Date Link Layer
5
©Dr.Z.Sun
Framing methods:Four methods:n
Character count
n
Flag bytes with bytes stuffing
n
Starting & ending flags with bit stuffing
n
Physical layer coding violations
Computer and Data Networks, 3. Date Link Layer
6
©Dr.Z.Sun
Framing - Character count
A character stream. (a)Without errors. (b)With one error.
Computer and Data Networks, 3. Date Link Layer
7
©Dr.Z.Sun
Framing - Flag bytes and byte stuffing
(a)A frame delimited by flag bytes. (b)Four examples of byte sequences before and after stuffing.
Computer and Data Networks, 3. Date Link Layer
8
©Dr.Z.Sun
Framing - bit stuffing
Bit stuffing
(a)The original data. (b)The data as they appear on the line. (c)The data as they are stored in receiver"s memory after destuffing.
Computer and Data Networks, 3. Date Link Layer
9
©Dr.Z.Sun
Error correction codes
n
Codeword = message + redundant
n
If two codewords are a Hamming
distanced apart, it will require d single- bit error to convert one into the other n
To detect d errors, you need a distance
of d+1 code n
To correct d errors, you need a distance
2d+1 code
n
Example: parity bit (even or odd)
Hamming method: (m+r+1)<=2
r n power of 2 (1,2,4, ...) check bits n the rest (3,5,6,7,9, ...) data bits n example bit 11 checked by (1,2,8)
Computer and Data Networks, 3. Date Link Layer
10
©Dr.Z.Sun
Assume Xi are data bits and Ri data bits
n
X3 corresponds to R1 and R2
n
X5 corresponds to R1 and R4
n
X6 corresponds to R2 and R4
n
X7 corresponds to R1, R2 and R4
n
X9 corresponds to R1 and R8
n
X10 corresponds to R2 and R8
n
X11 corresponds to R1, R2 and R8
n
R1 corresponds to {X3, X5, X7,
X9, X11}
n
R2 corresponds to {X3, X6, X7,
X10, X11}
n
R4 corresponds to {X5, X6, X7}
n
R8 corresponds to {X9, X10,
X11} n Example: m = 1101101 => ?? 1 ? 101 ? 101 => 11 10 101 0101 n
If the receiving node received: 11 10 1
11
1 0101
=> R1 = 1, R2 = 0 , R4= 1 , R8 =0 => 0(1) + 1(2) + 1(4) + 0(8) = 66
This implies that bit 6 is incorrect, as it is checked by R2 and R4
Computer and Data Networks, 3. Date Link Layer
11
©Dr.Z.Sun
Error detection codes
Polynomial code (cyclic redundancy code
or CRC code)n
Let r be the degree of generator
polynomial G(x). Append r zeros to the low-order end of the frame M(x) => x r M(x). n
Divide the bit string corresponding to
G(x) into the bit string corresponding to
x r
M(x) using modulo 2 division
n
Subtract the remainder from the bit
string corresponding to x r
M(x) using
modulo 2 subtraction. The results is the check-summed frame called polynomial T(x).
Computer and Data Networks, 3. Date Link Layer
12
©Dr.Z.Sun
Stop-and-wait and slide window protocol
n
Stop-and-wait ARQ: the sender sends a frame and
waits for acknowledgement before sending any further frame. There are two sorts of errors: sending and acknowledgement. n How about efficiency (stop and wait or window size is 1)? Satellite link is 50 kbit/s, round trip time 500 ms, frame size 1000 bits, frame transmission time 20 ms.
Efficiency = 20/(20+500) =1/26
n Slide window protocolallows the sender sends more frames up to a window size before stopping and waiting for acknowledgment
Computer and Data Networks, 3. Date Link Layer
13
©Dr.Z.Sun
Go Back N and Selective repeat
n
Pipe line technique: channel
capacity is B bit/s, frame size L, round-trip time R.
Channel Efficiency = L/(L+BR)
If L< BR the efficiency will be less
than 50%. n
Two techniques trade-off
bandwidth and buffer space
Go back to N(receive window = 1)
only receives frame in order and retransmit all frames after errors.
Selective repeatbuffers frames and
retransmit only the errored frame.
Computer and Data Networks, 3. Date Link Layer
14
©Dr.Z.Sun
Window size and Negative acknowledgment
n NAK acknowledges when frame damaged or unexpected (potential lost frame) n The maximum window size should be at most half of the range of the sequence number (Max_Seq+1)/2 n Trade-off risk of unnecessary retransmission, or idle for a long period after errors n Standard deviation of acknowledgment is small, the timer can be set "tight". Otherwise "loose".
Computer and Data Networks, 3. Date Link Layer
15
©Dr.Z.Sun
High-level Data link Control (HDLC)
n
Bit oriented and bit
stuffing n
2x8 bits for framing
n
8 bit address field identify
multiple terminals n
Control field can be used
for three types of frames: information, supervision and unnumbered. n
Data field
n
16 bits for CRC error
check
Computer and Data Networks, 3. Date Link Layer
16
©Dr.Z.Sun
Internet SLIP and PPP protocols
n Serial Line IP (SLIP):no error detection and correction, support only IP, need to know IP address in advance, no authentication, not a proved Internet standard. n Point-to-Point protocol (PPP):handles no error detection, support multiple protocol, address can be negotiated at connection time, permit authentication, many improvement over SLIP
Computer and Data Networks, 3. Date Link Layer
17
©Dr.Z.Sun
PPP frame format (character oriented)
n
Closely resemble HDLC frame format
n
Character oriented
Default for
unnumbered frame
0: Net layer protocol
1: otherDefault is 2.
Default is 1500.
Normally 2 but
can be negotiated for 4.
Default
Computer and Data Networks, 3. Date Link Layer
18
©Dr.Z.Sun
Summary
n
Link layer services
n
Framing
n
Error control
•
Error correction and Error detection
n
Flow control
•
Stop-and-wait, slide window
•
Go back N, Selective repeat, Negative
Acknowledgement
n
Dial-up protocols for Internet access
•
HDLC and PPP
Computer Networks Documents PDF, PPT , Doc