이종 라우팅 메커니즘을 위한 quickest path 기반 통합 라우팅 알고리즘

방영철 ( Young-cheol Bang ),정성택 ( Sungtaek Chung ) 한국인터넷정보학회 2006 인터넷정보학회논문지 Vol.7 No.1

링크상에 대역폭과 지연 제약들이 존재하는 네트워크 상에서 Quickest Path 는 소스에서 목적지 까지 크기가 인 메시지를 전송하는데 최소지연을 보장한다. 본 논문은 Circuit Switching, Stop and Forward, 그리고 이것들의 조합으로 이루어진 메커니즘을 반영하는 노드들에서의 메시지 전달을 위한 6가지의 전송 모드들을 고려한다. 처음 5개의 각 모드에 대해, 크기가 인 메시지의 전송을 위한 Quickest Path를 계산하는 O(m²+mnlogn)시간 알고리즘을 소개한다. 그리고 마지막 모드에 대해 O(m+nlogn)시간 안에 Quickest path를 계산하는 알고리즘을 소개한다. The quickest path problem deals with the transmission of a message of size from a source to a destination with the minimum end to end delay over a network with bandwidth and delay constraints on the links. We consider two basic modes and four variations for the message delivery at the nodes reflecting the mechanisms such as circuit switching, Internet protocol, and their combinations. For each of first five modes, we present O(m²+mnlogn) algorithm to compute the quickest path for a given message size . For the last mode, the quickest path can be computed in O(m+nlogn) 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.

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

김문성,방영철,추현승,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.

가중치에 따른 독립적 두 변수의 효율적 조합을 사용한 경로 찾기 알고리즘

김문성 ( Moonseong Kim ),방영철 ( Young-cheol Bang ),추현승 ( Hyunseung Choo ) 한국정보처리학회 2004 한국정보처리학회 학술대회논문집 Vol.11 No.2

실시간 통신에 있어서 경로의 지연시간과 자원의 활용은 정말 중요한 요소들이다. 그렇기에 단 하나의 기준만으로 경로를 설정한다는 것은 많은 문제를 일으킨다. 따라서 여러 링크 요소들을 효율적으로 운용할 수 있는 프로토콜이 필요할 것이다. 본 논문에서는 NP-hard 문제로 알려진 DCLC (Delay Constrained Least Cost) 경로 문제를 풀기위한 새로운 인자를 소개하였다. 가중치를 주어 새롭게 링크의 인자를 만드는 휴리스틱 알고리즘은, 주어진 가중치에 따라서 효율적인 경로 설정을 한다는 것을 컴퓨터 시뮬레이션으로 확인하였다. 본 논문에서 소개하는 방법으로 CCLD (Cost Constrained Least Delay) 경로 문제 또한 가중치의 변화만으로 아주 쉽게 풀 수 있을 것이다.

EDP들의 참조 테이블을 이용한 실용적인 경로 설정 및 파장 할당 알고리즘

김명희(Myung Hee Kim),방영철(Young-Cheol Bang),정민영(Min Young Chung),이태진(Tae-Jin Lee),추현승(Hyunseung Choo) 한국정보과학회 2004 정보과학회논문지 : 정보통신 Vol.31 No.2

경로 설정 및 파장 할당(Routing and Wavelength Assignment) 문제는 파장 할당 전송 기법 (Wavelength Division Multiplexing)을 기반으로 하는 광 네트워크에서 중요한 분야이다. 경로 설정 및 파장 할당 문제는 선형 프로그램(Linear Programming)과 그래프 컬러링(Graph Coloring)의 조합으로 해결되거나, 경로 선택에 기반한 그래프 알고리즘에 의해서 해결된다. 이와 같은 방법은 복잡하며 휴리스틱 알고리즘(heuristic algorithm)이 요구된다. 본 논문에서는 각각의 연결 요구에 대한 최대한의 EDPs(Edge Disjoint Paths)를 구함으로써 경로 설정 및 파장 할당 문제를 효율적으로 해결하는 새로운 방법을 제안한다. 이렇게 구한 EDPs는 참조 테이블에 저장되고 가중치 매트릭스의 갱신에 사용된다. 각 연결 요구에 대한 경로는 순서대로 가중치 매트릭스를 참조하여 결정한다. 본 논문에서 제안하는 알고리즘이 현재 실질적으로 효율적이라 알려진 BGAforEDP(Bounded Greedy Approach for EDP)보다 약 50%의 수행 시간내에 같거나 작은 파장 수를 사용하여 연결 요구를 만족시켜주고 있음을 시뮬레이션을 통해서 확인할 수 있다. Routing and wavelength assignment(RWA) problem is an important issue in optical transport networks based on wavelength division multiplexing(WDM) technique. It is typically solved using a combination of linear programming and graph coloring, or path selection based graph algorithms. Such methods are either complex or make extensive use of heuristics. In this paper we propose a novel and efficient approach which basically obtains the maximum edge disjoint paths (EDPs) for each source-destination demand pair. And those EDPs obtained are stored in Lookup Table and used for the update of weight matrix. Routes are determined in order by the weight matrix for the demand set. The comprehensive computer simulation shows that the proposed algorithm uses similar or fewer wavelengths with significantly less execution time than bounded greedy approach (BGA) for EDP which is currently known to be effective in practice.

