METHOD AND SYSTEM FOR CONFIGURING AN AUTONOMOUS SYSTEM

Abstract

A method for configuring a first autonomous system in a transit network is described. The method includes obtaining information according to which the traffic received by an ingress router of the first autonomous system is saturated, and determining a prefix of a destination subnet of a third autonomous system downstream of the first autonomous system. The method also includes extending the path associated with the prefix on at least one target router of the first autonomous system, the prefix and the at least one target router being determined by optimizing an objective function so that the path associated with the prefix must be extended for all the ingress routers of the first autonomous system which are geographically closer to the saturated router than the target router.

Claims

1. A method for configuring a first autonomous system in a transit network, the method including: obtaining information according to which traffic received by an ingress router of said first autonomous system is saturated, said traffic being received from at least one egress router of a second autonomous system upstream of said first autonomous system; determining a prefix of a destination subnet of a third autonomous system downstream of said first autonomous system, at least part of said traffic being destined for equipment of said destination subnet; extending a path associated with said prefix on at least one target router among ingress routers of said first autonomous system, said prefix and said at least one target router being determined by optimizing an objective function in compliance with at least these constraints, according to which: (i) for any ingress router of the first autonomous system, the traffic at the input of said router is below a saturation threshold; and (ii) the path associated with said prefix must be extended for all the ingress routers of the first autonomous system which are geographically closer to the saturated router than said target router.

2. The method of claim 1, wherein extending the path associated with said prefix on at least one said target router includes: reconfiguring a routing table of said target router by adding at least one autonomous system to an AS-Path attribute of the BGP protocol; and sending said attribute to at least one egress router of said second upstream autonomous system.

3. The method of claim 1, wherein optimizing the objective function comprises minimizing a number of ingress routers to be reconfigured.

4. The method of claim 1, wherein optimizing the objective function comprises minimizing a number of prefixes whose path is extended, or in minimizing a load of the most loaded interface.

5. The method of claim 1, wherein: said objective function is a linear function of the form: Min ?j?J z.sub.j, and said constraints are linearly expressed in the form: TABLE-US-00009 CST1: ?.sub.k?J x.sub.ijk = 1 ?i ? I, ?j ? J CST2: x.sub.ijk + y.sub.ik ? 1 ?i ? I, ?j ? J, ?k ? J CST3: x.sub.ijk ? y.sub.il ?i ? I, ?j ? J, ?k ? J, ?l ? L(j, k) CST4: ?.sub.i?I ?.sub.j?J p.sub.ijtx.sub.ijk ? c.sup.max b.sub.k ?k ? J, ?t ? T CST5: y.sub.ij ? z.sub.j ?i ? I, ?j ? J wherein: c.sup.max is a saturation threshold and b.sub.j is a maximum throughput supported by the saturated router; p.sub.ijt is a peak traffic associated with the prefix i on an interface j during a time range t; Lj is an ordered list of the ingress routers of the first autonomous system from closest to farthest from the saturated router; L(j,k) is a sub-list of Lj comprising the ingress routers of the first autonomous system which are geographically closer to the saturated router than said target router; x.sub.ijk is a binary decision variable equal to 1 if the traffic associated with the prefix i is routed from an ingress router to a target router, and equal to 0 if the traffic associated with the prefix i is not routed from an ingress router to a target router; y.sub.ij is a binary decision variable equal to 1 if the path associated with the prefix i is extended on an ingress router, and equal to 0 if the path associated with the prefix i is not extended on an ingress router; and z.sub.j is a binary decision variable equal to 1 if the ingress router is reconfigured, and equal to 0 if the ingress router is not reconfigured.

6. A system for configuring a first autonomous system in a transit network, the system including: an optimization unit configured to obtain information according to which traffic received by an ingress router of a first autonomous system is saturated, said traffic being received from at least one egress router of a second autonomous system upstream of said first autonomous system, said optimization unit being configured to determine a prefix of a destination subnet of a third autonomous system downstream of said first autonomous system, at least part of said traffic being destined for equipment of said destination subnet; a control unit configured to extend a path associated with said prefix on at least one target router among ingress routers of said first autonomous system, said prefix and said at least one target router being determined by said optimization unit by optimizing an objective function in compliance with at least these constraints, according to which: (i) for any ingress router of the first autonomous system, the traffic at the input of said router is below a saturation threshold; and (ii) the path associated with said prefix must be extended for all the ingress routers of the first autonomous system which are geographically closer to the saturated router than said target router.

