Schiebefensterprotokoll – Wikipedia

Art des Fehlererkennungsprotokolls auf der Datenverbindungsschicht und der Transportschicht für TCP

EIN Schiebefensterprotokoll ist eine Funktion von paketbasierten Datenübertragungsprotokollen. Schiebefensterprotokolle werden verwendet, wenn eine zuverlässige Zustellung von Paketen in der richtigen Reihenfolge erforderlich ist, beispielsweise in der Datenverbindungsschicht (OSI-Schicht 2) sowie im Transmission Control Protocol (TCP). Sie werden auch verwendet, um die Effizienz zu verbessern, wenn der Kanal eine hohe Latenz aufweisen kann.

Paketbasierte Systeme basieren auf der Idee, einen Datenstapel zu senden Paketzusammen mit zusätzlichen Daten, mit denen der Empfänger sicherstellen kann, dass sie korrekt empfangen wurden, möglicherweise eine Prüfsumme. Wenn der Empfänger die Daten überprüft, sendet er ein Bestätigungssignal oder “ACK” zurück an den Absender, um anzuzeigen, dass er das nächste Paket senden kann. In einem einfachen automatischen Wiederholungsanforderungsprotokoll (ARQ) stoppt der Absender nach jedem Paket und wartet darauf, dass der Empfänger ACK erhält. Dies stellt sicher, dass Pakete in der richtigen Reihenfolge ankommen, da jeweils nur eines gesendet werden kann.

Die Zeit, die für den Empfang des ACK-Signals benötigt wird, kann im Vergleich zu der zum Senden des Pakets erforderlichen Zeit eine erhebliche Zeitspanne darstellen. In diesem Fall kann der Gesamtdurchsatz viel geringer sein als theoretisch möglich. Um dies zu beheben, erlauben Schiebefensterprotokolle eine ausgewählte Anzahl von Paketen, die Fenster, gesendet werden, ohne auf eine Bestätigung warten zu müssen. Jedes Paket empfängt eine Sequenznummer, und die ACKs senden diese Nummer zurück. Das Protokoll verfolgt, welche Pakete bestätigt wurden, und sendet beim Empfang weitere Pakete. Auf diese Weise das Fenster Folien entlang des Paketstroms, aus dem die Übertragung besteht.

Schiebefenster sind ein wesentlicher Bestandteil vieler Protokolle. Es ist ein wichtiger Bestandteil des TCP-Protokolls, das es von Natur aus ermöglicht, dass Pakete nicht in der richtigen Reihenfolge ankommen. Es ist auch in vielen Dateiübertragungsprotokollen wie UUCP-g und ZMODEM enthalten, um die Effizienz im Vergleich zu Protokollen ohne Fenster wie XMODEM zu verbessern.

Basiskonzept[edit]

Konzeptionell wird jedem Teil der Übertragung (Pakete in den meisten Datenverbindungsschichten, aber Bytes in TCP) eine eindeutige fortlaufende Sequenznummer zugewiesen, und der Empfänger verwendet die Nummern, um empfangene Pakete in der richtigen Reihenfolge zu platzieren, doppelte Pakete zu verwerfen und fehlende zu identifizieren . Das Problem dabei ist, dass die Größe der Sequenznummer, die erforderlich sein kann, unbegrenzt ist.

Durch die Begrenzung der Anzahl von Paketen, die zu einem bestimmten Zeitpunkt gesendet oder empfangen werden können, ermöglicht ein Schiebefensterprotokoll die Kommunikation einer unbegrenzten Anzahl von Paketen unter Verwendung von Sequenznummern fester Größe. Der Begriff “Fenster” auf der Senderseite stellt die logische Grenze der Gesamtzahl der Pakete dar, die vom Empfänger noch bestätigt werden müssen. Der Empfänger informiert den Sender in jedem Bestätigungspaket über die aktuelle maximale Empfängerpuffergröße (Fenstergrenze). Der TCP-Header verwendet ein 16-Bit-Feld, um die Größe des Empfängerfensters an den Absender zu melden. Daher ist das größte Fenster, das verwendet werden kann, 216 = 64 Kilobyte.

Im Slow-Start-Modus startet der Sender mit einer geringen Paketanzahl und erhöht die Anzahl der Pakete in jeder Übertragung, nachdem Bestätigungspakete vom Empfänger empfangen wurden. Für jedes empfangene Bestätigungspaket wird das Fenster (logisch) um ein Paket verschoben, um ein neues Paket zu übertragen. Wenn der Fensterschwellenwert erreicht ist, sendet der Sender ein Paket für ein empfangenes Bestätigungspaket.

