Systems
Jonathan C. RowanhillPhilip E. VarnerJohn C. Knight
Department of Computer Science
University of Virginia
151 Engineer’s Way, Charlottesville, VA 22904-4740{rowanhill | varner | knight}@cs.virginia.eduAbstract
The management of modern distributed systems is com-plicated by scale and dynamics. Scalable, decoupled com-munication establishes flexible, loosely coupled componentrelationships, and these relationships help meet the presentdemands on management. However, traditional decoupledaddressing mechanisms tend to focus the addressing on onlyone of the parties involved in communication while, in gen-eral, a communication relationship involves a sender, com-municated content, and receivers. The state of all three aresimultaneously relevant to correctness of a managementrelationship and its communications. We introduce SelectiveNotification, a scalable, decoupled event disseminationarchitecture supporting simultaneous and combinedaddressing of senders, receivers, and events. We demon-strate its application to programming dynamic, scalablemanagement relationships. We then discuss its implementa-tion, and present measurements of its effective capabilities.
ration can be used for error recovery, and coupling this witha sense/analysis error-detection capability yields an archi-tecture for hierarchical management in support of generalfault tolerance mechanisms for networked information sys-tems.
Researchers are pursuing more dynamic and less hierar-chical management structures. Yet there is still merit to thehierarchical approach because of its ability to respond in acoordinated way to damage or attacks that are geographi-cally diverse. The combination of hierarchical and widelydistributed management has significant potential in complexsystems, and more generally, management hierarchy mustapply to increasingly large and dynamic informationsystems[10].
The elements of an approach to the hierarchical manage-ment with increased dynamics may be found in the form of aloosely coupled system[5]. Our proposed mechanism is ageneral architecture, illustrated by the intentionally generalexample of Figure 1. A very large collection (millions) ofnodes of type A (e.g., those requiring management) operatein coordination with a smaller collection of nodes of type B(e.g., those determining management actions). The hierar-chical relationships between them are established dynami-cally, being based on the current state of participants andthird parties such as trust authorities. In this example, nodesinteract with those of the same shade, where shade indicatessome aspect of their states. As their modelled state (shade inthe figure) change, their management relationships are auto-matically updated to reflect appropriate connections.Thereby, these relationships remain current and appropriateover highly dynamic system state. This occurs transparently,without requiring any node to know the state of any other.Consider the nodes of Figure 1 to be managers over alarge distributed system. In general, the appropriateness oftheir intercommunication might involve any combination ofthe state of senders, content, and receivers. This requires acommunication service addressing all three elements. It is intheir simultaneous combination that loosely coupled man-agement relationships may be achieved. By contrast, exist-ing scalable services such as publish/subscribe supportasymmetric addressing. The questions we address are: (1)
1.Introduction
Very large networked information systems—with mil-lions of components—have become crucial to many organi-zations, both military and civilian. Yet they are inescapablyexposed to a wide variety of traumas including extremeenvironmental conditions, failures of operating software,and losses of available resources because of malicious oraccidental damage. In order to provide dependable servicesuch networks have to respond to these changes withexplicit management because, without response, depend-ability would be limited by entropy. The required responsesmay be large and complex, necessitating a sophisticatedmanagement service architecture.
In this paper we introduce a communication mechanismfor facilitating the distributed management of networkedinformation systems, Selective Notification, that providessymmetrically addressed, decoupled event dissemination. Itpermits reconfiguration to be commanded quickly, effi-ciently and in a highly scalable way. This type of reconfigu-
whether a symmetrically addressed mechanism can scalewith reasonableperformance; and (2) whether it can be usedeffectively for expressing management relationships.
Selective Notification is a symmetrically addressed,decoupled event service that deals with both of these ques-tions. In this paper we present Selective Notification’s coreconcept—symmetric indirect addressing, and then we dem-onstrate its utility through application in a hypothetical man-agement scenario. This is followed by exposition of itsimplementation as data transforms as well as modificationsand extensions to Siena[2], a scalable publish/subscribearchitecture.
Our assessment of feasibility is based on experimentswith a full implementation. The results of these experimentsallow us to model its performance for systems far largerthan we can implement directly. We conclude that symmet-rically addressed decoupled communication scales for hier-archical event dissemination in loosely coupledmanagement.
2.Selective Notification
Clients of decoupled communication interact withouthaving knowledge of one another. More specifically, spa-tially decoupled communication[5] allows clients to inter-act despite not knowing each others’ location, quantity,distribution, or state. Property-based communication is aparticularly useful form that allows otherwise decoupledcomponents to communicate by describing—rather thanexplicitly naming—relevant objects in communication rela-tionships. Communication in this form involves two keyelements:
•Property addressable objects: Some objects advertise amodel of their properties to the communications service.
An object’s properties constitute its address.
•Descriptive, indirect addresses: Clients communicate bydescribing, (often through constraints) properties ofaddressable objects. A description forms an indirectaddress of the relevant targets for communication.
Several forms are in use today, and they differ in whichobjects are addressable and which objects perform address-ing. Three common forms are summarized in Table 1. Theyare content-based publish/subscribe[3,4], intentionallyaddressed one-to-many messaging[1], and sender qualifiedmessaging. If these decoupled addressing mechanisms wereused by a loosely coupled hierarchy such as that illustratedin Figure 1, several requirements might arise. A node under-taking reconfiguration might apply intentional addressing toindirectly target an event to managed nodes, doing so bydescribing the states of their internal security alarms forexample. Likewise, managed nodes might apply senderqualification to describe necessary properties of high-levelmanagers from which they will receive commands, requir-ing proper authority for example. However, the architecturesof Table 1 do not support delivery of communication eventsbased upon simultaneous consideration of all three address-ing mechanisms.
2.1The concept of Selective Notification
Selective Notification combines content, sender, andreceiver addressing in a unified, simultaneously appliedaddressing mechanism, and permits a scalable implementa-tion. We refer to the mechanism as the Selective Notificationservice or just Selective Notification where the meaning isclear. We refer to events using this mechanism as SelectiveNotification events. Selective Notification event delivery isillustrated in Figure 2. A message sending client is shown
Thousands of Type B Nodes
With Dynamic State
DynamicManagementRelationships
Third-PartyAuthorities
Millions of Type A Nodeswith Dynamic State
Figure 1. General networked information system management relationships.
on the left and an array of potential receivers clients areshown on the right. Both senders and receivers advertisetheir local state to form their respective addresses. In the fig-ure, each client’s advertised state is represented by anattached “puzzle-piece”. Sender addresses are lightlyshaded, while receiver addresses are white. Sender qualifi-cation is shown by sender puzzle pieces attached to receiv-ers, and intentional addressing is shown with receiverpuzzle pieces attached to senders. The characteristics thatdefine receiver content of interest are depicted by a blackpuzzle-piece at each receiver.
Senders push events to the communications system. Fig-ure 2 shows a sender emitting an event. Its content is a U-shaped black puzzle-piece. In the notation of this figure, anaddress matches an indirect address when their respectivepuzzle-pieces “fit together”. The Selective Notification ser-vice delivers an event to a receiver if and only if intentionaladdressing, sender qualification, and content addressingmatch. In this example, the sender’s event will be deliveredto receivers 1 and 4. The remaining receivers mismatch inone or more element of addressing.
Addressed ObjectEventsReceivers
Addressing ObjectReceiversSenders
3.Related work
Several research groups have applied decoupled com-munication for the purpose of management, such as Soft-ware Dock[7] and Astrolabe[13]. To our knowledge, theimportance of symmetry in establishing loosely coupledmanagement relationships has not been discussed.
Skarmeas et al.[11] describe a symmetrically addressed,decoupled communication mechanism in the form of anagent blackboard. It was not designed as a scalable architec-ture.
Overlap in potential between intentional addressing andpublish/subscribe has been applied in many applications,including sensor networks[9] and the control of robots[6].Designers of scalable communication mechanisms have alsonoted this potential. For example, Siena has been modifiedto support intentional addresses[8], while the authors of theAstrolabe system have proposed using Bloom filters toachieve publish/subscribe[12].
4.An example application
An example application for Selective Notificationmight be defending against a worm. Returning to the illus-tration of Figure 1, we assume on the order of a million low-level managers are embedded within a global distribution ofInternet Web servers and several thousand high-level man-agers are run by service providers. We also assume that theWeb servers are owned by a fictitious corporation, “Macro-corp”, that Macrocorp obtains security service from a sec-ond fictitious corporation, “Intellimune”, and thatMacrocorp cooperates with government emergencyresponse activities.
Our hypothesized scenario assumes the spread of a wormthat, like most worms, exploits a bug in network code toself-replicate (in this case, in Web servers). Unchecked, theworm might undermine Macrocorp’s global application.Fortunately, Intellimune and government systems monitor
SchemeContent-basedPublish SubscribeIntentionally Addressed One-to-many MessagingSender Qualified Messaging
SendersReceivers
Table 1: Summary of traditional, decoupled, property
based addressing schemes.
SenderEventReceiver 1Receiver 2
Addressing TypeSenderQualifiedIntentionalContent
AddressSenderSenderEventIndirect Address
ReceiverReceiverReceiver
Receiver 3Receiver 4Receiver 5
Figure 2. Selective Notification Addressing
for attacks against common software applications. Detectingthe attack, they manage systems such as Macrocorp’sthrough symmetrically addressed decoupled communicationpolicies. Our implementation uses an XML syntax but, inthis example, a more human-readable syntax is used.
4.1Modelling system state
Our model of Web servers, i.e., the state that Web serversadvertise as their address, is: Models are named elements consisting of typed, namedattributes. Every Web service in our example applicationpresents an instance of this model to Selective Notificationin which there is an assignment of a value to each modelattribute such as in the following example: This Web server is free to change its attribute values at anytime. It might, for example, periodically update its loadattribute with its latest calculation. Changes can also includeservers joining and leaving the system. All such changes arehandled automatically by the decoupled communicationsaspect of Selective Notification. Now suppose that Macrocorp agrees to respond to gov-ernment regional fault-response systems. Such high-levelsystems are not allowed to define their own region of com-mand or trustworthiness. Instead, these are assigned to fault-response systems by authorized third parties, such as a regu-lated trust manager. For example, a Northwest regional con-troller might be assigned the following sender qualificationsby authorized third parties: Restricted sender qualification within Selective Notificationallows a tiered-authority model of sender state enforcement,so that increasingly critical state can be managed by increas-ingly trustworthy elements. 4.2Connectivity policies Web servers describe the messages they will receive andthe clients from which they will receive messages throughdefinition of connectivity policies. For example, the Webservers in our hypothetical application might register thefollowing policy:{ AND OR { which translates to “Observes command events from anynational Intellimune control system as well as alerts greaterthan or equal to threat-level 4 from Northwest controllerswith trust rating greater than or equal to 2”. Once in place,received events from senders are those for which evaluationof the connectivity policy expression is true. Thus, Webservers only receive understandable commands and alertsfrom qualified commanders. 4.3Command and alert events Assume that a worm has begun propagating throughMacrocorp’s networks. A fault-response system in theNorthwest is the first to detect the worm infection. It deter-mines that the sensor events are all coming from Web serv-ers running version 2.4 of “IIS.” First, it reports this tonational fault-response systems. Then, it issues a worm alertas an event:Event : alert= “worm”;threat_level= 4;target= “IIS”;version= “2.4.*”} Any receiver of this event will be able to obtain the informa-tion associated with it by examining the attributes. Given that Web servers are enforcing the policy definedabove, all Web servers in the Northwest region will receivethis alert. From the alert they can determine whether theyare vulnerable to attack. Meanwhile, the worm continues toinfect the network. Intellimune attempts to halt the attackwith commands to Web servers. Its national fault-responsesystem has determined that the worm is spreading through a DispatcherClientNotificationForwarding Figure 3. Siena operates as a distributed hierarchy of dispatchers and clients. vulnerability exposed in CGI-scripts running on version 2.4of IIS Web servers. Therefore, it issues the following com-mand event: This event contains a preamble that is a selector (intentionaladdress). It selects Web servers that are running “IIS” ver-sion 2.4 and support CGI scripts. The event itself is a com-mand for those Web servers to disable CGI elements. Thegoal of this command is to limit the infection by disablingthe worm’s attack vector. In an attempt to limit the worm’s aggression, Intellimuneemits another command. It has determined that IIS version2.4 servers showing sustained load are potentially infected.These servers are ordered to shut-down with the followingcommand event: 5.Implementation We now proceed to describe our implementation of theSelective Notification service. We note that it has two limi-tations: (1) not all clients are supported as simultaneoussenders if efficiency is to be maintained; and (2) it necessi-tates more traffic in the overlay network than is strictlyrequired for content-based forwarding. Our implementation was developed, in part, by modify-ing the core data structures and algorithms of Siena[2] (Scalable Internet Event Notification Architecture)—a con-tent-based, publish/subscribe infrastructure. Siena’s core data structures are Filters and Notifications.A Notification is a communicated event consisting of a setof typed attribute/value pairs. Filters are Boolean conjunc-tive expressions over notification attributes. They are usedto define content subscriptions issued by potential receivers.Siena operates as a distributed tree of dispatch servers, anexample of which is shown in Figure 3. Dispatchers performtwo key algorithms. These are: •Filter Propagation: A subscribed filter, f, propagates upthe dispatcher tree until it arrives at the root of the tree,or at a dispatcher with a filter logically covering it, i.e., afilter that passes a superset of that passed by f. Dispatch-ers store received filters. Siena scales very well whenmost subscribed filters are covered by others. •Notification Forwarding: A published notification, p, ispropagated up to the root of the dispatcher tree. It is alsosent down any sub-tree from which a matching filter wasreceived. As a result, notifications are only forwarded tosub-trees with receivers. 5.1Data transformations The Selective Notification service transforms receiverpolicies and Selective Notification events into publish/sub-scribe filters and notifications, respectively. Figure 4sketches the transformation of data constructs from theSelective Notification service to Siena publish/subscribe.Shapes represent data objects. Arrows represent the prod-ucts of transformations. “Plus Signs” indicate the combina-tion of two data objects in a transform. Siena already supports content-based addressing. Thetransformation of sender qualification is straightforward,attributes and constraints are stored in notifications and fil-ters, respectively. The transformation of intentional address-ing is more complex and best illustrated by example.Consider a receiver with an attribute called “load” withvalue “0.3”. If the receiver advertises the selection function“X infrastructure The second part of the implementation required modifi-cation of the Siena dispatcher algorithms and data struc-tures. If it were applied without change to Siena, ourtransformed input would: (1) eliminate the scalability ofSiena filters; (2) fail to deliver most relevant notifications;and (3) allow clients to lie arbitrarily about their attributequalifications. If data transforms only were applied, Selec-tive Notification would be a nearly-pathological applicationof publish/subscribe. Therefore, significant alterations toalgorithms have been made while preserving the two coreoperations of notification forwarding and filter propagation.Briefly, these alterations and modifications are: •Notification Persistence: Notifications remain at dis-patchers for a specified lifetime where they forward tolater subscription filters. In this way, the consistent andrapid changing of filters for intentional addressing andsender qualification does not impede reliable delivery ofnotifications. •Filter Coagulation: Intentional addressing does not gen-erate efficient filter covering relationships. Hence, wedeliberately generalize filters, i.e., make them less spe-cific, to maintain system scalability. This reduces mes-sage forwarding efficiency because some messages areforwarded along paths that will not use them, but aggre-gation maintains notification delivery reliability, i.e., allreceivers obtain all and only relevant notifications. •Attribute Authorization and Capability: Clients of Selec-tive Notification must register for notification and sub-scription capabilities by “login” with a password. Thisrestricts clients to stating attributes in models and notifi-cations for which they are authorized to make claims.•Third Party Qualifiers: We enable third parties to con- • tribute state to client addressing, for example for trustmanagement. Third parties must be given permission, bysession key, from the client which they are to augment.Importantly, a third party may have different authorizedcapabilities than the client it augments. This supportstiered authority models in the use of sender qualificationand intentional addressing. Channeling and Event Ordering: Rather than computingthe forwarding path for all events, some events recordtheir forwarding paths, and others follow these paths.This allows streams of events to travel to the same set ofreceivers, even as their state changes. 6.Measurements of performance and a model of scale The essential practical challenge with Selective Notifi-cation is maintaining adequate performance with scale bothin terms of network size and rate of change of addresses.The issue of performance is complex because performancemetrics need to be defined and measured along the spectrumof dimensions that will affect performance in real systems.From the perspective of general utility, we consider the fol-lowing to be the critical metrics: •Sustainable event delivery time: Time from event issueto event delivery to all relevant clients. •Sustainable event throughput: The sustainable rate atwhich events can be issued into the service without over-loading the service. With those metrics in mind, the key dimensions that affectperformance are: •The size of the application system as measured by thetotal number of independent nodes. •The addressing policies that describe senders, receivers, Selection FunctionTemplate Subscriptions (a) Local Attribute ValuesActual ParametersLocal Attribute ValuesSender Qualifiers Event Content Selective Notification EventReceiver Policy Notifications SienaFilters (b) Figure 4. Data transforms through (a) the Selective Notification service and (b) Siena and content simultaneously. •The rate of change of the state, i.e., addresses being pre-sented to the Selective Notification mechanism. In this section, we present the results of experiments todetermine the metrics above for these parameters. Using theresults, we develop implementation performance-drivenmodels of scale. 6.2Measurement of dispatcher performance We assessed dispatcher performance by operating andmeasuring a dispatcher in a controlled environment; one inwhich all the input factors affecting performance are con-trolled. These factors were: •Available Resources: This includes computing hardware,network resources, and the run-time system environ-ment. •Event Forwarding Set Size: The size of the set of sub-dispatchers and clients to which events are forwarded.•Event Persistence Lifetime: The persistence lifetime ofevent messages. •Subscription Change Rate: The rate at which clientsmodify their state and the rate at which filter coagulationis performed. •Connection Policy Complexity: The number of attributeconstraints registered by clients. Our experimental apparatus, illustrated in Figure 5, is a“ping-pong” throughput experiment. A single “Pinger”application sends “ping” messages to “Ponger” applicationsin sequence. Ponger applications respond to the Pinger witha “pong” message. Additionally, Ponger applications gener-ate broadcast-like background “chatter” messages sent to allother Pongers. During the entire experiment, Ponger appli-cations randomly change the values of their client models(essentially their addresses) at a specified rate, representingdiverse dynamic state change throughout the distributed sys-tem. These last two conditions emulate a worst-case systembehavior with consistently changing client state and the con-tinuous broadcast of commands and alerts. By varying the number of Ponger elements, the rate atwhich they chatter, the event-persistence lifetime of chatter,the size of the Ponger client model, and the rate at whichPongers change their client model instances, we observeperformance capability with respect to the input parametersof interest. For purposes of experimentation, each applica-tion—including each Ponger, the Pinger, and the SelectiveNotification dispatcher—were run on separate computers. 6.1Experimental method In an effort to evaluate Selective Notification, we haveoperated overlay networks on a test-bed of 128 physicalcomputers, each of which is a dual 400 MHz CPU i86machine running Red Hat Linux 6.1 with kernel version 2.2.All software was implemented in Java for runtime 1.4.1.Network level communication was performed with TCPsockets over a 100 MBit/sec fully switched Ethernet. Somecomputers were dedicated to the execution of SelectiveNotification dispatchers and the remainder were used toexecute a hypothetical distributed application. Severalapplication nodes were located on each physical machineand this permitted a total of several thousand client nodes tobe constructed. The actual number of clients varied with thedetails of the experiments being conducted but was typically3,400. This target system allowed us to demonstrate someaspects of feasibility. However, this system is clearly noteven close to Internet scale and so we were not able to testSelective Notification over applications with hundreds ofthousands or millions of clients using it. Instead, we havemeasured the maximum, worst-case performance of a singledispatcher and used the results in an implementation-drivenmodels of performance of a large system. Assuming that alldispatchers have the same resources, we have modeled theworst-case performance of a dispatcher overlay networkusing the worst case performance of a single dispatcher forall dispatchers in the tree (assuming optimal network-levelperformance.) From this data, we have modeled theresources required to achieve necessary service properties inlarge networks. Pinger Dispatcher PongerPongerPonger Figure 5. An experimental test-bed for performance measurements. 6.2.1. Event throughput and output performance. Fig-ure 6(a) shows the maximum throughput rate computedusing the ping-pong experimental configuration. Figure 6(b)shows the maximum event forwarding rate computed for thesame experiments. The X-axes are the number of Pongerclients attached to the Selective Notification dispatcher inthe experiment. The Y-axis of Figure 6(a) is the chatter rateof Pongers communicating with each other using SelectiveNotification but in a worst-case, broadcast-like way. The Y-axis of Figure 6(b) is the total number of output notificationsfrom the dispatcher. Maximum throughput rates were calculated by varyingPonger broadcast-chatter rates and determining the point ofthroughput saturation, i.e., the point where the dispatcherwould begin falling behind permanently. This experimentwas performed with 10 second client-model attributeupdates and coagulation updates, and 60 second persistencelifetimes for notifications. Ping notifications were sentevery two seconds. In order to determine the factors affecting performance,three versions of the Selective Notification dispatcher wererun in separate trials. The first (labelled SN in Figure 6) wascomplete, the second (labelled Forward Only) performedforwarding calculations but then simulated infinitely-fastnetwork communications, and the third (labelled TCPRelay) blindly forwarded all notifications, i.e., it providedno Selective Notification notification service. The results(Figure 6) show that the throughput rate of Selective Notifi-cation under worst-case forwarding conditions (broadcast-like) is dominated by the cost of network communications.The dispatcher performing all forwarding calculations butonly pretending to do network communications (ForwardOnly) had twice the throughput of the dispatcher doing net-work communication but only pretending to do forwarding Worst-case Notification Throughput with Branching Factor200Notifications/Sec180165SN945512384.84521TCP RelayForwardOnlyOutput Notification Rate with Attribute Model Size1000Notifications/Sec80060040020001510152025Attribute Model Size350220170120900600Figure 7. The effect of client model size in attributes on the rate of notification forwarding.calculations (TCP Relay). Figure 6(b) shows that these costsare governed by the total number of output events that mustbe produced by the dispatcher. The measured rate of outputevents shown in Figure 6 is nearly constant for a given fea-ture set (attributes in address and other parameters) regard-less of branching factor (number of Pongers). Thus, theprimary determination of throughput is the size of the set ofpotential receivers. The cost is not comparable at ten Pongnodes because of domination by the cost of Java garbagecollection and other system activities. 6.2.2. Effect of client model size on performance. Thesize of client models, i.e., the number of attributes in theexposed address, has a significant impact on system perfor-mance. A client-model’s size is measured by the number ofattributes in its address. This is proportional to half the sizeof the default filters generated for intentional addressing. Worst-Case Notification Output Rate with Branching FactorOutput Notifications/Sec500040003000200018001650190047004500SN2100TCP RelayForwardOnly1501005001050Child Nodes(a)100055001060050480100100Child Nodes(b)Figure 6. (a) Worst-case event throughput with forwarding-set size; (b) Worst case event forwarding rate with forwarding-set size. Roundtrip Ping-Pong time over TimeLog(milliseconds)0501001502002504000432100Roundtrip Ping-Pong time over Timemilliseconds300020001000050100150200250secondssecondsFigure 8. Round-trip Ping/Pong-pair message time with Selective Notification. Figure 7 shows how the output notification rate of SelectiveNotification varies with the size of the attribute model. Thisexperiment was performed with 60 second message persis-tence, 10 second filter coagulation, and 50 Ponger applica-tions. The second data point (5 model attributes)corresponds roughly to the size of the attribute models in theexperiment from which data was collected in Figure 6.6.2.3. Round-trip message time. Our experimentsrecorded round-trip message time for ping and pong mes-sage pairs. Figure 8 shows ping-pong time over the courseof an experiment in linear and logarithmic scale. The data isfrom an experiment with 50 Pongers, with attribute changesevery ten seconds and notification persistence of 60 sec-onds. Ten messages were input to the dispatcher per second,so that the system was not processor-saturated. The experi-ment was run for 200 seconds. Average round-trip time was220 milliseconds, with a standard deviation of 430 millisec-onds. Deviation occurs from persistent notification time-outs, filter coagulation, clusters client model changes, andJava garbage collection. Under the worst case example ofthese conditions, round-trip time may be as high as three orfour seconds. with a million clients. Such a system could be served by athree-level tree of dispatchers if the branching factor was100. Figure 9 shows the estimated notification worst-casethroughput and worst-case delivery time for variations indispatcher-tree branching factor and resource dedication.We consider dedicated dispatcher networks (labelled withsolid shapes) in which the dispatchers use all computationalresources, and peer dispatcher networks (labelled withshape outlines) in which the dispatchers use one tenth of theresources while clients use the remainder. Using our current implementation, a dedicated dispatchertree with a branching factor of one thousand can support anotification every three seconds and deliver events in fourseconds to a million elements. With a branching factor often, a peer dispatcher tree can support four notifications persecond delivered in 60 seconds. Dedicated dispatchers at thehigher levels of the tree and peer dispatchers at lower levelscan provide intermediate results for both notification rate 2log Throughput (notes/sec)1.510.506.3A Model of scale From these experiments, it is clear that the throughputof Selective Notification depends heavily on the number ofclients and dispatchers connected to a dispatcher, and on thesize of client models. Less important but still significant arethe rates of client attribute (model) changes. Using the mea-surements from the previous section for a dispatcher operat-ing in controlled conditions, we can estimate the maximumthroughput potential of Selective Notification in large dis-tributed applications. A hierarchy of Selective Notification dispatchers isneeded to reach large numbers of clients. Consider a system 10d100d1000d10p100p1000p0-0.5-1-1.5-220406080worst case delivery (sec)Figure 9. Performance design space for varying dispatcher-tree branching factors and for dedicated or peer-hosted dispatchers. and throughput. 10,100 dedicated dispatchers at the base ofthe tree with a branching factor of 100 followed by peer dis-patchers with a branching factor of ten to the clients wouldresult in four notifications per second throughput with 24second delivery time. 7.Conclusions We have introduced a comprehensive and symmetricapproach to communication between managing entities andmanaged entities that has immediate utility in dealing withsecurity attacks and other traumas that require rapid recon-figuration of large networked information systems. Ourexperimental assessment of our implementation suggeststhat the approach scales and provides acceptable perfor-mance. It might be possible to cope with worm attacks invery large networks through rapid, targeted event dissemi-nation as illustrated in Section 4. While additional properties in management relationshipsare necessary to implement loosely coupled management,symmetric decoupled communication can serve as a back-bone for potential architectures. These systems will allowflexible, dynamic, and run-time management relationshipsto reflect and change with system and manager state. As aresult, traditional management structures, such as hierarchy,may be applicable to very large and dynamic systems. Thisincludes application to interface with more widely distrib-uted and cooperative forms of management. 8.Acknowledgements It is a pleasure to acknowledge many helpful discus-sions about this work and about the Siena software systemwith Antonio Carzaniga, Alex Wolf, and Dennis Heimbig-ner. This work was supported in part by the DefenseAdvanced Research Projects Agency under grant N66001-00-8945 (SPAWAR) and the Air Force Research Laboratoryunder grant F30602-01-1-0503. The views and conclusionscontained in this document are those of the authors andshould not be interpreted as necessarily representing theofficial policies or endorsements, either expressed orimplied, of DARPA, the Air Force, or the U.S. Government. References [1]W. Adjie-Winoto, E. Schwartz, H. Balakrishnan, and J. Lilley. “The design and implementation of an intentional namingsystem.” Operating Systems Review, Vol. 34 No. 5, pp 186-2001, December 1999. [2] A. Carzaniga, D. Rosenblum, A. Wolf. “Achieving scalabilityand expressiveness in an Internet-scale event notification ser-vice.” ACM Symposium on Principles of Distributed Com-puting, Portland OR, pp 219-227, July 2000. [3] A. Carzaniga, A. Wolf. “Content-based Networking: A NewCommunication Infrastructure.” NSF Workshop on an Infra-structure for Mobile and Wireless Systems. In conjunctionwith the IEEE International Conference on Computer Com-munications and Networks, Scotsdale AZ, October, 2001.[4] G. Cugola. E. Di Nitto, A. Fuggetta. “The JEDI event-basedinfrastructure and its application to the development of theOPSS WFMS.” IEEE Transactions on Software Engineering,Volume: 27 Issue: 9, pp 827 -850, September 2001. [5] P. Eugster, P. Felber, R. Guerraoui, A. Kermarrec. “The ManyFaces of Publish/Subscribe.” Microsoft Research TechnicalReport EPFL, DSC ID:2000104, January 2001. [6] B. Gerkey, M. Mataric. “Murdoch: Publish/Subscribe TaskAllocation for Heterogeneous Agents.” Fourth ACM Interna-tional Conference on Autonomous Agents, Barcelona, Spain,June 2000. [7] R.S. Hall, D. Heimbigner, A.L. Wolf. “A CooperativeApproach to Support Software Deployment Using the Soft-ware Dock.” IEEE/ACM International Conference on Soft-ware Engineering, Los Angeles CA. May 1999. [8] D. Heimbigner. “Adapting publish/subscribe middleware toachieve Gnutella-like functionality.” Eighth Annual Work-shop on Selected Areas in Cryptography, pp 176-181, Tor-onto, Canada, 2001. [9] C. Intanagonwiwat, R. Govindan, D. Estrin. “Directed Diffu-sion: A Scalable and Robust Communication Paradigm forSensor Networks.” ACM International Conference on MobileComputing and Networking, Boston MA. August 2000. [10] J. Martin-Flatin, S. Znaty, J. Hubaux. “A Survey of Distrib-uted Network and Systems Management Paradigms.” Journalof Network and Systems Management, Vol.7, No. 1, pp 9-22.1999 [11] N. Skarmeas, K.L. Clark. “Content based routing as the basisfor intra-agent communication.” Fifth International Workshopon Intelligent Agents(V): Agent Theories, Languages, andArchitectures, Paris, France, July 1998. [12] W. Vogels, C. Re, R. van Renesse, K. Birman. “A Collabora-tive Infrastructure for Scalable and Robust News Delivery.”IEEE Workshop on Resource Sharing in Massively Distrib-uted Systems, Vienna, Austria, July 2002. [13] R. van Renesse, K. Birman. “Scalable Management and DataMining Using Astrolabe.” First International Workshop onPeer-to-Peer Systems. Cambridge, Massachusetts. March2002. 因篇幅问题不能全部显示，请点此查看更多更全内容