Network Working Group P. Adamska
Internet-Draft A. Wierzbicki
Intended status: Standards Track T. Kaszuba
Expires: 13 October, 2009 PJIIT
May 18, 2009
Publish-subscribe over the generic Peer-to-Peer Protocols
draft-paulina-p2psip-pubsub-01
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on October, 2009.
Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of
publication of this document (http://trustee.ietf.org/license-info).
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document.
Abstract
This document introduces a generic publish-subscribe protocol, that
can be built on top of RELOAD or P2PP. It works both for the
unstructured and DHT-based Peer-to-Peer networks. Moreover it is
highly customizable to address the optimization issues and support
different topology structures. It can be used to implement P2P-SIP
services such as presence or event notification.
Adamska, et al. Expires October 13, 2009 [Page 1]
Internet-Draft Publish-Subscribe May 2009
Table of contents
1. Introduction...................................................2
2. Terminology....................................................2
3. Architecture...................................................3
3.1 Overview...................................................3
3.2 Publish-subscribe transport................................4
3.3 Core Algorithm.............................................4
3.4 Customizable Algorithm.....................................6
3.5 Topology Manager...........................................6
3.6 Publish-Subscribe API......................................8
3.6.1 Publish-Subscribe Interface...........................8
3.6.2 Publish-Subscribe Callbacks...........................9
4. Publish-Subscribe Protocol....................................10
4.1 General information.......................................10
4.1.1 Topic................................................10
4.1.2 Subscriber...........................................11
4.1.3 Subscription.........................................11
4.1.4 Event................................................12
4.1.5 Interest conditions..................................12
4.1.6 Access control rules.................................13
4.2 Default Customizable Algorithm............................14
4.2.1 Create topic.........................................14
4.2.2 Transfer topic.......................................16
4.2.3 Remove topic.........................................19
4.2.4 Subscribe............................................19
4.2.5 Unsubscribe..........................................20
4.2.6 Publish..............................................22
4.2.7 Notify...............................................22
4.2.8 Maintenance..........................................23
4.2.9 Reliability..........................................26
4.3 Message formats...........................................26
4.3.1 Standard header......................................27
4.3.2 Standard request header..............................28
4.3.3 Create topic.........................................29
4.3.4 Subscribe............................................29
4.3.5 Unsubscribe..........................................30
4.3.6 Publish..............................................30
4.3.7 Notify...............................................30
4.3.8 Standard response header.............................31
4.3.9 Subscribe response...................................31
4.3.10 Keep-alive..........................................32
4.4 Objects formats...........................................32
4.4.1 AC rules.............................................32
4.4.2 Rule.................................................32
4.4.3 Operation............................................33
4.4.4 User.................................................33
4.4.5 Subscriber...........................................34
4.5 Message types.............................................34
4.6 Event types...............................................35
4.7 Response codes............................................35
4.8 Security..................................................35
Adamska, et al. Expires October 13, 2009 [Page 2]
Internet-Draft Publish-Subscribe May 2009
5. Integrating publish-subscribe with P2PP/RELOAD................35
5.1 Extending P2PP/RELOAD interfaces..........................35
5.1.1 Callbacks............................................36
5.1.2 Objects..............................................43
5.1.3 API..................................................44
5.2 Usage of the extension....................................44
5.2.1 Objects..............................................44
6. Future work...................................................45
7. IANA Considerations...........................................45
8. References....................................................45
8.1 Normative references......................................45
8.2 Informative references....................................45
Authors' Addresses...............................................46
1. Introduction
The publish-subscribe protocol described in this paper is built on
top of the generic P2P protocols such as RELOAD[1] and P2PP[2]. Both
of them make the differences between peer-to-peer routing algorithms
transparent to the higher-layer applications. Our main concern while
designing the publish-subscribe protocol was to preserve this
transparency in the presence of a great variety of overlay types. The
proposed protocol may exchange messages both directly between the
specified peers or by encapsulating them in the resource objects and
sending inside the P2P insert request. A set of callback methods has
been defined to let the publish-subscribe layer capture the incoming
P2P requests, process them and modify the default P2P protocol
behavior if it is necessary. In this document we describe the generic
protocol, that works both for the unstructured and DHT-based P2P
networks. It can be easily configured to optimize its behavior using
the overlay-specific features or simply replaced by a set of
different algorithms for the various P2P networks. Both operations
are completely transparent for the higher-layer applications and
topology-independent. Additionally we also define the Access Control
Rules (AC), which allows higher-layer application to let some of the
users subscribe for the specified topic without granting them
permission to generate events. These rules are stored by all the
topic subscribers, as they can be responsible for accepting other
nodes' requests. The proposed publish-subscribe protocol also
provides so called Interest Conditions (IC) which can be used as a
simple filter for the received events. Each node can define the
group of users generating interesting events. Each node also stores
a certain number of events, that have recently been published for
the topic. The new subscriber may ask for sending some or all of
them after the successful subscription process. Nodes may also store
a configurable number of the 'backup nodes' in the special caches,
to use them in case of the direct parent's failure. The proposed
protocol allows replacement of the default publish-subscribe
algorithm with some other ones. This means that it may be integrated
with a set of different algorithms to be dynamically loaded depending
on the underlying overlay type (for instance Scribe-like for Pastry
Adamska, et al. Expires October 13, 2009 [Page 3]
Internet-Draft Publish-Subscribe May 2009
and some other for different ones). Moreover such operation is
completely transparent for the higher-layer applications and
topology-independent.
Due to the terminology differences between P2PP and RELOAD, in this
document we use 'insert' for the P2PP publish object and RELOAD
store request, and 'lookup' for the P2PP lookup and RELOAD fetch
request where distinguishing one from another is not essential.
This document is organized as follows. Section 3 describes the core
components of the protocol and briefly explains, how the proposed
mechanism may be extended. The proposed protocol MAY be integrated
with many different publish-subscribe algorithms. Section 4 describes
the elements common for all of them, introduces the default algorithm
and shows how it can be configured to optimize its behavior for
the DHT-based overlays. Detailed information about integration of the
publish-subscribe protocol with P2PP and RELOAD are presented in
section 5.
2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [3].
Some of the terminology has been borrowed from the P2PP[1] and
RELOAD[2] drafts.
Topic owner: The node which has created the topic.
Topic root: A non-leaf node in the topology structure - indirect
parent for all the other nodes. It MAY be a topic
subscriber or not. In the DHT-based overlays, it
will be the peer with id numerically closest to the
topic identifier.
Topic history: Every node participating in the topology structure,
that is able to accept new subscribers (which means
it is a peer, not client) stores the list of the
events that have recently been published for the
specified topic. During the subscription process
node can ask its parent to send some, or all of
them. History only refers to the custom events, not
the predefined ones, such as AC_MODIFIED.
Topic cache: The backup list of nodes participating in the topology
structure which is used in case of detecting the
direct parent's failure. There may be several types of
caches stored be a single node.
Adamska, et al. Expires October 13, 2009 [Page 4]
Internet-Draft Publish-Subscribe May 2009
3. Architecture
3.1 Overview
To provide a generic and highly extensible publish-subscribe
mechanism we decided to split it, as it is shown in the figure
3.1.1. The arrows illustrate the communication between the
various components of the publish-subscribe layer.
+---------------------------------------------------------------------+
| Publish-Subscribe API |
| +-----------------------------+ +-----------------------------+ |
| | Publish-Subscribe Callbacks | | Publish-Subscribe Interface | |
| +-----------------------------+ +-----------------------------+ |
| ^ ^ | |
+-----------|---------|---------------------------------|-------------+
| +------------------------+ |
+----------------------+ | |
| | v
+-------------------------------+ | +-------------------------------+
| Topology Manager | | | Customizable Algorithm |
+-------------------------------+ | +-------------------------------+
^ | ^
| | |
v | v
+---------------------------------------------------------------------+
| Core Algorithm |
| +-----------------------------------------------------------------+ |
| | Algorithm Configurator | |
| +-----------------------------------------------------------------+ |
+---------------------------------------------------------------------+
^
|
v
+---------------------------------------------------------------------+
| Publish-Subscribe Transport |
| +-----------------------------+ +-----------------------------+ |
| | RELOAD/P2PP Transport | | Direct Transport | |
| +-----------------------------+ +-----------------------------+ |
+---------------------------------------------------------------------+
Figure 3.1.1: Publish-subscribe layer architecture
The following sections provide the detailed description of the most
important components of the publish-subscribe layer.
Adamska, et al. Expires October 13, 2009 [Page 5]
Internet-Draft Publish-Subscribe May 2009
3.2 Publish-subscribe transport
This component is directly responsible for the communication. It
passes the incoming publish-subscribe messages to the Core Algorithm
and sends the outgoing ones. It hides the details of the sending
procedure - for example encapsulates a publish-subscribe message
inside the network resource object if it is to be sent within the
P2P insert request. All the publish-subscribe requests may be routed
either directly to some specified node, or using the overlay-specific
algorithm. The second method is chosen, when the exact destination is
not defined - for example to determine the root during the topic
creation procedure in a DHT-based network. Indications and responses
are always passed directly to a specified node.
[TODO: Perhaps for the direct connections publish-subscribe
use RELOAD's Attach() - as it was described in the SIP Usage]
3.3 Core Algorithm
This component provides the core features of the publish-subscribe
layer which are to be common for all the Customizable Algorithms.
All the incoming messages are passed directly to this component. It
checks whether it stores information about the specified topic (or
does not store - for the create topic request) and whether the
message originator is allowed to perform a certain operation. If
both requirements are fulfilled, it passes the message to the
Customizable Algorithm or the Topology Manager. Otherwise it sends
the response with an appropriate error code to the request
originator itself. It is also responsible for forwarding the events
notifications to the node's children and checking IC, before
passing them to the higher-layer application. Probably the most
interesting feature of this component is its ability to query the
P2P layer for the overlay type and dynamically load the appropriate
algorithm with the suitable configuration. This can be achieved by
defining a separate Algorithm Configurator that is used by the Core
Algorithm to create an appropriate Customizable Algorithm object.
The choice of the suitable component is made on the basis of the
underlying P2P network type. This object is also able to configure
such parameters as the size of the caches. Caches store the lists
of the 'backup nodes' to be used in case of detecting the direct
parent's failure. Each node may store several types of such lists,
for example associated with different levels of the multicast
tree. The decision on the number of caches depends on the
Customizable Algorithm component's policy. Each parent is
responsible for filling its children's caches by periodically
sending them keep-alive messages containing the appropriate lists
of nodes. Storing such information is essential in the
unstructured networks. However it may not be crucial in the
DHT-based ones, where the topology structure can be repaired at a
relatively low cost using the overlay-specific routing algorithm,
Adamska, et al. Expires October 13, 2009 [Page 6]
Internet-Draft Publish-Subscribe May 2009
without performing the complex lookup procedures. In such case
the Algorithm Configurator may set the cache size to 0 and treat
event notifications as a heartbeat messages to reduce the additional
traffic associated with the structure maintenance. Moreover, if some
new Customizable Algorithm requires sending any additional
information in a standard publish-subscribe message - it can
register this extended message format to make the Core Algorithm
load it instead of the standard message object after receiving the
specified request. For example the default Customizable Algorithm
stores the information about the Interest Conditions locally, but
some different algorithm may choose to built the IC-based multicast
tree, where the child's IC are the subset of its parent's IC. This
requires adding the information about the IC to the standard
subscribe request. Such extended message can be registered using
the Algorithm Configurator. Figure 3.3.1 illustrates the usage of
this component.
+----------------------------------------------------+----------------+
| | Core Algorithm |
| +----------------+
| |
+---------------------------------------------------------------------+
| ^
| chord-128-2-16+ | Customizable Algorithm
| |
v |
+--------------------------------------------+------------------------+
| | Algorithm Configurator |
| +------------------------+
| |
| 1. Create the appropriate Customizable Algorithm object |
| 2. Configure the object |
| 3. Register the messages for all the publish-subscribe operations |
| |
+---------------------------------------------------------------------+
Figure 3.3.1: Usage of the Algorithm Configurator component
3.4 Customizable Algorithm
This component implements all the methods from the Publish-Subscribe
Interface and takes care of the processing of most of them. For
instance the create topic operation requires performing different
procedures in the DTH-based and unstructured overlays. In the first
case it is enough to encapsulate the create topic request inside the
P2P insert request, giving the topic identifier as an object key.
The unstructured networks require performing the lookup procedure to
ensure that some other node has not created the specified topic
before. It is also necessary to place the SUBSCRIPTIONINFO objects
in the P2P network to inform other nodes about the existing
participants of the topology structure created for the particular
Adamska, et al. Expires October 13, 2009 [Page 7]
Internet-Draft Publish-Subscribe May 2009
topic. Additionally in the DHT-based networks transferring certain
topics to the new root may be necessary, if some new node joins the
P2P network and its ID is closer to the topic ID according to the
overlay-specific distance metrics. The Customizable Algorithm
component also takes part in the topology structure creation
process - this feature is described in details in the next section.
3.5 Topology Manager
This component is responsible for creating and maintaining the
specified topology structure. It handles all the subscribe requests
and takes part in the topic transfers. Currently there are two
structures defined: star and multicast tree. For the first one,
topology manager only ensures, that none of the nodes except the
topic root accepts new subscribers. The situation is slightly more
complex for the multicast trees. For instance the Customizable
Algorithm component may require creating IC-based trees. Then the
node, receiving a subscribe request, must check whether the new
subscriber's IC are the subset of its own ones. If it is not - it
has to forward the request to the higher level of the multicast
tree because it will not be receiving all the events that are
interesting to the new subscriber. In such cases Topology Manager
must consult the Customizable Algorithm component to identify the
next hop for forwarding the subscribe request. Figure 3.5.1
illustrates the subscribe procedure that uses the described
mechanism. Figure 3.5.2 shows the structure that does not apply
any additional rules for accepting the new subscribers. In this
case the marked node B may not be receiving all the interesting
events.
(a) +------------+ (b) +------------+
| Root | | Root |
| IC={1,2,3} |-+ | IC={1,2,3} |
+------------+ | +------------+
^ | | / \
subscribe | | | / \
| | | / \
| | | / \
subscribe +------------+ | +------------+ +------------+
+---------->| A | | | B | | A |
| | IC={1,2} | | | IC={2,3} | | IC={1,2} |
+------------+ +------------+ | +------------+ +------------+
| B | |
| IC={2,3} |<--------------------+
+------------+ subscriber accepted
Figure 3.5.1: Subscribe procedure that applies the additional
rules defined by the Customizable Algorithm component (a) and
the multicast tree after completing the procedure (b)
Adamska, et al. Expires October 13, 2009 [Page 8]
Internet-Draft Publish-Subscribe May 2009
(a) +------------+ (b) +------------+
| Root | | Root |
| IC={1,2,3} | | IC={1,2,3} |
+------------+ +------------+
| |
| |
| +------------+
| | A |
subscribe +------------+ | IC={1,2} |
+------------>| A | +------------+
| | IC={1,2} |-+ |
+------------+ +------------+ | |
| B | | +============+
| IC={2,3} |<----------------------+ | B |
+------------+ subscriber accepted | IC={2,3} |
+============+
Figure 3.5.2: Subscribe procedure that does not apply the additional
rules defined by the Customizable Algorithm component (a) and the
multicast tree after completing the procedure (b)
Figure 3.5.3 briefly describes the exact procedures performed by the
node receiving a subscribe request to build an IC-based multicast
tree using the proposed mechanism.
+---------------+----------+ +------------------------+----------+
| Tree Topology | | | Customizable Algorithm | |
+---------------+ | +------------------------+ |
| | | |
| 2. Query for a better | | 3. If the new subscriber's IC are |
| node to accept the | | the subset of this node's IC |
| request | | return null |
| 4. If the better node == | | 3'.Otherwise return this node's |
| null, accept the | | parent |
| request | | |
| 4'.If the better node | | |
| != null, forward the | | |
| request to that node | | |
| | | |
+--------------------------+ +-----------------------------------+
^ | ^ | ^
|1.subscribe |2 | |3.better |
| request | | | node |
| | | | |
| | | | |
+----------------+---|-------|-------------|---------------------|---+
| Core Algorithm | | +-------------+ | |
+----------------+ +-------------------------------------------+ |
| |
| |
Adamska, et al. Expires October 13, 2009 [Page 9]
Internet-Draft Publish-Subscribe May 2009
| 1. If the topic exists and the node is allowed to subscribe for |
| it |
+--------------------------------------------------------------------+
Figure 3.5.3: Procedure performed by the node receiving a subscribe
request
3.6 Publish-Subscribe API
3.6.1 Publish-Subscribe Interface
Application issues a publish-subscribe request using one of the
methods described below. All of them are implemented by the
Customizable Algorithm component. Each operation is asynchronous, as
it can take a long time to complete. Parameters enclosed in the
square brackets are optional.
void createTopic(String topicId, boolean subscribe,
[AccessControlRules ac])
@param topicId Topic identifier.
@param subscribe Value indicating whether this node wants to
automatically subscribe for the specified topic
after its creation. In this case the 'create topic'
request is specially prepared and there is no need
to send a separate 'subscribe' request later on.
@param ac Access control rules defined for the operations associated
with this topic.
void removeTopic(String topicId)
@param topicId Topic identifier.
void subscribe(String topicId, [InterestConditions ic],
[int eventIndex])
@param topicId Topic identifier.
@param ic Object representing Interest Conditions defined for the
particular topic by the higher-layer application.
@param eventIndex Value indicating which events from the topic
history node wants to receive after successfully
completing the subscribe operation.
Adamska, et al. Expires October 13, 2009 [Page 10]
Internet-Draft Publish-Subscribe May 2009
void unsubscribe(String topicId)
@param topicId Topic identifier.
void publish(String topicId, Event e)
@param topicId Topic identifier.
@param e Event to be published.
3.6.2 Publish-Subscribe Callbacks
Additionally the publish-subscribe layer defines a set of callback
methods, which are invoked after completing asynchronous operations
and can be implemented by the higher-layer application. These methods
are described below.
public void onTopicSubscribe(String topicId)
@param topicId Topic identifier.
Called after a successful subscription.
public void onTopicCreate(String topicId)
@param topicId Created topic identifier.
Called after a successful topic creation.
public void onTopicNotify(String topicId, byte[] message)
@param topicId Topic identifier.
@param message Message encapsulated in the received event.
Called when node receives a custom event notification.
public void onTopicRemove(String topicId)
@param topicId Removed topic identifier.
Called when node receives the notification informing that the
particular topic has been removed.
Adamska, et al. Expires October 13, 2009 [Page 11]
Internet-Draft Publish-Subscribe May 2009
public void onPubSubError(String topicId, Operation o, int errorCode)
@param topicId Topic identifier.
@param o Operation which failed to complete successfully.
@param errorCode Error code.
Called when an asynchronous operation fails to complete successfully.
4. Publish-Subscribe Protocol
4.1 General information
4.1.1 Topic
Apart from the identifier, there are several information stored for
each topic:
1) Owner
The node which has created the topic
2) Parent
Node's parent in the topology structure
3) Access Control Rules
Described in details in the section 4.1.6
4) Interest Conditions
Described in details in the section 4.1.5
5) Subscription list
The list of topic subscribers, which are this node's children in
the topology structure
6) Caches
The backup information about other nodes participating in the
topology structure
7) Distance
The distance between the peer id and the topic id (calculated
Adamska, et al. Expires October 13, 2009 [Page 12]
Internet-Draft Publish-Subscribe May 2009
using the overlay-specific metrics)
8) History
The list of the previously published events for the specified
topic
4.1.2 Subscriber
Apart from the topic identifier, this object contains information
such as:
1) User name
User name in the Peer-to-Peer network
2) Peer id
Peer id in the Peer-to-Peer network
3) IP address
4) Port number
Port used for exchanging the publish-subscribe messages directly
4.1.3 Subscription
Subscription contains the following information:
1) Subscriber
2) Expiration time
How long the subscription is valid - after this period node needs
to resubscribe
4.1.4 Event
Every publish-subscribe event contains information about its
publisher and the identifier of the topic it is associated with. The
proposed publish-subscribe protocol defines three types of events:
- remove topic - informs all subscribers that the particular topic
has been removed
- AC modified - informs all subscribers that the Access Control Rules
(section 4.1.6) for the specified topic have been modified
Adamska, et al. Expires October 13, 2009 [Page 13]
Internet-Draft Publish-Subscribe May 2009
- custom - this event encapsulates the user-defined events
4.1.5 Interest conditions
Each subscriber can define its Interest Conditions (IC) for the
topic. This means he can declare that he wants to receive information
only about the events published by a specified group of users. It can
be described as follows:
operation: eventtype(ALL): interestingusers[]
eventtype(...):interestingusers[]
If the 'interestingusers' list for the specified event type is empty,
it means that it is always interesting regardless the publisher. The
conditions defined for the event type ALL are always checked first.
If the 'interestingusers' list for it is empty, the decision on
whether the specified event is interesting or not, depends on the
'interestingusers' associated with the particular event type.
If there is no rule defined for some operation or event - it means it
is not interesting at all.
By default all the subscribers will be receiving every topic event.
It means that each non-leaf node in the topology structure has to
pass every event to all of its children. IC are defined locally and
checked by the topic subscriber before invoking the higher-layer
notify callback. Otherwise the node's parent in the topology
structure would have to define similar IC (to receive all the events,
that are interesting for its children). Additionally after modifying
IC, subscriber would in some cases have to be passed to a different
parent in the topology structure, generating extra traffic.
If IC for some topic are defined as follows:
NOTIFY: eventtype(ALL):
eventtype(REMOVETOPIC):
eventtype(MODIFYAC):
eventtype(CUSTOM): user1, user2, user3
then after receiving a CUSTOM notification from user1, 2 or 3, node
will inform higher layer about it. REMOVETOPIC and MODIFYAC events
are by default interesting regardless the publisher.
4.1.6 Access control rules
Nodes can define a set of rules for the topic, to grant other users
different access permissions (AC). These rules can be described as
follows:
Adamska, et al. Expires October 13, 2009 [Page 14]
Internet-Draft Publish-Subscribe May 2009
operation: eventtype(ALL): allowusers[]
eventtype(...): allowusers[]
If the 'allowusers' list for a specified event type is empty, it
means that the associated operation can be performed by any
subscriber. The permissions defined for the event type ALL are always
checked first. If the 'allowusers' list for it is empty, then
granting access permission depends exclusively on the 'allowusers'
defined for the particular event type.
If there is no rule for some operation or event - it means it is not
allowed.
For example if the rules for some topic are:
SUBSCRIBE: eventtype(ALL): user1, user2, user3, user4
PUBLISH: eventtype(ALL):
eventtype(REMOVETOPIC): user1
eventtype(MODIFYAC): user1
eventtype(CUSTOM): user1, user2, user3
It means that:
- Only user1 is allowed to modify AC rules for the topic. By default
this permission is granted exclusively to the topic owner.
- If the topology structure participant receives a 'subscribe'
request for example from user5, subscription will fail due to
access control restrictions. Only users 1, 2, 3 and 4 are allowed
to subscribe for the topic.
- User4 may (according to SUBSCRIBE rules) subscribe for receiving
the topic events, but isn't allowed (according to PUBLISH rules) to
generate them. Users 1, 2 and 3 are all allowed to publish
user-defined events, but only user1 has permission to remove this
topic. By default only topic owner has permission to publish the
predefined events such as REMOVETOPIC or MODIFYAC.
In case of any collisions in the AC rules - the most important is the
one marked with ALL clause. For example if the rules are defined as
follows:
PUBLISH: eventtype(ALL): user1, user2, user3
eventtype(REMOVETOPIC): user1
eventtype(MODIFYAC): user1
eventtype(CUSTOM): user4
User4 will not be able to publish any event, because the first rule
to be checked is: eventtype(ALL): user1, user2, user3. It could be
repaired either by removing the 'allowusers' list for event type ALL,
or adding user4 to it.
The topic owner always retains permission to modify AC rules and
remove the topic, but it can also grant it to other users. Rules
Adamska, et al. Expires October 13, 2009 [Page 15]
Internet-Draft Publish-Subscribe May 2009
defined for the 'notify' operation MAY differ for different nodes. By
default each subscriber will only accept event notifications from its
parent in the topology structure.
4.2 Default Customizable Algorithm
This section describes the default Customizable Algorithm component's
behavior and the possibilities of configuring it to address the
optimization issues. In some cases it is essential to determine
whether the underlying P2P network is a DHT-based or an unstructured
one. To fulfill this requirement we define an additional method that
asks the generic P2P protocol to calculate the distance between the
two given keys according to the overlay-specific metrics. Such
calculations are possible only in a DHT-based network. Each
publish-subscribe Customizable Algorithm component MUST implement
the set of operations defined in this section. In the diagrams shown
in this section we use '{PUBSUB}msg' notation to indicate, that the
message 'msg' is sent directly to the specified node and
'{P2P}insert(msg)' in case of messages encapsulated within an insert
request.
4.2.1 Create topic
To perform this operation node encapsulates the 'create topic'
message inside the P2P resource object, sets its key to the topic ID
and sends it within the P2P insert request. In the DHT-based networks
it is enough for the node receiving such request to check, whether it
does not store information about the specified topic itself
(figure 4.2.1). The unstructured networks require some lookup
procedure to determine, whether the topic has not been created by a
different node (figure 4.2.2). Such situation may occur, because the
object encapsulated inside the P2P resource object will in most cases
be stored by the 'create topic' request originator. This is where the
idea of the SUBSCRIPTIONINFO objects comes along. They are associated
with the particular topic and contain contact information about its
subscribers. The status of such object may be PENDING or ACCEPTED.
The difference between both states will be explained later on. Each
node receiving a 'create topic' request places a pending
SUBSCRIPTIONINFO object in the underlying P2P network. Then it looks
for other objects associated with the specified topic. If there is at
least one with the accepted status - it assures us that the specified
topic already exists. If the underlying P2P network stores only the
pending SUBSCRIPTIONINFO objects, than the peer with the lowest ID is
allowed to become the root for the specified topic. All the others
are supposed to remove their SUBSCRIPTIONINFO objects and send the
response with an appropriate error code. The 'create topic' request
may additionally contain a list of nodes, which are to be added to
the topic subscribers after successfully completing the operation.
This way its originator does not have to issue a separate 'subscribe'
request later on. The 'create topic' message may also be used to
Adamska, et al. Expires October 13, 2009 [Page 16]
Internet-Draft Publish-Subscribe May 2009
transfer the topic to the new root, in which case a special flag is
set to indicate that this request refers to an existing topic.
Regardless the purpose, the described request always contains AC
rules defined for the topic.
Topic root
| {P2P}insert(messageObject) |
|------------------------------>| 1. if this is not a topic transfer
| |
| {PUBSUB}409 |
|<------------------------------| 2. if the topic exists
| | 3. finished
| |
| | 2'. if the topic does not exist
| | 3'. create the topic
| {PUBSUB}200 | 4'. add the subscribers if the
|<------------------------------| request contains any
| | 5'. finished
Figure 4.2.1: Create topic procedure in a DHT-based network
Topic root Root's neighbor
| {P2P}insert(messageObject) | |
|--------------------------->| 1. if this is not a topic |
| | transfer |
| {PUBSUB}409 | |
|<---------------------------| 2. if the topic exists |
| | 3. finished |
| | |
| | 2'. create the topic with a |
| | PENDING status |
| | 3'. insert mine |
| | SUBSCRIPTIONINFO |
| | object with a |
| | PENDING status |
| | |
| |{P2P}lookup(SUBSCRIPTIONINFO) |
| |-------------------------------->|
| | |
| | |
| |
| | 5'. if no SUBSCRIPTIONINFO found for
| | this topic or only PENDING objects
| | created by the peers with the higher
| | IDs exist - set the topic's and the
| | SUBSCRIPTIONINFO object's status to
| | ACCEPTED
| | 6'. add the subscribers if the
| | request contains any
Adamska, et al. Expires October 13, 2009 [Page 17]
Internet-Draft Publish-Subscribe May 2009
| {PUBSUB}200 |
|<---------------------------|
| | 8'. finished
| |
| | 5''. if an ACCEPTED SUBSCRIPTIONINFO
| | found or the PENDING object created
| | by the peer with the lower ID exists
| | 6''. Remove the PENDING topic and mine
| | SUBSCRIPTIONINFO object
| {PUBSUB}409 |
|<---------------------------|
| | 8''. finished
| |
Figure 4.2.2: Create topic procedure in an unstructured network
4.2.2 Transfer topic
This operation is essential for the DHT-based networks. It MAY be
performed when the publish-subscribe layer receives the information
from the P2P layer, that it has accepted the other node's join
request. In such case the node iterates through all the topics it
stores information about. If it is the root for one of them and the
distance between the new peer's ID and the topic ID is smaller than
the distance calculated for this node, it sends a create topic
request inside the P2P insert message. Before sending the request,
the previous root MAY also add the list of its direct children to it.
All of the procedures associated with the topic transfer are
performed by the Topology Manager component, as it is responsible for
retaining the appropriate structure. For instance in the star
topology, all the request originator's children must be passed to the
new root as well. If some Customizable Algorithm component is
designed exclusively for the unstructured networks, it MAY choose not
to perform this procedure or use a different measure than the
distance between identifiers to determine, whether the specified
topic should be transfered. The brief description of the whole
procedure is shown in the figure 4.2.2.1.
+------------------------+-------+ +------------------+---------+
| Customizable Algorithm | | | Topology Manager | |
+------------------------+ | +------------------+ |
| | | |
| foreach(topic in storedTopics) | | 3. Transfer the topic |
| 2. If thisNode is the root | | to the new peer |
| for this topic && | | |
| thisNodeToTopicDistance> | | |
| newPeerToTopicDistance | | |
| | | |
+--------------------------------+ +----------------------------+
^ | ^
Adamska, et al. Expires October 13, 2009 [Page 18]
Internet-Draft Publish-Subscribe May 2009
|1.new |2.topic, |
| peer | new peer |
| | |
| | |
+----------------+---|-------------------------------------------|--+
| Core Algorithm | | | |
+----------------+ +-------------------------------------------+ |
| |
| |
| 1. New neighbor arrives |
| |
+-------------------------------------------------------------------+
Figure 4.2.2.1: Overview of the topic transfer procedure
The details of the transfer topic procedure performed by the Topology
Manager component are described in the figures 4.2.2.2 (for the star
topology) and 4.2.2.3 (for the multicast tree).
(a) Previous root New root
| |
| | 1. Add the nodes from
| | the list inside the
| | transfer request to
| | the topic
| | subscription list
| {PUBSUB}200 |
|<-------------------------|
| |
(b) Previous root's
child Previous root New root
| | |
| | {PUBSUB}200 | Accepting
| 1. Set parent to |<-------------| topic
| the new root | | transfer
| 2. Send keep-alive | |
| indication | |
| to inform the | |
| child about the | |
| parent's change | |
| | |
| {PUBSUB}keep-alive | |
|<------------------------| |
1. Check if this | | |
message was sent| 3. Remove the child | |
by my parent | from the topic | |
(otherwise | subscription list| |
discard it) | 4. If this node is | |
Adamska, et al. Expires October 13, 2009 [Page 19]
Internet-Draft Publish-Subscribe May 2009
2. Set parent to | not the topic
the one stated | subscriber itself
in keep-alive | - remove the
3. Update the cache| topic
4. Reset keep-alive| 5. Finished
timer for this |
topic |
|
Figure 4.2.2.2: Processing the transfer request(a) and response(b) by
the star topology
(a) Previous root New root
| |
| | 1. Add the request
| | originator to the
| | topic subscription
| | list
| {PUBSUB}200 |
|<--------------------------|
| |
(b) Previous root's
child Previous root New root
| | |
| | {PUBSUB}200 | Accepting
| 1. Set parent to |<-------------| topic
| the new root | | transfer
| 2. Send keep-alive | |
| indication | |
| to update the | |
| child's cache | |
| | |
| {PUBSUB}keep-alive | |
|<------------------------| |
1. Check if this | | |
message was sent| 3. Finished | |
by my parent |
(otherwise |
discard it) |
2. Set parent to |
the one sent |
in keep-alive |
3. Update the cache|
4. Reset keep-alive|
timer for this |
topic |
|
Adamska, et al. Expires October 13, 2009 [Page 20]
Internet-Draft Publish-Subscribe May 2009
Figure 4.2.2.3: Processing the transfer request(a) and response(b) by
the multicast tree
4.2.3 Remove topic
To perform this operation, the node publishes the predefined
REMOVE_TOPIC event among the topic subscribers. After that all the
SUBSCRIPTIONINFO objects associated with this topic MUST be removed
from the underlying P2P network.
4.2.4 Subscribe
To subscribe for a topic, node has to send a 'subscribe' request to
the peer that is already participating in the appropriate topology
structure. Determining the message destination is crucial for the
whole procedure. In the DHT-based networks it is enough to
encapsulate the publish-subscribe request in the resource object.
Then it can be captured using the P2P protocol callbacks. The
unstructured networks require performing the lookup procedure for the
SUBSCRIPTIONINFO objects to identify the existing topology structure
participants. After that the request may be sent directly to the
specified node. Also the multicast trees are built using a different
approach in the unstructured and DHT-based environment. In the first
case, node accepts only the subscribers with the ID greater than its
own one (figure 4.2.4.1). The nodes that do not fulfill these
requirements are forwarded to the direct parent. Only the topic root
accepts all the requests unless this is forbidden by the AC rules.
Such an arrangement of the topology structure participants simplifies
the recovery procedures after the direct parent's failure.
+--------+
| Root |
| id=2 |
+--------+
/ \
/ \
+--------+ +--------+
| A | | B |
| id=4 | | id=3 |
+--------+ +--------+
| |
| |
+--------+ +---------+
| C | | D |
| id=8 | | id=15 |
+--------+ +---------+
Figure 4.2.4.1: Multicast tree created on top of an unstructured
network
Adamska, et al. Expires October 13, 2009 [Page 21]
Internet-Draft Publish-Subscribe May 2009
In the DHT-based network the nodes are arranged by the distance
between their identifiers and the topic ID (figure 4.2.4.2).
+------------+
| Root |
| distance=2 |
+------------+
/ \
/ \
+------------+ +------------+
| A | | B |
| distance=4 | | distance=3 |
+------------+ +------------+
| |
| |
+------------+ +-------------+
| C | | D |
| distance=8 | | distance=15 |
+------------+ +-------------+
Figure 4.2.4.2: Multicast tree created on top of a DHT-based network
In the unstructured networks, after successfully completing the
described procedure, the new subscriber must place its
SUBSCRIPTIONINFO object in the underlying network. This is done only
if it is a peer, as clients SHOULD NOT be responsible for accepting
new subscribers. The node must also locally modify the AC rules for
the notify operation, to indicate that only its direct parent is
allowed to send event notifications to it. The standard subscribe
request also contains the additional information, such as the index
of the last received event. After accepting the new subscriber, its
parent must send the requested set of the notify messages containing
the historical events to it. Each subscription is valid only for a
specified time, so the node needs to renew it periodically.
4.2.5 Unsubscribe
If the node has no more children in the topology structure and it is
not the topic root, it simply sends an 'unsubscribe' request directly
to its parent and removes its SUBSCRIPTIONINFO object from the
overlay if it is necessary. If the node has more children, it also
has to send the keep-alive indication to them. It is depicted in
figure 4.2.5.1. The unsubscribe request sent to the node's parent
contains the list of its children. Parent node has to add the new
children to its own ones. Children nodes get keep-alive indication
with the information about the new parent and modify their cache
information (figure 4.2.5.2). If necessary, keep-alive indications
are propagated down along the multicast tree to update other node's
caches (the unsubscribing node can be stored in their grandparents
cache). Note that after unsubscribe root node does not notify the
Adamska, et al. Expires October 13, 2009 [Page 22]
Internet-Draft Publish-Subscribe May 2009
higher-layer about the received events anymore, but it is still able
to forward appropriate messages to its children.
+------+
| Root |
+------+
|
|
+-------+
+-->| A |
unsubscribe | +-------+
children={C,E} | |
| | keep-alive
| +--\--/--+ parent=A
+---| B\/ |----------+---+
| /\ | | |
+--/--\--+ | |
/ \ | |
/ \ | |
+-------+ +-------+ | |
| C | | E |<---+ |
+-------+ +-------+ |
^ |
| |
+-------------------------+
Figure 4.2.5.1: Multicast tree before the unsubscribe procedure
+------+
| Root |
+------+
|
|
+-------+
| A |
+-------+
/ \
/ \
+----------+ / \ +----------+
| Cache C: | +-------+ +-------+ | Cache E: |
| p={A} |<--------| C | | E |-------->| p={A} |
| g={ROOT} | +-------+ +-------+ | g={ROOT} |
| n={C,E} | | n={C,E} |
+----------+ +----------+
Figure 4.2.5.2: Multicast tree after the unsubscribe procedure
Adamska, et al. Expires October 13, 2009 [Page 23]
Internet-Draft Publish-Subscribe May 2009
4.2.6 Publish
There are three types of the predefined events that can be published
among the topic subscribers: AC_MODIFIED, TOPIC_REMOVED and CUSTOM.
The first one is generated, when the access control rules are
modified. The third one represents a custom event defined by the
higher-layer application. The default Customizable Algorithm
component requires all the publish messages to be delivered to the
topic root, which accepts the request, sends the appropriate response
to its originator and the set of notify indications to the direct
children. This is done to avoid the situation, when for example AC
rules have been modified, but the AC_MODIFIED event has not been
propagated among all of the topic subscribers. In such case some of
them may accept the events from the node which is not allowed to
generate them anymore. In the default Customizable Algorithm
component AC rules are defined so, that only the node's parent in the
topology structure is allowed to send event notifications to it. Note
that there are two situations, in which such indication may be
received. The first one is when a new event is generated by some
node. In this case the notification SHOULD be forwarded down along
the multicast tree. However it might happen that the new subscriber
receives the requested historical events after successfully
completing the subscribe operation. In such case no further
forwarding is needed. The node only updates its own topic history and
invokes the higher-layer callback. The default Customizable Algorithm
component also requires the node to be a topic subscriber to generate
events.
4.2.7 Notify
After receiving a publish request, topic root propagates the event
among its children using the notify message. Like all indications,
notifications are send directly to the specified nodes. Figure
4.2.7.1 briefly describes the procedure performed after receiving
such message. By default the Customizable Algorithm component defines
AC rules so, that only the node's parent in the topology structure is
allowed to send notifications to it. There are three predefined event
types sent within the notify message(see section 4.1.4). All the
received notifications MUST be forwarded to children unless they are
historical.
Child Parent
| |
| {PUBSUB}notify |
1. If operation not allowed - finished |<--------------------------|
| |
2. If event is interesting (according | |
to IC) and historical (appropriate | |
flag set to 1), node: | |
- updates topic history | |
Adamska, et al. Expires October 13, 2009 [Page 24]
Internet-Draft Publish-Subscribe May 2009
- if it is topic subscriber, not | |
just a forwarder invokes | |
higher-layer application callback | |
3. Finished | |
| |
2'. If event is interesting and new | |
(appropriate flag set to 0), | |
node: | |
- updates topic history | |
- forwards notification to | |
children (and invokes its own | |
callback if it is topic | |
subscriber) | |
3'. Finished | |
| |
Figure 4.2.7.1: Procedure performed after receiving
event notification
4.2.8 Maintenance
Apart from the necessity to transfer a topic to the new root in some
situations, there is also the nodes' failures problem that has to be
handled by the Customizable Algorithm component. To address this
issue, we define a keep-alive indication. Every node periodically
sends this message to its direct children. If some peer is the other
one's parent for several topics, it does not have to send a separate
indication for each one of them. Such message contains the
information about the current parent and the list of the 'backup
nodes' to be placed in the node's cache for each topic. When the
child detects its parent's failure, it uses the cache to resubscribe.
If the cache size is set to 0 by the Algorithm Configurator
component, the default Customizable Algorithm assumes, that the
keep-alive message does not carry any additional information and
treats the notify indication as a 'keep-alive', like Scribe does.
This way, if events are frequently published for the specified
topics, no additional traffic associated with the topology structure
maintenance is involved. This optimization mechanism can be
considered for the DHT-based networks, where the recovery procedure
may be performed at a relatively low cost using the overlay-specific
routing. In general there are three types of caches stored for each
topic: parents cache, grandparents cache and neighbors cache. The
capacities of the caches are the parameters k (for the parents and
neighbors) and g (for the grandparents). For the node N at the level
x, parents cache contains k nodes with the lowest id or the closest
to the topic id from the level x-1. It may also contain the node's
direct parent. The neighbor cache contains k nodes with the lowest id
or the closest to the topic id from the level x, which have the same
parent as N. The grandparents cache contains one node from each level
between x-2 and x-1-g. This cache is stored in case of the multiple
Adamska, et al. Expires October 13, 2009 [Page 25]
Internet-Draft Publish-Subscribe May 2009
nodes' failures in the highly unbalanced trees. When all the nodes
from the parents cache fail to respond or the cache is empty - the
node can try to send 'subscribe' request directly to its grandparent.
All the nodes at the same level and in the same subtree have the same
caches' contents. Nodes in the different subtrees have different
neighbors caches' contents. All the entries in the parents and
neighbors caches are sorted from the lowest id (or distance to the
topic id) to the highest. In the grandparents cache the node from the
highest level is stored at the lowest index. Examples of the topology
structures and caches' contents for both the unstructured and
DHT-based networks are shown in the figures 4.2.8.1 and 4.2.8.2.
------------------------------------------------------
+-------------+ +-------+ | Level 0
| Cache ROOT: |<------------------| ROOT | |
| p={} | | dist=2| |
| g={} | +-------+ |
| n={} | / | \ |
+-------------+ ----------------/----|----\---------------------------
+----------+ / | \ | Level 1
| Cache A: | +--------+ +-------+ +-------+ |
| p={ROOT} |<---------| A | | B | | C | |
| g={} | | dist=8 | | dist=3| | dist=5| |
| n={B,C} | +--------+ +-------+ +-------+ |
+----------+ ---------/-----\---------------|----------------------
+----------+ / \ | | Level 2
| Cache D: | +--------+ +-------+ +-------+ |
| p={B,C} |<-----| D | | E | | F | |
| g={ROOT} | | dist=11| | dist=9| | dist=6| |
| n={E,D} | +--------+ +-------+ +-------+ |
+----------+ ------------------|-------------|---------------------
| +---------+
| |
V V
+----------+ +----------+
| Cache E: | | Cache F: |
| p={B,C} | | p={B,C} |
| g={ROOT} | | g={ROOT} |
| n={E,D} | | n={F} |
+----------+ +----------+
Figure 4.2.8.1: Caches' contents for k=2 and g=1 in the DHT-based
network
-------------------------------------------------------
+-------------+ +-------+ | Level 0
| Cache ROOT: |<------------------| ROOT | |
| p={} | | id=2 | |
| g={} | +-------+ |
Adamska, et al. Expires October 13, 2009 [Page 26]
Internet-Draft Publish-Subscribe May 2009
| n={} | / | \ |
+-------------+ ----------------/----|----\---------------------------
+----------+ / | \ | Level 1
| Cache A: | +--------+ +-------+ +-------+ |
| p={ROOT} |<---------| A | | B | | C | |
| g={} | | id=8 | | id=3 | | id=5 | |
| n={B,C} | +--------+ +-------+ +-------+ |
+----------+ ---------/-----\---------------|----------------------
+----------+ / \ | | Level 2
| Cache D: | +--------+ +-------+ +-------+ |
| p={B,C} |<-----| D | | E | | F | |
| g={ROOT} | | id=11 | | id=9 | | id=6 | |
| n={E,D} | +--------+ +-------+ +-------+ |
+----------+ ------------------|-------------|---------------------
| +---------+
| |
V V
+----------+ +----------+
| Cache E: | | Cache F: |
| p={B,C} | | p={B,C} |
| g={ROOT} | | g={ROOT} |
| n={E,D} | | n={F} |
+----------+ +----------+
Figure 4.2.8.2: Caches' contents for k=2 and g=1 in an unstructured
network
Figure 4.2.8.3 briefly describes the usage of the grandparents cache
in case of the multiple nodes' failures.
+------+
+--->| ROOT |
| +------+
| |
| |
| +-\--/-+
| | A\/ |
| | /\ |
| +-/--\-+
| | \
possible path for | | \
resubsciption | +-\--/-+ +-\--/-+
| | B\/ | | E\/ |
| | /\ | | /\ |
| +-/--\-+ +-/--\-+
| |
| |
| +------+ +-------------+
+----| C |------->| Cache C: |
Adamska, et al. Expires October 13, 2009 [Page 27]
Internet-Draft Publish-Subscribe May 2009
+------+ | p={B,E} |
| g={A,ROOT} |
| n={C} |
+-------------+
Figure 4.2.8.3: Example of the grandparents cache usage
(algorithm parameters: k=2 and g=2)
After discovering the direct parent's failure, node tries to send the
'subscribe' request to the the first node from its parents cache. If
it does not respond, it is removed from the cache, and the
'subscribe' request is sent to the next one. If all the nodes from
the parents cache fail to respond, the grandparents cache is used. If
the grandparents cache does not contain any useful information and
the node's distance to the topic ID is greater than 0, than peer
assumes that it participates in the DHT-based network and there may
be some node which ID is closer to the topic ID than its own one. In
such case it encapsulates the 'transfer topic' request inside the P2P
insert message. If this message is received by some other node, it
performs a standard topic transfer procedure. If the peer is already
participating in the topology structure, than it only omits creating
the new topic. If the distance between the topic ID and the peer ID
is lower than 0, than node assumes, that it is participating in an
unstructured network and cannot rely on the overlay routing
algorithm. In such case the neighbor cache's contents are examined.
If it does not provide any useful information or this node is the
first one on the list, the subscriber performs the lookup procedure
for the SUBSCRIPTIONINFO objects associated with the same topic. If
it finds any nodes with the ID lower than its own one, than it must
send the subscribe message to the one with the lowest ID. If there
are no such nodes in the P2P network, than it assumes that it is the
new topic root and waits for the other nodes to send 'subscribe'
requests to it. These procedures guarantee the cycles avoidance.
Moreover they work both for the multicast tree and star topology.
4.2.9 Reliability
[TODO: history of events for temporary out-of-order issues, but not
the long term ones - history length as algorithm parameter]
4.3 Message formats
All the message formats described in this section are used by the
default Customizable Algorithm component. However they MAY be
extended by the user-defined ones if it is necessary and registered
by a different Algorithm Configurator object. In general there are
three types of messages: requests, indications and responses. Node
receiving the first one always sends response to the message
originator. Both requests and responses contain the unique
Adamska, et al. Expires October 13, 2009 [Page 28]
Internet-Draft Publish-Subscribe May 2009
identifier of the transaction, they are associated with. It is
generated by the request originator, who uses it to find out, which
operation is received response related to. Indications are messages
which do not require any response as they are not associated with a
pending operation.
4.3.1 Standard header
Every publish-subscribe message is preceded by the following header:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|IPver| Source IP //
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | Destination IP //
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | Source port //
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | Destination port //
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | Type | //
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// Source user name length | //
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// Source user name |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source peer id length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source peer id //
+ +
// |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination user name length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination user name //
+ +
// |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination peer id length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination peer id //
+ +
// |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Topic id length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Topic id //
+ +
// |
Adamska, et al. Expires October 13, 2009 [Page 29]
Internet-Draft Publish-Subscribe May 2009
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
IP version (3 bits): IP version number, 4 or 6
Source IP (32 or 128 bits): IP address of message sender
Destination IP (32 or 128 bits): IP address of message receiver
Source port (32 bits): Message sender's port number
Destination port (32 bits): Message receiver's port number
Type (8 bits): Publish-subscribe message type
Source user name length (32 bits): Length of the user's unhashed id
Source user name (undefined): User's unhashed id
Source peer id length (32 bits): Length of the peer id
Source peer id (undefined): Peer id
Destination user name length (32 bits): Length of user's unhashed id
Destination user name (undefined): User's unhashed id
Destination peer id length (32 bits): Length of the peer id
Destination peer id (undefined): Peer id
Topic id length (32 bits): Length of the topic id this message is
associated with
Topic id (undefined): Topic id this message is associated
with
4.3.2 Standard request header
Apart from the type-specific information, every request contains the
following header:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Transaction id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Transaction id (32 bits): Identifier of the transaction this
operation is associated with
Adamska, et al. Expires October 13, 2009 [Page 30]
Internet-Draft Publish-Subscribe May 2009
4.3.3 Create topic
Create topic message can be send to actually create a new topic, or
to transfer an existing one to the new root. The node recognizes the
requested operation by checking the value of the special flag inside
the header.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| F | AC rules //
+-+-+ +
// |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Subscribers list length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Subscriber 1 //
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
F (2 bits): Flag representing the requested operation type. Currently
only two types are defined (figure 4.3.3.1).
AC rules (undefined): Access control rules defined for the topic (see
section 4.4.1 for details).
Subscriber list length (32 bits): Length of the list containing the
subscribers to be added after the
topic creation.
+------+-------------------------------------------------------+
|Value | Description |
+------+-------------------------------------------------------+
| 0 | Creates new topic |
| | |
| 1 | Transfers an existing topic to new root |
+------+-------------------------------------------------------+
Figure 4.3.3.1
4.3.4 Subscribe
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Expiration time //
+ +
// |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Event index |
Adamska, et al. Expires October 13, 2009 [Page 31]
Internet-Draft Publish-Subscribe May 2009
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Distance |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Expiration time (64 bits): Time, after which node will have to
resubscribe
Event index (32 bits): Index of the last received event from the
topic history
Distance (32 bits): Distance between the subscriber id and topic id
4.3.5 Unsubscribe
Currently there are no type-specific values for this message. It
contains only the standard request header.
4.3.6 Publish
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Event type | User name length //
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | User name //
+-+-+-+-+-+-+-+-+-+-+ +
// |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Event type (8 bits): Field indicating, whether this is the
REMOVE_TOPIC, AC_MODIFIED or CUSTOM event
User name length (32 bits): Length of the event publisher's name
User name (undefined): Event publisher's name
Message length (32 bits): Length of the message encapsulated in the
CUSTOM event
Message (undefined): User-defined message encapsulated in the CUSTOM
event or the modified AC rules
4.3.7 Notify
Adamska, et al. Expires October 13, 2009 [Page 32]
Internet-Draft Publish-Subscribe May 2009
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|H| Event type | User name length //
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | User name //
+-+-+-+-+-+-+-+-+-+-+-+-+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
H (1 bit): Flag indicating whether this event is the new one (value
MUST be 0 in this case), or the old one from the topic
history (value MUST be 1)
Event type (8 bits): Field indicating, whether this is a
REMOVE_TOPIC, AC_MODIFIED or CUSTOM event
User name length (32 bits): Length of the event publisher's name
User name (undefined): Event publisher's name
Message length (32 bits): Length of the message encapsulated in the
CUSTOM event
Message (undefined): Message encapsulated in the CUSTOM event
4.3.8 Standard response header
Every response, except the response code, contains a unique
transaction identifier. The request originator uses it, to find out
which operation this response is related to.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Transaction number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Response code |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Transaction number (32 bits): Identifier of the transaction, this
response is associated with
Response code (32 bits): Response codes are described in section 4.7
Adamska, et al. Expires October 13, 2009 [Page 33]
Internet-Draft Publish-Subscribe May 2009
4.3.9 Subscribe response
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| AC rules //
+ +
// |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
AC rules (undefined): AC rules encoding is described in section 4.4.1
4.3.10 Keep-alive
Parent (undefined): Subscriber object containing node's parent in
the topology structure
Neighbors (undefined): List of the subscriber objects to put into the
neighbors cache. Its length depends on the k
parameter.
Parents (undefined): List of the subscriber objects to put into the
parents cache. Its length depends on the k
parameter.
Grandparents (undefined): List of the subscriber objects to put into
the grandparents cache. Its length depends
on the g parameter.
4.4 Objects formats
4.4.1 AC rules
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| List of rules length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| List of rules //
+ +
// |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
List of rules length (32 bits): Number of the rules on the list
List of rules (undefined): List of the AC rules (see section 4.4.2
for details)
Adamska, et al. Expires October 13, 2009 [Page 34]
Internet-Draft Publish-Subscribe May 2009
4.4.2 Rule
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Operation byte length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Operation //
+ +
// |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Event type | Allowed users list length //
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | User byte length //
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
// | User //
+-+-+-+-+-+-+-+-+-+-+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| User 2 byte length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ..... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Event type 2 | .... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Operation (undefined): Operation, this rule is associated with
Event type (8 bits): Particular event within an operation (at least
one event is mandatory)
User (undefined): User allowed to perform specified operation
4.4.3 Operation
0
0 1 2 3 4 5 6 7 8 9
+-+-+-+-+-+-+-+-+-+-+
| Operation type |
+-+-+-+-+-+-+-+-+-+-+
Operation type (8 bits): Type of an operation, this rule is
associated with. Currently defined values
correspond with the message types
(from 1 to 6) described in section 4.5.
4.4.4 User
Adamska, et al. Expires October 13, 2009 [Page 35]
Internet-Draft Publish-Subscribe May 2009
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Username byte length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Username //
+ +
// |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
4.4.5 Subscriber
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Username byte length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Username //
+ +
// |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Peer id byte length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Peer id //
+ +
// |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IP address byte length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IP address //
+ +
// |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Port number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
4.5 Message types
+------+-------------------------+-----------------------------+
|Value | Message type | Indication/Request/Response |
+------+-------------------------+-----------------------------+
| 0 | Standard response | Res |
| | | |
| 1 | Create topic | Req |
| | | |
| 2 | Subscribe | Req |
| | | |
| 3 | Unsubscribe | Req |
| | | |
| 4 | Publish | Req |
Adamska, et al. Expires October 13, 2009 [Page 36]
Internet-Draft Publish-Subscribe May 2009
| | | |
| 5 | Notify | Ind |
| | | |
| 6 | Keep-alive | Ind |
+------+-------------------------+-----------------------------+
4.6 Event types
+------+--------------------------------------------------+
| Type | Description |
+------+--------------------------------------------------+
| 0 | Topic removed |
| | |
| 1 | Access Control Rules modified |
| | |
| 2 | Custom event defined by higher-layer application |
| | |
+------+--------------------------------------------------+
4.7 Response codes
Response codes are inspired from HTTP.
+------+-------------------------------------------------------+
|Code | Description |
+------+-------------------------------------------------------+
| 200 | Operation successful |
| | |
| 403 | Operation forbidden due to AC rules |
| | |
| 404 | Operation cannot be completed, because the topic or |
| | subscriber it is associated with does not exist |
| | |
| 409 | Create topic operation cannot be completed because |
| | the specified topic already exists |
| | |
+------+-------------------------------------------------------+
4.8 Security
[TODO: Verifying user identity for AC rules, etc.]
5. Integrating publish-subscribe with P2PP/RELOAD
5.1 Extending P2PP/RELOAD interfaces
Adamska, et al. Expires October 13, 2009 [Page 37]
Internet-Draft Publish-Subscribe May 2009
There are several major differences between some of the P2PP and
RELOAD requests, we had to consider. P2PP publish allows application
to insert only one object per request. Single RELOAD store request
MAY contain several objects with the same resource-id, but different
kind-id's or data models. It is the same with the P2PP lookup and
RELOAD fetch requests. To provide the generic interfaces for both
protocols we decided to use object lists, not single objects in all
callbacks associated with the requests processing. Due to the
terminology differences between both protocols we use 'insert' for
the P2PP publish, and RELOAD store request, and 'lookup' for the P2PP
lookup and RELOAD fetch request where distinguishing one from another
is not essential.
5.1.1 Callbacks
We propose adding several callback methods to the P2PP/RELOAD
interfaces. They can be used by applications built on top of it not
only for gathering information about the received messages, but also
for passing data to the overlay layer. Parameters marked as [in] are
the ones that are passed to the higher layer by P2PP/RELOAD. These
marked as [out] are returned to the overlay by the application layer.
[TODO: Decide what about applications which do not want to use
callbacks - default implementation returning true shouldn't be a
problem, when performance is considered]
[TODO: Decide, whether signature/certificate checking should be
performed before or after the callback invocation (in the second case
application layer would have to update the object's signature) and
whether to invoke callbacks for example if the RELOAD layer already
knows that the signature is invalid]
boolean onDeliverRequest([in]Request message,
[in/out]List<GeneralObject> objectList)
@param message Received P2PP/RELOAD request.
@param objectList Value interpretation is message type dependent.
@return Value interpretation is message type dependent. In general
'true' means 'continue standard processing', and 'false'
means 'perform custom operation'.
Usually invoked directly after receiving a request and determining
that this node is message destination. In case of lookup requests -
after searching for the objects in the peer's resource table
(figure 5.1.1.1). If node stores the requested objects there, they
are passed to the higher layer using 'objectList' parameter.
Higher-layer application may decide to send these objects within the
lookup response, or pass a different ones using the same parameter.
Adamska, et al. Expires October 13, 2009 [Page 38]
Internet-Draft Publish-Subscribe May 2009
After the callback invocation P2PP/RELOAD checks the returned value.
If this value is 'true' it simply returns objects found in the
resource table in response (or 'NOT FOUND' message if none of the
requested objects is stored there). Otherwise response message
contents depend on the second callback parameter's value (objects
defined by higher layer are returned to the request originator). This
MAY be used by the application built on top of P2PP/RELOAD for
example to create different 'views' of the node's resource table,
depending on the lookup request originator. Higher layer MAY hide
object's value from some users or send different values to them.
Similar procedure is performed after receiving an insert request
(figure 5.1.1.2) although returned value interpretation is slightly
different. When this value is 'true', objects encapsulated inside the
insert request are simply put into the peer's resource table.
Otherwise either different objects are inserted or only P2PP/RELOAD
response is sent.
For both insert and lookup requests application layer MAY modify
object list elements' values or replace them with null. It MUST NOT
modify resource id, type or data model. For all the request types it
also MUST NOT alter the object list size.
Message
Receiver Originator
+------------------------------------------------+ +------+
| | | |
| RELOAD/| |RELOAD|
| Application P2PP | lookup |/P2PP |
| | | | request | | |
| | |<-----------------| |
| | 1. Fill object | | | | |
| | list (if | | | | |
| | some | | | | |
| | requested | | | | |
| | object isn't| | | | |
| | stored here | | | | |
| | - add null | | | | |
| | at this | | | | |
| | position) | | | | |
| | | | | | |
| | onDeliverRequest | | | | |
| | (request, objects)| | | | |
| |<-----------------------| | | | |
| | | | | | |
| 1. continue | | | | | |
| standard | true, objects | | | | |
| processing |----------------------->| | | | |
| | | | | | |
| | 1. return | | | | |
| | standard | | | | |
Adamska, et al. Expires October 13, 2009 [Page 39]
Internet-Draft Publish-Subscribe May 2009
| | response | | | | |
| | containing | | | | |
| | objects | | | | |
| | found in | | standard | | |
| | resource | | response | | |
| | table |----------------->| |
| | 2. finished | | | | |
| | | | | | |
| | | | | | |
| 1'. modify object | | | | | |
| list (if any | | | | | |
| of stored | | | | | |
| objects needs | | | | | |
| to be hidden | | | | | |
| from lookup | | | | | |
| request | | | | | |
| originator | | | | | |
| - set it to | | | | | |
| null) | | | modified | | |
| | false, modifiedObjects | | response | | |
| |----------------------->|----------------->| |
| | | | | | |
| | | | | | |
| | | |
+------------------------------------------------+ +------+
Figure 5.1.1.1: Node receives lookup request
Message
Receiver Originator
+------------------------------------------------+ +------+
| | | |
| RELOAD/| |RELOAD|
| Application P2PP | insert |/P2PP |
| | | | request | | |
| | |<-----------------| |
| | 1. Fill object | | | | |
| | list with | | | | |
| | values from | | | | |
| | resource | | | | |
| | table (if | | | | |
| | object with | | | | |
| | specified | | | | |
| | key and of | | | | |
| | specified | | | | |
| | type isn't | | | | |
| | already | | | | |
| | stored here | | | | |
| | - add null | | | | |
| | at this | | | | |
Adamska, et al. Expires October 13, 2009 [Page 40]
Internet-Draft Publish-Subscribe May 2009
| | position) | | | | |
| | | | | | |
| | onDeliverRequest | | | | |
| | (request, objects)| | | | |
| |<-----------------------| | | | |
| | | | | | |
| 1. continue | | | | | |
| standard | true, objects | | | | |
| processing |----------------------->| | | | |
| | | | | | |
| | 1. insert all | | | | |
| | objects from| | | | |
| | request into| | insert | | |
| | resource | | response | | |
| | table |----------------->| |
| | 2. finished | | | | |
| | | | | | |
| 1'. modify object | | | | | |
| list | false, modifiedObjects | | | | |
| |----------------------->| | | | |
| | 1. for each | | | | |
| | element on | | | | |
| | the list if | | | | |
| | it is not | | | | |
| | null insert | | | | |
| | it into | | insert | | |
| | resource | | response | | |
| | table |----------------->| |
| | | | | | |
| | | | | | |
| | | |
+------------------------------------------------+ +------+
Figure 5.1.1.2: Node receives insert request
boolean onForwardingRequest([in]Request message,
[in/out]List<GeneralObject> objectList)
@param message Received P2PP/RELOAD request.
@param objectList Value interpretation is message type dependent.
@return Value indicating, whether to forward or discard the message.
In case of discarding - node has to send P2PP response.
Otherwise request sender will try to retransmit its message
and finally assume unresponsive peer's failure.
Usually invoked directly after receiving a P2PP request (and
determining that this node is not the message destination), before
forwarding it to other node or sending 302 response. In case of
lookup requests (figure 5.1.1.3) - after checking, if the requested
object is not for example cached (or replicated) here. If such object
Adamska, et al. Expires October 13, 2009 [Page 41]
Internet-Draft Publish-Subscribe May 2009
is found, P2PP/RELOAD passes it to the higher layer using the
'objectList' parameter. Higher-layer application may decide to send
this object within the P2PP lookup response, or pass a different one
using the same parameter. After the callback invocation P2PP/RELOAD
checks the returned value. If this value is 'true' it simply forwards
the message or returns the cached/replicated objects in a standard
response. Otherwise the message is discarded, and P2PP/RELOAD
response containing objects defined by the higher layer is sent.
Figure 5.1.1.4 shows the procedure performed in case of receiving
insert request. If the returned value is 'true', the message is
forwarded. Otherwise node discards the message and sends insert
response to its originator.
For both insert and lookup requests application layer MAY modify the
object list elements' values or replace them with null. It MUST NOT
modify the resource id, type or data model. For all request types it
also MUST NOT alter the object list size.
Message
Receiver Originator
+------------------------------------------------+ +------+
| | | |
| RELOAD/| |RELOAD|
| Application P2PP | lookup |/P2PP |
| | | | request | | |
| | |<----------------| |
| | 1. Fill object | | | | |
| | list (if | | | | |
| | some | | | | |
| | requested | | | | |
| | object isn't| | | | |
| | replicated/ | | | | |
| | cached here | | | | |
| | - add null | | | | |
| | at this | | | | |
| | position) | | | | |
| | | | | | |
| | onDeliverRequest | | | | |
| | (request, objects)| | | | |
| |<-----------------------| | | | |
| | | | | | |
| 1. continue | | | | | |
| standard | true, objects | | | | |
| processing |----------------------->| | | | |
| | | | | | |
| | 1. return | | | | |
| | standard | | | | |
| | response | | | | |
| | containing | | | | |
| | replicated/ | | | | |
Adamska, et al. Expires October 13, 2009 [Page 42]
Internet-Draft Publish-Subscribe May 2009
| | cached | | | | |
| | objects, | | | | |
| | forward the | | | | |
| | message or | | | | |
| | send | | standard | | |
| | redirect | | response | | |
| | response |---------------->| |
| | 2. finished | | | | |
| | | | | | |
| | | | | | |
| 1'. modify object | | | | | |
| list (if any | | | | | |
| of stored | | | | | |
| objects needs | | | | | |
| to be hidden | | | | | |
| from lookup | | | | | |
| request | | | | | |
| originator | | | | | |
| - set it to | | | | | |
| null) | | | | | |
| | false, modifiedObjects | | | | |
| |----------------------->| | | | |
| | 1. send | | | | |
| | response | | | | |
| | containing | | modified | | |
| | modified | | response | | |
| | objects |---------------->| |
| | 2. finished | | | | |
| | | | | | |
| | | |
+------------------------------------------------+ +------+
Figure 5.1.1.3: Node receives lookup request
Message
Receiver Originator
+-------------------------------------------+ +------+
| | | |
| RELOAD/| |RELOAD|
| Application P2PP | insert |/P2PP |
| | | | request | | |
| | |<----------------------| |
| | 1. Fill object | | | | |
| | list with | | | | |
| | replicated/ | | | | |
| | cached | | | | |
| | objects (if | | | | |
| | object with | | | | |
| | specified | | | | |
| | key and of | | | | |
| | specified | | | | |
Adamska, et al. Expires October 13, 2009 [Page 43]
Internet-Draft Publish-Subscribe May 2009
| | type isn't | | | | |
| | replicated/ | | | | |
| | cached here | | | | |
| | - add null | | | | |
| | at this | | | | |
| | position) | | | | |
| | | | | | |
| | onDeliverRequest | | | | |
| | (request, objects)| | | | |
| |<-----------------------| | | | |
| | | | | | |
| 1. continue | | | | | |
| standard | true, objects | | | | |
| processing|----------------------->| | | | |
| | | | | | |
| | 1. forward the | | | | |
| | message or | | | | |
| | send | | standard | | |
| | redirect | | response | | |
| | response |---------------------->| |
| | 2. finished | | | | |
| | | | | | |
| 1'. modify | | | | | |
| object | false, modifiedObjects | | | | |
| list |----------------------->| | | | |
| | 1. for each | | | | |
| | element on | | | | |
| | the list if | | | | |
| | it is not | | | | |
| | null update | | | | |
| | replicated/ | | | | |
| | cached | | | | |
| | object | | insert | | |
| | | | response | | |
| | |---------------------->| |
| | | | | | |
| | | | | | |
| | | |
+-------------------------------------------+ +------+
Figure 5.1.1.4: Node receives insert request
boolean onDeliverResponse([in]Response message)
@param message P2PP/RELOAD response.
@return Value indicating whether to continue the standard P2PP/RELOAD
processing or not.
Invoked after receiving P2PP/RELOAD response. The returned value
interpretation is operation type dependent. For instance if it is
Adamska, et al. Expires October 13, 2009 [Page 44]
Internet-Draft Publish-Subscribe May 2009
'false' for the insert response, it means, that the specified object
MUST NOT be republished. This is useful, if it was only used to
encapsulate some higher-layer-defined message.
void onNeighborJoin(PeerInfo newNode, int nodeType)
@param newNode Object containing such information as ID, IP address,
and port number.
@param nodeType Value indicating, whether new node is a client, peer,
peer acting as bootstrap server, etc.
Invoked after accepting other node's join request and successfully
sending OK reply to it (figure 5.1.1.5).
Node accepting
join request New node
+-----------------------------+ +------+
| | | |
| RELOAD/| |RELOAD|
| Application P2PP | |/P2PP |
| | | | JoinRequest | | |
| | |<--------------------------| |
| | | | | | |
| | | | OK | | |
| | |-------------------------->| |
| | onNeighborJoin | | | | |
| |<-----------------| | | | |
| | | | | | |
| | | |
+-----------------------------+ +------+
Figure 5.1.1.5
void onNeighborLeave(PeerInfo removedNode, int nodeType)
@param removedNode Object containing such information as ID, IP
address, and port number.
@param nodeType Value indicating, whether new node is client, peer,
peer acting as bootstrap server, etc.
Invoked after removing a neighbor from the neighbor table.
5.1.2 Objects
We propose creating a MESSAGE object type. This object could be used
by the higher-layer applications to encapsulate its own messages
Adamska, et al. Expires October 13, 2009 [Page 45]
Internet-Draft Publish-Subscribe May 2009
within an insert request and make use of the overlay-specific
routing. In the DHT-based networks this enables sending a message
even if the exact destination's peer ID is unknown (we only know,
that it should be the closest one to some given object key). It also
guarantees that the message will not be routed to clients (as they
are not responsible for storing objects).
This object for P2PP could be described as follows:
Type: MESSAGE
Subtype: value indicating protocol
Message: raw message bytes
Below we propose the MESSAGE object's format using RELOAD semantics:
Kind-Id: MESSAGE
Data Model: single value
Value: value indicating protocol
raw message bytes
The received MESSAGE objects do not necessarily have to be stored in
the resource tables. Application built on top of P2PP/RELOAD MAY
prevent it by capturing insert messages containing such objects using
previously described callbacks and making overlay layer discard them.
After that, the request originator SHOULD also use the previously
described onDeliverResponse callback to prevent P2PP/RELOAD layer
from republishing the object and thus resending the higher-layer
message encapsulated in it.
5.1.3 API
We propose adding a method for calculating distance between the two
given keys according to the overlay-specific metrics and hash
algorithm. In our algorithm we use it for creating and maintaining
the topology structure. This method could be defined as follows:
int getDistance(String key1, String key2)
@param key1, key2 Method calculates the distance between these keys.
@return In the DHT-based networks returned value is greater or equal
to 0. In unstructured ones method always returns -1.
Publish-subscribe protocols built on top of the unstructured
overlays, based for instance on random walks, may also require access
to the routing information. This is why we propose two methods that
provide it:
Adamska, et al. Expires October 13, 2009 [Page 46]
Internet-Draft Publish-Subscribe May 2009
RoutingTable getRoutingTable()
@return Node's routing table.
NeighborTable getNeighborTable()
@return Node's neighbor table.
5.2 Usage of the extension
5.2.1 Objects
Apart from the generic MESSAGE object we also propose to add one
publish-subscribe-specific type called SUBSCRIPTIONINFO. It will be
placed in network to inform other nodes about the topic existence,
and help them join the multicast tree. This is essential for the
unstructured overlays.
For P2PP this object can be defined as follows:
Type = SUBSCRIPTIONINFO
Status = PENDING/ACCEPTED
Peer = PeerInfo object containing peer ID, IP address and port number
for the incoming publish-subscribe messages.
Below we propose the SUBSCRIPTIONINFO object's format using RELOAD
semantics:
Kind-Id: SUBSCRIPTIONINFO
Data Model: single value
Value: status = PENDING/ACCEPTED
peer = PeerInfo object containing peer ID, IP address and port
number for the incoming publish-subscribe messages.
When node wants to subscribe for some topic, it performs lookup for
the SUBSCRIPTIONINFO object (giving the topic ID as a key).
6. Future work
We plan to provide event metadata to extend the default Interest
Conditions and support advanced filters for the content-based
multicast.
7. IANA Considerations
Adamska, et al. Expires October 13, 2009 [Page 47]
Internet-Draft Publish-Subscribe May 2009
This document has no actions for IANA.
8. References
8.1 Normative references
[1] S. Baset, H. Schulzrinne and M. Matuszewski, "Peer-to-Peer
Protocol(P2PP)", draft-baset-p2psip-p2pp-01 (work in progress),
November 19, 2007.
[2] C. Jennings, B. Lowekamp, E. Rescorla, S. Baset and H.
Schulzrinne, "REsource LOcation And Discovery (RELOAD)",
draft-ietf-p2psip-reload-00 (work in progress), July 11, 2008.
[3] S. Bradner, "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997.
8.2 Informative references
[4] P. Maymounkov and D. Mazieres, "Kademlia: A peer-to-peer
information system based on the xor metric," Peer-To-Peer
Systems: First International Workshop, IPTPS 2002, Cambridge, MA,
USA, March 7-8, 2002: Revised Papers, 2002.
[5] S. Ratnasamy, M. Handley, R. M. Karp, and S. Shenker,
"Application-level multicast using content-addressable networks."
in Networked Group Communication, ser. Lecture Notes inComputer
Science, J. Crowcroft and M. Hofmann, Eds., vol.2233. Springer,
2001, pp. 14-29.
[6] A. Rowstron and P. Druschel, "Pastry: Scalable, distributed
object location and routing for large-scale peer-to-peer
systems," in Proc. Of the International Conference on
Distributed Systems platforms(Middleware), 2001.
[7] A.I.T. Rowstron, A-M. Kermarrec, M. Castro, and P. Druschel,
"Scribe: The design of a large-scale event notification
infrastructure." vol. 2233, pp. 30-43, 2001.
[8] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H.
Balakrishnan, "Chord: A scalable peer-to-peer lookup service for
internet applications," in SIGCOMM'01: Proceedings of the 2001
conference on Applications, technologies, architectures, and
protocols for computer communications. New York, NY, USA: ACM,
2001, pp. 149-160.
[9] Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker,
"Making gnutella-like p2p systems scalable," in SIGCOMM'03:
Proceedings of the 2003 conference on Applications, technologies,
Adamska, et al. Expires October 13, 2009 [Page 48]
Internet-Draft Publish-Subscribe May 2009
architectures, and protocols for computer communications.
New York, NY, USA: ACM, 2003, pp. 407-418
Authors' Addresses
Paulina Adamska
Dept. of Computer Networks
Polish-Japanese Institute of Information Technology
Koszykowa 86,
02-008 Warsaw
Poland
Email: tiia@pjwstk.edu.pl
Adam Wierzbicki
Dept. of Computer Networks
Polish-Japanese Institute of Information Technology
Koszykowa 86,
02-008 Warsaw
Poland
Email: adamw@pjwstk.edu.pl
Tomasz Kaszuba
Dept. of Computer Networks
Polish-Japanese Institute of Information Technology
Koszykowa 86,
02-008 Warsaw
Poland
Email: kaszubat@pjwstk.edu.pl