TECHNICAL FIELD

The disclosure relates to a network device for a network, a network manager for a network and methods for load balancing in a network.

BACKGROUND

The disclosure is in the field of networks and load balancing in such networks. In particular, the disclosure is directed to network devices and network managers as well as methods for load balancing in networks.

SUMMARY

The following considerations are made by the inventors:

Load balancing plays a crucial role in improving network utilization. The main idea of load balancing is to split traffic in a network over multiple paths in order to make a better use of network capacity.

Software-Defined Networking (SDN) controllers or Path Computation Elements (PCE) integrate traffic engineering methods to continuously optimize routing and load balancing. These centralized control plane entities leverage on a global view of the network to decide the most efficient way to split traffic. Segment-Routing (SR) or Multiprotocol Label Switching (MPLS) may be used to steer traffic in a network across multiple disjoint paths. In this case, the controller provides routing information to the source (source node) or head devices that perform load balancing in the network (i.e. source routing). However, these solutions require the presence of a centralized routing controller to calculate, install and maintain multiple paths over time, which may not be desirable for scalability, fault-tolerance, or deployment reasons. In addition, when SR or MPLS are used, network devices (e.g. IP devices) that do not have a programmable ASIC need to be replaced, which may be costly for network operators.

Decentralized load balancing solutions may be used to dynamically adjust routing in case of congestion or link failure. However, they only decide about the assignment of flows to multiple paths (e.g. parallel paths provided by a Fat tree topology). A distributed solution for providing multiple paths is called equal-cost multipath routing (ECMP). It is defined for Interior Gateway Protocols (IGPs) such as Open Shortest Path First (OSPF), Routing Information Protocol (RIP), Intermediate System to Intermediate System (IS-IS) and Enhanced Interior Gateway Routing Protocol (EIGRP). It uniformly divides traffic in a network across equal cost paths between an origin node and a destination node. The terms “origin node” and “destination node” may be used as synonyms. The terms “node” and “network node” may be used as synonyms. In IGPs, link weights are used to decentralize the path computation on each router (i.e. distributed routing). Each router maintains a shortest path tree to determine the next hop. In case, multiple shortest paths exist, routers can automatically activate load balancing with ECMP. However, in practice, the existence of multiple equal cost paths, that are disjoint enough to be good for load balancing, is very seldom.

It is desirable to define a distributed routing system that enforces more diverse routing opportunities than ECMP. Similarly to ECMP, it is desired that routers perform path computation in a distributed fashion, without exchanging additional routing information. Such a system should not rely on a centralized entity to calculate routing paths (e.g. SR policies) or routing information (e.g. IGP metrics).

To increase the routing flexibility in IGP protocols, Multi-Topology Routing (MTR) extensions may be used for example for OSPF and Intermediate System to Intermediate System Protocol (IS-IS). It allows operators to design multiple IGP weights, one by topology, such that each device may compute a set of shortest path trees that may be used to route for different needs (e.g., low latency, low congestion). In this case, the protocol maintains a separate Routing Information Base (RIB) and Forwarding Information Base (FIB) for each topology. The RIB is filled by received Link State Advertisements (LSAs) for the different topologies. As the protocol needs to exchange data for each topology, the number of topologies in practice is very limited (generally 3 or 4). For example, the link weights of multiple topologies may be optimized to achieve maximum path diversity across all topologies. The optimization of link weights for the different topologies is typically realized by a centralized network manager. Based on such an optimized Multi-Topology Routing Interior Gateway (MTR-IGP) configuration, an adaptive traffic engineering algorithm may perform dynamic traffic splitting adjustment for balancing the load across multiple routing topologies in reaction to the monitored traffic dynamics. A flexible algorithm (FlexAlgo) may be used as an extension of MTR and may add the possibility to exploit a topology (i.e. a metric type) with different constraints (e.g. inclusions or exclusions of nodes / links).

Centralized solutions may be used to configure network devices with load balancing functionalities. However, relying on a centralized entity can affect the scalability and robustness of the system. A centralized controller is also not desirable in some scenarios. When using Segment Routing (SR), path computation is realized by a SR-Traffic Engineering (SR-TE) controller (e.g. an SDN or PCE controller) that has full control over routing policies. Segment Routing (SR) may operate on top of IGP/MTR/FlexAlgo and provide the possibility to concatenate shortest paths by using inflexion points encoded as a label stack of IP addresses in packet headers for SRv6. This solution requires a hardware upgrade when devices do not have programmable chipsets. It also involves an extensive communication between the controller and devices.

While MTR/FlexAlgo provides a good lightweight Traffic Engineering (TE) solution compared to Segment Routing (SR), it yields a significant overhead as Link State Advertisements (LSA) are sent for each instance and the routing flexibility is tied to only a few available IGP instances (generally 3 or 4). In addition, a centralized management entity needs to optimize link weights or the definition of “algos” so that devices may produce a diverse set of paths that is interesting for load balancing. In general, network operators are looking for a number of maximally disjoint shortest paths between specific pairs of nodes with some additional constraints, e.g. a maximum latency or hop count.

A solution for distributed load balancing in a network may be based on an “adaptive probabilistic flooding” initiated by source nodes of the network to discover multiple path. Flooding adapts number of received messages to limit overhead. Similarly to SR, source nodes insert one label per intermediate node on the path to the destination, and the data plane forwards the packet by popping labels. The main disadvantage of this solution is that it generates a lot of overhead to discover routing paths and that the quality of paths depends on the flooding intensity. In case of unidirectional networks, it can also discover unfeasible paths.

Another solution for distributed load balancing in a network uses only one routing tree rooted at the destination (destination node). According thereto, the basic Shortest Path Tree (SPT) is augmented with edges to create more routing paths (obtaining a directed acyclic graph (DAG)). This augmentation of the tree may be done by each router of the network in a deterministic manner. When forwarding traffic towards the destination, each device selects all (or a subset of) neighbors in the DAG to send traffic to the destination. While this mechanism is totally distributed, it has the disadvantage that the total number of paths depends on the distance to the destination and the computation of paths cannot be parameterized (e.g. with a given number of paths, end-to-end latency or hop count limit, subset of active origin-destination pairs).

In view of the above, the present disclosure aims to improve load balancing in a network. In particular, an objective may be to provide a network device for a network, wherein the network device allows improving load balancing in the network. A further object may be to provide a network manager for a network, wherein the network manager allows improving load balancing in the network. A further object may be to provide a method that allows improving load balancing in a network.

The objective is achieved by the subject-matter of the enclosed independent claims. Advantageous implementations are further defined in the dependent claims.

A first aspect of the disclosure provides a network device for a network. The network device is configured to compute, based on a topology of the network, K disjoint shortest paths for a hop- by-hop routing to a destination node of the network. K is an integer number greater or equal to two.

That is, the first aspect proposes a network device configured for a distributed load balancing in a network, as the network device itself is configured to compute, based on the topology of the network, K disjoint shortest paths for a hop-by-hop routing to a destination node of the network. As a result, the network device allows overcoming disadvantages of centralized load balancing, such as those described above. Further, since the network device is configured to compute the K disjoint shortest paths for a hop-by-hop routing to a destination node of the network, the network device does not use source routing. As a result, disadvantages of source routing for load balancing, such as those described above, may be overcome by the network device according to the first aspect. For example, when using the network device in a network, a centralized routing controller, which is needed for source routing to install and maintain multiple paths, is not required. In other words, the network device according to the first aspect allows a distributed load balancing. For this, the network device is configured to compute, based on the topology of the network, the K disjoint shortest paths for a hop-by-hop routing to a destination node. That is, the network device may maintain a set of disjoint shortest paths that may be enforced in a hop- by-hop fashion using a standard forwarding (e.g. a standard IP forwarding in case of an IP network). As a result, the network device is not based on source routing so that no centralized routing controller is required. This enables distributed load balancing. Further, when using at least two network devices according to the first aspect in a network, there is no need to explicitly exchange routing information between the at least two network devices (assuming that they use the same strategy or algorithm for computing the K disjoint shortest paths). This is advantageous because it reduces the traffic in the network (no additional traffic due to exchange of routing information between the at least two network devices). Further, there is no need of pre-installing anything with regard to load balancing (e.g. routing paths, topologies etc.). In the light of the above, the network device according to the first aspect allows improving load balancing in the network.

The network device may be referred to as a network device for load balancing in the network or network device for distributed load balancing in the network. For example, when the network device is part of the network, the network device may compute, based on a topology of the network, K disjoint shortest paths for a hop-by-hop routing to a destination node of the network. That is, the network device may be a node of the network or is configured to be a node of the network. The network device may be implemented by hardware and/or software.

The destination node of the network may be a network device according to the first aspect. Nodes of the network may be network devices according to the first aspect. The term “network node” may be used as a synonym for the term “node”. Thus, the destination node may be referred to as destination network node.

The phrase “configured to compute K disjoint shortest paths for a hop-by-hop routing to a destination node of the network” may be understood as “configured to compute and maintain K disjoint shortest paths for a hop-by-hop routing to a destination node of the network”. The terms “next-hop routing” or “next-hop based routing” may be used as synonyms for the term “hop-by-hop routing”. Optionally, at least two of the K disjoint shortest paths may have one or more links in common. The K disjoint shortest paths may be maximally disjoint (i.e. they share a minimum number of links). That is, the K disjoint shortest paths may be K maximally disjoint shortest paths. The minimum number of links that the K disjoint shortest path share may be zero in case the K disjoint shortest paths are totally disjoint from each other. Optionally, at least one of the K disjoint shortest paths may be totally disjoint with regard to the other one or more paths of the K disjoint shortest paths, i.e. it may have no links in common with the other one or more paths. In other words, two disjoint shortest paths are totally disjoint in case they do not have a link in common.

