Cammini Minimi in Grafi Orientati

Appunti su Cammini Minimi in Grafi orientati

Download

Metodologia Greedy (Algoritmi Golosi)

Introduzione alla Metodologia Greedy (Algoritmi Golosi)

Download 1

Download 2

Network Simulator 2 (Parte Prima)

Network Simulator 2 è un simulatore di reti scritto in C++ e OTCL. Per poter realizzare una simulazione è necessario impostare mediante uno script uno scenario caratterizzato da nodi di trasmissione con relativi buffer e linee di uscita con una certa capacità, tempo di arrivo e lunghezza dei pacchetti, numero di pacchetti per nodo, ritardo dei pacchetti, topologia della rete da simulare,sorgenti di traffico,perdita di pacchetti ecc. Il simulatore fornirà, avviata la simulazione, un trace-file da analizzare, mediante l’analisi del quale otterremo i dati da rappresentare. La simulazione può avere una durata variabile secondo la complessità del modello. Per potere rappresentare lo scenario ns fornisce diversi oggetti che dovremo accuratamente utilizzare. Essi sono nodi, link, agenti di trasporto, generatori di traffico e ricevitori, applicativi. Bisogna tenere in considerazione, durante le simulazioni, della possibilità di perdita di pacchetti dovuta a errori di trasmissione sui link, eccessivo traffico, ritardi e sottodimensionamenti delle code e così via. Per le code vanno tenuti in considerazione la politica di gestione della coda, degli arrivi dei pacchetti (processo degli arrivi), lunghezza dei pacchetti e capacità dei link (processo dei tempi di servizio). Tra le politiche di gestione dei pacchetti individuiamo:

DropTail: i pacchetti vengono elaborati secondo l’ordine di arrivo nella coda

SFQ (Stochastic Fair Queue): si cerca di fornire una distribuzione statisticamente uguale ai pacchetti servendo in maniera equa le sorgenti

DRR (Deficit Round Robin): ogni sorgente ottiene un quanto di bit da trasmettere.

RED (Random Early Detection): si cerca di determinare la soglia di saturazione prima della saturazione stessa e si scartano i pacchetti provenienti da tutti i flussi prevenendo la congestione.

La componente OTCL di NS permette di definire le classi OTCL direttamente connesse alle classi C++, fornisce i metodi per accedere a tale classi e consente di instanziare gli oggetti che compongono il modello da simulare. Vediamo come utilizzare le classi NS:

2.0 Iniziare con NS

La prima cosa da fare è instanziare lo schedulatore del simulatore ed è sempre la prima istruzione da inserire:

set nome_simul [ new Simulator]

Possiamo poi instanziare i nodi:

set primo_nodo [$nome_simul node]

set secondo_nodo [$nome_simul node]

e i relativi agenti:

set primo_agente [ new tipo_agente]

set secondo_agente [ new tipo_agente]

Gli agenti vanno poi collegati ai relativi nodi

$nome_simul attach-agent $nome_nodo $nome_agente

E connessi tra loro

$nome_simul connect $primo_agente $secondo_agente

Due nodi possono essere collegati con il comando

$nome_simul duplex-link $primo_nodo $secondo_nodo dimensione_banda tempo_transito tipo_coda

Possiamo poi instanziare l’applicazione

set nome_applicazione [new tipo_Applicazione]

e collegarlo all’agente

$nome_applicazione attach-agent $nome_nodo $nome_agente

Possiamo poi avviare l’applicazione ad un tempo stabilito, ad esempio 0.1

$nome_simul at 0.1 “$nome_applicazione start”

E terminarla al tempo 0.3 con il comando

$nome_simul at 0.3 “exit”

Tutto quello che abbiamo visto fino ad ora lo potete trovare sul primo file di esempio presente nell'archivio.

Adesso facciamo partire il simulatore. Il simulatore avrà bisogno di un tracefile opportunamente gestito.Apriamo il tracefile di NAM come un comune file in sola scrittura:

set nome_file [open out.nam w]

E associamolo al simulatore

$nome_simulatore namtrace-all $fd

