# Telecommunications Network - Topology

This section covers questions such as:

• Where to place Nodes/Packet switching exchanges ?
• Where to place trunk lines ?
• Topologies and access methods used in LANs

Theory

• Topological Optimisation
• Graph Theory

Topological optimisation

Possible stages to designing a mesh network:

• Placing of nodes
• Routing assignment
• Capacity assignment

Some possible initial configuration strategies:

• Connections to N neighbours in order of least cost.
• Connections to N neighbours in order of greatest communication.
• Fully connected. Then remove links one at a time until required connectivity reached.

After these initial configurations the network may be modified to optimise for:

• Minimum cost
• Minimum hop count

etc.

Also traffic and routing considerations need to be taken into account.

Large networks

Larger networks are usually too complex to be designed as a pure mesh, therefore they are usually designed as a 'backbone' or 'layered' network.

Graph Theory

There is normally a resilience requirement for a network. That it should be able to survive one (or possibly N) link failures and still to be able to connect calls between any nodes.

There are two measures that can be used in this context:

Connectivity - Minimum number of Disjoint paths between any 2 nodes.

ie a 'connectivity' of N means that the network can withstand (N-1) failures.

if N=1 cannot withstand any failures

if N=2 can withstand 1 failure, etc.

For N=2 minimum config is called a 'hammingtonian cycle' ie a ring.

Minimum Degree - Minimum number of links connected to any node.

Degree N is necessary but not sufficient for connectivity N - use Kleitman to check.

Kleitman Connectivity test

For a test of N connectivity:

+----------+ |

|

| +--------+------------+------------------------+

| | choose any node and determine if there are N |

| | disjoint paths to all other nodes. |

| +---------------------+-------------+----------+

| yes no

|

| stop - network does not

| | have a connectivity of N

| |

| +---------------------+------------------------+

| | remove the node from the network |

| | set N= N-1 |

| +---------------------+------------------------+

| |

| +---------------------+------------------------+

| | is N > 0 ? |

| +---------------------+---+--------------------+

+---------------yes----+ +--no - stop

1K7 61.1.1.1.1.1.1.16.................................#

Addressing within a packet switching network

The Destination (and optionally the source) of a packet switched call are identified by an address consisting of 12 decimal digits, digits 1 to 4 are allocated by CCITT to identify the country and the network within that country.

This X.25 address, which is the packet switching equivalent of a telephone number, is sometimes known as an NUA (Network User Address).

In addition there is an optional 13th and 14th digit that is passed through the network transparently and can be used by the customers equipment to identify the system or task required, for example the digits could be used to specify whether the user wishes to connect to the companies mailbox or the companies database.

The 84 CCITT standard also specifies an address extension facility field which allows an OSI Network Service Access Point (NSAP) address which may be up to 40 decimal digits.

By 1984 agreements were reached between international standards bodies, ISO and CCITT, about an addressing scheme. This scheme relies on the concept of the network service access point (NSAP), which is the interface address between the network layer and the Transport layer of the OSI model. In addition, some progress was made towards establishing an international registration authority to control and administer the allocation of NSAP addresses, in a similar manner to the way in which CCITT administers data network identification codes (DNICs) to public networks.

Existing numbering plans such as X.121,F.69,E163, etc., as defined by CCITT for public networks, are considered inadequate for OSI addressing. They exclude private networks and LANs that do not attach to public networks and terminals on a private network, which can have more than one address assigned to them if that private network is attached to one or more public networks.

Numbering Plan Objectives

Numbering Plan Objectives

The numbering plans must be sufficiently flexible for efficient Network Design and facilitate expansion of the network without NUA changes.

In addition, each Network Termination Point must have a unique identity.

NUAs

NUA's are required:

a) To identify customers and Hybrid Networks directly connected to the Network.

b) To route calls within the network and to other networks.

c) To bill Customers and Hybrid Networks where appropriate.

PSTN validation and Billable NUAs

a) Network User Identifiers (NUI) are used to validate access via the PSDN for security, and for billing. The NUI is mapped to a billable NUA.

CCITT X.121

The International numbering plan for public data networks is defined by the CCITT X.121 recommendation.

The CCITT limit the length of this address to 14 decimal digits:

Data Network

Network Terminal

Code +-PNIC--------------+ +---+

+--DNIC-----+ +-------------NTN-------------------+

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

