Filosofia de engenharia: Radia Perlman

Principais conclusões

• Ela inventou o Spanning Tree Protocol, que fez o Ethernet comutado funcionar em escala. Enquanto trabalhava na Digital Equipment Corporation, Radia Perlman projetou o algoritmo de spanning tree – publicado em 1985 e padronizado como IEEE 802.1D – que permite às bridges de uma rede de topologia arbitrária calcularem, por conta própria, um único caminho livre de loops até cada destino, enquanto se curam discretamente contornando as falhas. Sem ele, links redundantes criam loops, e um único broadcast circula para sempre e derrete a rede.¹²³
• O compromisso que a define é a robustez: redes que permanecem corretas sob falha, inclusive falha maliciosa. Sua tese de doutorado no MIT, de 1988, chamava-se “Network Layer Protocols with Byzantine Robustness” – roteamento projetado para continuar funcionando não apenas quando os links morrem, mas quando os nós ativamente mentem. Projetar para o caso de falha, inclusive o adversarial, perpassa tudo o que ela construiu.¹
• Ela escreveu o livro-texto canônico e um poema dentro de uma patente. Perlman é autora de Interconnections: Bridges, Routers, Switches, and Internetworking Protocols, o livro com o qual uma geração de engenheiros de rede aprendeu, e coautora de Network Security: Private Communication in a Public World. Ela também escreveu “Algorhyme” – “I think that I shall never see / A graph more lovely than a tree” – para descrever a spanning tree, possivelmente a única patente de software registrada que contém um poema.³⁴⁷
• Ela detém mais de 100 patentes e está no National Inventors Hall of Fame – e não gosta de “Mãe da Internet”. Incluída no Internet Hall of Fame (2014) e no National Inventors Hall of Fame (2016), com mais de 100 patentes concedidas, Perlman passou décadas rejeitando o rótulo de “Mãe da Internet”, insistindo que ninguém sozinho inventou a Internet.¹⁵

O princípio

“I think that I shall never see / A graph more lovely than a tree. / A tree whose crucial property / Is loop-free connectivity.” – Radia Perlman, “Algorhyme,” o poema que descreve o Spanning Tree Protocol⁴

A maior parte da engenharia otimiza para o caso em que tudo funciona. Você projeta o caminho feliz, trata alguns erros que consegue imaginar e publica. As redes não concedem esse conforto. Uma rede é uma malha viva de máquinas que falham aleatoriamente, links que apagam no meio de um pacote e – se você tiver azar – nós que foram tomados e agora estão lhe alimentando mentiras. Toda a obra de Perlman parte da premissa oposta à da maior parte do código: o caso de falha não é um caso extremo, é o centro do projeto. Um protocolo justifica sua existência não por funcionar quando os fios estão limpos, mas por permanecer correto quando não estão – voltando sozinho, de forma autoestabilizável, a um bom estado, sem nenhum humano no circuito.¹³

O Spanning Tree Protocol é o princípio em sua forma mais pura. O problema que ele resolve é brutal e estrutural: se você conecta switches entre si com links redundantes – o que é obrigatório, para confiabilidade – você cria loops físicos, e um único quadro de broadcast circulará um loop para sempre, multiplicando-se a cada ramificação até saturar todos os links e a rede morrer. A correção ingênua é proibir loops, mas então você proibiu a redundância, e um único cabo cortado derruba metade do prédio. O insight de Perlman foi que dá para ter os dois: deixe os operadores conectarem a malha que quiserem, e faça com que os próprios switches calculem uma única árvore livre de loops que ainda assim alcança todo mundo, mantendo os links redundantes em reserva.²³ Sem controlador central, sem nenhum humano desenhando a árvore à mão – um algoritmo totalmente distribuído que converge sozinho e volta a convergir quando algo quebra.

Há uma segunda metade no princípio, e é a que dá profundidade à primeira: a robustez precisa se estender à malícia, não apenas ao acidente. Um nó que falhou simplesmente para; um nó comprometido continua falando, e o que ele diz foi projetado para machucar você. O trabalho de doutorado de Perlman fez a pergunta mais difícil – um protocolo de roteamento consegue continuar entregando pacotes corretamente mesmo quando alguns dos roteadores estão ativamente sabotando-o? – e respondeu-a com protocolos dotados de robustez bizantina.¹ A disciplina é a mesma que vai da spanning tree ao seu trabalho de segurança: pressuponha o pior do mundo em que seu protocolo vive, e projete de modo que ele se cure mesmo assim. E, ao longo de tudo, a estética é a simplicidade. Um protocolo simples é um protocolo sobre o qual você consegue raciocinar, provar coisas e confiar que vai convergir – e é por isso que a spanning tree cabe num poema.

