This paper essentially addresses the problem of using TCP over lossy wireless networks by comparing the available proposed solutions to this situation and extensions to TCP. These are split into three categories: 1) link-layer solutions, 2) connection-splitting solutions, and 3) E2E solutions. The link layer solutions attempt to do reliability at the link layer. Connection splitting solutions split the connection in to two pieces, allowing the base station to send ACKs upon receiving packets, and then making sure that the base station reliably transmits the data to the wireless nodes. E2E solutions simply modify the TCP behavior at the end nodes.
There are a lot of different methods of improving TCP performance. Among them are: SACKs (selective acknowledgements). Selective acknowledgements let the sender know exactly which packets were received, so as to avoid unnecessarily resending data. There is also explicit loss notification, which (as the name suggests) explicitly notifies the sender when a packet has been lost. This is advantageous because it helps the sender differentiate between losses that occur because of congestion and losses that occur because of noise in the link.
Other methods include retransmitting on the first duplicate ack, which is beneficial for lossy networks, where a loss is most likely to be due to noise rather than congestion. The final method is duplicate ack suppression at base stations, which gives the base station some time to retransmit the packet before it forwards the duplicate acks to the endpoint; this means that the endpoint will not decrease its congestion window when a non-congestion loss occurs, thereby keeping the throughput high.
As it turns out, the best method turns out to be a link-layer method that both suppresses duplicate acks at the base station and uses SMART based selective acknowledgments. This is called a TCP-aware algorithm because it must understand the meaning of the acknowledgements in order to work.
There's not much more to say about this paper other than the fact that there may be some overhead in determining that the connections being created are, in fact, TCP connections. It would be interesting to run the same experiments with both TCP and UDP and to determine how much overhead is involved in examining the packets. It might also be interesting to run some similar experiments with protocols that use NACKs instead of ACKs.
Monday, September 29, 2008
MACAW
While there are a lot of different corner cases that this paper presents, and a lot of different reasons for the algorithms presented, the final protocol is quite simple to explain. The protocol is essentially RRTS-RTS-CTS-DS-DATA-ACK. This is improved over the MACA algorithm, which only had RTS-CTS-DATA. The paper lists one-by-one the reasons for this algorithm. Let's start with the DS (data sending). Whenever there is congestion, a node must wait until all data has already been sent before sending an RTS. However, when the node doesn't have the ability to detect whether or not data is being sent, it has no way of knowing when to send the RTS. The DS message solves this problem by describing how much time it will take the data to be sent, thereby letting all nodes know when they can send their next RTS.
We can continue with the RRTS. If a node cannot send a CTS because it is currently overhearing traffic from some other stream, then it must notify potential senders when that traffic is done. It does so by using an RRTS, which tells the potential senders that they may now send an RTS message. Without the RRTS, potential senders would randomly send RTS messages, with almost no chance of doing so at a time when there was no interference.
The last addition to the protocol is the ACK. This comes straight out of the E2E paper, which says that if something can be done more efficiently at the lower levels, it should be done there, rather than pushed to the ends. In this case, the use of the ACK allows for much higher throughput, because wireless links are considerably noisier and less reliable than physical links. Since the loss of a packet does not necessarily mean congestion of the link in question, TCP's congestion avoidance is not an appropriate reliability mechanism for wireless networks. Thus, the reliability is programmed in at the link layer.
There is one more significant issue that this paper raises, which is the question of the back-off counter. The paper suggests using a shared value for this back-off counter, since everyone should have a consistent view of the network. Anyone that receives a back-off value immediately stores it. The paper also suggests multiple back-off values: one for the sender and one for the receiver. If an RTS is sent but not received, this means that there is congestion at the receiver. If a CTS is sent but not received, this means that there is congestion at the sender. The back-off counters are decremented accordingly. At the same time, to avoid massive fluctuations in back-off counters, the increase/decrease algorithm is changed to a increase by a factor of 1.5, and a decrease by a constant of 1. All of these, when put together, allow a conistent view of the network by all nodes, as well as a fairly stable back-off counter.
This paper mentions almost nothing about nodes entering and leaving the ranges of base stations. Suppose a node leaves the range of a base station while the base station is transmitting to it? Does the lack of an ACK mean that the base station will try to retransmit? Similarly, suppose a node enters the network. How does it go about making contact with a base station, while making sure not to cause interference with transmissions that are currently in progress? It could listen for DS messages, and then send an RTS at the next available time slot, but this would certainly not work if it were alone in the network. These questions seem to be left unanswered by the paper.
We can continue with the RRTS. If a node cannot send a CTS because it is currently overhearing traffic from some other stream, then it must notify potential senders when that traffic is done. It does so by using an RRTS, which tells the potential senders that they may now send an RTS message. Without the RRTS, potential senders would randomly send RTS messages, with almost no chance of doing so at a time when there was no interference.
The last addition to the protocol is the ACK. This comes straight out of the E2E paper, which says that if something can be done more efficiently at the lower levels, it should be done there, rather than pushed to the ends. In this case, the use of the ACK allows for much higher throughput, because wireless links are considerably noisier and less reliable than physical links. Since the loss of a packet does not necessarily mean congestion of the link in question, TCP's congestion avoidance is not an appropriate reliability mechanism for wireless networks. Thus, the reliability is programmed in at the link layer.
There is one more significant issue that this paper raises, which is the question of the back-off counter. The paper suggests using a shared value for this back-off counter, since everyone should have a consistent view of the network. Anyone that receives a back-off value immediately stores it. The paper also suggests multiple back-off values: one for the sender and one for the receiver. If an RTS is sent but not received, this means that there is congestion at the receiver. If a CTS is sent but not received, this means that there is congestion at the sender. The back-off counters are decremented accordingly. At the same time, to avoid massive fluctuations in back-off counters, the increase/decrease algorithm is changed to a increase by a factor of 1.5, and a decrease by a constant of 1. All of these, when put together, allow a conistent view of the network by all nodes, as well as a fairly stable back-off counter.
This paper mentions almost nothing about nodes entering and leaving the ranges of base stations. Suppose a node leaves the range of a base station while the base station is transmitting to it? Does the lack of an ACK mean that the base station will try to retransmit? Similarly, suppose a node enters the network. How does it go about making contact with a base station, while making sure not to cause interference with transmissions that are currently in progress? It could listen for DS messages, and then send an RTS at the next available time slot, but this would certainly not work if it were alone in the network. These questions seem to be left unanswered by the paper.
Tuesday, September 23, 2008
Gb Switched Router
This paper gives a general overview of modern techniques used to improve router performance. In retrospect, it would have been much better to read this paper before reading the other paper. Too late now. This paper covers the operation and need for switched backplanes, as well as the iSLIP and ESLIP protocols.
The general idea behind routers is that there are various linecards which take incoming packets and forward them to a decision maker, and are also able to transmit outgoing packets. The key issue is the decision maker. In early routers, it was a single CPU. As this CPU became the bottleneck in routers, it was replaced with an individual decision maker for each linecard, with a bus connecting the various CPUs (so that packets can move from one linecard to another). Then, since the bus became the bottleneck, the need for switched backplanes arose.
A switched backplane is essentially a grid that allows any linecard to connect to any other linecard. The only caveat is that a linecard can only connect to a single other linecard at a time. Therefore, there needs to be a scheduler to open and close connections on the grid. The algorithm used to determine which connections to open/close is called iSLIP. It works by allowing the sources to request destinations, letting the destinations choose a source in round-robin fashion, and then letting the sources choose a destination in round-robin fashion. The sources have multiple requests because of virtual output queuing (VOQ). In VOQ, each source has multiple queues so that no packet is stuck behind other packets which cannot reach their destinations.
A few other improvements are possible, such as the use of ESLIP to accomodate for multicast messages, and the use of priority queues to more tightly control delay.
This paper introduces a classification system for blocking in the backplane that is quite useful. The first kind is called Head of Line (HOL) blocking. HOL blocking occurs when there is no VOQ, and a packet is unable to reach its destination even though that destination is idle because that packet is second in the queue; the first packet is destined for a destination that is currently busy. While VOQ solves this issue, it does not solve the issue of input blocking our output blocking (where a packet at a given input/output cannot be transmitted because that input/output is currently transmitting a different packet). These issues cannot be solved except in the case of multicast, when they are solved by ESLIP.
The general idea behind routers is that there are various linecards which take incoming packets and forward them to a decision maker, and are also able to transmit outgoing packets. The key issue is the decision maker. In early routers, it was a single CPU. As this CPU became the bottleneck in routers, it was replaced with an individual decision maker for each linecard, with a bus connecting the various CPUs (so that packets can move from one linecard to another). Then, since the bus became the bottleneck, the need for switched backplanes arose.
A switched backplane is essentially a grid that allows any linecard to connect to any other linecard. The only caveat is that a linecard can only connect to a single other linecard at a time. Therefore, there needs to be a scheduler to open and close connections on the grid. The algorithm used to determine which connections to open/close is called iSLIP. It works by allowing the sources to request destinations, letting the destinations choose a source in round-robin fashion, and then letting the sources choose a destination in round-robin fashion. The sources have multiple requests because of virtual output queuing (VOQ). In VOQ, each source has multiple queues so that no packet is stuck behind other packets which cannot reach their destinations.
A few other improvements are possible, such as the use of ESLIP to accomodate for multicast messages, and the use of priority queues to more tightly control delay.
This paper introduces a classification system for blocking in the backplane that is quite useful. The first kind is called Head of Line (HOL) blocking. HOL blocking occurs when there is no VOQ, and a packet is unable to reach its destination even though that destination is idle because that packet is second in the queue; the first packet is destined for a destination that is currently busy. While VOQ solves this issue, it does not solve the issue of input blocking our output blocking (where a packet at a given input/output cannot be transmitted because that input/output is currently transmitting a different packet). These issues cannot be solved except in the case of multicast, when they are solved by ESLIP.
Monday, September 22, 2008
Scaling Routers
I'm going to be honest here. I have no idea what this paper said. Not that it was a bad paper. I think this paper should stay in the syllabus. It's just that I would prefer to have read some more background material on router design so that I had the necessary experience to understand this paper.
That being said, this paper looks like it discusses some upcoming problems in scaling routers to deal with ever-increasing internet traffic, which seems like a good thing to do. Everybody wants their downloads to go faster, from movies and music to software updates. However, the paper seems to assume that in the future, we will have individual routers with lots of packets being pumped through them simultaneously. While I think that's possible, it seems like this router is being designed for high speed links across the continent. With large companies strategically placing caches close to clients, this kind of router may not be necessary. Then again, who knows?
The basic ideas behind this paper are doing very simple, yet elegant load balancing, and simplifying the meshing architecture. In order to get large amounts of throughput, they do a very simple round-robin type of load balancing. At the same time, by using optics to increase the speeds of the links connecting linecards, they are able to reduce the necessary number of links in the mesh.
The paper also introduces an algorithm called Full Ordered Frames First (FOFF) which allows it to guarantee that packets from the same connection are not transmitted out of order. Frankly, this seems like a somewhat silly restriction to put on a router. All of the papers we have read so far in this class have told us that the internet does not guarantee in-order delivery. The author claims that out-of-order delivery can cause unnecessary retransmissions in TCP. While these unnecessary retransmissions seem unlikely give the current implementation of TCP, if it is indeed the case that such a router would misbehave, it seems like the best thing to do would be to modify the TCP protocol.
That being said, this paper looks like it discusses some upcoming problems in scaling routers to deal with ever-increasing internet traffic, which seems like a good thing to do. Everybody wants their downloads to go faster, from movies and music to software updates. However, the paper seems to assume that in the future, we will have individual routers with lots of packets being pumped through them simultaneously. While I think that's possible, it seems like this router is being designed for high speed links across the continent. With large companies strategically placing caches close to clients, this kind of router may not be necessary. Then again, who knows?
The basic ideas behind this paper are doing very simple, yet elegant load balancing, and simplifying the meshing architecture. In order to get large amounts of throughput, they do a very simple round-robin type of load balancing. At the same time, by using optics to increase the speeds of the links connecting linecards, they are able to reduce the necessary number of links in the mesh.
The paper also introduces an algorithm called Full Ordered Frames First (FOFF) which allows it to guarantee that packets from the same connection are not transmitted out of order. Frankly, this seems like a somewhat silly restriction to put on a router. All of the papers we have read so far in this class have told us that the internet does not guarantee in-order delivery. The author claims that out-of-order delivery can cause unnecessary retransmissions in TCP. While these unnecessary retransmissions seem unlikely give the current implementation of TCP, if it is indeed the case that such a router would misbehave, it seems like the best thing to do would be to modify the TCP protocol.
Thursday, September 18, 2008
CSZ
This paper provides a hypothetical solution to the real-time flow vs data flow issue. It suggests that real-time flows that need certain guarantees from the network can explicitly request these guarantees, and that using routers with WFQ implemented will achieve these guarantees. Similarly, in order to achieve a good quality of service for adaptable real-time applications (that only ask for best effort) will have a FIFO+ queue within the WFQ to address their needs. However, these applications must provide guarantees to the network that they will operate within certain bounds (by providing a rate and a bucket size). If multiple levels of service are desired (such as an extra level of service for datagrams), then multiple FIFO+ queues can be used within the WFQ.
The idea behind a FIFO+ queue is that a packet should not be adversely affected by many different sources. Therefore, any router that causes a packet to be delayed (more than the average delay time for packets of its priority) will mark the packet with the extra delay time. A router receiving that packet can then "pretend" to have received it earlier. This reduces the overall jitter that will be experienced by packets on long trips. As with most algorithms, I have trouble imagining a world in which a Tier 2 ISP would not take advantage of this by marking all of the packets from its own customers.
Once again, the most difficult part of this algorithm is the incentive. There must be some sort of incentive (other than being a good samaritan) for a user to declare their packets to be of the "lowest" priority. Once again, economic incentives are an option, except that nobody wants to pay money by the byte (just ask a Verizon Wireless Customer).
Overall, I think one of the most important things that this paper has done is to classify the different kinds of traffic that flow across the internet. There exists a distinction between a two-way video chat on Skype, a video being watched on YouTube, and a high resolution trailer for Starcraft 2 that's only available for download; this paper has done an excellent job of making these distinctions clear.
The idea behind a FIFO+ queue is that a packet should not be adversely affected by many different sources. Therefore, any router that causes a packet to be delayed (more than the average delay time for packets of its priority) will mark the packet with the extra delay time. A router receiving that packet can then "pretend" to have received it earlier. This reduces the overall jitter that will be experienced by packets on long trips. As with most algorithms, I have trouble imagining a world in which a Tier 2 ISP would not take advantage of this by marking all of the packets from its own customers.
Once again, the most difficult part of this algorithm is the incentive. There must be some sort of incentive (other than being a good samaritan) for a user to declare their packets to be of the "lowest" priority. Once again, economic incentives are an option, except that nobody wants to pay money by the byte (just ask a Verizon Wireless Customer).
Overall, I think one of the most important things that this paper has done is to classify the different kinds of traffic that flow across the internet. There exists a distinction between a two-way video chat on Skype, a video being watched on YouTube, and a high resolution trailer for Starcraft 2 that's only available for download; this paper has done an excellent job of making these distinctions clear.
Future Internet
This paper was written in 1994, and is quite insightful in that it predicts the rise of real-time video and audio links across the internet. The paper attempts to provide design decisions for the future of the internet. In particular, it suggests that there be multiple tiers of service within the internet, and that higher tiers should be explicitly requested by applications. The final suggestion is that there be admission control (i.e. the internet should reject some flows) to increase the quality of service for currently existing flows.
There are so many problems here, I don't even know where to begin. The suggestion of multiple tiers of service within the internet is a fine suggestion (because, in fact, real-time applications have very different needs when compared to applications such as FTP). Furthermore, the suggestion that the distinction be done above the IP layer (perhaps at the protocol layer) is also a good suggestion, because it allows the IP layer to serve its current purpose without taking on an unrelated purpose.
The suggestion that applications should explicitly request better service, while seemingly logical at first, creates a lot of difficulties in practice. The largest problem to be faced here is the problem of incentives. If there is no incentive to request the lower quality of service, everybody will request the higher quality of service. If the incentive is, as the paper suggests, monetary, then this will create additional problems. Nevermind the fact that people generally prefer to be billed a flat rate for unlimited internet access; if a remote host starts a high QoS TCP connection to an unsuspecting victim, will he be charged for the ACKs that he sends back? As another example, it would seem impossible for a server to declare that it wanted to stream videos to users at a high QoS, while still allowing users to "opt out" of the high QoS based on financial considerations. In general, connections between different nodes that requests different QoS levels will be tricky as a whole.
The admission control suggestion seems to be more applicable to traditional telephone conversations than it is to the internet. As far as the internet is concerned, everything is a packet, and there are no flows. Rejecting one flow so that another has a higher QoS would be very difficult to do on a router that is situated between two endpoints for several reasons: 1) the router may not see all of the traffic of that flow, making it difficult to reject the whole flow and 2) keeping track of which flows need high QoS and rejecting other flows because of it would entail large amounts of state within the router. The idea of rejecting flows so that others can have higher QoS is even more ridiculous when we consider where the responsibility should fall. Can it be done by any router? Can it be done by all ASs or just Tier 1 service providers? Who can decide which flows are more important than others? These issues will plague the idea of admission control if anybody ever tries to implement it.
I am even more surprised that this paper doesn't have a large focus on authentication. One of the largest issues of the modern internet is that in general, it is easy to spoof your own identity. If this issue could be solved, it would lead to great improvements in the internet from fairer routing to simpler authentication methods/interfaces. This issue is not considered very much in this paper. I am very disappointed with the paper's general lack of foresight.
There are so many problems here, I don't even know where to begin. The suggestion of multiple tiers of service within the internet is a fine suggestion (because, in fact, real-time applications have very different needs when compared to applications such as FTP). Furthermore, the suggestion that the distinction be done above the IP layer (perhaps at the protocol layer) is also a good suggestion, because it allows the IP layer to serve its current purpose without taking on an unrelated purpose.
The suggestion that applications should explicitly request better service, while seemingly logical at first, creates a lot of difficulties in practice. The largest problem to be faced here is the problem of incentives. If there is no incentive to request the lower quality of service, everybody will request the higher quality of service. If the incentive is, as the paper suggests, monetary, then this will create additional problems. Nevermind the fact that people generally prefer to be billed a flat rate for unlimited internet access; if a remote host starts a high QoS TCP connection to an unsuspecting victim, will he be charged for the ACKs that he sends back? As another example, it would seem impossible for a server to declare that it wanted to stream videos to users at a high QoS, while still allowing users to "opt out" of the high QoS based on financial considerations. In general, connections between different nodes that requests different QoS levels will be tricky as a whole.
The admission control suggestion seems to be more applicable to traditional telephone conversations than it is to the internet. As far as the internet is concerned, everything is a packet, and there are no flows. Rejecting one flow so that another has a higher QoS would be very difficult to do on a router that is situated between two endpoints for several reasons: 1) the router may not see all of the traffic of that flow, making it difficult to reject the whole flow and 2) keeping track of which flows need high QoS and rejecting other flows because of it would entail large amounts of state within the router. The idea of rejecting flows so that others can have higher QoS is even more ridiculous when we consider where the responsibility should fall. Can it be done by any router? Can it be done by all ASs or just Tier 1 service providers? Who can decide which flows are more important than others? These issues will plague the idea of admission control if anybody ever tries to implement it.
I am even more surprised that this paper doesn't have a large focus on authentication. One of the largest issues of the modern internet is that in general, it is easy to spoof your own identity. If this issue could be solved, it would lead to great improvements in the internet from fairer routing to simpler authentication methods/interfaces. This issue is not considered very much in this paper. I am very disappointed with the paper's general lack of foresight.
Tuesday, September 16, 2008
XCP
This paper defines a new protocol in which routers and end nodes cooperate in order to achieve optimal flow and fairness. The router simply computes the difference between its current use and its optimal use, and then sends messages to nodes telling them how much to increase or decrease their window sizes by. Similarly, the end nodes must tell the routers their current congestion window size and estimated round trip time. By using information returned by the router (piggybacking on an ACK), the end nodes can reach optimal utilization in one round trip, as opposed to the many needed by TCP.
This system is especially useful in that it allows for efficient communications across mediums such as satellite links, which have high bandwidth, but also high round trip times. The high round trip times mean that algorithms such as TCP take an enormous amount of time to use all of the available bandwidth (since the congestion window is adjusted by 1 per round trip). In contrast, XCP allows it to be done in just one round trip, which should (hopefully) yield desirable results in such situations.
The only flaw is the obvious inability to control misbehaving users. Users who simply transmit too many packets are likely to get away with it, because the only thing the router does is ask them to slow down. It won't start dropping their packets until its queues are full, so a misbehaving client can really steal a lot of bandwidth from other users. Even when you try to push this responsibility to the edge routers, there is a problem: the Tier 2 ASs may try to "cheat" their Tier 1 providers to get more bandwidth for their own customers.
However, this proves the point that the internet could be much more efficient if only we were able to trust the end users. It also introduces a very important notion of the separation between fairness and efficiency control. By using a single algorithm to determine by how much the flow needs to change, and using a completely separate algorithm to determine how to distribute the adjustment between different nodes, they have essentially turned the router into 2 components which can be modified separately. This is important for future updates.
Speaking of updates, this paper glosses over the distribution issue. While it is true that it can probably coexist with TCP, separate queues for each is probably not ideal. Neither is sending a TCP packet to check for the existence of XCP, especially if that packet has to go through many routers to perform the check properly. And lastly, the installation of XCP one AS at a time is known as a "forklift upgrade", and is generally considered to be one of the worst ways to do an upgrade.
This system is especially useful in that it allows for efficient communications across mediums such as satellite links, which have high bandwidth, but also high round trip times. The high round trip times mean that algorithms such as TCP take an enormous amount of time to use all of the available bandwidth (since the congestion window is adjusted by 1 per round trip). In contrast, XCP allows it to be done in just one round trip, which should (hopefully) yield desirable results in such situations.
The only flaw is the obvious inability to control misbehaving users. Users who simply transmit too many packets are likely to get away with it, because the only thing the router does is ask them to slow down. It won't start dropping their packets until its queues are full, so a misbehaving client can really steal a lot of bandwidth from other users. Even when you try to push this responsibility to the edge routers, there is a problem: the Tier 2 ASs may try to "cheat" their Tier 1 providers to get more bandwidth for their own customers.
However, this proves the point that the internet could be much more efficient if only we were able to trust the end users. It also introduces a very important notion of the separation between fairness and efficiency control. By using a single algorithm to determine by how much the flow needs to change, and using a completely separate algorithm to determine how to distribute the adjustment between different nodes, they have essentially turned the router into 2 components which can be modified separately. This is important for future updates.
Speaking of updates, this paper glosses over the distribution issue. While it is true that it can probably coexist with TCP, separate queues for each is probably not ideal. Neither is sending a TCP packet to check for the existence of XCP, especially if that packet has to go through many routers to perform the check properly. And lastly, the installation of XCP one AS at a time is known as a "forklift upgrade", and is generally considered to be one of the worst ways to do an upgrade.
Subscribe to:
Posts (Atom)