Brauche Hilfe bei Algorithmenentwicklung (Kommunikationsprotokoll)

[White_Fox]

Hallo allerseits

Folgende:
Ich entwerfe momentan ein Kommunikationsprotokoll damit sich ein Laptop und ein Mikrocontroller verstehen. Das Ganze stelle ich mir folgendermaßen vor:

Ein Telegramm (ich hoffe der Fachterminus ist richtig) besteht aus einem "Kopf" aus vier Bytes und einem Rumpf, der zwischen 0 und 255 Bytes enthält.
xxxx xxxB | xxxx xxxx | xxxx xxxx | RRRR RRRR

Bedeutet:
B - Bestätigungsbit
R - Anzahl der Bytes im Rumpf
x - Freie Bits oder weitere Informationen über die Daten im Rumpf, für die eigentliche Kommunikation jedoch hier nicht wichtig

Der Kommunikationsablauf soll wie folgt aussehen:
Sender: sendet ein Telegramm wie beschrieben, mit B=0

Empfänger: wartet auf Daten, wenn alle Daten beisammen sind (Anzahl der Bytes nach dem Telegrammkopf stehen ja in R). Kommen zu lange keine/nicht genug Daten rein (Timeout z.B. 100ms), wird die Nachricht verworfen. Sind alle Bytes vollständig und rechtzeitig im Speicher versammelt, führt der Empfänger eine CRC-Prüfung durch und sendet das Ergebnis zurück.

Sender: prüft den CRC-Wert. Stimmt der CRC, wird der Telegrammkopf zurückgesendet, diesmal mit B=1. Stimmt der CRC nicht, wird das ganze Telegramm nocheinmal (inkl. Telegrammkopf, wieder mit B=0), gesendet.


Nun will ich das Ganze in Code gießen und komme damit nicht recht zu Rande. Ich hab so einige Knoten im Hirn-wie lösen Informatiker sowas auf?

Das gleich sofort in Java runterzucoden hab ich gar nicht erst probiert, ich scheitere momentan schon an einem UML (mach ich mit Flowgorithm) für diese Angelegenheit. Zu viele If-Abfragen, das Ganze wird recht schnell ziemlich anstrengend.

Kann mir da irgendjemand helfen?

Nachtrag:
Ich sollte vielleicht noch etwas zu einigen Umständen schreiben, die mir das Leben schwer machen.

Der o.g. Algorithmus soll in einem eigenen Thread laufen. Im Wesentlichen hab ich eine Dauerschleife angedacht, wenn die Schleife beginnt wird erstmal überprüft ob überhaupt neue Daten reingekommen sind. Wenn ja, gehts weiter-wenn nicht, geht der Thread wieder schlafen.

Bisher hab ich mich nur der Empfängerseite am PC gewidmet-aber wie bringe ich in diesem Thread auch das Sende-Verhalten unter? Etwas Besseres als ein einfaches "ReadOrWrite"-Boolean ist mir nicht eingefallen.

while(true){
if(readoperation){
//Empfängercode
}
else{
//Sendecode
}
}
So richtig überzeugt hat mich das allerdings noch nicht. Vor allem: was mache ich, wenn beide, Computer und Mikrocontroller, gleichzeitig auf die Idee kommen etwas senden zu wollen?

Wie lösen diejenigen, die sowas jeden Tag machen, sowas?

[HaWe]

ich habe etwas ähnliches in Verwendung, das vlt als Basis dienen könnte:
wechselweise Nachrichten, feste Länge, Senden/Empfangen+Zurücksenden immer im Handshake, samt CRC, samt Timeout mit Neusenden falls keine Antwort, samt Neu-Sync und Neu-Einlesen bei Verbindungsunterbrechung im Sendestream.
Das muss ntl auf deine Bedürfnisse angepasst und erweitert werden.
Gleichzeitiges Senden wird durch den Handshake unterbunden, der aber noch ein Timeout zulässt, trotzdem könnte man noch zusätzlich ein Token einführen, welches nach einer gewissen Zeit verfällt bzw. automatisch an den Master zurückgeht (wie im Token Ring).
Funktioniert bei mir zwischen Arduino Due (wegen Multithreading) und Raspi als PC oder alternativ einem 2. Arduino.

Interesse?

ps,
das Neusenden kann einfach über das ack-Byte veranlasst werden (wenn ack=0, dann sofortiges Neusenden, ansonsten bei Bedarf eine neue Nachricht) - das hatte ich ursprünglich auch bei mir mit drin, aber wieder gelöscht, weil es für meine speziellen Zwecke (u.a. Geschwindigkeit im Muxer- plus Remote-Betrieb) überflüssig war.

[Peter(TOO)]

Hallo allerseits

Folgende:
Ich entwerfe momentan ein Kommunikationsprotokoll damit sich ein Laptop und ein Mikrocontroller verstehen. Das Ganze stelle ich mir folgendermaßen vor:

Ein Telegramm (ich hoffe der Fachterminus ist richtig) besteht aus einem "Kopf" aus vier Bytes und einem Rumpf, der zwischen 0 und 255 Bytes enthält.
xxxx xxxB | xxxx xxxx | xxxx xxxx | RRRR RRRR

