Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2015 | Buch

Einleitung Kapitel lesen Erstes Kapitel lesen

Entwurf und Analyse von Kommunikationsnetzen

Netzplanung – Wartesysteme – Network Calculus

verfasst von: Ulrich Killat

Verlag: Springer Fachmedien Wiesbaden

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Dieses Lehrbuch ist eine einführende Darstellung verschiedener Verfahren des Entwurfs und der Analyse von Kommunikationsnetzen. Nachrichtentechniker und Informatiker mit dem Schwerpunkt „Kommunikationsnetze“ sollten damit vertraut sein. Es spannt einen Bogen von exakten Planungsverfahren (sowie entsprechenden Näherungsverfahren) über Leistungsbewertung mit Hilfe der Warteschlangentheorie bis hin zu Verfahren, die Schranken für Ende-zu-Ende Leistungsparameter in Netzen bestimmen. Das Buch legt Wert auf die Zusammenhänge zwischen den einzelnen Themen, die üblicherweise in getrennten Fachbüchern behandelt werden. Der Autor weckt ein intuitives Verständnis für die beschriebenen Verfahren, weswegen viele mathematische Voraussetzungen und Zusammenhänge in Anhängen behandelt werden. Beispiele aus eigenen Forschungsarbeiten dienen vielfach zur Verdeutlichung der vermittelten Sachverhalte.
Hinweise zur Lösung aller Aufgaben finden sich auf der Plattform „DozentenPlus“ . Hier sind auch drei englischsprachige Power Point Präsentationen verfügbar, in denen der Stoff der drei Teile des Buches für Vorlesungen aufbereitet ist.

Inhaltsverzeichnis

Frontmatter
1. Einleitung
Zusammenfassung
Wir führen die Konzepte von Leitungs- und Paketvermittlung in Kommunikationsnetzen ein und vergegenwärtigen uns die wechselseitigen Abhängigkeiten von Verkehrsaufkommen, Ressourceneinsatz, Dienstgüte und Kosten. Diese Betrachtung führt auf die zentralen Themen des Buches, nämlich Planung und Leistungsbewertung von Netzen. Eine Übersicht über Lehrbücher, die den in den Kapiteln dieses Buches behandelten Stoff ausführlicher und tiefer gehend präsentieren, schließt das Kapitel ab.
Ulrich Killat

Netzplanung und Netzoptimierung