7. A non-transitory computer readable medium having stored thereon instructions which when executed by a processor, cause the processor to implement the steps of: obtaining information according to which traffic received by an ingress router of a first autonomous system is saturated, said traffic being received from at least one egress router of a second autonomous system upstream of said first autonomous system; determining a prefix of a destination subnet of a third autonomous system downstream of said first autonomous system, at least part of said traffic being destined for equipment of said destination subnet; and sending an instruction to extend a path associated with said prefix on at least one target router among ingress routers of said first autonomous system, said prefix and said at least one target router REk being determined by optimizing an objective function in compliance with at least these constraints, according to which: (i) for any ingress router of the first autonomous system, the traffic at the input of said router is below a saturation threshold; and (ii) the path associated with said prefix must be extended for all the ingress routers of the first autonomous system which are geographically closer to the saturated router than said target router.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0057] Other characteristics and advantages of the disclosed technology will emerge from the description given below, with reference to the appended drawings which illustrate exemplary embodiments devoid of any limitation.

[0058] FIG. 1 illustrates one exemplary implementation of a load balancing system in accordance with one particular embodiment of the disclosed technology.

[0059] FIG. 2 represents the main steps of a configuration method system in accordance with one embodiment of the disclosed technology.

DETAILED DESCRIPTION

[0060] FIG. 1 illustrates in detail one exemplary implementation of a load balancing system 100 in accordance with the disclosed technology.

[0061] In the embodiment described here, the load balancing system 100 includes a collection unit DC, an optimization OPT unit and a controller CTR.

[0062] In the embodiment of FIG. 1, these three entities are separated. As a variant, at least two of them can be integrated into the same equipment. They can be co-located or linked together by a network of any nature.

[0063] In the example described here, a first autonomous system AS1 includes three egress routers RS1, RS2, RS3, and a second autonomous system AS2, upstream of the first autonomous system AS1, includes three ingress routers RE1, RE2, RE3.

[0064] In the example described here, each egress router RSi is connected with the ingress router REi (of the same index).

[0065] Moreover, in the example of FIG. 1, the egress router RS1 is connected within the autonomous system AS1 to the egress router AS2, itself connected to the egress router RS3. The egress router RS1 therefore has two possibilities to send a packet to the destination subnet SRD1: [0066] either route this packet to the ingress router RE1, [0067] or route it to the egress router RS2, which can in turn either route it to the ingress router RE2, or to the egress router RS3, the latter then routing it to the ingress router RE3.

[0068] In the exemplary embodiment described here, it is assumed that the three ingress routers RE1, RE2, RE3 of the autonomous system AS2 are located respectively in Paris, London and Amsterdam.

[0069] In the example described here, the autonomous system AS3 includes two destination subnets SRD1, SRD2 and other destination subnets not represented.

[0070] Each of these autonomous systems ASi further includes a set Ei of routers R.

[0071] The addresses of the equipment of the same destination subnet have the same prefix.

[0072] For example: [0073] the destination subnet SRD1 contains the IP address range 10.0.0.0 to 10.0.0.255, and its prefix can be noted 10.0.0.0/24; and [0074] the destination subnet SRD2 contains the IP address range 20.0.0.0 to 20.0.0.255, and its prefix can be noted 20.0.0.0/24.

[0075] In accordance with the BGP protocol, each ingress router of the first autonomous system AS2 manages a routing table, which comprises, for each destination subnet to which it can route traffic, an AS-Path attribute which lists the autonomous system(s) that a packet must go through to reach this subnet. For example, the routing table for the ingress router RE1 includes two records: [0076] SRD1: AS-Path: AS2, AS3 [0077] SRD2: AS-Path: AS2, AS3