Sarà necessaria una procedura per gestire la chiusura del tracefile e la sua esecuzione. Potete trovare la procedura sul file di esempio presente nell'archivio. La prima cosa che la procedura dovrà fare sarà accedere al tracefile mediante il comando

global nome_simulatore nome_file

Dovrà poi svuotare il buffer con:

$nome_simulatore flush-trace

Dopo dovrà chiudere il file ed eseguire NAM su di esso

close $nome_file

exec nam out.nam &

exit 0

Nell'esempio allegato sarà mostrata la procedura che non ricorre a variabili globali.Dopo la chiusura della nostra applicazione, possiamo eseguire la procedura finish e avviare il simulatore con il comando:

$nome_simulatore run

Estendiamo l'esempio precedente impostando le regole di routing.Per impostare il protocollo di routing unicast si utilizza il comando:

$nome_simul rtproto Static per il routing statico (default)

$nome_simul rtproto Session per il session routing

$nome_simul rtproto DV $nodo1 ….. $nodoN per il Distance Vector routing sui nodi

$nome_simul rtproto LS $nodo1 $nodo2 per il Link State Routing

Per il multicast, dopo aver instanziato il simulatore eseguiamo il comando

$nome_simul multicast

e il comando

$nome_simul mrtproto type

dove type è:

CtrMcast per il Centralized Multicast

DM per il Dense Mode Multicast

ST per il Shared Tree Mode Multicast

BST per il Bi-directional Shared Tree Mode Multicast

Occupiamoci adesso della perdita dei dati. Dobbiamo creare un modello per gestire la perdita dei dati:

set nostro_modello [new ErrorModel]

E configuriamo il rate di perdita (specificando un valore x)

$nostro_modello set rate_ x

Possiamo indicare l'unità e la variabile casuale

$nostro_modello unit type

$nostr_modello ranvar type

E impostare il target

$nostro_modello drop-target type

Nell'archivio è presente un esempio sull'uso di questi comandi. Fino ad ora abbiamo utilizzato il prot TCP a livello trasporto. Per settare il protocollo UDP utilizziamo i comandi:

set sorgente [new Agent/UDP]

set destinazione [new Agent/NULL]

Sorgente e destinazione vanno poi collegati tra loro e ai rispettivi nodi come visto in precedenza.

3.0 Classe Node

Abbiamo visto che ns supporta due tipi di nodi: Unicast (un solo mittente e un solo destinatario) e Multicast (un mittente e più destinatari).Adesso vediamo le funzioni messe a disposizione per la gestione dei nodi. Ogni nodo ha un identificatore costituito da un intero che viene incrementato ad ogni nuova istanza. Per accedere a tale identificatore usiamo

$nome_nodo id

Mentre per accedere al suo indirizzo usiamo

$nome_nodo node_addr

I nodi vicini sono indicati da una lista accessibile da

$node neighbors

Un collegamento tra due nodi è rappresentato da un link. Esso è costituito da cinque elemneti principali:

head_ rappresenta il punto di ingresso del nodo

queue_ rappresenta la coda principale del link

link_ l'oggetto che modella il link

ttl_ oggetto che gestisce il ttl dei pacchetti

drophead_ oggetto che gestisce lo scarto dei pacchetti

Altri oggetti gestiscono il tracciamento dei pacchetti

enqT_ traccia i pacchetti in ingresso

deqT_ traccia i pacchetti in uscita

drpT_ traccia i pacchetti scartati

rcvT_ traccia i pacchetti ricevuti dal nodo successivo

La creazione di un link (la abbiamo già vista) viene effettuata tramite il comando

$nome_simul type-link node1 node2 bw delay qtype args

dove qtype può assumere i valori:

DropTail per la coda FIFO

FQ per il fair queuing

SFQ per la stochastic fair queuing

DRR per la deficit round robin queue

RED per la random early detection queue

CBQ per la class-based queuing

CBQ/WRR per la weighted round robin CBQ

E' possibile definire la dimensione massima della coda con

$nome_simul queue_limit _node1_ _node2_ _limit_