경로 추정 기반의 지연시간을 고려한 저비용 유니캐스트 라우팅 알고리즘

김문성 ( Moonseong Kim ),방영철 ( Young-cheol Bang ),추현승 ( Hyunseung Choo ) 한국인터넷정보학회 2007 인터넷정보학회논문지 Vol.8 No.1

특정 시간 내에 데이터 전송이 이루어져야 하는 실시간 멀티미디어 응용 서비스의 특성은 네트워크의 QoS(Quality of Service) 보장을 위한 중요한 요소이다. 종단간(End-to-End) 지연시간 제한 조건을 만족하면서 최소 비용을 갖는 (Delay Constrained Least Cost, DCLC) 경로를 찾는 문제는 이미 NP-hard 문제로 알려져 있다. DCLC 문제의 해법은 경로 지연시간과 비용간의 적절할 선택으로 해결하야 한다. 그러나 최적에 가까운 알고리즘으로 알려진 Salama의 DCUR 알고리즘[1]은 알고리즘의 단순성을 위하여 임의의 노드에서 경로 선정 시 목적 노드까지의 최소 비용 경로나 최소 지연시간 경로상의 다음 노드로만 제한을 하여 라우팅 경로의 비용측면에서 다소 비효율적이다. 일반적으로 최소 지연시간 경로의 비용은 최소 비용 경로의 비용보다 상대적으로 높은 경로 비용을 갖으며, 역으로 최소 비용 경로의 지연시간은 최소 지연시간 경로의 지연 시간보다 상대적으로 높은 지연시간을 갖는다. 본 논문에서는 이러한 점에 착안하여 DCLC문제를 해결하기 위해 확률적 추정 기법을 사용한다. 최근 발표한 독립적 두 변수간의 확률적 조합 알고리즘은 이러한 현상을 극복하기에 충분한 알고리즘이다[2]. 따라서 확률적 새로운 변수에 기반한 경로 추정 기법을 사용하였으며, 그에 대한 성능평가를 하였다. The development of efficient Quality of Service (QoS) routing algorithms in high speed networks is very difficult since divergent services require various quality conditions. If the QoS parameter we concern is to measure the delay on that link, then the routing algorithm obtains the Least Delay (LD) path. Meanwhile, if the parameter is to measure of the link cost, then it calculates the Least Cost (LC) path. The Delay Constrained Least Cost (DCLC) path problem of the mixed issues on LD and LC has been shown to be NP-hard. 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 propose the algorithm based on estimated path for the DCLC problem and investigate its performance. It employs a new parameter which is probabilistic combination of cost and delay. We have performed empirical evaluation that compares our proposed algorithm with the DCUR in various network situations.

두 독립변수의 효율적 조합을 사용한 멀티캐스트 트리 생성 알고리즘

김문성 ( Moonseong Kim ),방영철 ( Young-cheol Bang ),추현승 ( Hyunseung Choo ) 한국정보처리학회 2005 한국정보처리학회 학술대회논문집 Vol.12 No.1

멀티캐스트는 실시간 멀티미디어 전송 등에서 그 중요성이 매우 커지고 있다. 이러한 응용 기술들은 네트워크의 QoS(Quality of Service)보장을 위해 많은 자원을 필요로 한다. 네트워크의 자원은 한정되어 있기 때문에, 효율적인 자원의 사용을 위해서는 효율적인 멀티캐스트 라우팅 경로를 설정하는 것이 결정적 수단이다. 최소비용 멀티캐스트 라우팅 문제는 다양한 트리 최적화 문제를 해결하기 위한 기본적인 문제이며 다양한 연구가 있어왔다. 제안하는 알고리즘은 최소비용멀티캐스트 트리를 생성하는 휴리스틱 알고리즘으로 잘 알려진 TM 알고리즘과 가중치를 사용하여, 멀티캐스팅의 다양한 트리 최적화 문제에 적용되어 QoS에 따른 네트워크 자원의 사용효율을 극대화 하는데 기여할 것이다.

