AMP: A Better Multipath TCP for Data Center Networks

In recent years several multipath data transport mechanisms, such as MPTCP and XMP, have been introduced to effectively exploit the path diversity of data center networks (DCNs). However, these multipath schemes have not been widely deployed in DCNs. We argue that two key factors among others impeded their adoption: TCP incast and minimum window syndrome. First, these mechanisms are ill-suited for workloads with a many-to-one communication pattern, commonly found in DCNs, causing frequent TCP incast collapses. Second, the syndrome we discover for the first time, results in 2-5 times lower throughput for single-path flows than multipath flows, thus severely violating network fairness. To effectively tackle these problems, we propose AMP: an adaptive multipath congestion control mechanism that quickly detects the onset of these problems and transforms its multipath flow into a single-path flow. Once these problems disappear, AMP safely reverses this transformation and continues its data transmission via multiple paths. Our evaluation results under a diverse set of scenarios in a fat-tree topology with realistic workloads demonstrate that AMP is robust to the TCP incast problem and improves network fairness between multipath and single-path flows significantly with little performance loss.

In this paper we focus on striking a right balance between throughput and latency at transport layer. To that end, one seemingly natural way is to combine a multipath tranport protocol (e.g., MPTCP [35]) and a low-latency tranport protocol (e.g., DCTCP [5]) in that the former usually achieves a high throughput and the latter keeps switch buffer occupancy low by exploiting Explicit Congestion Notification (ECN). Thus, the crux of this idea is to maintain multiple subflows per connection using a multipath mechanism and each subflow runs a low-latency protocol such as DCTCP.
This makes sense because any single transport protocol is difficult to meet high-throughput and low-latency requirements. For example, Equal Cost Multi Path (ECMP) routing would be likely to cause collisons among long-lived DCTCP flows on the same link, which can degrade throughput substantially. In contrast, MPTCP is good at fast load-balancing, overcoming the shortcoming of ECMP. However, it tends to occupy switch buffers aggressively, thus hurting the performance of latencysensitive short flows.
We conduct such integration, which we call Data Center MultiPath (DCM, in short), and examine a similar existing approach called XMP [10]. We find that both schemes can provide fast load-balancing while keeping switch buffer occupancy low. However, two major challenges -TCP incast and minimum window syndromestill render these approaches less practical as a transport protocol for DCNs.
We carefully examine these problems when multipath schemes are in use ( §3). Multiple subflows in these MPTCP variants boost the possibility of TCP incast in a many-to-one communication pattern while for example senders and a receiver are co-located in a single rack. Worse, in that setting, network resource competition between ECN-capable multipath (e.g., DCM) and single-path (e.g., DCTCP) flows causes a serious co-existence problem, which we name minimum window syndrome. Surprisingly, the syndrome consistently makes multipath flows achieve 2-5× more throughput than single-path flows, thus severely violating fairness among the TCP flows. We find out that using both multiple subflows and small ECN marking threshold is behind the syndrome.
Finally we propose AMP, an adaptive multipath congestion control algorithm that is robust to the TCP incast problem and effectively handles the minimum window syndrome with little performance compromise on both throughput and latency. In addition to good fairness and high performance, we design AMP such that it is simple enough to keep its behavior traceable and its overheads low, and can shift traffic quickly from congested paths to less congested paths. AMP requires none of sophisticated mechanisms such as RTTdependent congestion window (cwnd) increase (in MPTCP) and dynamic cwnd decrease (in DCTCP).
AMP's approach is simple but effective: it simply transforms a multipath flow into a single-path flow at the onset of the problems. The key in AMP is the early detection of the problems. We leverage the fact that all subflows of a multipath flow have the smallest congestion window value, which is a good indicator that all of the subflows compete with other flows on a single link. If the minimum window state across all subflows remains for a small time period (e.g., 1-3 RTTs), AMP executes this transformation by deactivating all subflows but one. If AMP no longer receives ECN-marked packets for some time period (e.g., 8 RTTs), it reactivates all suspended subflows ( §4). Our evaluation shows that this neat technique substantially mitigates TCP incast and improve fairness without any side-effect ( §5.2).
AMP also simplifies congestion control operations, which keeps AMP easily traceable and its overheads low. AMP just increases only one window per RTT across all subflows, similar to the behavior of a singlepath TCP whereas the other schemes consider RTTs of all subflows to update their cwnd. In response to ECN signals, AMP cuts cwnd by a constant factor instead of dynamically adjusting it based on the fraction of marked packets ( §4.2). Our extensive evaluations in a large-scale fat-tree topology with realistic traffic matrix demonstrate that AMP under incast-like workloads works better than and in other workloads performs as well as the existing solutions, despite its simplicity ( §5.3).
Overall, this paper makes three main contributions: • To the best of our knowledge, we report for the first time that the minimum window syndrome can do exist when ECN-capable multipath and single-path TCPs are deployed in data centers. We carefully examine its root cause. • We propose AMP 1 , an adaptive multipath TCP for data center networks that effectively copes with the TCP incast and minimum window syndrome. AMP is resilient against the incast problem and ensures graceful co-existence with single-path TCP flows. • We evaluate AMP over a wide variety of realistic scenarios in a large-scale fat-tree topology, and demonstrate that AMP significantly mitigates buffer infla-tion and achieves higher fairness and comparable performance against existing multipath protocols.

PRELIMINARY
In this section we review two multipath mechanisms to facilitate our later discussions: (1) DCM, a new extension of MPTCP that combines the congestion control of MPTCP and DCTCP together; and (2) XMP, an existing proposal.

DCM
An intuitive and reasonable approach is to combine MPTCP and DCTCP. The main idea is to enable each subflow of MPTCP with the ECN response mechanism of DCTCP. On top of the basic MPTCP algorithm, which swiftly shifts traffic from highly congested to less congested paths, DCM handles ECN-marked packets similar to DCTCP for each subflow. That is, each subflow of DCM adjusts its sending rate in proportion to the extent of congestion, represented by the amount of ECN-marked packets. For instance, when a subflow rapidly reduces its cwnd due to receiving a large amount of ECN-marked packets over a few windows of data, DCM moves the traffic from that subflow to other subflows with better network condition (e.g. with larger cwnd and low RTT). In this way, each subflow of DCM follows DCTCP to reduce its cwnd and MPTCP to increase its cwnd. The DCM does, in short: • For each ACK on subflow s, w s ← w s +min( a w total , 1 ws ) • For each loss, w s ← ws 2 • For first marked ACK in a window, w s ← w s (1 − αs 2 ) w s is a cwnd size of subflow s, w total is r w r for all r and a controls the aggressiveness of cwnd increase across all subflows. The following formula calculates the value of a: a = w total max r (w r /rtt 2 r ) ( r (w r /rtt r )) 2 (1) Here max r is the maximum value across all subflows. For instance, when an MPTCP flow encounters a path with high RTT and low packet drop probability, it increases its aggressiveness to fully utilize that path. The aggressiveness is also capped by 1 ws to prevent a subflow to increase its cwnd more than one segment per RTT, ensuring that a subflow, and in turn, the MPTCP flow, is not harming other competing (possibly, single-path) flows. α s is an estimate of the fraction of marked packets on subflow s and is updated once per window of data (roughly an RTT) as follows: F s is the fraction of marked packets (in the last window of data) on subflow s; g is a (constant) weight coefficient for exponentially averaging α s . When α s → 0, ToR switch ... D S1 S2 S3 Sn S1 S2 S3 Sn Figure 1: A many-to-one communication scenario over a 10Gbps bottleneck link. w s decreases gently; as α s → 1, w s does more aggressively.

