네트워크 정리 : Data Link Layer _ 환경별 Medium Access Control 방식

Data Link Layer

• 유/무선의 Physical Layer를 통해 송/수신하는 데이터들에 대해서 reliable한 통신을 위한 link를 제공한다.
• 통신과정에서 필연적으로 error등의 잡음이 발생할 수 밖에 없는데 이를 제어해준다.
• Network Layer가 Router to Router 간 통신이였다면 Data Link Layer는 데이터가 hop by hop으로 전송되는 모든 단일 링크를 관리한다.
• 라우터 사이에도 여러 node가 존재할 수 있으며 각 링크를 책임지게 된다. 따라서 출발지에 도착지로 패킷을 보낼 때 IP주소는 그대로인 반면 MAC 주소는 계속해서 변하게 된다.

Alice -> Bob으로 데이터를 송신할 때

• Alice는 먼저 Bob의 IP주소를 DNS 프로토콜을 이용해서 알아낸다. 이를 패킷에 적는다.
• 자신이 속한 sub network를 벗어나기 위해 게이트웨이를 찾는다. 게이트웨이(라우터)의 IP주소는 DHCP를 이용해서 알아낸다.
• 게이트웨이(라우터)의 MAC 주소는 IP를 가지고 ARP 프로토콜로 구한다.
• 이제 엘리스의 MAC 주소 + 라우터의 MAC 주소, 엘리스의 IP 주소 + Bob의 IP주소 조합의 패킷을 보낸다.
• 스위치는 MAC 주소 테이블을 이용해서 Frame들이 전달될 때 맞는 포트로 보내준다. MAC 주소 테이블은 스스로 학습이 가능하므로 MAC 주소를 보고 맞는곳에 보내는게 가능하다.

라우터에 있는 라우팅 테이블을 통해 적절한 서브네트워크로 포워딩이 이뤄진다. 거기서 다시 다음 라우터의 IP 주소를 구하고, ARP를 이용해서 MAC주소를 구하는 것을 반복하게 된다. 그러다가 목적지 Bob의 IP주소를 알고있는 라우터에 도달하면 해당 도착지로 전송이 되고, 해당 노드는 도착지 MAC 주소가 자신의 주소와 동일한 것을 확인하고 네트워크 계층으로 올리고, IP주소 비교 후 목적지와 동일하면 포트번호까지 확인해서 목적지 프로세스에게 데이터를 전달하게 된다.

 

MAC _ Medium Access Control

• Random Access Protocols
  • 누구나 다른 존재의 제어 없이 매체에 접근하여 전송을 시도하는 방식
  • 충돌이 발생할 수 있다.
  • 호스트가 그리 많지 않다면 굳이 제어자가 없어도 상관이 없다. 충돌날 확률도 낮고 발생하면 그때 다시 재전송하면 된다.
• Controlled-Access Protocols
  • 중앙제어를 통해 일반 호스트들의 접근을 제어한다.
  • 충돌을 원천 차단하는 방식이다.
  • 충돌이 안나지만 그만큼 제어로 인한 오버헤드가 발생하고 구현이 복잡하다.
• Channelization Protocols
  • 공간(자원) 자체를 쪼개서 나눠서 사용하는 방식이다.
  • 자신이 할당 받은 구간 내에서 전송하므로 충돌이 전혀 발생하지 않는다.
  • 시간을 쪼개거나, 주파수를 쪼개서 할당받는다.
  • 전송량에 있어서 한계가 명확히 존재하므로 비효율적일 수 있다.

---

Random Access Protocol

• 각 노드들이 외부의 제약없이 자유롭게 Medium에 접근하여 데이터를 전송하려는 시도가 가능한 방식이다.
• 당연히 동시에 말하는 상황이 발생할 수 있고 그로인해 데이터의 충돌이 발생할 수 있다.
• 충돌이 발생하면 해당 데이터는 복구 불가능한 손실이 발생하므로 재전송해야한다.

Random Access의 발전 방향

CSMA/CD (Collision Detection)은 유선에서만 사용가능한 방식이다. 무선의 경우 거리에 따른 신호의 감쇄 너무 심해서 파악하기가 힘들다. 따라서 무선의 경우 CSMA/CA (Collision Avoidance)를 활용한다.

