P2PSIP L. Huang Internet-Draft ZST University Intended status: Standards Track Expires: July 12, 2009 January 13, 2009 Location and Discovery of Subsets of Resources draft-licanhuang-p2psip-subsetresourcelocation-01.txt Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on July 12, 2009. Copyright Notice Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license- info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Abstract This file is a proposal for location and discovery of filter resources Huang, Lican Expires July 12, 2009 FORMFEED[Page 1] Internet Draft location of subsets of resources January 2009 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 July 12, 2009 FORMFEED[Page 2] Internet Draft location of subsets of resources January 2009 Table of Contents 1. Introduction .....................................................3 2. Resource Register and Retrieve Language ..........................3 2.1 SQL-like Query language ......................................3 2.2 SQL-like Maintanence Language.................................5 3. Implementation of location and discovery of subsets of resources.5 3.1 VIRGO for SIP.................................................5 3.1.1 Terminology..............................................6 3.1.2 Illustration Example.....................................8 3.1.3 Maintenance of VIRGO for SIP............................10 3.1.4 Locating Authoritative Peer............................11 3.1.5 Agent of Authoritative Peer ............................14 4. Security considerations..........................................14 5. IANA Considerations..............................................14 6. References ......................................................14 6.1. Normative References ......................................14 6.2. Informative References ....................................15 Author's Address ....................................................15 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 userID@global-hier- part"/"local-name. Here userID@global-hier-part is user's machine ID; 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 Huang, Lican Expires July 12, 2009 FORMFEED[Page 3] Internet Draft location of subsets of resources January 2009 query::=SELECT{SUBDOMAIN|ENTITY|ATTRIBUTE|*|expr[[AS]c_alias] {,expr[[AS]c_alias]...}} 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 ; Huang, Lican Expires July 12, 2009 FORMFEED[Page 4] Internet Draft location of subsets of resources January 2009 Operation 4 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 Huang, Lican Expires July 12, 2009 FORMFEED[Page 5] Internet Draft location of subsets of resources January 2009 peers are only leaves of the network, others may coexist in different layers. These peers form a duplicated virtual hierarchical tree, with 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, Alice@music.popular.Britney. Huang, Lican Expires July 12, 2009 FORMFEED[Page 6] Internet Draft location of subsets of resources January 2009 Peer Node Entity(PNE): PNE contains following sections. +------------+------------------------------------------------------+ |Section Name| Description | +------------+------------------------------------------------------+ |PeerID |Peer ID, formed as userID@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 | +------------+------------------------------------------------------+ 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. Huang, Lican Expires July 12, 2009 FORMFEED[Page 7] Internet Draft location of subsets of resources January 2009 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 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 Huang, Lican Expires July 12, 2009 FORMFEED[Page 8] Internet Draft location of subsets of resources January 2009 +----------+ | 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 (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 Huang, Lican Expires July 12, 2009 FORMFEED[Page 9] Internet Draft location of subsets of resources January 2009 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 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 Huang, Lican Expires July 12, 2009 FORMFEED[Page 10] Internet Draft location of subsets of resources January 2009 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 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 Huang, Lican Expires July 12, 2009 FORMFEED[Page 11] Internet Draft location of subsets of resources January 2009 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 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) Huang, Lican Expires July 12, 2009 FORMFEED[Page 12] Internet Draft location of subsets of resources January 2009 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; p.lookup_location(QUERYMESSAGE); } } } Where, function selectRouteNodeFromRouteTable(select route with theoretical least hops from authoritative peer) is as following: Function p.selectRouteNodeFromRouteTable(requestPeerID) gnSet = Huang, Lican Expires July 12, 2009 FORMFEED[Page 13] Internet Draft location of subsets of resources January 2009 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 implementation of message and registered resource database (RRDB). 5. IANA Considerations This memo includes no request to IANA. 6. References 6.1. Normative References Huang, Lican Expires July 12, 2009 FORMFEED[Page 14] Internet Draft location of subsets of resources January 2009 [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. 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 July 12, 2009 FORMFEED[Page 15] Internet Draft location of subsets of resources January 2009 Huang, Lican Expires July 12, 2009 FORMFEED[Page 16]