Google Treasure Hunt 3: Busca em Profundidade (Depth-First Search)

Esse é outro problema do Google Treasure Hunt que eu resolvi. Esse foi o mais fácil de todos, e realmente não era necessário nenhum conhecimento de programação. Tenha-se em mente apenas que o não uso de programação para resolvê-lo não é de modo algum divertido! Tente ensinar seu computador a fazê-lo por você… O problema que eu obtive no Google foi o seguinte:

“Below is a diagram of a computer network. The nodes are hosts on the network, and the lines between them are links. A packet is sent out from host P with a destination of 4.229.231.150. Which nodes does the packet pass through on its way to the destination? (include start and final node in your answer)”

O diagrama para o modelo da rede acima foi fornecido na forma da tabela de roteamento a seguir:

“

A 26.40.28.17 75.174.216.140 => 126.186.188.58 26.40.28.17 => 17.100.195.84 4.229.231.0/24 => 75.174.216.140 13.157.234.26

B 13.157.234.26 76.246.145.72 => 53.12.68.161 126.186.188.58 => 75.174.216.140 53.12.68.0/24 => 26.40.28.17 17.100.195.84

C 53.12.68.161 75.174.216.140 => 219.88.219.35 229.23.61.42 => 13.157.234.26 17.100.195.0/24 => 103.19.57.145 126.186.188.58

D 103.19.57.145 86.60.122.237 => 86.60.122.237 117.146.177.141 => 53.12.68.161 229.23.61.0/24 => 219.88.219.35 212.222.1.12

E 4.229.231.150 4.229.231.150 => 103.19.57.145 54.35.7.207 => 54.35.7.207 126.186.188.0/24 => 199.223.210.72 229.23.61.42

F 54.35.7.207 4.229.231.150 => 229.23.61.42 13.157.234.26 => 199.223.210.72 26.40.28.0/24 => 4.229.231.150 86.60.122.237

G 86.60.122.237 229.23.61.42 => 54.35.7.207 13.157.234.26 => 103.19.57.145 103.19.57.0/24 => 212.222.1.12 219.88.219.35

H 212.222.1.12 126.186.188.58 => 219.88.219.35 75.174.216.140 => 86.60.122.237 103.19.57.0/24 => 103.19.57.145 229.23.61.42

I 229.23.61.42 4.229.231.150 => 4.229.231.150 117.146.177.141 => 54.35.7.207 126.186.188.0/24 => 199.223.210.72 212.222.1.12

J 199.223.210.72 53.12.68.161 => 229.23.61.42 4.229.231.150 => 54.35.7.207 219.88.219.0/24 => 219.88.219.35 4.229.231.150

K 219.88.219.35 4.229.231.150 => 199.223.210.72 17.100.195.84 => 212.222.1.12 126.186.188.0/24 => 86.60.122.237 103.19.57.145

L 117.146.177.141 4.229.231.150 => 219.88.219.35 117.146.177.141 => 126.186.188.58 26.40.28.0/24 => 76.246.145.72 75.174.216.140

M 75.174.216.140 199.223.210.72 => 13.157.234.26 4.229.231.150 => 117.146.177.141 126.186.188.0/24 => 17.100.195.84 26.40.28.17

N 17.100.195.84 4.229.231.150 => 26.40.28.17 219.88.219.35 => 13.157.234.26 17.100.195.0/24 => 75.174.216.140 76.246.145.72

O 76.246.145.72 4.229.231.150 => 17.100.195.84 86.60.122.237 => 126.186.188.58 13.157.234.0/24 => 53.12.68.161 117.146.177.141

P 126.186.188.58 13.157.234.26 => 53.12.68.161 4.229.231.150 => 76.246.145.72 103.19.57.0/24 => 26.40.28.17 117.146.177.141

”

Como você talvez tenha suposto, o primeiro símbolo é o ID do nó de rede, seguido por seu número IP. A seguir, você tem uma sequência de 3 regras de roteamento, o nó pode ver se essa regra em específico serve para o pacote entrante (incoming packet, ou pacote de rede no estágio de ingresso ao roteador). O ultimo número IP nos dá a rota padrão (“default route”), apenas no caso em que esse nó não encontrou nenhuma regra de roteamento que coubesse para um dado pacote (a rota padrão é como um “else” após uma sequência de “IF”s...).No caso do pacote chegar à rota padrão, esse pacote será direcionado para o host definido pelo endereço IP na última coluna da tabela acima.

Criei uma solução em C++, que usa um método de busca em profundidade para buscar por um caminho válido saindo de um dado nó para outro no modelo de rede do problema. Minha idéia foi fazer a função de busca em profundidade (em ingles, “depth-first search”) andar de nó em nó (nós são rotulados como: A, B, C, etc.), iterando sobre cada uma das regras da tabela de roteamento, e procurando por cada uma dessas regras que possa rotear adequadamente o pacote através da rede. A função abaixo é auto-explicável:

