Thursday, October 30, 2008

Looking Up Data in P2P Systems

This article begins with a discussion of centralized vs non centralized indexing structures in P2P systems. Entirely centralized systems, such as Napster, contain a single point of failure. This is the fundamental problem which subsequent systems aimed to solve. The article moves on to a discussion of some such symmetric, structured systems. They contrast Chord's circular skiplist routing scheme with tree-based routing schemes used by Pastry, Kademlia, and Tapestry with CAN's d-dimensional space based partitioning abstraction (which makes intuitive sense to those who are comfortable thinking in spatially).

They make a largely unfounded claim that P2P systems are useful for a lot more than illegal music sharing. However, for the most part, P2P systems haven't seen widespread adoption for problems other than illegal file sharing (you nerds in the back of the room are quick to point out that bit torrent is used to distribute various flavors of linux, but that was an already solved problem, sit back down). Why?

To rephrase, why do the LARGEST distributed systems in the world, those run by internet giants like Google and Yahoo, still run software stacks (such as MapReduce, Chubby, etc.) that are engineered to contain a small number of points of failure? I say it is because we have come to realize that the performance and complexity cost of making our systems entirely symmetrical is not justified. Instead we use replication and psuedo-distribution of mission critical centralized services to provide resiliency.

The only time we find value in a fully symmetric system is when we don't want to or can't have a centralized authority. However for any legitimate business use, we DO have a centralized authority, that being the business itself. This leaves a very narrow market for the justified use of these symmetrical systems, i.e. illegal or ad-hoc file sharing.

Before this, I hadn't read about any DHT's other than Chord, so I appreciated the abbreviated introduction to such a variety of other DHTs.

Tuesday, October 28, 2008

Active Networks

ANTS is a network toolkit that allows any user to inject his own code into the network layer, which applies only to his own packets on the network.

Their architecture uses Active Nodes which recognize and run network code which is embedded in packets (which they call capsules). They do provide a road map for incremental deployment into the current Internet.

This idea shares a lot in common with Overlay Networks, but includes lower level hooks.

Resilient Overlay Networks

Streaming thoughts as I read:

An application level networking protocol that sits on top of traditional IP and performs better both in the face of failures and generally (in terms of loss rate, latency, throughput).

-in the abstract they say that RON proved to be highly resilient to 32 outages, each over 30 minutes. However, they don't tell us how the traditional routing protocols (i.e. BGP) fared at handling the same failures. They get to this in the introduction, but I think they should cover it in the abstract.

-Is the performance of a twelve-node RON, representing 132 measured paths, representative? does this scale?

-plausibility of use in real world when ASs _are_ competing businesses? good for schools or other cooperating ASs i guess.

-they list some applications: overlay vpn and overlay ISP. has anybody built either of these?

-is a 5 percent loss probability improvement in 5 percent of samples significant enough to brag about? Did they see _any_ improvement of the same metric in RON_2 as well? if not why not?

-they found cases where RONs latency and throughput optimizing path selection algorithms found different paths? Couldn't this just be correlation and not causation (probably/hopefully addressed in the evaluation section)

-Because routing is done at a higher level, routers can make routing decisions based on metrics which are relevant to the service they are supporting.

-Uses Link-state routing by default.

-RON allows for a lot of policy to be specified as part of the routing policy.

-They implemented RON as a c++ library. They implemented a RON IP forwarder.

-Summarized nicely in table 1, they looked at three things: 1) RONs ability to detect/recover from dropped links. 2) RONs performance improvements in latency, throughput, loss rate. 3) stability of RON routes.

-Re 1, how big of a problem is this really? I am not convinced that this is a real problem with traditional BPG routing. Re 2, the improvements were good, but not great.

-They address problems that RON introduces with NATing, trust issues (RONs require trust), and scalability ("the RON design trades scalability for improved reliability")

Sunday, October 19, 2008

On Power-Law Relationships of the Internet Topology

This paper was a refreshing diversion from many of the protocol and systems building papers we have been reading. They grabbed three graphs, each separated by 6 months, of the Internet from the National Laboratory for Applied Network Research and plotted some simple statistics using log-log scale and noticed a lot of straight lines. Ha.

