WO2013023989A1

WO2013023989A1 - Method and device for selecting next hop in a data network

Info

Publication number: WO2013023989A1
Application number: PCT/EP2012/065601
Authority: WO
Inventors: Gregory DETAL; Olivier Bonaventure; Simon VAN DER LINDEN; Gildas AVOINE
Original assignee: Universite Catholique De Louvain
Priority date: 2011-08-12
Filing date: 2012-08-09
Publication date: 2013-02-21
Also published as: GB2493710A; GB201113931D0

Abstract

A method for sending a packet, said packet comprising a header, from a sender to a receiver in a data communication network comprising one or more routers having two or more available next hops leading to said receiver. An invertible function F encoding a sequence of X bits into another sequence of X bits is selected. The sender performs the steps of selecting a preferred next hop for each of said one or more routers; grouping each of said preferred next hops in a path selector, said path selector having a length X in bits; selecting a function F encoding a sequence of X bits into another sequence of X bits, said function being invertible; applying the inverse of said function to said path selector and storing the result in a first subset of said header; sending said packet across said data communication network. One router performs the steps of applying said function F to said first subset of said header for obtaining the original path selector; extracting from said path selector the preferred next hop selected by the sender for said one router; sending said packet through said preferred next hop.

Description

METHOD AND DEVICE FOR SELECTING NEXT HOP IN A DATA NETWORK

TECHNICAL FIELD [0001 ] The present invention relates generally to the field of data communications network. More particularly, the invention relates to a method for sending a packet from a sender to a receiver in a data communication network comprising one or more routers, a least one router having two or more available next hops and to devices for sending and routing packets in said data communication network.

DESCRIPTION OF RELATED ART

[0002] Load balancing plays a key role in enterprise, datacenter and ISP networks. It allows to improve the performance and the scalability of the Internet by distributing the load evenly across network links, servers, or other resources. Load balancing allows to maximize the throughput, achieve redundant connectivity or reduce congestion . Different forms of load balancing are deployed at various layers of the protocol stack. At the datalink layer, frames can be distributed over parallel links between two devices. At the application layer, requests can be spread on a pool of servers. At the network layer, the most common technique, Equal-Cost Multi-Path (ECMP) , allows routers to forward packets over multiple equally-good paths. ECMP may both increase the network capacity and improve the reaction of the control plane to failures. Current ECMP-enabled routers proportionally balance flows across a set of equal next hops on the path to the destination.

[0003] Various methods to select a next hop are known. The most deployed next-hop selection method is solely based upon a hash computed over several fields of the regular packet headers. Using a hash function ensures a somewhat fair distribution of the next-hop selection (See e.g. Z. Cao, Z. Wang, and E. Zegura "Performance of Hashing-Based Schemes for Internet Load Balancing" In Proc. IEEE INFOCOM, 2000). Most implementations include as input to the hash computation the transport-level port numbers allowing to improve the load spreading while still maintaining the same path for a given transport level flow.

[0004] However, using the transport header to perform the network layer forwarding breaks the layered architecture, enabling the transport layer to influence the path being followed by packets. Although some topology discovery applications exploit this principle, it remains difficult for end hosts to accurately control forwarding decisions or even be aware of the path diversity that is available in the network. Multipath-aware transport protocols such as SCTP-CMT or MultiPath TCP would clearly benefit from being able to select network paths that are as independent as possible to avoid congestion . Unfortunately, this is not possible with the existing hash-based load-balancing techniques. Source routing techniques could enable end hosts to choose the paths their packets follow. Unfortunately, standard IP source routing does not scale well and has well-known security problems. Better alternatives that let end hosts leverage on the path diversity have been proposed. However, these solutions rely on specific shim headers that follow the IP header. Experience shows that it is very difficult to incrementally deploy such a new header in a network.

