This paper describes a programmable hardware designed to allow rapid prototype of new hardware switch and router designs. This hardware is built-up from components commonly used for research and education outside of the networking space; the second version described in the paper uses a standard PCI bus for control and provides four gigabit ethernet outputs, so it is practical for researchers to deploy and can handle convincingly large amounts of load.
The research need filled by NetFPGA is an obvious one: most deployed networks work in large part using specialized hardware. Networking researchers typically did not have the means to create or modify hardware routers, so new ideas were tested with software routers. When tests with software routers yielded subpar performance, as they often do, authors would often argue that next-generation hardware routers or switches would be able to provide the functionality easily and without any loss of performance. NetFPGA allows these researchers to stop the hand-waving.
Wednesday, November 11, 2009
Monday, November 9, 2009
A Policy-aware Switching Layer for Data Centers
This paper proposes a switching architecture to ensure that some traffic is always routed through certain middleboxes. Given some collection of middleboxes of various types, the administrator specifies that the traffic matching some (source interface, source address/port, destination address/port) pattern must be forwarded through a certain type of middlebox (or routed to their final destination). Chains of middleboxes are specified by using a prior middlebox as the source interface type.
Switches along the paths of packets handle traffic that needs to be routed through a middlebox by encapsulating the ethernet frame in another ethernet frame destined for the middlebox. The router adjacent to the middlebox chosen removes this encapsulation, allowing the middlebox to act as if it were on the actual path.
The primary challenges of implementing this scheme comes with handling changes. To ensure compliance during a policy change without being able to mark packets passing through middleboxes, the authors propose dividing a change from policy P1 to P2 into multiple steps. First, each type of middlebox (relevant to the policy change) is split into two types (say, old and new) of middleboxes. Then (after the new-type middleboxes have processed all old traffic), the new policy is installed replacing the old type with the new type everywhere. Finally, after the new policy has been installed on all switches (and the old type middleboxes have processed all pending traffic), all middleboxes of the old type are switched to middleboxes of the new type.
The primary disadvantage of this routing scheme is latency. Compared to the traditional approach of placing middleboxes directly in the natural path of the packets, this scheme imposes an extra approx. 0.3 ms (based on the authors' testbed) of latency. The authors argue that this difference is insignificant given the general low-latency of the environment, but, for data-center-internal traffic, this may double the latency, which is very likely to substantially affect performance.
Switches along the paths of packets handle traffic that needs to be routed through a middlebox by encapsulating the ethernet frame in another ethernet frame destined for the middlebox. The router adjacent to the middlebox chosen removes this encapsulation, allowing the middlebox to act as if it were on the actual path.
The primary challenges of implementing this scheme comes with handling changes. To ensure compliance during a policy change without being able to mark packets passing through middleboxes, the authors propose dividing a change from policy P1 to P2 into multiple steps. First, each type of middlebox (relevant to the policy change) is split into two types (say, old and new) of middleboxes. Then (after the new-type middleboxes have processed all old traffic), the new policy is installed replacing the old type with the new type everywhere. Finally, after the new policy has been installed on all switches (and the old type middleboxes have processed all pending traffic), all middleboxes of the old type are switched to middleboxes of the new type.
The primary disadvantage of this routing scheme is latency. Compared to the traditional approach of placing middleboxes directly in the natural path of the packets, this scheme imposes an extra approx. 0.3 ms (based on the authors' testbed) of latency. The authors argue that this difference is insignificant given the general low-latency of the environment, but, for data-center-internal traffic, this may double the latency, which is very likely to substantially affect performance.
Internet Indirection Infrastructure
This paper describes an overlay-based Internet routing service built over the primitives of a DHT. Addresses in the overlay address consistent of two pieces, one which must match exactly and the other which is matched to the closest (longest prefix match) available address when routing messages. Receivers arrange to have an address routed to them by inserting a mapping (called a trigger) from an overlay address to some list of (overlay or IP) addresses. When a message is sent to an overlay address, these triggers are found, and for each trigger, the message is forwarded to the first functional address, passing along any left-over addresses in the trigger as metadata. These triggers are expired unless refreshed periodically and can be removed only if the destination-part is known. Conflicts in address assignment are avoided by using a sufficiently large address space.
The paper envisions that this addressing mechanism can be used to implement many commonly requested routing services:
Other concerns about this system are ones of security. The most obvious issue is that the flexibility to implement multicast comes with the ability to send massive amounts of duplicitous traffic to a victim host. The authors propose sending challenges to the trigger's mapped address to assure that the address to which triggers map actually permits the mapping. For cases where the victim is the infrastructure itself, the authors propose assigning resources based on the end-host inserting the trigger and detecting loops using either test packets or a bloom filter to mark visited hosts.
The authors also address concerns of eavesdropping or hijacking communications using the triggers. The authors argued that random private triggers would prevent eavesdropping attacks because a malicious third-party would need to guess the private trigger. Similarly, the authors would prevent hijacking by having the public trigger merely forward to a (hopefully unguessable) private trigger required to remove the public.
I felt that these security concerns would be better solved by using a traditional cryptographic end-to-end solution for hijacking and eavesdropping concerns (perhaps by encoding public keys in the public triggers) and authentication for trigger-removal requests. The authors wish i3 to be a relatively configuration-free system distributed between multiple administrative domains, to achieve these goals, almost any party should be able to run an i3 node. Given this, it seems a more viable attack would be to collect triggers by running (perhaps many) i3 nodes; since the trigger's values will be distributed at random among the i3 nodes and forwarded to other i3 nodes for caching, an attacker should be able to get the values of many private triggers.
The paper envisions that this addressing mechanism can be used to implement many commonly requested routing services:
- mobility — the mobile host simply maintains a trigger with a permanent address, arranging for it to point to its current real address;
- multiast — each subscribing host inserts a trigger for the multicast address (or, for large multicast groups, the hosts can arrange for a tree of triggers);
- anycast — endpoint encode their preferences in the inexactly matched portion of the address and ensure that exactly one trigger is the closest match;
- service composition — the end-host wishing to insert the service inserts a trigger listing the service, then itself; the service agrees to forward the message to the address it receives as metadata;
Other concerns about this system are ones of security. The most obvious issue is that the flexibility to implement multicast comes with the ability to send massive amounts of duplicitous traffic to a victim host. The authors propose sending challenges to the trigger's mapped address to assure that the address to which triggers map actually permits the mapping. For cases where the victim is the infrastructure itself, the authors propose assigning resources based on the end-host inserting the trigger and detecting loops using either test packets or a bloom filter to mark visited hosts.
The authors also address concerns of eavesdropping or hijacking communications using the triggers. The authors argued that random private triggers would prevent eavesdropping attacks because a malicious third-party would need to guess the private trigger. Similarly, the authors would prevent hijacking by having the public trigger merely forward to a (hopefully unguessable) private trigger required to remove the public.
I felt that these security concerns would be better solved by using a traditional cryptographic end-to-end solution for hijacking and eavesdropping concerns (perhaps by encoding public keys in the public triggers) and authentication for trigger-removal requests. The authors wish i3 to be a relatively configuration-free system distributed between multiple administrative domains, to achieve these goals, almost any party should be able to run an i3 node. Given this, it seems a more viable attack would be to collect triggers by running (perhaps many) i3 nodes; since the trigger's values will be distributed at random among the i3 nodes and forwarded to other i3 nodes for caching, an attacker should be able to get the values of many private triggers.
Wednesday, November 4, 2009
DNS Performance and the Effectiveness of Caching
This is a study of DNS in the wild, using traces of DNS requests and responses leaving two adminstrative domains along with TCP connections and disconnections. They found typical lookup performance was better than the '88 paper, but, still, many lookups would take an exceptionally long time from a user's perspective, apparently due to network or configuration problems. About 20% of all lookups got no answer (and no error repsonse) providing both high lookup latency and a probably uncachable negative result. Around 4% of the unanswered lookups were authority forwarding loops — an obvious misconfiguration. Some popular negative responding lookups were found to be common misconfigurations (e.g. asking the root servers to resolve 'loopback' or 'loghost').
The authors of the paper, however, were not mostly concerned with misconfiguration but with the effect of caching and TTL settings. The authors generally found that caching worked well for nameserver records, so most queries required few referrals (each of which is an extra round-trip to a server), substantially decreasing the latency of lookups. The authors found that the names requested followed a Zipf-like distribution and therefore most of the benefit of caching was obtained by caching relatively few names. They also found, based on the TCP trace, that because accesses to the same domain were highly clustered, short TTLs (popular for load balancing), did not cause substantial increases in the number of DNS queries or user-perceived latency.
The authors of the paper, however, were not mostly concerned with misconfiguration but with the effect of caching and TTL settings. The authors generally found that caching worked well for nameserver records, so most queries required few referrals (each of which is an extra round-trip to a server), substantially decreasing the latency of lookups. The authors found that the names requested followed a Zipf-like distribution and therefore most of the benefit of caching was obtained by caching relatively few names. They also found, based on the TCP trace, that because accesses to the same domain were highly clustered, short TTLs (popular for load balancing), did not cause substantial increases in the number of DNS queries or user-perceived latency.
Development of the Domain Name System
This article describes the design goals and some of the rationale behind the DNS protocol. The system DNS replaced was clearly neither scalable or efficient — previously, programs would scan a flat file listing hostnames and their corresponding IP addresses, and this file would be distributed to all end hosts. The replacement was to be distributed, so multiple adminstrative domains could add hosts, and was to be lightweight and provide cache, so as to provide comparable performance to the local database approach. Loftier goals of providing extensibility, but this seemed to be reflected in the initial design primarily in the existence of multiple types of records and the lack of structure demanded on names.
To achieve the distributed administrative control, DNS used an explicit hierarchy, which was to reflect the actual administrative hierarchy of the network. Each part of this hierarchy (a ‘zone’) is assigned to one or more DNS servers (each of which may be responsible for many distinct zones). Each DNS server returns a time-to-live (some number of seconds), permitting querying clients and servers to cache the records for an appropriate amount of time. The same caching policy applies to references to other DNS servers, allowing most queries to avoid loading the top of the hierarchy.
In spite of this caching strategy and centralized caches per-organization, the authors observed a relatively high query rate on the root servers of about seven queries per second (over all seven root servers; when only about twenty-five thousand hosts had names on the Internet), and overall poor performance due to wide-area network issues that would not be discovered in testing. Some of these issues were due to poor implementations. Some of the non-cached traffic was due to an initial lack of negative response caching.
A notable problem with DNS mentioned in the paper is one of misconfiguration. Administrators apparently did a very poor job of understanding or correctly setting TTLs, and the consequences of doing so were usually quite subtle.
With hindsight, it is clear that the paper's evaluation of DNS security was very pure. Though the authors mention the security concerns of resolvers blindly accepting records — albeit mostly from a misconfiguration scenario — they missed the chance to discover the poor use of additional answer sections that would cause major security problems later.
To achieve the distributed administrative control, DNS used an explicit hierarchy, which was to reflect the actual administrative hierarchy of the network. Each part of this hierarchy (a ‘zone’) is assigned to one or more DNS servers (each of which may be responsible for many distinct zones). Each DNS server returns a time-to-live (some number of seconds), permitting querying clients and servers to cache the records for an appropriate amount of time. The same caching policy applies to references to other DNS servers, allowing most queries to avoid loading the top of the hierarchy.
In spite of this caching strategy and centralized caches per-organization, the authors observed a relatively high query rate on the root servers of about seven queries per second (over all seven root servers; when only about twenty-five thousand hosts had names on the Internet), and overall poor performance due to wide-area network issues that would not be discovered in testing. Some of these issues were due to poor implementations. Some of the non-cached traffic was due to an initial lack of negative response caching.
A notable problem with DNS mentioned in the paper is one of misconfiguration. Administrators apparently did a very poor job of understanding or correctly setting TTLs, and the consequences of doing so were usually quite subtle.
With hindsight, it is clear that the paper's evaluation of DNS security was very pure. Though the authors mention the security concerns of resolvers blindly accepting records — albeit mostly from a misconfiguration scenario — they missed the chance to discover the poor use of additional answer sections that would cause major security problems later.
Monday, November 2, 2009
Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications
This paper describes the Chord DHT, a simulation-based evaluation of its load balancing and performance under churn, and a very small testbed evaluation of its latency across the wide-area network.
Chord maps its keys and nodes to conceptual ring, and uses the distance in one direction to route messages. A node is directly responsible for the keys between its address on the ring and the previous node's address and uses the following nodes as replicas for those keys. To guarantee routability to some node that thinks it is responsible for a key, each node has pointers to their current notion of their next or previous node. To provide fast routing in the common case, each node also keeps a pointer to nodes approximately 2^k units further around the ring for all k less than the key size.
Given these data structures to maintain, the paper presents algorithms for handling initialization of the finger table with relatively few messages and for maintaining the finger tables and replicas in the presence of failures. The paper provides some theoretical evidence these algorithms maintain good performance and availability in the presence of failures. The simulation evaluation gives good evidence that the algorithms can, in fact, maintain network connectivity in the presence of high failure rates, though they don't seem to show that that replicas would actually mitigate the impact of these failures in practice.
Chord is a very nice paper, but DHTs as envisioned in Chord have been relatively rare. Many distributed systems (especially lookup services which are relatively undemanding) are not actually large or unstable or decentralized enough to benefit from this sort of detailed handling of churn and scale, yielding approaches like the single-hop DHT (e.g. Dynamo, SEATTLE) and the replicated master (e.g. GFS).
Chord maps its keys and nodes to conceptual ring, and uses the distance in one direction to route messages. A node is directly responsible for the keys between its address on the ring and the previous node's address and uses the following nodes as replicas for those keys. To guarantee routability to some node that thinks it is responsible for a key, each node has pointers to their current notion of their next or previous node. To provide fast routing in the common case, each node also keeps a pointer to nodes approximately 2^k units further around the ring for all k less than the key size.
Given these data structures to maintain, the paper presents algorithms for handling initialization of the finger table with relatively few messages and for maintaining the finger tables and replicas in the presence of failures. The paper provides some theoretical evidence these algorithms maintain good performance and availability in the presence of failures. The simulation evaluation gives good evidence that the algorithms can, in fact, maintain network connectivity in the presence of high failure rates, though they don't seem to show that that replicas would actually mitigate the impact of these failures in practice.
Chord is a very nice paper, but DHTs as envisioned in Chord have been relatively rare. Many distributed systems (especially lookup services which are relatively undemanding) are not actually large or unstable or decentralized enough to benefit from this sort of detailed handling of churn and scale, yielding approaches like the single-hop DHT (e.g. Dynamo, SEATTLE) and the replicated master (e.g. GFS).
Looking Up Data in P2P Systems
This paper reviews peer-to-peer overlay networks from the perspective of how they approach the lookup problem (finding where to find data). It observes that there is a spectrum of actual implementations from centralized to hierarchical to symmetric. The paper focuses primarily on the symmetric sort, observing that they gain in resilience by not having any special nodes whose failures matter more than the failure of other nodes. (I find it curious that the actual variable performance availability of machines in P2P systems is not mentioned here.) Separate from the symmetric/hierarchical distinction the paper makes a distinction between structured and unstructured storage, where structured systems have "a well-defined set of information about other nodes". The authors only focus structured systems since the systems they consider unstructured prevent retrievability guarantees.
From these choices, the authors focus on DHTs, which are all symmetric, structured solutions to the distributed lookup problem. The paper describes several routing schemes (and their corresponding distance functions) and concludes with several practical issues that were apparently not well-solved on DHTs when the paper was written: such as assessing the impact of churn, handling malicious nodes, and providing more powerful primitives than lookup-by-key.
From these choices, the authors focus on DHTs, which are all symmetric, structured solutions to the distributed lookup problem. The paper describes several routing schemes (and their corresponding distance functions) and concludes with several practical issues that were apparently not well-solved on DHTs when the paper was written: such as assessing the impact of churn, handling malicious nodes, and providing more powerful primitives than lookup-by-key.
Subscribe to:
Posts (Atom)