Nombrando Entidades
Nombres
Direcciones
Identificadores
Espacio de Nombres
Resolución de Nombres
Mecanismo de Cierre
Ligamiento
Montaje
Nombrando Entidades
Nombres
• Definición: Un nombre en un sistema distribuido es un conjunto de caracteres o bits que representan a una entidad.
• Las Entidades pueden ser operadas.
• Ejemplo:
Nombre
Entidad
“Impresora”
Interfaz Donde se puede Operar
Nombrando Entidades
Nombres
• Existe un tipo importante de nombres, denominados Nombres
Humanos. Consisten en nombres destinados a ser utilizados por los
seres humanos.
•Ejemplos:
• Nombres de archivo
• Nombres de las Variables en un Código.
Nombrando Entidades
Direcciones
• Punto de Acceso:
Consiste en una entidad especial, cuyo nombre se denomina Dirección, y siempre esta asociada a una entidad. Es decir, el punto de acceso representa la dirección del cual se puede acceder la entidad al cual esta asociado.
• Una entidad puede tener asociado varios puntos de acceso.
• Ejemplo:
Nombre
Entidad
“Host” 255.255.255
Punto de Acceso
Nombrando Entidades
Direcciones
• Una entidad puede cambiar su punto de acceso; es decir, es asociada a un punto de acceso diferente.
• Ejemplo:
“Host” “Host”
255.255.255 100.100.100
“Servidor Manejador de Peticiones FTP”
Nombre Independiente de la Localidad
Nombrando Entidades
Identificadores
• Definición: Un identificador es un nombre que cumple con las siguiente propiedades:
• Representa a lo sumo una entidad.
• Cada entidad es representada por a lo sumo un identificador.
• Siempre se refiere a la misma entidad.
• Con el uso de Identificadores se puede representar a entidades sin ambigüedades.
• Ejemplos: Numero de cedula de una entidad “Persona”, y el RIF de una entidad “Empresa”.
Nombrando Entidades
Espacio de Nombres
• Definición: Los nombres en un sistema distribuido se organizan en lo que se llama un Espacio de Nombres.
• Se representa mediante un grafo dirigido que reúne el conjunto de las entidades de un sistema distribuido. Por lo tanto cada nodo tiene asociado un identificador.
• En dicho grafo pueden haber 3 tipos de nodos:
• Nodo Terminal: Representa una entidad nombrada y tiene la propiedad de no tener sucesor alguno.
• Nodo Directorio: Representa una entidad nombrada y tiene la propiedad de tener uno o mas sucesores.
• Nodo Raíz: Nodo con la propiedad de no tener antecesor alguno. Por simplicidad se debería tener un solo nodo raíz.
Nombrando Entidades
Espacio de Nombres
• Cada nodo tiene asociado una etiqueta y un identificador asociado a la entidad que representa.
• Cada nodo directorio tiene asociado una tabla que contiene los pares (etiqueta,identificador) de cada uno de sus sucesores.
• Ejemplo:
N5 N6N9
N4
N1 N2
N3 N8
N0bin
java
javac javax
config
home
Maverick
File0
Nodo Terminal
Nodo Directorio
N1: “bin”
N2: “home”
Nombrando Entidades
Espacio de Nombres
• Cada ruta en el grafo puede ser representada por una secuencia de etiquetas que corresponden a los nodos por los cuales ella atraviesa.
• Cada ruta puede ser relativa o absoluta.
• Ejemplo:
N5 N6N9
N4
N1 N2
N3 N8
N0bin
java
javac javax
config
home
Archivo1
N0:<N2,N8,N9>
Maverick
N3:<N6> Ruta Relativa
Ruta Absoluta
Nombrando Entidades
Espacio de Nombres
• Pueden haber 2 tipos de nombres en el grafo:
• Nombre Global
• Nombre Local
• Ejemplo:
N5 N6
N7
N9
N1 N2
N3 N8
N0bin
java
javac javax
home
Andross
Archivo1
Maverick
Archivo1
N4
Nombres Locales
Nombre Global
Nombrando Entidades
Resolución de Nombres
• Definición: Dado una ruta, al proceso de obtener el contenido del nodo que dicha ruta apunta, se le denomina Resolución de Nombres.
• Ejemplo: Dado la ruta N0:<N2,N8,N9>,
N7
N9
N2
N8
N0home
Andross
Archivo1
Maverick
Archivo1
N4
N1: “bin”
N2: “home”
N1
bin
N7: “Andross”
N8: “Maverick”
N9: “Archivo1”
La ruta original queda resuelta a
“/home/Maverick/Archivo1”
Nombrando Entidades
Mecanismo de Cierre
• Definición: Mecanismo que indica donde se debe comenzar el proceso de resolución de nombres y como se debe hacer.
• Ejemplo:
El mecanismo de cierre asegura que los nombres locales siempre se resuelven en el nodo directorio asociado a ella.
N7
N9
N2
N8
N0home
Andross
Archivo1Archivo1
N4
Maverick
Nombrando Entidades
Ligamiento
• Un Alias consiste en el uso de otro nombre para una entidad.
• Ejemplos:
Las variables de entorno que se usan en Windows tal como:
Classpath = C:\Archivos de programa\Java\clases
Nombrando Entidades
Ligamiento
• Hay 2 maneras de representar un alias en el grafo:
1) Permitir que varias rutas resuelvan al mismo nodo.
Ejemplo:
N5 N6
N7
N1N2
N3
bin
java
javac javax
home
Maverick
Archivo1
N4
N0
Archivo1
Ruta original:
“/home/Maverick/Archivo1”
Ruta Añadida:
“/bin/java/Archivo1”
“Hard Links”
Nombrando Entidades
Ligamiento
• Hay 2 maneras de representar un alias en el grafo:
2) Utilización de “Symbolic Link”
Ejemplo:
N5
N7
N1N2
N3
bin
java
Archivo1
home
Maverick
Archivo1
N4
N0 Se dice que
“N5 es un link simbólico a N4”
“/home/Maverick/Archivo1”
Nombrando Entidades
Montaje
• El proceso de resolución de nombres también puede ser utilizado
para unir diferentes espacios de nombres.
• Un “Mount Point” es un nodo directorio que en su tabla contiene
una entrada que hace referencia a un nodo en otro espacio de
nombres.
• Un “Mounting Point” consiste en el nodo que esta siendo
referenciado por algún nodo en otro espacio de nombres.
Nombrando Entidades
Montaje
• Ejemplo:
L7
L2
L0home
Andora
L4
code.cpp
Espacio de Nombres Foráneo EN2
N7
N9
N2
N8
N0home
Andross
Archivo1
N4
Archivo1
Maverick
Espacio de Nombres EN1
N9:”Archivo1”
L4:”code.cpp”
“Mount Point”“Mounting Point”
Nombrando Entidades
Montaje
• Considere un par de espacios de nombres que se encuentran
distribuidos en diferentes máquinas. Si se desea montar un “mount
point” en EN1 que haga referencia a EN2, se necesita:
• El nombre de un protocolo de acceso
• El nombre de la maquina que maneja EN2.
• El nombre del mounting point en el espacio de nombres
foráneo, EN2.
Nombrando Entidades
Montaje
• Ventaja del uso del Montaje:
N7
N9
N2
N8
N0home
Andross
Archivo1
N4
Archivo1
Maverick
N9:”Archivo1”
L4:”code.cpp”
>>cd /home/Maverick
>>ls –l
>>Archivo1 code.cpp
L7
L2
L0home
Andora
L4
code.cpp
Implementación de un Espacio de Nombres
(Name Space)
Distribución de un Espacio de Nombres
Cheriton y Mann (1989) Capa global: Está formada por el nodo raíz y sus nodos hijos.
Los nodos pertenecientes a esta capa se caracterizan por su estabilidad, dado que sus tablas de directorio cambian poco. estos nodos pueden representar organizaciones o grupo de organizaciones.
Capa Administrativa: Está formada por nodos directorio que juntos son manejados dentro de una organización. ellos se caracterizan porque ellos representan grupos de entidades que pertenecen a la misma organización o unidad de administración.
Capa Directiva: Está formada por nodos que cambian con regularidad. Su principal característica es que dichos nodos no son mantenidos solo por administradores del sistema, sino también por usuarios finales; Ya que esta capa contiene los directorios y archivos de dichos usuarios.
Distribución de un Espacio de Nombres – Ejemplo:
Distribución de un Espacio de Nombres
ITEM GLOBAL ADMINISTRATIVA
DIRECTIVA
Escala geográfica de la red
Mundial Organización Departamento
Numero total de nodos Pocos Muchos Números vastos
Tiempo de respuesta Segundos Milisegundos Inmediato
Propagación de actualizaciones
Floja Inmediata Inmediata
Numero de replicas Muchas Ninguna o pocas Ninguna
Caching del lado del cliente
Si Si A veces
Implementación de Resolución de Nombres
La distribución del Espacio de nombres a través de muchos servidores de nombres afecta la implementación de Resolución de Nombre. Dos métodos:
Resolución de nombres iterativa Resolución de nombres recursiva
Resolución de nombres iterativa
Resolución de nombres recursiva
Resolución de nombres recursiva
Iterativo Vs. Recursivo
El Domain Name System (DNS)
DNS es uno de los mas grandes servicios de naming distribuidos usados en la actualidad.
Es utilizado principalmente para conocer direcciones de hosts y de servidores de correos.
El Espacio de Nombres de DNS
Esta organizado jerárquicamente como un árbol con raíz. Una etiqueta es un String (case-insensitive) de caracteres alfanuméricos. Con un largo máximo de 63 caracteres.
El largo máximo de un nombre de camino completo no puede exceder los 255 caracteres.
La representación de un nombre de camino consiste de una lista de etiquetas separadas por puntos, comenzando con la que se encuentra mas a la derecha.
Como cada nodo en el espacio de nombres de DNS tiene exactamente un solo arco entrante (excepto la raíz que no tiene ninguno) la etiqueta del arco que llega al nodo se usa como nombre del nodo.
Un subárbol se denomina Dominio El camino al nodo raíz es denominado Nombre del
Dominio. El contenido de un nodo esta formado por una colección
de "registros de recursos"
baraka.ldc.usb.ve.
Registros de recursos
Implementación de DNS La implementación de DNS es muy similar a lo descrito
anteriormente. En esencia este servicio puede ser dividido en una capa global y una capa de administración. la capa de manejo esta formada por sistemas de archivos locales, esta no es formalmente parte de DNS y por lo tanto no es manejada por dicho servicio.
Cada zona es implementada por un servidor de nombres, el cual es siempre replicado para mayor disponibilidad. Los cambios en una zona especifica son manejados por el servidor de nombres primario. Los cambios se realizan modificando la base de datos local de DNS del servidor primario. Los servidores de nombre secundarios no acceden a la base de datos directamente, sino que solicitan al servidor primario que transfiera su contenido.
Una base de datos de DNS es implementada como una pequeña colección de archivos , de los cuales el mas importante contiene todos los registros de recursos de todos los nodos de una zona particular.
Esto permite que los nodos sean identificados simplemente a través de su nombre de dominio.
Base de Datos de DNS
Entidades Móviles
Los mecanismos de resolución de nombres vistos hasta ahora se utilizan para entidades “fijas”, y no soportan
asociaciones de nombre-dirección que cambian periódicamente
Naming vs. Locating Entities
Tipos de nombres Nombre “amistoso” humano Identificadores Direcciones
DNS Nombre “amistoso” humano Dirección
Naming vs. Locating Entities
cs.vu.nl
ftp
cs.unisa.edu.au
ftp
Naming vs. Locating Entities
cs.vu.nl
ftp
Naming vs. Locating Entities Soluciones
Guardar la dirección de la nueva maquina
DNS cs.vu.nl
ftp.cs.unisa.edu.au ftp.cs.berkely.edu …
Naming vs. Locating Entities Soluciones (continuación)
Guardar el nombre de la nueva maquina
DNS cs.vu.nl ftp.cs.unisa.edu.au
ftp.cs.berkely.educs.unisa.edu.au
ftp
ftp
Naming vs. Locating Entities
nombre nombre nombrenombre
dirección dirección direccióndirección
Naming vs. Locating Entities
nombre nombre nombrenombre
dirección dirección direccióndirección
identificador
Servicio de nombres
Servicio de localización
Soluciones Simples
Broadcasting y Multicasting Apuntadores: cadena de pares
stub - scion
Broadcasting y Multicasting
Quien es “X”?
A
B
X
Principio usado enAddress Resolution Protocol (ARP)
Apuntadores: pares (stub, scion)
Proceso P2
Proceso P1
Proceso P3
Proceso P4
Usado en SSPC (Stub Scion Pairs Chains)
Apuntadores: pares (stub, scion)
Proceso P1
Proceso P2
Proceso P3
Provee un mecanismo para cortar la cadena
Home-Based Approaches
Broadcasting y Multicasting díficiles de implementar eficientemente en grandes escalas de redes donde largas cadenas de apuntadores introducen problemas de desempeño y son suceptibles a enlaces rotos
Solución home location
Ejemplo
1. Manda paquete a la ubicación “home” del host
2. Retorna dirección de ubicación actual
3. Desvío del paquete
a la ubicación actual 4. Manda próximos paquetes a la ubicación actual
Ubicación actual del host
Ubicación “home” del host
Ubicación del cliente
Aproximaciones de jerarquía Mecanismo general
La red está dividida en un conjunto de dominios similar a la organización del DNS
Hoja del dominio, contenida en S
Raíz de T Nivel tope del dominio T
Nodo del dominio
Subdominio Sde T
Aproximaciones de jerarquía
Mecanismo general (Continuación…) Cada entidad es representada por un
“record de ubicación” en el nodo En una hoja se almacena la
dirección actual de la entidad En los niveles externos se guarda un
apuntador al nodo del nivel inferior que contiene la entidad
Ejemplo: Búsqueda de ubicación
Pedido de búsqueda
Dominio D
El nodo no tiene record de E, la petición es mandada al padre
M
El nodo conoce a E, la petición es mandada al hijo
Ejemplo: Actualización
Pedido de inserción
Dominio D
El nodo no tiene record de E, la petición es mandada al padre
M
El nodo conoce a E, la petición no se vuelve a enviar
Ejemplo: Actualización (cont.)
El nodo crea el recordy guarda la dirección
M
El nodo crea el recordy guarda el apuntador
Pointer Caches
En servicios de nombramiento tradicionales, el mapping entre el nombre y la dirección se asume que es estable
Caching solamente es efectivo si la data guardada raramente cambia
Ejemplo: Caching a reference
Cached pointers
Dominio D
E se mueve regularmenteentre dos subdominios
Scalability Issues
Problema sin ninguna medida especial, la raíz puede ser requerida para manejar muchas búsquedas y actualizaciones, lo cual producirá enbotellamiento
Solución particionar la raíz y otros nodos de alto nivel en subnodos distribuir los nodos uniformemente a lo largo de la red
Ejemplo: Usuario móvil
Subnodo de la raíz, responsable de atender requerimientos de E
Alternativo, y mejor opción para atender requerimientos de E
El cliente pide la
dirección actual de E
Ruta alterna parala búsqueda delrequerimiento
Dominio donde reside E actualmente
Ruta actual de la búsqueda delrequerimiento
Entidades No Referenciadas El problema de las entidades no
referenciadas “Broken links” en Internet Referencias Cíclicas Referencias Inalcanzables
Ref. Alcanzables
Ref. Cíclicas
Ref. Inalcanzables
Entidades No Referenciadas
Problemas a Resolver Localización de entidades no referenciadas Eliminación de entidades Fallas en las conexiones y redes
Solución Recolector de Basura (Garbage Collector)
Entidades No Referenciadas
Conteo de Referencias
Proceso PEsqueleto
Objeto O
Entidades No Referenciadas
Problemas Pérdida/Duplicación de Mensajes
Proceso PEsqueleto
Objeto O
El proxy p fue contado dos veces
Se pierde el ACK
Entidades No Referenciadas
Problemas (continuación) Condición de Carrera
P1 envía una referencia a P2
P1 elimina la referencia a O
P2 informa a O que tiene una referencia
P1 “avisa” a O que va a enviar una referencia
P1 elimina la referencia a O
P1 envía una referencia a P2
O confirma la referencia a P2
O ya fue eliminado
Tiempo Tiempo
Entidades No Referenciadas
Conteo de Referencias con peso
Peso TotalPeso
Parcial
Esqueleto Objeto O Peso
Parcial del proxy
Proceso P
Peso parcial del objeto divido a la mitad
Entidades No Referenciadas
Conteo de Referencias con peso
Proceso P2P2 obtiene la mitad del peso del proxy de P1P1 pasa la
referencia a P2
El peso parcial del esqueleto no se modifica
Proceso P1
Entidades No Referenciadas
Conteo de Referencias con peso
Proceso P2Proceso P1
P1 no tiene peso y crea un esqueleto adicional
Peso Total
Peso Parcial
El objeto no tiene peso parcial
P2 referencia al objeto o través de P1
Entidades No Referenciadas
Conteo de Referencias con generaciones
Proceso P1
Proceso P2
P1 pasa la referencia a P2
Contador de copias
Generación
El objeto posee una tabla con cantidad de copias por generación
Entidades No Referenciadas
Conteo de Referencias con generaciones Al eliminar una referencia, el esqueleto recibe el número de copias numCopia y de generación gen G[gen] -1 G[gen+1] + numCopia
Lista de Referencias
Definición Operaciones Idempotentes Ventajas
Lista de Referencias
Definición Es una estructura que tiene cada
proxy que mantiene los proxies que apuntan hacia éste.
En vez de contar las referencias se mantiene una lista explicita de los proxies incidentes.
Lista de Referencias
Operaciones Idempotentes Agregar Agregar un proxie ya listado a la
lista de referencia no tiene efecto. Eliminar Eliminar un proxie ya borrado de la
lista no tiene efecto.
Lista de Referencias
Operaciones Idempotentes El agregar por primera vez debe
ser cuidadosa. Ejemplo.
Lista de Referencias
Ventajas Facil de mantener la lista en caso
de fallas, el esqueleto chequea de vez en cuando que las referencias estén vivas.
Puede escalar mas fácilmente
Lista de Referencias
Desventajas Si la lista es muy grande, puede
que no escale muy bien. Una solución es que se limite la
cantidad de tiempo que estará una referencia en la lista.
Identificando Entidades Inalcanzables
Marcado Ingenuo (Naive Tracing) Marcado en Grupos
Entidades Inalcanzables
Marcado Ingenuo. Recordando mark-and-sweep. “Stop the world”. Mark-and-sweep modificado.
(algoritmo de los tres colores). Emerald.
Entidades Inalcanzables
Marcado Ingenuo Ventaja: Se logran eliminar las
entidades que no son alcanzables desde el conjunto raíz
Desventajas: durante el proceso de marcado y borrado el grafo no puede cambiar.
Entidades Inalcanzables
Marcado en grupos Consiste en dividir y conquistar Cuando los sub-problemas son
combinados. Ventaja: Reduce el overhead Desventaja: Cuando se combinan
los sub-problemas.
Preguntas
Top Related