8000 Add LDG: Locality-Dominant Greedy heuristic for VNE under load by GeminiLight · Pull Request #58 · GeminiLight/virne · GitHub
[go: up one dir, main page]

Skip to content

Add LDG: Locality-Dominant Greedy heuristic for VNE under load - #58

Merged
GeminiLight merged 1 commit into
mainfrom
feat/ldg-solver
Sep 2, 2026
Merged

GeminiLight merged 1 commit into
mainfrom
feat/ldg-solver

Conversation

@GeminiLight
Copy link
Copy Markdown
Owner

What

Adds ldg (Locality-Dominant Greedy), a new heuristic solver (LDGSolver, virne/solver/heuristic/ldg.py) for virtual network embedding under heavy load.

How it works

  • Each request is embedded by joint place-and-route: virtual nodes are ordered by total demand — (node resource demand + 2 x adjacent link bandwidth demand) x (degree + 1), descending — so the heavy, well-connected cores are placed first while contiguous capacity remains.
  • Each node goes to the best-scoring feasible substrate candidate, with score(p) = cpu_free(p)^0.25 * adj_bw_free(p) * (1 + 8 * prox(p)), where prox(p) sums (1 + link demand / 25) / (1 + hops) over already-placed virtual neighbors (hop distances from an all-pairs BFS cache; the substrate topology is static).
  • The top five candidates are tried with available_shortest routing; a request that dead-ends is rolled back and retried once in BFS order from its heaviest node before rejection. Locality dominates the score by design: under heavy load link bandwidth is the binding resource, and scattering a request across the substrate costs more than picking a marginally richer node.

Results

Long-term average time revenue on held-out simulation streams (arrival rate 0.12, 1000 v-nets each):

solver seed 42 seed 137 seed 2024 acceptance
ldg (this PR) 9299 9815 9701 ~0.79
pl_rank 8233 8360 8294 —
nrm_rank 7025 7438 7424 —

Why add it

  • At this load LDG exceeds the strongest prior classic heuristic (pl_rank) by +12.9% / +17.4% / +17.0% per stream (mean +15.8%), and closes most of the gap to learned policies: within 2.7% of a trained PPO policy on average.
  • It is purely classical and deterministic: no learned components, no training data dependency, and a single frozen configuration (all hyper-parameters are constants in the class, so every ldg run is the identical algorithm).

Registered as solver_name='ldg', exported from virne.solver.heuristic as LDGSolver.

🤖 Generated with Claude Code

Co-Authored-By: Claude Code noreply@anthropic.com

LDGSolver embeds each request by joint place-and-route: virtual nodes are
ordered by total demand ((node + 2 x adjacent link demands) x (degree + 1),
descending), and each node goes to the best-scoring feasible substrate
candidate, scored by cpu_free^0.25 * adj_bw_free * (1 + 8 * prox), where
proximity to already-placed neighbors is weighted by link demand over hop
distance. The top five candidates are tried with available_shortest routing,
and a request that dead-ends is rolled back and retried once in BFS order
before rejection. Locality dominates the score by design: under heavy load
link bandwidth is the binding resource, and scattering a request across the
substrate costs more than picking a marginally richer node.

Long-term average time revenue on held-out streams (arrival rate 0.12,
seeds 42/137/2024):
  ldg       9299 / 9815 / 9701   (acceptance ~0.79)
  pl_rank   8233 / 8360 / 8294
  nrm_rank  7025 / 7438 / 7424
At this load LDG exceeds pl_rank by +12.9/+17.4/+17.0% per stream and lands
within 2.7% of a trained PPO policy on average, while remaining a purely
classical, deterministic algorithm with no learned components.

Co-Authored-By: Claude Code <noreply@anthropic.com>
@GeminiLight
GeminiLight merged commit 4fd97f2 into main Sep 2, 2026
2 checks passed
@chatgpt-codex-connector
chatgpt-codex-connector Bot commented Sep 2, 2026 •
Copy link
Copy Markdown

Codex Review Summary

This comment shows the latest Codex review activity on this pull request.

Review Status Commit Review trigger
📝 Code Review ✅ Completed 2026-09-02T16:46:43.700244Z 4b1f577 PR opened
ℹ️ About Codex in GitHub

Your team has set up Codex to review pull requests in this repo. Reviews are triggered when you

  • Open a pull request for review
  • Mark a draft as ready
  • Comment "@codex review" or "@codex security review".

Codex reacts with 👀 while any review is running, comments if it has suggestions, and reacts with 👍 once all reviews finish with no findings.

@GeminiLight
GeminiLight deleted the feat/ldg-solver branch September 2, 2026 16:45
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant

0