Los Hipercubos como Grafos de Cayley.

0. Introducción.

En ésta entrada presentamos, en tres puntos, tres artículos científicos sobre la relación de los Dígrafos / Grafos de Cayley con las Redes de Interconexión de sistemas HPC / Supercomputadores. 

Es decir hablamos de las System Area Networks o SAN, tecnología que se está aplicando desde hace tiempo también a las Chip area Networks (CAN), cómo  los NoCs y PLDs).

En las redes LAN y WAN, que emergen / crecen de manera más natural y no sólo por diseño, y por lo tanto no necesariamente son regulares (aunque tienen otras propiedades conocidas), hasta ahora se han aplicado otro tipo de tecnologías, pero como comentamos en el apéndice ésto está empezando a cambiar ahora (tesis, 2014), al menos desde el punto de vista de las propuestas. Y esto tiene sus motivaciones. Por ejemplo la red WAN más conocida, Internet (hay otras como las decadentes redes ATM)como es bien conocido está empezando a tener problemas para escalar: la propia Internet Arquitecture Board reconoce que el BGP (Border Gateway Protocol), basado en Tablas de Router (RTs) que empiezan a ser exponenciales tendrá problemas en un futuro cercano y se están, de momento, proponiendo alternativas más estructuradas. Y los mismo está pasando con las importantes LAN que son los Data Centers  (que además están más sujetos a diseño): tecnologías emergentes como el Cloud, las Smart Cities, Bring you own device y el Internet de las cosas, si acaban de cuajar (evento que no está tan claro), reventarán la capacidad de las redes actuales. Además sin éstas nuevas tecnologías, las actuales no aprovechan de manera óptima los recursos.

Uno de los artículos  de los que hablamos se escribió  en 1992 por dos investigadores vinculados a la NSA (Agencia de Seguridad Nacional de EEUU) y se ha desclasificado en 2011. Creo que la opinión, juicio de valor, evaluación o como se quiera llamar que ofrezcan dos miembros de ésta agencia sobre un método tiene “más” valor que la que puedan ofrecer investigadores que trabajen en empresas o académicos, cada uno de ellos sujetos a determinados intereses institucionales y personales. Si no más valor, al menos es otro punto de vista al habitual.  Por otra parte han pasado casi dos décadas desde su publicación y hay que tenerlo en cuenta a la hora de leerlo (comentamos  sobre ésto más en detalle más  adelante).  

800px-National_Security_Agency_headquarters,_Fort_Meade,_Maryland

Antes de empezar recordamos que hay básicamente dos tipos de redes de interconexión, las directas (o estáticas, o de conmutación distribuida) y las indirectas (o dinámicas, o de conmutación centralizada, aquellas en las que los nodos procesadores se comunican entre ellos no directamente a través de un router sino a través de una red de conmutadores o switches),  que compiten en el mercado. A diferencia de los que pasa en el cerebro humano (todos tenemos una “arquitectura” similar aunque no exactamente igual),  en redes de interconexión CAN (Chip Area Network) y SAN (Systema area Network) todavía no hay un paradigma que se haya impuesto definitivamente. Y en ocasiones hay una cierta convergencia, con redes jerárquicas (como por ejemplo la del sistema Roadrunner) o híbridas  (es decir aquellas en las que cada nodo se enlaza a varias redes diferentes, como por ejemplo la de los sistemas Blue Gene / P de IBM, que tienen primero, un toro 3-D para comunicaciones punto a punto, segundo una de tipo tree optimizada para determinadas operaciones colectivas y tercero una de tipo anillo para otras operaciones colectivas; nótese el ahorro en cable quese obtendría de poder implementar estas operaciones colectivas de manera eficiente en una sola red….). Por otra parte recordamos que una red de interconexión es mucho más que una topología y que las decisiones de diseño son múltiples. Los Grafos de Cayley se utilizan como  modelos sobre todo para las primeras, las directas (aunque también para algunas indirectas).

Para las indirectas aparentemente se ha impuesto la “arquitectura” de tipo Fat Tree (The fat tree is the topology of choice across a wide range of network sizes for most commercial systems that use multistage interconnection networks. Most SANs used in multicomputer clusters and many used in the most powerful supercomputers are based on fat trees. Commercial communication subsystems offered by Myrinet, Mellanox, and Quadrics are also built from fat trees; multistage es otro nombre para las redes indirectas; SAN es systema area network. Fuente. 2000;  diría lo descrito sigue siendo la realidad en 2015).

No vamos a hablar de las indirectas en ésta ocasión. Sólo comentar que, al igual como veremos que la topología hipercubos / toros (k-ary n-cube), la arquitectura Fat Tree (k-ary n-tree) también tiene ciertos problemas para escalar. A estos efectos baste de momento un extracto de éste documento de Prace de 2012 sobre las tecnologías disponibles  para el reto exaescalar: Fat Tree topology is typical of x86 Linux based cluster while N dimensional torus is mainly used in specialist HPC systems such as IBM’s Blue Gene, Cray’s XE6 and Fujitsu’s K computer. A Fat Tree topology has the advantage of allowing a fully interconnected machine with a full bisection bandwidth. On the other hand, in a Fat Tree topology the number of switches and cables scale more than linearly with the number of nodes. It has been estimated that for an implementation of a state of the art Fat Tree topology using InfiniBand switches, to connect a machine with 11664 nodes (maximum dimension using the largest switches available) will require 100km of optical cables, 648 Level 1 36-port switches and 18 Level 2 648-port switches. This behaviour makes the Fat Tree topology a solution that can hardly be adopted on machines with million of nodes in the Exascale roadmap). ¡¡ 100 km de cable !!. En base a similares parámetros un bloguero estimaba que un computador exaescalar con tecnología Fat Tree podría costar entre 6 y 7 billones de euros; según otra estimación estaríamos en unos 26 billones de usd, para una red de 128.000 nodos y una ancho de banda de 200GB/s por nodo. En el documento Prace apuestan más bien por las topologías hipercúbica /tóricas para esas escalas, pero he visto otras opiniones. Como veremos estas también tienen serias limitaciones.

848102-Fat-Tree-0

