[ 네트워크 ] MAC protocol ( + ARP )

 

MAC protocol ( + ARP )

 

 

 

multiple access links, protocol

 multiple access links, protocol이라고 하는 것은 layer 2에서 하고 있는 핵심적인 기능 중 하나이다. 유선이든 무선이든 link 있을 때 이 link에 다수의 station 또는 user 단말들이 물려있을 때 어떻게 접속할 것인가. 동시에 같은 리소스를 써서 둘 이상이 접속하게 되면 충돌이 나는데 어떻게 할 것인가를 정하는게 multiple access protocol이다.

 요즘 사용하는 것은 broadcast 기반이다. shared wire인데, 대부분 회사, 학교에서 쓰고있는 유선 인터넷들은 이더넷이라고 하는 유선랜으로 연결되어 있다. 이 유선랜은 cable이 붙어있고 cable에 유선 station이 붙어있다. 내가 어떤 data를 보내면 누구든지 내 signal을 듣게 되고, 그 signal을 들어서 내가 수신인지 보고 아니면 버리는 메커니즘이다.

 무선인 경우에도 마찬가지이고, WiFi protocol을 쓰는 경우에도 마찬가지로 broadcast이다. 위성인 경우도 마찬가지다. 위성에서 어떤 signal을 쏴주게 되면 그 signal은 기본적으로 밑에 있는 단말들은 누구든지 안테나 signal에 들어오게 된다.

 그래서 누구든지 들을 수 있다하면 medium을 shared하는 것이다. 이것을 어떻게 share할 것인지가 multiple access이다.

 

 multiple access 이라고 하는 것은 하나의 share된 broadcast 채널이라는 얘기이다. 물론 두 개 이상이 될 수 있다. 무선이든 유선이든 하나의 채널이 share되고 있는 경우에 두 개 이상이 동시에 전송하게 될 경우 충돌이 난다. 두 개 이상의 signal이 합쳐져서 전달되기 때문에 수신 입장에서는 두개가 합쳐져서 수신되는 것이다. 온전히 수신하지 못하는 상황인 것이다.

 multiple access protocol이라고 하는 것은 distributed된 알고리즘이다. node들이 어떻게 share할지 정해주는 분산 알고리즘이다. 어떻게 나눠서 쓸것인가. channel sharing에 대한 약속을 communication해서 쓸 수 있는데 channel을 어떻게 share할 것인지에 대한 대화를 어떻게 할 것인가. 그것도 그 channel을 사용하게 되는 것이다. 즉, 대부분은 하나의 동일한 채널을 사용하는 것이다.

 

 

 이상적인 multiple access protocol?

 rate가 R bps라고 주어진 어떤 broadcast 채널이 있다하고, 그것을 하나의 node가 혼자 보낸다하면 rate R로 전송하면 되는 것이다. 만약 M개의 node가 전송한다면 평균적으로 R/M rate로 보낼 수 있다면 가장 이상적이다.

 그리고 또 fully decentralized에서 특별한 node가 전송이 돼서 coordinate를 하는 것이 없다고 봐야한다. clock level에서도 특별히 동기화되어 있지 않다고 가정하고 디자인한다.

 마지막으로 simple화하는 것이다.

 

 => 이것들을 만족하는 프로토콜이 있을까?

 

 

 

 

 

 

 MAC protocol : taxonomy

 MAC은 공유된 채널에 다수의 사용자가 접속할 수 있도록 도와주는 정의한 프로토콜이다. MAC 프로토콜은 세가지의 class로 얘기할 수 있다.

 

 

 

1. channel partitioning

 채널을 잘게잘게 쪼개서 channel을 여러 개의 sub channel로 만든다. channel을 잘게 나눠서 하는 approach가 보통 무선 셀룰라 시스템에서 많이 시도해 왔다. time slot으로 쪼개는게 TDMA, frequency로 나눈게 FDMA. code로 쪼개는 게 CDMA. 3세대에서 사용된 셀룰라 시스템이 CDMA 기술을 활용했던 것이다.

 잘게 채널을 나눠서 채널 한개한개를 쓰고자 하는 사용자에게 할당해주면 되곘다고 한 것이다. 다만 이 channel partitioning할 때 channel을 나눠주는 역할을 하는 장치가 필요하다. centralized된 누군가가 해주어야 한다.

 

