The data-oriented transfer service is essentially an abstraction layer that abstracts the transfer of large files into a service that can be used via API calls at the application layer.
The basic concept behind DOT is that file transfer is used by a large number of protocols (HTTP, FTP, SMTP, etc.), each of which could benefit from the separation between the transfer of metadata and the transfer of the actual file. DOT suggests that each file transferred should get a unique ID, and that a sender should upload files to DOT, and then pass a unique ID (as well as some hints) to the receiver, who can then receive the file from DOT.
The suggested benefits of this scheme are:
1) abstraction - the underlying transfer method can be changed from a TCP connection to a torrenting scheme without any trouble.
2) caching - by caching the files at local nodes, you can reduce the overall bandwidth use of multiple file transfers
3) faster transfer - in theory DOT can split a file up and send it to its destination over multiple links, thereby getting the file there faster
The authors claim that this file transfer scheme will be widely applicable. Actually, I think this transfer scheme is very narrowly applicable. Certainly, for large e-mail attachments, this scheme has SOME merit (see discussion on expiration below). However, the authors provide nearly no performance data, and they avoid discussing performance for small files. This leads us to believe that for small files (such as webpages, which constitute a good chunk of internet traffic), the DOT scheme has too much overhead to actually be useful. In the world of the web, it is probably best suited to embedded videos, which are usually handled by content distribution networks anyway.
There is a serious flaw in DOT concerning the expiration and caching of data. Let's begin with caching. As we saw in the DNS caching paper, most of the requests that go out across the internet are to servers that are visited exactly once. The rest are to a few very popular servers. It is unreasonable to expect caching of large files to be effective in a scenario where caching of DNS entries is not effective. Sure, DOT could cache files for very popular websites, but this would in essence be duplicating work already done by CDNs.
The expiration of data in DOT is also a serious issue. According to this paper, data expires when the sender sends notice to the DOT that the data need no longer be stored. This makes the DOT vulnerable to denial of service attacks by clients that upload data, and then never mark it as deletable. Furthemore, consider the e-mail sender we discussed above. Suppose he sends an e-mail with a large attachment out to a large number of recipientns. When is the correct time to mark the attachment as deletable? It is likely to be AFTER all recipients have downloaded the attachment. Of course, it is very difficult for the sender to know when all the recipients have finished downloading the file; this would likely require some sort of acknowledgement of receipt of the file. And, of course, if some of the e-mails bounce, or a single address forwards to multiple recipients, this will make counting much more difficult. In other words, the protocol must be modified in order to safely deploy DOT. Or, the sender can just never mark his attachment for deletion.
I'm not actually sure what kind of client would regularly use DOT to transfer files. BitTorrent is fairly dominant in the large file transfer market, and the rest of file transfers are likely to be over HTTP, in which case the files are likely to be small, and the overhead is likely to be significant. I'm not sure what problem the DOT system solves.
Monday, November 17, 2008
Thursday, November 13, 2008
X-Trace
Basically, what is being proposed here is a system that will be present throughout all the different levels of any internet application so as to be able to help people debug problems that they encounter. The idea is that the internet is getting REALLY complex (which is very true - just look at how much material we have for this class), and therefore, we need some sort of tool that will help us debug problems.
X-Trace generally assumes that the flow of packets across the internet will generate a tree of causality. There's a very good example of this in the paper, with the root being a web browser, and the leaves being a tree of DNS requests, and a tree with an HTTP request that leads to an Apache call. X-Trace accomplishes this kind of tracing with some metadata that is kept by all levels of a request. The metadata includes a unique identifier, an operation identifier, a parent id, and some options. The unique identifier allows reports from the same request to be grouped together, whereas the parent id allows these reports to be arranged into the appropriate tree structure.
Thus, for an intermediate device, application, or library to implement X-Trace, it must essentially implement two different calls: PushNext() and PushDown(). PushNext() indicates that it is pushing the X-Trace metadata to the next logical node in the eventual X-Trace tree. PushDown() indicates that the metadata is being pushed to a lower layer.
Once everyone has implemented these calls, they can generate reports for each X-Trace request. These reports are sent to a local handler (for security purposes). The X-Trace metadata also has a tag that allows them to (optionally) send the report to the original requester. This step is optional, since a company like Wikipedia or Google may not want to reveal any information about their internal composition.
The major issue with X-Trace seems to be deployment. For some protocols, such as HTTP, deployment is made easy through the use of extension headers. For others, such as TCP, this becomes much more difficult, and requires some changes to the Linux kernel. For UDP, it is impossible without either changing the protocol itself, or adding a tiny layer on top of it. If X-Trace can be deployed across the internet, and protocols can be altered so as to support it, then it will be an invaluable debugging tool. However, the likelihood of such a deployment seems small.
X-Trace generally assumes that the flow of packets across the internet will generate a tree of causality. There's a very good example of this in the paper, with the root being a web browser, and the leaves being a tree of DNS requests, and a tree with an HTTP request that leads to an Apache call. X-Trace accomplishes this kind of tracing with some metadata that is kept by all levels of a request. The metadata includes a unique identifier, an operation identifier, a parent id, and some options. The unique identifier allows reports from the same request to be grouped together, whereas the parent id allows these reports to be arranged into the appropriate tree structure.
Thus, for an intermediate device, application, or library to implement X-Trace, it must essentially implement two different calls: PushNext() and PushDown(). PushNext() indicates that it is pushing the X-Trace metadata to the next logical node in the eventual X-Trace tree. PushDown() indicates that the metadata is being pushed to a lower layer.
Once everyone has implemented these calls, they can generate reports for each X-Trace request. These reports are sent to a local handler (for security purposes). The X-Trace metadata also has a tag that allows them to (optionally) send the report to the original requester. This step is optional, since a company like Wikipedia or Google may not want to reveal any information about their internal composition.
The major issue with X-Trace seems to be deployment. For some protocols, such as HTTP, deployment is made easy through the use of extension headers. For others, such as TCP, this becomes much more difficult, and requires some changes to the Linux kernel. For UDP, it is impossible without either changing the protocol itself, or adding a tiny layer on top of it. If X-Trace can be deployed across the internet, and protocols can be altered so as to support it, then it will be an invaluable debugging tool. However, the likelihood of such a deployment seems small.
Internet Measurement
This paper basically analyzes the performance of TCP across the internet. By using more than 30 different sites, they get a relatively good collection of flows across the internet. They measure a few different variables to determine whether or not TCP is working as well as it could be. Among these variables are packet reordering, packet replication, packet corruption, bottleneck bandwidth, packet loss, packet loss independence, and packet delay.
The goal here is to provide suggestions for ways to improve the TCP protocol (or implementation thereof). Let's start with packet reordering. They find that the only real effect that packet reordering has on TCP is that it can occasionally trigger retransmissions, when delaying the duplicate acks would have sufficed. To counteract this, they note that if the number of duplicate acks required to retransmit is reduced to 2, but the receiver waits 20 ms before transmitting a duplicate ack, it reduces the number of unnecessary retransmissions. However, if these two changes are not used together, each of them will actually degrade TCP performance, and so they consider it impractical to deploy.
They found a little bit of packet replication, but could not find a good explanation. They did notice, however, that it was site-specific. In terms of packet corruption, they noted that about 1 packet in 5000 arrives corrupted. With a 16 bit checksum, they argue that there is a one in 3000000 chance that a corrupted packet will be accepted, though this probably fails to take into account the nature of bit corruption, as well as the way the checksum is computed. They still recommend increasing the number of bits in the checksum. Corruption for ack packets seems much less common, possibly due to the smaller payload.
They introduced a new method for determining bottleneck bandwidth. In general, when two packets are sent in immediate succession, they sit behind eachother in the queue of some router, and the time interval between their arrivals is a good estimate for the time it took to send one of the two packets. They introduce the notion of computing this value at the RECEIVER, because this will remove any trouble caused by the delay that ACKs encounter on their way back. Furthermore, since they discover that links can be very asymmetric, this method does not need to compensate for the asymmetry. Since some internet connections are spread across several links, or load-balanced, they introduce the concept of not just doing this for packet pairs, but also doing it with 4 or 5 packets. Their results indicate that estimates made at the SENDER are only accurate around 60% of the time, which is a shame, because it means that the TCP sender cannot use the timing of ACKs to estimate a bottleneck bandwidth.
Next, they examine loss rates. In general, they note that most links have one of two states: quiescent or busy. In the quiescent state, there is no packet loss. In the busy state, the loss rate is usually a few percent. They notice that the state of a link is closely correlated with the time of day, and that a quiescent link usually stays in that state for several hours. They are able to conclude that packet losses are correlated with eachother, and are not independent. They suggest using RED in routers instead of tail-drop. They also note that packet loss is sometimes completely asymmetric (by measuring the packet loss rates in both directions).
They then measure the effectiveness of TCP retransmission. They note that Solaris has some problems estimating round-trip time, and exclude it from their main results. They then note that only about 1/6th of retransmissions are unavoidable, and suggest that SACKs can be used to cut down on the number of retransmissions resulting from coarse feedback.
In general, this paper is really thick, and contains a lot of different computations, as well as a lot of different suggestions for improving TCP. I think this paper is really important, because it analyzes just how well TCP is ACTUALLY working as a protocol across the internet. It's one thing to develop a model and to theorize that one algorithm will work better than another, but it's another to actually do measurements.
The goal here is to provide suggestions for ways to improve the TCP protocol (or implementation thereof). Let's start with packet reordering. They find that the only real effect that packet reordering has on TCP is that it can occasionally trigger retransmissions, when delaying the duplicate acks would have sufficed. To counteract this, they note that if the number of duplicate acks required to retransmit is reduced to 2, but the receiver waits 20 ms before transmitting a duplicate ack, it reduces the number of unnecessary retransmissions. However, if these two changes are not used together, each of them will actually degrade TCP performance, and so they consider it impractical to deploy.
They found a little bit of packet replication, but could not find a good explanation. They did notice, however, that it was site-specific. In terms of packet corruption, they noted that about 1 packet in 5000 arrives corrupted. With a 16 bit checksum, they argue that there is a one in 3000000 chance that a corrupted packet will be accepted, though this probably fails to take into account the nature of bit corruption, as well as the way the checksum is computed. They still recommend increasing the number of bits in the checksum. Corruption for ack packets seems much less common, possibly due to the smaller payload.
They introduced a new method for determining bottleneck bandwidth. In general, when two packets are sent in immediate succession, they sit behind eachother in the queue of some router, and the time interval between their arrivals is a good estimate for the time it took to send one of the two packets. They introduce the notion of computing this value at the RECEIVER, because this will remove any trouble caused by the delay that ACKs encounter on their way back. Furthermore, since they discover that links can be very asymmetric, this method does not need to compensate for the asymmetry. Since some internet connections are spread across several links, or load-balanced, they introduce the concept of not just doing this for packet pairs, but also doing it with 4 or 5 packets. Their results indicate that estimates made at the SENDER are only accurate around 60% of the time, which is a shame, because it means that the TCP sender cannot use the timing of ACKs to estimate a bottleneck bandwidth.
Next, they examine loss rates. In general, they note that most links have one of two states: quiescent or busy. In the quiescent state, there is no packet loss. In the busy state, the loss rate is usually a few percent. They notice that the state of a link is closely correlated with the time of day, and that a quiescent link usually stays in that state for several hours. They are able to conclude that packet losses are correlated with eachother, and are not independent. They suggest using RED in routers instead of tail-drop. They also note that packet loss is sometimes completely asymmetric (by measuring the packet loss rates in both directions).
They then measure the effectiveness of TCP retransmission. They note that Solaris has some problems estimating round-trip time, and exclude it from their main results. They then note that only about 1/6th of retransmissions are unavoidable, and suggest that SACKs can be used to cut down on the number of retransmissions resulting from coarse feedback.
In general, this paper is really thick, and contains a lot of different computations, as well as a lot of different suggestions for improving TCP. I think this paper is really important, because it analyzes just how well TCP is ACTUALLY working as a protocol across the internet. It's one thing to develop a model and to theorize that one algorithm will work better than another, but it's another to actually do measurements.
Wednesday, November 5, 2008
i3
This paper presents the Internet Indirection Infrastructure, which is basically yet another addressing scheme built on top of IP. It is, however, slightly more flexible than the last one I complained about. In particular, it makes multicast and load balancing fairly easy.
Once again, the paper suggests a Chord structure somewhere within the internet that will store a collection of identifiers of m bits. Any given machine can store a trigger, which in its simplest form stores an identifier and a location, in this DHT. Then, messages that are sent across the internet are sent to these identifiers instead of to IP addresses. The identifiers in the messages are matched to identifiers in the DHT (sometimes using partial matches), and sent to the IP addresses found in the associated triggers.
This system allows for some fancy stuff, such as using partial matches to do multicast (each recipient puts in a trigger with the same identifier) or load balancing (have k random bits at the end of the identifier, and you will be directed to the server with the largest partial match). It also allows for some degree of source routing, by using identifier stacks instead of just plain identifiers.
Once again, I would like to complain about the terrible things this is going to do to both latency and round trip time across the internet. The latency stretch incurred by this system seems to be on the order of 4-6, which I think is fairly unacceptable. Furthermore, either packets must always be routed through the i3 system (which has the triangle routing problem), or destination IPs will be cached at the sender, which makes the cool features such as multicast and source routing much more difficult. I also think that they have not really addressed the issues associated with source routing (you can tie up network resources without creating routing loops).
Interestingly, I think this system might work very well as an opt-in system rather than an internet standard. It enables some very cool features, but it has some clear drawbacks (i.e. QoS) that I'd rather not see when accessing CNN or Google.
Once again, the paper suggests a Chord structure somewhere within the internet that will store a collection of identifiers of m bits. Any given machine can store a trigger, which in its simplest form stores an identifier and a location, in this DHT. Then, messages that are sent across the internet are sent to these identifiers instead of to IP addresses. The identifiers in the messages are matched to identifiers in the DHT (sometimes using partial matches), and sent to the IP addresses found in the associated triggers.
This system allows for some fancy stuff, such as using partial matches to do multicast (each recipient puts in a trigger with the same identifier) or load balancing (have k random bits at the end of the identifier, and you will be directed to the server with the largest partial match). It also allows for some degree of source routing, by using identifier stacks instead of just plain identifiers.
Once again, I would like to complain about the terrible things this is going to do to both latency and round trip time across the internet. The latency stretch incurred by this system seems to be on the order of 4-6, which I think is fairly unacceptable. Furthermore, either packets must always be routed through the i3 system (which has the triangle routing problem), or destination IPs will be cached at the sender, which makes the cool features such as multicast and source routing much more difficult. I also think that they have not really addressed the issues associated with source routing (you can tie up network resources without creating routing loops).
Interestingly, I think this system might work very well as an opt-in system rather than an internet standard. It enables some very cool features, but it has some clear drawbacks (i.e. QoS) that I'd rather not see when accessing CNN or Google.
DOA
This paper essentially suggests an alternate addressing scheme built on top of IP known DOA (delegation oriented architecture). It purports to address the problems created by NAT and firewalls - that is, they violate the principles of the internet. It claims to be better than IPv6, because the addresses do not reflect any kind of network topology (though what is wrong with that, I cannot tell).
The basic idea is that every machine anywhere has a 160-bit EID. These EIDs can be resolved to IPs through the use of a global lookup table. They suggest that this global lookup table be implemented as a DHT. Then, using a NAT or a firewall becomes simple. 1) You send your information (EID to IP mapping) to the NAT or firewall. 2) You place an entry in the EID mapping that maps your EID to the address of the NAT or firewall. After these two steps have been accomplished, a packet destined for your EID will make its way to the NAT or firewall through normal IP routing, and from there to you, with information that your NAT or firewall keeps in its local state.
This allows for some nice things, such as chaining intermediary elements, and the use of intermediate nodes that are not directly on the path between your own machine and other nodes on the internet.
The costs, though, are significant. This system is bad news for latency, since the average amount of time to resolve an EID was on the order of 138 ms. If that is just their test system, then it is reasonable to assume that this would increase (at least a little) for a larger DHT. After having read the paper on DNS performance, which points out that there are a large number of sites that are visited only once, this probably means that the quality of internet users' experiences would suffer at least a little. Most importantly, many connections are short-lived http connections, and users would like their pages to load quickly.
My own personal complaint about this system (which extends beyond the latency problem noted above) is that it essentially imposes a structure on the internet through its use of a DHT to do EID resolution. While it definitely solves the exhaustion of IPv4 addresses, so does IPv6. And they both impose some sort of structure on the internet. For IPv6, that structure is hierarchical addressing. For DOA, it is a DHT across the internet. The hierarchical system has been shown to have at least some merit (as in the case of DNS), whereas a DHT seems like it would suffer from frequent node losses which, while they would not affect correctness, would at the very least affect performance.
The basic idea is that every machine anywhere has a 160-bit EID. These EIDs can be resolved to IPs through the use of a global lookup table. They suggest that this global lookup table be implemented as a DHT. Then, using a NAT or a firewall becomes simple. 1) You send your information (EID to IP mapping) to the NAT or firewall. 2) You place an entry in the EID mapping that maps your EID to the address of the NAT or firewall. After these two steps have been accomplished, a packet destined for your EID will make its way to the NAT or firewall through normal IP routing, and from there to you, with information that your NAT or firewall keeps in its local state.
This allows for some nice things, such as chaining intermediary elements, and the use of intermediate nodes that are not directly on the path between your own machine and other nodes on the internet.
The costs, though, are significant. This system is bad news for latency, since the average amount of time to resolve an EID was on the order of 138 ms. If that is just their test system, then it is reasonable to assume that this would increase (at least a little) for a larger DHT. After having read the paper on DNS performance, which points out that there are a large number of sites that are visited only once, this probably means that the quality of internet users' experiences would suffer at least a little. Most importantly, many connections are short-lived http connections, and users would like their pages to load quickly.
My own personal complaint about this system (which extends beyond the latency problem noted above) is that it essentially imposes a structure on the internet through its use of a DHT to do EID resolution. While it definitely solves the exhaustion of IPv4 addresses, so does IPv6. And they both impose some sort of structure on the internet. For IPv6, that structure is hierarchical addressing. For DOA, it is a DHT across the internet. The hierarchical system has been shown to have at least some merit (as in the case of DNS), whereas a DHT seems like it would suffer from frequent node losses which, while they would not affect correctness, would at the very least affect performance.
Sunday, November 2, 2008
DNS Caching
This paper analyzes the performance of DNS; in particular, it attempts to measure and account for DNS packets that are sent unnecessarily. While it seems like a daunting task, they do have some good results.
Their experimental setup consists of a single node that is placed at the location where a university network connects to the rest of the internet. The node then measures both DNS lookups and regular connections across the node. They can then correlate their TCP connections with their DNS lookups. Their results consist of 3 major findings.
1. A large number of DNS lookups go unanswered. They found approximately 4 million answered lookups, with approximately 1.2 query packets for each, and approximately 10 million query packets total. This means that the amount of DNS traffic can be reduced significantly by fixing problems such as incorrect names, or the "loop-back" issue. They suggest configuring DNS clients not to conduct lookups for names that are not fully qualified.
2. Cache-sharing is not that useful past about 25 clients. They measured this by having a hypothetical cache, and then grouping clients by source IP into hypothetical shared caches. The end result was that shifting from no sharing to sharing by 25 clients improved performance, but increasing to over a thousand clients had no significant performance improvement. They explained this with the "popularity" theory. More than half of the DNS lookups were to unique names that were queried only once. In other words, there is a very small number of servers that are very popular, and a very large number that are relatively unknown. Caching is only good for the popular servers, and therefore doesn't require an enormous number of clients to cache all the popular servers.
3. NS caching is incredibly useful. The miss rates on name servers is approximately 25%, which means that if NS caching was turned off, the number of DNS queries making it to the root would increase by a factor of four. Since this is highly undesirable, NS caching should remain as-is; this is in contrast to A caching, which was addressed in item number 2.
Their experimental setup consists of a single node that is placed at the location where a university network connects to the rest of the internet. The node then measures both DNS lookups and regular connections across the node. They can then correlate their TCP connections with their DNS lookups. Their results consist of 3 major findings.
1. A large number of DNS lookups go unanswered. They found approximately 4 million answered lookups, with approximately 1.2 query packets for each, and approximately 10 million query packets total. This means that the amount of DNS traffic can be reduced significantly by fixing problems such as incorrect names, or the "loop-back" issue. They suggest configuring DNS clients not to conduct lookups for names that are not fully qualified.
2. Cache-sharing is not that useful past about 25 clients. They measured this by having a hypothetical cache, and then grouping clients by source IP into hypothetical shared caches. The end result was that shifting from no sharing to sharing by 25 clients improved performance, but increasing to over a thousand clients had no significant performance improvement. They explained this with the "popularity" theory. More than half of the DNS lookups were to unique names that were queried only once. In other words, there is a very small number of servers that are very popular, and a very large number that are relatively unknown. Caching is only good for the popular servers, and therefore doesn't require an enormous number of clients to cache all the popular servers.
3. NS caching is incredibly useful. The miss rates on name servers is approximately 25%, which means that if NS caching was turned off, the number of DNS queries making it to the root would increase by a factor of four. Since this is highly undesirable, NS caching should remain as-is; this is in contrast to A caching, which was addressed in item number 2.
DNS
This paper assumes that the reader knows the details of name lookup as they stood in 1988, which makes it somewhat difficult to understand the finer details of the paper. Below is my best attempt at understanding this paper.
The problems with the existing system, which was a HOSTS.txt file, were twofold. First, the file was growing large and unwieldy. Second, the administrative difficulties associated with the file were growing more than linearly. As a result, the DNS system was proposed.
DNS consists of multiple zones. Each zone is responsible for DNS lookups within its own zone. DNS supports multiple levels of hierarchy by allowing each zone to delegate sub-zones, which are also responsible for their own DNS lookups. This has the advantage of allowing different organizations to have different number of levels within their naming schemes. Each sub-zone gets a label, which can be a collection of 8-bit values. The length of a label cannot exceed 63 values, and the total length cannot exceed 256 such values (though apparently, those maximums are subject to change).
The DNS system consists of both DNS servers and DNS resolvers. The choice to separate these two systems stems from the fact that the storage of data and the protocols for accessing it should be different. The servers store data, whereas the resolvers implement the algorithms that enable them to access and distribute the data. In other words, different resolvers can be used throughout different systems so as to better serve the end-users, who may have a wide variety of operating systems or architectures.
One of the most interesting things about this paper is that they specifically took into consideration the difficulty of adopting DNS. They decided to use a relatively lightweight system so as not to discourage people from using DNS. They also wanted the system to be easily extensible; these two goals lead to a delicate balancing act.
I think the most interesting part of this paper is the part where they discuss failures. In particular, the tendency of system administrators to just copy examples out of the documentation, or to make mistakes (such as switching the identifier and TTL fields), led to incredibly poor performance across the system. Furthermore, their desire to simply get a system that worked, rather than a system that worked well, undermined the efforts of the DNS designers. In particular, system administrators would apparently not have their top level servers in different networks, but claimed that they were not a single point of failure anyway.
The problems with the existing system, which was a HOSTS.txt file, were twofold. First, the file was growing large and unwieldy. Second, the administrative difficulties associated with the file were growing more than linearly. As a result, the DNS system was proposed.
DNS consists of multiple zones. Each zone is responsible for DNS lookups within its own zone. DNS supports multiple levels of hierarchy by allowing each zone to delegate sub-zones, which are also responsible for their own DNS lookups. This has the advantage of allowing different organizations to have different number of levels within their naming schemes. Each sub-zone gets a label, which can be a collection of 8-bit values. The length of a label cannot exceed 63 values, and the total length cannot exceed 256 such values (though apparently, those maximums are subject to change).
The DNS system consists of both DNS servers and DNS resolvers. The choice to separate these two systems stems from the fact that the storage of data and the protocols for accessing it should be different. The servers store data, whereas the resolvers implement the algorithms that enable them to access and distribute the data. In other words, different resolvers can be used throughout different systems so as to better serve the end-users, who may have a wide variety of operating systems or architectures.
One of the most interesting things about this paper is that they specifically took into consideration the difficulty of adopting DNS. They decided to use a relatively lightweight system so as not to discourage people from using DNS. They also wanted the system to be easily extensible; these two goals lead to a delicate balancing act.
I think the most interesting part of this paper is the part where they discuss failures. In particular, the tendency of system administrators to just copy examples out of the documentation, or to make mistakes (such as switching the identifier and TTL fields), led to incredibly poor performance across the system. Furthermore, their desire to simply get a system that worked, rather than a system that worked well, undermined the efforts of the DNS designers. In particular, system administrators would apparently not have their top level servers in different networks, but claimed that they were not a single point of failure anyway.
Subscribe to:
Posts (Atom)