Back-Off Algorithm in Slotted CSMA/CA

Written by windwiser

[본 포스팅의 그림은 본인의 논문중에 하나에 있던 것들임. - 역시나 불펌금지 ㅋㅋ]

 

 

무선 통신 기술에서의 기본적인 매체 접근 기법으로 알려진 CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance)에서 주요한 부분이라 할 수 있는 것은 소히 백오프 과정이다. 무선 통신 기술에서는 매체가 공기이기 때문에, 패킷의 충돌 즉, collision 현상을 감지(sense)하는 것이 무척이나 어렵다. 이에, 발상을 바꾸어, 충돌을 감지하는 것이 아니라, 확률적으로 충돌을 회피해 보자는 것에서 시작된 것이 백오프 기법이다. 횡단보도를 걷는 상황을 상상해보자. 두 개의 횡단보도가 있고 한쪽에서는 많은 사람들이 정해진 시간(Arrival Rate?, Period)마다 곧잘 건너고 있지만, 한쪽에서는 많은 사람들이 뒤로 물러나기 바쁜 상황이다. 후자를 소히 High Traffic Load Network라 불러도 좋을 것이다. 전자의 경우 후자에 비해, 사람들이 뒤로 물러심!!이 상대적으로 적어도 좋다. 하지만 후자의 경우 이러한 횟수는 많고 빠르게 증가될 것이다. 하지만 여기서 문제가 끝나는 것이 아니라 얼마나 물러서야 하는가? 얼만큼씩 물러서야 하는가?등의 고민이 있게 된다. 아무리 High Traffic이라 하여도, 최소한의 지연을 가지고자 하는 노력은 필요하기 때문이다. 많은 문서들의 설명을 가만히 보고 있으면 IEEE 802.11 무선랜에서의 CSMA/CA에 대해서 주로 설명하고 있는데, 나는 ZIGBEE에서의 CSMA/CA에 기초해 설명해 볼까 한다. 의도한 바에 따라서.

백오프 과정을 이해하는 것에 핵심적인 key는 BP(BackOff Period)와 CW(Contention Window)의 정확한 관계를 이해하는 것에 있다고 자신한다. 무선랜과 zigbee에 관계없이 반드시 프레임을 전송코자 하는 모든 전송 디바이스들은 반드시 랜덤 지연시간을 결정하고 그만큼 wait를 해주게 된다. 이는 다음 식에 따라 결정된다.

위 식에 의해 결정된 시간은 해당 디바이스가 기다려야만 하는 시간임과 동시에 BP에 해당한다. 후자가 더 중요하다. 말그대로 풀자면 물러서는 주기정도로 해석될 것이지만 이는 그리 간단한 개념은 아니다. 예를 들어, bp가 3으로 결정되었다고 하자. 이것은 기본심볼단위 3개만큼의 시간에 해당하며 이 시간이 반드시 기다려야 하는 랜덤지연시간에 해당한다. 더욱이 이 3이라는 bp값은 cw의 구성 bp수에 해당하게 된다. 즉, 큰 bp는 큰 cw를 만들게 된다. 앞서 식의 랜덤지연시간이 bp이며 이 bp가 3이라 결정되었다면, 하나의 cw를 구성하는 bp가 3이되고  CCA가 2개의 CW를 수행한다고 할 때, 총 6개의 BP가 CCA수행에 필요케 된다. 이러한 일련의 구성의 흐름은 백오프 과정을 이해하는 것에 매우 기초적이고 중요하다.

위 그림은 내가 ICCAS 저널에 실었던 논문의 한 그림이다. 위 그림은 긴급 노드가 백오프 과정상의 차이로 인해 어떻게 일반 노드에 비해 전송의 우선순위를 가질수 있는지를 보여주고 있다. 긴급 노드가 만약, BP가 3이 결정되고 일반 노드가 4가 결정되었다면, 경쟁구간내에서 작은 BP와 작아진 CW에 근거해 긴급 노드의 채널 접근이 먼저 이루어짐에 따라, 일반 노드는 다시 백오프 과정을 수행해야 한다는 것이 그림의 요지이다.

