Projet

Général

Profil

Projet agregation v2 » Historique » Version 17

Laurent GUERBY, 01/04/2012 13:02

1 14 Laurent GUERBY
{{>toc}}
2 14 Laurent GUERBY
3 1 Laurent GUERBY
h1. Projet agregation v2
4 1 Laurent GUERBY
5 12 Laurent GUERBY
* [[Projet agregation]]
6 12 Laurent GUERBY
* 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
7 13 Laurent GUERBY
* Low Extra Delay Background Transport (LEDBAT) https://datatracker.ietf.org/doc/draft-ietf-ledbat-congestion/
8 1 Laurent GUERBY
9 1 Laurent GUERBY
h2. Divers
10 1 Laurent GUERBY
11 1 Laurent GUERBY
* 1 Mbit/s = 83 frames de 1500 byte/sec = 1 frame de 1500 byte toutes les 12 ms
12 1 Laurent GUERBY
* l'augmentation de latence sur la ligne permet la detection de la saturation des buffer
13 1 Laurent GUERBY
* on peut mesurer les variations de latence en regardant les variations de difference de timestamp destination moins source
14 8 Laurent GUERBY
* 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)
15 2 Laurent GUERBY
16 6 Laurent GUERBY
h2. Resolution de time.time()
17 1 Laurent GUERBY
18 4 Laurent GUERBY
* http://stackoverflow.com/questions/1938048/high-precision-clock-in-python
19 2 Laurent GUERBY
20 4 Laurent GUERBY
<pre>
21 2 Laurent GUERBY
guerby@pc2:~/work/tetaneutral.net/python/pa2$ cat ttime.py 
22 2 Laurent GUERBY
import time
23 2 Laurent GUERBY
24 2 Laurent GUERBY
N=1000
25 2 Laurent GUERBY
l=[]
26 2 Laurent GUERBY
for i in xrange(N):
27 2 Laurent GUERBY
    t1=time.time()
28 2 Laurent GUERBY
    t2=time.time()
29 2 Laurent GUERBY
    dt=t2-t1
30 2 Laurent GUERBY
    l.append(dt)
31 2 Laurent GUERBY
32 2 Laurent GUERBY
l.sort()
33 2 Laurent GUERBY
print l[0],l[-1],l[N/2],l[9*N/10]
34 2 Laurent GUERBY
guerby@pc2:~/work/tetaneutral.net/python/pa2$ python ttime.py 
35 2 Laurent GUERBY
9.53674316406e-07 3.00407409668e-05 1.90734863281e-06 2.14576721191e-06
36 2 Laurent GUERBY
guerby@pc2:~/work/tetaneutral.net/python/pa2$ python ttime.py 
37 2 Laurent GUERBY
9.53674316406e-07 1.19209289551e-05 1.90734863281e-06 2.14576721191e-06
38 2 Laurent GUERBY
guerby@pc2:~/work/tetaneutral.net/python/pa2$ python ttime.py 
39 2 Laurent GUERBY
9.53674316406e-07 0.000508069992065 1.90734863281e-06 2.14576721191e-06
40 2 Laurent GUERBY
</pre>
41 2 Laurent GUERBY
42 2 Laurent GUERBY
=> autour de 2 microsecondes en pratique
43 3 Laurent GUERBY
44 6 Laurent GUERBY
h2. Résolution de select en python
45 3 Laurent GUERBY
46 4 Laurent GUERBY
<pre>
47 3 Laurent GUERBY
guerby@pc2:~/work/tetaneutral.net/python/pa2$ cat tselect.py 
48 3 Laurent GUERBY
import time
49 3 Laurent GUERBY
import select
50 3 Laurent GUERBY
from socket import *
51 3 Laurent GUERBY
from select import select
52 3 Laurent GUERBY
53 3 Laurent GUERBY
54 3 Laurent GUERBY
55 3 Laurent GUERBY
s1 = socket(AF_INET, SOCK_DGRAM)
56 3 Laurent GUERBY
s2 = socket(AF_INET, SOCK_DGRAM)
57 3 Laurent GUERBY
58 3 Laurent GUERBY
N=1000
59 3 Laurent GUERBY
l=[]
60 3 Laurent GUERBY
for i in xrange(N):
61 3 Laurent GUERBY
    t1=time.time()
62 3 Laurent GUERBY
    r = select([s1,s2],[],[],1.0e-9)
63 3 Laurent GUERBY
    t2=time.time()
64 3 Laurent GUERBY
    dt=t2-t1
65 3 Laurent GUERBY
    l.append(dt)
