(paper)
This paper is about a resource for teaching/learning about networks. The idea is to expose students to L1 and L2 technologies. It's also possible to use for research for cheaply and easily building networks.
Thursday, November 12, 2009
Tuesday, November 10, 2009
A Policy-aware Switching Layer for Data Centers
(paper)
Data centers try to route their traffic through middleboxes (firewalls, load balancers, NATs, etc). They typically do this by putting them in-line on the network topology and trying to ensure there are no other paths. Sometimes some network traffic doesn't need to go through a particular box but it will anyway because that's how they've set up the topology. This paper proposes a L2 way to accomplish this better; they call it "the policy-aware switching layer", aka PLayer. The properties they want are correctness (can't circumvent), flexibility, and efficiency. pswitches classify traffic and redirect it to the appropriate middlebox. Middleboxes do not need to be modified, but switches would need to be changed. There is a central policy server that sends policies to all the pswitches so they know how to classify and direct traffic.
They implemented prototype pswitches using Click, and then "validated" its functionality on the DETER testbed. They make the disclaimer about their work being a prototype which of course tips you off that their performance is bad: 40% of normal throughput with 2x the latency. Owch!!!
They then provide a formal analysis that I do not buy at all. I personally think that a formal analysis of a system like this is BS. They are just rephrasing what they have said earlier in the paper with subscripts.
Interesting paper but honestly they went into too much detail and lost my attention in places. This might be because this is a tech report. In a few places it seemed like they were unnecessarily belaboring obvious points that I didn't need convincing about.
Data centers try to route their traffic through middleboxes (firewalls, load balancers, NATs, etc). They typically do this by putting them in-line on the network topology and trying to ensure there are no other paths. Sometimes some network traffic doesn't need to go through a particular box but it will anyway because that's how they've set up the topology. This paper proposes a L2 way to accomplish this better; they call it "the policy-aware switching layer", aka PLayer. The properties they want are correctness (can't circumvent), flexibility, and efficiency. pswitches classify traffic and redirect it to the appropriate middlebox. Middleboxes do not need to be modified, but switches would need to be changed. There is a central policy server that sends policies to all the pswitches so they know how to classify and direct traffic.
They implemented prototype pswitches using Click, and then "validated" its functionality on the DETER testbed. They make the disclaimer about their work being a prototype which of course tips you off that their performance is bad: 40% of normal throughput with 2x the latency. Owch!!!
They then provide a formal analysis that I do not buy at all. I personally think that a formal analysis of a system like this is BS. They are just rephrasing what they have said earlier in the paper with subscripts.
Interesting paper but honestly they went into too much detail and lost my attention in places. This might be because this is a tech report. In a few places it seemed like they were unnecessarily belaboring obvious points that I didn't need convincing about.
Monday, November 9, 2009
Internet Indirection Infrastructure
The Internet is built to provide point-to-point, unicast service: the sender sends a packet to one addressee. IP routers in the middle will direct the packet to the addressee. This paper discusses how to support multicast, anycast, and host mobility: the sender doesn't necessarily know the identities and/or location of the receiving hosts. They propose an overlay network (Internet Indirection Infrastructure aka i3) to support these tasks.
i3 decouples sending & receiving. Sources send packets to an identifier, and receivers can ask for all packets sent to that identifier. So --- anytime something is sent to a given identifier, it is distributed to everyone who has registered for that identifier. They map each identifier to an i3 server; there's one node for each ID. When a packet is sent, it goes to that server; then that server distributes it to all hosts registered to that ID. This is useful for mobility because triggers just need to be updated with the new address; multicast can be done by all of the recipients registering for the trigger; and honestly I am not sure I follow their explanation of how to apply this to anycast. Public triggers could be used for public severs, and private triggers can be used for short-term flows.
-- If there's only one node for each ID, how does this work in case of failures? Isn't non-replicated "hard state" generally a bad idea? They later say that end-hosts use periodic refreshing...which makes it soft state...but then your outage time would be the same length as your refresh period. If you are not a fault-tolerant application, do you want to be refreshing every 50ms? OK...so then they try to mitigate this later in the paper by saying (1) an application can maintain a backup trigger or (2) the overlay network can automatically manage replicas.
The underlying overlay is responsible for robustness, scalability, efficiency, and stability. They use the Chord lookup protocol. One thing to note is that routing using i3 is less efficient than point-to-point addressing. They can alleviate this by having senders cache the i3 server's IP address. You can still run into the "triangle problem" where the i3 server ends up being farther away than the recipient nodes; they say this can be solved by having receivers choose i3 servers close to them. This could worsen scalability problems...seems like certain i3 nodes could easily end up overwhelmed. They suggest hot spots could be avoided by replicating the trigger at multiple nodes.
Potential security problems....
-- Eavesdropping: anyone who knows a trigger can eavesdrop. They suggest that private triggers should be randomly chosen & kept secret. Plus periodically change it. Not sure if eavesdropping is actually a huge concern given that most people assume eavesdropping on the network is possible in other ways.
-- Trigger hijacking: a malicious user that removes a public trigger. They suggest an extra level of indirection.
-- DoS attacks by making lots of triggers that point to a victim & amplify the sending of a single packet.
i3 decouples sending & receiving. Sources send packets to an identifier, and receivers can ask for all packets sent to that identifier. So --- anytime something is sent to a given identifier, it is distributed to everyone who has registered for that identifier. They map each identifier to an i3 server; there's one node for each ID. When a packet is sent, it goes to that server; then that server distributes it to all hosts registered to that ID. This is useful for mobility because triggers just need to be updated with the new address; multicast can be done by all of the recipients registering for the trigger; and honestly I am not sure I follow their explanation of how to apply this to anycast. Public triggers could be used for public severs, and private triggers can be used for short-term flows.
-- If there's only one node for each ID, how does this work in case of failures? Isn't non-replicated "hard state" generally a bad idea? They later say that end-hosts use periodic refreshing...which makes it soft state...but then your outage time would be the same length as your refresh period. If you are not a fault-tolerant application, do you want to be refreshing every 50ms? OK...so then they try to mitigate this later in the paper by saying (1) an application can maintain a backup trigger or (2) the overlay network can automatically manage replicas.
The underlying overlay is responsible for robustness, scalability, efficiency, and stability. They use the Chord lookup protocol. One thing to note is that routing using i3 is less efficient than point-to-point addressing. They can alleviate this by having senders cache the i3 server's IP address. You can still run into the "triangle problem" where the i3 server ends up being farther away than the recipient nodes; they say this can be solved by having receivers choose i3 servers close to them. This could worsen scalability problems...seems like certain i3 nodes could easily end up overwhelmed. They suggest hot spots could be avoided by replicating the trigger at multiple nodes.
Potential security problems....
-- Eavesdropping: anyone who knows a trigger can eavesdrop. They suggest that private triggers should be randomly chosen & kept secret. Plus periodically change it. Not sure if eavesdropping is actually a huge concern given that most people assume eavesdropping on the network is possible in other ways.
-- Trigger hijacking: a malicious user that removes a public trigger. They suggest an extra level of indirection.
-- DoS attacks by making lots of triggers that point to a victim & amplify the sending of a single packet.
Thursday, November 5, 2009
DNS Performance and the Effectiveness of Caching
[paper]
As mentioned in the previous paper, DNS servers aggressively cache address data. The previous paper also suggests that negative caching could give a performance boost. This paper questions and tests the effectiveness of both of these mechanisms using DNS and associated TCP traffic from MIT CSAIL and KAIST, circa 2000 and 2001.
Background: Many servers ("stub servers" or "stub resolvers") do nothing but cache responses and act as proxies for resolvers (they will query another server if they do not already have the data cached). (Stub servers answer "recursive queries", whereas authoritative servers receive "iterative queries.")
They collected outgoing DNS queries, incoming DNS responses, and TCP session start and end packets. Notably they cannot observe DNS lookups cached inside their network (eg on the client itself). They removed all TCP sessions that didn't first generate a TCP lookup; I assume this removes the effect of client-cached addresses. They also removed all DNS A-record lookups not part of a TCP session; I don't understand why not or how this skews their findings, and this bothers me.
Their results:
-- About 80% of DNS lookups don't require a referral; this means the first NS contacted has the answer.
-- Total number of DNS queries is much higher than DNS lookups, meaning that many lookups require query retransmission. Despite retransmissions, about 20% of clients never got any answer (not even an error). They suggest that it is better to give up sooner than to keep retransmitting, and let the application figure out what else to do. Between 12-19% of their lookups did not have any retransmissions. Aggressive retransmissions can cause a lot of traffic -- 63% of all DNS queries they saw were for lookups that never received a response!
-- 13% of client lookups result in errors (most say the name does not exist).
-- Distribution of both successful and failed DNS requests are heavy-tailed. For one set of traces, 10% of names account for 68% of answers but then the remaining 32% are very distributed.
-- They do believe that NS record caching is important. Only 20% of responses came from a root server, which means that if TTLs on NS records were shorter, the root server load would increase by 5x.
Fact to remember: Address (A) records store IP addresses, and NS records say what name server is responsible for an IP address
---------------
Class Notes:
-- Top sites accessed a lot, but low TTL; then many sites accessed infrequently. Reminds me of the 80:20 rule.
-- Key point is to stop with aggressive retransmissions -- if multiple attempts get no response, give up because it's not helping.
As mentioned in the previous paper, DNS servers aggressively cache address data. The previous paper also suggests that negative caching could give a performance boost. This paper questions and tests the effectiveness of both of these mechanisms using DNS and associated TCP traffic from MIT CSAIL and KAIST, circa 2000 and 2001.
Background: Many servers ("stub servers" or "stub resolvers") do nothing but cache responses and act as proxies for resolvers (they will query another server if they do not already have the data cached). (Stub servers answer "recursive queries", whereas authoritative servers receive "iterative queries.")
They collected outgoing DNS queries, incoming DNS responses, and TCP session start and end packets. Notably they cannot observe DNS lookups cached inside their network (eg on the client itself). They removed all TCP sessions that didn't first generate a TCP lookup; I assume this removes the effect of client-cached addresses. They also removed all DNS A-record lookups not part of a TCP session; I don't understand why not or how this skews their findings, and this bothers me.
Their results:
-- About 80% of DNS lookups don't require a referral; this means the first NS contacted has the answer.
-- Total number of DNS queries is much higher than DNS lookups, meaning that many lookups require query retransmission. Despite retransmissions, about 20% of clients never got any answer (not even an error). They suggest that it is better to give up sooner than to keep retransmitting, and let the application figure out what else to do. Between 12-19% of their lookups did not have any retransmissions. Aggressive retransmissions can cause a lot of traffic -- 63% of all DNS queries they saw were for lookups that never received a response!
-- 13% of client lookups result in errors (most say the name does not exist).
-- Distribution of both successful and failed DNS requests are heavy-tailed. For one set of traces, 10% of names account for 68% of answers but then the remaining 32% are very distributed.
-- They do believe that NS record caching is important. Only 20% of responses came from a root server, which means that if TTLs on NS records were shorter, the root server load would increase by 5x.
Fact to remember: Address (A) records store IP addresses, and NS records say what name server is responsible for an IP address
---------------
Class Notes:
-- Top sites accessed a lot, but low TTL; then many sites accessed infrequently. Reminds me of the 80:20 rule.
-- Key point is to stop with aggressive retransmissions -- if multiple attempts get no response, give up because it's not helping.
Development of the Domain Name System
[paper]
This paper tells the story of the invention of DNS. Prior to DNS, every host had a plain text file named HOSTS.TXT that contained addressing information for all places they might want to reach. Clearly this was not scalable.
DNS has two components: name servers and resolvers. Name servers hold the addressing information & answer queries, and resolvers find name servers. Data for each DNS name is a "resource record" (RR) that carries a type, class field, and data. There are two mechanisms for transferring data from source to destination: zones and caching. A zone is a section of the tree controlled, updated, and maintained by a single organization. Resolvers (which can be centrally located or on a host itself) cache responses for each zone for as long as the TTL for that zone. A resolver is configured to point at servers for the root node and the top of the local domain. It then searches "downwards."
Surprises they encountered when DNS use became widespread:
-- Refinemenet of semantics. The form of data specification ended up confusing, eg how to order multiple IP addresses for a single host.
-- Performance. Initial performance was much worse than they expected. Root servers would get multiple copies of the same query from the same source because their responses were slower than resend timers. Measuring DNS performance precisely, however, proved problematic because of gateway changes, software releases, etc.
-- Negative caching. DNS can respond negatively to a query in 2 ways: name does not exist, or name exists but they don't have data for it. They expected negative responses to be rare but they ended up being extremely popular (20-60% of all queries) because of transition confusion (use of old addresses and shortcuts, etc). They expected it would drop off but it actually stayed between 15-50%. This is because a user would type one bad address and then their application would automatically try other potential addresses, in the process making a bunch of negative queries. They suggest that negative queries should be cached like positive queries to address this issue. I'm not sure what kind of a TTL should be put on negative query caches; perhaps there could be a force update command that would clear a negative query cache when that domain name got registered.
Their successes:
-- variable depth hierarchy
-- organizational structuring of names
-- datagram access
-- caching proved crucial!!
Shortcomings:
-- type & class growth -- either demand for new types & classes was misunderstood, or DNS makes new definitions too hard
-- upgrading from HOSTS.TXT -> DNS was hard, but seems like that isn't a long-term issue
-- distribution of control
I like this paper a lot, especially the "surprises" section. The negative caching is really interesting, I would never have guessed that.
Related paper that might be interesting: Protecting Browsers from DNS Rebinding Attacks. This paper is interesting, but I've never fully understood how it works. The basic idea is that Attacker.com wants to try to gain access to an internal resource (eg iternal.corporate.com). The attacker answers DNS queries for attacker.com with a really short TTL. After the user navigates correctly to attacker.com, the attacker then starts answering DNS queries for attacker.com with the IP address for internal.corporate.com (eg 10.10.10.105). A script on the loaded attacker.com website will issue a request for materials at attacker.com; this will then actually point to 10.10.10.105 and the attacker will successfully get the content. (Normally this operation should be denied, because attacker.com and internal.corporate.com are not the same domain.) The part I am confused about here is the administration of DNS. Why can any arbitrary person claim that any random IP address belongs to their domain name?
---------------
Class notes:
-- DNS is eventually consistent
-- Caching: scalability, reliability in outages, speed up flookup
-- Caching done in client resolution software + also in name servers
This paper tells the story of the invention of DNS. Prior to DNS, every host had a plain text file named HOSTS.TXT that contained addressing information for all places they might want to reach. Clearly this was not scalable.
DNS has two components: name servers and resolvers. Name servers hold the addressing information & answer queries, and resolvers find name servers. Data for each DNS name is a "resource record" (RR) that carries a type, class field, and data. There are two mechanisms for transferring data from source to destination: zones and caching. A zone is a section of the tree controlled, updated, and maintained by a single organization. Resolvers (which can be centrally located or on a host itself) cache responses for each zone for as long as the TTL for that zone. A resolver is configured to point at servers for the root node and the top of the local domain. It then searches "downwards."
Surprises they encountered when DNS use became widespread:
-- Refinemenet of semantics. The form of data specification ended up confusing, eg how to order multiple IP addresses for a single host.
-- Performance. Initial performance was much worse than they expected. Root servers would get multiple copies of the same query from the same source because their responses were slower than resend timers. Measuring DNS performance precisely, however, proved problematic because of gateway changes, software releases, etc.
-- Negative caching. DNS can respond negatively to a query in 2 ways: name does not exist, or name exists but they don't have data for it. They expected negative responses to be rare but they ended up being extremely popular (20-60% of all queries) because of transition confusion (use of old addresses and shortcuts, etc). They expected it would drop off but it actually stayed between 15-50%. This is because a user would type one bad address and then their application would automatically try other potential addresses, in the process making a bunch of negative queries. They suggest that negative queries should be cached like positive queries to address this issue. I'm not sure what kind of a TTL should be put on negative query caches; perhaps there could be a force update command that would clear a negative query cache when that domain name got registered.
Their successes:
-- variable depth hierarchy
-- organizational structuring of names
-- datagram access
-- caching proved crucial!!
Shortcomings:
-- type & class growth -- either demand for new types & classes was misunderstood, or DNS makes new definitions too hard
-- upgrading from HOSTS.TXT -> DNS was hard, but seems like that isn't a long-term issue
-- distribution of control
I like this paper a lot, especially the "surprises" section. The negative caching is really interesting, I would never have guessed that.
Related paper that might be interesting: Protecting Browsers from DNS Rebinding Attacks. This paper is interesting, but I've never fully understood how it works. The basic idea is that Attacker.com wants to try to gain access to an internal resource (eg iternal.corporate.com). The attacker answers DNS queries for attacker.com with a really short TTL. After the user navigates correctly to attacker.com, the attacker then starts answering DNS queries for attacker.com with the IP address for internal.corporate.com (eg 10.10.10.105). A script on the loaded attacker.com website will issue a request for materials at attacker.com; this will then actually point to 10.10.10.105 and the attacker will successfully get the content. (Normally this operation should be denied, because attacker.com and internal.corporate.com are not the same domain.) The part I am confused about here is the administration of DNS. Why can any arbitrary person claim that any random IP address belongs to their domain name?
---------------
Class notes:
-- DNS is eventually consistent
-- Caching: scalability, reliability in outages, speed up flookup
-- Caching done in client resolution software + also in name servers
Wednesday, November 4, 2009
Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications
[paper]
This paper presents Chord, a distributed lookup protocol. (Their routing algorithm was described as "skiplist-like routing" by the previous paper.) They use "consistent hashing" to assign IDs to nodes, in an attempt to load balance key assignments over nodes. One of their goals is scalability: each node should only need to know about a small number of other nodes. Also, they need to handle nodes leaving and entering the network without complete degradation of performance.
Each key has a "successor node", which is the node whose ID is equal to or most closely follows the key's ID. When a node joins the network, keys previously assigned to other nodes now become assigned to n if the new node's ID is closer to theirs. When a node leaves the network, its keys are reassigned to the next closest. Nodes maintain the ID of the next successor as well as a routing table that helps find a node closer to the key during a lookup propagation operation.
This paper presents Chord, a distributed lookup protocol. (Their routing algorithm was described as "skiplist-like routing" by the previous paper.) They use "consistent hashing" to assign IDs to nodes, in an attempt to load balance key assignments over nodes. One of their goals is scalability: each node should only need to know about a small number of other nodes. Also, they need to handle nodes leaving and entering the network without complete degradation of performance.
Each key has a "successor node", which is the node whose ID is equal to or most closely follows the key's ID. When a node joins the network, keys previously assigned to other nodes now become assigned to n if the new node's ID is closer to theirs. When a node leaves the network, its keys are reassigned to the next closest. Nodes maintain the ID of the next successor as well as a routing table that helps find a node closer to the key during a lookup propagation operation.
Looking Up Data in P2P Systems
P2P networks raise the "lookup problem": how can you locate data on the P2P network without a centralized server or hierarchy? Simplest form of lookup: searcher broadcasts a message to all neighbors with a request for X. Each neighbor checks its local database; if it doesn't have the item, it forwards to its neighbors, and repeat. However, all these broadcast messages will take up a lot of bandwidth.
Distributed hash tables (DHTs) offer a solution. In a DHT, all keys & nodes haves IDs. Each key is stored at a node with an ID that's "close" to the ID's key. Each node sends a lookup request to another node "closer" in the ID space until the lookup request gets to the right place. However, nodes need a routing algorithm to be able to *find* a closer node.
-- Skiplist-like routing: Each node has a table of node IP & ID pairs of nodes whose IDs are 1/2 around the ID space, 1/4 around, 1/8 around, etc. A searcher node will send a lookup request to the node with the closest ID that does not exceed the key ID.
-- Tree-like routing: Each node has a randomly assigned ID, and each one knows a node with a certain "prefix". It uses knowledge of the tree structure to find nodes.
-- Multi-dimensional routing: Not sure I quite follow this. D-dimensional Cartesian coordinate space partitioned into hyper-rectangles (zones), and each node has a zone & identified by the boundaries of its zone. A key gets a point in the d-dimensional space and is stored in the node that owns the key's point's zone. The lookup follows the straight line path from the searcher to the key.
I found this paper interesting because I've been wondering for a while how DHTs work, and this is a review of what seem like important topics for understanding anything about DHTs in more detail. I really like that this paper was on the reading list.
Distributed hash tables (DHTs) offer a solution. In a DHT, all keys & nodes haves IDs. Each key is stored at a node with an ID that's "close" to the ID's key. Each node sends a lookup request to another node "closer" in the ID space until the lookup request gets to the right place. However, nodes need a routing algorithm to be able to *find* a closer node.
-- Skiplist-like routing: Each node has a table of node IP & ID pairs of nodes whose IDs are 1/2 around the ID space, 1/4 around, 1/8 around, etc. A searcher node will send a lookup request to the node with the closest ID that does not exceed the key ID.
-- Tree-like routing: Each node has a randomly assigned ID, and each one knows a node with a certain "prefix". It uses knowledge of the tree structure to find nodes.
-- Multi-dimensional routing: Not sure I quite follow this. D-dimensional Cartesian coordinate space partitioned into hyper-rectangles (zones), and each node has a zone & identified by the boundaries of its zone. A key gets a point in the d-dimensional space and is stored in the node that owns the key's point's zone. The lookup follows the straight line path from the searcher to the key.
I found this paper interesting because I've been wondering for a while how DHTs work, and this is a review of what seem like important topics for understanding anything about DHTs in more detail. I really like that this paper was on the reading list.
Subscribe to:
Posts (Atom)