GraphGulo: گراف زمانمند برای ترافیک شبکه
پایتونخلاصهٔ کاملتر
تو صفحهٔ پروژه اومده که GraphGulo یه پروتوتایپ تحقیقاتیه برای تحلیل ترافیک شبکه: فایلهای خام PCAP و لاگهای فلو رو میگیره و به یه گراف زمانمند ایندکسشده تبدیل میکنه. سؤالی که به گفتهٔ نویسنده شکارچیهای تهدید واقعاً میپرسن اینه که «این IP بین ۱۴:۰۲ تا ۱۴:۰۹ با چه ماشینهایی حرف زده، فقط با دنبال کردن اتصالهای بهترتیب زمانی؟» و کتابخونههای معمول گراف جواب مستقیمی براش ندارن.
فرق اصلیاش پیمایش زمانمحوره: تو هر BFS و Dijkstra، یال (u → v, t) فقط وقتی طی میشه که t بزرگتر یا مساوی زمان رسیدن به u باشه. BFS هم بهجای صف ساده از یه min-heap مرتبشده بر اساس زمان رسیدن استفاده میکنه:
heap = [(t_start, source)]
while heap:
t_arrive, node = heappop(heap)
if node in visited: continue
visited[node] = t_arrive
# Binary search within this node's sorted edge block
for each neighbor v, edge_time t where t_arrive ≤ t ≤ t_end:
push (t, v)ایندکس node_ptr باعث میشه جستوجوی دودویی روی بلوک یالهای هر نود از مرتبهٔ O(log degree) بمونه. هستهٔ سنگین با Rust نوشته شده و از راه PyO3 به پایتون وصله: BFS موازی با Rayon، Dijkstra با bucket-queue برای پنجرههای زمانی کوتاه و شمارش یال با AVX2 (با fallback اسکالر).
نودها هم موقع build بر اساس درجه بین پنج لایه پخش میشن: هابهای خیلی پرترافیک تو ماتریس CSR از SciPy، درجهٔ متوسط تو Roaring Bitmap، نودهای عادی تو آرایهٔ مرتب NumPy و بقیه روی دیسک به شکل Parquet با فشردهسازی LZ4 یا Brotli. تخصیص لایهها برداری و با NumPy انجام میشه و برای ۲۱ میلیون نود حدود ۳ ثانیه طول میکشه.
عددها روی یه PCAP چهاردهگیگابایتی از دیتاست MAWI و یه لپتاپ Core i7 با ۱۶ گیگ رم گرفته شدن: ساخت گراف حدود ۱۰۰ ثانیه با ۱.۴۹ گیگابایت رم، BFS زمانمند ۳.۹ ثانیه، Dijkstra ۱.۴ ثانیه و window query با میانهٔ حدود ۱۵ میلیثانیه؛ NetworkX روی همین دیتاست قبل از تموم شدن بارگذاری رم رو تموم میکنه. نویسنده تأکید داره که این هنوز یه پروتوتایپ V1 هست: گراف بعد از ساخت تغییرناپذیره، اجرا تکماشینه، بکاند GPU نداره و لایهٔ Cold تو مسیر سریع Rust پیمایش نمیشه.
نکات کلیدی:
- تبدیل PCAP و لاگ فلو به گراف زمانمند، با پیمایش time-respecting بهصورت بومی
- هستهٔ Rust با PyO3: BFS موازی Rayon، Dijkstra با bucket-queue و شتاب AVX2
- ذخیرهسازی پنجلایه بر اساس درجهٔ نود، از CSR تا Parquet روی دیسک
- ۱۰۹.۶ میلیون یال با ۱.۴۹ گیگ رم؛ BFS حدود ۴ ثانیه و window query حدود ۱۵ میلیثانیه
- محدودیتها: گراف immutable، تکماشین، بدون GPU و بدون پیمایش لایهٔ Cold
