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.

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.

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.

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.

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.

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.

Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks

This paper is the design and implementation of a stateless fair queueing algorithm. The cute trick they used is that they have gateway routers tacking state onto the packets, allowing for stateful decisions without state.

This paper was much clearer than the FQ paper. I found some interesting tidbits in this, particularly in regards to the end-to-end argument. As we move these flow-oriented schemes into the network, I begin to question how much of TCP is being reimplemented in the network. For instance, they had a misbehaving UDP connection that hosed the TCP connections for one experiment. The stateless FQ solved this, giving each equal bandwidth. If you think about it, a good portion of TCP is enforcing that exact behavior. So, why are all of the hosts using TCP? If stateless FQ exists, they can likely use UDP and get the same throughput and congestion avoidance behaviors.

I know there's more to TCP than just that, it just caught my attention.

I found the tagging of packets to be really interesting. That's how Click does a lot of it's work, though they call it "painting" the packet. I question the security. If this is a great function, why not have the ultimate gateways, the hosts, tag their packets? Well, that's presumably a security concern. What would it take for the clients to implement this? Would it simply be a sliding window?

It's late and this isn't well reasoned, we'll see about class tomorrow.

This paper was great and should totally be left in.

Analysis and Simulation of a Fair Queueing Algorithm

This paper describes a fair queuing algorithm, in the sense that misbehaving clients cannot abuse the network. With standard TCP and FCFS queuing at the intermediate routers, a client who ignores the sliding window and packing drops can gain an advantage and a disproportionate share of the network. They demonstrate this, as well as a solution.

Some background exists in the TCP Daytona implementation by Savage. He implemented a form of TCP that misbehaved in precisely the wrong way to cause this. Also, during my time in Uganda, I found another problems with TCP. They have these "download accelerators" that open multiple TCP connections, allowing the one download to grab a larger portion of the network. This system doesn't solve this problem, as it queues on a per-connection basis. Is this algorithm used? I'm assuming so. Could it be modified to solve the tcp accelerator? It hoses the network at Makerere, that much I'm sure of.

The paper was thick and dense. I wasn't able to glean the details, but I found the algorithm and the concept simple enough. I doubt there is a version of this that reads more easily, I would much prefer that.

The paper is valuable, but not important enough for the syllabus. This could be explained in ten minutes in class.

Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks,

I read this paper earlier, on accident.

Congestion Avoidance and Control

This paper is a summary of the congestion control mechanisms built into the TCP standard. One of these is slow start, where the packet rate is only increased when an ack is received. The other is additive increase/multiplicative decrease. Lastly, the exponential backup mechanism is briefly justified.

These algorithms assume a number of things. One is that a dropped packet indicates congestion. In highly intermittent networks (802.11) this doesn't hold, and these algorithms tend to grossly overestimate the congestion in the network.

The paper itself is great, concise and clear. It looks long, at 25 pages, though around half of it is appendix.

As far as discussion topics, my normal questions come out:
Competing systems, and why
Assumptions, and why

This leads to a discussion of DTN, UDP, and any other systems I don't know about.

I'm also curious about what other assumptions are implicit. The big one for me has been that packet dropping one, but various work have shown some security assumptions which do not necessarily hold.

This paper should totally be kept in the reading list.

This paper was mostly technical work, with little pure research. I don't feel as though it left many open research questions. If any, it would be attacks on this system and it's assumptions.

Inferring AS Relationships

This paper is easily summarized, as they simply attempted to infer the nature of AS connections from their behavior. Nothing terribly difficult, and not rocket science. Each AS behaves differently based on who they are connected to, forwarding packets if the user has paid, and generally not forwarding if they have not. With a slightly more nuanced view, they show that it's not that hard to guess the relationships.

As to the paper itself, it went into far too much depth on the theoretical view of such a simple argument. That should have been left for an appendix, if anything. For discussion topics, I find little value. The previous paper gave a greater depth to the discussion of the reasoning for the AS setup. The inference of the AS status is not particularly interested to me either.

