HK1075769B - Load balancing techniques for inter-domain traffic engineering - Google Patents

Claims (7)

1. Verfahren zum Ausgleichen des Verkehrs auf Pfaden, die ein Netz mit dem Internet verbinden, umfassend:

   Bilden einer Verbindung zwischen einem Heimnetz und einem anderen Netz, welches mit einer Mehrzahl von Netzen verbunden ist, wobei die Verbindung eine Mehrzahl von Pfaden (p) umfasst, die den Verkehr in Form von Datenpaketen zwischen dem Heimatnetz und dem anderen Netz führen, wobei jeder Pfad eine Pfadlast (x_i), welche die einem Pfad (p) zugewiesene Verkehrsmenge darstellt, eine verfügbare Kapazität (c_i), welche die auf dem Pfad (p) übertragbare Verkehrsmenge darstellt, sowie eine niedrige Kapazitätsgrenze (l_i) und eine hohe Kapazitätsgrenze (h_i) aufweist, die die gemessenen hohen und niedrigen Kapazitätsgrenzwerte der verfügbaren Kapazität (c_i) darstellen;

   Messen der Pfadlast (x_i) jedes der Mehrzahl von Pfaden (p);

   Messen der hohen Kapazitätsgrenze (h_i(0)) jedes der Mehrzahl von Pfaden (p);

   Vergleichen der Pfadlast (x_i) und der hohen Kapazitätsgrenze (h_i (0)) für jeden der Mehrzahl von Pfaden (p);

   Auswählen eines der Mehrzahl von Pfaden (p), wobei die Mehrzahl von Pfaden (p) den ausgewählten Pfad (p₀) und andere Pfade (p_i) umfasst, wobei der ausgewählte Pfad (p₀) eine anfängliche Überlast (x₀(0)) aufweist, und wobei die Überlast vorhanden ist, wenn die Last (x₀(0)) des anfänglichen ausgewählten Pfades größer als die hohe Kapazitätsgrenze (h₀(0)) des anfänglichen ausgewählten Pfades ist; und

   Wählen der Pfadlast (x;) für jeden der Mehrzahl von anderen Pfaden (p_i) unter Einsatz einer partiellen Zuweisungsstrategie, wobei die partielle Zuweisungsstrategie umfasst:

   a) Indexieren der anderen Pfade (p;) mit i, wobei i ein Satz von Ganzzahlen 1 bis P ist, wobei P die Gesamtzahl der anderen Pfade (p_i) ist;

   b) Verknüpfen einer Mehrzahl von Ping-Intervallen mit einem Zähler (t), wobei der anfängliche Wert des Zählers auf Null (0) gesetzt wird und insgesamt N Ping-Intervalle vorhanden sind;

   c) Berechnen eines Teils (y(t)) der abzuladenden und auf andere Pfade (p_i) zu verteilenden Überlast (x₀(0)) des anfänglichen ausgewählten Pfades, wobei eine halbierende Suchstrategie zum Einsatz kommt, und zu Schritt (f) gesprungen wird;

   d) Berechnen der Last eines aktualisierten ausgewählten Pfads (x₀(t)), wobei die Last des ausgewählten aktualisierten Pfads (x₀(t)) gleich der Überlast (x₀(0)) des anfänglichen ausgewählten Pfades minus der Summe der niedrigen Kapazitätsgrenze für den/die i Pfade ist;

   e) Berechnen des Anteils (y(t)) der Last des aktualisierten ausgewählten Pfads (x₀(t)), der auf andere Pfade (p_i) abzuladen und zu verteilen ist, unter Einsatz einer halbierenden Suchstrategie;

   f) Messen der niedrigen Kapazitätsgrenze (l_i) und der hohen Kapazitätsgrenze (h_i) der anderen Pfade (p_i) am Ping-Interval (t);

   g) Verteilen des Anteils der ausgewählten Pfadüberlast oder der aktualisierten ausgewählten Pfadlast (x₀(t)) auf die anderen Pfade (p_i), wobei der Anteil des Verkehrs (y(t)) auf die anderen Pfade (p_i) mittels folgender Gleichung verteilt wird: $x_i=l_i\left(t\right)+\frac{h_i\left(t\right)-l_i\left(t\right)}{\sum _{i=1}^P\left(h_i,\left(t\right),-,l_i,\left(t\right)\right)}\left(y,\left(t\right)\right)$ und

   h) Anhalten, wenn keine weiteren Ping-Intervalle (t = N) vorhanden sind, andernfalls Erhöhen des nummerischen Wertes des Zählers um eins (I) und Fortfahren mit Schritt (d).
2. Verfahren zum Ausgleichen des Verkehrs auf Pfaden, die ein Netz mit dem Internet verbinden, nach Anspruch 1, wobei die halbierende Suchstrategie den Anteil (y(t)) des abzuladenden und zu verteilenden Verkehrs unter Einsatz folgender Gleichung wählt: $y\left(t\right)=\min \left\{\left(0.5\right)\left[\sum _{i=1}^P\left(h_i,\left(t\right),-,l_i,\left(t\right)\right)\right],(x_0\left(t,)\right)\right\}\mathrm{.}$
3. Verfahren zum Ausgleichen des Verkehrs auf Pfaden, die ein Netz mit dem Internet verbinden, nach Anspruch 1 oder 2, wobei die Menge des Verkehrs vom Heimatnetz zum großen Netz über den ausgewählten Pfad (p₀) mit Hilfe von Flußmengen-Messungen oder SNMP (Simple Network Management Protocol) gemessen wird.
4. Verfahren zum Ausgleichen des Verkehrs auf Pfaden, die ein Netz mit dem Internet verbinden, nach Anspruch 1, 2 oder 3, wobei die hohe Kapazitätsgrenze (h₀(0)) des anfänglichen ausgewählten Pfades mit Hilfe von aktiven Sensoren oder passiven Messungen der Verkehrsdetails gemessen wird.
5. Verfahren zum Ausgleichen des Verkehrs auf Pfaden, die ein Netz mit dem Internet verbinden, nach Anspruch 1 bis 4, wobei die hohe Kapazitätsgrenze (h₀(0)) des anfänglichen ausgewählten Pfades mit Hilfe der TCP (Transmission Control Protocol) SYN/ACK (Synchronize Acknowledgement) Antwortzeit gemessen wird.
6. Verfahren zum Ausgleichen des Verkehrs auf Pfaden, die ein Netz mit dem Internet verbinden, nach Anspruch 1 bis 5, wobei die hohe Kapazitätsgrenze (h₀(0)) des anfänglichen ausgewählten Pfades mit Hilfe von RTT (Round Trip Time) und Verlustmessungen gemessen wird.
7. Verfahren zum Ausgleichen des Verkehrs auf Pfaden, die ein Netz mit dem Internet verbinden, nach einem der vorhergehenden Ansprüche, wobei die niedrige Kapazitätsgrenze des anfänglichen ausgewählten Pfades gleich Null ist und die hohe Kapazitätsgrenze (h₀(0)) des anfänglichen ausgewählten Pfades gleich Eins ist.