Chapter 11 데이터 링크 제어 (Data Link Control).

Presentation on theme: "Chapter 11 데이터 링크 제어 (Data Link Control)."— Presentation transcript:

1 Chapter 11 데이터 링크 제어 (Data Link Control)

2 11장 데이터 링크 제어 11.1 프레임 짜기 11.2 흐름 및 오류 제어 11.3 프로토콜 11.4 잡음없는 채널
프레임 짜기 흐름 및 오류 제어 프로토콜 잡음없는 채널 잡음 있는 채널 HDLC 점-대-점 프로토콜 요약

3 11.1 프레임 짜기(FRAMING) 데이터 링크층은 비트들을 프레임 안에 만들어 넣어 각 프레임이 다른 프레임과 구분 되도록 해야 한다. 우편 시스템은 일종의 프레임 짜기의 예를 수행한다고 할 수 있다. 봉투에 편지를 넣는 간단한 행위로 인해 봉투가 분리 기능을 함으로써 서로 다른 정보가 뒤섞이지 않도록 하는 것이다. 주요 내용: 고정 길이 프레임 짜기 가변 길이 프레임 짜기

4 프레임 짜기 1. 고정 길이 프레임 2. 가변 길이 프레임 문자 중심 프로토콜 비트 중심 프로토콜

5 고정 길이 프레임 가변 길이 프레임 고정 길이 또는 가변 길이 - 예 : ATM 광역네트워크의 셀(cell)
- 주로 LAN에서 사용 - 프레임이 끝나는 곳과 다음 프레임이 시작하는 곳 지정

6 문자 중심 프로토콜 전달되는 데이터는 코딩 시스템의 8비트 문자(부록 A) 시작과 마지막에 플래그 추가
문자 중심 프로토콜 프레임

7 바이트 채워 넣기(stuffing) 와 빼내기(unstuffing)
정보 내에 플래그로 사용되는 패턴이 있을 경우 이를 플래그로 오인하지 않게 하기 위한 것

8 바이트 채워넣기는 텍스트에 플래그나 ESC 문제가 있을 때 여분의 1 바이트를 추가하는 처리이다.

9 비트 중심 프로토콜 Bit-oriented protocol 프레임의 데이터 부분을 전부 bit 열로 인식
플래그는 “ ”비트 패턴 사용 비트 중심 프로토콜의 프레임

10 비트 채워 넣기는 수신자가 데이터 속에 있는 “01111110”을 플래그로 오해하지 않도록 “0” 다음에 연속되는 “1”이 다섯 개 있으면 여분의 “0” 비트를 추가하는 처리이다.

11 비트 채워넣기(stuffing)와 빼내기(unstuffing)

12 11.2 흐름 제어와 오류 제어 데이터 링크층의 가장 중요한 책무는 흐름 제어(flow control)와 오류 제어(error control)이다. 총체적으로 이 기능들을 데이터 링크 제어(data link control)라고 한다. 주요 내용: 흐름 제어 오류 제어

13 흐름 제어는 송신자가 확인응답을 받기 전에 보낼 수 있는 데이터의 양을 제한하기 위해 사용하는 일련의 절차이다.
데이터 링크층의 오류 제어는 데이터 재전송을 요구하는 ARQ를 기반으로 한다.

14 11.3 프로토콜 이제 데이터 링크층이 한 노드로부터 다른 노드로 데이터를 보내기 위해 어떻게 프레임 짜기, 흐름 제어 및 오류 제어를 수행하는지 알아보자. 이러한 프로토콜들은 보통 프로그램 언어를 사용하여 소프트웨어로 구현된다. 구현 언어에 좌우되지 않기 위해서 언어 규칙에 구애 받지 않고 절차 자체를 설명하기 위해 각 프로토콜을 의사 코드를 사용하여 설명한다.

15 이 장에서 논의된 프로토콜의 종류