[0005] For performing load balancing at the network layer it is known to use Equal-Cost Multi-Path (ECMP). ECMP is discussed in C. Hopps "Analysis of an Equal-Cost Multi-Path Algorithm" RFC 2992, IETF, November 2000. ECMP is a packet forwarding strategy that uses paths that tie for the best path selection. When such strategies are being used, routers need to balance packets over multiple next hops. Various next-hop selection methods exist to balance packets over load-balanced paths. They should meet the following requirements:

- Minimal disruption: Packets from the same TCP flow should always follow the same path in order to avoid packet reordering.

- Transparency: Load balancing operates on normal network packets. It does not require any additional fields in packet header. - Operate at Line Rate: The additional computation required to balance the packets should be marginal.

Load balancing should also fairly share the load over the next hops. Since flows vary widely in terms of number of packets and volume, this is not that easy. Most load-balancing methods that meet these requirements are based on a hash function. They compute a hash over the fields that identify the flow in the packet headers. These fields are usually the source and destination IP addresses, the protocol number and the source and destination ports. In the present description, we call these fields the 5-tuple. The computed hash can then be used in various ways to select a next hop. The simplest and most deployed method is called Modulo-N. If there are N available next hops, the remainder of dividing the hash by N is used as an identifier of the next hop to use. Because of the roughly uniform distribution of the hashes, this method results in a uniform distribution in terms of number of packets.

PRIOR ART DISCUSSION

[0006] An example of a hashing-based network load balancing method is disclosed by document US 6,888,797 wherein a router 2 determines an output link 12, 13, 14,15 or 16 based on a hash value computed from header data comprising source address, destination address, source port, destination port, and protocol id, and from network load directions. This method allows the router to distribute the stream of packets to the output links according to a desired load distribution. However, this method does not allow the sender to predetermine the link to be selected for specific packets.

[0007] Another example of a hashing-base network load balancing method is disclosed in US 7,233,575. This document addresses the situation where at least routers in the network have the same number of valid next hops. In such a situation, the known hashing methods will assign all packet of a given flow, i.e. having same source and destination address to the same output next-hop in successive routers of the network. Load balancing of packets at different routers is highly correlated. This phenomenon is called polarization. This leads to systematic unbalanced load distribution. This problem is solved by assigning different hashing parameters to each of the routers, in such a way that the next-hop selections for each router are uncorrelated. However, this document also does not address the selection of specific paths.

[0008] The following references all either do not allow the control of the specific path, or require additional data in the header, and thereby do not meet the transparency requirement:

1 . P. B. Godfrey, I. Ganichev, S. Shenker, and I. Stoica. "Pathlet Routing".

In Proc. ACM SIGCOMM, August 2009.

2. H T. Kaur et al. BANANAS: "An Evolutionary Framework for Explicit and Multipath Routing in the Internet" In Proc. ACM SIGCOMM FDNA Workshop, 2003.

3. M. Motiwala, M. Elmore, N. Feamster, andS. Vempala. "Path Splicing" In Proc. ACM SIGCOMM, October 2008.

4. X. Yang and D. Wetherall. "Source Selectable Path Diversity via Routing Deflections" In Proc. ACM SIGCOMM, August 2006.

[0009] A method for adaptive routing of messages in a computer network is known from US5721820. The method provides adaptive source routing by generating at a source node a routing message describing a plurality of allowable paths via which data message can reach a desired destination. The data message and the routing message are sent by the source to a first switch, and the routing message is evaluated by control logic to determine if an available, allowable path exists. If so, the data message and routing message are sent via that path to the destination. The need of these routing messages generates additional overhead and makes this method non- transparent.

[0010] A method for transmitting a packet via a sequence of nodes in a network is known from US5353283. The transmitted-packet contains a sequence of one or more identifiers in a sequence of fields and a pointer pointing to a particular identifier in the sequence of identifiers in a field of a routing section of a header in the packet. A node of the sequence of nodes at which the packet is located selects a forwarding table from a set of forwarding tables maintained in a memory at that node. The node then retrieves an entry from the selected forwarding table indexed by the identifier in the sequence of identifiers pointed to by the pointer. The node then transmits the packet to the next node of the sequence of nodes indicated by the retrieved forwarding table entry. The need for these additional fields in the packet header makes this method also non-transparent.