The network may be an Internet Protocol (IP) network. In this case, the network device may be an IP network device. Optionally, the network device may be configured to be a router (router node) or a switch (switch node) of an IP network. For example, the network device may be configured to be an Autonomous System Border Router (AB SR) or ASBR node in an Interior Gateway Protocol (IGP) area.

The network device may be configured to use the computed disjoint shortest paths for performing a load balancing in the network, i.e. a load balancing of a traffic in the network. For example, for transmitting packets or data to the destination node, for which the K disjoint shortest paths are computed, the network device may be configured to perform, using the computed K disjoint shortest paths, load balancing. In this case, the network device may be configured to be a source node of the network. That is, the network device may be a source node of the network. The network device may be configured to be a source node and perform load balancing by splitting traffic or data (intended for the destination node) on two or more paths of the computed K disjoint shortest paths (computed for the destination node). In the whole disclosure, K is an integer number greater or equal to two.

The network device may be configured to learn or know the topology of the network. For example, the network device may be configured to learn or know the nodes and links between nodes of the network. For this the network device may be configured to receive information or messages broadcasted in the network, e.g. by the nodes of the network. The network device may be configured to receive such information or messages in a control plane. For example, such messages may be Link State Advertisements (LSAs) of link state routing protocols (e.g. OSPF or IS-IS). In an implementation form of the first aspect, the network device is configured to receive a load balancing request message (LBR message). The network device may be configured to compute K disjoint shortest paths for the hop-by-hop routing to the destination node of the network in response to the LBR message.

The LBR message may be also referred to as message or first message. In other words, the network device may be configured to be triggered by the LBR message to compute the K disjoint shortest paths for the hop-by-hop routing to the destination node of the network. That is, the network device may be configured to compute the K disjoint shortest paths for the hop- by-hop routing in response to receiving the LBR message. This has the advantage, that the computation of the K disjoint shortest paths for load balancing may be triggered by another entity (e.g. a network manager of the network).

The network device may be configured to receive the LBR message from a network manager of the network. The network manager may be a network manager according to the second aspect of the disclosure, as outlined below.

In an implementation form of the first aspect, the LBR message comprises a first set comprising one or more destination nodes of the network. The network device may be configured to compute, based on the topology of the network, for each destination node of the first set, to which a path from the network device exists, K disjoint shortest paths for the hop-by-hop routing to the destination node.

In other words, the network device may be configured to compute, based on the topology of the network, for each destination node of the first set, to which a path from the network device exists, K disjoint shortest paths for the hop-by-hop routing to the respective destination node. The LBR message may indicate one or more destination nodes of the network. The one or more destination nodes may be referred to as active node(s) with regard to load balancing.

This is advantageous, because it allows reducing computation effort of the network device with regard to enabling a distributed load balancing in the network. Namely, instead of the network device computing for every destination node of the network the K disjoint shortest paths, the computation may be limited to (an) active destination node(s), for which a path exists from the network device (e.g. via the network device).

In an implementation form of the first aspect, the first set comprises every destination node of the network. In other words, the LBR message may indicate all destination nodes of the network.

In an implementation form of the first aspect, the LBR message comprises a second set comprising one or more pairs of a source node and a destination node of the network. The network device may be configured to compute, based on the topology of the network, for each pair of the second set, for which a path from the network device to the destination node of the pair exists, K disjoint shortest paths for the hop-by-hop routing to the destination node of the pair.

In other words, the network device may be configured to compute, based on the topology of the network, for each pair of the second set, for which a path from the network device to the destination node of the respective pair exists, K disjoint shortest paths for the hop-by-hop routing to the destination node of the respective pair. The LBR message may indicate one or more pairs of a source node and a destination node of the network. The source node and the destination node of each pair of the second set may be referred to as active source node respectively active destination node with regard to load balancing. The term “origin node” may be used as a synonym for the term “source node”.

This is advantageous, because it allows reducing computation effort of the network device with regard to enabling a distributed load balancing in the network. Namely, instead of the network device computing for every destination node of the network the K disjoint shortest paths, the computation may be limited to (an) active destination node(s), for which there is a path from an active source node via the network device.

In an implementation form of the first aspect, the LBR message comprises an active flag. The network device may be configured to broadcast in the network a load balancing definition message (LBD message) in response to the LBR message comprising the active flag. The LBD message may be also referred to as message or second message. The flag may be referred to as “semi-distributed mode flag”. It may be used for triggering a semi-distributed configuration, when being active. In other words, the flag (comprised by the LBR message) may be a flag for triggering the LBD message, when being active. For example, “broadcasting in the network the LBD message” may mean “advertising in the network the LBD message”. That is, the network device may be configured to advertise in the network the LBD message in response to the LBR message comprising the active flag. This may be true in case the communication in the network is according to the Internet Protocol (IP), e.g. the OSPF routing protocol, i.e. in case the network is an IP network.

In an implementation form of the first aspect, the network device is configured to receive a load balancing definition message (LBD message) from a destination node of the network. The network device may be configured to compute, based on the topology of the network, K disjoint shortest paths for the hop-by-hop routing to the destination node.

The destination node of the network may be a network device according to the first aspect. Nodes of the network may be network devices according to the first aspect.

In an implementation form of the first aspect, the LBD message comprises a third set comprising one or more source nodes of the network. The network device may be configured to compute, based on the topology of the network, K disjoint shortest paths for the hop-by-hop routing to the destination node, in case the network device is part of the third set or of a path from at least one of the one or more source nodes of the third set to the destination node.

In other words, The LBD message may indicate one or more source nodes of the network. The source nodes of the third set may be referred to as active source nodes with regard to load balancing. The network device may be configured to compute, based on the topology of the network, K disjoint shortest paths for the hop-by-hop routing to the destination node (from which it received the LBD message), in case the network device is part of the third set or part of a path from at least one of the one or more source nodes of the third set to the destination node (from which it received the LBD message).

This is advantageous, because it allows reducing computation effort of the network device with regard to enabling a distributed load balancing in the network. In addition, it allows reducing the number of forwarding rules in a forwarding table (e.g. FIB), leaving space for other flows (e.g. memory, such as ternary content-addressable memory (TCAM), may be limited in number of rules). Namely, the computation of the K disjoint shortest paths may be limited to (an) active source node(s), for which there is a path via the network device to the destination node (from which the LBD message is received) or to which the network device corresponds.

In an implementation form of the first aspect, the LBD message comprises at least one of a third set comprising one or more source nodes of the network, the integer number K, disjointness criteria with regard to K disjoint shortest paths, constraints on quality of service (QoS), a metric for an identification of the topology of the network, an authorization to duplicate paths or not, an algorithm type for computing K disjoint shortest paths, and an exclusion set of links and/or nodes of the network.

In other words, the LBD message may indicate at least one of a third set comprising one or more source nodes of the network; the integer number K; disjointness criteria with regard to K disjoint shortest paths; constraints on quality of service (QoS); a metric for generation of the topology of the network, an authorization to duplicate paths or not; an algorithm type for computing K disjoint shortest paths; and an exclusion set of links and/or nodes of the network.

The third set of one or more source nodes of the network may activate multi-path routing (load balancing) for specific sources of the network or specific source-destination flows (may be referred to as origin-destination flows). The integer number K may indicate the number of disjoint shortest paths to be computed for a destination node. For example, the disjointness criteria may comprise at least one of the number of links that may be used more than once, the number of occurrence of links in paths, etc. The different disjointness criteria may be minimized.

The QoS may comprise for example at least one of a maximum hop count, a maximum latency, etc. The QoS constraints may be end-to-end QoS constraints. The QoS constraints may apply to all K disjoint shortest paths. The metric may indicate a basic topology to be used as a topology of the network for computing K disjoint shortest paths for the hop-by-hop routing to the destination node. The basic topology may allow a minimization of routing cost over the basic topology, that provides a metric (may be referred to as weight) for every link in the network. The metric may define the type of cost. For example, the metric may comprise or be cost, hop, delay etc. The authorization to duplicate paths or not may indicate whether the network device (e.g. when being a source node) may duplicate paths for load balancing.

The algorithm type may indicate which algorithm to use for computing the K disjoint shortest paths for a destination node of the network. The algorithm type of the LBD message may enable in a network comprising, as nodes, network devices according to the first aspect that the nodes agree on a common computation strategy for computing K disjoint shortest path for a respective destination node. That is, the algorithm type of the LBD message may enable that the nodes of the network agree on a distributed multi-paths computation strategy. This allows a hop-by-hop routing of data or packets in the network over loop free paths when load balancing is performed or executed in the network. The algorithm type may indicate an algorithm that is configured for computing K disjoint shortest paths that are loop free and may be used for hop-by-hop routing.

The exclusion set of links and/or nodes of the network may indicate for which links and/or nodes a load balancing is not to be done. Thus, the network device may be configured to ignore disjoint shortest paths that comprise a link and/or node of the exclusion set.

The network device may be configured to use or consider the information comprised by the LBD message when computing K disjoint shortest paths for a hop-by-hop routing to a respective destination node.

In an implementation form of the first aspect, the network device is configured to store information of the LBD message in a database of the network device. The network device may be configured to use the stored information for computing K disjoint shortest paths for the hop- by-hop routing to the destination node. The database may part of a control plane.

