Forum: Knobelecke

Hallo alle zusammen,

nach einer laengeren Abstinenz von diesem Forum melde ich mich gleich mit einer kleinen Aufgabe zurueck.

Vorab:
Es ist keine Aufgabe aus meinem Studium, die ich als Hausaufgabe zu loesen habe, sondern ein Problem, vor welches ich
vor ein paar Wochen gestellt wurde und auch gemeistert habe.

Also die Aufgabe:
Wie kann man eine Routingtabelle, welche folgende Parameter enthalten soll:
Sender,Empfaenger,Next Hop,Metrik
in einer einzigen Variable speichern?

Ich hoffe, dass ihr damit spass habt und es nicht zu leicht ist.

Gruss
Jan

edit: Und schon die erste fehlende Information, die verwendete Programmiersprache ist C++.
Ausserdem sind keine Strukturen/Namespaces/Klassen erlaubt. Es geht auch leichter.
edit2: Es mag ja sein, dass meine Knobelaufgaben etwas einfallslos sind. Aber ich finde solche Aufgaben machen auch ziemlich viel Spass

--
Physiker finden, Ingenieure erfinden.

 

Hi,
vielleicht verstehe ich nicht ganz, was Du meinst, indem du sagst, dass Du alles in einer Variable speichern möchtest. Meinst Du damit, dass alles an die speicherstelle geschrieben werden soll, zu der die zu der Variable zugehörige Adresse zeigt? Dann wär das ganze kein Problem, man müsste eben nur wissen, wie die Tabelle an dieser Stelle gespeichert ist und sie dann auslesen. Im simpelsten Falle koennte man alles in einen großen char* Array reinschreiben, mit ein paar sinnvollen Trennzeichen zwischen den einzelnen Einträgen. Aber ich habe das Gefühl, dass Du das nicht meintest. Vielleicht moechtest Du die Tabelle aber auch als integer Array darstellen (int*). Dort werden dann die Tabelleninformationen der Reihe nach mit einer sinnvollen codierung hineingeschrieben. Um das nicht genauer Beschreiben zu müssen, hier ein Bsp. (Routingtabelle von Wikipedia):

192.168.0.0 255.255.255.0 192.168.1.1 192.168.1.2 2
192.168.1.0 255.255.255.0 192.168.1.2 192.168.1.2 1

sollte im Array so gespeichert werden, die Punkte dienen nur zur Verdeutlichung und werdennicht gespeichert, die beiden Zeilen hängen im Array einfach aneinander:

192.168.000.000.255.255.255.000.192.168.001.001.192.168.001.002.2
192.168.001.000.255.255.255.000.192.168.001.002.192.168.001.002.1

Es ist klar, dass dies funktioniert, wenn die Metrik eine ganze Zahl ist, deren Betrag beschränkt ist.

Ehrlich gesagt, ich bin sehr unbedarft, was Routingtabellen und diesen ganzen „Netzwerkkram“ angeht. Es klingt aber interessant. Wozu brauchst du diese Tabellen?

 

Ok, ich war eben nicht eingeloggt, deshalb kann ich das obige jetzt nicht editieren. Es muss nicht unbedingt für jede einzelne Zahl von 0-9 ein Integer im Array reserviert werden. es kann auch einfach für die Zahlen zwischen den Punkten jeweils ein int reserviert werden, dann kann man sich einiges sparen. Man koennte aber auch das Speichertechnisch noch effizienter machen, aber das war nicht die Aufgabe und ich denke, ich habe jetzt auch genügend Worte darüber verloren.

Edit Warum muss es C++ sein? C würde hier reichen. Vermutlich liege ich dann nicht ganz richtig mit meiner Lösung. Naja, macht nix.

Benjamin

--
Über die (angemessen sachliche) Korrektur meiner Fehler freue ich mich stets.

 

Hi,

ja ich habe mich da vielleicht nicht ganz klar ausgedrueckt.
Ich habe es schon so gemeint, dass ich eine Variable (aehnlich wie ein Array) habe,
in dem die Informationen stehen.

Dein Ansatz mit dem char/int Array war schonmal nicht verkehrt.

