Faculdade de Engenharia da Universidade do Porto

Projecto de Router para Redes Móveis

Ricardo Miguel Faria

Relatório de Projecto realizada(o) no âmbito do Mestrado Integrado em Engenharia Electrotécnica e de Computadores

Major Telecomunicações

Orientador: Prof. Doutor Manuel Ricardo Co-orientador: Eng. Filipe Sousa

Fevereiro de 2009

© Ricardo Faria, 2009

iii

Abstract

The large and increasing volume of mobile equipment in big metropolitan areas, show us

that mobility is nowadays a big issue. From this, it is imperative that public transportation

systems provide broadband accesses to their vehicles, stops and passengers, allowing them to

be always connected despite where they are and if they are or not moving.

This dissertation aims to develop a communication router to be installed in public

transportation vehicles, such as taxis, bus, tram, etc., allowing the formation of ad-hoc

networks and connect themselves to another routers localized in bus/tram stops.

v

Índice

INTRODUÇÃO .............................................................................................. 1

1.1 MOTIVAÇÃO ....................................................................................... 1

1.2 PROBLEMA......................................................................................... 1

1.3 OBJECTIVOS E ESTRATÉGIA ........................................................................ 2

ESTADO DA ARTE ......................................................................................... 5

2.1 MPLS ............................................................................................. 5

2.2 OLSR ............................................................................................. 7

2.3 TRILL ............................................................................................ 8

2.4 WNMT ............................................................................................ 9

2.5 CONCLUSÃO ..................................................................................... 10

ANÁLISE DE FERRAMENTAS OU IMPLEMENTAÇÕES .............................................. 13

3.1 LABEL DISTRIBUTION PROTOCOL API ............................................................ 13

PLANO DE TRABALHO.................................................................................. 15

REFERÊNCIAS ............................................................................................ 17

vii

Lista de figuras

Figura 2.1 – Mapeamento entre tabelas de encaminhamento nível 2 e 3 ....................... 6

Figura 2.2 – Rotas através de ER-LSP e hop-by-hop LSP ............................................ 7

Figura 2.3 – Esquema de uma rede WNMT ............................................................ 9

ix

Lista de tabelas

Tabela 1 – Planeamento do Projecto ................................................................ 15

xi

Lista de abreviaturas e siglas

AP Access Point

API Application Programming Interface

DHCP Dynamic Host Configuration Protocol

ER-LSP Explicitly Routed LSP

FEC Forwarding Equivalence Class

FIFO First-In, First-Out

GSM Global System for Mobile Communications

IEEE Institute of Electrical and Electronics Engineers

IETF Internet Engineering Task Force

IP Internet Protocol

LAN Local Area Network

LSP Label Switched Path

LSR Label Switching Router

MAC Media Access Control

MPR Multipoint Relays

MPLS Multiprotocol Label Switching

OLSR Optimized Link State Routing Protocol

QoS Quality of Service

STP Spanning Tree Protocol

TRILL Transparent Interconnection of Lots of Links

UMTS Universal Mobile Telecommunications System

WIMAX Worldwide Interoperability for Microwave Access

WLAN Wireless Local Area Network

WMRP Wireless Metropolitan Routing Protocol

WNMT Wireless Network for Metropolitan Transports

LDP Label Distribution Protocol

1

Capítulo 1

Introdução

Este capítulo pretende fornecer uma visão global do trabalho que se pretende realizar.

1.1 Motivação

O aumento significativo de equipamentos móveis em grandes áreas metropolitanas

mostra-nos que a mobilidade é um problema nos dias de hoje.

Assim sendo, é imperativo que os transportes públicos forneçam acessos de banda larga

nos seus veículos e paragens aos seus passageiros, permitindo-lhes o acesso a serviços, como

Internet e a difusão de canais de vídeo, em qualquer altura e local, sem que tenham perda de

conectividade durante deslocações.

1.2 Problema

A criação de uma rede privada com a dimensão e escalabilidade pretendida e sendo auto-

configurável, levanta vários problemas, quer no seu projecto quer na sua implementação.

O desenvolvimento de um equipamento de comunicação de nível 2, a ser instalado em

veículos de transportes públicos (e.g. autocarro), deverá permitir a formação de redes ad-

