CCC Workshop on Global Development:

The Workshop on Global Development was held at the Claremont, Berkeley. Thanks to the CCC funding, we were able to fly 40+ participants and cover all their expenses. Although I was one of the organizers, the views presented here are mine and not of the participants or sponsors.

Background:
Digital technologies have done wonders for mankind. However, benefits of digital technologies (e.g., the Internet) are often limited to the “first world”, leading to the so-called “digital divide”. People in developing regions get access to a decreasing share of digital resources, which are critical for socio-economic development in the 21st century.

The last decade has seen a resurgence of interest in the application of digital technologies to address problems in global development. Eric Brewer’s TIER group at Berkeley is one example. However, this area has not (yet) gained acceptance as core computer science research. There are many reasons for this and the CCR editorial talks about them in detail.

The purpose of the CCC workshop was to bring together lead researchers in the area, along with experts in more established areas, and have a frank discussion about the future of developing regions research. This was a true workshop in the sense that unlike a “mini-conference” there were no PowerPoint presentations. The participants came with a vague idea of what their thoughts were and, after some intense discussion, left with a deeper understanding of the problem and possible solutions. We had to feel the pulse of the audience and adapt the workshop agenda on-the-fly. This was truly exciting.

Highlights of Day 1:

Panel on Technical vs. Non-Technical: Eric Brewer (Berkeley), Kentaro Toyama (Microsoft Research), Tapan Parikh (Berkeley), Bhaskar Raman (ITT-Bombay) went over the “Is ICTD a technical or a non-technical field”. There is a combination of some hard technical problems and some application of existing technologies in new ways. Computer scientists won’t get interested unless the problems are technically hard. The challenge is to either find problems that are both technically hard and can have a real impact or find innovative use of existing technologies that solves problems at large scale i.e., for millions of poor people.

Panel on Starting New Research Areas:
Before more researchers get interested in the area and a plethora of research material is published, we need to step back and learn from history. Deborah Estrin (UCLA), Randy Katz (Berkeley), Gaetano Borriello (Univ. of Washington), and Rakesh Agrawal (Microsoft Research) gave their insights on starting a new field. Deborah talked about her early experiences with sensor networks, Gaetano’s commented on the early days of pervasive computing, Rakesh on data mining and Randy talked about the opportunities and problems facing new fields in general. Food for thought: what is the use of X amount of papers published that all solve a problem Y, which will never actually occur in real life? Ever. I have purposely left out specific views of the panelists from this post. Some information is available from the workshop summary and proceedings, but we decided not to make the workshop minutes public. Feel free to contact me in private, if you want more information.

Keynote – Anil Gupta (Honey Bee Network):
Most of the afternoon was spent on discussing issues like branding, publication venues, funding, and education. And then Anil Gupta gave a very interesting keynote. He showed specific examples of innovation in developing regions, where poor people have engineered technology in various ways to solve their everyday problems. This shows that a) technology, specifically designed for their needs, can help their daily lives and b) people in the developing regions should not only be consumers of such research/products, but can actively participate as innovators themselves. Watch this Discovery Channel video about Honey Bee Network to get an idea of what Anil was talking about:

I must admit that at the end of the first day, everything was unclear. We raised more questions than answers and it was not clear what direction this research community will take. Or if this research community even exists in the first place.

Highlights of Day 2:
We started the day with presenting specific problems in networks/systems, HCI, AI, applications, and software engineering that the participants thought were important problems in the area. This helped to set some “grand challenges” for each sub-area. Frankly, I think most of them were examples of good individual projects instead of “grand challenges”. Nevertheless it helped the participants to get a feel of what research direction each sub-area may take.

Panel on Technology Transfer:
We had a panel on technology transfer with Nathan Eagle (MIT), Umar Saif (LUMS), Jonathan Jackson (Dimagi), and Vijay Chandru (Strandls). Vijay was behind the famous Indian Simputer project and talked about how they went about commercializing the Simputer and what lessons they learned (the image of the left is Vijay holding a Simputer). Umar talked about a startup that provides citizen journalism and another one that is like a SMS-Twitter for Pakistan. He described how these services have helped in disaster situations or how they are providing means for disseminating information in a place where there are often restrictions on the freedom of media. Jonathan talked about the ups and downs of providing healthcare technology solutions in Africa.

New SIG/Conference:
A turning point in the workshop was when Bill Thies presented a proposal for a new ACM SIG. There was unanimous support for forming such a SIG and everyone agreed with the goals and purpose of the SIG. Suddenly, there was a sense of community building. The area now had a name (sort-of) and a SIG to associate with. If developing regions research becomes part of main stream computer science in the coming decades, this exact moment was it’s birth in a way. We went on to discuss the specifics of publication venues (conferences and journals). I don’t want to disclose information about what exactly is happening, but it will be public soon.

Closing & Acknowledgments:
In the closing comments someone emphasized that “let’s not forget that we are all here because we want to touch human lives in someway. What we are doing in the end boils down to the direct impact on the underprivileged. This is the single most important and unique aspect of this area of research.” This thought stuck with me after the event.

I’d like to thank Tapan Parikh (Berkeley), Lakshmi Subramanian (NYU), and Bill Thies (Microsoft Research) for doing all the work. I merely helped in a few tasks here and there.

Eight years later, P2P file sharing is still going strong (now through BitTorrent), while the previously-academic DHTs have found their way into real use.  DHTs now form the decentralized lookup structures for file sharing services—in the form of so-called “trackerless” BitTorrent—with the DHT in the Vuze service comprising more than a million concurrent users.  (As an aside, I’m proud to note that Vuze’s DHT is based on Kademlia, which was proposed by one of my officemates in grad school, Petar Maymounkov.)

These self-organizing systems have also found their way into the datacenter.  One notable example is the storage system, Dynamo, that forms the basis for Amazon’s shopping cart and other back-end  applications.  Or Facebook’s Cassandra, used for its Inbox search.  Or the rest of the key-value stores that do automated partitioning.  And we are starting to see these techniques being proposed for scaling enterprise networks as well.  With that in mind, we wanted to broaden the scope of this year’s IPTPS to include topics relating to self-organizing and self-managing distributed systems, even those running in single administrative domains.

