Tinverse logo Tinverse LLC

Algorithms and data structures

EtherCAT master algorithms

An EtherCAT master starts knowing nothing: not how many devices are on the wire, not what they are, not how long a frame takes to reach each one. Within a few hundred milliseconds it has to know all three well enough to drive them on a fixed cycle where a late frame is a fault.

What follows are the algorithms that get it there and keep it there. Each gives the problem, when it runs, the steps as pseudocode, and what it costs. For a fieldbus master, cost is counted in frames on the wire as much as in instructions.

Notation

Procedure names are in small capitals, assignment is =, and indentation shows block structure. Each procedure lists what its arguments are before its steps. The behaviour follows ETG.1000, the EtherCAT specification: Parts 3 and 5 define what a layer does, Parts 4 and 6 define the protocol machines that do it.

Discovery

Enumerating and addressing the bus

Runs when

the master starts, and again after a topology change

How often

Once per start. Four to five frames per device.

Nothing tells the master how many devices are attached. It could be one, it could be two hundred. The answer comes from a property of the protocol rather than from configuration.

EtherCAT frames pass through every device in turn, and each one increments a counter in the frame if it was addressed. Auto-increment addressing uses that: a datagram carries a position that each device increases as it forwards, and the device that sees zero is the one being addressed. So the master counts up from below — to reach the nth device it sends −n, which n devices raise to zero on the way. Send a read for position n and exactly the nth device answers.

Read position n. If the counter comes back unchanged, there is no nth device and the bus is n long.

master device 0 pos −3 → −2 device 1 −2 → −1 device 2 −1 → 0 · answers nothing here Reading position 3 returns with the counter unchanged. That is the whole termination condition — the master never needs to be told how long the bus is. Each device then gets a fixed address, 0x1001 + position, so later traffic can name it directly instead of counting hops.
Figure 1 The end of the chain is discovered, not configured.

Discover(bus, ceiling)

bus the open transport · ceiling the configured maximum number of devices

  1. found = ⟨⟩
  2. for position = 0 to ceiling − 1
  3. status = Read-At-Position(bus, position, al-status)
  4. if status == no-reply
  5. return found // past the end of the chain
  6. links = Read-At-Position(bus, position, dl-status) // port link bits, used later
  7. address = Read-At-Position(bus, position, station-address)
  8. if address ≠ 0x1001 + position
  9. Write-At-Position(bus, position, station-address, 0x1001 + position)
  10. Write-At-Position(bus, position, dl-control, forward-ethercat)
  11. Append(found, record(position, address, links, status))
  12. return found

The address on line 8 is a function of position, so re-running discovery computes the same value and skips every write. The walk is idempotent. Discovery runs again after a topology change, and a device that already holds its address is not rewritten.

Line 11 appends only after every read and write for that device has succeeded, so a failure part-way through leaves no half-built record.

Cost

Four frames per device, plus one more for each device that was not already addressed — so between 4N and 5N for a bus of N. That count, not the instruction count, is what decides how long a cold start takes. Each step is one bus operation, so a caller can drive discovery from its cycle tick rather than blocking for the whole walk.

Application layer

Sequencing every device to OP

Runs when

the bus is brought up, and on recovery

How often

Four transitions per start: to INIT, PREOP, SAFEOP, then OP.

Every device runs the same small state machine — INIT, then PREOP, then SAFEOP, then OP — and the master has to walk the whole bus through it together. Configuration happens between the states: mailboxes are set up before PREOP is useful, the process image and clocks before SAFEOP, outputs only in OP.

The obvious implementation asks each device to change state and waits for it before moving to the next. That serialises the whole bus behind its slowest member. Instead every request goes out first, and only then does the master start asking whether they arrived.

Request-State(bus, devices, target, limit)

devices the discovered devices · target the state wanted · limit the poll ceiling derived from the configured timeout

  1. for each d in devices
  2. Write-Control(bus, d, target) // every request first
  3. attempts = 0
  4. loop
  5. if All-Report(bus, devices, target)
  6. return ok
  7. attempts = attempts + 1
  8. if attempts ≥ limit
  9. return Describe-Each-Device(bus, devices) // not just "timed out"
  10. Wait(poll-interval)

Line 9 is the difference between a diagnosable failure and an infuriating one. A master that reports only that a transition timed out leaves an engineer to find which of ninety devices refused; reading every device's status on the way out names it, along with the error code it is reporting.

Telling a refusal from slowness

A device that cannot make the transition keeps reporting the state it is still in. So comparing states alone cannot distinguish "refused" from "not yet", and the master would spend its whole poll budget waiting for an answer that already arrived.

The status carries a separate bit meaning "state transition not successful", and a status code saying why. Checking that bit before comparing states turns a full timeout into an immediate failure that names the device and its reason.

There is a matching bit on the way out. A device left latched in an error state will refuse a fresh request, so requests to the two lowest states also assert an acknowledge bit that clears the latch — which is what lets a master recover a bus it did not start.

Cost

N writes, then one read per device per poll. A transition that succeeds on the first poll costs 2N frames. One that fails costs N + N × P for P polls, plus one pass to build the diagnostic — which is a cost worth paying once, on a path that has already failed.

Metadata

Reading a device's EEPROM

Runs when

a device is first seen, before anything is configured

How often

Once per device, then cached. Several frames per EEPROM word.

Discovery finds devices. It does not say what they are. Identity, how many process-data channels a device has, what its default data mapping looks like — all of it lives in an EEPROM on the device, reached through a register interface.

That interface is asynchronous. The master writes an address, and the device signals when the word is ready by clearing a busy bit.

Read-Word(device, address, limit)

device the addressed slave · address the EEPROM word wanted · limit the poll ceiling

  1. Clear-Errors(device) // a latched error would fail this read instead of the last one
  2. Write(device, sii-address, address)
  3. Write(device, sii-control, read-command)
  4. for attempt = 1 to limit
  5. status = Read(device, sii-control)
  6. if status and busy-bit == 0
  7. return Read(device, sii-data)
  8. return timeout

Line 7 sits inside the busy check for a reason. Reading the data register before the device has cleared busy returns whatever the previous operation left there — a value that looks entirely plausible and belongs to a different address.

The poll ceiling on line 4 is what keeps one unresponsive device from hanging startup. This runs for every device in turn, so a device that never answers would otherwise stall the whole bus before it has even been configured.

Two details come from the device rather than the master. A single read returns four or eight octets, and which one is a property the device declares — so the master reads that back from the status rather than assuming a size. And starting a read needs a rising edge on the command bit, not merely writing a one to it: a bit left set by an abandoned read would make the next request do nothing at all, which is why the sequence clears the error state first.

Cost

Two writes and at least two reads per transaction, more while polling, returning four or eight octets each time. A device's full metadata is many transactions, so this dominates cold-start time on a large segment — which is why the result is cached and never re-read during operation.

Configuration

Validating the configured topology

Runs when

a configuration file is supplied, before any process data is set up

How often

Once, and only when configured offline.

Many installations are configured offline: an engineering tool produces a file describing the network, and the master is expected to bring up that network. The bus actually on the wire may differ — a device swapped, a segment added, a file one revision out of date.

The check is a walk down both lists comparing position by position. What matters is when it happens.

It runs before process-data setup, not during it. Validating as each device is configured would mean discovering the mismatch part-way through writing FMMUs, leaving some devices configured for a process image that is about to be abandoned. Checking first means a mismatch costs nothing but the check.

A rejection names the position and what differed. An engineer with a file one device out of date needs to know which device; being told only that validation failed leaves them comparing two lists by hand.

Process data

Laying out the process image

Runs when

the process image is planned, before the cyclic loop is frozen

How often

Once. The layout is then immutable for the life of the run.

Every device contributes some outputs and some inputs. The master gathers all of them into one shared address space — the process image — and tells each device which slice of it belongs to that device.

A cyclic frame is made of datagrams, and a datagram that uses logical addressing names one contiguous range of that space: a start address and a length. Every device whose slice lies inside the range takes part as the frame passes. A range cannot skip a gap, and it cannot name two separate stretches.

That one property decides the whole layout, because it means the cost of a cycle depends on how many contiguous runs the master has to address.

Suppose the master walks the bus once, appending each device's outputs and then its inputs as it meets them. The image comes out alternating: outputs, inputs, outputs, inputs. Now no contiguous range holds only outputs. Writing the outputs takes one datagram per device instead of one for all of them, and reading the inputs takes another per device — because each device's slice is its own isolated run.

Walking the bus twice fixes it. One pass collects every device's outputs, a second collects every device's inputs. Each direction is now a single unbroken run, so one datagram covers all the outputs and one covers all the inputs — and because the two runs sit next to each other, one combined read-write datagram can cover the entire image.

one pass, interleaved out 1 in 1 out 2 in 2 out 3 in 3 → six runs, six datagrams two passes, grouped out 1 · out 2 · out 3 in 1 · in 2 · in 3 → two runs: one datagram each, or one for both A logical datagram addresses one contiguous range, so the number of datagrams is the number of runs. Grouping by direction turns six runs into two, and the two are adjacent so one datagram can span both.
Figure 2 Grouping by direction turns six datagrams into two, because a datagram covers one contiguous run.

Translating one address range per device

A datagram covering the whole output block is addressed to the block, not to any device. So how does each device end up holding only its own bytes?

Each device contains an address-translation unit, and the master configures it with two things: which range of the shared image belongs to that device, and where that range lives in the device's own local memory. As the frame passes through, the device compares the addresses the datagram covers against its configured range and copies just the overlapping bytes — out of the frame for outputs, into the frame for inputs.

So the devices do the demultiplexing themselves, in hardware, as the frame goes by. That is what lets the master address the whole image at once and still have each device receive exactly its own share: a cyclic datagram never names a device at all.

It is also why the layout has to be settled before the cycle starts. Those translation units are configured once, from the layout, and a device's slice cannot move afterwards without reconfiguring them.

The standard bounds them: a device has at most sixteen such units, and each maps one contiguous logical range to one contiguous local range. A device needing more separate mappings than that cannot be configured, whatever arrangement of the shared image is chosen. This is the limit on how finely a process image can be divided.

Packing is done at bit granularity, not byte. A device contributing three bits takes three bits. That looks like a micro-optimisation and is not: the process image travels in every frame, so a wasted byte is a wasted byte per cycle, for the life of the machine.

Sizing the channel

One number has two sources that disagree. A device's description declares how large its process-data channel is; the selected data mapping declares how many bytes are actually being exchanged. The master takes the larger — the payload has to fit, but a device may advertise a wider channel for reasons the master cannot see.

A channel carrying outputs also gets its watchdog enabled. That is what makes a device fall back to a safe state if cyclic data stops arriving. Without it, a master that dies leaves its last commanded values driven indefinitely — which on a machine with an axis in motion is the difference between a stop and a runaway.

Cost

Two passes over the bus, done once before the cyclic loop is frozen. The resulting layout is immutable, so the cyclic path never rebuilds it and never allocates.

Cyclic data

Deriving the expected working counter

Runs when

the plan is compiled, then compared every cycle

How often

Computed once. Checked on every cycle, for the life of the machine.

A cyclic frame goes out carrying outputs and comes back carrying inputs. Nothing in it records which devices took part — except one counter travelling with the frame, which each device increments as it passes.

The counter counts participations, not devices. A datagram that both writes outputs and reads inputs gives one device more than one way to take part in the same pass, so a device's contribution depends on which directions its data lies in. That is why the numbers below are not all one.

The master therefore knows a cycle was complete when the counter returns the value it should. That value is never observed and then trusted; it is derived from the process image plan before the loop starts, so the first cycle is checked as strictly as the millionth.

Worked example

A segment with three drives, each with outputs and inputs mapped, and two input-only sensors, exchanged with one combined read-write:

DeviceMappingContributes
drive 1outputs2
drive 1inputs1
drive 2outputs2
drive 2inputs1
drive 3outputs2
drive 3inputs1
sensor 1inputs1
sensor 2inputs1
expected working counter11

A cycle returning 11 is healthy. A cycle returning 9 means two participations are missing, which is consistent with one drive dropping out entirely: a drive contributes 2 for its outputs and 1 for its inputs. A shortfall of 1 would instead point at a sensor.

Those numbers are the standard's. ETG.1000.4 says the counter is incremented "by two if a piece of data was successfully written and additionally incremented by one if a piece of data was successfully read", and it fixes which is which: a device "can retrieve data with this service (write operation) and put data with this service (read operation)". Retrieving is consuming the master's outputs, so an output mapping scores the write increment of two; putting is supplying the master's inputs, so an input mapping scores the read increment of one.

A device mapped in both directions therefore contributes three, and a segment of N such devices exchanged with one combined read-write expects 3N — 36 for twelve drives.

A mapping that only partly overlaps the datagram's address window contributes nothing at all. A partial overlap is a planning mistake, and counting it as a partial increment would produce an expected value that a healthy cycle can never match.

An assumption the layout has to keep true

The standard counts per device, not per mapping — a device increments once "if at least one" of the addressed regions matched, no matter how many of its regions did. This master instead adds up its mappings, which gives the same answer only while no device holds more than one mapping per direction inside a single datagram.

Its own layout guarantees that: each device is given exactly one mapping per direction. So the sum is correct here — but it is correct because of the layout, not on its own. A process image built some other way, giving one device two output regions in the same datagram, would make the master expect a number no conforming device will ever produce, and every cycle would look faulty.

Cost

Linear in the number of mapped regions, computed once when the plan is compiled. Every cycle after that costs one comparison. This is the cheapest health check in the system and the one that catches a device dropping off the bus within a single cycle.

Distributed clocks

Measuring propagation delay

Runs when

clocks are configured, before the cyclic loop starts

How often

Once. One broadcast frame plus a bounded number of reads per device.

Devices on an EtherCAT segment share a system time, and they use it to act simultaneously — to sample sensors or drive outputs at the same instant rather than as the frame sweeps past them. That only works if each device knows how long the frame took to reach it.

The delay is measured, not assumed. Each device timestamps the frame as it arrives at each of its ports, and those timestamps let the master reconstruct how long the signal spent on every link.

Why one broadcast, and not one frame per device

The timestamps only mean something together. They must all describe the same traversal, so the latch is one broadcast write that every device sees as it passes. Reading each device individually would produce timestamps from different frames taken at different moments, which cannot be differenced.

Compensate-Delays(chain)

chain the discovered devices with their port link bits

  1. tree = Rebuild-Topology(chain) // port 0 upstream; children in port order 1, 2, 3
  2. Broadcast-Latch(receive-time-port-0) // one frame, so all timestamps share a traversal
  3. for each device d in tree, in forwarding order
  4. if d forwards and d has no receive-time support
  5. return error // refuse rather than guess a residence time
  6. t = Read-Port-Times(d) // four ports plus the processing unit
  7. round-trip = Wrapping-Difference(t) // free-running 32-bit counters
  8. if round-trip > half the counter range
  9. return error // the difference is ambiguous; do not interpret it
  10. link = round-trip / 2 // the standard's symmetric-link assumption
  11. delay[d] = accumulated + link + branch-residence-before(d)
  12. for each device d
  13. Write(d, transmission-delay, delay[d])
  14. Write(d, system-time-offset, offset including delay[d])

Lines 7 to 9 handle counter wraparound. The timestamps come from free-running 32-bit counters, so a difference must be computed with wrapping arithmetic. A difference larger than half the counter's range has two equally valid readings. Rather than pick one, the measurement is rejected.

Line 4 covers missing hardware support. A device that forwards frames but cannot timestamp them leaves a gap in the accumulated delay. The only way to fill that gap would be to assume a residence time. Configuration fails instead.

Line 10 halves a round trip to get a one-way delay. This is the standard's symmetric-link assumption rather than this master's choice. A link whose two directions differ materially would break it.

Writing the offsets, then activating the sync unit

Measuring the delay tells the master how far each device is from the reference. Two more things have to happen before anything is synchronised.

First the clocks are aligned. The master zeroes the reference's offset, reads its clock once, and expresses every other device's offset against that single reading — corrected by that device's propagation delay. Reading the reference again for each device would make every offset relative to a different instant, and the alignment would be no better than the time between the reads.

Worked example

Three clock-capable devices. The master writes zero to the reference's offset and reads its clock once, getting 1 000 000 ns. Each device's own clock is running from whatever value it happened to hold at power-on, and each has a propagation delay already measured:

DeviceIts own clockDelay Offset writtenSystem time it now reports
0 (reference)1 000 0000 01 000 000
1999 300300 +1 0001 000 300
21 002 500640 −1 8601 000 640

Each offset is the reference reading minus that device's own clock, plus its delay. Device 1 is 700 ns behind the reference and sits 300 ns down the wire, so it is moved forward by 1 000 ns. Device 2 is 2 500 ns ahead, so it is moved back.

The last column is the check. Every device ends up reading the reference's one measurement plus its own propagation delay. These are deliberately not the same number: a device further down the wire sees the frame later, so its clock is set ahead by exactly that extra amount. Every device therefore shows the same value at the instant the frame reaches it, which is what acting together requires.

The single reading is what makes this work. If the master re-read the reference before each device, and each read costs one round trip of roughly 60 000 ns, device 2's offset would be built on a reference reading taken 60 000 ns after device 1's. The two clocks would end up that far apart, which is about a hundred times the 300 and 640 ns delays being corrected.

Then the sync unit is switched on. Aligned clocks let devices agree what time it is; a SYNC pulse is what makes them act at the same instant — sample a sensor, latch an output — rather than as the frame sweeps past. The master writes the pulse period, optionally a second slower one, and activates the unit.

Activation comes last. The unit starts generating pulses the moment it is activated, so activating before the offsets are written produces pulses from clocks that have not been aligned. That failure is harder to diagnose than no synchronisation, because the pulses are present and appear correct.

What this master does not do

It aligns the clocks once, at startup, and does not resynchronise them afterwards. There is no cyclic datagram that reads the reference clock and redistributes it.

The standard names the mechanism this leaves idle. A device's local clock "is incremented by 10 every 10 ns and depending on the drift of the clock by 9 or 11 ... for drift compensation" — that is, the hardware can run slightly fast or slow to correct itself. It decides which by comparing its own time against a value the master writes.

So the correcting loop exists in every device, and this master configures its parameters at startup. What it never does is write the comparison value again afterwards. With nothing to compare against, the correction has no input, and each clock free-runs from its initial offset at whatever rate its oscillator differs.

So synchronisation here is exact at startup and decays from there, at a rate set by crystal tolerance rather than by anything the master controls. For a short run or a loose requirement that may be fine. For sustained microsecond-class synchronisation it is not, and it should be settled before relying on it.

Cost

One broadcast frame plus a bounded number of reads per device. All of it happens before the cyclic loop is frozen; the cyclic path consumes the resulting plan and measures nothing.

Mailbox

Transferring parameters and files

Runs when

a parameter is read or written, or a file is transferred

How often

On demand. During OP, only inside the acyclic window.

Cyclic data is the same few bytes every cycle. Everything else — reading a fault code, writing a gain, loading firmware — is a request and a response through a mailbox.

Values larger than one message

A parameter might be one byte or several kilobytes. Small values ride inside the request itself. Larger ones are split into segments, and segments raise a problem: they look alike. A duplicated or retransmitted segment appended twice corrupts the value silently.

So each segment carries a bit that alternates. A segment whose bit did not alternate is a duplicate, and it is reported as a protocol error rather than accepted. The specification even has a dedicated abort code for it.

Abort codes are preserved rather than collapsed into a generic failure. The code is what separates "no such object" from "wrong size" from "read-only", and an integrator has no other source for that distinction.

How much data one segment carries

A segment always carries seven data octets, and a small count in its header says how many of the seven are real. That encoding cannot describe anything larger than seven. A device with a bigger mailbox sends more than seven in one segment, sets the count to zero, and the real size has to be taken from the message length instead.

Reading the count in both cases looks safe, and that is what makes it dangerous. Zero unused octets reads as seven — a sensible-looking answer that is wrong for every segment larger than the minimum. The rest of the segment is discarded, the transfer still ends when the device marks its last segment, and the caller gets a short value with nothing reported as failed. So the length governs whenever the message is longer than the minimum, and the count applies only at the minimum.

Transferring files, and handling a busy device

File transfer numbers its packets and ends when a packet arrives shorter than a full one. That is why a file whose length is an exact multiple of the packet size must end with an empty packet — the terminator is shortness, not a length field.

A device may answer that it is busy. The transfer retries the same step without advancing its packet number, and the number of retries is bounded. An unbounded retry is how a device that is permanently not ready becomes a master that never finishes.

Staging firmware, which is not applying it

The highest-consequence operation a master performs is also the one the standard says least about. It defines file transfer. It does not define what a device does with a firmware image once it has one.

So the master reports Staged, not success. It knows the bytes arrived. It does not know whether the device accepted them, whether it will boot, or which slot it chose. Claiming success would be claiming knowledge the master does not have.

Everything checkable is checked before any byte goes on the wire: an explicit destructive-write allowance from the caller, a non-empty image and filename, a maximum size, and optionally a checksum the caller supplies. A firmware transfer that fails part-way can leave a device unbootable, so a check that can be made early is made early.

Cost

One round trip for a small value. For larger transfers, roughly the byte count divided by the payload size, each costing one slot in the acyclic window — so a large transfer during operation is measured in cycles, not microseconds. Reading and writing are not symmetric: a read accepts whatever segment size the device sends, while a write emits the smallest legal segment and so spends one round trip per seven octets no matter how large the mailbox is.

Acyclic traffic

Budgeting the acyclic window

Runs when

the cyclic exchange of a cycle has completed

How often

Once per cycle, bounded by a configured message budget.

Not all traffic is cyclic. Reading a drive's error register, downloading a parameter, transferring firmware — these are request-and-response exchanges through a mailbox, and they share the wire with the cycle that must not be late.

Both kinds of traffic go out on the same wire, and a cycle is late if anything delays the frame carrying its process data. A mailbox exchange placed ahead of that frame adds its own transmission time to the cycle; one placed after it cannot, because by then the cyclic frame has already been sent and its response received.

The ordering is therefore fixed: acyclic work runs after the cyclic exchange has finished, never before it, and never for longer than its budget allows.

one cycle process data exchange acyclic window idle next tick deterministic — must not be extended bounded by a message budget One arbiter governs the window, not one per protocol. Separate budgets would each be honoured while the cycle paid their sum.
Figure 3 Acyclic work rides after the cycle, inside a budget.

The budget's scope is the part that has to be right. If parameter transfers and firmware transfers each keep their own per-cycle allowance, each is individually well behaved while the cycle pays for both. One arbiter, indexed by device, owns the whole window, so the cap applies to the total and one talkative device cannot occupy the window while another waits.

Cost

Bounded by the configured message cap per cycle. Queue capacity is fixed when the master is configured, so the window allocates nothing — which is the property that lets it run inside a real-time loop at all.

Supervision

Running three regions concurrently

Runs when

every cycle tick, once the bus is in OP

How often

Continuously, for as long as the machine runs.

A master in OP is doing three separate jobs on the same tick: exchanging process data, servicing whatever mailbox work is queued, and watching whether the segment is still healthy. Writing that as one flat state machine either loses the concurrency or multiplies the states until nobody can reason about them.

So OP is three regions that advance independently.

Worked example

A mailbox read to a diagnostic device times out mid-cycle:

RegionBeforeAfter
process datacyclingcycling — unaffected
acyclicwaiting for responsefaulted, with the mailbox reason
supervisionhealthydegraded

Outputs keep being driven. That is the behaviour a machine needs: losing a diagnostic read is not a reason to stop a moving axis. Had the regions been one state machine, the fault would have had nowhere to live except the whole master.

The other benefit is in what recovery sees. Because the fault is recorded in the region that failed, and carries its own reason, recovery policy can tell a working-counter fault from a mailbox fault and respond differently. A single global fault state would have told it only that something went wrong.

Within the process-data region, the substates — waiting for tick, sending, receiving, checking the counter, complete — describe ordering inside one tick, not a sequence of ticks. The whole exchange runs to completion before the cycle call returns.

The same treatment for DDS

The Tin DDS and Retina algorithms are documented the same way, in fourteen parts.

DDS algorithms →

These descriptions follow the EtherCAT master implementation and ETG.1000. Evaluation access and the full algorithm notes are available from engineering@tinverse.com.