Do You Know the Way to Vertex A ?
Jeffrey Ondich · American Mathematical Monthly · 1994
When I want to communicate with a member of my wife's family, it is often most efficient to send my message through my mother-in-law, Elinor. At any given moment, Elinor knows where everyone is, what they are doing, and the easiest way to reach them. Especially if I want to broadcast a message to the whole family, Elinor provides me with a fast, reliable communication mechanism. When I send electronic mail to a friend on the Internet, things are a bit different. My message gets divided into one or more packets (depending on how long-winded I am that day), and each packet is handed from machine to machine until it reaches my friend's computer. There is no central, omniscient authority like Elinor on the Internet, so each machine along each packet's path needs to make its own routing decisions. That is, each machine must decide which of its neighbor machines should receive my packet to ensure the most efficient delivery of my message. Elinor provides my family's communication system with centralized control. Of course, if Elinor gets sick or heads out in the camper with no forwarding address, our system will be in trouble. To avoid similar problems, the Internet relies on distributed control of its communications. In this column, I will describe one class of distributed algorithms used by portions of the Internet to make routing