We also plan to have a demo session at this year’s IPTPS to highlight developed and deployed systems.  The workshop will be collocated with NSDI in San Jose, so will be especially convenient for those in the Bay Area.  We welcome submissions (both paper and demos) from researchers, developers, and hackers.  If you don’t want to write a paper, come show off your running P2P system.

Paper submissions are due Friday, December 18, 2009.  More information can be found at http://www.usenix.org/event/iptps10/cfp/.

Call for Papers

The 9th International Workshop on Peer-to-Peer Systems (IPTPS ‘10) provides a forum for researchers to engage in a lively discussion of current and future trends in peer-to-peer systems. Co-located with NSDI ‘10 in San Jose, CA, this one-day workshop provides a venue in which to present and discuss peer-to-peer technologies, applications, and systems and to identify key research issues and challenges that lie ahead.

This year, the workshop’s charter will be expanded to include topics relating to self-organizing and self-managing distributed systems. This is in response to recent trends where self-organizing techniques proposed in early peer-to-peer systems have found their way into more managed settings such as datacenters, enterprises, and ISPs to help deal with growing scale, complexity, and heterogeneity. In the context of this year’s workshop, peer-to-peer systems are defined to be large-scale distributed systems that are mostly decentralized, are self-organizing, and might or might not include resources from multiple administrative domains.

Topics of interest include but are not limited to:

• Network and system support for peer-to-peer systems
• Self-organizing and self-managing distributed systems
• Adaptive algorithms and architectures for large-scale distributed systems
• New applications and protocols for peer-to-peer systems
• Availability, robustness, performance, and scaling
• Security, privacy, anonymity, anti-censorship, and incentives
• Lessons drawn from experience with deployed peer-to-peer systems
• Measurement, modeling, and workload characterization

Papers will be selected based on originality, likelihood of spawning insightful discussion, and technical merit. The program will include presentations of position papers along with plenty of time for lively discussion among the participants, as well as a demo session for working systems.

Important Dates

• Submissions due: Friday, December 18, 2009, 11:59 p.m. EST
• Notification of acceptance: Sunday, February 28, 2010
• Demo proposals due: Monday, March 15, 2010
• Electronic files due: Monday, March 29, 2010

This research opportunity is part of the SCAFFOLD project.  SCAFFOLD is a new network architecture that focuses on better supporting distributed and wide-area services.  These services, run over multiple hosts distributed across many locations, need to respond quickly to server and network churn: both unexpected changes (due to equipment failures and physical mobility) and intentional changes (during planned maintenance, load balancing, and workload migration). SCAFFOLD is exploring network support for treating service-level objects (rather than hosts) as first-class citizens and for providing a tighter coupling between object-based naming and routing.  While the design can support a clean-slate Internet architecture, we are immediately focusing on incremental deployment within a single datacenter or enterprise, as well as across multiple, geo-diverse datacenters.

The postdoctoral associate will provide a leadership role in designing, prototyping, and deploying a SCAFFOLD network.  System components include network-layer devices (OpenFlow-based routers/switches, proxies for backwards compatibility, and NOX-based network controllers), integrated end-hosts, and application-level services to be deployed on top of SCAFFOLD.

Applicants should have a Ph.D. in computer science or a related field at the time of starting the position. They should have a strong research record, as well as first-hand experience building complex networked systems.  Applicants are requested to apply via email (to Jen and myself) with a curriculum vitae and a description of their background and interests. The position will provide a competitive salary and support for further professional development.  Non-U.S. citizens or residents are welcome to apply.  The project is funded through the National Science Foundation, the GENI Project Office, the Office of Naval Research, and Cisco Systems.

One topic that was of particular interest to me were new ideas about datacenter networking; HotNets included two papers in each of two different research areas.

The first thematic area was addressing the problem of bisectional bandwidth within the datacenter. The problem is that each rack in a datacenter may have 40 machines, each potentially generating several Gbps of traffic.  Yet, all this traffic in typically aggregated at a single top-of-rack (ToR) switch, which often is the bottleneck in communicating with other racks.  (This is especially relevant for data-intensive workloads, such as Map Reduce-style computations.)  Even if the ToR switch is configured with 4-8 10Gbps links, this alone can be insufficient.  For example, an all-L2 network, while providing easy auto-configuration and supporting VM mobility, cannot take advantage of this capacity:  Even if multiple physical paths exist between racks, the Ethernet spanning tree will only use one.  In addition, the traditional method of performing L2 address resolution (ARP) is broadcast and thus not scalable.

Multiple solutions to this problem are currently being explored.  In SIGCOMM ‘09 in late August, we saw three papers that proposed new L2/L3 networks to address this problem.  The first two leveraged the locator/ID split, so that virtual resources are named by some identifier independent of their location.

• PortLand from UCSD effectively proposed a NAT layer for MAC addresses.  In Portland, virtual machines running on physical hosts can keep a permanent MAC address (identifier) even under VM migration, but their immediate upstream switch provides a location-specific “pseudo” MAC (the locator). Because these pseudo MACs are allocated hierarchically, they can be efficiently aggregated in upstream switches.  PortLand assumes that datacenter networks have a classic fat tree-like hierarchy between racks of servers, which is the typical network architecture in datacenters.  Instead of routing a packet to a VM’s MAC address, PortLand performs forwarding based on this pseudo-MAC; the VM’s upstream switch NATs between this PMAC and its permanent MAC. No end-host modifications need to be made (although one can certainly envision the host’s hypervisor to perform such NATting on the end-host itself before dispatching the packet to the unmodified VM). The sender is also unaware of this process, as its immediate upstream switch (resp. hypervisor) first translates the destination from MAC to PMAC before sending it out over the datacenter network. The question remains how to discover the MAC-to-PMAC binding, and Portland assumes a centralized lookup controller that stores these bindings and updates them under VM migration, much like the controller in Ethane. (In fact, Portland was prototyped using OpenFlow, which came out of Ethane.)

