Selbstähnlicher Prozess – Wikipedia

Selbstähnliche Prozesse sind Arten von stochastischen Prozessen, die das Phänomen der Selbstähnlichkeit aufweisen. Ein selbstähnliches Phänomen verhält sich bei Betrachtung mit unterschiedlichen Vergrößerungsgraden oder unterschiedlichen Maßstäben in einer Dimension (Raum oder Zeit) gleich. Selbstähnliche Prozesse können manchmal mit Schwerschwanzverteilungen beschrieben werden, die auch als Langschwanzverteilungen bezeichnet werden. Beispiele für solche Prozesse umfassen Verkehrsprozesse, wie z. B. Paketankunftszeiten und Burstlängen. Selbstähnliche Prozesse können eine langfristige Abhängigkeit aufweisen.

Überblick[edit]

Das Design robuster und zuverlässiger Netzwerke und Netzwerkdienste ist in der heutigen Internetwelt zu einer zunehmend herausfordernden Aufgabe geworden. Um dieses Ziel zu erreichen, spielt das Verständnis der Merkmale des Internetverkehrs eine immer wichtigere Rolle. Empirische Studien gemessener Verkehrsspuren haben dazu geführt, dass die Selbstähnlichkeit im Netzwerkverkehr weitgehend erkannt wurde.^[1]

Selbstähnlicher Ethernet-Verkehr weist Abhängigkeiten über einen langen Bereich von Zeitskalen auf. Dies steht im Gegensatz zum Telefonverkehr, der Poisson bei seiner Ankunft und Abreise darstellt.^[2]

Im traditionellen Poisson-Verkehr würden sich die kurzfristigen Schwankungen mitteln, und ein Diagramm, das eine große Zeitspanne abdeckt, würde sich einem konstanten Wert nähern.

Schwerschwanzverteilungen wurden in vielen natürlichen Phänomenen beobachtet, einschließlich physikalischer und soziologischer Phänomene. Mandelbrot etablierte die Verwendung von Verteilungen mit schwerem Schwanz, um reale fraktale Phänomene zu modellieren, z. B. Aktienmärkte, Erdbeben, Klima und Wetter.^{[citation needed]}

Der Datenverkehr für Ethernet, WWW, SS7, TCP, FTP, TELNET und VBR (digitalisiertes Video des Typs, der über ATM-Netzwerke übertragen wird) ist selbstähnlich.

Selbstähnlichkeit in paketierten Datennetzen kann durch die Verteilung von Dateigrößen, menschlichen Interaktionen und / oder Ethernet-Dynamik verursacht werden. Selbstähnliche und weitreichende abhängige Merkmale in Computernetzwerken stellen Personen, die Analysen und / oder das Design von Netzwerken durchführen, vor grundlegend andere Probleme, und viele der vorherigen Annahmen, auf denen Systeme aufgebaut wurden, sind in Gegenwart von nicht mehr gültig Selbstähnlichkeit.^[3]

Die Poisson-Verteilung[edit]

Bevor die Heavy-Tailed-Verteilung mathematisch eingeführt wird, wird im Folgenden kurz auf den Poisson-Prozess mit einer memorylosen Wartezeitverteilung eingegangen, mit dem (unter anderem) traditionelle Telefonnetzwerke modelliert werden.

Die Annahme von reinen Zufallsankünften und reinen Zufallsbeendigungen führt zu Folgendem:

• Die Anzahl der Anrufankünfte in einer bestimmten Zeit hat eine Poisson-Verteilung, dh:

${ displaystyle P (a) = left ({ frac { mu ^ {a}} {a!}} right) e ^ {- mu},}$

wo ein ist die Anzahl der eingehenden Anrufe T., und

${ displaystyle mu}$

ist die durchschnittliche Anzahl der eingehenden Anrufe T.. Aus diesem Grund wird reiner Zufallsverkehr auch als Poisson-Verkehr bezeichnet.

• Die Anzahl der Anrufabgänge in einer bestimmten Zeit hat auch eine Poisson-Verteilung, dh:

${ displaystyle P (d) = left ({ frac { lambda ^ {d}} {d!}} right) e ^ {- lambda},}$

wo d ist die Anzahl der Anrufabgänge in der Zeit T. und

${ displaystyle lambda}$

