There are many applications in the computer and communications fields that require the scheduling of a time-division multiplexed switches that has M input resources and M output resources. This gives rise to a scheduling problem in which the switch is to provide conflict-free connections to switch packets from the M inputs to the M outputs.
There are two kinds of issues on scheduling problem. One is a time slot assignment problem which is to find a conflict-free assignment of traffic units to slots such that the frame length is minimized. The other is a cell scheduling problem which is to avoid output conflicts with the objective of the maximizing throughput of a switching system.
The objective of this thesis is to develop an efficient time slot assignment algorithm and a cell scheduler which it can be easily implemented as a practical scheduler providing high throughput. In this thesis, first we presented a new method for time slot assignment. Unlike previous approaches which are based on network flow model, the novel method, called binary time slot assignment algorithm, is based on the graph coloring model. When the length of an initial set of time-slot requests is 2's power, this set is divided into two sets of time-slot requests using binary divide and conquer method based on the graph coloring model. This process is continued until resulting sets of time-slot requests are of length one. The time complexity of the proposed algorithm is O(NL $\log_{2}$ L), where N is the number of input/output links of the central switch and $L$ is the number of time-slots allotted to each link in the frame.
Second, we proposed a generalized time slot assignment algorithm, when the length of an initial set of time-slot requests is not equal to 2's power, using binary time slot assignment algorithm and network flow model. The time complexity of the algorithm is $O(M^3\cdot\log_{2}L+NL\cdot\log_{2}L)$. As we know, the most efficient algorithm proposed in the literature has been complexity of $O(min(L,M^2)$·min(N, $\sqrt{M})\cdotM^2)$, where M is the number of subscribers that is larger than N. To give a clear idea of relative efficiency between two algorithms, let us give a typical situation of M = L = $O(N^2)$. In this configuration, our algorithm makes a significant improvement in time complexity by the order of $O(M^{1.5}/\log_2M)$. The other main advantage of the proposed algorithm is that it is naturally suited to parallel implementations.
Third, although time slot assignment algorithms are inherent sequential, we described a parallel time slot assignment algorithm using PRAM model of computation. While the best-know parallel algorithm takes $O(M^3\log_2M)$ using $\lfloor{L/2}\rfloor$ processors. our parallel algorithm run in $O(M^2\log^2_2M)$ using same processors.
Finally, we presented a novel cell scheduler, called a self-firing cell scheduler, for input queuing ATM switches. The proposed self-firing cell scheduler consists of $N^2$ processing elements connected by a two dimensional torus network, where each processing can determine the diagonal by itself in a distributed manner. It allows a simple implementation for high speed ATM switches.
멀티컴퓨터나 통신분야에서 많이 응용되고 있는 시분할 다중스위치는 M개의 입출력으로 구성되어 있으며, 전송과 스위칭은 연속되는 프레임에 의해 동작된다. 프레임은 여러개의 타임스롯으로 나뉘어 지고, 이 타임스롯에 전송하고자 하는 트랙픽을 스위치에서 충돌이 생기지 않도록 스케쥴링해야 하는 스케쥴링 문제가 야기된다.
스케쥴링 문제에는 두가지 관점이 있다. 하나는 프레임의 길이을 최소화하면서 충돌없이 트랙픽을 할당하는 문제이며, 다른 하나는 프레임의 개념없이 매 타임스롯마다 트랙픽을 최대로 보낼수 있도록 스케쥴링하는 문제이다. 전자는 주로 SS/TDMA 시스템에 많이 사용되며, 후자는 ATM 스위치에서 응용되고 있다.
본 논문에서는 효율적인 타임스롯 할당 알고리즘과 높은 성능을 가지면서 쉽게 구현 가능한 스케쥴러를 제안하였다.
첫번째로, 타임스롯 할당을 위한 새로운 방법을 제안한다. 네트워크 흐름 모델을 사용한 기존방법과는 다르게, 그래프 칼라링 방법을 기초로 하여 제안된 이진 타임스롯 할당 알고리즘은 주어진 트랙픽의 프레임 길이가 2의 멱승일때 트랙픽을 정확히 반으로 나누어 할당한다. 이때, 시분할 다중스위치가 가지고 있는 물리적 제약조건을 만족시키면서, 분할된 트랙픽의 프레임 길이가 1이 될때까지 계속적으로 반복해 분할한다. 이 방법을 사용한 이진 타임스롯 할당 알고리즘의 시간복잡도는 O(N·L $\log_2$ L)이다. 여기서 N는 입출력의 링크수이고, L은 프레임의 길이다.
두번째로 이를 프레임의 길이에 상관없이 타임스롯에 할당할 수 있는 일반한된 타임스롯 할당 알고리즘을 제안한다. 네트워크 흐름 모델을 사용하여 주어진 트랙픽을 프레임의 길이가 2의 멱승이 되도록 스큐 분할 알고리즘을 통해 몇개의 분할된 트랙픽들을 먼저 구한다. 분할된 트랙픽들을 각각의 이진 타임스롯 할당 알고리즘을 이용하여 타임스롯에 할당한다. 네트워크 흐름 모델과 그래프 칼라링을 사용한 일반화된 타임스롯 알고리즘은 기존의 가장 효율적인 알고리즘보다 시간복잡도면에서 $O(M^{1.5}/\log_2M)$정도 향상됨을 보여주고 있다. 여기서 M은입출력 가입자 수이다. 또한 기존의 타임스롯 할당 알고리즘이 시켄스 알고리즘인 반면 우리가 제안하는 타임스롯 할당 알고리즘은 자연스럽게 병렬화 할수 있다는 장점이 있다.
세번째로, 일반화된 타입스롯 알고리즘을 사용하여 시간복잡도가 $O(M^2\log_{2}M)$인 병렬 타임스롯 할당 알고리즘 제안하였다. $\lfloor{L/2}\rfloor$개의 프로세서를 사용할때 기존의 가장 효율적인 알고리즘보다 $O(M/\log_{2}M)$이 향상되었다.
마지막으로, 높은 성능을 가지며 쉽게 구현 가능한 셀 스케쥴러를 제안한다. 제안된 스케쥴러는 Self-Firing 셀 스케쥴러라 하며 $N^2$개의 프로세서들로 구성되며, 이를 Torus형태로 서로를 연결한 구조이다. 이러한 스케쥴러에서 제안된 셀 스케쥴링 알고리즘을 수행하므로써, 높은 성능을 갖도록 했다. 또한 쉽게 구현가능하고, 빠른 시간내에 스케쥴링함으로써, 속도가 빠른 ATM 스위칭에 응용되도록 제안하였다. 한편 셀 스케쥴러의 성능을 평가하기 위해 3상 알고리즘과 비교 수행하여 그 우수함을 보였다.
