WDM방식을 기반으로 한 광 네트워크상에서 최대 EDPs(Edge Disjoint Paths)을 이용한 라우팅 및 파장할당 알고리즘

추현승,정성택,이성창,Choo, Hyun-Seung,Chung, Sung-Taek,Lee, Sung-Chang 한국정보처리학회 2004 정보처리학회논문지 C : 정보통신,정보보안 Vol.11 No.5

본 논문에서 파장 분할 다중화(WDM) 방식을 이용한 광 네트워크상의 라우팅과 파장할당 알고리즘을 고찰해 보겠다. 선형 프로그래밍(Linear Programming)과 그래프 컬러링(Graph Coloring)의 조합으로 이루어진 기존의 RWA기법들은 복잡하며, 발견적 방법(Heuristic Method) 사용이 요구된다. 이와 같은 방법은 실행시간이 길며, 최악의 경우에는 실행이 불가능하여 결과를 얻지 못한다. RWA를 해결하기 위한 다른 방법은 최대 EDPs(Edge Disjoint Paths)를 얻기 위해 greedy algorithm을 적용하는 것이다. 이것은 실행시간이 짧지만 파장의 수를 최적으로 사용하지 못한다. 본 논문에서 최대의 EDPs를 얻기 위해서 최대 흐름 기법(Maximum Flow Technique)을 이용한 새로운 알고리즘을 제안한다. 그리고 제안한 알고리즘과 기존에 제시된 최대 EDPs 알고리즘을 비교해 보겠다. In the present paper routing and wavelength assignment (RWA) in optical WDM networks is considered. Previous techniques based on the combination of integer linear programming and graph coloring are complex and require extensive use of heuristics. Such methods are mostly slow and sometimes impossible to get results due to infeasibility. An alternative approach applied to RWA employs on the greedy algorithm for obtaining the maximum edge disjoint paths. Even though this approach is fast, it produces a solution for any connection request, which is very far from the optimal utilization of wavelengths. We propose a novel algorithm, which is based on the maximum flow technique to obtain the maximum quantity of edge, disjoint paths. Here we compare the offered method with previous maximum edge disjoint paths algorithms ap plied to the RWA.

IMT-2000을 위한 시스템간 핸드오프의 성능 향상

추현승,윤희용,최대규,Choo, Hyun-Seung,Youn, Hee-Yong,Choi, Dae-Kyu 한국정보처리학회 2002 정보처리학회논문지 C : 정보통신,정보보안 Vol.9 No.6

For a successful inter-system handoff, several important issues must be handled and additional new features must be considered. This paper focuses on the cellular structure of small cells which are required for the high density of population and a handoff scheme designed between two heterogenous networks. Incase of inter-system handoff (ISHO), the time required to complete the handoff can vary and depends on the structure of networks. And also the transmission of additional signals can increase the probability of failure for ISHO. Here we propose the sub-boundary cell base station (Sub-BBS) to alleviate the role of the BBS. The Sub-BBS is adjacent to BBS in the same regional mobile network. 쪼en the mobile terminal enters Sub-BBS, the network starts finding a new route and after entering BBS, it initiates the transformation process. The proposed scheme significantly reduces the ISHO failure rate compared to the existing one which is the most recent and known as efficient.

3차원 토러스 구조를 갖는 멀티컴퓨터에서의 동적 작업 스케줄링 알고리즘

추현승,윤희용,박경린,Choo, Hyun-Seung,Youn, Hee-Yong,Park, Gyung-Leen 한국정보처리학회 2001 정보처리학회논문지 A Vol.8 No.3

