Berevoescu Remus-Napoleon 322CB

Dupa ce primim un packet pe o interfata, avem urmatoarele checkuri pentru:
    ->ethernet header:
    1. Daca packetul primit este mai scurt decat lungimea unui ethernet header => dropped
    2. Daca dest mac address nu este adresa mac a interfetei sau broadcast => dropped
    
    ->IP header:
    1. Daca routerul este destiniatia finala a packetului => trimitem un ICMP echo reply
    2. Daca checksum-um IPv4 este gresit => dropped
    3. Daca TTL == 0 sau 1 => trimitem un ICMP time exceeded
        altfel este decrementat
    4. Interogam structura de trie construita pe baza tabelei de rutare pentru next hop IP
        Daca nu gasim o adresa valida pentru next hop => trimitem un ICMP destination unreachable
    5. Updatam checksum-ul IPv4
    6. Interogam cache-ul ARP pentru a seta noua adresa mac destinate
        Daca nu avem aceasta adresa in cache, setam mac destinatie cu 0.0.0.0.0.0
        La pasul urmator (forwardare), daca mac destinatie este 0.0.0.0.0.0,
            packetul IPv4 este salvat in queue si o sa trimitem un ARP request
        Daca adresa mac este diferita de 0.0.0.0.0.0, packetul este forwardat
    
    ->ARP reply:
    1. Verificam daca perechea IP+MAC primita in ARP reply deja este prezenta in cache
        Daca da, nu facem nimic
        Daca nu, updatam cache-ul, scoatem primul mesaj din queue, ii setam adresa mac destinatie si il forwardam
    ->ARP request:
    1. Cand primim un ARP request:
        Verificam daca target IP address este egala cu adresa noastra IP de pe interfata pe care am primit
        Daca da, trimitem un ARP reply cu adresa noastra MAC
        Altfel, nu facem nimic

Observatii:
    1.Cand trimitem un ICMP echo reply, ICMP time exceeded sau ICMP destination unreachable nu mai interogam tria de rutare sau cache-ul ARP, ci doar trimitem pachetul
    pe interfata pe care l-am primit, catre adresa MAC de la care a fost trimis. Probabil in viata reala ar fi recalculate aceste adrese din cauza posibilitatii 
    schimbarii rutei (datorita unor rutere care au cazut intre timp sau sunt suprasolicitate), insa acest network simulat fiind static am decis sa optimizez procesul si 
    sa sar aceste interogari.
    
    2. ARP cache-ul este implementat ca o structura ce tine 3 field-uri:
    struct arp_cache {
        int len;                                => lungimea cache-ului
        int index;                              => indexul la care se fa face urmatoarea scriere
        struct arp_table_entry *arp_table;      => pointer catre un array de structuri ce tin perechi (IP, MAC)
    };
    De fiecare data cand primim un ARP reply, interogam acest cache ca sa vedem daca deja avem informatia.
    Daca deja avem, nu facem nimic.
    Daca nu avem informatia, incrementam arp_cache->index si salvam un nou entry in arp_table.
    Daca arp_table a ajuns la capacitate maxima (adica index == len) vom dubla capacitatea (len) si vom realoca tabela cu noua capacitate si salvam noul entry.

    De fiecare data cand forwardam un packet interogam cache-ul pentru a gasti adresa MAC a next hop-ului.
        Daca nu o gasim, salvam packetul in coada si trimitem un ARP request. Acest packet va fi dequeued si    forwardat odata cu primul ARP reply primit.
        Daca o gasim, packetul e fericit si il forwardam cu succes.
    
    3. Tria de rutare pe care o construim arata astfel:
    struct prefix_trie {
        struct prefix_trie *node[2];            => avem doua ramuri ale arborelui, ramura de bit = 0 si ramura de bit = 1
        uint32_t next_hop_ip;                   => aici salvam next_hop_ip daca nodul curent este un prefix valid, altfel e setat la 0
        int next_hop_interface;                 => same next_hop_ip
    };
    Mai intai construim tabela de rutare normala, folosind functiile din lib.c. Apoi chemam procedura de build_trie() care va genera arborele de prefixe.
    Pentru a construi arborele, iteram prin toate intrerile din tabela. Pentru fiecare intrare, traversam prefixul bit cu bit de la stanga la dreapta
    si construim nodurile din trie (nodul stang daca bitul e 0, altfel drept). La fiecare nod verificam daca urmatorul bit din masca este egal cu 0
    (aka daca am ajuns la sfarsitul mastii). Daca am ajuns la sfarsitul mastii, asta inseamna ca am ajuns la sfarsitul prefixului si ca in nodul curent salvam
    informatiile de next_hop_ip si next_hop_interface, apoi trecem la urmatoarea intrare din tabela de rutare.

    Cand citim din trie, traversam tria pe drumul IP-ului nostru si de fiecare data cand dam de informatii (next_hop_ip, next_hop_interface) le salvam.
    O sa trecem prin multiple noduri cu informatii, ultimul nod ce are informatii este cel cu prefixul cel mai lung, deci el ne intereseaza.
    Dupa ce parcurgem drumul descris de IP-ul nostru (drumul va fi de 32 de biti sau mai putin), returnam informatiile.