Nombrando Entidades

NombresDireccionesIdentificadoresEspacio de NombresResolucin de NombresMecanismo de CierreLigamientoMontaje

Nombrando Entidades

Nombres Definicin: Un nombre en un sistema distribuido es un conjunto de caracteres o bits que representan a una entidad. Las Entidades pueden ser operadas. Ejemplo:

NombreEntidadImpresoraInterfaz 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 Cdigo.

Nombrando Entidades

Direcciones Punto de Acceso: Consiste en una entidad especial, cuyo nombre se denomina Direccin, y siempre esta asociada a una entidad. Es decir, el punto de acceso representa la direccin del cual se puede acceder la entidad al cual esta asociado. Una entidad puede tener asociado varios puntos de acceso. Ejemplo:

NombreEntidadHost 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:HostHost255.255.255100.100.100Servidor Manejador de Peticiones FTPNombre Independiente de la Localidad

Nombrando Entidades

Identificadores Definicin: 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 ambigedades. Ejemplos: Numero de cedula de una entidad Persona, y el RIF de una entidad Empresa.

Nombrando Entidades

Espacio de Nombres Definicin: Los nombres en un sistema distribuido se organizan en lo que se llama un Espacio de Nombres. Se representa mediante un grafo dirigido que rene 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 Raz: Nodo con la propiedad de no tener antecesor alguno. Por simplicidad se debera tener un solo nodo raz.

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:N5N6N9N4N1N2N3N8N0binjavajavacjavaxconfighomeMaverickFile0Nodo Terminal

Nodo DirectorioN1: binN2: 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:N5N6N9N4N1N2N3N8N0binjavajavacjavaxconfighomeArchivo1N0:MaverickN3:Ruta RelativaRuta Absoluta

Nombrando Entidades

Espacio de Nombres Pueden haber 2 tipos de nombres en el grafo: Nombre Global Nombre Local Ejemplo:N5N6N7N9N1N2N3N8N0binjavajavacjavaxhomeAndrossArchivo1MaverickArchivo1N4Nombres LocalesNombre Global

Nombrando Entidades

Resolucin de Nombres Definicin: Dado una ruta, al proceso de obtener el contenido del nodo que dicha ruta apunta, se le denomina Resolucin de Nombres. Ejemplo: Dado la ruta N0:,N7N9N2N8N0homeAndrossArchivo1MaverickArchivo1N4N1: binN2: homeN1binN7: AndrossN8: MaverickN9: Archivo1

La ruta original queda resuelta a/home/Maverick/Archivo1

Nombrando Entidades

Mecanismo de Cierre Definicin: Mecanismo que indica donde se debe comenzar el proceso de resolucin 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.N7N9N2N8N0homeAndrossArchivo1Archivo1N4Maverick

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:Permitir que varias rutas resuelvan al mismo nodo.Ejemplo:N5N6N7N1N2N3binjavajavacjavaxhomeMaverickArchivo1N4N0Archivo1Ruta original:/home/Maverick/Archivo1

Ruta Aadida:/bin/java/Archivo1Hard Links

Nombrando Entidades

Ligamiento Hay 2 maneras de representar un alias en el grafo:2) Utilizacin de Symbolic LinkEjemplo:N5N7N1N2N3binjavaArchivo1homeMaverickArchivo1N4N0Se dice queN5 es un link simblico a N4/home/Maverick/Archivo1

Nombrando Entidades

Montaje El proceso de resolucin de nombres tambin 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 algn nodo en otro espacio de nombres.

Nombrando Entidades

Montaje Ejemplo:L7L2L0homeAndoraL4code.cppEspacio de Nombres Forneo EN2N7N9N2N8N0homeAndrossArchivo1N4Archivo1MaverickEspacio de Nombres EN1N9:Archivo1L4:code.cpp

Mount PointMounting Point

Nombrando Entidades

MontajeConsidere un par de espacios de nombres que se encuentran distribuidos en diferentes mquinas. Si se desea montar un mount point en EN1 que haga referencia a EN2, se necesita:El nombre de un protocolo de accesoEl nombre de la maquina que maneja EN2.El nombre del mounting point en el espacio de nombres forneo, EN2.

Nombrando Entidades

MontajeVentaja del uso del Montaje:N7N9N2N8N0homeAndrossArchivo1N4Archivo1MaverickN9:Archivo1L4:code.cpp

>>cd /home/Maverick >>ls l >>Archivo1 code.cppL7L2L0homeAndoraL4code.cpp

Implementacin de un Espacio de Nombres (Name Space)