In an implementation form of the first aspect, the LBR message comprises at least one of a flag for triggering a load balancing definition message (LBD message) when being active, a first set comprising one or more destination nodes of the network, a second set comprising one or more pairs of a source node and a destination node of the network, a third set comprising one or more source nodes of the network, the integer number K, disjointness criteria with regard to K disjoint shortest paths, constraints on quality of service (QoS), a metric for an identification of the topology of the network, an authorization to duplicate paths or not, an algorithm type for computing K disjoint shortest paths, and an exclusion set of links and/or nodes of the network.

In other words, the LBR message may indicate at least one of a flag for triggering a LBD message when being active; a first set comprising one or more destination nodes of the network; a second set comprising one or more pairs of a source node and a destination node of the network; a third set comprising one or more source nodes of the network; the integer number K; disjointness criteria with regard to K disjoint shortest paths; constraints on quality of service (QoS); a metric for generation of the topology of the network, an authorization to duplicate paths or not; an algorithm type for computing K disjoint shortest paths; and an exclusion set of links and/or nodes of the network.

The flag may be referred to as “semi-distributed mode flag”. That is, when the network device receives the LBR message comprising the flag being active, the network device may be configured to broadcast in the network the LBD message in response to the received LBR message comprising the active flag. In case the flag being inactive, the network device may be configured to not broadcast in the network the LBD message.

The first set of one or more destination nodes of the network may activate multi-path routing (load balancing) for specific destination nodes. The second set of one or more pairs of a source node and a destination node of the network may activate multi-path routing (load balancing) for specific source-destination flows (may be referred to as origin-destination flows). The third set of one or more source nodes of the network may activate multi-path routing (load balancing) for specific source nodes of the network or specific source-destination flows. The integer number K may indicate the number of disjoint shortest paths to be computed for a destination node. For example, the disjointness criteria may comprise at least one of the number of links that may be used more than once, the number of occurrence of links in paths, etc. The different disjointness criteria may be minimized. The QoS may comprise for example at least one of a maximum hop count, a maximum latency, etc. The QoS constraints may be end-to-end QoS constraints. The QoS constraints may apply to all K disjoint shortest paths. The metric may indicate a basic topology to be used as a topology of the network for computing K disjoint shortest paths for the hop-by-hop routing to the destination node. The basic topology may allow a minimization of routing cost over the basic topology, that provides a metric (may be referred to as weight) for every link in the network. The metric may define the type of cost. For example, the metric may comprise or be cost, hop, delay etc. The authorization to duplicate paths or not may indicate whether the network device (e.g. when being a source node) may duplicate paths for load balancing.

The algorithm type may indicate which algorithm to use for computing the K disjoint shortest paths for a destination node of the network. The algorithm type of the LBR message may enable in a network comprising, as nodes, network devices according to the first aspect that the nodes agree on a common computation strategy for computing K disjoint shortest path for a respective destination node. That is, the algorithm type of the LBR message may enable that the nodes of the network agree on a distributed multi-paths computation strategy. This allows a hop-by-hop routing of data or packets in the network over loop free paths when load balancing is performed or executed in the network. The algorithm type may indicate an algorithm that is configured for computing K disjoint shortest paths that are loop free and may be used for hop-by-hop routing.

The exclusion set of links and/or nodes of the network may indicate for which links and/or nodes a load balancing is not to be done. Thus, the network device may be configured to ignore disjoint shortest paths that comprise a link and/or node of the exclusion set.

The network device may be configured to use or consider the information comprised by the LBR message when computing K disjoint shortest paths for a hop-by-hop routing to a respective destination node.

In an implementation form of the first aspect, the network device is configured to store information of the LBR message in a database of the network device. The network device may be configured to use the stored information for computing K disjoint shortest paths for the hop- by-hop routing to the destination node. The database may part of a control plane.

In an implementation form of the first aspect, the network device is configured to compute the K disjoint shortest paths for the hop-by-hop routing to the destination node by computing, based on the topology of the network, in each iteration of K iterations a shortest path tree rooted in the destination node. In each iteration after a first iteration the network device may be configured to update link costs of the topology of the network by increasing a link cost of each link of the shortest path tree computed in the previous iteration, and compute the shortest path tree rooted in the destination node using the updated link costs.

Optionally, in each iteration after the first iteration the network device is configured to update link costs of the topology of the network by increasing, by a coefficient, the link cost of each link of the shortest path tree computed in the previous iteration, and to compute the shortest path tree rooted in the destination node using the updated link costs. For example, increasing the link cost of each link by a coefficient may mean multiplying the respective link cost with the coefficient. In each iteration after a second iteration the coefficient may be increased compared to the previous iteration.

In an implementation form of the first aspect, the network device is configured to compute the K disjoint shortest paths for the hop-by-hop routing to the destination node by setting in K/2 iterations weights of links of the topology of the network and computing, based on the topology of the network, a generalized almost directed acyclic graph (GAD AG). In each iteration after a first iteration the network device may be configured to update link weights of the topology of the network by increasing the weight of each link of the GAD AG of the previous iteration by a first value and, when considered in the opposite direction, by a second value smaller than the first value, and compute the GAD AG using the updated link weights. The network device may be configured to obtain, based on each of K/2 computed GADGs, two trees.

In each iteration after the first iteration the setting weights of links of the topology of the network may comprise or be the updating of link weights of the topology of the network. In an implementation form of the first aspect, the network device is configured to filter duplicated paths among the computed K disjoint shortest paths for the hop-by-hop routing to the destination node of the network.

In an implementation form of the first aspect, the network device is configured to store, in a forwarding table, the computed K disjoint shortest paths for the hop-by-hop routing to the destination node in association with the destination node. The forwarding table may be part of a data plane.

In an implementation form of the first aspect, the network device is configured to store, in the forwarding table, the computed K disjoint shortest paths for the hop-by-hop routing to the destination node in association with the destination node, in case the destination node is active with regard to load balancing and serves at least one source node that is active with regard to load balancing.

In an implementation form of the first aspect, the network device is configured to select a path to a desired destination node of the network by using a header field in addition to an Internet Protocol address (IP address) of the desired destination node. The header field indicates the path among K paths for the hop-by-hop routing to the desired destination node.

In other words, the network device may be configured to be a source node of the network, wherein the network device is configured to select a path to a desired destination node of the network by using a header field in addition to an IP address of the desired destination node. The advantage of using the header filed is that the network does not need to have different IP prefixes, one per path of the K disjoint shortest paths computed for a respective destination node (i.e. one per routing tree). This reduces the management burden.

In an implementation form of the first aspect, the network device is configured to select a path to a desired destination node of the network by using a prefix of an IP address of the desired destination node. The prefix indicates the path among K paths for the hop-by-hop routing to the desired destination node.

In other words, the network device may be configured to be a source node of the network, wherein the network device is configured to select a path to a desired destination node of the network by using a prefix of an IP address of the desired destination node. The advantage of using the prefix of the IP address is that there is no new header in packets or data communicated in the network and the communication in the network (transmission of packets or data) may rely or be based on basic IP forwarding.

In an implementation form of the first aspect, the network device is configured to transmit information in the network, the information indicating that the network device is configured to compute, based on the topology of the network, K disjoint shortest paths for the hop-by-hop routing to a destination node of the network.

In an implementation form of the first aspect, the network device is a router or a switch. The switch may be for example a layer 3 switch. The router may be a layer 3 router. For example, the network device may be an IP router or an IP switch (e.g. an IP layer 3 switch).

In order to achieve the network device according to the first aspect of the disclosure, some or all of the implementation forms and optional features of the first aspect, as described above, may be combined with each other.

A second aspect of the disclosure provides a network manager for a network. The network manager is configured to transmit a load balancing request message (LBR message) to at least one node of the network. The LBR message is configured to trigger the at least one node of the network to compute, based on a topology of the network, K disjoint shortest paths for a hop- by-hop routing to a destination node of the network, wherein K is an integer number greater or equal to two.

The network manager may be referred to as network manager for load balancing in the network or network manager for distributed load balancing in the network. The network manager may be implemented by hardware and/or software. The at least one node of the network may be a network device according to the first aspect, as described above. Optionally, the network manager may be referred to as network management system.

In an implementation form of the second aspect, the network manager is configured to transmit the LBR message to all nodes of the network. In an implementation form of the second aspect, the LBR message comprises at least one of an inactive flag, a first set comprising one or more destination nodes of the network, and a second set comprising one or more pairs of a source node and a destination node of the network.

The flag may be referred to as “semi-distributed mode flag”. For example, for each destination of the one or more destination nodes of the first set, K disjoint shortest paths for the hop-by- hop routing to the destination node is to be computed. For example, for the destination node of each pair of the second set, K disjoint shortest paths for the hop-by-hop routing to the destination node of the pair is to be computed. The flag (comprised by the LBR message) may be a flag for triggering a load balancing definition message (LBD message), when being active. Thus, the inactive flag does not trigger the LBD message.

In an implementation form of the second aspect, the network manager is configured to transmit the LBR message to one or more destination nodes of the network.

In other words, the network manager may be configured to transmit the LBR message to a subset of the nodes of the network, wherein the sub-set comprise one or more destination nodes of the network. The one or more destination nodes of the sub-set may be active with regard to load balancing.

In an implementation form of the second aspect, the LBR message comprises at least one of an active flag, and a third set comprising one or more source nodes of the network.

The flag may be referred to as “semi-distributed mode flag”. The flag (comprised by the LBR message) may be a flag for triggering the LBD message, when being active.

