Seidenstrasse routing

algoritm.md

Algorithm

busy(X): holds if node X is marked busy
mark(X): the transaction id node X is currently marked with

1. Create a empty list L of transactions to execute
2. Mark all nodes in the network as idle
3. For each transmission T in the transmission list:
	3.1. Lookup the first transaction X = (I, S, E) of T
	3.2. If (!busy(S) and !busy(E)) and ((mark(S) = 0 and mark(E) = 0) or mark(S) = I):
			add X to L and remove it from T
	3.2. If busy(S) and busy(E):
		3.2.1 Check for a conflicting transaction in L
		3.2.2 If a conflict Y = (_,S,E) from transaction T' exists for X
			3.2.2.1 Create two new transactions X_1 and X_2 with X_1 = (I, S,S_Storage) and X_2 = (I, S_Storage,E)
			3.2.2.2 Prepend T with X_2, X
			3.2.2.3 Prepend T' with Y			
			3.2.2.4 Remove Y from L, add X_1 instead
4. For each transaction (_, S,E) in L: Send 'prepare send' to S and 'prepare receive' to E to the routers
5. While L is not empty:
	5.1 For each transaction T = (I, S, E) in L:
		5.1.1 If 'prepare send' to S and 'prepare receive' to E have been acked:
			5.1.1.1 Send 'send from S to E' to the routers
		5.1.2 If 'send from S to E' has been acked:
			5.1.2.1 Mark node S with transmission id 0
			5.1.2.2 Mark node E with transmission id I
			5.1.2.3 Remove T from L
5. Goto 1

terms.md

Terms

Node

Point were one or more tubes end.

Endpoint

Node with exactly one tube ending, without local storage.

Router

Node with more then one tube ending an local endpoint and local storage. Each local storage is slot is treated as a virtual endpoint nodes. Same applies to the local endpoint. A router can have exactly one capsule in it mechanics, therefore it has to send this capsule to an other node (meaning: other node, local storage or local endpoint) before it can receive an other capsule.

Route

Ordered list of all nodes, a capsule has to pass to get from node A to node B, with A != B.

Action

Basic atomic actions that can be performed by routers.

• prepare A to receive from B: Put the router A into a state, which allows receiving a capsule from node B
• prepare A to send to B: Put the router A into a state, which allows sending a capsule to node B
• send from A to B: In case A is a router it starts to pull. In case B is a router it starts to push. Assuming A and B are adjacent nodes with A != B and at least one of them is a router.

Transaction

The process passing a capsule between two adjacent nodes A and B, with A != B. Abstracted as a threetuple (tranmission id, node A, node B). Assuming the capsule is passed from A to B the following actions are required:

1. prepare B to receive from A
2. prepare A to send to B
3. send from A to B

The first two actions can be performed in parallel. The third action can only be executed after the first two have been complete successfully. In case a transaction can not be executed completely the network enters an error state, requiring manual intervention.

Conflicting Transactions

Two transactions conflict iff. they could to be executed at the same time, but the end node of one transaction is the start node of the other one, and vice versa.

Transmission

Ordered list of transactions required to transport along a route from Endpoint A to Endpoint B, with A != B. Each transmission is identified by a incremental id.