Internet Packet Routing with the Boost Graph Library
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
In the last article, I introduced you to the Boost Graph Library (BGL) and showed you how to apply the BGL in the implementation of a make-like software build system. You constructed a graph object using the adjacency_list class with the add_edge and add_vertex functions, and you applied the topological_sort function to determine the order in which files should be compiled. You used depth_first_search to check whether there were any cycles in the file dependencies. This next challenge is to implement the core of an Internet router that adheres to the Open Shortest Path First (OSPF) protocol. First, however, let's quickly review how Internet routing works.
Internet Routing
When a computer sends a message to another using the Internet Protocol (IP), the message contents are put into a packet. In addition to its message data (payload), each packet includes metadata such as source and destination addresses, the length of the data, the sequence number, and so on. If the message is large, the data is split into smaller parts, each of which is turned into a packet. The individual parts are given sequence numbers so that the receiver can reassemble the original message.
If the destination address for the packet is outside the local network, the packet is sent from the originating machine to an Internet router. The router directs packets that it receives to other routers based on its routing table, which is constructed based on a routing protocol (I will discuss a couple of these protocols). After traveling from one router to the next (each step is called a hop), the packets arrive at their destination. If the network is congested, some packets might be dropped en route. Higher-level reliable protocols such as the Transmission Control Protocol (TCP) use handshaking between sender and receiver so that dropped packets are retransmitted. The UNIX program traceroute (or the Windows program tracert) can be used to show the route taken from your computer to other sites around the Internet.
The ultimate goal of a routing protocol is to deliver packets to their destinations as quickly as possible. A number of factors determine how long a packet takes to arrive (for example, the number of hops along the path, transmission delay within a router, transmission delay between routers, and network bandwidth). The routing protocol must choose the best paths between routers; this information is stored in a routing table.
The routing problem can be modeled as a graph by associating a vertex with each router and an edge for each direct connection between two routers. Information such as transmission delay is attached to each edge. Figure 1 shows a graph model for a simple router network.
){kind=link}
Figure 1 A set of Internet routers connected to one another, with the connections labeled with the mean transmission delay.