Frontmatter
2. Klassifizierung von Problemen
Zusammenfassung
Wir stellen in Kap. 2 eine Reihe typischer Aufgabenstellungen der Netzplanung bzw. Netzoptimierung vor, die sich immer auf die Struktur einer Minimierungsaufgabe mit Randbedingungen zurückführen lassen. Diese Liste ist bei weitem nicht erschöpfend und Kombinationen der diskutierten Probleme führen automatisch auf neue Aufgabenstellungen. In diesem Kapitel geht es vordringlich um die mathematische Formulierung eines Problems, wobei der Typ der jeweils verwendeten Entscheidungsvariablen noch nicht sonderlich herausgestellt wird, obwohl es – wie wir noch in Kap. 3 sehen werden – für die Lösung eines Problems letztlich ungeheuer wichtig ist, ob man es mit kontinuierlichen, ganzzahligen oder binären Variablen zu tun hat. Die Beispiele schlagen einen Bogen von einfachen Platzierungs-, Linkdimensionierungs- und Routingaufgaben bis hin zu optischen Netzen und schichtenübergreifender Optimierung.
Ulrich Killat
3. Methoden für die Lösung von Problemen der linearen Optimierung
Zusammenfassung
Als Lösungsverfahren für lineare Optimierungsprobleme werden der Simplex-Algorithmus und das Branch-and-Bound-Verfahren vorgestellt und anhand eines Beispiels erläutert. Die Relaxation von Nebenbedingungen führt auf die Lagrange-Funktion, das Konzept des dualen Problems und darauf abgestimmte Lösungsmethoden. Daneben werden auch heuristische Lösungskonzepte wie genetische Algorithmen diskutiert und die Leistungsfähigkeit der unterschiedlichen Lösungsverfahren in einem Beispiel aus dem Bereich der optischen Netze verglichen.
Ulrich Killat
4. Weiterführende Beispiele der Netzoptimierung
Zusammenfassung
Der optimierte Einsatz von Wellenlängenkonvertern und die dynamische Umkonfigurierung eines IP-Netzes sind zwei Beispiele von anspruchsvollen Planungsaufgaben, die hier überdies genutzt werden, methodische Ansätze zu verdeutlichen. Dabei handelt es sich zum einen um die Überführung einer nicht-linearen Problemstellung in eine lineare und zum zweiten um die Nutzung der Lagrange-Funktion zur Entwicklung verteilt ablaufender Algorithmen, die das Netz protokollgestützt in einen Optimalzustand steuern.
Ulrich Killat
5. Optimierung mit elastischen Verkehren
Zusammenfassung
In diesem Kapitel befassen wir uns mit der Fragestellung, wie eine Vielzahl von elastischen Verkehrsquellen ein vorgegebenes Netz optimal nutzen kann. Dazu wird eine konkave Nutzenfunktion eingeführt und der Gesamtnutzen aller unter Einhaltung von Bedarfs- und Kapazitätsrandbedingungen bestimmt. Der entscheidende Punkt ist hier, dass sich das Optimierungsproblem mit Hilfe der Lagrange-Funktion in ein verteiltes Optimierungsproblem überführen lässt. Dabei berechnen die Links einen Preis für die Linknutzung, der den Quellen übermittelt wird. Die Quellen passen ihre Senderaten dann den aktuellen Preisen an. Auf diese Weise lässt sich das Netz protokollgestützt in einen optimalen Zustand überführen, der Ähnlichkeit mit dem von Angebot und Nachfrage bestimmten Gleichgewichtszustand in einem Marktgeschehen hat. An dem Beispiel von Peer-to-Peer-Netzen wird diese Vorgehensweise und ihre Leistungsfähigkeit detailliert beschrieben.
Ulrich Killat
6. In Teil I verwendete Symbole
Zusammenfassung
Die in Teil 1 verwendeten Symbole werden hier in Tabellenform
zusammengefasst.
Ulrich Killat

Warteschlangensysteme

