무선 네트워크에서의 통념(Myth) 하나가 깨지다.

무선 네트워크에서 무선 기기들은 공기를 매개체로 통신한다. 그런데 공기는 케이블에 비해서 에러가 발생할 확률이 엄청나게 높다. 전파가 전송되던 중 충돌이 일어나거나, Noise에 의해 전파 모양이 다르게 변하거나, 신호가 약해서 목적지까지 닿지 않는 등 다양한 이유로 인해 패킷 전송 실패가 일어난다. 따라서 무선 네트워크의 통신 프로토콜들은 에러를 다루기 위해 신경을 많이 쓴다. 가장 기본적인 에러 처리 방법은 에러가 발생한 패킷을 재전송하는 것이다. 하지만 충돌이 일어난 무선 기기들이 동시에 패킷을 재전송한다면 또 다른 패킷 충돌이 일어날 것이고 이것 만으로는 문제를 해결할 수 없다. 이를 해결하기 위해 충돌이 일어난 무선 기기들은 랜덤한 대기 시간(backoff time)동안 기다렸다가 패킷을 재전송한다.

대기 시간을 결정하는 방법은 다음과 같다. 모든 무선 기기들은 경합 시간 범위(contention window, cw)라는 값을 갖고 있는데, 충돌이 일어나면 무선 기기들은 0부터 cw 사이에서 랜덤하게 고른 하나의 수의 시간 만큼 대기한다.

두 무선 기기가 같은 랜덤 대기 시간을 결정할 확률은 매우 작으므로 둘 사이에 또 다시 패킷 충돌이 일어날 확률 또한 매우 작아지지만, 여전히 충돌이 일어날 가능성은 남아있다. 따라서 두 번째 충돌 부터는 cw의 값을 증가시켜 같은 대기 시간을 선택할 확률을 더욱 낮춘다. (일반적으로 충돌이 일어날 때마다 cw를 2배씩 증가시키는 Binary Exponential Backoff 알고리즘을 사용한다.)

이러한 접근에는 ‘무선 네트워크에서 둘 이상의 무선 기기가 동시에 패킷을 전송할 경우 반드시 충돌이 발생하여 두 패킷 모두 사용할 수 없다.‘ 라는 전제가 깔려있다. 하지만 이 전제는 실제와 다르다. 실제 네트워크에서는 전파 충돌이 발생하여도 세기가 강한 전파는 형태를 유지하여 전송될 확률이 높다. (Capture effect 라고 하며, 물리에서 파동의 간섭 현상을 생각하면 된다.) 뿐만아니라, 다중 패킷 수신(Multipacket Reception)이라는 한 무선 기기가 둘 이상의 전파를 동시에 수신할 수 있는 기술 또한 개발되어왔다. 이와 같이, 실질적인 기술은 무선 네트워크에서 일반적으로 받아들여지던 전제를 뒤짚음으로써 새로운 방향을 제시하였다.

그리고 마침내, 최근에 발표된 MAC for Networks with Multipacket Reception Capability and Spatially Distributed Nodes¹ 라는 논문에서 무선 네트워크에서 backoff 시간에 대한 통념이 깨어졌다.

저자들은 논문에서 다음과 같이 주장한다. 수신 노드로부터 멀리 위치한 노드들은 가까이 위치한 노드들보다 전송하는 신호의 세기가 약하므로, capture effect에 의해서 수신 노드로부터 멀리 위치한 노드일수록 전송 확률이 낮아진다. 예를 들어, 위의 그림과 같이 S1 ~ S5 5개의 노드들이 동시에 R1에게 데이터를 전송하고 있는 네트워크를 가정해보자. R1은 다중 패킷 수신이 가능하다. 하지만 S1이 다른 노드들에 비해 R1에 가까이 위치하므로 다른 노드들보다 전송 확률이 높다. 만약 다른 노드들이 패킷 전송에 실패한다면, 이들은 backoff 시간 동안 대기한 후 패킷을 재전송 할 것이다. 하지만 가까이 위치한 S1이 여전히 높은 확률로 패킷을 전송하고 있으므로 다른 노드들은 모두 패킷 전송에 실패할 확률이 높다. 이런 현상은 전반적으로 전혀 공평하지 못하다. 오히려 전송 실패가 일어났을 때 빠른 시간 안에 에러를 처리할 수 있도록, 실패가 일어날수록 cw의 값을 감소시켜 먼저 전송할 확률을 증가시켜야 한다는 것이다.

이러한 접근들은 최근에 DB 분야에도 있었다. 가장 효율적인 데이터 저장 방식이라고 알려졌던 row store는 대용량 데이터 처리가 필요함에 따라 column store보다 비효율적일 수 있다는 연구 결과가 나왔고, 심지어 가장 효율적인 데이터 구성 방식이라고 알려졌던 Relational DB 또한 용도에 맞게 다른 종류의 구성 방식을 사용해야 한다는 주장이 제기되고 있다.

시대를 넘어선 불변의 법칙은 존재하지 않는다. 시간이 흐르면서 기존에는 절대 받아들여질 수 없었던 통념들이 뛰어난 방법으로 받아들여질 수도 있다.

자신이 가장 굳게 믿고 있는 통념 하나를 반대로 생각해보자. 엄청난 결과를 얻을지도 모른다.

참고 문헌

1. Celik, G. D., Zussman, G., Khan, W. F., and Modiano, E. 2010. MAC for Networks with Multipacket Reception Capability and Spatially Distributed Nodes. IEEE Transactions on Mobile Computing 9, 2 (Feb. 2010), 226-240.