BR112015026342B1 - Sistema de balanceamento de carga distribuída e método - Google Patents

Abstract

BALANCEAMENTO DE CARGA DISTRIBUÍDA. A presente invenção se relaciona a um balanceamento de carga distribuída em que um roteador recebe pacotes a partir de pelo menos um cliente e encaminha fluxos de pacote para múltiplos nós de balanceamento de carga (LB) de acordo com uma técnica de roteamento de multicaminho verificado por hash por fluxo. Para um dado fluxo de pacote, os nós de LB aleatoriamente selecionam um nó de servidor como um alvo para o fluxo de pacote entre múltiplos nós de servidor e enviar uma solicitação de conexão para o nó de servidor. Um módulo de balanceamento de carga no nó de servidor toma a decisão sobre a possibilidade de aceitar ou rejeitar a conexão com base em uma ou mais métricas indicando a carga atual do respectivo servidor. Se o módulo aceita a solicitação de conexão, uma conexão é estabelecida entre o servidor e o cliente. Caso contrário, os nós do balanceamento de carga podem selecionar outro nó de servidor e tentar novamente. As conexões estabelecidas entre clientes e servidores passam através de nós de balanceamento de carga, mas não são terminadas nos nós de balanceamento de carga.

Description

FUNDAMENTOS DA INVENÇÃO

[001] Balanceadores de carga convencionais são tipicamente caixas individuais e com um propósito único que incluem vários controladores de interface de rede (NICs), por exemplo oito NICs, com alguns dos NICs controlando o tráfego de entrada de/tráfego de saída para os clientes e os outros NICs administrando o tráfego de saída de/tráfego de saída para os dispositivos host (por exemplo, servidores, como servidores web) que estão tendo sua carga balanceada. Largura de banda ou rendimento nestes balanceadores de carga convencionais é tipicamente na faixa de 40 Gigabits por segundo (Gbps) no lado do cliente e 40 Gbps no lado do servidor. Como o tamanho e o escopo de aplicativos baseados em rede e serviços baseados em rede como serviços de computação em nuvem têm aumentado, centros de dados podem abrigar centenas ou mesmo milhares de dispositivos host (por exemplo, ser-vidores web) que precisam ter sua carga balanceada. Balanceadores de carga convencionais podem não ter bom dimensionamento em tais ambientes.

[002] Além disso, balanceadores de carga convencionais geralmente usam técnicas como conexões max, round robin, e/ou conexões least (least connections) aplicadas aos dados coletados a partir dos dispositivos host para selecionar qual dispositivo host irá administrar uma conexão. Além disso, balanceadores de carga convencionais normalmente servem como proxies para os dispositivos host que eles FRONT e, assim, encerram conexões (por exemplo, conexões TCP - Transmission Control Protocol) dos clientes e enviam o tráfego de clientes para os dispositivos host em conexões TCP estabelecidas entre os dispositivos host e o balanceador de carga. Assim, um dispositivo host e um cliente não se comunicam através de uma conexão TCP direta ao usar esses balanceadores de carga convencionais.

BREVE DESCRIÇÃO DAS FIGURAS

[003] A Figura 1 é um diagrama de blocos de um exemplo de sistema de ba- lanceamento de carga distribuída, de acordo com pelo menos algumas modalidades.

[004] A Figura 2 é um fluxograma de alto nível de um método de balanceamento de carga, que pode ser implementado pelo sistema de balanceamento de carga distribuída da Figura 1, de acordo com pelo menos algumas modalidades.

[005] A Figura 3 mostra um exemplo de nó do balanceador de carga que inclui o ingresso, o egresso e os componentes do rastreador de fluxo, de acordo com pelo menos algumas modalidades.

[006] A Figura 4 ilustra o fluxo de roteamento e no balanceador de carga distribuída, de acordo com pelo menos algumas modalidades.

[007] A Figura 5 ilustra os nós de anúncio de entrada para o roteador de borda de acordo com pelo menos algumas modalidades.

[008] A Figura 6 é um fluxograma de um método de roteamento de caminhos múltiplos, de acordo com pelo menos algumas modalidades.

[009] A Figura 7 ilustra graficamente o fluxo de pacotes assimétrico, de acordo com pelo menos algumas modalidades.

[010] A Figura 8 ilustra o fluxo de pacotes no sistema de balanceamento de carga distribuída, de acordo com pelo menos algumas modalidades.

[011] As Figuras 9A e 9B proporcionam um fluxograma de fluxo de pacotes ao estabelecer conexões no sistema de balanceamento de carga distribuída, de acordo com pelo menos algumas modalidades.

[012] As Figuras 10A a 10G ilustram o fluxo de pacotes no sistema de balanceamento de carga distribuída de acordo com pelo menos algumas modalidades.

[013] As Figuras 11A a 11D ilustram a administração de eventos que afetuam a filiação no anel hash compatível de nó do balanceador de carga, de acordo com pelo menos algumas modalidades.

[014] A Figura 12 é um fluxograma de alto nível de um método de verificação de integridade que pode ser realizado por cada nó do balanceador de carga de acordo com um intervalo de verificação de integridade de acordo com pelo menos algumas modalidades.

[015] A Figura 13 ilustra um método para verificação de integridade de um nó do balanceador de carga de outro nó do balanceador de carga, de acordo com pelo menos algumas modalidades.

[016] A Figura 14 ilustra graficamente um nó do balanceador de carga verificando a integridade de um ou mais nós do balanceador de carga, de acordo com pelo menos algumas modalidades.

[017] A Figura 15 ilustra os nós do balanceador de carga verificando a integridade dos nós de servidor, de acordo com pelo menos algumas modalidades.

[018] A Figura 16 ilustra graficamente uma vista da manutenção de outro nó que pode ter sua manutenção feita por um nó do balanceador de carga 110, de acordo com pelo menos algumas modalidades.

[019] A Figura 17 ilustra a informação de integridade que pode ter sua manutenção feita por cada nó do balanceador de carga, de acordo com pelo menos algumas modalidades.

[020] As Figuras 18A e 18B ilustram a administração de uma falha no nó do balanceador de carga, de acordo com pelo menos algumas modalidades.

[021] As Figuras 19A e 19B ilustram graficamente uma técnica de disponibili- zação de conexão, de acordo com pelo menos algumas modalidades.

[022] A Figura 20 é um fluxograma de alto nível de um método de disponibili- zação de conexão que pode ser realizado por cada módulo do balanceador de carga, de acordo com pelo menos algumas modalidades.

[023] A Figura 21 é um fluxograma de um método para distribuição da informação de conexão ativa recebida em um pacote de disponibilização de conexão que tem como alvo os nós do balanceador de carga, de acordo com algumas modalidades.

[024] A Figura 22 ilustra um método alternativo para distribuição da informação de conexão ativa recebida em um pacote de disponibilização de conexão que tem como alvo os nós do balanceador de carga, de acordo com pelo menos algumas modalidades.

[025] A Figura 23 ilustra um exemplo de arquitetura de pilha de software para um nó do balanceador de carga de acordo com pelo menos algumas modalidades.

[026] A Figura 24 ilustra os aspectos da tecnologia de processamento de pacote de núcleo que podem ser utilizados em modalidades.

[027] A Figura 25 ilustra um exemplo de processador de pacote de multicore para processamento de fluxos de dados nos nós do balanceador de carga, de acordo com pelo menos algumas modalidades.

[028] A Figura 26 ilustra outro exemplo de processador de pacote de multicore para processamento de fluxos de dados nos nós do balanceador de carga, de acordo com pelo menos algumas modalidades.

[029] A Figura 27 ilustra o processamento de pacotes que chegam por um processo de nó do balanceador de carga, de acordo com pelo menos algumas modalidades.

[030] A Figura 28 ilustra o processamento de pacotes que saem por um processo de nó do balanceador de carga, de acordo com pelo menos algumas modalidades.

[031] A Figura 29 ilustra um sistema de balanceamento de carga que inclui um balanceador de carga distribuída em um ambiente de produção, de acordo com pelo menos algumas modalidades.

[032] A Figura 30 ilustra um sistema de teste de balanceador de carga distribuída que incorpora um mecanismo de barramento de mensagens que permite que vários componentes do sistema de balanceamento de carga distribuída sejam configurados e executados em ou como um processo único, de acordo com pelo meno algumas modalidades.

[033] As Figuras 31 e 32 ilustram adaptadores de pacotes de barramento de mensagens e pipelines de pacote, de acordo com pelo menos algumas modalidades.

[034] A Figura 33A ilustra um exemplo de ambiente de rede do provedor, de acordo com pelo menos algumas modalidades.

[035] A Figura 33B ilustra uma implementação do balanceador de carga distribuída em um exemplo de ambiente de rede do provedor, como mostrado na Figura 33A, de acordo com pelo menos algumas modalidades.

[036] A Figura 34A ilustra um exemplo de implementação de rack físico do ba- lanceador de carga distribuída e nós do servidor de acordo com pelo menos algumas modalidades.

[037] A Figura 34B ilustra um outro exemplo de implementação do rack físico do balanceador de carga distribuída e nós do servidor de acordo com pelo menos algumas modalidades.

[038] A Figura 35 ilustra um exemplo ambiente de rede no qual um, dois ou mais balanceadores de carga distribuída são implementados em uma rede, de acordo com pelo menos algumas modalidades.

[039] A Figura 36 é um diagrama de bloco ilustrando um exemplo de sistema computacional que pode ser usado em algumas modalidades.

[040] Embora as modalidades sejam descritas neste documento à título de exemplo, para várias modalidades e figuras ilustrativas, aqueles versados na técnica reconhecerão que as modalidades não estão limitadas às modalidades ou figuras descritas. Deve ser compreendido que as figuras e a descrição detalhada nele não se destinam a limitar as modalidades ao modo específico divulgado, mas pelo contrário, a intenção é cobrir todas as modificações, equivalentes e alternativas que estejam dentro do espírito e do escopo, conforme definido pelas reivindicações ane- xas. Os títulos usados neste documento são apenas para fins organizacionais e não se destinam a serem usados para limitar o escopo da descrição ou das reivindicações. Conforme usado em toda esta aplicação, a palavra "pode" é usada em um sentido permissivo (isto é, significando ter o potencial para), ao invés do sentido obrigatório (isto é, significando deve). De forma semelhante, as palavras "incluir", "incluindo" e "inclui" significam incluindo, mas não limitado a.

DESCRIÇÃO DETALHADA

[041] Várias modalidades de métodos e sistemas para balanceamento de carga distribuída em ambientes de rede são descritas. As modalidades de um método e o sistema de balanceamento de carga distribuída são descritos de modo tal que possam ser implementados de acordo com modalidades de um balanceador de carga distribuída em vários ambientes de rede. As modalidades de balanceador de carga distribuída podem, por exemplo, ser utilizadas para facilitar e manter fluxos de pacotes, por exemplo, fluxos de pacote de tecnologia do Protocolo de Controle de Transmissão (Transmission Control Protocol, TCP na sigla em inglês), entre clientes em uma rede externa como a Internet e destinos, tipicamente servidores (por exemplo, servidores web, servidores de aplicações, servidores de dados, etc.) em uma rede local, como uma rede de provedor 1900, como ilustrado nas Figuras 33A e 33B. Enquanto modalidades são primariamente descritas neste documento em relação ao processamento de fluxos de pacotes TCP, é importante notar que modalidades podem ser aplicadas a outros protocolos de comunicações de dados além do TCP, e para outras aplicações que não sejam processamento de fluxos de pacotes.

[042] O balanceador de carga distribuída pode atuar para facilitar e manter os fluxos de pacotes TCP entre clientes particulares e servidores selecionados (por exemplo, servidores web). No entanto, o balanceador de carga distribuída não encerra os fluxos TCP dos clientes e não age como um proxy para os servidores como é feito em balanceadores de carga convencionais. Em vez disso, os nós do balance- ador de carga dos pacotes TCP do roteador de balanceador de carga distribuída recebidos dos clientes miram nos servidores, e os servidores usam suas pilhas de TCP para gerenciar as conexões TCP para os clientes. Em outras palavras, os servidores encerram o fluxo de pacote TCP dos clientes.

[043] Além disso, ao invés de nó(s) de balanceador de carga tomando decisões a respeito de qual servidor irá atender a uma solicitação de conexão baseada em uma técnica ou algoritmo de balanceamento de carga aplicado à informação coletada a partir dos servidores como é feito em tecnologia balanceadora de carga convencional, os nós de balanceador de carga podem selecionar aleatoriamente um servidor para receber um novo pedido de conexão, e um componente do balancea- dor de carga distribuída que reside no nó do servidor toma a decisão localmente quanto ao fato de se o servidor selecionado irá aceitar ou rejeitar a nova solicitação de conexão com base em uma ou mais métricas do status atual do respectivo servidor. Assim, as decisões as quais os servidores aceitam solicitações de conexão são movidas a partir dos nós do balanceador de carga aos nós de servidores que irão administrar as conexões. Em outras palavras, a decisão é movida para mais perto de onde e quando a solicitação de conexão será atendida.

[044] Para facilitar e manter os fluxos de pacotes entre os clientes e os servidores, as modalidades do balanceador de carga distribuída podem empregar várias técnicas ou tecnologias, incluindo, mas não limitadas a tecnologia de roteamento de múltiplos caminhos (multipath), tecnologia hashing consistente, tecnologia de tabela hash distribuída (distributed hash table, DHT), tecnologia BGP (Border Gateway Protocol), rastreamento de associação, verificação de integridade, publicação de conexão e encapsulamento e desencapsulamento de pacotes. Estes, bem como outros aspectos do sistema de balanceamento de carga distribuída são descritos a seguir em relação às Figuras.

Sistema de balanceamento de carga distribuída

[045] A Figura 1 é um diagrama de blocos de um exemplo de sistema de ba-lanceamento de carga distribuída, de acordo com pelo menos algumas modalidades. As modalidades do balanceador de carga distribuída podem ser implementadas em uma rede 100, por exemplo uma rede de provedor 1900 de um provedor de serviços, como ilustrado nas Figuras 33A e 33B. Como uma visão geral de alto nível da administração do pacote de cliente no sistema de balanceador de carga distribuída, um ou mais clientes 160 da rede 100 podem se conectar a um roteador de borda 102 da rede 100, por exemplo por meio de uma rede externa 150 como a Internet. O roteador de borda 102 pode roteiar os pacotes que entram (por exemplo, os pacotes TCP) dos clientes 160 para um componente do roteador de borda 104 do balanceador de carga distribuída que roteia os pacotes que entram para os nós do balanceador de carga (BC) 110 em uma camada de nó do balanceador de carga do sistema de ba- lanceador de carga distribuída. Em pelo menos algumas modalidades, o roteador de borda 104 pode tomar as decisões de roteamento de acordo com uma técnica de roteamento de caminhos múltiplos hash por fluxo, por exemplo, uma técnica de hashing de caminho múltiplo de custo igual (equal-cost multipath, ECMP na sigla em inglês). Os nós do balanceador de carga 110 por sua vez encapsulam os pacotes (por exemplo, de acordo com Protocolo de Datagramas do Usuário, User Datagram Protocol UDP na sigla em inglês) e roteia e os pacotes encapsulados para os módulos de balanceamento de carga locais 132 nos nós de servidor 130 por meio de uma malha de rede 120 (por exemplo, uma rede L3) na rede 100. A malha 120 pode incluir um ou mais dispositivos ou componentes de rede incluindo, mas não limitado a comutadores, roteadores e cabos. Nos nós de servidor 130, os módulos de balance- ador de carga locais 132 desencapsulam os pacotes e enviam os pacotes TCP do cliente para as pilhas TCP dos servidores 134. Os servidores 134 nos nós de servidor 130 então usam suas pilhas TCP para gerenciar as conexões para os clientes 160.

[046] A Figura 2 é um fluxograma de alto nível de um método de balanceamento de carga, que pode ser implementado pelo sistema de balanceamento de carga distribuída da Figura 1, de acordo com pelo menos algumas modalidades. Modalidades do sistema de balanceador de carga distribuída podem não resolver o difícil problema de atribuir carga entre vários destinos (por exemplo, servidores web), como é feito em balanceadores de carga convencionais. Por exemplo, balanceado- res de carga convencionais geralmente usam técnicas ou algoritmos, como conexões max, round robin, e/ou técnicas de conexões least para selecionar qual servidor deve administrar uma conexão. No entanto, estas técnicas têm desvantagens, e em particular, são difíceis de serem realizadas com sucesso em um sistema distribuído onde os dados utilizados para tomar decisões de balanceamento de carga é muitas vezes quase imediatamente obsoleto. Em pelo menos algumas modalidades do sistema de balanceador de carga distribuída, em vez de tentar selecionar um nó de servidor 130 para satisfazer uma solicitação de conexão utilizando uma ou mais das técnicas de balanceamento de carga como é feito nos balanceadores de carga convencionais, um nó do balanceador de carga 110 na camada de nó do balanceador de carga pode determinar aleatoriamente um nó do servidor 130 para receber uma solicitação para uma conexão de cliente. Se esse nó do servidor 130 considera-se sobrecarregado, o nó do servidor 130 pode enviar a solicitação de conexão de volta para o nó do balanceador de carga 110 informando assim ao nó do balanceador de carga 110 que o nó do servidor 130 não pode administrar a conexão no momento. A camada de nó do balanceador de carga pode então determinar aleatoriamente outro nó do servidor 130 para receber a solicitação de conexão, ou, alternativamente, pode retornar uma mensagem de erro para o cliente solicitante 160 para informar ao cliente 160 que a conexão não pode ser estabelecida no momento.

[047] Como indicado no 10 da Figura 2, a camada de nó do balanceador de carga do sistema de balanceador de carga distribuída recebe uma solicitação para uma sessão de comunicação (por exemplo, uma conexão TCP) de uma fonte. A fonte pode ser, por exemplo, ser um cliente 160 em uma rede externa 150 para a rede 100 que implementa o sistema de balanceador de carga distribuída. Em pelo menos algumas modalidades, a solicitação pode ser recebida do cliente 160 em um roteador de borda 102 da rede 100, e roteiado para um roteador de borda 104 que roteia os pacotes que entram para os nós de balanceador de carga (BC) 110 em uma camada de nó do balanceador de carga, por exemplo, utilizando uma técnica de hashing de roteamento de caminhos múltiplos (ECMP) por fluxo para selecionar de modo pseudo-aleatório um nó do balanceador de carga 110 ao qual uma determinada solicitação de conexão de um cliente 160 deve ser roteiada.

[048] Como indicado em 20, a camada de nó do balanceador de carga seleciona aleatoriamente um nó de destino e roteia a solicitação de conexão para o nó de destino selecionado. O nó de destino pode, por exemplo, ser um de uma pluralidade de nós do servidor 130 FRONTED pelo balanceador de carga. Em pelo menos algumas modalidades, um nó do balanceador de carga 110 na camada de balancea- dor de carga pode selecionar aleatoriamente um nó de servidor 130 para receber uma solicitação de conexão de todos os nós de servidor 130 conhecidos. No entanto, outros métodos que não sejam puramente seleção aleatória de entre todos os nós do servidor 130 conhecidos podem ser usados em algumas modalidades para selecionar os nós do servidor 130 para receber as solicitações de conexão. Por exemplo, em algumas modalidades, as informações sobre os nós do servidor 130 podem ser usadas pelos nós de balanceador de carga 110 para pesar a seleção aleatória dos nós de servidor 130. Como um exemplo, se os nós de balanceador de carga 110 sabem que diferentes nós de servidor 130 são tipos diferentes de dispositivos ou são configurados com CPUs diferentes e, portanto, têm diferentes capacidades, as informações podem ser usadas para influenciar a seleção aleatória no sentido (ou longe de) de determinados tipos ou configurações de nó do servidor 130.

[049] Como indicado em 30, o nó de destino determina se pode aceitar a sessão de comunicações. Em pelo menos algumas modalidades, um módulo de balan- ceador de carga local (BC) 132 no nó do servidor 130 determina se o respectivo servidor 134 no nó do servidor 130 pode aceitar a nova conexão com base em uma ou mais métricas do estado atual do respectivo servidor 134.

[050] Em 40, se a solicitação de conexão é aceita, então, conforme indicado em 50 o nó de destino informa a camada de nó do balanceador de carga que o nó de destino pode administrar a conexão. Como indicado em 60, uma sessão de comunicação é então estabelecida entre a fonte (por exemplo, um cliente 160) e o nó de destino (por exemplo, um servidor 134 de um nó de servidor 130) por meio da camada de nó do balanceador de carga. Em pelo menos algumas modalidades, o servidor 134 no nó do servidor 130 utiliza uma pilha TCP para gerenciar a conexão ao cliente 160.

[051] Em 40, se a solicitação de conexão não for aceita, então, conforme indicado em 70, o nó de destino notifica a camada de nó do balanceador de carga e o método pode retornar ao elemento 20. A camada de nó do balanceador de carga pode então selecionar aleatoriamente outro nó de destino em 20, ou, alternativamente, pode informar ao cliente solicitante 160 que a conexão não pode ser estabelecida no momento. Note que o cliente 160 pode, mas não necessariamente, reenvie a solicitação de conexão para iniciar o método novamente no elemento 10.

[052] Referindo-se novamente a Figura 1, pelo menos algumas modalidades do sistema de balanceamento de carga distribuída podem utilizar hardware comum para rotear o tráfego do cliente recebido em um roteador de borda 104 na rede 100 para os nós de servidor 130 na rede 100. Pelo menos algumas modalidades do ba- lanceador de carga distribuída podem incluir uma camada de nó do balanceador de carga que inclui vários nós do balanceador de carga 110. Em pelo menos algumas modalidades, cada nó do balanceador de carga 110 podem atender em uma ou mais das várias funções na camada de nó do balanceador de carga. Essas funções dos nós de balanceador de carga 110 podem incluir as funções de um nó de ingresso, um nó de egresso e um nó de rastreador de fluxo (como um rastreador de fluxo primário ou um rastreador de fluxo secundário para um determinado fluxo de pacotes). Em pelo menos algumas modalidades, cada nó do balanceador de carga 110 pode ser implementado na camada de nó do balanceador de carga ou como em um dispositivo de computação separado, como um dispositivo de computação montado em rack. Em pelo menos algumas modalidades, cada nó do balanceador de carga 110 pode servir em cada uma das três funções de nó de ingresso, nó de egresso e nó de rastreador de fluxo (como um rastreador de fluxo primário ou secundário para um fluxo de pacotes), com o nó do balanceador de carga 110 geralmente servindo em apenas uma (mas possivelmente em duas ou três) das funções para determinados fluxos de pacotes. É notado, no entanto, que em pelo menos algumas modalidades, não é permitido a um um nó do balanceador de carga 110 atender ambos o rastrea- dor de fluxo primário e o rastreador de fluxo secundário para um determinado fluxo de pacotes. Alternativamente, em algumas modalidades, cada nó do balanceador de carga 110 pode servir em apenas uma das três funções. Nesta modalidade, conjuntos separados de dispositivos de computação podem ser implementados na camada de nó do balanceador de carga especificamente como nós de ingresso, os nós de egresso e nós de rastreador de fluxo.

[053] Em pelo menos algumas modalidades, hashing consistente e tecnologia de anel hash consistente pode ser aplicado para determinar os rastreadores de fluxo primário e secundário para os fluxos de pacote. Cada fluxo de pacote de um cliente pode ser identificado exclusivamente, por exemplo, de quatro elementos que consistem em: o endereço IP do cliente, porta de cliente, endereço de IP do servidor (público) e porta do servidor. Este identificador pode ser abreviado como CP ou CcPp indicando o par de ponto de extremidade público e do cliente. Os pacotes associa- dos a qualquer fluxo TCP determinado (ou par CP) podem aparecer em qualquer nó do balanceador de carga 110 operando como um servidor de ingresso 112 devido a distribuição de fluxo do ECMP proveniente do roteador de borda 104. Hashing consistente é utilizado de modo que quando um pacote chega a um nó do balanceador de carga 110 que serve como um nó de ingresso, o nó de ingresso pode determinar qual nó do balanceador de carga 110 é responsável por manter o estado do fluxo de pacotes (ou seja, o nó rastreador de fluxo primário). O par CP pode ser hash pelo nó de ingresso para dentro de um anel hash consistente para determinar qual nó do balanceador de carga 110 é responsável por manter informações de estado para o fluxo de pacotes. O nó 110 determinado de acordo com o hash consistente do par CP para o fluxo de pacotes no anel hash consistente é o nó 110 que serve como o rastreador de fluxo primário para o fluxo de pacotes. Em pelo menos algumas moda-lidades, o nó sucessor no anel hash consistente serve como o rastreador de fluxo secundário para o fluxo de pacotes.

[054] A Figura 3 mostra um exemplo de um nó do balanceador de carga (BC) 110 que inclui componentes que implementam os todas as três funções (ingresso, egresso e rastreador de fluxo), de acordo com pelo menos algumas modalidades. Neste exemplo, um componente de servidor de ingresso 112 executa a função de entrada de receber pacotes TCP inbound de cliente(s) e de enviar os pacotes TCP como pacotes encapsulados para o(s) servidor (es). Um componente de servidor de egresso 114 executa a função de saída de receber pacotes de saída encapsulados do(s) servidor(es) e de enviar os pacotes TCP desencapsulados para o(s) cliente(s). Um componente de rastreador de fluxo 116 funciona como um rastreador de fluxo primário ou secundário para um ou mais fluxos de pacotes que são estabelecidos entre o(s) cliente(s) 160 e o(s) servidor(es) 134. O servidor de ingresso 112 também pode se comunicar com o rastreador de fluxo 116 no nó do balanceador de carga 110, ou com o rastreador de fluxo 116 em outro nó do balanceador de carga 110 para iniciar uma conexão TCP entre um cliente e um dos servidores 134 em resposta a uma solicitação de conexão recebida do respectivo cliente 160, ou para se obter informação de mapeamento para o fluxo de pacotes. Se o servidor de ingresso

Nós do balanceador de carga

[055] Referindo-se novamente à Figura 1, em pelo menos algumas modalidades, os nós de balanceador de carga 110 na camada de nó do balanceador de carga recebem o tráfego do cliente (pacotes, por exemplo, os pacotes TCP) a partir de um ou mais roteadores 104 na rede e encapsulam os pacotes de acordo com um protocolo (por exemplo, o Datagram Protocol (UDP)) utilizado pelo sistema balanceador de carga distribuída sobre a malha 120. A camada de nó do balanceador de carga em seguida encaminha os pacotes encapsulados para os nós do servidor de destino 130 sobre a malha 120. Cada nó do servidor 130 inclui um módulo local 132 que é um componente do sistema de balanceador de carga. O módulo 132 pode ser referido neste documento como um módulo de balanceador de carga ou simplesmente módulo de BC, e pode ser implementado em software, hardware ou uma combinação dos mesmos no nó do servidor 130. Em cada nó do servidor 130, o módulo de balanceador de carga respectivo 132 desencapsula os pacotes e envia os pacotes TCP a uma pilha TCP local para o processamento TCP normal. Em pelo menos algumas modalidades, a camada de nó do balanceador de carga pode manter informações de estado para cada fluxo TCP cliente-servidor; no entanto, os nós de ba- lanceador de carga 110 na camada de nó do balanceador de carga pode não interpretar nada sobre o fluxo TCP. Cada fluxo é gerenciado entre o servidor 134 no respectivo nó do servidor 130 e o cliente 160. O sistema de balanceador de carga distribuída assegura que os pacotes TCP cheguem ao servidor de destino correto 134. O módulo de balanceador de carga 132 em cada nó do servidor 130 toma a decisão sobre se o respectivo servidor 134 irá aceitar ou rejeitar uma nova conexão em res-posta a uma solicitação de conexão do cliente recebida de um nó do balanceador de carga 110.

[056] Em pelo menos algumas modalidades, o sistema de balanceamento de carga distribuída pode utilizar tecnologia de hashing consistente para, por exemplo, determinar quais nós de balanceador de carga 110 devem lembrar qual nó de servidor 130 é responsável por um determinado fluxo de pacotes TCP. Usando a tecnologia de hashing consistente, os nós de balanceador de carga 110 na camada de nó do balanceador de carga podem ser vistos como um anel hash consistente, e os nós de balanceador de carga 110 podem manter o controle de associação no anel e determinar membros particulares no anel que sejam responsáveis por determinados fluxos de pacotes de acordo com uma função de hashing consistente. Em pelo menos algumas modalidades, existem dois nós do balanceador de carga 110 que são responsáveis pelo rastreamento de cada fluxo de pacotes entre os clientes 160 e os servidores 134; estes nós 110 podem ser referidos como o nó de rastreador fluxo primário (RFP) e o nó de rastreador de fluxo secundário (RFS). Em pelo menos algumas modalidades, o rastreador de fluxo primário é o primeiro nó do balanceador de carga 110 no anel hash consistente para o fluxo, e o rastreador de fluxo secundário é o nó do balanceador de carga 110 seguinte ou subsequente no anel hash consistente distinto do nó de rastreador de fluxo primário. Neste arranjo, se o nó rastre- ador de fluxo primário falhar, então o nó rastreador de fluxo secundário pode se tornar o novo rastreador de fluxo primário, e outro nó do balanceador de carga 110 (por exemplo, o próximo nó 110 no anel hash consistente) pode assumir a função do ras- treador de fluxo secundário. É notado que em pelo menos algumas modalidades, não é permitido a um nó do balanceador de carga 110 atender ambos o rastreador de fluxo primário e o rastreador de fluxo secundário para um determinado fluxo de pacotes. Estas e outras mudanças de associação no anel hash consistente são discutidas mais adiante neste documento. Em pelo menos algumas modalidades, as informações de configuração para a implementação do balanceador de carga (por exemplo, lista(s) autorizada(s) dos nós de balanceador de carga 110 e nós de servidor 130 que estão atualmente em execução) podem ser mantidas por um componente de serviço de configuração 122 do sistema de balanceamento de carga distribuída, que pode por exemplo ser implementado em um ou mais dispositivos de servidores acoplados aos nós do balanceador de carga 110 por meio da malha 120.

[057] Em pelo menos algumas modalidades, para além de servir como nós de rastreador de fluxo primário e secundário, os nós de balanceador de carga 110 podem também executar uma ou duas funções para um determinado fluxo: a função de um nó de ingresso e a função de um nó de egresso. Um nó de ingresso de um fluxo de pacotes é o nó do balanceador de carga 110 que recebe o respectivo fluxo de pacotes a partir do roteador de borda 104 e encaminha o fluxo de pacotes (como pacotes encapsulados) para um servidor selecionado 134 em um nó de servidor 130 por meio da malha 120. Um nó de ingresso é o único nó do balanceador de carga 110 que move dados de clientes reais (pacotes de dados TCP) para o respectivo nó do servidor de destino 130. O nó de ingresso mantém um mapeamento do fluxo TCP para um respectivo módulo de balanceador de carga 132 no nó do servidor de destino 130 de modo que o nó de ingresso sabe a qual módulo do balanceador de carga 132 deve encaminhar o tráfego do cliente. Um nó de egresso é um nó do balancea- dor de carga 110 que é responsável pela transmissão do tráfego de resposta para um fluxo de pacotes recebido do nó do servidor 130 por meio da malha 120 para o respectivo cliente 160 por meio da rede de borda. O módulo de balanceador de carga 132 encapsula pacotes de resposta obtidos a partir do servidor 134 de acordo com um protocolo de balanceador de carga (por exemplo, UDP) e envia os pacotes de resposta encapsulados para o respectivo nó de egresso para o fluxo por meio da malha 120. Os nós de egresso são sem monitoração de estado e simplesmente de- sencapsulam os pacotes e enviam os pacotes de resposta (por exemplo, pacotes TCP) para a rede de borda a um roteador de borda 102 para entrega ao respectivo cliente 160 por meio da rede externa 150.

