Chordal Reliability Rings
Madhu Kumar S D
KReSIT IIT Bombay India -400076 91 495 2287113
Umesh Bellur
KReSIT IIT Bombay India -400076 91 22 25767865
madhu@it.iitb.ac.inABSTRACT
umesh@it.iitb.ac.in
V.K Govindan
Department of Computer Engineering National Institute of Technology
India-673 601
India
91 495 2286802 vkg@nitc.ac.in
b) hides the complexities and heterogeneity of the underlying
physical environment. c) provides a rich set of API for application development and d) ensures autonomic execution of the application after
deployment. Event based middleware has been described as consisting of five components[8][9]
a) Event Model that describes the data being handled b) Component Model that states the components of the
middleware c) Routing Model that models the communication issues d) Reliability Model that deals with failures and recovery e) Service Model that models the interactions of the
middleware with other models. Hermes[1] introduces two kinds of components for an event-based middleware, event brokers and event clients. Event brokers, distributed over the system, implement the entire functionality of an event based middleware and provide a service to event clients. To use the event-based middleware, event clients have to connect to at least one event broker. Event clients come in two flavors, event publishers that publish events and event subscribers that subscribe to events.
A running application can be the subject of many changes originating both from the underlying execution environment as well as the application itself. Ideally, changes should be handled by the middleware itself without inducing redeployment of the application over the distributed computing environment. Hence the design of the event based middleware should take into consideration the possible changes and their effect with insight and provide for consistent and uninterrupted performance in the presence of changes. The middleware should be able to adapt to changes in distributed applications and systems. Self adaptation or tuning of the middleware is needed for accommodating the changes affecting the middleware after deployment, as redeployment is very costly.
We have surveyed a number of event based middleware projects and found that sufficient attention has not been given to the notion of autonomic or dynamic adaptation. Dynamic adaptation or self tuning requirements of event based middleware forms the central theme of this paper. We focus on the following issues.
•
Formal definition of the triggers that cause dynamic adaptation in event based middleware.
Distributed, event based applications executing on publish-subscribe middleware (aka Event Based Middleware or EBM) are subject to many disruptive changes at runtime. These changes can be caused either by a change in environmental conditions such as the failure of an event broker node or can be caused by dynamically evolving application needs such as the sudden need to route events securely from a specific publisher to a set of subscribers. Ideally, the middleware should facilitate uninterrupted execution of applications without costly redeployment in the face of these changes. We formally study the requirements of such an “adaptive” middleware infrastructure and analyze adaptation in existing efforts. An adaptive overlay for a core level adaptive middleware with a chordal reliability ring is proposed on the basis of the study. We illustrate and prove that two of the adaptation triggers - node and link failures can be handled by the middleware in O (log n) time with the help of the chordal reliability ring.
Keywords
Adaptation triggers, Chordal reliability ring, Event Based Middleware (EBM), Fault tolerant, Overlay.
1. INTRODUCTION
The publish/subscribe (P/S) paradigm for communication between applications in a distributed system supports many- to- many asynchronous, decoupled interaction among information producers and information consumers. The loose coupling between the publishers and subscribers helps preserve anonymity and makes this a suitable paradigm for large scale distributed systems.
Event Based Middleware is manifestation of the P/S paradigm that provides general purpose middleware support to build event based applications. Built as an overlay network of event broker nodes, it helps the components of a large scale distributed application to adjust to the complexity and heterogeneity of the underlying physical environment. Ideally an event based middleware
a) provides an efficient and scalable communication
mechanism for the components of applications to interact
• The interconnection overlay topology of event brokers to facilitate adaptive behavior.
•
How can the event broker network be made resilient to broker and communication link failures?
In this paper we provide a model for defining and classifying dynamic adaptation by introducing the concept of adaptation triggers and their effects. Among the adaptation triggers so identified, we concentrate on two triggers which emphasize the resilient behaviour of the EBM. We provide a new topology model for interconnecting brokers and introduce a chordal reliability ring for resilient behavior. We also demonstrate that the adaptation is done in O (log n) time where n is the number of nodes.
The organization of the rest of this paper is as follows. In the next section, we present our new layered model for Event based Middleware, which abstracts the functional characteristics of an EBM. In Section III we present our new adaptive overlay network model with a chordal reliability ring. The chordal ring is for resilience in the face of node/link failure. Our algorithm for adapting to node/link failures is described and analyzed in this section. Section IV presents the related work in this area and assesses them on capability for dynamic adaptation. Section V summarizes the current status and future work of this research and concludes the paper.
2. A MODEL FOR ADAPTATION
The components [9] of an event based middleware are structured in a layered fashion in our model. The four different layers in our proposed model cover all the essential functionalities of an EBM. The layered architecture is illustrated in Figure 1.
The event model is a formal specification to be adhered to by the clients for event advertisements, event publishing, event subscriptions and matching subscriptions with published events. The overlay network topology represents a logical mapping of the physical network topology. The overlay network consists of event brokers, which are logical nodes in the middleware, connected by logical links to other brokers and clients. The event brokers are intelligent nodes in the middleware which perform routing of events between the clients. SERVICES ROUTING SCHEME OVER-EVENT LAY MODEL TOPOLOGY
Figure 1. Layered Architecture for Event Based Middleware
A logical link represents a high level communication mechanism between two logical nodes and corresponds to a physical path in the network which may consist of one or more physical links. The properties of the logical link reflect and abstract the actual physical conditions in the network, such as the hops, delay and protocols used among others.
The routing scheme defines how the events are dispatched between the clients, which are asynchronous in time and distributed in space. Different routing mechanisms like content based routing, topic based routing[2] and type based routing[2] algorithms are widely used for content delivery in EBM. Different routing schemes can be implemented on the same overlay substrate.
The Services layer includes additional and optional functionalities like support for secure communication, client mobility, broker mobility, quality of service (QoS) assurance and application-centered (domain-specific) services like the synchronization of audio and video data in multimedia communications.
In the layered architecture, the lowest layer of the EBM comprising of the event model and the overlay network is designated as the kernel of the EBM. The kernel is an essential feature and is present in all EBM. The kernel cannot be altered after deployment of the middleware. The two outer layers, i. e., the routing scheme and the services layer work in tandem to provide different types and numbers of services to the distributed computing application. We call these layers together as the shell of the EBM.
On this layered model we define the adaptation boundaries using the cause-effect model. We identify a list of causal events and their effects in the system. We term these causal events triggers. We define adaptation based on the activities in the middleware on occurrence of the triggers. The triggers occurring in an EBM can be grouped into two categories. a) Routine triggers b) Adaptation triggers
Routine triggers are fundamental occurrences that any P/S middleware should support. New event advertisement, registration of new clients, subscription modifications are some examples of routine events. These triggers are routine in nature and all EBM have to support them due to the fact that they represent the basic functionalities of any conventional EBM. In fact, we can go so far as to say these are really not adaptation triggers at all since they occur frequently.
Triggers such as the movement of clients, load variations and advertisements of events with special needs like express delivery or secure delivery need not be considered by the conventional middleware. These occurrences trigger a number of changes in the P/S system performance and we call them adaptation triggers. The adaptive middleware should have the necessary routines so as to adapt to these changes. Adaptation is defined as the property of self tuning on the part of the middleware on the occurrence of adaptation triggers to provide uninterrupted service to the applications without redeployment of either the middleware or the application.
Adaptation trigger events and our layered model of EBM are used to classify EBM that support dynamic adaptation into three types as follows.
1. EBM that support adaptation to client related
adaptation trigger events such as client mobility. 2. EBM that support adaptation to event model based
trigger events such as notification of an emergency event. 3. EBM that support adaptation to network based or
resource related trigger events such as broker or channel failure. Figure 2 illustrates the types of adaptation triggers, which are grouped based on the above classification scheme.
However this list is not exhaustive and more adaptation trigger events can be identified and mapped into one of these three categories.
An adaptive EBM anticipates the occurrence of all these trigger events and has the necessary logic integrated in the middleware code and executed automatically when the corresponding trigger event occurs. In other words the middleware needs to have the algorithms designed and coded for handling the occurrence of these trigger events.
EBM can support dynamic adaptation at various layers. A classification of the EBM based on the layer of support for dynamic adaptation is the illustrated next.
2.1
Adaptation in the layered EBM model
Adaptation Triggers Client Event Resource model Client movemenUrgent / Channel t express Failure event delivery Publishing rate variation Broker Failure (Link Load change) Secure AvailabEvent ility notificatVariatioions nFigure 2. Classification of Adaptation triggers
The layers at which an EBM supports adaptation form the basis for identifying the following two types of adaptive EBM.
1. Core level adaptive EBM 2. Shell level adaptive EBM
In core level adaptive EBM, adaptability is supported from the lowest layer of the EBM onwards, i. e., it is supported at all layers. In the shell level adaptive EBM, adaptive services are provided to the application only at the routing scheme and services layers, but the inner core layer or the kernel does not provide any inherent support for this adaptation. Core level adaptive EBM can be further classified as
a) EBM with adaptation oriented event model[11] b) EBM with adaptive overlay topology
Shell level adaptive EBM can be further classified as
a) EBM with Adaptive Routing scheme b) EBM with Adaptive Services
An ideal EBM is one that supports adaptation at all the four layers and this is possible only with a core level adaptive EBM. The ultimate goal of our research is to achieve this. In this paper we present our design for an adaptive overlay, which takes care of two of the triggers, namely, the failure of brokers and the failures of channels. In the next section we present our new adaptive overlay model and the chordal reliability ring which can adapt to broker failure and channel failure trigger events.
3.
AN ADAPTIVE OVERLAY MODEL
Our overlay topology for the event broker network is based on the multigraph structure. The main focus of this topology is on adaptation, especially to resource-based triggers such as node/link failure. A chordal reliability ring is maintained on the multi graph structure for fault tolerance.
In a wide area network there exists multiple physical connections between the computers. Hence a weighted multigraph structure is chosen to represent the overlay network with each node of the graph representing a broker. The edges represent the overlay communication channels that exist between brokers. Figure 3 illustrates the multigraph overlay model. 2 3 1 64 5 7
Secure Link Urgent / Express Link Normal Link Broker Node Figure 3. Multigraph overlay model
The links are weighted by their bandwidth or carrying capacities. There are multiple links defined between the brokers. Links, which have high bandwidth, can be used for speedy delivery of urgent events. Events whose delivery requires high security from threats like Denial of Service attacks, man in the middle attacks and others are to be routed through secure links, i.e., a path which supports communication of messages using a secure communication protocol. Hence the links between the nodes can be normal links, express links or secure links. The concept of chordal rings used in our overlay, and their theoretical background are described next.
3.1
Chordal rings in networks
A chordal ring is a ring of nodes with additional links called chords which connect nodes which are not adjacent to each other in the simple ring structure. Arden and Lee [14] proposed chordal rings of degree 3 (called chordal rings of third degree) as the topology for interconnection networks for efficient and reliable routing of data in multicomputers.
A third degree chordal ring [15] has an even number of nodes labeled with edges 0, 1, 2,…n-1 and each even node i is connected to nodes (i±1)modn and (i−c)modn, for some odd integer c.
[15] gives an optimization of chordal ring structures for minimum diameter for a given order and maximum order for given diameter. Periodically regular chordal rings are proposed for massively parallel architectures [16] as a “compromise for combining low node degree with small diameter” and are demonstrated to have smaller diameters, shorter routing paths and simpler routing algorithms as compared to competing architectures. [17] studies a class of chordal ring networks in which the chord length is a power of an odd radix, and show that they have many advantages in terms of dynamic performance in many application contexts. They also suggest the development of fault tolerant routing algorithms on such networks.
3.2 Chordal ring for adaptation to resource failure
In this paper, we propose an irregular chordal ring to model the overlay network in event based P/S systems. The fundamental multigraph topology representing the overlay has a subgraph which is a regular chordal ring of degree 4, i.e., it has an embedded chordal ring of degree 4.
Every node i has r edges, where r≥4. Each node has logical links to nodes (i±1)modn and(i±2)modn, if we consider the n nodes in the network to be sequentially numbered as 0..n-1. In addition, the nodes have links to any (log n) nodes numbered (i +k) mod n where k may vary between 3 and n-2.
In our chordal ring, the ids of the nodes are assigned in a scalable manner as follows. Assume that the maximum number of nodes or the node id space is 2 32. The first node gets id 0 and the second node is assigned the id 216 –1. After that, every new node that joins the ring is given the id mid-way between its left and right neighbours. Now we describe how this chordal ring can be used to increase the reliability and handle node and link failures. Figure 4 illustrates the chordal reliability ring. Every node is connected to nodes that are designated as two of its “neighbours” in the ring. In addition it has links to two of its next further “neighbours” too. When a node is added to the broker network, the neighbours are selected based on the round trip delay for a ‘ping’ like message. The lower layers report the round trip delay to the broker and one of the nodes with the lowest delay is selected as the neighbour. This selected node then inserts the new node into the chordal ring as its neighbour, making necessary updations in the chordal ring. All the information maintained by a node is backed up in one, two, three or four neighbouring nodes according to the required level of reliability. This can be decided based on the network conditions and failure statistics if available. When a node fails, neighbours detect (using any standard
method), as they already have a link between them. When a node fails, the neighbouring node can optionally do one of the following.
(1) Share the tasks of the broken node, if the current load at
the node is within the permitted limit. This limit is decided ultimately by the hardware parameters like processor speed, memory, buffer size etc. (2) Share the tasks with next neighbours by passing the
information if it cannot afford to takeover all the tasks of the failed broker. (3) If the current load is very high, and the neighbours are
also heavily loaded then the node can request for another broker to be set up, insert it into the ring by setting up new links, store up the pending actions and pass on them to the new broker as soon as it is up.
Broker node
Figure 4. Chordal reliability ring
A formal description of our weighted multigraph model of the broker network with the chordal reliability ring is given below.
3.3
Weighted multigraph model
The graph G is formally defined as G = B is the set of brokers (nodes) of the graph. En, Es and Eu are the sets of edges of the graph, representing different types of bi-directional overlay links between pairs of brokers. W is the set of weights for edges based on the link bandwidth and existing message traffic. These elements are formally described below. 3.3.1 The Broker Set -B B is the set of all Brokers. A broker b∈B is a nine tuple id = id of broker assigned when it joins the broker network Client = {c|c is a client (publisher/subscriber) registered with b} Neighset= {x | there exists a link from b to x in the overlay} Left,Right,Leftleftand Rightright are pointers to the left neighbour, left neighbour’s left neighbour, right neighbour, and right neighbour’s right neighbour respectively in the chordal ring. These nodes can be directly accessed by the node b and are based on locational proximity. Routetab is the routing table. The routing table implements a routing function R. The routing function maps from a domain set to the set of adjacent overlay links and clients. The domain set and the function mapping is determined by the routing algorithm. Pow is the computing power of the broker which is a function of the processing power and storage capacity of the broker node. 3.3.2 Normal link Set - En En is the set of all normal links (b1, b2), where b1 and b2 are two brokers in the graph and edge (b1, b2) represents a link in the overlay network between them. If En contains (b1, b2), it implies that b1 can directly address b2 and vice-versa, as the link is bi-directional. 3.3.3 Urgent or express link Set - EEu u is the set of all urgent links (b1, b2) where b1 and b2 are two brokers in the graph and edge (b1, b2) represents an express link in the overlay network between them. If Eu contains (b1, b2), it implies that b1 can directly address b2 and vice-versa as the link is bi-directional, and the latency of the message transfer is guaranteed to be in the range designated as the “express” range. Eu is a subset of En. 3.3.4 Secure link Set - EEs s is the set of all secure links (b1, b2) where b1 and b2 are two brokers in the graph and edge (b1, b2) represents a secure link in the overlay network between them. If Es contains (b1, b2), it implies that b1 can directly address b2 and vice-versa and the message will be delivered using secure protocols for message transfer throughout the path. Es is a subset of En. 3.3.5 Weight Set - W W is a weight set corresponding to the edges in En. Corresponding to each edge (b1, b2) in the edge set there is an element The reliable ring (or the chordal ring) is a sub graph ,Left(b)),(b,Leftleft(b))} bU{(b∈B The chordal reliability ring helps in adaptation to broker/link failures. An algorithm to create the chordal ring is outlined below. Upon creation of a new broker node, it contacts the nearest neighbour in the broker network. The contacted node inserts the new node into the broker network if it has id space in its neighbourhood. The new node is joined as its neighbour on the left or right depending on which side has more id space remaining. Only four nodes in the neighbourhood, including the new node and the contacted broker, require link and data updations, giving an O (1) complexity for the addition. The following is the formal description of this algorithm. The new broker node b: join-overlay (broker b) { A=ping-broker(); y=first(A); /* random select y from the list of closest neighbours */ send-join-request(broker y, broker b); } The requested neighbour y: Process-join-request(broker y, broker b) { /*Maxnodes is 2 32 */ if (((id[y] – id[y->Left]) mod Maxnodes)>=((id[y]->right-id[y]) mod Maxnodes)) { /* More id space on left side, hence join b as left neighbour of y*/ b->id=id[y] + ((id[y]–id[y->Left])/2) mod Maxnodes; Ly=Left[y]; Ry=Right[y]; LLy=Leftleft[y]; Left[y] =b; Right[b] =y; Left[b] =Ly; Leftleft[Ry] =b; Leftleft[y] =Ly; Rightright[b] =Ry; Right[Ly] =b; Rightright[Ly] =y; Modify-routing-table-backups(Ry, y, b, Ly, LLy); } else if ((id[y->Right])> (id[y] +1) mod Maxnodes) { /* join b as y’s right neighbour as there is id space there*/ id[B] =id[y] + (id[y->Right])-id[y])/2) mod Maxnodes; Ly=Left[y]; Ry=Right[y]; RRy=Rightright[y]; Right[y] =b; Left[b] =y; Right[b] =Ry; Rightright[Ly] =b; Rightright[y] =Ry; Leftleft[b] =Ly; Left[Ry] =b;Leftleft[Ry] =y; Modify-routing-table-backups(Ly, y, b, Ry, RRy); } else { /* there is no id space as B’s neighbour hence request neighbour’s neighbour send-join-request(y->Righright, broker b); } } In this manner, any new broker generated is inserted into the Chordal reliability ring. A formal complexity analysis of the join algorithm is beyond the scope of this paper. It can be seen that it is O (1) in the best case. In the next subsection we present the power of the chordal ring in handling the node and link failures. 3.4 Handling node failure and link failures using the chordal ring 3.4.1 Node Failure We discuss node failure and its efficient handling in our chordal ring overlay. AC B Figure 5. Part of a chordal ring Consider the three consecutive nodes A, B and C which form part of a chordal ring as shown in Figure 5. Suppose node B fails. Node A detects a failure in the link AB, but it does not know whether it is a link or node failure. It sends a test-neighbour (B) message to node C, its neighbour’s neighbour. When C receives this message it sends a test-acknowledgement message to node B to test if it is live or not. If it receives no reply within the stipulated time, it confirms node failure of B and sends failed (B) message to A. Nodes A and C execute a divide-Neighbour(B) and send messages to all the neighbours of B to request them to route messages meant for B to A or C. The complexity of this operation is bounded by O (degree (B)). If degree of B is bounded by log n then the complexity of the algorithm dealing with node failure is O (log n). 3.4.2 Link failure Suppose a link AB in the overlay fails. It is detected by nodes A and B, but they cannot ascertain whether it is a link failure or a node failure of the node at the other end of the link. There are two cases a. The link AB is a link on the chordal ring. b. The link AB is a chord of diameter > 2. The node handles the two cases differently. If the link is a link on the chordal ring, the actions taken are partially outlined in the algorithm on node failure, described in the previous section. If the neighbour’s neighbour does receive acknowledgement from the node suspected to have failed, it sends to the enquiring node the message that the node is up and original node confirms link failure. Then it routes via the neighbours neighbour all the messages meant for the neighbour. If the link is not a link on the chordal ring, the node A tries to confirm a link failure by routing a query message to the node at the other end B. It does so by routing to the node with id nearest to the id of B and having a link to A. The receiving node relays the message. It is thus routed through a traced series of nodes to the destination. If the destination node B is up, it sends a link-down message back via the incoming path, unless it has not already sent a query message similar to A. Thus node A either receives the query message or the link down message and in either case concludes that the link to node B is down and fixes up the alternate path so obtained as the new routing path. Node B also concludes that the link failed on receiving A’s query. If the sending node A receives neither the query message from B nor link down message it waits and ultimately gets a new route message from the neighbour of the failed node B. We assume degree of each node to be bound by log n and the links from every node to be uniformly distributed in the n-node space. Then the process takes O (log n) time. 3.5 Adaptation in the proposed overlay topology The multigraph based overlay topology model with the chordal ring can efficiently support all the adaptation triggers we have listed in Section III. The load variations on the links due to the increase of traffic can result in link failures or buffer overflow. This can be handled by an adaptive routing algorithm which can utilize the alternate paths available in the multi graph for load distribution and control. The chordal ring can also handle client mobility. Seamless mobility of clients and efficient local roaming and distant roaming of clients can be handled with minimum message overhead through the chordal ring. The routing information being duplicated in the neighbouring nodes of the chordal ring helps in adapting to local client movement (regional roaming) transparently. The design and analysis of the algorithms for dealing with mobility are beyond the scope of this paper. As there are express, normal and secure links defined in the overlay, adapting to the event disseminations of urgent, and secure events is straightforward. The failures of channel can be handled at the routing algorithm thorough the standby links. The broker failure will not affect the network as the routing and related information are backed up in four neighbouring nodes. (Left, Right, Leftleft and Rightright). An adaptive routing algorithm can also optimize of the routing paths established initially, in accordance with the changes in resource availability. Thus the proposed overlay is capable of supporting all the adaptation triggers listed in Figure 2. 4. RELATED WORK Event based Middleware is a well studied area and a number of research projects have been carried out in this field. Many prototypes have been developed and some of them like Hermes [1][2] and REBECA[7] are available in the public domain. We have surveyed the EBM research projects to assess the support for adaptation. We summarize our findings in Table 1. The research projects studied here are Hermes[1][2], Siena[5], JEDI[4], REBECA [6][7], Elvin[3], MEDYM[12], Kyra[13], and Gryphon[10]. Table 1. Adaptation support in EBM projects Adaptation 1 2 3 4 5 6 7 Trigger events Event Based Middleware projects Elvin N N N N N N N JEDI Y N N N N N N Siena N N N N N N N Gryphon N N N N Y Y Y Hermes N Y N Y N Y N MEDYM N N N N N N N Kyra N N N N N N N REBECA N N N N N N N The different columns of the table are to be interpreted as follows. 1. Client Mobility 2. Publishing rate variations 3. Express events delivery 4. Secure delivery 5. Link Fault tolerance 6. Node Fault tolerance 7 Resource availability variations The table clearly indicates that the currently known EBM prototypes do not support dynamic adaptation. Only Gryphon[10] and Hermes[2] support few of the adaptation triggers that we have listed earlier. An event Based Middleware which is having support to the adaptation requirements identified in Section 2 is not available. In other words the present EBM research does not support dynamic adaptation adequately. We have also studied the EBM projects on their overlay modeling of the broker network and the support for adaptation. The findings are summarized in Table 2. Table 2. Overlay topology models in EBM and adaptation support EBM Overlay Support for Adaptation at the Topology overlay topology level Used Elvin Star No support Hermes Transit/ Stub Node failure is addressed Siena Acyclic and No support general Graph structures Gryphon Hyper Graph Addresses node as well as link failures REBECA Symmetric Tree No support JEDI Tree No support MEDYM No Static overlay No support Kyra General Graph No support composed of cliques 5. CONCLUSION & FUTURE WORK This paper has presented a new model for dynamic adaptation in event based middleware by introducing the concept of adaptation triggers. The scope for adaptation in EBM has been categorized based on different adaptation triggers identified at various layers of the middleware. As the second step to a core level adaptive EBM, a weighted multi graph based structure for the overlay topology with a chordal reliability ring is proposed and described in this paper. We have proved that the chordal reliability ring can handle the node and link failures occurring in an Event Based Middleware in O (log n) time. We are developing an adaptive content based routing algorithm on this static topology. The routing algorithm proposes to use the already established concepts of filter merging[7][8] and covering along with other reported features of content based routing. The routing algorithm over the proposed overlay topology will be tested in a simulated environment. 6. REFERENCES [1] Peter. Pietzuch and Jean. Bacon. Hermes: A Distributed Event-Based Middleware Architecture. 1st International Workshop on Distributed Event-Based Systems (DEBS'02), In Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS'02), 611-618, Vienna, Austria, July 2002. [2] Peter R. Pietzuch. Hermes: A Scalable Event-Based Middleware. Ph.D. thesis, Computer Laboratory, Queens' College, University of Cambridge, February 2004. [3] Bill Segall and David Arnold. Elvin has left the Building: A Publish/Subscribe Notification Service with quenching. In Proceedings of AUUG Technical Conference '97, Brisbane, Australia, September 1997. [4] Gianpaolo Cugola, Elisabetta Di Nitto, and Alfonso Fuggetta. The JEDI Event-Based Infrastructure and its Applications to the Development of the OPSS WFMS. IEEE Transactions on Software Engineering (TSE), 27(9): 827-850, September 2001. [5] Antonio Carzaniga. Architectures for an Event Notification Service Scalable to Wide-Area Networks. PhD thesis, Politecnico di Milano, Milano, Italy, December 1998. [6] Ludger Fiege, Mira Mezini, Gero Mouhl, and Alejandro P. Buchmann. Engineering Event based Systems with Scopes. In the Proceedings of the European Conference on Object-Oriented Programming (ECOOP'02), volume 2374 of LNCS, 309-333, Malag a, Spain, June 2002. [7] Ludger Fiege, Gero Mouhl, and Alejandro Buchmann. An Architectural Framework for Electronic Commerce Applications. In Informatik 2001: Annual Conference of the German Computer Society, 2001. [8] Antonio Carzaniga, David S. Rosenblum, and Alexander L.Wolf. Design and Evaluation of a Wide-Area Event Notification Service. ACM Transactions on Computer Systems, 19(3): 332-383, August 2001. [9] David S. Rosenblum and Alexander L. Wolf. A Design Framework for Internet-Scale Event Observation and Notification. In Proceedings of the 6th European Software Engineering Conference/ACM SIGSOFT 5th Symposium on the Foundations of Software Engineering, Zurich, Switzerland, September 1997. [10] IBM TJ Watson Research Center. Gryphon: Publish/Subscribe over Public Networks. URL http://researchweb.watson.ibm.com/gryphon/Gryphon, December 2001. [11] Madhu Kumar S D and Umesh Bellur. SAME: A New Event Model for Adaptive Event Driven Middleware, KReSIT Technical report, IITB/KReSIT/2006/April/4, Kanwal Rekhi School of Information Technology, IIT Bombay, April 2006. [12] Fengyun Cao, Jaswinder Pal Singh. MEDYM: Match-Early and Dynamic Multicast for Content-Based Publish-Subscribe Service networks. In proceedings of ICDWS, 2005. [13] Fengyun Cao and Jaswinder Pal Singh. Efficient event Routing in Content-based Publish-Subscribe Service networks. In proceedings of IEEE INFOCOM 2004. [14] W. Arden and H. Lee. Analysis of Chordal Ring Network. IEEE Transactions on Computers Vol. 30 No: 4, pp 291-295, 1981. [15] P. Morillo, F. Comellas and M. A. Fiol. The optimization of chordal ring networks. World Scientific, pp-295-299, 1987. [16] Behrooz Perhami. Periodically regular chordal ring networks for massively parallel architectures. Frontiers’95 Fifth Symposium on the Frontiers of Massively Parallel Computation, 1995. [17] Behrooz Perhami. Chordal rings based on Odd-Radix number systems. Communications in Computing, pp-196-199, 2005. 因篇幅问题不能全部显示，请点此查看更多更全内容