| 2 | 3 | 4 | 2 | 1 | 9 | 2 | 0 | 1 | 0 | 0 | 5 | 1 | 5 |

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

+-DCC---+ +-----------------NN--------------------+

Data National

Country network Number

Code digit

DCC

The first 3 digits define the Data Country Code, which identifies the country. The first digit identifies the zone as follows:

0 - (escape code) digits that follow form part of E.164 numbering

plan, for interworking with ISDN (digital interworking).

1 - Public mobile satellite systems

2 - Europe

3 - North America

4 - Asia

5 - Pacific

6 - Africa

7 - South America

8 - (escape code) digits that follow form part of F.69 numbering

plan, for international Telex numbers

9 - (escape code) digits that follow form part of E.164 numbering

plan, for interworking with the PSTN (analogue interworking).

The assignment of the following 2 digits of the DCC are administered by the CCITT. Assignments by the Director of the CCITT of data country codes (DCC) will be published in the operational Bulletin of the International Telecommunication Union. The codes are listed in X.121 annex D.

For the UK X.121 (1988) shows:

234 United Kingdom of Great Britain and Northern Ireland

235 United Kingdom of Great Britain and Northern Ireland

236 United Kingdom

237 United Kingdom

Network Digit

The 4th digit identifies upto 10 public data networks within the country. The assignment is made nationally and the CCITT Secretariat is notified, they will be published in the Operational Bulletin of the ITU. For the UK this digit is assigned by Oftel.

The coding of the NTN depends on the Technology used. See following sections of this document.

PNIC

If a single DNIC is assigned to a group of Public or Private Data Networks, then these networks can be identified by a PNIC (Private data network identification code). See X.121 annex B for details of the coding. PNICs are administered nationally.

Digits 13 and 14 are known as the subaddress. These digits are not used by the network, these are passed transparently to the destination DTE for it to use for its own routing purposes.

Billable NUAs

The communication requirements of many projects now include the use of TCP/IP protocols and there is a growing demand for full support across the national data networks.

## Routing Strategies

Routing Algorithms for mesh networks

Deterministic Routing

This is a fixed policy unaffected by changing conditions. This may be implemented by having a routing table in each node on the network. In order to cope with link failures, the table may have backup routes in case of failure. This system may also require a hop count limit to avoid infinite loops.

examples

* Routing table - with backup routes in case of failure

requires hop count limit to avoid infinite loops

* Random routing

* Flooding - Advantage, requires no knowledge of network topology

Shortest path algorithms

This approach is simple to implement and provides the minimum distance. However, it does not account for network traffic or overloads on a link or a node. Subject of research in graph theory. Dijkstras algorithm provides the shortest path from a network node to every other node.

Minimum delay Algorithms

Reliability in deterministic routing

A reliable network should provide alternate routes for message transmission in order to handle such conditions as link or node failure

flooding technique

Here a message arriving in a node is transmitted to all neighbouring nodes or to a group of selected neighbouring nodes, the network is flooding with several copies of messages. Duplicate copies are discarded at the destination node. This technique is simple to implement, and the message almost always reaches the destination node, however it is extravagant in use of network resources.

Disjoint Deterministic Routes

For reliability and to maximise backup capability alternative routes between two nodes should be arranged so that no link or node is shared by any two routes.

Random Routing

Random routing procedures determine routing to the next node based on a probability distribution over the set of neighbouring nodes. For example, one random routing policy sends the message on any one of the links with equal probability.

Each node periodically estimates the minimum expected delay route to every destination node and enters the corresponding outgoing link address in a table. The destination node and its most desirable link address are stored in a routing table. When a packet arrives in a node, it is sent on the link corresponding to its destination node entry in the routing table. Every node transmits to each of its neighbouring nodes an estimate of minimum delay for every destination node. The delay of each node to itself is set to zero. The delay vector is stored as entries in the delay table for the link on which it arrived.

For a large number of nodes, network routing table sizes grow and require large amounts of storage.

Network nodes can be divided into groups or clusters of nodes. Then, the routing table size in a node can be reduced by providing less Information about nodes in other clusters.

In which each node makes routing decisions based on purely local Information.

In which the nodes exchange Information and the routing decisions are based on a blend of local and shared Information.

In which nodes report local Information to a routing centre, which in turn issues routing instructions to the individual nodes.