Frontmatter
7. Einführung in die Warteschlangentheorie
Zusammenfassung
Dieses Kapitel stellt das Warteschlangenparadigma und die damit einhergehende Terminologie vor. Das Beispiel eines D/D/1/N-Systems erlaubt es, die Abläufe in einer Warteschlange leicht nachzuvollziehen, weil die Komplexität eines stochastischen Geschehens entfällt.
Ulrich Killat
8. Zufallsprozesse
Zusammenfassung
Das Verhalten von Warteschlangensystemen wird zumeist von dem stochastischen Verhalten der Ankunfts- und Bedienprozesse bestimmt. Wir lernen die zeitdiskreten und zeitkontinuierlichen Markow-Ketten als gedächtnislose Prozesse kennen und bestimmen deren Gleichgewichtsverteilungen. Erneuerungsprozesse werden als Punktprozesse eingeführt, die der Einschränkung negativ-exponentieller Verweildauern nicht mehr unterliegen. Neben dem in der klassischen Warteschlangentheorie dominierenden Poisson-Prozess werden auch Prozesse behandelt, die durch Selbstähnlichkeit oder Endlastigkeit charakterisiert sind.
In einem ausführlichen Beispiel wird die Anwendung von Zufallsprozessen auf die Modellierung von Mobilitätsverhalten vorgestellt und deren Leistungsfähigkeit und Grenzen aufgezeigt.
Ulrich Killat
9. Einfache Markowsche Systeme
Zusammenfassung
Das einfachste Warteschlangensystem, das M/M/1-System, wird analysiert und seine Zustandsverteilung und die zugehörige Wartezeitverteilung berechnet. Auf dieser Basis ergeben sich dann zwanglos die Erwartungswerte für die Zahl der Kunden im System bzw. im Warteraum sowie die Erwartungswerte der Warte- und der Verweilzeit. Da Ankunfts- und Bedienraten zunächst zustandsabhängig angenommen werden, bietet die gefundene Zustandsverteilung eine gute Basis für weitere Modellierungen in Kap. 11.
Ulrich Killat
10. Gesetz von Little
Zusammenfassung
Das Gesetz von Little bezieht sich auf Erwartungswerte. Es stellt einen Zusammenhang her zwischen einer Anzahl wartender Kunden und der Wartezeit, die sie erfahren. Da im Beweis Aussagen über Zeitmittelwerte auf Erwartungswerte übertragen werden, ist der Gültigkeitsbereich des Gesetzes auf ergodische Systeme eingeschränkt – was in aller Regel keine einschneidende Randbedingung bedeutet. Daher gibt es eine Vielzahl von Anwendungen des Gesetzes, von denen hier zwei vorgestellt werden.
Ulrich Killat
11. Markowsche Warteschlangensysteme mit mehreren Bedienstationen
Zusammenfassung
Die in Kap. 9 abgeleitete Zustandsverteilung mit zustandsabhängigen Ankunfts- und Bedienraten lässt sich leicht zur Analyse von Systemen mit mehreren Bedienstationen heranziehen. Dabei stößt man im Falle eines Verlustsystems ohne Wartepuffer auf die bekannte Erlangsche Verlustformel, die lange Zeit das wichtigste Hilfsmittel zur Dimensionierung von Telefonnetzen darstellte. Hierzu wird ein von einem Knoten abgehendes Leitungsbündel mit einem Satz von Servern identifiziert. Ein genaueres Studium der Verlustformel zeigt den Bündeleffekt auf, der ein wichtiges Konzept im Verständnis verkehrstheoretischer Zusammenhänge darstellt.
Macht man sich von der Vorstellung frei, dass eine unendlich große Anzahl von Quellen einen Poisson-Eingangsverkehr produziert und betrachtet man statt dessen eine endliche Anzahl von Quellen, so greift die Engsetsche Verlustformel. Deren Bedeutung erschöpft sich allerdings nicht in den numerischen Differenzen zu der Formel von Erlang (die überdies häufig gar nicht so gravierend sind), sondern sie schärft den Blick für grundlegende Begrifflichkeiten wie der Zustandswahrscheinlichkeit als unbedingte und der Blockierungswahrscheinlichkeit als bedingte Wahrscheinlichkeit.
Ulrich Killat
12. M/GI/1-System
Zusammenfassung
Gegenüber dem M/M/1-System weist das M/GI/1-System eine weitere Zustandsvariable auf: die Restbedienzeit. Da diese zu Abgangszeitpunkten von Kunden, also für die eingebettete Markow-Kette, verschwindet, löst man das nach bekannten Verfahren lösbare Problem der eingebetteten Kette und zeigt dann mit einem hübschen Gedankenexperiment, dass die resultierende Zustandsverteilung mit der Lösung für das ursprüngliche Problem zusammenfällt. Die Formulierung der Lösung macht von der Laplace-Transformierten der Bedienzeitverteilung Gebrauch und das gilt auch für die Lösungen von Wartezeitverteilung und Verteilung der Abstände des Abgangsprozesses, die in diesem Kapitel ebenfalls vorgestellt werden.
Ulrich Killat
13. Vermittlungsknoten
Zusammenfassung
Koppelfelder für Leitungsvermittlung enthalten keine Puffer. Die Berechnung von Blockierungswahrscheinlichkeiten stützt sich daher zum einen auf ähnliche Überlegungen wie bei der Ableitung der Erlangschen Verlustformel und zum anderen auf die durch bedingte Wahrscheinlichkeiten ausgedrückte Erreichbarkeit von freien Leitungen, die eine Verbindung zum Ziel herstellen können.
Koppelmatrizen in der Paketvermittlung haben Puffer in den Eingängen, den Ausgängen oder als zentrale Speichereinheit. Die analytische Behandlung dieser Systeme weist große Ähnlichkeiten mit der Vorgehensweise bei dem M/D/1-System auf. In der Tat verhält sich ein Ausgangspuffer sehr ähnlich dem Puffer in einem M/D/1-System. Dasselbe gilt für die logischen Puffer, die in einem physikalischen Zentralpuffer organisiert sind. Das eingangsgepufferte System, das als einziges keine Geschwindigkeitsüberhöhung des Taktes in der Schaltmatrix benötigt, leidet unter dem Phänomen des „head of line blocking“, das den maximalen Durchsatz auf etwa 60 % begrenzt.
Ulrich Killat
14. Netze von Warteschlangen
Zusammenfassung
Für ein Netz von Warteschlangen mit unendlich großen Puffern und Poisson-Ankunftsprozessen lässt sich die Netzzustandsverteilung unter gewissen Bedingungen als Produkt der Zustandsverteilungen der einzelnen Warteschlangen darstellen. Dieses Ergebnis resultiert wie beim M/M/1-System aus dem Ansatz, die globalen Gleichgewichtsbedingungen durch lokale zu erfüllen. Die durch die Produktdarstellung suggerierte Unabhängigkeit der Warteschlangen existiert nur scheinbar: Eine Ratengleichung beschreibt die Abhängigkeiten der Subsysteme. Diese Zusammenhänge werden an Hand eines einfachen Beispiels erläutert.
Ulrich Killat
15. Verkehrsformung
Zusammenfassung
Mit Verkehrsformung werden Verfahren bezeichnet, die die statistischen Eigenschaften eines Eingangsverkehrs derart verändern, dass in einem nachgeschalteten Warteschlangensystem günstigere Leistungsparameter bezüglich Verzögerung und Verlusten zu beobachten sind. Dabei ist es unvermeidlich, dass dem Verkehrsformer nur die gezielte Verzögerung oder das gezielte Verwerfen von Paketen als Maßnahme zu Gebote steht. In diesem Kapitel werden drei unterschiedliche Typen von Verkehrsformern vorgestellt und damit einhergehende Zielkonflikte angesprochen. Wichtig ist die Beobachtung, dass der Durchlauf durch die Router eines IP-Netzes in der Regel zu einer Verkehrsglättung führt.
Ulrich Killat
16. Zuteilungsverfahren (scheduling)
Zusammenfassung
In diesem Kapitel studieren wir unterschiedliche Zuteilungsverfahren. Im Fall nicht-unterbrechender Prioritäten werden Erwartungswerte für die Wartezeiten auf der Basis eines M/GI/1-Ansatzes berechnet. Ein Beispiel verdeutlicht, dass sich für mehr als 3 Prioritätsklassen der damit verbundene Aufwand in der Regel nicht lohnt. Protokollgestütztes Polling, wie man es etwa von den Token-Zugriffsverfahren her kennt, wird mit Hilfe eines Servers, der „Ferienzeiten“ in Anspruch nimmt, modelliert. Der Erwartungswert für die Wartezeit enthält jetzt Zusatzterme, die proportional zu Erwartungswert und Varianz der Zufallsvariablen für die Ferienzeiten sind. Schließlich wird gezeigt, dass das mit Blick auf moderne Router interessante „Processor Sharing“ auf eine Zustandsverteilung wie die des M/M/1-Systems führt.
Ulrich Killat
17. GI/M/1-System
Zusammenfassung
In diesem Kapitel wird eine Methodik entwickelt, wie man zu Lösungen für das GI/M/1-System kommt, in dessen Kontext man die Annahme gedächtnisloser Ankunftsprozesse fallen gelassen hat. Beispielhaft werden Lösungen für den „interrupted Poisson process“ und einen durch eine Pareto-Verteilung gekennzeichneten Ankunftsprozess vorgestellt und mit den Ergebnissen für ein M/M/1-System verglichen.
Ulrich Killat
18. In Teil II verwendete Symbole
Zusammenfassung
Die in Teil 2 verwendeten Symbole werden hier in Tabellenform zusammengefasst.
Ulrich Killat