Axis of each powerlaw:

  1. <node rank (based on # of fanout connections from node), fanout>

  2. <node rank, frequency (bucketing fanout)>

  3. <# of nodes within range, radius of range (# of hops)>

Are #'s 1 and 2 very different?

Distributed Diffusion

This seems like a vision paper wherein, instead of talking about motes that currently exist, they speak about the "expected capabilities of sensor nodes." Judging by the motes we looked at in class Thursday, their guess was decent in terms of size and performance though the TAG paper focused on motes with much slower processors.

While they start with the observation that the organization of a sensor network can "begin to look like a distributed computing system," they are quick to point out that new techniques will be necessary to account for node failures, temporary outages, and power limitations.

As opposed to TAG's SQL like declarative language, Directed Diffusion uses attribute-value pairs to specify a set of data that the operator is interested in. Interests are diffused into the network and when a mote has a response the answer is sent along the reverse path that the interest came in on.

More simulation, but then that makes sense because it sounds like real sensor nets are still a brain child at this time.

Figure 3 is confusing.

The examples they use throughout the paper (tracking animals) are somewhat less compelling than the pie in the sky applications enumerated at the beginning of the paper. As we discussed in class, the reality of sensor nets has been somewhat less impressive than the early dreamers envisioned (remote geographic regions or toxic urban locations). Though I believe that some grad students here at Berkeley have done some work with sensor nets tracking sun exposure around berkeley and in forest settings (I think somebody gave a sys lunch talk about this last semester), so maybe we were being a little premature in class when we bashed this paper.

TAG - for sensornets

This paper explores an in-network solution for aggregation services in a sensornet.

The basic idea is that by thinking hard about the various types of aggregation functions that we find useful we can devise ways of cutting down on the amount of network overhead required to inject a query into the network and collect a response. In particular, we should throw data away at every available opportunity.

I really liked the taxonomy of network queries they presented, but i am fond taxonomies in general, so i might be biased.

My complaint is the typical one, that while sensornets seem to promise the world, more details about a real world deployment which actually worked would be nice, simulations only take us so far.

I also found the math in 3.2 unnecessarily complex, or under explained, or maybe I was just too lazy to re-read the section a couple of times to really understand what was going on.

Thursday, October 9, 2008

XORs in the Air

This paper discusses the technique of capitalizing on the broadcast nature of wireless networks. Since nodes in a wireless network unavoidably overhear packets that weren't intended for them, we have the opportunity to capitalize on this by XORing multiple packets together and sending only one packet the encoded form of arbitrarily many packets. This is genius!

Monday, October 6, 2008

Ad-hoc routing protocol showdown

This CMU paper from mobicom '98 uses simulation to compare the performance of ad-hoc routing protocols DSDV, TORA, DSR, and AODV.

They had to modify the ns network simulation software to account for node mobility, a more realistic physical layer, wireless NICS (not just wired), 802.11 MAC using DCF.

They also implemented each of these protocols and discovered, along the way

Not surprisingly, they found that node mobility has a negative impact on performance. Beyond that, the protocols break into two classes. This is obvious when looking at the shapes of the curves in figure 3. As the paper puts it, "TORA, DSR, and AODV-LL are all on-demand protocols, and their overhead drops as the mobility rate drops. As DSDV-SQ is a largely periodic routing protocol, its overhead is nearly constant with respect to mobility rate."

In a recent conversation with Ion Stoica during a meeting about experimentally reproducing a transport layer congestion event coined incast, I inquired as to the value of simulating incast vs. reproducing it using a real switch and nodes. Ion was less than enthusiastic about simulation, so we are moving ahead with a real experiment. This made the think about how there seems to be two camps in network research, those who simulate and those who run the real experiments. We have a number of paper from both camps. Here are just a few of the papers we have read which fall into one or the other.

  • XCP
  • RED
  • CSFQ

Real Experiments
  • Macaw
  • Mechanisms for improving TCP over wireless (Snoop)
  • Roofnet
  • ETX

It seems to me that simulating wireless networks is more difficult than simulating wired networks because there is more variability in their performance, and with wireless networking technology costing so little, what are the reasons that any research group would continue to simulate? One argument that comes to mind is that a good model allows and encourages us to more thoroughly understand what is causing the effects we observe in real life. This sort of reasoning leads to an argument that we should probably both simulate and then verify our simulations on real hardware for all networking research projects (and perhaps all systems projects in general). Of course, this takes extra time and effort which we might not have to spend. Also, I should go back and review the "Modeling Wireless links for Transport Protocols" paper to remind myself of the arguments they present for modeling/simulating.

Thursday, October 2, 2008

Modeling WLANs

  • Figure 1 and Figure 2 are quite confusing
  • I thought that most of the internet was still running TCP Reno or Tahoe, these guys claim that almost everybody is using SACK or NewReno
  • They claim that a weakness of using models is lack of reproducibility, but isn't this just a problem of bad writing, i.e. oversight by the writers. Even when doing real experiments instead of modeling experiments you can omit details about the experiment setup.

Unplanned WLAN mesh networks (Roofnet)

An MIT project to create a reliable mesh network by giving (selling?) wireless access points and roof mountable antennas to people around Cambridge.

Drawbacks are that people need to install an antenna on their roof, but this pretty much unavoidable unless nearly everybody in the city had an access point.

While I was living in Madison, I considered signing up for Mad City Broadband, which was a more structured commercial endeavor to provide wireless access. However, in my building, reception was sketchy so I didn't go with MCB. The antenna on the roof could have solved the problem, but I didn't have roof access in my apartment building. This seems like a flaw in the roof mounted antenna solution.