멀티컴퓨터 시스템은 많은 연산 노드들을 이용함으로써 높은 성능을 얻는다. 다차원 매쉬(mash)는 단순함과 효율성 때문에 멀티컴퓨터 구조로 널리 이용되었다. 본 논문은 3차원 토러스(torus) 시스템을 위한 최초 적합(first-fit) 방법에 기반한 효율적인 프로세서 할당 알고리즘을 제안한다. 이 알고리즘은 CST(Coverage Status Table)을 이용하여 3차원 정보를 2차원 정보로 변형하므로써 프로세서 할당 시간을 최소화 한다. 종합적인 컴퓨터 시뮬레이션 결과는 제안한 방법이 최적 적합(best-fit)에 기반한 기존 방법들과 비교해서 프로세서 이용률은 비슷하면서, 프로세서 할당 시간이 항상 짧다는 것을 보여준다. 성능 차이는 입력 부하가 증가함에 따라 더욱 두드러진다. 다른 스케줄링 환경상에서 제안된 방법의 성능을 조사하기 위해서, 전형적인 FCFS 스케줄링 기법과 함께 non-FCFS 스케줄링 기법도 연구된다. Multicomputer systems achieve high performance by utilizing a number of computing nodes. Multidimensional meshes have become popular as multicomputer architectures due to their simplicity and efficiency. In this paper we propose an efficient processor allocation scheme for 3D torus based on first-fit approach. The scheme minimizes the allocation time by effectively manipulating the 3D information an 2D information using CST (Coverage Status Table). Comprehensive computer simulation reveals that the allocation time of the proposed scheme is always smaller than the earlier scheme based on best-fit approach, while allowing comparable processor utilization. The difference gets more significant as the input load increases. To investigate the performance of the proposed scheme with different scheduling environment, non-FCFs scheduling policy along with the typical FCFS policy is also studied.

이차원 메쉬 상호 연결 망에 대한 효율적인 태스크할당 알고리즘

추현승(Choo Hyun Seung),박경린(Park Gyung Leen),유성무(Yoo Seong Moo) 한국정보처리학회 1999 정보처리학회논문지 Vol.6 No.6

An effective allocation of requested number of processors to newly incoming tasks in two-dimensional (2D) mesh interconnection networks is very important for achieving the desired high performance and resource utilization. It also needs to guarantee the complete recognition of the free submeshes based on contiguous and available processors with minimum overhead. An efficient task allocation algorithm for 2D meshes is presented in this paper. By employing a new approach for searching the one-dimensional array, the proposed algorithm can find the available submesh without the scanning of the entire 2D array unlike earlier designs. As a result, the new algorithm can significantly reduce the task allocation time. Comprehensive computer simulation shows that the average allocation time and waiting delay are much smaller than earlier designs irrespective of the size of meshes. The hardware overhead is comparable to other algorithms.

출구 버퍼모듈을 갖는 패킷교환식 상호 연결 망의 성능 분석

추현승(Choo Hyun Seung),박경린(Park Gyung Leen) 한국정보처리학회 1999 정보처리학회논문지 Vol.6 No.4

Packet-switched multistage interconnection networks(MINs) have been widely used for digital switching systems and super computers. In this paper we show that multiple packets in a switching element can move to the succeeding switching element in one network cycle by fully utilizing the cycle bandwidth. Only one packet movement was usually assumed in typical MINs. We present an analytical model for the MINs with the multiple packet movement scheme, and validate it by computer simulation. Comparisons with the traditional MINs of single packet movement reveal that the throughput is increased up to about 30% for practical size MINs. Similar result was also obtained for delays. The performance increase is more significant when the network traffic is nonuniform.

지연시간 한계의 만족과 효율적인 최소 지연변이 멀티캐스트 트리 생성 알고리즘

김문성,추현승,이영로,Kim Moon-Seong,Choo Hyun-Seung,Lee Young-Ro 한국정보처리학회 2005 정보처리학회논문지 C : 정보통신,정보보안 Vol.11 No.1

