L approche de programmation dynamique est souvent associ e au remplissage d un tableau deux dimensions et l' criture explicite de ce proc d sous forme it rative. Dans un langage fonctionnel comme Haskell, on b n ficie de quelques avantages d expressivit de haut niveau et de lisibilit qu on ne retrouve pas autrement. Dans cet article, je commence par explorer deux exemples triviaux de programmation dynamique. Ensuite, je passe sur un probl me tout aussi accessible, mais dont l ach vement optimal demandera l utilisation d une structure Data.

The Google Summer of Code is now over. It has been a great experience and I m very glad I ve been able to make it. I ve had the pleasure to contribute to a project showing very good promise for the future of communication: Ring. The words privacy and freedom in terms of technologies are being more and more present in the mind of people. All sorts of projects wanting to achieve these goals are coming to life each days like decentralized web networks (ZeroNet for e.g.), blockchain based applications, etc.

Debian I ve had the great opportunity to go to the Debian Conference 2016. I ve been introduced to the debian community and debian developpers ( dd in short :p). I was lucky to meet with great people like the president of the FSF, John Sullivan. You can have a look at my Debian conference report here. If you want to read my debian reports, you can do so by browsing the Google Summer Of Code category on this blog.

What I have done Ring is now in official debian repositories since June 30th. This is a good news for the GNU/Linux community. I m proud to say that I ve been able to contribute to debian by working on OpenDHT and developing new functionalities to reduce network traffic. The goal behind this was to finally optimize the data persistence traffic consumption on the DHT. Github repository: https://github.com/savoirfairelinux/opendht

Queries Issues:

• #43: DHT queries

Pull requests:

• #79: [DHT] Queries: remote values filtering
• 93: dht: return consistent query from local storage
• #106: [dht] rework get timings after queries in master

Value pagination Issues:

• #71: [DHT] value pagination

Pull requests:

• #110: dht: Value pagination using queries
• #113: dht: value pagination fix

Indexation (feat. Nicolas Reynaud) Pull requests:

• #77: pht: fix invalid comparison, inexact match lookup
• #78: [PHT] Key consistency

General maintenance of OpenDHT Issues:

• #72: Packaging issue for Python bindings with CMake: $DESTDIR not honored
• #75: Different libraries built with Autotools and CMake
• #87: OpenDHT does not build on armel
• #92: [DhtScanner] doesn t compile on LLVM 7.0.2
• #99: 0.6.2 filenames in 0.6.3

Pull requests:

• #73: dht: consider IPv4 or IPv6 disconnected on operation done
• #74: [packaging] support python installation with make DESTDIR=$DIR
• #84: [dhtnode] user experience
• #94: dht: make main store a vector>
• #94: autotools: versionning consistent with CMake
• #103: dht: fix sendListen loop bug
• #106: dht: more accurate name for requested nodes count
• #108: dht: unify bootstrapSearch and refill method using node cache

View by commits You can have a look at my work by commits just by clicking this link: https://github.com/savoirfairelinux/opendht/commits/master?author=sim590

What s left to be done

Data persistence The only thing left before achieving the totality of my work is to rigorously test the data persistence behavior to demonstrate the network traffic reduction. To do so we use our benchmark python module. We are able to analyse traffic and produce plots like this one:

Plot: 32 nodes, 1600 values with normal condition test.

This particular plot was drawn before the enhancements. We are confident to improve the results using my work produced during the GSOC.

TCP In the middle of the GSOC, we soon realized that passing from UDP to TCP would ask too much efforts in too short lapse of time. Also, it is not yet clear if we should really do that.

Week 10 & 11 During these two weeks, I ve worked hard on paginating values on the DHT.

Value pagination As explained on my post on data persistence, we ve had network traffic issues. The solution we have found for this is to use the queries (see also this) to filter data on the remote peer we re communicating with. The queries let us select fields of a value instead of fetching whole values. This way, we can fetch values with unique ids. The pagination is the process of first selecting all value ids for a given hash, then making a separate get request packet for each of the values.

This feature makes the DHT more friendly with UDP. In fact, UDP packets can be dropped when of size greater than the UDP MTU. Paginating values will help this as all UDP packets will now contain only one value.

• #71
• #110
• #113

Week 12 I ve been working on making the put request lighter, again using queries. This is a key feature which will make it possible to enable data persistence. In fact, it enables us to send values to a peer only if it doesn t already have the value we re announcing. This will substantially reduce the overall traffic. This feature is still being tested. The last thing I have to do is to demonstrate the reduction of network traffic.

