Monday, November 24, 2008

Map-Reduce Performance

So this is Andy and Matei's fantastic OSDI work, improving the performance of the speculative execution of Hadoop. It turns out to be pretty simple, as hadoop does everything in a very naive way. Good work, and great problem selection. Lastly, great acronym selection. Matei is great at that.

Firstly, this work lies under the huge shadow of Google. No one really knows what their system does. They published in 2002 (I think), and hadoop is just about catching up to their system at that time. It's a solid academic area, but there's an open question as to the novelty of the work because of that.

This particular work is likely pretty novel, as Google has a fairly homogeneous network. I think it's 3 types of systems at any point.

Another question revolves around map-reduce itself. I think it's telling how few research efforts actually USE the system, rather than work on the system. I've found that there's a set of problems that it solves, and it's really not a huge set. They're pretty much the uses we've found in the rad lab, log searching. It doesn't build services. It doesn't scale databases (yet). The parlab has map-reduce as one of the "dwarves", a series of solved parallel problems. It's not the key one, as some in systems seem to think.

So the key, in my mind, is to expand the map-reduce problems. My understanding is that MSR is doing this, Yahoo as well. Turning it into a non-consistent database is interesting. Generalizing the model to encompass other parallel problems is interesting. However, the original map-reduce paper never would have been published without Google backing it. It took the experience of it's deployment to get attention. How many great parallel architectures sit in dusty conference proceedings? How do we change this research area so that the simplicity of the map-reduce model is seen as an advantage?

Lastly, I think you should have people read the map-reduce paper and stonebreaker's nagging paper.

Policy Aware Switching

Firstly, I'm going to be out of class on Tuesday. I hope you guys have a good talk.

I couldn't finish it, 26 pages for something I've listened to numerous talks about. It's quite likely I've missed some details, but the idea is pretty simple:

Overlays give us a few advantages, one of which is in routing. We use that in this in the PAS to enforce routes that packets must fly by to reach their endpoint. For instance, we can enforce, in the overlay alone, that a packet must go through a firewall before hitting me.

This gives huge flexibility, all the flexibility you'd expect an overlay to allow. In my nascent graduate career, I first worked on a project that lined up very well with this. PAS gives you various abilities. You can do statistical tricks, allowing packets through some time, for active testing or load balancing.

It has one huge problem though, which is something I've talked about a few times on this blog. It's not optimizing for the common case. They want performance, and this doesn't increase it. For top-tier datacenter companies such as Google, this is totally useless. They'd much rather pay their network engineers a larger amount and get better utilization. It does make sense for smaller datacenters, but not really, as they have fewer configuration problems. Lastly, the engineers themselves are not likely to adopt technology that reduces their employment.

So this is neat work, and with it you can do some really cool things with a network. It's not targeted correctly. I can think of some good uses for this, mostly from ISPs and the like who may want more direct control of their traffic. For instance, they'd like to push all P2P people over some thinner line. That's not as sexy (or well funded) as datacenters.

Wednesday, November 19, 2008

App Layer Multicast

Ok, overlays give you multicast. I see that. This is an alright system for that, hierarchy. That's cool.

I could be that I'm tired, but I just don't have a lot to say about either of these items. Great, multicast. Cool. There's nothing elegant or useful here. Nothing mind-blowing, just "if I had to build a multicast overlay, this is what I'd do".

The related work section shows some of this. They don't really provide an argument as to why their system is superior to the others. They just give a big list of other work.

SRM

This describes Scalable, Reliable, Multicast. It uses some naming and ack tricks to get basic functionality, then they implement a whiteboard app with it.

Ok, so nothing tricky. They pointed out that Multicast doesn't fit with end to end, which is obvious enough to have been a brilliant observation. I now want to write a paper on end (to end)^n just so that it exists. It's a good point that I don't think I've entirely digested. In the overlay, you just create n^2 connections, each end-to-end. Are these equivalent? The notion of fate-sharing was what they used to differentiate the two. This is tricky, and I'm not in the right place to reason through this correctly.

