Assessing Routing Algorithms for Payment Channel Networks

To analyze fitting routing algorithms for PCNs, we first need to specify a system model. For this, we follow the models presented in the related work, e.g., References [34, 39, 47].

We define a PCN as an undirected graph \(G = (N, C)\). N is the set of nodes, and \(C \subseteq \lbrace (n_1, n_2) \mid n_1, n_2 \in N\rbrace\) represents the set of unidirectional channels. Nodes are generally identified by a unique ID \(waddr_n\) that is referred to as wallet address. For communication with other nodes in the network, a possibly variable (IP) address \(ipaddr_n\) is used.

Each channel \(c \in C\) is represented by a pair \((n_1, n_2)\) of distinct nodes \(n_1, n_2 \in N; n_1 \ne n_2\). The maximum transferable amount of c is denoted by the total capacity \(cap_c \in \mathbb {R}^{\geqslant 0}\). Since the graph of the network is undirected, the capacities \(cap_{(n_1, n_2)}\) and \(cap_{(n_2, n_1)}\) are equal. This does not hold for the balances \(b_c \in \mathbb {R}^{\geqslant 0}\), i.e., the currently transferable amount of each direction. \(b_{(n_1, n_2)}\) is the amount that node \(n_1\) can transfer to \(n_2\). The balance \(b_{(n_2, n_1)}\) applies vice versa. After a transaction, the balances are updated accordingly, so that \(cap_{(n_1, n_2)} = cap_{(n_2, n_1)} = b_{(n_1, n_2)} + b_{(n_2, n_1)}\).

Most of the nodes, channels and balances are not considered to be known by an individual node, due to the distributed and dynamic nature of a PCN. We assume that a node n is always aware of the channels it is part of, i.e., \(C_n = \lbrace (n_1, n_2) \in C \mid n = n_1 \vee n = n_2 \rbrace\), and their exact balances. Also, neighbor nodes \(N_n = \lbrace u \in N \mid (n, u) \in C\rbrace\), including their wallet and IP addresses are known by n. Beyond that, a node cannot be certain that information received earlier is (still) correct.

A payment is defined by a tuple \(P=(n_s, n_r, a)\). \(n_s \in N\) is the node that initiates the payment transaction (i.e., the payer or sender), \(n_r \in N\) is the receiving node (i.e., the payee), and \(a \in \mathbb {R}^{\gt 0}\) is the amount that is paid. All paths that can be constructed using the established channels between \(n_s\) and \(n_r\) are denoted by the set \(R_{(n_s, n_r)}\). Each path \(r \in R_{(n_s, n_r)}\) has a maximum payment value \(v_r \in \mathbb {R}^{\gt 0}\) that corresponds to the lowest balance of one of its channels in the direction of payment. The possible paths for P that can be used to transfer at least an amount of a are in the set \(R_P = \lbrace r \in R_{(n_s, n_r)} \mid v_r \ge a\rbrace\). Finally, the selection of a path in \(R_P\) is the responsibility of the node itself.

A node cannot be assumed to have prior knowledge of payments that are to be sent, received, or forwarded. Because of that, only historical information can be used to optimize the channel management and other operations. \(P_{i_n} \subseteq P_n\) denotes the payments that have been made by node n before the time i, whereas \(P_n\) represents the set of all payments by n. Likewise, also a time-indexed subset of relayed payments \(P_{r_n}\) is known by a node n.

When payments are routed over multiple channels, intermediate nodes can charge fees for providing the relaying service. These fees are split into a fixed amount \(f_n \in \mathbb {R}^{\geqslant 0}\) and a rate \(r_n \in \mathbb {R}^{\geqslant 0}\) of the payment. Both values are defined for each node \(n \in N\) and can be changed at any time. The total amount that a relaying node u must receive from its predecessor to transfer x to the payee or the next node is \(p_u = r_u * x + f_u\). If there are more intermediate nodes on a payment path, then this calculation has to be done for each of them, beginning at the last one. Importantly, the fees need to be known by the node prior to the execution of the transaction. Otherwise, it is not guaranteed that a payment arrives at the payee, since the fees may take a too large share of the overall payment.

