광 베니언 - 형 교환 망에서의 누화를 회피하기 위한 교환소자를 달리하는 멀티캐스트 스케줄링 (제1부) : 누화 관계의 그래프 이론적 분석

차영환(Yeonghwan Tscha) 한국정보과학회 2001 정보과학회논문지 : 정보통신 Vol.28 No.3

본 논문에서는 방향성 커플러를 이용하여 구성한 광 베니언-형 교환 망에 있어 교환소자를 달리하는 멀티캐스팅의 스케줄링을 고려한다. 임의의 주어진 시각에 최대한 하나의 접속만이 각각의 교환소자를 점유하기 때문에 블럭킹은 물론 누화가 발생하지 않도록 보장된다. 이러한 멀티캐스팅에서는 대개 수차례에 걸친 라우팅이 수반되므로 라우팅 횟수(즉, 스케줄링 길이)를 최소한으로 하는 것이 바람직하다. 먼저 일-대-다 접속 능력을 제공하는 광 베니언-형 망에서 접속들이 동일한 교환소자를 경유(즉, 누화를 유발)하기 위한 필요충분 조건을 제시한다. 멀티캐스트 접속을 일정한 부분접속들로 분할하는 규칙을 정의하고, 부분접속들간의 누화 관계를 그래프로 표현한다. 최악의 경우의 누화를 분석하기 위해 그래프차수의 상한을 제시한다. 후속 논문(제2부)[14]에서는 스케줄링 알고리즘과 스케줄링 길이의 상한을 고찰하고, 관련 연구결과와의 상세한 비교를 다룬다. In this paper, we consider the scheduling of SE(switching element)-disjoint multicasting in photonic Banyan-type switching networks constructed with directional couplers. This ensures that at most, one connection holds each SE in a given time thus, neither crosstalk nor blocking will arise in the network. Such multicasting usually takes several routing rounds hence, it is desirable to keep the number of rounds(i.e., scheduling length) to a minimum. We first present the necessary and sufficient condition for connections to pass through a common SE(i.e., make crosstalk) in the photonic Banyan-type networks capable of supporting one-to-many connections. With definition of uniquely splitting a multicast connection into distinct subconnections, the crosstalk relationship of a set of connections is represented by a graph model. In order to analyze the worst case crosstalk we characterize the upper bound on the degree of the graph. The successor paper(Part II)[14] is devoted to the scheduling algorithm and the upper bound on the scheduling length. Comparison with related results is made in detail.

센서 네트워크에서 낮은 전달 지연으로 근원지 위치 기밀을 강화하는 라우팅

차영환(Yeonghwan Tscha) 한국통신학회 2008 韓國通信學會論文誌 Vol.33 No.8B

센서 네트워크에 있어서 정보 전송 노드인 근원지의 위치를 악의적 추적자로부터 보호하기 위해 길이가 긴 경로를 통해 단일 메시지를 전송하는 라우팅에서는 전달 지연이 길어지는 단점이 있다. 본 논문에서는 전송 메시지가 사전에 주어진 경우, 근원지 위치를 보호하면서 최소 비용의 단일 경로를 이용하여 이들을 목적지로 전달하는 문제는 NP-complete 임을 보인다. 이러한 양 극단의 절충 방안이라 할 수 있는 경로 당 ω개의 메시지들을 전송하도록 하여 근원지의 위치 보호 능력을 높이면서도 전달 지연을 저감시키는 라우팅 프로토콜 GSLP-ω (GPSR-based Source Location Privacy with crew size ω)를 제안한다. 평가 기준으로는 목적지와의 최단 경로의 홉 수를 기준으로 정규 안전 기간(NSP: Normalized Safety Period)과 정규 전달 지연(NDL: Normalized Delivery Latency)을 고려한다. 평균 차수(degree)가 8인 노드 50,000개로 구성되는 네트워크 토폴로지 100개를 생성하여 측정한 결과 제안된 GSLP-ω는 GSLP-ω의 초기 버전인 GSLP와 기존의 대표적인 근원지 위치 보호 라우팅 프로토콜인 PR-SP(Phantom Routing - Single Path)보다 더 높은 안전 기간을 보였다. 전달 지연에서는 GSLP-ω가 PR-SP보다 높으나 GSLP 보다는 낮은 것으로 나타났다. Most of routing schemes that protect the source's location from a malicious attacker usually make use of a path of a long length per message for the sake of lengthening the safety period. The biggest problem to such approaches is taking a very long latency in transferring messages to the destination. In this paper we show the problem to find the least-cost single path that is enough to keep the source-location always secure from the attacker, provided that it is used for the delivery of a set of messages given in priori, is NP-complete. Consequently we propose a routing protocol GSLP-w(GPSR-based Source-Location Privacy with crew size ω) that is a trade-off between two extreme approaches. The advantage of GSLP-ω lies in its enhanced safety period for the source and its lowered delivery latency in messaging. We consider NSP(Normalized Sefety Period) and NDL(Normalized Delivery Latency), measured in terms of the least number of hops to the destination, to achieve tangible interpretation of the results. We ran a simulation to confirm our claim by generating 100 topologies of 50,000 nodes with the average number of neighbors being 8. The results show that GSLP-ω provides more enhanced NSP compared to other protocols GSLP, an earlier version of GSLP-ω, and PR-SP(Phantom Routing - Single Path), the most notable existing protocol for the source-location privacy, and less NDL than that of GSLP but more than that of PR-SP.