[0078] In accordance with the BGP protocol, the ingress router RE1 (respectively RE2, RE3) announces to the egress router RS1 (respectively RS2, and RS3) of the autonomous system AS1 that it is capable of routing the traffic to the destination subnets SRD1 and SRD2, this message including this information from its routing table, and in particular how far they are from each of these subnets. This distance is specific to the operation of the IP routing and does not correspond to a geographic distance. To distinguish it from a geographic distance, this distance will be called routing distance.

[0079] For example, the ingress router RE1 sends to the egress router RS1 two messages of the type UPDATE (SRD1, AS2, AS3) and UPDATE (SRD2, AS2, AS3) to indicate that it can route traffic to the destination subnet SRD1 (respectively SRD2) and that it is at a routing distance of two autonomous systems (in this case AS2, AS3) from the destination subnet SRD1 (respectively SRD2).

[0080] In the exemplary embodiment described here, the ingress router RE2 (respectively RE3) makes the same announcements to the egress router RS2 (respectively RS3).

[0081] FIG. 2 represents the main steps of a configuration method in accordance with one embodiment of the disclosed technology.

[0082] The balancing method includes a general step E10 of collecting data representative of the traffic received as input by the ingress routers RE1, RE2, RE3 of the autonomous system AS2.

[0083] If the collection of the data cannot be done simultaneously on all the prefixes, it can be done in time slots in groups of prefixes.

[0084] In the embodiment described here, these data make it possible in particular to determine: [0085] the peak throughput, in other words the maximum throughput, at the input of an ingress router during a time range; and [0086] the peak throughput corresponding to the packets of a destination subnet SRDi, in other words to the traffic associated with a given prefix over a time range.

[0087] In the exemplary implementation described here, two time ranges, i.e. for example the morning and the evening will be considered.

[0088] The notations used below are introduced using an example.

[0089] In the embodiment described here, 2 destination subnets SRD1, SRD2, noted SRDi, i.e. 2 prefixes i=1 to 2 are considered.

[0090] In the exemplary embodiment described here, the system includes 3 ingress routers RE1, RE2, RE3, in other words 3 interfaces j=1 to 3.

[0091] In the exemplary embodiment described here, 2 time ranges t=1 to 2 are considered.

[0092] p.sub.ijt denotes the peak traffic associated with the prefix i on the interface j during the time range t.

[0093] To illustrate the description, it is assumed that the nominal situation is that of table T1 in the Annex.

[0094] For example, for the router RE1, interface j=1, located in Paris: [0095] the maximum throughput in the morning (t=1) to the subnet SDR1 (prefix i=1), noted p.sub.111, is 3 Gbps; [0096] the maximum throughput in the morning (t=1) to SDR2 (i=2), noted p.sub.211, is 2 Gbps; [0097] the maximum throughput in the evening (t=2) to SDR1 (i=1), noted p.sub.112, is 6 Gbps; [0098] the maximum throughput in the evening (t=2) to SDR2 (i=2), noted p.sub.212, is 4 Gbps. DT.sub.jt denotes the maximum cumulative throughput on the interface j during the time range t.

[0099] Cj denotes the load on the interface j, defined as the ratio between the maximum throughput over one or more time ranges and the maximum throughput b.sub.j supported by this interface (assumed equal to 100 Gbps for all the interfaces below).

[0100] In the example of table T1, it is considered that the maximum throughput in the morning (t=1) at the input of the interface 1 (router RE1), noted DT.sub.11, is 80 Gbps; and that in the evening, this maximum throughput is DT.sub.12=93 Gbps. The load C.sub.1 of the router RE1 is therefore 93%.

[0101] The configuration method includes a step E20 to determine whether the traffic at the input of an ingress router REj of the autonomous system AS2 is saturated. In the embodiment described here, this determination is made by comparing the load of the router REj with a saturation threshold c.sup.max.

[0102] In the example described here, the saturation threshold c.sup.max is equal to 90%.

[0103] In the example of Table T1, the ingress router RE1 (or the interface 1) is determined to be saturated because C1 (93%) is greater than c.sup.max.

