;; -*-mode: Outline; -*- Notes on USENIX 2006. June 1-3, 2006. Copley Place, Boston, MA, USA. There were about 700 attendees -- notably smaller than USENIX 2001, which was also at Copley Place in Boston. There were 194 papers submitted, of which only 24 accepted. Curiously, hardly any of them were of any interest to me. Most of the papers were of the kind `we tinkered with this and this and found 10.4% improvement'. There weren't any insightful ideas. * PlanetLab: Evolution vs. Intelligent Design in Planetary-Scale Infrastructure Larry Peterson, Professor and Chair, Department of Computer Science, Princeton University; Director, PlanetLab Consortium Thursday, June 1, Keynote Address PlanetLab statistics: 670 machines in 35 countries, running about 600 slices. There are 2380 users, moving about 3-4TB of data per day and connecting to about 1M IP addresses outside PlanetLab. PlanetLab is a tradeoff, a good combination of various techniques rather than a single clever technique. PlanetLab is a technical solution to non-technical problems (like letting total strangers run their own code on your computer). Most of the talk was about these non-technical problems: how to convince people to connect their computers to the PlanetLab and let strangers run code. The have a few trade-offs indeed. For example, an owner of the computer has to contribute the minimum of resources. The owner may dedicate additional resources to favorite slices. An application running at a node is guaranteed a fair share of resources; anything beyond that is up to the negotiation with the node's owner. Incidentally, there are no memory limits on application. However, when swap space utilization goes over 90%, the largest user is killed. That proved quite sufficient for applications to watch their memory usage. Incidentally, no user of a node runs as a root. The VM kernel may be a bit modified to permit some services to be run by non-privileged users. They consciously follow the principle of least privilege. The trust model is also interesting: users register with the PlanetLab consortium (PLC) and get tickets. An application uses the ticket to `login' to a node and obtain node's resources. A node owner trusts PLC to exercise care in granting tickets. Contrast with GRID: in PlanetLab, once a remote user got access to a slice, he has his own VM and can install any software he wants. Slices are distributed VMs (across nodes), and the slice user can configure all these VMs as he wishes, installing the same or different software. In GRID, a remote user has no choice: it has to use the software installed at the node. * Deploying a Sensor Network on an Active Volcano Matt Welsh, Harvard University USENIX 2006 Invited talk, June 1, 2006 ``I will describe our experience deploying a wireless sensor network on Reventador, an active volcano in Ecuador, which recorded data on hundreds of eruptions and explosions over a three-week period. Deploying a sensor network in such a hostile and remote environment involves many challenges, including capturing high-quality data on seismic activity, debugging the network over the radio, and slogging through jungles to reach the deployment site.'' http://www.eecs.harvard.edu/~mdw/proj/volcano In particular, the slides of the talk are at http://www.eecs.harvard.edu/~mdw/proj/volcano/reventador-usenix.pdf Incidentally, they used a Zigbee radio (802.15.4) and a mote from Moteiv, Inc. The total cost of a mote: about $75. A radio draws only 20mA current when active and 5 microA when sleeping. Two D-size batteries proved sufficient for the 2-week experiment. For comparison, existing sensors in use by volcanologists require two car batteries (sic!) to operate. One has to carry those batteries through the jungle to the deployment site. Also, one has to visit those sensors every two weeks to swap the flash mini-drive, on which all the data are written. In contrast, the new sensor network offers on-line data acquisition. Data acquisition must be high-fidelity and precisely time-stamped. Their sensors acquire data at 100HZ per (seismic and several acoustic) channel, at 24 bits per channel. That is too much data to transmit, so the sensors accumulate data in a cyclic buffer and do some pre-processing: they detect an event (see the slides) and accumulate data only within a 60-sec window of an event. The accumulated data must be _reliably_ transmitted to the base station. They have designed a light-weight reliable communication protocol. The nodes are about 100 meters apart -- and still must maintain global time with 10 msec accuracy because proper timestamping is critical for data fidelity. The base station was 4 miles away, connected to a mesh via a freewave radio modem, with an intermediate repeater. Interestingly, a few nodes were 200-400 m apart, and still were able to communicate (with a dedicated pole antenna). The mesh network of nodes is self-organizing; one node chose a communication partner 1km away! It is amazing that the radio held up so well. One of the lessons is that the sensor network overall proved more reliable than the base station (a laptop at the hotel). Their base station regularly suffered power outages, because a worker was lazy and kept forgetting to add diesel to a generator in the middle of the night. The network had only one outage: they remotely rebooted nodes -- and they didn't come up. So, a grad student had to hike through the jungle to the volcano and manually reset the nodes (on the second day at the volcano, Ecuador military helped him with a helicopter). They had a few glitches in the drivers at the nodes, and had to fix them in the field (that's the reason they had to reboot the nodes, after uploading a fix). Anyway, the network overall was 90% reliable. OTH, the GUI at laptop, written in Java, regularly suffered various crashes and lock-ups (deadlocks). Lesson: build self-validation early on [and use better languages to program the base station?] It turns out that despite a good timing protocol, there were a few glitches in the timestamps. The protocol worked great in the lab, but not so great in the field. Sometimes (driver error?) a node would get quite an outlandish idea of the global time. They spent about 3-4 _months_ cleaning up the recorded data, identifying systematic time skews and removing them. The cleaned up data seem to show internal consistency and proved consistent with the data recorded by an old sensor, which just happen to be nearby. Somehow it never occurred to them to place an independent sensor right at a node, for the sake of validation and calibration. Anyway, volcanologists believed the data; furthermore, they seem to have discovered a previously unknown underground `action center' at the side of the volcano, far from the main shaft. * Panel: Open Source Software Business Models Moderator: Stephen Walli, Optaros, Inc. Panelists: Mike Olsen, Oracle/Sleepycat; Brian Aker, MySQL; Miguel de Icaza, Novell/Ximian ``The panelists come from a variety of backgrounds and software companies. The one thing they all have in common is that they have used free and open source software in those businesses to great effect. Come find out how the business models worked, how community made a difference, and just what an open source business looks like.'' Miguel: Ximian started with a goal to show that open source can be successful. They started with Evolution: alas, could not make any money off it. The real money maker was, unexpectedly, RedCarpet (a patch/update distribution system) -- which was proprietory, although the client was free. Miguel said that if he were to start a company again, it would be a proprietary software company. I have nothing more to prove, Miguel said. Now I would do it for money. A few aphorisms: even if your company OpenSource, your software must have at least some proprietory component. That sentiment was universally concurred with by all panelists. Incidentally, although Mono is LGPL, all contributors are asked to assign copyright to the Mono project. Another agreed upon aphorism: OpenSource is the best attack, but it is not a strategy, and it is not a business model. The panel come very strongly against patents; they said that software patents don't even make economic sense (takes too long to get, too costly, and it is not clear if the patent will hold up when issued). An interesting summary of Unix wars: it was about taking minicomputer market away from DEC, the incumbent. Unix was a weapon that united DEC competitors, who ganged together and `standardized' on the OS that did not run (at that time) on DEC computers. * Success, Failure, and Alternative Solutions for Network Security Peiter "Mudge" Zatko, BBN Technologies A pompous talk by a pompous person. Incidentally, the talk started ten minutes late: organizers had to scour local bars looking for Mudge. After Mudge eventually turned up, he took another 5 minutes looking through his files for the right document. One would think that a person working in security would not publicly go through the files on his computer... * Panel: Is University Systems Teaching and Research Relevant to Industry? Moderator: Gernot Heiser, NICTA/UNSW Friday, June 2 This panel will discuss the question of whether systems research published in the main conferences is too academic, and whether universities are turning out enough graduates with the right systems skills for industry. It will also look at whether industry could be more supportive of university teachers and researchers. Panelists: Andrew Tanenbaum, Margo Selzer (Harvard), Jim Waldo, A head of OS research at IBM TJ Watson center, a head of OS research at Intel, a similar person from HP. Jim Waldo made an observation about the inversion of focus: academic systems research now is quite short-term (because funding agencies insist on relevance). Some industry research is, in contrast, longer term, because payoff is bigger. An Intel person concurred: Intel currently sponsors longer term OS research; Intel invests in Berkeley and other universities. Intel is not interested in patents in this area, and encourages publications. Intel seeks to strategically influence university research. An IBM person concurred too. He said IBM is doing pure academic OS research with no immediate relevance. He said that academia should, ideally, work on big, _irrelevant_ systems. The system has to be big so only a team could develop it, learning to maintain and communicate in the process. He said that spending 5 or 7 years for a PhD is _good_; IBM certainly has no need for quick PhDs that could only solve micro-problems. The same person lamented that Linux stifled OS research; the main action now is small improvements and copying of the existing research. It took Linux 15 years to support large pages. From the audience: only few good universities produce good students; in most universities CS falls apart. Small colleges teach only `Java and HTML' as programming languages. In the rest, the discussion was an enumeration of existing, well-known problems. As someone noted, the panel went from bad to worse... Incidentally, I have offered a view from the left: they complain how long it takes for the OS research find any application in the industry. I said, look how long it takes for the programming languages research to find an application in OS research. You're still programming in C or in Java. That's disgusting [that's the word I used]. * Permissive Action Links, Nuclear Weapons, and the History of Public Key Cryptography Steven M. Bellovin, Columbia University ``From a security perspective, command and control of nuclear weapons presents a challenge. The security mechanisms are supposed to be so good that they're impossible to bypass. But how do they work? Beyond that, there are reports linking these mechanisms to the early history of public key cryptography. We'll explore the documented history of both fields and speculate on just how permissive action links --- the "combination locks" on nuclear weapons --- actually work.'' Bottom line: we still don't know how PAL really works. It is not certain that NSA has invented public-key cryptography in 1962 (in the NSAM-160 memorandum). It seems more likely NSA has invented digital signature. http://www.cs.columbia.edu/~smb/nsam-160/ Lesson for access control: find the one true mandatory control -- and block it. * Gold and Fool's Gold: Successes, Failures, and Futures in Computer Systems Research Butler Lampson, Microsoft Research People have been inventing new ideas in computer systems for nearly four decades, usually driven by Moore's Law. Many of them have been spectacularly successful: virtual memory, packet networks, objects, relational databases, and graphical user interfaces are a few examples. Other promising ideas have not worked out: capabilities, distributed computing, RISC, and persistent objects. And the fate of some is still in doubt: parallel computing, formal methods, and software reuse. The Web was not invented by computer systems researchers. In the light of all this experience, what will be exciting to work on in the next few years? The presenter listed Capabilities, Functional programming, Distributed programming and Security as the ideas that looked great at the time but didn't work out (or didn't work out yet?). I found it curious the mentioning of security along with Capabilities, FP and distributed programming. Perhaps the reason security hasn't work out in the mainstream industry is because the others didn't work out either? I tried to talked to him about the capabilities, but he didn't seem to care much (by calling Eros, etc. all failures). Well, Wirth too has written an article in IEEE Computer, calling logic programming, functional programming, virtual memory and complex instruction set architectures all failed ideas. I was curious what computer Wirth was using to type his article... * Why Mr. Incredible and Buzz Lightyear Need Better Tools: Pixar and Software Development Greg Brandeau, Vice President of Technology, Pixar Animation Studios Invited talk, Friday, June 2, 2006. Abstract: Movie-making and software are 100% interconnected at Pixar and other studios making computer-generated movies. This talk will discuss how we make movies at Pixar and how our movie-making process drives our software development efforts. We will discuss software requirements, development tools, and systems infrastructure. We will examine where we began and our current needs, as well as looking at the combinatorics that tell us what we will need in the future. We want to hear from you about what you think you can do, as we hope to engage the systems community to help make our vision a reality. Pixar is a relatively small company: 800 employees total, of which there are 75 animators and about 100 software developers. There are, on average, 4 computers per person. Greg Brandeau emphasized many times that Pixar is a _story_ company rather than a software development or computer graphics company. Therefore, all animation software and all stunning visual effects are not the end, but means -- to help the director and the artists to tell the story. Incidentally, this is the reason they develop quite sophisticated animation and computer graphics software: if people and objects in a scene look and behave realistically, then viewers' attention will be on the story rather than on odd behavior or looks. The main purpose of their animation and rendering software is to make the viewer _not_ to pay attention to animation and rendering. Greg Brandeau described in brief their production process, using their latest movie, 'cars', as an example. The production starts when somebody has an idea of a story, tells it to other artists and finally gets a go-ahead. The artists then produce a sketch of the story on index cards, discuss among themselves, and finally come to a computer to build wireframe models of objects and some scenes. The production begins. Incidentally, although they do have some idea of the story, they don't precisely know where it goes. They figure out as the story progresses. The software is developed (or composed from the plug-ins they have already) as they go along. It happens that the artists get stuck: the story just doesn't feel right. The production stops. It may resume later when the artists figure out the story line. New effects may be needed: e.g., the new story line may include an explosion, so software developers need to obtain/develop rendering engine for this effect. This shows that the movie director and the artists rule; computer graphics and animation is to support the artists. This also shows that software development at Pixar must be nimble: requirements change all the time as the story develops. As an illustration, for the movie 'cars' they have rendered total 6 million frames, only 180,000 of which (that is, roughly 1/40) comprise the final version of the movie. For the movie 'cars' they used 300 times more computing power than they did for the `Toy Story'. And yet the production time was roughly the same. Part of the reason was a `human limitation': an animator creates several frames and gets them rendered overnight. Next day, he brings the result to the director for his approval, changes, etc. These discussions are the limiting factor, which cannot be overcome: after all, a movie is created by people for people. The other reason the production time for 'cars' wasn't shorter is because they have tried several new effects: ambient shadows, to make shadows softer; irradiance (the light reflected from a red car makes a white wall appear reddish) and reflectivity. Cars have many shiny surfaces, so the latter was important. They had also developed a `car driving' animation software. An artist would specify only a small number of key poses of the car. The animation software fits a smooth curve, makes sure that car properly turns, that car's wheels properly turn, that the tires behave as inflated objects (deforming when moving over bumps), that the car has a suspension and bounces over bumps. A lot of physics is involved. The goal is to save animator's time and free them from animating 'trivial' (or, mechanizable) things -- so the animator can concentrate on the story. Again, Pixar is a story company. For the movie 'cars' they have to migrate to 64-bit computers. This is because the model of one car takes more than 2GB! And a scene may involve several cars. Therefore, they had to replace all their rendering farm with 64-bit computers, and recompile all their software. Here's the overview of their animation/rendering software: - 325 K lines of C code - 1.7 M lines of C++ code - 7,500 source code files - 24 different subsystems these counts do not include third-party library/system code: Qt, Tcl, Python, Boost, PTMalloc. The main platform: Linux, C++ with Qt. The choice of the language was decided in internal discussions, to keep code relatively portable if they need to migrate in the future. These discussions are still ongoing: which `glue' language to use, how to write a new plug-in, etc. Incidentally, the head of software development (with whom I talked after the presentation) received his education in Edinburgh, and he is well familiar with ML. He does not discount functional languages. How they migrated to Linux: they used to be a SunSolaris/SGI shop. However, the continuing improvement of the Intel platform could not be ignored. One day, a developer bought a Intel box from Dell and spent a week porting some of the animation software to Linux. It kind of worked. As Greg Brandeau says, other people piled into that developer's office, saw the result, cried `Gosh, it almost works! And it costs only $1000 and works faster than an $15,000 SGI computer'. In a short while, everything was moved to Intel/Linux. Each rendered frame is kept in a separate file; a database keeps track of files. Perforce keeps track of textures. They use Perforce again for version control of the code. The main part of the talk was software development problems they have encountered at Pixar -- problems they need (USENIX attendees') help. There are three main problems: - nimble software development - debugging and profiling - performance. Multi-threading is becoming a huge and pressing problem. To make software easier to develop and compose, they rely on plug-ins (for RenderMan) to great extent. Also, they use a lot of glue languages, like Tcl and Python (as well as shell scripts). Debugging and profiling is a big pain. They use Purify for debugging their C/C++ code. Alas, their models are huge and rendering runs for a long time (issues like memory corruption may occur only after a long while). Purify has trouble with very large models; also, Purify significantly slows down rendering, which makes bugs appear after even longer while. GDB has a very steep learning curve, and still doesn't help much in debugging. Profiling is a significant issue; they are basically writing their own specialized tools and insert timing loops in the code. So far, they have been taking great advantage of the CPU speed increase. This is coming to the end: further increases of CPU performance are now in terms of more cores rather than in higher speed. Software has to take advantage of multiple CPU cores. They are experimenting with multi-threading now, and it is _very_ hard. They really need help. Greg Brandeau repeated several times that Pixar is not a software development company. They would have gladly bought profiling, debugging tools or rendering software -- if it were available. Furthermore, they would have gladly payed free software programmers to develop software for them (profiling, debuggers, etc). They don't care if it is free or not, and what the developer wants to do with that software later: sell it or give it away. Greg Brandeau said several times: if you can help us with some of the problems, come talk to us and name your price. Pixar is open-minded; they have no problems with using or contributing to the Open Source (or paying to Open Source developers). They do that already. I personally think they need better languages (where memory corruption is not a problem). They need meta-programming, to assuredly synthesize fast code. Meta-programming can also help with multi-threading. I also think that OCaml or Haskell are better glue languages. * Routing Without Tears, Bridging Without Danger Radia Perlman, Sun Microsystems Laboratories ``Why is route calculation done at both layers 2 and 3 of networking? Is one better? Do we need both? This talk explains the historical accident by which bridging was conceived and the properties that make it attractive, and dangerous, today. The talk discusses new work being done in IETF known as TRILL (TRansparent Interconnection of Lots of Links), which combines the advantages of bridges (layer 2 forwarding devices) and routers (layer 3 forwarding devices).'' A wonderful talk, as ever. http://www.dista.de/netstpint.htm She developed the spanning tree routing algorithm. The development of the algorithm didn't take that long; writing a poem about it did. The end of that link has the Algorhyme: I think that I shall never see A graph as lovely as a tree. A tree which must be sure to span. So packets can reach every LAN. First the root must be selected. By ID, it is elected. Least cost paths from Root are traced. In the tree these paths are placed. A mesh is made by folks like me. Then bridges find a spanning tree. http://www.google.com/search?hl=en&ie=ISO-8859-1&q=Radia+Perlman+Bridging http://edu.ietf.org/download/50/routing-tutorial-ietf63.pdf At USENIX'2006 Radia Perlman revealed the Algorhyme for the TRILL protocol. Google doesn't find it yet. The upshot: the ISO protocol stack did have a few good features. For example, CLNP had a nice property of supporting a campus network. All `subnets' within a campus shared the same prefix and were bridged rather than routed. That means, a node can freely migrate within a campus; bridges needed no IP address and required (aside from setting campus-wide prefix) no configuration whatsoever. Compare with that IP, where each subnet has its own network prefix, routers must be assigned network addressES, and the node migration across the network is difficult to say the least. The TRILL project (RBridge) is an attempt to bring back some of that simplicity -- which IETF partisans just couldn't have ten years ago, because it was coming from their worst enemy, ISO. * An Introduction to Software Radio Eric Blossom, Blossom Research; Coordinator and Maintainer of the GNU Radio Project Invited talk, June 3, 2006. http://www.comsec.com/software-radio.html http://www.gnu.org/software/gnuradio/ The main limiting factor of software radio is analog-to-digital conversion. Software radio became feasible now because A/D converters have become `good enough' (plus CPU became fast enough to be able to process samples in Mbits range, without a dedicated DSP). An example of (non-free) software radio: Sandbridge (www.sandbridgetech.com), a handset that can handle CDMA or GSM cellular communication entirely in software. So, software radios (free or otherwise) are becoming mainstream. FCC considers them `enabling technology'. GNU Radio lets people experiment with (quite advanced RF processing: like CDMA, PSK and other similar modulations -- TV, GPS, and cellular communications) with the minimum of hardware. One can buy a GNU-designed board (a motherboard and two daughterboards -- with high-quality A/Ds and fast downconversion) for less than $1000. That is _all_ hardware one ever needs. An example of a really cool application: passive radar. Use the existing FM and HDTV stations to detect airplanes, by accurately measuring differences in phases of the direct and reflected signals. An FM station acts as an emitter of radiation. A passive radar can not only see a helicopter, but also detect the Doppler shift off the helicopter blades. What is totally amazing is being able to detect Doppler shift of the compressor blades of a jet engine! A passive radar can even see stealth aircrafts. Some big players in the GNU Radio: DARPA ACERT (BBN) (http://www.bbn.com/News_and_Events/Press_Releases/05_12_05.html), Virginia Tech, CMU, Rutger's Winlab. I have briefly talked to Eric Blossom after the talk, and explained the benefits of MetaOCaml over Python as a program generator, in enforcing the correct composition of the radio. He agreed and asked to send him a message. He said that if we want to prove our approach, it's better to start with an FM one or two-channel decoding. The next goal is shift-key modulation (PSK), for a transmitter and receiver connected at least with a coax.