An example with two relaying nodes is shown in Figure 1. In the example, in order for the payment amount \(p_3\) to arrive at node \(n_4\), the payer \(n_1\) has to transfer the amount \(p_1\) to the first intermediate node. \(n_2\) then retains the fee \(f_{n_2}=p_1 * \frac{r_2-1}{r_2} + \frac{f_2}{r_2}\) and forwards \(p_2 = p_1 - f_{n_2}\) to node \(n_3\). \(n_3\) also deducts its fee \(f_{n_3}\) and finishes the payment by transferring amount \(p_3 = p_2 - f_{n_3}\) to \(n_4\).

The purpose of a routing algorithm in a PCN is to find the subset \(R_{P_n} \subseteq R_P\) containing the routes for a payment known by node n. Ideally, the sets \(R_{P_n}\) and \(R_P\) for the same payment are equal, but in practice, this is unlikely due to the lack of information about the whole network by individual nodes. Based on discussions in the related work [21, 34, 47] and our own preliminary experiments, a routing algorithm for PCNs needs to fulfill the following functional and non-functional requirements:

As stated in Section 1, the usage of approaches from the field of WSN routing for PCNs is promising, since WSNs and PCNs have a number of commonalities. In the following, we further investigate these aspects.

However, there are also some important differences. For instance, WSNs rely on a shared medium, while PCNs rely on point-to-point connections. Second, WSNs are data-centric, which allows, e.g., spreading data within the whole network. This is also not desirable in PCNs, where payments should only be routed on certain channels. Alternatively, WSNs may have the goal to send data to a single data sink. In contrast, nodes in a PCN can become both senders and receivers of data (i.e., payments). Third, WSN routing algorithms divide the operation time into distinct phases, e.g., for route construction, maintenance, and usage. The route creation phase is then globally synchronized or even commonly executed. This is not possible for PCNs, since there is a lack of global synchronization between the nodes.

Because of these differences, it is not possible to directly apply WSN routing algorithms for PCNs. Hence, in the next section, we analyze existing WSN routing algorithms with regard to their applicability in PCNs.

Literally dozens of routing algorithms for WSNs have been proposed in recent years—for a concise overview, we refer to the surveys by Pantazis et al. [29], Mohamed et al. [28], and Al Aghbari et al. [4]. For our analysis, we applied these surveys as a foundation and furthermore scanned more recent approaches in the literature.

Overall, we evaluated 61 WSN routing protocols with regard to the requirements discussed in Section 3.2—here, we omit the requirement “cost efficiency,” since it does not play a role in WSN routing. Instead, the assessment of cost in terms of average routing fees is one focus in the evaluation (see Sections 5 and 6). Because of space constraints, it is not possible to list the 61 analyzed routing algorithms within this article. Instead, we refer the reader to the Supplemental Material for this article [23]. An overview of 16 algorithms discussed in the article at hand is given in Table 1.

During the analysis, we excluded algorithms because of the discussed requirements, starting with scalability and resource efficiency. A number of algorithms, e.g., DREAM [10] or LMR [22] apply routing tables that include all nodes of the network, which is not a suitable approach in large-scale PCNs. Therefore, these algorithms were excluded from the further analysis. Other approaches, e.g., ACQUIRE [40] may degenerate into flooding, while others, e.g., MERR [49] are based on a central control instance. Such algorithms are also not suitable for PCNs, since the routing may become too large, and there is no central control instance in PCNs, respectively.

A number of algorithms were excluded, since they are not satisfying the self-organization and flexibility requirement. For instance, SPastry [5] and others make use of a fixed network topology during runtime. Others, e.g., COUGAR [44] and DHAC [25], rely on a central base station to form clusters and are therefore also not suitable for PCNs.

Another requirement that leads to the exclusion of multiple WSN routing algorithms is the communication compatibility. For instance, LEACH-based [35] routing algorithms need a shared medium, which is not available in PCNs. Other algorithms like GRAB [45] and SAR [42] need a central sink and are therefore not suitable. Finally, location-based protocols cannot be applied in PCNs, since payment channels are location-independent. Therefore, algorithms like SELAR [24] or HGR [14] cannot be further regarded.