[001 1 ] The present invention aims at providing a method and device that overcomes the above-discussed drawbacks of the prior art.

[0012] In particular, it is an object of the present invention to provide a method for sending a packet from a sender to a receiver in a data communication network, wherein the sender can select the actual next hop out of a router in the network for specific packets, in the case where a router has more than one available next hops. Preferably, when the sender does not wish to select the actual next hop, the router having more than one available next hop should select the next hop in a load-balanced way, i.e. using each of the next hops evenly.

[0013] Another object of the present invention is to provide a sender and a router adapted for performing this method. Such a method and devices may be used for example for testing the operation of specific links and for monitoring the network. This feature may also be used for improving performance of the network

SUMMARY OF THE INVENTION [0014] According to a first aspect, the present invention relates to a method for sending a packet, said packet comprising a header, from a sender to a receiver in a data communication network comprising one or more routers, one or more routers having two or more available next hops leading to said receiver. In the method, a function F encoding a sequence of X bits into another sequence of X bits is selected, said function being invertible. The sender performs the steps of selecting a preferred next hop for each of said one or more routers; grouping each of said preferred next hops in a path selector, said path selector having a length X in bits ; applying the inverse of said function F to said path selector and storing the result in a first subset of said header; sending said packet across said data communication network. At least one of the routers performs the steps of applying said function F to said first subset of said header for obtaining the original path selector; extracting from said path selector the preferred next hop selected by the sender for said one router; sending said packet through said preferred next hop. Thereby, the sender can specify the path for the packet across the network, or "steer" the packets. The first subset of the header is the "controllable fields" discussed in the examples.

[0015] Said function F is advantageously selected among the functions where at least 40% or preferably 50% of the output bits change wherever a single bit in the input is changed. As a result of this choice, packets that have not been processed by a sender for being steered along a specific path are processed by a router of the network in a load-balanced way.

[0016] In a preferred embodiment of the invention, when the sender initiates a counter TTL and stores said counter in a second subset of said packet header and each successive router in the network receiving a packet decrements said counter TTL, a router having two or more available next hops uses said counter for extracting from said path selector the preferred next hop selected by the sender for said one router.

[0017] In a preferred embodiment, the grouping of each next hops in a path selector is performed by a lossless compression method. Thereby, an optimal use of the available space in the packet header is made for coding a maximum number of paths.

[0018] The function may advantageously be a block cipher selected from a group comprising Skip32 and RC5.

[0019] The first subset of header, where the path selector is stored, may comprise the source port and/or the destination port. It may also comprise the source address or a subset thereof, the destination address or a subset thereof, a flow label and an MPLS label. [0020] In a preferred embodiment, the sender further computes a hash function based on a third subset of said header and adds said hash function to each of said preferred next hops grouped in said path selector, and the router further computes the same hash function based on said third subset of said header and adds said hash function to each of said preferred next hops extracted from said path selector. Thereby, the phenomenon of polarization discussed above is avoided. The third subset of the header is the "uncontrollable fields" discussed in the examples.

[0021] According to a second aspect, the invention relates to the use of the method of the invention in an MultiPath TCP-enabled network.

[0022] According to a third aspect, the invention relates to a sender for sending a packet to a receiver in a data communication network comprising means for performing the steps performed by the sender in the method of the invention. These means may be implemented e.g. in electronics or in software.

[0023] According to a fourth aspect, the invention relates to a router for routing a packet to a receiver in a data communication network comprising means for performing the steps performed by the router in the method of the invention. These means may be implemented e.g. in electronics or in software.

[0024] According to a fifth aspect, the invention relates to a network comprising one or more senders according to the invention and/or one or more routers according to the invention.