Contexto

Radia Perlman nasceu em 18 de dezembro de 1951, em Portsmouth, Virgínia.¹ Ela estudou no MIT, onde obteve um bacharelado (SB) e um mestrado (SM) em matemática, e mais tarde um doutorado em ciência da computação, em 1988; sua tese chamava-se “Network Layer Protocols with Byzantine Robustness” – roteamento projetado para sobreviver a roteadores que se tornaram maliciosos.¹ O tema dessa tese não é uma nota de rodapé na carreira dela; é a declaração de propósito da carreira dela, escrita logo no começo.

Antes dos protocolos pelos quais é famosa, ela fez algo discretamente radical no Laboratório de Inteligência Artificial do MIT: no início dos anos 1970, desenvolveu o TORTIS – o “Toddler’s Own Recursive Turtle Interpreter System” – uma versão do ambiente da tartaruga LOGO simples o bastante para que crianças com até três anos e meio conseguissem programar um robô.¹ O fio condutor com o trabalho posterior é real. Ensinar uma criancinha a programar é um exercício de simplificação radical: reduzir uma ideia até que ela sobreviva ao contato com alguém que não tem conhecimento prévio nenhum. Ela passaria o resto da carreira reduzindo protocolos de rede ao mesmo tipo de núcleo essencial e compreensível.

Sua trajetória profissional passa pelas instituições que construíram a rede moderna. Ela trabalhou na BBN depois do MIT, depois entrou na Digital Equipment Corporation por volta de 1980, e foi na DEC – não num silo de pesquisa, mas resolvendo um problema real de produto – que inventou o algoritmo de spanning tree, projetou o roteamento do DECnet e fez trabalho fundamental ao mover o roteamento de abordagens distance-vector para link-state, inclusive o IS-IS.¹³ Depois da DEC, trabalhou na Novell, depois na Sun Microsystems (onde foi Sun Fellow e obteve mais de 40 de suas patentes), e mais tarde na Intel e na Dell EMC.¹ Ao longo do caminho, ela acumulou mais de 100 patentes concedidas, a inclusão no Internet Hall of Fame (2014) e no National Inventors Hall of Fame (2016), e um rótulo que passou anos rejeitando – “Mãe da Internet” – sob o argumento de que nenhuma pessoa sozinha inventou a Internet e de que o título marcado por gênero obscurece mais do que honra.¹⁵

O trabalho

O Spanning Tree Protocol: uma árvore que a própria rede faz crescer

Comece por aqui, porque é o princípio transformado em mecanismo. O cenário é uma LAN estendida – muitos segmentos costurados entre si por bridges (o que hoje chamamos de switches) – conectados com links redundantes para que nenhuma falha isolada possa particionar a rede. A redundância é inegociável para a confiabilidade. Mas redundância significa loops, e loops são fatais: os quadros Ethernet não carregam campo de time-to-live, então um quadro de broadcast que entra num loop é copiado em torno dele indefinidamente, e como os switches inundam os broadcasts por todas as portas, as cópias se multiplicam até consumirem toda a largura de banda disponível. A rede não fica lenta; ela morre. Isso é a tempestade de broadcast, e “a função básica do STP é evitar loops de bridge e a radiação de broadcast que resulta deles.”²

O algoritmo de Perlman, de 1985, resolve isso com uma computação distribuída que não precisa de autoridade central.³ Primeiro, as bridges elegem uma raiz – ganha a de menor identificador, decidido pela troca de pequenas mensagens, sem nenhum humano escolhendo.² Depois cada bridge calcula seu caminho de menor custo em direção à raiz e mantém ativo para encaminhamento apenas esse link, bloqueando os links redundantes.² O que resta é uma spanning tree: um único caminho livre de loops de cada segmento até a raiz e, portanto, entre quaisquer dois pontos, que ainda assim alcança cada LAN – exatamente a “loop-free connectivity” que o poema nomeia.⁴ Os links bloqueados não são desperdiçados; ficam em reserva. Quando um link ativo falha, as bridges detectam a mudança e o algoritmo calcula uma nova árvore de menor custo, promovendo um link em espera para restaurar a conectividade.² Essa é a autocura – automática, distribuída, sem nenhum operador tocar em nada.

