Chord

Chord

Chord es un protocolo sencillo y escalable de búsqueda distribuida en redes P2P que relaciona claves (keys) con nodos. Está diseñado para funcionar en redes descentralizadas (es decir, sin nodos privilegiados), y su funcionamiento permite concluir con un resultado exhaustivo de la búsqueda.

Funcionamiento general

Se considera una red formada por 2m nodos, que pueden estar activos o ausentes de la red. Dado un conjunto de claves en esa red, el protocolo Chord se encarga de asignar las claves existentes a los nodos activos y mantener esas asignaciones dinámicamente, es decir, a medida que los nodos van entrando y saliendo de la red. El resto de tareas vinculadas a la red -autenticación, almacenamiento de datos, interficie, etc.- son responsabilidad de los niveles superiores de la arquitectura.

La asignación de identificadores a nodos y claves se realiza mediante una función de hash consistente. En efecto, cuando un nodo o una clave entran en la red, reciben una identificación (id) que se obtiene calculando el hash (SHA-1) de la IP del nodo o del valor de la clave. Con este hashing se aleatorizan los accesos al sistema, de forma que para un atacante resulte difícil nodos o claves consecutivas o de posición estratégica en la red.

Una clave de id k se asigna al nodo de id k si éste está activo en la red. Si k no está, se busca el primer nodo posterior a k que esté activo y se le asigna a la clave: este nodo sustituivo se denomina sucesor de k (successor(k)).

Cuando k se conecte a la red, su nodo sucesor le transferirá las claves que estuvieran destinadas a él. Cuando un nodo abandona la red, transfiere las claves de las que se hacía cargo a su sucesor, es decir, al nodo con id siguiente a la suya. Con estos mecanismos, se garantiza la autorregulación de la red y el mantenimiento de las claves aun en un contexto de movilidad de los nodos participantes.

Procedimiento de búsqueda

El correcto mantenimiento de los nodos sucesores ya garantiza que las búsquedas se procesan de forma exhaustiva. Sin embargo, cada nodo almacena una cierta información adicional sobre la red que permite acelerar las búsquedas.

Esta información adicional se reduce a unos pocos nodos activos de la red, y se refleja en una tabla de rutas (finger table) interna. En la i-ésima fila de esta tabla consta el sucesor del nodo situado a distancia 2(i − 1) del nodo correspondiente (en dirección negativa en el círculo). De esta forma, cada nodo tiene un conocimiento más exhaustivo de sus homólogos más cercanos (aproximadamente, si N es el número de nodos totales, almacena información sobre O(log(N))).

Cuando un nodo solicita una clave j, examina su propia tabla de rutas; si encuentra el nodo responsable de j, envía la petición directamente al nodo afectado. En caso contrario, pregunta al nodo cuya id sea más cercana (menor) a j, que devolverá la id del nodo más cercano a j (menor) que encuentre en su tabla de rutas. De esta manera, el nodo remitente obtiene en cada nueva iteración un nodo más cercano a k, hasta llegar a k o a su sucesor. Todo este mantenimiento requiere el desarrollo de una señalización (mensajes entre nodos para mantener actualizadas las tablas de rutas) del orden de (log(N))2.

Escalabilidad

Chord está diseñado para ser altamente escalable, es decir, para que los cambios en las dimensiones de la red no afecten significativamente a su rendimiento. En particular, si N es el número de nodos de la red, su coste es proporcional a log(N).


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • chord — chord·ed; chord; clav·i·chord; clav·i·chord·ist; har·mon·i·chord; harp·si·chord; harp·si·chord·ist; hep·ta·chord; hex·a·chord; lyri·chord; mono·chord; neu·ro·chord; no·to·chord; no·va·chord; oc·ta·chord; pen·ta·chord; peri·chord; poly·chord;… …   English syllables

  • Chord — may refer to: Chord (music), an aggregate of musical pitches sounded simultaneously. Chord (guitar) an aggregate of musical pitches played simultaneously on a guitar Chord (geometry), a line segment joining two points on a curve Chord (astronomy) …   Wikipedia

  • Chord — ist ein strukturiertes Peer to Peer System, welches im Gegensatz zu den meisten unstrukturierten Systemen eine effiziente Suche nach Inhalten ermöglicht. Wie auch Gnutella ist Chord keine konkrete Implementierung, sondern ein Protokollsystem. Es… …   Deutsch Wikipedia

  • Chord — (k[^o]rd), n. [L chorda a gut, a string made of a gut, Gr. chordh . In the sense of a string or small rope, in general, it is written cord. See {Cord}.] 1. The string of a musical instrument. Milton. [1913 Webster] 2. (Mus.) A combination of… …   The Collaborative International Dictionary of English

  • chord — [ko:d US ko:rd] n [Sense: 1; Date: 1400 1500; Origin: accord] [Sense: 2 3; Date: 1500 1600; Origin: cord; influenced by Latin chorda ( CORD) (] [Sense: 2; Date: (17 19 centuries); Origin: chord string of a musical instrument )] …   Dictionary of contemporary English

  • chord — Ⅰ. chord [1] ► NOUN ▪ a group of three or more notes sounded together in harmony. DERIVATIVES chordal adjective. ORIGIN from ACCORD(Cf. ↑accord); the spelling was influenced by CHORD(Cf. ↑chord …   English terms dictionary

  • chord — chord, cord 1. Although we are dealing here with three English words, their histories are very much intertwined, and their ultimate origin is in the Latin word chorda which has several meanings. To begin with, there are two distinct words spelt… …   Modern English usage

  • chord — [ kɔrd ] noun count * 1. ) two or more musical notes played together a ) a particular position of the fingers on the guitar, producing a particular sound 2. ) TECHNICAL a straight line that connects two points in a circle or curved line… …   Usage of the words and phrases in modern English

  • Chord — Chord, v. i. (Mus.) To accord; to harmonize together; as, this note chords with that. [1913 Webster] || …   The Collaborative International Dictionary of English

  • Chord — Chord, v. t. [imp. & p. p. {Chorded}; p. pr. & vb. n. {Chording}.] To provide with musical chords or strings; to string; to tune. [1913 Webster] When Jubal struck the chorded shell. Dryden. [1913 Webster] Even the solitary old pine tree chords… …   The Collaborative International Dictionary of English

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”