2. random access

 채널이 쪼개져 있는 것이 아니라 한 개의 채널이 있는데 이것을 누군가가 사용하려고 했을 때 처리해주는 방식이다. 누가 언제 채널에 들어올지 알 수 없어서 random하게 접속한다고 생각한다. 한 개의 station만 접속하면 이 station만 접속하고 성공한다. 문제는 같은 시간에 두 개 이상의 station이 접속해서 충돌이 난다. 그래서 random access는 하나만 보냈을 때 성공하는 방식이다. 그렇다면 충돌이 났을 때 어떻게 할 것인가가 하나의 포인트가 될 것이다.

 

3. taking turns

 서로서로 번갈아가면서 보내도록 하는 방식이다. 이 방식은 간단한데 문제는 참여하고 있는 모든 node들이 항상 보낼게 있다라는 전제 하에서 돌아가는 것이다. 그러면 보내지 않을 때 리소스는 그냥 날라가는 것이다. 이 방식은 좋은 방식이 아니다.

 

 

 

 

 

 

 

Channel partitioning MAC protocol

 

1. TDMA

 

 채널을 시간 단위로 쪼개는 것이다. 6개의 slot으로 이루어진 frame이 있다. 매번 이 frame의 첫번째 slot은 1번 유저가 전송해 줄 수 있게 하겠다라고 정의한 것이다. 매 세번째는 3번이 보내도록 한다. 이렇게 정의해 놓은 것이 TDMA방식이다.

 그래서 TDMA를 잘 쓰려면 이 slot을 누가 쓸 것인지 정해줄 수 있는 장치가 있어야 한다. 셀룰라 시스템에선 기지국이 이런 역할을 했었다. 전화를 건다고 하면 전화를 거는 사용자에게 slot을 한 개 준다. 그 사람이 매번 해당 slot을 이용해서 데이터를 주고 받을 수 있게 한 것이다.

 결국 slot의 개수는 한정이 되는데 이 slot 개수로 동시에 통화할 수 있는 사용자의 수가 정해진다.

 

 

 

2. FDMA

 

 채널을 주파수 별로 쪼개는 것이다. 주파수별로 사용자가 사용할 수 있게 하고 그 주파수로 데이터를 전송할 수 있게 한 것이다. FDM cable 내에서 여러 주파수를 같이 보내더라도, 수신 딴에서 주파수 별로 분리할 수 있다. 그러면 주파수 몇 개가 나오느냐에 따라서 동시에 전송할 수 있는 사용자 수가 나올 것이다.

 앞에서 본 TDMA와 리소스 측면에서는 비슷하나, 실제 시스템을 운영하고 구현하는 측면에서는 다르다. FDMA는 지속적으로 한 사용자에게 bandwidth를 주는 것이기 때문에 리소스를 계속 끊임없이 사용하는 경우에 유리하다. 전화통화, 초창기 1세대 셀룰라 시스템에 사용되었다. 그 다음 FDM cable 유선에서도 이런 기술이 사용되었다.

 

 

 

 

 

 

 

 

 Random access protocols

 어떤 node가 언제 data를 보내야 될지가 명확하지 않다. 이럴 때 전화통화처럼 한 번 채널을 받으면 계속 전송하는 경우에는 사용하면 안된다. 어쩌다가 한 번 보낼 때 사용해야 한다. 맨 처음 전화통화를 걸 때 random access를 한다. 그 때는 채널이 없기 때문에 채널을 달라고 random access를 한 것이다. random access에 성공하면 기지국이 일정한 채널을 하나 주는 것이다.

 random access는 미리 사전에 coordination이 되어 있지 않다는 것이다. 누가 언제 보내는 지 알 수가 없다. 전화통화를 예로 들자면, 기지국에선 누가 언제 전화를 걸지 몰라서 미리 리소스를 할당하지 못한다. 그래서 전화통화를 거는 순간 random access 성공하면 채널을 하나 할당해준다. 운이 없게 둘 이상의 사용자가 리소스를 할당받으면 충돌이 발생한다.

 그래서 random access MAC protocol은 충돌을 어떻게 detection할것인가. 어떻게 recovery할 것인가. 이런 것들을 정의하게 된다. 이런 부분을 어떻게 해결하느냐에 따라서 여러가지 프로토콜이 나오게 된다. ALOHA, slotted ALOHA, CSMA 등등…

 slotted ALOHA는 지금도 이동통신 시스템에서 쓰는 개념이다. CSMA/CD는 유선 LAN에서 쓰는 방식이다. CSMA/CA는 무선 네트워크에서 쓰는 방식이다.

 

 

 

 