“

bool RoutingTable::routeTo( string node, string* resp )

{

bool do_it_again = true;

RoutingEntry rentry = findRouteEntry( node );

if ( rentry.doneThis() )

return false;

resp->append( rentry.getId() );

if ( rentry.getAddress().compare(getFinalDestination()) == 0 ) {

return false;

}

vector<RoutingRule> routing_rules = rentry.getRules();

vector<RoutingRule>::iterator i;

rentry.markThis(true);

// go through each of the routing rules

for ( i = routing_rules.begin(); ( i != routing_rules.end() ) &&

do_it_again; i++ )

{

if ( (*i).canRoute(getFinalDestination()) ) {

do_it_again = routeTo( (*i).getRedirection(), resp );

} // if

} // for

rentry.markThis(false);

// no rules; asks the default gateway…

if ( do_it_again )

{

do_it_again = routeTo( rentry.getDefaultRoute().getRedirection(),

resp );

}

return do_it_again;

}

”

Nessa solução usei apenas a STL do C++, ou C++ Standard Template Library (STL). Todos os nós são armazenados em estruturas como elementos de um vector, e são localizadas por símbolos de ID (A, B, C, etc.), ou por números IP (método findRouteEntry()). Cada nó tem a sua própria estrutura “Rules” (que você pode obter chamando getRules()). Uma vez processadas, cada uma dessas regras pode apontar para um outro nó da tabela, e a função routeTo pode atuar de forma recursiva sobre uma dada regra. Se nenhuma regra suficiente para combiner com o pacote for encontrada, a função routeTo é chamada sobre o nó retornado pela chamada a “getDefaultRoute”:

“

// no rules; asks the default gateway…

if ( do_it_again )

{

do_it_again = routeTo( rentry.getDefaultRoute().getRedirection(),

resp );

}

“

As chamadas para a função markThis() são para evitar recursões infinitas (iterar sobre os mesmos nós, de uma forma circular e muitas vezes irreversível, levando ao esgotamento de recursos computacionais). A semântica é simples: markThis(true), quando o código precisar entrar numa “regão crítca”, e markThis(false) quando tiver saído da região crítica.

Você conseguiria encontrar a diferença entre o método de roteamento que eu formulei para o que é implementado por roteadores de rede de verdade (de fabricantes como Cisco)? Talvez meus posts anteriores com questões da certificação CCNA da Cisco possam ajudar...

Google Treasure Hunt 2 - MapReduce?

Para resolver o Google Treasure Hunt 2, decidi usar um velho programa para busca de arquivos implementado em C++ usando multi-threading. Eu mudei algumas partes do código, só para garantir que possa fazer a busca pelos 2 padrões especificados no problema, e escolhi usar o framework Qt (da Trolltech) que tem algumas funções muito legais para lidar com arquivos, e isso é realmente verdade – você não precisa de mais nada, a não ser as classes QFile e QDir e derivadas delas.

Se você gosta de programação distribuída, talvez você já tenha ouvido falar no modelo MapReduce, desenvolvido pela Google (www.google.com). De acordo com Jeffrey Dean e Sanjay Ghemawat, em um artigo (“Distributed Programming with MapReduce”) escrito para o interessante livro “Beautiful Code” (O’Reilly, 2007), “MapReduce was developed as a way of simplifying the development of large-scale computations at Google.” (tradução: “O MapReduce foi desenvolvido como uma forma de simplicar o desenvolvimento de processamento em larga-escala no Google”) Acredito que esse problema proposto no Google Treasure Hunt não seja realmente um “processamento em larga-escala”, mas eu gostei da forma como o MapReduce funciona, e decidi aplicar esse conceito ao meu programa.

Aqui está o problema número 2 do Google Treasure Hunt:

Here is a random zip archive for you to download:
GoogleTreasureHunt08_14338682343771558225.zip

Unzip the archive, then process the resulting files to obtain a numeric result. You'll be taking the sum of lines from files matching a certain description, and multiplying those sums together to obtain a final result. Note that files have many different extensions, like '.pdf' and '.js', but all are plain text files containing a small number of lines of text.

Sum of line 4 for all files with path or name containing BCD and ending in .js
Sum of line 5 for all files with path or name containing foo and ending in .xml
Hint: If the requested line does not exist, do not increment the sum.

Multiply all the above sums together and enter the product below.
(Note: Answer must be an exact, decimal representation of the number.)

