especificación y verificación de routers software (12 créditos) j. guadalupe ramos díaz tutor:...
Post on 28-Jan-2016
218 Views
Preview:
TRANSCRIPT
Especificación y verificación de routers software
(12 Créditos)
J. Guadalupe Ramos Díaz
Tutor: Dr. Germán Vidal
DOCTORADO EN PROGRAMACIÓN DECLARATIVA E INGENIERÍA DE LA PROGRAMACIÓN
DSIC-PLIS-ELP-MIST
22
1. Currículum1.1 Formación1.2 Materias impartidas en México1.3 Participación en proyectos1.4 Ponencias en Congresos
Nacionales2. Docencia3. Investigación
3.1 Definición de router3.2 Objetivo3.3 Anotaciones3.4 Especificación de circuitos3.5 Lenguaje anfitrión3.6 Solución
4. Conclusiones 5. Trabajos futuros6. Plan de trabajo
Agenda:
33
Maestría en Ciencias Computacionales I. T. León (1998)
Adiestramiento en Investigación Tecnológica
Instituto de Investigaciones Eléctricas (Cuernavaca, México, 1995)
Ingeniería en Sistemas Computacionales I. T. Morelia (1994)
1. Currículum: 1. Currículum: FormaciónFormación
44
ProgramaciónProgramación de sistemas Programación para Internet Administración de archivos Redes de área localSistemas abiertosTópicos de redesTeleprocesoGraficación
1. Currículum: 1. Currículum: Materias Materias impartidasimpartidas
55
1. Currículum: 1. Currículum: Proyectos de Proyectos de I+DI+D
Sistema de graficación para QNXInstituto de Investigaciones Eléctricas
Asesor de proyectos de creatividad en etapas nacionales– Servidor genérico P2P – Sistema de monitoreo y control remoto
por Internet– Aplicaciones P2P
66
1. Currículum: 1. Currículum: Ponencias en Ponencias en Congresos NacionalesCongresos Nacionales
Intermediario para sistemas de información distribuidaCongreso de Ing. en Sist. Computacionales e Congreso de Ing. en Sist. Computacionales e Informática (I.T.Tuxtla Gutiérrez, Chiapas): CISCI’02Informática (I.T.Tuxtla Gutiérrez, Chiapas): CISCI’02
Propuesta de middleware para aplicaciones P2PSimposium Intertecnológico de Ciencias Simposium Intertecnológico de Ciencias Computacionales: SICI’01Computacionales: SICI’01
Servidor genérico para aplicaciones P2P1er. Congreso Nacional de Calidad en la Educación 1er. Congreso Nacional de Calidad en la Educación Superior Tecnológica: CNCEST’00Superior Tecnológica: CNCEST’00
77
2. Etapa de 2. Etapa de DocenciaDocencia
Materia Créditos
Ingeniería de requisitos O.O. 5
Bases de datos avanzadas 4
Tecnología software para ambientes web 5
Fundamentos lógicos de la Ingeniería de Software
4
Ingeniería de Software automática 4
88
3. Investigación: 3. Investigación: DefiniciónDefinición
cabeceraCarga útil
Paquete
Router
Dirección destino
Puertos de salida
Estructura de datos de rutas
Red destino PuertoTabla de encaminamiento
65.0.0.0/8
128.9.0.0/16
149.12.0.0/19
3
1
2
+Protocolos de encaminamiento
Routers extensibles
• Seguridad
• Políticas
• QoS
• Direcciones
• Evolución
99
3. Investigación: 3. Investigación: DefiniciónDefinición
Ejecución en un PC: Ejecución en un PC: • EnchufesEnchufes [Decasper et al. 1998], ETH Zurich & U. Washington [Decasper et al. 1998], ETH Zurich & U. Washington • ScoutScout [Peterson et al. 1999], U. Arizona, U. Princeton [Peterson et al. 1999], U. Arizona, U. Princeton • ClickClick [Kohler et al. 1999], MIT [Kohler et al. 1999], MIT
Ejecución en un PC + Procesador de Red: Ejecución en un PC + Procesador de Red: • VHDL + FPGAVHDL + FPGA [Lee et al. 1999], I.P. Virginia [Lee et al. 1999], I.P. Virginia• Intel IXP1200 + EnsambladorIntel IXP1200 + Ensamblador [Spalink et al. 2001], U. Princeton [Spalink et al. 2001], U. Princeton• NPClick + Intel IXP1200NPClick + Intel IXP1200 [Shah et al. 2003], U. Berkeley [Shah et al. 2003], U. Berkeley
Router Modular Router Modular Click Forma de Click Forma de grafosgrafos
Existen dos tipos: : [Spalink et al., 2001][Spalink et al., 2001]
1010
3. Investigación: 3. Investigación: ObjetivoObjetivoVentajas claras de los routers extensibles Ventajas claras de los routers extensibles (tema actual) respecto a los routers hardware(tema actual) respecto a los routers hardware
Actividad Actividad crucial en una red en una red Click debería Click debería tener un tener un entorno para especificación y y verificación de routers software, etc. verificación de routers software, etc. ¡No lo tiene!
ObjetivoObjetivo:: Desarrollar un lenguaje de Desarrollar un lenguaje de dominio específico sobre un lenguaje dominio específico sobre un lenguaje declarativo (multi-paradigma) para la declarativo (multi-paradigma) para la especificación y verificación de routers Clickespecificación y verificación de routers Click
1111
3. Investigación: 3. Investigación: AnotacionesAnotaciones
No existen antecedentes en la literatura del uso de un No existen antecedentes en la literatura del uso de un lenguaje declarativo para la especificación de routers lenguaje declarativo para la especificación de routers softwaresoftware
Existe un campo relacionado: Existe un campo relacionado: especificación y especificación y verificación de hardwareverificación de hardware
Explotamos la relación circuitos <-> grafos Click
Anfitrión
LibreríaDominio
Un lenguaje declarativo Un lenguaje declarativo empotradoempotrado es una librería que se incorpora a es una librería que se incorpora a un lenguaje ya existente un lenguaje ya existente LibreríaLibrería = Lenguaje de dominio = Lenguaje de dominio específicoespecífico
1212
3. Investigación: 3. Investigación: Especificación de Especificación de circuitoscircuitos
Especificación del lenguaje empotrado: Lava [Claessen, 2001]
Apoyado por Xilinx Inc.
halfAdd (a, b) = (sum, carry) where sum = xor (a, b) carry = and (a, b)
type Signal = [Bool]
and :: (Signal,Signal)->Signalxor :: (Signal,Signal)->Signal
type Signal = [Bool]
and :: (Signal,Signal)->Signalxor :: (Signal,Signal)->Signal
Librería
1313
3. Investigación: 3. Investigación: Especificación de Especificación de
circuitoscircuitos
sham1 (cmd, destReg, srcRegA, srcRegB) = (destReg’, aluOutput’) where (aluInputA, aluInputB) = regFile srcRegA srcRegB(destReg’,aluOutput’) aluOutput = alu cmd aluInputA aluInputB aluOutput’ = delay 0 aluOutput destReg’ = delay R0 destReg
• Especificación del lenguaje empotrado Hawk [Matthews, et al., 2000]
• Apoyado por Intel Inc.
1414
3. Investigación: 3. Investigación: Lenguaje Lenguaje anfitriónanfitrión
Curry es una extensión conservativa de Haskell (base de Lava / Hawk) con características de la programación lógica
CurryCurry
Proporciona el entorno apropiado para practicar verificación, simulación y análisis
Permitirá adaptar inmediatamente Lava y Hawk
Curry = lógica + funcional + concurrente + distribuida + OO = multi-paradigma
1515
3. Investigación: 3. Investigación: SoluciónSolución
FromDevice(eth0)->Print (“Paq:”)->Discard type Packet = [ Char ]
Caso Simple:
fromDevice :: Int -> PacketfromDevice _ = newPacket
print :: (String, Packet) -> Packetprint (s, px) = let p= s++px in p
discard :: Packet->Intdiscard p = 0
(->-->-) :: (a->b) -> ( b->c) -> a -> c(element1 ->- element2) inp = let mid = element1 inp in element2 mid
Conector de orden superior
(fromDevice ->-->- discard) 1
1616
3. Investigación: 3. Investigación: SoluciónSoluciónCaso a Caso a modelarmodelar::
Principal problema propio a un router::La conexión = ¿funciones? o ¿conectores? o ¿condicionales?
1717
3. Investigación: 3. Investigación: SoluciónSolución
router pkin = out where (pk, pto) = classifier pkin
pk2 = if pto==2 then paint pk 2 else GOTO . . .
CaracterísticasCaracterísticas::•Problema de salidas múltiples y condicionales
•Poco declarativo
•En Click no hay condicionales
1818
3. Investigación: 3. Investigación: SoluciónSolución
router:: Event -> Eventrouter inp = out where outclassif = classifier inp out = routerBranch outclassif
routerBranch (pk,0) = arpResponder (pk,0)routerBranch (pk,1) = arpQuerier (pk,1)routerBranch (pk,2) = out where st1 = paint (pk,2) 1111 st2 = strip st1 14 st3 = checkIPHeader st2 out = getIPAddress st3
type Event = (Packet, Puerto)
•Escritura de router mas cercana a Click Características::
•Incorporación de abstracción de eventos •Se aprovecha pattern matching para dar inteligencia a los elementos
1919
4.4. ConclusionesConclusiones
Los routers extensibles son un tema de actualidad que madurará y en el que Click sobresale
La especificación y verificación formal son de gran importancia para las empresas de hardware y ya hay esfuerzos basados en el uso de lenguajes declarativos. Curry podría tener un lugar ventajoso gracias a sus características multi-paradigma
Se han comprobado las ventajas de escribir un lenguaje empotrado con respecto la creación de un lenguaje nuevo (con intérprete, compilador, herramientas de verificación . . . )
2020
5. Trabajos futuros5. Trabajos futuros
Enlazar nuestro lenguaje con Click: Traductor de especificaciones Curry a Click (colaboración con E. Kohler, MIT)
Especificar los 242 elementos Click
Definir e implementar técnicas de análisis, verificación, etc. (concretas al dominio del problema) – Propiedades de un router:
No puede haber ciclos infinitos, verificar que a una entrada hay una salida, excepto con paquetes vencidosEl paquete sólo puede ser modificado en ciertos camposPara todo paquete debe haber una ruta de encaminamiento, etc.
2121
6. Plan de trabajo6. Plan de trabajo
Publicación PROLE’03 Publicación PROLE’03 (Terceras Jornadas (Terceras Jornadas sobre Lenguajes de Programación )sobre Lenguajes de Programación )
TESIS: Especificación (presente) Y TESIS: Especificación (presente) Y verificación (futuro) de routers softwareverificación (futuro) de routers software
Metodología de trabajo:Metodología de trabajo:– Contacto regular vía emailContacto regular vía email– Visita a la UPVVisita a la UPV– Asistencia a congresosAsistencia a congresos
Proyecto de I+D centrado en el temaProyecto de I+D centrado en el tema
2222
. . .. . .
top related