[0104] When an ingress router REj is determined to be saturated, the result of the test E20 is positive.

[0105] The disclosed technology proposes to rebalance the load by extending the path associated with a prefix on this saturated router, the disclosed technology assuming that when an egress router of the autonomous system AS1 learns that the path associated with a prefix is extended on an ingress router REj, it moves the traffic associated with this prefix on the ingress router REk of the autonomous system AS2 geographically closest to REj.

[0106] Table TD in the annex presents the geographical distances between Paris (PAR), London (LON) and Amsterdam (AMS).

[0107] For an ingress router REj, in other words for an interface j, Lj denotes the ordered list of the ingress routers REk (interfaces k), from closest to farthest from the interface j.

[0108] In this example: L1={1, 2, 3}, L2={2, 1, 3}, L3={3, 2, 1}.

[0109] In one embodiment of the disclosed technology, to extend the path associated with a prefix i on an ingress router REk (interface k), this router REk is reconfigured by adding to the attribute AS PATH of the BGP protocol an autonomous system in the list of the autonomous systems to go through to reach the destination subnet SRDi associated with this prefix.

[0110] For example, in the example described here, to extend the path associated with the prefix i=1 on the ingress router RE1, the record of the routing table of the ingress router RE1 associated with this prefix can be modified: [0111] SRD1: AS-Path: AS2, AS2, AS3

[0112] This configuration can be done by the controller CTR.

[0113] In accordance with the BGP protocol, the ingress router REi whose routing table has been modified announces this reconfiguration to the upstream egress router to which it is connected.

[0114] In this example, the ingress router RE1 sends to the egress router RS1 two messages of type UPDATE (SRD1, AS2, AS2, AS3).

[0115] The egress router RS1 takes note of this attribute change and chooses to route the traffic associated with the destination subnet SRDi (for example here SRD1) to another ingress router of the autonomous system AS2 offering a shorter BGP route towards this destination subnet.

[0116] Indeed, in the diagram of FIG. 1, the egress router RS1 has two possibilities to send a packet to the destination subnet SRD1: [0117] either route this packet to the ingress router RE1 that has announced the route AS2, AS2, AS3 (routing distance equal to 3 AS), [0118] or route this packet to the egress router RS2 which routes it to the ingress router RE2 that has announced the route AS2, AS2 (routing distance equal to 2 AS)

[0119] In this example, the second option which is the shortest will then be chosen.

[0120] Using the example of table T1, the effect of extension of the path associated with the prefix i=1, then with the prefix i=2 will be detailed below.

Extension of the Path Associated with the Prefix i=1

[0121] Table T2 in the Annex thus illustrates the throughputs at the input of each of the ingress routers RE1, RE2, RE3 assuming that the path associated with the prefix i=1 is extended on the router RE1.

[0122] In accordance with the disclosed technology, it is assumed that this path extension has the effect that the traffic associated with the prefix i=1 will be moved on the geographically closest interface, i.e. RE2 (see list L1). Consequently, if this is the case: [0123] the throughput p.sub.111 associated with the prefix i=1 at the input of the interface j=1 for the time range t=1 becomes 0, the entire associated traffic being routed on the interface 2; [0124] the total throughput DT.sub.11 is reduced by 3 Gbps; [0125] the throughput p.sub.121 associated with the prefix i=1 at the input of the interface j=2 which was 10 Gbps in the range t=1 is increased by 3 Gbps and becomes 13 Gbps; the total throughput DT.sub.21 is also increased by 3 Gbps; [0126] the throughput p.sub.112 associated with the prefix i=1 at the input of the interface j=1 for the time range t=2 becomes 0, the entire associated traffic being routed on the interface 2; the total throughput DT.sub.12 is reduced by 6 Gbps; the load C.sub.1 on the interface 1 is then 87%, below the threshold c.sup.max; [0127] the throughput p.sub.122 associated with the prefix i=1 at the input of the interface j=2 which was 20 Gbps in the range t=2 is increased by 6 Gbps and becomes 26 Gbps; the total throughput DT.sub.22 at the input of the router RE2 is also increased by 6 Gbps and becomes 94 Gbps.

