Assignment 2
Routing simulations, distance vector, is due thursday, february 23 (midnight), description, obtaining, building, and running the simulator.
![](http://writinghelp.online/777/templates/cheerup/res/banner1.gif)
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.
![routing algorithm implementation assignment Refer to caption](https://arxiv.org/extracted/5428891/Shortest_path_with_direct_weights.png)
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.
![routing algorithm implementation assignment Refer to caption](https://arxiv.org/extracted/5428891/Routing-example-for-dimension-order-routing-on-a-2-D-mesh.png)
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.
![routing algorithm implementation assignment Refer to caption](https://arxiv.org/extracted/5428891/flooding.png)
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.
![routing algorithm implementation assignment Refer to caption](https://arxiv.org/extracted/5428891/Example-of-Distance-Vector-Routing.png)
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.
![routing algorithm implementation assignment Refer to caption](https://arxiv.org/extracted/5428891/linkstate.jpg)
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.
![routing algorithm implementation assignment Refer to caption](https://arxiv.org/extracted/5428891/wsnrouting-protocols-energy-efficient-routing-3-2048.png)
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.
![routing algorithm implementation assignment Refer to caption](https://arxiv.org/x1.png)
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.
Nodes | Protocol | FDN | FDN Ratio | AND | AND Ratio |
---|---|---|---|---|---|
100 | LEACH | 42 | 1 | 613 | 1 |
Cell-LEACH | 129 | 3.14 | 501 | 0.82 | |
Multi-LEACH | 107 | 2.6 | 597 | 0.97 | |
EESRA | 363 | 8.85 | 819 | 1.33 | |
200 | LEACH | 41 | 1 | 570 | 1 |
Cell-LEACH | 122 | 2.97 | 490 | 0.86 | |
Multi-LEACH | 123 | 3 | 559 | 0.97 | |
EESRA | 330 | 8.05 | 826 | 1.45 | |
300 | LEACH | 41 | 1 | 585 | 1 |
Cell-LEACH | 129 | 2.97 | 505 | 0.86 | |
Multi-LEACH | 122 | 2.97 | 597 | 1 | |
EESRA | 322 | 7.85 | 872 | 1.49 | |
400 | LEACH | 42 | 1 | 581 | 1 |
Cell-LEACH | 129 | 3.14 | 507 | 0.87 | |
Multi-LEACH | 121 | 2.95 | 597 | 1.01 | |
EESRA | 312 | 7.61 | 883 | 1.52 |
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:
(1) |
(2) |
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.
![routing algorithm implementation assignment Refer to caption](https://arxiv.org/x5.png)
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.
![routing algorithm implementation assignment routing algorithm implementation assignment](https://production-media.paperswithcode.com/thumbnails/paper/2403.11228.jpg)
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.
TASK | DATASET | MODEL | METRIC NAME | METRIC VALUE | GLOBAL RANK | REMOVE |
---|
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.
(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*. ) | |
A* Ruby https://github.com/georgian-se/shortest-path | |
A* Crystal https://github.com/petoem/a-star.cr | |
A* (bidirectional with shortcuts) C++ https://github.com/valhalla/valhalla | |
NBA* JS https://github.com/anvaka/ngraph.path | |
NBA* Java https://github.com/coderodde/GraphSearchPal | |
NBA* Java https://github.com/coderodde/FunkyPathfinding | |
NBA* C++ https://github.com/vlarmet/cppRouting | |
NBA* (Parallel) C++ https://github.com/janhsimon/PNBAStar | |
NBA* (Parallel) Python https://github.com/rizasif/heuristic-search-2d | |
Multi-Level Dijkstra (CRP) C++ https://github.com/michaelwegner/CRP | |
Multi-Level Dijkstra C++ https://github.com/Project-OSRM/osrm-backend | |
Multi-Level Dijkstra (SARA) Java https://github.com/cc-routing/routing-sara | |
Pruned Highway Labelling C https://github.com/kawatea/pruned-highway-labeling | |
Pruned Landmark Labelling C++ https://github.com/iwiwi/pruned-landmark-labeling | |
ALT Java https://github.com/graphhopper/graphhopper | |
ALT Java https://github.com/jgrapht/jgrapht | |
ALT Python https://github.com/ryanpon/pathfinding-animator | |
Contraction Hierarchies Java https://github.com/graphhopper/graphhopper | |
Contraction Hierarchies Java https://github.com/michaeltandy/contraction-hierarchies | |
Contraction Hierarchies Java https://github.com/navjindervirdee/Advanced-Shortest-Paths-Algorithms | |
Contraction Hierarchies JS https://www.mjt.me.uk/posts/contraction-hierarchies/ | |
Contraction Hierarchies JS https://github.com/royhobbstn/contraction-hierarchy-js | |
Contraction Hierarchies C++ http://algo2.iti.kit.edu/source/contraction-hierarchies-20090221.tgz | |
Contraction Hierarchies C++ https://code.google.com/archive/p/monav/source/default/source | |
Contraction Hierarchies C++ https://github.com/Project-OSRM/osrm-backend | |
Contraction Hierarchies Java https://github.com/cc-routing/routing | |
Contraction Hierarchies C# https://github.com/itinero/routing | |
Contraction Hierarchies Rust https://github.com/easbar/fast_paths | |
Contraction Hierarchies Go https://github.com/LdDl/ch | |
Contraction Hierarchies Go https://github.com/nfleet/via | |
Contraction Hierarchies C++ https://github.com/vlarmet/cppRouting | |
Contraction Hierarchies Go https://github.com/s3131212/TNR-CH | |
Weak Contraction Hierarchies C++ https://github.com/tim3z/weakch | |
Customisable Contraction Hierarchies C++ https://github.com/RoutingKit/RoutingKit | |
Time-Dependent Contraction Hierarchies C++ https://github.com/GVeitBatz/KaTCH | |
Highways Hierarchies Java https://github.com/biafra23/mapsforge/tree/master/src/org/mapsforge/android/routing/blockedHighwayHierarchies | |
PHAST C++ https://github.com/vlarmet/cppRouting | |
Transit Node Routing Go https://github.com/s3131212/TNR-CH |
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
![routing algorithm implementation assignment Javatpoint Logo](https://static.javatpoint.com/images/logo/jtp-logo3.png)
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
IMAGES
COMMENTS
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.
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.
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
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.
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 ...
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 ...
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.
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
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 ...
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 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 ...
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.
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. 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*.
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 ...
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 ...
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
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.
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.
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 (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 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 ...
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.
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.
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 ...
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 ...
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 .