Method for balancing the data transfer load of a communication network and corresponding communication network

In contemporary, from a plurality of the link lines be networked nodes existing communication networks Data often transmitted within data packets. The data packets be it from a source network node from node to node to a destination network node transfer. Known transmission method of this kind are For example, the so-called. ATM method (asynchronous transfer mode), the so-called. MPLS method (multiprotocol label switching) and on the Internet Protocol (IP) -based ren.

For the transmission of data packets from a source node to a destination network node are usually several alternative Routes available. From these is for each to transmitted data packet or of related to each data packet stream Data packets each select an appropriate route. The choice depends in particular by the criterion that the data packets with the least possible delay and with as few packet losses to the destination network node to be transmitted. To optimize the data transfer performance the entire communication network should select moreover done in a manner that transmission bottlenecks, ie an overload of individual network nodes or link lines be avoided if possible. This can be done an appropriate distribution of the traffic load in the communication network be achieved. Here, however, gives the Problem, the route selection of the individual network nodes within the meaning a network inter-nodal distribution of traffic load coordinated.

From the IETF Internet Draft "OSPF Optimized Multipath (OSPF OMP)" C. Villamizar, dated February 1999, is a A method for data traffic distribution, in which to Vote the node load information from all network nodes be distributed via the communication network. there processed each network node of the other network nodes received load information to derive new load information to determine which are in turn distributed in the network. In general, the voting procedure converges after some Time to a state in which the in each network node present load information are consistent with each other. This then allows each network node each an autonomous decision a network node-specific load sharing to meeting that is optimized based on the total network. Before such optimized load distribution to be made can, but the convergence is only the relatively time-consuming voting procedure between all network nodes to be seen. In addition, due to any change in the Network topology, for example due to failure of a link line, a new convergence process.

In the IETF Internet Draft (IETF: Internet Engineering Task force) "draft-bumble-te-oct-00.txt" by Heinrich Hummel dated, of October 1999, it is proposed for distributing the Traffic load a central traffic-steering device use. Due to the central steering is the optimal distribution of traffic tuning all network nodes to one another is not required. The traffic-steering device transmits to each Network nodes of probabilities that for each destination network node indicate the probability that a respective to this destination network node leading route for below connection to be established is to be selected. At a subsequent connection is the to-use concrete Route then using a random according to the submitted Probability information selected. proves a fixed allocation of connections to routes However, particularly in permanent connections with fluctuating data rates as inflexible. Furthermore, requires constant mapping of connections to routes with frequent assembly and dismantling of connections an administrative burden for an individual Network nodes. This is particularly large, a plurality of subordinate communication networks interconnecting communications networks, such as large service provider networks, very expensive since many end-to-end connections between a potentially very large number of terminals to would manage.

Alternatively, could send data packets without considering a Compound belonging to the alternate routes be distributed to the destination network node. However, this causes the problem that the different forwarded data packets the destination network node generally not in their original Sending order arrive. A reconstruction of the original call-specific data packet stream is thus by the required waiting for each slower transmitted Data packet greatly retarded, particularly in Real-time applications often can not be tolerated.

It is an object of the present invention provide a method, with which the data traffic load in a communication network flexibly and with little effort, while largely Maintaining a connection-specific data packet sequence can be distributed. Another object is to a communication network for the realization of the invention specify method.

This object is achieved by a method with the features of claim 1 and a communication network with Features of patent claim 13.

For optimum network inter-nodal distribution of traffic load a communications network to be inventive when Process current data transmission capacity values for link lines and / or network nodes of the Communication network through a traffic-monitoring device determined. The data transfer capacity values preferably for all link cables determined and / or network node of the communication system, and give each their utilization, including their respective yet free transmission bandwidth on. From the determined data transfer capacity values is the traffic-monitoring device preferably for each node of the Communications network each have a network node-specific distribution information determined that to the network node in question is transmitted. One for einen'individuellen network nodes certain distribution information is for of this Network nodes reachable destination network notes the communication network respectively on, to be transmitted as to this destination network node Data packets on alternative to this destination network node leading routes are to be distributed. The on the individual Network node transmitted distribution information are matched that transmission bottlenecks throughout Communication network are largely avoided. A distributing the traffic load has over a energy, with at the data streams respectively over those route transfer of the largest remaining free transmission bandwidth be, the advantage that a Übertragungsengpaß not easy is transferred only to another route.

