Tag Archives: Online

Distributed Computing so far

I gave a half-hour presentation on my research at the admitted students weekend earlier.  I think I was able to convey some sense of the opportunities that Mudd offers for research, and presented a reasonable face of what it could look like.

The talk was an explanation of the concepts behind distributed hash tables, and an introduction to the work I’ve been doing with bitTorrent.

These are the slides I used: Admitted Students presentation

Experimenting with 802.11s

The purpose of this document is an explanation of what is defined in the IEEE 802.11s standard, and the states of current implementations based on this standard. 802.11s is the standardization of mesh networking. That is to say that it defines a protocol for mobile devices where they can communicate amongst themselves even when not directly connected, and can route data beyond their immediate environment.
This work has been ongoing for close to a decade, and has been progressing as a single proposal for the last four. The standard is for a complete system, explaining the MAC level standard that data will be transferred. This includes how clients can securely create connections, and how and when they should resend packets they receive which are meant for other devices in the mesh. As a result, this standard has become effectively all encompassing, as it defines standards from the hardware signal levels all the way up to complex software routing and security.
Even today, the standard is not formalized, meaning that nothing is focalized, and implementers are really very cautious to begin implementing mesh networking, because it may change and they would then have to re-write or design their implementation (it means specifically that wireless cards are not being built with mesh networking in mind, since chip design is more expensive and less changeable then software drivers.) The lowest level changes are made to the wireless frames in order to allow hops within the mesh, and would benefit from hardware changes to make those changes quickly implemented, however they will still work even when those changes are processed entirely in software, which is the current choice implementations are making until the standard is formalized.
Routing can be specified either explicitly, as the tree that the source is aware of that will extend to the root (or final destination in the mesh) or ad-hoc, where intermediate nodes make their own decisions on how to route the packet. However, routing is done using a QOS-esque process, where the route is first established, and subsequent packets can use the same path until it needs to be recalculated due to topological changes. In addition there is a periodic discussion about which node in the mesh should act as a root, and the ordering of nodes, which is based upon which node has wired access to other networks, and tie-broken by the MAC addresses. Beyond this there are different levels of structure that these networks can take on, similar to the differences we see today in ad-hoc networks and networks with access-points. These are called meshes with and without registration. Without registration, any node can come and go, and the rest of the mesh is unaware of any topology beyond that directly adjacent to it. In registration mode, the root is aware of the entire tomography of the network, and can make informed choices about how routes should be created.
While the major protocol specification seems to not be changing much at the present, there is still enough flux in details that implementations are not compatible with each other, and are still very rudimentary. I looked at three different implementations, none of which are inter-compatible, and all claim to be based off of the standard.
The first is the implementation of mesh networks used in the OLPC. This was one of the first implementations of mesh networking, and is not compatible with any widely used implementation outside of those devices. It works in OLPC clusters, and is a technical feat, although since the central points that were intended to ground the mesh networks have not yet materialized, it is quite underutilized as I understand it. Instead, in the situations where OLPCs have been deployed, a standard 802.11b network typically works well since all of the machines are close enough to the central access point.
The second is the open 802.11s project, which is designing a software driver for the Linux kernel. This version works currently for a limited set of wireless cards, whose Linux drivers are sufficiently open to allow the needed modifications. It is not included as part of the standard kernel distribution, which is a fairly powerful comment on the state of it’s development, since the kernel is typically thought of as including everything and the kitchen sink. It is simply the reference implementation being created as part of the development of the standard.
The third implementation is available in the latest version of FreeBSD. This version is included in the distribution, and notes that it does not work with the Linux version due to how primitive they are. I was unable to test this implementation as I was hoping to, because the emulated lab I was using didn’t allow the permissions that the code wanted to make to the wireless drivers. However, this code promises to be one of the most practical current versions of mesh networking. Setup is performed through the standard ifconfig linux tool. Where one specifies the access point in other protocols, here they specify the mesh they wish to use, and the parameters associated with it. Once the mesh is specified, routes are automatically formed, and users can manually specify nodes they wish to block or favor using included implementations.
I think the important takeaway from this exploration is into the state of mesh networking. I think the IEEE process here has been a hindrance to the development, and that it has trouble keeping up with the technological developments that are going on in this area. Enough new research keeps coming in that the standard needs to be constantly updated to keep from being outdated, and in so doing means that vendors are hesitant to implement inoperable devices, and keeps the whole field from the popularity it needs to really succeed. I think that we have had the opportunity to settle on an imperfect draft of this standard and actually have widespread mesh networking, but due to the fact that it can become useful only if everyone does the same thing, we have been very hesitant to do so.
Hopefully as smart phones continue to evolve we will begin to see mesh networking standardized in those devices, as the potential it envelops becomes increasingly important to our communication. Given the issues we’ve seen in recent years with cell companies growing troubles keeping their access point bandwidth in line with the consumer demand feels unsustainable, and will hopefully result in an increasing desire for truly distributed communication for both better reliability and bandwidth.

on p2p in the browser

The final project I want to accomplish this semester in my distributed computing independent study, is to come up with a way to access p2p capabilities from within the browser. I was originally hoping to do this with JavaScript API that relied behind the scenes on the new flash p2p protocol, rtmfp. The protocol has been around since last spring, but development for it is not exactly optimal. You need to be using flash to make the movie, and you need a proprietary and expensive piece of server software to coordinate data transfers. The protocol itself is still proprietary, meaning that Adobe won’t actually tell you how to make a server that can work with it, or how data is sent across the wire.

They finally have started advertising it at least, and so it will gain some prominence, and eventually the details will come to light, but for now it is unrealistic to attempt to use flash for a general server agnostic service. (http://www.ietf.org/proceedings/10mar/slides/tsvarea-1.pdf)

Instead, my plan is to modify the open source privoxy software and add p2p capabilities at that layer. My eventual goal is to make a communal grease-monkey system, where pages can be modified by the user through pieces of JavaScript, and those scripts can then be shared to friends. With the right level of abstraction, I think that this can produce a very powerful system. Starting next week, I’ll begin reading and hacking privoxy to find out how to integrate new code into that project.