16 11.4 잡음없는 채널 우선 프레임 손실도 없고 복제되지도 않으며 손상되지 않는 이상적인 채널을 가정하자. 이러한 종류의 채널에 대해서는 두 개의 프로토콜을 소개한다. 주요 내용: 가장 단순한 프로토콜 정지 후 대기 프로토콜

17 흐름이나 오류 제어 없는 가장 단순한 프로토콜 설계

18 가장 단순한 프로토콜의 송신측 알고리즘

19 가장 단순한 프로토콜의 수신측 알고리즘

20 예제 11.1 그림 11.7은 이 프로토콜을 사용하는 통신의 예이다. 매우 간단한 것을 볼 수 있다. 송신자는 일련의 프레임을 수신자와 무관하게 보낸다. 세 개의 프레임을 보내기 위해서는 송신자 쪽에서는 세 개의 이벤트가 발생하고 수신자 쪽에서도 세 개의 이벤트가 발생한다. 데이터 프레임은 경사진 상자로 나타내져 있으며 상자의 높이가 처음 비트와 마지막 비트의 전송 시간의 차이를 보여준다.

21 그림 11.7 예제 11.1의 흐름도

22 정지 후 대기 프로토콜

23 정지-후-대기 프로토콜의 송신측 알고리즘

24 정지-후-대기 프로토콜의 수신측 알고리즘

25 예제 11.2 그림 11.9는 이 프로토콜을 사용하는 통신의 한 예를 보여준다. 여전히 매우 간단하다. 송신자는 프레임을 하나 보내고 수신자로부터 확인응답을 기다린다. ACK가 도달하면 송신자는 다음 프레임을 보낸다. 이 프로토콜에서 프레임을 두 개 보내는 데는 송신자에게는 네 개의 이벤트가 발생되고 수신자에게는 두 개의 이벤트가 발생한다는 것에 유의하라.

26 그림 11.9 예제 11.2의 흐름도

27 잡음있는 채널 정지 후 대기 프로토콜이 어떻게 흐름 제어를 더 할 것인지에 대한 아이디어를 제공하지만 잡음없는 채널은 존재하지 않는다. 오류를 무시할 수 있거나 또는 오류 제어를 우리 프로토콜에 추가해야 한다. 본 절에서는 오류 제어를 사용하는 세 개의 프로토콜을 논의 한다. 주요 내용: 정지-후 대기 ARQ Go-Back-N ARQ 선택적 반복 ARQ

28 정지-후-대기 ARQ에서 오류 제어는 전송된 프레임의 사본을 가지고 있다가 타이머가 종료되면 프레임을 재전송 한다.

29 그림 정지-후-대기 ARQ 프로토콜 설계

30 알고리즘 11.5 정지-후-대기 ARQ 송신 측 알고리즘

31 알고리즘 11.5 정지-후-대기 ARQ 송신 측 알고리즘
(계속)

32 알고리즘 11.6 정지-후-대기 ARQ 프로토콜의수신 측 알고리즘

33 예제 11.3 그림 11.11은 정지 후 대기 ARQ의 예를 보여준다. 0번 프레임이 전송되어 확인응답을 받는다. 1번 프레임이 손실되어 타임아웃 이후에 재전송된다. 재전송된 1번 프레임이 확인응답되고 타이머가 멈춘다. 0번 프레임이 전송되고 확인응답받지만 응답 프레임이 손실된다. 송신자는 자기 프레임이 손실되었는지 확인응답 프레임이 손실되었는지 알지 못하며 0번 프레임을 다시 보내는데 이번에는 확인응답이 도달한다.

34 그림 예제 11.3의 흐름도

35 예제 11.4 정지 후 대기 ARQ에서 회선의 대역폭이 1 Mbps이고 1 비트가 왕복하는데 20ms가 소요된다고 가정하라. 대역폭-지연 곱은 얼마인가? 시스템의 데이터 프레임의 길이가 1,000비트라면 회선의 가용도는 얼마인가? 해답 대역폭-지연 곱은 다음과 같다.

