Gegenstand der vorliegenden Erfindung ist ein Verfahren zur Leitweglenkung in einem privaten Netz, in dem mindestens einige Leitwege eine Komprimierung einsetzen.

Die Erfindung bezieht sich auf private Telekommunikationsnetze. Solche Netze werden gebildet aus Verbindungsknoten, die untereinander durch Bögen oder Leitwege verbunden sind, die die Nachrichten und/oder die Signalisierung weiterleiten. Sie gilt sowohl für private Netze, die aus dedizierten Verbindungen bestehen (physische private Netze) als auch für virtuelle private Netze oder für gemischte Netze, die diese beiden Lösungen mischen. Im nachfolgenden Teil der Beschreibung wird die Erfindung unter Bezugnahme auf ein Beispiel für ein privates Netz mit Signalisierung beschrieben, aber sie gilt ganz allgemein für andere private Netze.

Bekanntermaßen erfolgt in solchen Netzen auf manchen Leitwegen eine Komprimierung der übertragenen Signale. Dieses kann insbesondere auf den Leitwegen der Fall sein, die nur einen einzigen Kanal aufweisen, um die Weiterleitung einer gößeren Anzahl von Nachrichten zu ermöglichen. Eine solche Komprimierung kann den Nachteil aufweisen, dass Qualitätsverluste induziert werden, und gegebenenfalls die Durchgangszeit auf Grund der für die Komprimierung und Dekomprimierung erforderlichen Zeit erhöht wird. Eine große Zahl von Komprimierungen und Dekomprimierungen kann auch Echos und Dämpfungen in der Übermittlung bewirken.

Einige Verfahren zur Leitweglenkung ignorieren die Zahl der Komprimierungen und Dekomprimierungen und akzeptieren die Beeinträchtigung der Qualität der Verbindungen in den Fällen, wo die Anzahl hoch ist. Diese Lösung führt dazu, dass in einigen Instanzen ein Dienst geliefert wird, der eine herabgesetzte Qualität aufweist. Andere Verfahren zur Leitweglenkung verwenden eine statische Leitweglenkungstabelle, bei der die Anzahl der Komprimierungen und Dekomprimierungen begrenzt ist. Diese Lösung ist begrenzt und gestattet keine vollständige Ausnutzung des privaten Netzes. Eine letzte Lösung besteht darin, per Konfiguration die Anzahl der Durchgangsknoten und somit die mögliche Anzahl an Komprimierungen und Dekomprimierungen zu begrenzen; diese Lösung ist nicht in allen privaten Netzen anwendbar und schränkt deren mögliche Konfigurationen ein.

Dokument XP000210435 (IBM TECHNICAL DISCLOSURE BULLETIN) vom 1. August 1991 beschreibt ein Verfahren, das darin besteht, einen Graphen zu konstruieren, der gewichtet wird durch die Kosten für Komprimierung, Dekomprimierung und Übertragung.

Der am wenigsten kostspielige Weg wird durch einen herkömmlichen Algorithmus, wie z.B. den Dijkstra-Algorithmus ermittelt.

Bei den privaten Netzen stellt sich auch das Problem des Überlaufs; d.h. das Problem einer Verbindungsanforderung, der vom Netz nicht entsprochen werden kann, da die Kapazitäten gesättigt sind. Das kann passieren, sobald die privaten Leitwege des privaten Netzes eine feste Kapazität aufweisen, die nicht dynamisch zugewiesen wird und unter dem maximal möglichen Verkehrsvolumen liegt. Es ist bekannt, die entsprechende Verbindung dadurch zu gewährleisten, dass man das öffentliche Netz oder ein anderes externes Netz benutzt. Mit anderen Worten: falls ein Teilnehmer eines ersten Knotens des privaten Netzes versucht einen Teilnehmer eines zweiten Knotens zu erreichen und wenn mindestens ein Leitweg des privaten Netzes gesättigt ist, so dass die Verbindung nicht gewährleistet werden kann, erfolgt die Verbindung direkt vom ersten Knoten zum zweiten Knoten über ein externes Netz – typischerweise das öffentliche Netz.

Diese Lösung wirft folgende Probleme auf. Zum einen ist der Rückgriff auf das öffentliche Netz mit Kosten verbunden; zum anderen ist es nicht sicher, dass ein Bündel für den Zugang zu dem öffentlichen Netz für alle Knoten vorhanden ist. Außerdem ist diese Lösung wirtschaftlich nicht sehr rentabel und nutzt die Kapazitäten des privaten Netzes nicht vollständig aus.

Die Erfindung bietet eine Lösung für diese Probleme an; sie ermöglicht es, den Überlauf des privaten Netzes zu managen, wobei die Kosten für den Zugang zum öffentlichen Netz minimiert und die Nutzung der Kapazitäten des privaten Netzes maximiert wird. Sie gilt nicht nur für Überlaufvorgänge hin zum öffentlichen Netz, sondern ganz allgemein für Überlaufvorgänge in Richtung aller Arten von Netzen, die zum privaten Netz extern sind: geschaltetes öffentliches Netz, öffentliches erd- oder satellitengestütztes Mobilfunknetz, anderes privates Netz, usw.

Der Dijkstra-Algorithmus wird in Algorithmuswerken beschrieben und ist bekannt dafür, in einem Graphen einen kürzesten Weg zwischen zwei Knoten zu finden. Man kann insbesondere nachschlagen in (erforderlichenfalls Referenz einfügen). Dieser Algorithmus ist folgender: man betrachtet einen Graphen G mit N Knoten, der bewertet wird, das heißt, von dem jeder zwischen zwei Knoten i und j existierende Weg mit einer Bewertung oder einem Gewicht 1(i, j) versehen wird. Als s betrachtet man einen Ausgangsknoten des Graphen G, mit d einen Ankunftsknoten, und man sucht einen Weg, der &pgr;(s, d), die Entfernung von s zu d minimiert, das heißt die Summe der Bewertungen der Bögen, die s mit d verbinden.

Als S schreibt man den Teilgraphen von G, der gebildet wird aus den Knoten x, für die man den minimalen Weg hin zu s kennt und S als sein Komplement. Außerdem schreibt man die Gesamtheit der Nachbarknoten eines bestimmten Knotens i als &Ggr;_i.