Volviendo al tema principal que nos ocupa, en el primer artículo, de ¿ 2006 ? muestran algunas de las limitaciones de los hipercubos así como por qué es conveniente que en una topología que va a ser la base de una red de interconexión real tenga recorridos hamiltonianos; en el segundo, de 1992, hablan sobre la conveniencia de los grafos de Cayley para modelar redes de interconexión así como de enrutamiento en estos grafos por caminos más cortos (shortest path); en el tercero, de 1998, un matemático demuestra que los hipercubos de cualquier dimensión son Grafos de Cayley. Por el camino citamos muchos otros artículos relevantes.

1. Las limitaciones de la familia de grafos llamados Hipercubo. 

Estoy leyendo sobre redes de interconexión (RI).

Cuando se habla de redes de interconexión directas, se pone siempre el ejemplo de los Hipercubos, que no obstante no escalan bien ya que a partir de un determinado número de nodos (del orden de miles) al aumentar el grado de los vértices linealmente con la dimensión, su coste empieza a ser prohibitivo. El coste de un sistema HPC o supercomputador depende en gran parte del número de cables y de switches / routers y el primer número, el de cables (no tengo claro si es así también para el segundo en redes directas) dependen a su vez del grado.

Para subsanar esta deficiencia se ha diseñado las redes k-arias d-cubos, que son una generalización de los hipercubos (también se les llama toros).

Título. Distributed algorithms for building Hamiltonian cycles in k-ary n-cubes and hypercubes with faulty links. ¿ 2006 ?

Autor. Iain A. Stewart

Extracto.

Numerous interconnection networks have been proposed as underlying topologies for parallel computers.

As to which network is chosen depends upon a number of factors relating to the topological, algorithmic and communication properties of the network and the types of problems to which the resulting computer is to be applied.

One of the most popular interconnection networks is undoubtedly the n-dimensional hypercube Qn. Some of its pleasing properties, with regard to parallel computation, include: it is node- and link-symmetric; it is Hamiltonian; it has diameter n; it has a recursive decomposition; and it contains, or “nearly” contains (as subgraphs), almost all interconnection networks currently vogue in parallel computing (see [29] for these results and more on the hypercube).

Some of the commercial machines whose underlying topology is based on the hypercube are the Cosmic Cube [37], the Ametek S/14 [8], the iPSC [21, 22], the Ncube [14, 22] and the CM-200 [15].

However, every node of Qn has degree n, and consequently, as n increases so does the degree of every node. High degree nodes in interconnection networks can lead to technological problems in parallel computers whose underlying topology is that of the said interconnection network.

One method of circumventing this problem, so as to still retain a “hypercube-like” interconnection network, is to build parallel computers so that the underlying topology is the k-ary n-cube Qk n . The k-ary n-cube Qk n is similar in essence to the hypercube, but by a judicious choice of k and n we can include a large number of nodes yet keep the degree of each node fixed. For example, the hypercube Q12 has 4096 nodes and every node has degree 12. However, Q16 3 has 4096 nodes and every node has degree 6. Of course, one usually loses out in some other respect (for example, in terms of diameter) but often this loss is not too catastrophic.

The k-ary n-cube Qk n has not been investigated to the same extent as the hypercube, but it is known to have the following properties (amongst many others): it is nodeand link-symmetric [7]; it is Hamiltonian [9, 12]; it has diameter n⌊k/2⌋ [9, 12]; it has a recursive decomposition; and it contains many important interconnection networks such as cycles (of certain lengths) [7], meshes (of certain dimensions) [9] and even hypercubes (of certain dimensions) [12]. Machines whose underlying topology is based on a k-ary n-cube include the Mosaic [38], the iWARP [11], the J-machine [32], the Cray T3D [26] and the Cray T3E [5]

Como se ve entre las propiedades recomendables de los hipercubos y su generalización está el tener ciclos hamiltonianos.  ¿ Por qué  es conveniente que una red de interconexión esté basada en una topología que tenga ciclos hamiltonianos ?:

The existence of a Hamiltonian cycle in an interconnection network is extremely useful as, for one thing, it facilitates all-to-all broadcasts, with messages being “daisy-chained” around the cycle.

Also, the existence of a Hamiltonian path between two nodes enables algorithms designed for linear arrays to be simulated in the (faulty) k-ary n-cube.

Es decir determinar la existencia (o dar los pasos necesarios para poder determinarla) de recorridos hamiltonianos en topologías que se puedan utilizar como base de redes de interconexión es altamente útil desde el punto de vista práctico. Sin embargo el examinador de mi segunda solicitud de patente ha considerado que los métodos que yo he descubierto para resolver ésto en un familia importante de dígrafos de cara a las aplicaciones no son más que ideas abstracta s que no pueden ser objeto de una patente. ¿¿¿???. Increíble pero cierto. 

Es más, diría y quizás estoy especulando que muy posiblemente las investigaciones se han centrado tanto en este tipo de topologías ya que investigar el problema de recorridos hamiltonianos en otras basadas en Dígrafos de Cayley es más complejo.

It is well known that Qn and Qk n possess fault-free Hamiltonian cycles in the presence of at most n − 2 and 2n − 2 faulty links, respectively; indeed, under the additional modest assumption that a node in Qn or Qk n is incident with at least 2 healthy links, there are still Hamiltonian cycles in Qn and Qk n when there are 2n − 5 [16] and 4n − 5 [6] faulty links, respectively, and these results are optimal.

Obviamente conocer la existencia de recorridos hamiltonianos en un Dígrafo no es suficiente y para las aplicaciones además se necesita construirlos. Por eso nosotros hemos dado también un método eficiente de construcción (que está patentado en la primera patente).

However, the existence of a Hamiltonian cycle is not necessarily sufficient for algorithmic viability as the cycle needs to be constructed, and not by a centralized algorithm which necessarily takes time exponential in n, but by a distributed algorithm which hopefully will run in polynomial-time and have minimal message-passing overhead.

Terminamos comentando que una de las grandes ventajas del hipercubo y su generalización es que  permiten simular otras topologías, propiedad muy deseable. Además, a diferencia de otras propuestas basadas en el grupo simétrico con muy poca oferta de tamaños, las redes hipercúbicas y sobre todo sus generalizaciones, las redes tóricas se ofrecen para múltiples tamaños. Gracias a las técnicas de nuestra patente se abre el abanico de familias de redes escalables (teniendo poca diferencia en el número de nodos, y manteniendo las mismas propiedades).