36 예제 11.4(계속) 이 시스템은 송신자로부터 데이터가 수신자에게 전달되고 다시 수신자로부터 송신자로 돌아오기까지 20,000 비트를 보낼 수 있다. 그러나 시스템은 오직 1000 비트만을 전송한다. 우리는 이 회선의 가용도는 오직 1000/20000 즉 5%라고 할 수 있다. 이와 같은 이유에서 높은 대역폭을 갖거나 긴 지연 시간을 갖는 회선에서는 정지 후 대기 ARQ는 회선의 용량을 낭비하는 셈이다.

37 만일 예제 11.4에서 응답에 무관하게 15개의 프레임을 전송할 수 있는 프로토콜이 있다면 가용도는 어떻게 되는가?
예제 11.5 만일 예제 11.4에서 응답에 무관하게 15개의 프레임을 전송할 수 있는 프로토콜이 있다면 가용도는 어떻게 되는가? 해답 대역폭-지연 곱은 여전히 20,000비트이다. 시스템은 15개의 프레임 즉 15,000비트를 왕복 지연 시간 동안에 전송할 수 있다. 이는 가용도가 15000/20000 즉 75%라는 것을 의미한다. 물론 손상된 프레임을 재전송해야 하므로 가용도는 많이 떨어지게 된다.

38 N 복귀 프로토콜에서 순서번호는 모듈로 2m 인데, 여기서 m은 비트 단위의 순서 번호 필드의 길이이다.
Go-Back-N 프로토콜 N 복귀 프로토콜에서 순서번호는 모듈로 2m 인데, 여기서 m은 비트 단위의 순서 번호 필드의 길이이다.

39 그림 Go-Back-N ARQ의 송신 창

40 송신 창은 세 개의 변수 Sf , Sn, Ssize 를 갖는 크기가 2m − 1 인 가상의 상자를 정의하는 추상적인 개념이다.
송신 창은 적법한 확인응답이 도착하면 하나 또는 그 이상의 틈새를 밀어낼 수 있다.

41 그림 Go-Back-N ARQ 수신 창

42 수신 창은 한 개의 변수 Rn을 갖는 크기가 1인 가상 상자를 정의하는 추상적인 개념이다

43 그림 Go-Back-N ARQ의 설계

44 그림 Go-Back-N ARQ 창 길이

45 N 복귀 ARQ에서는 송신 창의 크기는 2m 보다 작아야 하며 수신 창의 크기는 항상 1이다.

46

47 47

48

49 예제 11.6 그림 11.16은 N 복귀의 예이다. 전향 채널은 안정적이지만 반대 방향 채널은 그렇지 못한 경우의 예이다. 데이터 프레임은 유실되지 않았지만 어떤 ACK 프레임들은 지연되고 하나는 유실되었다. 이 예는 또한 응답이 지연되거나 유실된 경우에 어떻게 누적 확인응답이 문제를 해소하는지도 보여준다. 초기화 이 후에 일곱 개의 송신자 이벤트가 있었다. 요청 이벤트들은 네트워크에서 온 데이터에 의해 시작되며 도달 이벤트들은 물리층에서 온 응답에 의해 시작된다. 여기서는 타임아웃 이벤트는 없는데 이는 모든 미해결 프레임들이 타이머가 만료되기 전에 확인응답되기 때문이다. 비록 2번 ACK가 유실되었지만 3번 ACK가 2번 및 3번 ACK의 구실을 하는 것에 유의해라. 네 개의 수신자 이벤트가 있는데 모두 물리층에서 프레임이 도착하면 동작한다.

50 그림 예제 11.6의 흐름도

