Publish/subscribe systems are frequently used for disseminating documents to various clients geographically distributed in the network. Typically, such systems consist of publishers who produce documents, subscribers who consume them, and a broker that delivers documents from publishers to subscribers.
If the publish/subscribe system maintains multiple brokers to achieve scalability, a document routing method between brokers is needed. To do this, in the first part of this dissertation, we propose an efficient subscription routing algorithm with subscriptions especially expressed in XPath patterns as in an XML-based publish/subscribe system [55]. We first discuss that publish/subscribe systems can utilize the homomorphism relationship among XPath patterns to route XPath patterns. Then, we develop a lattice data structure called the partially ordered set of XPath patterns (abbreviated as POX) and its corresponding algorithm for efficiently maintaining homomorphism relationships. Finally, we present performance evaluation results that validate our algorithm with respect to system performance and scalability.
In the second part of this dissertation, we mention the $\textsl{k}$ -NN query that the publish/subscribe system can frequently encounter and develop algorithms for exact $\textsl{k}$ -NN search using the R-tree that is the most popular structure to index multi-dimensional data items. Our method pre-computes and maintains l nearest neighbors for each subscription and exploits them to prune the search space. To minimize the cost of reading the l-NN subscriptions from the disk, we also propose a method that expects l’, the minimum value of l, according to the value $\textsl{k}$. We prove that our method always returns exact results and propose complete algorithms that process the $\textsl{k}$ -NN query and update the R-tree. The experimental results show that our method outperforms the existing one proposed in [49].
In Mobile Ad Hoc Networks (MANETs) where clients cannot be supported by any infrastructure such as a broker, the document routing problem of the publish/subscribe system become more complex. In the third part of this dissertation, we propose a scalable publish/subscribe system for large MANETs. Existing publish/subscribe services for MANETs can be categorized into Document Flooding (DF), Destination-Based Routing (DBR), and Content-Based Routing (CBR). Although those approaches may work well when the network size is small, all of them suffer from the performance degradation as the size of the network increases. In this dissertation, we compare these three approaches, and then propose a scalable publish/subscribe communication scheme in large MANETs by combining DF and CBR hierarchically. Our approach is to cluster all nodes in networks and to exploit CBR and DF for the intra- and inter-cluster communication, respectively. By using this approach, we can effectively utilize benefits of both approaches. Our performance evaluation results demonstrate that the proposed approach outperforms existing ones with respect to document delivery ratio and energy consumption.
출판/구독 시스템은 네트워크 상에 떨어져 있는 많은 클라이언트들에게 문서를 배포하는데 주로 사용된다. 출판자로부터 구독자로의 문서 전달을 담당하는 브로커는 네트워크 환경에 따라 사용 가능할 수도 있고 불가능할 수도 있다.
브로커의 사용이 가능한 경우, 출판/구독 시스템은 확장 가능성을 위해 다수의 브로커들로 구성될 수 있으며, 이때 브로커들 사이의 문서 전달 방식이 필요하다. 이를 위해, 본 논문의 첫 번째 부분에서 XML 기반 출판/구독 시스템에서 사용하는 subscription인 XPath패턴을 효율적으로 전달하는 방법을 제안한다. 우선 XPath 패턴들 사이의 준동형 관계가 이를 전달하는데 활용될 수 있음을 논의하고, XPath 패턴들의 부분 순서 집합인 래티스 데이터 구조를 제안하고 이를 효율적으로 유지하는 알고리즘을 제시한다. 그리고 시스템의 성능과 확장 가능성 측면에서 제안된 알고리즘의 효율성을 보여주는 실험 결과를 보인다.
본 논문의 두 번째 부분에서 우리는 $\textsl{k}$ -NN 질의가 출판/구독 시스템에서 빈번히 발생할 수 있음을 언급하고 R-tree를 이용한 정확한 $\textsl{k}$ -NN을 찾는 알고리즘을 개발한다. 제안하는 방법은 각 subscription에 대해서 l-NN subscription들을 미리 계산해 두었다가 질의를 처리할 때 검색 공간을 줄이는 데 사용한다. 디스크로부터 l-NN subscription을 읽어 들이는 비용을 최소화하기 위해 $\textsl{k}$ 값에 따라 l의 최소값인 l’을 예측하는 방법을 제안한다. 우선 제안하는 방법이 항상 정확한 값을 돌려준다는 것을 이론적으로 증명하고, $\textsl{k}$-NN 질의를 처리하고 R-tree를 유지하는 완전한 알고리즘을 보인다. 실험 결과는 제안하는 방법이 기존 방법에 비해 우수한 성능을 낸다는 사실을 보인다.
모바일 애드 혹 네트워크(MANET)과 같이 브로커의 사용이 불가능한 환경에서는 출판/구독 시스템에서의 문서 전달 방법이 보다 복잡해진다. 이에 본 논문의 세 번째 부분에서는 큰 MANET에서의 확장 가능한 출판/구독 시스템을 제안한다. 기존에 제안되었던 MANET에서의 출판/구독 시스템들은 문서 플러딩(DF: document flooding), 목적지 기반 라우팅(DBR: destination-based routing), 그리고 내용 기반 라우팅(CBR: content-based routing)의 세 가지로 구분된다. 이들 방법 모두는 네트워크 크기가 작을 때에는 잘 동작할 수 있지만, 네트워크 크기가 커짐에 따라 성능 저하가 발생하게 된다. 본 논문에서는 세 가지 방법들을 비교하고, DF 방식과 CBR 방식을 계층적으로 결합하여 큰 MANET에서의 확장 가능한 출판/구독 시스템을 제안한다. 본 논문에서 제안하는 방식은 네트워크 상의 모든 노드들을 클러스터링하여 클러스터 내부 통신은 CBR 방식을 사용하고, 클러스터간 통신은 DF 방식을 사용한다. 제안하는 방법을 통하여 두 가지 방식의 장점을 효과적으로 활용할 수 있다. 마지막에는 시스템 성능과 확장 가능성 측면에서 제안된 방식의 효율성을 보여주는 실험 결과를 보인다.
