randtree.mac

这是一个著名的应用层组播中间件的源码

//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.

/**
 *  randtree.mac 
 *  Adolfo Rodriguez
 *
 *  Implementation of a simple random tree overlay.  
 *  Nodes have a maximum number of children they are willing to accept.
 *  If full, a node receiving a join request will redirect the request to
 *    one of its children.
 *  By specifying a parent file, this code recreates a random tree for 
 *    reproducibility.
 *  
 *  Notes:
 *  Assumes that the (single) sender of multicast data is the root of the tree.
 *    All requests to join the overlay are sent to this node.
 *  Forwards data blindly without regard to session ID's.  Also, requests to 
 *    join and leave a multicast session are ignored.  A real protocol would 
 *    handle these.  
 */
#include "adolfo_filter.h" //includes the declaration of the adolfo filter.
#include "overlay_suggestions.h" //includes extensible parameters for higher level hints about the overlay.


typedef char* chars;

protocol randtree //This file defines the protocol randtree.

addressing ip     //The address space which this protocols uses are
                  //the set of IP addresses.

trace_off         //Turn off all protocol tracing.

constants {       //The set of [global]  constants available to the protocol.
  int RANDTREE_MAX_CHILDREN = 15;
  int RANDTREE_MAX_CHILDREN_NON_SRC = 10;
  int RANDTREE_JOIN_TIMEOUT = 5;
  int DEBUG_INTERVAL = 4;

}

states {          //A semi-colon separated list of protocol state names.
  //init is a special system start state, and its declaration is not needed.
  //init;
  joining unready;
  joined;
}

/*
 * Type definitions of neighbors randtree uses. These neighbor types
 * inherit many properties from a base neighbor class defined in
 * neighbor_set.h and discussed in section 4.2 of the manual.
 */
neighbor_types {
    /*
     * Simple syntax:
     * <NBR_TYPE_NAME> <SIZE>;
     *
     * Defines a type of <NBR_TYPE_NAME> which holds a set of
     * no more than <SIZE> objects of type neighbor_<NBR_TYPE_NAME>.
     *
     * Advanced syntax:
     * <NBR_TYPE_NAME> <SIZE> { <variable declarations;> }
     *
     * Defines a type of <NBR_TYPE_NAME> which holds a set of
     * no more than <SIZE> objects of type neighbor_<NBR_TYPE_NAME>.
     * Each neighbor_<NBR_TYPE_NAME> object will have state for the
     * variables declared within.
     */
  rparent 1; 
  rchildren RANDTREE_MAX_CHILDREN;
  suggestion_list RANDTREE_MAX_CHILDREN {
    double end_time;
  }

}

/*
 * Definition and mapping of transport types.
 *
 * Syntax:
 * <TYPE> <NAME>;
 *
 * Creates a transport type of type <TYPE> and maps it to the name
 * <NAME>. In the case of randtree (and most bottom-layer protocols),
 * it will define transports of several priorities. When message types
 * are defined, their transport type can be specified, as demonstrated
 * below.
 *
 */
transports {
  TCP HIGHEST;
  TCP HIGH;
  TCP MED 5;
  TCP LOW 5;
  UDP BEST_EFFORT;
}

/*
 * Definition of message types.
 *
 * Syntax:
 * (<TRANSPORT>) <MESSAGE TYPE> { <variable definitions> }
 *
 * Creates a message type called <MESSAGE TYPE>. If <TRANSPORT> is
 * specified (this is optional), it specifies the default lower layer's
 * transport method to be used for this message. The message 
 * variables are declared much like normal, with a few exceptions:
 * 
 * - to declare an array, use <type> <name> <length>;
 * - to declare a two-d array, use <type> <name> <length> <length>;
 * - larger dimensional arrays are not presently supported.
 * - neighbor types can be included, message types cannot.
 * - user-defined types (included in .h files at the top) can be used.
 *
 * Note that all messages can include a data buffer supplied from the
 * higher layer/application. There is no need to declare this as part
 * of the message. These message types merely specify the message
 * headers.
 *
 */
messages {
  BEST_EFFORT join {
  }
  HIGHEST join_redirect {
    int who;
  }
  HIGHEST join_reply {
  }
  HIGHEST remove {
  }
  HIGHEST wean {
  }
  BEST_EFFORT data {  // Data is sent best-effort by default
    short comm_type;
    short priority;
  }

}

/*
 * Declaration of state variables (note the difference between state
 * variables and the protocol's FSM state).
 *
 * These variables are declared according to normal conventions, with
 * the same exceptions as existed for message variables. Additionally,
 * neighbor set type variables may be preceded by fail_detect, which
 * causes MACEDON to automagically monitor those neighbors for
 * failure.
 */
state_variables {    
//    rparent papa;  
//    rchildren kids;
  fail_detect rparent papa;  
  fail_detect rchildren kids;
  char * got_msg nodump;
  int forced_parent;
  int forced_children;
  adolfo_filter master;     //This filter collects stats on all data received.
  adolfo_filter master_useful;  //This filter collects stats on useful data received. 
  timer join;
  timer printer DEBUG_INTERVAL;

  int CURRENT_MAX_CHILDREN;

  suggestion_list suggestions;
  double parent_suggestion_give_up;

}     

