Servidor Radius II

30 10 2007

Retomando este tema seguiré exponiendo la información sobre los servidores Radius.

Existen algunos mensajes definidos por los RFC 2865 y 2866:

Access-Request→ Enviado por un cliente RADIUS para solicitar autenticación y autorización para conectarse a la red. Debe contener el usuario y contraseña (ya sea de usuario o CHAP); además del puerto NAS, si es necesario.

Access-Accept→ Enviado por un servidor RADIUS en respuesta a un mensaje de Access-Request. Informa que la conexión está autenticada y autorizada y le envía la información de configuración para comenzar a usar el servicio.

Access-Reject→ Enviado por un servidor RADIUS en respuesta a un mensaje de Access-Request. Este mensaje informa al cliente RADIUS que el intento de conexión ha sido rechazado. Un servidor RADIUS envía este mensaje ya sea porque las credenciales no son auténticas o por que el intento de conexión no está autorizado.

Access-Challenge→ Envío de un servidor RADIUS en respuesta a un mensaje de Access-Request. Este mensaje es un desafío para el cliente RADIUS. Si este tipo de paquete es soportado, el servidor pide al cliente que vuelva a enviar un paquete Access-Request para hacer la autenticación. En caso de que no sea soportado, se toma como un Access-Reject.

Accounting-Request→ Enviado por un cliente RADIUS para especificar información de cuenta para una conexión que fue aceptada.

Accounting-Response→ Enviado por un servidor RADIUS en respuesta a un mensaje de Accounting-Request. Este mensaje reconoce el procesamiento y recepción exitosa de un mensaje de Accouting-Response.

Para la implementación del servidor RADIUS, utilizamos las siguientes herramientas de hardware y software:

  • Una laptop con Linux que fungirá como servidor RADIUS (en nuestro caso, Ubuntu).
  • Un Access Point-Router WRV200 Business Service.
  • Laptops con tarjetas inalámbricas usadas como clientes.
  • FreeRADIUS como servidor.
  • MySQL para el almacenamiento de datos de usuarios.

A continuación se presentan los pasos a detalle seguidos para la configuración de FreeRADIUS.

Instalación

Actualmente, FreeRADIUS permite su instalación mediante la descarga y compilación del código fuente. Sin embargo, para su mejor manejo, resulta más práctico convertir el código fuente en un paquete Debian e instalarlo desde el mismo. Para ello, primero se instala lo siguiente para la construcción de paquetes Debian. Cabe mencionar que build-essential no funciona en cualquier sistema Debian.

# apt-get install build-essential
# apt-get install apt-src

Posteriormente, se actualizan las listas de paquetes disponibles (para que se descargue la versión más actual en los repositorios), se crea el directorio donde se guardará FreeRADIUS y se descarga.

# apt-src update
# mkdir ~/build_freeradius

# cd ~/build_freeradius

# apt-src install freeradius

El documento ‘rules’ en ‘~/build_freeradius/freeradius-1.1.3/debian’ debe modificarse para que las siguientes líneas se vean así:

#buildssl=--without-rlm_eap_peap --without-rlm_eap_tls
--without-rlm_eap_ttls --without-rlm_otp --without-rlm_sql_postgresql

--without-snmp
#modulelist=krb5 ldap sql_mysql sql_iodbc
buildssl=--with-rlm_sql_postgresql_lib_dir=`pg_config --libdir`
--with-rlm_sql_postgresql_include_dir=`pg_config --includedir`
modulelist=krb5 ldap sql_mysql sql_iodbc sql_postgresql

Esto hará que FreeRADIUS se instale con los módulos que necesitamos.

El archivo ‘control’, en el mismo directorio, debe verse así:

Source: freeradiusBuild-Depends: debhelper (>= 5), libltdl3-dev, libpam0g-dev, libmysqlclient15-dev | libmysqlclient-dev, libgdbm-dev,libldap2-dev, libsasl2-dev, libiodbc2-dev, libkrb5-dev, snmp, autotools-dev, dpatch (>= 2),libperl-dev, libtool, dpkg-dev (>= 1.13.19), libssl-dev, libpq-devBuild-Conflicts:

Esto hará que FreeRADIUS se asocie con las librerías que requiere para funcionar. En nuestro caso, principalmente, MySQL y SSL
Ahora se ejecutan los siguientes comandos para actualizar el archivo ‘control’ y para instalar las librerías sin problemas:

