MPLS 를 이용한 IP 네트웍 이동성 서비스 최적화

박혜경 ( Park Hae Kyeong ),백의현 ( Euhyun Paek ) 한국정보처리학회 2004 한국정보처리학회 학술대회논문집 Vol.11 No.2

최근 널리 사용되고 있는 공중 무선랜 및 일반 무선랜 서비스가 확장되면, 사용자들은 자동차, 기차, 버스, 비행기, 여객선 등에서 자신의 노트북을 이용하여 인터넷 서비스를 받을 수 있도록 요구하게 될 것이다. 이러한 서비스가 가능하기 위해서 단말이 아니라 네트웍에 대한 이동성 서비스가 제공되어야 한다. 본 연구에서는 MPLS망을 이용하여 이동 단말 및 이동 네트웍의 데이터 전달 경로를 최적화 하는 방법을 제시하고자 한다. 이 방법은 IP 네트웍 이동성을 위한 경로 최적화를 MPLS망의 에지 라우터에서 제공하는 방법이다. 에지 라우터 LER는 IP 네트웍의 이동 정보인 바인딩 정보를 전달 받아 바인딩 캐쉬에 저장하고, 바인딩 정보를 이용하여 미리 설정되어 있는 적절한 LSP에 매핑하여 LIB를 구성한다.

이중연결 요소를 구하는 최적 임의 병렬 알고리즘 (pp.873-876)

박혜경(Hae Kyeong Park),유관우(Kwan Woo Ryu) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.1A

본 논문에서는 정점의 수(│V│)가 n이고 간선의 수(│E│)가 m인 연결된 무방향 그래프 G=(V,E)가 주어질 때, 이 그래프의 이중연결 요소를 구하는 최적 임의 병렬 알고리즘을 제시한다. E에 속한 임의의 두 간선 e와 g가 같은 간선이거나 같은 단순 사이클에 속하면, e와 g는 같은 이중연결 요소에 속하게 되는데, 이때 E를 같은 이중연결 요소에 속하는 집합들로 나누는 것을 이중연결 요소 문제라 한다. 이 이중연결 요소 문제를 최적으로 해결하기 위해 가장 걸림들이 되는 부분은 G의 신장 트리를 나타내는 간선 리스트가 주어질 때, 이 신장 트리의 오일러 행로를 쉽게 구할 수 있는 적절한 인접 리스트를 구하는 부분인데, 이를 위해서는 최적인 안정된 정수 정렬 알고리즘의 개발이 필수적이라고 믿어왔다. 그러나 지금까지 이러한 알고리즘은 개발되지 않고 있다. 따라서 본 논문에서는 [8]에 나타난 최적이지만 불안정한 정수 정렬 알고리즘을 사용하여 위의 인접 리스트를 구하는 최적 임의 병렬 알고리즘을 제시하고, 또 이 알고리즘을 이용하여 이중연결 요소를 Priority CRCW PRAM 상에서 O(logn)시간과 O(m+n)연산으로 구하는 최적 알고리즘을 제안한다.

우편 모델에서 온라인 최적 병렬 방송 알고리즘

박혜경(Hae Kyeong Park),하경주(Kyeong Ju Ha),유관우(Kwan Woo Ryu) 한국정보과학회 1996 정보과학회논문지 : 시스템 및 이론 Vol.23 No.1

최근 병렬 컴퓨터의 하드웨어 구조가 강력한 여러 프로세서들이 통신 네트워크에 의해 연결되는 경향을 보임에 따라, 병렬 시스템의 네트워크 구조를 프로세서들 사이의 완전 통신 그래프 모양으로 가정하는 경향을 띠게되었다. 우편 모델(postal model)은 이러한 특징을 잘 표현하는 모델로 통신 지연(latency) 인자 λ(≥1)를 사용하여 알고리즘의 설계와 분석, 실제 기계에서 알고리즘의 성능평가 모두를 용이하게 한 병렬 모델이다. 이러한 병렬모델의 특성을 알아보려는 시도에서 본 논문에서는 메세지 방송 문제와 전위합(prefix sums) 문제에 대해서 생각해 본다. 하나의 메세지를 방송하는 문제는 메세지 M을 가지는 프로세서 P_0가 다른 모든 프로세서(P₁, P₂, ..., P_(n-1))로 M을 전송하는 문제이다. Bar-Noy와 Kipnis는 우편모델에서 이 문제를 해결하는 최적 알고리즘을 제안하였는데, 이 알고리즘은 최적 알고리즘이지만 오프라인으로 수행된다는 단점이 있다. 본 논문에서는 이 문제를 해결하기 위한 간단하면서도 최적인 온라인 알고리즘을 제시하고, 또 여기서 사용된 방법을 이용하여 전위합 문제를 최적 시간에 해결하는 알고리즘을 제시한다. The hardware organizations of massively parallel processors seem to be converging towards a collection of powerful processors connected by a communication network that can be modeled as a complete graph. The postal model that conveys this trend very well is a parallel model, by using a parameter λ≥1 for describing communication latency, to design and analyze algorithms with ease and to accurately predict the performance of these algorithms on real machines. We consider the single-element broadcasting problem and the prefix sums problem to show the appropriateness of the postal model as a parallel model. The single-element broadcasting problem is that processor P_0 holding message M broadcasts the message to all the other processors P₁, P₂, ..., P_(n-1) An optimal algorithm in this model for this problem has been proposed by Bar-Noy and Kipnis. but this algorithm is an off-line algorithm. In this paper, we present another optimal algorithm in the model that is simple as well as on-line. We also show that the same strategy can be applied to obtain an optimal algorithm for solving the

