Warteschlangennetzwerke

Ein Warteschlangennetzwerk verbindet mehrere Servicestationen so, dass Kunden, die eine Station verlassen, zu einer anderen weitergeleitet werden; bemerkenswerterweise weisen viele solcher Netzwerke ein Produktform-Gleichgewicht auf, das sich über die Stationen faktorisieren lässt.

Definition

Ein Warteschlangennetzwerk ist eine Sammlung miteinander verbundener Servicestationen, durch die sich Kunden gemäß Routing-Wahrscheinlichkeiten bewegen, und seine Analyse zielt auf die gemeinsame stationäre Verteilung der Anzahlen an allen Stationen ab, die sich unter weitreichenden Bedingungen in ein Produkt von Einzelstations-Termen faktorisieren lässt.

Scope

Dieses Thema behandelt offene und geschlossene Warteschlangennetzwerke, Routing-Wahrscheinlichkeiten und Verkehrsflussgleichungen, Jacksons Theorem über die stationäre Verteilung offener Markow-Netzwerke in Produktform, die BCMP-Erweiterung auf mehrere Kundentypen und Bedienungsdisziplinen, das Ankunftstheorem und die Mittelwertanalyse für geschlossene Netzwerke sowie die Quasireversibilität als strukturellen Grund für die Produktform.

Core questions

• Wie bestimmen Routing-Wahrscheinlichkeiten die effektive Ankunftsrate an jeder Station?
• Wann faktorisiert die gemeinsame stationäre Verteilung in ein Produkt über die Stationen?
• Wie unterscheiden sich geschlossene Netzwerke mit einer festen Kundenpopulation von offenen?
• Welche strukturelle Eigenschaft von Stationen garantiert die Produktform?

Key theories

Jacksons Produktform-Theorem

In einem offenen Netzwerk von exponentiellen Einzelserver-Warteschlangen mit Markowschem Routing ist die stationäre Verteilung das Produkt von geometrischen Verteilungen, deren Parameter aus der Lösung der Verkehrsflussgleichungen stammen, sodass sich die Stationen im Gleichgewicht als unabhängig verhalten.

Quasireversibilität und das BCMP-Theorem

Stationen, die quasireversibel sind, lassen sich zu Netzwerken mit Produktform-Gleichgewichten zusammensetzen, und das BCMP-Theorem erweitert dies auf mehrere Kundentypen und verschiedene Bedienungsdisziplinen, wodurch die Klasse der handhabbaren Netzwerke erheblich erweitert wird.

Clinical relevance

Warteschlangennetzwerke modellieren Computersysteme, Kommunikations- und Paketnetzwerke, flexible Fertigung und Lieferketten, und die Produktform-Theorie sowie die Mittelwertanalyse ermöglichen effiziente Leistungsvorhersagen von Durchsatz, Auslastung und Antwortzeit, ohne den gesamten gemeinsamen Zustandsraum simulieren zu müssen.

History

Jackson führte 1957 offene Netzwerke mit Produktform-Lösungen ein, Gordon und Newell behandelten 1967 geschlossene Netzwerke, das BCMP-Theorem von 1975 vereinte mehrere Klassen und Disziplinen, und Kellys Monographie von 1979 erklärte die Produktform durch Reversibilität und etablierte damit die Theorie, die der Leistungsanalyse von Computersystemen zugrunde liegt.

Key figures

• James Jackson
• Frank Kelly
• Forest Baskett
• Mani Chandy

Seminal works

• kelly1979
• jackson1957

Frequently asked questions

Was ist ein Produktform-Netzwerk?

Es ist ein Warteschlangennetzwerk, dessen Gleichgewichtsverteilung in ein Produkt von Termen faktorisiert, einen pro Station, sodass die Stationen im stationären Zustand statistisch unabhängig erscheinen, obwohl Kunden zwischen ihnen fließen.

Was ist der Unterschied zwischen offenen und geschlossenen Netzwerken?

Ein offenes Netzwerk hat externe Ankünfte und Abgänge, sodass die Kundenpopulation schwankt, während ein geschlossenes Netzwerk eine feste Anzahl von Kunden unter den Stationen zirkulieren lässt, ohne Eintritte oder Austritte.