AVR-Chat

Anybody aware of a masterless(multimaster) protocol ( ie: any device 
can communicate with any other device on the net based on device ID - 
and any device can be shut-down without affecting the bus -  something 
similar to echelon bus but way simple) that can be applied on AVRs and 
affordable for hobbyists

On Sat, Mar 05, 2005 at 08:17:18PM -0000, phisatho wrote:

> Anybody aware of a masterless(multimaster) protocol ( ie: any device
> can communicate with any other device on the net based on device ID
> - and any device can be shut-down without affecting the bus -
> something similar to echelon bus but way simple) that can be applied
> on AVRs and affordable for hobbyists

Have a look at ROBIN:

     http://www.bdmicro.com/code/robin/

-Brian
-- 
Brian Dean
BDMICRO - ATmega128 Based MAVRIC Controllers
http://www.bdmicro.com/

Brian,

I had a (very) quick look at it, and it looks fairly complex to me, 
lots of decoding and stuff. I'm a very basic c programmer, and that 
looks above my skill level, plus it appears you need an RS485 chip. 
Wouldn't it be easier to utilise a 2 wire interface instead? I'm 
currently looking at the mega64, and it has the module onboard, but 
it appears to allow multi-masters, and only needs the two pull-ups 
on the SDA & SCL lines. I realise that it'd be a pain in the butt on 
older chips (I've played with 8535s), but I think it may be simpler 
to implement.

In your opinion, would it be easier/more efficient to go for TWI or 
for ROBIN?

Adam R.

--- In AVR-Chat@yahoogroups.com, Brian Dean <bsd@b...> wrote:
> On Sat, Mar 05, 2005 at 08:17:18PM -0000, phisatho wrote:
> 
> > Anybody aware of a masterless(multimaster) protocol ( ie: any 
device
> > can communicate with any other device on the net based on device 
ID
> > - and any device can be shut-down without affecting the bus -
> > something similar to echelon bus but way simple) that can be 
applied

> > on AVRs and affordable for hobbyists
> 
> Have a look at ROBIN:
> 
>      http://www.bdmicro.com/code/robin/
> 
> -Brian
> -- 
> Brian Dean
> BDMICRO - ATmega128 Based MAVRIC Controllers
> http://www.bdmicro.com/

> From: Brian Dean
> 
> On Sat, Mar 05, 2005 at 08:17:18PM -0000, phisatho wrote:
> 
> > Anybody aware of a masterless(multimaster) protocol ( ie: any device
> > can communicate with any other device on the net based on device ID
> > - and any device can be shut-down without affecting the bus -
> > something similar to echelon bus but way simple) that can be applied
> > on AVRs and affordable for hobbyists
> 
> Have a look at ROBIN:
> 
>      http://www.bdmicro.com/code/robin/
> 
> -Brian

Brian,

In the ROBIN document, under "Multi-Master" you mention that, upon detection of
a collision between two masters (both trying to send at once) the master should
"back-off by a random amount".  I understand the concept, but, given two devices
containing identical hardware, software and reset at the same time (i.e.: has
the same "life history") how does it generate a random number with a high
probability of being different from other devices?  My thoughts:

0) Can't use memory contents as a random number seed since the devices history
may be the same causing lockstep random numbers.

1) Pass the on-chip timer/clock value through a hash to generate pseudo-random
delay values that are widely dispersed given small time value differences.  This
assumes that the devices are not running from the same clock and/or not reset by
the same HW reset signal.

2) Use a value from an independent clock source such as an RTC as the hash input
in #1.  The problem here, again, is that it doesn't work unless the RTCs are
different and not in lockstep.

So, if you don't have some independent random number seed source (independent
clock, noisy diode, etc.) how do you generate the random/pseudo-random back-off
delay?  Are there register/memory contents of an AVR that are truly "random" at
power-up/reset and not dependent on the device's past history?

Hmm, just thought of a #3: Use very high amplification on one of the internal
A/D's to intentionally read "noise" and use the low byte as the random number or
as the seed ...

Regards,

Chuck Hackett

Adam Read wrote:
> 
> Brian,
> 
> I had a (very) quick look at it, and it looks fairly complex to me, 
> lots of decoding and stuff. I'm a very basic c programmer, and that 
> looks above my skill level, plus it appears you need an RS485 chip.

DS485s are small and cheap.

