The Call Routing in Telephone Networks

Nowadays we take it for granted that someone in England can make a phone call to Australia, or that someone in India can read web pages that are on a computer in Canada. We live in a society in which almost every home has its own telephone line which is connected to a local exchange in the nearest village or town, from there to a main exchange in the nearest city, and from there to any other city in any country in the world. In this way, a person is able to dial a friend in another country just as easily as if they were in the same street. BT’s Worldwide Network Management CentreIn order that these large and complicated networks can work properly, mathematics and computer simulation have to be used to understand the networks. The aim is to find out how large networks can be designed and controlled to provide reliable communications systems and to use resources efficiently. The reliable and efficient operation of networks is of vital commercial importance to both users and telephone companies, and even modest percentage improvements can correspond to large revenue gains. BT’s Worldwide Network Management Centre

A large network is affected by many factors which are often hard to predict. There can be busy and quiet periods through the day. If a television program has a phone-in vote, there can be a sudden overload at one point in the network. If a digger cuts through a major telephone wire while repairing the road, there can be a sudden and unexpected failure. Mathematicians have developed ingenious ways of routing calls which can cope with these unpredictable events. These routing schemes work by searching out the spare capacity in the network so as to route calls away from parts of the network that are broken or full and into parts that are loaded.The A good routing strategy doesn’t only need to be able to find the spare capacity in the network. In order to work well in real networks, it needs to be simple, so that thousands of calls a second can be routed instantly. It also needs to be decentralised; a central controller would be much too slow and could go disastrously wrong if it had a power failure, or got cut off from the rest of the network. Mathematicians have recently been able to show the surprising fact that these different goals can all be achieved simultaneously. Even simple, decentralised schemes can find the spare capacity as efficiently as more complicated schemes.

Trunk reservation

When we try and route calls through a whole network instead of just out of a single village, many surprising things can go wrong. For example, if a call from Aybury to Beeford finds that the direct link between them is full, it is tempting to route it via some other city, say Ceeville, if possible. This is a good thing to do if the network is lightly loaded, but if it is heavily loaded then most calls have to use an indirect route instead of a direct one, thus using two links instead of one. Because each call is using twice as many links as it needs, the network can then only carry half as many calls in total!Mathematicians have devised a scheme known as trunk reservation to avoid this problem. We reserve some capacity on each link for directly routed calls. So if a link is becoming full, no indirect calls are accepted on it. The amount of reserved capacity only needs to be very small – maybe space for half a dozen calls on a link that could carry several hundred. This is a very simple scheme, and easy to implement in real networks.The effect of trunk reservation is that we sometimes refuse to carry calls that we could fit in. It seems like this would be a bad thing to do. But in fact, by throwing away a few harmful calls, we can carry far more calls overall.

Sticky routing

Sticky routing is a principle that has been much studied in the last 10 years. Suppose that a call is to be connected between city A and city B but that all the direct links are currently busy. The routing strategy needs to find a longer path to get from A to B which can carry the call.To do this, city A remembers an intermediate city, C say, to use for such overflow calls and attempts to set up the connection from city A to city B via city C. If this connection is accepted then that two-link route is used for this call and is remembered for future calls between cities A and B.If the two-link connection A-C-B is rejected because it is currently too busy then this call is refused connection (the person calling hears a engaged tone) and the intermediate city is reset at random to another city, D say. The next overflow call between cities A and B will then attempt to use the new path A-D-B.The sticky principle sticks to the same two-link route as long as it is not too congested, and then switches to a new path when congestion is seen. In this way, a sticky routing strategy searches for and uses any available spare capacity that exists in the network.