Por que isso importa como engenharia: a spanning tree é um algoritmo distribuído autoestabilizável que o operador pode ignorar. Você pluga os cabos, adiciona redundância por segurança, e a rede se organiza sozinha – e volta a se organizar quando algo quebra. O IEEE padronizou o algoritmo como 802.1D em 1990, e por décadas ele rodou dentro de essencialmente todo switch Ethernet gerenciável vendido.² É também um modelo de compreensibilidade: a coisa toda cabe num poema de doze versos porque a ideia por baixo é genuinamente simples, e simples é o que permite que você confie que ela converge.⁴

Roteamento link-state, IS-IS e Interconnections

A spanning tree governa o bridging dentro de uma LAN estendida; o roteamento entre redes é o problema maior, e Perlman também moldou isso. Na DEC, ela ajudou a afastar o roteamento dos protocolos distance-vector – nos quais cada roteador conhece apenas o custo até cada destino conforme relatado pelos seus vizinhos, um design propenso à convergência lenta e ao “contar até o infinito” – em direção ao roteamento link-state, no qual cada roteador aprende a topologia completa e calcula os próprios caminhos mais curtos.¹ Seu trabalho no IS-IS (Intermediate System to Intermediate System), o protocolo link-state que se tornou a contraparte OSI do OSPF, é parte da razão pela qual o roteamento link-state é robusto e rápido para convergir; ele é construído para inundar mudanças de topologia de forma confiável e recalcular caminhos, que é o mesmo instinto de autocura da spanning tree, uma camada acima.¹

Ela também escreveu o livro – literalmente. Interconnections: Bridges, Routers, Switches, and Internetworking Protocols é o texto com o qual uma geração de engenheiros de rede aprendeu a área, e Network Security: Private Communication in a Public World (com Charlie Kaufman e Mike Speciner) tornou-se referência padrão.⁷ O que distingue a escrita dela é a mesma coisa que distingue seus protocolos: a insistência em explicar por que um design é como é, não apenas o que ele faz – ensinando o leitor a raciocinar sobre correção e falha, não a decorar uma especificação.

Projetar contra a malícia: roteamento com robustez bizantina e dados que expiram

Este é o trabalho que mais a revela. Uma rede que se cura contornando nós quebrados já é difícil o bastante; sua pesquisa de doutorado, “Network Layer Protocols with Byzantine Robustness,” perguntou se o roteamento consegue continuar entregando pacotes corretamente mesmo quando alguns roteadores foram tomados e estão fazendo tudo ao seu alcance para atrapalhar – descartando pacotes, mentindo sobre a topologia, forjando mensagens de roteamento.¹ Um nó que falhou é silencioso e previsível; um nó bizantino é barulhento e adversarial, e o protocolo tem que entregar mesmo assim. Tratar a falha maliciosa como um caso de primeira classe a ser projetado – não como um complemento de segurança parafusado depois – está décadas à frente da forma como a maioria dos sistemas foi construída, e descende diretamente do mesmo instinto da spanning tree: pressuponha que o mundo é hostil e convirja para o correto de qualquer forma.¹

Esse instinto se prolongou no seu trabalho de segurança posterior. Ela contribuiu para modelos de confiança em infraestrutura de chave pública e – uma ideia caracteristicamente limpa – para mecanismos de dados que expiram: gerenciamento de chaves efêmeras projetado para que a informação possa se tornar, de forma confiável, irrecuperável depois de um tempo escolhido, a garantia de que dados apagados realmente sumiram. É a mentalidade do caso de falha voltada para a privacidade.¹ A maioria dos sistemas é construída para lembrar; ela perguntou como se constrói um sistema em que se pode confiar que vai esquecer, que é o problema mais difícil e mais adversarial.

TRILL e a disciplina da simplicidade

