Casse-tête.

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From French to

Threaded View
Bonsoir la foule,

Voici un petit problE8%me intE9%rE9%ssant,
pas de l'E9%lectronique mais bon pour les mE9%ninges :
j'ai sur un bus un rE9%seau de cartes
que je voudrais numE9%roter automatiquement.
(je vais tenter une description en mode tE9%lE9%graphique)

Soit un bus avec un maitre et N esclaves. Les E9%changes
se font via un protocole (genre JBUS) qui inclut le
numE9%ro d'esclave [ 1...N ] auquel le maitre s'adresse,
et on rE9%serve le numE9%ro zE9%ro pour s'adresser E0% tous.
Ni le maitre ni aucun esclave n'envoient de
trame sur le bus si celui-ci est dE9%ja occuppE9%.
(chaque esclave recoit toutes les trames, mais ne prend en
compte que celle qui lui est adressE9%e par son propre numE9%ro,
et dans ce cas il rE9%pond au maitre. Seule la trame de
numE9%ro zE9%ro sera prise en compte par tous les esclaves,
et dans ce cas aucun ne rE9%pond - sinon il y a collision)

Ceci E9%tant posE9%, voici ce qu'il faut rE9%soudre :
Sachant qu'E0% la toute premiE8%re mise sous tension,
aucun esclave n'a de numE9%ro, comment le maitre peut-il
attribuer E0% chacun un numE9%ro unique dans [ 1...N ] ?

--------

J'ai pensE9% E0% cet algo :
le maitre envoie E0% tous les esclaves une trame signifiant
AB% voici un numE9%ro, qui en veut ? BB%
Chaque esclave n'ayant pas encore de numE9%ro rE9%pond
AB% moi je veux bien BB%,
le maitre renvoie un acknowledge signifiant :
AB% ok, alors garde-le BB%
puis passe au suivant.
L'astuce consiste E0% ce que chaque esclave, avant de rE9%pondre,
attende pendant une durE9%e alE9%atoire comprise entre 0 et N-1,
(ou que chaque esclave ne rE9%ponde qu'avec une probabilitE9% 1/N)
afin d'E9%viter les collisions avec une probabilitE9% non nulle.

Deux cas possibles :

1B0%) Plus d'un esclave rE9%pond en mEA%me temps :
il y a collision, la trame est perdue, le numE9%ro
courant n'est pas attribuE9%, et le maitre rE9%itE8%re.

2B0%) Un esclave rE9%pond avant tous les autres :
les autres esclaves voyant passer sa trame se taieront,
le maitre recevra sa rE9%ponse et lui reverra l'acknowledge,
le numE9%ro sera attribuE9%,
le maitre passe E0% l'attribution suivante.

MEA%me si l'attribution dE9%pend du dE9%lai alE9%atoire
(ou de la proba en 1/N) nE9%cE9%ssaire E0% l'anti-collision,
pour une vitesse de bus assez E9%levE9%e et un nombre
d'esclaves pas trop grand, aprE8%s un temps fini 'T'
on atteindra TOUJOURS la limite oF9% chaque esclave
prE9%sent sur le bus aura un numE9%ro unique attribuE9%.


PremiE8%re question : vaut-il mieux que les esclaves :
- Attendent pendant une durE9%e alE9%atoire comprise entre 0 et N-1.
- Ne rE9%pondent qu'avec une probabilitE9% 1/N.


Seconde question : y a-t'il une faille dans cet algo,
qui ferait que ca ne fonctionne pas du tout,
ou est-ce que ca tient bien la route ?

Re: Casse-tête.
Le 11/10/11 22:49, Jean-Christophe a écrit :
Quoted text here. Click to load it

Quand un serveur DHCP attribue les IP dans un réseau ethernet,
l'identification des paquets se fait sur l'adresse MAC de la carte
réseau. Dans ton cas, si plusieurs esclaves répondent presque en même
temps comment vont ils savoir à qui la réponse du master est adressée?
Pendant la procédure d'attribution du numéro il faudrait que les
esclaves signent leur paquet (avec un checksum aléatoire ou autre) et
que le master renvoie cette signature dans sa réponse.

Re: Casse-tête.
Julien Arlandis a tapoté du bout de ses petites papattes :
Quoted text here. Click to load it

Elle est adressée au premier qui répond si j'ai bien compris. Donc
aucune ambigüité. S'il y a chevauchement, donc collision, toutes les
cartes la détectent, annulent, et la procédure recommence.

Moi je ne vois pas de faille, mais je trouve ça lent et compliqué. En
plus, ça n'est utile/possible que si toutes les cartes sont les mêmes
et n'ont pas d'entrées/sorties spécifiques (ou alors il faut une
deuxième passe de la carte maitre pour interroger toutes les cartes
esclaves par leur numéro pour leur demander ce qu'elles font et/ou à
quoi elles sont connectées, ce qui complique encore un peu plus).