forms a distribution information receiving node depending on the distribution information a classification regulation, by the address information to be transmitted Data packets are divided into individual address classes. As the classification is based on address information applied can eg a source address of the data packet, a combination of Source address with one or more destination addresses of the data packet or indicative of an association with a connection, Information contained in the data packet are used. According to the distribution of information, the address information can For example, according Adreßintervallen, according to the values ​​of a applicable to a so-called address information. hash function or according to predefined bit combinations of address information are divided into address classes. The address classes are each an alternative to a respective destination network node assigned leading routes. To transmit a Data packet whose address information is extracted, the determined address class of the extracted address information and associated data packet over which the particular address class Route transmitted.

Extracting the address information and determining the associated Address class requires on the part of the network node in question only a small effort. Nevertheless, is characterized ensures that belonging to the same end-to-end connection Data packets usually have the same address information have, are transmitted via the same route. To this Example, changing the order of data packets, belong to the same end-to-end connection, on the way be for each destination network node largely avoided.

Only in the case of a change of classification regulation, for example due to network congestion changing, a existing end-to-end connection to a different route be diverted, whereby the data packet sequence shortly can be disturbed. Such short-term disturbances but are generally tolerable. When using compounds highly variable data rate is a redirect to a new route even often advantageous when connected in terms of a uniform utilization Network resources.

An elaborate management of assignments of all end-to-end connections to routes is the novel process not mandatory. This is particularly large, a connecting plurality of subordinate communication networks Kommun ikationsnetzen very advantageous because in such Cases, a very large number of end-to-end connections between terminals of all subordinate communications networks be managed.

Moreover, the invention is largely independent of whether the data packets in a connection-oriented communication network be transmitted or connectionless. This is particularly in communications networks having different hierarchical levels or heterogeneous communication networks, the data packets often in parts connection-oriented and at times connectionless forward, a significant advantage represent.

Advantageous embodiments of the invention are in the dependent Claims.

According to an advantageous embodiment of the invention can the data transfer capacity utilization values ​​using a routing protocol of the communication network, such as the routing protocol PNNI (private network to network interface) or the OSPF routing protocol (open shortest path first) preferably be determined at regular time intervals.

Using a routing protocol, the traffic-monitoring device required also for traffic shaping Strukturinformaticnen, for example over the course of all Routes of the communication network is obtained.

A data transmission capacity value can, for example, still free transmission bandwidth of each link line, the unused portion of the entire transmission bandwidth or specify the current bit rate of the link line. Further, the data transfer capacity utilization values ​​can connection-specific transmission priority specifically, leitwegspezifsich, source network node-specific and / or destination network node-specific be determined. The identification of such specific data transfer capacity values ​​permits highly differentiated distribution of the traffic load.

To determine the data transfer capacity utilization values ​​can by one or more, but preferably of all, Network nodes of the communications network link line-specific, leitwegspezifische, connection-specific and / or transmission priority specific Utilization information for the of the respective network node outgoing link lines, Routes and / or compounds for the traffic monitoring device are received.

From the data transmission capacity values ​​indicated above, specifically identified can through the traffic-monitoring device according to connection-specific, transmission priority specific leitwegspezifische, source network node-specific and / or destination network node-specific distribution information, preferably for all of the network nodes Communication network are determined.

According to an advantageous embodiment of the invention can for determining the distribution information previously determined determined data transfer capacity utilization values ​​and / or previously Distribution information is extrapolated in time. By Temporal Extrapolation distributing information to the at a later time to be expected Traffic load in an optimum way.