Network Calculus

Frontmatter
19. Einführung in den Network Calculus
Zusammenfassung
Aufgabe des „Network Calculus“ ist es, Schranken für Leistungsparameter von Netzknoten oder Hintereinanderschaltungen von Netzknoten anzugeben, um einerseits einen Beitrag zu Dimensionierungsproblemen in Netzen zu liefern und andererseits den Aufwand, der in einer detaillierten Warteschlangenanalyse stecken würde, auf ein erträgliches Maß zu reduzieren. In diesem Kapitel werden die grundlegenden, von der Idee der Einhüllenden von Stichprobenpfaden ausgehenden Konzepte und Begrifflichkeiten vorgestellt. Als wesentliche Leistungskenndaten werden die Rückstau- und die Verzögerungsschranke eingeführt. Dabei unterstellen wir stationäre Zuwächse der betrachteten Prozesse. Zur Beschreibung von Rückstau- und Abgangsprozess bietet sich der kompakte Formalismus der Min-Plus-Algebra an.
Ulrich Killat
20. Deterministischer Network Calculus
Zusammenfassung
Im Deterministischen Network Calculus wird eine „Worst-case“-Betrachtung angestellt: Die Einhüllenden markieren Grenzen, die nie von einem Stichprobenpfad überschritten werden. Auf dieser Basis werden Rückstau- und Verzögerungsschranken zunächst für einen Einzelknoten und dann für eine Kette von Knoten entwickelt. Dabei macht man sich die Rechenregeln der Min-Plus-Algebra zunutze.
Da die zugrunde liegenden Einhüllenden unter keinen Umständen verletzt werden, können die daraus berechneten Schranken nicht besonders eng sein.
Ulrich Killat
21. Stochastischer Network Calculus
Zusammenfassung
Der Stochastische Network Calculus lässt (in geringem vorgegebenen Maße) Überschreitungen der durch die Einhüllenden von kumulativen stochastischen Prozessen definierten Grenzen zu. Als Konsequenz dessen gelten die abgeleiteten Schranken für Verzögerung und Rückstau auch nur mit einer gewissen (kleinen) Verletzungswahrscheinlichkeit. Bei den Berechnungen erweisen sich die Konzepte von effektiver Bandbreite und effektiver Kapazität als besonders hilfreich. Mit ihrer Hilfe lassen sich auch die beim Multiplexen von Datenströmen auftretenden Bündelgewinne modellieren. Bei der Beschreibung einer Kette von Netzknoten muss ein nicht geringer mathematischer Aufwand getrieben werden, da von einer statistischen Unabhängigkeit der in benachbarten Netzknoten zu beschreibenden Prozesse nicht immer ausgegangen werden kann. Beispiele zur Anwendung der Theorie auf Rufannahme-Algorithmen belegen ihre Effizienz.
Ulrich Killat
22. In Teil III verwendete Symbole
Zusammenfassung
Die in Teil 3 verwendeten Symbole werden hier in Tabellenform zusammengefasst.
Ulrich Killat

Anhang

Frontmatter
23. Mathematische Grundlagen
Zusammenfassung
In diesem Kapitel sind eine Reihe mathematischer Kenntnisse, die man zum Verständnis des Stoffes benötigt, die aber vielfach in anderen Vorlesungen behandelt werden, für den Leser zusammengefasst.
Ulrich Killat
24. Übungsaufgaben
Zusammenfassung
Dieses Kapitel enthält Übungsaufgaben zu jedem der drei Teile des Buches.
Ulrich Killat
Backmatter
Metadaten
Titel
Entwurf und Analyse von Kommunikationsnetzen
verfasst von
Ulrich Killat
Copyright-Jahr
2015
Electronic ISBN
978-3-8348-2531-5
Print ISBN
978-3-8348-2530-8
DOI
https://doi.org/10.1007/978-3-8348-2531-5

Neuer Inhalt

    Bildnachweise