On peut savoir à quoi c'est censé servir ?

--
LeLapin



Re: Casse-tête.
On 11 oct, 23:30, LeLapin

Quoted text here. Click to load it

C'est bien ca.

Quoted text here. Click to load it

Si ca tourne (par exemple) E0% 115 kbps et qu'on a des time-out assez
courts,
ces trames-lE0% ne prendront pas plus de 8 octets, etc.
On laisse le truc tourner dans son coin pendant qu'on fait autre chose
d'utile.
L'important est que l'algo finisse E0% coup sFB%r par attribuer un numE9%ro
unique E0% chaque carte.
( bon, ok, lE0% je dE9%fends ma crE8%merie, mais si tu as une idE9%e, on en
discute :o)

Quoted text here. Click to load it

Aucun problE8%me : une fois les numE9%ros attribuE9%s,
chaque carte peut ensuite rE9%pondre E0% une demande d'identification
via un code spE9%cifique inclus dans le protocole.

Quoted text here. Click to load it

C'est un sous-ensemble d'un truc plus vaste pour une
E9%tude pro alors dE9%solE9% de ne pouvoir dE9%tailler le reste.
Mais en gros voilE0% le topo, qui reste assez gE9%nE9%rique :
un bus, du monde dessus, et l'idE9%e de paramE9%trer le matos
*automatiquement* sans avoir un gus pour positionner
des straps sur chaque carte, ni leur attribuer un numE9%ro
en les branchant une par une sur le bus, etc.
(bref : un bon algo, et les bE9%canes se dE9%merdent entre elles)

Re: Casse-tête.
On 11 oct, 23:12, Julien Arlandis

Quoted text here. Click to load it

Oui, mais ici toutes les cartes esclaves sont identiques,
le hard et le soft sont tous les mEA%mes ( prod sE9%rie )
et on a aucun moyen de les discerner :
pas de strap ni de puce ayant un identifiant unique.


Quoted text here. Click to load it

A moins que je n'ai pas compris ton objection (?)
ce cas est dE9%ja pris en compte :

 | 1B0%) Plus d'un esclave rE9%pond en mEA%me temps :
 | il y a collision, la trame est perdue, le numE9%ro
 | courant n'est pas attribuE9%, et le maitre rE9%itE8%re.


Quoted text here. Click to load it

Mon protocole de com inclut bien un CRC16 pour
vE9%rification de non-corruption des trames recues.

Re: Casse-tête.
Jean-Christophe a tapoté du bout de ses petites papattes :
Quoted text here. Click to load it

Minimum indispensable pour la détection de collision.

--
LeLapin



Re: Casse-tête.
Le 11/10/2011 23:33, Jean-Christophe a écrit :
Quoted text here. Click to load it

Comment se passe la détection d'une collision ?
Le signal est détruit par interférences ?

Re: Casse-tête.
"Julien Arlandis"

Quoted text here. Click to load it

Oui : le CRC sera faux donc la trame sera rejetée.

Dans le cas où plusieurs esclaves répondent en même temps,
la collision entrainera le rejet de ces réponses,
donc le maitre n'enverra même pas de confirmation,
et réitérera le numéro courant non encore attribué.



Re: Casse-tête.
Le 11/10/2011, Jean-Christophe a supposé :
Quoted text here. Click to load it