# cd ~/build_freeradius/freeradius-1.1.3/debian# cat control.postgresql >> control# apt-get install libssl-dev libpq-dev

Ahora deben cambiarse las siguientes líneas en el archivo ‘changelog’ encontrado en el directorio ‘~/build_freeradius/freeradius-1.1.3/debian/’.

freeradius (1.1.3-3ubuntu1tls) feisty; urgency=low* Add tls support for compilation-- reauthor <reauthor@gmail.com> Fri, 16 Mar 2007 20:22:40 +0200

Finalmente, se escriben los siguientes comandos para construir el paquete e instalarlo. Además, se requirió la instalación del paquete de conexión de FreeRADIUS con MySQL llamado: ‘freeradius-mysql_1.1.3-3ubuntu1tls_i386.deb’.

# cd ~/build_freeradius# fakeroot dpkg-buildpackage -b –uc freeradius# dpkg -i freeradius_1.1.3-3ubuntu1tls_i386.deb# dpkg -i freeradius-mysql_1.1.3-3ubuntu1tls_i386.deb

Al instalarse los paquetes, se ejecutan; para poder configurarlos, deben pararse con el siguiente comando:

# /etc/init.d/freeradius stop

Configuración

FreeRADIUS cuenta con diversos archivos que deben configurarse para lograr que funcione como se requiere. Los principales son: radiusd.conf, users, clients.conf, sql.conf y eap.conf, todos localizados en /etc/freeradius. A continuación se describe la configuración que debe haber en cada uno de ellos. Lo más importante se marca con rojo.

Radiusd.conf

Aquí solamente es necesario cambiar los argumentos relacionados con SQL, EAP y la configuración del dominio al que los clientes se conectarán. SQL se configura para que RADIUS se conecte a él para comparar la información de autenticación. EAP es el protocolo para la autenticación de usuario, usada normalmente en redes inalámbricas.
Este archivo de configuración es demasiado largo así que aquí sólo se presentan las secciones de interés que fueron modificadas. Para comenzar, debe sustituirse todo ${confdir} encontrado en el archivo por el directorio actual de FreeRADIUS, en nuestro caso ‘/etc/freeradius’.

modules { pap {auto_header = yes}chap {

authtype = CHAP}

pam {pam_auth = radiusd

}unix {

cache = nocache_reload = 600

radwtmp = ${logdir}/radwtmp}

$INCLUDE /etc/freeradius/eap.confmschap {

authtype = MS-CHAPuse_mppe = yes

require_encryption = yesrequire_strong = no

# Windows envía un nombre de usuario como DOMINIO\usuario;
# pero, en la respuesta a Challenge, sólo envía el
# usuario. Esto provoca un error. Al colocar sí en este
# hack, el error se corrige.with_ntdomain_hack = yes

}ldap {

server = "ldap.your.domain"basedn = "o=My Org,c=UA"

filter = "(uid=%{Stripped-User-Name:-%{User-Name}})"start_tls = no

access_attr = "dialupAccess"dictionary_mapping = ${raddbdir}/ldap.attrmap

ldap_connections_number = 5timeout = 4

timelimit = 3net_timeout = 1

}...

preprocess {huntgroups = /etc/freeradius/huntgroups

hints = /etc/freeradius/hintswith_ascend_hack = no

ascend_channels_per_line = 23# Mismo motivo que el pasado, pero para hacerlo en el

# preprocesamientowith_ntdomain_hack = yes

with_specialix_jetstream_hack = nowith_cisco_vsa_hack = no

}...

ippool main_pool {# Se coloca el rango de IPs disponibles y la máscara de

# redrange-start = 192.167.1.1

range-stop = 192.167.1.254netmask = 255.255.255.0

cache-size = 800session-db = ${raddbdir}/db.ippool

ip-index = ${raddbdir}/db.ipindexoverride = no

maximum-timeout = 0}

}
instantiate { execexpr}authorize {

preprocesschap

mschapsuffix

# EAP, activa el protocolo EAP para autorización. FILES, hace que

# se lea el archivo ‘users’. SQL, hace que se entre a la base de# datos de MySQL para buscar los datos del cliente.

eapfiles

sql}

authenticate {Auth-Type PAP {

pap}

Auth-Type CHAP {chap

}Auth-Type MS-CHAP {

mschap}

unix# Habilita la autenticación EAP

eap}