[0128] It is seen that the load C.sub.2 of the ingress router RE2 of 94% then exceeds the saturation threshold C.sup.max.

[0129] It is now assumed that the path associated with the prefix i=1 is also extended on the ingress router RE2 and that this path extension has the effect that the traffic associated with the prefix i=1 will be moved on the interface geographically closest to RE2, that is to say towards RE3 (see list L1).

[0130] Table T3 in the Annex illustrates the throughputs at the input of each of the ingress routers RE1, RE2, RE3 assuming that the throughput associated with the prefix i=1 is extended on the routers RE1 and RE2 and is therefore routed on the ingress router RE3. In particular: [0131] the throughput p.sub.121 associated with the prefix i=1 at the input of the interface j=2 for the time range t=1 becomes 0, the entire associated traffic being routed on the interface 3; the total throughput DT.sub.11 is reduced by 13 Gbps; [0132] the throughput p.sub.131 associated with the prefix i=1 at the input of the interface j=3 which was 2 Gbps in the range t=1 is increased by 13 Gbps and becomes 15 Gbps; the total throughput DT.sub.31 is also increased by 13 Gbps; [0133] the throughput p.sub.122 associated with the prefix i=1 at the input of the interface j=2 for the time range t=2 becomes 0, the entire associated traffic being routed on the interface 3; the total throughput DT.sub.22 is reduced by 26 Gbps; the load C.sub.1 on the interface 2 is then 70%, below the threshold c.sup.max; [0134] the throughput p.sub.132 associated with the prefix i=1 at the input of the interface j=3 which was 2 Gbps in the range t=3 is increased by 26 Gbps and becomes 28 Gbps; the total throughput DT.sub.32 at the input of the router RE2 is also increased by 26 Gbps and becomes 96 Gbps.

[0135] It is seen that the load C.sub.3 of the ingress router RE3 of 94% exceeds the saturation threshold c.sup.max of 90%.

[0136] In this example, it is not possible to route the ingress traffic on another ingress router of the autonomous system AS2.

[0137] Consequently, the extension of the paths associated with the prefix i=1 on the ingress routers RE1, RE2 does not make it possible to avoid the saturation phenomenon addressed by the disclosed technology.

Extension of the Path Associated with the Prefix i=2

[0138] Table T4 in the Annex thus illustrates the throughputs at the input of each of the ingress routers RE1, RE2, RE3 assuming that the path associated with the prefix i=2 is extended on the router RE1, and that this traffic is routed to the ingress router RE2. In particular: [0139] the throughput p.sub.211 associated with the prefix i=2 at the input of the interface j=1 for the time range t=1 becomes 0, the entire associated traffic being routed on the interface 2; the total throughput DT.sub.11 is reduced by 3 Gbps; [0140] the throughput p.sub.221 associated with the prefix i=2 at the input of the interface j=2 which was 3 Gbps in the range t=1 is increased by 2 Gbps and becomes 5 Gbps; the total throughput DT.sub.21 is also increased by 2 Gbps; [0141] the throughput p.sub.212 associated with the prefix i=2 at the input of the interface j=1 for the time range t=2 becomes 0, the entire associated traffic being routed on the interface 2; the total throughput DT.sub.12 is reduced by 4 Gbps; the load C.sub.1 on the interface 1 is then 89%, below the threshold c.sup.max; [0142] the throughput p.sub.222 associated with the prefix i=2 at the input of the interface j=2 which was 3 Gbps in the range t=2 is increased by 4 Gbps and becomes 7 Gbps; the total throughput DT.sub.22 at the input of the router RE2 is also increased by 4 Gbps and becomes 92 Gbps.

[0143] It is seen that that the load C.sub.2 of the ingress router RE2 of 92% exceeds the saturation threshold C.sup.max of 90%.

[0144] It is now assumed that the path associated with the prefix i=2 is also extended on the ingress router RE2 and that this path extension has the effect that the traffic associated with the prefix i=2 is moved on the interface geographically closest to RE2 that is to say towards RE3.