Bedeutet:
B - Bestätigungsbit
R - Anzahl der Bytes im Rumpf
x - Freie Bits oder weitere Informationen über die Daten im Rumpf, für die eigentliche Kommunikation jedoch hier nicht wichtig

Ich würde den Aufbau ändern:
yyyy yyyB | RRRR RRRR | xxxx xxxx | xxxx xxxx | cccc cccc

y = Telegramm-Typ
c = CRC

Hat sich so bei meinen Protokollen bewährt.

Wenn du die Länge schon am Anfang kennst, weisst du wie gross der Puffer sein muss und wann die CRC kommt.
Grundsätzlich kann dann der Rumpf auch unterschiedlich lang sein. Wenn du die Rumpflänge nicht kennst, weisst du nicht wo die Längenangabe steht.

MfG Peter(TOO)

[White_Fox]

@HaWe:
Ja, sehr gerne. :)


@Peter:
Die Idee mit den unterschiedlichen Telegrammtypen gefällt mir. Würde andere Schwierigkeiten, die ich mit meinem bisherigen Protokollentwurf noch sehe, lösen. :)


Allerdings steh ich immer noch vor der Frage: Wie entwickelt man Algorithmen, wenn es mit zwei simplen Rechenoperationen und einer boolschen Auswertung nicht mehr getan ist?
Ich denke da an sowas wie das Karnaugh-Veitch-Diagramm und Wertetabellen um boolsche Gleichungen aufzustellen. Gibt es für meine Aufgabe da auch ein Werkzeig? Ich kann mir schwer vorstellen daß Informatiker einfach nur im Kopf lauter If-Abfragen durchexerzieren und irgendwann ein UML da rauspressen. Das erscheint mir viel zu mühselig und...unstrukturiert.

[HaWe]

@HaWe:
Ja, sehr gerne. :)

dann bitteschön:
hier ist der Basiscode:
http://www.mindstormsforum.de/viewtopic.php?f=78&t=8689&start=30#p67815

und hier eine Anwendung zur Fernsteuerung und zum Monitoring (schrittweise runterblättern!):
http://www.mindstormsforum.de/viewtopic.php?f=78&t=8851#p69042

[Peter(TOO)]

Hallo White_Fox,

Die Idee mit den unterschiedlichen Telegrammtypen gefällt mir. Würde andere Schwierigkeiten, die ich mit meinem bisherigen Protokollentwurf noch sehe, lösen. :)
Ich habe so 20 Jahr Protokolle implementiert, sowohl genormte wie auch eigene. Da ist etwas Erfahrung hängen geblieben.


Allerdings steh ich immer noch vor der Frage: Wie entwickelt man Algorithmen, wenn es mit zwei simplen Rechenoperationen und einer boolschen Auswertung nicht mehr getan ist?
Ich denke da an sowas wie das Karnaugh-Veitch-Diagramm und Wertetabellen um boolsche Gleichungen aufzustellen. Gibt es für meine Aufgabe da auch ein Werkzeig? Ich kann mir schwer vorstellen daß Informatiker einfach nur im Kopf lauter If-Abfragen durchexerzieren und irgendwann ein UML da rauspressen. Das erscheint mir viel zu mühselig und...unstrukturiert.
Ich habe das immer über State Diagramme gemacht (Zustandsübergangsdiagramm).
Daraus kann man direkt eine State Machine codieren.
Diese State Machine habe ich dann direkt als Interrupt-Routine verwendet. Bei jedem Interrupt muss nur ein einzelnes Zeichen verarbeitet werden, Fehler können teilweise direkt erkannt werden und mit dem letzten Zeichen ist auch das ganze Telegramm ausgewertet, schneller gehts nicht.

Für die Zustandsübergangsdiagramme gibt es mittlerweile auch eine Reihe von Tools:
https://de.wikipedia.org/wiki/Zustands%C3%BCbergangsdiagramm#Werkzeuge

Zudem ist das ganze auch un UML (Zustandsdiagramm (UML)) vorhanden.

MfG Peter(TOO)
P.S.
Ich habe mich zudem immer am OSI-Schichtenmodell orientiert. Wobei man nicht alle 7 Schichten wirklich getrennt implementieren muss, man kann für einfache Protokolle meistens mehrere Schichten zusammenfassen.

[White_Fox]

Mensch Peter...Zustandsübergangsdiagramme, da hab ich doch schonmal was von gehört. Das scheint mir genau das zu sein nach dem ich suche... :)

[Peter(TOO)]

Mensch Peter...Zustandsübergangsdiagramme, da hab ich doch schonmal was von gehört. Das scheint mir genau das zu sein nach dem ich suche... :)
Findest du auch in Datenblättern. Ein kleines einfaches bei den meisten µCs, wenn es um Reset, Sleep usw. geht.

Ich hatte mal ein recht komplexes für eine Maschine gezeichnet. Waren so 20 bis 30 Seiten. Hatte ich dann bei mir an die Wand geklebt und die Transitions mit farbiger Nähseide markiert. War sonst zu mühsam die Labels immer auf den Blättern zu suchen.

