One of the issues I am considering as part of my PhD is how to encourage ISPs and other ASes to share routing information despite privacy concerns, worry about loss of autonomy and economic incentives not to share this with other ASes.
The benefit of ASes sharing this information would be the ability to compute routing outcomes centrally leading to faster convergence compared to having each domain do it's own computation with partial knowledge and more efficient routers because computation could be offloaded to a "routing service".
However, a possible approach that allows computation to take place without revealing the inputs is described in A New Approach to Interdomain Routing Based on Secure Multi-Party Computation, Gupta et. al, 2012 published at HOTNETS 2012.
This is based on applying secure multi-party computation (SMPC) to interdomain routing. SPMC algorithms are based upon the intuition in Shamir's paper How to Share a Secret from 1979 and work on homomorphic encryption.
Their solution is partially centralised, in that k compute nodes are used to perform the computation together. It still more centralised than the current model leading to the benefits of improved convergence and offloading of work from routers. To provide a level of security, these servers would be owned by different providers and we assume that they will not collude to reveal any secrets entrusted to them.
Each AS splits their routing policy is split into k shares and send each share to the group of k compute nodes. A SPMC algorithm is used to compute the BGP-routing outcome across the shares received from the each AS. The result of this algorithm is only a partial outcome representing a share of the outcome (a route to a destination). Each compute node returns this partial outcome to each AS and the AS combines the k shares received to reveal the final result.
This scheme provides our privacy guarantees because no one node knows enough to reconstruct the routing policy nor the outputs of the computation. The scheme is also resistant to a degree of collusion, privacy is maintained as as long as fewer than k/2 nodes decide to pool their results.
Routing computation is simplified to make implementing the scheme feasible by assuming only the use of next-hop policies and computation is done on a per-domain basis rather than a prefix basis. A routing policy consists of two components: a ranking of all possible routes to a destination and a specification of which route to a destination will be exported to which peer. Network topology is known to all parties and denoted as [n] = {1...n} set of domains. Each domain u has two inputs: (1) ranking of its neighbors; and (2) for every two neighbor i and j, the willingness to export routes that have i as next-hop to j.
The scheme was implemented using the SEPIA Java SPMC library and the authors reported it takes 0.13 seconds compute the route to destination for a single domain with 19 neighbours and 10 iterations (the number of iterations is 2D+1 where D is the depth of the customer-provider hierarchy, see the definition in Gao and Rexford's paper). This experiment was carried out on a single compute node (a PC 2,7GHz quad core machine).
Is this a workable solution? No but it is a proof-of-concept. The code was not optimised and a full performance analysis was not done. Furthermore, the measurement was for the computation of only one route to destination and a full implementation would calculate many for each AS. This is obviously another scalability problem but the authors believe that this could be addressed if each compute node performs these calculation in parallel. This is feasible since there is no dependencies between computation but its practicality was not explored here.
Evaluation. This scheme provides good privacy guarantees and an implementation is described.
There are several open problems:
a) How scalable is this approach? Investigate its scalability with respect to neighbours, depth of hierarchy and number of computations required for a full BGP routing table. Also what is the effect on end-to-end performance and reliability of the Internet?
b) How do we hide network information such as who is the neighbour of a given AS? It is assumed that the inter domain network topology is known, that is every AS is willing to reveal its neighbours. The authors suggest that because this assumption may not hold, they intend to investigate also hiding network information using the SPMC approach could be explored. It doesn't appear to date that they did do this so this remains an open problem.
c) Can this scheme be generalised to prefix-based and QoS based routing? This would allow traffic engineering without revealing sensitive information.
d) Can this scheme be extended to address BGP instability due to failure?