ist die durchschnittliche Anzahl der Anrufabgänge in der Zeit T..

• Die Intervalle, T.Zwischen Anrufankünften und -abgängen liegen Intervalle zwischen unabhängigen, identisch verteilten Zufallsereignissen. Es kann gezeigt werden, dass diese Intervalle eine negative Exponentialverteilung haben, dh:

${ displaystyle P.[Tgeq t]= e ^ {- t / h}, ,}$

wo h ist die mittlere Haltezeit (MHT).^{[citation needed]}

Die Schwerschwanzverteilung[edit]

Eine Distribution soll einen schweren Schwanz haben, wenn

${ displaystyle lim _ {x to infty} e ^ { lambda x} Pr[X>x]= infty quad { mbox {für alle}} lambda> 0. ,}$

Modellierung des selbstähnlichen Verkehrs[edit]

Da (im Gegensatz zum herkömmlichen Telefonieverkehr) paketierter Verkehr selbstähnliche oder fraktale Eigenschaften aufweist, gelten herkömmliche Verkehrsmodelle nicht für Netzwerke, die selbstähnlichen Verkehr führen.^{[citation needed]}

Mit der Konvergenz von Sprache und Daten wird das zukünftige Multi-Service-Netzwerk auf paketiertem Verkehr basieren, und Modelle, die die Art des selbstähnlichen Verkehrs genau widerspiegeln, werden erforderlich sein, um zukünftige Multi-Service-Netzwerke zu entwickeln, zu entwerfen und zu dimensionieren.^{[citation needed]}

Frühere analytische Arbeiten, die in Internetstudien durchgeführt wurden, gingen von Annahmen wie exponentiell verteilten Paket-Zwischenankünften aus, und Schlussfolgerungen, die unter solchen Annahmen gezogen wurden, können bei Vorhandensein von Verteilungen mit starkem Schwanz irreführend oder falsch sein.^[2]

Das Ableiten mathematischer Modelle, die den weitreichungsabhängigen Verkehr genau darstellen, ist ein fruchtbares Forschungsgebiet.

Leland et al haben einen mathematischen Formalismus zur Beschreibung selbstähnlicher stochastischer Prozesse bereitgestellt.^[4] Für die Zahlenfolge

${ displaystyle Y = (Y_ {i}: i = 0,1,2, …, N)}$

mit gemein

${ displaystyle { hat { mu}} = { text {E}} (Y_ {i})}$

,

Abweichungen

${ displaystyle y_ {i} = Y_ {i} – { hat { mu}}}$

,

Varianz

${ displaystyle { hat { sigma}} ^ {2} = { text {E}} (y_ {i} ^ {2})}$

,

und Autokorrelationsfunktion

${ displaystyle r (k) = { text {E}} (y_ {i}, y_ {i + k}) / { text {E}} (y_ {i} ^ {2})}$

mit Verzögerung k, wenn die Autokorrelation dieser Sequenz das Fernverhalten aufweist

${ displaystyle r (k) sim k ^ {- d} L (k)}$

wie k→ ∞ und wo L (k) ist eine sich langsam ändernde Funktion bei großen Werten von kwird diese Sequenz a genannt selbstähnlicher Prozess.

Das Methode zum Erweitern von Behältern kann verwendet werden, um selbstähnliche Prozesse zu analysieren. Stellen Sie sich eine Reihe gleich großer, nicht überlappender Bins vor, die die ursprüngliche Sequenz von teilen N. Elemente in Gruppen von m gleich große Segmente (N / m ist eine ganze Zahl), so dass neue Fortpflanzungssequenzen basierend auf den Mittelwerten definiert werden können:

${ displaystyle Y_ {i} ^ {(m)} = (Y_ {im-m + 1} + … + Y_ {im}) / m}$

.

Die aus dieser Sequenz ermittelte Varianz wird skaliert, wenn sich die Behältergröße so ändert, dass

${ displaystyle { text {var}}[Y^{(m)}]= { hat { sigma}} ^ {2} m ^ {- d}}$

genau dann, wenn die Autokorrelation die einschränkende Form hat^[5]

${ displaystyle lim _ {k to infty} r (k) / k ^ {- d} = (2-d) (1-d) / 2}$

.