Week 8 This particular week has been tiresome as I did catch a cold ;). I did come back from Cape Town where debconf taking place. My arrival at Montreal was in the middle of the week, so this week is not plenty of news

What I ve done I have synced myself with my coworker Nicolas Reynaud, who s working on building the indexation system over the DHT. We have worked together on critical algorithms: concurrent maintenance of data in the trie (PHT).

Week 9

What I ve done Since my mentor, who s also the main author of OpenDHT, was gone for presenting Ring at the RMLL, I ve been attributed tasks that needed attention quickly. I ve been working on making OpenDHT run properly when compiled with some failing version of Apple s LLVM. I ve had the pleasure of debugging obscure runtime errors that you don t get depending on the compiler you use, but I mean very obscure.

I have released OpenDHT 0.6.2! This release was meant to fix a critical functionality bug that would arise if one of the two routing table (IPv4, IPv6) was empty. This was really critical for Ring to have the 0.6.2 version because it is not rare that a user connects to some router not giving IPv6 address. Finally, I have fixed some minor bugs in my work on the queries.

During week 5 and 6, I have been to the debian conference 2016. It was really interesting meeting with a lot of people all so involved in Debian.

Key signing party Each year, this is a really important tradition: people gather together and exchange GPG public key fingerprint and sign each other s keys. This contributes greatly to the growth of the web of trust.

I did exchange public key fingerprint with others. It was the first opportunity become more connected in the PGP web of trust. I think this is something that needs to make its way to the less technical people so that everyone can benefit from the network privacy features. There is support for some mail clients like Thunderbird, but I think there is still work to do there and mostly there is work to do about the opinion or point of view people have about encryption ; people don t care enough and they don t really know what encryption can do for them (digital signature, trust and privacy).

Ring now part of Debian During the first week at debcamp, Alexandre Viau, an employee at Savoir-Faire Linux and a also a Debian developer (DD for short), has packaged Ring for Debian. Users can now install Ring like so:

$ sudo apt-get install ring

This is an important moment as more people are now going to easily try Ring and potentially contribute to it.

Presentating Ring Alexandre Viau and I have been thinking about presenting Ring at debconf 2016. We finally did it.

I have finally made a version of the queries code that can viably be integrated into the master branch of OpenDHT. I am awaiting my mentor s approval and/or comments.

What s done Queries. The library will provide the additional following functions in its API:

void get(InfoHash id, GetCallbackSimple cb, DoneCallback donecb= , Value::Filter f = Value::AllFilter(), Where w =  )  
void query(const InfoHash& hash, QueryCallback cb, DoneCallback done_cb =  , Query q =  );

The structure Where in the first signature will allow the user to narrow the set of values received through the network those that verify the where statement. The Where actually encapsulates a statement of the following SQL-ish form: SELECT * WHERE <some_field>=<some_field_value>. Also, the DhtRunner::query function will let the user do something similar to what s explained in the last paragraph, but where the returned data is encapsulated in FieldValueIndex structure instead of Value. This structure has a std::map<Value::Field, FieldValue>. You can think of the FieldValueIndex as a subset of fields of a given Value. The Query structure then allows you to create both Select and Where statements .

What s next

• Value pagination. I have begun working on this and I now have a more clear idea of the first step to accomplish. I have to redesign the get operation callbacks calling process by making a callback execution per SearchNode instead of per Search (list of SearchNode). This will let us properly write the value pagination code with node concurrency in mind. This will therefor make sure we don t request a value from a node if it doesn t stores it;
• Optimizing announce operations;

GSOC Comme j ai mentionn dans au article ant rieur, je participe au programme Google Summer Of Code gr ce l organisation Debian qui supervise mes travaux contribuant au logiciel libre Ring.

Deux jours restants Il reste deux jours avant mon d part pour le Cape, en Afrique du sud. C est pour assister l v nement debconf ( Debian conference ), organis par Debian, que je me rends l . Cet v nement est organis chaque ann e et, l ann e prochaine, c est Montr al que a aura lieu !

J ai tr s h te de vivre cette exp rience qui sera sans doute innoubliable. Debian est une organisation pioni re du monde du logiciel libre. Je rencontrerai des gens tr s d vou s et partageant avec moi beaucoup d int r ts pour le logiciel libre et sa philosophie.

L Afrique du sud Ce sera la premi re fois que je prendrai l avion et je ferai une escale Amsterdam, une ville que j aimerais bien visiter un jour. Ahhhh Jacques Brel. Je suis tr s heureux que le continent d Afrique soit la premi re destination me permettant de sortir du continent d Am rique pour la premi re fois. J ai bien h te de vivre l ambiance du Cape.

