This thesis describes flow control algorithms achieving two kinds of max-min fairness properties, that is to say, bandwidth max-min fairness and utility max-min fairness and provides a control-theoretic approach to analyze the stability of proposed algorithms. Our algorithms are scalable in that routers do not need to store any per-flow information of each flow and they use simple first come first serve (FCFS) discipline, stable in that the stability is proven rigorously when there are flows with heterogeneous round-trip delays, and optimal in that the gains used for controllers are optimally adjusted.
First, we present a network architecture for the distributed bandwidth max-min flow control of elastic flows and generalize stability conditions to enhance network performance. We suggest two closed-loop system models that approximate our flow control algorithms in continuous-time domain where the purpose of the first algorithm is to achieve the target queue length and that of the second is to achieve the target utilization. The slow convergence of many rate-based flow control algorithms, which use queue lengths as input signals, can be resolved by the second algorithm. Based on these models, we find the conditions for con-troller gains that stabilize closed-loop systems when round-trip delays are equal and extend this result to the case of heterogeneous round-trip delays with the help of Zero exclusion theorem.
Second, we revise the proposed algorithms and provide application-performance oriented flow control algorithms. We present a network architecture for the distributed utility max-min flow control of elastic and non-elastic flows where utility values of users (rather than data rates of users) are enforced to achieve max-min fairness. We also provide a distributed link algorithm that does not use the information of users' utility functions. To show that the proposed algorithm can be stabilized not locally but globally, we found that the use of nonlinear control theory is inevitable. The stability of the network is proven by means of so-called loop transformation and absolute stability theorem, viewing the network as a feedback control system with slope-restricted monotone nonlinear feedback. Even though we use a distributed flow control algorithm, it is shown that any kind of utility function can be used as long as the minimum slopes of the functions are greater than a certain positive value. We believe that the proposed distributed algorithm is the first to achieve utility max-min fairness with guaranteed stability in a distributed manner.
We simulate our algorithms with optimal gain sets for various configurations including a multiple bottleneck network to verify the usefulness and extensibility of our algorithms. Our framework lends itself to a single unified flow control scheme that can simultaneously serve, not only elastic flows, but also non-elastic flows such as voice, video and layered video.
본 논문은 최대-최소 대역폭 공평성과 최대-최소 효용 공평성을 달성하는 흐름제어 알고리즘을 제안하며 안정성을 분석하기 위해 제어이론적인 접근 방법을 취하였다. 제안된 알고리즘은 라우터가 개별 흐름의 정보를 저장할 필요가 없으므로 확장성이 있으며, 다양한 지연을 가진 흐름들에 대해 안정함이 증명되어 있으며, 제어기에 사용되는 이득값이 최적으로 조정되어 있다.
먼저, 탄성적 흐름들에 대해 분산적으로 동작하는 최대-최소 대역폭 공평 흐름제어를 위한 망 구조를 제안하며 망 성능을 향상시키기 위해 안정성 조건을 일반화한다. 제안된 흐름제어 알고리즘을 연속 시간 영역에서 표현하는 두 가지의 폐쇄 루프 시스템 모델을 제안하는데, 첫번째 알고리즘은 목표 대기열 길이를 달성하며, 두번째 알고리즘은 목표 활용도를 달성한다. 대기열 길이를 입력 신호로 하여 전송률을 기반으로 동작하는 많은 흐름제어 알고리즘의 수렴이 느린 문제를 두번째 알고리즘으로 해결할 수 있다. 이러한 모델들을 기반으로 하여 왕복 지연이 단일한 경우에 대해 제어 이득값의 조건을 구하고 영점 배제 이론을 적용하여 왕복 지연이 다양한 경우로 조건을 확장한다.
다음으로, 제안된 알고리즘을 개선하여 응용 프로그램의 성능 향상을 목표로 하는 흐름제어 알고리즘을 제안한다. 즉, 탄성적 흐름들과 비탄성적 흐름들을 분산적으로 제어하여 최대-최소 효용 공평성을 달성하는 망 구조를 제안한다. 이 때에 최대-최소 효용 공평성은 대역폭이 아닌 효용값이 최대-최소 공평성을 달성하는 것이다. 또한, 사용자의 효용 함수에 대한 정보를 전혀 사용하지 않는 분산된 링크 알고리즘을 제안한다. 제안하는 알고리즘이 지역적이 아닌 전역적으로 안정화 되는 것을 보여주기 위해서 비선형 제어 이론의 사용이 불가피함을 알 수 있다. 망을 기울기가 제한된 비선형 피드백을 가진 제어 시스템으로 간주하고, 루프 변환 기법과 절대 안정성 이론을 사용하여 망의 안정성을 증명한다. 또한, 분산된 흐름 제어 알고리즘임에도 불구하고, 효용 함수의 최소 기울기가 어떤 양수값보다 크기만 하면 그 어떠한 형태의 효용 함수도 사용될 수 있음을 증명한다. 제안하는 알고리즘은 안정성이 보장되면서 최대-최소 효용 공평성을 분산적으로 달성하는 최초의 알고리즘이다.
제안된 알고리즘들의 실용성과 확장성을 검증하기 위해 다중 병목 망을 포함한 다양한 경우에 대하여 최적 이득값을 이용하여 시뮬레이션한다. 제안된 구조는 탄성적 흐름 뿐만 아니라 음성, 비디오, 다계층 비디오 등의 비탄성적 흐름까지 동시에 지원할 수 있는 통합된 형태의 흐름 제어 알고리즘에 적합하다.
