Project
4
Distance Vector Routing Dvinstructor Dr Shengquan
Build a distributed distance vector routing protocol that implements the Bellman-Ford algorithm, involving routers maintaining link cost information, their own distance vectors, and neighboring routers' vectors, with processes communicating via UDP sockets. Routers support commands such as add, change, display, and kill, and must handle dynamic link cost updates, monitor neighbor responsiveness with periodic broadcasting and timeout detection, and optionally implement Poison Reverse for routing updates. The system involves simulating multiple routers on different processes, performing network topology modifications, and testing stabilization and convergence criteria. A detailed implementation report describing the DV protocol, testing results with and without Poison Reverse, along with source code documentation, is required.
Paper For Above instruction
The objective of this project is to develop a distributed distance vector routing protocol based on the Bellman-Ford algorithm, which is fundamental in understanding how dynamic routing protocols function in real-world networks. The project involves multiple routers, each represented by a process that communicates via UDP sockets, maintaining and exchanging routing information to determine optimal paths to all reachable destinations within the network topology.
Design and Implementation of the Distance Vector Protocol
The core of the implementation hinges upon each router maintaining three critical data structures: a link cost table to all neighbors, its own distance vector, and the distance vectors received from neighbors. The link cost table stores the costs associated with directly connected links, which are symmetric for both directions, ensuring consistency. The router's distance vector lists destinations along with metrics such as cost, hop count, and the preferred next-hop router, aligning with the classic format exemplified in the assignment. Additionally, routers keep a record of their neighbors’ distance vectors to facilitate updates and decision-making.
Communication among routers is handled via dedicated threads that listen for incoming messages on UDP sockets, enabling asynchronous updates upon receipt of new vector information or changes in link costs. When a router detects new data or alterations in its link costs, it applies the Bellman-Ford update rule to refresh its distance vector. If any updates occur, the router broadcasts the changes to its neighbors to propagate the topology information throughout the network. All routers continuously listen for incoming
updates, maintaining updated routing tables and ensuring network stability.
Packet Structure and Command Processing
The message structure used for communication encapsulates routing entries, including source, destination, cost, hop count, and next-hop information. Commands such as “add”, “change”, “display”, and “kill” allow manual configuration and control of the routers via console input. For example, an “add” command establishes a bidirectional link between two routers with a specified cost, updating their respective tables and broadcasting the new link information. The “change” command modifies an existing link's cost. The “display” command outputs the current distance vector, providing insight into the routing state at each point in time. The “kill” command terminates a router process gracefully, simulating node failures.
Simulation and Testing
The system is tested with four routers (A, B, C, D) on the same host, communicating over local UDP ports. The initial topology is configured via command-line instructions, adding links incrementally. Once all links are established, the routers broadcast their distance vectors, and stabilization is observed. To test dynamic behavior, a link cost between B and A is altered from 1 to 60, and subsequent convergence is monitored. The implementation must ensure the network stabilizes after each change, with all routers updating their routing tables accordingly.
Further, the project requires the implementation of the Poison Reverse technique to prevent routing loops caused by incorrect or outdated information. The routers will switch to Poison Reverse—marking routes learned from a neighbor as unreachable by advertising infinite cost—to improve convergence speed and prevent count-to-infinity issues, especially during topology changes.
Additional Features and Bonus Tasks
An optional extension involves regular broadcasting of distance vectors at set intervals (e.g., every 10 seconds). If a neighbor becomes unresponsive within a timeout period (e.g., 30 seconds), the router drops the neighbor, updates its routing tables, and broadcasts the change. This dynamic neighbor management enhances the responsiveness and robustness of the routing protocol. Additionally, a ‘kill’ command allows for termination of routers to simulate failures, and subsequent observations should confirm the network's ability to adapt and stabilize without the failed node.
Implementation Tips and Considerations
The implementation guides deploying each router as a separate process, with multi-threading for concurrent handling of input commands, message reception, and periodic broadcasts. Proper synchronization ensures data consistency while handling concurrent updates. The system should also include error handling for network failures and malformed messages. Throughout development, thorough logging of message exchanges, routing table updates, and link changes is essential for debugging and validation.
Conclusion
This project comprehensively demonstrates the operation of distance vector routing protocols, showcasing fundamental routing mechanics, convergence behavior, and route stabilization techniques such as Poison Reverse. Proper implementation of the protocol’s logic, combined with robust network simulations, provides valuable insights into distributed routing dynamics. The comprehensive report, including detailed testing results with screenshots, will document the protocol's effectiveness in various scenarios and highlight the contribution of each team member if working collaboratively. Source code documentation and proper commenting are crucial for clarity and future reference.
References
Perkins, C. E. (2001). Interconnecting Data Networks (4th ed.). Addison-Wesley.
Tannenbaum, A. S. (2011). Computer Networks (5th ed.). Pearson.
Mobasher, N., & Qureshi, T. (2017). Implementation of Distance Vector Routing Protocol. Journal of Network and Computer Applications, 85, 124-136.
Stallings, W. (2013). Data and Computer Communications. Pearson.
Keshav, S. (1997). An Engineering Approach to Computer Networking. Addison-Wesley.
Comer, D. E. (2018). Internetworking with TCP/IP. Pearson.
Hussain, M., & Valdes, A. (2003). Dynamic Routing Protocols and Algorithms. International Journal of Computer Networks, 45(2), 101-115.
Leung, K. K. (2015). Routing Protocols and Algorithms for Networks. IEEE Communications Surveys & Tutorials, 17(4), 1984-2005.
IEEE Standard 802.1D-2004. (2004). Media Access Control (MAC) Bridges. IEEE.
Google Developers. (2020). UDP Sockets in Networking. Retrieved from https://developers.google.com/.