[0025] According to a sixth aspect, the invention relates to a software comprising means for performing the steps performed by the sender in the invention and/or for performing the steps performed by the router in the invention. BRIEF DESCRIPTION OF THE DRAWING

[0026] Fig.1 a schematic view of an example network wherein the invention may be deployed.

[0027] Fig.2 illustrates schematically the steps of the method of the invention performed in a sender.

[0028] Fig.3 illustrates schematically the steps of the method of the invention performed in a router.

[0029] Fig.4 illustrates deviations from an optimal distribution amongst two possible next-hops.

DETAILED DESCRIPTION OF THE INVENTION

[0030] A schematic representation of all possible paths between a sender S and a destination D in an exemplary network is shown in Fig. 1 . A set of routers according to the invention R1 , R2, ... R8 may transport data packets along possible hops from a router to a next one shown as arrows. Routers R1 and R3 have two available next hops, and therefore these routers may select two possible next hops for an incoming data packet. Similarly, router R4 has three available next hops. In this example there exist five different load-balanced paths between nodes S and D.

[0031] In an example embodiment, the method of the invention is decomposed in four separate operations. First, the desired path is specified as a sequence of next-hop selections by the sender, that we call a path selector. This path selector is then encoded inside selected header fields of the packets. We call these header fields controllable fields. Third, each router recovers from these fields the encoded path selector and, finally, the load- balanced next-hop selection it needs to apply on this packet. These four operations allow senders according to the invention to steer their packets inside the network. In this example, we focus on IPv4 and use the source and destination ports as controllable fields, i.e., they are used to encode the path selector. We also define uncontrollable fields that are used to add randomness in the forwarding process of packets from senders not according to the invention. With IPv4, these uncontrollable fields may include the source and destination IP addresses and the protocol number. The example embodiment starts from two assumptions. First, the same encoding function is used on all devices (senders or routers) inside the network. Second, the network topology is available to the sender, either directly or through a network information such as ALTO . From this network topology, it is possible to compute all the load-balanced paths for a given sender-destination pair. In the following, we first describe how the method represents a path as a path selector and how a router retrieves from a path selector the next-hop selection it needs to apply. Second, we discuss how to encode the path selector inside the packet header. Then, we discuss the load-balancing distribution of packets passing through routers and how the invention avoids polarization. Finally, we summarize the complete operations of the invention.

[0032] The path selector is encoded in the controllable field of the header. Designating the length in bits of this controllable field by X, a simple embodiment of the invention divides these X bits in a number L of subfields of equal length. However, in order to maximize the number of next hops selections that can be encoded inside a path selector having a limited length X in bits, a preferred embodiment of the invention encodes the path selector using a lossless compression. An example of an applicable lossless compression is as follows:

[0033] The following definitions are used in the description of this preferred embodiment:

B The radix of the path selector, i.e., the numeral base to encode the path selector,

n. The next-hop selection of the i^th router.

L The length of the path selector, i.e., number of next-hop

selections that can be encoded in it.

N_r The number of next hops available for a router r that needs to forward a packet.

N_r(d) The number of load-balanced next hops N_r on router r for the destination prefix d.

F(x) An invertible function applied on x.

H(x) A Hash function applied on x.

Uf The uncontrollable fields used.

Ej(nj) A function applied on a next-hop selection. It allows to add

randomness using u_f to the next-hop selection.

Dj(p) A function that performs the inverse of E,, i.e., x = Dj(Ej(x)) Vx

