MapReduce scheduling

MapReduce is fairly new and Hadoop implementation, as described in the paper , seems rather primitive and has a lot of room for improvement. I am not saying the creators of Hadoop did not do their job, but rather systems like these take time to evolve themselves. LATE is a big step towards improving its performance. The best part about this paper is that it is easy to understand , contrary to the usual scheduling paper where lots of math are used to describe their scheduling policy.

Enough praises.. I didn't like the parameters. I know the authors spent two pages of sensitivity analysis justifying them, and I respect their diligence. I just don't trust such static parameters can adapt to such a wide range of workloads. When things get overly complex, can we autotune it like how parallel programming community has done? It is almost impossible to predict performance because there are so many variable factors involved.

This work has much potential, especially because map reduce is merely scratching the surface of many powerful parallel distributed computation models. Many of these are only possible because of the rapid increase in network bandwidth. However, there is still significant differences in network bandwidth between different hosts in a data center. The scheduling decision here does not account for network topology and current machine workload. There are risks to using machines near the straggler as backup though, there is a higher chance for correlated failure because of network issue or machine issue (for a different thread / core on the same physical host)

All in all, this paper is great, but surely there are a lot more to be done.

Policy aware switching layer for data centers

This paper describes a way to insert middle boxes into the network in a logical but not physical fashion. This certainly relates to previous paper we have read that argues why middle boxes are disliked by the academic community because they break certain assumptions that were made during the design of the Internet.

Given a controlled environment such as Internet data center, the designer is essentially given the freedom to start from a clean slate. This allows this work to have a chance to be deployed as supposed to be a pure academic exercise, which I am really looking forward to. I suspect only real deployment will tell whether the complexity in its design is going to be an issue in daily operation or not.

In addition, I am worried that the performance overhead in the design (presenting itself as reduction in throughput as well as increase in latency) is going to render the system not cost effective economically. I am not sure how much of it comes from the fact it is Click-based and its software overhead, but it would be nice if authors could have attributed the overhead in more detail. (or perhaps our course project would help)

Delay Tolerant Network

The author argues the TCP has fundamental assumptions that are broken in "challenged" networks both in network characteristics and end point capabilities. Instead, the author proposes an architecture that is delay and link loss tolerant using a store and forward overlay to interconnect them.

I liked the ideas behind this paper and more importantly, the ideas in the paper have been in real deployments which is always a validation of the work. Although I am not sure if the rural areas are truly connected using this sort of technology. To have seamless transition from normal network to "challenged" network, the interface needs to be much more general. Most application written today rarely handle network failure gracefully, and to have these networks as functional as well connected networks, I believe network infrastructure is merely a first step. An application framework that makes failure handling explicit is also needed.

An Architecture for Internet Data Transfer

This paper describes an architecture to separate data transfer mechanism and the setup of the transfer, and thus enable the use of innovative transfer methods such as multipath and peer to peer protocols.

Overall a fairly straightforward idea, essentially a level of indirection to transfer large amounts of data using an asynchronous I/O model (receiver pull) . It uses plugins to add new transfer mechanisms to the system while maintaining backwards compatibility. It also divides data into chunks so that optimizations such as caching are more effective.

I think the main advantage is that this architecture allows features such as multipath and caching to be added hidden behind a very general interface. This is very powerful, but it allows little application control over caching and multipath policies. These plugins are ultimately shared resources between different application and I don't think the current design expose any application control over this. For example, if a bulk transfer happens between US and UK millitary , they probably don't want their data cached in intermediate nodes in other countries or want to control the multiple path selection process.

XTrace

This paper talks about tagging data and trace through different layers of protocol to provide better diagnostic tools in a distributed application. Overall a very good idea, as many applications are very difficult to analyze when it breaks down and faster diagnosis can lead to shorter downtime.

I assume this is to be used in online fashion. So it works like insurance against potential failure. There is some cost to instrument code to use xtrace, however it will likely reduce the pain when problem happens. Is this motivation strong enough for a company to adopt? How does this compare to the google approach of running multiple copies to buy them diagnosis time.

Also because this is online approach, performance overhead can also be a problem. But it is justified if it reduces the number of fail over copies a deployment needs.

