Sequenznummer mit Überlauf

Hallo,

bei mir werden Nachrichten mit einer Sequenznummer versehen.
Wie macht man es denn am schönsten bei einem Überlauf, wenn man wissen will ob eine Nummer "neuer" ist als die andere? Meine Seuqenznummer ist im Moment vom Typ unsigned int (4 Byte).

Ajaw

Von was fuer einer Art Nachrichten reden wir denn?

Wenn deine Sequenznummern ueberlaufen und du keine Vorkehrungen getroffen hast, hast du auf jeden Fall mal ein Problem.

Entweder du waehlst deinen Zahlenraum so gross, dass ein Ueberlauf nicht vorkommt, oder du nutzt zusaetzlich noch einen Timestamp als Kriterium. Anders macht es TCP ja auch nicht (Stichwort: PAWS)

Hab mal folgendes gemacht.
Das sollte doch eigenlicht auch abfangen, falls mal ein paar Nummern zwischendurch "verloren gehen".
Das klappt auch für einen Überlauf oder?
Sieht jemand ein Problem oder Verbesserungsvorschläge.

bool isNewer(unsigned int lhs, unsigned int rhs)
{
   bool ret;
   static const unsigned int eps = 10000;

   unsigned int diff = rhs - lhs;
   ret = diff < eps && diff != 0;

   return ret;
}

Apeman

Ajaw schrieb:

Entweder du waehlst deinen Zahlenraum so gross, dass ein Ueberlauf nicht vorkommt, oder du nutzt zusaetzlich noch einen Timestamp als Kriterium. Anders macht es TCP ja auch nicht

wo hat tcp einen timestamp?
topic: seq-nummern dürfen ruhig überlaufen, wenn beide teilnehmer wissen, dass nach der höchsten nummer wieder die 0 kommt, ist doch alles gut.

Ajaw

Apeman schrieb:

wo hat tcp einen timestamp?

RFC 1323

This memo presents a set of TCP extensions to improve performance
over large bandwidth*delay product paths and to provide reliable
operation over very high-speed paths. It defines new TCP options for
scaled windows and timestamps, which are designed to provide
compatible interworking with TCP's that do not implement the
extensions. The timestamps are used for two distinct mechanisms:
RTTM (Round Trip Time Measurement) and PAWS (Protect Against Wrapped
Sequences). Selective acknowledgments are not included in this memo.

Apeman schrieb:

topic: seq-nummern dürfen ruhig überlaufen, wenn beide teilnehmer wissen, dass nach der höchsten nummer wieder die 0 kommt, ist doch alles gut.

Aber auch nur dann, wenn du die korrekte Reihenfolge garantieren kannst. Ansonsten bist du verratzt.

thordk

also das nach sequenznummer 4294967296 noch ein paket mit der sequenznummer 0 eintrudelt, welches tatsächlich vorher abgeschickt wurde und sich nur leicht verspätet hat, ist so dermaßen unwahrscheinlich, dass man tatsächlich einfach den gesamten wertebereich seines sequenznummerntyps als geschlossenen ring betrachten kann, ohne in probleme zu rennen. in meinem beispiel also nen 32 bit unsigned int.

Apeman

Ajaw schrieb:

Apeman schrieb:

wo hat tcp einen timestamp?

RFC 1323

das sind aber optionale erweiterungen für spezialfälle. für gewöhnlich sendet ein TCP keine timestamps mit.

Ajaw schrieb:

Apeman schrieb:

topic: seq-nummern dürfen ruhig überlaufen, wenn beide teilnehmer wissen, dass nach der höchsten nummer wieder die 0 kommt, ist doch alles gut.

Aber auch nur dann, wenn du die korrekte Reihenfolge garantieren kannst. Ansonsten bist du verratzt.

verstehe ich nicht. seq-nummern sind doch gerade dazu da, um die korrekte oder falsche reihenfolge festzustellen.

Ajaw

Apeman schrieb:

das sind aber optionale erweiterungen für spezialfälle. für gewöhnlich sendet ein TCP keine timestamps mit.

Das hab ich ja auch nirgends behauptet, oder? Ich habe nur gesagt, dass TCP mit Sequenznummern und Timestamps arbeitet. Wann, wo und wieso habe ich nicht erwaehnt.

Apeman schrieb:

verstehe ich nicht. seq-nummern sind doch gerade dazu da, um die korrekte oder falsche reihenfolge festzustellen.

Eben. Was aber nur funktioniert wenn sie nicht (zu frueh) umbrechen.

Fuer den Threadersteller wuerde wohl auch ein 16-Bit-Datentyp als Sequenznummer ausreichen. Aber er wollte ja wissen wie man es am "schoensten" macht.

Danke für die Antworten auf den code ist leider keiner eingegangen (dafür umsomehr auf TCP ;))
Mein System ist übrigens Zeitlos glücklich. Hat einfach keine Uhr. Daher erübrigt sich die Sache mit Timestamps.

pumuckl

Also wenn ich das richtig verstanden hab willst du die ankommenden Nachrichten nach Sequenznummern ordnen. Es kann also durchaus mal vorkommen, dass Nachricht mit SeqNr 123 nach Nachricht mit SeqNr 125 eintrudelt. Ab irgendeiner Differenz ist es allerdings nichtmehr wahrscheinlich, dass da zwei Nachrichten vertauscht wurden. Und ab einer noch hoeheren Differenz liegt der Verdacht nahe, dass da gerade ein Ueberlauf passiert ist. Beispielsweise fuer 16 Bit (Seqnr von 0 bis 65535) keonnte man das dann so machen:
- Differenz von 1 bis 10.000 => normaler Fall
- Differenz von (-)55535 bis (-)65535 => Ueberlauf, die wahre Differenz ist dann
65535 - diff, liegt also wieder im normalen Bereich
- Differenz zwischen 10.000 und 55535 => Da ist irgendwas so gehoerig durcheinander geraten, dass man es vielleicht nicht mehr bearbeiten sollte.

Wenn deine Toleranzen groesser sein sollen, musst du evtl. die Range fuer deine SeqNummern anpassen, so dass du immernoch einen grossen Bereich von Abstaenden hast, der eingentlich nie auftreten darf.

Bei deinem Code sollte das schon von sich aus so funktionieren, nehmen wir mal folgende Kombinationen:

4 und 5000 => 4 < 5000 wird ganz normal berechnet
5000 und 4 => 4 - 5000 = 60532 in der unsigned short welt (hab jetzt keine Lust auf ellenlange riesenzahlen), also liefert dein isnewer auch richtiggehend (?)* false
65300 und 12 (Ueberlauf!) => 12 -65300 = 248 in der ushort welt, alles in Ordnung, deine Funktion funktioniert so also ganz gut.

Das einzige was ich noch hinzufuegen wuerde ist eine Ausnahme/Fehlerbehandlung falls diff doch mal groesser als 10.000 sein sollte. (Wie gesagt, dann ist gehoerig was schief gelaufen, ist aber theoretisch moeglich)

* nur wenn kleinere Zahlen neuer sein sollen...