Che cosa fa la ricerca del percorso nel routing Internet e in che modo è diversa da A *?

6

Nota: se non capisci questa domanda, non esitare a chiedere chiarimenti nei commenti anziché votare, potrebbe essere che questa domanda abbia bisogno di un po 'più di lavoro al momento. Sono stato indirizzato qui dalla chat room di Stack Excange Root Access perché la mia domanda non si adattava Super User .

In molti aspetti gli algoritmi di individuazione dei percorsi come una stella sono molto simili all'instradamento di Internet. Ad esempio:

A node in an A* path finding system can search for a path though edges between other nodes.

A router that's part of the internet can search for a route though cables between other routers.

Nel caso di A *, gli elenchi aperti e chiusi vengono mantenuti dal sistema nel suo insieme, separatamente da ogni singolo nodo e ogni nodo è in grado di memorizzare temporaneamente uno stato che comprende più numeri.

I router su Internet sembrano avere proprietà notevoli, come ho capito:

They are very performant.

New nodes can be added at any time that use a free address from a finite (not tree like) address space.

It's real routing, like A*, there's never any doubling back for example.

Similar IP addresses don't have to be geographically nearby.

The network reacts quickly to changes to the networks shape, for example if a line is down.

Routers share information and it takes time for new IP's to be registered everywhere, but presumably every router doesn't have to store a list of all the addresses each of it's directions leads most directly to.

Sto cercando una descrizione di base, generale e di alto livello dei meccanismi degli algoritmi dal punto di vista di un singolo router. Qualcuno ne ha uno?

Suppongo che i router pubblici di Internet non utilizzino A * in quanto le spese generali sarebbero troppo grandi e ridotte al minimo. Presumo anche che ci sia un unico metodo in tutto il mondo perché sembra che debba coinvolgere molti dati di trasferimento per aggiornare e comunicare una quantità ragionevole di stato tra router vicini.

Ad esempio, forse la quantità di dati che deve essere memorizzata in ogni router scala logaritmicamente con il numero di router che esistono in tutto il mondo, il dettaglio e l'affidabilità del routing sono ridotti a distanze crescenti, c'è un aumento del backtracking coinvolto nelle parti della rete che sono meno geograficamente uniformi o forse ogni router esegue effettivamente una ricerca in stile A *, mantenendo temporaneamente gli elenchi aperti e chiusi quando arriva un pacchetto.

    
posta alan2here 09.06.2012 - 21:12
fonte

1 risposta

6

La principale differenza tra gli algoritmi effettivamente utilizzati per l'instradamento Internet e l'algoritmo A * è che

  • L'algoritmo A * richiede tutte le informazioni su una rete - conoscenza di ogni nodo e esattamente come i nodi sono connessi - su una singola macchina, e quella macchina trova il percorso completo migliore.
  • Gli algoritmi di routing del pacchetto in esecuzione su un router sono "algoritmi distribuiti" che utilizzano varie euristiche per ottenere risultati "buoni" (ma raramente i "migliori") con quantità molto limitate di informazioni su ciascun router e quantità di tempo molto limitata a router. Ogni router fa un po 'di lavoro - sceglie il prossimo passo nel percorso. Nessuno dei router calcola mai un "percorso completo" e il percorso effettivo percorso da un pacchetto è raramente il migliore.

Poiché A * trova il percorso migliore, perché usiamo altri algoritmi che ci forniscono percorsi non ottimali? L'algoritmo A * è impossibile su Internet per diversi motivi. Ora ci sono così tanti nodi su Internet che non è pratico per un router avere abbastanza RAM per memorizzare l'indirizzo IP di ogni nodo e quali nodi sono collegati ad esso. Anche se ogni router ha un sacco di RAM, quando viene acceso un nuovo router o viene installato un nuovo collegamento, ci aspettiamo che il nuovo percorso inizi a gestire i pacchetti più o meno immediatamente, piuttosto che aspettare che il router scarichi la connessione diagramma dell'intero internet e in attesa di ogni altro router sul pianeta per aggiornare il suo schema di connessione. Molti router hanno pacchetti in entrata così veloci che non c'è semplicemente abbastanza tempo per eseguire un algoritmo A * completo su ogni pacchetto. In alcuni casi, i cambiamenti nella rete che influenzano il percorso di un pacchetto possono verificarsi mentre il pacchetto è in volo, dopo che il pacchetto è stato inviato.

Ho sentito che il protocollo di routing più semplice possibile - "routing hot potato" - funziona sorprendentemente bene nei piccoli internetworks: Ogni router tiene traccia dell'indirizzo IP di ciascun nodo finale direttamente collegato ad esso. Se il router riceve un pacchetto con uno di questi come indirizzo di destinazione, il router lo invia a quel nodo finale e il percorso del pacchetto è completo. In caso contrario, un router che utilizza "routing hot potato" invia in modo casuale il pacchetto in arrivo a qualsiasi router direttamente collegato ad esso.

Ho saputo che il Border Gateway Protocol è attualmente il più popolare protocollo di reindirizzamento su Internet. RFC4271 (e il suo errata ) fornisce informazioni dettagliate che, in linea di principio, sono sufficienti per costruire un router interoperabile.

In genere tali protocolli utilizzano una combinazione di due tecniche per consentire a ciascun router di creare la propria tabella di routing :

  • Passiva: quando un pacchetto da un indirizzo IP A arriva sulla porta X, e in seguito qualche pacchetto con una destinazione dello stesso indirizzo IP A arriva su un'altra porta, il router lo sa deve inviare il secondo pacchetto alla porta X. Il numero di indirizzi univoci associati a una porta diventerà troppo grande per archiviarli tutti, quindi il router utilizza riepilogo delle rotte . Il riepilogo delle rotte si basa sul fatto che le macchine geograficamente vicine, infatti, hanno in genere indirizzi IP simili e gli indirizzi IP sono distribuiti in modi che tipicamente formano un albero gerarchico di sottoreti geografiche.
  • Attivo: il router invia il proprio indirizzo IP e (un sommario) gli indirizzi IP delle macchine direttamente connesse ad esso, ai router vicini, in genere utilizzando protocollo di informazioni di routing .
risposta data 10.06.2012 - 19:08
fonte

Leggi altre domande sui tag