Wenn das Fensterlimit 10 Pakete beträgt, kann der Sender im langsamen Startmodus mit der Übertragung eines Pakets beginnen, gefolgt von zwei Paketen (vor dem Senden von zwei Paketen muss eine Paketbestätigung empfangen werden), gefolgt von drei Paketen usw. bis zu 10 Paketen. Nach Erreichen von 10 Paketen sind weitere Übertragungen jedoch auf ein für ein empfangenes Bestätigungspaket übertragenes Paket beschränkt. In einer Simulation sieht es so aus, als würde sich das Fenster für jedes empfangene Bestätigungspaket um eine Paketentfernung bewegen. Auf der Empfängerseite verschiebt das Fenster auch ein Paket für jedes empfangene Paket.

Die Schiebefenstermethode stellt sicher, dass Verkehrsstaus im Netzwerk vermieden werden. Die Anwendungsschicht bietet weiterhin Daten für die Übertragung an TCP an, ohne sich um die Probleme mit der Überlastung des Netzwerkverkehrs sorgen zu müssen, da der TCP auf Sender- und Empfängerseite Schiebefenster des Paketpuffers implementiert. Die Fenstergröße kann je nach Netzwerkverkehr dynamisch variieren.

Für den höchstmöglichen Durchsatz ist es wichtig, dass der Sender nicht gezwungen ist, das Senden durch das Schiebefensterprotokoll vor einer Umlaufverzögerungszeit (RTT) zu beenden. Die Begrenzung der Datenmenge, die gesendet werden kann, bevor auf eine Bestätigung gewartet wird, sollte größer sein als das Bandbreitenverzögerungsprodukt der Kommunikationsverbindung. Ist dies nicht der Fall, begrenzt das Protokoll die effektive Bandbreite der Verbindung.

Motivation[edit]

In jedem Kommunikationsprotokoll, das auf einer automatischen Wiederholungsanforderung zur Fehlerkontrolle basiert, muss der Empfänger empfangene Pakete bestätigen. Wenn der Sender innerhalb einer angemessenen Zeit keine Bestätigung erhält, sendet er die Daten erneut.

Ein Sender, der keine Bestätigung erhält, kann nicht wissen, ob der Empfänger das Paket tatsächlich empfangen hat. Es kann sein, dass es bei der Übertragung verloren gegangen oder beschädigt wurde. Wenn der Fehlererkennungsmechanismus eine Beschädigung aufdeckt, wird das Paket vom Empfänger ignoriert und eine negative oder doppelte Bestätigung wird vom Empfänger gesendet. Der Empfänger kann auch so konfiguriert sein, dass er überhaupt keine Bestätigung sendet. In ähnlicher Weise ist der Empfänger normalerweise unsicher, ob seine Bestätigungen empfangen werden. Es kann sein, dass eine Bestätigung gesendet wurde, diese jedoch auf dem Übertragungsmedium verloren ging oder beschädigt wurde. In diesem Fall muss der Empfänger die erneute Übertragung bestätigen, um zu verhindern, dass die Daten ständig erneut gesendet werden. Andernfalls muss er sie ignorieren.

Protokolloperation[edit]

Der Sender und der Empfänger haben jeweils eine aktuelle Sequenznummer nt und nr, beziehungsweise. Sie haben jeweils auch eine Fenstergröße wt und wr. Die Fenstergrößen können variieren, sind jedoch in einfacheren Implementierungen festgelegt. Die Fenstergröße muss größer als Null sein, damit Fortschritte erzielt werden können.

Wie normalerweise implementiert, nt ist das nächste zu sendende Paket, dh die Sequenznummer des ersten noch nicht übertragenen Pakets. Gleichfalls, nr ist das erste noch nicht empfangene Paket. Beide Zahlen nehmen mit der Zeit monoton zu; sie nehmen immer nur zu.

Der Empfänger kann auch die höchste bisher empfangene Sequenznummer verfolgen; Die Variable ns ist eins mehr als die Sequenznummer der höchsten empfangenen Sequenznummer. Für einfache Empfänger, die nur Pakete in der richtigen Reihenfolge annehmen (wr = 1), das ist das gleiche wie nr, kann aber größer sein, wenn wr > 1. Beachten Sie den Unterschied: alle Pakete unten nr wurden empfangen, keine Pakete oben ns empfangen wurden und zwischen nr und nswurden einige Pakete empfangen.

Wenn der Empfänger ein Paket empfängt, aktualisiert er seine Variablen entsprechend und sendet eine Bestätigung mit dem neuen nr. Der Sender verfolgt die höchste empfangene Bestätigung nein. Der Sender weiß, dass alle Pakete bis zu, aber nicht enthalten nein wurden empfangen, ist aber unsicher über Pakete zwischen nein und ns;; dh neinnrns.