다음 그림은 역시 같은 논문에 사용한 그림으로 무선랜과 지그비의 백오프 기법의 차이를 보다 자세히 보여주고 있다. 여기서의 물리계층은 DSSS라고 가정하고 있다.

위 그림에서 먼저 생각해 보아야 할 것은, 최대 허용가능한 BP의 범위가 작은 센서네트워크 쪽보다 해당 범위가 최대 1023개의 BP값을 가지는 무선랜에서 보다 더 트래픽 적응에 용이하다는 점이다. 언뜻 생각해 보면, 큰 BP는 많은 백오프 지연시간을 만들지 않나 생각할 수 있지만, 네트워크에 가중되는 트래픽이 커질때, 센서네트워크 나아가 지그비에서는 최대 4번의 재전송 시도후에 프레임을 버릴 수 밖에 없다는 것에 문제가 있다. 반면에, 무선랜에서는 큰 CW구성 BP 수에 있어서의 허용 범위를 가지기 때문에 네트워크 트래픽이 계속적으로 가중된다고 할지라도 보다 재전송 여유를 가질 수 있는 것이다.

위 그림은 센서네트워크(IEEE 802.15.4) 나아가 ZIGBEE에서의 SLOTTED CSMACA의 수행 순서도에 해당한다. 아래는 이에 대한 수행절차에 대한 설명이다.

Slotted CSMA/CA Algorithm 수행 시에 중요하게 가만하고 있어야 하는 3개의 variable이 존재한다. 그것은 NB, CW, BE이다.

 

NB : Number of times CSMA/CA Algorithm was required to backoff while attempting to access the channel.

즉, channel을 접근하는 단계에서, backoff에 대해 요구된 CSMA/CA Algorithm의 수행 횟수가 됨.

CW : channel을 access하기 전에, channel이 idle하다고 판단될 때에, number of BPs 즉, Backoff Period의 수를 의미합니다.(Contention Window을 구성하는 단위)

BE : Backoff Exponent는 CCA(Channel Clear Access)를 수행하기 전에, 기다려야 하는 Random delay value를 결정하는 것에 쓰이는 parameter이다. Random delay value는 다음의 range안에서 결정된다.

 

알고리즘이 시작하면, 먼저, 초기 동작으로서 다음을 수행한다.

 

1. Initialization Step

- NB = 0, CW = 2

- Batterylife Extension이 지원된다면, 2 or macMinBE 값 중에 작은 값으로 지원되지 않는다면, Default로, macMinBE가 선택된다. ( macMinBE의 Default값은 3이다. )

- 마지막으로, 처음 CSMA/CA Algorithm을 수행 시에는 macMinBE를 0으로 두어, Random Delay를 NULL로 만들어 버려, 바로 CCA동작으로 진행하게 된다.

 

2. 다음으로, 앞서 정해진 BE에 의해 정해진 Random Delay만큼 기다린다.(Timer)

3. 다음으로, channel의 activity를 검사하기 위해서, BP(Backup Period) boundary에서, 한번의 CCA동작을 수행한다. 이때, channel이 IDLE한가 아닌가에 따라 두 가지 방향으로 수행이 진행된다.

4. IDLE하지 않다면, CW를 2로 reset하고, NB++을 수행하고, BE를 BE+1과 aMaxBE값중에 작은 값으로 SET한다. AMaxBE는 default값이 5이다. BE가 증가한다는 것은 IEEE 802.11에서의 DCF Algorithm 에서 처럼, 이것은 훨씬 큰 backoff delay를 가지게 될 확률이 높아짐을 의미한다. 마지막으로 NB 즉, CSMA/CA의 수행횟수가 backoffs의 최대 값으로 define되어 있는 macMaxCSMABackoff=5보다 작은지 보고 작다면,  Random delay 동작으로 돌아간다.