[White_Fox]

Ok...ich schätz ich weiß wie ich es (zumindest auf der PC-Seite) angehe. Da gibt es ein prima Entwurfsmuster, um einen Zustandsautomaten zu realisieren, da hatte ich doch unlängst ein klasse Buch in der Hand (Entwurfsmuster von Kopf bis Fuß-äußerst empfehlenswert).

In Java kann ich das gut machen, aber in C (ich will das ja noch einen Mikrocontroller programmieren) leg ich mir damit die Karten. Na-aber auch das Problem erschlag ich schon irgendwie. Erstmal das Ganze in Java zum Laufen bringen (das wird mit einem ausführlichen Unit-Test eh lang genug dauern...)

Vielen Dank für eure Anregungen bisher. Ich rolle den Thread wieder auf wenn ich das in C implementiere... :)

[Peter(TOO)]

Ok...ich schätz ich weiß wie ich es (zumindest auf der PC-Seite) angehe. Da gibt es ein prima Entwurfsmuster, um einen Zustandsautomaten zu realisieren, da hatte ich doch unlängst ein klasse Buch in der Hand (Entwurfsmuster von Kopf bis Fuß-äußerst empfehlenswert).
Wenn du den Automaten gezeichnet hast, kannst praktisch direkt ab der Zeichnung codieren. :-)

Zuerst gibt es einen grossen Switch mit allen Zuständen.
In jeden Zustand siehst du dann, welche Bedingung in welchen anderen Zustand wechselt und was zu tun ist.
Bis du das zusammen, und auch alle Ausnahmen berücksichtigt, hast, musst du am Meisten Nachdenken.

Das State-Diagramm ist wie eine Flow-Chart, die Codierung ist wirklich nur einen Fleissarbeit. :-)
Zumindest für mich war das dann der langweilige Teil der Arbeit.

[White_Fox]

Ja, das Codieren selber find ich auch nicht allzu spannend. Die Denkarbeit reizt mich auch mehr, naja...
Wobei die Implementierung eines Zustandsautomaten mit Klassen deutlich einfacher geht als mit einer riesigen Switch-Anweisung. :)



Eine Frage zu deinem Protokoll-Kopf hab ich noch:
Du schickst den CRC gleich sofort mit. Warum, wo ist da der Vorteil?
So wie ich das am Anfang machen wollte, ist der CRC kein Bestandteil des Telegramms. Den Teil, wo der CRC enthalten ist, kann ich ja schlecht in die Prüfsummenberechnung einschließen, da das Ergebnis zur Zeit der Berechnung selbstverständlich nicht bekannt ist.
Also...warum hast du es so gelöst?

[Peter(TOO)]

Eine Frage zu deinem Protokoll-Kopf hab ich noch:
Du schickst den CRC gleich sofort mit. Warum, wo ist da der Vorteil?
So wie ich das am Anfang machen wollte, ist der CRC kein Bestandteil des Telegramms. Den Teil, wo der CRC enthalten ist, kann ich ja schlecht in die Prüfsummenberechnung einschließen, da das Ergebnis zur Zeit der Berechnung selbstverständlich nicht bekannt ist.
Also...warum hast du es so gelöst?
Die Prüfsumme wird als letztes angehängt, zu diesem Zeitpunkt ist alles bekannt.
Die Prüfsumme befindet sich übrigens auf OSI-Layer 2 Wobei in der Beschreibung Level 2 und 3 teilweise zusammengefasst sind, bzw. nicht sauber getrennt werden, weil dies mehr Daten ergäbe.
OSI ist nur eine Empfehlung und Stütze, kein Zwang!

BTW: Prüfsumme und CRC sind zwei etwas unterschiedliche Verfahren.

MfG Peter(TOO)

[HaWe]

ich schicke die Prüfsumme auch gleich mit, dann kann der Empfänger die Prüfsumme nach Empfang sofort nachrechnen und mit der mitgeschickten vergleichen, und sieht dann sofort, ob alles ok ist mit der Nachricht.

[Holomino]

Der Härtetest ist die abreißende Verbindung. Wenn also der Stecker gezogen und anschließend wieder angesteckt wird (oder die Funkverbindung mal kurzfristig abreißt), sollten beide Seiten störungsfrei weiterlaufen.
Wenn das funktioniert, ist das Protokoll gut.:p

[HaWe]

Der Härtetest ist die abreißende Verbindung. Wenn also der Stecker gezogen und anschließend wieder angesteckt wird (oder die Funkverbindung mal kurzfristig abreißt), sollten beide Seiten störungsfrei weiterlaufen.
Wenn das funktioniert, ist das Protokoll gut.:p

ja, das ist bei meinem Algorithmus sichergestellt, Vorraussetzung ist, dass wenigstens einer von beiden weiterläuft.
Wenn beide aus sind, stellen sie erst wieder eine neue Verbindung automatisch her, wenn sie beide wieder an sind, das ist ntl klar, aber auch das muss nicht gleichzeitig sondern kann auch zeitversetzt passieren.