/*
 * Definition of the protocol transitions. That is, the code which is
 * triggered when events occur. This wholly codifies the entry-points
 * into the protocol execution.
 *
 * A transition is defined by a tuple (S,T,N,A), and is specified by
 * the syntax: (S) T N { A }
 *
 * S: A state expression which can contain either a single state, or
 *    an expression such as "any", "!<state>", etc. The transition is
 *    said to be enabled when the state expression is true.  If S is
 *    omitted, it is taken as "any."
 * T: The type of event which occured. This list currently is the set
 *    {recv, forward, API, timer}
 * N: The name of the event.  For message events (recv and forward),
 *    this refers to the set of message types.  For timer events, the
 *    set of defined timers.  For API events, the set of API calls.
 * A: A list of actions to take.  These actions can be arbitrary C++
 *    code (with MACEDON library funcitons), timer actions, API calls,
 *    state transitions, or combinations of these.  Note in particular
 *    special library functions are created to make API calls to either
 *    the application or the lower layer.  These follow one of two
 *    formats: "<API>_<message type>" for the API calls which send
 *    data, or "<API>" for the API calls which don't.  Their parameter
 *    lists depend on the fields of the message and the parameters
 *    defined in macedon_api.h.
 *
 * For more information on the MACEDON library functions, refer to
 * section 4.2 of the manual.
 */
transitions {
  //The init API call will be called at the protocol's start time,
  //so the system will be in the init state. 
  init API init {
    timer_resched (printer, DEBUG_INTERVAL);
    CURRENT_MAX_CHILDREN = RANDTREE_MAX_CHILDREN;
    if ( source_ != me ) { //Note: source_ and me are global automatic variables.
      CURRENT_MAX_CHILDREN = RANDTREE_MAX_CHILDREN_NON_SRC;
    }

    parent_suggestion_give_up = 0.0;
    if ( source_ == me ) { //Note: source_ and me are global automatic variables.
      // If I am the source, just mark myself joined
      debug_macro("In API init -- changing state to joined.\n");
      state_change(joined);
      replay_experiment();  // Traces start of experiment
    }
    else {
      // I am not the source
      read_parent_file();  // Attempts to read static tree file.
                           // Note: this is a routine call
                           // defined in the routines block below.
      state_change(joining); 
      if (!forced_parent) { // Note: forced_parent is a peripheral state variable
        route_join(source_, 0, 0, -1);  // Source is the bootstrap
        forced_parent = source_;
      }
      else {
        route_join (forced_parent, 0, 0, -1); // Note: special library function
                                          // to instruct the lower layer
                                          // (the network substrate) to route
                                          // the join message to
                                          // forced_parent
      }
      timer_resched (join, RANDTREE_JOIN_TIMEOUT); // Note: built-in timer
                                                   // scheduling function

      replay_init();
    }
  }

  // Note: trigger this transition when a timer event occurs on the
  // join timer and we are in the joining state.
  joining timer join {
    // Timer fired, retry join
    if(parent_suggestion_give_up == 0.0 || curtime < parent_suggestion_give_up) {
      debug_macro ("timer join forced_parent: %.8x\n", forced_parent);
      route_join (forced_parent, 0, 0, -1);
      timer_resched (join, RANDTREE_JOIN_TIMEOUT);
    } else {
      debug_macro ("giving up on trying to join under suggested parent\n");
      neighbor_rparent* existing = neighbor_random(papa);
      ASSERT (existing != NULL);
      forced_parent = existing->ipaddr;
      parent_suggestion_give_up =0.0 ;
      route_remove(forced_parent, 0, 0, -1);  // remove yourself from the old parent
      state_change(joined);
    }
  }

  // Note: trigger this transition when a message is received of type
  // join and we are in the joined state.
  joined recv join {
    clean_suggestions();
    neighbor_rchildren * redir; // a pointer to a neighbor object kept in rchildren sets.
    if ( (neighbor_query(suggestions, from) && neighbor_space(kids)) || (!neighbor_query(kids, from) && neighbor_space(kids) && neighbor_size(kids) < CURRENT_MAX_CHILDREN) ) { // built-in neighbor fns.
      // He is not my child and I have space for him
      neighbor_remove(suggestions, from);
      neighbor_add(kids, from); 
      route_join_reply(from, 0, 0, -1);
      debug_macro ("route_join_reply to: %.8x status(%d)\n", from, macedon_sendret);
      upcall_notify(kids, NBR_TYPE_CHILDREN); // Notify upper layer of change
    }
    else if (neighbor_query (kids, from)) {
      // already our child, do nothing
    }
    else {   // choose random child to redirect join
      redir = neighbor_random(kids); 
      route_join_redirect(redir->ipaddr, from, 0, 0, -1); // route a join_redirect message to
                                                // redir->ipaddr with message header set
                                                // to "from"
    }
  }

  joining recv join_reply {
    // The join worked
    neighbor_rparent* existing = neighbor_random(papa);
    if (existing != NULL && existing->ipaddr && existing->ipaddr != from) {
      route_remove(existing->ipaddr, 0, 0, -1);  // remove yourself from the old parent
    }
    neighbor_clear(papa);
    debug_macro ("join_reply from: %.8x\n", from);

    state_change(joined);
    replay_add(from);  // Trace having joined the overlay
    neighbor_add(papa, from);
    upcall_notify(papa, NBR_TYPE_PARENT); // Notify upper layer of change
    timer_cancel (join);
  }