preacct {preprocess

acct_uniquesuffix

}accounting {

detailunix

radutmp# Lee las cuentas localizadas en la base de datos de MySQL

sql}

session {radutmp

# Usa MySQL en el manejo de sesionessql

}post-auth {

# Usa MySQL para las tareas de post-autenticaciónsql

}pre-proxy {

}post-proxy {

eap}

Sql.conf
Se decidió usar MySQL como backend para los usuarios de RADIUS debido a que permite administrarlos de forma simple y flexible. Es más sencillo agregar campos a una base de datos (que puede hacerse incluso desde una aplicación de escritorio o web) que modificar los archivos de configuración de FreeRADIUS.
Una vez que en el archivo de configuración ‘radiusd.conf’ se ha activado el soporte para SQL, debemos configurar el archivo ‘sql.conf’ que contiene información sobre el servidor SQL y las consultas que se deben hacer para obtener la información de los usuarios.
En las primeras líneas se da información sobre el servidor SQL, después viene la definición de las tablas y, por último, las consultas. Las consultas no se colocaron en este archivo, pero pueden verse en el archivo adjunto.

sql { driver = "rlm_sql_mysql"
 # Es importante colocar el IP del servidor. El usuario root o el

 # usuario que tenga permisos a la base de datos ‘radius’ que
 # después crearemos. Finalmente, se coloca la contraseña de este
 # usuario.
   server = "localhost"
   login = "root"
   password = "alipi"

 # Definición de base de datos y tablas

radius_db = "radius"acct_table1 = "radacct"

acct_table2 = "radacct"postauth_table = "radpostauth"

authcheck_table = "radcheck"authreply_table = "radreply"

groupcheck_table = "radgroupcheck"groupreply_table = "radgroupreply"

usergroup_table = "usergroup"nas_table = "nas"

deletestalesessions = yessqltrace = no

sqltracefile = ${logdir}/sqltrace.sqlnum_sql_socks = 5

connect_failure_retry_delay = 60sql_user_name = "%{User-Name}"

...}

Eap.conf
Se configura este archivo para que EAP (Extensible Authentication Protocol) funcione como protocolo de autenticación. EAP se utilizará como PEAP (Protected EAP). El cual, a su vez, usará MSCHAPV2 (Microsoft Challenge-Handshake Authentication Protocol). Además se requiere establecer la lista de certificados.

eap { # Se le dice que use PEAPdefault_eap_type = peaptimer_expire = 60

ignore_unknown_eap_types = nocisco_accounting_username_bug = no

md5 {}

leap {}

gtc {auth_type = PAP

}tls {

# Se cambian los ${raddbdir} por /etc/freeradiusprivate_key_password = whatever

private_key_file = /etc/freeradius/certs/cert-srv.pemcertificate_file = /etc/freeradius/certs/cert-srv.pem

CA_file = /etc/freeradius/certs/demoCA/cacert.pemdh_file = /etc/freeradius/certs/dh

random_file = /dev/urandom}

# Se le dice que use MSCHAPV2peap {

default_eap_type = mschapv2}

mschapv2 {}

}

Una vez configurado este archivo, deben crearse ligas simbólicas a los certificados que EAP necesita, para que pueda localizarlos. Para ello, se entra al directorio donde se guardan los certificados y se ejecuta un rehash.

# cd /etc/freeradius/certs# c_rehash

Users
Este archivo es el que contiene la información de los usuarios que pueden acceder a la red, en caso de que no se use otro método. En nuestro caso, este archivo no tiene mucho uso puesto que se usó una base de datos en MySQL. Todas las configuraciones que tengan como usuario DEFAULT, son las que se asignarán a los usuarios en caso de que no estén especificadas para ellos.

Clients.conf
Aquí se especifican los IPs o subredes desde las cuales se aceptarán peticiones. Si llega una petición de acceso desde un IP que no esté registrado aquí, el servidor RADIUS simplemente la ignora, negándole el acceso. En nuestro caso se acepta al localhost y al AP que enviará las solicitudes.

client 127.0.0.1 { secret = supersecretradiuskey

shortname = some_name 	  }

client 192.167.1.1 { # Esta clave es el shared secret que usará el AP para comunicarse

secret = lolo shortname = linksys-g

}

