최근 ATM스위치를 위한 대부분의 연구는 병렬 하드웨어 자체에 규칙성과 자체 라우팅 특성을 가지는 다단계 상호연결 네트워크에 근거하여왔다. 그러나 네트워크는 동시에 또는 병렬로 전송되지만 서로 충돌을 피찰 수 없다는 측면에서는 블러킹 네트워크라고 할 수 있는데, 주로 밴얀 네트워크가 그 구조에 사용되어왔다. 밴얀 형태의 스위치에 있어서 처리율을 증가시키고, 블러킹을 제거하기 위해서 즉 내부링크의 속도를 증가시키고, 모든 스위치 노드에 버퍼를 두고, 병렬로 다중 연결링크를 두고, 그 네트워크 전에 부하를 균등하게 하는 통 여러 가지 방법들이 사용되어 왔다. 따라서 본 논문에서는 모든 블러킹이 제거되고 하드웨어 복잡도를 향상시키기 위하여 재순환 선플?스체인지 네트워크의 사용을 제안하였다. 이 구성은 하드웨어 복잡도 면에서 한층 단순하여진 구조인 재순환 셔플?스체인지 네트워크와, 동일한 목적지로 전달되는 패킷들에 있어서 우선순위가 결정된 후 순위가 높은 패킷은 다음 네트워크로 보내고, 순위가 낮은 패킷들을 재순환하는 트리구조의 순위 네트워크로 구성된다. 전송된 패킷은 밴얀 네트워크에서 분할 및 합성 알고리즘을 통하여 자체 라우팅 방식으로 최종 목적지에 전송되도록 구성된다. 처리율과 대기 시간 및 버퍼 크기에 따른 패킷의 손실율은 통일한 부하에 따라 각 포트에 도달한 패킷들의 확률을 이항분포로서 적용된다. 이때, $50\%$의 부하 정도면 버퍼 사이즈 $B_{size}=15$이상 즉, 16이면 허용 가능한 손실윤을 나타낸다. 그러므로 본 논문은 하드웨어의 복잡도 측면에서 기존의 바이토닉 정렬기를 재순환 셔플잌스체인지 네트워크로 구성하여 단순화 시켰다.
최근 ATM스위치를 위한 대부분의 연구는 병렬 하드웨어 자체에 규칙성과 자체 라우팅 특성을 가지는 다단계 상호연결 네트워크에 근거하여왔다. 그러나 네트워크는 동시에 또는 병렬로 전송되지만 서로 충돌을 피찰 수 없다는 측면에서는 블러킹 네트워크라고 할 수 있는데, 주로 밴얀 네트워크가 그 구조에 사용되어왔다. 밴얀 형태의 스위치에 있어서 처리율을 증가시키고, 블러킹을 제거하기 위해서 즉 내부링크의 속도를 증가시키고, 모든 스위치 노드에 버퍼를 두고, 병렬로 다중 연결링크를 두고, 그 네트워크 전에 부하를 균등하게 하는 통 여러 가지 방법들이 사용되어 왔다. 따라서 본 논문에서는 모든 블러킹이 제거되고 하드웨어 복잡도를 향상시키기 위하여 재순환 선플?스체인지 네트워크의 사용을 제안하였다. 이 구성은 하드웨어 복잡도 면에서 한층 단순하여진 구조인 재순환 셔플?스체인지 네트워크와, 동일한 목적지로 전달되는 패킷들에 있어서 우선순위가 결정된 후 순위가 높은 패킷은 다음 네트워크로 보내고, 순위가 낮은 패킷들을 재순환하는 트리구조의 순위 네트워크로 구성된다. 전송된 패킷은 밴얀 네트워크에서 분할 및 합성 알고리즘을 통하여 자체 라우팅 방식으로 최종 목적지에 전송되도록 구성된다. 처리율과 대기 시간 및 버퍼 크기에 따른 패킷의 손실율은 통일한 부하에 따라 각 포트에 도달한 패킷들의 확률을 이항분포로서 적용된다. 이때, $50\%$의 부하 정도면 버퍼 사이즈 $B_{size}=15$이상 즉, 16이면 허용 가능한 손실윤을 나타낸다. 그러므로 본 논문은 하드웨어의 복잡도 측면에서 기존의 바이토닉 정렬기를 재순환 셔플잌스체인지 네트워크로 구성하여 단순화 시켰다.
Most of the recent researches for ATM switches have been based on multistage interconnection network known as regularity and self-routing property. These networks can switch packets simultaneously and in parallel. However, they are blocking networks in the sense that packet is capable of collision w...
Most of the recent researches for ATM switches have been based on multistage interconnection network known as regularity and self-routing property. These networks can switch packets simultaneously and in parallel. However, they are blocking networks in the sense that packet is capable of collision with each other Mainly Banyan network have been used for structure. There are several ways to reduce the blocking or to increase the throughput of banyan-type switches: increasing the internal link speeds, placing buffers in each switching node, using multiple path, distributing the load evenly in front of the banyan network and so on. Therefore, this paper proposes the use of recirculating shuffle-exchange network to reduce the blocking and to improve hardware complexity. This structures are recirculating shuffle-exchange network as simplified in hardware complexity and Rank network with tree structure which send only a packet with highest priority to the next network, and recirculate the others to the previous network. after it decides priority number on the Packets transferred to the same destination, The transferred Packets into banyan network use the function of self routing through decomposition and composition algorithm and all they arrive at final destinations. To analyze throughput, waiting time and packet loss ratio according to the size of buffer, the probabilities are modeled by a binomial distribution of packet arrival. If it is 50 percentage of load, the size of buffer is more than 15. It means the acceptable packet loss ratio. Therefore, this paper simplify the hardware complexity as use of recirculating shuffle-exchange network instead of bitonic sorter.
Most of the recent researches for ATM switches have been based on multistage interconnection network known as regularity and self-routing property. These networks can switch packets simultaneously and in parallel. However, they are blocking networks in the sense that packet is capable of collision with each other Mainly Banyan network have been used for structure. There are several ways to reduce the blocking or to increase the throughput of banyan-type switches: increasing the internal link speeds, placing buffers in each switching node, using multiple path, distributing the load evenly in front of the banyan network and so on. Therefore, this paper proposes the use of recirculating shuffle-exchange network to reduce the blocking and to improve hardware complexity. This structures are recirculating shuffle-exchange network as simplified in hardware complexity and Rank network with tree structure which send only a packet with highest priority to the next network, and recirculate the others to the previous network. after it decides priority number on the Packets transferred to the same destination, The transferred Packets into banyan network use the function of self routing through decomposition and composition algorithm and all they arrive at final destinations. To analyze throughput, waiting time and packet loss ratio according to the size of buffer, the probabilities are modeled by a binomial distribution of packet arrival. If it is 50 percentage of load, the size of buffer is more than 15. It means the acceptable packet loss ratio. Therefore, this paper simplify the hardware complexity as use of recirculating shuffle-exchange network instead of bitonic sorter.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
가설 설정
이와 같이 처리율을 얻고, 모든 패킷의 블러킹된 패킷의 기대값을 구하기 위하여 입출력 패킷 의 보존 관계식을 이용한다. 우선, 이전에 타임 슬롯에 블러킹되지 않은 패킷의 확률을 정상 상태에서 a라고 가정한다.
6%이므로 일반적으로 출력 큐를 사용하였을 때 나타나는 부하율 약 80%보다는 성능면에서 많이 떨 어지는 단점이 있다. 이 결과로부터 입력 큐의 패킷의 수를 Random Variable K 라고 가정하고, 그 큐의 평균 길이를 구하기 위하여 다음과 같이 적용한다.
각 포트의 버퍼는 타임 슬롯에 따라 유입되는 패킷을 FIFO의 기법에 따라 처리된다.이때 유입되는 패킷은 슬롯마다 각 포트에 대한 전송 되는 트래픽, p의 확률을 가지며 그것은 어느 한 출력 포트에 도달하는 확률은 동일한 1/N의 확률을 갖는다 고 가정한다.
정리 2. 제어비트가 '0'일 때는 상위출력 연결을, T일 때는 하위출력 연결임을 가정하면, 역 밴얀 네트워크의 퍼뮤테이션은 밴얀 네트워크의 출력이 역밴얀 네트워크 의 입력으로 연결되었을 때 모든 스테이지에서 충돌이 발생하지 않는다.
제안 방법
6%까지 가능하나, 이 때의 버퍼의 크기는 현실성이 배제되므로, 실용 가능한 버퍼의 크기로 구현하기 위하여 부하율을 다음과 같이 적용하면, 55%인 경우 대략 40이며 45%의 경우는 버퍼 사이즈가 10이면 수용할 만한 패킷의 손실율을 갖는다. 그러므로 본 논문은 하드웨어의 복잡 도 측면에서 기존의 바이토닉 정렬기를 재순환 셔플잌 스체인지 네트워크로 구성하여 단순화 시켰다.
이때 역밴얀 자체 라우팅 네트워크가 되도록 밴얀 네트워크에서 스 테이지마다 목적지 주소의 기준 비트를 정하여 두 개의 데이터 집합 형태로 반복 분리함으로서 다음 스테이지 의 정보 없이도 스위치의 연결이 가능하도록 알고리즘을 설계하였다. 또한 역밴얀 네트워크에서는 앞의 기준 비트의 역순으로 스테이지마다 스위치 연결 설정을 위한 알고리즘을 제안하였다. 이렇게 구성된 스위치의 처 리율과 대기 시간 및 버퍼 사이즈에 따른 패킷의 손실 율을 분석한 결과 스위치의 부하율은 최대 58.
본 논문에서 제안된 스위치는 정렬의 기능을 수행하기 위하여 바이토닉 정렬기 대신에 하드웨어 복잡도 면 에서 아주 탁월한 단일 스테이지로 구성된 재순환 셔플 잌스체인지 네트워크를 사용한다, 기존의 정렬기에 비하여 경로설정 알고리즘 적용에 매우 단순하여진다. 또한 트리구조를 갖는 순위 네트워크를 구성하여 우선순 위를 정한 후 중복되는 패킷이 재순환 되도록 하여, 재 순환되는 패킷은 버퍼로 들어가게 되며 각 버퍼의 전단 에서 충돌될 경우 유입되는 패킷의 흐름이 유지되도록 제어된다.
본 논문에서는 정렬기로서 셔플잌스체인지 네트워크, 순위 네트워크 그리고 밴얀 네트워크로 구성된 ATM 스위치를 제안하였다. 우선, 하나의 스테이지로 구성되 어서 하드웨어의 복잡도 면에서는 탁월하게 단순화된 셔플잌스체인지 네트워크를 구성하고, 이를 통하여 목 적지 정보로 정렬된 패킷의 결과에 따라 트리 구조인 순위 네트워크에서 각각 동일한 목적지 주소를 갖는 패 킷들에 대하여는 우선순위를 부여하기위한 알고리즘 적 용하였다.
에서 패킷의 수 에 관한 확률 생성 함수를 얻기 위하여 사용될 수 있다.이 함수로부터 평균 큐의 크기를 계산하기 위하여 dQ/dz 를 구한 후 르피 탈 정리를 이용하여 극한 값을 구하면 다음과 같은 결과를 얻는다
우선순위가 가장 높은 패킷은 다음 단계인 밴얀 네트워크로 전송되어 서로 구별되는 목적지 주소를 갖게 된다. 이때 역밴얀 자체 라우팅 네트워크가 되도록 밴얀 네트워크에서 스 테이지마다 목적지 주소의 기준 비트를 정하여 두 개의 데이터 집합 형태로 반복 분리함으로서 다음 스테이지 의 정보 없이도 스위치의 연결이 가능하도록 알고리즘을 설계하였다. 또한 역밴얀 네트워크에서는 앞의 기준 비트의 역순으로 스테이지마다 스위치 연결 설정을 위한 알고리즘을 제안하였다.
이론/모형
Batcher의 알고리즘을 셔플잌스체인지 네트워크에서 각 스테이지마다 구현하기 위해 계속적으로 증가하는 m series를 사용한다. 이는 Batcher 의 정 렬 네트워크 의 연속적인 스테이지의 피봇 비트가 (;0), (11, io), (12, ii, io), im-2, ii, io)와 같이 구성되기 때문이다.
을 얻을 수 있다. 이와 같이 처리율을 얻고, 모든 패킷의 블러킹된 패킷의 기대값을 구하기 위하여 입출력 패킷 의 보존 관계식을 이용한다. 우선, 이전에 타임 슬롯에 블러킹되지 않은 패킷의 확률을 정상 상태에서 a라고 가정한다.
성능/효과
밴얀과 역밴얀 네트워크의 역상때문에, i 스테이지 의 하부 블럭의 다음 제어비트가 특성 1에 의해 항상 서로 보수 관계가 됨을 말한다. 결과적으로 역밴얀 네트워 크는 위의 유도 가설에 의해 모든 스테이지에서 충돌 없이 연결됨이 증명된다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.