The extrapolated data transfer capacity values ​​or Distribution information can later with actual, to extrapolated time to compare determined values. Depending on the agreement reached, a be modified or omitted subsequent extrapolation or subsequently extrapolated values ​​correspondingly stronger are weighted or weaker.

According to a further advantageous embodiment of the invention may have a specific for a network node distribution information include share information, for each of the alternative Specify leading to a destination network node routes, what proportion of transmitted to this destination network node Data packets to be transmitted through the respective route. Here, a portion of the information to be provided to indicate how much of the data packets, for example, in an overload situation, discard.

With the share information may further include a random number generator are weighted with the aid of data packets to one of the Routes are allocated for transferring.

An embodiment of the invention is described below with reference to the drawing explained.

These respectively in a schematic representation<sl><li>Figure 1 is a two subordinate communications networks connecting Communications network with several alternative, from an ingress node to an egress node leading routes,</li><li>Figure 2 shows the same communication network when submitting Data transmission capacity values ​​and distribution information,</li><li>Figure 3 is a block diagram of a traffic monitoring device acting, central network node of the communication network and</li><li>Figure 4 is a block diagram of the ingress network node.</li></sl>

In <b>Figure 1</b> is a communication network KN1 shown schematically, on the two subordinate communications networks KN 2 and are coupled KN 3. The communication network KN1 has a connected to the communication network KN 2 ingress node NK1, a printer connected to the communication network KN 3 Egress network nodes NK4, an as traffic-monitoring device acting, central network node ZNK and other network nodes NK2 and NK3 on. The network node NK1, ..., NK4, ZNK the communications network KN1 are the link lines L1, ..., L6 crosslinked. It connects the link cable L1, the network nodes NK1 and NK2, the link line L2, the network nodes NK1 and NK3, the link line L3 network nodes NK3 and ZNK, the link line L4 the network node ZNK and NK2, the link line L5 the network node NK4 and NK2, and the link line L6 the network node NK4 and ZNK.

Each network node NK1, ..., NK4, ZNK can data packets to each other the network nodes NK1, ..., NK4, ZNK each have several alternative routes transmit. For clarity, are shown in Figure 1, only the entry for the network node NK1 Egress network nodes NK4 leading routes LW1, LW2 and LW3 exemplified. Route LW1 takes place via the Link lines L1 and L5, route LW2 via the link lines L1, L4 and L6 and route LW3 via the link lines L2, L3 and L6.

For the present embodiment it is assumed that data transmission in the communications networks KN 2 and KN 3 on the Internet Protocol (IP) and the communication network KN1 on the so-called. MPLS protocol (multiprotocol label switching) based. According to an alternative embodiment, the Communications network KN1 as well as so-called. ATM network (asynchronous transfer mode) to be realized.

For the transmission of data packets over the routes LW1, LW2 and LW3 can within the MPLS protocol one connection along these routes, for example by means of a so-called. Setup message, being constructed. These compounds, which are often are also referred to as an LSP (Label Switched Path), can created for each route, either in advance or only when needed will. To be transmitted via such a COG Data packets according to MPLS protocol each with a called. provided "label" that specifies a route to be used.

Hereinafter, without loss of generality data transfers of source terminals (not shown) of the communication network via the communication network KN2 KN1 to target devices (not shown) of the communication network KN3 in the context of end-to-end connections between the Source and destination terminals considered. In communications networks, KN 2 KN 3 and are to be in this frame transmitting data transported within IP data packets. The IP data packets each contain a minimum a destination terminal identified destination IP address and a the respective source terminal identified source IP address. Furthermore, the single end-to-end connections different transmission priorities.

To be transmitted in the context of end-to-end connections IP data packets from the communication network KN 2 for ingress network node NK1 transferred. This determined the contained in the IP data packets destination IP addresses a particular Egress network nodes NK4 here, to the communication network, Here KN 3, a respective destination terminal. also the transmission priority of a respective end-to-end connection determined. The ingress node has the NK1 IP data packets now such the alternative, to the egress node NK4 leading routes LW1, LW2 and LW3 to distribute that transmission bottlenecks in the communication network KN1 largely avoided and the transmission resources as possible be optimally utilized. In the event that the communications networks KN 2 KN 3 or a large number of terminals is coupled to each of these routes, or LSPs very many end-to-end connections are eliminated.

