ضغط قائمة عناوين IP بأفضل طريقة

بمجرد أن قرأت على Habr مقالة حول تكوين BGP على جهاز توجيه. يمكن استخدام التعليمات الواردة من هناك لتكوين جهاز التوجيه المنزلي بحيث تمر حركة المرور إلى عناوين IP محددة عبر قناة أخرى. ومع ذلك ، هناك مشكلة: يمكن أن تكون قائمة عناوين IP كبيرة للغاية.

بالإضافة إلى الشبكات من القائمة ، تتم إضافة أكبر الشبكات الفرعية للشبكات المجاورة إلى هذا الرسم البياني. اقرأ عن سبب الحاجة إلى ذلك.


بدا الأمر وكأنه شجرة شبكة من Roskomnadzor في مايو 2018.

في البداية حاولت إضافة القائمة بأكملها عبر / ip route add to My MikroTik hAP ac lite - نفدت مساحة جهاز التوجيه. ثم قمت بتحميل جميع العناوين في الذاكرة من خلال BGP - عمل جهاز التوجيه قليلاً وتعلق. أصبح من الواضح أن القائمة تحتاج إلى التشذيب.

يذكر المقال الأداة المساعدة قائمة محلل شبكة الاتصال من Unacacrificed . إنها تفعل ما أحتاجه ، لكنني رأيتها بعد أن بدأت في اختراع دراجتي. ثم انتهيت من الاهتمام ، لأن ما قمت به يعمل بشكل أفضل ، وإن كان أبطأ بكثير.

لذلك ، بيان المشكلة: تحتاج إلى كتابة برنامج نصي يأخذ قائمة من عناوين IP والشبكات كمدخلات ويقصرها على الحجم المحدد. في هذه الحالة ، يجب أن تغطي القائمة الجديدة جميع العناوين من القائمة القديمة ، ويجب أن يكون عدد العناوين الجديدة التي يجب إضافتها إليها ضئيلًا.

لنبدأ بإنشاء رسم بياني لجميع شبكات المصدر (ما هو في الصورة أعلاه). ستكون عقدة الجذر هي الشبكة 0.0.0.0/0. عند إضافة شبكة فرعية جديدة A ، نجد الشبكة الفرعية B في الشجرة بحيث يكون A و B على الشبكة الفرعية C ويكون حجم الشبكة الفرعية C ضئيلًا (الحد الأقصى للقناع). بمعنى آخر ، يجب أن يكون عدد البتات الشائعة للشبكات الفرعية A و B كحد أقصى. نضيف هذه الشبكة الفرعية المشتركة إلى الشجرة ، وفي داخلنا ننقل الشبكات الفرعية A و B. ربما يمكن أن يسمى هذا بالشجرة الثنائية.

على سبيل المثال ، قم ببناء شجرة من شبكتين فرعيتين (192.168.0.1/32 و 192.168.33.0/24):



الحصول على الشجرة:



إذا أضفنا ، على سبيل المثال ، الشبكة 192.168.150.150/32 ، فإن الشجرة ستبدو كما يلي:



يشير اللون البرتقالي إلى شبكات فرعية مشتركة تمت إضافتها أثناء إنشاء الأشجار. هذه الشبكات الفرعية الشائعة هي أننا "سننهار" لتقليل حجم القائمة. على سبيل المثال ، إذا قمت بإنهاء العقدة 192.168.0.0/16 ، فسنقوم بتقليل حجم قائمة الشبكات بمقدار 2 (كانت هناك 3 شبكات من القائمة الأصلية ، أصبحت 1) ، لكننا في نفس الوقت نغطي 65536-1-1-256 = 65278 عناوين IP ، والتي غير المدرجة في قائمتنا الأصلية.

من الملائم لكل عقدة حساب "معامل الفوائد الناتجة عن الانهيار" ، مع عرض عدد عناوين IP التي ستتم إضافتها بالإضافة إلى كل الإدخالات المحذوفة من القائمة:

weight_reversed = net_extra_ip_volume / (in_list_records_count - 1) 