Se você der uma olhada no código fonte, existem 2 threads; o primeiro (Mapper) obtêm a lista de arquivos com um padrão de nomes fornecido (no meu caso, nomes contendo “BCD” e com extensão “.js”, ou contendo “foo” e terminando com “.xml”); o segundo thread (Reducer) utiliza a lista com nomes de arquivos do thread Mapper e faz uma outra busca mais profunda dentro de cada um dos arquivos pré-selecionados (para obter os valores de números nas linhas de número “4”). O principal método do Mapper é o seguinte:

bool FileSearchMap::depthFirstTraversal(const QString& currentDir)

{

QDir dirP(currentDir);

QString temp;

QString fileName;

QStringList entryP = dirP.entryList();

QStringListIterator entryL(entryP);

while (entryL.hasNext())

{

producerMutex.lock();

if (myFileCount == 5)

{

bufferNotFull.wait(&producerMutex);

} // if - mutex and signal

producerMutex.unlock();

fileName.clear();

temp = entryL.next();

if ((temp != ".") && (temp != ".."))

{

fileName = currentDir;

fileName.append('\\');

fileName.append(temp);

if (isDirectory(fileName))

{

depthFirstTraversal(fileName);

}

else

{

if (isRegular(fileName))

{

unsigned int ftype = 0;

if ( ( fileName.endsWith(".js") ) &&

( fileName.contains("BCD") ) )

ftype = TXT_FILE_PATTERN;

else if ( ( fileName.endsWith(".xml") ) &&

( fileName.contains("foo") ) )

ftype = XML_FILE_PATTERN;

if ( ftype != 0 )

{

DirEntry dentry( fileName, ftype );

queueMutex.lock();

textFiles.push(dentry);

queueMutex.unlock();

producerMutex.lock();

++myFileCount;

producerMutex.unlock();

bufferNotEmpty.wakeAll();

}

}

} // if - isDirectory / isRegular

} // if

} // while

return true;

}

O método acima sera chamado exatamente uma vez, a partir do método “run” da minha implementação do QThread no Mapper. Colocando o método depthFirstTraversal para rodar, primeiramente ele obtêm todos os arquivos do diretóro, chamando o método entryList, da classe QDir. Então um iterator é instanciado sobre a lista de arquivos anteriormente obtida, e, enquanto estiver iterando sobre os arquivos, e antes que qualquer coisa eu faço uma chamada à função wait da estrutura QWaitCondition: a “wait condition” é um tipo de variável de condição usada para sincronizar threads, interrompendo-o no caso de ter obtido 5 arquivos (claro, pode ser qualquer número que você queira). Porque obter exatamente 5 arquivos e interromper a execução, esperando para que a estrutura QWaitCondition seja liberada? Isso é usado de forma a criar um buffer com capacidade para 5 arquivos (no máximo), a partir do qual o thread Reducer pode iterar sobre cada um dos arquivos listados pelo thread Mapper, abrir cada um desses arquivos, e procurar pelo critério de busca dado. Dessa forma, o thread Reducer pode lidar apenas com uma lista de 5 arquivos, esgotá-la, e depois permitir que o Mapper preencha com mais alguns novos arquivos encontrados. Essa é a primeira regra usada para sincronizar os 2 threads: “Mapper, comece a cobrir o buffer com os nomes dos arquivos encontrados, até que ele tenha 5 elementos. Daí, espere até que o Reducer consuma alguns desses arquivos, pois a partir disso você pode obter mais alguns arquivos. Faça isso até o fim dos tempos”. Agora, o thread Reducer, obtendo todos os arquivos que o Mapper consiga procurar:

void KeySearchReduce::run()

{

DirEntry dirEntry;

int cnt = 0;

do

{

prod->producerMutex.lock();

if (prod->myFileCount == 0)

{

prod->bufferNotEmpty.wait(&prod->producerMutex);

if (prod->isSearchDown())

{

prod->producerMutex.unlock();

return;

}

}

prod->producerMutex.unlock();

prod->queueMutex.lock();

dirEntry = prod->getFirstTextFile();

prod->queueMutex.unlock();

QFile infile(dirEntry.getFileName());

if (!infile.open(QIODevice::ReadOnly | QIODevice::Text) )

continue;

QString line;

unsigned int i = 0;

QTextStream in(&infile);

if ( dirEntry.getFileType() ==

FileSearchMap::TXT_FILE_PATTERN ) {

while (!in.atEnd())

{

line = in.readLine();

++i;

if ( i == 4 ) {

lineP2Count += atol(line.toLocal8Bit().constData());

++foundCount;

break;

}

} // while

} else if ( dirEntry.getFileType() ==

FileSearchMap::XML_FILE_PATTERN ) {

while (!in.atEnd())

{

line = in.readLine();

++i;

if ( i == 5 ) {

lineP1Count += atol(line.toLocal8Bit().constData());

++foundCount;

break;

}

} // while

} // if - getFileType()

infile.close();

prod->producerMutex.lock();

prod->myFileCount--;

prod->producerMutex.unlock();

prod->bufferNotFull.wakeAll();

} while (!prod->isSearchDown());

}