[0145] Table T5 in the Annex thus illustrates the throughputs at the input of each of the ingress routers RE1, RE2, RE3 assuming that the throughput associated with the prefix i=2 is extended on the routers RE1 and RE2 and routed on the ingress router RE3. In particular: [0146] the throughput p.sub.221 associated with the prefix i=2 at the input of the interface j=2 for the time range t=1 becomes 0, the entire associated traffic being routed on the interface 3; the total throughput DT.sub.21 is reduced by 5 Gbps; [0147] the throughput p.sub.231 associated with the prefix i=2 at the input of the interface j=3 which was 5 Gbps in the range t=1 is increased by 5 Gbps and becomes 10 Gbps; the total throughput DT.sub.31 is also increased by 5 Gbps; [0148] the throughput p.sub.222 associated with the prefix i=2 at the input of the interface j=2 for the time range t=2 becomes 0, the entire associated traffic being routed on the interface 3; the total throughput DT.sub.22 is reduced by 7 Gbps; the load C.sub.2 on the interface 2 is then 85%, below the threshold c.sup.max; [0149] the throughput p.sub.232 associated with the prefix i=2 at the input of the interface j=3 which was 5 Gbps in the range t=2 is increased by 7 Gbps and becomes 12 Gbps; the total throughput DT.sub.32 at the input of the router RE2 is also increased by 7 Gbps and becomes 77 Gbps; the load C.sub.3 on the interface 2 is then 85%, below the threshold c.sup.max.

[0150] It is seen that that this load rebalancing by extension of the path associated with the prefix i=2 on the routers RE1 and RE2 leads to a situation in which none of the ingress routers RE1, RE2, RE3 are saturated.

[0151] Very advantageously, the configuration method according to the disclosed technology makes it possible to automatically determine a prefix (step E40) and the ingress routers of the autonomous system AS2 on which the paths associated with this prefix must be extended (step E50) so that traffic is rebalanced so that none of these ingress routers are saturated.

[0152] In accordance with the disclosed technology, this determination is done by optimizing an objective function FOBJ in compliance with a set of constraints.

[0153] In the embodiment described here, the optimization of the objective function FOBJ consists in minimizing the number of ingress routers (or interfaces) to be reconfigured.

[0154] In the embodiment described here, the optimization function meets 5 constraints: [0155] the first constraint CST1 imposes that the traffic associated with a prefix i is routed on one and only one ingress router; [0156] the second constraint CST2 prohibits triggering the routing of the traffic associated with a prefix i towards an ingress router REk while extending the path associated with this prefix on this ingress router; [0157] the third constraint CST3 imposes that if the traffic associated with a prefix i is switched from an ingress router REj to an ingress router REk, then the path associated with this prefix must be extended on all the ingress routers classified between these two routers REj (included) and REk (excluded) in the list Lj; [0158] the fourth constraint CST4 imposes that, whatever the time range t, all the incoming traffic on an ingress router REj must not exceed the saturation threshold C.sup.max; and [0159] the fifth constraint CST5 imposes that if at least one path associated with a prefix on an ingress router is extended, then this ingress router must be reconfigured.

[0160] In one embodiment of the disclosed technology, this optimization is implemented by the execution of a linear program, the objective function as well as the constraints being expressed in the form of linear functions with respect to decision variables.

[0161] In one embodiment, the following notations are introduced: [0162] p.sub.ijt: peak traffic associated with the prefix i on the interface j during a time period t. [0163] Lj: ordered list of the ingress routers of the first autonomous system from closest to farthest from the saturated router REj. [0164] L(j,k): sub-list of Lj comprising the ingress routers of the first autonomous system which are geographically closer to the saturated router REj than said target router REk. [0165] x.sub.ijk: binary decision variable equal to 1 if the traffic associated with the prefix i is rerouted from the interface j to the interface k, 0 if not; [0166] y.sub.ij is a binary decision variable equal to 1 if the prefix i has its path extended on the interface j, 0 if not. [0167] z.sub.j is a binary decision variable equal to 1 if the interface j is reconfigured, 0 if not.

