This paper is another examination of solutions to and the cause of the incast problem. They analyze the incast phonemon with and without the changes proposed in the CMU paper (much lower minRTO/disabling delayed ACKs). Unlike the CMU paper, the evaluation here primarily uses a constant data per source scenario rather than a constant data per sink scenario. They find that this fixed-source-size workload yields more complex goodput behavior than the other scenario. And in contrast the CMU findings, the authors find that delayed ACKs, in fact, do help against incast for large numbers of senders because they induce increased variance in the RTT estimate and TCP window size.
The authors produced a simple numerical model of the throughput collapse behavior assuming that it is determined by the number of retransmission timeout events and the interpacket wait time. From this model and refinements, the authors produce an explanation for the throughput collapse behavior: first, throughput collapses as the number of retransmission timeouts increases with the number of senders, then the width of period in which retransmission timeouts are triggered (per congestion event) increases, so recovery senders become desynchronized, but eventually the width of that distribution becomes so wide that senders about to experience a timeout interfere with senders just recovering from a timeout.
It is disappointing that the qualitative observations which would seem to explain the throughput collapse are not incorporated into the model, nor is an good empirical way to test for their presence beyond fitting a more complicated model attempted or suggested.
Sunday, September 27, 2009
Monday, September 21, 2009
VL2
This paper is remarkable similar to PortLand. Therefore, I will focus first on the differences:
The authors use some traces (presumably from MS data centers) and show that flow size varies a lot, traffic patterns are not very predictable, and small failures are frequent. They use these traces to motivate their choice of random load balancing rather than assuming a smarter scheme exists. For their prototype evaluation they measure utilization and fairness under an all-to-all TCP scenario on their 75-node testbed (apparently with near-commodity hardware) and measure interference between two services (with and without large numbers of TCP flows (‘mice’) in one service).
Probably the best feature of this paper is the authors extensive reuse of existing protocol implementations (OSPF, ECMP, etc.) This means that their fabric is probably more readily deployable and more hardware-agnostic than PortLand. It is also a disadvantage: they are not taking advantage of the relatively predictable topology they demand for routing, and many more pieces of hardware (each end-host) needs to be reconfigured than under the PortLand scheme which is truly invisible to the end-hosts.
- Topology — the supported topologies are folded Clos networks. Similar to fat trees, these provide many paths between racks and, as in PortLand, the authors propose routing flows randomly over the paths. Both of the papers examine three-stage topologies, both of which would support approximately the same number of end-hosts based on the number of ports each switch had; though the fat tree topology examined would use considerably more switches. To achieve similar performance VL2 assumes that switch-to-switch bandwidths are substantially higher than end-host-to-switch bandwidths. The fat tree topology is also considerably more regular, so where PortLand relies on location-specifying MAC addresses and explicit failure notifications the VL2 scheme runs a link state protocol between switches (but not to export end-host addresses) while .
- Layer choice — VL2 uses location-specifying IP addresses; providing a mapping from location-agnostic (relocatable) IP addresses to location-specific ones analagous to PortLand's AMAC to PMAC mapping. Unlike PortLand, using IP addresses combines two mappings (AMAC to PMAC and PMAC to IP) that PortLand maintained into one mapping that VL2 contains (AA to LA). The disadvantage, of course, is that servers need extra support to know this mapping (doing IP in IP encapsulation) rather than it being backwards-compatible as using the ARP cache is.
- The directory servers — in this paper, they are only responsible for the AA to LA mappings (no failure matrix), and replication/distribution of the directory servers is actually implemented. Also, the directory servers are queried by end-hosts rather than by switches;
- Autoconfiguration story — None seems apparent in this paper.
- Hardware required — The system in this paper runs on commodity switching ASICs, relying mostly on existing switch features rather than custom switching software.
The authors use some traces (presumably from MS data centers) and show that flow size varies a lot, traffic patterns are not very predictable, and small failures are frequent. They use these traces to motivate their choice of random load balancing rather than assuming a smarter scheme exists. For their prototype evaluation they measure utilization and fairness under an all-to-all TCP scenario on their 75-node testbed (apparently with near-commodity hardware) and measure interference between two services (with and without large numbers of TCP flows (‘mice’) in one service).
Probably the best feature of this paper is the authors extensive reuse of existing protocol implementations (OSPF, ECMP, etc.) This means that their fabric is probably more readily deployable and more hardware-agnostic than PortLand. It is also a disadvantage: they are not taking advantage of the relatively predictable topology they demand for routing, and many more pieces of hardware (each end-host) needs to be reconfigured than under the PortLand scheme which is truly invisible to the end-hosts.
Saturday, September 19, 2009
PortLand
This paper describes a layer-2 switch fabric targeted at datacenters. Scalability and the obvious simple correctness goals apply (loop-free forwarding, fault-tolerance) as well as ease of configuration and allowing IP addresses to move around in the datacenter.
To make this task simpler (that is, with less per-switch state) the authors fix the datacenter's topology as a fat tree and designate a centralized ‘fabric manager’ (which must be replicated for fault tolerance, of course) which coordinates between switches.
As with SEATTLE, the switches in this scheme handle all ARP requests themselves in addition to managing routing.
Switch state is kept small by distributing ‘pseudo MAC’ addresses which encodes the position of the destination node in the topology; a host's actual MAC address is never distributed to other nodes. The fabric manager controls the IP to PMAC mapping, allowing switches to respond to ARP requests and generate gratuitous ARPs if a PMAC becomes invalid.
Forwarding is kept loop-free by assuming a rooted fat tree and by following the rule that a packet changes from going up toward the root to down toward a node exactly once. For load balancing, switches can choose freely between upstream ports (the authors suggest switching on flows to keep each flow single-path); for fault-tolerance, the fabric manager distributes failure information to affected switches who then update their routing tables accordingly.
Probably the most clever scheme here is switch autoconfiguration. Bottom level switches discover that they are connected to enough non-switches, and the level number of higher-level switches propagates up the fat-tree. Position number assignment is done in a greedy fashion, synchronized by a higher level switch.
Combined with failed link detection, this should make (re)configuration automatic except for the pesky issue of the fabric manager and communication with it.
The authors tested their system on a 16-host prototype, evaluating its response to failures, IP migration, and the overhead it imposed on the fabric manager. Failures resulted in approximately 100 milliseconds of disconnectivity (which was, of course, made worse by TCP timeouts), and for the VM migration scenario, the TCP flow stalls fails for periods of approx 200-600 ms. For the fabric manager, they evaluated the overhead of between 25 and 100 ARP misses/sec/host, asssumed scaling, and extrapolated the CPU and network bandwidth uses of the fabric manager, and found that the fabric manager would require a lot of CPU resources (70 cores for the 100 ARP/sec case with ~30k hosts).
These numbers are disappointing though the authors point out that these miss rates seem unrealistic and that the fabric manager could probably be distributed to a cluster. Since presumably the authors are pretty confident that ARP miss rates are considerably lower in a real data center, it is disappointing that they didn't try to measure or intelligently estimate the rate at which they would be expected to occur. The linear extrapolation is also disappointing — couldn't the authors have really run their fabric manager on a synthetic trace with these miss rates and host count and measured the CPU usage?
To make this task simpler (that is, with less per-switch state) the authors fix the datacenter's topology as a fat tree and designate a centralized ‘fabric manager’ (which must be replicated for fault tolerance, of course) which coordinates between switches.
As with SEATTLE, the switches in this scheme handle all ARP requests themselves in addition to managing routing.
Switch state is kept small by distributing ‘pseudo MAC’ addresses which encodes the position of the destination node in the topology; a host's actual MAC address is never distributed to other nodes. The fabric manager controls the IP to PMAC mapping, allowing switches to respond to ARP requests and generate gratuitous ARPs if a PMAC becomes invalid.
Forwarding is kept loop-free by assuming a rooted fat tree and by following the rule that a packet changes from going up toward the root to down toward a node exactly once. For load balancing, switches can choose freely between upstream ports (the authors suggest switching on flows to keep each flow single-path); for fault-tolerance, the fabric manager distributes failure information to affected switches who then update their routing tables accordingly.
Probably the most clever scheme here is switch autoconfiguration. Bottom level switches discover that they are connected to enough non-switches, and the level number of higher-level switches propagates up the fat-tree. Position number assignment is done in a greedy fashion, synchronized by a higher level switch.
Combined with failed link detection, this should make (re)configuration automatic except for the pesky issue of the fabric manager and communication with it.
The authors tested their system on a 16-host prototype, evaluating its response to failures, IP migration, and the overhead it imposed on the fabric manager. Failures resulted in approximately 100 milliseconds of disconnectivity (which was, of course, made worse by TCP timeouts), and for the VM migration scenario, the TCP flow stalls fails for periods of approx 200-600 ms. For the fabric manager, they evaluated the overhead of between 25 and 100 ARP misses/sec/host, asssumed scaling, and extrapolated the CPU and network bandwidth uses of the fabric manager, and found that the fabric manager would require a lot of CPU resources (70 cores for the 100 ARP/sec case with ~30k hosts).
These numbers are disappointing though the authors point out that these miss rates seem unrealistic and that the fabric manager could probably be distributed to a cluster. Since presumably the authors are pretty confident that ARP miss rates are considerably lower in a real data center, it is disappointing that they didn't try to measure or intelligently estimate the rate at which they would be expected to occur. The linear extrapolation is also disappointing — couldn't the authors have really run their fabric manager on a synthetic trace with these miss rates and host count and measured the CPU usage?
Wednesday, September 16, 2009
Detailed Diagnosis in Enterprise Networks
This paper describes a system (called NetMedic) for identifying the likely location of the root cause of faults from component state/performance traces. Machine-local information (such CPU and memory utilization) in addition to network information (such as traffic rates and response times) are collected and assigned to “components” which, in the paper's evaluation, correspond to entities such as machines, user processes, or the collective networking infrastructure.
Since the system does not assume any domain knowledge about the measurements it receives, faults are detected based on measurements deviating from their usual values. Diagnosis uses historical correlations to determine whether an anomalous measurement bis likely influencing/influenced by another. To determine which components' measurements to compare, domain knowledge is used: ‘template’ mark the dependencies each component type has to other components (e.g. between a machine and all of its processes or between processes communicating over IP). Given this directed dependency graph and the likelihood of measurements influencing each other, the ‘best’ cause is determined based on the best geometric means of influence scores on paths from the alleged cause to components, weighted by the destination components' abnormality, combined with this geometric mean for the component being diagnosed.
The authors include an evaluation where they analyze whether their system can diagnose injected faults causes correctly. They compare their approach to a simpler approach and a hand-tuned aporoach. Both share the dependency graph and root cause ranking method. The simpler method only measures whether components are ‘abnormal’ and computes influencing ranks based solely on whether both components are abnormal; the hand-tuned method only measures influence between variables hand-marked as related. The authors find that their system gave the correct cause as the first ranked cause for almost all the injected faults, and did so substantially better than the simple approach, which was successful about half of the time. The hand-tuned approach did not a substantial improvement, showing that the authors had not lost much but avoiding domain-specific knowledge in that part.
One troubling aspect of this work is formulas that seem to be chosen mostly arbitrarily (e.g. using geometric mean and sqrt(c->e value * global weighted value) for cause ranking; the choice of 0.1 and 0.8 has a ‘default’ edge weight; etc.) Of course, the authors had to make some choice here, but from the results we cannot tell how sensitive correct diagnosis is to these choices — is there technique actually general enough that they mostly don't matter? (The authors did do a sensitivity analysis for one of these parameters — the length of history used for diagnosis.)
There's also the big step away from fully domain-agnostic diagnosis in requiring templates. These templates are fortunately applicable to many kinds of applications, which is why, based on their motivation, they felt it okay to use them but not such similar input about the measurements they are taking. But these templates do not look entirely trivially to make: the ones they show have many subtle dependencies, such as on machine firewalls and other traffic. Are they actually easy to infer, and given that the authors have gone to great effort to develop a method for ignoring irrelevant correlations, how useful are they?
Since the system does not assume any domain knowledge about the measurements it receives, faults are detected based on measurements deviating from their usual values. Diagnosis uses historical correlations to determine whether an anomalous measurement bis likely influencing/influenced by another. To determine which components' measurements to compare, domain knowledge is used: ‘template’ mark the dependencies each component type has to other components (e.g. between a machine and all of its processes or between processes communicating over IP). Given this directed dependency graph and the likelihood of measurements influencing each other, the ‘best’ cause is determined based on the best geometric means of influence scores on paths from the alleged cause to components, weighted by the destination components' abnormality, combined with this geometric mean for the component being diagnosed.
The authors include an evaluation where they analyze whether their system can diagnose injected faults causes correctly. They compare their approach to a simpler approach and a hand-tuned aporoach. Both share the dependency graph and root cause ranking method. The simpler method only measures whether components are ‘abnormal’ and computes influencing ranks based solely on whether both components are abnormal; the hand-tuned method only measures influence between variables hand-marked as related. The authors find that their system gave the correct cause as the first ranked cause for almost all the injected faults, and did so substantially better than the simple approach, which was successful about half of the time. The hand-tuned approach did not a substantial improvement, showing that the authors had not lost much but avoiding domain-specific knowledge in that part.
One troubling aspect of this work is formulas that seem to be chosen mostly arbitrarily (e.g. using geometric mean and sqrt(c->e value * global weighted value) for cause ranking; the choice of 0.1 and 0.8 has a ‘default’ edge weight; etc.) Of course, the authors had to make some choice here, but from the results we cannot tell how sensitive correct diagnosis is to these choices — is there technique actually general enough that they mostly don't matter? (The authors did do a sensitivity analysis for one of these parameters — the length of history used for diagnosis.)
There's also the big step away from fully domain-agnostic diagnosis in requiring templates. These templates are fortunately applicable to many kinds of applications, which is why, based on their motivation, they felt it okay to use them but not such similar input about the measurements they are taking. But these templates do not look entirely trivially to make: the ones they show have many subtle dependencies, such as on machine firewalls and other traffic. Are they actually easy to infer, and given that the authors have gone to great effort to develop a method for ignoring irrelevant correlations, how useful are they?
Floodless in SEATTLE
This paper proposes an architecture for managing Ethernet routing over an enterprise-type network. It aims to provide more scalability than Ethernet bridging and easier administration and address portability than IP subnetting and VLAN-based approaches. In this approach, switches use a link-state protocol to route amongst themselves, and, using this, form a DHT to store end-host routing information. This DHT distributes the routing information across the routers so the amount of information stored by each switch is proportional the average number of end hosts a router has. This information is, of course, not local to the switches which need it, so switches maintain a cache of this information, invalidated (by the destination switch) on the use of a stale entry. To interact with unmodified end hosts, the authors implement ARP and DHCP backed by information in the DHT. ARP broadcasts used to invalidate cached are translated to unicasts to interested hosts by tracking which hosts may have cached entries.
The authors evaluated their using a trace driven simulation on several real network topologies and an evaluation with an actual implementation on a very small network.
From the simulations, they showed that the information maintained per router was actually smaller than both Ethernet bridging based approaches and that it achieved better routes (given similar cache sizes) than past identity-based routing proposals. From the actual implementation, they measured the per-packet overhead, performance when attempting to contact many non-existent hosts, and switch fail-over speed.
It's unfortunate that this paper did not include an explicit comparison to IP subnetting or VLANs, by which it is clearly motivated. It is understandable why, of course; their arguments against IP subnetting are based on ease of configuration which is very difficult to measure. For VLANs, only some of their complaints were about ease of configuration, but for the others it might be hard to infer a suitable configuration from their topology information.
This scheme is attractive for its careful attention to complete transparency for end-hosts, which should make it relatively easy to deploy. The big problem is that deploying it in the most straightforward way involves changing all switches over; it would seem, however, that there's probably some way of constructing a reasonable middle-ground where it is deployed gradually across the network.
The authors evaluated their using a trace driven simulation on several real network topologies and an evaluation with an actual implementation on a very small network.
From the simulations, they showed that the information maintained per router was actually smaller than both Ethernet bridging based approaches and that it achieved better routes (given similar cache sizes) than past identity-based routing proposals. From the actual implementation, they measured the per-packet overhead, performance when attempting to contact many non-existent hosts, and switch fail-over speed.
It's unfortunate that this paper did not include an explicit comparison to IP subnetting or VLANs, by which it is clearly motivated. It is understandable why, of course; their arguments against IP subnetting are based on ease of configuration which is very difficult to measure. For VLANs, only some of their complaints were about ease of configuration, but for the others it might be hard to infer a suitable configuration from their topology information.
This scheme is attractive for its careful attention to complete transparency for end-hosts, which should make it relatively easy to deploy. The big problem is that deploying it in the most straightforward way involves changing all switches over; it would seem, however, that there's probably some way of constructing a reasonable middle-ground where it is deployed gradually across the network.
Monday, September 14, 2009
Random Early Detection Gateways
This describes a queue discipline that gives better congestion signals to TCP flows than Drop Tail and slight refinements on Drop Tail like Early Random Drop. The authors observe that a problem with Drop Tail and Early Random Drop is that they both only act when the queue is near-full, thereby discriminating against bursty flows and causing global synchronization. To avoid this, this scheme (RED) tracks a long-term average queue size and ‘marks’ (drop for TCP) packets according to this size such that marks are distributed approximately evenly over time. The authors evaluate their scheme with multiple TCP flows with different round-trip times going over a bottleneck link, and show that it avoids global synchronization and achieves fairness among bursty flows (in their example, TCP flows over a high-bandwidth delay product relative to their window size).
The oddest omission from this paper to me was packet sizes: The algorithm and the simulations work in terms of whole packets apparently without considering the size of packets. This is particularly odd given that one might expect bursty interactive flows to have variable packet sizes.
This paper does remarkably simplify its problem by assuming that all flows are running a congestion control algorithm, as this scheme does not converge to fairness in the phase of loss-agnostic flows (which the authors did not test). The authors propose sampling dropped packet, showing that a window of dropped packets is likely to have close to the expected number (based on actual) of dropped packets from each flow; however, the authors don't evaluate this scheme beyond this theoretical observation.
The oddest omission from this paper to me was packet sizes: The algorithm and the simulations work in terms of whole packets apparently without considering the size of packets. This is particularly odd given that one might expect bursty interactive flows to have variable packet sizes.
This paper does remarkably simplify its problem by assuming that all flows are running a congestion control algorithm, as this scheme does not converge to fairness in the phase of loss-agnostic flows (which the authors did not test). The authors propose sampling dropped packet, showing that a window of dropped packets is likely to have close to the expected number (based on actual) of dropped packets from each flow; however, the authors don't evaluate this scheme beyond this theoretical observation.
Congestion Control for High Bandwidth-Delay Product Networks
This paper describes a protocol (called XCP) for congestion control that utilizes explicit signaling of the degree of congestion by routers. To replace the dropped-packet signal, senders include an explicit ‘feedback&rsquo field indicating their desired window size adjustment upon receiving an ACK for a packet. Routers modify this value (guided by the sender's current window size and RTT estimate, which the sender must also include) according to both fairness and efficiency criteria. To adjust for efficiency, routers estimate the difference between incoming and the maximum outgoing bandwidth and ensure that provided feedback values add up to this value over the measurement interval. To provide fairness, the additive-increase/multiplicative-decrease scheme of TCP is used to set the feedbacks, with the overall amount of increase or decrease chosen to match the measured bandwidth deficit or surplus. When the bandwidth deficit or surplus is almost 0 but fairness has not been achieved, feedback is still set for some portion of traffic to ensure convergence to fairness.
The authors measured their scheme in simulation in number of circumstances. Their simulations showed that it output performed TCP with any of several queuing disciplines in terms of speed of convergence to near full utilization and fairness and behavior with competing flows. (One notable exception was their "shuffling" scheme to ensure convergence to fairness would cause notable loss of throughput when a router downstream of a bottleneck would try to adjust bandwidth upwards to provide it a better share.) Additionally, the authors' simulations showed that their new protocol could be made to not discriminate against TCP flows.
The biggest issue with this protocol is the difficulty of implementation. To implement this scheme, routers will need to track per-flow state, and to provide it with security, would need to occasionally “test” flows to ensure that they are not cheating. The authors do propose a scheme similar to Core-Stateless Fair Queuing to isolate the changes of XCP to an administrative domain, but besides reducing the security issue and the number of potential flows to track to a function of the number of edge routers, this scheme does not seem to reduce the per-router overhead. And though the scheme to multiplex TCP flows alongside XCP flows helps, even the core/edge strategy for XCP (which the authors did not simulate) appears ill-suited for incremental deployment.
From a security standpoint, I find it somewhat disturbing that the ‘check if the flow’ responds scheme relies upon the sender-provided RTT estimate. I guess, however, that reasonable capping of this RTT would still yield an improvement upon the response time of such ‘enforcement’ schemes on traditional TCP.
The authors measured their scheme in simulation in number of circumstances. Their simulations showed that it output performed TCP with any of several queuing disciplines in terms of speed of convergence to near full utilization and fairness and behavior with competing flows. (One notable exception was their "shuffling" scheme to ensure convergence to fairness would cause notable loss of throughput when a router downstream of a bottleneck would try to adjust bandwidth upwards to provide it a better share.) Additionally, the authors' simulations showed that their new protocol could be made to not discriminate against TCP flows.
The biggest issue with this protocol is the difficulty of implementation. To implement this scheme, routers will need to track per-flow state, and to provide it with security, would need to occasionally “test” flows to ensure that they are not cheating. The authors do propose a scheme similar to Core-Stateless Fair Queuing to isolate the changes of XCP to an administrative domain, but besides reducing the security issue and the number of potential flows to track to a function of the number of edge routers, this scheme does not seem to reduce the per-router overhead. And though the scheme to multiplex TCP flows alongside XCP flows helps, even the core/edge strategy for XCP (which the authors did not simulate) appears ill-suited for incremental deployment.
From a security standpoint, I find it somewhat disturbing that the ‘check if the flow’ responds scheme relies upon the sender-provided RTT estimate. I guess, however, that reasonable capping of this RTT would still yield an improvement upon the response time of such ‘enforcement’ schemes on traditional TCP.
Subscribe to:
Posts (Atom)