Differences between revisions 7 and 8
Revision 7 as of 2008-06-26 09:52:38
Size: 10801
Editor: anonymous
Comment: converted to 1.6 markup
Revision 8 as of 2009-02-18 22:59:35
Size: 9293
Editor: alpt
Comment:
Deletions are marked like this. Additions are marked like this.
Line 54: Line 54:
 * The Routing Tree has to be maximally disjoint, i.e. two generic routes of the same RT have to share the least number of subpaths. For more information on this topic see:  http://www.hpl.hp.com/personal/Sung-Ju_Lee/abstracts/papers/icc2001b.pdf  * The Routing Tree has to be maximally disjoint, i.e. two generic routes of
  
the same RT have to share the least number of subpaths.
  
For more information on this topic see:
http://www.hpl.hp.com/personal/Sung-Ju_Lee/abstracts/papers/icc2001b.pdf
Line 58: Line 61:
 * The Routing Tree must not be expanded infinitely, i.e. it must not be too large.

 * Two nodes will use the CR to communicate only in particular situations: when they need to send a large quantity of data or when they need a really low trtt (total round-trip time) for real time applications. In all the other average cases, the unicast best route will be sufficient.

 * A CT connection isn't necessarily symmetric: the best CRT from S to D may not coincide with that from D to S. Hence, if also D needs to replies to S large chunks of data it will need to create a new CRT, otherwise it will just use the inverse of the S->D CRT.
 * The Routing Tree must not be expanded infinitely, i.e. it must not be too
  
large.

 * Two nodes will use the CR to communicate only in particular situations:
  
when they need to send a large quantity of data or when they need a really
  
low trtt (total round-trip time) for real time applications. In all the
  
other average cases, the unicast best route will be sufficient.

 * A CR connection isn't necessarily symmetric: the best CRT from S to D may
  
not coincide with that from D to S.
   
Hence, if also D needs to replies to S large chunks of data it will need to
  
