로그-하이퍼큐브의 임베딩 알고리즘과 지름 개선

Study on Embedding Algorithm and Improving the Diameter of Log-hypercube

상호연결망으로 널리 알려진 하이퍼큐브는 노드 및 에지 대칭성, 간단한 라우팅 알고리즘, 분지수 n, 지름 n, 망비용 을 갖는다. 하이퍼큐브는 여러 가지 장점을 갖고 있지만, 노드 개수 증가에 비해 분지수가 으로 증가하는 단점이 있다. 이러한 단점은 상호연결망의 망비용이 이 되는 이유이다. 로그-하이퍼큐브는 하이퍼큐브의 망비용을 개선하기 위해 최근에 제안된 상호연결망이다. 로그-하이퍼큐브는 분지수 증가를 최소화하여 분지수를 으로 개선하였다. 또한 지름 값은 1.5n-1로 알려졌다. 이러한 결과를 이용하여 망비용은 으로 하이퍼큐브 보다 개선된 결과를 갖는다. 본 연구에서는 로그-하이퍼큐브와 하이퍼큐브의 관계를 분석하기 위해 두 그래프 사이의 임베딩 알고리즘을 개발한다. 하이퍼큐브를 로그-하이퍼큐브에 임베딩하는 연장율 값은 이다. 임베딩의 결과는 하이퍼큐브에서 개발된 알고리즘을 로그-하이퍼큐브에서 활용하고자 하는 경우 추가적인 비용이 이 요구된다. 또한 로그-하이퍼큐브의 지름 값 1.5n-1을 1.25n-1로 개선하였다.

The Hypercube, which is widely known as the interconnection network, have symmetrical node and edge, a simple routing algorithm, a degree of n, a diameter of n, and a network cost . The hypercube have many advantages, but its degree increases to in comparison to the increasing number of nodes. This disadvantage is the reason why the network cost of the interconnection network is . The Log-hypercube is an interconnection network which was suggested recently to improve the Hypercube’s network cost. The Log-hypercube improved the degree to by minimizing the increase of the degree. Also its degree is known as 1.5n-1. By using this result the network cost is , which is a better result than the Hypercube. In this research we develop the embedding algorithm between the two graphs to analyze the relation between the Log-hypercube and Hypercube. The extension rate which embeds the Hypercube in the Log-hypercube is . The embedding’s result tell us that an additional price is required when we use the algorithm which was developed in the Hypercube in Log-hypercube. Also we improved the Log-hypercube’s diameter (1.5n -1) to (1.25n –1).