CHAP 3. The Data Link Layer: Part 1

강의내용 - Stalling책

• Chap 6. 오류검출 및 정정

Chap 7. 데이터링크 제어 프로토콜

• 강의 내용

- Data Link Layer 개념: 인접한 Machine간('Link')에 어떻게 'Data'를 전달할 것인가?

(c.f.: Physical Layer: Machine간에 어떻게 물리적인 'Signal'을 전달할 것인가?)

- 기능

*① Framing

② Flow Control

③ Error Control

Topics

• Computer Network

S

S

R

RR

R

R

R

R

S

S

S

S

KNUE

충북대

KREN

leased line

NSFNet

U. C. at

Berkeley

U. C. at

L. A.

210.93.99.64

Data Link Layer

- host-router

- router-router

Network Layer

- host-host

S

202.31.104.1

• Purpose: "reliable", "efficient" communication bet. two "adjacent" machines.

⇒ 인접한 Machine간('Link')에 어떻게 Data를 Error없이, 효율적으로 전달할 것인가?

(Stallings 10th ed.) p.346 Fig. 11.3  (WAN: D.L layer, LAN: LLC)

(Stallings 7th ed.) p.564 Fig. 15.5

• Functions of Data Link Layer

① Framing: 어떻게 '데이터‘의 전송 단위(frame)를 구분할 것인가?

⇒ Start & End of a frame

- Error detection & correction: 어떻게 frame의 error를 탐지할 것인가?

⇒ Checksum & ARQ (Automatic Repeat Request)

(ex) frame format:

(Stallings 10th ed.) p.233 fig.7.7 - FCS (Frame Check Sequence)

② Flow control: frame을 어떻게, 얼마나 보낼 것인가?

⇒ sliding window protocol

③ Error control: Error 발생시 어떻게 조치를 취할 것인가?

⇒ stop-and-wait/go-back-N/selective repeat

• Frame transmission

Sender:

① Breaks the data up into discrete frames.: "Framing"

② Computes the checksum for each frame and adds it to the frame.

③ Sends the frame. : "Flow-control"

Receiver:

④ The checksum is recomputed. : "Error-detection & correction"

⑤ IF the newly computed checksum is different from the one	contained in the received frame,

THEN  Discard the "bad" frame

ELSE Send O.K. message (ACK, acknowledgement)

Sender:

⑥ IF ACK is received, send the new frame

ELSE (time-out) Retransmit the old frame. : "Error-control"

(Stallings 10th ed.) p.219 Fig. 7.1

(Stallings 7th ed.) p.248 Fig. 7.1, p.269 Fig. 7.9

Framing

• How to mark the start and end of a frame.

⇒ "Synchronization" bet. the sender and the receiver.

• Starting and Ending Flags with Bit Stuffing

- Idea: Each frame begins and ends with a special bit pattern.

Flag: 01111110 (SYNC)

(Stallings 10th ed.) p.233 Fig. 7.7

- What if SYNC appears in the data?

⇒ Bit stuffing

□A sender stuffs a 0 bit into 5 consecutive 1's in the data.

If the receiver sees 5 consecutive incoming 1 bits followed by a 0 bit,

it deletes the 0.

⇒ No SYNC in the data.

(Stallings 10th ed.) p.234 Fig. 7.8

(Stallings 7th ed.) p.263 Fig. 7.7, p.264 Fig. 7.8

Error Detection & Correction

• Error detection method

- Inserting "error-detecting" codes: Insert enough info. to allow the receiver to deduce that an error "occurred", and have it request a "retransmission".

⇒ ARQ (Automatic Repeat Request) protocol

(ex) a single parity bit in ASCII:

Used for "single" bit error detection not "double" error.

(Stallings 10th ed.) p.195: 패리티 비트

• CRC (Cyclic Redundancy Code)

- W. Peterson and D. Brown, "Cyclic Codes for Error Detection", Proceedings of the IRE, Jan. 1961

- Polynomial(다항식) code: Treat a bit string as representation of a polynomial with coefficients of 0 and 1 only.

(ex)  1 1 0 0 0 1 ⇔ x5 + x4 + 1

- Modulo 2 polynomial arithmetic을 사용:

No "carries" for addition and No "borrows" for subtraction.

(ex)	1 0 0 1 1 0 1 1	1 1 1 1 0 0 0 0

+	1 1 0 0 1 0 1 0	-	1 0 1 0 0 1 1 0

0 1 0 1 0 0 0 1	0 1 0 1 0 1 1 0

⇔ Both addition and subtraction are identical to XOR (Exclusive OR)

(같으면 0, 다르면 1)

- Idea

① The sender and receiver must "agree" upon a degree r generator polynomial, G(x) in advance.

⇒ Both the high- and low-order bits of the G(x) must be 1.

② Append a checksum to the end of the frame in such a way that the polynomial represented by the checksummed frame is "divisible" by G(x).

③ When the receiver gets the checksummed frame, it tries dividing it by G(x).

④ If there is a "remainder", there has been a transmission "error".

(Stallings 10th ed.) p.192 Fig. 6.1, p.194 Fig. 6.2

