Department of Computer Science,
Office: LSRC D211. Email: syu at cs.duke.edu
We study the problem of assigning subscribers to brokers in a wide-area content-based publish/subscribe system, considering not only similarities in subscription interests but also their network locations and event distribution. The optimization problem that balances multiple performance criteria including bandwidth, delay, and load balance is NP-complete, so systems have turned to heuristics and/or simpler algorithms that ignore some performance criteria. Evaluating these approaches has been challenging because optimal solutions remain elusive for realistic problem sizes. To enable proper evaluation, we develop a Monte Carlo approximation algorithm with good theoretical properties and robustness to workload variations.