Questions tagged [routing]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
41 views

Count-to-infinity avoidance techniques and hold-down timeout based question

I am trying to understand count-to-infinity avoidance techniques, and came across this topology. Now, suppose the interface eth1 on R1 has gone bad, and assuming that split horizon, triggered updates ...
user avatar
0 votes
1 answer
124 views

why use bellman-ford instead of Dijstra in RIP routing?

The RIP routing protocol was published in 1988 and uses Bellman-Ford algorithm to calculate shortest path. Also more recent version of RIP (RIPv2 and RIPng) use the same algorithm. The Djikstra ...
user avatar
  • 103
0 votes
1 answer
62 views

Why use private IP addresses in a LAN instead of MAC address

Why do we use a private IP address instead of using the MAC address in a local network? It makes sense that we have IP addresses for large networks where packets have to be routed because the IP ...
user avatar
  • 35
0 votes
0 answers
51 views

Find minimum cost cycle in graph G=(V,E) that visits vertices in required subset V′⊂V exactly once & covers edges in required subset E′⊂E atleast once

I have been researching about general routing problems and came across a problem similar to the Travelling Salesman Problem: Find a minimum cost cycle in a graph $G = (V, E)$ which visits vertices in ...
user avatar
2 votes
0 answers
62 views

Algorithm for stacked orders in food delivery (Pick up and deliveries)

I am trying to implement stacking orders While the most optimal solution would be to consider picking up orders from nearby restaurants that have similar food prep time AND nearby delivery locations. ...
user avatar
  • 121
0 votes
0 answers
17 views

The size of a router's forwarding table

Consider a home network. Say three computers, a network printer and an internet connection. The three computers and the network printer will use the router to communicate with each other. I am ...
user avatar
  • 349
1 vote
1 answer
67 views

Trying to understand a Router's Forwarding Table

I am trying to understand how a router's forward table works. As such, I am working on the following problem. Problem: A router’s forwarding table has the following entries. \begin{array} {|r|r|}\...
user avatar
  • 349
0 votes
0 answers
57 views

Routing with constraints

The following is the statement of the problem: There are 40 packets to be delivered in a day. Each packet needs to be delivered to a particular location. Apart from this, there are constraints also ...
user avatar
  • 1
1 vote
0 answers
45 views

Delivery problem, unsure which exact problem it is

I'm looking for guidance on how to reduce the following problem to a known problem or a suggestion for solving it altogether. Optimal / heuristic solutions or any other suggestions are greatly ...
user avatar
  • 51
1 vote
0 answers
26 views

An algorithm to find differences between routing paths

I need to come up with an algorithm that finds differences in the sequence of each product's routing (or sequence of processes). There are several processes aligned together and each process's been ...
user avatar
0 votes
2 answers
54 views

Route finding on a graph that must go through multiple edges

I have this graph It shows a graph of a map that has nodes and segments (or edges), with weights, that connect these nodes. Some of these segments have addresses on, and some of these addresses are ...
user avatar
0 votes
0 answers
21 views

Lowest cost path(s) between source and destination that collects required items

I have an undirected graph where each vertex is given some items from a set of items. My goal is to find the lowest cost path from my source vertex to destination vertex while collecting all such ...
user avatar
2 votes
1 answer
50 views

Raptor algorithm: find next best paths

