[네트워크] 16. Link Layer Protocol

이제 L2 layer인 데이터 링크 계층에 대해 알아보도록 하겠습니다.

 

Link layer의 PDU는 frame 입니다.

• application layer : message..
• transport layer : segment
• network layer : datagram(packet)
• link layer : frame
• physical layer : bit..

 

link layer는 아래와 같은 service를 제공합니다.

• header, trailer 붙여서 datagram 캡슐화
• MAC 주소를 기반으로 최종 목적지 찾아가기
• reliable delivery : TCP에서 reliable 통신을 배웠습니다. link layer에서도 한번 더 reliable한 통신을 지원합니다.
• flow control
• error detection : 노이즈 등으로 발생한 error를 receiver가 detect하게 되면, retransmission를 요청하거나 drop 합니다.
• error correction : receiver는 error에 대해 correct할 수 있습니다.
• half-duplex and full-duplex : half-duplex는 양쪽 다 전송을 할 수 있지만, 동시에 전송할 수는 없습니다.

 

---

Error detection & correction

Link layer에서 error를 찾고 correct하는 과정을 보도록 하겠습니다.

 

EDC = Error Detection and Correction bit (redundancy)

Error detection은 edc를 통해 error를 찾을 수 있습니다.

하지만 100% 믿을 수는 없고, tcp checksum과 다르게 불필요합니다.

D는 여기서 error check를 통해 보호받는 데이터 입니다.

위와 같은 과정으로 error를 찾고, error가 있다면 다른 처리를, error가 없다면 정상적으로 L3 layer로 올려줍니다.

 

 

Parity checking

error를 찾는 방법으로 parity checking가 있습니다.

 

 

왼쪽처럼 parity bit이 하나만 있고, 5bit씩 잘라서 1의 개수가 짝수인지 홀수인지를 통해 error가 발생했는지 알 수 있습니다.

짝수 parity를 사용한다면, 가로,세로를 세서 1의 개수가 짝수가 되게 만들어 준 후, 최종적으로 두 방향의 parity가 똑같다면 error가 발생하지 않은 것입니다.

 

만약 error bit가 발생한다면 오른쪽처럼 row, column 방향 모두 XOR 연산을 통해 parity error가 정확히 어디서 발생했는지 알아낼 수 있습니다.

parity bit에서 error가 생겨도 똑같이 할 수 있습니다.

 

하지만 error bit가 두 개 이상일 경우, 위 방법은 문제가 됩니다.

또한 EDC에 parity bit들이 붙게 되므로, 이 크기만큼 손해가 발생합니다.(위에선 5+3+1 = 9bit만큼)

이러한 이유로 CRC 방법을 사용합니다.

 

Cyclic redundancy check

parity check와 다르게, CRC는 CRC bit를 여러 개 사용합니다.(r bits)

이 방법을 사용한다면, r + 1 보다 적게 발생한 error에 대해 알 수 있습니다.

 

방법은 아래와 같습니다.

• 통신하는 두 대상 모두 G에 대해 알고 있습니다. (G는 bit 수 마다 패턴이 정해져 있습니다.)
• D를 left shift r번 해줍니다. 이 수를 G로 나눈 값의 나머지는 R이 나옵니다.
• 이 R를 D 뒤에 붙여서 전송합니다.
• EDC가 붙은 D를 받고 G로 나눠보면, 나머지가 0이 나옵니다.

나머지가 0이라면 error가 발생하지 않은 것이고, 아니라면 error가 발생했다는 것입니다.

주의할 점은, 나눗셈을 하는 과정에서 빼기가 아닌 XOR(또는 carry, borrow가 없는 빼기)를 해야하며,

R이 G보다 작지만 계산 과정 상 가장 큰 bit가 0이 아니라면, 나눌 수 있다는 점을 조심해야 합니다.

 

위 노란 예제의 답은 1001이 나옵니다.

 

---

Multiple access links, protocols

link에는 두 가지 종류가 있습니다. 

1. point to point : 1대1로 통신을 합니다(Ethernet switch)
2. broadcast(shared wire or medium) : 모든 link로 데이터를 보냅니다(wifi)

wifi와 같이 signle shared broadcast channel을 Multiple access link라고 합니다.

 

이런 환경에서 만약 동시에 여러 개의 signal을 보내게 되면 collision이 발생합니다.

 

muliple access protocol : 노드들이 채널을 나누어 쓰는 프로토콜

별도의 채널을 사용하지 않고 알고리즘으로 채널을 어떻게 나누어 쓸 지 결정할 수 있습니다.

 

이상적인 상황에서 희망하는 수준(desiderata)는 아래와 같습니다.

• 다른 사람은 사용하지 않고, 한 pair만 사용할 때 rate는 R로 사용 가능합니다.
• M개 노드들이 전송을 할 때, R / M 를 사용합니다.
• fully decentralized : 다른 사항을 고려하지 않는 상황입니다.(클록)

 

이 방법엔 3가지 방법이 있습니다.