1. Slotted ALOHA

 frame들이 같은 사이즈라고 가정하자. 그리고 시간은 똑 같은 size의 slot으로 나눠져 있다고 가정한다. 한 개 frame을 한 개 slot에서 보낸다라고 가정한다. 그리고 node들은 slot의 시작하는 시점을 알고 있어서 sync는 맞춰져 있다고 가정한다. 두 개 이상의 node가 같은 slot에서 전송하면 실패하게 되고, 모든 node들은 충돌을 detect할 수 있다고 가정한다.

 위와 같이 가정했을 때, node가 충돌이 없었다면 아무 문제 없다. 그런데 충돌이 났으면 재전송을 해야한다. 그 node가 바로 이어지는 time slot에서 재전송하면 또 충돌날 것이다. 확률적으로 확률 p로 보낼지 말지 결정한다. 그러면 확률적으로 충돌나는 것을 줄일 수 있다.

 

 

 node 1,2,3이 동시에 frame을 전송해서 충돌이 발생하였다. 그 다음에는 1,2,3 모두 보내지 않기로 결정한다. 그 다음엔 확률을 적용해서 1,2가 보내졌다. 충돌이 났다. 그 다음 확률이 적용돼서 2만 보내졌다. 성공했다. 이런 것을 반복한다. node 1,2,3이 각자 보내는데 9개의 slot을 사용하였다. 사실 순서를 지정해서 보냈으면 3번만 했으면 충분했으나, 누가 언제 보낼 지 알 수가 없다. 그래서 각자 random access를 하다보니 이런 상황이 나오는 것이다.

장점 : 각자가 계속 시도해봐서 전송한 것이다. decentralized된 방식이고, 간단하다.

단점 : 충돌이 나고 slot을 낭비한다. idle한 slot도 있다. node들이 충돌을 바로바로 detection할 수 없기도 하고, clock 싱크도 맞아야 한다.

 

 

 slotted ALOHA의 성능이 얼마나 되는지 계산해보자. 일단 N개의 node가 뭔가를 보내려고 하는 상황에 있다. 확률 p로 보내려고 시도한다. 그러면 어떤 특정 slot에서 성공하려면 확률 p로 하나만 보내져야 한다. N 노드 중에 누구 하나라도 성공하면 되니까 성공할 확률은 Np(1-p)^(N-1) 이다. 확률을 통해서 성공할 확률을 구할 수 있다. 성공하기 위해서 확률 p를 어떻게 해줘야 할까. 최대 효율이 나오게 하는 p를 미분해서 구해보자. N을 무한대로 보내고 계산하면은 최대 효율은 1/e = 약 0.37이 된다. 즉, slotted ALOHA 방식을 썼을 때 최대 37%정도의 시간을 제대로 써서 보낼 수 있다는 말이다.

 

 

 

 

2. Pure ALOHA

 

 slot이 나눠져 있지 않은 ALOHA이다. 싱크도 맞지 않는 경우이다. 이런 경우에도 충돌이 발생하는데, clock이 정해져 있지 않기 때문에 slot에 걸쳐서 충돌이 발생한다. slot의 경우는 어떤 slot 하나만 보내면 성공인데, 이 경우는 slot이 없기 때문에 충돌의 가능성이 높아진다. 충돌이 발생하지 않으려면 노란색의 입장에서는 t0-1부터 t0+1까지 누군가가 보내면 안되는 것이다.

 

 그래서 (1-p)^(N-1)이 두번 곱해지게 되는 것이다. 이것도 역시 N을 무한대로 보내서 계산해보면 최대값이 1/(2e)가 된다. 아까 나왔던 최대값의 절반인 0.18이다. 그래서 slotted ALOHA보다 성능이 많이 떨어진다. 무선 전송 처음 시도하던 1970년대 초창기에 이런 것을 쓰기도 한다.

 

 

 

 

 