XMP
XMP is another multipath congestion control algorithm that aims to strike a balance between latencythroughput trade-offs. XMP combines an ECN-based scheme for controlling the buffer occupancy in switches and a rate-based congestion control algorithm for balancing traffic among its subflows. The XMP does, in short: • Every window of data on subflow s, w s ← w s + δ s • For each loss, w s ← ws 2 • For first marked ACK in a window, w s ← w s (1 − 1 β ) δ s dictates the amount of cwnd increase for each subflow, calculated once per window of data; and β is a fixed reduction factor (set to 4 in [10]). The value for δ s is calculated by the following formula: XMP is in principle similar to MPTCP and DCM, but there are differences, too. One of them is that in XMP, network congestion is signaled via packet queuing delay (inferred through RTT) and ECN-marked packets.

ISSUES OF MPTCP VARIANTS
MPTCP and its ECN-capable variants have not been widely deployed in DCNs. While there may be several other reasons, we identify two key technical issues. First, the ECN-capable MPTCP variants (DCM and XMP) are unable to handle incast-like traffic; many applications (MapReduce [13], Partition/Aggregate [5], etc.) have a many-to-one communication pattern that is prevailing in DCNs. Second, the ECN-capable MPTCP variants fail to gracefully coexist with an ECN-capable single-path TCP such as DCTCP; an MPTCP variant can hurt DCTCP flows' throughput significantly. We call this problem the minimum window syndrome. In what follows, we demonstrate the impact of these two problems via simulation under a simple topology shown in Figure 1.  Figure 2: Impact of the TCP incast on different multipath protocols (DCM and XMP) and DCTCP. DCM and XMP use four subflows per connection. File size is 128KB, link capacity is 10Gbps, and switch buffer size is 100 packets. The y-axis is log-scaled.

TCP incast
TCP incast can happen in applications which have barrier-synchronized workload and a high fan-in communication pattern. A unique characteristic of the barriersynchronized workload is that traffic of multiple TCP flows to the same destination arrives in a bursty fashion at a bottleneck switch, which has a shallow buffer. This causes bursty packet losses and eventually triggers expensive timeout at TCP senders, which substantially delays the completion of a job [5].
TCP incast is a well-studied topic [5,42] and for instance DCTCP mitigates the problem using ECN. Unfortunately, the ECN-capable MPTCP variants are still susceptible to the TCP incast even in the help of ECN. To demonstrate that, we create a simulation environment as shown in Figure 1 using NS-3 [1]. The simulation setup is as follows. Every 1 second k number of multipath flows join to a bottleneck link with a fixed interval of 50µs where k = 10, 20, 30, 40 while setting the flow size to 128KB. Each simulation lasts for 20 sec. Each multipath flow has 4 subflows. In the setup, we test DCM and XMP. We also separately run DCTCP as baseline. Figure 2 shows that DCTCP overall outperforms DCM and XMP. In many cases the average flow completion time (FCT) of DCTCP is almost 1-2 orders of magnitude shorter than that of DCM and XMP; when k = 30, the average FCT of DCTCP is about 2ms whereas that of DCM and XMP is over 800ms. Furthermore, the FCT distribution of DCTCP has a narrow standard deviation (i.e., the whisker bar in the graph), but the standard deviation of XMP and DCM is large (less than 1 millisecond for DCTCP vs. above 1 second for DCM and XMP). This means that the other schemes have a long-tailed FCT distribution and make some flows experience much higher FCTs (due to retransmission timeouts).
From these results, it is evident that the multipath variants cannot handle the TCP incast problem. The reason is somewhat obvious. The MPTCP variants maintain 4 subflows. Hence, one multipath flow generates at least 4 packets per RTT. More number of multipath flows implies a sharp increase of the probability of burst packet losses. For example, every RTT 30 multipath flows shown in Figure 2 generate at least 120 packets, which are far exceeding the queue length (i.e., 100 packets in this case) of the bottleneck switch. Without giving up the benefit of a multipath protocol, a (practical and possibly natural) way to deal with this problem may be allowing both multipath and single-path protocols and letting them share the DCN fabric. The basic idea is to permit DCTCP for latencysensitive applications and multipath protocols for bandwidthhungry services. However, keeping graceful co-existence of these two different protocols turns out to be challenging, which we discuss next.

Minimum window syndrome
In the presence of ECN-capable multipath (e.g., DCM and XMP) and single-path TCP flows (e.g., DCTCP), serious unfairness between them can occur. The key characteristic of this problem is that when all the subflows of DCM or XMP flows compete with DCTCP flows on the same bottleneck link, DCTCP flows obtain 2-5 times less amount of bandwidth and higher queueing delay than they should. We call this co-existence problem the minimum window syndrome.
Triggering the syndrome. We discuss when the syndrome can occur through examples shown in Figure 3. We assume that network switches ECN-mark packets only if their instant queue length is larger than a marking threshold K. Such switches are widely deployed in data centers. To keep the discussion simple, let us assume K = 4 and zero propagation delay. That is, as soon as packet leaves the queue, sender can send a new packet as it receives acknowledgment instantly.
In Figure 3(a), two single-path flows share the bottleneck link fairly by generating on average two packets per RTT (bounded by queuing delay); in other words, cwnd in each flow oscillates between 1-3 packets. Now suppose that 5 single-path flows compete with each other as illustrated in Figure 3(b). Because K = 4, a new arriving packet finds the queue length is always equal to K, meaning that it is the 5th packet in the queue. Thus, all packets across flows are ECN-marked all the time, and each flow is forced to reduce its cwnd to one packet. Even though there is no way to further reduce cwnd (as it is one packet), the number of packets arriving at the queue always exceeds K. This causes persistent buffer inflation (also discussed in [6]), but there is no unfairness across flows.
Finally, Figure 3(c) illustrates a case where the singlepath flow in S 5 is replaced with one multipath flow having four subflows. Similar to the previous case, all packets across flows are ECN-marked. Even if the cwnd of the single-path flows and all subflows reduces to one packet, the number of packets in flight far exceeds K all the time. However, since all the subflows belong to one multipath flow, the flow ends up sending four times more packets than single-path ones. Furthermore, the syndrome substantially escalates the likelihood and impact of the persistent buffer inflation (see the buffer length twice as large as K in Figure 3(c)), which can potentially harm latency-sensitive short flows.
Conditions for the syndrome. In reality, BDP needs to be considered and is a few tens of packets in DCNs [10,43]. Thus, to create the syndrome, more than (BDP + K) number of flows are necessary. However, the MPTCP variants set minimum congestion window size (cwnd min )an internal constant that governs the minimum number of packets a sender can send regardless of congestion level-to two packets 2 . Thus, the number of flows including single-path flows and subflows in multipath flows should be larger than (BDP + K)/cwnd min .
Demonstration of the syndrome. Now suppose a setup in Figure 1 where an ECN-enabled switch connects n sending servers and one receiving server. The receiver is equipped with DCTCP, DCM and XMP; server  S 1 runs DCM (or XMP) having r subflows, and the remaining n − 1 servers with DCTCP (n ≥ 2). Those n senders send traffic to the receiver. We do various simulations by varying parameters and study the impacts of the syndrome. We change the simulation duration from 10ms to 1 sec, use 1Gbps and 10Gbps link and test both DCM and XMP. Across these variations, we observe a very similar trend. Thus we only show the results of the 1 sec duration over 10Gbps link using XMP in interest of space. We depict a setting as (K, r) where K is the ECN marking threshold and r is the number of subflows.
Varying number of subflows: Given 8 DCTCP flows and one DCM or XMP flow, we vary the number of subflows from 2 to 8, while setting K = 10 and cwnd min = 2 as suggested in [10]; thus, the setting is (10, {2 . . . 8}). Figure 4(a) shows that the syndrome begins as soon as the DCM or XMP flow starts to use three subflows or more. When four subflows are used, the XMP flow obtains 2.3× higher goodput than DCTCP flows. The figure clearly demonstrates that the number of subfows is a key factor that triggers the problem. DCTCP flows seem to have no problem in the 2-subflow case. However, the problem recurs when at least about 16 DCTCP flows are in use (not shown for brevity). Worse, using two subflows costs about 10% goodput loss (e.g., 1Gbps out of 10Gbps rate) when compared to using four subflows [10]. Also, a number of subflows (e.g., 8 subflows) are in general beneficial when there exist lots of paral-lel paths in a large DCN [35]. Thus, using a smaller number of subflows is not a fundamental solution.
Different marking threshold: As a small marking threshold can be a potential cause of the problem, increasing K may be useful. However, this can also introduce an additional delay, which might hurt the flow completion time of latency-sensitive short flows. Nevertheless, we test K = 20. With the setting (20, 4), we vary the number of DCTCP flows. Figure 4(b) shows that increasing the marking threshold marginally alleviates the problem; given 8 DCTCP flows, a goodput gap between DCTCP and DCM or XMP is a factor of two. In contrast, recall that the gap is a factor of 2.3 under the same condition in Figure 4(a). We also tested a case where cwnd min = 1 while keeping the setting as (10,4). This reduced the likelihood of the syndrome, but we observed that a slight increase of the number of DCM or XMP flows (from 1 to 4) triggered the syndrome, when 8 DCTCP flows are given (the exact graph is omitted). Summary. We obtain two key findings from these results. First, the condition that triggers the minimum window syndrome is relatively simple: the total number of packets in flight from both multipath and singlepath flows should exceed BDP plus K frequently. In our setup, BDP is 20 packets. In Figure 4(a), the condition begins to hold when the setting has 3-4 subflows for the XMP flow and 8 DCTCP flows (the average number of packets in flight is about 30-32). Second, tweaking those parameters either alleviates the problem marginally or makes performance loss inevitable.