우편 모델에서 전위합을 구하는 효율적인 병렬알고리즘

박혜경(Hae Kyeong Park),유관우(Kwan Woo Ryu) 한국정보과학회 1995 한국정보과학회 학술발표논문집 Vol.22 No.1

최근 병렬 컴퓨터의 하드웨어 구조가, 강력한 여러 프로세서들이 통신 네트워크에 의해 연결되는 경향을 보임에 따라, 병렬 시스템의 네트워크 구조를 프로세서들 사이의 완전 통신 그래프 모양으로 가정하는 경향을 띠게되었다[1,2,3,5,8]. 우편 모델(postal model)[3]은 이러한 특징을 잘 표현하는 모델로 통신 지연(latency) 인자 λ(≥1)를 사용하여 알고리즘의 설계와 분석, 실제 기계에서 알고리즘의 성능평가 모두를 용이하게 한 병렬 모델이다. 본 논문에서는 이러한 우편 모델 상에서 전위합(prefix sums) 문제를 해결하고자 한다. 전위합 문제는 n개의 원소의 집합 S=(x_0, x₁,…,x_n-¹)와 이진 결합 연산자(binary associative operator)* 가 주어질 때, n개의 부분합 S_1=x_0*x₁*… *x₁ (O ≤ i ≤ n-1)를 계산하는 문제이다. 본 논문에서는 이 전위합 문제를 해결하는 두 알고리즘을 제시하는데, 첫째 λ차 트리를 이용한 (4λ-1)[logλn]-1시간의 온라인(on-line) 알고리즘과, 둘째 피보나치트리를 이용한 2fλ(n)-1시간의 오프라인(off-line) 알고리즘이다. 여기서 fλ(n)은 하나의 메세지를 모든 프로세서로 방송(broadcast)하는데 필요한 시간, θ(λlogn/log(λ+1))을 나타내며, 제안한 오프라인 알고리즘은 이 최적 방송시간의 약 2배 정도에 수행되는 효율적인 알고리즘이다.

MPLS를 위한 라우팅 프로토콜 설계 및 구현

박혜경(Hae-Kyeong Park),전성익(Sung-Ik Jun),강선무(Sun-Moo Kang) 한국통신학회 2000 한국통신학회 학술대회 및 강연회 Vol.2000 No.5

Foucault와 여성의 언어

박혜경(Hae-Kyeong Park) 영남대학교 인문과학연구소 1995 人文硏究 Vol.17 No.1

홈네트워크에서 IPv6 전환 기술 연구

박혜경 ( Hae-kyeong Park ),백의현 ( E-hyen Paik ) 한국정보처리학회 2005 한국정보처리학회 학술대회논문집 Vol.12 No.2

가정 내의 정보가전기기가 네트워크로 연결돼 기기, 시간, 장소에 구애 받지 않고 서비스가 이뤄지는 유비쿼터스 디지털 홈으로 진화하기 위해, 댁내 많은 수의 단말들을 수용하고 이동성을 지원할 수 있는 IPv6 기술의 적용이 필수적으로 요구된다. 본 논문에서는 홈네트워크에서 IPv6 전환기술을 적용하기 위한 방안 및 구조 등을 제시하고자 한다.

분산 망에서 자원발견을 위한 결정 알고리즘

박혜경(Hae Kyeong Park),유관우(Kwan Woo Ryu) 한국정보과학회 2001 정보과학회논문지 : 정보통신 Vol.28 No.4

