This paper describes BotGraph, a system to detect Web-account abuse traffic generated by bots. It attempts to determine the botnet on the collective scale, not determining individual nodes, by taking advantage of similarities in configuration among nodes in a botnet. Detecting this abuse consists of detecting aggressive signups and logins.
Detecting botnet signups is based on spikes of signups from a given IP address. Locating all bots in a bot-user group is done through use of a graph with users as vertices and weighted edges between them showing their activity similiarity. This paper uses a DryadLINQ-based system to process large amounts of data in parallel for these user-user graphs. A nice thing about this paper is that if the botnets adaptively limit their signups or e-mails sent per bot, even if the graph doesn't pick them up as being bots, their activities will have been sufficiently scaled back that they don't pose nearly the problem they did previously.
Showing posts with label networking. Show all posts
Showing posts with label networking. Show all posts
Wednesday, December 9, 2009
Sunday, December 6, 2009
Not-a-Bot: Improving Service Availability in the Face of Botnet Attacks; Gummadi, Balakrishnan, Maniatis, & Ratnasamy
Botnets are responsible for a large portion of all undesirable web traffic, such as spam, DDoS attacks, and click-fraud, which can be reduced with effective schemes to correctly classify traffic as human-generated or bot-generated. However, these schemes must not trust potentially-infected hosts and must be as transparent as possible to users. This paper describes Not-a-Bot (NAB), a human-activity attester that requires both a Trusted Platform Module chip and a verifier module implemented in the Xen hypervisor at any server wishing to use it. NAB attempts to reduce bot-generated traffic while not affecting human-generated traffic.
An interaction is attested to be human-generated based on how closely recent activity from the keyboard and mouse ports matches the potential web traffic. If matching recent activity cannot be found, an alert is issued that the activity could not be attested. Bots could replicate this user behavior in their messages to be sent, but NAB rate-limits this activity by requiring application-specific time between attestations. The TPM on a host then signs and sends the request on, where it can be checked at the destination verifier.
The authors evaluate their scheme on actual traces of several hundred users, as well as malware traces and spam messages. They found that NAB does very well in suppressing spam, DDoS attempts, and click-fraud by around 90%, and it didn't deny any human-generated traffic.
In reading about the scenarios in which NAB is actually applied, I wondered how many average e-mail users would actually want to deploy NAB. The authors then addressed this question by saying that e-mail users would benefit from having all their mail correctly classified. However, I personally don't feel that I'm largely affected by mis-classification of my e-mails, so I still have a hard time accepting that NAB could catch on widely. The DDoS scenario is less effective in justifying use of NAB, particularly since some legitimate web requests could be machine-generated. As for detecting click-fraud, any company getting ad revenue could make use of NAB, but the benefits for users is low; I particularly disliked the idea of having an attester bundled with installed toolbars.
An interaction is attested to be human-generated based on how closely recent activity from the keyboard and mouse ports matches the potential web traffic. If matching recent activity cannot be found, an alert is issued that the activity could not be attested. Bots could replicate this user behavior in their messages to be sent, but NAB rate-limits this activity by requiring application-specific time between attestations. The TPM on a host then signs and sends the request on, where it can be checked at the destination verifier.
The authors evaluate their scheme on actual traces of several hundred users, as well as malware traces and spam messages. They found that NAB does very well in suppressing spam, DDoS attempts, and click-fraud by around 90%, and it didn't deny any human-generated traffic.
In reading about the scenarios in which NAB is actually applied, I wondered how many average e-mail users would actually want to deploy NAB. The authors then addressed this question by saying that e-mail users would benefit from having all their mail correctly classified. However, I personally don't feel that I'm largely affected by mis-classification of my e-mails, so I still have a hard time accepting that NAB could catch on widely. The DDoS scenario is less effective in justifying use of NAB, particularly since some legitimate web requests could be machine-generated. As for detecting click-fraud, any company getting ad revenue could make use of NAB, but the benefits for users is low; I particularly disliked the idea of having an attester bundled with installed toolbars.
Friday, November 20, 2009
Skilled in the Art of Being Idle: Reducing Energy Waste in Networked Systems; Nedevschi, Chandrashekar, Liu, Nordman, Ratnasamy, & Taft
This paper examines the energy wasted by computers not taking advantage of idle times to go into lower power sleep modes. The authors straight out acknowledge that this problem of when and how to effectively put nodes to sleep without them losing their network presence has been examined, with wake-on-LAN and proxying as potential solutions.
Based on traces from actual users, they justify the need for these solutions by showing that the studied computers actually do spend a lot of time in idle and that in many cases, long gaps of time pass between packet arrivals at the idle machine. Not suprisingly, the machines tend to have more frequently arriving packets in the office setting than in the home setting, with some users having even more available idle time than others.
I like this paper because it breaks down the type of network traffic seen in both the home and office settings; it starts out breaking both the incoming and outing packets into unicast, multicast, and broadcast groupings, and then further examines the breakdown of the multicast and broadcast packets into such things as ARP, IGMP, etc. These breakdowns are important because the power savings possible due to proxying for a node are dependent on which packets a node does not actually need to be woken up for.
Protocols are classified into groupings such as "don't-ignore" (ARP or DHCP requests for the sleeping node), "don't wake", ignorable, and mechanical response that the proxy can respond to. With these classifications in mind, the authors present 4 proxy schemes that offer varying levels of power savings, with the tradeoff that less application state is maintained. They find that their more aggressive schemes offer a lot of power savings, particularly in the office environment, and create a prototype of their proxy architecture in Click.
Based on traces from actual users, they justify the need for these solutions by showing that the studied computers actually do spend a lot of time in idle and that in many cases, long gaps of time pass between packet arrivals at the idle machine. Not suprisingly, the machines tend to have more frequently arriving packets in the office setting than in the home setting, with some users having even more available idle time than others.
I like this paper because it breaks down the type of network traffic seen in both the home and office settings; it starts out breaking both the incoming and outing packets into unicast, multicast, and broadcast groupings, and then further examines the breakdown of the multicast and broadcast packets into such things as ARP, IGMP, etc. These breakdowns are important because the power savings possible due to proxying for a node are dependent on which packets a node does not actually need to be woken up for.
Protocols are classified into groupings such as "don't-ignore" (ARP or DHCP requests for the sleeping node), "don't wake", ignorable, and mechanical response that the proxy can respond to. With these classifications in mind, the authors present 4 proxy schemes that offer varying levels of power savings, with the tradeoff that less application state is maintained. They find that their more aggressive schemes offer a lot of power savings, particularly in the office environment, and create a prototype of their proxy architecture in Click.
Cutting the Electric Bill for Internet-Scale Systems; Qureshi, Weber, Balakrishnan, Guttag, & Maggs
This paper discusses reducing energy costs of operating a data center. This technique relies on temporal and spatial fluctuations in electricity costs as well as use of dynamic request routing across widely distributed machines. The notion of energy elasticity determines how much money can actually be saved by changing the load on a machine; machines with greater energy proportionality can save more money when they're less used than those machines that continue to burn lots of power when idle.
The authors choose to focus on real-time electricity pricing instead of future, predicted markets, though RT makes up about 10% of the market share. Routing to different geographic areas to obtain the best price relies on low correlation between hourly prices in different regions, which appears to be the case between different Regional Transmission Organizations (RTOs). Part of the difference in cost between two locations at once is the fact that different time zones reach their peak cost at non-peak hours in other locations.
An inherent tradeoff in cutting cost of electricity by routing it elsewhere geographically is an increase in bandwidth costs, which the authors accounted for in part of their study. They did find that this cut the amount of energy costs that could be saved, but they still managed to cut total operating costs. Further reductions could be made through enrolling in demand reduction programs, but that would require delay-insensitive workloads within the data center, and it's not obvious whether that tradeoff would end up being monetarily beneficial.
Regardless of the assumptions the authors must make to simulate their ideas, I think the idea of geographic routing based on hourly electricity costs is a great idea (to the extent that performance doesn't suffer greatly), particularly if the work might be moved around anyway due to node failure or data placement.
The authors choose to focus on real-time electricity pricing instead of future, predicted markets, though RT makes up about 10% of the market share. Routing to different geographic areas to obtain the best price relies on low correlation between hourly prices in different regions, which appears to be the case between different Regional Transmission Organizations (RTOs). Part of the difference in cost between two locations at once is the fact that different time zones reach their peak cost at non-peak hours in other locations.
An inherent tradeoff in cutting cost of electricity by routing it elsewhere geographically is an increase in bandwidth costs, which the authors accounted for in part of their study. They did find that this cut the amount of energy costs that could be saved, but they still managed to cut total operating costs. Further reductions could be made through enrolling in demand reduction programs, but that would require delay-insensitive workloads within the data center, and it's not obvious whether that tradeoff would end up being monetarily beneficial.
Regardless of the assumptions the authors must make to simulate their ideas, I think the idea of geographic routing based on hourly electricity costs is a great idea (to the extent that performance doesn't suffer greatly), particularly if the work might be moved around anyway due to node failure or data placement.
Thursday, November 19, 2009
Scalable Application Layer Multicast; Banerjee, Bhattacharjee, & Kommareddy
This paper describes the NICE (NICE is the Internet Cooperative Environment) multicast protocol. Like SRM, NICE is implemented at the application layer so as not to require changes to the underlying network. NICE uses hierarchical layers to group nodes into clusters and in doing so, reduce stretch, or unnecessarily increased path length from the unicast path.
When new hosts attempt to join, they first communicate with a Rendezvous Point (RP) node, which then directs them to high-tiered nodes, which subsequently direct the host to lower-level nodes close to them. Higher-level nodes are cluster leaders, responsible for keeping the size of their associated cluster between a certain threshold and splitting or merging the cluster group when the max or min threshold is passed. Members of a cluster alert each other to their presence throughput periodic heartbeat messages.
The authors simulate NICE and compare their results to Narada, an existing multicast protocol. They find that it performs comparably, but with less control overhead and less stress (total messages sent over a link) on links. The hierarachical structure of NICE seems to be the main reason that it has such low control overhead and hence can be used (at least in simulation) for groups of large sizes, say, greater than 1024 hosts, which Narada cannot do. The paper references another paper about Narada, but I wished they would have given a succint, organized comparison of the two protocols.
This paper went much more into detail about the underlying workings of the multicast groups, while the other paper offered a more concrete example of when this multicast framework would be used and how to detect and deal with losses.
When new hosts attempt to join, they first communicate with a Rendezvous Point (RP) node, which then directs them to high-tiered nodes, which subsequently direct the host to lower-level nodes close to them. Higher-level nodes are cluster leaders, responsible for keeping the size of their associated cluster between a certain threshold and splitting or merging the cluster group when the max or min threshold is passed. Members of a cluster alert each other to their presence throughput periodic heartbeat messages.
The authors simulate NICE and compare their results to Narada, an existing multicast protocol. They find that it performs comparably, but with less control overhead and less stress (total messages sent over a link) on links. The hierarachical structure of NICE seems to be the main reason that it has such low control overhead and hence can be used (at least in simulation) for groups of large sizes, say, greater than 1024 hosts, which Narada cannot do. The paper references another paper about Narada, but I wished they would have given a succint, organized comparison of the two protocols.
This paper went much more into detail about the underlying workings of the multicast groups, while the other paper offered a more concrete example of when this multicast framework would be used and how to detect and deal with losses.
A Reliable Multicast Framework for Light-weight Sessions and Application Level Framing; Floyd, Jacobson, McCanne, Liu, & Zhang
This paper discusses scalable reliable multicast (SRM). It starts off by presenting the problems of blindly scaling unicast to multicast. Reliable delivery becomes a very difficult problem to tackle when there are multiple receivers and a layer of indirection involved. Interestingly, the authors advocate the use of Application Data Units (ADU) which is a method more closely tied to an application for requesting pieces of data.
The authors then go on to describe wb, an application that uses reliable multicast, and the design decisions that accompany it. Particular to wb are that all senders and receivers are part of the same multicast group without regard to roles, and delivery order of packets does not matter to the application. With the latter fact in mind, it seems odd that they should choose this as their example application, since part of the difficulty in multicast comes in with ordering packets correctly. To detect gaps due to losses without causing a response implosion on the sender side, receivers send periodic messages about which sequence numbers they have seen; they work together to send and respond to repair requests after first waiting some random timeout.
The paper gives the expected number of requests and timer delays for a few topologies: chain, star, and bounded-degree trees, and then shows some simulation results for these topologies. One realism missing from the simulations was the possibility of dropping repairs and repairs requests and thus requiring retransmissions of retransmissions. I hated the simulation result graphs. They weren't labeled at all, so I had to jump back and forth to the text a few times to figure out what everything was.
The authors then go on to describe wb, an application that uses reliable multicast, and the design decisions that accompany it. Particular to wb are that all senders and receivers are part of the same multicast group without regard to roles, and delivery order of packets does not matter to the application. With the latter fact in mind, it seems odd that they should choose this as their example application, since part of the difficulty in multicast comes in with ordering packets correctly. To detect gaps due to losses without causing a response implosion on the sender side, receivers send periodic messages about which sequence numbers they have seen; they work together to send and respond to repair requests after first waiting some random timeout.
The paper gives the expected number of requests and timer delays for a few topologies: chain, star, and bounded-degree trees, and then shows some simulation results for these topologies. One realism missing from the simulations was the possibility of dropping repairs and repairs requests and thus requiring retransmissions of retransmissions. I hated the simulation result graphs. They weren't labeled at all, so I had to jump back and forth to the text a few times to figure out what everything was.
Thursday, November 12, 2009
X-Trace: A Pervasive Network Tracing Framework; Fonseca, Porter, Katz, Shenker, & Stoica
This paper discusses X-Trace, a network diagnostic tool that works across a range of domains and applications by adding metadata to all network operations that originate from certain tasks. By keeping track of which tasks spawn new tasks, X-Trace ends up keeping track of task trees, whose steps it can replay to troubleshoot failures. Nodes push IDs to their next hop and establish these task trees through pushDown and pushNext, functions for lower and same layer hops, respectively.
X-Traces design was driven by 3 core ideas: trace requests should be sent in-band, collected traces should be sent out-of-band, and originators and receivers of requests should be decoupled. These principles have good reasons behind them, namely that trace requests need to be able to follow the same path as the original flow, that cted data should avoid the troublesome spots that it will help diagnose, and that administrative domains (ADs) that are unwilling to disclose some of their information need not fear this tool doing just that.
A few scenarios for using X-Trace are described including how traces could pinpoint problems; these scenarios include web site requests from an Apache server, web hosting services for photos, the i3 overlay network, tunneling, and troubleshooting ISP connections. A big open issue for X-Trace is security, for its metadata and for generating reports. I liked how frankly the authors acknowledged problems with X-Trace, that is, how difficult it was to deploy and how easy adoption/retrofitting of it would be.
NetFPGA: A Network Tool for Research and Education; Watson, McKeown, & Casado
This short paper describes the NetFPGA system, an FPGA-based platform originally created as a teaching tool to give students experience with network physical and link layers. It is currently in version 2, the main difference from version 1 being its format, using PCI and requiring no specialized backplanes or rack.
NetFPGA sounds like a great tool for people who want practical experience in developing networking hardware but cannot due to cost and complexity of such activities; networking researchers now needn't rely solely on software routing for their implementations. I don't know what their current status of running software on the actual boards is; apparently the software part of the routers was not initially run on the boards and required some outside computer, which is unfortunate.
NetFPGA sounds like a great tool for people who want practical experience in developing networking hardware but cannot due to cost and complexity of such activities; networking researchers now needn't rely solely on software routing for their implementations. I don't know what their current status of running software on the actual boards is; apparently the software part of the routers was not initially run on the boards and required some outside computer, which is unfortunate.
Tuesday, November 10, 2009
A Policy-aware Switching Layer for Data Centers; Joseph, Tavakoli, & Stoica
This paper describes PLayer, a policy-aware switching layer for data centers. PLayer is meant to help combat the problems posed by middleboxes (e.g. firewalls) and having equivalent logical and physical network topologies. With middleboxes that are hard-wired into the physical network, any rerouting of traffic due to server failures could bypass the middlebox, meaning that behavior is not reliable.
PLayer separates the notions of policy from reachability, meaning that traffic goes through middleboxes as expected by data center policy, not just as network mechanisms allow. Additionally, middleboxes are taken off the physical network data path, with traffic forwarded to them via a policy-aware pswitch. Pswitches contain switch and policy cores; as the authors point out, minimal hardware change is required for PLayer to actually be adopted in data centers.
However, it's not clear from the paper how these switches would be acquired, if DC owners would have to hack their own together. The authors themselves developed a software implementation of the pswitches using Click. They simulated use of the pswitches on a small collection of topologies and found through the use of simple micro-benchmarks that their software prototype incurred an increase in latency and decrease in throughput. Despite this degrading performance, use of pswitches offers guarantees that middleboxes will be traversed as desired even in the presence of network churn.
PLayer separates the notions of policy from reachability, meaning that traffic goes through middleboxes as expected by data center policy, not just as network mechanisms allow. Additionally, middleboxes are taken off the physical network data path, with traffic forwarded to them via a policy-aware pswitch. Pswitches contain switch and policy cores; as the authors point out, minimal hardware change is required for PLayer to actually be adopted in data centers.
However, it's not clear from the paper how these switches would be acquired, if DC owners would have to hack their own together. The authors themselves developed a software implementation of the pswitches using Click. They simulated use of the pswitches on a small collection of topologies and found through the use of simple micro-benchmarks that their software prototype incurred an increase in latency and decrease in throughput. Despite this degrading performance, use of pswitches offers guarantees that middleboxes will be traversed as desired even in the presence of network churn.
Internet Indirection Infrastructure; Stoica, Adkins, Zhuang, Shenker, & Surana
This paper discusses i3 (Internet Indirection Infrastructure), an overlay network that provides indirection through decoupling of sending and receiving to allow flexible support for anycast, mobility, and other services. i3 uses rendezvous-style communication; receiving nodes insert triggers onto specified servers that consist of a packet id of interest and an IP address to which these packets should be forwarded. Thus, receivers and senders may remain blissfully unaware of how many of the other there are.
Mobility is supported by having receiving nodes simply update their triggers when their addresses change. Multicast involves all group members setting up triggers for an i3 id. To allow intermediate steps like HTML->WML mapping, id chains can be created, and large-scale multicast can be accomodated by hierarchical triggers.
i3 is implemented and simulated using Chord. Some measurements of note include the per-packet fowarding and routing overhead; forwarding overhead seems to add between 10-40 us. While i3 allows flexible implementation of a number of services with fairly low overhead, it has some issues with security. One in particular that stands out is that any user can insert or remove a trigger for any receiver from an i3 node, which seems like a big flaw fixable only through more indirection or verification.
Mobility is supported by having receiving nodes simply update their triggers when their addresses change. Multicast involves all group members setting up triggers for an i3 id. To allow intermediate steps like HTML->WML mapping, id chains can be created, and large-scale multicast can be accomodated by hierarchical triggers.
i3 is implemented and simulated using Chord. Some measurements of note include the per-packet fowarding and routing overhead; forwarding overhead seems to add between 10-40 us. While i3 allows flexible implementation of a number of services with fairly low overhead, it has some issues with security. One in particular that stands out is that any user can insert or remove a trigger for any receiver from an i3 node, which seems like a big flaw fixable only through more indirection or verification.
Thursday, November 5, 2009
DNS Performance and the Effectiveness of Caching; Jung, Sit, Balakrishnan, & Morris
This paper presents findings about DNS regarding its performance and effectiveness of caching. Studying traces from MIT and KAIST, the authors show the breakdown of DNS query types; they found that around 60% were name-to-address queries, with another 25-30% being reverse address-to-name queries. However, they say they excluded DNS lookups not associated with TCP connections from these statistics and then revealed that 50% of MIT lookups fall into this category. How much does this class of lookups change their results?
It sounds like a lot of DNS traffic is somewhat gratuitous, for example with systems doing reverse lookups and then verifying that result by doing an A lookup on it. Surprisingly, nearly 1/4th of all DNS lookups go unanswered, with at least another 10% receiving a negative answer. The authors also chart latency of lookups based on number of referrals in the process. Not surprisingly, 2 or more referrals can cause a a tenfold increase in latency. Also not surprising is that caching can bring this latency down significantly, as well as easing the load at the root servers.
The authors further study caching through a trace-based simulation which looks at cached IP address hits. They find that a small number of names are very frequently accessed, allowing cache rates for small size caches to be high, and that increasing TTL increases cache hits only to a certain degree, as web pages with a given name are often accessed in small, successive bursts. I liked this paper because it actually took a look at what all those DNS lookups are running around the net doing.
It sounds like a lot of DNS traffic is somewhat gratuitous, for example with systems doing reverse lookups and then verifying that result by doing an A lookup on it. Surprisingly, nearly 1/4th of all DNS lookups go unanswered, with at least another 10% receiving a negative answer. The authors also chart latency of lookups based on number of referrals in the process. Not surprisingly, 2 or more referrals can cause a a tenfold increase in latency. Also not surprising is that caching can bring this latency down significantly, as well as easing the load at the root servers.
The authors further study caching through a trace-based simulation which looks at cached IP address hits. They find that a small number of names are very frequently accessed, allowing cache rates for small size caches to be high, and that increasing TTL increases cache hits only to a certain degree, as web pages with a given name are often accessed in small, successive bursts. I liked this paper because it actually took a look at what all those DNS lookups are running around the net doing.
Development of the Domain Name System; Mockapetris & Dunlap
This paper describes the initial goals behind the creation of the Domain Name System, or DNS. Originally, mappings of host names to addresses was maintained in one single centrally-located HOSTS.TXT file. Understandably, this approach became unwieldy and needed to be distributed somehow.
The new DNS approach was designed to adhere to the following constraints: provide the same information as HOSTS.TXT, allow distributed management, and flexibly interoperate across environments including the DARPA Internet, all while providing "tolerable" performance and imposing few limits on size of names or other components associated with it.
DNS requires the use of name servers, which store information and answer queries, and resolvers, which interact with client programs to find the right name server to connect to. Resolvers can choose to cache query responses. DNS has an internal name space in the form labels concatenated together from a variable-depth tree, allowing organizations flexibility to organize themselves and expand internally.
I found it amusing to hear that the Berkeley community was somewhat resistant to the change to DNS. As this paper was written over 20 years ago, I wonder if HOSTS.TXT is still used by many systems; I know I personally use a hosts mapping file in Linux to build shortcuts on top of DNS, but to be at all usable, HOSTS.TXT really needs to be an extra layer in addition to DNS to handle special cases at local levels.
The new DNS approach was designed to adhere to the following constraints: provide the same information as HOSTS.TXT, allow distributed management, and flexibly interoperate across environments including the DARPA Internet, all while providing "tolerable" performance and imposing few limits on size of names or other components associated with it.
DNS requires the use of name servers, which store information and answer queries, and resolvers, which interact with client programs to find the right name server to connect to. Resolvers can choose to cache query responses. DNS has an internal name space in the form labels concatenated together from a variable-depth tree, allowing organizations flexibility to organize themselves and expand internally.
I found it amusing to hear that the Berkeley community was somewhat resistant to the change to DNS. As this paper was written over 20 years ago, I wonder if HOSTS.TXT is still used by many systems; I know I personally use a hosts mapping file in Linux to build shortcuts on top of DNS, but to be at all usable, HOSTS.TXT really needs to be an extra layer in addition to DNS to handle special cases at local levels.
Monday, November 2, 2009
Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications; Stoica, Morris, Karger, Kaashoek, & Balakrishnan
This paper discusses Chord, a distributed lookup protocol. Chord is a DHT that uses a distributed routing table and requires that each node have knowledge of only a few neighbors, making it scalable. It maintains a balanced load through the use of consistent hashing. Any key k has a successor node successor(k) that it corresponds to, with successor(k) being the first clockwise node from the identifier k. Nodes leaving and joining the network simply have values transferred back and forth between successors and themselves.
Each chord node maintains more than just the next successor; it keeps a finger table of a subset of log n nodes. These finger table entries can be used to find an identifier k by finding the closest predecessor j to k in the table and then sending the request to j and recursing until eventually the correct node has been found. A difficulty is in dealing with simultaneously joining/failing nodes, though apparently given a small "settling" time, the finger tables will eventually converge nicely.
The authors simulate Chord on a large network (thousands of nodes storing tens of thousands of keys) and also try it out on a smaller scale experimental testbed, looking at latency and path length. Problems they have not yet tackled include dealing with a partitioned Chord ring and dealing with malicious users. Additionally, there's a tradeoff between required number of lookups and finger table sizes which could use further exploration. Otherwise, Chord seems like a fairly straightforward, simple distributed lookup scheme.
Each chord node maintains more than just the next successor; it keeps a finger table of a subset of log n nodes. These finger table entries can be used to find an identifier k by finding the closest predecessor j to k in the table and then sending the request to j and recursing until eventually the correct node has been found. A difficulty is in dealing with simultaneously joining/failing nodes, though apparently given a small "settling" time, the finger tables will eventually converge nicely.
The authors simulate Chord on a large network (thousands of nodes storing tens of thousands of keys) and also try it out on a smaller scale experimental testbed, looking at latency and path length. Problems they have not yet tackled include dealing with a partitioned Chord ring and dealing with malicious users. Additionally, there's a tradeoff between required number of lookups and finger table sizes which could use further exploration. Otherwise, Chord seems like a fairly straightforward, simple distributed lookup scheme.
Looking Up Data in P2P Systems; Balakrishnan, Kaashoek, Karger, Morris, & Stoica
This article discusses the lookup problem in P2P networks, that is, scalable and efficient lookup. A few approaches include centralized databases, which have scalability and fault-tolerance issues, and DHTs, which involve passing around of key-value pairs. P2P systems do not employ hierarchical lookups, treating each host equally in the algorithm. Broadcasts between neighbors can be used when a node doesn't have a key, but too many broadcasts can quickly take down a system by using up all available bandwidth.
The authors then go into more depth about the DHTs, describing how each step in a lookup for some key or ID should progress to a node with a closer value to ID, based on some definition of closeness such as numeric difference or number of similar prefix bits. Chord is a DHT that uses a skip-list to allow binary searches for keys, whereas Pastry, Tapestry, Kademlia, and CAN all use tree-based structures.
The article is brief, having been published in communications of the ACM, but it seems to go into too much detail about the wrong things. I would have been more interested in an organized comparison of the different DHT implementations and an analysis of their strengths and weaknesses. Instead, I got a long discussion about P2P systems, skip lists, and hash table lookups.
The authors then go into more depth about the DHTs, describing how each step in a lookup for some key or ID should progress to a node with a closer value to ID, based on some definition of closeness such as numeric difference or number of similar prefix bits. Chord is a DHT that uses a skip-list to allow binary searches for keys, whereas Pastry, Tapestry, Kademlia, and CAN all use tree-based structures.
The article is brief, having been published in communications of the ACM, but it seems to go into too much detail about the wrong things. I would have been more interested in an organized comparison of the different DHT implementations and an analysis of their strengths and weaknesses. Instead, I got a long discussion about P2P systems, skip lists, and hash table lookups.
Thursday, October 29, 2009
Active network vision and reality: lessons from a capsule-based system; Wetherall
This paper describes a framework for Active Networks called ANTS. ANTS allows users to implement network functionality across an unrestricted set of nodes. Applications send special packets called capsules, in essence an extended IP packet which contains the actual service code to run on it, which are passed around via active node extensible routers.
ANTS decouples capsules from service code, caching service code for particular streams of packets and requesting code from a capsule's previously-visited active node if the current node doesn't have the service code cached. Capsules are kept from misbehaving by being greedy with resources or interfering with other payloads in the network by the ANTS sandbox in which their code is run.
The authors show graphs of ANTS latency and throughput versus capsule payload size and compare these results to impelementations of forwarding in Java and C. I had always heard people complain about how slow Java is compared to compiled languages like C, but I had never seen any results to verify that sentiment; these graphs were enough for me, as the C implementation can get about 4x the throughput of ANTS/Java. Hence, if the authors are more interested in ease of portability, they can stick with their Java implementation of ANTS, but if they want better performance, Java is not the answer.
Active Networks definitely seem to be in violation of the E2E principle: trying to implement functionality at the link layer for not much gain. Apparently Active Networks have applications such as multicast that they would be useful for distributing over the wide-area, but short of these few applications, it's difficult to see the real need for them.
ANTS decouples capsules from service code, caching service code for particular streams of packets and requesting code from a capsule's previously-visited active node if the current node doesn't have the service code cached. Capsules are kept from misbehaving by being greedy with resources or interfering with other payloads in the network by the ANTS sandbox in which their code is run.
The authors show graphs of ANTS latency and throughput versus capsule payload size and compare these results to impelementations of forwarding in Java and C. I had always heard people complain about how slow Java is compared to compiled languages like C, but I had never seen any results to verify that sentiment; these graphs were enough for me, as the C implementation can get about 4x the throughput of ANTS/Java. Hence, if the authors are more interested in ease of portability, they can stick with their Java implementation of ANTS, but if they want better performance, Java is not the answer.
Active Networks definitely seem to be in violation of the E2E principle: trying to implement functionality at the link layer for not much gain. Apparently Active Networks have applications such as multicast that they would be useful for distributing over the wide-area, but short of these few applications, it's difficult to see the real need for them.
Resilient Overlay Networks; Andersen, Balakrishnan, Kaashoek, & Morris
This paper discusses Resilient Overlay Networks (RON), which was created as a solution to the connectivity problems created by BGP's taking too much time to recover from faults. RON nodes continually monitor path (or virtual link) quality between themselves and other nodes and exchange this information amongst themselves to determine optimal routes based on some quality metric.
As different applications have different route needs in terms of latency, loss, and throughput, each group of clients (program communicating with node's RON software) can use their own metrics to determine paths. The entry node of a packet into the network identifies the needs of the incoming flow and selects a path from its routing table; it tags the packet with a flow ID and sends it on its way. Subsequent RON nodes can use flow ID tags to speed up the sending process for future packets.
RON uses link-state routing, where each node in the overlay needs to send information to every other node, which seems like a lot of wasteful overhead. However, since the problem being tackled deals with convergence time, RON floods are perhaps more desirable than lack of connectivity in the network. The three metrics a RON nodes keeps track of for each link are latency, loss, and throughput, and nodes frequently probe virtual links to ensure they're still usable.
In evaluating RON, the authors found that in one scenario RON was able to fully overcome outages (defined as packet loss rates above some given threshold for a certain length of time) and up to 60% of outages in the second set, the difference for which the authors don't discuss much, brushing it off as differences in the setup and also claiming that the 40% were due to sites not being reachable by any other RON site. It's not clear to me that the problem of connectivity posed by BGP's slow recovery justifies the use of RON, which will not scale well and also might not play well with NATs.
As different applications have different route needs in terms of latency, loss, and throughput, each group of clients (program communicating with node's RON software) can use their own metrics to determine paths. The entry node of a packet into the network identifies the needs of the incoming flow and selects a path from its routing table; it tags the packet with a flow ID and sends it on its way. Subsequent RON nodes can use flow ID tags to speed up the sending process for future packets.
RON uses link-state routing, where each node in the overlay needs to send information to every other node, which seems like a lot of wasteful overhead. However, since the problem being tackled deals with convergence time, RON floods are perhaps more desirable than lack of connectivity in the network. The three metrics a RON nodes keeps track of for each link are latency, loss, and throughput, and nodes frequently probe virtual links to ensure they're still usable.
In evaluating RON, the authors found that in one scenario RON was able to fully overcome outages (defined as packet loss rates above some given threshold for a certain length of time) and up to 60% of outages in the second set, the difference for which the authors don't discuss much, brushing it off as differences in the setup and also claiming that the 40% were due to sites not being reachable by any other RON site. It's not clear to me that the problem of connectivity posed by BGP's slow recovery justifies the use of RON, which will not scale well and also might not play well with NATs.
Tuesday, October 27, 2009
On Inferring Autonomous System Relationships in the Internet; Gao
This paper discusses ASes and inferring the relationships between them. It formally defines the concepts of peering, provider-customer, and sibling ASes based on the notion of transiting on behalf of other ASes. The author uses the fact that the selective export rule provides valley-free paths to establish 6 possible patterns an AS path can fit (e.g., uphill, downhill, uphill->downhill, uphill->p2p, p2p->downhill, uphill->p2p->downhill).
The author introduces maximal uphill and downhill paths, which are respectively the longest uphill path in an AS path (customer->provider and sibling->sibling edges only) and the remaining path that isn't the maximal uphill path. Relationships between pairs of ASes on a path can be determined if the top (topmost) providers for the uphill and downhill directions are known for these maximal paths.
The degree of an AS can be estimated by its size, allowing us to find the top provider. Prior to the top provider, all relationships are customer->provider or sibling relationships, and all following it are provider->customer or sibling relationships; these can be further refined based on transiting knowledge obtained from the ordering of ASes in a path.
Using heuristic algorithms, the author finds that out of all AS relationships from BGP routing tables taken at 3 different dates, few (1-2%) are siblings, a few more (~8%) are peering, and the remainder are customer-provider. He verifes his inferences with information from AT&T and the WHOIS lookup service, finding that their customer-provider inferences are correct, their peering inferences are generally correct, and sibling inferences are sometimes off.
This paper presented a cool, simple method for inferring AS relationships. However, it all hinges on the notion that a provider is larger in size than its client, which seems like a generally safe assumption to make, though it would be nice if the author had done some verifications of his own.
The author introduces maximal uphill and downhill paths, which are respectively the longest uphill path in an AS path (customer->provider and sibling->sibling edges only) and the remaining path that isn't the maximal uphill path. Relationships between pairs of ASes on a path can be determined if the top (topmost) providers for the uphill and downhill directions are known for these maximal paths.
The degree of an AS can be estimated by its size, allowing us to find the top provider. Prior to the top provider, all relationships are customer->provider or sibling relationships, and all following it are provider->customer or sibling relationships; these can be further refined based on transiting knowledge obtained from the ordering of ASes in a path.
Using heuristic algorithms, the author finds that out of all AS relationships from BGP routing tables taken at 3 different dates, few (1-2%) are siblings, a few more (~8%) are peering, and the remainder are customer-provider. He verifes his inferences with information from AT&T and the WHOIS lookup service, finding that their customer-provider inferences are correct, their peering inferences are generally correct, and sibling inferences are sometimes off.
This paper presented a cool, simple method for inferring AS relationships. However, it all hinges on the notion that a provider is larger in size than its client, which seems like a generally safe assumption to make, though it would be nice if the author had done some verifications of his own.
Monday, October 26, 2009
On Power-Law Relationships of the Internet Topology; Faloutsos, Faloutsos, & Faloutsos
This paper presents empirically-discovered power laws that can shine some light on traits of the Internet topology including neighbors and inter-domain connectivity. These laws are based on data about the number of ASes present between 1997 and 1998.
A few power laws were uncovered. The first involves the rank exponent, which states that the outdegree (number of edges incident to a node) is proportional to the rank of the node (index of node sorted by decreasing outdegree) raised to the constant R (slope of outdegree vs. rank of nodes, which can differ per graph family). Through this power law, the authors derive an estimation for the number of edges in a graph, which in practical terms can give an idea of connections between domains in the Internet.
A second power law states that the frequency of an outdegree (number of nodes with that outdegree) is proportional to the outdegree raised to the constant O (slope of frequency vs. outdegree). Apparently the O value is fairly constant regardless of the graph family. I found this law pretty amazing, as I would have expected much more randomness in outdegree frequency. In particular, the authors make a fairly strong statement about using this law to test realism of a topology, that if the exponent is far off or if the topology doesn't follow the law, "it probably does not represent a real topology."
A less powerful "law" (deemed an approximation because it consists of only 4 data points) deals with neighboring connectivity, stating that the number of pairs of nodes within some number of hops is proportional to the number of hops raised to the power of H (slope of pairs of nodes within some number of hops vs. number of hops). One of the four graphs actually had enough data to show any evidence of this approximation; the others were pretty worthless.
The final power law states that the eigenvalues of a graph are proportional to the order (in decreasing eigenvalue sequence) raised to the power of E (slope of sorted eigenvalues vs. order). This law is much more abstract to me; I'm not quite sure what the practical ramifications of it are.
I didn't think I'd like this paper initially, thinking it would be heavy on the math and light on applicability, but with each power law, the authors presented some ways to use the law, such as for estimating the number of edges, neighbors, and diameter of a graph. Additionally, these laws can be used to verify the realism of proposed topologies. In using these laws to make predictions for the future, however, they are basing estimates on a little over one year's worth of data from the late 90s. My intuition is that their guesses are far too low, but I would be interested in seeing current numbers for the Internet.
A few power laws were uncovered. The first involves the rank exponent, which states that the outdegree (number of edges incident to a node) is proportional to the rank of the node (index of node sorted by decreasing outdegree) raised to the constant R (slope of outdegree vs. rank of nodes, which can differ per graph family). Through this power law, the authors derive an estimation for the number of edges in a graph, which in practical terms can give an idea of connections between domains in the Internet.
A second power law states that the frequency of an outdegree (number of nodes with that outdegree) is proportional to the outdegree raised to the constant O (slope of frequency vs. outdegree). Apparently the O value is fairly constant regardless of the graph family. I found this law pretty amazing, as I would have expected much more randomness in outdegree frequency. In particular, the authors make a fairly strong statement about using this law to test realism of a topology, that if the exponent is far off or if the topology doesn't follow the law, "it probably does not represent a real topology."
A less powerful "law" (deemed an approximation because it consists of only 4 data points) deals with neighboring connectivity, stating that the number of pairs of nodes within some number of hops is proportional to the number of hops raised to the power of H (slope of pairs of nodes within some number of hops vs. number of hops). One of the four graphs actually had enough data to show any evidence of this approximation; the others were pretty worthless.
The final power law states that the eigenvalues of a graph are proportional to the order (in decreasing eigenvalue sequence) raised to the power of E (slope of sorted eigenvalues vs. order). This law is much more abstract to me; I'm not quite sure what the practical ramifications of it are.
I didn't think I'd like this paper initially, thinking it would be heavy on the math and light on applicability, but with each power law, the authors presented some ways to use the law, such as for estimating the number of edges, neighbors, and diameter of a graph. Additionally, these laws can be used to verify the realism of proposed topologies. In using these laws to make predictions for the future, however, they are basing estimates on a little over one year's worth of data from the late 90s. My intuition is that their guesses are far too low, but I would be interested in seeing current numbers for the Internet.
Sunday, October 25, 2009
White Space Networking with Wi-Fi like Connectivity; Bahl, Chandra, Moscibroda, Murty, & Welsh
This paper discusses WhiteFi, a Wi-Fi like protocol meant for use in UHF white spaces. The difficulty in configuring networks in the UHF realm is efficient channel assignment and Access Point (AP) discovery without causing interference from packet transmissions. WhiteFi must deal with spatial/temporal variation (different channels available in different locations/times) and spectrum fragmentation (non-contiguous channels).
WhiteFi uses special hardware called KNOWS which consists of a UHF translator that translates Wi-Fi signal to the proper UHF band, scanner that searches for signals, and processor that performs a FFT on the incoming signals. APs select the channel to operate on by finding the channel that maximizes the metric MCham, their expected share of the channel as calculated from all associated clients; channel selection happens periodically.
Variable channel widths complicate the process of clients finding an AP. Instead of scanning every possible channel at every channel width, clients scan a subset of channels and use the SIFT technique to detect an AP in hardware. Moving this process from software to hardware and reducing the number of scans improved performance significantly in simulation. One important aspect of channel assignment the paper neglects is incumbent detection; the authors bank on future research solving this problem and assume that part is dealt with.
When an AP or client senses an incumbent on the channel, it disconnects. WhiteFi handles these disconnections via a chirping protocol. In the APs normal beacons, it advertises a backup channel. In the case of disconnection, AP and client switch to the backup channel and transmit chirps until a new channel can be decided selected.
This paper had a number of aspects that were mysterious to me. First off, I didn't have much previous knowledge of the UHF spectrum, and the paper's introduction didn't really help that much. (Thanks to Wikipedia for a very helpful summary and description of UHF.) Secondly, why all this focus on wireless microphones? Out of all the electronic equipment out there, are these really the main concern in terms of wireless transmitters that could be impacted by interference from packets? Maybe it's just that in particular they are prevalently used with difficult-to-predict usage. An unfortunate fact of research on the UHF spectrum is that full-scale evaluations cannot be done without FCC approval, so simulations have to suffice.
WhiteFi uses special hardware called KNOWS which consists of a UHF translator that translates Wi-Fi signal to the proper UHF band, scanner that searches for signals, and processor that performs a FFT on the incoming signals. APs select the channel to operate on by finding the channel that maximizes the metric MCham, their expected share of the channel as calculated from all associated clients; channel selection happens periodically.
Variable channel widths complicate the process of clients finding an AP. Instead of scanning every possible channel at every channel width, clients scan a subset of channels and use the SIFT technique to detect an AP in hardware. Moving this process from software to hardware and reducing the number of scans improved performance significantly in simulation. One important aspect of channel assignment the paper neglects is incumbent detection; the authors bank on future research solving this problem and assume that part is dealt with.
When an AP or client senses an incumbent on the channel, it disconnects. WhiteFi handles these disconnections via a chirping protocol. In the APs normal beacons, it advertises a backup channel. In the case of disconnection, AP and client switch to the backup channel and transmit chirps until a new channel can be decided selected.
This paper had a number of aspects that were mysterious to me. First off, I didn't have much previous knowledge of the UHF spectrum, and the paper's introduction didn't really help that much. (Thanks to Wikipedia for a very helpful summary and description of UHF.) Secondly, why all this focus on wireless microphones? Out of all the electronic equipment out there, are these really the main concern in terms of wireless transmitters that could be impacted by interference from packets? Maybe it's just that in particular they are prevalently used with difficult-to-predict usage. An unfortunate fact of research on the UHF spectrum is that full-scale evaluations cannot be done without FCC approval, so simulations have to suffice.
Interactive WiFi Connectivity for Moving Vehicles; Balasubramanian, Mahajan, Venkataramani, Levine, & Zahorjan
This paper describes ViFi, a protocol for minimizing interruptions in connectivity of WiFi in moving vehicles. The authors describe six policies for handoffs between base stations: RSSI (highest signal strength BS), BRR (highest beacon reception ratio), Sticky (stay with BS until connectivity drops too low), History (BS with historically best performance), BestBS (BS that will be best in future), and AllBSes (utilize all BSes in range). AllBSes represents an upper bound to performance; if packets are lost for one BS, there will likely be another that received them, particularly in situations involving bursty loss.
ViFi works by having the vehicle designate a BS as its anchor, acting as the vehicle's gateway to the Internet, and other BSes in range of the vehicle are auxiliaries. The vehicle periodically broadcasts beacons that contain info about the current anchor and auxiliaries as well as the previous anchor. ViFi is actually deployed in VanLAN, and the authors use traces collected from DieselNet for simulations as well.
ViFi employs the techniques of diversity and salvaging to improve session connections; diversity is the use of multiple basestations to deliver packets, and salvaging is the transmitting of unacknowledged data from the Internet held in previous anchors. Some of the difficulties in ViFi are similar to those in the ExOR system, including coordination between nodes.
The algorithm for transmission works as follows: if the intended destination receives a packet, it sends an ACK. Any auxiliaries that overhear the packet and don't hear the ACK within a certain period probabilistically relay the packet. These relaying auxiliaries must take into account other auxiliaries that might be relaying as well as quality of connectivity, all while trying to keep the expected number of relays to a minimum. Packet reception rates are based on the beacons the vehicle sends.
ViFi doesn't do any packet reordering, as the authors claim it's not necessary for good performance, but it might have been nice to see some numbers about how frequent reordering is. The graphs involving session length took me a little longer to understand than I would have liked; I think there may be more intuitive ways of showing how good the connections were.
On the whole, ViFi seems like a pretty good idea and gets good results for short TCP transfers and VoIP sessions. I wonder how representative of a typical vehicle workload these tests are, though. Certainly short TCP transfers as from web surfing makes sense, but how often are people Skyping on a Microsoft shuttle bus? I liked that the paper talked about the limitations of ViFi; unfortunately, it sounds like large-scale deployment would be very difficult, and if ViFi were only implemented in large islands, maintaining connectivity could be complex.
ViFi works by having the vehicle designate a BS as its anchor, acting as the vehicle's gateway to the Internet, and other BSes in range of the vehicle are auxiliaries. The vehicle periodically broadcasts beacons that contain info about the current anchor and auxiliaries as well as the previous anchor. ViFi is actually deployed in VanLAN, and the authors use traces collected from DieselNet for simulations as well.
ViFi employs the techniques of diversity and salvaging to improve session connections; diversity is the use of multiple basestations to deliver packets, and salvaging is the transmitting of unacknowledged data from the Internet held in previous anchors. Some of the difficulties in ViFi are similar to those in the ExOR system, including coordination between nodes.
The algorithm for transmission works as follows: if the intended destination receives a packet, it sends an ACK. Any auxiliaries that overhear the packet and don't hear the ACK within a certain period probabilistically relay the packet. These relaying auxiliaries must take into account other auxiliaries that might be relaying as well as quality of connectivity, all while trying to keep the expected number of relays to a minimum. Packet reception rates are based on the beacons the vehicle sends.
ViFi doesn't do any packet reordering, as the authors claim it's not necessary for good performance, but it might have been nice to see some numbers about how frequent reordering is. The graphs involving session length took me a little longer to understand than I would have liked; I think there may be more intuitive ways of showing how good the connections were.
On the whole, ViFi seems like a pretty good idea and gets good results for short TCP transfers and VoIP sessions. I wonder how representative of a typical vehicle workload these tests are, though. Certainly short TCP transfers as from web surfing makes sense, but how often are people Skyping on a Microsoft shuttle bus? I liked that the paper talked about the limitations of ViFi; unfortunately, it sounds like large-scale deployment would be very difficult, and if ViFi were only implemented in large islands, maintaining connectivity could be complex.
Subscribe to:
Posts (Atom)