EMule et BitTorrent 70 % plus rapides grâce à Intel ?

Inscrit le 13/08/2002
24735 messages publiés
Envoyer un message privé
Guillaume Champeau , sujet ouvert le 13/04/2007 à 11:02
Intel et deux universités américaines ont communiqué cette semaine les résultats de travaux de recherche visant à accélérer les transferts de fichiers en P2P. Leur méthode, Similarity-Enhanced Transfer (SET), promet d'accélerer jusqu'à 70 % la vitesse des téléchargements. Comment est-ce possible ?

Le fondeur de microprocesseurs Intel a depuis longtemps marqué son intérêt pour les réseaux P2P. Sa filiale d'investissement a misé l'an dernier 7 millions de dollars sur Pando, un service de partage de fichiers en P2P par e-mail (concurrent direct du français Podmailer). En 2004, Intel avait également lancé son Philanthropic Peer-to-Peer Program pour aider la recherche dans le domaine du calcul distribué pour les applications médicales de type Folding@Home, qui reposent sur les mêmes architectures types que les applications de partage de fichiers.

Cette semaine, Intel a présenté officiellement une nouvelle méthode de P2P mise au point avec les Universités de Carnegie Mellon et Purdue. Selon leurs travaux, la méthode baptisée Similarity-Enhanced Transfer (SET) permettrait d'accélerer les transferts sur les réseaux P2P de 30 à 70 %. Une jolie promesse, qui repose sur l'amélioration d'une technique de mise en pièces des fichiers déjà exploitée par la plupart des applications comme eMule. Elle part du principe que plusieurs fichiers différents qui circulent sur un même réseau peuvent contenir des données similaires qui peuvent être indifféremment reprises pour reconstituer l'un ou l'autre des fichiers. Par exemple, un film original en anglais et le même film doublé en français n'ont que la bande son qui diffère. Il serait donc possible lors du téléchargement de prendre la piste vidéo à la fois sur le fichier de la VO et le fichier de la VF. Idem pour les fichiers MP3 dont seul les métadonnées (tags) ont été modifiés d'un fichier à l'autre, ou pour des versions différentes d'un même logiciel.

Une technique utilisable sur tous les réseaux P2P

Actuellement, chaque fichier sur un réseau P2P est identifié de façon unique par un code appelé "hash", calculé à partir de chaque octet du fichier. Changez un seul octet, et tout le hash est modifié, rendant impossible les échanges entre des documents identiques aux hashs différents. Pour pallier à cette lacune, La méthode SET divise chacun des fichiers en une multitude de morceaux (chunks) différents. Alors qu'eMule le fait déjà en coupant chaque fichier en morceaux de 9 Mo avant de le reconstituer (et ceci uniquement pour limiter les corruptions en cours de téléchargement), SET propose de diviser les fichiers en morceaux infimes de quelques kilo-octets seulement. Le hash de chaque petite miette est alors calculé, passé à la moulinette, et pour ne pas saturer les réseaux et capacités de calcul, un petit échantillon de quelques dizaines de hash seulement est ensuite compilé dans un ordre savamment pensé.

Cet échantillon est alors rendu public sur le réseau P2P, et chaque utilisateur qui souhaite télécharger ou partager un fichier peut comparer son propre échantillon avec celui du voisin. Avec un échantillon de seulement 30 petits morceaux, les chercheurs affirment qu'ils reconnaissent empiriquement 99 % des fichiers similaires. Si l'échantillon est suffisamment proche de celui recherché, l'ensemble des hash de tous les morceaux sont aors communiqués pour permettre les transfersts des morceaux identiques, même si dans sa totalité le fichier n'a pas le même hash.

La technique a été expérimentée sur différents réseaux P2P, dont BitTorrent, avec différents films et fichiers MP3. Grâce à SET, ils ont pu télécharger une bande annonce de 30 Mb en trois fois moins de temps qu'il en aurait fallu normalement, car ils ont su trouver des sources alternatives qui possédaient au moins 50 % de similarité. Les vitesses de transferts sur certains fichiers MP3 ont pu être accéléré de 70 %. Selon leurs simulations, la technique fonctionne le mieux sur les infrastructures réseaux les moins rapides, qui sont les plus courantes, notamment pour les connexions ADSL qui sont assymétriques. Lorsque les réseaux sont très rapides avec clients et serveurs qui communiquent à plein, le gain est minimum.