멀티미디어 그룹 애플리케이션들이 증가함에 따라, QoS 요구사항을 만족하는 멀티캐스트 트리를 생성하는 것은 매우 중요한 문제로 부각되고 있다. 본 논문에서는 NP-complete ans제인 지연시간 제한과 지연변이 제한을 만족하는 멀티캐스트 트리(DVBMT : delay- and delay variation-bounded multicast tree) 문제를 다루겠다. 이 문제는 목적노드들을 포함하는 신장 트리를 생성하는 것으로, 이들 목적노드들은 최소화된 멀티캐스트 지연변이를 가지며, 시작노드에서 각 목적노트로의 경로상의 지연시간은 제한된 지연시간을 만족한다. 이러한 문제의 해법은 온라인 게임이나 쇼핑, 또는 원격 회의와 같은 실시간 통신 서비스를 제공하는데 필요하다. 지금까지 DVBMT 문제를 이상적으로 다루었다고 알려진 DDVCA보다 본 논문에서 제시한 알고리즘이 더욱 효율적이라는 것은 성능 평가를 통해 확인할 수 있다. 이를 통해 확인된 성능 향상은 DDVCA를 normalized surcharge로 계산 했을 때, 약 $3.6{\%}$에서 $11.1{\%}$에 이른다. 본 논문에서 제안한 알고리즘의 시간복잡도는 $O(mn^2)$이다. With the proliferation of multimedia group applications, the construction of multicast trees satisfying QoS requirements is becoming a problem of prime importance. In this paper, we study the delay- and delay variation-bounded multicast tree (DVBMT) problem which is NP-complete. The problem is to construct a spanning tree for destination node, which has the minimized multicast delay variation, and the delay on the path from the source to each destination is bounded. A solution to this problem is required to provide decent real-time communication services such as on-line games, shopping, and teleconferencing. Performance comparison shows that the proposed scheme outperforms DDVCA which is known to be effective so far in any network topology. The enhancement is up to about $3.6{\%}{\~}11.1{\%}$ in terms of normalized surcharge for DUVCA. The time complexity of our algorithm is $O(mn^2)$.

비용 효과적인 MIPv6의 위치 관리 방안

최대규,이형민,추현승,Choi, Dae-Kyu,Lee, Hyung-Min,Choo, Hyun-Seung 한국정보처리학회 2004 정보처리학회논문지 C : 정보통신,정보보안 Vol.11 No.2

NIPv4의 지역적 등록 방식은 MN의 지역 등록을 지원한다. 이 방식에서는 MN이 HA에게 등록하는 경우, HA는 GFA 이동 에이전트의 주소를 등록한다. MN이 지역 망 내에서 FA 사이를 움직이는 경우에는 HA에게 등록하지 않고 GFA에게만 FA의 변경 사실을 알린다. MIPv6에서는 이와 유사한 방식으로 HMIPv6를 제안한다. HMIPv6에서는 GFA와 유사한 MAP가 존재한다. MN이 지역 내에서 핸드오프 하는 경우에는 MAP에게만 BU 메시지를 전달한다. 이로 인해 핸드오프 시 지연과 BU 메시지 비용을 줄인다. 하지만 HMIPv6에서 MN이 MAP 사이를 이동하는 경우, 자신과 통신하고 있는 모든 CN에게 위치 변경 사실을 알려야 하므로 시그널링 비용이 MN의 CN 수에 따라서 감격하게 증가한다. 본 논문에서는 MN이 MAP 간을 이동하는 경우에 MAP를 서로 연결함으로써 HMIPv6에서 존재하는 문제를 해결한다. 이때 MAP 사이의 연결에 따라서 발생하는 부가적인 비용은 여러 가지 변수로 전체 시그널링 비용 계산시 고려된다. 이 값과 HMIPv6에서 전체 시그널링 비용을 비교하여 MN이 MAP 사이를 움직이는 경우에 몇 단계까지 BU 메시지를 HA와 CN에게 보내지 않을지 결정한다. 본 방식을 사용하면 기존의 장식에 비하여 MN의 위치 관리비용을 효과적으로 사용할 수 있게 된다. Recently MIP becomes more important for the macro mobility support in the emergence of the global system such as IMT-2000. However this Protocol suffers from many weaknesses on the location management. MIPv4 regional registration is presented for the local registration of MNs. MIPv6 can benefit from the reduced mobility signaling with external networks by employing a local MAP, that is called HMIPv6. The total signaling cost of HMIPv6 is rapidly increased by the number of CNs of an MN when the MN moves around between MAPs. In this paper, we propose a new location management scheme in MIPv6 that reduces the total signaling cost in the location update based on HMIPv6 Here the MN does not send the BU to CNs and HA when it moves around between MAPs. Instead it informs the current location by transferring the modified BU to the previous MAP. According to the results of the performance analysis, we determine the upper bound for the number of forwarding links allowed among adjacent MAPs without the BU information.

