In our class lectures, we covered virtual circuits and machine load, among other topics. Having a strong interest in real world application, I chose to follow this lead and examine some aspects of our national telecommunications infrastructure -- perhaps I could find out what algorithm is used to establish telephone connections, and whether this algorithm is comparable to what we covered in class. The time allotted for this project was not long enough to be able to obtain detailed information on how the telephone network actually functions, but I was able to pursue the subject at the engineering library. I found an interest in circuit switching, but the material available was limited.
Taub and Schilling provide a reasonable explanation of the phone system within the United States, and I will relate what I learned from their book.
If there were only one central switching exchange and N subscribers, then this setup would require N connections to the exchange and N(N-1)/2 switches to complete all possible connections of one subscriber to another. Suffice it to say that such a setup would be rather impractical. Putting aside the number of switches, there would be significant loss of signal over the long stretch of wire to the central exchange. To avoid this impractical situation, the system is set up in a hierarchical manner, with offices of varying class spread out across the nation, with local networks that are linked at higher classes.
Following is a listing of the roughly pyramidal hierarchy, and the number of offices at each level.
Class Office Approx. # in system
1 Regional Center 10
2 Sectional Center 50
3 Primary Center 150
4 Toll Center 600
5 End Office Subscriber 10,000

The way these offices form a network to allow connectivity begins with each subscriber being directly connected to an end office, with the connection named a "subscriber loop". Two people who are connected to the same end office need only that office to establish the circuit to communicate. In certain areas (e.g. high density), end offices may connect to each other. Each end office connects directly to a toll center, which in turn connects to a primary center, and so on, up the hierarchy. The actual setup is not as much of a concern to me as how a call is actually routed, and the information on this is vague.
I was under the impression that perhaps I would find that telephone switching attempts to minimize the maximum load on any given connection. However, that is not the case. Taub and Schilling provide an idea of how circuits are completed by presenting a caller A trying to reach person B in a separate city.
Let 5A be the caller's end office, and, similarly, 5B be the receiver's end office. If the end offices are directly connected, then an attempt to form the circuit will be attempted through the direct connection. Otherwise, the call signal will traverse up the trunk line from office 5A to its corresponding toll center, 4A. If a complete circuit is possible from here (either through a connection to 4B then 5B, or by direct connection to 5B), then a circuit will be made. Otherwise, we must again traverse the hierarchy and find a connection. This can go all the way to the top (through 1A and 1B), if, for example, the two callers are in opposite coasts of the U.S.
At times, although a low-level connection can be made, the channel may have reached its load limit, and so a connection through higher offices in the network are necessary. Thus, the system apparently utilizes a simple "shortest-path" algorithm for connections. As anticipated, no consideration is given to expected call duration at all in actually forming the circuit. If absolutely no circuits are possible given the load on all relevant offices within the hierarchy, then a busy signal is returned, although the recipient of the intended call is not using the phone at the time. This online method may work for phone calls, but it would, of course, not be a good method if the required/possible bandwidth were to vary.


Taub and Schilling present a bit on server load,, where the server is the hardware in the phone network used to complete a circuit. In a population of N telephone subscribers, it is very unlikely that all of them will be using the telephone simultaneously. The actual usage of the telephone is non-deterministic. However, it is predictable. It is not economically practical for telephone companies to ensure that there will always be enough switching gear to accommodate the demand -- there will be statistical outliers. For instance, maybe for a certain period on a holiday, demand may exceedthe available switches. Switching gear is expensive to purchase and maintain, so the telephone companies maintain less switching gear and rate themselves with a "grade of service".
The grade of service is the probability that the service can establish a requested (dialed) connection. Thus, if the grade of service is P.01, then there is a .01 chance that the call will be rejected.

Definitions of the following terms:

"Servers" = hardware of the switching center and the circuits, toll lines, etc...

"Load"= of course, the traffic which a switching facility must handle from t1 to t2.
= average number of servers that are in use in that time period.
The units for load are called "Erlang"s (named after Danish engineer A. K. Erlang)

An intuitive formula:
p = ¶ * h
p is the load in Erlangs.
¶ is the number of calls from t1 to t2. (ie. the calling rate).
h is the average duration of a call.


Ex:
If t1 to t2. is 25 minutes (i.e. 1500 secs.),
and 50 subscribers begin calling in that time frame
and the total combined duration of the calls is 5400 secs.

Then load is:
p = (50 calls/1500 sec) * (5400 sec / 50) = 3.6 Erlangs.
And average load per caller is .072 Erlangs.



Going back to the formula, p = ¶ * h.
If the number of servers are s, then the probability that all servers are busy (i.e. that the call is blocked) is:
(ps/s!)
B(s, p) = -----------
…sj=0(pj/j!)

This is called the Erlang B Congestion Formula.
A recursive relation for it is:
pB(s-1, p)
B(s, p) = ----------------------
s + pB(s-1, p)

As you would expect, if servers = 0, then B(0, p) = 1
==> Without servers, it's guaranteed that each call is blocked.

Using this formula, if p=14, and the desired grade of service is B=P.01, then 23 servers are needed.
If you want grade of service P.001, then 27 servers must be present.

The law of large numbers would inditate that a larger facility with larger load is more efficient than a smaller facility.


Here's a table to demonstrate that:
Average load, p ====> 10 Erlangs 19 Erlangs
Grade of service B(s, p) P.001 P.001
# of servers needed, s 21 100
Average # of servers idle 11 (52% idle) 25 (25% idle)