Christopher Peplin

Maximizing USB Bulk Transfer Throughput

2012-02-06T00:00:00-08:00

Ever get so stuck on a problem that web searches only lead back to your own forum post with the original question? This post is hopefully an end to that for some people.

A few months ago, I ran into a performance problem with USB bulk transfers on the chipKIT, an Arduino-compatible PIC32 microcontroller. I posed this question to the chipKIT and Microchip communities:

I'm just getting started with USB programming using the recently released Microchip library on the chipKIT with the network shield. I've tried to learn as much as I can about proper USB programming and it's been good for the most part - however, I'm stuck at a ~75KB/s bulk transfer speed.

At Ford, we created a device for the OpenXC project that spits out discrete messages to a host PC over USB as fast as possible. The current strategy is to use JSON delimited by newlines sent via a bulk transfer endpoint. I trimmed down the GenericUSB example to test the maximum transfer rate of such a device, and created a Python receiver for the host (it uses libusb as the underlying USB library). The benchmarking code is available at GitHub.

On the chipKIT side, the main loop is pretty simple: it continuously writes a 45 byte JSON message to the USB endpoint:

while(true) {
    while(usb.HandleBusy(handleInput));
    handleInput = usb.GenWrite(DATA_ENDPOINT, messageBuffer, messageSize);
}

In Python it's a similar loop that requests a read of some size until it hits 10MB transferred. This is the actual PyUSB read function that gets called:

device.read(self.endpoint, self.message_size)

The original question continues:

If you download the benchmarkUSB.pde sketch to the chipKIT, then run "python receiver.py" it will read 10MB from the device with various "read request" sizes ranging from 64 bytes (one packet) to 1KB.

It's my understanding that requesting more data from the host at a time will increase throughput as messaging overhead drops - for some reason, this isn't the case for my code. You'll see as the request size increases the throughput actually drops from 75KB/s to even lower numbers.

Potential Solutions

The most common answer I found to throughput issues was to increase the amount of data requested by the host. This seems like sound advice, but it just wasn't fixing the problem for me.

Another bit of advice (from Professor Ed Olson at the University of Michigan) was to use asynchronous requests so that multiple USB request blocks (URB) were always in flight. I found this enhancement mentioned elsewhere, and it is in line with the other potential fix - making sure the USB device is always busy sending data.

Unfortunately, switching to asynchronous requests had no effect either - the benchmark still showed abysmal throughput on the order of 50 - 70KB/s.

The Fix

The problem ended up being much simpler and had more to do with one of the core design principles of USB. After shelving this issue for a few months, I revisited the problem and something caught my eye.

No matter how many bytes were requested on the host, from 64 to 4096, the read operation only every returned 45 bytes - one message. USB uses 64 byte packets, and it uses a less than 64 byte packet (traditionally but not limited to a zero length packet) to indicate the end of a transfer. Were we causing a lot of extra overhead by ending every transfer after 45 byets?

I padded out the 45 byte test message I was using to 64 bytes, and now it is much faster (70KB/s from Python to 650+ KB/s). Previously, we requested 1024 bytes but got 45, which is less than a full 64 byte packet so of course, the transfer was closed.

In hindsight this seems like a pretty important thing to know about USB, but being new to driver development, it wasn't obvious and I couldn't find any references to how the less-than-max length packet can effect performance elsewhere.

The complete fix for OpenXC's use case will be to make sure every message is padded out to 64 bytes and to request bulk transfer sizes that are big enough to get good throughput but small enough to not be too delayed. I have yet to confirm, but my understanding is that if we request a 4KB read and don't mark the end of the transfer with a less-than-max length packet, the host device will block waiting for the rest of the requested data.

References

chipKIT Compatible Arduino-based Makefile

2011-12-09T00:00:00-08:00

The Arduino is a great platform for rapid prototyping hardware devices. If you need to squeeze a bit more performance out of your project, I've recently found the Digilent chipKIT a great drop-in replacement board.