سنستخدم الوزن = 1 / الوزن_المراجع ، كما هو أكثر ملاءمة. من الغريب أن يكون الوزن مساويًا لما لا نهاية إذا كان هناك ، على سبيل المثال ، شبكتان / 32 في القائمة ، والتي تشكل معًا شبكة كبيرة واحدة / 31.

وبالتالي ، كلما كان الوزن أكبر ، كلما كان من المربح انهيار مثل هذه الشبكة.

يمكنك الآن حساب الوزن لكل العقد في الشبكة ، وفرز العقد حسب الوزن وطي الشبكات الفرعية حتى نحصل على حجم القائمة التي نحتاج إليها. ومع ذلك ، هناك صعوبة: في الوقت الذي ننهار فيه الشبكة ، تتغير أوزان جميع الشبكات الأصل.

على سبيل المثال ، لدينا شجرة ذات أوزان محسوبة:



دعنا ننهار الشبكة الفرعية 192.168.0.0/30:



انخفض وزن العقدة الأصل. إذا كانت هناك عُقد في الشجرة يزيد وزنها عن 0.166 ، فيجب طي ما يلي.

نتيجة لذلك ، يجب ضغط القائمة بشكل متكرر. الخوارزمية هي شيء مثل هذا:

1. نحسب الأوزان لجميع العقد.
2. لكل عقدة ، قم بتخزين الحد الأقصى لوزن العقدة الفرعية (Wmax).
3. اتضح أن Wmax لعقدة الجذر هي الحد الأقصى لوزن العقدة في الشجرة بأكملها (قد يكون هناك العديد من العقد مع وزن يساوي Wmax).
4. بشكل متكرر ضغط جميع الشبكات مع وزن يساوي Wmax من عقدة الجذر. في هذه الحالة ، نعيد حساب الوزن. نعود إلى عقدة الجذر.
5. انخفض Wmax من عقدة الجذر - نقوم بتنفيذ الخطوة 4 حتى نحصل على الحجم المطلوب لقائمة الشبكات.

الشيء الأكثر إثارة للاهتمام هو مراقبة الخوارزمية في الحركة. فيما يلي مثال لقائمة الشبكات:

192.168.0.1
192.168.0.2
192.168.0.8/29
192.168.150.1
192.168.150.2
192.168.150.8/29
192.168.20.1
192.168.20.2
192.168.20.3
192.168.20.4
192.168.20.5
192.168.20.6
192.168.20.7

هنا 192.168.0.0/24 و 192.168.150.0/24 الشبكات الفرعية متطابقة في البنية - من الأفضل أن نرى كيف ، أثناء الضغط ، تنتقل الخوارزمية من فرع إلى آخر. وأضاف 192.168.20.0/24 الشبكة الفرعية من أجل إظهار أنه في بعض الأحيان أكثر ربحية ضغط الشبكة الأم من الشبكة التابعة. انتبه إلى الشبكة الفرعية 192.168.20.0/30: بعد ملء الشجرة ، يكون وزنها أقل من الشبكة الفرعية الأصل.

ملء شجرة:



هنا الخط الأسود هو الشبكة الحقيقية من القائمة الأصلية. الشبكات الصفراء المضافة. الأزرق هو وزن العقدة. الأحمر هو الشبكة الحالية. الوردي هو صافي المنهار.

ضغط



كانت هناك فكرة لتسريع خوارزمية انهيار الشبكة: لهذا ليس من الضروري انهيار الشبكات ذات الوزن الأقصى في كل تكرار. يمكنك تحديد قيمة الوزن مسبقًا ، والتي ستمنحنا قائمة بالحجم المطلوب. يمكنك الاختيار عن طريق البحث الثنائي ، أي ضغط مع وزن معين ومعرفة ما هو حجم القائمة التي يتم الحصول عليها في الإخراج. صحيح ، لهذا تحتاج إلى ضعف مقدار الذاكرة وإعادة كتابة الكود - أنا ببساطة لم أضع يدي عليه.

الآن يبقى للمقارنة مع شبكة قائمة المحلل اللغوي من مقالة حول BGP.