create a new CRT, otherwise it will just use the inverse of the S->D CRT.
Line 111: Line 121:
 /* The first call */
 crt_discovery(S, D, best_bw, max_trtt(S -> D), NULL);

 crt_discovery(S (source node),
   D (destination node),
 /* The first call: send a discovery packet to `S', asking it to find a
  * way to reach D */
 ret = S.crt_discovery(D, best_bw, max_trtt(S -> D), NULL);

 /*
  * Note that calling S.crt_discovery(arguments) is equivalent to send a
  * `arguments' to `S'.
  * The return value from a call to S.crt_discovery() is the reply
  * packet sent by S.
  */

 crt_discovery( D (destination node),
Line 120: Line 137:

  /*
   * Note that calling crt_discovery() is equivalent to send a
   * `dpkt' to `S' with the min_bw and trtt_limit values
   * included in the pkt itself.
   * Reading the return value from a call to crt_discovery() is
   * equivalent to receive a reply packet from `S'.
   */
 
Line 131: Line 139:
  if(S in dpkt)
   /* We're present in the dpkt, and this is the
    * second time we received i
t, thus a cycle
  if(self in dpkt)
   /* We're in the dpkt, thus a cycle
Line 138: Line 145:
  /* Append S in dpkt.   /* Append self in dpkt.
Line 140: Line 147:
  dpkt.append(S);

  if(S.route_D_set == 1 AND dpkt.flag!=ACK_FORCED)
  dpkt.append(self);

  if(self.route_D_set == 1 AND dpkt.flag!=ACK_FORCED)
Line 150: Line 157:
  foreach i in r(S)   foreach i in r(self)
Line 158: Line 165:
   if (trtt(S -> D, i) > trtt_limit OR
    bw(S -> D, i) < min_bw)
   if (i in dpkt)
    /* The dpkt has already been sent to i. In
     * order to avoid infinite loops, we don't
     * send it to him again. */
     continue;

   if (trtt(self -> D, i) > trtt_limit OR
    bw(self -> D, i) < min_bw)
Line 169: Line 182:
   add_tmp S -> D, gw i;
   add_tmp D -> S, gw i;
   add_tmp self -> D, gw i;
Line 175: Line 187:
    * packets of the connection S -> D which S receives     * packets of the connection self -> D which  self receives
Line 178: Line 190:
   ack = crt_discovery(i, D,
         flowbrate(last_node(dpkt) -> S),
   ack = i.crt_discovery(i, D,
         flowbrate(last_node(dpkt) -> self),
Line 187: Line 199:
    del S -> D, gw i;
    del D -> S, gw i;
    continue;
    del self -> D, gw i;
Line 195: Line 205:


/* If we've got this far, set deepened to 1 */
   deepened=1;
   else
  /* If we've got this far, set deepened to 1 */
    deepened=1;
Line 210: Line 219:
    ack = crt_discovery(i, D,
      flowbrate(last_node(dpkt) -> S),
    ack = i.crt_discovery(i, D,
      flowbrate(last_node(dpkt) -> self),
Line 218: Line 227:
     del S -> D, gw i;
     del D -> S, gw i;
     del self -> D, gw i;
Line 231: Line 239:

 /* TODO: is it correct to use `flowbrate' in that way? */
Line 233: Line 243:
Here it is the same pseudo code without comments:
{{{

 int max_trtt(S -> D) {

  if (S wants to create CRT to D to send a large amount of data)
   return (A directly proportional value to D);

  else if (S wants to create a fast, low delay, connection to D)
   return best_trtt;
 }

 crt_discovery(S, D, best_bw, max_trtt(S -> D), NULL);

 crt_discovery(S (source node),
   D (destination node),
   min_bw (minimum avail bw required for each route),
   trtt_limit (maximum trtt allowed),
   dpkt (discovery packet))
 {

  int deepened=0;
  
  if(S in dpkt)
   return ACK_NEGATIVE;

  dpkt.append(S);

  if(S.route_D_set == 1 AND dpkt.flag!=ACK_FORCED)
    return ACK_CHANGEPATH;

  foreach i in r(S)
  {

   if (i in last_node(dpkt))
    continue;

   if (trtt(S -> D, i) > trtt_limit OR
    bw(S -> D, i) < min_bw)
    continue;

   add_tmp S -> D, gw i;
   add_tmp D -> S, gw i;

   ack = crt_discovery(i, D,
         flowbrate(last_node(dpkt) -> S),
         trtt_limit, dpkt);
   if (ack == ACK_NEGATIVE)
    del S -> D, gw i;
    del D -> S, gw i;
    continue;

   else if (ack == ACK_CHANGEPATH)
     JointGW.append(i);

   deepened=1;
  }

  if (deepened == 1)
   return;

  else if (JointGW is not NULL) {
   for i in JointGW {
    ack = crt_discovery(i, D,
      flowbrate(last_node(dpkt) -> S),
      trtt_limit, dpkt);
    if (ack == ACK_NEGATIVE || ack == ACK_CHANGEPATH)
     del S -> D, gw i;
     del D -> S, gw i;
     continue;
    deepened=1;
   }
  }
  
  if(deepened == 0)
   return ACK_NEGATIVE;
 }
}}}

NTK_RFC 0013

Subject: Caustic Routing - A multipath generalization


This text describes a possible expansion of the current Npv7 protocol. It will be included in the final documentation, so feel free to correct it. But if you want to change the system here described, please contact us first.


Caustic routing

Multipath routing is method which sends packets of a same connection through different paths.

Caustic Routing is a multipath generalization which aims to redistribute the network traffic in an efficient way, imposing a small load on the interested nodes.

Note that this RFC is not complete. If you want to contribute to its development, DO IT! ;)

Basic idea

The basic idea of the Caustic Routing (CR) is to apply recursively the multipath routing: the source node S chooses one or more neighbours R as gateways to reach the destination D. Each neighbour r_i of R chooses one or more gateways R'(r_i) to reach the destination D. Each neighbour r'_i of R'(r_i) chooses one or more gateways to reach the destination D. And so on, recursively. You can imagine a tree which grows from S and then converges to D. We call the set of all the routes established from S to D, the Caustic Routing Tree (CRT).

Features

The Caustic Routing is specifically designed to load balance the traffic among the greatest possible number of nodes, without affecting the overall performance of the network. Indeed, since the connection flow will be split recursively, each node will receive only a small part of the total traffic, thus its link won't be saturated.

The general result is that a single connection won't be ever capable of saturating an entire path.

General rules

The recursion of the CR has to be regulated to avoid the creation of infinite loops, the saturation of links and the dispersion of packets, thus it will follow these principles:

  • Infinite loops must not be created.
  • The Routing Tree has to be maximally disjoint, i.e. two generic routes of
  • Path with saturated bandwidth should be avoided.
  • The Routing Tree must not be expanded infinitely, i.e. it must not be too
    • large.
  • Two nodes will use the CR to communicate only in particular situations:
    • when they need to send a large quantity of data or when they need a really low trtt (total round-trip time) for real time applications. In all the other average cases, the unicast best route will be sufficient.
  • A CR connection isn't necessarily symmetric: the best CRT from S to D may
    • not coincide with that from D to S. Hence, if also D needs to replies to S large chunks of data it will need to

      create a new CRT, otherwise it will just use the inverse of the S->D CRT.

Caustic Routing Tree discovery

Let's suppose that the node S wants to send a large quantity of data to D. The source node S, before contacting D, will set up a Caustic Routing Tree that reaches D from S. The discovery of the S->D CRT will be done in the following way:

        Let  D  be the destination node.

        Let  r(N)  be the set of rnodes (neighbours) of the node N, which can be
             utilised as gateway to reach D.
        Let  r(N,i)  be the i-th of such rnodes.

        Let  bw(N -> D, i) = bw( r(N,i) -> D )  be the current available
             bandwidth capacity of the route N -> i -> D.
        Let  best_bw  be the current available bandwidth capacity of the best
             route N -> D.

        Let  trtt(N -> D, i) = trtt( r(N,i) -> D )  be the current total round
             trip time of the route N -> i -> D.
        Let  best_trtt  be the current trtt of the best route N -> D.

        Let  flowrate(I -> N)  be the throughput of packets of the connection
             S -> D which N receives from I.

        /* The max_trtt imposes the limit on the growth of the Routing Tree */
        int  max_trtt(S -> D) {

                if (S wants to create CRT to D to send a large amount of data)
                        /* In this case we don't care to have a big delay,
                         * because we just want to send the biggest possible
                         * amount of data to D. Thus we use a max_trtt
                         * proportional to the total amount of data we want to
                         * send. For example, if we want to send 7Gb, we don't
                         * care to have a complessive delay of 10seconds if we
                         * reach a throughput of 4Gb/s */
                        
                        return  (A directly proportional value to D);

                else if (S wants to create a fast, low delay, connection to D)
                        /* In this case if we set  max_trtt=best_trtt  then in
                         * the CRT there will be only routes which don't
                         * increase the overall delay of the connection. */
                        return  best_trtt;
        }

        /* The first call: send a discovery packet to `S', asking it to find a
         * way to reach D */
        ret = S.crt_discovery(D,  best_bw,  max_trtt(S -> D),  NULL);

        /* 
         * Note that calling S.crt_discovery(arguments) is equivalent to send a
         * `arguments' to  `S'.
         * The return value from a call to S.crt_discovery() is the reply
         * packet sent by S.
         */

        crt_discovery(  D (destination node), 
                        min_bw (minimum avail bw required for each route),
                        trtt_limit (maximum trtt allowed),
                        dpkt (discovery packet))
        {
                int deepened=0;
                
                if(self  in  dpkt)
                        /* We're in the dpkt, thus a cycle
                         * has been formed. Return ACK_NEGATIVE and
                         * destroy it. */
                        return  ACK_NEGATIVE;

                /* Append  self  in  dpkt.
                 * This is the same operation used in Tracer Packets. */
                dpkt.append(self);

                if(self.route_D_set == 1  AND  dpkt.flag!=ACK_FORCED)
                        /* 
                         * We've already received a dpkt and set a route to D,
                         * moreover the caller isn't forcing us to use this
                         * path,  thus we advice it to use another one.
                         */
                         return ACK_CHANGEPATH;

                foreach  i  in  r(self) 
                { 

                        if (i  in  last_node(dpkt))
                                /* Don't consider the node from which we
                                 * received the `dpkt' */
                                continue;

                        if (i in dpkt)
                                /* The dpkt has already been sent to i. In
                                 * order to avoid infinite loops, we don't
                                 * send it to him again. */
                                 continue;

                        if (trtt(self -> D, i) > trtt_limit  OR 
                                bw(self -> D, i) < min_bw)
                                /* Don't use `i' as gw, since it doesn't meet
                                 * the minimum requirements */
                                continue;

                        /*
                         * Set two temporary routes in the krnl routing table:
                         * These two routes, if not utilised, will expire after
                         * 300 seconds. 
                         */
                        add_tmp  self -> D, gw i;

                        /* 
                         * Recurse.
                         * The  min_bw  for  `i'  will be the throughput of 
                         * packets of the connection  self -> D  which  self  receives
                         * from I.
                         */
                        ack = i.crt_discovery(i,  D,  
                                            flowbrate(last_node(dpkt) -> self),
                                            trtt_limit, dpkt);
                        if (ack == ACK_NEGATIVE)
                                /* 
                                 * We cannot use  `i'  as gw to reach  D.
                                 * Remove the temporary routes previously set in
                                 * the routing table
                                 */
                                del  self -> D, gw i;

                        else if (ack == ACK_CHANGEPATH)
                                /* `i' is advising us to use another path 
                                 * append  `i'  to the set  JointGW */
                                 JointGW.append(i);
                        else
                                /* If we've got this far, set deepened to 1 */
                                deepened=1;
                }

                if (deepened == 1)
                        return;

                else if (JointGW is not NULL) {
                        /* 
                         * Since we didn't find any good gw to reach D, let's
                         * try to use those added in the JointGW set 
                         */
                        for  i  in  JointGW {
                                ack = i.crt_discovery(i,  D,  
                                                flowbrate(last_node(dpkt) -> self),
                                                trtt_limit, dpkt);
                                if (ack == ACK_NEGATIVE || ack == ACK_CHANGEPATH)
                                        /* 
                                         * This time, we know that `i'
                                         * definitely cannoy be used.
                                         */
                                        del  self -> D, gw i;
                                        continue;

                                /* If we've got this far, set deepened to 1 */
                                deepened=1;
                        }
                } 
                
                if(deepened == 0)
                        /* We didn't find any good gateway to reach D. */
                        return  ACK_NEGATIVE;
        }

        /* TODO: is it correct to use `flowbrate' in that way? */

Bnodes diversification

When a CRT exits from a gnode, it should try to use the maximum number of bnodes, instead of just one. This is easily achieved by letting each node select gateways which point to different bnodes.

TODO

Caustic Routing Tree update

We need a light mechanism to ensure that a CRT will be always up to date.

Caustic Routing congestion control

We need a mechanism to ensure a congestion control of the overall traffic passing over a CRT. This paper can be used as a starting point: http://www.cs.pitt.edu/%7Eelhaddad/aequitas/ http://www.cs.pitt.edu/%7Eelhaddad/aequitas/elhaddad.pdf

Network coding

Explore the possibilities of integrating the network coding approac in the Caustic Routing: http://en.wikipedia.org/wiki/Network_coding

Packet reordering

The TCP Packet reordering problem can make useless the use of Caustic or Multipath routing if not handled correctly. See the RFC 2991: http://tools.ietf.org/html/rfc2991

Life probability

Take in consideration the NTK_RFC 0005: http://lab.dyne.org/Ntk_life_probability

Ntk_caustic_routing (last edited 2009-02-18 23:00:39 by alpt)