Todos estos archivos se encuentran adjuntos a la práctica para poder observarlos más a detalle. Con esto se da por finalizada la configuración del servidor RADIUS.
Para correr FreeRADIUS, una vez hechas todas estas modificaciones, se escribe el comando:

# /etc/init.d/freeradius start

Sin embargo,

# freeradius -X

permite observar todas las operaciones que se están llevando a cabo.

Configuración de MySQL
FreeRADIUS hace uso de una base de datos llamada radius.
Primero se entra a MySQL y se ejecuta el siguiente comando, para crearla:

mysql> create database radius;

Después, en la línea de comandos, se hace lo explicado abajo, lo cual correrá un script que FreeRADIUS trae consigo:

# cd /usr/share/doc/packages/freeradius/doc/examples/# mysql –u root -p radius < mysql.sql

Así ya se cuenta con una base de datos para la autenticación. Las tablas más importantes son:

  1. usergroup: Aquí se define a qué grupo pertenece cada usuario. Sus atributos son:
    • id. Identificador de registro.
    • UserName. Nombre de usuario.
    • GroupName. Grupo al que pertenece el usuarios
  2. radcheck: Aquí se definen las contraseñas de cada usuario. Sus atributos son:
    • id. Identificador de registro.
    • UserName. Nombre de usuario.
    • Attribute. Tipo de contraseña. En nuestro caso, ‘User-Password’.
    • Op. Es el operador que se usará para la comprobación. Para nosotros ‘==’.
    • Value. La contraseña.
  3. radreply: En esta tabla se definen los atributos sobre la conexión y sesión de los usuarios; por ejemplo, IP asignada y tiempo de espera máximo. En nuestro caso, permitimos que se asignen los de DEFAULT contenidos en el archivo ‘users’; por lo tanto, no insertamos nada en la tabla.
  4. radgroupreply: Similar a radcheck pero permite establecer atributos a un grupo de usuarios completo. Atributos:
    • id. Identificador de registro.
    • GroupName. Nombre de grupo.
    • Attribute. Nombre del atributo que se quiere agregar.

Nosotros sólo hicimos uso de uno, el tipo de autenticación: ‘Auth-Type’.
Op. Es el operador que se usará para la comprobación. Para nosotros ‘:=’.
Value. El valor del atributo. Nuestro Auth-Type es ‘EAP’.

Después de realizar todos los pasos anteriores todavía nos falta el configurar el AP para que realmente utilice el Radius para la autenticación, ésto lo encontraras en el siguiente archivo, que también contiene todo lo anterior; decidí subir el archivo y publicar lo anterior porque a la mayoría de las personas únicamente les interesará el configurar el Servidor Radius, y a otros pocos ya el utilizarlo en alguna aplicación como es la implementación de la autenticación en un AP.

El archivo lo puedes conseguir dando click aquí.

Sin más esperando que les sea útil, y agradeciendo a los miembros de mi equipo nuevamente por su coolaboración en la realización del práctica (del cuál el archivo es el reporte de práctica) me despido hasta el próximo post!.

Anuncios




¡USB Key de 128 Gb!

28 10 2007

Samsung ha anunciado que está lista para poder empezar a fabricar memorias USB de 128 Gb, pero ¿cómo es esto posible?

30 nm chip Durante años se ha estado discutiendo sobre las diferentes tecnologías que podrían sustituir al flash memory como medio de almacenamiento, es incuestionable que ésta tecnología ha logrado superarse y mantenerse inceiblemente. Samsung dice que ha logrado desarrollar el primer chip de 30nm (1 nanómetro= 1×10^-9 m), que es capaz de brindar una capacidad de 64 Gb, lo que es equivalente a cuatro veces la capacidad máxima que es comercializada hoy en día.

Al utilizar el modelo de producción de chips de 30nm uno de éstos chips representa la capacidad de 8Gb, mientras que una memorira como SD podría utilizar 16 de éstos para brindar capacidades de 128 Gb. Los discos duros podrían utilizar 64 de estos chips para poder brindar capacidades de 512Gb.

Las memorias que promete Samsung de 128Gb no son únicamente impresionantes por el hecho de que proveerán espacio para 32,000 archivos de música u 80 películas en calidad DVD, sino porque también está más allá de lo que se considera lo “standar” en máxima capacidad para discos duros en laptops, 80Gb. Lo más impresionante según Samsung es que estos chips no son ciencia ficción, la compañía espera poner en producción masiva los chips para el año 2009.