1. channel partitioning : n개로 나누는 것입니다.
2. random access : collision을 허용하고, 난수로 사용하는 것입니다. (recover 방법 제시)
3. taking turns : 서로 돌아가면서 채널을 사용하는 방식입니다.

이 3가지에 대해 자세히 알아보도록 하겠습니다.

 

Channel partitioning : TDMA

TDMA(time division multiple access)는 slot을 부여해서 채널을 나누는 것입니다.

 

6개의 slot으로 나눈다면, 각 round마다 해당 slot에서 패킷을 보내게 됩니다.

 

 

Channel partitioning : FDMA

FDMA(frequency division muliple access)는 주파수로 나누어서 특정 주파수 band를 할당시켜 주는 방법입니다.

 

 

(라디오에서 FM, AM이라고 표현하는 것을 들어보셨을 것입니다.)

AM은 진폭을 변조하는 것이고(수직), FM은 주파수를 변조하는 것입니다(수평).

 

 

Random access protocols

random access protocol은 collision을 허용한다고 하였습니다.

만약 혼자서 채널을 사용한다면 collision은 생기지 않을 것입니다.

하지만 두 노드 이상 채널을 사용하면 collision이 발생합니다.

이 collision을 어떻게 발견하고, recover하는 지가 중요합니다.

종류는 slotted ALOHA, ALOHA, CSMA, CSMA/CD, CSMA/CA가 있습니다.

 

 

Random access protocol ( Slotted ALOHA)

슬롯에서 노드가 전송을 하고, collision이 발생하지 않으면 다음 슬롯에서 계속 보낼 수 있습니다.

만약 노드가 전송을 했는데 collision이 발생한다면, 확률 p로 기다리게 됩니다.

처음 c에서 노드 1,2,3,이 모두 전송을 시도했을 때, 각자 random한 시간을 기다리게 됩니다.

이 시간은 똑같은 시간을 기다릴 수도 있기 때문에, 이후 c에서 노드1과 2가 다시 collision이 발생한 것을 볼 수 있습니다.

 

 

 

Pure (unslotted) ALOHA

(pure ALOHA는 slotted ALOHA보다 먼저 나온 방법입니다.)

slot으로 구분하는 것이 아닌, 구간으로 구분하는 것으로, 충돌할 확률이 증가합니다.

위 그림에선 t0에서 보낸 node i frame은 [t0 - 1, t0 + 1]구간에서 보낸 다른 frame과 충돌합니다.

 

두 방식을 비교해보면, slotted ALOHA가 효율이 더 좋다는 것을 알 수 있습니다. (미분을 이용해서 증명)

 

 

CSMA(Carrier sense mulitple access)

이제 wifi에서 사용하는 방식인 CSMA를 알아보도록 하겠습니다.

이 방식은 LBT를 사용합니다(listen before transmit).

다른 노드를 방해하지 않는 선에서 채널을 사용하자!가 목표입니다.

 

 

t1 시점에선 4번째 컴퓨터는 채널이 비어있는 것으로 생각하고 패킷을 전송합니다.

하지만 특정 시점이 지난 이후 collision이 생깁니다.

이 방법의 문제점은 두 가지가 있습니다.

1. collision이 발생하면 패킷 전체가 깨져버립니다.
2. distance, propagation delay가 발생합니다.

이 방법을 보완하기 위해 나온 방법이 CSMA/CD 입니다.

 

 

CSMA/CD(collision detection)

collision을 detect한 시간이 경과한 이후, collision이 발생했다면 jam signal을 보냅니다.

 

관련된 알고리즘을 보도록 하겠습니다.

 

• 채널이 idle이라면, frame 전송을 시작합니다.
• NIC가 모든 frame을 보내는 동안 아무런 collision을 detect하지 못했다면, 성공입니다.
• 만약 frame을 전송 중에 collision을 detect하면, 전송을 중단하고 jam signal을 보냅니다.
• m번째 충돌 이후, 0부터 2^m-1 사이 값중 랜덤한 K값을 선택하고 K * 512 bit time 만큼 기다립니다.(많이 충돌이 생겼을수록 확률적으로 기다리는 시간은 늘어나는 식)

 

 

Taking turns protocol

위에서 배운 두 가지 protocol을 비교해보겠습니다.

• channel partitioning protocol : idle이 안 생길수록 효율이 좋으니 high load일 때 좋습니다.
• random access protocol : collision이 있으니 low load일 때가 좋습니다.

taking turns는 두 가지 장점을 합친 방법입니다.

 

Taking turns protocol은 polling과 token passing 방법 두 가지가 있습니다.

 

polling은 master가 존재하여 poll을 slave에게 주어 전송할 수 있게 합니다.

polling overhead가 발생하며, master가 작동을 하지 않을 때 위험하다는 특징이 있습니다.

 

 

token passing 방법은 master가 없이 token ring을 만들어서 token이 돌면서 보낼 사람을 찾는 방법입니다.

token 이 돌아가는 overhead가 있고, token을 가진 채로 죽어버리면 문제가 생깁니다.

 

---