7.19. Problemas de la ruta más corta¶
Cuando usted navega por la web, envía un correo electrónico o ingresa a una computadora del laboratorio desde otra ubicación en el campus, tras bambalinas se lleva a cabo mucho trabajo para transferir la información de su computadora a otra computadora. El estudio en profundidad de cómo fluye la información de una computadora a otra a través de Internet es el tema principal de una asignatura de redes de computadoras. Sin embargo, hablaremos lo suficiente sobre cómo funciona Internet como para entender otro algoritmo de grafos muy importante.
Figura 1: Descripción general de la conectividad en Internet¶
Figura 1: Descripción general de la conectividad en Internet
La Figura 1 muestra una visión general de alto nivel de cómo funciona la comunicación en Internet. Cuando usted usa su navegador para solicitar la consulta de una página web de un servidor, la solicitud debe viajar a través de su red de área local y salir a Internet a través de un enrutador. La solicitud viaja a través de Internet y finalmente llega a un enrutador para la red de área local donde se encuentra el servidor. La página web que usted solicitó viaja a través de los mismos enrutadores para llegar a su navegador. Dentro de la nube etiquetada como “Internet” en la Figura 1 hay enrutadores adicionales. La tarea de todos estos enrutadores es trabajar juntos para lograr que su información viaje de un lugar a otro. Usted podría verificar que hay muchos enrutadores para su computadora si ésta admite el comando traceroute. El texto mostrado a continuación presenta la salida del comando traceroute que ilustra que hay 13 enrutadores entre el servidor web en el Luther College y el servidor de correo en la Universidad de Minnesota.
1 192.203.196.1
2 hilda.luther.edu (216.159.75.1)
3 ICN-Luther-Ether.icn.state.ia.us (207.165.237.137)
4 ICN-ISP-1.icn.state.ia.us (209.56.255.1)
5 p3-0.hsa1.chi1.bbnplanet.net (4.24.202.13)
6 ae-1-54.bbr2.Chicago1.Level3.net (4.68.101.97)
7 so-3-0-0.mpls2.Minneapolis1.Level3.net (64.159.4.214)
8 ge-3-0.hsa2.Minneapolis1.Level3.net (4.68.112.18)
9 p1-0.minnesota.bbnplanet.net (4.24.226.74)
10 TelecomB-BR-01-V4002.ggnet.umn.edu (192.42.152.37)
11 TelecomB-BN-01-Vlan-3000.ggnet.umn.edu (128.101.58.1)
12 TelecomB-CN-01-Vlan-710.ggnet.umn.edu (128.101.80.158)
13 baldrick.cs.umn.edu (128.101.80.129)(N!) 88.631 ms (N!)
Enrutadores desde un servidor hasta el siguiente en Internet
Cada enrutador en Internet está conectado a uno o más enrutadores. Así que si usted ejecuta el comando traceroute en diferentes momentos del día, es probable que vea que su información fluye a través de diferentes enrutadores en momentos diferentes. Esto se debe a que hay un costo asociado con cada conexión entre una pareja de enrutadores que depende del volumen de tráfico, la hora del día y muchos otros factores. En este momento no le sorprenderá saber que podemos representar la red de enrutadores como un grafo con aristas ponderadas.
Figura 2: Conexiones y ponderaciones entre enrutadores en Internet¶
Figura 2: Conexiones y ponderaciones entre enrutadores en Internet
La Figura 2 muestra un pequeño ejemplo de un grafo ponderado que representa la interconexión de enrutadores en Internet. El problema que queremos resolver es encontrar la ruta con la menor ponderación total a través de la cual enrutar cualquier mensaje dado. Este problema debería sonar familiar pues es similar al problema que resolvimos usando una búsqueda en anchura, excepto que aquí nos interesa la ponderación total de la ruta en lugar del número de saltos en ella. Cabe señalar que si todas las ponderaciones son iguales, el problema es el mismo.