CALL ROUTING IN TELEPHONE NETWORKS
INTRODUCTION
ROUTING is a process of finding a path from a source to every destination in the network. A routing protocol sets up a routing table in routers and switch controllers. A node makes a local choice depending on global topology
Telephone calls must be routed across a network of multiple exchanges, potentially owned by different telephone carriers. The exchanges are all connected using trunks. Each exchange has many "neighbours", some of which are also owned by the same telephone operator, and some of which are owned by different operators. When neighbouring exchanges are owned by different operators, they are known as interconnect points.
This means that there is really only one virtual network in the world that enables any phone to call any other phone. This virtual network comprises many interconnected operators, each with their own exchange network. Every operator can then route calls directly to their own customers, or pass them on to another operator if the call is not for one of their customers.
Call Routing
When a call is received by an exchange, there are two treatments that may be applied: • Either the destination terminal is directly connected to that exchange, in which case the call is placed down that connection and the destination terminal rings. • Or the call must be placed to one of the neighboring exchanges through a connecting trunk for onward routing.
Each exchange in the chain uses pre-computed routing tables to determine which connected exchange the onward call should be routed to. There may be several alternative routes to any given destination, and the exchange can select dynamically between these in the event of link failure or congestion.
The routing tables are generated centrally based on the known topology of the network, the numbering plan, and analysis of traffic data. These are then downloaded to each exchange in the telephone operators network. Because of the hierarchical nature of the numbering plan, and its geographical basis, most calls can be routed based only on their prefix using these routing tables.

Routing In Telephone Networks
Telephone network topology • 3-level hierarchy, with a fully-connected core • AT&T: 135 core switches with nearly 5 million circuits • LECs may connect to multiple cores
Routing algorithm • If endpoints are within same CO, directly connect • If call is between COs in same LEC, use one-hop path between COs • Otherwise send call to one of the cores • Only major decision is at toll switch • one-hop or two-hop path to the destination toll switch • (why don’t we need longer paths?) • Essence of problem
Features of telephone network routing • Stable load • can predict pairwise load throughout the day • can choose optimal routes in advance • Extremely reliable switches • downtime is less than a few minutes per year • can assume that a chosen route is available • can’t do this in the Internet • Single organization controls entire core • can collect global statistics and implement global changes • Very highly connected network • Connections require resources (but all need the same)
The cost of simplicity • Simplicity of routing a historical necessity • But requires • reliability in every component • logically fully-connected core • Can we build an alternative that has same features as the telephone network, but is cheaper because it uses more sophisticated routing? • Yes: that is one of the motivations for ATM • But 80% of the cost is in the local loop • not affected by changes in core routing • Moreover, many of the software systems assume topology • too expensive to change them
Dynamic nonhierarchical routing (DNHR) • Simplest core routing protocol • accept call if one-hop path is available, else drop • DNHR • divides day into around 10-periods • in each period, each toll switch is assigned a primary one-hop path and a list of alternatives • can overflow to alternative if needed • drop only if all alternate paths are busy • crankback • Problems • does not work well if actual traffic differs from prediction
Metastability
• Burst of activity can cause network to enter metastable state • high blocking probability even with a low load • Removed by trunk reservation • prevents spilled traffic from taking over direct path
Trunk status map routing (TSMR) • DNHR measures traffic once a week • TSMR updates measurements once an hour or so • only if it changes “significantly” • List of alternative paths is more up to date
Real-time network routing (RTNR) • No centralized control • Each toll switch maintains a list of lightly loaded links • Intersection of source and destination lists gives set of lightly loaded paths • Example • At A, list is C, D, E => links AC, AD, AE lightly loaded • At B, list is D, F, G => links BD, BF, BG lightly loaded • A asks B for its list • Intersection = D => AD and BD lightly loaded => ADB lightly loaded => it is a good alternative path • Very effective in practice: only about a couple of calls blocked in core out of about 250 million calls attempted every day