O Reducer na primeira linha do comando “do” diz o seguinte: “Ei Mapper, você tem algum arquivo para que eu possa procurar pelo informação numérica na linha X? Caso você não tenha arquivo algum, eu esperarei um pouco, até que você tenha algo para mim...” Então, para cada arquivo que o thread Reducer processa, ele avisará ao Mapper, de forma a que ele possa alimentar mais o buffer. No caso do Mapper estiver dormindo em um buffer cheio com 5 elementos, ele será acordado e então recomeçará a cobrir o buffer com arquivos – isso é feito com uma chamada a prod->bufferNotFull.wakeAll(), encontrado no fim do loop principal do Reducer. A chamada a wakeAll faz com que todos os threads que estejam dormindo sobre essa variável de condição acordem imediatamente (ou quase). Com isso, o Mapper pode estar dormindo na linha bufferNotFull.wait(&producerMutex), no início do loop de busca, e essa chamada à função wakeAll a partir do Reducer pode liberar o bufferNotFull (uma instância do QWaitCondition), permitindo ao Mapper reiniciar o processo de completar o seu buffer de 5 elementos de novo. Tudo o que o Mapper tem que fazer é cobrir o buffer com nomes de arquivos.

Nós estamos lidando aqui com recursos compartilhados, e os mutexes são de uso obrigatório (veja as referências às instâncias de QMutex no código fonte) uma vez que essa aplicação é multithreaded, e não queremos que ocorram condições de corrida.

Colocando tudo junto:

FileSearchMap* mapper = new FileSearchMap;

KeySearchReduce* reducer = new KeySearchReduce;

mapper->setDirectory( dir );

reducer->setMapper( mapper );

mapper->start();

reducer->start();

mapper->wait();

reducer->wait();

long long a1, a2;

cout << argv[1] << " contains " <<>getFoundCount()

<< " files that contains " <<>getLineCount()

<< " lines for the pattern 1 ( " << (a1 = reducer->getLineP1Count()) <<

" ) and pattern 2 ( " << (a2 = reducer->getLineP2Count()) << " )." << endl;

long long response = a1*a2;

cout << "Response: (" <<>")" << endl;

Aqui, a chamada getLineP1Count() retorna a soma de todos os numeros na linha 4, nos arquivos com o primeiro padrão; e getLineP2Count() faz o mesmo para o padrão de busca 2.

Claro, dá pra resolver o problema todo sem usar capacidade de multithread, mas aí não tem graça! :)

Doctor Dobb's Code Talk

Para quem gosta de ler coisas sobre programação, um excelente site sempre foi o da revista Doctor Dobb's Journal [www.ddj.com]. Agora eles disponibilizaram um serviço de blog para os leitores. As discussões são sempre muito interessantes, para quem gosta de coisas como otimização de código, "thread-local heaps", arrays multi-dimensionais, desenvolvimento de software distribuído, e qual a melhor máquina para programar. Quem tiver a fim de participar, começa dando uma olhada no meu blog:
http://dobbscodetalk.com/index.php?option=com_myblog&task=view&id=531&Itemid=29

Vejo vocês lá!

Google Treasure Hunt 4

O Google resolveu disponibilizar uma espécie de competição, onde são propostos problemas e pede-se a solução deles, cujas respostas sugerem (na verdade, praticamente obrigam) a aplicação de algum recurso computacional. Até onde eu sei, os problemas são únicos para cada candidato, o que inviabiliza qualquer tentativa de “trabalho em conjunto”. Chama-se de “Google Treasure Hunt 2008” [http://treasurehunt.appspot.com/]. O conjunto de problemas apresentado (atualmente, contando com apenas 4) assemelha-se aos vistos em outros campeonatos de programação, como o International Collegiate Programming Contest (ICPC), da Association for Computing Machinery (ACM) [www.acm.org]. Resolvi o último desses problemas (o quarto), e detalho aqui como cheguei à solução.

O problema proposto foi o seguinte:

“Find the smallest number that can be expressed as

the sum of 11 consecutive prime numbers,

the sum of 25 consecutive prime numbers,

the sum of 513 consecutive prime numbers,

the sum of 1001 consecutive prime numbers,

the sum of 1129 consecutive prime numbers,

and is itself a prime number.

For example, 41 is the smallest prime number that can be expressed as

the sum of 3 consecutive primes (11 + 13 + 17 = 41) and

the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41).”