51 예제 11.7 그림 11.17은 프레임이 손실될 때 무슨 일이 일어나는지 보여준다. 0번, 1번, 2번 및 3번 프레임이 전송되었다. 그러나 1번 프레임이 손실되었다. 수신자는 2번과 3번 프레임을 받지만 이들 프레임은 순서가 바뀌어(1번 프레임을 기다리는데) 도달했기 때문에 그냥 버려진다. 송신자는 1번, 2번 및 3번 프레임의 확인응답을 받지 못한다. 결국 타이머가 만료된다. 송신자는 모든 미해결 프레임들을 다시 보낸다(1번, 2번 및 3번). 1번부터 3번까지의 프레임을 다시 보내는 것은 한 개의 이벤트에 대한 응답이라는 것에 유의하라. 송신자가 이 이벤트에 응답할 때는 다른 이벤트에 의해 동작되는 것을 받아들일 수 없다. 이는 2번 ACK가 도달할 때 송신자는 여전히 3번 프레임을 보내느라 바쁘다.

52 예제 11.7(계속) 물리층은 이 이벤트가 다 완료되어 데이터 링크층이 다시 휴지 상태에 들어갈 때까지 기다려야 한다. 지연을 나타내기 위해 수직선을 보여주고 있다. 3번 ACK에 대해서도 같은 이야기가 성립하나 3번 ACK가 도달할 때는 송신자의 2번 ACK에 대해 응답하는 중이다. 4번 ACK 도달할 때도 같은 일이 생긴다. 두 번째 타이머가 만료되기 전에 모든 미결 프레임들이 전송되었으며 타이머는 멈추게 된다는 것에 유의하라.

53 그림 예제 11.7에 대한 흐름도

54 정지 후 대기 ARQ는 송신 윈도우 크기가 1인 N 복귀 ARQ의 특별한 경우이다.

55 그림 11.18 Selective Repeat ARQ의 송신 창

56 그림 11.19 Selective Repeat ARQ의 수신 창

57 그림 11.20 Selective Repeat ARQ의 설계

58 그림 11.21 Selective Repeat ARQ, 창 크기

59 선택적 반복 ARQ에서는 송신 창과 수신 창의 크기는 최대 2m의 절반이다.

60 (continued)

61 (continued)

62

63

64

65 그림 11.22 Selective Repeat ARQ에서 데이터 전달

66 예제 11.8 이 예는 1번 프레임이 유실되는 예제 11.3과 유사하다. 선택적 반복이 이 경우에 어떻게 동작하는지를 보여준다. 그림 11.23은 이러한 상황을 보여준다. 주요 차이 하나는 타이머의 개수이다. 여기서는 각 전송되거나 재전송되는 프레임마다 타이머가 필요하며 이는 타이머에 번호를 붙일 필요가 있다는 것을 말한다. 0번 프레임을 위한 타이머는 첫 번째 요청에 따라 시작되지만 이 프레임의 ACK가 도달하면 멈춘다. 1번 프레임을 위한 타이머는 두 번째 요청에 따라 시작되어 NAK가 도달하면 다시 시작하여 결국 ACK가 도달하여 멈춘다. 다른 두 개의 타이머는 해당 프레임이 전송되면서 시작하여 마지막 도달 이벤트 시점에서 멈춘다.

67 예제 11.8(계속) 수신자 쪽에서는 프레임을 받는 것과 네트워크층에 보내진 것을 구별할 필요가 있다. 두 번째 도달 이벤트에 2번 프레임이 도달하며 이 프레임을 보관하여 표시해 두지만(색칠해 둔 칸) 1번 프레임이 아직 도달하지 않았으므로 네트워크층에 보내지는 않는다. 다음 번 도달에서 3번 프레임이 도착하며 1번 프레임의 사본이 드디어 도착하면 1, 2, 3번 프레임을 네트워크층에 보낼 수 있게 된다. 네트워크층으로 보내기 위한 두 개의 조건이 있다. 우선 일련의 연속된 프레임들이 도착하여야 한다. 두 번째로 그 일련의 프레임은 창의 시작점에서부터 시작한다는 것이다. 첫 번째 도착 이후에 오직 하나의 프레임만 있으며 창의 앞에서부터 시작한다. 마지막 도착 이후 세 개의 프레임이 있으며 첫 번째 것이 창의 앞에서부터 시작한다.