Ils encouragent chaque concepteur de logiciel de P2P à implanter leur méthode. Il y a seulement trois paramètres à définir : la taille des chunks (qui doit être un compromis entre optimisation des transferts et probabilité d'avoir des morceaux identiques), le nombre de chunks à placer dans l'échantillon (ils ont calculé que 28 morceaux leur donnait une probabilité de 90 % de trouver des fichiers qui avaient plus de 10 % de similarité, et le seuil de similarité des échantillons au dessus duquel on peut entrer en deuxième phase de transfert.

Lire la suite
18 réponses
Inscrit le 05/04/2007
10 messages publiés

Actuellement, chaque fichier sur un réseau P2P est identifié de façon unique par un code appelé "hash", calculé à partir de chaque octet du fichier. Changez un seul octet, et tout le hash est modifié, rendant impossible les échanges entre des documents identiques aux hashs différents. Pour pallier à cette lacune, La méthode SET divise chacun des fichiers en une multitude de morceaux (chunks) différents. Alors qu'eMule le fait déjà en coupant chaque fichier en morceaux de 9 Mo avant de le reconstituer (et ceci uniquement pour limiter les corruptions en cours de téléchargement), SET propose de diviser les fichiers en morceaux infimes de quelques kilo-octets seulement. Le hash de chaque petite miette est alors calculé, passé à la moulinette, et pour ne pas saturer les réseaux et capacités de calcul, un petit échantillon de quelques dizaines de hash seulement est ensuite compilé dans un ordre savamment pensé.



Pas idiot Faut juste s'assurer d'utiliser une méthode de hash qui provoque pas de collisions (Deux parties différentes -> même hash), ou avec une probabilité infime, sinon ça marche plus
Inscrit le 03/02/2005
963 messages publiés
En allant jusqu'au bout du raisonnement, on pourrait avoir un réseau qui met à disposition des elements si petits (ex:256octets, dans ce cas pas de compromis d'optimisation) qu'ils n'appartiendraient à aucune oeuvre en particulier.

Chaque client diffusant ces petits vecteurs d'information à ceux qui les réclament...
Pas de hash global de fichier, donc plus de mise à disposition d'oeuvre protégée.

Seul les "catalogues" de hash reconstituant l'ensemble des vecteurs d'une même oeuvre serait interdit.

En se servant d'un gigantesque dictionnaire des vecteurs possédés par tout le monde, on pourrait décomposer n'importe quelle oeuvre en simple catalogue de hash, recomposable en demandant à chacun les vecteurs correspondant.

Ce ne serait plus du multi-sourcing, mais de l'omni-sourcing.
Certes, ca reste asses théorique...
Inscrit le 15/05/2003
240 messages publiés
Ouais enfin c'est un peu osé de dire que ça améliore la vitesse de transfert. Disons que c'est peu précis. Ca améliore effectivement en théorie la vitesse moyenne (donc on peut dl plus souvent le fichier et donc le dl en sera bien évidemment plus rapide). Alors oui c'est très utile pour les réseaux comme eMule mais pour bitto ça l'est déjà bcp moins. Perso suffit de trouver les bons trackers et tu dl en perm à vitesse max de ta bande passante (on dit merci aux pays nordiques ).
Et sur des systèmes de serveurs à clients je ne vois absolument pas où l'on pourrait avoir un gain de vitesse, même minime !

Da Cryptum
Inscrit le 09/02/2005
480 messages publiés
En fait ça n'augmente pas la vitesse de téléchargement, mais ça augmente les sources possibles. Par contre j'ai du mal a imaginer que ca marche aussi bien : 2 musiques encodées avec divers encodeurs mp3, donneront des fichiers assez différents bit par bit, même si en gros ça donne la même chose (à l'oreille..).
Par contre ca peut très bien marcher pour 2 mp3 identiques, avec juste idtags différents, ça reviendrait à partager juste les idtags, c'est pas mal!


godvicien> après calcul, un fichier de 700Mo serait décomposé en 2734375 'vecteurs' de 256 octets, il y a environ 10^220 'vecteurs' de 256 octets possibles, donc pour les identifier c'est pas pratique... Donc on ne peut pas créer un catalogue global qui recollerait les 'vecteurs', ça reviendrait à bosser en base 256*8=2048 au lieu de base 2, et le partage de chaque vecteur serait inutile, car on téléchargerait le catalogue, qui liste les vecteurs, et avec une table gigantesque (10^220 entrées), on recrée le fichier binaire.
Bref ça ne fonctionne pas comme ça, et ici ce n'est pas un catalogue global, mais bien chaque source qui se débrouille avec ceux qui veulent télécharger, ça devient local, et donc possible.

En tout cas ce qui serait intéressant c'est de faire une étude mathématique de la chose pour trouver le bon compromis sur les 3 paramètres cités dans l'article.
Inscrit le 02/04/2006
2208 messages publiés
Vous seriez pas en train d'essayer de faire interdire l'exeption de courte citation par hasard ?
Inscrit le 30/03/2007
392 messages publiés
C'est Logistep qui va se frotter les mains...
Inscrit le 29/01/2005
428 messages publiés
bonne idée mais mauvaise idée

En tout cas pour eMule.

D'une part, ça augmentera peut être le téléchargement d'un client, mais de toute façon, il y aura une comprensation sur le réseau, à cause de la sacro sainte règle UL=DL
En aucun cas, ça n'aidera à améliorer la vitesse de téléchargement sur le réseau...

D'autre part, ça créera forcément plus d'overhead (pour les clients et les serveurs) et d'utilisation de mémoire, car va falloir le gérer le système de reconnaissance des hashs

Et puis c'est très aléatoire leur histoire. Ca ne marchera qu'avec des fichiers quasi identiques, comme dit dans l'article, si les MDs sont modifiés, pour le truc des pistes... mais c'est très restreint car l'encodage doit être le même, la taille doit être la même (ou en tout cas le début) sinon on décalle tout le découpage des chunks et plus rien ne correspond!
Du coup, ça ne marche que si les fichiers proviennent d'une même source

Enfin bref, fausse bonne idée dans l'immédiat pour eMule. C'en est discuté sur le forum d'emule-project .
[message édité par DarkVanneur le 14/04/2007 à 00:15 ]
Inscrit le 03/02/2005
963 messages publiés

Et puis c'est très aléatoire leur histoire. Ca ne marchera qu'avec des fichiers quasi identiques, comme dit dans l'article, si les MDs sont modifiés, pour le truc des pistes... mais c'est très restreint car l'encodage doit être le même, la taille doit être la même (ou en tout cas le début) sinon on décalle tout le découpage des chunks et plus rien ne correspond!


Intéressant !

imaginons un fichier :
Fichier Z = ACTGGTCACGTAGCATCGATCGATCGTACGTACGTACGTACTAGCTACCTG hash=10257
Et sa copie à 99% : le seul dernier G est retiré et replacé au début, ce qui décale tout d'une lettre :
Fichier X = GACTGGTCACGTAGCATCGATCGATCGTACGTACGTACGTACTAGCTACCT hash=45423

En effet. Une seule lettre de décalée est le hash global est modifié de telle sorte qu'il n'est plus du tout comparable à l'original.
Pourtant sémantiquement, nous savons que les 2 fichiers sont quasi-identiques : reprendre le premier 'G' du fichier X, et le remettre à la fin pour obtenir une copie de Z.

Tous les protocoles découpent maintenant les fichiers en sous parties qui ont un hash individuel :

Fichier Z = ACT-GGT-CAC-GTA-GCA-TCG-ATC-GAT-CGT-ACG-TAC-GTA-CGT-ACT-AGC-TAC-CTG
hashs === 465-154-687-132-687-984-548-946-135-768-351-687-451-876-416-779-354

Fichier X = GAC-TGG-TCA-CGT-AGC-ATC-GAT-CGA-TCG-TAC-GTA-CGT-ACG-TAC-TAG-CTA-CCT
hashs === 646-415-468-132-168-984-354-946-513-576-435-687-945-687-641-779-435

On voit que ce mécanisme ne permet pas de rectifier le décalage d'une seule lettre entre Z et X.
Tous les hash sont differents, et on ne peut considérer "X" comme identique à 99% de "Z", ce qu'il est pourtant.
Donc X ne peut servir de source pour reconstituer Z, ce qui n'est pas optimal.

C'est peut être là une l'amelioration possible (ce qu'a p-e fait intel).

Avant de calculer les hash, Il faut découper sémantiquement les fichiers :
- Séparer les headers, tags, pistes sonores, pistes vidéo, textes
- Découper les pistes en séquences, voir en images, formes...

Ce qui donne comme découpage sémantique :

Fichier Z = (000)-ACT-GGT-CAC-GTA-GCA-TCG-ATC-GAT-CGT-ACG-TAC-GTA-CGT-ACT-AGC-TAC-CTG
hashs === (000)-465-154-687-132-687-984-548-946-135-768-351-687-451-876-416-779-354

Fichier X = (00G)-ACT-GGT-CAC-GTA-GCA-TCG-ATC-GAT-CGT-ACG-TAC-GTA-CGT-ACT-AGC-TAC-CT(G)
hashs === (546)-465-154-687-132-687-984-548-946-135-768-351-687-451-876-416-779-354

Ainsi meme un décalge initial ne perturberait pas l'ensemble des hashs, les fichiers sont bien identiques à 99%.
Et le fichier X ainsi découpé peut servir de source pour reconstituer le fichier Z.


Bref, avant de calculer les hash, il faut un découpage sémantique le plus fin possible, ex :
on calcul le hash d'une image et on demande aux autres peers qui possede cette image, dans quelque fichier qu'elle soit.


C'est p-e ca l'inovation d'intel ?
Edit : ok rien a voir..
[message édité par godvicien le 14/04/2007 à 17:15 ]
Inscrit le 15/05/2003
240 messages publiés
En fait si j'ai bien compris, l'encodage, les headers ou je ne sais koi, on s'en tape. Ce n'est que des bits aussi.
Imaginez que l'on veuille reconstituer une banane () en piquant des atomes (ou molécules puisque dans notre cas ce n'est pas piquer un bit par ci et un bit par là mais bien un petit paquet de bits) par-ci et par-là (je veux dire de tel objet ou tel matière .. enfin bref je me fais comprendre) et qui seraient identiques pour reconstituer la banane originelle. Au final si l'on a bien piquer les bonnes molécules, on devrait se retrouver avec le même hash que la banane originelle. Puisque l'on aurait aussi piquer des molécules afin de reconstituer l'header. L'encodage une fois de plus n'a rien à voir. Ce n'est qu'une série de bit disposée/composée de telle sorte que cela correspond à tel encodage (bon là je sais pas si je me suis fais comprendre mais disons que l'encodage ça n'a rien à avoir avec une structure "physique", ou bien une série de bit le mettant en valeur, en fait c'est juste précisé dans l'headers et puis si la série de bits est bien reconstituée, le décodeur arrivera à reconnaitre l'encodage et le décoder ...).

Je suis dans le faux ou y a du vrai ?

Après lecture du thread sur emule-project on se rend bien compte que cela n'aura que très peu d'impact sur le temps de téléchargement au bout du compte. C'est typiquement lié au leeching pur et dur et au leech inutile (dl inutile d'un film qu'on ne regardera jamais etc etc) je veux dire par là du download gourmand et qu'on pourrait se passer et qu'on se passerait en passant par des systèmes plus règlementer tel que sur des trackers bitto privé. Par contre personne n'y a pensé mais si cette technique fonctionne, n'aurait-elle pas un impact très positif sur les dl des fichiers rares ???? Qui dit plus de possibilités de sources, veut dire meilleur dl sur les fichiers rares et ça c'est justement le gros problème d'emule !! Parce qu'en général les fichiers bien partagés sont aussi mis plus souvent souvent en priorité d'upload chez les clients de ce fait ils sont toujours plus partagés (jusqu'à un certain point bien sûr) et les fichiers rares sont plus souvent mis de côtés puisqu'il y a moins de dl. Certes y a des options de push rare files mais bon ce n'est qu'une aide et non l'aide ultime ...