From the 61 analyzed algorithms, three were finally selected for further assessment and implementation in PCNs:

As can be seen, one particular goal of our analysis was to select algorithms that focus on different requirements and apply different conceptual approaches to routing. The intention of this is to be able to derive general recommendations on which types of WSN routing protocols are promising candidates for future research in PCN routing.

The Temporally Ordered Routing Algorithm (TORA) [31] is a protocol from the family of “link reversal” algorithms. This means that for each possible destination, TORA creates a graph based on the nodes and the communication channels in a WSN. The links in the graph are directed towards the destination following the shortest path. On certain events, e.g., a link failure, the directions of some links are reserved, which is the origin of the protocol family name. In general, all the routing information is exchanged locally in packets of constant size.

E-TORA [46] extends TORA by route and energy parameters. In theory, packets should use different routes in the network to improve the utilization of the remaining energy in battery-powered nodes and therefore, to prolong the network lifetime. This is achieved by adding the actual route to the data packets so that each node knows the exact paths to the destination. When a node forwards a packet, E-TORA finds the route with the maximum c, where \(c = \alpha \times \frac{E_{min}}{\overline{E}} + (1 - \alpha) \times \frac{h_{min}}{h}\), \(E_{min}\) is the minimal energy of a node on the route, \(\overline{E}\) is the average energy of all nodes on the route, h is the hop count, and \(h_{min}\) is the hop count of the shortest route. Instead of choosing the downlink-neighbor with the shortest path to the destination like TORA, the next node in the route with the maximum c is used as the next hop for the forwarded packet.

The implementation in this article follows mostly the original TORA implementation from the ns-2 simulator¹[7]. According to E-TORA, the collection of routes for each downstream link has been implemented. However, the metric c is changed to take the liquidity of payment channels into account instead of the remaining energy, which is the most important constraint in WSNs. The complete procedure that selects the next link of a route can be seen in Algorithm 1. Initially, if all links are undirected, a query (QRY) packet is broadcasted to locate the destination (line 2). If no downstream link exists, then the procedure ends without a result, because the destination cannot be found (line 5). Otherwise, the available routes that have been collected using update (UPD) packets are iterated to find the best one (lines 10ff). For each route, the metric in line 15 is calculated and compared to the value of the previous route. As described above, not only the length of the route is part of the metric (line 13) but also the liquidity in the channels (lines 11 and 12). Therefore, the identified route should have mostly balanced channels and as a consequence, the time a channel is kept open is increased. The importance of liquidity and route length can be parameterized (line 14).

When implementing E-TORA for usage in PCNs, we intended to directly use the found paths from E-TORA as payment channels in PCNs. However, preliminary tests have shown that the original paths are very quickly outdated, especially on nodes that are far away from the destination. This is due to the property of E-TORA that link failures or new links have only a local impact. The solution is to use these routes only for the decision which neighbor is the next hop, as it can be seen in line 17 of Algorithm 1.

In E-TORA, packets should use different routes in the network to improve the utilization of the remaining energy in WSN nodes and therefore, to prolong the network lifetime. This is achieved by adding the actual route to the sent packets, so that each node knows the exact path to the destination. However, this may cause a constraint with regard to the intended scalability of E-TORA, since the amount of data grows linearly to the lengths of the paths. Considering a very large PCN, the size of the packets may be difficult to handle for nodes with a limited bandwidth. We adapted E-TORA accordingly by introducing a Time-to-Live (TTL) parameter for the packets (line 2 of Algorithm 1).

The next algorithm that has been selected is M-DART [13]. The unique feature of M-DART and its predecessor DART [19] is the use of dynamic addresses based on the node’s position in the network. This means, if the node moves, i.e., it establishes a new link or removes one, its address will probably change. In DART, this is formalized as the Prefix Subgraph Constraint, which ensures that nodes in a connected subgraph share an address prefix. The addresses themselves are organized in a tree, where the leaves are the nodes and different levels form subtrees of the same prefix, as it is shown in Figure 2.

