2008-11-06 Readings - Names, Identifiers, and Network Architecture

MIDDLEBOXES NO LONGER CONSIDERED HARMFUL

Michael Walfish, Jeremy Stribling, Maxwell Krohn, Hari Balakrishnan, Robert Morris, and Scott Shenker

Summary:

Presents the Delegation-Oriented Architecture (DOA), that not only allows, but also facilitates, the deployment of middleboxes. Basic idea is very simple. Instead of doing node ID on IP addresses & ports, do it using another layout of abstraction of EID (Endpoint ID). Implementation requires DHT for EID translation, addition to the OS kernel space to do the EID lookup, and addition to the network stack headers to have DOA header between IP header and transport header. Their initial implementation has tolerable overhead.

Discussions & Criticisms:

First, minor point, the name DOA isn't all that cute or inspiring or blandly technological. Usually I don't even notice the name but when I was reading the paper and my roommate was watching some disturbing junk on Youtube, the screams he made pretty much sounded like DOOOOOUUUUUUAAAAAAHHHH!!!!! Had the name being Goa then at least some people would recognize it as some place in Indian, albeit associated with the short-lived Portugese colonial presence there ...

Second, major point. Continuing the train of thought from the DNS paper, there's no chance this technology would get adoptedin real life. It solves a somewhat artificial problem - the complaints from Internet architecture purists (the authors themselves) about the harmfulness of middle boxes and how it violates various Internet design principles. I would have preferred something snappy and blunt, e.g. Scott Shenker coming out and saying "We think middle boxes are no longer full of crap." He made and equivalent statement about his prior work in QOS and that message stuck more than any paper would. Also, the way it's presented, it requires too many architectural changes in the underlying network implementation. So costs > benefits.

There might be an economy of scale business argument for concentrating the management of middle boxes into an expert third-party, and remove the redundant expertise in that area from across multiple businesses/organizations. But for most organizations, the control over the potentially critical functionality of the middle boxes far negates any saving in efficiency. Nevertheless the "outsourced" middle boxes idea is worth keeping in mind and has the potential to completely disrupt the on-the-path middle boxes business.

The overhead results in the paper are not yet fully convincing. Latency overhead could get large for large administrative domains with large DHT lookup table. Packet header overhead could get large for small chatty type packets. Might need lots of caching in the style of DNS.

Also it's not clear to me on which nodes the DHT would reside. For example, if we use Chord, who would be the "other" Chord nodes?

Potential security exploits in DOA are obvious.



INTERNET INDIRECTION INFRASTRUCTURE

Ion Stoica, Daniel Adkins, Shelley Zhuang, Scott Shenker, Sonesh Surana

Summary:

Outlines the Internet Indirection Infrastructure (i3). Motivated by the current inefficiencies in multicast and anycast, and the network architecture's sole focus on unicast. Basic idea is to have (ID, data) and (ID address) pairs to separate sending and receiving. The senders and receivers rendevouz at some point in the network. Implemented in an overlay network (Chord used for the particular implementation). Each node stores sufficient state to facilitate rendevouz. Each node stores state for ID allocated in Chord style. Lots of implementation details.

Discussions & Criticisms:

Not sure if we're solving a real life problem here. Most multicast/unicast would be large content provider to many individual end-consumer. The multi-cast tree/Akamai approach seems to work fine. Mobility would be a better motivation. But perhaps that's because the home agen/foreign agent business is really ugly. How do cell phones manage mobility? Perhaps IP/voice convergence should learn from cell phones in terms of mobility?

The architecture would inherit all the deficiencies of Chord. In particular the hop count routing metric is broken (ETX, ETT would be better?).

Much of the implementation ugliness needed arised out of the assumption that multi-cast and unicast traffic can be treated well in the same infrastructure. I think they are fundamentally different. But not sure if the best solution is the current solution (faking multicast using clever unicast through Akamai and such), or something else. Mobility we should consider borrowing ideas from cell phones.

Security threat model is horrendous. You have Chord nodes storing routing information and act as points of transit. These are end consumers, and has a significantly lower level of trust than routers etc. managed by ISPs and backbones. Can eavesdrop/re-route/spoof like crazy.

Also potentially creating bottlenecks at the network edge - using the low capacity of the network edge to do stuff that should arguably be done in the network core.

Still, a nice idea that more or less solves what it sets out to solve under the constraints it places on itself.