[0168] The following notations are introduced: [0169] c.sup.max is a saturation threshold and b.sub.j is the maximum throughput supported by the router REj. [0170] x.sub.ijk is a binary decision variable equal to 1 if the traffic associated with the prefix i is routed from a router REi to a router REj, 0 if not; [0171] y.sub.ij is a binary decision variable equal to 1 if the path associated with the prefix i is extended on an ingress router REj, 0 if not; [0172] z.sub.j is a binary decision variable equal to 1 if the ingress router REi is reconfigured, 0 if not.

[0173] With these notations: [0174] the objective function FOBJ consisting in minimizing the number of ingress routers (or interfaces) to be reconfigured is expressed: [0175] FOBJ: Min ?.sub.j?J z.sub.j [0176] the 5 constraints CST1 to CST5 are expressed:

TABLE-US-00002 CST1: ?.sub.k?J x.sub.ijk = 1 ?i ? I, ?j ? J CST2: x.sub.ijk + y.sub.ik ? 1 ?i ? I, ?j ? J, ?k ? J CST3: x.sub.ijk ? y.sub.il ?i ? I, ?j ? J, ?k ? J, ?l ? L(j, k) CST4: ?.sub.i?I ?.sub.j?J p.sub.ijtx.sub.ijk ? c.sup.max b.sub.k ?k ? J, ?t ? T CST5: y.sub.ij ? z.sub.j ?i ? I, ?j ? J

[0177] In one embodiment of the disclosed technology, the optimization of the objection function FOBJ in compliance with the linearized constraints CST1 to CST5 such as above can for example be implemented by a CPLEX solver version 12.56 published by IBM (registered trademark), or by a CBC (Coin-or Branch and Cut) solver distributed at the address https://www.coin-or.org/Cbc.

[0178] The optimization method provides the prefix i and the interfaces j (or ingress routers REj) for which the path associated with this prefix i must be extended.

[0179] In the embodiment described here, and as mentioned previously, the extension of a path associated with a prefix i on an ingress router REk (step E50) includes: [0180] a reconfiguration of this router by adding at least one autonomous system to an AS-Path attribute of the BGP protocol; and [0181] a sending of said attribute to the egress routers of the upstream autonomous system.

[0182] In the embodiment described here, with reference to FIG. 1, the optimization unit OPT has the hardware architecture of a computer. It includes in particular a processor 10, a random access memory 11, a read-only memory 12 and communication means 13.

[0183] The read-only memory 12 constitutes a recording medium within the meaning of the disclosed technology. It includes a computer program PG in accordance with the disclosed technology.

[0184] This computer program PG includes instructions for executing the following steps when said program is executed by a computer. [0185] obtaining, from the collection device DC, information according to which the traffic received by an ingress router of a first autonomous system is saturated; [0186] determining a prefix of a destination subnet of an autonomous system downstream of said first autonomous system; [0187] sending an instruction to extend the path associated with said prefix on at least one target router among the ingress routers of said first autonomous system.

[0188] This instruction can for example be sent to the controller CTR so that it extends the path associated with the prefix i on an ingress router of the autonomous system.

[0189] In one particular embodiment, the computer program PG implements the integer linear program ILP described previously to determine the prefix and the routers to be reconfigured.

ANNEX

[0190]

TABLE-US-00003 TABLE T1 interface interface interface p.sub.ijt (Gbps) j = 1 j = 2 j = 3 Time prefix i = 1 p.sub.111 = 3 p.sub.121 = 10 p.sub.131 = 2 range prefix i = 2 p.sub.211 = 2 p.sub.221 = 3 p.sub.231 = 5 t = 1 DT.sub.j1 DT.sub.11 = 80 DT.sub.21 = 80 DT.sub.31 = 80 Time prefix i = 1 p.sub.112 = 6 p.sub.122 = 20 P.sub.132 = 2 range prefix i = 2 p.sub.212 = 4 p.sub.222 = 3 p.sub.232 = 5 t = 2 DT.sub.j2 DT.sub.12 = 93 DT.sub.22 = 88 DT.sub.32 = 70 Load Cj .sup.C.sub.1 = 93% .sup.C.sub.2 = 88% .sup.C.sub.3 = 80%

