Member Avatar for aminit

Hello all dear friends :

I want to ask u about the Shortest path for routing , I want to make a project to calculate the shortest path for send the packets , so what's your suggestion ?? and can I make an algorithm to calculate the shortest path depending on the bandwith?

Thanks in advance

  • 3 Contributors
  • 6 Replies
  • 192 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by brandonrunyon

Dani AI

Generated

— two related but different design choices you need to pick before coding: do you want to (A) choose the path that gives the largest end-to-end throughput (maximize the bottleneck link), or (B) treat bandwidth as one component of a numeric cost so that you minimize a single aggregated cost? As and pointed out, this is classic graph theory — the choice changes both the algorithm and the trade-offs (throughput vs latency vs hop count).

If your goal is maximum throughput, implement the "widest path" (maximin) variant. It is a small modification of Dijkstra: keep a capacity value per node (best bottleneck so far) and always expand the node with the largest capacity. Example pseudocode:

# widest-path (maximizes minimum bandwidth along the path)
for each node v:
  cap[v] = 0
cap[source] = INF
PQ = max-heap keyed by cap
while PQ not empty:
  u = pop_max(PQ)
  for each edge (u,v) with bandwidth b:
    newcap = min(cap[u], b)
    if newcap > cap[v]:
      cap[v] = newcap
      prev[v] = u
      update PQ

If you need multiple metrics (bandwidth + delay + reliability) the problem becomes multi-constraint routing and is generally NP-hard. Practical approaches: (1) compute k-shortest paths (Yen/Eppstein) and pick the first that meets constraints, (2) use heuristics / Lagrangian relaxation to combine metrics into a single tunable cost, or (3) perform explicit traffic-engineering (pick and install candidate paths). For the "hybrid" idea you mentioned, note that real networks mix protocols by route redistribution and by protocols that blend behaviors (EIGRP is often described this way). Redistribution requires metric translation, route tags and administrative-distance choices to avoid loops — design those pieces explicitly.

Project plan (practical): model the network as a graph with attributes (bandwidth, delay), implement plain Dijkstra (cost-based), widest-path, and a k-shortest routine; run on random and hand-crafted topologies; log convergence, path choice, and simple throughput/latency estimates. Start small, verify correctness on tiny graphs, then scale.

Recommended Answers

All 6 Replies

Member Avatar for aminit

Thx for your reply , I want to ask you another questiom , in these days the using of dynamic routing has been increased in data transmission security , Distance vector is one of the algorithms that used to do that purpose , In fact there are another algorithms like "Link state" algorithm but each one of them has it special use , so it's possible to make a merge between 2 algorthims (like hyprid) ?

Member Avatar for ryan461

I know Cisco routers support route distribution i believe its called. So you could have one network EIGRP, and the next network OSPF. Or one being RIP, or another OSPF. This is typically not done unless there's a reason for it. Most people as far as I know praise OSPF as its not Cisco dependent, and doesnt have the limits of RIP.

Member Avatar for aminit

thx again for the reply ,actually maybe each one of them has it's own features that cann't exist in the other , let's assume that EIGRP it's easy to implement but it has weak security , and OSPF it has a strong secutiy but its complex , so my idea was making a merge system can have "some" of thier architectural ...

Member Avatar for ryan461

well EIGRP is proprietary so cant really look at that. For feature differences theyre fairly minimal between protocols

Member Avatar for brandonrunyon

This all falls under the category of Graph Theory... no?

I would imagine looking into path finding algorithms like Dijsktra's would be a good place to focus on since so many routers use it.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.