Since the appearance of smart devices like as smart phones and table PCs, the mobile data traffic has been heavily increased. Many researchers and experts from network sectors predict that such explosive increase in the amount of mobile traffic will be lasted for a while and it will reach to ten-fold increase within the next 5 years. Due to the mobile data explosion, current wireless networks are facing to the severe traffic overloads. To cope with the serious threat, we should exhaust every means of alleviating traffic overloads. Among many ones, we particularly focus on the way to optimally utilize network resources in this dissertation. We propose several link-layer algorithms achieving optimal performances based on the learning approach.
First, we study about recent throughput optimal CSMA (Carrier Sense Multiple Access) protocols.
Although those algorithms are optimal in the throughput aspect, most of them are known to exhibit poor delay performance making them impractical for implementation. Thus, we focus on the recent idea of exploiting multiple channels for delay reduction in CSMA, and prove that it is per-link delay order-optimal, i.e O(1)-asymptotic-delay per link, if the number of virtual channels is logarithmic with respect to mixing time of the underlying CSMA Markov chain. The logarithmic number is typically small, i.e., at most linear with respect to the network size.
Second, we develop an optimal rate adaptation protocol. We noticed that existing rate adaption schemes have been driven mainly by heuristics. In contrast, we formulate the rate adaptation problem as a kind of multi-armed bandit (MAB) problem. We derive an asymptotic upper bound for the expected reward in the corresponding MAB problem. This provides a fundamental performance limit that any rate adaptation algorithm cannot exceed. We then propose algorithms that approach this performance limit, and adapt their design to non-stationary environments where the success transmission probabilities at different rates evolve over time. We illustrate the efficiency of our algorithms (compared to the state-of-the-art algorithms) using both trace-driven simulations and implementation in a 802.11n real network test-bed.
Related to the second topic, we finally study the MAB with additional observations problem, which is modeled on the rate adaptation with packet probing scenario. We investigate how much more observations help to significantly improve the performance in both stochastic and adversarial settings as done in the MAB literature. First, for the stochastic setting, we derive an asymptotic upper bound on expected reward and propose two algorithms called SIMPLE and KL-UCB-A. In particular, we have shown that KL-UCB-A is order-optimal in terms of the number of rounds T under mild conditions. Second, for the adversarial setting, we also develop an algorithm that achieves an order-optimal reward with respect to the number of arms, the number of observations and the number of rounds.
최근 들어 스마트 폰, 태블릿 PC를 비롯한 각종 모바일 장치 수가 꾸준히 증가하고 있다. 이와 더
불어 첨단 모바일 장치들의 새로운 서비스 및 애플리케이션들은 통상 많은 트래픽을 생성하기 때문에,
모바일 트래픽량은 기하급수적으로 증가하게 되었다. 이러한 모바일 트래픽 폭증은 기존 무선 망에
심각한 부하를 야기하여 원할한 운용에 큰 장애가 될 수 있다. 이 문제를 해결하기 위한 방법으로 더
많은 초소형 셀을 촘촘히 설치하여 전체적인 무선 네트워크의 자원을 증대시키는 방안과 주어진 자원을
최대한 효율적으로 사용하는 매커니즘을 개발하는 방안이 있다. 본 학위 논문에서는 두 번째 방안에 더
중점을 두어 무선 네트워크 자원을 효율적으로 사용하는 링크 계층 프로토콜 설계에 대해서 다루었다.
링크 계층에 주목한 이유는 링크 계층의 주요 역할이 네트워크 자원의 할당이며, 무선 액세스 네트워크
등 많은 무선 네트워크들이 링크 계층 및 그 아래 계층에서 구현된 기능들만으로도 동작하기 때문이다.
본 학위 논문에서는, 첫째로 MAC 프로토콜과 관련하여 최적 처리량과 최적 지연을 동시에 달성
하는 분산화된 알고리즘에 대해 분석을 하였다. MAC 프로토콜은 네트워크 전체의 성능을 결정하는,
네트워크 시스템의 가장 기본적인 모듈 중 하나이다. 이 분야 관련 연구로 최근 Optimal CSMA라고
불리는 네트워크 최적 성능을 달성하는 분산화된 MAC 알고리즘들이 발표 되었으나 이들은 대개 지연
성능이 매우 안 좋은 것으로 알려져 있다. 다시 말해, 마치 네트워크의 처리량과 지연간에는 상충관계
가 존재하는 것처럼 인식되었다. 이에 따라 CSMA의 높은 지연 문제를 해결하기 위한 여러 연구들이
진행되었지만 이들은 (1) 특정 네트워크 토폴로지를 가정한다거나 (2) 낮은 지연을 얻기 위해 처리량을
희생하거나 (3) 시뮬레이션 등의 실험적 결과에 그치고 있다. 본 학위 논문에서는 지연감소를 위해 복수
개의 채널을 활용한 알고리즘을 고려하고, 엄밀한 수학적 분석을 통해 기 알고리즘이 처리량 측면에서
최적일 뿐만 아니라 가상 채널 개수가 CSMA 마코프 체인의 믹싱타임에 대해 로그 수준이면 링크별
지연 최적성 까지도 동시에 보장됨을 증명하였다.
둘째로, 무선 네트워크에서의 최대 처리량을 달성하는 비트 전송률 적응 기법을 제시하였다. 비트
전송률 적응 기법이란, 송신 노드가 수신 노드로 매 패킷을 보낼 때 마다, 과거 전송 기록이나 현재 채널 상태 등의 정보들을 바탕으로 얼마의 전송률로 보낼지를 선택하는 모듈을 말한다. 비트 전송률 선택의 목표는 통상 평균 처리량 (전송 속도와 그 전송 속도로의 전송 성공 확률의 곱)이 제일 큰 전송률로
패킷을 보내는 것이다. 하지만 채널 상태에 의존하는 전송 성공 확률을 사전에 알 수 없기 때문에 이
를 직접 전송 해보면서 학습을 통해 예측할 수 밖에 없다는 것이 본 문제의 어려움이다. 기존의 다른
연구들은 전부 휴리스틱한 기법을 제시하였고, 최적의 처리량을 달성하지 못하였다. 하지만 본 학위논
문에서는 전송률 선택 문제를 기계학습 분야의 주요 문제 중 하나인 MAB(Multi-armed bandit) 문제의
형태로 엄밀히 정의하고, 이에 대한 최적 알고리즘을 설계하였고, 그 최적성을 수학적으로 증명하였다.
이론적 분석에서 더 나아가 실용성을 검증하기 위해, 제안된 비트 전송률 선택 알고리즘을 실제 802.11n
네트워크 테스트베드에 구현하고, 다른 주요 전송률 선택 알고리즘들과 성능을 비교하였다. 다양한
시나리오에서의 실험 결과들이 제안 알고리즘의 우수성을 입증하였다.
셋째로, 두 번째 주제와 연관되어 패킷 프로빙이 허용되는 환경에서의 비트 전송률 적응 기법에
대해 연구하였다. 이 연구의 주요 질문은 이러한 환경에서 패킷 프로빙을 통해 얻을 수 있는 통해 얼
마나 처리량을 향상시킬 수 있는지, 충분한 패킷 프로빙 횟수는 어느 정도 되는지에 대한 것이다. 이에
대한 결과를 도출하기 위해 위 문제를 추가 관찰이 있는 MAB 문제로 정의를 하고, 주어진 패킷 프로빙
횟수에 대해 도달 할 수 있는 처리량의 근본적인 상한을 구하고 그에 근접할 수 있는 패킷 프로빙을 포
함한 링크 적응 기법들을 고안하였다. 이에 대한 다양한 시뮬레이션을 통해, 제안 알고리즘의 우수성을
확인했고, 초기단계의 프로빙의 중요성을 알 수 있었다.
