Setelah saya membaca di Habr,
artikel tentang mengkonfigurasi BGP di router. Instruksi dari sana dapat digunakan untuk mengonfigurasi router rumah sehingga lalu lintas ke alamat IP tertentu melewati saluran lain. Namun, ada masalah: daftar alamat IP bisa sangat besar.
Selain jaringan dari daftar, subnet umum terbesar dari jaringan tetangga ditambahkan ke grafik ini. Baca terus untuk alasan ini diperlukan.
Itu tampak seperti pohon jaringan dari Roskomnadzor pada Mei 2018.Pertama, saya mencoba menambahkan seluruh daftar via / ip route add ke MikroTik hAP ac lite saya - router kehabisan ruang disk. Lalu saya memasukkan semua alamat ke dalam memori melalui BGP - router bekerja sedikit dan menggantung. Jelaslah bahwa daftar itu perlu dipangkas.
Artikel tersebut menyebutkan
utilitas daftar jaringan parser dari
Unsacrificed . Dia melakukan apa yang saya butuhkan, tetapi saya melihatnya setelah saya mulai menemukan sepeda saya. Kemudian saya menyelesaikannya karena minat, karena apa yang saya lakukan bekerja lebih baik, walaupun jauh lebih lambat.
Jadi, pernyataan masalah: Anda perlu menulis skrip yang mengambil daftar alamat IP dan jaringan sebagai input dan mempersingkatnya ke ukuran yang ditentukan. Dalam hal ini, daftar baru harus mencakup semua alamat dari yang lama, dan jumlah alamat baru yang dipaksa untuk ditambahkan haruslah minimal.
Mari kita mulai dengan membuat grafik dari semua jaringan sumber (apa yang ada dalam gambar di atas). Node root akan menjadi jaringan 0.0.0.0/0. Saat menambahkan subnet A baru, kami menemukan subnet B di pohon sehingga A dan B berada di subnet C dan ukuran subnet C minimal (topeng maksimum). Dengan kata lain, jumlah bit umum dari subnet A dan B harus maksimum. Kami menambahkan subnet umum ini ke pohon, dan di dalam kami mentransfer subnet A dan B. Mungkin ini bisa disebut pohon biner.
Misalnya, bangun pohon dua subnet (192.168.0.1/32 dan 192.168.33.0/24):
Dapatkan pohonnya:
Jika kita menambahkan, katakanlah, jaringan 192.168.150.150/32, maka susunannya akan terlihat seperti ini:
Oranye menunjukkan subnet umum yang ditambahkan selama konstruksi pohon. Subnet-subnet umum inilah yang akan kita "runtuh" untuk mengurangi ukuran daftar. Misalnya, jika Anda menutup simpul 192.168.0.0/16, maka kami akan mengurangi ukuran daftar jaringan sebanyak 2 (ada 3 jaringan dari daftar asli, menjadi 1), tetapi pada saat yang sama kami juga mencakup 65536-1-1-256 = 65278 alamat IP, yang tidak termasuk dalam daftar asli kami.
Lebih mudah bagi setiap simpul untuk menghitung "koefisien laba dari keruntuhan", yang menunjukkan jumlah alamat IP yang akan ditambahkan ke setiap entri yang dihapus dari daftar:
weight_reversed = net_extra_ip_volume / (in_list_records_count - 1)
Kami akan menggunakan bobot = 1 / weight_reversed, as lebih nyaman. Sangat mengherankan bahwa bobotnya bisa sama dengan tak terhingga jika, misalnya, ada dua / 32 jaringan dalam daftar, yang bersama-sama membentuk satu jaringan besar / 31.
Dengan demikian, semakin besar bobotnya, semakin menguntungkan untuk menghancurkan jaringan tersebut.
Sekarang Anda dapat menghitung bobot untuk semua node dalam jaringan, mengurutkan node berdasarkan berat dan menciutkan subnet sampai kami mendapatkan ukuran daftar yang kami butuhkan. Namun, ada kesulitan: saat kita menutup jaringan, bobot semua jaringan induk berubah.
Misalnya, kami memiliki pohon dengan bobot yang dihitung:
Mari runtuh subnet 192.168.0.0/30:
Berat simpul induk telah menurun. Jika ada simpul di pohon dengan bobot lebih besar dari 0,166, maka yang berikut harus diciutkan.
Akibatnya, daftar harus dikompres secara rekursif. Algoritme adalah sesuatu seperti ini:
- Kami menghitung bobot untuk semua node.
- Untuk setiap simpul, simpan berat maksimum simpul anak (Wmax).
- Ternyata Wmax dari simpul akar adalah bobot maksimum dari simpul di seluruh pohon (mungkin ada beberapa simpul dengan bobot yang sama dengan Wmax).
- Kompres secara rekursif semua jaringan dengan bobot yang sama dengan Wmax dari node root. Dalam hal ini, kami menghitung bobotnya. Kami kembali ke simpul root.
- Wmax dari node root telah menurun - kami melakukan langkah 4 sampai kami mendapatkan ukuran yang diinginkan dari daftar jaringan.
Hal yang paling menarik adalah mengamati algoritma yang bergerak. Berikut ini adalah contoh untuk daftar jaringan:
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.7Di sini, subnet 192.168.0.0/24 dan 192.168.150.0/24 identik dalam struktur - lebih baik untuk melihat bagaimana algoritma melompat dari satu cabang ke cabang lain selama kompresi. Dia menambahkan subnet 192.168.20.0/24 untuk menunjukkan bahwa kadang-kadang lebih menguntungkan untuk mengompres jaringan induk daripada jaringan anak. Perhatikan subnet 192.168.20.0/30: setelah mengisi pohon, bobotnya kurang dari subnet induk.
Mengisi pohon:
Di sini font hitam adalah jaringan nyata dari daftar asli. Jaringan tambah kuning. Biru adalah bobot simpul. Merah adalah jaringan saat ini. Pink adalah jaring yang runtuh.
Kompresi
Ada ide untuk mempercepat algoritme runtuhnya jaringan: untuk ini, tidak perlu runtuh hanya jaringan dengan bobot maksimum pada setiap iterasi. Anda dapat memilih sebelumnya nilai bobot, yang akan memberi kami daftar ukuran yang diinginkan. Anda dapat memilih dengan pencarian biner, mis. kompres dengan bobot tertentu dan lihat ukuran daftar apa yang didapat pada output. Benar, untuk ini, Anda perlu memori dua kali lebih banyak dan menulis ulang kode - saya tidak bisa mendapatkannya.
Sekarang tinggal membandingkan dengan
network-list-parser dari artikel tentang BGP.
Kelebihan dari skrip saya:
- Pengaturan yang lebih mudah: cukup tentukan ukuran yang diperlukan dari daftar jaringan, dan output akan menjadi daftar ukuran yang persis seperti itu. Network-list-parser memiliki banyak pegangan, dan Anda perlu menemukan kombinasi keduanya.
- Rasio kompresi menyesuaikan dengan daftar asli. Jika kami menghapus beberapa jaringan dari daftar, maka kami akan mendapatkan lebih sedikit alamat tambahan, jika kami menambahkan lebih banyak. Dalam hal ini, ukuran daftar yang dihasilkan akan konstan. Anda dapat memilih ukuran maksimum yang bisa ditangani oleh router, dan tidak khawatir tentang daftar yang menjadi terlalu besar di beberapa titik.
- Daftar yang dihasilkan berisi jumlah minimum yang mungkin dari jaringan tambahan. Pada daftar tes dari GitHub, algoritma saya memberi 718479 alamat IP tambahan, dan network-list-parser - 798761. Perbedaannya hanya 10% .
Bagaimana saya menghitung ini? Menonton1. Luncurkan
./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
dan kami mendapatkan daftar yang bersih tanpa sampah dan sebagian berkurang. Saya akan membandingkan kualitas kompresi parsed.txt. (tanpa langkah ini, ada masalah mengevaluasi berapa banyak IP palsu yang ditambahkan jaringan-parser).
2. Luncurkan
./network-list-parser-darwin-386-1.2.bin -src-file parsed.txt -dst-file parsed1.txt 2>&1
dan kami mendapatkan daftar terkompresi, lihat output, ada baris "Tambahkan 7,3% cakupan IP (798761)."
File parsed1.txt memiliki 16649 entri.
3. Luncurkan
python3 minim_net_list.py parsed.txt 16649.
Kami melihat baris ### bukan ips nyata: 718479.
Saya hanya melihat satu kekurangan dari skrip yang dihasilkan: ini bekerja untuk waktu yang lama dan membutuhkan banyak memori. Di MacBook saya, daftar ditekan selama 5 detik. Di Raspberry -
satu setengah menit . Dengan RyPy3 di Mac lebih cepat, saya tidak bisa menempatkan PyPy3 di Raspberry. Network-list-parser terbang ke sana-sini.
Secara umum, masuk akal untuk menggunakan skema ini hanya untuk perfeksionis, karena semua yang lain tidak mungkin menghabiskan begitu banyak sumber daya komputasi demi 10% dari jaringan yang disimpan. Yah, sedikit lebih nyaman, ya.
Tautan ke proyek di GitHubJalankan seperti ini:
python3 minimize_net_list.py real_net_list_example.txt 30000 | grep -v ### > result.txt
Faktanya, itu saja.
UPDPochemuk dalam komentar menunjukkan kesalahan dalam menghitung berat, saya memperbaikinya dan sekarang, ketika mengompresi daftar yang sama dari contoh dengan pengaturan yang sama, 624925 alamat IP ditambahkan yang tidak ada dalam daftar asli. Ini sudah
22% lebih baik daripada saat memproses network-list-parser
Kode baru di
github.com/phoenix-mstu/net_list_minimizer/tree/untested cabang yang belum diuji