Es gibt allerdings noch eine optimiertere Loesung, was die Zugriffszeiten und den Quelltext angeht.
Denn wenn es in einem Array gespeichert ist,
dann funktioniert das Suchen des Next Hop oder der Metrik nur ueber eine Schleife, die den Wert der Sende-IP und der Ziel-IP mit jedem Eintrag in dem Array vergleichen muss.

Ich habe die Bedingung mit C++ gestellt, da ich 1. das ganze in C++ geschrieben habe und ich mir nicht sicher bin,
ob der von mir verwendete Ansatz in C ueberhaupt existiert.

Die Tabellen benoetige ich in meinem Praxissemester, in welchem ich in OMNeT++ (Eine Netzwerksimulationsumgebung)
unteranderem einen Netzwerklayer geschrieben habe, der mit dem Dijkstra Algorithmus fuer jede Ende zu Ende verbindung die "beste" Route herausfindet und diese dann in der Routingtabelle abspeichert.

Aber freut mich, dass ich doch nicht der einzige bin, der sowas interessant findet.

Gruss
Jan

--
Physiker finden, Ingenieure erfinden.

 

So,

nachdem sich wohl niemand weiteres fuer dieses Raetsel zu interessieren scheint :(
werde ich hier jetzt mal meine Loesung posten.

Also das Stichwort heisst std::map bzw std::pair.

Denn der Nachteil an Arrays oder Vektoren ist, dass wenn man einen Wert darin sucht, man immer ueber eine Schleife
darin suchen muss.

Nicht aber in der map, denn darin werden 2 Werte einander zugewiesen.
Der erste Wert ist der Key (Entspricht dem Index in einem Array) und der zweite Wert ist
der Inhalt, den man gerne dem Key zuordnen will (Also der Wert der in dem Array an der Speicherstelle mit diesem Index steht).

Da aber fuer eine Verbindung von 2 Werten (also SenderIP und EmpfaengerIP) 2 weitere Werte gesucht sind,
haut das mit der map noch nicht ganz hin.

Die Loesung dafuer ist das std::pair.
Ein pair kann man sich wie ein struct vorstellen, welches 2 beliebige Werte beinhaltet und diese wieder zu einer Variable zusammenfasst.

Also macht man eine map, welche ein pair als Key und ein pair als gesuchter Wert.
Und schon ist die gesamte Routingtabelle in einer Variable gespeichert,
aus welcher man sofort den gesuchten Wert bekommt, ohne vorher mit hilfe einer Schleife danach suchen zu muessen.

In Quellcode sieht das dann so aus:

//Das ist die map, in welcher die Routingtabelle gespeichert wird.
//Die IP-Adressen nehme ich der einfachheit halber als int an.
std::map<std::pair<int,int>,std::pair<int,double> > RoutingTabelle;

//Hier wird eine neue Route an die Routingtabelle angehaengt
//falls die Route schon existiert, werden die Werte einfach ueberschrieben
void NeueRoute(int SenderIP, int EmpfaengerIP, int HextHop, double Metrik){
    std::pair<int, int> Key(SenderIP, EmpfaengerIP);
    std::pair<int, double> Informationen(NextHop, Metrik);

    RoutingTabelle[Key] = Informationen;
}

//Und das auslesen des NextHop, um zu wissen, wo das Paket auf dieser
//Route hingeschickt werden soll.
//Falls keine Routeninformationen existieren, gibt die Funktion -1 zurueck
int NextHop(int SenderIP, int EmpfaengerIP){
    int zurueck = -1;
    std::pair<int,int> Key(SenderIP,EmpfaengerIP);

    //Das ist nur die Abfrage, ob der Eintrag in der Tabelle existiert.
    if(RoutingTabelle.find(Key) != RoutingTabelle.end()){
        zurueck = RoutingTabelle[Key].first; //Hole vom 2. pair den ersten Wert, also den NextHop und schreibe ihn in die Variable zurueck
    }

return zurueck;
}

Und um die optimierung der Laufzeit zu verdeutlichen hier ein kleines Beispiel:
Bei einer Tabelle mit ca 800000 Eintraegen braucht der PC bei einer Loesung mit
Arrays ca 40ms um den richtigen Eintrag in der Tabelle zu finden.
Mit der map ist die Suchzeit auf weniger als 1ms gesunken.

@d-503: Und danke schoen fuers mitmachen.

Gruss
Jan

--
Physiker finden, Ingenieure erfinden.