e il ritardo di propagazione nella direzione indicata (rappresentato da timeinterval) con:

$nome_simul delay node1 node2 timeinterval

Alcuni metodi permettono di gestire lo stato del link:

$nome_simul rtmodel-at time command node1 node2

dove command può essere:

up per attivare un collegamento

down per disabilitare un collegamento

up? per interrogare lo stato del link

cost per settare il costo

cost? Per interrogare il costo di un link

4.0 Classi Agent, Application, Traffic Generator

Un agente è un elemento che genera il traffico dati (trasmettitore), rimuove il traffico ricevuto (ricevitore) o fa entrambe le cose (bidirezionale). In realtà non si opera con dati reali ma solo con le dimensioni delle informazioni al fine di tenere traccia della quantità di dati trasmessi. Esistono numerosi tipi di agenti, ciascuno configurabile manualmente. Consultate il manuale ns per avere informazioni dettagliate sui protocolli. La classe Application permette di definire il modello di applicazione al quale associare un profilo di traffico definito dalla classe TrafficGenerator. Esistono 4 classi derivate da TrafficGenerator, ciascuna rappresentante un modello di traffico differente:

EXPOO_TRAFFIC : per il modello di traffico “On/Off” con distribuzione esponenziali dei tempi di permanenza in ogni stato

POO_Traffic: per il modello con tempi di permanenza in ciascuno stato distribuiti secondo una distribuzione di Pareto .

CBR_Traffic: per il modello di traffico a rate costante, con pacchetti di dimensione fissa

TrafficTrace:per il modello di traffico basato su misurazioni reali importate da un trace file).

5.0 Raccolta dei Risultati

Si può ricorrere a due strategie per raccogliere i risultati della simulazione:

Mediante tracefile. Un trace è un oggetto inserito in un link, che raccoglie tutti gli eventi che coinvolgono i pacchetti trasmessi su di esso. Ogni pacchetto è tracciato mendiante la sua intestazione costituita da:

identificativo univoco

tipo di pacchetto

dimensione del pacchetto

identificativo dell’interfaccia di trasmissione (per il multicast)

identificativo di flusso

nodo sorgente

nodo destinazione

Per utilizzare un tracefile bisogna prima aprirlo in scrittura

$nome_simul nome_trace_file [open nome_file w]

Scrivere su file tutte le informazioni raccolte:

$nome_simul trace-queue $node1 $node2 $nome_trace_file

E infine chiudere il file:

close $nome_trace_file

Le voci scritte su file saranno caratterizzate dai seguenti attributi:

tipo di evento (ricezione, accodamento, trasmissione, scarto)

istante in cui si verifica l’evento

nodo sorgente

nodo destinazione

tipo di pacchetto

dimensione del pacchetto

flag per utilizzi specifici (collegamenti wireless, etc,...)

identificativo di flusso

indirizzo e porta del mittente

indirizzo e porta del destinatario

numero di sequenza

identificativo univoco di pacchetto

E' possibile fare il trace di tutti i pacchetti su tutti i link:

$nome_simul namtrace-all $nome_nam_file

$nome_simul trace-all $nome_trace_file

O su uno specifico link:

$nome_simul trace-queue $node0 $node1 $nome_trace_file

$nome_simul namtrace-queue $n0 $n1 $nome_trace_file

Mediante Monitor: un monitor consente di analizzare alcune variabili del modello:

size_ dimensione della coda in byte

pkts_ numero di pacchetti in coda

parrivals_ numero di pacchetti arrivati

barrivals_ numero di byte arrivati

pdepartures_ numero di pacchetti trasmessi

pdrops_ numero di pacchetti scartati

bdrops_ numero di byte scartati

Download 1

V

Validator: componente che analizza la struttura grammaticale e sintattica di un testo, costituito da sequenze di tokens, al fine di stabilirne la coerenza con determinati standard linguistici. Appartiene alla famiglia dei parser.

Elementi di Programmazione Dinamica

Elementi di Programmazione dinamica

Download Parte Prima

Download Parte Seconda

Download Parte Terza