Distribucin de un Espacio de NombresCheriton y Mann (1989)Capa global: Est formada por el nodo raz 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 organizacin. ellos se caracterizan porque ellos representan grupos de entidades que pertenecen a la misma organizacin o unidad de administracin.

Capa Directiva: Est formada por nodos que cambian con regularidad. Su principal caracterstica es que dichos nodos no son mantenidos solo por administradores del sistema, sino tambin por usuarios finales; Ya que esta capa contiene los directorios y archivos de dichos usuarios.

Distribucin de un Espacio de Nombres Ejemplo:

Distribucin de un Espacio de Nombres

Implementacin de Resolucin de NombresLa distribucin del Espacio de nombres a travs de muchos servidores de nombres afecta la implementacin de Resolucin de Nombre. Dos mtodos:

Resolucin de nombres iterativaResolucin de nombres recursiva

Resolucin de nombres iterativa

Resolucin de nombres recursiva

Resolucin 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 DNSEsta organizado jerrquicamente como un rbol con raz. Una etiqueta es un String (case-insensitive) de caracteres alfanumricos. Con un largo mximo de 63 caracteres.El largo mximo de un nombre de camino completo no puede exceder los 255 caracteres.La representacin 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 raz que no tiene ninguno) la etiqueta del arco que llega al nodo se usa como nombre del nodo.Un subrbol se denomina Dominio El camino al nodo raz es denominado Nombre del Dominio.El contenido de un nodo esta formado por una coleccin de "registros de recursos"baraka.ldc.usb.ve.

Registros de recursos

Implementacin de DNSLa implementacin de DNS es muy similar a lo descrito anteriormente. En esencia este servicio puede ser dividido en una capa global y una capa de administracin. 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 pequea coleccin 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 travs de su nombre de dominio.

Base de Datos de DNS

Entidades MvilesLos mecanismos de resolucin de nombres vistos hasta ahora se utilizan para entidades fijas, y no soportan asociaciones de nombre-direccin que cambian peridicamente

Naming vs. Locating EntitiesTipos de nombresNombre amistoso humanoIdentificadoresDireccionesDNSNombre amistoso humano Direccin

Naming vs. Locating Entitiescs.vu.nlftp

Naming vs. Locating Entitiescs.unisa.edu.auftpcs.vu.nlftp

Naming vs. Locating EntitiesSolucionesGuardar la direccin de la nueva maquinaDNS cs.vu.nlftp.cs.unisa.edu.auftp.cs.berkely.edu

Naming vs. Locating EntitiesSoluciones (continuacin)Guardar el nombre de la nueva maquinaDNS cs.vu.nlftp.cs.unisa.edu.auftp.cs.berkely.educs.unisa.edu.auftpftp

Naming vs. Locating Entitiesnombrenombrenombrenombredireccindireccindireccindireccin

Naming vs. Locating EntitiesnombrenombrenombrenombredireccindireccindireccindireccinidentificadorServicio de nombresServicio de localizacin

Soluciones SimplesBroadcasting y MulticastingApuntadores: cadena de pares stub - scion

Broadcasting y MulticastingQuien es X?ABXPrincipio usado enAddress Resolution Protocol (ARP)

Apuntadores: pares (stub, scion)Usado en SSPC (Stub Scion Pairs Chains)

Apuntadores: pares (stub, scion)Provee un mecanismo para cortar la cadena

Home-Based ApproachesBroadcasting y Multicasting dficiles de implementar eficientemente en grandes escalas de redes donde largas cadenas de apuntadores introducen problemas de desempeo y son suceptibles a enlaces rotosSolucin home location

EjemploManda paquete a la ubicacin home del host2. Retorna direccin de ubicacin actual3. Desvo del paquete a la ubicacin actual 4. Manda prximos paquetes a la ubicacin actualUbicacin actual del hostUbicacin home del hostUbicacin del cliente

Aproximaciones de jerarquaMecanismo generalLa red est dividida en un conjunto de dominios similar a la organizacin del DNS

Hoja del dominio, contenida en SRaz de T Nivel tope del dominio TNodo del dominioSubdominio Sde T

Aproximaciones de jerarquaMecanismo general (Continuacin)Cada entidad es representada por un record de ubicacin en el nodoEn una hoja se almacena la direccin actual de la entidadEn los niveles externos se guarda un apuntador al nodo del nivel inferior que contiene la entidad

Ejemplo: Bsqueda de ubicacin Pedido de bsquedaDominio DEl nodo no tiene record de E, la peticin es mandada al padreMEl nodo conoce a E, la peticin es mandada al hijo

