Home

Geometrische Analyse und optimierte Kabelführung bei der

Contents

1. Die Punkte die bei der Implementierung m glichst ber cksichtigt werden sollten wurden bereits in der Analyse vorhandener Algorithmen auf Seite 7 n her erl u tert Als Eingabe erwartet der Algorithmus den Graphen im Algorithmus 3 mit der Menge V bezeichnet und den Weg der gefunden werden soll im Algorithmus 3 mit dem Starttripel s bezeichnet Da es im Allgemeinen wesentlich mehr Knoten als Kanten in einem Graphen gibt ist die Speicherung des Graphen als Matrix sehr ungeeignet wie die Matrix des Graphen Abbildung 11 auf Seite 19 zeigt 17 Switch Switch 2 Switch 3 Switch 4 Abbildung 9 Beispielnetzwerk Abbildung 8 auf Seite 17 als Graph HB e Switch 1 Abbildung 10 Zwei Graphen mit dem gleichen Sachverhalt dennoch sind sie un terschiedlich Die Wegstrecke in der linken Abbildung betr gt 5 92 m die in der Rechten 5 54 m 0 2 4 oo 00 Go 2 0 m m 00 00 Go 4 o 0 o 1 oo 00 D o 0 2 00 00 o 1 2 0 2 o oo 2 0 00 A 00 m o 0 Zum einen enth lt die Matrix sehr viele Eintr ge die mit dem oo Zeichen gef llt sind was bedeutet dass es zwischen diesen beiden Knoten keine Kante gibt Des Weiteren f llt auf dass die Matrix an der Hauptdiagonalen gespiegelt ist was dar an liegt dass es sich um einen ungerichteten Graphen handelt Wenn es eine Kante zwischen dem Knoten 1 und 2 gibt dann auch eine zwischen dem Knoten 2 und 1 Zwar wird der Speicheraufwand nur n
2. gend Raum f r Verbesserungen hinsichtlich des Ablaufs des Algorithmus und seiner Implementierung Aufgrund der mangelnden Zeit waren diese leider nicht zu reali sieren Denkbar w re auch ein Algorithmus der einen ganz anderen Ansatz verfolgt Seine Integration in das Programm sollte aufgrund der sehr flexiblen Schnittstelle keine gr eren Probleme bereiten Schlussendlich bleibt zu berlegen wie sinnvoll einer Verschmelzung der beiden Strukturen ndml_version_1 1 dtd und save_version_1 dtd und somit eine Integra tion der Kabekanalnetzdaten in die NDML Bescheibung sinnvoll ist Damit einher gehen w rde auch dass die Definition der save_ version 1 dtd in ein XML Schema berf hrt werden m sste Dies h tte zus tzlich den Vorteil dass sich die Typanga ben feiner spezifizieren lassen Auch sollte das Programm CaNDeL noch mehr in die CANDY Umgebung integriert werden was aufgrund der Zeit und des deshalb eher prototypischen Charakters des Programms nicht m glich war 30 Anhang Glossar Apache License Lizenzmodell f r freie Software 10 die von der Apache Group die unter anderem den Apache Webserver entwickelt haben entwickelt worden ist CaNDeL Cable Network Design TooL Der Name des Pro gramms welches im Rahmen dieser Belegarbeit entstan den ist CANDY Computer Aided Network Design Utilit Y Hierbei handelt es sich um ein Projekt zur Erstellung einer Soft ware im Umfeld der Netzwerkprojektierung 18 Designer Ist de
3. die zu einer L sung des Problems f hren k nnen 2 2 2 Dijkstra Algorithmus Der von Edsger Wybe Dijkstra entwickelte Algorithmus geh rt zu der Klasse der Greedy Algorithmen zu deutsch gierige Algorithmen Diese zeichnen sich dadurch aus dass sie immer den Folgezustand w hlen der zum jetzigen Zeitpunkt den gr ten Gewinn bzw das beste Ergebnis verspricht lokales Optimum Hieraus kann sich auch ein globales Optimum ergeben Oft wird diese Art von Algorithmen an gewendet um NP vollst ndige Probleme l sen zu k nnen Diese Berechnung f hrt dann zwar meist nicht zu einem optimalen Ergebnis aber zu einer sehr guten An n herung Im Falle des Dijkstra Algorithmus erh lt man ein optimales Ergebnis Der Algorithmus dient dazu in einem bewerteten ungerichteten bzw gerichteten Graphen alle k rzesten Wege von einem bestimmten Startknoten aus zu berech nen Allerdings darf die Bewertung der Kanten im Gegensatz zum Bellman Ford Algorithmus nicht negativ sein Der Dijkstra Algorithmus in Pseudocode ist auf Seite 9 zu finden Dabei ist die Menge V ist die Menge der Knoten E die Menge f r jedes ve V tue Distanz v oo Vorg nger v kein 0 Distanz s Vorg nger s U V M f r jedes s v E mit v U tue Distanz v Kosten s v LM MUv solange MA tue w hle u aus M mit Distanz u minimal M M u U U u f r jedes u v E mit v U tue M M U v wenn Distanz u Kosten u v lt Distanz v
4. Berechnung Zeigt das berechnete Ergebnis an Abbildung 27 Zuvor berechnetes Ergebnis nochmals anzeigen ber 1 S Eruck das Netewerk aus Abbildung 28 Graph ausdrucken XI
5. T lt technology gt lt nic gt lt nic id ni2 description home de2 gt lt l_nicType 1_wireless OFF _satelliteOriented OFF l_wired ON gt lt technology gt 100 Base T lt technology gt lt nic gt lt nics gt lt media gt lt medium id mel name UTP_CAT_5 length 100 0 gt lt connectedNic id nil gt lt connectedNic id ni2 gt lt medium gt lt media gt Listing 2 NDML Beschreibung eines Netzwerks mit zwei Rechnern 2 4 Gesetzliche Bestimmungen und Normen Zu diesem Bereich geh rt die graphische Darstellung von Netzwerkkabeln in einem Grundriss sowie die Verlegepl ne Aber auch etwaige Brandschutzbestimmungen die zum Beispiel die Art der Kabelf hrung in ffentlichen Geb uden regeln m ssen beachtet werden 2 4 1 Graphische Darstellung Bei der Recherche musste ich feststellen dass es anscheinend noch kein Symbol f r ein Netzwerkkabel in einem Grundriss nach derzeit g ltiger DIN gibt Stattdessen wird das Schaltzeichen f r Steckdosen verwendet und mit EDV beschriftet Abbil dung 6 auf Seite 14 20 Ebenso scheint es auch keine einheitliche Regelung zu geben wie man den Verlauf von Kabeln in einen Grundriss einzuzeichnen hat 2 4 2 Brandschutzbestimmungen Kabel auch Netzwerkkabel sollten und d rfen nicht beliebig verlegt werden Dies macht unter anderem das Auffinden von Kabeln in verputzten W nden viel einfa cher So stehen zum Beispiel viele Hobby Handwerker oft vor de
6. dass sie ein Elektroinstallateur lesen kann um mit Hilfe dessen die Kabel verlegen zu k nnen Aber auch die An passungsf higkeit des Programms an die eigenen Anforderungen spielt eine wichtige Rolle Die bisherige Beschreibung des Netzwerks durch die ndml_ version _1 1 dtd konnte nicht genutzt werden um das System der Kabelkan le zu erfassen da die Struktur daf r nicht ausgelegt ist So musste eine neue Struktur entwickelt werden die diese Aufgabe erf llen kann Die Datei save_ version_ 1 dtd ist ein Beispiel wie so etwas aussehen kann F r die Zukunft bleibt zu berlegen ob nicht die beiden Struktu ren zu einer zusammengef hrt werden sollten bzw die Kanalstruktur in die NDML aufgenommen werden soll siehe NDML Version 2 0 und 3 0 14 Dies h tte den Vorteil dass es keine zweigeteilte Datenhaltung mehr gibt und alle projektrelevan ten Informationen an einer zentralen Stelle gelagert werden Allerdings k nnte es auch zum Nachteil geraten wenn die anderen Programmteile nie auf diese Informa tionen zugreifen und sich dadurch die Struktur unn tigerweise aufbl ht Je nach Realisierung der Verschmelzung w ren keine oder nur sehr geringe Anpassungen in den brigen Programmteilen von CANDY notwendig und auch bei CaNDeL w ren 29 die Anpassungen schnell durchgef hrt Um den Code m glichst leicht wartbar zu gestalten sollte dieser gut strukturiert und kommentiert sein Deswegen gibt es f r jede Methode eine Erl uteru
7. noch kein PDF eingelesen worden ist wird man jetzt aufgefordert den Ma stab des Graphen anzugeben Anschlie end beginnt die Berechnung Ist diese Beendet so ffnet sich ein zweites Fenster in dem das Ergebnis in Form einer Tabelle dargstellt wird Abbildung 26 auf Seite XI F r jeden Weg der in der NDML Datei beschrieben ist wird ein k rzester Pfad durch den Graphen gesucht sofern die entsprechenden Ger te auch zugewiesen wor den sind Die erste beiden Spalten der Tabelle geben die Endpunkte des Weges wie der f r die der k rzeste Pfad berechnet werden sollte Die dritte Spalte enth lt die Knoten die man berqueren muss um den k rzesten Weg zu gehen oder eine ent sprechende Fehlermeldung wenn kein Pfad gefunden werden konnte entweder weil der Pfad zu lang ist oder weil es keine M glichkeit gibt die beiden Endpunkte zu verbinden Ist eine direkte Verbindung wie zwischen dem Server und dem Switch 5 Abbildung 26 auf Seite XT m glich so gibt es eine entsprechende Ausgabe Damit der Weg leicht nachvollzogen werden kann werden die zu durchquerenden Knoten mit einer entsprechenden Nummer versehen Um Absch tzen zu k nnen wie viel Reserve das Kabel noch bietet ist in der vierten und f nften Spalte aufgelistet wie lang das Kabel maximal sein darf und wie lang der berechnete Pfad ist ber den Button drucken kann man die Ergebnistabelle ausdrucken Der Button schlie en schlie t das Ergebnisfenster Um sich das Ergebnis z
8. 2 4 1 Graphische Darstellung o 2 4 2 Brandschutzbestimmungen 2 22 2 nenn Erstellung des Programms 3 1 Vorraussetz ngen 222 Ee ee re es 3 2 Nutzung des Grundriss oo 3 3 Erstellung des Kabelkanalnetzwerks 3 4 Optimale Wege berechnen nn 3 5 Erl uterung der Konfigurationsdatei o 2 22mm 3 6 Erl uterung des Speicherformats 2 22mm nun 3 7 Verwendete Frameworks 3 8 Die Programmstruktur Benutzerhandbuch 4 1 Start des Programms e esa sa ciac n nenn 4 2 Knoten einf gen ss saas a ee 4 3 Kanten einf gen nenn 4 4 Knoten losch l i 2 222 2 zweier e ER 4 5 PDF Datei einlesen 4 6 NDML einlesen und Ger te zuweisen 22 222m nn 4 7 Ger te und Beschriftungen einf gen nn 4 8 Berechnung der k rzesten Wege 2 2 o o al VO oo XA DO gt O I e Rp w oo qa e 14 14 16 16 17 21 22 23 23 4 9 Ausdr cken ari 4 4 4 t zi zer Ar Ar a rd A A 4 10 Das Meng x x 2 2 a a nn EEE E 4 11 Konfiguration von CaNDeL e 5 Res mee Anhang Glossar u 22 3822 A ar AAA E Bea e a Eiter t un sca m m mL Ed E ee nern Eigenst ndigkeitserkl rung e Tabellenverzeichnis 1 2 Verschiedene Kabeltypen und deren Maximall ngen 11 Farbzuordnung in der properties version_1l dtd 29 Abbildungsverzeichni
9. Belegarbeit mit dem Thema Geometrische Analyse und optimierte Kabelf hrung bei der Rechnernetze Projektierung Integration vorhandener Projektierungstools in die CANDY Umgebung Philipp B nisch Matr Nr 2839385 Fakult t Informatik TU Dresden 31 01 2006 Computer Aided Network Design UtilitY Zusammenfassung Dieser Beleg ist im Rahmen meiner Belegarbeit an dem Lehrstuhl f r Rechnernetze Fakult t Informatik an der TU Dresden unter der Betreuung von Dr rer nat D G tter und Dr Ing A Luntovskyy entstanden Ziel des Belegs ist es das an dem Lehrstuhl entwickelte Programm CANDY um eine weitere Komponente zu erweitern Diese soll die Aufgabe haben eine optimale Kabelf hrung in einem Netz aus Kabelkan len zu berechnen und auszugeben Technische Universit t Dresden Fakult t Informatik AUFGABENSTELLUNG F R DIE BELEGARBEIT Name Vorname B nisch Phillipp Studiengang Informatik Matr Nr 2839385 Email boenisch p web de Thema Geometrische Analyse und optimierte Kabelf hrung bei RN Projektierung Integration vorhandener Projektierungstools in die CANDY Umgebung Zielstellung F r die Projektierung von Rechnernetzen ist die Optimierung der Kabelf hrung mit Ber cksichtigung der Konzepte strukturierter Verkabelung der gro en Bedeutung F r das Terti rbereich der Verkabelung eines LANs sollte ein parametrisiertes 2D Modell entwickelt werden Die Arbeit muss Optimierungsaspekte bei Leitungsf h
10. Ethernet 5 Ethernet www koehler ks de Ethernet html 6 Extensible Markup Language http de wikipedia org wiki Xml 7 Optimalit tsprinzip von Bellman http de wikipedia org wiki Optimalit 8 Portable Document Format http de wikipedia org wiki Pdf 9 XML Schema Definition http de wikipedia org wi ki XSD 10 Apache Software Foundation Apache License Internet www apache org licenses LICENSE 2 0 11 Free Software Foundation General Public License In ternet www gnu org licenses gpl html 12 Free Software Foundation Lesser General Public Licen se Internet www gnu org copyleft lesser html 13 Clark Helwig M glichkeiten und Grenzen des vollautomatischen Entwurfs von Local Area Rechnernetzen Hauptseminar Fakult t In formatik TU Dresden 2004 www rn inf tu dresden de scripts 1srn Lehre candy vortraege Helwig Verkabelung pdf 14 Robert H nel Optimierung der Fachsprache NDML mit Abbildung in eine XML basierte Da tenbank Diplomarbeit Fakult t Informatik TU Dresden 2005 www rn inf tu dresden de scripts lsrn Lehre candy Haenel Diplomarbeit pdf 15 IDRsolutions JPedal Open Source Internet www jpedal org gpl html 16 Sun Microsystems Inc Java Software Internet www java com de 17 JDOM JDom Internet www jdom org 18 TU Dresden Lehrstuhl f r Rechnernetze Fakult t In formatik Computer Aided Network Design UtilitY www rn inf tu dres
11. Menge V gestrichen Des Weiteren spielt auch die Reihenfolge der zu ermittelnden Wege wie das Re s mee f r die Implementierung auf Seite 9 gezeigt hat eine wichtige Rolle Die implementierte Strategie f ngt mit der Leitung an die die geringste maximale Ka bell nge hat danach die n chst gr ere bis schlussendlich zur gr ten maximalen L nge Damit verfolgt die Strategie das Ziel die kritischsten Wege die mit der kleinsten Maximall nge zuerst zu finden und sich dann den weniger kritischen zu zuwenden Es sei aber darauf hingewiesen dass diese Strategie nicht immer zum Ziel f hren muss wie man sich an den Abbildungen 4 und 5 auf Seite 10 klarmachen kann Angenommen die maximale L nge des Weges C gt B liegt etwas ber die der durchgezogenen Linie von Abbildung 5 und die maximale L nge von A gt B ist etwas gr er als die Strecke von A gt B aber geringer als die L nge der gepunkteten Linie Der Algorithmus berechnet dann zun chst den Weg f r C gt B und ermittelt die gestrichelte Linie Wenn man jetzt annimmt dass die Kanten eine Kapazit t von eins haben dann l sst sich kein Weg mehr f r A gt B ermitteln Das Problem hat aber eine L sung wie man in der Abbildung 4 sehen kann Eine m gliche L sung dass A gt B den gepunkteten Weg nimmt und C gt B den gestrichelten 3 5 Erl uterung der Konfigurationsdatei Um das Programm m glichst flexibel zu halten bietet es diverse Einstellungsm g lichke
12. amit steht es aber im Widerspruch zu der Annahme dass A der k rzeste Weg war Der von Bellman und Lester Ford entwickelte Algorithmus hnelt sehr dem Floyed Warshall Algorithmus Beide dienen der Berechnung der k rzesten Wege in einem Graphen Der Bellman Ford Algorithmus in Pseudocode ist auf Seite 8 zu finden f r alle ve V tue Distanz v Vorg nger v kein Distanz s 0 wiederhole n 1 mal f r jedes u v E tue wenn Distanz u Gewicht u v lt Distanz v dann Distanz v Distanz u Gewicht u v Vorg nger v u f r jedes u v E tue wenn Distanz u Gewicht u v lt Distanz v dann STOP mit Ausgabe Zyklus negativer L nge gefunden Ausgabe Distanz Algorithmus 1 Bellman Ford Algorithmus 2 Die Menge V in dem skizzierten Bellman Ford Algorithmus enth lt die Knoten des Graphen E ist die Menge der Kanten die auch ungerichtet sein k nnen Gewicht ist die Gewichtsfunktion f r die Kanten Die Gewichtsfunktion kann auch negative Werte liefern s ist der Startknoten U ist die Menge der noch zu bearbeitenden Knoten und n die Anzahl der Knoten Kardinalit t von V Die Komplexit t des Algorithmus liegt bei O V E wobei V die Anzahl der Knoten und E die Anzahl der Kanten im Graphen ist Es sei auch noch auf die Arbeit 13 verwiesen in der sich auch schon n her mit der dynamischen Optimierung nach Bellman befasst worden ist und Ans tze geschildert werden
13. as Ergebnis einer Berechnung XI Zuvor berechnetes Ergebnis nochmals anzeigen XI Graph ausdrucken Coon nn XI Liste der Algorithmen 1 Bellman Ford Algorithmus 2 2 Common 8 2 Algorithmus von Dijkstra 9 3 Algorithmus zur Berechnung der optimalen Kabelf hrung 20 Listings 1 ndml version 1 1 dtd nommen 12 2 NDML Beschreibung eines Netzwerks mit zwei Rechnern 13 3 properties versionh_l dtd o o 21 d save version o dtd w a a rea u aa era 22 5 ISolver java el e id EE 24 6 IRet rnDataJjava 2222 2225 a Wen sd ae aat 25 To fIriplej vap sa aa O ii ias 26 1 Einf hrung CANDY ist ein Projekt des Lehrstuhls f r Rechnernetze unter der Leitung von Prof Dr habil A Schill an der Fakult t Informatik der TU Dresden zur Erstellung einer Software im Umfeld der Netzwerkprojektierung Ziel des Projektes ist es eine Arbeitsumgebung zu schaffen mit der man die Vernetzung in Neubauten von der Topologie ber die Kosten bis hin zur Leitungsf hrung ermitteln kann Weitere Informationen siehe 18 Im Rahmen dieser Belegarbeit sollte die CANDY Umgebung um eine weitere Funk tionalit t erg nzt werden Ziel war die Erstellung eines Programms mit dem man ein Netzwerk aus Kabelkan len erstellen kann und daf r die optimale Kabelf hrung ermittelt 1 1 Erl uterung der Aufgabenstellung Die erste Aufgabe bestand demnach darin sich mit vorhandenen Algorithmen zu besch ft
14. ch den Mauszeiger in die Zeichenfl che so ndert sich sein Aussehen und mit einem Links klick wird ein Knoten eingef gt Abbildung 15 auf Seite VIT Dieser wird automa tisch an dem Raster ausgerichtet Stellt man w hrend des Klicken fest dass man die falsche Position gew hlt hat so kann man bei noch gedr ckter linker Maustaste die Knoten verschieben 4 3 Kanten einf gen Mit einem Klick auf das Maussymbol Abbildung 16 auf Seite VII in der Symbol leiste kann man in den entsprechenden Modus wechseln Um die Kante zu zeichnen bewegt man die Maus ber einen Knoten Der Mauszeiger verwandelt sich in ein Handsymbol Zum Einf gen einer neuen Kante bewegt man mit gedr ckter linker Maustaste den Zeiger zum Zielknoten und l sst die Taste dort wieder los Dort die Maustaste wieder loslassen und die Kante wird eingef gt Abbildung 17 auf Seite VIII Knoten k nnen verschoben werden in dem man mit der Maus dar ber f hrt bis sich der Mauszeiger in ein Pfeilkreuz ndert Mit gedr ckter linker Maustaste den Knoten an die gew nschte Stelle ziehen und die Taste wieder loslassen Abbildung 18 auf Seite VIII Es k nnen auch mehrere Knoten gleichzeitig verschoben werden indem man meh rere Knoten selektiert und dann einen von ihnen verschiebt Mehrere Knoten kann man selektieren indem man mit der Maus an eine beliebige Stelle klickt und mit gedr ckter linker Maustaste einen Kasten aufzieht Abbildung 19 auf Seite VIII 25 publ
15. dann Distanz v Distanz u Kosten u v Vorg nger v u begin Ausgabe Distanz und Vorg nger Algorithmus 2 Algorithmus von Dijkstra 1 der Kanten Kosten die Gewichtsfunktion f r die Kanten s der Startknoten und U die Menge der noch zu bearbeitenden Knoten Nach dem Durchlauf des Algorithmus muss allerdings noch ein zweiter Algorithmus gestartet werden der aus dem Vorg nger den minimalen Spannbaum entspricht den k rzesten Wegen ermittelt Dies stellt kein gro es Problem mehr dar und soll an dieser Stelle vernachl ssigt werden Die Komplexit t des Dijkstra Algorithmus liegt bei O n wobei n die Anzahl der Knoten ist Durch die Verwendung eines Fibonacci Heap anstelle einer Knotenliste betr gt die Laufzeit nur noch O m n log n wobei m die Anzahl der Kanten ist 2 2 3 Res mee f r die Implementierung Die beiden betrachteten Algorithmen sind f r die L sung des vorliegenden Problems nur bedingt geeignet Beide Verfahren nutzen als Kriterium f r die Wahl des k r zesten Weges die Gewichtsfunktion also die Kosten die es verursacht wenn man eine Kante nutzt Diese Kosten kann man mit den L ngen der Kanten gleichsetzen Nach dem Durchlauf der Algorithmen sind die kosteng nstigsten Wege in einem Graphen ermittelt worden also in diesem Fall die Wege mit der geringsten L nge Dies ist aber f r das gegebene Problem nicht ausreichend Ein wichtiges Kriterium bei der Wegewabhl ist auch n
16. den unter der Beriicksichtigung dass die Kanten nur eine begrenzte Kapazit t haben einen gro en Einfluss auf die ermittelten k rzesten Wege hat W re zuerst der Weg C gt B berechnet worden und anschlie end der Weg A gt B h tte sich ein ganz anderes Ergebnis ergeben wie man anhand der Abbildung 5 auf Seite 10 sehen kann Die Kapazit t der Kan le ist wieder eins Der 2 e s D e u e e e o SH rn am mm TN m mm dl Cl meet mmm mm Abbildung 5 Ermittelte k rzeste Wege C gt B und A gt B 10 Weg C gt B ist zwar jetzt etwas k rzer gegen ber dem gestrichelten Weg aus der Abbildung 4 daf r ist der Weg A gt B wesentlich l nger geworden Des Weiteren beachten die Algorithmen nicht dass die einzelnen k rzesten Wege bestimmte L ngen nicht berschreiten d rfen da sonst die maximalen L ngen der verschiedenen Netzwerkkabeltypen berschritten werden k nnten Wie man anhand Kabeltyp Standard L nge RG58 Kabel 10Base2 185 m RG8 Kabel 10Base5 500 m CAT 3 Kabel 10Base T 100 m CAT 5 Kabel 10Base T 100 m 100Base T 100 m Multimode Glasfaser 1000Base SX 550 m 10GBase SR 82 m 10GBase LX4 300 m 1000Base SX 2 000 m 1000Base LX 10 000 m 10GBase LX4 10 000 m 10GBase ER 40 000 m Singlemode Glasfaser Monomodeglasfaser 1000Base LX 10 000 m STP 1000Base CX 25 m Doppelt twinaxiale Kupferkabel 10GBase T 100 m Tabelle 1 Verschiedene Kabelt
17. den de scripts 1srn Lehre candy 19 JGraph Ltd JGraph Internet www jgraph com 20 Klaus J rgen Schneider Bautabellen f r Architekten Werner Verlag Neuwied 16 edition August 2004 II 21 unitherm Gesetzliche Grundlagen Internet www unitherm online de wisspool gesetze index php 22 Prof H Vogler Algorithmen Datenstrukturen und Programmierung vorlesungsmaterial Graphalgorithmen page 141ff September 2005 www orchid inf tu dresden de gdp lehre IV Eigenst ndigkeitserkl rung Hiermit erkl re ich Philipp B nisch dass ich die vorliegen de Arbeit selbstst ndig verfasst keine anderen als die ange gebenen Hilfsmittel verwendet und die Stellen die anderen Werken dem Wortlaut nach entnommen sind mit Quellenan gaben kenntlich gemacht habe Philipp B nisch Dresden den 31 Januar 2006 properties networkData DataManager SCH startet Miete SimpleSolver ReturnData NumberTextField Triple ExtendedFilechooser Returnblata 5caleDialog Triplelmpl ResolutionDialog graphComponents ExtendedRealEditor beinhaltet ExtendedgraphcellEditor Ze LinkCellMouseAdapter ExtendedJ raph ExtendedMarqueeHandier ExtendedGraphlayoutlache ExtendedEdge ExtendedGraphlll LinkCell LinkGeliew ExtendedgEdgewiew ExtendedPortiew ExtendedviewFacton Abbildung 12 Paketstruktur des Programms VI Datei Bearbeiten Ansicht Favoriten Ex
18. derungen geht und somit der Informationsgehalt in etwa gleich geblieben ist basiert diese 1Dient lediglich als Richtwert H ngt stark von den eingesetzten Technologien wie Hubs oder Switches ab Bezeichnet die Gesamtkabell nge oder die L nge des Kabel zwischen zwei Stationen 11 Arbeit dennoch auf der NDML Version 1 1 Dies f hrt auch dazu das eigene XML Definitionen durch eine DTD beschrieben werden und nicht wie bei den neueren NDML Varianten durch ein XML Schema Allerdings sind die DTD leicht in das XML Schema berf hrbar so dass an dieser Stelle kein gro er Nachteil entsteht Die f r dieses Programm wichtigsten Definitionen der NDML Version 1 1 kann man dem Listing 1 auf Seite 12 entnehmen Es werden Ger te device definiert Diese lt ELEMENT devices devicex gt lt ELEMENT device 1_agentx gt lt ATTLIST device id ID REQUIRED gt lt ELEMENT nics nicx gt lt ELEMENT nic l_nicType technology gt lt ATTLIST nic id ID REQUIRED home IDREF REQUIRED gt lt ELEMENT media mediumx gt lt ELEMENT medium connectedNic gt lt ATTLIST medium id ID REQUIRED length CDATA IMPLIED gt lt ELEMENT connectedNic EMPTY gt lt ATTLIST connectedNic id IDREF REQUIRED gt Listing 1 ndml_version_1 1 dtd stellen die einzelnen Rechner Switches usw des Netzwerks dar Neben anderen Eigenschaften m ssen die Ger te jeweils eine feste ID haben Ihnen lassen sich Schnittstelle
19. dgesWanted 23 public interface ISolver public final static int TO LONG_ERROR 1 public final static int NO WAY ERROR 2 public final static int NO ERROR 1 Berechnet die kuerzesten Wege in einem Graphen param graph Graph in dem die kuerzesten Wege berechnet werden sollen param edgesWanted Wege fr die der kuerzeste Verlauf ermittelt werden soll param edgesCapacity Die einzelnen Kapazitaeten der Kanten a A XA XA ZS return Liste der ermittelten kuerzesten Wege public List lt IReturnData gt solveTheProblem Object graph Object edgesWanted Object edgesCapacity Listing 5 ISolver java Object edgesCount sehr allgemein gehalten Es wird lediglich festgelegt dass der Methode der Graph die gesuchten Wege und die Kapazit ten der Kanten bergeben werden m ssen Die Art und Weise wie dies geschieht bleibt dem Programmierer vorbehalten Implementiert wurde eine Variante in Anlehnung an Optimale Wege berechnen auf Seite 17 Die Tripel werden in ITriple definiert Die R ckgabe der berechneten Wege erfolgt ber die Struktur IReturnData Das Paket graphComponents enth lt nur Klassen die von dem Framework JGraph erben und an die Bed rfnisse des Programms angepasst sind Als Unterpakete ent h lt es noch die Pakete handler und views 4 Benutzerhandbuch Dieser Abschnitt erl utert wie man das Programm CaNDeL starten und nutzen kann Im Unterordner data befinden sich unt
20. er anderem drei Beispieldateien Die Datei Netzwerk uml ist eine NDML Beschreibung eines Netzwerks mit einem Server und f nf Switches Die Datei Beispiel cml enth lt einen Beispielgraphen und die Datei Grundriss pdf enth lt ein Beispiel f r einen Grundriss 4 1 Start des Programms ffnet man den Ordner vom Programm CaNDeL Abbildung 13 auf Seite VII so enth lt dieser drei Eintr ge Der Ordner pics enth lt Graphiken die vom Programm selbst genutzt werden Der Ordner data ist das Arbeitsverzeichnis des Programms und die JAR Datei das eigentliche Programm Zum Starten des Programms reicht h ufig ein Doppelklick auf die Datei aus vorausgesetzt dass Java mindestens in der Version 1 5 installiert ist Falls nicht so kann man es unter 16 herunterladen 24 public interface IReturnData IER Liste von ITriples die die durchlaufenen Kanten enthalten public List getList IER Laenge des berechneten Wegs public double getLength EE Fehlercode der waehrend der Berechnung aufgetreten ist see ISolverfNO_ERROR see ISolverfNO_WAY ERROR see 1Solver IO_LONG_ERROR public int getErrorCode IER Das ITriple beinhaltet den Weg der berechnet werden sollte public ITriple getTriple Listing 6 IReturnData java 4 2 Knoten einf gen Die Knoten des Graphen kann man platzieren indem man in der Symbolleiste auf das Knotensymbol Abbildung 14 auf Seite VII klickt F hrt man dana
21. erden und sich den baulichen Gegebenheiten des Geb u des anpassen Abbildung 2 auf Seite 7 Auch muss ber cksichtigt werden dass die Kan le nicht nur waagerecht verbaut werden um eine Etage zu versorgen sondern auch senkrecht um bspw mehrere Etagen zu verbinden oder um den WLAN Router unter der Decke anschlie en zu k nnen Abbildung 2 Richtungs nderung Abbildung 3 Aufsplittung 2 2 Analyse vorhandener Algorithmen 2 2 1 Bellman Ford Algorithmus W hrend meiner Vorbereitung habe ich mich n her mit dem Bellman Ford Algo rithmus besch ftigt Dieser geh rt der Gruppe der dynamischen Algorithmen an Das Konzept der dynamischen Algorithmen bzw Programmierung ist vornehmlich von Herrn Bellman einem amerikanischen Mathematiker in den 1940er Jahren entwickelt worden Es geht davon aus dass sich einige Optimierungsprobleme in kleinere Teilprobleme aufteilen lassen Die Optimall sung dieser Teilprobleme ergibt die Optimall sung des Gesamtproblems Optimalit tsprinzip von Bellmann 7 Ein Beispiel hierf r ist die Berechnung der k rzesten Wege in einem Graphen Es gibt einen k rzesten Weg A in einem Graphen zwischen den Knoten X und Y Zus tzlich f hrt der Weg A auch ber die Knoten U und V Nach dem Optimalit tsprinzip muss dann auch der Weg zwischen U und V optimal d h so kurz wie m glich sein Wenn das nicht der Fall w re dann k nnte man den Weg A verk rzen in dem man einen k rzeren Weg zwischen U und V w hlt D
22. eren Kan len die untereinander verbunden sind Dabei kann es auch zu Abzweigungen Kreuzungen und Richtungs nderungen kom men An den Enden der Kan le treten die Kabel aus diesen aus und werden mit den entsprechenden Ger ten verbunden so wie es in der Abbildung 8 auf Seite 17 dargestellt ist Dieser Sachverhalt l sst sich gut mit einem ungerichteten Graphen wiedergeben Die einzelnen Kanten des Graphen stellen die Kan le dar die Ecken des Graphen zuk nftig Knoten genannt k nnen dazu genutzt werden Kreuzun gen abzubilden Richtungs nderungen vorzunehmen oder Endpunkte zu markieren Abbildung 9 auf Seite 18 Die Endpunkte k nnen mit den Ger tebezeichnungen beschriftet werden die dort aufgestellt werden sollen Diese k nnen der NDML Beschreibung des Netzwerks entnommen werden siehe Analyse der NDML auf Seite 11 Bei den Kanten m ssen zwei Dinge beachtet werden Zum einen muss man eine M glichkeit haben deren L nge angeben zu k nnen um berechnen zu k nnen wie lang die gesamte Wegstrecke ist Zum Anderen muss man die Kapazit t der einzel nen Kan le angeben k nnen d h wie viele Kabel eine Kanal aufnehmen kann Da der Designer eine PDF Datei mit dem Grundriss einlesen kann und diese im Hin tergrund der Zeichenfl che dargestellt wird bietet es sich an die L nge der Kan le implizit aus der L nge der Kanten auszulesen Dies hat die Vorteile dass der Desi gner das Netzwerk ma stabsgetreu erstellen und an dem Grund
23. eser Eintrag 2Cable Network Design TooL 22 e startNode ist der Startknoten der Kante e endNode ist der Zielknoten der Kante e label ist die Kapazit t der Kante sofern sie von der Standardkapazit t ab weicht 3 7 Verwendete Frameworks Neben der Berechnung der k rzesten Wege muss das Programm noch weitere Funk tionen bieten Es m ssen PDF Dateien dargestellt XML Dateien eingelesen und Graphen gezeichnet werden Recherchen haben ergeben dass bereits viele Frame works existieren die diese gew nschten Aufgaben erf llen F r die Darstellung der PDF Dateien habe ich mich f r das Framework JPedal entschieden 15 welches in zwei Varianten erh ltlich ist Es gibt eine kommerzi elle Version und eine freie Version die unter der GPL Lizenz 11 steht Diese ist zwar etwas lter als die kommerzielle Version aber f r die Zwecke des Programms vollkommen ausreichend F r die Erstellung des Graphen habe ich das Framework JGraph 19 gew hlt Auch dieses Framework liegt sowohl als kommerzielle Variante als auch als freie Variante die unter der LGPL 12 steht vor JGraph stellt unter anderem alle Funktionen zur Verf gung die zur komfortablen Erstellung und Editierung eines Graphen notwendig sind Um XML Dateien einfach einlesen und schreiben zu k nnen kommt das Framework JDom 17 zum Einsatz Dieses liegt unter der Apache License 10 die vergleichbar mit der LGPL ist Es ist recht einfach in der Handhabung und kann z
24. ic interface ITriple extends Comparable Cloneable IER Ermittelt ob zwei Tripel gleich sind Da es sich bei dem Graphen der Kabelkanaele um einen ungerichteten Graphen x handelt spielt es keine Rolle ob man Startknoten Zielknoten Kosten oder Zielknoten Startknoten Kosten schreibt Deshalb werden diese beiden Tripel als gleich angesehen param obj Das Triple mit dem verglichen werden soll x Qreturn true wenn gilt Triplel xl yl zl und Triple2 x2 y2 z2 mit xl x2 und yl y2 oder xl y2 und yl x2 ansonsten false public boolean equals Object obj public Object getSource public Object getTarget public double getCost public void setSource Object source public void setTarget Object target public void setCost double i public ITriple clone Listing 7 ITriple java 4 4 Knoten l schen Es k nnen jederzeit selektierte Knoten durch Driicken der Entf Taste gel scht wer den Wenn dieser Knoten bereits mit Kanten verbunden war so werden diese eben falls gel scht 45 PDF Datei einlesen Eine PDF Datei kann man einlesen indem man in der Symbolleiste auf das PDF Icon klickt Abbildung 20 auf Seite VIII Daraufhin ffnet sich ein Fenster in dem man die gew nschte PDF Datei ausw hlen kann Hat man die gew nschte Datei gefunden wird man dazu aufgefordert den Ma stab des Grundrisses einzugeben Abbildung 21 auf Seite IX damit die L nge
25. igen und diese zu analysieren und zu testen ob sie f r diese Aufgabenstel lung geeignet sind Zu diesem Zweck habe ich mich n her mit dem Bellman Ford Algorithmus und dem Dijkstra Algorithmus auseinander gesetzt Des Weiteren galt es sich mit den gesetzlichen Bestimmungen und den g ltigen DIN Normen zu be sch ftigen um diese bei der Implementierung zu ber cksichtigen Zus tzlich musste noch eine passende Repr sentation der Realit t sprich dem Grundriss mit seinen Kabelkan len gefunden werden um diese m glichst einfach und intuitiv zu gestal ten so dass sich der Benutzer des Programms schnell zurecht finden kann ohne vorher lange die Anleitung studiert zu haben Letztendlich musste das entstandene Programm nat rlich auch noch ausgiebig getestet werden 2 Vorarbeit Bevor das Programm realisiert werden konnte mussten einige Nachforschungen an gestellt werden So wird ein Algorithmus ben tigt der den optimalen Kabelverlauf berechnet Dazu galt es eine geeignete Repr sentation des Sachverhalts ein Grund riss mit eingezeichneten Kabelkan len zu finden um berhaupt einen Algorithmus anwenden zu k nnen Schlie lich mussten die Algorithmen selbst auf ihre Taug lichkeit gepr ft werden Des Weiteren soll das Programm auf den Ergebnissen der vorherigen CANDY Programmstufen aufbauen Arbeitsgrundlage f r diese ist eine NDML Datei eine CANDY eigene XML Spezifikation die alle wichtigen Daten des Netzwerks enth lt Um diese ver
26. iten an die besonders die Erstellung des Graphen betreffen Da aber die Stan dardeinstellungen f r 99 der F lle ausreichend sind und somit nderungen nur sehr selten vonn ten sind k nnen diese nicht direkt im Programm manipuliert wer den Stattdessen gibt es eine zentrale Datei namens Einstellungen xml die alle Parameter beinhaltet nderungen in dieser Datei werden dann bei einem Neu start des Programms bernommen Definiert wird die Datei durch die DTD pro perties_ version_ 1 dtd siehe Listing 3 auf Seite 21 Die Bedeutung der einzelnen lt ELEMENT properties EMPTY gt lt ATTLIST properties std_color 0 1 2 3 4 5 6 7 8 9 10 11 12 REQUIRED label_color 0 1 2 12 REQUIRED selec_color 0 1 2 3 4 5 6 7 8 09 10 11 12 REQUIRED std_ capacity CDATA REQUIRED std length CDATA REQUIRED cell_ size CDATA REQUIRED grid_gap CDATA REQUIRED port_ size CDATA REQUIRED edge_ width CDATA REQUIRED 3 4 5 6 7 8 9 10 11 Listing 3 properties _ version _1 dtd 21 Parameter k nnen dem Benutzerhandbuch unter Konfiguration von CaNDeL auf Seite 28 entnommen werden 3 6 Erl uterung des Speicherformats Um dem Programm die M glichkeit des Speichern und Ladens zu geben bedarf es eines geeigneten Formats welches alle notwendigen Daten aufnehmen kann um dar aus zu einem sp teren Zeitpunkt den Graphen rekonstruieren zu k nnen Es muss die Position der einzelnen Knoten gesicher
27. l angepasst werden Ein weiteres Problem der NDML Beschreibung ist dass die Schnittstellen zwar ein Attribut technology siehe Analyse der NDML auf Seite 11 besitzt allerdings ist dieses vom Typ PCDATA und kann somit alle m glichen Zeichensequenzen beinhal ten Um das Feld f r die Auswertung nutzen zu k nnen m sste es eine Definition geben welche Zeichenketten zul ssig sind und was diese genau bezeichnen Aller dings w rde diese Information alleine nicht ausreichen um zu ermitteln wie Lang ein Kabel maximal sein darf Wie sich im Res mee f r die Implementierung auf Seite 9 gezeigt hat bt auch die Wahl des Kabels eine gro e Rolle auf die maxi male L nge aus Um diesen Problem aus dem Weg zu gehen wird stattdessen das Attribut length des mediums ausgewertet Es wird davon ausgegangen dass dies die maximale L nge des Kabels zwischen zwei Ger ten ist Da das Attribut nur optional ist wird bei dem Fehlen dieser Angabe von einer maximalen L nge von 100 Metern ausgegangen Da das Programm nur die optimale Verlegung von Netzwerkabeln berechnen soll werden nur Leitungen mit in die Berechnung einbezogen bei denen das Attribut I_nicType in nic in der NDML Bescheibung wie folgt gesetzt ist e 1_wireless OFF e 1_satellite0riented OFF e 1_wired ON Zus tzlich m ssen die einzelnen Leitungen mindestens zwei connectedNic besitzen Da im Allgemeinen ein Kabel nur zwei Enden hat werde
28. m Problem ob sie an der gew nschten Stelle ein Loch bohren k nnen oder nicht weil sich in der N her eine Steckdose befindet Wenn sich der Elektriker an die Richtlinien gehalten hat dann l sst sich das Problem sehr leicht aus der Welt schaffen Die Kabel sollten von der Stelle ihres Austretens senkrecht nach unten fiihren und erst knapp ber dem Fu boden horizontal weiter gef hrt werden 13 EDV ANA Abbildung 6 Schaltzeichen f r eine Steckdose nach DIN 40900 mit zus tzlicher Beschriftung Neben dieser Vereinfachung gibt es noch viele weitere Bestimmungen bspw um die Brandgefahr im Kurzschlussfall so gering wie m glich zu halten Erw hnt seien hier unter anderem das Bauproduktgesetz der EG vom 10 08 1992 das EG Grund lagendokument 2 Brandschutz 02 94 die Musterbauverordnungen die Landesbau ordnungen die Sonderbauten Richtlinien und etwaige Genehmigungen im Einzelfall 21 3 Erstellung des Programms Aus den vorausgegangenen Vor berlegungen muss eine Vorgehensweise abgeleitet werden wie das Programm entwickelt werden soll Zudem m ssen die Ziele definiert und m gliche Einschr nkungen vorgenommen werden um das Programm realisieren zu k nnen 3 1 Vorraussetzungen Unter der Rubrik Gesetzliche Bestimmungen und Normen auf Seite 13 wurde be reits die gesetzliche Sachlage etwas hinterleuchtet Die richtige Kabelverlegung wird von vielen Einflussfaktoren bestimmt Es kommt auf die Beschaffe
29. mm nutzt einige Features wie erweiterte for Schleifen und generische Datentypen die erst mit der neuen Version 1 5 von Java eingef hrt worden sind Um das Programm ausf hren zu k nnen wird deshalb Java in der Version 1 5 ben tigt 3 2 Nutzung des Grundriss Aus den Betrachtungen unter Der Grundriss auf Seite 6 liegt es nahe das Ka belkanalnetzwerk digital und nicht per Hand zu erstellen So kann das Programm relativ einfach gehalten werden und es entf llt das Durchsuchen des gescannten Grundriss nach den Kan len Um dem Designer das Erstellen des Kanalnetzwerks zu erleichtern bietet es sich an den Grundriss in den Hintergrund der Zeichenfl che zu legen F r diese Zwecke eignet sich das PDF Format sehr gut Es ist genauso wie das Programm selbst welches in Java realisiert ist plattform und systemunab h ngig Auch ist die Erzeugung einer PDF Datei relativ einfach Viele Programme bieten von sich aus schon einen PDF Export an Ist diese M glichkeit nicht gege ben so kann man eine PDF Datei erzeugen indem die Datei auf einem virtuellen Drucker ausgedruckt wird der dann aus den Druckdaten eine PDF Datei erzeugt 3 3 Erstellung des Kabelkanalnetzwerks Aus den unter Analyse der Realit t auf Seite 6 genannten Gr nden und der Ent scheidung im vorangegangenen Abschnitt muss das Programm eine M glichkeit bie ten dass der Nutzer ein Kabelkanalnetzwerk erstellen kann Ein solches Netzwerk besteht aus im Allgemeinen mehr
30. n nic zuweisen home Diese stellen die einzelnen Buchsen dar in die man die Netzwerkkabel hineinstecken kann Untereinander verbunden werden die Schnittstellen ber Leitungen medium wobei unter Leitungen nicht nur Kabel sondern auch kabellose Medien wie Satelliten bertragung und WLAN zu verstehen sind Eine NDML Beschreibung f r ein Netzwerk mit zwei Rechnern die direkt mitein ander verbunden sind k nnte so aussehen wie es auf Seite 13 dargestellt ist F r das Programm muss also eine geeignete Struktur gefunden werden um den Sachverhalt der NDML Datei auf den schon mehrfach erw hnten Graphen zu ber tragen Es muss ermittelt werden welche Ger te untereinander verbunden werden sollen Dazu ist es notwendig die Liste der Leitungen durchzugehen um festzustel len welche Schnittstellen miteinander verbunden werden sollen Um die Usability des Programms zu erh hen w re es sch n wenn der Nutzer zus tzlich noch die Information bekommt welche Schnittstelle zu welchem Ger t geh rt da ihm so die Zuordnung wesentlich erleichtert wird 12 dontprintsemicolon lt devices gt lt device id del name Rechner_1 description Dies_ist_der_Rechner_1 gt lt device id de2 name Rechner_2 description Dies_ist_der_Rechner_2 gt lt devices gt lt nics gt lt nic id nil description home del gt lt l_nicType l_wireless OFF _satelliteOriented OFF l_wired ON gt lt technology gt 100 Base
31. n bei mehr als zwei einge tragenen connectedNics nur die ersten beiden Eintr ge ausgewertet Der einfachheit halber arbeitet das Programm nur im zwei dimensionalen Raum Das hei t wenn eine Berechnung f r eine waagerechte Verkabelung gestartet wird so k nnen senkrechte Kabelkan le nicht ber cksichtigt werden und umgekehrt Um dies dennoch bei der Planung ber cksichtigen zu k nnen berechnet das Programm nicht nur die L nge des Kanals und gibt diese aus sondern es wird auch die ma ximale L nge des Kabels ausgegeben Abbildung 7 auf Seite 15 welches in diesen Kanal gelegt werden soll So kann man einfach eine Absch tzung machen wie viel Reserve das Kabel noch bietet und anhand dessen absch tzen ob eine senkrechte Weiterf hrung noch m glich ist max L nge ermittelte L nge 10 00 m 2 67 m 94 00 m 5 84 m 100 00 m 6 14 m 110 00 m 1 000 00 m 4 50 m x Abbildung 7 Ausgabe der berechneten L nge und der Maximall nge Unter Erstellung des Kabelkanalnetzwerks auf Seite 16 wird erl utert dass die L nge der Kan le aus den L ngen der Kanten ermittelt werden Damit die Umrech 15 nung der L ngen der graphischen Darstellung in metrische Ma e korrekt durchge f hrt wird muss der Monitor mit einer Aufl sung von 72 DPI arbeiten Im Normal fall stellt dies keine Einschr nkung der Nutzung des Programms dar da die meisten handels blichen Monitore in dieser Aufl sung arbeiten Das Progra
32. n berechnet werden bis man den Zielknoten erreicht hat Im schlimmsten Fall ist dies der Knoten der am weitesten vom Startknoten entfernt ist und somit derjenige der zuletzt gefunden wird Im Anschluss muss noch der richtige Weg ermittelt werden der zum eigentlichen Ziel f hrt Dabei wird gleich eine Fehleranalyse gestartet Wenn ein Weg gefunden worden ist so wird dieser zur ckgegeben Wenn der gefundene Weg l nger ist als die maximal erlaubte L nge so kommt es zu einer Fehlermeldung Es kann aber auch passieren dass kein Weg gefunden wird weil es sich um keinen zusammenh ngenden Graphen handelt In diesem Fall gibt der Algorithmus eine entsprechende Fehlermeldung zur ck Die Funktion minimum ermittelt von einer Menge aus Tripeln dasjenige Tripel welches die geringsten Kosten hat Es muss beachtet werden dass die Reihenfolge in S eine wichtige Rolle spielt da diese die Reihenfolge der zu durchlaufenden Knoten wiedergibt In der vorliegenden Form ber cksichtigt der Algorithmus der Einfachheit halber allerdings nicht dass jedes Tripel doppelt vorkommt siehe Res mee f r die Implementierung auf Seite 9 Eingabe Starttripel s Menge aller Kanten V Ergebnis Berechneter k rzester Weg S Daten int l nge Tripel such Tripelmenge D Tripelliste S Initialisierung der Daten l nge 0 such s start s start 0 Alle vom Startknoten aus erreichbaren Knoten ermitteln f r alle ve V tue wenn s von v von da
33. n der Kanten richtig berechnet werden k nnen Anschlie end wird die Datei in den Hintergrund gezeichnet 4 6 NDML einlesen und Ger te zuweisen Eine NDML Datei kann man einlesen indem man auf das NDML Symbol in der Symbolleiste klickt Abbildung 22 auf Seite IX Daraufhin ffnet sich ein Fenster in dem man die gew nschte NDML Datei ausw hlen kann Danach stehen die Daten der NDML Datei im Programm zur Verf gung 26 4 7 Ger te und Beschriftungen einf gen Standardm ig haben die Kan le eine Kapazit t von f nf Soll diese individuell ge ndert werden so kann man die Kapazit t einer Kante ndern indem man auf diese doppelklickt und die gew nschte Kapazit t eintr gt Abbildung 23 auf Seite IX Die Eingabe mit Enter best tigt Den einzelnen Knoten kann man diejenigen Ger te zuweisen die in der NDML de finiert sind Dazu muss als erstes eine NDML Datei eingelesen werden Danach ein fach auf einen Knoten doppelklicken und in der sich ffnenden Liste das gew nschte Ger t ausw hlen Die Beschriftung wird daraufhin in den Graphen eingef gt und das Symbol ndert sich zu einem Viereck Abbildung 24 auf Seite X Die Zuwei sung kann jederzeit wieder entfernt werden in dem man den Eintrag Zuweisung entfernen in der Liste ausw hlt 4 8 Berechnung der k rzesten Wege Um die Berechnung der k rzesten Wege zu starten muss man auf das Rechensymbol in der Symbolleiste klicken Abbildung 25 auf Seite X Falls zuvor
34. n verschiedensten Ausf hrungen wie das Bild auf Seite 7 zeigt Es gibt offene Kan le geschlossene Kan le Unterputz Kan le Aufputz Kan le eckige Kan le runde Kan le Kan le aus Kunststoff Kan le aus Metall nur um ein paar Beispiele zu nennen Im Hausgebrauch werden sie meist genutzt um bspw die Zuleitung f r den Fernseher zu verstecken oder den Kabelsalat hinter dem PC etwas zu ordnen Man kann sie aber auch geb udeweit einsetzen und alle Leitungen des Geb udes in Kan len verlegen Dies hat den Vorteil dass man genau wei wo die Leitungen verlaufen und diese zus tzlich gesch tzt sind Des Weite ren kommt man im Bedarfsfall relativ schnell an sie heran wenn zum Beispiel ein Kabel defekt ist oder die Netzwerktechnik gewechselt wird und alle Netzwerkkabel ausgetauscht werden m ssen Auch ist es bei ausreichender Gr e der Kan le kein Problem nachtr glich noch weitere Kabel zu verlegen wenn dies n tig wird Aufgabe des Designers ist es sich Gedanken um den Verlauf der Kan le zu machen und diese richtig zu dimensionieren um die Wartungskosten des Kabelnetzwerks so gering wie m glich zu halten Diese Kosten k nnen zum Beispiel die Behebung von Abbildung 1 Kabelkan le in verschiedenen Ausf hrungen Fehlern im Leitungssystem sein der Austausch von Leitungen oder das Verlegen zus tzlicher Leitungen Selbstverst ndlich k nnen sich die Kan le auch aufsplitten bzw zusammengef hrt Abbildung 3 auf Seite 7 w
35. nen W nschen editieren Die verschiedenen Parameter im einzelnen e std_ color legt die Farbe fest in der die Knoten und Kanten gezeichnet werden e label_ color legt die Farbe fest in der die Beschriftungen der Knoten und Kanten geschrieben werden e selec_ color bestimmt die Farbe wenn Knoten und oder Kanten selektiert werden Die etwaigen zugeh rigen Beschriftungen nehmen ebenso diese Farbe an e std_ capacity legt fest wie gro die Standardkapazit t der Kan le sein soll wenn diese nicht explizit angeben wird e std_length legt fest wie lang die maximale L nge einer Leitung ist wenn das optionale Attribut length in der NDML Beschreibung des Netzwerks nicht gesetzt ist e cell_size bestimmt die Gr e der einzelnen Knoten e grid_ gap definiert den Abstand der einzelnen Grid Punkte e port_ size legt die Gr e der Ports der Knoten fest Dieser Wert sollte immer kleiner als cell_ size sein e edge_width gibt die Breite der Kanten vor Die Farben der ersten drei Parameter werden mittels Zahlen angegeben wie sie in der Tabelle 2 auf Seite 29 angegeben sind 5 Res mee Die Aufgabe dieser Belegarbeit bestand darin ein Programm zu schreiben wel ches eine optimale Verlegung von Leitungen in einem System aus Kabelkan len berechnet Dazu mussten in der k rze der Zeit m gliche technische Realisierungen ausgelotet und die am Erfolg versprechenste implementiert werden Entstanden ist 28 Wert Farbe schwarz blau ro
36. ng in der zugeh rigen JavaDoc Falls diese nicht ausreichend ist befinden sich auch noch viele Kommentare im Code selbst in denen n her auf implementierungsspezifische Aspekte eingegangen wird In diesem Beleg wurde die Entwicklung des Programms CaNDeL erl utert mit des sen Hilfe man ein System aus Kabelkan len erstellen und anschlie end die optimalen Wege berechnen lassen kann Allerdings ist der Begriff optimal in diesem Zusam menhang ein schwieriger Begriff ist Ein Weg in einem Graphen ist optimal wenn dieser die k rzeste Verbindung zwischen zwei Knoten darstellt So stellt sich nun die Frage wann zwei oder mehr Wege in einem Graphen optimal sind Wenn der eine kurz ist und der andere Weg daf r l nger ist oder wenn beide Wege ann hernd gleich lang sind In CaNDeL ist das Problem derart gel st dass zuerst der Weg f r die Leitung berechnet wird welche die kleinste Maximall nge hat anschlie en diejenige mit der zweitkleinsten usw Eine optimale L sung ist dann gefunden wenn f r jeden Leitung ein Weg gefunden werden konnte Allerdings f hrt diese Heran gehensweise nicht immer zu einer optimalen L sung wie schon in Optimale Wege berechnen auf Seite 17 festgestellt worden ist Da diese Art von Algorithmen schon relativ komplex ist meist O n und auf w rts bed rfen sie einer genauen Analyse und effizienten Implementierung Der in CaNDeL implementierte Algorithmus erf llt seine Aufgabe bietet aber noch gen
37. nheit der einzelnen R ume an die dort verwendeten Baumaterialien und die Verl ufe der brigen Ka bel und Leitungen Des Weiteren ben auch noch regionale Bestimmungen Einfluss auf das Bauvorhaben aus Da diese Daten aber nicht in der NDML Beschreibung vorliegen und der Nutzer des Programms mit der Eingabe dieser Daten nicht ber fordert werden soll wird keinerlei R cksicht bei der Berechnung der optimalen Wege auf diese Sachverhalte genommen Es wird davon ausgegangen dass der Designer selbst einen guten Kenntnisstand hat und diesen nutzt um eventuelle Fehler bei der Verlegung der Kabelkan le zu vermeiden Ebenso wird davon ausgegangen dass die verschiedenen Kabeltypen alle den glei chen Durchmesser besitzen Somit kann man die Kapazit t eines Kanals mit der Anzahl an Kabeln die der Kanal aufnehmen kann gleichsetzen Angenommen ein Kanal hat die Kapazit t f nf so lassen sich in diesem Kanal f nf Kabel unterbrin gen Dies erleichtert zum Einen die Berechnung der optimalen Wege aber auch f r den Anwender bringt es Vorteile Die NDML Beschreibung des Netzwerks bietet bis jetzt keine M glichkeit an den Durchmesser eines Kabels zu spezifizieren So m sste der Nutzer f r jede Kabelart dazu aufgefordert werden deren Durchmesser anzugeben Eine zweite Erleichterung f r den Nutzer ergibt sich daraus dass jeder 14 Kanal eine Standardkapazit t von f nf hat Nur wenn der Kanal eine abweichende Gr e hat muss diese individuel
38. nn D DU v Berechnung der k rzesten Wege vom Startknoten aus solange D size gt 0 oder s nach such nach tue such minimum D D D such E E U such f r alle v V tue wenn such nach v von dann f r alle d D tue wenn v E und v D oder v kosten lt d kosten und v ziel d ziel dann D DU v Ermittlung des Weges vom Startknoten zum Zielknoten such s ziel s ziel 0 solange s start getFirst S start tue f r alle e E tue wenn such von e nach dann S putFirst S e l nge l nge e kosten such e break Auswertung der Berechnung wenn S size 0 dann return Es konnte leider kein Weg ermittelt werden wenn l nge gt s kosten dann return Der ermittelte Weg ist leider zu lang sonst L return S Algorithmus 3 Algorithmus zur Berechnung der optimalen Kabelf hrung 20 Insgesamt muss der ganze Algorithmus so oft wiederholt werden wie es zu berech nende Wege gibt Das Problem dass die Kanten nur eine bestimmte Kapazit t besitzen ist so gel st worden dass es in der Implementierung neben der Menge V noch eine weitere Menge gibt die die gleichen Tripel wie V enth lt nur das unter Kosten die Kapazit t der jeweiligen Kanten vermerkt ist Nach jedem Durchlauf des Algorithmus wird dann gepr ft ber welche Kanten der ermittelte Weg f hrt und deren Kapazit t um eins verringert Hat eine Kante die Kapazit t Null erreicht so wird diese aus der
39. och die Kapazit t der einzelnen Kanten siehe dazu Analyse der Realit t auf Seite 6 Wenn zu viele k rzeste Wege ber eine Kante f hren kann es dazu kommen dass die Kapazit t berschritten wird In diesem Fall muss nach einem alternativen Weg gesucht werden Dieser neue Weg wird zwar l nger als der alte Weg sein ansonsten w re er ja schon beim ersten Durchlauf gefunden worden aber ohne diese Nachrechnung g be es gar keinen m glichen Weg Zu beachten ist auch dass die Nachrechnung nicht erst ab dem Knoten gestartet werden kann von dem die volle Kante abgeht da das Ziel lauten muss den zweitk rzesten Weg im Graphen zu finden Und dies muss nicht gegeben sein wenn man den Algorithmus erneut von diesem Knoten starten l sst und nicht von dem Ursprungsknoten der Berechnung wie man anhand der Abbildung 4 auf Seite 10 leicht sehen kann Dies stellt die gefundenen Wege von A B und C gt B dar wobei die Kanten alle eine Kapazit t von eins haben Der Weg A gt B ist zuerst ermittelt worden Die durchgezogene Linie kennzeichnet die Wegf hrung nach einem Neustart des Algorithmus an Knoten D und die gestrichelte Linie die Wegf hrung nach einem Neustart am Ausgangsknoten C 600000000000000000000000000000 D Ze e d Abbildung 4 Zuerst ermittelte k rzeste Wege A gt B und C gt B An dieser Abbildung l sst sich auch leicht erkennen dass auch die Reihenfolge in der die Wege berechnet wer
40. och halb so gro wenn man nur eine Ma trixh lfte sichert sie enth lt aber immer noch viele berfl ssige Eintr ge Deshalb erfolgt die Speicherung des Graphen als eine Menge von Tripeln in Anlehnung an 18 Lo Abbildung 11 Einfacher Graph 22 Die Tripel haben die Form Startknoten Zielknoten Kosten Der dritte Eintrag des Tripels Kosten kann je nach Einsatz eine andere Bedeutung haben Er kann die L nge einer Kante beinhalten die Kapazit t einer Kante usw Nutzt man noch die Eigenschaft aus dass der Graph ungerichtet ist so ergibt sich folgende Menge V wenn man den Graphen wie in Abbildung 11 auf Seite 19 in dieser Tripelschreibweise darstellt V 1 2 2 1 7 3 1 3 4 3 5 1 4 5 2 5 6 2 Bei der Implementierung darf man dann nicht vergessen zu beachten dass eigentlich jedes Tripel doppelt vorkommt wobei die ersten beiden Eintr ge miteinander ver tauscht sind Das Starttripel s stellt den Weg dar f r den die k rzeste Wegf hrung berechnet werden soll Es hat die Form s Startknoten Zielknoten max L nge Der implementierte Algorithmus Pseudokode siehe Seite 20 lehnt sich stark an den Dijkstra Algorithmus aus 22 an Er ist nur etwas modifiziert worden um den besonderen Anforderungen gerecht zu werden Zun chst werden die Daten initialisiert Dann beginnt die eigentliche Suche der k rzesten Weg vom Startknoten aus Daf r m ssen zun chst die k rzesten Wege zu allen anderen Knote
41. r Nutzer des Programms der ein Kabelka nalnetzwerk designt DPI Dots per Inch Typische Einheit zur Angabe der Aufl sung DTD Document Type Definition Legt die Struktur eines XML Dokuments fest 3 GPL GNU General Public License Lizenzmodell f r freie Software 11 JavaDoc Automatisch aus dem Java Quelltext generierte Do kumentation die auf Kommentaren bestimmter Syntax beruht LAN Local Area Network NDML Network Design Markup Language XML Dialekt der von CANDY genutzt wird LGPL GNU Lesser General Public License Lizenzmodell fir freie Software 12 weniger restriktiv als GPL PDF Portable Document Format Plattform bergreifendes Da teiformat f r druckbare Dokumente welches von Adobe Systems entwickelt worden ist 8 Waagerechte Verkabelung Betrachtet man ein Haus bzw Grundriss von oben und legt dann Leitungen handelt es sich um eine waagerechte Verkabelung WLAN Wireless LAN XML Extensible Markup Language Standard zur Erstellung maschinen und menschenlesbarer Dokumente in Form einer Baumstruktur 6 XML Schema siehe XSD XSD XML Schema Definition Komplexe Sprache zur Beschrei bung eines XML Typsystems 9 Literatur 1 Algorithmus von Dijkstra http de wikipedia org wi ki Dijkstras_ Algorithmus 2 Bellman Ford Algorithmus http de wikipedia org wiki Bellman Ford Algorithmus 3 Document Type Definition http de wikipedia org wi ki DTD 4 Ethernet http de wikipedia org wiki
42. riss ausrichten kann und nicht explizit f r jede Kante deren L nge angegeben werden muss Allerdings f hrt das zu einer neuen Definition der Gleichheit zweier Graphen Im Allgemei nen sind der Graph 1 mit der Knotenmenge V1 der Kantenmenge El sowie der 16 Abbildung 8 Beispielnetzwerk Gewichtsfunktion Gl und der Graph 2 mit V2 E2 und G2 gleich wenn gilt V 1 V2 9 und EI E2 und G1 G2 9 wobei sich die Namen der Knoten unterscheiden k nnen Das hei t die L ngen der Kanten und die Position der Knoten spielen keine Rolle Diese Eigenschaft wird auch als Automorphismus bezeichnet Dies ist bei dem im Programm verwendeten Graphen nicht der Fall Abbildung 10 auf Seite 18 Die Positionen der einzelnen Knoten spielen eine wichtige Rolle da so die Kanten festgelegt werden und somit auch die L nge der Kanten Die Kapazit t der Kanten wird durch deren Beschriftung festgelegt Entf llt diese wird von einer Standardkapazit t von f nf ausgegangen siehe Vorraussetzungen auf Seite 14 3 4 Optimale Wege berechnen Kernst ck des Programms ist der Algorithmus zur Berechnung der k rzesten Wege in einem Graphen Da das Programm erst einmal nur die technischen M glichkei ten ausloten soll und die eigentliche Implementierung sehr zeitaufwendig war f llt der Algorithmus eher rudiment r aus Es wurde zwar versucht ihn zu optimieren aber im Mittelpunkt dieser Arbeit stand vor allem die technische Realisierung des Programms
43. rung betrachten Die Optimierungskriterien z B w ren Kabell nge Anzahl von Koppler Verteiler und Verst rker Anzahl von L chern und berg nge Gesamtkosten bei Leitungsf hrung etc In der Arbeit muss man auf existierende Optimierungsalgorithmen mit Nutzung des 2D Modells angehen Lee Wave Algorithm Bellman s Dynamic Programming Algorithm etc Im Rahmen der Arbeit soll auch ein XML basiertes Beschreibungsmodell f r die Geb udegeometrie bzw die Kabeltrassen in Rechnernetzen erarbeitet werden Als Vorlage ist die existierende problem orientierte Sprache NDMLv1 0 Network Design Markup Language zu verwenden Das oben genannte Modell muss in diese Sprache abgebildet werden In der Belegarbeit muss man definitiv zeigen dass die abstrakten Datentypen welche durch NDML gemappt werden optimal zu den CANDY spezifischen Zwecken sind Weiterhin ist innerhalb des CANDY Projekts eine Schnittstelle des Modells zu weiteren Projektierungs Tools bzw als Webservices mit Nutzung des J2EE Framework zu konzipieren und ein Trassierungsprogramm f r strukturierte Verkabelung mit dem Schwerpunkt Terti rsysteme zu implementieren Das Modell dient als Grundlage semantisches Schema zum Aufbau entsprechender Datenbank und muss in normalisierter Form dargestellt werden bzw sind die abstrakten Datentypen und Objekte Komponenten Services optimiert Weiterhin sind innerhalb der Arbeit die Konzepte weiterer Integration vorhandener Projektierungstool
44. s os 0 JO Oo A Ga N e N DD N N N N N N N e e Fa ka ka RR e Fa ah k DVD N O On A N e N Oa RA D N ra D Kabelkan le in verschiedenen Ausf hrungen 7 Richtungs nderung eines Kabelkanals 2 2 22 220 7 Aufsplittung bzw Zusammenf hrung eines Kabelkanals 7 Zuerst ermittelte k rzeste Wege A gt B und CB 10 Ermittelte k rzeste Wege C gt BundA gt B 10 Schaltzeichen f r eine Steckdose nach DIN 40900 14 Ausgabe der berechneten L nge und der Maximall nge 15 Beispielnetzwerk 17 Beispielnetzwerk Abbildung 8 auf Seite 17 als Graph 18 Zwei unterschiedliche gleiche Graphen 18 Einfacher Graph st dE ea leckere eier ns 19 Paketstruktur des Programms 2 2 nn VI Inhalt des Ordners CaNDeL 2 2m nn VII Knoten zeichnen ausw hlen o nn VII Knoten gezeichnet o VII Kanten einf gen ausw hlen o o VII Neue Kante hinzugef gt o nn nn VIII Verschieben eines Knoten o o VIII Mehrere Knoten selektieren VIII PDF einlesen w hlen VIII Eingabefenster f r den Ma stab 2 2 o o IX NDML einlesen w hlen 2 2 2 un o o IX Kapazit t einer Kante festlegen 2 2 2 2 2 nennen IX Knoten ein Ger t zuweisen 2 2m nn X Berechnung der k rzesten Wege starten X D
45. s Netzwerk fertig konzipiert ist Und dies stellt genau die Aufgabe von CANDY dar Es muss also ein Weg gefunden werden wie der Designer optimal bei seiner Aufgabe unterst tzt werden kann Dies kann geschehen indem er vor der Nutzung dieses Programms von Hand die Kan le in den Grundriss einzeichnet und das Programm diese Zeichnung auswertet Eine andere M glichkeit ist dass der Designer die Kan le am PC einzeichnen kann Nat rlich muss es dann m glich sein dass skizzierte Kabelkanalnetzwerk auszudrucken um dem Bauleiter die n tigen Instruktionen erteilen zu k nnen wie die Kan le verlegt werden sollen Die erste Variante hat den Vorteil dass das einzeichnen der Kan le schnell erledigt werden kann und kein PC ben tigt wird Allerdings ist es hinterher sehr schwer und fehleranf llig den Grundriss einzulesen und die Kan le maschinell zu identifizieren Au erdem muss bei einer nderung des Netzwerks diese im Grundriss vorgenommen und anschlie end erneut eingelesen werden Die zweite Variante hat den Vorteil dass das Netzwerk direkt am PC erstellt werden kann und nderungen leicht m glich sind Zudem entf llt die Fehlerquelle das beim Einlesen des Grundrisses Kanten nicht erkannt bzw falsche Kanten ermittelt werden Nachteilig ist dass eine Druckfunktion und oder Speicherfunktion realisiert werden muss um auch sp ter noch auf das erstellte Netzwerk zugreifen zu k nnen 2 1 2 Der Kabelkanal Kabelkan le gibt es in de
46. s als Webservices in die CANDY Umgebung zu entwickeln bzw mit Nutzung des J2EE Framework Schwerpunkte Recherche und Analyse bestehender Algorithmen zur Optimierung der Kabelf hrung Lee Wave Algorithm Bellman s Dynamic Programming Algorithm etc Analyse der im Rahmen des CANDY Projekts benutzten XML basierten Dokumenten und Verarbeitungsmodelle Konzipieren und Entwicklung des Trassierungsprogramms bzw als Webservices mit Nutzung des J2EE Framework Testen anhand einer Beispielnetzwerkgeometrie Entwicklung der Konzepte weiterer Integration vorhandener Projektierungstools in die CANDY Umgebung bzw mit Nutzung des J2EE Framework als Webservices Betreuer Dr Dietbert G tter Dr Andriy Luntovskyy Verantwortlicher Hochschullehrer Prof Dr A Schill Institut Institut f r Systemarchitektur Lehrstuhl Rechnernetze Beginn am 1 April 2005 Einzureichen am 1 Oktober 2005 Inhaltsverzeichnis 1 Einf hrung 1 1 Erl uterung der Aufgabenstellung Vorarbeit 2 1 Analyse der Realit t 2 2 2 22 Como nn SET Der Grundriss ios 2 222 0022 28828 DNA 212 Der Kabelkan l sa cos 2 2 2a0 3 A E H 2 2 Analyse vorhandener Algorithmen 2 2 1 Bellman Ford Algorithmus 2 nn nme 2 2 2 Dijkstra Algorithmus 222222 on nn 2 2 3 Res mee f r die Implementierung 22 222 200 2 3 Analese der NDML 2 2 22222 2 22 0m mama nn 2 4 Gesetzliche Bestimmungen und Normen
47. t cyan dunkelgrau grau gr n hellgrau magenta orange pink wei gelb bE Sel o n oaan el wl Rio Tabelle 2 Farbzuordnung in der properties version _1 dtd dabei das vorliegende Programm CaNDeL welches eine M glichkeit der Umsetzung prototypisch demonstrieren soll Zun chst musste man sich in das Thema der Kabelverlegung einarbeiten Das hei t es galt sich mit gesetzlichen Bestimmungen und geltenden Richtlinien vertraut zu machen sowie der optimalen Verlegung von Kabeln in einem Kanalsystem vertraut zu machen Mathematisch gesehen ist dies ein Problem der optimalen Wegfindung in einem Graphen erw hnt seien dazu an dieser Stelle nur kurz die Algorithmen Bellman Ford und Dijkstra Des Weiteren musste eine Programmstruktur entworfen werden die m glichst gut wartbar und erweiterungsf hig ist Dazu geh rt auch die Suche nach bereits vorhan den Programmen und Frameworks um diese entweder selber einsetzen zu k nnen oder um diese zu analysieren um L sungen f r eigene Probleme zu finden Eben so wichtig wie eine flexible Programmstruktur ist eine gute Benutzerschnittstelle damit der Anwender des Programms m glichst schnell und ohne gr ere Probleme mit dem Programm arbeiten kann Das Hauptaugenmerk lag hierbei auf der Er stellung des Kabelkanalnetzwerks und der Ausgabe des berechneten Ergebnisses Dieses muss auch in der Form zur Verf gung stehen
48. t werden ebenso etwaige Beschriftungen die Kanten und deren Kapazit t sowie bereits eingelesene PDF und NDML Dateien Aus diesen Anforderungen ist die Beschreibung save_ version 1 dtd siehe Listing 4 auf Seite 22 entstanden saveData sichert projektweite Daten wohingegen node die lt ELEMENT saveData nodes edges gt lt ATTLIST saveData name CDATA REQUIRED ndml CDATA IMPLIED pdf CDATA IMPLIED gt lt ELEMENT nodes nodex gt lt ELEMENT node EMPTY gt lt ATTLIST node id ID REQUIRED xPos CDATA REQUIRED yPos CDATA REQUIRED devicelD CDATA IMPLIED gt lt ELEMENT edges edgex gt lt ELEMENT edge EMPTY gt lt ATTLIST edge startNode IDREF REQUIRED endNode IDREF REQUIRED label CDATA IMPLIED Listing 4 save_ version 1 dtd Eigenschaften jedes einzelnen Knotens und edge die Eigenschaften jeder einzelnen Kante aufnimmt Dabei haben die einzelnen Attribute die folgende Bedeutung e name ist der Name des Projekts e ndmi ist der Pfad zu der zuvor eingelesenen NDML Datei Wurde noch keine eingelesen so entf llt dieser Eintrag e pdf ist der Pfad zu der zuvor eingelesenen PDF Datei Wurde noch keine eingelesen so entf llt dieser Eintrag e id ist die systemweit einmalige ID eines Knotens e xPos ist die X Position eines Knotens e yPos ist die Y Position eines Knotens e devicelD ist die ID des Ger ts welches einem Knoten zugewiesen worden ist Wenn noch keines zugewiesen worden ist so entf llt di
49. tras Adresse C CaNDeL Datei Kabelkanalnetz ber ii Einen weiteren Knoten hinzuf gen Abbildung 14 Knoten zeichnen ausw hlen O ICE Abbildung 15 Knoten gezeichnet Datei Kahelkanalnetz ber Knoten verschieben Kanten erzeugen Abbildung 16 Kanten einf gen ausw hlen VII Abbildung 17 Neue Kante hinzugef gt Abbildung 18 Verschieben eines Knoten Abbildung 19 Mehrere Knoten selektieren 3 liegt ein POF in den Hintergrund ein Abbildung 20 PDF einlesen w hlen VIII Geben Sie den Ma stab ein EJ Geben Sie den Ma stab des Grundriss ein Abbildung 21 Eingabefenster f r den Ma stab helkanalnetz ber Liest die NDML Beschreikung des Net Abbildung 22 NDML einlesen w hlen Abbildung 23 Kapazit t einer Kante festlegen IX Abbildung 24 Knoten ein Ger t zuweisen alnetz ber Startet die Berechnung des Metmwerks Abbildung 25 Berechnung der k rzesten Wege starten Switch 4 Switch 2 Switch 3 Switch 1 Server ber Knoten max L nge ermittelte L nge Der ermittelte k rzeste Weg ist leider bereits zu lang 10 00 m 13 32 m Switch 1 Es konnte leider kein Weg ermittelt werden 94 00 m Switch 5 direkte Verbindung 100 00 m 1 43 m Switch 3 14 110 00 m 8 38 m Switch 4 Switch 3 14 1 000 00 m 11 20 m Abbildung 26 Das Ergebnis einer
50. u einem sp teren Zeitpunkt nochmals anzeigen zu lassen einfach in der Symbolleiste auf das Ergeb nissymbol klicken Abbildung 27 auf Seite XI ACHTUNG Es wird keine neue Berechnung gestartet sondern nur das zuvor berechnete Ergebnis angezeigt 4 9 Ausdrucken Das Ergebnis der Berechnung kann ber das Ergebnisfenster siehe Das Ergebnis einer Berechnung auf Seite 27 gedruckt werden Der erstellte Graph kann mit samt Hintergrundbild ber das Drucksymbol in der Symbolleiste gedruckt werden Abbildung 28 auf Seite XI 27 4 10 Das Men Alle zuvor beschriebenen Funktionen lassen sich auch ber das Men ausf hren Zus tzlich bietet das Men Datei an einen neuen Graphen zu erstellen Hierbei werden alle bis dahin noch nicht gespeicherten nderungen verworfen Man kann au erdem die Seiteneinstellung f r die Druckdatei vornehmen und bspw die Sei tenr nder neu einstellen Des Weiteren lassen sich dort Eintr ge zum Laden und Speichern finden Wichtig beim Laden und Speichern ist dass sich die Datei sa ve_version_ 1 dtd in dem gleichen Ordner wie die zu speichernde ladende Datei befindet Das Men ber ffnet ein Fenster mit Informationen ber CaNDeL 4 11 Konfiguration von CaNDeL Die wichtigsten Einstellungen in CaNDeL lassen sich individuell auf die eigenen Be d rfnisse abstimmen Um nderungen vorzunehmen muss man die Datei Einstel lungen xml im Unterordner data ffnen und diese nach sei
51. um Beispiel XML Dateien auch validierend einlesen und sie so auf Fehler analysieren 3 8 Die Programmstruktur Das Programm setzt sich aus den Paketen dialog graphComponents networkData properties und solver zusammen wobei das Paket graphComponents noch die Pakete views und handler beinhaltet graphische Darstellung siehe Abbildung 12 auf Seite VI Die main Funktion des Programms befindet sich in der Klasse Main und startet nur den Coordinator Dieser bernimmt die komplette Verwaltung des Programms und vermittelt zwischen den einzelnen Paketen Das Paket properties verwaltet die Daten zur Konfiguration des Programms wie es unter Erl uterung der Konfigurationsdatei properties version 1 dtd auf Seite 21 geschildert ist Das Paket networkData ist die Mittelschicht zwischen den Da tenstrukturen des Graphen und der Darstellung des Graphen Zudem verwaltet es die Ger te die aus der NDML Beschreibung ausgelesen werden Das Paket dialog beinhaltet Dialoge um mit dem Nutzer zu kommunizieren Das Paket solver im plementiert den Algorithmus wie er unter Optimale Wege berechnen auf Seite 17 skizziert worden ist Um den Algorithmus m glichst gut austauschbar zu machen sind die ben tigten Datenstrukturen und Methoden in Interfaces siehe Listing 5 6 und 7 auf Seite 24 25 und 26 definiert worden Zudem ist die Methode solveTheProblem in ISolver mit der Signatur List lt IReturnData gt solveTheProblem Object graph Object e
52. wenden zu k nnen musste diese analysiert und die f r das zu erstellende Programm wichtigen Spezifikationen ermittelt werden Bei der Erbauung von Geb uden m ssen viele Gesetze und Richtlinien ber cksich tigt und beachtet werden Das trifft auch f r die Verkabelung zu Deswegen galt es entsprechende Nachforschungen anzustellen um gegebenenfalls wichtige Sachver halte bei der Implementierung zu ber cksichtigen Wichtig ist auch die graphische Darstellung damit sich der Designer m glichst schnell mit dem Programm zurecht finden kann und auch der Elektroinstallateur der im Anschluss die einzelnen Netz werkkabel verlegen soll sofort erblicken kann wo er welches Kabel verlegen soll 2 1 Analyse der Realit t Um ein Programm zu realisieren muss man zuerst die reale Welt studieren um diese verstehen zu k nnen Erst mit diesem Verst ndnis kann ein anwendergerechtes Programm geschrieben werden welches das gegebene Problem zufrieden stellend l st Wichtig beim Hausbau ist der Grundriss Dieser gibt vor wo welche Wand verl uft wie hoch die Decken sind und vieles mehr Aber auch die Kabelkan le selbst bed rfen einer genaueren Betrachtung da diese die eigentliche Basis f r die Berechnung der optimalen Wege bilden 2 1 1 Der Grundriss Im Allgemeinen ist es so dass der Verlauf der Kabelkan le noch nicht im Grundriss enthalten ist Diese werden erst nachtr glich von der f r das Netzwerk zust ndigen Person eingetragen wenn da
53. ypen und deren Maximall ngen 4 5 der Tabelle 1 auf Seite 11 sehen kann ist es aber gar nicht so leicht eine Aussage zu treffen wie lang ein Kabel sein darf So kann ein und dasselbe Kabel bei identischer bertragungsrate unterschiedlich lang sein nur bedingt durch die Verwendung einer anderen bertragungstechnik Hat man dieses Problem gel st so k nnte man den Algorithmus terminieren sobald dieser w hrend der Berechnung feststellt dass der bis jetzt berechnete Weg bereits l nger ist als es die Maximall nge des Kabels zul sst Der zu implementierende Algorithmus muss demnach zwei Kriterien bei der We gewahl ber cksichtigen Zum einen die L nge der Kanten und zum anderen die Kapazit t der Kanten Des Weiteren ist die Reihenfolge in der die k rzesten Wege berechnet werden wichtig 2 3 Analyse der NDML Um Berechnen zu k nnen wie die Kabel verlegt werden soll werden die Daten der Netzwerkinfrastruktur ben tigt Diese sollten laut Aufgabenstellung der NDML Beschreibung entnommen werden die in den vorangegangenen Programmstufen von CANDY erstellt worden ist Hierbei handelt es sich um ein CANDY eigenes XML Format welches durch eine DTD definiert wird Zur Zeit der Belegerstellung befand diese sich in der Version 1 1 Nach Fertigstellung lag eine Weiterentwicklung zu der Version 2 0 vor und berlegungen f r eine Version 3 0 siehe 14 Da es sich aber bei den Neuerungen eher um strukturelle als um inhaltliche Ver n

Download Pdf Manuals

Related Search

Related Contents

The GALFA HI User`s Guide  USER'S GUIDE  the advanced energy rfg 5500 generator with display  Mobistel EL560Dual 2.4" 130g Black  2 MODE OPERATOIRE COLLECTE  Sahara 1150017 project mount  

Copyright © All rights reserved. Failed to retrieve file