66 3 Laurent GUERBY
67 3 Laurent GUERBY
l.sort()
68 1 Laurent GUERBY
print l[0],l[-1],l[N/2],l[9*N/10]
69 3 Laurent GUERBY
guerby@pc2:~/work/tetaneutral.net/python/pa2$ python tselect.py 
70 3 Laurent GUERBY
9.77516174316e-06 0.000253915786743 1.09672546387e-05 1.12056732178e-05
71 3 Laurent GUERBY
guerby@pc2:~/work/tetaneutral.net/python/pa2$ python tselect.py 
72 3 Laurent GUERBY
9.77516174316e-06 5.41210174561e-05 1.09672546387e-05 1.12056732178e-05
73 4 Laurent GUERBY
</pre>
74 3 Laurent GUERBY
75 1 Laurent GUERBY
=> 12 microsecondes
76 1 Laurent GUERBY
=> 18 microsecondes avec 5 socket vs 2 donc compter + 2 micro/socket
77 6 Laurent GUERBY
78 6 Laurent GUERBY
h2. Generer un payload random
79 6 Laurent GUERBY
80 6 Laurent GUERBY
* http://docs.python.org/library/random.html
81 6 Laurent GUERBY
* http://docs.python.org/library/struct.html
82 6 Laurent GUERBY
83 6 Laurent GUERBY
<pre>
84 6 Laurent GUERBY
import random
85 6 Laurent GUERBY
import struct
86 6 Laurent GUERBY
87 6 Laurent GUERBY
88 6 Laurent GUERBY
N=256*256*256*256-1
89 6 Laurent GUERBY
S=160000
90 6 Laurent GUERBY
random.seed(0)
91 6 Laurent GUERBY
s="".join([struct.pack("I",random.randint(0,N)) for i in xrange(S/4)])
92 6 Laurent GUERBY
print S,len(s)
93 6 Laurent GUERBY
</pre>
94 6 Laurent GUERBY
95 9 Laurent GUERBY
h2. Premiere mesure de controle de latence : debit
96 6 Laurent GUERBY
97 6 Laurent GUERBY
* sur une ligne ADSL capable de 11 Mbit/s soutenu TCP
98 6 Laurent GUERBY
* 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
99 6 Laurent GUERBY
* sur le client on note le timestamp client en microseconde, le numero de sequence et le timestamp server du paquet
100 6 Laurent GUERBY
* une fois le test fini (1000 paquets) on calcule paquet par paquet la difference timestamp client moins timestamp server
101 7 Laurent GUERBY
* on calcul le min de ces differences sur tous les paquets
102 7 Laurent GUERBY
* on graphe chaque difference moins le min des difference = la deviation par rapport a la normale en microseconde
103 6 Laurent GUERBY
104 6 Laurent GUERBY
Avec D = 10 Mbit/s = en dessous de la capacité de la ligne ça donne :
105 6 Laurent GUERBY
106 6 Laurent GUERBY
!10-1200.png!
107 6 Laurent GUERBY
108 6 Laurent GUERBY
Avec D = 15 Mbit/s = au dessus de la capacité de la ligne ça donne :
109 1 Laurent GUERBY
110 1 Laurent GUERBY
!15-1200.png!
111 6 Laurent GUERBY
112 7 Laurent GUERBY
On voit sur les deux graphes des petits pics qui correspondent aux moments ou le modem ADSL pedale un peu pour envoyer.
113 7 Laurent GUERBY
114 1 Laurent GUERBY
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.
115 6 Laurent GUERBY
116 7 Laurent GUERBY
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.
117 7 Laurent GUERBY
118 1 Laurent GUERBY
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.
119 9 Laurent GUERBY
120 9 Laurent GUERBY
h2. Deuxieme mesure : paquet par seconde
121 9 Laurent GUERBY
122 9 Laurent GUERBY
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)
123 9 Laurent GUERBY
124 9 Laurent GUERBY
* Taille 200 = 5485 pps 8.7 Mbit/s sur theo a 6250 pps
125 9 Laurent GUERBY
!10-200.png!
126 9 Laurent GUERBY
127 9 Laurent GUERBY
* Taille 350 = 3552 pps 9.9 Mbit/s sur theo a 3570 pps
128 9 Laurent GUERBY
!10-350.png!
129 9 Laurent GUERBY
130 9 Laurent GUERBY
* Taille 400 = 3126 pps 10 Mbit/s sur theo a 3125 pps
131 9 Laurent GUERBY
!10-400.png!
132 9 Laurent GUERBY
133 9 Laurent GUERBY
On voit donc qu'il y a aussi une limite de traitement en pps sur le modem qui peut entrainer du buffer bloat
134 10 Laurent GUERBY
135 11 Laurent GUERBY
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
136 10 Laurent GUERBY
137 11 Laurent GUERBY
Script de test utilisé : attachment:iperf-20120304.py
138 14 Laurent GUERBY
139 14 Laurent GUERBY
h2. tuntap
140 14 Laurent GUERBY
141 14 Laurent GUERBY
http://backreference.org/2010/03/26/tuntap-interface-tutorial/
142 14 Laurent GUERBY
143 14 Laurent GUERBY
* http://www.mjmwired.net/kernel/Documentation/networking/tuntap.txt#102
144 14 Laurent GUERBY
<pre>
145 14 Laurent GUERBY
3.2 Frame format:
146 14 Laurent GUERBY
	  If flag IFF_NO_PI is not set each frame format is: 
