DESTINATION TAG ROUTING TECHNIQUES BASED ON A STATE MODEL FOR THE IADM NETWORK

A "state model" is proposed for solving the problem of routing and rer outing messages in the Inverse Augmented Data Manipulator (IADM) netwo rk. Using this model, necessary and sufficient conditions for the rero utability of messages are established, and then destination tag scheme s are derived. These schemes are simpler, more efficient, and require less complex hardware than previously proposed routing schemes. Two de stination tag schemes are proposed. For one of the schemes, rerouting is totally transparent to the sender of the message and any blocked li nk of a given type can be avoided. Compared with previous works that d eal with the same type of blockage, the time x space complexity is red uced from O(log N) to O(1). For the other scheme, rerouting is possibl e for any type of link blockage. A universal rerouting algorithm is co nstructed based on the second scheme, which finds a blockage-free path for any combination of multiple blockages if there exists such a path , and indicates absence of such a path if there exists none. In additi on, the state model is used to derive constructively a lower bound on the number of subgraphs which are isomorphic to the Indirect Binary n- Cube network in the IADM network. This knowledge can be used to charac terize properties of the IADM networks and for permutation routing in the IADM networks.