Toute cette histoire est un peu aléatoire.
Je m'explique: que se passe-t-il le jour où un module esclave tombe en
panne?
On le remplace (en plus il  n'y a pas de switch à régler), mais quelle
adresse va lui être attribuée ? S'il reçoit une nouvelle adresse,
l'application côté maître doit être modifié. Comment ?
Bref tout un tas de questions qui influent le système dans sa
globalité.
Pour avoir côtoyé divers systèmes maître/esclave (Profibus,
Modbus/Jbus)
les esclaves étaient toujours adressés avant mise en service. Leur
adresse étant en rapport avec leur fonction dans le projet.

--
In gold we trust (c)



Re: Casse-tête.
 "Jo Kerr"

Quoted text here. Click to load it

Sur un groupe de N esclaves tous numérotés par le maitre,
si on en remplace un seul, alors le numéro qui lui
sera automatiquement attribué sera forcément le même.
( cela découle de l'algo décrit précédemment )

Quoted text here. Click to load it

Il ne peut pas recevoir une adresse différente
car toutes les autres N-1 adresses sont déja attribuées.

Quoted text here. Click to load it

Pas à mon sens.

Quoted text here. Click to load it

Oui, tout à fait.

Quoted text here. Click to load it

Oui j'entends bien, mais ici le but est de numéroter automatiquement,
et sans aucune intervention manuelle sur chacun des boitiers.
Leur identification se fait après numérotation, et pour chaque carte
le maitre peut donc identifier de quel type il s'agit
( sur ce sujet, voir ma réponse à LeLapin )




Re: Casse-tête.
Jean-Christophe a tapoté du bout de ses petites papattes :
Quoted text here. Click to load it

Ca simplifierait beaucoup si tu mettais une daisy chain.

--
LeLapin



Re: Casse-tête.
"LeLapin"

Quoted text here. Click to load it
.
Mais ca allongerait sensiblement les temps
de com avec les cartes situées en fin de chaine.
Et la topologie existe déja : un seul bus
avec tout le monde dessus, en parallèle.
( pas en série, Zarkon nous en protège )

Tant que le principe proposé est OK alors ca me va.
Bien sûr, si quelqu'un a un autre algo à proposer, je suis preneur.

( j'ai d'autres questions à venir mais avant ca
il faut déja valider/invalider ce point-là )



Re: Casse-tête.
Quoted text here. Click to load it
car toutes les autres N-1 adresses sont déja attribuées.

Et si tu en a deux qui crament simultanément ?

Cela implique que le nombre d'adresse possible soit identique au nombre de
cartes, quelles soit dispo en permanence

De toute façon chaque carte va avoir une fonctionnalité et une seule sinon
je ne vois pas comment cela peut marcher, donc tu va bien être obligé de
leur mettre un codage fonctionnel fixe, qu'il soit sur programmable sur la
carte ou en externe.


Quoted text here. Click to load it

Et ton maitre quelle adresse ? Il lui en faut bien une


Quoted text here. Click to load it
« voici un numéro, qui en veut ? »

Non, imagine que tu allume une carte sup ou qu'il y ai un plantage sur une
comment le maitre va le savoir pour lui proposer une adresse ?


Respecte le protocole DHCP ( tu peux le simplifier puisque tu n'aura qu'un
seul serveur ), ton client sans adresse contacte le maitre et lui demande
une adresse avec sa fonction, le maitre propose une valeur d'adresse, le
client lui accuse réception . Tu n'utilise pas de bail, pour simplifier les
choses.

Pour la gestion des collisions de toute façon cela va être intégré dans ton
protocole de comm standard, car je suppose que la comm peut être a
l'initiative du maitre ou des clients, au besoin tu adapte tes trames pour
une longueur fixe et un crc, au besoin tu t'inspire d'ethernet





Re: Casse-tête.
On 12 oct, 14:32, "JP"

Quoted text here. Click to load it

Et pourquoi pas 70 cartes qui crament en mEA%me temps ?
Cela ne concerne pas la question posE9%e, qui est d'assigner
automatiquement un numE9%ro unique E0% chaque esclave.

Quoted text here. Click to load it

Le maitre maintient une table du nombre de cartes trouvE9%es,
et les correspondances index->numE9%ro.

Quoted text here. Click to load it

Pour l'instant, chaque carte esclave est identique,
je l'ai dE9%ja dit dE8%s le dE9%but. Si tu changes les
termes de ma question, ta rE9%ponse n'y rE9%pond plus.
( je comprends ton contre-argument,
mais il n'est pas de mise pour l'instant )

Quoted text here. Click to load it

Nous sommes donc d'accord (pour l'instant)

Quoted text here. Click to load it

Non.


Sur le bus maitre/esclaves, le maitre n'a pas besoin
d'adresse, car il n'est jamais adrE9%ssE9% par un esclave.
Le maitre s'adresse aux esclaves, les esclaves ne
prennent jamais l'initiative d'envoyer un message
sur le bus SAUF en rE9%ponse E0% une requE8%te du maitre.

(ceci dit, au niveau supE9%rieur de la hiE9%rarchie,
chaque maitre de chaque sous-groupe d'esclaves est
lui-mEA%me sur un autre bus reliE9% E0% un PC, mais cela ne concerne
plus la question posE9%e E0% l'origine et on s'E9%loigne du sujet)

Quoted text here. Click to load it

Non : lors de l'install sur site, on installe
TOUTES les cartes sur le bus avant numE9%rotation.

Quoted text here. Click to load it

Si une carte est plantE9%e elle ne rE9%pondra plus au requE8%tes
du maitre, qui saura donc que cette carte-lE0% est HS.
(et si elle est HS ca ne sert E0% rien
de tenter de lui rE9%attribuer un numE9%ro)

Quoted text here. Click to load it

J'ai posE9% dE8%s le dE9%but la condition que
chaque esclave est rigoureusement identique.
Donc pas d'identifiant hard ni soft.


Re: Casse-tête.
Le 12/10/2011, Jean-Christophe a supposé :

Quoted text here. Click to load it

Donc il y a une identification de chaque carte dans le logiciel
embarqué.
Pourquoi ne pas intégrer l'adresse esclave dans ce même logiciel (ça se
fait) et on éviterait bien des problèmes et aléas.