[058] Como mencionado anteriormente, em pelo menos algumas modalidades, cada nó do balanceador de carga 110 pode executar as funções de um nó de ingresso, um nó de egresso e/ou um nó de rastreador de fluxo (tanto como um ras- treador de fluxo primário ou secundário) para diferentes fluxos de pacote. Um único nó do balanceador de carga 110 na camada de nó do balanceador de carga pode realizar qualquer uma das funções, dependendo de qual fluxo de pacotes o nó está processando. Por exemplo, em pelo menos algumas modalidades, um nó do balan- ceador de carga 110 pode performar como um nó de ingresso para um fluxo de pacotes, como um rastreador de fluxo primário ou secundário para outro fluxo de pacotes e como um nó de egresso para outro fluxo de pacotes. Além disso, em pelo menos algumas modalidades um nó do balanceador de carga 110 pode executar várias funções para o mesmo fluxo de pacotes, como por exemplo como nó de ingresso e como rastreador de fluxo primário (ou secundário) para um determinado fluxo de pacotes. No entanto, em pelo menos algumas modalidades, para fins de redundância e recuperação, um nó do balanceador de carga 110 não é permitido a servir como o nó de rastreador de fluxo primário e secundário para o mesmo fluxo de pacotes.

[059] Acima estão descritas modalidades onde cada nó do balanceador de carga 110 pode servir em qualquer uma das três funções de servidor de ingresso, servidor de egresso e rastreador de fluxo. No entanto, em algumas modalidades, diferentes grupos de dispositivos de computação podem ser atribuídos às diferentes funções do sistema de balanceamento de carga. Por exemplo, em algumas modalidades, podem existir diferentes conjuntos de nós de ingresso, nós de egresso e nós de rastreador de fluxo, cada um implementado em um dispositivo de computação separado. Como outro exemplo, em algumas modalidades, um conjunto de dispositivos de computação pode servir como nós de ingresso e nós de rastreador de fluxo, enquanto um outro conjunto de dispositivos de computação podem servir apenas como nós de ingresso.

Módulos de balanceador de carga

[060] Como mencionado anteriormente, cada nó do servidor 130 inclui um módulo de balanceador de carga local 132 que é um componente do sistema de ba- lanceador de carga. O módulo 132 pode ser implementado em software, hardware ou uma sua combinação destes no nó do servidor 130. Em pelo menos algumas modalidades, o balanceador de carga do módulo 132 em um nó de servidor 130 pode executar três funções principais: encapsular pacotes que saem e desencapsular pacotes que chegam, tomando decisões de balanceamento de carga local para o servidor 134 no nó 130, e disponibilização de conexão. Estas três funções são brevemente descritas abaixo e descritas em maior detalhe mais adiante neste documento.

[061] Pelo menos algumas modalidades do sistema de balanceamento de carga distribuída não encerram as conexões TCP e não falsificam pacotes; os endereços IP de origem e destino de todos os pacotes enviados através da camada de nó do balanceador de carga são os endereços IP reais dos pontos de extremidade (ou seja, os clientes 160 e os servidores 134) envolvidos nos fluxos de pacote. Em vez de falsificação, estas modalidades encapsulam todos os pacotes enviados entre os nós de balanceador de carga 110 e os nós do servidor 130 na malha 120, por exemplo como pacotes UDP. Uma vez que os pacotes de entrada em um fluxo de pacotes que chegam a um nó do servidor 130 a partir de um nó do balanceador de carga 110 atuando como o nó de ingresso para o fluxo são encapsulados pelo nó do balanceador de carga 110, os pacotes precisam ser desencapsulados e redirecionados para um fluxo TCP localhost para o servidor 134 no nó 130. O módulo de balan- ceador de carga 132 no nó 130 realiza este desencapsulamento. Da mesma forma, os pacotes de saída para um fluxo de pacotes do servidor 134 são encapsulados pelo módulo de balanceador de carga 132 e enviadas por meio da malha 120 a um nó do balanceador de carga 110 atuando como o nó de egresso para o fluxo de pacotes.

[062] Em pelo menos algumas modalidades, os módulos de balanceador de carga 132 nos nós de servidor 130 também tomam decisões locais relacionadas ao balanceamento de carga para os servidores 134 nos respectivos nós de servidor 130. Especificamente, o módulo de balanceador de carga 132 em um nó 130 decide se o respectivo servidor 134 aceitará outro fluxo TCP em resposta ao receber um pedido para uma nova conexão TCP. Como observado anteriormente, os nós de balanceador de carga 110 encapsulam todos os pacotes enviados para o módulo de balanceador de carga 132, de modo que o módulo de balanceador de carga 132 na verdade não recebe um pacote de sincronização (SYN, do inglês synchronize) TCP do cliente 160; em vez disso, o módulo de balanceador de carga 132 recebe uma mensagem de solicitação de conexão de acordo com o protocolo de encapsulamento (por exemplo, UDP) de um rastreador de fluxo 116 o qual o módulo de balancea- dor de carga 132 pode aceitar ou rejeitar. Se o módulo de balanceador de carga 132 aceita a mensagem de solicitação de conexão, o módulo de balanceador de carga 132 cria um pacote SYN destinado para o localhost. Quando o localhost aceita a conexão, isto é a própria pilha TCP administrando a respectiva conexão do cliente.

[063] Em pelo menos algumas modalidades, para tomar a decisão sobre se uma mensagem de solicitação de conexão deve ser aceita, o módulo de balancea- dor de carga 132 olha para uma ou mais métricas em relação ao consumo de recursos atual no nó do servidor 130, e se há recursos suficientes para administrar a nova conexão, o módulo de balanceador de carga 132 aceita a conexão. Em pelo menos algumas modalidades, as métricas de recursos que podem ser consideradas pelo módulo de balanceador de carga 132 podem incluir um ou mais de, mas não estão limitadas a, utilização da CPU, consumo de banda recente e o número de conexões estabelecidas. Outros métricas podem ser consideradas em vez de ou em adição a estas métricas em algumas modalidades. Por exemplo, em algumas modalidades, o módulo de balanceador de carga pode considerar a latência do servidor (ou seja, a quantidade de tempo que as solicitações gastam no backlog de conexão do servidor) como uma métrica, e pode rejeitar a solicitação de conexão se a latência do servidor estiver acima de um limite. Usando estas e/ou outras métricas, o módulo de balanceador de carga 132 pode decidir para o respectivo servidor 134 se o servidor 134 deve aceitar ou rejeitar novos fluxos de pacote. Em pelo menos algumas modalidades, uma taxa de utilização de recursos (por exemplo, N% de utilização) pode ser determinada a partir da(s) métrica(s) individualmente ou em combinação e em comparação com um limiar (por exemplo, utilização de 90%). Se a taxa de utilização de recursos determinada for igual ou superior ao limiar, ou se adicionar a ligação poderia mover para a taxa acima do limiar, então a solicitação de conexão pode ser rejeitada.

[064] Em pelo menos algumas modalidades, os módulos de balanceamento de carga 132 podem implementar um método probabilístico para determinar se as mensagens de solicitação de conexão devem ser rejeitadas. Em vez de rejeitar todas as solicitações de conexão, se a utilização dos recursos for igual ou superior a um limiar como descrito acima, este método pode rejeitar solicitações de conexão em diferentes probabilidades em dois ou mais diferentes níveis de utilização. Por exemplo, se a utilização dos recursos é de 80%, um módulo de balanceador de carga 132 pode rejeitar as solicitações de conexão a uma probabilidade de 20% ; se a utilização de recursos é de 90%, o módulo de balanceador de carga 132 módulo pode rejeitar as solicitações de conexão a uma probabilidade de 25%; se a utilização de recursos é de 95%, o módulo de balanceador de carga 132 pode rejeitar solicita-ções de conexão a uma probabilidade de 50% ; e em 98% ou acima, o módulo de balanceador de carga 132 pode rejeitar todas as solicitações de conexão.

[065] Em pelo menos algumas modalidades, cada mensagem de solicitação de conexão pode incluir uma indicação de quantas vezes a mensagem de solicitação de conexão foi rejeitada pelos módulos de balanceador de carga 132. Se uma mensagem de solicitação de conexão recebida por um módulo de balanceador de carga 130 indica que ela foi rejeitada por um número limite de vezes, o módulo de balanceador de carga 130 pode aceitar a conexão mesmo que as métricas de de-sempenho do nó do servidor 130 indiquem que a solicitação de conexão deve ser rejeitada.

[066] Em alguns casos, é possível que todos os módulos do balanceador de carga 132 aos quais uma mensagem de solicitação de conexão é enviada rejeitem a solicitação de conexão. Em pelo menos algumas modalidades, para evitar que uma mensagem de solicitação de conexão seja devolvida de um módulo de balanceador de carga 132 para outro módulo de balanceador de carga 132 por um período indeterminado, pode ser dado um tempo de permanência para cada mensagem de solicitação de conexão. Se este tempo de permanência expira, o nó de rastreador fluxo pode encerrar a solicitação e notificar o respectivo cliente 160 de que o pedido não pode ser atendido no momento.

[067] Em pelo menos algumas modalidades, os módulos de balanceamento de carga 132 nos nós de servidor 130 também realizam disponibilização de conexão com os nós do balanceador de carga 110. Em pelo menos algumas modalidades, para executar a divulgação de conexão, periodicamente ou não (por exemplo, uma vez por segundo) cada módulo de balanceador de carga 132 analisa a tabela de ro- teamento (por exemplo, uma tabela de roteamento netstat) no nó do servidor 130 e publica uma lista de conexões ativas (fluxos TCP) de volta para os nós de balancea- dor de carga 110. Os nós de balanceador de carga 110 que precisam ser informados sobre a existência de um determinado fluxo de pacote são os nós de balanceador de carga 110 que estão servindo como o nó de ingresso e como os rastreadores de fluxo primário e secundário para o respectivo fluxo de pacote. Em algumas modalida- des, o módulo de balanceador de carga 132 pode usar uma técnica de hashing consistente para filtrar a lista de nós de balanceador de carga 110 que precisam ser informados sobre os fluxos TCP ativos no nó do servidor 130. Por exemplo, o módulo de balanceador de carga 132 pode determinar quais nós de balanceador de carga 110 estão servindo como os rastreadores de fluxo primário e secundário para um determinado fluxo de pacote de acordo com o anel hash consistente. Em algumas modalidades, o módulo de balanceador de carga 132 rastreia qual nó do balancea- dor de carga 110 enviou o último pacote de dados ao módulo de balanceador de carga 132 para cada fluxo de pacote, e usa essa informação para determinar quais nós de balanceador de carga 110 estão servindo como nós de ingresso para os fluxos de pacote, já que apenas os nós de ingresso encaminham dados de clientes para o módulo de balanceador de carga 132. Em algumas modalidades, o módulo de balanceador de carga 132, em seguida formula mensagens para cada um dos nós de balanceador de carga 110 que foi determinada a necessidade de ser informado sobre os fluxos de pacote e envia as mensagens para os nós de balanceador de carga 110 para informar aos nós 110 que o nó de servidor 130 respectivo ainda está mantendo as conexões com os clientes 160. Esta disponibilização de conexão com os nós de balanceador de carga 110 pelos módulos de balanceador de carga 132 pode ser vista como extensão de uma concessão nos nós de balanceador de carga 110. Se um nó do balanceador de carga 110 não recebeu uma mensagem de disponibilização de conexão indicando um determinado fluxo de pacote em um período de tempo (por exemplo, dez segundos), então o nó do balanceador de carga 110 é livre para esquecer o respectivo fluxo de pacote.

Roteamento de caminhos múltiplos para os nós do balanceador de carga

[068] A Figura 4 ilustra aspectos do fluxo de pacotes e de roteamento no ba- lanceador de carga distribuída, de acordo com pelo menos algumas modalidades. Em pelo menos algumas modalidades, cada nó de ingresso (nós de ingresso são apresentados na Figura 4 como servidores de entrada 112) anuncia a sua capacidade de rotear um ou mais pontos de extremidade públicos (por exemplo, o endereço IP e porta) para o roteador de borda 104 para o balanceador de carga distribuída, por exemplo por meio do BGP (border gateway protocol na sigla em inglês). Em pelo menos algumas modalidades, ao invés de cada nó de ingresso se anunciar para o roteador de borda 104 por meio de uma sessão BGP, um ou mais nós de ingresso, por exemplo, dois nós vizinhos, poderão estabelecer sessões BGP com o roteador de borda 104 para anunciar o nó de ingresso, como mostrado na Figura 5.

[069] Balanceadores de carga convencionais podem normalmente servir apenas a um único ponto de extremidade público. Em contraste, modalidades do balan- ceador de carga distribuída permitem que vários nós do balanceador de carga 110 atendam a um único ponto de extremidade público. Dependendo da capacidade do roteador, isso permite configurações em que um único endereço IP público roteado para todos os servidores de entrada 112 possam administrar toda a largura de banda (por exemplo, 160 Gbps) através dos roteadores de borda 104. Em pelo menos algumas modalidades, para alcançar este objetivo, os roteadores de borda 104 podem utilizar uma técnica de roteamento de caminho múltiplo com em hash por fluxo de 4 camadas, por exemplo, uma técnica de roteamento ECMP, para distribuir o tráfego entre vários servidores de entrada 112 cada um anunciando o mesmo endereço IP público. Distribuição de pacotes de entrada para todos os servidores de entrada 112 usando fonte de 4 camadas e portas de destino para os fluxos como parte do fluxo hash dos roteadores de borda 104 pode geralmente manter os pacotes para cada conexão roteada para o mesmo nó do balanceador de carga 110 servindo como um servidor de ingresso 112 para prevenir pacotes fora do pedido. Deve ser notado, no entanto, que os roteadores de borda 104 podem usar outras técnicas para distribuir o tráfego entre os servidores de entrada 112 em algumas modalidades.

[070] A Figura 4 mostra também que dois ou mais balanceadores de carga distribuída podem ser implementados em uma rede 100. Os dois ou mais balancea- dores de carga distribuída podem cada um atuar como um balanceador de carga independente que FRONTS uma pluralidade de servidores 130, cada um anunciando um endereço IP público diferente, ou, alternativamente, como mostrado na Figura 4, dois ou mais balanceadores de carga distribuída podem cada um anunciar o mesmo endereço IP, e uma técnica de hashing (por exemplo, uma técnica de rotea- mento de caminho múltiplo por fluxo de 4 camadas) pode ser utilizada nos roteadores de borda 102 para partilhar os fluxos de pacote para fora dos roteadores de borda 104, que por sua vez distribuem os fluxos de pacote aos seus servidores de entrada 112 respectivos.

[071] A Figura 5 ilustra o uso do Border Gateway Protocol (BGP) para anunciar nós de ingresso para o roteador de borda, de acordo com pelo menos algumas modalidades. Neste exemplo, há quatro nós do balanceador de carga que servem como nós de ingresso 110A através de 110D na implementação do balanceador de carga. Roteador de borda104 roteia pacotes de entrada de clientes (não mostrados) para os nós de balanceador de carga 110. Em pelo menos algumas modalidades, o roteador de borda 104 pode tomar as decisões de roteamento de acordo com uma técnica de roteamento de caminhos múltiplos hash por fluxo de 4 camadas, por exemplo, uma técnica de roteamento de caminho múltiplo de custo igual (equal-cost multipath, ECMP na sigla em inglês).

[072] Em pelo menos algumas modalidades, o roteador de borda 104 percebe os nós de ingresso 110 que estão disponíveis no momento na implementação de balanceador de carga para receber tráfego de clientes por meio de sessões de anúncio de tecnologia do Border Gateway Protocol (BGP) iniciadas pelos nós de ingresso 110. Cada nó de ingresso 110 poderia usar BGP para anunciar-se ao roteador de borda 104. No entanto, o BGP normalmente leva um tempo relativamente longo para realizar conversão (três segundos ou mais). Usando esta técnica onde cada nó de ingresso 110 anuncia-se por meio do BGP, se um nó de ingresso 110 cai, ele pode demorar um tempo considerável em termos de rede (três segundos ou mais) para que a sessão BGP no roteador de borda 104 expire e, portanto, para que o roteador de borda 104 perceba o fechamento da falha e rotacione novamente os fluxos de TCP atuais para o nó de ingresso 110.

[073] Para evitar o problema da convergência com o BGP e para recuperar mais rapidamente após a falha do nó 110, em pelo menos algumas modalidades, em vez de um nó de ingresso 110 anunciar a si mesmo ao roteador de borda 104 por meio de uma sessão do BGP, pelo menos outro nó de ingresso 110 na implementação do balanceador de carga 110 fica com a responsabilidade de anunciar o nó de ingresso 110 ao roteador de borda 104 por meio do BGP. Por exemplo, em algumas modalidades, como mostrado na Figura 5, os nós de ingresso vizinhos à esquerda e à direita 110 de um determinado nó de ingresso 110, por exemplo os vizinhos da esquerda e da direita em uma lista ordenada dos nós 110, por exemplo um anel hash consistente formado pelos nós 110, podem anunciar o determinado nó de ingresso 110 para o roteador de borda 104. Por exemplo, na Figura 5, o nó de ingresso 110A anuncia os nós de ingresso 110B e 110D, o nó de ingresso 110B anuncia nós de ingresso 110A e 110C, o nó de ingresso 110C anuncia os nós de ingresso 110B e 110D e o nó de ingresso 110D anuncia os nós de ingresso 110C e 110A. Os nós de ingresso 110 verificam e se comunicam sobre a integridade uns dos outros como descrito mais tarde neste documento. Usando o método de verificação de integridade como descrito, nós não íntegros podem ser detectados e a informação pode ser propagada entre os nós 110 em menos de um segundo, por exemplo, em 100 milissegundos (ms). Ao determinar que um nó de ingresso 110 não é íntegro, os nós de ingresso 110 que anunciam o nó não íntegro podem parar imediatamente de anunciar o nó não íntegro 110. Em pelo menos algumas modalidades, os nós de ingresso 110 encerram as sessões BGP com o roteador de borda 104 enviando uma mensagem para encerramento do TCP ou algo similar para a sessão BGP para o roteador de borda 104. Assim, ao invés de esperar que uma sessão BGP estabelecida por um nó com falha 110 expire para detectar a falha do nó 110, o roteador de borda 104 pode descobrir o nó com falha 110 quando os outros nós de ingresso 110 que anunciam o nó com falha 110 encerram as sessões BGP com o roteador de borda 104 que anuncia o nó 110 ao detectar que o nó 110 é não íntegro. A administração das falhas do nó do balanceador de carga é mais discutida em relação às Figuras 18A e 18B mais adiante neste documento.

[074] A Figura 6 é um fluxograma de um método de roteamento de caminhos múltiplos, de acordo com pelo menos algumas modalidades do sistema de balanceamento de carga distribuída. Como indicado em 900, os nós de ingresso 110 em uma implementação de balanceador de carga anunciam seus nós vizinhos 110 para o roteador de borda 104. Em pelo menos algumas modalidades, os nós de ingresso 110 podem determinar seus nós vizinhos 110 de acordo com uma lista ordenada dos nós 110, como um anel hash consistente. Em pelo menos algumas modalidades, os nós de ingresso 110 anunciam seus nós vizinhos 110 ao roteador de borda 104 usando sessões BGP, com uma sessão BGP estabelecida para o roteador de borda 104 para cada nó 110 anunciado.

[075] Como indicado em 902, o roteador de borda 104 distribui o tráfego recebidos de clientes 160 para os nós de ingresso ativos (anunciados) 110 de acordo com uma técnica de roteamento de caminhos múltiplos por fluxo hashed, por exemplo uma técnica de roteamento de custo igual de caminhos múltiplos (ECMP). Em pelo menos algumas modalidades, o roteador de borda 104 expõe um endereço IP público para os clientes 160; os nós de ingresso 110 todos anunciam o mesmo endereço IP público para o roteador de borda 104. O roteador de borda usa uma fonte de 4 camadas e portas de destino como parte do hash de fluxo do roteador de borda 104 para distribuir os pacotes que chegam entre os nós de ingresso 110. Isto geral- mente mantém os pacotes para cada ligação roteados para o mesmo nó de ingresso 110.

[076] Como indicado em 902, a os nós de ingresso encaminham os fluxos de dados para mirar nos nós de servidor 130. Em pelo menos algumas modalidades, os nós de ingresso 110 interagem com os nós de rastreador fluxo primário e secundário para os fluxos de dados mapearem os fluxos de dados para os nós do servidor alvo 130. Assim, cada nó de ingresso 110 pode manter os mapeamentos de fluxos de dados por meio do nó 110 que pode ser utilizado para encaminhar apropriadamente os pacotes recebidos para os nós de servidor alvo 130.

[077] Elementos 906 até 910 referem-se a detecção e recuperação de falhas nos nós de ingresso 110. Como indicado em 906, os nós de ingresso 110 podem detectar que um nó de ingresso 110 caiu, por exemplo de acordo com uma técnica de verificação de integridade, como descrito neste documento. Ao detectar que o nó 110 caiu, seus nós vizinhos 110 param de anunciar o nó 110 para o roteador de borda 104. Em pelo menos algumas modalidades, isto envolve o envio de uma mensagem para encerramento do TCP para o roteador de borda 104 para a sessão BGP respectiva.

[078] Como indicado em 908, o roteador de borda 104, ao detectar que o nó de ingresso 110 caiu, por meio do encerramento das sessões BGP, redistribui o tráfego de entrada dos clientes 160 para os restantes nós de ingresso 110 de acordo com a técnica de roteamento de caminhos múltiplos por fluxo hashed. Assim, pelo menos alguns fluxos de dados podem ser roteados para diferentes nós de ingresso 110.

[079] Como indicado no 910, os nós de ingresso 110 podem recuperar mapeamentos conforme necessário e encaminhar os fluxos de dados para os nós de servidor alvo apropriados. Métodos para recuperação de falhas do nó 110 falhas nos nós de ingresso 110 são discutidas em outras partes deste documento. Como um exemplo, um nó de ingresso 110, ao receber um pacote para o qual ele não tem um mapeamento atual, pode usar uma função hash consistente para determinar um nó de rastreador de fluxo para o fluxo de dados de acordo com um anel hash consistente e recuperar o mapeamento do nó de rastreador de fluxo.

Fluxo de pacotes assimétrico

[080] Em pelo menos algumas modalidades, para utilizar eficientemente a largura de banda do nó de ingresso e uso da CPU quando a proporção de tráfego de saída em relação aos dados de entrada for maior do que 1, o sistema de balanceamento de carga distribuída encaminha pacotes de saída dos nós de servidor 130 para vários nós de egresso como mostrado na Figura 7. Em pelo menos algumas modalidades, para cada conexão, o módulo de balanceador de carga 132 no respectivo nó de servidor 130 HASHES o ponto de extremidade do cliente/tupla do ponto de extremidade público e usa um algoritmo de hash consistente para selecionar um nó do balanceador de carga 110 para servir como o servidor de egresso 114 para o respectivo fluxo de pacote de saída. No entanto, em algumas modalidades outros métodos e/ou os dados podem ser utilizados para selecionar os servidores de egresso 114 para conexões. O servidor de egresso selecionado 114 pode ser tipicamente, mas não necessariamente, um nó do balanceador de carga diferente 110 do nó do balanceador de carga 110 que serve como um servidor de ingresso 112 para a conexão. Em pelo menos algumas modalidades, a menos que haja uma falha deste nó do balanceador de carga 110/servidor de egresso 114, todos os pacotes de saída para a determinada conexão serão encaminhados para o mesmo servidor de egresso 114, a fim de evitar pacotes fora do pedido.

[081] Em pelo menos algumas modalidades, o método e os dados usados para a seleção de um servidor de egresso 114 pelos nós do servidor 130 podem ser diferentes do método e dos dados utilizados para a seleção de um servidor de ingresso 112 realizada pelos roteadores de borda 104. O uso dos diferentes métodos e dados pode resultar em geral em um nó do balanceador de carga diferente 110 sendo selecionado como o nó de egresso para uma determinada conexão do que o nó do balanceador de carga 110 selecionado como o nó de ingresso para a conexão, e também pode resultar em vários nós do balanceador de carga 110 sendo selecionados como nós de egresso para administrarem o tráfego de saída para conexões que passam por um único nó do balanceador de carga 110 que serve como um nó de ingresso.

[082] A Figura 7 ilustra graficamente o fluxo de pacotes assimétrico, de acordo com pelo menos algumas modalidades. Pelo menos uma conexão foi estabelecida a partir de clientes 160 na rede externa 150 por meio do servidor de ingresso 112 para cada um dos nós de servidor 130A, 130B, 130C e 130D. Em pelo menos algumas modalidades, para selecionar nós de egresso para as conexões, para cada conexão, o módulo de balanceador de carga 132 no respectivo nó de servidor 130 HASHES o ponto de extremidade do cliente/tupla do ponto de extremidade público e usa um algoritmo de hash consistente para selecionar um nó do balanceador de carga 110 para servir como o servidor de saída 114 para o respectivo fluxo de pacote de saída. Por exemplo, o nó do servidor 130A selecionou o servidor de egresso 114A para uma conexão, e o nó do servidor 114B selecionou o servidor de egresso 114A para uma conexão e o servidor de saída 114B para uma outra conexão. No entanto, em algumas modalidades outros métodos e/ou os dados podem ser utilizados para selecionar os nós de egresso para conexões.

Recuperação de falhas de nós de balanceador de carga, sem que a conexão do cliente caia

[083] Enquanto é possível que os nós do balanceador de carga 110 usem hashing consistente para determinar qual nó de servidor 130 deve receber o tráfego de clientes, devido ao longo tempo de vida de algumas conexões esta abordagem pode não manter os fluxos existentes nos casos onde um novo nó do servidor 130 junta-se à associação de hashing consistente e há uma falha do nó do balanceador de carga de ingresso 110 subsequente. Neste cenário, um nó do balanceador de carga 110 que assume um fluxo a partir da falha do nó 110 pode não ser capaz de determinar o mapeamento original selecionado, já que o anel hash consistente para os servidores 130 teria uma associação diferente. Assim, em pelo menos algumas modalidades, a tecnologia de tabela hash distribuída (DHT) pode ser usada pelos nós de balanceador de carga 110 para selecionar nós de servidor 130 para conexões de e para rotear pacotes para os nós de servidor selecionados 130. Uma vez que um nó do servidor 130 foi selecionado de acordo com o DHT para receber uma determinada conexão, e assumindo que o nó do servidor 130 permanece íntegro e que o módulo de balanceador de carga 132 no nó do servidor 130 continua a estender a concessão ao transmitir periodicamente o status daquela conexão ativa com o DHT (por exemplo, por meio da disponibilização da conexão), o DHT irá reter o mapeamento até que a conexão seja concluída. Uma falho do nó de ingresso 110 impacta a distribuição de pacotes do roteador de borda 104 para os nós de balancea- dor de carga restantes 110, resultando nos nós do balanceador de carga 110 que recebem o tráfego de um diferente conjunto de conexões do cliente. No entanto, uma vez que o DHT rastreia todas as conexões ativas, os nós de balanceador de carga 110 podem consultar o DHT para obter concessões para quaisquer mapeamentos ativos. Como resultado, todos os nós de balanceador de carga 110 nodos vão passar o tráfego aos nós de servidor corretos 130, evitando assim a falha de conexões de clientes ativos, mesmo no caso de falha de um nó do balanceador de carga de ingresso 110.

Fluxo de pacotes no sistema de balanceamento de carga distribuída

[084] A Figura 8 ilustra o fluxo de pacotes no sistema de balanceamento de carga distribuída, de acordo com pelo menos algumas modalidades. Deve ser notado que as linhas sólidas com setas na Figura 8 representam os pacotes TCP, en- quanto as linhas pontilhadas com setas representam pacotes UDP. Na Figura 8, um servidor de ingresso 112 recebe os pacotes TCP de um ou mais clientes 160 por meio do roteador de borda 104. Após a recepção de um pacote TCP, o servidor de ingresso 112 determina se ele tem um mapeamento para o fluxo de pacotes TCP para um nó do servidor 130. Se o servidor de ingresso 112 tem um mapeamento para o fluxo de pacotes TCP, então o servidor 112 encapsula o pacote TCP (por exemplo de acordo com o UDP) e envia o pacote encapsulado para o nó do servidor alvo 130. Se o servidor de ingresso 112 não tem um mapeamento para o fluxo de pacotes TCP, o servidor de ingresso 112 pode enviar uma mensagem UDP incluindo informações sobre o fluxo de pacotes TCP extraídas do pacote TCP para o rastrea- dor de fluxo primário 116A para estabelecer uma conexão com um nó do servidor 130 e/ou obter um mapeamento para o fluxo de pacotes TCP. Figuras 9A e 9B e Figuras 10A até 10G ilustram métodos para estabelecer uma conexão entre um cliente 160 e um nó de servidor 130. O módulo de balanceador de carga 132 em um nó de servidor 130 seleciona aleatoriamente nó(s) de balanceador de carga 110 para servir como o(s) servidor(es) de egresso 114 para conexão(ões) TCP no nó do servidor 130 e pacotes de resposta TCP encapsulados por UDP aos cliente(s) 160 por meio do(s) servidor(es) 114.

[085] As Figuras 9A e 9B proporcionam um fluxograma de fluxo de pacotes ao estabelecer conexões no sistema de balanceamento de carga distribuída, de acordo com pelo menos algumas modalidades. Tal como indicado em 200 da Figura 9A, um servidor de ingresso 112 recebe um pacote TCP de um cliente 160 através do roteador de borda 104. Em 202, se o servidor de ingresso 112 tem um mapeamento para o fluxo TCP para um nó do servidor 130, então o servidor de ingresso 112 encapsula e envia o pacote TCP ao respectivo nó do servidor 130, como indicado em 204. Deve ser notado que o servidor de ingresso 112 pode receber e processar continuamente pacotes para um, dois ou mais fluxos TCP de um, dois ou mais clientes 160.

