My protocol Adressing problem.

A protocol I am writing has a problem. I was wondering if any of the many smart people around here has a solution.. or could point me to a protocol that has this all sorted.

Packets of data are send src dst address over a two three wire bus like I2C, interconnecting several MCU's, Like I2C this protocol has a General Address.

Here is my problem.

Below is the section of the protocol that deals with addresses and how to do dynamic allocation of addresses. but if two devices both send the Device Address Set Command at the same time, say when they are turned on, then forever will they by bouncing commands back and forth untill they both overflow thr addresses.

Is thr any method I can use to prevent this from going on?

General Address A General Address is only valid as a Destination Address. All nodes must listen for packets sent to this address and process them.

Dynamic Address Self-Alocation on the General Address

The node wishing to assign it self an address should pick the first address number (a=1) and send a Device Address Set Command to the General Address.

This will inform all other Nodes of the New Nodes Address. If the Src Address Matches that of any reciever then the Reciever, who has the matching address, should send a Device Address Respond Command to the General Address.

So any Node that recieves a Device Address Response Command with a Source matching it's own must select a new address (a+1) and try this address repeating the above steps.

If the the address overflows trying to self assign then there must be 255 addressed devices in the Node Collection, in this case this node should send no more messages on the Bus.

DaveC

Reply to
DaveC
Loading thread data ...

... I take it that this is a multimaster network, probably with some form of collision detection?

How about a random delay on collision? That's how most multimaster networks resolve this type of conflict. Of course you'll need some form of seed for a random number generator. This is often a serial number, mac address, or based on the least significant bits of a noisy analog input. You just need to find something that's *very* likely to be different between individual network nodes.

Cheers, Alf.

Reply to
Unbeliever

"Unbeliever" wrote in news:40d00e2f$0$5583$ snipped-for-privacy@news.optusnet.com.au:

That's it!!.. All my devices have unique serials

Thanks Alf

Reply to
DaveC

For an example of address allocate via serial#, you can look at the microchip 24LCS61/62 devices.

-jg

Reply to
Jim Granville

Take that thought one step further and say the lowest serial number wins, and only one device needs to try again.

Maybe you could even hash your serial nubers into addresses.

- Tom

Reply to
Thomas Carley

"Thomas Carley" wrote in news:Ac2dnZhCu9C8sE3dRVn- snipped-for-privacy@comcast.com:

The Serial is made from the following.

11 Device Manufature + 16 bits 12 Device Product ID + 8 bits 13 Device Product Version + 8 bits 14 Device Serial Number + 16 bits

6 Bytes in total.. so my next trick is working a way to encode this into a simple seed.. My address is 1 byte. I thought just adding all the bytes together and ignoring the overflow, or perhaps ones compliment. Still a chance that two devices will be the same.

Then take that one byte and set the tmr on thr MCU to pause that long,

or

Pause for 1ms dec that byte each time (255 ms is ok in this case)

or

Transmit Serial Sum byte along with the "Device Address Set Command" so ,... like you say the reciever will respond with this Serial Sum byte.. and so the sender will know its identification even though it does not have an address at that stage..

I think that is it.. and I only just typed it. Thinking is over-rated.

Thanks every one.

DaveC

Reply to
DaveC

In general I think it is a better idea of letting the new node do the work of finding a unique address, rather than forcing an existing node to change its address. If the node id is used by other nodes, say for communications addressing, suddenly changing an address complicates ongoing transactions. Also, forcing an address change can cause a ripple through the network, while making the new node find its own doesn't. Finally, it only seems right that the new kid on the block has to pay his dues to fit in!

Thad

Reply to
Thad Smith

Thad Smith wrote in news: snipped-for-privacy@acm.org:

Hi Thad.. I think, there has been some confusion.. Must probebly due to my bad tech writing style. I've altered the above approch based on some ideas from other posts.

Lets call the new Node C and two existing Nodes A & B The existing addresses are A = 1 B = 2 C = 0

STEP 1: When C comes on to the network it will

- Set its own address. C += 1 ( c=1 first time)

- send a Device Address Set Command to all Nodes (This command will have the src address = 1 and the dst = 0 and includes a unique 5 byte serial number for the Node)

STEP 2: Node A & B will get this command

- Node B will ignore it but,

- Node C will action it because the src address = it's own address Node C will send a Device Address Respond Command to all nodes (This command will have the src address = 1 and the dst = 0 and includes the recieved unique 5 byte serial number of Node C)

STEP 3: All nodes will get this but only Node C will action it based on the following rule.

