Hallo an alle, Ich schreibe gerade meinen eigenen TCP/IP Stack für einen ARM Cortex M3 und bin gerade beim DNS Resolver. Ich habe mir überlegt ich implementiere einen Cache, indem ich die letzten 10 Anfragen speichere. Jeder Eintrag hat eine Leasetime die bei jedem Zugriff zurückgesetzt wird und nach einer bestimmten Zeit abläuft. Um jeden Eintrag eindeutig identifizieren zu können habe ich mir gedacht ich speichere eine CRC aus Querry-Adresse. Ist dieses Konzept so eine gute Lösung? Danke im Voraus lg Robert
Ich denke mal bei 10 Einträgen ist die CRC Berechnung langsamer, als wie wenn du in einer Schleife mittels strcmp einfach alle DNS Namen durchgehst. Bei so kleinen Datenmengen muss man immer berücksichtigen, dass man jegliche 'Beschleuniger' auch nicht umsonst bekommt.
Robert S. schrieb: > Jeder Eintrag hat eine Leasetime die bei > jedem Zugriff zurückgesetzt wird und nach einer bestimmten Zeit abläuft. Die Antwort eines DNS-Servers beinhaltet ohnehin eine Gültigkeits- dauer. Das sollte deine obere Schranke für das Caching sein. Falls der Cache überfüllt wird, musst du ggf. vorher Einträge rauswerfen. CRCs sind so konzipiert, dass sie bestmöglich Bitfehler bei einer bitorientierten Übertragung erkennen können, für allgemeine Hashes gibt's andere Algorithmen. Wenn du sowas machst, musst du natürlich immer die Möglichkeit von hash collisions mit einbeziehen.
Karl heinz Buchegger schrieb: > Ich denke mal bei 10 Einträgen ist die CRC Berechnung langsamer, als wie > wenn du in einer Schleife mittels strcmp einfach alle DNS Namen > durchgehst. > Bei so kleinen Datenmengen muss man immer berücksichtigen, dass man > jegliche 'Beschleuniger' auch nicht umsonst bekommt. Da der Domainname 255 Zeichen lang sein kann, wird der DNS Chache ziemlich groß. Da ich RAM beschränkt bin denke ich ist es keine gute Idee. Der Hash muss ja für jede Querry nur einmal generiert werden. Somit denke ich schon, dass es schneller ist. Welche Hash Algorithmen sind den in einer solchen Situation passend? lg Robert
Robert S. schrieb: > Der Hash muss ja für jede Querry nur einmal generiert werden. Somit > denke ich schon, dass es schneller ist. Du scheinst in der Vorstellung zu leben, dass es genügt nur den Hash zu speichern. Dem ist aber nicht so. Der Hash kann dir nur das Auffinden des Eintrags beschleunigen. Danach musst du sowieso noch vergleichen, ob die Strings übereinstimmen! Wenn es so einfach wäre, hättest du einen perfekten Kompressionsalgorithmus gefunden. 255 Bytes in einen einzigen int quetschen, sodass jede der möglichen 255 Bytes Kombinationen einen eindeutigen Hash-Code hat. Beim Hashen schmeisst man immer Information weg! Mehrere unterschiedliche Strings können daher denselben Hashcode erzeugen. Man nennt das Kollisionen. Im Extremfall (zugegeben: konstruiert) sind alle deine 10 Hashcodes identisch, obwohl jedesmal nach einer anderen DNS gesucht wurde. > Der Hash muss ja für jede Querry nur einmal generiert werden. Somit > denke ich schon, dass es schneller ist. Kommt drauf an. Um den Hashcode zu erzeugen, musst du quer durch den kompletten String. Ein Vergleich kann aber auch dann schon abbrechen, wenn die ersten beiden Bytes unterschiedlich sind. Ich will dich nicht davon abhalten, da etwas Komplizierters zu benutzen. Ich möchte nur darauf hinweisen, dass es praktisch immer einen Breakeven Point gibt, an dem die Optimierung mehr kostet als sie bringt.
Karl heinz Buchegger schrieb: > Du scheinst in der Vorstellung zu leben, dass es genügt nur den Hash zu > speichern. Dem ist aber nicht so. Der Hash kann dir nur das Auffinden > des Eintrags beschleunigen. Danach musst du sowieso noch vergleichen, ob > die Strings übereinstimmen! Danke für die Information. Genau das dachte ich. Wieder was gelernt =) > Ich will dich nicht davon abhalten, da etwas Komplizierters zu benutzen. > Ich möchte nur darauf hinweisen, dass es praktisch immer einen Breakeven > Point gibt, an dem die Optimierung mehr kostet als sie bringt. Ich werde mal in den sauren Apfel beißen und die Domain als Klartext speichern. Optimieren kann man ja immer noch. Danke für die Hilfe und noch einen schönen Tag lg Robert