There's a somewhat tangential interesting point there. Multicast is equivalent to many unicasts. If you buy the hirearchy, you can implement all of this above that. This is probably why multicast doesn't matter that much. With that, we get to keep end-to-end and the existing routing infrastructure, at the loss of performance for a very small set of applications.

Either way, they pretty much implemented bittorrent in the paper filler, explaining possible uses of multicast with caching. That's when you know it's an important work: something like a "future work" section creates an industry.

Overall, I probably don't have much to say here. It's not too surprising how they did this, and that they punted the ordering stuff to a higher layer.

Monday, November 17, 2008

DTN

This is going to be brief, as I actually work on this. I'm currently implementing version 6 of the bundle protocol and TCP convergence layer in python. I've decided to be completely negative here as well. Hopefully others will have the discussion of why this is so fucking sweet.

The biggest problem in DTN is that it doesn't solve a lot of the problems it proposes. Satellite networks? Sure, those are multihop with limited connectivity. Developing regions? Ehhh... most connections are one hop. Cell phone to tower is the only connection with disruption. Everything internal is good. Sensor networks? They don't want the abstractions, as the overhead is too high. Also, established wireless protocols seem to work fine.

The key thing about DTN is that it's so general. It applies to every network, but it isn't optimized for the characteristics of the network itself. With that, it has to compete with networks specifically designed for the properties of the network. It can't. We need graceful degradation, allowing for transitions as network conditions change. DTN is a big broad hammer, encompassing everything. The next step is to morph that into something that can compete with scapels, not just networks where nothing currently works.

DOT

DOT describes the "data-oriented transfer" service. The idea here is to separate the data transfer, and stick another layer in our fat protocol stack. It's really heavily related to my class project, actually. Lots of the same issues, more people trying to get practical value out of the DHT work.

I'm not totally sold on loving or hating it. It seems completely unreasonable, but I'm not sure I can put my finger on why. It doesn't optimize the common case, as they point out. Flexibility is nice, but only when you are solving a problem. They are not solving a problem really, rather just trying to allow for a design space where there currently isn't one. This means a system like this will never be used, but it doesn't mean it's bad work.

I should note, that one metric for success the authors had is that the SMTP client they build was robust enough for one of the two authors to use. I'm sold.

I do agree that this is more elegant. That may be the fact that I'm currently implementing a system with a lot of parallels to this. I think my biases will be laid bare in class.

In conclusion, this paper may be an argument as to why my yelling about metrics last class was wrong.

Wednesday, November 12, 2008

X-Trace

What's the X stand for? Extensible? Extra?

Anyhow, X-Trace is Rodrigo and George's work on pushing tracing into the appropriate layers to get a view of the entire system. With this, debugging is easier. It does this in the obvious ways, and has the obvious problems.

The big problem for this is adoption. To use X-Trace, you have to instrument it, which means writing specific code in each protocol you want to trace. That's a huge headache. However, they deal with this well, allowing (limited) incremental adoption as well as focusing on an area (datacenters) that has the amount of top-down control needed to push such a sweeping change.

Performance is another problem. They analyzed the performance hit of their daemons, and showed it's not a huge problem. However their apache trace took a 15% hit. Assuming this is high as it's research code, that's still huge. The obvious thing to me is to instrument only a limited set of things, or to be able to turn it off until you have an error, then try to reproduce it on a limited number of servers running the service. I think they eventually did this as well.

I wonder how related this is to debugging on multicores. I argued with andy about wanting a distributed GDB, and this is approaching the ballpark of such a system.

Internet Measurement

This is probably the densest paper we've read. It's an in-depth analysis of TCP's behavior. It attempts to analyze the assumptions we have when building TCP, just as the network's infrequent reordering to the packet error rate. It's an immense work.

On a note, I'm going to start a list of worst project/protocol names. New on the list: SACK. SACKs are not new to me, but this is a new list and I've recently been reminded of it.