방향성 안테나에 기반을 둔 이동 애드 혹 네트워크에서의 대체 경로 설정

차영환(Yeonghwan Tscha) 한국멀티미디어학회 2007 멀티미디어학회논문지 Vol.10 No.9

방향성 안테나에 기반을 둔 애드 혹 네트워크를 위한 신뢰성 있는 브로드캐스팅 기법

차영환(Yeonghwan Tscha) 한국정보기술학회 2008 한국정보기술학회논문지 Vol.6 No.6

In this paper we propose a low-cost reliable broadcasting scheme called BSART (Broadcasting with Selected Acknowledgement and Repeated Transmission), designed especially for mobile ad hoc networks which are capable of directional communications using switched beam antenna elements. To alleviate the broadcast storm problem, a phenomena generates heavily redundant messages in broadcasting, a method to control the number of message forwarding nodes performing broadcasting(including the number of antenna elements deployed by these nodes) is taken into account. Recognizing ACK-based reliable transmission usually causes the ACK implosion problem, the repeated transmission without ACK (R-scheme) is applied to the switch element where the number of recipient neighbor nodes is above some particular threshold, otherwise the native ACK-based Acknowledgement (A-scheme) is considered. It is given through simulation that the proposed BSART is capable of controlling the number of message forwarding nodes, as well as the number ACK message incoming into to the forward nodes, and that the message delivery ratio is beyond 90% at nodal speed of 20m/s.

Multi - Log₂N 다중접속 망의 넌블럭킹 조건에 관한 새로운 결과

차영환(Yeonghwan Tscha),이균하(Kyoon Ha Lee) 한국정보과학회 1992 한국정보과학회 학술발표논문집 Vol.19 No.1

본 논문에서는 그 동안 미해결 문제(open problem)들[1-4]로 남아있던 Multi-Log₂N 다중접속 망의 Rearrangeable 넌블럭킹 조건과 Strictly 넌블럭킹 조건을 제시 하였다. 기존의 예측[1,2]과 달리 Multi-Log₂N 다중접속 망의 넌블럭킹 조건들은 Multi-Log₂N 일대일접속 망의 넌블럭킹 조건들과 일치한다는 흥미로운 결과를 얻었다. 본 논문에서 규명된 넌블럭킹 조건들은 물론 SIS(Subconnection-Intersection Set) 정규화된 SIS(Normalized SIS), SIG(Subconnection-Intersection Graph) 및 UMSR(Unified Multiconnection-Segmenting Rule)등은 다중접속 광대역 스위치의 개발은 물론 하나 또는 2개 이상의 스위치 망을 복수개 이용하는 다양한 구조의 다중접속 스위치 망에 있어 유용성있는 기본 자료로 활용될 수 있을 것으로 판단된다.

근원지 위치 보호 라우팅 기법 GSLP의 확장에 관한 연구

차영환(Yeonghwan Tscha) 한국정보기술학회 2012 한국정보기술학회논문지 Vol.10 No.1

In wireless sensor networks, it may be easy to repeatedly eavesdrop the packet transmission signal and finally to identify the packet-originating node(i.e., source). GSLP(GPSR-based Source-Location Privacy) was proposed as a routing scheme that countermeasures against such tracing and also that relays packets appropriately so that other assets locations are kept private. Through simulations, in this paper, the source-location privacy level(safety period) of GSLP was evaluated by comparing with Phantom routing for the case that a source node changes and the other case where several sources transmit their packets simultaneously. In the former, GSLP kept at a certain privacy level as the number of sources needed location-privacy increases, and in the latter, the privacy level of GSLP roughly doubled that of Phantom. In case that multiple adversaries trace their own sources concurrently, GSLP showed low delivery latency and high privacy level provided that each source sends its packets to a randomly selected base station rather than to a near or far-off one.

광 베니언 - 유형 교환 망에서의 누화를 회피하기 위한 교환소자를 달리하는 멀티캐스트 스케줄링(제2부) : 스케줄링 길이 및 넌블럭킹 특성

차영환(Yeonghwan Tscha) 한국정보과학회 2001 정보과학회논문지 : 정보통신 Vol.28 No.4