(Stallings 7th ed.) p.210 Fig. 6.3

- The algorithm for computing checksum

① Let r be the degree of G(x). Append r zero bits to the lower-order end of the frame, M(x), so it now contains m+r bits and corresponds to the polynomial xr․ M(x).

② Divide the bit string corresponding to G(x) into the bit string corresponding to xr․ M(x) using modulo 2 division.

③ Subtract the remainder from the bit string corresponding to xr․ M(x) using modulo 2 subtraction. The result is the "checksummed frame" to be transmitted, T(x).

(Stallings 10th ed.) p.198 - p.200 Example

(Stallings 7th ed.) p.212 Example

- How to represent an error:

Case 1: No error

Arrive T(x)	T(x)/G(x) … remainder = 0 ; O.K.

Case 2: Error

Arrive T(x) + E(x)	{T(x) + E(x)}/G(x)

= T(x)/G(x) + E(x)/G(x)

"Always divisible"	"E(x)가 G(x)를 인수로

갖고 있으면 divisible"

Each 1 bit in E(x) corresponds to a bit that has been "inverted".

If there are k 1 bits in E(x), k single bit errors occurred.

(ex)	T(x)	= 1 1 1 0  (x3 + x2 + x)

+  E(x)	=   1   1   (    x2     + 1)

T(x) + E(x)	= 1 0 1 1  (x3      + x + 1)

- What kind of error can be detected by CRC with G(x)?

All of the following are NOT divisible by G(x) and hence are "detectable".

(즉, E(x)가 G(x)를 인수(factor)로 가질 수 없는 경우들은 모두 검출 가능함.)

⇒ (Stallings 10th ed.) p.202

(Stallings 7th ed.) p.214

① All single bit errors

(pf) E(x) = xi for some i. (i 번째 bit에서 error가 발생)

For G(x), both the first and last terms must be non-zero.

∴G(x) has at least "two" terms and can NOT divide "one" term, E(x).

② All double bit errors, as long as G(x) has a factor with at least three terms.

(pf) E(x) = xi + xj , i > j. (i 와 j 번째 bit에서 error가 발생)

= xj ․(xi-j + 1)

G(x) must divide either xj or (xi-j + 1).

But, it does NOT divide xj, and

it can be shown that it does NOT divide (xi-j + 1) EXCEPT for very "large" values of i - j beyond the practical frame length.

(ex) (xk + 1), k<32768의 경우 G(x) = x15+xi4+1로 나눌 수 없음.

③ Any "odd" no. of errors as long as G(x) contains a factor (x+1).

(pf) Proof by "contradiction". (모순법 - 홀수개의 항은 x+1으로 나누어지지 않음을 증명함.)

Assume that E(x) has an "odd" no. of terms AND is "divisible" by (x+1).

Then, E(x) = (x+1)․F(x)

E(1) = (1+1)․F(1) = 0 since 1+1 = 0 (∵modulo 2 addition)

But, E(1) = 1 since E(x) has an odd no. of terms.  (ex) 1+1+1 = 1

∴ The assumption is wrong.

즉, E(x)가 홀수개의 항을 갖고 있으면 (x+1)을 인수로 가질 수 없다.

그런데, G(x)가 x+1을 인수로 갖고 있으므로, E(x)는 G(x)로 나누어지지 않는다.

④ Any "burst"(연속) error for which the length of the burst is "less than" the length of G(x).

(pf) E(x) = xi․(xk-1 + … + x + 1) ; k 개의 연속 error, xi 는 위치를 표시.

We known that G(x) does NOT divide xi.

For k<n where n is the length of G(x),

G(x) will NOT divide (xk-1 + … + 1), since G(x) is of "higher" order. (G(x)의 차수는 n-1)

(ex)	T(x)	= 1 0 1 0 1 1 ; sender가 보낸 frame

T(x) + E(x)	= 1 1 0 1 1 1 ; receiver가 받은 frame

E(x) =   1 1 1	; x4 + x3 + x2 = x2․(x2 + x + 1)

단항이므로 G(x)로 나누어지지 않음.

G(x)보다 차수가 작으면 나누어지지 않음

⑤ Most "larger" burst errors.

(pf) E(x) = xi․(xr + … + x + 1)  ; r+1 개의 연속 error의 경우

The prob. that E(x) is divisible by G(x) is 1/2r-1,

if all error patterns are considered "equally likely".

(즉, r+1 개의 연속 error의 경우, E(x)가 G(x)로 나누어질 확률 = 1/2r-1)

For a longer burst, the prob. is 1/2r [Peterson, 1961]

- International standard

① CRC-12: x12 + x11 + x3 + x2 + x + 1

② CRC-16: x16 + x15 + x2 + 1

16-bit checksum

③ CRC-CCITT: x16 + x12 + x5 + 1

(Comite Consultatif International de Telegraphique et Telephonique)

⇒ All three contain (x + 1) as a prime factor.

- A simple shift register circuit calculates the checksum in "H/W".

⇒ Not a big delay.

(Stallings 10th ed.) p.203, p.235

(Stallings 7th ed.) p.217 Fig. 6.5