Now that we have learned about hierarchical routing, we are almost ready to discuss dynamic routing. Before we go from hierarchical routing to dynamic routing, we need to note and understand a few critical issues.
10.2.1 Limitation of Hierarchical Routing
The need for dynamic routing is better understood if we understand the limitations of hierar- chical routing. Recall that while hierarchical routing avoided the looping problem by clever use of nodes at different levels along with a set of rules, it also led to situations in which some trunkgroups could not be used for routing even though capacity was available.
Consider Figure 10.5, where switches 1 and 4 are at a lower level and switches 2 and 3 are at a higher level. We can see from the figure that a call originating in switch 1 destined for switch 4 can use the HU trunkgroup 1-4 or overflow the call to routes 1-3-4, or 1-2-4 or finally to 1-2-3-4. However, a call from switch 2 to switch 3 can only use the final trunkgroup 2-3; it cannot use a path such as 2-1-3 or 2-4-3, although at the time of the arrival of the call there might be plenty of trunks available on links 2-1, 1-3, 2-4, and 4-3. Thus, you can see the inefficiency in how hierarchical routing works.
F I G U R E 10.5 Limitation due to hierarchical routing.
10.2.2 Historical Perspective
In the 1970s, the idea of being able to have some flexibility in routing that can use unused capacity, rather than the limitation imposed by hierarchical routing, was explored. One im- portant issue that needed to be addressed was the looping problem—that is, it could not be done within the framework of the hierarchical routing since a major reason for using hierar- chy was to avoid the looping problem. In the 1970s, some important developments took place in parallel: the first was the ability to use stored program control (SPC) in a switch, and the second was the development of common channel interoffice signaling (CCIS). SPC provided the software functionality for switching control. CCIS provided the ability to exchange con- trol information such as call setup and tear-down through out-of-band signaling instead of using in-trunk signaling for such functions, which was becoming noticeably slower when a call needed to go over multiple trunkgroups in serial to its destination; this out-of-band com- munication was a data communication service, meaning that information was exchanged as data packet services. Through evolution, CCIS, which used to be referred to as CCIS6, became CCS and eventually SS7; see Chapter 12 for further details.
In addition, there was another important observation, especially in the continental United States. Due to different time zones in the country, there were times when certain trunkgroups were idle or had very little utilization, but again, due to hierarchical routing, these trunk- groups could not be used. An example involves calls between New York and Atlanta, which are located in the Eastern time zone, at 8:00 AM. If the trunkgroup between New York and Atlanta is fully occupied at that time, a newly arrived call between these two cities could be alternately routed via Los Angeles, located in the Pacific time zone, which is 3 hours behind the Eastern time zone. It is then 5:00 AM in Los Angeles and it is less likely that there will be many calls between New York and Los Angeles or between Atlanta and Los Angeles at that time. This means the new call can conceivably use New York–Los Angeles and Los Angeles–
Atlanta trunkgroups to route this call. While this is an extreme example, it suggests that at least the set of routes a call between two switches can attempt can possibly be different de- pending on the time of the day, that is, the routing can be time-dependent rather than having the same or a fixed order at all times of the day. In essence, we can start to see that some form of dynamic routing that is at least time-dependent can be of benefit to the network in terms of carrying more calls. Actually, the potential benefit of dynamic routing is often credited to Nakagome and Mori [519], who first discussed the benefits of flexible routing.
As you can see, in the above illustration, all the routes are of a maximum of two links (trunkgroups). We want to clarify that these two links are only in the core of the network. The
actual call dialed by a user arrives at an end office from which the call is forwarded to the ingress switch in the core network. Similarly, from the egress switch, the call goes to the end office at the other end before reaching the actual receiving user. Thus, the maximum two-links part is addressed only between the ingress and the egress switch in the core network. Obvi- ously, more than two links in this part can be possible. However, there are three important drivers that led to all dynamic routing methods to limit calls to a maximum of two links:
• An issue was how to handle the looping problem. It is easy to see that the looping problem can be easily handled with a maximum of two links for a call: a call can be going directly from the ingress switch to the egress switch on a direct link; if this link is busy, the call can try another route going from the ingress switch to an intermediate switch. The intermedi- ate switch on receiving the call knows that the call needs to be sent directly to the egress switch, not another intermediate switch, due to the limit on the number of links. This then automatically avoids any looping problem.
• A second issue was the complexity of software implementation of the dynamic routing function. Note that the concept of dynamic routing arose toward the end of the 1970s and early 1980s when software for telephone switches was still in its nascent stage, not to mention the high cost of implementing a complex function. The goal was to keep the complexity down, for example, if the looping problem could be addressed easily without introducing software complexity.
• There is minimal incremental gain from allowing more than two links. Common sense indicates that if more than two links are allowed, a network will certainly have more paths to the destination, and thus would have the ability to complete more calls. However, a telephone network is required to maintain an acceptable grade-of-service (GoS); in the United States, this was mandated by the Federal Communication Commission (FCC). An acceptable level of GoS was to maintain average call blocking at 1% or lower; an additional discussion of call blocking is presented later in Chapter 11. What we need to understand is that if a network is provisioned with a bandwidth to meet 1% call blocking GoS in the presence of dynamic routing where a call is limited to a maximum of two links, how much incremental gain can we gain if we were to have dynamic routing with more than two links? It was reported in [30] that this gain was not significant, i.e., the blocking would go down from 1% to about 0.96%.
Now, from the first two items, we can see that the software complexity can be minimized if a route is limited to a maximum of two-link paths. From the third item, when considered along with the software complexity issue, we can see that the gain in reduction in blocking can come at a very heavy price in terms of increased software complexity. Rather, if keeping GoS low is an important goal, it can be achieved by other means, for example, adding more capacity to the network. At the same time, it is easy to recognize that if we can provide many alternate paths between two switches, we have the opportunity to reduce call blocking. In a network with a maximum of two links for a path, the simplest way to achieve this is to make the topology of the network fully connected or nearly fully connected. For example, in a fully connected network withNswitches, there areN−2two-link paths in addition to the direct link path.
10.2.3 Call Control and Crankback
Hierarchical routing uses a progressive call control (PCC) mechanism. This means that the call control is forwarded from one switch to another until it reaches its destination unless the call cannot find any outgoing trunk at an intermediate trunk; in this case, the call is lost. In other words, the control of the call is not returned to the originating switch to try another possible path.
Suppose we could return the control of a call from an intermediate switch to the originat- ing switch. This would mean that the network is providing originating call control (OCC); the functionality of returning a call to the originating switch and trying another route is called crankback. With the advent of the dynamic call routing, the question of whether the network should provide PCC or OCC and whether it should provide crankback also arises.
Figure 10.6 illustrates how crankback works and its relation to OCC and PCC. Consider a call arriving at switch 1 destined for switch 2. It can try the direct link path 1-2. Suppose there is no bandwidth available on link 1-2 when the call arrives. The call will then attempt to use the next route in the routing table 1-3-2. If link 1-3 has no available capacity, the call will attempt the next route in the routing table 1-4-2; this overflow attempt is, however, not a crankback. So what is a crankback? Consider a slightly different situation. Suppose when the call attempted the second route 1-3-2, it found bandwidth on the first link 1-3 and thus the control of the call is forwarded to node 3; however, on arriving at node 3 it was discov- ered that there is no bandwidth available on link 3-2 for this call. There are two possibilities:
either send the control of the call back to the originating switch 1 and let the originating switch decide what to do next (for example, try another route such as 1-4-2), or drop the call.
The control of the call can be sent back to the originating switch 1 if the network has OCC, the process of reverting back to switch 1 and trying another route is called crankback. If the network does not have OCC, it must act as PCC. Thus, drop the call means that the call on arriving at node 3 is lost due to nonavailability of capacity on link 3-2; this occurs due to PCC, the call control cannot be returned to switch 1. As you will see later, some dynamic routing schemes provide OCC while others do not.
F I G U R E 10.6 Illustration of crankback.
10.2.4 Trunk Reservation
Trunk reservation, also known as state protection, refers to logical reservation of a part of a capacity on a link for its own direct traffic. Note that trunk reservation does not mean phys- ical reservation of a trunk. In this sense, this is a misnomer, and state protection is a better name. We have decided to retain the term trunk reservation because of its historical use and the prevalence of the use of this term in a large body of literature over the years.
Trunk reservation refers to a threshold on a trunkgroup; if a trunkgroup is not filled with calls before this threshold is reached, a call between other origin-destination pairs can still use a trunk from this trunkgroup. Consider trunkgroup connecting switching nodesiand j with capacity cij, which is given in a number of circuits. Suppose the trunk reservation parameter is given byrij, also given in number of circuits. Ifrij=0, then no trunk is reserved.
However, if rij=cij, trunkgroup i-j does not allow any alternate routing; certainly, in real networks this condition is never used. Typically,rijis close to zero; it should not be too low or too high. A rule of thumb is thatrij≈√2cij; later, in Section 11.8, we will illustrate the impact on performance for different values of trunk reservation.
Another interpretation of trunk reservation is that a call that connects the ends of trunk- group i-j is given access to all capacity cij, while a call for another origin-destination pair that is using linki-jcan have access to effective capacity,cij−rij. You may wonder why we need to do this. While dynamic routing provides flexibility to use multilink paths for routing, under certain loads it may not be desirable to route calls on multilink paths for the benefit of the network. Consider a path made up of two links; it can route a call for the end nodes of this path, or, from the point of view of the network, each link can be used to carry a call for the end nodes of each link. Thus, a network carrying two calls, one call each on direct link paths instead of one call carrying on the two-link path made up of the same two direct links, has more call-carrying capacity. To illustrate this, consider a three-node network where links between each node have one unit of capacity each. We number the nodes as 1, 2, and 3.
Here, the maximum call carrying capacity is three—one each for each pair of nodes on the corresponding direct link, that is, 1-2, 1-3, and 2-3. However, if we allow a pair of nodes to use the alternate path, say for pair 1:2 we allow a call to take the route 1-3-2, then the network would have only two call-carrying capacity—one on the direct path for pair 1:2, another on the alternate path 1-3-2, and none for other pairs.
It so happens that in the absence of trunk reservation, dynamic routing can exhibit bista- bility in certain load conditions (refer to Section 11.8). That is, a network can have different blocking levels for the same offered load, sometimes staying in one for a certain amount of time and then moving to another due to fluctuation in load. This is also referred to as metasta- bility (or bistability). By using trunk reservation, this metastable behavior can be minimized and often avoided. A formal definition of offered load will be presented later in Chapter 11;
furthermore, in Section 11.8.4, we will discuss the implication of no trunk reservation and metastable behavior.
10.2.5 Where Does Dynamic Routing Fit with Hierarchical Routing?
When a hierarchical routing architecture already exists, the question of where to fit in dy- namic routing arises. When dynamic routing is introduced as the routing scheme within an
IXC’s network, the switching level of switches in the dynamic routing network can be thought of as if it is at the primary switching center level. In other words, toll switches and end-office switches are considered to be in a level below the switch level of dynamic routing switches.
This is illustrated in Figure 10.7.
It may be noted that both an end-office switch or a toll switch may be connected by a trunkgroup to a switch in the dynamic routing network. Consider end-office switch 9, which is connected to the dynamic routing core via toll switch 8. However, end-office switches 6 and 7 are directly connected to the dynamic routing core. Furthermore, we can now see that a call from one end office to another end office can traverse at least three trunkgroups (for example, 6-1, then 1-3, and finally 3-7), or it can possibly be five trunkgroups where at most two trunkgroups are in the dynamic routing core (for example, 9-8-5-4-3-7).
10.2.6 Mixing of OCC and PCC
It is possible to mix OCC and PCC from the perspective of an end office to another end office.
The edge networks, where a call starts and ends, have PCC while the dynamic routing core has OCC. Consider again Figure 10.7. A call originating in end-office switch 9 and destined for switch 7 uses PCC to forward the call to switch 8, which forwards it to switch 5. Then switch 5, being the originating node in the dynamic routing core, may hold the control of the call and try alternate routes within the dynamic routing network until the path is established to switch 3, the destination node within the dynamic routing core for this call. Once the call is established within the dynamic routing core to switch 3, the call control is forwarded from switch 5 to switch 3 so that progressive call control can be used for completing the call to end-office switch 7.
10.2.7 Recap
We now summarize a few key points about dynamic routing. All dynamic routing schemes for the telephone networks allow at most two links for a call. Often, the network is fully-
F I G U R E 10.7 Dynamic call routing in conjunction with hierarchical routing.
interconnected, or nearly fully-interconnected. Also, all schemes include trunk reservation.
They all differ in the following areas:
• Progressive or originating call control, and crankback.
• Time-dependent, or adaptive.
• Off-line computation, or near on-line computation.
• Routing calculation.
• Link information used and how it is used.