Graph partitioning: cutting a service graph with graph theory

Why this scenario exists

A service graph is usually placed as one unit: the whole pipeline runs on one node, so the slowest stage sets the makespan and that node carries all of the work. Splitting the pipeline across tiers is the standard lever, and it is a combinatorial problem, not a scheduling one: where to cut decides both the pipelined execution time and how many intermediate results cross the network.

This scenario fixes the workload and the topology, and shows that the cut alone moves a request between tiers. It is the reference point for comparing any other placement strategy on the same graph, including the genetic one.

What it shows

How to route the subtasks of one request to different nodes. The applications file declares a video analytics pipeline: seven subtasks connected by dependencies, from capture to notify, so one request produces a small graph instead of a single task.

Before the simulation starts, GraphPartitioner cuts that graph:

  1. it finds the weakly connected components of the dependency graph;
  2. inside each component it assigns the heaviest subtasks first to the least loaded partition (longest processing time first);
  3. it then swaps pairs of subtasks between partitions while the swap removes more dependency edges than it adds, and while no partition exceeds the balance tolerance.

GraphPartitioningOrchestrator maps the resulting partitions to the available tiers in the order mist, edge, cloud. The subtask name and the application identifier select the partition at runtime, and the orchestrator picks the next eligible node of that tier in round robin.

The plan printed below is the same graph, so the figure and the console agree: detect and classify are pulled out of the big partition because they are the two heaviest stages, and the four dashed edges are what has to cross the network at runtime.

flowchart LR
    subgraph P2["P0.2 cloud - 1950 MI"]
        capture["capture<br/>200 MI"] --> preprocess["preprocess<br/>600 MI"]
        track["track<br/>800 MI"] --> aggregate["aggregate<br/>300 MI"]
        aggregate --> notify["notify<br/>50 MI"]
    end
    detect["detect<br/>4000 MI, P0.0 mist"]
    classify["classify<br/>2500 MI, P0.1 edge"]
    preprocess -.->|20 kB| detect
    detect -.->|10 kB| classify
    detect -.->|10 kB| track
    classify -.->|50 kB| aggregate
    classDef pulled fill:#cfe8ff,stroke:#333;
    class detect,classify pulled;

The API detail this example exists to show

PureEdgeSim caches an application placement: after the first decision, later tasks of the same device reuse the same destination. A per-subtask plan needs the opposite. The Python orchestrator therefore clears the flag after every decision:

def orchestrate(self, task, application_id: int = 0):
    destination = super().orchestrate(task, application_id)
    task.source_device.application_placed = False
    return destination

The base method returns the destination, so the override must return it too. Without those lines, only the first subtask of each request would follow the plan and the others would go to the same node.

The scenario

examples/graph_partitioning/settings describes:

The orchestrator runs on the device itself (enable_orchestrators=false), so a mist partition can be hosted by the requesting device.

Run it

From the repository root, after pip install -e .:

python examples/graph_partitioning/graph_partitioning.py

What to look for

The console prints the plan before the run starts:

GraphPartitioningOrchestrator - Application 0 (Soft Real-time): 3 partitions, cut 4 edges (720000 bits per request)
  P0.0 ['detect'] (4000 MI)
  P0.1 ['classify'] (2500 MI)
  P0.2 ['capture', 'preprocess', 'track', 'aggregate', 'notify'] (1950 MI)

tasks= 9600 ok= 9600 avg_delay=0.024    cloud=3537 edge=4349 mist=1714 failed(dependency)=   0 energy=47.9631

Change PARTITIONS_PER_COMPONENT to see the trade-off: more partitions spread the load further but cut more edges.

Files

Where to go next