P2PSIP L. Huang Internet-Draft ZST University Intended status: Standards Track Expires: January 28, 2009 Location and Discovery of Subsets of Resources Status of this Memo Distribution of this memo is unlimited. By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract This file is a proposal for location and discovery of filter resources selected by search-conditions. The peers,which are virtually grouped, construct n-tuple overlay virtual hierarchical tree overlay network. With cached addresses of peers, the overload of traffic in tree structure can be avoided. The resources are classified into hierarchical domains, and registered into the peers which are located in the same domain virtual groups as the resources'. This proposal supports flexible queries by a SQL-like query statement. Huang, Lican Expires January 2008 FORMFEED[Page 1] Internet Draft location of subsets of resources July 27, 2008 Table of Contents 1. Introduction .....................................................2 2. Resource Register and Retrieve Language ..........................2 2.1 SQL-like Query language ......................................2 2.2 SQL-like Maintanence Language.................................4 3. Implementation of location and discovery of subsets of resources.4 3.1 VIRGO for SIP.................................................4 3.1.1 Terminology..............................................5 3.1.2 Illustration Example.....................................6 3.1.3 Maintenance of VIRGO for SIP.............................8 3.1.4 Locating Authoritative Peer............................10 3.1.5 Agent of Authoritative Peer ............................12 4. Security considerations..........................................13 5. IANA Considerations..............................................13 6. References ......................................................13 6.1. Normative References ......................................13 6.2. Informative References ....................................13 1. Introduction This file is a proposal for location and discovery of subsets of resources selected by search-conditions. The goal of this proposal aims to enhance the functions of REsource LOcation And Discovery (RELOAD)"[RELOAD]. The applications using SIP protocols always need to locate subsets of resources. This subsets of resources may be related in same social groups, etc. This document gives a strategy to use SQL-like language to select these subsets of resources. The Implementation of this strategy uses modified VIRGO[VIRGO] overlay network. VIRGO is a multi-tuple virtual hierarchical overlay network with cached node address. The lookup protocols is similar as the protocols in VIRGO[VIRGO], which is also illustrated in the paper[P2PSD]. 2. Resource Register and Retrieve Language The convention of resources is formed as global-hier-part"/"local- name. Here global-hier-part is formed as domain names, which are global unique names. The local-name is formed as Entity.Attribute. 2.1 SQL-like Query language query::=SELECT{SUBDOMAIN|ENTITY|ATTRIBUTE|*|expr[[AS]c_alias] {,expr[[AS]c_alias]...}} Huang, Lican Expires January 2008 FORMFEED[Page 2] Internet Draft location of subsets of resources July 27, 2008 FROM domainref [WHERE search_condition]; Here, SUBDOMAIN is for querying subdomain for a given super Domain; ENTITY is for querying all entities for a given search condition ; ATTRIBUTE is for querying all attributes for a given search condition ;expr is for the property queried, which may be a set of properties; [AS] c_alias is the alias name for expr; domainref is for Domain Name, in which we can use * to indicate all sub domains; search_condition is similar to SQL statement in Database. Supposing there exists a network of music, which contains Britney.popular.music. In the following, there are several examples of query operations. Operation 1 The form "global-hier-part/Entity?" is to query all resources in the global-hier-parts domain. For example, "Britney.popular.music/FAN?" queries all fans of Britney Spears. We can use the following Statement: SELECT * FROM Britney.popular.music where ENTITY= "FAN"; Operation 2 Suppose that global-hier-part can be expressed as leafDomain.superDomain. The form "?.superDomain/" is to query all leafDomains. This is possible because of the hierarchical structure and the protocols. For example, "?.popular.music" queries all sun domains of all popular singers. We can use the following Statement: SELECT SUBDOMAIN FROM *.popular.music; Operation 3 The form "global-hier-part/local-name" is to query specific resource. For example, "Britney.popular.music/FAN.Alice" queries the information of Alice -- fans of Britney. We can use the following Statement: SELECT * FROM Britney.popular.music WHERE ENTITY ='FAN'AND ATTRIBUTE = "NAME"AND NAME= Alice ; Operation 4 Huang, Lican Expires January 2008 FORMFEED[Page 3] Internet Draft location of subsets of resources July 27, 2008 The form "global-hier-part/expression" is to query the resources which satisfy the conditions of the expression indicated. Expression can be scope, maximum, minimum, where condition like SQL statements. For example, "Britney.popular.music/FAN where sex = female" queries all fans of Britney Spears who are female. We can use the following Statement: SELECT * FROM Britney.popular.music WHERE ENTITY ='FAN'AND ATTRIBUTE = "SEX" AND SEX = female; 2.2 SQL-like Maintanence Language The resources are maintained by the SQL-like maintenance language. Insert statement registers new resources into the domain. Delete statement drops the resource registration from the domain. Update statement changes the information registered in the domain. The formats of these statements are as the following: DELETE FROM domainref [WHERE search_condition]; INSERT INTO domainref[(entity.attribute{, entity.attribute...})] {VALUES (expr | NULL {,expr |NULL...}) ; UPDATE domainref SET entity.attribute = expr |NULL{, entity.attribute = expr|NULL ...}; For example, the following statement deletes all female fans of Britney Spears. DELETE FROM Britney.popular.music WHERE ENTITY="FAN"AND ATTRIBUTE = "SEX" AND SEX = female; 3. Implementation of location and discovery of subsets of resources. 3.1 VIRGO for SIP Virtual Hierarchical Tree Gird Organizations(VIRGO) for SIP is a hybrid of unstructured P2P and structured P2P technologies. The Peers construct multi-tuple Virtual Hierarchical Overlay Network. Some peers are only leaves of the network, others may coexist in different layers. These peers form a duplicated virtual hierarchical tree, with Huang, Lican Expires January 2008 FORMFEED[Page 4] Internet Draft location of subsets of resources July 27, 2008 one root layer, several middle layers, and many leaf virtual nodes. Random connections cached in a peer's routing table are maintained. The peers within the same groups are fully connected. VIRGO for SIP routes request message to the peer with theoretical least hops from destination peer. The route tables of peers contains two kinds of route addresses, tree addresses, which are prerequiste, and cached addresses. 3.1.1 Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT","SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. The following is some terms related to the Virtual Hierarchical Overlay Network for SIP. Registered Resource Database(RRDB): The resouce information organized by entities and attributes. Peer: Peer is a node which MUST keep registered resource database(RRDB) and route table. PeerID: Hierarchical domain name. For example. music.popular.Britney. Peer Node Entity(PNE): PNE contains following sections. +------------+------------------------------------------------------+ |Section Name| Description | +------------+------------------------------------------------------+ |PeerID |Peer ID, formed as domain name | +------------+------------------------------------------------------+ |TYPE |route TYPE codes (TREE as 0, CHACHE as 1) | +------------+------------------------------------------------------+ |GUL |the value of gateway upmost layer of the Peer | +------------+------------------------------------------------------+ |TTL |the time interval that the route record may be cached | | |before the source of the information should again be | | |consulted. | +------------+------------------------------------------------------+ |UTS |Unreachable time stamp.If the route was cached, then | | |reflesh it by TTL rule.If the route is gateway node in| | |virtual tree structure,notice to manager to repair it.| +------------+------------------------------------------------------+ |IPADDRESSes |IP addresses of the replicated Peers | +------------+------------------------------------------------------+ Huang, Lican Expires January 2008 FORMFEED[Page 5] Internet Draft location of subsets of resources July 27, 2008 Route Table : It is consisted of multiple PNEs. Client: Host in which user program maintains,locates and discovers resources. Local Peer: The peer Client firstly attached. Foreign Peer: The peer Client detached. Authoritative Peer: The peer keeps requested resources in its RRDB. Authoritative Peer controls the subdomains like DNS zone[RFC1035]. Replicated Peer: The peer can be replicated by machines with different IP addresses, but all with same contents in their RRDB and route tables. Gateway Role: Peer with gateway role takes part in routing functions in several different layers of virtual groups. All the Peers are the same except some peers take the function of gateways in the meantime. Gateway uppermost layer (GUL ): GUL is the uppermost virtual group layer that the gateway is in. The layers are ordered from root layer which is labelled as level 1. Virtual group: Virtual group is formed virtually by peers; and virtual groups in the upper layer are formed by the peers with the gateway role. N-tuple virtual group tree: N-tuple virtual group tree is a hierarchical tree formed by virtual groups. Among the nodes of the lower layer virtual groups, N-tuple gateway nodes in each group are chosen to form upper-layer groups, and from the nodes of these upper- layer groups to form upper-upper-layer groups in the same way, and this way is repeated until a root-layer group is formed. 3.1.2 Illustration Example We here give an illustration example about music. The music in classified into popular and classic music and sub domains as shown in the following figure. Peer A (IP address 10.31.21.5) keeps the informations about Britney, such as Fans, songs, tc, so it is classified as the group of music.popular.Britney Huang, Lican Expires January 2008 FORMFEED[Page 6] Internet Draft location of subsets of resources July 27, 2008 Peer B (IP address 210.12.56.125 ) keeps the informations about Britney and Madanna, so it is classified as the groups of music.popular .Britney and music.popular. Peer C (IP address 78.2.127.45) keeps the informations of Beethoven, so it is classified as the group of music.classic.Beethoven +----------+ | music | +----------+ | Peer A | | Peer C | +----------+ | | _________________|_________________ | | | | +----------+ +---------+ | popular | | classic | +----------+ +---------+ | Peer A | | Peer C | | Peer B | | | +----------+ +---------+ | | | | | | ------------------ | | | | | | | +----------+ +----------+ +-----------+ | Britney | | Madonna | | Beethoven | +----------+ +----------+ +-----------+ | Peer A | | Peer B | | Peer C | +----------+ +----------+ +-----------+ (1) Route table of Peer A music.popular.Madonna TREE 2 NULL NULL 210.12.56.125 music.classic.Beethoven TREE 1 NULL NULL 78.2.127.45 Huang, Lican Expires January 2008 FORMFEED[Page 7] Internet Draft location of subsets of resources July 27, 2008 (2) Route table of Peer B music.popular.Britney TREE 1 NULL NULL 10.31.21.5 (3) Route table of Peer C music.popular.Britney TREE 1 NULL NULL 10.31.21.5 3.1.3 Maintenance of VIRGO for SIP In VIRGO for SIP, all Peers formed into N-tuple virtual group tree. The Virtual Hierarchical Overlay Network can be established by manual or automatedly by establishment protocol which is shown as following: 3.1.3.1 Primitives and Functions sender.send (message,receiver), sender sends message to receiver sender.send(message,receiver (- Set), sender sends message to all the receivers belong to a Set RouteTableAdd(PNE,type), add PNE to route table RouteTableDelete(PNE), delete PNE from route table lookup_location(PeerID),find the authoritative peer's location LengthOfSamePrefix(PeerID,PeerID), length of shared prefixes between two peers LengthOfPeerID(PeerID), the length of PeerID hopDistance2object(pi,PeerID), the theoretical hops from the peer to the authoritative peer selectRouteNodeFromRouteTable(PeerID), choose next hop node from route table checkupRRDB(QUERYMESSAGE), retrieve resources in RRDB 3.1.3.2 Setup first peer Set GUL in peer's PNE value 1. 3.1.3.3 Peer Join Huang, Lican Expires January 2008 FORMFEED[Page 8] Internet Draft location of subsets of resources July 27, 2008 Peers are virtually architectured as Tree Structure. Some peers take roles of gateways. When a peer joins the network, it first finds one of peers which share the maxmium prefixs with the joining peer, then the joining peer sends the JOINMESSAGE to the latter,the latter will broadcast the message to all peers in the virtual group. Here, a new peer P_join joins the network. 1. P_join finds one of peers-- P_groupToJoin, which belongs to virtual group--joinGroup and shares maximium prefixs with P_join. 2. P_join.send(JOINMESSAGE, P_groupToJoin); 3. P_groupToJoin.send(JOINMESSAGE, pi (- joinGroup); 4. (pi (- joinGroup).send(pi.CONFIRMATIONMESSAGE, P_join); (pi (- joinGroup).RouteTableAdd(P_join.PNE,TREE); 5. P_join.RouteTableAdd((pi (- joinGroup).PNE,TREE); 6. set joinGroup to one upper layer group; 7. set P_groupToJoin = pi (- joinGroup; 8. repeat step 2 to 7 until replicated nodes no less than n-tuple in joinGroup or joinGroup is root group. 3.1.3.4 Peer Leave Here, a leaving peer P_leave , which belongs to virtual group--leftFromGroup, leaves the network. 1. P_leave finds the most top layer virtual group within -- leftFromGroup. 2. P_leave .send(LEAVEMESSAGE,pi (- leftFromGroup); 3. (pi (- leftFromGroup).send(pi.CONFIRMATIONMESSAGE, P_leave ); (pi (- leftFromGroup).RouteTableDelete(P_leave .PNE); 4. set leftFromGroup to one lower layer group; 5. repeat step 2 to 4 until the most bottom group the leaving peer Huang, Lican Expires January 2008 FORMFEED[Page 9] Internet Draft location of subsets of resources July 27, 2008 within. 3.1.4 Locating Authoritative Peer Every Peer is the same but some coexist in more than one layer. Every Peer maintains a route table. Route table includes addresses of Foreign Peers which are prerequiste for Virtual Hierarchical Overlay Network and cached addresses of Foreign Peers which are refreshed by TTL rule. The query process is shown as the following figure. | Foreign | Client | | +-------+ +--------+ | +-------+ +-------+ | | user queries | |queries | | | | | |User |------------->| Local |---------|->|Foreign|-->| Tree +| |Program| | Peer | | |Peer | | Cache | | |<-------------| |<--------|--| |<--|(route | | |user responses| |responses| | | | table)| +-------+ +--------+ | +-------+ +-------+ | A A | | Route cache operations | | |___________|____ | | | | | | V | | | V +----------------+ | +--------+ +------+ | Tree + | | |Authori-| | | | Cache | | |tative |-->|RRDB | | (route table) | | |Peer |<--| | +----------------+ | | | | | | +--------+ +------+ The query process is as the following: User program sends QUERY MESSAGE to Local Peer. If Local Peer is the Authoritative Peer, then Local Peer will check its RRDB to resolve the request resources. Otherwise, The Local Peer will routes to the Foreign Peer which is closer to the Authoritative Peer by calculating theoretical hops. Then the Foreign Peer routes to the even closer Foreign Peer. Repeat this process, until the Authoritative Peer has been found. Finally, the Authorirative Peer retrieves request resources by check Huang, Lican Expires January 2008 FORMFEED[Page 10] Internet Draft location of subsets of resources July 27, 2008 its RRDB, and responses to the Local Peer. The latter will forward the response to the User Program. 3.1.4.1 lookup protocol Step 1 UserProgram.send (QUERYMESSAGE, LocalPeer) Step 2 authoritativePeer = LocalPeer.lookup_location(QUERYMESSAGE.PeerID) Step 3 RESULTMESSAGE= authoritativePeer.checkupRRDB(QUERYMESSAGE); Step 4 authoritivePeer=send(RESULTMESSAGE, LocalPeer); Step 5 LocalPeer.send(RESULTMESSAGE, UserProgram); Step 6 LocalPeer.RouteTableAdd(authoritativePeer.PNE,CHACHE); Where, function of lookup_location (locates the authoritative peer by the minimum hops) is as following: Function p.lookup_location(QUERYMESSAGE) { if LengthOfSamePrefix(p.PeerID,QUERYMESSAGE.PeerID)== LengthOfPeerID(QUERYMESSAGE.PeerID)-1 return p; else { routeP = p.selectRouteNodeFromRouteTable(QUERYMESSAGE.PeerID); p.send(QUERYMESSAGE,routeP); if (message sending is successful) routeP.lookup_location(QUERYMESSAGE); else { Mark routeP as unreachable in p.routetable; Huang, Lican Expires January 2008 FORMFEED[Page 11] Internet Draft location of subsets of resources July 27, 2008 p.lookup_location(QUERYMESSAGE); } } } Where, function selectRouteNodeFromRouteTable(select route with theoretical least hops from authoritative peer) is as following: Function p.selectRouteNodeFromRouteTable(requestPeerID) gnSet = Minimum(p.hopDistance2object(pi (- RouteTable,requestPeerID)); return routeP = random(gnSet); Where, function hopDistance2object (calculating theoretical hops from authoritative peer ) is as following: Function p.hopDistance2object(pi,requestPeerID) if LengthOfSamePrefix(pi.DNSI, requestPeerID) ==1 return LengthOfDomainName(requestPeerID)+pi.GUL -3; elseif pi.GUL < LengthOfSamePrefix(pi.PeerID, requestPeerID) return LengthOfDomainName(requestPeerID) - LengthOfSamePrefix(pi.PeerID, requestPeerID)-1; else return LengthOfDomainName(requestPeerID)+pi.GUL - 2*LengthOfSamePrefix(pi.PeerID,requestPeerID)-1 3.1.5 Agent of Authoritative Peer When Authoritative Peer receives query or maintenance message, the agent will resolve the SQL-like statement in the message and deal this statement with RRDB. 4. Security considerations The security considerations should be taken into account in the Huang, Lican Expires January 2008 FORMFEED[Page 12] Internet Draft location of subsets of resources July 27, 2008 implementation of message and registered resource database (RRDB). 5. IANA Considerations This memo includes no request to IANA. 6. References 6.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC1035] Mockapetris, P., "DOMAIN NAMES - IMPLEMENTATION AND SPECIFICATION",Specification," RFC1035, USC/Information Sciences Institute,November, 1987. 6.2. Informative References [VIRGO] Huang, L., "VIRGO: Virtual Hierarchical Overlay Network for Scalable Grid Computing ",Proc. European Grid Conference(EGC2005), in LNCS 3470, p911-921, 2005. [P2PSD] Huang, L., "A P2P service discovery strategy based on content catalogues", Data Science Journal, Vol(6), 2007, ppS492-S499. http://www.jstage.jst.go.jp/article/dsj/6/0/S492/_pdf [Lican] Lican Huang, "draft-licanhuang-dnsop-distributeddns-04.txt" (work in progress) , June 2008. [LicanICCS] Lican Huang, "Resource Discovery Based on VIRGO P2P Distributed DNS Framework", ICCS 2008, LNCS 5103 pp:501-509 [RELOAD] C. Jennings, B. Lowekamp, E. Rescorla,S. Baset, H. Schulzrinne, "REsource LOcation And Discovery (RELOAD)",draft-ietf-p2psip-reload-00.txt (work in progress) , July 2008. Huang, Lican Expires January 2008 FORMFEED[Page 13] Internet Draft location of subsets of resources July 27, 2008 Authors' Addresses Lican Huang Current Address: Institute of Network & Distributed Computing, Zhejiang Sci_Tech University, Hangzhou, P.R.China EMail: licanhuang@zist.edu.cn; huang_lican@yahoo.co.uk Huang, Lican Expires January 2008 FORMFEED[Page 14] Internet Draft location of subsets of resources July 27, 2008 Full Copyright Statement Copyright (C) The IETF Trust (2008). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST, AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Acknowledgement Funding for the RFC Editor function is currently provided by the Internet Society. Huang, Lican Expires January 2008 FORMFEED[Page 15]