Perlman também foi sua crítica mais aguçada, e é por isso que projetou a sucessora da spanning tree. A grande limitação do STP é o reverso de sua virtude: para matar loops, ele bloqueia links redundantes, o que significa que largura de banda fica ociosa, e o tráfego entre dois switches próximos pode ser forçado a um longo desvio pela raiz.⁶ O TRILL – “Transparent Interconnection of Lots of Links” – é sua resposta, e é a síntese de toda a sua carreira: é “a aplicação do roteamento link-state ao problema do customer-bridging com reconhecimento de VLAN.”⁶ Os switches TRILL, chamados RBridges, rodam o protocolo link-state IS-IS entre si para aprender a topologia completa e calcular os caminhos mais curtos, de modo que o TRILL “estabelece caminhos por todos os links ativos” em vez de bloqueá-los – a resiliência e a simplicidade do bridging plug-and-play, com a eficiência de caminho do roteamento.⁶ É o trabalho de link-state e o trabalho de spanning tree dobrados num só design.

Ao longo de tudo isso, perpassa um compromisso com a simplicidade que é fácil subestimar. A spanning tree é famosa em parte por ser pequena o bastante para caber num poema; seus livros-texto são amados porque explicam em vez de enumerar; sua queixa permanente sobre boa parte das redes é que elas são mais complexas do que precisam ser. A simplicidade, para Perlman, não é preferência estética – é o que torna um protocolo comprovadamente correto e confiavelmente autoestabilizável. Você não pode confiar que um mecanismo se cura sozinho se não consegue raciocinar sobre ele, e não consegue raciocinar sobre o que não cabe na sua cabeça.⁴⁶

O método

Leia transversalmente a spanning tree, o IS-IS, a tese de robustez bizantina, o trabalho de segurança e o TRILL, e os mesmos compromissos se repetem. O método de Perlman é menos um slogan do que um conjunto de hábitos permanentes.

Projete primeiro para o caso de falha. A spanning tree não é um algoritmo de encaminhamento com tratamento de falha acrescentado; a falha é o problema que ela existe para resolver – links redundantes que precisam coexistir com a ausência de loops, e links ativos que vão morrer e precisam ser contornados.²³ A lição transcende em muito as redes: não projete o caminho feliz e remende o tratamento de erro, projete primeiro os modos de falha e deixe o caminho feliz cair de um sistema que já sobrevive a eles. É a barreira de evidências aplicada à robustez – “funciona quando nada está quebrado” não é evidência; “converge para o correto quando os links falham” é.

Pressuponha a malícia, não apenas o acidente. As falhas mais difíceis não são as silenciosas; são os nós que foram comprometidos e agora estão mentindo. A tese de robustez bizantina de Perlman trata o adversário como entrada de projeto, não como pensamento tardio.¹ É o mesmo instinto sobre o qual Adi Shamir construiu uma carreira criptográfica – você não entende um sistema enquanto não perguntou o que um atacante que controla parte dele consegue fazer – e é por isso que uma fronteira de permissão ou um protocolo de roteamento precisa ser projetado contra o participante que está ativamente tentando quebrá-lo.

Faça-o autoestabilizável – sem nenhum humano no circuito. A virtude mais profunda da spanning tree é que o operador pode ignorá-la: ela converge sozinha e volta a convergir depois de uma falha sem ninguém desenhar a árvore.² A disciplina é empurrar a recuperação para dentro do sistema, em vez de para dentro de um manual de operação, porque uma rede que precisa de um humano para se curar não se cura às 3 da manhã. É o mesmo impulso de correção distribuída que Leslie Lamport trouxe ao consenso: defina o bom estado com precisão e então construa um protocolo que retorne a ele a partir de qualquer ponto de partida.

Mantenha-o simples o bastante para raciocinar sobre ele – e para ensinar. Um protocolo que cabe num poema é um protocolo que você consegue provar que converge; um livro-texto que explica por que torna a próxima geração capaz de raciocinar em vez de decorar.⁴⁷ A simplicidade aqui não é minimalismo por si só – é a precondição para a confiança, a mesma economia de meios que faz os mecanismos mais fortes serem também os mais compreensíveis, no espírito do produto minimamente digno.

