C-Mesh

Routing-Simulation in C

Alain Horner (@elHornair), 01. Juli 2013

Intro

Aufgabenstellung

• Offizielle Aufgabenstellung
• Kennen wir alle

Lösungskonzept

Funktionsweise der Knoten

• Boss-Worker Modell
• Boss: Auf Paket warten
• Boss: Paket an Worker weitergeben
• Worker: Paket verarbeiten

Funktionsweise der Knoten

Verteilung der Pakete

Funktionsweise der Knoten

Boss-Worker: Implementierung mit Pthreads

while (1) {
    // wait for next package
    newsockfd = wait_for_connection(sockfd);

    // let worker handle package
    pthread_create(&workers[thread_counter], NULL, worker_init, (void *)newsockfd);

    // alternate workers
    thread_counter += 1;
    if (thread_counter >= NUM_WORKERS) {
        thread_counter = 0;
    }
}
                    

Details: Siehe Github

Verbindungen zu Nachbaren

• Nachbar: Knoten, dessen IP-Adresse und Port bekannt ist
• Nachbaren-Liste
• Bidirektionale Verbindungen -> Handshake

Verbindungen zu Nachbaren

Handshake

Routing

• Z.B. “In welcher Richtung liegt das Ziel?”
• Tabelle mit zwei Einträgen
• Pro Eintrag: Nachbar (IP-Adresse und Port)

Routing

• Eigenheit von Aufgabenstellung ausgenutzt: “Pakete werden immer von der Quelle zum Ziel oder vom Ziel zur Quelle gesendet”
• Routingtabelle möglichst früh anpassen
• Einträge werden nie überschrieben

Paket-Forwarding

• Knoten: Paket weiterleiten, falls nicht für mich
• Routingtabelle verwenden
• Fallback: Flooding

Paket-Forwarding

Flooding

Paket-Forwarding

Problem mit ringförmig verbundenen Knoten

Erreichen des Ziels

• Nur bei Quell- und Zielknoten möglich
• Ausgabe der Nachricht
• Umwandlung des Nachrichtenpakets in OK-Paket
• Routing sehr einfach
• Schwarze Liste wird ignoriert
• OK-Paket: Zurück bis zu ursprünglichem Sender

Demo

Demo

• Python-Testprogramm
• 1 Startknoten
• 1 Zielknoten
• 10 Verbindungsknoten
• 3 Pakete

Outro

Lessons learned

• Geteilte Ressourcen immer locken
• Debugging: Gnu Debugger (GDB)

Weiterführende Links

• Sourcecode
• Dokumentation
• Pthreads

Fragen?

Danke!