통계적 구간 추정에 근거한 비용과 지연시간에 조화로운 유니캐스트 라우팅을 위한 새로운 인자

김문성,방영철,추현승,Kim, Moon-Seong,Bang, Young-Cheol,Choo, Hyun-Seung 한국시뮬레이션학회 2007 한국시뮬레이션학회 논문지 Vol.16 No.1

고속 네트워크에서 QoS 라우팅은 수많은 사용자의 요구를 만족하기가 매우 어렵다. 네트워크의 경로설정 알고리즘에서 측도로써 단지 링크지연시간만을 고려한다면 그 경로는 최소지연시간 경로가 될 것이며, 링크비용만을 고려한다면 최소비용경로를 찾을 것이다. 지연시간 한계의 최소비용(Delay Constrained Least Cost; DCLC)문제는 NP-hard 문제로 알려져 있으며, 두 개의 인자 경로비용과 지연시간을 혼합한문제로 생각할 수 있다. 경로설정 시 최소지연시간을 생각하면 그 경로는 상대적으로 높은 비용의 경로이며, 반대로 최소비용만을 생각하면 그 경로는 상대적으로 높은 지연시간을 얻는다. 따라서 DCLC문제를 풀기위해서는 단 하나의 인자만을 고려해서는 안 되며 두 개의 인자를 동시에 고려할 수 있는 새로운 인자를 요구하게 되었다. 따라서 본 논문에서는 DCLC 문제를 풀기위해 경로비용과 지연시간을 동시에 확률적으로 고려한 새로운 인자를 소개한다. 시뮬레이션 결과는 새로운 인자가 DCLC 문제에 적절하다는 것을 보여주었다. The development of efficient Qualify of Service (QoS) routing algorithms in high speed networks is extremely difficult to achieve, because in order to operate, divergent services require various quality conditions. If the parameter of concern is to measure the delay on a specific link, the routing algorithm obtains the Least Delay (LD) path. Meanwhile, if the parameter is to measure the link cost, the Least Cost (LC) path is calculated. The Delay Constrained Least Cost (DCLC) path problem of the mixed issues on the LD and LC has been shown to be NP-hard. The path cost of LD path is relatively more expensive than that of the LC path, and the path delay of the LC path is relatively higher than that of the LD path in the DCLC problem. In this paper, we introduce the new factor for balancing cost and delay. The simulation result shows that our introduced factor is satisfied to solve the DCLC problem.

AAA MIP 환경에서 공유영역 기반 세션키 재사용을 통한 고속 핸드오프 방식 연구

최유미,정민영,추현승,Choi, Yu-Mi,Chung, Min-Young,Choo, Hyun-Seung 한국정보처리학회 2005 정보처리학회논문지 C : 정보통신,정보보안 Vol.12 No.4

