Over the past one and half years, we have been using RDMA over commodity Ethernet (RoCEv2) to support some of Microsoft's highly-reliable, latency-sensitive services. This paper describes the challenges we encountered during the process and the solutions we devised to address them. In order to scale RoCEv2 beyond VLAN, we have designed a DSCP-based priority flow-control (PFC) mechanism to ensure large-scale deployment. We have addressed the safety challenges brought by PFC-induced deadlock (yes, it happened!), RDMA transport livelock, and the NIC PFC pause frame storm problem. We have also built the monitoring and management systems to make sure RDMA works as expected. Our experiences show that the safety and scalability issues of running RoCEv2 at scale can all be addressed, and RDMA can replace TCP for intra data center communications and achieve low latency, low CPU overhead, and high throughput.

Modern datacenter applications demand high throughput (40Gbps) and ultra-low latency (< 10 μs per hop) from the network, with low CPU overhead. Standard TCP/IP stacks cannot meet these requirements, but Remote Direct Memory Access (RDMA) can. On IP-routed datacenter networks, RDMA is deployed using RoCEv2 protocol, which relies on Priority-based Flow Control (PFC) to enable a drop-free network. However, PFC can lead to poor application performance due to problems like head-of-line blocking and unfairness. To alleviates these problems, we introduce DCQCN, an end-to-end congestion control scheme for RoCEv2. To optimize DCQCN performance, we build a fluid model, and provide guidelines for tuning switch buffer thresholds, and other protocol parameters. Using a 3-tier Clos network testbed, we show that DCQCN dramatically improves throughput and fairness of RoCEv2 RDMA traffic. DCQCN is implemented in Mellanox NICs, and is being deployed in Microsoft's datacenters.

Abstract In this note, we prove that a collection of single bend paths on a grid, the so‐called B1 representations, have strong Helly number 4. This corrects a false claim from Ref. [Golumbic et al., Networks, 54 (2009), 130–138; and other errata are also corrected. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013

Abstract We combine the known notion of the edge intersection graphs of paths in a tree with a VLSI grid layout model to introduce the edge intersection graphs of paths on a grid. Let 𝒫 be a collection of nontrivial simple paths on a grid 𝒢. We define the edge intersection graph E P G (𝒫) of 𝒫 to have vertices which correspond to the members of 𝒫, such that two vertices are adjacent in E P G (𝒫) if the corresponding paths in 𝒫 share an edge in 𝒢. An undirected graph G is called an edge intersection graph of paths on a grid (EPG) if G = E P G (𝒫) for some 𝒫 and 𝒢, and 〈𝒫,𝒢〉 is an EPG representation of G . We prove that every graph is an EPG graph. A turn of a path at a grid point is called a bend. We consider here EPG representations in which every path has at most a single bend, called B 1 ‐EPG representations and the corresponding graphs are called B 1 ‐EPG graphs. We prove that any tree is a B 1 ‐EPG graph. Moreover, we give a structural property that enables one to generate non B 1 ‐EPG graphs. Furthermore, we characterize the representation of cliques and chordless 4‐cycles in B 1 ‐EPG graphs. We also prove that single bend paths on a grid have Strong Helly number 3. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

A graph $G=(V,E)$ is a chordal probe graph if its vertices can be partitioned into two sets, P (probes) and N (non-probes), where N is a stable set and such that G can be extended to a chordal graph by adding edges between non-probes. We give several characterizations of chordal probe graphs, first, in the case of a fixed given partition of the vertices into probes and non-probes, and second, in the more general case where no partition is given. In both of these cases, our results are obtained by introducing new classes, namely, N-triangulatable graphs and cycle-bicolorable graphs. We give polynomial time recognition algorithms for each class. N-triangulatable graphs have properties similar to chordal graphs, and we characterize them using graph separators and using a vertex elimination ordering. For cycle-bicolorable graphs, which are shown to be perfect, we prove that any cycle-bicoloring of a graph renders it N-triangulatable. The corresponding recognition complexity for chordal probe graphs, given a partition of the vertices into probes and non-probes, is $O(|P||E|)$, thus also providing an interesting tractable subcase of the chordal graph sandwich problem. If no partition is given in advance, the complexity of our recognition algorithm is $O(|E|^2)$.