Les requins Y parrait qu y a des requins au Cape.

I ve been reworking the code for the queries I introduced in the first week.

What s done

• I have worked on value pagination and optimization of accnounce operations;
• Fixed bugs like #72, #73;
• I ve split the Query into Select and Where strcutures. This change was explained here.

What s still work in progress

• Value pagination;
• Optimizing announce operations;

I have been working on writing serializable structure for remote filtering of values on the distributed hash table OpenDHT. This structure is called Query.

What s done The implementation of the base design with other changes have been made. You can see evolution on the matter here; Changes allow to create a Query with a SQL-ish statement like the following

Query q("SELECT * WHERE id=5");

You can then use this query like so

get(hash, getcb, donecb, filter, "SELECT * WHERE id=5");

I verified the working state of the code with the dhtnode. I have also done some tests using our python benchmark scripts.

What s next

• Value pagination;
• Optimization of put operations with query for ids before put, hence avoiding potential useless traffic.

Thoughts The Query is the key part for optimizing my initial work on data persistence on the DHT. It will enhance the DHT on more than one aspects. I have to point out it would not have been possible to do that before our major refactoring we introduced in 0.6.0.

I am part of the group of students working with the Debian organization. You can see my profile on the Debian wiki here.

Improving distributed and secure communication using free software This the title of my project for this summer. It sounds good, but what am I going to really do? Well, since I m a student at Universit du Qu bec Montr al, I have had the opportunity to meet with the company Savoir-Faire Linux in Montreal last year and that s when I found out about their exciting project: Ring.

Ring is one of the few projects which bring communication confidentiality and freedom in the hands of the users.

OpenDHT Ring is divided in multiple components as explained here: https://ring.cx/en/about/technical. The component I work on is called OpenDHT. This is the distributed hash table which enables Ring users to communicate in a decentralized network. I have already been working on this project for a year now, so you won t see me posting reports where I say I have to find my way around in this project. In fact, I have contributed to rewriting a major part of the code for better maintainability. In the begining of last summer, I was able to be part of a research association between Savoir-Faire Linux and Universit du Qu bec Montr al. We have been working on adding two major features to OpenDHT.

Short introduction to Distributed Hash Tables OpenDHT is based on the Kademlia design. If you know about DHTs, you are aware that they define the notion of distance using the XOR metric. This makes the tuple (H_n, xor) a metric space, where H_n is the space of identifier keys of length n. This way, you can find an identifier be the closest to a target hash than the rest of the nodes in the network.

In order to find some data that is associated with some hash h, you have to find the nodes in the network for which the distance between their hash identifier and the target hash h is minimized. The group of nodes which are the closest to the target hash (OpenDHT allows up to 8 nodes) will hold data for that hash.

Data persistence Let s say you ask a group of 8 nodes to hold some data for a hash and you want the data to hold the whole time until its expiration time as come. If the group of 8 nodes change because that for some reason those nodes leave or others just arrive and have an id that is closer to the target hash than the initial group of 8 nodes. The data would then not be found on the new group of 8 nodes. A first and simple solution was to count on the initial creator of the value to periodically announce the value to the group of 8 nodes. However, what if this node leaves? This is one of the main problem that I ve been working on solving since 2015. A first version of this was produced on September 2015. However, we experienced traffic issues and were forced to redesign the OpenDHT network requests engine. We are presently working on adding a Query feature that would enable filtering of data on remote nodes, hence substantially lowering the overall traffic produced by a response to a get request.

Indexation During the last year, I have also been working on the design of a solution for the use case of indexation. In a more technical way, this is the capability to find data by providing a map where its key is a string field and the mapped value is the value associated to that field, much like in a form. This could help find data for which you don t know the hash, but you have specific information about its content. In other words, this would be a search engine for OpenDHT. I have already created a working, but still in progress, version of this. You can find it on http://opendht.net, on the index branch. Now, Nicolas Reynaud (kaldoran) is contributing to this during the GSOC.

Roadmap As I explained on my page on the Debian Wiki, I am going to work on:

1. Developing new functionalities in OpenDHT aiming at reducing overall generated traffic.
2. Maintenance and optimization of the OpenDHT code in general.
3. Optimizing data persistence solution over the distributed hash table.
4. Merge (1) in the Ring daemon component in order to benefit from lower traffic in Ring.
5. Make OpenDHT use TCP protocol instead of UDP. This is going to reduce code complexity and enhance robsutness of the DHT.

For further details, read my reports!