[17] CH5 Link 계층 < 서론, 오류검출 및 정정 >

< 링크 계층에서의 용어 >

 - 링크 계층 프로토콜을 실행하는 장치를 노드라고 한다.  Node : Host, Router, WIFI

 - 통신 경로상의 인접한 노드들을 연결하는 통신 채널을 링크라한다. 유선link , 무선link

 - 제 2계층 packet을 frame이라 부른다. Datagram을 캡슐화한다.

 

Data-link계층은 한 노드에서 다른 이웃 노드로 link를 통해 datagram을 전달하는 책임을 진다. 

 

- Datagram은 link별로 다른 link protocol을 통해서 전달할 수 있다. 

- Link protocol별로 다른종류의 service를 제공할 수도 있다. 

 

교통 운송과의 비교 

여행객 = datagram , 교통운송 구간 = 통신 link , 운송방식 = link계층 protocol , 여행사 직원 = routing algorithm

 

< 링크 계층이 제공하는 서비스 >

 - 프레임화 : 거의 모든 링크 계층 프로토콜은 네트워크 계층 데이터그램을 링크상으로 전송하기 전에 링크 계층 프레임에 캡슐화 한다. 프레임은 네트워크 계층 데이터그램이 들어 있는 데이터 필드와 여러 개의 헤더 필드로 구성 

 

- 링크 접속 : 매체 접속 제어(MAC) 프로토콜은 링크상으로 프레임을 전송하는 규칙에 대해서 명시한다. 공유매체(shared medium)인 경우엔 매체접속 제어 수행한다. 출발지와 목적지를 인지하기 위해서 frame header내의 "MAC"주소가 사용됨(이는 IP주소와 다르다.)

 

- 신뢰적 전달 : 링크 계층 프로토콜이 신뢰적 전달 서비스를 제공하는 경우 네트워크 계층 데이터그램은 링크상에서 오류 없이 전달한다. 트랜스포트 계층의 신뢰적 전달 서비스와 마찬가지로 확인응답(acknowledgment)과 재전송을 통해 가능해진다. 광섬유나 일부 동축케이블과 같은 bit오류율이 낮은 경우에는 거의 사용X, 오류율이 높은 무선 link등에서 사용된다. 

 

- 흐름 제어 : 송신 node의 전송속도를 수신 node의 수신속도에 맞춤 

 

- 오류 검출 : 신호 감쇄나 잡음에 의해 발생. 수신 node는 오류 발생을 감지해 송신 node에게 재전송을 요청한다. 

- 오류 정정 : 수신 node는 오류 발생을 인지하고 재전송 없이 그 오류를 정정함

 

Half duplex : link의 양 node는 모두 전송할 수 있지만 동시에 전송하지는 않음 

Full duplex : link의 양 node는 동시에 전송할 수 있다. 

 

< Link 걔층은 어디에 구현되는가 >

 - 모든 host에 구현된다. 

 - Link 계층은 "adaptor"에 구현된다.(NIC라 부른다.)

 - Host의 system bus에 연결된다. 

 - Hardware, software, firmware가 결합되어 있는 형태 

 

< Adaptor의 통신 >

송신 node : Frame안에 datagram을 캡슐화 한다. 오류 검출 bit를 추가한다. rdt기능 및 흐름제어 등을 수행한다. 

 

수신 node : 오류 점검,rdt 및 흐름제어 등을 수행한다. Datagram을 분리해 꺼내어 상위 계층에 전달한다. 

 

 

< 오류 검출 >

EDC = 오류 검출 및 정정bit 

D = 오류 검사에 의해 보호되는 data(header field도 포함될 수 있다.)

 

비트 오류를 방지하기 위해 송신 노드에서 데이터 D에 오류 검출 및 정정 비트(EDC)를 첨가한다. 수신자는 자신이 수신한D'과EDC'만으로 원래의 D가D'가 동일한지 결정한다. 

오류 검출은 100%신뢰할 수는 없다.! protocol은 일부 오류를 발견하지 못할 수도 있으나 이는 매우 드물다. EDC field가 클수록 오류 검출과 정정 능력이 뛰어나다. 

 

< 패리티 검사 >

가장 단순한 형태의 오류 검출은 단일 패리티 비트의 사용. 하지만 2bit 오류가 발생한다면 오류 검출 불가.

 

< checksum 방법 >

- Transport 계층(UDP,TCP)

 Header field와 data field 모두 한꺼번에 묶어서 checksum 계산 

 

- IP 계층

 IP header에 대해서만 오류 검출 수행(UDP와 TCP segment이 자체 checksum을 지녔으므로)

 

< 순환중복검사(CRC) >

 - Data bit들(D)은 이진수로 간주한다.

 - r+1 bit pattern의 생성기(generator)G를 선택 

 - 목표 : 크기 r의 CRC bit들(R)을 다음과 같이 선택

           -  <D,R>은 G로 나뉘어야 함

           - 수신 node는 G를 알고 있음. 수신된<D,R>을 G로 나누어 봄. 만약 나머지가 0이 아니면 오류 발견!

           - r+1 bit 개수보다 작은 모든 오류를 검출할 수 있다. 

 - 실제 시스템에서 널리 사용됨 

 

d비트로 이루어진 데이터 D를 송신 노드가 수신노드로 전송하고자 한다고 가정하자. 먼저 송신자와 수신자는 G로 표기되는 생성자로 알려진 r+1 비트 패턴에 대해서 합의한다. G의 최상위 비트는 1이여야 한다. 

 

주어진 데이터D에 송신자는 r개의 추가 비트 R을 선택해서 D의 뒤에 덧붙이며, 이 d+r비트 패턴은 모듈로-2 연산을 이용하면 G로 정확히 나누어 진다. 만일 나머지가 0이 아니면 오류를 발견된 것이다. 

 

모든 CRC검사는 덧셈의 올림(carry)나 뺄셈의 빌림(borrow)없는 모듈로-2 연산을 사용한다. 이것은 덧셈과 뺄셈이 동일함을 뜻하며 XOR연산과 동일하다. (1이 하나면 1출력)

일반 이진연산에서처럼 2**k를 곱하는 것은 비트 패턴을 k개의 위치만큼 왼쪽으로 이동시키는 것이다. 따라서 주어진 D,R에 대해서 D*2**k XOR R은 위 그림과 같이 d+r비트 패턴을 만든다. 

 

< CRC 예시 >

송신자가 어떻게 R을 계산하는지 알아보자. 먼저 다음과 같은 식을 만족하는 n이 있도록 하는 R을 구해야 한다. 

D.2r XOR R = nG

즉, D.2r XOR R을 나머지 없이 G로 나눌 수 있도록 R을 선택해야 한다. 이 식의 양쪽에 R을 XOR하면 다음과 같다.

D.2r = nG XOR R

이 식은 D*2**R을 G로 나누면 나머지가 정확히 R이 되는 것을 뜻한다. 다시말해서 위처럼 R을 계산할 수 있다. 

 

위 예시는 D=101110 , d=6, G=1001, r=3인 경우에 대한 계산 예시이다. 이 경우에 전송되는 9개 비트는 101110011이다.

 

D*2**r = 101011*G XOR R인지 확인해보자.