---

Hej NG!

Vi er ved at opbygge en netværkssimulator med nogle netværks knuder og
forbindelser derimellem. Får at kunne rute pakkerne rundt på netværket, skal
vi have udregnet bedste ruter til rutningstabellen. Derfor skal vi have
repræsenteret hele netværket i en træ struktur! Vi koder i Java, og kan ikke
finde ud af om der findes en velegnet struktur....vi har kigget lidt på
JTree, men ved ikke om denne er den rigtige. Er der nogen der har nogle
erfaringer med dette emne?

mvh
Allan & Mikkel

---

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

"holst" <holst@control.auc.dk> writes:

> Vi koder i Java, og kan ikke finde ud af om der findes en velegnet
> struktur....vi har kigget lidt på JTree, men ved ikke om denne er
> den rigtige.

Hvorfor bruge så lang tid på spekulation, når I kan lave jeres egen på
et kvarter?

Martin

- --
Homepage: http://www.cs.auc.dk/~factotum/
GPG public key: http://www.cs.auc.dk/~factotum/gpgkey.txt
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: Using Mailcrypt+GnuPG <http://www.gnupg.org>

iEYEARECAAYFAj3SuaEACgkQYu1fMmOQldW7GwCgyUxrTbM95PZs/lUIzSt7ZGYJ
rjMAn1GNZoKsx7eRWbsiMWZ9CTEA4oKn
=jKxv
-----END PGP SIGNATURE-----

---

Martin Christensen <knightsofspamalot-factotum@gvdnet.dk> writes:

> Hvorfor bruge så lang tid på spekulation, når I kan lave jeres egen på
> et kvarter?

Fordi velvalgte datarepræsentation kan have stor betydning for
køretiden og hukommelsesforbruget.

Alt efter Allan og Mikkels netværkstopologi er der forskellige
grafrepræsentationer der giver det bedste resultat, og hvis man bare
naivt vælger en kan man let vælge galt.

--
Peter Makholm | I congratulate you. Happy goldfish bowl to you, to
peter@makholm.net | me, to everyone, and may each of you fry in hell
http://hacking.dk | forever
| -- The Dead Past

---

> Fordi velvalgte datarepræsentation kan have stor betydning for
> køretiden og hukommelsesforbruget.

Hørt!

> Alt efter Allan og Mikkels netværkstopologi er der forskellige
> grafrepræsentationer der giver det bedste resultat, og hvis man bare
> naivt vælger en kan man let vælge galt.

Ja, det lyder bare som om at du har en masse færdige løsninger
som er implementeret, og så skal du bare vælge een...

Altså... ellers ville man vel bare analysere sine behov/krav
og så gå i gang med at lave "den bedste"?? Eller hvad??

/ Michael

---

"Michael Banzon" <anyone@anywhere.anyhow> writes:

> Ja, det lyder bare som om at du har en masse færdige løsninger
> som er implementeret, og så skal du bare vælge een...

Næhhhh, det er ikke så tit jeg laver advanceret graf-behandling.

> Altså... ellers ville man vel bare analysere sine behov/krav
> og så gå i gang med at lave "den bedste"?? Eller hvad??

Ja, hvor 'gå i gang' betyder at tage en algoritmikbog og læse den.

--
Peter Makholm | Have you ever felt trapped inside a Klein bottle?
peter@makholm.net |
http://hacking.dk |

---

holst wrote:

> Vi er ved at opbygge en netværkssimulator med nogle netværks knuder og
> forbindelser derimellem. Får at kunne rute pakkerne rundt på netværket, skal
> vi have udregnet bedste ruter til rutningstabellen. Derfor skal vi have
> repræsenteret hele netværket i en træ struktur! Vi koder i Java, og kan ikke
> finde ud af om der findes en velegnet struktur....vi har kigget lidt på
> JTree, men ved ikke om denne er den rigtige. Er der nogen der har nogle
> erfaringer med dette emne?