Man kann auch einen Satz entsprechender additiver Sequenzen konstruieren

${ displaystyle Z_ {i} ^ {(m)} = mY_ {i} ^ {(m)}}$

,

basierend auf den expandierenden Behältern,

${ displaystyle Z_ {i} ^ {(m)} = (Y_ {im-m + 1} + … + Y_ {im})}$

.

Vorausgesetzt, die Autokorrelationsfunktion zeigt dasselbe Verhalten, folgen die additiven Sequenzen der Beziehung

${ displaystyle { text {var}}[Z_{i}^{(m)}]= m ^ {2} { text {var}}[Y^{(m)}]= ({ hat { sigma}} ^ {2} / { hat { mu}} ^ {2-d}) { text {E}}[Z_{i}^{(m)}]^ {2-d}}$

Schon seit

${ displaystyle { hat { mu}}}$

und

${ displaystyle { hat { sigma}} ^ {2}}$

sind Konstanten diese Beziehung bildet a Varianz-zu-Mittelwert-Potenzgesetz (Taylors Gesetz), mit p= 2-d.^[6]

Tweedie-Distributionen sind ein Sonderfall von Exponentialdispersionsmodellen, eine Klasse von Modellen, die zur Beschreibung von Fehlerverteilungen für das verallgemeinerte lineare Modell verwendet werden.^[7]

Diese Tweedie-Verteilungen sind durch eine inhärente Skaleninvarianz und damit für jede Zufallsvariable gekennzeichnet Y. das gehorcht einer Tweedie-Verteilung, der Varianz var (Y.) bezieht sich auf den Mittelwert E (Y.) nach dem Machtgesetz,

${ displaystyle { text {var}} , (Y) = a[{text{E}},(Y)]^ {p},}$

wo ein und p sind positive Konstanten. Der Exponent p Die Varianz zum mittleren Potenzgesetz, das mit bestimmten selbstähnlichen stochastischen Prozessen verbunden ist, liegt zwischen 1 und 2 und kann daher teilweise durch eine Tweedie-Verbindung der Poisson-Gamma-Verteilung modelliert werden.^[6]

Die additive Form des Poisson-Gamma-Modells der Tweedie-Verbindung hat die kumulierende Erzeugungsfunktion (CGF).

${ displaystyle K_ {p} ^ {*} (s; theta, lambda) = lambda kappa _ {p} ( theta)[(1+s/theta )^{alpha }-1]}}$

,

wo

${ displaystyle kappa _ {p} ( theta) = { dfrac { alpha -1} { alpha}} left ({ dfrac { theta} { alpha -1}} right) ^ { alpha}}$

,

ist die kumulative Funktion, α ist der Tweedie-Exponent

${ displaystyle alpha = { dfrac {p-2} {p-1}}}$

,

s ist die generierende Funktionsvariable, θ ist der kanonische Parameter und λ ist der Indexparameter.

Die erste und zweite Ableitung der CGF mit s = 0ergibt den Mittelwert bzw. die Varianz. Man kann somit bestätigen, dass sich die Varianz für die additiven Modelle auf den Mittelwert durch das Potenzgesetz bezieht,

${ displaystyle mathrm {var} (Z) propto mathrm {E} (Z) ^ {p}}$

.

Während diese Tweedie-Verbindung Poisson-Gamma-CGF die Wahrscheinlichkeitsdichtefunktion für bestimmte selbstähnliche stochastische Prozesse darstellt, gibt sie keine Informationen über die der Sequenz inhärenten Fernkorrelationen zurück Y..

Nichtsdestotrotz bieten die Tweedie-Verteilungen ein Mittel, um die möglichen Ursprünge selbstähnlicher stochastischer Prozesse aufgrund ihrer Rolle als Brennpunkte für einen zentralen grenzenartigen Konvergenzeffekt zu verstehen, der als Tweedie-Konvergenzsatz bekannt ist. In nichttechnischen Begriffen sagt uns dieser Satz, dass jedes exponentielle Dispersionsmodell, das asymptotisch ein Varianz-Mittelwert-Potenzgesetz manifestiert, eine Varianzfunktion haben muss, die in den Bereich der Anziehung eines Tweedie-Modells fällt.

