SDN Firewall Rule Placement — ILP
Dari topologi .gml ke satu slot TCAM di switch
Alur nyata satu rule firewall — dari file topologi & ruleset dimuat, diproses oleh Python/networkx, dioptimasi oleh solver AMPL+CBC, sampai diverifikasi ulang dan disimpan. Setiap cell & rumus di halaman ini diambil langsung dari notebook, bukan ilustrasi.
gulir untuk ikuti alurnya
01 · Input
Dua berkas mentah masuk
Sebelum ada penempatan apa pun, sistem butuh peta jaringan dan daftar rule yang harus ditaruh.
Topologi jaringan Cell 4/13
# nx.read_gml(GML_PATH, label="id") Contoh NSFNET: 13 node, 15 edge "11" EGRESS = "6"
.gml graph + degree node fisik saja
Ruleset firewall Cell 6/13
# snort_{N}.csv 500 – 4007 rule tergantung topologi
.csv priority → kelas Snort 3
02 · Pra-pemrosesan — bukan solver
Python & networkx memetakan jaringan
Tahap ini murni algoritma graph klasik (DFS/BFS) dan aritmetika biasa. Solver ILP belum terlibat sama sekali di sini.
Cari semua jalur ingress → egress Cell 5/13
PATHS = list(nx.all_simple_paths (G, INGRESS, EGRESS))shortest_path_length (G, INGRESS)# Surfnet saja: itertools.islice(nx.shortest_simple_paths(...), k=15)
NSFNET · ABVT · Geant2001 · BICS → all_simple_paths
Surfnet → k-shortest (k=15)
Hitung jatah kapasitas per node, per kelas Cell 6/13
eligible = (path_count[n] >= 1) and (dist_ingress[n] <= threshold[c])if eligible else 0
NSFNET: rumus rata (awal)
ABVT · Geant2001 · BICS · Surfnet: fungsi identik terverifikasi
03 · Optimisasi — di sini solver bekerja
AMPL + CBC memilih penempatan
Satu-satunya titik di seluruh proses di mana ILP benar-benar mencari solusi optimal — bukan sekadar hitung-hitungan.
min w_h·Σ y_n + w_d·Σ dist_n·x_i,n + w_m·Σ m_i·x_i,n
COVERAGE
Tiap jalur wajib ketemu rule minimal di satu node.
CAPACITYCLASS
Jatah TCAM per kelas prioritas tidak boleh terlampaui.
PRIORITYPOSITION
Rule prioritas tinggi wajib dekat ingress (≤ threshold hop).
Solve per seed Cell 7–8/13
status: solved
status: limit (gap dicatat jujur)
selain itu → raise error
04 · Verifikasi independen
Hasil solver dicek ulang, bukan dipercaya mentah
Coverage, kapasitas per node, dan posisi prioritas dihitung ulang secara terpisah dari solver.
Re-check manual Cell 8/13
Σ x_i,n for n in path >= 1 # coverage ulang # kapasitas ulang
05 · Output
Hasil tersimpan, apa adanya
Termasuk gap solver kalau statusnya limit — tidak disamakan dengan hasil optimal terbukti.
summary.json
per_seed.csv
rule_placement.csv
Sebelum & sesudah · NSFNET
Dari 13 node kosong ke 5 node aktif
Posisi node persis sesuai koordinat lon/lat asli di Nsfnet.gml. Data sesudah diambil dari rule_placement.csv seed 42 — bukan simulasi.
Sebelum — graph mentah, y_n belum ditentukan
Sesudah — 5 node aktif, ukuran = jumlah rule
11 (ingress) → 375 rule
6 (egress) → 124 rule
0, 9, 12 → 1 rule masing-masing
node_used : 5.0 (std 0.0)
Contoh konkret · NSFNET
Satu rule, tiga syarat, dua kemungkinan
Rule R1 (prioritas 1, threshold ≤ 3 hop) menyusuri jalur ingress 11 → egress 6.
diterima 3 syarat lolos
ditolak kapasitas kelas 1 penuh