Software Magpie

My latest squeeze

2011-07-16T04:54:00.000-07:00

My last audio CD player failed, and my CDs were taking up too much space. I decided finally to go properly digital with my music. I was anxious to control the software, at least to some extent, and to ensure I could use a good range of formats, not just MP3.

I built a mini-ATX box to run Vortexbox, to provide my digital jukebox. Vortexbox is based on a Fedora Linux distribution, preconfigured on installation to act immediately as a jukebox, without having to mess with it further. Being Linux-based, and with source available, should allow arbitrary tinkering.

To feed my Quad 34/306 hi-fi system, I decided to try the Logitech Squeezebox Touch. Until all the bits arrived for the Vortexbox, I have been playing BBC Radio 3 on Internet radio, which works well, even though the Squeezebox is currently using a WiFi connection. (I'm just setting up the Vortexbox now.)

I was pleased to find that I can ssh in to the Touch. On doing so for the first time, I read:

root@squeeze1's password:

This network device is for authorized use only. Unauthorized or improper use
of this system may result in you hearing very bad music. If you do not consent
to these terms, LOG OFF IMMEDIATELY.

Ha, only joking. Now you have logged in feel free to change your root password
using the 'passwd' command. You can safely modify any of the files on this
system. A factory reset (press and hold add on power on) will remove all your
modifications and revert to the installed firmware.

Enjoy!

I found that mildly amusing, but it also emphasises a big change in attitude for consumer devices: this one is clearly my device, and I can change it as I like, not just in trivial ways.

Networking and interprocess communication

2009-10-08T05:49:00.000-07:00

Last year I implemented a unicast subset of XTP as a plausible attempt at a new transport-level protocol for use on Blue Gene. XTP has some of the flavour of the Universal Receiver Protocol: an XTP transmitter can cause the same receiver to execute different protocols (eg, datagram, reliable datagram, transaction, or stream) by sending different sets of orthogonal options. Unfortunately, although XTP is simpler and more flexible than TCP/IP it still seemed over-complicated. In particular, it has elaborate state transitions to end a conversation. There are other ambiguities in the specification. An INRIA report on a formal specification of XTP (mechanically verified) was helpful in resolving various problems I noticed when doing my implementation, or validating solutions that I developed independently.

In November, I read the book Patterns in Network Architecture: A Return to Fundamentals, by John Day (ISBN-13: 978-0-13-225242-3). The book packs a lot of material into its 400 pages, with many interesting observations along the way. Several simple points are relevant here. Day reviews the history of protocol development and analyses the components of various protocols. He observes that there might be only three types of protocols:

relaying protocols, including multiplexing protocols
error- and flow-control protocols ("error control" protocols)
application protocols

In Chapter 6 (Divining Layers) Day considers why and how one might structure network protocols, and in particular, the purpose of layers of protocols. He therefore designs a basic internet protocol in stages. He concludes, as Metcalfe observed in 1972, that "networking is interprocess communication", but refines the observation: "networking is distributed IPC and only IPC" (ie, the resulting protocol suite exists only to permit communication between (or amongst) application processes), and "a layer is a distributed IPC facility". Subsequent chapters provide a detailed and more formal construction of a complete new network architecture with those observations in mind. The architecture uses IPC protocols recursively in a way reminiscent of Cheriton's VMTP.

The relationship between networking and IPC is I suppose fairly obvious, yet easily forgotten. Many protocols quickly form arbitrary stacks, layered elaborately but pointlessly, like pyramids of acrobats. The essential exchange of data between applications is almost an afterthought. By contrast, specialised protocols such as IBM's one-sided communication protocol on Blue Gene can indeed support specific IPC schemes, such as ARMCI. (In earlier posts, I dubbed that protocol "Clint": the protocol with no name.) With care, such a protocol can support several compatible IPC regimes efficiently, as Clint does for both ARMCI and MPI.

XTP was designed to support a bigger range of IPC options than we need for Plan 9 in this environment. We should do something more specific, and simpler. Unfortunately, Clint is not adequate because one fundamental IPC in Plan 9 is the 9P file serving protocol, which is conversation oriented.

no warranty of merchantability

2008-05-02T12:00:00.000-07:00

In Press On, mentioned below, Thimbleby notes that most software, even commercial software, comes with essentially no warranty or guarantee. ("There is no warranty of merchantability nor of fitness for a particular purpose.")

He compares that to the guarantee for Cross pen s, which I reproduce below:

Cross Writing Instruments Full Perpetual Warranty Guarantee

All Cross writing instruments and desk set penholder mechanisms are unquestionably guaranteed against mechanical failure, regardless of age.

Any Cross product or part requiring service under this warranty will be repaired or replaced at no charge when received at our factory from the consumer (postage and insurance are the responsibility of the consumer, and shipping and handling fees may apply). Any such product that is no longer in production and cannot be repaired will be replaced by a comparable Cross product. Leads, erasers and ink refills exhausted in the course of normal use, and emblems and other customized decorations, are excluded from this warranty; also excluded are fountain pen nibs and other parts damaged from impact, unreasonable use or obvious abuse. The Cross guarantee extends our assurance of a lifetime of writing pleasure to every owner of a Cross writing instrument.

This warranty gives you the specific legal rights, and you may have other rights which vary from state to state or jurisdiction to jurisdiction.

I see there is no mention of "beta". How close can we get to this ideal, for non-trivial programs and systems?

By the way, they are also excellent pens. I ought to have insured mine against theft.

Bottled it

2008-04-30T16:26:00.000-07:00

Shopping yesterday, I compared prices of bottled water at my local Sainsbury's (a supermarket chain in the United Kingdom). The Highland Spring was exceptionally troublesome. I took a snapshot with my mobile phone. I wonder what the shelf-fillers made of it.

Note: the suffix p is "pence" (plural of penny)

Reading List

2008-04-27T09:58:00.000-07:00

Here are a few things I've read recently, apart from papers and reports:

Press On: principles of interaction programming, by Harold Thimbleby: (devices often have frustrating user interfaces, but we can apply intelligent computer science informed by context to get much better ones, and he provides some programs to do it; although the book is not as beautiful as one of Edward Tufte's, there is a similar intellectual range and excitement, including relevant historical analogies, and the importance of context to any design)
Chris Okasaki's Publications (data structures and algorithms for functional programming languages)
Software Engineering for Internet Applications, which is online, although I bought the paperback (only 2006, and the technology is already outdated, but the book is still worthwhile for its extensive design discussions and revelations about the worrying low-level stuff underpinning web applications, and of course the technology is still in use)
Beyond the Desktop Metaphor (as it suggests, looking for alternatives to the over-present desktop, but I didn't find it had much fizz, compared to Press On, and although there were a few ideas worth applying, I thought most of the results were dull compared say to just using Acme or an iPhone)

A Fistful of Protocols

2008-04-06T09:12:00.001-07:00

With my able assistants, clever Google and slightly less reliable Memory (with a "y"), I considered existing protocols designed for high-speed, highly-reliable networks, including URP (indirectly), NETBLT, LNTP, VMTP, SNR, and XTP, roughly in that order; and read previous reviews of them. I also looked at Plan 9's early Nonet and later IL/IP protocols, RFC1077, SCP, SCMP, and a few "one-sided communication" protocols. (I haven't got a specification for Nonet but most of the code is online.) The MPI specification defines a programming interface not a protocol, and so is not directly useful but there are papers about using one-sided protocols for MPI implementation.

Most of these protocols were designed to include high-speed wide-area internets, except Nonet and IBM's one-sided protocol with no name, which I shall call Clint. Clint was designed specifically for the Blue Gene environment. As noted earlier, that environment does not eliminate failures such as loss or data corruption, but greatly reduces their likelihood. For instance, the network is local area only, will not impose arbitrary delays on packets, and will not drop packets because some intervening node is suddenly congested (as might happen on the Internet). It might make a mistake, but rarely. That should allow us to make a few simplifying assumptions, but our project's requirements for fault-tolerance still require us to account for uncommon errors.

The Clint paper shows that per-packet header overhead matters, because the payload is small: 248 bytes on the Torus, after allowing for an 8-byte header read by the hardware. The hardware likes data on 16-byte boundaries, so an extra 8-byte sofware header fits well. That is too small for a complete message context, so Clint transmits a larger header containing a full context in every initial message until the first response from the receiver provides its own unique identifier for that context, reducing the header to the near minimal 8 bytes in all subsequent messages. The scheme saves the latency of a round trip to establish that context first, and avoids wasting bandwidth on big headers in all packets.

What do we need from our transport protocol? We certainly need virtual circuits for 9P connections, and reliable messaging for MPI-like things. Of the existing protocols, XTP looked the most promising: it offers fast setup of contexts for message sending, including context key exchange (with a similar effect to Clint). It follows URP in making the receiver reactive, which allows it to support both datagrams and connections in the same structure by having a transmitter drive the receiver appropriately. The receiver state is transmitted only on demand, and promptly, removing the need for most timers at the receiver.

I am currently implementing a simplified variant of XTP, with a nod or two to Nonet. The packet formats are different, with a view towards a more subtle implementation along x-kernel lines. Some aspects of XTP are replaced by other mechanisms. I think rate-based control is better done at the application level, for instance, and we might do something a little different for multicast, given the special forms of multicast supported by the Tree and Torus. Timers can be rather sloppy and statically-defined, because errors will typically arise only because a node crashes or hangs, or someone is careless with the wire cutters. Out-of-order delivery will occur on the Torus and must not cause needless retransmissions, but how many packet frames might elapse before an obviously missing packet is declared lost? Apart from that, the reliability of the networks allows an early driver to assume error-free networks, with later support for retransmission and other error recovery.

Protocols and Plan 9 on Blue Gene

2008-04-05T02:07:00.000-07:00

A small group of us is developing new small-scale systems software for large-scale supercomputers, such as the IBM Blue Gene series, based on the distributed operating system Plan 9 from Bell Labs.

Blue Gene has groups of up to 64 CPU nodes, each with several processors, connected to the outside world through an IO node per group. The network provision is unusual (although that itself is not unusual in the supercomputer world). Only the IO node has a conventional Ethernet. The CPU nodes are typically connected in a 2D or 3D structure by a special Torus network. CPU nodes within each group are connected to each other and to the IO node for the group by a "class routed" network, commonly called the Tree, although routing tables can create other topologies.

The Ethernet is nothing special and we simply use the existing Internet protocols. Just to get started, we also run IP over the Tree and the Torus, with small MTUs. Given Plan 9's straightforward Medium structure in its Internet stack, it was short work to add Tree and Torus medium drivers. A kernel process reads the raw device (/dev/torus or /dev/vc0), strips the medium header, and passes the resulting Block up the stack; in the other direction, the medium driver adds the tree or torus driver's header to an IP packet and writes it to the device. A few lines of shell script configure the new media into the IP subsystem.

Historically, attempts to provide improved replacements for TCP have failed, partly because new protocols are hard to deploy, and partly because some suggested improvements have simply been added as extensions to TCP or its implementations. Even so, the Tree and the Torus have properties that make it attractive to consider other transport protocols. Both networks have small payloads per packet (240 or 256 bytes), high speed, high reliability (low error rate and retransmission in hardware), and automatic flow control. (The Tree delivers packets in order, but the Torus does not.) Each network provides its own form of multicast, different from IP multicast. The Tree can do certain reduction operations in the network (combining results up the tree).

Existing applications commonly use the Message Passing Interface (MPI) to exchange data and control computations. Much of it is supported at the library level, but we can make good use of suitable primitives at the transport level. We also hope to provide an alternative native messaging interface simpler than MPI's. Our system applications will be using Plan 9's 9P protocol extensively to represent and share services and resources. It seems we shall need both connectionless and connection-oriented communication.

The supercomputer environment makes large-scale experiments in protocol design and implementation easier than on a normal LAN or the Internet. For instance, there are hundreds of nodes, but we can readily ensure that all of them are running the same implementation of the same version of the protocol, and we can change the protocol(s) without too much fuss. Being able to inter-operate directly with other systems is not a key requirement (working through a protocol bridge is fine for now).

Despite the hardware flow control at the packet level, we still need flow control in the transport protocol: network access is multiplexed, and producer and consumer rates are not always matched. (Rate control in the protocol can be avoided by applying it at a higher level in the system.) On the other hand, the networks' highly reliable delivery might reduce and simplify error recovery. Unfortunately the error rate is not zero, so we must still allow for them (at some level, for many applications).

For several decades, protocols have been designed and sometimes implemented, to suit high-speed, highly-reliable networks. Perhaps something suitable exists, off-the-peg, or even off-the-wall. In the next post, I shall mention a few of them and sketch what I am currently implementing.