ncsim: A Lightweight Simulator for Networked Edge Computing with Wireless Interference Modeling Bhaskar Krishnamachari∗ , Maya Gutierrez∗ , and Jared Coleman∗† ∗ University of Southern California
arXiv:2605.01094v1 [cs.DC] 1 May 2026
[email protected], [email protected] † Loyola Marymount University [email protected]
scheduling with physically-grounded 802.11 WiFi models in a single Python package. ncsim deliberately occupies the space between packet-level network simulators (ns-3, OMNeT++) and workflow simulators (SimGrid, WRENCH, CloudSim, iFogSim): more wireless-realistic than workflow tools, but much lighter than ns-3 for scheduler sweeps. Because no prior tool combines DAG-aware scheduling with realistic 802.11 contention modeling, scheduler comparisons in the literature have implicitly assumed interference-free or abstract-link conditions. We therefore use ncsim to perform what is, to our knowledge, the first like-for-like comparison of DAG schedulers under realistic CSMA/CA interference: a 108-run factorial study finds that the scheduler appearing optimal under an interference-free model is outperformed in 27.8% of scenarios, a rank inversion. In the most striking case, I. I NTRODUCTION Edge and fog computing architectures distribute computation the HEFT scheduler produces 2.7× worse makespan than a across heterogeneous nodes connected by networks of varying simple round-robin baseline, yet an interference-free evaluation capacity and reliability [1]. Effective task scheduling in these would confidently select HEFT. This result is infeasible to environments requires co-optimizing compute placement and produce with either class of existing tool; ncsim therefore not network transport: a task placement that minimizes computation only motivates realistic wireless modeling but actively corrects time may incur excessive data transfer costs, while a network- scheduler rankings that would otherwise be systematically wrong. aware placement may underutilize fast processors. The contributions are: Existing simulation tools address parts of this problem. Network simulators such as ns-3 [2] and OMNeT++ [3] 1) ncsim simulator: a modular architecture combining provide detailed protocol stacks but are heavyweight, complex DAG scheduling (HEFT, CPOP, round-robin) with 802.11 to configure, and lack native support for DAG-based task WiFi models (log-distance path loss, MCS rate adaptation, scheduling. Conversely, task scheduling simulators such as Bianchi CSMA/CA contention, hidden terminal SINR SimGrid [4], WRENCH [5], and CloudSim [6] model workdegradation, multi-hop routing with dynamic bandwidth flows and compute resources but typically abstract the network sharing) in ∼5,500 lines of Python. as point-to-point links with fixed bandwidths, omitting wireless 2) Three-stage validation ladder: nine internal experiments contention, interference, and multi-hop effects. Edge-specific matching analytical predictions exactly, reproduction of tools like iFogSim [7] and EdgeCloudSim [8] add domainBianchi’s published results [9], and cross-validation against specific features but use simplified wireless models that do ns-3 packet-level simulations (mean error 4%). not capture the distance-dependent rates, CSMA contention, 3) Rank inversion finding: a 108-run factorial on grid netor hidden terminal interference that characterize real 802.11 works revealing that interference-free evaluation produces deployments. wrong scheduler rankings in 27.8% of scenarios. We present ncsim,1 an open-source, lightweight, flow4) Scalability confirmation: a 36-run study on a 100-node level discrete-event simulator that combines DAG workflow random geometric graph with 30–50 task DAGs, where the 1 https://github.com/ANRGUSC/ncsim rank inversion rate rises to 50%.
Abstract—Evaluating DAG task schedulers for wireless edge computing requires jointly modeling compute placement and wireless interference, yet existing tools treat them in isolation. This gap leads to rank inversions: the scheduler that appears optimal under an interference-free model can be the worst choice under realistic wireless conditions. We present ncsim, a lightweight discrete-event simulator that bridges this gap by combining DAG workflow scheduling with physically-grounded IEEE 802.11 CSMA/CA interference modeling in a single Python package. A 108-run factorial experiment reveals rank inversions in 27.8% of scenarios, with the interference-free-optimal scheduler producing up to 2.7× worse makespan than a simple round-robin baseline; scaling to a 100-node random geometric graph raises the inversion rate to 50%. These rank inversions show that interference-free evaluation can select the wrong algorithm entirely, justifying the design and use of ncsim.
III. A RCHITECTURE In this section, we describe the architecture of ncsim, which is organized around a layered discrete-event simulation (DES) engine with pluggable components for scheduling, routing, and
Pkt
Swe ep
-Lev el
Hid . Te
rm. CSM A
We situate ncsim at the intersection of DAG scheduling research and wireless network simulation. The key gap is not any single prior system but the combination our target users need: DAG-aware scheduling, wireless CSMA/CA and hiddenterminal modeling, and lightweight sweepability in one tool. Table I summarizes the comparison. DAG scheduling and workflow systems. DAG scheduling has a rich history in parallel computing, from list-scheduling and dynamic-level scheduling to HEFT and CPOP [11], [12], [13], [10]. Benchmarking and parametric scheduler design tools such as SAGA, PISA, and parametric decomposition enable adversarial search and systematic ablation [14], [15], [16]. Dispersed and edge execution systems (Jupiter, Tactical Jupiter, and throughput-oriented extensions) integrate DAG scheduling with profiling and orchestration on real clusters [17], [18], [19]. None of these model wireless contention at the physical layer, and to our knowledge no prior study has compared these schedulers under realistic 802.11 CSMA/CA interference — a gap ncsim is built to close. Network simulators and wireless/edge DAG systems. ns3 [2] and OMNeT++ [3] provide detailed WiFi, LTE, and TCP/IP stacks with high-fidelity channel models, but they are heavyweight: configuring custom DAG scheduling requires external workflow engines and C++ glue code, and packetlevel simulation times make large parameter sweeps prohibitive. A growing body of edge/IoT DAG scheduling work tackles heterogeneous devices and MEC offloading [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30], [31], but it typically assumes abstract link rates rather than modeling the CSMA/CA and hidden-terminal phenomena that dominate real 802.11 channels. Workflow and edge simulators. SimGrid [4], WRENCH [5], and CloudSim [6] support DAG workflows natively but model networks as links with fixed or analytically-derived bandwidths. This abstraction fits wired data centers but omits wireless contention, hidden terminals, and spatial reuse. Edge-specific tools such as iFogSim [7] and EdgeCloudSim [8] add latencysensitive placement and mobility but retain simplified wireless models. ncsim fills the resulting gap by combining DAGaware scheduling with physically-grounded 802.11 wireless models in a lightweight Python package, providing a controlled environment where wireless effects can be systematically varied and their impact on scheduling quality precisely measured.
Tool
WiF i
II. R ELATED W ORK
TABLE I: Simulator comparison. ncsim uniquely combines DAG-native scheduling with CSMA/CA and hidden terminal modeling at flow-level granularity.
DAG
Sections II to V survey related work and describe ncsim’s architecture, system model, and simulation engine. Section VI validates the WiFi model, and Section VII presents the experimental evaluation. Section VIII discusses implications and future directions.
ns-3 [2] OMNeT++ [3] SimGrid [4] WRENCH [5] CloudSim [6] iFogSim [7] EdgeCloudSim [8] ncsim
✗ ✗ ✓ ✓ ✓ ✓ ✗ ✓
✓ ✓ ✗ ✗ ✗ ✗ ✓ ✓
✓ ✓ ✗ ✗ ✗ ✗ ✗ ✓
✓ ✓ ✗ ✗ ✗ ✗ ✗ ✓
✓ ✓ ✗ ✗ ✗ ✗ ✗ ✗
High High Low Low Low Med Med Low
Fig. 1: High-level architecture of ncsim.
interference modeling. Figure 1 illustrates the data flow from scenario specification through simulation to output traces. A. Design Goals Four principles guide ncsim. Determinism: rounding all simulation times to microsecond precision (10−6 s) yields bitidentical results across runs and platforms. Modularity: six abstract base classes (Table III) decouple schedulers, routing, and interference models so swapping one does not touch the others. Simplicity: scenarios are declarative YAML; the whole simulator is ∼5,500 lines of Python with minimal dependencies. Physical grounding: link bandwidths are derived from RF parameters (transmit power, frequency, path loss exponent), so link rates are physically consistent with node positions rather than specified as arbitrary constants.
TABLE II: Scope of validity: phenomena modeled by ncsim and their impact on scheduling studies. Phenomenon
Status
Impact
CSMA/CA contention Hidden terminals MCS rate adaptation Path loss Pkt-level dynamics TCP slow-start Fading / mobility Multi-slot parallelism
Modeled (Bianchi) Modeled (SINR) Modeled (11n/ac/ax) Modeled (log-distance) Not modeled Not modeled Optional (log-normal) Not modeled
High High Medium High Low† Medium‡ Low§ App-dependent
†
For bulk transfers. ‡ For short flows. § For static deployments.
TABLE IV: Artifact components shipped with ncsim. Component
Availability
ncsim source (∼5,500 LoC Python) YAML scenario configurations Validation experiment scripts ns-3 Dockerfile and cross-validation scripts Raw JSONL result traces Plotting and analysis scripts
GitHub included included included included included
execution, facilitating the automated parameter sweeps used throughout Section VII.
TABLE III: Pluggable abstractions in ncsim. ABC
Implementations
Scheduler RoutingModel InterferenceModel LinkModel QueueModel DAGSource
Manual, RoundRobin, HEFT, CPOP Direct, WidestPath, ShortestPath None, CSMA Bianchi Static FIFO Single, Multi
E. Artifact Availability ncsim is released as an open-source research artifact to support community adoption and reproducibility. The repository bundles everything needed to regenerate the results in Sections VI and VII: simulator source, scenario configurations, validation experiment scripts, a Dockerized ns-3 environment, raw JSONL traces, and plotting scripts (Table IV).
B. Scope and Assumptions IV. S YSTEM M ODEL ncsim targets macroscopic scheduling decisions rather than protocol engineering. It intentionally omits packet-level In this section, we present the formal models underlying simulation, physical-layer channel dynamics (fading, OFDM), ncsim: the network and compute infrastructure, the DAG mobility, and multi-slot compute parallelism, retaining the workflow representation, the scheduling and routing framephenomena that most affect scheduling: CSMA/CA contention, works, and the physically-grounded 802.11 WiFi model that hidden terminals, and MCS rate adaptation. Table II summarizes captures contention and hidden terminal effects. the modeling scope. ncsim’s flow-level abstraction targets the regime of scheduler evaluation with bulk DAG edges (10 MB-class payloads), A. Network Model where steady-state throughput dominates and TCP slow-start A network consists of nodes and directed links. Each node v is negligible. The Bianchi saturation model and capturehas a compute capacity Cv (compute units per second) and an threshold hidden-terminal model are the right level of fidelity optional 2D position (xv , yv ) used for RF calculations. Each for that regime: they capture the first-order effects that change link ℓ from node u to node v has a bandwidth Bℓ (MB/s) and scheduling outcomes (channel time-share and SINR-driven rate latency Lℓ (seconds). Topologies are specified in YAML and drops) without the cost of packet-level simulation. We use can be arbitrary directed graphs. deterministic path loss throughout to isolate contention and hidden-terminal effects from fading and mobility; stochastic B. Compute Model channels are available but are not the focus of this paper. C. Key Abstractions Six abstract base classes (Table III) let researchers plug in their own schedulers, routing models, or interference models without touching the core event engine; every component used in Section VII is itself an instance of these interfaces. D. Visualization and Tooling
A task t has a compute cost wt (in compute units). The execution time on node v is wt /Cv . Each node processes one task at a time using FIFO queuing. Tasks follow a five-state lifecycle: P ENDING → R EADY → Q UEUED → RUNNING → C OMPLETED.
C. DAG Workflow Model ncsim includes a React/D3 web-based visualization frontend with three views: a network topology view showing nodes, Workflows are modeled as directed acyclic graphs (DAGs) links, and active transfers; a Gantt chart of task execution where nodes represent tasks and edges represent data depenand transfer timelines per node; and an animated replay dencies. Each edge e = (ti , tj ) carries a data payload of size with playback controls for observing bandwidth recalculation de (in MB) that must be transferred from the node executing cascades. Simulation output is written in JSONL trace format ti to the node executing tj before tj can begin. If ti and tj are (one JSON object per event) for integration with external placed on the same node, the transfer is instantaneous (zero analysis tools. The command-line interface supports batch cost). DAGs are injected at specified simulation times.
where N0 is the noise floor. The path loss exponent n ranges The scheduler receives a NetworkSnapshot, an im- from 2 (free-space) to ≥ 3.5 (dense indoor). The PHY data rate is selected from the appropriate 802.11 mutable view of node capacities, link bandwidths, queue depths, MCS table based on the computed SNR: and active transfers, and returns a PlacementPlan mapping each task to a node. ncsim includes four schedulers: Rℓ = max{rk : SNRℓ ≥ SNRmin,k } (4) • Manual: Uses pinned_to annotations from the YAML. This selects the highest-rate MCS whose minimum SNR • RoundRobin: Cycles through nodes, respecting pin conrequirement is met, producing a discrete rate staircase, a key straints. feature that continuous-rate models fail to capture. • HEFT/CPOP: Adapted from the SAGA scheduling li2) Carrier Sensing and Conflict Graph: The carrier sensing brary [10] via an adapter that constructs a fully-connected range dCS is the maximum distance at which a transmission virtual network with actual bandwidths for connected pairs triggers the clear channel assessment (CCA) mechanism: and near-zero bandwidth for unreachable pairs, causing the Ptx −θCCA −PL(d0 ) scheduler to naturally avoid infeasible placements. 10 n dCS = d0 · 10 (5) The SAGA adapter can be easily extended to include any The conflict graph GC = (L, EC ) is defined over links. scheduler from the SAGA library [15]. Without RTS/CTS, two links conflict if either transmitter can sense any node of the other link. With RTS/CTS, any node of E. Routing and Bandwidth Sharing one link sensing any node of the other creates a conflict. Three routing models determine the path for data transfers: 3) CSMA Bianchi Model (csma_bianchi): The dynamic • Direct: Only allows transfers over explicit single-hop links. model separates two interference mechanisms. Let A be the set • WidestPath: Modified Dijkstra maximizing bottleneck band- of currently active links, C = A ∩ N (ℓ) the active contending ℓ width. neighbors, and Hℓ = (A \ N (ℓ)) \ {ℓ} the active hidden • ShortestPath: Standard Dijkstra minimizing total latency. terminals. a) Contention factor.: The number of contending stations Multi-hop transfers use store-and-forward semantics: the is n = 1 + |Cℓ |. Using Bianchi’s saturation throughput effective bandwidth is the minimum (bottleneck) across all links analysis [9], the MAC efficiency η(n) is computed from the in the path, and latency is the sum. When multiple transfers coupled equations for transmission probability τ and collision share a link, each receives a fair share: probability p: Bℓ · f (ℓ) Bper-flow (ℓ) = (1) 2(1 − 2p) Nℓ (6) τ= (1 − 2p)(Wmin + 1) + p Wmin (1 − (2p)m ) where f (ℓ) is the interference factor and Nℓ is the number of p = 1 − (1 − τ )n−1 (7) concurrent flows on link ℓ. When a transfer starts or completes, all affected transfers are recalculated and their completion with minimum contention window W min = 16 and maximum events rescheduled. backoff stage m = 6. We solve numerically via bisection D. Scheduling Framework
F. WiFi / 802.11 Model The WiFi model replaces static link bandwidths with rates derived from RF parameters, and models contention and hidden terminal interference using physically-grounded analytical models. The physical-layer and MAC models draw on standard 802.11 analysis: path loss and MCS selection are standard; carrier-sensing range and conflict graph construction are adapted from the literature; the Bianchi contention model and capture-threshold hidden terminal factor are our specific contributions to this simulation framework. The following subsections formalize these mechanisms. 1) Physical Layer: The received power at distance d uses log-distance path loss: d PL(d) = PL(d0 ) + 10 n log10 (2) d0 Prx (d) = Ptx − PL(d) (3) where PL(d0 ) is the Friis free-space loss at reference distance d0 = 1 m, n is the path loss exponent, and Ptx is the transmit power. The signal-to-noise ratio is SNR = Prx − N0 (in dB),
(Section VI-B) to obtain the equilibrium (τ ∗ , p∗ ). The MAC efficiency is then: η(n) =
Psuccess · Tsuccess E[Tslot ]
(8)
where Psuccess , Tsuccess , and E[Tslot ] are the probability, duration, and expected slot time for successful transmissions, respectively. Each contending station receives a fair share η(n)/n of the channel capacity. b) Hidden terminal factor.: Hidden terminals transmit simultaneously with link ℓ, causing interference at the receiver. The SINR is: ! (lin) Prx SINRℓ = 10 log10 (9) P (lin) (lin) N0 + j∈Hℓ Pj In 802.11, each frame is transmitted at a pre-selected MCS and either decoded successfully or lost entirely; there is no fallback to a lower MCS during reception [32], [33]. The MCS rateselection thresholds include operating margins (implementation loss, fading margin, AGC settling) that are not required for frame decoding. The decode threshold for a given MCS is
therefore lower than the selection threshold by a capture margin ∆: θdecode = θselect − ∆ (10) We use ∆ = 5 dB, consistent with the gap between ns-3’s IdealWifiManager selection and its TableBasedErrorRateModel decode thresholds, and with measured capture thresholds of 4–10 dB in the literature [34]. The hidden terminal factor is: ( 1.0 if SINRℓ ≥ θdecode fHT (ℓ) = (11) 0.01 otherwise (frame failure)
TABLE V: Experiment 1: Link length vs. data rate (802.11ax, 5 GHz). Dist(m)
SNR(dB)
MCS
Pred(MB/s)
Sim(MB/s)
1 12 30 50 75 105 140
68.58 36.20 24.27 17.61 12.33 7.94 4.19
11 9 5 3 2 0 n/a
17.925 14.338 8.600 4.300 3.225 1.075 0.000
17.925 14.338 8.600 4.300 3.225 1.075 0.000
a local recomputation within the conflict-graph neighborhood. When a transfer starts or completes on link ℓ, the engine identifies all active transfers whose links share a conflictgraph neighbor with ℓ; for each, it recomputes the contendingη(n) f (ℓ) = fHT (ℓ) · (12) neighbor and hidden-terminal counts |Cℓ |, |Hℓ |, recalculates n the combined interference factor f (ℓ) (Equation (12)), and clamped to [0.01, 1.0]. When transfers start or complete, updates the end-to-end bottleneck bandwidth. If the new ncsim recalculates f (ℓ) for all active transfers sharing a bandwidth differs, the in-flight completion event is cancelled conflict graph neighbor with the affected link, and reschedules and rescheduled from the remaining data. The cascade can ripple to neighbors-of-neighbors but is bounded by conflicttheir completion events accordingly. graph degree (4–12 for our grid topologies). V. S IMULATION E NGINE Overall complexity is O(E · K · log N ) where E is the total number of events, K the average neighborhood size, and N the In this section, we describe the discrete-event simulation enmaximum pending-queue size. Each simulation in our 108-run gine that forms the core of ncsim. The engine orchestrates the study completes in under 2 seconds on commodity hardware. interplay between task execution, data transfer, and interference dynamics through an event-driven architecture. VI. VALIDATION c) Combined factor.: The total interference degradation combines both effects multiplicatively:
A. Event Processing ncsim uses an event-driven DES with a min-heap priority queue. Six event types are processed in priority order at each simulation time: 1) DAG I NJECT: Invokes scheduler, initializes task states 2) TASK C OMPLETE: Frees node, triggers output transfers 3) T RANSFER C OMPLETE: Delivers data, checks readiness 4) TASK R EADY: Starts task or enqueues if node busy 5) TASK S TART: Begins execution, schedules completion 6) T RANSFER S TART: Acquires link bandwidth, schedules completion The priority ordering at the same simulation time is chosen for causal correctness: completions are processed before starts, and task completions before transfer completions, so that a freed node is immediately available to any task that becomes ready at the same instant. Stale events are cancelled via lazy deletion and discarded when they reach the head of the queue; all times are rounded to microsecond precision (10−6 s) for deterministic cross-platform behavior. B. Bandwidth Recalculation Cascade The most technically subtle aspect of the engine is the bandwidth recalculation cascade: wireless interference means the effective bandwidth of a link depends on which other links are simultaneously active, and that set changes continuously as transfers begin and end. ncsim therefore follows a simple principle of recalculation: any change in link activity triggers
We defend ncsim’s flow-level model with a three-stage validation ladder. Rung 1 (Internal). Nine controlled experiments verify that link-rate, contention, and hidden-terminal implementations match their analytical definitions exactly. Rung 2 (Literature). We reproduce Bianchi’s Table III and Figure 6 to confirm the MAC analytical component [9]. Rung 3 (Ground truth). We cross-validate against ns-3 [2] packetlevel simulation in contention and hidden-terminal regimes, obtaining a 4% mean error across 20 seeds. Each rung closes a different credibility gap: Rung 1 rules out implementation bugs, Rung 2 rules out analytical mis-modeling, and Rung 3 rules out flow-level abstraction error relative to a packet-level reference. A. Internal Verification Nine controlled experiments, each isolating a specific WiFi model component, match analytical predictions exactly (zero error to the precision reported). We present three representative experiments in detail; the remaining N-way contention scaling test appears in Section VI-B. 1) Experiment 1: Link Length vs. Data Rate: A single link between two nodes at varying distances from 1 m to 140 m. Table V shows selected results. The simulated rate matches the analytically predicted MCS-selected rate at every distance. At 140 m the SNR (4.19 dB) falls below MCS 0 (5 dB threshold), correctly yielding zero rate. Figure 2 plots the characteristic staircase pattern: rate is constant within each MCS band and drops discretely at each SNR threshold.
Fig. 2: Experiment 1: PHY data rate vs. link distance showing discrete MCS transitions (802.11ax, 5 GHz, n=3). Red dots mark experimentally verified data points from Table V.
2) Experiment 2: Parallel Link Separation: Two parallel 30 m links separated vertically by distances from 5 m to 200 m. Figure 3 illustrates the three interference regimes. At separation ≤ 70 m, all node pairs are within the carrier sensing range (71.2 m), so the links contend via Bianchi’s model: each gets η(2)/2 ≈ 0.44 of the base rate 8.6 MB/s = 3.79 MB/s. At separation ≥ 75 m, the links become hidden terminals, and SINR degradation determines the effective rate. Notably, the effective rate drops at the CS range boundary: from 3.79 MB/s (contention) to 3.23 MB/s (hidden terminal at 75 m), before recovering at larger separations. This nonmonotonic behavior is the classic hidden terminal effect: within sensing range, links coordinate via CSMA/CA and time-share the channel fairly (each receiving 44% of the full 8.6 MB/s); just outside sensing range, links transmit simultaneously without coordination, and the resulting mutual interference degrades each receiver’s SINR enough to force a lower MCS rate (from MCS 5 to MCS 2). The hidden terminal regime is thus worse than fair contention sharing at close range. As separation increases further, interference power diminishes: SINR recovers to MCS 3 (4.3 MB/s) at 90 m and MCS 4 (6.45 MB/s) at 130 m. All 15 data points match predictions exactly. 3) Experiment 4: Three Parallel Links: This experiment extends the two-link topology of Experiment 2 to three parallel 30 m links placed at y = 0, y = s, and y = 2s (links A, B, C), each carrying a 10 MB transfer. Figure 4 illustrates the topology with separation s as the independent variable. As s increases, three interference regimes emerge: (i) allconflict (s ≤ 35.6 m): all three pairs are within dCS , each link gets Rbase · η(3)/3; (ii) mixed (35.6 < s ≤ 71.2 m): adjacent pairs (A–B, B–C) contend via Bianchi, while the outer pair (A–C at distance 2s) are hidden terminals, creating asymmetric rates; and (iii) all-hidden (s > 71.2 m): no conflict-graph edges, each link sees the others purely as hidden terminals. Because A/C and B generally have different rates, one group finishes first, and the remaining links’ interference conditions change. The analytical prediction accounts for this multi-phase behavior.
Fig. 3: Experiment 2: effective per-link rate vs. separation for two parallel 30 m links. The non-monotonic dip at the CS boundary (71.2 m) is the hidden-terminal effect, analyzed in the body text. n4
Link C
n5
s n2
Link B
n3 2s
s ≤ 35.6 m: all conflict 35.6 < s ≤ 71.2 m: mixed s > 71.2 m: all hidden
s n0
Link A
n1
30 m
Fig. 4: Experiment 4 topology: three parallel 30 m links at variable separation s. As s increases, the interference regime transitions from all-conflict to mixed (adjacent pairs contend, outer pair A–C are hidden terminals) to all-hidden.
Table VI shows the results. All 11 test points match exactly. In the mixed regime at s=70 m, an interesting crossover occurs where A/C become faster than B, because the outer links benefit from their mutual hidden-terminal distance while B contends with both neighbors. This experiment validates the model’s ability to correctly compose Bianchi contention and SINR degradation in a single topology with asymmetric interference conditions and multi-phase dynamic recalculation. 4) Additional Validation Experiments: Five additional experiments validate: (3) two-transmitter shared-receiver topologies, (5) staggered transfer starts with dynamic recalculation, (6) perlink bandwidth sharing with multiple flows, (8) five-link hidden terminal cascades with different data sizes, and (9) combined bandwidth sharing with hidden terminal interference. All pass. B. External Validation Against Bianchi (2000) Internal validation confirms self-consistency but does not establish that our implementation of Bianchi’s equations is correct. We therefore reproduce the numerical results from Bianchi’s original paper [9] using his exact parameters: FHSS
TABLE VI: Experiment 4: Three parallel links at varying separation. In the mixed regime the middle link B contends with both neighbors while outer links A, C contend only with B and see each other as hidden terminals. s(m)
Regime
Pred RA
Sim RA
Pred RB
Sim RB
10 35 40 50 70 75 100 150
all-conf all-conf mixed mixed mixed all-hid all-hid all-hid
2.461 2.461 1.861 2.174 2.840 3.225 4.300 6.450
2.461 2.461 1.861 2.174 2.840 3.225 4.300 6.450
2.461 2.461 2.461 2.461 2.720 2.867 3.822 5.160
2.461 2.461 2.461 2.461 2.720 2.867 3.822 5.160
A=C by symmetry in all cases. Rates in MB/s.
TABLE VII: Reproduction of Bianchi [9] Table III: normalized saturation throughput S for W =32, m=3. n
Computed
Published
Rel. Error
2 3
0.847311 0.836828
0.8473 0.8368
0.001% 0.003%
Fig. 5: Reproduction of Bianchi [9] Figure 6: normalized saturation throughput vs. number of stations for two (W, m) configurations. The W =128 curve’s non-monotonicity between n=5 and n=10 is consistent with Bianchi’s published results. Digitized data points overlay our curves to within 0.34% relative error, confirming faithful reproduction.
1 Mbps basic access (no RTS/CTS), with slot duration 50 µs, SIFS 28 µs, DIFS 128 µs, propagation delay 1 µs, payload 8184 bits, MAC header 272 bits, PHY header 128 bits, and ACK TABLE VIII: N-way Bianchi contention scaling (30 m links at 112 bits. 5 m separation). η(n) is the Bianchi MAC efficiency. 1) Table III Reproduction: Table VII compares our comn η(n) η(n)/n Pred(MB/s) Sim(MB/s) puted normalized saturation throughput S against the values 2 0.881 0.440 3.787 3.787 published in Bianchi’s Table III for W =32, m=3. At n=2, our 3 0.859 0.286 2.461 2.461 solver computes S = 0.847311 versus the published 0.8473 4 0.837 0.209 1.799 1.799 (relative error 0.001%). At n=3, we compute S = 0.836828 5 0.818 0.164 1.407 1.407 6 0.802 0.134 1.149 1.149 versus 0.8368 (relative error 0.003%). These sub-basis-point 7 0.788 0.113 0.968 0.968 differences are consistent with rounding in the published table. 8 0.726 0.091 0.780 0.780 We solve the coupled equations (Equations (6) and (7)) by bisection rather than fixed-point iteration, which can oscillate when the mapping slope exceeds unity; with ϵ = 10−12 Rung 3 cross-validates the combined model (path loss + MCS convergence is guaranteed in at most 40 steps. 2) Figure 6 Reproduction: Figure 5 reproduces Bianchi’s selection + CSMA/CA + hidden terminal capture) against Figure 6 throughput curves for W =32, m=5 and W =128, ns-3 [2], a packet-level simulator that models 802.11 at full m=3 across n=5 to n=50 stations. Both curves match the protocol fidelity. Both experiments use 802.11ax at 5 GHz on a 20 MHz expected monotonic throughput decay; the W =128 curve channel with parameters matched between ncsim’s RFConfig reproduces the slight non-monotonicity between n=5 and defaults and ns-3’s ConstantRateWifiManager (see Tan=10 consistent with Bianchi’s published results. Data points ble IX for the full list). Critically, A-MPDU is disabled to digitized from Bianchi’s original figure overlay our computed match Bianchi’s single-frame assumption. Each ns-3 point is curves to within 0.34% relative error. the mean over 20 seeds (30 s per run, first 2 s discarded as 3) N-Way Contention Scaling: To confirm that the Bianchi warmup). model scales correctly within the full simulation loop, we place 1) Experiment 1: Contention Scaling: We place n ∈ n ∈ {2, . . . , 8} parallel 30 m links at 5 m separation (all within {1, . . . , 8} co-located STA-AP link pairs at 30 m link length carrier-sensing range), each carrying a 10 MB transfer. and 5 m vertical separation, all well within the 71.2 m carrierTable VIII confirms the Bianchi solver produces correct sensing range, creating a complete conflict graph. Each STA throughput predictions when embedded in the full simulation sends saturated UDP traffic to its AP. Figure 6(a) overlays engine with real RF parameters and dynamic recalculation. ncsim’s Bianchi prediction Rbase · η(n)/n against the ns-3 C. Cross-Validation Against ns-3 per-station goodput. Rungs 1 and 2 establish internal self-consistency and ncsim’s Bianchi model, which accounts for PHY overhead faithful reproduction of Bianchi’s analytical framework, but (preamble, SIFS, ACK) in the efficiency computation, tracks nsall comparisons are against formulas ncsim itself implements. 3 closely across all station counts. At n=1, the solo goodput
TABLE IX: Aligned parameters for ns-3 cross-validation.
Fig. 6: Cross-validation of ncsim against ns-3. (a) n-way saturated goodput; (b) two-link throughput vs. separation. ncsim tracks ns-3 within 0.3–11% across all regimes. Parameters per Table IX; each ns-3 point: mean ± 95% CI over 20 seeds.
Parameter
ncsim
ns-3
TX power Frequency Channel width Path loss exp. Ref. loss (1 m) Noise floor CCA threshold CWmin CWmax A-MPDU Guard interval
20 dBm 5 GHz 20 MHz 3.0 46.4 dB −95 dBm −82 dBm 16 1024 disabled 3200 ns
TxPowerStart/End = 20 Band 5 GHz, ch. 36 ChannelSettings Exponent = 3.0 ReferenceLoss = 46.4 RxNoiseFigure = 6 CcaEdThreshold = -82 MinCw = 15 MaxCw = 1023 MaxAmpduSize = 0 GuardInterval = 3200
TABLE X: Scheduler inputs. No scheduler observes interference. Scheduler
Planner Inputs Network View
Intf?
predictions differ by only 0.3% (3.78 vs. 3.77 MB/s). The Manual Pin annotations N/A No maximum error of 7.6% occurs at n=7, where the Bianchi fixedRoundRobin Node list N/A No † point approximation slightly overestimates MAC efficiency. The HEFT DAG, Cv , Bℓ Full virtual net No CPOP DAG, Cv , Bℓ Full virtual net† No mean error across all n is 4.0%. Both curves exhibit the same † Actual BW for reachable pairs; 0.001 MB/s for unreachable. monotonic decay shape with Pearson correlation r > 0.999. All 95% confidence intervals are below ±0.02 MB/s, confirming that 30 s of saturated traffic reaches steady state. 2) Experiment 2: Separation Sweep: Two parallel 30 m links four subsections that follow build the evidence progressively: are placed at vertical separation s ∈ {10, 20, . . . , 200} m. As s routing interactions with interference (Section VII-B), magniincreases beyond the 71.2 m carrier-sensing boundary, the links tude of interference impact (Section VII-C), rank inversions in transition from Bianchi contention (symmetric time-sharing at a 108-run factorial (Section VII-D), and sensitivity analyses η(2)/2) to the hidden terminal regime, where simultaneous delineating an interference danger zone, the parameter regimes transmissions may corrupt frames at the receiver. ncsim’s where interference is most consequential (Section VII-E). All experiments use 802.11ax at 5 GHz with a path loss expocapture-threshold model (Equation (10)) predicts a throughput nent of n = 3 (except where explicitly varied), heterogeneous dip at the CS boundary: per-link rate drops from 1.94 MB/s compute capacities (80–300 units/s), 10 MB data payloads per (contention) to 1.50 MB/s (hidden terminal frame loss) before DAG edge, and deterministic seed 42. recovering sharply at s = 120 m when the interferer’s power Three DAG structures of increasing complexity are used falls below the capture threshold and frames are decoded across all experiments: successfully at the full solo rate (3.78 MB/s). Figure 6(b) • Small (5 tasks): Fork-join, T0 → {T1 , T2 , T3 } → T4 . overlays ns-3 results. ns-3 confirms the qualitative behavior across all regimes. In • Medium (10 tasks): Diamond, T0 → {T1 –T4 } → {T5 –T8 } → T9 with selective cross-links between layers. the contention zone (s ≤ 70 m), ns-3 goodput is stable at 1.92– 2.06 MB/s (1–6% from ncsim). At the CS boundary (s = • Large (20 tasks): Multi-level pipeline, T0 → 4 → 6 → 6 → 3 tasks per layer with sparse inter-layer connections. 72 m), ns-3 exhibits a throughput dip to 1.34 MB/s, confirming ncsim’s predicted dip direction and location (11% error). In All tasks have compute_cost = 500 and all edges have the hidden terminal zone (s = 72–100 m), ncsim’s capture- data_size = 10 MB (except where varied in Section VII-E). threshold model predicts 1.50 MB/s and ns-3 measures 1.34– 1.50 MB/s (0.5–11% error). At large separations (s ≥ 120 m) A. Scheduler Information and Fairness Both the interference-free and interference-aware modes where interference power falls below the capture threshold, both models show recovery: ncsim predicts the full solo rate of present an identical NetworkSnapshot to the scheduler, 3.78 MB/s and ns-3 reaches 3.62–3.77 MB/s (0.3–4.4% error). containing the same WiFi-derived link bandwidths (Table X). The ns-3 simulation scripts, Dockerfile for reproducible No scheduler sees the conflict graph or contention factors; builds, and all raw results are included in the paper’s supple- these are runtime phenomena computed after the schedule has been committed. Any difference in makespan is therefore mentary repository under paper/ns3/. attributable solely to interference that the scheduler could not VII. E XPERIMENTAL E VALUATION anticipate. The central finding of this paper, made possible by ncsim, is that ignoring wireless interference produces systematically B. Routing Strategy Comparison wrong scheduler rankings in over a quarter of scenarios tested Because multi-hop routing determines contention domains, — a comparison no prior workflow or edge simulator supports we first establish how routing strategies interact with interfernatively, and which ncsim is designed to make routine. The ence before evaluating schedulers. We compare widest-path
TABLE XII: Interference impact: makespan (seconds) without interference vs. with csma_bianchi, using shortest-path routing. HEFT and CPOP produce identical placements on the 5-task DAG but diverge as DAG complexity grows.
Fig. 7: Link utilization under widest-path (left) vs. shortest-path (right) routing on a 4×4 grid mesh with a 20-task DAG. Widestpath concentrates 9–10 flows on an 8-hop perimeter corridor; shortest-path spreads traffic across 12 links with shorter routes, reducing makespan by 1.9× under CSMA contention. TABLE XI: Routing comparison: makespan (seconds) for widest-path (W) vs. shortest-path (S) under HEFT with csma_bianchi. Network
DAG
W (s)
S (s)
Winner
2×2 (4 nodes)
5 tasks 10 tasks 20 tasks
15.38 32.60 88.13
15.38 32.50 64.51
Tie Shortest Shortest
Net. DAG None
HEFT Bian.
Slow. None
CPOP Bian.
Slow.
5T 2×2 10T 20T
11.43 18.76 27.50
15.38 32.50 64.51
+35% 11.43 +73% 18.76 +135% 29.53
15.38 41.32 70.96
+35% +120% +140%
5T 3×3 10T 20T
8.43 12.76 17.11
19.06 35.16 96.70
+126% 8.43 19.06 +176% 13.65 52.01 +465% 19.98 104.24
+126% +281% +422%
5T 4×4 10T 20T
8.93 12.88 +44% 8.93 12.88 +44% 15.02 827.23 +5406% 15.02 827.23 +5406% 21.75 794.39 +3553% 20.65 873.26 +4129%
shortest-path, a 24× difference, because the widest paths route transfers through 3–4 hops across the full grid diameter, creating overlapping contention domains that reduce effective bandwidth to a fraction of the solo rate. C. Interference Impact Analysis
Before asking whether interference changes scheduler rankings, we first quantify whether it changes absolute makespans 3×3 (9 nodes) enough to matter. We measure the impact of CSMA/CA inter5 tasks 315.20 12.88 Shortest ference by running each of the nine grid-network scenarios with 4×4 (16 nodes) 10 tasks 1396.9 827.23 Shortest the interference-aware model versus the interference-free model, 20 tasks 1703.4 794.39 Shortest both using shortest-path routing and HEFT. As detailed in Section VII-A, both modes present identical NetworkSnapshot inputs to the scheduler; the only difference is the presence and shortest-path routing under HEFT scheduling with the or absence of runtime contention and hidden-terminal effects. interference-aware model across grid mesh networks of three Table XII shows slowdowns ranging from 35% to 5,406%, sizes (2×2, 3×3, 4×4) and three DAG complexities (5, 10, and large enough that the interference-free model is objectively 20 tasks). All links use 40 m grid spacing with heterogeneous unreliable for scheduler selection in these regimes. compute capacities (80–300 units/s). Key findings. Interference impact ranges from 35% to over Figure 7 shows the resulting link utilization for each strategy. 5400% across all configurations. Several patterns emerge: Link color and thickness indicate the number of bidirectional data flows traversing each link. Widest-path routing funnels • No configuration escapes contention entirely. Even the smallest scenario (2×2, 5 tasks) shows a 35% slowdown, nearly all traffic through an 8-hop perimeter corridor (nodes because the Bianchi MAC overhead reduces effective through0–1–2–6–10–14–13–12), loading each link with 9–10 flows put whenever links share the channel. and leaving the right half of the network idle. Shortest-path • Denser networks amplify interference. The 3×3 grid (32 routing distributes traffic across 12 links with shorter routes links) shows 126–465% slowdown, while the 4×4 grid (68 (avg 3.1 hops vs. 4.5), spreading load more evenly. Under links) shows up to 5406%. More links create larger conflict CSMA contention, widest-path’s flow concentration produces neighborhoods. severe airtime competition: its makespan is 1341 s compared to • Dense interference creates cascading delays. In the 4×4 712 s for shortest-path (1.9× slower). The result illustrates that grid, HEFT distributes tasks across 16 nodes assuming single-flow optimal routing (maximizing bottleneck bandwidth) uncontested bandwidth. During execution, many simultabecomes counterproductive when multiple concurrent transfers neous transfers contend, reducing effective rates and causing compete for shared wireless airtime. HEFT’s schedule to become severely suboptimal. Key findings. Shortest-path routing wins in 7 of 9 configurations with 2 ties. The advantage is most pronounced in • CPOP shows equal or worse slowdowns. CPOP matches the 4×4 grid, where widest-path routing selects longer paths HEFT on the 5-task DAG (identical placements), but exhibits with higher bottleneck bandwidth but incurs substantially more higher slowdowns on larger DAGs in the 2×2 and 3×3 wireless interference due to multi-hop transmissions traversing grids (e.g., 281% vs. 176% for 10 tasks on 3×3). CPOP’s more contention domains. In the 4×4 grid with 5 tasks, widestcritical-path-based allocation concentrates communication path achieves a makespan of 315.2 s compared to 12.9 s for along fewer paths, making those paths more vulnerable to 5 tasks 10 tasks 20 tasks
19.06 79.88 142.94
19.06 35.16 96.70
Tie Shortest Shortest
contention. In the 4×4 grid, both schedulers suffer extreme slowdowns. These results demonstrate that ignoring wireless interference in scheduling can lead to order-of-magnitude performance prediction errors, motivating the physically-grounded model in ncsim. D. Scheduler Comparison and Rank Inversions The interference impact results above suggest a deeper question: does ignoring interference merely produce inaccurate makespan predictions, or does it lead to wrong choices among schedulers? To answer this, we execute a full factorial comparison: 3 networks × 3 DAGs × 3 schedulers (HEFT, CPOP, RoundRobin) × 2 routings × 2 interference models = 108 simulation runs. All runs use 802.11ax at 5 GHz, heterogeneous compute capacities, and seed 42. For each of the 18 (network, DAG, routing) triples, we identify the best scheduler under each interference model. A rank inversion occurs when the winning scheduler changes Fig. 8: Scheduling regret ratios. Each bar shows the ratio between the interference-free and interference-aware models. of the interference-free-optimal makespan (scheduler chosen The scheduling regret is the relative performance penalty under the interference-free model, run under the interferencefrom deploying the interference-free-optimal scheduler in the aware model) to the oracle makespan (best scheduler under presence of interference. interference). A ratio of 1.0 indicates zero regret; red bars Table XIII presents makespan ratios for each scheduler mark rank inversions where the interference-free choice is relative to the best under the interference-aware model; a ratio suboptimal. of 1.00 denotes the optimal choice. The key statistics are: • Rank inversion rate: 27.8% (5 of 18 triples). • Mean relative regret: 20.2% across all 18 triples. under the interference-aware model, these concurrent transfers • Maximum relative regret: 168.3% (4 × 4 grid, 10-task contend on overlapping conflict graph neighborhoods: each DAG, widest-path: HEFT chosen under the interference-free transfer’s effective bandwidth drops to a fraction of its solo model gives 1396.9 s, but round-robin achieves 520.6 s under rate as the Bianchi model allocates channel time among the interference-aware model). contenders. The resulting makespan increases to 1,396.9 s, a HEFT dominates under interference-free models. Under 94× blowup. In contrast, round-robin achieves 520.6 s under the interference-free model, HEFT or CPOP wins in all 18 the same interference model. Although round-robin makes no triples. This is expected: both algorithms optimize the critical attempt to optimize the critical path, its placement pattern path by distributing tasks across nodes to maximize parallelism, generates fewer concurrent transfers, resulting in less severe assuming uncontested bandwidth. The sophisticated scheduling contention. The scheduling regret, the penalty for choosing logic of HEFT and CPOP provides clear advantages when the HEFT based on the interference-free evaluation, is 168%. A researcher evaluating these schedulers without interference network behaves as these algorithms assume it will. Round-robin wins in large networks under interference. modeling would confidently select HEFT, unaware that it In the 4 × 4 grid with the interference-aware model and widest- produces 2.7× worse performance than a round-robin baseline. Routing modulates the effect. Shortest-path routing mitipath routing, round-robin wins for all three DAG sizes, a striking reversal. The mechanism is clear: HEFT spreads tasks gates rank inversions in some cases by reducing the number of across many of the 16 available nodes to exploit parallelism, but hops per transfer and thus the number of contention domains this creates many concurrent multi-hop transfers that contend traversed. The 4 × 4 / 5-task scenario shows a rank inversion on shared wireless channels. Round-robin’s simpler placement under widest-path routing (60% regret) but not under shortestcycles through nodes in order, which tends to concentrate work path (zero regret). However, shortest-path does not eliminate on nearby nodes with fewer concurrent transfers and thus less inversions entirely: in the 4 × 4 / 10-task scenario, the inversion persists even with shortest-path routing (98% regret), because contention. To illustrate this mechanism concretely, consider the most the DAG is large enough to generate concurrent transfers even dramatic rank inversion: the 4 × 4 grid with 10 tasks and along short paths. widest-path routing. Under the interference-free model, HEFT Figure 8 visualizes the regret ratio (naive makespan divided achieves a makespan of 14.9 s by distributing tasks across by oracle makespan) for all 18 triples. The 13 triples at 1.0 many of the 16 nodes, creating multiple concurrent inter-node show zero regret; the 5 bars above 1.0 are rank inversions, transfers that exploit the assumed link bandwidths. However, with the 4 × 4 / 10-task / widest-path case reaching 2.68×.
TABLE XIII: Makespan ratios under csma_bianchi relative to the best scheduler for each (network, DAG, routing) triple. A ratio of 1.00 denotes the optimal choice; higher values show how much worse that scheduler performs. “None↓” indicates which scheduler an interference-free evaluation would select. Bold entries mark rank inversions where the interference-free choice is suboptimal. Net.
DAG
H
Widest-path C RR None↓
H
Shortest-path C RR None↓
5T 2 × 2 10T 20T
1.00 1.00 2.71 HEFT 1.00 1.52 2.38 HEFT 1.13 1.00 1.63 CPOP
1.00 1.00 1.00 1.27 1.00 1.10
2.01 HEFT 1.74 HEFT 1.69 HEFT
5T 3 × 3 10T 20T
1.00 1.00 2.00 HEFT 1.19 1.00 8.32 CPOP 1.00 1.79 6.49 HEFT
1.00 1.00 2.00 HEFT 1.00 1.48 13.05 HEFT 1.00 1.08 8.31 HEFT
5T 4 × 4 10T 20T
1.60 1.60 1.00 HEFT 1.00 1.00 2.68 2.68 1.00 HEFT 1.98 1.98 1.01 1.28 1.00 CPOP 1.00 1.10
6.56 HEFT 1.00 HEFT 1.97 CPOP
These results demonstrate the headline capability of ncsim: by jointly modeling scheduling and wireless interference, it corrects scheduler rankings that interference-free evaluation gets wrong. Because prior workflow and edge simulators abstract away wireless contention, this kind of cross-model comparison has not been available, and the policy errors it exposes have remained invisible. E. Sensitivity Analysis The results above demonstrate that wireless interference can dramatically affect scheduler rankings. However, a natural question arises: under what conditions is interference most consequential, and when can it safely be ignored? To address this question, we conduct two sensitivity sweeps that vary key parameters affecting interference severity: the communicationto-computation ratio (data size per DAG edge) and the level of concurrent workload (number of simultaneous DAGs). 1) Communication-to-Computation Ratio: The communication-to-computation ratio (CCR) determines the relative importance of network transfer time versus compute time. We sweep data size per edge across {1, 2, 5, 10, 20, 50, 100} MB on the 3×3 grid with HEFT and shortest-path routing, testing all three DAG types (5, 10, and 20 tasks). Figure 9 shows the interference slowdown as a function of CCR. The results reveal a non-monotonic pattern: slowdown peaks at intermediate CCR values (≈0.3–1.1) and decreases at both extremes. The mechanism differs at each end. At low CCR (1–2 MB), transfers complete so quickly that the probability of temporal overlap between concurrent flows is small, and contention has little opportunity to develop. At very high CCR (50–100 MB), HEFT’s scheduling logic recognizes the enormous transfer costs and collapses tasks onto fewer nodes to avoid inter-node communication entirely, a scheduling adaptation that eliminates contention by eliminating transfers. The interference “danger zone” lies in between, where transfers are long enough to overlap but the scheduler still distributes tasks across multiple nodes. For the 20-task DAG, the peak slowdown of 7.3× occurs at 10 MB per edge, corresponding to
Fig. 9: Interference slowdown vs. CCR (3×3 grid, HEFT, shortest-path). Slowdown peaks at intermediate CCR values where transfers are long enough to contend but not so large that the scheduler collapses tasks onto one node. The 20-task DAG reaches 7.3× at CCR≈ 0.53.
a CCR of approximately 0.5 (where transfer time and compute time are comparable). 2) Multi-DAG Contention: In practice, edge computing platforms rarely service a single workflow in isolation; multiple applications submit DAGs concurrently, and their transfers share the same wireless medium. To evaluate how ncsim captures this multi-tenant scenario, we inject k ∈ {1, 2, 3, 4, 5} identical 5-task fork-join DAGs with 0.5 s stagger on the 3×3 grid (HEFT, shortest-path). Each DAG is scheduled independently, meaning that HEFT optimizes each workflow without knowledge of the others’ transfers. Figure 10 shows that contention scaling is super-linear under csma_bianchi. Without interference, k=5 DAGs produce 2.14× the makespan of k=1 (18.0 s vs. 8.4 s), reflecting the expected linear increase from staggered injection plus queuing at compute nodes. With interference, however, k=5 produces 3.86× the single-DAG makespan (73.5 s vs. 19.1 s). The gap
TABLE XIV: Sensitivity analysis summary. Each row identifies the parameter regime where interference impact is most severe. Experiment
Parameter
Danger Zone
Peak Effect
CCR Multi-DAG
Data size (MB) DAG count k
5–20 MB k≥2
7.3× at 10 MB 4.1× gap at k=5
TABLE XV: Scalability: makespan ratios on a 100-node random geometric graph (312 links, avg. degree 6.2) with 30-, 40-, and 50-task DAGs. Format follows Table XIII. Interference slowdowns range from 48× to 136×. DAG 30T 40T 50T
Fig. 10: Multi-DAG makespan scaling on 3×3 grid (5-task DAGs, HEFT, shortest-path). Contention amplifies superlinearly: the gap between the curves widens from 2.26× (k=1) to 4.08× (k=5).
H
Widest-path C RR None↓
H
Shortest-path C RR None↓
1.24 1.00 2.40 HEFT 1.16 1.00 1.89 HEFT 1.00 1.01 2.04 CPOP 1.00 1.09 2.29 HEFT 1.00 1.59 2.31 HEFT 1.18 1.00 1.46 CPOP
pairs within 80 m WiFi range, yielding 312 undirected links (average degree 6.2). We test 30-, 40-, and 50-task multi-level pipeline DAGs across all three schedulers and both routing strategies (36 runs total). Table XV presents the makespan ratios. Three of six triples between the two curves widens with each additional DAG: the slowdown factor grows from 2.26× at k=1 to 2.98× at k=2 (50%) exhibit rank inversions, an even higher rate than the to 4.08× at k=5, indicating a positive feedback loop. Each 27.8% observed on grid topologies. Interference slowdowns additional DAG contributes its own transfers to the contention are dramatically larger: 48× to 136×, compared to the 1.4×– pool and prolongs the duration of existing transfers (through 54× range on grids. The denser conflict neighborhoods in a reduced effective bandwidth), which in turn increases the 100-node RGG create far more contention than a 4 × 4 grid. Two patterns differ from the grid results. First, CPOP wins temporal overlap with subsequent DAGs. This super-linear scaling is invisible to interference-free models, which predict under interference for both 30-task triples (ratios 1.00 vs. HEFT near-linear growth and would substantially underestimate the at 1.16–1.24), whereas HEFT outperformed the others on the smaller grids. CPOP’s critical-path focus yields placements that makespan of multi-tenant edge deployments. 3) Sensitivity Summary: Table XIV consolidates the findings create fewer concurrent transfers in the dense RGG. Second, across both sensitivity dimensions. Taken together, these results round-robin is consistently worst (ratios 1.46–2.40), unlike the delineate an interference danger zone, the conjunction of 4 × 4 grid where round-robin sometimes won; with 100 nodes, parameter settings under which interference effects are most round-robin’s cyclic placement scatters tasks across distant severe and most likely to change scheduling conclusions. nodes, maximizing multi-hop contention. The full 36-run experiment completes in under 10 minutes on Wireless interference has the greatest impact, and is most likely to produce rank inversions, at moderate communication-to- commodity hardware (single-threaded Python 3.11), confirming computation ratios (5–20 MB payloads per edge) with multiple that the greedy clique approximation (used automatically for the 312-link conflict graph) keeps ncsim tractable at 100+ node concurrent workflows (k ≥ 2). These conditions are not exotic. Data payloads of 5–20 MB scales. The main computational bottlenecks are conflict graph per DAG edge are representative of computer vision pipelines construction (Bron-Kerbosch with greedy fallback for > 50 (transferring image frames between processing stages) and links) and event queue size (grows with concurrent transfers). sensor fusion applications (aggregating data from multiple VIII. C ONCLUSION AND F UTURE W ORK modalities). Multiple concurrent workflows are the norm on ncsim is a lightweight discrete-event simulator combining shared edge platforms. In other words, the interference danger zone corresponds precisely to the deployment scenarios that DAG workflow scheduling with physically-grounded 802.11 motivate edge computing research, which means that tools WiFi models, validated against analytical predictions, Bianchi’s ignoring interference are most unreliable in exactly the settings published results, and ns-3 packet-level simulations. Using ncsim, we show that ignoring wireless interference results where they are most needed. in systematically wrong scheduler rankings. Because prior F. Scalability workflow simulators model the network as fixed-bandwidth To demonstrate that ncsim’s findings generalize beyond links, scheduler comparisons in the literature have not been regular grid topologies, we run a scalability experiment on a able to surface this effect; ncsim enables what is, to our 100-node random geometric graph (RGG): 100 nodes placed knowledge, the first like-for-like comparison of DAG schedulers uniformly in a 500 m × 500 m area with links between all under realistic 802.11 contention, and that comparison reveals
that the interference-free-optimal scheduler is outperformed in 27.8% of grid scenarios and 50% of scenarios on a 100node random geometric graph. Sensitivity analyses show that interference impact peaks at moderate communication-tocomputation ratios and amplifies super-linearly with concurrent workflows, precisely the conditions that characterize wireless edge deployments. Evaluations that ignore wireless interference therefore risk systematically wrong conclusions about which scheduling algorithms are superior. Scope and limitations. ncsim uses a flow-level model, saturation-based Bianchi contention, a capture-threshold hiddenterminal model, deterministic path loss, and synthetic DAGs. These choices suit controlled scheduler evaluation but do not replace packet-level simulation for protocol design, captureeffect research, or mobility studies; extensions to those regimes are future work. Future work also includes: (1) interference-aware scheduling that queries the conflict graph during placement; (2) dynamic rescheduling in response to observed congestion; and (3) extending the ns-3 cross-validation to wider traffic patterns and multihop topologies. ncsim and all experimental configurations are available at https://github.com/ANRGUSC/ncsim. ACKNOWLEDGMENT This work was supported in part by Army Research Laboratory under Cooperative Agreement W911NF-17-2-0196. R EFERENCES [1] W. Shi, J. Cao, Q. Zhang, Y. Li, and L. Xu, “Edge Computing: Vision and Challenges,” IEEE Internet of Things Journal, vol. 3, no. 5, pp. 637–646, Oct. 2016. [2] ns-3 Consortium, “ns-3: A Discrete-Event Network Simulator,” https: //www.nsnam.org/, accessed Mar. 2026. [3] A. Varga and R. Hornig, “An Overview of the OMNeT++ Simulation Environment,” in Proc. ICST SIMUTools, 2008. [4] H. Casanova, A. Giersch, A. Legrand, M. Quinson, and F. Suter, “Versatile, Scalable, and Accurate Simulation of Distributed Applications and Platforms,” Journal of Parallel and Distributed Computing, vol. 74, no. 10, pp. 2899–2917, 2014. [5] H. Casanova, S. Pandey, J. Oeth, R. Tanaka, F. Suter, and R. Ferreira da Silva, “WRENCH: A Framework for Simulating Workflow Management Systems,” in Proc. WORKS Workshop, 2018, pp. 74–85. [6] R. N. Calheiros, R. Ranjan, A. Beloglazov, C. A. F. De Rose, and R. Buyya, “CloudSim: A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms,” Software: Practice and Experience, vol. 41, no. 1, pp. 23–50, 2011. [7] H. Gupta, A. Vahid Dastjerdi, S. K. Ghosh, and R. Buyya, “iFogSim: A Toolkit for Modeling and Simulation of Resource Management Techniques in the Internet of Things, Edge and Fog Computing Environments,” Software: Practice and Experience, vol. 47, no. 9, pp. 1275–1296, 2017. [8] C. Sonmez, A. Ozgovde, and C. Ersoy, “EdgeCloudSim: An Environment for Performance Evaluation of Edge Computing Systems,” Transactions on Emerging Telecommunications Technologies, vol. 29, no. 11, e3493, 2018. [9] G. Bianchi, “Performance Analysis of the IEEE 802.11 Distributed Coordination Function,” IEEE Journal on Selected Areas in Communications, vol. 18, no. 3, pp. 535–547, Mar. 2000. [10] H. Topcuoglu, S. Hariri, and M.-Y. Wu, “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing,” IEEE Trans. Parallel Distrib. Syst., vol. 13, no. 3, pp. 260–274, 2002. [11] T. L. Adam, K. M. Chandy, and J. R. Dickson, “A Comparison of List Schedules for Parallel Processing Systems,” Communications of the ACM, vol. 17, no. 12, pp. 685–690, 1974.
[12] Y.-K. Kwok and I. Ahmad, “Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors,” ACM Computing Surveys, vol. 31, no. 4, pp. 406–471, 1999. [13] G. C. Sih and E. A. Lee, “A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures,” IEEE Trans. Parallel Distrib. Syst., vol. 4, no. 2, pp. 175–187, 1993. [14] J. Coleman and B. Krishnamachari, “Comparing Task Graph Scheduling Algorithms: An Adversarial Approach,” arXiv preprint arXiv:2403.07120, 2024. [15] J. Coleman, B. Krishnamachari, and contributors, “SAGA: Scheduling Algorithms Gathered (software),” https://github.com/anrgusc/saga, 2024. [16] J. Coleman, R. V. Agrawal, E. Hirani, and B. Krishnamachari, “Parameterized Task Graph Scheduling Algorithm for Comparing Algorithmic Components,” arXiv preprint arXiv:2403.07112, 2024. [17] P. Ghosh, Q. Nguyen, P. K. Sakulkar, J. A. Tran, A. Knezevic, J. Wang, Z. Lin, B. Krishnamachari, M. Annavaram, and S. Avestimehr, “Jupiter: A Networked Computing Architecture,” in Proc. UCC Companion, 2021. [18] A. Poylisher, A. Cichocki, K. Guo, J. Hunziker, L. Kant, B. Krishnamachari, S. Avestimehr, and M. Annavaram, “Tactical Jupiter: Dynamic Scheduling of Dispersed Computations in Tactical MANETs,” in MILCOM 2021, 2021. [19] X. Zhao, D. Hu, and B. Krishnamachari, “Design and Experimental Evaluation of Algorithms for Optimizing the Throughput of Dispersed Computing,” arXiv preprint arXiv:2112.13875, 2021. [20] S. Suryavansh, C. Bothra, K. T. Kim, M. Chiang, C. Peng, and S. Bagchi, “I-BOT: Interference-Based Orchestration of Tasks for Dynamic Unmanaged Edge Computing,” arXiv preprint arXiv:2011.05925, 2020. [21] X. Li, M. Abdallah, S. Suryavansh, M. Chiang, K. T. Kim, and S. Bagchi, “DAG-based Task Orchestration for Edge Computing,” in Proc. SRDS, 2022, pp. 23–34. [22] X. Li, M. Abdallah, Y.-Y. Lou, M. Chiang, K. T. Kim, and S. Bagchi, “Dynamic DAG-Application Scheduling for Multi-Tier Edge Computing in Heterogeneous Networks,” arXiv preprint arXiv:2409.10839, 2024. [23] S. Yi, Z. Hao, Q. Zhang, Q. Zhang, W. Shi, and Q. Li, “LAVEA: Latencyaware Video Analytics on Edge Computing Platform,” in Proc. SEC, 2017. [24] W. Zhang, S. Li, L. Liu, Z. Jia, Y. Zhang, and D. Raychaudhuri, “HeteroEdge: Orchestration of Real-time Vision Applications on Heterogeneous Edge Clouds,” in IEEE INFOCOM, 2019, pp. 1270–1278. [25] L. Lin, P. Li, J. Xiong, and M. Lin, “Distributed and Application-aware Task Scheduling in Edge-clouds,” arXiv preprint arXiv:1902.04362, 2019. [26] J. Liang, K. Li, C. Liu, and K. Li, “Joint offloading and scheduling decisions for DAG applications in mobile edge computing,” Neurocomputing, vol. 424, pp. 160–171, 2021. [27] K. Li, “Energy-Constrained DAG Scheduling on Edge and Cloud Servers with Overlapped Communication and Computation,” Journal of Grid Computing, 2024. [28] L. Long, Z. Liu, J. Shen, and Y. Jiang, “SecDS: A security-aware DAG task scheduling strategy for edge computing,” Future Generation Computer Systems, p. 107627, 2025. [29] M. Chiang and T. Zhang, “Fog and IoT: An Overview of Research Opportunities,” IEEE Internet of Things Journal, vol. 3, no. 6, pp. 854– 864, 2016. [30] M. Chiang, S. Ha, I Chih-Lin, F. Risso, and T. Zhang, “Clarifying Fog Computing and Networking: 10 Questions and Answers,” IEEE Communications Magazine, vol. 55, no. 4, pp. 18–20, 2017. [31] K. T. Kim, C. Joe-Wong, and M. Chiang, “Coded Edge Computing,” in IEEE INFOCOM, 2020, pp. 237–246. [32] F. Daneshgaran, M. Laddomada, F. Mesiti, M. Mondin, and M. Zanolo, “Saturation Throughput Analysis of IEEE 802.11 in the Presence of Non Ideal Transmission Channel and Capture Effects,” IEEE Trans. Communications, vol. 56, no. 7, pp. 1178–1188, Jul. 2008. [33] M. Zorzi and R. R. Rao, “Capture and Retransmission Control in Mobile Radio,” IEEE J. Sel. Areas Commun., vol. 12, no. 8, pp. 1289–1298, Oct. 1994. [34] Z. Hadzi-Velkov and B. Spasenovski, “Capture Effect in IEEE 802.11 Basic Service Area Under Influence of Rayleigh Fading and Near/Far Effect,” in IEEE PIMRC, 2002.