The usual complaints apply to this work. It's old, we're not sure how relevant the findings are to the modern internet. There were many reorderings and bursty losses due to routers updating their routes. This is presumably less likely now. Follow-on work would be great to read, as it would show what changes were implemented in reaction to these finding (not many I'd wager).

I really like these deep, measurement papers. There's so much nonsense about building a system when there's such a light understanding of the problem you're trying to solve. This work likely led to tens of future projects for exactly that reason. There are plenty of engineers in systems, we need more analysis.

Particularly, I want more social science techniques in systems and networking. This is probably a deeper analysis of user cases. We build so many technologies that are solving problems that don't exist. They get into SIGCOMM, put in a binder and on a CV, and that's it. Though, to be fair, that may just be academic problem...

Anyhow, I feel like I had something else of value to say about this work, but I can't remember. Perhaps I'll update once I remember.

Thursday, November 6, 2008

i3

Matei lied to me and told me that this was the better paper of the two.

i3 is a fairly obvious scheme to provide mobility and multicast with an overlay. There's a few interesting implementation details that they tweezed out of the idea, but none are crucial for the actual design.

Again I come to question that has haunted me through this class, adoption. Overlays are nice for adoption, as you presumably control each client. This works particularly well for p2p, less so for others.

A big part of this paper was being general and applying to traditional servers, which don't need this. You only pay a performance penalty if there is no mobility or multicast. The lack of these is the common case. I also think it will remain the common case as we deploy more wide area wireless networks.

So, this really fits mobility and multicast in p2p networks. Each has interesting use cases I think, multicast is nice to steal stuff and mobility will allow a large class of applications on personal communication devices.

Wednesday, November 5, 2008

DOA

Woah. First thing, don't name a project DOA. Name it something better, like PANTS.

Secondly, this is 16 pages about a fairly simple idea. The diea is to generalize middleboxes in some way, dealing with all of the issues the things bring up. The most common issue is addressing machines inside of NATs, as their addresses are meaningless outside of the LAN. These guys define a new namespace that is global and flat, fudge a DNS scheme, and allow the packets to give a source routing like scheme.

This is an interesting point though. Essentially, source routing solves all of this, right? I mean, if I send a source routed packet to a NAT box, with (192.168.0.10) as the last source to route to, it would work. Assuming local DNS (such as avahi) you could make the last source be: (darth-vader) or (waterloo) and get the packet there without global naming. I suppose that the NAT will need to be addressed in some meaningful manner, but those usually are globally unique.

Huh, that might be a good idea.

Anyhow, this work was good, but it's got that "never going to be used" problem, as it requires both sides use it to get an advantage. I don't think this is inherent to the solution either, as my thing above is a slightly more reasonable version of this. For instance, a VoIP app may just broadcast a "register" packet saying "hey! I'm listening on this port for VoIP, if you get one, give it here". Then you've done some of the delegation they speak of, without the new naming scheme. You can get looked up via traditional DNS and bam, way around that punching a hole crap.

Lastly, note that skype fixed this with a big server in the real world. Both clients talk to it, and then skype tells each client what port the other has open. Doesn't work for pure P2P, unless you can negotiate a P2P node to do this for you...

Sunday, November 2, 2008

DNS Caching

This was a dense work from MIT and KAIST where they gathered traces of DNS traffic to determine the effectiveness of DNS caching. There were two primary findings: DNS requests follow the known zipfian distribution, and low TTL DNS entries do not really affect the caching.

This was really really dense with a whole lot of figures and percentages. I think I followed most of it, with the argument that the zipfian distribution is correct being the most obvious. They argue it shows that caching is not that important, as most users only use the cache for a few minutes as they browse the same site. This is important as servers are using TTL-based load balancing.

Note that this only applies for addressing, not forwarding. I think this is a crucial point, as it allows us to distribute the load at that level. Since it's likely amazon.com owns that hardware, TTL multiplexing makes a lot of sense.

Interesting bit about scaling out DNS. I'm always interested in how these things have changed, as I feel like the internet has become much more stable since 2000. Then, the obvious question is: how did they stabilize it?

DNS

This paper was strange. I know DNS, and this paper actually made me a little more confused. I expect it was mostly terminology. Zones, for instance, are a strange name for administrative domains.

The paper itself was great, as it dealt heavily with an issue very close to my heart; technology adoption. As I work in Information and Communication Technology for Development (ICTD) getting users of my technology is of paramount importance.

The HOSTS.TXT file was a perfect example of "good enough" technology, which is the biggest obstacle to adoption. It's just not worth it to the users unless the benefits of the new technology outweigh the losses from adoption. This is why it's nearly impossible to get new networking technology adopted. The advantages are too small compared to the risks.

The DNS folks lamented a great deal over this fact. The users who did not switch caused tons of problems, and the users who only partially transitioned caused the most. I think that Berkeley TCP implementations were probably the definitive reason that TCP is so widely adopted.

I'm not sure exactly what I'm trying to say. I just want a more involved discussion on how to push network technology. Right now you have to implement it at user level, that way people don't need to monkey with their systems to use it.

I'm rambling. I'l bring this up in class.

Thursday, October 30, 2008

DHTs

I've decided to put both DHT papers into the same post, as they covered a lot of the same material.

These were papers on distributed hash tables. They what they seem to be, but there are some clever tricks in each individual one. You hash an address and this then maps to another machine via a series of lookups.

What I don't understand is how these things help P2P, as is argued at such depth. Since you don't get to organize the data in a pure P2P network, you can't really create any address -> data mappings. Both are handed to you, you can only create a search service that gives you one if given the other.

I do like DHTs as DNS replacements though, that seems like the proper model of usage. This is an actual problem too, as I can remember comcast's DNS server choking and access to goggle being hindered.

I guess I don't have much to write as we read the Chord paper for 262. All of my clever insight is gone.

Monday, October 27, 2008

Active Networks

I still don't really know what active networks are. Wiki says:

"The active network architecture is composed of execution environments (similar to a unix shell that can execute active packets), a node operating system capable of supporting one or more execution environments. It also consists of active hardware, capable of routing or switching as well as executing code within active packets. This differs from the traditional network architecture which seeks robustness and stability by attempting to remove complexity and the ability to change its fundamental operation from underlying network components. Network processors are one means of implementing active networking concepts. Active networks have also been implemented as overlay networks."

That didn't help too much. I suppose it's reasonable that the applications should be allowed to reform the network. However, as my previous post said, this isn't going to optimize throughput, and thus won't be of huge value.

Is this a formative work for overlay networks?

Rambling aside, the paper itself was a survey of the lessons learned in implementing such a system. Not terribly valuable, in my own view.

Lastly, I am intrigued by the idea, at least for the DTN case. DTN's are highly mobile, with the network shifting around all the time. It may be valuable to modify the network architecture in this case. Then again, I barely understand this to begin with. I'll muse more after lecture.

RON

Ron is a really good name for a project. It just reads well.

RON is a "Resilient Overlay Network". It makes a lot of sense in an area where there are significant network problems. The overlay allows for more informed, better routing decisions. Specifically it routes around trouble spots in the internet. It can also be used to enforce policies among the routers that can't be enforced at the BGP layer.

The largest problem with this paper is that their justification went away. I very seldom experience outages. In fact, I can't remember the last one. I do know that my last outage was my home router anyhow. People get paid a lot of money to make sure that core routers don't tip over. These guys did not anticipate the internet becoming quite the serious business it is now.

My guess is that is early "Look at fun stuff we can do with overlays!" work. This is valid for spotty networks, but I've developed a hypothesis from our readings in this class. Anything that doesn't optimize throughput eventually gets phased out. In the common case of a working network, the network engineers have decided that you should take this path to google, and they know WAY more than you about their network setup. You should probably trust them.

Oh, and another note. Fantastic use of e2e!

Sunday, October 19, 2008

Internet Routing Topology

This paper details the problems with the previous power-law view of network topologies. Their complaints are obvious in retrospect, as the power-law view doesn't take actual network requirements into account. They then demonstrate that incorporating actual networking requirements (throughput being the big one) into the construction of network graphs improves the modeling ability of said graph.

There's not a lot to say here really. I buy it, but it's just the normal interplay between theoreticians and practitioners. The theory folks build general models and the engineers want exact networks.

I personally side with the engineers and I find this work to be valuable. The best answer is to test on the real network, and get actual data from industry.

I'm surprised this is recent work. I suppose the internet has grown so fast that no one is exactly sure of what it looks like on the inside. The business concerns limit the amount of information that we have about the internals.

This is rambling now, but I think taking reality into account does lead to better mappings.

Power Laws

An interesting work that demonstrates the 1998-era internet can be described concisely by some power law relationships. The particulars of the relationships are not that important.

I totally buy the argument, as it's clear that there's a generic topology that should be consistent throughout the network. As the paper was written for the 1998 internet, it's likely that the boom of the late 90s to early 00s was not anticipated. I'd like to see a reassessment of this work for the modern internet. I should mention that they explicitly said that their assumptions do not account for the boom and bust properties of technology.

I do question the usefulness of this work. I see the value in being able to build reasonable approximations of the internet. However, this sort of mechanism only applies in areas where it's impossible to directly measure the network. Sensornets, datacenters, and the like are small enough (and generally have design documents) that we don't need to approximate anything. Perhaps it would still be valuable to model these other networks as university researchers may not have access to the designs of the other networks.

I like the design of the work. It's very systems to build something and then figure out the theoretical grounds for it, rather than the other way around. These heuristic works make sure that the theoretical backings are of use.

Thursday, October 16, 2008

Blank!

I'm skipping the sensornet readings this week, as I have the TIER workshop on Friday. Normal ramblings will commence Tuesday of next week.

Wednesday, October 8, 2008

XORs in the Air

Hah! I walked away from reading the previous paper convinced I had a good idea for wireless encoding, and then this paper does just that. This paper uses an xor encoding of packets to send multiple packets at the same time. The logistics of it are complicated, but it works, and works well. Totally fantastic.

I'm not sure what else to say. This is a totally reasonable way to exploit the gains inherent in a broadcast medium. Their insight into the benefits given to the bottlenecks was great as well.

I still like my idea of using erasure coding, but that's just going to maximize throughput, not utilize the network more effectively. This allows wireless networks to get advantages for being highly packed, which the roofnet folks never addressed.

The only thing mildly overlooked is security, which I think isn't a problem either. End-to-end encryption should provide any guarantees, and there are definitively no new attacks generated by using this.

I'll stop fawning, but drop the other paper and emphasize this heavily!

ExOR

This paper is a follow-on to roofnet and ETX. It describes ExOR, a broadcast-based routing algorithm. The basic idea is simple: You broadcast a packet. Those that hear it correctly decide amongst each other as to when they've received it. Then, the one closest to the destination does this again.

That's the story anyhow. The implementation is a mess, with "bundling" of packets required to mitigate the inevitable loss, and then traditional routing to deal with those lost packets. The latency losses for such a system are enormous, but that's not discussed at all by the authors. They simply emphasize throughput as some godly metric. There's no discussion of scalability either, as these gossip algorithms won't. This seems nearly wholly unusable.

That's not to say that there are not clever ideas here. It's clear that a great deal of data is wasted in a wifi network because of broadcast. Because only one router can talk at a time, we should gain some benefit by forcing the others to listen. The authors listed erasure coding in related work, but said that their system did not need to identify specific paths, or disjoint paths. That's true, but only in a superficial way. They do identify the optimal cost path, for instance.

I like the erasure coding mechanism more. I see that they are attempting to deal with the broadcast properties, but this is not correct. It seems to me that doing the following would be better:

S broadcasts.
All others hear it. You wait (random * error rate on the packet) to broadcast yourself. This means that those who got it better will broadcast first, getting the packet along. Also, the erasure coding will allow the first two or three packets to get to the end, and allow for reconstruction there.