DESIGN
We propose AMP, a multipath congestion control mechanism that coexists well with ECN-capable singlepath TCPs and is resilient against TCP incast. In designing AMP, in addition to the obvious objectiveshigh throughput and low latency, we have the following design objectives: • Good fairness: Multipath and single-path TCP flows should be able to achieve their fair share of bandwidth at a bottleneck link, even in the presence of an incast-like traffic pattern.
• Fast traffic shifting: Multipath flows should be able to avoid congested paths quickly. This especially helps latency-sensitive short single-path TCP flows experience less impact due to congestion.
• Simplicity: An algorithm should be kept as simple as possible so that its behaviors are easily analyzed and its overheads are kept low.
To achieve the above objectives, we deliberately test existing solutions: DCM and XMP. In analyzing them, we make several key observations essential for our design.

Key observations
(1) The number of subflows for a multipath flow should not be static. Multiple subflows are in general beneficial to obtain high throughput. On the contrary, in the presence of the TCP incast and minimum window syndrome, it is effective to have a smaller number of subflows (ideally, one subflow), as discussed in §3. However this costs throughput performance. Thus having the static number of subflows can only achieve either good fairness against single-path flows or high throughput, but not both of them. Thus, the number of subflows should be adjusted adaptively, which can be done by (de)activating subflows in an online fashion. However, it is inappropriate to deactivate subflows incrementally because mitigating the two problems can take too long, which may cause significant queuing delay to latency-sensitive short flows over a longer period of time.
(2) The cwnd values in subflows are a cue for the TCP incast and syndrome. Detecting these problems early is key to adjusting the number of subflows. We notice that when these problems are about to occur, subflows are in a unique status where the cwnd values across all subflows are always equal to a minimum (e.g., two packets in [10,35]). This is a good indicator that these problems are in effect because it is unlikely that all subflows of a multipath flow passing through different paths face excessive congestion, especially in a large-scale data center that has 100s of parallel paths between a pair of source and destination.
(3) Adaptive cutback of cwnd at subflow slows down traffic shifting. One of differences between DCM and XMP is the response mechanism to ECNmarked packets. In DCM a subflow cuts its cwnd in proportion to the fraction of marked packets over a window (see Eq. (2)); whereas in XMP a subflow decreases its window by a constant factor β (see §2.2). To understand the effect of this difference, we modify MPTCP to reduce the cwnd of subflow by a constant factor (we use β = 4) when it sees ECN-marked packets and examine traffic shifting times for MPTCP with β = 4 and DCM. Given a topology shown in Figure 5, a multipath flow (DCM or MPTCP) with two subflows begins to traverse from S 2 to D 2 at 0s. Then, S 3 sends traffic to D 3 using DCTCP within interval (1s, 2s) and another DCTCP flow from S 1 to D 1 for (2s, 3s). At 2s, a multipath flow is sending its entire traffic through the upper path and we plot how cwnd of each subflow varies within interval (1.999s, 2.01s) after the second DCTCP flow appears on the upper path. Figure 6 shows that MPTCP finishes traffic shifting about 4ms faster than DCM.
The reason is because a DCTCP subflow in DCM conservatively reduces cwnd based on the fraction of marked packets. Hence, even if there exists a congestion-free path, a DCM flow shifts its traffic slowly. In contrast, with a constant factor (e.g., β = 4), MPTCP is aggressive enough to make a subflow on the congested path quickly reduce its window, thereby achieving faster traffic shifting than DCM. This conservative nature of DCTCP perfectly makes sense if a flow traverses one path only. However, because the subflows of a multipath flow travel through multiple different paths in general, it is more appropriate to get rid of traffic from the congested path rather than to withstand against congestion.
(4) RTT measurements of subflows are unnecessary for updating their cwnd. Interestingly, both DCM and XMP rely on RTT measurements in increasing cwnd of subflows. DCM inherits MPTCP's design principles, one of which targets to address the RTT mismatch issue [41] that can occur when there are paths with high RTT and low loss probability and paths with low RTT and high loss probability. However, higher RTT typically means large queuing delay and hence high loss probability in DCNs because DCNs usually have a symmetrical structure where all paths between a pair of servers have the same length. Thus, DCNs have no paths that cause the RTT mismatch problem.
Moreover, ECN tends to equalize RTTs throughout the data center network when network switches react to instant queue length with a small ECN marking threshold [5,10]. Assuming 5-hop paths with 10Gbps links, 10 packets of marking threshold and 1500B packets, a maximum RTT difference is just about 108µs. In average cases, as the utilization of network links increases, the RTT difference will become even smaller. Thus, differentiating the sending rate of each subflow based on such a small RTT difference would not bring much benefit. Even in a case that a path is highly congested, sources can quickly identify it with ECN signals and do traffic shifting accordingly.

