Broadband integrated services networks have to satisfy different requirements demanded by both a diverse set of applications and network providers. Real-time, fair, and link-sharing requirements are representative instances. Real-time requirement is to guarantee a delay bound for a session when the session passes through a network. Fair and link-sharing requirements are to distribute bandwidth evenly. Especially, fair requirement is a special instance of link-sharing requirement. The essence of satisfying such requirements is in packet scheduling algorithms. In this dissertation, we study the design, analysis, and implementation of packet scheduling algorithms that satisfy real-time, fair, and link-sharing requirements together. We aim to achieve high network utilization, high fairness and scalablility. Here, network utilization indicates the number of admitted real-time sessions. High fairness means bandwidth is distributed evenly in short time intervals. Scalability says that scheduling complexity does not depend on the number of sessions. However, the three goals cannot be achieved simultaneously since they conflict one another. We propose several packet scheduling algorithms
that provide right trade-offs between the goals. Proposed algorithms achieve at least one goal better than existing algorithms, achieving the other goals in the same level.
First, we propose an analysis tool called a Service Curve (SC) server to be used in variable-sized packet networks. This tool derives a guaranteed delay bound for a session where individual routers in the connection path of the session may adopt different scheduling algorithms instead of the same algorithms.
A network element, such as a transmission link and a scheduler, is characterized by a guaranteed service curve in the tool. Then, heterogenoues network elements are all modeled by homogeneous SC servers. The tool enables us to calculate the guaranteed delay bound and the maximum backlog amount for a session when the session passes through multiple SC servers. The tool is superior to the well-known Latency-Rate servers in the sense that SC servers can describe the worst-case behavior of a strictly larger class of schedulers.
Second, we propose a Service Curve (SC) algorithm that achieves high network utilization with O(log N) scheduling complexity where N is the number of sessions in variable-sized packet networks. Since most service curve algorithms are studied in fixed-sized networks, they cannot be applicable to general networks such as the Internet. In addition, how to allocate a service curve for a session determines both the level of network utilization and the deadline computation complexity in a service curve algorithm. However, there is little study on service curve allocation schemes to achieve high network utilization while having a constant time for deadline computations. We have found a kind of service curves that result in constant times for computing deadlines. Furthermore, we have proposed three service curve allocation schemes that achieve high network utilization with constant time deadline computation. The three are Delay Distribution (DD) scheme,
Network Service Curve Distribution (ND) scheme, and RC-EDF scheme. DD scheme can achieve the highest network utilization in the case of a single server. However, DD scheme is not optimal in the case of a network of servers. In this case, ND scheme can achieve higher network utilization than DD scheme. RC-EDF scheme can achieve exactly the same network utilization as the Rate-Controlled Earliest Deadline First (RC-EDF) algorithm, which is known to achieve a very high level of network utilization. We prove mathematically this identicalness. RC-EDF scheme can achieve the highest network utilization among the three. However, in this case, RC-EDF scheme has a disadvantage that the admission procedure for a session is complex compared to DD or ND scheme.
Third, we propose an algorithm that achieves high network utilization with O(log N) scheduling complexity where N is the number of sessions in fixed-sized packet networks. The proposed algorithm is a specialization of Service Curve Earlist Deadline (SCED) algorithm. SCED is a service curve algorithm proposed by Saroiwan et al. applicable to fixed-sized packet networks. However, there is no study on how to achieve high network utilization while holding O(log N) scheduling complexity where N is the number of sessions. The specialized SCED can be regarded as a version of the proposed SC algorithm optimized to fixed-sized networks. If SCED adopts the mentioned DD, ND, or RC-EDF scheme,
high network utilization can be achieved even in fixed-sized networks. Compared to the proposed SC algorithm, the special SCED has advantages in simplicity.
Fourth, we propose an algorithm that satisfies not only real-time requirement but also fair and link-sharing requirements in variable-sized networks. The proposed algorithm is a generalization of Hierarchical Fair Service Curve (H-FSC) algorithm, called generalized H-FSC. H-FSC integrates a real-time algorithm and a fair algorithm to satisfy real-time and link-sharing requirements, respectively. In addition, a mediating algorithm is used to distribute bandwidth between the two algorithms. The generalized H-FSC replaces the real-time algorithm by the above SC algorithm to achieve high network utilization. The generalized H-FSC can achieve higher network utilization than H-FSC. Even with this advantage, the total scheduling complexity is the same. We prove that the mediating algorithm can be implemented in O(log N) complexity where N is the number of sessions.
Finally, we propose an algorithm that achieves relatively high network utilization while having a constant time implementation cost without special hardware. The proposed algorithm is a Hierarchical Deficit Round Robin (H-DRR) algorithm applicable to variable-sized packet networks. (In fixed-sized networks, we also propose a Hierarchical Round Robin (H-DRR) algorithm.) The key feature of the proposed algorithm is that session queues are served indirectly based on a rate-based hierarchy. This indirect service makes it possible to separate high-rate sessions from low-rate sessions. That is, the number of low-rate sessions does not affect delay bounds for high-rate sessions. Surprizingly, the network utilization achievable by H-DRR is comparable to those of Generalized Processor Sharing (GPS) algorithms. Note that GPS algorithms have O(log N) scheduling complexity where N is the number of sessions.
광대역 통합 서비스망에서는 다양한 응용 프로그램들과 네트웍 제공자들이 각기 다른 요구를 필요로 하며, 대표적인 요구로는 실시간성, 공평성, 그리고 링크 공유성을 들 수 있다. 실시간성은 실시간 응용들에게 네트웍을 통과할 때 지연의 한계를 보장하는 것이다. 공평성과 링크 공유성은 직관적으로 대역폭이 골고루 분배되는 것을 의미하며, 공평성은 링크 공유성의 한 특별한 경우이다. 이러한 요구들을 만족시키는 핵심은 패킷 스케쥴링 알고리즘에 있다. 이 논문은 실시간성, 공평성, 그리고, 링크 공유성을 동시에 만족시키는 패킷 스케쥴링 알고리즘들을 설계하고, 분석하며, 구현하는 것을 다룬다. 목표로 하는 알고리즘은 높은 네트웍 유용도와 높은 공평성, 그리고 좋은 확장성을 추구한다. 여기서 높은 네트웍 유용도란 실시간성을 제공하는 세션의 수가 많음을 의미한다. 또, 높은 공평성이란 작은 시간 구간에 대해서도 대역폭이 골고루 분배됨을 의미한다. 좋은 확장성은 세션 수가 증가해도 구현 복잡도가 같이 증가하지 않음을 말한다. 그러나, 이 세 가지 목적은 서로 충돌하기 때문에 동시에 모두를 성취하는 것은 불가능하다. 이 논문에서는 이 목적들을 적절히 조율한 알고리즘들을 제안한다. 제안한 알고리즘들은 기존의 알고리즘에 비하면, 최소한 하나 이상의 목적에서 더 나으면서도 그 외의 목적들을 동일하게 성취한다.
첫째로 우리는 서비스 곡선 서버라 불리는, 가변 크기 패킷망에서 사용될 수 있는 분석 도구를 제안한다. 이 도구는 세션이 통과하는 라우터들이 모두 동일한 스케쥴러를 사용하는 경우가 아니라, 서로 다른 스케쥴러를 채용하는 경우에도 그 세션에 제공되는 지연의 한계를 추출할 수 있다. 이 도구는 스케쥴러 혹은 전송 라인과 같은 네트웍 요소들이 보장하는 서비스 곡선으로 특성화한다. 그러면, 이질적인 네트웍 요소들은 모두 “동일한” 서비스 곡선 서버로 모델링 된다. 제안하는 도구는 실시간 세션이 여러 개의 서비스 곡선 서버들을 통과할 때 걸리는 지연의 한계와 버퍼 큐에 쌓일 수 있는 최대량을 모두 계산할 수 있다. 이 도구는 기존에 잘 알려진 LR 서버보다 엄격히 더 큰 범주의 스케쥴러들을 포함할 수 있다는 장점을 가진다.
둘째로 우리는 가변 크기 패킷망에서 높은 네트웍 유용도를 O(log N) 구현 복잡도로 성취하는 서비스 곡선 알고리즘을 제안한다. 여기서 N은 세션 수를 나타낸다. 기존의 서비스 곡선 알고리즘은 대부분 고정 크기 패킷망에서 연구되었기 때문에 인터넷과 같이 일반적인 망에는 적용할 수 없었다. 또한, 서비스 곡선 알고리즘은 어떤 서비스 곡선을 각 세션에 할당하는가에 따라서 데드라인 계산 복잡도와 네트웍 유용도가 둘 다 달라진다. 그러나, 어떤 서비스 곡선 할당 방식이 데드라인 계산 복잡도가 상수 시간이 되면서, 높은 네트웍 유용도를 성취할 수 있는 지에 대한 연구가 거의 없었다. 우리는 어떤 서비스 곡선이 상수 시간에 데드라인을 계산할 수 있는 지를 찾았다. 또한, 이 상수 시간을 갖는 서비스 곡선에 기반하여 높은 네트웍 유용도를 성취할 수 있는 세가지 서비스 곡선 할당 방식을 제안한다. 이 세가지는 각각 DD 방식, ND 방식, RC-EDF 방식이라 불린다. DD 방식은 하나의 라우터만 고려하는 경우에 최적이다. 그러나, 세션이 여러 개의 라우터를 지나는 경우에는 ND 방식이 높은 네트웍 유용도를 갖는다. RC-EDF 방식은 잘 알려진 RC-EDF 알고리즘과 동일한 네트웍 유용도를 갖게 하는 방식이며 우리는 수학적으로 이 동일성을 증명한다. RC-EDF는 세 가지 방식 중에 가장 높은 네트웍 유용도를 성취할 수 있지만, 이 경우 DD 방식 혹은 ND 방식과 달리 세션의 승인 절차가 복잡하게 되는 단점이 있다.
셋째로 우리는 고정 크기 패킷망에서 높은 네트웍 유용도를 O(log N) 구현 복잡도로 성취하는 알고리즘을 제안한다. 여기서 N은 세션 수를 나타낸다. 제안하는 알고리즘은 특화된 SCED 알고리즘이다. SCED 알고리즘은 Sariowon 등의 저자에 의해서 제안된 것으로, 고정 크기 패킷망에서 사용될 수 있는 서비스 곡선 알고리즘이다. 그러나, 기존에는 어떤 서비스 곡선 할당 방식이 높은 네트웍 유용도를 가지면서 구현 복잡도를 O(log N)으로 유지할 수 있는 지에 대한 연구가 이루어지지 않았다. 특화된 SCED 알고리즘은 앞서 제안한 가변 크기 패킷망에서의 서비스 곡선 알고리즘을 고정 크기 패킷망에 최적화시킨 것이다. 만일 SCED 알고리즘이 앞서 제안한 서비스 곡선 할당 방식인 DD 방식, ND 방식, 그리고 RC-EDF 방식을 채용하면, 고정 크기 패킷망에서도 높은 네트웍 유용도를 성취할 수 있다. 이 특화된 SCED 알고리즘은 가변 크기 패킷망에서 제안된 서비스 곡선 알고리즘과 비교했을 때 더 간단하기 때문에 구현의 이점을 갖는다.
넷째로 우리는 가변 크기 패킷망에서 실시간성뿐만 아니라 공평성과 링크 공유성까지도 동시에 만족시키는 알고리즘을 제안한다. 제안하는 알고리즘은 H-FSC 알고리즘을 일반화한 것이다. H-FSC 알고리즘은 실시간성을 만족시키기 위한 실시간 알고리즘과 공평성과 링크 공유성을 만족시키기 공평 알고리즘을 통합한 것으로, 대역폭을 이 두 알고리즘에게 분배하는 중계 알고리즘이 사용된다. 제안하는 일반화된 H-FSC 알고리즘은 기존의 실시간 알고리즘을 앞서 제안한 서비스 곡선 알고리즘으로 교체한 것이다. 우리는 이 경우에 중계 알고리즘의 구현 복잡도가 증가하지 않고, 그대로 동일함을 수학적으로 증명한다. 일반화된 H-FSC 알고리즘을 H-FSC 알고리즘과 비교하면, 구현 복잡도는 동일하면서도 더 높은 네트웍 유용도를 갖는다.
마지막으로 우리는 별도의 하드웨어를 사용하지 않아도 구현 복잡도가 상수시간이면서, 상대적으로 높은 네트웍 유용도를 갖는 알고리즘을 제안한다. 제안하는 알고리즘은 계층적 라운드-로빈 알고리즘이다. 가변 크기 패킷망과 고정 크기 패킷망에서는 각각 H-DRR 알고리즘과 H-RR 알고리즘을 제안한다. 계층적 라운드-로빈 알고리즘의 가장 큰 특징은 세션들을 직접 서비스하지 않고, 서비스 비율에 근거한 계층적 데이터 구조를 통해서 간접적으로 세션 큐를 접근시킴으로써, 세션들간의 “분리”를 가능하게 만든다. 이 분리 기능 때문에 상위 계층에 의해서 서비스 받는 세션들은 하위 계층에 의한 세션들의 수에 전혀 영향을 받지 않는다. 이 특성으로 말미암아 계층적 라운드-로빈 알고리즘은 GPS 알고리즘에 필적하는 네트웍 유용도를 갖는다. 계층적 라운드-로빈 알고리즘에 비해서, GPS 알고리즘은 N이 세션 수를 나타낼 때 O(log N) 구현 복잡도를 갖는 단점이 있다.
