A new marginal revenue based scheduling algorithm for publish/subscribe systems

Publish/subscribe paradigm is seen as a good candidate in constructing distributed applications due to its unique and powerful features such as anonymity, asynchrony and many-to-many communication. As applications based on publish/subscribe increases greatly, it is required to support different quality of service properties. However, most current solutions adopt simple matching strategies without distinguishing crucial tasks from non-crucial ones, which lead to poor performance of key tasks when publish/subscribe systems are in heavy load. In this paper, we introduce the notion of subscription priority, and propose a new marginal revenue based scheduling (MRBS) algorithm which considers subscription priority. MRBS uses priorities of attribute constraints to sort the matching order for an event, and in such a way MRBS can distinguish important subscriptions from less important ones. MRBS is proven to be able to produce the maximum event matching revenue. A priority-sensitive algorithm for subscription information maintenance is also given. Finally, we conduct detailed experimental evaluation to verify the effectiveness of our approach.