10801
Comment: converted to 1.6 markup
|
9293
|
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 it, 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
- 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 same RT have to share the least number of subpaths. For more information on this topic see:
- 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.
- 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
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