Zu Beginn enthält der Teilgraph S nur den Knoten s, und S enthält sämtliche anderen Knoten, denen folgende Anfangswerte zugewiesen sind:

&pgr;(s, i) = 1(s, i) für i ∁ &Ggr;_s, wobei der Elternknoten s ist;

&pgr;(s, d) = ∞, für die anderen Knoten, die keinen Elternknoten haben.

Eine Iteration des Algorithmus findet folgendermaßen statt.

Falls S leer ist oder er nur Knoten i mit &pgr;(s, i) = ∞ enthält, hat man beendet.

Anderenfalls betrachtet man den Knoten n aus S , der dem Ausgangsknoten am nächsten ist, d.h. der Knoten, der &pgr;(s, i), i ∊ S minimiert; man nimmt diesen Knoten und man nimmt ihn aus S heraus, um ihn in s einzusetzen.

Anschließend betrachtet man die Nachbarn dieses Knotens n und man berechnet &pgr;(s, n) + 1(&pgr;, j), j ∊ &Ggr;_n und j ∊ S;

Wenn diese Menge kleiner ist als &pgr;(s, j) aktualisiert man &pgr;(s, j) und man aktualisiert auch den Knoten &phgr;(j), der Eltern von j ist, der zu n wird.

Man nimmt diese Operation für alle Knoten von &Ggr;_n vor, dann ordnet man S um.

Auf diese Art und Weise fügt man allmählich sämtliche Knoten des Graphen zu S hinzu, indem man mit zunehmender Länge der Wege vorgeht.

Wenn man einen Weg zu einem bestimmten Knoten d sucht, kann der Algorithmus vor dem Ende unterbrochen werden, sobald der Zielknoten in dem Teilgraphen S hinzugefügt wurde.

Der Algorithmus wird folgendermaßen durch die Umkehrung bewiesen. Man betrachtet n als den S am nächsten kommenden Knoten, der zu S hinzugefügt werden soll. Wenn es einen am nächsten gelegenen Weg gibt, geht dieser Weg von s aus und gelangt zu n, und weist einen ersten Knoten in S auf, der als m geschrieben wird. Man hat dann &pgr;(s, m) + &pgr;(m, n) < &pgr;(s, n ) und da &pgr;(m, n) positiv oder null ist, &pgr;(s, m) < &pgr;(s, n) was der Hypothese widerspricht. Es ist außerdem klar, dass &pgr;(s, m) in einer vorhergehenden Iteration berechnet wurde, bei der Hinzufügung des Elternteils von m in S.

Die Erfindung schlägt eine Lösung für das Leitweglenkungsproblem in den privaten Netzen vor, die auf einigen Leitwegen eine Komprimierung der Signale einsetzen, die die Qualität der Verbindungen erhält, und gleichzeitig eine gute Nutzung der Kapazitäten des Netzes gewährleistet. Außerdem gestattet sie es, andere Bedingungen zu erfüllen, und zum Beispiel den Überlauf hin zu anderen Netzen zu managen.

Es ist klar, dass dieses Problem ein wichtiges technisches Problem ist, und dass das Verfahren, auf das Anspruch erhoben wird, unter diesem Gesichtspunkt eine technische Lösung zu einem technischen Problem darstellt – selbst wenn es einen Algorithmus verwendet.

Genauer gesagt schlägt die Erfindung ein Verfahren zur Leitweglenkung zwischen einem Quellknoten und einem Zielknoten in einem privaten Netz vor, das Knoten aufweist, die durch Leitwege verbunden sind, wobei jeder Leitweg von der Art ohne Komprimierung oder von der Art mit Komprimierung sein kann,

wobei eine Komprimierung auf mindestens einem dieser Leitwege eingesetzt wird, aber die Gesamtzahl der für die Weiterleitung einer Nachricht durchgeführten Komprimierungen und Dekomprimierungen eine festgesetzte Höchstgrenze nicht überschreiten darf; dieses Verfahren beinhaltet mindestens einen Schritt, der darin besteht, die Ergebnisse zu speichern, die man für einen bestimmten Wert der Anzahl von Komprimierungen und Dekomprimierungen gewonnen hat, um sie für die späteren Berechnungen zu nutzen;

dadurch gekennzeichnet, dass es folgendes enthält:

• – einen Schritt Suche nach einem kürzesten Weg zwischen einem Quellknoten und einem Zielknoten bei einer bestimmten Anzahl von Komprimierungen und Dekomprimierungen;
• – dann mindestens einen weiteren Schritt Suche nach einem kürzesten Weg zwischen diesem Quellknoten und diesem Zielknoten, wobei man den Wert der Anzahl an Komprimierungen und Dekomprimierungen zunehmen lässt, wobei dieser kleiner oder gleich der festgesetzten Höchstgrenze bleibt;
• – dann einen Schritt Ermittlung des kürzesten Weges unter den zuvor gefundenen kürzesten Wegen.

Bei einer Ausführungsart der Erfindung schließt das Verfahren die Wahl einer Kostenfunktion ein, und die Leitweglenkungsberechnung beinhaltet die Minimierung der Kostenfunktion.

Vorteilhafterweise enthält ein Leitweglenkungsberechnungsschritt für eine bestimmte Anzahl von Komprimierungen in einem Knoten (n), wo die Anzahl Komprimierungen ab dem Quellknoten gleich der bestimmten Anzahl ist, die Suche nach den benachbarten Leitwegen, auf denen eine Komprimierung eingesetzt wird, und die Speicherung für einen späteren Berechnungsschritt.

Ein Schritt Leitweglenkungsberechnung für eine bestimmte Anzahl von Komprimierungen kann durch Anwendung des Dijkstra-Algorithmus erfolgen, wobei die Anzahl der Komprimierungen beim Hinzufügen eines Knotens zur Leitweglenkung überprüft wird.

Bei einer anderen Ausführungsart der Erfindung beinhaltet das Netz außerdem Überlaufbögen hin zu einem externen Netz, und das Verfahren enthält mindestens zwei Schritte Leitweglenkungsberechnung für eine bestimmte Anzahl Überlaufvorgänge und für eine bestimmte Anzahl Komprimierungen, einen Schritt Leitweglenkungsberechnung für eine Anzahl Überlaufvorgänge und eine bestimmte Anzahl Komprimierungen, die Informationen verwenden, die gewonnen werden bei einem Schritt zur Leitweglenkungsberechnung für eine Überlaufzahl kleiner als diese bestimmte Überlaufzahl.