Parte Seconda e Terza inserita il 11/12/09 alle ore 6.35

Tabelle Hash

introduzione all'hashing

Download

Correzione pag.7 il 16/11/2009 ore 12.51

Correzione pag.2 il 27/11/2009 ore 17.48

B-Tree

introduzione ai b-alberi

Download

TCL\OTCL (Tool Command Language\Object TCL)

1.0 Fondamenti

Tcl/Otcl è un linguaggio di scripting position-based, solitamente usato su sistemi embedded costituito da una sequenza di comandi separati dal carattere “newline” o ; . Ogni comando è composto da una o più parole che rappresentano la direttiva e i parametri presi in input. Ogni comando genera un suo output costituito da una stringa stampata a video. A differenza di molti linguaggi di scripting il Parser non assegna significati agli argomenti. Ad esempio il comando

% set y 4

Assegna alla variabile y il valore 4

% set x y+5

Assegna alla variabile x il valore stringa “y+5”

%set w $y+10

Assegna alla variabile w il valore stringa “4+10”. Il simbolo $ permette di accedere alla variabile memorizzata con il nome indicato subito dopo il carattere stesso.
Per effettuare le operazioni aritmetiche si ricorre al comando

%expr espressione

Dove espressione rappresenta l’espressione aritmetica che vogliamo calcolare. Il nome di una variabile può contenere lettere , numeri e underscore. Non è necessario definire variabili prima del loro uso. Con la sintassi [ comando ] è possibile inserire comandi come parametri di altri comandi. Ad esempio

%set x [ set y 10]

Assegnerà ad x ed a y il valore 10. In alternativa si può usare “ ”.

%set b 5
%set x “ b-5 vale [ expr $b-5] ”

Ora x varrà “b-5 vale 0”.
I caratteri speciali come $ possono essere ignorati se preceduti dal caratter \ . Ad esempio

%set x \$

Assegnerà ad x il valore stringa $ . Può anche permettere di scrivere un comando su più linee ignorando il carattere “invio”.
Il comando puts permette la scrittura su un determinato device. Per stampare su schermo scriviamo

%puts “ Esempio di stampa su schermo”

I commenti vanno preceduti dal carattere #
Adesso lavoriamo con le stringhe. Possiamo utilizzare i tradizionali caratteri speciali

* zero o più caratteri
? un singolo carattere
[ x-y] un carattere del set compreso dalle lettere qui indicate come x e y
[ ] un set tra i caratteri presenti all’interno delle parentesi.

Le stringhe possono essere manipolate mediante il comando

%String option ?args? ?args?

Vediamo alcune opzioni.

%string first pattern stringa2 ?start_index?

Cerca pattern in stringa2 a partire da start_index se specificato. Ritorna la posizione della prima occorrenza trovata, altrimenti ritorna -1. Possiamo usare l’opzione last al posto di first per avviare la ricerca a partire dall’ultimo carattere.

%string length stringa

ritorna il numero di caratteri presenti in stringa.

%stringa match ?-nocase? pattern stringa

verifica se pattern corrisponde a stringa, altrimenti ritorna -1. Con –nocase è possibile il match è case-unsensitive.

%string range stringa inizio fine

ritorna il range di caratteri trovati in stringa a partire dal pattern inizio e a finire con il pattern fine.

%string tolower stringa ?first? ?last?

ritorna la conversione in minuscolo di stringa a partire da first e a finire con last se questi sono specificati. Al posto di tolower si può specificare toupper per convertire in maiuscolo.

%scan string_format var_name ?var_name2?....

Effettua il parsing dei parametri indicati come var_name secondo la convenzione specificata da string_format. Ad esempio si può usare

%d per intero decimale
%o per intero ottale
%x per intero esadecimale
%b per intero binario
%c per singolo carattere

%format format_string ?arg1? ?arg2?...

Formatta arg1,arg2…. Second la convenzione specificata da format_string
Per ulteriori comandi potete consultare il manuale.

2.0 Liste e Array

Adesso vediamo come usare le liste. In tcl gli elementi di una lista vanno racchiusi tra {}. È possibile annidare più liste per creare matrici. Per creare una lista useremo il comando

