routing algorithm implementation assignment

Assignment 2

Routing simulations, distance vector, is due thursday, february 23 (midnight), description, obtaining, building, and running the simulator.

  Corporate and Professional Publishing Group

An engineering approach to computer networking, by s. keshav.

ISBN 0-201-63442-2 * Hardcover * 688 pages * 1997

Book Description · Preface · Glossary · Bibliography · Solutions · Slides · Simulator · Exercises · Errata · Cover (73K) · Ordering Information · C&P Welcome Page .

Link-State Routing

Assignment designed by Snorri Gylfason .

The two fundamental routing algorithms in packet-switched networks are distance-vector and link-state. Your assignment is to implement link-state router in the REAL simulator (This is described in Section 11.6 in the textbook).

Before you start By now you should feel comfortable using the REAL simulator. If that is not the case, you should read the manuals for REAL. The are accessible online: http://www.cs.cornell.edu/home/skeshav/real/man.html . You will not be able to do this assignment without understanding REAL in some detail .  If you have specific questions about REAL, mail [email protected]. Please also check the REAL FAQ .

Topology of the network

Each node in the network represents a router. It contains a next-hop table for each node in the network. Each entry in the next-hop table tells us which physical link to choose so the packet will reach its destination at minimum cost. For example, if we wanted to send packet from node 3 to 12, we would look up in the next-hop table in node 3 and see that it is best to send the packet to node 4. When the packet reaches node 4, that node does the same (using its own next-hop table) and will find out that it is best to send the packet to node 11, etc.

Failure/Recovery of a link

In this assignment we will simulate one type of failure, link failure (but not a failure of a router). A router must be able to discover a failure and recovery of a link to its neighbor. For example, if the link between node 3 and 4 fails, both nodes 3 and 4 must have some mechanism to discover the link failure. They must as well discover when the link is up again. The mechanism you should use in this assignment is a simple HELLO protocol. Each router sends each of its neighbors a HELLO packet every 10.0 time units (even if it thinks a link to that router is down). When a router gets a HELLO packet it sends a HELLO_ACK packet back. When the sender of a HELLO packet receives a HELLO_ACK packet it knows that the link is alive. But if it doesn't receive an ack it doesn't necessarily mean that the link is down, maybe the ack packet was simply lost or corrupted. Therefore a link isn't considered down except if for a series of HELLO packets we didn't receive an ACK (here you should use 5 missing acks as a failed link). Example: Node 3 has two neighbors, 1 and 4. Note that 3 of course also receives HELLO packets from 1 and 4). Note also that (a) you need not print the following out when submitting the assignment: this is only an example to show you how HELLO works (b) the times here are indicative of the progress of time: they are not the times you will actually see in the simulation.

Time 10.0: 3 sends HELLO to 1 and 4 Time 10.1: 3 receives a HELLO_ACK from 1  (therefore link 3-1 is up)

Time 20.0: 3 sends HELLO to 1 and 4 Time 20.1: 3 receives a HELLO_ACK from 1  (therefore link 3-1 is up) ... Time 50.0: 3 sends HELLO to 1 and 4 Time 50.1: 3 receives a HELLO_ACK from 1  (therefore link 3-1 is up)

Time 60.0: 3 noticed that it has sent 5 HELLO packets to 4 without getting any ACKs so the 3-4 link is considered down. Time 60.0: 3 sends HELLO to 1 and 4   (note: 3 still tries to send HELLO packets to node 4) Time 60.1: 3 receives a HELLO_ACK from 1  (therefore link 3-1 is up) ... Time 230.0: 3 sends HELLO to 1 and 4 (assume the 3-4 link is still considered down) Time 230.1: 3 receives a HELLO_ACK from 1  (therefore link 3-1 is up) Time 230.2: 3 receives a HELLO_ACK from 4 (so link 3-4 is also up again)

Link-State Packets (LSP)

Whenever a router detects that a link is down it sends an LSP with an infinite cost for the link to all other routers. Similarly when a router detects that a link has recovered, it sends an LSP with the link's cost to all other routers. The LSP packets are not sent directly to all other routers but by using controlled flooding (as described on page 305 in the textbook). An LSP packet contains the router's ID, the neighbor's ID (the node on the other end of the link), and the cost of the link.  When a router gets an LSP packet it stores it in its LSP database. Then it recalculates its next-hop table using the Dijkstra algorithm (Section 11.6.2 in the textbook).

How to do the assignment

Read the textbook

Read Chapter 11 in the textbook. Read Section 11.6 very carefully and make sure you understand it.

In this assignment you use the REAL simulator as before. Your code should be in a file called "sim/sources/link_state_router.c". This files contains the control function for the router. The name of that function should be "link_state_router()" (similar to "ecn_dummy.c" and "ecn_dummy()").

Put the file " link_state_master.c " into the "sim/sources" directory (see below), and the file " link_state.l " into the "sim/ecn" directory.

Change the following lines in the two makefiles:

"sim/sources/makefile":

• functions = link_state_master.c link_state_router.c functionobj = link_state_master.o link_state_router.o

"sim/makefile":

• sourceobj = sources/link_state_master.o sources/link_state_router.o

Note: you may have to do "make depend" to create necessary dependencies for the new files.

Link-state master node

The "link_state_master.c" file contains a code for a control node which at certain time changes the status (up/down) of links in the network. The master notifies you on its actions by printing information on the screen. The "link_state_master.c" contains a table of link state change events. Now it contains only a few events, but while testing it you should add more events. You do that by simply adding lines to the "link_changes" array near the top of the "link_state_master.c" file. The format is described in there. (Note: You may also need to change the "end_simulation" parameter in the "link_state.l" file, if you want your simulation to run for longer time).

HELLO protocol

First implement the HELLO protocol. When a node x notices that a link to node y is down, print out "<time>: Link <x> - <y> is down". Use a similar printf when a node x discovers that a link is up again. Test it and make sure it works. Both HELLO and HELLO_ACK packets should be a DATA packets. Use the first byte of pkt->data to identify the type (HELLO or HELLO_ACK).

This is a function which you can use to discover the neighbors of node 'node'. The second parameter is an array of int (it should be at least at size 12). The function puts the neighbors into the array and returns the number of neighbors. Example: For node 7 (which has 3 neighbors: 5, 8, 9), the function should return 3 and the first 3 elements of the array you past into the function should contain 5, 8 and 9.

• int find_neighbors( int node, int neighbors[] ) {   gredgeptr       edge;   int neighbors_cnt;   neighbors_cnt = 0;   edge = Graph->edges;   while ( edge != 0 ) {     if ( edge->node1->nodedata->nodeid == node ) {       neighbors[neighbors_cnt++] = edge->node2->nodedata->nodeid;     }     if ( edge->node2->nodedata->nodeid == node ) {       neighbors[neighbors_cnt++] = edge->node1->nodedata->nodeid;     }     edge = edge->next;   }   return neighbors_cnt; }

Timer It is easy to set up timers in REAL. Simply create a packet of type TIMER and call set_timer() to activate it. You can actually choose any type you want, as long as the type is defined in file kernel/config.h.

• make_pkt(pkt); pkt->type = TIMER; set_timer( 10.0, pkt );  /* The first argument is the time until the timer event                           * (in seconds). This should be a float. */

After 10.0 time units the node receives a TIMER event.

Link-State Packets

Next you should implement the LSP part. An LSP should be a DATA packet (like HELLO and HELLO_ACK). You should use the first byte of pkt->data to distinguish it from the HELLO packets. On link state change (and *only* on a link state change), create and send LSP packets to each of your neighbors. Implement a subset of  the controlled flooding protocol described in the textbook. Specfically: (a) no need to ack LSPs (b) don't age LSPs (c) no need for a lollipop sequence space (d) no need to worry about network partitioning. You do not need these refinements because, in this assignment, routers never go down. You can use any data structure you want to store the LSPs, but it is most convenient to store the information in two parts: (a) an array that tells the latest sequence number received from each router (this tells you whether or not to forward the LSP when flooding), and (b) a Graph structure (defined in src/graph.h) that stores your notion of the topology (be sure that you make a local copy of this structure, instead of overwriting the global!). Storing the topology in the graph structure will allow you to use Dijkstra's routing algorithm already provided in file sim/kernel/routing.c.

Next-hop table

When a router receives a LSP packet changing the current state, it must recalculate its next-hop table. To do that you should implement the Dijkstra algorithm (Section 11.6.2 in the textbook) or modify source for the algorithm from the Net.  If you want to implement your own version of the algorithm, be careful to test it on a simple example. Even though the algorithm looks simple it is quite easy to make mistakes while coding it, and a tiny bug may cause the rest of the assignment to fail. It is essential to get it right. Make sure you understand it completely before you start coding it (I suggest you go through the algorithm by hand at least once). Implement it separately (not in the simulator) to begin with, test it carefully and make sure it works as it should. Then, plug it into the simulator.

Note: the description in the book is slightly imprecise. When it says 'pick' a node in step 2, that means remove it from set T. So, even if it is not added to P, it will still be removed from T. You will understand this better if you step through the example in Figure 11.11.

The next-hop table should be a global array (i.e. outside the "link_state_router()" function) defined as:

• int g_next_hop_table[12][12];

g_next_hop_table[2][5] should contain the next hop information going from node 2 to 5. Since each router is an individual host, each router must only read/write its own row of the table.

When a router has recalculated its row of the g_next_hop_table it must do two things. First it should print out the next hop values in a single line of the following format:

• <time>: Next hop for <node> = 1:<hop to 1>, 2:<hop to 2>, ... , 12:<hop to 12>
• 1321: Next hop for 3 = 1:1, 2:1, 3:3, 4:4, 5:1, 6:1, ... , 12:4

And secondly it must call a function named "sanity_check" defined as:

• void sanity_check( int **table )

The sanity_check function checks whether the routing table is consistent. Essentially, it tests that (a) the next hop is actually a neighbor, and (b) for randomly selected source and destination, following the routing tables will let you reach the destination from the source. For instance, we may pick source 3 and destination 9. We will use g_next_hop_table [3][9] to find the next hop towards  9. We will then follow the hops indicated by your table and make sure we reach 9. You may want to write your own sanity check algorithm. We will plug in our own sanity check to test your implementation. Note that on a link failure, the routing table is INCONSISTENT. So, sanity check should and will fail until consistency is regained. Do not worry if sanity check fails!

Note that even though the description of the assignment is quite long the assignment itself is fairly simple.

What to submit (IMPORTANT) You should send in only one file "link_state_router.c" by email (to [email protected]).

• Your submission should print out the following events: link up, link down, and routing table computed on receiving an LSP. For the format of these printfs, please look at the detailed description of these events.
• Don't uuencode it and don't tar it.
• In the previous assignments some students have sent me the binaries, don't do that.
• The body of the email should only contain the c file (no comments from you).
• Don't use C++ comments (use /* ... */ but not // ...).

Grading Your implementation will be tested on a different network topology. It will be of the same, or smaller, size (so your next-hop table can be of size 12), with the same assumptions as above - like links of equal cost 1000, and no router failures. We will test the sanity of the routing tables at the end of the simulation. The assignment will be binary graded, 0 or 1.  

Assignment 3: Routing Algorithm

Due: friday, march 27, 2020, 10:00 pm. in groups of up to 2 students.

In this assignment, you will implement a distributed, asynchronous, distance-vector routing algorithm based on the Bellman-Ford algorithm that we learned in the lecture.

The network is modelled as an undirected graph with a certain number of nodes. Each link in the graph is associated with a positive integer cost. Below is a simple example of a graph with 3 nodes and 3 links. The nodes in the graph would, in a distributed and asynchronous manner, send each other messages containing information about their distance vectors, and, when receiving a message from another node, update their distance vectors accordingly. The expected outcome of the routing algorithm is that each node keeps a distance vector that stores its shortest-path distances (lowest costs) to other nodes in the graph, and knows how to find the shortest path to every other node.

Understanding the Starter Code

Download the starter code which includes two files: dvsim.py and dvnode.py . Below is an overview of these two files.

dvsim.py is the main simulator code which implements a simulated environment of the distributed, asynchronous route computing process. It initializes the topology (the nodes and the links with costs) of the input graph and provided class definitions such as Packet , Event and EventList . The implementation in this file is given to you and you won't need to change it much (and you won't submit it to MarkUs); however, you need read it carefully and understand thoroughly what it does and how it is related to the Node class defined in dvnode.py . You only need to modify this file when you try to create different test cases for your algorithm. Below are the things that you may need to modify.

• NUM_NODES : this is the number of nodes in the graph. You may change it according to the size of the graph that you want to test on.
• The generate_topology() method in Simulator : this is the method that manually assigns the costs of the links in the graph. You may change it whichever graph topology that you'd like to test. Make sure the size of the graph is consistent with what indicated by NUM_NODES .
• The generate_random_topology() generates graph randomly given NUM_NODES . You use this to generate test cases automatically instead of manually.
• The if link_changes block the __init__ method of Simulator adds link-change events to the simulation. You may modify here to add more link-change events.
• The generate_link_change() method specifies what exactly happens in the link-change event: which link's cost changes and what's the new cost of the link. You may modify this method in order to create the test case you need.
• Other than the above places, you should avoid modifying any other parts of dvsim.py . Since you will NOT submit your own dvsim.py , you need to make sure your submitted code works correct with the original dvsim.py .

dvnode.py is the file that you will work on completing. This file defines the Node class for each node in the network. You will implement the following methods:

• __init__() : the constructor of the Node class. You will initialized the dist_table which keeps the distance vectors as well as the predecessors list that will store the predecessors of the node in its shortest paths to every other nodes. The node may also want to start sending some packets to their neighbours.
• update() : this method is called when the node receives a packet from another node. You'll need to update the distance table and the predecessor list accordingly, and notify the node's neighbours about the update when necessary.
• link_cost_change_handler() : this method is invoked when a link-change event occurs. The cost of a link would change and the node need to update its distance table and predecessor list accordingly, and notify the node's neighbours when necessary.
• You are allowed to add additional helper methods to the Node class.

Testing and Report

The command to run the simulator is the following:

python3 dvsim.py HasLinkChange Seed

where HasLinkChange (1 or 0) specifies whether or not to add link-change events to the simulation, and Seed (an integer) is the seed of the pseudo-random number generator.

