[chord] Forward: Re: REMINDER: Chord MACEDON Specification
Frans Kaashoek
kaashoek at csail.mit.edu
Thu Oct 7 23:43:05 EDT 2004
----- Forwarded message from Charles Killian <ckillian at cs.duke.edu> -----
Date: Thu, 07 Oct 2004 20:31:05 -0700
From: Charles Killian <ckillian at cs.duke.edu>
To: Frans Kaashoek <kaashoek at csail.mit.edu>
Subject: Re: REMINDER: Chord MACEDON Specification
Message-ID: <416609F9.60602 at cs.duke.edu>
Hi Frans --
I'm sorry I have taken so long to follow up with you. I hope the move
went successfully. I did want to let you know I'm going ahead and
releasing our chord specification, with notes that there may be mistakes
in it which we have not noticed yet, and that as we get more feedback
I'll include it with the distribution. Whenever you get the chance to
respond (and I understand it may take some time to page things back in),
I'll appreciate it.
Thanks -
Chip
Frans Kaashoek wrote:
>Chip,
>
>there are some detailed comments coming from our end. unfortunately,
>we don't have any offices today (since we are moving), it probably
>take a couple more days. sorry.
>
> Frans
>
>On Thu, 18 March 2004 at 16:01 (-0500), Charles Killian wrote:
>
>
>>Thanks Ion --
>>
>>I appreciate you taking a look at it. It's a very helpful sanity check
>>for us to make sure we are on the same page. I'll make these notations,
>>and then prepare to include it in the next release.
>>
>>--Chip
>>
>>
>>
>>Ion Stoica wrote:
>>
>>
>>
>>>Chip,
>>>
>>>I looked briefly over the code, and I have not spotted any
>>>bug. However, I have two comments though:
>>>
>>>- It appears that the code implements only a successor list of size
>>>two, right? Anyway, I think you should mention what is the size of
>>>the successor list under "Notes:"
>>>
>>>- In your code, fix_fingers invokes update_others. This is not
>>>incorrect, but it is not in the original Chord pseudocode
>>>in the SIGCOMM paper. update_others is called only when the node
>>>joins. And then update_others is invoked for *all* nodes who have n
>>>as a finger. Also note that in the ToN paper we have eliminated
>>>update_others altogether. Again, the code is not incorrect, but I
>>>would mention this difference under "Notes:"
>>>
>>>Best,
>>>
>>>Ion
>>>
>>>Charles Killian wrote:
>>>
>>>
>>>
>>>>Good morning --
>>>>
>>>>Below is a copy of the email I sent two weeks ago. Since I haven't
>>>>heard from you yet -- I wanted to remind you we'll be publishing our
>>>>Chord specification soon, but we'd like to get some feedback from you
>>>>first. If you have any questions or comments, I'd love to hear them.
>>>>
>>>>Thanks -
>>>>Chip
>>>>
>>>>encl: Original email follows, chord specification file, and MACEDON
>>>>manual.
>>>>
>>>>Attached we have included the MACEDON specification for Chord, and a
>>>>manual which describes MACEDON in a bit more detail. It is our hope that
>>>>you will take some time in the next two weeks to look over it. We
>>>>believe it to be a mostly accurate representation of the chord
>>>>algorithms (exceptions noted inside the specification), and we intend to
>>>>use it as the basis for comparisons with other specifications we or
>>>>others have written. On Wednesday, March 17th, we would also like to
>>>>make it available for download from the MACEDON website, with your
>>>>consent if possible.
>>>>
>>>>To fully make use of and understand the specifications, it is our hope
>>>>that you will also download the currently available MACEDON package at
>>>>http://macedon.kcubes.com/ . We also welcome you to join the
>>>>MACEDON-Announce listserve (at
>>>>http://www.kcubes.com/cgi-bin/mailman/listinfo/macedon-announce), where
>>>>we announce new versions of the package that are released, and other
>>>>important information.
>>>>
>>>>We look forward to discussing this specification with you. Please
>>>>email macedon at kcubes.com with questions or comments.
>>>>
>>>>Thank you --
>>>>Chip Killian
>>>>
>>>>
>>>>------------------------------------------------------------------------
>>>>
>>>>//Copyright (c) 2004, Charles Killian, Adolfo Rodriguez, Dejan
>>>>Kostic, Sooraj Bhat, and Amin Vahdat
>>>>//All rights reserved.
>>>>//
>>>>//Redistribution and use in source and binary forms, with or without
>>>>//modification, are permitted provided that the following conditions
>>>>are met:
>>>>//
>>>>// * Redistributions of source code must retain the above copyright
>>>>// notice, this list of conditions and the following disclaimer.
>>>>// * Redistributions in binary form must reproduce the above copyright
>>>>// notice, this list of conditions and the following disclaimer in
>>>>// the documentation and/or other materials provided with the
>>>>// distribution.
>>>>// * Neither the names of Duke University nor The University of
>>>>// California, San Diego, nor the names of its contributors
>>>>// may be used to endorse or promote products derived from
>>>>// this software without specific prior written permission.
>>>>//
>>>>//THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
>>>>"AS IS"
>>>>//AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
>>>>TO, THE
>>>>//IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
>>>>PURPOSE ARE
>>>>//DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
>>>>BE LIABLE
>>>>//FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
>>>>CONSEQUENTIAL
>>>>//DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
>>>>GOODS OR
>>>>//SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
>>>>HOWEVER
>>>>//CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
>>>>LIABILITY,
>>>>//OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
>>>>OF THE
>>>>//USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
>>>>DAMAGE.
>>>>
>>>>/**
>>>>Implementation of the Chord protocol
>>>>Adolfo Rodriguez
>>>>
>>>>Notes:
>>>>This implementation currently only supports:
>>>>- 32-bit hash addresses
>>>>- Fixed stabilize and fix-finger timeouts
>>>>- Recursive forwarding
>>>>**/
>>>>
>>>>#include "scribe-ext.h"
>>>>#include "macedon_cache.h"
>>>>
>>>>protocol chord
>>>>
>>>>addressing ip
>>>>
>>>>trace_off
>>>>
>>>>constants {
>>>>int BITS = 32;
>>>>double STABLE_TIMEOUT = 0.3; // stabilize timer
>>>>int FIX_TIMEOUT = 1; // fix_fingers timer
>>>>// int FIX_TIMEOUT = 20;
>>>>int JOIN_TIMEOUT = 10; // initial join timer
>>>>int PRINT_TIMEOUT = 2; // for debugging
>>>>}
>>>>
>>>>states {
>>>>joining;
>>>>joined;
>>>>}
>>>>
>>>>neighbor_types {
>>>>finger 1 {
>>>> int start; // the range for this finger
>>>> int hashf; // the hash of this finger
>>>>}
>>>>}
>>>>
>>>>transports {
>>>>TCP HIGH;
>>>>TCP LOW;
>>>>}
>>>>
>>>>messages {
>>>>HIGH find_pred { // used to find the predecessor of an ID
>>>> int id; // the hash in question (the one whose predecessor we want)
>>>> int who; // who originated the query (IP)
>>>>}
>>>>HIGH find_pred_reply { // response to find_pred
>>>> int pred_id; // the hash of the predecessor
>>>> int succ; // the successor's IP
>>>> int succ_id; // the hash of the successor
>>>> finger pf BITS; // my routing table
>>>>}
>>>>HIGH get_pred { // queries a node for its predecessor and successor
>>>>} HIGH get_pred_reply { // returns the requested information
>>>> int pred;
>>>> int pred_id;
>>>> int succ;
>>>> int succ_id;
>>>>}
>>>>HIGH update_pred { // instructs a node to potentially update its
>>>>predecessor
>>>> int id; // hash of the sending node
>>>>}
>>>>HIGH update_others { // instructs others to potentially correct an
>>>>entry
>>>> int id; // where i am sending this request
>>>> int node; // sender's hash
>>>> int who; // sender's IP address
>>>>}
>>>>HIGH update_ft { // an "other" sends this msg back to its
>>>>predecessor to
>>>> // checks its routing table for any related changes
>>>> int node; // sender's hash
>>>> int who; // sender's IP address
>>>>}
>>>>LOW data {
>>>> int receiver_hash;
>>>> int sender_hash;
>>>> int sender_ip;
>>>> int priority;
>>>>}
>>>>LOW data_path_req { // solicits a mapping message
>>>> int receiver_hash;
>>>> int sender_hash;
>>>> int sender_ip;
>>>> int priority;
>>>>}
>>>>HIGH mapping { // Mappings are used to populate the location cache
>>>> int low_hash;
>>>> int high_hash;
>>>> int map_ip;
>>>>}
>>>>}
>>>>
>>>>
>>>>state_variables { int myhash;
>>>>// disable failure detection for now
>>>>// fail_detect finger myfinger BITS;
>>>>// fail_detect finger pred;
>>>>finger myfinger BITS; // routing table
>>>>finger pred; // predecessor entry
>>>>mac_cache map; // location cache
>>>>finger successors_succ; // for error recovery
>>>>timer stabilize STABLE_TIMEOUT;
>>>>timer fix_fingers FIX_TIMEOUT;
>>>>timer printer PRINT_TIMEOUT;
>>>>timer join;
>>>>}
>>>>transitions {
>>>>
>>>>init API init { // called to initialize protocol
>>>> int i, id, start, adjusted, max = (int)pow(2,BITS);
>>>> neighbor_finger *myent;
>>>>
>>>> myhash = hashof(me); print_addr(myhash);
>>>> neighbor_add(pred,me); // just me so far in ring
>>>> myent = neighbor_entry(pred,me);
>>>> myent->hashf = myhash;
>>>>
>>>> for (i=0; i<BITS; i++) { // initializes all finger entries to me
>>>> neighbor_add(myfinger[i],me);
>>>> myent = neighbor_entry(myfinger[i],me);
>>>> myent->hashf = myhash;
>>>> start = (int)pow(2,i); adjusted = start + myhash;
>>>> myent->start = adjusted % max; // the start address of this finger
>>>> }
>>>> timer_resched(printer, PRINT_TIMEOUT); // for debugging
>>>> if (source_ == me) { // i am the bootstrap
>>>> state_change(joined); // consider self joined
>>>> replay_experiment();
>>>> timer_resched(stabilize, STABLE_TIMEOUT); // schedule maintenance
>>>> timer_resched(fix_fingers, FIX_TIMEOUT);
>>>> }
>>>> else { // not the bootstrap
>>>> state_change(joining); // just joining
>>>> id = myhash + 1; // route find pred to just beyond me
>>>> replay_init();
>>>> route_find_pred(source_, id, me, 0, 0, -1);
>>>> timer_resched(join, JOIN_TIMEOUT); // my request could get lost
>>>> }
>>>> upcall_notify(pred,NBR_TYPE_PEER);
>>>>}
>>>>
>>>>joining timer join { // retry if my request was lost
>>>> int id = myhash + 1;
>>>> route_find_pred(source_, id, me, 0, 0, -1);
>>>> timer_resched(join, JOIN_TIMEOUT);
>>>>}
>>>>
>>>>
>>>>joined recv find_pred {
>>>> int succ, succ_hash, nextguy, done;
>>>> neighbor_finger *myent;
>>>> done = 0;
>>>> myent = neighbor_random(myfinger[0]); // gets the successor
>>>>
>>>> if (isinrange(field(id), myhash, myent->hashf)) { // arrived at
>>>>destination
>>>> done = 1;
>>>> }
>>>>
>>>> if (done == 1) {
>>>> succ = myent->ipaddr;
>>>> succ_hash = myent->hashf;
>>>> if (field(who) != me) { // i did not originate request
>>>> route_find_pred_reply( field(who), myhash,
>>>> succ, succ_hash, myfinger, 0, 0, -1);
>>>> }
>>>> // Note that this node's successor field is updated via
>>>>stabilize timers
>>>> // else { // update entries if needed
>>>> // register_knowledge(succ, succ_hash);
>>>> // } Adolfo: Probably not needed.
>>>> return;
>>>> }
>>>>
>>>> nextguy = nexthop(field(id));
>>>> if (nextguy != me) { // route the find_pred
>>>> route_find_pred( nextguy, field(id), field(who), 0, 0, -1);
>>>> }
>>>> else {
>>>> exception(48);
>>>> }
>>>>}
>>>>
>>>>joining recv find_pred_reply {
>>>> int i;
>>>> int powow;
>>>> neighbor_finger *predent, *myent;
>>>>
>>>> // my predecessor's old successor may suit me as route entry
>>>> register_knowledge(field(succ), field(succ_id));
>>>> // update p's old successor
>>>> route_update_pred(field(succ), myhash, 0, 0, -1);
>>>>neighbor_clear(pred); // set my new predecessor
>>>> neighbor_add( pred, from);
>>>> predent = neighbor_random( pred);
>>>> predent->hashf = field(pred_id);
>>>> state_change( joined); // now joined
>>>> timer_resched( stabilize, STABLE_TIMEOUT); // schedule maintenance
>>>> timer_resched( fix_fingers, FIX_TIMEOUT);
>>>> replay_add( from);
>>>> upcall_notify(pred,NBR_TYPE_PEER);
>>>>}
>>>>
>>>>
>>>>joined timer stabilize { // stabilize timer
>>>> // responsible for correcting predecessor and successor values
>>>> neighbor_finger *myent = neighbor_random(myfinger[0]); // successor
>>>> if (myent->ipaddr != me) route_get_pred( myent->ipaddr, 0, 0,
>>>>-1); // query successor for pred
>>>>}
>>>>
>>>>
>>>>joined recv get_pred {
>>>> neighbor_finger *predent = neighbor_random(pred);
>>>> neighbor_finger *succent = neighbor_random(myfinger[0]);
>>>> route_get_pred_reply( from, predent->ipaddr, predent->hashf,
>>>>succent->ipaddr, succent->hashf, 0, 0, -1); // let querying node know
>>>>whom my successor
>>>> // and predecessor are
>>>>}
>>>>
>>>>joined recv get_pred_reply {
>>>> int old_start, i;
>>>> neighbor_finger *myent = neighbor_random(myfinger[0]);
>>>>
>>>> if (myent->ipaddr != from) return; // make sure reply is
>>>>
>>>>
>>>>from successor
>>>
>>>
>>>> neighbor_clear(successors_succ);
>>>> neighbor_add(successors_succ, field(succ_id));
>>>> if (field(pred_id) == myhash) return; // if he thinks i am
>>>>his predecessor, we are done
>>>>
>>>> register_knowledge(field(pred), field(pred_id)); // update fingers
>>>> myent = neighbor_random(myfinger[0]); // successor has likely changed
>>>> route_update_pred( myent->ipaddr, myhash, 0, 0, -1); // let him
>>>>know of me
>>>>}
>>>>
>>>>
>>>>joined recv update_pred {
>>>> neighbor_finger *predent = neighbor_random( pred);
>>>>
>>>> // check to see if sending node should be our predecessor
>>>> if (isinrange( field(id), predent->hashf, myhash)) {
>>>> sprintf(trace_buf_, "change pred: old %.8x new %.8x\n",
>>>>predent->hashf, field(id));
>>>> trace_print();
>>>> neighbor_remove( pred, predent->ipaddr);
>>>> neighbor_add( pred, from);
>>>> predent->hashf = field(id);
>>>> upcall_notify(pred,NBR_TYPE_PEER);
>>>> }
>>>>}
>>>>
>>>>
>>>>joined timer fix_fingers {
>>>> // responsible for lazily correcting route (finger) table entries
>>>> int myrand, start, powow, nextguy;
>>>> neighbor_finger *myent, *predent;
>>>> myent = neighbor_random(myfinger[0]);
>>>> predent = neighbor_random(pred);
>>>> if (predent->ipaddr == me || myent->ipaddr == me) return; //
>>>>if i am alone in this ring, get out
>>>>
>>>> myrand = randint(BITS-1) + 1; // select a random finger entry
>>>> start = (int)pow(2, myrand);
>>>> start = start + myhash; // the start address for this entry
>>>> // route a find pred toward this start address
>>>> nextguy = nexthop(start);
>>>> route_find_pred( nextguy, start, me, 0, 0, -1);
>>>> powow = myhash - start; // go backwards in the ring to correct others
>>>> // route an update others message toward them
>>>> nextguy = nexthop(powow);
>>>> route_update_others( nextguy, powow, myhash, me, 0, 0, -1);
>>>>}
>>>>
>>>>joined recv find_pred_reply {
>>>> // when attempting to fix my finger table, I will get replies from
>>>>nodes
>>>> // to consider
>>>> register_knowledge(field(succ), field(succ_id)); // update fingers
>>>>}
>>>>
>>>>joined recv update_others {
>>>> int sendupdate, nextguy;
>>>> neighbor_finger *predent, *myent;
>>>>
>>>> sendupdate = 0; // don't send an update unless we change a finger
>>>>entry
>>>> myent = neighbor_random(myfinger[0]); // successor
>>>> predent = neighbor_random(pred); // predecessor
>>>> if (isinrange(field(id), myhash, myent->hashf)) { // final
>>>>destination
>>>> sendupdate = register_knowledge(field(who), field(node));
>>>> if (sendupdate == 1 && predent->ipaddr != me &&
>>>>predent->ipaddr != field(who)) {
>>>> route_update_ft(predent->ipaddr, field(node), field(who), 0,
>>>>0, -1);
>>>> }
>>>> return;
>>>> }
>>>>
>>>> nextguy = nexthop (field(id));
>>>> if (nextguy != me) { // route the message
>>>> route_update_others(nextguy, field(id), field(node), field(who),
>>>>0, 0, -1);
>>>> }
>>>>}
>>>>
>>>>joined recv update_ft {
>>>> int mybit, loopbit, sendupdate, powow;
>>>> neighbor_finger *myent, *predent;
>>>>
>>>> sendupdate = register_knowledge(field(who), field(node));
>>>> if (sendupdate == 1 && predent->ipaddr != me && predent->ipaddr !=
>>>>field(who)) { // only propagate if my state actually changed
>>>> route_update_ft( predent->ipaddr, field(node), field(who), 0, 0,
>>>>-1);
>>>> }
>>>>}
>>>>
>>>>any recv mapping {
>>>> map.insert(field(low_hash), field(high_hash), field(map_ip)); }
>>>>
>>>>joined recv data {
>>>> routedata(field(sender_hash), field(sender_ip),
>>>>field(receiver_hash), size, field(priority), msg, 0);
>>>>}
>>>>
>>>>joined recv data_path_req {
>>>> routedata(field(sender_hash), field(sender_ip),
>>>>field(receiver_hash), size, field(priority), msg, 1);
>>>>}
>>>>
>>>>API route {
>>>> routedata(hashof(me), me, dest, size, transport, msg, 0);
>>>>}
>>>>
>>>>API routeIP {
>>>> routedata(hashof(me), me, dest, size, transport, msg, 1);
>>>>}
>>>>
>>>>any timer printer {
>>>> dump_state();
>>>>}
>>>>
>>>>API downcall_ext {
>>>> switch(operation) {
>>>> case TEST_OWNER: {
>>>> test_owner_arg *targ = (test_owner_arg*)arg;
>>>> neighbor_finger *predent;
>>>> predent = neighbor_random(pred);
>>>> return isinrangeright(targ->nodeId,predent->hashf,myhash);
>>>> }
>>>> default: { //downcall not supported
>>>> return -1;
>>>> }
>>>> }
>>>> return 0;
>>>>}
>>>>
>>>>API error {
>>>> neighbor_finger *myent, *myent2;
>>>> int loopbit;
>>>> sprintf(trace_buf_, "Neighbor %.8x died!\n", neighbor);
>>>> trace_print();
>>>>
>>>> if (neighbor_query(pred, neighbor)) { // predecessor died
>>>> neighbor_remove(pred, neighbor);
>>>> myent = neighbor_random(myfinger[BITS-1]);
>>>> neighbor_add(pred, myent->ipaddr);
>>>> myent2 = neighbor_random(pred);
>>>> myent2->hashf = myent->hashf;
>>>> upcall_notify(pred,NBR_TYPE_PEER);
>>>> }
>>>>
>>>> for (loopbit = BITS-1; loopbit>=1; loopbit--) {
>>>> if (neighbor_query(myfinger[loopbit], neighbor)) {
>>>> myent = neighbor_random(myfinger[loopbit-1]);
>>>> neighbor_remove(myfinger[loopbit], neighbor);
>>>> neighbor_add(myfinger[loopbit], myent->ipaddr);
>>>> }
>>>> }
>>>> if (neighbor_query(myfinger[0], neighbor)) { // successor diede
>>>> myent = neighbor_random(myfinger[0]);
>>>> int old_start = myent->start;
>>>> neighbor_remove(myfinger[0], neighbor);
>>>> if (neighbor_size (successors_succ))
>>>> myent = neighbor_random(successors_succ);
>>>> else
>>>> myent = neighbor_random(myfinger[1]);
>>>> neighbor_add(myfinger[0], myent->ipaddr);
>>>> myent2 = neighbor_random(myfinger[0]);
>>>> myent2->start = old_start;
>>>> myent2->hashf = myent->hashf;
>>>> }
>>>>}
>>>>}
>>>>
>>>>routines {
>>>>int nexthop (int target) {
>>>> int i,j,done;
>>>> neighbor_finger *predent, *myent, *myent2;
>>>>
>>>> done = 0; // haven't found the next hop yet
>>>> // first check if the target is beyond last finger
>>>> j = 0;
>>>> i = BITS-1;
>>>> myent = neighbor_random(myfinger[i]);
>>>> myent2 = neighbor_random(myfinger[j]);
>>>> if (isinrange( target, myent->start, myent2->start )) {
>>>> done = 1;
>>>> }
>>>> for (j = BITS-1; j > 0; j--) { // loop thru fingers to find right one
>>>> if (done == 0) {
>>>> i = j - 1;
>>>> myent = neighbor_random(myfinger[i]);
>>>> myent2 = neighbor_random(myfinger[j]);
>>>> if (isinrange( target, myent->start, myent2->start )) {
>>>> done = 1;
>>>> }
>>>> }
>>>> }
>>>> done = 0; // reset flag
>>>> for (j = i; j >= 0; j--) { // backs up to make sure that we
>>>>forward to // a node strictly before target
>>>> if (isinrange( myent->hashf, myent->start, target )) {
>>>> if (myent->start != target) {
>>>> done = 1;
>>>> }
>>>> }
>>>> if (myent->ipaddr == me || done == 0) { // still looking
>>>> // note that I should not forward to myself (lightly populated case)
>>>> myent = neighbor_random(myfinger[j]);
>>>> }
>>>> }
>>>> return myent->ipaddr; // could return me if i am the only node
>>>>}
>>>>
>>>>int register_knowledge (int target_ip, int target_hash) {
>>>> // updates the appropriate finger table entry // returns 1 if
>>>>an update occurred
>>>> int mybit, loopbit, powow;
>>>> int change=0;
>>>> neighbor_finger *predent, *myent, *myent2;
>>>> mybit = BITS-1;
>>>> for (loopbit = mybit; loopbit >= 0; loopbit--) {
>>>> myent = neighbor_random(myfinger[loopbit]);
>>>> powow = myent->start;
>>>> if (isinrange(target_hash, powow, myent->hashf)) {
>>>> sprintf(trace_buf_, "change finger %d: old %.8x new %.8x start
>>>>%.8x\n", loopbit, myent->hashf, target_hash, powow);
>>>> trace_print();
>>>> change=1;
>>>> neighbor_remove( myfinger[loopbit], myent->ipaddr );
>>>> neighbor_add( myfinger[loopbit], target_ip);
>>>> myent = neighbor_random( myfinger[loopbit] );
>>>> myent->hashf = target_hash;
>>>> myent->start = powow;
>>>> }
>>>> }
>>>> return change;
>>>>}
>>>>
>>>>void routedata (int route_from, int from_ip, int route_dest, int
>>>>route_size, int route_transport, char *route_msg, int pathreq) {
>>>> int should_forward, nextguy;
>>>> neighbor_finger *predent;
>>>> predent = neighbor_random(pred);
>>>> if (isinrangeright(route_dest, predent->hashf, myhash)) {
>>>>// final destiation
>>>> }
>>>> else { // trying to route through
>>>> nextguy = nexthop(route_dest);
>>>> if (nextguy != me) { // I can route it
>>>> if (!pathreq)
>>>> should_forward = upcall_forward(nextguy, route_msg, route_size,
>>>>COMM_TYPE_UNICAST);
>>>> else should_forward = 0;
>>>> if (should_forward == 0) {
>>>> if (!pathreq) { // no need to check cache, routing thru overlay
>>>> route_data( nextguy, route_dest, from_ip, route_from,
>>>>route_transport, route_msg, route_size, route_transport);
>>>> }
>>>> else { // requesting cache services
>>>> int lower = map.query(route_dest);
>>>> if (lower) { // he's in my cache
>>>> route_data( lower, route_dest, from_ip, route_from,
>>>>route_transport, route_msg, route_size, route_transport);
>>>> }
>>>> else {
>>>> route_data_path_req( nextguy, route_dest, from_ip,
>>>>route_from, route_transport, route_msg, route_size, route_transport);
>>>> }
>>>> }
>>>> }
>>>> return;
>>>> }
>>>> }
>>>>
>>>> // I must be the final destination
>>>> // I may be the only node in the system
>>>> should_forward = upcall_forward( 0, route_msg, route_size,
>>>>COMM_TYPE_UNICAST);
>>>> if (should_forward == 0) {
>>>> // printf("deliverance 1 dest %.8x, pred %.8x, mine
>>>>%.8x\n", route_dest, predent->hashf, myhash);
>>>> int low;
>>>> if (predent->ipaddr == me)
>>>> low = myhash;
>>>> else
>>>> low = predent->hashf-1;
>>>> if(pathreq && from_ip!=me) { // send a mapping if possible
>>>> route_mapping(from_ip, low, myhash, me, 0, 0, -1);
>>>> }
>>>> upcall_deliver( route_msg, route_size, COMM_TYPE_UNICAST);
>>>> }
>>>>}
>>>>}
>>>>
>>>>
>>>>
>>>>
----- End forwarded message -----
More information about the chord
mailing list