MA 방식 _ ALOHA (hello) 

• 일단 보내고 싶을 때 바로 보내는 방식이다.
• 어쩌다 가끔씩 데이터를 보내는 경우에 적합하다. 개발년도가 1970년대이므로 그럴 만하다.
• Collision Detection 기능을 제공하므로 충돌이 났다고 판단되면 재전송한다.

재전송 알고리즘 : Binary Exponential back-off algorithm

• ACK를 통해 판단한다. ACK는 데이터를 보내는 주파수랑은 별도의 주파수를 사용하므로서 데이터 송수신과의 충돌은 피하였다.
• RTT 시간만큼 기다리고 ACK가 제시간안에 안오면 충돌로 판단한다. 이때 재전송 횟수에 비례하여 추가적으로 기다리고 재전송한다.
• 만약 첫 재전송이면 0~(2^1 - 1)사이의 랜덤한 수만큼 기다린다. 예를들어 4번째 재전송이면 0 ~ 15사이의 랜덤한 수를 뽑고 8이라면 8만큼 더 기다린 후 재전송하게 된다.
• 충돌이 자주날수록 재전송을 위해 대기하는 시간이 2의 지수 승으로 증가한다. (그래서 binary exponential 이다)

단점

• 모든 손실을 충돌이라고 판단하므로 비효율적이다.
• 조금만 데이터 전송하는 매체가 많아져도 충돌 확률이 급격히 올라간다.

개선 : Slotted ALOHA 방식

• 모든 데이터 패킷을 동일한 출발 선상에 세우는 방식이다. 예를들어서 3초 단위마다 데이터를 보낼 수 있다고 하면 2.7~3.9초에 보내는 데이터는 3초에, 3.4~4.1초에 보내는 데이터는 6초에 보내야 한다.
• 일률적으로 시간대를 맞추는 방식으로 기존 방식보다 충돌확률이 절반으로 줄어든다. 충돌이 발생하더라도 한 구간에 모아서 충돌이 발생하게 할 수 있다.

CSMA 방식 _ Carrier Sense Multiple Access 

• 캐리어(반, 쟁반)의 존재를 감지하고 MA한다.
• 전송 전에 주변 전송을 감지하다가 없으면 그때 전송한다.
• 눈치게임이랑 비슷하다. 말로만 하고 음성이 겹치는 순간 걸리는것이다. 이때 음성의 전파속도가 느리다면 걸리는 사람수가 많을 수 있다.

문제점

Propagation Delay(전파 지연)에 따른 문제점이 있다.

B는 주변에 통신이 없어서 t1초에 데이터를 전송한다.

C도 주변에 통신이 없어서 t2초에 데이터를 전송한다.

하지만 B가 보낸 데이터와 C가 보낸 데이터가 겹쳐서 서로 손실된다. 만약 B가 D에 데이터를 보내고 있었다면 D는 정상적인 데이터를 받지 못하고 손실 패킷이라 판단 후 폐기하고 ACK를 보내지 않게된다. B는 기다리다가 time out 후 재전송된다. 따라서 낭비되는 시간이 많아서 비효율적이다.

• 여기서의 큰 문제는 B와 C가 충돌이 발생한 것을 모르고 타임아웃 후 재전송 될 때까지 기다리는 것이 문제이다. 충돌을 파악하려면 Listener를 통해 외부의 주파수를 들어야하는데 자신이 보내는 데이터의 주파수로 인해 무선환경에서는 이를 파악하기가 어렵다.
  따라서 유선환경에서만 충돌감지가 가능하다.
• 또한 수신측은 충돌이 발생한 부분이 노이즈인지, 기존 데이터인지 구분하지 못한다. 따라서 전체 데이터를 다 듣고 난 후에야 CRC 등의 Error Detection을 하고 잘못된 패킷임을 알고 ACK를 안보내고 해당 패킷을 폐기하게 된다.
  그러면 수신측은 쓸데없인 데이터를 다 듣고 이를 분석하고 그동안 송신측도 대기하다가 시간 만료 후 재전송하게 되는 비효율적인 과정이 발생한다.

개선 (이더넷) : CSMA / CD _ Collision Detection