> Wouldn't it be easier to utilise a 2 wire interface instead? I'm 
> currently looking at the mega64, and it has the module onboard, but 
> it appears to allow multi-masters, and only needs the two pull-ups 
> on the SDA & SCL lines. I realise that it'd be a pain in the butt on 
> older chips (I've played with 8535s), but I think it may be simpler 
> to implement.
> 
> In your opinion, would it be easier/more efficient to go for TWI or 
> for ROBIN?

TWI is I2C which is only a board level thing and relies on a specific
hardware approach that is unsuitable for long cabling.

On Mon, Mar 07, 2005 at 12:35:07PM -0000, Adam Read wrote:

> I had a (very) quick look at it, and it looks fairly complex to me,
> lots of decoding and stuff. I'm a very basic c programmer, and that
> looks above my skill level, plus it appears you need an RS485 chip.
> Wouldn't it be easier to utilise a 2 wire interface instead?

RS485 is only 2 signal wires.

> I'm currently looking at the mega64, and it has the module onboard,
> but it appears to allow multi-masters, and only needs the two
> pull-ups on the SDA & SCL lines. I realise that it'd be a pain in
> the butt on older chips (I've played with 8535s), but I think it may
> be simpler to implement.
> 
> In your opinion, would it be easier/more efficient to go for TWI or
> for ROBIN?

For short distances of a 1 meter or less, then I2C is fine.  I2C is not
designed for longer distances without bus extenders.  If you need
longer, you need something like RS485, CAN, etc.

-Brian
-- 
Brian Dean
BDMICRO - ATmega128 Based MAVRIC Controllers
http://www.bdmicro.com/

On Mon, Mar 07, 2005 at 08:28:07AM -0600, Chuck Hackett wrote:

> In the ROBIN document, under "Multi-Master" you mention that, upon
> detection of a collision between two masters (both trying to send at
> once) the master should "back-off by a random amount".  I understand
> the concept, but, given two devices containing identical hardware,
> software and reset at the same time (i.e.: has the same "life
> history") how does it generate a random number with a high
> probability of being different from other devices?

One thing I had played with was letting one of the A/D lines float,
and use it's value for the seed.

Another alternative is to set one of the timers to free-run, then when
the first uart receive interrupt occurs, use the timer value at that
time for the seed.  Due to variations in the crystals, chances are
those counters won't be the same for any two boards except for very
high precision clock sources.

If one wanted to get really really good random number sequences, like
cryptographic quality randomness, another method would be to use a
radioactive source and detector.  Between any three detector hits, if
the time between the first to the second is greater than the second to
the third, call that a "1" bit, otherwise call it a "0" bit.  You'll
get some very seriously high quality random data that way, though the
effort might not be worth it in this application :-)

> My thoughts:

> 0) Can't use memory contents as a random number seed since the
>    devices history may be the same causing lockstep random numbers.

Right.

> 1) Pass the on-chip timer/clock value through a hash to generate
>    pseudo-random delay values that are widely dispersed given small
>    time value differences.  This assumes that the devices are not
>    running from the same clock and/or not reset by the same HW reset
>    signal.

Yep.

> 2) Use a value from an independent clock source such as an RTC as
>    the hash input in #1.  The problem here, again, is that it
>    doesn't work unless the RTCs are different and not in lockstep.

You could use the RTC to clock a certain duration and after that has
expired, take the value of a counter being clocked by the main system
clock.  Similarly to what I mentioned above, due to variations in
crystal clocks they don't clock with super high precision and after a
short time two crystal clocks will certainly diverge, providing
different seeds.

> So, if you don't have some independent random number seed source
> (independent clock, noisy diode, etc.) how do you generate the
> random/pseudo-random back-off delay?  Are there register/memory
> contents of an AVR that are truly "random" at power-up/reset and not
> dependent on the device's past history?

Not that I'm aware of.  I think you'd have to use some environmental
entity that you can measure, or use small variations in crystals, etc,
to provide different seed values for the pseudo random number
generator.

> Hmm, just thought of a #3: Use very high amplification on one of the
> internal A/D's to intentionally read "noise" and use the low byte as
> the random number or as the seed ...

Yes - similar to what I mentioned above.

-Brian
-- 
Brian Dean
BDMICRO - ATmega128 Based MAVRIC Controllers
http://www.bdmicro.com/

For this application, you really DO NOT need a very random
value. The whole idea is that the transmitters that
"collided" wait different time intervals before retrying.
You just want one to be different than the other. Don't
bother with all that stuff to get genuinely random values.

Jim Wagner

On Mon, 7 Mar 2005 18:50:10 -0500
 Brian Dean <bsd@bdmicro.com> wrote:
> 
> On Mon, Mar 07, 2005 at 08:28:07AM -0600, Chuck Hackett
> wrote:
> 
> > In the ROBIN document, under
> "Multi-Master" you mention that, upon
> > detection of a collision between two masters (both
> trying to send at
> > once) the master should "back-off by a random
> amount".  I understand
> > the concept, but, given two devices containing
> identical hardware,
> > software and reset at the same time (i.e.: has the
> same "life
> > history") how does it generate a random number
> with a high
> > probability of being different from other devices?
> 
> One thing I had played with was letting one of the A/D
> lines float,
> and use it's value for the seed.
> 
> Another alternative is to set one of the timers to
> free-run, then when
> the first uart receive interrupt occurs, use the timer
> value at that
> time for the seed.  Due to variations in the
> crystals, chances are
> those counters won't be the same for any two boards
> except for very
> high precision clock sources.
> 
> If one wanted to get really really good random number
> sequences, like
> cryptographic quality randomness, another method would be
> to use a
> radioactive source and detector.  Between any three
> detector hits, if
> the time between the first to the second is greater than
> the second to
> the third, call that a "1" bit, otherwise call
> it a "0" bit.  You'll
> get some very seriously high quality random data that
> way, though the
> effort might not be worth it in this application :-)
> 
> > My thoughts:
> 
> > 0) Can't use memory contents as a random number seed
> since the
> >    devices history may be the same
> causing lockstep random numbers.
> 
> Right.
> 
> > 1) Pass the on-chip timer/clock value through a hash
> to generate
> >    pseudo-random delay values that
> are widely dispersed given small
> >    time value differences.  This
> assumes that the devices are not
> >    running from the same clock and/or
> not reset by the same HW reset
> >    signal.
> 
> Yep.
> 
> > 2) Use a value from an independent clock source such
> as an RTC as
> >    the hash input in #1.  The
> problem here, again, is that it
> >    doesn't work unless the RTCs are
> different and not in lockstep.
> 
> You could use the RTC to clock a certain duration and
> after that has
> expired, take the value of a counter being clocked by the
> main system
> clock.  Similarly to what I mentioned above, due to
> variations in
> crystal clocks they don't clock with super high precision
> and after a
> short time two crystal clocks will certainly diverge,
> providing
> different seeds.
> 
> > So, if you don't have some independent random number
> seed source
> > (independent clock, noisy diode, etc.) how do you
> generate the
> > random/pseudo-random back-off delay?  Are there
> register/memory
> > contents of an AVR that are truly "random"
> at power-up/reset and not
> > dependent on the device's past history?
> 
> Not that I'm aware of.  I think you'd have to use
> some environmental
> entity that you can measure, or use small variations in
> crystals, etc,
> to provide different seed values for the pseudo random
> number
> generator.
> 
> > Hmm, just thought of a #3: Use very high
> amplification on one of the
> > internal A/D's to intentionally read
> "noise" and use the low byte as
> > the random number or as the seed ...
> 
> Yes - similar to what I mentioned above.
> 
> -Brian
> -- 
> Brian Dean
> BDMICRO - ATmega128 Based MAVRIC Controllers
> http://www.bdmicro.com/
> 
> 
> 
> 
> 
> 
> 
> 
> 
> Yahoo! Groups Sponsor
> 
> 
>   ADVERTISEMENT 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> Yahoo! Groups Links
> 
> To visit your group on the web, go
> to:http://groups.yahoo.com/group/AVR-Chat/ 
> To unsubscribe from this group, send an email
> to:AVR-Chat-unsubscribe@yahoogroups.com 
> Your use of Yahoo! Groups is subject to the Yahoo! Terms
> of Service.
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 

---------------------------------------------------------------
The Think Different Store
http://www.thinkdifferentstore.com/
For All Your Mac Gear
---------------------------------------------------------------

> From: Brian Dean
> 
> > .... given two devices containing identical hardware,
> > software and reset at the same time (i.e.: has the same "life
> > history") how does it generate a random number with a high
> > probability of being different from other devices?
> 
> One thing I had played with was letting one of the A/D lines float,
> and use it's value for the seed.

I like this one if the configuration has an open A/D line, or, one might even be
able to use a used A/D line if the signal being sampled is not also being fed to
another device you don't want to conflict with ... although you probably would
get a different A/D result in different devices even if they were connected to
the same power, clock, Vref and input signal so that might even work due to
noise, chip temp, etc..

> Another alternative is to set one of the timers to free-run, then when
> the first uart receive interrupt occurs, use the timer value at that
> time for the seed.  Due to variations in the crystals, chances are
> those counters won't be the same for any two boards except for very
> high precision clock sources.

That would be worth experimenting withy ...

> If one wanted to get really really good random number sequences, like
> cryptographic quality randomness, another method would be to use a
> radioactive source and detector.  Between any three detector hits, if
> the time between the first to the second is greater than the second to
> the third, call that a "1" bit, otherwise call it a "0" bit.  You'll
> get some very seriously high quality random data that way, though the
> effort might not be worth it in this application :-)

