AU781148B2 - Method for evaluating routes in a communications network - Google Patents

Description

GR 99 P 1786 Description Method for assessment of routes in a communications network Communications networks are normally either in the form of packet-oriented networks or line-oriented networks.

In this case, packet-oriented networks are more suitable for transmitting information without any realtime nature, such as data, e-mails or files, while line-oriented networks are highly suitable for transmitting information with a real-time nature, such as voice or moving images. However, as line-oriented and packet-oriented networks converge, voice and moving-image information is also increasingly being transmitted in packet-oriented networks. Examples of packet-oriented networks are the Internet or ATM Asynchronous Transfer Mode) with the expression ATM also occasionally being used as a synonym for B-ISDN Broadband Integrated Services Digital Network). The packet-oriented network technology will be explained in more detail in the following text using the example of

ATM.

A characteristic feature of packet-oriented networks is the packet-oriented transmission of information. In ATM networks, the information is in this case, for example, split into packets of equal length also referred to as "ATM cells" which have a cell-header comprising bytes, and an information section (payload) comprising 48 bytes. In this case, the individual cells are allocated by the cell headers to specific information streams also referred to as "virtual connections". In contrast to, for example, a line-oriented TDMA method, in which timeslots are allocated from the start to different types of data traffic, the information GR 99 P 1786 la streams that arrive at an ATM interface are segmented into the said 53-byte cells, and these cells are then sent onward sequentially in the sequence GR 99 P 1786 2in which they were produced. The multiplexing method used for TDMA is also referred to as "static multiplexing", while that used for ATM is referred to as "statistical multiplexing". Owing to the flexibility of statistical multiplexing, the information streams in the case of ATM may have any desired data rates, while the data rate for the individual information streams also referred to as "connections" when using static multiplexing is fixed for example at 64 kbps in the case of ISDN owing to the fixed association between the timeslots and the information streams.

As a consequence of this difference, the routing of a requested connection in packet-oriented networks is dependent on the available capacity remaining on a route while, in line-oriented networks, it is in principle independent of the load level of the individual transmission paths. For example, on a route in a line-oriented network along which, for example, connections can be carried, using a TDM method, in fixed allocated timeslots each having a capacity of 64 kbps, a further connection can also invariably be set up when 29 connections have already been set up, since the further connection does not require a higher data rate than the remaining capacity of 64 kbps that is still available, since its data rate is constant.

However, only connections for which a data rate of less than 30 Mbps has been requested can be set up along a route in a packet-oriented network with an assumed remaining capacity of 30 Mbps. Connections with a higher data rate are, however, rejected. If any alternative routes exist, they can be set up by way of a substitute along an alternative route with sufficient remaining capacity. However, renewed routing is required in order to determine an alternative route.

Various routing methods are known by means of which it is possible to determine routes in networks. One option GR 99 P 1786 2a is referred to as "source routing", in which the complete route GR 99 P 1786 -3to a destination switching node is determined, starting from an initial switching node. For ATM networks, for example, the ATM forum has demanded source routing for the purposes of the PNNI Private Network-Network Interface) Specification. In this case, the route is determined by the initial switching node and then, when setting up the connection, the calculated route is transmitted to the switching nodes along the route, by signaling. A further option is referred to as "Hop-by- Hop routing" in which each switching node along a route recalculates the rest of the route, or the next section of the route. This method is used, for example, in the Internet or in ATM networks without source routing.

What are referred to as flooding methods have been proposed in order to exclude from the routing process those routes which use overloaded or interrupted transmission paths. In this case, all the switching nodes measure the traffic levels of the transmission paths connected to them at defined times, and pass this information on to all the other switching nodes within a group. This passing on of information is referred to as "flooding". Flooding can additionally also be carried out when the traffic levels on the transmission paths change significantly for example when the actual load level on a transmission path with a total capacity of 150 Mbps differs by more than 10 Mbps from the last load level passed on. For example, the PNNI Specification proposes that methods be used in ATM networks which provide a routing algorithm with the respective traffic levels measured most recently in the switching nodes in the ATM network for those transmission paths which are directly connected to them. In the context of PNNI, reference should also be made to U. Gremmelmaier, J. Pischner, M. Winter and P.

Jocher, "Performance Evaluation of the PNNI Routing Protocol using an Emulation Tool", ISS 97 XVI World Telecom Congress Proceedings, pp 401 408.

