[컴퓨터망]- Multiple Access Protocol

 

Multiple Access Protocol?

link에 다수의 단말기들이 물려 있을 때 어떻게 접속할 것인가, 둘 이상이 접속하면 충돌이 나는데 어떻게 해결할 것인가를 정하는 게 

multiple access protocol이다.

 

두가지 기법이 있다.

 

Point-to-Point link와 broadcast가 있다.

요즘 사용하는 방식은 broadcast이다.

shared wire인데 흔히 우리가 사용하는 공유기라고 생각하면 된다.

무선이든 유선이든 하나의 chanel이 share 되고 있는 경우에 두 개 이상이 동시에 전송하게 될 경우 충돌이 일어난다.

multiple access protocol은 node들이 어떻게 share 할지 정해주는 분산 알고리즘이다.

어떻게 나눠서 쓸 것인가. 채널 공유에 대한 약속을 결정해주는 알고리즘이다.

해당 약속에는 어떤 노드가 언제 전송할지 등등이 포함되어 있다.

 

이상적인 Multiple access protocol?

 

rate가 R인 채널이 있다하고, 단일 노드가 통신을 한다면 rate R로 전송하면 될 것이다.

만약 M개의 노드가 전송한다면 평균적으로 R/M으로 보낼 수 있다면 가장 이상적이다.

 

 

mac protocol : taxononmy

공유된 채널에 다수의 사용자가 접속할 수 있도록 도와주는 프로토콜이다.

 

three class가 있다.

 

channel partitioning

채널을 잘개 쪼개서 여러 개의 서브 채널로 만든다.
여기서 타임슬롯으로 쪼개는건 TDMA, 주파수로 나는 것을 FDMA, code로 쪼갠 것을 CDMA이다.

즉 잘게 채널을 나눠서 채널 한개한개를 쓰고자 하는 사용자에게 할당해 주면 되겠다고 한 것이다.

 

TDMA

Time division multiple access라고 한다.

채널을 시간 단위로 쪼개는 것이다.

각 노드 별로 채널을 사용할 수 있는 시간을 할당해준다.

즉 시간을 정해서 첫 번째 slot은 1번이 쓰고, 3번째 슬롯은 3번이 써라!! 이렇게 정해 놓은 것이다.

slot의 개수는 한정되어서, slot 개수로 동시에 통화할 수 있는 사용자의 수가 정해진다.

 

FDMA

채널을 주파수 별로 쪼개는 것이다.

노드 별로 채널을 사용할 수 있는 주파수를 할당해 준다.

여러 주파수를 같이 보내더라도, 수신 측에서 주파수 별로 분리할 수 있다.

주파수가 나오는 개수가 곧 동시에 전송할 수 있는 사용자의 수단.

 

Random access protocols

어떤 노드가 언제 보내야 될지가 명확하지 않다.

따라서 random access protocol은 충돌을 어떻게 detection 할 것인가., 충돌로부터 어떻게 회복할 것인가 등을 정의한다.

 

예시로는 

• ALOHA, slottted ALOHA, CSMA 등

 

 

Slotted ALOHA

가정

• frame들이 같은 사이즈라고 가정하자. 그리고 시간은 같은 size의 slot으로 나눠져 있다.
• 노드들은 slot의 시작점을 알고 있어서 sync 돼있다.
• 한 슬롯에서 2개 이상의 노드가 전송하는 경우 모든 노드는 충돌을 감지한다.
• C : 충돌, S : 성공, E: 빈

그림을 보면 node 1,2,3이 동시에 전송해서 충돌이 발생했다. 그다음 1,2,3을 모두 보내지 않기로 결정하고 보내지 않는다.

그다음에는 일련의 과정을 통햇 1,2가 전송 -> 2가 전송 -> 1,3이 충돌 -> 한턴 쉬고 -> 1을 전송->3을 전송

 

 

장점

• 단일 활성 노드는 채널의 전체 전송을 지속적으로 이용할 수 있다.
• 매우 분산된 시스템. 노드의 슬롯만 동기화되어 있으면 됨.
• 간단하다.

단점

• 충돌로 인한 슬롯의 낭비 및 충돌 처리가 필요
• 사용하지 않는 슬롯이 있을 수 도 있다.
• 노드는 패킷 전송 시간보다 짧은 시간에 충돌을 감지할 수 있다.

 

성능은 37% 정도의 시간을 제대로 써서 보낼 수 있다.

 

 

Pure ALOHA

slot이 나눠져 있지 않은 ALOHA이다. 싱크도 맞지 않는 경우이다.

이런 경우에도 충돌이 발생하는데, clock이 정해져 있지 않기 때문에 slot에 걸쳐서 충돌이 발생한다.

slot의 경우는 어떤 slot 하나만 보내면 성공인데, 이 경우는 slot이 없기 때문에 충돌 가능성이 높다.

만약 노란색 입장에서 충돌이 발생하지 않으려면 t0~ to+1까지 아무도 보내면 안 된다.

 

slotted ALOHA보다 절반 떨어진 18% 성능이다.

 

 

CSMA(carrier sense multiple access)

내가 보내기 전에 다른 쪽이 보내고 있는지 확인할 거야!
만약 확인해서 누군가 보내고 있으면 전송을 미룬다
만약 누군가 보내고 있지 않다면 전송한다.

신호를 전달해서 전송할 수 있는 것을 carrier이라고 한다.

