NETWORK ROUTING OBJECTIVES
AND
CONSTRAINTS
495
1
I
Top
layer
Figure
28.3
Five-link connection
in
a three-tier network hierarchy
Careful network design and a shrewd call routing programme at each exchange will
ensure conformance to the routing plan, but this may require considerable adminis-
trative effort in establishing appropriate routing tables at each switch or exchange within
the network as we discuss later.
Signals which accompany the call or connection setup message are intended to help
to convey the previous history of the call or packet (for example, the existence of a
previous satellite link) and make appropriate routing choice easier.
In the example of Figure
28.4,
caller
1,
connected to exchange A and wishing to call
B, has reached exchange
C
by means of a satellite link. Although both cable and
satellite links are available from exchange
C to exchange
B,
the call is only allowed to
mature if a circuit is available on the cable link. If instead the call were to be permitted
to overflow to the satellite link, then the connection would not meet the required
transmission quality standard. (If, however, the connection was only possible by the use
of a double satellite link, then the call could have been permitted to mature).
By contrast, caller
2,
(on exchange
C,
may be connected either over the satellite or the
cable link. Two alternative routing policies are available to the owner and operator of
exchange
C
to
ensure optimum routing of both caller’s calls. In the one shown, the
operator has chosen to make the satellite first choice for caller
2’s
calls. This inflicts
496
NETWORK ROUTING, INTERCONNECTION
AND
INTERWORKING
Exchange
Caller
1
Satellite Satellite
Exchange
,
Cable
Exchange
c
(only choice
for
B
caller
1
)
Destination
I
-*
Caller
2
Figure
28.4
Routing
based
on
call
history
the propagation delays associated with satellite links on a large proportion of caller
2’s
calls to exchange
B,
but has the advantageous effect
of
maximizing the availability of
cable circuits for connection of caller
l’s
calls to exchange
B,
so
preventing the failure
of calls in the instance when otherwise only an unacceptable ‘double satellite path’ were
available.
In the alternative scheme the operator of exchange C could have chosen to make the
cable link to exchange
B
first choice, even for caller
2’s
calls. This would have the effect
of minimizing the propagation time of caller
2’s
calls, and may be desirable when caller
1
is a customer of a different network operator.
A common feature of all good routing schemes is their simplicity. Complicated
routing schemes can lead to administrative difficulties and oversights. Apart from
network congestion and poor transmission quality, slow call set-up and a burden of
exchange data maintenance can also result.
All routing schemes rely upon the exchanges to analyse the
dialled number
or
network
address
(i.e.
OS1
layer
3
address) to determine the destination of the call. Additionally,
signalling information about required supplementary services (e.g.
closed user group
or
intelligent network
services) and the call’s previous history (e.g. ‘previous satellite link’)
help to determine the selection of an appropriate route to the destination and an
appropriate charge.
Closed user group (CUG)
information carried at connection setup time can be used to
ensure that only certain customer lines or ports may be connected together. This might
help, for example, to prevent unauthorized dial-in to a computer centre. Only members
of the
CUG
may be connected to the centre. Intelligent network services include, among
others, freephone, in which the charges for the call are invoiced to the receiver rather
than the call originator. Finally, the connection history (e.g ‘previous satellite link’) or
required quality attributes of the connection (e.g. for frame relay the
committed
information rate (CZR)
may also affect call setup or connection routing.
THE ADMINISTRATION
OF
ROUTING TABLES
497
The switches in all types of networks therefore need to analyse the
network address
to
determine the intended destination of a connection and other service parameters and
quality information to assess any constraints on the path to the destination. Ideally,
only the minimum amount of information is analysed at any particular switch or
exchange, to minimize time and effort required to determine the next step in the path.
Thus, for example, at an outgoing international telephone exchange at least the
country
code
indicator digits of the dialled number need to be inspected to select the appropriate
route to the country concerned. A trunk telephone exchange must inspect only the
area
code
to determine the onward route selection. Finally, a destination local exchange
needs to examine all the digits of the destination customer’s local number to select the
exact line required.
28.3
THE ADMINISTRATION
OF
ROUTING TABLES
Historically, network routing plans were administered by means of
routing tables
in
each of the individual switches or exchanges. Each exchange thus had a ‘look-up’ table
of permissible address code (e.g. telephone area codes), and alongside each code, a list
of the alternative routes available
for
completion of relevant calls. Thus in the example
of Figure 28.5, we illustrate the network topology of six interconnected nodes, and the
routing tables resident in exchanges A and B to reach the various telephone number
blocks, OOlXX (at A), 012XX (at
B),
034XX (at D), 053XX (at C), 069XX (at E) and
091XX (at
F).
The example
of
Figure 28.5 illustrates the complexity of setting up and administering
the routing plan, as well as the problems of circular routing and maximum hop count
already discussed. The first observation is that each of the exchanges requires a separate
routing table. There is little or no commonality between the routing tables (the other
four for exchanges
C,
D, E and
F
are not shown),
so
that considerable manual effort is
required first to work out the tables and second to type them in to the
configuration data
of each of the individual exchanges. There is a very high probability in complex
networks of errors in the routing plan design and further potential for errors during the
typing-in stage.
If we now examine closely the routing commands given to exchanges A and B in
Figure 28.5 for the handling of codes 053XX (to exchange C) we can see the potential
for a circular route being set up, for if exchange D is told to use ‘via A’ as a third choice
route to exchange C (code 053XX) then at times when the links B-C and D-C are
overloaded or out-of-service due to network failure calls to code 053XX may be passed
in endless loop A-RD-A, etc.
We also see the problem of minimizing the maximum hop count. The intention of the
designer of the network in Figure 28.5 is that the maximum hop count shall be three.
Thus, for example, the third choice route from A-to-C is A-E-D-C. However, the
third choice route from E-to-C might also be via three hops (E-A-RC),
so
how do we
prevent the circuitous routing (exceeding the maximum hop count) A-E-A-B-C?
The answer is that the routing tables need also to take account of the
origin
of the
call as well as the intended destination.
Thus calls arising at exchange E but
origin-
ated
by exchanges other than exchange
E
should not be allowed the third option to
498
NETWORK ROUTING, INTERCONNECTION
AND
INTERWORKING
a
m
'S
-
a
(c
'S
-
Y
X
m
d
.M
ROUTING
PROTOCOLS
USED
IN
MODERN NETWORKS
499
exchange C. Similarly, calls appearing at exchange
E
directly from exchange A should
not be passed directly back again.
Further increasing the problem, the dialled digit train may need to be altered.
Historically, this was necessary because the switching action ofelectromagnetic exchanges
was triggered by the pulsed digit train,
so
that the digits were literally ‘used’ to activate the
switching.
As
a result each subsequent exchange sent fewer digits to the next along the
chain of the connection.
So
that, for example, an electromagnetic exchange at point A in
Figure
28.5,
might expect only to receive the digits XX when accepting calls to the digit
range OOlXX, the ‘001’ having been used or deleted by previous exchanges in the
connection. Modern computer controlled exchanges generally relay the entire dialled
number, but when signalling to older electromechanical exchanges they may have to adapt
the train to the
routing digits
required to activate the switching (Chapter
6).
The problems of call origin and call history dependent routing described above make
for complicated signalling between the exchanges and complicated routing tables (based
on the
route origin)
within the exchanges. Worse still, every time further capacity or new
trunks are added to the network topology, all the routing tables in each of the
exchanges may need to be amended. Routing table administration remains one of the
major operational burdens of telephone and ISDN network operators.
28.4 ROUTING PROTOCOLS USED
IN
MODERN NETWORKS
In contrast to telephone networks, where typically the individual switches (exchanges)
are supplied by different equipment manufacturers, data networks have often been built
from switches all supplied by a single manufacturer, with a common
network manuge-
ment
system. The common manufacturer and network management system shared by all
the switches enables the use of proprietary signalling and control mechanisms to be
applied to traffic routing within the network. Thus most data network management
systems require only the association of groups of destination network addresses to
particular switches. The routing tables for all other switches are then generated according
to the network management system’s knowledge of the current network topology, using a
set of automated routing design rules and routing
algorithms
(e.g. preference for high
capacity routes over low capacity routes, preference for low hop count path, etc.). The
human task of administering routing tables in modern data networks is thus far more
straightforward than telephone network routing table administration.
Once the route is set-up for a particular connection (i.e. in a connection-oriented
network such as
X.25
packet switching, frame relay or ATM), it is not usually altered
during the duration of the call (i.e. the period of communication). Leaving the routing
of the connection unaltered (path oriented routing) means that the transmission
propagation time across the network between the two devices is not subject to any
unnecessary jitter (variability of delay). In addition, there is much reduced risk of cells
which might otherwise have taken different paths from getting out of order. It is also
much easier to determine and manage a network loading scheme, because nominal
bandwidth allocations may be made to each of the connections which must statistically
share a given physical transmission path.
500 NETWORK ROUTING, INTERCONNECTION AND INTERWORKING
In the most modern of networks (e.g. router and ATM networks), the entire routing
administration is automated,
so
that switches within the network are programmed to
‘learn’ about the topology of the network the ideal route to a given destination
(network address). A
routing protocol
is employed by such networks
so
that the
individual nodes can discover the network topology automatically and keep themselves
abreast of changes. Examples of
routing protocols
are used in the
Internet
are
0
routing information protocol (RIP)
0
open shortest path first (OSPF)
0
border gateway protocol (BGP)
0
exterior gateway protocol (EGP)
Routing protocols are used widely in the
Znternet
to pass information between routers
about the various sub-networks making up the network. One of the first protocols
developed was the
exterior gateway protocol (EGP)
defined by RFCs 827,888 and 904).
This was a protocol intended to be used between router on a sub-network (say university
campus) and an inter-site network (internet)
so
that
internal
UNIX
computers on the
sub-network could locate and establish connections to
exterior
ones in bordering
networks. EGP has subsequently been largely replaced by the
border gateway protocol
(BGP)
defined by RFC 1267.
Within most router networks (e.g. Cisco, Wellfleet, 3Com, etc.) it is common to use
proprietary routing protocols
(interior routing protocols, ZRP),
but the
RIP (routing
information protocol)
defined by RFC 1058 set the initial standard for transfer of
routing topology information,
so
that a routing table could be maintained by a
source
router.
The table enables the router (near the source of a message) to determine the best
path across the
Internet.
RIP complements the
hello protocol
of RFC 89
1
which is used
to register and synchronise new connections in the network.
The
OSPF (open shortest path Jirst)
protocol is a newer, more complex and more
sophisticated protocol than RIP but intended to bring about a simplification of the
topology of the
Internet
by introducing a structured hierarchy of routing nodes. It has
become the accepted ‘standard’ routing protocol in router networks,
Intranets
(corporate router networks) and the
Internet.
As an example of the way in which switches within a modern network may be pro-
grammed automatically to discover the network topology and keep abreast
of
all changes
made to it, thus enabling optimal routing of calls, connection and traffic at all times, we
discuss next how the
hello state machine
defined in the ATM network standards (see also
Chapter 26) enables constant updating
of
the
ATM
network topology state.
28.5
NETWORK TOPOLOGY STATE AND THE
‘HELLO STATE MACHINE’
The ATM forum is developing, as part of its
PNNZ (private network-node interface,
based on the ATM UN1 v3.1) specification, a sophisticated
source routing
control
mechanism, in many ways similar to the techniques used in the
Internet.
NETWORK TOPOLOGY STATE AND THE ‘HELLO STATE MACHINE 501
By keeping a record in its
topology database
of all information supplied to it about
the topology of the network
as
a whole, an ATM network node always has a view of the
entire private ATM network routing domain. The node is thus able to determine the
route from itself
to
any
reachable
address.
The information about the topology and any changes made to it are conveyed as
topology state elements,
including
topology state parameters.
These are conveyed
between the nodes in the network by means of
topology state packets. Topology state
parameters
are classified into two types
0
attributes (these influence routing decisions; a security
attribute
of a particular node
may cause the set-up of a particular connection to be refused)
0
metrics (these are values which accumulate over the path of the connection as a
whole to determine whether it is acceptable, e.g. the propagation delays of individ-
ual links in the connection are added as
metrics)
When a new link or node is added to the network, then the directly affected nodes
communicate with one another over the new link using the
hello
procedure. This is a
standardized protocol enabling the two nodes to identify themselves to one another and
work out the change in topology of the network as a whole. The new topology
information is then flooded (i.e. broadcast) to the other nodes in their
peer group
(i.e.
sub-network) or
advertised
to neighbouring border nodes of neighbouring peer groups
by means of
topology state packets.
These inform the other nodes of any new addresses
which are now
reachable
and also which exit route to take from the
peer group
(PG).
The routing information is stored in the topology database as ‘address A
reachable
through entity B’, where
B
is a known node within the peer group. Routing
to
outside
of the
peer group,
as we shall see, is catered for by the
peer group leader (PGL).
A
peer group
as defined by ATM forum’s PNNI specification, is a collection of nodes
sharing the same
peer group
ID
(identiJier).
As the peer group
ID
is defined during the
initial configuration of the node by the human installer, a
peer group
is in effect a human
operator-defined sub-network.
Within
a
peer group
an
election
determines the
peer group leader (PGL).
The
election
is an ongoing process which results in the node with the highest
leadership priority
taking over certain of the more important network routing (inter-sub-network) tasks on
behalf of the peer group as a whole. The peer group leader is automatically promoted to
the next layer in the routing hierarchy. However, should another node achieve a higher
leadership priority (as a result of some topology or capacity change within the peer
group) then it will take over the PGL function.
At the next layer of the hierarchy each
peer group
appears only as a single node,
a
logical group node (LGN).
It is represented in the topology management process at this
level by the peer group leader. At the highest level in the hierarchy is the top peer group
(Figure
28.6).
When neighbouring nodes running the
hello protocol
conclude that they belong to the
same
peer group
then they synchronize their databases (recording the sub-network or
peer group
structure). They then
jood
(i.e. broadcast) this information to
all
other
members of the peer group. In the case where the nodes do not belong to the same peer
group, then they are
border nodes
in adjacent peer groups, and an
uplink
is said to exist
502
NETWORK ROUTING, INTERCONNECTION AND INTERWORKING
top
peer group
QB
I*
I\
I\
I*
I\
I,
,
logical group
node
(LGN)
peer group
,’
,’
Figure
28.6
Peer groups
(PG),
logical group nodes
(LGN)
and the hierarchy
of
PNNI
routing domains
from the border node to the
peer group leader
of the neighbouring
logical group node.
The communication between the border node and its partner’s
peer group leader
is
equivalent to the hello procedure but this time between
logical group nodes
concluding
that they are interconnected. The new topology information in this case is said to be
advertised
to other
peer group leaders
at the same hierarchical level. The
exterior
reachable addresses
(ERA,
i.e. those outside the peer group) are defined in a special
routing table called a
designated transit list
(DTL)
held by the peer group leader.
In contrast to
uplinks, horizontal links
are logical links between nodes in the same
peer group.
Once the route to a given destination has been determined by a source node (either
from its own database or from information provided by the peer group leader), normal
UN1 signalling procedures can be used to set up the connection. If necessary (e.g. due to
current traffic conditions in the network causing a particular route to be unsuitable or
overloaded)
crankback
and
alternative routing
may be invoked (in other words the first
route choice is abandoned and a second path is attempted).
The node names (or addresses) used to identify nodes in a PNNI network are similar
in style to
Internet
addresses: lots of numbers, dots and letters (Chapter 29). Thus the
four nodes in peer group PG(A.3) of Figure 28.6 are called A.3.1, A.3.2, A.3.3, A.3.4.
This is the style of information held by the
topology database and designated transit list
(Address A
reachable
via B3.2, C4.4,
D5.7,
.
. .
,
etc.).
SIGNALLING IMPACT UPON ROUTING AND CALL SET-UP DELAYS
503
28.6
SIGNALLING IMPACT UPON ROUTING AND
CALL SET-UP DELAYS
We next consider the way in which the network signalling can impact upon the time
taken to analyse destination network addresses and setup connections across a
network. Our example is pitched in a telephone or
ISDN
network but similar effects
could equally impact the propagation of packets or frames across a data network.
Most telephone network and
ISDN
signalling systems allow the number analysis and
route selection to be carried out in one of two ways, either in an
en
bloc
manner, or in the
alternative
overlap
manner. In the
en bloc
manner, the first local exchange waits for the
customer to dial all the digits
of
the destination number before the number analysis is
completed and the outgoing route is selected. All necessary digits of the dialled number
and other information are then sent together (or
en
bloc)
to the subsequent exchange.
The subsequent exchanges are thus not bothered with setting up calls until all the in-
formation about the call and its destination is available. The exchange processor load on
subsequent exchanges is thereby minimized. Figure 28.7(a) illustrates
en
bloc
call set-up.
In the alternative
overlap
manner
of
call set up, each exchange in the connection
selects the outgoing route as soon as it has sufficient information to do
so (even if not all
the information about the destination has been received) and passes on subsequent
information as it receives it. Thus in the diagram of Figure 28.7(b), the connection may
already have been made right through to exchange
'C'
even before the customer has
finished all the digits of the destination number. The same would not be true in the
en
bloc
case. It is this feature that gives the
overlap
signalling method its edge over
en
bloc
All dioits
I
I
before
diallid
Exchange
exchange A
I
A
I
responds
I
Col1
swltched
then
all
sent to
informotion
'en bloc
exchange
B
Other
exchanges
la) 'En-bloc'call set-up
Local
Trunk
exchange
.
Other
exchange-
'
exchonge
Trunk
'A'
'C'
'8'
exchonges
Exchange switches
Number through to
'8'
0
dialled
subsequent digtts
on directly
os
recelved
.
and passes
(Area code1
and destination
to
'B'
digits
Passed directly Digits passed
on
as available
(b)
'Overlap' call set up
Figure
28.7
'En
bloc'
and 'overlap' signalling at call set-up
504
NETWORK ROUTING, INTERCONNECTION AND INTERWORKING
signalling, in being faster at setting up calls. The disadvantage of the method is the
greater processing time wasted at all exchanges waiting to receive and relay digits of the
dialled number.
The same problems arise in data networks.
In a frame relay network, frames may be many thousand bytes in length, each preceded
by a
header
which identifies the intended destination. The time to propagate the frame
from end-to-end across the network thus depends heavily upon whether it is relayed in its
entirety from each node to the next and wholly received before it is relayed on (akin
en bloc
mode),
or whether onward tranmission may start as soon as the destination has been
identified (i.e. immediately after analysis of the header, akin to
overlap mode).
In many
cases in datacommunication, where a
cyclic redundancy check
(CRC)
code is applied to
detect and correct errors in the contents of the frame, the
en bloc
mode has to be used,
because the CRC must be checked before the frame is relayed onwards. The CRC is
usually transmitted at the end of the frame. Although this improves the accuracy of
delivered frames, it increases the time needed for propagation through the network.
28.7 PLAUSIBILITY CHECK DURING NUMBER ANALYSIS
A common failing of network operators, and one which may seem attractive (par-
ticularly to those operators using the
en bloc
method of signalling call or connection
set-up information), is to carry out undue
plausibility checks
on the destination
network
address
or dialled number. Thus, for example, telephone exchanges could be made to
look up and check whether a valid number of digits have been dialled, or whether a
particular area code within a destination country is valid, etc. Such
plausibility checks
can have the benefit of removing the burden of spurious traffic from the network.
Unfortunately, however, the updating
of
these
plausibility checks
is often overlooked
when new area codes are made available in the destination country, or when number
length changes are made. The result is that the exchanges may fail calls to newly valid
numbers, with understandable customer annoyance. Had the
plausibility check
never
been used, the problem would not have arisen. Furthermore where plausibility checks
are instigated in a network using overlap signalling, the call set up may be unnecessarily
delayed. Special administrative care
is
therefore required in the use of such checks.
28.8 NETWORK INTERCONNECTION
Until the early
1980s
most telecommunications networks were owned and operated by
state monopoly telephone companies. Thus within a given country or territory the
telephone network or public data network was operated by a single entity,
so
that tech-
nical interface standards and quality levels were uniform across the network and routing
plans could be determined unilaterally. For international interconnection of national
monopoly the ITU (International Telecommunications Union) existed to agree and
regulate common international standards for
gateway
connections and routing between
different national networks. These set the standards for technical interworking and
operational cooperation.
Không có nhận xét nào:
Đăng nhận xét