Static Routing In GNS3

Actually this is our first lab using GNS3. The previous post contains a few info on how to open a project and save along with configurations. In previous post, we initiated RIP on routers which computed the routing table entries automatically. Here I will add the first experiment which required manual routing table entry.

Simply open a new project and create a simple topology like shown below. (Click on any image to enlarge)

Here we have 4 routers, where routers R1 and R4 uses only one interface and R2, R3 uses two interfaces. First we need to configure each interface in use. So, after starting all the routers, we open their terminal and then configure the interfaces as we did in previous post. Configuring R1:

Configuring R2:

Configuring R3:

Configuring R4:

Now you can use show ip route command to see routing table on each table. You will see that the routing tables are incomplete. In fact, if you try to ping 192.168.3.1 from R1, it wont be possible to do so. Because ping packets need a round trip route. So, in router R1, we will need to add routing table entries for network 192.168.2.0 and 192.168.3.0. Similarly, router R2 will only need information for network 192.168.3.0 as the other two networks are directly connected to it.. R3 also only need information for network 192.168.1.0 while R4 needs information for network 192.168.1.0 and 192.168.2.0. We will now add these information. In config mode, we can use ip route to add a routing table entry. Next screenshots shows entries for each router.

For router R1:

For router R2:

For router R3:

For router R4:

Now try to ping from each router to each interface, and it works :D Also use show ip route in routers to see the updated routing table entries we have just added. Have fun experimenting!

Simple RIP Routing In GNS3

This is a very basic lab in GNS3 where we will create a simple ring topology of routers and ehternet switches and then run RIP routing protocol on these routers. When we were experimenting in network simulation lab, we found that it is very hard to find simple GNS3 examples showing very basic things. So I am going to put them here as we follow the lab experiments. We will be using CISCO c2600 routers. It is possible to do similar experiment using other routers for which you have an IOS image.

Designing a topology is very easy in GNS3. Just drag and drop from left side dock. Make sure to open a empty project and in new blank project dialogue, make sure both the checkboxes are ticked. Also, make sure idle values of routers are set. If not set yet, right click on a router and select idle-pc. Here is the snapshot of a network we will be using here. (Click on any image to enlarge)

Here each router has two interfaces, namely f0/0 and f0/1. We need to setup ip addresses on each interfaces of all 5 routers. Here I will show the configuration commands for router 1. Make sure all the routers are started, and to get the console, right click on a router and select console.

enable

R1#conf t

R1(config)#int f0/0

R1(config-if)#ip add 192.168.5.2 255.255.255.0

R1(config-if)#no sh

R1(config-if)#exit

R1(config)#int f0/1

R1(config-if)#ip add 192.168.1.1 255.255.255.0

R1(config-if)#no sh

R1(config-if)#end

R1#copy running-config startup-config

Here is a screenshot

Some explanation of short forms: conf t stands for configure terminal, which is simply telling that we will be configuring this router via terminal. However there are other ways to do so. Then we specify the interface we wish to configure in this router, for example: interface f0/0. Then we add ip address and subnet mask. Next is no sh, which stands for no shutdown. It means, this interface will remain "up" the whole time. Here, we can bring it down by providing a shutdown command.

So after configuring all the interfaces, we save the project and copy running configuration to startup configuration file, so that if we close or stop it, we will be able to load the settings directly without having it configured manually again which is a great hassle. 

In the same process, we configure all the interfaces in all the routers. This is the first step of this lab. Now we need to tell the routers that we are going to run RIP on them.

To do so, go into configure mode again (by giving conf t command).

R1(config)#router rip

R1(config-router)#network 192.168.1.0

R1(config-router)#network 192.168.5.0

R1(config-router)#end

As we can see, every router is associated with two networks, so you just provide the network addresses. As we did before, we copy the running configuration to startup configuration once again. After configuring all the routers, we can check their IP routing table to see if all the networks have been discovered by RIP. Snapshot of this step:

Now that all the paths have been discovered. We can now test the network by pinging all the IPs to ensure that all the nodes are reachable from all the others. For example:

The final requirement was to test how RIP respond to any change on the network. For example on router R1, we can see that it has two ways to reach network 192.168.3.0. What happens if we disable interface f0/1, it should not be able to forward packets via hop 192.168.1.2. So we enter configuration mode again and select interface f0/1 on router R1, and give "shutdown" command which will stop interface f0/1. Then we wait a 2-3 seconds (in slow machines, we may need to wait longer, even minutes). Now if you check routing table on R1 by show ip route command, you will see that, network 192.168.3.0 has now only one way. Snapshot is given below. Compare it with what you got last time with show ip route command. You can enable this interface again by putting "no shutdown" command.

So, these are the simple commands we used to complete this task. Have fun with experimenting,

SPOJ - POSTERS

138. Election Posters

Although this problem is actually a good data structure problem, which is meant to be solved by range tree, but as that would need a trick. We only have 40000 nodes so total of 80000 points, but actual range is huge (10^7) for range trees. So, we can map the points so that they span over the minimum range (i.e. compress them). Sounds pathetic, right? However, there are easier ways to solve this.

By using STL set, you can make the problem pretty simulation type. Lets consider a set which contains the ranges, but not as given in input. At any moment, the set will represent the wall at that time, i.e. only visible ranges (so they must be mutually exclusive).

Now, whenever we need to add a new range, we find the leftmost poster (or piece of poster still visible) which must fall under the current one (probably you already got it, it's called lower_bound) and the rightmost poster segment that must fall under it. All the segment between these two segments will be covered, so we remove them from set. Now, we just again insert new left fragment, new right fragment and the new range... that simple it is!

Finally, we can keep and index with each segment so that we can calculate the number of actual different segment at the end of the day :)
For more clarification, consider the sample case:

5
1 4
2 6
8 10
3 4
7 10

The states of the set are shown after each input:

1 4
first entry
{(1,4)}

2 6
{1,4) is leftmost and rightmost at the same time (according to above discussion)
So, we remove it and insert new ranges:
{(1,1),(2,6)}

8 10
no conflict
{(1,1),(2,6),(8,10)}

3 4
conflicts with (2,6) (left and right both)
{(1,1),(2,2),(3,4),(5,6),(8,10)}

7 10
conflicts with (8,10)
{(1,1),(2,2),(3,4),(5,6),(7,10)}

Finally, segments with different id:
(1,1), (2,2), (3,4), (7,10). Note, (2,2) and (5,6) should have same id.

It's good if you have understood what to do, and it's even better if you don't, cause you should solve your problems on your own :p