Research On Key Technologies In Internet-scale Publish/Subscribe Systems

The wide spread of Internet leads to a new type of distributed computing environment in recent years, namely the Internet-scale distributed computing environment. In comparison with the traditional distributed computing environments, the new environment is characterized by the large scale, decentralization and dynamic in addition to heterogeneity. These new features result in a requirement for loosely-coupled interaction among the participants in the environment. The publish/subscribe (pub/sub) paradigm can make the information producers and consumers fully decoupled in time, space and flow, so it is a desirable solution for the Internet-scale distributed computing.However, existing pub/sub technologies suffer a number of problems on the expressiveness, efficiency and reliability, which make them not directly applicable in the Internet-scale computing environment, In this thesis, we researched the key technologies in the Internet-scale pub/sub system and proposed some novel solutions for it, so that the pub/sub system can become a general, efficient and reliable infrastructure for the Internet computing environment.We first propose a novel data model for the pub/sub system to support heterogeneous events in the Internet environment. The Semantic Web technologies are introduced into the pub/sub system to solve the heterogeneity of events both in semantics and in structure,In the proposed data model, events are represented as RDF graphs and subscriptions are represented as RDF graph patterns. When an event is published, the system first converts it into an RDF graph before further processing. For events with the Map format, we propose a converting solution based on the event schema. We extend the original event schema to append the necessary information for conversion. For events with the XML format, we proposed a converting solution based on XML Schema and XSLT. We also discuss how the subscriptions in the existing pub/sub systems can be represented with the RDF graph patterns, and the corresponding converting algorithms. As far as we know, this is the first pub/sub solution that can support heterogeneous events both in semantics and in structure.An efficient matching algorithm is proposed based on the new data model, In an Internet-scale computing environment, there may be a large number of participantsthat exchange information with each other frequently, so the pub/sub system should be efficient enough to process the heavy workload. In comparison with the existing graph matching algorithms, the proposed algorithm is much more efficient because it makes use of the characteristics of the RDF graph and the restrictions we exert on the events and subscriptions. The basic idea of the proposed algorithm is to decompose the event graph and the subscription graph into a set of arcs, which are the basic units for matching. Same arcs from different subscriptions just need to be matched once. An index structure is built for the arcs of the subscription graphs, which is based on the concept model of the system. The AND-OR tree is used to record all matching solutions for the arcs in a subscription and then to calculate the final matching result, so that the time-consuming backtracking on the event graph and subscription graphs can be avoided.In an Internet-scale pub/sub system, there may be a lot of event brokers which are owned by different organizations and distributed all over the world, so the routing protocol for the pub/sub system should be fault-tolerant and can support the self-organization of the system. We combine the peer-to-peer (P2P) technology with the pub/sub technology and propose a novel routing protocol. Under certain system conditions, the proposed protocol can guarantee the exactly-once delivery of events to all interested subscribers with low overhead on network traffic. If the conditions are not satisfied, the proposed protocol can also achieve a much lower event-loss rate than existing protocols. The basic idea of the protocol is to better match the routing of the pub/sub system with the routing of the P2...