Designing DCCP: Congestion Control Without Reliability May 29, 2009

The Datagram Congestion Control Protocol (DCCP) is a transport layer protocol that values speed over correctness, e.g. streaming media, telephony, etc.

DCCP provides a choice of congestion control schemes. This option is exposed at the application level. The choices are either a selective acknowledgment TCP-style scheme using a congestion window with additional control based on the ratio of data packets to acknowledgments, or a scheme where the sender transmits at a certain rate based on periodic feedback from the receiver.

Retransmissions are not always desirable and are easily added above the transport layer. Thus, everything sent over the transport layer (packets and acknowledgments included) has a unique sequence ID number. Since there are no retransmissions, the acknowledgment ID numbers refer to the latest packet received, leaving the specifics of packets not arriving to other modules within DCCP. Furthermore, for some flows, a 6-byte long sequence number in the header may be a significant amount of overhead, especially when sending e.g. an 8-byte data packet; therefore, DCCP includes an alternate set of headers using a 3-byte long sequence number which is concatenated with 3 upper bytes at the receiver.

Designing DCCP: Congestion Control Without Reliability May 29, 2009

This paper describes the DCCP protocol, which is designed as an alternative to UDP which will provide the same timeliness prioritization over reliability while adding the congestion control that UDP lacks.

The main points of this paper are as follows:

1. Congestion control should be decoupled from the protocol itself. Different applications have different communications requirements. While some prefer discarding corrupted information, others prefer receiving it. In other cases, some datagrams are more important than others (I-frames vs. B/P-frames in MPEG video), so if some have to be dropped due to buffers, it can be helpful to be able to handle some more carefully than others. DCCP provides flexibility in congestion control by acting as a congestion control framework which different congestion algorithms can be “plugged into.” This has the added benefit of allowing different congestion control for halves of a bidirectional communication, since many of the applications of UDP (and subsequently DCCP) tend to be mostly unidirectional.
2. The main requirement for congestion control is sequence numbers. These allow the protocol to detect loss and respond accordingly. Even though DCCP does not require retransmission, it also does not preclude it, if the application determines that there is sufficient time to make it worthwhile. However, as opposed to TCP, which numbers bytes in a byte stream, UDP and DCCP provide an abstraction in terms of datagrams, not bytes. Therefore, the sequence numbers in DCCP are specified in terms of packets. They also took the opportunity to specify a variable number of bits in the header for sequence numbers. Whereas TCP only specifies 32 bits which are used to specify bytes in the byte stream (which is becoming more and more of a problem with gigabit and higher bandwidths), DCCP can use up to 48 bits to specify a number of packets. This provides resilience against both malicious users (trying to run reset attacks is much harder than it is against TCP) and mistimed packet arrivals. However, they also recognized that not all applications need the overhead of 48-bit sequence numbers, so they created an option to use 24-bit numbers instead. This opens the attack window for reset attacks, but reduces the overhead when it is unlikely that mistimed packets will overlap a window in 24-bit space. This provides the application developer a choice of resilience or overhead.
3. Connection management should provide flexibility in usage models. In order to provide congestion management, DCCP is required to use a connection-based paradigm more similar to TCP. However, since connections over DCCP can often be mostly unidirectional, it is helpful to be able to configure the half-connections separately. DCCP provides this through feature negotiation, wherein both sides of a connection can agree on the policies to be implemented at one or both endpoints. In addition to adding per-direction policies, DCCP provides mobility support by allowing multiple connections to tie into a single session. This is made much easier since DCCP is an unreliable protocol and therefore requires much less synchronization upon the change in an endpoint’s location.

The main weakness in this protocol is that it is not backwards compatible in any useful sense with either TCP or UDP. While it is careful to be TCP-friendly (and indeed, compared to UDP, almost anything is friendlier to TCP), it requires fresh implementations on end-nodes, NATs, etc., which is a distinct barrier to deployment.

It would be interesting to see future research on this protocol using an overlay on a UDP system. Since NATs already support UDP, it might be an effective way to test the congestion control policies without requiring multiple nodes on the path to understand a new protocol. However, it remains to be seen whether it would be as effective as an overlay.

CUBIC: A New TCP-Friendly High-Speed TCP Variant May 25, 2009