Da Cryptum
[message édité par Cryptum le 14/04/2007 à 02:04 ]
Inscrit le 29/01/2005
428 messages publiés
alors d'abord, pour ta première partie, c'est faux dans ce cas, on n'est pas à l'échelle de l'atome, mais à l'échelle de macromolécules (qq kos), donc un encodage différent, sur qq kos, change toute la donne.
Recompiler alors devient impossible.

Ensuite, pour ta deuxième partie, je ne vois pas en quoi les fichiers rares seraient avantagés car comme je l'ai dit, il faut un fichier source identique à la base. Et même si il y avait un gain, les fichiers populaires en profiteraient tout autant.
Quant aux priorités de partage dans eMule, ce que tu dis n'est pas représentatif de toutes les mules. La grande majorité ne touche pas aux priorités souvent parce qu'ils ne savent même pas que c'est possible. La priorité [Auto] ajuste donc bien les priorités selon la popularité. Ca c'est la théorie. Dans la pratique, c'est pour moi l'un des points noirs d'eMule, même avec des priorités basses sur les fichiers populaires, leur nombre de demandes étouffe complètement les priorités sur les fichiers rares.
Et c'est là qu'interviennent les mods et les fonctions de powershare et autres
Inscrit le 14/12/2005
21 messages publiés
Une autre téchnique pourrait être d'essayer de recomposer les fichiers à partir de chunk locaux.
C'est un peu l'idée que j'avais essayer d'avancer ici (enfin moi ca restait trés trés théorique).
A un niveau plus elevé, quand on telecherge tout une saison d'un série, ne pourrait on pas télécharger le générique une seule fois vu que celui ci est identitque pour chaque épisode?
Inscrit le 29/01/2005
428 messages publiés
C'est p-e ca l'inovation d'intel ?