In an implementation form of the second aspect, the LBR message comprises at least one of a flag for triggering a load balancing definition message (LBD message) when being active, a first set comprising one or more destination nodes of the network, a second set comprising one or more pairs of a source node and a destination node of the network, a third set comprising one or more source nodes of the network, the integer number K, disjointness criteria with regard to K disjoint shortest paths, constraints on quality of service (QoS), a metric for an identification of the topology of the network, an authorization to duplicate paths or not, an algorithm type for computing K disjoint shortest paths, and an exclusion set of links and/or nodes of the network.

The above description of the network device according to the first aspect is correspondingly valid for the network manager of the second aspect. The above description of the network manager according to the second aspect may be correspondingly valid for the network device according to the first aspect.

The network manager of the second aspect and its implementation forms and optional features achieve the same advantages as the network device of the first aspect and its respective implementation forms and respective optional features.

In order to achieve the network manager according to the second aspect of the disclosure, some or all of the implementation forms and optional features of the second aspect, as described above, may be combined with each other.

A third aspect of the disclosure provides a method for load balancing in a network. The method comprises computing, by a network device of the network, based on a topology of the network K disjoint shortest paths for a hop-by-hop routing to a destination node of the network, wherein K is an integer number greater or equal to two.

The load balancing may be referred to as “distributed load balancing”. The description of the network device of the first aspect is correspondingly valid for the method of the third aspect. The description of the network manager of the second aspect may be correspondingly valid for the method of the third aspect. The network device performing the computation of the method of the third aspect may be a network device according to the first aspect of the disclosure. In an implementation form of the third aspect, the method comprises receiving, by the network device, a load balancing request message (LBR message). The method may comprise computing, by the network device, K disjoint shortest paths for the hop-by-hop routing to the destination node of the network in response to the LBR message.

In an implementation form of the third aspect, the LBR message comprises a first set comprising one or more destination nodes of the network. The method may comprise computing, by the network device, based on the topology of the network for each destination node of the first set, to which a path from the network device exists, K disjoint shortest paths for the hop-by-hop routing to the destination node.

In an implementation form of the third aspect, the first set comprises every destination node of the network.

In an implementation form of the third aspect, the LBR message comprises a second set comprising one or more pairs of a source node and a destination node of the network. The method may comprise computing, by the network device, based on the topology of the network for each pair of the second set, for which a path from the network device to the destination node of the pair exists, K disjoint shortest paths for the hop-by-hop routing to the destination node of the pair.

In an implementation form of the third aspect, the LBR message comprises an active flag. The method may comprise broadcasting, by the network device, in the network a load balancing definition message (LBD message) in response to the LBR message comprising the active flag.

That is, the method may comprise broadcasting, by the network device, in the network a load balancing definition message (LBD message) in response to the network device receiving the LBR message comprising the active flag.

In an implementation form of the third aspect, the method comprises receiving, by the network device, a load balancing definition message (LBD message) from a destination node of the network. The method may comprise computing, by the network device, based on the topology of the network K disjoint shortest paths for the hop-by-hop routing to the destination node. In an implementation form of the third aspect, the LBD message comprises a third set comprising one or more source nodes of the network. The method may comprise computing, by the network device, based on the topology of the network K disjoint shortest paths for the hop-by-hop routing to the destination node, in case the network device is part of the third set or of a path from at least one of the one or more source nodes of the third set to the destination node.

In an implementation form of the third aspect, the LBD message comprises at least one of a third set comprising one or more source nodes of the network, the integer number K, disjointness criteria with regard to K disjoint shortest paths, constraints on quality of service (QoS), a metric for an identification of the topology of the network, an authorization to duplicate paths or not, an algorithm type for computing K disjoint shortest paths, and an exclusion set of links and/or nodes of the network.

In an implementation form of the third aspect, the method comprises storing, by the network device, information of the LBD message in a database of the network device. The method may comprise using, by the network device, the stored information for computing K disjoint shortest paths for the hop-by-hop routing to the destination node.

In an implementation form of the third aspect, the LBR message comprises at least one of a flag for triggering a load balancing definition message (LBD message) when being active, a first set comprising one or more destination nodes of the network, a second set comprising one or more pairs of a source node and a destination node of the network, a third set comprising one or more source nodes of the network, the integer number K, disjointness criteria with regard to K disjoint shortest paths, constraints on quality of service (QoS), a metric for an identification of the topology of the network, an authorization to duplicate paths or not, an algorithm type for computing K disjoint shortest paths, and an exclusion set of links and/or nodes of the network.

In an implementation form of the third aspect, the method comprises storing, by the network device, information of the LBR message in a database of the network device. The method may comprise using, by the network device, the stored information for computing K disjoint shortest paths for the hop-by-hop routing to the destination node.

In an implementation form of the third aspect, the method comprises computing, by the network device, the K disjoint shortest paths for the hop-by-hop routing to the destination node by computing, based on the topology of the network, in each iteration of K iterations a shortest path tree rooted in the destination node. In each iteration after a first iteration the method may comprise updating link costs of the topology of the network by increasing a link cost of each link of the shortest path tree computed in the previous iteration, and computing the shortest path tree rooted in the destination node using the updated link costs.

In an implementation form of the third aspect, the method comprises computing, by the network device, the K disjoint shortest paths for the hop-by-hop routing to the destination node by setting in K/2 iterations weights of links of the topology of the network and computing, based on the topology of the network, a generalized almost directed acyclic graph (GADAG). In each iteration after a first iteration the method may comprise updating link weights of the topology of the network by increasing the weight of each link of the GADAG of the previous iteration by a first value and, when considered in the opposite direction, by a second value smaller than the first value, and computing the GADAG using the updated link weights. The method may comprise obtaining, by the network device, based on each of K/2 computed GADGs two trees.

In each iteration after the first iteration the setting weights of links of the topology of the network may comprise or be the updating of link weights of the topology of the network.

In an implementation form of the third aspect, the method comprises filtering, by the network device, duplicated paths among the computed K disjoint shortest paths for the hop-by-hop routing to the destination node of the network. In an implementation form of the third aspect, the method comprises storing, by the network device, in a forwarding table the computed K disjoint shortest paths for the hop-by-hop routing to the destination node in association with the destination node.

In an implementation form of the third aspect, the method comprises storing, by the network device, in the forwarding table the computed K disjoint shortest paths for the hop-by-hop routing to the destination node in association with the destination node, in case the destination node is active with regard to load balancing and serves at least one source node that is active with regard to load balancing.

In an implementation form of the third aspect, the method comprises selecting, by the network device, a path to a desired destination node of the network by using a header field in addition to an Internet Protocol address (IP address) of the desired destination node. The header field indicates the path among K paths for the hop-by-hop routing to the desired destination node.

In an implementation form of the third aspect, the method comprises selecting, by the network device, a path to a desired destination node of the network by using a prefix of an IP address of the desired destination node. The prefix indicates the path among K paths for the hop-by-hop routing to the desired destination node.

In an implementation form of the third aspect, the method comprises transmitting, by the network device, information in the network, the information indicating that the network device is configured to compute, based on the topology of the network, K disjoint shortest paths for the hop-by-hop routing to a destination node of the network.

In an implementation form of the third aspect, the network device is a router or a switch.

The method of the third aspect and its implementation forms and optional features achieve the same advantages as the network device of the first aspect and its respective implementation forms and respective optional features.

In order to achieve the method according to the third aspect of the disclosure, some or all of the implementation forms and optional features of the third aspect, as described above, may be combined with each other. A fourth aspect of the disclosure provides a method for load balancing in a network. The method comprises transmitting, by a network manager of the network, a load balancing request message (LBR message) to at least one node of the network. The LBR message is configured to trigger the at least one node of the network to compute, based on a topology of the network, K disjoint shortest paths for a hop-by-hop routing to a destination node of the network, wherein K is an integer number greater or equal to two.

The load balancing may be referred to as “distributed load balancing”. The description of the network manager of the second aspect is correspondingly valid for the method of the fourth aspect. The description of the network device of the first aspect may be correspondingly valid for the method of the fourth aspect. The network manager performing the transmission of the method of the fourth aspect may be a network manager according to the second aspect of the disclosure.

In an implementation form of the fourth aspect, the method comprises transmitting, by the network manager, the LBR message to all nodes of the network.

In an implementation form of the fourth aspect, the LBR message comprises at least one of an inactive flag, a first set comprising one or more destination nodes of the network, and a second set comprising one or more pairs of a source node and a destination node of the network.

In an implementation form of the fourth aspect, the method comprises transmitting, by the network manager, the LBR message to one or more destination nodes of the network.

In an implementation form of the fourth aspect, the LBR message comprises at least one of an active flag, and a third set comprising one or more source nodes of the network.

In an implementation form of the fourth aspect, the LBR message comprises at least one of a flag for triggering a load balancing definition message (LBD message) when being active, a first set comprising one or more destination nodes of the network, a second set comprising one or more pairs of a source node and a destination node of the network, a third set comprising one or more source nodes of the network, the integer number K, disjointness criteria with regard to K disjoint shortest paths, constraints on quality of service (QoS), a metric for an identification of the topology of the network, an authorization to duplicate paths or not, an algorithm type for computing K disjoint shortest paths, and an exclusion set of links and/or nodes of the network.

The method of the fourth aspect and its implementation forms and optional features achieve the same advantages as the network device of the first aspect and its respective implementation forms and respective optional features.

In order to achieve the method according to the fourth aspect of the disclosure, some or all of the implementation forms and optional features of the fourth aspect, as described above, may be combined with each other.

