Dissertação

{en_GB=Routing on Multiple Optimality Criteria: Theory and Protocols} {} EVALUATED

{pt=O conceito de caminho ótimo numa rede está vinculado a: (a) um conjunto de atributos de caminhos; (b) uma operação binária de extensão sobre atributos, que calcula atributos de caminhos a partir de atributos de ligações; e (c) uma ordem total sobre atributos, que define um critério de otimalidade estabelecendo a preferência relativa entre atributos de caminhos. Os protocolos vetoriais padrão, tais como EIGRP, BGP, DSDV ou Babel, só resolvem o problema do encaminhamento em caminhos ótimos se a operação binária de extensão for isótona para a ordem total, deixando assim de parte muitos critérios de otimalidade de interesse prático. Isotonicidade expressa que a preferência relativa entre quaisquer dois atributos é preservada quando estes são estendidos com qualquer terceiro atributo. Apresentamos uma solução geral para o encaminhamento em caminhos ótimos e, de forma mais abrangente, para o encaminhamento em múltiplos critérios de otimalidade. Uma ideia fundamental é a derivação de ordens parciais sobre atributos que satisfaçam isotonicidade e respeitem todas as ordens totais que definem um critério de otimalidade numa designada coleção de tais critério. Concebemos novos protocolos de encaminhamento que operam sobre ordens parciais e que em cada nó elege um conjunto de atributos, em vez de um único, como fazem os protocolos vetoriais padrão. A nossa avaliação sobre redes realistas mostra que os protocolos concebidos requerem apenas alguns atributos eleitos por destino e convergem rapidamente. Os conceitos e protocolos introduzidos abrem caminho a soluções para outros problemas de encaminhamento, não necessariamente relacionados com otimalidade., en=The concept of optimal path in a network is bound to: (a) a set of path attributes; (b) a binary extension operation on attributes, which calculates path attributes from link attributes; and (c) a total order on attributes, which defines an optimality criterion by establishing the relative preference among path attributes. Standard vectoring protocols, such as EIGRP, BGP, DSDV or Babel, only solve the problem of routing on optimal paths if the binary extension operation is isotone for the total order, thus leaving out many optimality criteria of practical interest. Isotonicity expresses that the relative preference between two attributes is preserved when they are extended with a third attribute. We present a general solution to routing on optimal paths and, more broadly, to routing on multiple optimality criteria. A fundamental idea is the derivation of partial orders on attributes that satisfy isotonicity and respect every optimality criterion of a designated collection of such criteria. We design new routing protocols that compute on partial orders and have each node elect a set of attributes, rather than a single attribute, as standard vectoring protocols do. Our evaluation over realistic networks shows that the protocols devised require only a few elected attributes per destination and converge fast. The concepts and protocols introduced pave the way for solutions to other routing problems, not necessarily related to optimality.}
{pt=Problemas de encaminhamento, Protocolos de Vetoriais, Critérios de Otimalidade, Encaminhamento em Caminhos Ótimos, Álgebras do Encaminhamento, Ordens Parciais, en=Routing problems, Routing Protocols, Optimality Criteria, Optimal Path Routing, Routing Algebras, Partial Orders.}

Outubro 9, 2020, 9:30

Orientação

ORIENTADOR

João Luís Da Costa Campos Gonçalves Sobrinho

Departamento de Engenharia Electrotécnica e de Computadores (DEEC)

Professor Associado