分散非重複サンプリング (DNDS)

Tool
分散非重複サンプリング (DNDS)

分散非重複サンプリング (DNDS)

DNDSは「Distributed Non-Duplicate Sampling with Application on Network-wide Flow Cardinality Estimation」(IEEE ICDCS 2025) の公式実装です。分散ネットワーク環境における非重複サンプリング（NDS）を拡張し、複数のスイッチや観測点にまたがるフロー測定での重複排除と効率的なサンプル収集を目指します。P4 を用いたデータプレーン実装（Tofino / bmv2）と、Python ベースの制御・集計ロジックを含むことがリポジトリから読み取れます。実運用や研究評価に向けた実装例として活用できます。

https://github.com/aka334/DNDS

概要

Distributed Non-Duplicate Sampling (DNDS) は、従来の非重複サンプリング（NDS）を分散ネットワーク環境へ拡張した実装です。ネットワーク全体でのフロー個数推定（flow cardinality estimation）などを目的に、複数のスイッチや観測点が同一フローを重複してサンプリングしてしまう問題を抑制しつつ、効率的にサンプルを収集・集約できる仕組みを提供します。本リポジトリは IEEE ICDCS 2025 で発表された論文の公式実装とされ、P4（Tofino と bmv2）向けのデータプレーンコードと、Python によるソフトウェアコンポーネントを含む構成が確認できます。研究検証や実践的なプロトタイピングに適したリソースを含むことが期待されます。

GitHub

リポジトリの統計情報

  • スター数: 4
  • フォーク数: 0
  • ウォッチャー数: 4
  • コミット数: 5
  • ファイル数: 4
  • メインの言語: Python

主な特徴

  • 分散環境向けの非重複サンプリング（DNDS）の公式実装（論文: IEEE ICDCS 2025）
  • P4 データプレーン実装（Tofino および bmv2）を含むため、ASIC やソフトスイッチ両方で検証可能
  • Python ベースのソフトウェアコンポーネントで制御・集約・評価を実行
  • ネットワーク全体のフロー個数推定など、計測・可観測性の研究に適合

技術的なポイント

DNDS の技術的要点は「分散した観測点での重複サンプリングを防ぎつつ、高い計測精度とスケーラビリティを両立する」点にあります。単一のスイッチ内での非重複サンプリング（NDS）は、フローごとに一度だけサンプルを保持するなどの手法で達成できますが、ネットワーク全体にまたがると同一フローが複数のスイッチで観測され、重複が生じます。DNDS では、分散ポイント間での重複排除を実現するために、パケットやフローの識別子に基づく一貫した選択ルール（例えばハッシュ関数による選択基準やスイッチ間で共有する優先順位付け）を用いることが想定されます。

実装面では P4 を用いたデータプレーンプログラムが中心で、Tofino（商用ASIC）と bmv2（ソフトウェアスイッチ）向けのコードがそれぞれ提供されています。これにより、ハードウェア固有の機能（例えば高性能ハッシュやメモリ管理）とソフトスイッチ上での柔軟な試験の双方で挙動を比較検証できます。Python 側のコンポーネントは制御平面として、スイッチ間の設定配布、サンプルの収集、集約アルゴリズム（推定器への入力変換、重複補正）および評価用のスクリプトを担うと考えられます。

設計上のチャレンジとしては、通信オーバーヘッドを抑えつつ分散合意を取らずに重複を抑制する手法の選定、スイッチの限られたメモリ・処理能力に応じたデータ構造の利用、そして誤差（サンプリングによるバイアスや見逃し）を低減するための補正ロジックの実装が挙げられます。DNDS はこれらに対して、P4 による高速パケット処理と Python による柔軟な集約処理を組み合わせることで現実的なトレードオフを提供している点が注目できます。最終的な評価はハードウェア（Tofino）とソフト（bmv2）の実験結果を比較し、精度・遅延・リソース消費を踏まえた実用性を示すことを目的としていると推察されます。

プロジェクトの構成

主要なファイルとディレクトリ：

  • README.md: file — プロジェクト概要、依存関係、実行方法や論文参照などが記載されている想定
  • Software: dir — Python ベースの制御・集約・評価スクリプトを格納。コントローラ（サンプル集約、推定アルゴリズム、ログ処理）や実験再現用のスクリプトが含まれている可能性が高いです。
  • Tofino: dir — Tofino 向けの P4 プログラムや target 固有の設定（コンパイル／デプロイ用スクリプト、レジスタ初期化手順など）を配置。ハードウェア特有の最適化や制限に対応するコードがあると想定されます。
  • bmv2: dir — bmv2（ソフトスイッチ）向けの P4 コードおよびシミュレーション／実験用のセットアップスクリプト。Tofino 実装との比較検証やローカル環境での実行に使用されます。

各ディレクトリは、データプレーン（P4）と制御平面（Python）の連携を想定した構成になっており、実験用のトポロジや設定ファイル、集約サーバの受け口定義などが含まれている可能性があります。README を起点に依存ライブラリ（P4 コンパイラ、bmv2、Tofino の SDK、Python パッケージなど）を揃え、まずは bmv2 上での動作確認を行い、Tofino での実機評価へ段階的に進めるワークフローが推奨されます。

まとめ

分散ネットワークのフロー計測における重複排除を実践的に検証する公式実装で、P4 と Python の組合せにより研究・評価が容易です。

リポジトリ情報：