기가비트 라우터 시스템에서의 내부 데이터 처리를 위한 소프트웨어 구조

이왕봉,정영식,김태일,방영철,Lee, Wang-Bong,Chung, Young-Sik,Kim, Tae-Il,Bang, Young-Cheol 한국정보처리학회 2003 정보처리학회논문지 C : 정보통신,정보보안 Vol.10 No.1

인터넷 사용자의 증가와 인터넷을 이용한 전자상거래(E-commerce)의 확산 그리고 네트워크 게임 등으로 인해 인터넷상의 사용자 데이터는 끊임없이 증가하고 있는 상태이다. 이러한 인터넷의 확산을 지원하기 위해 고속 통신을 가능하게 할 초고속 라우터가 상용화되는 추세이다. 고속의 패킷 라우팅 처리를 위해 고안된 라우터 구조를 살펴보면, 라인 인터페이스와 호스트 프로세서는 각각 제어용 프로세서를 가지고 있어 독립된 디바이스로 동작하며 패킷 스위칭과 고속의 패킷 포워딩, 신속한 FIB(Forwarding Information Base)처리 등을 구현하고 있다. 본 논문에서는 라우팅 정보를 관리하는 유니캐스트 및 멀티캐스트 라우팅 프로토콜과 OAM(Operation And Maintenance) 관련 패킷을 비포워딩(nonforwarding) 패킷으로 정의하고, 이를 처리하는 라인 인터페이스와 호스트 프로세서에서의 소프트웨어 구조를 제시하였다. 또한 분산 시스템에 요구되는 프로세서 간의 통신 메커니즘으로 프로세서간 통신 처리용 프로토콜(Inter-Processor Communication Message Protocol)을 설계 및 적용하여 기존의 UDP/IP를 이용하는 통신 메커니즘에 비해 성능이 향상됨을 확인하였다. Internet traffic is getting tremendously heavier due to the exponential growth of the Internet users, the spread of the E-commerce and the network games. High-speed routers for fast packet forwarding are commercially available to satisfy the growing bandwidth. A high-speed router, which has the decentralized multiprocessing architecture for IP and routing functions, consists of host processors, line interfaces and switch fabrics. In this paper, we propose a software architecture tuned for high-speed non-forwarding packet manipulation. IPCMP (Inter-Processor Communication Message Protocol), which is a mechanism for IPC (Inter-Processor Communication), is also proposed and implemented as well. Proposed IPC mechanism results in faster packet-processing rate by 10% as compared to the conventional IPC mechanism using UDP/IP.

무선 센서 네트워크에서 이동성 관리 기법

유진근(Jinkeun Yu),정의훈(Eui-Hoon Jeong),방영철(Young-Cheol Bang),서대영(Dae-Young Seo),이계선(Kye-Seon Lee),주성순(Seong-Soon Joo) 한국IT서비스학회 2010 한국IT서비스학회 학술대회 논문집 Vol.2010 No.1

무선 센서 네트워크 환경 하에서 움직이는 노드를 고려하여 끊임없는 통신을 지원하기 위한 노드의 이동성 지원에 관한 연구가 주목을 받고 있다 센서 네트워크 환경은 자원이 제한적이고 노드들이 구성하는 네트워크의 크기가 비교적 작기 때문에 노드들의 이동성을 효율적으로 관리하기 위한 이동성 관리 기법에 대한 연구가 필요하다, 본 논문에서는 센서 네트워크 환경에서 노드의 이동성을 지원하기 위한 이동성 관리 기법을 제안하고 퀄넷(Qualnet) 시뮬레이터 통하여 그 성능을 검증한다.

그리드 기반 분산시스템을 통한 시스템 성능 평가

장수환(Soo-Hwan Jang),박수연(Soo-Yeon Park),박주현(Ju-Hyun Park),방영철(Young-Cheol Bang),공기석(Ki-Sok Kong) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.2Ⅰ

그리드는 국가 전략산업 뿐만 아니라, 여러 응용분야에서도 실용성이 많이 대두 되면서, 국내를 비롯한 유럽과 미주에서 많은 연구가 진행 중이다. 본 실험에서 분산된 고성능의 컴퓨팅자원을 활용하여 자체 제작한 파이 프로그램의 실행을 통하여, 클러스터의 작업능력과 클러스터수에 따른 처리 시간의 차이를 분석하여, 그리드 분산시스템의 필요성과 효율성을 확인하고자 한다.