Everybody Is Free To Wear Sunscreen!

26 10 2007

Pues el otro día oyendo el radio a altas horas de la madrugada, escuchando la emisora Imagen que pasa canciones algo curiosas/interesantes y buenas a esas horas de la madrugrada me topé con una canción que me empezó a envolver por el contenido de su letra, y pues cómo todo buen estudiante de sistemas no dude ni un segundo en encender mi computadora y “googlear” parte de las frases que oí.

De éste modo es como terminé sabiendo que la canción que estaba oyendo se llamaba “Everybody Is Free To Wear Sunscreen”, la canción fue sacacda al mercado por el director australiano Baz Luhrmann en 1998 en el album “Something For Everybody”.

La canción incluye un track leído de frases cómicas pero que en cierto modo te hacen reflexionar, sobre un track de música melosa/triste. El track de las frases es leído por el actor vocal autraliano Lee Perry y el coro de la canción es interpretado por Quindon Tarver.

La letanía que se lee se sacaron de la columna de Schmich de 1997 que se publicó en el “Chicago Tribune”, y es una columna de consejos muy popular y controversial.

Sin Más Preambulo aquí les dejo la letra de la canción en inglés así como un video que contiene subtitulos en español.

 

Letra:

Ladies and Gentlemen of the class of ’99
Wear Sunscreen.
If I could offer you only one tip for the future, sunscreen would be
it. The long term benefits of sunscreen have been proved by
scientists whereas the rest of my advice has no basis more reliable
than my own meandering experience…
I will dispense this advice, now.

Enjoy the power and beauty of your youth;
oh nevermind; you will not understand the power and beauty of your youth until they’ve faded.
But trust me, in 20 years you’ll look back at photos of yourself, and recall in a way you can’t grasp now how much possibility lay before
you and how fabulous you really looked….
You are not as fat as you imagine.

Don’t worry about the future; or worry, but know that worrying is as
effective as trying to solve an algebra equation by chewing bubblegum.
The real troubles in your life are apt to be things that never crossed your worried mind;
the kind that blindside you at 4pm on some idle Tuesday.

Do one thing everyday that scares you

Sing

Don’t be reckless with other people’s hearts, don’t put up with people who are reckless with yours.

Floss

Don’t waste your time on jealousy;
sometimes you’re ahead, sometimes you’re behind; the race is long,
and in the end, it’s only with yourself.

Remember the compliments you receive, forget the insults;
if you succeed in doing this, tell me how.

Keep your old love letters, throw away your old bank statements.

Stretch

Don’t feel guilty if you don’t know what you want to do with your life…
the most interesting people I know didn’t know at 22 what they wanted to do with their lives,
some of the most interesting 40 year olds I know still don’t.

Get plenty of calcium.

Be kind to your knees, you’ll miss them when they’re gone.

Maybe you’ll marry, maybe you won’t,
maybe you’ll have children, maybe you won’t,
maybe you’ll divorce at 40,
maybe you’ll dance the funky chicken on your 75th wedding anniversary…
what ever you do, don’t congratulate yourself too much
or berate yourself either – your choices are half chance,
so are everybody else’s.
Enjoy your body, use it every way you can,
don’t be afraid of it, or what other people think of it,
it’s the greatest instrument you’ll ever own..

Dance…even if you have nowhere to do it but in your own living room.

Read the directions, even if you don’t follow them.

Do NOT read beauty magazines, they will only make you feel ugly.

Get to know your parents, you never know when they’ll be gone for good.

Be nice to your siblings, their your best link to your past and the people most likely to stick with you in the future.

Understand that friends come and go, but with the precious few you should hold on.
Work hard to bridge the gaps in geography and lifestyle because the older you get,
the more you need the people you knew when you were young.

Live in New York City once, but leave before it makes you hard;
live in Northern California once, but leave before it makes you soft.

Travel.

Accept certain inalienable truths, prices will rise, politicians will philander,
you too will get old and when you do you’ll fantasize that when you were young
prices were reasonable, politicians were noble and children respected their elders.

Respect your elders.

Don’t expect anyone else to support you.
Maybe you have a trust fund, maybe you’ll have a wealthy spouse;
but you never know when either one might run out.

Don’t mess too much with your hair, or by the time you’re 40, it will look 85.

Be careful whose advice you buy, but, be patient with those who supply it.
Advice is a form of nostalgia, dispensing it is a way of fishing the past from the disposal,
wiping it off, painting over the ugly parts and recycling it for more than it’s worth.