Die Folgenummern entsprechen immer der Regel, dass neinnrnsntnein + wt. Das ist:

  • neinnr: Die höchste vom Sender empfangene Bestätigung kann nicht höher als die höchste sein nr vom Empfänger bestätigt.
  • nrns: Die Spanne vollständig empfangener Pakete kann nicht über das Ende der teilweise empfangenen Pakete hinausgehen.
  • nsnt: Das höchste empfangene Paket kann nicht höher sein als das höchste gesendete Paket.
  • ntnein + wt: Das höchste gesendete Paket wird durch die höchste empfangene Bestätigung und die Größe des Sendefensters begrenzt.

Senderbetrieb[edit]

Wann immer der Sender Daten zum Senden hat, kann er bis zu senden wt Pakete vor der letzten Bestätigung nein. Das heißt, es kann eine Paketnummer übertragen nt so lange wie nt < nein+wt.

Wenn kein Kommunikationsfehler vorliegt, erhält der Sender bald eine Bestätigung für alle von ihm gesendeten Pakete nein gleicht nt. Wenn dies nicht nach einer angemessenen Verzögerung geschieht, muss der Sender die Pakete zwischen erneut senden nein und nt.

Techniken zum Definieren einer “angemessenen Verzögerung” können äußerst aufwändig sein, wirken sich jedoch nur auf die Effizienz aus. Die grundlegende Zuverlässigkeit des Schiebefensterprotokolls hängt nicht von den Details ab.

Empfängerbetrieb[edit]

Jedes Mal, wenn ein Paket nummeriert ist x empfangen wird, prüft der Empfänger, ob es in das Empfangsfenster fällt, nrx < nr+wr. (Die einfachsten Empfänger müssen nur einen Wert verfolgen nr=ns.) Wenn es in das Fenster fällt, akzeptiert der Empfänger es. Wenn es nummeriert ist nrwird die Empfangssequenznummer um 1 erhöht und möglicherweise um mehr, wenn zuvor weitere aufeinanderfolgende Pakete empfangen und gespeichert wurden. Wenn x > nrwird das Paket gespeichert, bis alle vorhergehenden Pakete empfangen wurden.[1] Wenn xnsLetzteres wird auf aktualisiert ns=x+1.

Wenn sich die Paketnummer nicht im Empfangsfenster befindet, verwirft der Empfänger sie und ändert sie nicht nr oder ns.

Unabhängig davon, ob das Paket angenommen wurde oder nicht, sendet der Empfänger eine Bestätigung, die den Strom enthält nr. (Die Bestätigung kann auch Informationen über zusätzliche Pakete enthalten, die zwischen empfangen werden nr oder ns, aber das hilft nur der Effizienz.)

Beachten Sie, dass es keinen Sinn macht, das Empfangsfenster zu haben wr größer als das Sendefenster wt, weil Sie sich keine Sorgen über den Empfang eines Pakets machen müssen, das niemals übertragen wird; der nützliche Bereich ist 1 ≤ wrwt.

Sequenznummernbereich erforderlich[edit]

Sequenznummern Modulo 4, mit wr= 1. Anfänglich, nt=nr= 0

Bisher wurde das Protokoll so beschrieben, als ob die Sequenznummern unbegrenzt groß sind und ständig zunehmen. Anstatt jedoch die vollständige Sequenznummer zu übertragen x In Nachrichten ist es nur möglich zu senden x mod N.für einige endliche N.. ((N. ist normalerweise eine Potenz von 2.)

Beispielsweise empfängt der Sender nur Bestätigungen im Bereich nein zu ntinklusive. Da garantiert es das nt– –neinwtgibt es höchstens wt+1 mögliche Folgenummern, die zu einem bestimmten Zeitpunkt eintreffen könnten. Somit kann der Sender die Sequenznummer eindeutig so lange decodieren, wie N. > wt.

Eine stärkere Einschränkung wird vom Empfänger auferlegt. Der Betrieb des Protokolls hängt davon ab, dass der Empfänger neue Pakete (die akzeptiert und verarbeitet werden sollten) zuverlässig von erneuten Übertragungen alter Pakete (die verworfen und die letzte Bestätigung erneut übertragen werden sollten) unterscheiden kann. Dies kann bei Kenntnis der Fenstergröße des Senders erfolgen. Nach dem Empfang eines Pakets nummeriert x, der Empfänger weiß das x < nein+wt, damit nein > x– –wt. Somit sind die Pakete nummeriert x– –wt wird nie wieder übertragen.

Die niedrigste Sequenznummer, die wir jemals in Zukunft erhalten werden, ist ns– –wt

Der Empfänger weiß auch, dass der Sender nein kann nicht höher sein als die höchste jemals gesendete Bestätigung nr. Die höchste Sequenznummer, die wir möglicherweise sehen konnten, ist nr+wtns+wt.

Somit gibt es 2wt verschiedene Sequenznummern, die der Empfänger jederzeit empfangen kann. Es könnte daher scheinen, dass wir haben müssen N. ≥ 2wt. Die tatsächliche Grenze ist jedoch niedriger.

Die zusätzliche Erkenntnis ist, dass der Empfänger nicht zwischen zu niedrigen Sequenznummern (kleiner als) unterscheiden muss nr) oder die zu hoch sind (größer oder gleich ns+wr). In beiden Fällen ignoriert der Empfänger das Paket, außer um eine Bestätigung erneut zu senden. Es ist also nur notwendig, dass N.wt+wr. Wie es üblich ist wr<wt (zB siehe Go-Back-N unten), dies kann größere ermöglichen wt innerhalb eines festen N..

