Category Archives: sugar

The Diamond Age

In Sugar/OLPC circles, Neal Stephenson’s The Diamond Age is a major touchstone, to the point that I thought I knew most of the plot before I even started, just by diffusion … and maybe I did, but a half-overheard story is a funny thing. The pieces you hear may be a coherent story in their own right, without being quite the same as the one on the page.

From references around OLPC, especially in the context of the eponymous Nell project, I imagined the book as a story about one girl who, like thousands of others, cannot afford tuition at a proper school, and so instead receives a tablet (the Primer) with a whole lot of artificial intelligence and a gigantic educational Choose Your Own Adventure story. The story is designed to teach each student how to become a creative, resourceful, self-reliant woman. The story spans elementary school to university, and teaches all subjects you might need: literacy, nutrition, history, self-defense, politics, engineering, and more. From this angle, the story sounds very much like what might happen if you extrapolated OLPC’s path forward a century or two.

What was striking to me, then, is all the story elements that don’t fit this mold, and suggest a vision instructively different from OLPC.

The Primer was not created for the masses. It was commissioned by one billionaire nobleman for his granddaughter, and its wider release was unintentional, though perhaps not unwelcome.

The Primer’s automation is effective only when augmented by a devoted human tutor acting in loco parentis. Students whose tutors are not emotionally invested do not become productive members of society, and those without tutors become nothing more than obedient foot soldiers, the antithesis of creative innovators.

The Primer relies heavily on an always-on internet connection, which it uses in part to pull in new story elements contributed by a huge number of participating adults, who do not even always realize what kind of impact they are having.

EDIT: Oh, and the main character also attends an exclusive boarding school that covers subject matter less suited to digital media.

Of course, the Primer is not the whole story, but sexually transmitted supercomputers and self-assembling skyscrapers seem … less directly relevant to the present day.

It’s Google

I’m normally reticent to talk about the future; most of my posts are in the past tense. But now the plane tickets are purchased, apartment booked, and my room is gradually emptying itself of my furniture and belongings. The point of no return is long past.

A few days after Independence Day, I’ll be flying to Mountain View for a week at the Googleplex, and from there to Seattle (or Kirkland), to start work as a software engineer on Google’s WebRTC team, within the larger Chromium development effort. The exact project I’ll be working on initially isn’t yet decided, but a few very exciting ideas have floated by since I was offered the position in March.

Last summer I told a friend that I had no idea where I would be in a year’s time, and when I listed places I might be — Boston, Madrid, San Francisco, Schenectady — Seattle wasn’t even on the list. It still wasn’t in March, when I was offered this position in the Cambridge (MA) office. It was an unfortunate coincidence that the team I’d planned to join was relocated to Seattle shortly after I’d accepted the offer.

My recruiters and managers were helpful and gracious in two key ways. First, they arranged for me to meet with ~5 different leaders in the Cambridge office whose teams I might be able to join instead of moving. Second, they flew me out to Seattle (I’d never been to the city, nor the state, nor any of the states or provinces that it borders) and arranged for meetings with various managers and developers in the Kirkland office, just so I could learn more about the office and the city. I spent the afternoon wandering the city and (with help from a friend of a friend), looking at as many districts as I could squeeze between lunch and sleep.

The visit made all the difference. It made the city real to me … and it seemed like a place that I could live. It also confirmed an impressive pattern: every single Google employee I met, at whichever office, seemed like someone I would be happy to work alongside.

When I returned there were yet more meetings scheduled, but I began to perceive that the move was essentially inevitable. The hiring committee had done their job well, and assigned me to the best fitting position. Everything else was second best at best.

It’s been an up and down experience, with the drudgery of packing and schlepping an unwelcome reminder of the feeling of loss that accompanies leaving history, family, and friends behind. I am learning in the process that, having never really moved, I have no idea how to move.

But there’s also sometimes a sense of joy in it. I am going to be an independent, free adult, in a way that cannot be achieved by even the happiest potted plant.

After signing the same lease on the same student apartment for the seventh time, I worried about getting stuck, in some metaphysical sense, about failure to launch from my too-comfortable cocoon. It was time for a grand adventure.

This is it.

Existence

A message on the OLPC mailing list today said

uno de los primeros impactos sociales del Plan Ceibal fue que aparecieron niños que técnicamente no existían, no tenían cédula de identidad