AMP algorithm
We now discuss the exact algorithm of AMP designed with the above four observations. AMP mainly consists of three components: (i) subflow suppression/release, (ii) constant factor decrease of congestion window, and (iii) RTT-agnostic congestion window increase.
The subflow suppression/release is a key mechanism that ensures graceful coexistence between multipath and single-path flows. The second component enables fast traffic shifting. The final part, as its name suggests, excludes RTT measurements, without any performance penalty, from the part of increasing cwnd, which overall makes our algorithm simple. Algorithm 1 shows the pseudocode of AMP, that we explain next in detail.
Subflow suppression/release (SSR). The SSR mechanism permits detection of cases where all subflows belonging to an AMP flow struggle at the same bottleneck link due to congestion. A representative example is a many-to-one communication pattern (e.g., incast) where multiple flows (and subflows) compete for bandwidth at a last mile hop (i.e., ToR switch). Upon detection, AMP transforms its flow to a single-path flow. Once congestion disappears, AMP converts its flow from a single-path flow to a multipath one.
Subflow suppression consists of two steps: detection and suppression. (1) At detection step, AMP checks whether the cwnd of all its subflows has been equal to a minimum window size for γ number of consecutive RTTs (lines 3-9 in Algorithm 1). (2) At suppression step, if the previous detection condition is met, AMP deactivates all its subflows except for the initial one by resetting active flag (lines [11][12][13].
Overall, while it is a simple heuristic, SSR ensures fairness between multipath and single-path flows at a shared bottleneck link. It also helps to accommodate more senders during an incast-like episode or to reduce the chance of costly timeouts. We demonstrate SSR's efficacy in §5.2.
RTT-agnostic congestion window increase. As discussed in §4.1, employing an ECN-based congestion control tends to equalize RTTs in DCNs. The difference in RTTs for paths is at most K packets where K is a small marking threshold at switches (say, 10 packets). In addition, the RTT mismatch problem does not exist in DCNs, either. Based on these insights, for each nonduplicate ACK of subflow, we simply increase its cwnd by 1/w total (line 25 in Algorithm 1) where w total is the total window size across all subflows. This ensures that AMP can only increase one segment per RTT across all subflows, preserving network fairness with single-path flows at bottleneck links [24,41].
The amount of cwnd increase of AMP also strikes a right balance. Given an congestion control algorithm C, let the amount of cwnd increase of a subflow per ACK be C inc . For instance, the amount, 1/w total , is AMP inc .
cwnd increase Response to ECN SSR AMP w s + 1/w total w s (1 − 1/β) DCM w s + min( a w total , 1 ws ) w s (1 − α s /2) a as in Eq. (1) α s as in Eq. (2) XMP w s + δ s w s (1 − 1/β) δ s as in Eq. (3) Table 1: Summary on AMP, DCM and XMP. Now suppose RTT difference among all subflows is negligible. Then, Eq. (1) for DCM reduces to a ≈ w max /w total where w max is the maximum window size across all subflows. The increasing amount per ACK is then about w max /(w total ) 2 which we call DCM inc . In case of XMP, Eq. (3) reduces to δ s ≈ w s /w total . Note that δ s is the amount of cwnd increase per RTT in XMP. Since w s is the current window size of subflow s, the subflow would receive w s number of ACKs. Thus, for every ACK, XMP increases cwnd of a subflow by 1/w total , which is XMP inc . Putting it together, we have Note that if w max approaches w total , DCM inc ≈ AMP inc . Looking at these relationships among three algorithms, the increment is comparable across all of them, but AMP's algorithm is much simpler than the other two.

Constant factor decrease of congestion window.
In AMP a subflow responds to ECN signals once every window of data (i.e., approximately an RTT) by reducing its cwnd with a constant factor β, as depicted at line 29 of Algorithm 1. The parameter β should be determined such that a link is fully utilized. In other words, a queue should not be completely drained due to cwnd reduction. In [10], this problem of choosing β is formulated as follows: Note β ≥ 2; otherwise, it reduces cwnd more aggressively than a standard TCP. We choose β using this formula. For instance, consider a DCN where each link has 1Gbps speed and RTT is about 250µs [5] (i.e., BDP is about 20 packets). If we set K = 10, β ≥ 3. Since computing BDP even for other link speed (e.g., 10Gbps) is easy, it is straightforward to set β after K is first determined.
Summary. Table 1 highlights key mechanisms of AMP, DCM and XMP. From the table, we see that AMP is much simpler than other solutions, easing the tuning of AMP. A key differentiator is the subflow suppression/release mechanism that mitigates the TCP incast and minimum window syndrome.

EVALUATION
In this section we evaluate AMP via extensive simulations using NS-3. For comparison, we use DCTCP, DCM and XMP 3 . We first study how to tune the parameters of AMP. We then examine AMP under a few basic scenarios. In particular, we will answer robustness of AMP against the TCP incast, its effectiveness to the minimum window syndrome, and its speed in traffic shifting. We finally study the overall performance of AMP under a large-scale fat-tree topology that represents a realistic data center network.
Basic configuration. Throughout our simulations, the following parameters are used without any change: (i) a link rate of 10Gbps, (ii) a link delay of 2µs, (iii) an MSS of 1400 bytes, (iv) a maximum queue size of 100 packets, and (v) β = 4 for AMP and XMP. We also tested AMP over 1Gbps settings and observed that the trends were similar to those of 10Gbps settings. We only show the results under the 10Gbps settings in interest of space.
We set a default value for each of the following parameters: (i) the number of subflows per multipath flow = 4, (ii) the minimum congestion window size, cwnd min = 2 packets, and (iii) the ECN marking threshold, K = 10 packets. When necessary (e.g., for further analysis), we change their values.
Evaluation metrics. We have four key metrics: Jain's fairness index [22], goodput, flow completion time (FCT) and job completion time (JCT). We define JCT as a time period until all flows in a job finish their transmission from its beginning.

Parameter tuning
The subflow suppression/release (SSR) mechanism has two parameters: γ to begin the subflow suppression process and τ to finish it. We empirically determine γ and τ .
First, setting γ is relatively easy; we test different γ values (1-10 RTTs) in the presence and absence of the TCP incast and minimum window syndrome. If there indeed exist the two problems in the network, it is im- The y-axis is log-scaled.
portant to begin the suppression process early enough to alleviate their impact quickly. When γ ≥ 3 (in RTTs), AMP reacts these problems slowly. For instance, under the same setting for the TCP incast shown in Figure 2, average FCT of AMP, when γ = 3, is an order of magnitude higher than that of DCTCP. When γ = 1, there is a chance of false alarm. We find AMP performs best when γ = 2, which we use by default. Second, setting τ (i.e., the exit threshold) should be more cautious. The risk involved in selecting τ is oscillation. If τ is too small, AMP will repeatedly begin and end the suppression process. The frequent oscillation may be synchronized across AMP flows, which subsequently causes faster queue build-up due to traffic bursts when all suspended subflows across flows are reactivated simultaneously. This may make all incoming packets ECN-marked, which in turn leads to the repetition of the whole suppression process by suspending all subflows.
To find a suitable value for τ , we conduct simulations while varying τ and using 3-5 AMP flows under the topology shown in Figure 1. Figure 7 depicts how many suppression episodes happen across different τ values and the number of flows. Ideally, there must be only one episode. However, when τ < 6, there are more than one episode; moreover, the count of episodes varies a lot when the number of AMP flows is different. When τ ≥ 6, the SSR mechanism becomes stable (meaning that there is only one episode), and the median queue length is just about 10 packets. Therefore, we set τ = 8 as default (to be conservative).

Microbenchmarking
Robustness against the TCP incast. Multipath congestion control mechanisms usually work poorly when they are used for traffic that is short-lived and has a high fan-in pattern (e.g., TCP incast). To understand how well AMP tolerates such a traffic pattern, we use the same simulation setup used in §3.1. That is, there is no mix of single-path and multipath flows; we use multipath protocols only to transfer high fan-in short-lived traffic. This time we vary file size from 128KB to 1MB. DCTCP is used again as baseline.
AMP is as good as DCTCP apart from a case of 40 flows, in which AMP performs slightly worse than DCTCP (Figure 8). However, AMP outperforms XMP and DCM; in most cases the average FCT of AMP is almost 1-2 orders of magnitude shorter than that of XMP and DCM. For instance, Figure 8(a) shows that when the number of flows is 30 and flow size is 128KB, the FCT of AMP is about 2ms and that of XMP and DCM is over 800ms. In addition, AMP has a narrow standard deviation in its FCT distribution, but XMP and DCM have a large standard deviation (1-2ms for AMP vs. 1 second for XMP and DCM). This confirms that AMP presents a stable FCT performance even under various TCP incast scenarios. Note that the y-axis of the graph is presented in log scale.
The SSR mechanism in AMP mitigates the possibility of buffer overflow significantly, thus that of the expensive TCP timeout. When the number of flows is 30 in Figure 8(a), we observe that AMP has no timeout during the simulation whereas XMP and DCM face up to 10 and 16 timeouts respectively (with 7 timeouts at 90th percentile for both schemes). Notably, when flow size is smaller than 128KB (e.g., 64KB), all multipath schemes work as well as DCTCP and there is little difference among the three multipath approaches; even the SSR mechanism is not triggered at all as the flow size is too small. Thus, if the flow size is at least as large as 128KB, our approach would work better than others as we observe a similar trend for a flow size of 1MB (graph omitted).
Effectiveness to the minimum window syndrome. We use the topology shown in Figure 1 and test the impact of the syndrome on different schemes while varying the number of DCTCP flows and multipath flows. All flows arrive at 0 sec and end at 1 sec. Figure 9 shows that in almost all cases AMP outperforms the other two schemes. As the number of multipath flows increases, we find the syndrome aggravates fairness even in the presence of a small number of DCTCP flows (cf., two cases of 4 DCTCP flows between Figures 9(a) and 9(c)). Note that the syndrome itself is weak in some cases (e.g., given less than 8 flows in Figure 9(a) and 4 flows in Figure 9(b)); thus marginal difference in fairness is observed among the three schemes.
Since the syndrome causes persistent buffer inflation, we examine queue length. From Figure 10, we make two observations. When there is no syndrome (Figure 10(a)), the queue length distributions across AMP, XMP and DCM are similar. On the other hand, when 4 DCM and XMP flows are used (Figure 10(b)), the queue length is more than 20 packets (100% inflation at median) all the time. On the contrary, the queue length difference of AMP is just about 2 packets (at median, 10 packets in Figure 10(a) and 12 packets in Figure 10(b)). If the intensity of the syndrome grows, the queue length will become more inflated accordingly. In general AMP can mitigate the persistent buffer inflation better than other schemes even if the syndrome is more intensive.
The SSR mechanism is key to high performance in both fairness and delay. When we disable SSR, all three approaches present equally poor performance.
Traffic shifting speed. We now evaluate how quickly AMP shifts traffic. We run the same simulation done in §4.1 under the setup in Figure 5. Recall that DCM's traffic shifting time is about 7ms. Figure 11 shows that both AMP and XMP achieve similar traffic shifting time (about 3ms), reassuring DCTCP's slowness in shifting traffic and suggesting that a fixed amount of congestion window reduction to ECN signals is suitable for multipath congestion control mechanisms.

Large-scale simulation
We now study the overall performance of AMP with different workloads in a realistic data center setup. As many data center networks employ a multi-rooted tree topology [2,17,36], we use a 3-tier fat-tree topology that has 128 servers, 32 ToR, 32 aggregate and 16 core switches. ECMP routing is employed to select a path on a per-flow basis.
Incast with background traffic. We aim to examine the performance of a high fan-in workload (i.e., incast traffic) in the presence of background traffic. Specifically, we use DCTCP to generate the incast traffic and a multipath protocol for the background traffic. Note that this scenario is different from one in §5.2 where a multipath protocol is used to transfer the incast traffic.
Setting: We consider a scenario where a client makes parallel reads in a cluster filesystem in the presence of background traffic. We model this as a unit of job: a client sends a 2KB request to 10 servers, each of which in turn sends back a 64KB block of response data to the client. One job ends after receiving all blocks. Thereafter a new job begins. There are 8 parallel jobs, and clients and servers in each job are randomly selected.  Each host sends a long flow to a randomly selected host to generate traffic on background. The flow size is determined by a Pareto distribution with shape parameter of 1.5 and mean of 192MB. Once a long flow ends, a new one begins immediately. A simulation continues until 1000 long flows are completed. Results: Figure 12 presents job completion times of short DCTCP flows. Notice from the figure that a key in the legend is the protocol name used for long flows. We plot, as a baseline, the case where DCTCP is also used for long flows. Overall, we make two observations. First, AMP does not harm short DCTCP flows even if multipath flows use as many as 8 subflows. The results in Figure 12 show that the AMP case (i.e., AMP is used for long flows) obtains slightly better JCT performance than the baseline case across all scenarios.
Second, more number of subflows in DCM or XMP makes the JCT of short DCTCP flows grow quickly. When XMP is used for long flows, the 90th percentile JCT is 1.2ms in the 4-subflow case (Figure 12(a)), 1.5ms in the 6-subflow case (Figure 12(b)), and 1.8ms in the 8-subflow case (Figure 12(c)). In contrast, the 90th percentile JCT is 1.1ms in case where AMP even has 8 subflows, thus reducing JCT by 0.6ms (39% improvement) compared to the corresponding XMP case.
Summary: From the above observations, we conclude that our SSR mechanism reduces buffer inflation effec-tively and hence makes competing short DCTCP flows finish faster. While we recommend 4 subflows per multipath flow, AMP may safely support up to 8 subflows.
General workload. We now study interaction between short and long flows. Our goal here is to confirm that, despite its simplicity, AMP works as well as other schemes and its SSR mechanism brings no harm.
Setting: 50% of the servers run long flows, and the remaining servers generate short flows scheduled by a Poisson flow arrival with rate λ = 256 flows/s. Those long flows last for 10 sec to increase chance of saturating the network. The size for short flow is chosen between 1KB and 1MB at uniformly random. We only present results of cases where short flows use DCTCP and long flows use a multipath protocol because other combinations (e.g., DCTCP for long flows and a multipath protocol for short flows) that we tested make no significant difference in performance compared to a base case where both short and long flows use DCTCP only.
We use permutation traffic matrix that has been used in many previous works [3,10,35,12,16,26]. Specifically, a host establishes at most two connections: one for receiving traffic and the other for sending traffic. For sending traffic, the host chooses its receiver at random.
Results: Figure 13(a) shows the FCT results of different schemes. A key in the legend denotes a protocol used for long flows. We observe that short DCTCP  Figure 14: The FCT of short DCTCP flows with data mining workload used in pFabric [7]. If a flow size < 100KB, the flow is short; otherwise, it is considered long. The short and long flows coexist. A key in the legend denotes a protocol used for long flows.
flows achieve the best FCT result when AMP and XMP are used for long flows. The worst FCT performance was observed when DCTCP is used for long flows because DCTCP suffers from poor ECMP load-balancing.
In case of long DCM flows, DCTCP flows work reasonably well and about 10% of the short DCTCP flows obtain longer FCTs than DCTCP flows competing with long AMP flows. This is because DCM's traffic shifting is slower than that of AMP, thus causing a high queuing delay.
The long flows of AMP and XMP show little difference in goodput. Interestingly, DCM achieves the best performance, which is because it trades (queuing) delay for goodput. Again, using DCTCP for long flows yields the worst goodput performance due to the same reason in the FCT case. Figure 13(c) shows the mean network utilization at all layers of the fat-tree topology. As expected, the multipath schemes perform equally well because they balance their load among multiple paths.
We also examine those schemes in a fat-tree topology with 128 servers using a realistic data mining workload [7] and under an intensive condition that an average inter-flow arrival time in each server is about 780µs. Figure 14 depicts the FCT of short DCTCP flows when another type of protocol is used for long flows. When AMP is used for long flows, the 90th percentile FCT of short DCTCP flows is 0.18ms, but the corresponding FCT for XMP and DCM is 0.27ms and 0.28ms respectively (∼55% improvement over the two schemes). We observe a similar level of improvement at the 99th percentile: 0.78ms for AMP, 1.35ms for XMP and 1.41ms for DCM. Note that the goodput distribution of long flows across all schemes is almost identical (graph omitted).
Summary: Our results suggest that ECN alone can signal network congestion fast enough for multipath congestion control and considering RTT as part of an ECNbased multipath congestion control brings little benefit in the current setting of DCNs. The results also confirm that a fixed amount of congestion window reduction to ECN signals enables faster traffic shifting than adjusting the window dynamically. Thus AMP is light and as good as other solutions.

RELATED WORK
Pathological congestion events. TCP incast [39] and TCP outcast [34] are well-known pathological TCP problems in DCNs. The TCP incast is a congestion collapse incident for TCP flows that belong to barriersynchronized workloads with a high fan-in traffic pattern. A bursty packet arrival overflows shallow switch buffer, leading to expensive TCP timeouts. In contrast, in the TCP outcast, when a few flows from one input port compete for an output port with many flows from another input port, the few flows are penalized more severely. These problems are fundamentally different from the minimum window syndrome studied in this work. While those problems require switch buffer overflow, the syndrome does not; but it results in severe unfairness between ECN-capable single-path and multipath TCP flows.
Multipath congestion control. A transport layer protocol that exploits multiple paths between source and destination has been an active area of research [20,44,21,35,10,25,14]. MPTCP [35] divides a TCP flow into multiple subflows. Since those subflows may take different paths, MPTCP shifts traffic between its subflows to avoid congested paths. XMP [10] is similar to MPTCP, but it leverages ECN to maintain low buffer occupancy. MMPTCP [26] uses a packet scattering technique to improve delay performance of short flows while it acts as a regular MPTCP for long flows. Unfortunately, these schemes fail to handle TCP incast and minimum window syndrome. On the contrary, AMP is simpler and handles those problems better than these schemes.
ECN-based congestion control. In data centers, many ECN-based proposals adopt instant queue length based ECN. As one of the earlier works in this category, DCTCP [5] reacts to the extent of congestion estimated from the fraction of marked packets. D2TCP [38] and L2DCT [32] build upon DCTCP; D2TCP focuses on decreasing the likelihood of missed deadlines for TCP flows, and L2DCT aims to reduce FCT for short flows. ECN* [43] proposes dequeue marking to improve the performance of both short and long flows. Since a small threshold is used in all of these schemes, they can be prone to the minimum window syndrome when ECNcapable multipath protocols are deployed together.
Delay-based congestion control. Delay-based congestion control mechanisms had continuous attention in the past for the Internet [9,37,40] and wireless networks [29,15]. Lately, refreshed interest in those mechanisms has grown in the context of DCNs [27,30]. DX [27] and TIMELY [30] measure queuing delays at the microsecond granularity, and use the measurements to keep buffer occupancy low. These approaches are single-path protocols; they may suffer from poor loadbalancing of ECMP as DCTCP does. Thus, it would be of interest to extend AMP for delay-based schemes. Scheduling, prioritization and load balancing. A large body of work focuses on scheduling and prioritization [7,33,31,16,8,18], or load balancing [4,19] to support low latency in DCNs. For scheduling and prioritization, some rely on priority queuing with multiple queues [8,18]; others conduct decentralized [7,16] or centralized scheduling [33]; one combines different strategies adopted in prior works [31]. Load balancing schemes [4,19] break a flow down into small groups of packets, which are in turn distributed across multiple paths. In general, these approaches may be useful to mitigate the TCP incast and minimum window syndrome.

CONCLUSION
In this paper we presented that existing multipath congestion control mechanisms fail to handle (1) the TCP incast problem that causes temporal switch buffer overflow due to synchronized traffic arrival; and (2) the minimum window syndrome that causes persistent buffer inflation and serious unfairness. To overcome the limitation of the existing solutions, we proposed AMP that adaptively switches its operation between a multiple-subflow mode and single-subflow mode. Our extensive evaluation results showed that AMP is simple yet effective to those problems and in general works well, which makes deploying AMP in data centers attractive.


extfieldsofstudy:
Computer Science
Mathematics

text:
Few-Shot Learning with Graph Neural Networks

We propose to study the problem of few-shot learning with the prism of inference on a partially observed graphical model, constructed from a collection of input images whose label can be either observed or not. By assimilating generic message-passing inference algorithms with their neural-network counterparts, we define a graph neural network architecture that generalizes several of the recently proposed few-shot learning models. Besides providing improved numerical performance, our framework is easily extended to variants of few-shot learning, such as semi-supervised or active learning, demonstrating the ability of graph-based models to operate well on 'relational' tasks.

INTRODUCTION
Supervised end-to-end learning has been extremely successful in computer vision, speech, or machine translation tasks, thanks to improvements in optimization technology, larger datasets and streamlined designs of deep convolutional or recurrent architectures. Despite these successes, this learning setup does not cover many aspects where learning is nonetheless possible and desirable.
One such instance is the ability to learn from few examples, in the so-called few-shot learning tasks. Rather than relying on regularization to compensate for the lack of data, researchers have explored ways to leverage a distribution of similar tasks, inspired by human learning Lake et al. (2015). This defines a new supervised learning setup (also called 'meta-learning') in which the input-output pairs are no longer given by iid samples of images and their associated labels, but by iid samples of collections of images and their associated label similarity.
A recent and highly-successful research program has exploited this meta-learning paradigm on the few-shot image classification task Lake et al. (2015); Koch et al. (2015); Vinyals et al. (2016); Mishra et al. (2017); Snell et al. (2017). In essence, these works learn a contextual, task-specific similarity measure, that first embeds input images using a CNN, and then learns how to combine the embedded images in the collection to propagate the label information towards the target image.
In particular, Vinyals et al. (2016) cast the few-shot learning problem as a supervised classification task mapping a support set of images into the desired label, and developed an end-to-end architecture accepting those support sets as input via attention mechanisms. In this work, we build upon this line of work, and argue that this task is naturally expressed as a supervised interpolation problem on a graph, where nodes are associated with the images in the collection, and edges are given by a trainable similarity kernels. Leveraging recent progress on representation learning for graphstructured data Bronstein et al. (2017); Gilmer et al. (2017), we thus propose a simple graph-based few-shot learning model that implements a task-driven message passing algorithm. The resulting architecture is trained end-to-end, captures the invariances of the task, such as permutations within the input collections, and offers a good tradeoff between simplicity, generality, performance and sample complexity.
Besides few-shot learning, a related task is the ability to learn from a mixture of labeled and unlabeled examples -semi-supervised learning, as well as active learning, in which the learner has the option to request those missing labels that will be most helpful for the prediction task. Our graph-1 arXiv:1711.04043v2 [stat.ML] 29 Jan 2018 Under review as a conference paper at ICLR 2018 based architecture is naturally extended to these setups with minimal changes in the training design. We validate experimentally the model on few-shot image classification, matching state-of-the-art performance with considerably fewer parameters, and demonstrate applications to semi-supervised and active learning setups.
Our contributions are summarized as follows: • We cast few-shot learning as a supervised message passing task which is trained end-to-end using graph neural networks.
• We match state-of-the-art performance on Omniglot and Mini-Imagenet tasks with fewer parameters.
• We extend the model in the semi-supervised and active learning regimes.
The rest of the paper is structured as follows. Section 2 describes related work, Sections 3, 4 and 5 present the problem setup, our graph neural network model and the training, and Section 6 reports numerical experiments.

RELATED WORK
One-shot learning was first introduced by Fei- Fei et al. (2006), they assumed that currently learned classes can help to make predictions on new ones when just one or few labels are available. More recently, Lake et al. (2015) presented a Hierarchical Bayesian model that reached human level error on few-shot learning alphabet recongition tasks.
Since then, great progress has been done in one-shot learning. Koch et al. (2015) presented a deeplearning model based on computing the pair-wise distance between samples using Siamese Networks, then, this learned distance can be used to solve one-shot problems by k-nearest neighbors classification. Vinyals et al. (2016) Presented an end-to-end trainable k-nearest neighbors using the cosine distance, they also introduced a contextual mechanism using an attention LSTM model that takes into account all the samples of the subset T when computing the pair-wise distance between samples. Snell et al. (2017) extended the work from Vinyals et al. (2016), by using euclidean distance instead of cosine which provided significant improvements, they also build a prototype representation of each class for the few-shot learning scenario. Mehrotra & Dukkipati (2017) trained a deep residual network together with a generative model to approximate the pair-wise distance between samples.
A new line of meta-learners for one-shot learning is rising lately: Ravi & Larochelle (2016) introduced a meta-learning method where an LSTM updates the weights of a classifier for a given episode. Munkhdalai & Yu (2017) also presented a meta-learning architecture that learns meta-level knowledge across tasks, and it changes its inductive bias via fast parametrization. Finn et al. (2017) is using a model agnostic meta-learner based on gradient descent, the goal is to train a classification model such that given a new task, a small amount of gradient steps with few data will be enough to generalize. Lately, Mishra et al. (2017) used Temporal Convolutions which are deep recurrent networks based on dilated convolutions, this method also exploits contextual information from the subset T providing very good results.
Another related area of research concerns deep learning architectures on graph-structured data. The GNN was first proposed in Gori et al. (2005); Scarselli et al. (2009), as a trainable recurrent messagepassing whose fixed points could be adjusted discriminatively. Subsequent works ; Sukhbaatar et al. (2016) Chang et al. (2016) develop graph interaction networks that learn pairwise particle interactions and apply them to discrete particle physical dynamics. Duvenaud et al. (2015); Kearnes et al. (2016) study molecular fingerprints using variants of the GNN architecture, and Gilmer et al. (2017) further develop the model by combining it with set representations Vinyals et al. (2015), showing state-of-the-art results on molecular prediction.

PROBLEM SET-UP
We describe first the general setup and notations, and then particularize it to the case of few-shot learning, semi-supervised learning and active learning.
We consider input-output pairs (T i , Y i ) i drawn iid from a distribution P of partially-labeled image collections for arbitrary values of s, r, t and K. Where s is the number of labeled samples, r is the number of unlabeled samples (r > 0 for the semi-supervised and active learning scenarios) and t is the number of samples to classify. K is the number of classes. We will focus in the case t = 1 where we just classify one sample per task T . P l (R N ) denotes a class-specific image distribution over R N . In our context, the targets Y i are associated with image categories of designated imagesx 1 , . . . ,x t ∈ T i with no observed label. Given a training set using the model Φ(T ; Θ) = p(Y | T ) specified in Section 4 and R is a standard regularization objective.
Few-Shot Learning When r = 0, t = 1 and s = qK, there is a single image in the collection with unknown label. If moreover each label appears exactly q times, this setting is referred as the q-shot, K-way learning.
Semi-Supervised Learning When r > 0 and t = 1, the input collection contains auxiliary images x 1 , . . . ,x r that the model can use to improve the prediction accuracy, by leveraging the fact that these samples are drawn from common distributions as those determining the output.
Active Learning In the active learning setting, the learner has the ability to request labels from the sub-collection {x 1 , . . . ,x r }. We are interested in studying to what extent this active learning can improve the performance with respect to the previous semi-supervised setup, and match the performance of the one-shot learning setting with s 0 known labels when s + r = s 0 , s s 0 .

MODEL
This section presents our approach, based on a simple end-to-end graph neural network architecture. We first explain how the input context is mapped into a graphical representation, then detail the architecture, and next show how this model generalizes a number of previously published few-shot learning architectures.

SET AND GRAPH INPUT REPRESENTATIONS
The input T contains a collection of images, both labeled and unlabeled. The goal of few-shot learning is to propagate label information from labeled samples towards the unlabeled query image. This propagation of information can be formalized as a posterior inference over a graphical model determined by the input images and labels.
Following several recent works that cast posterior inference using message passing with neural networks defined over graphs Scarselli et al. (2009) associate T with a fully-connected graph G T = (V, E) where nodes v a ∈ V correspond to the images present in T (both labeled and unlabeled). In this context, the setup does not specify a fixed similarity e a,a between images x a and x a , suggesting an approach where this similarity measure is learnt in a discriminative fashion with a parametric model similarly as in Gilmer et al. (2017), such as a siamese neural architecture. This framework is closely related to the set representation from Vinyals et al. (2016), but extends the inference mechanism using the graph neural network formalism that we detail next. In its simplest incarnation, given an input signal F ∈ R V ×d on the vertices of a weighted graph G, we consider a family A of graph intrinsic linear operators that act locally on this signal. The simplest is the adjacency operator A : and w i,j its associated weight. A GNN layer Gc(·) receives as input a signal x (k) ∈ R V ×d k and produces , are trainable parameters and ρ(·) is a point-wise non-linearity, chosen in this work to be a 'leaky' ReLU Xu et al. (2015).
Authors have explored several modeling variants from this basic formulation, by replacing the pointwise nonlinearity with gating operations Duvenaud et al. (2015), or by generalizing the generator family to Laplacian polynomials Defferrard et al. (2016); Kipf & Welling (2016); Bruna et al. (2013), or including 2 J -th powers of A to A, A J = min(1, A 2 J ) to encode 2 J -hop neighborhoods of each node Bruna & Li (2017). Cascaded operations in the form (2) are able to approximate a wide range of graph inference tasks. In particular, inspired by message-passing algorithms, Kearnes et al. (2016); Gilmer et al. (2017) generalized the GNN to also learn edge featuresÃ (k) from the current node hidden representation:Ã where ϕ is a symmetric function parametrized with e.g. a neural network. In this work, we consider a Multilayer Perceptron stacked after the absolute difference between two vector nodes. See eq. 4: Then ϕ is a metric, which is learned by doing a non-linear combination of the absolute difference between the individual features of two nodes. Using this architecture the distance property Symmetry ϕθ(a, b) = ϕθ(b, a) is fulfilled by construction and the distance property Identity ϕθ(a, a) = 0 is easily learned.
The trainable adjacency is then normalized to a stochastic kernel by using a softmax along each row. The resulting update rules for node features are obtained by adding the edge feature kernelÃ (k) into the generator family A = {Ã (k) , 1} and applying (2). Adjacency learning is particularly important in applications where the input set is believed to have some geometric structure, but the metric is not known a priori, such as is our case.
In general graphs, the network depth is chosen to be of the order of the graph diameter, so that all nodes obtain information from the entire graph. In our context, however, since the graph is densely connected, the depth is interpreted simply as giving the model more expressive power.

Construction of Initial Node Features
The input collection T is mapped into node features as follows. For images x i ∈ T with known label l i , the one-hot encoding of the label is concatenated with the embedding features of the image at the input of the GNN.
where φ is a Convolutional neural network and h(l) ∈ R K + is a one-hot encoding of the label. Architectural details for φ are detailed in Section 6.1.1 and 6.1.2. For imagesx j ,x j with unknown label l i , we modify the previous construction to account for full uncertainty about the label variable by replacing h(l) with the uniform distribution over the K-simplex: V j = (φ(x j ), K −1 1 K ), and analogously forx.

RELATIONSHIP WITH EXISTING MODELS
The graph neural network formulation of few-shot learning generalizes a number of recent models proposed in the literature.
Siamese Networks Siamese Networks Koch et al. (2015) can be interpreted as a single layer message-passing iteration of our model, and using the same initial node embedding (5) x and resulting label estimationŶ * = jÃ (0) * ,j x (0) j , u , with u selecting the label field from x. In this model, the learning is reduced to learning image embeddings φ(x i ) whose euclidean metric is consistent with the label similarities.
Prototypical Networks Prototypical networks Snell et al. (2017) evolve Siamese networks by aggregating information within each cluster determined by nodes with the same label. This operation can also be accomplished with a gnn as follows. we consider where q is the number of examples per class, and where x (0) is defined as in the Siamese Networks. We finally apply the previous kernelÃ (1) = softmax(ϕ) applied to x (1) to yield class prototypes: Matching Networks Matching networks Vinyals et al. (2016) use a set representation for the ensemble of images in T , similarly as our proposed graph neural network model, but with two important differences. First, the attention mechanism considered in this set representation is akin to the edge feature learning, with the difference that the mechanism attends always to the same node embeddings, as opposed to our stacked adjacency learning, which is closer to Vaswani et al. (2017). In other words, instead of the attention kernel in (3), matching networks consider attention mechanisms of the formÃ is the encoding function for the elements of the support set, obtained with bidirectional LSTMs. In that case, the support set encoding is thus computed independently of the target image. Second, the label and image fields are treated separately throughout the model, with a final step that aggregates linearly the labels using a trained kernel. This may prevent the model to leverage complex dependencies between labels and images at intermediate stages.

TRAINING
We describe next how to train the parameters of the GNN in the different setups we consider: fewshot learning, semi-supervised learning and active learning.

FEW-SHOT AND SEMI-SUPERVISED LEARNING
In this setup, the model is asked only to predict the label Y corresponding to the image to classifȳ x ∈ T , associated with node * in the graph. The final layer of the GNN is thus a softmax mapping the node features to the K-simplex. We then consider the Cross-entropy loss evaluated at node * : The semi-supervised setting is trained identically -the only difference is that the initial label fields of the node will be filled with the uniform distribution on nodes corresponding tox j .

ACTIVE LEARNING
In the Active Learning setup, the model has the intrinsic ability to query for one of the labels from {x 1 , . . . ,x r }. The network will learn to ask for the most informative label in order to classify the samplex ∈ T . The querying is done after the first layer of the GNN by using a Softmax attention over the unlabeled nodes of the graph. For this we apply a function g(x (1) i ) ∈ R 1 that maps each unlabeled vector node to a scalar value. Function g is parametrized by a two layers neural network. A Softmax is applied over the {1, . . . , r} scalar values obtained after applying g: In order to query only one sample, we set all elements from the Attention ∈ R r vector to 0 except for one. At test time we keep the maximum value, at train time we randomly sample one value based on its multinomial probability. Then we multiply this sampled attention by the label vectors: The label of the queried vector h(l i * ) is obtained, scaled by the weight w ∈ (0, 1). This value is then summed to the current representation x (1) i * , since we are using dense connections in our GNN model we can sum this w · h(l i * ) value directly to where the uniform label distribution was concatenated After the label has been summed to the current node, the information is forward propagated. This attention part is trained end-to-end with the rest of the network by backpropagating the loss from the output of the GNN.

EXPERIMENTS
For the few-shot, semi-supervised and active learning experiments we used the Omniglot dataset presented by Lake et al. (2015) and Mini-Imagenet dataset introduced by Vinyals et al. (2016) which is a small version of ILSVRC-12 Krizhevsky et al. (2012). All experiments are based on the q-shot, K-way setting. For all experiments we used the same values q-shot and K-way for both training and testing.
Code available at: https://github.com/vgsatorras/few-shot-gnn 6.1 DATASETS AND IMPLEMENTATION 6.1.1 OMNIGLOT Dataset: Omniglot is a dataset of 1623 characters from 50 different alphabets, each character/class has been drawn by 20 different people. Following Vinyals et al. (2016) implementation we split the dataset into 1200 classes for training and the remaining 423 for testing. We augmented the dataset by multiples of 90 degrees as proposed by Santoro et al. (2016).
Architectures: Inspired by the embedding architecture from Vinyals et al. (2016), following Mishra et al. (2017), a CNN was used as an embedding φ function consisting of four stacked blocks of {3×3-convolutional layer with 64 filters, batch-normalization, 2×2 max-pooling, leaky-relu} the output is passed through a fully connected layer resulting in a 64-dimensional embedding. For the GNN we used 3 blocks each of them composed by 1) a module that computes the adjacency matrix and 2) a graph convolutional layer. A more detailed description of each block can be found at Figure  3.