hoc, interligando-se com outros equipamentos localizados nas paragens e routers baseados na

norma IEEE 802.16 (Worldwide Interoperability for Microwave Access ou WIMAX) ou na IEEE

802.11 (Wireless Local Area Network ou WLAN). Esporadicamente, poderá ser usado em locais

2 Introdução

sem cobertura de equipamentos com as normas anteriormente referidas, a tecnologia

Universal Mobile Telecommunications System (UMTS).

De entre os vários problemas, alguns têm a sua resolução mais simplificada, como por

exemplo, aquando da ligação de um terminal à rede, é necessário atribuir a este um IP. Este

problema pode ser resolvido com um servidor DHCP que atribui a todos os terminais, após um

DHCP request, um IP, sendo assim mais fácil que um terminal mantenha o seu IP inicial,

enquanto se desloca pela rede, tal como acontece numa rede wireless ao deslocar-se pelos

vários APs.

Algo mais complicado e com solução não tão fácil é perceber como é que o equipamento

adoptado que será colocado, por exemplo nos autocarros, conseguirá estabelecer uma

conexão com os restantes equipamentos, que estarão, ou fixos nas paragens ou em pontos

estratégicos, equipados com WIMAX. Encontrar solução para este problema torna-se mais

difícil uma vez que os autocarros estão em constante movimento, e com isto temos também

que garantir que os terminais que se deslocam ao longo da rede, da paragem para o

autocarro, p.e., mantêm a sua ligação existente sem perda de conectividade e de dados. Para

tal têm, como referido anteriormente, que manter o mesmo IP. Isto obriga que a rede esteja

preparada para fazer o encaminhamento de tramas, pelos diversos equipamentos usados,

quando o terminal se encontra em deslocação.

De notar que, para a implementação desta rede é necessário que todos os terminais

estejam a apenas 1 (um) hop IP entre si e a gateway para o exterior, ou seja, que todos

equipamentos usados se comportem como um switch.

1.3 Objectivos e Estratégia

O objectivo deste trabalho é permitir que um utilizador, por exemplo, ao chegar a uma

paragem, se consiga ligar ao equipamento aí existente, adquirindo um IP. Ao deslocar-se para

o interior de um qualquer autocarro, o seu terminal ligar-se-á ao equipamento que se

encontra no autocarro mantendo conectividade e o mesmo IP. Posteriormente, ao deslocar-se

para outras paragens e autocarros a conectividade manter-se-á, assim como, o IP obtido

inicialmente.

O equipamento de comunicação usado nas paragens estará ligado à rede usando Ethernet

Gigabit e o dos autocarros ligar-se-ão ao das paragens usando a norma IEEE 802.11 e quando

em andamento a equipamentos IEEE 802.16, WIMAX, que garantirão a cobertura fora das

zonas das paragens. Nas áreas não cobertas, quer pela norma IEEE 802.11, quer pela IEEE

802.16, será usado um modem HSDPA para ligação UMTS. Este será sempre um último recurso

pois o tráfego realizado é pago e a velocidade da ligação é bastante inferior às restantes

tecnologias.

Introdução 3

Estes equipamentos em conjunto funcionarão como um switch gigante de nível 2, em que

todos os terminais e a gateway de acesso à Internet estarão apenas a um hop IP de distância.

Haverá um central que funcionará como servidor DHCP para poder atribuir os IPs aos

terminais, sendo que os restantes terão que ser capazes de efectuar DHCP relay.

Com a mobilidade de terminais e o grande número de nós de uma rede dimensionada para

ambiente metropolitano, é necessário um protocolo de sinalização para garantir um caminho

desde aos equipamentos e a gateway de saída e que seja responsável pelo plano de dados,

sendo baseado no Multiprotocol Label Switching (MPSL).

Existem alguns protocolos que fazem algo semelhante, mas ou não têm a escalabilidade

necessária, cerca de 1500 nós e 10000 terminais, mas com mobilidade assegurada, como o

MPLS, ou então tem a escalabilidade que se pretende mas sem a mobilidade necessária, como

o Transparent Interconnection of Lots of Links (TRILL). Assim é necessária a criação de um

protocolo que consiga fazer o que o MPLS e o TRILL fariam juntos. A criação do Wireless

Metropolitan Routing Protocol (WMRP) vem tentar colmatar esta “falha”.

