Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Need some tips how to implement distance vector router algorithm

shortest path

  • Please log in to reply
6 replies to this topic

#1 thatsme

thatsme

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 218 posts

Posted 25 November 2011 - 02:56 AM

Hi. I have a task to implement distance vector router algorithm. It should send packets from sender to server. I have little clue what should I do. I don't ask code from you but I would like to get some tips on following problems:
1) I previuos tasks i had to make communication between sender and server by using sockets (sender -> server) . As i understand, in the current task routers happen to appear between sender and server (sender -> router -> server). Shold I create class Router and send packets to it's instances? If so, how to connect to Router's object? By using sockets?
2) How many routers do I need and why?
3) How many servers do i need? Why? is 1 enough?
4) How to calculate the shortest path to server? Is it ok, if class Sender knows all paths, their values, calculates shortest path using dijkstra algorithm and gives to packet some data structure containg sequence of routers to be passed while traveling to server?
5) Maybe someone could draw me simple class diagram?
  • 0

#2 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 25 November 2011 - 05:11 AM

Back up just a little bit: can you diagram what you're trying to calculate? Where will the information be located?
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#3 thatsme

thatsme

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 218 posts

Posted 25 November 2011 - 06:02 AM

Let's say there is a graph with values i need to calculate the shortest path from one point to another (i suppose, that point in this case is router). Where will the information be located? The packet with information is being sent from Sender class to Server class. While being sent the packet passes many routers. In the end, information will be located in server. My explanations might be quite unclear because I have little knowledge about implementing distance vector algorithm in sockets programming
  • 0

#4 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 25 November 2011 - 07:12 AM

Here's my issue: you can attempt to determine the shortest possible distance using a breadth-first search, or you can do packet inspection to determine how far an individual packet traveled. Which are you trying to do?
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#5 fread

fread

    Programming God

  • Senior Member
  • PipPipPipPipPipPip
  • 897 posts
  • Location:Trinidad and Tobago
  • Learning:C, Java, C++, C#, PHP, Python, PL/SQL

Posted 25 November 2011 - 07:32 AM

Hi. I have a task to implement distance vector router algorithm. It should send packets from sender to server. I have little clue what should I do. I don't ask code from you but I would like to get some tips on following problems:
1) I previuos tasks i had to make communication between sender and server by using sockets (sender -> server) . As i understand, in the current task routers happen to appear between sender and server (sender -> router -> server). Shold I create class Router and send packets to it's instances? If so, how to connect to Router's object? By using sockets?
2) How many routers do I need and why?
3) How many servers do i need? Why? is 1 enough?
4) How to calculate the shortest path to server? Is it ok, if class Sender knows all paths, their values, calculates shortest path using dijkstra algorithm and gives to packet some data structure containg sequence of routers to be passed while traveling to server?
5) Maybe someone could draw me simple class diagram?

This almost looks like an undergrad project and may require some thoughtful consideration along with reading supporting documents or your text. Those questions depend on a lot of different things.

If i had a task like this, I would try to break the project into sections. At each stage identifying the inputs and outputs.

Ps: I did a course in networks last year and one group of students from my class had something like this for the semester project. I did a (best effort) IPV4 to IPV6 and vice versa conversion.
  • 0

#6 wim DC

wim DC

    Roar

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 2681 posts
  • Programming Language:Java, JavaScript, PL/SQL
  • Learning:Python

Posted 25 November 2011 - 08:48 AM

  • Yes create a router class, and yes connect to it trough sockets.
  • That should be in the assignment. At least 1 I guess :P and up to as many as required.
  • 1 would make most sence, your client sends stuff to the server in the end. You can have more at a different "location" but it should work the same.
  • That depends how much the program must resemble reality. In reality you got an existing network (you start with 1 existing router then - being the network)
    a new router is added. And it will broadcast to all its neighbors for a routing table to "learn" where to send stuff. All routers that receive this broadcast add this
    new router to their table, and send a copy of their table to the new one.

    If it doesn't have to be so "real" then your program can "just" know all routers and do the dijkstra stuff. That basically checks every single possible path untill it has reached
    the end and all other paths have become longer than this one.

    The Client should not know the path. The client propably only knows 1 router to which it sends stuff, and from then on. The router must decide the packet continues.
  • What you created now was
    Client ---sockets---Server
    What it will be:
    Client---router ---router---...----router---Server
    Your client will NEVER create a socket connection to the Server! The client only connects to the single router he knows and connects to that one - sending stuff to it.
    That router then accepts whatever the client has send, client should have told to where it needs to go (Server IP + send the client IP as well) and that's all the router
    needs to know to where the client data should go next.
    Then that router starts socket connection with next router and sends it onwards, untill it reaches the router who is connected to the server. Then finally
    that router can connect to that server, deliver the data (And don't forget to send where the data came from (Client IP) so the server can reply)

  • 0

#7 thatsme

thatsme

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 218 posts

Posted 28 November 2011 - 01:53 AM

1. I wonder how to differ between many routers. All stuff will be happening in localhost, so address is going to be the same for all routers. My friend gave me an idea of creating list of custom sockets (custom socket - not real, written by me). However, for me it's hard to imagine what friend wanted to say. Maybe every device (sender, router...) should have it's own array containing id's of neighbour routers. Would this be a good simulation of sockets?
2. I also don't know where it's best to store those routers. Maybe i should create special class RoutersList ?
3. For shortest path counting my friend suggested me that every router should have table containing information about neighbour routers. This would allow me to calculate shortest path to every device without knowing the exact path. However I woull like to know more detailed information how this calculation happens. Let's say client wants to send packet to server. So it asks neighbour router for it's table of neighbour routers. If asked router has any neghbour routers itself, he also asks the for their tables and so on. Is it how the calculation happens?
  • 0





Also tagged with one or more of these keywords: shortest path

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download