je n'ai rien lu en ce sens. Voici un article plus technique en anglais si tu veux vérifier

quand on telecherge tout une saison d'un série, ne pourrait on pas télécharger le générique une seule fois vu que celui ci est identitque pour chaque épisode?


à la seule condition que le début du fichier se fasse au même moment, à la frame près. Et là j'ai des doutes.
C'est bien ce que Godvicien a détaillé.
[message édité par DarkVanneur le 14/04/2007 à 17:04 ]
Inscrit le 03/02/2005
963 messages publiés
Exact ! Ca parait évident, il faut commencer par interroger son propre Disque avant de demander au voisins...

Le probleme que souleve Darkvanneur, c'est qu'il n'y a aucune logique dans le découpage d'un fichier en sous partie : on découpe par nb de bits. donc le moindre décalage rend caduque toute la suite...

Donc d'un épisode à l'autre le codage en bits du générique peut être décaler, et la mule ne le reconnait pas, et donc demande aux voisins leur version du générique...
Inscrit le 15/05/2003
240 messages publiés
Ok DarkVanneur

De toute manière pour le générique cela ne pourrait fonctionner puisque chaque générique est différent d'un épisode à un autre. Eh oui le bitrate n'est pas le même d'un ép à un autre donc le générique est différent à chaque fois.