Ejemplo: Actualizacin Pedido de insercinDominio DEl nodo no tiene record de E, la peticin es mandada al padreMEl nodo conoce a E, la peticin no se vuelve a enviar

Ejemplo: Actualizacin (cont.)El nodo crea el recordy guarda la direccinMEl nodo crea el recordy guarda el apuntador

Pointer CachesEn servicios de nombramiento tradicionales, el mapping entre el nombre y la direccin se asume que es estableCaching solamente es efectivo si la data guardada raramente cambia

Ejemplo: Caching a referenceCached pointersDominio DE se mueve regularmenteentre dos subdominios

Scalability IssuesProblema sin ninguna medida especial, la raz puede ser requerida para manejar muchas bsquedas y actualizaciones, lo cual producir enbotellamientoSolucin particionar la raz y otros nodos de alto nivel en subnodos distribuir los nodos uniformemente a lo largo de la red

Ejemplo: Usuario mvilSubnodo de la raz, responsable de atender requerimientos de EAlternativo, y mejor opcin para atender requerimientos de EEl cliente pide la direccin actual de E Ruta alterna parala bsqueda delrequerimientoDominio donde reside E actualmenteRuta actual de la bsqueda delrequerimiento

Entidades No ReferenciadasEl problema de las entidades no referenciadasBroken links en InternetReferencias CclicasReferencias InalcanzablesRef. Alcanzables

Ref. CclicasRef. Inalcanzables

Entidades No ReferenciadasProblemas a ResolverLocalizacin de entidades no referenciadasEliminacin de entidadesFallas en las conexiones y redesSolucinRecolector de Basura (Garbage Collector)

Entidades No ReferenciadasConteo de ReferenciasProceso PEsqueletoObjeto O

Entidades No ReferenciadasProblemasPrdida/Duplicacin de MensajesProceso PEsqueletoObjeto OEl proxy p fue contado dos vecesSe pierde el ACK

Entidades No ReferenciadasProblemas (continuacin)Condicin de CarreraP1 enva una referencia a P2P1 elimina la referencia a OP2 informa a O que tiene una referenciaP1 avisa a O que va a enviar una referenciaP1 elimina la referencia a OP1 enva una referencia a P2O confirma la referencia a P2O ya fue eliminadoTiempoTiempo

Entidades No ReferenciadasConteo de Referencias con pesoPeso TotalPeso ParcialEsqueletoObjeto OPeso Parcial del proxyProceso PPeso parcial del objeto divido a la mitad

Entidades No ReferenciadasConteo de Referencias con pesoProceso P2P2 obtiene la mitad del peso del proxy de P1P1 pasa la referencia a P2El peso parcial del esqueleto no se modificaProceso P1

Entidades No ReferenciadasConteo de Referencias con pesoProceso P2Proceso P1P1 no tiene peso y crea un esqueleto adicionalPeso TotalPeso ParcialEl objeto no tiene peso parcialP2 referencia al objeto o travs de P1

Entidades No ReferenciadasConteo de Referencias con generacionesProceso P1Proceso P2P1 pasa la referencia a P2Contador de copiasGeneracinEl objeto posee una tabla con cantidad de copias por generacin

Entidades No ReferenciadasConteo de Referencias con generacionesAl eliminar una referencia, el esqueleto recibe el nmero de copias numCopia y de generacin genG[gen] -1G[gen+1] + numCopia

Lista de Referencias Definicin Operaciones Idempotentes Ventajas

Lista de ReferenciasDefinicin 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 ReferenciasOperaciones IdempotentesAgregar 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 ReferenciasOperaciones IdempotentesEl agregar por primera vez debe ser cuidadosa.Ejemplo.

Lista de ReferenciasVentajasFacil de mantener la lista en caso de fallas, el esqueleto chequea de vez en cuando que las referencias estn vivas.Puede escalar mas fcilmente

Lista de ReferenciasDesventajasSi la lista es muy grande, puede que no escale muy bien. Una solucin 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 InalcanzablesMarcado Ingenuo.Recordando mark-and-sweep.Stop the world.Mark-and-sweep modificado. (algoritmo de los tres colores).Emerald.

Entidades InalcanzablesMarcado IngenuoVentaja: Se logran eliminar las entidades que no son alcanzables desde el conjunto razDesventajas: durante el proceso de marcado y borrado el grafo no puede cambiar.

Entidades InalcanzablesMarcado en gruposConsiste en dividir y conquistarCuando los sub-problemas son combinados.Ventaja: Reduce el overheadDesventaja: Cuando se combinan los sub-problemas.

Preguntas