This paper introduces a TCP variant whose window growth function is a cubic function in terms of the elapsed time since the last loss event. This growth function is real-time and unlike TCP, its window size calculation is independent of RTT values. The authors note that the under-utilization of TCP is most notably due to its slow start function (especially for short-lived flows where the slow-start function does not have time to utilize available bandwidth). The main contributions of this paper are:

1. An improved window growth function: CUBIC builds on top of BIC and provides a new window growth function. This function grows faster than BIC’s growth function right after a window reduction, and also when probing for the maximum bandwidth. The idea is that after a window reduction, we want to quickly get back to the bandwidth that was assumed to be the available bandwidth, but when we are close to this assumed maximum, we should slow down in order to avoid bandwidth over-estimates. When probing for higher bandwidth, the window size starts off growing slowly, and accelerates its growth quickly as it moves away from the previously assumed maximum.
2. TCP Friendliness: CUBIC aims to be fair to existing TCP traffic. To do so, the protocol emulates TCP window growth algorithm after a packet drop. If TCP’s estimated window size is larger than CUBIC’s window size, then CUBIC simply uses TCP’s algorithm to set the new window size. Also in short RTT networks TCP’s growth function becomes more aggressive, whereas CUBIC’s growth function which is independent of RTT values remains the same; thus it favors TCP traffic under short RTT values because it is passive about RTT values.
3. High utilization while retaining scalability and stability: The independence from RTT values for window size calculation makes CUBIC more stable and prone from oscillations that other variations like STCP face. The fast growth away from W-max (the assumed value for maximum window size) ensures the scalability of the protocol. This is in contrast to TCP’s AIMD policy for window growth. Thus by growing the window much faster than TCP, CUBIC keeps utilization high while scaling better as well.

I can’t think of any major problems with the design, except for the exponential growth of the window size during the “max probing” stage. It seems like when trying to probe for maximum bandwidth, it is easy to overshoot the actual maximum bandwidth by a large factor. Also the authors note that CUBIC behaves less aggressive than TCP in low-RTT environments. This could be a disadvantage for CUBIC hosts when TCP and CUBIC are used together. I’m not sure if their “TCP mode” handles this case or not.

Internet Congestion Control for Future High Bandwidth-Delay Product Environments May 25, 2009

This paper discusses XCP, a proposed successor to TCP which provides much better behavior than TCP by increasing bandwidth utilization, reducing bottleneck queueing, and drastically reducing packet loss, especially over networks with high bandwidth-delay products.

The main points of the paper were as follows:

1. The most significant insight provided by this paper is that TCP tries to do too much at once. By separating efficiency and fairness, XCP is able to better serve both goals. This is primarily because optimizing efficiency and fairness require two different algorithms. Optimizing efficiency is best served by a multiplicative-increase multiplicative-decrease (MIMD) system, which allows XCP to quickly converge on maximum utilization of the available bandwidth by all flows. Optimizing fairness, on the other hand, it best served by an additive-increase multiplicative-decrease (AIMD) system, which converges to a fair solution. Since TCP only uses AIMD for all efficiency and fairness requirements, it is sluggish when trying to take advantage of all of the available bandwidth.
2. In addition to allowing different algorithms for efficiency and fairness, splitting the goals also allows modifying one system without affecting the other. This is useful in multiple contexts. For example, it is possible to modify the fairness controller to take advantage of pricing information to allow usage-based billing and bandwidth allocation. It is also possible to use a different fairness controller, like one based on a binomial law, in order to try to optimize fairness in different situations. This simplifies the design and testing of different algorithms because the amount of code that has to be modified is reduced and there is no risk of damaging efficiency while modifying fairness.
3. While XCP is a very effective system, it is all for naught if it cannot be deployed efficiently. The authors of the paper provide two different ways that XCP can be incrementally deployed. The first is as a cloud within a TCP network. This would allow an ISP to deploy XCP within their administrative domain while the rest of the Internet remained primarily TCP-based. This would benefit ISPs because of the fairness options allowed under XCP. Some ISPs are already trying to implement usage-based billing/allocation, and XCP would facilitate that through its fairness controller design. The other option is to modify XCP routers to handle TCP traffic as well, balancing TCP and XCP traffic using a weighted fair-queuing approach. This is somewhat similar to the dual-stack IP situation, where more and more routers are having to handle two similar, but distinct, classes of traffic fairly.