In diesem Fall enthält das Verfahren vorzugsweise die Wahl einer Kostenfunktion, die repräsentativ ist für die Kosten des Überlaufs, und die Leitweglenkungsberechnung beinhaltet die Minimierung der Kostenfunktion.

Vorzugsweise erfolgen die Rechenschritte für eine bestimmte Überlaufzahl, indem man die Anzahl der Komprimierungen verändert, dann indem man die Anzahl der Überlaufvorgänge verändert.

Weitere Kennzeichen und Vorteile der Erfindung treten beim Lesen der nachfolgenden Beschreibung von Ausführungsarten der Erfindung zutage, die beispielhaft und unter Bezugnahme auf die beigefügten Zeichnungen erfolgt, wobei diese folgendes zeigen:

1 eine schematische Darstellung der Ausführung des Verfahrens aus der Erfindung in einem privaten Netz mit sechs Knoten;

2 eine schematische Darstellung der Ausführung der Erfindung in einem anderen privaten Netz;

3 eine schematische Darstellung der Ausführung der Erfindung in noch einem weiteren privaten Netz.

Die Erfindung schlägt vor, in einem privaten Netz eine Leitweglenkung durch Suchen des kürzesten Weges zwischen einem Quellknoten und einem Zielknoten für einen bestimmten Wert der Anzahl der Komprimierungen und Dekomprimierungen zu berechnen, dann indem man den Wert der Anzahl an Komprimierungen und Dekomprimierungen erhöht. Zwecks Begrenzung der Anzahl der Rechenvorgänge schlägt die Erfindung außerdem vor, die für einen bestimmten Wert der Anzahl der Komprimierungen und Dekomprimierungen gewonnenen Ergebnisse zu speichern, um sie für spätere Berechnungen zu nutzen.

Im Folgenden werden wir die Erfindung anhand eines Beispiels eines privaten Netzes beschreiben, das verschiedene Arten von Bögen oder Leitwegen enthält, nämlich Leitwege mit und ohne Komprimierung; das Netz erlaubt außerdem die Weiterleitung von Sprach- oder Datenkommunikation. Bei dem Beispiel betrachtet man die folgenden Regeln für die Weiterleitung durch das Netz:

• – indem man von einem Knoten zum nächsten vorgeht, versucht man falls möglich in der gleichen Verbindungsqualität – komprimiert oder nicht – zu bleiben, so dass die Komprimierungs- und Dekomprimierungsfreiheiten für die spätere Weiterleitung der Nachricht nicht verringert werden;
• – wenn Komprimierung erforderlich ist, um von einem Knoten zu seinem Nachbarn zu gelangen, dann darf die Gesamtzahl der Komprimierungen und Dekomprimierungen, die für die Weiterleitung der Nachricht durchgeführt werden, nicht die gewählte Höchstgrenze überschreiten; diese Grenze kann außerdem gegebenenfalls von der Art der durchlaufenden Nachricht abhängen; diese Grenze wird vorteilhaft so ermittelt, dass sie eine Hörqualität beim Eintreffen ermöglicht.
• – falls eine Nachricht in komprimierter Form auf einem Knoten eintrifft und falls der folgende Leitweg es erlaubt, führt man fort, ohne die Nachricht zu dekomprimieren; ansonsten kann man die Nachricht dekomprimieren.

1 zeigt eine schematische Darstellung der Ausführung des Verfahrens der Erfindung in einem privaten Netz mit sechs Knoten. Das Netz aus der 1 enthält sechs Knoten, die von 1 bis 6 nummeriert sind, und die folgenden Leitwege oder Bögen:

• – Leitwege ohne Komprimierung zwischen den Knoten 1 und 3, 3 und 2, 2 und 4, 4 und 5, 5 und 6, die auf der Figur mit „q" gekennzeichnet sind;
• – Leitwege mit Komprimierung zwischen den Knoten 1 und 2, und 2 und 6, die auf der Figur mit „q_c" gekennzeichnet sind.

Bei dem Beispiel, das in 1 als Referenz angegeben wird, sucht man eine Leitweglenkung zwischen dem Quellknoten 1 und dem Zielknoten 6, mit einer maximalen Anzahl von Komprimierungen und Dekomprimierungen NVcompMax von 2. Intuitiv ist die Lösung eine Leitweglenkung via Knoten 2, mit einer einzigen Komprimierung und einer Dekomprimierung am Knoten 6; wie weiter oben erläutert dekomprimiert man nicht beim Durchgang durch den Knoten 2.

Die Erfindung schlägt vor, zur Gewinnung der Lösung den Dijkstra-Algorithmus für eine Berechnung des kürzesten Wegs anzuwenden, mit Abänderungen, die es gestatten, die Bedingungen hinsichtlich der Anzahl der Komprimierungen und Dekomprimierungen zu erfüllen. Sie schlägt vor, den Algorithmus anzuwenden, um nach und nach kürzeste Wege für bestimmte Anzahlen von Komprimierungen und Dekomprimierungen zu suchen. Bei dem Beispiel aus 1 beginnt man damit, die kürzesten Wege zu suchen, die keine Komprimierung aufweisen, wie symbolisch unten in 1 durch die Ebene P(0) dargestellt; anschließend sucht man die kürzesten Wege, die eine Komprimierung aufweisen, in der Ebene P(1), dann die kürzesten Wege, die zwei Komprimierungen und Dekomprimierungen aufweisen, in der Ebene P(2). Im Folgenden schreiben wir die Entfernung zwischen dem Knoten s und dem Knoten n bei einer Leitweglenkung, die höchstens v Komprimierungen und Dekomprimierungen aufweist, als &pgr;_v(s, n).

Bei der Anwendung auf den Fall der 1 wird das Verfahren folgendermaßen angewandt. Auf der Ebene P(0) betrachtet man die Leitweglenkungen, die weder Komprimierung noch Dekomprimierung aufweisen, und man berechnet so:

&pgr;₀(1, 3) = 1

&pgr;₀(1, 2) = 2

&pgr;₀(1, 4) = 3

&pgr;₀(1, 5) = 4

&pgr;₀(1, 6) = 5,

wobei die kürzesten Wege in 1 fett dargestellt sind.

Auf der Ebene P(1) betrachtet man die Leitweglenkungen, die eine Komprimierung aufweisen und man berechnet so:

&pgr;₁(1, 2) = 1, wobei man über den Leitweg zwischen 1 und 2 geht,

&pgr;₁(1, 6) = 2, wobei man über den Leitweg zwischen 1 und 2, dann über den Leitweg zwischen 2 und 6 geht, ohne an Knoten 2 zu dekomprimieren.

Auf der Ebene P(2) betrachtet man die Leitweglenkungen die zwei Komprimierungen oder Dekomprimierungen aufweisen, und man berechnet so:

&pgr;₂(1, 4) = 2, wobei man den Leitweg zwischen 1 und 2 passiert, mit einer Komprimierung und einer Dekomprimierung;

&pgr;₂(1, 5) = 3, wobei man den Leitweg zwischen 1 und 2 passiert, dann den Leitweg zwischen 2 und 6, ohne an Knoten 2 zu dekomprimieren, aber mit Dekomprimierung an Knoten 6.

Vorteilhafterweise schlägt die Erfindung vor, bei einem Schritt der Berechnung den kürzesten Weg zu verwenden, der für einen Knoten bei dem vorhergehenden Berechnungsschritt verwendet wurde. So kann man immer noch unter Bezugnahme auf die 1 bei der Berechnung in der Ebene P(1) folgendes nutzen:

• – die Tatsache, dass der Leitweg zwischen dem Knoten 1 und dem Knoten 2 eine Komprimierung impliziert, und
• – die Tatsache, dass &pgr;₀(1, 2) = 2, und dass der Leitweg zwischen dem Knoten 2 und dem Knoten 6 eine Komprimierung impliziert,
  
  wobei diese beiden Tatsachen bei der Berechnung des kürzesten Wegs in der Ebene P(0) ermittelt werden. Mit anderen Worten ist es so, dass wenn man auf der Ebene P(0) auf einem Knoten n zu einem Leitweg gelangt, auf dem eine Komprimierung möglich ist, man die Entfernung zwischen dem Quellknoten und dem Knoten n, die man in der Berechnung auf der höheren Ebene verwenden wird, schreibt als &pgr;₀(s, n). Dieses wird in 1 durch gestrichelte Linien zwischen den Ebenen P(0) und P(1) dargestellt.

So kann man in Ebene P(1) direkt &pgr;₁(1, 2) und &pgr;₁(1, 6) berechnen.

Ebenso zeigen die gestrichelten Linien zwischen den Ebenen P(1) und P(2) an, dass man die Ergebnisse, die bei den Berechnungen in der Ebene P(1) erzielt wurden, auf der Ebene P(2) verwenden kann.

Auf jeder Ebene kann man für die Berechnungen den Dijkstra-Algorithmus verwenden, oder einen analogen Algorithmus für die Berechnung des kürzesten Wegs. In diesem Fall kann man bei einer Iteration des Dijkstra-Algorithmus wenn man die Nachbarknoten testet, überprüfen, ob man die Höchstzahl an Komprimierungen beachtet. Falls dieses der Fall ist, kann man die Entfernung auf einer höheren Ebene aktualisieren.

In dem Beispiel aus 1 vermeidet man auf Ebene P(2) eine Neuberechnung der Leitweglenkung mit einer Komprimierung von Knoten 1 nach Knoten 6, indem man über Knoten 2 geht. Beim Passieren des Knotens 6 auf der Ebene P(1) hat man auf Anhieb &pgr;₂(1, 5) aktualisiert, wobei man ermittelte, dass man dekomprimieren muss, um den Leitweg zwischen 6 und 5 zu nehmen. Ebenso hat man beim Passieren von Knoten 2 in der Ebene P(1) &pgr;₂(1, 4) aktualisiert, wobei man bestimmte, dass dekomprimiert werden muss, um den Leitweg zwischen 2 und 4 zu nehmen.

Wenn man in einer Ebene keinen kürzesten Weg mehr findet, oder wenn man nicht fortfahren kann, erhöht man die bestimmte Anzahl der Komprimierungen und man gelangt somit auf eine höhere Ebene.

Diese Ausführung der Erfindung läuft darauf hinaus, nach und nach die Wege zu suchen, die eine bestimmte Anzahl von Komprimierungen und Dekomprimierungen implizieren, und bei jeder Änderung der Anzahl von Komprimierungen und Dekomprimierungen die Entfernungen in den höheren Ebenen zu aktualisieren. Der beste Weg – falls es diesen gibt – ist

Somit gelangt man zur Berechnung des besten Weges, mit einer Anzahl Komprimierungen und Dekomprimierungen, die unter der Höchstzahl NVCompMax liegt. Die Ermittlung des Wegs erfolgt durch Zurückverfolgen der Elternknoten, wobei man vom Zielknoten d ausgeht, und wobei die Anzahl der Komprimierungen und Dekomprimierungen gezählt wird.

Wenn man den Wert von v, für den das Minimum &pgr;*(s, d) erreicht wird, als h schreibt, sucht man den Vorgänger von d auf der Ebene P(h), d.h. &phgr;_h(d). Für jeglichen Knoten j auf der Leitweglenkung von s nach d, der mit k Komprimierungen und Dekomprimierungen erreicht wird, wählt man den Vorgänger von j in der Ebene P(n), mit n²k und &pgr;n(s, j) + &pgr;(j, d) = &pgr;*(s, d) wobei die Entfernung &pgr;(j, d) die Entfernung auf der optimalen Leitweglenkung ist, die bereits zwischen j und d ermittelt wurde. Es gelingt einem somit bis zum Knoten s zurück zu verfolgen. Der Wechsel der Ebene ist also ein Hinweis auf eine Änderung der Komprimierung. Dieses ermöglicht es, zu ermitteln, wann die Nachricht dekomprimiert werden muss, oder wann sie durchlaufen muss, ohne dekomprimiert zu werden.