%set nome_lista { elemento1 elemento2 ….}

mentre con il comando

%list nome_lista { elemento1 elemento2 ….}

si ottiene la stampa a video della lista ma non viene memorizzata.
Il primo elemento di una lista viene indicato con l’indice 0 mentre l’ultimo con l’indice end. Il comando

%lindex nome_lista ?indice?

restituisce l’elemento di indice ‘indice’ se specificato, altrimenti restituisce tutta la lista. Possiamo ordinare alfabeticamente una lista con il comando

%lsort nome_lista

Il comando supporta diverse opzioni.
Il comando

%lappend nome_lista elemento

inserisce ‘elemento’ alla fine della lista. In questo comando non va specificato il simbolo $ quando ci si riferisce ad una lista memorizzata . Ad esempio se creiamo la lista chiamata elenco e vogliamo inserire l’elemento ‘ultimo’ useremo

%lappend elenco ultimo

E non %lappend $elenco ultimo

Possiamo inserire un elemento nella posizione desiderata con il comando

%linsert nome_lista posizione elemento

Per sapere quanti elementi contiene una lista impartiamo

%llength nome_lista

Passiamo ora agli array. In tcl gli array sono associativi. Ciò vuol dire che l’indice è una stringa che possiamo scegliere a nostro piacere. Per creare una lista o per inserire un elemento usiamo il comando

%set array nome_array(indice) valore

Possiamo creare un array a partire da una lista con il comando

%set array nome_array [ list indice1 elemento1 indice2 elemento2 …]

Possiamo ottenere l’insieme delle coppie indice-valore con il comando

%array get nome_array

Qui non bisogna specificare $.Non otteniamo gli indici ordinati alfabeticamente ne secondo l’ordine di inserimento, ma secondo uno schema utilizzato da tcl per memorizzare la struttura dati. Per ottenere una lista di indici a partire da un pattern specifico usiamo

%array names nome_array ?pattern?

Se pattern non è specificato ritorna tutti i valori. Anche qui non va utilizzato il $.

3.0 Strutture di Controllo

Le strutture di controllo non differiscono molto dagli altri linguaggi. Qui però è importante rispettare la spaziatura tra un carattere e l’altro. Per maggiore chiarezza guardare gli esempi allegati.
Per la selezione:

if {espressione} {
body
} elseif {condizione} {
body
} else {
body
}

Per switch:

Switch ?option? string {
pattern1 body1
…..
}

Per while:

while {espressione} {
body
}

Per for:

for {variabile} {condizione} {cond_progr} {
body
}

Per foreach

foreach variabile { elem1 elem2 … } {
body
}

4.0 I/O su file

Adesso occupiamoci di I/O su file. I file possono essere acceduti mediante una variabile.

Per aprire un file impartiamo

%open nome_var [ open "nome_file" "mod"]

dove mod indica la modalità di accesso e può essere:

w+ per lettura e scrittura, crea il file se non esiste

r+ per lettura e scrittura, il file deve esistere

r per lettura

w per scrittura

..

Per scrivere un file usiamo il comando puts con parametro la nostra variabile.

%puts nome_var stringa

Chiudiamo il file con il comando

%close nome_var

Per leggere una riga usiamo il comando gets:

%gets nome_var

Per leggere byte usiamo il comando read

%read nome_var n

Dove n è il numero di byte che vogliamo leggere. La scrittura e la lettura verrà effettuata nella posizione in cui si trova il puntatore al file. Per muovere il puntatore nella posizione 'n' usiamo il comando:

%seek nome_var n

Per conoscere l'attuale posizione del puntatore invece diamo:

%tell nome_var

5.0 Procedure

In tcl le procedure possono essere definite per accettare un numero predefinito di elementi oppure un numero variabile. Inoltre possono essere richiamate ricorsivamente, possono ritornare valori o essere "void". Si definisce una procedura mediante la sintassi

proc nome_procedura args1... {

body

}

