Kontakt: 

Stand: 28.10.2003
Erstellt: F. Haberland

Nichthierarchische Netze

NHR-Teilnetzberechnung  VE-orientiertes Routing  Trunkreservation  Bündelberechnung  Dekomposition

Es wird ein Verfahren beschrieben, ein autarkes nichthierarchisches Netz oder ein in ein hierarchisches Netz eingebettetes nichthierarchisches Teilnetz zu dimensionieren und zu optimieren. Im zweiten Fall müssen die beteiligten Vermittlungseinheiten (VE) Vermittlungsfunktionen innerhalb einer Netzebene haben. Für ein solches (i.Allg.) Teilnetz soll die Installation eines mehrstufigen nichthierarchischen Dreieckroutings (NHR) möglich sein. Derartige NHR-Teilnetze werden jeweils in einer eigenen Iterationsschleife mit wechselseitig betriebenen Bündeln und Trunkreservation kostenoptimierend berechnet. Dabei können Quer- oder Letztwege-Teilnetze mit VE- oder VSt-bezogenem Routing nach verschiedenen Modi berechnet oder optimiert werden.

Mögliche Anwendungsfälle sind

• ein nichthierarchisches Einebenennetz mit Letztwegen,
• die höchste Netzebene eines hierarchischen Netzes als nichthierarchisches Letztwegenetz,
• Bereiche einer Ebene eines hierarchischen Netzes als abgeschlossene Teilnetze,
• beliebig geschnittene Teilnetze einer Ebene eines hierarchischen Netzes.

Soweit für ein NHR-Teilnetz keine oder nur teilweise eine explizite Routingliste vorgegeben wird, erstellt bzw. ergänzt das Verfahren gemäß einer gewünschten Stufenzahl dieses Routing. Die Entscheidung einer Querwegenetz-Berechnung wird ggf. vom Verfahren korrigiert, wenn nicht bei allen beteiligten VE im umfassenden hierarchischen Netz ein Überlauf in dieses möglich ist.

Trunkreservation ist ein Prinzip, bei welchem der Verkehr in einen vorrangig und einen nachrangig zu behandelnden Anteil aufgeteilt wird. Vorrangverkehr kann das Bündel immer belegen, wenn mindestens eine Leitung frei ist. Nachrangverkehr kann dasselbe Bündel nur belegen, wenn dabei mindestens TR Leitungen frei bleiben. TR ist die vorgebbare Größe der Trunkreservation. Für das NHR-Teilnetz kann festgelegt werden, bis zu welcher Routingstufe (1. Teilweg des Dreiecks) und ob für Verkehr im zweiten Teilweg Vorrang gelten soll.

nach oben

NHR-Teilnetzberechnung

Für jedes in das hierarchische Netz eingebettete NHR-Teilnetz wird die Menge der am NHR-Teilnetz (TN) beteiligten VE auf das Teilnetzmodell abgebildet. Das TN hat eigene (komplizierter strukturierte) TN-VE und TN-Verkehrselemente. Die TN-VE fungieren als Quellen und als Transitknoten. Senken des TN sind im TN vertretene VSt der gegebenen Ebene.

Die NHR-Teilnetzberechnung ist ein Eingriff in die taktgesteuerte Berechnung des umfassenden hierarchischen Netzes. Im Takt der Teilnetzebene Eb vor Beginn des Untertakts Eb werden für alle zu einem NHR-Teilnetz gehörenden VE die das Teilnetz betreffenden Verkehrselemente angesammelt und in das Teilnetz übertragen. Für alle nicht an Teilnetzen dieser Ebene beteiligten VE wird der Untertakt Eb noch ausgeführt, danach aber die Untertaktsteuerung unterbrochen.

Für die an TN der Ebene Eb beteiligte VE wird am Taktende (alle Untertakte nach Untertakt Eb unterbrochen) die Teilnetzberechnung ausgeführt. Es folgt die Übertragung der vom Teilnetz geleisteten und der übergelaufenen Verkehre in die Verkehrselemente des hierarchischen Netzes.

Für alle VE des Netzes wird die Taktsteuerung bei Takt Eb und Untertakt (Eb + 1) wieder aufgenommen.

VE-orientiertes Routing

Für NHR-Teilnetze ist nur Dreieckrouting zugelassen, d.h. der Verkehr von TN-Quelle zu TN-Senke wird über höchstens eine Transit-VE geführt. Es ist Mehrfachüberlauf bis zu einer vorgebbaren Stufenzahl möglich. Jedes TN-Verkehrselement enthält das zugehörige Routing und trägt anstelle des Verkehrswertes die Verkehrsbestandteile jedes einzelnen Routingschrittes.

nach oben

Die Routing-Einträge eines UVE-Senke-bezogenen Verkehrselements sind

Werden Vorgabebündel mit der LSZ des betreffenden Teilnetzes und mit einer solchen Bündelberücksichtigungsregel, welche die Einrichtung des Bündels verbietet, angetroffen, so sind Wege über diese Bündel unzulässig.

Die Syntax der expliziten Routingliste erlaubt ebenfalls, dass ein bestimmtes (darüber hinaus auch jedes) Direktwegbündel verboten werden kann. Für NHR-Querwegenetze wird ein explizites Routing mit Stufenzahl Null, d.h. Direktwegverbot und keine Umwegangabe, toleriert. Eine derartige explizite Routingliste kann das Ergebnis einer NHR-Teilnetzoptimierung sein.