2008-11-04 Readings - DNS and the Web

DEVELOPMENT OF THE DOMAIN NAME SYSTEM

Paul V. Mockapetris, Kevin J. Dunlap

Summary:

Talks about the original motivation for and implementation of DNS. Motivated by how the HOSTS.txt fails to scale. Original system requirements include scale, distributed management, no limit for names & data associated with names, interoperable across DARPA Internet and other networks. Additional requirements that helped transition/adoption include independence on network topology, avoid focing a single OS or organizational style. Generally minimalist design to allow greatest implementation flexibility. Caching responses is really important, including caching negative responses. Adoption resistance mainly arised from different assumptions regarding how systems should work. Also protocol compliance tests should assume people do enough to get this working and do no more, and thus must include mechanisms that require demonstration of the required functionality.

Discussions & Criticisms:

Overall a very interesting story of how a core component of the Internet got developed. The motivation of the system was pretty obvious, and I don't think anyone would dispute that DNS is needed or that DNS has been successful. What got me going is the adoption story, perhaps a model for designing future technologies that are likely to be adopted on a large scale.

I think there are several criteria for the DNS success story to be repeated. 1. The technology must tackle a critical problem that makes both research and industry say "Oh crap we're screwed", and resolve the problem with significant demonstrable benefits. 2. The technology must be minimalist in design, and make no assumptions about system topology, architecture, organizational style, policy priorities. 3. The initial technology must be minimalist in design, resolve the problem at hand and do not try to force solutions for other problems (the debate on MX records could easily have blown out of control and had MX been central to DNS, the MX debate could have scuttled DNS adoption). Once adoption is well underway, layer-on functionality can be introduced. 4. The techonology must work under the assumption that real life implementers will achieve minimal functionality and does very little testing/tuning.

Would appreciate comments re the above list.

I also find it interesting to think about the naming resolution/distribution problems for the Internet (DNS) and for the phone network (basically through human contact).


DNS PERFORMANCE AND THE EFFECTIVENESS OF CACHING

Jaeyeon Jung, Emil Sit, Hari Balakrishnan

Summary:

Presents DNS trace data and associated analysis. Data comes from around 2000-2001. Three continuous chunks on the order of days. Trace from link connecting MIT LCS and KAIST to the WAN. Also has trace-driven simulations to investigate caching strategies and the effect of changing the cache TTL. Key results include a large % of no answer or error results - the former takes up a large chunk of traffic due to overly persistent retries. Also, long-tail name access patterns suggest low cache TTL does not impede performance, and shared cache among clients do not improve performance.

Discussions & Criticisms:

First, the data collection method. I appreciate that as a first-of-its-kind study, they had to work with whatever data they have instead of whatever data they would wish for. Still, future studies should consider capturing more data and do some kind of Poisson sampling with the data (e.g. samples a few hours at a time over several months using Poisson sampling). General intuition that Poisson sampling captures time averages. I think both tracing and data analysis capabilities have increased greatly since the work was first published.

Long tail name access patterns means TTL ~ duration of each user session, since it's reasonably pointless to cache across sessions that go all over the place. Turning point of all their TTL vs hit rate curves occur at TTL ~ 500 sec. Seems to correspond to duration of user sessions.

Did they propose any fixes for the observed pathologies (no answers, repeated answers etc.)?

Caching and TTL messages reasonably convincing and looks adoptible - just requires software config. of DNS cache, right? Have people been willing to do this?

2008-10-30 Readings - Distributed Hash Tables

LOOKING UP DATA IN P2P SYSTEMS

Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris, Ion Stoica

Summary:

Surveys various DHT (distributed hash table) schemes for lookup in P2P systems. Frames the "lookup problem" and describes the DHT. Outlines one-dimensional routing (Chord), tree-like routing (Pastry and Tapestry), and multidimensional routing (CAN). Notes open problems in the field, e.g. distance function, operation costs, fault tolerance, proximity routing, malicious nodes, indexing and keyword search.

Discussions & Criticisms:

It would be nice for a survey paper to kind of do some comparative study using some figure of merit. Doesn't need to say one thing sucks and another rocks, but would give an indication of the pros and cons of each. The community did arrive at the conclusion later that Chord is basically the best of them.

Not much else to say for a survey paper. DHT is still new material for me. Skipped the undergraduate database class and didn't fully "get" the topic in CS262A. Also read the Chord and CAN paper there. This will hopefully sink in on the second pass.


