MessageRouting.cpp

#include "BleStar.h"

/*
	Methods to route messages.  Messages have a specific lifecycle based on how they originate.

	Definitions:
		- This device - this device.  Note that this is also given an entry in the routingTable
		- parent device - a device that's connected to this device where this device is a peripheral.
		  nrf52 and nr51 devices both support this.  There's only one possible connection here
		- child device - a device that's connected to this device as a peripheral where this device is acting as central
		  only nrf52 devices can support this, and there can be multiple child devices
		- upstream devices - devices findable by walking up parent device connections
		- downstream devices - devices findable by walking down child device connections
		- connected devices - parent and child devices with active UART connections
		- gateway device - the ultimate parent device; usually this one is connected somehow to the cloud and relays messages to/from that


	Topology example where THIS DEVICE is connected to a PARENT DEVICE upstream, and ultimately UPSTREAM DEVICE, and
	is connected to 3 CHILD DEVICES, through which it can reach N DOWNSTREAM DEVICES

	- UPSTREAM DEVICE (the ultimate parent device is a.k.a. a GATEWAY DEVICE)
	    - PARENT DEVICE
			- THIS DEVICE
				- CHILD DEVICE 1
				- CHILD DEVICE 2
					- DOWNSTREAM DEVICE 1
				- CHILD DEVICE 3
					- DOWNSTREAM DEVICE 2
					- DOWNSTREAM DEVICE 3
					- ..
					- DOWNSTREAM DEVICE N
			- [OTHER DEVICE CONNECTED TO PARENT]
				- etc.
		- [OTHER DEVICES...]

	There are a few fields in each Message that control behavior:
		- messageType int {ORIGIN, HOP, AWAITING_NEW_MESSAGE, NONE}
			ORIGIN = a message that has been generated by the user/a program using BleStar
					 these messages stay in the MessageTable at the originating device until a successful ACK/NACK/timeout
			INCOMING = a message that's incoming from a HOP but hasn't been fully received yet.  Once received it
 					 will be routed and become one or many HOPs, or will become NONE (i.e. no further path to destination)
 					 these can also trigger a message received callback if the receiving device is a match
 			HOP = 	 temporary message entries that only exist until the message has been ACK/NACKed/timeout from connected devices
					 there can be multiple hops created by any incoming or sent message
			NONE = 	 the MessageType once a message has been routed or is no longer needed.  When the messagetable fills up
					 these will be disposed of and the messageTable defragmented

		- hasBeenRouted (boolean) = whether or not a message needs to be routed.  Usually applies for ORIGIN/AWAITING_NEW_MESSAGE
					 the routing algorithm ignores these entries typically if true

		- isSystemMessage (boolean) -- these never need acknowledgement to the origin.  Not used in routing
		- origin - the ultimate origin of the message; always a device name (and used so that ACK/NACKs can be routed back to this)
		- destination - the ultimate destination or the message.  This can look like:
					A device name (e.g. "GOVEE_3422"); a unique name for a specific device
					A subscription name (e.g. "/ECUDATA"); a name that starts with a slash and multiple devices can consume this message,
									similar to how MQTT works
					A * (literally "*"); this means send to all connected devices, and should be used sparingly, most likely by system Messages
					A "" (literally null / a zero length string).  This translates to "send upstream to ultimate patent node"; useful
									for messages that need to find a gateway for transmission onwards to the cloud, etc.
									This is also used by system messages to update routing tables of what's reachable downstream
		- fromHop = where the message just came from.  This is a directly connected device name
		- ToHop = where the message will next be sent.  Also a directly connected device name.  The message routing methods
					find out what this is based on the routing table and fill this in

	Because the messageTable can only hold a limited number of entries, entries are only routed once there is sufficient space to fan
	out messages into the number of hops required, so routing will often "wait" until these is space in the messageTable for this.  The
	messageTable also has to allow space for new incoming messages and new user sent or system messages, so the priority is:

	 	1. _messageTableCapacity - _messageTableSize < _numberOfBleConnections:
		 			only system messages allowed, or receiving new messages (could be from every entry simultaneously)
		 			can only route messages if forwarding to one device (i.e. no net new messageTable entries created)

		2. _messageTableCapacity - _messageTableSize < _numberOfBleConnections * 2:
		 			can route messages, user cannot send new ones (need to leave space for fanning and getting rid of
					existing messages that need to be routed)

		3. _messageTableCapacity - _messageTableSize > _numberOfBleConnections * 2
					Users can send messages if they like

	When the messageTable looks like it is filling up, and cannot meet the above, it is by default optimized to delete "NONE"
	entries, thus creating space for more, but if there are lots of messages hitting the device hard, and the messageTable is
	not big enough, then this optimization will cause performance to suffer.  Keeping the messageTable sufficiently large is
	therefore important for performance.


	There are a few typical states in the lifecycle of a message:
		 1.  Message created and "sent" by user (or system message):
		 			a. Check for space in messageTable, optimize if necessary, return false if not enough space
					b. Message is stored in messageTable ORIGIN:  requiresRouting = true

		 2.  PollRoutingMessages() is called regularly
		 			a. if no messages/routing has changed, then we return and don't waste CPU trying to route anything
		 			   messageTable is scanned from earliest entry to latest to look for anything that needs routing
					b. if there's a message that needs routing, the method checks for how many net new message entries are needed
					   and then how many messageEntries are needed based on how many routes are in the routingTable for each destination
					   If insufficient, pollRoutingMessages() returns without doing anything.  There may be messages that needs fewer fan-outs
					   later in the message queue, but this method is FIFO only
					c. If the method gets this far, and hasBeenRouted is false, it calls routeMessage(Message * message),
					   which then "fans out" the origin/incoming message to wherever the routing table indicates it can
					   find a route to the destnation
					d. pollRoutingMessages() then keeps looking for more messages to fan out if there is space remaining


		3.  For each message that can be routed, routeMessage() is called
		 			a. routeMessage looks up the routingTable and allocates a new entry in messageTable that points to the same place in
					   messageBuffer (so we don't end up using space to duplicate the same messageBuffer) as follows:
					   	- if messageType = ORIGIN, a new entry of messageType = HOP is created, the ORIGIN message remains, hasBeenRouted = true;
						- if messageType = INCOMING
							First, this incoming message is repurposed to be messageType "HOP" with the destination found in the routingTable
							Any subsequent routes get a new entry in messageTable with the required routing

					b. the rules used are as follows:
						i. if the destination is a deviceName, then there should only be one possible route - either the destination
						   shows up in the routingTable as accessible through a child device, or it MUST be upstream in a parent device.
						   The one exception is that if a message cannot be routed back through where it came from or we risk an
						   infinite loop of some kind
						ii.if the destination is a subscription name, then it starts with a '/' (slash) and it can be routed to more than
						   one device, so it is routed to whichever child devices have a route to the destination device with a subscription
						   if the message comes from a child/downstream device, it is always also sent to the parent device, as there
						   may be subscriptions resting in upstream devices (or "OTHER DEVICES" in the diagram above)
						iii. if there is no route found the the message is ignored, unless it's routed to a gateway and the destination is a unique
						   device name, in which case a routed NACK is sent



*/