Because X Trace is designed to be deployed across many ADs, if there is a bug in XTrace, it could potentially introduce correlated failure, which worries me a bit. Now things like performance bugs are multiplied and security bugs allows attackers to attack multiple ADs at once and through the entire application.

End to End Internet Packet Dynamics

This paper reports a large scale study of Internet performance using daemons installed on more than thirty nodes. The study goes on the conclude a list of result about various irregularities seen in Internet routing. It clears some misconceptions and shows that these irregularities do happen and sometimes frequently. Many of these irregularities also happen in site dependent fashion.

While many of these results are interesting facts and potentially lead to other further investigations of Internet irregularities. However, I feel the more valuable lesson from this particular study is the process of evaluating Internet performance at large scale. They were able to obtain a controlled experiment environment by embedding network daemons at various sites. I feel it will be more and more difficult to convince organizations to participate in today's world, especially non-academic settings.

They mentioned that they used 100k data to test bulk transfer. That seems quite low for any network today, and perhaps even low for Internet in 1995.

i3

This paper presents an Internet overlay that delivery packets in a rendezvous fashion. I think it is a very elegant solution to the problem of mobility and multicast, because ultimately the data is what the receiver is after. Its location is only a mean for it to obtain that piece of data. This sort of reminds me of web mail but with a much tighter latency constraint. We get mobility of webmail by having a pull model instead of a push model, however it is certainly too slow if we do the samething at packet level. So i3 essentially uses webmail model as control plane and establish a fast data path for more packets.

I like the basic idea behind i3. I am not certain the implementation can be widely deployed due to the problem in scaling up. They are already seeing some performance overhead with using DHT as trigger maintenance method. Nevertheless this model of communication opens up a wide range of possiblities to improve and hopefully overtime there will be innovation in the details of implementation of such system that overhead and scaling problem can be resolved.

Middlebox no longer considered harmful

This paper presents a new architecture of routing and naming so that the design of the Internet makes incorporating middleboxes easier. The authors argue that although middleboxes violates two of the tenets, the reason is that original Internet design is not flexible enough.

The new design uses the notion of EID to serve as global unique identifier, and uses method such as delegation to hop from one EID to another EID. This is how they enable middleboxes not on the physical path. It depends on DHT for naming lookup, translating EIDs to IP addresses or other EIDs.

It wasn't particularly clear to me that the problem with NAT and middleboxes are very serious. I think as ugly as middleboxes and NATs are, they are working fairly well. Everyone is buying them and manufacturs are coming up with various configuration tools to make sure they are set up correctly. This architecture has a clean design to it, but at what cost? Having an entire routing architecture depedant on a dynamic system like DHT just sounds like a bad idea. Particularly because the DHT is on the critical path of every flow until it is cached. The author recognizes the latency of DHT look up as a problem and throws out the caching as a general solution, but I think it is more difficult than that. Also the distributed nature of DHT makes it hard to find problems should one of the node respond slowly or fail.

DNS Performance and Effectiveness of Caching

This paper studies the performance of DNS by taking traces at two campus networks. The result was surprising because I rarely have issues with DNS lookup. Even more surprising is the fact that a large percentage of lookups are never answered.. I suspect the situation has improved since this study was done. Perhaps we need to do another round of study of this sort.

The authors conclude that since short TTL is being employed for a number of applications such as loadbalancing, NS caching is far more effective compared to caching of the actual result. The number of referrals have significant impact on the latency of the lookup.

I like this paper and this sort of large scale studies on the Internet, because there are just so many factors that affect a typical user's Internet experience. Users often do not know where the problem is when they experience a problem. DNS certainly would not be the first place I think of when I have connectivity issues.

Development of the Domain Name System

This paper describes the Domain Name System, which is the de-facto standard in Internet naming protocol. It describes the original goals of DNS, how it evolved and the design decisions behind DNS. Compared to other descriptions of DNS I have seen before, this paper focuses much more on the broader case of resource look up rather than the narrower sense of translating domain name into ip address. Unfortunately, some of these features such as multiple type and class did not see significant expansion even until today. This is not an isolated instance where systems were designed over generic.