MINI-IMAGENET
Dataset: Mini-Imagenet is a more challenging dataset for one-shot learning proposed by Vinyals et al. (2016) derived from the original ILSVRC-12 dataset Krizhevsky et al. (2012). It consists of 84×84 RGB images from 100 different classes with 600 samples per class. It was created with the purpose of increasing the complexity for one-shot tasks while keeping the simplicity of a light size dataset, that makes it suitable for fast prototyping. We used the splits proposed by Ravi & Larochelle (2016) of 64 classes for training, 16 for validation and 20 for testing. Using 64 classes for training, and the 16 validation classes only for early stopping and parameter tuning.

FEW-SHOT
Few-shot learning experiments for Omniglot and Mini-Imagenet are presented at Table 1 and Table  2 respectively. We evaluate our model by performing different q-shot, K-way experiments on both datasets. For every few-shot task T , we sample K random classes from the dataset, and from each class we sample q random samples. An extra sample to classify is chosen from one of that K classes.
Omniglot: The GNN method is providing competitive results while still remaining simpler than other methods. State of the art results are reached in the 5-Way and 20-way 1-shot experiments. In the 20-Way 1-shot setting the GNN is providing slightly better results than Munkhdalai & Yu (2017) while still being a more simple approach. The TCML approach from Mishra et al. (2017) is in the same confidence interval for 3 out of 4 experiments, but it is slightly better for the 20-Way 5-shot, although the number of parameters is reduced from ∼5M (TCML) to ∼300K (3 layers GNN).
At Mini-Imagenet table we are also presenting a baseline "Our metric learning + KNN" where no information has been aggregated among nodes, it is a K-nearest neighbors applied on top of the pair-wise learnable metric ϕ θ (x j ) and trained end-to-end, this learnable metric is competitive by itself compared to other state of the art methods. Even so, a significant improvement (from 64.02% to 66.41%) can be seen for the 5-shot 5-Way Mini-Imagenet setting when aggregating information among nodes by using the full GNN architecture. A variety of embedding functions φ are used among the different papers for Mini-Imagenet experiments, in our case we are using a simple network of 4 conv. layers followed by a fully connected layer (Section 6.1.2) which served us to compare between Our GNN and Our metric learning + KNN and it is useful for fast prototyping. More complex embeddings have proven to produce better results, at Mishra et al. (2017) a deep residual network is used as embedding network φ increasing the accuracy considerably. Regarding the TCML architecture in Mini-Imagenet, the number of parameters is reduced from ∼11M (TCML) to ∼400K (3 layers GNN).
Omniglot results are presented at Table 3, for this scenario we observe that the accuracy improvement is similar when adding images than when adding labels. The GNN is able to extract information from the input distribution of unlabeled samples such that only using 20% of the labels in a 5-shot semi-supervised environment we get same results as in the 40% supervised setting.
In Mini-Imagenet experiments, Table 4, we also notice an improvement when using semi-supervised data although it is not as significant as in Omniglot. The distribution of Mini-Imagenet images is more complex than for Omniglot. In spite of it, the GNN manages to improve by ∼2% in the 20% and 40% settings.   Table 4: Semi-Supervised Learning -Mini-Imagenet average accuracies with 95% confidence intervals.

