MonkeyTree: Near-Minimal Congestion for Multi-tenant Training via Migration Anton A. Zabreyko Weiyang Wang Manya Ghobadi MIT Abstract . We present MonkeyTree, the first system to mitigate network congestion in multi-tenant GPU clusters through job-migration based defragmentation rather than network-layer techniques. As cloud operators co-locate ML training jobs on shared, oversubscribed networks, congestion degrades training throughput for over a third of jobs. Prior approaches either rely on routing and flow scheduling—which we show have fundamental limits when traffic exceeds capacity, or require costly full-bisection bandwidth topologies with packet spraying. MonkeyTree exploits characteristics of ML training traffic: ring-based collectives generate exactly one cross-rack flow per rack a job spans, making congestion-free placements achievable . The sparse constraint structure admits abundant valid configurations, making them easy to reach with few migrations. Once reached, low fragmentation is self-reinforcing , as new arrivals disturb only a few racks. MonkeyTree formulates defragmentation as an integer linear program that minimizes worker movements, subject to per-rack fragmentation bounds. We prove a tight bound showing any placement can be defragmented to at most two cross-rack fragments per ToR, and extend the formulation to hybrid parallelism with multiple rings per server. Migration is implemented via in-memory checkpoint-and-restore over RDMA, incurring only 9.02 9.02 seconds of system overhead end-to-end per worker. We evaluate MonkeyTree using a custom simulator modeling clusters of up to 2,048 H200 GPUs and prototype on a five-node A100 testbed. MonkeyTree improves average job completion time by 14% over the next best baseline on a cluster of 1,024 GPUs with a 4:1 oversubscription. With a high 16:1 oversubscription ratio and 2,048 GPUs, MonkeyTree keeps p99 job completion time within 5% of ideal. 1. Introduction Multi-tenant GPU clusters have become a common deployment model for machine learning (ML) training workloads in the cloud ( 67 ; 8 ; 53 ; 59 ; 55 ; 72 ) . In such environments, network congestion is a persistent challenge: concurrent jobs compete for shared bandwidth, degrading training throughput of 36.1% of the jobs ( 8 ) . The problem is compounded by the fact that operators traditionally build oversubscribed datacenter networks to reduce cost, further limiting available capacity during traffic bursts ( 18 ; 60 ; 54 ) . Prior work has tackled this problem from two directions. The first is to leverage routing ( 8 ; 53 ; 73 ; 59 ) and flow-scheduling ( 55 ; 57 ) techniques to mitigate congestion by selecting efficient paths and time-multiplexing network resources across jobs. However, we demonstrate that these approaches have fundamental limits: when aggregate traffic exceeds network capacity, flow collisions become inevitable even with optimal routing and flow scheduling (§ 2 ). At the other extreme, industry leaders are pushing packet spraying over full-bisection bandwidth topologies as the ultimate solution ( 13 ; 14 ; 6 ; 63 ) . This network architecture provides near-ideal performance, but at substantial cost. Achieving full-bisection bandwidth requires a large number of network switches, and packet spraying demands specialized switches and NICs ( 47 ) . Cloud providers must therefore trade performance against infrastructure expense. We analyze the traffic patterns of multi-tenant DNN training jobs and show that traffic is dominated by sparse elephant flows, in which each GPU communicates with only one other GPU for the majority of its traffic. This sparsity suggests network congestion is rare , even on oversubscribed networks. In practice, however, jobs are often fragmented across servers in different racks. Such fragmentation persists under high load despite locality-aware job schedulers (§ 2 ), causing the flow count on ToR-to-spine links to spike and increasing network load by 4.85 \times relative to optimal placement (§ 6.3 ). This leads to congestion despite sparse per-job traffic. Existing mitigation approaches address this only through networking techniques ( 8 ; 55 ; 57 ; 53 ; 59 ; 73 ) , but do not tackle the root cause, leaving clusters persistently fragmented. We argue that the most effective way to address congestion in multitenant GPU clusters lies not in optimizing network transfers but in job placement . Based on this insight, we propose MonkeyTree, a system that continuously maintains a low-fragmentation state through small, proactive job migrations —moving workers of the same job to concentrate them on the same racks. This defragmentation reduces competing network traffic at its root cause, rather than reacting to congestion after it arises. Using job migration to reduce congestion in GPU clusters remains unexplored, a legacy of CPU-centric datacenters. However, CPU workloads generate arbitrary traffic matrices, making congestion-free placements both ill-defined and rare. Reaching a defragmented placement that minimizes network traffic requires migrating a large fraction of workers, yet contention persists because no placement isolates traffic from workers entirely (§ 2.2 ). We argue that GPU training traffic is fundamentally different, and migration-based defragmentation is not only practical but highly effective for multi-tenant ML clusters, requiring only a small number of targeted migrations to eliminate congestion. MonkeyTree rests on three key insights about the structure of ML training traffic: First, congestion-free states are achievable in GPU clusters. The majority of ML training traffic consists of ring-based collectives that generate exactly one flow per rack a job spans. This property transforms the problem: rather than minimizing network traffic, we need only keep each rack’s outgoing flows below its uplink count. Any placement satisfying this constraint achieves full path isolation. Secondly, congestion-free states are abundant . Unlike CPU workloads, where low-traffic placements are rare, the sparse constraint structure for GPU training admits many valid congestion-free configurations. Worker ordering and placement within racks do not affect traffic patterns, and each rack’s constraint is independent. These degrees of freedom make congestion-free states easy to reach from any starting point. Finally, maintaining low fragmentation is self-reinforcing . Once a cluster reaches a valid state, maintaining it requires minimal effort. A new job can violate constraints at only a few racks, and because valid placements are abundant, a small number of migrations restores compliance. Building on these insights, MonkeyTree employs a centralized controller and distributed daemons that operate alongside existing job schedulers without modifying their placement logic (§ 4 ). When jobs arrive, the scheduler assigns GPUs as usual. MonkeyTree monitors the resulting placement and checks whether any rack’s fragmentation exceeds a threshold derived from its uplink count. If so, the controller invokes a migration solver to compute the minimum migrations needed to restore a congestion-free state. Once fragmentation is bound, the controller computes routes using a Perfect routing scheme we designed (§ 5.4 ), that assigns each DP flow a dedicated uplink, achieving full path isolation. Daemons on each server execute migrations and configure local routing rules. By exploiting ML traffic sparsity and the self-reinforcing nature of low fragmentation, MonkeyTree keeps migration overhead minimal, typically requiring less than two moves per job arrival. The core algorithmic contribution is the migration solver. We formulate the problem as an integer linear program (ILP): given a current placement, find a new placement that meets the fragmentation target while minimizing worker movements (§ 5.2 ). We first solve this for workloads with a single ring-based collective and prove a tight bound: any placement can be defragmented into at most 2 cross-rack fragments per ToR (§ 5.1 ). This bound is both achievable and necessary in the worst case. Using insights from the proof, we extend the formulation to hybrid parallelism, where each server runs multiple workers forming parallel communication rings (§ 5.3 ). Realizing this design requires addressing two challenges. The first is ILP scalability: integer programs have worst-case exponential complexity. However, our analysis shows that the ILP solve time scales with the number of moves required (§ 5.2 ). Combined with the abundance and self-reinforcing nature of low-fragmentation cluster states, the number of moves required is two or less 80% of the time. This keeps solve times low in practice. For a cluster with 1,024 GPUs, solving the ILP takes 0.89 seconds on average, triggered on average every 102 minutes at 80% load (§ 6.5 ). The second challenge is migration overhead. Live migration is considered complex and disruptive, but modern DNN training makes it surprisingly simple. Training frameworks already provide checkpointing to store and restore state for fault tolerance, and we build migration directly on this infrastructure. We implement in-memory checkpoint-and-restore over RDMA using PyTorch’s Distributed Checkpointing library ( 52 ) . To evaluate MonkeyTree, we build a custom Rust-based simulator for modeling multi-tenant distributed ML training, modeling clusters of up to 2,048 H200 GPUs and a 400 Gbps network. We implement several models, including variants of GPT-3 ( 7 ; 42 ) , GPT-OSS ( 49 ) , Llama2 ( 62 ) , and Llama3 ( 17 ) (§ 6.1 ). We also prototype MonkeyTree in a testbed with five nodes, each equipped with one A100 GPU and a 100 Gbps RDMA NIC, and perform an end-to-end migration benchmark. In simulation, we demonstrate that on a cluster of 1,024 nodes MonkeyTree improves average job completion time by 14 % over the next best baseline (§ 6.2 ). On a cluster of 2,048 GPUs with an oversubscription ratio of 16:1, we keep the p99 job-completion slowdown to just 5% (§ 6.4 ). Our testbed prototypes support efficient migration, with 9.02 s of system overhead from the start of migration to resuming training (§ 7 ). To the best of our knowledge, this is the first system to mitigate congestion between competing ML training jobs using migration as the primary remedy. We plan on open-sourcing our codebase upon publication. This work does not raise any ethical issues. 2. Motivation Figure 1 . A multitenant GPU cluster. Figure 2 . Migration and network congestion in shared CPU vs. GPU clusters. Different colors represent workers in different jobs; each ToR switch supports two units of demand. The CPU cluster (top) requires 11 migrations, yet inter-job congestion persists on racks 4 and 7. The GPU cluster (bottom) needs only 4 migrations to eliminate congestion. Figure 3 . Sample congestion-free states for GPU clusters, for jobs shown in Figure 3 . Despite different placements, all states have two or fewer fragmented jobs, thereby generating at most two units of demand per rack. 2.1. Multi-Tenant Training and Congestion Multi-tenant training is ubiquitous in today’s cloud environment ( 8 ; 53 ; 59 ; 55 ; 57 ; 73 ) . A typical GPU cluster consists of GPU servers interconnected by a hierarchical network, shown in Figure 1 . Each GPU server contains multiple GPUs, each with a dedicated NIC, as well as an internal high-bandwidth interconnect shown at the bottom of Figure 1 . In these shared GPU clusters, each training job occupies one or more GPU servers, making the network the primary shared resource. Unfortunately, network congestion significantly degrades training performance, with Alibaba reporting up to 36.1% of the jobs experience throughput reduction due to congestion ( 8 ) . Two directions have emerged to address this. The first invests in network infrastructure: packet spraying over full-bisection bandwidth topologies delivers near-ideal performance but requires expensive specialized hardware such as Nvidia’s SuperNICs ( 47 ; 46 ) . Many deployments, therefore, accept oversubscribed networks to reduce cost ( 18 ; 60 ; 54 ) . The second direction employs software techniques, such as routing ( 8 ; 53 ) and flow scheduling ( 55 ; 57 ) , to mitigate congestion in oversubscribed networks. We evaluate Crux as an example of these approaches, on a cluster with 1,024 GPUs and 4:1 network oversubscription ratio. We observe a 26\% average slowdown despite the mitigation: when aggregate traffic exceeds network capacity, flow collisions become inevitable regardless of strategy. Flow scheduling approaches like Cassini attempt to overlap one job’s communication with another’s computation, but this strategy is fragile because it requires well-matched job characteristics and becomes unstable when iteration times differ by even a slight amount ( 58 ) . Both approaches overlook a more fundamental solution: reducing traffic entering the network in the first place. A job whose workers reside entirely within a single rack generates no traffic beyond the ToR layer, whereas a fragmented job spanning multiple racks requires communication through the spine. When too many fragmented jobs share a rack, the aggregate uplink demand exceeds the ToR’s uplink capacity, leading to congestion. Job scheduling doesn’t resolve fragmentation: our evaluation shows that in a cluster of 1,024 GPUs across 16 racks, up to 93 % of ToRs carry more uplink demand than their capacity even under a locality-optimized scheduler. This happens in production systems at scale as well. We analyzed Alibaba’s report and found that almost 50% of their jobs are fragmented ( 8 ) . The natural remedy is defragmentation through job migration , yet prior work on network contention in GPU clusters ignores it, a legacy of CPU-centric multitenant clusters where migration was impractical. 2.2. Migration Challenges in CPU Workloads Migration-based approaches for CPU workloads fall into two categories. The first addresses resource sharing at the server level, where CPU cores and memory are the primary contended resources ( 15 ; 23 ; 69 ) . Early GPU migration works, such as Gandiva ( 71 ) , adopted the same granularity, splitting GPUs across jobs on a server. This does not apply to our setting, where the network above between ToR and spine switches is the primary contended resource ( 8 ; 19 ) . The second jointly optimizes placement and routing to reduce network contention ( 31 ) . However, CPU workloads generate arbitrary traffic patterns, yielding a multi-objective problem: minimize network traffic while minimizing migrations. This formulation has fundamental limitations. Consider five jobs (color-coded) on 32 servers across eight racks in Figure 3 . Each ToR has two uplinks supporting two units of demand, and each node sends one unit of traffic uniformly to others in its job. The initial placement is fragmented, with racks demanding up to 3.8 units (Figure 3 , top-left). The placement that minimizes peak per-ToR traffic requires at least 11 migrations (Figure 3 , top), yet congestion persists: only two racks stay within uplink capacity, and racks 4 and 7 still exhibit inter-job contention between the green and pink jobs. This illustrates two problems. First, eliminating congestion is impossible: no placement achieves zero inter-job contention in this example, and alternative solutions simply shift congestion to different jobs. Without a policy specifying job priorities, there is no clear optimum. Second, good states are sparse: diverse CPU traffic patterns make low-congestion placements rare targets, requiring one-third of the cluster to migrate in this example alone—a ratio that worsens with scale. In summary, migration for CPU workloads faces fundamental obstacles. Does this change for GPU workloads? 3. Tractability of GPU Migration Distributed training jobs consist of computation and communication operations. Communication arises from parallelizing model training across GPUs, creating data dependencies that manifest as network transfers. Modern LLM training combines multiple parallelization strategies, each generating distinct traffic patterns. Table 1 shows traffic generated by one iteration of Llama3-70B and GPT3-175B on 128 GPUs with a local batch size of 16. Tensor parallel (TP) traffic is the largest but remains confined to high-bandwidth interconnects such as NVLink within a server. Among traffic entering the datacenter network, data-parallel (DP) collectives dominate: 7.5 \times and 29.4 \times larger than pipeline-parallel (PP) traffic for Llama and GPT, respectively. Congestion, therefore, manifests most significantly when DP collectives from different jobs collide. Hence, we define a placement to be a congestion-free state if no DP traffic across jobs competes in the network. To minimize network congestion, we focus on managing DP traffic. DP replicates the model across GPUs, with each GPU processing a different data batch. Fully Sharded Data Parallelism (FSDP) extends DP by sharding parameters across GPUs. Both require synchronizing gradients or parameters at the end of each training iteration through collective communication. These collectives generate traffic proportional to model size with the same volume and pattern, so we treat them identically and refer to both as DP traffic. When combined with other parallelisms such as PP and TP, only a subset of GPUs shares the same model replica; we call this subset a replica group , and each performs its own collective independently. Ring-based collectives. We focus on ring-based collective algorithms, which are bandwidth-optimal and generate the sparsest traffic pattern ( 60 ) . When a replica group spans multiple racks, each ToR generates one flow entering and leaving, regardless of how many workers reside in that rack or their ordering. We refer to such traffic as DP-flows throughout the rest of the paper. This sparsity fundamentally changes the property of congestion-free states in shared GPU clusters. Model Llama3-70B GPT3-175B Parallelism Deg. Total % of DP Net? Deg. Total % of DP Net? TP 8 35.8 TB 426% N 8 68.8 TB 3276% N DP/FSDP 4 840 GB 100% Y 4 2.1 TB 100% Y PP 4 48 GB 5.7% Y 4 72 GB 3.4% Y Table 1 . Traffic composition of common LLMs with different parallelism and whether the traffic is carried in the network. 3.1. Congestion-Free States are Achievable Consider again the example in Figure 3 , now with GPU jobs. We assume each server has one GPU and runs training with DP-only (i.e., one replica group per job); we discuss the multi-GPU and hybrid parallelism cases in Section 5.3 . Since DP traffic dominates network congestion, we analyze only DP synchronization traffic, where each GPU sends one unit of demand to its neighboring node. The total network demand generated by each job is the same across CPU and GPU jobs; however, unlike the CPU case, the traffic matrix is sparse : ring-based collectives generate exactly one flow per ToR per fragmented job. As long as each ToR contains fewer than two fragmented jobs, the number of outgoing flows stays below the number of uplinks. This sparsity resolves the ill-defined optimization problem from Section 2.2 . In particular, there exist states in which the traffic leaving each ToR does not exceed its uplink capacity (bottom-left of Figure 3 ). We define such states as congestion-free , since this condition allows each DP flow to be assigned a dedicated uplink, achieving path isolation . Under minimal uplink provisioning, such states always exist (§ 5.1 ). For CPU workloads, operators must balance network contention against migration overhead ( 31 ; 27 ; 32 ) . In contrast, for ML workloads this tradeoff disappears: because congestion-free states are always attainable, they can be enforced as a constraint, allowing the optimization to focus solely on minimizing migrations. Now, we turn to minimizing migrations: given a contended state, what is the minimum number of worker movements to reach any congestion-free state? The bottom of Figure 3 shows such placement with the minimum amount of migration, requiring only 4 compared to 11 in the CPU case. Such a reduction stems from another property of GPU jobs: congestion-free placements are readily available. 3.2. Congestion-Free States Are Abundant The achievable nature of congestion-free states implies another useful property; any state where the number of flows leaving each ToR does not exceed its uplink count is equally good, and we do not need to find a single optimal arrangement. For instance, Figure 3 shows four other congestion-free placements for GPU workloads, in addition to the bottom right placement in Figure 3 . Notice that even seemingly fragmented placements, like the bottom-right one, are congestion-free. This flexibility compounds in several ways. First, workers within a replica group are order-insensitive: they form a ring in any order through a simple re-assignment of ranks for communication, and still produce the same sparse traffic pattern in the network. Second, the constraint is local to each ToR, as satisfying the uplink bound at one ToR is independent of other ToRs. Consequently, unlike CPU workloads, where low-congestion placements are rare and expensive to reach, congestion-free states in a shared GPU cluster are plentiful. Hence, we can always reach one from any contended state through a small number of migrations (§ 6 ). 3.3. Congestion-Free States are Self-Reinforcing Once a cluster reaches a congestion-free state, maintaining it requires only incremental effort. A single new job spans a limited number of ToRs, so its arrival can violate the uplink constraint at only those few racks—a small, localized perturbation to an otherwise valid configuration. Because valid placements are abundant, restoring compliance never requires a far-reaching search: a small number of migrations among the affected racks suffices. This creates a virtuous cycle: few migrations mean low overhead, low overhead makes proactive maintenance practical, and a well-maintained cluster presents only simple, local violations to correct. Rather than gradually drifting into a highly contended state that demands expensive cluster-wide reorganization, the system naturally remains in the neighborhood of valid configurations. 4. MonkeyTree System Design Figure 4 . Overview of MonkeyTree. A centralized controller and per-node daemons operate alongside existing schedulers. Our analysis in Section 3 shows that migration in shared GPU clusters is both practical and desirable. We introduce MonkeyTree, a system that eliminates network contention in shared GPU clusters through migration-based defragmentation. Overview. Figure 4 illustrates MonkeyTree’s architecture and workflow. The system consists of a centralized controller (§ 4.1 ) and distributed daemons (§ 4.2 ), operating alongside existing job schedulers without modifying their placement logic. The workflow begins when a job arrives, and the existing job scheduler 1 assigns GPU placements to the new job. Rather than intervening in placement decisions, MonkeyTree monitors the resulting cluster state 2 and initiates migration only when necessary. We set a fragmentation threshold based on the ToR uplink count to ensure path isolation is always achievable (§ 5.1 ). If any rack exceeds this threshold, the controller invokes the migration solver 3 to compute the minimum worker movements needed to restore a congestion-free state (§ 5.2 ). Whether or not migrations are needed, the controller computes routes 4 that provide path isolation for all DP flows (§ 5.4 ). It then sends migration instructions and routing assignments to the daemons 5 . Each daemon executes its assigned migrations via an efficient checkpoint-and-restore operation 6 and configures local routing rules to steer DP traffic onto isolated paths. 4.1. MonkeyTree Controller The controller interfaces with the cluster’s job scheduler (e.g., Slurm ( 30 ) ) to observe placement decisions. It does not modify the scheduler’s allocation logic, but allows the scheduler to make an initial decision after job arrival. If the placement decision violates the fragmentation constraint, MonkeyTree intervenes and computes a new placement that satisfies the constraint while minimizing migrations. Migration decisions. When a new job’s placement causes any rack’s fragmentation to exceed the threshold, the controller computes the minimum migrations to restore compliance. The threshold is set to equal the number of uplinks per ToR, ensuring that path isolation is always achievable. Section 5 details the migration algorithm. Perfect routing solver. After each job arrival or migration, the controller reconfigures routing to achieve path isolation. MonkeyTree uses a deterministic routing scheme, called Perfect routing , that assigns each DP traffic a dedicated uplink, guaranteed to exist as long as fragmentation stays within the threshold. The controller transmits routing assignments to the daemons, which compute ECMP hashes that steer traffic onto the assigned paths, similar to prior work ( 8 ; 37 ) . 4.2. MonkeyTree Daemons Daemons run on each server and handle job lifecycle operations: launching jobs with pre-computed ring orderings, executing migrations, and updating routing configurations. Migration execution. We implement migration itself as checkpoint-and-restore over GPUDirect RDMA. When the controller initiates a migration, the source daemon pauses training after the current iteration completes and checkpoints model state to the destination. The destination daemon receives the checkpoint into CPU memory, then loads it onto GPUs and resumes training with the replica group. This approach leverages existing checkpointing infrastructure and avoids overwhelming GPU memory during transfers. Section 7 describes our prototype implementation. 5. MonkeyTree Formulation In this section, we first show that for a GPU cluster with at least two uplinks per ToR, congestion-free states are well-defined and always achievable (§ 5.1 ). We then formulate the problem of minimizing the number of migrations to bound the number of DP-flows that enter the fabric as an Integer Linear Program (ILP) (§ 5.2 , § 5.3 ). Finally, we present a routing scheme, Perfect routing , that exploits the bound on DP-flows to guarantee path isolation, nearly eliminating congestion (§ 5.4 ). 5.1. Bounding Fragmentation Degree Formally, we define a rack’s fragmentation degree as the number of DP flows originating from this rack that have destinations outside it. For pure DP jobs, this equals the number of fragmented jobs under the rack. We begin by characterizing what is achievable given a cluster and a set of jobs. Theorem 1. For any cluster and any set of pure DP or FSDP jobs running on it, there exists a job placement such that no rack has a fragmentation degree greater than two. Proof . Order the jobs arbitrarily, and place their workers sequentially across the cluster from left to right. For any rack, this placement induces at most three contiguous regions. The front consists of the trailing workers of a job that began on a previous rack and finishes on the current one. The end consists of the leading workers of a job, with the remaining workers placed on subsequent racks. The middle consists of jobs that are entirely contained within the rack. Jobs in the middle region do not contribute to fragmentation, since all of their communication remains local to the rack. Moreover, the front and end regions each contain at most one job that spans racks. Therefore, each rack can contain at most two fragmented jobs, implying that the fragmentation degree of any rack is at most two. We note that there are scenarios in which achieving a fragmentation degree better than two is impossible. For example, consider two jobs whose sizes each exceed the capacity of a single rack, running on a cluster with three racks. In this case, the two jobs must overlap on at least one rack, forcing that rack to have a fragmentation degree of at least two. Input w_{0}(s,t) Initial placement: # of job s workers on ToR t \lambda Fragmentation threshold S=\{s_{0},\cdots,s_{j}\} Set of jobs to be placed, where job j requires s_{j} workers T Number of ToRs (racks) C ToR capacity, i.e., number of nodes below a ToR Output w(s,t) Final placement: # of job s workers on ToR t Table 2 . Variable definitions. (1) \displaystyle\min \displaystyle\textstyle\sum_{\text{all }s,t}\frac{1}{2}\left|w(s,t)-w_{0}(s,t)\right| (2) s.t. \displaystyle\textstyle\sum_{t0\ \text{and}\textstyle\sum_{t^{\prime}\neq t}w(s,t^{\prime})>0\right\}\right|\leq\lambda \displaystyle\forall\ \text{ToR }t (5) \displaystyle w(s,t)\geq 0 \displaystyle\forall\ s,t Figure 5 . MonkeyTree’s ILP formulation for minimizing migration. Once a placement limits the number of DP-flows exiting each rack to be less than the number of ToR uplinks, a congestion-free cluster only requires a routing scheme that assigns each flow to a dedicated uplink, guaranteeing path isolation. We derive such a routing scheme, which we call Perfect routing , for a two-tier network topology, detailed in Section 5.4 . Combined with the worst-case minimum fragmentation degree of two, our routing scheme implies that provisioning just two uplinks per rack is sufficient for a congestion-free network for shared GPU clusters. The above arguments establish that a congestion-free state is achievable . Next, we formulate MonkeyTree’s core algorithm that finds a sufficiently defragmented placement from an initial fragmented one, minimizing the number of migrations between the two. We assume each rack has more than two allocated uplinks and aim to find a congestion-free state in which no rack’s fragmentation degree exceeds the number of uplinks. 5.2. MonkeyTree ILP for DP and FSDP Jobs In this section, we identify the minimum number of migrations needed to defragment every rack below a set threshold, thereby achieving a nearly congestion-free state. We focus on pure DP and FSDP jobs here, and extend our formulation to model parallelism in Section 5.3 . Table 2 defines the variables we use in this formulation, and Listing 5 illustrates MonkeyTree’s optimization problem. We model this problem as follows: let S denote the set of jobs, and let T denote the number of racks. We construct a bipartite graph in which the left nodes s\in S correspond to fragmented jobs in the cluster, and the right nodes t ( 0\leq t