68 예제 11.8(계속) 또 다른 중요한 점은 두 경우 모두 유사해 보이지만 NAK가 세 번째 도착 이후가 아닌 두 번째 도착 이후에 보내진다는 것이다. 그 이유는 이 프로토콜은 불필요한 NAK와 재전송되는 프레임으로 네트워크가 번잡하지 않도록 하려하기 때문이다. 두 번째 NAK 또한 송신자로 하여금 1번 프레임을 다시 보내도록 알리기 위해 1번 NAK를 기억하여(nakSent 변수를 사용하여) 프레임 수신으로 인해 창이 밀려 움직이기 전에는 다시 보내지 않는다. NAK는 각 창의 위치마다 한 번만 보내지며 창의 첫 번째 칸을 지정한다.

69 예제 11.8(계속) 다음 요점은 ACK에 관한 것이다. 여기서는 오직 두 개의 ACK만 보내진 것에 유의하라 첫 번째 ACK는 오직 첫 번째 프레임에 대해서만 확인응답한 것이나 두 번째 것은 세 개의 프레임을 응답한다. 선택적 반복에서는 데이터가 네트워크층에 보내지고 나서 전송된다. 만일 n개의 프레임이 한꺼번에 보내졌으면 오직 한 개의 ACK를 보내 그 모든 프레임에 대해 확인응답한다.

70 그림 예제 11.8의 흐름도

71 그림 11.24 Go-Back-N ARQ에서 피기백킹 설계

72 HDLC 고급 데이터 링크 제어(HDLC, High-level Data Link Control)는 점-대-점과 다중점 링크상에서 반이중 통신과 전이중 통신 모두를 지원하도록 설계된 실제 프로토콜이다. HDLC는 본 장에서 논의한 ARQ 장치를 구현한 것이다. 주요 내용: 구성과 전송 모드 프레임 제어 필드

73 그림 정규 응답 모드

74 그림 비동기 균형 모드

75 그림 HDLC 프레임

76 그림 서로 다른 프레임 유형의 제어 필드 형식

77

78 예제 11.9(계속) 그림 11.29는 어떻게 U-프레임을 사용하여 연결 설정과 해제를 하는지를 보여준다. 노드 A가 일련의 SABM 프레임을 사용하여 설정을 요청하고 노드 B는 이에 UA 프레임을 사용하여 긍정 응답을 보내는 것에 유의하라. 이 교환 이후에 두 노드들 사이에서 데이터 교환이 일어날 수 있다. 데이터 전달 이후에는 노드 A는 DISC 프레임을 보내 연결을 해제하며 노드 B는 UA 프레임을 보내 이에 응답한다.

79 그림 연결과 연결 해제 예

80 예제 11.10 그림 11.30은 피기백킹(piggybacking)을 사용하여 데이터를 교환하는 것을 보여준다. 지극 A는 프레임 번호가 0인 I-프레임으로 정보 교환을 시작하며, 프레임 번호 1인 I-프레임이 뒤따른다. 지국 B는 B의 I-프레임에 A의 두 프레임에 대한 확인 응답을 보낸다. 지국 B의 첫 번째 I-프레임은 N(S) 필드에 프레임 번호 0을 가지며, N(R) 필드는 A에서의 프레임 0, 1의 수신을 확인응답하고 다음에 도착할 프레임이 프레임 2라는 것을 나타내도록 2를 가진다. 지국 A로부터 추가로 프레임을 받기 전에 지국 B는 두 번째와 세 번째 프레임(프레임 번호 1, 2)을 전송한다.