carrier를 통해서 탐지하는 것을 carrier sense라고 한다.

하지만 이러한 carrier sense를 사용해도 충돌이 발생할 수 있다.

-> 전파지연 두 노드가 서로의 시작된 전송을 듣지 못할 경우

충돌이 발생하면 패킷 전송 시간이 낭비되고,

거리와 전파지연은 충돌 확률을 결정하는데 역할을 한다.

CSMA/CD

충돌을 detection 할 수 있는 경우는 CSMA/CD라는 프로토콜을 사용한다.

아주 짧은 시간 내에 충돌을 감지할 수 있고,

충돌이 일어난 경우 바로 전송을 취소한다. -> 채널 낭비가 감소

유선에서는 충돌감지가 쉽지만 무선에서는 어렵다.

따라서 무선 LAN인 경우 CSMA/CD를 쓰지 않는다.

 

 

CSMA/CD 알고리즘

1. NIC에서 네트워크 계층으로부터 데이터그램을 받고, frame을 만든다.
2. NIC는 채널 상태를 감지한다.
   1. 비어 있는 경우 프레임 전송을 시작한다
   2. 사용 중인 경우 채널이 빌 때까지 기다린 다음 전송한다.
3. NIC이 충돌 없이 전체 프레임을 전송하면 프레임 처리가 완료된다.
4. NIC가 전송 중에 다른 전송을 감지하면 중단하고 jam 신호를 전송한다.
5. 전송을 중단한 후, NIC는 이진 백오프 과정에 진입한다.
   • m번쨰 충돌 후, NIC는 0,1,2,... 2ᵐ-1중에서 임의의 값을 선택해서 k*512비트 시간 동안 대기하다가 다시 2번 단계로 돌아간다.
   • 충돌이 많이 발생할 경우 백오프 간격이 더 길어진다.
   • 충돌이 많이 발생할 경우 범위가 익스포넨셜 하게 증가한다.
     • 충돌을 겪을수록 충돌이 일어날 확률이 줄어든다

 

효율성은 ALOHA 방식보다 효과적이라고 알려져 있다.

 

 

Taking Turns

 

channel partitioning MAC protocols

• 서로 순서를 바꿔가면서 하는 방식이다. 채널을 아주 공평하게 나눠서 쓸 수 있는 방식이지만 load가 낮은 상황에서는
  효율성이 떨어질 수 있다.
• channel 10개가 있는데 쓰는 사람이 나밖에 없어도 채널을 하나만 할당해 주니 효율이 떨어진다.

 

Random access MAC protocols

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

 

Polling

마스터노드가 여러 자식 노드들에게 순서를 지정해 주는 방식이다.

하지만 이런 경우 차례를 지정해줘야 하는 overhead가 있고, polling을 해서 전송해야 하니 지연도 있다.

그리고 마스터가 문제가 생기면 전송이 되지 않는 문제가 발생한다.

 

 

token passing

token을 넘겨주는 방식이다.

현재 토큰을 가지고 있는 노드만이 데이터 전송을 할 수 있고, 데이터 전송 할 게 없다면 토큰을 다른 노드들에게 넘겨준다.

하지만 이러한 방식은 토큰을 관리하는 오버헤드가 잇고, 토큰을 기다리는 latency가 있을 수 있다.

그리고 토큰 방식에 문제가 생기면 실패할 수 있다.

 

 

 

요약

• MAC(multiple Access protocol)은 둘 이상의 연결 시 충돌을 어떻게 해결할 것인가를 결정하는 프로토콜이다.
  • point-to-point, broadcast가 있다.
• MAC에는 3가지 분류가 있다.
  • channel partitioning : 채널을 잘게 쪼개서 서브채널로 할당
    • 방식은 timeslot과 주파수로 나누는 2가지 방식이 있다.
  • random access : 채널을 나누지 않고, 보낼 게 있으면 보내라!
    • 어떻게 충돌을 감지하고, 충돌을 해결할지가 중요하다.
    • ALOHA, slotted ALOHA, Pure ALOHA, CSMA, CSMA/CD가 있다.
      • slotted ALOHA는 슬롯을 나눠서 한슬롯마다 하나씩 전송가능
        • 효율이 37%, 충돌이 일어나면 대기하는 등 슬롯의 낭비가 심하다
      • Pure ALOHA는 슬롯을 나누지 않고 진행.
        • 효율이 18%, 슬롯을 나누지 않아서 충돌이 자주 발생
      • CSMA :  보내기 전에 채널이 idle 하냐, busy 하냐를 물어서 전송하는지 결정
        • 충돌 감지를 위해서 backoff 전략을 선택.
          • 충돌을 하면 할수록 변수 선택 범위가 늘어나 충돌확률이 줄어든다.
  • taking turns
    • 차례를 지정해 준다! polling과 token이 있다.
      • Polling은  마스터가 slave들에게 차례를 부여하는 것.
        • 차례를 부여하는 오버헤드가 있고, 차례를 기다리는 지연시간, 그리고 마스터가 망가지면 전체에 문제가 생긴다.
      • Token passing은 token을 가지고 있는 사람만 보낼 수 있다.
        • 만약 보낼 게 없다면 token을 넘겨줌.
          • token을 관리하기 어렵고(오버헤드), 토큰을 기다리는 지연, 그리고 토큰 자체에 문제가 생기면 실패한다.