3. CSMA

 CSMA (carrier sense multiple access). 유선이든 무선이든 어떤 signal을 전달해서 전송할 수 있는 것을 carrier라고 한다. carrier를 sense할 수 있다. 전송하기 전에 channel을 listen할 수 있다. 지금 누가 데이터를 보내고 있는가 아닌가를 들어볼 수 있다. 그래서 channel이 idle하다고 보이면 전송시도 하는 것이다. 그런데 sense했더니 누군가가 보내고 있으면 busy하다고  보고 전송을 미루는 것이다.

 

 CSMA에서 충돌이 발생한 상황. 예시를 보면 아무도 안 보낸다고 해서 t0에 노란색이 전송을 시작한다. signal이 propagation delay가 있어 점점 퍼져나가는 그림을 띈다. 그리고 t1이라는 시간에 idle하다고 봐서 빨간색이 전송을 시도한다. 전송을 하는데 좀 있다가 봤더니 충돌이 났다. 이 충돌이 감지가 되면 충돌이 났다고 알게된다.

 그렇다면 이 충돌을 어떻게 처리해줄까?

 

 

 

CSMA/CD

 충돌을 detection 할 수 있는 경우는 CSMA/CD라는 프로토콜을 사용한다. 아주 짧은 시간 내에 충돌을 detection할 수 있는 방식이다. 충돌이 난 경우에 전송을 취소한다.

 이런 방식은 유선 LAN에서 사용할 수 있다. 일단 충돌난 것을 바로 detection 할 수 있는데 그 이유는 유선방식에선 siganl 강도를 측정할 수 있으니까 내가 보낸 signal 대비 받는 signal을 측정해서 충돌여부를 검사할 수 있다.

 무선에서는 쉽지 않다. 무선에서는 보통 보내는 것이 받는 것보다 파워가 더 크기 때문에 누군가가 동시에 전송했다 하더라도 내가 보내는 것에 압도 되어서 저쪽에서 누군가가 동시에 보낸 게 정확하게 detection이 잘 안됨. 그래서 무선 LAN인 경우에는 CSMA/CD를 쓰지 않는다.

 

 

 CSMA/CD 알고리즘

1. NIC에서 datagram을 상위계층에서 받는다.

2. NIC가 channel이 idle한지 본다. idle한 것이 sense 됐으면 전송한다. 만약 busy하다면 idle해질 때까지 기다린다. idle이면 전송한다.

3. idle이여서 전송하였다.

4. 보냈는데 만약에 다른 detection이 됐다면 바로 취소해야 한다. 취고하고 jam signal이라는 것을 보낸다.

5. 충돌이 났으니까 바로 이어서 보내면 또 충돌날 것이니 한 템포 쉬었다가 보낸다. 다음 보내는 것은 확률 p로 정하는데 어떤 확률로 보낼 것인지 정해주는 protocol이 있다. 바로 binary backoff 방식이다. 어떤 충돌이 났을 때 0에서 3까지의 숫자를 뽑는다. 뽑은 시간만큼을 기다렸다가 재전송한다. 만약 0을 뽑았으면 바로 전송하고 3을 뽑으면 3번 쉬는 것이다. 그런데 idle을 기다리는 얘들이 많을 수도 있다. 이러면 0에서 3까지 뽑으면 같은 숫자를 뽑아 다시 충돌날 확률이 높다. 그래서 다시 충돌이 나면 0에서 7까지 뽑는다. 그래도 또 충돌이 많이 난다면 다시 0에서 15까지 뽑는다. 결국 가장 작은 수를 뽑은 얘가 한 개여서 그 얘가 성공할 때까지 진행한다. 최대로 1023까지 늘어난다. 1023까지 해보고 계속 충돌이 난다면 취소한다. 이것은 충돌이 문제가 아니라 네트워크의 문제라고 보는 것이다.

 

(참고) 이러한 CSMA/CD의 효율성은 ALOHA보다는 높다는 걸 알아두자.

 

 

 

 

 

 

 

 

 

 Taking turns MAC protocol