ACTIVE LEARNING
We performed Active Learning experiments on the 5-Way 5-shot set-up when 20% of the samples are labeled. In this scenario our network will query for the label of one sample from the unlabeled ones. The results are compared with the Random baseline where the network chooses a random sample to be labeled instead of one that maximally reduces the loss of the classification task T .
Results are shown at Table 5. The results of the GNN-Random criterion are close to the Semisupervised results for 20%-labeled samples from Tables 3 and 4. It means that selecting one random label practically does not improve the accuracy at all. When using the GNN-AL learned criterion, we notice an improvement of ∼ 3.4% for Mini-Imagenet, it means that the GNN manages to correctly choose a more informative sample than a random one. In Omniglot the improvement is smaller since the accuracy is almost saturated and the improving margin is less.
Method 5-Way 5-shot 20%-labeled GNN -AL 99.62% GNN -Random 99.59% Method 5-Way 5-shot 20%-labeled GNN -AL 55.99% ±1.35% GNN -Random 52.56% ±1.18% Table 5: Omniglot (left) and Mini-Imagneet (right), average accuracies are shown at both tables, the GNN-AL is the learned criterion that performs Active Learning by selecting the sample that will maximally reduce the loss of the current classification. The GNN -Random is also selecting one sample, but in this case a random one. Mini-Imagenet results are presented with 95% confidence intervals.

CONCLUSIONS
This paper explored graph neural representations for few-shot, semi-supervised and active learning. From the meta-learning perspective, these tasks become supervised learning problems where the input is given by a collection or set of elements, whose relational structure can be leveraged with neural message passing models. In particular, stacked node and edge features generalize the contextual similarity learning underpinning previous few-shot learning models.
The graph formulation is helpful to unify several training setups (few-shot, active, semi-supervised) under the same framework, a necessary step towards the goal of having a single learner which is able to operate simultaneously in different regimes (stream of labels with few examples per class, or stream of examples with few labels). This general goal requires scaling up graph models to millions of nodes, motivating graph hierarchical and coarsening approaches Defferrard et al. (2016).
Another future direction is to generalize the scope of Active Learning, to include e.g. the ability to ask questions Rothe et al. (2017), or in reinforcement learning setups, where few-shot learning is critical to adapt to non-stationary environments.