Seja seu próprio revisor mais severo. O STP funciona, e ainda assim Perlman projetou o TRILL para corrigir o desperdício de links bloqueados do STP com as ideias de link-state em que passara uma carreira.⁶ O hábito permanente é continuar atacando o próprio melhor trabalho – nomear a limitação daquilo pelo qual você é famoso e construir sua sucessora – que é a ideia de qualidade é a única variável transformada em prática: a pergunta nunca é “isto está bom o bastante para publicar?”, mas “este ainda é o design certo?”.

Cadeia de influência

Quem a moldou

A tradição de matemática e IA do MIT. Dois diplomas em matemática e um doutorado no MIT, além do trabalho inicial no AI Lab nos sistemas da tartaruga LOGO, deram-lhe tanto o rigor para provar um protocolo correto quanto o instinto de tornar ideias radicalmente simples.¹ Ensinar uma criança de três anos a programar é a mesma habilidade de fazer uma spanning tree caber num poema. (Influência formativa)

A comunidade inicial de internetworking. Seus anos na BBN e na DEC a colocaram dentro das instituições que de fato construíam as redes de longa distância e locais nos anos 1970 e 1980, onde os problemas não eram acadêmicos – loops de fato derretiam redes reais – e o trabalho em DECnet, IS-IS e bridging surgiu de resolvê-los.¹ (Influência direta)

A tradição de falhas bizantinas. Seu foco doutoral em protocolos robustos contra falha maliciosa a conecta à linhagem do pensamento em sistemas distribuídos – formalizada por Leslie Lamport e outros – que pergunta como um sistema permanece correto quando alguns participantes se comportam de forma arbitrária, até adversarial.¹ (Influência formativa)

Quem ela moldou

Todo Ethernet comutado. O Spanning Tree Protocol, padronizado como IEEE 802.1D, rodou dentro de essencialmente todo switch gerenciável por décadas – a razão silenciosa pela qual plugar cabos redundantes numa rede corporativa não a derruba.²³

As malhas modernas de data center. O TRILL e suas ideias de bridging por link-state empurraram a área em direção a malhas que usam todos os seus links via roteamento de caminho mais curto, em vez de bloquear a redundância, moldando a forma como grandes redes de data center são construídas.⁶

Uma geração de engenheiros de rede. Por meio de Interconnections e Network Security, Perlman ensinou a área a raciocinar sobre bridges, roteadores e protocolos – seu estilo explicativo é parte da razão pela qual tantos profissionais pensam sobre redes da forma como pensam.⁷

O fio condutor

Perlman é a pedra angular da resiliência da própria rede nesta série – a figura que fez os fios por baixo de tudo o mais se curarem sozinhos. Leslie Lamport construiu a teoria dos sistemas distribuídos que permanecem corretos sob falha, inclusive falhas bizantinas em que os nós se comportam de forma arbitrária; Perlman construiu os protocolos que fazem exatamente isso em redes reais, e sua tese de robustez bizantina é a pergunta de Lamport respondida na camada de roteamento.¹ Adi Shamir tornou os sistemas confiáveis projetando contra o atacante que controla parte deles – o mesmo instinto adversarial que Perlman trouxe ao roteamento, uma década na sua própria direção. E Tim Berners-Lee construiu uma web para todos, mas uma web só alcança todos porque a rede comutada e roteada por baixo dela permanece conectada apesar das falhas – ou seja, por causa da spanning tree e do roteamento link-state que Perlman moldou. Onde Lamport diz defina a correção e prove que ela sobrevive à falha e Shamir diz projete contra o adversário, Perlman diz: construa a rede de modo que ela se cure sozinha – sem nenhum humano no circuito, mesmo quando alguns dos nós estão mentindo. (Ponte da série)

O que eu tiro disto

A lição que guardo de Perlman é projetar primeiro para o caso de falha. Meu instinto, como o da maioria dos construtores, é escrever o caminho feliz – a requisição que dá certo, o link que se mantém de pé, o nó que se comporta – e depois salpicar tratamento de erro assim que funciona. A spanning tree é a repreensão: a falha não é algo que acontece com o design, é aquilo para o qual o design existe. Links redundantes e cabos morrendo não são casos extremos a serem remendados; são a razão inteira pela qual o protocolo tem a forma que tem, e o caminho feliz simplesmente cai de um sistema que já sobrevive a eles. Então, quando construo algo agora – um loop de sincronização, um caminho de retry, uma fronteira de permissão – tento partir de “o que quebra, e como isto se cura sem mim?”, em vez de chegar a isso por último. Um sistema que precisa de mim acordado às 3 da manhã para se recuperar é um sistema que não terminei de projetar.