But trust me on the sunscreen…





Algoritmos De Búsqueda

25 10 2007

Algoritmo A* De BúsquedaMap

El algoritmo A* es usualmente utilizado en los problemas para encontrar la mejor ruta o camino, lo que realiza el algoritmo es construir todas las rutas desde un punto inicial hasta encontrar alguna que llegue al nodo final o meta. De éste modo solamente construye aquellas rutas que son candidatas a formar una solución o camino desde el inicio hasta el nodo final.


Para poder determinar que rutas son las que tienen mayor probabilidad de llegar al nodo meta, el algoritmo utiliza una heurística basada en la distancia de cualquier punto dado hacía la meta. Donde se diferencia el algoritmo A* de otros algoritmos avaros de “best-first search” es el hecho de que va tomando en cuenta la distancia que ya ha recorrido hasta el momento, haciendo de este modo una respuesta mucho más completa y óptima.

A* es una combinación entre los algoritmos de búsqueda de anchura con algoritmos de profundidad, esto debido a la función que utiliza f(n)= g(n)+h(n), dónde h(n) [que tiende primero a profundidad] representa el valor heurístico del nodo a evaluar y g(n) [que tiende a primero en anchura] representa el costo real del camino recorrido para poder llegar al nodo. Lo anterior lo posibilita a cambiar de camino de búsqueda cuando se encuentra un camino que pareciera ser más óptimo.
Los usos que se le pueden dar a éste algoritmo son el de trazar las rutas para llegar de una ciudad a otra, algo como lo que tiene la Secretaría de Comunicaciones y Transportes para trazar la ruta de una ciudad a otra sacando el menor costo y recorrido posible. La aplicación se llama “Traza Tú Ruta”
.

Algoritmo “Best-First-Search”
Éste algoritmo es una optimización de “breadth-first search” y lo mejora al expandir el nodo más prometedor a través de alguna regla dada. Lo que intenta realizar el algoritmo es estimar el porcentaje de probabilidad de que el nodo “n” sea la mejor opción al utilizar una heurística de evaluación de una función f(n), que depende mayormente en la descripción de “n”, es decir en la habilidad para poder describir la meta y la información que se conoce hasta el punto en el que el algoritmo se encuentra así como cualquier otra información que sea relevante para el problema.


Así el algoritmo busca predecir que tan cercano a una solución es un camino dado, esto lo realiza extendiendo los caminos que se encuentran más cercanos a dicha solución primero, el modo específico de búsqueda se conoce como “greedy best-first search”. La implementación más eficiente para la selección del mejor candidato por extensión es a través de una cola de prioridad.
domino
Creo que uno de los mejores uso que se le puede dar a éste algoritmo es la teoría de juego. Podemos ver claramente como la computadora va a ser capaz de ir seleccionando “la mejor opción hasta el momento” para ganar, o ir prediciendo cuales son los movimiento que podrán seguirle a cierta tirada.


Aunque debemos de tener en cuenta que no podrá ser aplicable para todos los juegos puesto que por ejemplo en el ajedrez simplemente para el 4to movimiento el número de posibles jugadas o movimientos es de 9,100,000, y este es un número que va aumentando exponencialmente, llegando a un total posible en el orden de los veinte septillones, es decir 20×1042.

Simulated Annealing
Éste es un algoritmo de probabilidad que busca y localiza la mejor aproximación posible para el resultado óptimo de una función dada dentro de un universo de búsqueda amplio. Se utiliza generalmente cuando el campo de búsqueda es discreto, por ejemplo los tours que visitan determinadas ciudades.


Su nombre y la idea principal provienen del método en la metalurgia de recocido, que conllevan el calentamiento y enfriamiento controlado de los materiales para elevar el número de cristales y reducir sus defectos.recocido
En éste algoritmo cada punto “s” del universo de búsqueda es comparado con el estado de algún sistema físico, y la función que se utiliza E(s) es interpretada como la energía interna del sistema en ese estado dado. La meta es llevar al sistema de un punto aleatorio inicial a un estado en el cual éste tenga la menor cantidad posible de energía.