- Any node that recieves a Device Address Respond Command with the 5 byte code matching it's own should goto STEP1:

STEP 4: If Node C gets no instruction to change its address by the time it Masters the bus again then it may asume that no other Node on the Bus has the same address and to may start sending general commands.

The end DaveC

Reply to
DaveC

SNIP:

I forgot a couple of important Rules. That I hope will avoid the case where Nodes C & D both try to start Address Resolution at the same time.

In the above example we will say Node C is in Address Resolution Mode while A & B are in Run Mode.

Address Resolution Mode;

- Add one (a+=1) to address on reception of Device Address Set Command send to all nodes. But discard this packet.

- Do not send Device Address Respond Commands

Run Mode;

- Buffer only one Device Address Set Command while in Slave Mode. All others will be silently discarded.

Ofcourse all these rules only work on a Bus like I2C where one Node can master at a time. I'm not sure of other bus protocols. I wish to make it as flexable as I can.

Another idea was to had was to ensure that one devices was at address one and only it issued addresses to new Nodes. but that puts the burdon of the Node having to keep a full address table.

DaveC

Reply to
DaveC

DaveC wrote: [...]

Typo alert: looks like both the above "Node C" should be "Node A" instead.

So, in a little more figurative terms: the new kid on the block goes around yelling "I'm going to call myself 'X'", and only relent on that once it receives a punch to the face from one of the residents explaining it that 'X' is already taken. Repeat until no punch within the expected punch time interval.

Problems with this approach:

  • Current holder of name 'X' may have been too busy to punch the new arriver in time. Confusion or bloody battle ensues.

  • The process is rather lengthy. It takes O(N) punch times on a net of N participants, and O(N^2) to get the whole thing running after power-up, when nobody has a name yet.

To avoid both problems, revert the scheme to the way waiting in lobbies works: the new kid arrives, and asks the general public: who was the last to arrive? Said person raises a hand, and gives his ID. New kid uses ID+1. Or use a central 'draw a number here' appliance.

--
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
Reply to
Hans-Bernhard Broeker

You still have a problem if you start up the network with several new devices that have not been an assigned an address. In order to fix this the device needs to be able to set up "talk" wait time for itself before it grabs the bus and starts talking again.

The one thing I do not like about this approach is if/when a device fails and you have many devices on the bus you have to use a hunt and peck tactic to find the bad device.

Reply to
Bradley

My version: Each device hashes its own id to a value N less than

255 and prime, call it P. It also rehashes its id to a second value M, also less than P. This is all just like a hash table. It then probes for an available address N, and if that fails tries for (N+M) modulo P. That way the search path will not be the same for all devices, and with a reasonable hash algorithm the process will be O(1) until the addresses are roughly 90% taken.

It may be easier to make the universal poll address 255, so that 0 is a usable device address.

You can probably simulate all this quite well using my GPLd hashlib system, available at:

--
fix (vb.): 1. to paper over, obscure, hide from public view; 2.
to work around, in a way that produces unintended consequences
 Click to see the full signature
Reply to
CBFalconer

CBFalconer wrote in news:40D2FF50.CF2279C1 @yahoo.com:

Did you lot see my own follow up to post you are RE'ing?

Nodes will have two basic Modes. Run mode and Address Allocation Mode (Start up). Below is the method I have a the moment.

it has the same origional problems, having to enquire all existing nodes from 1 up.

But it does work with "start up the network with several new devices " case. With out using any deleys. The "code" below works on the idea that in I2C Multi Master Mode, each device in turn can Master the bus while all others listen. I dont think it is restricted to I2C though, all is needed is a way to broadcase messages to all Nodes on the Bus.

Note that I'm using the term Bus not Network.

An alternative fix to what I've done below would be to have all Run Mode nodes send out that highest known address as an extra data byte to the Address Command.

int ownAddress = 1;

ADDRESS ALLOCATION MODE:

int tNodeCount = 1; int tMsgCount = 0;

Bus_Slave Mode:

- Ignore reception of all commands other then Address Sets - Upon reception of Address Set. - tMsgCount ++; - compair 5 byte serial in packet to own serial - If it's the same then let ownAddress = packet src address + tNodeCount - else tNodeCount++;

Bus_Master Mode:

- If tMsgCount == 0 then Goto RUN MODE

- tMsgCount = 0;

- Send out Address Request to General Address with ownAddress as src AddrReq src = ownAddr dst = 0 data = 5 byte serial

RUN MODE

Bus_Slave Mode:

- Upon reception of Address Set - compair packet src address with ownAddress - If they are the same then send Address Set Command AddrSet src = ownAddr dst = 0 data = Recieved Data