“One of the primary social impacts of Plan Ceibal [Uruguay's deployment of OLPC XO laptops to all public school children] was that children appeared who technically didn’t exist, because they didn’t have an identity card.”

It appears that you need a card to get a laptop, and for some families this created the first sufficient incentive to enter their children into the government’s national identity system. To me this seems like a good reminder to expect unexpected effects, for good or ill, when attempting bold social interventions.

Barbeque

I went to a barbeque with some OLPC/Sugar folks, and spent most of the evening chatting with the good old boys about the good old days. I learned that one of them designed this album cover for the Talking Heads using specially written editing software. I learned about bit plane graphics and why they make sense. I learned about the methods and dangers of pointer arithmetic on a CPU whose ALU is narrower than its pointer (incrementing a pointer becomes non-atomic!).

Someone told me that a 14-year-old kid wrote a Sugar activity that’s based on a library I wrote, which is basically the highest level of success I could have hoped for.

In short, it was a really nice evening, with more than enough calories to pay for the 12 miles of bicycling today.

Education, Geek to Geek

Monty of Xiph.Org just put out a new video on the fundamentals of digital multimedia, hopefully the first of many. It’s a fun intro for anyone who’d like to know more about the foundations of modern audio/video technology, especially students. I think it’s a good example of how the geeks of the world can and should work to raise new generations of geeks, worldwide.

Board

This evening the Sugar Labs Oversight Board held an open dinner-meeting in Cambridge. After dinner, we went back to 1CC for some more civilized discussion in a quieter venue.

It was supposed to be a contentious meeting, something about trademark policies, but we quickly found a rough consensus, which I’m sure someone will document somewhere. No decisions were made, except about beer.

It was a pleasantly direct and calm event. There were very few of the endless circles to which I’ve become accustomed at these sorts of meetings.

Beauty

This afternoon I took a stroll around Harvard with some friends. I can recommend without reservation Harvard Square on a sunny summer Sunday afternoon and Herrell’s Mudpie flavor.

I spent much of the weekend building a generic monoid-annotated self-balancing binary tree with bidirectional links and stable leaves. I’m not sure why monoid-annotated trees are so little-known, as they are super-useful. I learned about them here, though that author incorrectly refers to them as Finger Trees.

Anyway, they’re pretty cool. Using the monoid for summation over the integers, and an enhanced AA balancing procedure I was able to build a list with O(log(N)) performance for lookup, insertion, deletion, and search.

Beautiful.

EDIT: Turns out WordPress really doesn’t like certain Unicode characters…

To fix the network

(for context, see a review of OLPC’s networking troubles)

A group of OLPC engineers, especially C. Scott Ananian and Michael Stone, were dissatisfied with the the behavior of the current collaboration stack, and decided to start from scratch, laying out a set of “Network principles” from which a new collaboration system could be derived. Their proposal is a bit hard to compare to the Telepathy design, as it is written from a dramatically different perspective.

Telepathy, and in particular Telepathy’s implementation of XMPP, is meant to be a single-source, near-universal solution for all collaboration problems. Telepathy provides identity (as a Jabber ID), buddy lists with presence and status updates, buddy search, text IM, multi-user chat rooms, remote procedure calls (D-Bus Tubes), reliable bytestreams (Stream Tubes), voice over IP, videoconferencing, file transfer, and a growing list of more. All these features are integrated together, so that an application that starts with a text chat between two users can easily initiate a file transfer, or a voice chat, alongside it.

Telepathy is also designed to make the most of even the worst network topologies. Most of this support comes simply from having a central server, which ensures that any user who can see the server can communicate with any other user who can see the server, or any federated server. Telepathy also provides a number of NAT traversal techniques, many originally standardized by Google, for optimizing bandwidth, latency, and server performance, by bypassing the server when possible.

Telepathy is designed for interoperability with other Jabber clients, up to a point. XOs running Sugar can chat over the local network with Macs running iChat, because both support the link-local XMPP specification. With a properly configured server, and a change to the Sugar UI, Sugar users could chat with anyone on jabber.org or even Google Talk. Of course, other Jabber clients don’t provide Sugar’s Activity system, so interoperability is limited to text, voice, video, and files. If non-Sugar applications start using Telepathy’s Tubes system, then compatible Sugar Activities can potentially be written, but at this time virtually all use of Tubes seems to be within Sugar.

Telepathy’s many features make it a tremendously powerful single source. They also make it complicated and confusing. For example, Telepathy supports both multi-server operation (via Federation) and buddy search (via Gadget), but Gadget only acts within a single server, so locating buddies on a different server requires a separate mechanism. Explaining this within a comprehensible user interface seems difficult to me. “Network Principles” describes the opposite approach.

“Network Principles” is so named because it is not a singular software entity. It’s a set of ideas for how networked collaboration should be implemented, drawn up in such a way that very little new software is actually required to implement it. Its tagline could be “use as little software as possible, but no less.”.

In the network principles architecture, (hereafter referred to as NPA), a user is identified by a DNS name. All knowledge about that user comes by communicating over IP with the IP address specified by that DNS name. For example, instead of asking a central jabber server what Activities a user is running, one would simply communicate with some daemon running on that user’s machine. The story is similar for file transfer, video chat, or any other network collaboration use case. The user’s identity, the DNS name, immediately enables you to contact that user directly. The principal motivation for this design is to ensure that all traffic is direct and unicast, to avoid the multicast routing breakdown experienced by Salut on wireless networks. It also permits extremely simple, transparent debugging, using tools like ifconfig and ping.

Of course, this described system only works if there is a DNS server available and all users have mutually routable IP addresses. There are several common scenarios in which the network architecture does not meet this description, and which Telepathy goes to great lengths to support. NPA proposes to support these scenarios instead by slightly changing the network architecture:

  • On serverless, link-local networks, there is (by definition) no DNS server. In NPA, link-local networking would be supported by modifying DNS (e.g. via an NSS plugin) to produce a machine’s link-local IPv6 address by hashing the user’s DNS name. The IPv6 address space is sufficiently large that collisions are unlikely. (Telepathy uses mDNS here, with its problems of inefficiency on wireless networks and unreliable design.)
  • On a LAN with private IP addresses provided by a router, but no need to communicate outside the LAN, NPA users can simply continue to use their link-local addresses via the described hashing scheme. Alternatively, a cooperating router could provide a dynamic DNS server to allow users to adopt DNS names.
  • On a multiple-LAN network with private IP addresses provided by a router, but no need to communicate outside the network, some sort of server is required. The server could be a cooperating router providing a slightly unusual fake-DNS service, or (if efficiency is not critical) it could be an IPv6 tunnel gateway.
  • On a network with private IP addresses connected to the internet via NAT, NPA users wishing to communicate outside the LAN would require a network tunnel, such as an IPv6 tunnel, with a global address at the endpoint. That (unique per-user) endpoint address would then be listed in the user’s DNS record, updated by dynamic DNS. (Telepathy employs the Jabber server itself as a sort of tunnel, with the user’s JID serving as her global identifier. Telepathy also adds some NAT traversal techniques to improve efficiency.)
  • On dynamic public IP addresses, NPA users would simply employ dynamic DNS to keep their name record up to date.

Like Telepathy, the NPA is designed for interoperability, but in a very different sense. Because NPA simply demands that collaborating users be able to route to each other’s IP addresses, they may now communicate with any service whose requirements are the same. Most obviously, users might run web servers, and collaboration could occur over HTTP. Anyone with a web browser could participate, even those running operating systems with no notion of NPA. A user could also run an IRC daemon, a gnutella node, or (notably) a Telepathy-compatible XMPP server. Running such a server would allow collaborative Activities to run as they do now… almost.

NPA trades away two major things to achieve its simplicity. The most obvious is efficiency, at least in certain limits. In Telepathy, a user can send a message to many other users with a single packet. In Salut, this is achieved by link-layer multicast. In Gabble, this is a service provided by the server, which is presumed to have substantially more bandwidth than the clients. The server forwards the message to all the right people, acting as a sort of bandwidth amplifier.

In NPA, there is no distinction between link-local connections and global connections, and so no provision for making use of multicast routing, which (for the foreseeable future) is only available within private networks. Similarly, there is no provision for bandwidth amplifiers. Both of these features could be provided by a particular library layered on top of NPA, but then these features would only be applicable to other applications using this library. Such a layer would, in my view, be approaching a reimplementation of Gabble or Salut.

The value of one-to-many transmission should not be overstated. The problems experienced with multicast routing in wireless networks indicate that falling back to multiple independent unicast transmissions might not be such a great loss after all. Similarly, the value of bandwidth amplification by a server is questionable, especially given the poor observed performance of ejabberd under load. In the oft-mentioned case of a “school server”, the server shares a LAN with the users, and so has essentially no bandwidth advantage.

Another efficiency loss with NPA occurs in the case of users behind NATs. Thanks to NAT hole-punching, it is possible for two Telepathy users behind NATs to communicate with each other directly, using techniques such as STUN. In NPA, it is difficult to imagine a system for NAT traversal, because NAT’ed users see each other only through the public IPs of their tunnel endpoints, which could easily be inconveniently located in the network. (EDIT: Michael Stone notes that a large family of techniques, notably Teredo tunneling, have developed to provide direct NAT traversal for IPv6 tunnels. Such techniques could be employed to avoid triangle routing and achieve behaviors equal to Telepathy’s.) Direct connections of this sort are particularly important for videochat and voip, which are both bandwidth-intensive and demand low latency. The importance should not be overstated: Sugar has done very little in the way of videoconferencing or voip, and Skype often routes calls through relays without complaints from users. Nonetheless, we can imagine that if the users’ IPv6 tunnel endpoint is on the other side of a satellite link, then all local collaboration traffic might be forced over this slow, unreliable, expensive link.

Another significant sacrifice is disconnection resilience. Salut and Gabble enable collaborative sessions to persist even as their membership rotates. The lead user needs not remain for activity to continue. Strictly speaking, this is true for NPA as well, but not for collaboration based on HTTP, IRC, or any other standard server-based protocol. Server-based protocols are almost always designed with the assumption that the server is a long-lived third party, providing a service to the users. Running such a server on a child’s laptop, over an unreliable wireless network, is bound to create disappointment. To support this feature in NPA, an Activity would either have to direct traffic through a reliable third party (reprising the XMPP server in Gabble) or implement a distributed data coherence algorithm (reprising much of Salut’s Clique protocol).

Admittedly, many current Sugar Activities simply fall over if the leader leaves. There may even be some bugs in the Presence Service that make the user interface problematic in these cases. I also admit that this particular feature is a personal interest of mine. Nonetheless, I genuinely feel its an important property, and not one to be given up so easily.

So after this exhaustive (indeed, exhausting) comparison, what are we left with? I cannot foresee jettisoning Salut or Gabble. Both provide important features, and there is not as yet anything resembling an alternative. However, I do think that the “Network Principles” are valuable, particularly as they provide, in some cases, a way out from our current unwinnable fights with wireless networks. We would do well to see where we can integrate these principles into Sugar, without disrupting our present systems.

The first logical step, to me, is to make use of Michael Stone’s remarkable DNS-hash-based NSS module. Salut relies on mDNS to spread presence information, implemented in the Avahi library. I suspect we could modify Avahi to use hashDNS instead of mDNS, resulting in a dramatically reduced number of network broadcasts. Salut’s performance on wifi and mesh might improve significantly; if it did, we would both validate the approach and enjoy a valuable win. This would at least nominally violate the link-local XMPP standard, but the approach is quite elegant, so it could potentially be standardized.

We would also improve our ability to locate problems with finer granularity. On an NPA network, correct functioning can be verified layer by layer. Even if the top layer is unchanged, this can be valuable for diagnosis in the field.

A very brief and extremely selective history of OLPC and collaboration technology, performed entirely from memory

OLPC’s founders wanted to improve education, and in their vision, education requires communication. They envisioned a computer system in which students, and teachers, could easily work together on projects, and share all kinds of documents and media. To describe this vision, they adopted a buzzword: “collaboration”.

Implementing this collaboration required a network. In schools with electricity, that network could be provided by standard wireless networking systems, and in schools with excellent systems support, collaboration could be supported by a server. In schools without electricity, or outside of schools entirely, the laptops would have to talk to each other directly, and so OLPC became perhaps the first adopter of the IEEE 802.11s standard for “mesh networking”, using a chip sourced from Marvell to implement the required behaviors.

Collaboration also requires a software system to perform communication over the network, and for this, OLPC contracted Collabora, a free software development firm working on a then-new project called Telepathy. Telepathy’s original purpose was to provide an abstraction layer over chat services, like AIM, MSN Messenger, or Google Chat, so that a chat client could work without knowing the details of each system. OLPC contracted Collabora to extend Telepathy’s XMPP (i.e. Jabber) support to arbitrary data channels, not just human-readable text. They called these channels “Tubes”.

Both Marvell’s mesh system and Collabora’s Telepathy software took years to debug. Debugging was especially hindered by the NDAs surrounding the firmware on Marvell’s chip, which prevented volunteer experts from fixing problems or adding features. (Such NDAs have become deeply ingrained in the culture of wireless device manufacturers, not least due to concerns about liability for FCC compliance violations.) Telepathy too proved difficult for outsiders to improve, due in part to its use of specialized technologies like XMPP, and a large, intricate codebase.

When both systems seemed to be approaching a degree of reliability independently, testing began on using them together. OLPC’s engineers quickly discovered that the combined system was extremely fragile, even in somewhat idealized tests. In particular, two major problems were discovered. The first was that Telepathy’s serverless communications component, known as Salut, could not be used simultaneously by more than roughly a dozen users in a room. With more users than this, typical collaborative applications would begin to fail.

After a great deal of discussion and testing by expert engineers, a rough consensus was reached, that the failure to support more users could be attributed to the behavior of multicast routing. Salut was written with a reliance on efficient routing of multicast packets, and makes deliberate use of multicast given this assumption. Marvell’s mesh routing algorithms did not provide efficient multicast routing for a large number of nearby users. (More efficient routing algorithms have been the subject of numerous research papers in recent years, but have not yet reached broad implementation.)

With Salut’s high volume of multicast traffic being routed inefficiently, a small number of users could quickly saturate the available wireless network bandwidth. Performance improved if a wireless access point was provided, but most wireless access points use the inefficient “basic rate” for all broadcast and multicast transmissions, which results in a similar saturation of bandwidth, typically seen at around 20 participating users. Salut did appear to work well on wired 100Mb ethernet, where broadcast is highly efficient and there is a great excess of bandwidth, but this use case was of little interest for OLPC, since its hardware did not have an ethernet port, and its schools could not afford to install the wiring.

A second problem was observed when a server was used to enhance collaboration. When communicating via a server, Salut and multicast are not used, and so network problems are substantially alleviated. However, the only server software recommended by Collabora, ejabberd, proved to have substantial scaling problems of its own. In testing, ejabberd had a tendency to crash when supporting more than about 100 simultaneous users, as might be common in even a small school. While several potential issues were identified and resolved, testing has proven difficult, and recent tests have run into server instabilities again. Debugging is made difficult both by the need to have several hundred active clients, and by ejabberd’s unusual internal structure (it is written in Erlang).

Telepathy also suffered from its immaturity. The developers implemented necessary features as fast as possible, and as such they were often not implemented in the most efficient way. For example, in many cases, Telepathy would take compact binary data, expand it using base64 so that it was valid plain text, and then send that text over a zlib-compressed channel, spending a great deal of CPU time in the process. Telepathy’s network transports have since been made much more efficient in many respects, but not until after OLPC began sending laptops to customers. Much efficiency work still remains.

The final problem that I will mention here is opacity. Telepathy is an abstraction layer; its goal is to hide things from the developer. This can make it difficult to determine what went wrong when things are not working. This is especially true due to the way that Sugar uses Telepathy. Sugar carefully hides all mention of IP addresses, XMPP identifiers, and all other technical matters, behind an extremely simple non-textual user interface, designed to be used by children who do not yet read well.

Sugar still uses Telepathy for collaboration, and its deep integration into every collaborative Activity makes it unlikely to ever be otherwise. However, frustrated with the various issues with the Telepathy stack, some OLPC engineers began searching for a better architecture for networked collaboration. I’ll discuss their proposals in my next post.

Worthwhile

I sometimes wonder if I am doing the right thing by spending time on projects for OLPC and Sugar Labs. I do my best to work on it only during free time, but then, some graduate students spend their whole life in lab, and simply don’t have free time. What keeps me involved, apart from the social ties, are writeups like this one, from Stephanie Selvick of the OLPC Senegal student team.

In the first session, I was paired up with a male teacher who was nervous about communication. He asked if I spoke French, and I apologized that I did not. He then continued to have entire conversations with me in English. He began by saying he didn’t think the teachers would use the computers in their classroom. This particular school received their XO’s 6 months ago, received their first teacher training about 2 months ago, and will be introducing the students to the computers for the first time on Monday. … After that, my partner began by pointing to each individual activity and asking how each could be implemented into his curriculum. Although I scoff at the ideology that “curriculum” is somehow not important, I began to understand the dilemma. I said we should begin by opening one activity and we can answer those questions about curriculum after.

Distance was his gem! The distance activity measures the distance between two XO computers. It sends sound waves between them and a measurement in meters pops onto the screen. He loved it. He began brainstorming assignments for his kids to measure the distance around their homes or rooms and said they could also figure out area from those numbers. Although it took us the full 90 minutes for him to be comfortable with opening the program and inviting another XO to share the program, his enthusiasm was quite the relief. When each person shared what they learned from the first session, it was great to see his enthusiasm about distance in other teams about other activities. The goal of making teachers the experts for each other felt underway.