[086] Em 202, se o servidor a entrada 112 não tem um mapeamento para o fluxo TCP, o pacote pode ser um pacote de sincronização (SYN) de TCP de um cliente 160. Como indicado em 206, após receber um pacote SYN, o servidor de ingresso 112 extrai dados do pacote SYN e encaminha os dados ao rastreador de dados primário 116A, por exemplo em uma mensagem UDP. Em pelo menos algumas modalidades, o servidor de ingresso 112 pode determinar o rastreador de fluxo primário 116A e/ou o rastreador de fluxo secundário 116B para o fluxo TCP de acordo com uma função hash consistente. Em 208, o rastreador de fluxo primário 116A armazena os dados, por exemplo, em uma tabela hash, gera um número de sequência TCP inicial para o lado do nó de servidor 130 da conexão TCP, e encaminha os da-dos e o número de sequência TCP para o rastreador de fluxo secundário 116B. Em 210, o rastreador de fluxo secundário 116B pode também armazenar os dados, fabricando e enviando um pacote SYN/ACK para o cliente 160, o pacote SYN/ACK contendo pelo menos o número de sequência TCP.

[087] Como indicado em 212, o servidor de ingresso 112 recebe um pacote de confirmação (ACK, de acknowledgement em inglês) de TCP do cliente 160 por meio do roteador de borda 104. O servidor de ingresso 112 neste momento não tem um mapeamento para o fluxo TCP para um nó de servidor 130, de modo que em 214 o servidor de ingresso 112 envia uma mensagem incluindo dados extraídos do pacote ACK para o rastreador de fluxo primário 116A. Como indicado em 216, ao receber a mensagem, o rastreador de fluxo primário 116A confirma o fluxo TCP de acordo com os dados armazenados, e confirma que o número de sequência de confirmação (+1) do pacote ACK coincide com o valor enviado em SYN/ACK. O rastreador de fluxo primário 116A seleciona então um nó de servidor 130 para receber o fluxo TCP, e envia uma mensagem contendo os dados, número de sequência TCP e endereço IP do módulo de balanceador de carga local 132 no nó do servidor selecionado 130 para o rastreador de fluxo secundário 116B. Como indicado em 218, o rastreador de fluxo secundário 116B também confirma o número de dados e sequência TCP, fabrica uma mensagem SYN, e envia a mensagem SYN fabricada para o módulo de ba- lanceador de carga local 132 no nó do servidor 130 selecionado. O método continua no elemento 220 da Figura 9B.

[088] Como indicado em 220 da Figura 9B, em resposta à mensagem SYN fabricada, o módulo de balanceador de carga 132 pode examinar uma ou mais métricas do nó do servidor 130 para determinar se o nó do servidor 130 pode aceitar a conexão. Em 222, se o módulo de balanceador de carga 132 determina que o nó do servidor 130 no momento não pode aceitar a conexão, então em 224 o módulo de balanceador de carga 132 envia uma mensagem para o rastreador de fluxo secundário 116B. O rastreador de fluxo secundário 116B pode apagar as informações para o fluxo que armazenou anteriormente. Em 226, o rastreador de fluxo secundário 116B envia uma mensagem ao rastreador de fluxo primário 116A. O rastreador de fluxo primário 116A pode então selecionar um novo nó do servidor alvo 130 e enviar uma mensagem para rastreador de fluxo secundário 116B, como indicado em 216 da Figura 9A.

[089] Em 222, se o módulo de balanceador de carga 132 determina que o nó do servidor 130 pode aceitar a conexão, em seguida, como indicado em 228 da Figura 9B o módulo de balanceador de carga local 132 constrói um pacote TCP SYN a partir do SYN fabricado e envia o pacote TCP SYN para o servidor 134 no nó do servidor 130. O endereço IP de origem do pacote TCP SYN é preenchido com o atual endereço IP do cliente 160 de modo que o servidor 134 irá crer que recebeu uma conexão TCP direta para o cliente 160. O módulo de balanceador de carga de 132 armazena detalhes relevantes sobre o fluxo TCP, por exemplo, em uma tabela hash local. Tal como indicado em 230, o servidor 134 responde com um pacote SYN/ACK o qual o módulo de balanceador de carga 132 intercepta. Como indicado em 232, o módulo de balanceador de carga 132 em seguida envia uma mensagem incluindo informações de conexão para o rastreador de fluxo secundário 116B para indicar que a conexão foi aceita. Após receber esta mensagem, em 234 o rastreador de fluxo secundário 116B registra o mapeamento para o servidor 134 e envia uma mensagem semelhante para o rastreador de fluxo primário 116A, que também registra as informações de mapeamento. Como indicado em 236, o rastreador de fluxo primário 116A em seguida encaminha uma mensagem de mapeamento para o servidor de ingresso 112. Servidor de ingresso 112 tem agora um mapeamento para o fluxo TCP do cliente 160 para o servidor 130.

[090] Em 238, o servidor de ingresso 112 encapsula e encaminha quaisquer pacotes de dados em buffer para o fluxo de dados para o módulo de balanceador de carga local 132 no nó do servidor 130. Pacotes de entrada adicionais para o fluxo de dados do cliente 160 recebidos pelo servidor de ingresso 112 são encapsulados e encaminhados diretamente para o módulo de balanceador de carga 132, que desen- capsula os pacotes e envia os pacotes de dados para o servidor 134.

[091] Em 240, o módulo de balanceador de carga 132 seleciona aleatoriamente um servidor de egresso 114 para o fluxo de dados. Subsequentes pacotes TCP de saída do servidor 134 são interceptados pelo módulo de balanceador de carga 132, encapsulado de acordo com o UDP, e encaminhados para o servidor de egresso arbitrariamente selecionado 114. O servidor de saída 114 desencapsula os pacotes de egresso e envia os pacotes TCP para o cliente 160.

[092] Como notado acima, em 202, se o servidor a entrada 112 não tem um mapeamento para o fluxo TCP de um pacote recebido, o pacote pode ser um pacote de sincronização (SYN) de TCP de um cliente 160. No entanto, o pacote pode não ser um pacote TCP SYN. Por exemplo, se a associação do nó do balanceador de carga 110 muda devido a adição ou falha de um nó do balanceador de carga 110, o roteador de borda 104 pode iniciar roteamento de pacotes para um ou mais fluxos TCP para o servidor de ingresso 112 para qual o servidor de ingresso 112 não tenha mapeamentos. Em pelo menos algumas modalidades, após a recepção de tal pacote para o qual o servidor de ingresso 112 não tem um mapeamento, o servidor de ingresso 112 pode utilizar a função hash consistente para determinar o rastreador de fluxo primário 116A e/ou o rastreador de fluxo secundário 116B para o fluxo TCP de acordo com o anel hash consistente e enviar uma mensagem para o rastreador fluxo primário 116A ou para o rastreador de fluxo secundário 116B para solicitar o mapeamento. Ao receber o mapeamento para o fluxo TCP de um rastreador de fluxo 116, o servidor de ingresso 112 pode armazenar o mapeamento e iniciar o encapsulamento e encaminhar o(s) pacote(s) TCP para o fluxo TCP para o nó do servidor de destino correto 130.

Detalhamento do nó do balanceador de carga

[093] Em pelo menos algumas modalidades, os nós de balanceador de carga 110 cada um tem três funções: • Ingresso - Receber todos os pacotes de entrada de um cliente 160 em uma conexão do cliente, rotear os pacotes para um nó do servidor 130 se o mapeamento for conhecido, ou enviar uma mensagem ao rastreador de fluxo se o mapeamento não for conhecido. Os pacotes de saída de um nó de ingresso são encapsulados (por exemplo, de acordo com o UDP) pelo nó de ingresso. • Rastreamento de fluxo - Manter o controle dos estados de conexão (por exemplo, qual nó do servidor 130/servidor 134 foi designado para servir cada conexão do cliente). Rastreadores de fluxo também participam no estabelecimento de conexões entre clientes 160 e servidores 134. • Egresso - Desencapsulamento e encaminhamento de pacotes de saída recebidos de um servidor 134 para um cliente 160.

[094] Em pelo menos algumas modalidades, na função de ingresso, um nó do balanceador de carga 110 é responsável por encaminhar pacotes aos servidores 134 quando um mapeamento cliente -> servidor é conhecido, ou encaminhar uma solicitação para um rastreador de fluxo quando o mapeamento é desconhecido. Em pelo menos algumas modalidades, um nó do balanceador de carga 110 que serve como um nó de ingresso para uma determinada conexão de cliente/fluxo de dados podem também servir como o rastreador de fluxo primário ou o rastreador de fluxo secundário para a conexão do cliente, mas não ambos.

[095] Em pelo menos algumas modalidades, na função de rastreador de fluxo, um nó do balanceador de carga 110 é responsável por manter o estado de conexões que ainda estão sendo estabelecidas, bem como manter o mapeamento cliente-> servidor para conexões estabelecidas. Dois rastreadores de fluxo estão envolvidos com cada conexão de cliente individual, referidos como rastreador de fluxo primário e rastreador de fluxo secundário. Em pelo menos algumas modalidades, os rastrea- dores de fluxo associados com conexões de cliente podem ser determinados utilizando um algoritmo de hash consistente. Os rastreadores de fluxo também executam a funcionalidade de balanceamento de carga incluindo, mas não se limitando a seleção pseudo-aleatória de um nó de servidor 130 para cada nova conexão do cliente. Note que o módulo de balanceador de carga local 132 em um nó de servidor selecionado 130 pode rejeitar uma solicitação de conexão, se isto determinar que o servidor 134 não pode administrar a conexão. Caso isto ocorra, então os rastreado- res de fluxo podem selecionar outro nó do servidor 130 e enviar a solicitação de conexão ao outro nó do servidor 130. Em pelo menos algumas modalidades, a função de rastreador de fluxo primário e a função de rastreador de fluxo secundário para uma determinada conexão são realizadas por diferentes nós de balanceador de carga 110.

[096] Em pelo menos algumas modalidades, na função de egresso, um nó do balanceador de carga 110 está sem monitoração de estado e desencapsula pacotes de entrada recebidos dos nós de servidor 130, executa alguma validação e encaminha os pacotes TCP de saída para os respectivos clientes 160. Em pelo menos al- gumas modalidades, um módulo de balanceador de carga local 132 em um nó de servidor 130 pode selecionar arbitrariamente um nó do balanceador de carga 110 para uma determinada conexão.

Topologia do anel hash consistente do nó do balanceador de carga

[097] Em pelo menos algumas modalidades, os nós de balanceador de carga 110 formam uma topologia de anel com base no hashing consistente do keyspace de entrada (ponto de extremidade do cliente, ponto de extremidade público). O keyspace de entrada pode ser dividido entre os nós do rastreador de fluxo disponíveis, e cada nó de rastreador de fluxo pode ser responsável por responder às consultas correspondentes ao seu keyspace. Em pelo menos algumas modalidades, os dados podem ser replicados para os nós de rastreador de fluxo primário e secundário com base no sucessor no anel hash consistente (por exemplo, o nó de rastreador de fluxo secundário é o nó sucessor, ou próximo nó no anel hash consistente, para o nó de rastreador de fluxo primário). Se um nó de rastreador de fluxo cai por algum motivo, o próximo nó do balanceador de carga no anel hash consistente adquire o keyspace do nó que falhou. Quando um novo nó de rastreador de fluxo se une, o nó registra seu ponto de extremidade (por exemplo, com um serviço de configuração 122 como mostrado na Figura 1), de modo que outros nós de balanceador de carga fiquem cientes sobre a alteração de configuração na implementação do balanceador de carga e, portanto, no anel hash consistente. A administração das adições e falhas dos rastreadores de fluxo no anel de hash consistente é discutida em maior detalhe em referência às Figuras 11A até 11D.

Nó de ingresso <-> comunicações do nó de rastreador de fluxo

[098] Em pelo menos algumas modalidades, os nós do balanceador de carga 110 servindo como nós de ingresso podem ficar cientes sobre os nós de balancea- dor de carga 110 servindo como nós de rastreador de fluxo do serviço de configuração 122. Os nós de ingresso podem monitorar o serviço de configuração 122 para alterações de associação na implementação do balanceador de carga e, portanto, no anel hash consistente. Quando um nó de ingresso recebe um pacote de um cliente 160 cujo nó de ingresso não tem um mapeamento, o nó de ingresso pode utilizar uma função hash consistente para determinar qual nó de rastreador de fluxo deverá executar o serviço no pacote. Em pelo menos algumas modalidades, a entrada para a função hash é o par (ponto de extremidade do cliente, ponto de extremidade público) do pacote. Em pelo menos algumas modalidades, os nós de ingresso e os nós de rastreador de fluxo se comunicam por meio de mensagens de UDP.

[099] Quando um nó de rastreador de fluxo primário recebe uma mensagem de um nó de ingresso para um novo fluxo de pacotes, o nó de rastreador de fluxo primário determina aleatoriamente um número de sequência TCP e encaminha outra mensagem para o nó de rastreador de fluxo secundário. O nó de rastreador de fluxo secundário gera uma mensagem TCP SYN/ ACK para o cliente. Ambos os rastrea- dores de fluxo têm memória do par de ponto de extremidade de conexão do cliente e o número de sequência TCP, e guardam esta informação até que a pressão de memória ou expiração fazem com que o estado seja removido.

[0100] Quando o nó de rastreador de fluxo primário recebe uma mensagem de um nó de ingresso que um pacote TCP ACK foi recebido, o nó de rastreador de fluxo primário verifica se o número de sequência de TCP confirmado corresponde ao valor armazenado que foi enviado no pacote SYN/ACK, selecciona um nó do servidor 130 para atender à solicitação e encaminha uma mensagem para o nó de ras- treador de fluxo secundário. O nó de rastreador de fluxo secundário envia uma mensagem ao módulo de balanceador de carga 132 no nó do servidor selecionado 130 para iniciar uma conexão TCP real com a pilha TCP no nó do servidor 130, e em seguida, aguarda uma resposta de confirmação do nó do servidor 130.

[0101] Quando o nó de rastreador fluxo secundário recebe uma confirmação de conexão do módulo de balanceador de carga 132 no nó do servidor 130, um fluxo de mensagem inverso através do rastreador de fluxo primário o nó de ingresso é desencadeado, armazenando informação sobre o nó do servidor associado 130 em ambos os nós. Deste ponto em diante, pacotes TCP adicionais recebidos no nó de ingresso são encaminhados diretamente para o módulo de balanceador de carga 132 no nó do servidor 130.

Módulo de balanceador de carga <-> Comunicações de nó do balanceador de carga

[0102] Em pelo menos algumas modalidades, cada módulo de balanceador de carga 132 registra seu ponto de extremidade com o serviço de configuração 122 e monitora o serviço de configuração 122 continuamente por alterações de associação na camada de nó do balanceador de carga. O que se segue descreve as funções do módulo de balanceador de carga 132 de acordo com pelo menos algumas modalidades: • Disponibilização de conexão - periodicamente (por exemplo, uma vez por segundo) ou não periodicamente divulgar o conjunto de conexões ativas (ponto de extremidade do cliente, ponto de extremidade público) no respectivo nó do servidor 130 para ambos rastreadores de fluxo primário e secundário responsáveis por essas conexões, bem como para os nós de ingresso que enviaram pacotes pela última vez para o módulo de balanceador de carga 132 para essas conexões. A função de dis- ponibilização de conexão renova a concessão para os estados de conexão nos nós de balanceador de carga responsáveis 110. • Alterações na associação de monitoramento na camada de balanceador de carga. Se a associação é alterada, os módulos de balanceamento de carga 132 podem usar estas informações para enviar imediatamente conexões ativas para os nós de balanceador de carga que agora são responsáveis pelas conexões.

Fluxo de pacotes no sistema de balanceamento de carga distribuída - detalhes

[0103] O sistema de balanceamento de carga distribuída pode incluir vários nós do balanceador de carga 110. Em pelo menos algumas modalidades, cada nó do balanceador de carga 110 no sistema de balanceamento de carga distribuída pode servir nas funções de um nó de rastreador de fluxo, um nó de egresso e um nó de ingresso para conexões do cliente 160 com os servidores 134. O sistema de balanceamento de carga distribuída pode também incluir um módulo de balanceador de carga 132 em cada nó do servidor 130.

[0104] As Figuras 10A a 10G ilustram o fluxo de pacotes no sistema de balanceamento de carga distribuída de acordo com pelo menos algumas modalidades. Nas Figuras 10A até 10G, pacotes trocados entre nós de balanceador de carga 110 e pacotes trocados entre nós de balanceador de carga 110 e nós do servidor 130 são mensagens UDP ou pacotes TCP de cliente encapsulados por UDP. Em pelo menos algumas modalidades, os pacotes TCP de cliente existem apenas na rede 100 em forma desencapsulada no lado norte dos nós de balanceador de carga 110 em trânsito para e a partir do roteador de borda 102 (ver Figura 1). Deve ser notado que as linhas sólidas com setas nas Figuras 10A-10G representam pacotes TCP, enquanto as linhas pontilhadas com setas representam pacotes UDP.

[0105] Em pelo menos algumas modalidades, o sistema de balanceamento de carga distribuída pode tentar preservar as conexões estabelecidas no caso de uma falha no nó do balanceador de carga único 110. Em pelo menos algumas modalidades, isto pode ser conseguido por meio da replicação dos detalhes da conexão em um nó de rastreador de fluxo primário e um nó de rastreador de fluxo secundário, de modo que, se qualquer um destes nós falhar, um mapeamento de conexão cliente- >servidor pode ser restaurado pelos nós de rastreador de fluxo restantes. Em pelo menos algumas modalidades, alguma perda de pacotes pode ocorrer em caso de falha de um nó; no entanto, retransmissões de cliente/pacote TCP de servidor podem recuperar os pacotes perdidos.

[0106] Cada conexão TCP de um cliente pode ser referida como um fluxo TCP, e identificada exclusivamente por 4 elementos que consistem em: o endereço IP do cliente, porta de cliente, endereço IP do servidor (público) e porta do servidor. Este identificador pode ser abreviado como CP ou CcPp indicando o par de ponto de extremidade público e do cliente. Os pacotes associados a qualquer fluxo TCP determinado (ou par CP) podem aparecer em qualquer nó do balanceador de carga 110 operando como um servidor de entrada 112 devido à distribuição de fluxo do ECMP hashed do roteador de borda a montante 104. No entanto, pacotes para um fluxo TCP podem em geral continuar a chegar ao mesmo nó do balanceador de carga 110 a não ser que haja um link ou falha no nó do balanceador de carga 110 que faça com que o fluxo TCP seja redirecionado. O nó do balanceador de carga 110 que recebe os pacotes de um fluxo TCP do roteador a montante 104 é referido como o nó de ingresso para o fluxo TCP.

[0107] Em pelo menos algumas modalidades, hashing consistente é utilizado de modo que quando os pacotes chegam em um nó do balanceador de carga 110 que serve como um nó de ingresso para o fluxo TCP, o nó de ingresso pode determinar qual nó do balanceador de carga 110 contém o estado para o fluxo TCP (ou seja, o nó de rastreador de fluxo). O par CP pode ser submetido a hash pelo nó de ingresso para dentro de um anel hash consistente para determinar qual nó do balan- ceador de carga 110 é responsável por manter informações de estado no que diz respeito ao fluxo TCP. Este nó serve como o rastreador de fluxo primário para o fluxo TCP. O nó sucessor no anel hash consistente serve como o rastreador de fluxo secundário para o fluxo TCP.

[0108] Em pelo menos algumas modalidades, todos os nós de balanceador de carga 110 podem servir como nós de ingresso, nós de rastreador de fluxo primário e nós rastreador de fluxo secundário. Dependendo do resultado de hash consistente para um fluxo TCP, um nó do balanceador de carga 110 que serve como nó de in- gresso para o fluxo TCP pode também servir como o nó de rastreador de fluxo primário ou secundário para o fluxo TCP. No entanto, em pelo menos algumas modalidades, diferentes nós de balanceador de carga física 110 executam as funções de rastreador de fluxo primário e secundário para o fluxo TCP.

Estabelecendo Conexões

[0109] Fazendo referência à Figura 10A, novas conexões de um cliente 160 podem ser desencadeadas por um pacote de sincronização (SYN) de cliente TCP. Os nós de balanceador de carga 110 na verdade não estabelecem uma conexão com um nó de servidor 130 mediante o recebimento do pacote SYN, nem imediatamente selecionam um nó de servidor 130 para receber a conexão. Em vez disso, os nós de balanceador de carga 110 armazenam dados relevantes de pacotes SYN do cliente, e geram um pacote SYN/ACK em nome do nó do servidor 130 a ser escolhido ainda. Referindo-se a Figura 10C, uma vez que o cliente 160 responde com o primeiro pacote ACK no handshake de três vias TCP, os nós de balanceador de carga 110 selecionam um nó do servidor 130, geram um pacote SYN equivalente para aquele nó do servidor 130, e tentam estabelecer uma conexão TCP real com o nó do servidor 130.

[0110] Fazendo novamente referência à Figura 10A, após receber um pacote SYN do cliente no nó do balanceador de carga 110 que serve como o servidor de ingresso 112 para o fluxo TCP, o servidor de ingresso 112 extrai os campos de dados do pacote SYN e encaminha os dados para o rastreador de fluxo primário 116A para o fluxo TCP. O rastreador de fluxo primário 116A armazena os dados, por exemplo, em uma tabela hash, gera um número de sequência TCP inicial (para o lado do servidor da conexão TCP) e encaminha os mesmos dados para o rastreador de fluxo secundário 116B. O rastreador de fluxo secundário 116B fabrica um pacote SYN/ACK para o cliente 160 contendo aquele número de sequência TCP dp servidor.

[0111] Na Figura 10A, o servidor de ingresso 112, as funções do rastreador de fluxo primário 116A e rastreador de fluxo secundário 116B são realizadas por diferentes nós do balanceador de carga 110. No entanto, em alguns casos, o nó do balanceador de carga 110 que serve como o servidor de ingresso 112 para um fluxo TCP pode ser o mesmo nó 110 que serve como rastreador de fluxo primário 116A ou rastreador de fluxo secundário 116B para o fluxo TCP (mas não ambos). A razão pela qual o servidor de ingresso 112 para um fluxo de pacote pode estar no mesmo nó 110 como um rastreador de fluxo 116 para o fluxo é que o roteador de borda 104 seleciona de modo pseudo-aleatório o servidor de ingresso 112 para o fluxo de acordo com uma técnica de roteamento de caminho múltiplo hashed por fluxo (por exemplo, uma técnica de roteamento ECMP), enquanto os rastreadores de fluxo 116 para o fluxo de pacote são determinados em um anel hash consistente de acordo com uma função hash consistente aplicada as informações de endereço do fluxo de pacote. Se o servidor de ingresso 112 para um fluxo de pacote está no mesmo nó 110 como um rastreador de fluxo 116 para o fluxo de pacote, os dados do pacote SYN só podem ser transmitidos a partir do nó 110 que implementa o servidor de ingresso 112 para o outro nó 110 do rastreador de fluxo 116. Por exemplo, na Figura 10B, o rastreador de fluxo primário 116A está no mesmo nó do balanceador de carga 110A que o servidor de ingresso 112 para o fluxo TCP, enquanto o rastreador fluxo secundário 116B está em um nó do balanceador de carga 110B diferente, e, assim, os dados do pacote SYN são encaminhados do nó 110A (pelo rastreador de fluxo 116A) para o rastreador de fluxo secundário 116B no nó do balanceador de carga 110B.

[0112] Referindo-se a Figura 10C, quando os pacotes não-SYN chegam a um servidor de ingresso 112, o servidor de ingresso 112 sabe ou não a qual nó de servidor 130 deve encaminhar os pacotes. O primeiro pacote não-SYN a chegar a um servidor de ingresso 112 para um fluxo TCP deve ser o primeiro pacote de reconhe- cimento (ACK) TCP no handshake de três vias TCP (ou, possivelmente, um pacote de dados subsequente), onde o campo de número de reconhecimento TCP combina com o número de sequencia do servidor (+1) que foi enviado ao pacote SYN/ACK na Figura 10A. Quando o servidor de ingresso 112 recebe um pacote não-SYN para o qual não tem mapeamento de servidor, ele encaminha uma mensagem ao rastrea- dor de fluxo primário 116A para o fluxo TCP, a mensagem incluindo informações do pacote ACK como um número de seqüência, ou, alternativamente, contendo o próprio pacote ACK. Em pelo menos alguns casos, o rastreador de fluxo primário 116A memoriza os dados armazenados para o fluxo TCP e confirma que o número de sequência reconhecida (+1) corresponde ao valor que foi enviado para o cliente 160 no pacote SYN/ACK. O rastreador de fluxo primário então seleciona um nó de servidor 130 para o fluxo TCP e encaminha outra mensagem contendo os dados armazenados anteriormente para o fluxo TCP, o número de sequência do servidor e um endereço IP para o módulo de balanceador de carga 132 no nó do servidor selecionado 130 para o rastreador de fluxo secundário 116B. O rastreador de fluxo secundário 116B confirma o número de sequência do servidor, registra as informações e envia uma mensagem SYN fabricada para o módulo de balanceador de carga 132 no nó do servidor selecionado 130. O ponto de extremidade CP no fluxo TCP está agora mapeado para o módulo de balanceador de carga 132/nó do servidor 130. O módulo de balanceador de carga 132 no nó do servidor 130 é responsável por criar um legítimo pacote TCP SYN para o servidor 134 no nó do servidor 130 quando ele recebe a mensagem SYN fabricada do rastreador fluxo secundário 116B. Ao criar o pacote SYN, o endereço IP de origem é preenchido com o endereço IP real do cliente 160 de modo que o servidor 134 irá crer que recebeu uma solicitação de conexão TCP direta do cliente 160. O módulo de balanceador de carga 132 armazena os detalhes relevantes sobre o fluxo TCP, por exemplo, em uma tabela hash local, e envia o pacote TCP SYN para o servidor 134 (por exemplo, injeta o pacote SYN no kernel do

Linux do servidor 134).

[0113] Na Figura 10C, o servidor de ingresso 112, as funções do rastreador de fluxo primário 116A e rastreador de fluxo secundário 116B são realizadas por diferentes nós do balanceador de carga 110. No entanto, em alguns casos, o nó do balanceador de carga 110 que serve como o servidor de ingresso 112 para um fluxo TCP será o mesmo nó 110 que serve como rastreador de fluxo primário 116A ou rastreador de fluxo secundário 116B para o fluxo TCP (mas não ambos). Por exemplo, na Figura 10D, o rastreador de fluxo secundário 116B está no mesmo nó do ba- lanceador de carga 110A que o servidor de entrada 112 para o fluxo TCP, enquanto o rastreador de fluxo primário 116A está em um nó do balanceador 110B diferente.

[0114] Referindo-se a Figura 10E, o servidor 134 (por exemplo, o kernel do Linux) responde com um pacote SYN/ACK que o módulo balanceador de carga 132 também intercepta. O pacote SYN/ACK pode conter um número de sequência TCP diferente do que foi entregue originalmente ao cliente 160 no SYN/ACK que foi gerado a partir do rastreador de fluxo secundário 116B (ver Figura 10A). O módulo de balanceador de carga 132 é responsável por aplicar o número de sequência delta aos pacotes de entrada e de saída. O pacote SYN/ACK do servidor 134 também aciona uma mensagem (por exemplo, uma mensagem de UDP) a partir do módulo de balanceador de carga 132 de volta para o rastreador de fluxo secundário 116B para indicar que a ligação com o nó do servidor selecionado 130/ módulo de balan- ceador de carga 132/servidor 134 foi bem-sucedido. Após receber esta mensagem, o rastreador de fluxo secundário 116A pode registrar o mapeamento de par de ponto de extremidade público e do cliente (CP) entre o cliente 160 e o servidor 134 como comprometidos, e enviar uma mensagem semelhante para o rastreador de fluxo pri-mário 116A que também irá registrar o mapeamento CP. O rastreador de fluxo primário 116A pode então enviar uma mensagem de mapeamento CP para o servidor de ingresso 112, o que faz com que o servidor de ingresso 112 encaminhe quais- quer pacotes de dados em buffer para a conexão ao módulo de balanceador de carga local 132 no nó do servidor 130 como pacotes de dados encapsulados.

[0115] Referindo-se a Figura 10F, o mapeamento CP para a conexão é conhecido pelo servidor de ingresso, de modo que os pacotes TCP de entrada recebidos pelo servidor de ingresso 112 para a conexão podem ser encapsulados (por exemplo, de acordo com UDP) e encaminhados diretamente ao módulo de balance- ador de carga local 132 no nó do servidor 130 como pacotes de dados encapsulados. O módulo de balanceamento de carga 132 desencapsula os pacotes de dados e envia os pacotes TCP para o servidor 134 no nó de servidor 130, por exemplo, injetando os pacotes TCP em uma pilha TCP no kernel. Pacotes de saída do servidor 134 são interceptados pelo módulo de balanceador de carga 132 no nó do servidor 130, encapsulados (por exemplo, de acordo com o UDP) e encaminhados para um nó do balanceador de carga arbitrária 110 que o módulo de balanceador de carga 132 seleciona aleatoriamente como o servidor de egresso 114 para esta conexão. O servidor de saída 114 desencapsula os pacotes e envia os pacotes desen- capsulados para o cliente 116. A função egressa do nó do balanceador de carga selecionado 110 é sem monitoração de estado, por isso, um nó do balanceador de carga diferente 110 pode ser selecionado como o servidor de egresso 114 para a conexão em caso de falha do nó do balanceador de carga 110 servindo como o servidor de egresso. No entanto, em geral, o mesmo nó do balanceador de carga 110 é utilizado como o servidor de egresso 114 para a duração da conexão para reduzir ou eliminar a reordenação dos pacotes de saída.

[0116] Referindo-se a Figura 10G, em pelo menos algumas modalidades, se o módulo de balanceador de carga 132A em um nó de servidor 130A que é selecionado pelo rastreador de fluxo primário 116A (ver Figura 10C) determina que está sobrecarregado, ele tem a opção de rejeitar o a mensagem SYN fabricada recebida do rastreador de fluxo secundário 116B (ver Figura 10C). Em pelo menos algumas mo- dalidades, a mensagem SYN fabricada inclui um valor de vida útil (VU) ou contador que permite um número máximo de rejeições. Em pelo menos algumas modalidades, se este valor VU chega a zero, o módulo de balanceador de carga 132A pode aceitar a conexão ou cortar a conexão para descarregar carga. Se o módulo de ba- lanceador de carga 132A decide rejeitar a conexão, ele diminui o valor VU e envia uma mensagem para rejeitar o rastreador de fluxo secundário 116B. O rastreador de fluxo secundário 116B redefine o mapeamento CP e envia uma mensagem de liberação para o rastreador de fluxo primário 116A para fazer o mesmo. O rastreador fluxo primário 116A escolhe um novo módulo de balanceador de carga 132B em outro nó de servidor 130B e envia uma nova mensagem alvo de volta para o rastreador de fluxo secundário 116B, que envia uma nova mensagem SYN fabricada ao módulo balanceador de carga recém-escolhido 132B. Observe que quedas de pacote podem fazer com que essa sequência não se complete; no entanto, uma retransmissão do cliente 160 pode desencadear o processo de seleção do módulo de balanceador de carga novamente no rastreador de fluxo primário 116A, que pode, mas não necessariamente, escolher o mesmo módulo de balanceador de carga 132 para a conexão se ele não tomou conhecimento sobre a rejeição anterior do pacote SYN fabricado.