The provision of the necessary for the distribution of the data packets Information is <b>Figure 2</b> clarified. Figure 2 shows the communication network KN1 when transferring load information A1, ..., A4 and distribution information V1, ..., V4.

The utilization information A1, ..., A4 provides a timely be capacity utilization of the communication network and resist at regular intervals by the network nodes NK1, ..., NK4 respectively transmitted to the central network node ZNK. A respective network node NK1, ..., NK4 determined by means of regular Intervals for each threat it Link cable on this link line currently occupied bandwidth. Alternatively, to link specific line Bandwidth assignments separately for all transmission priorities Routes are determined and / or. The a Network node NK1, ..., NK4 determined transmission bandwidth become a load information A1, ..., summarized A4 and it shall be transmitted to the central network node ZNK.

determined from the transmitted usage information A1, ..., A4 the central network node then ZNK for each of the Network node NK1, ..., NK4 a network node-specific distribution information V1, ..., V4 and those notified in the respective network node. A distribution information V1, ..., V4 for a network node NK1, ..., NK4 includes for each of this network node from the destination network node to reach the Communications network KN1 share information, to each specify this destination network node leading route, what proportion intended for this target node data packets is to transfer this route. In addition, in a Distribution information also contain a proportion specified be that indicates what proportion of a respective destination network node to be transmitted data packets, for example in an overload situation, discard. This percentage is specified in hereinafter also referred to as a rejection percentage.

<b>Figure 3</b> shows a block diagram of the central network node ZNK. As functional components are a link to the lines L3, L4 and L6 connected network assembly and a NB coupled thereto processor board PB shown. In the Network module NB is the so-called. OSPF routing protocol (o-pen shortest path first) implemented. According to an alternative Embodiment, a routing protocol also called. PNNI protocol used (private network to network interface) will.

Using the routing protocol OSPF extracted the central Network nodes ZNK structure information SI from the communication network KN1 which the entire structure of data transmission describe. The structure information SI describe particular all from any first network node NK1, ..., NK4, ZNK at any second network node NK1, ..., NK4, ZNK running routes and the maximum transmission bandwidth of each link line L1, ..., L6 of the communication network KN1. Where appropriate, this information may also detects each transmission priority specific will. The acquired structure information SI are from the Network module NB transmitted to processor board PB.

Furthermore directs the network module NB also in regular Intervals received utilization information A1, ..., A4 for processor module PB on. These included contained in the usage information A1, ..., A4 Bandwidth allocations initially on the basis of the structural information SI contained maximum transmission bandwidths in to data transmission capacity values ​​that the total still free transmission capacity for each link line L1, ..., L6, optionally transfer priority specifically, specify.

The thus determined data transfer capacity values using predetermined data transfer capacity values temporally extrapolated estimates the capacity situation at a future date to receive. This allows time predictive and therefore very efficient traffic control.

calculated from all of the data transmission capacity values the processor module then PB distributing information V1, ..., V4, individually for each Network node NK1, ..., NK4. Also for the central network node ZNK even distribution information is so (not shown) determined. The distribution information determined V1, ..., V4 of the processor board PB of the network board NB transmitted and from this at regular intervals to the respective intended network node NK1, ..., NK4 transferred.

The distribution information V1, ..., V4 are determined, that the split in accordance with the distribution of information streams all network nodes NK1, ..., NK4, ZNK in their entirety so, ..., L6 distribute to each link lines L1, that there are still free transmission bandwidth optimally be used and transmission bottlenecks are avoided.