Der Tweedie-Konvergenzsatz kann verwendet werden, um den Ursprung der Varianz zum mittleren Potenzgesetz zu erklären. 1 / f Rauschen und Multifraktalität, Merkmale, die mit selbstähnlichen Prozessen verbunden sind.^[6]

Netzwerkleistung[edit]

Die Netzwerkleistung nimmt mit zunehmender Selbstähnlichkeit allmählich ab. Je ähnlicher der Verkehr ist, desto länger ist die Warteschlange. Die Warteschlangenlängenverteilung des selbstähnlichen Verkehrs nimmt langsamer ab als bei Poisson-Quellen. Die Abhängigkeit von großer Reichweite impliziert jedoch nichts über die kurzfristigen Korrelationen, die die Leistung in kleinen Puffern beeinflussen. Darüber hinaus verstärkt das Aggregieren von Strömen von selbstähnlichem Verkehr typischerweise die Selbstähnlichkeit (“Burstiness”) anstatt es zu glätten, was das Problem verschärft.^{[citation needed]}

Selbstähnlicher Datenverkehr weist die Persistenz von Clustering auf, was sich negativ auf die Netzwerkleistung auswirkt.

• Beim Poisson-Verkehr (in herkömmlichen Telefonienetzen) kommt es kurzfristig zu Clustering, das sich jedoch langfristig glättet.
• Bei selbstähnlichem Verkehr kann das Burst-Verhalten selbst Burst sein, was die Clustering-Phänomene verschärft und die Netzwerkleistung verschlechtert.

Viele Aspekte der Netzwerkqualität hängen von der Bewältigung von Verkehrsspitzen ab, die zu Netzwerkfehlern führen können, z

• Zellen- / Paketverlust und Warteschlangenüberlauf
• Verletzung von Verzögerungsgrenzen zB im Video
• Schlimmste Fälle beim statistischen Multiplexing

Poisson-Prozesse verhalten sich gut, weil sie zustandslos sind und die Spitzenbelastung nicht aufrechterhalten wird, sodass sich die Warteschlangen nicht füllen. Bei Fernordnung halten Peaks länger an und haben größere Auswirkungen: Das Gleichgewicht verschiebt sich für eine Weile.^[8]

Siehe auch[edit]

Verweise[edit]

1. ^ Park, Kihong; Willinger, Walter (2000), Selbstähnliche Bewertung des Netzwerkverkehrs und der Leistung, New York, NY, USA: John Wiley & Sons, Inc., ISBN 0471319740.
2. ^ ^{ein b} “Anhang: Heavy-Tailed-Distributionen”. Cs.bu.edu. 2001-04-12. Abgerufen 2012-06-25.
3. ^ “Die Website zur Selbstähnlichkeit und Fernabhängigkeit in Netzwerken”. Cs.bu.edu. Abgerufen 2012-06-25.
4. ^ Leland, WIR; Leland, WIR; MS Taqqu; W. Willinger; DV Wilson (1994). “Über die Selbstähnlichkeit des Ethernet-Verkehrs”. IEEE / ACM Trans. Netw. 2: 1–15. doi:10.1109 / 90.282603. S2CID 6011907.
5. ^ Tsybakov B & Georganas ND (1997) Zum selbstähnlichen Verkehr in Geldautomatenwarteschlangen: Definitionen, gebundene Überlaufwahrscheinlichkeit und Verteilung der Zellenverzögerung. IEEE / ACM Trans. Netw. 5, 397–409
6. ^ ^{ein b c} Kendal, Wayne S.; Jørgensen, Bent (27.12.2011). “Tweedie-Konvergenz: Eine mathematische Grundlage für Taylors Potenzgesetz, 1 / f-Rauschen und Multifraktalität”. Körperliche Überprüfung E.. Amerikanische Physikalische Gesellschaft (APS). 84 (6): 066120. doi:10.1103 / physreve.84.066120. ISSN 1539-3755. PMID 22304168.
7. ^ Jørgensen, Bent (1997). Die Theorie der Dispersionsmodelle. Chapman & Hall. ISBN 978-0412997112.
8. ^ “Alles, was Sie schon immer über selbstähnlichen Netzwerkverkehr und Fernabhängigkeit wissen wollten, sich aber schämten zu fragen *”. Cs.kent.ac.uk. Abgerufen 2012-06-25.

Externe Links[edit]