[0117] Em pelo menos algumas modalidades, o contador VU pode ser utilizado para evitar continuamente o envio de solicitações de conexão para os nós do servidor 130, que podem ocorrer, por exemplo, se todos os nós do servidor 130 estiverem ocupados. Em pelo menos algumas modalidades, cada vez que um módulo de balanceador de carga 132 rejeita uma solicitação de conexão em nome de um respectivo nó do servidor 130, o módulo de balanceador de carga 132 diminui o contador VU. Os nós do rastreador de fluxo 116 podem monitorar o contador VU e, desde que o contador VU não seja zero (ou esteja acima de um limiar especificado), podem selecionar outro nó de servidor 130 e fazer outra tentativa. Se o contador VU chega a zero (ou atinge o limiar especificado), a solicitação de conexão é descartada e não são feitas mais tentativas pelos nós de rastreador de fluxo 116 para enviar uma solicitação de conexão para um dos nós de servidor selecionados 130 para aquela conexão. Em pelo menos algumas modalidades, uma mensagem de erro pode ser enviada para o respectivo cliente 160.

[0118] Em pelo menos algumas modalidades, o sistema de balanceador de carga distribuída suporta múltiplos endereços IP públicos. Como tal, é possível que um cliente 160 possa iniciar duas conexões TCP a partir do mesmo número de porta de cliente para dois endereços IP públicos diferentes. Essas conexões TCP são distintas do ponto de vista do cliente 160, mas internamente o balanceador de carga distribuída pode mapear as conexões para o mesmo nó do servidor 130, o que resultaria em uma colisão. Em pelo menos algumas modalidades, para detectar e administrar possíveis colisões, o módulo de balanceador de carga 132 ao receber o pacote SYN fabricado do rastreador de fluxo secundário 116B como mostrado nas Figuras 10C e 10D, pode comparar a informação de endereço com suas ligações ativas e, se esta conexão puder vir a causar uma colisão, rejeitar a solicitação de conexão, como mostrado na Figura 10G.

Administração de falhas e adições do nó do balanceador de carga

[0119] Em muitos balanceadores de carga convencionais, algumas ou todas as conexões existentes são perdidas no caso de uma falha do balanceador de carga. Em pelo menos algumas modalidades, no caso de falha de um nó do balancea- dor de carga individual 110, o sistema de balanceamento de carga distribuída pode manter pelo menos algumas das conexões estabelecidas de modo que os clientes e os servidores podem continuar a troca de pacotes por meio das conexões até que as conexões sejam concluídas normalmente. Além disso, o sistema de balanceamento de carga distribuída pode continuar a servir as conexões que estavam no processo de serem estabelecidas no momento da falha.

[0120] Em pelo menos algumas modalidades do sistema de balanceamento de carga distribuída, um protocolo de recuperação de falha pode ser implementado, podendo recuperar conexões de cliente existentes, no caso de uma falha no nó do balanceador de carga única 110. No entanto, várias falhas de nós de balanceador de carga 110 podem resultar em conexões de clientes perdidas. Em pelo menos algumas modalidades, as retransmissões TCP entre um cliente 160 e um servidor 134 podem ser utilizadas como um meio de recuperação após uma falha do nó do balan- ceador de carga 110.

[0121] Além de falhas potenciais no nó do balanceador de carga 110, novos nós do balanceador de carga 110 podem ser adicionados ao sistema de balancea- dor de carga distribuída. Esses novos nós 110 podem ser adicionados à camada do balanceador de carga e, portanto, para o anel hash consistente e as funções do nó do balanceador de carga 110 no que diz respeito a conexões de clientes existentes podem ser ajustadas de acordo com a alteração, conforme necessário.

Fluxo de Administração rastreador falhas dos nós e adições

[0122] Em pelo menos algumas modalidades, conforme cada conexão é estabelecida (ver, por exemplo, as Figuras 10A até 10G), as informações do estado da conexão são passadas por meio de dois nós do balanceador de carga 110, referidos como rastreadores de fluxo primário e secundário, que podem ser determinados usando um algoritmo de hash consistente que, por exemplo, usa a tupla (IP do cliente: porta, IP público: porta) como uma entrada de função hash. No caso de uma falha de um nó do balanceador de carga única 110, pelo menos um dos nós do balan- ceador de carga 110 remanescentes pode continuar a ser mapeado por meio da função hash consistente e pode conter a informação de estado necessária para uma conexão direcionar os pacotes ao nó de servidor selecionado 130 para uma conexão. Além disso, no caso de uma adição de um nó do balanceador de carga 110 ao anel hash consistente, informações do estado para conexões podem ser atualizadas para os rastreadores de fluxo apropriados.

[0123] Figuras 11A a 11D ilustram a administração de eventos que afetuam a filiação no anel hash compatível de nó do balanceador de carga, de acordo com pelo menos algumas modalidades. Estes eventos podem incluir, mas não estão limitados a, a adição de um novo nó de rastreador de fluxo primário, adição de um novo nó de rastreador de fluxo secundário, falha de um nó de rastreador de fluxo primário e falha de um nó de rastreador de fluxo secundário.

[0124] A Figura 11A ilustra a administração da adição de um novo nó de ras- treador de fluxo primário ao anel hash consistente. A linha superior da Figura 11A mostra o rastreador fluxo 116A como o rastreador de fluxo primário para uma ou mais conexões do cliente e nó de rastreador de fluxo 116B como o rastreador de fluxo secundário para a(s) mesma(s) conexão(ões). Na linha inferior da Figura 11A, um novo nó de rastreador de fluxo 116C foi adicionado, tornando-se o rastreador de fluxo primário para a(s) conexãs(ões) do cliente. Nó do rastreador de fluxo 116A, anteriormente o rastreador de fluxo primário, torna-se o rastreador de fluxo secundário, enquanto o nó de rastreador fluxo 116B, anteriormente o rastreador de fluxo secundário, torna-se um próximo rastreador de fluxo no anel hash consistente. A informação de estado para a(s) ligação(ões) do cliente que foram mantidas por rastrea- dores de fluxo 116A e 116B podem ser fornecidas para o novo rastreador de fluxo primário 116C. Além disso, o rastreador de fluxo 116B pode "esquecer" suas conexões anteriormente rastreadas quando na função de rastreador de fluxo secundário.

[0125] A Figura 11B ilustra a administração da adição de um novo nó de ras- treador de fluxo secundário ao anel hash consistente. A linha superior da Figura 11B mostra o rastreador fluxo 116A como o rastreador de fluxo primário para uma ou mais conexões do cliente e nó de rastreador de fluxo 116B como o rastreador de fluxo secundário para a(s) mesma(s) conexão(ões). Na linha inferior da Figura 11B, um novo nó de rastreador de fluxo 116C foi adicionado, tornando-se o rastreador de fluxo secundário para a(s) conexão(ões) do cliente. Nó do rastreador de fluxo 116A permanece como o rastreador de fluxo primário para a(s) conexão(ões), enquanto o nó de rastreador de fluxo 116B, anteriormente o rastreador de fluxo secundário, torna-se um próximo rastreador de fluxo no anel hash consistente. A informação de estado para a(s) conexão(ões) do cliente que foram mantidas por rastreadores de fluxo 116A e 116B podem ser fornecidas para o novo rastreador de fluxo secundário 116C. Além disso, o rastreador de fluxo 116B pode "esquecer" suas conexões anteriormente rastreadas quando na função de rastreador de fluxo secundário.

[0126] A Figura 11C ilustra o gerenciamento de falha de um nó de rastreador de fluxo primário no anel hash consistente. A linha superior da Figura 11C mostra rastreador fluxo 116A como o rastreador de fluxo primário para uma ou mais conexões de clientes, fluxo nó de rastreador de fluxo 116B como o rastreador de fluxo secundário para a(s) mesma(s) conexão(ões), e nó de rastreador de fluxo 116C como um próximo rastreador de fluxo no anel hash consistente. Na linha inferior da Figura 11C, o nó de rastreador de fluxo primário 116A apresentou uma falha. Nó de rastreador de fluxo 116B torna-se o rastreador de fluxo primário para a(s) cone- xão(ões), enquanto o nó de rastreador de fluxo 116C torna-se o rastreador de fluxo secundário para a(s) conexão(ões). A informação de estado para a(s) conexão(ões) de cliente é mantida pelo rastreador de fluxo 116B e pode ser fornecida para o novo rastreador de fluxo secundário 116C.

[0127] A Figura 11D ilustra o gerenciamento de falha de um nó de rastreador de fluxo secundário no anel hash consistente. A linha superior da Figura 11D mostra rastreador fluxo 116A como o rastreador de fluxo primário para uma ou mais conexões de clientes, fluxo nó de rastreador de fluxo 116B como o rastreador de fluxo secundário para a(s) mesma(s) conexão(ões), e nó de rastreador de fluxo 116C como um próximo rastreador de fluxo no anel hash consistente. Na linha inferior da Figura 11D, o nó de rastreador de fluxo secundário 116B apresentou uma falha. Nó de rastreador de fluxo 116A permanece como o rastreador de fluxo primário para a(s) conexão(ões), enquanto o nó de rastreador de fluxo 116C torna-se o rastreador de fluxo secundário para a(s) conexão(ões). A informação de estado para a(s) cone- xão(ões) de cliente é mantida pelo rastreador de fluxo 116B e pode ser fornecida para o novo rastreador de fluxo secundário 116C.

[0128] Em pelo menos algumas modalidades, os módulos de balanceamento de carga 132 nos nós de servidor 130 realizam disponibilização de conexão aos nós do balanceador de carga 110. Em pelo menos algumas modalidades, a disponibili- zação da conexão periodicamente (por exemplo, uma vez por segundo) ou não periodicamente empurra as informações de estado de conexão atual dos nós de servidor 130 para os nós do balanceador de carga 110 servindo como nós de rastreador de fluxo e nós de ingresso, que atuam para atualizar ou restaurar os mapeamentos de conexão para os nós de rastreador de fluxo primário e secundário para as conexões. Em pelo menos algumas modalidades, um módulo de balanceamento de carga 132 pode detectar uma alteração de associação de rastreador de fluxo, por exemplo, como ilustrado nas Figuras 11A a 11D. Em resposta, o módulo de balanceador de carga 132 pode executar uma publicação de conexão para preencher as informações de estado para as conexões nos nós de rastreador de fluxo primário e secun-dário, que podem ter sido alteradas para as conexões quando houve alteração na associação. Deve ser notado que a disponibilização de conexão pode permitir pelo menos que algumas conexões sejam recuperadas no caso de múltiplas falhas de nós do balanceador de carga.

Fluxo de mensagens relacionadas à falhas

[0129] Em pelo menos algumas modalidades, o protocolo entre os nós de ras- treador de fluxo primário e secundário pode incluir uma correção ou funcionalidade de sincronização. Por exemplo, referindo-se a Figura 11A, quando um novo rastrea- dor de fluxo primário 116C une-se ao anel hash consistente, o novo nó 116C pode reivindicar o keyspace de hash consistente para algum número de conexões (~ 1/N) e começar a receber tráfego relacionado a estas conexões do roteador de borda 104. No entanto, o novo nó de rastreador de fluxo primário 116C não tem qualquer estado armazenado para as conexões, de modo que pode operar em cada pacote como se fosse o primeiro pacote recebido do cliente 160. O rastreador de fluxo primário é responsável pela geração de números de sequência TCP do servidor em resposta a pacotes SYN (ver, por exemplo, Figura 10A) e pela seleção dos nós de servidor 130 em resposta ao primeiro pacote ACK do cliente 160 (ver, por exemplo, Figura 1) , e esses valores gerados podem discordar de valores escolhidos pelo ras- treador de fluxo primário anterior (nó de rastreador de fluxo 116A na Figura 11A). No entanto, em pelo menos algumas modalidades do algoritmo de hash consistente atribui o rastreador de fluxo primário anterior (nó de rastreador de fluxo 116A na Figura 11A) para a função de rastreador de fluxo secundário, e este rastreador de fluxo ainda mantém o estado previamente armazenado para as composições. Assim, pelo menos em algumas modalidades, quando o rastreador de fluxo secundário (nó de rastreador de fluxo 116A na Figura 11A) detecta uma discrepância na informação recebida do rastreador de fluxo primário 116C, ele pode enviar mensagens de atualização de volta para o rastreador de fluxo primário 116C para trazer o dois nós de balanceador de carga 110 servindo como rastreadores de fluxo para as conexões em sincronização. Métodos semelhantes podem ser utilizados para sincronizar os rastreadores de fluxo após outras mudanças na associação do anel hash consistente.

Detalhes do módulo de balanceador de carga

[0130] Em pelo menos algumas modalidades, o módulo de balanceador de carga 132 é um componente do sistema de balanceamento de carga distribuída que reside em cada um dos nós de servidor 130. Funções do nó do balanceador de carga 132 incluem, mas não estão limitadas a, desencapsulamento dos pacotes recebidos dos nós do balanceador de carga 110 e envio dos pacotes desencapsulados para o servidor 134 no nó do servidor 130, e encapsulamento dos pacotes de saída do servidor 134 e o envio dos pacotes encapsulados para um nó do balanceador de carga 110.

[0131] Em pelo menos algumas modalidades, os pacotes de entrada para os módulos de balanceador de carga 132 nos nós de servidor 130 dos nós de balance- ador de carga 110 servindo como servidores de ingresso 112 são um pacotes de protocolo (por exemplo, UDP) sem monitorização de estado que encapsulam os pacotes reais de dados de clientes. Cada pacote de dados de cliente encapsulado tem o clienteIP:port de um respectivo cliente 160 como o endereço de origem e o publi- cIP: port do servidor 134 como o endereço de destino. Os de módulos balanceador de carga 132 tiram o encapsulamento dos pacotes de dados de cliente e enviam os pacotes aos respectivos servidores 134 nos nós de servidor 130, por exemplo, ao redirecionar os pacotes para um fluxo TCP localhost.

[0132] Em pelo menos algumas modalidades, pacotes de saída dos servidores 134 para os nós de balanceador de carga 110 servindo como servidores de egresso 114 são pacotes de protocolo (por exemplo, UDP) sem monitoração de estado que encapsulam os pacotes IP de saída. Os módulos de balanceador de carga 132 encapsulam os pacotes IP de saída e enviam os pacotes encapsulados aos servidores de egresso 114 por meio da malha 120. Cada pacote IP de saída encapsulado tem o publicIP: port do servidor 134 como o endereço de origem e clientIP:port de um respectivo cliente 160 como um endereço de destino.

Funcionalidade do módulo balanceador de carga

[0133] Em pelo menos algumas modalidades, as funções do módulo de ba- lanceador de carga 132 em um nó de servidor 130 podem incluir um ou mais de, mas não estão limitados a: • Túneis de UDP de terminação do(s) nó(s) do balanceador de carga 110, por exemplo, do servidor de ingresso 112 administrando uma conexão para um cliente 160. Isto inclui a remoção do encapsulamento UDP dos pacotes de dados de entrada do cliente recebidos dos servidores de ingresso 112. • Seleção de um servidor de egresso 114 para receber o tráfego de saída para uma conexão. • Interceptação dos pacotes IP de saída em uma conexão com o respectivo servidor 134, encapsulamento dos pacotes IP de saída para a conexão, e envio dos pacotes encapsulados para o servidor de egresso 114. • Desconfiguração do número de sequência em pacotes de entrada e de saída de modo que o número de sequência esteja alinhado com o número de sequência gerado pelos nós de rastreador de fluxo 116 quando os nós de rastreador de fluxo 116 enviaram um SYN/ACK para o cliente 160. • Tomada de decisão sobre a possibilidade de aceitar ou rejeitar uma conexão para o respectivo servidor 134, por exemplo, com base em uma ou mais métricas indicando a carga atual do respectivo servidor 134. • Detecção e rejeição de conexões do mesmo endereço clientIP:port para o respectivo servidor 134 se houver uma conexão ativa para que que aquele endereço clientIP:port evite colisões. • Rastreamento de conexão e disponibilização de conexão.

Informação de configuração do módulo de balanceador de carga

[0134] Em pelo menos algumas modalidades, cada módulo de balanceador de carga 132 pode adquirir e armazenar localmente um ou mais, mas não limitado aos seguintes conjuntos de informações para sua configuração: um conjunto de pontos de extremidade de nó do balanceador de carga 110; um conjunto de endereços IP públicos válidos que eles devem servir; e o(s) número(s) de porta nos quais o respectivo servidor 134 aceita conexões de entrada. Em menos algumas modalidades, esta informação pode ser adquirida a partir de ou atualizada pelo acesso ou consulta a um componente deserviço de configuração 122 do sistema de balancea- dor de carga distribuída, como ilustrado na Figura 1. Outros métodos de aquisição de informações podem ser utilizados em algumas modalidades.

Administração de pacote de módulo de balanceador de carga

[0135] A seguir são descritas operações do módulo de balanceador de carga 132 para o tráfego de entrada e tráfego de saída de acordo com pelo menos algumas modalidades. Em pelo menos algumas modalidades, quando um pacote de dados de entrada é recebido pelo módulo de balanceador de carga 132, o pacote de dados é desencapsulado do pacote UDP, e o endereço de destino no pacote TCP desencapsulado é validado pela primeira vez contra um conjunto de endereços de IP públicos configurados. Se não houver correspondência, o pacote é descartado ou ignorado. Em pelo menos algumas modalidades, o módulo de balanceador de carga 132 pode ajustar o número de sequência no cabeçalho TCP por um delta constante, de modo que o número de sequência coincide com o número de sequência escolhido aleatoriamente gerado pelos nós de rastreador de fluxo 116 que enviaram o pacote SYN/ACK para o cliente 160. O módulo de balanceador de carga 132 registra o mapeamento do ponto de extremidade [Cliente: Public] para o ponto de extremidade [Cliente: Servidor] como um estado interno.

[0136] Em pelo menos algumas modalidades, para pacotes TCP de saída do servidor 134, o módulo de balanceador de carga 132 primeiro confere seu estado interno para determinar se o pacote é para uma conexão ativa que o módulo de ba- lanceador de carga está gerenciando. Se não for, o módulo de balanceador de carga 132 apenas passa o pacote através. Se for, o módulo de balanceador de carga 132 encapsula o pacote TCP de saída, por exemplo de acordo com o UDP, e encaminha o pacote encapsulado para um nó do balanceador de carga 110 que foi selecionado como o servidor de egresso 114 para esta conexão. Em pelo menos algumas modalidades, o módulo de balanceador de carga 134 pode ajustar o número de sequência TCP no pacote TCP de saída por um delta constante, de modo que fique alinhado com o número de sequência gerado pelos nós de rastreador de fluxo 116 que enviaram o pacote SYN/ACK para o cliente 160.

Rastreamento de conexão

[0137] Em pelo menos algumas modalidades, o módulo do balanceador de carga 132 em cada nó do servidor 130 gerencia uma tabela hash contendo detalhes de conexão para cada conexão de cliente ativa para o respectivo servidor 134. Em pelo menos algumas modalidades, a chave para a tabela hash é a tupla (clien- tIp:port, publicIp:port). Em pelo menos algumas modalidades, o estado da conexão para cada conexão de cliente pode incluir um ou mais de, mas não limitado a: • O IP do cliente: Porta • O IP público: Porta • O número de sequência TCP do servidor inicial fornecido pelo rastrea- dor de fluxo dos nós 116. • O número delta da sequência TCP do servidor. • O endereço IP original do rastreador de fluxo primário. • O endereço IP original do rastreador de fluxo secundário. • O endereço IP do último servidor de ingresso 112 detectado. • Um tempo de expiração para esta entrada • Índices de LRU (least recent used)/Colisão

[0138] Em pelo menos algumas modalidades, cada módulo de balanceador de carga 132 gera periodicamente mensagens de disponibilização de conexão para os nós de rastreador de fluxo primário e secundário para todas as conexões de clientes ativos. Em pelo menos algumas modalidades, o conteúdo de /proc/net/tcp é digitalizado e cruzado com as conexões ativas em tabela hash do módulo balanceador de carga de modo que irão continuar a ser disponibilizadas para os nós de rastrea- dor de fluxo até que o kernel do Linux deixe de rastrear a conexão. Disponibilização de conexão será discutida com mais detalhes adiante neste documento.

Desconfiguração de número sequencial

[0139] Como descrito anteriormente, em pelo menos algumas modalidades os nós de balanceador de carga 110 geram pacotes SYN/ACK em resposta aos pacotes SYN do cliente 160 em nome do servidor 134. Somente após o cliente 160 enviar um pacote ACK (o handshake de três vias TCP) o módulo de balanceador de carga 110 envia qualquer dado para um módulo de balanceador de carga 132 em um nó de servidor 130. Quando o módulo de balanceador de carga 132 é instruído primeiramente a estabelecer uma conexão de cliente, o módulo de balanceador de carga 132 fabrica localmente um pacote SYN para iniciar uma conexão TCP com o servidor 134 no nó do servidor 130, e intercepta o pacote SYN/ACK do servidor 134. Normalmente, o servidor 134 (por exemplo, o kernel do Linux no nó do servidor 130) seleciona um número de sequência TCP totalmente diferente do que o que o cliente recebeu no pacote SYN/ACK dos nós de balanceador de carga 110. Assim, em pelo menos algumas modalidades, o módulo de balanceador de carga 132 pode corrigir os números de sequência de todos os pacotes na conexão TCP entre o cliente 160 e o servidor 134. Em pelo menos algumas modalidades, o módulo de balanceador de carga 132 calcula a diferença entre o número de sequência gerado pelos nós de ba- lanceador de carga 110 e o número de sequência gerado pelo servidor 134 e armazena a diferença como um valor delta na entrada da tabela hash para a conexão TCP. Quando os pacotes de dados recebidos chegam do cliente 160 na conexão, o cabeçalho TCP conterá números de confirmação de que não irão se alinhar com o número de sequência usado pelo servidor 134, de modo que o módulo de balancea- dor de carga 132 subtrai o valor delta (por exemplo, utilizando um complemento de dois) do valor de número de sequência no cabeçalho TCP. O módulo de balancea- dor de carga também adiciona o valor delta para o número de sequência em pacotes de saída a partir do servidor 134 para o cliente 130 na conexão.

Verificação de integridade no sistema de balanceador de carga distribuída

[0140] Em pelo menos algumas modalidades do sistema de balanceador de carga distribuída, cada nó do balanceador de carga 110 requer uma visão consistente dos elementos íntegros na implementação de balanceador de carga (ou seja, dos nós do balanceador de carga íntegros 110 e nós do servidor 130) para, pelo menos, as seguintes razões: • Balanceamento de carga - Os nós do balanceador de carga 110 precisam detectar falhas no nó do servidor 130 e convertê-las em um conjunto de nós de servidor 130 íntegro que possa aceitar o tráfego do cliente. • Gerenciamento de estado distribuído - O balanceador de carga é um sistema distribuído com o estado compartilhado/replicado em múltiplos nós de ba- lanceador de carga 110 (por exemplo, de acordo com um mecanismo de hashing consistente). A fim de tratar adequadamente o tráfego de cliente, cada nó do balan- ceador de carga 110 necessita ter eventualmente uma visão consistente dos nós do elemento íntegro 110 na implementação do balanceador de carga.

[0141] Para alcançar este objetivo, em pelo menos algumas modalidades do sistema de balanceamento de carga distribuída podem implementar modalidades de um protocolo de verificação de integridade que monitora os nós na implementação do balanceador de carga e detecta os nós não íntegros tão rapidamente quanto possível. O protocolo de verificação de integridade pode propagar informações de integridade entre os nós na implementação de balanceador de carga, e pode fornecer métodos que permitem que os nós se convertam em um conjunto de nós íntegros. Além disso, o protocolo de verificação de integridade pode fornecer mecanismos para relatar nós íntegros/não íntegros e mudanças de estado na implementação do balanceador de carga.

[0142] Em pelo menos algumas modalidades, o protocolo de verificação de integridade pode ser baseado em um ou mais de, mas não limitado a, os seguintes pressupostos: • Todos os nós na implementação do balanceador de carga são conhecidos. (ou seja, o protocolo de verificação de integridade não pode executar a descoberta). • Todas as falhas de nó são falhas com paragem segura (fail-stop). • Todas as mensagens entre os nós são mensagens de protocolo sem monitorização de estado (por exemplo, UDP), e as mensagens podem ser descartadas, atrasadas, duplicadas ou corrompidas. Não existem garantias sobre a entrega de mensagens.

[0143] Em algumas modalidades, pelo menos, um nó em uma implementação do balanceador de carga (por exemplo, um nó do balanceador de carga 110 ou os nós de servidor 130) pode ser considerado íntegro sob as seguintes condições: • Todos os componentes internos do nó estão em estado pronto (pronto para lidar com o tráfego de cliente). • Links de rede de entrada/saída do nó são íntegros (para pelo menos os controladores de interface de rede (NICs) em que os tráfegos de cliente fluem).

[0144] A Figura 12 é um fluxograma de alto nível de um método de verificação de integridade que pode ser realizado por cada nó do balanceador de carga de acordo com um intervalo de verificação de integridade de acordo com pelo menos algumas modalidades. Como indicado em 1000, a cada intervalo de balanceador de carga, por exemplo, a cada 100 milissegundos, cada nó do balanceador de carga (BC) 110 pode realizar a verificação de integridade de pelo menos outro nó de BC 110 e de pelo menos um nó do servidor 130. Como indicado em 1002, o nó do ba- lanceador de carga 110 pode atualizar suas informações de saúde armazenadas localmente de acordo com as verificações de integridade. Como indicado em 1004, o nó do balanceador de carga 110 pode então selecionar aleatoriamente pelo menos um outro nó do balanceador de carga 110 e enviar suas informações de saúde para o nó do balanceador de carga selecionados 110. Em pelo menos algumas modali- dades, o nó 110 pode também enviar uma lista de nós do balanceador de carga íntegros 110 para um ou mais nós de servidor 130, por exemplo, para os mesmos nós de servidor 130 que têm sua integridade verificada pelo nó 110. Os elementos da Figura 12 são explicados mais detalhadamente na discussão a seguir.

[0145] Em pelo menos algumas modalidades do protocolo de verificação de integridade, um nó do balanceador de carga 110 não afirma sua própria integridade para os outros nós do balanceador de carga 110. Em vez disso, um ou vários outros nós de balanceador de carga 110 podem verificar a integridade do nó 110. Por exemplo, em pelo menos algumas modalidades, cada nó do balanceador de carga 110 pode periodicamente ou não periodicamente selecionar aleatoriamente um ou mais outros nós 110 para verificação de integridade. Como outro exemplo, em pelo menos algumas modalidades, um ou mais outros nós de balanceador de carga 110, por exemplo os dois vizinhos mais próximos de um determinado nó do balanceador de carga 110 sobre uma lista ordenada de nós 110, como um anel hash consistente, podem, cada um, periodicamente ou não periodicamente verificar a integridade de um determinado nó 110. Em pelo menos algumas modalidades, um nó de verificação de integridade 110 pode incluir o uso de pings de integridade enviados aos NICs 1114 no nó 110 como ilustrado na Figura 23. Em pelo menos algumas modalidades, se um primeiro nó 110 determina que um segundo nó 110 é íntegro por meio de uma verificação de integridade, o primeiro nó 110 pode atualizar (por exemplo, aumentar) o contador de pulsação para o segundo nó 110 armazenado na informação local de integridade para os nós de balanceador de carga 110. O primeiro nó 110 envia periodicamente ou não periodicamente suas informações de integridade local a um ou mais outros nós de balanceador de carga 110 na implementação de balanceador de carga, que podem atualizar suas próprias informações de integridade local em conformidade (por exemplo, incrementando o contador de pulsação para o segundo nó) e enviar suas informações atualizadas de integridade local a um ou mais outros nós 110. As informações de pulsação para o segundo nó 110 podem assim ser propagadas para os outros nós 110 na implementação do balanceador de carga. Desde que o segundo nó 110 seja saudável, todos os outros nós 110 que estão acessíveis a partir do segundo nó 110 devem, assim, ver que o contador de pulsação do segundo nó 110 é aumentado de uma forma consistente, por exemplo, uma vez por segundo ou uma vez a cada dez segundos. Se o segundo nó 110 é detectado como não íntegro pelos nós 110 que verificam sua integridade, não é enviada pulsação para o nó 110 pelos nós de verificação de integridade 110 e, após algum limite de tempo, os outros nós 110 na implementação de balanceador de carga 110 consideram o nó 110 em questão como sendo não íntegro ou cortado.

[0146] Em pelo menos algumas modalidades, um nó do balanceador de carga 110 pode verificar um ou mais aspectos de seu próprio estado interno e, se o nó 110 detecta que não é íntegro por algum motivo, o nó 110 pode parar de responder aos pings de integridade de outros nodos 110 que verificam sua integridade. Assim, os nós 110 que verificam a integridade do nó não íntegro 110 podem considerar o nó 110 como não íntegro, e podem não propagar aumentos de pulsação em nome do nó 110.

Detalhes do protocolo de verificação de integridade

[0147] Em pelo menos algumas modalidades, o protocolo de verificação de integridade pode aproveitar uma técnica de contador de pulsação e comunicar tecnologia de protocolo. O protocolo de verificação de integridade pode ser considerado como tendo duas partes principais - a verificação de integridade e detecção de co- municação/falha.

[0148] Verificação de integridade - Cada nó do balanceador de carga 110 na implementação de balanceador de carga pode periodicamente ou não periodicamente avaliar a integridade de um ou mias nós 110 na implementação. Métodos pelos quais o um ou outros nós são determinados são discutidos mais adiante. A idéia central de verificação de integridade é que se um nó 110 verifica a integridade de outro nó 110 e determina que o outro nó 110 é íntegro, o nó de verificação 110 afirma que o outro nó 110 é íntegro pelo aumento e propagação de um contador de pulsação para o outro nó 110. Em outras palavras, os nós 110 não afirmam a sua própria integridade para outros nós; em vez disso, um ou mais outros nós 110 verificam e afirmam a integridade de cada nó 110 na implementação do balanceador de carga.