The biggest weakness of this paper is that many of the parameters seem to be based on theoretical results. Normally this is the thing lacking from papers, which tend to use “stochastic optimization” to pick algorithmic parameters. However, in the case of this paper, it might be nice to see a chart where they try their optimal parameters against others to verify that they are indeed optimal.

Future research on XCP should look at various fairness algorithms in order to determine which are best for deployment on the Internet at large, with its large number of traffic classes and diversity of users. Research could also examine all of the various control parameters to verify that they still apply on the Internet as well.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

1. Conditions for retransmission — instead of using actual timer for timeout in every case or automatically retransmitting after n duplicate ACKs, assert interval between when a packet was sent and when a corresponding duplicate ACK was seen is within round-trip time.
2. Congestion control — instead of blindly increasing congestion window size until congestion is detected, decreasing the window size to compensate, then repeating the cycle, TCP Vegas makes an estimate based on non-congested round-trip time and the current congestion window size, and compares to the number of unrelated bytes sent between a packet and its ACK.
3. Slow-start — to set a more accurate threshold window for switching to linear expansion of the congestion window from exponential expansion, the experimental Vegas* is proposed. Vegas* sends four packets and waits for ACKs; as they arrive, it schedules congestion window size increases in the future and adjusts the threshold window based on the corresponding bandwidth estimates.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

This paper describes they modifications the authors made to the Reno version of the TCP protocol as implemented in BSD Unix in order to improve the behavior of the protocol in the face of network congestion.

They describe three major improvements to the TCP protocol, all of which affect the sender only, which makes this modification desirable from a deployment point of view:

1. The first mechanism modifies the retransmission behavior. Reno retransmits only when a coarse-grain timer event occurs or when it receives a certain number of duplicate ACKs. The problem with this is that these events do not occur very quickly and thus harm throughput as the sender waits to retransmit data. Vegas improves on this by timestamping segments and using ACKs as a trigger to check the timestamps on the next relevant segment against the RTT. This enables it to retransmit much sooner than waiting for a number of duplicate ACKs, in some cases even before it has received one duplicate ACK. This had the effect of reducing the number of coarse-grain timeouts by half, which they showed could have a considerable effect on throughput (19% if all coarse-grain timeouts could be removed).
2. The second mechanism involves how Vegas deals with congestion. Reno tends to be very reactive to congestion, and in fact it relies on generating some amount of congestion in order to determine the bandwidth of the network. Clearly, this is less than desirable, so Vegas takes a more proactive approach. It measures the achieved throughput versus the theoretical maximum throughput (measured in terms of RTT and window size), and then changes the congestion window to keep the achieved throughput between two thresholds which are relative to the theoretical maximum. The version that the authors settle on tries to keep between one and three buffers in use through the bottleneck router. They try to use at least one so that they can adapt to the bottleneck bandwidth increasing, and restrict it to three to keep from overrunning the bottleneck. This is probably the most important contribution of this paper, since it allows an increase in throughput while reducing the load on the bottleneck router relative to Reno.
3. The third mechanism involves the slow-start behavior of TCP. Their mechanism in many ways mimics the congestion avoidance mechanism described above in that it measures achieved throughput versus expected throughput and uses that threshold to switch from exponential to linear segment growth in order to mitigate overrunning the bandwidth of the network. This provides the same general slow-start behavior without generating nearly as much packet loss as Reno does during its slow-start period. Their performance numbers show that Reno’s packet loss numbers flatten out over time because of the relatively large amount of packet loss during the initial slow-start. In contrast, Vegas’s packet loss numbers scale linearly with transfer size, which indicates that there is no additional penalty incurred by its slow-start mechanism.

In addition to the performance validations performed for the three major enhancements, the authors also performed fairness, stability, and queue behavior experiements to ensure that Vegas would not harm existing Internet users as a result of small- or large-scale deployment. All of these experiments show that Vegas either outperforms, or at least does not significantly underperform Reno in all of the various metrics tested.

