Note: Discovering Topology

On how OpenLCB can help a large modular layout discover (or confirm) how the modules are connected.

June 2010 David Harris Proposal

Modular clubs, and larger modular-meets need a way of configuring modules into a cohesive whole that is time and effort efficient. This proposal suggests some approaches to this. Essentially, an organization would set some standards and define some standard Events to implement that standard.

(See also the separate figure in a PDF file)

When joining one set of modules to another set, only the 'edge events', is those events that link the modules across their mutual adjoining edge, need to be taght. All internal events between nodes on each set of modules do not need to be touched.

Edge-events will normally be limited to:
(1) Block-occupancy events, and
(2) Signal events.

In this proposal each module, or set of modules, is assigned a module-id. The module-id represents the module as a virtual-node. Note that the nodes in these modules still have their own node IDs and events.

The modules can then send a set of pre-defined events between themselves.

Each modular organization will:
(1) Develop a protocol which defines the set of predefined events that represent the edge-messages.
(2) Assign a range of "Module IDs" to clubs and individuals. So, for example I might be assigned: Ntrak.dpharris.xx (symbolically) or 01.00.34.02.54.xx (numerically), based on Ntrak's number (01.00.43) and my membership number (0254). My modules would be numbered 01, 02, 03 etc.
(3) Develop a set of global events, if needed, such as 'Start Auto-topology Configuration'.

As an example of predefined edge-events, Ntrak might define:

  1. 0001 Red-Line East block is occupied

  2. 0002 Red-Line East block is unoccupied

  3. 0003 Red-Line East signal is stop

  4. 0004 Red-Line East signal is caution

  5. 0005 Red-Line East signal is proceed

  6. ...

  7. 001D Green-Line West block is occupied

  8. ....

Each NTrak module would be required to implement these pre-defined edge-events. This can be done by a dedicated node, possibly obtained from the organizing committee, or implemented across a number of nodes, one at each end of the module(s), say. To ease set-up, a special configuration tool can be provided that knows the event numbers, and can program the appropriate event slots into the nodes.

How it works:

Consider two modules A and B.

west |===1===||=loco>==||====2===||======| east

Option 1 - creating the layout by taking a loco for a spin:

When a loco transitions from module-1 to module-2 from west to east, module-2 will report east-block-occupied and east-signal-state events. In the case of my module, it would send: NTrak.dpharris.01.0001 and NTrak.dpharris.01.0003. Since, module-1 knows that the loco is still occupying its west block, and therefore is exiting to the east, it will be expecting to receive some events from its adjacent module, it can insert these events into into its appropriate event-slots: West-block-occupied and West-signal-stop. In addition, in the process, it will learn the module-id of the adjacent module. Similarly, when the loco completes leaving module-1, module-2 will learn module-1 events. Alternately, a module can remembers the last edge-events it sees, then fill its slots as soon as it becomes occupied.

Option 2 - creating the layout centrally:

Each track has a one wire electrical bidirectional connection between modules which is used to identify adjacent modules. The central meet network-manager software automatically gathers all the module-ids, and then instructs each module, in succession, to report while it simultaneously activates each inter-module line. In more detail, the manager tells module-1 to report. Module-1 activates its Red-line-East intermodule wire and sends the associated East messages. The next module detects the active wire and reports 'Module -2 West-intermodule-line-activated' and fills its slots with node-1's events. This process quickly establishes the topology of the layout. The modules can learn the intermodule messages immediately or the network manager can set them explicitly, possibly at a later time.

Discussion:

Advantages:

This should greatly speed-up connecting modules. Other central functions, which are usually assigned to the human meet network-manager, can also be automated. For example a scale plan of the layout could be developed automatically at the time of topology discovery. The dimensions of each module would be in electronic form, either directly from the modules' nodes, or from separate media.

Disadvantages:

This requires some coordination, although not that much. Different organizations, even down to the individual level can have differing standards and protocols. This can be a good or bad thing.

Comments:

  1. Can tumble-down be automatically configured, if the appropriate nodes are told to do tumble-down?

  2. Similarly, for a module that goes from a single to double track via a turnout, could it manage its assignments based on the setting of the turnout?


May 2010 Discussion

Using CAN would work better if only one end was connected at a time. How about a switch in the middle of every module, which can disconnect the ends from each other? Open the switch, have the end of module A communicate to the end of module B to figure out what's going on, then close the switch and have everybody communicate their results.