Bei dieser Ausführungsart hat man ein privates Netz beschrieben, bei dem man am Ausgang eines Leitwegs mit Komprimierung über ein komprimiertes Signal verfügte, das unter Beibehaltung der Komprimierung weiter geleitet werden kann. Daher aktualisiert man bei den Berechnungen auf der Ebene P(v) die &pgr;_v+1(s, i). Es ist auch möglich, Leitwege zu verwalten, die zwangsläufig eine Komprimierung und eine Dekomprimierung erzeugen – was bei Leitwegen der Fall sein kann, die einen externen Multiplexer verwenden, oder einen Kompressor anderer Beschaffenheit. In diesem Fall würde man einfach die n_v+2(s, i) aktualisieren, wenn man auf einen Leitweg gelangt, der einen solchen Multiplexer benutzt, mit einem nicht komprimierten Signal. Wenn man mit einem komprimierten Signal auf einen Leitweg gelangt, der einen solchen Multiplexer verwendet, muss das Signal dekomprimiert werden, bevor es auf dem Leitweg passiert. In diesem Fall würde man &Pgr;_v+3(s, i) aktualisieren.

Die Erfindung ermöglicht es somit, verschiedene Arten von Komprimierung zu verwalten und passt sich an alle Kompatibilitätsregeln bei der Signalübertragung an.

Außerdem hat man sich bei der Ausführungsart aus 1 nur um die Komprimierungen gekümmert, und aus diesem Grund weisen die Bögen alle für die Berechnung des kürzesten Weges eine Bewertung 1 auf. Wie bei der Ausführungsart aus 2 ist es auch möglich, einen Kostenpunkt zu betrachten, der keine Stückkosten sind, beispielsweise einen Kostenpunkt, der repräsentativ ist für die Nutzung der Kapazitäten des privaten Netzes, typischerweise ein abnehmender Kostenpunkt, wenn die Anzahl der verfügbaren Kapazitäten abnimmt.

2 zeigt eine andere Ausführungsart der Erfindung. Bei dem Beispiel aus 2 hat man nicht nur das Problem der Komprimierung, sondern auch das Problem des Überlaufs hin zu einem externen Netz berücksichtigt. In diesem Fall ermöglicht es die Erfindung die Anzahl der Komprimierungen und Dekomprimierungen zu begrenzen, und auch die Anzahl der Überlaufvorgänge zu einem externen Netz hin zu begrenzen. Somit sorgt man für die Aufrechterhaltung der Dienstqualität, die Begrenzung der Dauer des Verbindungsaufbaus.

2 zeigt ein Beispiel für ein privates Netz mit vier Knoten, das vier Knoten enthält, die von 1 bis 4 nummeriert sind, und Leitwege oder Signalisierungsbögen zwischen den Knoten 1 und 2, 3 und 4, und einen Leitweg ohne Komprimierung zwischen den Knoten 2 und 3. Außerdem sind Überlaufvorgänge oder Sprünge durch ein externes Netz möglich

• – zwischen den Knoten 1 und 2, mit einer Gebühr von 1;
• – zwischen den Knoten 1 und 4, mit einer Gebühr von 3;
• – zwischen den Knoten 3 und 4, mit einer Gebühr von 1.

Bei diesem Beispiel sucht man eine Leitweglenkung zwischen dem Knoten 1 und dem Knoten 4, die höchstens eine Anzahl Überlaufvorgänge oder Sprünge NsautMax gleich zwei aufweist, und die Summe der Gebühren minimiert. Bei dem Beispiel wurde keine Komprimierung berücksichtigt, aber die Erfindung gilt auch bei Vorliegen von Komprimierung, wie es die Ausführungsart zeigt, die unter Bezugnahme auf 3 beschrieben wurde.

Intuitiv ist die Lösung eine Leitweglenkung mit einem Überlauf zwischen den Knoten 1 und 2, wobei man zwischen den Knoten 2 und 3 über das private Netz geht, und mit einem weiteren Überlauf zwischen den Knoten 3 und 4.

Zur Erzielung dieser Lösung schlägt die Erfindung vor, den Dijkstra-Algorithmus für eine Berechnung des kürzesten Weges anzuwenden, mit Abänderungen, die es erlauben, die Bedingungen hinsichtlich der Anzahl Sprünge zu erfüllen. Sie schlägt vor, den Algorithmus anzuwenden, um nach und nach kürzeste Wege für bestimmte Anzahlen von Sprüngen zu ermitteln. Bei dem Beispiel aus 1 beginnt man damit, die kürzesten Wege zu suchen, die keinen Sprung aufweisen, wie symbolisch unten in 1 durch die Ebene P(0) dargestellt; anschließend sucht man den kürzesten Weg, der höchstens einen Sprung aufweist, in der Ebene P(1), dann den kürzesten Weg, der zwei Sprünge aufweist in der Ebene P(2). Als &pgr;_v(s, n) schreiben wir im Folgenden die Gesamtgebühr, die zwischen dem Knoten s und dem Knoten n verwirkt wird, und welche unendlich ist, wenn man den Knoten nicht erreichen kann.

Bei der Anwendung auf den Fall aus der 2 wird das Verfahren folgendermaßen angewandt. Auf der Ebene P(0) betrachtet man die Leitweglenkungen ohne Sprung und man berechnet auf diese Art und Weise:

&pgr;₀(1, 2) = ∞;

&pgr;₀(1, 3) = ∞;

&pgr;₀(1, 4) = ∞; denn es ist in der Tat unmöglich, einen Knoten des Netzes ohne Überlauf zu erreichen.

Auf der Ebene P(1) betrachtet man die Leitweglenkungen, die eine Komprimierung aufweisen und man berechnet auf diese Art und Weise:

&pgr;₁(1, 2) = 1 mit Überlauf zwischen 1 und 2;

&pgr;₁(1, 3) = 1 mit Überlauf zwischen 1 und 2, dann über den Leitweg zwischen 2 und 3;

&pgr;₁(1, 4) = 3 mit Überlauf zwischen 1 und 4.

Auf der Ebene P(2) betrachtet man die Leitweglenkungen, die zwei Sprünge aufweisen und man berechnet so &Pgr;₂(1, 4) = 2 mit Überlauf zwischen 1 und 2, dann zwischen 3 und 4.

Wie weiter oben schlägt die Erfindung vor, bei einem Schritt der Berechnung den kürzesten Weg zu verwenden, der für einen Knoten beim vorhergehenden Rechenschritt verwendet wurde. So kann man unter Bezugnahme auf 2 bei der Berechnung auf der Ebene P(1) folgendes nutzen:

• – die Tatsache, dass ein Überlauf zwischen dem Knoten 1 und dem Knoten 2 möglich ist, und
• – die Tatsache, dass ein Überlauf zwischen dem Knoten 1 und dem Knoten 4 möglich ist.

