Algoritmo per deframmentare i problemi cross-pipe in una rete per i segnali di routing tramite?

Per i commenti di Steve Ever ho esaminato i diagrammi di flusso. Alla fine sono incappato nel concetto di flussi multi-commodity ( link ) che in sostanza afferma che il problema è noto per essere un Problema NP-completo; non esiste un algoritmo elaborato per risolvere il problema come lo avevo definito in modo apparente.

Tuttavia, mi rifiuto di accettare il tipo di rallentamento che un approccio prettamente NP-completo richiederebbe. Invece ho deciso di ridefinire leggermente il problema. Usando una versione piuttosto bastardata dell'approccio buddy ( link ) sono in grado di ottenere il mio tempo di allocazione per registrare ( n) per la maggior parte dei miei tubi. Ho ancora bisogno di un approcchio NP completo per il passaggio finale, ma il passaggio finale può essere limitato a una situazione con solo poche decine di "flussi" / pipe da mappare, rendendo possibile anche un approcio NP. Tuttavia, questo approcio dipende dalle specifiche del mio sistema, non risolve il problema come detto sopra, semplifica i fattori a una frazione così piccola da rendere NP completo fattibile.

Ci scusiamo per chiunque abbia letto questo problema che sperava in una buona soluzione al problema dichiarato. Il meglio che posso suggerire è Programmazione lineare.

Non penso che tu abbia un problema con il grafico, penso che tu abbia un problema di riempimento del contenitore .

Per quanto ne so, la teoria dei grafi è preoccupata per la lunghezza della rotta (più corta, più lunga, # di spigoli, ecc ...) mentre il problema del packing bin riguarda l'utilizzo più efficiente di alcuni container.

Nel tuo caso, le pipe di rete sono i tuoi contenitori e la larghezza di banda dei segnali è ciò che stai impacchettando nei tuoi tubi.

L' articolo di Wikipedia sulla confezione bin descrive brevemente alcuni algoritmi o approcci da considerare. È un problema NP-difficile, ma si possono trovare soluzioni ottimali se si è in grado di "imbrogliare" le regole. Sospetto che una soluzione "abbastanza buona" possa essere facilmente trovata per il tuo caso, e ci sono alcune implementazioni suggerite collegate all'interno dell'articolo.

Nel caso più semplice, avrai una serie di bin in cascata da ottimizzare. Ogni livello della serie rappresenterebbe un passaggio attraverso la rete della rete. Questo approccio presuppone che sia possibile commutare i percorsi nodali al volo o che la larghezza di banda del segnale rimanga fissa per l'intervallo di configurazione. In sostanza, si tratta di un approccio divide et impera che utilizza un algoritmo di bin packing per ottimizzare l'utilizzo della larghezza di banda.

Se hai bisogno di affrontare il caso più complesso in cui devi considerare la capacità del percorso completo, a più passaggi, dovrai modificare il tuo approccio all'algoritmo del contenitore. Potresti imbatterti in questo caso se non puoi configurare al volo. La sfida in questo caso è che ogni segnale dato potrebbe avere più percorsi attraverso la mesh, ma è necessario tenere conto della capacità consumata dal segnale in base al percorso effettivamente utilizzato.

Vorrei ingannare il caso più complesso iniziando con il numero minore di segnali o il numero di potenziali percorsi. In questo caso, l'algoritmo di primo adattamento potrebbe essere un punto ragionevole da avviare. Probabilmente dovrai eseguire una serie di iterazioni e dovrai implementare una sorta di memoria all'interno dell'algoritmo per evitare di avviare scenari che non si risolvono.

Un'altra considerazione per aiutare la convergenza dell'algoritmo è quella di non preoccuparsi dell'utilizzo "ideale" o "più efficiente" della capacità. La realtà è che "abbastanza buono" significa che tutti i segnali passano attraverso un numero ragionevole di hop. Cavillare sull'efficienza una volta superata abbastanza è improbabile che fornisca utili benefici per il tuo sforzo.

Infine, se esiste un grado di varianza all'interno delle capacità del segnale, aggiungerei una capacità di riserva per tubo o sovrastimerebbe la larghezza di banda del segnale per fornire spazio per le escursioni al di fuori della norma.