Se si decide di accettare un numero variabile di parametri, quando la procedura sarà invoca bisognerà racchiudere tutti i parametri tra " " oppure passarli come lista altrimenti l'interprete non sarà in grado di riconoscerli. Una procedura può anche accedere a variabile globali ma queste vanno prima definite prima della procedura, e poi bisognerà indicare all'interprete di cercare quella variabile fuori dalla procedura definita mediante il comando "%global var_name". Se ad esempio vogliamo usare la variabile globale "ciao" nella procedura "saluti" dobbiamo scrivere:

%set ciao ciao

%proc saluti tuo_nome {

global ciao

puts "$ciao $tuo_nome"

}

6.0 OTCL

Otcl è l’estensione ad oggetti di TCL. Anche se si parla di programmazione ad oggetti, OTCL non va pensato come un normale linguaggio Object Oriented come java o C++. In OTCL le classi possono essere definite in maniera incrementale, ovvero i metodi possono essere aggiunti in runtime. Ogni oggetto è un comando, ogni sottocomando è un argomento dell’oggetto. Possiamo definire una classe con il comando

%Class Nome_classe

e un oggetto con il comando

%Nome_classe nome_oggetto

Tutti le variabili e i metodo sono pubblici e tutte le classi ereditano dalla superclasse Object. Questa superclasse fornisce alcuni metodo per reperire informazioni sulle classi o sugli oggetti. Un oggetto può essere distrutto con il comando

%nome_oggetto destroy

Una variabile di un oggetto può essere instanziata con il comando

%nome_oggetto set nome_variabile valore

Se non specifichiamo il valore il comando fornità come risultato il valore attuale della variabile.
Una variabile di classe può essere instanziata con il comando

%nome_classe set nome_variabile valore

e può essere richiamata all'interno delle procedure mediante il comando

%class instvar nome_variabile

Da questo momento in poi, all'interno della procedura, la variabile di classe sarà disponibile.
Possiamo aggiungere un metodo ad una classe con il comando

%nome_classe instproc nome_metodo args1…. {
body
}

I metodi possono essere richiamati con il comando:

%nome_oggetto nome_metodo ?args?

La parola chiave $self può essere utilizzata per riferirsi all’interno di un metodo all’attuale oggetto instanziato . Il comando

%$self instvar nome_variabile

Permette di accedere alla variabile definita da qualche parte all’interno della classe grazie al comando 'instavar'. Un metodo particolare è il costruttore. Serve all’interprete per poter richiamare il costruttore di Object. Se non viene definito dal programmatore verrà implementato dall’interprete. Un metodo costruttore ha la forma:

%nome_classe instproc init {args} {
……body….
eval $self next $args
}

L’ultimo rigo di comando permette all’interprete di richiamare il costruttore della superclasse.
Otcl ammette l'ereditarietà multipla. Per per ereditare da una serie di classi usiamo:

%Class nome_classe -superclass {nome_superclasse1 nome_superclasse2....}

Nel caso in cui le superclassi implementassero metodi con stess prototipo e firma, uno soltanto dei metodi verrà ereditato. Sarà l'ordine con cui sono indicate le superclassi a stabilire quale sarà il metodo ereditato. Le classe indicata per prima avrà priorità maggiore rispetto alle successive. E' possibile scrivere classi in file script diversi. Basta scrivere il codice su file, ad esempio, un file per ogni classe, scrivere il "main" su di un file aggiungendo come primissime istruzioni i comandi

%source nome_script

uno per ogni file che abbiamo scritto. Il "main" sarà l'unico file che dovremmo eseguire direttamente.

Download1

Download2

Archivio Download1 aggiornato il 07/11/2009 alle 14.15

Archivio Download2 inserito il 10/11/2009 alle 19.55

Correzione post il 12/11/2009 alle 12.26

Correzione Download2 il 05/12/2009 alle 18.33

K

Known Iusses: insieme di problemi noti agli sviluppatori, posti all'attenzione degli utenti. Tali problemi possono rappresentare bugs non ancora risolti oppure emergono in corrispondenza di cattivi utilizzi da parte degli utenti o in presenza di software con problemi di compatibilità.