It has to be noted that all devices, elements, units and means described in the present application could be implemented in software or hardware elements or any kind of combination thereof. All steps which are performed by the various entities described in the present application as well as the functionalities described to be performed by the various entities are intended to mean that the respective entity is adapted to or configured to perform the respective steps and functionalities. Even if, in the following description of specific embodiments, a specific functionality or step to be performed by external entities is not reflected in the description of a specific detailed element of that entity which performs that specific step or functionality, it should be clear for a skilled person that these methods and functionalities can be implemented in respective software or hardware elements, or any kind of combination thereof.

BRIEF DESCRIPTION OF DRAWINGS

The above described aspects and implementation forms of the present disclosure will be explained in the following description of specific embodiments in relation to the enclosed drawings, in which Fig. 1 shows a network device according to an embodiment of the present disclosure (cf. Fig. 1 A) and a network manager according to an embodiment of the present disclosure (cf. Fig. IB);

Fig. 2 shows a method according to an embodiment of the present disclosure (cf. Fig. 2A) and a method according to a further embodiment of the present disclosure (cf. Fig. 2B);

Fig. 3 shows an example of a network for which the network device of Fig. 1 A and the network manager of Fig. IB may be configured;

Fig. 4 shows an example of a network device according to an embodiment of the present disclosure and a network manager according to an embodiment of the present disclosure;

Fig. 5 shows an example of functions of the network device and network manager of Fig. 4;

Fig. 6 shows two examples of forwarding tables that may be used by a network device according to an embodiment of the present disclosure;

Fig. 7 shows an example of an algorithm that may be used by a network device according to an embodiment of the present disclosure for computing disjoint shortest paths for a hop-by-hop routing to a destination node of a network;

Fig. 8 shows an example of an algorithm that may be used by a network device according to an embodiment of the present disclosure for computing disjoint shortest paths for a hop-by-hop routing to a destination node of a network; and

Fig. 9 shows an example of results of different steps of the algorithm of Fig. 8, when a network device according to an embodiment of the present disclosure performs the algorithm.

In the Figures, corresponding elements are labeled with the same reference sign.

DETAILED DESCRIPTION OF EMBODIMENTS

Fig- 1 shows a network device according to an embodiment of the present disclosure (cf. Fig. 1 A) and a network manager according to an embodiment of the present disclosure (cf. Fig. IB). The network device of Fig. 1 A is an example of the network device according to the first aspect of the present disclosure. The above description with regard to the network device according to the first aspect is valid for the network device of Fig. 1A. The network manager of Fig. IB is an example of the network manager according to the second aspect of the present disclosure. The above description with regard to the network manager according to the second aspect is valid for the network manager of Fig. IB.

The network device 2 of Fig. 1 A is a network device for a network 1. The network device 2 is configured to compute, based on a topology of the network 1, K disjoint shortest paths for a hop-by-hop routing to a destination node of the network 1. K is an integer number greater or equal to two.

The network device 2 may comprise a processor or processing circuitry (not shown) configured to perform, conduct or initiate the various operations of the network device 2 described herein. The processing circuitry may comprise hardware and/or the processing circuitry may be controlled by software. The hardware may comprise analog circuitry or digital circuitry, or both analog and digital circuitry. The digital circuitry may comprise components such as applicationspecific integrated circuits (ASICs), field-programmable arrays (FPGAs), digital signal processors (DSPs), or multi-purpose processors. The network device 2 may further comprise memory circuitry, which stores one or more instruction(s) that can be executed by the processor or by the processing circuitry, in particular under control of the software. For instance, the memory circuitry may comprise a non-transitory storage medium storing executable software code which, when executed by the processor or the processing circuitry, causes the various operations of the network device 2 to be performed. In one embodiment, the processing circuitry may comprise one or more processors and a non-transitory memory connected to the one or more processors. The non-transitory memory may carry executable program code which, when executed by the one or more processors, causes the network device 2 to perform, conduct or initiate the operations or methods described herein.

The network manager 3 of Fig. IB is a network manager for a network 1. As shown in Fig. IB the network 1 may comprise different nodes (network nodes) la, lb and 1c. In addition, examples of links between the nodes are shown. For example, at least one of the nodes la, lb and 1c of the network 1 may be a network device according to Fig. 1A. The network shown in Fig. IB is only an example of a network and does not limit the present disclosure.

The network manager 3 is configured to transmit a load balancing request message (LBR message) to at least one node (e.g. node la) of the network 1. The LBR message is configured to trigger the at least one node of the network 1 to compute, based on a topology of the network 1, K disjoint shortest paths for a hop-by-hop routing to a destination node of the network. K is an integer number greater or equal to two.

The network manager 3 may comprise a processor or processing circuitry (not shown) configured to perform, conduct or initiate the various operations of the network manager 3 described herein. The processing circuitry may comprise hardware and/or the processing circuitry may be controlled by software. The hardware may comprise analog circuitry or digital circuitry, or both analog and digital circuitry. The digital circuitry may comprise components such as application-specific integrated circuits (ASICs), field-programmable arrays (FPGAs), digital signal processors (DSPs), or multi-purpose processors. The network manager 3 may further comprise memory circuitry, which stores one or more instruction(s) that can be executed by the processor or by the processing circuitry, in particular under control of the software. For instance, the memory circuitry may comprise a non-transitory storage medium storing executable software code which, when executed by the processor or the processing circuitry, causes the various operations of the network manager 3 to be performed. In one embodiment, the processing circuitry may comprise one or more processors and a non-transitory memory connected to the one or more processors. The non-transitory memory may carry executable program code which, when executed by the one or more processors, causes the network manager 3 to perform, conduct or initiate the operations or methods described herein.

For further information on the network device 2 and network manager 3 of Fig. 1 reference is made to the above description of the network device according to the first aspect of the disclosure and the network manager according to the second aspect of the disclosure as well as to the following description of Figures 2 to 9.

Fig- 2 shows a method according to an embodiment of the present disclosure (cf. Fig. 2A) and a method according to a further embodiment of the present disclosure (cf. Fig. 2B). The method of Fig. 2A is an example of the method according to the third aspect of the present disclosure. The above description with regard to the method according to the third aspect is valid for the method of Fig. 2A. The method of Fig. 2B is an example of the method according to the fourth aspect of the present disclosure. The above description with regard to the method according to the fourth aspect is valid for the method of Fig. 2B. The method of Fig. 2A is a method for load balancing in a network, such as the network 1 of Fig. 1. The method comprises the step Sla of computing based on a topology of the network K disjoint shortest paths for a hop-by-hop routing to a destination node of the network, wherein K is an integer number greater or equal to two. The method of Fig. 2A may be performable by a network device of the network, e.g. by the network device of Fig. 1A.

The method of Fig. 2B is a method for load balancing in a network, such as the network 1 of Fig. 1. The method comprises the step Sib of transmitting a load balancing request message (LBR message), to at least one node of the network. The LBR message is configured to trigger the at least one node of the network to compute, based on a topology of the network, K disjoint shortest paths for a hop-by-hop routing to a destination node of the network. K is an integer number greater or equal to two. The method of Fig. 2B may be performable by a network manager of the network, e.g. by the network manager of Fig. IB.

For further information on the methods of Fig. 2 reference is made to the above description of the method according to the third aspect of the disclosure and the method according to the fourth aspect of the disclosure as well as to the following description of Figs. 3 to 9.

Fig- 3 shows an example of a network for which the network device of Fig. 1 A and the network manager of Fig. IB may be configured.

The network 1 of Fig. 3 may be an IP network. For example, the network 1 may comprise Autonomous System Border Router (ASBR) nodes 11 in an IGP area. For implementing a load balancing (distributed load balancing) of traffic between the ASBR nodes 11, the ASBR nodes 11 each may be a network device of Fig. 1A. For implementing the load balancing of traffic between the ASBR nodes 11 of the network 1 an optional network manager 3 may be present, that is configured to communicate with the ASBR nodes 11 of the network 1 (e.g. transmit messages to the ASBR nodes 11). The network manager 3 may be a network manager of Fig. IB.

Since ASBR nodes 11 are ingress and egress nodes of the network 1 for traffic, an operator may want to activate load balancing over K paths between all pairs of ASBR nodes 11 (i.e. all pairs of border nodes) or between a subset of pairs of a source node and a destination node (i.e. origindestination pairs or source-destination pairs) of the ASBR nodes 11. For achieving the load balancing, Segment Routing (SR) would require a centralized path computation entity (e.g. SR-TE controller) and an upgrade of the data plane. However, some operators may desire to keep using legacy IGP devices. In this case, source routing with SR may not be used and traffic is forwarded in a hop-by-hop fashion at IP layer. Therefore, using the network device of Fig. 1A as the ASBR nodes 11 and the network manager of Fig. IB as the optional network manager 3 for achieving load balancing in the network 1 of Fig. 3 is advantageous. Namely, in this case the load balancing is a distributed load balancing, wherein each ASBR node 11 may be configured to compute, based on a topology of the network 1, K disjoint shortest paths for a hop-by-hop routing to a respective destination node of the network 1. K is an integer number greater or equal to two. The optional network manager 3 may optionally trigger an ASBR node 11 to compute the K disjoint shortest paths for a hop-by-hop routing to a respective destination node of the network 1. Further, the optional network manager 3 may optionally provide configuration information (e.g. high-level requirements) to the ASBR nodes 11. However, for the load balancing the network manager 3 is not required to provide explicit routing information to the ASBR nodes 11. That is, for a distributed load balancing of traffic between the ASBR nodes 11 (each being a network device of Fig. 1 A), no explicit routing information needs to be exchanged between the ASBR nodes 11 or received from the optional network manager 3 or a central controller. Thus, the present disclosure allows achieving a distributed load balancing of a traffic between nodes 11 of a network 1, wherein each of the nodes 11 may be configured to create or compute, for each destination node of a managed set of destination nodes of the network, K disjoint shortest paths for a hop-by-hop routing to the respective destination node. For this, no communication of explicit routing information between the nodes 11 is necessary.

