lesson_04.md 3.0 KB
Piattaforme Software per la Rete - lesson 4
Giacomo Verticale
17 March 2016
Exact Match Lookup
Bridge Ethernet
Il primo bridge ethernet è nato per connettere due reti separate Il problema di usare solo un ripetitore per connettere due reti è che fonderei le due reti portando dalle due parti molto traffico inutile.
Il bridge presenta due interfacce e ha una tabella di routing
- Se il destinatario della trama si trova nella stessa interfaccia da cui è arrivata la trama, questa non viene propagata
- Se il destinatario è nell'altra interfaccia, la trama viene propagata Il bridge ha un algoritmo di apprendimento con cui si annota l'interfaccia da cui provengono le varie trame per poter effettuare forwarding.
Requisiti prestazionali
- Lunghezza trame ethernet = 64Byte (max=1500Byte) Fissata dal requisito di distanza massima della rete Le trame internet più diffuse sono ack (40byte+14 intestazione) Quindi vengono inviati 64-54Byte=10Byte inutilmente
- Velocità del collegamento = 10Mbit/s
- Tempo tra 2 trame = 64x8bit/10Mbit/s = 51,2us
Nel tempo tra 2 trame le operazioni da fare sono:
- (sovra)Scrivere la riga della tabella
- Leggere la riga corrispondente Queste operazioni vanno fatte per 2 interfacce allo stesso tempo Quindi ho 4 operazioni di lookup per ogni intervallo Ovvero 1 lookup ogni 12,8us
Di solito in questi algoritmi il limite alle prestazioni è il singolo accesso a memoria, mentre le operazioni aritmetiche hanno un impatto trascurabile.
Il primo bridge Dec aveva un tempo di accesso a memoria di 100ns Max numero di righe= 8000 Soluzione: array ordinato Max n. accessi a memoria= log2(8000)=13 Costo di lookup = 1,3us
Tecnologia FDDI
è una tecnologia di rete ad anello, ha lunghezza minima della trama 40Byte Velocità= 100Mbit/s Tempo tra 2 trame = 3.2us
Per migliorare le prestazioni si potrebbero usare memorie più veloci ma questo alzerebbe il prezzo sul mercato, :( Per questo è stato introdotto l'uso delle tabelle hash Che consistono in una funzione di hash che mappa gli input in un array con indici di n bit Nel caso peggiore dell'utilizzo di una hash table, tutti i mac finiscono nella stessa chiave, quindi ho tempi di accesso analoghi ad una tabella Se ho una funzione di hash abbastanza buona da non avere collisioni, ho tempo di accesso costante Se inizio ad avere tante collisioni, posso cambiare la funzione di hashing Quello che si fa di solito è avere una famiglia di funzioni di hashing, ne scelgo una a caso e valuto le prestazioni, se va male cambio la funzione e ne scelgo un'altra.
Originariamente si era pensato ad un albero di 3 livelli invece ad una lista, questo permette di avere al massimo 7 collisioni Nell'implementazione del gigaswitch in caso di collisione si utilizzava una CAM ovvero una memoria che era in grado di fare ricerca in parallelo in hardware.
MAC 48bit A(x)=a0x^47+a1x^46+...+a46x+a47 Sono i bit del mac address H(x)=A(x)M(x)modG(x) output,input,parametro che determina una specifica funzione hash