Based on the particular properties of the addressing scheme, routing a packet towards its destination is as simple as finding the longest shared prefix entry in the routing table to gather the address of the next hop (lines 4ff of Algorithm 2). For this, the routing table gets updated by periodic messages from neighbors and contains an entry for each level-k sibling, e.g., in case of node 000 the siblings are 001, 01X, and 1XX. M-DART extends the routing table of DART to store more than a single next hop for a sibling to offer multiple paths to the destination (line 7). Furthermore, the routing table includes the costs of a path, i.e., the minimum hop count, the network ID for validating the own address, and a route log to avoid loops.

Since the addresses of this routing protocol are subject to change, each node needs an identifier that remains constant. In our implementation, we choose the wallet address, because it complies with the requirements. To lookup the address for a given identifier, a DHT is used as proposed in Reference [19] (see line 1 of Algorithm 2). To store or retrieve an address, the belonging identifier is hashed to get the address of the anchor node, where the address-identifier pair is deposited.

The main challenge in implementing M-DART is not only its sophisticated design but also inaccuracies in the pseudo code of crucial procedures in DART [19]. Again, the ns-2 simulator [7] was consulted to serve as a basis for this implementation. Despite the comprised loop avoidance in M-DART, first tests have shown the presence of occasional loops. Since they can be traced back to outdated routing tables, we use a TTL parameter (line 3) and collect the visited nodes while recording routes.

The last of the candidate routing protocols for PCNs is TERP [1]. It is based on AODV but incorporates trust and energy parameters to avoid malicious nodes on routes and to reduce the overall power consumption. Like AODV, it is a reactive protocol and hence establishes routes on demand by broadcasting control packets. Also, the definition of these packets remains mostly unchanged against the original AODV. The established routes are then cached in a routing table.

There already exists an AODV-based algorithm for PCNs proposed in Reference [21] (see Section 2). This approach uses the liquidity and fee of a payment path to choose the best route. With TERP, the route selection is also trust-aware for defending against misbehaving nodes. Therefore, all nodes monitor the packets of neighbor nodes in their wireless radius and use the gathered information to estimate the trust in them. For instance, dropped packets that should have been forwarded result in a decreased trust.

Since our implementation has the requirement to work in PCNs, the monitoring of other nodes is slightly different than in WSNs. The underlying model exposes the success of various higher-level interactions with nodes to the routing algorithm that are summarized in the following:

The implementation uses counters for each neighbor node to keep track of the interactions and their success. Since a payment path is always constructed from the destination to the source, i.e., to be able to accumulate the overall fee, every node knows the potential next hop and the next but one hop of a route during construction. Hence, the trust in the next hop can be incorporated into the decision in a payment path. Like in the original TERP, trust is based on the direct trust in a node and the indirect trust in the same node of others. The calculation of the direct trust can be seen in Algorithm 3. Basically, its value is the proportion of successful interactions with the next node (line 4). If there have not been any interactions with this node, then a neutral value is returned (line 6).

Determining the indirect trust is outlined in Algorithm 4. At first, the direct trust of the next but one node in the next node is requested (line 1). If nothing is returned, then a neutral value is assumed (line 3). Then, the requested value is multiplied with the direct trust in the next but one node (line 4), which at the same time is the result for the indirect trust in the next node.

The final trust \(t_n = w_1 \times \text{directTrust}(n) + w_2 \times \text{indirectTrust}(n, n_a)\) in a node n is then determined by the use of direct and indirect trust values, whereas \(w_1\) and \(w_2\) are weights and \(n_a\) is the node after n on the path. The resulting trust value can then be classified using different levels, e.g., Trusted, \(Less trusted\), Indecisive, or Misbehaving.

Finally, the original composite routing function of TERP is modified to accept liquidity and fee parameters instead of energy cost. The metric shown in Equation (1), where \(w_{1-4}\) are weights used to determine the importance of the single parameters, n is the next hop, \(n_a\) is the next but one hop, \(l_{min}\) is the minimum liquidity on the path, \(f_{acc}\) (fixed) and \(r_{acc}\) (rate) are the accumulated fee, and c is the hop count, is used to find the path that minimizes its value and is then used for the payment:

Our evaluation is based on the following high-level objectives:

To provide deterministic results in different, repeatable scenarios, we opted for using a simulator instead of a real-world testbed for evaluating the implemented routing algorithms. Figure 3 provides an overview of the simulator, which is available as open source software.² In the following, we briefly introduce the core components of the simulator:

The simulator allows running simulation cycles, with one cycle representing a single payment routed over one or more channels. Depending on the number of channels on the path, the length of one cycle can vary, but it always contains one complete payment. Cycles are set to define for how many payments a particular simulation should run. Before the actual simulation cycles can start, it is necessary to initialize all nodes by executing “dummy” cycles. This so-called ramp-up phase makes sure that all nodes are able to set up internal data structures, most importantly routing tables. For more details about the simulator, we refer to https://github.com/dlob/pcn-simulation. The repository also contains the concrete templates and settings used in the single evaluation runs presented in the article at hand.

As pointed out above, nodes in a PCN may behave in different ways. The goal of the behavior model described in the following is to allow the modeling of different roles a particular user (and therefore node) may adopt. To describe the roles, we first define several characteristics a role may assume (Section 5.3.1). Notably, different roles may share characteristics, and some characteristics are parameterizable. The roles themselves are presented in Section 5.3.2.

Based on the defined roles, we are now able to define simulation scenarios. These scenarios combine a collection of roles and their proportional distribution among the nodes. For each scenario, we allow a network size of 30, 200, or 1,000 nodes, each with 500 simulation cycles. With each new cycle, a single payment is carried out, i.e., per evaluation run, 500 payments are covered. To measure the metrics presented in Section 5.5 without the influence of concurrent payments, payments are carried out sequentially, i.e., per cycle, one payment is started and finished. In the next cycle, another payment is covered. The mentioned network sizes have been chosen based on preliminary experiments, since they have shown to be well-suited to exemplify differences in the performance of the adapted routing algorithms. While the Lightning Network has approximately 16,400 nodes,³ we observed during preliminary experiments that the outcomes in terms of the assessed metrics (see Section 5.5) do not change significantly if we increase the number of nodes beyond 1,000. Partially, this can be traced back to the fact that the success rates for scenarios with 1,000 nodes are already not sufficient any longer (see Section 6).

Because the simulations as defined in the templates are deterministic, there is no need for a further variation of the cycle number. Preliminary experiments have shown that 100 cycles at most are consumed to stabilize the PCN with the largest number of nodes. Therefore, 500 cycles are considered to be a good trade-off between the time that is necessary for simulation execution and PCN stabilization.

The first scenario to be taken into account is the basic scenario, which is used for comparison with other scenarios. Therefore, it uses only a small set of standard roles. The most universal role without limiting characteristics, e.g., offline phases, and a larger impact on the routing algorithms’ performance is the heavy consumer. Additionally, we decided to use the hub role, because we consider hubs as an integral part of PCNs. Since at least one hub should be available in each generated template and the smallest template based on this scenario has 30 nodes (see above), the resulting proportions are ~97% of heavy consumers and ~3% hubs.

Based on the basic scenario, we define several derived scenarios to allow a comparison of the routing algorithm’s performance. These scenarios differ only in a single additional role from the basic scenario. Therefore, we replace one sixth of the heavy consumers, because preliminary experiments have shown this to be a good compromise between only a very little impact and the over-representation of the new role. These scenarios represent the edge cases of PCNs that are needed to reach our evaluation goals (see Section 5.1).

Faulty scenario: Since defects in software and an unreliable infrastructure can affect operations in a PCN, we introduce this scenario to examine the fault tolerance of the implemented routing algorithms. For this purpose, the faulty user role is added to the roles of the basic scenario. According to the replacement rule defined above, the proportions in this scenario are: ~81% heavy consumers, ~16% faulty users, and ~3% hubs.

Malicious scenario: Besides of faults that happen accidentally, there is the threat of attackers who want to interfere the proper operation of a PCN. Such behavior is implemented in the malicious user role that is part of this scenario. Altogether, the malicious scenario consists of ~81% heavy consumers, ~16% malicious users, and ~3% hubs.

Low-participation scenario: Another challenge for the routing algorithms are nodes in a PCN that are offline most of the time. To investigate the impact of this behavior on the network, the passive consumer role is incorporated in the low-participation scenario. This results in the following proportions of roles: ~81% heavy consumers, ~16% passive consumers, and ~3% hubs.