In the above description with regard to Fig. 3 and in the following description of the Figures it is assumed that the network is an IP network. This is merely by way of example and, thus, not limiting for the present disclosure. Thus, the description of the Figs. 3 to 9 is correspondingly valid for a different type of network. Optionally, the nodes of the network may be configured for link state routing protocols (e.g. OSPF or IS-IS). This allows the nodes of the network to get to know a topology of the network. A node of a network may also be referred to as or may represent a network device. For example, in embodiments of the present disclosure nodes of a network may be or may be implemented like the network device of Fig. 1 A. For further information on the nodes 11 (network devices) of the network 1 of Fig. 3 and the optional network manager 3 reference is made to the above description of Figs. 1 and 2 as well as the following description of Figs. 4 to 9.

Fig- 4 shows an example of a network device according to an embodiment of the present disclosure and a network manager according to an embodiment of the present disclosure. The network device of Fig. 4 is an example of the network device according to the first aspect of the present disclosure. The network device of Fig. 4 is an implementation form of the network device of Fig. 1A. The above description with regard to the network device according to the first aspect and the network device of Fig. 1 A is valid for the network device of Fig. 4. The network manager of Fig. IB is an example of the network manager according to the second aspect of the present disclosure. The network manager of Fig. 4 is an implementation form of the network manager of Fig. IB. The above description with regard to the network manager according to the second aspect and the network manager of Fig. IB is valid for the network manager of Fig. 4.

For the following description, it is assumed that the network device 2 is part of a network comprising several nodes (i.e. several network devices). In other words, the network device 2 may form with other network devices the network, wherein the network device 2 and the other network devices are the nodes of the network. Further it is assumed, that the other nodes of the network are also a network device according to Fig. 4. That is, they are implemented in the same way as the network device 2 of Fig. 4. The following description is correspondingly valid in case at least one node or all of the other nodes of the network is/are differently implemented.

As indicated in Fig. 4, the network manager 3 may transmit or broadcast a load balancing request message (LBR message) to the network device 2. Thus, the network device 2 may receive the LBR message from the network manager 3. For example, the network manager 3 may be configured to transmit or broadcast the LBR message based on requirements received from the network operator or end-users.

By transmitting or broadcasting the LBR message the network manager 3 may trigger or instruct the network device 2 to compute (or create) and maintain, for each pair of a set comprising one or more pairs of an active source node and an active destination node, K disjoint shortest paths for a hop-by-hop routing to the destination node of the respective pair. In this context, the term “active” may be understood such that an active source node or an active destination node is involved in load balancing of a traffic between at least one pair of a source node and a destination node of the network.

The network manager 3 may be configured to configure the network by transmitting or broadcasting the LBR message according to two modes (configuration modes). In case of a first configuration mode of the network manager 3 (may be referred to as centralized mode), the network manager 3 may be configured to transmit or broadcast the LBR message to all nodes or devices of the network. That is, the LBR message is intended for all nodes or devices of the network. In case of a second configuration mode of the network manager 3 (may be referred to as semi-distributed mode), the network manager 3 may be configured to transmit or broadcast the LBR message to a set of destination nodes or destination network devices of the network. The destination nodes of said set may be destination nodes of the network that are active with regard to load balancing. The destination nodes of said set in turn may be configured to configure the rest of the nodes in a distributed fashion. For example, in the semi-distributed mode, the network device 2 may be configured to broadcast, in response to receiving an LBR message from the network manager 3, a load balancing definition message (LBD message) for configuring nodes (not having received the LBR message from the network manager 3) in a distributed fashion. This allows configuring the nodes (not having received the LBR message from the network manager 3) with information of the LBR message (that may be comprised by the LBD message). For example, in the centralized mode all active nodes may be configured by transmitting or broadcasting an LBR message from the network manager, while in the semidistributed mode active destinations may be configured by transmitting or broadcasting an LBR message from the network manager.

For indicating to the network device 2 and nodes of the network which configuration mode is active, the LBR message may comprise a flag. In case the flag is active, the semi-distributed mode is activated, and in case the flag is inactive, the centralized mode is activated. Thus, the network device 2 may broadcast the LBD message in case the LBR message, received from the network manager 3, comprises the flag being active. This flag may be referred to as “semidistributed mode flag”. The flag may be a flag for triggering the LBD message when being active. For a communication between the network manager 3 and the network device 2 at least one of the following protocols may be used: Network Configuration Protocol (NetConf), Border Gateway Protocol (BGP) and Command Line Interface (CLI). The present disclosure is not limited to these protocols and, thus, any other protocol may be used in addition or alternatively. The aforementioned may be valid for a communication between the network manager 3 and the nodes of the network. The dissemination of the configuration in the semi-distributed mode may be implemented as an extension of the routing protocol of the network using a specific Type Length Value (TLV) option.

The LBR message may comprises the aforementioned flag for triggering an LBD message when being active (i.e. for indicating the centralized mode of the management device 3 when being inactive or the semi-distributed mode when being active). Alternatively, the LBR message may not comprise said flag and the mode of the network manager may be set (e.g. by default) for the network, i.e. for all nodes of the network.

The LBR message may comprise a first set comprising one or more destination nodes of the network or a second set comprising one or more pairs of a source node and a destination node of the network. The first set may indicate to the network device 2 (or any other node of the network) one or more destination nodes that are active with regard to load balancing in the network. Thus, the network device 2 may be configured to compute, based on the topology of the network, for each destination node of the first set, to which a path from the network device 2 exists, K disjoint shortest paths for the hop-by-hop routing to the respective destination node. The second set may indicate to the network device 2 (or any other node of the network) one or more pairs of a source node and a destination node that are active with regard to load balancing. Thus, the network device 2 may be configured to compute, based on the topology of the network, for each pair of the second set, for which a path from the network device 2 to the destination node of the respective pair exists, K disjoint shortest paths for the hop-by-hop routing to the destination node of the respective pair.

Optionally, in case the semi-distributed mode is active, the LBR message may comprise a third set comprising one or more source nodes of the network. The third set may indicate to the network device 2 (or any other node of the network) one or more source nodes that are active with regard to load balancing in the network. The network device 2, receiving the third set of one or more source nodes of the network in an LBR message, may be configured to broadcast an LBD message that comprises the third set of one or more source nodes of the network.

Further, the LBR message may comprise at least one of the following parameters (configuration parameters): the integer number K; disjointness criteria with regard to K disjoint shortest paths; constraints on quality of service (QoS); a metric for an identification of the topology of the network; an authorization to duplicate paths or not; an algorithm type for computing K disjoint shortest paths, and an exclusion set of links and/or nodes of the network.

In case the semi-distributed mode is active, the network device 2, receiving the LBR message, may be configured to broadcast an LBD message that comprises the one or more parameters of the received LBR message.

Optionally, any of the above parameters may not be part of the LBR message and may be set (e.g. by default) for the network, i.e. for all nodes of the network.

The LBD message may comprise the third set comprising one or more source nodes of the network. In case the network device 2 receives a LBD message from a node of the network, the received LBD message comprising the third set comprising one or more source nodes of the network, the following may be valid: The network device 2 may be configured to compute, based on the topology of the network, K disjoint shortest paths for the hop-by-hop routing to the node (from which the LBD message is received), in case the network device is part of the third set or of a path from at least one of the one or more source nodes of the third set to the node from which the LBD message is received).

Further, the LBD message may comprise at least one of the following parameters (configuration parameters): the integer number K; disjointness criteria with regard to K disjoint shortest paths; constraints on quality of service (QoS); a metric for generation of the topology of the network; an authorization to duplicate paths or not; an algorithm type for computing K disjoint shortest paths, and an exclusion set of links and/or nodes of the network.

The nodes of the network, i.e. the network device 2 and the other nodes, may be configured to use the same algorithm or method for computing K disjoint shortest paths for a hop-by-hop routing to a destination node. The algorithm type may be provided to the nodes of the network, i.e. the network device 2 and the other nodes, using the LBR message (broadcasted or transmitted by the network manager 3) and optionally using the LBD message in case of the semi-distributed mode being active. In addition or alternatively, the algorithm type may be set (e.g. by default) for the network, i.e. for all nodes of the network. Below two examples for the algorithm that may be used by the nodes of the network and, thus, the network device 2 for computing the K disjoint shortest paths (i.e. two algorithm types) are described with regard to Figs. 7 to 9.

Using the same algorithm at each node of the network allows routing packets in the network over loop free paths when routing them in a hop-by-hop fashion towards their respective destination. For this, each node of the network and, thus, the network device 2 may be configured to compute (and maintain) K disjoint shortest paths for a hop-by-hop-routing to a respective active destination node. That is, each node of the network and, thus, the network device 2 may be configured to compute (and maintain) K forwarding rules towards active destinations in the network. A node of the network (e.g. the network device 2) may be configured to use the K disjoint shortest paths computed for a hop-by-hop-routing to a respective destination as K forwarding rules for forwarding packets or data to the respective destination. Since the nodes of the network use the same algorithm for computing K disjoint shortest paths, the nodes of the network use the same algorithm for generating the forwarding rules. As a result, K disjoint shortest paths between all active source nodes and active destination nodes may be established or generated. This allows a consistent sequence of routing decisions taken in a hop-by-hop fashion at different nodes of the network. Therefore, no routing loops may occur and the characteristics of the paths in the network for forwarding packets or data is satisfactory in terms of disjointness and routing costs. As a result, load balancing of traffic in the network may be improved.

