|
Size: 4824
Comment:
|
Size: 7733
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 13: | Line 13: |
| In the current version of the Npv7 the link quality is measured only with the rtt and packets loss, so only the lantecy is actually considered, this isn't optimal since also a link with a bandwidth of 20000 bps can have a good lantecy. It isn't a critical problem since more than one route is used to reach a single dst_node, so when a route is satured the kernel will use another one looking in the nexthop table of that route. |
In the current version of the Npv7, the Radar measures the link quality using only the rtt (round-trip time) and packets losses. This isn't optimal, because the bandwidth capacity is ignored, thus a link having a poor bandwidth, f.e 20Kbps, but a good latency, will be preferred over a link with a big bandwidth but a medium latency. |
| Line 23: | Line 21: |
| In order to improve the link measurement a node must include in the tracer pkts the available bandwidth of its traversed link. The link bandwidth, which will be used to modify the real rtt, in this way it will be possible to have a traffic shaping based also on the real bandwidth of the links. |
A node must include in the Tracer Packets, not only the rtt of the traversed link, but also the current bandwidth capacity. In this way it will be possible to have a traffic shaping based also on the real bandwidth of the links. |
| Line 31: | Line 28: |
| There are two phases of measurement: in the first the total bandwidth of the | There are two phases of measurement. In the first the total bandwidth of the |
| Line 35: | Line 32: |
| The utilised bandwidth will be monitored with iptables and the libiptc library. See http://www.tldp.org/HOWTO/Querying-libiptc-HOWTO/bmeter.html . |
The utilised bandwidth will be monitored with the libpcap library. |
| Line 38: | Line 34: |
| We also need to know the total bandwidth which can handle the network interface. What is a good method to do this? |
/* TODO TODO */ /* TODO TODO */ /* TODO TODO */ /* TODO: Let's use the Packet Pair and Packet Train to measure the bw of the * links */ http://perform.wpi.edu/downloads/wbest/README |
| Line 41: | Line 41: |
| === Total available bandwidth === | # We also need to know the total bandwidth which can handle the network # interface. What is a good method to do this? # ==== Total available bandwidth ==== |
| Line 50: | Line 54: |
| destination of the link. The link is monitored with libiptc and the maximum | destination of the link. The link is monitored with libpcap and the maximum |
| Line 53: | Line 57: |
| Since the link might be asymettric the measurement is also repeated by A and | Since the link might be asymmetric the measurement is also repeated by A and |
| Line 56: | Line 60: |
| === Realtime bandwidth monitoring === | ==== Realtime bandwidth monitoring ==== |
| Line 58: | Line 62: |
| With the use of the libiptc library, B can monitor the bandwidth usage of its | With the use of the libpcap library, B can monitor the bandwidth usage of its |
| Line 85: | Line 89: |
| http://hinezumilabs.org/cgi-bin/viewcvs.cgi/netsukuku/src/igs.c?rev=HEAD&content-type=text/vnd.viewcvs-markup | http://hinezumi.org/cgi-bin/viewcvs.cgi/netsukuku/src/igs.c?rev=HEAD&content-type=text/vnd.viewcvs-markup |
| Line 87: | Line 91: |
==== Rtt delay ==== Each node of the network will delay the forwarding of a received Tracer Packet by a time inversely proportional to its upload bandwidth. In this way the TPs will continue to be received in order of efficiency. The side effect of this rule is that the extreme cases will be ignored, i.e. a route with a very low rtt but with a very poor bw, or a route with an optimal bw but with a very high rtt. However, in the ``real world'' these extreme cases are rare, because the rtt and the bw are often related. For more information about the order of efficiency of the Tracer Packets you can read the document on the QSPN v2: http://netsukuku.freaknet.org/doc/main_doc/qspn.pdf ==== Route bandwidth ==== The bandwidth capacity of the route S -> D is denoted with bw(S -> D) and is equal to the bandwidth of the worst link in the route. For example: {{{ S --64Mb/s--> R --64Mb/s--> T --32Mb/s--> O --100Mb/s--> I --100Mb/s--> D }}} the route bandwidth of this segment is bw(S -> D)=32Mb/s. A TP needs to memorized only _one_ bw capacity value, and that is the bw() of the traversed current route. For example, is S sends a TP, when it will arrive on T, the bw capacity will be bw(S->R->T)=64, but when it will reach O, it will change to bw(S->R->T->O)=32. == Asymmetric routes == The QSPN gives to each node the best download route to reach all the other node. Let's consider the node S and D: {{{ 1: ,--<-<-<---. / \ S D \ / 2: `-->->->---' }}} The routes of type 1 are the best upload routes from D to S, while the routes of type 2 are the opposite. The QSPN gives to S only the routes of type 1, while D knows only the route of type 2. If the routes aren't symmetric, when S will upload something to D, it will use a route of type 1, which will give poor performance. The solution is very simple: S, when uploading a large chunk of data, will request to D its D->S routes, which are the routes of type 2, i.e. the best upload routes from S to D. The Netsukuku daemon, using libpcap, will monitor the packets outgoing from localhost. If the packets are being sent for more than 16 seconds, it will request to the destination node the best uploads routes and add them in the routing table. In this way, the upload routes will be requested only when necessary. |
|
| Line 100: | Line 165: |
| If the protocol of the application uses the "tos" value in its IP packets, it | If the protocol of the application uses the TOS value in its IP packets, it |
| Line 104: | Line 169: |
| == Caveats == If the libiptc are used, it will be more difficult to port the daemon for other kernels than Linux. Libpcap is a good alternative. It is possible to capture the packets for some seconds using libpcap, count them and find how much bandwidth is used. |
Alternatively it is possible to keep in the kernel only the average table, because this is the most used. The specific "best latency" and "best bandwidth" routes can be added in the kernel only at the moment of their utilization. For example, when bittorrent will start the download from the nodes A,B,C, the ntkd monitor will add in the kernel the "best bandwidth" routes for A,B,C. |
| Line 113: | Line 178: |
| The inet-gw which share their internet connection measure also the utilzed | The inet-gw which share their Internet connection measure also the utilzed |
| Line 120: | Line 185: |
| == Load balancing == The load balancing will be always used, because the routes are added in the kernel using the multipath option. The packets sent to a node will use different routes The load balancing inside Netsukuku doesn't suffer the problems of the IGS load balancing. Indeed, the ntk nodes are consistent between themself, i.e. a ntk node doesn't use NAT to reach another ntk node. |
NTK_RFC 0002
Subject: bandwidth measurement
This text describes a change to the Npv7. 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.
Link measurement issues
In the current version of the Npv7, the Radar measures the link quality using only the rtt (round-trip time) and packets losses. This isn't optimal, because the bandwidth capacity is ignored, thus a link having a poor bandwidth, f.e 20Kbps, but a good latency, will be preferred over a link with a big bandwidth but a medium latency.
Improvement
A node must include in the Tracer Packets, not only the rtt of the traversed link, but also the current bandwidth capacity. In this way it will be possible to have a traffic shaping based also on the real bandwidth of the links.
Bandwidth measurement
There are two phases of measurement. In the first the total bandwidth of the new links is measured by the hooking node and the destination nodes, in the second the bandwidth of the links is constantly monitored.
The utilised bandwidth will be monitored with the libpcap library.
http://perform.wpi.edu/downloads/wbest/README
# We also need to know the total bandwidth which can handle the network # interface. What is a good method to do this? #
Total available bandwidth
A <-> B <-> C
The node B is hooking to A and C. At the end of the hook, B measures the total available bandwidth of the links B<->C and B<->A. It sends an indefinite amount of random packets, for some seconds, to the destination of the link. The link is monitored with libpcap and the maximum rate of bytes per second is registered as the maximum available upload bandwidth for that specific link. These steps are repeated for each rnode. Since the link might be asymmetric the measurement is also repeated by A and C. In the end we have the measurement of: A->B, B->A, C->B, B->C.
Realtime bandwidth monitoring
With the use of the libpcap library, B can monitor the bandwidth usage of its links.
Max_link_bw = Total available bandwidth of the link
free_link_bw = available/not used bandwidth of the link
cur_used_link_bw= amount of bandwidth currently used
Max_NIC_bw = maximum bandwidth of the network interface
cur_used_NIC_bw = amount of the total bandwidth currently used of the network
interfaceTo calculate the `free_link_bw':
free_link_bw = Max_link_bw - cur_used_link_bw
if(free_link_bw > Max_NIC_bw - cur_used_NIC_bw)
free_link_bw = (Max_NIC_bw - cur_used_NIC_bw);The free_link_bw' value will be used to modify the rtt' used to sort the routes in the routing table.
modified_rtt(free_link_bw, real_rtt) = 27<<27 + real_rtt - bandwidth_in_8bit(free_link_bw) real_rtt must be <= 2^32-27<<27-1 (about 8 days) You can find the definition of bandwidth_in_8bit() here: http://hinezumi.org/cgi-bin/viewcvs.cgi/netsukuku/src/igs.c?rev=HEAD&content-type=text/vnd.viewcvs-markup
Rtt delay
Each node of the network will delay the forwarding of a received Tracer Packet by a time inversely proportional to its upload bandwidth. In this way the TPs will continue to be received in order of efficiency. The side effect of this rule is that the extreme cases will be ignored, i.e. a route with a very low rtt but with a very poor bw, or a route with an optimal bw but with a very high rtt. However, in the real world these extreme cases are rare, because the rtt and the bw are often related. For more information about the order of efficiency of the Tracer Packets you can read the document on the QSPN v2: http://netsukuku.freaknet.org/doc/main_doc/qspn.pdf
The bandwidth capacity of the route S -> D is denoted with bw(S -> D) and is equal to the bandwidth of the worst link in the route. For example: the route bandwidth of this segment is bw(S -> D)=32Mb/s. A TP needs to memorized only _one_ bw capacity value, and that is the bw() of the traversed current route. For example, is S sends a TP, when it will arrive on T, the bw capacity will be bw(S->R->T)=64, but when it will reach O, it will change to bw(S->R->T->O)=32.
The QSPN gives to each node the best download route to reach all the other node. Let's consider the node S and D: The routes of type 1 are the best upload routes from D to S, while the routes of type 2 are the opposite. The QSPN gives to S only the routes of type 1, while D knows only the route of type 2. If the routes aren't symmetric, when S will upload something to D, it will use a route of type 1, which will give poor performance. The solution is very simple: S, when uploading a large chunk of data, will request to D its D->S routes, which are the routes of type 2, i.e. the best upload routes from S to D. The Netsukuku daemon, using libpcap, will monitor the packets outgoing from localhost. If the packets are being sent for more than 16 seconds, it will request to the destination node the best uploads routes and add them in the routing table. In this way, the upload routes will be requested only when necessary.
It may also happens that a link has a good bandwidth but a high latency. A low latency is needed by semi-realtime applications: for a ssh connection we don't care to have a 100Mbs connection but we want to use the shell in realtime, so when we type a command we get a fast response. The Netsukuku should create three different routing tables: If the protocol of the application uses the TOS value in its IP packets, it is possible to add a routing rule and choose the right table for that protocol: the ssh protocol will be routed by the second table. Alternatively it is possible to keep in the kernel only the average table, because this is the most used. The specific "best latency" and "best bandwidth" routes can be added in the kernel only at the moment of their utilization. For example, when bittorrent will start the download from the nodes A,B,C, the ntkd monitor will add in the kernel the "best bandwidth" routes for A,B,C.
The inet-gw which share their Internet connection measure also the utilzed bandwidth of the Internet connection. The maximum download and upload bandwidth is known since it must be specified by the user in the netsukuku.conf config file. In this way, monitoring the device used by the Internet default route, it's trivial to known the available bandwidth.
The load balancing will be always used, because the routes are added in the kernel using the multipath option. The packets sent to a node will use different routes The load balancing inside Netsukuku doesn't suffer the problems of the IGS load balancing. Indeed, the ntk nodes are consistent between themself, i.e. a ntk node doesn't use NAT to reach another ntk node. related: [Netsukuku_RFC] Route bandwidth
S --64Mb/s--> R --64Mb/s--> T --32Mb/s--> O --100Mb/s--> I --100Mb/s--> D
Asymmetric routes
1: ,--<-<-<---.
/ \
S D
\ /
2: `-->->->---'Latency VS bandwidth
IGS
Load balancing