Para solucionar o problema proposto, resolvi utilizar a linguagem de programação C++, pelos recursos que a STL oferece (estruturas como set’s, vector’s, operações sobre conjuntos, etc.). Antes de tudo, o grande problema foi o de gerar os números primos. De modo que o problema não se refere a um limite razoável para a quantidade de números primos que a solução envolva, gerar uma tabela com todos os números primos até o limite considerável de 100.000, por exemplo, resolvi obter uma listagem pronta com o todos os números primos abaixo de 100 mil [http://members.aol.com/MICRO46/primes_1.zip], um total de exatamente 78498 primos. A razão de usar uma tabela pronta foi que o método que eu estava usando para gerar essa lista de primos demorava algo em torno de 4 minutos... Posteriormente, otimizei o procedimento para durar menos de 0,5 segundos, e gerei o resultado em disco. Contudo, quem não tiver afim de gerar essa quantidade de primos, esses arquivos prontos são uma mão na roda. Com o conjunto de primos em mãos, apliquei o procedimento seguinte:

1) Calcular as somas dos números primos em cada um dos intervalos (11, 25, 513, 1001, 1129) – isso implica em somar os primos em todos os subintervalos de tamanho 11, por exemplo, dentro do conjunto de primos, o que gerou uma seqüência de 78488 intervalos de tamanho 11, até 77.370 subintervalos de tamanho 1129;

2) Fazer uma intersecção de conjuntos, 2 a 2, com os conjuntos resultantes da operação acima (por exemplo, as somas de todos os subintervalos de tamanho 11 geram um conjunto) – o objetivo é obter as somas que são comuns entre esses conjuntos de somatórios de primos;

3) Ordenar o conjunto intersecção resultante e mostrar o primeiro valor (ou seja, o menor).

Para as etapas 1 e 2, o método que usei foi o seguinte:

void

sum_subintervals(const vector<long>& primes, unsigned long max,

set<long>* pivot)