현재 무선 네트워크 IP를 위한 이동성 자원의 표준인 Mobile IP는 이동 노드(Mobile Node, MN)의 접속에 관한 사용자 인증이 비효율적이다. 본 논문에서는 네트워크 구성원들의 상호 인증 및 보안 서비스를 위해서 인증(Authentication), 권한부여(Authorization) 및 과금(Accounting)을 지원하는 AAA 프로토콜에 기반하여 Mobile IP의 보안성을 유지하고 빠른 핸드오프를 수행하는 새로운 보안 핸드오프 방식을 제안한다. AAA 프로토콜은 QoS를 제한하는 비효율적인 인증 절차가 존재하여 MN이 핸드오프를 수행할 때마다 새로운 세션 키를 분배 받아야 한다. 본 논문에서는 MN이 핸드오프를 수행할 때 발생하는 지연 시간과 MN의 인증으로 인한 AAA 서버의 오버헤드를 줄이고자 공유(Overlap, 오버랩) 네트워크 구조 기반의 세션키 재사용 방법을 제안한다 본 방식에서는 MN의 보안성 향상을 위하여 공유 세션 키를 유선상에서 전달하는 방식에 기반하고, 그에 따라 신속하고 자연스러운 핸드오프 메커니즘을 제공한다. 분석적 모델링결과에 의하면 제안하는 방식은 기존 세션키 재사용 방식과 비교하여 핸드오프 시간을 고려하는 핸드오프 실패율에 있어서 $40\%$정도의 성능향상을 보인다. The Mobile W provides an efficient and scalable mechanism for host mobility within the Internet. However, the mobility implies higher security risks than static operations in fixed networks. In this paper, the Mobile IP has been adapted to allow AAA protocol that supports authentication, authorization, and accounting(AAA) for security and collection for accounting information of network usage by mobile nodes(MNs). For this goal, we Propose the boundary tone overlapped network structure while solidifying the security for the authentication of an MN. That is, the Proposed scheme delivers the session keys at the wired link for MN's security instead of the wireless one, so that it provides a fast and seamless handoff mechanism. According to the analysis of modeling result, the proposed mechanism compared to the existing session key reuse method is up to about $40\%$ better in terms of normalized surcharge for the handoff failure rate that considers handoff total time.

구간 추정 기반의 지연시간을 고려한 저비용 유니캐스트 라우팅 방식

김문성,방영철,추현승,Kim, Moon-Seong,Bang, Young-Cheol,Choo, Hyun-Seung 한국정보처리학회 2004 정보처리학회논문지 C : 정보통신,정보보안 Vol.11 No.2

멀티미디어 응용 서비스에서는 특정 시간 내에 데이터 전송이 이루어져야 하는 시간 의존성이 있다. 이러한 실시간 특성은 네트웍의 QoS 보장을 위한 중요한 요소이다. 네트웍 사용자의 증가와 응용 프로그램의 데이터 전송율의 증가로 네트웍 자원을 효율적으로 사용하기 위한 연구는 계속 진행되고 있다. 종단간(End-to-End) 지연시간 제한 조건을 만족하면서 최소 비용을 갖는(Delay Constrained Least Cost, DCLC) 경로를 찾는 문제는 이미 NP-hard 문제로 알려져 있다. 최소 지연시간 경로의 비용은 최소 비용 경로의 비용보다 상대적으로 높은 경로 비용을 갖으며, 역으로 최소 비용 경로의 지연시간은 최소 지연시간 경로의 지연 시간보다 상대적으로 높은 지연시간을 갖는다. 본 논문에서는 이러한 단점을 극복하여 DCLC문제에 접근하기 위해 링크비용과 지연시간을 확률적으로 조합한 인자를 사용한 새로운 알고리즘을 연구하였다. 최근 Salama에 의해 제안된 DCUR 알고리즘은 최적에 가까운 알고리즘이나, 제안한 알고리즘은 DCUR 알고리즘과 비교하여 종합적인 컴퓨터 시뮬레이션 결과에 의하면 노드 수 200에서 38% 이상의 효과를 보았다. 본 알고리즘의 특징은 선택의 요소로서 새로운 인자를 만들었고, 링크를 순차적으로 선택하지 않고 동적으로 선택하는 방법을 구현하였다는 것이다. The end-to-end characteristic Is an important factor for QoS support. Since network users and required bandwidths for applications increase, the efficient usage of networks has been intensively investigated for the better utilization of network resources. The distributed adaptive routing is the typical routing algorithm that is used in the current Internet. The DCLC(Delay Constrained 1.east Cost) path problem has been shown to be NP-hard problem. The path cost of LD path is relatively more expensive than that of LC path, and the path delay of LC path is relatively higher than that of LD path in DCLC problem. In this paper, we investigate the performance of heuristic algorithm for the DCLC problem with new factor which is probabilistic combination of cost and delay. Recently Dr. Salama proposed a polynomial time algorithm called DCUR. The algorithm always computes a path, where the cost of the path is always within 10% from the optimal CBF. Our evaluation showed that heuristic we propose is more than 38% better than DCUR with cost when number of nodes is more than 200. The new factor takes in account both cost and delay at the same time.