Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
2007-04-03
2007-04-03
Vaughn, William (Department: 2144)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C709S245000
Reexamination Certificate
active
10389623
ABSTRACT:
A system and method for enabling highly scalable multi-node event distribution networks through the use of summary-based routing, particularly event distribution networks using a content-based publish/subscribe model to distribute information. By allowing event routers to use imprecise summaries of the subscriptions hosted by matcher nodes, an event router can eliminate itself as a bottleneck thus improving overall event distribution network throughput even though the use of imprecise summaries results in some false positive event traffic. False positive event traffic is reduced by using a filter set partitioning that provides for good subscription set locality at each matcher node, while at the same time avoiding overloading any one matcher node. Good subscription set locality is maintained by routing new subscriptions to a matcher node with a subscription summary that best covers the new subscription. Where event space partitioning is desirable, an over-partitioning scheme is described that enables load balancing without repartitioning.
REFERENCES:
patent: 6182143 (2001-01-01), Hastings et al.
patent: 6202093 (2001-03-01), Bolam et al.
patent: 6298455 (2001-10-01), Knapman et al.
patent: 6334151 (2001-12-01), Bolam et al.
patent: 6336119 (2002-01-01), Banavar et al.
patent: 6728715 (2004-04-01), Astley et al.
patent: 6760340 (2004-07-01), Banavar et al.
patent: 6910033 (2005-06-01), Rosenblum
patent: 6961728 (2005-11-01), Wynblatt et al.
patent: 7050432 (2006-05-01), Banavar et al.
patent: 2003/0135556 (2003-07-01), Holdsworth
patent: 2003/0188198 (2003-10-01), Holdsworth et al.
patent: 2004/0003064 (2004-01-01), Astley et al.
patent: 1043671 (2000-10-01), None
Aguilera, Marcos K. et al., “Matching Events in a Content-based Subscription System,”PODC '99, Atlanta, GA, pp. 53-61 (1999).
Banavar, Guruduth et al., “an Efficient Multicast Protocol for Content-Based Publish-Subscribe Systems,”ICDCS 1999, pp. 262-272 (1999).
Bayer, Rudolf & E. McCreight, “Organization and Maintenance of Large Ordered Indexes,”Acta Informatica, vol. 1, Fasc. 3, pp. 173-189 (1972).
Beckmann, Norbert, et al., “The R★-tree: An Efficient and Robust Access Method for Points and Rectangles,”SIGMOD 1990, pp. 322-331 (1990).
Bloom, Burton H., “Space/Time Trade-offs in Hash Coding with Allowable Errors,”Communications of the ACM, vol. 13, No. 7, pp. 422-426 (Jul. 1970).
Carazaniga, Antonio et al., “Design and Evaluation of a Wide-Area Event Notification Service,”ACM Transactions on Computer Systems, vol. 19, No. 3, pp. 332-383 (Aug. 2001).
Carazaniga, Antonio et al., “Fast Forwarding for Content-Based Networking,”Technical Report CU-CS-922-01, Department of Computer Science, University of Colorado, pp. 1-12 (Nov. 2001).
Carazaniga, Antonio and Alexander L. Wolf, “Fast Forwarding for Content-Based Networking,”Technical Report CU-CS-922-01, Department of Computer Science, University of Colorado, pp. 1-15 (Sep. 2002).
Fabret, Francoise et al., “Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems,”SIGMOD 2001, 22 pgs. (May 2001).
Fan, Li et al., “Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol,”IEEE/ACM Transactions on Networking, vol. 8, No. 3, pp. 281-293 (Jun. 2000).
Ferreira, C. E. et al., “The Node Capacitated Graph Partitioning Problem: A Computational Study,”Mathematical Programming, No. 81, pp. 229-256 (1998).
Garcia, Yvan J. et al., “A Greedy Algorithm for Bulk Loading R-trees,”ACM-GIS 1998, pp. 163-185 (1998).
Gough, John and Glenn Smith, “Efficient Recognition of Events in a Distributed System,”Proceedings of ACSC-18, Adelaide, Australia, 7 pgs. (1995).
Gruber, R. E. et al., “The Architecture of the READY Event Notification Service,”Proceedings of the 19th IEEE International Conference on Distributed Computing Systems Middleware Workshop, 6 pgs (1999).
Guttman, Antonin, “R-Trees: A Dynamic Index Structure for Spatial Searching,”SIGMOD 1984, pp. 47-57 (1984).
Intanagonwiwat, Chalermek et al., “Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks,”MOBICOM 2000, pp. 56-67 (2000).
Liu, Zhen, et al., “Clustering Algorithms for Content-Based Publication-Subscription systems,”ICDCS 2002, pp. 133-142 (2002).
Marais, Hannes and Krishna Bharat, “Supporting Cooperative and Personal Surfing with a Desktop Assistant,”Proceedings of ACM UIST'97, pp. 129-138 (Oct. 1997).
Opyrchal, Lukasz, et al., “Exploiting IP Multicast in Content-Based Publish-Subscribe Systems,” Proceedings of Middleware 2000, 23 pgs. (2000).
Rowstron, Antony et al., “SCRIBE: The Design of a Large-Scale Event Notification Infrastructure,”NGC2001, London, 13 pgs. (Nov. 2001).
Segall, Bill and David Arnold, “Elvin has left the building: A publish/subscribe notification service with quenching,”Proceedings AUUG97 Australian Unix Users Group Annual Conference, pp. 243-255 (1997).
Snoeren, Alex C. et al., “Mesh-Based Content Routing using XML,”SOSP 2001, pp. 160-173 (2001).
Wang, Yi-Min et al., “The SIMBA User Alert Service Architecture for Dependable Alert Delivery,”Proceedings of IEEE International Conference on Dependable Systems and Networks, pp. 463-474 (Jul. 2001).
Wong, Tina et al., “An Evaluation of Preference Clustering in Large-Scale Multicast Applications,”INFOCOM 2000, pp. 451-460 (2000).
Yan, Tak W. and Hector Garcia-Molina, “The SIFT Information Dissemination System,”TODS, vol. 24, No. 4, pp. 529-565 (1999).
Yu, Haobo et al., “A Hierarchical Proxy Architecture for Internet-scale Event Services,”WETICE 1999, pp. 78-83 (1999).
Hendrickson et al., “A Multilevel Algorithm for Partitioning Graphs”,Proceedings of the 1995 ACM/IEEE conference on Supercomputing, San Diego, CA, pp. 626-657 (1995).
Achlioptas Demetrios
Das Gautam
Larson Per-Ake
Qiu Lili
Verbowski Chad E.
Gerezgiher Yemane M.
Microsoft Corporation
Vaughn William
Wolf Greenfield & Sacks P.C.
LandOfFree
Summary-based routing for content-based event distribution... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Summary-based routing for content-based event distribution..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Summary-based routing for content-based event distribution... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3783706