The main weakness of this paper is that the experiments were all relatively small-scale. This is probably an artifact of the age of the paper, but the Internet is so much larger than it was then, with so many different classes of traffic, that their performance numbers may not be as meaningful in a modern context. I would like to see their experiments rerun with modern bandwidth-delay products on the Internet today.

Future research in this field should examine the remaining performance left “on the table” in terms of TCP transmissions to determine the best parts of the protocol to improve. This paper focused exclusively on the sender’s side of the transmission, which makes their performance numbers all the more impressive. Even though the receiver is supposed to be passive in TCP, it might be interesting to see what kinds of further performance gains could be achieved by collusion between sender and receiver, with each taking an active role in maximizing throughput.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

(i) the three most important things the paper says

The first most important topic that the paper covers is the fact that TCP Reno relies on congesting a network in order for it to be detected.  This is a huge observation, as TCP Reno must effectively make the congestion situation worse in order for it to get better.  The authors claim (and thereby show) that TCP Vegas handles this situation much differently.  TCP Vegas attempts to predict a congestion-based situation before it leads to significantly decreased performance on the network as a whole (by clogging up buffers at each intermediate router).  What the authors are effectively saying here is that the anti-congestion measures in place in TCP should be based upon preventative measures instead of failure-based measures.

The next observation that the authors make deals with the conservativeness of the Reno retransmit algorithm.  The authors claim that the retransmit algorithm doesn’t quite detect when there’s been a lost packet quite fast enough (fast enough meaning before the next global timeout).  TCP Vegas addresses this by, instead of waiting for a third consecutive repeated ACK, attempting to guess based upon the timeout value of each individual outstanding packet (versus the global timeout).

A third important observation made by the authors stated that the slow start mechanism used by Reno was too aggressive.  The exponential start could basically create a congestion problem just by how quickly it can ramp up (without testing out the current network condition).  TCP Vegas handles this by providing more time in between exponential growth periods, allowing the TCP connection to gauge its progress slowly (a slower ramp up) without congesting the connection on a wrong guess.

(ii) the most glaring problem with the paper

One of the biggest problems with this paper is the fact that it introduces quite a bit of complexity to (what was) a relatively simple protocol.  This means that the TCP connection itself will require more processing power.  While this may not be of great concern to higher-computation capable modern PCs, this could become a problem for lower powered embedded systems that use TCP as a mode of communication.  With lower powered devices on the rise (internet phones, etc.) increasing the complexity of TCP might not be the greatest idea.

(iii) the future research directions of the work

I feel that a larger scale study could be done with TCP Vegas on a TCP Reno based Internet.  The study that was done contained a small set of Vegas connections over the internet, but what would be interesting would be assigning a large subset of the Internet to use the TCP Vegas design on top of the TCP Reno Internet.  I feel that this will reveal more information about the usefulness of TCP Vegas in a TCP Reno world (and whether or not the conservativeness of Vegas will fall prey to the aggressive actions of TCP Reno).

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

The paper by Brakmo and Peterson out of University of Arizona introduces a new TCP implementation, which improves on congestion avoidance mechanisms in TCP. The authors present the new techniques in contrast to the older TCP implementation called Reno, and evaluate simulation and measurement results of the two implementations. The three key techniques in Vegas are:

1) Retransmission mechanism: In both implementations, the goal is to avoid relying on coarse grained timers, and allow faster retransmission of lost packets in between coarse timer ticks. In Reno, this simply happens after three duplicate ACKs for an old packet are received. In Vegas, a timestamp is recorded for each sent packet and when the appropriate ACK for this packet is received, the Round-Trip-Time is updated. This RTT is used to see whether the first duplicate ACK already indicates a packet loss (because it arrives later than the estimate arrival time of the ACK of the lost packet) or if the first two ACK packets after a retransmission are also late, in which case more packets have been lost shortly before retransmission.

2) Congestion Avoidance: The authors describe Reno as an reactive implementation in the sense that Reno always pushes the bandwith over the “limit” of the optimal bandwidth by filling up router buffers on the way until packet loss occurs. This leads to oscillations in the send speed over long-going connections, filling up buffers unnecessarily. Their Vegas implementation, in contrast, tries to be proactive when increasing or decreasing the send window size. It does this by calculating the Expected and Actual throughput when changing the send window size, to find out if increases or decreases are necessary. This is done by comparing the rate to thresholds, so unnecessary oscillations are avoided.