En cada paso el algoritmo considera a algunos de los vecinos del actual estado “s”, y probabilísticamente calcula y decide si debe de moverse a alguno de ellos. Las probabilidades son escogidas de tal forma que el sistema tienda a tener menor cantidad de energía. Éste paso es repetido uno número de iteraciones determinadas por el programador o hasta que se alcance un estado de energía que sea aceptable para el sistema.

Para poder aplicar éste algoritmo a un problema en específico es necesario que uno le proporcione los siguientes parámetros: el universo de estados, la meta en energía de la función E(s), la forma de generar a los candidatos a través de una función vecinos(), el nivel de aceptación probabilística en función P() y el itinerario de recocido temp(). Todos estos parámetros tienen un impacto significativo en la eficiencia del método. Lamentablemente no existe un modo de determinar que opciones de valores serán los mejores para cada problema, y no hay forma de encontrarlos para u n problema en específico.

Su uso puede ser para cualquier problema de búsqueda de mejor camino, o mejor opción siempre y cuando se puede generar los parámetros arriba mencionados que se necesitan para el funcionamiento del mismo.

Hill Climbing
Éste algoritmo pertenece a los de búsqueda local, y su implementación es bastante sencilla lo cual lo hace muchas veces la opción favorita por muchos a pesar de que existan algoritmos que puedan dar mejores y más exactos resultados.

El algoritmo puede ser utilizado en la resolución de problemas que tienen varias posibles soluciones pero en las cuales algunas son mejores que otras. El algoritmo se comienza con una de estas soluciones escogidas al azar. Y poco a poco va buscando una mejora a dicha solución, por más mínima que ésta sea. Hasta que el algoritmo llega a un punto en el que ya no puede encontrar ninguna mejora a la solución y es entonces cuando termina. Por lo general cuando llega a éste punto la solución es bastante cercana a la más optima, aunque nunca se puede garantizar que llegue a la óptima.

Lo que realiza el algoritmo es el buscar maximizar o minimizar una función f(x) dada, donde “x” se refiere a estados discretos del problema. Estos estados usualmente son representados por vértices en una gráfica. Así el algoritmo va a seguir una gráfica de vértice a vértice, siempre aumentando o disminuyendo localmente el valor de la función hasta encontrar un máximo o mínimo local.

Ant Colony Optimization
Es un algoritmo que utiliza probabilidad para solucionar problemas computacionales a través de la búsqueda de los mejores caminos en un grafo. Está inspirado en el modo en como las hormigas pueden encontrar el mejor camino hacía su colonia desde un punto dado.

Básicamente lo que éste algoritmo hace es tener una o varías hormigas dentro del grafo que van a ir recorriendo dicho grafo a través de diferentes caminos y/o decisiones, y van a ir depositando un valor de “feromona” en los caminos que utilizen para realzar la importancia del mismo. Cada feromona en el camino va a ir disminuyendo un porcentaje que el programador decide, esto es para que si éste durante un dado periodo no es visitado pierda la importancia.

De éste modo el algoritmo va a ir encontrando un camino óptimo para poder visitar todos los nodos del algoritmo de una manera sencilla (no se puede asegurar que la más óptima). El algoritmo se corre tantas veces como el programador lo requiera o hasta que no exista alteraciones sustanciales en los valores del camino encontrado, lo cual indica que el algoritmo a llegado a un punto estable.

Éste algoritmo se puede utilizar para encontrar las mejores (no se sabe si óptimas) rutas para visitar cierto “universo” de ciudades o lugares dados, o como lo mencioné en un principio cualquier problema computacional que pueda ser representado a través de grafos.





FLib…. “A Java Library”

18 10 2007

FLIB

Pues navegando por Internet buscando un componente para NetBeans para poder añadir un calendario de una forma fácil y eficiente, me di cuenta que había demasiadas implementaciones (Java Component V5.1, Mig Calendar Component, etc), pero el problema es que todas ellas cobraban entre $50 y $120 dólares, lo cuál seamos honestos es una exageración por un pedazo de código de 800Ks….

Cuando estaba apunto de darme por vencido en la página número 14 de Google encontre un vínculo a FLib la cuál es una librería diseñada por Tony Freixas, se trata de una librería de código abierto de alta calidad de tres componentes para Java:

JCalendar es un componente para calendarios, se puede utilizar para desplegar la fecha y/o el tiempo para dejar que el usuario las seleccione; viene en dos formas: un panel que contiene un calendario y una “combo box” con un calendario que se despliega al darle click.