81 예제 11.10(계속) N(R)정보는 변하지 않는다. B의 프레임 1, 2는 지국 B가 여전히 다음에 도착할 A의 프레임 2를 기대하고 있음을 나타낸다. 지국 A는 모든 데이터의 전송을 완료하였으므로, I-프레임을 이용한 피기백킹은 할 수 없고, 대신 S-프레임을 전송하여 확인응답을 보내게 된다. RR부호는 지국 A가 여전히 수신할 준비가 되어 있음을 나타낸다. 이 프레임의 N(R) 필드의 숫자 3은 지국 A가 프레임 0, 1 과 2를 수신했으며 이제 프레임 3을 기대하고 있음을 지국 B에게 알려준다.

82 그림 오류 없는 피기백킹 예

83 예제 11.11 그림 11.31은 데이터를 교환하되 프레임이 유실된 경우를 보여준다. 앞의 예에서 지국 B에서 지국 A로 보낸 프레임 1에 오류가 발생했다고 가정하자. 시스템이 N 복귀 프로토콜을 사용한다는 것에 유의하라. 지국 A는 지국 B에게 프레임 1과 2를 재전송하도록 알려야만 한다. 지국 A는 프레임 1의 오류를 알리기 위해 거부(REJ) S-프레임을 보낸다.

84 예제 오류 있는 피기백킹 예

85 11.7 점-대-점 프로토콜 HDLC는 점-대-점 및 다중점 구성 모두에서 사용될 수 있는 일반적인 프로토콜이지만 가장 널리 사용되는 점-대-점 연결 프로토콜은 PPP(Point-to Point) 프로토콜이다. 주요 내용: 프레임 짜기 천이 단계 단계 다중화 다중링크

86 그림 PPP 프레임 형식

87 PPP는 바이트 중심 프로토콜로서 탈출 문자 0111110을 사용하여 바이트 채우기를 한다.

88 그림 천이 단계

89 그림 PPP에서 다중화

90 그림 프레임에 캡슐화된 LCP 패킷

91

92

93 그림 PPP 프레임에 캡슐화된 PAP 패킷

94 그림 PPP 프레임에 캡슐화된 CHAP

95 그림 PPP 프레임에 캡슐화된 IPCP 패킷

96

97 그림 11.39 PPP 프레임에 캡슐화된 IP 데이터그램

98 그림 다중링크 PPP

99 예제 11.12 PPP 연결이 임의의 네트워크층 패킷을 전달할 때 겪는 상태를 예로 보자. 그림 11.41은 네트워크 패킷 전달의 천이 단계를 보여주고 있다. 사용자 사이트에서부터 시스템 사이트까지 데이터의 단방향 이동임을 추측 할 수 있다(ISP를 통해 e메일을 전송하는 것처럼) . 먼저 처음 두 프레임은 링크 설정을 나타낸다. 그림에서 나타나진 않지만 인증을 위한 PAP 사용여부와 주소 제어 필드를 제어하는 두 개의 옵션을 보여 준다. 세 번째와 네 번째 프레임은 인증에 필요하고 다섯 번째 여섯 번째 프레임은 IPCP를 사용하는 네트워크 계층 연결 설정에 필요하다.

100 예제 11.12(계속) 다음의 몇몇 프레임들은 일부 IP 패킷이 PPP 프레임에서 캡슐화 된다는 것을 보여준다. 시스템(또는 수신자)는 네트워크 계층 프로토콜에서 사용되기도 하지만 수신된 데이터는 데이터 전송 이전에 사용된 NCP 프로토콜이 IPCP이기 때문에 IP 프로토콜에서 지연 되어야 한다는 것을 알고 있다. 데이터 전송 후에 사용자는 시스템으로부터 허용된 데이터 링크 연결을 종료한다. 사용자나 시스템이 다른 NCP 프로토콜을 사용하고 싶다면 네트워크 계층 IPCP를 종료하고 데이터 링크 계층 실행을 유지하기 위한 결정을 해야 한다.

101 그림 예제

102 그림 예제(계속)

103 11.8 요약 Q & A 103

104 연습문제 풀이해서 Report로 다음 주까지(일주일 후) 제출해 주세요! 알림