≡ [0,B[.

A||B The concatenation of A and B.

[0034] A load-balanced path in a network can be described as a set of successive routers and their next-hop selections. For instance, the load balanced path highlighted in bold in Fig. 1 can be expressed as the following sequence: {R1 → R2,R4→ R7}, where Ri→ Rj means that Ri forwards the packet to Rj . There is no need to represent the next-hop selection of router R7 towards D as R7 only has one possible next hop. By knowing the number N_r of available next hops towards a destination for each router r in the network, next-hop selections can be mapped to a number n ≡ [0,N_r[, where n indicates the index of the next hop which should be selected. By using this representation, the highlighted path in Fig. 1 can therefore be expressed as the following sequence of next-hop selections: {1 → 0, 3→ 2}, where i→ j specifies that the i^th router on the path selects the j^th next hop. We define this sequence of next-hop selections to be a path selector.

Path Selector Representation.

[0035] To force a packet to follow a specific load-balanced path, the sender encodes the path selector inside the source and destination ports of the packet headers. The sender may store a path selector as a positional base-B unsigned integer, where B is known as the radix and shared by all the nodes in the network. This allows maximizing the number of next-hop selections that can be encoded inside the path selector, while minimizing the number of bits used. For a specific load-balanced path in the network, the path selector p can be generalized as:

i=0

where n, is an unsigned integer in base B that represents the next-hop selections of the i^th router on the path. For the moment, we assume that each router is able to determine its position in the path selector. Only routers having multiple load-balanced next hops to forward a packet must retrieve the path selector. In this case, the router first extracts the path selector p from the packet's header fields and then retrieves the next-hop selection.

A path selector p can be inverted on the i^th router on the path to find the next- hop selection n, it needs to 4 apply on a packet by applying Eq. 2: = P

mod B (2) wherein the L and J represent the integer division. The integer division by B, removes all load-balanced next-hop selections of upstream routers while the modulo operation removes all load-balanced next-hop selections of downstream routers.

Path Selector Length.

[0036] The fixed size of the packet header fields used to encode the path selector limits the number of encodable next hop selections to:

where X is the size in bits of the header fields used to encode the path selector. With IPv4, X = 32 since the ports are used to convey the path selector. Increasing B decreases L, thus the number of load balanced next- hop selections that can be encoded inside the path selector. As the potential value of n, is limited by the radix B, one should choose a B value so that it is the maximum degree in every possible network (for each possible destination prefix). It can be expressed as:

B = rnax(N_r(d)) ¥ r, d (⁴)

It is possible to represent for any router r in the network a next-hop selection n with a value which is lower than the maximum number of available next hops at any router in the network. In practice, most routers have a hardcoded upper bound on the number of next hops they can use for a destination, most of them use a maximum of 16 next hops .

Using a radix which is equal to the maximum number of next hops N_r for all routers might end up in an inefficient usage of the available bits in the packet header. Relaxing the problem by allowing routers to use more that one position inside the path selector would give more flexibility on the load- balanced next-hop selection values that can be encoded at the source. For instance, if a router uses 3 positions of the path selector, then a sender can use n≡ [0, 3 χ B[ to represent the next-hop selection of this router.

Position Inside the Path Selector.

[0037] Up to now, we assumed that each router knows its position inside the path selector. However, in a real world scenario it is impossible for a router to identify the sequence of upstream routers thus making impossible to know its position inside the path selector. To still enable a sender to construct a path selector and for routers to extract corresponding next-hop selections, the method may use the Time-to-Live (TTL) of the packet to identify each router's position inside the path selector. As the TTL is decremented by each router and as the path selector is bounded by L, we can define the position of each routerto be

i : = ttli mod L, where ttl, is the TTL value of the packet received at the i router. The sender can, by knowing the initial TTL of the packets, encode the next-hop selection of each router on the path at the corresponding position inside the path selector. As previously mentioned, to allow a router to use more than one position inside the path selector, the router must decrement the TTL of the packets it forwards more than one time.

One Load-Balanced Path - Multiple Path Selectors.

[0038] When multiple connections between the same pair of hosts want their packets to follow the same load balanced path, using the same path selector generates a collision as each connection will use the same port numbers. To overcome this issue, the method may allow to generate multiple path selectors to describe the same load balanced path using two solutions that can be combined. First, the unused positions inside the path selector can be filled with random values. Second, by changing the initial TTL, the position of each router in the path selector changes and thus the pair of ports used to force a specific load-balanced path. This ensures that the 5-tuple used by the hosts varies from one connection to another. Example.

[0039] Let us now illustrate how the method works in the simple network shown in Fig. 1 . First, based on Eq. 3, we can deduce that the radix B must be 3. Using this radix, from Eq. 3, we can encode 20 load-balanced next-hop selections inside a path selector. Let us assume that the sender uses an initial TTL of 64 and wants this packet to follow the highlighted path in Fig. 1 . The positions of the next-hop selections of routers R1 and R4 inside the path selector are respectively 4 (64 mod 20) and 2 (62 mod 20). The path selector computed by the sender based on Eq. 1 can therefore be expressed as: p = {4→0, 2→2} = 0 x 3⁴ + 2 x 3² = 18

Note that this implies encoding a next-hop selection of 0 for all other positions inside the path selector. This value is then encoded inside the packet header. R1 retrieves from the packet header the same path selector and the TTL value to compute its position inside the path selector, i.e., 4. It then computes the next-hop selection it needs to apply on the packet based on Eq. 2:

W4 mod 3

Q4

R1 decrements the TTL of the packet and forwards it to the next hop labeled 0, i.e., R2. R2 does not have load-balanced next hops. It forwards the packet to R4 and decrements the TTL. R4 applies the same operation as R1 . R4 computes:

The packet is therefore forwarded to R7 and then to D as R7 only has one possible next hop to forward the packet.

Invertible Function

[0040] According to the method of the invention, the path selector is encoded inside the packet header using an invertible function F. This invertible function should meet two properties:

- Bijection:

F should be bijective such that there is a one-to-one correspondence between its domain and image which must be a sequence of bits of length X, {0, 1 }^x , where X is the length in bits of the controllable fields. F must also be invertible, i.e.,

3 F^~1 that is the inverse of F such that: F^"1 (F(x)) = x Vx e {0,

1 }^X

- Avalanche effect:

F must exhibit the avalanche effect . Indeed, a simple bijective function might end up in a poor distribution of the traffic . For instance, if only the port numbers are used as controllable fields, we do not want that all web traffic goes through the same next hop. Therefore, we require that the invertible function exhibits the avalanche effect, that is for a small variation of the input (different source-ports) a large variation of the output is observed. A large number of output bits (40% or even 50%) should change for a single input bit change.

Based on these two requirements, block ciphers such as Skip32 or RC5 are good candidates to implement this invertible function when 32 bits are controllable. Skip32 is a 32 bit block cipher based on SKIPJACK and available from http://www.qualcomm.com.aU/PublicationsDocs/skip32.c. RC5 is another block cipher described in R. L. Rivest "The RC5 Encryption Algorithm" Proc. FSE, volume 1008, pages 86-96, 1994. Using such functions to encode the path selector enables a router to apply the inverse of this function on the controllable fields of the packet header to retrieve the path selector.

[0041] Fig.2 illustrates schematically the steps of the method of the invention performed in the sender. The identities of the different paths to be selected are grouped in the path selector p. Optionally, a hash function H is applied to the "uncontrollable fields", which are, in the example shown, the IP source, the IP destination, the protocol and the TTL (Time-to-live counter) The inverse of the function F is applied to the result and stored in the "controllable fields" of the header (the source port and destination port fields in the example shown)

[0042] Fig.3 illustrates schematically the steps of the method of the invention performed in a router. The function F is applied to the "controllable fields" (source port and destination port in the example shown) and provides the path selector p. The TTL may be used as an index in the path selector for retrieving the applicable next hop. Optionally, the same hash function H is applied to the same "uncontrollable fields" (in the example shown, the IP source, the IP destination, the protocol and the TTL). Te result thereof is added to the applicable element of the path selector for obtaining the applicable next hop.

[0043] The pseudocode showing the operations performed by a router that has multiple paths available to forward a packet is as follows: Network-wide constant: X = The number of bits of the controllable fields in the packet header.

Input: pckt = The packet to forward.

Output: The next-hop selection to apply on pckt.

H is a hash function

1 : L <- L logB(2^x) J

2: Cf ExtractControllableFields(pckt)

3: u_f <— ExtractUncontrollableFields(pckt)

4: ttl <- ExtractTTL(pckt)

5: p ^ F¹ (cb)

6: ni <- L p/ B^{(ttl mod L)} J -H(u_f || ttl) mod L

7: if n, < Ni then

8: return n,

9: else

10: return H(u_f II c_f II ttl) mod Ni

1 1 : end if [0044] The Pseudocode showing the path selector

Construction:

Input: path = A set (tt^n,), where ttl, is the TTL of the packet when received by router i on the path and ni the next-hop selection that should be undertaken by router i.

Input: Uf = The uncontrollable fields the source needs to use to send a packet.

Output: The path selector to use to force a packet to follow the path using the uncontrollable fields Uf .

H is a hash function

1 : L <- L logB(2^A) J 2: p ^ O

3: for (ttlj, rij)≡ path do

4: p <- p + (rii +H(u_f || ttlj) mod B) x B^{(ttl mod L)}

5: end for

6: return p

[0045] Fig.4 shows the results obtained by the applicant when performing simulations comparing methods according the inventions and known methods. The graph shows the cumulative distribution function CDF [%] in function of the load repartition [% packets] for deviations from an optimal distribution 50%/50% amongst two possible next-hops. The two first curves starting from the left of the graph are for methods according to the invention (Controllable per-Flow Load Balancing CFLB) using block ciphers Skip32 and RC5 respectively. The third and fourth curves represent the results obtained with known hash-based load balancers MD5 and CRC16 respectively. Each method was simulated using realistic traces and evaluated the fraction of packets forwarded to each next hop. The simulations were based on the CAIDA passive traces collected in July 2008 at an Equinix data center in San Jose, CA (SHANNON, C, ABEN, E., CLAFFY, K., AND ANDERSEN, D. The CAIDA Anonymized 2008 Internet Traces - 2008-07-17 12:59:07 - 2008-07-1714:01 :00. http://www.caida.org/data/passive/passive_2008_dataset.xml) To analyze how the method of the invention balances the non-controlled traffic compared to hash-based techniques, 10 million packets (extracted from the CAIDA traces) were forwarded through one load balancer performing a distribution among N = 2 next hops using either methods according to the invention or classical hash functions . Fig. 4 shows the result of this simulation (computed every second). There are three observations resulting from Fig. 4. First, using CRC16 as a hash-based load balancer gives a rather poor distribution of packets. Second, as the maximum deviation value never goes up to 4% of packets, the load distribution among the two output links is close to an equal 50/50 % repartition of traffic for all evaluated techniques except CRC16. Third, the methods according to the invention, (CFLB-Skip32 and CFLB-RC5) whatever the block cipher used, achieve an equivalent load distribution as a hash-based load balancer using MD5. The applicant did not observe a significant impact on the quality of the load distribution according to the B (radix of the path selector) value used. In conclusion, it was shown that the method according to the invention allows obtaining a good load balancing in a controllable way.

[0046] It has been experienced that the invention can be used advantageously in a MultiPath TCP-enabled network. MultiPath TCP (MPTCP) is an extension to TCP that splits a data stream over multiple TCP subflows while still presenting a standard TCP socket API to applications (FORD, A., RAICIU, C, HANDLEY, M., AND BONAVENTURE, O. TCP Extensions for Multipath Operation with Multiple Addresses. Internet draft, draft-ietf-mptcp-multiaddressed-09, IETF, June 2012.). MultiPath TCP associates each TCP subflow (identified by its 5-tuple) to its MPTCP-session identified by a token which is exchanged within the first subflow establishment. The token enables the use of any arbitrary port number in subsequent new TCP subflows, as the token uniquely associates the TCP subflow to its corresponding MPTCP session and not the 5-tuple. If MultiPath TCP is used, the source and destination port of the TCP header can thus be used as controllable bits in the method of the invention allowing the latter to encode more next-hop selections within the path selector.

[0047] The terms and descriptions used herein are set forth by way of illustration only and are not meant as limitations. Those skilled in the art will recognize that many variations are possible within the spirit and scope of the invention as defined in the following claims, and their equivalents, in which all terms are to be understood in their broadest possible sense unless otherwise indicated. More specifically, the examples above are given in the context of an IPv4, but the invention applies as well to IPv6 networks, MPLS networks, and TRILL networks. As a consequence, all modifications and alterations will occur to others upon reading and understanding the previous description of the invention. In particular, dimensions, materials, and other parameters, given in the above description may vary depending on the needs of the application.

[0048] The work leading to this invention has received funding from the European Union Seventh Framework Programme (FP7) under grant agreement n ° 257422.

Claims

1. A method for sending a packet, said packet comprising a header, from a sender to a receiver in a data communication network comprising one or more routers, one or more routers having two or more available next hops leading to said receiver,

characterized in that :

- a function F encoding a sequence of X bits into another sequence of X bits is selected, said function being invertible;

- the sender performs the steps of

- selecting a preferred next hop for each of said one or more routers;

- grouping each of said preferred next hops in a path selector, said path selector having a length X in bits ;

- applying the inverse of said function F to said path selector and storing the result in a first subset of said header;

- sending said packet across said data communication network;

- one router of the one or more routers performs the steps of

- applying said function F to said first subset of said header for obtaining the original path selector;

- extracting from said path selector the preferred next hop selected by the sender for said one router;

- sending said packet through said preferred next hop.

2. The method of claim 1 characterized in that said function F is selected among the functions where at least 40% of the output bits change wherever a single bit in the input is changed.

3. The method according to any of preceding claims characterized in that said function F is selected among the functions where at least 50% of the output bits change wherever a single bit in the input is changed.

4. The method according to any of preceding claims wherein

- the sender initiates a counter TTL and stores said counter in a second subset of said packet header;

- each successive router in the network receiving a packet decrements said counter TTL;

characterized in that

- a router having two or more available next hops uses said counter for extracting from said path selector the preferred next hop selected by the sender for said one router.

5. The method according to any of preceding claims characterized in that said grouping of each of said preferred next hops in a path selector is performed by a lossless compression method.

6. The method according to any of preceding claims characterized in that said function is a block cipher selected from a group comprising Skip32 and RC5.

7. The method according to any of preceding claims characterized in that said first subset of said header is selected among the group comprising the source port and the destination port.

8. The method according claim 7 characterized in that the group further comprises the source address or a subset thereof, the destination address or a subset thereof, a flow label and an MPLS label.

9. The method according to any of preceding claims characterized in that

- the sender further computes a hash function based on a third subset of said header and adds said hash function to each of said preferred next hops grouped in said path selector;

- the router further computes the same hash function based on said third subset of said header and adds said hash function to each of said preferred next hops extracted from said path selector.

10. Use of the method of any of claims 1 to 9 in an MultiPath TCP-enabled network.

11. A sender for sending a packet to a receiver in a data communication network characterized in that it comprises means for performing the steps performed by the sender in the method of any of claims 1 to 9.

12. A router for routing a packet to a receiver in a data communication network characterized in that it comprises means for performing the steps performed by the router in the method of any of claims 1 to 9.

13. A network comprising one or more senders according to claim 1 1 and/or one or more routers according to claim 12.

14. A software comprising means for performing the steps performed by the sender in the method of any of claims 1 to 9 and/or for performing the steps performed by the router in the method of any of claims 1 to 9.