Sunday, September 28, 2008

Wireless TCP

So, this paper was focused on the ways to allow TCP to run over a wireless network.

I'm intrigued that there was so much work on mechanisms that clearly violate the end-to-end principle. I'm guessing that a big reason for this is that the wireless link is the last hop. It's not like we're doing anything to the internals of the network. This also might help with mobility.

The end-to-end paper does give reasons to push functionality into the network, but not at the transport layer. The point of it is to push functionality down into lower layers if necessary, not push layers down, as some of these solutions have done. This is the link-layer solution that is actually used.

So, as to why this is a great idea. An interesting point is that wired and wireless networks are different. One reason not to push reliable transmission into a wired network is that it requires state at the router. This isn't possible at the high speed required of wired networks. However, wireless has a much lower bitrate, so we presumably have excess computation power (maybe we should have used it to save power...) This power is used to store and process these packets and retransmissions.

The only thing I had not contemplated about this work before is the effect of reordering. It's not obvious to me that the link requires in-order processing, but it seems as though TCP has become dependent on a property of classical internetworking that perhaps it should not have. I'm not sure of the implications of that, but it's at least a clear indicator that this is the case.

Saturday, September 27, 2008

Macaw

I'm changing the format of the posts as Randy wants more of a discussion. The "this is what the paper was about stuff" isn't valuable for that, it should be interesting observations alone.

I aggressively skimmed this paper, as I know most of the wireless stuff pretty well. In macaw, they are assuming "symmetry" among the nodes, which is actually much different from what's actually done. Wireless, like DTN, is generally only a one-hop technology. You use wireless to get to a wire. This is of course different in sensor nets, and a few other applications. So the focus on having all nodes be equal was somewhat strange.

I like it though, as I feel that wireless's flexibility isn't highly utilized. You can, if we figured out this wireless thing, get n^2 connections of n machines without rewiring. The limitation on this is the spectrum required, which would not scale with n. In particular, it would start running off into reserved spectrum pretty quickly.

Now, this wouldn't be of value in home computers, as there are few connections between home computers. It's all to some massive server somewhere. However, in a constrained area that has many peer-to-peer connections (oh, a datacenter or a sensor net) this would be fantastic.

Datacenters are currently out of scale for this, and sensor nets do it. I think the first might be able to be solved.

The next paper will have me musing on the inherent differences between wired and wireless, which will explain why the above may not be feasible.

Thursday, September 18, 2008

Dangit

I read the wrong papers again.

Gb Switched Router

Wow, I should have read this before the last paper. This was a thorough description of how (semi) modern routers are designed, complete with descriptions of terminology used all over the previous paper. It describes the algorithms used in these routers as well. Lastly, it suggests a modification to these algorithms for multicast routing.

The paper was clear, unambiguous and totally helpful. I always assume that anything in networks/systems is actually dead simple, and this demonstrates that. This paper is fantastically valuable, and should totally be in the reading.

I really found the model of adoption for routers to be interesting. As we discussed in class, you worried that RED and other algorithms are not being used due to ignorance, or worry or whatnot. This shows, to me at least, that it's not that case. They've pushed cutting edge algorithms in at the router level, the difference is that these algorithms give a performance boost under the common case while RED does not. RED only benefits you in high congestion, which you avoid like the fucking plague. The algorithms speed up your router all the time. So, I think to have an impact on the routing world you can't focus on esoteric events like congestion collapse, you have to focus on the common case or no one will care.

Wednesday, September 17, 2008

Scaling Routers

We read a paper about building a 100 Tb/s router, and the design considerations required for it. I wasn't able to pick up too much from the paper, as lingo usage was endemic. I did figure that router design is still generally pretty simple, with N^2 connections among the inputs all over the place, which was acceptable, it seems.

I'm not sure what I was supposed to get out of this anyhow? The power discussion? They mentioned that router power usage is becoming the limiting factor, so they were switching to optical. Ok, that's a good idea, I agree. They gave a proof that it would 100% of the throughput, which I guess I buy, I mean, they are switching between lots of flows and I could see that working.

I don't think this paper was particularly valuable, a more general work on router structure probably would have been more beneficial to someone at my level, at least.

Sunday, September 14, 2008

XCP

This paper details the eXtensible Control Protocol, which isn't particularly extensible. However, it attempts to improve upon TCP, particularly in instances of high delay/bandwidth product. This is done by breaking end-to-end and sticking a layer above IP in the routers that explicitly informs the protocol users about current congestion, and some complicated mathematics.
I found this interesting as I have worked on DTN, something else that works on TCP's irresponsible on high delay links. The systems seem unrelated, as this relies on ACKs for transfer of information, which DTN does not assume.
The most interesting aspect of the paper is the complete disregard of the end-to-end principle. I'm not sure how meaningful this is, tying the congestion control into the routers. TCP does a beautiful thing in assuming drops mean congestion. This is an assumption based on the lower layer, requiring no changes at the router. I feel as though a more interesting research agenda may be to reassess the assumptions the transport layer can make about the IP layer, now that the IP layer has RED and such. Perhaps backing off less on a drop, these things.

Saturday, September 13, 2008

RED

This paper deals with "Random Early Detection" algorithms for marking or dropping packets. It's a particularly elegant solution to the question of what packets are dropped when the router gets congested. Instead of waiting for congestion, it drops or marks packets with higher probability as we approach congestion. It begins once you pass some heuristic for average queue size. This is done as a weighted average, as would be expected. Eventually the queues are filled and the probability of a drop is one.
I consider this so elegant as conversations that utilize more packets have a higher probability of being selected for dropping. It just falls out of the scheme. Totally brilliant.
I was confused about the punishment of bursty communications it claims to avoid, but I think I understand that now. Because it works on average queue size rather than actual queue size, the bursts do not imply a higher chance of drop. There is a chance that the queues may fill before the average queue size catches up though...

I did some work in Randy's datacenter 294 class that dealt with congestion control in datacenter networks. I made modifications to Click, which used RED as one of the mechanisms implemented.

The paper is ungodly long for such a simple system. RED is not complicated, and I feel as though a quick view of the Wiki page would be more valuable than this in-depth analysis of the algorithm.