DaveC

Reply to
DaveC

In another posting of yours I read that your devices have unique serial numbers.

You could, if your protocol is software-based and under your control, implement a dominant/recessive handshake like CAN uses:

  1. A device, when connected to the bus, starts out in listen mode. If it detects bus activity, it becomes a SLAVE. If after a timeout of A ms, still no bus activity was detected, it becomes the (single) MASTER.
  2. When the new device is a SLAVE, it waits until an ENUMERATION packet is received, which will assign an address to the SLAVE. Before that happens, the SLAVE will stay quiet.
  3. The MASTER periodically sends ENUMERATION packets. The period must be shorter than timeout A, so that a new device always sees bus activity when a MASTER exists. The packet consists of the ENUMERATION command itself, followed by a dummy serial number with all bytes as 0xFF.
  4. If a SLAVE without address sees the ENUMERATION packet, it starts sending its serial number. Each '0' bit means that it asserts the bus, while a '1' bit means that the bus is left floating. The bus has a pullup somewhere, so that every listener reads a '1' when all SLAVEs "send" a '1'.
  5. While sending each bit, the SLAVE reads back the bus. If the SLAVE meant to send a '1' (leave bus floating), but the bus reads back as '0' (asserted), the only possible explanation is that _another_ SLAVE has asserted the bus in this bit slot. That means that the other SLAVEs' serial number is lower than ours, because at least one of its' bits is '0' where we have a '1'. We silently declare the other SLAVE as winner of this ENUMERATION and cease to send any more bits of our serial number. Instead we wait for the next ENUMERATION packet that will arrive within a timeout of A ms.
  6. A SLAVE that was able to send its complete serial number without any detected collision, is the winner of the ENUMERATION and receives an address from the MASTER. The MASTER is responsible of keeping track of addresses to not give out the same address twice.
  7. A SLAVE that already has an address assigned, does not join the protocol. Instead, when detectign the ENUMERATION packet, it simply ignores it (and the following serial number data).
  8. The MASTER knows that no new SLAVE was connected, when the ENUMERATION serial number reads back as all-0xFF. This was what the MASTER has sent, and no device altered any of it. Note: for this to work, you may not ever program a device to serial number all-0xFF.

Any N new devices connected simultanously to the bus, get their addresses assigned within (N+1)*A ms max.

Note that bit timing is essential for this. All new devices must send their data at the very same time, so that all bits line up OK. You may have to program this in assembler, and/or have tight control over interrupts in your devices. One option is to have a dedicated master that does not have any interrupts running, and to enable interrupts in the slave devices only after the address has been assigned.

While CAN uses such a protocol for each and every packet, and therefore needs tight control over bit timing for every bit, you don't actually have such a requirement. You can use a normal UART with 8N1, and once the address is assigned, you can switch to a very relaxed protocol.

Marc

Reply to
jetmarc

Perhaps this page can give you an idea :

formatting link

Rene

--
Ing.Buero R.Tschaggelar - http://www.ibrtses.com
& commercial newsgroups - http://www.talkto.net
Reply to
Rene Tschaggelar

Marc,

your post is almost identical to the protocol I have designed some time ago using UART.

Do you know a particular implementation of such protocol you have described ?

I have been also inspired by CAN (and also by LIN).

Or use 2 modes: the enumeration is low-baudrate software-based (for dominant/recessive handshake) and other communication uses hardware.

Now to your suggested process of assigning addresses:

What hapens if the master assigns the address but the SLAVE does not receive the assignment for any reason (bus noise etc) ? I believe the above method you have described automatically reenumerates during next enumeration.

Where is the +1 coming from ?

In my case the Master enumerates until there is anything to enumerate, i.e. keeps sending 0xFF to the bus until it actually sees 0xFF (i.e. all the devices have been enumerated during this enumeration). This is all one bus transaction. The device backs-up when sees the dominant when expects recessive, but tries to enumerate right after.

So using 9.6k,8N1 as enumeration baudrate and 48bit for SN, the bus enumerates in

(6.25ms*N+RQ)

where N is # of slaves and RQ is length of master's request. In the above case the theoretical enumeration rate is 160 devices per second (+RQ).

Roman

Reply to
Roman Ziak

That all sounds good.. but my protocol is not an electronic / interface one. Each packet has a checksum so any transmition errors can be delt with. And so no Address Assigning errors.

Any way, I've now simulated this aspect of my protocol in code and every thing seems good, so thanks again every one for the ideas.

Who knows some of you may end up using it ;)

DaveC

Reply to
DaveC

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.