Da Cryptum
Inscrit le 14/12/2005
21 messages publiés
Pour les génériques je ne vois pas pourquoi les bitrates ne seraient pas les mêmes si ils sont encodés par les mêmes personnes et avec les mêmes outils et de facon automatisé, il devrait être possible d'avoir de fortes similarités.
De plus, si la similarité existe au niveau applicatif, la reproduire au niveau binair ne semble pas inconsevable, je ne sais pas comment marche exactement le format divx, mais en mpeg, il suffirait de reprendre le générique de l'episode précédent et d'inclure une trame I (enfin je crois) au moment ou les images différent. Je ne dis pas que cela serait simple, notamment pour définire comment deux images différent et cela serait sans doute couteux en ressources, mais il ne me parait pas impossible qu'intel sorte des outils pour augmenter la similarité des fichiers lors de la compression, quitte a sortir des proc optimiser pour aprés.
Inscrit le 15/05/2003
240 messages publiés
Mais d'un générique à un autre, tout diffère à peu de chose près ! L'un contiendra du macroblocking à tel endroit, l'autre aura plus de bitrate ici et là alors que l'autre le contraire. Ceci est logique puisque chaque encodage d'ép, son bitrate étant VARIABLE vu que la DURÉE de l'épisode n'est PAS la même. En fait il faudrait encoder le générique séparément pour avoir ensuite de fortes similitudes. Mais bon c'est une solution pénible ..

Da Cryptum
Inscrit le 03/02/2005
963 messages publiés
En effet, pour le générique il ne semble pas possible d'avoir exactement deux fois le même encodage au bit près !
D'allieurs avec des systemes qui convertissent de 30 (usa) à 25 images/sec (france), je ne suis même pas sur que le générique soit exactement identique d'un épisode à l'autre.

La seule solution est un découpage non pas binaire, mais bel et bien sémantique, et donc avec un tag qui indique que l'on doit reprendre le générique officel tel quel.
On aurait alors un seul "fichier" spécifique au générique officiel de la série; les tags des épisodes référencant directement celui ci. Ainsi même notre propre collection locale ferait l'économie de plusieurs Mo concernant les génériques de chaques épisode compactés en un seul fichier.

Je ne pense pas qu'il y ait d'autre solution...
Inscrit le 03/06/2003
32 messages publiés
Les teams coupent les génériques sur leurs rips TV ...
Répondre

Tous les champs doivent être remplis.

OU

Tous les champs doivent être remplis.

FORUMS DE NUMERAMA
Poser une question / Créer un sujet
vous pouvez aussi répondre ;-)
Numerama sur les réseaux sociaux