El caso es que al día  de hoy para los tamaños que empiezan a tener los sistemas HPC o que se pretende que tengan en los próximos años (reto exaescalar), las redes hipercúbicas / tóricas empiezan a no ser una buena opción por las limitaciones señaladas. Y ya hemos dado un apunte  que indica que tampoco los paradigmas indirectos que existen hoy lo son.

Pero tampoco hay, de momento, pese a las múltiples propuestas, hay una mejor alternativa. Un destacado investigador, académico pero muy enfocado a la transferencia tecnológica a la industria (con varios casos de éxito en su haber),  en su libro (del que es co-autor) se manifestaba muy escéptico con todas estas propuestas de cara a las aplicaciones reales (most of them were proposed with the goal of minimizing the network diameter, given a number of nodes and a node degree. As will be seen in chapter 2, fo pipelined switching techniques, network latency is almost insensitive to network diameter, specially when messages are long. So it is unlikely that those topologies are implemented). Ahora mismo me veo incapaz de evaluar ésta opinión. El libro se publicó en 2003 y de momento seguimos con las mismas topologías que entonces y por lo tanto es muy respetable. No se que pensará actualmente al respecto. En fin, y tampoco comparar diferentes diseños de redes de interconexión es una actividad sencilla. Ésto hace que las nuevas propuestas, perfectamente justificadas, no terminen de cuajar.

Por otra parte, al igual que otros componentes, como procesadores, memorias etc…el sector de las redes de interconexión, en cuanto a las redes implementadas en sistemas reales ha sido bastante dinámico, como se puede ver en las estadísticas del Top500.

Un buen resumen de la “dinámica topológica” referida al Top10 del Top500 se puede encontrar en éste libro, capítulo primero, del cual extractamos la siguiente imagen. Se recomienda la lectura del todo el capítulo. Nótese que el Top10, que incluye en todo momento a la vanguardia tecnológica del sector HPC, no es para nada representativo de los que pase en el resto de los 490 sistemas de la lista, como demuestra la segunda imagen extraída de ésta presentación.

dinámica de las topologias

Dinámica Topológica de los Sistemas HPC. Topological Dynamics of HPC systems.

Topologías HPC en el Top500

Topologías HPC en el Top500

Perteneciendo el campo de las topologías HPC al de las áridas tecnologías, no se puede hablar de modas, aunque en apariencia la dinámica es similar al de éstas…