• Sender가 충돌을 감지하면 (자신이 보내는 주파수에 변경이 감지되면) 수신하고 있는 모든 대상들에게 (A, C, D) 특수한 Signal을 준다. 이를 확인한 수신측은 즉시 수신하고 있던 데이터를 Abort한다. 그러고 송신측은 다시 보낸다.
• 무선은 충돌을 DETECT 할 수 없다. 이건 유선 환경 Ethernet에 한정된 방식이다.

개선 (Wireless) : CSMA / CA _ Collision Avoidance

• 무선환경에서는 주파수의 강도가 거리에 따라 급격하게 감쇄되는 특징이있다. 면적이 넓어질수록 신호의 강도가 옅어지기 때문이다. 주변환경의 노이즈로 인한 감쇄 말고도 3차원 공간으로 신호가 구 형태로 퍼지면서 옅어진다고 생각하면 된다.
  마치 풍선을 크게 불면 점점 얇아지고 풍선의 색도 옅어지는 것과 같은 원리이다.
• 따라서 자신이 신호를 보내는 Signal은 매우 크게 들리고, 외부의 Signal은 매우 작게 들리므로 충돌이 발생하더라도 자신이 보내는 데이터의 변위는 매우 미미하게 바뀌게 된다. 따라서 이게 노이즈인지 충돌인지 분간을 할 수 없다.
• 결과적으로 무선환경에서는 CD를 포기하고 CA를 하게 되었다.
• 현대 무선 네트워크 환경에서 사용하는 방식이다.

CA를 위한 3가지 전략

Inter Frame Space (IFS) & Contention Window + Wait for ACK

• 일단 계속 주변 데이터 전송 상태를 Sensing한다. (자신이 조용하므로 감지가 가능하다)
• 주변의 Idle 상태가 확인되면 IFS만큼 기다린다. 이때 IFS는 전송할 데이터의 우선순위에 따라 모두 다르고 고정적인 값을 갖게된다.
• 하지만 IFS가 동일한, 우선순위가 동일한 데이터들이 존재할 수 있다. 따라서 IFS가 지났다고 바로 보내지 않고 Contention Window값 내에서 랜덤한 시간을 골라서 또 기다린다.
• 이렇게 최대한 충돌이 발생하지 않도록 하기위해 우선순위에 따라 분류하고 랜덤한 대기 시간을 통해 골고루 분배하는 것이다.
• 이 모든건 자신이 데이터를 보내면서 동시에 충돌을 감지하지 못하기 때문이다.
• 만약 랜덤한 시간으로 7을 고르고 1, 2, 3, 4를 세는데 주변에서 데이터를 송신하여 IDLE상태가 깨지면 다시 IDLE상태가 될 때까지 다시 기다린다. 이후 IFS만큼 기다린 후 랜덤 수를 다시 고르지 않고 4부터 이어서 7까지 센 후 전송을 하게된다. 
  즉, 데이터를 전송하려고 대기한 만큼 우선순위를 높혀줌으로서 Starvation을 막는 Aging기법의 일종이라고 볼 수 있다.
• 이전에 Binary Back off Algorithm에서 얘기한 방식과 마찬가지로 만약 충돌이 발생한다면 K값을 증가시키고 0 ~ (2^K-1) 범위의 Contention Window를 갖게된다. 충돌이 잦을수록 재전송 시간이 늘어나게 되는 원리이다.

---

Controlled Access

• 중앙집중식 제어
• 데이터를 보낼 매체들끼리 미리 정보를 교환하여 보낼 여부를 파악한다.
• Reservation / Polling, Token passing 3가지 방식이 존재한다.

Reservation

• 말 그대로 예약을 하고 예약 순서대로 먼저 데이터를 전송한다. 이 예약정보를 모든 매체들은 알고 있어야 한다. 그래야 전송이 모두 종료되었는지 알 수 있다.
• 최대 5개의 Station을 가질 수 있도록 고정되어 있고, 각 Station당 보낼 수 있는 데이터의 양도 정해져있다. 따라서 전송하는 데이터량의 편차가 클 경우 매우 비효율적이다.
• 사용하지 않는다.

Polling: Select and Poll Functions