3) Slow-Start: To optimize the slow-start period in TCP, the authors propose to use the congestion avoidance mechanism also during the slow-start phase, changing also the point in time where the send window size is doubled. This can only happen in Vegas once every two RTT, whereas Reno did it every RTT. This slows down the start a little, but avoids overshooting the available bandwith and reduces the need for retransmission.

The most glaring problem of the paper is the fact that the simulations don’t take different networks into accounts, no variations of the delay or available bandwith are simulated. Seeing the behavior in a multi-hop simulation with changing environmental conditions would have made a stronger point.

Future research directions for these TCP mechanisms are looking into congestion avoidance mechanisms that have minimal support from the routers on the way, which can signal end hosts and warn them about upcoming congestions or there optimal sending rate in a more direct way. These mechanisms could be simulated and evaluated.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

This paper talks about TCP Vegas, a TCP implementation based on TCP Reno but with better throughput and fewer packet losses. The basic idea is to try to predict congestion and avoid it, as opposed to Reno’s approach which creates congestion and then adjusts afterwards. The main contributions of the paper are:

1. Retransmission Mechanism: Reno uses a coarse timeout for retransmissions, thus typically taking too long before retransmitting. It also retransmits when 3 duplicate ACKs are received. However, Vegas realizes eliminating dependency on this coarse-grain timer would reduce timeouts further, and increase throughput. Vegas recalculates RTT times each time an ACK arrives, thus giving better estimates of RTT. Then it takes advantage of this accurate RTT and uses certain ACKs as a hint to check if a timeout should occur: (1) rather than waiting for N duplicate ACKs, each time a duplicate ACK is received, check to see if any of the relevant segments have timed out. If so retransmit them. (2)Check the timeout for segments in question for the first or second non-duplicate ACK is received after a retransmission. By using this policy, Vegas can quickly detect if a retransmission is necessary, rather than having to wait for the coarse grain timeout to expire.
2. Congestion Avoidance and modified Slow-start: Reno needs to create losses before it can detect congestion. It has to continually increase its window size for higher bandwidth, until it congests the network. Vegas on the other hand tries to predict congestion by comparing the current throughput to an expected throughput calculation. Vegas tries to keep bandwidth between two predetermined threshold values (indicating the number of extra buffers to use in the network). As for slow-start, Reno always sets the threshold window to half the congestion window when a retransmit timeout occurs.  The congestion window will exponentially increase until the slowstart threshold, after which it will be a linear increase. Vegas on the other hand only uses exponential growth every other RTT, and between the RTTs it keeps the window fixed to calculate an accurate throughput rate.
3. Implementation can play a significant role in performance of a protocol: TCP Vegas is an implementation of the TCP protocol, in the same manner that TCP Reno is. This goes to prove how implementation details that are typically left out of the protocol specification can play a significant role on the performance of the end-system, and thus careful considerations should be made for the implementation.

Problems: Vegas tries to always keep a few extra buffers filled up in the network. That is, it sends enough traffic to ensure that some segments are buffered up on the routers. While this might result in good performance for a few nodes, when there are thousands or millions of Vegas nodes all doing the same thing, the routers’ buffers could easily be overwhelmed and start dropping packets. It seems like a greedy idea to aim to buffer packets on the routers all the time.

Future Research: Vegas was the basis for RenoNew and therefore provided the groundwork for the current popular TCP implementation. I don’t know anything about RenoNew, but I would assume some research was done to change the buffering mechanism of Vegas, as it would have most likely overwhelmed routers’ buffers.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

(i) Three most important things

1. TCP Reno uses coarse-grain timeouts in addition to the Fast Retransmit and Fast Recovery mechanisms to detect and transmit lost segments but eliminating the dependency on coarse-grain timeouts would result in a 19% increase in throughput. TCP Vegas proposes a new retransmission mechanism that treats the receipt of certain ACKs as a hint to check if a timeout should occur to reduce the time to detect lost packets.

2.  TCP Reno’s congestion detection and control mechanism uses the loss of segments as a signal that there is congestion in the network. TCP Vegas proposes that it looks at the changes in the sending rate to detect congestion. TCP Vegas compares the measure throughput rate with an expected throughput rate to determine the rate at which to send packets.

