idnits 2.17.1 draft-paulina-p2psip-pubsub-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.ii or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. See https://trustee.ietf.org/license-info/.) Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- == There are 33 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (May 13, 2009) is 5463 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: '4' is defined on line 2296, but no explicit reference was found in the text == Unused Reference: '5' is defined on line 2301, but no explicit reference was found in the text == Unused Reference: '6' is defined on line 2307, but no explicit reference was found in the text == Unused Reference: '7' is defined on line 2312, but no explicit reference was found in the text == Unused Reference: '8' is defined on line 2316, but no explicit reference was found in the text == Unused Reference: '9' is defined on line 2323, but no explicit reference was found in the text Summary: 1 error (**), 0 flaws (~~), 8 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group P. Adamska 2 Internet-Draft A. Wierzbicki 3 Intended status: Standards Track T. Kaszuba 4 Expires: 13 October, 2009 PJIIT 5 May 13, 2009 7 Publish-subscribe over the generic Peer-to-Peer Protocols 8 draft-paulina-p2psip-pubsub-00 10 Status of this Memo 12 This Internet-Draft is submitted to IETF in full conformance with the 13 provisions of BCP 78 and BCP 79. 15 Internet-Drafts are working documents of the Internet Engineering 16 Task Force (IETF), its areas, and its working groups. Note that 17 other groups may also distribute working documents as Internet- 18 Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet-Drafts as reference 23 material or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt. 28 The list of Internet-Draft Shadow Directories can be accessed at 29 http://www.ietf.org/shadow.html. 31 This Internet-Draft will expire on October, 2009. 33 Copyright Notice 35 Copyright (c) 2009 IETF Trust and the persons identified as the 36 document authors. All rights reserved. 38 This document is subject to BCP 78 and the IETF Trust's Legal 39 Provisions Relating to IETF Documents in effect on the date of 40 publication of this document (http://trustee.ietf.org/license-info). 41 Please review these documents carefully, as they describe your rights 42 and restrictions with respect to this document. 44 Abstract 46 This document introduces a generic publish-subscribe protocol, that 47 can be built on top of RELOAD or P2PP. It works both for the 48 unstructured and DHT-based Peer-to-Peer networks. Moreover it is 49 highly customizable to address the optimization issues and support 50 different topology structures. It can be used to implement P2P-SIP 51 services such as presence or event notification. 53 Table of contents 55 1. Introduction...................................................2 56 2. Terminology....................................................2 57 3. Architecture...................................................3 58 3.1 Overview...................................................3 59 3.2 Publish-subscribe transport................................4 60 3.3 Core Algorithm.............................................4 61 3.4 Customizable Algorithm.....................................6 62 3.5 Topology Manager...........................................6 63 3.6 Publish-Subscribe API......................................8 64 3.6.1 Publish-Subscribe Interface...........................8 65 3.6.2 Publish-Subscribe Callbacks...........................9 66 4. Publish-Subscribe Protocol....................................10 67 4.1 General information.......................................10 68 4.1.1 Topic................................................10 69 4.1.2 Subscriber...........................................11 70 4.1.3 Subscription.........................................11 71 4.1.4 Event................................................12 72 4.1.5 Interest conditions..................................12 73 4.1.6 Access control rules.................................13 74 4.2 Default Customizable Algorithm............................14 75 4.2.1 Create topic.........................................14 76 4.2.2 Transfer topic.......................................16 77 4.2.3 Remove topic.........................................19 78 4.2.4 Subscribe............................................19 79 4.2.5 Unsubscribe..........................................20 80 4.2.6 Publish..............................................22 81 4.2.7 Notify...............................................22 82 4.2.8 Maintenance..........................................23 83 4.2.9 Reliability..........................................26 84 4.3 Message formats...........................................26 85 4.3.1 Standard header......................................27 86 4.3.2 Standard request header..............................28 87 4.3.3 Create topic.........................................29 88 4.3.4 Subscribe............................................29 89 4.3.5 Unsubscribe..........................................30 90 4.3.6 Publish..............................................30 91 4.3.7 Notify...............................................30 92 4.3.8 Standard response header.............................31 93 4.3.9 Subscribe response...................................31 94 4.3.10 Keep-alive..........................................32 95 4.4 Objects formats...........................................32 96 4.4.1 AC rules.............................................32 97 4.4.2 Rule.................................................32 98 4.4.3 Operation............................................33 99 4.4.4 User.................................................33 100 4.4.5 Subscriber...........................................34 101 4.5 Message types.............................................34 102 4.6 Event types...............................................35 103 4.7 Response codes............................................35 104 4.8 Security..................................................35 106 5. Integrating publish-subscribe with P2PP/RELOAD................35 107 5.1 Extending P2PP/RELOAD interfaces..........................35 108 5.1.1 Callbacks............................................36 109 5.1.2 Objects..............................................43 110 5.1.3 API..................................................44 111 5.2 Usage of the extension....................................44 112 5.2.1 Objects..............................................44 113 6. Future work...................................................45 114 7. IANA Considerations...........................................45 115 8. References....................................................45 116 8.1 Normative references......................................45 117 8.2 Informative references....................................45 118 Authors' Addresses...............................................46 120 1. Introduction 122 The publish-subscribe protocol described in this paper is built on 123 top of the generic P2P protocols such as RELOAD[1] and P2PP[2]. It 124 may exchange messages both directly between the specified peers or 125 by encapsulating them in the resource objects and sending inside 126 the P2P insert request. A set of callback methods has been defined 127 to let the publish-subscribe layer capture the incoming P2P requests, 128 process them and modify the default P2P protocol behavior if it is 129 necessary. In this document we describe the generic protocol, that 130 works both for the unstructured and DHT-based P2P networks. It can 131 be easily configured to optimize its behavior using the 132 overlay-specific features or simply replaced by a set of different 133 algorithms for the various P2P networks. Both operations are 134 completely transparent for the higher-layer applications and 135 topology-independent. Additionally we also define the Access Control 136 Rules (AC), which allows higher-layer application to let some of the 137 users subscribe for the specified topic without granting them 138 permission to generate events. These rules are stored by all the 139 topic subscribers, as they can be responsible for accepting other 140 nodes' requests. The proposed publish-subscribe protocol also 141 provides so called Interest Conditions (IC) which can be used as a 142 simple filter for the received events. Each node can define the 143 group of users generating interesting events. Each node also stores 144 a certain number of events, that have recently been published for 145 the topic. The new subscriber may ask for sending some or all of 146 them after the successful subscription process. Nodes may also store 147 a configurable number of the 'backup nodes' in the special caches, 148 to use them in case of the direct parent's failure. 150 2. Terminology 152 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 153 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 154 document are to be interpreted as described in RFC 2119 [3]. 156 Some of the terminology has been borrowed from the P2PP[1] and 157 RELOAD[2] drafts. 159 Topic owner: The node which has created the topic. 161 Topic root: A non-leaf node in the topology structure - indirect 162 parent for all the other nodes. It MAY be a topic 163 subscriber or not. In the DHT-based overlays, it 164 will be the peer with id numerically closest to the 165 topic identifier. 167 Topic history: Every node participating in the topology structure, 168 that is able to accept new subscribers (which means 169 it is a peer, not client) stores the list of the 170 events that have recently been published for the 171 specified topic. During the subscription process 172 node can ask its parent to send some, or all of 173 them. History only refers to the custom events, not 174 the predefined ones, such as AC_MODIFIED. 176 Topic cache: The backup list of nodes participating in the topology 177 structure which is used in case of detecting the 178 direct parent's failure. There may be several types of 179 caches stored be a single node. 181 3. Architecture 183 3.1 Overview 185 To provide a generic and highly extensible publish-subscribe 186 mechanism we decided to split it, as it is shown in the figure 187 3.1.1. The arrows illustrate the communication between the 188 various components of the publish-subscribe layer. 190 +---------------------------------------------------------------------+ 191 | Publish-Subscribe API | 192 | +-----------------------------+ +-----------------------------+ | 193 | | Publish-Subscribe Callbacks | | Publish-Subscribe Interface | | 194 | +-----------------------------+ +-----------------------------+ | 195 | ^ ^ | | 196 +-----------|---------|---------------------------------|-------------+ 197 | +------------------------+ | 198 +----------------------+ | | 199 | | v 200 +-------------------------------+ | +-------------------------------+ 201 | Topology Manager | | | Customizable Algorithm | 202 +-------------------------------+ | +-------------------------------+ 203 ^ | ^ 204 | | | 205 v | v 206 +---------------------------------------------------------------------+ 207 | Core Algorithm | 208 | +-----------------------------------------------------------------+ | 209 | | Algorithm Configurator | | 210 | +-----------------------------------------------------------------+ | 211 +---------------------------------------------------------------------+ 212 ^ 213 | 214 v 215 +---------------------------------------------------------------------+ 216 | Publish-Subscribe Transport | 217 | +-----------------------------+ +-----------------------------+ | 218 | | RELOAD/P2PP Transport | | Direct Transport | | 219 | +-----------------------------+ +-----------------------------+ | 220 +---------------------------------------------------------------------+ 221 Figure 3.1.1: Publish-subscribe layer architecture 223 The following sections provide the detailed description of the most 224 important components of the publish-subscribe layer. 226 3.2 Publish-subscribe transport 228 This component is directly responsible for the communication. It 229 passes the incoming publish-subscribe messages to the Core Algorithm 230 and sends the outgoing ones. It hides the details of the sending 231 procedure - for example encapsulates a publish-subscribe message 232 inside the network resource object if it is to be sent within the 233 P2P insert request. All the publish-subscribe requests may be routed 234 either directly to some specified node, or using the overlay-specific 235 algorithm. The second method is chosen, when the exact destination is 236 not defined - for example to determine the root during the topic 237 creation procedure in a DHT-based network. Indications and responses 238 are always passed directly to a specified node. 240 [TODO: Perhaps for the direct connections publish-subscribe 241 use RELOAD's Attach() - as it was described in the SIP Usage] 243 3.3 Core Algorithm 245 This component provides the core features of the publish-subscribe 246 layer which are to be common for all the Customizable Algorithms. 247 All the incoming messages are passed directly to this component. It 248 checks whether it stores information about the specified topic (or 249 does not store - for the create topic request) and whether the 250 message originator is allowed to perform a certain operation. If 251 both requirements are fulfilled, it passes the message to the 252 Customizable Algorithm or the Topology Manager. Otherwise it sends 253 the response with an appropriate error code to the request 254 originator itself. It is also responsible for forwarding the events 255 notifications to the node's children and checking IC, before 256 passing them to the higher-layer application. Probably the most 257 interesting feature of this component is its ability to query the 258 P2P layer for the overlay type and dynamically load the appropriate 259 algorithm with the suitable configuration. This can be achieved by 260 defining a separate Algorithm Configurator that is used by the Core 261 Algorithm to create an appropriate Customizable Algorithm object. 262 The choice of the suitable component is made on the basis of the 263 underlying P2P network type. This object is also able to configure 264 such parameters as the size of the caches. Caches store the lists 265 of the 'backup nodes' to be used in case of detecting the direct 266 parent's failure. Each node may store several types of such lists, 267 for example associated with different levels of the multicast 268 tree. The decision on the number of caches depends on the 269 Customizable Algorithm component's policy. Each parent is 270 responsible for filling its children's caches by periodically 271 sending them keep-alive messages containing the appropriate lists 272 of nodes. Storing such information is essential in the 273 unstructured networks. However it may not be crucial in the 274 DHT-based ones, where the topology structure can be repaired at a 275 relatively low cost using the overlay-specific routing algorithm, 276 without performing the complex lookup procedures. In such case 277 the Algorithm Configurator may set the cache size to 0 and treat 278 event notifications as a heartbeat messages to reduce the additional 279 traffic associated with the structure maintenance. Moreover, if some 280 new Customizable Algorithm requires sending any additional 281 information in a standard publish-subscribe message - it can 282 register this extended message format to make the Core Algorithm 283 load it instead of the standard message object after receiving the 284 specified request. For example the default Customizable Algorithm 285 stores the information about the Interest Conditions locally, but 286 some different algorithm may choose to built the IC-based multicast 287 tree, where the child's IC are the subset of its parent's IC. This 288 requires adding the information about the IC to the standard 289 subscribe request. Such extended message can be registered using 290 the Algorithm Configurator. Figure 3.3.1 illustrates the usage of 291 this component. 293 +----------------------------------------------------+----------------+ 294 | | Core Algorithm | 295 | +----------------+ 296 | | 297 +---------------------------------------------------------------------+ 298 | ^ 299 | chord-128-2-16+ | Customizable Algorithm 300 | | 301 v | 302 +--------------------------------------------+------------------------+ 303 | | Algorithm Configurator | 304 | +------------------------+ 305 | | 306 | 1. Create the appropriate Customizable Algorithm object | 307 | 2. Configure the object | 308 | 3. Register the messages for all the publish-subscribe operations | 309 | | 310 +---------------------------------------------------------------------+ 311 Figure 3.3.1: Usage of the Algorithm Configurator component 313 3.4 Customizable Algorithm 315 This component implements all the methods from the Publish-Subscribe 316 Interface and takes care of the processing of most of them. For 317 instance the create topic operation requires performing different 318 procedures in the DTH-based and unstructured overlays. In the first 319 case it is enough to encapsulate the create topic request inside the 320 P2P insert request, giving the topic identifier as an object key. 321 The unstructured networks require performing the lookup procedure to 322 ensure that some other node has not created the specified topic 323 before. It is also necessary to place the SUBSCRIPTIONINFO objects 324 in the P2P network to inform other nodes about the existing 325 participants of the topology structure created for the particular 326 topic. Additionally in the DHT-based networks transferring certain 327 topics to the new root may be necessary, if some new node joins the 328 P2P network and its ID is closer to the topic ID according to the 329 overlay-specific distance metrics. The Customizable Algorithm 330 component also takes part in the topology structure creation 331 process - this feature is described in details in the next section. 333 3.5 Topology Manager 335 This component is responsible for creating and maintaining the 336 specified topology structure. It handles all the subscribe requests 337 and takes part in the topic transfers. Currently there are two 338 structures defined: star and multicast tree. For the first one, 339 topology manager only ensures, that none of the nodes except the 340 topic root accepts new subscribers. The situation is slightly more 341 complex for the multicast trees. For instance the Customizable 342 Algorithm component may require creating IC-based trees. Then the 343 node, receiving a subscribe request, must check whether the new 344 subscriber's IC are the subset of its own ones. If it is not - it 345 has to forward the request to the higher level of the multicast 346 tree because it will not be receiving all the events that are 347 interesting to the new subscriber. In such cases Topology Manager 348 must consult the Customizable Algorithm component to identify the 349 next hop for forwarding the subscribe request. Figure 3.5.1 350 illustrates the subscribe procedure that uses the described 351 mechanism. Figure 3.5.2 shows the structure that does not apply 352 any additional rules for accepting the new subscribers. In this 353 case the marked node B may not be receiving all the interesting 354 events. 356 (a) +------------+ (b) +------------+ 357 | Root | | Root | 358 | IC={1,2,3} |-+ | IC={1,2,3} | 359 +------------+ | +------------+ 360 ^ | | / \ 361 subscribe | | | / \ 362 | | | / \ 363 | | | / \ 364 subscribe +------------+ | +------------+ +------------+ 365 +---------->| A | | | B | | A | 366 | | IC={1,2} | | | IC={2,3} | | IC={1,2} | 367 +------------+ +------------+ | +------------+ +------------+ 368 | B | | 369 | IC={2,3} |<--------------------+ 370 +------------+ subscriber accepted 372 Figure 3.5.1: Subscribe procedure that applies the additional 373 rules defined by the Customizable Algorithm component (a) and 374 the multicast tree after completing the procedure (b) 376 (a) +------------+ (b) +------------+ 377 | Root | | Root | 378 | IC={1,2,3} | | IC={1,2,3} | 379 +------------+ +------------+ 380 | | 381 | | 382 | +------------+ 383 | | A | 384 subscribe +------------+ | IC={1,2} | 385 +------------>| A | +------------+ 386 | | IC={1,2} |-+ | 387 +------------+ +------------+ | | 388 | B | | +============+ 389 | IC={2,3} |<----------------------+ | B | 390 +------------+ subscriber accepted | IC={2,3} | 391 +============+ 393 Figure 3.5.2: Subscribe procedure that does not apply the additional 394 rules defined by the Customizable Algorithm component (a) and the 395 multicast tree after completing the procedure (b) 397 Figure 3.5.3 briefly describes the exact procedures performed by the 398 node receiving a subscribe request to build an IC-based multicast 399 tree using the proposed mechanism. 401 +---------------+----------+ +------------------------+----------+ 402 | Tree Topology | | | Customizable Algorithm | | 403 +---------------+ | +------------------------+ | 404 | | | | 405 | 2. Query for a better | | 3. If the new subscriber's IC are | 406 | node to accept the | | the subset of this node's IC | 407 | request | | return null | 408 | 4. If the better node == | | 3'.Otherwise return this node's | 409 | null, accept the | | parent | 410 | request | | | 411 | 4'.If the better node | | | 412 | != null, forward the | | | 413 | request to that node | | | 414 | | | | 415 +--------------------------+ +-----------------------------------+ 416 ^ | ^ | ^ 417 |1.subscribe |2 | |3.better | 418 | request | | | node | 419 | | | | | 420 | | | | | 421 +----------------+---|-------|-------------|---------------------|---+ 422 | Core Algorithm | | +-------------+ | | 423 +----------------+ +-------------------------------------------+ | 424 | | 425 | | 426 | 1. If the topic exists and the node is allowed to subscribe for | 427 | it | 428 +--------------------------------------------------------------------+ 429 Figure 3.5.3: Procedure performed by the node receiving a subscribe 430 request 432 3.6 Publish-Subscribe API 434 3.6.1 Publish-Subscribe Interface 436 Application issues a publish-subscribe request using one of the 437 methods described below. All of them are implemented by the 438 Customizable Algorithm component. Each operation is asynchronous, as 439 it can take a long time to complete. Parameters enclosed in the 440 square brackets are optional. 442 void createTopic(String topicId, boolean subscribe, 443 [AccessControlRules ac]) 445 @param topicId Topic identifier. 447 @param subscribe Value indicating whether this node wants to 448 automatically subscribe for the specified topic 449 after its creation. In this case the 'create topic' 450 request is specially prepared and there is no need 451 to send a separate 'subscribe' request later on. 453 @param ac Access control rules defined for the operations associated 454 with this topic. 456 void removeTopic(String topicId) 458 @param topicId Topic identifier. 460 void subscribe(String topicId, [InterestConditions ic], 461 [int eventIndex]) 463 @param topicId Topic identifier. 465 @param ic Object representing Interest Conditions defined for the 466 particular topic by the higher-layer application. 468 @param eventIndex Value indicating which events from the topic 469 history node wants to receive after successfully 470 completing the subscribe operation. 472 void unsubscribe(String topicId) 474 @param topicId Topic identifier. 476 void publish(String topicId, Event e) 478 @param topicId Topic identifier. 480 @param e Event to be published. 482 3.6.2 Publish-Subscribe Callbacks 484 Additionally the publish-subscribe layer defines a set of callback 485 methods, which are invoked after completing asynchronous operations 486 and can be implemented by the higher-layer application. These methods 487 are described below. 489 public void onTopicSubscribe(String topicId) 491 @param topicId Topic identifier. 493 Called after a successful subscription. 495 public void onTopicCreate(String topicId) 497 @param topicId Created topic identifier. 499 Called after a successful topic creation. 501 public void onTopicNotify(String topicId, byte[] message) 503 @param topicId Topic identifier. 505 @param message Message encapsulated in the received event. 507 Called when node receives a custom event notification. 509 public void onTopicRemove(String topicId) 511 @param topicId Removed topic identifier. 513 Called when node receives the notification informing that the 514 particular topic has been removed. 516 public void onPubSubError(String topicId, Operation o, int errorCode) 518 @param topicId Topic identifier. 520 @param o Operation which failed to complete successfully. 522 @param errorCode Error code. 524 Called when an asynchronous operation fails to complete successfully. 526 4. Publish-Subscribe Protocol 528 4.1 General information 530 4.1.1 Topic 532 Apart from the identifier, there are several information stored for 533 each topic: 535 1) Owner 537 The node which has created the topic 539 2) Parent 541 Node's parent in the topology structure 543 3) Access Control Rules 545 Described in details in the section 4.1.6 547 4) Interest Conditions 549 Described in details in the section 4.1.5 551 5) Subscription list 553 The list of topic subscribers, which are this node's children in 554 the topology structure 556 6) Caches 558 The backup information about other nodes participating in the 559 topology structure 561 7) Distance 563 The distance between the peer id and the topic id (calculated 564 using the overlay-specific metrics) 566 8) History 568 The list of the previously published events for the specified 569 topic 571 4.1.2 Subscriber 573 Apart from the topic identifier, this object contains information 574 such as: 576 1) User name 578 User name in the Peer-to-Peer network 580 2) Peer id 582 Peer id in the Peer-to-Peer network 584 3) IP address 586 4) Port number 588 Port used for exchanging the publish-subscribe messages directly 590 4.1.3 Subscription 592 Subscription contains the following information: 594 1) Subscriber 596 2) Expiration time 597 How long the subscription is valid - after this period node needs 598 to resubscribe 600 4.1.4 Event 602 Every publish-subscribe event contains information about its 603 publisher and the identifier of the topic it is associated with. The 604 proposed publish-subscribe protocol defines three types of events: 606 - remove topic - informs all subscribers that the particular topic 607 has been removed 609 - AC modified - informs all subscribers that the Access Control Rules 610 (section 4.1.6) for the specified topic have been modified 612 - custom - this event encapsulates the user-defined events 614 4.1.5 Interest conditions 616 Each subscriber can define its Interest Conditions (IC) for the 617 topic. This means he can declare that he wants to receive information 618 only about the events published by a specified group of users. It can 619 be described as follows: 621 operation: eventtype(ALL): interestingusers[] 622 eventtype(...):interestingusers[] 624 If the 'interestingusers' list for the specified event type is empty, 625 it means that it is always interesting regardless the publisher. The 626 conditions defined for the event type ALL are always checked first. 627 If the 'interestingusers' list for it is empty, the decision on 628 whether the specified event is interesting or not, depends on the 629 'interestingusers' associated with the particular event type. 631 If there is no rule defined for some operation or event - it means it 632 is not interesting at all. 634 By default all the subscribers will be receiving every topic event. 635 It means that each non-leaf node in the topology structure has to 636 pass every event to all of its children. IC are defined locally and 637 checked by the topic subscriber before invoking the higher-layer 638 notify callback. Otherwise the node's parent in the topology 639 structure would have to define similar IC (to receive all the events, 640 that are interesting for its children). Additionally after modifying 641 IC, subscriber would in some cases have to be passed to a different 642 parent in the topology structure, generating extra traffic. 644 If IC for some topic are defined as follows: 646 NOTIFY: eventtype(ALL): 648 eventtype(REMOVETOPIC): 649 eventtype(MODIFYAC): 650 eventtype(CUSTOM): user1, user2, user3 652 then after receiving a CUSTOM notification from user1, 2 or 3, node 653 will inform higher layer about it. REMOVETOPIC and MODIFYAC events 654 are by default interesting regardless the publisher. 656 4.1.6 Access control rules 658 Nodes can define a set of rules for the topic, to grant other users 659 different access permissions (AC). These rules can be described as 660 follows: 662 operation: eventtype(ALL): allowusers[] 663 eventtype(...): allowusers[] 665 If the 'allowusers' list for a specified event type is empty, it 666 means that the associated operation can be performed by any 667 subscriber. The permissions defined for the event type ALL are always 668 checked first. If the 'allowusers' list for it is empty, then 669 granting access permission depends exclusively on the 'allowusers' 670 defined for the particular event type. 672 If there is no rule for some operation or event - it means it is not 673 allowed. 675 For example if the rules for some topic are: 677 SUBSCRIBE: eventtype(ALL): user1, user2, user3, user4 678 PUBLISH: eventtype(ALL): 679 eventtype(REMOVETOPIC): user1 680 eventtype(MODIFYAC): user1 681 eventtype(CUSTOM): user1, user2, user3 683 It means that: 684 - Only user1 is allowed to modify AC rules for the topic. By default 685 this permission is granted exclusively to the topic owner. 686 - If the topology structure participant receives a 'subscribe' 687 request for example from user5, subscription will fail due to 688 access control restrictions. Only users 1, 2, 3 and 4 are allowed 689 to subscribe for the topic. 690 - User4 may (according to SUBSCRIBE rules) subscribe for receiving 691 the topic events, but isn't allowed (according to PUBLISH rules) to 692 generate them. Users 1, 2 and 3 are all allowed to publish 693 user-defined events, but only user1 has permission to remove this 694 topic. By default only topic owner has permission to publish the 695 predefined events such as REMOVETOPIC or MODIFYAC. 697 In case of any collisions in the AC rules - the most important is the 698 one marked with ALL clause. For example if the rules are defined as 699 follows: 701 PUBLISH: eventtype(ALL): user1, user2, user3 702 eventtype(REMOVETOPIC): user1 703 eventtype(MODIFYAC): user1 704 eventtype(CUSTOM): user4 706 User4 will not be able to publish any event, because the first rule 707 to be checked is: eventtype(ALL): user1, user2, user3. It could be 708 repaired either by removing the 'allowusers' list for event type ALL, 709 or adding user4 to it. 711 The topic owner always retains permission to modify AC rules and 712 remove the topic, but it can also grant it to other users. Rules 713 defined for the 'notify' operation MAY differ for different nodes. By 714 default each subscriber will only accept event notifications from its 715 parent in the topology structure. 717 4.2 Default Customizable Algorithm 719 This section describes the default Customizable Algorithm component's 720 behavior and the possibilities of configuring it to address the 721 optimization issues. In some cases it is essential to determine 722 whether the underlying P2P network is a DHT-based or an unstructured 723 one. To fulfill this requirement we define an additional method that 724 asks the generic P2P protocol to calculate the distance between the 725 two given keys according to the overlay-specific metrics. Such 726 calculations are possible only in a DHT-based network. Each 727 publish-subscribe Customizable Algorithm component MUST implement 728 the set of operations defined in this section. In the diagrams shown 729 in this section we use '{PUBSUB}msg' notation to indicate, that the 730 message 'msg' is sent directly to the specified node and 731 '{P2P}insert(msg)' in case of messages encapsulated within an insert 732 request. 734 4.2.1 Create topic 736 To perform this operation node encapsulates the 'create topic' 737 message inside the P2P resource object, sets its key to the topic ID 738 and sends it within the P2P insert request. In the DHT-based networks 739 it is enough for the node receiving such request to check, whether it 740 does not store information about the specified topic itself 741 (figure 4.2.1). The unstructured networks require some lookup 742 procedure to determine, whether the topic has not been created by a 743 different node (figure 4.2.2). Such situation may occur, because the 744 object encapsulated inside the P2P resource object will in most cases 745 be stored by the 'create topic' request originator. This is where the 746 idea of the SUBSCRIPTIONINFO objects comes along. They are associated 747 with the particular topic and contain contact information about its 748 subscribers. The status of such object may be PENDING or ACCEPTED. 749 The difference between both states will be explained later on. Each 750 node receiving a 'create topic' request places a pending 751 SUBSCRIPTIONINFO object in the underlying P2P network. Then it looks 752 for other objects associated with the specified topic. If there is at 753 least one with the accepted status - it assures us that the specified 754 topic already exists. If the underlying P2P network stores only the 755 pending SUBSCRIPTIONINFO objects, than the peer with the lowest ID is 756 allowed to become the root for the specified topic. All the others 757 are supposed to remove their SUBSCRIPTIONINFO objects and send the 758 response with an appropriate error code. The 'create topic' request 759 may additionally contain a list of nodes, which are to be added to 760 the topic subscribers after successfully completing the operation. 761 This way its originator does not have to issue a separate 'subscribe' 762 request later on. The 'create topic' message may also be used to 763 transfer the topic to the new root, in which case a special flag is 764 set to indicate that this request refers to an existing topic. 765 Regardless the purpose, the described request always contains AC 766 rules defined for the topic. 768 Topic root 769 | {P2P}insert(messageObject) | 770 |------------------------------>| 1. if this is not a topic transfer 771 | | 772 | {PUBSUB}409 | 773 |<------------------------------| 2. if the topic exists 774 | | 3. finished 775 | | 776 | | 2'. if the topic does not exist 777 | | 3'. create the topic 778 | {PUBSUB}200 | 4'. add the subscribers if the 779 |<------------------------------| request contains any 780 | | 5'. finished 782 Figure 4.2.1: Create topic procedure in a DHT-based network 784 Topic root Root's neighbor 785 | {P2P}insert(messageObject) | | 786 |--------------------------->| 1. if this is not a topic | 787 | | transfer | 788 | {PUBSUB}409 | | 789 |<---------------------------| 2. if the topic exists | 790 | | 3. finished | 791 | | | 792 | | 2'. create the topic with a | 793 | | PENDING status | 794 | | 3'. insert mine | 795 | | SUBSCRIPTIONINFO | 796 | | object with a | 797 | | PENDING status | 798 | | | 799 | |{P2P}lookup(SUBSCRIPTIONINFO) | 800 | |-------------------------------->| 801 | | | 802 | | | 803 | | 804 | | 5'. if no SUBSCRIPTIONINFO found for 805 | | this topic or only PENDING objects 806 | | created by the peers with the higher 807 | | IDs exist - set the topic's and the 808 | | SUBSCRIPTIONINFO object's status to 809 | | ACCEPTED 810 | | 6'. add the subscribers if the 811 | | request contains any 812 | {PUBSUB}200 | 813 |<---------------------------| 814 | | 8'. finished 815 | | 816 | | 5''. if an ACCEPTED SUBSCRIPTIONINFO 817 | | found or the PENDING object created 818 | | by the peer with the lower ID exists 819 | | 6''. Remove the PENDING topic and mine 820 | | SUBSCRIPTIONINFO object 821 | {PUBSUB}409 | 822 |<---------------------------| 823 | | 8''. finished 824 | | 826 Figure 4.2.2: Create topic procedure in an unstructured network 828 4.2.2 Transfer topic 830 This operation is essential for the DHT-based networks. It MAY be 831 performed when the publish-subscribe layer receives the information 832 from the P2P layer, that it has accepted the other node's join 833 request. In such case the node iterates through all the topics it 834 stores information about. If it is the root for one of them and the 835 distance between the new peer's ID and the topic ID is smaller than 836 the distance calculated for this node, it sends a create topic 837 request inside the P2P insert message. Before sending the request, 838 the previous root MAY also add the list of its direct children to it. 839 All of the procedures associated with the topic transfer are 840 performed by the Topology Manager component, as it is responsible for 841 retaining the appropriate structure. For instance in the star 842 topology, all the request originator's children must be passed to the 843 new root as well. If some Customizable Algorithm component is 844 designed exclusively for the unstructured networks, it MAY choose not 845 to perform this procedure or use a different measure than the 846 distance between identifiers to determine, whether the specified 847 topic should be transfered. The brief description of the whole 848 procedure is shown in the figure 4.2.2.1. 850 +------------------------+-------+ +------------------+---------+ 851 | Customizable Algorithm | | | Topology Manager | | 852 +------------------------+ | +------------------+ | 853 | | | | 854 | foreach(topic in storedTopics) | | 3. Transfer the topic | 855 | 2. If thisNode is the root | | to the new peer | 856 | for this topic && | | | 857 | thisNodeToTopicDistance> | | | 858 | newPeerToTopicDistance | | | 859 | | | | 860 +--------------------------------+ +----------------------------+ 861 ^ | ^ 862 |1.new |2.topic, | 863 | peer | new peer | 864 | | | 865 | | | 866 +----------------+---|-------------------------------------------|--+ 867 | Core Algorithm | | | | 868 +----------------+ +-------------------------------------------+ | 869 | | 870 | | 871 | 1. New neighbor arrives | 872 | | 873 +-------------------------------------------------------------------+ 874 Figure 4.2.2.1: Overview of the topic transfer procedure 876 The details of the transfer topic procedure performed by the Topology 877 Manager component are described in the figures 4.2.2.2 (for the star 878 topology) and 4.2.2.3 (for the multicast tree). 880 (a) Previous root New root 881 | | 882 | | 1. Add the nodes from 883 | | the list inside the 884 | | transfer request to 885 | | the topic 886 | | subscription list 887 | {PUBSUB}200 | 888 |<-------------------------| 889 | | 891 (b) Previous root's 892 child Previous root New root 893 | | | 894 | | {PUBSUB}200 | Accepting 895 | 1. Set parent to |<-------------| topic 896 | the new root | | transfer 897 | 2. Send keep-alive | | 898 | indication | | 899 | to inform the | | 900 | child about the | | 901 | parent's change | | 902 | | | 903 | {PUBSUB}keep-alive | | 904 |<------------------------| | 905 1. Check if this | | | 906 message was sent| 3. Remove the child | | 907 by my parent | from the topic | | 908 (otherwise | subscription list| | 909 discard it) | 4. If this node is | | 910 2. Set parent to | not the topic 911 the one stated | subscriber itself 912 in keep-alive | - remove the 913 3. Update the cache| topic 914 4. Reset keep-alive| 5. Finished 915 timer for this | 916 topic | 917 | 919 Figure 4.2.2.2: Processing the transfer request(a) and response(b) by 920 the star topology 922 (a) Previous root New root 923 | | 924 | | 1. Add the request 925 | | originator to the 926 | | topic subscription 927 | | list 928 | {PUBSUB}200 | 929 |<--------------------------| 930 | | 932 (b) Previous root's 933 child Previous root New root 934 | | | 935 | | {PUBSUB}200 | Accepting 936 | 1. Set parent to |<-------------| topic 937 | the new root | | transfer 938 | 2. Send keep-alive | | 939 | indication | | 940 | to update the | | 941 | child's cache | | 942 | | | 943 | {PUBSUB}keep-alive | | 944 |<------------------------| | 945 1. Check if this | | | 946 message was sent| 3. Finished | | 947 by my parent | 948 (otherwise | 949 discard it) | 950 2. Set parent to | 951 the one sent | 952 in keep-alive | 953 3. Update the cache| 954 4. Reset keep-alive| 955 timer for this | 956 topic | 957 | 959 Figure 4.2.2.3: Processing the transfer request(a) and response(b) by 960 the multicast tree 962 4.2.3 Remove topic 964 To perform this operation, the node publishes the predefined 965 REMOVE_TOPIC event among the topic subscribers. After that all the 966 SUBSCRIPTIONINFO objects associated with this topic MUST be removed 967 from the underlying P2P network. 969 4.2.4 Subscribe 971 To subscribe for a topic, node has to send a 'subscribe' request to 972 the peer that is already participating in the appropriate topology 973 structure. Determining the message destination is crucial for the 974 whole procedure. In the DHT-based networks it is enough to 975 encapsulate the publish-subscribe request in the resource object. 976 Then it can be captured using the P2P protocol callbacks. The 977 unstructured networks require performing the lookup procedure for the 978 SUBSCRIPTIONINFO objects to identify the existing topology structure 979 participants. After that the request may be sent directly to the 980 specified node. Also the multicast trees are built using a different 981 approach in the unstructured and DHT-based environment. In the first 982 case, node accepts only the subscribers with the ID greater than its 983 own one (figure 4.2.4.1). The nodes that do not fulfill these 984 requirements are forwarded to the direct parent. Only the topic root 985 accepts all the requests unless this is forbidden by the AC rules. 986 Such an arrangement of the topology structure participants simplifies 987 the recovery procedures after the direct parent's failure. 989 +--------+ 990 | Root | 991 | id=2 | 992 +--------+ 993 / \ 994 / \ 995 +--------+ +--------+ 996 | A | | B | 997 | id=4 | | id=3 | 998 +--------+ +--------+ 999 | | 1000 | | 1001 +--------+ +---------+ 1002 | C | | D | 1003 | id=8 | | id=15 | 1004 +--------+ +---------+ 1006 Figure 4.2.4.1: Multicast tree created on top of an unstructured 1007 network 1009 In the DHT-based network the nodes are arranged by the distance 1010 between their identifiers and the topic ID (figure 4.2.4.2). 1012 +------------+ 1013 | Root | 1014 | distance=2 | 1015 +------------+ 1016 / \ 1017 / \ 1018 +------------+ +------------+ 1019 | A | | B | 1020 | distance=4 | | distance=3 | 1021 +------------+ +------------+ 1022 | | 1023 | | 1024 +------------+ +-------------+ 1025 | C | | D | 1026 | distance=8 | | distance=15 | 1027 +------------+ +-------------+ 1029 Figure 4.2.4.2: Multicast tree created on top of a DHT-based network 1031 In the unstructured networks, after successfully completing the 1032 described procedure, the new subscriber must place its 1033 SUBSCRIPTIONINFO object in the underlying network. This is done only 1034 if it is a peer, as clients SHOULD NOT be responsible for accepting 1035 new subscribers. The node must also locally modify the AC rules for 1036 the notify operation, to indicate that only its direct parent is 1037 allowed to send event notifications to it. The standard subscribe 1038 request also contains the additional information, such as the index 1039 of the last received event. After accepting the new subscriber, its 1040 parent must send the requested set of the notify messages containing 1041 the historical events to it. Each subscription is valid only for a 1042 specified time, so the node needs to renew it periodically. 1044 4.2.5 Unsubscribe 1046 If the node has no more children in the topology structure and it is 1047 not the topic root, it simply sends an 'unsubscribe' request directly 1048 to its parent and removes its SUBSCRIPTIONINFO object from the 1049 overlay if it is necessary. If the node has more children, it also 1050 has to send the keep-alive indication to them. It is depicted in 1051 figure 4.2.5.1. The unsubscribe request sent to the node's parent 1052 contains the list of its children. Parent node has to add the new 1053 children to its own ones. Children nodes get keep-alive indication 1054 with the information about the new parent and modify their cache 1055 information (figure 4.2.5.2). If necessary, keep-alive indications 1056 are propagated down along the multicast tree to update other node's 1057 caches (the unsubscribing node can be stored in their grandparents 1058 cache). Note that after unsubscribe root node does not notify the 1059 higher-layer about the received events anymore, but it is still able 1060 to forward appropriate messages to its children. 1062 +------+ 1063 | Root | 1064 +------+ 1065 | 1066 | 1067 +-------+ 1068 +-->| A | 1069 unsubscribe | +-------+ 1070 children={C,E} | | 1071 | | keep-alive 1072 | +--\--/--+ parent=A 1073 +---| B\/ |----------+---+ 1074 | /\ | | | 1075 +--/--\--+ | | 1076 / \ | | 1077 / \ | | 1078 +-------+ +-------+ | | 1079 | C | | E |<---+ | 1080 +-------+ +-------+ | 1081 ^ | 1082 | | 1083 +-------------------------+ 1085 Figure 4.2.5.1: Multicast tree before the unsubscribe procedure 1087 +------+ 1088 | Root | 1089 +------+ 1090 | 1091 | 1092 +-------+ 1093 | A | 1094 +-------+ 1095 / \ 1096 / \ 1097 +----------+ / \ +----------+ 1098 | Cache C: | +-------+ +-------+ | Cache E: | 1099 | p={A} |<--------| C | | E |-------->| p={A} | 1100 | g={ROOT} | +-------+ +-------+ | g={ROOT} | 1101 | n={C,E} | | n={C,E} | 1102 +----------+ +----------+ 1104 Figure 4.2.5.2: Multicast tree after the unsubscribe procedure 1106 4.2.6 Publish 1108 There are three types of the predefined events that can be published 1109 among the topic subscribers: AC_MODIFIED, TOPIC_REMOVED and CUSTOM. 1110 The first one is generated, when the access control rules are 1111 modified. The third one represents a custom event defined by the 1112 higher-layer application. The default Customizable Algorithm 1113 component requires all the publish messages to be delivered to the 1114 topic root, which accepts the request, sends the appropriate response 1115 to its originator and the set of notify indications to the direct 1116 children. This is done to avoid the situation, when for example AC 1117 rules have been modified, but the AC_MODIFIED event has not been 1118 propagated among all of the topic subscribers. In such case some of 1119 them may accept the events from the node which is not allowed to 1120 generate them anymore. In the default Customizable Algorithm 1121 component AC rules are defined so, that only the node's parent in the 1122 topology structure is allowed to send event notifications to it. Note 1123 that there are two situations, in which such indication may be 1124 received. The first one is when a new event is generated by some 1125 node. In this case the notification SHOULD be forwarded down along 1126 the multicast tree. However it might happen that the new subscriber 1127 receives the requested historical events after successfully 1128 completing the subscribe operation. In such case no further 1129 forwarding is needed. The node only updates its own topic history and 1130 invokes the higher-layer callback. The default Customizable Algorithm 1131 component also requires the node to be a topic subscriber to generate 1132 events. 1134 4.2.7 Notify 1136 After receiving a publish request, topic root propagates the event 1137 among its children using the notify message. Like all indications, 1138 notifications are send directly to the specified nodes. Figure 1139 4.2.7.1 briefly describes the procedure performed after receiving 1140 such message. By default the Customizable Algorithm component defines 1141 AC rules so, that only the node's parent in the topology structure is 1142 allowed to send notifications to it. There are three predefined event 1143 types sent within the notify message(see section 4.1.4). All the 1144 received notifications MUST be forwarded to children unless they are 1145 historical. 1147 Child Parent 1148 | | 1149 | {PUBSUB}notify | 1150 1. If operation not allowed - finished |<--------------------------| 1151 | | 1152 2. If event is interesting (according | | 1153 to IC) and historical (appropriate | | 1154 flag set to 1), node: | | 1155 - updates topic history | | 1156 - if it is topic subscriber, not | | 1157 just a forwarder invokes | | 1158 higher-layer application callback | | 1159 3. Finished | | 1160 | | 1161 2'. If event is interesting and new | | 1162 (appropriate flag set to 0), | | 1163 node: | | 1164 - updates topic history | | 1165 - forwards notification to | | 1166 children (and invokes its own | | 1167 callback if it is topic | | 1168 subscriber) | | 1169 3'. Finished | | 1170 | | 1172 Figure 4.2.7.1: Procedure performed after receiving 1173 event notification 1175 4.2.8 Maintenance 1177 Apart from the necessity to transfer a topic to the new root in some 1178 situations, there is also the nodes' failures problem that has to be 1179 handled by the Customizable Algorithm component. To address this 1180 issue, we define a keep-alive indication. Every node periodically 1181 sends this message to its direct children. If some peer is the other 1182 one's parent for several topics, it does not have to send a separate 1183 indication for each one of them. Such message contains the 1184 information about the current parent and the list of the 'backup 1185 nodes' to be placed in the node's cache for each topic. When the 1186 child detects its parent's failure, it uses the cache to resubscribe. 1187 If the cache size is set to 0 by the Algorithm Configurator 1188 component, the default Customizable Algorithm assumes, that the 1189 keep-alive message does not carry any additional information and 1190 treats the notify indication as a 'keep-alive', like Scribe does. 1191 This way, if events are frequently published for the specified 1192 topics, no additional traffic associated with the topology structure 1193 maintenance is involved. This optimization mechanism can be 1194 considered for the DHT-based networks, where the recovery procedure 1195 may be performed at a relatively low cost using the overlay-specific 1196 routing. In general there are three types of caches stored for each 1197 topic: parents cache, grandparents cache and neighbors cache. The 1198 capacities of the caches are the parameters k (for the parents and 1199 neighbors) and g (for the grandparents). For the node N at the level 1200 x, parents cache contains k nodes with the lowest id or the closest 1201 to the topic id from the level x-1. It may also contain the node's 1202 direct parent. The neighbor cache contains k nodes with the lowest id 1203 or the closest to the topic id from the level x, which have the same 1204 parent as N. The grandparents cache contains one node from each level 1205 between x-2 and x-1-g. This cache is stored in case of the multiple 1206 nodes' failures in the highly unbalanced trees. When all the nodes 1207 from the parents cache fail to respond or the cache is empty - the 1208 node can try to send 'subscribe' request directly to its grandparent. 1209 All the nodes at the same level and in the same subtree have the same 1210 caches' contents. Nodes in the different subtrees have different 1211 neighbors caches' contents. All the entries in the parents and 1212 neighbors caches are sorted from the lowest id (or distance to the 1213 topic id) to the highest. In the grandparents cache the node from the 1214 highest level is stored at the lowest index. Examples of the topology 1215 structures and caches' contents for both the unstructured and 1216 DHT-based networks are shown in the figures 4.2.8.1 and 4.2.8.2. 1218 ------------------------------------------------------ 1219 +-------------+ +-------+ | Level 0 1220 | Cache ROOT: |<------------------| ROOT | | 1221 | p={} | | dist=2| | 1222 | g={} | +-------+ | 1223 | n={} | / | \ | 1224 +-------------+ ----------------/----|----\--------------------------- 1225 +----------+ / | \ | Level 1 1226 | Cache A: | +--------+ +-------+ +-------+ | 1227 | p={ROOT} |<---------| A | | B | | C | | 1228 | g={} | | dist=8 | | dist=3| | dist=5| | 1229 | n={B,C} | +--------+ +-------+ +-------+ | 1230 +----------+ ---------/-----\---------------|---------------------- 1231 +----------+ / \ | | Level 2 1232 | Cache D: | +--------+ +-------+ +-------+ | 1233 | p={B,C} |<-----| D | | E | | F | | 1234 | g={ROOT} | | dist=11| | dist=9| | dist=6| | 1235 | n={E,D} | +--------+ +-------+ +-------+ | 1236 +----------+ ------------------|-------------|--------------------- 1237 | +---------+ 1238 | | 1239 V V 1240 +----------+ +----------+ 1241 | Cache E: | | Cache F: | 1242 | p={B,C} | | p={B,C} | 1243 | g={ROOT} | | g={ROOT} | 1244 | n={E,D} | | n={F} | 1245 +----------+ +----------+ 1247 Figure 4.2.8.1: Caches' contents for k=2 and g=1 in the DHT-based 1248 network 1250 ------------------------------------------------------- 1251 +-------------+ +-------+ | Level 0 1252 | Cache ROOT: |<------------------| ROOT | | 1253 | p={} | | id=2 | | 1254 | g={} | +-------+ | 1255 | n={} | / | \ | 1256 +-------------+ ----------------/----|----\--------------------------- 1257 +----------+ / | \ | Level 1 1258 | Cache A: | +--------+ +-------+ +-------+ | 1259 | p={ROOT} |<---------| A | | B | | C | | 1260 | g={} | | id=8 | | id=3 | | id=5 | | 1261 | n={B,C} | +--------+ +-------+ +-------+ | 1262 +----------+ ---------/-----\---------------|---------------------- 1263 +----------+ / \ | | Level 2 1264 | Cache D: | +--------+ +-------+ +-------+ | 1265 | p={B,C} |<-----| D | | E | | F | | 1266 | g={ROOT} | | id=11 | | id=9 | | id=6 | | 1267 | n={E,D} | +--------+ +-------+ +-------+ | 1268 +----------+ ------------------|-------------|--------------------- 1269 | +---------+ 1270 | | 1271 V V 1272 +----------+ +----------+ 1273 | Cache E: | | Cache F: | 1274 | p={B,C} | | p={B,C} | 1275 | g={ROOT} | | g={ROOT} | 1276 | n={E,D} | | n={F} | 1277 +----------+ +----------+ 1279 Figure 4.2.8.2: Caches' contents for k=2 and g=1 in an unstructured 1280 network 1282 Figure 4.2.8.3 briefly describes the usage of the grandparents cache 1283 in case of the multiple nodes' failures. 1285 +------+ 1286 +--->| ROOT | 1287 | +------+ 1288 | | 1289 | | 1290 | +-\--/-+ 1291 | | A\/ | 1292 | | /\ | 1293 | +-/--\-+ 1294 | | \ 1295 possible path for | | \ 1296 resubsciption | +-\--/-+ +-\--/-+ 1297 | | B\/ | | E\/ | 1298 | | /\ | | /\ | 1299 | +-/--\-+ +-/--\-+ 1300 | | 1301 | | 1302 | +------+ +-------------+ 1303 +----| C |------->| Cache C: | 1304 +------+ | p={B,E} | 1305 | g={A,ROOT} | 1306 | n={C} | 1307 +-------------+ 1309 Figure 4.2.8.3: Example of the grandparents cache usage 1310 (algorithm parameters: k=2 and g=2) 1312 After discovering the direct parent's failure, node tries to send the 1313 'subscribe' request to the the first node from its parents cache. If 1314 it does not respond, it is removed from the cache, and the 1315 'subscribe' request is sent to the next one. If all the nodes from 1316 the parents cache fail to respond, the grandparents cache is used. If 1317 the grandparents cache does not contain any useful information and 1318 the node's distance to the topic ID is greater than 0, than peer 1319 assumes that it participates in the DHT-based network and there may 1320 be some node which ID is closer to the topic ID than its own one. In 1321 such case it encapsulates the 'transfer topic' request inside the P2P 1322 insert message. If this message is received by some other node, it 1323 performs a standard topic transfer procedure. If the peer is already 1324 participating in the topology structure, than it only omits creating 1325 the new topic. If the distance between the topic ID and the peer ID 1326 is lower than 0, than node assumes, that it is participating in an 1327 unstructured network and cannot rely on the overlay routing 1328 algorithm. In such case the neighbor cache's contents are examined. 1329 If it does not provide any useful information or this node is the 1330 first one on the list, the subscriber performs the lookup procedure 1331 for the SUBSCRIPTIONINFO objects associated with the same topic. If 1332 it finds any nodes with the ID lower than its own one, than it must 1333 send the subscribe message to the one with the lowest ID. If there 1334 are no such nodes in the P2P network, than it assumes that it is the 1335 new topic root and waits for the other nodes to send 'subscribe' 1336 requests to it. These procedures guarantee the cycles avoidance. 1337 Moreover they work both for the multicast tree and star topology. 1339 4.2.9 Reliability 1341 [TODO: history of events for temporary out-of-order issues, but not 1342 the long term ones - history length as algorithm parameter] 1344 4.3 Message formats 1346 All the message formats described in this section are used by the 1347 default Customizable Algorithm component. However they MAY be 1348 extended by the user-defined ones if it is necessary and registered 1349 by a different Algorithm Configurator object. In general there are 1350 three types of messages: requests, indications and responses. Node 1351 receiving the first one always sends response to the message 1352 originator. Both requests and responses contain the unique 1353 identifier of the transaction, they are associated with. It is 1354 generated by the request originator, who uses it to find out, which 1355 operation is received response related to. Indications are messages 1356 which do not require any response as they are not associated with a 1357 pending operation. 1359 4.3.1 Standard header 1361 Every publish-subscribe message is preceded by the following header: 1363 0 1 2 3 1364 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 1365 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1366 |IPver| Source IP // 1367 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1368 // | Destination IP // 1369 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1370 // | Source port // 1371 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1372 // | Destination port // 1373 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1374 // | Type | // 1375 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1376 // Source user name length | // 1377 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1378 // Source user name | 1379 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1380 | Source peer id length | 1381 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1382 | Source peer id // 1383 + + 1384 // | 1385 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1386 | Destination user name length | 1387 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1388 | Destination user name // 1389 + + 1390 // | 1391 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1392 | Destination peer id length | 1393 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1394 | Destination peer id // 1395 + + 1396 // | 1397 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1398 | Topic id length | 1399 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1400 | Topic id // 1401 + + 1402 // | 1403 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1405 IP version (3 bits): IP version number, 4 or 6 1406 Source IP (32 or 128 bits): IP address of message sender 1408 Destination IP (32 or 128 bits): IP address of message receiver 1410 Source port (32 bits): Message sender's port number 1412 Destination port (32 bits): Message receiver's port number 1414 Type (8 bits): Publish-subscribe message type 1416 Source user name length (32 bits): Length of the user's unhashed id 1418 Source user name (undefined): User's unhashed id 1420 Source peer id length (32 bits): Length of the peer id 1422 Source peer id (undefined): Peer id 1424 Destination user name length (32 bits): Length of user's unhashed id 1426 Destination user name (undefined): User's unhashed id 1428 Destination peer id length (32 bits): Length of the peer id 1430 Destination peer id (undefined): Peer id 1432 Topic id length (32 bits): Length of the topic id this message is 1433 associated with 1434 Topic id (undefined): Topic id this message is associated 1435 with 1437 4.3.2 Standard request header 1439 Apart from the type-specific information, every request contains the 1440 following header: 1442 0 1 2 3 1443 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 1444 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1445 | Transaction id | 1446 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1448 Transaction id (32 bits): Identifier of the transaction this 1449 operation is associated with 1451 4.3.3 Create topic 1453 Create topic message can be send to actually create a new topic, or 1454 to transfer an existing one to the new root. The node recognizes the 1455 requested operation by checking the value of the special flag inside 1456 the header. 1458 0 1 2 3 1459 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 1460 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1461 | F | AC rules // 1462 +-+-+ + 1463 // | 1464 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1465 | Subscribers list length | 1466 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1467 | Subscriber 1 // 1468 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1470 F (2 bits): Flag representing the requested operation type. Currently 1471 only two types are defined (figure 4.3.3.1). 1473 AC rules (undefined): Access control rules defined for the topic (see 1474 section 4.4.1 for details). 1476 Subscriber list length (32 bits): Length of the list containing the 1477 subscribers to be added after the 1478 topic creation. 1480 +------+-------------------------------------------------------+ 1481 |Value | Description | 1482 +------+-------------------------------------------------------+ 1483 | 0 | Creates new topic | 1484 | | | 1485 | 1 | Transfers an existing topic to new root | 1486 +------+-------------------------------------------------------+ 1488 Figure 4.3.3.1 1490 4.3.4 Subscribe 1492 0 1 2 3 1493 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 1494 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1495 | Expiration time // 1496 + + 1497 // | 1498 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1499 | Event index | 1500 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1501 | Distance | 1502 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1504 Expiration time (64 bits): Time, after which node will have to 1505 resubscribe 1507 Event index (32 bits): Index of the last received event from the 1508 topic history 1510 Distance (32 bits): Distance between the subscriber id and topic id 1512 4.3.5 Unsubscribe 1514 Currently there are no type-specific values for this message. It 1515 contains only the standard request header. 1517 4.3.6 Publish 1519 0 1 2 3 1520 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 1521 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1522 | Event type | User name length // 1523 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1524 // | User name // 1525 +-+-+-+-+-+-+-+-+-+-+ + 1526 // | 1527 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1528 | Message length | 1529 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1530 | Message | 1531 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1533 Event type (8 bits): Field indicating, whether this is the 1534 REMOVE_TOPIC, AC_MODIFIED or CUSTOM event 1536 User name length (32 bits): Length of the event publisher's name 1538 User name (undefined): Event publisher's name 1540 Message length (32 bits): Length of the message encapsulated in the 1541 CUSTOM event 1543 Message (undefined): User-defined message encapsulated in the CUSTOM 1544 event or the modified AC rules 1546 4.3.7 Notify 1547 0 1 2 3 1548 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 1549 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1550 |H| Event type | User name length // 1551 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1552 // | User name // 1553 +-+-+-+-+-+-+-+-+-+-+-+-+ + 1554 | | 1555 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1556 | Message length | 1557 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1558 | Message | 1559 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1561 H (1 bit): Flag indicating whether this event is the new one (value 1562 MUST be 0 in this case), or the old one from the topic 1563 history (value MUST be 1) 1565 Event type (8 bits): Field indicating, whether this is a 1566 REMOVE_TOPIC, AC_MODIFIED or CUSTOM event 1568 User name length (32 bits): Length of the event publisher's name 1570 User name (undefined): Event publisher's name 1572 Message length (32 bits): Length of the message encapsulated in the 1573 CUSTOM event 1575 Message (undefined): Message encapsulated in the CUSTOM event 1577 4.3.8 Standard response header 1579 Every response, except the response code, contains a unique 1580 transaction identifier. The request originator uses it, to find out 1581 which operation this response is related to. 1583 0 1 2 3 1584 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 1585 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1586 | Transaction number | 1587 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1588 | Response code | 1589 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1591 Transaction number (32 bits): Identifier of the transaction, this 1592 response is associated with 1594 Response code (32 bits): Response codes are described in section 4.7 1596 4.3.9 Subscribe response 1597 0 1 2 3 1598 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 1599 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1600 | AC rules // 1601 + + 1602 // | 1603 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1605 AC rules (undefined): AC rules encoding is described in section 4.4.1 1607 4.3.10 Keep-alive 1609 Parent (undefined): Subscriber object containing node's parent in 1610 the topology structure 1612 Neighbors (undefined): List of the subscriber objects to put into the 1613 neighbors cache. Its length depends on the k 1614 parameter. 1616 Parents (undefined): List of the subscriber objects to put into the 1617 parents cache. Its length depends on the k 1618 parameter. 1620 Grandparents (undefined): List of the subscriber objects to put into 1621 the grandparents cache. Its length depends 1622 on the g parameter. 1624 4.4 Objects formats 1626 4.4.1 AC rules 1628 0 1 2 3 1629 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 1630 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1631 | List of rules length | 1632 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1633 | List of rules // 1634 + + 1635 // | 1636 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1638 List of rules length (32 bits): Number of the rules on the list 1640 List of rules (undefined): List of the AC rules (see section 4.4.2 1641 for details) 1643 4.4.2 Rule 1644 0 1 2 3 1645 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 1646 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1647 | Operation byte length | 1648 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1649 | Operation // 1650 + + 1651 // | 1652 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1653 | Event type | Allowed users list length // 1654 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1655 // | User byte length // 1656 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1657 // | User // 1658 +-+-+-+-+-+-+-+-+-+-+ + 1659 | | 1660 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1661 | User 2 byte length | 1662 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1663 | ..... | 1664 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1665 | Event type 2 | .... | 1666 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1668 Operation (undefined): Operation, this rule is associated with 1670 Event type (8 bits): Particular event within an operation (at least 1671 one event is mandatory) 1673 User (undefined): User allowed to perform specified operation 1675 4.4.3 Operation 1677 0 1678 0 1 2 3 4 5 6 7 8 9 1679 +-+-+-+-+-+-+-+-+-+-+ 1680 | Operation type | 1681 +-+-+-+-+-+-+-+-+-+-+ 1683 Operation type (8 bits): Type of an operation, this rule is 1684 associated with. Currently defined values 1685 correspond with the message types 1686 (from 1 to 6) described in section 4.5. 1688 4.4.4 User 1690 0 1 2 3 1691 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 1692 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1693 | Username byte length | 1694 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1695 | Username // 1696 + + 1697 // | 1698 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1700 4.4.5 Subscriber 1702 0 1 2 3 1703 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 1704 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1705 | Username byte length | 1706 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1707 | Username // 1708 + + 1709 // | 1710 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1711 | Peer id byte length | 1712 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1713 | Peer id // 1714 + + 1715 // | 1716 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1717 | IP address byte length | 1718 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1719 | IP address // 1720 + + 1721 // | 1722 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1723 | Port number | 1724 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1726 4.5 Message types 1728 +------+-------------------------+-----------------------------+ 1729 |Value | Message type | Indication/Request/Response | 1730 +------+-------------------------+-----------------------------+ 1731 | 0 | Standard response | Res | 1732 | | | | 1733 | 1 | Create topic | Req | 1734 | | | | 1735 | 2 | Subscribe | Req | 1736 | | | | 1737 | 3 | Unsubscribe | Req | 1738 | | | | 1739 | 4 | Publish | Req | 1740 | | | | 1741 | 5 | Notify | Ind | 1742 | | | | 1743 | 6 | Keep-alive | Ind | 1744 +------+-------------------------+-----------------------------+ 1746 4.6 Event types 1748 +------+--------------------------------------------------+ 1749 | Type | Description | 1750 +------+--------------------------------------------------+ 1751 | 0 | Topic removed | 1752 | | | 1753 | 1 | Access Control Rules modified | 1754 | | | 1755 | 2 | Custom event defined by higher-layer application | 1756 | | | 1757 +------+--------------------------------------------------+ 1759 4.7 Response codes 1761 Response codes are inspired from HTTP. 1763 +------+-------------------------------------------------------+ 1764 |Code | Description | 1765 +------+-------------------------------------------------------+ 1766 | 200 | Operation successful | 1767 | | | 1768 | 403 | Operation forbidden due to AC rules | 1769 | | | 1770 | 404 | Operation cannot be completed, because the topic or | 1771 | | subscriber it is associated with does not exist | 1772 | | | 1773 | 409 | Create topic operation cannot be completed because | 1774 | | the specified topic already exists | 1775 | | | 1776 +------+-------------------------------------------------------+ 1778 4.8 Security 1780 [TODO: Verifying user identity for AC rules, etc.] 1782 5. Integrating publish-subscribe with P2PP/RELOAD 1784 5.1 Extending P2PP/RELOAD interfaces 1786 There are several major differences between some of the P2PP and 1787 RELOAD requests, we had to consider. P2PP publish allows application 1788 to insert only one object per request. Single RELOAD store request 1789 MAY contain several objects with the same resource-id, but different 1790 kind-id's or data models. It is the same with the P2PP lookup and 1791 RELOAD fetch requests. To provide the generic interfaces for both 1792 protocols we decided to use object lists, not single objects in all 1793 callbacks associated with the requests processing. Due to the 1794 terminology differences between both protocols we use 'insert' for 1795 the P2PP publish, and RELOAD store request, and 'lookup' for the P2PP 1796 lookup and RELOAD fetch request where distinguishing one from another 1797 is not essential. 1799 5.1.1 Callbacks 1801 We propose adding several callback methods to the P2PP/RELOAD 1802 interfaces. They can be used by applications built on top of it not 1803 only for gathering information about the received messages, but also 1804 for passing data to the overlay layer. Parameters marked as [in] are 1805 the ones that are passed to the higher layer by P2PP/RELOAD. These 1806 marked as [out] are returned to the overlay by the application layer. 1808 [TODO: Decide what about applications which do not want to use 1809 callbacks - default implementation returning true shouldn't be a 1810 problem, when performance is considered] 1812 [TODO: Decide, whether signature/certificate checking should be 1813 performed before or after the callback invocation (in the second case 1814 application layer would have to update the object's signature) and 1815 whether to invoke callbacks for example if the RELOAD layer already 1816 knows that the signature is invalid] 1818 boolean onDeliverRequest([in]Request message, 1819 [in/out]List objectList) 1821 @param message Received P2PP/RELOAD request. 1823 @param objectList Value interpretation is message type dependent. 1825 @return Value interpretation is message type dependent. In general 1826 'true' means 'continue standard processing', and 'false' 1827 means 'perform custom operation'. 1829 Usually invoked directly after receiving a request and determining 1830 that this node is message destination. In case of lookup requests - 1831 after searching for the objects in the peer's resource table 1832 (figure 5.1.1.1). If node stores the requested objects there, they 1833 are passed to the higher layer using 'objectList' parameter. 1834 Higher-layer application may decide to send these objects within the 1835 lookup response, or pass a different ones using the same parameter. 1836 After the callback invocation P2PP/RELOAD checks the returned value. 1837 If this value is 'true' it simply returns objects found in the 1838 resource table in response (or 'NOT FOUND' message if none of the 1839 requested objects is stored there). Otherwise response message 1840 contents depend on the second callback parameter's value (objects 1841 defined by higher layer are returned to the request originator). This 1842 MAY be used by the application built on top of P2PP/RELOAD for 1843 example to create different 'views' of the node's resource table, 1844 depending on the lookup request originator. Higher layer MAY hide 1845 object's value from some users or send different values to them. 1847 Similar procedure is performed after receiving an insert request 1848 (figure 5.1.1.2) although returned value interpretation is slightly 1849 different. When this value is 'true', objects encapsulated inside the 1850 insert request are simply put into the peer's resource table. 1851 Otherwise either different objects are inserted or only P2PP/RELOAD 1852 response is sent. 1854 For both insert and lookup requests application layer MAY modify 1855 object list elements' values or replace them with null. It MUST NOT 1856 modify resource id, type or data model. For all the request types it 1857 also MUST NOT alter the object list size. 1859 Message 1860 Receiver Originator 1861 +------------------------------------------------+ +------+ 1862 | | | | 1863 | RELOAD/| |RELOAD| 1864 | Application P2PP | lookup |/P2PP | 1865 | | | | request | | | 1866 | | |<-----------------| | 1867 | | 1. Fill object | | | | | 1868 | | list (if | | | | | 1869 | | some | | | | | 1870 | | requested | | | | | 1871 | | object isn't| | | | | 1872 | | stored here | | | | | 1873 | | - add null | | | | | 1874 | | at this | | | | | 1875 | | position) | | | | | 1876 | | | | | | | 1877 | | onDeliverRequest | | | | | 1878 | | (request, objects)| | | | | 1879 | |<-----------------------| | | | | 1880 | | | | | | | 1881 | 1. continue | | | | | | 1882 | standard | true, objects | | | | | 1883 | processing |----------------------->| | | | | 1884 | | | | | | | 1885 | | 1. return | | | | | 1886 | | standard | | | | | 1887 | | response | | | | | 1888 | | containing | | | | | 1889 | | objects | | | | | 1890 | | found in | | standard | | | 1891 | | resource | | response | | | 1892 | | table |----------------->| | 1893 | | 2. finished | | | | | 1894 | | | | | | | 1895 | | | | | | | 1896 | 1'. modify object | | | | | | 1897 | list (if any | | | | | | 1898 | of stored | | | | | | 1899 | objects needs | | | | | | 1900 | to be hidden | | | | | | 1901 | from lookup | | | | | | 1902 | request | | | | | | 1903 | originator | | | | | | 1904 | - set it to | | | | | | 1905 | null) | | | modified | | | 1906 | | false, modifiedObjects | | response | | | 1907 | |----------------------->|----------------->| | 1908 | | | | | | | 1909 | | | | | | | 1910 | | | | 1911 +------------------------------------------------+ +------+ 1912 Figure 5.1.1.1: Node receives lookup request 1914 Message 1915 Receiver Originator 1916 +------------------------------------------------+ +------+ 1917 | | | | 1918 | RELOAD/| |RELOAD| 1919 | Application P2PP | insert |/P2PP | 1920 | | | | request | | | 1921 | | |<-----------------| | 1922 | | 1. Fill object | | | | | 1923 | | list with | | | | | 1924 | | values from | | | | | 1925 | | resource | | | | | 1926 | | table (if | | | | | 1927 | | object with | | | | | 1928 | | specified | | | | | 1929 | | key and of | | | | | 1930 | | specified | | | | | 1931 | | type isn't | | | | | 1932 | | already | | | | | 1933 | | stored here | | | | | 1934 | | - add null | | | | | 1935 | | at this | | | | | 1936 | | position) | | | | | 1937 | | | | | | | 1938 | | onDeliverRequest | | | | | 1939 | | (request, objects)| | | | | 1940 | |<-----------------------| | | | | 1941 | | | | | | | 1942 | 1. continue | | | | | | 1943 | standard | true, objects | | | | | 1944 | processing |----------------------->| | | | | 1945 | | | | | | | 1946 | | 1. insert all | | | | | 1947 | | objects from| | | | | 1948 | | request into| | insert | | | 1949 | | resource | | response | | | 1950 | | table |----------------->| | 1951 | | 2. finished | | | | | 1952 | | | | | | | 1953 | 1'. modify object | | | | | | 1954 | list | false, modifiedObjects | | | | | 1955 | |----------------------->| | | | | 1956 | | 1. for each | | | | | 1957 | | element on | | | | | 1958 | | the list if | | | | | 1959 | | it is not | | | | | 1960 | | null insert | | | | | 1961 | | it into | | insert | | | 1962 | | resource | | response | | | 1963 | | table |----------------->| | 1964 | | | | | | | 1965 | | | | | | | 1966 | | | | 1967 +------------------------------------------------+ +------+ 1968 Figure 5.1.1.2: Node receives insert request 1970 boolean onForwardingRequest([in]Request message, 1971 [in/out]List objectList) 1972 @param message Received P2PP/RELOAD request. 1974 @param objectList Value interpretation is message type dependent. 1976 @return Value indicating, whether to forward or discard the message. 1977 In case of discarding - node has to send P2PP response. 1978 Otherwise request sender will try to retransmit its message 1979 and finally assume unresponsive peer's failure. 1981 Usually invoked directly after receiving a P2PP request (and 1982 determining that this node is not the message destination), before 1983 forwarding it to other node or sending 302 response. In case of 1984 lookup requests (figure 5.1.1.3) - after checking, if the requested 1985 object is not for example cached (or replicated) here. If such object 1986 is found, P2PP/RELOAD passes it to the higher layer using the 1987 'objectList' parameter. Higher-layer application may decide to send 1988 this object within the P2PP lookup response, or pass a different one 1989 using the same parameter. After the callback invocation P2PP/RELOAD 1990 checks the returned value. If this value is 'true' it simply forwards 1991 the message or returns the cached/replicated objects in a standard 1992 response. Otherwise the message is discarded, and P2PP/RELOAD 1993 response containing objects defined by the higher layer is sent. 1995 Figure 5.1.1.4 shows the procedure performed in case of receiving 1996 insert request. If the returned value is 'true', the message is 1997 forwarded. Otherwise node discards the message and sends insert 1998 response to its originator. 2000 For both insert and lookup requests application layer MAY modify the 2001 object list elements' values or replace them with null. It MUST NOT 2002 modify the resource id, type or data model. For all request types it 2003 also MUST NOT alter the object list size. 2005 Message 2006 Receiver Originator 2007 +------------------------------------------------+ +------+ 2008 | | | | 2009 | RELOAD/| |RELOAD| 2010 | Application P2PP | lookup |/P2PP | 2011 | | | | request | | | 2012 | | |<----------------| | 2013 | | 1. Fill object | | | | | 2014 | | list (if | | | | | 2015 | | some | | | | | 2016 | | requested | | | | | 2017 | | object isn't| | | | | 2018 | | replicated/ | | | | | 2019 | | cached here | | | | | 2020 | | - add null | | | | | 2021 | | at this | | | | | 2022 | | position) | | | | | 2023 | | | | | | | 2024 | | onDeliverRequest | | | | | 2025 | | (request, objects)| | | | | 2026 | |<-----------------------| | | | | 2027 | | | | | | | 2028 | 1. continue | | | | | | 2029 | standard | true, objects | | | | | 2030 | processing |----------------------->| | | | | 2031 | | | | | | | 2032 | | 1. return | | | | | 2033 | | standard | | | | | 2034 | | response | | | | | 2035 | | containing | | | | | 2036 | | replicated/ | | | | | 2037 | | cached | | | | | 2038 | | objects, | | | | | 2039 | | forward the | | | | | 2040 | | message or | | | | | 2041 | | send | | standard | | | 2042 | | redirect | | response | | | 2043 | | response |---------------->| | 2044 | | 2. finished | | | | | 2045 | | | | | | | 2046 | | | | | | | 2047 | 1'. modify object | | | | | | 2048 | list (if any | | | | | | 2049 | of stored | | | | | | 2050 | objects needs | | | | | | 2051 | to be hidden | | | | | | 2052 | from lookup | | | | | | 2053 | request | | | | | | 2054 | originator | | | | | | 2055 | - set it to | | | | | | 2056 | null) | | | | | | 2057 | | false, modifiedObjects | | | | | 2058 | |----------------------->| | | | | 2059 | | 1. send | | | | | 2060 | | response | | | | | 2061 | | containing | | modified | | | 2062 | | modified | | response | | | 2063 | | objects |---------------->| | 2064 | | 2. finished | | | | | 2065 | | | | | | | 2066 | | | | 2067 +------------------------------------------------+ +------+ 2068 Figure 5.1.1.3: Node receives lookup request 2070 Message 2071 Receiver Originator 2072 +-------------------------------------------+ +------+ 2073 | | | | 2074 | RELOAD/| |RELOAD| 2075 | Application P2PP | insert |/P2PP | 2076 | | | | request | | | 2077 | | |<----------------------| | 2078 | | 1. Fill object | | | | | 2079 | | list with | | | | | 2080 | | replicated/ | | | | | 2081 | | cached | | | | | 2082 | | objects (if | | | | | 2083 | | object with | | | | | 2084 | | specified | | | | | 2085 | | key and of | | | | | 2086 | | specified | | | | | 2087 | | type isn't | | | | | 2088 | | replicated/ | | | | | 2089 | | cached here | | | | | 2090 | | - add null | | | | | 2091 | | at this | | | | | 2092 | | position) | | | | | 2093 | | | | | | | 2094 | | onDeliverRequest | | | | | 2095 | | (request, objects)| | | | | 2096 | |<-----------------------| | | | | 2097 | | | | | | | 2098 | 1. continue | | | | | | 2099 | standard | true, objects | | | | | 2100 | processing|----------------------->| | | | | 2101 | | | | | | | 2102 | | 1. forward the | | | | | 2103 | | message or | | | | | 2104 | | send | | standard | | | 2105 | | redirect | | response | | | 2106 | | response |---------------------->| | 2107 | | 2. finished | | | | | 2108 | | | | | | | 2109 | 1'. modify | | | | | | 2110 | object | false, modifiedObjects | | | | | 2111 | list |----------------------->| | | | | 2112 | | 1. for each | | | | | 2113 | | element on | | | | | 2114 | | the list if | | | | | 2115 | | it is not | | | | | 2116 | | null update | | | | | 2117 | | replicated/ | | | | | 2118 | | cached | | | | | 2119 | | object | | insert | | | 2120 | | | | response | | | 2121 | | |---------------------->| | 2122 | | | | | | | 2123 | | | | | | | 2124 | | | | 2125 +-------------------------------------------+ +------+ 2126 Figure 5.1.1.4: Node receives insert request 2128 boolean onDeliverResponse([in]Response message) 2130 @param message P2PP/RELOAD response. 2132 @return Value indicating whether to continue the standard P2PP/RELOAD 2133 processing or not. 2135 Invoked after receiving P2PP/RELOAD response. The returned value 2136 interpretation is operation type dependent. For instance if it is 2137 'false' for the insert response, it means, that the specified object 2138 MUST NOT be republished. This is useful, if it was only used to 2139 encapsulate some higher-layer-defined message. 2141 void onNeighborJoin(PeerInfo newNode, int nodeType) 2143 @param newNode Object containing such information as ID, IP address, 2144 and port number. 2146 @param nodeType Value indicating, whether new node is a client, peer, 2147 peer acting as bootstrap server, etc. 2149 Invoked after accepting other node's join request and successfully 2150 sending OK reply to it (figure 5.1.1.5). 2152 Node accepting 2153 join request New node 2154 +-----------------------------+ +------+ 2155 | | | | 2156 | RELOAD/| |RELOAD| 2157 | Application P2PP | |/P2PP | 2158 | | | | JoinRequest | | | 2159 | | |<--------------------------| | 2160 | | | | | | | 2161 | | | | OK | | | 2162 | | |-------------------------->| | 2163 | | onNeighborJoin | | | | | 2164 | |<-----------------| | | | | 2165 | | | | | | | 2166 | | | | 2167 +-----------------------------+ +------+ 2168 Figure 5.1.1.5 2170 void onNeighborLeave(PeerInfo removedNode, int nodeType) 2172 @param removedNode Object containing such information as ID, IP 2173 address, and port number. 2175 @param nodeType Value indicating, whether new node is client, peer, 2176 peer acting as bootstrap server, etc. 2178 Invoked after removing a neighbor from the neighbor table. 2180 5.1.2 Objects 2182 We propose creating a MESSAGE object type. This object could be used 2183 by the higher-layer applications to encapsulate its own messages 2184 within an insert request and make use of the overlay-specific 2185 routing. In the DHT-based networks this enables sending a message 2186 even if the exact destination's peer ID is unknown (we only know, 2187 that it should be the closest one to some given object key). It also 2188 guarantees that the message will not be routed to clients (as they 2189 are not responsible for storing objects). 2191 This object for P2PP could be described as follows: 2193 Type: MESSAGE 2194 Subtype: value indicating protocol 2195 Message: raw message bytes 2197 Below we propose the MESSAGE object's format using RELOAD semantics: 2199 Kind-Id: MESSAGE 2200 Data Model: single value 2201 Value: value indicating protocol 2202 raw message bytes 2204 The received MESSAGE objects do not necessarily have to be stored in 2205 the resource tables. Application built on top of P2PP/RELOAD MAY 2206 prevent it by capturing insert messages containing such objects using 2207 previously described callbacks and making overlay layer discard them. 2208 After that, the request originator SHOULD also use the previously 2209 described onDeliverResponse callback to prevent P2PP/RELOAD layer 2210 from republishing the object and thus resending the higher-layer 2211 message encapsulated in it. 2213 5.1.3 API 2215 We propose adding a method for calculating distance between the two 2216 given keys according to the overlay-specific metrics and hash 2217 algorithm. In our algorithm we use it for creating and maintaining 2218 the topology structure. This method could be defined as follows: 2220 int getDistance(String key1, String key2) 2222 @param key1, key2 Method calculates the distance between these keys. 2224 @return In the DHT-based networks returned value is greater or equal 2225 to 0. In unstructured ones method always returns -1. 2227 Publish-subscribe protocols built on top of the unstructured 2228 overlays, based for instance on random walks, may also require access 2229 to the routing information. This is why we propose two methods that 2230 provide it: 2232 RoutingTable getRoutingTable() 2234 @return Node's routing table. 2236 NeighborTable getNeighborTable() 2238 @return Node's neighbor table. 2240 5.2 Usage of the extension 2242 5.2.1 Objects 2244 Apart from the generic MESSAGE object we also propose to add one 2245 publish-subscribe-specific type called SUBSCRIPTIONINFO. It will be 2246 placed in network to inform other nodes about the topic existence, 2247 and help them join the multicast tree. This is essential for the 2248 unstructured overlays. 2250 For P2PP this object can be defined as follows: 2252 Type = SUBSCRIPTIONINFO 2253 Status = PENDING/ACCEPTED 2254 Peer = PeerInfo object containing peer ID, IP address and port number 2255 for the incoming publish-subscribe messages. 2257 Below we propose the SUBSCRIPTIONINFO object's format using RELOAD 2258 semantics: 2260 Kind-Id: SUBSCRIPTIONINFO 2261 Data Model: single value 2262 Value: status = PENDING/ACCEPTED 2263 peer = PeerInfo object containing peer ID, IP address and port 2264 number for the incoming publish-subscribe messages. 2266 When node wants to subscribe for some topic, it performs lookup for 2267 the SUBSCRIPTIONINFO object (giving the topic ID as a key). 2269 6. Future work 2271 We plan to provide event metadata to extend the default Interest 2272 Conditions and support advanced filters for the content-based 2273 multicast. 2275 7. IANA Considerations 2277 This document has no actions for IANA. 2279 8. References 2281 8.1 Normative references 2283 [1] S. Baset, H. Schulzrinne and M. Matuszewski, "Peer-to-Peer 2284 Protocol(P2PP)", draft-baset-p2psip-p2pp-01 (work in progress), 2285 November 19, 2007. 2287 [2] C. Jennings, B. Lowekamp, E. Rescorla, S. Baset and H. 2288 Schulzrinne, "REsource LOcation And Discovery (RELOAD)", 2289 draft-ietf-p2psip-reload-00 (work in progress), July 11, 2008. 2291 [3] S. Bradner, "Key words for use in RFCs to Indicate Requirement 2292 Levels", BCP 14, RFC 2119, March 1997. 2294 8.2 Informative references 2296 [4] P. Maymounkov and D. Mazieres, "Kademlia: A peer-to-peer 2297 information system based on the xor metric," Peer-To-Peer 2298 Systems: First International Workshop, IPTPS 2002, Cambridge, MA, 2299 USA, March 7-8, 2002: Revised Papers, 2002. 2301 [5] S. Ratnasamy, M. Handley, R. M. Karp, and S. Shenker, 2302 "Application-level multicast using content-addressable networks." 2303 in Networked Group Communication, ser. Lecture Notes inComputer 2304 Science, J. Crowcroft and M. Hofmann, Eds., vol.2233. Springer, 2305 2001, pp. 14-29. 2307 [6] A. Rowstron and P. Druschel, "Pastry: Scalable, distributed 2308 object location and routing for large-scale peer-to-peer 2309 systems," in Proc. Of the International Conference on 2310 Distributed Systems platforms(Middleware), 2001. 2312 [7] A.I.T. Rowstron, A-M. Kermarrec, M. Castro, and P. Druschel, 2313 "Scribe: The design of a large-scale event notification 2314 infrastructure." vol. 2233, pp. 30-43, 2001. 2316 [8] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. 2317 Balakrishnan, "Chord: A scalable peer-to-peer lookup service for 2318 internet applications," in SIGCOMM'01: Proceedings of the 2001 2319 conference on Applications, technologies, architectures, and 2320 protocols for computer communications. New York, NY, USA: ACM, 2321 2001, pp. 149-160. 2323 [9] Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker, 2324 "Making gnutella-like p2p systems scalable," in SIGCOMM'03: 2325 Proceedings of the 2003 conference on Applications, technologies, 2326 architectures, and protocols for computer communications. 2327 New York, NY, USA: ACM, 2003, pp. 407-418 2329 Authors' Addresses 2331 Paulina Adamska 2332 Dept. of Computer Networks 2333 Polish-Japanese Institute of Information Technology 2334 Koszykowa 86, 2335 02-008 Warsaw 2336 Poland 2338 Email: tiia@pjwstk.edu.pl 2340 Adam Wierzbicki 2341 Dept. of Computer Networks 2342 Polish-Japanese Institute of Information Technology 2343 Koszykowa 86, 2344 02-008 Warsaw 2345 Poland 2347 Email: adamw@pjwstk.edu.pl 2348 Tomasz Kaszuba 2349 Dept. of Computer Networks 2350 Polish-Japanese Institute of Information Technology 2351 Koszykowa 86, 2352 02-008 Warsaw 2353 Poland 2355 Email: kaszubat@pjwstk.edu.pl