How to create a routing table for a network

[IDS]

So while learning for an exam I came across the following sample:

I have to create a routing table to the given network (attachement).

There are 4 Routers (A-D) and the numbers on the connecting lines are the linkcosts. The routing tables are in the given format.

Step | Router A                      | Router B                      | Router C                     | Router D                      |

0       | [ (0,A) (/,/) (/,/) (/,/) ] | [ (/,/) (0,B) (/,/) (/,/) ] | [ (/,/) (/,/) (0,C) (/,/) ] | [ (/,/) (/,/) (/,/) (0,D) ] |

 

The tuples (x,y) show the costs and the Next-Hop target. You have to follow the given sequence and every vector in the table shows the distance and the Next-Hop targets. Right now the routing tables are empty and  the routers dont even know their neighbours (given through  (/,/). The cost of a Router reaching to itself is 0.

 

I know its kinda off topic but since I couldnt find a solution in the internet i was hoping one of you guys could help me solve and understand it.

Best regards, IDS

[Ghideon]

Hello.
Usually I have seen routing tables having a destination sub-net, cost and next-hop. Since destination is not included in the tuples I guess that the destination is implicit from the position in the tuples have in the table.

Here is an attempt. It shows how a packets, at router A, will be routed next to reach routers A,B,C or D

[ (0,A) (2,B) (1,C) (1,C) ] 

(0,A) = done, nothing to do

(2,B) = B is reached directly by routing to B, cost is 2

(1,C) = C is reached directly by routing to C, cost is 1

(1,C) = D is reached indirectly by first routing to C (next-hop) , cost is 1.

Apply the above reasoning to the other three tables.

 

 

(Disclaimer: last time i did some serious work on routing tables was in the 90's my memory regarding this is rusty and maybe also obsolete at this time) 

[IDS]

Thanks for your fast reply!

So it would go like that i think:

B : (2/A) (0/B) (4/C) (5/D)

C : (1/A) (4/B) (0/C) (1/D)

D : (2/A) (5/B) (1/C) (0/D)

 

But what about those "steps" on the left side? Cause it says step 0-3. :/

Edited January 22, 2020 by IDS

[Ghideon]

1 hour ago, IDS said:

But what about those "steps" on the left side? Cause it says step 0-3. 😕

I'm unable to see "0-3" in the post, should the end result be four lines so that the table is created alliteratively, filling more tuples on each line? If so I probably posted the final row for "A" without the intermediate steps.

1 hour ago, IDS said:

So it would go like that i think:

B : (2/A) (0/B) (4/C) (5/D)

C : (1/A) (4/B) (0/C) (1/D)

D : (2/A) (5/B) (1/C) (0/D)

Maybe I misinterpreted the requirement. I think the table only may contain the adjacent routers so I guess that only router C will contain all of A,B,C,D. There is for instance no direct route B-D so B must know that packages intended for D should be sent to C. Maybe there is more context you can post? 

[IDS]

So here is the fullt text linked to the picture of the network:

The picture shows a Network with 4 Routers (A-D) and the linkcosts. The routing table should be in the following format:

Step | Router A                      | Router B                      | Router C                     | Router D                      |

0       | [ (0,A) (/,/) (/,/) (/,/) ] | [ (/,/) (0,B) (/,/) (/,/) ] | [ (/,/) (/,/) (0,C) (/,/) ] | [ (/,/) (/,/) (/,/) (0,D) ]  |

The tuple (x,y) shows the costs and the next-hop target. The target is given through  the order. (This means every vextor in the table shows the distance and the next hop to the targets A, B, C and D in this order. At the start the routing tables are empty - the routers do not even know their neighbours. The Routers reach themselves with the cost of 0.

The routers start now to snyc in periodic time distances. Stop when you have reached a convergent status. 

Note: The solution depends on the order the packages are send - so lets say all routers send their packages at the exact same time.

-translated

So it says that all of them send their packages at the same time. my guess was to maybe do it like:

Step | Router |

0        | [ (0,A) (/,/) (/,/) (/,/) ]

1        | [ (0,A) (2,B) (1,C) (/,/) ]

2        | [ (0,A) (2,B) (1,C) (1,D) ]

But I am still kinda clueless tbh :´D

[Ghideon]

Thanks for the update, this allows for a more complete analysis.

2 hours ago, IDS said:

The target is given through  the order.

OK, that indicates the guess that the destination is implicit from the position the table is correct. Here is a modified attempt. I guess you are on the right path but I suspect the routing table for router A may only contain the name of the next router, the next-hop target. So the green (2,C) entry below means an outgoing packet from router A, intended for router D should be sent to C for further routing. The cost is 2.

|Step | Router A |

0        | [ (0,A) (/,/) (/,/) (/,/) ]

1        | [ (0,A) (2,B) (1,C) (/,/) ]

2        | [ (0,A) (2,B) (1,C) (2,C) ]

Router B is more interesting since I guess that there is some selection algorithm involved to make the task more interesting. Note that the table is not static for some tuples, the router B will calculate that the route to C is cheaper through A. In reality this is more complicated. A discussion about the history behind the algorithms, mathematic proofs and issues in real applications is off topic for this thread, but could be very interesting. 

|Step | Router B |

0        | [ (/,/) (0,B) (/,/) (/,/) ]

1        | [ (2,A) (0,B) (4,C) (/,/) ]

2        | [ (2,A) (0,B) (3,A) (5,C) ]

3        | [ (2,A) (0,B) (3,A) (4,A) ]

C and D are similar to create.

Attached below is a reference from a textbook on distributed computing.
Note that the "B" router in the example only contains adjacent routers.
Destination is explicit in the table. "kostnad" translates to "cost". 
The example is slightly more complicated than the task above since cost for the routes are asymmetric.

 

Edited January 23, 2020 by Ghideon
grammar

[Phi for All]

I thought this was for a new HGTV woodworking show, my bad. Carry on. 

[Ghideon]

2 minutes ago, Phi for All said:

I thought this was for a new HGTV woodworking show, my bad. Carry on. 

The picture above is from an era way before Home & Garden Television was launched! Easy to mix up 
 

[IDS]

First of all, I am very thankful for your help!

I tried to finish the other tables, could you maybe tell me if I am right? 

|Step | Router A |

0        | [ (0,A) (/,/) (/,/) (/,/) ]

1        | [ (0,A) (2,B) (1,C) (/,/) ]

2        | [ (0,A) (2,B) (1,C) (2,C)  ]

 

|Step | Router B |

0        | [ (/,/) (0,B) (/,/) (/,/) ]

1        | [ (2,A) (0,B) (4,C) (/,/) ]

2        | [ (2,A) (0,B) (3,A) (5,C) ]

3        | [ (2,A) (0,B) (3,A) (4,A) ]

 

|Step | Router C |

0        | [ (/,/) (/,/) (0,C) (/,/) ]

1        | [ (1,A) (4,B) (0,C) (1,D) ]

2        | [ (6,B) (3,A) (0,A) (1,D) ]

|Step | Router D |

0        | [ (/,/) (/,/) (/,/) (0,D) ]

1        | [ (2,A) (0,B) (1,C) (0,D) ]

2        | [ (2,C) (4,C) (1,C) (0,D) ]

3        | [ (6,C) (3,C) (1,C) (0,D) ]

 

I have no idea why I have so much trouble with such a basic task I guess X-X

[Ghideon]

1 hour ago, IDS said:

First of all, I am very thankful for your help!

I tried to finish the other tables, could you maybe tell me if I am right? 

|Step | Router A |

0        | [ (0,A) (/,/) (/,/) (/,/) ]

1        | [ (0,A) (2,B) (1,C) (/,/) ]

2        | [ (0,A) (2,B) (1,C) (2,C)  ]

 

|Step | Router B |

0        | [ (/,/) (0,B) (/,/) (/,/) ]

1        | [ (2,A) (0,B) (4,C) (/,/) ]

2        | [ (2,A) (0,B) (3,A) (5,C) ]

3        | [ (2,A) (0,B) (3,A) (4,A) ]

 

|Step | Router C |

0        | [ (/,/) (/,/) (0,C) (/,/) ]

1        | [ (1,A) (4,B) (0,C) (1,D) ]

2        | [ (6,B) (3,A) (0,A) (1,D) ]

|Step | Router D |

0        | [ (/,/) (/,/) (/,/) (0,D) ]

1        | [ (2,A) (0,B) (1,C) (0,D) ]

2        | [ (2,C) (4,C) (1,C) (0,D) ]

3        | [ (6,C) (3,C) (1,C) (0,D) ]

 

I have no idea why I have so much trouble with such a basic task I guess X-X

Thanks for the feedback! 

A quick check.

Router A seems right. Step 2 gets a second route to B through C but since that is longer (=5) you have correctly rejected it. If a third step would be added the router A would get a route to D through B-C but more expensive (=7) so no changes will be made to A's routing table.

Router B Seems OK, as argued above

Router C has a typo on step 2, I think (0,A) should be (0,C). Also I think the route to A will not change on step 2. Unless there is some weird algorithm or additional information the router will likely keep (1,A) since that is cheaper than going through B at cost 6. 

Router D seems a little off:

0        | [ (/,/) (/,/) (/,/) (0,D) ] Seems OK

1        | [ (2,A) (0,B) (1,C) (0,D) ] This step could not contain information about A and B yet, how about  this: | [(/,/) (/,/) (1,C) (0,D) ]

2        | [ (2,C) (4,C) (1,C) (0,D) ]   (4,C) should likely be (5,C) since D->C->B is 1+4=5

3        | [ (6,C) (3,C) (1,C) (0,D) ]  (3,C) should likely be (4,C) since D->C->A->B = 1+1+2=4

 

Important note: I have tried to stay very basic in the analysis above since the exam task does not provide much information. That means that if this is an exam for a specific implementation for instance a certification for a specific brand or manufacturer there could be other things that the exam expects to be taken into account. 

Additional, non important stuff:

I note that this little example looks very simple but contains enough to be used as a basis for a discussion about a lots of additional questions for the interested. Example: if the routers keep the more expensive path instead of dropping them the routers would have backup paths in case of failure. But if they do, additional algorithms may be required. If A knows B can be reached through C, and C knows B can be reached through A, What happens if B goes off-line? Will a package intended for B bounce back and forth between A and C? Such questions is not likely something a network engineer will care much about on a daily bases in a modern environment. Designing the algorithms, improving them, and studying the math behind it is ongoing. 

The picture reference above is from a book for a course in distributed computing, 1993 edition. Much of it is obsolete now. I guess that newer sources could be based more on interest since the topic contains so much more nowadays.

[IDS]

I am so thankful for your help!