US-12627600-B2 - Method and system for configuring an autonomous system

US12627600B2US 12627600 B2US12627600 B2US 12627600B2US-12627600-B2

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.

Inventors

Yannick Carlinet
Eric Gourdin
NANCY PERROT

Assignees

ORANGE

Dates

Publication Date: 20260512
Application Date: 20240510
Priority Date: 20230512

Claims (7)

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 j , and said constraints are linearly expressed in the form: CST1: Σ kϵJ x ijk = 1 ∀i ϵ I, ∀j ϵ J CST2: x ijk + y ik ≤ 1 ∀i ϵ I, ∀j ϵ J, ∀k ϵ J CST3: x ijk ≤ y il ∀i ϵ I, ∀j ϵ J, ∀k ϵ J, ∀l ϵ L(j, k) CST4: Σ iϵI Σ jϵJ p ijt x ijk ≤ c max b k ∀k ϵ J, ∀t ϵ T CST5: y ij ≤ z j ∀i ϵ I, ∀j ϵ J wherein: c max is a saturation threshold and b j is a maximum throughput supported by the saturated router; p 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 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 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 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

TECHNICAL FIELD The disclosed technology is in the context of a transit network. It more particularly relates to a method and a system making it possible to rebalance the load in an Autonomous System (AS) when it is detected that one of its input interfaces is saturated. DISCUSSION OF RELATED TECHNOLOGY Equivalently, the expressions “input interface” or “ingress router” will be used. In certain implementations, such an ingress router receives, from one or more egress routers of an autonomous system called “upstream” autonomous system, traffic including packets, and routes each of these packets, from their destination IP address to a destination subnet of an autonomous system called “downstream” autonomous system. It is recalled that the IP addresses of the equipment in the same destination subnet belong to the same address range called “prefix”. It is also recalled that these transit networks use the BGP protocol (Border Gateway Protocol) to exchange network routing and accessibility information (called prefixes) between the autonomous systems. The BGP protocol in particular defines an eBGP (Exterior BGP) operating mode used between two autonomous systems AS. This protocol defines messages, each associated with a certain number of attributes. For example, once the eBGP connection has been established between the ingress router of a first autonomous system and an egress router of a second upstream autonomous system, the ingress router communicates to the egress router: information on the destination networks it knows and for which it proposes transit, as well asa certain number of attributes associated with these networks, which make it possible to avoid loops. It is up to the egress routers of the second upstream autonomous system to choose an ingress router of the first autonomous system which offers the best route to a destination subnet. Particularly, when several routes are possible to the same destination subnet, the BGP protocol allows a router to determine the best route to be used and to announce it to its neighboring routers. For this purpose, the protocol defines an “AS Path” attribute which includes an ordered list of the autonomous systems traversed to reach a destination subnet. Other things being equal, the BGP protocol chooses the route with the shortest “AS Path” attribute. It is common for some input interfaces to be saturated but not for others. In the current state of the art, a solution to try to get out of this saturation situation consists in reconfiguring the saturated ingress router by increasing the list of the “AS Path” attribute associated with a destination subnet, in other words with a prefix. The egress routers of the second upstream autonomous system then move the traffic destined for this prefix towards another ingress router. But the large number of prefixes as well as the combinatorics related to the nature of the problem make it very difficult to choose the prefixes whose paths must be extended. Indeed, a chosen prefix can cause saturation on an ingress router; it is then necessary to choose new prefixes on this last ingress router, which can lead to new saturations elsewhere, and so on. The disclosed technology aims a configuration method and system that does not present these drawbacks. SUMMARY Thus, and according to a first aspect, the disclosed technology relates to a method for configuring a first autonomous system in a transit network, this method including: a step of obtaining information according to which the traffic received by an ingress router of the 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;a step of 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;a step of extending the path associated with said prefix on at least one target router among the 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. Correlatively, the disclosed technology relates to a system for configuring a first autonomous system in a transit network, this system including: an optimization unit configured to obtain information according to which the 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 s