Alternately, have that be a module in the center that can control the switch too, and do it remotely. Each module closes its switch, and then tells the newly combined network to close the next switches, and pretty soon it's all connected up again (does that work when opening the switches? Must ensure that everybody hears before opening up)

October 2009 Discussion

David Harris

MERG list has been batting ideas around about how to do signaling and other control using local links between control points.

I think we need to try to define this for OpenLCB, and we have previously made some suggestions around this. I think including local topological links are a good idea. Alan and others had suggested using a 1-wire like interface to send node interface info between adjacent nodes -- while in addition having a LCB connection for information flow, both between nodes and to others, such as displays. The suggestion is to have 4-6 links per node, to connect to adjacent nodes. In the case of a track section, only two are needed, for a turnout, three, and for slips and other nodes, perhaps up to 6.

One idea would be to use a very simple active-low 1-wire link. A node would pull-down the appropriate link concurrently with a successful transmission of (specific) LCB packets. The links would notify adjacent nodes to process the associated LCB-packets. The packets would include the NID and interface#, for auto-configuration, but also other information with state -- for example occupancy, signal state, etc.

Alan Robinson

It's interesting you've picked this one up. The discussion was sparked off by Pertti Tapola, a new Finnish member of the MERG Yahoo Group. His postings are - how shall I say it - voluminous (pot calling kettle black?) but so far he's been a great brain-stormer who likes to discuss options rather than fight for some stupid corner. It'might be good to have him on board, but I've no idea if he'd be at all interested.

We haven't got as simple as a 1-wire interface yet. Mike Bolton asked if we were familiar with Dallas One-Wire, but that's all. The most likely options discussed so far have been my own QCBSP (3 pins/wires minimum per neighbour link) and software UARTs (2 pins/wires minimum). So far, I'm inclined to favour UARTs (software, probably, but the standard needn't specify) for this job. If you've got a suggestion using only one wire, I'm all ears. If not, can we come up with one?

I'm a bit nervous about using a simple open-collector link and a protocol operating over the bus because it has to work without any central control. If two nodes simultaneously try to establish who their neighbours are, how do we guarantee they don't interfere? It might not be too hard if they're on the same CAN segment, but if not, what then? That could happen in a get-together where adjacent modules are on different CAN segments.

Half-duplex software UARTs, perhaps? If the neighbour links only have to carry repeated node ID and port number, message collisions ought to be easy to deal with. If each node tries again after a pseudo-random interval based on its node ID (we've already mandated code that does most of that), and doesn't start to transmit if it has seen an incoming start bit, that should work. Another refinement: once a node has successfully received its neighbour's node ID, it could drop to a much lower but still pseudo-random transmission rate. Hmmmm. Didn't think of that until now: I think I'll post it on MERG.

Whether the neighbour links also carry track occupancy, etc. as well is a moot point. The MERG discussions so far haven't ruled a common bus in or out. Pertti's starting point was NX routing using distributed modules. The comms topology is still entirely up for grabs. What we're talking about here is his option (2) out of quite a lot, which uses a bus and neighbour links to establish who is next door to who. My initial inclination (that's all it is) is to say that the neighbour links are only used to establish topology. If they only carry node ID and port number, they can be slow as hell and therefore easily interference-proof and dirt cheap, as well as using up very little processing power. Once a node knows who its neighbours are, it can do all the rest via the bus.

Are you happy with my terminology, 'Neighbour Link', and 'Port Number' especially? We'd have to agree something.

Bob Jacobsen

I think, in the context of OpenLCB, all you need is the ability to advertise a few bytes to your physical neighbors.

The distance involved isn't large, because you're connecting "right next door". If you're willing to pull a two-wire cable & use a common CAN ground, you could use e.g. the Maxim 1-wire 64-bit part which is practically free. Except for the shared ground, no other electrical connection is needed; the part is powered by the 1-wire connection.

Example protocol:

Goal is to find the node ID of the node handling various things on the adjacent module. From there, you can build up whatever protocol needed for EventIDs, etc.

Some nodes have a "next-door identification feature" (NDIF); all others aren't involved.

A) Send out a specific broadcast NMRA communication that means "All NDIF nodes, do your thing". I'd use a specific reserved EventID for this, but you could use a special op code.