이 때까지 살펴본 protocol의 단점

1. channel partitioning MAC protocol

 서로 순서를 바꿔가면서 하는 방식이다. channel이 아주 공평하게 나눠서 쓸 수 있는 방식이다. 그러나 load가 낮은 상황에서는 효율성이 떨어질 수 있다. channel 10개가 있는데 쓰는 사람이 나밖에 없으면 channel 10개 쓰면 전송률 높을텐데 channel 하나만 쓰니 전송률은 그냥 1/n 상태이니 효율이 떨어질 수 있다.

2. random access MAC protocol

 random access는 low load에서는 효율적이다. load가 적을 때는 누군가가 random하게 가져가서 쓰면 된다. 그런데 high load인 경우에 충돌이 막 발생할 테니 어느정도 load가 넘어가면 random access는 동작하기 어렵다.

 

 

그렇다면 이제 Taking turns 방식을 살펴보자

 

polling

1. polling

 순서를 돌려가면서 쓰는 방식이다. 이런 방식 중에 polling이라는 방식이 있다. polling은 master node가 있어서 여러 slave node들한테 master가 너 데이터 보낼래? 라는 call을 던져서 데이터를 보내게 한다.

 그러나 이런 경우에 polling overhead가 있고, polling을 해서 전송해야 하니까 그만큼의 lateny도 있다. 그리고 master가 문제 있으면 전송이 되지 않는 문제가 발생한다.

 

 

 

 

token passing

2. token passing

 

 token을 넘겨주는 token passing이라는 방식이 있다. 어떤 control token을 순차적으로 넘겨주는 것이다.

1. token을 보내줬는데 보낼게 없다.

2. token을 넘겨준다. data를 보내준다.

그러나 token을 돌리는 overhead가 있고, token을 기다리는 latency가 있을 수 있다. token 방식에 문제가 생기면 실패할 수도 있다.

 

 

 

 

 

 

 

 

 

Cable access network

 집에 인터넷 설치를 하고 있으면 대부분 유선 cable을 통해서 들어오고 있을 것이다. 그러면 집에 들어온 cable은 TV랑 컴퓨터랑 전화기가 물려있는 경우가 있다. 이런 경우에 인터넷하고 TV의 channel들은 data가 다른 주파수로 분리돼서 날라간다. 올라가는 경우에도 마찬가지로 다른 주파수를 써서 보낸다.

 downstream : 우리집으로 내려오는 경우.

 upstream : 우리집에서 올라가는 경우.

보통 downstream이 많아서 bandwidth가 크다. 이 때 downstream은 아무 문제 없다. 왜냐하면 controller가 다른 주파수를 가진 데이터를 적절히 섞어서 보내면 되기 때문이다. 우리집 수신기는 받기만 하면 된다.

 문제는 upstream일 경우에 생긴다. 우리집만 있는게 아니라 여러 집이 같은 bandwidth를 통해 보내야 한다. 이게 충돌날 수 있는 문제이다. 이런 충돌을 해결하기 위해 각각 집에서 CMTS에게 리소스를 달라고 요청하면서 upstream 해야 한다는 것을 CMTS에 알려준다. 그래서 CMTS에서 리소스를 할당해주는 방식이다.

 

 

 

 

 

 

