It seems like a good idea that every node have enough information to compute routes on its own. That means that a relatively accurate available credit for each direction of account should be broadcast soon after any balance or credit limit change. Available credit limit changes could be broken up into deceivingly-sized and -timed increments to make it difficult to reconstruct any transactions from them. There is no need for a block chain to validate this information just for routing purposes -- each address can sign its own balance change messages to authenticate them. Any peer can then generate one or more decent candidate routes for its transaction and make attempts to use them without launching on a big distributed fishing expedition for available credit.
This could be made quite scalable I think: Every peer doesn't need to know about the available credit on every account in the whole network. A peer could just listen to the broadcasts and pick out the accounts it considers useful to know about (nearby accounts and others it thinks it might use for payments) for caching and rebroadcast. If it needs to learn about an account it doesn't know, it can broadcast a request for it. If it also broadcasts the amount it wishes to send to that account, it might event receive back a custom-made path. The incentive for fulfilling such request could be just that you get to decide where someone else's transaction goes, which might be favourable to you.
For a more well-defined and scalable concept of the scope of available credit messages, see Building Cells By Block Chain.
Also, the payer chooses a candidate path for the transaction and sends it out when it initiates the transaction, but if that path does not have enough available credit for some reason, the intermediary at the blockage should be able to try another route, which may very well be more successful, since it is closer to the recipient, and likely have more up-to-date information on available credit in that region of the network. Of course, intermediaries could just choose different routes based on their preference, which I think is fine, as long as those routes ultimately meet the payer's approval.
It would probably be useful for the payer to be able to include some parameters, such as the minimum amount that must arrive at the target node.
Every server can build a representation of the credit network from two types of available credit messages:
credit_offer - max. net obligations that will be accepted from another node going forward
credit_accept - max. net obligations that will be emitted to another node going forward
Both types contain the following data:
(Many of these from the same source could be packaged and signed together for efficiency.)
A credit_offer from node A (source) to node B (partner) and a credit_accept from node B (source) about node A (partner) are combined to create a credit connection that allows obligations to flow from node B to node A. The max. obligations that will flow is the smaller of the two message amounts.
A node's incoming and outgoing credit connections define exchanges that node advertises, and the rates those exchanges will occur at. For example, if a node has an incoming connection with a relative value of 0.6, and an outgoing connection with a relative value of 1.5, it will emit 1.5 units on the outgoing connection for every 0.6 units it receives on the incoming connection.
This design gives a single node no flexibility to advertise that it won't perform an exchange between one of its incoming connections and one of its outgoing connections. Therefore if a person wishes to not perform exchanges between all their connections, they must have multiple nodes.
Available credit and exchange rates are not binding, just advisory.
Nodes might choose to advertise more available credit or better exchange rates than they actually offer, in an attempt to attract more transaction traffic and profit from advantageous exchanges. Advertising more available credit than exists would just waste everyone's time, because a transaction attempting to use the unavailable credit wouldn't go through, and so the deception wouldn't be profitable. Advertising deceptively good exchange rates also shouldn't be very profitable if payers have the ability to specify the minimum amount that must reach the recipient -- payers would just compute how much should reach the recipient at advertised rates, and if an intermediary was lying, the transaction won't go through, and again the liar wouldn't profit.
The one way a deceptive intermediary might profit here is from fees for simply reserving credit for a transaction. An intermediary could falsely advertise an attractive route, accept transaction promises that arrive with fees attached for credit reservation, and then release those promises, since it never had any intention of completing the transaction. Predecessor nodes on the path wouldn't be able to distinguish this from the case where insufficient credit was available further up the path.