Hub scenario: In the previous scenarios, the properties of the network graph like average vertex degree or shortest path length are approximately the same. To add some more variance, the hub density is increased in this scenario. Because hubs are already part of all scenarios, we replace the hubs of the basic scenario with second-level hubs and add the normal hub role like the additional roles of the scenarios above. This gives us a role composition of ~81% heavy consumers, ~16% hubs, and ~3% second-level hubs.

As stated above, the faulty, malicious, low-participation, and hub scenarios provide edge cases, and therefore differ only in one particular role from the basic scenario. In contrast, the commercial scenario has been constructed to have a sophisticated, rather complex scenario with a number of roles and properties that could be reasonable for payment systems. Therefore, this scenario incorporates also the remaining roles described in Table 2, i.e., these roles not used in the other scenarios yet. We start by using the most universal role, the heavy consumer, for roundabout half of the nodes (48%) in the scenario, because this ensures that enough spendable capital is existing. A significant amount of users of a PCN is considered to be not always online. Therefore, 20% of passive consumers are used to represent this category of users. This leaves us with roundabout one third of the roles to be divided between the commercial roles like the subscription service with 10%, the trader with 12%, the hub role with 9%, and the second-level hub with 1%. Since the trader is a more universal role than the subscription service, its representation in the PCN is slightly higher. For this scenario, we left out the malicious and the faulty user roles, because the distinction between nodes belonging to these roles and normal nodes when analyzing real-world PCNs for future reevaluations is considered to be hard. This is because the certain characteristics that have been chosen for these roles are difficult to identify from an outer perspective, e.g., the causing node for a failed transaction cannot be determined without any doubt when using the faulty user role.

Using the templates for the discussed scenarios, the simulator initializes PCN topologies. For this, not only the roles of nodes are selected randomly (but following the distributions). In addition, the templates contain channels, which correspond to the character of the single nodes. For instance, hubs naturally have usually a large number of open channels while passive consumers tend to have only a small number of channels. Also, the templates predefine the payments to be carried out in one evaluation run. For instance, it is defined if a role should get more incoming than outgoing payments. Within one generated template, the settings are the same, leading to deterministic results for different evaluation runs applying the same template. The applied templates are available in our Git repository.

Finally, we define the metrics used to assess the quality of the routing protocols in our simulations. For this, we follow the metrics proposed by Roos et al. [39] and Yu et al. [47]:

All metrics are calculated until time (i.e., cycle) t, so that we are able to plot the progress of the single metrics over time.

For all investigated routing protocols, the success ratio is surely the most important metric. As it can be seen in Figure 4(a), the overall performance of E-TORA regarding this metric is rather low, particularly in comparison to the results of TERP in Figure 4(c). Figure 4(a) also shows that the performance rapidly decreases for larger network sizes. A possible reason for this is outdated information about payment paths. The state of a payment path can get stale at certain nodes when update messages are not traveling fast enough in the network or the TTL added in our implementation of E-TORA (see Section 4.1) prevents the notifications to be further transmitted. This affects the bigger scenarios more, since the configuration of the TTL is the same for all network sizes.

The performance of E-TORA looks somewhat better in terms of the average hop count metric. Regarding this aspect, E-TORA outperforms the other routing algorithms significantly as it can be seen in Figure 5(a). Although the diagram shows only the basic and the hub scenario, this can also be observed in the remaining scenarios [23]. Nevertheless, the good results come with no surprise, because a main property of E-TORA is the usage of the shortest path available in the network.

Another interesting observation can be made regarding the measurements of the average channel count. Typically, the usage of E-TORA as routing algorithm in larger simulations leads to a decreasing average channel count per node as a result of the low success ratio (see the basic scenario in Figures 4(a) and 5(b) as a representative example). One exception is the malicious scenario that is also shown in Figure 4(b). In comparison to the basic scenario, where the average channel count for E-TORA stays approximately the same, the values obtained from the metric using the malicious scenario are rising similar to the other routing algorithms. The explanation for this is the intended behavior of the malicious user role. Since channels are opened greedily and the closing of them is refused by this role, they stay open for the rest of the simulation. In conjunction with rejecting to pass through payments, the outcome is a low success ratio and an increasing average channel count per node for the malicious scenario in general.