5. CCA후에 IDLE하다면, CW=CW-1;을 수행하고, 다시 CCA를 수행하는데, 다시 한번 CCA를 수행한 후, CW가 마침내 0이 되었다면, Frame을 전송한다.

BP가 결정되면 CW가 결정된다. 만약 상대적으로 어떠한 전송 디바이스에 채널 전송의 우선순위를 주고 싶다고 한다면, 초기 BP의 값을 작게 결정해 줌으로써 우선권을 보장해 줄 수 있을 것이다. 하지만 현실적으로 네트워크의 트래픽은 변화무쌍하고 계속적으로 가중될 수 있다. 따라서, 가중되는 트래픽 상황에 따라 BP의 값을 상대적으로 잇점을 줄 수 있다면 어떨까?

앞서 CSMA/CA수행과정을 읽어보면, BP를 결정하는 BE값에 주목하게 된다. 해당 BE값이 동적으로 설정될 수 있다면 주어진 네트워크 트래픽하에서 또한 변화하고 가중되는 트래픽 상황에서도 특정 노드의 전송을 보장할 수 있는 기법이 나오게 된다. 이러한 동적으로 변화는 트래픽에 따른 SLOTTED CSMA/CA의 백오프 파라미터들을 동적으로 설정하게 함으로써, 간단히 특정 노드의 전송을 보장하는 것이 내가 발표한 논문의 핵심 알고리즘이었다. 마지막 그림은 의도적으로 특정 전송 디바이스의 우선순위를 백오프 과정상의 잇점을 통해 어떻게 보장할 수 있는가를 예를 들어 보여주고 있다.

 

경우 1과 2의 비교를 통해, 실시간 긴급 노드가 백오프 과정상의 매체 접근의 우선권을 가짐을 알 수 있다. 초기 BE가 상대적으로 작기 때문에, 확률적으로 백오프 지연과정에서 작은 BP(경우 1에서는 3)를 얻게 된다. 이는 짧은 백오프 과정을 만들게 되어, 메시지 노드는 CCA 수행 중에 긴급 노드가 매체를 선점함에 따라 다시 백오프 과정을 수행하게 된다. 경우 3은 OffSet의 역할을 보여주고 있다. OffSet이 3으로 설정된 경우에, 3번째 슬롯까지 메시지 노드는 백오프 과정에 돌입하지 못하고 단순히 기다리게 된다. 이때 긴급 데이터 노드는 백오프 과정을 수행하여 매체를 선점할 수 있게 된다.

다음 그림은 본인 논문의 결과중에 하나로 동적으로 변화하는 네트워크 트래픽에 따라 동적으로 변화하는 백오프 과정으로 인해 향상된 긴급 노드의 성능 평가에 해당한다.

경우 A는 최대 의 네트워크 부하에서의 평균 지연시간과 처리율에 해당한다. 이때 비실시간 메시지 데이터 노드의 수를 증가(20->30)시키면, 네트워크의 부하가 가중되게 된다. 경우 B는 증가된 네트워크 부하로 인해, 실시간 긴급 데이터 노드의 높아진 평균 지연시간과 낮아진 처리율을 나타낸다. 이를 보완하기 위해, 하나씩 감소된 BE와 CW를 새로이 백오프 과정에 적용하게 된다. 이를 통해 향상된 결과가 경우 C에 해당한다. 마지막으로 경우 D는 OffSet을 적용하여 경우 C에 비해 더욱 향상된 결과를 나타낸다. 이처럼 네트워크의 가중되는 트래픽에 따라 동적으로 BE, CW, OffSet을 적용케 되면, 증가된 트래픽 상황에서도 실시간 긴급 데이터의 실시간성을 보존할 수 있음을 실험적으로 증명하고 있다.

[출처] Back-Off Algorithm in Slotted CSMA/CA|작성자 윈드와이