Note: Descriptions are shown in the official language in which they were submitted.
CA 02607338 2007-11-01
PCT/EP2006/061865 - 1 -
2004P19635WOUS
Description
Routing method for optimizing link capacity and increasing
availability
The invention relates to a routing method for optimizing link
capacity and increasing availability in a packet-based
communication network comprising nodes and links.
According to definition, a communication network is a resource
which comprises network nodes which are remote from one another
and which are connected to one another via lines or so-called
links. A network node, or also node is a station in the
communication network at which at least two or more links come
together. In addition, these nodes can also be access points to
the communication network and can thus be used as data source
or destination for data. The transmission of data from a data
source to a destination node for data in a communication
network is called data traffic. The connection between two
network nodes, which is permanent in most cases, is called a
link. The data are transported between the nodes via these
linkso
In a communication network built up of nodes and links, two
types are distinguished on the basis of the switching
technology: circuit-switched and packet-based communication
networks.
In the circuit-switched communication network such as, for
example, telecommunication networks, a continuous channel is
switched for the entire duration of a data transport.
In the packet-based communication network such as, for example,
X.25 networks or the Internet, no permanent continuous physical
channel is made available for a connection for the data traffic
but the data are divided into small,
CA 02607338 2007-11-01
PCT/EP2006/061865 - 2 -
2004P19635WOUS
individual packets which also have different lengths in some
cases. Into these packets, supplementary information for
identifying data sources and destination are packed. The
supplementary information of these packets is then analyzed by
the network nodes through which they pass and the packets are
forwarded to the destination by the respective network node.
The analysis of this supplementary information in the
individual network nodes and the corresponding forwarding of
the individual packets is also called routing or routing
method. A network node in which such a routing method is
implemented is also called a router.
In conventional packet-based communication networks such as,
for example, the Internet, an optimum path for transmitting the
data packets - that is to say the data traffic - is usually
determined during routing with the aid of so-called metricso
Metrics are understood to be fixed routing criteria for which
information relating to the paths is stored in the individual
network nodes. This information is continuously adapted to the
path determined, adjacent network nodes being informed about
the links existing in the other adjacent network nodes, and
their status.
In a node, an address for the node is usually stored in a so-
called routing table for a particular destination which is
given by a destination address of the packet. A network node
which receives a data packet then evaluates the destination
address information integrated in the packet, determines the
address of the associated next network node by means of the
routing table and forwards the packet to this node in
accordance with the metrics via a link. In this manner, the
packets are switched from node to node, as it were, by the
communication network from the data source to the destination,
the links between the nodes being loaded in accordance with the
number of data packets which are transmitted via them.
CA 02607338 2007-11-01
PCT/EP2006/061865 - 3 -
2004P19635WOUS
Large packet-based communication networks such as, for example,
the Internet, are frequently subdivided into subareas which are
again packet-based communication networks. In the Internet,
which uses both the Internet Protocol and the Transmission
Control Protocol as basic protocol, individual, strictly
delimited addressable areas can be defined by a special system.
Such an area is called a domain and can be addressed
selectively. If then a data packet is switched within such a
defined area - that is to say within a domain - from node to
node through the domain from the data source to the destination
which can lie within or at the boundaries of the domain, this
is also called intra-domain routing.
In most cases, packet-based subnetworks or domains are operated
by so-called network operators who, on the one hand, are
interested in distributing the entire data traffic in their
communication network in such a manner that the capacities of
the connections between the nodes, that is to say of the links,
are optimally loaded. On the other hand, it is of importance to
the network operator that a high availability of their
communication network and its services exists in spite of
errors on individual links.
The essential routing methods for intra-domain routing in
packet-based networks such as, for example, the Internet,
operate on the basis of metrics according to which the shortest
path at the least cost is sought for the transmission of data
packets. Such a routing method known from the prior art is for
example, the OSPF (Open Shortest Path First) protocol Version
2, which, apart from routing, also carries out the processing
and forwarding of the routing information. A detailed
description of the OSPF protocol can also be found in the
document J.Moy, 'OSPF Version 2v , RFC 2328, under
httpo//www.ietf.org/rfc/rfc2328etxt, which was published by the
Internet Engineering Task Force (IETF).
CA 02607338 2007-11-01
PCT/EP2006/061865 - 4 -
2004P19635WOUS
A further intra-domain routing method known from the prior art
in packet-based communication networks is represented by the
IS-IS (Intermediate System Intermediate System) protocol which
was defined in the document ReCallon "Use of OSI IS-IS for
Routing in TCP/IP and Dual Environment", RFC 1195 under
httpe//www,ietfeorg/rfc/rfcll95etxt, published by the Internet
Engineering Task Force (IETF) and has similarities with the
OSPF protocol.
In case of faults in a link or a node, the neighbors of the
failed element and the other nodes in the communication network
are informed in both protocols - the OSPF protocol and the IS-
IS protocol - whereupon the shortest path for the data traffic
must be recalculated again by each node. The selection of the
path is determined by the topology of the communication network
and by the metrics used. In the routing protocols mentioned,
the metrics are in most cases selected in such a manner that
the data traffic is approximately optimally distributed to the
links and thus an optimum link capacity is achieved. However,
both routing methods have the disadvantage that in the case of
a fault, the information about a failure must first be
distributed in the entire network and then a new, shortest path
must be determined throughout the network, as a result of which
the availability becomes less due to the propagation times for
the fault reporting. Although it is possible, in communication
networks having propagation times which are not too long, to
achieve a fault reaction time - and thus restriction in
availability - which is tolerable for many applications with,
eog, OPSF routing in combination with accelerated fault
detection and accelerated algorithms for path finding, these
fault reaction times are not sufficient for applications having
extremely high availability and real-time requirements such as,
for example, telemedical operations, remote controls for robots
etco or for communication networks having extremely long link
propagation times such as, e,g, satellite links.
CA 02607338 2007-11-01
PCT/EP2006/061865 - 5 -
2004P19635W0US
For this reason, a routing method with high reliability for
intra-domain routing in packet-based networks was developed as
part of the key component for the mobile Internet of the Next
Generation (or KING) project, by which method an alternative
path is offered in the case of a fault. The so-called
Outdegree2 (02) routing, which is described in the document
G. Schollmeier, J. Charzinski et ale, "Improving the Resilience
in IP Networks" for the High Performance Switching and Routing
(HPSR) Workshop 2003 in June 2003 in Turin, Italy, allocates to
each node in a communication network two next nodes for each
data destination. In the case of a fault, therefore, there is
always still one path for the transmission of data packets to
the data destination so that a maximum reliability with
shortest possible response time is achieved by this approach.
Investigations as part of the KING project have found, however,
that the 02 routing method achieves a poorer, higher, link
loading because of the detours partially necessary in the data
transmission path. Although the 02 routing method achieves very
high availability, it has the disadvantage of poor link
capacity.
The present invention is based on the object, therefore, of
specifying a routing method by means of which both optimum link
capacity and high availability for the data traffic are
achieved.
According to the invention, the object is achieved by means of
a routing method for optimizing link capacity and increasing
availability in a packet-based communication network comprising
nodes and links, wherein the data traffic to be routed is
allocated to one of at least two priority levels, after which
the data traffic having a high priority level is routed first,
after that the data traffic having a low priority level is
routed and in the process, the routing methods used, known per
se are adapted to the requirements of the respective data
traffic.
CA 02607338 2007-11-01
PCT/EP2006/061865 - 6 -
2004P19635W0US
In particular the advantages achieved by means of the
invention consist in that both optimum link capacity and high
reliability and rapid fault response for the corresponding data
traffic can be achieved at the same time. It is made possible
that the data traffic to which a high priority level has been
allocated such as, for example, data traffic with real-time
requirements, is forwarded first in the communication network
and only then the data traffic having a low priority level is
distributed to the links.
Furthermore, it is recommended to use an Outdegree2 routing
method known per se, for routing the data traffic having a high
priority level because this known routing method offers maximum
reliability with shortest possible response time for the data
traffic having a high priority level.
In a further embodiment of the invention, it is advantageous
if, for routing the data traffic having a low priority level,
routing methods for intra-domain routing, known per se, are
used because these known routing methods in most cases
determine the shortest path in accordance with the respective
metrics for the data transmission. This path determination,
therefore, achieves optimum link capacity for the data traffic
having a low priority level. Above all, it is also achieved
that the data traffic having the low priority level is placed
onto links which are loaded little by data traffic having a
high priority level.
It is particularly advantageous if the Open Shortest Path First
protocol, known per se, is used as intra-domain routing
protocol for routing the data traffic having a low priority
level because this protocol is defined as Version 2 in the
Request for Comments (RFC) 2328 of the Internet Engineering
Task Force (IETF) and is used by various manufacturers of
routers.
CA 02607338 2007-11-01
PCT/EP2006/061865 - 7 -
2004P19635W0US
It is also advantageous if the Intermediate System Intermediate
System protocol, known per se, is used as intra-domain routing
protocol for routing the data traffic having a low priority
level. This routing protocol is defined by the Request for
Comments (RFC) 1195 of the Internet Engineering Task Force
(IETF) and is frequently used today as Interior Gateway
protocol - meaning for intra-network routing - and for load
distribution and by operators of large IP networks.
It is proposed that the respective reliability requirements are
utilized as criterion for allocating the data traffic to be
routed to one of at least two priority levels. The result is
that both traditional Internet services such as, e,g, World
Wide Web, E-mail etc, for which a lower reliability is
necessary, and highly available real-time services can be
offered in communication networks and processed with complex
routing methods.
It is also advantageous if the respective Quality-of-Service
requirements are utilized as criterion for allocating the data
traffic to be routed to one of at least two priority levels. By
utilizing the Quality-of-Service requirements, other factors
for determining the quality of a service which is offered in a
communication network are also utilized for allocating the data
traffic to be routed to a priority level. This is of particular
importance because Quality-of-Service can be defined
differently for different services within a communication
network.
A preferred development of the invention also provides that the
Internet Protocol is used as basic protocol for the data
traffic in the packet-based communication network because the
Internet Protocol is independent of the medium used and can
therefore be used both in local
CA 02607338 2007-11-01
PCT/EP2006/061865 - 8 -
2004P19635W0US
packet-based communication networks - so-called local area
networks - and in long-haul packet-based communication networks
- so-called wide area networks.
It is also advantageous if an optimization of the load
distribution, known per se, is carried out for the routing
method for routing the data traffic having a high priority
level as a result of which the reliability and the speed of the
data traffic is increased.
It is also advantageous if an optimization of the load
distribution, known per se, is carried out for the routing
method for routing the data traffic having a low priority level
as a result of which the reliability and the speed of the data
traffic is increased.
An optimization of the link cost metrics is preferably utilized
for optimizing the load distribution since this determines not
only short paths but also fast and cost-effective paths.
A preferred development of the invention also provides that
first the optimization for routing the data traffic having a
high priority level is carried out, then a remaining residual
capacity is calculated and for this the routing of the data
traffic having a low priority level is carried out because
optimum link capacity, high reliability and fast fault response
for data traffic of different priority levels can be achieved
by this means.
In the text which follows, the invention is explained in
greater detail in exemplary manner by referring to the attached
figure 1. Figure 1 shows the diagrammatic sequence of the
method according to the inventiona
CA 02607338 2007-11-01
PCT/EP2006/061865 - 9 -
2004P19635W0US
In the figure, four nodes X, Yl, Y2 and Z of a communication
network are shown, the destination node Z forming the
destination for the transmission of the data traffic within the
communication network. The other nodes X, Yl, Y2 are connected
via links L1, L2 in such a manner that the first link L1 leads
from the first node X to the further node Yl and the second
link L2 leads from the first node X to the further node Y2.
In a first step 1, the data traffic DV to be routed is marked
in accordance with its requirement for reliability and thus
allocated to a priority level PKn, PKe. The lower priority
level PKn identifies the data traffic DV having normal
reliability requirements. The higher priority level PKe marks
the data traffic DV having high reliability requirements.
If then the data traffic DV identified by a priority level PKn,
PKe reaches the first node X of the communication network in a
second step 2, the priority level PKn, PKe of the data traffic
DV is evaluated by the first node X in a third step 3. In the
first node X - as in all other nodes Y1, Y2 of the
communication network - two routing entries per destination
node Z are stored. One routing entry defines the path for the
routing of the data traffic DV having normal reliability
requirements, identified by the lower priority level PKn, to
the destination node Z, the shortest path for this data traffic
DV being determined on the basis of optimized metrics. The
other entry specifies the path for the data traffic DV having
high reliability requirement, identified by the higher priority
level PKe, to the destination node Z by means of 02 routing.
In a fourth step 4, the data traffic DV having the high
reliability requirement, which is marked by the
CA 02607338 2007-11-01
PCT/EP2006/061865 - 10 -
2004P19635W0US
priority level PKe, is now conducted via the first link L1 to
the further node Yl to the destination node Z in accordance
with the path specified by the 02 routing.
In a fifth step 5, the data traffic DV identified by the
priority level PKn is then transmitted along the shortest
paths, resulting from the optimized metrics used, via the
second link L2 to the further node Y2 to the destination node
Z.
As described, step 5 - the determination of the path on the
basis of optimized metrics - can be carried out after the path
selection for the 02 routing of the data traffic DV having high
reliability requirements. As an alternative, however, it is
also possible that step 5 is carried out jointly with the path
selection for the 02 routing.