Pretende-se então implementar fisicamente o trabalho até agora realizado em ambiente

de simulação NS3, e realizar um protótipo de demonstração de todo o sistema, mostrando

todas as capacidades num ambiente real.

5

Capítulo 2

Estado da Arte

Neste capítulo é realizada uma breve discrição sobre os protocolos estudados para a

realização do presente trabalho.

2.1 MPLS

Nas redes IP convencionais, os pacotes são encaminhados hop-by-hop, e cada router, ao

longo do percurso, toma a decisão do caminho por onde o pacote irá seguir. O próximo hop

para um pacote é escolhido com base na tabela de encaminhamento que o router tem,

actualizada por protocolos de encaminhamento.

A arquitectura Multiprotocol Label Switching, MPLS, procura resolver os problemas de

escalabilidade e de encaminhamento rápido de pacotes. É uma solução que integra label

swapping forwarding com o encaminhamento da camada de rede, routing IP.

Para efectuar o encaminhamento de pacotes, segundo [1], são necessárias funções de

controlo que constroem e actualizam as tabelas de encaminhamento. Estas tabelas definem

as rotas e como os labels são mudados em cada nó como ilustrado na Figura 2.1.

O MPLS coloca um cabeçalho, pequeno e com dimensão fixa, apenas com um significado

local, usado para identificar uma classe de encaminhamento equivalente, Forwarding

Equivalence Class (FEC), a qual representa um grupo de pacotes que é reencaminhado da

mesma maneira, ou seja, através do mesmo caminho e recebendo o mesmo modo de

encaminhamento, visto que têm o mesmo requisito de transporte.

6 Estado da Arte

Figura 2.1 – Mapeamento entre tabelas de encaminhamento nível 2 e 3

A atribuição de um pacote a uma FEC apenas é efectuada uma vez, aquando da entrada

desse pacote num nó que está num domínio MPLS. Os pacotes com uma determinada FEC

seguem um caminho comum através dos nós com MPLS, chamado Label Switched Path (LSP).

A escolha de encaminhamento através dos nós é efectuada por cada nó através do label de

entrada, que é usado para saber qual o next hop e o label de saída, sendo feito a troca entre

os dois cabeçalhos no pacote, label swapping. Isto é efectuado em cada nó e antes de este

ser encaminhado. O LSP tem que estar atribuído e o cabeçalho colocado em cada nó para que

o tráfego possa ser encaminhado.

Usando LSPs, o MPLS consegue fornecer muitas das vantagens das redes orientadas às

ligações.

OS nós MPLS são chamados de Label Switching Routers (LSR), e cada nó conhece os

protocolos de controlo do MPLS, trabalhando na camada 3, encaminhando os pacotes e

atribuindo-lhes uma FEC, adicionando-lhes os respectivos cabeçalhos.

Parte fulcral para o funcionamento do MPSL é a ligação entre os cabeçalhos (que

representam as FEC) e a rota que irá ser percorrida. Para tal acontecer, é necessário

adicionar o cabeçalho ao pacote, ligá-lo ao LSP, e distribuir a ligação entre o cabeçalho e a

rota pelos restantes LSRs. Desta forma, é garantido que os nós adjacentes partilham um FEC

comum, ligando-os ao LSP respectivo. A tabela de encaminhamento é, desta forma,

construída com base na distribuição dos labels.

O MPLS suporta mais que um tipo de encapsulamento, ou seja, mais que um label no

mesmo pacote, organizado no formato first-in, first-out (FIFO), designado por label stack.

A escolha do percurso, de forma a criar o LSP para um FEC particular, pode ser, ou

baseada no encaminhamento hop-by-hop, no qual cada LSR, independentemente dos

restantes, determina o próximo hop para o LSP, baseado na sua tabela de encaminhamento

IP, construída pelo protocolo de encaminhamento habitual, ou então através de

Estado da Arte 7

encaminhamento explícito, explicitly routed LSP (ER-LSP), no qual o LSP tem todo o percurso

de LSRs que o pacote irá percorrer. Os dois percursos podem ser iguais, mas usualmente são

diferentes, como apresentado na Figura 2.2.

Figura 2.2 – Rotas através de ER-LSP e hop-by-hop LSP