--
In gold we trust (c)



Re: Casse-tête.

Quoted text here. Click to load it

Ce qui prE9%cE8%de est ce que j'ai dit au tout dE9%but.
 ----
Ce qui suit est une rE9%ponse E0% une supposition (fausse) faite
par un intervenant : que les esclaves ne sont pas tous identiques.

Quoted text here. Click to load it


Non - pour l'instant - ce sont toutes les mEA%mes.

Quoted text here. Click to load it

Je rE9%pE8%te que les esclaves sont tous identiques :
mEA%me hard, mEA%me soft.

Re: Casse-tête.
Le 12/10/2011, Jean-Christophe a supposé :


Quoted text here. Click to load it

Ok, mais comment se distinguent-ils, ou comment sont-ils "identifiés"?
Car tu disais:
Quoted text here. Click to load it

Ce qui laisse supposer qu'il y a des "types" différents.

--
In gold we trust (c)



Re: Casse-tête.
On 13 oct, 11:15, Jo Kerr

| Je rE9%pE8%te que les esclaves sont tous identiques :
| mEA%me hard, mEA%me soft.

Quoted text here. Click to load it

Par le numE9%ro que le maitre leur attribue.

Quoted text here. Click to load it
|| Leur identification se fait aprE8%s numE9%rotation, et pour chaque
carte
|| le maitre peut donc identifier de quel type il s'agit
Quoted text here. Click to load it

Ce qui prE9%cE8%de est une rE9%ponse (malheureuse)
E0% une supposition (fausse) faite par un intervenant,
qui proposait que les esclaves ne soient pas tous identiques :
comme je l'ai dit au dE9%but du message auquel tu rE9%ponds !
http://groups.google.com/group/fr.sci.electronique/msg/b05d0ec2ff5004c2

Donc, les esclaves sont tous identiques : mEA%me hard, mEA%me soft.
( lE0%, on tourne en rond ... )

Pour l'instant le principe de numE9%rotation automatique tient la route.
Bien sFB%r que si quelqu'un a un autre algo E0% proposer, pour les
mEA%mes conditions (tous esclaves identiques) je suis preneur.

Quand E0% cet algo il reste une question : vaut-il mieux que les
esclaves
- Attendent pendant une durE9%e alE9%atoire comprise entre 0 et N-1.
- Ne rE9%pondent qu'avec une probabilitE9% 1/N.

(ca marche dans les deux cas, mais je suppose que l'un est plus rapide
que l'autre)


Re: Casse-tête.
Quoted text here. Click to load it
( là, on tourne en rond ... )

Ce qui me gêne, même hard, soft ca c'est courant et n'est pas grave, même
fonctionnalité a la limite pourquoi pas si ce sont eux qui gèrent leur truc
et s'adressent a un serveur, mais en plus totalement esclave d'un process
central la je tique un peu.

Ton maitre va s'adresser a des trucs  choisis aléatoirement et leur dire de
réaliser quelque chose, cela peut se comprendre sur une demande de process
ou de calcul, mais si tu a une interface avec le monde réel, je ne vois pas.



Re: Casse-tête.

Quoted text here. Click to load it

C'est pourtant une topologie assez usitE9%e.

Quoted text here. Click to load it

Non, ce n'est pas comme ca que ca marche.

Quoted text here. Click to load it

Oui, je m'y attendais un peu :o)
Les esclaves sont effectivement des unitE9%s de traitement dE9%portE9%es
d'E9%vE8%nements physiques, et sont rE9%guliE8%rement scannE9%s par le mait=
re.
De plus, il y a plusieurs de ces rE9%seaux, dont tous les maitres sont
sur un autre bus - distinct - reliE9% E0% un PC ( disons-le comme ca )

Bon, c'est normal que quand le cahier des charges
n'est pas entiE8%rement dE9%voilE9%, il y ait des mecs
qui posent des questions aussi lE9%gitimes que gEA%nantes !
Mais bon, si je ne peux vraiment pas entrer dans le dE9%tail,
je sais aussi que certains connaissent ce genre de situation.
Donc, si vous l'acceptez, on reste sur ce sous-ensemble,
juste histoire de valider/infirmer ce rogntudju d'algorithme,
ou d'en proposer un autre, ok ?
Parce-que j'ai d'autres questions en suspens ...

Site Timeline