You should create various test cases to verify that your implementation is correct, and to observe the behaviour of the algorithm in different scenarios. In particular, you're required to write up a report.pdf as part of your assignment submission. The report should include the following parts:

• Your name and student number, and a quick summary of what's completed and not completed in your submission.
• With HasLinkChange set to 0 (i.e., no link-change events), use a test case on a graph with 5 nodes to convince the reader that your algorithm is working correctly. Add printouts for the intermediate steps to show that the algorithm is behaving as expected.
• With HasLinkChange set to 1 , use a test case on a graph with 4 nodes to demonstrate the " good news travels fast " behaviour of the routing algorithm.
• With HasLinkChange set to 1 , use a test case on a graph with 4 nodes to demonstrate the " bad news travels slowly " behaviour of the routing algorithm.
• Study/analyze/discuss, on a reasonably detailed level, the complexity of the routing algorithm in terms of the number of messages needed to be sent in the network. Note that the requirement on this part is intentionally vague and open-ended so that you need to think about what approach is the best for studying this issue.
• Page limit: The total length of your report should NOT exceed 8 pages .

Requirements

Below are some specific requirements just so that you know what to do and that your code can be properly marked by the TA.

• Read the starter code thoroughly . The comments in the starter code contain detailed information regarding how the simulator works and how your code should be written. Please make sure to read it thoroughly and understand how exactly it works.
• Use Python 3 and make sure your code works correct on the lab computers.
• Make sure your dvnode.py works correctly with the original dvsim.py since your will NOT submit your own dvsim.py
• Follow the instructions in the comments in the starter code. Do NOT modify the parts that are marked as "DO NOT MODIFY".
• Your node should only send messages when it is necessary, i.e., the number of messages sent must be the minimum possible.
• Keep in mind that you're implementing a distributed algorithm, i.e., every node is only supposed to operate on the information stored locally and each node can only communicate with its immediate neighbours. Any violation of this principle, e.g., accessing information or invoking a method at other nodes, would result in significant deduction in marks.
• You may assume that every node has the knowledge that the distance value from a node to itself is always 0, regardless of whether the node is a neighbour or not.

Submissions

You will submit the following two files using the web submission interface of MarkUs.

• report.pdf with the content specified in the above "Testing and Report" section. Presentation matters : your report must be presented in a clean and concise manner that is easy-to-understand for others.

You can submit the same filename multiple times and only the latest version will be marked, so it is a good practice to submit your first version well before the deadline and then submit a newer version to overwrite when you make some more progress. Again, make sure your code runs as expected on a lab computer.

Late homework submissions are penalized by 1% for every hour of lateness, rounded up, to a maximum of 24 hours. Submissions will no longer be accepted 24-hours past the deadline, except for documented unusual circumstances.

Below is the tentative overall marking scheme of this assignment:

• Correctness without link-change events: 30%
• Correctness with link-change events: 30%
• Report: 30%
• Coding style and documentation: 10%

Coding style matters. Your code must be written in a proper style and must be well commented so that anyone else can read your code and easily understand how everything works in your code.

Academic Integrity

Please be reminded that ALL assignment submissions will be checked for plagiarism at the end of the term. Make sure to maintain your academic integrity carefully, and protect your own work. It is much better to take the hit on a lower assignment mark (just submit something functional, even if incomplete), than risking much worse consequences by committing an academic offence.

A summary of the routing algorithm and their optimization,performance

This essay provides a comprehensive analysis of the optimization and performance evaluation of various routing algorithms within the context of computer networks. Routing algorithms are critical for determining the most efficient path for data transmission between nodes in a network. The efficiency, reliability, and scalability of a network heavily rely on the choice and optimization of its routing algorithm. This paper begins with an overview of fundamental routing strategies, including shortest path, flooding, distance vector, and link state algorithms, and extends to more sophisticated techniques.

Index Terms:

I introduction.

This paper presents a comprehensive summary of routing algorithms, including their optimization and performance metrics. With the expansion of network scale, traditional point-to-point (P2P) communication has become impractical. This limitation is not confined to computer networks, which are widely recognized, but extends to Network on Chip (NoC), optical networks, social networks, and other relevant domains. To improve network performance metrics such as communication bandwidth, latency, delay, and packet loss ratio, it is imperative to analyze the network structure, topology, and routing algorithms.

This study consists of some typical routing algorithm. Most of them are the examples in the course we have learnt before. All of these routing algorithm are not perfect. They have their own advantages and drawbacks, which decide the specific application scenarios. despite their simple prinple, they have formed the base of the modern routing algorithm.

This study also encompasses an exploration of several advanced routing algorithms. While most of these algorithms are currently in the research phase and have not been deployed in production environments, they offer valuable insights into the evolving trajectory of routing algorithm development. This investigation aims to contribute significantly to the field by forecasting future trends and fostering advancements across the industry.

II Some typical routing algorithm and their pros & cons

Ii-a shortest path algorithm.

The Shortest Path Algorithm is a fundamental concept in the field of computer science and networking, aimed at finding the shortest path between two points in a graph. This graph can represent various physical, social, or abstract networks, where nodes represent entities and edges represent the connection or distance between these entities. The shortest path is the one that minimizes the sum of the weights of the edges traversed between the source and destination nodes. There are several algorithms designed to solve the shortest path problem, with Dijkstra’s algorithm and the Bellman-Ford algorithm being among the most prominent.

Dijkstra’s Algorithm

Proposed by Edsger W. Dijkstra in 1956, this algorithm solves the shortest path problem for a graph with non-negative edge weights, producing a shortest path tree. This tree contains the shortest path from the source node to all other nodes in the graph.

How it Works: Dijkstra’s algorithm maintains a set of nodes whose shortest distance from the source is already known and a set of nodes whose shortest distance is not yet determined. Initially, the distance to the source is zero and infinity for all other nodes. The algorithm repeatedly selects the node with the smallest known distance from the source, updates the distances to its neighbors, and repeats the process until all nodes have been processed. Pros:

It guarantees to find the shortest path in graphs with non-negative edge weights.

It is relatively straightforward to implement.

It cannot handle graphs with negative edge weights.

Its computational complexity can be high for dense graphs without optimizations like priority queues.

Bellman-Ford Algorithm

The Bellman-Ford algorithm extends the capability to handle graphs with negative edge weights, allowing it to detect negative weight cycles in the graph.

How it Works: It relaxes the edges of the graph repeatedly, updating the cost to reach each node from the source if a cheaper path is found. This process is repeated for each edge, and the algorithm checks for negative cycles, which occur if a cost can be further reduced after sufficient iterations. Pros:

Capable of handling graphs with negative edge weights.

Can identify negative cycles in the graph.

It is slower than Dijkstra’s algorithm due to higher time complexity.

Shortest Path Algorithms are widely applicable in:

Network Routing: Optimizing data packet paths in computer networks.

Geographic Mapping: Determining shortest routes in mapping and navigation systems.

Resource Allocation: Efficient route planning in logistics and supply chain management.

Social Networking: Analyzing connections in social networks.

II-B Randomly Pick Direction

The Randomly Pick Direction (RPD) routing algorithm represents an unconventional approach in the landscape of routing strategies, particularly within the realms of ad hoc networks, mesh networks, and certain types of distributed systems. Unlike deterministic or optimized routing algorithms that seek the most efficient path based on specific metrics (like shortest path, least congestion, or highest throughput), RPD bases its routing decisions on randomness. Here, we delve into the mechanics, advantages, and potential drawbacks of the RPD routing algorithm.

The core principle of the RPD routing algorithm is its reliance on random selection to determine the next hop for a packet. When a packet arrives at a node, instead of calculating the best path to the destination, the node randomly selects one of its available neighbors as the next hop. This process repeats at each intermediate node until the packet reaches its intended destination or a predefined maximum number of hops is exceeded. Pros:

Simplicity: The algorithm is straightforward to implement as it does not require complex calculations or maintenance of detailed routing tables. This simplicity is particularly beneficial in rapidly changing or unpredictable network environments.

Load Balancing: By randomly distributing the packets across various paths, RPD can naturally balance the load among different nodes and links, potentially reducing congestion on popular routes.

Robustness: The randomness inherent in RPD provides a degree of resilience against certain types of network failures or attacks, as there is no fixed path for malicious entities to target or for failures to disrupt.

Inefficiency: Random path selection is inherently less efficient than algorithms that optimize for specific metrics. This can lead to longer paths, increased latency, and higher packet loss rates, especially in dense or complex networks.

Unpredictability: The performance of RPD can be highly variable and unpredictable, making it difficult to guarantee service quality or meet specific performance criteria.

Wastefulness: The algorithm may generate excessive network traffic due to the non-optimal paths taken by packets, leading to wasted bandwidth and energy, particularly in wireless networks.

Applications

Dynamic and Ad Hoc Networks: In environments where network topology changes frequently, the simplicity and adaptability of RPD make it a suitable choice.

Load Testing and Simulation: RPD can be used to simulate worst-case scenarios or to test the robustness of networks against random traffic patterns.

Initial Route Discovery: In some hybrid routing schemes, RPD can serve as an initial route discovery mechanism before more optimized paths are established.

The Randomly Pick Direction routing algorithm, with its unique approach of utilizing randomness in routing decisions, offers a trade-off between simplicity and performance. While not suited for all applications, particularly those requiring high efficiency and predictability, RPD finds its niche in scenarios where network flexibility, robustness, and simplicity are prioritized over optimal performance. Its role in the broader ecosystem of routing algorithms highlights the diversity of strategies available for managing data flow across complex networks.

II-C Dimention-Ordered Routing

Dimension-Ordered Routing (DOR) is a deterministic routing strategy commonly employed in mesh and hypercube network topologies, particularly within the context of parallel computing and network-on-chip (NoC) architectures. This algorithm is characterized by its methodical approach to routing, where packets are forwarded through network dimensions in a specific order until they reach their destination. The most common forms of Dimension-Ordered Routing include XY routing (for 2D meshes) and XYZ routing (for 3D meshes), though the concept extends to higher dimensions in more complex topologies.

Principle: In DOR, each node in the network is assigned a unique coordinate based on its position within the network’s dimensional grid. Routing decisions are made based on the coordinate difference between the source and destination nodes, with packets being forwarded along one dimension at a time until the coordinate in that dimension matches the destination’s.

XY Routing (2D Mesh): Packets first move along the X dimension until they align with the destination’s X coordinate, and then proceed along the Y dimension.

XYZ Routing (3D Mesh): Similar to XY routing, but packets also move along the Z dimension if necessary, following the X and Y movements.

Simplicity: The algorithm is straightforward, making it easy to implement and understand. It requires minimal computational overhead, contributing to lower latency in routing decisions.

Determinism: Since the path is determined solely by the source and destination coordinates, the routing behavior is predictable, which simplifies deadlock and congestion management.

Scalability: DOR scales well with network size, as the routing logic does not fundamentally change with the addition of more nodes or dimensions.

Path Rigidity: The deterministic nature of DOR means that the paths are fixed, which can lead to congestion if certain routes become heavily trafficked.

Suboptimal for Non-Uniform Traffic: In cases where network traffic is not uniformly distributed, DOR may not utilize all available paths efficiently, leading to underutilization of network resources.

Vulnerability to Failures: The fixed routing paths mean that any failure in the network can significantly impact communication, requiring additional mechanisms for fault tolerance.

Application:

Parallel Computing Systems: Where predictable and efficient communication patterns are essential for performance.

Network-on-Chip (NoC) Architectures: In multicore processors, where a predictable and low-latency communication scheme is crucial for inter-core communication.

Embedded Systems and IoT Devices: Where computational simplicity and predictability are more critical than adapting to varying traffic patterns.

II-D Oblivious Routing

Oblivious Routing is a network routing strategy characterized by its use of predetermined paths for packet transmission, regardless of the current state or traffic conditions within the network. This approach contrasts with adaptive routing strategies that dynamically change paths based on network congestion or failures. Oblivious routing algorithms determine the path between a source and a destination solely based on the identities of these endpoints and do not alter the routing decisions in response to network traffic changes.

Oblivious routing involves directing traffic from its origin to its destination along preset paths, with the routing decisions made without regard to the current traffic levels. Although determining the best oblivious routing strategy is generally unfeasible for all network layouts, our findings demonstrate that it is feasible for the structured layouts commonly found in data center networks. [ 3 ] Principles of Oblivious Routing:

Path Determination: Routes between any pair of nodes are predefined and do not change in response to network conditions. These paths can be computed offline, based on the network topology and possibly aiming to optimize certain performance metrics averaged over a range of traffic patterns.

Load Distribution: A key goal of oblivious routing is to distribute traffic evenly across the network to prevent congestion on any single path. This is often achieved through the use of randomized or round-robin selection among multiple precomputed paths for each source-destination pair.

Simplicity: The oblivious nature of the routing simplifies the implementation, as the path computation is done offline and does not require complex, real-time decision-making algorithms.

Predictability: Since the routes do not change in response to traffic, network behavior under given traffic patterns is predictable, facilitating easier network analysis and planning.

Scalability: Oblivious routing can scale well with network size because it avoids the overhead of dynamic route computation and state information exchange.

Inefficiency under Specific Conditions: Oblivious routing may not handle sudden, localized spikes in traffic optimally, as it cannot reroute traffic to less congested paths in real-time.

Suboptimal for Varying Traffic Patterns: Since paths do not adapt to changing network conditions, oblivious routing may not be as efficient as adaptive routing in environments where traffic patterns vary widely and unpredictably.

Potential for Congestion: If the predetermined paths are not well-chosen, or if traffic patterns change significantly from those anticipated during path computation, parts of the network may become congested.

Data Center Networks: In environments with well-understood and relatively stable traffic patterns, oblivious routing can provide a good balance between simplicity and performance.

Parallel Computing: Oblivious routing can be effective in parallel computing environments where communication patterns are predictable and can be optimized offline.

Networks with Predictable Traffic: Any network scenario where traffic patterns are known in advance and do not exhibit significant fluctuations may benefit from the predictability and simplicity of oblivious routing.