Jeg vil tro at I mere har brug for en generel graf end et træ (netværket er vel
ikke uden 'cirkler'?), men I skulle i hvert fald kunne finde en passende
struktur her:
<http://www.cs.williams.edu/~bailey/JavaStructures/>

(jeg har ikke selv brugt klasserne)

Ulrik Magnusson

---

"holst" <holst@control.auc.dk> wrote in message
news:aquccs$8f9$1@sunsite.dk...
> Hej NG!
>
> Vi er ved at opbygge en netværkssimulator med nogle netværks knuder og
> forbindelser derimellem. Får at kunne rute pakkerne rundt på
netværket, skal
> vi have udregnet bedste ruter til rutningstabellen. Derfor skal vi
have
> repræsenteret hele netværket i en træ struktur! Vi koder i Java, og
kan ikke
> finde ud af om der findes en velegnet struktur....vi har kigget lidt
på
> JTree, men ved ikke om denne er den rigtige. Er der nogen der har
nogle
> erfaringer med dette emne?

Den slags er næppe indbygget i Java, men bortset fra det har jeg masser
af erfaring indenfor området - blot med pascal som sprog.

Prøv evt. nogle af linkene på min hjemmeside.

Hilsen
Uffe Kousgaard
www.routeware.dk

---

"holst" <holst@control.auc.dk> skrev i en meddelelse
news:aquccs$8f9$1@sunsite.dk...
> Hej NG!
>
> Vi er ved at opbygge en netværkssimulator med nogle netværks knuder og
> forbindelser derimellem. Får at kunne rute pakkerne rundt på netværket,
skal
> vi have udregnet bedste ruter til rutningstabellen. Derfor skal vi have
> repræsenteret hele netværket i en træ struktur! Vi koder i Java, og kan
ikke
> finde ud af om der findes en velegnet struktur....vi har kigget lidt på
> JTree, men ved ikke om denne er den rigtige. Er der nogen der har nogle
> erfaringer med dette emne?