3. TCP Reno sets the threshold window for slow-start to one half of the congestion window. The slow-start period ends when the exponentially increasing congestion window reaches the threshold window and then increases linearly from then on but if the initial threshold window value is too small then throughput suffers or if value is too larger then packets will be lost. TCP Vegas allow exponential grown only every other RTT to able to detect and avoid congestion during slow-start and when the actual rate falls below the expected rate by the equivalent of one router buffer then Vegas changes from slow-start mode to linear increase/decrease mode.

(ii) Most glaring problem

The most glaring problem would be that when TCP Vegas is intermixed with other versions of TCP like Reno then the performance of TCP Vegas degrades because TCP Vegas reduces the sending rate before TCP Reno since Vegas detects congestion earlier and thus gives more bandwidth to the TCP Reno connections.

(iii) Future Research Directions

Future research directions for this work would be to study how the network congestion avoidance algorithm affects fairness when TCP Vegas connections need to compete with more aggressive TCP implementations like TCP Reno.

TCP Vegas: End to End Congestion Avoidance on a Global Internet May 15, 2009

The paper introduces TCP Vegas and compares it against TCP Reno in terms of throughput and retransmission rate. The results show that Vegas makes uses of available bandwidth and avoids congestion (indeed avoids creating congestion) more effectively than Reno. Furthermore, these results are not at the expense of other non-Vegas TCP flows. TCP Vegas achieves these results even when all the flows are TCP Vegas flows.

The major contributions of Vegas are a new algorithm for determining retransmission, a new measurement for detecting (and thus avoiding) congestion, and a modified slow start mechanism that avoids overrunning bottleneck router buffers.

The new retransmission algorithm uses system clock timestamps to estimate RTTs instead of the BSD-based 500ms “ticks”. This means RTT estimates are more accurate. Further, Vegas uses ACKs to check if a timeout has occurred instead of waiting for a “tick” to pass. Lastly, instead of waiting for n (3) duplicate ACKs to be received before retransmitting, Vegas retransmits after the RTT has been exceeded.

The second contribution is the new congestion avoidance mechanism. Using a base RTT and accurately measuring the change in RTTs between segment sends and ACKs, Vegas can calculate an expected and actual throughput. Vegas then defines two thresholds, a lower and upper threshold. By adjusting the send window size to keep the throughput between the lower and upper thresholds, Vegas can keep between 1 and 3 segments in the bottleneck router’s buffer full. This means Vegas can effectively utilize available bandwidth without overrunning the bottleneck router’s buffer.

Lastly, Vegas uses the expected and actual throughput measurements to avoid overrunning the bottleneck router’s buffers during slow start. Instead of doubling the window size every RTT, Vegas doubles every other RTT. Every other RTT, it measures the throughput. If the throughput begins to decrease, Vegas switches to linear growth mode to avoid causing congestion in the network.

It seems clear from the results presented that TCP Vegas is a better implementation of TCP than TCP Reno. However, it would also seem that TCP Vegas is considerably more difficult to implement. The algorithms for the improved features are more complex than even TCP Reno (which is by no means simple).

I’d like see how quality of service implementations/mechanisms work with Vegas. Because Vegas is very adept at consuming available bandwidth without causing congestion, I expect that some QoS implementations will suffer because of the lack of “slack” bandwidth now available.

Modeling TCP Throughput: A Simple Model and its Empirical Validation May 11, 2009

(i) The three most important things the paper says:

1) This paper was able to show that the majority of TCP window decreases are due to time outs and not fast retransmits as previously thought.  This was a novel concept at the time and it became their basis for their model which takes into account time out loss indications.

2) They proposed a simplified equation/expression for TCP bandwidth in the paper (Equation 32).  This equation provided an output of performance for TCP taking into consideration “packet loss indication rate”, “RTT” and “max window size”.  Subsequently, they were able to prove the correctness of this model through comparison with traces of real data.

3) It was observed that during a period without loss indications, the window of the sender is dominated by the congestion avoidance algorithm and the receiver’s advertised window.  This shows that as a consequence, a period without loss indications will have a window grow up to Wmax, but will not grow further beyond this value.  This was an important observation in the basis of Equation 32, since it provided a bound for the window size.