The final core observation regarding E-TORA is its immense communication network utilization. As Figures 6(a) and 6(b) show, the amount of packets as well as their size increase in the course of the simulation. This is caused by the excessive route management that is necessary in the later cycles of a simulation to keep the payment paths up to date. Since the route maintaining process is an inherent part of E-TORA, our adapted implementation for PCNs does not change this behavior. Moreover, if the individual payment path would be used more frequently and only few paths are necessary throughout the whole network, E-TORA could perform very well. But since the payers and payees in a PCN are considered to be diverse and regular payments are of lesser importance, E-TORA is probably not very well-suited for use in PCNs.

Again, we begin the analysis of M-DART by examining the routing algorithm’s success ratio as can be seen in Figure 4(b). For most scenarios, M-DART shows slightly better results than E-TORA and has a significantly good performance in the hub scenario, as can be seen in Figure 7(a): M-DART exceeds the success ratio of the other routing algorithms especially with an increased amount of hubs in the network. In the hub scenario, M-DART seems to benefit from the resulting higher channel count per node, which in turn accelerates the traveling of routing messages in the network. Since M-DART is a pro-active protocol, the speed of the distribution of network changes significantly influences the ability to route payments correctly.

In contrast to the higher success ratio in the hub scenario, M-DART struggles in simulations of large scenarios, as can be seen in Figure 4(b). This diagram shows the basic scenario as a representative for all large scenarios where M-DART is not able to find a path for multi-hop payments at all. The small amount of successful payments that are visible in the figure are only based on direct channels between payers and payees. The reason for this weak success ratio is the strong presence of loops in the routing tables of the nodes. As it was the case with E-TORA, this is likely once again a manifestation of outdated routes, which may be explained by longer travel distances for routing messages.

Besides the very low success ratio in large simulations, M-DART performs very well with regard to the average fee metric. In nearly all scenarios, obviously except the large ones, the use of M-DART leads to a lower average fee for payment relaying. This is exemplarily shown in Figure 7(b) with the basic and hub scenarios. Since M-DART in contrast to E-TORA and TERP does not incorporate the fee in the route creation process, the reason for this behavior is not obvious. Instead, M-DART returns multiple possible routes to let the node choose the one that fits its goals best. In the implemented roles, this is mostly the cheapest path. Therefore, it is probable that the approach to not optimize routes in the forefront, like M-DART is using it, leads to the lower average fee.

Another observation from Figure 7(b) is the significant higher average fee in the hub scenario than in the basic scenario. This does not only affect M-DART but all algorithms and is also present for the hub scenarios of small and large size. Therefore, we assume that this behavior originates from the implementation of hubs and their variable fee calculation. Since the commercial scenario does not show an average fee on a comparable level although it has more hubs than the basic scenario, it is possibly also related to the particular combination of roles.

TERP is the only implemented routing algorithm that is able to achieve a reasonable success ratio in large scenarios. As Figure 4(c) shows, the value of this metric is actually declining in larger PCNs but TERP is still executing multi-hop payments in contrast to M-DART and E-TORA. In general, TERP outperforms the other two algorithms on average in all scenarios and network sizes. A possible reason for this is very likely the better adaptability of on-demand routing algorithms like TERP to the changing network.

Another good performance of TERP regarding the success ratio is shown in the faulty scenario. As it can be seen in Figure 8(a), the difference between the basic and the faulty scenario is minimal, especially in contrast to M-DART. Since TERP has a build-in trust estimation for the purpose of avoiding unreliable intermediate nodes, we can see that this functionality is working as intended. Nevertheless, the success ratio drops a bit that can be explained by payments that originate or end at faulty nodes or by an unfinished trust estimation, i.e., too few interactions with a faulty node exist.

To continue the evaluation of the success ratio of TERP, we change to the low-participation scenario. Since the passive consumer role is part of this scenario, a lower success ratio than in the basic scenario can be expected. Instead, the measurements of the metric remain on the level of the basic scenario as it can be seen in Figure 8(b). This is again a consequence of the on-demand route creation of TERP, because offline nodes are not reachable and hence not part of a payment path. Proactive routing algorithms like M-DART do not have the possibility to easily avoid offline nodes and therefore experience a serious decrease of the success ratio.

Completely different results for the success ratio of TERP are observed in the malicious scenario. Basically, TERP uses the same trust estimation as in the faulty scenario to detect uncooperative behavior. It can be seen in Figure 8(a) that the trust-based routing is not working as intended in the malicious scenario. Although the collection of data about uncooperative interactions is the same for both use cases, the results are very different. However, there are certain behavioral variations of the malicious user role if compared to the faulty user: The latter only drops some transactions, while the malicious user aims at executing no payments at all. This higher degree of “malfunctions” is obviously influencing the success ratio very negatively.

The last metric that is discussed regarding TERP is the average hop count. As it can be seen in Figure 7(a), the success ratio of TERP does not benefit from the additional channels, which originate from the higher hub density. However, the average hop count shown in Figure 5(a) of the hub scenario is lower as in the basic scenario, which is the result of the shorter average path length of the hub scenario. Nevertheless, for most scenarios and network sizes, the average hop count metric for TERP produces values that are more than twice as high as the values of M-DART or E-TORA. We trace back this behavior to the route weighting that is less focused on short paths than on a high liquidity and trust. Trivially, the longer payment paths also lead to a higher average fee as it is shown in Figure 7.

During the evaluation of the implemented routing algorithms, we were able to assess their actual suitability for use in PCNs. Therefore, we revisit the literature-based assessment of WSN protocols in Section 3.2 by incorporating the measurements collected in the simulations. An overview is provided in Table 3.

As we can see from the evaluation results, each routing algorithm achieves better results than the others in at least a single performance metric: E-TORA finds the shortest payment paths, M-DART ensures the lowest fee for payment relaying, and TERP reaches the highest success ratio on average. Nevertheless, the algorithms have different shortcomings like the network utilization of E-TORA, which decreases scalability, the problem of M-DART with routing-loops in large networks and limited flexibility, and the higher hop count and fees of TERP. This should be taken into account when using these algorithms (or just some of their design choices) as foundations for PCN routing.

Notably, the inclusion of trust information (as in TERP) seems to be very beneficial in PCNs, and therefore should be regarded in future work in the area. With regard to the decision whether proactive or reactive routing protocols are more promising, the reactive TERP has led to the best overall results in our evaluations. However, if channels are open for a long time, and there are few faulty or malicious nodes in a PCN, proactive routing protocols may lead to better results than shown in the work at hand. Therefore, it is for sure an interesting idea to investigate if routing protocols could be exchanged during runtime, based on the behavior of the single nodes, and the goals of the payers. This resembles the notion of transitions [6], i.e., to adapt communication mechanisms in networked systems at runtime, which is for sure a very interesting future research direction.

Despite these meaningful insights, our article has a number of limitations, which we want to discuss in the following paragraphs. To start with, we deliberately did not compare the WSN routing protocols to already existing PCN routing protocols like Spider or SilentWhisper (see Section 2). Therefore, we cannot make a statement if the implemented algorithms perform better or worse than PCN-specific protocols. This would for sure be an interesting idea for future work (see Section 7).

Also, whereas the different scenarios used in our evaluation are able to produce solid results based on our PCN model, we cannot create a truly representative average scenario yet because of the missing analyses of existing PCNs, and especially the behavior of the nodes in a PCN. Instead, we decided to cover a number of possible scenarios, which could also be easily adapted for future reevaluations. The implementations of the node roles in the simulator are so far limited to the possibilities described in our PCN model (see Section 3.1). Therefore, not all possible characteristics of a PCN user are represented in our roles but only the most important ones to reach our evaluation goals. Due to the flexible design of the presented simulator, roles can be easily added or adapted to refine the model for future evaluations.

As written before, our simulator provides the capabilities to apply different roles, different scenarios, and of course different routing algorithms. Accordingly, we will use it in the future to further investigate routing algorithms for PCNs, taking into account the abovementioned aspects.