Asynchronous transfer mode (ATM) has been widely accepted as the most promising solution to implement the broadband ISDN. But, since ATM is based on the use of very high-speed and reliable fiber optic transmission facilities, it has been very important issue to design a high-performance packet switch to meet the throughput requirements. Thus, various architectures for ATM switches have been proposed, and many of the proposed switching architectures employ the banyan network as a basic building block because of its hardware simplicity and selfrouting capability. In this dissertation work, we study the cut-through buffered banyan and the dilated banyan networks for ATM switch design.
First, we present an analytic model for estimating the performance of buffered banyan networks with cut-through. In the analytic model, we assume that the input traffic is uniform and consider throughput and delay as relevant performance measures. In order to consider the dependencies between consecutive time slots, we first analyze two head-of-line (HOL) buffers of a switching element (SE) by introducing the ""blocked"" state, and then analyze the whole buffer module in the SE with a Markov chain. To validate the analytic model, we compare some analytic results to simulation results. The comparison shows that the analytic results appear to be in good agreement with simulation for light and medium loads, but have small difference from simulation results at heavy load.
Next, we propose a dilated banyan network with back-pressure mechanism to fully utilize the routing capacity wasted in a pure dilated banyan network. The proposed switch has both input and output queues, and employs a priority scheme in order to prevent the out-of-sequence problem. We also design the nonblocking SE which is constructed using two sorting networks and a routing stage, in order to reduce the hardware complexity of the dilated network. The performance of the proposed switch is analyzed under the uniform traffic assumption. Although we assume that the input traffic pattern is uniform, the traffic flow inside the network is not uniform since a blocked packet is destined to the same destination as in the previous time slot. Thus, to consider the nonuniformity, we introduce some approximations into the analyses of the network and output queue. Numerical and simulation results show that the maximum throughput of the proposed switch is improved by about 11% as compared to that of the pure dilated banyan network in case of a dilation degree d = 2, and the maximum throughput of about 1 is obtained with d = 3.
Finally, we propose a dilated banyan network with recirculation. Unlike the switch with back-pressure, the proposed switch utilizes the wasted routing capacity of the pure dilated banyan network by employing the deflection routing algorithm and recirculation links. In the output queue, a resequencing function is implemented to handle the out-of -sequence problem occurring in the network. We first consider a contention resolution method by random service for processing of the recirculated packets, and analyze the performance. For analysis, we assume that the input traffic pattern and the traffic flow inside the network are uniform. From numerical and simulation results, we can see that the maximum throughput of the switch is a little higher than that of the network with back-pressure, while the switch requires a large number of output buffers and long resequencing delay. Next, we consider a contention resolution method by priority service, and analyze the throughput performance of the network under the uniform assumption. Numerical and simulation results show that the throughput performances of two contention resolution methods is almost the same. But, by employing the priority service, we can see that the required output buffers and resequencing delay decrease significantly.
ATM (asynchronous transfer mode)은 광대역 종합 정보 통신망의 구축을 위한 가장 적절한 해결책으로 인식되어 왔다. 그러나, ATM은 고속의 신뢰성 있는 광섬유를 전송 매체로 사용하므로 그 전송 속도를 충족시키는 고성능의 패켓 스위치의 설계가 중요한 문제로 나타났다. 이에따라, 많은 스위치 구조에 대한 제안이 발표되었으며, banyan 네트웍은 간단한 하드웨어와 자가 routing의 이점으로 제안된 스위치들의 기본 블럭으로 주로 채택되어 왔다. 본 논문에서는 buffered banyan과 dilated banyan 네트웍을 이용한 ATM 스위치 설계에 대해 연구하였다.
먼저 cut-through 기능이 있는 buffered banyan 네트웍 스위치의 성능 측정을 위한 분석 모델을 제시하였다. 분석 모델에서는 입력 트래픽이 균일하다고 가정하고, 성능 지수로 스위치의 이용 효율과 전송 지연 시간을 생각했다. 연속된 슬롯 사이의 확률의 의존성을 고려하기 위해 스위칭 엘리멘트에 있는 두 개의 HOL (head-of-line) 버퍼에 대해 블로킹 상태를 도입하여 분석하고, 전체 버퍼모듈을 마르코프 체인을 이용하여 분석했다. 분석 모델의 검정을 위해 분석결과를 시뮬레이션과 비교하였으며, 그 결과 적정 부하 상태에서는 결과가 잘 일치하였으며 과부하에서는 약간의 차이를 보였다.
다음으로 단순 dilated banyan 네트웍에서 낭비되는 routing 용량을 충분히 이용하기 위해 전송 확인 장치가 있는 dilated banyan 네트웍을 제안하였다. 제안된 스위치는 입력 queue와 출력 queue를 동시에 가지며 priority 체계를 사용하여 패켓 전송시의 순서 오류를 방지한다. 또한, 두개의 sorting 망과 한개의 routing 단으로 구성되는 nonblocking 스위칭 엘리멘트를 설계하여 스위치의 하드웨어 복잡도를 줄였다. 제안된 스위치의 성능은 스위치에 입력되는 트래픽이 균일하다는 가정하에서 분석및 시뮬레이션 되었다. 분석 모델에서는 재전송되는 패켓에 의해 발생하는 스위치 내부에서의 트래픽의 불균일을 고려하여 근사기법을 사용했다. 분석 및 시뮬레이션 결과 dilation이 2 일때 단순 dilated banyan 네트웍에 비해 스위치의 최대 이용 효율이 약 11% 향상되며, dilation이 3 일 때는 거의 100% 의 최대 이용 효율을 얻음을 알 수 있었다.
마지막으로 재순환 장치가 있는 dilated banyan 네트웍을 제안하였다. 제안된 스위치는 전송 확인 기능이 있는 스위치와 달리 굴절 routing 알고리듬과 재순환 선로를 사용하여 단순 dilated banyan 네트웍의 성능을 개선한다. 출력 queue에는 망 내부에서 발생되는 패켓의 전송 순서 오류를 처리하기 위해 패켓 재배열 기능이 구현된다. 스위치의 성능은 스위칭 엘리멘트에서 패켓 충돌시 임의 선택에 의한 해결 방식을 채택할 경우와 순환 횟수에 따라 우선권을 주는 경우로 나누어 분석하고 시뮬레이션 하였다. 분석 모델에서는 스위치 입력단과 스위치 내부에서의 트래픽 흐름이 균일하다고 가정하였다. 분석및 시뮬레이션 결과 스위치의 최대 이용 효율이 전송 확인 장치를 사용한 경우보다 약간 높으며, 두가지 충돌 해결 방식에 대해 스위치의 최대 이용 효율은 거의 같음을 알 수 있었다. 또한, 우선권을 주는 방식을 채택할 때 필요한 출력 버퍼의 수와 패켓 재배열을 위한 지연 시간을 크게 줄일 수 있음을 알 수 있었다.