Adaptive routing, because of its requirement for adjustment to network conditions, is difficult to manage from a central point. Parameters such as message queue lengths and expected delays at each node have to be collected in the central node. The inherent delay in receiving and disseminating this Information can result in addressing traffic conditions. However a centralised scheme is feasible and desirable in some situations.

1K7 61.1.1.1.1.1.1.16of Floyd. The supervisor simply needs to pick the optimal path from one source node to a given destination node and not all optimal paths from every node. This leads to an optimised version of the algorithm that is executed in about 12 milliseconds by the supervisor for any circuit.

Floyds Algorithm

1. Let Ni (i=1,2, ... K) be the K nodes in the network.

2. Let Ns be the starting node (source)

and Nt be the ending node (sink)

3. Let Cij be the cost of the line between nodes Ni and Nj. This cost is a function of the bandwidth and load of the line. Cij= (a very large number) under any of the following conditions.

a. node Ni, node Nj, or link (Ni,Nj) is down.

b. link (Ni,Nj) does not exist.

c. Node Ni or Nj is out of pass-through capacity.

| i = s,t | /

| j = s,t | /

d. Link (Ni,Nj) is out of channels.

4. Let Lj (j=1,2 ... K) stand for the label assigned to the nodes Nj (j=1,K). The label is of the form Lj = {p(j),d(j)}. At the end of the iterative procedure, if node Nj is in the optimal path, p(j) represents the next node in the optimal path and d(j) represents the optimal cost from node Nj to the destination node Nt. Initially set

Lj = {*,} j= t /

and for the destination node Nt set

Lt = {*,0}

where * represents an undefined quantity.

5. Let 'list' stand for a list of nodes that can contain anywhere from 0 to K nodes, where K is the total number of nodes in the network. Initialise the list to contain only Nt, the destination node.

6. Let F* stand for the cost of an optimal path from Ns to Nt that is known at any stage in the iterative procedure. At the end of the iterative procedure, if a path is successfully established, F* contains the true optimal cost. Initially set F* = .

7. Nodes Ni and Nj are called neighbours if there is a direct link between Ni and Nj.

Floyds Algorithm - the Iterative Procedure

Step 1 If the list is empty, go to Step 4. Otherwise, retrieve the first node from the list and delete the node from the list. Let Ni be the retrieved node whose label is

Li = {p(i),d(i)}

Comments: During the first iteration the retrieved node is Nt whose label is {*,0}.

Step 2 Examine each neighbour Nj of Ni.

If d(i)+Cij < d(j)

and if d(i) + Cij < F*:

a. Set d(i) = d(i) + Cij

b. Set Lj = {Ni,d(j)}

c. Add Nj to the list, if it is not already a member.

d. If j=s, set F* = d(j).

Comments Examine each neighbour to see if its cost of reaching the destination node can be improved by going through the retrieved node. Examine further to see if such an improved cost is less than the known cost of an optimal solution. If so, reset its cost and label and add it to the list for further consideration. If, in addition, the neighbour is the origination node, set the known cost of an optimal path to the new optimal cost. (Note that the second 'if' condition in this step is an important variation and optimisation of conventional path selection methods.)

Step 3 Goto step 1, retrieving another node from the list

Step 4 If F* = , there is no path from Ns to Nt;

go to step 5.

Otherwise, F* is the optimal cost of going from Ns to Nt and the path is determined from the labels as described below.

Step 5 End.

When F* = , the path is determined from the following procedure. /

Step 1 Let i = s.

Step 2 Determine Nj, the next node in the optimal path, from the label {Nj,d(i)} assigned to node Ni.

Step 3 If j=t, the path has been determined; go to Step 4.

Otherwise, set i=j and go to Step 2.

Step 4 End.

Other packet switching issues related to addressing

Datagram network

This is conceptually the simplest type of packet switched network, each packet is self contained and must contain the user data and any Information needed by the network to deliver the packet correctly such as the calling address.

• Very resilient, since each packet finds its own way through the network depending on the loading and status of switches and links at the time.
• Datagram networks are more efficient for quick transactions which may only generate 1 or 2 packets.

• High overhead, since each packet must contain the calling address, optionally the called address, and any additional facilities such as reverse charging.
• There is the possibility that since packets can go through the network by different routes they could overtake each other, therefore steps need to be taken to ensure packets are reassembled in the correct order at the destination.

Virtual call network

This is similar to a telephone call in that there is a call establishment phase, followed by data transfer, followed by call cleardown. Only the call request packet need contain the calling address and call facilities, this call request packet sets up a route through the network and subsequent packets need only specify a virtual circuit number to identify the call.

