On the Addressing Problem of Loop Switching

Recently, J. R. Pierce 1 proposed a data communication system concept whereby subscribers are placed on interconnected "loops". A message originating in one loop and destined for a recipient in another loop must find its way through the network of interconnections. Such a system is potentially efficient for data communication because it exploits the one-way nature of many such transmissions by eliminating the need to set up an entire line between two parties in the conventional manner. The realization of this potential efficiency depends in part on the existence of an efficient routing scheme. Such a scheme is discussed by Graham and Pollak in Ref. 2. Briefly, they assigned to each loop a ternary address; a message destined for a certain loop is tagged with the address of its destination, and upon entering a loop, a computation 1445 1446 T H E BELL SYSTEM TECHNICAL JOURNAL, SEPTEMBER 1972 involving that loop address and the message destination address yields the distance of the message from its destination. The message then moves in such a way as to decrease this distance. In particular, it is assumed that there are n loops and each address is a sequence of N (fixed) O's, l ' s and el's; let H be the n X N matrix the ith row H{ of which is the address of the ith loop. The addresses are chosen in such a way that if D,, is the distance between the ith and jth loop (by Z),, is meant the fewest number of loops which it is necessary to cross to to get from the tth to the jth), then N