B) All NDIF nodes hear the message and read 48 bits from their neighbor. Those 48 bits are the neighbors nodeID. Now they've got that NodeID, and are happy for their internal purposes.

C) In addition, the NDIF nodes can datagram that information to whoever sent (A), since the source of (A) was known from that message. (A) then picks up the entire topology from the combination of source&next-door-ID in those messages. And there's enough redundancy to detect lots of types of errors.

So what can you do with a neighbor's node ID? That Node ID is key to identifying known-unique events that your neighbor could emit. For example, establish a convention that modules will have a node at each end, emitting ID/1 for last block occupied; ID/2 for last block not occupied; ID/3 for block track not clear to enter (turnout set against , or whatever), etc. Now you've got a signaling and control system that can automatically set up.

The protocol is standard OpenLCB, with special boards (for the next-door connection) and conventions on use.

Alan Robinson

The distance involved isn't large, because you're connecting "right next door". If you're willing to pull a two-wire cable & use a common CAN ground, you could use e.g. the Maxim 1-wire 64-bit part which is practically free. Except for the shared ground, no other electrical connection is needed; the part is powered by the 1-wire connection.

Not so sure about that. The longest likely neighbour link would be the length of the longest plain-track block, plus some more for where modules are located and round-the-houses wiring routes. Long wires are likely to be loomed or trunked with others, and we don't know what those wires are carrying, so it could be noisy. I think the neighbour links should be about as noise immune as the CAN bus is. There's little point in making them much better, unless that's achievable at no extra cost. Some sort of low bit-rate comms would make this objective easier to meet because interference will be mostly HF, which can be filtered out by a simple RC. Achieving noise immunity does of course include packet validation in software. One simple way would be to accept the data only when the same values have been received more than once. A bit more thinking needed, perhaps.

B) All NDIF nodes hear the message and read 48 bits from their neighbor. Those 48 bits are the neighbors nodeID. Now they've got that NodeID, and are happy for their internal purposes.

Yes, except port number is needed too, for the (probably few) cases where adjacent nodes have more than one neighbour link. One case I thought of was a reversing loop where a plain track module has both its links connected to the same turnout module. That said, Pertti has cast doubt on whether plain track modules are needed. But he started with ideas on how to do NX routing without a central signalbox, and he's now moving on to automatic control of the trains as well (expect DC versus DCC sparks!), so I don't know where that's heading.

So what can you do with a neighbor's node ID? That Node ID is key to identifying known-unique events that your neighbor could emit. For example, establish a convention that modules will have a node at each end, emitting ID/1 for last block occupied; ID/2 for last block not occupied; ID/3 for block track not clear to enter (turnout set against , or whatever), etc. Now you've got a signaling and control system that can automatically set up.

Yes. Plus number of blocks ahead unoccupied, lengths of those blocks, and speed limits: info which could be input to a superbly realistic automatic train control process.

The protocol is standard OpenLCB, with special boards (for the next-door connection) and conventions on use.

Yes. And neighbour-to-neighbour comms would use directed packets, not events. Since the data passed could get quite complex, should it use the streaming protocol, one stream per neighbour link?

Why is the broadcast message in (A) above needed, and who sends it? If the neighbour links are only ever used to send node ID and port number, they could simply transmit them continuously. That would fit in nicely with data validation by comparing successive frames.

So how about this: the neighbour link protocol includes a bit that says 'I now know what your address is'. When both nodes see this from their peers they can have a little bus dialogue to confirm things, after which they're in up-and-running mode. Or is the little dialogue superfluous?

Alan Robinson

I'm beginning to have a vision thing. The various threads led by Pertti Tapola on the MERG list and this discussion here seem to me to be converging on something most interesting.

Pertti began with wondering how a distributed modular NX routing panel might be made. Now the discussion is broadening into how trains might be automatically controlled. Very soon we'll have ideas for all the components of a totally automated layout run entirely by standard general-purpose software.

Humans and scripted timetables generate route requests. The modules provide the signalling. With track occupancy detection, you know not only the route (block lengths, speed limits, number of blocks ahead unoccupied, even gradients if you want!) but where on its route each train is. In other words, you've got a complete electronic 'driver's eye' view of the line ahead of each train. A piece of automatic driver software, constantly updated with what's ahead of each train, sends packets to a DCC command station to control them. The driver software doesn't need to know anything about the rest of the layout: just the line ahead. The only configuration it needs is train characteristics.

Because it contains both signalman-centred and driver-centred elements, it removes the difficulties of using DCC with automation. I've been wondering how you might do that for a while. If you're ahead of me there, I apologise!

A system like this allows NX routing. It allows very realistic automated operation. It allows a mixture of scripted-timetable and ad-hoc workings. It allows a mixture of automated trains and manually controlled trains. And it allows throttles to show a human driver what's ahead.

Few people would want all that capability of course, but a system that can do it ought to be capable of anything, which why it appeals to me. Especially throttles with graphic displays of the line ahead, which I guess would find a larger market than automation.

Bob Jacobsen

The advantage of using a 1-wire memory chip to hold the data is that it can be electrically isolated from everything else that's going on. The sender powers it over the single-wire+ground connection. That greatly reduces problems with ground offsets, etc.

"port number" isn't really a OpenLCB concept at the moment, but the more I think about it, the more useful it seems for this.

I was thinking that each "end" of a module would use a different node or at least a different node number. That would then be used for addressing, event IDs, etc.

Two node numbers in a single piece of hardware is a little complex, though.

Better might be to define a port number (1 through 32? 1 through 255?), and then include that in EventIDs, datagrams, etc. Each 1-wire connection sender advertises it's NodeID and port number; the receiver can combine those to know what EventIDs to look for and where to send datagrams.

Need to define a format for the exchanged data, and make sure it's extensible for future things.

Why is the broadcast message in (A) above needed,

It implements the statement "your connections are complete, so you can start thinking now". I think you still want it, even if you have a local activation, because there might be long-distance effects in the information. I can't think of any at the moment, but that doesn't mean they don't exist.

and who sends it?

A circuit board with a CAN connection and a button, whose only purpose in life is to do this. Or a computer. Or any of the special "Module Handler Node" boards, when a special button on them is pushed.

If the neighbour links are only ever used to send node ID and port number, they could simply transmit them continuously. That would fit in nicely with data validation by comparing successive frames.
So how about this: the neighbour link protocol includes a bit that says 'I now know what your address is'. When both nodes see this from their peers they can have a little bus dialogue to confirm things, after which they're in up-and-running mode. Or is the little dialogue superfluous?

I like the idea of a completely local "We're connected, so lets come up" mechanism. That would let pieces of a modular layout be tested as they're connected together.

Having a "are we really connected?" dialog (or a timeout: Have to keep getting data for 3 seconds to make sure the connection has really been made) is a good idea. You need both the 1-wire and CAN connections up to succeed, so that's the thing to test.

Also, it's got to handle the "opps, hooked that up wrong, this module needs to go over there!" case. Maybe if a node notices different information on the 1-wire, it starts over? (Can't start over on loss-of-signal, because the next mode might just have been turned off for a second)

Alan Robinson

Some more thoughts........

  1. Pertti's first idea of track control nodes was as physical entities. But the same entities (same code, even) could run on a PC. A mixture of both could work together. They could run on more than one PC (e.g. one per module). They just send messages to each other, and needn't know or care what hardware is hosting their peers.

  2. A use for automatic train driver software: throttles which can be switched in and out of autopilot. Scenario: Despatcher at module D and Receiver at module R between them request a route from D's yard to R's yard. When he gets the off, D drives the train manually out of his yard onto the main line, then switches his throttle to autopilot. If R is a long way from D the train is going to end up in an elephant parade. All handled automatically. Sometime after D has switched to autopilot, the train is handed from throttle D to throttle R, including the train characteristics info. To an observer of the train, the handover is completely seamless and unnoticeable. Someone at an intermediate module might set up a conflicting movement, and the train has to wait. All handled. All this may be going on completely out of sight of either D or R, who are now shunting their yards. Eventually, R gets notice that a route has been set up into his yard, so he knows the train is coming. D might have been a bit of a devil and not even told him what sort of train it is. Doesn't matter. When the train comes into view, R switches his throttle out of autopilot and drives the train manually into his yard.

I reckon we've got the brains between us to work out all the details and standards needed to achieve something like that. OpenLCB could become something rather more than just a me-too rival to CBUS or NMRAnet S9.5.

David Harris

There was mention on MERG about all-RF control of trains (but Alan shut it down ;-) ).

I can see all RF coming, too. However, OpenLCB should be able to adapt easily to these, since we are planning message-routing, etc.


Site hosted by

This is SVN $Revision: 775 $