(ii) The most glaring problem with the paper:

They made a couple of big assumptions in this paper, which they didn’t really provide significant reasoning and proof (e.g. triple ACK, window sizes, subtleties of fast recovery algorithm).  Their proof of correctness was linked to how their model stacked up against real data.  Since they didn’t dive too deeply into their assumptions, there may be cases (possibly big ones) that their model overlooks.

(iii) The future research directions of the work:

How does this model hold up in a wireless environment, where failures occur much more frequently.  Also, does the assumptions that were used to construct Equation 32 in this paper still hold true in 2009 (almost a decade later the paper was produced).  Assumptions such as, round trip time is independent of the window size being “mostly” true.  In light of such evolutions in technology and assumptions, perhaps “Equation 32” would need to be updated.

(i) The three most important things the paper says:

1) This paper was able to show that the majority of TCP window decreases are due to time outs and not fast retransmits as previously thought.  This was a novel concept at the time and it became their basis for their model which takes into account time out loss indications.

2) They proposed a simplified equation/expression for TCP bandwidth in the paper (Equation 32).  This equation provided an output of performance for TCP taking into consideration “packet loss indication rate”, “RTT” and “max window size”.  Subsequently, they were able to prove the correctness of this model through comparison with traces of real data.

3) It was observed that during a period without loss indications, the window of the sender is dominated by the congestion avoidance algorithm and the receiver’s advertised window.  This shows that as a consequence, a period without loss indications will have a window grow up to Wmax, but will not grow further beyond this value.  This was an important observation in the basis of Equation 32, since it provided a bound for the window size.

(ii) The most glaring problem with the paper:

They made a couple of big assumptions in this paper, which they didn’t really provide significant reasoning and proof (e.g. triple ACK, window sizes, subtleties of fast recovery algorithm).  Their proof of correctness was linked to how their model stacked up against real data.  Since they didn’t dive too deeply into their assumptions, there may be cases (possibly big ones) that their model overlooks.

(iii) The future research directions of the work:

How does this model hold up in a wireless environment, where failures occur much more frequently.  Also, does the assumptions that were used to construct Equation 32 in this paper still hold true in 2009 (almost a decade later the paper was produced).  Assumptions such as, round trip time is independent of the window size being “mostly” true.  In light of such evolutions in technology and assumptions, perhaps “Equation 32” would need to be updated.

A Protocol for Packet Network Intercommunication April 7, 2009

The biggest contribution in this paper appears to be the transmission control program, or TCP. The TCP as described here seems reminiscent of the stub/remote procedure call model presented in [1]. A TCP provides fragmentation and encapsulation of data, which makes it fairly easy to discern the destination of the packet and (to some extent) what to do with it once it gets there.

Second, TCPs provide some reliability mechanisms, in terms of retransmitting unacknowledged packets and checks for duplicate packets within a certain timeframe.

Third, the concept of gateways as an interface between multiple networks: a gateway is essentially a cut vertex on a network graph. The idea is that one can use two completely different protocols — one for each network — but still get the data through. The gateway may reconstitute and refragment packets as it sees fit, and may readdress something so that it goes to the proper place within a network. A possible analogy is currency-changing: it’s worth the same overall, but separated in different quanta and accepted in different places. I would imagine that the concept of network address translation is a derivative of this.

The paper mentions using a window for retransmission of packets to avoid the problem of finite sequence numbers. However, to transmit a very large piece of data, one might run out of sequence numbers, especially if transmitting a large number of small packets.

References

1. A. D. Birrell and B. J. Nelson, “Implementing Remote Procedure Calls”, ACM Transactions on Computer Systems, Vol. 2, No. 1, pp. 39-59, February 1984.

A Protocol for Packet Network Interconnection April 7, 2009

