The capacity of core networks has increased tremendously due to recent technology development in optical transmission and high-speed router/ethernet switches. However, IP networks originally designed to provide best-effort services can not guarantee strict or statistical quality-of-service (QoS) requirements for real-time traffic flows because resources are not reserved and all packets are treated equally in most nodes. Thus, it is very important to monitor network status and manage network resources in order to guarantee QoS for flows with real-time performance requirements. Since the delay performance strongly depends on the available band-width of the path among many network resources, this dissertation is concerned with monitoring the available bandwidth and proposing an admission control scheme of internet flows based on the estimated available bandwidth.
First, a new mechanism is proposed to estimate the available bandwidth of a queueing system, whose service rate and the load of input traffic are not known in advance. In order to estimate the available bandwidth, we propose a probing method called a minimally backlogging method and propose two statistics. The first statistic is based on the delay of each probing packet and the second statistic is based on the amount of probing packets served in a specific time interval. We first show that an M/G/1 queueing system is stable when probing packets are sent to the system according to the minimally backlogging method. We also show that the available bandwidth can be estimated by using either of the two statistics if the probing packets are sent to the queueing system by the minimally backlogging method. Especially, the second statistic can be used to estimate the available bandwidth of a G/G/1 queueing system. We apply the theory developed for a single server. in order to estimate the available bandwidth for a local server as an application. The accuracy of the two proposed statistics is evaluated numerically under Poisson and self-similar traffic loads.
Second, a new mechanism which estimates the available bandwidth for multiple hop routes is proposed by extending the approach for a single server, especially with the second statistic, and introducing a simplified path model which simplifies a multiple hop path into a combination of a fixed delay component and a virtual server. Since the proposed mechanism can estimate the available bandwidth quickly and track it adaptively and continuously, a reasonable range of available bandwidth for a short time interval can be obtained using the mean and variance of the estimated available bandwidth. The performance of the proposed available bandwidth estimation mechanism is evaluated by simulation in a multiple hop network topology.
Finally, a scalable architecture and an admission control algorithm for real-time flows are proposed. Since individually managing each traffic flow on each of its traversed routers causes a fundamental scalability problem in both data plane and control plane, we consider that each flow is classified at an ingress router and data traffic is aggregated according to the class inside the core network in our proposed re-source management architecture as shown in a DiffServ framework. In our approach, admission decision is made for each flow at the edge (ingress or egress) routers, but it is scalable because the algorithm consists of simple arithmetic computations and a single comparison logic. In the proposed admission control scheme, an admissible bandwidth, which is defined as the maximum rate of a flow that can be accommodated additionally while satisfying the delay performance requirements for both existing and new flows, is calculated based on the available bandwidth which is estimated by edge routers through monitoring minimally backlogging probing packets. The admissible bandwidth is a threshold for admission control, and thus, it is very important to accurately estimate the admissible bandwidth. The performance of the proposed scheme is evaluated with a set of simulation experiments using highly bursty traffic flows.
광전송 기술과 고속 라우터 기술의 발달로 통신망의 전송 능력이 크게 향상 되었음에도 불구하고, 자원이 예약되지 않고 모든 패킷이 동등하게 처리되는 특성으로 인해 인터넷 망에서 엄격하거나 통계적인 서비스 품질(QoS: Quality of Service)이 아직 보장되지 않고 있다. 실시간 성 흐름(flow)들에 대해 서비스 품질을 보장해 주기 위해서는 망의 관측과 자원의 관리가 반드시 필요하다. 실시간 성 흐름들은 지연에 민감하기 때문에, 본 학위 논문에서는 지연을 주된 서비스 품질로써 다룬다. 지연은 많은 자원들 가운데 가용 대역에 크게 의존하기 때문에, 본 학위 논문에서는 먼저 가용 대역을 추정하는 문제를 다루고, 다음으로 추정된 가용 대역에 기반해 실시간 성 흐름들을 수락 제어하는 새로운 방법을 제안한다.
본 학위 논문은 서비스 율, 입력 트래픽의 부하가 알려지지 않은 대기 시스템의 가용 대역을 추정하는 새로운 방법을 제안한다. 최소 잔량 방법이라는 탐침 방법과 두가지 통계량(statistic)을 제안한다: 한 가지는 탐침 패킷의 지연에 기반한 통계량이고, 다른 하나는 탐침 패킷의 서비스 율에 기반한 통계량이다. 일반적인 서비스 시간을 갖는 시스템에 탐침 패킷을 제외한 데이타 패킷의 부하가 1보다 낮게 포아송 과정으로 입력될 때, 그 시스템에 최소 잔량 방법으로 탐침을 하더라도 그 시스템이 안정하다는 것을 증명하였다. 두 가지 통계량 모두 가용 대역에 대한 추정량이 될 수 있음을 보였으며, 특히 두번째 통계량은 데이타 패킷이 일반적인 과정으로 도착하는 경우에도 가용 대역의 추정량이 됨을 보였다. 시뮬레이션을 통해 데이타 트래픽이 포아송 과정 또는 자기 유사(self-similar) 과정으로 도착하는 경우에 탐침 시간이 유한하더라도 두 통계량의 정확성이 매우 높음을 관측할 수 있다.
본 학위 논문은 앞서 단일 서버에 대해 개발된 예측 이론을 확장하여, 다중 홉 경로에 대한 가용 대역을 추정하는 새로운 방법을 제안한다. 단일 서버에서 개발된 이론을 사용하기 위해 다중 홉 경로를 고정 지연 성분과 가상 서버로 구성되는 단순화된 경로로 모델링한다. 제안되는 가용 대역 추정 방식은 가용 대역을 빨리 찾아서 가변하는 가용 대역을 계속해서 매우 근사하게 뒤따르기 때문에 짧은 시간에 가변하는 가용 대역의 범위를 알아낼 수 있다. 제안된 방식은 기존의 방식에 비해 데이타 트래픽의 가변성이 높은 환경에서 특히 더 좋은 성능을 내는 것을 시뮬레이션을 통해 확인할 수 있다.
마지막으로 실시간 성 흐름들의 지연 서비스 품질을 보장하기 위해서 새로운 서비스 구조와 수락 제어 방식을 제안한다. 기본적으로 확장성을 위해서 DiffServ 환경에서와 마찬가지로 흐름들은 진입(ingress) 라우터에서 클래스가 구별되어 출구(egress) 라우터에 도달하기까지 망 내부(core) 라우터에서는 클래스 단위로만 처리가 된다고 가정한다. 특히, 클래스는 실시간성의 높은 클래스와 비실시간성의 낮은 클래스 두 가지만 존재하는 것으로 가정하며, 실시간성 클래스에 속하는 흐름들만 수락 제어를 거치게 되고 비실시간성 클래스에 속하는 흐름들은 수락 제어를 거치지 않고 입력이 가능하다. 대신 비실시간성 흐름에 의해 실시간성 클래스의 서비스 품질이 영향을 받지 않도록 망 내부에서는 실시간성 트래픽이 비실시간성 트래픽에 비해 높은 우선 순위로 서비스 받는 것을 가정한다. 제안하는 서비스 구조에서 수락 제어는 진입 라우터에서만 이루어지기 때문에, 수락 요구에 대해 빠른 응답이 가능하고 망 내부 노드에서 각 흐름들에 대한 정보의 관리 혹은 자원의 예약을 요구하지 않기 때문에 확장성 있는 구조라고 할 수 있다. 수락 제어 알고리즘은 단순한 계산과 비교만으로 이루어지기 때문에 확장성에 있어 유리하다. 제안되는 수락 제어 알고리즘에서는 수락 제어를 판단하는 문턱값이 되는 허용 대역(admissible bandwidth: 이 값은 지연 성능을 만족시키는 한도내에서 추가로 받아들일 수 있는 최대의 대역으로 정의된다)의 계산이 가장 중요하다. 허용 대역의 추정치가 명시적으로 유도되기 때문에 각종 관련 변수들(예를 들면, 허용 지연 범위, 지연 위반 확률의 문턱값 등)의 영향을 직관적으로 알 수 있다. 허용 대역은 가용 대역(available bandwidth)의 평균과 분산에 의존해 결정되는데, 가용 대역을 탐침 방식으로 추정하기 때문에 가용 대역의 추정에 오차가 존재할 수 있다. 분산의 오차를 보상하기 위해 VMF(variance multiplication factor)를 도입하지만, 작은 VMF 값의 사용으로도 원하는 서비스 품질의 제공이 가능하며, 기본 측정 구간(T)의 길이를 조금 증가시키면 VMF를 사용하지 않고도 서비스 품질이 보장되는 것을 시뮬레이션을 통해 관측할 수 있다. 제안된 측정에 기반한 수락 제어 방식은 파라메타에 기반한 방식에 비해 훨씬 높은 자원 사용율(utilization)을 얻음과 동시에 실시간성 흐름들의 지연 서비스 품질을 만족시켜 주기 때문에 서비스 품질 제공 가능한 차세대 인터넷 구현에 적용이 될 수 있다.