TABLE-US-00004 TABLE T2 interface interface interface p.sub.ijt (Gbps) j = 1 j = 2 j = 3 Time prefix i = 1 p.sub.111 = 0 p.sub.121 = 13 p.sub.131 = 2 range prefix i = 2 p.sub.211 = 2 p.sub.221 = 3 p.sub.231 = 5 t = 1 DT.sub.j1 DT.sub.11 = 77 DT.sub.21 = 83 DT.sub.31 = 80 Time prefix i = 1 p.sub.112 = 0 p.sub.122 = 26 P.sub.132 = 2 range prefix i = 2 p.sub.212 = 4 p.sub.222 = 3 p.sub.232 = 5 t = 2 DT.sub.j2 DT.sub.12 = 87 DT.sub.22 = 94 DT.sub.32 = 70 Load Cj .sup.C.sub.1 = 87% .sup.C.sub.2 = 94% .sup.C.sub.3 = 80%

TABLE-US-00005 TABLE T3 interface interface interface p.sub.ijt (Gbps) j = 1 j = 2 j = 3 Time prefix i = 1 p.sub.111 = 0 p.sub.121 = 0 p.sub.131 = 15 range prefix i = 2 p.sub.211 = 2 p.sub.221 = 3 p.sub.231 = 5 t = 1 DT.sub.j1 DT.sub.11 = 77 DT.sub.21 = 70 DT.sub.31 = 93 Time prefix i = 1 p.sub.112 = 0 p.sub.122 = 0 .sup.P.sub.132 = 28 range prefix i = 2 p.sub.212 = 4 p.sub.222 = 3 p.sub.232 = 5 t = 2 DT.sub.j2 DT.sub.12 = 87 DT.sub.22 = 68 DT.sub.32 = 96 Load Cj .sup.C.sub.1 = 87% .sup.C.sub.2 = 70% .sup.C.sub.3 = 80%

TABLE-US-00006 TABLE T4 interface interface interface p.sub.ijt (Gbps) j = 1 j = 2 j = 3 Time prefix i = 1 p.sub.111 = 3 p.sub.121 = 10 p.sub.131 = 2 range prefix i = 2 p.sub.211 = 0 p.sub.221 = 5 p.sub.231 = 5 t = 1 DT.sub.j1 DT.sub.11 = 78 DT.sub.21 = 82 DT.sub.31 = 80 Time prefix i = 1 p.sub.112 = 6 p.sub.122 = 20 P.sub.132 = 2 range prefix i = 2 p.sub.212 = 0 p.sub.222 = 7 p.sub.232 = 5 t = 2 DT.sub.j2 DT.sub.12 = 89 DT.sub.22 = 92 DT.sub.32 = 70 Load Cj .sup.C.sub.1 = 89% .sup.C.sub.2 = 92% .sup.C.sub.3 = 80%

TABLE-US-00007 TABLE T5 interface interface interface p.sub.ijt (Gbps) j = 1 j = 2 j = 3 Time prefix i = 1 p.sub.111 = 3 p.sub.121 = 10 p.sub.131 = 2 range prefix i = 2 p.sub.211 = 0 p.sub.221 = 0 p.sub.231 = 10 t = 1 DT.sub.j1 DT.sub.11 = 78 DT.sub.21 = 77 DT.sub.31 = 85 Time prefix i = 1 p.sub.112 = 6 p.sub.122 = 20 P.sub.132 = 2.sup. range prefix i = 2 p.sub.212 = 0 p.sub.222 = 0 p.sub.232 = 12 t = 2 DT.sub.j2 DT.sub.12 = 89 DT.sub.22 = 85 DT.sub.32 = 77 Load Cj .sup.C.sub.1 = 89% .sup.C.sub.2 = 85% .sup.C.sub.3 = 85%

TABLE-US-00008 TABLE TD PAR LON AMS PAR 0 345 km 357 km LON 345 km 0 355 km AMS 357 km 355 km 0