• 권위적인 선생님과 수동적인 학생들이 있는 구조이다.
• 선생님이 학생들에게 발언의사가 있는지 묻고 있다면 말할 수 있게한다. 선생이 학생에게 말하고 싶을 때는 지목 후 말한다.
• 만약 A 학생이 다른 학생 B에게 말하고 싶다면 먼저 선생님이 자신에게 할말이 있는지 물을 때까지 기다린다. 이때 B에게 할말을 선생에게 말한다. 선생이 B를 지목하고 말해준다.
• 이때 선생님이 Primary이다.
  • PRIMARY -> Station: Primary가 A 노드에게 SEL 신호를 보내서 데이터를 받을 준비가 됐는지 묻는다. ACK가 오면 DATA를 전송한다. A 노드는 DATA를 받고 ACK를 보낸다.
  • Station -> PRIMARY: Primary가 Station에 Poll 신호를 보내서 보낼 데이터가 있는지 묻는다. NACK 면 없는 것이고, 보낼게 있다면 바로 DATA를 송신한다. Primary는 받고 ACK를 보낸다.
• 사용하지 않는다.

데이터 전송이 많을 경우 충돌을 피하기 위해 사용될 만하지만 오버헤드가 너무 커서 매우 답답한 구조이다.

Token Passing

• 통신을 하려는 노드들이 하나의 링을 이룬다. 이때 자신들의 그룹에 대해서는 토큰을 보유한 경우에만 통신을 하게 된다. 토큰을 가지고 있을 때 통신을 하고난 후 자신의 차례가 끝나면 정해진 방향으로 토큰을 전달한다.
• 토큰을 잃어버리거나 손상을 입을 경우 문제가 크다.
• 사용하지 않는다.

---

Channelization Protocol

• 자원을 나눠서 할당하여 매체간 충돌이 발생하지 않도록 하는 방식이다.
• 주파수, 시간, 코드 등으로 나눈다.

FDMA _ Frequency Division Mdeium Access

• 사용가능한 공통의 주파수 대역폭에 대해서 쪼개서 사용하는 방식이다.
• 2계층에 접속하는 방식이 이 방식이다.
• 대역폭이 넒을수록 데이터의 전송속도가 빨라지는데 이를 쪼개므로 속도가 느려지게된다.
• 데이터 통신에 참여할 매체의 개수를 미리 알고 파악해야 하는 선행 작업이 필요하다.
• 만약 대역폭 300MHz에 10개의 매체가 존재한다면 각각 30MHz를 할당받고 동시에 데이터 송수신을 할 수 있게 되는 것이다.
• FDM은 저주파의 대역폭을 고주파의 대여폭의 채널에 결합하는 기술이다.

TDMA _ Time Division Medium Access

• 시간을 쪼개서 일정 시간대에만 데이터를 송신할 수 있는 방식이다.
• 데이터 통신에 참여할 매체의 개수를 미리 알고 파악해야 하는 선행 작업이 필요하다.

CDMA _ Code Division Medium Access

• 현대 모바일 네트워크가 사용하는 방식이다.
• 각 노드들은 보낼 데이터에 자신들의 Code를 곱해서 보내주게 된다.
• 이때 중요한 점이 각 노드들에 배정된 코드들은 같은 코드와 곱해지면 4가되고 다른 코드와 곱해지면 0이되는 특징이 있다.

예시

만약 4개의 노드가 존재한다고 해보자. 그러면 각 노드 n1, n2, n3, n4는 각자 자신의 코드 c1, c2, c3, c4와 곱해진다. 이러한 데이터들은 주변 매체들이 데이터 전송에 개의치 않고 보내게 되므로, n1*c1 + n2*c2 + n3*c3 + n4*c4가 존재하게 된다.

 

이때, n3가 n1의 데이터를 받고 싶다면 들어오는 데이터에 대해서 c1을 곱한다.

그러면 데이터는 (n1*c1 + n2*c2 + n3*c3 + n4*c4) * c1 => (n1 * 4 + n2 * 0 + n3 * 0 + n4 * 0) => 4 * n1 만 남게 된다. 그러면 4로 나눠서 "n1" 데이터를 취할 수 있게 된다.

• 이러한 CDMA 핵심 기술 라이센스를 갖고 있는 기업이 퀄컴이다.