Over the last decade, significant attentions have been paid to the study of distributed scheduling algorithms in wireless multi-hop networks, with provable performance guarantee in terms of throughput and utility. The main results there can be summarized: first, there exists a tradeoff between complexity and performance, and second, most algorithms rely on heavy message passing for optimal performance guarantee. Despite the long history and great importance of such distributed algorithms, the question of designing a fully distributed contention resolution protocol has remained unresolved. As a promising response, recent theoretical researches have shown that carrier sense multiple access (CSMA) can be designed to achieve throughput- and utility-optimality without any control message exchange, i.e., in a completely distributed way. We refer to such a class of algorithms as {\em optimal CSMA}.
However, such advances in the theory domain cannot guarantee the performance in the practice domain, which naturally motivates the need for the validation of theory through real implementations (i.e., experimental evaluation). Thus, we focus on the practicality of the theory-driven algorithm by implementing such a theory-driven algorithm since theory by nature entails many assumptions for its mathematical tractability, which may lead to the fundamental gap between theory and practice.
In this dissertation, we first implement the optimal CSMA algorithm with conventional hardware and open device driver, and then extensively evaluate its performance using systematic decoupling approach in terms of topology, channel, and congestion control in the practical setting.
By analyzing the experimental results, we investigate the gaps between theory and practice and how to bridge them without hurting guaranteed performance of the original algorithm.
Next, we develop the {\em enhanced practical version} of the theory-driven algorithm given the three challenging conditions: (i) over legacy hardware, (ii) via software update, and (iii) in a fully distributed manner. This can be carried out by plausible ideas for both access probability selection and holding time control so that it is practically working well in real systems over various tough conditions. Moreover, we consider the integration of TCP with optimal CSMA for its practical usage. To overcome unfairness issue among TCP flows in several asymmetric scenarios, we introduce a simple but novel scheme called {\em virtual queue}, which does not require any modification in TCP. Throughout extensive simulations and experiments with a 15-node wireless testbed, we evaluate the performance of the whole proposed schemes and show that our implementations nearly achieve optimal performance as proved in theory, and outperforms existing competitive protocols such as two naive versions of optimal CSMA and 802.11 DCF under a wide range of scenarios. To the best of our knowledge, our implementation over legacy 802.11 hardware is the first effort in the CSMA-based wireless scheduling.
지난 10년 동안 무선 다중홉 네트워크를 위한 자원 할당 방법에 있어서 성능 최적화를 이론적으로 증명한 계층 교차 기반의 알고리즘 (e.g. Max Weight Scheduling) 이 많이 제안됐다. 하지만, 이러한 이론 기반의 알고리즘들은 높은 복잡도 및 구현의 어려움으로 인해, 무선 다중홉 네트워크 테스트베드를 활용한 성능 검증이 거의 이루어지지 않았다. 이러한 문제를 해결하기 위해 최근 메시지 교환 없이 네트워크의 전송용량과 효용함수 기반의 최적화를 달성하는 최적 CSMA (Optimal CSMA) 알고리즘이 등장했다. 이 알고리즘은 무선랜의 대표적인 채널 접근 제어 방법인 CSMA (Carrier Sense Multiple Access) 를 기반으로 채널 접근 확률과 데이터 전송 시간을 링크의 큐 길이에 대한 함수로 조절함으로써, 낮은 복잡도 및 분산화된 특성을 가지면서 최적의 성능을 보장하므로 실제 구현을 통한 성능 검증을 가능하게 만들었다.
본 박사 학위 논문은 이와 같은 구현상의 장점을 가진 최적 CSMA 알고리즘을 종래의 무선랜 카드와 랩탑으로 구성된 네트워크 시스템에 오버레이 프로토콜로 구현하고, 다양한 현실적인 시나리오에서 그 성능을 평가했다. 그 결과, 최적 CSMA 알고리즘은 이론에서 모델링되지 않은 다양한 상황에서 성능 저하가 발생했고, 이를 해결하고자 하는 연구에 동기를 부여했다. 우리는 우선 이론과 실제의 차이가 발생하게 만드는 근본 원인을 분석하고, 그로부터 성능을 개선하기 위한 현실적인 방법으로 기존 802.11 하드웨어를 수정없이 그대로 이용해서 실제로 가장 많이 사용되는 802.11 DCF (CSMA/CA) 알고리즘보다 효율적이고 공평한 자원 할당을 보장하는 개선된 알고리즘 (Enhanced-CSMA) 을 제안했다. 이를 현실적인 시나리오에서 검증하기 위해, 15대의 무선 노드로 구성된 대규모 테스트베드에 제안한 알고리즘을 구현하고, 다른 CSMA 기반 알고리즘과 성능을 비교해서 제안하는 방법의 우수성을 검증할 수 있었다. 또한, 현재 인터넷에서 가장 많이 사용되는 전송제어 프로토콜인 TCP 와 결합하는 연구를 수행했다. TCP가 최적 CSMA 알고리즘 위에서 잘 동작하도록 구현상 간단하면서도 효과적인 가상 큐 기반의 최적 CSMA 알고리즘을 제안했고, 이를 실제 시스템에 구현해서, 채널 경쟁의 비대칭성이 존재하는 시나리오에서 실험함으로써 제안하는 방법의 우수성을 검증했다. 특히, 본 학위 논문에서 개발된 알고리즘은 기존의 무선랜 하드웨어를 그대로 이용해서 구현할 수 있기 때문에, 현재의 와이파이 기반 인프라스트럭쳐 네트워크에서 사용되는 802.11 DCF 프로토콜을 오직 소프트웨어 업데이트만을 통해서 대체하는 방안으로 활용될 수 있을 것으로 기대한다.