I'm reading Microsoft's white paper "Round-Based Public Transit Routing" (the RAPTOR algorithm). What are the ways to find next best paths (path is a sequence of trips and transfers from source to ...
user avatar
  • 121
2 votes
0 answers
37 views

Finding multiple paths through a grid such that every grid square is equally used

Setup Here’s the setup: I have an $N$ x $N$ grid of tiles, and a list of $M$ agents that need to move across the grid. Each agent has its own start tile $S(a)$, end tile $E(a)$, and an exact number ...
user avatar
1 vote
1 answer
61 views

Multi-Path Length Minimization

I've been thinking about path planning and am trying to make good heuristics for cases with multiple agents. Suppose there are sets $S_i$ of coordinates in $\mathbb R^2$ or $\mathbb R^3$, each of the ...
user avatar
2 votes
1 answer
115 views

Mutli-Path Collision Avoidance

I need an algorithm which can do the following: Given some finite number of particles (circles) each with the same radius, and a list of prescribed points for each particle, find paths in $\mathbb{...
user avatar
1 vote
1 answer
34 views

Finding stages in routing algorithm

I have an undirected graph where I need to find routes of minimum cost in a point to multi-point, but where cost can be reduced by creating intermediate "packs" of routing terminals. I am currently ...
user avatar
  • 111
2 votes
2 answers
6k views

How do web browsers find out the MAC address?

While reading through my textbook, I discovered that if you want to access a particular web page, your web browser will find out the IP address of the web server that hosts the web page and try and ...
user avatar
  • 21
1 vote
1 answer
703 views

Finding path with specific length in weighted graph

Given a weighted, cyclic, directed graph and two nodes I am looking for a connecting path which total weight comes as near as possible to a specific value which is greater than the shortest path. ...
user avatar
0 votes
1 answer
116 views

In "multi hop" network, is computer => computer 0 hop or 1 hop?

Would this here, a computer sending information directly to another computer, count as 0 hops or 1 hop?
user avatar
  • 1
0 votes
0 answers
118 views

Shortest path for vehicle routing problem with alternative locations

I'm currently developing an algorithm that solves the vehicle routing problem with time windows and the possibility for clients to be delivered to multiple locations. Right now, I'm trying to find ...
user avatar
  • 1
2 votes
1 answer
80 views

How to solve cubing, batching, and routing problem together?

I am working on an order picking project, which requires to cube the items into several totes in a trolley, then batching the totes, followed by parallel aisle picking/routing. The input data has ...
user avatar
0 votes
0 answers
91 views

Intuition for the convergence of the distance vector routing protocols

What is an intuitive way to think about the convergence of the distance vector routing algorithm? According to Wikipedia: Distance-vector routing protocols use the Bellman–Ford algorithm and Ford–...
user avatar
1 vote
0 answers
33 views

Routing a DAG through 5 consecutive butterfly networks

I have two questions concerning the paper Nearly linear-size holographic proofs. In the second paragraph of section 6, A Graph Coloring Problem, it is claimed that Using standard packet-routing ...
user avatar
1 vote
0 answers
44 views

Delivering to two or more locations in one go while respecting deadlines?

Assume that I have a business where people can place product orders. Each order must be delivered within a time limit, say $x$ minutes. I need 15 minutes to make each product. However, multiple ...
user avatar
  • 152
1 vote
1 answer
85 views

Combinatorial Optimization: Shortest distance given sets of drivers and riders

Problem: I have 2 sets, one of drivers and one of riders. All my participants need to reach one common destination. I wish to calculate the shortest combined distance in order for all participant to ...
user avatar
1 vote
0 answers
109 views

How do distributed algorithms for shortest path finding handle negative cycles?

I am searching the web for an answer to this question, but I have only found answers for non-distributed algorithms. I am interested in this for its application to Distance Vector routing.
user avatar
  • 167
3 votes
1 answer
2k views

Distance Vector Routing Example

Consider a network with five nodes, N1 to N5, as shown as below. The network uses a Distance Vector Routing protocol. Once the routes have been stabilized, the distance vectors at different nodes are ...
user avatar
0 votes
1 answer
66 views

Seek to infer "correct" route from sequence of stops

Let us consider school buses. Let a 'Bus Route' be a sequence of bus stops travelled by a single school bus (day after day). Let a 'Bus Stop' be a combination of Latitude (Lat), Longitude (Lon) and ...
user avatar
2 votes
1 answer
1k views

Routing algorithm for train network

I am trying to analyse a weighted multi-graph which represents a snapshot of a rail network for a particular day. As such, the vertices of the graph can be considered stations and the weighted edges ...
user avatar
  • 121
1 vote
1 answer
315 views

Shortest Path using at most k colors

I have an edge-colored network, in which edges also have a length, and I am considering the problem of determining the shortest Path between a pair of nodes, with the additional constraint that the ...
user avatar
  • 63
1 vote
1 answer
76 views

Question regarding terminology used to describe Benes networks

I'm studying a routing problem on a cyclic butterfly network. The paper I am reading states that two properties of the cyclic butterfly network make it efficient for the routing algorithm it describes....
user avatar
0 votes
1 answer
219 views

A path modification problem in directed graphs

We start with a given finite directed graph. It could represent transitive relations such as: data transfer paths in social networks, transportation connections, etc. Let us use the notation A->B ...
user avatar
2 votes
1 answer
118 views

route and/or packing optimization algorithm

What type of problem would this question fall under, are there known algorithms/heuristics for it, what would be good resources to learn more about solving it? Given: a list of items each with a ...
user avatar
  • 21
1 vote
0 answers
2k views

How to use Clarke and Wright saving algorithm to afford heterogeneous fleet?

I want to solve Heterogeneous fleet in vehicle routing problem using the Clarke and Wright saving algorithm. After reading many literature I found two options: Explicit and early assignment for the ...
user avatar
4 votes
0 answers
109 views

Parallel bubble sorting on arbitrary graphs

Are there bubblesort-esque algorithms for sorting on arbitrary graphs? I'm working on a problem in which $k$ robots are placed randomly on a graph and have to reach their respective goals as quickly ...
user avatar
0 votes
0 answers
72 views

Planning interviews

This is real-world problem, but I need to model it with algorithm as I am going to implement it (probably with PostGIS and Google Maps). Problem is: Everyday I am receiving job offers, and I have to ...
user avatar
  • 101
1 vote
1 answer
80 views

How can simulated annealing be related to the vehicle routing problem?

I have been searching through internet how could simulated annealing to solve the vehicle routing problem, but didn't find anything that made it clear to me. Most of what I found are research papers ...
user avatar
0 votes
0 answers
38 views

Looking for algorithms context-aware to solve a Bicycle Routing Problem

I am conducting a study has the general objective to build a route recommendation system for bicycle users, able to suggest viable alternatives to dislocation in urban environments, with reference to ...
user avatar
0 votes
0 answers
98 views

How to avoid looping of packets while implementing k-shortest paths algorithm in Network Simulator-3?

I am trying to implement k-shortest paths algorithm in NS-3 for IPv4GlobalRoutingProtocol. I am concerned about how to avoid looping of packets. My implementation calculates k-shortest paths from ...
user avatar
3 votes
1 answer
510 views

Shortest path problem where edge weight depends on path taken

I am attempting to find the most efficient route to get from a source to a destination in a bus network. Each stop is a vertex in a graph, and each edge between vertices represents a route between ...
user avatar
2 votes
2 answers
2k views

Raptor Algorithm: Differences between trip and route

I'm reading Microsoft's white paper "Round-Based Public Transit Routing" (the RAPTOR algorithm). In this algorithm, there are some definitions that I don't understand: About trip: trip represents ...
user avatar
2 votes
0 answers
60 views

How to know for sure that a router is congested?

Suppose a router X is dropping packets. Another router A will investigate whether X is dropping packets due to congestion. What are the procedures that A should follow? A already knows X's buffer ...
user avatar
  • 21
2 votes
1 answer
230 views

Route planning for a car driver picking up people using public transport

We just had an interesting though for a routing algorithm for people carpooling. Imagine the following situation: Person 1 is driving with his car from the south of city A to city B far in the north. ...
user avatar
1 vote
0 answers
79 views

Best route around confirmed appts - Traveling Salesman Problem

First, I am not a programmer, but an end user. We are trying to come up with a solution to a TSP issue that is causing us SIGNIFICANT time being wasted "manually" routing. Here is the issue. We ...
user avatar
1 vote
2 answers
456 views

Algorithm for finding the best “route” of tasks

I have the following problem: Let's say I'm in a city with some friend we have a bunch of tasks to do. All persons start on a different position, for example (0/0), (10/5), (-20/0), ... , and every ...
user avatar
0 votes
2 answers
170 views

Listing all possible train routes [closed]

I'm interested whether there is the standard solution to the following problem. Some number of train routes is given: Route1: First City -> Next City -> ... -> Last City Route2: ... ... We need to ...
user avatar
  • 467
3 votes
1 answer
198 views

Unsplittable flow in capacitated networks

I have an undirected network with capacitated links/edges. Between some nodes unsplittable traffic has to be routed. All demands and capacities are known, but it is uncertain if all flows can be ...
user avatar
  • 131
0 votes
2 answers
868 views

Bellman–Ford negative path meaning

In the Bellman–Ford algorithm, what is the practical meaning of having a negative path between routers? I have tried searching the net but didn't find any data thanks Eli
user avatar
2 votes
0 answers
477 views

Optimal vehicle routing on map

Currently I am developing a piece of software that solves the vehicle routing problem. The task is the following: I have several vehicles along the town I have lots of destination points along the ...
user avatar
  • 131