A segunda lição é que a simplicidade é o que torna a robustez confiável. É tentador tratar a elegância da spanning tree – pequena o bastante para caber num poema – como um detalhe biográfico charmoso. Não é; é o ponto. Você não pode confiar que um mecanismo se cura sozinho se não consegue raciocinar sobre se ele converge, e não consegue raciocinar sobre o que não cabe na sua cabeça. Os protocolos de Perlman são robustos porque são simples, e seus livros-texto perduram porque ensinam o porquê, não a especificação. Isso reformulou a simplicidade, para mim, de um item desejável para uma propriedade estrutural da correção. Quando um design fica complicado o bastante para que eu não consiga mais me convencer de que ele se recupera de toda falha, a complexidade não é sofisticação – é o bug que eu ainda não encontrei.

Perguntas frequentes

O que é o Spanning Tree Protocol?

O Spanning Tree Protocol (STP) é um protocolo de rede, inventado por Radia Perlman em 1985 na Digital Equipment Corporation e padronizado como IEEE 802.1D, que evita loops em redes Ethernet com bridges ou switches dotadas de links redundantes.²³ Sem ele, conexões redundantes criam loops, e como os quadros Ethernet não têm time-to-live, um broadcast circula um loop para sempre e se multiplica numa tempestade de broadcast que satura a rede. O STP corrige isso automaticamente: os switches elegem uma raiz, cada switch mantém para encaminhamento apenas seu melhor caminho em direção à raiz e bloqueia os links redundantes, deixando uma única árvore livre de loops que ainda assim alcança cada segmento. Quando um link ativo falha, o algoritmo recalcula uma nova árvore e promove um link de backup bloqueado, curando a conectividade sem intervenção humana.²

Por que Radia Perlman é chamada de “Mãe da Internet” e por que ela não gosta disso?

Perlman é frequentemente chamada de “Mãe da Internet” porque o Spanning Tree Protocol e seu trabalho de roteamento link-state são fundamentais para a forma como as redes modernas permanecem conectadas.¹ Ela rejeita o rótulo há anos, argumentando que nenhuma pessoa sozinha inventou a Internet – ela foi obra de muitas pessoas e muitas tecnologias – e que destacar um único inventor é tanto impreciso quanto uma distração.⁵ Ela também se opôs ao enquadramento marcado por gênero, sustentando que o gênero de alguém não deveria ser a lente para o trabalho de uma vida.⁵

O que é roteamento com robustez bizantina?

Roteamento com robustez bizantina é o roteamento projetado para continuar entregando pacotes corretamente mesmo quando alguns roteadores não estão meramente falhos, mas ativamente maliciosos – descartando tráfego, mentindo sobre a topologia da rede ou forjando mensagens de roteamento. Foi o tema da tese de doutorado de Perlman no MIT, de 1988, “Network Layer Protocols with Byzantine Robustness.”¹ A distinção importa: um nó que falhou é silencioso e previsível, enquanto um nó bizantino (comprometido) se comporta de forma arbitrária e adversarial, então o protocolo precisa alcançar a entrega correta apesar dos participantes que tentam quebrá-lo. Tratar a falha maliciosa como um caso central de projeto, em vez de um patch de segurança posterior, é o fio condutor do trabalho de Perlman.¹

O que é o TRILL e como ele melhora o Spanning Tree Protocol?

O TRILL (“Transparent Interconnection of Lots of Links”) é um protocolo que Perlman projetou como sucessor do STP.⁶ O STP evita loops bloqueando links redundantes, o que desperdiça largura de banda e pode forçar o tráfego a longos desvios pela raiz. Em vez disso, o TRILL aplica o roteamento link-state ao bridging: seus switches, chamados RBridges, rodam o protocolo IS-IS entre si para aprender a topologia completa e calcular os caminhos mais curtos, de modo que ele “estabelece caminhos por todos os links ativos” em vez de desativá-los – mantendo a simplicidade plug-and-play do bridging enquanto ganha a eficiência de caminho e a resiliência do roteamento.⁶

Fontes