Die Prozesse Routingerstellung aus Routingvorgabe und Routingergänzung arbeiten mit dem Ziel, ein für die Algorithmen benötigtes vollständiges Routing zu installieren. Dabei werden zunächst Bündelvorgaben in der Weise berücksichtigt, dass keine Routingeinträge entstehen, die zu nicht erlaubten Bündeln gehören. Fehlen am Ende Routingeinträge, werden diese nacherstellt und können sich dann auch auf nichterlaubte Wege beziehen. Für Querwegenetze ist solches Verfahren zulässig. Für Letztwegenetze erfolgt eine abschließende Prüfung auf Zulässigkeit der zweiten Teilwege von Routing-Dreiecken.

Stellt sich bei Berechnung eines NHR-Querwegenetzes heraus, dass nicht für jede Quelle-Senke-Beziehung ein Überlauf in das umfassende hierarchische Netz möglich ist (damit ist dann auch kein Kostenvergleich möglich), wird automatisch auf den Letztwegemodus umgeschaltet.

nach oben

Iteration

Jedem Paar von TN-VE ist ein wechselseitig betreibbares Bündel (WBB) ohne Bündelteilung zugeordnet. Die iterative Berechnung eines NHR-Teilnetzes erfolgt für feste Bündelgrößen nach folgendem Schema:

Jedem der Routing-Einträge ist der dem durch UVE und Ziel-VE genannten WBB anzubietende Verkehr mit Mittelwert und Streuwert zugeordnet. Die Verkehrselemente sind doppelt angelegt (alt/neu), wobei die jeweils alte Verkehrsflussmatrix immer den gültigen Stand des letzten Iterationsschrittes festhält. Die "neue" Verkehrsflussmatrix entsteht durch die ermittelbaren Verkehrsflüsse und Überläufe:

Einem Bündel UVE->ZVE wird neben anderen Verkehrskomponenten auch der Verkehr des UVE-Routingeintrags Ziel[j] = ZVE angeboten. Nach Bündelberechnung und Dekomposition steht fest, welcher Verkehrsanteil vom Bündel geleistet wird und welcher überläuft. Beide Anteile werden in die "neue" Verkehrsflussmatrix übertragen: Folgt bei der UVE dem Ziel[j] noch ein Ziel[j+1], dann wird der Überlaufverkehr in das entsprechende UVE-Verkehrsflusselement der neuen Matrix beim Ziel[j+1] additiv übernommen. Gibt es keinen höherrangigen Zieleintrag mehr, ist der Überlauf als Verlust bezüglich des TN zu werten. Der geleistete Verkehr wird in die neue Matrix, und zwar in das der ZVE zugeordnete Verkehrsflusselement derselben Senke bei dem Ziel ZwTeilw additiv übernommen.

Für in gleicher Weise beteiligten Verkehr des Routingeintrags ZwTeilw gilt sinngemäß: Geleisteter Verkehr hat die Senke erreicht; Überlaufverkehr verlässt das TN.

nach oben

In der Ablaufsteuerung der Bündelberechnung werden je WBB für beide Verkehrsrichtungen alle Verkehrsanteile von Verkehrsflusselementen beider TN-VE angesammelt, die gemäß Zieleintrag auf die jeweils andere VE des WBB zu führen sind. Es addieren sich also Verkehrsanteile, die im Direktweg, im 1., 2., ... Überlauf und solche die (bereits übergelaufen) im zweiten Teilweg angeboten werden.

Um eine Dekomposition der beiden Richtungsverkehre zu ermöglichen, wird der Summenverkehr auch getrennt nach Verkehrsrichtung erfasst. Da das Bündel mit Trunkreservation (s.o.) zu berechnen ist, werden auch Vorrang- und Nachrangverkehr getrennt erfasst. Die bei der Bündelberechnung ermittelbaren Überlaufwahrscheinlichkeiten für Vorrang- und Nachrangverkehr werden für die Dekomposition der Verkehrsbestandteile benutzt.

Vor der ersten Iterationsschleife gibt es nur Verkehrsangebote im Direktweg. Nach der ersten Iterationsschleife stehen bereits Verkehrsangebote im 1. Überlaufweg, aber noch keine im 2. Überlaufweg und noch kein Angebot im zweiten Teilweg an. Diese kommen erst nach der zweiten Iterationsschleife hinzu.

Ist eine Iterationsschleife beendet, wird die neue Verkehrsflussmatrix als alte genommen und die nunmehr neue bis auf die originalen Direktwegangebote gelöscht. Die gesamte Iteration erfolgt nur für feste Bündelgrößen. Es sind mindestens so viele Schleifen nötig wie es Routingstufen gibt, bevor erstmals Verlust im ersten Teilweg auftritt und eine Konvergenz beginnen kann.

Ist die Iterationsgenauigkeit, gemessen an der Summe aller betragsmäßigen Änderungen der Verkehrsflusseinträge, bezogen auf das Gesamtangebot, erreicht, erfolgt eine abschließende Schleife mit zusätzlichen Auswertungen. Dabei werden für ein Querwege-Teilnetz die aus dem TN herausführenden Überlaufverkehre und die Überlaufkosten bestimmt. Für ein Letztwege-Teilnetz werden die TN-bezogenen Ende-zu-Ende-Verluste ermittelt. 

nach oben