{

unsigned long soma = 0, j = 0, old_sum = 0;

set<long> sums;

for (j = 0; j <>

{

soma += primes.at(j);

} // for

sums.insert(soma);

while ( (j <>

{

old_sum = soma;

soma = old_sum - primes.at(j-max) + primes.at(j);

++j;

sums.insert(soma);

}

set<long> s;

if (pivot->size() != 0)

{

set_intersection(sums.begin(), sums.end(), pivot->begin(),

pivot->end(), inserter(s, s.end()) );

pivot->clear();

copy(s.begin(), s.end(), inserter(*pivot, pivot->begin()));

}

else

{

copy( sums.begin(), sums.end(), inserter(*pivot, pivot->end()) );

}

}

O código é pouco óbvio, mas eu explico: o que ele faz é pegar intervalos de um certo tamanho (11, 25, 513, etc.) e somar os elementos nesse intervalo. Uma solução bastante elementar seria tentar somar diretamente todos os valores, e fazer isso para cada intervalo. Computacionalmente, no entanto, esse método repete desnecessariamente operações de soma (a maior parte dos elementos seriam somados duplicados entre subintervalos consecutivos). Foi exatamente nessas somas supérfluas que o algoritmo que eu fiz gerou otimizações. Por exemplo, o primeiro subintervalo de tamanho 11 é o seguinte:

{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}

O próximo subintervalo é assim:

{3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}

Qual a diferença entre os 2? No segundo, inseriu-se o 37 e removeu-se o 2. De forma geral, cada subintervalo adiciona à seqüência anterior o próximo elemento primo, e remove o primeiro elemento da sequência anterior do resultado. Aplicando esse método iterativamente, foi possível reduzir a complexidade da solução de uma exponencial (em função do quadrado do conjunto de primos) para uma solução linear, com o esforço de execução variando apenas sobre o tamanho da tabela de primos.

Pra finalizar, a parte mais simples do código apenas mostra o algoritmo acima rodando em cima de cada constante do problema:

set<long> all_sums;

int nums[5] = { 11, 25, 513, 1001, 1129 };

int i;

for (i = 0; i < 5; i++)

{

sum_subintervals(primes, nums[i], &all_sums);

}

if (all_sums.size() > 0)

cout << "Solution: " << *(all_sums.begin()) << endl;

Nem precisei ordenar o conjunto resultante, porque a classe template “set” da Standard Template Library já adiciona os elementos em ordem na estrutura. Quando tudo dá certo, na submissão aparece isso:

Correct answer: XXXXXXXXXX
Your answer was: Correct

Your answer was correct! Congratulations, you're part-way there.
There will more questions over the coming weeks, and the first person to answer them all correctly will win a prize, so keep trying!

Boa sorte!

CCNA / WANs

Questão CCNA sobre “Wide Area Networks” (WAN):

“Why won’t the serial link between the Corp router and the Remote router come up?

Corp#sh int s0/0

Serial0/0 is up, line protocol is down

Hardware is PowerQUICC Serial

Internet address is 10.0.1.1/24

MTU 1500 bytes, BW 1544 Kbit, DLY 20000 usec,

reliability 254/255, txload 1/255, rxload 1/255

Encapsulation PPP, loopback not set

Remote#sh int s0/0

Serial0/0 is up, line protocol is down

Hardware is PowerQUICC Serial

Internet address is 10.0.1.2/24

MTU 1500 bytes, BW 1544 Kbit, DLY 20000 usec,

reliability 254/255, txload 1/255, rxload 1/255

Encapsulation HDLC, loopback not set

A. The serial cable is faulty.

B. The IP addresses are not in the same subnet.

C. The subnet masks are not correct.

D. The keepalive settings are not correct.

E. The layer 2 frame types are not compatible.”

Avaliando cada um dos itens, temos que a letra “A” não pode ser verdadeira porque, se assim o fosse, a mensagem após o comando “sh int s0/0” (ou melhor, “show interface serial0/0”) indicaria que a interface Serial0/0 estaria “down” e não “up” (“Serial0/0 is up”). Tal informação indicaria uma falha física, como um cabo serial desconectado ou com defeito – contudo as coisas parecem funcionar na linha física serial. Apenas após a vírgula vemos algo mais esclarecedor; há uma mensagem indicativa dizendo “line protocol is down”. O protocolo estar não-funcional, mas a linha serial estar perfeita, nos faz levantar 2 hipóteses possíveis: se estivéssemos trabalhando com mecanismos de roteamento dinâmico, divergências em parâmetros de sincronização do tipo “Dead timers” (como os encontrados no RIP e no EIGRP) que especificam o tempo em que uma mensagem permanece válida até ser automaticamente descartada dentro do tempo determinado (estratégia usada para evitar loops de roteamento), poderia causar problemas de comunicação e gerar mensagens de “protocol is down”; caso não estejamos lidando com algoritmos de roteamento, inúmeros utilitários do Cisco IOS poderiam ser úteis aqui, mas das telas podemos deduzir de forma direta o que pode estar ocorrendo de ruim...

Acontece que os protocolos PPP e HDLC não são inteiramente compatíveis. Para não conhecedores das plataformas Cisco, isso pode parecer um contra-senso, porque o protocolo PPP prevê o uso do HDLC para encapsular datagramas sobre linhas seriais. Acontece que o HDLC ao qual a listagem acima se refere diz respeito a uma versão proprietária do High-Level Data Link Control, que funciona com um formato diferente de frame HDLC, incluindo um campo a mais chamado “Proprietary”. Esse belo fruto da inovação Cisco é incompatível com o padrão ISO HDLC, e acaso você queira interligar roteadores de diferentes fabricantes, vai ser melhor optar por um formato padrão de encapsulamento como o PPP.

Voltando ao mostrado no enunciado, e do acima exposto, temos que os roteadores acima estão utilizando formatos diferentes e incompatíveis de roteamento: HDLC no roteador Remote, e PPP no roteador Corp. Trocar o formato de um ou de outro já resolveria o problema, e portanto a letra “E” esclarece exatamente a razão do problema, porque ambos HDLC e PPP são protocolos de enlace de dados, ou seja, de camada 2 (layer 2).

Access Control Lists - ACLs

Tópicos que tem ocorrido com mais freqüência são aqueles relacionados com segurança, apesar de ser um assunto mais freqüente em exames mais avançados como o CCNP e o CCIE. Na questão abaixo, um exemplo básico com Access Control Lists (ACLs), retirado do livro “CCNA Study Guide, Sixth Edition”, do Todd Lammle:

“You configure the following access list:

access-list 110 deny tcp 10.1.1.128 0.0.0.63 any eq smtp

access-list 110 deny tcp any eq 23

int ethernet 0

ip access-group 110 out

What will the result of this access list be?

A. Email and Telnet will be allowed out E0.

B. Email and Telnet will be allowed in E0.

C. Everything but email and Telnet will be allowed out E0.

D. No IP traffic will be allowed out E0.”

Na questão, uma lista de comandos do roteador é apresentada, e pede-se o resultado da execução de tal lista num roteador hipotético. Aqui deve-se ter sempre em mente uma interpretação recorrente nas provas da Cisco: que o que não constar da relação de comandos, presume-se que foi omisso. Ou melhor, a lista de comandos começa exatamente com a primeira sentença de “access-list ...”, e termina com “ip access-group 110 out”. O trecho então não é parte de uma entrada do administrador de rede, mas sim uma sequência completa e indivisível de comandos.

Os comandos de access-lists na questão acima são no formato “extended”, ou seja, são no formato que começa com a definição da ação (“deny” ou “permit”), o intervalo de hosts de origem, o intervalo de hosts destino e, possivelmente, condições que especificam em que porta a restrição vai se impor. As listas extended são numeradas com identificadores de 100 a 199, e com elas é possível filtrar pacotes por campos IP de camada 3 e até alguns serviços de camada 4 ou maior (WWW, Telnet, SMTP, etc.), o que amplia o espectro de usos possíveis para as ACLs, como por exemplo mitigar ataques Denial-of-Service (DoS), DoS Smurfs, IP Spoofing, etc. É possível estabelecer regras que serão aplicadas especificamente a pacotes TCP com a flag SYN setada, por exemplo, o que serve de ajuda contra ataques de SYN flood. Certo, apenas “mitigar”, não necessariamente impedir tais ataques, dada a dificuldade em definir regras sobre grupos de pacotes suspeitos num universo tão grande de possibilidades de ataques. Mas a utilidade das ACLs ainda assim é muito bem vinda e quebra alguns galhos.

Quando é preciso definir regras que se apliquem a apenas um par de hosts, como a sentença “access-list 110 deny ip host 172.16.10.3 host 172.16.20.5”, por exemplo, que bloqueia pacotes IP com campo de origem 172.16.10.3 e destino para 172.16.20.5, a tarefa é imediata. Contudo, é mais comum, na definição das regras de ACLs, quando é necessário que sejam aplicadas regras a um intervalo de hosts numa sub-rede, pode-se recorrer aos wildcards. Vamos dizer que queiramos aplicar determinada regra ao conjunto de hosts nas sub-redes de 192.168.113.0 até 192.168.140.0. Primeiro, calcule quantas sub-redes existem entre os endereços anteriores; diminuindo 113 de 140 (140 – 113), obtemos 27. Agora é preciso achar uma potência de 2 que seja maior ou igual a esse intervalo; temos que 32 é maior que 27 (16 é outra potência de 2, mas é menor que 27), e portanto nos serve para esse propósito. Esse valor é 32 é o tamanho do bloco, e quando diminuído de 1, nos traz o endereço de wildcard. Nesse caso, temos que o endereço de wildcard para esse intervalo é 0.0.31.255. O terceiro octeto, que guarda informações das sub-redes onde serão aplicadas a regra de ACL, tem valor 31, representado um bloco de 32 (192.168.113.0 até 192.168.145.0). Esse intervalo é maior do que o que o intervalo que queremos, mas serve ao propósito. O quarto octeto contêm um valor de 255, que permite a presença de qualquer valor, e nos garante que todos os hosts nessas sub-redes sejam também contemplados com a regra ACL.

De volta à questão, a primeira sentença aplica a regra de que será descartado qualquer pacote SMTP (porta 25) com origem em quaisquer dos hosts em 10.1.1.128 até 10.1.1.192 (wildcard = 0.0.0.63, bloco igual a 64). A segunda regra descarta todos os pacotes com destino ao serviço de Telnet (porta 23). Logo a seguir, essas 2 regras são aplicadas à interface E0 (ethernet0) para saída (“out”), ou seja, em “post-routing”, após o pacote ter sido roteado localmente no roteador e estar prestes a ser encaminhado para a interface de saída, as regras são aplicadas. A princípio, até aí tudo bem, temos 2 regras, uma que nega totalmente serviços para a porta 23, e outra que nega serviço SMTP (porta 25) para um conjunto de hosts. A alternativa C parece convidativa, mas algo vai errado na lista de acesso: se era esse o fim almejado pelo administrador (negar pacotes para serviços portas 23 e 25), ele deveria ter incluído a regra “permit ip any” no final da lista de acesso, porque a última regra é “deny ip any”, o que faria com que qualquer pacote tivesse o repasse concedido pela interface ethernet0. Devido à omissão dele, a interface E0 vai perder comunicação com o mundo. Alternativa D é a correta.

RIP Troubleshooting

Continuando na linha dos enunciados que abranjam o maior número de conceitos, temos essa questão, que apresenta pontos importantes e que costuma marcar presença nas seções da prova CCNA relacionadas a troubleshooting e protocolos de roteamento:

“Which of the following is true regarding the following output? (Choose two.)

04:06:16: RIP: received v1 update from 192.168.40.2 on Serial0/1

04:06:16: 192.168.50.0 in 16 hops (inaccessible)

04:06:40: RIP: sending v1 update to 255.255.255.255 via FastEthernet0/0 (192.168.30.1)

04:06:40: RIP: build update entries

04:06:40: network 192.168.20.0 metric 1

04:06:40: network 192.168.40.0 metric 1

04:06:40: network 192.168.50.0 metric 16

04:06:40: RIP: sending v1 update to 255.255.255.255 via Serial0/1 (192.168.40.1)

A. There are three interfaces on the router participating in this update.

B. A ping to 192.168.50.1 will be successful.

C. There are at least two routers exchanging information.

D. A ping to 192.168.40.2 will be successful.”

Um ponto que merece destaque nessa questão é procurar listar o que ela quer que você saiba, a partir da situação exposta. Na assertiva A, o que ela procura saber sobre a quantidade de interfaces de rede. As assertivas B e D, sobre a conectividade com as redes 192.168.40.0 e 192.168.50.0, ou melhor, se pacotes ICMP “ping” podem ser enviados e recebidos com sucesso para essas redes. A letra D pede o número mínimo de roteadores na transação acima.

Para saber exatamente quantas interfaces estão participando no cenário acima, é útil olhar cuidadosamente nos trechos do log que mencionam atualizações (updates) de tabelas de roteamento RIP, saindo do roteador atual para o mundo externo. As linhas 3 e 8, do log em negrito, anunciam envios (sending) para atualização de tabelas de rotas, que passam respectivamente, “via FastEthernet0/0” e “via Serial0/1”. Como não existem mais mensagens desse tipo (“sending v1 update”), do acima exposto podemos deduzir que apenas 2 interfaces de rede são apresentadas. A assertiva A é falsa, pois alega um mínimo de 3 (o mínimo é 2).

Dos questionamentos sobre o número de interfaces no roteador, partimos para a quantidade de roteadores que participam das mensagens de debug do RIP, anunciando e/ou recebendo rotas novas. Se mensagens do tipo “sending v1 update” nos ajudaram a encontrar as interfaces de rede, as mensagens “received...” vão nos dizer quais (e principalmente quantos) roteadores participam do handshake do RIP pra estabelecimento dinâmico de rotas, uma vez que apenas roteadores podem anunciar e atualizar rotas. Do parágrafo anterior, vemos que esse roteador anuncia (mensagens “sending...”) através de 2 interfaces (Serial0/1 e FastEthernet0/0), e recebe uma atualização de rotas através da Serial0/1 (do roteador 192.168.40.2). Temos 2 roteadores, um que é o roteador local (a partir do qual temos acesso à mensagem de log), e outro que emite uma mensagem de anúncio de rotas (192.168.40.2, via interface Serial0/1). A letra C está certa.

Restam-nos as letras B e D. As linhas 2 e 7 nos dizem a mesma coisa, ou seja, que a rota para a rede 192.168.50.0 é “alcançada” após 16 hops, e portanto inalcançável (linha 2). A linha 7 nos descreve que essa mesma rede tem métrica 16, o que significa a mesma coisa, em vista do fato de que o RIP tem métrica máxima de 15, para rotas possíveis e roteáveis. Métrica 16 é rota inacessível, desligada pelo administrador ou “envenenada” pelo próprio algoritmo do RIP, para evitar anúncios de circulares de rotas impossíveis (estratégia conhecida como “poisonous routing”, envenena a rota e anuncia ela desse jeito, para que as outras redes a enxerguem como proibida e assim evitar que outros roteadores na área administrativa anunciem essa rota inválida a outros roteadores). Como esse host 192.168.50.1 faz parte da rede 192.168.50.0, e como essa rede é métrica 16, um ping para esse host retornaria uma mensagem de inalcançável. Letra “B” está errada.

A letra D quer saber se um ping para o host 192.168.40.2 pode ser alcançável, e a resposta é sim, e temos 2 evidências para garantir isso: primeiro, que na linha 6 vemos que quando o roteador vai construir as entradas da tabela de roteamento, momento no qual algumas rotas dinâmicas externas são reconhecidas e acrescentadas, a rota para a rede 192.168.40.0 apresenta-se com métrica 1 – isso quer dizer que a rota para essa rede passará primeiro pelo “next hop router”, ou seja, o roteador vizinho, conectado pela interface Serial0/1. Uma métrica ótima, que perde apenas para as métricas de rotas estáticas e para as diretamente conectadas (as com flag “S” e as com métrica 0, respectivamente). Isso serviria para garantir que a rede 192.168.40.0 é acessível, mas não que um ping para o host 192.168.40.2 pode ser realizado com sucesso. Contudo, a primeira linha de log nos garante isso, porque o anúncio da tabela de rotas para essa rede veio exatamente do roteador de endereço IP 192.168.40.2. Uma coisa legal com roteamento dinâmico é que as rotas são configuradas nas 2 direções, e se recebemos uma mensagem de 192.168.40.2, certamente que poderemos enviar mensagens para lá também (a menos que uma ACL tenha sido colocada de barreira, impedindo tráfego ICMP de saída no roteador conectado à S0/1). A letra D está correta também.

Respostas: C e D