GR 99 P 1786 4 Routing in line-oriented, public telephone networks is known. In this case, the routing process is normally carried out in a number of steps, since these networks are normally hierarchically constructed since there are generally a large number of switching nodes. In a first step, connections in these networks are routed from an initial switching node on a lower hierarchical level to a switching node on the uppermost hierarchical level and then, in a second step, they are routed within the uppermost hierarchy level to a switching node which represents the connection destination before, finally, being routed in a third step to the destination switching node in a lower hierarchy level. In this case, the first and third steps generally make use of fixed selected routes or, for example if these are interrupted, fixed set alternative routes, while the second step frequently requires only a selection of the transmission path between the two affected switching nodes in the uppermost hierarchy level, since the switching nodes in the uppermost level are virtually completely networked with one another. However, Signaling procedure No. 7, which has been standardized for line-oriented telephone networks, does not support source routing, that is to say the initial switching node cannot pass on a route which it calculated. In consequence, the switching nodes along the route do not know the route that has already been traveled over either, so that, when using this routing method, it is possible for loops to occur in the routes in network, for example the Internet, which are not hierarchically structured and/or are only partially networked.

German Patent DE 441356 discloses a dynamic routing method for routing in packet-oriented networks, in which blockages in transmission paths are detected, and GR 99 P 1786 4a the load level on the transmission paths is determined from the frequency of these blockages. The probability of the transmission paths being occupied can be calculated off-line, from destination traffic data, by the use of a routing management GR 99 P 1786 5 processor. The "Forward Looking Routing" algorithum as defined by K. R. Krishnan, T. J. Ott in Forward-Looking Routing, A New State-Dependent Routing Scheme, Teletraffic Science for New Cost-Effective Systems, Networks and Services, ITC-12 (1989) is suitable, for example, for such a calculation. However, this method considers only connections with an identical, constant bandwidth, such as those which are typical for conventional telephone connections in line-switching networks, that is to say the bandwidth for one connection is, for example, 64 kbps. For packetoriented networks such as ATM networks (Asynchronous Transfer Mode), on the other hand, a constant bit rate is an exceptional situation, since connections can be made in accordance with the subscribers' connection requirements with different bandwidths, which can vary with time. In addition to the desired bandwidth, for example 1 Mbps, connection requests from subscribers often also contain information relating to the required connection quality.

The invention is based on the object of improving the routing for packet-oriented communications networks.

The object is achieved by the features of patent claim 1.

The major aspect of the invention is the assessment of routes in a communications network which comprises switching nodes and transmission paths and is, in particular, packet-oriented and possible connectionoriented, and in which link costs which are assigned to the transmission paths are used to form amended link costs, and the routes are assessed as a function of the amended link costs. The major advantage of the invention is that different assessments of the routes can be obtained by different amendments to the originally assigned link costs. It is thus advantageously possible to control the assessments of GR 99 P 1786 5a the routes by the nature of the amendments to the original link cost, that is to say without changing the assessment itself.

R Q n 17 C 6 According to one refinement of the method according to the invention, the amended link costs are intended to be formed by addition of randomly selected real numbers to the link costs, with the absolute magnitude of the real numbers being less than a maximum number, which is selected to be sufficiently small that the link costs are not substantially changed claim 2. This advantageously generally results in minimally different route costs for routes which would have identical route costs if the original link costs had not been amended.

However, a route with significantly higher route costs than the optimum route costs has an optimum route, even if the original link costs are amended, [lacuna] considerably higher route costs than the optimum route costs then determined. Minimal differentiation between the route costs is thus advantageously achieved only within a group of routes whose route costs with unamended link costs are identical, while the allocation of the routes to such groups of routes with the same route costs, and the sequence of the groups themselves, remain unchanged.

According to one development of the method according to the invention, an optimum route, which is defined as a function of the amended link costs, is determined by means of a deterministic routing algorithm claim 3.

This has the advantage that a deterministic routing algorithm is in general less complex than a nondeterministic routing algorithm, and can thus be processed more efficiently.

According to one refinement of the method according to the invention, the deterministic routing algorithm is in the form of a Dijkstra algorithm claim 4. Proven standard software can thus advantageously be used, since the Dijkstra algorithm has actually been known GR 99 P 1786 6a since 1959, and highly efficient and technically proven implementations are available. The optimum route also advantageously has minimum route costs.