• VL2 from MSR includes both L2 and L3 elements, unlike Portland’s L2-only solution. Changhoon Kim presented this work; he was a recent PhD graduate from Princeton (and in fact I served on the committee for his thesis, which included VL2). VL2 particularly focused on achieving both high bisectional bandwidth and good fairness between competing flows.    Using data collected from Microsoft’s online services, they found a high degree of variance between flows.  The implications of this is that a static allocation of bandwidth wouldn’t be all that promising, unless one managed to fully provision for high bisectional-bandwidth everywhere, which would be quite expensive. One of the particularly nice things about their evaluation (and implementation)—certainly aided by the support of an industrial research lab!—is that it ran on a  cluster consisting of 3 racks, 80 servers, and 10 switches, so provided at least some limited scaling experience.
  On to specifics.  While Portland used “virtualized” Ethernet identifiers, VL2 assigns “virtualized” application-level IP addresses (AAs) to all nodes.  And rather than performing the equivalent of L2 NATing on the first-hop switches, VL2 uses unmodified switches but modifies end-hosts—in virtualized datacenter environments, it’s not terrible difficult to forklift upgrade your servers’ OS—to perform location-specific address (LA) resolution.  This is the identifier/locator split.  So applications use location-independent IP addresses, but a module on end-hosts resolves an AA IP address to a specific location address (LA) of the destination’s top-of-rack switch, then encapsulates this AA packet within an LA-addressed IP header.  This module also serves to intercept ARP requests for LA addresses and convert ARP broadcasts into unicast lookups to a centralized directory service (much like in PortLand and Ethane).   While this addressing mechanism replaces broadcasts and serves as an indirection layer to support address migration, it doesn’t itself provide good bisectional bandwidth.  For this, VL2 uses both Valiant Load Balancing (VLB) and Equal-Cost Multi-Path (ECMP) routing to spread traffic uniformly across network paths.  VLB makes use of a random intermediate waypoint to route traffic between two endpoints, while ECMP is used to select amongst multiple equal-cost paths.   With multiple, random intermediate waypoints, communication between two racks can follow multiple paths, and ECMP provides load balancing between those paths.  So, taken together, a packet from some source AA to a destination AA will first be encapsulated with the LA address of the destination’s ToR switch, which in turn is encapsulated with the the address of an intermediate switch for VLB.  This is shown in the figure to the left (taken from the VL2 paper). Interestingly, all of VL2’s mechanisms are built on backward-compatible network protocols (packet encapsulation, ECMP, OSPF, etc.).

• BCube from MSR Asia specifically focused on scaling bisectional bandwidth between nodes in shipping-container-based modular datacenters.  This is a follow-on work to their DCell architecture from the previous year’s SIGCOMM.  BCube (and DCell) are, at their core, more complex interconnection networks (as compared to today’s fat trees) for wiring together and forwarding packets between servers.  They propose a connection topology that looks very much like a generalized hypercube.  So we are in fact seeing the rebirth of complex interconnection networks that were originally proposed for parallel machines like Thinking Machine’s CM-5; now it’s just for datacenters rather than supercomputers.  Actually wiring together such complex networks might be challenging, however, compared to today’s fat-tree architecture.

So these proposals all introduced new L2/L3 network architectures for the datacenter.  In HotNets, we saw more proposals for using different technologies, as opposed to new topologies (to borrow a phrase from here):

• A group from Rice, CMU, and Intel Pittsburgh argued that traditional electrically-switched networks (i.e., Ethernet) in the datacenter should be accompanied by an optically-switched network for bulk data distribution.  This proposal takes advantage of reconfigurable optical switches to quickly set up light-paths between particular hosts for large transfers.  So their resulting system is a hybrid:  using electrical, packet-switched networks for small flows or for those requiring low-latency, but using optical, circuit-switched networks for large flows that can withstand the few millisecond delay necessary to reconfigure the optical switches.   And these types of larger flows are especially prevalent in data-intensive workloads (e.g., scientific computing and MapReduce).
• A group from Microsoft Research focused on a similar problem—the paper’s presenter even joked that he could just skip his motivation slides.  But instead of proposing a hybrid electric/optical network, they argued for a hybrid wired/wireless network, where wireless links are used to provide a “fly-way”  between servers.  Instead of using these additional links for large transfers (as in the above proposal), however, this work uses these additional links to handle transient overages on the existing wired network.  Because it’s a wireless network, one doesn’t need to physically wire them up in place; the paper suggests that wireless connections in the 60GHz band might be especially useful given some prototypes that achieve 1-15 Gbps at distances of 4-10m.  The paper also discusses wired fly-ways by using additional switches to inter-connect random subsets of ToR switches, but the talk seemed to focus on the wireless case.

Either way, it’s interesting to see competing ideas for using different technologies to handle bisectional capacity problems (whether transient or persistent).

HotNet’s second thematic area of datacenter network papers considers managing all this new complexity.  There were two papers on NOX, which is a network controller for managing OpenFlow networks.

• The first paper asked the question whether we needed special networking technologies to support new datacenter architectures (the talk focused specifically on the problem of building VL2), or whether we could construct similar functionality via NOX and OpenFlow switches.  They found (perhaps not surprisingly) that NOX could be sufficient.
• The second NOX paper focused on greater support for virtualized end-hosts.  OpenVSwitch is meant to work with various end-host virtualization technologies (Xen, KVM, etc.) and provide functionality for managing their virtual network interfaces (instead of, e.g., Xen’s simple Ethernet bridge).  Openvswitch can be used, for example, to setup particular routes between VM instances or to provide encapsulation and tunneling between VMs.  The latter could enable L3 migration of VMs, with a VM’s old physical location forwarding packets to the VM’s new location (akin to Mobile IP).  Traditional VM migration, on the other hand, uses ARP spoofing and is thus limited to migration between hosts on the same L2 network.

