{{>toc}}

h1. Projet agregation v2

* http://ee.lbl.gov/papers/congavoid.pdf

** Congestion Avoidance and Control

* [[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/

* QoS tail drop vs by IP http://lists.tetalab.org/pipermail/tetaneutral/2011-April/000129.html

* tc http://marc.info/?l=netfilter&m=129669999112670&w=2

* tc TEQL http://lartc.org/howto/lartc.loadshare.html

* tc NATALIE http://flap.mynetmemo.com/wp-content/uploads/2012/04/NATALIE.pdf

* VXLAN Virtual eXtensible LANs layer 2 over UDP tunnel http://linux-network-plumber.blogspot.fr/2012/09/just-published-linux-kernel.html

** http://tools.ietf.org/html/draft-mahalingam-dutt-dcops-vxlan-02

** http://blogs.cisco.com/datacenter/digging-deeper-into-vxlan/

* http://hardware.slashdot.org/story/12/10/23/1946248/increasing-wireless-network-speed-by-1000-by-replacing-packets-with-algebra

** http://www.mit.edu/~medard/papers2011/Modeling%20Network%20Coded%20TCP.pdf

** http://en.wikipedia.org/wiki/Linear_network_coding

* MPTCP

** https://linuxfr.org/news/mptcp-tcp-dans-un-monde-ultra-connecte

** https://archive.fosdem.org/2012/schedule/event/multipathtcp.html

* LEDBAT

** http://www.bortzmeyer.org/6817.html

** http://tools.ietf.org/wg/ledbat

* http://www.coverfire.com/archives/2013/01/01/improving-my-home-internet-performance/

** http://git.coverfire.com/?p=linux-qos-scripts.git;a=blob;f=src-3tos.sh;hb=HEAD

** http://www.coverfire.com/archives/2011/02/21/network-latency-experiments

** http://www.coverfire.com/projects/ping-exp/

* http://multipath-tcp.org/pmwiki.php?n=Main.50Gbps

* https://code.google.com/p/kernel/wiki/NetScalingGuide

* Rate < (MSS/RTT)*(1 / sqrt(p)) where p is the probability of packet loss.

** Credit: Mathis, Semke, Mahdavi & Ott in Computer Communication Review, 27 (3), July 1997, titled The macroscopic behavior of the TCP congestion avoidance algorithm.

** http://www.infoblox.com/community/blog/tcp-performance-and-mathis-equation 

* https://gettys.wordpress.com/2013/07/10/low-latency-requires-smart-queuing-traditional-aqm-is-not-enough/

* Confused, Timid, and Unstable: Picking a Video Streaming Rate is Hard http://www.stanford.edu/~huangty/imc012-huang.pdf

* http://linuxfr.org/wiki/Une-introduction-au-contr%C3%B4le-du-trafic-r%C3%A9seau-avec-Linux

* http://www.coverfire.com/articles/queueing-in-the-linux-network-stack/

* A delay-based metric for the Babel routing protocol http://www.pps.univ-paris-diderot.fr/~jch/research/rapport-jonglez-2013.pdf

* Linux Base Driver for the Intel(R) Ethernet 10 Gigabit PCI Express Family of Adapters http://downloadmirror.intel.com/14687/eng/readme.txt

* HTB burst cburst http://mailman.ds9a.nl/pipermail/lartc/2005q3/016682.html

** http://www.docum.org/docum.org/tests/htb/burst/

** http://linux-ip.net/traffic-control/htb-class.png

** http://linux-ip.net/traffic-control/diagram.html

* Multiwan avec une Mikrotik RB750UP http://blog.lekermeur.net/?p=2129

** Load Balancing Using  PCC & RouterOS http://mum.mikrotik.com/presentations/US12/steve.pdf

* http://git.coverfire.com/?p=linux-qos-scripts.git;a=blob;f=src-3tos.sh;hb=HEAD

* UDT: Breaking the Data Transfer Bottleneck http://udt.sourceforge.net/index.html

* TCP Tuning for the Web [linux.conf.au 2014] https://www.youtube.com/watch?v=hzPVeYtoNdE

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://en.wikipedia.org/wiki/IEEE_802.3

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://www.siongboon.com/projects/2006-03-06_serial_communication

* 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 MAC f2:b3:28:1c:f4:88 

vers 10.40.0.1:32767 MAC 26:af:3e:41:71:be

envoi UDP payload "AAAA"

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. Test de re-bind

En cas de changement d'IP sur la ligne ADSL le NAT des modem / routeurs peut couper une connection UDP établie (visible sur openvpn) la solution est de forcer un changement de port source si la connection apparait comme non fonctionnelle

<pre>

import sys

import socket

mode=sys.argv[1]

RBUFL=2000

remote_port=6600

if mode=="client":

    remote_addr=sys.argv[2]

    s = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)

    s.bind(("", 0))

    peer=(remote_addr,remote_port)

    s.sendto("TOTO1",peer)

    s.close()

    s = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)

    s.bind(("", 0))

    s.sendto("TOTO2",peer)

else:

    s = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)

    s.bind(("", remote_port))

    p,peer=s.recvfrom(RBUFL)

    print p,peer

    p,peer=s.recvfrom(RBUFL)

    print p,peer

</pre>

Test :

<pre>

client$ python tbind.py client testlg1 6600

# while on server:

server$ python tbind.py server

TOTO1 ('192.168.1.18', 47975)

TOTO2 ('192.168.1.18', 60607)

</pre>

=> changement de port effectif

h2. Perte de paquet

On observe des pertes de paquets consecutifs sur la ligne ADSL free a Saint-Gaudens mais pas de saturation de buffer a 15 Mbit/s : c'est probablement ce qui explique la faible performance TCP.

!z-free-16m.png!

h2. Perte de paquet 3 lignes

Envoi de 10000 paquets de 1200 byte UDP a un rythme de 2 Mbit/s sur les 3 lignes ADSL de saint gaudens (orange, free, FDN), on mesure la variation de demi-ping = Y par time stamp reception saint-gaudens = X, le tout en nombre de microseconde

!lagstg2.png!

Les pertes sont donc bien synchrones entre les 3 lignes ADSL.

h2. Attachements