In general, I liked this paper because it gave me a lot of historical perspective and the shortcoming and surprises that authors did not original expect. However, the description of DNS in this paper reads too much like a functional specification. A lack of typical usage pattern can cause some confusion for someone who is not very familar with DNS (me). In this respect, I find the second paper to be more helpful.

Chord

This paper describes in detail the design and implementation of Chord DHT system. It is a dynamic system that allows efficient content retrieval based on key value pairs and without centralized coordination.

The central idea to CHord is consistent hashing to allow some ways of balancing the load on different nodes in the chord ring. To further enhance the performance, Chord uses finger tables to allow O(log n) look up time of a particular key in the ring.

There are a couple of issues in this paper that were not clearly addressed. Issues such as fault recovery and migration of state between nodes on a planned take down of a node seems central to the correct functioning and operation of chord ring but received very little attention.

Another problem with this design is the latency in the lookup. Although Log(n) in terms of number of nodes in the hash space, the delay is still significant. Also each hop in the chord ring is an overlay and might translate into multiple hops in IP.

Overall, I still like this DHT compared to others in that it is simple to follow and works reasonably well. As system designers, in many cases, we tend to over design a system and makes it difficult to get implementation right. At some point, law of diminishing return kicks in and it is better to use the simpler design. I think Chord strikes a balance between simplicity and functionality, which is why it is one of the more popular DHTs.

Looking up data in P2P systems

This paper discusses reason behind P2p DHT like systems. Main reason for it is for fault tolerant data look up. They depend on symmetric lookup instead of hierarchical lookup. This way, no single failure is going to bring down the network , however, they tend to not scale as well.

The paper compares different DHT systems based on how they organize the data structure for key lookup. (tree vs. skiplist) and poses a number of open problems.

I like this paper because it gives a gentle introduction to set of problems in DHT and motivation behind it. It also gives nice taxonomy of different DHT project, which serves as a nice lead in to Chord.

Active Network

This paper talks about Active Network. Active networks allows per packet specific processing and embed the processing inside of packet using the concept of a capsule. This gives the network the flexibility to adapt to different need quickly and allows rapid deployment of new protocols.

The main problem that I see and author recognize in this setting is security and performance. To address security, they are using a restricted subset of Java. However, I don't think they are considering the problem of resource exhaustion. Of course, they have a certificate based solution as back up. However, that is very heavy weight, and usually the root trust has to be traced to one entity. I doubt all the networks in the world would trust a single entity to certify active code running in their networks. Subtle problems such as routing loops can occur simply because of a bug. Performance is also a critical issue. If the active content is not cached at the node, loading the node could introduce significant latency.

I like this paper in the curriculum because it introduces necessary background of active networks and gives some reflection on the experience of implementing such a toolkit.

RON

This paper describes an overlay network that is designed to improve recovery time in routing when failure happens and integrate path selection and routing more tightly with distributed applications. They argue that BGP infrastructure takes too long to stabilize.
Ron addresses this by forming a relatively small scale overlay network and maintain link state information to other Ron nodes. It actively sends out probes periodically to detect outage relatively quickly.

I like this paper because it gives a clear goal of overlay networks. It is usually designed to solve a particular issue that is difficult to solve without overhauling entire routing protocol. (in this case, BGP) However, just by limiting the scale of the problem and implementing functionality at application level, RON provides a practical path to deploy such systems. I think that is generally a big win for overlay networks and that's why they have been such active research areas.

Power Laws of Internet

The authors proposed thee laws of power relationships on the topology of the Internet and used measurement studies on a sample of the Internet to validate these proposals.
1. The outdegree of a node is proportional to the rank of the node to the power of a constant.
This is useful to estimate the number of edges in the Internet as the function of number of nodes.
2. The frequency of an outdegree is proportional to the outdegree to the power of a constant.
3. The eigen values of a graph is proportional to the order to some power of a constant.

I find this paper to be somewhat strange. The author proposed three laws based on some intuition and used specific sample to validate those claims. This somehow lacks rigor and it seems to be that there is no way to know if the same law holds today without redoing a comprehensive measurement. Perhaps there is something significant that I am missing, but I find this paper to lack some rigor and I was hardly convinced after reading it.