GR 99 P 1786 7 According to one variant of the method according to the invention, the communications network assesses relevant routes only for one requested connection claim This advantageously reduces the number of routes to be assessed and, in consequence, the processing time for assessment of the routes.

According to one development of the method according to the invention, the routes are assessed for each request for a connection claim 6. The amendment of the link costs, in particular the random selection of the real numbers, advantageously means that, if there are a number of optimum routes which would have identical minimum route costs if the link costs were not amended, one of these routes is optionally selected on the requested connection for each connection request, even though a deterministic routing algorithm, that is to say a routing algorithm which determines the same optimum route without amending the link costs in each case, is used to select the route that is optimum for the connection. This advantageously considerably reduces the statistically average probability of blocking, since the load levels on the transmission paths are more uniform than if the connections were all set up along the same route.

According to one application of the method according to the invention to a method for setting up a connection in a communications network which comprises switching nodes and transmission paths, the connection is set up along a route which is optimum for this connection claim 7. The assessment of the routes is thus advantageously used for the selection of a route. In particular, the randomly controlled amendment of the link costs when there are a number of comparable routes leaves the question open as to which of the routes is GR 99 P 1786 7a optimum for that connection. The connections are therefore not automatically set up via the same route, with the load being shared between D 9900 P 1786 8 equivalent routes. This considerably reduces the blocking rates for connections.

According to one refinement of the application of the method according to the invention the route which is optimum for the connection is determined by that switching node which processes the request for the connection claim 8. This has the advantage that the request can be processed very efficiently, since no messages are required between the node processing request and a further node carrying out the routing.

According to one development of the application of the method according to the invention, the optimum route for the requested connection is reported to all the switching nodes along the optimum route for the requested connection while the connection is being set up claim 9. The invention can thus advantageously be used in networks with source routing.

The method according to the invention will be explained in more detail in the following text with reference to a number of figures, in which: Figure 1 uses a block diagram to show a communications network with switching nodes and transmission paths, Figure 2 uses a table to show all the routes which originate from the switching node KI to the other switching nodes in the communications network illustrated in Figure 1, Figure 3a uses a table to show the formation, according to the invention, of amended link costs from link costs assigned to the transmission paths, and GR 99 P 1786 8a Figure 3b uses a table to show the assessment, according to the invention, of the routes listed in Figure 2, as a function of the amended link costs.

GR 99 P 1786 9 Figure 1 shows a communications network KN with four switching nodes Ki, 1 i 4. The switching node K 1 is connected to the switching node K 2 by means of a transmission path U1 2 and to the switching node K 3 by means of a transmission path U1 3 the switching node K 4 is connected to the switching node K 2 by means of a transmission path U 24 and the switching node K 3 by means of a transmission path U 34 a transmission path

U

14 which is represented by a dotted line in the drawing, is also provided between the switching nodes

K