O MPLS garante escalabilidade, quer em relação ao número de nós quer ao fluxo de

tráfego, e ainda flexibilidade, pois não está preso a uma tecnologia de encaminhamento

específica. Pode ainda ser usado com outros protocolos ou arquitecturas, para suportar, por

exemplo, Quality of Service (QoS).

Tem como inconveniente ter sido projectado para uso em WLANs, o que para o caso de

redes LAN, nível 2, tem que ser adaptado.

2.2 OLSR

O Optimized Link State Routing Protocol (OLSR) em [2], foi desenvolvido para redes ad-

hoc. Este protocolo serve para trocar informação entre nós sobre a topologia da rede onde

está a ser executado.

Para troca de informação, cada nó escolhe um conjunto de nós vizinhos como multipoint

relays (MPR). Apenas estes MPRs podem fazer o encaminhamento do tráfego de controlo,

usado para difusão na rede. Para evitar a inundação da rede com mensagens de controlo, os

MPRs têm mecanismos que reduzem o número de transmissões necessárias. Mesmo assim,

estas transmissões são frequentes o que provocam muitos overheads na rede.

8 Estado da Arte

Estes MPRs são os responsáveis por declarar o estado das ligações. Para que o OLSR tenha

a informação correcta sobre o percurso mais curto, é necessário que os MPRs forneçam essa

informação ao(s) nó(s) que a(s) escolheu(escolheram).

Esta informação é enviada periodicamente, de forma a garantir a actualização das tabelas

de encaminhamento. Estas são construídas usando os MPRs para criar rotas entre um nó e

qualquer ponto da rede.

Devido ao uso dos MPRs e às mensagens de controlo, este protocolo não permite grande

escalabilidade. O aumento da topologia iria fazer aumentar o número de MPRs, gerar mais

mensagens de controlo e seria difícil os MPRs controlarem em tempo aceitável o estado das

ligações.

2.3 TRILL

O Transparent Interconnection of Lots of Links (TRILL) em [3], é uma combinação entre

spanning tree e link state routing protocol.

As spanning trees são usadas em redes de nível 2 para encontrar caminhos entre os nós,

mas estas convergem lentamente com a deslocação dos nós na rede, o que provoca ou perda

de dados ou atraso na entrega dos mesmos e faz com que os percursos sejam demasiado

rígidos, sendo que o percurso pode não ser o melhor numa determinada situação.

Os link state routing protocols são protocolos nível 3, que permitem que o tráfego seja

direccionado através de percursos de custo mínimo, em vez de ser agregado numa spanning

tree. Isto fornece maior capacidade de agregação e maior resistência a quebras de ligações.

Infelizmente, redes IP obrigam a que os terminais tenham endereços IP diferentes quando

mudam de sub-redes, sendo que todo o tráfego é interrompido aquando da mudança.

Muito frequentemente, o uso de spanning tree resulta num ineficiente uso da topologia de

ligações, na qual o tráfego concentra-se no percurso da spanning tree e percorre sempre esse

mesmo percurso, mesmo que exista um mais eficiente e directo. Para evitar este problema,

recorre-se ao uso de múltiplas spanning trees, mas isto obriga a configurações adicionais.

Alem disto, o uso do número de ramos é limitado, e o protocolo reage a pequenas alterações

da topologia da rede de forma muito acentuada na reconfiguração das ligações que se

encontram em uso.

O Spanning Tree Protocol (STP) tenta evitar que ciclos, num conjunto de bridges

interligadas, aconteça, desactivando ligações físicas para que apenas um percurso seja

possível, evitando loops. Isto acarreta com uma grande desvantagem, que é, todo o tráfego

que circularia pela ligação agora desactivada, irá por outro caminho, juntamente com o

tráfego que já iria circular pelo mesmo caminho, aumentando assim o tráfego, diminuindo a

Estado da Arte 9

largura de banda e, respectivamente, a velocidade nesse caminho. Assim, o tráfego não segue

o caminho mais eficiente, como seria esperado.

Apesar das vantagens acima referidas, os link state routing protocols associados a

spanning tree, não resolvem o problema da falta de mobilidade provocado pelos link state

protocols e a baixa escalabilidade provocada pelas spanning trees.

2.4 WNMT

Para o projecto em questão, será necessário a criação de uma Wireless Network for