LANs

 주소는 IP뿐만 아니라 MAC에서도 주소가 있다. MAC 또는 LAN 또는 physical address라고도 한다.

 어떤 실제 물리적인 network card나 ethernet card가 있을 때 card의 실제 물리적인 주소가 필요하다. IP주소를 할당하기 전에 식별할 무언가가 필요하다. 즉 network에 아직 물려 있지 않은 상황에서 이 card를 식별할게 필요하다. 그래서 물리적으로 연결된 interface를 구분하기 위한 무언가가 필요하다.

 이것을 MAC address라고 한다. 48bit이고 대부분 network card들은 MAC address를 고유하게 가지고 있다. 제조사에서 만든 것이기에 전세계의 MAC address 중 고유한 주소를 갖게 된다. 16진수로 표기한다.

 cmd - ipconfig /all - 물리적 주소 에 나와있다. 복수개가 있을 수 있는데, 이것은 WiFi card에 대한 주소가 있을 수 있고, 유선 card에 대한 주소가 있을 수 있다. network card마다 물리적인 주소가 있다.

 

 

 

 

 

 local area network에 물릴 때는 물리적 주소만 가지고 network 내에서 식별해주면 된다. 이 내부에서는 굳이 IP주소를 할당해 줄 필요가 없다.

 

 제조사가 MAC address의 일정 부분을 사서 부여한다. IP주소와 MAC주소를 비유로 보자면, MAC주소는 주민등록번호고, IP주소는 집주소이다. 그러면 이 집주소의 이 주민등록번호를 가진 사람이 살고 있다. 이 사람이 이사를 가면 IP주소는 바뀌지만 주민등록번호는 바뀌지 않는다. MAC과 IP의 주소 관계를 형성시켜주는 protocol이 필요하다. 바로 ARP라는 것이다.

 (참고) LAN card를 다른 컴퓨터에 옮길 수 있고, 다른 local area로 갈 수도 있다. MAC 주소는 옮겨갈 수 있느나, IP는 옮길 수 없다.

 

 

 

 

 

 

ARP : address resolution protocol

 MAC 주소가 어떻게 IP주소를 알까? 이것을 해결해주는 프로토콜이다. ARP table은 LAN에 연결된 각각의 node가 가지고 있다.

<IP address; MAC address; TTL>

 

 여기서 TTL은 매핑관계가 고정되어 있다고 생각하지 않아, 20분 마다 갱신하도록 하기 위해 있다. 그래서 20분 마다 이 매핑이 유효한지 체크한다. 그래서 각각의 host는 MAC 주소와 IP주소가 부여되어 있다.

 

 

 

 

 

 

 ARP protocol : same LAN

 A가 B한테 datagram을 보내려고 한다. B의 MAC 주소가 A의 ARP table에 없을 때 어떻게 할까? A가 ARP 쿼리 패킷을 broadcast한다. B의 IP주소를 가지고 MAC address를 물어보는 것이다. 그러면 destination MAC address는 FF-FF-FF-FF-FF-FF 이다. 이것은 network 내에 있는 누구나 수신 가능하다는 뜻이다. 모든 node들이 이 쿼리를 받는다. B가 받으면 A한테 MAC address를 담은 채 reply를 보내준다.

 A는 B에 대한 IP와 MAC 주소의 매핑을 caches (saves) 한다. (timeout 날때까지). 그래서 ARP는 plug-and play다. 어떤 net관리자 개입없이 무언가가 넣어지면 각자의 역할을 실행하는 것이다.

 

 

 

 

 Addressing 과정

 A에서 B까지 datagram을 보내는데 R이라는 라우터를 거쳐가는 상황이다. A는 B의 IP주소를 안다고 가정하자. A는 첫번째 hop router (R) 의 주소를 안다고 가정하자. A는 R의 MAC 주소를 안다고 가정하자.

 

 

 

 

 A가 자신의 source IP 주소를 넣고, B의 IP주소를 넣는다. 이 초록색 영역은 network 계층에서 IP주소를 넣는 작업이다. 파란색은 MAC 계층의 작업이다. A는 R의 MAC 주소를 넣고, 자신의 MAC 주소를 넣는다. 아직 B의 MAC 주소를 모르기 때문에 R의 MAC 주소를 MAC destination에 넣은 것이다.

 

 

 

 A에서 R까지 MAC 주소를 가지고 전달이 된다. 일단 라우터에서는 IP주소는 건들이지 않는다. MAC부분만 바꿔서 보낸다.

 라우터는 A에 물린 interface와 B에 물린 interface가 있다. B에 물린 interface에서 MAC을 수정하는데, 자신의 MAC 주소를 MAC src로 넣고, B의 MAC 주소를 MAC dest로 넣어서 전달한다.

 

 

 

 B는 이를 받고, B에서는 MAC 부분을 빼고 IP주소를 본다. 그래서 B에서 자기의 상위계층으로 올려 보낸다.

 

 

 

 

 

 

 

 

[참고]

Computer Networking A Top-Down Approach 7-th Edition / Kurose, Ross / Pearson