XORs in The Air: Practical Wireless Network Coding

This paper describes COPE, an encoding scheme that takes advantage of the wireless broadcast communication pattern to mix packets from different sources together to increase the amount of information conveyed using a fixed amount of packets sent.

This is definitely a neat idea. However, this scheme seems rather complex to implement because it violates so many assumptions that network applications now assumes. TCP scheme will likely not work well with this either since the batching of packets can be seen as a source of delay.

ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

This paper describes a technique that combines MAC layer and routing together. This breaks the conventional layering structure in network protocol, but offers better throughput as now it takes advantage of the slight chance that some packets might get "lucky" and travel further than it could reliably transfer.
The main problem with this scheme is how to prevent the overhead of communication between the recipients from overwhelming the benefit the scheme might offer. ExOR did the following:
1. batching of packets
2. use of batch map with packet transfer so that information is transferred at the same time as verifying the previous hop's transfer.
However, because this scheme is not compatible with existing TCP protocol, dedicated proxy is required to convert TCP connections into this kind of connection. This could be an obstacle that prevents its wide deployment. Many other technically superior solutions are not deployed because of compatibily issues.

A High-Throughput Path Metric for Multi-Hop Wireless Routing

This paper describes the underlying routing protocol used in Roofnet, called ETX (expected transmission count). The key idea is that wireless medium breaks the assumption that link is either working or not working. Minimal hop count can be suboptimal because the smaller the number of hop is, the chance of a weak link increases. Instead, ETX considers three factors: transmission loss ratio, assymmetry in the network link quality, interference causing reduction in throughput as the number of hops increase.

I liked the paper because this scheme neatly integrats all of the three mentioned dimensions that affect the throughput of the route. It also has extensive evaluation to prove the ETX is more optimal than minimum hop count in most cases.

The environment described in this paper is very similar to that of Roofnet. Certainly in a loosely connected Roofnet environment, because ETX considers link quality in its routing decision, it provides better quality routes. However, if the environment is changed to a densely connected, corporate environment, would ETX's overhead of link probing make it unsuitable candidate to use in these settings? Even in roofnet, some parts of it (i.e. near MIT campus) would be much densely connected. In these settings, I would argue interference is much more important factor to consider than loss ratio. Smart channel allocation will probably provide a much better gain in throughput.

Architecture and Evaluation of an Unplanned 802.11b Mesh Network

Compared to the previous paper, which takes the route of simulation, this paper is much more convincing since it carries a physical deployment in a real environment. There are so many factors not modeled(or difficult to model correctly) that can have significant impact on network performance in complex urban neighborhood. (Obstruction, interference , etc.)

The main contribution of the paper is the evaluation of the multi hop routing performance and their routing protocol Srcr which tries to find highest useful throughput rate between any pairs of nodes. It seems plausible in urban environment because of the high density of quality links, this sort of sharing between different home users can boost speed even higher (due to time multiplexing) and possibly guard against outage of a single provider.

Modeling Wireless Links for Transport Protocol

This paper summarizes a series of issues in current modeling of wireless links and how these inaccuracies can lead to potentially incorrect design decisions for transport protocol. As the underlying link layer characteristics change, the upper layer would need to adapt as well to perform optimally.

This paper characterizes many aspects and details of wireless network that makes it so hard to get accurate model. However, after reading it, I only feel that no matter how careful my model is, it is still not going to represent reality accurately enough. Certainly modeling is much more efficient to evaluate a new protocol or a proposal to change an existing protocol, but all I got from the paper is that modeling is probably never going to be good enough. Now I feel to make a very convincing argument, I will need real deployment data. Perhaps modeling would only serve as a first level filter in a feasibility study.

That leads to my second question. Given limited time to develop a model just to check if my protocol has a chance to perform well, which of these characteristics should I consider. This was not answered in the paper, and I feel that would benefit me and other network researchers a lot.

This paper is still an excellent paper to read, since it summarizes many link layer characteristics in different wireless networks that directly lead to many decisions that we made at the transport layer. It also serves well in the curriculum as a lead-in to a number of more detailed wireless papers.