Antes de los años que aparecen en la imagen la topología prevalente era el Hipercubo, topología que llegó a tener una serie de Conferencias, sólo para ella, que comenzaron en 1986. El autor del artículo explica claramente las razones de la caída en desgracia del hipercubo: primero, no hay importantes aplicaciones para las que el hipercubo encaje como el guante a la mano (y si las hay para otras que lo han sustituido como el toro 3-d; segundo, la escasez de oferta para todos los tamaños (su número de vértices se duplica en cada incremento), tercero y más importante, el problema del aumento del grado con la escala, en relación con las limitaciones de los commutadores (número de pins) y cuarto, también relacionado con la dimensionalidad, el hecho de que topologías de elevadas dimensiones, cuando son empotradas en espacios de menores dimensiones (como el plano en aplicaciones VLSI) requieren cables más largos.

Las lecciones son claras: la escala ha sido importante para la funcionalidad de las topologías. A partir de un determinado tamaño los hipercubos, que eran topologías óptimas para los tamaños inferiores, se han quedado fuera de juego. Y no veo porque no le puede pasar los mismo a las topologías prevalentes ahora. A esto hay que añadir lo que señala el autor del artículo: las nuevas tecnologías que se están introduciendo continuamente favorecen a una u otra topología.

Todos estos factores hacen que las continuas propuestas de nuevas topologías tengan todo el sentido y que ésta situación sea favorable al desarrollo de nuevas herramientas que faciliten encontrar las redes de interconexión adecuadas para la nueva escala y las nuevas tecnologías. Sin embargo un examinador de la USPTO considera que ésto no son más  que ideas abstractas, materia no patentable.

En este momento no podemos dejar de acordarnos de SiCortex, que basó su negocio en una red de interconexión innovadora (basada en los grafos de Kaufman, que no son de Cayley), pero que duró poco (2003-2009).

Nota (actualización sábado 13 de 2015. Entiendo que otra posibilidad es frenar el escalado en el número de nodos y centrarse en aumentar la capacidad (el número de procesadores) de cada nodo, aumentando el ancho de banda de la red para mantener el equipo equilibrado (ver por ejemplo el roadmap de Infiniband el protocolo de red más aceptado, y que es compatible con las  dos topologías de las que hemos  hablado, el fat-tree y las tóricas). Obviamente esto tiene sus límites pues  los procesadores del nodo también se conectan mediante una red y entiendo que diseñar una red NOC no es más sencillo que diseñar una red SAN. De cualquier manera intentaré averiguar sobre ésta posibilidad…

IBTA_Roadmap v2014-11-12

Estas consideraciones me hacen concluir que tiene interés una economía de los sistemas HPC que intente predecir los parámetros de un sistema HPC en el futuro lejano. El tipo de preguntas que nos interesan son,  por ejemplo, ¿ tendrá más núcleos que procesadores o todo lo contrario ? o ¿ Existe algún límite “natural” sea tecnológico o económico al tamaño de un supercomputador, tal que a partir de éste tamaño es mejor hacer más unidades de éste tamaño que incrementar el  tamaño de los existentes ?. En la serie Trade Lane Megacities, ya nos hemos preguntado algo similar con respecto a los buques y llegamos a la conclusión de que incluso con demanda ilimitada, para cada nivel tecnológico / coste de infraestructura portuaria, sí existe un tamaño óptimo de los buques mercantes.

Claramente el respectivo coste de diseño de una red on-chip y de una red externa es clave así como los anchos de banda que se consigan en uno u otro (ojo, primera impresión, puedo estar equivocado y/o puede haber otros parámetros a tener en cuenta; no se debe de olvidar por ejemplo la memoria). Haré una entrada sobre ésto cuando lo tenga más claro…

Algunos datos, enlaces para empezar:

–cualquier discusión de éste tipo debe de tener en cuenta las así llamadas “leyes” de Moore (1965), Dennard scaling (1974), Amdahl, Gustafson, Grosch, Metcalfe-Network, regla de Rent (¿ 1960 o 2005 ?, ¿ ejemplo  de secreto comercial ?), y otras.

los chips multinúcleo o multicore.

la explicación de Intel de por qué se tuvo que pegar el salto en mejoras en la frecuencia y arquitectura de uniprocesadores al multicore.

En definitiva la ley de Moore, que afirma que cada 18 meses se duplican el número de transistores va a seguir vigente por un tiempo con la tecnología MOSFET, pero por los motivos explicados (básicamente el heat wall), ésta mayor cantidad de recursos computacionales (más transistores en la misma superficie), ahora se tiene que dirigir a otros fines que no sean aumentar la frecuencia de reloj. Por ejemplo a reducir el consumo energético, a paralelismo (o sea multicore) etc…

La tendencia industrial hacía el multicore es clara, pero no está tan claro que sea tan solida como lo fue la tendencia hacía el aumento de frecuencia de reloj. No tengo claro de momento si existe una buena teoría del multicore. Que yo no lo tenga claro no quiere decir que la industria tampoco lo tenga claro; ya se sabe que no dan puntada sin hilo.

Sí existen varias publicaciones que indican sus limitaciones, las tecnologías que se deben de mejorar para mantener el equilibrio (multicore, even without multithreading too, is still a good thing. It can be used, for example, to allow multiple programs on a desktop system to always be executing concurrently. Multithreading, even without multicore too, is still a good thing. Threads can make it easier to logically have many things going on in your program at a time, and can absorb the deadtime of other threads. But, the big gain in performance is to use both to speed up a single program. For this, we need a combination of both multicore and multithreading).

La ley de Amdahl aplicada a la tecnología multicore.  Bastante técnico. Parece que la ley de Moore trasladada al multicores sería duplicar el número  núcleos por chip cada dos años.

Dark Silicon and the End of Multicore Scaling. 2011. El artículo más citado sobre un problema que ya existía antes de los multicore pero que se ha agudizado con las elevadas densidades que los acompañan: para evitar el recalentamiento no se pueden activar todos los transistores del chip y esto hace que este funcione por debajo de su rendimiento potencial. Ya hay varias posibles soluciones que se están explorando: reducir la superficie; la solución dim que pasa por consideraciones energéticas (architectural techniques that spend area to buy energy efficiency); la solución vía especialización (The specialized horseman uses dark silicon to implement a host of specialized coprocessors, each either much faster or much more energy efficient (100 to 1,000) than a general-purpose processor; me parece interesante: en las fabricas físicas también se están sustituyendo computadores universales, es decir los seres humanos por otros más especializados pero aún así más eficientes en lo  suyo, los robots); y la solución deus ex machina, que sería complicado de explicar en unas líneas (for dark silicon, one deus ex machina would be a breakthrough in semiconductor devices, es decir un backtraking radical). Una entrevista al autor dónde explica el fenómeno.

–Un curioso, denso y reciente artículo que repasa los límites (de todo tipo) a la computación: Limits on Fundamental Limits to Computation. Aunque en mi opinión el artículo ofrece al final menos de lo que promete, contiene una tabla resumen interesante, y es un buen catálogo de límites, en diferentes aspectos (de ingeniería, de diseño, de energía, de espacio/tiempo y de complejidad computacional) y a diferentes niveles. Demasiado ingenieril; algo de filosofía lo haría más interesante.

Interconnect Limits on Gigascale Integration (GSI) in the 21st Century. Un artículo de 2001. Extracto: The International Technology Roadmap for Semiconductors (ITRS) projects that by 2011 over one billion transistors will be integrated into a single monolithic die [1]. The wiring system of this billion-transistor die will deliver power to each transistor, provide a low-skew synchronizing clock to latches and dynamic circuits, and distribute data and control signals throughout the chip. The resulting design and modeling complexity of this GSI multilevel interconnect network is enormous such that over 10 coupling inductances and capacitances throughout a nine-to-ten-level metal stack must be managed. A seminal paper [2] focuses on the transistor limits for a GSI system; therefore, this paper will address the limits that on-chip interconnects place on a GSI system design in the 21st century. 

Una presentación de los mismos autores. ExtractoMiniaturization does not enhance interconnect performance!!

Fin de nota (actualización 13 de junio).

2. El artículo desclasficado por la NSA: el problema de enrutamiento por caminos más cortos en Grafos de Cayley, equivalente a factorización en grupos de permutaciones. 

Como todo esto son conceptos abstractos sin ninguna relación concreta con las aplicaciones (espero que el lector pueda captar el tono de indignada ironía), la NSA financió en 1992 del siglo pasado una investigación que sólo desclasificó en 2011.

DOCID: 3929129 approved for release by NSA on 12-01-2011 ,Transparency Case# 63853

Título. Processor Interconnection Networks from Cayley Graphs. 1992

STEPHEN T. SCHIBELL and RICHARD M. STAFFORD

Sobre los autores:

As a student of computational group theory, Stephen honed his proficiency for analyzing algorithms and data structures under the tutelage of his professor, Charles Coffin Sims, the developer of permutation group software. A mathematics prodigy, Stephen also reviewed Sims’ book, “Computation with Finitely-presented Groups,” Volume 48 of the Encyclopedia of Mathematics.

Stephen authored and co-authored numerous mathematical publications including 25 papers, 21 of which were classified. Stephen conducted unclassified research that can be regarded as a first attempt to find general purpose routing algorithms for interconnection networks. He co-authored “Processor Interconnection Networks From Cayley Graphs,” and an article that was featured in Discrete Applied Mathematics, The Journal of Combinational Algorithms, Informatics and Computational Sciences. His classified works ranged over several secret matters of strategic importance to the NSA that were essential to the security and safety of the United States of America

UNCLASSIFIED Editor’s Note: This paper will appear in a special issue of Dilcrem Applied Mathematics devoted to Electl’ical Engineering and Graph Theory.

Abstract. This paper is divided into three sections. In the first section we discuss Cayley graphs and show how they may be used as a tool for the design and analysis of network architectures for parallel computers. In the second section we present our research on the routing problem. This research can be regarded as a first attempt to find general purpose routing algorithms for interconnection networks. In the last section we considerthe problem ofconstructingCayley graphs that meetspecific design parameters.

Antes de entrar en detalle sobre el contenido del artículo conviene comentar sobre la fecha: el lector pensará que los juicios emitidos en una publicación de 1992 no tienen valor en 2015.

Para demostrar que esto no es correcto reseñamos algunas surveys o artículos que se han ido publicando posteriormentes sobre el mismo tema. Varias comunidades de investigadores estudian el tema sobre el que hablamos: ingenieros de telecomunicaciones, ingenieros computacionales, matemáticos algebraicos, matemáticos de teoría de grafos etc…Nos interesa sobre todo un enfoque ingenieril lo más apegado posible a las aplicaciones reales:

–1989. El survey ingenieril clásico sobre Grafos de Cayley y redes de interconexión es A group-theoretic model for symmetric interconnection networks, de Akers y Krishnamurthy.

–1999.  Cayley Graphs and Interconnection Networks (Marie-claude Heydemann, Bertrand Ducourthial);

–2009. A New Family of Cayley Graph Interconnection Networks Based on Wreath ProductZhen Zhang, Xiaoming Wang. Extracto: Design of interconnection networks is an important integral part of any parallel processing or distributed systems. Performance of the distributed system is significantly determined by the choice of the network topology. Desirable properties of an interconnection network include low degree, low diameter, symmetry, low congestion, high connectivity, and high fault tolerance. For the past several years, there has been active research on a class of graphs called Cayley graphs because these graphs possess many of the above properties….These graphs have optimal fault tolerance and logarithmic diameters. The shortest path routing and embedding of a Hamiltonian cycle, meshes, and hypercubes are also discussed. R.K.Das and B.P.Sinha develop a new network topology with odd degrees [7]. The point-to-point routing and one-to-all routing algorithms are also developed.

–2007. Structural properties of Cayley digraphs with applications to mesh and pruned torus interconnection networks. En éste artículo de Xiao y Parhami se pone de manifiesto el valor del enfoque que hemos seguido en nuestra investigación:  Despite numerous interconnection schemes proposed for distributed multicomputing, systematic studies of classes of interprocessor networks, that offer speed-cost tradeoffs over a wide range, have been few and far in between. A notable exception is the study of Cayley graphs that model a wide array of symmetric networks of theoretical and practical interest. Properties established for all, or for certain subclasses of, Cayley graphs are extremely useful in view of their wide applicability.

–2009. Relationships among popular interconnection Networks: Generalization of Cayley Graphs Generated by Transposition Trees Connectivity, Decomposition and Orientation. Resumen. Star generated graphs were proposed as an attractive alternative to hypercubes for massive parallel computing in early 1980s, due to sublogarithmic regularity and diameter. However, star graphs suffer from n! vertices. As the gaps between (n-1)! and n! grow too fast to be considered for practical implementation. (n,k)-Arrangement graphs and (n,k)-Star graphs were proposed as a remedy for n! problem. Star graphs are one extreme case in a general class of Cayley graphs generated by transposition trees. This work generalizes Cayley graphs generated by transposition trees to a class that contains both (n,k)-Arrangement graphs and (n,k)-Star graphs as special cases. Moreover connectivity properties, decomposition methods, relationships among different classes of interconnection networks and local orientation rules are derived. Finally, even more general and flexible class of interconnection networks is introduced.   

–2012. Lecture notes on some problems on Cayley graphs. Elena Konstantinova. Extracto. The definition of Cayley graph was introduced by Arthur Cayley in 1878 to explain the concept of abstract groups which are generated by a set of generators in Cayley’s time. This definition has two main historical sources: group theory and graph theory….There is also a big branch of mathematics in which algebraic methods are applied to problems about graphs. This is algebraic graph theory involving the use of group theory and the study of graph invariants. One of its branches studies Cayley graphs that are symmetrical graphs with properties related to the structure of the group. In the last fifty years, the theory of Cayley graphs has been developed to a rather big branch in algebraic graph theory. It has relations with many practical problems, and also with some classical problems in pure mathematics such as classification, isomorphism or enumeration problems. There are problems related to Cayley graphs which are interesting to graph and group theorists such as hamiltonian or diameter problems, and to computer scientists and molecular biologists such as sorting by reversals. In these Notes we present some problems on Cayley graphs dealing with combinatorial and structural properties of graphs. First of all, we pay attention to the hamiltonian and diameter problems on Cayley graphs defined on the symmetric group…We also show how these graphs connect with applied problems in molecular biology and computer sciences. It is known that Cayley graphs are used in the representation of interconnection networks. The vertices in such graphs correspond to processing elements, memory modules, and the edges correspond to communication lines. The main advantage in using Cayley graphs as models for interconnection networks is their vertex–transitivity which makes it possible to implement the same routing and communication schemes at each node of the network they model. Furthermore, some of them have other advantages such as edge–transitivity, hierarchical structure allowing recursive construction, high fault tolerance and so on. Al estudiar los problemas de hamiltonicidad y diametro se centra sobre todo en los Pancake Cayley graphs. 

2012. An Efficient Algorithm for the Diameter of Cayley Graphs Generated by Transposition Trees Ashwin Ganesan. Extracto. Cayley graphs possess a certain amount of symmetry. In a symmetric network, the topology of the network looks the same from every node. It is now known that many families of symmetric networks possess additional desirable properties such as optimal fault-tolerance [8], [9], algorithmic efficiency [10], optimal gossiping protocols [11] [12], and optimal routing algorithms [13], among others, and so have been widely studied in the fields of interconnection networks. New topologies continue to be proposed and assessed [14]. Cayley graphs, permutation groups, and distance-related questions continue to be an active area of research, and have also found applications in computational biology [15] and wireless sensor networks [16].

The diameter of a network represents the maximum communication delay between two nodes in the network. The design and performance of algorithms or bounds that determine or estimate the diameter of various families of Cayley graphs of permutation groups is of much theoretical and practical interest. The problem of determining the diameter of a Cayley network is the same as that of determining the diameter of the corresponding group for a given set of generators; the latter quantity is defined to be the minimum length of an expression for a group element in terms of the generators, maximized over all group elements. This diameter problem is difficult even for the simple case when the symmetric group is generated by cyclically adjacent transpositions [17]. The pancake flipping problem, which corresponds to determining the diameter of a particular permutation group, was studied in [18], and while some bounds were given there and an improvement was made recently [19], this problem remains open as well.

2012. Distributed Computing and Internet Technology: 8th International Conference ICDCIT. Artículo. MSTAR: a new two level interconnection network. En éste artículo bastante reciente se ponen de manifiesto, primero, las limitaciones de las redes de tipo hipercubo, y segundo, que actualmente no existe una buena alternativa. 

2013, julio. Borel Cayley Graph-Based Topology Control for Consensus Protocol in Wireless Sensor Networks. Este artículo se sale un poco de las redes de interconexión de sistemas HPC que estamos estudiando pero es interesante pues uno de sus autores es investigador de Intel. Por otra parte también la hamiltonicidad es una propiedad deseable. Extractos. We approach topology control with predefined graphs. Structured graphs have been studied for a long time and are good candidates for interconnection networks [14, 15]. Various graph-based interconnection networks have been applied to wavelength division multiplexed optical networks [15], satellite constellations [16], and chip design [17]. In peer-to-peer overlay network schemes, various structured graphs are investigated and compared to unstructured P2P overlay network [18]. Examples of P2P overlay networks include k ring lattices with Chords [19], de Bruijn graphs with Koorde, and distance halving [20, 21]. There is theoretic analysis to apply de Bruin and Cayley graphs to P2P [22, 23]. Graph-based wireless sensor networks have also been explored by other researchers [2428]. In general, a predefined graph topology with its deterministic connection rule facilitates performance analysis. In addition, some offer symmetry, hierarchy, and hamiltonicity, and can have a constant low degree and existing distributed routing protocol, all preferable properties for WSNs. // We focus on Borel Cayley graphs, a member of Cayley graph family [29]. In [30], it was shown that Borel Cayley graphs have potential to be efficient logical topologies for dense WSNs because of their small degree and short diameter. Also, BCGs are symmetric graphs, a property that enables distributed routing [31]. One of BCG applications is the consensus protocol, a distributed node-to-node message exchange rule to drive nodes to an agreement for a quantity of interest [32]. BCGs showed good performance when compared to mesh, torus, and small world networks [33]. Más sobre los grafos de Cayley de borel aquí, de 2010.

805635.fig.001a

Cómo se ve, realmente ya no tendría mucho sentido un survey general y sí algunos especializados.

Pasamos ya a extractar algunas partes del artículo que ha motivado el punto, el de los investigadores de la NSA, de 1992.

Extractos (con algunos comentarios míos).

Interconnection networks are often modeled by graphs. The vertices of the graph correspond to processing elements. memory modules. or just switches. The edges correspond to communication lines. If communication is one-way. the graph is directed; otherwise. the graph is undirected. 

Vertex symmetric graphs are especially well suited as models for interconnection networks because these graphs have the property that the graph viewed from any vertex looks the same. Thus, in such networks the same routing algorithm may be used at each processor. Moreover, the symmetry of the graph minimizes congestion, as traffic is distributed uniformly over all vertices. (Note that a random graph would satisfy the second property but not the first.)

The Cayley Graph Model

We mentioned in the introduction that vertex symmetric graphs make “good” interconnection networks. Indeed, most of the computers in service today that are based upon large-scale parallel processing have interconnection networks that are vertex ,symmetric graphs.

For example, the Connection Machine has a network architecture that !can be modeled by the 12-dimensional binary hypercube. The 256 X 256 torus-connected 2- dimensional mesh is the architecture of the MPP at the NASA/Goddard Space Flight ‘Center. Finally, the butterfly network and the cube-connected cycle network are also ‘vertex symmetric graphs that are widely accepted as models for network architectures. Our basic working hypothesis is that network architectures should be vertex symmetric graphs. The central problem then is to find new symmetric graphs that provide superior performance as computer architectures.

Como es bien conocido Casi todos los (infinitos) Grafos Vértice Simétricos son Grafos de Cayley. Ojo, corrijo, esto no es bien conocido: es una conjetura (página 21): It is conjectured that almost all vertex-transitive graphs of order n are Cayley graphs. El artículo de Babai es de 1994 y desconozco el estatus de la conjetura. Los últimos datos empíricos parecen confirmarla: en un estudio exhaustivo, de 111360 grafos cúbicos vértice transitivos (todos los de orden 128o o inferiores) sólo 1434 no eran de Cayley.  En el caso general el tema sigue investigándose con intensidad.     

Nosotros hace poco investigamos sobre la posibilidad de extender las técnicas de la patente (que sirven sobre todo para los Dígrafos de Cayley bigenerados) a los Grafos de Vértice Transitivos. No recuerdo las conclusiones pero sí recuerdo que desde luego la traslación no es directa. Tengo que volver a releer la entrada.

Seguimos extractando del artículo principal del punto.

Thus, finite groups provide an infinite source of vertex symmetric graphs. In addition, graph theoretic properties are reflected in the algebraic structure of the group and vice versa. Over the past 100 years mathematicians have developed powerful tools with which to study the internal structure of finite groups. Consequently, this vast theory can be used to investigate graph theoretic properties of interconnection networks based upon Cayley graphs. . This important observation was made by Sheldon Akers and BalaKrishnan Krishnamurthy in [1]. Using this group theoretic approach, they found two new families ofvertex symmetric graphs that they called star graphs and pancake graphs [1]. They also showed that these new interconnection networks in many ways were superior to the ndimensional binary hypercube and the cube-connected cycle networks.

We end this section with a discussion of two design issues that suggest “good” interconnection networks should be large graphs ohmall degree and small diameter. The first design issue is to design a network with transmission delays as small as possible. Since the maximum number oflinks used to transmit any single message is the diameter of the graph, one would think one should make the diameter of the graph as small as possible.

A general rule of thumb for the total cost of a supercomputer is that two thirds of the total cost is due to the processor and memory modules and one third of the cost is the network itself. It is estimated that as much as one third of the network cost is related to the total number of wires; this cost includes the expense of driving messages at very high rates through the wires.

Lo que decíamos, el número de cables, que crece con el grado.

We now present some evidence that Cayley graphs of nonabelian groups and in particular, Cayley graphs Qf the nonabelian simple groups, may provide the best interconnection networks, at least in the sense of producing graphs of small degree and diameter.

Precisamente algunos de los pasos de la (segunda) solicitud de patente, contenidos en las reclamaciones que el examinador ha rechazado proporcionan métodos para identificar este tipo de Digrafos de Cayley, los no abeliano o no commutativos y simples, y para determinar si tienen recorridos hamiltonianos o no.

In the second section we present our research on the routing problem. Routing is the problem of communicating efficiently among the processors and memories. Usually a routing algorithm is network dependent, that is, given a network, one must find a routing algorithm for that specific network. We present in this paper a routing algorithm for any computer architecture satisfying certain properties. Moreover, we demonstrate that our algorithm is extremely efficient in many cases. In the third section we consider the problem of constructing Cayley graphs that meet specific design parameters. In particular, we present research done in support of an effort to study the influence of these parameters on network performance.

Routing is the problem of communicating efficiently among the processors and memories of an interconnection network. Graph theoretically this problem is equivalent to finding paths between pairs ofvertices. The task of finding paths from one vertex to another in a graph has been extensively studied and there exist many algorithms for this purpose. Dijkstra’s algorithm, for example, finds the shortest paths between any pair ofvertices. This algorithm can be used in any graph (directed or undirected). The problem with all of these algorithms is that they require an excessive amount of overhead. That is, too much of the computer’s resources must be allocated to routing. . The solution at the moment is to design routing algorithms for each specific network. These special purpose algorithms usually only apply to the interconnection network they were intended for. For example, the routing algorithm used in the Connection Machine depends totally on the geometry of the 12-dimensional binary n-cube and is completely different from the routing algorithm used in the MPP. The main purpose ofthis section is to present our own research on this problem. Our research can be regarded as a first attempt to find general purpose routing algorithms for interconnection networks. Specifically, we present a routing algorithm for any Cayley graph of a permutation group satisfying certain properties. Moreover, we will demonstrate that our algorithm in many cases is extremely efficient. In addition, we shall presentsome promising new interconnection topologies. All of the groups we study in this section will be permutation groups. In light of Cayley’s theorem we have lost no generality

Por lo  tanto cuando hablan de routing se refieren al problema del camino más corto entre dos nodos, y no al problema de recorridos hamiltonianos.

El artículo es interesante pues demuestran que el problema del camino más corto en este tipo de dígrafos es equivalente al problema de factorizar los elementos del grupo en secuencias de generadores.

Proposition 2.1. Factoring elements in G as “words” in the generators is equivalent to routing in the Cayley graph reG, A).

En el mismo año en el que estos dos investigadores publicaron su informe luego desclasificado se publicaba un survey con un contenido similar:

Título.  Symmetry in interconnection networks based on Cayley Graphs of permutations groups: a survey.

En este artículo analizan variadas topologías propuestas por otros investigadores como Grafos de Cayley con un énfasis puesto en algoritmo de enrutamiento por camino más corto en éstas topologías. Hacen un comentario muy relevante:

Remark 3.2. (página 375).

Notice that the notion of minimum distance between vertices in a graph is crucial to the definition of k-distance transitivity as well as to the problem of shortest path routing. If the underlying graph is a Cayley Graph, then the problem of finding the minimum distance between any arbitrary vertices say p and the designated vertex I (corresponding to the identity element) is equivalent to finding a minimal length generating sequence for the element p.  This latter problem when the generator set is not fixed is not only known to be NP-Hard, but PSpace-complete as well. However by fixing the set of generators in advance…Jerrum has derived polynomial time algorithms for minimal length generating sequence for elements of the symmetric group. This observation drives home the idea that practical interconnection networks can not be built out of arbitrary finite groups and arbitrary sets of generators.

Hemos reflexionado y escrito mucho sobre este tema en el pasado y éste comentario nos ha abierto los ojos. El artículo de Jerrum, que conocía pero no recuerdo si pude consultar, es The complexity of finding minimal-length generator sequence (1985).  No recuerdo si el tamaño del input que consideraba el autor era el grado de la permutación o el número de vértices.  Tema a revisar.

Terminamos éste punto recordando a otro autor que también ha trabajado en Institutos dedicados a temas de alta especulación filosófica, especializados sobre todo en las ideas abstractas más elevadas: instituciones de Defensa de EEUU (sí otra indignada ironía) y que desde hace unos años está publicando en forma de artículos informes no públicos que realizó mientras trabajaba en Los Alamos National Laboratory. Un primer ejemplo. Y un segundo ejemplo.

Es interesante pues este autor habla de algoritmos de comunicaciones globales en Grafos de Cayley pero sin mencionar los recorridos hamiltonianos. Obviamente el enrutamiento por recorridos hamiltonianos no es el único método posible para organizar las comunicaciones globales (que hay que realizar de todas maneras), sólo es el óptimo. Este autor presenta otros métodos (no obstante, me sigue sorprendiendo que no cite a los recorridos hamiltonianos).

Título. GLOBAL COMMUNICATION ALGORITHMS FOR CAYLEY GRAPHS.

Abstract.

We discuss several combinatorial problems that arise when one looks at computational algorithms for highly symmetric networks of processors. More specifically, we are interested in minimal times associated with four communication tasks (defined more precisely below):

universal broadcast, every processor has a vector that it wishes to broadcast to all the others;

universal accumulation, every processor wishes to receive the sum of all the vectors being sent to it by all the other processors;

universal exchange, every processor wishes to exchange a vector with each other processor;

and global summation, every processor wants the sum of the vectors in all the processors.

This paper is adapted from and corrects errors in an unpublished internal report from Los Alamos National Laboratory [10].

El artículo propio [10] es el siguiente: V. Faber, “Global communication algorithms for hypercubes and other Cayley coset graphs,” unpublished internal Los Alamos National Laboratory report, LA-UR 87-3136 (1987).

Aparentemente, desde más o menos 2008 estos temas se están desclasificando (tema a estudiar). Por otra parte no es casualidad que este tipo de agencias, cómo la NSA o las Agencias / Institutos de Defensa traten sobre estos temas y tengan investigadores propios dedicados a investigar sobre redes de interconexión. No es el amor a las elevadas ideas abstractas lo que les motiva. Entre otras cosas entiendo que normalmente encriptan todas sus comunicaciones; los métodos habituales de acceder a claves son de fuerza bruta que hacen un uso extensivo de la supercomputación; la velocidad de un supercomputador depende en gran parte de la red de interconexión (ahora no sólo la externa sino también la interna de  los propios chips); les interesa por lo tanto conocer en detalle el estado del arte al respecto. Ya se sabe que la IIGM la ganó un supercomputador…

Nota al margen.

Aprovechamos para recordar que es con ésta agencia, la NSA, con la que el recientemente fallecido y brillante matemático John F. Nash (Nobel, Abel y…Óscar) intercambió una serie de cartas, recientemente desclasificadas, en las que proponía un sistema criptográfico, basado en pares de permutaciones (no relacionado con nuestros resultados), que la NSA finalmente no adoptó por considerarlo débil.

Carta de John F. Nash al "Major" Grosjean

Carta de John Nash al Mayor Grosjean

Por el camino,  Nash hacía algunos visionarios comentarios sobre la teoría de la complejidad computacional y su relación con la criptografía (similares a los que hizo Godel en su famoso intercambio epistolar con Von Neumann).

Hicimos una entrada sobre éstas cartas y sirva ésta entrada, aunque sea a destiempo, como homenaje a Nash por su accidentada defunción (que casualmente fue el día siguiente al del (claramente injustificado) rechazo de mi (segunda) solicitud de patente).

Nash esquizofrenia

Pese a sus aparentes éxitos, Nash no tuvo una vida fácil pues padeció esquizofrenia. Sorprendentemente se curó. Él achacaba la curación a un cambio hormonal sobrevenido con la edad.

Fin de nota al margen.

3. Los hipercubos son Grafos de Cayley (ojo, no bigenerados en general).

El caso es que me he preguntado si los hipercubos y su generalización se podían expresar como digrafos / grafos de Cayley y aunque la respuesta me parecía evidente (sí) me ha costado encontrar algo al respecto.

Y lo he encontrado de un autor (no podía ser de otra manera) con el que ya nos hemos cruzado y cuyos resultados hemos utilizado ampliamente en la patente, John D. Dixon.

GROUPS WITH A CAYLEY GRAPH ISOMORPHIC TO A HYPERCUBE. 1997

JOHN D. DIXON

Abstract.

A process is described for enumerating the Cayley graphs isomorphic to a binary d-cube for small values of d. There are 4 Cayley graphs isomorphic to the 3-cube, 14 isomorphic to the 4-cube, 45 isomorphic to the 5-cube and 238 isomorphic to the 6-cube. A similar method may be used for any graph with a prime power number of vertices.

Proporciona generadores. ¡¡¡ Ese Dixon !!!

Apéndice. Otros campos de redes de interconexión en los que tienen las topologías / arquitecturas basadas en Grafos de Cayley son los de:

1. Data Centers.

Para ver el estado del arte en arquitecturas y topologías de DC ver éste libro: Fat tree, con conmutadores top of the rack y end of the row;

Pero, en base a consideraciones de coste y uso eficiente de los recursos también se están empezando a proponee topologías de DC basadas en grafos de Cayley. 2014.

Para más bibliografía ver aquí, 2015.

Una tesis reciente (2014). Comentan que tanto el Internet como los Data Centers empiezan a tener problemas de escalabilidad, con sus tecnologías actuales.

2. Redes P2P, con Tablas de Hash Distribuidas.

Extracto.

A distributed hash table (DHT) is a class of a decentralized distributed system that provides a lookup service similar to ahash table: (key, value) pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key. Responsibility for maintaining the mapping from keys to values is distributed among the nodes, in such a way that a change in the set of participants causes a minimal amount of disruption. This allows a DHT to scale to extremely large numbers of nodes and to handle continual node arrivals, departures, and failures.

DHTs form an infrastructure that can be used to build more complex services, such as anycast, cooperative Web cachingdistributed file systems, domain name services, instant messaging, multicast, and also peer-to-peer file sharing and content distribution systems.

Notable distributed networks that use DHTs include BitTorrent‘s distributed tracker, the Coral Content Distribution Network, the Kad network, the Storm botnet, the Tox instant messenger, Freenet and the YaCy search engine.

Eso es lo que afirman en un artículo de ¿ 2005 ?

Título. Cayley DHTs — A Group-Theoretic Framework for Analyzing DHTs Based on Cayley Graphs

Extractos. 

The unified analytical framework discussed in this paper – Cayley DHTs – allows us to compare DHT topologies on a more abstract level and characterizes common features of current DHT designs. In a nutshell, we show that most current static DHT topologies such as hypercubes, ring graphs, butterflies, cube-connected cycles, and d-dimensional tori fall into a generic group-theoretic model, Cayley graphs, and can be analyzed as one class. These Cayley graph based DHTs (hereafter Cayley DHTs), including both non-content degree DHTs and constant degree DHTs, intentionally or unintentionally take advantage of several important Cayley graph properties such as vertex/edge symmetry, decomposability, good connectivity and hamiltonicity to achieve DHT design goals such as scalability, communication load balancing, optimal fault tolerance, and routing efficiency. Several non-Cayley DHTs also utilize techniques in their dynamic DHT algorithms that try to imitate desirable Cayley graph properties, again showing the close relationship between Cayley graph properties and desirable DHT system features.

The most notable feature of Cayley graphs is their universality. Cayley graphs embody almost all symmetric interconnection networks, as every vertex transitive interconnection network can be represented as the quotient of two Cayley graphs[2]. They represent a class of high performance interconnection networks with small degree and diameter, good connectivity, and simple routing algorithms. 

Hamiltonicity is important for DHT design because it enables DHTs to embed a ring structure so as to implement ring based routing in dynamic DHT algorithms. Ring based routing, characterized by the particular organization of the DHT identifier space and ensuring the DHT fault tolerance in a dynamic P2P environment by means of maintaining successor/predecessor relationships between nodes, is used by almost all DHT proposals. Gummadi et al. [5] observes that the ring structure “allows the greatest flexibility and hence achieves the best resilience and proximity performance of DHTs”. Although in terms of our analytical framework, we do not fully agree with Gummadi et al. on the conclusion that ring graphs are the best static DHT topologies, we agree that an hamiltonian cycle should exist in static DHT topologies in order to ease the dynamic DHT algorithm design. 

5. Gummadi, K., Gummadi, R., Gribble, S., Ratnasamy, S., Shenker, S., Stoica, I.: The impact of dht routing geometry on resilience and proximity. In: ACM Annual Conference of the Special Interest Group on Data Communication, Karlsruhe, Germany (2003).

3. Wireless Sensor Networks.

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: