Network Ring on Microcontrollers

Hello, dear habrasoobschestvu!
Not so long ago, I had to deal with the network topology in the form of a “redundant ring”, the principles of which I would like to talk about.
In order to avoid misunderstandings, I should say right away that only devices on microcontrollers are connected to the ring - there are no switches on the line and so on. Only microcontrollers with a physical Ethernet layer in the form of a three-port hardware switch Micrel (about it - below). Well, since Ethernet was used, I will allow myself the liberty to continue using the expression “network ring”.

Initially, the post was planned as a translation of ways to organize a ring from this document with jokes and tricks with comments and additions. In the development process, the proposed options were tested, but they did not suit for some reason. What this article was born from. I hope that the ways of organizing the work of the network ring described here can be useful not only for me.
Who cares - welcome under cat.
Under the cat a lot of letters and traffic

A little bit of the simplest theory.

Whoever is familiar with the topic, can safely move on to the next section (“The Essence of the Task”).
')
Let's start from afar. If it is necessary to combine more than two devices into one network, then the problem of network configuration arises. After all, interconnected devices can be in several different ways (in a different order, so to speak). The layout and connection of network devices is called network topology . There are three basic topologies: Star, Tire and Ring. In this article we will consider the topology in the form of a ring.

So, imagine spherical devices in vacuum, several devices, networked as follows:

This is a typical network ring. Typically, in such a ring, data is transmitted strictly in one direction (for example, clockwise). In this case, the breakage of at least one communication line can lead to the inoperability of the entire system. But depending on the method of communication between devices, the ring may become “redundant”. This means that even if we deliberately (or not deliberately) break one of the connections, data transfer between devices will still be possible in full. But this requires the proper organization of the exchange in the network ring. What we will do next.
It is worth mentioning that in a ring topology, redundancy can also be achieved through the use of a double ring, in which data is duplicated and transmitted in different directions, but we will only talk about the topology with one ring.

So, redundancy makes it possible to ensure operability in the case of a single break. This is undoubtedly a plus, but on the other hand it creates some problems. For example, if one of the devices sends broadcast packets (Broadcast), then each subsequent device in the ring will broadcast them to its neighbor and so in a circle to infinity, which ultimately can lead to a complete network failure (the so-called Broadcast storm ). To prevent this, special protocols were developed to avoid “looping”, as well as to find the shortest paths in the network topology. Such protocols, for example, are STP, RSTP, MSTP and STB. Basically, these protocols are designed for complex topologies, in which configurations can be used both in the form of a star, and in the form of a ring, and in more complex combinations of the three basic topologies. More information can be found here , here , and here .

The essence of the task

To organize the exchange between devices in such a way that a storm does not occur, and in the event of a single break, the network must remain operational. In addition, it should be possible to accurately determine the location of the ring break.

What we have

• 14 devices on microcontrollers (STM32F207) installed in an electric train
• Devices connected in one ring
• Micrel KSZ8863 / RLL hardware switch is used as the Ethernet physical layer.
• The load on the processor from the use of the network should be minimal . In fact, this is one of the most “main-priority” requirements, since the real-time processor deals with quite resource-intensive tasks and every millisecond counts
• It so happened that the connection point-to-point was not needed. Only Broadcast is used. But the final solution allows you to implement this as well (with certain completion)

Since all further algorithms will be directly connected with the KSZ8863 / RLL switch, then a little more about it:
Datasheet here
In short:

• a three-port switch (two Ethernet ports are “out” and one is “inward” per processor, hereinafter referred to as ports No. 1, 2 and 3, respectively)
• Separate MAC addresses for ports 1 and 2
• Interfaces to the processor: MII and RMII plus interfaces for control - I2C and SPI
• 8 static routes (oh, how late I saw this footnote in the datasheet, but more on that later)
• Filtering "their" packets when routing (such a protection against looping)
• Dynamic routes (he learns on the basis of MAC addresses and the port number on which packets arrive)
• Support for VLAN ID, speed 10/100 megabits, autonegotiation, he himself is able to determine the "overlap" of the cable, the distance in meters to the point of cable break and a few more buns

Finding a solution

At the initial stage of development, it was immediately decided to abandon the existing network control protocols (STP, RSTP, etc.) for the following reasons:

• Too much extra for our simple topology.
• None of these protocols is hardware supported by the physical layer. And, accordingly, the load falls on the processor, which is already not sweet. Although there is a line “IEEE 802.1d rapid spanning tree protocol support” in the datasheet of the switch, in fact this means that the datasheet provides an approximate algorithm that can be implemented by means of a processor, which is not quite suitable for us.

And also, since our system only needed broadcasts, to reduce the load, it was decided to abandon the transport layer protocols, that is, to do everything on “bare” Ethernet packets.

But first, let's see how the manufacturer of switches offers us to build a ring.

Option number 1 (an attempt to solve the problem only by means of the physical layer - unmanaged ring)

Next comes a free retelling of the document by reference from the article title.

Filtering by MAC address of the device sending the packet (MAC Source Address Filtering)

The switch implements a hardware mechanism for “Learning” and “Forwarding” packets. After receiving the packet, the switch “learns” - saves the sender's address and the corresponding port number from which the packet was received in the MAC dynamic routing table. A packet forwarding decision is made based on this table and the MAC address of the destination device (Destination MAC). If a match is found in the table (the MAC address is already known to the switch), then the packet is redirected to the corresponding port. If the address is unknown, then the packet is broadcasted to all ports, except for the one from which it was received (this is the default behavior and it is configured).

Thus, when a packet is received, the sender’s address is only memorized and not used when making a routing decision. This is fraught with the appearance of "looped" packages. However, if the switch is able to filter (and KSZ8863 can) incoming packets based on the sender's address, then the implementation of an unmanaged ring is possible. As soon as the switch receives a packet, the address of the sender in which coincides with the local MAC address of one of the ports, the packet is dropped (drop). That is, the package is removed from the ring after passing a full circle.

Schematically, this can be represented as:

Approximate algorithm:

1. The switch receives a packet from the processor (from port 3)
2. Sends it to one of the ports (for example, always to port number 2)
3. The packet runs through the full ring and is dropped by the sender (in the picture, the 1st switch sent the packet and, after the full circle, it dropped it)

Pros:

• Everything is done by the switch, there is no load on the processor

Minuses:

• If you break one of the links, the network will stop working

It does not suit us. We look further.

Option # 2 - Redundancy based on option # 1

The easiest way to organize redundancy by filtering at the sender's address is to send packets received from the processor to two external ports at once (on both sides of the ring). In this case, with a single break, the package will still receive all the devices. The most important problem is that if there is no break in the ring, all devices will receive this package twice (duplicate). On the other hand, by the absence of duplicates, it is possible to determine between which devices the break occurred. Everything works like this:


Here, as in the previous version, the packet runs in a circle and is dropped by the sender.

As already mentioned, the disadvantage is duplicate packets that increase the load on the processor and reduce the efficiency of the network. In addition, obtaining duplicates will lead to a problem with the learning mechanism of the switch. First, the dynamical table will constantly change (a packet comes from one port, then another one, and the MAC address is the same) and the worst variant of the path will always be the last (the packet that went the longest will write the “worst” port to the table) . Secondly, it can lead to the fact that one of the packages will be dropped as a “local package”. Local is a packet that arrives from a port to which it must be redirected during routing. It turns out something like this:


Explanation of the figure:

1. Processor 4 sends the packet to device 1
2. Switch number 4 sends it to both external ports
3. On switch # 1, the first packet arrives at port 1 (because the distance is shorter) and the port is set to 1 in the routing table for MAC 4.
4. Then on switch No. 1 a duplicate of the packet will come to port 2 (the distance is longer and we need to go through two devices) and the port will be set to 2 in the routing table for MAC 4.

Then the following happens:

1. Processor 2 sends the packet to device 4
2. Switch 2 sends it to both external ports
3. The packet arrives in switch # 1 on port 2 and is dropped because in the routing table it is determined that for MAC 4 packets need to be redirected to the same port.
4. Device number 4 in the end will receive only one package without a duplicate.

As a result, we have the fact that we can not accurately determine why there was no duplicate. And what exactly was the reason for the disappearance of a duplicate - a break or an accidental drop.
In order to make sure that both duplicates come when there is no break, you need to disable training in a switch. Disabling training leads to the fact that the routing table always remains empty and local packets are never dropped. The main disadvantage of this solution is, again, shifting the load of digging deductions on the processor. In this case, all incoming packets are sent to port 3, regardless of whether they are addressed to the processor or not. This problem can be solved by prohibiting the redirection of packets with unknown addresses to the third port (so that all packets pass “by” except those addresses that are in static routes).

Pros:

• At break the network will continue to work

Minuses:

• Additional processor load

Note: After all the frills, I did come to this version with some changes and my own protocol. But so far we do not know this, so let's continue to try the options ...

Option number 3 - Improved version of the previous one (now - managed ring)

As already mentioned, the main disadvantage of the previous method are duplicate packets, increasing the load on the processor. In this version we will fix it by doing this:

• Each device in the ring should turn off one of the external ports on reception ( note: all devices must turn off the port with the same number !). Due to this we get:
  
  • Packages in the ring will only move in one direction.
  • The receiver will eventually receive only one packet without a duplicate.
  • Disabled port will be used in case of ring break.

Also here we will use a special switch interrupt, which signals a link status change ( Link Status Interrupt ).

This solution already requires constant monitoring and (in the event of a break) control from the processor. That is, in fact, the ring is already becoming managed (managed), but instead we get fast fault detection and fast ring reconfiguration even in large networks.

Switch initialization:

1. We disable training on ports 1 and 2 in each device.
2. We configure a static route by which all packets with the recipient's address equal to our local one are sent to port 3 (per processor).
3. We enable routing for unknown addresses (all packets with unknown addresses of recipients will roam to both external ports).
4. Disable reception on the 2nd port in all devices.
5. Enable interrupt by changing the status of the line.

As a result, all traffic comes to the first port and leaves the second (packets run clockwise).

If the connection between the devices is broken, then the Interrupt (Link Status Interrupt) comes to these devices and we must proceed to reconfigure the ring.

Reconfigure Ring:

The procedure is very simple and takes place with minimal delays.

1. After receiving, we check which port is open.
2. If first, then
   
   • We send a broadcast message to all devices that port 2 must be enabled for reception
   • We include receiving packets from the 2nd port in
3. If on the second port, then
   
   • Ignore the Broadcast message that you need to enable the 2nd port to receive
   • Making diagnostics, if necessary.

KSZ8863 has a built-in mechanism for determining the location of the break (from the internal registers, you can read the approximate distance in meters to the point of cable damage).

Ring restoration:

When the cable is fixed, we will again receive a Link Status Interrupt

1. Checking which port the interrupt came on
2. If on the first, then we send a broadcasted message to all devices that it is necessary to disable reception from port 2

Packages start running clockwise again. Profit!

The document also contains the following figures:

Delay in rebuilding the ring:
Latency = T _interrupt + T _{read interrupt} + T _{broadcast message} + T _{enable P2 Receive}

T _interrupt = approximately 100us
T _{read / write} = 4.8us for an SPI interface with a frequency of 5Mhz (in order to write one register, you need to transfer three bytes)
T _message = (n - 1) x 7.7us (where n is the number of devices in the ring) is the time it takes a broadcast to reach the last device. Implied packet is 64 bytes long and 7.7us delay per device

We get:
Latency = 100us + 4.8us + (n - 1) x 7.7us + 4.8us

For example, for a ring of 16 devices we get:
Latency = 225us (approximately)

Based on the above formula, you can calculate the maximum number of devices in the network with the maximum allowable delay:
For example, if the maximum allowed delay is 1ms, we get:
1ms = 100us + 4.8us + (n - 1) x 7.7us + 4.8us
n <(890.4 / 7.7) +1
Maximum number of devices in the ring: n = 116

This official document from the developers KSZ8863 ends.

Everyone is happy, thank you all, curtain ...

And after the curtain, as usual, the most interesting begins:

Option number 3, in principle, arranged for everyone. Naturally, with minor corrections, because as presented now, it is not entirely reliable. Let me explain with an example: if a Broadcast package sent after detecting a break doesn’t receive all the devices (you never know how it will turn out, the power may disappear), then the connection will completely fall apart.
But I didn’t have to dig deeper because another global problem had appeared.

So, we have a schematically depicted ring:



Unfortunately, the cars in the train are not so linked.

We unplug our train, install the devices in the cars as they should stand and get this:



The first mistake is immediately noticeable - in the figure, the cable that goes “along the bottom” of the cars is too long. Now I don’t remember exactly the length of the whole train, but this is about 250 meters. That is, for ethernet, a cable of such length is deadly.

In fact, this is not a problem, and the main developer came up with the best option - like this:



As you can see - now the cars are connected through one. Here are the port numbers on the devices. And you can see that they very well fit into the previously proposed version of the construction of the ring.

Profit? - As if not so.

Unexpectedly (aha, as always) , an additional condition appeared that in the process of operation any car (except the head ones) could be deployed. And the system, naturally, should work. And it turns out that's the trouble:



As you can see, the connection around the ring is broken. If it is not clear why - I will explain. In the previous picture, you can completely go around the ring, assuming, for example, that port 2 works only on transmission. That is, you can go through the chain: port 2 -> port 1, port 2 -> port 1. And so on. After the turn of the car, this principle is violated.

Therefore, from the seemingly ideal option, we had to give up and look for a new one.
Well, let's get down to the invention of bicycles ...

Bicycle №1 - Managed Redundant Ring Control Protocol (MRRCP) v1.0

Then the understanding came that the processor would have to be loaded anyway, and you will not get off with one physical layer with minimal control. You must be able to dynamically rebuild the ring for any configuration of compounds.
Like it or not, I had to invent my own protocol for controlling the ring. Actually, its epic name is given above.

Let me remind you once again that it was critical to load the processor as little as possible with the network. Therefore, from the point of view of the “correctness” of using Ethernet, everything that is further written in this variant is horror, flying on the wings of the night ...

Initialization:

1. Disable learning addresses in the switch
2. Local addresses for ports 1 and 2 are NOT set, we do not need them
3. We prohibit reception and transmission on all ports (static routes can “interrupt” these prohibitions - we use them)
4. We clear static routes in our switch.
5. We write the zero route here:
   
   • All that goes with the recipient's address 44: 44: 00: 00: 00: 07 (this is the type of Broadcast address for the MRRCP) is redirected only to the processor.

The meaning of initialization is that nothing at all without our permission to the processor does not fall and does not go into the network.

Directly algorithm:

Each device has a route table (in fact, it is an array of structures). Each such structure refers to a specific device in the ring. The structure is approximately as follows:

struct { //     ... unsigned char DestinationDevice; //       ,     unsigned char SendToPort; //  ""   -    + 1. unsigned char MinDistance; //       unsigned char NotUpdatedTimes; } Route; 

That is, each device knows how to get to any other (which port to send packets to and how far the device is located). The whole algorithm revolves around this route table.
After power-up, the entire route table is clogged with obviously incorrect values ​​so that the ring is built, so to speak, from zero.

At intervals of N milliseconds, each device sends its MRRCP packet to port 1 and port 2. N can be taken from the ceiling. For example, 200. It all depends on how critical the speed of ring reconfiguration after a break is. Reliability was more important for us (so that it would be precisely rebuilt, and not rebuilt somehow, but quickly).

The package is sent as follows:

• Destination MAC - 44: 44: 00: 00: 00: 07
• Source MAC - 22: 22: 00: 00: 00: XX , where XX is the device number
• EtherType - 0x7701 (selected so that it does not intersect with conventional)
• Package Body:
  
  • YY - the number of devices in the chain
  • XX - the number of the device that started the chain
  • ZZ..ZZ - Chain of devices - numbers of devices through which this package passed. That is, each device leaves its mark here and sends the packet further (with some reservations - see below).
• In the last four bytes of the Ethernet packet, a hardware-calculated checksum is transmitted (CRC32)

Processing MRRCP packet:

1. A variety of checks on the validity of the data in the package (checking the device number of the sender, checksum, etc.)
2. We pass a chain of devices in a loop, starting from the end :
   
   • The latest device in the chain is the number of the neighbor nearest us, the last but one is the number of the neighbor through one device, etc. This determines the “distance” to the chained device.
   • If the distance to the device is less than the one that is stored in the route table, then we update the route in the processor’s memory and also update the static route No. X in the switch (where X is the device number from the chain). Please note that you need to update exactly if the value is less . Because with an even number of devices in the ring, the opposite devices will have the same distance both on one side of the ring and on the other. For an example, look at devices # 1 and # 8 below.
   • In addition, it is necessary to enclose routes if the NotUpdatedTimes field exceeds a certain limit (this is the timeout of the validity of the route). That is, if the route has not been updated for a long time and suddenly a packet from this device has arrived, then it will be updated, even if the distance is greater than what is stored in the route table. This is necessary to rebuild the ring when the cliff. The NotUpdatedTimes field is incremented by a timer and reset when we receive a packet from the device, and the correct values ​​are already recorded in the route table for it.
3. If the packet was not sent by our device (and if our device is not found in the chain), then we add our number to the end of the chain and send it to the port “opposite” to where the MRRCP packet was received (for example, from the 1st, then 2nd and vice versa, that is, we kind of let the package pass through us, adding the mark that the package passed us). Checking for the presence of our device in the chain is needed for the drop of packages that have already run in a circle.

Here is a small example in the figure:


For the device number 8 (it is opposite to the first one), the routes will be built depending on which side of the ring the first package will “run faster”.
Note that the figure shows the routes that are stored in the processor's memory, and not the static routes of the switch.

About writing static routes to a switch:
Routes need to be written this way:
Dest.MAC - 55: 55: 00: 00: 00: XX , where ( XX is the device number from the chain)
Forwarding Port - port number, opposite to the one from where the packet + port 3 came from (processor). That is, if the packet came from port 1, then you need to write down port 2 and vice versa. Why this is the case - see the explanation below.

In general, the algorithm works as follows:

• Initially, there is no exchange other than MRRCP packets.
• After the MRRCP packets from each device run through the entire ring once, in all devices the overall picture of the network topology appears (to which port to send to)
• Data exchange between devices starts.

Thanks to static routes (with ports “vice versa”) we can broadcast broadcasts, but there will be no point-to-point communication.

For broadcasting by Broadcast, you need to send a packet to both ports (1 and 2) with Dest.MAC 55: 55: 00: 00: 00: XX , where XX is the number of your (yes, yes, your own) device. Due to the reversal of port numbers in static routes, a broadcast will pass through all devices around the ring and drop on the device, “on the back of the ring from the sender. There will be no duplicates because they will be dropped based on static routes

Explanation:



The break point is determined on those devices whose maximum distance to the most distant device is N - 1 (where N is the number of devices in the network). See picture:



It can be seen that devices №1 and №6 will have routes with a distance (6 - 1) = 5 , which means a break between them.
For a ring with an odd number of devices, a break is considered a little different - a little easier there.
An alternative option to define a break can be to use the Link Status interrupt, as described above.

Pros:

• The ring is dynamically rebuilt when the network is broken and restored

Minuses:

• It seemed that they were not, but I was wrong

Total:

Everything worked on the debugging stand of 3 devices, but in the invention of bicycles I couldn’t stop ...

Bike number 2 - the final, MRRCP v2.0

When checking, it turned out that devices with numbers higher than seven work in the ring incorrectly. After killing a day looking for a problem, it turned out that I (I repent and pour ashes on my head) did not notice a footnote in the datasheet of the switch that he has only eight static routes. That is, the algorithm only works if the devices in the ring are less than 8. It was an epic file. But there was a good reason to rework the crutch with Dest.MAC for Broadcast from the previous bike.

This is how the new and final version was born. It differs only in the work with the switch. With MRRCP packets, everything stays the same.

Initialization:

1. Set local MAC addresses for ports 1 and 2 in the form of 22: 22: 00: 00: 00: XX , where XX is our device number
2. Clear static routes
3. We write the zero route here:
   
   • All that comes with the recipient's address 44: 44: 00: 00: 00: 07 (this is the type of Broadcast MRRCP address) is redirected only to the processor in port 3.
4. We write the first route like this:
   
   • All that comes with the recipient's address 55: 55: 00: 00: 00: 01 (this is a type of Broadcast address for data) is redirected to all ports (the switch itself will pass the port to which the redirected packet was received).
5. We disable training, as well as reception and transmission on all ports (so that only static routes are working)
6. Turn on the Source MAC filter on ports 1 and 2 (so that the device that broadcasts broadcasts drops its packets after running through the full circle)

MRRCP packets are sent in the same way as in the previous version. And in the handler, you just need to remove the entry of static routes in the switch.

Now Broadcast is done like this:

1. The broadcasting device sends the packet to both ports with Dest.MAC 55: 55: 00: 00: 00: 01 and Src.MAC 22: 22: 00: 00: 00: XX , where XX is the number of its device
2. Packages pass in a circle around the ring and are dropped by the sender.

The definition of ring rupture is the same as in the previous version.

If you need a point-to-point connection, you can implement it by adding to the initialization a static packet forwarding setting with a Dest.MAC equal to the local MAC to port 3. And also configure packet forwarding with unknown addresses to ports 1 and 2.

Pros:

• It uses only two static routes of the switch and at the same time the number of devices is not limited to the 7th.
• You can organize a point-to-point relationship.
• In the ring, routes automatically change after changing the network configuration.
• There is no constant exchange with the switch on the management interface (I2C). It turned out to be important, since three more devices “hang” on the same interface. The switch is configured only once after power on.

Minuses:

• Duplicate packages. To screen them out, we just need a route table, by which we can filter packets that come from the “wrong port” directly in the Ethernet interrupt without passing them further.

The time for rebuilding the ring was not exactly measured. With very much overestimated values ​​of timeout validity of routes and the period of sending MRRCP packets, the ring is reassembled in 1-2 seconds. In our case, this was enough.

The result can be summarized as follows - having driven on different bikes, we returned to option number 2 (from the developers of the switch) with modifications in the form of MRRCP.

Constructive criticism is strongly encouraged.

I hope that this article will be useful to someone and it will be possible to get around some rakes. Good luck!

UPD2 : MAC addresses for devices and for MRRCP packets were randomly selected. As dukelion noted, if everything is done according to standards, then MAC addresses have special bits for defining groups and functional MAC addresses. Link to IEEE tutorial .
UPD : Thanks for the invite, moved the article to the hub "Programming microcontrollers"

ps I can not give the source code. I hope you understand why.
pps I apologize if the explanations in places seemed too lengthy and the terms are not used quite correctly - I tried to explain in the most accessible language to make it clearer.
ppps It is very interesting to know how would you solve this problem with the foregoing? Thank.