[NW] CSMA/CD

※ 질문/내용오류/공유할 내용이 있다면 jinkilee73@gmail.com으로 메일 주세요 :-)

이번 포스팅에서는 CSMA/CD를 공부해보자. CSMA/CD는 Carrier Sense Multiple Access/Collision Detection의 약자이다. 의미만 생각을 해보면, 충돌을 감지하는 다수 접근? 대충 이 정도로 추측을 하고 접근을 해보자.

CSMA/CD를 설명하기 전에 CSMA/CD이 무엇인지부터 정의해보자. 위키피디아에는 다음과 같이 정의되어 있다. 

http://en.wikipedia.org/wiki/Carrier_sense_multiple_access_with_collision_detection

Carrier sense multiple access with collision detection (CSMA/CD) is a Media Access Control method in which:^[1]

• a carrier sensing scheme is used.
• a transmitting data station that detects another signal while transmitting a frame, stops transmitting that frame, transmits a jam signal, and then waits for a random time interval before trying to resend the frame.

CSMA/CD is a modification of pure carrier sense multiple access (CSMA). CSMA/CD is used to improve CSMA performance by terminating transmission as soon as a collision is detected, thus shortening the time required before a retry can be attempted.

CSMA/CD is notable for its usage in early Ethernet installations, although this has fallen out of use as Ethernet switches have become commonplace.

위와 같이 위키피디아에서 정의해두었다. MAC method라고 하는데 MAC이 무엇인지는 차차 설명하기로 하고, 지금은 그냥 무슨 방법이다 정도로만 이해하도록 하자.

CSMA/CD는 다음과 같이 작동한다. 하나의 네트워크에 컴퓨터가 다음과 같이 연결되어있다고 가정해보자.

위의 그림은 A, B, C, D의 컴퓨터가 하나의 이더넷 네트워크에 연결이 되었을때, A가 t1부터 t2까지 데이터를 전송하는 것을 그림으로 나타낸 것이다. (세로축은 시간이라고 보면 된다.) A는 우선 자신이 속한 네트워크에 전송되고 있는 데이터가 있는지 확인한다. 있으면 기다렸다 보낼 것이고, 없으면 즉시 전송할 것이다. 이 때 CSMA/CD로 전송되는 모든 데이터들이 내부에 있는 모든 네트워크로 전달이 된다. 

여기서 잠깐!! 뭐라고? 하나의 LAN에 연결되어있는 PC가 데이터를 전송할 때 모든 PC에 데이터를 뿌른다고? 특정 목적지한테만 뿌리는게 아니고? 딱 들어도 비효율적이다. 이 부분에 대해서는 나중에 설명을 할 터이니 우선은 그냥 그런가보다~ 하고 넘어가자.

그러면 가령, D에서는 t3부터 t4까지 데이터를 감지하게 된다. 여기서 중요한 사실은 Delay가 존재한다는 것이다. 비록 A가 t1이라는 시간에 데이터를 전송했지만 데이터가 캐이블을 타고 가는 동안 시간이 조금 걸려서 t3라는 시간에 D에 도달하게 된다. 반대로 생각해보자. D입장에서는 t3라는 시간까지는 D는 네트워크가 idle 하다고 느끼게 된다. 비록 t1이라는 시간에 A가 이미 데이터를 보냈음에도 불구하고. 바로 이것이 Collision의 원인이다. 아래의 그림을 보자.

A가 t1에 데이터를 보낼 때 D1은 t1'에 데이터를 보낸다. 왜냐하면 아직 A의 데이터가 D에 도달하지 않았기 때문에 D는 네트워크가 idle 하다고 생각하기 때문이다. 그러다보니까 c1이라는 시간에 최초 충돌이 발생한다. 그런데 최초의 충돌이 중요한 것이 아니다. 데이터를 보내고 있는 A나 D가 실제로 충돌을 느끼는 시간이 중요한 것이다. 아래의 그림을 보자.

D는 위의 그림에서 c1에 충돌을 처음 감지한다. 이 때 D는 바로 데이터 전송을 멈춘다. 같은 일이 A에서도 일어난다. A도 t1과 t2사이에 D의 데이터를 감지할 수 있기 때문에 그 때 충돌을 감지한 후 데이터 전송을 멈추고 Jamming signal을 보낸다.

그 다음은 데이터를 다시 보내는 것이다. 그런데 A와 D가 바로 데이터를 다시 보내면 또 다시 충돌이 날 확률이 굉장히 높을 것이다. 따라서 random한 시간을 기다린 후 데이터를 전송한다. 그랬음에도 불구하고 또 충돌이 발생하면 또 같은 과정을 반복한다. 또 충돌나면 또 반복한다. 이런식으로 15번 충돌이 발생해버리면 "나 더 이상 여기서는 통신 못 해먹겠다."하고 배째라 상태가 된다.

아래의 그림은 CSMA/CD의 전체 Flow를 설명해준다.

잘 보면 위에서 다 설명한 부분이다. 단, K라는 변수는 충돌이 일어난 회수를 의미한다. 아까 15번이라는 충돌 가능 최대치가 있었지? 그것이 Kmax니까 K가 뭔지는 대충 알 거라고 생각한다. "K > Kmax"를 비교하는 부분이 왼쪽 밑에 노랗게 있는데 그 부분 위에 이상한 수식들이 있다. 그것이 바로 기다릴 random한 시간을 계산하는 부분이다. 그리고 한번도 언급하지 않은 것이 있는데, 1-persistent, nonpersistent 그리고 p-persistent이다. 이는 데이터를 전송하는 방법이라고 보면 된다.

우선, 1-persistent이다. 가장 효율이 안 좋은 방법으로, 하나의 PC가 자신이 속해있는 네트워크에서 전송되는 데이터를 감지하지 못 하면 자기의 데이터를 그냥 보낸다. 데이터를 감지하면 보내지 말고 기다린다. 더 이상 설명할 것도 없다.

nonpersistent는 1-persistent 보다는 조금 개선된 방법이다. PC가 데이터를 감지하면 보내지 말고 기다리고, 데이터를 감지하지 못 하면 random한 시간을 기다린 후 데이터를 보낸다. random 한 시간을 기다림으로서 충돌을 피할 수 있을 수도 있다는 것을 이용한 것이다.

마지막으로 p-persistent이다. 이는 PC가 데이터를 감지하지 못 할 경우 특정 p의 확률로 자기의 데이터를 보낸다. 그리고 q(= 1-p)의 확률로 특정 시간(slot)을 기다린다. 그리고 또 다시 데이터를 listen한다. 이 때 idle하면 다시 p의 확률로 데이터를 보내고 q의 확률로 특정 시간(slot)을 기다린다. 만일 idle하지 않으면(busy), collision이 발생한 것처럼 행동한다.

위의 세 가지 방법에 대한 Flow Diagram을 보면 아래와 같다.

결론적으로 아래와 같은 동작을 하게 된다.

CSMA/CD에 관하여 자세하게 설명했다. 다음 포스팅에서 설명할 부분은 이전의 포스팅에서 설명했던 30개의 PC가 있는 사무실에서의 LAN 구성하는 이야기를 다시 할 것이다.