// check for "stuck" messages also in here.....

/*! \brief Brief description.
 *         Brief description continued.
 *
 *  Detailed description starts here.
 */


void BleStar::pollRoutingMessages() {

	// First check if anything has changed, and if not, exit to spare CPU cycles
	if (!mTable.getMessageTableHasBeenChanged()
		&& !rTable.getRoutingTableHasBeenChanged()
		&& !Message::getMessagesHaveBeenChanged()
	) { return; }

	int totalMessagesRouted = 0;
	int totalRoutesUsed = 0;

	for (int i = 0; i < mTable.getSize(); i++) {
		Message * m = mTable.getMessage(i);

		if (m->getRequiresRouting()) {
			char * destination = m->getDestination();
			int fromBleDeviceIndex = getBleDeviceIndex(m->getFromHop());
			int routingTableIndex = rTable.getIndexFromNamePointer(destination);
			if (routingTableIndex < 0) { routingTableIndex = rTable.getIndexFromName(destination); }

			// first calculate how big the messageTable needs to expand by - if requied
			int newMessageTableEntriesRequired = 0;
			if (destination[0] != '/') {
				newMessageTableEntriesRequired = 1;
			} else {
				for  (int j = BLE_PERIPHERAL_INDEX; j < MAX_CENTRAL_CONNECTIONS + 2; j++) {
					if ((fromBleDeviceIndex != j) && rTable.getDoesRouteExist(routingTableIndex, j)) {
						newMessageTableEntriesRequired++;
					}
				}
			}

			if (newMessageTableEntriesRequired == 0) {
				Log.w("Error: no route found for message from %s in routingTable", m->getFromHop());
				return;
			}

			// now ensure there is space in messageTable to fan out messages if required

			if (m->getMessageType() == MESSAGE_TYPE_INCOMING) { newMessageTableEntriesRequired--; }
			if (mTable.getCapacity() - mTable.getSize() - newMessageTableEntriesRequired < _numberOfBleConnections +2) {
				mTable.defragmentMessages();
			}
			if (mTable.getCapacity() - mTable.getSize() - newMessageTableEntriesRequired < _numberOfBleConnections +2) {
				Log.w("Warning:  MessageTables close to capacity (%d of %d slots used), cannot routes more messages", mTable.getSize(), mTable.getCapacity());
				return;
			}

			// now route the messages as required
			mTable.makeSpaceForRouting(i, newMessageTableEntriesRequired);
			int messageTableIndex = i + (m->getMessageType() == MESSAGE_TYPE_ORIGIN ? 1 : 0);
			int routesUsed = 0;

			// scan the routing table backwards - the bleperipheral option should be looked at last as a potential route
			for (int j = MAX_CENTRAL_CONNECTIONS + 2; j >= BLE_PERIPHERAL_INDEX; j--) {
				if (fromBleDeviceIndex != j && rTable.getDoesRouteExist(routingTableIndex, j)) {

					if ((routesUsed == 0 && m->getMessageType() == MESSAGE_TYPE_INCOMING)) {
						mTable.setHopsInMessage(m, _thisDeviceName, bleDeviceTable[j].peerName);
					} else {
						mTable.cloneMessage(m, _thisDeviceName, bleDeviceTable[j].peerName, messageTableIndex);
					}
					routesUsed++;
					totalRoutesUsed++;
					messageTableIndex++;

					if (destination[0] != '/' && destination[0] != '*') { return; }
				}
			}	// j loop, scanning through available connections in routing table
			totalMessagesRouted++;
		}	// if requiresRouting
	}	// loop through messageTable
	Log.i("MessageRouting called, routing %d messages, used %d routes", totalMessagesRouted, totalRoutesUsed);
}