Metropolitan Transports (WNMT). Como visto em [4], é um tipo de rede criada para lidar com

os requisitos de uma rede que tem nós em movimento e que pretende que os seus

utilizadores, em constante deslocação através dos vários nós, nunca percam conectividade,

como demonstrado na Figura 2.3.

Para que todo o sistema seja funcional, é necessário o desenvolvimento de um

equipamento de comunicações de nível 2, designado por Rbridge. Estas Rbridges terão que

fazer todo o encapsulamento do tráfego que irá circular ao logo da rede, tendo que

comunicar entre elas e os equipamentos terminais que se encontram nas suas imediações.

Na criação de uma rede assim, espera-se que esta seja auto-configurável e que não se

baseie em protocolos como RIP e OSPF. A mobilidade é, sem dúvida, o principal problema,

pois as Rbridges estão em constante movimento e é necessário estabelecer ligações entre as

Figura 2.3 – Esquema de uma rede WNMT

10 Estado da Arte

Rbridges dos autocarros (móveis) e as das estações (fixas) e entre cada uma delas e os

terminais. Pretende-se também que esta seja escalável até cerca de 10000 terminais e 1500

Rbridges (nós), valores que se poderão aproximar do esperado para um ambiente

metropolitano.

Para isso, é necessária a criação de um protocolo que colmate as falhas do MPLS e TRILL.

Este protocolo, Wireless Metropolitan Routing Protocol (WMRP), será um protocolo de nível

2.5, ou seja, adicionará mais um cabeçalho à trama, permitindo que terminais mantenham o

mesmo IP durante o seu movimento dentro da rede, mas fazendo que estes estejam a apenas

um hop IP de distância entre terminais e a gateway de saída para o exterior da rede WNMT.

Qualquer tipo de tráfego broadcast ou multicast enviado pelos terminais para a rede

deverá ser automaticamente bloqueado pelas Rbridges terminais, para não ocorrer uma

inundação da mesma com mensagens desnecessárias. Para tal, é necessário criar um

mecanismo que substitua as habituais mensagens que constantemente circulam em redes

(ARP,DHCP requests, etc.).

A actualização das tabelas de encaminhamento é feita de forma radial, para as Rbridges

mais próximas da Rbridge que está a mandar uma mensagem de Controlo de Topologia (TC),

mensagem esta periódica, na qual a Rbridge informa quais as Rbridges mais próximas. Esta

envia também periodicamente mensagens MAC Control (MC), a qual contem a sua tabelas de

endereços MAC que irá partilhar com as Rbridges vizinhas. Para informar das combinações IP-

MAC (dos equipamentos terminais), a Rbridge usa mensagens de Controlo de IP (IC).

Para uma Rbridge encaminhar as frames que lhe chegam, pede às Rbridges vizinhas as

suas TCs, MCs e ICs, caso seja no início do percurso. Se não for, é enviada para a última

posição conhecida do terminal.

Como a rede interna é de nível 2, é necessário, como dito anteriormente, um servidor de

DHCP, para que seja atribuído a um terminal um IP, e haja uma administração central dos IPs

ocupados e livres.

Para que todo o sistema seja completamente funcional, este deve ser transparente para o

utilizador, ou seja, independente do equipamento terminal usado. Este deve apenas ser capaz

de equipamentos baseados na norma IEEE 802.11.

2.5 Conclusão

Para a realização do presente projecto, é necessário um protocolo que garanta, quer

escalabilidade, pois é dimensionada para ambiente metropolitano, mobilidade, visto os

Estado da Arte 11

terminais estarem em constante movimento, tem que ser simples e com pouco overhead,

para não sobrecarregar a rede.

O OLSR, para a dimensão pretendida, necessitaria de um enorme número de MPRs, o que

geraria um aumento absurdo de mensagens de controlo, tornando inaceitável o controlo das

ligações por estes.

Como as redes IP obrigam, aquando à mudança de sub-redes, os terminais a mudar de

endereço IP para a sua gama, todo o tráfego é interrompido aquando da mudança. Para tal, o

TRILL não resolve o problema da falta de mobilidade provocado pelos link state protocols e a

baixa escalabilidade provocada pelas spanning trees, não cumprindo os requisitos para este

trabalho.