선행 논문(제1부)[13]에서는 광 베니언-형 교환 망에 있어 누화를 야기하는 멀티캐스트 접속들간의 관계를 그래프로 표현하고, 해당 그래프의 차수의 상한을 제시하였다. 본 논문(제2부)에서는 교환소자를 달리하는 멀티캐스팅의 스케줄링에서의 라우팅 횟수 즉, 스케줄링 길이에 대해 다룬다. 최적의 스케줄링 길이를 구하는 문제는 NP-complete이므로 최적 길이의 상한의 두 배이내의 길이를 제공하는 근사 알고리즘을 제시한다. 아울러, 링크를 달리하는(즉, 넌블럭킹) 멀티캐스팅에 관한 스케줄링 길이를 고찰한다. 얻어진 스케줄링 길이 하에서 다양한 넌블럭킹 베니언-형 멀티캐스팅 망들을 규명한다. In our predecessor paper(Part I)[13], we introduced a graph that represents the crosstalk relationship among multicast connections in the photonic Banyan-type switching network, and found the upper bound on the degree of it. In this paper(Part II), we consider the number of routing rounds(i.e., scheduling length) required for SE(switching element)-disjoint multicasting in photonic Banyan-type switching networks. Unfortunately, the problem to find an optimal scheduling length is NP-complete thus, we propose an approximation algorithm that gives its scheduling length is always within double of the upper bound on the optimal length. We also study the scheduling length on the link-disjoint(i.e., nonblocking) multicasting. Various nonblocking Banyan-type multicasting networks are found under the scheduling lengths.

이동 애드 - 혹 네트워크를 위한 신뢰성 있는 동적 소스 라우팅 프로토콜

임화정(HwaJung Lim),차영환(YeongHwan Tscha) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.2Ⅲ

본 논문에서는 이동 애드-혹 네트워크(mobile ad-hoc networks)의 대표적인 경로구축 방법인 DSR(dynamic source routing)을 확장된 R-DSR(robust DSR)을 제안한다. 제안된 R-DSR에서는 기존의 단일 경로 상의 2-홉 간격의 모든 노드들이 대체 노드를 경유하여 복수 개의 라우팅 경로를 유지하도록 구성되기 때문에, 경로 상의 일부 노드들이 이동하더라도 경로가 유지될 확률이 높아 메시지 전달률이 향상된다. 수학적 분석을 통하여 관련 연구 중 가장 우수한 것으로 알려진 Das의 다중경로 프로토콜보다 더 높은 라우팅 경로 유지 확률을 나타냄을 보였다. 아울러, 대체경로의 위상적 특성에 의한 빠른 대체경로로의 복구도 가능하다는 결론을 얻었다.

통신용 실시간 운영체제의 설계 및 구현

천대녕(Daenyung Chun),차영환(Yeonghwan Tscha),강영만(Youngman Kang),전광일(Gwangill Jeon),양선희(Sunhee Yang),이영희(Younghee Lee) 한국정보과학회 1988 한국정보과학회 학술발표논문집 Vol.15 No.2

MORTOS(Message-Oriented Real-Time Operating System)는 통신 소프트웨어에 실시간 및 동시 처리 기능을 제공하는 목적으로 당 연구소에서 설계, 구현된 운영체제이다. 이는 event에 따라 스케쥴링되는 event-driven 방식으로, 정상 동작시에 시분할에 따른 context 스위칭과 프로세스의 상태 관리 그리고 인터럽트 처리에 따르는 부담을 최소화하여 최상의 성능을 갖도록 하였다. 그리고 강력한 오류 처리 기능을 통해 고신뢰도를 요구하는 시스템에 적합하도록 하였으며, CHILL과 같이 언어 확장개념을 통해 사용자로 하여금 쉽게 이용할 수 있도록 인터페이스를 간단히 하였다.

이동 통신망을 위한 도시지역에서의 위치 등록 발생율에 관한 연구

박정환(Junghwan Park),전민희(Minheui Jeon),차영환(Yeonghwan Tscha),이균하(Kyoon Ha Lee) 한국정보과학회 1993 한국정보과학회 학술발표논문집 Vol.20 No.1

이동 가입자(mobile station)에 대한 위치정보의 신속한 처리는 이동 통신망에 있어 필수적이다. 특히, 서울과 같은 대도시 지역에서의 이동 가입자의 빈번한 위치 이동은 트래픽의 폭주를 낳을 수 있기 때문에 위치정보의 신속한 처리를 위해 위치 등록기(location register)의 적절한 위치 선정이 중요하다. 본 논문에서는 도로를 중심으로한 정방형 형태의 도심지에 있어 이동 가입자의 트래픽 이동 형태를 반영한 위치 등록 발생률의 분석과 하나의 위치 등록기에 수용 가능한 위치 영역(location area)수의 산정과 이에 따른 위치 등록 발생률을 분석하였다. 분석 결과 본 연구에서 제안된 방법은 대도시 밀집지역에 있어 위치 등록기의 설치 위치 선정과 위치 등록 발생률의 예측에 매우 유용함을 알 수 있었다.