HK1075769B - Load balancing techniques for inter-domain traffic engineering - Google Patents

Claims (7)

1. Procédé pour équilibrer un trafic sur des chemins reliant un réseau à l'Internet comprenant:

   la formation d'une connexion entre un réseau local et un autre réseau qui est relié à une pluralité de réseaux, où la connexion comprend une pluralité de chemins (p) transportant du trafic sous la forme de paquets de données entre le réseau local et l'autre réseau, dans lequel chaque chemin a une charge de chemin (x_i), qui est la quantité de trafic allouée à un chemin (p), une capacité disponible (c_i), qui est la quantité de trafic que le chemin (p) peut transmettre, et une limite de capacité inférieure (l_i) et une limite de capacité supérieure (h_i) qui sont les limites de capacité supérieure et inférieure mesurées de la capacité disponible (c_i);

   la mesure de la charge de chemin (x_i) de chacun de la pluralité de chemins (p);

   la mesure de la limite de capacité supérieure (h_i(0)) de chacun de la pluralité de chemins (p);

   la comparaison de la charge de chemin (x_i) et de la limite de capacité supérieure (h_i(0)) pour chacun de la pluralité de chemins (p);

   la sélection d'un de la pluralité de chemins (p), où la pluralité de chemins (p) comprend le chemin sélectionné (p₀) et d'autres chemins (p_i), le chemin sélectionné (p₀) ayant une surcharge initiale (x₀(0)), et où la surcharge existe lorsque la charge du chemin initial sélectionné (x₀(0)) est plus grande que la limite de capacité supérieure du chemin initial sélectionné (h₀(0)); et

   le choix de la charge de chemin (x_i) pour chacun de la pluralité d'autres chemins (p_i) en utilisant une stratégie d'allocation fractionnaire, dans lequel la stratégie d'allocation fractionnaire comprend:

   (a) l'indexation des autres chemins (p_i) par i, dans laquelle i est un ensemble d'entiers de 1 à P, où P est le nombre total des autres chemins (p_i);

   (b) l'association d'une pluralité d'intervalles ping avec un compteur (t), où la valeur initiale du compteur est réglée à zéro (0) et il y a un total de N intervalles pin;

   (c) le calcul d'une partie (y(t)) de la surcharge du chemin sélectionné initial (x₀(0)) à décharger et à distribuer sur d'autres chemins (p_i) en utilisant une stratégie de recherche bissectionnelle et en sautant à l'étape (f);

   (d) le calcul de la charge du chemin sélectionné actualisé (x₀(t)), dans lequel la charge du chemin sélectionné actualisé (x₀(t)) est égale à la surcharge du chemin sélectionné initial (x₀(0)) moins la somme de la limite de capacité inférieure pour i chemin(s);

   (e) le calcul de la partie (y(t)) de la charge du chemin sélectionné actualisé (x_o(t)) à décharger et distribuer aux autres chemins (p_i) en utilisant une stratégie de recherche bissectionnelle;

   (f) la mesure de la limite de capacité inférieure (l_i) et de la limite de capacité supérieure (h_i) des autres chemins (pi) à l'intervalle ping (t);

   (g) la distribution de la partie de surcharge du chemin sélectionné ou de la charge du chemin sélectionné actualisé (x₀(t)) aux autres chemins (p_i), où la partie du trafic (y(t)) est distribuée aux autres chemins (p_i) en utilisant l'équation $x_i=l_i\left(t\right)+\frac{h_i\left(t\right)-l_i\left(t\right)}{\sum _{i=1}^P\left(h_i,\left(t\right),-,l_i,\left(t\right)\right)}\left(y,\left(t\right)\right)$ et

   (h) l'arrêt s'il n'y a plus d'intervalles ping (t = N), sinon l'augmentation de un (1) de la valeur numérique du compteur puis le passage à l'étape (d).
2. Procédé pour équilibrer un trafic sur des chemins reliant un réseau à l'Internet selon la revendication 1, dans lequel la stratégie de recherche bissectionnelle choisit la partie (y(t)) du trafic à décharger et à distribuer en utilisant l'équation: $y\left(t\right)=\min \left\{\left(0.5\right)\left[\sum _{i=1}^P\left(h_i,\left(t\right),-,l_i,\left(t\right)\right)\right],(x_0\left(t,)\right)\right\}\mathrm{.}$
3. Procédé pour équilibrer un trafic sur des chemins reliant un réseau à l'Internet selon la revendication 1 ou 2, dans lequel la quantité de trafic à partir du réseau local vers le grand réseau sur le chemin sélectionné (p₀) est mesurée en utilisant des mesures de niveau de flux ou le protocole SNMP (Simple Network Management Protocol).
4. Procédé pour équilibrer un trafic sur des chemins reliant un réseau à l'Internet selon la revendication 1, 2 ou 3, dans lequel la limite de capacité supérieure du chemin sélectionné initial (h₀(0)) est mesurée en utilisant des sondes actives, ou des mesures passives des détails de trafic.
5. Procédé pour équilibrer un trafic sur des chemins reliant un réseau à l'Internet selon l'une quelconque des revendications 1 à 4, dans lequel la limite de capacité supérieure du chemin sélectionné initial (h₀(0)) est mesurée en utilisant le temps de réponse de synchronisation/accusé de réception (SYN/ACK) de protocole TCP (Transmission Control Protocol).
6. Procédé pour équilibrer un trafic sur des chemins reliant un réseau à l'Internet selon l'une quelconque des revendications 1 à 5, dans lequel la limite de capacité supérieure du chemin sélectionné initial (h₀(0)) est mesurée en utilisant le temps d'aller et retour (RTT), et des mesures de perte.
7. Procédé pour équilibrer un trafic sur des chemins reliant un réseau à l'Internet selon l'une quelconque des revendications précédentes, dans lequel la limite inférieure de capacité du chemin sélectionné initial (l₀(0)) est égale à 0 et la limite de capacité supérieure du chemin sélectionné initial (h₀(0)) est égale à 1.