O que mais se assemelha ao procurado é o MPLS, pois garante a escalabilidade necessária,

quer em relação ao número de nós quer ao fluxo de tráfego. Visto ter sido projectado para

redes WLAN, tem que ser adaptado para redes nível 2.

Assim, o WMRP, baseado no MPLS, permite o que se pretende, pois são feitas as

alterações necessárias ao MPLS, diminuindo as mensagens que circulam pela rede, e como é

de nível 2.5, permite a todos os terminais estarem a apenas um hop IP entre eles e entre

cada um deles e a gateway de saída.

12 Estado da Arte

13

Capítulo 3

Análise de ferramentas ou Implementações

Neste capítulo é analisada uma ferramenta que será usada no decorrer da realização do

projecto proposto

3.1 Label Distribution Protocol API

Para que se possa alterar o protocolo MPLS, de forma a interliga-lo ao até agora trabalho

efectuado em ambiente de simulação NS-3, no qual já existe material para a execução

simulada do projecto proposto, é necessário a instalação de uma Application Programming

Interface (API) que permita configurar o MPLS.

O Label Distribution Protocol (LDP), em [5] e [6], fornece meios para os LSRs pedirem,

distribuírem e libertarem informação para os restantes LSRs da rede. O LDP permite aos LSRs

descobrirem potenciais nós, e estabelecerem sessões LDP entre eles, de forma a criar os LSPs.

Assim, os LSRs podem distribuir estes labels através dos percursos que conhece, de

maneira a garantir suporte para o encaminhamento do MPLS.

Com esta API, espera-se poder configurar e alterar o protocolo MPLS para os requisitos da

rede pretendida.

15

Capítulo 4

Plano de Trabalho

Este capítulo apresenta, na Tabela 1, uma programação inicial do trabalho esperado que,

apesar de ser uma ideia em bruto, sempre sujeita a muitas alterações ao longo do percurso,

fornece uma programação de trabalho ao longo do próximo semestre.

Para a adaptação do MPLS para o WMRP, será necessário adicionar a um sistema a correr

Linux, o LDP, tendo que ser compilado um kernel com esse módulo. Todo o restante trabalho

terá como base este sistema.

Depois de ter todo o sistema operacional, e percebido o funcionamento prático do LDP,

será necessário estudar uma forma de estabelecer uma ligação entre o sistema e todas as

funcionalidades desenvolvidas em ambiente NS-3. O desenvolvimento de uma Framework é

imperativo para tornar toda a integração de sistemas mais fácil, com módulos que

estabeleçam a ligação entre o sistema real, e as funções em NS-3.

TarefasImplementar um Sistema com LDP

Interacção entre LDP e NS-3

Desenvolvimento de uma "Framework"

Validação dos módulos

Teste / Validação Global

Escrita da Dissertação

Fevereiro Março Abril Maio Junho

Tabela 1 – Planeamento do Projecto

16 Plano de Trabalho

Findo todo o desenvolvimento, é necessário testar, primeiro os módulos e depois todo o

sistema, começando numa rede mais pequena e estática, passando depois para redes de

maior dimensão e com nós móveis.

17

Referências

[1]. Ruela, José and Ricardo, Manuel. "MPLS - Multiprotocol Label Switching". Faculdade

de Engenharia da Universidade do Porto e INESC Porto.

[2]. "Optimized Link State Routing Protocol (OLSR)". IETF. [Online] [Cited: November 2,

2008.] http://www.ietf.org/rfc/rfc3626.txt.

[3]. "Transparent Interconnection of Lots of Links (TRILL)". IETF. [Online] 2 de November

de 2008. http://tools.ietf.org/html/draft-ietf-trill-prob-05#page-7.

[4]. Ricardo, Manuel et al. "WiMetroNet - A Scalable Wireless Network for Metropolitan

Transports". INESC Porto.

[5]. LDP Specification. IETF. [Online] January 2001. [Cited: Fevereiro 5, 2009.]

http://www.ietf.org/rfc/rfc3036.txt.

[6]. Cisco. MPLS Label Distribution Protocol (LDP). [Online] May 1, 2008. [Cited: February

6, 2009.]

http://www.cisco.com/en/US/docs/ios/mpls/configuration/guide/mp_ldp_overview.pdf.