Exceeds the total of the data streams on one of the link lines L1, ..., L6 whose maximum transmission capacity is the affected network nodes each distribution information with a network node individual warp Share transmitted. The proposal submitted to one of these network nodes rejection proportion is in each case proportional to the usually Bandwidth content to this network node in the congested Link Line Busy. The rejection units are dimensioned that the remaining data streams, the maximum transmission bandwidth the link lines L1, ..., not exceed L6. The rejection of play can also transfer priority specific be determined. In this case, for data streams lower priority higher rejection Shares set as for data streams higher transmission priority.

In particular a network node NK1, ..., NK4 respective transmission situations eg if one link line or a secondary network node, can by the processor module PB also one or more new routes for These nodes are determined. In this case, a the new routes describing routing information to this Network nodes transmit.

<b>Figure 4</b> shows a block diagram of the ingress network node NK1 in a detailed representation. As the functional components are a network module NB1 to which the communication network KN 2 and the link lines L1 and L2 connected are, and coupled to the network module NB1 Control device ST shown. As can be seen already from Fig 1 is run on the link line L1 the routes LW1 and LW2 and on the link line L2 of the route LW3. In the network module NB1 is the OSPF routing protocol implemented. According to an alternative embodiment, as Routing protocol and the PNNI protocol are used.

In the control device ST to the network node NK1 is last transmitted distribution information V1 stored. This includes share information necessary for each to egress network nodes NK4 leading route LW1, LW2 and LW3 each the proportion of on this route to the transmitted data packets indicates. Further, in the distribution information V1 contain rejection percentage that indicates how much of the Data packets to be assigned a rejection path VP, ie how much of the data packets should be discarded. For the present Embodiment, it is assumed that by the Share details 3/8 of the data packets to route LW1, 2/8 of Data packets each to routes and LW2 LW3 and 1/8 of the data packets be assigned to the warp path VP.

originating the distribution of from the communication network KN 2 and the egress network node NK4 to transfer IP data packets is in reference to the transmission of a single IP data packet DP.

originating Upon arrival of one of the communications network KN 2 IP data packet DP is the network board NB1 first checks its destination IP address, so a respective Egress network nodes NK4 here to determine. furthermore is the network board NB1 the source IP address QA of the data packet DP and extracted to the control device ST transfer.

In the control device ST is a scheduling routine ER and a so-called. hash routine HR implemented, both on a control means in the so-called ST stored. hashtable access HTAB. By scheduling routine ER is from those contained in the distribution information V1 Share information a share this information corresponding assignment of address classes 0, ..., 7 to the routes LW1, LW2, LW3 and the warp path VP produced. The assignment is in the Hash table HTAB stored. In the present embodiment, are the route LW1 the address classes 0, 1 and 2, the route LW2 the address classes 3 and 4, the route LW3 the Address classes 5 and 6 and the warp path VP, the assigned address class. 7

Using the hash routine HR can from an address information, such as the source IP address QA inhaled. formed hash value be who in a classification of address information Address classes allowed. For forming a hash value from a Address information, individual bits of the address information linked with each other or with other constant bit patterns will. This has the purpose, that the hash values ​​of different Address information statistically possible be equally distributed to a uniform distribution the address information to go to the address classes. In the present case, the hash routine HR any forms Address information respectively to hash values ​​in the range of From 0 to 7, in turn, the individual address classes 0, ..., 7 represent. By the approximately uniform distribution address information on address classes leads the pro rata Allocation of address classes 0, ..., 7 to one of the routes to Distribution information V1 proper assignment to be transmitted Data packets to routes.

The source IP address QA of the IP data packet DP is the Hash routine HR in the present embodiment on the Hash value displayed 5, and thus associated with the address class. 5 On the basis of the hash table, the controller determines HTAB ST then the route LW3 as to the Address class 5 assigned route and then transmits a that route information identifying the network board NB1. This provides the transferred IP data packet DP according to the MPLS protocol with a "label" the the route LW3 specified and transmits the IP data packet DP, embedded in a MPLS data package from the Link line L2 in the communications network KN1. This transfers the MPLS packet on the by the "Label" specified Route LW3 to egress network nodes NK4, of the IP data packet DP extracted from the MPLS data package, and in the Communications network KN 3 received.