I don't know about you, but my projects don't have radioactive sources in them
:-)

I maintained Crypto equipment in the Air Force and IIRC they used "noisy" diodes
as a source for random data.

> > .... Are there register/memory
> > contents of an AVR that are truly "random" at power-up/reset and not
> > dependent on the device's past history?
> 
> Not that I'm aware of.  I think you'd have to use some environmental
> entity that you can measure, or use small variations in crystals, etc,
> to provide different seed values for the pseudo random number
> generator.

Amazing how much work we have to go through to get truly "random" numbers out of
a powerful computer/microcontroller.  Thankfully there aren't many applications
that require truly random number sequences.

Thanks for the info ...

Cheers,

Chuck Hackett
"Good judgment comes from experience, experience comes from bad judgment"
7.5" gauge Union Pacific Northern (4-8-4) 844
http://www.whitetrout.net/Chuck

> From: Jim Wagner
> 
> For this application, you really DO NOT need a very random
> value. The whole idea is that the transmitters that
> "collided" wait different time intervals before retrying.
> You just want one to be different than the other. Don't
> bother with all that stuff to get genuinely random values.

You are correct in that we don't really need "random" values in this application
(collision resolution).  The conversation really started by needing to generate
two "different" values in the case where two processors are connected in the
same local environment such that they are running identical software, receive
the same bus data, and are reset by the same HW reset signal.

Cheers,

Chuck Hackett
"Good judgment comes from experience, experience comes from bad judgment"
7.5" gauge Union Pacific Northern (4-8-4) 844
http://www.whitetrout.net/Chuck

> From: Doug Locke
> 
> If my memory serves, Ethernet uses the binary exponential backoff algorithm to
> avoid two stations recommencing transmitting after a packet collision. May be
> worth a look via Google.

I did look this up but it bases the back-off time on a "Slot Time" value and I
can't find a definition of this value.  I suspect that it's based on the MAC
address or some other configuration value.  

I was looking at a case where the two devices are identical (same software,
etc.) and share the data bus and reset signal - i.e.: they both have the same
historic view of the world so would thus generate identical values unless you
can use something like clock speed differences, etc. which we have discussed.

Cheers,

Chuck Hackett
"Good judgment comes from experience, experience comes from bad judgment"
7.5" gauge Union Pacific Northern (4-8-4) 844
http://www.whitetrout.net/Chuck

At 01:07 PM 9/03/2005, you wrote:

>I was looking at a case where the two devices are identical (same software,
>etc.) and share the data bus and reset signal - i.e.: they both have the same
>historic view of the world so would thus generate identical values unless you
>can use something like clock speed differences, etc. which we have discussed.

But of course no 2 devices on an RS485 networks are exactly the same :-)
each one has an UNIQUE ADDRESS and mixed with a free running timer
could generate random numbers which are different.

Regards

John Samperi

******************************************************
                         Ampertronics Pty. Ltd.
   11 Brokenwood Place Baulkham Hills, NSW 2153 AUSTRALIA
          Tel. (02) 9674-6495       Fax (02) 9674-8745
                Email: samperi@ampertronics.com.au
                  Website  http://www.ampertronics.com.au
* Electronic Design   * Custom Products   * Contract Assembly
******************************************************

> From: John Samperi
> 
> >I was looking at a case where the two devices are identical (same software,
> >etc.) and share the data bus and reset signal - i.e.: they both have the same
> >historic view of the world so would thus generate identical values unless you
> >can use something like clock speed differences, etc. which we have discussed.
> 
> But of course no 2 devices on an RS485 networks are exactly the same :-)
> each one has an UNIQUE ADDRESS and mixed with a free running timer
> could generate random numbers which are different.

Good point ...

Cheers,

Chuck Hackett
"Good judgment comes from experience, experience comes from bad judgment"
7.5" gauge Union Pacific Northern (4-8-4) 844
http://www.whitetrout.net/Chuck