As a quicker read, this paper did give a good background on AS and BGP.

This paper is redundant and doesn't add much to the syllabus. I would remove it for an earlier paper describing the discussions made to push BGP to where it is. I'm a sucker for those sorts of things.

Routing Notes

This paper was a summary of the internetworking protocols, and how AS's are connected. The majority of the discussion was about BGP.

This paper was quite valuable, giving a good description of the protocols involved and the problems that arrive from their use. I particularly enjoyed the discussion of the economic concerns for ISPs. The transition from academic network to commercial entity was no doubt difficult, but it was interesting how the user demands enforced cooperation.

An interesting aside is how early networks did not always support this framework. AOL is my example from my youth. Traditionally, AOL did not allow you ot leave AOL's network. This paper allowed me to understand how and why they attempted to do that.

Lastly, the design of BGP is great. It's simple and seems to solve most of the concerns of users. However, I know of a few security concerns in the BGP protocol. The use of TCP, in particular, seems strange.

This paper was great, and should be kept in the reading. It was clear and valuable. The reading for this week is a little long, at around 30-40 pages for two days.

Open research questions were not given in this paper, as it was an overview of existing technology. They did mention issues scaling iBGP routers. I personally wonder at how far this technology can scale as we continue to increase the connectivity of our devices. As always, I wonder about alternative schemes and where they are used.

This is a description of how our network works. The implications of the paper are benign for that reason, as it's not really the paper as the technology described.

Increase/Decrease Algorithms

This paper was about the algorithms to enforce congestion avoidance. They make a distinction between congestion avoidance (staying in low congestion) and congestion control (staying out of high congestion). They find that additive increase/multiplicative decrease is the appropriate answer. This is done with a rigorous proof of its correctness.

Some background on these algorithms from the TCP Daytona paper by Savage. In this, he shows the assumptions shown in this work. The biggest thing is that they trust the client to implement the protocol correctly. If they don't they can game this algorithm to improve their performance. Very cool result there.

I consider the above an interesting discussion topic. Also, an interesting question revolves around the appropriate layer in the stack for this functionality. Anything above IP likely violates the skinny waist model, as the intermediate routers are the ones using this. However, a basic layer without any control flow is useful for more generic systems. There's seemingly no obvious answer, though I expect that implementing it at IP is probably correct, as control flow is a basic property of networks.

The paper was nice, although it was went into too much depth on the deep proofs. The graphical proofs were valuable enough.

They punted on a great deal of questions, from the guessing of the number of users to async operation. They worked on a very abstract, singular problem and didn't leave that area.

As to the implications of this work, this is what's currently used, as far as I know. Greatly impactful.

HE DESIGN PHILOSOPHY OF THE DARPA PROTOCOLS

This was read with great speed before class, as bnrg has been down.

Packet switching because it was "obvious" for the apps, not any high minded idealism
This is strange, as the packet switching model gained them so much
interesting point about priorities. GSM is a network that was designed by industry, so accountability was priority one, which has hampered the network severely.
So there are networks which break the IP plan by providing higher level semantics at the network level. I wonder if that has happened since IP was developed?
good point about IP's failure if network retransmits are common. However, that can also be implemented at a higher level.
Poor implementation of TCP problem was shown with the Savage paper on the fast TCP
Ends with a discussion of TCP. Quite good, and shows how scalability was priority one. As processing power scales faster than population, we may be able to move away from that model...

End-To-End Arguments in System Design

End-To-End Arguments in System Design

More emphasis on APIs as the primary design problem
You have to have end-to-end, as there are too many failure cases.
end-to-end meaning check and verify, generally
non end-to-end solutions (TCP) are only optimizations
When to end? Presumably when we hit hardware levels of risk
great example on delivery
don't care about acks, system could die after packet received. You want application ack
E2E Duplicate packets: what if application sends multiple packets?
Need E2E, if implicitly.
Remind me to name my distributed file system something other than SWALLOW
Not enough discussion of the performance optimizations of pushing it into the network
E2E as users making calls. That's pretty funny.