Advantages of a virtual call network

• Packets are delivered in order since they all take the same route.
• More efficient in line usage since, each packet does not need to contain the full address.
• Network resources are allocated at call setup time so that even during times of congestion, provided that a call has been setup, then subsequent packets should get through.
• Billing is easier, since billing records need only be generated per call and not per packet.
Disadvantages of a virtual call network
• The switching equipment needs to be more powerful since each switch needs to store details of all the calls that are passing through it and to allocate capacity for any traffic that each call could generate.
• Resilience to the loss of trunk circuits is more difficult since if a trunk fails then all the calls over that trunk must be dynamically reestablished over a different route.

Datagram v Virtual Circuit

CCITT chose a protocol that supports virtual call networks, however as a concession to datagram networks X.25 allows 'fast select calls' which are call request packets which may contain upto 128 bytes of data.

Call reconnect on trunk failure

DTE DCE trunk DTE DCE

unique call ID

-- call -- ------------------- -- call --

-- acc -- ------------------- -- add ---

------------------- data transfer ---------------------

trunk fails

---CLR F500 * CLR F500 ---

------- re-est over diff --

route

same unique call ID

-------- REJ 0 ------------

------- REJ 0 -------------

recover any data that may have been lost on failed trunk

---------DATA 0 -----------

--------------------- data transfer ---------------------

=================================================================

If the call cannot be re-established

DTE DCE trunk DTE DCE

unique call ID

-- call -- ------------------- -- call --

-- acc -- ------------------- -- add ---

------------------- data transfer ---------------------

trunk fails

---CLR F500 * CLR F500 ---

------- re-est over diff --

route

same unique call ID

-- CLR NC ---- --- CLR NC --

## Public Network Routing Principles

For a network it is not enough to have diverse physical routes. You must also ensure that the routing tables in the switches are able to make use of the diverse routing. Otherwise a single failure may isolate part of the network.

The routing tables may be generated offline and then downloaded to the network.

Example:

Transit

Level

+-----+-------+ +-------------+

Intermediate | Switch +---------+ Switch|

Level 2 | +---------+ |

+---+------+--+ +-+------+----+

| +--------------+-+ |

| +----------------+ | |

+---+----+----+ +---+----+----+

Dependent | switch | | switch |

Level 3 | | | |

+-----+-------+ +-----+-------+

| |

| |

+-----+-------+ +-----+-------+

Internet | switch +---------+ switch |

Level 4 | +---------+ |

+----+--------+ +-------------+

user port

This diagram represents a minimum configuration, it appears to fully connected with backup paths, however when you look at the routing you may see the following:

Transit

Level

A

+-----+-------+ +-------------+

Intermediate | B +-S---S-+ C |

Level 2 | +-S---S-+ |

+---+------+--+ +-+------+----+

P +--------------+-+ S

| +--------------P+ P P

+---+----+----+ +---+----+----+

Dependent | D | | E |

Level 3 | | | |

+-----+-------+ +-----+-------+

P S

| S

+-----+-------+ +-----+-------+

Internet | F +------P-+ G |

Level 4 | +------P-+ |

+----+--------+ +-------------+

P

H

where: P = Primary Route

S = Secondary route

As an example take a call from the transit level (A) to a host (B). The call enters switch B, This would route it to its primary route to switch D, This would route it to its primary route to switch F. This has a primary route to the host (H) so the call succeeds.

Now Imagine there is a fault between switch D and F.

Transit

Level

A

+-----+-------+ +-------------+

Intermediate | B +-S---S-+ C |

Level 2 | +-S---S-+ |

+---+------+--+ +-+------+----+

P +--------------+-+ S

| +--------------P+ P P

+---+----+----+ +---+----+----+

Dependent | D | | E |

Level 3 | | | |

+-----+-------+ +-----+-------+

P S

x Fault this is down S

+-----+-------+ +-----+-------+

Internet | F +------P-+ G |

Level 4 | +------P-+ |

+----+--------+ +-------------+

P

H

where: P = Primary Route

S = Secondary route

Again take the same example of a call from the transit level (A) to a host (H). The call enters switch B, This would route it to its primary route to switch D. This would try its route it to its primary route to switch F but its down, there are no secondary routes so the call would fail.

HENCE CALL FAILS DUE TO A SINGLE TRUNK FAILURE.

Redirection