[0149] Detecção de comunicação/falha - Em pelo menos algumas modalidades, o protocolo de verificação de integridade pode aproveitar um protocolo de comunicação para propagar informação de integridade do nó do balanceador de carga 110 entre os nós de balanceador de carga 110 na implementação do balanceador de carga. O protocolo de comunicações converge rapidamente, e fornece eventuais garantias de consistência que são suficientes para efeitos do sistema de balanceamento de carga distribuída. Em pelo menos algumas modalidades, utilizando o protocolo de comunicação, cada nó do balanceador de carga 110 mantem contadores de pulsação para cada outro nó 110 na implementação de balanceador de carga, por exemplo em uma lista de pulsação. Cada nó do balanceador de carga 110 executa periodicamente ou não periodicamente uma verificação de saúde de pelo menos um outro nó do balanceador de carga 110 como descrito acima, e aumenta o contador de pulsação para um nó 110 sob determinação por meio da verificação de integridade de que o nó que passou por verificação 110 é íntegro. Em pelo menos algumas modalidades, cada nó do balanceador de carga 110, seleciona aleatoriamente periodicamente ou não periodicamente pelo menos um outro nó 110 na implementação do balanceador de carga à qual transmite a sua atual lista de pulsação. Após o recebimento de uma lista de pulsação de outro nó 110, um nó do balancea- dor de carga 110 mescla as informações de pulsação na lista recebida com sua própria lista de pulsações, determinando o contador máximo de pulsação para cada nó 110 nas duas listas (as listas recebidas e sua própria lista) e usando a determinado contador máximo de pulsação em sua própria lista de pulsação. Por sua vez, esta lista de pulsação é enviada para outro nó selecionado aleatoriamente 110, que atualiza sua própria lista de pulsação em conformidade, e assim por diante. Usando esta técnica, a informação de pulsação para cada nó íntegro 110 é eventualmente (por exemplo, em poucos segundos) propagada para todos os outros nós de balanceador de carga 110 na implementação de balanceador de carga. Enquanto o contador de pulsação continua a aumentar para um determinado nó do balanceador de carga 110, ele é considerado como íntegro pelos outros nós 110. Se um contador de pul- sador de nó do balanceador de carga 110 não é aumentado por um período determinado pela verificação de integridade e método de comunicação, então outros nós do balanceador de carga 110 podem convergir no nó do balanceador de carga 110 sendo considerado não integro.

Nós de balanceador de carga verificadores de integridade

[0150] O que se segue descreve um método para a verificação de um nó do balanceador de carga 110 que pode ser realizado por um outro nó do balanceador de carga 110 de acordo com pelo menos algumas modalidades. Com referência à Figura 23, em algumas modalidades, pelo menos, um nó do balanceador de carga 110 pode ser considerado íntegro se uma ou mais das seguintes condições são determinadas para o nó 110: • As threads do processador (por exemplo, threads do código de processamento de pacote 1108) do nó 110 estão em estado pronto (interno). • O nó 110 sabe o endereço IP do roteador de borda 104 e/ou o endereço MAC (interno). • Todos as threads e/ou manipuladores de protocolo do nó 110 estão em estado pronto (interno). • Os links de entrada e saída do lado norte (roteador de borda 104/rede de borda) e do lado sul (servidores 130/rede de produção) estão ativos (externo). • O nó 110 pode receber e expedir pacotes por meio dos controladores de interface de rede (NICs) utilizados na implemetação do balanceador de carga. Por exemplo, em um exemplo de modalidade de nó do balanceador de carga 110 conforme mostrado na Figura 23, o nó 110 deve receber e expedir os pacotes com sucesso por meio do NIC 1114A virado para o norte e do NIC 1114B virado para o sul.

[0151] Se uma ou mais destas condições de integridade não aguentam em um determinado nó 110, o nó 110 pode ser considerado não íntegro. Deve ser notado que, em algumas modalidades, um nó 110 só é considerado íntegro se todas as condições acima referidas puderem ser realizadas para o nó 110.

[0152] Em pelo menos algumas modalidades, adicionalmente às condições de integridade acima, um terceiro NIC, mostrado na Figura 23 como NIC 1114C, em cada nó do balanceador de carga 110 que pode, por exemplo, ser utilizado para comunicações de plano de controle pode também ser verificado por um nó 110 por meio do envio de pacotes de e para o recebimento de pacotes do NIC e, se a verificação do terceiro NIC falhar, o nó 110 a ser verificado pode ser considerado não íntegro.

[0153] A Figura 13 ilustra um método de exemplo para verificação de integridade de um nó do balanceador de carga de outro nó do balanceador de carga, de acordo com pelo menos algumas modalidades. Neste exemplo, o nó do balanceador de carga 110A é o nó do balanceador de carga verificador de integridade 110B. Cada nó 110A e 110B tem um NIC voltado para o norte (NIC 1114A na Figura 23) e um NIC voltado para o sul (NIC 1114B na Figura 23). Em 1, o nó 110A envia um pacote (por exemplo, um pacote ping) a partir de seu NIC voltado para o norte até o NIC voltado para o norte 110B por meio do roteador de borda 104. Nó 110B recebe o pacote em seu NIC voltado para o norte, e em 2 envia uma resposta do seu NIC voltado para o norte até o NIC voltado para o norte do nó 110A por meio da malha 120, desde que as condições indicadas na lista acima estejam corretas. Após receber a resposta sobre em seu NIC voltado para o norte, em 3, o nó 110A envia um pacote (por exemplo, um pacote ping) a partir do seu NIC voltado para o sul até o NIC voltado para o sul do nó 110B por meio da malha 120. Nó 110B recebe o pacote em em seu NIC voltado para o sul, e em 4 manda uma resposta a partir de seu NIC voltado para o sul até o NIC voltado para o sul do nó 110A por meio do roteador de borda 104, desde que as condições indicadas na lista acima estejam corretas. Ao receber a resposta no seu NIC voltado para o sul, o nó 110A considera que o nó 110B é saudável e aumenta o contador de pulsação local do nó 110B, que pode então ser propagado para outros nós 110 de acordo com um protocolo de comunicação, como previamente descrito.

[0154] Como uma alternativa para o acima exposto, em algumas modalidades, o nó do balanceador de carga 110B pode responder à primeira mensagem de ping, recebida em seu NIC voltado para o norte, através do seu NIC voltado para o sul para o NIC voltado para o sul do nó 110A, e responde à segunda mensagem de ping, recebida em seu NIC voltado para o sul, através do seu NIC voltado para o norte para o NIC voltado para o norte do nó 110A.

[0155] Além disso, em algumas modalidades, o nó 110A também realizar a verificação de integridade de um terceiro NIC do nó 110B que é usado para controlar comunicações de plano (mostradas como NIC 1114C na Figura 23) pelo nó de ping do terceiro NIC de 110B de seu próprio terceiro NIC e receber uma resposta à mensagem de ping em seu terceiro NIC do nó do terceiro NIC de 110B se o nó de 110B estiver íntegro. A mensagem de ping e a resposta podem passar por um ou mais dispositivos de plano de controle 170, por exemplo, um comutador de rede.

[0156] O mecanismo de verificação geral descrito acima exerce todas as ligações de entrada e saída e caminhos de dados do nó 110B em todas as direções (norte, sul, e através do plano de controle), bem como todos os NICs do nó de 110B, e também verifica a integridade interna do nó 110B enquanto os pacotes de pink atravessam as filas internas e faz a expedição do nó 110B, como faria um pacote de cliente.

Atribuição das responsabilidades da verificação de integridade para os nós do balanceador de carga

[0157] Em pelo menos algumas modalidades, cada nó do balanceador de carga 110 em uma implementação do balanceador de carga tem acesso a uma lista (uma lista classificada) de todos os outros nós balanceador de carga 110 na implementação do balanceador de carga, por exemplo, através de uma função de configuração e/ou de um componente de serviço de configuração 122, como mostrado na Figura 1. Em pelo menos algumas formas modalidades, cada nó do balanceador de carga 110 pode selecionar, aleatoriamente, um ou mais dentre outros nós 110 na lista para realizar verificação de integridade a cada intervalo de verificação de integridade, incrementando seu contador de pulsação se for determinado como íntegro. Note-se que a lista inclui todos os nós do balanceador de carga 110 na implementação do balanceador de carga, se considerando íntegro ou não-íntegro, através do mecanismo de verificação de integridade, e os nós momentaneamente não-íntegros 110 podem ser selecionados aleatoriamente a partir da lista e verificados quanto à integridade, bem como os nós íntegros 110. Assim, um nó momentaneamente não- íntegro 110 pode ser determinado como sendo íntegro por um ou mais nós 110 que verificam a integridade do nó 110, seu contador de pulsações pode ser incrementado e propagado a outros nós 110 e o nó não-íntegro 110 pode então retornar à con-dição íntegra.

[0158] Alternativamente, em algumas modalidades, cada nó 110 do balance- ador de carga pode assumir a responsabilidade de verificar a integridade de um ou mais dentre outros nós 110 na lista e incrementar seu contador de pulsações, se determinados como íntegros. Por exemplo, em algumas modalidades, cada nó 110 pode assumir responsabilidade por outros dois nós, por exemplo, seu nó 110 vizinho mais próximo "esquerdo" (ou anterior) ou "direito" (ou seguinte) na lista. Note que a lista pode ser considerada circular e um nó 110 ao "fim" da lista pode assumir a responsabilidade pela verificação de integridade de um nó 110 no "início" da lista, e vice-versa. Em algumas modalidades, os dois outros nós 110 podem ser selecionados de outro modo, por exemplo, como os dois vizinhos mais próximos a seguir na lista. Em algumas modalidades, cada nó 110 pode assumir responsabilidade pela verificação de integridade de mais do que dois outros nós 110 na lista, por exemplo, mais três ou quatro nós 110. Em pelo menos algumas modalidades, se um nó vizinho 110 que está sendo verificado por um nó 110 é determinado como não-íntegro, então o nó 110 pode assumir responsabilidade pela verificação de saúde de pelo menos um nó na lista que o nó vizinho não-íntegro 110 era responsável por verificar. Em pelo menos algumas modalidades, além da verificação de integridade de seus nós 110 vizinhos (por exemplo, um nó vizinho "esquerdo" e "direito"), cada nó 110 do balan- ceador de carga pode também, periodicamente ou aperiodicamente, selecionar de maneira aleatória um nó 110 no anel e realizar uma verificação de integridade daquele nó 110 selecionado aleatoriamente e, se for íntegro, incrementar e propagar as pulsações do nó 110 aleatório. Em pelo menos algumas modalidades, todos os outros nós 110 na lista ordenada são levados em conta para a seleção aleatória e verificados quanto à integridade, independentemente de o outro nó 110 ter sido anteriormente considerado íntegro ou não.

[0159] Em pelo menos algumas modalidades, cada nó 110 executa a verificação de integridade de um ou mais nós 110 selecionados aleatoriamente, ou alternativamente de seus nós vizinhos 110 e um nó selecionado aleatoriamente, a um intervalo regular, que pode ser referido aqui como o intervalo de verificação de integridade. Por exemplo, em algumas modalidades, o intervalo de pulsações pode ser de 100 milissegundos, embora intervalos mais breves ou mais longos possam ser usa- dos. Além disso, em pelo menos algumas modalidades, cada nó 110 envia ou "comunica" sua lista de pulsações atual para pelo menos um outro nó 110 selecionado aleatoriamente a um intervalo regular, que pode ser referido como intervalo de comunicação. Em algumas modalidades, o intervalo de verificação de integridade e o intervalo de comunicação podem ser os mesmos, embora eles não sejam necessariamente os mesmos.

[0160] A Figura 14 ilustra graficamente um nó do balanceador de carga verificando a integridade de um ou mais nós do balanceador de carga, de acordo com pelo menos algumas modalidades. Neste exemplo, há oito nós do balanceador de carga 110A - 110H na implementação do balanceador de carga. O círculo tracejado representa uma lista ordenada de todos os nós 110 na implementação. Em algumas modalidades, cada nó 110 pode selecionar aleatoriamente um ou mais outros nós 110 na lista de verificação de integridade em cada intervalo. Como alternativa, em algumas modalidades, cada nó 110 do balanceador de carga pode assumir a responsabilidade de verificar um ou mais nós 110 específicos na lista ordenada, por exemplo, o nó 110A pode assumir a responsabilidade pela verificação de integridade de seus dois nós 110B e 110H vizinhos mais próximos, de acordo com a lista orde-nada mostrada na Figura 14. Ademais, o nó do balanceador de carga pode ainda selecionar aleatoriamente outro nó 110 da lista ordenada a cada intervalo de verificação de integridade. Como mostrado neste exemplo, o nó 110A também selecionou aleatoriamente o nó 110F para verificação de integridade. No intervalo de comunicação, o nó 110A seleciona aleatoriamente outro nó 110 íntegro, por exemplo, o nó 110D, e envia sua lista de pulsações atual para o outro nó 110 selecionado, por exemplo, em uma mensagem UDP. Um nó 110, ao receber uma lista de pulsações de outro nó 110, pode atualizar sua própria lista de pulsações apropriadamente e propagar a lista de pulsações a um ou mais nós 110 selecionados aleatoriamente no próximo intervalo de comunicação.

Verificação de integridade dos nós do servidor

[0161] Além de verificar a integridade dos nós 110 do balanceador de carga, como descrito acima, as modalidades do protocolo de verificação de integridade podem realizar a verificação de integridade dos nós do servidor 130, incluindo os módulos do balanceador de carga 132 e os servidores 134 nesses nós 130. Em pelo menos algumas modalidades, um nó do servidor 130 pode ser considerado íntegro, se um ou mais das seguintes condições forem determinadas para o nó 130: • O módulo do balanceador de carga 132 é íntegro. • O nó do servidor 130 responde com êxito aos pings íntegros (por exemplo, pings íntegros L7).

[0162] A Figura 15 ilustra os nós do balanceador de carga verificando a integridade dos nós de servidor, de acordo com pelo menos algumas modalidades. Em pelo menos algumas modalidades, cada nó do balanceador de carga 110 em uma implementação do balanceador de carga tem acesso a uma lista de todos os outros nós do balanceador de carga 110 na implementação do balanceador de carga, bem como uma lista de todos os nós do servidor 130 na implementação do balanceador de carga. A(s) lista(s) pode(m) ser obtida(s) e atualizada(s), por exemplo, através de uma função de configuração e/ou através de um componente de serviço de configuração 122, como mostrado na Figura 1. Em pelo menos algumas modalidades, os nós do servidor 130 podem ser formas de realização, o servidor 130 pode ser submetido a hash consistente de encontro aos nós do balanceador de carga íntegros 110 para formar um anel de hash consistente, como ilustrado na Figura 15. Em pelo menos algumas modalidades, cara nó do servidor 130 no anel é verificado quanto à integridade por dois nós do balanceador de carga íntegros 110 no anel. Por exemplo, na Figura 15, o nó do servidor 130A é verificado quanto à integridade pelos nós do balanceador de carga 110A e 110C. Esses dois nós 110 podem ser referidos como o primeiro (nó 110A) e segundo (110B nó) nó de verificação de integridade 110 para o nó do servidor 130 no anel de hash consistente. Note-se que um determinado nó do balanceador de carga íntegro 110 pode verificar a integridade de mais de um nó do servidor 130. Por exemplo, na Figura 15, o nó do balanceador de carga 110A também verifica a integridade dos nós do servidor 130B e 130C. Além disso, um determinado nó do balanceador 110 pode ser um primeiro nó de verificação de integridade 110 para um ou mais nós do servidor 130 e um segundo nó de verificação de integridade 110 para um ou mais nós do servidor 130. Por exemplo, na Figura 15, o nó do balanceador de carga 110A é o primeiro nó de verificação de integridade para os nós do servidor 130A e 130B e o segundo nó de verificação de integridade para os nós do servidor 130C e 130D.

[0163] Em pelo menos algumas modalidades, se um nó do balanceador de carga 110 falhar, o pertencimento às mudanças do anel de hash consistente e um ou mais dos outros nós do balanceador de carga 110 que ainda são íntegros e, assim, ainda no anel de hash consistente podem assumir a responsabilidade pela verificação de integridade dos nós do servidor 130 verificados anteriormente quanto à integridade pelo nó 110 que falhou.

[0164] Em pelo menos algumas modalidades, cada nó íntegro 110 realiza a verificação de integridade de seus nós atribuídos do servidor 130 a um intervalo regular, o que pode ser referido como um intervalo de verificação do servidor. Em pelo menos algumas modalidades, o intervalo de verificação do servidor pode ser superior ou igual ao intervalo de comunicação mencionado anteriormente.

[0165] Em pelo menos algumas modalidades, para realizar uma verificação de integridade de um nó do servidor 130, um nó do balanceador de carga íntegro 110 (por exemplo, o nó 110A na Figura 15) envia uma mensagem de ping íntegro (por exemplo, uma mensagem de ping íntegro em HTTP L7) para um nó do servidor 130 (por exemplo, o nó do servidor 130A na Figura 15). Se for saudável, o nó do servidor 130 envia uma resposta de ping de volta ao nó do balanceador de carga 110. Em pelo menos algumas modalidades, a mensagem de ping é recebida e processada pelo módulo do balanceador de carga 132 no nó do servidor 130, assim, o ping de verificação de integridade, se bem-sucedido, estabelece que o módulo 132 no nó do servidor 130 é íntegro. Após receber a resposta ao ping, o nó do balanceador de carga 110 considera o nó do servidor 130 como íntegro e incrementa o contador de pulsações para o nó do servidor 130.

[0166] Em pelo menos algumas modalidades, os contadores de pulsações para todos os nós do servidor 130 verificados quanto à integridade por um determinado nó do balanceador de carga íntegro 110 pode ser propagado aos outros nós do ba- lanceador de cargo 110, por exemplo, de acordo com a técnica de comunicação descrita anteriormente para os contadores de pulsações do nó do balanceador de carga 110 em que o nó 110 envia sua lista de pulsações para pelo menos um outro nó 110 selecionado aleatoriamente a um intervalo regular (o intervalo de comunicação), e o nó de recebimento 110 atualiza sua própria lista de pulsações de acordo com os valores máximos nessas duas listas.

Detecção de falhas e comunicação

[0167] Em pelo menos algumas modalidades, as informações obtidas através da verificação de integridade do nó do balanceador de carga 110 e das verificações de integridade do nó do servidor 130 descritos acima podem precisar ser propagadas a todos os nós 110 na implementação do balanceador de carga, de modo que todos os nós do balanceador de carga 110 possam manter uma vista consistente da implementação do balanceador de carga. Como descrito acima, em pelo menos em algumas modalidades, os nós do balanceador de carga 110 podem se comunicar uns com os outros de acordo com um protocolo de comunicação para trocar e propagar essas informações de integridade e detectar falhas no nó do balanceador de carga 110 e no nó do servidor 130.

[0168] Em pelo menos algumas modalidades, em um intervalo regular (referi- do como o intervalo de comunicação), cada nó do balanceador de carga de 110 se-leciona aleatoriamente outro nó do balanceador de carga 110 e envia ao outro nó 110 sua vista dos nós do balanceador de carga íntegro 110 e os nós do servidor 130 juntamente com os contadores de pulsações para os nós do balanceador de carga 110 e os nós do servidor 130. Contanto que um nó do balanceador de carga ou nó do servidor 130 sejam íntegros, o nó passará por sua verificação de integridade e seu contador de pulsações continuará aumentando. Se o contador de pulsações para um nó não mudar para um intervalo especificado (que pode ser denominado um intervalo de tempo de falha), então suspeita-se que o nó falhou quanto aos nós do balanceador de carga 110. Uma vez que há suspeita de um nó ter falhado, os nós do balanceador de carga 110 podem esperar por um intervalo especificado (que pode ser denominado intervalo de tempo não-íntegro) antes de determinar que o nó é não-íntegro. Este intervalo de tempo não-íntegro permite que os nós do balanceador de carga 110 esperem até que os nós do balanceador de carga 110 saibam que o nó falhou.

[0169] A Figura 16 ilustra graficamente um estado, ou uma vista, da integridade de outro nó (o nó do balanceador de carga 110 ou o nó do servidor 130) que pode ser mantido por um nó do balanceador de carga 110, de acordo com pelo menos algumas modalidades. Suponha que o nó do balanceador de carga 110 inicie com uma vista do nó em questão como sendo íntegro, como indicado em 300. Isso indica que o contador de pulsações para o nó foi incrementando. No entanto, se o contador de pulsações não aumentar para um determinado intervalo especificado (o intervalo de tempo de falha), como indicado em 302, então o nó do balanceador de carga 110 suspeita que o nó tenha falhado, como indicado em 304. Se o contador de pulsações do nó não aumentar para um intervalo especificado (o intervalo de tempo não- íntegro), como indicado em 206, então o nó do balanceador de carga 110 considera o nó não-íntegro, como indicado em 308. No entanto, se o contador de pulsações para os incrementos do nó antes de o intervalo de tempo não-íntegro expirar como indicado em 310, o nó do balanceador de carga 110 novamente considera o nó como íntegro 300. Do mesmo modo, o recebimento de um incremento de pulsações para um nó não-íntegro como indicado em 312 pode fazer com que o nó seja considerado íntegro 300.

[0170] A determinação de que um nó é não-íntegro pode envolver diferentes ações por parte dos nós do balanceador de carga 110, dependendo de se o nó não- íntegro é um nó do balanceador de carga 110 ou um nó do servidor 130, e também dependendo da relação do nó 110 do balanceador de carga com o nó não-íntegro, como descrito em algum outro momento neste documento.

Dados do nó do balanceador de carga

[0171] Em pelo menos algumas modalidades, cada nó do balanceador de carga 110 pode manter os dados sobre o estado da implementação do balanceador de carga. Em pelo menos algumas modalidades, estes dados podem ser mantidos ema um ou mais estruturas de dados em cada nó do balanceador de carga 110 incluindo, sem se limitar a, uma lista do nó do balanceador de carga, uma lista do nó de balanceador de carga suspeita e uma lista de pulsações. A Figura 17 ilustra um nó do balanceador de carga exemplificativo 110 que mantém uma lista do nó do ba- lanceador de carga 320, uma lista dos nós do balanceador de carga suspeito 322, uma lista dos nós do balanceador de carga não-íntegros 324 e uma lista de pulsações do nó do balanceador de carga 326.

[0172] Em pelo menos algumas modalidades, cada nó do balanceador de carga 110 pode manter uma lista de nós do balanceador de carga 320, que é uma lista dos nós do balanceador de carga íntegros 110 que podem ser usados, por exemplo, para determinais quais nós 110 são íntegros e, portanto, estão participando do protocolo de comunicação. Apenas os nós 110 na lista 320 estão envolvidos na propagação de informações do balanceador de carga através do protocolo de comunicação, apenas os nós 110 na lista 320 são considerados como parte do anel de hash consistente e apenas os nós 110 nesses nós do servidor de verificação de integridade da lista 130. Um nó 110 pode selecionar aleatoriamente outro nó 110 dessa lista 320 para o qual suas informações de pulsações são enviadas. Além disso, os contadores de pulsações são trocados apenas para os nós 110 que estão na lista dos nós do balanceador de carga íntegros 320 no momento. Em algumas modalidades, um nó do balanceador de carga N pode ser adicionado à lista dos nós do balanceador de carga íntegros 320 de outro nó do balanceador de carga 110 se o nó N passar por uma verificação de integridade quanto ao nó do balanceador de carga 110 ou se o nó do balanceador de carga 110 receber uma mensagem de comunicação sobre o nó N de algum outro nó do balanceador de carga 110 na lista 320.

[0173] Em pelo menos algumas modalidades, cada nó do balanceador de carga 110 pode manter uma lista dos nós do balanceador de carga suspeitos 322, que é uma lista dos nós do balanceador de carga cujo contador de pulsações (ver a lista de pulsações 326) não aumentou para um intervalo especificado (denominado intervalo do tempo de falha). Se um nó do balanceador de carga E estiver na lista de nós do balanceador de carga suspeitos 322 de um nó do balanceador de carga 110, então o nó do balanceador de carga 110 não comunicação quanto ao nó E. Se algum outro nó do balanceador de carga 110 na lista dos íntegros 320 comunicar o nó do balanceador de carga 110 sobre o nó E com um contador de pulsações mais elevado do que o contador do nó E na lista de pulsações 326 do nó 110, então o nó E será movido da lista de suspeitos 322 para lista de íntegros 320. Se o nó E permanecer na lista de suspeitos 322 do nó do balanceador de carga 110 por um intervalo especificado (referido como um intervalo de tempo não-íntegro), o nó E é considerado não-íntegro pelo nó do balanceador de carga 110 e é movido para uma lista do nó não-íntegro 324. Um nó 110 na lista de nós íntegros 324 (neste exemplo, o nó G) pode ser movimento para a lista de nós íntegros 320 de um nó do balanceador de carga 110 a partir do momento em que o nó G passa por uma verificação de integridade no nó 110 ou a partir do recebimento de um contador de pulsações atualizado para o nó G de outro nó 110.

[0174] Em pelo menos algumas modalidades, cada nó do balanceador de carga 110 pode manter uma lista de pulsações 326 para os nós do balanceador de carga 110 conhecidos. Para cada nó, 110, esta lista 326 pode incluir um contador de pulsações e um marcador de tempo que indica quando o contador de pulsações alterou pela última vez.

[0175] Em pelo menos algumas modalidades, cada nó do balanceador de carga 110 pode também manter uma lista de pulsações para todos os nós do servidor conhecidos, não mostrado na Figura 17. Esta lista pode ser semelhante à lista de pulsações do nó do balanceador de carga 326. Em algumas modalidades, as duas listas podem ser combinadas. Em pelo menos algumas modalidades, as informações de pulsações para os nós do servidor 130 podem ser propagandas entre os nós do balanceador de carga 110, por exemplo, de acordo com um protocolo de comunicação, juntamente ou em adição às informações de pulsações para os nós do balanceador de carga 110.

[0176] Enquanto a Figura 17 mostra quatro listas separadas, deve-se notar que duas ou mais listas podem ser combinadas em uma única lista. Por exemplo, em algumas modalidades, uma única lista de todos os nós 110 pode ser mantida em cada nó do balanceador de carga 110 e um sinalizador de bit ou outras estruturas de dados podem ser usados para indicar se cada nó é, no momento, suspeito, íntegro ou não-íntegro.

Dados do nó do servidor

[0177] Em pelo menos algumas modalidades, os nós do servidor 130 e os módulos do balanceador de carga locais 132 nos nós 130 não participam do protocolo de comunicação com os nós do balanceador de carga 110. Os nós do balance- ador de carga 110 comunicam as informações de pulsações sobre os outros nós do balanceador de carga 110 obtidos pelo método de verificação de integridade do nó do balanceador de carga e as informações de pulsações sobre os nós do servidor 130 obtidas pelo método de verificação de integridade do nó do servidor apenas entre eles mesmos (de modo específico, cada nó do balanceador de carga 110 comunica apenas aos nós atualmente em sua lista de nós do balanceador de carga íntegros 320).

[0178] No entanto, cada nó do servidor 130 / módulo do balanceador de carga 132 pode precisar de informações sobre os nós do balanceador de carga íntegros 110 na implementação do balanceador de carga, de modo que o nó do servidor 130 possa determinar os nós do balanceador de carga 110 (nós egressos, especificamente) aos quais o nó do servidor 130 pode encaminhar o tráfego de saída do cliente e determinar quais os nós do balanceador de carga aos quais as informações de disponibilização de conexão deve ser enviada. Em pelo menos algumas modalidades, para fornecer essas informações aos nós do servidor 130, os nós do balancea- dor de carga 110 podem, periodicamente ou aperiodicamente, atualizar os nós do servidor 130 com informações identificando os nós do balanceador de carga atualmente íntegros 110 (por exemplo, a lista de nós do balanceador de carga íntegros 320 na Figura 17). Em pelo menos algumas modalidades, os nós do balanceador de carga 110 que são responsáveis pela verificação de integridade de um determinado nó do servidor 130 (ver Figura 15) são responsáveis por fornecer as informações identificando os nós do balanceador de carga atualmente íntegros ao servidor 130. Por exemplo, referindo-se à Figura 15, o nó do balanceador de carga 110A pode enviar sua lista de nós do balanceador de carga íntegros 320 aos nós do servidor 130A, 130B, 130C e 130D, o nó do balanceador de carga 110B pode enviar sua lista de nós do balanceador de carga íntegros 320 aos nós do servidor 130C, 130D e 130E, e assim por diante.

Administração de falhas no nó do balanceador de carga

[0179] As Figuras 18A e 18B ilustram a administração de uma falha no nó do balanceador de carga, de acordo com pelo menos algumas modalidades. A Figura 18A mostra um exemplo de implementação do balanceador de carga. Há quatro nós do balanceador de carga de 110A a 110D atualmente na implementação do balan- ceador de carga. Roteador de borda104 roteia pacotes de entrada de clientes (não mostrados) para os nós de balanceador de carga 110. Em pelo menos algumas modalidades, o roteador de borda 104 pode tomar as decisões de roteamento de acordo com uma técnica de roteamento de caminhos múltiplos hash por fluxo de 4 camadas, por exemplo, uma técnica de roteamento de caminho múltiplo de custo igual (equal-cost multipath, ECMP na sigla em inglês). Em pelo menos algumas modalidades, o roteador de borda 104 é informado sobre os nós do balanceador de carga 110 que estão atualmente disponíveis na implementação do balanceador de carga para receber o tráfego do cliente através de anúncios do nó do balanceador de carga 110, por exemplo, anúncios através da tecnologia de Boarder Gateway Protocol (BGP) iniciados pelos nós do balanceador de carga 110. No entanto, em pelo menos algumas modalidades, em vez de um nó do balanceador de carga 110 anunciando a si mesmo ao roteador de borda 104 através de uma sessão de BGP, pelo menos outro nó 110 na implementação do balanceador de carga assume a responsabilidade pelo anúncio do nó 110 ao roteador de borda 104 através de BGP. Por exemplo, em algumas modalidades, como mostrado na Figura 18A, os nós vizinhos esquerdo e direito 110 de um determinado nó 110 anunciando o determinado nó 110 ao roteador 104. Por exemplo, o nó do balanceador de carga 110A anuncia os nós 110B e 110D, o nó do balanceador de carga 110B anuncia os nós 110A e 110C e o nó do balan- ceador de carga 110C anuncia os nós 110B e 110D.

[0180] Como mostrado no exemplo da Figura 18A, cada nó do balanceador de carga 110 também verifica periodicamente a integridade de um ou mais dos ou- tros nós do balanceador de carga 110, por exemplo, um ou mais nós selecionados aleatoriamente 110, um ou mais nós vizinhos 110, como determinado por uma lista ordenada de nós do balanceador de carga, ou um ou mais nós vizinhos e um ou mais nós aleatoriamente selecionados. Além disso, cada nó do balanceador de carga 110 pode periodicamente verificar a integridade de pelo menos um nó de servidor 130 e também pode enviar sua lista de nós do balanceador de carga íntegros 110 aos nós do servidor que ele verificar quanto à integralidade. As informações de integridade para os nós do balanceador de carga 110 e para os nós do servidor 130 podem ser propagadas entre os nós 110, por exemplo, de acordo com um protocolo de comunicação.