Beispiele[edit]

Das einfachste Schiebefenster: Stop-and-Wait[edit]

Obwohl das Stop-and-Wait-ARQ-Protokoll üblicherweise vom Sliding-Window-Protokoll unterschieden wird, ist es tatsächlich die einfachste mögliche Implementierung. Das Sendefenster ist 1 Paket und das Empfangsfenster ist 1 Paket. So, N. = 2 mögliche Folgenummern (zweckmäßigerweise durch ein einzelnes Bit dargestellt) sind erforderlich.

Beispiel für Mehrdeutigkeit[edit]

Der Sender sendet abwechselnd Pakete, die mit “ungerade” und “gerade” gekennzeichnet sind. Die Bestätigungen sagen ebenfalls “ungerade” und “gerade”. Angenommen, der Sender hat nach dem Senden eines ungeraden Pakets nicht auf eine ungerade Bestätigung gewartet und stattdessen sofort das folgende gerade Paket gesendet. Es kann dann eine Bestätigung erhalten, die besagt, dass “als nächstes ein ungerades Paket erwartet wird”. Dies würde den Sender in ein Dilemma bringen: Hat der Empfänger beide Pakete empfangen oder keines?

Zurück-N[edit]

Go-Back-N ARQ ist das Schiebefensterprotokoll mit wt> 1, aber ein fester wr= 1. Der Empfänger lehnt es ab, ein anderes Paket als das nächste nacheinander anzunehmen. Wenn ein Paket während der Übertragung verloren geht, werden die folgenden Pakete ignoriert, bis das fehlende Paket erneut übertragen wird. Dies entspricht einem Mindestverlust von einer Umlaufzeit. Aus diesem Grund ist es bei Verbindungen mit häufigem Paketverlust ineffizient.

Beispiel für Mehrdeutigkeit[edit]

Angenommen, wir verwenden eine 3-Bit-Sequenznummer, wie sie für HDLC typisch ist. Das gibt N.= 23= 8. Schon seit wr= 1 müssen wir begrenzen wt≤7. Dies liegt daran, dass nach dem Senden von 7 Paketen 8 mögliche Ergebnisse vorliegen: 0 bis 7 Pakete könnten erfolgreich empfangen worden sein. Dies sind 8 Möglichkeiten, und der Sender benötigt genügend Informationen in der Bestätigung, um sie alle zu unterscheiden.

Wenn der Sender 8 Pakete gesendet hat, ohne auf eine Bestätigung zu warten, könnte er sich in einem Dilemma befinden, das dem Stop-and-Wait-Fall ähnelt: Bedeutet die Bestätigung, dass alle 8 Pakete erfolgreich empfangen wurden oder keines davon?

Selektive Wiederholung[edit]

Der allgemeinste Fall des Schiebefensterprotokolls ist Selective Repeat ARQ. Dies erfordert einen viel leistungsfähigeren Empfänger, der Pakete mit höheren Sequenznummern als dem aktuellen akzeptieren kann nr und lagern Sie sie, bis die Lücke gefüllt ist.

Der Vorteil besteht jedoch darin, dass es nicht erforderlich ist, die folgenden korrekten Daten für eine Umlaufzeit zu verwerfen, bevor der Sender darüber informiert werden kann, dass eine erneute Übertragung erforderlich ist. Dies wird daher für Verbindungen mit geringer Zuverlässigkeit und / oder einem Produkt mit hoher Bandbreitenverzögerung bevorzugt.