I kan jo kigge på Graph Foundation Classes for Java fra IBM alphaworks
(http://www.alphaworks.ibm.com/tech/gfc)
Niels Harremoës


>
> mvh
> Allan & Mikkel
>
>

---

"holst" wrote

> Vi er ved at opbygge en netværkssimulator med nogle netværks knuder og
> forbindelser derimellem. Får at kunne rute pakkerne rundt på netværket, skal
> vi have udregnet bedste ruter til rutningstabellen. Derfor skal vi have
> repræsenteret hele netværket i en træ struktur! Vi koder i Java, og kan ikke
> finde ud af om der findes en velegnet struktur....vi har kigget lidt på
> JTree, men ved ikke om denne er den rigtige. Er der nogen der har nogle
> erfaringer med dette emne?

I foråret designede og implementerede mine venner og jeg faktisk en
lille hændelsesdrevet netværkssimuleringspakke (eng. 'event driven
simulation'), som en del af et projekt omkring routing inspireret af
den måde myrer finder mad på Vi anvendte primært vores egen
datastruktur, basalt set bygget ovenpå en graf-repræsentation, men med
visse modifikationer af graf-datastrukturen, så den kunne simulere et
netværk med flow af pakker og med begrænset kapacitet på både routere
og køer.

Hvis I er interesserede er hele rapporten og koden frit tilgængelig på
officehelp.gone.dk/ITCProjekter/AntRoutingSystem/AntRoutingSystem.html

(hvis dette link fejler, som det gjorde lige da jeg afprøvede det nu
så prøv det mere kryptiske :
http://w1.1791.telia.com/~u179101311/ITCProjekter/AntRoutingSystem/AntRoutingSystem.html
- det skulle virke.)

En lille ekstranote, der måske kunne være interessant for jer - for at
kunne vise disse grafer 'pænt', anvendte vi desuden en frit
tilgængelig pakke "Grappa" (se
http://www.research.att.com/~john/Grappa/), som også tilbyder en lang
række graf-datastrukturer og generelle tools.

Jeg vil dog foreslå at i konstruerer jeres egne datastrukturer (gerne
inspireret af vores). Grappa-pakken er meget generel og til tider lidt
(for) C-inspireret

vh troels

---

On 20 Nov 2002 14:17:40 -0800, Troels C. Damgaard <tcd@it-c.dk> wrote:
> http://w1.1791.telia.com/~u179101311/ITCProjekter/AntRoutingSystem/AntRoutingSystem.html

Routing via scentnedliggelse fra de ''myrer'' der passerer en router? Det lyder
som swarm-intelligence. Blev det effektivt?

--
Jesper - Der burde downloade rapporten og læse...

---

jlouis@pc-063.diku.dk (Jesper Louis Andersen) wrote

> Routing via scentnedliggelse fra de ''myrer'' der passerer en router? Det lyder
> som swarm-intelligence. Blev det effektivt?

Hmmmm, godt spørgsmål.

Den korte version er - vi har en formodning om at det kan blive
effektivt - i visse situationer...

En lidt længere version følger... (men kortere end rapporten )

Marco Dorigo (der er en af de tunge drenge bag myre-algoritme-tingen)
og et par andre forskere har rapporteret (og skrevet en bunke artikler
om) at have lavet nogle overordentligt velfungerende og effektive
myrealgoritmer. Bl.a. en routing-algoritme 'AntNet' til
packet-switchede netværk (internettet). Det må siges at være den
myrealgoritme vi primært har ladet os inspirere af i dette projekt. De
anfører at i deres tests router den bedre end en række
standardrouting-algoritmer (bl.a. Bellman-Ford og OSPF) på et tungt
belastet netværk. Med "bedre" forstås her lavere pakkedød og hurtigere
sendetid for pakker.

Hele tricket skulle være at myrealgoritmer har en indbygget
adaptivitet i forhold til skiftende parametre for problemet de
forsøger at optimere en løsning til. Derfor interesserede vi os heller
ikke for specielt for statiske problemstillinger, men kastede os over
routing, der jo er et forbandet dynamisk problem. "forbandet", da
problemstillingen ikke bare er dynamisk i sig selv, men det kan
faktisk ændre på parametrene bare at forsøge at måle på situationen på
netværket (ved f.eks. at sende testpakker ud.)

Vores undersøgelser har været mere kvalitative i den forstand at vi
undersøgte hvilke makrofænomener vi rent faktisk kunne dreje
routing-algoritmen hen imod. Derfor lavede vi et
myre-routing-algoritme 'skelet', og implementerede en række
heuristikker (smarte tricks), som vi kunne skrue på via parametre.

Dermed blev det muligt at stille spørgsmål som: Kan vi få
routing-algoritmen (ARS) til at primært at route henover den korteste
vej? Kan vi få routing-algoritmen til at prioritere at pakkedød meget
sjældent skal ske? Etc. etc.

(Nu må jeg hellere forsøge at runde af) - Vi fandt, at det faktisk var
muligt at opnå disse effekter, og fik da også noget der lignede meget
fine routing-tider og lav pakkedød i forhold til en lille
'dæmon'-algoritme vi implementerede som en slags reference-ramme.
(Basalt set havde denne 'dæmon'-routing-algoritme et øjebliksbillede
af hele netværket i hvert klokke-tick.)

Men(!) - det var altså kun nogle få tests, primært på et simpelt 10x10
grid netværk med én sender og én modtager. Så der er ikke meget sjov i
det endnu. Men forhåbentlig får vi tid til at kigge lidt mere på det,
på et senere tidspunkt. Det kunne være sjovt at gå lidt videre med
det...

Hmmm, det blev vist lidt langt... Men sådan går det når man bliver
spurgt om noget som er spændende. Tak for tiden, hvis der var nogen
der gad at læse så langt

vh troels