[0181] A Figura 18B ilustra a administração da falha de um único nó do balan- ceador de carga 110 no exemplo de implementação do balanceador de carga da Figura 18A. Neste exemplo, o nó do balanceador de carga 110B falhou por algum motivo. Por exemplo, os nós 110A e 110C podem verificar a integridade do nó 110B e ambos podem detectar que o nó 110B está falhando em suas verificações de integridade. Assim, os nós 110A e 110C não incrementam o contador de pulsações para o nó 110B. As informações de pulsações dos nós 110A e 110B são propagadas aos outros nós do balanceador de carga íntegros 110 (neste exemplo, o único outro nó do balanceador de carga é o nó 110D), de acordo com o protocolo de comunicação. Assim que todos os nós do balanceador de carga íntegros 110 (neste exemplo, os nós 110A, 110C e 110D) convergirem na falha do nó 110B, ou um mais dos eventos a seguir podem ocorrer, sem se limitar a eles. Note-se que estes eventos não ocor-rem necessariamente nesta ordem. • Os nós 110A e 110C param de anunciar o nó 110B ao roteador de borda 104. Em pelo menos algumas modalidades, isso envolve o encerramento da sessão de BGP que o nó 110 estabeleceu com o roteador de borda 104 para anunciar o nó 110B. Note-se que cada nó 110 estabelece uma sessão de BGP separada com o roteador de borda 104 para cada outro nó 110 que ele anuncia, de modo que encerrar a sessão de BGP para o nó 110B não afeta os outros nós 110 que são anunciados. Em pelo menos algumas modalidades, um nó 110 termina uma sessão de BGP com o roteador de borda 104 enviando uma mensagem de TCP fechado ou semelhante para a sessão de BGP ao roteador de borda 104. • Em resposta à detecção de que nó 110B não está mais sendo anunciado por nenhum dos nós, o roteador de borda 104 para de rotear os pacotes de dados do cliente ao nó 110B. O roteador de borda 104 também ajusta a submissão de hash de vias múltiplas (por exemplo, ECMP) para redistribuir os fluxos de pacote dos clientes aos nós do balanceador de carga íntegros restantes 110, especificamente aos servidores ingressos 112 nos nós 110. Para qualquer fluxo de pacote roteado a um servidor de ingresso 112 para o qual o servidor de ingresso 112 não possuir um mapeamento cliente->servidor, o mapeamento pode ser obtido a partir de um nó mapeador de fluxo para a conexão cliente->servidor, de acordo com a técnica ilustrada nas Figuras de 10A a 10G. • Os nós 110A e 110C podem, cada um, abrir uma sessão de BGP para o roteador 104 para anunciar um ao outro. Note-se que, uma vez que ambos os nós 110A e 110C são anunciados ao roteador de borda 104 pelo nó do balanceador de carga 110D, bem como pelo nó 110B, o fato de que nó 110B pode parar de anunciar os nós 110A e 110B ao roteador de borda 104 quando ele falhar não faz com que o roteador de borda 104 pare de rotear pacotes a esses dois nós 110. • Em pelo menos algumas modalidades, os nós 110A e 110C podem assumir responsabilidade pela verificação de integridade um do outro, visto que agora eles são nós vizinhos 110. Note-se que o nó 110B, embora considerado pouco saudável, pode ainda ser verificado aleatoriamente quanto à integridade por um ou mais dos outros nós 110. • Um ou mais dos nós do balanceador de carga íntegros restantes 110 podem assumir a responsabilidade pelo mapeamento de fluxo das conexões anteri-ormente mapeadas por fluxo pelo nó 110B. Por exemplo, o nó 110C e/ou o nó 110D podem assumir como os mapeadores de fluxo primário ou secundário, como ilustrado nas Figuras 11C e 11D, para uma ou mais conexões para as quais o nó 110B foi um mapeador de fluxo primário ou secundário. • Um ou mais dentre os nós do balanceador de carga íntegros 110 pode assumir a responsabilidade pela verificação de integralidade dos nós do servidor 130 anteriormente verificados quanto à integralidade pelo nó 110B. Os nós do servidor 130 são atualizados com a lista de nós do balanceador de carga (agora não incluindo o nó 110B) pelos nós do balanceador de carga restantes 110. Por exemplo, na Figura 18B, o nó do balanceador de carga 110A começa a verificação de integrali- dade e a atualização do nó do servidor 130C e o nó do balanceador de carga 110C começa a verificação de integralidade e a atualização do nó do servidor 130B. • No roteador de borda 104, as sessões de BGP do nó que falhou 110B eventualmente atingem o tempo limite. Em alternativa, o roteador de borda 104 pode encerrar as sessões de BGP ao reconhecer que esse nó 110B falhou.