Diese beiden Tatsachen werden bei der Berechnung des kürzesten Wegs auf der Ebene P(0) ermittelt, wenn man die Nachbarknoten von Knoten 1 prüft und ermittelt, dass man die Knoten 2 und 4 nur um den Preis eines Überlaufs erreichen kann. Allgemeiner gesagt: wenn man auf der Ebene P(0) zu einem Knoten n mit einem möglichen Überlauf gelangt, speichert man die Information für die Berechnung auf der höheren Ebene. Dieses wird in 1 durch eine gestrichelte Linie zwischen den Ebenen P(0) und P(1) symbolisiert. So kann man auf der Ebene P(1)&pgr;₁(1, 2) und &pgr;₁(1, 4) direkt berechnen.

Ebenso gibt die gestrichelte Linie zwischen den Ebenen P(1) und P(2) an, dass man auf der Ebene P(2) das Ergebnis verwenden kann, das bei den Berechnungen in der Ebene P(1) erzielt wurde, das heißt, dass wenn man zum Knoten 3 gelangt, man nicht über den Knoten 4 gehen kann, wegen der Bedingung betreffend die Überlaufzahl, aber dass dieser Knoten mit Überlaufvorgängen erreicht werden kann.

Für die Berechnungen kann man mutatis mutandis das Verfahren verwenden, das unter Bezugnahme auf 1 beschrieben wurde. Man kann auch vorteilhaft das Verfahren verwenden, das weiter unten unter Bezugnahme auf 3 beschrieben wird, und unter Bezugnahme auf den Anhang; der Algorithmus aus dem Anhang kann vereinfacht werden, so dass nur die Überlaufvorgänge oder nur die Komprimierungen berücksichtigt werden.

Die Erfindung wurde unter Bezugnahme auf 2 für den Fall beschrieben, dass Kosten als die Summe der Gebühren berechnet werden, die jeweils für den Überlauf verwirkt werden. Man kann eine andere Form der Berechnung der Kosten für den Überlauf betrachten und beispielsweise die Kosten, die in der Patentanmeldung beschrieben werden, die von der Anmelderin unter dem Titel „Leitweglenkung der Anrufe mit Überlaufvorgängen in einem privaten Netz" hinterlegt wurde. Diese Kosten berücksichtigen nicht nur die Gebühren, die auf Grund des Überlaufs verwirkt werden, sondern auch die Belegung der Kapazitäten im Netz: unter zwei Leitweglenkungen gibt man derjenigen den Vorzug, die die niedrigste Gebührensumme aufweist und bei gleichen Gebühren bevorzugt man diejenige Leitweglenkung, die die beste Nutzung der Kapazitäten des Netzes gewährleistet.

3 zeigt noch eine Ausführungsart der Erfindung, in einem anderen privaten Netz. In dem Beispiel aus 3 betrachtet man gleichzeitig eine Begrenzung hinsichtlich der Anzahl von Komprimierungen und Dekomprimierungen und hinsichtlich der Anzahl an Sprüngen oder Überlaufvorgängen.

Das Netz aus 3 enthält 4 Knoten, die von 1 bis 4 nummeriert sind, und Leitwege oder Bögen mit einem Multiplexer zwischen den Knoten 1 und 2, 2 und 3, 3 und 4. Wie weiter oben erläutert impliziert ein Leitweg mit Multiplexierung eine Komprimierung und eine Dekomprimierung. Zwecks Vereinfachung bei der Darstellung der Figur und auf Grund der Tatsache, dass es nicht möglich ist, eine einzige Komprimierung zu haben, zählt man nicht die Komprimierungen und die Komprimierungen, sondern die Anzahl der Durchlaufe in einem Leitweg mit einem Multiplexer; das lauft darauf hinaus, die Komprimierungen und Dekomprimierungen immer 2er-weise zu zählen: somit entspricht die Ebene P(0, 1) nicht einer Komprimierung, sondern einem Durchgang in einem Leitweg mit einem Multiplexer, das heißt in der Tat einer Komprimierung und einer Dekomprimierung.

Ein Überlauf ist möglich zwischen den Knoten 1 und 4, mit einer Gebühr von 1. Bei dem Beispiel sucht man eine Leitweglenkung zwischen dem Quellknoten 1 und dem Zielknoten 4, mit einer maximalen Anzahl von Durchgängen in einem gemultiplexten Leitweg NVcompMax von 2, und einer maximalen Anzahl von Sprüngen NSautMax von 2. Man sucht eine Leitweglenkung, welche die Kosten des Überlaufs &pgr;_h,v(s, i) minimiert, d.h. die Gesamtgebühr die auf Grund des Überlaufs verursacht wird. Intuitiv ist die Lösung eine Leitweglenkung durch direkten Überlauf zwischen den Knoten 1 und 4. Die Mindestanzahl Sprünge zwischen s und n wird geschrieben als Saut_{h ,v}(s, n).

Zur Erzielung der Lösung schlägt die Erfindung vor, den Dijkstra-Algorithmus anzuwenden, um nach und nach kürzeste Wege für eine bestimmte Anzahl v von Durchgangen in einem gemultiplexten Leitweg zum einen und eine bestimmte Anzahl h von Sprangen zum anderen zu suchen. Bei dem Beispiel aus 1 beginnt man damit, die kürzesten Wege zu suchen, die keine Komprimierung (v = 0) und keinen Sprung (h = 0) aufweisen, wie symbolisch unten in 1 durch die Ebene P(h = 0, v = 0) dargestellt; anschließend sucht man die kürzesten Wege, die eine Komprimierung und keinen Sprung aufweisen in der Ebene P(0, 1), dann die kürzesten Wege, die zwei Komprimierungen und Dekomprimierungen und keinen Sprung aufweisen in der Ebene P(0, 2). Schließlich sucht man die Wege mit einem Sprung und keiner Komprimierung auf der Ebene P(1, 0), was es ermöglicht, eine Lösung zu erzielen. Wie bei 2 schreibt man das Paar, das gebildet wird aus der Anzahl der Sprünge und der Gesamtgebühr, die verwirkt wird zwischen dem Knoten s und dem Knoten n in einer Leitweglenkung, die v Komprimierungen und Dekomprimierungen und h Sprünge aufweist als &pgr;_{h ,v}(s, n).

