HSLS Proof

David Young
29 Jun 2004

Below are the logs recorded by the HSLS routing daemons on a five-router testbed consisting of both wired and wireless links. The HSLS daemon was instrumented so that we could cause a link-state change by sending a signal with the UNIX "kill" command. The signal causes the router to simulate the link's failure, first; then the link's restoration.

The routers are called "powerbook," "noam," "cuw," "istaboot," and "staboot." They were connected in a chain, powerbook to noam (wire), noam to cuw (wireless), cuw to istaboot (wire), and istaboot to staboot (wireless). All the routers' clocks were synchronized to within one second.

The operator provoked a change of link-state on powerbook five times, at 08:34:11, 08:34:16, 08:34:25, 08:34:36, and 08:34:53. In the logs, the link-state changes can be seen propagating across the chain of routers according to the Adaptive HSLS limited dissemination algorithm. For example, at 08:34:11, staboot indicates that it receives powerbook's link-state update after four hops; staboot retransmits the update:

08:34:11 staboot hslsd: LSU (hopcount 3, hoplimit 65535, oseqno 2)
08:34:11 staboot hslsd: RELAY LSAs begin
08:34:11 staboot hslsd: RELAY link powerbook <- noam-tlp0 seqno 2 flags 0
08:34:11 staboot hslsd: RELAY LSAs end
08:34:11 staboot hslsd: RELAY retransmitted 65535-hop LSU

Also at 08:34:11, the routers on the path between staboot and can be seen relaying the link-state update.

Logs are plain text files and will open in new windows.