Congestion and Price Signals

DSR is aggressively Agoric in nature. Congestion happens when demand for some link exceeds its bandwidth, or load exceeds some capacity at a node such as buffering or CPU power for routing. This may happen on short notice. Assuming that guides take tolls into account, it may still occur that congestion begins during the useful lifetime of a path provided by the guide. Here are some proposals to cope with this: (just one for now)

When you have a large hunk of data to send, or anticipate streaming data at a high rate for an extended time, ask the guide for several paths between the source and the destination and send all paths to both ends. AT&T would have called these ‘diverse routes’.

Some classic window-style flow control and error control protocols (X.25 for instance) were adept at exploiting several physical links for a single stream, joining the streams at the destination while preserving the original order to reform the original stream. See multi-flow and error control. With part of the data flowing along each path the code for that protocol can easily observe the extracted toll on each path and quickly optimize their respective flow rates. This adjustment can be done in the span of a couple of network round trips and the error control naturally compensates for lost packets due to the congestion that presumably drove up the price on some of the paths.

This logic is at the end-points. New paths may be acquired from guides during transmission. The guides may indeed pay for congestion and price information that customers can provide at lower cost than the guide’s own testing.

This protocol has the additional social benefit of offloading the overloaded facility very quickly. Neither Tymnet nor Internet has such a scheme, I think. Bit-Torrent does something like this in that data congestion from one supplier decreases the total amount of data that you get from that supplier, without losing any data. Data source location is adjusted according to available bandwidth.

It is not clear how the guide is to choose a set of paths. It could deprecate nodes or links on the paths already offered. It could return a net, perhaps a partial order, instead of a path set. (A partial order is a set of ordered pairs. For every finite partial order there is a unique minimal subset whose transitive closure is the partial order. Oops.

traceroute?

Another supplementary plan is a global protocol where a special tracer packet elicits from selected nodes a report. The replies should optionally include: Some of these fields might be omitted as tracer packet option. Some might be encrypted to requester’s public key included in tracer packet, and signed by node’s private key. Another tracer packet option is to include node’s public key in reply. Yet another tracer packet bit-set is which nodes replies are requested from.

When tracer packets traverse a link with currency change, there is some confusion. For now I would propose that replies would state the exchange rate which would be two numbers which are nearly reciprocals of each other.

This code makes invitations concrete. The notion there is that invitations are not lost and sent only when buffers become available. It was suggested that invitations might carry price information for diagnosing congestion. If some signal, like invitations or acknowledgment, were sent upstream with price information on a low frequency basis, even absent new buffers, then a class of planning becomes possible. I suppose we could call it a ‘price signal’, not unlike the economics usage. That scheme seems simpler than some I had been imagining.

The planner needs to know where the congestion is. A price signal could include prices of other priorities, prices at other nodes, even special deals, I suppose. The question is what to propose as an initial standard.

These ideas should be compared with these. There is a common problem of such signals flowing along a circuit without queuing behind extant traffic.