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
- Link assignment
- Routing assignment
- Capacity assignment
Link Assignment
Some possible initial configuration strategies:
- Connections to N neighbours in order of least cost.
- Connections to N neighbours in order of greatest communication.
- Random link selection.
- 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.
Network-Layer Addressing
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
Identification Number subaddress
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.
Subaddess
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
TCIP/IP Address Allocation and Registration
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.
Adaptive routing strategies
Adaptive Routing in ARPANET
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.
Hierarchical Adaptive Routing
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.
Isolated Adaptive Routing
In which each node makes routing decisions based on purely local Information.
Distributed Adaptive Routing
In which the nodes exchange Information and the routing decisions are based
on a blend of local and shared Information.
Centralised Adaptive Routing
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.
Advantages of a datagram network
- 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.
Disadvantages of a datagram network
- 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.
- 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.
Issues
Redirection
loadsharing
resilience.