This ability to perform more fine-grain network resource management is very interesting.  While most of these above papers (except the latter one) focus on supporting L2/L3 addressing and connectivity, our own SCAFFOLD project looks at the higher-level problem of supporting wide-area, distributed services.   Distributed services typically scale-out by replicating functionality across many machines; for customer-facing services, some combination of additional mechanisms are used for server selection and failover:  DNS, BGP tricks and IP anycast, VRRP, VIP/DIP load balancers, ARP spoofing, etc.  All this complexity is because, while clients are trying to access replicated services, the Internet provides communication between unicasted hosts. Thus, SCAFFOLD explores building a network architecture that supports communication between services, instead of network interfaces, and that explicitly supports churn (whether planned or unplanned) amongst the set of end-hosts composing that service. I’ll expand on SCAFFOLD’s motivation and design more in a future post.

Conflating naming, location, and authorization, browsers use domains for three purposes:

1. Domains provide a human-readable name for what administrative entity a client is interacting with (e.g., the “common name” identified in SSL server certificates).
2. Domains specify where to retrieve content after they are resolved to IP addresses (through DNS).
3. Domains specify what security policies to enforce on web objects and their interactions, especially as it relates to browser Same Origin Policy (SOP).

CoralCDN’s domain manipulation clearly focuses on the location/addressing aspect of web objects (#2).  And while it has generated abuse complaints given its naming (#1)—either from sites complaining about “illegal mirroring,” third-parties mistakenly issuing DMCA take-down notices, or from those fearing phishing attacks—its most serious implications apply to browser security (#3).

The Same Origin Policy in browsers specifies how scripts and instructions from an origin domain can access and modify browser state.  This policy most significantly applies to manipulating cookies, browser windows, frames, documents (through the DOM), as well as to requesting URLs via an XmlHttpRequest. At its simplest level, all of these behaviors are only allowed between resources that belong to the identical origin domain.  This provides security against sites accessing each others’ private information kept in cookies, for example.  It also prevents websites that run advertisements (such as Google’s AdSense) from easily performing click fraud and pay themselves advertising dollars by programmatically “clicking” on the advertisements shown on their site.  (This is enforced because advertisements like AdSense are loaded in an iframe that the parent “document”—the third-party website that stands to gain revenue—cannot access, as the frame belongs to a different domain.)

One caveat to the strict definition of an identical origin (per RFC-2965) is that it provides an exception for domains that share the same domain.tld suffix, in that www.example.com can read and set cookies for example.com.  Consider, however, how CoralCDN’s domain manipulation effects this.  When example.com is accessed via CoralCDN, it can manipulate all nyud.net cookies, not just those restricted to example.com.nyud.net.  Concerned with the potential privacy violations from this, CoralCDN does not “support” cookies, in that its proxies delete any Cookie or Set-Cookie HTTP headers.

Many websites now manage cookies via javascript, however, so cookie information still “leaks” between Coralized domains on the browser. This happens often without a site’s knowledge, as sites commonly use the URL’s domain suffix without verifying its name. Thus, if the Coralized example.com writes nyud.net cookies, these will be sent to evil.com.nyud.net if the client visits that webpage. Honest CoralCDN proxies will delete these cookies in transit, but attackers can still circumvent this problem.  For example, when a client visits evil.com.nyud.net, javascript from that page can access nyud.net cookies, then issue a XmlHttpRequest back to  evil.com.nyud.net with cookie information embedded in the URL.  These problems are mitigated by other security decisions: As CoralCDN does not support https or POST, it is unlikely that sites will establish authenticated sessions over it.  Given these attack vectors, however, simply opening up CoralCDN to a peer-to-peer deployment as is would introduce significant risk.  Similar attacks would be possible against other uses of the Same Origin Policy in the browser, especially as it relates to the ability to access and manipulate the DOM.

These issues demonstrate other challenges with deploying a secure, cooperative CDN, beyond the problem of finding the right “tradeoff” I talked about previously. It may be attractive to consider using end-hosts in a peer-to-peer fashion, perhaps even embedding proxy software in resource containers or VMs to satisfy those users’ concerns.  If clients and servers can be slightly modified, end-to-end signatures (as in RFC 2660 and Firecoral) can help ensure the integrity of content distributed through an untrusted proxy network.  Similar care would still need to be taken, however, to ensure the appropriate confidentiality of user-specific information.

In fact, these are some of the very challenges and approaches we are tackling with Firecoral, which seeks to build a P2P-CDN by running “cooperative proxies” as a browser extension of participating peers. We’re actively working towards a release; hopefully any day now!

Interface design

While superficially obvious, this interface design achieves several important deployment goals:

• Transparency: Work with unmodified, unconfigured, and unaware web clients and web servers.
• Deep caching: Support the automatic retrieval of embedded images or links also through CoralCDN when appropriate.
• Server control: Not interfere with sites’ ability to perform usage logging or otherwise control how their content is served (e.g., via CoralCDN or directly).
• Ad-friendly: Not interfere with third-party advertising, analytics, or other tools incorporated into a site.
• Forward compatible: Be amenable to future end-to-end security mechanisms for content integrity or other end-host deployed mechanisms.

Consider an alternative, even simpler, interface design. RedSwoosh, Dijjer, FreeCache, and CoBlitz, among others, all embedded origin URLs within the URL’s relative path, e.g., http://nyud.net/example.com/file. Not only is HTTP parsing simpler, but their nameservers do not need to synthesize DNS records on the fly (unlike CoralCDN’s DNS servers for *.nyud.net) and can take better advantage of client-side DNS caching. Unfortunately, while such an interface supports the distribution of specifically named files, it fails to transparently load an HTML webpage: Any relative embedded links would lack the example.com prefix, and a proxy would thus be unable to identify to which origin domain it refers. (One alternative might be to try to rewrite pages to add such links, although active content such as javascript makes this notoriously difficult, even ignoring the goal of not modifying server content.)

CoralCDN’s approach, however, interprets relative links with respect to a page’s Coralized hostname, and thus transparently requests these objects through it as well. But because CoralCDN does not modify body content, all absolute URLs continue to point to their origin sites. Thus, third-party advertisements are largely unaffected, and origin servers can use simple web beacons to log clients. Origin sites retain control about how their content is displayed and, down the line, content may be amenable to verification through end-to-end content signatures (as in RFC2660) or web tripwire tricks.

An API for dynamic adoption

CoralCDN was envisioned with manual URL manipulation in mind, whether by publishers editing HTML, users typing Coralized URLs, or third-party posters to Usenet groups or web portals submitting Coralized URLs. After deployment, however, users soon began treating CoralCDN’s interface as an API for accessing CDN services.

On the client side, these techniques included simple browser extensions that offer “right-click” options to Coralize links or that provide a CoralCDN link when a page appears unavailable. They also ranged to more complex integration into frameworks like Firefox’s Greasemonkey. Greasemonkey allows third-party developers to write site-specific javascript code that, once installed by users, manipulates a site’s HTML content (usually through the DOM interface) whenever the user accesses it. CoralCDN scripts for Greasemonkey include ones that automatically rewrite links, or that add Coralized links (in text or via tooltips) to posted articles on Slashdot, digg, or other portals. CoralCDN was also integrated directly into a number of client-side software for podcasting, such as Plone’s Plodcasting, Juice Receiver, and Easypodcast. Given the view that podcasting served to “democratize” Internet radio broadcasting, this seemed to fit quite well with CoralCDN’s stated aims of “democratizing content publication”.

But perhaps the more interesting cases of CoralCDN integration are those on the server-side. In flash-crowd scenarios, smaller websites might become overloaded for a variety of reasons: bandwidth-limited to serve larger files (especially due to hosting contracts), CPU-limited given expensive scripts (e.g., PHP), or disk-limited given expensive database queries. At the same time, their webserver(s) can often still handle the network interrupt and processing overhead for simple HTTP requests. And further, websites often still want to get complete logs for all page accesses, especially given Referer headers. Given such scenarios, a common use of CoralCDN is for origin servers to directly receive an HTTP request, but respond with an HTTP redirect (302) to a Coralized URL that will serve the actual content.

This is as simple as installing a server plugin and writing a few lines of code. For example, the complete dynamic redirection rule using Apache’s mod_rewrite plugin is the following:

   RewriteEngine on
   RewriteCond %{HTTP_USER_AGENT !^CoralWebPrx
   RewriteCond %{QUERY_STRING !(^|&)coral-no-serve$
   RewriteRule ^(.*)$ http://%{HTTP_HOST.nyud.net %{REQUEST_URI [R,L]

while similar plugins and scripts exist for other web platforms (e.g., the Wordpress blogging suite).

Redirection rules must be crafted somewhat carefully, still. In the above example, the second line checks whether the client is a CoralCDN proxy and thus should be served directly. Otherwise, a redirection loop could be formed. Numerous server misconfigurations have omitted such checks; thus, CoralCDN proxies check for potential loops and return errors if present. Amusingly, some early users during CoralCDN’s deployment caused recursion in a different way. By submitting URLs with many copies of nyud.net appended to the hostname suffix:

   http://example.com.nyud.net.nyud.net....nyud.net/

they created a form of amplification attack against CoralCDN. This single request caused a proxy to issue a number of requests, stripping the last instance of nyud.net off in each iteration. Such requests are now rejected.

While the above dynamic rewriting rules apply for all content, other sites incorporate URL Coralization in more inventive ways:

   RewriteCond %{HTTP_REFERER slashdot\.org [NC]
   RewriteCond %{HTTP_REFERER digg\.com [NC,OR]
   RewriteCond %{HTTP_REFERER blogspot\.com [NC,OR]

Combined with the above, these rules redirect clients to CoralCDN if and only if the requester originates from particular high-traffic portals. In Apache, such rules can be specified in .htaccess files and thus do not require administrative privileges. Other sites have even combined such tools with server plugins that monitor server load and bandwidth use, so that their servers only start rewriting requests under high load conditions.

These examples have shown users innovate with CoralCDN’s simple interface, which can be accessed like any other URL resource. We have even recently seen Coralized URLs being dynamically constructed within client-side Flash ActionScript. Indeed, CoralCDN’s most popular domain as of January 2009 was a Tamil imitation of YouTube that loads Coralized URLs from Flash animations of “recently watched” videos.

An Elastic Computing Resource

One of the most interesting aspects of these developments has been the adoption of CoralCDN as an elastic resource for content distribution, long before the term “cloud computing” was popularized and Amazon began offering CDN and other “surge” services.  Through completely automated means, work can get dynamically expanded out to use CoralCDN when websites require additional bandwidth resources, and contracted back when flash crowds abate. Still without prior registration, sites can even specify between several options on how they would like CoralCDN to handle their requests. X-Coral-Control headers returned by webservers provide in-band signaling and are saved as cache meta-data, such as whether to “redirect home” when domains exceed their bandwidth limits (per our previous post). But again, this type of control illustrates CoralCDN’s interface as a programmable API.

Admittedly, CoralCDN can provide free service (and avoid registration) because it operates on a deployment platform, PlanetLab, comprised of volunteer research sites.  On the flip side, CoralCDN’s popularity led it to quickly overwhelm the bandwidth resources allocated to PlanetLab by affiliated sites, leading to the fair-sharing mechanisms we described earlier.  My next (and final) post about our experiences with CoralCDN asks whether we should just move off a trusted platform like PlanetLab and accept untrusted operators.

Let us frame this argument by first considering some usage statistics from CoralCDN’s deployment.  The available aggregate data from 167 of the ~250 operating CoralCDN nodes during one recent, randomly-chosen day (January 20, 2009) shows that these nodes received a total of 9.74M requests from 983K unique client IPs.  These requests were for 596K unique URLs at 9,895 domains.  The figure on the left plots the entire distribution of requests per URL: The most popular URL received 448K requests itself, while 420K URLs (a full 70%) received a single request.  These requests appear to follow the Zipf-like distribution common among web caching and proxy networks.

So, if a small number of pages are so popular, we might measure their working set size, to determine how much storage is actually required to handle a large fraction of the total requests.  This table provides such an analysis.  The most popular 0.01% of URLs account for more than 38% of the total requests to CoralCDN, yet require only 52MB of storage. 1% of URLs account for almost 80% of requests, yet still require only 1.8GB of storage.  Recall that each CoralCDN proxy on PlanetLab has a 3GB disk cache.

These workload distributions support one aspect of CoralCDN’s design: Content should be locally cached by the “forward” CoralCDN proxy directly serving end-clients, given that small to moderate size caches in these proxies can serve a very large fraction of requests.  This differs from the traditional DHT approach of just storing data on a small number of globally-selected proxies, so-called “server surrogates”.  (While not analyzed here, per-node local caching also supports geographic differences in request distributions, provided that clients interact with nearby proxies.)

On the other hand, such a workload points out the unnecessary complexity in CoralCDN’s design: Global cooperation through a highly-scalable DHT indexing layer has marginal benefit to hit rates. We see this result in the following breakdown:

76.7% hit in local cache

9.8% returned 4xx or 5xx error code

7.0% fetched from origin site

6.3% fetched from other CoralCDN proxy

–  2.3% from level-2 cluster (local)

–  1.8% from level-1 cluster

–  2.2% from level-0 cluster (global)

In short, almost 77% of requests to proxies are satisfied locally, while only a little more than 6% result in cooperative transfers.  (The high rate of error messages is due to the bandwidth management of our underlying hosting service.)  A related result about the limits of cooperative caching had been observed earlier by Wolman et al, but instead from the perspective of client hit rates.  During the original design of CoralCDN, we had thought that this result may not be directly applicable to CoralCDN’s main goal, which was to decrease origin server load, not increase client hit rate.  The concern was that non-cooperating groups of caches would each individually request content from the origin, potentially overloading it.

To assess the benefits of cooperative caching to reduce server load, consider the three main usage scenarios observed in CoralCDN:

1. Random surfing: Recall that fully 70% of unique URLs through CoralCDN saw a single request. These may be from posted server links that are unpopular.  Or they may be from clients explicitly Coralizing links themselves (e.g., using client-side plugins) for a variety of reasons, such as (presumed) anonymity, censorship or filtering circumvention, or automated crawling.
2. Resurrect this page: Users attempt to use CoralCDN to retrieve content that is otherwise unavailable due to a overloaded or unavailable origin server.  This commonly occurs after Coralized links are posted as backup links or in comments on portals like Slashdot:  “Site down.  Try the Coral Cache“
3. Free bandwidth and flash crowds: The majority of requests to CoralCDN are for popular content, already widely cached, from a stable set of “customer” domains. Even its flash crowds occur on the order of minutes, not seconds.

These various use cases require different solutions, but CoralCDN’s design is not ideal for any of these cases:  It’s a jack-of-all-trades, master of none.

For unpopular content (use case #1), clients do not meaningfully change server-side load by using cooperative caching. Furthermore, the goal of censorship or anonymity circumvention can be better served simply through open proxies or specialized tools such as Tor (which recently saw a significant uptick from its use by Iranian protesters).

For long-term unavailable content (use case #2), CoralCDN is not designed for archival storage and durability.  For short-time horizons, on the other hand, if clients directly overload the server before CoralCDN can retrieve a valid copy of the content, its cooperation is also to no avail.  In fact, even if CoralCDN has already retrieved a valid copy of the file, many origin servers—especially those deployed via third-party hosting—cause it to replace good content with bad (as I discussed earlier).

Finally, for popular content (use case #3), one could imagine alternative cooperative strategies that only rely on regional cooperation.  Coral’s clustering algorithms would still be used for self-organizing the network into local groups, but a simple one-hop DHT could be used for content discovery (via consistent hashing).  After all, the above data shows that cooperation between proxies on a global scale (level-0) is only used to satisfy 2.2% of requests.  Such a strategy would easily scale to a CoralCDN network that is at least one order of magnitude larger than its current deployment.  Alternatively, to simply maintain its current 200–400 node deployment on PlanetLab, having each node maintain connectivity and liveness information about all others would certainly result in improved performance compared to its current “scalable” design.

One might ask, however, if CoralCDN remains the correct design for a truly Internet-scale cooperative CDN, where either the active working set or the number of participating proxies are several orders of magnitude larger.  Especially in the case of the latter, a single request from each distinct group could perhaps still overwhelm servers, which was our initial concern.  Unfortunately, a more “peer-to-peer” deployment—which is what CoralCDN’s algorithms are designed for—introduces a different problem if we wish to preserve CoralCDN’s compatibility with unmodified web clients and servers:  security.

There is nothing stopping malicious proxies from returning spam, malware, advertisements, or other modified content to unsuspecting web clients. I’ll return to this question of security and naming in a later post, but the overall implication seems to be a trade-off: either backwards compatible with today’s Web and a smaller deployment on trusted infrastructure (such as PlanetLab), or a more peer-to-peer deployment that requires end-host adoption.  In fact, this last point is one of the strong motivations behind our ongoing work on Firecoral.

So that’s the downside of CoralCDN’s design.  But it did catch on beyond what we expected; mostly, I believe, because of its simple user interface that requires no registration and little knowledge, yet was eventually used in a variety of flexible, powerful ways.  In fact, our “customers’” interactions with CoralCDN portended the elastic use of cloud computing resources for (what some have called) surge computing.  I’ll discuss this in my next post.

To provide Internet connectivity in the developing world is a daunting task, with problems pertaining to a high cost of bandwidth, ill-provisioned equipment and power, scarcity of on-site expertise, and adverse environmental conditions. Most common way to offset bandwidth cost/consumption is to deploy high-performance web proxy caches at the edge. Such high-performance proxies, primarily designed for the developed world, run as a dedicated service on a well-provisioned server with a large amount of RAM. The problems with “porting” this solution as-is are manifold and would only exacerbate the problems pertaining to power consumption and adverse environmental conditions. The initial expenditure involved for acquiring such powerful servers would make inventory control harder and also make deployments expensive because of having to supply, manage and maintain not only the end host laptops and but also their servers.

A high-performance, efficient cache storage engine which can index large disks is essential not only for static web caching but also for enabling other bandwidth/latency reduction techniques like WAN acceleration and web pre-fetching. Disk price is plummeting by the month and is currently at a dime/GB, but the price of a server which can index a terabyte disk could be anywhere between $1000 to $2000. Such servers will have high power consumption due to large amounts of RAM and the requirement of an operational temperature that further complicates the problem. Further, most of the RAM has to be dedicated to provide only a web cache, which is undesirable considering the low bandwidths in these environments. Cheap laptops and netbooks, on the other hand, are ruggedized for developing world environments. They are made for low power consumption and are designed for use in adverse environmental conditions where power might be irregular. If we can design a cache storage engine which can run efficiently on cheap laptops and index terabytes of disk, then we will be able to address an important problem that arises in providing good web services for developing-regions. Laptops solve the problems pertaining to power, environment, and maintenance, whereas large disks solve the problems pertaining to low bandwidth.

Our work, HashCache, is a configurable cache storage engine which can index terabytes of disk by using 6 to 20 times less memory compared to traditional web proxy caches.

The high memory requirement of traditional proxies stems from two reasons. First, regular hashtable data structures spend a lot of memory on pointers and keys. Second, they alienate the disk, which is the performance bottleneck, by using it only as a storage device. HashCache is an entirely new way of building a disk cache engine with indexing schemes devoid of any pointers and the disk itself being used as an application-level data structure. What this does is enable the minimal usage of memory for indexing and allow the application to directly interact with the disk, which is the performance bottleneck. HashCache is a range of disk indexing policies ranging from ones using no main memory at all for indexing to ones which consume 6-10 times less memory than traditional high-end proxies yet provide similar or better performance. The figure on the left illustrates the comparison. It shows cost vs. performance comparison of various HashCache policies and existing proxies.

While the intricate details of the seven different policies can be found in our paper, the following is a reasonable attempt at a summary. Traditional proxies build fully associative caches and hence their index hashtables need to contain pointers to be able to reference content that can possibly go at any location. The keys are the names (hashes of names) and the values are pointers in to the filesystem. The simplest HashCache policy uses that disk directly as a large set-associative hashtable with fixed sized bins, it stores the metadata of on-disk hashtable in main memory for speeding up lookup operations. The value in this hashtable is the final object itself. Restricting the number of locations that an object can be placed by using set-associativity and having those locations contiguous on the disk eliminates the requirement of pointers. It also reduces the number of bits needed to represent the hash value of the object name in the hashtable since the lower order bits can be decoded from the bin number in the hashtable. Objects larger than a bin need additional place for storage. The remaining part of the object is stored in a circular log. This bare-bones index needs 11 bits of RAM to index an object on the disk. The rest of the policies revolve around memory requirement and disk performance optimizations over this simple setting.

We have built a web proxy cache using the HashCache indexing policies and have been actively deploying it freely for educational and academic purposes. A commercial offering of HashCache is also planned. Just a few days back, we helped a group at Cornell College of Agriculture to install HashCache and a WAN Accelerator on top of that called Waprox  at a node in Uganda. They are part of the Durable Rust Resistance in Wheat project and wish to use the node to download a large number of agricultural documentation for the education of local farmers. On the left is a picture of Stefan Einarson handing over the HashCache box to head of Crop Sciences at Makerere University in Uganda. We wish to continue doing such deployments for free for educational and academic purposes in the developing world. You can contact us directly if you need faster connectivity for an educational project in a developing region. We will be glad to help.

The future direction in this line of work is a larger project aimed at developing a networking stack for poorly provisioned edge networks. The idea is to develop on top of HashCache and provide a full software stack of bandwidth and latency reduction techniques including WAN Acceleration, web pre-fetching, local disk web-search engines and ultimately a generic offline cache of any popular website. Our proposal paper at the CCC Developing Regions Workshop has more details. We are also working towards incorporating new and efficient memory technologies like flash memory to offset problems relating to scale and power. We are currently developing a hybrid memory management technique that takes into account the density and functionality differences of different memory types in a hybrid architecture and comes up with clever strategies to provide applications with large amounts of efficient random access memory. Stay tuned and we will keep you posted with the progress we make towards this developing regions network stack.

Dirty Slate Design reflects a design philosophy for systems and networking research, where deployability is a central goal.  While it’s often tempting to try to solve problems by wiping the slate clean and starting afresh, expecting a complete redesign and redeployment of systems as important, complex, and far-flung as the Web or the Internet is rather optimistic at best.

So, rather than implying something that is just “quick and dirty,” this philosophy tries to push new functionality or designs in a way that can be retrofitted into existing systems/networks or can reuse existing mechanisms in new ways, whenever possible.  This isn’t to say that clean-slate architectures don’t have their place, either as a “thought experiment” or something that’s trying to look farther over the horizon.   And we don’t want to restrain ourselves to incremental improvements given what’s possible with today’s mechanisms, protocols, or technologies.  Further,  what actually constitutes “clean-slate” versus “dirty-slate” is rather subjective (just look at the NSF FIND projects, for example, where some of these could certainly be incrementally deployed on today’s Internet).  Rather, let’s worry about the “dirty details” because systems often have to make non-obvious engineering tradeoffs and operate in complex environments.  Because those dirty bits often lead to new, interesting research questions, and the ultimate goal should always be impact.

In the next few weeks or months, we should be describing a bunch of new projects that take some of these ideas to heart, mostly focusing on distributed systems and network architectures for geo-diverse datacenters.  Stay tuned.

Interacting with hosting platforms

CoralCDN’s self-regulation works well in trusted environments, and this approach is used similarly in other peer-to-peer (e.g., BitTorrent and tor) and server-side (e.g., Apache mod_bandwidth) environments.  But when the resource provider (such as PlanetLab, a commercial hosting service, or peer-to-peer end-users) wants to enforce resource restrictions, rather than assume the software functions correctly, the situation becomes more challenging.

Many services run on top of PlanetLab; CoralCDN only being one of them.  Each of these instances is allocated a resource container (a “slice”) across all PlanetLab nodes.  This doesn’t have the same level of isolation as a virtual machine instance, but its much more scalable (in number of slices per node, each per-node slice called in sliver in PlanetLab).

PlanetLab began enforcing average daily bandwidth limits per sliver in 2006; prior to that, sliver usage was all self-enforced. Thereafter, however, when a sliver hit 80% of its daily limit, the PlanetLab kernel began enforcing bandwidth caps (using Linux’s Hierarchical Token Bucket scheduler) as calculated over five-minute epochs.  CoralCDN’s daily limit is 17.2 GB/day per sliver to the public Internet.

So, we see here two levels of bandwidth control: admission control by CoralCDN proxies and rate limiting by the underlying hosting service. Even though CoralCDN uses a relatively conservative limit for itself (10 GB/day), it still surpasses the 80% mark (13.8 GB) of its hosting platform on 5–10 servers per day. And once this happens, these servers begin throttling CoralCDN traffic, leading to degraded performance.  The main cause of this overage is that, while CoralCDN counts successful HTTP responses, its hosting platform accounts for all traffic—HTTP, DNS, DHT RPCs, system log transfers, and other management traffic—generated by CoralCDN’s sliver.

Unfortunately, there does not appear to be sufficiently lightweight or simple user-space mechanisms for proper aggregate resource accounting.  Capturing all traffic via libpcap, for example, would be too heavy-weight for our purposes.  Furthermore, a service would often like to make its own policy-based queuing decisions based on application knowledge.  For example, CoralCDN would prioritize DNS traffic before DHT RPCs, HTTP traffic next, and log collection of lowest priority. This is difficult through application-level control alone, while using a virtualized network interface that pushes traffic back through a user-space network stack would be expensive.

CoralCDN’s experience suggests two desirable properties from hosting platforms that enforce resource containers.  First, these platforms should provide slivers with their current measured resource consumption in a machine-readable format and in real time.  Second, these platforms should allow slices to express policies that affect how the underlying platform enforces resource containment. While this pushes higher-level preferences into lower layers, such behavior is not easily performed at these higher layers (and thus compatible with the end-to-end argument).  And it might be as simple as exposing multiple resource abstractions for slices to use, e.g., multiple virtual network connections with different priorities.

Somewhat amusingly, one of CoralCDN’s major outages came from a PlanetLab misconfiguration that changed its bandwidth caps from GBs to MBs.  As all packets were delayed for 30 seconds within the PlanetLab kernel, virtually all higher-layer protocols (e.g., DNS resolution for nyud.net) were timing out.  Such occasional misconfigurations are par for the course, and PlanetLab Central has been an amazing partner over the years.  Rather than criticize, however, my purpose is to simply point out how increased information sharing can be useful.  In this instance, for example, exposing information would have told CoralCDN to shut down many unnecessary services, while policy-based QoS could have at least preserved DNS responsiveness.

Over-subscription and latency sensitivity

While CoralCDN faced bandwidth tensions, there were latency implications with over-subscribed resources as well.  With PlanetLab services facing high disk, memory, and CPU contention, and even additional traffic shaping in the kernel, applications face both performance jitter and prolonged delays.  For example, application-level trace analysis performed on CoralCDN (in Chapter 6 of Rodrigo Fonseca’s PhD thesis) showed numerous performance faults that led to a highly variable client experience, while making normal debugging (”Why was this so slow?”) difficult.

These performance variations are certainly not restricted to PlanetLab, and they have been well documented in the literature across a variety of settings.  More recent examples have shown this in cloud computing settings.  For example, Google’s MapReduce found performance variations even among homogeneous components, which led to their speculative re-execution of work.  Recently, a Berkeley study of Hadoop on Amazon’s EC2 underscored how shared and virtualized deployment platforms provide new performance challenges.

CoralCDN saw the implications of performance variations most strikingly with its latency-sensitive self-organization.  Coral’s DHT hierarchy, for example, was based on nodes clustering by network RTTs. A node would join a cluster provided some minimum fraction (85%) of its members were below the specified threshold (30 ms for level 2, 80 ms for level 1).  This figure shows the measured RTTs for RPC between Coral nodes, broken down by levels (with vertical lines added at 30 ms, 80 ms, and 1 s). While these graphs show the clustering algorithms meeting their targets and local clusters having lower RTTs, the heavy tail in all CDFs is rather striking.  Fully 1% of RPCs took longer than 1 second, even within local clusters.

Another lesson from CoralCDN’s deployment was the need for stability in the face of performance variations, which are only worse in heterogeneous deployments.  This translated to the following rule in Coral.  A node would switch to a smaller cluster if fewer than 70% of a cluster now satisfy its threshold, and form a singleton only if fewer than 50% of neighbors are satisfactory.  Before leveraging this form of hysteresis, cluster oscillations were much more common (leading to many stale DHT references).  A related focus on stability helped improve virtual network coordinate systems for both PlanetLab and Azureus’s peer-to-peer deployment, so it’s an important property to consider when performing latency-sensitive self-organization.

Next up…

In the next post, I’ll talk a bit about some of the major availability problems we faced, particularly because our deployment has machines with static IP addresses directly connected to the Internet (i.e., not behind NATs or load balancers).  In other words, the model that the Internet and traditional network layering was actually designed with in mind…