|
Size: 7733
Comment:
|
Size: 7321
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 28: | Line 28: |
| 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. |
There are two phases of measurement. In the first the total bandwidth capacity 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. |
| Line 33: | Line 33: |
/* 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 # We also need to know the total bandwidth which can handle the network # interface. What is a good method to do this? # |
|
| Line 53: | Line 42: |
| 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. |
There are different methods to measure the bandwidth of a link. The first and the simplest is to send an indefinite amount of random packets, for some seconds, to the destination of the link. The trasmission rate is then monitored with libpcap and the maximum rate of bytes per second is registered as the maximum available upload bandwidth for that specific link. This method is very effective, indeed the measured bw is the real one and is not approximated. Its side effect is that it requires the complete saturation of the link, for some seconds. The second technique is more refined. It consists in the Packet Pair and Packet Train techniques, see http://perform.wpi.edu/downloads/wbest/README and http://www-static.cc.gatech.edu/fac/Constantinos.Dovrolis/bw.html |
| Line 58: | Line 58: |
| C. In the end we have the measurement of: A->B, B->A, C->B, B->C. | C. In the end, we have the measurement of: A->B, B->A, C->B, B->C. |
| Line 68: | Line 70: |
| cur_used_link_bw= amount of bandwidth currently used | |
| Line 70: | Line 71: |
| Max_NIC_bw = maximum bandwidth of the network interface cur_used_NIC_bw = amount of the total bandwidth currently used of the network interface }}} To 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 |
nflows = number of flows which compete for bw on the same link. A flow is the stream of packets associated to a specific connection |
| Line 123: | Line 107: |
| The QSPN gives to each node the best download route to reach all the other | The QSPN v1 gives to each node the best download route to reach all the other |
| Line 152: | Line 136: |
Note that in the QSPN v2 there's a builtin support for the asymmetric routing. |
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 capacity 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.
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.
There are different methods to measure the bandwidth of a link.
The first and the simplest is to send an indefinite amount of random packets, for some seconds, to the destination of the link. The trasmission rate is then monitored with libpcap and the maximum rate of bytes per second is registered as the maximum available upload bandwidth for that specific link. This method is very effective, indeed the measured bw is the real one and is not approximated. Its side effect is that it requires the complete saturation of the link, for some seconds.
The second technique is more refined. It consists in the Packet Pair and Packet Train techniques, see http://perform.wpi.edu/downloads/wbest/README and http://www-static.cc.gatech.edu/fac/Constantinos.Dovrolis/bw.html
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
nflows = number of flows which compete for bw on the same link.
A flow is the stream of packets associated to a specific
connection
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 v1 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. Note that in the QSPN v2 there's a builtin support for the asymmetric routing.
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