In der Ebene P(0, 0) betrachtet man die Leitweglenkungen, die weder Komprimierungen noch Sprünge aufweisen und man ermittelt, dass keine Leitweglenkung ohne Komprimierung und ohne Überlauf vorhanden ist. Durch Testen der Nachbarn von Knoten 1 ermittelt man, dass man den Knoten 2 mit einer Komprimierung erreichen kann und dass man den Knoten 4 mit einem Sprung erreichen kann. Das führt dazu, die Entfernungen in den Ebenen P(0, 1) und P(1, 0) zu aktualisieren, wie mit gestrichelten Linien auf der Figur dargestellt.

In der Ebene P(0, 1) betrachtet man die Leitweglenkungen mit einer Komprimierung und ohne Sprung und man ermittelt dass &pgr;_0,1(P(1, 2) den Wert 0 hat und dass man keine anderen Knoten erreichen kann. Bei Prüfung der Nachbarn von Knoten 2 stellt man fest, dass man den Knoten 3 mit 2 Komprimierungen erreichen kann, und man aktualisiert die entsprechende Entfernung auf der Ebene P(0, 2), wie durch die gestrichelte Linie zwischen den Ebenen P(0, 1) und P(0, 2) dargestellt.

In der Ebene P(0, 2) betrachtet man die Leitweglenkungen mit zwei Komprimierungen und ohne Überlauf. Man stellt fest, dass &pgr;_0,2(1, 3) den Wert 0 hat und dass man den Knoten 4 nicht erreichen kann.

In der Ebene P(1, 0) ermittelt man, dass man den Knoten 4 mit einem Überlauf erreichen kann und dass &pgr;_1,0(1, 4) den Wert 1 hat.

Bei diesem Beispiel versucht man, die Anzahl der Sprünge zu minimieren und man hört auf, sobald man den Zielknoten in einer Ebene erreicht hat. Wenn man den Zielknoten für einen bestimmten Wert h₀ der Anzahl der Sprünge erreicht, kann man auch die Berechnungen betreffend die verschiedenen möglichen Werte von v fortführen und den Weg betrachten, der eine minimale Entfernung für alle möglichen Werte v mit h² h₀ hat.

Die Anlage am Ende der vorliegenden Beschreibung zeigt eine Art und Weise für das Rechenvorgehen für ein Netz des Typs aus 3. Bei dieser Ausführungsart der Erfindung nimmt man erneut Berechnungen der kürzesten Wege in jeder Ebene vor, wobei der Dijkstra-Algorithmus angewandt wird.

In dem Beispiel aus dem Anhang tastet man die Werte der Anzahl von Sprüngen h bei NSautMax ab und für jeden Wert scannt man die Werte der Anzahl v an Komprimierungen und Dekomprimierungen von 0 bis NVCompmax. So nimmt man nach und nach die Berechnung in jeder Ebene P(h, v) vor.

Bei jeder Ebene beginnt man mit einer Initialisierung. Wenn h und v Null sind, anders ausgedrückt in der Ebene P(0, 0) initialisiert man folgendermaßen: für alle Knoten außer dem Quellknoten, initialisiert man &pgr;_{h ,v}(s, n) unendlich; für jeglichen Knoten des Netzes ist &phgr;_h,v(n) in der Ebene P(h, v) NULL; das heißt kein Knoten hat einen Vorgänger im Baum der kürzesten Wege. Für h = 0 und v = 0 bei den Nachbarknoten von s initialisiert man &pgr;_0,0(s, n) mit dem entsprechenden Wert der Funktion LireCoût (LesenKosten); diese Funktion veranschlagt die Durchgangskosten zwischen zwei benachbarten Knoten auf dem Leitweg, der sie verbindet, oder auf einem Überlaufbogen, der sie verbindet.

Dann setzt man in S alle Knoten n ein, die nicht die Quelle sind, mit einer Entfernung &pgr;_0,0(s, n). Dann nimmt man eine Kohärenzprüfung vor, indem man die Formel VerifCohérence (1(s, n), h = 0, v = 0, s, n) anwendet. [VerifCohérence = ÜberprüfenKohärenz]. Diese Funktion prüft die Kompatibilität der Qualitäten in der aktuellen Ebene und bereitet die Kosten vor für die folgende Ebene. In der Ebene P(0, 0) überprüft diese Funktion die Kohärenz zwischen s und n, d.h. überprüft, dass eine Leitweglenkung zwischen s und n möglich ist.

Für Werte h und v, die nicht alle beide null sind, d.h. in anderen Ebenen als P(0, 0) nimmt man die Initialisierung folgendermaßen vor: man leert die Menge S und setzt dort die Punkte ein, bei denen die Anzahl Sprünge größer oder gleich dem aktuellen Wert von h ist. Dieses entspricht dem folgenden Vorgehen:

• – falls ein Knoten n bereits mit einer Anzahl Sprünge kleiner als h erreicht wird, das heißt, wenn es einen Weg zwischen dem Quellknoten s und dem Knoten n in weniger als h Sprüngen gibt, darf der Knoten nicht dem Quellknoten angenähert werden, indem man über einen Knoten mit einer Anzahl Sprünge größer oder gleich h läuft. Es ist also nicht erforderlich, den Knoten n in S zu setzen. Dieses entspricht der Optimierungswahl bei dieser Ausführungsart der Erfindung, bei der man die Anzahl der Überlaufvorgänge minimiert, selbst um den Preis einer zusätzlichen Komprimierung.
• – falls der Knoten n bereits mit einer Anzahl Sprünge gleich h erreicht wird, das heißt, wenn es einen Weg zwischen dem Quellknoten s und dem Knoten n mit h Sprüngen gibt, kann der Knoten n als Transit dienen, um andere Knoten mit h Sprüngen zu erreichen; er kann sich auch der Wurzel nähern, mittels einer zusätzlichen Komprimierung oder Dekomprimierung; man setzt also den Knoten n in S ein;
• – falls der Knoten n bereits mit einer Anzahl Sprünge größer h erreicht wird, das heißt, wenn es einen Weg zwischen dem Quellknoten s und dem Knoten n mit mehr als h Sprüngen gibt, oder wenn es keinen Weg zwischen s und n gibt, kann der Knoten n dem Quellknoten angenähert werden; man setzt ihn dann in S ein.

Man hat dann in S nach der Initialisierung in der Ebene P(h, v) die Menge der Knoten, die noch nicht erreicht werden oder die durch Leitweglenkungen mit h Sprüngen oder mehr erreicht werden.

Nach der Initialisierung nimmt man die Berechnung der Wege in der Ebene P(h, v) vor. In jeder Ebene nimmt man eine Berechnung durch Anwendung des Dijkstra-Algorithmus vor, wobei die Werte von &Pgr;_h,v in den höheren Ebenen aktualisiert werden, wenn man nicht mehr unter Einhaltung der Bedingungen hinsichtlich h und v weitergehen kann.

Man betrachtet also den Knoten n aus S, der die Gebühr &pgr;_{h , v}(s, i) minimiert. Dann geht man wie beim Dijkstra-Algorithmus vor; wenn man die Nachbarn von n betrachtet, überprüft man jedoch, ob man komprimieren muss, um zum Punkt n zu gelangen, oder ob man dekomprimieren muss, wie beim Beispiel aus 1. Auf entsprechende Art und Weise aktualisiert man die Entfernungswerte in der Ebene P(h, v + 1).

Wenn ein Punkt in der Nachbarschaft nur durch einen Überlauf erreicht werden kann, aktualisiert man den entsprechenden Entfernungswert in der Ebene P(h + 1, v). In dieser Ebene überprüft man wie vorstehend, ob man komprimieren oder dekomprimieren muss; die Bedingungen für Komprimierung und Dekomprimierung können nämlich auch auf einen Überlaufbogen Anwendung finden.

Bei einer Ausführungsart ist es so, dass wenn ein Leitweg ohne Komprimierung vorhanden ist, welche dem Überlauf zugrunde liegt, man den Überlauf nur dann gestattet, wenn der Leitweg gesättigt ist. Das läuft darauf hinaus, die Kapazitäten des privaten Netzes zu optimieren, bevor der Überlauf genehmigt wird; man könnte ein ähnliches Ergebnis mit einer Entfernung n erzielen, die die Nutzung der Kapazitäten des Netzes berücksichtigt, wie in der vorgenannten Patentanmeldung der Anmelderin erläutert.

Nach dem Durchlaufen der verschiedenen Ebenen, zumindest so lange bis man eine Leitweglenkung findet, die zum Zielknoten gelangt, begegnet man der Leitweglenkung wieder wie unter Bezugnahme auf 1 erläutert.

Bei dem Beispiel aus 3 gibt man der Begrenzung der Überlaufgebühren den Vorzug vor der Anzahl von Komprimierungen und Dekomprimierungen. Dieses schlägt sich nieder im Durchlaufen der Berechnungsebenen – wobei man damit beginnt, die Bedingung hinsichtlich der Anzahl von Komprimierungen und Dekomprimierungen zu sättigen, bevor ein Sprung ins Auge gefasst wird. Natürlich funktioniert die Erfindung auch im gegenteiligen Fall, oder allgemeiner gesprochen bei jeglichem beliebigen Abtasten der verschiedenen möglichen Ebenen. Mit den weiter oben verwendeten Schreibweisen h und v geht es gemäß der Erfindung darum, die Paare (h, v) mit h² NVCompmax und v² NSautMax zu scannen. Man kann wie bei der Beschreibung vorgehen, indem man die Werte von v bei konstantem h abtastet, und dann h erhöht; man könnte auch die Werte von h bei konstantem v abtasten, und dann v erhöhen. Man könnte auch Berechnungen mit h + v konstant vornehmen, oder jegliche sonstige Lösung. Insbesondere die Anwendung des Algorithmus aus der Anlage mit v = 0 liefert eine Lösung für die Berechnung der 1.

Die Erfindung ist nicht auf die beschriebenen Ausführungsarten beschränkt; sie gilt ganz allgemein in jedwedem privaten Netz für die Leitweglenkungsberechnung, die eine oder mehrere Gebühren minimiert, wobei eine oder mehrere Bedingungen hinsichtlich eines Höchstwertes erfüllt werden; im Beispiel aus 1 minimiert man die Entfernung ausgedrückt in Anzahl der Leitwege und die Bedingung ist eine Bedingung betreffend die Zahl der Komprimierungen und Dekomprimierungen. Bei dem Beispiel aus 2 minimiert man Überlaufkosten und die Bedingung ist eine Bedingung betreffend die Anzahl von Sprüngen. Bei dem Beispiel aus 3 versucht man die Überlaufgebühren zu minimieren und die Bedingungen betreffend die Anzahl an Komprimierungen und Dekomprimierungen und betreffend die Anzahl der Überlaufvorgänge zu erfüllen. Man kann die Erfindung auch auf verschiedene Bedingungen und auf unterschiedliche Kostenfunktionen anwenden.

Man könnte auch den Schritt Bestimmung der Mindestzahl von Komprimierungen und Dekomprimierungen nicht einsetzen; das hätte nur eine gegebenenfalls längere Berechnung zur Folge und ein unnützes Scannen von nicht zufrieden stellenden Lösungen.

Bei den bevorzugten Ausführungsarten hat man die Anzahl an Komprimierungen und Dekomprimierungen gezählt. Es ist klar, dass man auch nur die Anzahl der Komprimierungen zählen kann, oder lediglich die Zahl der Dekomprimierungen, um vergleichbar die Gesamtzahl von Komprimierungen und Dekomprimierungen zu begrenzen. Dieses beruht auf der allgemein anwendbaren Regel, dass eine Dekomprimierung zwangsläufig auf eine vorherige Komprimierung folgt. Festzuhalten ist, dass diese Regel nicht immer gilt, wenn man mehrere Arten von Komprimierungen vorsieht.

Die Erfindung gilt auch für Netzarten, die sich von denjenigen unterscheiden, die in den bevorzugten Ausführungsarten beschrieben werden.

Schließlich wird in der Beschreibung und in den Ansprüchen der Dijkstra-Algorithmus genannt. Es versteht sich, dass dieser Begriff nicht nur die Version des Algorithmus des kürzesten Wegs abdeckt, die von Dijkstra vorgeschlagen wird, sondern auch die diesem nahe kommenden Versionen und insbesondere den Bellman-Algorithmus oder den Floyd-Algorithmus. Festzuhalten ist, dass der Bellman-Algorithmus nur für Graphen ohne Kreise gilt.