This paper describes a protocol which seems to be the predecessor of the TCP/IP suite used today by the Internet. It makes the argument that packet networks are likely to use different conventions, which makes trying to standardize on one packet format difficult, if not impossible. Therefore, they propose a standardized internetwork header, which can be read and interpreted (at least in some sense) by the gateways between different networks. This internetwork header contains all of the information necessary to determine the destination of the packet as well as information useful for sequencing and fragmentation. On top of this internetwork header, individual networks are free to add a local header or trailer to allow the packet to traverse that particular network on its way to the next gateway or the destination host. Also described in this paper are addressing formats (network/TCP/port), sequence numbers (which address bytes relative to the start of the message stream), and a very powerful retransmission mechanism. The retransmission mechanism uses a “window” over which data can safely be sent, with the notion that it is safe to send data as long as the receiver knows that it is not receiving outdated packets. The only complicating factor is synchronizing the sequence numbers at the beginning of an association, which is handled by providing a special SYN bit to indicate the start of an association.

In my opinion, the biggest problem with this paper is that they provide no flexibility for future network growth. While the fragmentation mechanism is excellent for supporting larger and larger packet sizes as technology advances, the addressing scheme (as we have seen with the push from IPv4 to IPv6) is limited by what they see as the largest conceivable network. Unfortunately, networks have become much larger than the initial network designers could conceive. Perhaps it would have been better to allocate more bits to the address space (just a stopgap unless it is taken to the extreme a la IPv6), or even better, to somehow make it possible to specify how many bits were being used for addressing. As long as only a few bits are necessary, the header can stay small, but as more bits are required, the header can grow slightly to greatly increase the address space.

Future research in this area might include ways to make the protocol more flexible in the face of networks which greatly surpass the properties of networks conceived of in this work. As mentioned with variable-size addresses above, maybe the approach should be to make a standard, but flexible format which allows organic growth, which might ease the pain we are currently feeling in the transition to IPv6, which requires a dual-stack architecture.

A Protocol for Packet Network Interconnections April 7, 2009

The authors make the observation that hosts often need to communicate across homogeneous networks, and that the best way to facilitate this is through gateways at the network boundaries. This approach handles formatting and fragmentation issues without compromising the integrity of the message. A key point is that gateways can perform fragmentation as needed but should not be responsible for reconstructing segments. This is left to the end host, because there are no guarantees that any one node other than the host will have all the packets go through it, and because the processing done at the gateways should be kept to a minimum. This follows from the end-to-end argument.

This paper introduces the concept of a reliable message queue between two processes. This is a natural and powerful abstraction for designers as it allows a process to provide a message and a destination and not have to worry any further about transportation. Key points are that each host must have a globally unique identifier, and that the notion of a locally unique port must be introduced to handles multiple processes on the same host.

The most important thing about the protocol is that its functionality is built on top of an unreliable, best effort network. By constructing the protocol around a sliding window, the authors are able to achieve reliable, in-order delivery. In addition, they are able to leverage the size of the window to implement flow control. This again falls in line with the end-to-end argument, and represents the “smart” host’s attempt at deducing the state of the network without any explicit information.

I would say that a drawback of this paper is that it does not contain any formal verification or at least simulation results. One or both of these would have been very useful in backing up the major contributions like flow control. The authors provided a solid framework for implementing TCP, but it does not seem that they actually deployed it at this point.

This is an incredibly significant paper in the history of networking research, and the concepts contained in it have been thoroughly analyzed, refined, and followed up on. In this context it is useful to think about what fundamental new directions future research could take. One such direction could be to identify abstractions other than the shared queue that TCP provides that might be useful for process communication. I believe that as the internet evolves and overlay networks become prominent a variety of special purpose abstractions will find widespread use.

A Protocol for Packet Network Intercommunication April 7, 2009

(i) the three most important things the paper says

This paper presents TCP, a communication protocol abstraction on top of the data link layer. There are many concepts from this TCP paper. TCP provides end-to-end reliability where the ends are processes on hosts. Packet sequencing and window based flow control is introduced to TCP. TCP introduces ports multiplexing/demultiplexing to identify connections between processes. Different source/dest port connections result in separate connections and are sent in different TCP messages. TCP protocol and gateways are introduced and designed to abstract away data link addressing differences, MTU differences with fragmentation, and data link protocol differences.

(ii) the most glaring problem with the paper

The paper provides ideas and concepts but no test implementation. Congestion avoidance at gateways has practical problems. TCP’s addressing scheme is not extensible and talks with regards to accounting, for example, was done in a few sentences without detail.

(iii) the future research directions of the work.

The important concepts from this paper provide grounds for future research on next generation transport layer protocols, addressing, congestion avoidance and routing algorithms.