Oblivious routing offers a trade-off between the simplicity and predictability of fixed routing paths and the potential inefficiency in the face of dynamic, unpredictable traffic patterns. Its suitability varies depending on the specific requirements and characteristics of the network, including traffic stability, the need for real-time adaptability, and the complexity of managing dynamic routing protocols. In contexts where traffic patterns are well-understood and relatively stable, oblivious routing can significantly simplify network design and operation while providing adequate performance.

II-E Flooding

Flooding is a fundamental routing technique used in computer networks to disseminate information from one node to all other nodes in the network without the need for a predefined route. This brute-force method ensures that a packet sent from a source node is delivered to all possible destinations by transmitting it to every neighbor except the one it was received from. Flooding is simple and does not require complex route discovery or maintenance protocols, making it useful in certain network scenarios. How Flooding Works:

Packet Transmission: When a node receives a packet intended for flooding, it duplicates the packet and sends it to all its directly connected neighbors, except the node from which it received the packet.

Termination Condition: To prevent packets from circulating indefinitely, flooding typically employs one of two mechanisms: a) A hop count limit (TTL - Time To Live), which decrements at each node. The packet is discarded when the TTL reaches zero. b) Sequence numbers to identify and discard duplicates, preventing a node from forwarding the same packet more than once.

Simplicity: Flooding does not require sophisticated routing algorithms or knowledge of the network topology, making it easy to implement.

Robustness: It ensures message delivery as long as there is at least one path between the source and destination, making it highly reliable in highly dynamic or disrupted network environments.

Low Latency: Since packets take all possible paths to the destination, they are likely to find the shortest path, potentially reducing latency for critical applications.

High Network Traffic: Flooding generates a large amount of redundant network traffic, which can lead to congestion and deplete network resources.

Inefficiency: Sending the same packet through multiple paths without considering the network’s state can be highly inefficient, especially in large or dense networks.

Security Concerns: The indiscriminate broadcasting nature of flooding can pose security risks, making it easier for malicious entities to intercept or inject packets.

Route Discovery: In some network protocols, such as Dynamic Source Routing (DSR) in ad hoc networks, flooding is used for route discovery phases before switching to more efficient routing for data transmission.

Broadcasting: Flooding is an effective method for distributing information to all nodes in the network, useful in applications requiring broad dissemination, such as updates or emergency alerts.

Distributed Systems: In certain distributed algorithms, flooding is used to ensure that all nodes receive critical control messages or synchronization signals.

Flooding, with its simplicity and robustness, is an essential routing technique in specific network scenarios where reliability and broad reach are more critical than efficiency and resource consumption. Despite its drawbacks, such as high network traffic and potential security vulnerabilities, it remains a valuable tool in the networking toolkit, especially for applications requiring universal message dissemination or in networks where the topology changes frequently.

II-F Distance Vector Routing

Distance Vector Routing is a classical routing algorithm used in packet-switched networks, where routers determine the best path to each destination based on the distance to those destinations. The ”distance” is typically measured in terms of hops, but it can also account for other metrics like latency, bandwidth, or cost. This algorithm is based on the principle of dynamic programming and is known for its simplicity and ease of implementation.

How Distance Vector Routing Works:

Distance Vectors: Each router maintains a table (distance vector) that contains the best known distance to every destination in the network and the next hop router on the best path to that destination.

Periodic Updates: Routers periodically exchange their distance vectors with their immediate neighbors. Each router updates its own distance vector based on the information received, calculating potential new paths that might be better than the current ones. The update is based on the Bellman-Ford algorithm, which helps in finding the shortest path.

Metric Calculation: The cost to reach a destination is calculated using the metric of distance. When a router receives a distance vector from a neighbor, it adds the cost to reach that neighbor to the costs in the distance vector. If this sum for a destination is lower than the known cost, the router updates its distance vector with this new lower cost and the corresponding next hop.

Simplicity: Distance Vector Routing is straightforward to implement and understand, making it suitable for smaller or less complex networks.

Decentralization: The algorithm operates in a completely decentralized manner, where each router makes independent decisions based on the information from its neighbors.

Autonomy: It allows routers to dynamically adapt to changes in the network topology, such as link failures or the addition of new routers, without requiring a central authority.

Slow Convergence: Distance Vector Routing can be slow to converge to a stable set of routing tables after a change in network topology. This can lead to temporary routing loops and count-to-infinity problems.

Scalability Issues: The periodic updates and the need to broadcast the entire routing table to neighbors can lead to scalability issues in larger networks, as it consumes bandwidth and processing power.

Security Vulnerabilities: Without proper security measures, malicious routers can introduce incorrect routing information into the network, leading to routing loops or black holes.

Small to Medium-Sized Networks: Due to its simplicity and ease of configuration, Distance Vector Routing is well-suited for small to medium-sized networks.

RIP Protocol: The Routing Information Protocol (RIP) is one of the most well-known implementations of Distance Vector Routing, used in many small to medium-sized networks.

Distance Vector Routing provides a simple and effective method for routing in packet-switched networks, with the benefit of decentralized decision-making and adaptability to network changes. However, its limitations in terms of convergence speed, scalability, and security need to be considered when choosing it for larger or more dynamic network environments. Despite these challenges, Distance Vector Routing remains foundational to understanding routing protocols and is an integral part of network design and operation in specific contexts.

II-G Link State Routing

Link State Routing is an advanced network routing protocol that overcomes some of the limitations inherent in distance vector routing protocols. It operates by having each router learn the entire network topology, allowing for a more comprehensive and dynamic understanding of the network. Each router independently calculates the shortest path to every possible destination using its knowledge of the network topology. The algorithm most commonly associated with link state routing is Dijkstra’s shortest path algorithm. How Link State Routing Works:

Topology Discovery: Each router in the network discovers its immediate neighbors and learns the cost (e.g., bandwidth, delay, or other metrics) to reach them, typically through the exchange of hello packets.

Link State Advertisement (LSA): Every router creates a packet of information called a Link State Advertisement that contains its connectivity and the cost to each of its neighbors. These LSAs are then flooded to all routers in the network, ensuring that every router receives an identical copy of the topology information.

Topology Database: Each router uses the LSAs to build a complete map of the network’s topology, stored in a database. This database is identical on all routers, providing a comprehensive view of the network.

Route Calculation: With the complete network topology at its disposal, each router independently calculates the shortest path to every destination using Dijkstra’s algorithm. The outcome of this calculation is a shortest-path tree with the router itself as the root.

Rapid Convergence: Link state routing protocols converge more quickly than distance vector protocols because they have a complete view of the network. Changes are propagated rapidly, and each router independently recalculates routes, minimizing the time to convergence.

Scalability: The use of LSAs and the flooding mechanism allows link state protocols to scale effectively to larger networks compared to distance vector protocols.

Avoidance of Routing Loops: The global knowledge of the network prevents the formation of routing loops, a common problem in distance vector routing protocols.

Accurate and Efficient Routing: Having a complete view of the network allows routers to make informed decisions about the shortest paths, leading to more efficient use of network resources.

Resource Intensity: Maintaining a complete topology map and running Dijkstra’s algorithm requires more memory and processing power than distance vector routing protocols.

Initial Traffic Overhead: The initial flooding of LSAs to establish the topology database can create significant traffic, although this is mitigated in steady-state operations.

Complexity: The mechanisms of LSA flooding, maintaining the topology database, and calculating routes add complexity to the router’s operation and configuration.

OSPF (Open Shortest Path First): One of the most widely used link state routing protocols in IP networks. OSPF is designed for scalability and efficiency in diverse network topologies.

IS-IS (Intermediate System to Intermediate System): Another link state protocol used in large enterprise and service provider networks. It functions similarly to OSPF but can operate in both IP and OSI environments.

Link State Routing provides a robust framework for routing in complex and diverse network environments, offering advantages in terms of convergence speed, scalability, and routing efficiency. Despite its resource requirements and operational complexity, the benefits of link state routing make it a preferred choice for large, dynamic networks seeking reliable and efficient routing solutions.

II-H Multipath Routing

Multipath Routing is a network routing technique that finds multiple feasible paths between a source and a destination in a network. Unlike traditional routing methods that use a single best path for packet delivery, multipath routing leverages the redundancy of network paths to improve reliability, bandwidth, and load balancing. This approach can significantly enhance the overall performance and fault tolerance of network communications.

How Multipath Routing Works:

Path Discovery: Multipath routing protocols begin by discovering multiple paths between the source and destination. This can be achieved through various mechanisms, including extending traditional routing protocols or using specialized multipath discovery processes.

Path Selection: Among the discovered paths, the protocol selects a subset for use in routing. Selection criteria may include path length, bandwidth, latency, or other quality-of-service (QoS) metrics. The objective is to optimize the network’s performance while avoiding congestion and ensuring reliability.

Traffic Distribution: Traffic is distributed across the selected paths based on predefined rules or dynamically in response to network conditions. Distribution strategies can range from simple round-robin to more complex algorithms that consider path characteristics and network load.

Path Maintenance: Multipath routing protocols monitor the status of active paths and can dynamically adjust the set of paths in use. If a path becomes unavailable or suboptimal due to network changes, the protocol can reroute traffic to maintain performance and reliability.

Increased Bandwidth: By utilizing multiple paths simultaneously, multipath routing can aggregate bandwidth, offering higher data throughput.

Improved Reliability and Fault Tolerance: The availability of alternative paths enhances network reliability, as failures in one path can be mitigated by rerouting traffic through others.

Enhanced Load Balancing: Distributing traffic across multiple paths helps in balancing load more evenly across the network, preventing congestion on any single path.

Reduced Latency: In some cases, multipath routing can reduce latency by selecting the fastest path available for critical traffic.

Complexity: Implementing and managing multipath routing adds complexity to network design and operation, requiring sophisticated algorithms for path discovery, selection, and maintenance.

Overhead: The process of maintaining multiple paths and distributing traffic can introduce additional control traffic and processing overhead.

Interference and Out-of-Order Delivery: When packets for the same transmission are sent over paths with varying latencies, it can lead to packet reordering, requiring additional mechanisms to reorder packets at the destination.

Data Center Networks: Multipath routing is extensively used in data centers to optimize the use of available bandwidth and enhance fault tolerance.

Internet Traffic: Protocols like Multiprotocol Label Switching (MPLS) can implement multipath routing to improve the efficiency and reliability of internet traffic routing.

Wireless Networks: In wireless mesh networks and mobile ad hoc networks (MANETs), multipath routing can improve resilience and performance in the face of dynamic network conditions.

Multipath Routing offers a powerful approach to enhancing network performance, reliability, and efficiency. By intelligently leveraging multiple paths through the network, it provides significant benefits over traditional single-path routing techniques. However, the increased complexity and overhead associated with managing multiple paths are important considerations when implementing multipath routing in a network.

II-I Energy-Efficient Routing

Energy-Efficient Routing is a critical concept in the design and operation of wireless sensor networks (WSNs), ad hoc networks, and other types of networks where energy conservation is a priority. The primary goal of this routing strategy is to minimize energy consumption across the network to prolong the lifetime of battery-powered nodes, ensuring network sustainability and reliability over time. This is particularly important in environments where replacing or recharging batteries is impractical or impossible.

Principles of Energy-Efficient Routing:

Energy Awareness: Routing decisions are made based on the energy consumption of different paths and the residual energy of nodes, prioritizing routes that minimize overall energy usage and balance the energy expenditure among nodes to avoid early depletion of any single node.

Low Power Operations: The protocol may implement mechanisms to reduce power consumption, such as reducing transmission power, using energy-efficient data aggregation techniques, and putting nodes into sleep mode when they are inactive.

Multi-Hop Routing: Instead of direct communication between distant nodes and a base station, which can be energy-intensive, data packets are forwarded through multiple intermediate nodes using shorter, energy-efficient hops.

Strategies for Energy-Efficient Routing

Minimum Energy Routing: Selects the path that consumes the least amount of energy, regardless of the number of hops, to transfer data from the source to the destination.

Energy Balancing: Focuses on distributing the energy consumption evenly across the network to prevent the rapid depletion of individual nodes, which could create network gaps.

Data Aggregation: Involves combining data from multiple nodes to reduce the number of transmissions, thereby saving energy. This is particularly effective in networks where data from different sensors can be aggregated without loss of information.

Extended Network Lifetime: By minimizing energy consumption, energy-efficient routing protocols significantly extend the operational lifespan of battery-powered networks.

Increased Reliability: Evenly distributing energy usage helps prevent node failures, enhancing the overall reliability of the network. Cost Efficiency: Reducing the frequency of battery replacements lowers the maintenance cost of deploying wireless sensor networks in remote areas.

Complexity: Energy-efficient routing algorithms can be more complex to implement, requiring additional computations to assess energy metrics and make routing decisions.

Performance Trade-offs: Focusing on energy efficiency might result in increased latency or reduced data throughput due to the preference for multi-hop routing over more direct paths.

Dynamic Network Conditions: The effectiveness of energy-efficient routing can be influenced by changes in network topology, such as node mobility or failure, requiring adaptive algorithms to maintain efficiency.

Wireless Sensor Networks (WSNs): Used in environmental monitoring, military surveillance, and smart agriculture, where sensors are often deployed in inaccessible locations.

Internet of Things (IoT): In IoT applications, extending battery life is crucial for devices that are expected to operate for long periods without human intervention.

Ad Hoc Networks: In scenarios like disaster recovery or military operations, where network infrastructure might be unavailable or impractical, energy efficiency ensures longer operational periods.

Energy-Efficient Routing is essential for optimizing the longevity and reliability of networks where energy resources are limited. Through careful routing decisions and techniques aimed at minimizing and balancing energy consumption, these protocols help to ensure that networked systems, especially those deployed in challenging or remote environments, can continue to operate effectively over extended periods. Despite the challenges and trade-offs involved, the benefits of energy-efficient routing in terms of cost savings, network sustainability, and device longevity are significant, making it a key consideration in the design of modern wireless networks.

III Some modern Routing algorithm

Iii-a eesra [ 8 ], iii-a 1 introduction.

This paper introduces an energy-efficient clustering and hierarchical routing algorithm named EESRA, aimed at extending the lifespan of wireless sensor networks (WSNs) with increasing network size. This algorithm is an enhancement over the ”low-energy adaptive clustering hierarchy” (LEACH) protocol, addressing its scalability issues by adopting a three-layer hierarchy to minimize cluster heads’ load and randomize their selection. Moreover, EESRA employs multi-hop transmissions for intra-cluster communications to implement a hybrid WSN MAC protocol. The paper’s simulation results demonstrate that EESRA outperforms other WSN routing protocols in terms of load balancing and energy efficiency on large-scale WSNs.