147 14 Laurent GUERBY
	     Flags [2 bytes]
148 14 Laurent GUERBY
	     Proto [2 bytes]
149 14 Laurent GUERBY
	     Raw protocol(IP, IPv6, etc) frame.
150 14 Laurent GUERBY
</pre>
151 14 Laurent GUERBY
152 14 Laurent GUERBY
153 14 Laurent GUERBY
* http://en.wikipedia.org/wiki/Ethernet_frame
154 14 Laurent GUERBY
<pre>
155 14 Laurent GUERBY
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
156 14 Laurent GUERBY
7 octets of 10101010	1 octet of 10101011	6 octets	6 octets	(4 octets)	2 octets	42–1500 octets	4 octets	12 octets
157 14 Laurent GUERBY
</pre>
158 14 Laurent GUERBY
159 16 Laurent GUERBY
* http://en.wikipedia.org/wiki/Ethernet_II_framing#Ethernet_II
160 17 Laurent GUERBY
* http://en.wikipedia.org/wiki/EtherType
161 17 Laurent GUERBY
For example, an EtherType value of 
162 17 Laurent GUERBY
0x0800 signals that the frame contains an IPv4 datagram. 
163 17 Laurent GUERBY
0x0806 indicates an ARP frame, 
164 17 Laurent GUERBY
0x8100 indicates an IEEE 802.1Q frame
165 17 Laurent GUERBY
0x86DD indicates an IPv6 frame. 
166 17 Laurent GUERBY
0x8035 RARP
167 17 Laurent GUERBY
0x8870	Jumbo Frames
168 17 Laurent GUERBY
0x88A2	ATA over Ethernet
169 17 Laurent GUERBY
0x88CC	LLDP
170 17 Laurent GUERBY
0x9100	Q-in-Q
171 17 Laurent GUERBY
172 16 Laurent GUERBY
173 14 Laurent GUERBY
* http://en.wikipedia.org/wiki/IPv4#Packet_structure
174 14 Laurent GUERBY
version premier 4 bits du premier octet = 4
175 14 Laurent GUERBY
ip source octet 13 a 16
176 14 Laurent GUERBY
ip dest octet 17 a 20
177 14 Laurent GUERBY
178 14 Laurent GUERBY
* http://en.wikipedia.org/wiki/IPv6_packet
179 14 Laurent GUERBY
version premier 4 bits du premier octet = 6
180 14 Laurent GUERBY
ip source octet 9 a 24
181 14 Laurent GUERBY
ip dest octet 25 a 40
182 15 Laurent GUERBY
183 15 Laurent GUERBY
h2. Compression
184 15 Laurent GUERBY
185 15 Laurent GUERBY
http://www.oberhumer.com/opensource/lzo/
186 15 Laurent GUERBY
<pre>
187 15 Laurent GUERBY
Here are some original timings done on an Intel Pentium 133 back in 1997. Multiply by a constant factor for modern machines.
188 15 Laurent GUERBY
189 15 Laurent GUERBY
memcpy(): ~60 MB/sec
190 15 Laurent GUERBY
LZO1X decompression in C: ~16 MB/sec
191 15 Laurent GUERBY
LZO1X decompression in optimized assembler: ~20 MB/sec
192 15 Laurent GUERBY
LZO1X-1 compression: ~5 MB/sec
193 15 Laurent GUERBY
More detailed results can be found in the documentation.
194 15 Laurent GUERBY
</pre>
195 15 Laurent GUERBY
196 15 Laurent GUERBY
https://github.com/jd-boyd/python-lzo
197 15 Laurent GUERBY
198 15 Laurent GUERBY
h2. Allocation équitable de bande passante
199 15 Laurent GUERBY
200 15 Laurent GUERBY
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]].
201 15 Laurent GUERBY
202 15 Laurent GUERBY
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
203 15 Laurent GUERBY
204 15 Laurent GUERBY
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.
205 15 Laurent GUERBY
206 15 Laurent GUERBY
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.
207 15 Laurent GUERBY
* 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.
208 15 Laurent GUERBY
* 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.
209 15 Laurent GUERBY
210 15 Laurent GUERBY
211 15 Laurent GUERBY
h2. Attachements