본 논문에서는 네트웍으로 연결된 일련의 장치들이 서로를 발견하는 문제인 자원 발견 (Resource Discovery)문제를 해결하는 알고리즘을 제안한다. 최근 Harchol등은, 장치의 수를 n이라 할 때, O(nlog² n) 연결 통신복잡도와 O(n²log² n) 포인터 통신복잡도를 가지고 O(log² n) 시간복잡도에 이 문제를 해결하는 알고리즘을 제안하였는데, 이는 임의(randomized) 알고리즘이며 종료시점(convergence)을 식별할 방법이 없다는 단점을 가진다. 본 논문에서 우리는 이러한 단점을 없앤 더욱 효율적인 결정 (deterministic) 알고리즘을 제안한다. 제안 알고리즘은, 총 링크 수를 m이라 할 때, O(mlog n) 연결 통신 복잡도와 O(n²log n) 포인터 통신복잡도를 가지고 O(log n) 시간복잡도에 자원발견 문제를 해결한다. In this paper, we propose a deterministic algorithm to solve the resource discovery problem, that is, some subset of machines to learn the existence of each other in a large distributed network. Harchol et al. proposed a randomized algorithm solving this problem within O(log²n) rounds with high probability, which requires O(nlog²n) connection communication complexity and O(n²log²n) pointer communication complexity, where n is the number of machines in the network. His solution is based on randomization method and it is difficult to determine convergence time. We propose an efficient algorithm which improve performance and the non-deterministic characteristics. Our algorithm requires O(log n) rounds which shows O(mlog n) connection communication complexity and O(n²log n) pointer communication complexity, where m is the number of links in the network.

이중연결요소를 구하는 최적 임의 병렬 알고리즘 (pp.957-964)

박혜경(Hae Kyeong Park),유관우(Kwan Woo Ryu) 한국정보과학회 1996 정보과학회논문지 : 시스템 및 이론 Vol.23 No.9

정점의 수(ㅣVㅣ)가 n이고 간선의 수(ㅣEㅣ)가 m인 연결된 무방향 그래프 G=(V,E)가 주어질 때, E에 속한 임의의 두 간선 e와 g가 같은 간선이거나 같은 단순 사이클에 속하면, e와 g는 같은 이중연결요소에 속하게 되는데, 이때 E를 같은 이중연결요소에 속하는 집합들로 나누는 것을 이중연결요소 문제라 한다. 본 논문에서는 이러한 이중연결요소 문제를 해결하는 최적 임의 병렬 알고리즘을 소개하는데, 이는 먼저 G의 신장 트리를 나타내는 간선리스트가 주어질 때, 이 신장 트리의 오일러 행로를 쉽게 구할 수 있는 적절한 인접리스트를 구한 다음, 이를 이용하여 이중연결요소 문제를 해결하는, Priority CRCW PRAM 상에서 O(logn)시간과 O(n+m)연산으로 수행될 확률이 높은 알고리즘이다. Given a connected, undirected graph G=(V,E) of n vertices and m edges, two edges e and g in E are in the same biconnected component if e=g or e and g are on a common simple cycle. In this paper, we present an optimal randomized parallel algorithm for computing biconnected components of G, i.e., for partitioning the set E of edges into its subsets such that each such subset consists of a biconnected component of G, This algorithm first constructs an appropriate adjacency list for finding an Euler tour of a spanning tree of G, given an edge list representing that spanning tree, and then computes the biconnected components by utilizing the Euler tour, in O(logn) time using O(n+m) operations with high probability on the Priority CRCW PRAM.

우편 모델 상에서 합병 문제를 해결하는 효율적인 병렬 알고리즘

이동규(Dong Kyoo Lee),박혜경(Hae Kyeong Park),유관우(Kwan Woo Ryu) 한국정보과학회 1997 한국정보과학회 학술발표논문집 Vol.24 No.1A

합병 문제는 정렬된 두 개의 리스트 A=(α_0, α₁, α₂,...,α_(l-1)와 B=(b_0, b₁, b₂,...,b_(m-1)가 주어질 때, 이 두 리스트를 합병하여 하나의 정렬된 리스트 C=(c_0, c₁, c₂,...,c_(n-1) (n=l+m)로 만드는 문제이다. 이 문제는 여러 가지 문제를 해결하는데 필요한 중요한 문제이므로 지금까지 이를 해결하는 효율적인 알고리즘들이 많이 제안되었다. 하지만 이러한 알고리즘들은 프로세서들간의 통신 지연 인자 λ를 고려하지 않았으므로, 본 논문에서 사용하는 모델인 우편 모델(postal model)에서 효율적으로 수행될 수 없다. 따라서 본 논문에서는 2λ log n/log(λ+1)+λ-1 시간에 수행되는 새로운 알고리즘을 제안하는데, 이는 지금까지 밝혀지지 않은 바이토닉 순서(bitonic sequence)의 새로운 성질을 이용한 알고리즘이다. 또한 본 논문에서는 우편 모델에서 합병 문제의 하한이 f_λ(n), 즉 Θ(λlog n/log(λ+1))임을 증명하고, 따라서 위의 알고리즘이 최적에 가까운 알고리즘임을 보여준다.