The key contributions of the paper include:

An innovative energy-efficient clustering and hierarchical routing algorithm that outperforms existing WSN routing protocols in terms of scalability and energy efficiency.

The introduction of a hybrid WSN MAC protocol that incorporates both sleep and collision avoidance mechanisms alongside TDMA slots for efficient data forwarding.

A comprehensive simulation analysis demonstrating the algorithm’s effectiveness in extending the network lifespan and achieving better load balancing across large-scale WSNs.

III-A 2 Optimization

The EESRA (Energy Efficient Scalable Routing Algorithm) optimizes traditional energy-efficient routing in several key ways, focusing on addressing the scalability and energy consumption issues inherent in the LEACH protocol and other WSN (Wireless Sensor Network) routing protocols:

Three-layer Hierarchy: EESRA introduces a three-layer hierarchical structure to reduce the load on cluster heads (CHs) by incorporating an additional layer of cluster congregations (CGs) between the CHs and the cluster members (CMs). This structure helps in distributing the energy consumption more evenly across the network, thus optimizing energy usage and extending the network lifespan.

Hybrid MAC Protocol: The algorithm employs a hybrid Medium Access Control (MAC) protocol that combines sleep and collision avoidance mechanisms for efficient data sensing and transmission. This approach allows for more efficient use of energy, as nodes can enter a low-power state when not actively transmitting data.

Multi-hop Intra-cluster Communication: Unlike traditional protocols that may rely solely on single-hop communication, EESRA uses multi-hop transmissions within clusters. This method reduces the energy consumed in data transmission by minimizing the distance over which individual transmissions need to occur.

Randomized Cluster Head Selection: To further balance the energy consumption across the network, EESRA implements a randomized selection of cluster heads. This ensures that no single set of nodes bears the brunt of the energy consumption, leading to a more uniform depletion of resources across the network.

Load Balancing: By adopting a three-layer hierarchy and utilizing multi-hop communication, EESRA effectively balances the load among nodes. This prevents certain nodes from depleting their energy resources too quickly, thereby optimizing the overall energy usage within the network.

III-A 3 Performance Evaluation

The simulation results Fig. 7 presented in the paper demonstrate that EESRA outperforms traditional LEACH and its variants in terms of energy efficiency, load balancing, and scalability, especially in large-scale WSNs. By addressing the critical challenges of energy consumption and network scalability, EESRA optimizes traditional energy-efficient routing protocols, offering a significant improvement in extending the network lifespan while maintaining high network performance.

III-B GAPSO‐SVM [ 9 ]

Iii-b 1 introduction.

GAPSO-SVM is proposed as an innovative clustering routing protocol, specifically designed for the IoT perception layer, with an emphasis on energy-aware localization and routing. It integrates a Support Vector Machine (SVM) for precise location estimation and a Genetic Algorithm-Particle Swarm Optimization (GAPSO) for efficient clustering. The primary contributions of this approach include:

A hybrid IDSS-based clustering routing protocol that significantly enhances energy efficiency and network longevity over previous methodologies.

An SVM-based localization algorithm that enables accurate location estimation without the need for GPS, addressing a common limitation in geographic protocols.

A hybrid GAPSO algorithm that optimizes clustering with superior convergence rate and efficiency compared to similar endeavors.

The GAPSO-SVM algorithm’s framework involves specifying sensor nodes and beacons, alongside calculating the energy required for transmitting and receiving data, optimizing the network’s energy consumption for effective data communication from cluster heads (CHs) to the sink.

Through simulation, GAPSO-SVM demonstrated substantial improvements in network lifetime and energy efficiency, utilizing SVM for precise localization without GPS and leveraging GAPSO for efficient clustering. The results indicated marked advancements in convergence rates, network longevity, and energy savings, significantly outperforming the metrics of the existing EEWC algorithm.

III-B 2 Optimization Process

The GAPSO-SVM algorithm employs a hybrid optimization strategy that combines the strengths of Genetic Algorithms (GA) and Particle Swarm Optimization (PSO) to enhance the clustering and routing processes in IoT networks. The optimization process is detailed as follows:

Initialization: The set of sensor nodes within the network is defined, alongside the specification of beacon and non-beacon nodes. This step forms the basis for the clustering and routing mechanism.

Energy Calculation: For each node, the energy required to transmit (ET) and receive (ER) an L-bit message over a distance d 𝑑 d italic_d is calculated using:

where E e ⁢ l ⁢ e ⁢ c subscript 𝐸 𝑒 𝑙 𝑒 𝑐 E_{elec} italic_E start_POSTSUBSCRIPT italic_e italic_l italic_e italic_c end_POSTSUBSCRIPT is the energy consumed per bit by the transmitter or receiver circuit, and ϵ f ⁢ s subscript italic-ϵ 𝑓 𝑠 \epsilon_{fs} italic_ϵ start_POSTSUBSCRIPT italic_f italic_s end_POSTSUBSCRIPT , ϵ m ⁢ p subscript italic-ϵ 𝑚 𝑝 \epsilon_{mp} italic_ϵ start_POSTSUBSCRIPT italic_m italic_p end_POSTSUBSCRIPT are the amplifier energy consumption parameters for free space and multipath models respectively.

Hybrid GAPSO Mechanism: The optimization leverages the fast convergence rate of PSO and the robust search capabilities of GA. The population of solutions (sensor nodes’ clustering configurations) is evolved using both GA and PSO principles:

Part of the population is processed using GA operations (selection, crossover, and mutation) to explore the search space.

The remaining part is updated using PSO rules, guiding the particles (solutions) toward the best-found positions.

Hybridization Coefficient (HC): A key parameter in GAPSO, HC determines the proportion of the population to be processed by GA in each iteration. An optimal HC value ensures a balanced exploration and exploitation, enhancing the algorithm’s efficiency and convergence.

Evaluation and Iteration: The fitness of each solution is evaluated based on criteria such as energy efficiency, network lifetime, and connectivity. The population is then updated iteratively, combining GA and PSO updates to find an optimal clustering configuration.

III-B 3 Performance Evaluation

The performance of GAPSO-SVM was rigorously tested against the EEWC algorithm, showcasing significant improvements in network lifetime and energy efficiency. Key findings include:

Improved Convergence Rate: GAPSO-SVM demonstrated an 80% improvement in convergence rate over EEWC(Fig. 8a ), leading to faster optimization of CHs.

Extended Network Lifetime: The network lifetime under GAPSO-SVM extended by 11% (Fig. 8b ), attributed to optimized clustering and routing strategies.

Energy Efficiency: GAPSO-SVM reduced the energy consumption significantly(Fig. 8c ), ensuring a sustainable IoT network operation.

III-B 4 Conclusion

The simulation results indicate that GAPSO-SVM outperforms the existing EEWC algorithm in terms of convergence rate, network longevity, and energy efficiency, making it a promising solution for energy-aware localization and routing in IoT networks.

• [1] wikipedia, “Shortest path problem,” https://en.wikipedia.org/wiki/Shortest_path_problem , 2024, [Online; accessed 22-Feb-2024].
• [2] M. Behrouzian Nejad, A. Mehranzadeh, and M. Hoodgar, “Performance of input and output selection techniques on routing efficiency in network-on-chip,” International Journal of Computer Science and Information Security, , vol. 9, 09 2011.
• [3] S. Supittayapornpong, P. Namyar, M. Zhang, M. Yu, and R. Govindan, “Optimal oblivious routing for structured networks,” in IEEE INFOCOM 2022 - IEEE Conference on Computer Communications , 2022, pp. 1988–1997.
• [4] A. E. Abdallah, “Smart partial flooding routing algorithms for 3d ad hoc networks,” Procedia Computer Science , vol. 94, pp. 264–271, 2016, the 11th International Conference on Future Networks and Communications (FNC 2016) / The 13th International Conference on Mobile Systems and Pervasive Computing (MobiSPC 2016) / Affiliated Workshops. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1877050916317872
• [5] A. Gupta, A. Smith, and A. Sun, “Design and implementation of fisheye routing protocol for mobile ad hoc networks,” none , 09 2001.
• [6] cisco, “Link State Routing Protocol,” https://www.ciscopress.com/articles/article.asp?p=2180210&seqNum=11 , 2014, [Online; accessed 22-Feb-2024].
• [7] ArunChokkalingam, “Energy Efficient Routing,” https://www.slideshare.net/ArunChokkalingam/wsnrouting-protocols-energy-efficient-routing , 2020, [Online; accessed 22-Feb-2024].
• [8] E. F. Ahmed Elsmany, M. A. Omar, T.-C. Wan, and A. A. Altahir, “Eesra: Energy efficient scalable routing algorithm for wireless sensor networks,” IEEE Access , vol. 7, pp. 96 974–96 983, 2019.
• [9] M. N. Shad, M. Maadani, and M. N. Moghadam, “Gapso-svm: An idss-based energy-aware clustering routing algorithm for iot perception layer,” Wireless Personal Communications , vol. 126, no. 3, pp. 2249–2268, 2022. [Online]. Available: https://doi.org/10.1007/s11277-021-09051-5

Subscribe to the PwC Newsletter

Join the community, edit social preview.

Add a new code entry for this paper

Remove a code repository from this paper, mark the official implementation from paper authors, add a new evaluation result row.

Remove a task

Add a method, remove a method, edit datasets, routing algorithms.

17 Mar 2024  ·  Ujjwal Sinha , Vikas Kumar , Shubham Kumar Singh · Edit social preview

Routing algorithms play a crucial role in the efficient transmission of data within computer networks by determining the optimal paths for packet forwarding. This paper presents a comprehensive exploration of routing algorithms, focusing on their fundamental principles, classification, challenges, recent advancements, and practical applications. Beginning with an overview of the significance of routing in modern communication networks, the paper delves into the historical evolution of routing algorithms, tracing their development from early approaches to contemporary techniques. Key categories of routing algorithms, including distance vector, link-state, and path vector algorithms, are examined in detail, along with hybrid approaches that integrate multiple routing paradigms. Common challenges faced by routing algorithms, such as routing loops and scalability issues, are identified, and current research efforts aimed at addressing these challenges are discussed.

Code Edit Add Remove Mark official

Datasets edit.

process 0 (0.0) lower 3 to 3841.9 lower 1 to 1897.4 process 1 (1897.4) lower 4 to 3776.2 lower 2 to 2537.7 process 2 (2537.7) lower 5 to 6274.0 process 4 (3776.2) process 3 (3841.9) process 5 (6274.0)

Instantly share code, notes, and snippets.

systemed / gist:be2d6bb242d2fa497b5d93dcafe85f0c

• Download ZIP
• Star ( 86 ) 86 You must be signed in to star a gist
• Fork ( 12 ) 12 You must be signed in to fork a gist
• Embed Embed this gist in your website.
• Share Copy sharable link for this gist.
• Clone via HTTPS Clone using the web URL.
• Learn more about clone URLs
• Save systemed/be2d6bb242d2fa497b5d93dcafe85f0c to your computer and use it in GitHub Desktop.

easbar commented Jun 17, 2019 • edited Loading

Contraction Hierarchies Rust https://github.com/easbar/fast_paths/

Sorry, something went wrong.

LdDl commented Aug 23, 2019 • edited Loading

CH (without turn restricted pathes) + Dijkstra with turn restricted pathes on Golang https://github.com/LdDl/ch

vlarmet commented Feb 4, 2020

Contraction Hierarchies and PHAST (Hardware-accelerated shortest path trees) in C++ https://github.com/vlarmet/cppRouting

s3131212 commented Mar 8, 2021

Transit Node Routing ( + Contraction Hierarchies) in Go: https://github.com/s3131212/TNR-CH

adityarauniyar commented Jul 2, 2021

All routing algo implementations in one place (using cpp and google test) : https://github.com/adityarauniyar/graph-algorithms

Computer Network

• Operating Systems
• Computer Fundamentals
• Interview Q

Physical Layer

Data link layer, network layer, routing algorithm, transport layer, application layer, application protocols, network security.

Interview Questions