إيجابيات السيناريو الخاص بي:

1. إعداد أكثر ملاءمة: ما عليك سوى تحديد الحجم المطلوب لقائمة الشبكات ، وسيكون الإخراج عبارة عن قائمة بهذا الحجم بالضبط. يحتوي محلل قائمة الشبكات على الكثير من المقابض ، وتحتاج إلى العثور على مجموعة منها.
2. نسبة الضغط تتكيف مع القائمة الأصلية. إذا أزلنا بعض الشبكات من القائمة ، فسنحصل على عناوين إضافية أقل ، إذا أضفنا المزيد. في هذه الحالة ، سيكون حجم القائمة الناتجة ثابتًا. يمكنك اختيار الحد الأقصى للحجم الذي يمكن لجهاز التوجيه التعامل معه ، ولا تقلق بشأن زيادة حجم القائمة في مرحلة ما.
3. تحتوي القائمة الناتجة على أقل عدد ممكن من الشبكات الإضافية. في قائمة الاختبار من GitHub ، أعطت خوارزمي الخاص بي 718479 عناوين IP إضافية ، ومحلل قائمة الشبكات - 798761. الفرق هو 10 ٪ فقط .
   
   
   كيف يمكنني حساب هذا؟ مشاهدة

   1. إطلاق
   
   

     ./network-list-parser-darwin-386-1.2.bin -src-file real_net_list_example.txt -dst-file parsed.txt -aggregation-max-fake-ips 0 -intensive-aggregation-min-prefix 31 2>&1 

   
   وحصلنا على قائمة تنظيفها دون القمامة وخفضت جزئيا. سأقارن جودة ضغط parsed.txt. (بدون هذه الخطوة ، كانت هناك مشاكل في تقييم عدد قوائم محلل شبكة IP المزيفة التي يضيفها).
   
   2. إطلاق
   
   

    ./network-list-parser-darwin-386-1.2.bin -src-file parsed.txt -dst-file parsed1.txt 2>&1 

   
   وحصلنا على قائمة مضغوطة ، انظر إلى الإخراج ، هناك سطر "إضافة 7.3٪ تغطية عناوين IP (798761)."
   
   يحتوي ملف parsed1.txt على 16649 إدخالات.
   
   3. إطلاق
   
   python3 minimize_net_list.py parsed.txt 16649.
   نرى الخط ### ليست حقيقية IPS: 718479.
   
   
   

أرى عيبًا واحدًا فقط من البرنامج النصي الناتج: إنه يعمل لفترة طويلة ويتطلب الكثير من الذاكرة. على جهاز MacBook الخاص بي ، يتم الضغط على القائمة لمدة 5 ثوانٍ. على التوت - دقيقة واحدة ونصف . مع RyPy3 على جهاز Mac ، أصبح أسرع ، لم أتمكن من وضع PyPy3 على Raspberry. شبكة قائمة محلل الذباب هناك وهناك.

بشكل عام ، من المنطقي استخدام هذا المخطط فقط للمتخصصين في الكمال ، منذ ذلك الحين من غير المرجح أن ينفق الآخرون الكثير من موارد الحوسبة من أجل 10٪ من الشبكات المحفوظة. حسنا ، أكثر ملاءمة قليلا ، نعم.

رابط للمشروع على جيثب

تشغيل مثل هذا:

 python3 minimize_net_list.py real_net_list_example.txt 30000 | grep -v ### > result.txt 

هذا ، في الواقع ، هو كل شيء.

محدث
أشار Pochemuk في التعليقات إلى وجود خطأ في حساب الوزن ، لقد قمت بإصلاحه والآن ، عند ضغط نفس القائمة من المثال بنفس الإعدادات ، تتم إضافة 624925 عنوان IP غير موجود في القائمة الأصلية. هذا هو بالفعل 22 ٪ أفضل مما كانت عليه عند معالجة محلل شبكة القائمة
كود جديد في github.com/phoenix-mstu/net_list_minimizer/tree/untested فرع غير مجرب