[C#] Logica voor matchen IP adres aan beschikbare netwerken

[Kokkers]

Als wannabe scripter en niet gehinderd door enige kennis en ervaring wilde ik onderstaand even spiegelen bij de meer ervaren rotten.

Ik heb de beschikking over een file (aangeleverde dump) met daarin 100.000+ unieke IPv4 adressen die representatief zijn voor het bezoek aan website X.

Daarnaast heb ik een andere file met daarin de beschikbare netwerken (peers) van een BGP router. Het gaat hier om enkele duizenden netwerken. (111.111.111.0/20 bijv.)

Nu wil ik weten hoeveel procent van de unieke (potentiële) IP adressen niet bereikbaar zijn via aangesloten peers/netwerken op deze router en dus alleen via betaalde transit verbindingen te bereiken zijn.

Mijn eerste idee is om alle IP adressen in een array A in te lezen en vervolgens alle netwerken in een array B. Met een bitwise XOR operator kan er gekeken worden of een betreffende IP adres (uit array A) binnen het betreffende netwerk valt (in array B ). Array B is eigenlijk een ordinaire routing table.

Dit betekent dat voor elke entry in array A array B doorlopen moet worden en er voor elk netwerk in array B een XOR uitgevoerd wordt op zoek naar een match . Eventueel kan het iteratief doorlopen van array B afgebroken worden na een gevonden match.

Mijn gevoel zegt dat dit zal werken maar dat het een hoop tijd kost om de data op deze manier te verwerken. Wat kan ik hier aan optimaliseren? De gemiddelde huis-tuin-en-keuken router doet dit vast efficiënter .

Mijn voorkeur gaat uit naar C# maar dat is voor dit vraagstuk niet zo heel relevant.

Heeft iemand hier ideeën over?

[Grijze Vos]

Als je je array B sorteert dan kun je relatief eenvoudig met wat matches op de eerste meest significante byte van het IP het aantal items uit B waartegen je moet matchen verminderen. Eventueel kun je daarna nog doorgaan naar de tweede meest significante byte. Voor het zoeken gebruik je een simpele binary search.

[Sebazzz]

Gevoel, probeer het gewoon eens? Meten is weten

En de taal is slechts een tool, voel je je bij C goed, gebruik dan C. C# is wel wat makkelijker als je even snel iets wil doen.

[voodooless]

Er zijn natuurlijk best een handvol manieren te verzinnen om dit heel erg snel te doen Ik zou echter gewoon eerst werkenden code maken. Misschien is het al wel snel genoeg.

De eerste makkelijke optimalisatie slag is waarschijnlijk het onderverdelen van de netmasks in groepen aan de hand van het eerste deel van het adres (voor zover de netmask dit toelaat natuurlijk). Zo kun je al heel snel een groot deel van je checks overslaan. Het makkelijkste kun je daarvoor een hash tabel gebruiken. De key is dan het eerste stuk van je netwerk, en de value een lijst met netwerken die daarbinnen vallen.

Dit kun je natuurlijk nog verder uitbreiden naar de volgende laag.. Of je maakt het multithreaded... Er zijn nog wel heel veel optimalisatieslagen te verzinnen

[CyBeR]

Je voorstel is prima. Een kleine optimalisatie is de array met de netwerken sorteren op prefixgrootte. Dus de kleinste prefixen vooraan, de grotere achteraan. (En voor de duidelijkheid, een /1 prefix is kleiner dan een /32.)

Overigens moet je niet XORen maar ANDen. if (net == ip AND mask) then match else fail.

[ Voor 20% gewijzigd door CyBeR op 25-05-2010 00:05 ]

[Kokkers]

Dank voor antwoorden, ik ga er mee aan de slag.

[Janoz]

Op zich is er nog wel een andere mogelijkheid. Je zou de beschikbare netwerken (je 'array B') ook om kunnen bouwen naar een binaire zoek boom. Hierdoor heb je gegarandeerd maar maximaal 32 bool checks nodig per ip adres. De complexiteit van het algorithme veranderd dan van een O(N*M) naar een O(N) (waarbij N de lengte van array A is en M de lengte van array B. Het opbouwen van de boom vind ik niet significant voor de efficientie omdat de grootte van deze lijst 100x zo klein is als de andere lijst)

Het is echter meer een vinger oefening. De simpele cartaansproduct-approach zal niet heel lang duren.

[Kokkers]

Voor de volledigheid nog een toevoeging aan dit topic; het resultaat is acceptabel.

code:

********************
* IP_BGP_Match_0.1 *
********************
Reading ip_list.txt
Done importing 746.595 IP addresses 
Starting IP address dedupe
241.861 IP addresses left after dedupe 
Reading bgp_routes_notransit_cidr.txt
Done importing 71.173 routes
Matching IP addresses to available networks 
..........
Done
Summary:
Number of routes: 71.173
Number of distinct IP addresses: 241.861
Number of IP adresses matching BGP routing table: 228.546
Estimated peering ratio: 94,49%
Duration: 00:02:21
- Press any key to exit -