The Routing algorithm is divided into two categories: It is also known as global routing algorithm as it computes the least-cost path between source and destination by using complete and global knowledge about the network. This algorithm takes the connectivity between the nodes and link cost as input, and this information is obtained before actually performing any calculation. is referred to as a centralized algorithm since it is aware of the cost of each link in the network. It is an algorithm that obtains the routing information by using local information rather than gathering information from other nodes. It is also known as decentralized algorithm as it computes the least-cost path between source and destination in an iterative and distributed manner. In the decentralized algorithm, no node has the knowledge about the cost of all the network links. In the beginning, a node contains the information only about its own directly attached links and through an iterative process of calculation computes the least-cost path to the destination. A Distance vector algorithm is a decentralized algorithm as it never knows the complete path from source to the destination, instead it knows the direction through which the packet is to be forwarded along with the least cost path. In case of flooding, every incoming packet is sent to all the outgoing links except the one from it has been reached. The disadvantage of flooding is that node may contain several copies of a particular packet. In case of random walks, a packet sent by the node to one of its neighbors randomly. An advantage of using random walks is that it uses the alternative routes very efficiently. Basis Of Comparison Adaptive Routing algorithm Non-Adaptive Routing algorithm Define Adaptive Routing algorithm is an algorithm that constructs the routing table based on the network conditions. The Non-Adaptive Routing algorithm is an algorithm that constructs the static table to determine which node to send the packet. Usage Adaptive routing algorithm is used by dynamic routing. The Non-Adaptive Routing algorithm is used by static routing. Routing decision Routing decisions are made based on topology and network traffic. Routing decisions are the static tables. Categorization The types of adaptive routing algorithm, are Centralized, isolation and distributed algorithm. The types of Non Adaptive routing algorithm are flooding and random walks. Complexity Adaptive Routing algorithms are more complex. Non-Adaptive Routing algorithms are simple. Send your Feedback to [email protected] Help Others, Please Share Learn Latest Tutorials Transact-SQL Reinforcement Learning R Programming React Native Python Design Patterns Python Pillow Python Turtle Preparation Verbal Ability Company Questions Trending Technologies Artificial Intelligence Cloud Computing Data Science Machine Learning B.Tech / MCA Data Structures Operating System Compiler Design Computer Organization Discrete Mathematics Ethical Hacking Computer Graphics Software Engineering Web Technology Cyber Security C Programming Control System Data Mining Data Warehouse Engineering Mathematics Discrete Mathematics Operating System Computer Networks Digital Logic and Design C Programming Data Structures Theory of Computation Compiler Design Computer Org and Architecture What is Routing? The process of choosing a path across one or more networks is known as Network Routing. Nowadays, individuals are more connected on the internet and hence, the need to use Routing Communication is essential. Routing chooses the routes along which Internet Protocol (IP) packets get from their source to their destination in packet-switching networks. This article will discuss the details of the Routing Process along with its different types and working principles. What is a Router? Routers are specialized pieces of network hardware that make these judgments about Internet routing. It is a networking device that forwards data packets between computer networks. Also, it helps to direct traffic based on the destination IP address . It ensures that data reaches its intended destination. As the router connects different networks, it manages data traffic between them. The Router operates at Layer 3 (the network layer) of the OSI Model . It is also responsible for determining the best path for data to travel from one network to another. Routing refers to the process of directing a data packet from one node to another. It is an autonomous process handled by the network devices to direct a data packet to its intended destination. Note that, the node here refers to a network device called – ‘ Router ‘. Routing is a crucial mechanism that transmits data from one location to another across a network (Network type could be any like LAN, WAN, or MAN ). The process of routing involves making various routing decisions to ensure reliable & efficient delivery of the data packet by finding the shortest path using various routing metrics which we will be discussing in this article. Routing of a data packet is done by analyzing the destination IP Address of the packet. Look at the below image: Routing of packets The Source Node (Sender) sends the data packet on the network, embedding the IP in the header of the data packet. The nearest router receives the data packet, and based on some metrics, further routes the data packet to other routers. Step 2 occurs recursively till the data packet reaches its intended destination. Note: There are limits to how many hop counts a packet can do if it is exceeded, the packet is considered to be lost. What are Different Types of Routing? Routing is typically of 3 types, each serving its purpose and offering different functionalities. Types of Routing 1. Static Routing Static routing is also called as “non-adaptive routing”. In this, routing configuration is done manually by the network administrator. Let’s say for example, we have 5 different routes to transmit data from one node to another, so the network administrator will have to manually enter the routing information by assessing all the routes. A network administrator has full control over the network, routing the data packets to their concerned destinations Routers will route packets to the destination configured manually by the network administrator. Although this type of routing gives fine-grained control over the routes, it may not be suitable for large-scale enterprise networks. 2. Dynamic Routing Dynamic Routing is another type of routing in which routing is an autonomous procedure without any human intervention. Packets are transmitted over a network using various shortest-path algorithms and pre-determined metrics. This type of routing is majorly preferred in modern networks as it offers more flexibility and versatile functionality. It is also known as adaptive routing. In this, the router adds new routes to the routing table based on any changes made in the topology of the network. The autonomous procedure of routing helps in automating every routing operation from adding to removing a route upon updates or any changes made to the network. 3. Default Routing Default Routing is a routing technique in which a router is configured to transmit packets to a default route that is, a gateway or next-hop device if no specific path is defined or found. It is commonly used when the network has a single exit point. The IP Router has the following address as the default route: 0.0.0.0/0. What is the Working Principle of Routing? Routing works by finding the shortest path from the source node to the destination node across a network. Here’s the step-by-step working of routing: Step 1: Communication initiation The first step that typically happens is, one node (client or server) initiates a communication across a network using HTTP protocols. Step 2: Data Packets The source device now breaks a big chunk of information into small data packets for reliable and efficient transmission. This process is called de-assembling and encapsulating the data payload. Then each data packet is labeled with the destination node’s IP address. Step 3: Routing Table The Routing table is a logical data structure used to store the IP addresses and relevant information regarding the nearest routers. The source node then looks up the IP addresses of all the nodes that can transmit the packet to its destination selects the shortest path using the shortest path algorithm and then routes accordingly. The Routing Table is stored in a router, a network device that determines the shortest path and routes the data packet. Step 4: Hopping procedure In the procedure or routing, the data packet will undergo many hops across various nodes in a network till it reaches its final destination node. Hop count is defined as the number of nodes required to traverse through to finally reach the intended destination node. This hopping procedure has certain criteria defined for every data packet, there’s a limited number of hops a packet can take if the packet exceeds that, then it’s considered to be lost and is retransmitted. Step 5: Reaching the destination node Once all the data packets reach their intended destination node, they re-assemble and transform into complete information that was sent by the sender (source node). The receiver will perform various error-checking mechanisms to verify the authenticity of the data packets. Overall, the data packet will be transmitted over the least hop-count path as well as the path on which there is less traffic to prevent packet loss. Working of Routing In the above image, we have 3 major components The shortest path is highlighted in red, the path with the least hop count. As we can see, there are multiple paths from source to node but if all the appropriate metrics are satisfied, the data packets will be transmitted through the shortest path (highlighted in red). What are the Main Routing Protocols? RIP (Routing Information Protocol): It is a distance-vector protocol that uses hop count as a metric. OSPF (Open Shortest Path First): OSPF is a link-state protocol that finds the shortest path using the Dijkstra algorithm. EIGRP (Enhanced Interior Gateway Routing Protocol): It is a hybrid protocol that combines features of distance-vector and link-state. BGP (Border Gateway Protocol): It is a path-vector protocol that is used for routing between different autonomous systems on the internet. IS-IS (Intermediate System to Intermediate System): It is a link-state protocol that is primarily used in large networks like ISPs. What are Different Routing Metrics? The purpose of routing protocols is to learn about all the available paths to route data packets, build routing tables, and make routing decisions based on specified metrics. There are two primary types of routing protocols rest of them ideate from these two only. 1. Distance Vector Routing In this type of routing protocol, all the nodes that are a part of the network advertise their routing table to their adjacent nodes (nodes that are directly connected) at regular intervals. With each router getting updated at regular intervals, it may take time for all the nodes to have the same accurate network view. Uses fixed length sub-net, not suitable for scaling. Algorithm used: Bellman Ford Algorithm to find the shortest path. 2. Link State Routing Link State Routing is another type of dynamic routing protocol in which routes advertise their updated routing tables only when some new updates are added. This results in the effective use of bandwidth. All the routers keep exchanging information dynamically regarding different links such as cost and hop count to find the best possible path. Uses a variable length subnet mask, which is scalable and uses addressing more effectively. The algorithm used: Dijkstra’s Algorithm to find the shortest path. Let’s look at the metrics used to measure the cost of travel from one node to another:- Hop Count: Hop count refers to the number of nodes a data packet has to traverse to reach its intended destination. Transmitting from one node to another node counts as 1 – hop count. The goal is to minimize the hop count and find the shortest path. Bandwidth Consumption: Bandwidth is the ability of a network to transmit data typically measured in Kbps (Kilobits per second) , Mbps (Megabits per second) , or Gbps (Gigabits per second) . The bandwidth depends on several factors such as – the volume of data, traffic on a network, network speed, etc. Routing decision is made in a way to ensure efficient bandwidth consumption. Delay: Delay is the time it takes for a data packet to travel from the source node to its destination node. There are different types of delay such as – propagation delay, transmission delay, and queuing delay. Load: Load refers to the network traffic on a certain path in the context of routing. A data packet will be routed to the path with a lesser load so that it reaches its destination in the specified time. Reliability: Reliability refers to the assured delivery of the data packet to its intended destination although there are certain other factors, the data packet is routed in such a way that it reaches its destination. The stability and availability of the link in the network are looked over before routing the data packet from a specific path. What are the Advantages of Routing? Overall routing can be done in various ways its important to know the requirements and use the one that fits right for our specific needs, hence automated routing is typically preferred as the routing of packets is done by the algorithms defined and the manually configurable routing can give us a fine-grained control over the network. Routing is a highly scalable operation for transmitting data that is, in a large-scale enterprise network it becomes crucial to manage information related to all the nodes that may be sharing sensitive and confidential information regarding the organization. Load Balancing is also one of the crucial aspects taken care of by routing data packets off the routes that are generally busy as sending data through those routes will only put our data at risk of getting lost. What are the Disadvantages of Routing? Every type of routing comes with some pros and cons here are some of the disadvantages for specific types of routing : Static Routing: This type of routing is appropriate only for smaller networks where the network administrator has an accurate view of the network & good knowledge of topology else it might raise some security concerns and complex configuration issues. Dynamic Routing: Everything is done automatically by the algorithms, providing less control over the network that may not be suitable for every kind of network. It is also computationally expensive and consumes more bandwidth. Default Routing: The path on which the packets are to be transmitted by default is configurable but can be a complex procedure if not defined clearly. Routing is a fundamental concept in computer science that allows every network device across the world to share data across the internet. Here, the shortest path is selected by the routing algorithms when routing a data packet. So, the Routing Algorithms select the shortest path based on metrics like – hop count, delay, bandwidth, etc. What is Routing – FAQs What are routing examples. Traffic in a road system is an example of routing, in which driver picks a selected path that reduces their travel time. How does a router work? Routes examine the IP in the header of every data packet received and if it belongs to it then it keeps the data packet else it re-routes it to another router based on some metrics. What is a Default Gateway? The default gateway is simply a router or another network device that allows the host to connect with other networks outside its local network. It is a crucial component of internetwork communication. Please Login to comment... Similar reads. Geeks Premier League Geeks Premier League 2023 Improve your Coding Skills with Practice What kind of Experience do you want to share? Routing and Wavelength Assignment (RWA): Overview Cite this chapter. Hussein T. Mouftah 2 & Pin-Han Ho 2   176 Accesses Routing and wavelength assignment (RWA) constitutes one of the most fundamental elements in the control and management of an optical network. This chapter provides an introduction to the design principles and objectives of the constraint of the RWA problem, and an overview of proposed schemes and approaches of the implementation and analytical modeling of the RWA process. The constraints imposed on a wavelength-routed optical network are outlined in Section 3.2, which includes topics of physical constraint and diversity constraint. Section 3.3 describes modeling of optical networks with and without wavelength conversion capability. The model incorporates networks containing partial wavelength convertible nodes with different conversion ranges. We also provide an algorithm for performing optimal routing and wavelength assignment in networks with nodes of partial wavelength conversion capability. The approach is based on a modified Dijkstra’s shortest path first algorithm, and can achieve a good computation complexity compared with some other reported schemes. This is a preview of subscription content, log in via an institution to check access. Access this chapter Subscribe and save. Get 10 units per month Download Article/Chapter or eBook 1 Unit = 1 Article or 1 Chapter Cancel anytime Available as PDF Read on any device Instant download Own it forever Available as EPUB and PDF Compact, lightweight edition Dispatched in 3 to 5 business days Free shipping worldwide - see info Durable hardcover edition Tax calculation will be finalised at checkout Purchases are for personal use only Institutional subscriptions Unable to display preview.  Download preview PDF. A. Chiu, R. Tkach, J. Luciani, A. Banerjee, J. Drake, D. Blumenthal, A. Fredette, N. Froberg, and J. Strand (Editor), “Impairments And Other Constraints On Optical Layer Routing,” Internet Draft, <draft~ietf-ipo-impairments-01.txt>, work in progress , Dec. 2001. Google Scholar   E. L. Goldstein, L. Eskildsen, and, A. F. Elrefaie, “Performance Implications of Component Crosstalk in Transparent Lightwave Networks,” IEEE Photonics Technology Letters , Vol.6, No.5, May 1994. J. Strand, A. Chiu, and R. Tkach, “Issues for Routing in the Optical Layer,” IEEE Communications Magazine , Vol. 39, No. 2, pp. 81–88, Feb. 2001. Article   Google Scholar   R. Tkach, E. Goldstein, J. Nagel, and, J. Strand, “Fundamental Limits of Optical Transparency”, Optical Fiber Communication Conference , Feb. 1998, pp. 161–162. J. Yates, J. Lacey and M. Rumsewicz, “Wavelength Converters in Dynamically Reconfigurable WDM Networks,” IEEE Communications Surveys , 2nd quarter issue. S. Xu, L. Li, and S. Wang, “Dynamic Routing and Assignment of Wavelength Algorithm in Multifiber Wavelength Division multiplexing Networks”, IEEE Journal on Selected Areas in Communications . Vol. 18, No. 10, pp. 2130–2137, Oct. 2000. I. Chlamtac, A. Farago, and T. Zhang, “Lightpath (Wavelength) Routing in Large WDM Networks,” IEEE JSAC, vol. 14, pp. 909–913, June 1996. E. Karasan and E. Ayanoglu, “Effects of Wavelength Routing and Selection Algorithms on Wavelength Conversion Gain in WDM Optical Netowrk”, IEEE/ACM Transactions on Networking , Vol. 6, No. 2, April 1998. G. Xue, “Optimal Lightpath Routing and Rerouting in WDM Networks,” Proceedings IEEE Globecom 2001 , OPC02–6. B. M. E. Moret and H. D. Shapiro, Algorithms from P to NP Volume I Design & Efficiency , the Benjamin/Cummings Publishing Company, Inc. J. P. Jue and G. Xiao, “An Adaptive Routing Algorithm for Wavelength-Routed Optical Networks with a Distributed Control Scheme,” Proceedings IEEE Ninth International Conference on Computer Communications and Networks (IC3N2000) , Oct. 2000. H. Zang, Jason P. Jue, and B. Mukherjee, “A Review of Routing and Wavelength Assignment Approaches for Wavelength-Routed optical WDM Networks”, Optical Networks Magazine, SPIE, Vol. 1, Number 1 , pp. 47–60, Jan. 2000. I. Chlamtac, A. Farago, and T. Zhang, “Lightpath (Wavelength) Routing in Large WDM Networks,” IEEE Journal of Selected Areas in Communications , Vol. 14, No. 5, June 1996. R. Chow and T. Johnson, “Distributed Operating System & Algorithm”, Addison Wesley Longman, Inc . 1997. Download references Author information Authors and affiliations. Queen’s University at Kingston, Ontario, Canada Hussein T. Mouftah & Pin-Han Ho You can also search for this author in PubMed   Google Scholar Rights and permissions Reprints and permissions Copyright information © 2003 Springer Science+Business Media Dordrecht About this chapter Mouftah, H.T., Ho, PH. (2003). Routing and Wavelength Assignment (RWA): Overview. In: Optical Networks. Springer, Boston, MA. https://doi.org/10.1007/978-1-4615-1169-4_3 Download citation DOI : https://doi.org/10.1007/978-1-4615-1169-4_3 Publisher Name : Springer, Boston, MA Print ISBN : 978-1-4613-5426-0 Online ISBN : 978-1-4615-1169-4 eBook Packages : Springer Book Archive Share this chapter Anyone you share the following link with will be able to read this content: Sorry, a shareable link is not currently available for this article. Provided by the Springer Nature SharedIt content-sharing initiative Publish with us Policies and ethics Find a journal Track your research Programming Assignment 2 (130 points) Implementing a distance vector routing algorithm. In this lab, you will be writing a "distributed" set of procedures that implement a distributed asynchronous distance vector routing for the network shown in Figure Lab.4-1. The Basic Assignment The routines you will write For the basic part of the assignment, you are to write the following routines which will ``execute'' asynchronously within the emulated environment that the authors have provided for this assignment. For node 0, you will write the routines: rtupdate0(struct rtpkt *rcvdpkt) . This routine will be called when node 0 receives a routing packet that was sent to it by one if its directly connected neighbors. The parameter *rcvdpkt is a pointer to the packet that was received. rtupdate0() is the "heart" of the distance vector algorithm. The values it receives in a routing packet from some other node i contain i 's current shortest path costs to all other network nodes. rtupdate0() uses these received values to update its own distance table (as specified by the distance vector algorithm). If its own minimum cost to another node changes as a result of the update, node 0 informs its directly connected neighbors of this change in minimum cost by sending them a routing packet. Recall that in the distance vector algorithm, only directly connected nodes will exchange routing packets. Thus nodes 1 and 2 will communicate with each other, but nodes 1 and 3 will node communicate with each other. As we saw in class, the distance table inside each node is the principal data structure used by the distance vector algorithm. You will find it convenient to declare the distance table as a 4-by-4 array of int 's, where entry [i,j] in the distance table in node 0 is node 0's currently computed cost to node i via direct neighbor j. If 0 is not directly connected to j, you can ignore this entry. We will use the convention that the integer value 999 is ``infinity.'' Figure Lab.4-2 provides a conceptual view of the relationship of the procedures inside node 0. Similar routines are defined for nodes 1, 2 and 3. Thus, you will write 8 procedures in all: rtinit0(), rtinit1(), rtinit2(), rtinit3(),rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3() Software Interfaces The procedures described above are the ones that you will write.  Authors Kurose and Ross have written the following routines that can be called by your routines: The simulated network environment Your procedures rtinit0(), rtinit1(), rtinit2(), rtinit3() and rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3() send routing packets (whose format is described above) into the medium. The medium will deliver packets in-order, and without loss to the specified destination. Only directly-connected nodes can communicate. The delay between is sender and receiver is variable (and unknown). When you compile your procedures and Kurose-Ross's procedures together and run the resulting program, you will be asked to specify only one value regarding the simulated network environment: Tracing. Setting a tracing value of 1 or 2 will print out useful information about what is going on inside the emulation (e.g., what's happening to packets and timers). A tracing value of 0 will turn this off. A tracing value greater than 2 will display all sorts of odd messages that are for my own emulator-debugging purposes. A tracing value of 2 may be helpful to you in debugging your code. You should keep in mind that real implementors do not have underlying networks that provide such nice information about what is going to happen to their packets! The Basic Assignment (100 points) You are to write the procedures rtinit0(), rtinit1(), rtinit2(), rtinit3() and rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3() which together will implement a distributed, asynchronous computation of the distance tables for the topology and costs shown in Figure 1. You should put your procedures for nodes 0 through 3 in files called node0.c, .... node3.c. You are NOT allowed to declare any global variables that are visible outside of a given C file (e.g., any global variables you define in node0.c. may only be accessed inside node0.c ). This is to force you to abide by the coding conventions that you would have to adopt is you were really running the procedures in four distinct nodes. To compile your routines: cc prog2.c node0.c node1.c node2.c node3.  Prototype versions of these files are here: node0.c , node1.c , node2.c , node3.c . You can pick up a copy of the file prog2.c at http://www.ccs.neu.edu/home/rraj/Courses/U640/F04/Programs/prog2.c . This assignment can be completed on any machine supporting C. It makes no use of UNIX features. As always, most instructors would expect you to hand in a code listing, a design document, and sample output. For your sample output, your procedures should print out a message whenever your rtinit0(), rtinit1(), rtinit2(), rtinit3() or rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3() procedures are called, giving the time (available via the global variable clocktime ).  For rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3() you should print the identity of the sender of the routing packet that is being passed to your routine, whether or not the distance table is updated, the contents of the distance table (you can use the pretty-print routines), and a description of any messages sent to neighboring nodes as a result of any distance table updates. The sample output should be an output listing with a TRACE value of 2. Highlight the final distance table produced in each node. Your program will run until there are no more routing packets in-transit in the network, at which point our emulator will terminate. The Advanced Assignment (30 points) You are to write two procedures, rtlinkhandler0(int linkid, int newcost) and rtlinkhandler1(int linkid, int newcost) , which will be called if (and when) the cost of the link between 0 and 1 changes. These routines should be defined in the files node0.c and node1.c, respectively. The routines will be passed the name (id) of the neighboring node on the other side of the link whose cost has changed, and the new cost of the link. Note that when a link cost changes, these routines will have to update the distance table and may (or may not) have to send updated routing packets to neighboring nodes. In order to complete the advanced part of the assignment, you will need to change the value of the constant LINKCHANGES (line 3 in prog2.c) to 1. FYI, the cost of the link will change from 1 to 20 at time 10000 and then change back to 1 at time 20000. Your routines will be invoked at these times. We would STRONGLY recommend that you first implement the basic assignment and then extend your code to implement the advanced assignment. It will not be time wasted. What to submit Please submit a zip file electronically, that contains: the source file(s) a README file that describes  your implementations of the subroutines, and special instructions (if any) for running the code. a sample output -- more on this below. Please email your submission to our TA Shweta Jain (shweta AT ccs ).   Please also submit a hard copy of your source and README files in class on Wednesday, December 1. CNT4704: Analysis of Computer Communication Networks Home                       Lecture notes                         Assignment Programming Assignment 3: Distributed Simulation of Distance Vector Routing protocol (Assigned: Nov. 4th, Due: Nov. 18th midnight, Late submission by Nov. 24th with 20 points off) In this lab, you will be writing a "distributed" set of procedures that implement a distributed asynchronous distance vector routing for the network shown in Figure 1. This project is implemented in the similar way as in project 2---a simulator is provided ( prog3.c ) and your task is to complete the coding for several function calls that will be called by the simulator in a statistical way. To complete the project, you need to understand well the example shown on Page 32,33 in lecture notes Chapter4-part2.ppt. The routines you will write : You are to write the following routines which will ``execute'' asynchronously within the emulated environment that the textbook authors have written for this assignment. For node 0, you will write the following two routines: rtupdate0(struct rtpkt *rcvdpkt) . This routine will be called when node 0 receives a routing packet that was sent to it by one if its directly connected neighbors. The parameter *rcvdpkt is a pointer to the packet that was received. rtupdate0() is the "heart" of the distance vector algorithm. The values it receives in a routing packet from some other node i contain i 's current shortest path costs to all other network nodes. rtupdate0() uses these received values to update its own distance table (as specified by the distance vector algorithm). If its own minimum cost to another node changes as a result of the update, node 0 informs its directly connected neighbors of this change in minimum cost by sending them a routing packet. Recall that in the distance vector algorithm, only directly connected nodes will exchange routing packets. Thus nodes 1 and 2 will communicate with each other, but nodes 1 and 3 will not communicate with each other. As we saw in class (example in Page 32 in Chapter4-part2.ppt), the distance table inside each node is the principal data structure used by the distance vector algorithm. It is declared as a 4-by-4 array of int 's, where the i-th row is the distance vector of node i. If the node i is not directly connected to the current node , this i-th row entry can be ignored. We will use the convention that the integer value 99 is ``infinity'', which is defined as micro in all code files. Figure. 2 provides a conceptual view of the relationship of the procedures inside node 0. Similar routines are defined for nodes 1, 2 and 3. Thus, you will write 8 procedures in all: rtinit0(), rtinit1(), rtinit2(), rtinit3(),rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3() Software Interfaces The procedures described above are the ones that you will write. The following routines have been provided in the simulator ( prog3.c ) that can be called by your routines:        It will create a packet containing the distance vector mincosts[] (4 entries) and send to destination node destid (specifying that it is sent from the source node srcid). And at the same time print out information of such event. After a simulated time delay, the rtupdate?() function of the destination node destid will be called to process this received packet. The packet is the following structure, which is already declared for you. The Simulated Network Environment Your procedures rtinit0(), rtinit1(), rtinit2(), rtinit3() and rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3() send routing packets (whose format is described above) into the medium. The medium will deliver packets in-order, and without loss to the specified destination. Only directly-connected nodes can communicate. The delay between a sender and a receiver is statistically variable (and unknown). When you compile your procedures and the provided prog3.c procedures together and run the resulting program, you will be asked to specify only one value regarding the simulated network environment: Tracing. Setting a tracing value of 1 or 2 will print out useful information about what is going on inside the emulation (e.g., what's happening to packets and timers). A tracing value of 0 will turn this off. A tracing value greater than 2 will display all sorts of odd messages that are for my own emulator-debugging purposes. A tracing value of 2 may be helpful to you in debugging your code. You should keep in mind that real implementors do not have underlying networks that provide such nice information about what is going to happen to their packets! The Required Content in Project Report You are to write the procedures rtinit0(), rtinit1(), rtinit2(), rtinit3() and rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3() which together will implement a distributed, asynchronous computation of the distance tables for the topology and costs shown in Figure 1. You should put your procedures for nodes 0 through 3 in files called node0.c, .... node3.c. You are NOT allowed to declare any global variables that are visible outside of a given C file (e.g., any global variables you define in node0.c. may only be accessed inside node0.c ). This is to force you to abide by the coding conventions that you would have to adopt is you were really running the procedures in four distinct nodes. To compile your routines use (under the department's Eustis machine): cc -o dvSim prog3.c node0.c node1.c node2.c node3 .c , which will generate the executable program called dvSim. Prototype versions of these files are here: node0.c , node1.c , node2.c , node3.c . Note that do not pay attention to the empty function linkhandler0(linkid, newcost) in the above 4 nodes' code files. It is used by the textbook authors for advanced graduate course teaching. This assignment can be completed on any machine supporting C. It makes no use of UNIX features. You are expected to submit in the four code file (code0.c ~ code3.c), and the generated executable code. And a project report file with a sample output ( with a screenshot image showing the simulator running procedure/result ). You are not supposed to modify the simulator code prog3.c For your sample output, your procedures should call printdt?() at the end of rtinit?(), and call printdt?() whenever your node needs to send out a distance vector update message in rtupdate?(). The sample output should be an output listing with a TRACE value of 2 . Highlight the final distance table produced in each node. Your program will run until there are no more routing packets in-transit in the network, at which point the emulator will terminate. JAVA Version Of This Assignment Entity.java,  Entity0.java,  Entity1.java,   Entity2.java,  Entity3.java,  NetworkSimulator.java,  Event.java, Packet.java,   EventList.java,  EventListImpl.java,  Project.java Note that the Java code will allow you to hang yourself by sending incorrect packets via the toLayer2() method of NetworkSimulator.  So please be extra careful there. NIST 800-53 Common Controls Hub The Cisco router must be configured to enable routing protocol authentication using FIPS 198-1 algorithms with keys not exceeding 180 days of lifetime. Finding ID Version Rule ID IA Controls Severity V-216739 CISC-RT-000050 SV-216739r929061_rule Medium Description A rogue router could send a fictitious routing update to convince a site's perimeter router to send traffic to an incorrect or even a rogue destination. This diverted traffic could be analyzed to learn confidential information about the site's network or used to disrupt the network's ability to communicate with other networks. This is known as a "traffic attraction attack" and is prevented by configuring neighbor router authentication using FIPS 198-1 algorithms for routing updates. If the keys used for authentication are guessed, the malicious user could create havoc within the network by advertising incorrect routes and redirecting traffic. Some routing protocols allow the use of key chains for authentication. A key chain is a set of keys that is used in succession, with each having a lifetime of no more than 180 days. Changing the keys frequently reduces the risk of them eventually being guessed. If a time period occurs during which no key is activated, neighbor authentication cannot occur, and therefore routing updates will fail. STIG Date 2024-06-06 Check Text ( C-17971r929059_chk ) Review the router configuration using the configuration examples below for BGP and OSPF. EIGRP, RIP, and IS-IS only support MD5 and will incur a permanent finding for those protocols. Note: The 180-day key lifetime is Not Applicable for the DODIN Backbone. The remainder of the requirement still applies. Verify that neighbor router authentication is enabled for all routing protocols. If neighbor authentication is not enabled this is a finding. Verify that authentication is configured to use FIPS 198-1 message authentication algorithms. If the routing protocol authentication is not configured to use FIPS 198-1 algorithms this is a finding. Verify that the protocol key lifetime is configured to not exceed 180 days. If any protocol key lifetime is configured to exceed 180 days this is a finding. BGP Example: key chain Fix Text (F-17969r929060_fix) Configure routing protocol authentication to use a NIST-validated FIPS 198-1 message authentication code algorithm with keys not exceeding 180 days of lifetime as shown in the examples. BGP Example: Step 1: Configure a keychain using a FIPS 198-1 algorithm with a key duration not exceeding 180 days. key chain Information Author Services Initiatives You are accessing a machine-readable page. In order to be human-readable, please install an RSS reader. All articles published by MDPI are made immediately available worldwide under an open access license. No special permission is required to reuse all or part of the article published by MDPI, including figures and tables. For articles published under an open access Creative Common CC BY license, any part of the article may be reused without permission provided that the original article is clearly cited. For more information, please refer to https://www.mdpi.com/openaccess . Feature papers represent the most advanced research with significant potential for high impact in the field. A Feature Paper should be a substantial original Article that involves several techniques or approaches, provides an outlook for future research directions and describes possible research applications. Feature papers are submitted upon individual invitation or recommendation by the scientific editors and must receive positive feedback from the reviewers. Editor’s Choice articles are based on recommendations by the scientific editors of MDPI journals from around the world. Editors select a small number of articles recently published in the journal that they believe will be particularly interesting to readers, or important in the respective research area. The aim is to provide a snapshot of some of the most exciting work published in the various research areas of the journal. Original Submission Date Received: . Active Journals Find a Journal Proceedings Series For Authors For Reviewers For Editors For Librarians For Publishers For Societies For Conference Organizers Open Access Policy Institutional Open Access Program Special Issues Guidelines Editorial Process Research and Publication Ethics Article Processing Charges Testimonials Preprints.org SciProfiles Encyclopedia Article Menu Subscribe SciFeed Recommended Articles Google Scholar on Google Scholar Table of Contents Find support for a specific problem in the support section of our website. Please let us know what you think of our products and services. Visit our dedicated information section to learn more about MDPI. JSmol Viewer Solving the vehicle routing problem with stochastic travel cost using deep reinforcement learning. 1. Introduction 2. preliminary, 2.1. vrp-stc, 2.2. reinforcement learning framework, 3.1. formulation of drl. State: Status s t = ( R t , C t ) is a part of the solution, for instance, G ( Q , q , R ) created at time step t . Here, R t (for t ≠ 0) is the group of customers receiving services, which includes all of the chosen customer locations up to step t , C t is the set of candidate nodes at step t , Q is the maximum capacity of each vehicle, q is the demand of customers. Action: Action a t indicates that at step t , the candidate node π t is chosen from the candidate node set C t and added to the service customer set R t . Transition: With the action a t , a modern fractional solution is obtained as the following state, i.e., s t+ 1 = ( R t+ 1 , C t+ 1 ). Within the updated state, R t+ 1 includes π t in addition to the nodes chosen so far, whereas C t+ 1 consists of the candidate nodes from C t with π t expelled. Reward: To minimize the total cost, we define the value of the objective function at step t as Obj t = min E( cost ), and the reward at step t as r t = Obj t−1 − Obj t . Policy: The strategy P θ is parameterized using θ within the GAT-AM model. At each step t , a candidate node is automatically chosen as the service customer node until all service customer nodes are chosen, resulting in the final solution π = { π 1 , π 2 , …, π n ,} generated by the policy. 3.3. Encoder 3.4. decoder, 3.5. algorithm. REINFORCE with Rollout Baseline number of epochs E, steps per epoch T, batch size B, significance α  Initialize θ, θ ← θ    epoch = 1, …, E       step = 1, …, T            Test (P , P ) < α       θ ← θ       3.6. Stochastic Travel Costs 4. experiments, 4.1. experimental settings, 4.2. baseline methods and evaluation metrics, 4.3. comparison analysis, 4.4. model convergence performance, 4.5. visualization, 5. conclusions. Algorithmic Refinement and Generalization: The model currently exhibits certain limitations. Enhancing the algorithm’s generalization capacity to accommodate a broader spectrum of environments and various problem scenarios represents a pivotal area for future investigation. Real-time Dynamic Planning: With the growing demand for practical applications, implementing real-time dynamic planning within the model to accommodate the evolving logistics demands and traffic conditions is a pressing challenge awaiting resolution. Multi-objective Optimization: The present model primarily focuses on minimizing the total travel cost. In the future, exploration could be extended to achieve a balance among multiple objectives, such as service level assurance and minimizing environmental impacts. Author Contributions Data availability statement, acknowledgments, conflicts of interest. Khalil, E.; Dai, H.; Zhang, Y.; Dilkina, B.; Song, L. Learning combinatorial optimization algorithms over graphs. Adv. Neural Inf. Process. Syst. 2017 , 30 , 6348–6358. [ Google Scholar ] Bengio, Y.; Lodi, A.; Prouvost, A. Machine learning for combinatorial optimization: A methodological tour d’horizon. Eur. J. Oper. Res. 2021 , 290 , 405–421. [ Google Scholar ] [ CrossRef ] Glorot, X.; Bengio, Y. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, Sardinia, Italy, 13–15 May 2010; pp. 249–256. [ Google Scholar ] Sutton, R.S.; Barto, A.G. Reinforcement Learning: An Introduction. IEEE Trans. Neural Netw. 1998 , 9 , 1054. [ Google Scholar ] [ CrossRef ] Silver, D.; Schrittwieser, J.; Simonyan, K.; Antonoglou, I.; Huang, A. Mastering the game of Go without human knowledge. Nature 2017 , 550 , 354–359. [ Google Scholar ] [ CrossRef ] [ PubMed ] Mnih, V.; Kavukcuoglu, K.; Silver, D.; Rusu, A.A.; Veness, J.; Bellemare, M.G.; Graves, A.; Riedmiller, M.; Fidjeland, A.K.; Ostrovski, G. Human-level control through deep reinforcement learning. Nature 2015 , 518 , 529–533. [ Google Scholar ] [ CrossRef ] Karimi-Mamaghan, M.; Mohammadi, M.; Meyer, P.; Karimi-Mamaghan, A.M.; Talbi, E.-G. Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art. Eur. J. Oper. Res. 2022 , 296 , 393–422. [ Google Scholar ] [ CrossRef ] Watkins, C.J.; Dayan, P. Q-learning. Mach. Learn. 1992 , 8 , 279–292. [ Google Scholar ] [ CrossRef ] Williams, R.J. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn. 1992 , 8 , 229–256. [ Google Scholar ] [ CrossRef ] Konda, V.; Tsitsiklis, J. Actor-critic algorithms. Adv. Neural Inf. Process. Syst. 1999 , 12 , 1008–1014. [ Google Scholar ] Silver, D.; Lever, G.; Heess, N.; Degris, T.; Wierstra, D.; Riedmiller, M. Deterministic policy gradient algorithms. In Proceedings of the International Conference on Machine Learning, Beijing, China, 22–24 June 2014; pp. 387–395. [ Google Scholar ] Schulman, J.; Levine, S.; Abbeel, P.; Jordan, M.; Moritz, P. Trust region policy optimization. In Proceedings of the International Conference on Machine Learning, Lille, France, 7–9 July 2015; pp. 1889–1897. [ Google Scholar ] Lillicrap, T.P.; Hunt, J.J.; Pritzel, A.; Heess, N.; Erez, T.; Tassa, Y.; Silver, D.; Wierstra, D. Continuous control with deep reinforcement learning. arXiv 2015 , arXiv:1509.02971. [ Google Scholar ] Schulman, J.; Wolski, F.; Dhariwal, P.; Radford, A.; Klimov, O. Proximal policy optimization algorithms. arXiv 2017 , arXiv:1707.06347. [ Google Scholar ] Babaeizadeh, M.; Frosio, I.; Tyree, S.; Clemons, J.; Kautz, J. Reinforcement learning through asynchronous advantage actor-critic on a gpu. arXiv 2016 , arXiv:1611.06256. [ Google Scholar ] Levine, S.; Finn, C.; Darrell, T.; Abbeel, P. End-to-end training of deep visuomotor policies. J. Mach. Learn. Res. 2016 , 17 , 1334–1373. [ Google Scholar ] Deng, Y.; Bao, F.; Kong, Y.; Ren, Z.; Dai, Q. Deep direct reinforcement learning for financial signal representation and trading. IEEE Trans. Neural Netw. Learn. Syst. 2016 , 28 , 653–664. [ Google Scholar ] [ CrossRef ] Zheng, G.; Zhang, F.; Zheng, Z.; Xiang, Y.; Yuan, N.J.; Xie, X.; Li, Z. DRN: A deep reinforcement learning framework for news recommendation. In Proceedings of the 2018 World Wide Web Conference, Lyon, France, 23–27 April 2018; pp. 167–176. [ Google Scholar ] Silver, D.; Huang, A.; Maddison, C.J.; Guez, A.; Sifre, L.; Van Den Driessche, G.; Schrittwieser, J.; Antonoglou, I.; Panneershelvam, V.; Lanctot, M. Mastering the game of Go with deep neural networks and tree search. Nature 2016 , 529 , 484–489. [ Google Scholar ] [ CrossRef ] [ PubMed ] Silver, D.; Hubert, T.; Schrittwieser, J.; Antonoglou, I.; Lai, M.; Guez, A.; Lanctot, M.; Sifre, L.; Kumaran, D.; Graepel, T. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science 2018 , 362 , 1140–1144. [ Google Scholar ] [ CrossRef ] Schrittwieser, J.; Antonoglou, I.; Hubert, T.; Simonyan, K.; Sifre, L.; Schmitt, S.; Guez, A.; Lockhart, E.; Hassabis, D.; Graepel, T. Mastering atari, go, chess and shogi by planning with a learned model. Nature 2020 , 588 , 604–609. [ Google Scholar ] [ CrossRef ] Vinyals, O.; Fortunato, M.; Jaitly, N. Pointer networks. Adv. Neural Inf. Process. Syst. 2015 , 28 . [ Google Scholar ] [ CrossRef ] Lu, H.; Zhang, X.; Yang, S. A learning-based iterative method for solving vehicle routing problems. In Proceedings of International Conference on Learning Representations. Available online: https://openreview.net/forum?id=BJe1334YDH (accessed on 13 August 2024). Manchanda, S.; Mittal, A.; Dhawan, A.; Medya, S.; Ranu, S.; Singh, A. Learning heuristics over large graphs via deep reinforcement learning. arXiv 2019 , arXiv:1903.03332. [ Google Scholar ] Mazyavkina, N.; Sviridov, S.; Ivanov, S.; Burnaev, E. Reinforcement learning for combinatorial optimization: A survey. Comput. Oper. Res. 2021 , 134 , 105400. [ Google Scholar ] [ CrossRef ] Cappart, Q.; Chételat, D.; Khalil, E.B.; Lodi, A.; Morris, C.; Veličković, P. Combinatorial optimization and reasoning with graph neural networks. J. Mach. Learn. Res. 2023 , 24 , 1–61. [ Google Scholar ] Kool, W.; Van Hoof, H.; Welling, M. Attention, learn to solve routing problems! arXiv 2018 , arXiv:1803.08475. [ Google Scholar ] Nowak, A.; Villar, S.; Bandeira, A.S.; Bruna, J. A note on learning algorithms for quadratic assignment with graph neural networks. Stat 2017 , 1050 , 22. [ Google Scholar ] Li, Z.; Chen, Q.; Koltun, V. Combinatorial optimization with graph convolutional networks and guided tree search. Adv. Neural Inf. Process. Syst. 2018 , 31 . Available online: https://proceedings.neurips.cc/paper_files/paper/2018/file/8d3bba7425e7c98c50f52ca1b52d3735-Paper.pdf (accessed on 13 August 2024). Drori, I.; Kharkar, A.; Sickinger, W.R.; Kates, B.; Ma, Q.; Ge, S.; Dolev, E.; Dietrich, B.; Williamson, D.P.; Udell, M. Learning to solve combinatorial optimization problems on real-world graphs in linear time. In Proceedings of the 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), Miami, FL, USA, 14–17 December 2020; pp. 19–24. [ Google Scholar ] Lodi, A.; Mossina, L.; Rachelson, E. Learning to handle parameter perturbations in combinatorial optimization: An application to facility location. EURO J. Transp. Logist. 2020 , 9 , 100023. [ Google Scholar ] [ CrossRef ] Xidias, E.; Zacharia, P.; Nearchou, A. Intelligent fleet management of autonomous vehicles for city logistics. Appl. Intell. 2022 , 52 , 18030–18048. [ Google Scholar ] [ CrossRef ] Luo, H.; Dridi, M.; Grunder, O. A branch-price-and-cut algorithm for a time-dependent green vehicle routing problem with the consideration of traffic congestion. Comput. Ind. Eng. 2023 , 177 , 109093. [ Google Scholar ] [ CrossRef ] Bai, R.; Chen, X.; Chen, Z.-L.; Cui, T.; Gong, S.; He, W.; Jiang, X.; Jin, H.; Jin, J.; Kendall, G. Analytics and machine learning in vehicle routing research. Int. J. Prod. Res. 2023 , 61 , 4–30. [ Google Scholar ] [ CrossRef ] Puterman, M.L. Markov decision processes. Handb. Oper. Res. Manag. Sci. 1990 , 2 , 331–434. [ Google Scholar ] Veličković, P.; Cucurull, G.; Casanova, A.; Romero, A.; Lio, P.; Bengio, Y. Graph attention networks. arXiv 2017 , arXiv:1710.10903. [ Google Scholar ] He, K.; Zhang, X.; Ren, S.; Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Las Vegas, NV, USA, 27–30 June 2016; pp. 770–778. [ Google Scholar ] Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A.N.; Kaiser, Ł.; Polosukhin, I. Attention is all you need. arXiv 2017 , arXiv:1706.03762. [ Google Scholar ] Rennie, S.J.; Marcheret, E.; Mroueh, Y.; Ross, J.; Goel, V. Self-critical sequence training for image captioning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Honolulu, HI, USA, 21–26 July 2017; pp. 7008–7024. [ Google Scholar ] Liu, Z.; Li, X.; Khojandi, A. The flying sidekick traveling salesman problem with stochastic travel time: A reinforcement learning approach. Transp. Res. Part E Logist. Transp. Rev. 2022 , 164 , 102816. [ Google Scholar ] [ CrossRef ] Kingma, D.P.; Ba, J. Adam: A method for stochastic optimization. arXiv 2014 , arXiv:1412.6980. [ Google Scholar ] Helsgaun, K. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems. Rosk. Rosk. Univ. 2017 , 12 , 966–980. [ Google Scholar ] Bello, I.; Pham, H.; Le, Q.V.; Norouzi, M.; Bengio, S. Neural combinatorial optimization with reinforcement learning. arXiv 2016 , arXiv:1611.09940. [ Google Scholar ] Click here to enlarge figure VRP20 VRP50 VRP100 Method Obj Gap Time Obj Gap Time Obj Gap Time LKH3 6.14 0.00% (7 h) 10.38 0.00% (7 h) 15.65 0.00% (13 h) OR Tools 6.42 4.84% (-) 11.22 8.12% (-) 17.14 9.34% (-) AM (greedy) 6.40 4.57% (1 s) 10.98 5.78% (3 s) 16.80 7.34% (8 s) AM (sampling) 6.25 2.12% (6 m) 10.62 2.31% (28 m) 16.23 3.72% (2 h) GAT-AM (greedy) 6.35 3.76% (1 s) 10.88 4.82% (2 s) 16.13 2.89% (5 s) GAT-AM (sampling) 6.18 0.98% (5 m) 10.51 1.25% (11 m) 15.89 1.53% (23 m) VRP-STC20 VRP-STC50 VRP-STC100 Method Obj Time Obj Time Obj Time AM (greedy) 9.54 (2 s) 16.36 (8 s) 25.08 (23 s) AM (sampling) 9.31 (13 m) 15.98 (1 h) 24.68 (4.5 h) GAT-AM (greedy) 9.34 (2 s) 16.01 (6 s) 24.67 (13 s) GAT-AM (sampling) 9.18 (7 m) 15.68 (16 m) 24.36 (46 m) The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content. Share and Cite Cai, H.; Xu, P.; Tang, X.; Lin, G. Solving the Vehicle Routing Problem with Stochastic Travel Cost Using Deep Reinforcement Learning. Electronics 2024 , 13 , 3242. https://doi.org/10.3390/electronics13163242 Cai H, Xu P, Tang X, Lin G. Solving the Vehicle Routing Problem with Stochastic Travel Cost Using Deep Reinforcement Learning. Electronics . 2024; 13(16):3242. https://doi.org/10.3390/electronics13163242 Cai, Hao, Peng Xu, Xifeng Tang, and Gan Lin. 2024. "Solving the Vehicle Routing Problem with Stochastic Travel Cost Using Deep Reinforcement Learning" Electronics 13, no. 16: 3242. https://doi.org/10.3390/electronics13163242 Article Metrics Article access statistics, further information, mdpi initiatives, follow mdpi. Subscribe to receive issue release notifications and newsletters from MDPI journals COMM: ACM SIGCOMM August 2024 Hector Cancela , Eduardo Cerqueira , Eric Gamess , Daniel Guidoni Association for Computing Machinery United States Save to Binder No abstract available. Proceeding Downloads Multicast routing, modulation level, and spectrum assignment in elastic optical networks - a genetic algorithm and light-hierarchy approach. Luis Cubilla , Diego P. Pinto-Roa , Jose Colbes Multicast transmission in elastic optical networks (EON) is a central problem. When EON admits modulation schemes, the multicast problem is called multicast routing and modulation level and spectrum assignment (MRMLSA). Whenever EON supports light-... Implementation of a Low-cost AIS Transmitter based on SDR Romina García , Máximo Pirri , Gonzalo Belcredi , Claudina Rattaro The Automatic Identification System (AIS) was developed primarily to enhance maritime safety. While large ships are mandated to equip AIS stations, the situation differs for smaller vessels, particularly recreational ones, as AIS technology is not ... A Study of the Resilience of the Mosquitto MQTT Broker Running on Raspberry Pi Against Fuzzy DDoS Attacks Jhanvi Patel , Eric Gamess The Message Queuing Telemetry Transport (MQTT) protocol is widely utilized for the Internet of Things (IoT) and other sectors. Due to its popularity, the vulnerabilities within MQTT implementations have attracted attention from malicious actors. This ... Intelligent Malware Detection Integrating Cloud and Fog Computing Carlos H. Paiva , Mateus F. Nascimento , Renan L. Rodrigues , Rafael L. Gomes Currently, there is a noticeable increase in the digitization of services provided by companies and government agencies, and there is also an increase in concern about the cybersecurity aspects of corporate and personal data due to the rise of malicious ... Connection Management Using Automated Firewall Based on Threat Intelligence Marcus A. Costa , Yago M. Costa , Yanne O. Almeida , Francisco J. Cardoso , In the context of constantly evolving cyber threats, the need for dynamic and adaptive security solutions is imperative. The approach of Threat Intelligence is crucial, as it aims to collect, analyze, and interpret relevant information about digital ... Metaverse IoT Confluence: Architecture Overview, Challenges and Requirements Jeferson Rodrigues Cotrim , Cintia Borges Margi Metaverse is a virtual universe connecting virtual worlds and entities to the real world. The Metaverse applications are based on real world data to provide immersion and integration to users. IoT is a network interconnection paradigm designed for ... Development of New Radio Schedulers in OpenAirInterface Pablo Andrés Vázquez , Walter Piastri , Wilder Pena , Lucas Ingles , This paper presents an analysis, implementation, and validation of new radio schedulers within the OpenAirInterface (OAI) framework. Leveraging the flexibility of OAI, we scrutinize existing MAC layer functionalities and propose enhancements through the ... Hector Cancela Search about this author Eduardo Cerqueira Search about this author Eric Gamess Search about this author Daniel Guidoni Search about this author Recommendations Ubimob '05: proceedings of the 2nd french-speaking conference on mobility and ubiquity computing, lanc '11: proceedings of the 6th latin america networking conference, ubimob '08: proceedings of the 4th french-speaking conference on mobility and ubiquity computing, export citations. Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download Download citation Copy citation We are preparing your search results for download ... We will inform you here when the file is ready. Your file of search results citations is now ready. Your search export query has expired. Please try again. 175 IMAGES (PDF) Traffic Routing Algorithm for Road Network Flow for the generic Routing and Wavelength Assignment algorithm with Routing Algorithm Routing Algorithms ROUTING ALGORITHM -INTRODUCTION Flowchart of the routing and wavelength assignment algorithm employed COMMENTS Assignment 1: Routing Simulations The purpose of this assignment is to reinforce students' understanding of distance-vector and link-state routing. This assignment uses a simulator rather than having students write an actual routing daemon implementing RIP or OSPF to avoid as much implementation overhead as possible and focus on the algorithms themselves. Implementation of routing algorithms, both distance vector and ... Nearly all intradomain routing algorithms used in real-world networks fall into one of two categories, distance-vector or link-state. In this assignment, you will implement distributed distance-vector and link-state routing algorithms in Python and test them with a provided network simulator. distance-vector-routing · GitHub Topics · GitHub logbook distance-vector-routing gbn computer-networks assignment-solutions alternating-bit-protocol poison-reverse postgraduate-subjects wireshark-lab Updated Jul 13, ... distance vector routing algorithm Implementation in C . networking network-programming distance-vector-routing Updated Nov 25, 2020; C; AbdullahArean / HandsOnNetworking Assignment 2: Routing Simulations The purpose of this assignment is to reinforce students' understanding of distance-vector routing. This assignment uses a simulator rather than having students write an actual routing daemon implementing RIP or OSPF to avoid as much implementation overhead as possible and focus on the algorithms themselves. CS519: Assignment 4; Link-state routing Link-State Routing. Assignment designed by Snorri Gylfason. Goal. The two fundamental routing algorithms in packet-switched networks are distance-vector and link-state. ... Grading Your implementation will be tested on a different network topology. It will be of the same, or smaller, size (so your next-hop table can be of size 12), with the ... routing-algorithm · GitHub Topics · GitHub The Vehicle Monitoring And Routing System (VMARS) makes use of GPS to provide the exact location of the vehicle. It allows a parent to monitor the vehicle in real-time using a GPS-based device possessed by its driver. It is also capable of finding the shortest route to reach the destination passing through all the checkpoints which uses our ... Assignment 3 Overview. In this assignment, you will implement a distributed, asynchronous, distance-vector routing algorithm based on the Bellman-Ford algorithm that we learned in the lecture. The network is modelled as an undirected graph with a certain number of nodes. Each link in the graph is associated with a positive integer cost. Programming Assignment: Implementing an Algorithm Lab 2: Implementing a Routing Algorithm Overview In this lab, you will be writing a "distributed" set of procedures that implement a distributed asynchronous distance vector routing for the network shown in Figure 1. Figure 1: Network topology and link costs for DV routing lab The Basic Assignment A summary of the routing algorithm Routing algorithms are critical for determining the most efficient path for data transmission between nodes in a network. The efficiency, reliability, and scalability of a network heavily rely on the choice and optimization of its routing algorithm. ... "Design and implementation of fisheye routing protocol for mobile ad hoc networks," none ... Classification of Routing Algorithms The routing algorithms can be classified as follows: Adaptive Algorithms. Non-Adaptive Algorithms. Hybrid Algorithms. Types of Routing Algorithm. 1. Adaptive Algorithms. These are the algorithms that change their routing decisions whenever network topology or traffic load changes. The changes in routing decisions are reflected in the topology ... Routing Algorithms Routing algorithms play a crucial role in the efficient transmission of data within computer networks by determining the optimal paths for packet forwarding. This paper presents a comprehensive exploration of routing algorithms, focusing on their fundamental principles, classification, challenges, recent advancements, and practical applications ... Unicast Routing Major Protocols of Unicast Routing. Distance Vector Routing: Distance-Vector routers use a distributed algorithm to compute their routing tables. Link-State Routing: Link-State routing uses link-state routers to exchange messages that allow each router to learn the entire network topology. Path-Vector Routing: It is a routing protocol that maintains the path that is updated dynamically. COS 226 Programming Assignment: Map Routing Map Routing. Implement the classic Dijkstra's shortest path algorithm and optimize it for maps. Such algorithms are widely used in geographic information systems (GIS) includingMapQuest and GPS-based car navigation systems. Maps. For this assignment we will be working with maps, orgraphs whose vertices are points in the plane and are ... Routing algorithm implementations · GitHub Routing algorithm implementations. Raw. gistfile1.txt. (Dijkstra and plain A* are generally not included here as there are thousands of. implementations, though I've made an exception for rare Ruby and Crystal versions, and for Thor, Mapzen's enhanced A*. PDF A Multithreaded Initial Detailed Routing Algorithm Considering Global This paper presents a novel initial detailed routing algorithm to consider industrial design-rule constraints and optimize the total wirelength and via count. Our algorithm consists of three major stages: (1) an efective pin-access point generation method to identify valid points to model a complex pin shape, (2) a via-aware track assignment ... Computer Network An adaptive routing algorithm is also known as dynamic routing algorithm. This algorithm makes the routing decisions based on the topology and network traffic. The main parameters related to this algorithm are hop count, distance and estimated transit time. An adaptive routing algorithm can be classified into three parts: Centralized algorithm ... GitHub cppRouting is an R package which provide routing algorithms (shortest paths/distances, isochrones) and traffic assignment solvers on non-negative weighted graphs. cppRouting is characterized by :. its ability to work on large road graphs (country/continent scale) its large choice of one-to-one shortest path algorithms; its implementation of contraction hierarchies and associated routing algorithms Routing and wavelength assignment The second approach is to consider both route selection and wavelength assignment jointly. First routing, then wavelength assignment Routing algorithms Fixed path routing. Fixed path routing is the simplest approach to finding a lightpath. The same fixed route for a given source and destination pair is always used. What is Routing? Routing is a fundamental concept in computer science that allows every network device across the world to share data across the internet. Here, the shortest path is selected by the routing algorithms when routing a data packet. So, the Routing Algorithms select the shortest path based on metrics like - hop count, delay, bandwidth, etc. PDF ROUTING AND WAVELENGTH ASSIGNMENT (RWA): OVERVIEW through the efforts of routing and wavelength assignment schemes that can adapt to network size and dimension. An optimal or near-optimal deployment of transponders, along with a properly designed routing and wavelength assignment strategy, is essential for maximizing and economizing the network resource utilization. Programming Assignment 2: Implementing a Distance Vector Routing Algorithm Programming Assignment 2 (130 points) Due Tuesday, November 30, 11:59 PM. Implementing a Distance Vector Routing Algorithm. This assignment is identical to the programming assignment given in Chapter 4 of Kurose-Ross's text "Computer Networking: A Top-Down Approach Featuring the Internet", 3rd edition. A few minor changes have been made for our ... Programming Assignment 4: Implementing an Algorithm Programming Assignment 3: Distributed Simulation of Distance Vector Routing protocol (Assigned: Nov. 4th, Due: Nov. 18th midnight, Late submission by Nov. 24th with 20 points off) Overview. In this lab, you will be writing a "distributed" set of procedures that implement a distributed asynchronous distance vector routing for the network shown ... Multicast Routing, Modulation Level, and Spectrum Assignment in Elastic Luis Víctor Maidana Benítez, Melisa María Rosa Villamayor Paredes, José Colbes, César F. Bogado-Martínez, Benjamin Barán, and Diego P. Pinto-Roa. 2023. Routing, Modulation Level, and Spectrum Assignment in Elastic Optical Networks. A Serial Stage Approach with Multiple Sub-Sets of Requests Based on Integer Linear Programming. The Cisco router must be configured to enable routing protocol Security Technical Implementation Guides (STIGs) that provides a methodology for standardized secure installation and maintenance of DOD IA and IA-enabled devices and systems. The Cisco router must be configured to enable routing protocol authentication using FIPS 198-1 algorithms with keys not exceeding 180 days of lifetime. Electronics The Vehicle Routing Problem (VRP) is a classic combinatorial optimization problem commonly encountered in the fields of transportation and logistics. This paper focuses on a variant of the VRP, namely the Vehicle Routing Problem with Stochastic Travel Cost (VRP-STC). In VRP-STC, the introduction of stochastic travel costs increases the complexity of the problem, rendering traditional ... Proceedings of the 2024 Latin America Networking Conference Multicast Routing, Modulation Level, and Spectrum Assignment in Elastic Optical Networks - A Genetic Algorithm and Light-hierarchy Approach ... (MQTT) protocol is widely utilized for the Internet of Things (IoT) and other sectors. Due to its popularity, the vulnerabilities within MQTT implementations have attracted attention from malicious ... Open Source Reinforcement Learning Framework for Routing and ... RSA-RL is an open source reinforcement learning framework for routing and spectrum assignment (RSA) in Python using PyTorch and PFRL. Installation To install rsa-rl, use pip . assignment essay homework phd report resume review speech thesis