Note: Descriptions are shown in the official language in which they were submitted.
CA 02294807 1999-12-30
WO 99/02009 PCT/SE98/01314
Loop Detection
Technical Field of the Invention
The present invention relates to a method and a device for traffic-management
in
networks.
In particular the present invention relates to a method for detecting loops in
networks, in particular in a connection-oriented networks such as, for
example, an
Asynchronous Transfer Mode (ATM) networks, and to a device for use in this
method.
Description of Related Art
There are two major types of networks used for sending information between
networks - connection-oriented networks and connection-less networks.
In connection-oriented networks, such as, for example, an Asynchronous
Transfer
Mode network, a message or information stream is transferred between two end
systems (such as a computer or a telephone or the like),e.g. A and B,
connected to
the network by a connection which is established for, and maintained during
the
transfer. Thus before any message can be sent a logical/virtual connection set-
up
phase must take place. During the connection set-up process, which can be
initiated
by the end systems through signalling to the network or by management systems
or
by other means, a path through the network is selected, logical channels are
allocated on the links between the nodes in the paths, resources are reserved
in the
links and the nodes, and the logical channels are interconnected in the nodes,
which
in this type of network comprise switches.
During the connection set-up process the switches register interconnected
logical
channels in tables so that the information in the subsequent data phase of the
CA 02294807 1999-12-30
WO 99/02009 PCT/SE98/01314
7
connection can be transferred easily, typically by hardware logic, between
interconnected logical channels.
In the case of ATM networks the information in the connections is sent in the
form
of cells, each containing 53 bytes of which 5 form a header and 48 are the
payload.
The header contains the identity of the logical channel for the connection on
the
current link. This identifier is changed as necessary by the switch as the
cell passes
through the node and is transmitted on the next link. The payload contains
information from the stream or message being transferred by the connecrion.
For connections set-up as a consequence of initiating signals from the end
systems,
loops typically can not occur as this is prevented by functions in the network
which
handle the signalling.
1n order to ensure that the route is functioning correctly special maintenance
packets called loop-back cells can be sent out on the route. A loop back cell
contains information in which the source of the loop-back cell and the
destination of
the cell can be identified. There is also an indicator, called a loop-back
indicator,
which shows whether the cell is travelling towards or from the loop-back
point/destination. Thus if node A wishes to check that the route to node B is
functioning correctly it transmits a loop-back cell with A as the source and B
as the
destination. The cell contains information which states that the cell is a non-
user
cell, and in particular that it is a maintenance cell. The maintenance cell
has a field
indicating that it is a loop-back cell. This field informs the destination
switch or
node, in this case node B, that it must turn around the cell and send it back
to the
source. Thus a node, upon receiving a loop-back cell, checks the loop-back
point/destination field to see if it shall loop the cell back. If it does loop
the cell
back then it changes the loop-back indicator to show that the cell has been
looped. It
does not change the source identity or the loop-back identity. There may also
be
another field in the loop-back cell, called the correlation tag, which remains
unchanged. If the route between A and B is functioning correctly then node A
will
CA 02294807 1999-12-30
WO 99/02009 PCT/SE98/01314
receive back the loop-back cell from B with the loop-back indicator indicating
that
the cell has been turned around. This event occurs some time after the
insertion of
the loop-back cell. This time depends on the length of the route and any
queuing or
other delays present on it.
The connection set-up procedure takes some time, in the order of tens to
hundreds
of milliseconds per node traversed, and thus introduces some latency for the
end
systems. However once the connection is established then the information can
be
transferred through the nodes/switches in an efficient way by the switch
hardware.
When a fault occurs in the network the connection is typically broken and a
new
connection has to be set up. The new connection will then be routed so as to
avoid
the troubled part of the network.
In large connection-less networks (by connection-less it is meant that no
fixed
communication is set up between communicating devices but that information is
sent by the best route available at the time) e.g. the Internet, where
information is
sent as discrete packets of information between nodes, e.g. A, B, the packets
comprise a header i.e. a part which contains information about, amongst other,
its
identification, where it came from (its source), where it must go (its
destination), its
length and other useful infolnation. Each node uses a routing protocol to
exchange
routing information on how to best reach other nodes in a network. A
description of
a routing protocol is described in HUITEMA, CHRISTIAN, "Routing in the
Internet", ISBN 0-13-132192-7, Chapter 4.4 to Chapter 4.2.6., the disclosures
of
which are incorporated within this application by reference. When these
packets of
information are being routed between nodes in a network there is always the
possibility that a loop can occur. This may happen when a link or a node in a
route
is closed down or otherwise temporarily or permanently is unable to accept a
new
package of information from a preceding node. The preceding node in this case
then
forwards packets of information via an alternative path which it has stored in
its
routing information protocol. It is however possible that this alternative
path at
some stage contains a link which has a routing information protocol which
leads
CA 02294807 1999-12-30
WO 99/02009 PCT/SE98/01314
4
back to this preceding node. In this case the packets are routed from the
preceding
node via the alternative path back to the preceding node again. Thus a loop is
formed. If a loop is formed then system resources are wasted on unnecessarily
sending the packets on hops around the loop. Information packages caught in a
loop
can be considered as being worthless as even if the loop is broken it is
unlikely that
they can be delivered to their destinations at the collect time.
Loops are, however, usually transient problems. This is because the routing
information protocols are updated with information on the network status and
hence
i0 the primary and alternative paths for each node are constantly also being
updated.
This updating can be performed by, for example, exchanging distance vectors or
information on link states between nodes.
Distance vectors contain information for each destination in the network,
usually
1~ one element per destination, on the time, distance or 'cost' of sending a
packet from
the particular node to that destination. Each node exchanges, by a routing
protocol,
distance vectors with all its neighbouring nodes. These exchanges take place
periodically and ,possibly, also when events occur which lead to changes in
the
costs. The distance vectors received from neighbours and knowledge about the
cost
20 of the links to the neighbours are used by nodes to recalculate its
distance vectors.
When a packet is received for forwarding to a certain destination the
corresponding
distance vector states which link should be used to forward the packet at the
lowest
cost. The path with the lowest cost is then used to route the packet. If a
node or a
link to a node fails in a particular path then its neighbouring nodes note
that the cost
25 of using this failed node or link is infinity and therefore an alternative
path must be
chosen. The information about the failed node is sent to other neighbouring
nodes in
an updated distance vector. These nodes then update their own distance vectors
and
send them to other neighbouring nodes and so on. Thus the information on the
failed link slowly propagates through the network. Each updated distance
vector
30 influences all the neighbouring nodes and it takes a number of exchanges of
distance vectors between neighbouring nodes before the distance vectors
converge
CA 02294807 1999-12-30
WO 99/02009 PCT/SE98/01314
and a new steady-state is re-established. During this convergence period it is
possible that packages which were sent on the original path are influenced by
the
changing distance vectors and end up in a loop. This loop naturally ends when
the
distance vectors have converged. However during the convergence period, which
5 can last up to the order of a minute, scarce processor and bandwidth
resources are
wasted.
Another reason for the transient nature of loops is that in most connection-
less
networks there are protocols in which each packet of information has a
counter,
usually in its header, called "Time to Live" which ensures that the package is
dropped, i.e. destroyed and removed from the network, after either a certain
time
has lapsed or, more usually, after the package has passed through a
predetermined
number of nodes. Depending on the value of the "Time to Live" counter value
when
the loop occurs and on the delays in the loop, a loop can exist for period of
up to
1~ approximately one minute. During this period scarce router processor
resources are
wasted on processing the packets in the loop which, as mentioned above, are
considered worthless and are doomed to be discarded. A description of a "Time
to
Live" counter can be found in HUITEV1A, CHRISTIAN, "Routing in the Internet",
ISBN 0-13-132192-7, Chapter 3.3.1 "The Internet Header" which is incorporated
within this application by reference.
Connection-less networks are flexible and messages can be sent quickly as
there is
no need to establish a reserved connection between source and destination
before
sending a message. These networks however require considerable processor
capacity to determine the destination of each package being transmitted and
loops
can occur in the system which waste resources.
In order to improve the performance of networks, it has been proposed to form
so-
called "label switching networks" (also known as "mufti-protocol label
switching
networks") in which a connection-less network is superimposed on a connection-
oriented neri~rork. In other words a connection-less device such as a router
is
CA 02294807 1999-12-30
WO 99/02009 PCTISE98/01314
6
associated with a connection-oriented device such as a switch in. for example,
an
ATM network. Each router uses its routing protocol to build up its routing
table
with destination information which states which is the best route towards each
specific destination, i.e. which node, called the downstream node, it must
forward
traffic to in order to reach the desired destination. It will then request a
logical
channel number, known generically as a 'label', from that downstream neighbour
for the traffic/packet to each destination. When the node gets a corresponding
request from its upstream neighbours it can order its switch component to
interconnect these channels. As this process is being carried out in the nodes
in the
i0 network, link layer connections from each source to each destination will
be
established. These connecrions will follow the same paths as the best paths
which
have been decided by the routing protocols and distance vectors.
A problem with such label switching networks is that the router network can
cause a
loop which is then superimposed onto the connection-oriented network. As there
is
no special mechanism in a connection-oriented network for detecting loops it
is
possible for such loops to exist for relatively long periods of time before
the router
network notices in the normal way that there is a loop.
Summary
A problem with connection-less, e.g. router, networks superimposed on
connection-
oriented, e.g. switch and/or ATM, networks is that the existence of a loop
causes a
waste of system resources. Present art routing protocols designed for router
networks do not provide guarantees against loops. They merely provide
conditions
in which the protocol rules ensure that the marimum life time of a loop is
limited.
This means that if a loop occurs then system resources are wasted until the
loop
reaches its maximum life time or the system undergoes some change which
coincidentally breaks the loop.
CA 02294807 1999-12-30
WO 99/02009 PCT/SE98J01314
7
The present invention seeks to reduce the wastage of system resources when a
loop
occurs by providing active means for detecting loops and for breaking loops in
a
connection-oriented network, in particular an ATM network, and more especially
a
network comprising a connection-less network superimposed on a connection-
s oriented network. This is achieved by a method in which when a source switch
establishes a connection to a destination switch or node in a connection-
oriented
network it inserts a loop-detecting means, for example a loop-detecting cell,
into the
route. This loop-detecting cell contains identifying means which can be
recognised
by the source node if the loop-detecting cell returns to the node. It there is
no loop
IO then this cell will continue to the destination point of the route where it
will be
discarded. If there is a loop then the loop-detecting cell will return to the
source
node. It will be recognised by the source node and this will alert the source
node
that there is a loop present and action can then be taken to avoid the loop,
e.g. the
source node can inform an associated network controlling device, e.g. a
router, that
15 there is a loop present. This has the advantage that a loop can be detected
within a
few milliseconds instead of approximately one minute.
In a preferred embodiment of the invention the loop-detecting means is a loop-
back
cell in which, in the information fields of the cell, the source node or
switch is both
20 the source and destination (i.e. turning point) of the loop-back cell. If
there is no
loop present then the Loop-back cell cannot return to the source node or
switch
without being (intentionally) looped as it is transmitted on a link which only
leads to
the destination point of the route. If there is a loop present then a loop-
hack cell
which has the source identity in both the source and destination/Ioop-back
fields
25 will return to the source node or switch. The loop-back indicator shows
that the cell
is travelling towards the turning/loop-back point. The node or switch detects
the
loop by realising that it is itself the source and destination of the loop-
back cell. It
checks if it is the destination for the loop-back cell and if it is not the
destination
then the cell is transmitted along its logical channel. In order to identify
that it is the
30 originator of the loop-back cell it can use the source identity field or
the correlation
CA 02294807 1999-12-30
WO 99/02009 PCT/SE9$/01314
tag, or both. It shall also check that the loop-back indicator shows that the
cell is
flowing in the direction towards the Loop-back point.
In one embodiment of the invention, in order to ensure that packages of
information
are not sent into a potential looping path, after sending out a loop detection
cell the
source node can queue incoming traffic until a certain time has elapsed. This
time is
chosen such that there is a significant probability that if there is indeed a
loop then
the loop detection cell will return to the source node before the time
elapsed.
However the elapsed time must not be too long as this leads to unacceptable
delays
in the processing of the packets and requires large buffers. The time is
therefore
selected dependent on the type of information being sent and the expected
length of
the route.
In an other embodiment of the invention, in order to avoid delaying packets
unnecessarily the node starts to send packets without delay along the route
after the
loop detection cell has been sent. This means that an assumption is made that
the
new route will not cause a loop. This assumption is acceptable in the case
that the
occmTence of loops is rare and/or it is unacceptable to delay packets.
Brief Description of the Drawings
Figure 1 shows a schematic diagram representing one embodiment of a simplified
network according to the invention.
Figure 2 shows schematically one embodiment of a loop-detecting cell according
to
the invention.
Detailed Description of Embodiments
Figure l, which will be used to illustrate the basic idea of the invention,
shows an
example of a hypothetical simple connection-less network superimposed on a
CA 02294807 1999-12-30
WO 99/02009 PCT/SE98/01314
9
connection-oriented network consisting of nodes A, B, C, D and E. In this
embodiment, each node has a connection-less device, shown for the sake of
example as routers, AR, BR, CR, DR and ER respectively, and a connection-
oriented device, shown for the sake of example as ATM switches AS, BS, CS, DS,
and ES respectively. It is naturally possible for the present invention to be
applied to
hybrid networks in which connection-less devices and/or connection-oriented
devices and/or combinations of connection-less and connection-oriented devices
are
present.
The routers and switches are interconnected by links L1, L2, L3, L4 and L~.
Each
node A-E has a route determining means, for example in the form of a routing
table,
resp. RTE,, RTs, RTE, RTD, RTE which contains route information means, for
example in the form of route information entries E~,_B, EA_c, EA-p, Ea.-E,
etc. to Ex_Y
(where X is the source and Y is the destination node) showing how packets are
to be
routed from the resp. node to the other nodes in the network. These entries in
the
route tables are built up from route cost identifying means, in a manner which
is
known from the prior art, for example in the form of distance vectors, which
each
node transmits to its neighbouring nodes in the network, and which will not be
described in detail here. As an example, the route table for node A, RTA,
contains
information on how to send information packets from node A to node B, from
node
A to node C, from node A to node D and from node A to node E. Note that there
are
several ways that node A can send packets to node E, i.e. via link Ll, L3, L4,
L~ or
via links L2, L4, L5. Normally node A would send packets to node E via links
L2,
L4, L5 as this gives the shortest and therefore "cheapest" route, (assuming
that the
cost of using a link is the same for all links in the network) thus the
distance EA-E
from source node A to destination node E would have a cost of 3. If link L2 is
broken then node A would use links L 1, L3, L4, LS instead and the distance
from
node A to node E would be increased to 4 and the route information entry would
be
chanced to reflect this.
CA 02294807 1999-12-30
WO 99/02009 PCT/SE98101314
Similarly node B has a distance to node E, EB_E, which is 3, if node 3 is
intact and
which rises to 4 if node 3 fails.
Far node D the distance to node E, Ep_E, is 1 unless link LS is broken in
which case
the distance becomes infinity - i.e. it becomes impossible to reach node E
from node
D.
The routers AR-ER use their routing tables to establish connections through
their
switches AS-ES as described previously. Thus in a normal situation router :~R
when
10 it wishes to send traffic to E requests a label from node CR, i.e. in the
case of ATM
a logical channel number, CLEa-c for the traffic to E. Packets destined for E
received by A will then be forwarded to C through that channel.
Router CR will ask D for a label, CLEc-d, for traffic for E and can then order
its
1~ switch CS to interconnect CLEa-c with CLEc-d thereby allowing the tragic
from A
to E to be handled by switch CS and thus bypassing, and saving resources in.
router
CR.
In the same way nodes X which are upstream of A for traffic towards E will ask
A
for a label CLEx-a which then allows AR to order its switch AS to interconnect
CLEx-a with CLEa-c.
These connections established as described above will follow the paths
determined
by the routing tables RTx in the routers. If some event causes these routers
to
2~ generate a loop then this will lead to a connection loop.
Consider, for example, what happens if there is a break in link L=1. This will
be
detected by router CR which will try to inform its neighbours, routers AR and
BR,
that its distance to D and E is infinite. If, for any reason, this message to
B is lost
then AR will. believe that it can reach D via B at a cost of 3 and AR will
inform C of
this. This leads to a routing loop.
CA 02294807 1999-12-30
WO 99/02009 PCT/SE98/01314
11
Previous to this event, A has a channel CLEa-c to C for the traffic towards E,
and B
has a corresponding channel CLEb-c for its traffic towards E.
As a result of this event node A will release its channel to C and will
instead ask B
for a channel to B, CLEa-b for its traffic towards E. BS will interconnect
that with
the existing channel CLEb-c. C will ask A for a channel CLEc-a for its traffic
towards E. Router AR will order switch AS to interconnect CLEc-a with CLEa-b
and router CR will order switch CS to interconnect CLEb-c with CLEc-a, thus
forming a loop connection. As long as the loop persists, all packets towards E
will
circulate in the loop and cause a waste of links and switch resources and
eventually
lead to problems such as overflows in switch buffers and the like.
The present invention reduces this problem of wasted resources by providing a
l~ loop-detection means. In the preferred embodiment of the invention shown in
figure
2 the loop-detection means comprises a specially modified maintenance loop-
back
cell 20 which is produced and transmitted by a switch whenever it establishes
a
communication channel to another switch. Cell 20 has a header 18 and a payload
19. This loop detection cell 20 has the originating switch identified both in
the
source field 21 as the source as well as in the turning point field 22. This
cell 20 can
also have a loop-back indicator field 23 which shows if the cell has been
looped
back. Thus if switch AS is to establish communication with switch ES it
produces a
loop detection cell 20 in which the cell will contain AS as the source and AS
as the
turning point. This cell 20 is then sent on the route which should lead to
switch ES
and normally it should never come back to switch AS. If switch AS subsequently
receives back any cell which contains AS in both source and turning point
fields
(21, resp. 22) and with the loop-back indicator 23, if present, showing that
the cell
has not been looped back then it means that a loop has been folined. The
source can
also be identified by some other source field, for example, a correlation tag
24 as
specified in the ITU-T 610 specification. Switch AS can then take appropriate
action to prevent the loop being used and/or to break the loop and/or send an
alarm
CA 02294807 1999-12-30
WO 99/02009 PCT/SE98/01314
12
out of the network. In this way a loop can be detected in the time it takes
the Ioop-
detection cell to hop round the loop in the newly established route. Generally
it can
be considered that loops contain only a few nodes and lima. Thus the time that
a
loop detection cell takes to hop around the loop generally will be short and a
loop
will be detected quickly in a method according to the invention.
If there is no loop then the loop-detecting cell will continue to the
destination node
and be discarded, or possibly looped back with the loop-back indicator changed
to
'looped'.
If there is a loop but the loop-detecting cell is lost or expires before
returning to the
switch which produced it then the loop will be removed in due time in the
normal
way.
In this preferred embodiment of the method according to the invention the
switch
which produces the loop-detecting cell assumes that there will not be any
loops
present on the route and forwards packets of information on the route after
sending
the loop-detecting cell. This avoids delaying the packets of information but
can lead
to some packets being lost if there is indeed a loop. The number of packets
lost will,
however, owing to the more rapid loop detection enabled by use of a loop-
detection
cell, be less than the number which would have been lost anyway if no loop-
detection cell had been sent. Thus this embodiment leads to an improved
transmission perfolinance and no signal delay.
In a second embodiment of the method according to the invention the switch
which
produces the loop-detecting cell assumes that there is a loop present on the
route. In
this case it has a timer which is set to expire a predetermined time interval
after the
loop-detection cell has been sent on the alternate route. The length of the
timer is
chosen to correspond to an appropriate maximum loop length. Such a maximum
length could, for example, be chosen to correspond to the time which a packet
would take to hop around a loop of an arbitrary number of lima, or could be a
set
CA 02294807 1999-12-30
WO 99/02009 PCT/SE98/01314
I3
number of transmission periods. Packets with a destination on the route are
stored
until the end of the timer period. If the loop-detection cell has not yet
returned to the
switch then it is assumed that there is no loop present and the stored packets
of
information are transmitted on the route. This embodiment leads to more
improved
transmission quality as no packets of information will be lost in the loop at
the cost
of introducing a delay into the transmission of one or more packets of
information.
The choice of which embodiment of the invention to use naturally depends on
the
type of information in the data packets - a delay may be acceptable in a data
transmission which however cannot accept the loss of a few packets of
information
without suffering a discernible loss of quality, while a telephony
conversation may
be able to accept a loss of quality but not a transmission delay. It is
possible for a
node or switch to determine which embodiment to use for each packet it
receives:
some being transmitted immediately while others are delayed.
In a third embodiment of the present invention, not shown, the loop detection
cell is
produced at pre-programmed or predetermined intervals.
In a fourth embodiment of the present invention, not shown, the loop detection
cell
is not produced each time a route is established but after a route has been
established a pre-programmed or predetermined number of times.
The invention is naturally riot limited to networks having only S nodes and 5
links
but is adaptable to networks of any size.
2~
While the inventive concept has been illustrated by the example of a
connection-less
network superimposed on a connection-oriented network, it is of course
conceivable
to use the present invention in purely connection-oriented networks as well as
in
networks comprising a connection-oriented network or switch.
CA 02294807 1999-12-30
WO 99/02009 PCT/SE98/OI314
I4
The invention is not limited to loop-detecting means based on a loop-back cell
but
can use any other cell which can be suitably designed or modified to inform an
originating device that a loop exists.