The network device 2 (and the other nodes of the network) may be configured to use or consider the information comprise by the LBR message and the information comprised by the LBD message for computing (and maintaining) K disjoint shortest paths for a hop-by-hop routing to a respective destination.

In some cases, it might not be possible for the network device 2 (or another node of the network) to find paths towards a destination node that are all different. For this case, the LBR message and optionally the LBD message (in case the semi-distributed mode is active) may comprise an authorization to duplicate paths or not. For example, the LBR message and optionally the LBD message may comprise a parameter to authorize or not duplicated paths in the data plane (e.g. duplicated rules or entries in a forwarding table, such as a Forwarding Information Base (FIB)). For duplicated paths, the network device 2 (and the other nodes of the network) may be configured to use hash-based splitting. The network device 2 may be configured to use duplicated entries to give more weights to some paths. The network device 2 may be configured to perform hash-based splitting by computing a hash value on an IP header to determine which forwarding rule to select. If a forwarding rule is duplicated, the path associated to it has more chance to be selected. For example, if four paths are configured and two of them are identical, the split ratio over the duplicated path is 1/2, while being 1/4 for the other two paths. Without duplicated paths, the split would have been 1/3 for each path. The network device 2 may optionally be configured to perform a path computation method that proposes duplicated path on purpose to give more importance to one path for load balancing (e.g. a path with more capacity).

The network manager 3 and/or the network device 2 may be configured to specify what load balancing strategy to be deployed at source nodes of the network. Examples of load balancing strategy comprise load-aware, random etc.

As shown in Fig. 4, with regard to the load balancing concept according to the present disclosure the network manager 3 may comprise a load balancing manager 31 for performing the functions and operations of the network manager 3 described herein. The network device 2 may comprise a load balancing module 21, a database 22 and a forwarding table 23. The term “routing table” may be used as a synonym for the term “forwarding table”. The database 22 may be configured to store the topology of the network that is used for computing K disjoint shortest paths for a hop-by-hop routing to a respective destination node. The topology of the network may be a topology of the network according to one metric. For example, the database may be configured to store nodes, node states, links and/or link states of the network. For this the network device may be configured to receive messages broadcasted in the network, e.g. by the nodes of the network. The network device may be configured to receive such messages in a control plane. For example, such messages may be Link State Advertisements (LSAs) of link state routing protocols (e.g. OSPF or IS-IS). The database 22 may be configured to store information of a received LBR message and optionally information of a received LBD message. The load balancing module 21 may be configured to perform the functions and operations of the network device 2 described herein. For example, the load balancing module 21 may be configured to use information stored in the database 22 (e.g. the topology of the network and optional information of an LBR message). The load balancing module 21 may comprise a configuration manager 21a, a K-next-hop maintenance module 21b and a load balancing table population module 21c. The term “routing table population module” may be used as a synonym for the term “load balancing table population module”. With regard to Fig. 5, an example of the functions of the configuration manager 21a, the K-next-hop maintenance module 21b and the load balancing table population module 21c is described.

The forwarding table 23 may be configured to store the computed K disjoint shortest paths for the hop-by-hop routing to a respective node in association with the respective destination node.

For further information on the network device 2 and the network manager 3 reference is made to the above description of Figs. 1 to 3 as well as the following description of Figs. 5 to 9.

Fig- 5 shows an example of functions of the network device and network manager of Fig. 4.

As shown in Fig. 5, the load balancing manager 31 of the network manager 3 may be configured to transmit an LBR message to the network device 2. This is indicated by the reference sign 51.

The configuration manager 21a may be configured to receive the LBR message. That is, the configuration manager 21a may be configured to receive updates (in the form of the LBR message) from the network manager 3. The LBR message may comprise information (configuration information) as described above. The configuration manager 21a may be configured to save the information of the received LBR message in the database 22. This is indicated by the reference sign 52. That is, the configuration manager 21a may be configured to maintain the database 22 and enforce it. The database 22 may be referred to as configuration database. The configuration manager 21a may be configured to maintain a consistent database. In case the semi-distributed mode is activated (e.g. by a respective flag of the LBR message being active), the configuration manager 21a may be configured to transmit or broadcast a LBD message when the LBR message, received by the configuration manager 21a from the network manager 3, triggers the configuration manager 21a to do so. That is, the configuration manager 21a may be configured to propagate a configuration provided by the LBR message with an LBD message. This is indicated by the reference sign 53. The LBD message comprises information of the received LBR message, as outlined above. In this case, the network device 2 is a destination node and the semi-distributed mode is active. The configuration manager 21a may be configured to receive an LBD message from another node of the network. The configuration manager 21a may be configured to save the information of the received LBD message in the database 22. The configuration manager 21a may be configured to provide or propagate information of the database 22, information of a received LBR message and/or information of a received LBD message to the K-next-hop maintenance module 21b and the load balancing table population module 21c. This is indicated by the reference signs 54 and 55.

The K-next-hop maintenance module 21b may be configured to perform the computation of K disjoint shortest paths for a hop-by-hop routing to a respective destination node, as outlined above. For this, the K-next-hop maintenance module 21b may be configured to use information stored in the database 22 (e.g. information with regard to the topology of the network or the topology of the network). Further, the K-next-hop maintenance module 21b may use for this computation information of an LBR message received by the configuration manager 21a and/or information of an LBD message received by the configuration manager 21a. Below two examples for an algorithm that may be used by the K-next-hop maintenance module 21b for the aforementioned computation are described with regard to Figs. 7 to 9. For example, the K-next- hop maintenance module 21b may be configured to compute, for each active destination node of the network, based on the topology of the network K disjoint shortest paths for a hop-by-hop routing to the respective active destination node. The K-next-hop maintenance module 21b may be configured to provide or propagate the computation result to the load balancing table population module 21c. This is indicated by the reference sign 56.

The load balancing table population module 21c may be configured to fill a forwarding table 23 (e.g. forwarding table of the data plane) with forwarding rules using the computation result received from the K-next-hop maintenance module 21b. This is indicated by the reference sign 57. For this, the load balancing table population module 21c may be configured to use information stored in the database 22. Further, the load balancing table population module 21c may use information of an LBR message received by the configuration manager 21a and/or information of an LBD message received by the configuration manager 21a. For example, the load balancing table population module 21c may be configured to fill a forwarding table 23 with forwarding rules for the active destination nodes of the network using the K disjoint shortest path computed, by the K-next-hop maintenance module 21b, for each of the active destination nodes. Optionally, the load balancing table population module 21c may be configured to filter duplicated paths and/or unnecessary forwarding rules (e.g. only keeping active destination nodes and installing forwarding rules only when the destination node serves at least one active source node). An active destination node is active with regard to load balancing and an active source node is active with regard to load balancing.

The above-described functions of the configuration manager 21a, the K-next-hop maintenance module 21b and the load balancing table population module 21c are functions of the network device 2. Thus, the network device 2 may be configured to perform these functions.

Fig- 6 shows two examples of forwarding tables that may be used by a network device according to an embodiment of the present disclosure. For example, the network device of Fig. 1 A may use at least one of these forwarding tables.

For forwarding packets in a network, optionally only a source node may split a sourcedestination flow by selecting a path towards the destination node of the source-destination flow. That is, only the source node may split the traffic or packets to a respective destination node on two or more paths towards the respective destination node. The network device 2 may be configured to be a source node. That is, the network device 2 may be configured to split a source-destination flow by selecting a path towards the destination node of the sourcedestination flow when the network device 2 is the source node of the source-destination flow. In other words, the network device 2 may be configured to split the traffic or packets to a respective destination node on two or more paths towards the respective destination node when the network device 2 is the source node that initially starts the traffic or initially transmits the packets.

Optionally, the selection of each path may be realized using a header field (e.g. Tree ID) in addition to an IP address. This is exemplarily shown in Fig. 6A. On the left column of the forwarding table of Fig. 6A the IP address of the destination node is shown. In the middle column of the forwarding table of Fig. 6A the header field for selecting the path of the K disjoint shortest paths computed for the destination node is shown. In the example of Fig. 6A, the integer number K is for example three (K = 3). This is only by way of example not limiting the present disclosure. On the right column of the forwarding table of Fig. 6Athe corresponding IP address of the next-hop, that is of the next node, in the path towards the destination node is indicated. As indicated by the last number (highlighted in Fig. 6A as bold) of the IP address of the nexthop, the next-hops are different due to the corresponding different paths chosen using the header field from the computed K disjoint shortest paths for the destination node. The advantage of the header field method is that the network does not need to have different IP prefixes, one per routing tree (i.e. one per paths of K disjoint shortest paths computed for a respective destination). This reduces the management burden.

Alternatively, the selection of each path may also be realized with an IP prefix as shown in Fig. 6B. That is, standard IP forwarding may be used. When using standard IP forwarding the forwarding table may be as shown in Fig. 6B. In this case, nodes may belong to K sub-nets and have K IPs. Each sub-net may have its own prefix, each one may be used to identify and select paths. The advantage is that there is no new header in packets and basic IP forwarding may be used.

As shown in the left column of the forwarding table of Fig. 6B, the path of the K disjoint shortest paths computed for the destination node may be selected by the IP address, e.g. by the second to last number (highlighted in Fig. 6B as bold) of the IP address. In the example of Fig. 6B the integer number K is for example three (K = 3). This is only by way of example not limiting the present disclosure. On the right column of the forwarding table of Fig. 6B the corresponding IP address of the next-hop, that is of the next node, in the path towards the destination node is indicated. As indicated by the last number of the IP address of the next-hop, the next-hops are different due to the corresponding different paths chosen using the IP address (e.g. the second to last number of the IP address) from the computed K disjoint shortest paths for the destination node.