JWizard es un componente para realizar los “Wizards” de instalación, es decir las pantallitas que nos llevan de la mano a través del proceso para completar alguna tarea como intalar un programa, configurarlo, etc. Es bastante sencillo de utilizar y contiene todas las características que tienen éste tipo de ventanas como son un logo del lado izquierdo, un título, un subtítulo para cada ventana, botones de atrás, siguiente, terminar, cancelar y ayuda, entre otras características.

TableLayout es como su nombre lo índica un manejador de layouts. Está altamente basado en HTML para de éste modo poder remplazar completamente el complicado GridLayout.
Espero que les sea de utilidad y pues es hora que continué programando mi proyecto final de APIS….





Multiplicación Egipcia

16 10 2007

También es conocida como multiplicación por duplicación y para realizarla no es necesario conocer la tabla de multiplicar, si aquella que nos hicieron aprender desde pequeños, simplemente necesitamos saber sumar.

En el antiguo Egipto es el modo en como realizaban las multiplicaciones y se conocía como “multiplicación y mediación”; actualmente éste método es utilizado lamentablemente únicamente por campesinos y otras personas muy escazas en países como Rusia.

Pero que mejor forma de explicar éste método que realizando un ejemplo para que todos podamos seguirlo paso a paso y pues… quien sabe aprender a realizar las multiplicaciones de un modo más sencillo… bueno para alguien que no sepa multiplicar. Así que vayamos a los pasos a seguir por el algoritmo y posteriormente ejemplificaremos con números.

Supongamos que deseamos multiplicar W x Z los pasos a seguir son los siguientes:

  1. Escribimos en una primera columna la serie 1, 2, 4, 8, 16, … mientras que sea menor a W (2^n<W), esto se puede obtener sumando las anteriores.
  2. Posteriormente escribimos una segunda columna donde se pondrá la serie: Z, 2Z, 4Z, 8Z, .., del mismo modo lo realizaremos sumando las anteriores.
  3. Ahora en la tercera columna necesitamos marcar los renglones que contengan los números en la primera columna que nos den como resultado “W”, esto lo realizamos checándolo del mayor al menor.
  4. De éste modo el resultado se obtiene simplemente sumando las cifras que se encuentran en la 2° columna de los renglones marcados.

Vgr:

67 X 82

                    1        82 
                    1        82  Ok
                    2       164  Ok
                    4       328
                    8       656
                   16      1312
                   32      2624
                   64      5248  Ok
                           5494=(5248+164+82)

Se escogieron los renglones que tienen en la primer columna 64, 2 y 1 debido a que 64+2+1=67 que es nuestro número “W”.

El resultado es la suma de los números que están en esos renglones en la segunda columna (5248, 164 y 82).

Pues espero les parezca interesante este nuevo método y pues espero sus comentarios!

P.S. Agradesco a Palacios por su idea para éste post!





USB 3.0

8 10 2007

USBIntel y otras manufactureras planean sacar al mercado la nueva versión de la ubicua tecnología USB durante la primera mitad del año 2008, se ha comentado que el nuevo puerto soportará velocidades 10 veces más rápidas al agregar un vínculo de fibra óptica además de los usuales cables de cobre.

Intel junto con Microsoft, Hewlett-Packard, Texas Instruments, y otros está trabajando para poder liberar las especificaciones de la nueva tecnología lo antes posible.

Cómo el lanzamiento de una nueva tecnología siempre lleva más o menos dos años entre que se libera la especificación y ésta se pone disponible en el mercado, se calcula que los primeros puertos USB 3.0 empezaran a rondar el mercado para el 2009 o 2010.

El actual estándar, el USB 2.0, tiene una velocidad de transferencia tope de 480 Mb/s, por lo que un incremento de diez veces significará a aproximadamente 4.8 Gb/s. Muchos dispositivos no necesitan de ésta cantidad de transferencia tan elevada, pero algunos otros podrían llegar a utilizar inclusive más como podrían ser discos duros, tarjetas flash y dispositivos ópticos como DVD’s, Blu-ray y HD DVD. Actualmente cuando necesitamos mayor velocidad utilizamos el puerto IEEE 1394 “FireWire” que llega a transferir a una velocidad tope de 800 Mb/s.

No debemos de preocuparnos por cuando llegue la nueva tecnología, puesto que todos nuestros aparatos que funcionaban con la versión 2.0 podrán seguir funcionando con la versión 3.0.