BRIEF DESCRIPTION OF THE DRAWING
The foregoing as well as other objects, features, and advantages of my invention will be more apparent from a description of the drawing in which:
FIG. 1 is a block diagram illustrating the environment in which the concentrator network is utilized and controlled;
FIG. 2 illustrates in greater detail the various switches and links in the concentrator network illustrated in FIG. 1;
FIG. 3 illustrates three network maps which are utilized in my path selection and routing system;
FIG. 4 schematically illustrates map generation circuitry and circuitry which implements my path selection system; and
FIG. 5 illustrates the anticipated improved blocking performance utilizing my "least-busy" path selection arrangement.
DESCRIPTION
FIG. 1 illustrates the environment in which the two-stage concentrator network CN is utilized and controlled.
More specifically, the concentrator network is an additional switching network which is added to a telephone system known as TSPS No. 1, which system is utilized to provide centralized automated operator service primarily on long-distance telephone calls. TSPS No. 1 is comprehensively described in the December 1970, issue of the Bell System Technical Journal. More specifically, the communication bus system illustrated in FIG. 1 corresponds to FIG. 1 on page 2563 of the above-mentioned BSTJ.
To elaborate, processor SPC in FIG. 1 comprises duplicated processing units for operating in accordance with a stored program to service telephone calls. Processor SPC indirectly receives dialed digits and controls trunk position network TPN to establish connections from telephone trunks associated with calling stations to operator positions which are not illustrated. Translator CBT in FIG. 1 provides logic for decoding orders from the SPC received over the CBT bus and for providing them to network controller TPN1 and network controller CN1 for controlling the establishment of connections in the network associated with each of these controllers. The circuitry of the network controllers may correspond to that shown on page 2576 of the above-mentioned BSTJ. These are well-known controllers including pulsers for controlling the operation of ferreed switches to establish network connections.
Concentrator network CN is a two-stage network which has been added to the 1-out-of-N bus of the TSPS No. 1 System. Controller CN1 controls the establishment of connections in the concentrator network in accordance with commands received from processor SPC and translator CBT.
FIG. 2 illustrates in greater detail the topology of concentrator network CN. Network CN comprises 32 first-stage switches designated S1-01 to S1-32. The second digit which is a 1 indicates that these are first-stage switches and the two digits following the hyphen identify the particular first-stage switch. Thus designation Si-o2 identifies first-stage switch number two. Network CN also comprises eight second-stage switches designated S2-1 to S2-8. Network CN is utilized to establish connection from a communication path terminated on a first-stage switch to an idle outlet on a second-stage switch. This is known as a "point-to-group" connection.
Each of the stages comprises well-known individual reed switches comprised of individual contacts known as ferreeds. Each of the first-stage switches includes 128 (i.e., 16 .times. 8) ferreeds for selectively establishing connections from any of sixteen input lines such as P1-P16 to any of 8 interstage links terminated thereon such as L01-1 to L01-8. Each second-stage switch comprises 256 (i.e., 32 .times. 8) ferreeds for selectively establishing connections from any of 32 links to any of 8 output leads. For example, switch S2-1 can be controlled to establish connections from any of 32 links L01-1, L02-1...L32-1 to any of the 8 outputs D1-1 to D1-8. It is seen that a single link is provided between each of the first-stage switches S1- and each of the second-stage switches S2-. In other embodiments of my invention, it is anticipated that more than one link may interconnect each of the first- and second-stage switches.
FIG. 5 illustrates the improved blocking performance which is obtained in network CN utilizing my "least-busy" path selection as compared with the priorly utilized "most-busy" and random path selections. These graphs were prepared based upon monte carlo simulation techniques.
Turning now to FIG. 3, three maps are illustrated. Map A indicates the idle or busy status of each of the links associated with each of the first-stage switches. In this map, a 1 indicates an idle link and an 0 indicates a busy link. For example, for first-stage switch S1-01, links L01-1, L01-2, and L01-8 are busy and links L01-3 and L01-7 are idle.
Map B indicates the idle or busy status of the outlets associated with the second-stage switches. For example, outlet D8-1 associated with second-stage switch S2-8 is busy, whereas each of the other labeled outlets of this switch are idle. Maps A and B are well-known network map tables and similar maps are utilized in the TSPS processor for selecting paths and for controlling the establishment of connections in network TPN as described on page 2572 et seq. of the above-mentioned BSTJ. Similar network maps are also described in S. S. Karp Pat. No. 3,613,089, issued Oct. 12, 1971, and K. S. Dunlap et al. U.S. Pat. No. 3,281,539, issued Oct. 25, 1966. Maps A and B are updated in the course of normal call processing to reflect the actual busy-idle status of the hardware elements specified in these maps.
In accordance with this one preferred embodiment of my invention, a third map is generated to indicate the congestion level or the number of idle outlets of the second-stage switches. This congestion map is shown as map C in FIG. 3. The generation of this map will be described in detail hereinafter; however, this map can be easily generated by hardware or software by counting the number of 1s in each row of map B. The count for each row indicates the number of idle outlets in the switch associated with the row. For example, we will assume that switch S2-1 as indicated in map B has six idle outlets (i.e., six 1s). Thus, in map C, a 1 is inserted in the column labeled S2-1 in the row which indicates switches with 6 outlets idle. Thus each vertical column only has a single one inserted therein.
Reading map C, it is apparent that none of the second-stage switches have 8 outlets idle, but switches S2-3 and S2-8 each have 7 outlets idle. In accordance with the principles of my invention, if possible, either switch S2-3 or S2-8 will be utilized to establish the next connection. If, however, these two switches cannot be utilized, then those switches with 6 idle outlets will be considered. Sequentially each of the other second-stage switches is considered in its order of congestion, such that those switches with one idle outlet are considered last.
To summarize the above, a congestion map is generated and iteratively and least congested switches are considered for establishing a desired connection. Thus, as a first choice, the second-stage switches with eight outlets idle are utilized. As a second choice those second-stage switches with seven idle outlets are utilized and so on, reading down the rows of map C until finally those second-stage switches with only one idle outlet are considered.
FIG. 4 illustrates one circuit which generates map C from map B and also illustrates one circuit utilized to implement my least-busy routing arrangement. The information generated by the circuitry of FIG. 4 specifies a second-stage switch and outlet in that switch, which are to be utilized for establishing the desired connection. This information is conveyed to processor SPC which generates the appropriate control information. This control information is conveyed to controller CN1 in FIG. 1 for controlling concentrator network CN to establish the desired connection. Controller CN1 operates in a manner substantially identical to controller TPN1 whose operation is described in the above-mentioned BSTJ.
Initially all registers and counters shown in FIG. 4 contain Os. Each time a connection in network CN is established or broken-down, processor SPC enables clock C1. The clock provides a periodic HIGH signal in the form of a square wave on lead C1-A to register AR1 which is also a 3-bit binary counter. In response to the first HIGH signal over lead C1-A, register AR1 counts and therefore now contains the binary address 001 which is conveyed to memory MRY. In a well-known manner the addressed word, which is the first row of information in map B, is inserted into register MOR1. Thus, register MOR1 now contains the following binary information: 001...11. Clock C1 also provides periodic output signals over lead C1-B at much greater frequency than over lead C1-A. These signals cause the information in register MOR1 to be consecutively shifted out and applied to gate 41. The signals received over lead C1-B also energize gate 41 to strobe the information in the form of binary is into eight-stage shift register counter SRC. Each time a binary 1 is output from register MOR1, a binary 1 is inserted in register SRC. However when a 0 is output from register MOR1, a 1 is not inserted in register SRC, and the contents of register SRC are not shifted. After lead C1-B has gone HIGH eight times, each of the 8 bits in register MOR1 have been inserted, and register SRC now contains a number of is equal to the number of 1s in the original word in register MOR1.
Turning to FIG. 3, and assuming that each of the bit positions not shown in map B in the row labeled S2-1 are 1s (in other words assuming row S2-1 contains six 1-s and two 0s) then six 1s would have been shifted into register SRC. Register SRC would then provide HIGH outputs on the first six output leads to the rightmost one detector circuit RMD. Thus leads SRC1-SRC6 would be HIGH and leads SRC7 and SRC8 would be LOW. Circuit RMD comprises wellknown logic for detecting the rightmost 1 in a word and for providing a HIGH output on the single output lead associated with the detected rightmost 1. Thus, circuit RMD provides a HIGH output over lead 6ID. This lead indicates that the particular second-stage switch associated with the word retrived from map B has 6 idle outputs. The output leads 1ID-8ID respectively correspond to the 1-to-8 possible idle outlets for a given switch. Here lead 6ID associated with eight-by-eight crosspoint array CAY is energized.
To generate map C, shown in FIG. 3, the second-stage switch identity must also be known so that a 1 can be inserted in the proper column of the map. Binary-to-1-out-of-8 detector 8DR converts the binary address 001 in register AR1 to a 1-out-of-8 code and provides a HIGH signal only on lead 8DR1. The HIGH signal on lead 8DR1 energizes a vertical selection lead of crosspoint array CAY. Only the memory element having its vertical and horizontal selection leads concurrently energized will store a 1. Thus, since leads 8DR1 and 6ID are energized a 1 will be inserted in the first column of the third row of crosspoint array CAY. Turning again to FIG. 3, the inserted 1 is the 1 in the column designated S2-1 and the row designated "6 outlets idle."
This same procedure is repeated for each of the other rows of map B so that is are inserted in the appropriate locations of map C.
More specifically, clock C1 again enables lead C1-A and counter AR1 again increments its count so that the register now contains the binary word 010. Now the second row, associated with switch S2-2, is read out of map B into register MOR1. As described previously, the bits of the word in register MOR1 are consecutively shifted out and counted by register SRC. Detector RMD then provides the appropriate HIGH output which indicates the number of idle outputs associated with switch S2-2. This HIGH signal energizes the proper horizontal selector lead of array CAY. Decoder 8DR decodes the binary address 010 in register AR1 and provides a HIGH signal on output lead 8DR2 which enables the proper vertical selection lead of array CAY. Thus, for example, a 1 is inserted in the memory element at the intersection of the second column and third row of array CAY.
The preceding has described how the circuitry of FIG. 4 devices map C from map B. After each of the eight rows of map B has been addressed, output, and processed to generate map C, processor SPC then disables clock Cl and resets register AR1 to all 0s.
When a scanner (not shown) associated with processor SPC detects a service request on one of the communication lines terminated on a first-stage switch, the scanner indicates to the processor the identity of the calling line and the identity of the first-stage switch on which that line is terminated. Assume, for example, that a call is detected over communication line or path P1 of switch SL-01 in FIG. 2. At this time, processor SPC enables clock C2 and, concurrently, loads register AR3 with a binary word 0001 which indicates that the calling line is terminated on switch S1-01. IF switch S1-08 had been indicated, the binary word 0100 (i.e., binary 8) would have been loaded into register AR3.
Responsive to the loading of binary word 0001 into register AR3, the first row of map A is retrieved from memory MRY in a well-known fashion. The word 001...10 (FIG. 3, map A, fist row) is output into memory output register MOR3. As mentioned above, clock C2 was concurrently enabled and this clock provides a HIGH input to address register AR2 which is also a binary counter. Thus, register AR2 now contains the binary word 001, and, accodingly, the first row of map C in array CAY is output into register MOR2. Register MOR2 now contains the binary word 000...00 (FIG. 3, map C, first row). The binary words in register MOR3 and MOR2 are now compared on a bit-by-bit basis to ascertain if an idle link is available to one of the least-congested second-stage switches. More specifically, the first bit in each of the words in register MOR3 and MOR2 are ANDed together by gate G1, and each of the other bits in each register is respectively ANDed by gates G2-G8. Thus a logical product is formed between the words 001...10 and 000...00, which logical product is 000...00. Thus gates G1-G8 each provides LOW output indicating that no second-stage switches with eight idle outlets can be utilized.
Clock C2 now provides another HIGH signal to register AR2 which increments its present count to 010. Now, the second row of map C is output into register MOR2, and the logical product is formed between binary words 001...10 (register MOR2) and 001...01 (register MOR3). Gate G3 provides a HIGH output to indicate that the desired connection can be completed through switch S2-3. Gates G1-G8 respectively correspond to switches S2-1 to S2-8. Leftmost one detector logic LDL is a well-known circuit for detecting the leftmost 1 in a word input thereto, and for generating an output word with a 1 only in the bit position corresponding to the leftmost 1. Thus logic LDL provides LOW outputs on all its output leads except lead LDL3. IF more than one second-stage switch, with the same number of idle outlets had been available, then two or more is would have been input into logic LDL. By choosing the leftmost 1, logic LDL operates to choose among available second-stage switches having the same congestion. Of course, a random selection or other selection of second-stage switches having the same congestion could also be utilized.
The HIGH output of gate G3 also causes OR gate G10 to generate a HIGH output signal to stop clock C2. Thus, the other rows of map C are not consecutively output.
As described above, the rows of map C are output in order of increasing congestion and compared with the appropriate row output from map B only until a match occurs which indicates that a path is available through a second-stage switch.
Now that logic LDL has provided a HIGH output over lead LDL3, indicating the connection that can be established via switch S2-3, an idle outlet on this switch must now be chosen. More specifically, one-out-of-8-to-binary logic 1BL translates the word output from logic LDL into the binary output word 011, which output word is applied to register AR1 over cable C11. Thus the binary word 011 is inserted in register AR1, and, accordingly, the third row of map B is output into register MOR1. Thus the binary word 111...01 is now stored in register MOR1. Since the 1s indicate idle outlets, this call could be completed by establishing a connection over either outlets D3-1; D3-2; D3-3; or D3-8, but could not be completed over outlet D3-7 which is busy. Leftmost-one detector LMO detects the leftmost 1 and provides an output word having a 1 corresponding to the leftmost detected 1. Thus detector LMO provides the following output word 100...00 to processor SPC indicating that outlet D.sub.- -1 has been selected. The word 010...00 would have indicated that outlet D.sub.- -2 had been selected.
Since processor SPC already knows the identity of the calling line (p1), and the corresponding first-stage switch S1-01) and was informed of the selected second-stage switch (S2-3) by logic 1BL, and was also informed of a selected idle outlet on that switch (D3-1) by detector LMO, processor SPC then generates the appropriate order to control controller CN1 to establish the desired connection through network CN.
Illustrative Software Embodiment
As mentioned previously, maps A, B, and C can be updated under program control, and moreover, the selection of a path through a least congested second-stage switch can also be performed by a software arrangement. The following subroutines are written in PL/I, a well-known programming language which is, for example, extensively described in A Guide to PL/I, by Pollack and Sterling and published in 1969 by Holt, Rinehart and Winston, Inc. The operation of each subroutine is self-explanatory in view of its preamble which identifies all variables used therein, and the function performed thereby.
UPDATE-MAPS: PROCEDURE(S1NUMBER,S2NUMBER,DNUMBER,ACTION):
Subroutine to update the three maps corresponding to a two stage concentrator consisting of thirty-two 16.times.8 first-stage switches and eight 32.times.8 second-stage switches. the subroutine is entered with the first-stage switch number (s1number), the second-stage switch number (s2number), the outlet number (dnumber), and a variable (action) indicating whether a connection has been made (action=`1`b) or broken (action=`0`b). the subroutine updates the first-stage map (mapa) the second-stage map (mapb), and the congestion map (mapc).
declare (sinumber,s2number,dnumber) binary fixed;
declare (mapa(32),mapb(8),mapc(8)) external bit (8);
declare action bit(1);
declare r(8) initial (`1`b,`01`b,`001`b,`0001`b,
`00001`b,`000001`b,`0000001`b,
`00000001`b) bit(8);
if action
then mapa(s1number)=mapa(s1number) .epsilon. -r(s2number);
else mapa(s1number)=mapa(s1number) .vertline. r(s2number);
if action
then mapb(s2number)=mapb(s2number) .epsilon. -r(dnumber);
else mapb(s2number)=mapb(s2number) .vertline. r(dnumber);
n=9; do i=1 to 8;
If mapb(s2number) .epsilon. r(i) then n=n-1;
end;
if n<9 then mapc(n) = mapc(n) .vertline. r(s2number):
if action
then mapc(n-1) = mapc(n-1) .epsilon. -r(s2number);
else mapc(n+1) = mapc(n+1) .epsilon. -r(s2number);
return: end update-maps;
hunt-and-route: procedure(s1number,s2number,dnumber);
subroutine to path hunt (ascertain all accessible idle paths) and route (select one of these paths) connections through a two-stage concentrator consisting of thirty-two 16.times.8 first-stage switches and eight 32.times.8 second-stage switches. the subroutine is entered with the first-stage switch number (s1number) and returns with the second-stage switch number (s2number) and the outlet number (dnumber) of the path selected. if no path is available, the subroutine returns with s2number=0.
declare (sinumber,s2number,dnumber) binary fixed:
declare (mapa(32),mapb(8),mapc(8)) external bit(8);
declare (x,y) bit(8);
x = mapa (s1 number); do i=1 to 8;
y = x .epsilon. mapc(i);
if y then do;
s2number = index(y,`1`b);
dnumber = index(mapb(s2number),`1`b);
return
end
end s2number = 0; return: end hunt-and-route;
the results of these subroutines provide path hunting and routing information which are utilized by processor SPC in a well-known manner to generate commands to network controllers to establish a connection to the selected outlet (DNUMBER) of the selected second stage switch (S2NUMBER).
SUMMARY
In summary, a routing system is disclosed for establishing connections through the least-congested second-stage switches of a concentrator to minimize call blocking. A congestion map is generated and the information in this congestion map is compared with other information indicating the idle accessible links. After a successful comparison, a least-congested second-stage switch which can be utilized is thereby chosen, and then an idle outlet on the selected switch is selected. With this information the processor generates the appropriate orders to establish the desired connection.