Chord: A SCALABLE PEER-TO-PEER LOOKUP SERVICE FOR INTERNET APPLICATIONS

Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan

Summary:

Presents Chord, an architecture and an implementation of a P2P lookup services. Key ideas include a circular structure, consistent hashing to load balance, finger tables to provide O(logN) lookup cost, successor nodes to ensure nodes can join and leave without affecting system performance. Generally agreed to be the best P2P DHT there is. Lots of details in the implementation. Not clear how to deal with concurrent joins and departures.

Discussions & Criticisms:

Same concerns as my first read of the paper. The system is obviously proved to be good and accepted as such. Easy of implementation? Is it adopted widely? Is the next random P2P start up going to jump onto the Chord bandwagon?

The modifications to the vanilla protocol to facilitate concurrent joins/departures look somewhat awkward. Seems like one does need to read their technical report to see all the proofs.

Mentioned this in class. Chord uses hop count now. People have proved for various contexts that hop count may suck as a routing metric. Any attempts to apply ETX and other such tricks to Chord? Could be side project once I take care of business in the datacenter track.

DHT for datacenters? Surely there must be techniques that we can recycle for something.

2008-10-25 Readings - Overlay Networks

RESILIENT OVERLAY NETWORKS

David Andersen, Hari Balakrishnan, Frans Kaashoek, and Robert Morris

Summary:

Presents the Resilient Overlay Networks (RON), an overlay network system to allow participating nodes to send data to each other around network outages. Basic idea is to have an overlay network, with participating nodes being hopefully geographically/topologically dispersed. Nodes run some algorithms to detect outage conditions, and switch from direct routes to source - 3rd party - destination type routes as appropriate. Include tight application integration mechanisms to specify what is an "outage". Also includes mechanisms to allow overlay routing per some policies and algorithm to detect outages and select alternate routes. Results show that the system addresses the problem that it sets out to address.

Discussions & Criticisms:

Waaaaaaaaaait .......... isn't one of the original goals of the internet to be resilient against outages and to auto-magically route around them? What the hell happened? Did we totally fail? I guess we did :(

I guess the root cause for the failure comes from the need for both intra-AS and inter-AS routing algorithms to avoid fluctuations and route flaps, which necessarily mean slow convergence to new route table state when existing routes go down. So basically RON type overlay is necessary for quick outage detection.

Does RON ever switch back to a direct route once the traditional routing tables converge? Didn't manage to dig that out of their route selection algorithm.

Good piece of research but arguably a less worthy piece of software engineering. My main objection is that the system tries to do too much at once, again leading to a good technology that is very unlikely to see adoption. The key idea is to have some kind of overlay that routes around outages. But the RON system, as it is presented, messes that up with tighter application integration, policy routing, and some what of a new routing protocol.

Ok so here's what I would do. My approach would be to do the minimalist design, i.e. overlays that route around outages with a minimalist routing protocol, do it TRANSPARENTLY to the application, and offer optional handles to specify application "outage" definitions. Routing policy specifications should be left in the hands of people who actually understand policy specs, and should come as a double optional configuration thing. "Legacy" applications running on the ordinary TCP stack should require minimal migration changes or no changes at all.

I would also put out Java/C/C++/Python libraries implementing this new overlay in a transparent fashion, basically still offering the nice socket interface, complete with all the necessary online API documentation.

The next step would be to partner with some enterprise/campus network, and have the system in limited, managed deployment to work out all the kinks (also data for more research).

Somewhere along the line we would need to figure out what applications/use cases would especially benefit from this overlay. Else there's no way we can convince ordinary users to install/configure the system. Good time to push for adoption would be after significant outages - "Use our system so that the next time you can keep working instead of just helplessly whine and moan and endlessly complain!" Somewhat devious .... benefiting from outages.

More seriously, technology wise, seems that a very small number of geographically/topologically dispersed nodes would be sufficient to facilitate routing around outages.

The resilience against flooding attack argument wouldn't work if nodes are not multi-homed.

Overlay routing itself seems to be an open question still.

Obvious security concerns with data traversing 3rd party network end points.


ACTIVE NETWORK VISION AND REALITY: LESSONS FROM A CAPSULE-BASED SYSTEM

David Whetherall

Summary:

Talks about the experiences of implementing the ANTS system and how it shaped the author's views on the original vision for active systems. ANTS is implemented in Java, has basic active network functionality, and includes a sandbox (extension of existing Java security mechanisms) for running active network code. Active network node receives capsules, demux for the appropriate routine to run, runs the routine (which may include forwarding), and repeats. Variety of outstanding issues including security and resource isolation. Key lessons include capsules are useful, but need traffic patterns that made code caching effective; sandboxing achieves some local isolation/protection, but attacks against the network still need to be stopped; greatest value in allowing evolution of services in the network layer.

Discussions & Criticisms:

Fingers tired from the RON ramble. This might be short.

Is the fundamental goal of the network to communicate or to compute? Hmm ...

Their "Deployment" section basically tells me the technology is not deployed. But nice to see the authors being sensitive to deployment requirements and issues.

Any business case for offering new services in the network?

DNS caching results may undermine their reliance/assumption of traffic patterns that allow code caching to be effective.

Hmm ... the real value of active networks seems to be network services variation/evolution. There's gotta be more uses for this very "different" idea.

ASs may prevent active network services from traversing administrative boundaries? "Why should I use resources on my own network to help you compute services for which users pay only you and not also us?"

Seems really useful for sensor nets though.

2008-10-21 Readings - Topology

ON POWER LAW RELATIONSHIPS OF THE INTERNET TOPOLOGY

Michalis Faloutsos, Petros Faloutsos, Christos Faloutsos

Summary:

Presents analysis of routing data to extract insights of Internet topology circa 1997-1998. Data set comes from BGP routing tables between ASs and router tables. Internet growth during the period covered is 45%. Key finding is that many topology metrics have power law relationships (A = kB^p or logA = plogB + logk) to one another. Fit data to power laws using linear regression, with correlation coefficients ~0.96 and above, sometimes as high as 0.99. Specific power laws found include out-degree = rank of the node to the power of ~-0.80, frequency (number) of nodes of an out-degree = out-degree to the power of ~-2.2, pairs of nodes separated by a number of hops = number of hops to the power of ~4.7, with the upper bound of number of hops < graph =" order" style="font-weight: bold;">

Discussions & Criticisms:

Are the authors related? Couldn't figure out whether they are relations or not, but Michalis and Petros' webpages make it looks like there's a Faloutsos clan out there.

Must have taken a LONG time to crunch the data and generate the graphs. I like how the key results are presented tersely in nicely highlighted boxes.

What is the significance of the eigenvalue of graphs? The authors mention the eigenvalue power law exponent is good for distinguishing different families of graphs. Other significance?

There is not much to criticize. Their mathematics is near air-tight (at least the couple of small parts that I cared to check). One can complain about the representativeness of their data, but their power law relationships are so near identical across data sets that it has to be some really non-fundamental coincidence to give them such nice results. Also the linear regression coefficients are as high as any experimental data can hope to get. Really surprising.

If there is a shortcoming I guess it's the unclear way of how someone could use their results. I buy their results and I concur that the power law perspective is really nice for understanding and essential for simulation, and it should also inform network design. But how does one begin to incorporate their findings in actual design tasks? Any related work that uses their power law findings?

The authors make me feel inadequate about my own math .... Must seek to arm myself with some basic level of number crunching competence. Would help with understanding machine learning stuff too.


A FIRST PRINCIPLES APPROACH TO UNDERSTANDING THE INTERNET'S ROUTER LEVEL TOPOLOGY

Lun Li, David Alderson, Walter Willinger, John Doyle

Summary:

Presents toy models to show that the power-law focus on building Internet models fail, and models more guided by first-principle designs would be better. Basic idea is that many randomly generated graphs can fit the macroscopic power laws, but not all of those would be a good representation of the Internet. Presents topology choices as driven by technology and economic constraints, and thus are not randomly generated at all. Uses toy topologies including preferential attachment, randomly generated graphs, heuristically optical graphs, graphs inspired by some real-life systems, and graphs designed to be sub-optimal. All conform to the same power laws, but some are clearly better than others. Uses traditional performance metrics, graph theoretic metrics (same for all topologies), and graph likelihood metric (roughly how likely would the given graph topology turn up in a random graph generator).

Discussions & Criticisms:

Pretty complicated and heavily theoretical paper to present a very simple idea - that Internet shows power law relationships doesn't mean stuff with power law relationships would represent the Internet.

Good paper to temper the (over)enthusiasm over power laws.

Good discussion of economic constraints.