The chipKIT is based on the PIC32 microcontroller (as opposed to the Ardunio's Atmel ATmega chips), and thus uses a different toolchain for compiling. The folks at Digilent have kindly released a new version of the Arduino IDE renamed MPIDE which includes the pic32 compilers and other tools.

If you're not wild about GUI IDEs, there are a few Arduino-compatible Makefiles floating around that allow you to build and deploy code from the command line. None of these that I've found have supported the chipKIT until now - I've published on GitHub an extended version of Martin Oldfield's Arduino.mk that works with the tools provided by MPIDE.

The biggest change is allowing the tool names to be overriden - e.g. you need to use pic32-gcc instead of avr-gcc. To use it, follow Martin's instructions but instead of including Arduino.mk at the bottom of your Makefile, just include chipKIT.mk instead.

Thanks for Martin for the well-documented Makefile - this would have taken much longer had it not been so clearly explained.

Source

Download the chipKIT.mk Makefile from GitHub.
Check out Martin Oldfield's original project.

Filesystem Music Collection Sync to Rdio

2011-08-23T00:00:00-07:00

Rdio is pretty neat, but I've been missing out on some of the fun because I can't sync my music collection to my Rdio account. I don't use iTunes or Windows Media Player, so the Rdio Desktop Music Collector doesn't do me much good.

Thankfully, there's a great Rdio API that we can use to manually sync from the filesystem. I put together a command-line Python tool that takes care of the job, or at least it did for me. You can run it multiple times safely, as it keeps track of which albums have already been uploaded.

The tool is available on GitHub at rdiosync - I hope it's helpful for someone else, too.

Command-line Build and Deploy to the BUG

2011-08-04T00:00:00-07:00

I recently started a new job, and we're working with the BUG YT from Bug Labs. The primary language for BUG apps is Java, and they helpfully provide libraries for interacting with all of the available hardware modules as OSGi services.

The recommended development environment is their Dragonfly SDK, an Eclipse plugin. It provides shortcuts for creating new BUG applications with the proper build configuration and ways to deploy to either a physical BUG or a virtual BUG simulator.

Try as I might, I've never been able to have a positive relationship with Eclipse - it boils down to the fact that the least important thing in any workspace view seems to be the code itself. I've paried Eclipse with Eclim so I can code in Vim but take advantage of plugins like Dragonfly, but the complicated setup is dragging my little work laptop down.

Building with Maven

The last few times I had to use Java, I found Maven to be a good command-line alternative to the build features of Eclipse. I've created a Maven archetype and a small deploy script that can replicate some of the important features of the Dragonfly SDK on the command line - no mouse required.

The code for the bug-archetype is available on GitHub, where I've also written up more detailed installation instructions. There's not much to the archetype itself - the trickiest part was finding an existing OSGi bundle archetype that fit my needs and adding in the Bug Labs libraries.

This is the first archetype I've made, and I'm a little rusty on the internals of Maven, so if you have trouble I'd be happy to work through it with you - just file an issue in the GitHub project.

A Google Voice Landline with Asterisk

2011-06-04T00:00:00-07:00

Inspired by a recent Maximum PC article, I recently set up a land line telephone that supports both incoming and outgoing calls from my Google Voice number. I opted to use an installation of Asterisk in on a standard Ubuntu server instead of using one of the pre-built PBX Linux distributions. The process involved enough fiddling and Google searching that I thought a summary of how my setup works could be helpful for others.

You can probably guess by the recent addition of calling to Gmail that Google is using VoIP protocols to shuffle Voice traffic around. Thankfully, they're somewhat standard, and Asterisk recently added official support for it. Just like the calling feature in Gmail, an Asterisk server can connect to Google and send/receive calls.

Chef Cookbook

I've written a Chef cookbook that does most of this configuration automatically. I'll go over the basics of the cookbook if you don't use Chef.

Install the Package

The best place to get the Asterisk package is the official asterisk.org repository. Add it to your /etc/apt/sources.list:

deb http://packages.asterisk.org/deb natty main

Then install the PGP key and update your package lists:

sudo apt-key adv --keyserver subkeys.pgp.net --recv-keys 175E41DF
sudo apt-get update

Finally, install the two packages we need:

sudo apt-get install asterisk-1.8 asterisk-dahdi

Configuration

There are five configuration files to change:

`/etc/asterisk/sip.conf`

Set localnet to the IP range of your LAN, e.g. 192.168.1.0/255.255.255.0
tcpenable = 'yes'
disallow = 'all'
allow = ... for ulaw, gsm, ilbc, and speex
externip must be set to your external (i.e. WAN) IP address

Finally, in the [authentication] section, add the details for your user account:

[DESIRED_ASTERISK_USERNAME]
secret=YOUR_DESIRED_PASSWORD
type=friend
callerid="Your Name <username>"
host=dynamic
context=outbound

`/etc/asterisk/extensions.conf`

This file sets up all routing paths for getting calls from Google to your user. This configuration is probably a bit more than is required (and is a mashup of a few different blog posts), but it's working for me at the moment:

[general]
static=yes
writeprotect=no
clearglobalvars=no

[globals]
CONSOLE=Console/dsp             ; Console interface for demo
IAXINFO=guest                   ; IAXtel username/password
TRUNK=Zap/G2                    ; Trunk interface
TRUNKMSD=1                  ; MSD digits to strip (usually 1 or 0)

[default]
exten => s,1,Set(CALLERID(name)=${DB(cidname/${CALLERID(num)})})
exten => s,n,Dial(SIP/YOUR_ASTERISK_USERNAME, 10)
exten => s,n, Hangup
exten => YOUR_ASTERISK_USERNAME, 1, Dial(SIP/YOUR_ASTERISK_USERNAME, 10)

[google-in]
exten => YOUR_ASTERISK_USERNAME, 1, GotoIf(${DB_EXISTS(gv_dialout/channel)}?bridged)
exten => YOUR_ASTERISK_USERNAME, n, NoOp(Callerid  ${CALLERID(name)})
exten => YOUR_ASTERISK_USERNAME, n, Set(CALLERID(num)=${SHIFT(CALLERID(name),@)})
exten => YOUR_ASTERISK_USERNAME, n, Set(CALLERID(name)=${DB(cidname/${CALLERID(num)})})
exten => YOUR_ASTERISK_USERNAME, n, Dial(SIP/YOUR_ASTERISK_USERNAME, 20, aD(:1))
exten => YOUR_ASTERISK_USERNAME, n(bridged),Bridge(${DB_DELETE(gv_dialout/channel)}, p)

[outbound]
include => seven-digit
include => local-devices
include => tollfree
include => talk-gmail-outbound
include => talk-numeric-outbound
include => dial-uri

[local-devices]
exten => YOUR_ASTERISK_EXTENSION_NUM, 1, Dial(SIP/YOUR_ASTERISK_USERNAME, 10)

[tollfree]
exten => _411, 1, Dial(SIP/18004664411@proxy.ideasip.com,60)
exten => _1800NXXXXXX,1,Dial(SIP/${EXTEN}@proxy.ideasip.com,60)
exten => _1888NXXXXXX,1,Dial(SIP/${EXTEN}@proxy.ideasip.com,60)
exten => _1877NXXXXXX,1,Dial(SIP/${EXTEN}@proxy.ideasip.com,60)
exten => _1866NXXXXXX,1,Dial(SIP/${EXTEN}@proxy.ideasip.com,60)

[seven-digit]
exten => _NXXXXXX,1,Set(CALLERID(dnid)=1512${CALLERID(dnid)})
exten => _NXXXXXX,n,Goto(1512${EXTEN},1)
exten => _NXXNXXXXXX,1,Set(CALLERID(dnid)=1${CALLERID(dnid)})
exten => _NXXNXXXXXX,n,Goto(1${EXTEN},1)

[talk-gmail-outbound]
exten => _[a-z].@gmail.com,1,Dial(gtalk/google/${EXTEN}@gmail.com)
exten => _[A-Z].@gmail.com,1,Dial(gtalk/google/${EXTEN}@gmail.com)

[talk-numeric-outbound]
exten => _1XXXXXXXXXX,1,Dial(gtalk/google/+${EXTEN}@voice.google.com)
exten => _+1XXXXXXXXXX,1,Dial(gtalk/google/+${EXTEN}@voice.google.com)

[dial-uri]
exten => _[a-z].,1,Dial(SIP/${EXTEN}@${SIPDOMAIN},120,tr)
exten => _[A-Z].,1,Dial(SIP/${EXTEN}@${SIPDOMAIN},120,tr)
exten => _X.,1,Dial(SIP/${EXTEN}@${SIPDOMAIN},120,tr)

`/etc/asterisk/jabber.conf`

This file configures the authentication details for your Google account (Jabber is the protocol used by GTalk, and it's technically how you log in). This file contains your Google password, so make sure it's only readable by your user or root.

[general]
autoregister=yes

[google]
type=client
serverhost=talk.google.com
username=YOUR_GOOGLE_ACCOUNT@gmail.com/Talk
secret=YOUR_GOOGLE_PASSWORD
port=5222
statusmessage=Asterisk Server - Not a Human
status=xaway

`/etc/asterisk/gtalk.conf`

Finally, this file links together your Google account (defined previous in the jabber.conf file) with Google Voice.

[general]
context=google-in       ; Context to dump call into
allowguest=yes

[guest]         ; special account for options on guest account
disallow=all
allow=ulaw

[gtalk]
username=YOUR_GOOGLE_USER@gmail.com
disallow=all
allow=ulaw
context=google-in
connection=google

Google Voice Configuration

The last step is to enable Google Talk as an extension in your Google Voice account. This should be pretty straightforward.

Caveats

There are a few known issues with this setup.

The Google account you use will appear logged into Google Talk anytime the server is running. Messages sent to the server will just get lost in the ether. I set up a separate Google account with my Voice number so this wouldn't be an issue. If you already have an established Voice number that you don't want to change, another option is to create a second Google account for chat only - although then you lose the ability to use the inlined chat in Gmail. If anyone has a better solution for this, I'd love to know about it.

Incoming calls are somewhat unreliable. Sometimes the phone will ring, but after picking it up you just get dead air. My cell phone keeps ringing when this happens so I'm still able to pick up the call. It's annoying, however, and I'd love to find the root cause.

I suspect that Google's requirement that you hit "1" when accepting a call via SIP is the problem. This Asterisk config attempts to do that automatically for you, but it took me quite a while to nail down that process and it's most likely still not working. Sometimes jabbing "1" when I get dead air seems to wake it up, but not every time.

Otherwise, outgoing calls work quite well. The only issue I've ever had is if I'm using all of my upstream bandwidth doing something else, but that's not unique to Asterisk. Some QoS controls in your router should help out with that.

OAuth for Privacy

2011-05-29T00:00:00-07:00

I wrote this paper for Professor Lorrie Cranor's Privacy Policy, Law & Technology course at Carnegie Mellon Unversity. A PDF version is available.

Abstract

The rise of Facebook, Twitter and their associated ecosystems of third-party applications was accompanied by a new authentication protocol, OAuth. The protocol enables single sign-on (SSO) as well as limited information sharing between web services at the behest of users without revealing credentials. It also provides an opportune hook for confirming privacy policies with users during authentication, but because of the difficulties of enforcement, an extended OAuth is no more or less effective than other efforts to increase user awareness. The most effective approach will be the education of web developers and information platform operators.

Introduction

The era of Web 2.0 may have reached buzz-word status, but the changes in Internet-enabled applications it ushered in have had an enormous impact on the quantity and flow of personal information online. With web applications, more user activities are done entirely online, and the services are becoming increasingly interconnected. The rise of Facebook, Twitter and their associated ecosystems of third-party applications was accompanied by a new authentication protocol, OAuth. OAuth enables single sign-on (SSO) as well as limited information sharing between web services at the behest of users without revealing credentials. Unlike the last major SSO contender, OpenID, OAuth has gained widespread adoption. For example, applications taking advantage of Facebook's OAuth access include the New York Times and Farmville.

The procedure to grant a third-party client access to data stored in a centralized personal information store, e.g. Facebook, is now greatly simplified and users are comfortable with the process. The ease and familiarity means that more people are sharing more data with more sites, and understanding the privacy policies of each party involved is even more of a daunting task.

Authorizing access to a resource through OAuth is inherently different than visiting a single website with a browser. The authorization is done under the banner of an already trusted website. The OAuth process provides an opportunity to better inform the user of the privacy they can expect for their data and to warn them when data leaves the safety of the host application. One of the hurdles for the standard privacy enhancing protocol P3P was that it required adding an additional step to a user's workflow: setting up privacy policy preferences, paying attention to a warning icon at each new website, using a different search engine, etc. Instead, P3P-style privacy negotiation can be bundled with authentication and shown to the user on the same OAuth permission page they expect. This paper describes one such possible extension to the OAuth specification.

OAuth provides an opportune hook for confirming privacy policies with users during authentication, but because of the difficulties of enforcement, an extended OAuth is no more or less effective than other efforts to increase user awareness. The most effective approach will be the education of web developers and information platform operators.

Definitions

This project intentionally uses some of the same language as the OAuth2 specification. The published definitions are provided verbatim, with some additional comments for clarity.

protected resource "An access-restricted resource which can be obtained using an OAuth-authenticated request." E.g. an e-mail address or phone number.
resource server "A server capable of accepting and responding to protected resource requests." E.g. Facebook or Twitter.
client "An application obtaining authorization and making protected resource requests." E.g. a third-party such as the New York Times or a Zynga.
resource owner "An entity capable of granting access to a protected resource."
end-user "A human resource owner."
token "A string representing an access authorization issued to the client. The string is usually opaque to the client. Tokens represent specific scopes and durations of access, granted by the resource owner, and enforced by the resource server and authorization servers."
access token "A token used by the client to make authenticated requests on behalf of the resource owner."
authorization server "A server capable of issuing tokens after successfully authenticating the resource owner and obtaining authorization. The authorization server may be the same server as the resource server, or a separate entity." E.g. Facebook or Twitter, which act as both resource servers and authentication servers.

Web Services

A web service, loosely defined, is an application hosted on the Internet that exposes its functionality and data not only through a graphical user interface in a browser, but through a computer-readable interface (commonly referred to as an application programming interface or API). A web application with an API can be combined with other data sources by developers to create unique combinations of features or entirely new applications based on data previously collected or processed. For example, third-parties can offer additional insight into a user's social network by tapping into the connections they've already made in an application like Facebook. Such data sharing significantly lowers the barrier of entry for new applications, which can now piggyback off of the success of other platforms instead of building an entirely new user base. Users appreciate not needing to sign up for as many accounts, and developers appreciate the deferring of authentication work to other servers.

As users begin connecting the applications they use together, they have started thinking (often subconsciously) about their online identity. Users are concerned with who has access to their identity and to which elements of their personal information and activities online. Application developers continue to need a way to uniquely identify users to offer services, and of course want to share the work of authentication if possible. The interests of the two parties can often seem at odds.

Identity Management

Identity management is the process or system by which users control the contents of and access to the pieces of their digital identity. There are two approaches to identity management - user-centric and organization-centric.

Organization-centric management is the approach taken by many companies today, where user data is increasingly linked with a unique identifier to try and create relationships between an individual's accounts in different business entities.

User-centric management gives the individual more control. This system avoids using globally unique identifiers for users, instead creating service-specific identifiers that uniquely identify a user within an area but are insufficient for cross-referencing between databases. In some proposed systems, access control resides in a "permission hub," where a user identifies and authenticates, and third-party clients connect to request access to various resources. While not conceived as such, OAuth's capabilities and usage patterns are in some ways an embodiment of this idea. Users are consolidating their personal information into a few large data silos (e.g. Facebook), using OAuth to control access.

A further evolution of user-centric identity management is the Personal Data Store (PDS). A PDS is a server - either a user's own computer or a hosted solution – that stores personal information and releases it as needed to third-parties with the user's consent. It combines personal information storage, authentication, validation and permissions into one system. This idea shares many features with a "permission hub," and thus the existing social networks.

The PDS highlights some security and privacy concerns with data consolidation, especially considering that previously distributed, uncorrelated information is now centralized in a single server and thus a single, vulnerable target. An analysis of the benefits and risks of this approach to identity management is beyond the scope of this project. However, considering the success of Facebook (arguably a proprietary PDS), it is reasonable to assume that for many, these concerns aren't a top priority or that the benefits of such a system outweigh the risks.

The goal of this project is to find a way to provide a basic level of privacy protection and notification to users of these systems while minimizing any additional burden on users and software developers. The success of these so-called "software as a service" applications depends on the availability of a secure but extremely simple method of authenticating and sharing user information between services. OAuth fostered innovation by lowering the barrier of entry for developers to link data and for users to try out new tools, and any additional privacy controls cannot stand in the way of this feature without risking alienating the market.

Personal Value in Linking Data

Beyond single sign-on, OAuth was the first user-friendly protocol for linking accounts together for the purposes of sharing data. The process is initiated by the user, so there is likely some apparent benefit for them to do so. This is not a situation where the resource server is offering user data to third-parties for profit or marketing. The rate of user adoption indicates there is great value to consumers in being able to link their data between services.

Conversely, OpenID has had limited success in gaining popular traction. OAuth and OpenID undoubtedly have different goals. OpenID providers serve primarily for identity management - the user's OpenID URL is their identity online. OAuth, oppositely, was created to solve security concerns when delegating access to a user's account with a specific service. Instead of providing a username and password, third-parties can use an access token with limited capabilities that can be revoked at will by the user without having to change their password. For better or worse, OAuth has emerged as the leading protocol in both realms. Web developers found OAuth to be easier to implement than OpenID, and so began using it as their primary SSO tool.

Debating the merits of relying on a limited number of proprietary OAuth servers (e.g. Facebook and Twitter) instead of an unrestricted set of OpenID providers is beyond the scope of this project, but again, we must recognize the higher acceptance of OAuth among users.

API Keys

Before OAuth, API keys were the most popular way of authenticating requests to or between web services. These are simple persistent access tokens generated once and appended to each HTTP request, which uniquely authenticates and authorizes a user for that request. Their implementation is generally insecure, as requests made over standard HTTP (and not SSL-encrypted HTTPS) are sent in the clear and the token is susceptible to snooping. More importantly, they are too cumbersome for end users, who won't be bothered with copy and pasting long strings from application to application.

OAuth adds an extra layer of security be default (by using signed authentication requests in the original specification, and requiring SSL encryption in the next iteration), and pushes the exchange of access tokens down from the user layer to the server layer. The end result is the same - the third party has some sort of authentication token that allows them to make requests on behalf of the user - but the details of the process are transparent to the user.

Single Sign-On v.s. Access Delegation

The use of OAuth for single sign-on can unfortunately lead to data creep, as third parties take advantage of the protocol to gather data from users. Users are so comfortable with the OAuth process that they may not fully review each request for access. An application that only uses the protocol for authentication may be requesting access to much more data than is required to perform their business function.

The client application does not always have malicious intent. Hoping to avoid having to reacquire access in the future (and thus bother their users), and also to give themselves as much flexibility as possible, developers have a tendency to ask for complete access to a user's information even if a subset would be sufficient.

Furthermore, there is no standard granularity (either in the specification or in common practice) of control that a user has over the access granted to clients. Some data stores grant access on a per-item basis, while others offer only blunt "read" and "read and write" options. Requests for authentication have a wide range of requirements. Linking to personal information, or even identifying an individual is often unnecessary. The primary risks of broader application of authentication include covert identification, excessive use and excessive aggregation. The authentication protocol should be careful not to encourage excessive data exposure.

State of Identification, Authorization & Privacy

Privacy Policy Troubles

The protections offered to users by first-party information stores are not often made clear during the OAuth authorization workflow. When a user submits personal information to a trusted website, they expect the site to follow its stated privacy policy. It is not clear that they can expect the same level of protection from third-parties to which they grant access. OAuth offers no opinion on the responsibility of clients to abide by the resource server's privacy policy. Furthermore, there is no requirement in the specification for the resource server to verify compliance by the client.

In practice, the protections offered to users differ on a site to site basis. This is no different than without OAuth (where users still must expect different privacy policies on different websites), but the addition of almost trivial data sharing between companies stacks the cards against users. One may say that granting access via OAuth is sufficient consent, but the current user interfaces do not sufficiently explain the risks and conditions. The result is a clean, simple interface for sharing information which encourages users to share more and give up privacy in exchange for promised improvements in service. This protocol could be more mindful of users without significantly complicating the process.

Pragmatic Privacy Enhancement

Ideas for an overhaul of identity management have been brewing over a period of years, while users and developers are moving ahead with whatever technology is most accessible. It is in the interest of all parties to make smaller, incremental improvements to existing technologies to improve user privacy instead of focusing soley on ideal, complete systems.

In a keynote address at the Identity 2.0 conference, Dick Hardt questioned which sector will spearhead such an identity overhaul. The success of OAuth proves the power of small companies and individual developers in shaping the technologies used online. Some of the most technically up-to-date, standards-compliant and accessible websites are from these small players, not the government, banks or large corporations (who are in fact notoriously behind the curve online). Many of the disruptive software technologies of the past five years have started as grassroots efforts led by developers and not the result of any corporate-backed strategy.

In Practice

There are many projects in the identity management space that attempt (or have the capability) to integrate at least one aspect of privacy control with single sign-on - fine-grained information release, permissions delegation, personal information storage, etc. OAuth is a slim protocol that has only one parameter specifically aimed at access control - scope.

When a client makes a request for a resource on behalf of the resource owner, it can optionally set the value of the scope parameter. This parameter is a space separated, unordered list of values that describes the types of data or permissions this application is requesting. The OAuth specification leaves the details of the possible values up to the authorizing and resource servers, meaning that each OAuth provider has a different set of permitted scope values and valid combinations. For example, Facebook's implementation of the OAuth2 draft describes a set of "extended permissions" that can be requested via the scope parameter. MySpace made their own proprietary modifications to the original OAuth protocol to implement a similar feature.

Typically, the user will see a human-readable description of the scope requested on the authorization screen. If they accept, the scope is stored alongside the access token that is generated - together, a contract between the two applications. The client's subsequent requests for protected resources with this access token can only access the data or perform the actions described by the stored scope. There is no way for the third-party to access a resource to which the user did not specifically grant access (unless there are security holes in the resource server).

This is a screenshot of the OAuth access grant for the New York Times Facebook application. Facebook informs users of the resources requested by the application, but does not allow fine grained control. The page includes a subdued notice that use of the data is subject to the application's privacy policy, not Facebook's.

In common practice, the scope describes only what can be accessed, not what can be done with the information after it has been shared. There is no notice for a user that by granting access to their e-mail address (stored with the content provider), they may be unintentionally providing it to advertisers as well.

Two examples of OAuth authorization pages, Facebook and MySpace, illustrate the lack of standardization for informing users of data exposure. MySpace includes a descriptive notice in small, light gray text at the bottom of the screen: "The service you are linking to is not provided by MySpace. If you choose to link to this service, it may share your data in accordance with the privacy policy of and your privacy settings on the linked service."

It also includes a note about and a direct link to the account page for revoking access for previously authorized applications:

"To revoke access to this linked service and for more information visit the Sync section of your MySpace account."

This is a screenshot of the extended permissions on MySpace OAuth access grant page. MySpace added proprietary permissions parameters to the original OAuth specification, as well as OpenID. Users can choose whether or not to grant permission for each resource individually with check boxes. Similar to Facebook, the page includes a subdued (but more descriptive) notice that the shared data is subject to a new privacy policy.

The authorization page for Facebook applications provides much less information. If the client application provided one, Facebook will display a link to a privacy policy with a note about possible extended use. In the case of the New York Times Facebook client:

"Use of this data is subject to the The New York Times Privacy Policy".

Again, the text is small, gray and likely to be missed by users. Compared to MySpace, this version at least provides a link to the client application's website. Disturbingly, however, if the application omits a privacy policy link from their application settings, not only is no link displayed but there is no longer any mention of possible extended data use. In this case, it would be reasonable (but dangerously incorrect) for a user to assume that their data is still covered by the Facebook privacy policy, and at no greater risk of exposure after authorizing the application for access.

This is especially important since once a user's data is transferred, it could be stored indefinitely on the third-party servers. By granting OAuth access to one's Facebook profile, for example, their entire social network history could be replicated on an insecure server with no policy for data protection or breach handling.

Most application developers implicitly agree to platform policies written by the resource servers when an application is first created. The policies range in their limitations, but for example, Facebook's developer agreement requires that data not be sold to advertisers. The privacy policy and develop policy are typically not in the same location on the resource server's website, and end-users are not expected to navigate to the developer area.

Proposed OAuth Extension

OAuth is an interesting candidate for integrating privacy controls because it is an open standard and in the set of popular authentication systems, a relatively simple protocol. OAuth is also a standard in flux - the next version of the standard, OAuth2, is current being drafted. The draft is already implemented by Facebook, while the first version is in use elsewhere. The standard is at a late enough stage that such privacy extensions will not likely be incorporated, but the activity does suggest that the market for an authentication standard is active and willing to adapt quickly.

No existing authentication system with wide deployment has ever met all of the criteria for a complete identity management system. Rather than trying to build a complete system from scratch, or even modify an existing one to cover all areas, OAuth should be extended only in ways that are most natural. One problem with privacy enhancing technologies is that they typically add to or change the workflow of a user. This approach instead augments something they are already used to doing (OAuth) with privacy controls.

The proposed extension adds additional user control of and consent to information release and an element of minimal disclosure (pseudonyms). The goal of the extension is not to implement all aspects of identity management, as others have tried in the past, but to embolden OAuth to become a partner in a mixed "identity metasystem". Compared to other existing or proposed systems, the extended OAuth specification does not attempt to be as feature complete or secure. It represents a pragmatic approach to identity management, and attempt to create an incremental improvement on the way to a better system.

Viewing an OAuth access request as a pseudo-P3P policy, the protocol is current missing the "usage" section which would define the intended use of the data. OAuth can be combined with P3P-style privacy summaries to allow users to simultaneously authenticate and approve privacy policies. The extension registers a usage parameter (similar to scope) that uses P3P compact policies to describe how the information will be used. Additionally, the specification recommends that only a pseudonym is exposed to the client by default, unless more detailed identification is specifically requested.

Parameter Name usage

Parameter Usage Location The end-user authorization endpoint request, the end-user authorization endpoint response, the token endpoint request, the token endpoint response, and the "WWW-Authenticate" header field.

Access Grant

When a client is requesting an access grant (the process of prompting a user to grant permissions) they can optionally provide the usage parameter.

usage - The intended use of the data in the scope of the access request expressed as a P3P compact policy. This parameter is optional.

Errors

invalid_usage The requested usage is invalid, unknown, or malformed.

Access Token

After the access grant, the client can request an access token.

Request

usage - The intended use of the data in the scope of the access request expressed as a P3P compact policy. If the access grant being used already represents an approved usage, the requested usage MUST be equal or lesser than the usage previously granted. This parameter is optional.

Response

usage - The allowed use of the data in the scope of the access request expressed as a P3P compact policy. The authorization server SHOULD include the parameter if the requested usage is different from the one requested by the client. This parameter is optional.

Errors

invalid_usage - The requested usage is invalid, unknown, malformed, or exceeds the previously granted usage.

Sample P3P Compact Policy

A social network user may have the following privacy preferences, expressed and stored as a P3P compact policy:

ALL DSP CURa ADMa DEVa IVAa IVDa OUR NOR ONL DEM CNT PRE

This (optimistic) policy will match applications that use the data requested only for completing the current action (e.g. searching a friends list), individual analysis or individual decision making (e.g. personalized service based on a social network profile). The only recipient of the data can be the client application itself, and the data cannot be retained beyond an active user session (meaning that the application must re-request the information it requires from the resource server each time the user logs in). The user must be able to access all information stored with the application about themselves. Finally, the application must have a dispute resolution plan.

If the user begins the authorization process for an application with the following non-compliant policy, they will be warned of the specific differences:

ALL DSP CURa ADMa DEVa IVAa IVDa TEL OUR NOR ONL DEM CNT PRE

In this case, the application plans to use the data for telemarketing - something the user's privacy preferences do not allow. Technically, P3P compact policies are only intended for use with HTTP cookies. Using them here is a slight stretch of the P3P specification, but it reflects their spirit. One limitation of compact policies (addressed in the P3P 1.1 draft specification) is the lack of granularity - the usage described in the policy applies to all data collected from the user. The 1.1 specification introduced compact statements, which group together a set of compact policy elements to describe one or more types of data. This allows the application or user to specify different intended usage for each type of data mentioned in the scope parameter, a reasonable request for both parties when considering the wide range of information shared via OAuth (from first name to geotagged photographs).

Use Cases

No Privacy Settings

If an authorization server does not allow users to predefine their minimum privacy requirements or the user does not have any set, the site must assume the highest level of privacy. The user should be prompted on each access grant to confirm the privacy settings manually.

Insufficiently Limited Use

If a user has their minimum privacy preferences set at the authorization server and the client is requesting usage beyond what is allowed by those preferences, the user should be shown a prominent warning and a description of the specific discrepancies. The user should be able to manually grant access even in this case.

This is a mockup of an extended OAuth access page with a privacy policy mismatch. If the user's privacy settings do not match the usage requested by the application, they should be warned but allowed to proceed.

Sufficiently Limited Use

If a user has their minimum privacy preferences set at the authorization server and the client is requesting usage less than or equal to what is allowed by those preferences, the user not be shown anything specific regarding the privacy settings (beyond perhaps a small icon indicating that there are no issues). Since the majority of cases will likely fall into this use case, users should not be constantly bothered with notifications that the privacy settings are acceptable. They should only be notified when there is an issue. In this case, the user just needs to decide if they wish to grant access to the specific application, confident that the third party's privacy policy matches their own personal privacy requirements.

Usage Upgrade

If a client has an access token for a user, but wishes to expand the usage of their personal information, they must reacquire the token from the authorization server either by prompting the user out-of-band (e.g. e-mail) of their new desired usage or by requiring the user's permission at the next application launch. They must reacquire the token with the new usage settings, and they must be properly stored with the authorization server.

Policy Violation

There is no technical way to enforce a usage policy. The authorization server must be vigilant in confirming the practices of their permitted client applications, and follow up with complaints from their customers. In the case of a breach of policy, all users of that application (easy to find from the content provider's access token registry) must be notified and given the option to continue or terminate their relationship with that client.

Alternatives

There are numerous alternative approaches to integrating privacy with authentication and identity management. This section describes some of the efforts of other projects, as well as ideas considered and dropped in favor of the OAuth extension described in this paper.

Web2ID

Current single sign-on solutions rely on a trusted, centralized identity provider to authenticate users at various websites. This violates the user's privacy because the websites they authenticate with are exposed to the identity provider. One example of a decentralized single-sign on system is Web2ID, an SSO framework that uses public & private key encryption in place of an identity provider.

Tailored specifically for in-browser web service mashups, Web2ID avoids some of the problems associated with the redirects and page refreshes required by OAuth. The added complexity is of debatable value for end-users, however. Web2ID also introduces a broader identity management framework (closer to OpenID) and is not backwards compatible with any existing protocols.

User-centric Federated SSO

Centralized SSO also violates user privacy by allowing identity managers and service providers to exchange and link personal information and web traffic. The User-centric Federated Single Sign-On System (UFed) adopts the principles of user-centric identity management to protect privacy. UFed relies on existing protocols, but not the most widely used ones. It also sacrifices simplicity for security, something which many service providers do not require and which developers may resent.

P3P

The existing machine-readable privacy protocol, P3P, could be used without modification during the authentication process for clients. The primary use case for P3P requires the user's browser or other end-user application acting as a user-agent to access a website's P3P policy. Instead, the authorization server could act as the user agent and communicate directly with the client application. Users no longer need to install any additional software for policy checking and the rollout can be a resource server-led effort.

Short of implementing dynamic per-user full P3P policies, the authorization server and client could use standard P3P compact policies in their HTTP headers when requesting token access. The workflow would be identical to that described in section 4, but with the policies sent via HTTP headers instead of URL parameters.

This approach would require the modification of neither the P3P or OAuth specifications, so can be implemented by any resource server immediately. That said, without being explicitly described in a standard protocol, it must rely on becoming common practice through other means. Another problem is that the definition of the scope and usage fields would be less similar in the code. For example, typical open-source OAuth libraries accept URLs, user IDs and access tokens as parameters. This approach would require them to also accept the HTTP request itself, to access the P3P headers. There is an increased chance that the scope and usage would fall out of sync as their data structures diverge.

Identity Metasystem

Personal identity on the Internet is based on a fractured landscape of incompatible systems and has seemingly been on the verge of its next phase (some say "Identity 2.0") for multiple years. No single system has been created that completely satisfies developers and users alike, and those that have come close never saw widespread deployment. Identity advocates propose an "identity metasystem" that combines the many existing implementations of identity management into a unified platform.

The "identity metasystem" attempts to unify the interface for online authentication for both developers and consumers. The task is not impossible, as such abstraction layers have been created for other areas of computing (e.g. video, networking). The inspiration for the system is the Laws of Identity, a set of principles for identity management set collaboratively by identity advocates. They cover user consent, disclosure, information user justification and usability.

The most promising of the alternatives, it is also one of the biggest. This system may eventually mitigate the privacy concerns described in section 3.1, but widespread deployment is remote compared to the availability of OAuth today.

Conclusion

Despite their similarity in implementation, there is a problematic difference between the proposed usage parameter and its counterpart scope. If a protected resource is not in the scope of an access token (e.g. e-mail address), there is no technical way for the third party to access that data. If the application doesn't abide by the policy they were granted by the usage parameter, there is no technical recourse. There is no way for the user to detect that the information is being misused, and no way to revoke access once it has been transferred off of the resource server. This fact makes the extended OAuth specification no better and no worse than existing privacy policy tools when it comes to protecting users. What it does provide is better notification and a clearer contractual agreement between parties.

In the end, any new identity system has to be sold first to developers. Developers will accept and implement a relatively complicated identification protocol if and only if the information behind the authentication wall is of sufficient value. Despite complaining loudly, developers using the Twitter API all migrated from Basic Authentication to OAuth because the API was compelling enough to do so. Other service providers with a lower uptake in OAuth usage suffer from a lack of quality offerings.

Without much trouble, OAuth can be extended to incorporate existing approaches to communicating privacy preferences. Unfortunately, it is susceptible to the same issues - namely a lack of enforcement and thus a lack of incentive for client compliance. Unless the resource servers required it (unlikely), developers would be unlikely to adapt the privacy extension.

Recommendations

OAuth is not a traditional single sign-on solution in that the identity has stronger ties to the identity provider. The resource servers & identity providers should take advantage of this close relationship to make a safer user experience. Within the bounds of the existing OAuth2 specification, the follow recommendations would improve user notification and expand awareness of the risks of data exposure:

In the interest of their customers, resource servers are encouraged to hold their client applications to the terms of the host application's privacy policy. To maintain the faith of their users, they must aggressively pursue those who violate it.
Resource servers should hold third-party applications to higher standards when granting access to the ecosystem. The requirements at registration for Facebook and Twitter clients are minimal, with little verification of the legitimacy of any proposed application. This has certainly helped with the rapid expansion of applications, but at the cost of user security and privacy.
Authorization servers are encouraged to support only SSO by default. A user's unique identifier should be considered a protected resource, and a pseudonym should be provided in its absence. For example, with a blank scope field, Facebook applications can currently access "all public data in a user's profile, including her name, profile picture, gender, and friends" as well as the user's unique identifier (i.e. Facebook ID). For simple single sign-on, absolutely none of this is required - only a valid, permission-less access token that sufficiently identifies the user. Clients should be required to explicitly request each protected resource in the scope parameter beyond this pseudonym, to make it clear to users and developers what information is accessible to each party.
Users should be allowed to modify the valid lifetime of access tokens. They should be able to to grant single use or other time-limited access tokens instead of the default permanent ones.

Offline References

The online references for this article are linked inline.

Wang Bin et al. "Open Identity Management Framework for SaaS Ecosystem." In: ICEBE '09: Proceedings of the 2009 IEEE International Conference on e-Business Engineering. Wash- ington, DC, USA: IEEE Computer Society, 2009, pp. 512–517. isbn: 978-0-7695-3842-6.

Stephen Farrell. "API Keys to the Kingdom." In: IEEE Internet Computing 13.5 (2009), pp. 91–93. issn: 1089-7801.

Suriadi Suriadi, Ernest Foo, and Audun Josang. "A User-centric Federated Single Sign-on System." In: NPC '07: Proceedings of the 2007 IFIP International Conference on Network and Parallel Computing Workshops. Washington, DC, USA: IEEE Computer Society, 2007, pp. 99–106. isbn: 0-7695-2943-7.

Stephen T. Kent and Lynette I. Millett. Who Goes There?: Authentication Through the Lens of Privacy. Washington, D.C.: National Academies Press, 2003. Chap. 1,2.

Monitoring Civil Infrastructure

2011-05-29T00:00:00-07:00

A PDF of this post is available

Introduction

Civil engineers were some of the first to take advantage of the information revolution around the time of plugging semi-conductor prices. As early as the 1970's, major infrastructure projects were wired with real-time monitoring and control systems to lower costs and improve safety and operating efficiency. This trend continues today.

Meanwhile, computer system architecture shifted three major times in these past 40 years. Individual, personal computers gave way to mainframes and thin clients. The tide shifted back to powerful end-user clients in the 1990's. Now, the cloud and web services embody somewhat of a throwback to the mainframe era. Computer networks remained quite small in comparison to some infrastructure sensor networks, at least until until the rise of the Internet as we know it. Now, some computer systems rival the largest infrastructure projects in size (if not cost). These systems have some of the same issues with monitoring and statistics analysis.

An example of a relatively new, distributed computer application are massively multiplayer online games. The game publisher Blizzard has a vested interested in tracking the users of their online game World of Warcraft for billing, game balancing and to plan for future expansions. In order to scale the game world in a reasonable fashion, the developers split up the environment into thousands of shards. The gameplay statistics must make it back to a centralized location at Blizzard eventually, but the fractured architecture doesn't lend itself to a simple solution.

The data center ecosystem itself is also one massively distributed system, encompassing thousands of nodes across a diverse geography. In short, distributed systems are more common than ever and the importance of monitoring, tracking and accounting hasn't waned.

These applications are what bring the computer world more in line with the monitoring situation in civil infrastructure. Civil engineers and government organizations in charge of projects such as roads, bridges, oil & gas pipelines and waterways have been struggling with monitoring some of the earliest distributed systems. These are not distributed in the same computing sense of the word; they are often entirely offline and unpowered. For decades, their data has been gathered (often inconsistently) by hand. The engineers tasked with accounting for trillions of dollars of public assets and physical systems are dealing with what could be viewed as widespread network unreliability and wholly unreliable nodes.

Infrastructure Monitoring

The operators and designers of civil and computing infrastructure have a keen interest in collecting knowledge of the behavior of the systems. Infrastructure management is increasingly data-driven, requiring ever more monitoring. It is also useful for providing a global-level view of the condition of a system. This can often be a good indicator of when and where a failure occurred, giving operators prime candidates for further investigation. The three primary motivations for infrastructure monitoring are asset management, safety and operations.

Asset Management

Asset management is an increasingly popular (and in some cases required) strategy for managing an organization's physical assets. It includes performing continuous inventory, risk modeling, and life-cycle and condition assessment. All of these rely heavily on computing for data collection and analysis. A monitoring system more tightly integrated with asset management tools can give more accurate predictions - e.g. automatically collected gas measurements in power transformers can be taken nearly continuously, compared to quarterly or yearly manual inspections. On the computing side, data centers are becoming increasingly heterogeneous and asset management is important, albeit to a lesser degree.

Safety

Many infrastructure components require constant inspection to ensure safe operation. Components have different safe operating ranges for various statistics (temperature, pressure, cycles, etc.) and the more accurate and up-to-date this information is when it reaches the control center, the better. There are fewer safety considerations for computer applications, but a parallel metric is the reliability and robustness of users' data storage.

Operations

Normal day-to-day operations of some types of infrastructure previously required many employees on-site to monitor and operate different components. With a two-way communication system between infrastructure and control room (i.e. one that sends commands and receives metrics), these jobs can be done more efficiently with fewer people and with a better sense of the status of the system as a whole. For example, operators on two ends of a pipeline many have a difficult time determining the status of an issue occurring in the middle. With remote monitoring, these parties can deal with the situation all from the same room. The same goals hold true for data center operations, and especially for geographically distributed software systems.

Sensing

Modern research prefers wireless sensors over wired. These systems are harder to disrupt, which is of greater concern when the system is out in the open and many network hops away from the central office. A widely distributed wired network involves a significant amount of extra infrastructure, and damage to the infrastructure being monitoring often implies damage to the monitoring system itself. Wireless systems have the advantage of being easier to deploy, as they can self-organize into ad-hoc networks (see the figure below) as long as they are within range of another sensor node. Connectivity problems also tend to be isolated to individual units, and are easier to troubleshoot.

Wireless sensors along a pipeline form an ad-hoc wireless network and communicate only with nearby neighbors (source)

Recent projects have taken a page (knowingly or not) from tools like the computer network monitoring application Ganglia and now use a unified data format, regardless of sensor or data type. For example, a single update could consist of:

Type of data (1 byte)
Geographic coordinates, determined via GPS or inferred via signal strength of other nodes
Network address
Actual data (4 bytes)

These monitoring networks self-organize into a dynamic hierarchy of nodes based on their placement and capabilities. There are generally three types of nodes deployed:

Basic sensor node
Communication relay node - collects data in its 1- or 2-hop neighborhood
Data Discharge Node - forward results to the Network Control Center, i.e. the one with a connection to the Internet

Whereas in computer system monitoring, each node generally has similar capabilities for communication and sensing, the role of these nodes are bound by their physical capabilities. Hierarchical organization becomes a simpler problem of guaranteeing a wide enough dispersal of communication relay and data discharge nodes to reach all of the levels of the hierarchy, compared to the somewhat arbitrary trees made in computer networks.

An example hierarchy for a network of sensor nodes (source).

A critical feature of these networks is the scalability of their performance: "[s]uch a dense array must be designed to be scalable, which means that the system performance does not degrade substantially, or at all, as the number of components increases" (source). The fact that each node only communicates with its closest neighbors is a strong indication that such a design is scalable to tens of thousands of nodes.

Collection & Processing

A significant impediment to a monitoring system's success is the amount of processing required to put the data into a useful form. The amount of data recorded for infrastructure components can be extensive, reaching multiple terabytes of data per day, but "[m]uch of such data [is] being collected but not used because processing is too costly" (source). Even with the recent advances in "massively distributed smart sensors", infrastructure managers still lack a general computation framework to explore, experiment with and analyze the data. Controls software vendors are driven by the requirements set forth by operators, but these operators' demands are often only responding to what vendors have given them in the past.

Data collection, storage, processing and querying is a general enough task that it could and should be standardized across all areas of infrastructure. Computer systems have converged around a few simple data formats and protocols to ensure interoperability and save time by avoiding re-implementing existing features. A few of these include:

The Hypertext Transfer Protocol (HTTP) for exchanging data between

  remote systems, which contributed to the success of the World Wide Web.

XML and JSON for encoding data into a predictable and quickly

  parseable format, which contributed to the enhanced interactivity of Web
  2.0.

SQL for querying relational databases, which made user customization
```
  possible on the web.
```

HTML, Cascading Style Sheets (CSS) and JavaScript for user interfaces,

  which led the way for browser-based applications like Google Docs.

An example monitoring implementation using these technologies is Nagios, a tool to monitor computer grid infrastructure.

"The Nagios distribution provides only the basic set of sensors, but custom sensors can be developed by using any existing programming language. This means that Nagios can be used for monitoring virtually anything as long as appropriate sensor can be developed." (source)

Nagios provides a uniform interface to the monitored statistics, on top of which any number of processing and analysis applications can be built. Nagios is not intended for the resiliency that something like an electricity grid would require, but many smaller infrastructure projects and those with less critical tasks could likely use this system without modification.

State of the Art

One recent project at the University of California, San Deigo set out to implement an extensible structural health monitoring platform using some of these open technologies. They proposed a system with many components, including:

Networked sensor arrays
A high-performance centralized database
Computer vision analysis
Physics analysis
Visualizations that allow comparison between experimental and numerical simulation data
Modeling and risk analysis

This was an ambitious project, attempted to provide a standard way "to measure, acquire, process, and analyze the massive amount of data that is currently coming on-line (not to mention the terabytes of streaming data that will inundate potential users in the near future) in order to extract useful information concerning the condition assessment of the monitored structures." Unfortunately, the project's web portal is no longer online and no further information about the project could be found. A likely cause of failure is that the system tried to combine too many components into a single piece. Monitoring and data querying is one of the few tasks that can be completely generalized across industries. Considering that computer vision analysis and risk modeling will likely change substantially between a pipeline operator and telecommunications operator, these systems should be left to the various industries to implement as they see fit. As long as the data collection system provides a uniform interface to query the monitoring statistics, it can still be of great value.

SCADA

Supervisory Control and Data Acquisition (SCADA) is an all-encompassing descriptor for real-time communication systems that connect infrastructure to operators. SCADA systems can be uni- or bi-directional - that is they can both send monitoring data back to the operator and propagate control commands to infrastructure. These types of systems are popular in industrial environments as well, as a way to monitor and control heavy equipment.

There are many existing SCADA-style systems (an estimated 150-200 different protocols), dating back to the late 1960's. SCADA is very popular with power utilities as a mechanism for coordinating generation capacity among power plant operators; the generators must react very quickly to changes in load, and an automated communication system is the only way to respond fast enough. In the few first decades of their existence, SCADA systems were primarily developed in-house and extremely customized for specific use cases. As computer software firms spawned in the 1980's and 1990's, more infrastructure operators switched to purchasing their controls software from existing vendors. This has both positives and negatives.

Standard Networking Protocols

In the last 20 years, SCADA software vendors have migrated towards using the standard Internet Protocol (IP) for communication. This is a widely accepted protocol in computing systems, and the success and diversity of the Internet proves its flexibility. The other most popular protocols are DeviceNet and ControlNet.

Previously, operators would find themselves purchasing very large, completely proprietary systems designed to monitor just a single attribute of their system - for example, monitoring electrical power phase. An operator's terminal could be littered with different applications, each for a very specific part of the system. The integration between these components was poor because of the difficulties in sharing data among them.

Once concern with using IP is that now, running on the same network as consumers and potentially malicious attackers, there are additional security risks for a SCADA system, especially when ill-timed or unauthorized control messages could have disastrous consequences.

Standard Interfaces

Familiarizing operators with a SCADA user interface is a critical step in deploying a successful system, and one that was given short shrift in the first few decades of deployment. Along with most of the population of the 1960s, very few operators were familiar with computer interfaces and thus it "was imperative that the [SCADA] operator interface be graphical in nature to provide the dispatchers with a similar look and feel to what they were used to" (source).

Security & Confidentiality

As mentioned, the privacy and security of a SCADA system is especially of concern when using networks shared by others. In general, "[m]onitoring and controlling these systems is an enormous undertaking, requiring constant supervision" (source). They must be architected to avoid cascading failures so connectivity issues in one area of the Internet do not effect the stability of safety of a piece of critical infrastructure. SCADA systems are some of the most diverse and complex integrated systems, commonly containing "as many as 50,000 input/output modules for data collection." Since infrastructure systems are so interdependent, failure or damage in one operator's infrastructure may cause a larger part of the infrastructure to become unstable. Many types of infrastructure are dependent on telecommunications to keep their SCADA systems running, and if standardization and collaboration continues across industries, the integration points will only become more prevalent.

Knowing this, systems using a standard shared network with open protocols are not without fault. They allow for more efficient operation and potentially more collaboration, "but it also exposes the safety-critical industrial network to the myriad security problems of the Internet" (source).

It's important to distinguish between the control and monitoring halves of SCADA, as they have very different security requirements. Some types of infrastructure have a much greater need for control than others, who are satisfied with mostly monitoring. It would be a mistake to require both systems to have the same level of protection (although they both require robustness).

Some common strategies for improving the security of SCADA systems on an open network are:

Make certainly all network traffic is protected using common Internet security measures such as Transport Layer security (TLS)
Establish industry-wide data security practices.
Educate operators on these best practices. Many reported security breaches were the result of operator error.

Openness

Before fretting too much about security and spending additional money, the operators should also consider the true sensitivity of the data they are collecting. The surface appeal for protecting data is great, but often the data would not expose anything a watchful eye could not detect by manual inspection. The true motivation for protecting data may be different. For example, the Federal Energy Regulatory Commission removed previously accessible statistics and documents from their website in the name of security, "but a 2003 investigation strongly suggests that advancing the economic interests of favored industries or keeping executive actions from being scrutinized are the actual motivations" (source).

Operators need a standard and objective process for determining the sensitivity of information, and should err more on the side of release than protection (depending on the risk involved). The reason is that "[r]evealing data on the vulnerabilities of certain kinds of infrastructure can be a net benefit when the target would be inadequately defended absent that revelation. A series of GAO reports about weaknesses in defensive measures at commercial nuclear power plants, for example, played a key role in overcoming industry resistance to stricter security standards" (source).

Computer engineers have long appreciated the massive amount of cognitive power accessible through the Internet, people ready and willing to tackle difficult problems. The same is true for infrastructure issues, and "government officials should release organizational information whenever society is more effective than terrorists at utilizing it". This level of transparency could both force utilities to "internalize more fully the costs of attacks" and encourage more self-interested regulatory action to protect from attack in the first place.

Attacks are so rare that as a private company operating a piece of infrastructure, it doesn't often make business sense to spend money on protection. The government lacks the regulatory power to make these industries account for the full social costs of these events - and up to 90% of the nation's critical infrastructure is privately owned and operated (source). Private industry, even when operating publicly owned infrastructure, lacks strong incentives to properly protect it.

In computing, open source cryptographic algorithms are more trusted and widely used than closed-source proprietary complements because their vulnerabilities have been exposed and patched. They are not more susceptible to attack solely because of increased knowledge of their inner workings. Security by obscurity is insufficient; non-disclosure is almost certainly an admission of the existence of vulnerabilities, but it doesn't guarantee any of them are being resolved.

Non-disclosure risks more than just the reputation of the company in question - it risks public safety and the structural integrity of critical infrastructure. Companies certainly recognize this, and is a part of the reason for protecting data - anything exposed to the government could potentially show up in civil enforcement action against the company.

Of course, there must be a balance between openness and security. Data on nuclear fuel distribution and quantity is protected because of the potentially extreme consequences from unauthorized access. However, the positives of openness and possibilities of early vulnerability discovery likely outweigh any risk in most other industries.

A monitoring system based on open standards could easily support a mechanism to filter and aggregate operating statistics for public consumption. Real-time data will likely always be considered too sensitive, but there should be a clear path from SCADA systems to a more accessible (but still digital) version of the data, one without any extra costs beyond initial setup.

Comparison

This section compares the culture and basic monitoring styles of civil and computer engineering.

Culture

Civil and computer engineers come from different backgrounds and don't have much shared history. The two industries have evolved with very different major players and cultures.

Traditional Civil Engineering Ethos

The first 20 years after monitoring systems were first widely deployed can be described as being embodied by a traditional civil engineering ethos. With the newfound availability of computers and data storage, this was a period of great change in design and planning.

Process & Information Security

From the start, information security was a critical concern for operators. They also intended to keep specific operation process details within a company or industry. These were viewed as details that didn't need to be exposed, for the good of the company and the infrastructure.

Custom Software

Software development was a very new field, and many operators found themselves hiring consultants to develop custom monitoring software for their specific use case. Each operator had slightly different requirements, even within the same industry, and at the start there wasn't much interoperability or data sharing.

Expert Interfaces

For industries with generations of existing workers, there wasn't a clear path to designing proper user interfaces or training the operators. One approach is to make the interface as visually similar to the physical component. Others focused on more tabular displays of data, similar to what was previously a hand-written spreadsheet. In both cases, it often took an expert understanding of the system to be able to interpret the (often terse) monitoring system displays.

Computer Engineering Ethos

At the same time, the computer engineering world was rapidly expanding and in hindsight had a few basic principles.

Openness

In part due to the early ties between computers and academia, some of the first widely used applications were open source - this means that the underlying source code for the system is provided free of charge to view and modify. This allowed new developers to quickly see how existing systems worked, and to assist in the development and expansion of applications.

Standard, open communication protocols also played an important role early on, especially with the development of the Internet. Without a freely implementable communication standard, the World Wide Web could not have succeeded.

Finally, openness has been a core tenant of security from the start of computing. Even today, many large software companies share fine-grained details of the operations of their systems in order to expand knowledge in the field and potentially reap the benefit of open source contributions to their projects.

Humanized UI

User interface design is an important part of everything to do with computers - without the interface, there is very little of interest in networked applications. This is opposed to infrastructure, where the physical components exist in the world regardless of if they are monitored by a communications network.

The interfaces range from technically demanding (like the early civil infrastructure displays) to layman friendly. A core principle is flexibility, however, meaning that with time and effort, almost every system can settle on a good UI.

Modern Civil Engineering Ethos

As SCADA matured over the last 20 years, the ethos of engineers working on monitoring civil infrastructure has changed. Some of the ideas from computer engineering have migrated over, and the further development of a strong software industry improved standards and interoperability.

Industry-level Standardization

Most infrastructure industries have some general standards and guidelines for SCADA systems. Specific software vendors have become more popular in certain areas, meaning that an operator moving from one power utility to another is more likely to find familiar nomenclature and interfaces. For example, in 1993 the American Petroleum Institute issued a set of overall SCADA guidelines to reconcile a huge diversity of interface styles for pipeline monitoring. Infrastructure management is founded on a set of core ideas and tools that can be applied to many different industries with only a few changes (new expert consultants, different Weibull curves, etc.), and the same is true for monitoring systems.

Third-party Software

Most monitoring software is now developed by third-party software vendors such as Seimens and Rockwell Automation. While these systems still have some proprietary components, communication protocol standards now have much more support.

Active versus Passive

Computer network monitoring systems are typically monitoring other software system and the monitoring is inherently very tightly woven with the application itself. This allows for a passive monitoring approach that gathers its data directly from the application, or by politely eavesdropping on network activity. This isn't possible in non-computing infrastructure where the "application" is something physical, without any explicit bits associated with it.

Both types of monitoring accomplish the same end goal, but passive monitoring in computer networks is used primarily in an attempt to lower the performance overhead of monitoring. Civil infrastructure will rarely if ever have the same problem (since wireless sensors can be positioned as to not obstruct normal operation), but the difference could lead to another divergence in monitoring techniques.

User Interfaces

State of UI in SCADA

The purpose of SCADA is to "allow operators to monitor and control systems" (source), so the presentation of data is a critical component that should receive equal consideration with sensor hardware and data security. Unfortunately, this hasn't been the case for many SCADA developers. A 2005 safety study by the National Transportation Safety Board on SCADA for liquid pipelines found that inconsistent and problematic user interfaces were the cause of many accidents, challenging the claims that the systems are a success. The study concluded:

"The principle issue in the SCADA-related accidents investigated by the Safety Board was the delay in a controller's recognizing a leak and beginning efforts to reduce the effect of the leak. SCADA factors identified in these accidents include alarms, display formats, the accuracy of SCADA screens, the controller's ability to accurately evaluate SCADA data during abnormal operating conditions, the appropriateness of controller actions, the ability of the controller and the supervisor to make appropriate decisions, and the effectiveness of training in preparing controllers to interpret the SCADA system and react to abnormal conditions."

This highlights the importance of good interface design, as most of these issues are simply the result of controllers not understanding the information presented to them by the monitoring system. These are operators who interpret a graph incorrectly, dismiss repeated warnings because of frequent false positives, and those who can't get a good sense of the true health of the system in the field based on tabular data.

A screenshot from a SCADA system for monitoring a pipeline (from the NTSB study)

The study examined the role of SCADA systems in 13 pipeline accidents from 1992 to 2004, and found that a SCADA system contributed to the accident in some form in ten of them. Implemented poorly, a monitoring and control system can harm instead of help.

These systems should strive to control as much as is reasonably possible automatically. A common complaint about these systems is that false alarms are so frequent, that operators have a difficult time distinguishing the real alarms when they do occur. These annoying alerts can lead to a serious signal being ignored for a long time by an operator who has tuned them out, or a misdiagnosis of the root cause. As many as possible of these false positives should be handled by a low level of automatic control operations done by the computer, even if it means stopping system components for a brief period when not strictly necessary. Recent research on data center fingerprinting, which identifies new incidents based on data collected during historical events, could be applied to such automatic failure identification and repair. The human operator should be brought into the loop only when a bigger system problem is identified and automated response is not sufficiently subtle or intelligent.

The standardization of colors and symbols within (and even across) industries is also required to minimize re-training and misinterpretation. This hasn't always happened, primarily because a lot of SCADA system development "occurred company-by-company due to the unique characteristics of each company's operating practices and other computer systems. For example, one company may use red to show an operating pump while another may use green" (from the NTSB study). Consistent, appropriate use of color is one of the major tenants of good user interface design and all existing displays should be evaluated to make sure they meet this standard. Other UI improvements that the NTSB suggest are:

Real-time comparison with historical data to recognize abnormalities, especially in areas the operator many not be explicitly trained.
Integrate company safety procedures into control systems to guide operators down the correct resolution path.
Extended operator training - operators should be experts in the system.
Increase contrast between foreground and background colors.
Minimize the quantity of colors and make sure their meaning is consistent between screens.
Target 40% blank space on screens to minimize clutter.

User Interfaces & User Experience

Beyond incremental improvements, civil infrastructure interfaces have a unique opportunity to push the envelope of interfaces. These systems have very wide market penetration, and whatever interface they provide (good or bad) has a tendency to become the industry standard out of familiarity. A potentially more revolutionary interface change could take advantage of an immersive virtual world instead of buttons and charts. Research regarding different physical interfaces for computers, and the effect of integrating virtual elements with the real world found that they can "create a system that leverages the human mind's pattern recognition skills to detect anomalies on a live running network" (source).

Naturally, due to the popularity of computer and video games among computer network operators and researchers, a few attempts have been made to create such an immersive visualization for network monitoring. The primary challenge is to carefully select "input and output metaphors within [the] real time 3D virtual environment," and it proved especially challenging because there is no obvious analogous physical element for network constructs - the activity is all bits flowing on wires. Physical infrastructure monitoring is not bothered as much by this issue, since at the root of most infrastructure monitoring task is some physical object. Metaphors are not required.

An immersive, humanized environment offers more opportunities for pattern recognition of data that would be shown in an unsuitable format on a traditional display. Immersive virtual environments can also improve collaboration between operators. Currently, operators working together on a problem must communicate through voice or video. This is because it's difficult to tell at a glance what an operator is doing at a computer terminal. Inside a virtual world, the operator's current activity and status can be made obvious by the actions of their character. If the operator is opening a valve on the pipeline, they will appear doing just that inside the environment. In the control center, they're sitting in an office chair as always.

Serious Games

The idea of serious games is a good example of a daring use of existing interfaces in a novel way.

"The term serious games has developed as a rebuttal to the idea that games are purely for leisure purposes and its use goes back to Plato's work on the importance of play as a teaching method. Recently, the serious games movement has emerged from academic communities identifying the power of play for supporting non-leisure activities such as education and training." (source)

Beyond training, serious games can also be used for monitoring and interacting with live environments in real-time. Using a first- or third-person viewpoint into a world that looks very similar to the actual physical components is a more natural way to get the sense of a system's status.

A core requirement of an infrastructure monitoring version of a serious game is to avoid simplifying critical components to the degree that accuracy is lost. The interface must certainly contain abstractions, lest it become a micromanagement simulator, but it cannot ignore real-world issues that other training simulations tend to ignore.

Modern Video Games

Thankfully, a lot of work has already been done in developing immersive 3D virtual environments in modern computer and video games. For the purposes of entertainment and creative expression, game developers are creating increasingly detailed worlds. Some of the important features that could be applied to infrastructure management are highlighted by a few recent titles:

Valve's Half-Life 2 (2004) - provides advanced real-time physics simulation that could be used for combining real-time sensor data and prediction models.
Electronic Arts' Mirror's Edge (2007) - includes expansive, detailed urban environments that could be used for building and bridge inspection.
Gas Powered Games' Supreme Commander 2 (2010) - gives top-down strategic control of thousands of military units, which could be used for routing traffic on busy streets, waterways and in the air.
Rail Simulator Development's RailWorks 2 (2010) - gives complete control of accurately modeled passenger and cargo trains. With a connection to a SCADA system, this game could be useful almost out of the box.

Most state-of-the-art game engines (the software that renders the world and controls the behavior of objects in it) are not available to the public directly, but many expose a flexible interface that allows anyone to modify the gameplay. Computer games are often popular well beyond their initial release because of large communities of gamers and developers creating "mods" that twist the game engine into completely new forms. Some examples that suggest the possibilities for infrastructure management mods include:

Gary's Mod (for Half-Life 2) - strips down the game to its core physics engine to allow creating devices as varied as operational submarines, construction cranes and rocket ships.
Empires (for Half-Life 2) - extends the formerly single-play, first-person only game to include a commander with a top-down view of the battlefield who can give orders to players exploring the world. This style of game closely matches the management hierarchy of many infrastructure operators.
BusMod (for Grand Theft Auto 4) - in a game built for causing violent mayhem in an urban environment, this mod highlights a more mundane feature of the city and lets the player drive a bus route.

A few open-source game engines are available, if the modding interface isn't sufficient for any specific monitoring task. Some research has been done on using one of these engines for a computer network monitoring task.

Conclusion

Civil infrastructure is a notoriously underfunded part of our society. The ASCE's yearly infrastructure report cards have been giving failing grades for over a decade, yet overall investment in infrastructure hasn't risen. The improvements proposed in this paper clearly cost money, something which few infrastructure managers have available for non-critical upgrades.

However, remember that the promise of real-time monitoring and SCADA was a decrease in total lifetime cost of infrastructure. This promise was largely fulfilled. With some up-front investment, more efficient operation and monitoring can potentially save a lot of money. After 40 years of SCADA systems, it's time to move into the next major phase of technological advancement, which holds the same cost saving promise. Monitoring systems succeeded, but they risk falling behind like the rest of America's infrastructure without proper consideration.

The next evolution in monitoring must consider the true target of the system: the users. Julian Bleecker's Design Fiction essay gets it right:

"Engineering makes things for end-users. Accounting makes things for markets, demographics and consumers. Design makes things for people."

Engaging interfaces are not reserved exclusively for entertainment and pleasure, and neither is good design.

Massively Distributed Monitoring

2011-05-29T00:00:00-07:00

A PDF of this article is available

Abstract

As the scale of distributed systems continue to grow, the basic question of monitoring the system's status becomes more difficult. How do you monitor an extremely large scale network of nodes without requiring a massive, centralized cluster for data collection?

To monitor these systems from a central location would mean potentially hundreds of thousands of new connections every second, each with a very small update. Persistent connections do not help, since a server cannot maintain that many open connections.

This paper evaluates different approaches to monitoring and describes the implementation of a few novel monitoring techniques in the peer-to-peer video distribution network Astral. Peers in Astral use a self-organized dynamic hierarchy, temporal batching and update filtering to increase the scalability of the monitoring subsystem. Some of the trade-offs associated with these optimizations are also enumerated.

Introduction

Computer system architecture shifted three major times in the past 30 years. Individual, personal computers gave way to mainframes and thin clients. The tide shifted back to powerful end-user clients in the 1990's. Now, the cloud and web services embody somewhat of a throwback to the mainframe era.

A web service is both distributed and centralized - distributed in that the client and server are separated; centralized in that all clients of a particular service connect to the same central hub. In data centers and a few emerging peer-to-peer applications, smaller distributed systems are emerging. The data center ecosystem itself is one massively distributed system, encompassing thousands of nodes across a diverse geography. In short, distributed systems are more common than ever and the importance of monitoring, tracking and accounting hasn't waned.

Problem

As distributed systems become the norm, business process managers are more and more interested in collecting knowledge of the behavior of the system. Planning and marketing are also increasingly data-driven. Each client, server or peer in a system generates potentially valuable usage statistics. System operators want to access this data from the granularity of an individual node up to an aggregate value for the entire system, or a value derived from many statistics.

As the scale of a distributed system increases, the monitoring task can potentially become a burden for an application. The demands and overhead of monitoring can equal or exceed those of the system's normal duties.

A prime example of a problematic monitoring situation is that for large peer-to-peer networks. With lessons learned from the centralization of Napster and the unstructured overlay network of Gnutella, modern peer-to-peer applications like BitTorrent focus on a completely decentralized operation that incorporates a minimal amount of local structure in the network graph. BitTorrent trackers can collect statistics on the files they seed, but statistics for a resource distributed among multiple trackers are difficult to reconcile.

Another example is massively multiplayer online games. Blizzard has a vested interested in tracking the users of their massively multiplayer online game World of Warcraft for billing, game balancing and to plan for future expansions. In order to scale the game world in a reasonable fashion, the developers split up the environment into thousands of shards. The gameplay statistics must make it back to a centralized location at Blizzard eventually, but the fractured architecture doesn't lend itself to a simple solution.

Civil infrastructure monitoring efforts have also encountered these issues. Consider a thousand mile gas pipeline - current monitoring approaches require wireless sensors spaced evenly along the route, which can quickly outpace a large data center in raw number of nodes.

Research Goals

This paper summarizes the challenges with large-scale, distributed monitoring systems and details some accepted solutions and their limitations. To test these ideas, we extended the logging and monitoring functionality of the experimental distributed system Astral.

Astral is a peer-to-peer streaming media content delivery network. The intent of Astral is to leverage the available upstream bandwidth of users watching a live video stream to alleviate the stress (and bandwidth bill) of the stream provider. Instead of all retrieving the video stream from a central location, clients look among network peers for those watching the same event. To match the quality and quantity of metrics available from a centralized system (and demanded by management), Astral must provide detailed usage statistics on the streams and their viewers. Using Astral, we found some of the limits of centralized data collection and tested the feasibility of a more distributed approach.

Definitions

Source / Node - The root source of a statistic, e.g. a user's client connected to the Astral network.
Sink / Collector - The hub for collecting statistics from sources.
Supernode - A parent node in charge of 1 to $n$ child nodes. The leader of a neighborhood of nodes. Typically not specially deployed hardware, but common nodes promoted by the system dynamically.

Monitoring

Metrics

The range of specific metrics that a system designer or operator might like to have is quite wide, and thus a monitoring framework must have a generic, unified interface for specifying the type, number and value of data points. It must be simple to add new metrics for each node, of different types of data.

In the context of an individual node, metrics include:

CPU usage (instantaneous and averaged)
Hard disk usage
Memory usage
Swap space usage
Clock skew
Network throughput
Network latency

One level higher, applications have their own (potentially more interesting) metrics. For some common infrastructure-level components, metrics include:

Database query latency
Database index performance
Database replication status
Task queue failure rates

A peer-to-peer network's metrics include:

Number of peers
Supernode organization
Supernode history
Network membership history for a peer
Specific data requested from the network
Resource available at a peer

The metrics for an online game include:

Individual player playtime
Aggregate player activity
Inter-player transactions
Non-player character spawns
Occurrence of in-game events

The types of civil infrastructure vary widely, but they tend to have close relation to a physical world element and external sensor input. Some sensor data may come in the form of video or images, further complication collection and storage methods. Common infrastructure metrics include:

Temperature
Pressure
Flood gate status (boolean)

Challenges

The world of data center monitoring is changing rapidly. The developers of the popular monitoring tool Ganglia remark that "high performance systems today have sharply diverged from the monolithic machines of the past and now face the same set of challenges as that of large-scale distributed systems."

The variety of systems described earlier are all beginning to look like data centers, and vice versa. The core goal of any monitoring system is a global view of the system for the purposes of health monitoring, performance optimization and accounting. An aggregate global view is more useful in a truly large scale system, where individual node failures are likely masked or handled by efficient failover. Consider that "failure" in a network of cable TV set-top boxes could be a user turning off a power strip each night.

The Ganglia developers suggest that the most important design challenges for a distributed monitoring system are scalability, robustness, extensibility, manageability, portability and overhead. This paper covers three of these in greater detail.

Overhead

Performance overhead can manifest itself on individual nodes or across the network as a whole. The monitoring system must not have a significant effect on the core task of the application, which means it must not consume significant CPU time, perform much disk access, or transfer large amounts of data over the network.

A small network footprint also lends itself to a more dynamic system. The less data that must be transferred, the quicker the operator can view the status of the entire system. Processing data as close to its source as possible can both lessen the network and central collection server load (source). This must not come at the expense of application performance.

What exactly can and should be processed at the point of collection isn't always clear. For aggregate statistics, processing isn't possible without a full (or at least somewhat broad) view of the system. Nodes in a sensor network, oppositely, are able to process raw sensor data into a time averaged, human-parseable statistic before sending. In a general sense, the local processing optimization implies that data should be summarized when and where applicable before being sent to the sink.

Scaling

There are three primary techniques for scaling monitoring systems: hierarchical aggregation, arithmetic filtering and temporal batching. Unfortunately, all three introduce complexity, uncertainty and or delay and can make the system highly sensitive to failure.

Hierarchical Aggregation

One problem for a centralized data sink is the sheer number of updates. A way to alleviate this stress is to aggregate the data from multiple nodes at strategic points in the network hierarchy. The exact size of each aggregated group is configurable, depending the desired load on the collection servers. The collected statistics can either be forwarded along as a batch of individual updates or combined into a single summary value (e.g. average CPU load across a cluster of nodes).

Unfortunately, network failures are amplified in a system with hierarchical aggregation. For example, "if a non-leaf node fails, then the entire subtree rooted at that node can be affected. [The] failure of a level-3 node in a degree-8 aggregation tree can interrupt updates from 512 leaf node sensors." (source)

Arithmetic Filtering

Many metrics change infrequently, so arithmetic filtering can be used to limit the update frequency. After being reported to the sink once, the metric is cached and assumed to remain constant if no further updates are received. This only works for certain classes of statistics (boolean states are a good example), and also introduces ambiguity - it's difficult or impossible to distinguish between a non-reporting node that truly has a constant value and one that has failed. One possible solution for identifying truly failed nodes is to use the existence of other updates from a node as an implicit aliveness update.

Temporal Batching

For statistics that change frequently, but aren't immediately required by the system operator, temporal batching can further alleviate stress on the monitoring system. Either at individual nodes or combined with hierarchical aggregation, the values for a metric over a period of time are batched before being sent to the sink.

Beyond problems associated with the inherent delay in updates, temporal batching makes the system much more vulnerable to networking problems - "a short disruption can block a large batch of updates" (source). Updates can be persisted to a log on disk at each node to make sure they are not lost.

A derived metric called network imprecision (NI) was proposed to account for these variances when viewing system-wide statistics. NI is a "stability flag" that indicates if the underlying network organization is stable, which is a good indicator of the general accuracy of the statistics. To calculate NI, each update from a neighborhood of nodes must include:

The number of nodes who may not be included in this update
The number of nodes who may be double counted
The total number of nodes

This solution for scalability introduces its own scalability issue - the system must report when nodes no longer are reachable, so an accurate accounting of the number of active nodes in the system is required. This will not scale well to a large peer-to-peer network without hierarchical organization and thus, we're back where we started.

Manageability

Manageability deals with both the system's own automated organization as well as that of the humans ultimately consuming the monitoring data. The management overhead must scale slowly with the number of nodes for the system to remain useful.

The management and monitoring tools of large distributed systems have the potential to become more complicated than the applications themselves. Components of the system can be grouped into organizations and split up work in a federated style to alleviate the management stress. The Domain Name System (DNS), for example, operates across thousands of administrative and technical domains by leaving many decisions up to the local administrators.

The Astrolabe project proposed achieving scalability through a hierarchy of zones, each zone consisting of one or more nodes. The zone summarizes statistics into fields of a bounded size - e.g. a count of nodes with a certain property, not a list of their names. The system provides eventual consistency of these aggregate values, which is likely sufficient for many distributed monitoring tasks (especially considering the length of time it takes any action to propagate through an extremely large and diverse network).

State of the Art

As data centers operations matured, monitoring coalesced around a few state of the art tools. This section describes some of the design decisions of these tools.

Storage

Any monitoring activity can generate a significant amount of data, given enough nodes and metrics. Even a single metric, measured often can quickly cripple flat-file storage and traditional databases.

As an evolution from flat-file storage, the designers of CARD choose to use a standard SQL relational database. The motivation was the existing robust query language (SQL), and the ability to modify table definitions after creation. The developers were satisfied with their choice but there are a few issues for a larger scale system. Monitoring data is not especially relational and could better fit in a database intended for simpler data models. A database with map-reduce style querying could also provide a more natural interface. In fact, the designers had to add custom SQL syntax to allow flexible enough querying.

Every monitoring task is going to require this flexibility in data schema and query capability. A database specialized for such flexibility, specifically one of the newer schema-less databases like MongoDB or Redis, is likely a better fit. Non-traditional databases are not new to monitoring - by far the most popular choice, used by both Ganglia and collectd, is RRDtool. RRDtool is a circular database designed specifically for time slice data like monitoring statistics. The operator configures a maximum database size and older data is automatically overwritten in a round-robin fashion to maintain this size.

Operators who wish to archive such data must workaround its cyclical nature by moving weekly or monthly aggregate data to other RRDtool databases, and again to yearly and beyond. These quirks (and its rather slow performance when drawing graphs) make it a sufficient but less than perfect choice.

Finally, CARD only scaled to a few hundred nodes and due to their scale-up (and not scale-out) design, a relational database would likely have a difficult time keeping up if the system were to grow into tens of thousands of nodes.

Collection

The method a system uses for collecting monitored statistics can have a huge impact on its scalability; the two ends of the spectrum are push and pull.

Pull

A pull approach requires the sink to explicitly request each desired data point from the nodes in the system. The sink must poll the nodes at some regular interval if continuous updates are desired. This requires central coordination and registration of all nodes in the system, which is often infeasible, especially in loosely structured peer-to-peer networks.

If the time it takes the sink to cycle through all of the nodes exceeds the polling time, time between polling must be increased (thus losing freshness). Parallel querying can improve this, but only up to a certain point, after which the pull model runs into an issue shared with the push model. Regardless of how often polling can be occur, it is likely that much of the data is duplicated or unchanged. This results in more network traffic than is necessary for freshness.

The pull method is used by the open source monitoring tool Munin, which periodically polls pre-registered nodes to retrieve updates.

Push

A push approach places the burden of sending updates on the end nodes - either sporadically or at a regular interval, they send their updates to the sink identified by a known address. One problem with this approach is management and configuration. The update frequency and sink address are potentially difficult to change as they are distributed among many nodes (possibly not controlled by the operator). The use of a long-lived name and DNS can alleviate address changes, but updating any other settings will require that the nodes occasionally contact a configuration server to synchronize.

The scaling challenges of the push model are very similar to those of running a large web application - the sink must be able to handle a high request throughput, most of them very small write operations. The write-heavy workload is somewhat unique, but not especially challenging for today's databases.

The push method is used by two prominent monitoring tools in the industry, Ganglia and collectd.

Hybrid

A hybrid push/pull gathering style can potentially minimize the duplication of data, maximum freshness and reduce network traffic. From cold start, the sink sends a request for data to each node with an associated count $c$. The node performs as in the push model $c$ times, at which point the sink refreshes the query for another period. This allows occasional configuration changes to happen more naturally, while not introducing constant network overhead (source). The nodes should self-register as in the push model.

At the time of writing this report, there were no widely used systems in the industry that use this hybrid approach.

Similarities to Civil Infrastructure

Interestingly, the shift in data centers to clusters of low to moderately powerful nodes brings the computing world more in line with the monitoring situation in civil infrastructure. Civil engineers and government organizations in charge of projects such as roads, bridges, oil & gas pipelines and waterways have been struggling with monitoring some of the earliest distributed systems. These are not distributed in the familiar computing sense; they are often entirely offline and unpowered. For decades, their data has been gathered (often inconsistently) by hand. The engineers tasked with accounting for trillions of dollars of public assets and physical systems are dealing with what could be viewed as widespread network unreliability and wholly unreliable nodes.

The increasing affordability of small, accurate, low-power sensors greatly interests civil engineers and infrastructure planners as the promise of accurate, fresh data is now realistic. Nearly all new construction comes complete with a range of sensors and a suite of software for monitoring and analyzing the current (and predicted future) state of the piece of infrastructure.

Modern research prefers wireless sensors over wired. These systems are harder to disrupt, which is of greater concern when the system is out in the open and many network hops away from the central office. A widely distributed wired network involves a significant amount of extra infrastructure, and damage to the infrastructure being monitoring often implies damage to the monitoring system itself. Wireless systems have the advantage of being easier to deploy, as they can self-organize into ad-hoc networks as long as they are within range of another sensor node. Connectivity problems also tend to be isolated to individual units, and are easier to troubleshoot.

Recent projects have taken a page (knowingly or not) from tools like Ganglia and now use a unified data format, regardless of sensor or data type. For example, a single update could consist of:

Type of data (1 byte)
Geographic coordinates, determined via GPS or inferred via signal strength of other nodes
Network address
Actual data (4 bytes)

These monitoring networks self-organize into a dynamic hierarchy of nodes based on their placement and capabilities. There are generally three types of nodes deployed:

Basic sensor node
Communication relay node - collects data in its 1- or 2-hop neighborhood
Data Discharge Node - forward results to the Network Control Center, i.e. the one with a connection to the Internet

Whereas in computer system monitoring, each node generally has similar capabilities for communication and sensing, the role of these nodes are bound by their physical capabilities. Hierarchical organization becomes a simpler problem of guaranteeing a wide enough dispersal of communication relay and data discharge nodes to reach all of the leaves of the tree, compared to the somewhat arbitrary trees made in computer networks.

Astral, a Testbed

The major components of the central web application sink and a node in the Astral network. Nodes communicate with one another via HTTP using an embedded web server (the Tornado Python package). The web application that accepts statistics updates is written in Ruby using the Sinatra web framework. The system component for actually streaming video is completely separate - this is based around Adobe Flash's Real-Time Message Protocol (RTMP).

Astral is a peer-to-peer content distribution network specifically built for live, streaming media. Without IP multicast, if content producers want to stream video of live events to users, they are forced to create a separate feed for each user. A peer-to-peer approach is more efficient and offloads much of the work from the origin servers to the edge nodes of the network.

Astral is built on the premise of having knowledge of a virtual overlay network of streaming clients. The system bootstraps itself and obtains this knowledge automatically through messaging among nodes and (to a limited extend) an origin web server. The nodes communicate with HTTP using an embedded web application running on each. They use simple JSON messages over the wire with a standard format for statistics. Each node runs a Python background process and the user sends control messages to it from the browser via simple HTTP requests in Javascript.

Definitions

Stream - A real-time data stream either of a live video source or of a stored recording
Node - A networked computer running the Astral client and connected to the Astral network. The node can be acting as as producer, consumer, seeder, or a combination.

Goals

The primary motivation for Astral is the group project in Carnegie Mellon University's 18-842 Distributed Systems class. A team of four developers (including myself) designed and implemented the peer discovery & organization protocol and streaming video service over the Spring 2011 semester. My own development efforts were also focused on adding a statistics generating and gathering component to the system for the purposes of this paper.

Challenges

In contrast to traditional file sharing peer-to-peer networks, Astral is purpose-built to distribute live media. This prompted some interesting design decisions; for instance, any client inside the network is guaranteed that what they are looking for is widely available. Simply a client's membership in the network is a hint that it has data to distribute to its peers.

Compared to a centralized distribution network, Astral's nodes must pay special attention to reliability. Users expect a steady video stream, even if the quality has to be occasionally reduced due to network congestion. In the centralized architecture, content producers provide reliability by scaling out with additional origin servers. In a peer-to-peer version, the departure of any one client could have a rippling effect on its peers. Astral keeps multiple streams open for the same content to increase robustness, similar to bonding multiple network interface cards together into one IP address.

Because of this resource duplication, the statistics component must take care to deduplicate stream popularity statistics. Each count must be identified with a unique node identifier to avoid counting the backup as well as the primary stream as separate users.

Statistics

The statistics monitored in the Astral network are:

Current (deduplicated) number of nodes watching a stream
Number of nodes acting as seeders for a stream
Bitrate of the stream
IP addresses of nodes watching a stream, for geographic visualization
Network bandwidth of each node

Hierarchical Aggregation

The peers in Astral self-organize into a shallow hierarchy at startup, by going through this process:

Query a central web application for a bootstrap list of supernodes
Determine the round trip time to each supernode as a heuristic to find
```
 the closest
```

 supernode for its lifetime. The relationship is stored persistently and
 survives peer restarts.

All statistics updates from peers are sent directly to their parent supernode, so beyond the initial bootstrapping step (which in total occurs only once per node) there is no load on the central server from individual peers.

The number of peers managed by a supernode is proportional to their available processing capacity, uptime and bandwidth. Long-living peers are obviously preferred to be supernodes to avoid requiring the re-registration of every child node. Each supernode can lessen the load on the sink linear with the number of child nodes registered with it.

Arithmetic Filtering

Astral performs limited arithmetic filtering for the stream viewer statistics. When a peer first requests a stream, that information is propagated back to the sink through a supernode. Once receiving the stream, the peer sends a heartbeat every 5 seconds to its parent supernode. The supernode does not propagate this back to the sink, and thus it assumes that the peer continues to watch the stream. When a peer leaves the network (either notifying the supernode during the proper shutdown procedure or as detected at the supernode by missed heartbeats), the supernode notifies the sink of the change in the peer's status.

This filtering minimizes the number of updates making it all the way back to the sink, but keeps the data as fresh as possible with what are essentially invalidation callbacks (à la AFS). Without this filtering, the sink would have to manage the heartbeats, which could quickly overwhelm the server.

Temporal Batching

The stream provider is generally interested in the average bitrate of video received by the clients, but this information is not required to be completely fresh. Even after the live stream is concluded, this information is useful for provisioning network bandwidth in the future.

Astral takes advantage of this by batching 5 seconds of video bitrate statistics and returning only an average of these values to the sink. The batching is done at the level of individual peers, and in the future could also be performed at each supernode to further diminish the number of updates.

Evaluation

The effects of hierarchy depth and batch window delay on the overall number of update requests in a 100,000 node cluster. The cells contain the total number of requests per second received by the sink.

Depth / Batch Window Size	0	5s	10s	30s
One Level (Baseline Centralized)	100,000	20,000	10,000	3,333
Two Level (1000 supernodes)	1,000	200	100	33
Three Level (10 + 1000 Supernodes)	10	2	1	0.33

The effects of hierarchy depth and batch window delay on the worst case freshness in a 100,000 node cluster. The cells contain the worst possible update delay in seconds.

Depth / Batch Window Size	0	5s	10s	30s
One Level (Baseline Centralized)	0	5s	10s	30s
Two Level (1000 supernodes)	0 + 2 hops	10s	20s	60s
Three Level (10 + 1000 Supernodes)	0 + 3 hops	15s	30s	90s

This graph relates the total number of nodes being monitored with the total number of requests per second that the sink cluster must be able to handle. The vertical axis is logarithmic to accommodate the large range of request rates.

This graph relates the total number of nodes being monitored with the total number of sink servers required to process them, assuming a maximum average of 500 requests per second per sink. The vertical axis is logarithmic to accommodate the large range of request rates.

This graph relates the batch window size (in seconds) with the total number of requests per second, on average, that the sink cluster must be able to handle. The vertical axis is logarithmic to accommodate the large range of request rates.

Astral is obviously a very young project, and quantitative analysis analysis at this point is likely to change quite a bit. However, we can do some basic comparisons between a baseline, completely centralized monitoring system and one with the various improvements discussed. These are currently mathematical projections, with the goal of performing practical tests when Astral's development settles.

Baseline Centralized

With a push-based collection style, the limits of a sink are very similar to that of a modern web application. The most common bottlenecks are:

Throughput & concurrency capabilities of the front-end web server
Throughput of the application server
Performance of web application logic
Database write throughput

A state-of-the-art web application stack geared towards a write-heavy workload could consist of:

Nginx Web Server as the point of entry for requests
Phusion Passenger Ruby application server running 4+ concurrent OS threads
Ruby web application
Redis, a high-performance key-value store

The central web application component of Astral runs on this basic stack, deployed at the moment on the Heroku platform. On an Intel Core 2 2.2GHz processor laptop with 4GB of RAM, the Redis database performs at an average of 40,000 set (i.e. write) operations per second (determined with the redis-benchmark tool, distributed with the Redis server package). A Ruby application in front of the database can server an average of 500 requests per second (and re-implementing the core statistics API in Java or Scala could increase that further) (source).

In order to have fresh information within 1 second, and assuming an average of 1 update per second from each node, the sink must be able to handle $n$ requests per second, where $n$ is the number of nodes in the system. With a cluster of four application servers and one Redis database, for example, the sink could handle updates from a 2,000 node system on average. The statistics in the graphs later in this post for a 1-level hierarchy correspond to this baseline centralized case.

Optimized Distributed

A much larger scale system such as one for streaming the presidential inauguration (during which in 2009, CNN served 1.3 million concurrent streams at the peak) isn't feasible with this linear scaling factor. To handle that many nodes with a centralized sink would require a 2,600 server cluster just for monitoring.

The primary goal of the optimizations discussed in this paper is to lower the rate of updates from each node. Temporal batching like Astral's 5 second buffer lowers the rate by a factor of 5. Hierarchical aggregation lowers it by a factor proportional to the fanout of the supernodes. The effect of arithmetic filtering is more difficult to determine, as it depends on the length of time each node is connected. The longer a node is connected, the more the cost of the single connection request required is amortized. Short-lived clients will cost no more than with a non-filtered approach, and long-lived clients will avoid potentially thousands of requests over a one hour live event.

The first chart below illustrates the effects of both tree depth and batching window size on the total number of update requests received by the sink. Something to keep in mind when adding levels to the hierarchy is the load on supernodes. If these are regular peers in the network, they may not be able to sustain a high rate of requests without impacting the user experience. These projections assume the supernodes are capable of an average of 100 requests per second, and is probably a bit high.

The second chart illustrates the worst case delay experienced due to batching. These projections assume that batching is done at every level (both supernodes and regular nodes). If it only occurs on individual nodes, the delay is never worse than that in a single level hierarchy (plus a negligible amount for the increased number of hops).

The delay from each of these optimizations can be predicted with some confidence. With a two-level hierarchy (a level of supernodes with regular nodes beneath each), the delay for batch updated is equal to the batching duration of each node. A 5 second window avoids a significant number of requests but doesn't significantly delay the data. Other monitoring tasks might be satisfied with even longer delays, up to minutes (note that temporal batching could also be incorporated into a simple centralized collection architecture, with the same benefits). If the supernodes perform their own temporal batching, or there is a deeper hierarchy with additional batch windows, the worst case delay is only the sum of the batching windows along the height of the tree. Delay in one branch has no effect on the freshness of data from another.

A monitoring system with a two-level hierarchy and with a 5 second batching window on average (i.e. some may be delivered closer to real-time than others, based on the operators needs), the same four server sink cluster from the baseline centralized example could handle 1 million nodes (up from 2,000).

Conclusion

We have explored how many types of distributed systems are converging around very similar monitoring challenges, including traditional data center environments, civil infrastructure and peer-to-peer networks. The modern best practices described in this paper for scaling up a monitoring system to thousands of nodes come from the literature and existing systems in many fields and the experience of implementing Astral, a peer-to-peer content distribution network implemented in part to test out these ideas.

Astral as it stands is an incomplete system, and additional work is required before it is production-ready. Its performance and exact approach to monitoring will likely change. The quantitative evaluation of Astral can be extended in future work to determine the optimal values for configurable parameters such as the supernode fanout and batch window.

Monitoring these large systems is an increasingly large task, one that cannot take continue to take lower priority over other application features. Applications stand to benefit from decreased overhead if monitoring can be worked into the system early on in its development, and developers are encouraged to plan the accessible views into their systems as early as possible.

Source Code

Astral is available as an open source project on GitHub.

Acknowledgements

Thanks to the students in the 18-845 course of Spring 2011 at Carnegie Mellon University who kindly review this paper and offered their feedback. Thanks also to Professor David O'Hallaron and Kushal Dalmia for their help with research for the project over the semester.

Data Center Efficiency & Renewable Energy

2011-05-29T00:00:00-07:00

A PDF of this article is available

Abstract

Cloud-based software applications have spurred a renewed interest in thin clients - laptops, smartphones and tablet PCs. The resulting increase in the demand for servers in data centers challenges the current electrical grid, but provides an opportunity to pioneer renewable energy, demand response and distributed generation. Organizational issues hinder immediate improvement, but as the infrastructure costs of information technology firms rise, cooperation with utilities will be an increasingly attractive idea.

Implications of Thin Clients

The software as a service (SaaS) business model is relatively new for application developers and IT firms. Instead of selling packaged software to customers to run on their local computer hardware, SaaS companies provide access to their applications exclusively via the Internet. Any computation required is done by the vendor, on servers they provide. As broadband Internet connection speeds reach more of the population, SaaS has become increasingly popular, and the effect is clear in the hardware purchasing decisions of both businesses and consumers. After years of increasing power in home computers, SaaS shifts the heavy lifting to servers.

In a few ways, SaaS is a throwback to the push for "thin clients" in the 1990's. Thin clients were proposed as low-cost, energy efficient, underpowered machines that would serve as a gateway to applications hosted and run by third parties on Internet servers, or "in the cloud" For whatever reason it failed to take off in the first iteration, the latest push has spurred laptop and smartphone sales, and encouraged new devices like Apple's iPad. Their minimal energy demands are even more attractive in today's energy concious society.

Thin clients use up to 24% less electricity than desktop computers, but some of that efficiency is lost in in the increased demand for servers. (source)

A consequence of the shift is a dramatic increase in the number of servers required to support clients that previously ran their own applications. The type of hardware used for these servers is also quite different that in the last decade. Whereas IBM and Sun Microsystems built their companies with large mainframe servers, they are now sustained by sales and support of volume servers. These are small, inexpensive servers built with commodity parts. Instead of a massive mainframe (a single point of failure for a company), data centers house thousands of rack mounted volume server replacements. A recent report found that "[i]f growth continues in line with demand, the world will be using 122 million servers in 2020, up from 18 million today."

An increase in the number of servers implies a change in the distribution of demand for energy. Processing power is being concentrated in data centers, instead of distributed evenly among all customers. Unless new data centers are strategically planned to optimize energy efficiency, they will burden IT firms with increasing costs, utilities with demand spikes and the environment with increasing emissions. Regulatory agencies, IT firms and public power utilities can cooperate to find an optimal solution that maximizes profit, minimizes emissions, and alleviates some of the problems with young renewable energy sources.

Data Center Efficiency

The costs and demands of data centers can be first viewed at the level of an individual deployment. The site infrastructure capital costs of a data center, separate from any application development, alone accounts for 2/3 of IT costs of a data center (source). These costs as well as emissions are increasing on par with the total number of servers in operation.

This diagram shows projected data center emissions. Volume servers represent the fastest growing segment (source).

Volume servers are substantially more difficult to run efficiently, primarily due to their number. Tracking the energy use of 5 high-end machines is a simpler affair than tracking the use of thousands of volume servers. It is also common for a volume server to run with a small amount of load if it is dedicated to a task with an uneven workload. Similar to power utilities overprovisioning for reliability, servers are overprovisioned to meet their peak demand. Unfortunately, a volume server at 20% load still uses 60-90% of its peak power consumption. In the previous decade, an expensive mainframe would be made to always run at optimal efficiency, as it represented a significant cost and investment. A single inefficient volume server is easy to write off because of the tiny impact, but the combined cost in a data center is high.

The total cost of ownership of a 1U or volume server is almost four times that of the hardware itself and is still increasing, according to the EPA.

The high energy demands and fast growth of data centers prompted the United States Congress to pass Public Law 109-431 requiring the Environmental Protection Agency to report on the current state of energy efficiency in data centers. Among the EPA's findings is the surprising distribution of power within a single data center. Another recent report put data to this fact, not spoken of much outside of IT circles:

"Only about half of the energy used by data centres powers the servers and storage; the rest is needed to run back-up, uninterruptible power supplies (UPS) (5%) and cooling systems (45%)." (source)

Despite the large increase in the number of servers, their individually low power requirements and strides in server energy efficiency mostly mitigate any large increase in power demand. The true effect is the indirect power required to cool the server rooms. This puts data centers more in line with industrial loads, where demand is largely for reactive power. In more detail (from the EPA),

"If the power and cooling overhead needed to support the IT equipment are factored in, only about half the power entering the data center is used by the IT equipment. The rest is expended for power conversions, backup power, and cooling. Peak power usage for data centers can range from tens of kilowatts for a small facility, to tens of megawatts for the largest data centers."

Data centers often perform critical functions for business who are loath to experiment with a system that is working well enough to finish the job. The increased costs are bearable with the subsequent increase in profit due to enhanced availability and features. The EPA found resistance to energy efficiency widespread in IT businesses:

"With the increasing importance of digital information, data centers are critical to businesses and government operations. Thus, data center operators are particularly averse to making changes that might increase the risk of down time. Energy efficiency is perceived as a change that, although attractive in principle, is of uncertain value and therefore may not be worth the risk."

The EPA plans to introduce Energy Star ratings for data centers and their equipment, allowing cost planners to better analyze the total cost of ownership for a server. In combination with increased public pressure for environmental efficiency, the efficiency of data centers should continue to increase.

Virtualization

Even with efficiency improvements, naive data center software will hamper any energy conservation. As consumers are encouraged to shut electrical devices off when not in use, and to hunt down glowing lights and phantom power in their living rooms, a server often burns for them 24/7 to provide on-demand availability.

Server virtualization is a new technique to avoid this symptom. Briefly, virtualization allows many virtual servers be spun up and down dynamically across a smaller number of physical servers. One piece of hardware that was previously leased by a small website can now be used to run 50 small websites with no change for the customer. For example, at night when application activity is low, the servers can be automatically shut down to save power. A small volume website run on a single server can also be scaled up to hundreds in a few seconds if there is a large traffic spike. Utilities such as California's PG & E are offering monetary incentives to remove physical hosts from demand and use virtualization instead. Virtualization allows data centers to aviod the volume server efficiency problem discussed earlier. Virtual servers can be spread across the fewest number of physical machines required, each running at 100% load and thus maximum efficiency.

Location

Location selection is a critical decision for IT companies, regardless of power, because of the sensitivity and security requirements of data and software running inside. They also must consider the added network latency due to the geographic distance between service and client. At the start of the new Internet age, data centers were typically located closed to metropolitan areas to provide the lowest latency to their prime users. Unfortunately, this proved less than ideal as the number of servers grew according to the EPA:

"It is important to note that two of the cities with the highest concentration of data centers — New York City and San Francisco — are geographically isolated areas with relatively limited electricity transmission resources."

Some of the areas of high congestion concern noted by the U.S. Department of Energy are also popular locations for data centers which contribute additional strain to the grid.

A high density strip of data centers mirrors the strip of transmission congestion in the previous figure. (source)

The impact of data center location is less important than it was a decade ago. IT firms are increasing interconnecting their networks (peering) to avoid paying transit costs to the Internet backbone providers, and to create direct links to their customers. These changes, both policy wise and physically, have more effect on latency than data center location. The latency within regions of considerable size is comparable enough to allow more flexibility in locating a data center.

Unfortunately, data center locations are notoriously hard to analyze, as companies are understandably protective of the information. The EPA found that comprehensive data about the locations is not readily available because:

Organizations are concerned about the physical security of these critical infrastructure facilities
Private data centers are seen as a confidential, strategic asset
Many data centers are part of larger commercial buildings and campuses and therefore not separately identified or metered
Data centers have only recently been seen by government agencies as important infrastructure and an indicator of economic activity

While increasing the efficiency of individual data centers reduces costs and increases profits, the environmental impact may be negligible. A recent Greenpeace report found that many new data centers are located next to strong but non-renewable power sources.

"[...] efficiency by itself is not green if you are simply working to maximise output from the cheapest and dirtiest energy source available. The US EPA will soon be expanding its EnergyStar rating system to apply to data centres, but similarly does not factor in the fuel source being used to power the data centre in its rating criteria."

Acting individually, data center operators are encountering the same issue as consumers regarding renewable power sources. The electricity market and Kirchoff's laws dictate that with a general connection to the grid, it cannot be definitively said where the power originated. Data centers must accept a mix of clean and dirty energy sources.

Data centers are typically located near baseload, reliable sources of power. They are increasingly being built outside of metropolitan areas partly in response to the congestion encountered with the earliest data centers. The lower cost of land, construction also contribute to the shift. As long as power and latency are met at an adequate cost level, the location of a data center is relatively flexible. This makes them a good candidate for pairing with power sources that are cost effective only in certain regions. An ongoing issue with wind power is that the wind blows strongest in the central United States, exactly where the demand is the lowest and most spread out. Utilities could work with IT firms to move the load, not the generation.

Common Goals Among Utilities & ITC

The effect of data center growth and location on the power grid and public utilities was one of the items set to be investigated by Public Law 109-431. The EPA was required to analyze "[...] the potential cost savings and benefits to the energy supply chain through increasing the energy efficiency of data centers and servers, including reducing demand, enhancing capacity, and reducing strain on existing grid infrastructure [...]."

The EPA suggested that electric utilities "consider offering incentives for energy-efficient data center facilities and equipment." Data centers represent a significant portion of the load in the United States, so having an open communications channel between the two could benefit both parties. According to the EPA,

"Nationwide, the energy use estimate for data centers translates into a peak load of more than 7 GW in 2007 (equivalent to the output of about 15 baseload power plants), growing to about 12 GW if current growth trends continue."

Many data centers are located near metropolitan areas and contribute to the transmission congestion problems threatening the United States. According to the EPA, "the peak-load reductions achievable through energy efficiency improvements could play a significant role in relieving capacity constraints in these grids."

With server virtualization and given that most major IT firms have multiple data centers among which work is distributed, the demand of any given location could be made highly flexible. When the servers are operating continuously, the load shape of a data center is currently very flat. Some of the efficiency improvements may change that, including the ability to use outside air for cooling and computational load distribution among multiple data centers. Consider a data center handling exclusively non real-time data processing timed to peak at night, located near a wind turbine installation. A coordinated effort between IT firms and power utilities could pair computation load profiles with the best possible generator time profile.

This flexibility, and the requirement of steady power for data centers, offer two additional opportunities for cooperation - demand response and distributed generation.

Demand Response

Due to their requirements for high reliability, data centers are already equipped to resist short interruptions in power supply. The servers are usually backed with a large, UPS (flywheel or large battery) for the entire data center, or individual batteries on each server. With proper incentives, the utilities could use data centers for demand response by switching servers to their backup power source for short periods of time. The EPA's investigation confirms the feasibility of such an idea:

"Although it is often assumed that data centers are not good candidates for load management because of the critical function they perform, high-reliability data centers are in fact designed to continue operating when the power grid is unavailable — using on-site power generation and storage, which suggests that they can also reduce the energy drawn from the grid at times of peak load. "

There would be some additional technical work to implement such a system reliably, as the backup equipment is not intended to be used regularly. The failure rates and repair costs may change if the batteries are discharged often.

These backup batteries also make data centers a good target for renewable power sources like solar and wind, which both have inconsistent time profiles and often generate the most power when it is least needed. Energy storage with compressed air, elevated water or chemical batteries is a promising grid-level solution, and with batteries already in place in data centers, the utility would have smaller startup costs. Fluctuations in generation would matter even less if this was used in combination with a local prime mover generator that was the primary backup for the data center.

Distributed Generation

Some data centers have additional power generation on site for backup and also to alleviate any voltage fluctuations on the grid. Distributed generation is being discussed by utilities, but a large number of private generators are already in operation at data centers. An intelligent connection to the grid is required to bridge between the utilities and these local generators.

"On-site power generation, whether it is an engine, fuel cell, microturbine, or other prime mover, supports the need for reliable power by protecting against long-term outages beyond what the UPS and battery systems can provide. DG/CHP systems that operate continuously provide additional reliability compared to emergency backup generators that must be started up during a utility outage." (source)

Distributed generation applications at data centers include:

Standby/backup power
Continuous prime power
Combined heat and power (CHP)

Renewable generation is often more feasible and less risky at small scale, making distributed generation such as this a good candidate for widespread testing.

Impediments to Implementation & Conclusion

The biggest impediments to adoption are organizational - the complexity and massive scale of the power grid combined with the unwillingness of private, competitive companies to open up what they consider trade secrets make large scale cooperation unrealistic.

The relationship between data center operators, their financial planners and those interested enough in the environment to start a conversation is difficult to predict.

"Many companies, for example, do not know whether a 50% increase in customer volume would require 25% or 100% more server and data center capacity. As a result, data center facilities can sit half empty, particularly just after construction. In other cases, companies find they complete one data center build program only to find, because of capacity constraints, they must launch a new one almost immediately." (source)

Ultimately, what will get companies moving is an opportunity to reduce operating costs of data centers. More and more, they recognize the weight on their balance sheet of the infrastructure demands of SaaS, and only when there is a concise solution to seriously reduce that number will they take action.

Viewing GPX files in Embedded Google Maps

2011-05-28T00:00:00-07:00

While making field recordings for the August 23, 1966 project two years ago, I carried along a small GPS logger. I sat on the resulting GPX file while the project wrapped up, but now that I've posted an in-depth recap of the project I thought linking the location with the audio files would be an interesting experiment.

A quick search led me to Kaz Okuda's project on Google Code, gpxviewer - a perfect match. From the project's page:

The GPX viewer is a 100% client-side JavaScript GPX file viewer that uses Google Maps to map waypoints and tracklogs.

GPX files are a standard GPS data format that is supported by many software applications. It is an XML based data format which lends itself nicely to being parsed in JavaScript.

Since it is written entirely in JavaScript, this script can be added to any web page with minimal effort and little or no server code. Just copy a GPX file to your web site, make a web page with an embedded Google Map, include the script, and initialize it.

The script works fine, but it hasn't been updated since 2007 and is only compatible with the now deprecated Google Maps API v2. I forked the project to GitHub and added support for version 3 of the Google Maps API. I also changed the coding style of the library has been changed a bit, for clarity.

(Kaz, I hope you don't mind - I'd be happy to get this work merged back in with your project. Google Code just doesn't lend itself well to parallel development.)

Usage

With jQuery, using the library is as simple as:

function loadGPXFileIntoGoogleMap(map, filename) {
    $.ajax({url: filename,
        dataType: "xml",
        success: function(data) {
          var parser = new GPXParser(data, map);
          parser.setTrackColour("#ff0000");
          parser.setTrackWidth(5);
          parser.setMinTrackPointDelta(0.001);
          parser.centerAndZoom(data);
          parser.addTrackpointsToMap();
          parser.addWaypointsToMap();
        }
    });
}

$(document).ready(function() {
    var mapOptions = {
      zoom: 8,
      mapTypeId: google.maps.MapTypeId.ROADMAP
    };
    var map = new google.maps.Map(document.getElementById("map"),
        mapOptions);
    loadGPXFileIntoGoogleMap(map, "myTracks.gpx");
});

Source Code

The Audio of August 23, 1966

2011-05-28T00:00:00-07:00

This post is part of a series describing the August 23, 1966 project.

We had two recording sessions for the August project: field recordings for providing ambient sound in the airlock chamber and voice-over recordings for the headset narration and voice commands.

Airlock Ambiance

These recordings were made in and around the University of Michigan campus and in my apartment building, using an M-Audio Nova microphone. I sought out the sounds of wind passing through narrow walkways, the hum of machinery, and other background sounds. Most of the recordings were slowed down quite dramatically.

Title of media

Mission Control Instructions

Visitors to the gallery installation wear a radio headset, and during their trip to space, a voice gives instructions on how and when to move about the exhibition.

These were recorded in my Ann Arbor apartment with an M-Audio Nova microphone, and that's me speaking.

Title of media

Headset Narration

As the visitor's star forms on the Wiremap in front of them, Brian Nord's voice chimes in with occasional narration.

These were recorded in the DL-1 lab at the University of Michigan with an M-Audio Nova microphone.

Title of media

Miscellaneous

Finally, we recorded a few other phrases to throw in to the exhition to give it some spice. Some are pretty silly.

Title of media

The Wiremap of August 23, 1966

2011-05-28T00:00:00-07:00

This post is part of a series describing the August 23, 1966 project.

The Wiremap is an innovative projection technique that displays a 3D image in space using a standard computer projector. The projector throws a beam of light on an array of vertical wires. From the focal point of the projector's lens, all the wires are evenly spaced from one another and have a known distance from the projector. With that information (both a horizontal coordinate and depth), and using some careful calculations on the computer, we can project simple images at various depths in the field. From any perspective other than the projector's position, the wires appear randomly placed and the image becomes visible.

Our implementation uses mason's string for the field, 3/4" plywood for the top and bottom alignment/hanging boards, and standard nuts and washers as anchors for each string. Our map has 256 strings, placed in a randomized dimension of depth through an equal number of holes in both the top and bottom alignment boards. The strings are secured with bolts on the top board and weighted down with a washer below the bottom board. When the top board is raised to 8ft, the wires become taught and can be aligned to a 90 degree angle with the floor. The Wiremap must be calibrated each time the projector is positioned - this includes making sure the wires are parallel, the projector sees the wires evenly spaced, and there is no unnecessary tilt or keystone in the projector's image.

The 256-string Wiremap installed in the gallery.

Wiremap Software Library

In order to facilitate quicker prototyping and make the Wiremap software more accessible to the team, we wrote a Processing library for rendering simple shapes in the Wiremap field. The library improves upon the source code provided by the creator of the Wiremap by reducing code duplication and abstracting most of the implementation details away from a user who wishes to simply draw a sphere, rectangle or sliver in the field. The library also includes a novel calibration method developed in response to inaccuracies in our construction.

The August 23, 1966 logo is actually a sphere generated by this library. Project this image onto our Wiremap, and a three dimensional sphere appears.

Abstraction

The shapes library gathers the coordinate conversion and wire selection math into a single class. The original Processing code required duplicating a set of functions in every Processing sketch that output to the Wiremap. Now, the user creates an instance of the Wiremap class and provides a few key measurements of the physical interface as well as a text file listing the wire depths. The calculation is done as necessary, and not exposed to the user.

Coordinate Systems

One key difference between the original source and the Wiremap library is the coordinate system used for each plane. Previously, the coordinates of X, Y and Z were all physical inches and matched the actual dimensions of the Wiremap. To facilitate quicker transitioning from a regular Processing sketch (using the standard 2D renderer) to one for the Wiremap, the X and Y were changed to be in the standard, Processing-style pixel coordinate system.

The Z plane remains in inches, as there is no obvious relationship between Z space on the screen (which is infinite in both directions) and Z space in the Wiremap field (limited by the physical dimensions). Thus, Z coordinates in the field range from 0 to the field depth.

The library was released under the Apache open source license on GitHub (https://github.com/peplin/wiremap-shapes),

Results

Despite careful planning, we had trouble at the very end of the build phase accurately calibrating our Wiremap. The final transportation from our workspace to the gallery sealed the deal; we were never able to form a satisfactory image in the field after the move.

Continue to the next section, details of the heartbeat monitor.

Twoverse, the universe of August 23, 1966

2011-05-28T00:00:00-07:00

This post is part of a series describing the August 23, 1966 project.

The software core of the August 23, 1966 project is a Java software system named "Twoverse," a parallel universe that exists only in the digital realm.

The Twoverse architecture can be split into three levels - server, client and input. This diagram (full size) includes some unimplemented elements, such as input from a sound sensor.

System Design

The broad concept of Twoverse includes mechanics and partial system specifications for a massively multiplayer online game. The scope was minimized due to time constraints and to better fit the gallery installation. However, even with a smaller scope, a complete vertical slice of the entire system was implemented and used. Downsized from a universe of many types of objects, the system currently supports a universe made of stars with a few properties, and constellations that connect them with meta-objects known as links. Extensibility was considered from the beginning of development, so adding new objects will require a minimal amount of work.

Server

The system relies on a central server to provide the following:

A persistant database of all objects in the universe and their current state, using MySQL
User account management, as well as authenticated session negotiation
A public API for interacting with the universe, via Apache XML-RPC
Client pull style updates for minimizing bandwidth requirements, via an XML feed
A browser based frontend to view the status of objects in the universe, via PHP

Client

Using the XML-RPC API, many types of clients are possible. This includes graphical, text-based, mobile, e-mail, etc. The clients implemented for the gallery installation are graphical clients written using the Processing development environment and include the following features:

Users can scroll and zoom around a graphical universe of glowing stars
Users can click on an individual star to view a close-up view and additional details about its creation and properties
Users can create a new star in the universe, and watch a 3D visualization of their star's formation
Users can draw constellations that connect the stars in the universe, and leave them for other users to see
Users can visit the gallery website to view a table of all of the stars in the universe, their properties and current status

The graphical client uses the XML-RPC API as defined by the server, and updates its local cache of the universe via the server's XML feed.

A screenshot of the star chart in a web browser during the time the gallery was open:

Library

The client and server for Twoverse share many common functions, and were designed to inherit from the same code hierarchy. They both stem from a Twoverse Java library, which includes many utility classes, shared functionality and the server executable. The Twoverse library provides these features and many others:

Database wrapper for a persistent universe - could be used to run SQL database client-side. (Revisiting this, a more established ORM should be used.)
XML-RPC servlet for serving XML-RPC requests
Thread-safe universal object manager for maintaining the state of the universe
User session manager
Small unit test suite for core classes
Processing camera wrapper for simplifying the elusive camera() function
Flexible 2D/3D point coordinate class

Additional documentation is available as Javadoc comments with the source code.

Interface Screenshots

A screenshot of the multi-touch Client with a group of stars displayed at the default zoom level. The lines connecting the stars are constellations drawn by a user.

A screenshot of the multi-touch Client viewing the details of a single star.

A screenshot of the multi-touch Client zoomed in for a closer look at a cluster of stars.

Continue to the next section, details of the multi-touch table.

The Pulse Oximeter of August 23, 1966

2011-05-28T00:00:00-07:00

This post is part of a series describing the August 23, 1966 project.

In researching ways to detect the human heartbeat, we found that photoplethysmography would be the simplest and least expensive way to bring an immediate and personal touch to the gallery installation. A photoplethysmograph is usually obtained with a pulse oximeter - this is the device used in hospitals that grips a person's finger to measure their heart & respiration rates.

Concepts

A pulse oximeter simply illuminates the skin with light from an LED (usually infrared), and measures the luminance of the skin on the other side. Each cardiac cycle brings more blood to the extremities, the finger becomes denser, and thus less light passes through to the detector. When the blood flows away, more light is let through. This fluctuation can be measured and the timing of the luminance peaks used for determining the heart rate.

This project required knowledge of signal processing filters and operational amplifiers. This schematic describes the circut used inside the pulse oximeter. It is also provided as a Fritzing file.

For fun, you can look at the original schematic.

Implementation

This device is advantageous for its low intrusiveness. In our implementation, the visitor just needs to gently place their finger on top of the light sensor. Depending on the person, the shape, rate and range of the photoplethysmograph obtained can vary widely, but we found the results distinct enough to obtain a stable heart rate from most visitors in under 15 seconds.

Our device used the amplified signal of an inexpensive photo-resistor passed through a high pass filter and captured by an Arduino microcontroller. The microcontroller fed an averaged luminosity to a Processing sketch on the host computer, which analyzed the signal for peaks. The peaks were then converted to a frequency, and passed along to the gallery software. The software is general to heart rate monitoring, and can be used for other applications that are interested in the data. There is also a sketch to visualize the value of the pulse oximeter on a graph.

Source Code

Continue to the next section, details of the audio recordings of August.

The Multi-touch Table of August 23, 1966

2011-05-28T00:00:00-07:00

This post is part of a series describing the August 23, 1966 project.

The multi-touch table created for the project is a rear diffused illumination design, and is housed in a core‐ten steel cabinet with recessed cooling fans and an access panel on the rear vertical wall. The touch surface is a 1/2" polycarbonate sheet with an adhesive projection film applied to the underside (acting as a diffuser for the projected image).

Infrared light is projected at the diffuser from below (inside the cabinet) the touch surface. The table used an array of six multiple LED lamps. When an object touches the surface it reflects more light than the diffuser or objects far away from the surface. The change in light is detected by a webcam placed inside the cabinet, and the signal processed by our software as user input.

Multi-touch Software

The multi-touch table used The Beta, from the NUI Group, to process the video stream from the webcam. The Beta, tbeta for short, is an open source tool that analyzes video to find tracking data for objects it recognizes as fingers or cursor devices. The software provides a great deal of control over the video parameters (high-pass filter, amplification, threshold, etc.) that adapts well to many types of multi-touch displays.

Tbeta outputs the tracking data using the TUIO protocol, which is an open framework for receiving input events in various programming environments. For this project, the TUIO events sent by tbeta were received using the open source Java TUIO library in a Processing sketch.

The Twoverse post includes some screenshots of the user interface displayed on the multi-touch table.

Results

Despite careful calibration and testing in our workspace, the final move to the gallery threw the multi-touch table out of alignment and with the remaining time, we were unable to make it sufficiently responsive enough to user interaction. The distribution of IR light on the table's surface was difficult to control, and hot spots had the habit of throwing the exposure of the webcam off and confusing Tbeta.

Although we used the surface as a display, gallery visitors had to use a traditional mouse to interact with the galaxy.

Continue to the next section, details of the Wiremap display.

The Simulated Time of Threephase

2011-05-27T00:00:00-07:00

This post is part of a series describing the Threephase project.

A primary task for any game is making things move. The default approach in a single-player, desktop computer game is somewhat clear. The software has total control over the CPU, and there is only a single player waiting for game world updates. A web-based game needs to optimize for many simultaneous games, while minimizing server costs.

Update Frequency

In a single-player, desktop computer game, it is reasonable to set a small timestep (e.g. 1 second) at each of which the game will recalculate and update the entire world. Powerful processors permit this method to scale up to very large games locally, providing the player with a consistent, up-to-date world.

Unfortunately, this strategy doesn't scale to the web, where a server will have more individual game instances to process and where it is infeasible to dedicate an entire processor to a single game instance at all hours of the day. Thanks to the patterns of web users, there are some relatively easy ways to decrease the amount of work that needs to be done. Updating at a regular timestep would be overeager, when a player typically isn't visiting the web application every second or demanding real-time updates. Users are much more tolerant of short delays (i.e. 1-5 seconds) on the web than in desktop applications.

On-Demand Updates

At the minimum, Threephase updates on demand, only when the player visits their game. To provide background, out-of-band notifications (e.g. e-mails with in-game alerts), however, the game does occasionally need to be updated to check the conditions. Instead of maintaining a steady, short timestep, Threephase gradually decreases the interval between updates as a player stops visiting the game. 12 hours after a visit, the game updates only once an hour. Three days after the last player visit, game updates may be as infrequent as once a day.

Players visiting every day (and by implication those more invested in their virtual world) will receive an appropriately higher update rate, thanks to the processing power left free by those visiting Threephase less often.

Crossing the Day Boundary

The technical impact of this design is that every element of the game needs to be able to update itself over any time interval - 10 seconds, 10 minutes, 10 days. Instead of simply calculating the difference between now and 1 second ago, the objects need to handle updates spanning multiple days. This is important in Threephase because there are certain statistics and calculations that need to occur exactly once per day. That includes:

Calculating the marginal cost curve
Clearing fuel market prices
Storing average marginal price and operating level statistics

The algorithms to calculate these values need to be able to step through the calculation for multiple days, and not condense the change into a single value. For example, if three days have passed since an update, the server must to calculate the marginal price of power on each of the three days, not on average. It is possible to use an integral in some situations where the calculations per day are unimportant, and this method is preferred if possible.

Update Scope

In addition to the question of when to update, the game must decide how much to update. A naive approach is to update every game element, every time, starting from the top of the object hierarchy. This method grows in complexity exponentially as games are created, and does a lot of unnecessary work. It also runs into problems with a fixed timestep - if the work cannot be finished before the next interval (e.g. 1 second), the updates will fall behind and never catch up. Another method is to maintain a list of only the objects that explicitly need to be updated. This avoids duplicated work, but is difficult to maintain.

A representation of naive, update-all approach to game updating. A naive approach to update scope chooses to update every game object starting and the top of the object hierarchy. This approach is not scalable to many simultaneous game instances, especially with short timesteps in between updates.

A representation of improved, list-based update approach game updating. An improved scope for updates maintains a list of specific objects that need to be updated. It saves time and work over the naive approach, but still has difficulty scaling in small timestep situations.

A representation of lazy approach to game updating. A lazy approach to update scope updates objects only on demand from player actions. A request for the operating level of a generator may or may not propagate up the hierarchy of objects, depending on the last update time of each object in between.

Distributed Updates

Threephase uses a distributed update strategy, where updates start at the lowest levels of the hierarchy and propagate upwards only as needed. This approach harmonizes well with HTTP, which is closely tied to a request/response cycle of communication between client and server. For HTTP, there is no concept of a long-running job that continuously updates the game. Clients should also not have to worry about keeping the game state up-to-date.

When a request arrives, the server need only return the best answer it can find, not necessarily the perfect answer. This approach relies on caching at multiple levels of the hierarchy to update the minimum amount of game state necessary to maintain consistency. This frees up processing power for other games, and also increases the response time for players.

Accelerated Game Speed

These update issues are compounded by the fact that games are permitted to scale the passage of time to shorten game duration. Running a power system in real-time speed would be an achingly slow gaming experience, and it would be difficult to observe trends over time. Instead, the time in game can be scaled up as much as 200 times normal. The in-game time is displayed on every page, and begins counting from the epoch of the game. This represents an accelerated view into the future, allowing players to see the near to medium-term implications of their choices.

At the high end of the time scale, update intervals can be especially problematic. At the maximum (200 times real-time), a day passes in game every 12 normal minutes. Nearly every player visit is crossing dozens, if not hundreds of day boundaries. The calculations mentioned must efficiently handle updating a large number of days.

GameTime Helper

To take advantage of the useful time helper methods in both Ruby and the Ruby on Rails web framework, Threephase uses a dynamic GameTime class when dealing with in-game time. The root problem is that given a Time object, the system needs to be able to tell if it has already

Without a steady timestep, all updates must handle the possibility that multiple days have passed since the last update. The lower timeline shows how the day boundary crossing problem is compounded when game speed is increased. been scaled from real-time to game time. A method receiving an instance of GameTime has some implicit metadata (the fact that this is a GameTime, not a regular Time) that the time is already scaled. In addition, the class provides automatic conversion between real and game-time as needed.

Each instance of a Country generates a unique GameTime class definition, with the game's epoch and speed stored as class constants. All times are scaled forward from the epoch (and an error is thrown if a pre-epoch time is passed as an argument), limiting worry about time scaling to a single location in the code base. The class can smoothly convert between scaled game time and unscaled real time.

> game.speed
=> 5
> GameTime = game.time
=> GameTime
> GameTime.epoch
=> Sat, 06 Nov 2010 03:38:49 UTC +00:00
> Time.now
=> 2010-11-06 03:39:10 UTC
> GameTime.now
=> Sat, 06 Nov 2010 03:42:08 UTC +00:00
> GameTime.at(Time.now)
=> Sat, 06 Nov 2010 03:42:43 UTC +00:00
> GameTime.at(Time.now).to_normal
=> 2010-11-06 03:39:45 UTC

Continue to the next section on implementing Threephase.

The Game Objects of Threephase

2011-05-27T00:00:00-07:00

This post is part of a series describing the Threephase project.

The primary geographical units of Threephase are the Country, the State and the City. At any time, there are multiple game worlds running simultaneously. Each game (or Country) has its own unique attributes and available power technologies. The player can choose to either join an existing Country or create a new one (perhaps to experiment with a new regulatory system). A Country's virtual world is ongoing and persistent - players can join and leave at any time.

To join a Country (game and Country are used interchangeably), the player creates a State.

The State is the player's relationship to a certain Country - they can participate in multiple games simultaneously, but with only one State in each game. The player assigns a name, research budget (which effects the cost of new technology) and a map to the new State.

Game/Country

In order to lower the barrier to entry for new players, the player may join and leave games at any time. The time spent finding and joining a game should be minimal. The player should be able to start making in-game decisions as soon as possible to grab and keep their attention. The effects of a State suddenly dropping out of the Country are dampened to not negatively effect the experience for other players when someone leaves the game.

Attributes

A Country has many adjustable attributes that are set at creation. These include, but are not limited to:

Minimum & maximum transmission line capacity
Relative cost of technology
Relative wind speed
Type of economic regulation

The attributes affect the difficulty of the game (e.g. relatively higher capital costs make new construction more difficult) similar to how new laws and public policies can affect power utility strategy in real life. They can also simulate different physical environments, e.g. the relative scale of the average wind speed can make a State more or less inclined to add wind turbines to their generator portfolio.

Economic Regulation

Economic regulation is a critical factor in operating a profitable utility. The available economic regulation types in Threephase are rate of return, marginal cost bidding, and locational marginal pricing (discussed in more detail later on). Power utility regulation is an unsolved problem, and the ability to switch between types in Threephase makes comparing scenarios in different regulatory environments a possible use case.

Map

Each State has a map which defines the land and natural resources underneath and neighboring each City. The proximity of City to areas of the map can have a non-trivial effect on the price of certain types of generation in the City because of the abundance of natural resources (discussed further later).

Multiplayer Elements

Threephase is a multiplayer game. Each Country is shared among the players that control a State in that Country. These players currently share national fuel prices. Generators that use non-renewable fuel purchase their operating fuel at prices determined by a national fuel market. Every day, the market price for each fuel type (e.g. coal, oil, natural gas, etc.) is cleared based on the total demand (the sum of the demand of all generators using that fuel, with respect to their projected operating level) and the total supply (the sum of the availability of the fuel's raw natural resource in the State maps).

To bootstrap the economy, each fuel market is initialized with a starting price (randomized within a pre-specified standard deviation, for variety's sake) and a price elasticity of supply. The supply of fuel does not change since State maps are static in the current implementation, so the price elasticity is used to calculate how the fuel price reacts to changes in demand.

The shared fuel prices mean that a player's decision to build many large coal generators can have implications on the generator portfolios of another player ( who may be less inclined to build coal plants due to the increasing cost of fuel).

State

Within a State, the player has complete control over all generators and transmission lines. The player can view the average cost curve of their generators, graphed in order of their average cost. The ideal, cost-minimizing strategy would run the generators in this order - cheapest first.

Average Cost Curve

Threephase makes a conscious decision to use the average cost curve, as opposed to the marginal cost curve, to attempt to take into the account the capital investment of each generator. This is a deviation from the industry norm, done in part to assist my own understanding.

A common point of confusion for non-experts is how utilities could ever expect to do more than depreciate their equipment while operating at the marginal cost. Different types of regulation attempt to compensate in various ways, most commonly with what are known as capacity payments. These are side payments made by the regulator to encourage re-investment and continued expansion of operations.

Geographic Visualization

The dashboard of each state displays a basic visualization of the State and its Citys. The map also visualizes the composition of the land underneath the State. Each small dot is a Block, and each Block has one of a few different types - mountains, plains or water. Each Block also has an index per natural resource, describing its relative abundance in that area. There are currently indices for the non-renewable resources natural gas, coal and oil and for the renewable resources sun, water and wind. In the current implementation, the block types and indices are chosen randomly. This can be improved using map generation algorithms to create more natural and useful land organization - mountain ranges, rivers, etc.

A screenshot of the State "heads-up display", which shows a map of the natural landscape, where the cities fall in relationship to natural resources, and historical statistics on the price of fuel and electricity.

Location Based Discounts

The location of a City on the map has important implications. Based on the availability of coal within the region, for example, a certain percentage discount is given to coal generators operating in that City. Wind turbines in an area of Blocks with high wind indices will be more effective than in other places.

The discounts are calculated by finding all blocks within a certain radius of the City, scaled based on the population. Larger cities will extend further out from their center point, so they can be expected to utilize a wider area of natural resources.

On the in-game map, the natural resource indices of the land beneath each City can have an effect on the price of local generation. Blocks within a certain radius of a City (green dots within the blue circle, scaled based on population) that contain large amounts of coal or natural gas can make a City a good choice for matching generator types.

Creating Objects

To create a generator, the player selects a GeneratorType from a list of available technologies.

Each Country can customize the list of available GeneratorTypes to simulate different time periods and regulatory environments (e.g. before advanced nuclear or coal with carbon capture and sequestration). The player can compare the available GeneratorTypes based on their attributes to decide which would be the best choice for their portfolio. The current interface is a simple table, sortable by column. Additional comparison visualizations can make the choices easier to understand, and convey some of the issues with new technologies. Lauren Fleishman's work in summarizing and comparing generators is a good inspiration for the user interface.

Generator Type Attributes

The attributes for a GeneratorType loosely belong to three different groups - those that:

Scale the marginal cost
Scale the capital cost
Scale the rate of occasionally positive & negative one-time events

For example, the waste disposal cost effects the marginal cost of power for the GeneratorType. The tax credit lowers the initial capital investment, relative to the size of the generator. The technical reliability effects the frequency of equipment failure, and the technical complexity effects the time it takes to repair a generator once a failure occurs. A complete list is available in the Threephase wiki. Some of the values for attributes were inferred from the U.S. Energy Information Administraton, but others still need to be researched.

Capacity Range

Each GeneratorType also has a range of valid capacities - the number of MWh the GeneratorType can produce at its peak. This range reflects the general capabilities of the GeneratorType, and also its typical applications in real world power grids. For example, gas turbines have relatively lower capacity limits than nuclear generators, and they are typically used as peaking plants (to cover spikes in demand) as opposed to baseload plants which are more efficient in large capacities.

Object Type Extensibility

These attributes and effects are not specific to generators. The objects in Threephase are members of a TechnicalComponent hierarchy, allowing them to share the flexibility enjoyed by generators. Transmission lines, power storage devices, and other component classes all have these attributes.

Generators, transmission lines and power storage devices all inherit from a common parent type - the TechnicalComponent. This allows the game to share code when interacting with each type of object, and still allow for some customization.

In the case of transmission lines, the player can choose from LineTypes such as high-voltage DC and high-voltage AC of varying capacities and resistances.

Most of the attributes are shared with generators through the TechnicalComponent model, but class-specific attributes (e.g. underground v.s. above ground lines) are also supported.

Implementation Note

The relationships are maintained using single-table inheritance (so GeneratorType, LineType and StorageDeviceType share a database table) and polymorphic associations (so a State can reference instances of the three classes in a generic fashion).

Continue to the next section on game mechanics.

The Mechanics of Threephase

2011-05-27T00:00:00-07:00

This post is part of a series describing the Threephase project.

Demand

In a new state, players will see immediately that their power grid is not meeting customer demand. This is critical in power systems, much more so than any other commodity market. Unlike typical consumer product supply and demand, a lack of supply of electricity doesn't generate consumer buzz like a gadget shortage. The system experiences instability and outages fails if demand and generation don't match exactly.

Notifications

Thanks to the way players authenticate with Threephase (with their existing Twitter or Facebook account, using the OAuth protocol), the server can optionally communicate to players out-of-band when such emergency situations arise. Imagine a tweet or Facebook message from Threephase when generation dips dangerous close to or below the level of demand.

Changing Demand

The first solution to not meeting demand, of course, is to build more generators. Not all is perfect, however, as demand is not static. The load of each City (and overall that of the State) changes based on the time of day. Each City has a predefined load profile function, which determines how that City's demand changes during the day. Generally, demand is higher in the afternoon and early evening than late at night. A player's system may be sufficient at 8am, but insufficient later in the day.

The current load profile function is static, and simply scales linearly with the number of customers in a City. In the future, each City could have a more intelligent, varying load profile function. The current function (found by visual approximation) is:

-.1 ∗ ((.42 ∗ Hour - 5)4 ) + 100) ∗ Customers/Constant)

Equipment Failure

In addition to changes in demand, components in the system can also fail due to equipment malfunction, natural disasters or union strikes. The system must have enough capacity to withstand the loss of its largest component - this is known as an n - 1 reliability constraint. As mentioned earlier, the GeneratorType determines the relative frequency and severity of failures. The Country can also enforce stricter reliability constraints (e.g. n - 2) for experimentation.

The parameters for describing these failures - technical reliability (i.e. mean time between failure) and technical complexity (i.e. mean time to repair) - are not the same descriptors used by the electricity industry, but they are more familiar to laypeople and describe similar concepts to the system-wide metrics used by experts (e.g. the system average interruption duration index, or SAIDI). These two attributes determine the frequency at which failures are triggered.

Primary Player Goals

Players of the game have two basic motives:

Generate enough power to meet demand
Route the power generated to the demand

Line Constraints

The requirement to transmit power changes the reality of the operating strategy quite a bit. The ideal system, where generators are operated in order of their marginal cost, becomes impossible when the physical location of generators and customers is considered. The line constraint feature was removed from the list of initial features of Threephase, but it is the next big logical step for simulating reality.

The physical location of load on the grid can make the ideal, cost-minimizing generation scenario impossible. In this example, Titusville has 150MW of demand and no generator, but the only transmission line into the City has a maximum capacity of 50MW. It is impossible to transmit enough electricity to meet demand.

Profit

The true root motive of any utility operator is profit. The ability to make a profit on the system is critical to re-investment in new technology, system upgrades, and investor satisfaction (in the case of investor-owned utilities). This greatly depends on the economic regulatory environment, both in the real world and Threephase. The current implementation supports rate of return and marginal cost bidding regulation.

Simplified Operating Costs

In all of the regulatory environments, the actual cost of operations depends on the operating levels of each generator. In the current implementation, this is set based on the ideal strategy - generators are enabled in order of their marginal or average cost. Transmission line constraints must be completed before a more realistic scenario can be demonstrated.

Rate of Return

Rate of return regulation is the simplest to calculate and understand. The customers payments are simply the total cost of operating the system at the level demanded multiplied by a regulated rate of return (e.g. 8%). This type of regulation is highly desirable for utilities, as players of the game will quickly realize. A guaranteed return on investment is great encouragement for expanding the system to levels beyond what is actually required. The cost of capital in this system is also lowered, as the risk to banks loaning money is low if the debtor is guaranteed a return on their investment by the government.

In real-world rate of return regulation, there is a possibility that investment decisions made by the utility will not be approved by the regulator. In the future, Threephase could add intelligence to its regulating algorithm to reject extraneous investment and equipment purchases.

In the current implementation, approval is always granted.

Marginal Cost Bidding

The next type of regulation is marginal cost, or average cost bidding. This type calculates the average cost curve each day, and the generators "bid in" at their marginal or average cost (a bid price enforced by the regulators). The market price of electricity for the day is set at the intersection of demand that curve. Generators at the intersection price will break even, generators above it will potentially make a profit and those below are operating below their marginal cost and are thus guaranteed to lose money.

In both rate of return and marginal cost bidding, the generator's operating levels are set automatically each day by the server. An optional operating level override is planned for future versions, to allow players to experiment with and view the effects of market manipulation.

Locational Marginal Pricing

The next regulation type to be implemented in Threephase will be locational marginal pricing.

This regulation type depends on determining generator operating levels that respect transmission line constraints. Each City in the State (more generally each node) has a local price, which is affected by the system-wide transmission capacity, cost of local generation and the local demand.

In this example, Titusville has a marginal price of $80 because of its isolation from high capacity transmission lines, relatively high demand and (not pictured) an expensive local generator to make up the difference.

Continue to the next section on in-game time.

Implementation of Threephase

2011-05-27T00:00:00-07:00

This post is part of a series describing the Threephase project.

Test-driven Development

The development of Threephase followed the test-driven design philosophy. This method encourages that before any implementation, a test case is written that exercises a small piece of desired functionality. Initially the test will fail since nothing has been implemented. The implementation goal is to write just enough code to pass the test - providing some degree of certainty in correctness and making sure no more code than is necessary is written. The resulting collection of test cases (the test suite) is also a critical tool for making sure that contributions from the open source community don't break existing features. Each test case also serves as live, runnable documentation of how a class or method is supposed to work.

Unit Testing

At its core, Threephase is a web application using the Ruby on Rails framework. Most of the interesting logic is in the application's models (i.e. the State, Generator, etc.), so there is relatively loose coupling to Rails itself. The test suite uses the RSpec testing framework for its human-readable test cases and strong integration with Rails. To test the standard request/response patterns of the game's API, the project uses a custom set of RSpec feature groups. These can be called like methods in a test case to avoid duplication, e.g.:

describe StatesController do
    before do
        @game = Factory :game
    end

    context "as an admin" do
        before do
            login_as_admin
        end

        it_should_behave_like "standard GET show"
        it_should_behave_like "standard PUT update"
    end
end

This example makes use of the it_should_behave_like feature group ability in RSpec, allowing much of the test logic to be shared among controllers. Object Factories Instead of test fixtures (preloaded database objects), Threephase uses the Factory Girl framework to use object factories in test cases. Object factories are simpler to maintain than fixtures, and minimizes work during development to data models that are in flux.

Graphics

Threephase originally intended to use the Javascript graphics library Processing.js to render the map, charts and graphs in the browser. Upon further investigation, the library seemed to lack helpful charting features that other libraries offered, and the odd support of syntax from the Java version of Processing made using the language somewhat unnatural (a pure Javascript API to Processing.js was discovered later).

Instead, Threephase uses two different Javascript graphics libraries: Raphaël for basic charting and mapping and Flot for the piecewise graph necessary for the average cost curve visualization. Raphaël also has an existing charting extension, gRaphaël which reduced the amount of boilerplate graph code that had to be written.

Performance

The performance of both libraries is very good in modern browsers (performance tested in Mozilla Firefox and Google Chrome). The bottleneck for rendering complex visualizations at the moment is the time in downloading the data required from the server in the background, not rendering.

Database

The majority of the objects in Threephase are stored using the standard object-relational mapping provided by Rails, backed by a PostgreSQL database. The objects in Threephase (and the physical entities in the real world) are highly relational, so this is a good choice not only for the wide support of SQL databases, but because it fits the data model well.

Asynchronous Tasks

The browser-based nature of Threephase rests on HTTP, the most basic web protocol. HTTP has no knowledge of long running processes, and the relationship between a client and the server is finished after a single request/response cycle. There is not an immediately clear way to mesh this with the very demanding interaction required by games.

Motivation

In order to provide reasonable response times, so players don't get impatient waiting for pages to load, the majority of the computation to update the game needs to happen outside of the normal player interaction cycle - whether updating one element or a thousand.

A desktop game may use different threads of execution to make sure a player is never waiting for a network packet to finish downloading, or for a texture to load from the hard drive. In web applications, the server can use asynchronous task queues to accomplish the same thing.

Whenever possible, computation is bundled up into a "task" and queued to run at a later time - ideally as soon as possible, so the player gets updated data, but with no guarantee that it will happen before the server returns a response to the client. If the job hasn't completed, it may return cached data that is valid, but not completely up-to-date. There is a trade-off between performance and liveliness, and in this case player perception of the game's speed is more important than absolutely current information. To accomplish this, Threephase uses the Resque background job library backed by a Redis database.

Task Examples

Examples of work to be done in tasks include:

Charging customers based on their demand and the marginal price
Deducting power grid operating costs over a time period
Handling random events: research advancements that lower capital costs, unionized worker strikes, etc.
Clearing the market price of each fuel

Currently, Threephase only uses one simple task to update the game world. As more update logic is added, they will be done as tasks.

Continue to the next section, an evaluation of Threephase.

Evaluation of Threephase

2011-05-27T00:00:00-07:00

This post is part of a series describing the Threephase project.

The proposed endpoint of this project was a deployed game server with a playable version of Threephase. One of the first tasks to make sure this was accomplished was to define the scope of the game for the initial version. Clearly, there is enough material to extend beyond a two month timeframe. The core logic of the virtual world took longer than expected to implement, and as a result progress fell behind the list of planned features. Threephase is not currently robust enough for a public deployment, and needs additional work to optimize performance and the user interface. The three evaluation criteria from the project proposal were:

Reception among players. Document reactions during beta testing. Is the game captivating?
Conveyance of critical power systems concepts. Is the game a useful teaching aid?
Robustness and scalability of game architecture. Is the system well-designed? Are upgrades streamlined?

The project was not far enough along by the end of the semester to perform user testing, but the introduction of power systems concepts and scalability of the system made good progress.

Design Changes

Threephase evolved from a turn-based game to real-time before the design was finalized. Real-time strategy games are a more natural setting for players, but when the project was proposed the technology for real-time updates in the browser was not mature. While still an emerging technology, recent developments in non-blocking web servers and browser sockets led to a shift in Threephase 's playing style.

Instead of requiring a somewhat complicated system of action points and player turns, the game world is persistent and never stops. This presented some additional implementation challenges, but in the end will be a more compelling interface.

Project Management

The project uses the Lighthouse issue tracking system to track milestones and tasks. The initial schedule planned a milestone every four days. This duration ended up being too short, and did not allow for slippage or early finishes. Week long milestones (for a project receiving 3/4 of the time of its participants) would be a more flexible and realistic time period.

Time Distribution

The time spent on Threephase was tracked over the past two months with the time tracking tool Timetrap. Split into general categories, most of the time was spent on the backend code (which determines the data storage and object interaction). The second most time was spent in testing.

The initial concept of Threephase evolved over the summer months, culminating in software requirements and architecture documents (now in the project's wiki page). The first month of development was spent implementing the core data models, application controllers and basic web views to interact with the game. The second and final month was spent implementing the game logic - maintaining consistency in the virtual world, updating objects and enforcing the different regulatory conditions.

Future Work

Serious Games

Threephase represents a proof of concept of a platform for teaching and experimenting with power system concepts in the context of a familiar game-like interface. The motive roughly follows the ideas behind the Serious Games Initiative (and other, less formal pushes towards games for learning and experimenting).

Serious games try to leverage the immersive power of games for education, for both academics and continued learning. These games also serve as excellent training tools within industry. Instead of building strictly academic simulations, experts can make an approachable game, something that laypeople would be interest in playing and the experts themselves would enjoy outside of a class or job.

Player Responsibility Scope

A core requirement of serious games is to avoid simplifying critical components, which could alienate the experts of the field, while balancing enough au- tomation that newcomers can learn at their own pace. The game needs to be able to adjust the scope of decisions a player must make, and the extent of the complexity they see, in order to allow players to focus on only certain aspects of the system at one time.

Something discovered firsthand over the course of this project is that it can be overwhelming to be responsible for all aspects of the system, coming dangerously close to the micromanagement of resources. The game must balance between system level decisions and real-world issues that high-level simulations often ignore. The player should be able to select from a range of difficulty levels that automate different areas of the system to adjust the difficulty.

Expanded Multiplayer

Collaborative learning is also possible with serious games. In Threephase, each State is run by an individual player, but this could be expanded to allow cooperative play - one player controlling the generators and another the transmission lines. This actually reflects another real-world regulatory scenario, where these areas of the power grid are separated by law into different management entities.

Improvements

There is a long list of features that could be added to Threephase. The most interesting and pressing items are:

Line Constraints & Location Marginal Prices

The implementation of transmission line construction and the respecting of line constraints in determining the operating levels of generators. The game is lacking a key component of real power systems without this. LMP-style regulation depends on this feature.

Avoiding Outages

The consequences for not meeting demand in Threephase are unclear.

The player is warned of the condition and their state essentially freezes in place - customers aren't charged, operating costs aren't deducted, and no power is generated. This is an overly forgiving approach, as there are serious consequences for an outage in the real world ranging from unhappy customers to financial penalties and even eviction from the market.

Players in Threephase are given this great leeway to allow new players a build-up period, where they can build enough generators to meet demand when first joining a game. This phase could be re-worked to occur before players officially join the game and must being running their utility.

Once the game has started and harsher consequences are in place, a more useful warning for players will be that "generation is projected to come dangerous close to not meeting generation," thereby giving the player a chance to resolve the situation before an outage.

Load Profiles & Demand Response

The load profile of each city is static, and varies only linearly with the population. This could be improved not only by introducing more interesting variations, but by incorporating the idea of demand response. If customers are offered time-dependent electricity prices, they (or their networked appliances) can schedule their operating hours to minimize their costs and stabilize the load for generators. For example, electricity is generally less expensive at night due to excess capacity (and can even have a negative price), and customers are unaffected by short voluntary outages of certain appliances.

This feature would require additional intelligence in the load profile algorithm, as its value would be based on price as well as time.

Intelligent Map Generation

The maps assigned to each State must be generated more intelligently, creating a natural a landscape with a relationship between blocks. The current implementation does not allow for realistic groupings of generators around certain resources (e.g. wind farms in a windy area), since the indices can shift dramatically from block to block.

Expanded Multiplayer

The multiplayer aspects of the game could be expanded beyond shared national fuel prices to include interstate trade. Interstate transmission lines are implemented but not exposed to the player in the interface. Fuel contracts and contracts for different on transmission have also been proposed.

Interactive Visualizations

The map and chart visualizations need to be improved to be more accurate, interactive and useful. The map rendering was intended as the primary interface for the game, but sits as a sidebar in the current implementation. It should present a natural way of viewing the geograph of the State and interacting with the generators and transmission lines. Threephase exposes a JSON API for nearly every function of the game, so the possibilities here depend primarily on user experience decisions.

Mobile Client

Because an API already exists, a mobile client would be a good addition to the system, so players can keep track of their power grid without being near a browser.

Threephase - A Browser-based Electric Power System Game

2011-05-27T00:00:00-07:00

This post is part of a series describing the Threephase project.

Threephase is a web browser-based game simulating the electric power generation and transmission system. The project was completed over a two month period beginning in September 2010, to satisfy the graduate project requirement for Master's in Information Networking (MSIN) candidates at the Information Networking Institute of Carnegie Mellon University (CMU).

This article is an abriged version of the final report, reformatted for the web and with some (less formal) comments and reflections added. I've split it up into a few posts:

The primary inspiration for Threephase was the class "The Engineering & Economics of Power Systems" offered at CMU in the Spring of 2010. The class introduced core power system concepts and discussed many of the issues effecting the utilities today. From my perspective as a computer scientist and video gamer, the available computer simulations for learning these concepts had room for expansion and improvement.

The power system is a growing, popular concern of which the complexity is not well understood by non-experts. The simulations and teaching tools currently available aren't sufficiently accessible and modern to attract people from outside the industry. Threephase is an attempt to balance between the artistic, playful and technical elements to create an immersive virtual world for experimentation and learning.

From conception to implementation, the design shifted in a few ways in respose to the demands of the web-based user interface. The nature of the web protocol HTTP also presented unique challenges to a real-time game, and Threephase applies some novel techniques to find scalable solutions.

Source Code

The game's source code is provided under an MIT open source license at GitHub.

Acknowldgements

This project would not have been possible without the assitance of my advisors and professors at CMU. The course I mentioned was taught by: Dr. Lester Lave (who sadly passed away shortly after the completion of this project), Dr. Marija Ilić and Dr. Jovan Ilić.

The advisors for this project in particular were Dr. Jay Apt and Dr. Gabriela Hug.

Current Player Actions & Abilities

In the current version of Threephase, players can:

Create new games and choose attributes for the game
Join existing games that have already started
Build city-local generators from a list of available types and a range of capacities
View marginal price of electricity over time
View marginal cost of each generator over time
View marginal price of each type of fuel

Once the objects are created, the current version of the backend can:

Calculate market price for each fuel based on supply and demand
Automatically assign the optimal operating level for each generator
Order generators based on marginal cost or average cost
Deduct operating costs (cost of fuel, cost of workforce, etc.) over a time period from a player's cash
Add customer payments (based on marginal price of electricity) over a time period to a player's cash
Calculate marginal price for rate of return regulation
Calculate marginal price for marginal cost bidding regulation, assuming a vertical demand curve
Discount generator operating costs based on map geology
Trigger random equipment failures (rate determined by generator attributes) - equipment repair is notably not yet implemented

Background

Now more than ever, the consumption and generation of electricity are on the minds of policy makers and concerned citizens alike. Green power, smart grids, and the renewed popularity of nuclear energy seem like obvious solutions to increasing efficiencies, so the lack of implementation momentum puzzles many people outside the industry. The most (and nearly only) visible change in the past decade to consumers is the shift from incandescent to CCFL light bulbs - hardly revolutionary.

Since the widespread restructuring of the power system in the early 1970's, the complexity of power economics has surpassed the understanding of most people, including the politicians charged with deciding the future of the system itself. The engineering problems are also non-intuitive to those without an electrical engineering background. For example, despite the hype, wind power alone is not the ultimate solution to the world's energy and environmental issues, but this isn't communicated to or well understood by laypeople. There is an opportunity for educating the public and increasing awareness of the tough realities of the power system.

Computer & Video Games

The power system is frequently included in computer and video games, dating at least back to Maxis' SimCity of 1989 (and the version that I played, SimCity 2000). Electricity appears even earlier in board games, where controlling the power & water utilities in Monopoly garnered players a key advantage. More recently, the German board game Power Grid used the power system as its core game mechanic.

Source

Electricity transmission surfaced as a game mechanic in recent computer games as well, such as Darwinia and the new massively multiplayer game Love. In both games, protecting transmission lines from attack and malfunction is a key objective.

Source

On the other end of the spectrum, the current power system teaching tool used at Carnegie Mellon University, Gipsys, excels in the technical but isn't approachable enough to engage those with a passing interest. Since this project started, IBM released a web-based city planning serious game, CityOne, which asks players to make public policy decisions to improve efficiency in their virtual city. IBM's take on serious games is unfortunately less of a challenging, immersive virtual world and more of a marketing tool.

The frequent appearance of the electrical system in games is not a coincidence - the concepts of generation and transmission fit well with strategy gameplay. The games market is ripe for a serious game that combines popular fascination with an idealized power system and the often troublesome state of engineering and economics in the actual industry. This game could be used for both education and casual enjoyment.

Concept

Threephase tries fill the remaining gap, and balance between the artistic, the playful and the technical. A new generation of gamers is being formed online, by the likes of Zynga's Farmville, Frontierville and Mafia Wars. These gamers are comfortable with having a persistent, virtual world in the games they play. They are accustomed to games lasting days or months, and even those without a set endpoint. Unfortunately, few of these games challenge players to learn or think creatively. They are a missed opportunity to show a wide audience the positive effects of gaming firsthand.

The goal of Threephase is to be approachable by a lowest common denominator of people who understand technology, use the web and are willing to play a game (or already do). Each player is handed control of a state-wide utility company and tasked with generating enough power to meet customer demand. Each player operates in a game world shared with other players, where the repercussions of energy decisions in one state can be felt by many others.

Continue to the next section on game objects.

August 23, 1966

2011-05-27T00:00:00-07:00

How do you tell the universe's story as our story? Myth has been intertwining the small and the large for a very long time, with varying degrees of success. Our modern physical cosmology is another mythic story in the suite of human cosmogonies. Though it holds a special place as one that is connected to physical reality, it may be interpreted in many ways. By implementing mechanical and digital interaction technologies, the interpretation can become re-manifestation, where the observer tells a personal story of the cosmos.

In 2009, I along with three teammates at the University of Michigan tried to make sense of that question. We received a grant as a part of the GROCS program, which was started to try and encourage inter-departmental collaboration unified by technology. The team consisted of four people from three departments:

Myself, Chris Peplin (computer science)
Brian Nord (physics, specifically cosmology)
Jiangang Hao (also astrophysics)
John Walters (art & design, specifically sculpture)

In November 2008, we proposed that over the next semester we would:

"[...] explore the possibility of a collaborative universe creation computer game written in Java and Processing. Based on a true to life cosmic starting point, participants can manipulate galaxies and change the laws of physics on the fly. The creator can allow players to catalog and experiment with a shared universe (similar to the game, Spore ) while exploring scientific laws and theories of creation, order, and design."

We named the project "August 23rd, 1966," after the date of the first photograph of the Earth from the far side of the moon by Lunar Orbiter 1.

Our proposal was accepted, and from January to May 2009, we focused our ideas into a three day interactive gallery installation. Visitors could configure and create their own personal star, then witness its birth, life and death in a virtual universe alongside others'.

This writeup is split into a few separate posts:

Gallery Installation

The gallery experience went something like this:

A visitor enters and sees a desktop computer, a multi-touch table and a big black tent. They approach the multi-touch table to view a galaxy of stars. They manipulate the viewpoint, with their hands, and select existing stars to see details of their makeup and date of birth.

The user then selects a location for their own, personal addition to the universe: a new star.

A webcam connected to the multi-touch table automatically configures the temperature (and thus color) of the new star based on the color of the user's clothing. This information is fed over the network to a computer powering a Wiremap, located inside the black tent.

The user dons a radio headset and space helmet (a modified face shield) and steps into an antechamber at the edge of the tent - a simulated airlock. A sound dome suspended from the ceiling fills the room with ambient industrial noise, much like the loud life support systems on the space shuttle. Verbal instructions are piped to the user from the multi-touch table's computer over the radio headset, and a second visitor in the gallery can acts as "mission controller" and communicate via another headset. Much like NASA's controllers in Houston, TX, they do not have the same visuals as the person in the tent.

A voice instructs the user to place their finger on a sensor at the edge of a small black box in the airlock, lit by a single red bulb, in order to check their life signs. (The box is a heartbeat detector and its reading is used to set the oscillation frequency of the new star.)

These events are synchronized with the Wiremap, so when the visitor is informed that the airlock door is unlocked and they enter the darkened tent (simulating the isolation of space), the birth of their star begins in front of their eyes. A new voice on the headset occasionally describes the unfolding sights, and the visitor is free to walk around and examine a kinetic three dimensional representation of their star's creation (a light field suspended on a grid of strings).

After a few minutes, the process is complete and the user is directed to leave the tent and return their helmet. Their star is now a part of a universe shared by all of the other visitors to the gallery. A second computer near the multi-touch table offers a view of the entire universe via a web browser, with instructions on how to keep tabs on stars from home.

This video gives a sense of what the final gallery installation looked like, and hopefully a sense of the experience.

August 23, 1966 from Christopher Peplin on Vimeo.

Abstract

August's installation can be considered a play off of the many-worlds theory - alongside our world, with its crumbling economies and warring nations, there exists a digital universe that is directed by you, the user. Just like in our known universe, many parameters are outside of your control. The interesting part is choosing what you can, timing as you may, and watching the results.

Our intention was to create a multiplayer environment, where visitors to the gallery and online users from elsewhere are interacting in the same virtual universe - we called it Twoverse. Users would begin their experience in the gallery with our unique hardware and visualizations, then continue to monitor the objects they create in a web interface from home.

From a game design perspective, we took into account the potential for replayability of what we were creating. We reasoned there were a few factors that would hopefully give users reason to return to the installation or visit the website:

The excitement of putting your name on a cluster of planets or on a convoy of space vessels destined for Andromeda.
The parental like ownership you may feel watching your star grow up, and the pains in your heart when it dies.
Something to check on for just a few minutes each day, and more potentially intellectually rewarding than fantasy football scores.

Objects in the Universe

We envisioned the universe would start with some phenomena and astral bodies, but the rest was up to the users. There are two different categories of objects, each with a set of parameters configurable by the user: man-made bodies and celestial bodies. These objects span from human scale (single science satellites or cities) up to unfathomably large (galaxy clusters).

Some of the parameters envisioned for satellites include the intended research purse, nationality, speed, orbit and destination. For planets, the parameters could include size, density, composition, orbit and population.

The current version implements a single object: stars, with configurable size and temperature.

Documentation

I've posted more detailed descriptions and documentation for each of the core components of the installation in separate articles.

Reflection

The most important goal to me, and one we did accomplish, was to complete a vertical slice of the entire Twoverse system. Our gallery installation and the hardware and software that supported it touched an amazing number of topics, and I know everyone on the team learned a great deal about their own and one another's fields in the process. During this project, I expanded my knowledge with hands on experience in:

XML-RPC
Java Servlets
Multi-threading and databases in Java
Audio in the Processing environment
Library development for Processing
Multi-touch input processing
Graphics performance optimization
Analog signal processing (filters, opamps)

Future Work

There were a few items left incomplete that I think are interesting enough to mention as possibilities for future work.

Real-time Data Integration

Far from an isolated simulation, this parallel virtual universe could have crossover with our current space (and in real time!). Imagine the Sun in this virtual universe mirroring the solar flares of our own.

The proliferation of real-time data APIs over the Internet present an opportunity for integrating these information into the game. In another example, the user interface could become blurred during periods of high proton wind, or space vehicles and satellites could lose communication and spin out of control.

Twoverse could also bring in factors here that have nothing to do with astronomy in an attempt to relate more directly back to the human scale - e.g. the amount of activity in the gallery could determine properties of some special galaxy cluster, or the people in the room could automatically have an asteroid generated for them.

Time Scales

Time is a big issue with this game, one not sufficiently explored.

The progression of events must be slow enough that you can make some decisions one day, but then you have to wait 24 hours or more for big enough changes to happen. The speed must also be fast enough that we can demonstrate phenomena in a reasonable time span.

Not all of the objects need obey the same time scale, since the goal of Twoverse isn't to be absolutely accurate. The time scale for stars could be greatly accelerated so we can ultimately see them collapse. For space travel, maybe it takes 3 hours instead of 3 days to go from Earth to the moon.

Continue to the next section, details of the software system Twoverse.

Astral - Efficiently Distributing Live Video

2011-05-27T00:00:00-07:00

Astral is a peer-to-peer content distribution network specifically built for live, streaming media. Without IP multicast, if content producers want to stream live events to consumers, they are forced to create separate feeds for each user. A peer-to-peer approach is more efficient and offloads much of the work from the origin servers to the edges of the network.

This project was completed over the course of the Spring 2011 semester in the Distributed Systems (18-842) course at Carnegie Mellon University, taught by Professor Bill Nace. The Astral team included myself, Fabian Popa, Darshana Advani and Anusha Varshney.

This post is a modified version of the final report the team wrote collaboratively and submitted with the project. It has been reformatted for the web, and rewritten/expanded in certain places.

Concept

Live events are an extremely popular motivation for streaming video. President Obama's 2009 inauguration, CNN served a record 21.3 million live video streams , with as many as 1.3 million concurrent connections at the peak.

Looking at the way those streams were provided (i.e. in-browser) and considering related press releases, we can infer that in order to serve such massive amounts of data, providers invariably need to partner with global content distribution networks (CDNs) like Akamai and Limelight. That's potentially an expensive proposition for popular events, although less so than we thought at the start of the project. Amazon recently added live streaming support to their CloudFront CDN at quite reasonable prices, making the added complexity and reliability issues of a peer-to-peer solution somewhat suspect.

The typical centralized streaming architecture depends on a network of geographically distributed edge servers to which the clients connect. Since IP multicast isn't feasible over a WAN (due to the many different router configurations between the source and destination), the stream is duplicated once per end user.

In contrast, a peer-to-peer approach could take the producer's stream and seed it into the network at different (potentially geographically dispersed) points. The stream's consumers could then participate in uploading the data they're viewing to others, using a fairly determined portion of their available bandwidth. A real-world distribution would look much like a telephone fan-out system for school and office closings.

Design & Architecture

Astral is based on a flexible peer-to-peer client application with a few different user interfaces. The two major components are the centralized web application (astral-web) run by the network operator (implemented in Ruby, with Sinatra) and a Python process running on each individual node.

The nodes each run a small embedded web server and expose a simple (currently unauthenticated) ReST API. The API is used for three things:

Inter-node communication
Node to astral-web communication (the Sinatra app implements a subset of the same API)
Communicating with the user interface in the browser (AJAX requests)

A Flash applet in the browser accesses video devices, encodes and finally sends the video into the network using the Real-Time Messaging Protocol. The actual video stream is distributed out-of-band via a chain of TCP tunnels, which connect all of the stream consumers to a Real Time Messaging Protocol (RTMP) server at the source, without ever opening a direct link.

Depending on their configuration, a Python client can act as a stream source, seeder, or consumer (or a combination, bandwidth permitting). The source streams from an external video device through a Flash applet in the browser, which forwards the media stream to the local node and on to the overlay network. The bandwidth limitations of common household Internet connections limit the number of forwarded streams per node to one or two, creating an interesting network graph of consumer chains.

After installing the Astral client, the user visits the URL of astral-web in a browser. This displays a list of all available streams. Each stream has a preview screenshot (not implemented) and metadata, provided by the producer and the source node. When a user selects a stream to watch, the browser communicates their selection to the background process via JavaScript with HTTP requests.

Once the stream is forwarded to the client by at least one other node on the network, the user can view it directly in the browser or in any other streaming media player (by clicking a stream link embedded in the web page).

Node Communication

The Astral client is designed with flexibility in mind. A node can be any of a content producer, consumer or seeder. These three types of nodes make up the clients of the overlay network. The network loosely follows the supernode organization of KaZaa and Skype.

A node announces its presence in the network (and thus its candidacy for stream forwarding) by sending an HTTP POST request to a supernode with itself as the data. When a user requests to watch a stream, the node propagates its interest in this stream through to its neighbor nodes until a node is found that is capable and willing to forward the content (this is somewhat controlled flooding, and the strategy could likely be improved).

When a node leaves the network, it performs a few critical shutdown steps to give other nodes ample opportunity to adjust their stream source or target; it sends HTTP DELETE requests to any nodes to which it is forwarding a stream, any child nodes, and (if it has one) its primary supernode. This keeps data as consistent as possible in the network without the overhead of excessive heartbeat messages.

Communication Design Changes

The original design of Astral planned to use ZeroMQ for inter-node communication. ZeroMQ is message-oriented library that sits on top of TCP sockets to provide very fast messaging between threads, applications and networked machines. Astral requires occasional messaging between peers, and ZeroMQ would have been a good fit.

In the process of implementing the messaging handling code, however, we realized that much of the logic for routing messages is already implemented in widely available web frameworks. Web services that use the Representational State Transfer (ReST) style are also a natural fit for the type of messages that Astral nodes exchange - e.g. creating and deleting nodes, streams and stream forward requests.

With this insight, we replaced the messaging core with an embedded web server (specifically Facebook's Tornado). Each node starts an instance of this server listening on port 8000 at startup, and exposes a simple ReSTful API that accepts and returns data in the JSON format. An additional advantage of this approach is that it enabled Astral to use simple HTTP requests in JavaScript to communicate with the node from a web browser.

(The choice of Tornado was one of familiarity, but it's event-driven nature actually clashes with a few of the Astral API calls. At the moment, it's possible to deadlock two nodes with a specific series of requests. Tornado should be swapped out for a threaded web server.)

Video Streaming

We originally looked at the gstreamer and VLC multimedia libraries, mainly to take advantage of their excellent codec support and stream packaging functionality. Although we were able to get example streams open with both libraries in Linux, it turned out that accessing video devices was not as well supported in OS X (the preferred platform of one of the developers).

Adobe Flash provides better cross-platform device APIs and includes native support for RTMP - these two things made the choice clear for a proof-of-concept. RTMP is an application-layer protocol over TCP with built-in reliability mechanisms (tolerance of lost packets and dynamic packet sizing, negotiated with the server). The stream is encoded with with VP6 video and MP3 audio.

The choice influenced the core design of Astral. We expected to be performing explicit chunking of the stream before sending it off to peers. Since RTMP already provides segmentation and packaging (including meta-information in the header), we were able to benefit from reliability and picture adjustment right out of the box. However, it is arguable that additional reliability guarantees could be achieved in the future by packaging frames directly (e.g. two-stream input on separate paths for immediate failover).

On top of this foundation, we integrated a lightweight Python RTMP server (rtmplite) that acts as a distribution hub for all streams published by the node. All consumers of that stream connect to the corresponding publisher's RTMP server through a dynamically constructed chain of TCP tunnels hosted by network participants.

(This may be a serious bottleneck, considering that all clients still need to connect to a single streaming server. Our understanding of the RTMP server isn't complete enough to say how the bandwidth is conserved in this situation. In the future, a more native streaming solution is probably the best course of action, one that allows more precise control over the video frames.)

In a way, we could look at it as pseudo circuit switching, where you share the connection through the system with others. It is guaranteed that the consumer will get the stream they're viewing over that same connection until a node on the chain of TCP tunnels fails. At that point, Astral immediately tries to reestablish connection by replacing the missing link or potentially constructing a new path.

Reliability

Reliability is of greater concern in a peer-to-peer distribution network. If any point in the chain fails, the consumer loses their real-time stream. There are a few ways around this:

Buffer enough of the stream so that the stream can continue playing while a new source is located.
Always open two connections to the stream, for immediate failover.

Neither is implemented in the current version.

Source Stream Uploading

Astral currently implements source streaming from the browser only. The original design allowed producers to direct any existing streaming device or client at a local TCP socket, but a switch to using the Adobe Flash-based protocol RTMP made this more challenging. Our target external device, VLC, does not currently support sending a video stream to an RTMP server. As planned, the streaming interface is extremely simple; it is very similar to hitting play YouTube. The Flash applet also natively supports streaming from any attached device, be it a USB webcam or Firewire HD camera.

User Interface for Selecting Stream

The user interface for Astral proceeded exactly as planned. It is deployed to a central location, and accessed via a traditional web browser by all clients. After selecting a stream, the user can view the video embedded in the page via a Flash consumer applet. The page also displays the RTMP server's URL, so users can connect with another streaming client if they so choose.

Stream Seeding

Nodes in the overlay network can volunteer to seed a specific stream in order to increase its availability. This requires no special logic - the only difference between a seeding node and a regular consumer is that the seeder does not connect to the stream with a Flash consumer.

Peer-to-Peer Overlay Network Communication

Astral clients bootstrap themselves with knowledge of the overlay network obtain via static configuration files, the origin webserver, and finally, their primary supernode. When a node joins the network, it requests a partial list of supernodes from the origin web application. It selects the closest supernode from this list (based on ping round-trip time) and attempts to register with it. If the supernode is already at capacity (currently a hard-coded limit of 100 children), the node continues down the sorted list of supernodes until one accepts it.

If no supernodes are available or none have capacity, a node promotes itself to supernode status, extending the capacity of the network automatically.

Simulation of Overlay Network

Astral has not been tested in a large-scale, simulated environment as was planned. The system has been tested with a 4-node setup, but needs to be scaled up to flush out issues with the overlay network protocol. A potentially good way to test the system is to load a node with many fake node details via the HTTP API.

Command Line Interface

Astral includes a command line tool for interacting with the local node. This is useful for programmatic integration testing. It controls the node by sending HTTP requests to the same ReST API used by other components. The CLI can display and update stream and node metadata, create new tickets and new streams, and most other node actions.

Challenges & Interesting Bits

Streaming Video

Video streaming is obviously a critical component of the Astral system. We needed to confirm our initial assumptions regarding native multimedia libraries (VLC, gstreamer) much earlier. Native and cross-platform video device access is possible (other applications are able to do it), but we found ourselves in a time crunch by the time we came to testing the capabilities. These turned out to be non-trivial to operate on both Mac OS X and Linux (the operating systems used by our developers). Using Flash and RTMP for video was a good alternative, but compromised the original architecture vision and has its own drawbacks.

Same Origin Policy

The same origin policy was the biggest impediment to implementing the entire UI in the browser.

The switch to a simpler HTTP API for node communication enabled the browser to communicate directly with a locally running node using simple JavaScript. The original plan called for a browser extension, but the switch made this unnecessary.

However, browsers enforce something called the same origin policy, which constrains JavaScript requests to the same domain from which the script was retrieved (it's a good thing in general for security). The Astral interface's JavaScript is retrieved from the origin web server (e.g. http://astral-video.heroku.com), but needs to connect to http://localhost:8000 - a clear violation of the same-origin policy.

Fortunately, we were able to work around this restriction by manipulating URL query parameters and with clever interpretation of the queries on the server side. For extended user interaction, a browser extension may be necessary - these have the advantage of being able to query any domain.

Visualization

We also implemented a JavaScript visualization of nodes, streams and forwarded streams to get a better sense of the state of the system. The visualization opens a WebSocket (a new web technology in modern browsers for persistent, two-way communication between browser and server) with the server, and the server pushes any updates to its knowledge of the network through this connection. The nodes, streams and tickets are drawn on the screen with using the Protovis graphics library.

Interestingly, the visualizations on each node are not identical due to their different viewpoint of the network, and thus incomplete information. Purposefully, none of the nodes has complete global knowledge.

Conclusion

The project proved that distributed distribution is possible, but we found that the costs of centralized distribution aren't as high as we initially predicted (which explains its continued popularity). The additional complexity that comes with distributing via a peer-to-peer network may not be worth the trouble, especially considering the extra challenge with collecting accurate statistics about stream consumers. In the industry, the video distribution company Joost dropped support for their peer-to-peer distribution system in favor of a more traditional, centralized approach with Flash in 2008.

That said, Astral proved to be both a challenging and rewarding proof-of-concept project to learn the complexities of building a peer to peer network, as well as the state of the art in video streaming.

Source Code

Parallelizing the FLAC Encoder

2011-05-26T00:00:00-07:00

A couple of years ago, a friend (Max Miller) and I worked on a project to parallelize the FLAC audio encoder. We modified the official encoder, and while it never made it into the official release, I think some of the ideas are still interesting. I've included the origin report here. You can also jump straight to the code.

Introduction

Our project began with the intention to parallelize the FLAC encoder and create a multi-threaded transcoder (FLAC to MP3) that operated at the audio block level. Upon acquiring the FLAC source code (which includes the C and C++ libraries, flac command line encoder/decoder and some example programs), we realized the need to scale back our expectations of the project. The FLAC API is an extensive, robust library which was built from the ground up, unfortunately, as a serial application.

We spent the first two weeks attempting to understand the flow of the basic flac encoder when dealing with a typical audio file (2 channel, 16-bit WAV). After that, we identified possible points of parallelism at two levels of the encoding process: the high level (the frontend, above the library), and low level (within the library).

This report summarizes the serial algorithm, it's potential for parallelism, and our issues with the library design in implementation. Ultimately, we were successful at parallelizing the algorithm at a high level using a pipeline from Intel's Threading Building Blocks (TBB). This project has definitive implications on the future of the FLAC project, but its integration depends on the evolution of the flac program (which is currently written in C, and thus incompatible with TBB) and the cooperation of the project owner (Josh Coalson) and community.

Serial Problem

FLAC is a lossless audio codec that converts WAV files to compressed FLAC files that are seekable and streamable. A FLAC file contains a stream header followed by a series of audio frames which hold a small piece of the encoded audio along with enough information to decode that frame. The encoding algorithm can be described at a high level in this way:

Read WAV file header and confirm its parameters are compatible with this encoder
Open the output file stream
Write stream header, including metadata such as artist/album information and an MD5 checksum

Finally, do the encoding:

while(blocksLeft) {
    readBlock();
    encodeBlockToFlac();
    writeFrameToOutputStream();
}

Each block of audio is processed in 3 stages.

Inter-channel Decorrelation The encoder decides whether or not to split the audio into channels (left & right), and if so, which method. One option is a simple left/right split, and another (which often garners significant extra compression) is mid and side channels.
Modeling The audio signal is approximately modeled by a function in one of three ways. The function should ideally represent the original audio with fewer bits.
1. Constant signal frames fit to a simple, constant function with only one argument
2. Extremely busy or random frames are modeled verbatim, as themselves
3. All other frames are modeled using general linear predictive coding (LPC)
Residual Coding Once modeled, the model is subtracted from the original audio to produce the residual, or error. This stream is then encoded using Rice codes (a special set of Huffman codes) and run length encoding.

The bulk of the FLAC project is a C library (libFLAC) that implements the codec as per the format specification. There is also C++ library of wrapper classes (libFLAC++). Any actual FLAC encoder or program using the FLAC format must implement the encoding algorithm as described above, using functions provided in libFLAC. The reference encoder in the source, flac, provides one such implementation.

Buffering & Blocking

There are two important considerations regarding speed and compression ratio with the serial problem. There are two buffers - one reads directly from the input file and feeds its data to the second buffer that holds the actual block of audio to be processed. The second buffer is of constant size (one block of samples), but the first is variable. The example encoder frontend reads 1024 samples into the first buffer, and calls the process frame function. That function funnels data from the first buffer to the second, waiting until the second has one full block of audio before actually processing (encoding) the frame. Thus, the variable size of the first buffer is important to consider in relation to available memory, disk read speed and cache size.

Block size is also an important parameter. Similar to thread overhead problems in parallel programming, too small of a block size will lower the overall compression while too large a block will not allow the compressor to generate an efficient model for the audio.

Serial Performance

In terms of real world performance, the FLAC encoder typically encodes a 3-4 minute song in 4-6 seconds which translates into approximately 40 seconds per album. By profiling the reference encoder with gprof, we discovered that 94-98\% of that time is spent within the different variants of process_frame (the middle step of the while loop from above).

Truncated profiling results showing the prime candidates for parallel speedup:

index  \% time  self   children    called     name
                0.00    0.00       1/3080     FLAC__stream_encoder_finish [37]
                0.00   12.99    3079/3080     FLAC__stream_encoder_process [6]
[7]     96.5    0.00   13.00    3080          process_frame_ [7]
                0.00   12.34    3080/3080     process_subframes_ [8]
                0.00    0.47    3080/3080     FLAC__MD5Accumulate [22]
...

Concurrent Architecture

We spent a large amount of time after beginning this project identifying which classes and source files were of interest. We narrowed our modifications down to the example C++ encoder and both the libFLAC and libFLAC++ libraries. At first look, we had no problem finding embarrassingly parallel loops. Many of the functions in the library iterate over large data sets with computationally intensive processes (process_frame, which does the LPC calculations, is a good example). However, many of the loops turned out to usually iterate over much smaller numbers of items than we expected.

After analyzing the actual runtime and size of each loop, our top three parallel plans were:

A 4-6 stage pipeline within process_frame, which is called on each frame.
A parallel_for within stream_encoder_process for a loop that iterates over each sample in the block.
A 4 stage pipeline at the encoder frontend level, mimicking the pseudocode demonstrated in the Serial Problem section.

Our program uses plan 3, because it cleanly separates I/O from computation in a situation very similar Intel's example code for the TBB pipeline. Each frame is processed completely independent of any other, so data dependencies are in theory minimal. Plan 1 is also clearly separated, but the overhead of a pipeline for each frame is too much, and would limit any speedup drastically. We determined that the work in loop of the second plan was ultimately insignificant in comparison to other areas of the encoder.

Pipeline Filters

Before explaining the hazards of this design, we present our pipeline filter plan and the read/write dependencies between each filter. These filters are defined in filters.h, and the type of token passed among them is in pipelinestruct.h.

InputFilter

Read: infile, shared encoder

Write: shared encoder, raw WAV buffer, byte counters

PCMFilter (parallel)

Read: byte counter, shared encoder, raw WAV buffer

Write: PCM buffer

ProcessFilter (parallel)

Read: PCM buffer, byte counter

Write: parallel encoder

OutputFilter

Read: parallel encoder

Write: outfile, shared encoder

Serial Nature

While designing the pipeline, it became obvious that libFLAC was built from the ground up as a serial library. Every function in the library is based the StreamEncoder struct, which stores all information about the audio file, encoding status and state, progress measures and every buffer minus the first, variable sized buffer of raw WAV data. This struct is very convenient in serial, as it imitates object oriented functionality in C. In parallel, the fact that this much state is held by one object severely restricts the parallelism. To solve this problem, we rewrote a handful of library functions to be pipeline-safe. Instead of working on a single encoder struct, they now take two encoder structs as arguments - a shared encoder read by every filter and another encoder mutually exclusive to a token. The motive behind this is to give each pipeline token a unique, local encoder to keep encoding state and buffers. Anytime file metadata or progress counters are requested in a function, they instead read the shared encoder (which is thread safe).

Performance Results

The parallel version compares very favorably to the serial example encoder. Both encoders are still I/O bound at times (especially on large files). CPU usage sometimes drops below 100\%, but this has to do more with buffer sizes than the parallelism. We used a test suite of 6 audio files, which we encoded while timing using the two encoders, then verified by hand that the resulting audio was not corrupted. We saw very large speedups in all of the test cases, which we attribute to the fact that the intense computation is now parallel, and the I/O and computation are also separated into multiple threads by the pipeline structure. File size did not have a noticeable impact on encoding time.

test1.wav (530MB) - Nine Inch Nails - Ghosts, Disc 1
- Quiet, ambient CD with lots of constant and silent frames
test2.wav (584MB) - Nine Inch Nails - Ghosts, Disc 2
- Heavier industrial sound, a good mix of the three frame types)
test3.wav (17MB) - Wolf Eyes - Dead in a Boat
- Noise rock, stress verbatim frames
test4.wav (58MB) - Charles Mingus - Wednesday Night Prayer Meeting
- Acoustic jazz, lots of ambient noise, no silent frames
test5.wav (57MB) - Fiona Apple - Window
test6.wav (22MB) - Tom Waits - Lie to Me
- Electric blues with louder, full frames than the previous track

Results

Run on a dual core AMD Athlon X2 4200+, averaged over 3 runs:

Starting testing...

Encoding ./test1.wav with serial encoder...
average wall time  0m48.408s
Encoding ./test1.wav with parallel encoder...
average wall time  0m27.92s
73% speedup

Encoding ./test2.wav with serial encoder...
average wall time  1m2.962
Encoding ./test2.wav with parallel encoder...
average wall time  0m35.693
76% speedup

Encoding ./test3.wav with serial encoder...
average wall time  0m1.971s
Encoding ./test3.wav with parallel encoder...
average wall time  0m1.118s
76% speedup

Encoding ./test4.wav with serial encoder...
average wall time  0m6.209s
Encoding ./test4.wav with parallel encoder...
average wall time  0m2.963s
109% speedup

Encoding ./test5.wav with serial encoder...
average wall time  0m6.524
Encoding ./test5.wav with parallel encoder...
average wall time  0m2.65
146% speedup

Encoding ./test6.wav with serial encoder...
average wall time  0m1.844s
Encoding ./test6.wav with parallel encoder...
average wall time  0m0.973s
89% speedup

Testing finished.

Average speedup: 94%

Lessons Learned

This project was an immense learning experience for both of us. This is our first time touching a project of this magnitude, and it was eye opening to see their code organization and documentation. We also had to understand automake, and its Makefile generation scripts. We still do not know how to use this tool to its fullest, but we could figure out was very helpful for adding our libraries and new files.

Our confidence in parallel design patterns was strengthened by planning and implementing the encoder. Countless times during the planning stage, something we learned in lecture really solidified in our minds. Examples of this include being wary of thread overhead and watching for blocking I/O. Most importantly, we saw firsthand how very difficult it can be to parallelize code written for serial execution. It is always a better situation to be working with code already optimized for minimum data dependencies. The majority of our time was spent separating the shared and mutually exclusive encoders, and still, there are some issues we have yet to resolve. Namely, the following extra requirements/limitations are placed on the encoder:

No loose mid-side stereo
Verification while encoding
Verification after decoding (using the MD5 checksum)

These are not serious problems, and could be rectified with additional effort. We made a decision to focus elsewhere on this project, as these options eluded complete understanding and aren't common encoding options.

Conclusion

FLAC is an embarrassingly parallel encoder that looked very simple to parallelize. The vast source code made that job much harder, but ultimately there wasn't any more difficulty in the actual parallel design besides for what we anticipated. Intel's Threading Building Blocks freed us up to break down the library into functions we could use without worrying about the details of threads. At the scale of the TBB finger exercise, TBB's usefulness is not entirely clear. Integrated into a large project like this, TBB's algorithms were extremely helpful. We hope to see the library in common use, so a program like this could be distributed.

Our encoder is not full featured. Based on the example C++ encoder, it encodes a very limited subset of the types of files understood by the full-fledged FLAC reference encoder. There is no reason why our pipeline design could not be melded with the robust encoder, but it is beyond the time frame of this class. The reference encoder is a C program, so any further modifications would and should start as a new, C++ reference encoder. Time permitting, we will pursue this idea with the creator of FLAC and search for interested developers in the FLAC community. There are hints of interest in a multi-threaded FLAC encoder on the web, so enlisting the help of other develops should not be impossible with the solid start we've completed already.

Source

Files created or modified in FLAC source:

examples/cpp/encode/file/filters.h
examples/cpp/encode/file/filters.cpp
examples/cpp/encode/file/pipelinestruct.h
examples/cpp/encode/file/main_parallel.cpp
include/FLAC++/encoder.h
include/FLAC/stream_encoder.h
src/libFLAC++/stream_encoder.cpp
src/libFLAC/stream_encoder.c

The patches to the FLAC encoder are available at GitHub.

A PDF version of this post.

References

Standardizing Python Web Application Deployment

2011-05-25T00:00:00-07:00

Deployment is one of the most talked about issues in the Python web application community. Every development shop comes up with their own approach, pieced together with experience and blog posts.

Fabric is often mentioned as the Python alternative to the code deploy tool Capistrano, but there are many more Capistrano plugins and extensions than Fabfiles. One reason for this is a lack of standard application layouts (i.e. where is the WSGI application, the javascript files, list of dependencies, etc.). What if there were a standard convention for organizing and deploying small- to medium-sized applications? We are open-sourcing the configuration we use at Bueda for building and deploying Django and Tornado web applications. There are four related projects that make up the release:

python-webapp-etc - Config files for tools to deploy Python webapps

buedafab (a.k.a. "ops") - A collection of Fabric commands for deployment

django-boilerplate - A standard layout for Django apps

tornado-boilerplate - A standard layout for Tornado apps

I will let the documentation of each individual repository speak for itself. Ideas, comments and contributions are welcome - we hope to come to a community consensus on good standard practice.