Fig- 7 shows an example of an algorithm that may be used by a network device according to an embodiment of the present disclosure for computing disjoint shortest paths for a hop-by-hop routing to a destination node of a network. The network device may be the network device 2 of the Figs. 1 and 3 to 5.

The algorithm or method of Fig. 7 for computing, based on the topology of the network, K disjoint shortest paths for a hop-by-hop routing to a destination node comprises finding K shortest path trees for the destination node. The K shortest path trees may be referred to as K Dijkstra trees. As outlined above, K is an integer number greater or equal to two (K > 2). The computation of trees may consider the intent given by the load balancing request (LBR) message. For instance, the algorithm of Fig. 7 may maximize the disjointness. For example, the algorithm of Fig. 7 may compute for each active destination node K shortest path trees where at each iteration the cost of links in a previous shortest path tree is increased (e.g. by a coefficient a).

As shown in Fig. 7, in a first step S71 the network device may be configured to use the topology of the network (G =(V,A)) and costs (e.g. IGP costs) of the links of the network for computing K disjoint shortest paths for a hop-by-hop routing to a respective destination node of the network. In a next step S72 the network device may be configured to compute the K disjoint shortest paths for the hop-by-hop routing to the respective destination node by computing, based on the topology of the network, a shortest path tree rooted in the respective destination node. As indicated in Fig. 7, the network device may be configured to repeat the step 72 K-times (i.e. perform K iterations) in order to compute in each iteration of the K iterations a shortest path tree rotted in the respective destination node. As indicated in the step S73, in each iteration after a first iteration (i.e. in each iteration after performing the step S72 for the first time) the network device may be configured to update link costs of the topology of the network by increasing a link cost of each link of the shortest path tree computed in the previous iteration. Thus, in each iteration after a first iteration, in the step S72, the network device may be configured to compute the shortest path tree rooted in the destination node using the updated link costs (updated in step S73). After performing the K iteration, in a step S74, the network device may be configured to output the computed K shortest path trees rooted in the respective destination node as the computation result of computing K disjoint shortest paths for the hop-by-hop routing to the respective destination node of the network.

Optionally, in each iteration after the first iteration, the network device is configured to update link costs of the topology of the network by increasing, by a coefficient, the link cost of each link of the shortest path tree computed in the previous iteration. This corresponds to the step S73. In each iteration after a second iteration the coefficient may be increased compared to the previous iteration.

Fig- 8 shows an example of an algorithm that may be used by a network device according to an embodiment of the present disclosure for computing disjoint shortest paths for a hop-by-hop routing to a destination node of a network. The network device may be the network device 2 of the Figs. 1 and 3 to 5.

According to the algorithm of Fig. 8 the network device may be configured to compute the K disjoint shortest path for a respective destination node by iteratively computing K/2 Generalized Almost Directed Acyclic Graph (GADAG) guided by link weights. The algorithm allows to generate K/2 GADAG that are as disjoint as possible. Two maximally disjoint shortest paths may be extracted from each GADAG. In the iterations of the algorithm the new GADAG minimizes the weight of its links (e.g. the sum of link weights), that are updated at each iteration based on the number of times a link is used in a previous GADAG. The algorithm of Fig. 8 may be described as following:

For generating K/2 GADAG the network device may be configured to use the topology of the network (G(V,A)) with a cost (e.g. IGP cost) associated with each link as input (cf. step S81). The network device may be configured to perform K/2 iterations. For example, in each iteration, the network device may be configured to update the weight of links (may be referred to as arcs) traversed by GAD AGs to the number of GAD AGs using them and add 0.5 on opposite links (directed graph). This may correspond to or be part of step S84 of Fig. 8. Further, in each iteration, the network device may be configured to create a cycle using for example Depth First Search (DFS), Breadth First Search (BFS) or Shortest Path (SP). This may correspond to or may be part of step S83 of Fig. 8. This may comprise selecting the link with the smallest weight and consider its source to be the root node, then visit links prioritizing smallest link weights. Furthermore, in each iteration, the network device may be configured to add ears one by one (start from outgoing links in the current GADAG and run DFS/BFS/SP by prioritizing smallest link weights, stop when a node from the GADAG is visited). Continue adding ears until each node of the network is covered. This may correspond to or may be part of step S83 of Fig. 8.

As shown in Fig. 8, in a first step S81, the network device may be configured to use the topology of the network (G =(V, A)) and costs (e.g. IGP costs) of the links of the network for computing K disjoint shortest paths for a hop-by-hop routing to a respective destination node of the network. In a next optional step S82 the network device may configured to set a weight of each directed link (e.g. zero (o) or a weight associated with a metric/topology of the network). In a next step S83 the network device may be configured to compute the K disjoint shortest paths for the hop-by-hop routing to the respective destination node by computing, based on the topology of the network, a GAD AG (weighted GAD AG). For this, the network device may use DFS, BFS or SP. As indicated in Fig. 8, the network device may be configured to repeat the step 83 K/2 times (i.e. perform K/2 iterations) in order to compute in each iteration of the K/2 iterations a GAD AG (weighted GAD AG). As indicated in the step S84, in each iteration after a first iteration (i.e. in each iteration after performing the step S73 for the first time) the network device may be configured to update link weights of the topology of the network by increasing the weight of each link of the GAD AG of the previous iteration by a first value and, when considered in the opposite direction, by a second value smaller than the first value. For example, the first value may be equal to one (1) and the second value be equal to a half (0.5). Thus, in each iteration after a first iteration, in the step S83, the network device may be configured to compute the GADAG using the updated link weights (updated in step S84). The term “arc” may be used as a synonym for the term “link”. As indicated in step S85, the network device may be configured to obtain, based on each of K/2 computed GADG, two trees for the respective destination node. Thus, in the step S86, the network device may be configured to output K trees for the respective destination node as the computation result of computing K disjoint shortest paths for the hop-by-hop routing to the respective destination node of the network.

Fig- 9 shows an example of results of different steps of the algorithm of Fig. 8, when a network device according to an embodiment of the present disclosure performs the algorithm.

Fig. 9 (A) shows an example of a first GADAG that may be computed by the network device, based on the topology of the network, using a classical way in a first iteration of step S83 (i.e. when performing the step S83 the first time).

Fig. 9 (B) shows an example of performing the step S84 a first time, i.e. in a second iteration of the algorithm of Fig. 8. According thereto, the network device may update link weights of the topology of the network by increasing the weight of each link of the first GADAG of the previous iteration (i.e. the first GADAG of Fig. 9 (A)) by a first value and, when considered in the opposite direction, by a second value smaller than the first value. For the examples of Fig. 9 it is assumed that the initial weights of the network are zero (o), the first value is one (1) and the second value is a half (0.5). Fig. 9 (B) shows the network with the updated link weights. Fig. 9 (C) shows an example of computing a second GADAG that may be computed by the network device based on the topology of the network with the updated link weights (i.e. the network of Fig. 9 (B)) in a classical way in a second iteration of step S83 (i.e. when performing the step S83 a second time). For this, at first a cycle or loop with the smallest link weights (i.e. smallest cost) may be generated (shown on the left of Fig. 9 (C)). Next, all remaining nodes of the network may be covered by adding one or more ears (shown in the middle of Fig. 9 (C)). In the example of Fig. 9, adding one ear is sufficient for covering all nodes of the network. As a result of the aforementioned two sub-steps of Step S83 the second GADAG is generated in a classical way as shown on the right side of Fig. 9 (C).

As described above with regard to Figs. 9 (B) and (C), the network device may generate, based on the second GADAG a third GADAG. For this, Fig. 9 (D) shows on the left the updating step S84 performed based on the second GADAG and on the right the third GADAG. The aforementioned iterations may be repeated until K/2 GADAG are generated.

Once all K/2 GADAG are computed (e.g. for each pair of source node and destination node), two maximally disjoint shortest paths may be generated or computed based on each GADAG. As a result, K disjoint shortest paths may be generated based on the K/2 GADAG.

For example, two maximally disjoint shortest paths may be generated based on a GADAG as follows: Given a GADAG and a destination node t, two trees may be generated. A first tree is included in the GADAG. A second tree is included in the GADAG, wherein each link of the GADAG is considered in the opposite direction. For a given source s the first path is selected in the first tree and the second path is selected in the second tree. The aforementioned is exemplarily shown in Fig. 9 (E) for the first GADAG of Fig. 9 (A), wherein the left side of Fig. 9(D) shows the first path and the right side of Fig. 9 (D) shows the second path.

If the network is two-connected (i.e. two disjoint paths exist between all pairs of nodes of the network), the pairs of paths extracted from a GADAG ensure the existence of at least one path for each pair of a source node and destination node for every failure. The two paths obtained using a GADAG are totally disjoint and ensure the existence of backup path. This is a main advantage of the method according to Figs. 8 and 9. The present disclosure has been described in conjunction with various embodiments as examples as well as implementations. However, other variations can be understood and effected by those persons skilled in the art and practicing the claimed subject-matter, from the studies of the drawings, this disclosure and the independent claims. In the claims as well as in the description the word “comprising” does not exclude other elements or steps and the indefinite article “a” or “an” does not exclude a plurality. A single element or other unit may fulfill the functions of several entities or items recited in the claims. The mere fact that certain measures are recited in the mutual different dependent claims does not indicate that a combination of these measures cannot be used in an advantageous implementation.