Die Fenstergröße wr muss nur größer sein als die Anzahl von aufeinanderfolgenden verlorene Pakete, die toleriert werden können. Daher sind kleine Werte beliebt; wr= 2 ist üblich.

Beispiel für Mehrdeutigkeit[edit]

Das äußerst beliebte HDLC-Protokoll verwendet eine 3-Bit-Sequenznummer und bietet optional eine Möglichkeit zur selektiven Wiederholung. Wenn jedoch eine selektive Wiederholung verwendet werden soll, ist die Anforderung, dass nt+nr ≤ 8 muss beibehalten werden; wenn wr wird auf 3 erhöht, wt muss auf 6 verringert werden.

Nehme an, dass wr= 2, aber ein unveränderter Sender wird mit verwendet wt= 7, wie es typischerweise bei der Go-Back-N-Variante von HDLC verwendet wird. Angenommen, der Empfänger beginnt mit nr=ns= 0.

Angenommen, der Empfänger sieht die folgende Reihe von Paketen (alle Modulo 8):

0 1 2 3 4 5 6 (Pause) 0

weil wr= 2, der Empfänger akzeptiert und speichert das endgültige Paket 0 (denkt, es ist Paket 8 in der Reihe), während er eine erneute Übertragung von Paket 7 anfordert. Es ist jedoch auch möglich, dass der Sender keine Bestätigungen empfangen hat und das Paket erneut übertragen hat In diesem letzteren Fall würde der Empfänger das falsche Paket als Paket 8 akzeptieren.

Die Lösung besteht darin, dass der Sender begrenzt wt≤6. Mit dieser Einschränkung weiß der Empfänger, dass, wenn alle Bestätigungen verloren gegangen wären, der Sender nach Paket 5 gestoppt hätte. Wenn er Paket 6 empfängt, kann der Empfänger schließen, dass der Sender die Bestätigung für Paket 0 (die des Senders) empfangen hat nein≥1), und daher muss das folgende Paket mit der Nummer 0 Paket 8 sein.

Erweiterungen[edit]

Es gibt viele Möglichkeiten, das Protokoll zu erweitern:

  • In den obigen Beispielen wurde davon ausgegangen, dass Pakete bei der Übertragung niemals neu angeordnet werden. Sie können während des Transports verloren gehen (Fehlererkennung macht Korruption gleichbedeutend mit Verlust), erscheinen jedoch niemals außer Betrieb. Das Protokoll kann erweitert werden, um die Neuordnung von Paketen zu unterstützen, solange die Entfernung begrenzt werden kann. der Sequenznummernmodul N. muss um den maximalen Fehlordnungsabstand erweitert werden.
  • Es ist möglich, nicht jedes Paket zu bestätigen, solange bei einer Pause eine Bestätigung gesendet wird. Beispielsweise bestätigt TCP normalerweise jedes zweite Paket.
    • Es ist üblich, den Sender sofort zu informieren, wenn eine Lücke in der Paketsequenz erkannt wird. HDLC hat hierfür ein spezielles REJ-Paket (Reject).
  • Die Sende- und Empfangsfenstergrößen können während der Kommunikation geändert werden, solange ihre Summe innerhalb der Grenze von bleibt N.. Normalerweise werden ihnen jeweils Maximalwerte zugewiesen, die diese Grenze einhalten, aber der Arbeitswert kann zu einem bestimmten Zeitpunkt unter dem Maximum liegen. Speziell:
    • Es ist üblich, die Größe des Sendefensters zu verringern, um die Übertragung zu verlangsamen, um sie an die Geschwindigkeit der Verbindung anzupassen, wodurch Sättigung oder Überlastung vermieden werden.
    • Eine übliche Vereinfachung der selektiven Wiederholung ist das sogenannte SREJ-REJ ARQ. Dies funktioniert mit wr= 2 und puffert Pakete nach einer Lücke, lässt aber nur ein einzelnes verlorenes Paket zu; während Sie auf dieses Paket warten, wr= 1 und wenn ein zweites Paket verloren geht, werden keine Pakete mehr gepuffert. Dies bietet den größten Leistungsvorteil des vollständigen selektiven Wiederholungsprotokolls bei einer einfacheren Implementierung.

Siehe auch[edit]

Verweise[edit]

  • Comer, Douglas E. “Internetworking mit TCP / IP, Band 1: Prinzipien, Protokolle und Architektur”, Prentice Hall, 1995. ISBN 0-13-216987-8
  • Peterson, Larry L. und Davie, Bruce S. “Computernetzwerke: Ein Systemansatz”, Morgan Kaufmann, 2000. ISBN 1558605142

Externe Links[edit]