CS551Final Project Part (1)Bill Chenghttp://merlot.usc.edu/cs551-f121 Computer Communications - CSCI 551 Copyright © William C. Cheng2Peer-to-Peer File Sharing System Computer Communications - CSCI 551 Copyright © William C. Chengthe words "packet" and "message" are interchangablePeer-to-peer: if one is using the system, one must besharing his/her resourcesApplication layer network named SERVANTmessages are sent via flooding (no loops)reply to messages are sent along the path it was receivedA→B and B→A must use the same connectionBi-directional connections between neighborsTwo types of nodesbeacon nodes: well known addresses that every nodeknows, fully connected to form the core of the networkregular nodesoperationally, beacons are just like regular nodes(except a beacon does not need to join the network)Part (1): form and maintain the network (45% project grade)3Message Types Computer Communications - CSCI 551 Copyright © William C. ChengJoinHelloKeepaliveCheck (keep things connected)StatusPart (2): think google and napster (35% project grade)StoreSearchGetDeleteNotifyCommon header4Message Format Computer Communications - CSCI 551 Copyright © William C. Cheng0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Data LengthUOIDTTLMessage Type0Probabilitically unique5UOID Computer Communications - CSCI 551 Copyright © William C. Cheng char *GetUOID( char *node_inst_id, char *obj_type, char *uoid_buf, int uoid_buf_sz) { static unsigned long seq_no=(unsigned long)1; char sha1_buf[SHA_DIGEST_LENGTH], str_buf[104]; sprintf(str_buf, "%s_%s_%1ld", node_inst_id, obj_type, (long)seq_no++); SHA1(str_buf, strlen(str_buf), sha1_buf); memset(uoid_buf, 0, uoid_buf_sz); memcpy(uoid_buf, sha1_buf, min(uoid_buf_sz,sizeof(sha1_buf))); return uoid_buf; }0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15CommonHeaderFor example, join request6Requests Computer Communications - CSCI 551 Copyright © William C. ChengHost LocationHostnamemust avoid loopsRequests are flooded to the entire SERVANT networknodes must cache a copy of any flooded messagemessage cache expires after MsgLifetime orGetMsgLifetimeUOIDPort1) for loop detection, i.e., drop duplicate messagesbased on UOID2) to route a response message to the originator of thecorresponding request messageanonymity of the message senders and message receivers0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Common HeaderFor example, join response7Responses Computer Communications - CSCI 551 Copyright © William C. ChengJoin RequestUOIDPortHostnameRan-domuse the UOID of the join request to do routingDo not know exactly who initiated the join (only know theUOID of the join request)intermediate nodes must cache a copy of the join requestmessage and which link it came from in order to send thejoin responsejoin request initiator uses JoinTimeoutstartup-14012.ini[init]InitNeighbors=2MinNeighbors=1[beacons]nunki:14012=nunki:14013=nunki:14014=nunki:14015=8Network Formation Computer Communications - CSCI 551 Copyright © William C. Chengbeacon nodes are fully connectednunki:14013nunki:14012nunki:14014nunki:14015beacon noderegular nodeneighborstemporaryconnectionstartup-14012.ini[init]InitNeighbors=2MinNeighbors=1[beacons]nunki:14012=nunki:14013=nunki:14014=nunki:14015=send join request to a beacon9Join Computer Communications - CSCI 551 Copyright © William C. Chengnunki:14013nunki:14012nunki:14014nunki:14015beacon noderegular nodeneighborstemporaryconnectionnunki:14007startup-14007.ini[init]InitNeighbors=2MinNeighbors=1[beacons]nunki:14012=nunki:14013=nunki:14014=nunki:14015=join reqbeacon nodes are fully connectedstartup-14012.ini[init]InitNeighbors=2MinNeighbors=1[beacons]nunki:14012=nunki:14013=nunki:14014=nunki:14015=join request is flooded to thewhole network, send join reply10Join Computer Communications - CSCI 551 Copyright © William C. Chengnunki:14013nunki:14012nunki:14014nunki:14015beacon noderegular nodeneighborstemporaryconnectionjoin rply(distance=2781)flooding join reqstartup-14007.ini[init]InitNeighbors=2MinNeighbors=1[beacons]nunki:14012=nunki:14013=nunki:14014=nunki:14015=send join request to a beaconbeacon nodes are fully connectedflooding stopped if packetalready seen11Join Computer Communications - CSCI 551 Copyright © William C. Chengnunki:14013nunki:14012nunki:14014nunki:14015beacon noderegular nodeneighborstemporaryconnectionflooding join reqjoin rply(distance=557)join rply(distance=1022)join rply(distance=71)startup-14012.ini[init]InitNeighbors=2MinNeighbors=1[beacons]nunki:14012=nunki:14013=nunki:14014=nunki:14015=startup-14007.ini[init]InitNeighbors=2MinNeighbors=1[beacons]nunki:14012=nunki:14013=nunki:14014=nunki:14015=join request is flooded to thewhole network, send join replysend join request to a beaconbeacon nodes are fully connected12Join Computer Communications - CSCI 551 Copyright © William C. Chengnunki:14013nunki:14012nunki:14014nunki:14015beacon noderegular nodeneighborstemporaryconnectionstartup-14012.ini[init]InitNeighbors=2MinNeighbors=1[beacons]nunki:14012=nunki:14013=nunki:14014=nunki:14015=nunki:14012 (2781)nunki:14015 (1022)nunki:14013 (557)nunki:14014 (71)nunki:14007init_neighbor_listnunki:14013nunki:14014sort replies, write bottom ones toinit_neighbor_list in HomeDirectorystartup-14007.ini[init]InitNeighbors=2MinNeighbors=1[beacons]nunki:14012=nunki:14013=nunki:14014=nunki:14015=flooding stopped if packetalready seenjoin request is flooded to thewhole network, send join replysend join request to a beaconbeacon nodes are fully connected13Hello Computer Communications - CSCI 551 Copyright © William C. Chengnunki:14013nunki:14012nunki:14014nunki:14015beacon noderegular nodeneighborstemporaryconnectionstartup-14012.ini[init]InitNeighbors=2MinNeighbors=1[beacons]nunki:14012=nunki:14013=nunki:14014=nunki:14015=nunki:14007init_neighbor_listnunki:14013nunki:14014restart, no need to join, just sayhellostartup-14007.ini[init]InitNeighbors=2MinNeighbors=1[beacons]nunki:14012=nunki:14013=nunki:14014=nunki:14015=sort replies, write bottom ones toinit_neighbor_list in HomeDirectoryflooding stopped if packetalready seenjoin request is flooded to thewhole network, send join replysend join request to a beaconbeacon nodes are fully connectedhello14Hello Computer Communications - CSCI 551 Copyright © William C. Chengnunki:14013nunki:14012nunki:14014nunki:14015beacon noderegular
View Full Document
Unlocking...