Publish/subscribe systems have demonstrated the ability to scale to large numbers of users and high data rates when providing content-based data dissemination services on the Internet. However, their services are limited by the data semantics and query expressiveness that they support. On the other hand, the recent work on selective dissemination of XML data has made significant progress in moving from XML filtering to the richer functionality of transformation for result customization, but in general has ignored the challenges of deploying such XML-based services on an Internet-scale. In this paper, we address these challenges in the context of incorporating the rich functionality of XML data dissemination in a highly scalable system. We present the architectural design of ONYX, a system based on an overlay network. We identify the salient technical challenges in supporting XML filtering and transformation in this environment and propose techniques for solving them. A large number of emerging applications, such as mobile services, stock tickers, sports tickers, personalized newspaper generation, network monitoring, traffic monitoring, and electronic auctions, has fuelled an increasing interest in ContentBased Data Dissemination (CBDD). CBDD is a service that delivers information to users (equivalently, applications or organizations) based on the correspondence between the content of the information and the user data interests. Figure  1 shows the context in which a data dissemination system providing this service operates. Users subscribe to the service by providing profiles expressing their data interests. Data sources publish their data by pushing messages to the system. The system delivers to each user the messages that match her data interests; these messages are presented in the format required by the user. Over the past few years, XML has rapidly gained popularity as the standard for data exchange in enterprise intranets and on the Internet. The ability to augment data with semantic and structural information using XML-based encoding raises the potential for more accurate and useful delivery of data. In the context of XML-based data dissemination, user profiles can involve constraints over both the structure and value of XML fragments, resulting in potentially more precise filtering of XML messages. In many emerging applications, the relevant XML messages also need to be transformed for data and application integration, personalization, and adaptation to wireless devices. While . Integrating XML processing into such distributed environments appears to be a natural approach to supporting large-scale XML dissemination. Distributed pub/sub systems partition the profile population to multiple nodes and direct the message flow to the nodes hosting profiles based on the content of messages (referred to as content-driven routing). Integrating XML into contentdriven routing, however, brings the following key challenges. As XML mixes structural and value-based information, content-driven routing needs to support constraints over both. The inherent repetition and recursion of element names in XML data also defeats well-known routing , a multi-query processor that we built previously, represents a set of profiles using an operator network on top of a Non-Deterministic Finite Automaton (NFA) to share processing among those profiles. Using YFilter for distributed XML dissemination raises the issues of distributing the NFA-based operator network, and efficient scheduling of the operators for both profile processing and contentdriven routing. In this paper, we present the initial design of ONYX (Operator Network using YFilter for XML dissemination), a largescale dissemination system that delivers XML messages based on user specifications for filtering and transformation. The contributions of our work include the following. We leverage the YFilter processor for content-driven routing. In particular, we use the NFA-based operator network to represent routing tables, and provide an initial solution to constructing the routing tables from the distributed profile population. We address the issue of how to perform incremental message transformation in the course of routing. In order to boost the effectiveness of routing, we provide an algorithm that partitions the profile population based on exclusiveness of data interests. We develop holistic message processing for sharing the work among various processing tasks at a node (i.e., content-driven routing, incremental transformation and user profile processing). Dependency-aware priority scheduling is used to support such sharing while providing a fast path for routing. We investigate various formats for efficient XML transmission. Last but not least, we provide an architectural design of the system and mechanisms for building such a system. The paper proceeds as follows. Section 2 details the requirements and motivation. Section 3 describes our system model. Core techniques addressing the various challenges are presented in Section 4, followed by a detailed broker architecture design in Section 5. Section 6 includes extended related work. Section 7 concludes the paper. In this section, we present the requirements for large-scale XML dissemination, and provide a brief survey of existing solutions, which motivates our work presented in this paper. A starting point for our requirements is the use of XML as the data model and a subset of XQuery [7] as the profile model. User profiles can contain constraints over both structure (using path expressions) and value (using value-based predicates) of XML fragments. For example, if a user is interested in stock information distributed in San Francisco and under the subject "Stock", she can express her interest using the query below (based on the NITF DTD [23]). It specifies that the root element nitf must (1) have a child element head that in turn contains a child element pubdata whose attribute edition.area has the value "SF", and (2) have a descendant element tobject.subject whose attribute tobject.subject.type has the value "Stock". User profiles can also contain specifications for result customization. For example, a user can use the query below to specify that for each NITF article that matches the for and where clauses (which are equivalent to the query above), transform it to a new article with the root element stock_news containing elements selected from the original article using path expressions "body/body.head/hedline", and "body/body. content". for $n in $msg/nitf where $n/head/pubdata/@edition.area = "SF" and $n//tobject.subject/@tobject.subject.type = "Stock" return <stock_news> {$n/body/body.head/hedline} {$n/body/body.content} </stock_news> As the profile model is based on the XQuery language, in the sequel, we use the terms profile and query interchangeably. The second dimension of requirements is scalability. More specifically, the service must scale along the following dimensions. Data volume. The data volume is determined by the number of messages per second arriving at the system and the message size. Depending on the application, the number of messages per second ranges from several to thousands. For example, NASDAQ real-time data feeds include 3,000 to 6,000 messages per second in the pre-market hours [43] ; Network and application monitoring systems such as NetLogger can also receive up to a thousand messages per second [44] . The message size can vary from 1 KB (e.g., XML encoded stock quote updates) to 20 KB (e.g., XML news articles). Query population. The query population in a dissemination system can also span a wide range, reaching millions of queries for applications such as personalized newspaper generation and mobile operators providing stock quote updates. Frequency of query updates. A third scalability issue is the frequency with which users update their data interests. While in some applications queries change on a daily basis, in some others they can change much more frequently. Result Volume. When result customization is supported, the volume of results to be delivered can be tremendous. This is because for each message, point-to-point delivery is needed for every query matched by the message. Take, for example, a stock quote update service. Suppose that the peak message rate from a data source is 5000 per second, each message is 1 KB, the user population is 10 million, and the average query selectivity is as low as 0.001%. A back-of-theenvelope calculation gives an estimation of the result volume as 4 Gb per second. Disseminating this volume of data from a central server can be prohibitively expensive. Having outlined the problem of large-scale XML-based data dissemination, we next present the position of our work within the large body of related work. Publish , a multi-query processor that we built previously, also supports result customization using a subset of XQuery. Although these XML filtering and transformation systems provide higher levels of expressiveness, their centralized style of processing limits their scalability. Revisiting Figure 2 , today's XML filtering and transformation systems can be best described by the lower right corner of the matrix combining lower scalability and higher expressiveness. Our work on content-based data dissemination adopts the paradigm of distributed processing to exploit aggregated bandwidth and processing power. As indicated in Figure 2 , our system ONYX incorporates the high level of expressiveness of XML filtering and transformation into a distributed data dissemination service. In this section, we present the operational features of ONYX. ONYX provides content-based many-to-many data dissemination from publishers to end users. It consists of an overlay network of nodes. Most of the nodes serve as information brokers (or brokers, for short) that handle messages and user queries, while a few of them collaborate to provide a registration service. The overview is illustrated in Figure 3 . The service interface provided by ONYX consists of several methods (some of which are similar to those in [3]): Register a data source: A data source registers with ONYX by contacting the registration service and providing information about its location, the schema used, the expected message rate and message size, etc. (as illustrated by message 1 in Figure 3 ). The registration service assigns an ID to the data source, and chooses a broker as the root broker for the data source. The choice of the root broker is based on its topological distance to the data source, the bandwidth available, and the data volume expected from that source. After the service forwards the information about the new data source to the root broker (message 2), it returns the assigned ID and the address of the root broker to the data source (message 3). Publish data: After registration, a data source publishes its data by attaching its ID to each message and pushing the message to its root broker (message 4). Register a data interest: To subscribe, the user contacts the registration service, and provides his profile and network address (message 5). The registration service assigns an ID to this profile, and chooses a broker as the host broker for this profile based on the user's location and/or the content of the profile. At the end of the registration, the service forwards the profile and related information to the host broker (message 6), and returns the profile ID and host broker address to the user (message 7). Thereafter, the host broker will deal with all the user requests concerning that profile. Update a data interest: Subsequent changes to a profile (including updates and deletion) are sent directly to the host broker (message 8). Note that users do not need a method to retrieve the messages matching their interests, because those messages are pushed to them from the system (e.g., message 9). Additional methods are provided for data sources to update the schema and other information sent previously. Fault-tolerance can be achieved by having backup nodes for the registration service and the brokers or using other techniques. That discussion is beyond the scope of this paper. ONYX is an application-level overlay network. It consists of two layers of functionality. The lower layer, called the control plane, deals with application-level broadcast trees and gives each broker a broadcast tree rooted at that broker that reaches all other brokers in the network. Figure 4 shows such a tree in a network consisting of six brokers. Algorithms for constructing broadcast trees have been provided elsewhere (e.g., [14] ). In this section, we focus on the higher layer of functionality in ONYX -content-based processing, which is the primary concern of this paper. We decompose the operations in this layer into two planes of processing -the data plane and the query plane. The data plane captures the flow of messages in the system while the query plane captures the flow of queries and query-related updates in the system. As we will see, the duality of data and query is a pervasive feature of ONYX. We now discuss the three tasks performed in this layer -content-driven routing, incremental transformation, and user query processing. Content-driven routing is necessary to avoid the flooding of messages to all brokers in the network. It builds on top of the broadcast tree described above. The routing is contentdriven because instead of forwarding a message to all the children in the broadcast tree, a broker sends it to only the subset that is "interested" in the message. This routing scheme, which matches a message's content with routing table entries (or routing queries) representing the interests of child brokers, is in sharp contrast to the address-based IP routing scheme. Figure 4 shows an example of routing a message based on its content. The routing tables for Broker 1 and 4 are shown conceptually. The table at Broker 1 specifies a routing query "/nitf/head/pubdata[@edition.area= "NY"]" for Broker 2, and a similar one "/nitf/head/pubdata[@edition.area= "SF"]" for Broker 4. The matching of a new message arriving at Broker 1 with either routing query results in routing the message to the corresponding child. The building of such routing tables by summarizing the queries of downstream brokers is a subtask in the query plane. The matching of messages against routing queries occurs in the data plane. Incremental transformation is the second task in the content-based processing layer. Interesting cases of transforming messages during routing include (1) early projection, i.e., removal of data, and (2) early restructuring. An example of early projection is as follows. A data source publishes messages containing multiple news articles. If all the user queries downstream of a link are interested only in a subset of the articles (e.g., those distributed in the area "SF"), messages can be projected onto the articles of interest before they are forwarded along that link using the following query: <batched-nitf> { for $n in $msg/batched-nitf/nitf where $n/head/pubdata/@edition.area ="SF" return $n } </batched-nitf> An example of restructuring is message transcoding based on the profiles of wireless users, say, when all users downstream of a link require images and comments to be removed and tables to be converted to lists. Incremental transformation helps reduce message sizes and avoids repeated work at multiple brokers. We enable incremental transformation by attaching transformation queries to the output links of brokers on the path of routing. User queries downstream of a link are aggregated and the commonality in their transformation requirements is extracted to form the transformation query. These subtasks happen in the query plane. The corresponding subtask in the data plane consists of transforming messages using these queries, before the messages are sent to the output links. User query processing is the task of matching and transforming messages against individual user queries at their host brokers. For the user queries resident at a particular broker, this is the last step of message processing (although the arriving messages may be routed and transformed for other downstream user queries). The subtask in the query plane consists of issues such as indexing of user queries for which the broker is a host broker, and the subtask in the data plane consists of matching messages against these indexes. Table 1 summarizes the content-based processing tasks in ONYX and their subtasks over the query and data planes.
Authors in REF presented the design of a large scale distributed XML dissemination system.
Towards an Internet-Scale XML Dissemination Service
VLDB
Computer Science