Took a LONG time to really make it clear what their "first principles approach" actually is.

Caveat for the other implication they brought up. Just because things that have been designed are unlikely to come from randomness, things that are not random doesn't automatically imply the presence of some organized design.

At what point does model become attempt to replicate or attempt to snap shot?

2008-10-16 Readings - Sensor Networks

TAG: A TINY AGGREGATION SERVICE FOR AD-HOC SENSOR NETWORKS

Samuel Madden, Michael J. Franklin, Joseph M. Hellerstein, Wei Hong

Summary:

Describes a way to implement SQL-like functionality for ad-hoc sensor nets. There are two key ideas. First, users write SQL-like stuff to query the sensor net, instead of writing low-level potentially buggy C code to do the same thing. Second, the query will be fulfilled as it is "incast" back to the query source. Lots of tricks to save the amount of transmission to reduce energy consumption. Simulation based evaluation and prototype implemented. Results show their system performs much better than "centralized" query in cutting down communication.

Discussion & Criticisms:

Philosophically speaking, I do believe aggregation is very important for sensor networks. Also, detecting anomalies also very important. So are we opening some sort of flood gate of requests for all functionalities to be put on the sensor motes? Ok so we can express anomalies detection queries in SQL. Non-SQL expressible queries? If there can be such things ....

Transmission power >> on-board computational power for wireless. Therefore all the efforts to do as much as possible through active nodes in the network makes complete sense. Should borrow this general approach for other wireless apps. Wired situations on-board computation power ~ or > transmission power, so duplicate computations may be more power intensive there. How can we systematically measure end-to-end power efficiency in wireless?

Did the paper try to cram too much into a limited amount of space? It also defined more or less a new database query language.

Insights can be recyled in DHT stuff? Basically the paper outlines a way to implement a distributed database capable of responding to a variety of queries. There's GOT to be use for the same ideas elsewhere.

Agree with the usability argument that user-facing API should be as high level as possible. Wouldn't want to have a null pointer exception from a mote ... I want to actually use this!

Also liked the work as an example of mixing fields (databases and wireless) to create something really funky and really new. No longer a new idea and people have caught on and done follow up studies, right?



DIRECTED DIFFUSION: A SCALABLE AND ROBUST COMMUNICATION PARADIGM FOR SENSOR NETWORKS

Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin

Summary:

Describes the directed diffusion paradigm for sensor nets. Tasks described by attribute-value pair. A node injects "interest" in certain tasks. The "interest" gets forwarded periodically and kept alive periodically through the network. Nodes getting an "interest" may forward it to some subset of its neighbors. "Interest" state is cached at nodes, with state scaling with the number of active tasks. "Gradients" establish the direction of data propagation. Nodes propagate along the gradients the events they detect that match their cached interests. Can "reinforce" certain paths to select gradients for data flow based on empirical link quality.

Discussions & Criticisms:

The key ideas are not seen only here - doing computation in the network, use empirically good paths. I feel like doing some reference and publishing date chasing to see who borrowed from what, or have we been reinventing the wheel, so to speak. Would be sad if the wireless world got so big that even experts in the field cannot keep up .... TAG did give a nod to this paper, I don't think the Roofnet set of papers referenced this, even though they came later.

Data centric approach definitely smells of design sensibilities from databases. Chased down the authors backgrounds. Interestingly none of them have a prominant database background.

The authors explicity want to defer the study of naming to focus on the study of diffusion/data routing. I understand the need for this. But can it actually be done? Not convinced if all their results need to be qualified as "The system is thus given we name everything like this."

Periodic broadcast of "interest" - doesn't this lead to very bad/chatty protocol that's very power hungry? Possibly that alone undid all the savings from doing data transformation in the network. Their comparative simulations relative to flooding and omniscient multi-cast would fail to capture this cost.

State storage could become a scalability issues when the number of active tasks go up.

Again, doing more computations on nodes can save transmission energy - duplicate suppression unsurprisingly good.

I wonder what power model they used to compute/simulate dissipated energy. Looks like they only included transmission energy anyways. The authors weren't very detailed about this.

Did not like the somewhat unintuitive terminology.

I also noticed that my routine skepticism re wireless ad-hoc networks for IP type data reduces significantly when we're talking about wireless ad-hoc for sensor nets.

Doing drop-front queueing on readings

But will blog in order. Hence the appearance of being severely behind :-)

Drop-front really IS the best queuing scheme.