[0182] É possível que dois nós do balanceador de carga 110 pode falhar no ou quase no mesmo tempo. Se os dois nós do balanceador de carga com falha não forem adjacentes uns aos outros, então as falhas são independentes e podem ser administradas como falhas separadas do nó 110 único, de acordo com o método ilustrado na Figura 18B. No entanto, se os dois nós com falha forem adjacentes um ao outro (por exemplo, os nós 110B e 110C na Figura 18A, então, tão logo todos os nós do balanceador de carga íntegros 110 (neste exemplo, os nós 110A e 110D) detectarem e convergirem para a falha, um ou mais dentre os, mas sem se limitar aos, eventos a seguir podem acontecer. Note-se que estes eventos não ocorrem necessariamente nesta ordem. • Os nós 110A encerra a sessão de BGP para o roteador de borda 104 para o nó 110B. • O nó 110D encerra a sessão de BGP para os roteadores de borda 104 para o nó 110C. • Os nós 110A e 110D iniciam a sessão de BGP com o roteador de borda 104 para anunciar um ao outro. • Os nós 110A e 110D pode iniciar a verificação de integridade um do outro. Note-se que os nós 110A e 110D também podem continuar a verificação de integridade dos nós com falha 110. • Os nós íntegros restantes 110 atualizam os nós do servidor 130 com as listas de nós do balanceador de carga íntegros. • O tráfego pode continuar a fluir a partir do roteador de borda 104 até o nó 110B e/ou nó 110C, já que esses dois nós 110 podem continuar a anunciar um ao outro ao roteador de borda 104. No entanto, essas sessões de BGP atingirão eventualmente o tempo limite e, com efeito, esse roteador de borda 104 redistribuirá os fluxos aos nós anunciados restantes 110. • Os nós 110B e 110C podem encerrar suas sessões de BGP com o roteador de borda 104 em que eles anunciam os nós 110A e 110D, respeitosamente, se os nós 110B e 110C julgarem-se ainda íntegros.

Disponibilização de conexão

[0183] Referindo novamente à Figura 1, em pelo menos algumas modalidades, os nós do balanceador de carga 110 em uma implementação do balanceador de carga mantêm informações de estado para as conexões TCP de cliente aos servidores 130. Essas informações de estado permitem que os nós do balanceador de carga 110 roteiem o tráfego de entrada do cliente a partir do roteador de borda 104 para os nós do servidor 130 responsáveis pelas conexões TCP. Os módulos do ba- lanceador de carga 132 nos nós do servidor 130 mantêm listas das conexões TCP ativas aos seus respectivos servidores 134. A disponibilização de conexão é um me- canismo através do qual os módulos do balanceador de carga 132 nos nós de servidor 130 podem disponibilizar suas listas de conexões de TCP do cliente ativas aos nós do balanceador de carga 110. Em pelo menos algumas modalidades, os pacotes de disponibilização de conexão são formados e publicados aos nós do balance- ador de carga 110 pelos módulos de carga 132 em um intervalo regular, o qual pode ser denominado intervalo de disponibilização de conexão.

[0184] Em pelo menos algumas modalidades, as informações de estado de conexão mantidas pelos nós do balanceador de carga 110 podem ser visualizadas como uma forma de cache e a manutenção das informações do estado para uma conexão particular pode ser visualizada como a manutenção de uma concessão em um nó do balanceador de carga 110 para essa conexão. A menos que as entradas de cache sejam renovadas, os nós do balanceador de carga 110 pode não ser capaz de rotear os fluxos de dados para os nós do servidor 130 que estão administrados os fluxos de dados. O mecanismo de disponibilização de conexão renova periodicamente os caches e, portanto, as concessões, nos nós do balanceador de carga 110 com as informações do estado de conexão atuais a partir dos nós do servidor 130 para manter os pacotes TCP fluindo dos clientes 160 para os nós do servidor apropriados 130. Quando um cliente 160 encerra uma conexão TCP a um servidor 134, o módulo do balanceador de carga 132 no nó do servidor 130 associado àquela conexão eliminará a conexão de sua lista de conexões ativas e, portanto, não disponibilizará mais a conexão TCP através do mecanismo de disponibilização de conexão. Assim, as informações do estado de conexão para essa conexão (a entrada ou entradas de cache) nos nós do balanceador de carga 110 associados àquela conexão (especificamente, o servidor de ingresso 112 e os mapeador de fluxo primário e secundário 116 para a conexão) não é mais renovada e a conexão é eliminada pelos nós do balanceador de carga 110. Em pelo menos algumas modalidades, a entrada ou entradas de cache para a conexão podem permanecer no cache em um nó do balanceador de carga 110 até que a memória seja requisitada para alguma outra conexão ativa.

[0185] Assim, o mecanismo de disponibilização de conexão estende, periodicamente ou aperiodicamente, as concessões de conexão nos servidores ingressos 112 e os mapeadores de fluxo primário e secundário 116 para manter o tráfego do cliente fluindo. Além disso, o mecanismo de disponibilização de conexão pode ajudar na recuperação de pelo menos algumas falhas do nó do balanceador de carga 110. Quando um ou mais dos nós do balanceador de carga 110 mantendo as informações do estado para uma conexão do cliente falhar, as informações da conexão ativa fornecidas aos nós do balanceador de carga restantes 110 pela disponibiliza- ção de conexão podem, em alguns casos, ser usadas para recuperar a conexão.

[0186] Usando o mecanismo de disponibilização de conexão, os nós do servidor 130 são as fontes de autoridade para os estados da conexão entre os servidores 134 e os clientes 160. Além disso, o encerramento das conexões aos servidores 134 é administrado passivamente pelos módulos do balanceador de carga 132 nos nós do servidor 130 e nos nós do balanceador de carga 110. O controle de fluxo não é necessário entre os nós do servidor 130 e os nós do balanceador de carga 110. Em outras palavras, os módulos do balanceador de carga 132 não precisam enviar mensagens aos nós do balanceador de carga 110 para informar ativamente aos nós que conexões específicas foram encerradas. Quando um servidor de 134 encerra uma conexão, o servidor 134 libera seu estado interno para a conexão. O módulo de ba- lanceador de carga 132 usa o estado interno do servidor 134 para preencher o pacote de disponibilização de conexão. Uma vez que a conexão não está mais no estado interno do servidor 134, a conexão não é disponibilizada aos nós do balanceador de carga 110. A concessão para a conexão no nó do balanceador de carga 110 então expira e os nós do balanceador de carga 110 esquece passivamente a conexão. A memória em um cache do nó do balanceador de carga 110 que foi usado para a co-nexão pode então ser usado para outras conexões, conforme necessário.

[0187] Em algumas modalidades, as concessões para as conexões mantidas pelos nós do balanceador de carga 110 pode envolver entradas de marcação de tempo para as conexões no cache. Quando uma concessão de conexão é renovada por um pacote de disponibilização de conexão, a marcação de tempo pode ser atualizada. Se a concessão de uma conexão não for renovada porque a conexão não está mais sendo disponibilizada pelo módulo do balanceador de carga 132 no nó do servidor 130, então a marcação de tempo não é mais atualizada. Em pelo menos algumas modalidades, um método de coleta lenta de lixo pode ser usado, em que a entrada para a conexão pode permanecer no cache até que a memória seja requisitada. Por exemplo, em pelo menos algumas modalidades, as marcações de tempo nas entradas de cache podem ser comparadas a um limite de tempo de renovação de concessão; se o marcador de tempo para uma entrada de cache for mais antigo do que o limite, então a entrada é obsoleta e pode ser reutilizada. No entanto, em algumas modalidades, as entradas obsoletas podem passar por coleta de lixo ativa.

Recipientes de disponibilização de conexão

[0188] Em pelo menos algumas modalidades, para cada conexão TCP do cliente, há três nós do balanceador de carta 110 que mantêm um estado de conexão - o nó 110 servindo como o servidor de ingresso 112, o nó 110 servindo como o ma- peador de fluxo primário 116 e o nó servindo como o mapeador de fluxo secundário 116. Para um determinado fluxo TCP, os mapeadores de fluxo primário e secundário 116 podem ser determinados, por exemplo, por um nó do balanceador de carga 110, aplicando-se uma função hash consistente ao fluxo TCP para encontrar o nó do ma- peador de fluxo primário 116 e seu nó sucessor no anel hash consistente. O nó do balanceador de carga de 110 que serve como o servidor de ingresso 112 para um fluxo TCP é o nó 110 que recebe tráfego para esse fluxo a partir do roteador de bor-da 104 com base na função hash de vias múltiplas internas (por exemplo, ECMP) do roteador de borda 104. Se houver uma falha no nó 110 ou uma adição, o nó do ba- lanceador de carga 110 que serve como o servidor de ingresso 112 pode alterar em vários dos fluxos TCP ativos; e os nós do balanceador de carga 110 que servem como os mapeadores de fluxo para pelo menos alguns fluxos TCP ativos podem alterar (ver, por exemplo, as Figuras de 11A a 11D). Para cada fluxo TCP para o servidor 132 em um nó do servidor 130, o módulo do balanceador de carga 132 no nó do servidor 130 mantém informações de estado indicando que um dos nós do balan- ceador de carga 110 é o servidor de ingresso de 112 para esse fluxo TCP, visto que ele recebe tráfego desse nó do balanceador de carga 110. No entanto, em pelo menos algumas modalidades, o módulo do balanceador de carga 132 pode não saber e pode ser incapaz de determinar qual dos nós do balanceador de carga 110 está servindo como os mapeadores de fluxo primário e secundário para um fluxo TCP, visto que o módulo do balanceador de carga 132 pode não saber a função hash consistente que é utilizada. Em outras palavras, em pelo menos algumas modalidades, os módulos do balanceador de carga 132 não executam um hashing consistente.

Disponibilização das informações da conexão ativa

[0189] As Figuras 19A e 19B ilustram graficamente uma técnica de disponibi- lização de conexão, de acordo com pelo menos algumas modalidades. A Figura 19A ilustra os módulos do balanceador de carga (BC) que publicam informações da conexão ativa aos nós do balanceador de carga. Em pelo menos algumas modalidades, cada módulo do balanceador de carga 132 coleta informações para cada fluxo TCP ativo no nó do servidor 130 e forma um pacote de disponibilização de conexão. As informações para um determinado fluxo TCP incluem informações de identificação do nó do balanceador de carga 110 que serve como o servidor de ingresso 112 para o fluxo. Quando um pacote de disponibilização de conexão estiver pronto (por exemplo, quando o intervalo de disponibilização de conexão foi atingido), o módulo do balanceador de carga 132 seleciona aleatoriamente um nó do balanceador de carga 110, por exemplo, a partir da lista de nós do balanceador de carga íntegros 110 que são enviados periodicamente aos nós do servidor 130 a partir dos nós do balanceador de carga 110 que verificam a integralidade dos nós do servidor 130, como descrito anteriormente. O módulo do balanceador de carga 132, em seguida, envia o pacote de disponibilização de conexão ao nó 110 selecionado. Por exemplo, na Figura 19A, o módulo do balanceador de carga 132A enviou um pacote de dispo- nibilização de conexão ao nó do balanceador de carga 110A e posteriormente envia outro pacote de disponibilização de conexão ao nó do balanceador de carga 110B.

[0190] A Figura 20 é um fluxograma de alto nível de um método de disponibi- lização de conexão que pode ser realizado por cada módulo do balanceador de carga 132, de acordo com pelo menos algumas modalidades. Como indicado em 500, o módulo do balanceador de carga (BC) 132 cria uma entrada de disponibilização de conexão para cada fluxo TCP ativo no respectivo nó do servidor 130. Em pelo menos algumas modalidades, o módulo do balanceador de carga 132 recupera a série de conexões TCP ativas que o servidor 134 no nó do servidor 130 administra, por exemplo, a partir do /proc/net/tcp no nó do servidor 130. Para cada conexão TCP ativa, o módulo do balanceador de carga 132 busca (por exemplo, em uma tabela mantida localmente das conexões ativas) o nó do balanceador de carga 110 que está servindo como o servidor de ingresso 112 para o fluxo TCP e cria uma entrada de disponibilização de conexão que indica a tupla TCP para a conexão (por exemplo, uma tupla de 4 que consiste em: endereço IP do cliente, porta do cliente, endereço IP do servidor (público) e porta do servidor) e para o servidor de ingresso 112 para a conexão. Note-se que cada módulo balanceador de carga 132 mantém informações para cada conexão TCP ativa indicando o último nó do balanceador de carga 110 a partir do qual um pacote foi recebido para a conexão, e tais informações podem ser usadas pelo módulo do balanceador de carga 132 para identificar o nó de ingresso 110 para cada conexão ativa.

[0191] Como indicado em 502, o módulo do balanceador de carga 132 seleciona aleatoriamente um nó do balanceador de carga 110 ao qual o pacote de dispo- nibilização de conexão (contendo uma ou mais entradas de disponibilização de conexão, com uma entrada para cada conexão TCP ativa) deve ser enviado. Em pelo menos algumas modalidades, o módulo do balanceador de carga 110 pode ser selecionado aleatoriamente quando o módulo do balanceador de carga 132 determinar que o pacote de disponibilização de conexão está pronto para ser enviado. Em pelo menos algumas modalidades, essa determinação é feita de acordo com um intervalo de disponibilização de conexão. Como exemplos não limitativos, o intervalo de dis- ponibilização de conexão pode ser de 100 milissegundos (ms) ou um segundo. Em pelo menos algumas modalidades, o módulo do balanceador de carga 110 é selecionado a partir de uma lista de nós do balanceador de carga íntegros 110 que foram anteriormente recebidos a partir de um dos nós do balanceador de carga 110. Como indicado em 504, o módulo do balanceador de carga disponibiliza, então, o pacote de disponibilização de conexão ao nó do balanceador de carga 110 selecionado. Em pelo menos algumas modalidades, o pacote de disponibilização de conexão é um pacote sem estado, por exemplo, um pacote UDP. Em algumas modalidades, o pacote de disponibilização de conexão pode ser comprimido antes de enviar os pacotes ao nó do balanceador de carga alvo 110. Em pelo menos algumas modalidades, as informações de disponibilização de conexão podem ser enviadas ao nó do balan- ceador de carga alvo 110 em um ou mais pacotes.

[0192] Como indicado pela seta que volta do elemento 504 ao elemento 500, o módulo do balanceador de carga 132 pode compilar continuamente pacotes de disponibilização de conexão, selecionar nós aleatórios 110 e enviar os pacotes aos nós selecionados. Como mencionado acima, isso pode ser executado de acordo com um intervalo de disponibilização de conexão, de modo que os nós do balancea- dor de carga 110 sejam atualizados com relativa regularidade com informações da conexão ativa para manter as concessões de conexão nos nós do balanceador de carga 110.

[0193] Em pelo menos algumas modalidades, visto que os pacotes de dispo- nibilização de conexão são distribuídos aleatoriamente aos nós do balanceador de carga 110 pelos módulos do balanceador de carga, os nós do balanceador de carga 110 que recebem os pacotes de disponibilização de conexão são responsáveis por distribuir as informações da conexão ativa nos pacotes de disponibilização de conexão aos nós de ingresso/primário/secundário 110 corretos para as conexões. A Figura 19B e as Figuras 21 e 22 ilustram métodos para a distribuição de informações da conexão ativa que podem ser usadas em pelo menos algumas modalidades.

[0194] A Figura 19B ilustra a distribuição de informações da conexão ativa entre os nós do balanceador de carga 110, de acordo com pelo menos algumas modalidades. Quando um nó do balanceador de carga 110 recebe um pacote de disponi- bilização de conexão de um módulo do balanceador de carga 132, o nó do balance- ador de carga 110 pode analisar as informações para cada fluxo TCP indicado para determinar o nó de ingresso e os nós do mapeamento primário e secundário para esse fluxo. Se o nó do balanceador de carga 110 estiver servindo em uma dessas funções para um fluxo, o nó do balanceador de carga 110 consome as informações para o fluxo (por exemplo, pela atualização de seu cache de informações de estado). Em pelo menos algumas modalidades, o nó do balanceador de carga 110 pode também incluir as informações para o fluxo no(s) pacote(s) a ser(em) enviado(s) para um ou mais de outros nós 110 que estão servindo nas outras funções para o fluxo. Para os fluxos restantes indicados pelo pacote de disponibilização de conexão, o nó do balanceador de carga 110 divide as informações da conexão ativa em dois ou mais pacotes menores e envia cada pacote a um ou mais dos outros nós do balan- ceador de carga 110. Por exemplo, em pelo menos algumas modalidades, um pacote contendo informações da conexão ativa para um ou mais fluxos pode ser enviado aos nós do balanceador de carga 110 que estão servindo como o servidor de ingresso 112, o mapeamento de fluxo primário 116A e o mapeamento de fluxo secundário 116B para o(s) fluxo(s).

[0195] A Figura 21 é um fluxograma de um método para distribuição das informações de conexão recebidas em um pacote de disponibilização de conexão aos nós do balanceador de carga 110, de acordo com pelo menos algumas modalidades. Como indicado em 520, um nó do balanceador de carga 110 recebe um pacote de disponibilização de conexão de um módulo do balanceador de carga 132. O módulo do balanceador de carga 132 gerou o pacote e selecionou o nó do balanceador de carga 110 para receber o pacote, por exemplo, conforme descrito em referência às Figuras 19A e 20. O pacote de disponibilização de conexão pode incluir informações que identificam o nó do servidor 130 a partir do qual o pacote foi recebido (por exemplo, um endereço IP do módulo do balanceador de carga 132 no nó do servidor 130) e uma lista de entradas identificando as conexões TCP ativas (por exemplo, uma de 4 tuplas consistindo em: endereço IP do cliente, porta do cliente, endereço IP do servidor (público e porta do servidor para cada conexão).

[0196] Nos elementos 522-530 da Figura 21, o módulo do balanceador de carga 110 processa iterativamente as informações de conexão TCP indicadas no pacote de disponibilização de conexão recebido. Como indicado em 522, o nó do balanceador de carga 110 analisa a entrada para um próximo fluxo TCP no pacote para determinar nó de ingresso 110 e os nós 110 do mapeador de fluxo primário e secundário para o respectivo fluxo TCP. Em pelo menos algumas modalidades, o nó do balanceador de carga 110 obtém a identidade do nó de ingresso 110 a partir da entrada de disponibilização de conexão. Em pelo menos algumas modalidades, os nós do mapeador de fluxo primário e secundário 110 para o fluxo TCP podem ser determinados de acordo com a função hash consistente. Em 524, se o nó do balan- ceador de carga 110 estiver servindo em uma das funções para o fluxo de TCP a ser examinado, então em 526 o nó do balanceador de carga 110 consome as informações para o fluxo, por exemplo, atualizando seu cache de informações de estado. Como indicado em 528, o nó do balanceador de carga 110 pode adicionar a entrada de disponibilização de conexão para o fluxo de TCP a um pacote que está sendo construído e deve ser enviado a outro nó do balanceador de carga 110. Em 530, se houver mais entradas de disponibilização de conexão para os fluxos no pacote de disponibilização de conexão, então o método retorna a 522 para processar a próxima entrada. Caso contrário, o nó do balanceador de carga envia o(s) pacote(s) re- cém-construído(s), cada um contendo um subconjunto das entradas de disponibili- zação de conexão do pacote de disponibilização de conexão original para os nós do balanceador de carga alvo 110 para os pacotes, como indicado em 532. Em pelo menos algumas modalidades, os pacotes enviados aos nós do balanceador de carga alvo 110 são pacotes sem estado, por exemplo, pacotes UDP. Em algumas modalidades, os pacotes podem ser comprimidos antes de envias os pacotes aos nós do balanceador de carga alvo 110.

[0197] Assim, em pelo menos algumas modalidades, nos elementos 522-528 da Figura 21, o nó do mapeador de fluxo 110 constrói um ou mais pacotes (por exemplo, pacotes de UDP), cada um para ser enviado a um nó específico dentre os outros nós 110 de acordo com as informações determinadas em 522 a partir das entradas de disponibilização de conexão no pacote de disponibilização de conexão recebido. Em pelo menos algumas modalidades, um pacote enviado a outro nó 110 contém entradas para fluxos TCP para os quais o nó alvo 110 está servindo como nó de ingresso 110, nó do mapeador de fluxo primário 110 ou nó do mapeador do fluxo secundário 110. Note-se que em algumas modalidades um determinado nó do ba- lanceador de carga 110 pode servir como o nó do mapeador de fluxo primário ou de ingresso para um fluxo TCP ou como um nó do mapeador de fluxo secundário ou de ingresso para um fluxo TCP.

[0198] A Figura 22 ilustra um método alternativo para distribuição das informações da conexão ativa recebida em um pacote de disponibilização de conexão que tem como alvo os nós do balanceador de carga 110, de acordo com pelo menos algumas modalidades. Como indicado em 550, um nó do balanceador de carga 110 recebe um pacote de disponibilização de conexão de um módulo do balanceador de carga 132. Neste método, como se indica em 552, um processo no módulo do ba- lanceador de carga 110 analisa as entradas de disponibilização de conexão no pacote e divide o pacote recebido em um ou mais pacotes menores, conforme o caso. O módulo do balanceador de carga 110 não consome localmente as informações de fluxo durante esse processo. Uma vez que o pacote de disponibilização de conexão foi dividido em um ou mais pacotes, os pacotes são então processados, como se indica em 554-560. Em 554, se o nó alvo 110 para o pacote for esse nó do balance- ador de carga 110, então o nó do balanceador de carga 110 consome localmente o pacote, como indicado em 556. Caso contrário, o pacote é enviado para o nó do ba- lanceador de carga alvo 110. Em 560, se houver mais pacotes a serem processados, então o método retorna ao 554. Caso contrário, o método é realizado.

[0199] Assim, o nó do balanceador de carga 110 que recebe um pacote de disponibilização de conexão de um módulo do balanceador de carga 132 pode dividir o pacote de disponibilização de conexão em dois ou mais pacotes menores que são específicos para nós específicos dentre os outros nós do balanceador de carga 110 e distribuir os pacotes conforme o caso, enquanto consomem-se internamente as informações de fluxo de qualquer fluxo TCP que estiver sendo administrado no momento pelo nó do balanceador de carga 110. Enquanto isso, outros nós do balan- ceador de carga 110 também podem estar recebendo pacotes de disponibilização de conexão dos módulos do balanceador de carga 132, dividindo as entradas de disponibilização de conexão em vários pacotes menores e enviando os pacotes menores aos nós alvo 110 para então distribuir as informações da conexão ativa entre os nós 110.

Acionadores de disponibilização de conexão

[0200] Em pelo menos algumas modalidades, uma disponibilização de conexão pode ser acionada em um módulo do balanceador de carga 132 por um ou mais eventos diferentes. Como observado anteriormente, em algumas modalidades, um pacote de disponibilização de conexão pode ser gerado e enviado a um nó do ba- lanceador de carga selecionado aleatoriamente 110 de acordo com um intervalo de disponibilização de conexão, por exemplo, a 100ms ou um segundo intervalo, para renovar as concessões para as conexões TCP nos nós do balanceador de carga 110. Em algumas modalidades, uma mudança na associação dos nós do balancea- dor de carga 110 pode acionar um evento de disponibilização de conexão imediata. Em pelo menos algumas modalidades, o módulo do balanceador de carga 132 pode ser informado sobre a mudança da lista de nós do balanceador de carga íntegros 110 enviados de um dos nós do balanceador de carga 110 que verifica a integralida- de do respectivo nó do servidor 130. Ao detectar a alteração de acordo com a lista (uma supressão ou uma adição), o módulo do balanceador de carga 132 pode gerar um pacote de disponibilização de conexão e enviar a um nó do balanceador de carga 110, de modo que as conexões TCP afetadas pela mudança podem ser recuperavas com mais rapidez pelos nós do balanceador de carga 110.

Prevenir loops dos pacotes

[0201] Os loops dos pacotes de disponibilização de conexão podem ocorrer se a associação da camada do balanceador de carga mudar durante o processamento de um pacote de disponibilização de conexão. Um primeiro nó 110 pode receber um pacote de disponibilização de conexão de um módulo do balanceador de carga 132 e envia um pacote menor a um segundo nó 110. No entanto, se a associação mudou, o segundo nó 110 pode determinar que o pacote deve ir para o primeiro nó 110 e pode, assim, adiantar o pacote para o primeiro nó 110. Em pelo menos algumas modalidades, para evitar que ocorra esse loop, diferentes números de portas podem ser usados para os pacotes de disponibilização de conexão recebidos dos módulos do balanceador de carga 132 e daqueles recebidos dos nós do balan- ceador de carga 110 e os nós do balanceador de carga 110 não redistribuem os pacotes de disponibilização de conexão recebidos dos outros nós do balanceador de carga 110.

Alternativas de distribuição de pacotes de disponibilização de conexão

[0202] Nos métodos de publicação de conexão descritos acima, o módulo do balanceador de carga 132 seleciona aleatoriamente um nó do balanceador de carga 110 para o qual um pacote de disponibilização de conexão é enviado. No entanto, em algumas modalidades, outros métodos podem ser usados para selecionar um nó do balanceador de carga 110. Por exemplo, em algumas modalidades, o nó do ba- lanceador de carga 132 pode construir um ou mais pacotes de disponibilização de conexão que são direcionados a um nó de ingresso 110 particular que administra um ou mais fluxos TCP ativos e envia o(s) pacote(s) ao(s) nó(s) de ingresso alvo 110. O(s) nó(s) de ingresso 110 então redistribuiriam as informações da conexão ativa aos mapeadores de fluxo primário e secundário para as conexões. Como outro exemplo, em algumas modalidades, em vez de enviar o pacote de disponibilização de conexão a um único nó 110, selecionado aleatoriamente, cada pacote de dispo- nibilização de conexão pode ser enviado pelo módulo do balanceador de carga 132 a um ou mais nós íntegros 110, ou para todos os nós íntegros 110.

Arquitetura do nó do balanceador de carga

[0203] A Figura 23 ilustra um exemplo de arquitetura de pilha de software para um nó do balanceador de carga 110, de acordo com pelo menos algumas modalidades, e não se pretende limitativa. Neste exemplo de arquitetura de pilha de software, o nó do balanceador de carga 110 é executado em um único processo de tecnologia Java™ 1102 que usa a tecnologia Java Native Interface(JNI™) 1104 para administrar uma camada do código nativo que pode incluir um código nativo do servidor do balanceador de carga 1106 e um código de processamento de pacote do núcleo 1108 para o código da tecnologia Intel™ Dataplane Development Kit (DPDK). O código nativo pode fazer interface com dois controladores de interface de rede (NICs 1114A e 1114B). O primeiro NIC (NIC 1114A) pode se voltar para o "norte"; isto é, para o roteador de borda 104. Um segundo NIC (NIC 1114B) pode se voltar para o "sul"; isto é, para o nó do servidor 130. Em pelo menos alguma modalidade, NICs 1114A e 1114B podem não manter as pilhas TCP. Assim, pelo menos algumas modalidades podem incluir um terceiro NIC 1114C que não suporta conexões TCP, de modo que o nó do balanceador de carga 110 pode se comunicar com os processos através de um plano de controle e vice-versa. Alternativamente, em algumas modalidades, apenas o primeiro NIC 1114A, voltado para o norte, e o segundo NIC 111B, voltado para o sul, podem ser implementados no nó do balanceador de carga 110 e o segundo NIC 1114B, voltado para o sul, pode ser implementado como uma pilha TCP através da qual o nó do balanceador de carga 110 pode se comunicar com os processos através do plano de controle. O nó do balanceador de carga 110 também inclui um software de tecnologia de sistema operacional (OS) 1112, por exemplo, um kernel Linux™ e uma camada de software de tecnologia Java Virtual Machine (JVM™) 1110 no topo de um software de tecnologia de OS 1112 e de tecnologia JNI 1104.

[0204] Em pelo menos algumas modalidades, os nós do balanceador de carga 110 no sistema de balanceamento de carga distribuído podem, cada, precisar processar concomitantemente muitos fluxos de dados a altas taxas de pacote. Em pelo menos algumas modalidades, para obter o nível necessário de rendimento, os nós do balanceador de carga 110 podem lançar mão da tecnologia Intel™ Dataplane Development Kit (DPDK) para um processamento de pacotes de alta performance. A tecnologia DPDK permite a um programa de userspace ler/registrar pacotes direta- mente para e a partir do controlador de interface de rede (NIC) e ignora várias camadas da pilha de rede kernel Linux (exceto o driver do NIC de base ixgbe Linux). A abordagem DPDK para processamento de pacotes rejeita a entrada com base em processador de interrupção em favor de núcleos de CPU dedicados que fazem um levantamento direto do hardware do NIC em um loop ocupado. Esta abordagem pode permitir taxas de pacotes muito maiores, à custa de aumentar a saída térmica pela execução contínua de núcleos de CPU dedicados em um loop ocupado. A tecnologia DPDK também pode fornecer ferramentas para processamento de pacotes, incluindo gerenciamento de núcleo de CPU, filas livres de bloqueio, pools de memória e primitivos de sincronização. Como mostrado na Figura 24, na tecnologia DPDK, um núcleo de CPU dedicado 600 pode ser usado para cada tarefa específica e o trabalho é passado de um núcleo de CPU 600A a outro núcleo de CPU 600B utilizando filas sem bloqueio 602.

[0205] As filas de DPDK 602 modem ser implementadas usando buffers em anel com potência de dois rápidos e podem suportas variantes de consumi- dor/fabricante únicas ou múltiplas. As múltiplas variantes de consumidor/fabricante não são de fato livres de bloqueio, visto que não contêm um loop de comparação e alternância (CAS) para sincronizar o acesso. Toda a memória do buffer de pacote pode ser pré-alocada em pools de memória, de modo que apenas os ponteiros para os buffers sejam livros e registrados nas filas 602. Os pools de memória podem ser implementados como filas, podem ser otimizados para distribuir a memória ao longo do canal de memória e classificar e podem suportar uma alocação otimizada de acesso de memória não-uniforme (NUMA). Em pelo menos algumas modalidades, os buffers do pacote podem usar um método, como o paradigma Mbuf, que sobrea- loca o bastante de reserva dinâmica e reserva da parte final em cada buffer do paco-te para suportar operações de encapsulação/desencapsulação que podem adicio- nar/remover cabeçalhos de camada de rede externa sem exigir cópias do buffer.

[0206] Em pelo menos algumas modalidades dos nós do balanceador de carga 110, uma arquitetura de processamento do pacote de núcleo pode ser implementada para lançar mão da tecnologia DPDK. Cada nó do balanceador de carga de 110 pode incluir pelo menos um processado de pacote com múltiplos núcleos implementados de acordo com a arquitetura de processamento de pacote do núcleo. A arquitetura de processamento de pacotes do núcleo pode usar um paradigma de consu- midor/fabricante único para o fluxo do pacote através das filas e núcleos do processador de pacote com múltiplos núcleos. Nesse paradigma, cada fila é a entrada para um e somente um núcleo e cada núcleo é a saída para um e somente um núcleo para cada outro núcleo ao qual ela alimenta pacotes. Além disso, a memória usada pelos núcleos no processador de pacotes com múltiplos núcleos não é compartilhada; cada núcleo tem a sua própria região de memória, separadamente. Assim, não há compartilhamento de memória ou fila entre núcleos, nenhuma contenção de memória ou fila e não há necessidade de mecanismos de compartilhamento de memória ou fila, como uma solicitação de propriedade (RFO) ou de comparação e alternância (CAS). As Figuras 25 e 26 ilustram exemplos de processadores de pacote com múltiplos núcleos implementados de acordo com a arquitetura de processamento de pacote do núcleo.

[0207] A Figura 25 ilustra um exemplo de processador de pacote com múltiplos núcleos, de acordo com a arquitetura de processamento de pacote do núcleo que lança mão da tecnologia de DPDK para processar os fluxos de ados, de acordo com pelo menos algumas modalidades. A arquitetura de processamento de pacote do núcleo pode ser implementada como um processador de pacote com múltiplos núcleos, de acordo com um paradigma de fabricante/consumidor único. Em pelo menos algumas modalidades, como ilustrado na Figura 23, os nós do balanceador de carga 110 têm, cada, dois controladores de interface de rede (NICs) - um NIC 1114A voltado para o norte, que se volta para a rede de borda/roteador de borda 104 e um NIC 1114B voltado para o sul, que se volta para os nós do servidor/para a rede de produção 130. Em pelo menos algumas modalidades, os NICs 1114 podem ser NICs de 10 Gpbs. A maioria dos pacotes que fluem através de um nó do balan- ceador de carga 110 é recebida em um desses dois NICs (NIC 1114A ou 1114B), processada (por exemplo, encapsulada ou desencapsulada) e transmitida para outro NIC (NIC 1114B ou 1114A).

[0208] Com referência à Figura 25, em pelo menos algumas modalidades, um nó do balanceador de carga 110 gira até dois núcleos de CPU, um núcleo receptor (RX) 610 e um núcleo transmissor (TX) 630 para cada NIC 1114. O nó do balancea- dor de carga 110 também gira até uma quantidade de núcleos de trabalho 620 que processam pacotes para os dois NICs 1114 nas duas direções; nesse exemplo, quatro núcleos de trabalho de 620A a 620D são usados. Os núcleos receptores 610 leem os lotes de pacotes de entrada de suas filas de entrada conforme elas chegam ao NIC 1114 e distribuem os pacotes aos núcleos de trabalho 620 que realizam a maior parte do trabalho para cada pacote, com cada núcleo receptor 610 alimentando pacotes em uma respectiva fila de entrada de trabalho 612 para cada núcleo de trabalho 620. Em pelo menos algumas modalidades, um núcleo receptor 610 pode realizar uma técnica de 4 camadas de "fluxo hash" em cada pacote de entrada (se-melhante à técnica de roteamento de vias múltiplas submetidas a hash por fluxo que podem ser usadas pelo roteador de borda 104, como descrito anteriormente) para distribuir os pacotes aos núcleos de trabalho 620 ao mesmo tempo em que garante que toda conexão de cliente específica (distinguida pelo sem endereço IP ou porta) será processada pelo mesmo núcleo de trabalho 620. Isso significa que cada núcleo de trabalho 620 pode sempre visualizar o mesmo subconjunto de pacotes e elimina a contenção nos dados de estado administrados pelo núcleo de trabalho 620, de modo que nenhum bloqueio seja necessário. Os ponteiros para os pacotes recebidos podem ser distribuídos entre as filas de trabalho 622 que os núcleos de trabalho 620 monitoram continuamente para uma nova entrada. Os núcleos trabalhadores 620 são responsáveis por gerenciar o estado (por exemplo, nó de servidor atribuído 130) para cada ligação, e pode desempenhar o encapsulamento ou desencapsula- mento de UDP no pacote antes de encaminhar o pacote para uma de suas filas de saída 632. Os núcleos de transmissão 630 percorrem as filas de saída 632 de núcleo trabalhador 620 e escrevem os pacotes de saída ao seu NIC 1114 correspondente conforme aparecem nas filas 632.

[0209] A Figura 26 ilustra um exemplo de processador de pacote multicore implementado de acordo com a arquitetura de processamento de pacotes central que se aproveita da tecnologia DPDK para o processamento de fluxos de dados, de acordo com, pelo menos, algumas modalidades. A arquitetura de processamento de pacotes de núcleo pode ser implementada como um processador de pacote multicore de acordo com um paradigma de único produtor/único consumidor. Em pelo menos algumas modalidades, além de processar os fluxos de TCP de cliente de alto rendimento, a arquitetura de núcleo de DPDK em um nó do balanceador de carga 110 também pode ser utilizado para enviar e receber pacotes nos NICs voltados para Norte e Sul 1114 para outros protocolos tais como ARP, DHCP, e BGP. Na modalidade mostrada na Figura 26, um núcleo trabalhador 620A é dedicado a manipula-ção dos pacotes para esses protocolos. Esse núcleo trabalhador 620A pode ser referido como um núcleo trabalhador "lento", uma vez que o processamento desses pacotes geralmente acontece a um ritmo mais lento do que os fluxos de TCP de cliente, enquanto os outros núcleos trabalhadores 620B-620D que processam apenas os fluxos de TCP de cliente podem ser encaminhados para núcleos trabalhadores mais rápidos. Os núcleos de recepção 610A e 610B manipular os pacotes de entrada nos NICs voltados para norte e voltados para sul 1114, respectivamente, podem identificar os pacotes que devem ser tratados pelo núcleo trabalhador lento 620A e direcionar os pacotes para filas de entrada 622 para o núcleo trabalhador lento 620A. O núcleo trabalhador lento 620A também pode monitorar uma fila de entrada 622 para os pacotes gerados através de Java/JNI, e uma fila de saída 634 para pacotes de saída para Java/JNI. O núcleo trabalhador lento 620A também emitir para uma fila de entrada 622 para cada um dos núcleos trabalhadores rápidos 620B até 620D de modo que o núcleo trabalhador lento 620A possa enviar os pacotes para cada um dos núcleos trabalhadores rápidos 620B até 620D, para os pacotes de publicação de conexão de exemplo. O núcleo trabalhador lento 620A também tem uma fila de saída 632 que alimenta cada um dos núcleos de transmissão 630A e 630B.

[0210] Em pelo menos algumas modalidades, a terceira fila de entrada 622 de cada núcleo trabalhador rápido 620B até 620D é uma fila de saída a partir do núcleo trabalhador lento 620A. Em pelo menos algumas modalidades, essa terceira fila de entrada 622 podem ser, por exemplo, usada para a receber e processar os pacotes de publicação de conexão, cada um contendo informações de estado de conexão, através das filas trabalhadoras rápidas 620B até 620D. Para pelo menos alguns desses pacotes de publicação de conexão pode não haver nenhuma saída para os núcleos de transmissão 630. Em vez disso, as informações de estado de conexão nas quais os pacotes podem ser consumidos pelo núcleo trabalhador rápido 620, por exemplo, atualizando o estado armazenado para um ou mais fluxos de pacotes que o núcleo trabalhador rápido respectivo 620 mantém. Assim, as filas de saída do núcleo trabalhador lento 620A que a inserir aos núcleos trabalhadores rápidos 620B até 620D podem fornecer um caminho que não seja uma fila de entrada 622 diretamente de um núcleo de recepção 610 para atualizar os estados armazenados dos núcleos trabalhadores rápidos.

[0211] Em pelo menos algumas modalidades, os processadores de pacote multicore das Figuras 25 e 26 podem filtrar os pacotes de entrada e apenas processar e emitir os pacotes que são válidos. Por exemplo, em pelo menos algumas modalidades, os núcleos de recepção 610 podem filtrar os pacotes que são de um pro tocolo não suportado por qualquer um dos núcleos trabalhador 620 e, portanto, não envia os pacotes para os núcleos trabalhadores 620. Em pelo menos algumas modalidades, os núcleos trabalhadores 620, quando processam os pacotes, podem, cada um, primeiro analisar os pacotes lidos a partir das filas de entrada de trabalhador respectivas 622 para determinar caso os pacotes devam ser aceitos para processamento adicional e emitidos aos núcleos de transmissão 630, e apenas podem concluir o processamento e emissão dos pacotes para os núcleos de transmissão 630 que sejam aceitos; os pacotes não aceitos podem ser descartados. Por exemplo, os núcleos trabalhadores 620 pode buscar pelas informações de endereço para cada pacote e só aceitam os pacotes que sejam direcionados a endereços válidos que estejam sendo balanceados em relação à carga, descartando quaisquer outros pacotes.

Manipulando dados de Border Gateway Protocol (BGP)

[0212] Em pelo menos algumas modalidades, os fluxos de pacotes associados a um cliente de BGP dentro e fora da arquitetura do núcleo podem ser tratados da seguinte forma. Visto que os NICs 1114A e 1114B não estão vinculados ao kernel de Linux, a conexão de TCP ao roteador de borda 104 é interceptada pela arquitetura de núcleo, conforme ilustrado na Figura 26 e processa-se através do núcleo trabalhador lento 622A, que passa os pacotes de BGP para o espaço de Java através da fila de saída 634. Esses pacotes de TCP são tratados posteriormente através de um ou mais módulos no nó do balanceador de carga 110 antes de ser entregue ao cliente de BGP, incluindo o processamento pelo kernel de Linux para gerenciar a conexão de TCP e efetivamente traduzir os pacotes em um fluxo de TCP. Esse projeto permite que o cliente de BGP seja escrito usando bibliotecas de soquete de TCP Java padrão.

[0213] A Figura 27 ilustra o processamento de pacotes de TCP de BGP que chegam por um processo de nó do balanceador de carga (BC) 650, de acordo com pelo menos algumas modalidades. Um pacote do roteador de borda 104 chega no NIC voltado ao norte 640 e entra na fila de entrada 640 para núcleo de recepção 652. O núcleo de recepção 652 lê a partir da fila 640, identificou o pacote como um pacote BGP, e coloca o pacote na fila de entrada 654 um para o núcleo trabalhador lenta 656. O núcleo trabalhador lento 656 valida o pacote e coloca-o na fila de saída de JNI 658. O receptor de pacote de JNI 660 lê o pacote da fila de 658 via JNI, des- configura os endereços de origem/destino, e escreve o pacote a uma soquete bruto 644. O kernel de Linux 646 recebe o pacote bruto, manipula o mesmo de acordo com o protocolo TCP, e acrescenta os dados de carga útil ao soquete de InputStream de TCP. Os dados do pacote são, então, entregues a um soquete de TCP Java no cliente de BGP 662.

[0214] A Figura 28 ilustra o processamento de pacotes de TCP de BGP que saem por um processo de nó do balanceador de carga (BC) 650, de acordo com pelo menos algumas modalidades. O cliente de BGP 662 grava os dados em um so- quete de TCP Java do kernel do Linux 646. O kernel do Linux 646 manipula os dados de acordo com o protocolo de TCP e converte os dados em pacote(s) de TCP. Em pelo menos algumas modalidades, o(s) pacote(s) de TCP correspondem a uma regra de iptables de 127.x.x.x. O(s) pacote(s) de TCP são colocados numa fila de saída 648, por exemplo, uma fila Netfilter LOCAL_OUT. Um thread Java do receptor de pacote JNI 670 monitora a fila 648 via JNI, recebe o(s) pacote(s) de TCP e marca cada NF_STOLEN para fazer o kernel 646 esquecê-los. O thread Java desconfigura os endereços de origem/destino e adiciona o(s) pacotes(s) a uma fila de entrada JNI 672 para o núcleo trabalhador lento 656 via JNI. O núcleo trabalhador lento 656 recebe o(s) pacote(s) de TCP de sua fila de entrada de JNI 672 e coloca os pacotes na fila de saída 664 para o núcleo de transmissão 666 de NIC voltado ao norte 640. O núcleo de transmissão 666 lê o(s) pacote(s) de TCP a partir de sua fila de entrada 664 e escreve-os para o NIC voltado ao norte 640. Os pacotes de TCP são enviados através de NIC 640 o roteador de borda 104.

Teste e simulação de balanceadores de carga distribuída

[0215] O balanceador de carga descrito neste documento é um sistema distribuído que exige a interação de muitos componentes independentes (por exemplo, roteadores, nós do balanceador de carga, módulos balanceadores de carga, etc.). Para realizar o teste dos componentes, lógica e protocolos distribuídos, assim como para simular os cenários tais como falhas de nós, quedas de mensagem e atrasos, as modalidades de um sistema de teste são descritas que permitem que o balance- ador de carga distribuída para seja executado em um único processo no qual as interações podem ser testadas sem exigir que o código seja implantado em vários hosts em uma topologia de rede complexa (por exemplo, uma rede de produção). Para conseguir isso, é descrito um mecanismo de software referido como um barra- mento de mensagem que permite que múltiplos componentes balanceadores de carga sejam configurados e executados em ou como um processo único; o processo único só pode ser executado em um único sistema de host. O mecanismo de barra- mento de mensagem permite que o sistema de balanceadores de carga distribuída seja testado como um processo único, por exemplo, em um único sistema de host, enquanto que para os componentes balanceadores de carga (por exemplo, os nós do balanceador de carga e os módulos balanceadores de carga) parece que estão executando em uma rede de produção real.

[0216] O barramento de mensagem fornece uma estrutura que permite que o balanceador de carga distribuída seja executado como um único processo. Cada uma dentre a uma ou mais camadas de barramento de mensagem do processo simula um segmento de rede (por exemplo, Ethernet) entre os componentes balance- adores de carga distribuída. Os componentes de software do sistema balanceador de carga distribuída não tem de ser escrito de uma forma especial para permitir que os componentes operem dentro do ambiente de barramento de mensagem. Em vez disso, a estrutura de barramento de mensagem fornece um componente (que pode ser referido como um NIC de barramento de mensagem ou adaptador de pacote), que intercepta os pacotes os componentes do produto de sistema balanceador de carga distribuída, direciona os pacotes para a rede simulada fornecida através de uma camada de barramento de mensagem em vez de uma rede física real e fornece os pacotes para os componentes alvo. As camadas de barramento de mensagem não implementam pilha(s) de TCP/IP para a comunicação entre os componentes. Em vez disso, as camadas de barramento de mensagem realizam interface com o sistema operacional do sistema host (OS) e usam a pilha de TCP/IP do sistema host. As camadas de barramento de mensagem alavancam a pilha de TCP/IP fornecida pelo OS para converter os fluxos de TCP que os clientes e servidores esperam para e a partir dos pacotes individuais que o barramento de mensagem intercepta e entrega.

[0217] Em pelo menos algumas modalidades, a interface com o barramento de mensagem, componentes de balanceador de carga pode ser proporcionado com pelo menos um barramento de mensagem controlador de interface de rede (NIC), cada um com um controlo de acesso ao meio válido endereço (MAC), que envia os pacotes para e recebe pacotes a partir do ambiente de rede simulado de barramento de mensagem em vez de para e a partir de uma rede física. Um NIC de barramento mensagem é uma placa de rede virtual que se fixa ao barramento de mensagem em vez de a uma rede física. Cada componente balanceador de carga que precisa se comunicar através do barramento de mensagem requer pelo menos NIC de barra- mento de mensagem. Um NIC de barramento de mensagem serve como uma saída de pipeline para o barramento de mensagem e como uma entrada de pipeline para o componente. Os componentes podem instanciar múltiplas interfaces de rede de bar- ramento de mensagem para cada NIC barramento de mensagem.

[0218] Uma interface de rede de barramento de mensagem é um mecanismo para componentes se fixarem a um barramento de mensagem através de um NIC de barramento de mensagem. Uma interface de rede de barramento de mensagem pode ser sinônimo de uma interface de configuração de interface (ifconfig) na tecnologia Linux, com uma diferença de que a interface de rede de barramento de mensagem se fixa ao barramento de mensagem em vez de a uma rede física. Uma interface de rede de barramento de mensagem tem um endereço IP, e fica no topo de um NIC de barramento de mensagem. A interface de rede de barramento de mensagem expõe uma interface de fonte de pacotes, que pode ser utilizado pelo componente para receber os pacotes a partir do barramento de mensagem, e uma interface de coletor de pacote que pode ser utilizada pelo componente para enviar os pacotes para o barramento de mensagem.

[0219] Cada nó do balanceador de carga processa pacotes de rede individuais que são entregues e enviados através de uma implementação da fonte de pacote e interfaces de coletor de pacote. Quando se executa no ambiente de barramento de mensagem, essas interfaces são implementadas por meio da interface de rede de barramento de mensagem que adiciona ou remove os cabeçalhos de camada 2 de Ethernet (para os nós do balanceador de carga que esperam que isso seja realizado pela pilha de rede do kernel). Em um ambiente de produção conforme mostrado na Figura 29, a implementação da fonte de pacote e interfaces de coletor de pacote recebem e transmitem pacotes em uma interface de rede real. Em um ambiente de barramento de mensagem conforme mostrado na Figura 30, a implementação da fonte de pacote e interfaces de coletor de pacote recebem pacotes a partir de e transmitem pacotes em uma camada ou camadas de barramento de mensagem.

[0220] Por uma questão de simplicidade, um NIC de barramento de mensagem e uma interface de barramento de mensagem podem ser coletivamente referidos como um adaptador de pacote de barramento de mensagem, ou, simplesmente, adaptador de pacote. Consulte, por exemplo, as Figuras 31 e 32.

[0221] A Figura 29 ilustra um sistema de balanceamento de carga que inclui um balanceador de carga 700 distribuída em um ambiente de produção, de acordo com pelo menos algumas modalidades. O balanceador de carga de 700 foi simplificado para essa descrição. O balanceador de carga 700 pode se conectar aos clientes 742 em uma rede externa 740 através de um roteador de borda 702 de uma instalação de rede, tal como um data center que implementa o balanceador de carga 700. O balanceador de carga 700 inclui vários tipos de componentes - pelo menos um roteador de borda 704, dois ou mais de nós do balanceador de carga (BC) 710, dois ou mais balanceadores de carga (BC) 732 cada um implementado em um nó de servidor separado (não mostrado), um ou mais componentes de rede que formam malha 720, como roteadores ou switches, e em pelo menos algumas modalidades de um serviço de configuração 722. Em pelo menos algumas modalidades cada componente do balanceador de carga 700 pode ser implementado como ou em um dispositivo de computação separada, tal como um dispositivo de computação montado em rack.

[0222] A Figura 30 ilustra um sistema de teste de balanceador de carga 800 distribuída que incorpora um mecanismo de barramento de mensagem que permite que vários componentes do sistema de balanceamento de carga distribuída sejam configurados e executados em ou como um processo único, de acordo com pelo menos algumas modalidades. No balanceador de carga de 700 mostrada na Figura 29, cada componente de software de balanceador de carga é instalado e executado em um dispositivo de computação separada (por exemplo, o software balanceador de carga nos nós do balanceador de carga 710, e os módulos balanceador de carga 732 nos nós de servidor). Para ativar esses componentes de software balanceador de carga para executar em um único processo, cada componente de software balan- ceador de carga (mostrado como nós do balanceador de carga (BC) 810 e módulos balanceadores de carga (BC) 832 na Figura 30) pode incluir um código que abstrai a conectividade de rede dos componentes de modo que os pacotes dentro e fora do componente de software balanceador de carga também possam ser interceptados e roteados através do mecanismo de barramento de mensagem em vez de serem enviados e recebidos em uma rede física.

[0223] Em pelo menos algumas modalidades, no sistema de teste balancea- dor de carga distribuída 800, o mecanismo de barramento de mensagem não implementa pilha(s) de TCP para comunicações entre os componentes. Em vez disso, o mecanismo de barramento de mensagem realiza interface com o sistema operacional do sistema host (OS) e usa a pilha de TCP do sistema host. Em pelo menos algumas modalidades, a funcionalidade de barramento de mensagem se vincula ao kernel (por exemplo, o kernel de Linux) do OS do sistema host abaixo da camada de usuário por meio das tabelas de IP, uma funcionalidade do kernel. A funcionalidade de barramento de mensagem realiza um gancho nas tabelas de IP no nível de kernel, intercepta pacotes, e envia os pacotes para o processo de barramento de mensagem para roteamento.

[0224] Conforme mostrado através do roteador de borda simulado 862 e a malha simulada 864 na Figura 30, a funcionalidade dos componentes de rede física (por exemplo, o roteador de borda 704 e a malha 720 na Figura 29) pode ser simulada no software, como podem os clientes 860, os servidores 834, e serviço de configuração 866. Observa-se, no entanto, que em pelo menos algumas modalidades servidores reais em vez de simulados 834 podem ser utilizados nos sistemas de teste de balanceador de carga distribuída 800. As camadas de barramento de mensagem 850 da Figura 30 substituem a infraestrutura de rede física. Assim, os componentes de software balanceador de carga (nós do balanceador de carga 810 e módulos balanceadores de carga 832) podem ser executados no sistema de teste ba- lanceador de carga 800 enquanto sem obterem conhecimento de que não estão executando em um ambiente de rede de produção, conforme mostrado na Figura 29.

[0225] Alguns componentes (por exemplo, roteadores simulados) podem ser conectados à mais de uma camada de barramento de mensagem 850 de modo a transmitir pacotes a e receber pacotes de diferentes camadas de barramento de mensagem 850 que simulam segmentos de rede.

[0226] O mecanismo de barramento de mensagem implementado nas camadas de barramento de mensagem 850 do sistema de teste de balanceamento de carga distribuída 800 simula o "fio" de um segmento de rede. Em pelo menos algumas formas de realização, o mecanismo de barramento de mensagem entrega os pacotes para componentes de destino no sistema de teste de balanceamento de carga distribuída de 800 com base nos endereços MAC dos componentes. Assim, cada componente de software balanceador de carga (nós do balanceador de carga 810 e módulos balanceadores de carga 832) fornece um endereço MAC para a(s) camada(s) de barramento de mensagem 850 à(s) qual(ais) o mesmo está conectado de modo que o componente de software balanceador de carga possa receber os pacotes que são enviados para a(s) mesma(s) a partir de outros componentes no sistema de teste de balanceamento de carga distribuída 800.

Adaptadores de pacote de barramento de mensagem

[0227] As Figuras 31 e 32 ilustram adaptadores de pacotes de barramento de mensagem, de acordo com pelo menos algumas modalidades. Em pelo menos algumas modalidades, cada componente de software balanceador de carga (BC) processa os pacotes de rede individuais que são entregues e enviados através de uma implementação das interfaces PacketSource e PacketSink. Com referência à Figura 31, quando em execução no sistema de teste de balanceamento de carga distribuída 800, essas interfaces (mostradas como interface de fonte de pacote 862 e interface de coletor de pacote 864) podem ser implementadas através de um adaptador de pacote 860 entre a camada de barramento de mensagem 850 e o componente de software balanceador de carga 870 que adiciona ou remove os cabeçalhos de ca- mada 2 de Ethernet para os componentes de software de balanceamento de carga 870 que esperam que isso seja realizado pela pilha de rede do kernel. No ambiente de produção conforme ilustrado na Figura 29, a aplicação de PacketSource e PacketSink para os componentes de software de balanceamento de carga receberem e transmitirem os pacotes em interfaces de rede reais dos dispositivos físicos em que os componentes são implementados.

[0228] Referindo-se à Figura 31, em pelo menos algumas modalidades, quando um componente de software de balanceamento de carga 870 transmite um pacote, os threads de execução que chama um método de envio de pacote da interface de sink 864 transversal a uma cadeia de funções dentro de um adaptador de pacote 860 e também dentro de uma camada de barramento de mensagem 850 para entregar eventualmente o pacote para o componente de destino, adicionando o pacote àquela fila de entrada do componente. Em pelo menos algumas modalidades, quando um componente de software balanceador de carga 870 receber um pacote, o componente de software balanceador de carga 870 chama um método de pacote de recepção da interface de fonte de pacote 862 e lê os pacotes a partir de sua fila de entrada. Em pelo menos algumas modalidades, o mecanismo de barra- mento de mensagem não precisa de quaisquer threads adicionais próprias para entregar os pacotes.

Pipelines de pacote de barramento de mensagem

[0229] Referindo-se à Figura 32, em pelo menos algumas modalidades, a lateral de barramento de mensagem 850 da interface da fonte de pacote 862 e da interface de coletor de pacote 864 fornecem um recurso de pipeline de pacote. Quando um componente de software balanceador de carga 870 envia um pacote através da interface de coletor de pacotes 864, os dados de pacote podem atravessar uma série de etapas (pacote de pipeline 880) antes de chegar na camada de barramento de mensagem 850. Esses estágios podem modificar o pacote, remover o pacote, duplicar o pacote, atrasar o pacote, etc. Uma vez que um pacote percorre a pipeline de pacote 880 e a camada de barramento de mensagem 850 seleciona um componente de destino 870, uma segunda série de estágios de pipeline (pipeline de pacote 882) associada ao componente de destino 870 também pode ser percorrida antes do pacote ser adicionado à fila de entrada do componente de destino 870.

Ambientes de rede de provedor de exemplo

[0230] Essa seção descreve os ambientes de rede de provedor de exemplo nos quais as modalidades dos métodos e aparelhos de balanceamento de carga distribuída podem ser implementados. No entanto, esses ambientes de rede provedora de exemplo não são destinos a serem limitantes.

[0231] A Figura 33A ilustra um exemplo de ambiente de rede de provedor, de acordo com pelo menos algumas modalidades. A rede de provedor 1900 pode fornecer virtualização de recurso aos clientes através de um ou mais serviços de virtua- lização 1910 que permitem aos clientes acessar, comprar, aluar, ou de outra forma obter instâncias 1912 de recursos virtualizados, incluindo, mas não limitado a, recursos computacionais e de armazenamento, implementadas em dispositivos dentro da rede ou das redes de provedor em um ou mais data centers. Os endereços IP privados 1916 podem ser associados às instâncias de recursos 1912; os endereços IP privados são os endereços da rede interna das instâncias de recursos 1912 na rede de provedor 1900. Em algumas modalidades, a rede de provedor 1900 também poderá fornecer endereços IP públicos 1914 e/ou faixas de endereços IP públicos (por exemplo, endereços Internet Protocol version 4 (IPv4) ou Internet Protocol version 6 (IPv6)) que os clientes podem obter do provedor 1900.

[0232] Convencionalmente, a rede de provedor 1900, através dos serviços de virtualização 1910, pode permitir que um cliente do provedor de serviços (por exemplo, um cliente que opera a rede de cliente 1950A) para associar dinamicamente, pelo menos, alguns endereços IP públicos 1914 atribuídos ou alocados ao cliente com instâncias de recursos 1912 em particular atribuídas ao cliente. A rede de provedor 1900 também pode permitir que o cliente remapeie um endereço IP público 1914, previamente mapeado para uma instância de recurso de computação virtuali- zada 1912 alocada ao cliente, para outra instância de recurso de computação virtua- lizada 1912 que também é atribuída ao cliente. Usando as instâncias de recurso de computação virtualizada 1912 e endereços IP públicos 1914 fornecidos pelo provedor de serviço, um cliente do provedor de serviço, tal como o operador da rede de cliente 1950A pode, por exemplo, implementar aplicações específicas para cliente e apresentar as aplicações do cliente em uma rede intermediária 1940, como a Internet. Outras entidades de rede 1920 na rede intermédia 1940 pode, então, gerar tráfego para um endereço IP público de destino 1914 publicado pela rede de cliente 1950A; o tráfego é roteado ao data center de provedor de serviços, e no data center é roteado, através de um substrato de rede, para o endereço IP privado 1916 da instância de recurso de computação virtualizada 1912 atualmente mapeada para o endereço IP público de destino 1914. Da mesma forma, o tráfego de resposta da instância de recurso de computação virtualizada 1912 pode ser roteado através do substrato de rede de volta para a rede intermediária 1940 para a entidade de origem 1920.

[0233] Os endereços IP privados, conforme usados neste documento, se referem aos endereços da rede interna das instâncias de recursos em uma rede de provedor. Os endereços IP privados só são roteáveis dentro da rede de provedor. O tráfego de rede que se origina de fora da rede de provedor não é diretamente roteado aos endereços IP privados; em vez disso, o tráfego usa endereços IP públicos que são mapeados para as instâncias de recurso. A rede de provedor pode incluir os dispositivos ou aparelhos de rede que fornecem tradução de endereços de rede (NAT) ou uma funcionalidade semelhante para desempenhar o mapeamento de endereços IP públicos para endereços IP privados e vice-versa.

[0234] Os endereços IP públicos, conforme usado neste documento, são endereços de rede rotáveis de internet que são atribuídos a instâncias de recurso, ou através do provedor de serviço ou através do cliente. O tráfego roteado a um endereço IP público é traduzido, por exemplo, através de uma conversão de endereço de rede de 1:1 (NAT), e encaminhado ao respectivo endereço IP privado de uma instância de recurso.

[0235] Alguns endereços IP públicos podem ser atribuídos através da infraes- trutura de rede de provedor para instâncias de recurso específicas; esses endereços IP públicos podem ser referidos como endereços IP públicos padrões, ou simplesmente endereços IP padrões. Em pelo menos algumas modalidades, o mapeamento de um endereço IP padrão para um endereço IP privado de uma instância de recurso é a configuração de inicialização padrão para todos os tipos de instância de recurso.

[0236] Pelo menos alguns endereços IP públicos podem ser repartidos ou obtidos pelos clientes da rede de provedor 1900; então, um cliente pode atribuir seus endereços IP públicos alocados para instâncias de recursos específicos alocados ao cliente. Esses endereços IP públicos podem ser referidos como endereços IP públicos de cliente, ou simplesmente endereços IP de cliente. Em vez de ser atribuído pela rede de provedor 1900 às instâncias de recursos como no caso dos endereços IP padrão, os endereços IP cliente podem ser atribuídos às instâncias de recursos pelos clientes, por exemplo, através de um API fornecido pelo provedor de serviço. Ao contrário dos endereços IP padrões, os endereços IP de cliente são alocados às contas e podem ser remapeados para outras instâncias de recursos pelos respectivos clientes conforme necessário ou desejado. Um endereço IP do cliente é associado com a conta do cliente, não uma instância de recurso especial, e o cliente controla esse endereço IP até que o cliente escolha libera-lo. Ao contrário dos endereços IP estáticos convencionais, os endereços IP de cliente permitem que o cliente mascare as falhas de instância de recurso ou de zona de disponibilidade por meio do remapeamento dos endereços IP públicos do cliente a qualquer instância de recurso associada à conta do cliente. Os endereços IP de cliente, por exemplo, permitem que um cliente circunvenha problemas com instâncias de recurso do cliente ou software por meio do remapeamento de endereços IP de cliente para substituir instâncias de recurso.

[0237] A Figura 33B ilustra uma implementação do balanceador de carga distribuída em um exemplo de ambiente de rede do provedor, como mostrado na Figura 33A, de acordo com pelo menos algumas modalidades. Uma rede de provedor 1900 pode fornecer um serviço 1910 aos clientes 1960, por exemplo, um serviço de armazenamento virtualizado. Os clientes 1960 podem acessar o serviço 1910, por exemplo, através de um ou mais APIs para o serviço 1910, para se obter uso dos recursos (por exemplo, recursos de armazenamento ou recursos de computação) implementados em múltiplos nós de servidor 1990 em uma porção de rede de produção do provedor de rede 1900. Os nós do servidor 1990 podem, cada um, implementar um servidor (não mostrado), por exemplo, um servidor de web ou servidor de aplicativo, assim como um módulo de balanceador de carga local (BC) 1992. Um ou mais ba- lanceadores de carga distribuída 1980 podem ser implementados em uma camada de balanceador de carga entre a rede de fronteira e a rede de produção. O(s) rotea- dor(es) de fronteira 1970 podem receber pacotes (por exemplo, os pacotes de TCP) em fluxos de pacotes dos clientes 1960 através de uma rede intermediária 1940, como a Internet, e encaminhar os pacotes aos roteadores de borda do(s) balancea- dor(es) de carga distribuída 1980 através da rede de fronteira. Os pacotes podem ser direcionados ao(s) endereço(s) IP público(s) publicado(s) pelo roteador(es) de borda do(s) balanceador(es) de carga distribuída 1980. O roteador de borda de cada balanceador de carga distribuída 1980 pode distribuir os fluxos de pacote entre os nós do balanceador de carga do balanceador de carga distribuída respectivo 1980. Em pelo menos algumas modalidades, cada nó do balanceador de carga que serve como um nó de ingresso anuncia o mesmo endereço IP público ao roteador de borda, e o roteador de borda distribui os fluxos de pacote dos clientes 1960 entre os servidores de ingresso de acordo com uma técnica de roteamento múltiplas trajetórias em hash por fluxo, por exemplo, uma técnica de submeter a hash (ECMP) de múltiplas trajetórias de custo igual. Os nós do balanceador de carga podem usar o protocolo de conexão descrito neste documento para determinar os nós de servidor alvo 1990 para os fluxos de pacotes e para facilitar as conexões entre os servidores e os clientes 1960. Uma vez que uma conexão for estabelecida, os nós de ingresso encapsulam e enviam os pacotes recebidos para os fluxos aos nós de servidor alvo 1990 na rede de produção, enquanto os nós rastreadores de fluxo manterão o estado para as conexões. Os módulos balanceadores de carga 1992 nos nós de servidor 1990 podem tomar as decisões em relação a se os respectivos servidores nos nós de servidor 1960 aceitam as conexões. Os módulos balanceadores de carga recebem e desencapsula os pacotes dos nós de ingresso, e enviam os pacotes desen- capsulados (por exemplo, os pacotes de TCP) aos respectivos servidores nos nós de servidor 1990. Os módulos balanceadores de carga 1992 também pode selecionar nós do balanceador de carga como nós de egresso para os fluxos de pacotes, e encapsular e enviar pacotes de saída para os fluxos para os nós de egresso seleci-onados através da rede de produção. Os nós de egresso, por sua vez, desencapsu- lam os pacotes e enviam os pacotes desencapsulados na rede de fronteira para a entrega aos respectivos clientes 1960.

[0238] A Figura 34A ilustra um exemplo de implementação de rack físico do balanceador de carga distribuída e nós do servidor de acordo com pelo menos algumas modalidades, e não deve ser interpretada como limitante. Em pelo menos algumas modalidades, vários componentes do balanceador de carga distribuída podem ser implementados em ou como dispositivos de computação montados em rack.O rack 190 pode incluir múltiplos dispositivos de computação, cada um servindo como um nó do balanceador de carga (nós BC 110A-110F), e múltiplos dispositivos de computação, cada um servindo como um nó de servidor (nós de servidor 130A- 130L). O rack 190 também pode incluir pelo menos um roteador de borda 104, um ou mais dispositivos de rede montados em rack (roteadores, switches, etc.) que a formam a malha 120, e um ou mais outros componentes 180 (outros dispositivos de rede, painéis de patch, fontes de alimentação, sistemas de refrigeração, barramen- tos, etc.). A instalação de instalação 100, como um data center ou centers que implementam a rede de provedor de 1900 das Figuras 33A e 33B, pode incluir um ou mais racks 190.

[0239] A Figura 34b ilustra outro exemplo de implementação de rack físico do balanceador de carga distribuída e nós do servidor de acordo com pelo menos algumas modalidades, e não deve ser interpretada como limitante. A Figura 34B mostra os nós BC 110 e os nós de servidor 130 implementados como dispositivos de computação montado em slot, por exemplo, servidores blade, no rack 190.

[0240] A Figura 35 ilustra um exemplo ambiente de rede no qual um, dois ou mais balanceadores de carga distribuída podem ser implementados em uma rede, com os nós de servidor separadamente implementados, de acordo com pelo menos algumas modalidades. Nesse exemplo, dois balanceadores de carga distribuída 1980A e 1980B são mostrados. Os balanceadores de carga distribuída 1980 pode receber, cada um, fluxos de pacote do cliente 1960 através da rede de fronteira e desempenhar os métodos de balanceamento de carga descritos neste documento para distribuir os fluxos de pacote através de múltiplos nós de servidor 1990. Em algumas implementações, cada balanceador de carga distribuída 1980 pode ser uma aplicação em rack semelhantes aos racks 190 mostrados nas Figuras 34A e 34B, mas sem os nós de servidor instalados nos racks balanceadores de carga. Os nós de servidor 1990 podem ser dispositivos de computação montados em rack, tais como servidores blade instalados em um ou mais racks separados dentro do data center. Em algumas implementações, os nós de servidor 1990 podem implementar dois ou mais serviços diferentes prestados pelo provedor de rede, com cada serviço liderado por um ou mais dos balanceadores de carga 1980.

Sistema ilustrativo

[0241] Em pelo menos algumas modalidades, um servidor que implementa uma parte ou todos os métodos e aparelho de balanceamento de carga distribuída conforme descrito neste documento pode incluir um sistema de computador de uso geral que inclui ou está configurado para acessar um ou mais meios acessíveis por computador, tal como o sistema de computador 2000 ilustrado na Figura 36. Na modalidade ilustrada, o sistema de computador 2000 inclui um ou mais processadores 2010 acoplados a uma memória de sistema 2020 através de uma interface de entra- da/saída (I/O) 2030. O sistema computacional 2000 inclui ainda uma interface de rede 2040 acoplada à interface de I/O 2030.

[0242] Em várias modalidades, o sistema computacional 2000 pode ser um sistema de uniprocessador, incluindo um processador 2010, ou em um sistema de multiprocessadores, incluindo vários processadores 2010 (por exemplo, dois, quatro, oito, ou outro número adequado). Os processadores 2010 podem ser quaisquer processadores adequados capazes de executar instruções. Por exemplo, em várias modalidades, os processadores 2010 podem ser de uso geral ou processadores embutidos que implementam qualquer um de uma variedade de arquiteturas de conjunto de instruções (ISAs), tais como os ISAs x86, PowerPC, SPARC, ou MIPS, ou qualquer outro ISA adequado. Em sistemas com multiprocessadores, cada um dos processadores 2010 pode comumente, mas não necessariamente, implementar a mesma ISA.

[0243] A memória do sistema 2020 pode ser configurada para armazenar instruções e dados acessíveis pelo(s) processador(s) 2010. Em várias modalidades, a memória do sistema 2020 pode ser implementada usando qualquer tecnologia de memória adequada, tal como a memória estática de acesso aleatório (SRAM), RAM dinâmica síncrona (SDRAM), memória do tipo Flash/não volátil, ou qualquer outro tipo de memória. Na modalidade ilustrada, as instruções do programa e os dados que implementam uma ou mais funções desejadas, tais como esses métodos, técnicas e dados descritos acima para os métodos e aparelho de balanceamento de carga distribuída são mostradas armazenadas dentro da memória do sistema 2020 como o código 2024 e os dados 2026.

[0244] Em uma modalidade, a interface de I/O 2030 pode ser configurada para coordenar o tráfego de I/O entre o processador 2010, a memória do sistema 2020, e quaisquer dispositivos periféricos no dispositivo, incluindo a interface da rede 2040 ou outras interfaces periféricas. Em algumas modalidades, a interface de I/O 2030 pode executar qualquer protocolo necessário, cronometragem ou outras transformações de dados para converter sinais de dados de um componente (por exemplo, memória do sistema 2020) em um formato adequado para uso por outro componente (por exemplo, processador 2010). Em algumas modalidades, a interface de I/O 2030 pode incluir suporte para os dispositivos anexados através de vários tipos de barra- mentos periféricos, tais como uma variante do barramento de Interconexão de Componentes Periféricos (PCI) padrão ou o Barramento Serial Universal (USB) padrão, por exemplo. Em algumas modalidades, a função da interface de I/O 2030 pode ser dividida em dois ou mais componentes separados, tal como uma ponte norte e ponte sul, por exemplo. Além disso, em algumas modalidades, alguma ou toda a funcionalidade da interface de I/O 2030, tal como uma interface para a memória do sistema 2020, pode ser incorporada diretamente no processador 2010.

[0245] A interface de rede 2040 pode ser configurada para permitir que os dados sejam trocados entre o sistema computacional 2000 e outros dispositivos 2060 anexados a uma rede ou redes 2050, tais como sistemas ou dispositivos computaci- onais, conforme ilustrado nas Figuras 1 a 35, por exemplo. Em várias modalidades, a interface de rede 2040 pode suportar a comunicação através de quaisquer redes adequadas de dados gerais com fio ou sem fio, tais como os tipos de rede Ethernet, por exemplo. Adicionalmente, a interface da rede 2040 pode suportar a comunicação através das redes de telecomunicações/telefonia, tais como redes de voz analógicas ou redes de comunicações de fibra digital, através das redes de área de armazenamento, tais como Canal de Fibra SANs, ou através de qualquer outro tipo adequado de rede e/ou protocolo.

[0246] Em algumas modalidades, a memória de sistema 2020 pode ser uma modalidade de um meio acessível por computador configurado para armazenar as instruções de programa e os dados conforme descrito acima para as Figuras 1 até 35 para a implementação de modalidades de um sistema de balanceamento de carga distribuída. No entanto, em outras modalidades, as instruções e/ou dados do programa podem ser recebidos, enviados ou armazenados em diferentes tipos de meios acessíveis por computador. De forma geral, um meio acessível por computador pode incluir mídias de armazenamento não transitórias ou mídias de memória, tais como mídias magnéticas ou ópticas, por exemplo, disco ou DVD/CD acoplado ao sistema computacional 2000 através da interface de I/O 2030. Um meio de armazenamento acessível por computador não transitório pode incluir também quaisquer mídias voláteis ou não voláteis, tais como RAM (por exemplo, SDRAM, DDR SDRAM, RDRAM, SRAM, etc.), ROM, etc, que podem estar incluídas em algumas modalidades do sistema computacional 2000 como memória do sistema 2020 ou outro tipo de memória. Além disso, um meio acessível por computador pode incluir meios de transmissão ou sinais, tais como sinais elétricos, eletromagnéticos ou digitas, transportados através de um meio de comunicação, tal como uma rede e/ou um link sem fio, tal como pode ser implementado através da interface da rede 2040.

[0247] Modalidades da divulgação podem ser descritas tendo em conta as seguintes cláusulas: 1. Um sistema balanceador de carga distribuída, compreendendo: uma pluralidade de nós do balanceador de carga; e uma pluralidade de nós de servidor compreendendo, cada um, um servidor e um módulo balanceador de carga; em que a pluralidade de nós do balanceador de carga é configurada para distribuir os fluxos de pacotes a partir de um ou mais clientes entre a pluralidade de nós de servidor, em que, para distribuir os fluxos de pacote entre a pluralidade de nós de servidor, a pluralidade de nós do balanceador de carga é configurada para: selecionar nós de servidor dentre a pluralidade de nós de servidor para receber solicitações de conexão para os fluxos de pacote dos clientes; e enviar as solicitações de conexão para os nós de servidor selecionados; em que o módulo balanceador de carga em cada nó de servidor está configurado para: receber uma solicitação de conexão para um fluxo de pacote a partir de um dentre uma pluralidade de nós do balanceador de carga; determinar se a conexão deve ser aceita pelo servidor no nó de servidor; se o servidor não puder aceitar a conexão, rejeitar a solicitação de conexão; e se o servidor puder aceitar a ligação, cooperar com a pluralidade de nós do balanceador de carga para estabelecer uma conexão para o fluxo de pacote entre o cliente respectivo e o servidor respectivo. 2. O sistema de balanceador de carga distribuída conforme como descrito na cláusula 1, que compreende ainda um roteador configurado para distribuir os fluxos de pacote a partir de um ou mais clientes entre a pluralidade de nós do balance- ador de carga de acordo com uma técnica de roteamento de múltiplas trajetórias em hash. 3. O sistema de balanceador de carga distribuída conforme referido na cláusula 1, em que, para determinar se a conexão deve ser aceita pelo servidor no nó do servidor, o módulo de balanceador de carga será configurado para analisar uma ou mais métricas do servidor no nó de servidor para determinar se o servidor pode aceitar a ligação, em que uma ou mais métricas de uso de recurso atuais incluem um ou mais dentre a utilização de CPU, o consumo de largura de banda, a latência de servidor, e o número de conexões estabelecidas. 4. O sistema de balanceador de carga distribuída conforme descrito na cláusula 1, em que a pluralidade de nós do balanceador de carga está, ainda, configurada para selecionar os nós de servidor dentre a pluralidade de nós de servidor para receber as solicitações de conexão de acordo com uma técnica de seleção aleatória. 5. O sistema de balanceador de carga distribuída conforme referido na cláusula 1, em que a pluralidade de nós do balanceador de carga é, ainda, configurada para selecionar outro nó de servidor dentre a pluralidade de nós de servidor para receber solicitações de conexão rejeitadas e enviar a solicitação de conexão para o outro nó de servidor. 6. O sistema de balanceador de carga distribuída conforme referido na cláusula 1, em que cada fluxo de pacote é um fluxo de pacote de Protocolo de Controle de Transmissão (TCP) e em que cada conexão estabelecida entre um cliente e um servidor é uma conexão TCP. 7. O sistema de balanceador de carga distribuída conforme referido na cláusula 1, em que cada ligação estabelecida entre um cliente e um servidor se origina no cliente, passa através de um ou mais da pluralidade de nós do balanceador de carga, e é terminada pelo servidor. 8. Um método, que compreende: realizar, através de uma ou mais de uma pluralidade de nós do balanceador de carga: receber um pacote de um fluxo de pacote para um cliente; e enviar uma solicitação de conexão para o fluxo de pacote a um nó de servidor selecionado dentre uma pluralidade de nós de servidores; realizar, através do nó de servidor selecionado: determinar se um servidor no nó de servidor pode ou não aceitar a conexão; rejeitar a solicitação de conexão mediante determinação de que o servidor não pode aceitar a conexão; e aceitar a solicitação de conexão mediante determinação de que o servidor pode aceitar a conexão. 9. O método conforme é referido na cláusula 8, em que a referida aceitação da solicitação de ligação compreende o nó do servidor selecionado cooperando com os um ou mais nós do balanceador de carga para estabelecer uma ligação entre o respectivo cliente e o respectivo servidor para o fluxo de pacote. 10. O método conforme referido na clausula 9, em que o fluxo de pacote é um fluxo de pacote de Protocolo de Controle de Transmissão (TCP) e em que a conexão estabelecida entre o cliente e o servidor é uma conexão TCP. 11. O método tal como é referido na cláusula 9, em que a conexão estabelecida se origina no cliente, passa através de uma dentre a pluralidade de nós do balanceador de carga, e é terminada pelo servidor. 12. O método conforme referido na cláusula 8, em que o pacote é recebido a partir de um roteador que distribui fluxos de pacote a partir de um ou mais clientes entre a pluralidade de nós do balanceador de carga de acordo com uma técnica de roteamento múltiplas trajetórias em hash. 13. O método conforme referido na cláusula 8, em que a referida determinação se um servidor no nó de servidor pode ou não pode aceitar a conexão compreende a análise de uma ou mais métricas de uso de recurso atuais do servidor para determinar se o servidor pode aceitar a conexão. 14. O método conforme referido na cláusula 8, compreendendo ainda os nós do balanceador de carga que selecionam um ou mais nós de servidor dentre a pluralidade de nós de servidor de acordo com uma técnica de seleção aleatória. 15. O método conforme referido na cláusula 8, que compreende, ainda, se o nó de servidor selecionado rejeita a solicitação de conexão, os um ou mais nós do balanceador de carga enviando a solicitação de conexão para um outro nó de servidor selecionado de entre a pluralidade de nós de servidor. 16. Um meio de armazenamento acessível por computador não transitório armazena as instruções de programa executáveis por computador para implementar um módulo de balanceador de carga em cada uma dentre uma pluralidade de nós de servidor, cada módulo de balanceador de carga operável para: receber, a partir de um dentre uma pluralidade de nós do balanceador de carga, uma solicitação de conexão para um fluxo de pacote a partir de um cliente; determinar se um servidor no nó de servidor pode ou não aceitar a conexão; rejeitar a solicitação de conexão mediante determinação de que o servidor não pode aceitar a conexão; e comunicar com o nó do balanceador de carga e com o servidor para estabelecer uma conexão entre o cliente e o servidor para o fluxo de pacote mediante a determinação de que o servidor pode aceitar a conexão. 17. O meio de armazenamento acessível por computador não transitório conforme referido na cláusula 16, em que, para determinar se um servidor no nó do servidor pode ou não aceitar a conexão, o módulo de balanceador de carga é operá- vel para analisar uma ou mais métricas de uso de recurso atuais do servidor para determinar se o servidor pode aceitar a conexão. 18. O suporte de armazenamento acessível por computador não transitório conforme referido na cláusula 17, em que uma ou mais métricas de uso de recursos atuais incluem um ou mais dentre utilização da CPU, o consumo de largura de ban- da, a latência de servidor e o número de conexões estabelecidas. 19. O meio de armazenamento acessível por computador não transitório conforme referido na cláusula 16, em que as instruções do programa são, ainda, executáveis por computador para implementar o nó do balanceador de carga selecionado aleatoriamente o nó de servidor dentre a pluralidade de nós de servidor para receber a solicitação de conexão. 20. O meio de armazenamento computador por acessível não transitório conforme referido na cláusula 16, em que, para rejeitar a solicitação de conexão, o módulo de balanceador de carga é operável para diminuir um contador de tempo de vida (VU) na solicitação de conexão e retornar à solicitação de conexão ao nó do balanceador de carga, em que as instruções de programa são, ainda, executáveis por computador para implementar o nó do balanceador de carga: verificar o contador de VU na solicitação de conexão retornada; se o contador de VU estiver acima de um limite, selecionar outro nó de servidor dentre a pluralidade de nós de servidor para receber a solicitação de conexão; e se o contador de VU for igual ou inferior ao limite, remover a solicitação de conexão.

Conclusão

[0248] Várias modalidades podem incluir ainda receber, enviar ou armazenar instruções e/ou dados implementados, de acordo com a descrição acima sobre um meio acessível por computador. De forma geral, um meio acessível por computador pode incluir mídias de armazenamento ou mídias de memória, tais como mídias magnéticas ou ópticas, por exemplo, disco ou DVD/CD-ROM, mídias voláteis ou não voláteis, tais como RAM (por exemplo, SDRAM, DDR, RDRAM, SRAM, etc.), ROM, etc., bem como mídias de transmissão ou sinais, tais como sinais elétricos, eletromagnéticos ou digitas, transmitidos através de um meio de comunicação, tal como uma rede e/ou um link sem fio.

[0249] Os diversos métodos, conforme ilustrado nas Figuras e descritos neste documento, representam modalidades exemplares dos métodos. Os métodos podem ser implementados em software, hardware ou uma combinação dos mesmos. A ordem do método pode ser mudada, e vários elementos podem ser adicionados, reordenados, combinados, omitidos, modificados, etc.

[0250] Várias modificações e alterações podem ser feitas, como estaria óbvio para uma pessoa versada na técnica tendo o benefício desta divulgação. Destina-se a abranger todas essas modificações e alterações e, por conseguinte, a descrição acima como sendo consideradas ilustrativas, em vez de uma forma restritiva.

Claims (11)

1. Sistema de balanceamento de carga distribuída, CARACTERIZADO pelo fato de que compreende: uma pluralidade de nós de balanceamento de carga (110A-110n); e uma pluralidade de nós de servidor (130A-130m), cada um compreendendo um servidor e um módulo de balanceamento de carga; em que a pluralidade de nós de balanceamento de carga é configurada para distribuir fluxos de pacote a partir de um ou mais clientes (160) dentre a pluralidade de nós de servidor, em que, para distribuir os fluxos de pacote dentre a pluralidade de nós de servidor, a pluralidade de nós de balanceamento de carga é configurada para: selecionar nós de servidor dentre a pluralidade de nós de servidor para receber solicitações de conexão para os fluxos de pacote a partir dos clientes; e enviar as solicitações de conexão para os nós de servidor selecionados; em que o módulo de balanceamento de carga em cada nó de servidor é configurado para: receber uma solicitação de conexão para um fluxo de pacote a partir de uma dentre a pluralidade de nós de balanceamento de carga; determinar se a conexão deve ser aceita pelo servidor no nó de servidor; se o servidor não pode aceitar a conexão, rejeitar a solicitação de conexão; se o servidor pode aceitar a conexão, cooperar com a pluralidade de nós de balanceamento de carga para estabelecer uma conexão para o fluxo de pacote entre o respectivo cliente e o respectivo servidor, selecionar um dentre a pluralidade de nós de balanceamento de carga para atuar como um servidor de egresso para receber e encaminhar o tráfego de saída do nó de servidor para o respectivo fluxo de pacote de saída da conexão, em que a seleção é baseada em um identificador para o fluxo de pacote entre o cliente e o servidor; e Interceptação dos pacotes IP de saída na conexão, encapsulamento dos pacotes IP de saída, e envio dos pacotes IP para o servidor de egresso selecionado.

2. Sistema de balanceamento de carga distribuída, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que compreende, adicionalmente, um roteador configurado para distribuir os fluxos de pacote a partir de um ou mais clientes dentre a pluralidade de nós de balanceamento de carga de acordo com uma técnica de roteamento de multicaminho verificado por hash.

3. Sistema de balanceamento de carga distribuída, de acordo com a reivindicação 1 ou 2, CARACTERIZADO pelo fato de que, para determinar se a conexão deve ser aceita pelo servidor no nó de servidor, o módulo de balanceamento de carga é configurado para analisar uma ou mais métricas de uso de recurso atual do servidor no nó de servidor para determinar se o servidor pode aceitar a conexão, em que a uma ou mais métricas de uso de recurso atual incluam um ou mais dentre utilização de CPU, consumo de largura de banda, latência de servidor e número de conexões estabelecidas.

4. Sistema de balanceamento de carga distribuída, de acordo com qualquer uma das reivindicações 1 a 3, CARACTERIZADO pelo fato de que a pluralidade de nós do balanceamento de carga é, adicionalmente, configurada para selecionar outro nó de servidor dentre a pluralidade de nós de servidor para receber uma solicitação de conexão rejeitada e enviar a solicitação de conexão ao outro nó de servidor.

5. Sistema de balanceamento de carga distribuída, de acordo com qualquer uma das reivindicações 1 a 3, CARACTERIZADO pelo fato de que para rejeitar a solicitação de conexão, o módulo do balanceamento de carga é configurado para diminuir um contador de tempo de vida (TTL) na solicitação de conexão e retornar a solicitação de conexão ao nó de balanceamento de carga, em que o nó de balanceamento de carga é configurado para: verificar o contador de TTL na solicitação de conexão retornada; se o contador de TTL estiver acima de um limite, selecionar outro nó de servidor dentre a pluralidade de nós de servidor para receber a solicitação de conexão; e se o contador de TTL for igual ou inferior ao limite, liberar a solicitação de conexão.

6. Sistema de balanceamento de carga distribuída, de acordo com qualquer uma das reivindicações 1 a 5, CARACTERIZADO pelo fato de que cada conexão estabelecida entre um cliente e um servidor se origina no cliente, passa através de um ou mais dentre a pluralidade de nós de balanceamento de carga e é encerrada pelo servidor.

7. Método, CARACTERIZADO pelo fato de que compreende: executar, por um ou mais dentre uma pluralidade de nós de balanceamento de carga: receber um pacote em um fluxo de pacote para um cliente; e enviar uma solicitação de conexão para o fluxo de pacote para um nó de servidor selecionado dentre uma pluralidade de nós de servidor; executar, pelo nó de servidor selecionado: determinar se um servidor no nó de servidor pode ou não aceitar a conexão; rejeitar a solicitação de conexão ao determinar que o servidor não pode aceitar a conexão; aceitar a solicitação de conexão ao determinar que o servidor pode aceitar a conexão, em que a dita aceitação da solicitação de conexão compreende o nó de servidor selecionado cooperando com um ou mais nós de balanceamento de carga para estabelecer uma conexão entre o respectivo cliente e o respectivo servidor para o fluxo de pacote; selecionar um dentre a pluralidade de nós de balanceamento de carga para atuar como um servidor de egresso para receber e encaminhar o tráfego de saída do nó de servidor para o respectivo fluxo de pacote de saída da conexão, em que a seleção é baseada em um identificador para o fluxo de pacote entre o cliente e o servidor; e Interceptação dos pacotes IP de saída na conexão, encapsulamento dos pacotes IP de saída, e envio dos pacotes IP para o servidor de egresso selecionado.

8. Método, de acordo com a reivindicação 7, CARACTERIZADO pelo fato de que a conexão estabelecida se origina no cliente, passa através de um ou mais dentre a pluralidade de nós de balanceamento de carga e é encerrada pelo servidor.

9. Método, de acordo com a reivindicação 7 ou 8, CARACTERIZADO pelo fato de que o pacote é recebido a partir de um roteador que distribui fluxos de pacote a partir de um ou mais clientes entre a pluralidade de nós de balanceamento de carga de acordo com uma técnica de roteamento de multicaminho verificado por hash.

10. Método, de acordo com qualquer uma das reivindicações 7 a 9, CARACTERIZADO pelo fato de que a dita determinação de se um servidor no nó de servidor pode ou não aceitar a conexão compreende analisar uma ou mais métricas de uso de recurso atual do servidor para determinar se o servidor pode aceitar a conexão.

11. Método, de acordo com qualquer uma das reivindicações 7 a 10, CARACTERIZADO pelo fato de que compreende, adicionalmente, se o nó de servidor selecionado rejeita a solicitação de conexão, o um ou mais nós de balanceamento de carga enviando a solicitação de conexão para outro nó de servidor selecionado dentre a pluralidade de nós de servidor.

Images