1 and K 4 This is intended to indicate that transmission paths U for example the transmission path U1 4 can be temporarily overloaded and/or interrupted. Each of the switching nodes Ki has associated routing information RINF (Ki) An arrow pointing to the switching node K 1 also indicates that a request VA for a connection V to a connection destination VZ for example the switching node K 4 is transmitted to this switching node K 1 Figure 2 shows the routing information RINF (K 1 associated with the switching node K 1 This contains, for example, the routes Rij which lead from the switching node K 1 to the switching nodes Kj, 2 j 4, and their route cost RK (RIj). The routes Rj are in this case defined as one of possibly a number of different options for passing from the switching node

K

1 including the transmission nodes Kj, 2 j 4 and the transmission paths U, to the switching destination VZ in the example the switching node K 4 In the example, including the optional transmission path U 14 three routes Rlj-k, 1 k in each case pass from the switching node K 1 to the switching nodes Kj, to be precise originating from the switching node K 1 on the route R 12 -1 directly to the switching node K 2 on the route R 12 2 via the switching nodes K 3 and K 4 to the GR 99 P 1.786 9a switching node K 2 and on the route R 1 2- 3 via the switching node K 4 to the switching node K 2 the route

R

1 3- 1 via the switching nodes K 2 and K 4 the route R 1 3-2 directly rl nA T 1 7 0C 10 and the route R 1 3- 3 via the switching node K 4 to the switching node K 3 the route R 1 4- 1 via the switching node

K

2 the route R 1 4- 2 via the switching node K 3 and the route R 1 4- 2 directly to the switching node K 4 The route costs RK (Rlj-k) of the route Rlj-k are in each case obtained from the sum of the amended link costs L for each of the transmission paths U used by the routes. In this example, for simplicity reason, it is assumed that all the transmission paths U are bi-directional and that the link costs LK are independent of the direction of the connection.

Figure 3a shows how link cost LK assigned to the transmission paths U can be used to form amended link costs L as a function of randomly selected numbers EPS.

By way of example, let us assume that the link costs LK (Uij) 1, the number EPS (U 12 0.003, the number EPS

(U

13 0.005, the number EPS (U 14 0.012, the number EPS (U 24 0,002, the number EPS (U 34 0.007 and the amended link costs L (Uij) LK (Uij) EPS (Uij) are defined for the transmission paths Uij, ij 12, 13, 14, 24, 34. It should be noted that the term "link costs" should not be interpreted literally in the sense of "costs". Any desired values which are relevant for the transmission paths may be used for form the link costs LK, such as traffic levels or Quality of Service values. By choosing all the link costs LK to be equal to 1, and when using a Dijkstra algorithm, the routes which have optimum route costs RK are those whose connection destination VZ is reached via as few switching nodes K as possible such optimization metrics are also referred to as "least hops" in the specialist world. The preferred routes R are thus those which reach their connection destination VZ with the shortest delay times, since the total delay time in a route R is normally governed essentially by the sum of GR 99 P 1786 10a the delay times for passing through the switching nodes K, provided the transmission paths U are terrestrial, and do pass via satellites. The maximum absolute magnitude of the numbers EPS (Uij), which is 0.012, is so small that the amended GR. 99 P 17R8 11 link costs do not differ significantly from the link costs LK so that the least hops metrics are still valid when carrying out the method according to the invention.

Figure 3b lists the route costs RK for the routes Rlj-k listed in Figure 2, which have been determined in accordance with the formula quoted in Figure 2 for determining the route costs RK, based on the amended link costs quoted in Figure 3a. If the optional transmission path U 14 is ignored, the route R 14 -1 is the optimum route RMIN with the lowest route costs RK of all the routes R. The route R 14 -1 is at the same time the optimum connection route RMIN(V) for the requested connection V to the switching node K 4 since, although it has the same number of hops as the route R 14 its route costs RK are, however, marginally lower. Taking account of the optional transmission path U 14 the route

R

12 -1 is the optimum route RMIN, with the lowest route costs RK of all the routes R. In this case, the route

R

14 3 is the optimum-connection route RMIN(V) for the requested connection V to the switching node K 4 since it has one hop fewer than the routes R 14 1 and R 14 2 that is to say the number EPS (U 14 which is relevant to the route R 14 3 admittedly has by far the greatest absolute value compared to all the numbers EPS, but this does not substantially change the link costs LK, so that the least hops optimization metrics are still valid.

For the exemplary embodiment, it is assumed that switching node K 1 originates a request VA to set up a connection V to the connection destination VZ. This connection destination VZ is assumed to be the switching node K 4 and the connection V is thus assumed to be the connection V 14 In order to restrict the search area, the switching node K 1 assesses only those routes R (V 14 which are relevant for this connection GR( 99 D 178C lla

V

1 4, that is to say the routes R 1 4- 1

R

1 4- 2 and R 1 4- 3 The numbers EPS are formed for these routes by using a random number generator, and the amended link costs L are then CD 00 0 17og 12 formed. These amended link costs L are used, as the basis for a program for example, which carries out the deterministic Dijkstra algorithm to determine the optimum-connection route RMIN (V 14 that is to say the route R 14 3 when the possibly overloaded and/or interrupted transmission path U 14 is taken into account, otherwise the route R 14 -1 If the state of the transmission path U 14 is known, for example by the state being reported in the network by means of a flooding method, this is considered, for example, by excluding the transmission path U1 4 from the routing process for the duration of the overloading and/or interruption, for example by assigning it very high link costs LK in comparison to the link costs LK of the transmission paths U which are not overloaded and/or interrupted.

Following the routing process, the requested connection V1 4 is set up along the optimum-connection route RMIN

(V

14 Particularly noted advantages are claimed when using the invention in connection-oriented networks with source routing, for example ATM networks. In networks such as these, a largely uniform distribution of requested connections over a number of optimumconnection routes RMIN can be achieved, for example, statistically on average, provided the numbers EPS are formed once again regularly, for example for each requested connection V. If the numbers EPS are in this case formed, for example, using a random number generator, this therefore results in different route costs RK for the relevant routes R on each occasion. In the exemplary embodiment, the routes R 14 -1 and R 14 2 have the route costs RK (R 14 2.005 and RK

(R

14 2 2.019. The route costs for the next requested connection V 14 could be, for example, RK (R 14 2.023 and RK (R 14 2 2.004, with the route R 14 2 in consequence being determined as the optimum-connection GR 99 P 1786 12a route RMIN (V 14 If the link costs LK were not amended, both routes R 14

R

1 4- 2 would have identical route costs RK (R 1 4- 1 RK (R 1 4- 2 2. In this case, owing to the deterministic behavior of the routing algorithm, the same optimum-connection route RMIN (V 14 would be determined for each GR 99 P 1786 13 requested connection V, for example the route R 14 No connections would be set up along the route R 14 2 until the route R 14 -1 was completely full. A major advantage of this largely uniform distribution is that, on average, it results in the rejection probability for a number of connections, whose requested data rate generally varies randomly, being reduced significantly.

The rejection probability is advantageously reduced even further by using a flooding method, for example the PNNI method, in the network, in order to exclude overloaded and/or interrupted transmission paths from routing, at least during the time period when the route is overloaded and/or interrupted.

It should be mentioned that the invention can, of course, also be applied to any desired communications networks KN, in particular connectionless communications networks KN such as the packet-oriented Internet. In the Internet for example, each individual packet is transmitted along a packet-specific route R, that is to say each packet's route in a virtual connection V is independent of the routes R of the previous and subsequent packets within the same virtual connection V; the switching nodes K, which, for example, are in the form of Internet Routers, in this case in each case determine only the next switching node K for each packet in a virtual connection V referred to as a "hop" in the specialist world. In accordance with the method according to the invention, each router distributes possibly successive packets, which are associated with the same virtual connection V, over a number of transmission paths U. The transmission paths U which are connected to one router are in this case advantageously uniformly loaded, on average. In this case, for example, different delay times for the individual packets can lead to changes in the original sequence of the packets. In this case, the original sequence of the packets in the virtual GR 99 P 1786 13a connection V is reproduced in the receiver using a higher protocol layer.

fG 00 D 17Q 14 A number of methods are known for this, for example the Transport Control Protocol TCP.

Claims (6)

1. A method for assessing routes in a communication network (KN) consisting of switching nodes and transmission paths having assigned link costs the method comprising the steps of: forming amended link costs for the transmission paths based upon the link costs and assessing the routes based upon the amended link costs wherein the assessment is controlled by the amendments made to the link costs (LK) to form amended link costs rather than by changing the assessment itself. S

2. The method according to claim 1, wherein the amended link costs are formed by addition of randomly selected real numbers (EPS) to the link costs (LK), wherein the absolute value of the real numbers is smaller than a greatest number which is chosen to be sufficiently small such that the link costs (LK) are not S 20 substantially modified.

3. The method according to any one of claims 1 or 2, wherein an optimal route (RMIN) based upon the amended link costs is determined with the aid of a deterministic routing algorithm.

4. The method according to claim 3, wherein the deterministic routing algorithm is a Dijkstra algorithm. The method according to any one of the preceding claims, wherein only routes relevant to the communication network (KN) are assessed for a requested connection

6. The method according to claim 5, wherein the assessment of the routes is based upon each request for a connection [R.LI R IE] I 123 doc cdg

16- 7. The method according to any one of claims 5 or 6, wherein the connection is established via a route (RMIN(V)) which is optimal for this connection 8. The method according to claim 7, wherein the route (RMIN(V)) which is optimal for the connection is determined by the switching node (K 1 processing the request (VA) for the connection 9. The method according to any one of claims 7 or 8, wherein, while the connection is being established, the route is communicated to all switching nodes along the route (RMIN(V)) which is optimal for the requested connection 10. A computer program product, comprising computer software for performing the method according to any one of claims 1 to 9, using at least one computer processor. o° 15 11. A switching node comprising means for performing the method according to any one of claims 1 to 9. o 12. A communication network (KN) comprising devices and/or computer program products performing the method according to any one of claims 1 to 9. DATED this third Day of March, 2005 Siemens Aktiengesellschaft Patent Attorneys for the Applicant SPRUSON FERGUSON K[ \LEIUBEI4123 doc cdg