Projet agregation v2 » Historique » Version 19
Version 18 (Laurent GUERBY, 01/04/2012 13:41) → Version 19/93 (Laurent GUERBY, 01/04/2012 16:27)
{{>toc}}
h1. Projet agregation v2
* [[Projet agregation]]
* uTP (uTorrent transport protocol) is a transport protocol which uses one-way delay measurements for its congestion controller. http://www.rasterbar.com/products/libtorrent/utp.html
* Low Extra Delay Background Transport (LEDBAT) https://datatracker.ietf.org/doc/draft-ietf-ledbat-congestion/
h2. Divers
* 1 Mbit/s = 83 frames de 1500 byte/sec = 1 frame de 1500 byte toutes les 12 ms
* l'augmentation de latence sur la ligne permet la detection de la saturation des buffer
* on peut mesurer les variations de latence en regardant les variations de difference de timestamp destination moins source
* sur 1 Mbit/s si 20 utilisateurs envoient des paquets de 1500 byte ca fait 4 frame de 1500 byte/sec par utilisateur soit une latence de 250ms (~ 50 kbit/s par utilisateur)
h2. Resolution de time.time()
* http://stackoverflow.com/questions/1938048/high-precision-clock-in-python
<pre>
guerby@pc2:~/work/tetaneutral.net/python/pa2$ cat ttime.py
import time
N=1000
l=[]
for i in xrange(N):
t1=time.time()
t2=time.time()
dt=t2-t1
l.append(dt)
l.sort()
print l[0],l[-1],l[N/2],l[9*N/10]
guerby@pc2:~/work/tetaneutral.net/python/pa2$ python ttime.py
9.53674316406e-07 3.00407409668e-05 1.90734863281e-06 2.14576721191e-06
guerby@pc2:~/work/tetaneutral.net/python/pa2$ python ttime.py
9.53674316406e-07 1.19209289551e-05 1.90734863281e-06 2.14576721191e-06
guerby@pc2:~/work/tetaneutral.net/python/pa2$ python ttime.py
9.53674316406e-07 0.000508069992065 1.90734863281e-06 2.14576721191e-06
</pre>
=> autour de 2 microsecondes en pratique
h2. Résolution de select en python
<pre>
guerby@pc2:~/work/tetaneutral.net/python/pa2$ cat tselect.py
import time
import select
from socket import *
from select import select
s1 = socket(AF_INET, SOCK_DGRAM)
s2 = socket(AF_INET, SOCK_DGRAM)
N=1000
l=[]
for i in xrange(N):
t1=time.time()
r = select([s1,s2],[],[],1.0e-9)
t2=time.time()
dt=t2-t1
l.append(dt)
l.sort()
print l[0],l[-1],l[N/2],l[9*N/10]
guerby@pc2:~/work/tetaneutral.net/python/pa2$ python tselect.py
9.77516174316e-06 0.000253915786743 1.09672546387e-05 1.12056732178e-05
guerby@pc2:~/work/tetaneutral.net/python/pa2$ python tselect.py
9.77516174316e-06 5.41210174561e-05 1.09672546387e-05 1.12056732178e-05
</pre>
=> 12 microsecondes
=> 18 microsecondes avec 5 socket vs 2 donc compter + 2 micro/socket
h2. Generer un payload random
* http://docs.python.org/library/random.html
* http://docs.python.org/library/struct.html
<pre>
import random
import struct
N=256*256*256*256-1
S=160000
random.seed(0)
s="".join([struct.pack("I",random.randint(0,N)) for i in xrange(S/4)])
print S,len(s)
</pre>
h2. Premiere mesure de controle de latence : debit
* sur une ligne ADSL capable de 11 Mbit/s soutenu TCP
* du serveur (gw) vers le client (stg) on envoie un paquet UDP de 1200 byte toutes les 1200/D secondes avec un numero de sequence, un timestamp serveur en microseconde et un payload random
* sur le client on note le timestamp client en microseconde, le numero de sequence et le timestamp server du paquet
* une fois le test fini (1000 paquets) on calcule paquet par paquet la difference timestamp client moins timestamp server
* on calcul le min de ces differences sur tous les paquets
* on graphe chaque difference moins le min des difference = la deviation par rapport a la normale en microseconde
Avec D = 10 Mbit/s = en dessous de la capacité de la ligne ça donne :
!10-1200.png!
Avec D = 15 Mbit/s = au dessus de la capacité de la ligne ça donne :
!15-1200.png!
On voit sur les deux graphes des petits pics qui correspondent aux moments ou le modem ADSL pedale un peu pour envoyer.
On voit donc dans le deuxieme cas le buffer du modem se remplir au fur et a mesure de l'envoi des paquets => c'est parfaitement observable donc maitrisable.
Le but de l'algorithme de controle est de baisser le debit cible quand on voit la mesure de controle deriver pour la ramener proche d'un niveau normal.
Note : a cause d'un drift possible d'horloge entre le client et le serveur le niveau normal de la mesure doit etre calculé sur les N derniers paquets / minutes.
h2. Deuxieme mesure : paquet par seconde
Cette fois ci a debit fixé a 10 Mbit/s soit en dessous de la capacité de la ligne on fait varier la taille du paquet donc le nombre de paquet par seconde (pps)
* Taille 200 = 5485 pps 8.7 Mbit/s sur theo a 6250 pps
!10-200.png!
* Taille 350 = 3552 pps 9.9 Mbit/s sur theo a 3570 pps
!10-350.png!
* Taille 400 = 3126 pps 10 Mbit/s sur theo a 3125 pps
!10-400.png!
On voit donc qu'il y a aussi une limite de traitement en pps sur le modem qui peut entrainer du buffer bloat
A noter que si on rajoute les 20 bytes de header IP et 8 byte de header UDP dans le compteur de débit on sature plutot vers 6500 pps pour 10 Mbit/s, soit 190 byte/packet, payload de 190-20-8=162 byte
Script de test utilisé : attachment:iperf-20120304.py
h2. tuntap
http://backreference.org/2010/03/26/tuntap-interface-tutorial/
* http://www.mjmwired.net/kernel/Documentation/networking/tuntap.txt#102
<pre>
3.2 Frame format:
If flag IFF_NO_PI is not set each frame format is:
Flags [2 bytes]
Proto [2 bytes]
Raw protocol(IP, IPv6, etc) frame.
</pre>
* http://en.wikipedia.org/wiki/Ethernet_frame
<pre>
Preamble Start of frame delimiter MAC destination MAC source 802.1Q tag (optional) Ethertype (Ethernet II) or length (IEEE 802.3) Payload Frame check sequence (32âbit CRC) Interframe gap
7 octets of 10101010 1 octet of 10101011 6 octets 6 octets (4 octets) 2 octets 42â1500 octets 4 octets 12 octets
</pre>
* http://en.wikipedia.org/wiki/Ethernet_II_framing#Ethernet_II
* http://en.wikipedia.org/wiki/EtherType
For example, an EtherType value of
0x0800 signals that the frame contains an IPv4 datagram.
0x0806 indicates an ARP frame,
0x8100 indicates an IEEE 802.1Q frame
0x86DD indicates an IPv6 frame.
0x8035 RARP
0x8870 Jumbo Frames
0x88A2 ATA over Ethernet
0x88CC LLDP
0x9100 Q-in-Q
* http://en.wikipedia.org/wiki/IPv4#Packet_structure
version premier 4 bits du premier octet = 4
ip source octet 13 a 16
ip dest octet 17 a 20
* http://en.wikipedia.org/wiki/IPv6_packet
version premier 4 bits du premier octet = 6
ip source octet 9 a 24
ip dest octet 25 a 40
<pre>
# envoyer un paquet UDP "AAAA" en python IPv4 et IPv6
import socket
addr=""
buf="AAAA"
s = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
peer=("10.40.0.1",32767)
s.bind((addr, 0))
s.sendto(buf,peer)
s6 = socket.socket(socket.AF_INET6, socket.SOCK_DGRAM)
s6.bind((addr, 0))
peer6=("2a01:6600:8081:cb01::1",32767)
s6.sendto(buf,peer6)
</pre>
Resultats sur tuntap :
<pre>
ipv4
depuis 10.40.0.2 10.40.0.1 MAC f2:b3:28:1c:f4:88
vers 10.40.0.1:32767 10.40.0.2:32767 MAC 26:af:3e:41:71:be
envoi UDP payload "AAAA"
from socket paquet len = 50
000 00 000 00 008 08 000 00 038 26 175 AF 062 3E 065 41 113 71 190 BE 242 F2 179 B3 040 28 028 1C 244 F4 136 88
008 08 000 00 069 45 000 00 000 00 032 20 000 00 000 00 064 40 000 00 064 40 017 11 038 26 123 7B 010 0A 040 28
000 00 002 02 010 0A 040 28 000 00 001 01 203 CB 245 F5 127 7F 255 FF 000 00 012 0C 029 1D 012 0C 065 41 065 41
065 41 065 41
ipv4 pareil mais depuis 10.50.0.2 vers 10.50.0.1:32767 avec vlan tag 128
paquet len = 54
000 00 000 00 129 81 000 00 038 26 175 AF 062 3E 065 41 113 71 190 BE 242 F2 179 B3 040 28 028 1C 244 F4 136 88
129 81 000 00 000 00 128 80 008 08 000 00 069 45 000 00 000 00 032 20 000 00 000 00 064 40 000 00 064 40 017 11
038 26 103 67 010 0A 050 32 000 00 002 02 010 0A 050 32 000 00 001 01 178 B2 222 DE 127 7F 255 FF 000 00 012 0C
054 36 015 0F 065 41 065 41 065 41 065 41
ipv6
depuis 2a01:6600:8081:cb01::2 MAC f2:b3:28:1c:f4:88
vers [2a01:6600:8081:cb01::1]:32767 MAC 26:af:3e:41:71:be
envoi UDP payload "AAAA"
from tap paquet len = 70
000 00 000 00 134 86 221 DD 038 26 175 AF 062 3E 065 41 113 71 190 BE 242 F2 179 B3 040 28 028 1C 244 F4 136 88
134 86 221 DD 096 60 000 00 000 00 000 00 000 00 012 0C 017 11 255 FF 042 2A 001 01 102 66 000 00 128 80 129 81
203 CB 001 01 000 00 000 00 000 00 000 00 000 00 000 00 000 00 002 02 042 2A 001 01 102 66 000 00 128 80 129 81
203 CB 001 01 000 00 000 00 000 00 000 00 000 00 000 00 000 00 001 01 193 C1 022 16 127 7F 255 FF 000 00 012 0C
133 85 049 31 065 41 065 41 065 41 065 41
</pre>
h2. Compression
http://www.oberhumer.com/opensource/lzo/
<pre>
Here are some original timings done on an Intel Pentium 133 back in 1997. Multiply by a constant factor for modern machines.
memcpy(): ~60 MB/sec
LZO1X decompression in C: ~16 MB/sec
LZO1X decompression in optimized assembler: ~20 MB/sec
LZO1X-1 compression: ~5 MB/sec
More detailed results can be found in the documentation.
</pre>
https://github.com/jd-boyd/python-lzo
h2. Allocation équitable de bande passante
Les outils comme tc http://en.wikipedia.org/wiki/Tc_(Linux) permettent d'allouer equitablement de la bande passante par IP source cf leur usage actuel [[Buffer_Bloat#QoS]].
Ces outils travaillent au niveau paquet par paquet donc en présence de plusieurs paquets de 1500 bytes provenant de plusieurs utilisateurs la latence pour les petits paquets d'autre utilisateurs va être fortement impactée, par exemple si 15 utilisateurs
Une solution alternative est de travailler en volume et non plus par paquet : chaque paquet envoyé sur le tunnel va contenir des fragments de paquet de tous les utisateurs au prorata equitable.
Exemple concret : une ligne ADSL avec 15 utilisateurs, pour arrondir supporte un paquet a 1500 byte a 1 Mbit/s soit un paquet 1500 toute les 12 ms. 14 envoient du TCP a 1500 byte et le dernier fait des ping de 100 byte.
* solution par paquet classique : la latence du ping dans le pire des cas est 14*12ms= 168 ms et elle va etre fortement variable suivant le nombre de paquet de 1500 des autres utilisateurs.
* solution en volume : la latence du ping est de 12ms constante. Si le paquet ping est entre 100 et 200 alors la latence sera simplement de 2*12ms = 24ms constante aussi.
h2. Attachements
h1. Projet agregation v2
* [[Projet agregation]]
* uTP (uTorrent transport protocol) is a transport protocol which uses one-way delay measurements for its congestion controller. http://www.rasterbar.com/products/libtorrent/utp.html
* Low Extra Delay Background Transport (LEDBAT) https://datatracker.ietf.org/doc/draft-ietf-ledbat-congestion/
h2. Divers
* 1 Mbit/s = 83 frames de 1500 byte/sec = 1 frame de 1500 byte toutes les 12 ms
* l'augmentation de latence sur la ligne permet la detection de la saturation des buffer
* on peut mesurer les variations de latence en regardant les variations de difference de timestamp destination moins source
* sur 1 Mbit/s si 20 utilisateurs envoient des paquets de 1500 byte ca fait 4 frame de 1500 byte/sec par utilisateur soit une latence de 250ms (~ 50 kbit/s par utilisateur)
h2. Resolution de time.time()
* http://stackoverflow.com/questions/1938048/high-precision-clock-in-python
<pre>
guerby@pc2:~/work/tetaneutral.net/python/pa2$ cat ttime.py
import time
N=1000
l=[]
for i in xrange(N):
t1=time.time()
t2=time.time()
dt=t2-t1
l.append(dt)
l.sort()
print l[0],l[-1],l[N/2],l[9*N/10]
guerby@pc2:~/work/tetaneutral.net/python/pa2$ python ttime.py
9.53674316406e-07 3.00407409668e-05 1.90734863281e-06 2.14576721191e-06
guerby@pc2:~/work/tetaneutral.net/python/pa2$ python ttime.py
9.53674316406e-07 1.19209289551e-05 1.90734863281e-06 2.14576721191e-06
guerby@pc2:~/work/tetaneutral.net/python/pa2$ python ttime.py
9.53674316406e-07 0.000508069992065 1.90734863281e-06 2.14576721191e-06
</pre>
=> autour de 2 microsecondes en pratique
h2. Résolution de select en python
<pre>
guerby@pc2:~/work/tetaneutral.net/python/pa2$ cat tselect.py
import time
import select
from socket import *
from select import select
s1 = socket(AF_INET, SOCK_DGRAM)
s2 = socket(AF_INET, SOCK_DGRAM)
N=1000
l=[]
for i in xrange(N):
t1=time.time()
r = select([s1,s2],[],[],1.0e-9)
t2=time.time()
dt=t2-t1
l.append(dt)
l.sort()
print l[0],l[-1],l[N/2],l[9*N/10]
guerby@pc2:~/work/tetaneutral.net/python/pa2$ python tselect.py
9.77516174316e-06 0.000253915786743 1.09672546387e-05 1.12056732178e-05
guerby@pc2:~/work/tetaneutral.net/python/pa2$ python tselect.py
9.77516174316e-06 5.41210174561e-05 1.09672546387e-05 1.12056732178e-05
</pre>
=> 12 microsecondes
=> 18 microsecondes avec 5 socket vs 2 donc compter + 2 micro/socket
h2. Generer un payload random
* http://docs.python.org/library/random.html
* http://docs.python.org/library/struct.html
<pre>
import random
import struct
N=256*256*256*256-1
S=160000
random.seed(0)
s="".join([struct.pack("I",random.randint(0,N)) for i in xrange(S/4)])
print S,len(s)
</pre>
h2. Premiere mesure de controle de latence : debit
* sur une ligne ADSL capable de 11 Mbit/s soutenu TCP
* du serveur (gw) vers le client (stg) on envoie un paquet UDP de 1200 byte toutes les 1200/D secondes avec un numero de sequence, un timestamp serveur en microseconde et un payload random
* sur le client on note le timestamp client en microseconde, le numero de sequence et le timestamp server du paquet
* une fois le test fini (1000 paquets) on calcule paquet par paquet la difference timestamp client moins timestamp server
* on calcul le min de ces differences sur tous les paquets
* on graphe chaque difference moins le min des difference = la deviation par rapport a la normale en microseconde
Avec D = 10 Mbit/s = en dessous de la capacité de la ligne ça donne :
!10-1200.png!
Avec D = 15 Mbit/s = au dessus de la capacité de la ligne ça donne :
!15-1200.png!
On voit sur les deux graphes des petits pics qui correspondent aux moments ou le modem ADSL pedale un peu pour envoyer.
On voit donc dans le deuxieme cas le buffer du modem se remplir au fur et a mesure de l'envoi des paquets => c'est parfaitement observable donc maitrisable.
Le but de l'algorithme de controle est de baisser le debit cible quand on voit la mesure de controle deriver pour la ramener proche d'un niveau normal.
Note : a cause d'un drift possible d'horloge entre le client et le serveur le niveau normal de la mesure doit etre calculé sur les N derniers paquets / minutes.
h2. Deuxieme mesure : paquet par seconde
Cette fois ci a debit fixé a 10 Mbit/s soit en dessous de la capacité de la ligne on fait varier la taille du paquet donc le nombre de paquet par seconde (pps)
* Taille 200 = 5485 pps 8.7 Mbit/s sur theo a 6250 pps
!10-200.png!
* Taille 350 = 3552 pps 9.9 Mbit/s sur theo a 3570 pps
!10-350.png!
* Taille 400 = 3126 pps 10 Mbit/s sur theo a 3125 pps
!10-400.png!
On voit donc qu'il y a aussi une limite de traitement en pps sur le modem qui peut entrainer du buffer bloat
A noter que si on rajoute les 20 bytes de header IP et 8 byte de header UDP dans le compteur de débit on sature plutot vers 6500 pps pour 10 Mbit/s, soit 190 byte/packet, payload de 190-20-8=162 byte
Script de test utilisé : attachment:iperf-20120304.py
h2. tuntap
http://backreference.org/2010/03/26/tuntap-interface-tutorial/
* http://www.mjmwired.net/kernel/Documentation/networking/tuntap.txt#102
<pre>
3.2 Frame format:
If flag IFF_NO_PI is not set each frame format is:
Flags [2 bytes]
Proto [2 bytes]
Raw protocol(IP, IPv6, etc) frame.
</pre>
* http://en.wikipedia.org/wiki/Ethernet_frame
<pre>
Preamble Start of frame delimiter MAC destination MAC source 802.1Q tag (optional) Ethertype (Ethernet II) or length (IEEE 802.3) Payload Frame check sequence (32âbit CRC) Interframe gap
7 octets of 10101010 1 octet of 10101011 6 octets 6 octets (4 octets) 2 octets 42â1500 octets 4 octets 12 octets
</pre>
* http://en.wikipedia.org/wiki/Ethernet_II_framing#Ethernet_II
* http://en.wikipedia.org/wiki/EtherType
For example, an EtherType value of
0x0800 signals that the frame contains an IPv4 datagram.
0x0806 indicates an ARP frame,
0x8100 indicates an IEEE 802.1Q frame
0x86DD indicates an IPv6 frame.
0x8035 RARP
0x8870 Jumbo Frames
0x88A2 ATA over Ethernet
0x88CC LLDP
0x9100 Q-in-Q
* http://en.wikipedia.org/wiki/IPv4#Packet_structure
version premier 4 bits du premier octet = 4
ip source octet 13 a 16
ip dest octet 17 a 20
* http://en.wikipedia.org/wiki/IPv6_packet
version premier 4 bits du premier octet = 6
ip source octet 9 a 24
ip dest octet 25 a 40
<pre>
# envoyer un paquet UDP "AAAA" en python IPv4 et IPv6
import socket
addr=""
buf="AAAA"
s = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
peer=("10.40.0.1",32767)
s.bind((addr, 0))
s.sendto(buf,peer)
s6 = socket.socket(socket.AF_INET6, socket.SOCK_DGRAM)
s6.bind((addr, 0))
peer6=("2a01:6600:8081:cb01::1",32767)
s6.sendto(buf,peer6)
</pre>
Resultats sur tuntap :
<pre>
ipv4
depuis 10.40.0.2 10.40.0.1 MAC f2:b3:28:1c:f4:88
vers 10.40.0.1:32767 10.40.0.2:32767 MAC 26:af:3e:41:71:be
envoi UDP payload "AAAA"
from socket paquet len = 50
000 00 000 00 008 08 000 00 038 26 175 AF 062 3E 065 41 113 71 190 BE 242 F2 179 B3 040 28 028 1C 244 F4 136 88
008 08 000 00 069 45 000 00 000 00 032 20 000 00 000 00 064 40 000 00 064 40 017 11 038 26 123 7B 010 0A 040 28
000 00 002 02 010 0A 040 28 000 00 001 01 203 CB 245 F5 127 7F 255 FF 000 00 012 0C 029 1D 012 0C 065 41 065 41
065 41 065 41
ipv4 pareil mais depuis 10.50.0.2 vers 10.50.0.1:32767 avec vlan tag 128
paquet len = 54
000 00 000 00 129 81 000 00 038 26 175 AF 062 3E 065 41 113 71 190 BE 242 F2 179 B3 040 28 028 1C 244 F4 136 88
129 81 000 00 000 00 128 80 008 08 000 00 069 45 000 00 000 00 032 20 000 00 000 00 064 40 000 00 064 40 017 11
038 26 103 67 010 0A 050 32 000 00 002 02 010 0A 050 32 000 00 001 01 178 B2 222 DE 127 7F 255 FF 000 00 012 0C
054 36 015 0F 065 41 065 41 065 41 065 41
ipv6
depuis 2a01:6600:8081:cb01::2 MAC f2:b3:28:1c:f4:88
vers [2a01:6600:8081:cb01::1]:32767 MAC 26:af:3e:41:71:be
envoi UDP payload "AAAA"
from tap paquet len = 70
000 00 000 00 134 86 221 DD 038 26 175 AF 062 3E 065 41 113 71 190 BE 242 F2 179 B3 040 28 028 1C 244 F4 136 88
134 86 221 DD 096 60 000 00 000 00 000 00 000 00 012 0C 017 11 255 FF 042 2A 001 01 102 66 000 00 128 80 129 81
203 CB 001 01 000 00 000 00 000 00 000 00 000 00 000 00 000 00 002 02 042 2A 001 01 102 66 000 00 128 80 129 81
203 CB 001 01 000 00 000 00 000 00 000 00 000 00 000 00 000 00 001 01 193 C1 022 16 127 7F 255 FF 000 00 012 0C
133 85 049 31 065 41 065 41 065 41 065 41
</pre>
h2. Compression
http://www.oberhumer.com/opensource/lzo/
<pre>
Here are some original timings done on an Intel Pentium 133 back in 1997. Multiply by a constant factor for modern machines.
memcpy(): ~60 MB/sec
LZO1X decompression in C: ~16 MB/sec
LZO1X decompression in optimized assembler: ~20 MB/sec
LZO1X-1 compression: ~5 MB/sec
More detailed results can be found in the documentation.
</pre>
https://github.com/jd-boyd/python-lzo
h2. Allocation équitable de bande passante
Les outils comme tc http://en.wikipedia.org/wiki/Tc_(Linux) permettent d'allouer equitablement de la bande passante par IP source cf leur usage actuel [[Buffer_Bloat#QoS]].
Ces outils travaillent au niveau paquet par paquet donc en présence de plusieurs paquets de 1500 bytes provenant de plusieurs utilisateurs la latence pour les petits paquets d'autre utilisateurs va être fortement impactée, par exemple si 15 utilisateurs
Une solution alternative est de travailler en volume et non plus par paquet : chaque paquet envoyé sur le tunnel va contenir des fragments de paquet de tous les utisateurs au prorata equitable.
Exemple concret : une ligne ADSL avec 15 utilisateurs, pour arrondir supporte un paquet a 1500 byte a 1 Mbit/s soit un paquet 1500 toute les 12 ms. 14 envoient du TCP a 1500 byte et le dernier fait des ping de 100 byte.
* solution par paquet classique : la latence du ping dans le pire des cas est 14*12ms= 168 ms et elle va etre fortement variable suivant le nombre de paquet de 1500 des autres utilisateurs.
* solution en volume : la latence du ping est de 12ms constante. Si le paquet ping est entre 100 et 200 alors la latence sera simplement de 2*12ms = 24ms constante aussi.
h2. Attachements