Network routing and control arrangement

Abstract

Abstract A system is disclosed for selecting and establishing connections through a two-stage concentrator network utilizing path selection circuitry adapted to minimize blocking. This circuitry operates to select a path through the second-stage switch which is the least congested (i.e., has the most idle output lines). More specifically, "congestion" information is generated from "outlet" information specifying the idle/busy status of the outlets or terminals of the second-stage switches. This congestion information is logically combined with link information, specifying the idle/busy status of link paths interconnecting the stages, to ascertain if a path is available through one of the least congested second-stage switches. If a path is available, an idle outlet is selected on a least-congested second-stage switch, and then a connection is completed to the selected idle outlet. FIELD OF THE INVENTION This invention pertains to selecting and establishing paths through connecting networks and, more specifically, to arrangements for controlling the establishment of paths through two-stage concentrator networks. BACKGROUND OF THE INVENTION AND PRIOR ART When a system ascertains that a connection must be established from a communication path through a network, it is desirable if the connection is completed over a path which tends to minimize the blocking potential for future connections. It is apparent that each time one connection is completed through the network, this increases the probability that future connections will be blocked. However, certain path selection and routing arrangements tend to minimize this blocking and thereby, tend to increase the capacity of a network. Conceptually, there are two distinct phases in the completion of a connection through a network. The first phase is known as a path hunt. In the path hunt phase, all accessible idle paths through the network are ascertained. In other words, all paths which could be utilized to complete a connection are ascertained. The second phase is known as routing and entails the selection of one of the available paths ascertained in the first phase. The connection is then established through the network over the one selected path. In prior art systems, several routing techniques have been utilized. One technique is known as "random-selection" routing and, in this technique, a selected path is chosen at random from all available usable paths. This technique is effective in that it tends to equalize the wear of equipment in the network. In another prior art routing technique, herein termed a "most-busy" technique, connections are completed through the most-congested switches or nodes which can handle the connection. For a discussion of this technique see, for example, page 1373 et seq. of the November, 1966, issue of Bell System Technical Journal. This technique is intuitively based upon the supposition that since the probability of completing a call through a highly congested switch is very low, if a path is now available through such a switch, the path should be utilized because for a succeeding call the probability of using this switch is also very low. Still another prior art routing technique is known as "sequential hunt" or "packing" and entails the selection of the first available usable route in a predetermined sequence of all possible routes. It is an object of this invention to optimally route and establish connections through a two-stage concentrator network in a manner to minimize blocking for future connections. SUMMARY OF THE INVENTION I have discovered that connections can be optimally established to minimize blocking in a two-stage concentrator network by utilizing the paths through the least congested second-stage switches. The least-congested switches are defined to be those with the greatest number of idle outlets or terminals. More specifically, in accordance with this one illustrative embodiment of my invention, each stage of the two-stage network comprises a plurality of switches which are interconnected by links. A link map is generated which specifies the idle links associated with each of the first-stage switches. A second outlet map is generated which specifies the idle outputs for each of the second-stage switches. A "congestion" map is also generated which indicates the number of idle outlets for each second-stage switch. When a service request is detected over a communication line terminated in the network, information is obtained specifying the idle-busy status of the links connected to the first-stage switch on which this line is terminated. This obtained information is then logically compared with congestion information retrieved from the congestion map to ascertain the least congested second-stage switch over which the connection cannot be established. More specifically, a logical comparison is instituted to ascertain if the connection can be established over the second-stage switches with N idle outlets, in which N denotes the number of outlets on each second-stage switch. If not, a second logical comparison is instituted to ascertain if the connection can be established over the second-stage switches with N-1 idle outlets. If necessary, further successive comparisons are instituted until finally a comparison is instituted to ascertain if the connection can be established over the second-stage switches with one idle outlet. Upon ascertaining that a "least congested" second-stage switch can be utilized, an idle outlet on that switch is then selected. Based upon information identifying the first-stage switch, the derived information specifying the selected least-congested second-stage switch and the derived information specifying the selected outlet on the selected second-stage switch, the network is controlled to physically establish the connection through the network. In accordance with a feature of my invention, connections are established through the least-congested second-stage switches of a two-stage concentrator to minimize blocking. In accordance with another aspect of my invention a congestion map is derived from a map specifying the idle outlet status of the second-stage switches. In accordance with another aspect of my invention a sequence of logical comparisons are instituted to identify the class of second-stage switches with the most idle outlets having idle usable links connected thereto.

Inventors

• 👤 Andrew Frederick Bulfer

Bibliographic Details