Introduction to Packet Tracer

Packet Tracer is a protocol simulator developed at Cisco Systems. Packet Tracer (PT) is a powerful and dynamic tool that displays the various protocols used in networking, in either Real Time or Simulation mode. This includes layer 2 protocols such as Ethernet and PPP, layer 3 protocols such as IP, ICMP, and ARP, and layer 4 protocols such as TCP and UDP. Routing protocols can also be traced. Packet Tracer is a supplement to and not a replacement for experience with real equipment. Students are encouraged to compare the results obtained from Packet Tracer network models with the behavior of real equipment.

Creating a New Topology in Packet Tracer
Start Packet Tracer



Choosing Devices and Connections
We will begin building our network topology by selecting devices and the media in which to connect them. Several types of devices and network connections can be used. For this lab we will keep it simple by using End Devices, Switches, Hubs, and Connections.
Single click on each group of devices and connections to display the various choices. When we select a device in the left panel, in the right panel we see all the listed devices of that type.


Single click on the End Devices.


Single click on the Generic host.



Move the cursor into topology area. You will notice it turns into a plus “+” sign.


Single click in the topology area and it copies the device.

 


Add three more hosts.


Adding a Hub

Select a hub, by clicking once on Hubs and once on a Generic hub.

 


Add the hub by moving the plus sign “+” below PC0 and PC1 and click once.


Connect PC0 to Hub0 by first choosing Connections.



Click once on the Copper Straight-through cable.



Perform the following steps to connect PC0 to Hub0:

1. Click once on PC0
2. Choose FastEthernet
3. Drag the cursor to Hub0
4. Click once on Hub0 and choose Port 0
5. Notice the green link lights on both the PC0 Ethernet NIC and the Hub0 Port 0 showing that the link is active.

1	2	3	4	5

Repeat the steps above for PC1 connecting it to Port 1 on Hub0. (The actual hub port you choose does not matter.


Adding a Switch

Select a switch, by clicking once on Switches and once on a 2950-24 switch.

 


Add the switch by moving the plus sign “+” below PC2 and PC3 and click once.

 


Connect PC2 to Hub0 by first choosing Connections.



Click once on the Copper Straight-through cable



Perform the following steps to connect PC2 to Switch0:

1. Click once on PC2
2. Choose FastEthernet
3. Drag the cursor to Switch0
4. Click once on Switch0 and choose FastEthernet0/1
5. Notice the green link lights on PC2 Ethernet NIC and amber light Switch0 FastEthernet0/1 port. The switch port is temporarily not forwarding frames, while it goes through the stages for the Spanning Tree Protocol (STP) process.
6. After a about 30 seconds the amber light will change to green indicating that the port has entered the forwarding stage. Frames can now forwarded out the switch port.

1	2	3	4	5	6

Repeat the steps above for PC3 connecting it to Port 3 on Switch0 on port FastEtherent0/2. (The actual switch port you choose does not matter.)


Move the cursor over the link light to view the port number. Fa means FastEthernet, 100 Mbps Ethernet.


After you successfully create the topology like here,

Be sure you are in Realtime mode.

Select the Add Simple PDU tool used to ping devices.


Click once on PC0, then once on PC3.
The PDU Last Status should show as Successful.


For a detailed successful topology creation and traffic flow, click here.

Technorati Tags: introduction to packet tracer,packet tracer tutorial,packet tracer,packet tracer devices

Variation of Linked List

In this tutorial we are going to discuss some variations of linked list.

Doubly-linked List

If you look at single link list, the chain is seen formed in a way that every node has a field next that point to the next node. This continues till the last node where we set the next to NULL i.e. the end of the list. There is a headNode pointer that points to the start of the list. We have seen that moving forward is easy in single link list but going back is difficult. For moving backward, we have to go at the start of the list and begin from there. Do you need a list in which one has to move back or forward or at the start or in the end very often? If so, we have to use double link list.

In doubly-link list, a programmer uses two pointers in the node, i.e. one to point to next node and the other to point to the previous node. Now our node factory will create a node with three parts.

First part is prev i.e. the pointer pointing to the previous node, second part is element, containing the data to be inserted in the list. The third part is next pointer that points to the next node of the list. The objective of prev is to store the address of the previous node.

Let’s discuss the code of the node of the doubly-link list. This node factory will create nodes, each having two pointers. The interface methods are same as used in singly link list. The additional methods are getPrev and setPrev. The method getPrev returns the address of the previous node. Thus its return type is Node*. The setPrev method sets the prev pointer. If we have to assign some address to prev pointer, we will call this method. Following is the code of the doubly-linked list node.

/* this is the doubly-linked list class, it uses the next and prev pointers */ class Node { public: int get() { return object; }; // returns the value of the element void set(int object) { this->object = object; }; // set the value of the element Node* getNext() { return nextNode; }; // get the address of the next node void setNext(Node* nextNode) // set the address of the next node { this->nextNode = nextNode; }; Node* getPrev() { return prevNode; }; // get the address of the prev node void setPrev(Node* prevNode) // set the address of the prev node { this->prevNode = prevNode; }; private: int object; // it stores the actual value of the element Node* nextNode; // this points to the next node Node* prevNode; // this points to the previous node };

Most of the methods are same as those in singly linked list. A new pointer prevNode is added and the methods to get and set its value i.e. getPrev and setPrev. Now we will use this node factory to create nodes.

You have to be very cautious while adding or removing a node in a doubly linked list. The order in which pointers are reorganized is important. Let’s have a pictorial view of doubly-link list. The diagram can help us understand where the prevNode and nextNode are pointing.

 

This is a doubly link list. The arrows pointing towards right side are representing nextNode while those pointing towards left side are representing prevNode. Suppose we are at the last node i.e. the node with value 1. In case of going back, we usually take the help of prevNode pointer. So we can go to the previous node i.e. the node with value 7 and then to the node with value 8 and so on. In this way, we can traverse the list from the end to start. We can move forward or backward in doubly-link list very easily. We have developed this facility for the users to move in the list easily.

Let’s discuss other methods of the doubly-linked list. Suppose we have created a new node from the factory with value 9. We will request the node factory to create a new object using new keyword. The newly created node contains three fields i.e. object, prevNode and nextNode. We will store 9 into object and connect this new node in the chain. Let’s see how the pointers are manipulated to do that. Consider the above diagram, the current is pointing at the node with value 6. The new node will be inserted between the node with value 6 and the one with value 8.

In the first step, we assign the address of the node with value 8 to the nextNode of the new node.

newNode->setNext( current->getNext() );

In the next step, a programmer points the prevNode of the newNode to the node with value 6.

newNode->setprev( current );

In the third step, we will set the previous node with value 8 to point to the newNode.

(current->getNext())->setPrev(newNode);

Now the prevNode of the node with value 8 is pointing to the node with value 9.

In the fourth step, the nextNode of the node with value 6 is pointing to the newNode i.e. the node with value 9. Point the current to the newNode and add one to the size of the list.

current->setNext( newNode );

current = newNode;

size++;

Now the newNode has been inserted between node with value 6 and node with value 8.

Circularly-linked lists

Let’s talk about circularly linked list. The next field in the last node in a singly-linked list is set to NULL. The same is the case in the doubly-linked list. Moving along a singly-linked list has to be done in a watchful manner. Doubly-linked lists have two NULL pointers i.e. prev in the first node and next in the last node. A way around this potential hazard is to link the last node with the first node in the list to create a circularly-linked list.

The next method in the singly-linked list or doubly-linked list moves the current pointer to the next node and every time it checks whether the next pointer is NULL or not. Similarly the back method in the double-linked list has to be employed carefully if the current is pointing the first node. In this case, the prev pointer is pointing to NULL. If we do not take care of this, the current will be pointing to NULL. So if we try to access the NULL pointer, it will result in an error. To avoid this, we can make a circularly linked list.

We have a list with five elements. We have connected the last node with the first node. It means that the next of the last node is pointing towards the first node.

The same list has been shown in a circular shape.

 

You have noticed that there is no such node whose next field is NULL. What is the benefit of this? If you use the next or back methods that move the current pointer, it will never point to NULL. It may be the case that you keep on circulating in the list. To avoid this, we get help from the head node. If we move the head node in the circularly linked list, it will not be certain to say where it was pointing in the start. Its advantages depend on its use. If we do not have to move too much in the list and have no problem checking the NULL, there is little need a circularly-linked list. But this facility is available to us.

In this example, we made a circular linked list from a singly link list. In a singly link list we move in one direction. We point the next pointer of the last node to the first node. We can do the same with the doubly-linked list. The prev pointer of the first node will point to the last node and the next pointer of the last node will point to the first node. If you arrange all the nodes in a circle, one of the pointers (i.e. next pointer) will move in clockwise direction while the prev pointers in anti-clockwise direction. With the help of these pointers, you can move in the clockwise direction or anti-clockwise direction. Head node pointer will remain at its position. You don’t need to change it. If there is a need to remove the node pointed by head node than you have to move the head pointer to other node. Now we don’t have any NULL pointer in the doubly-linked list. We will not get any exception due to NULL pointers.


Benefits of using circular list

While solving the Josephus problem, it was witnessed that the usage of circular linked list helped us make the solution trivial. We had to just write a code of some lines that solved the whole problem. In the program, we included the class CList (which is of our data structure i.e. circular linked list) and used all of its methods according to the requirements. There was no problem regarding the working of the methods. We just called these methods and their definition in the class CList worked well.

Now we will see what happens if we solve the Josephus problem by using an array instead of the class in our program. In this case, we have to define an array and write code to move back and forth in the array and to remove different elements properly in a particular order. A programmer needs to be very careful while doing this, to reach the solution of the problem. Thus our code becomes very complex and difficult for someone to understand and modify it. Moreover we cannot use this code in some other problem. There is no need to be worried whether an array, singly linked list, doubly linked list is used or circular linked list being employed internally in implementing the list in defining the class of list data type. We only want that it should create objects of list. The usage of the class of a data structure simplifies the code of the program. We can also use this class wherever needed in other programs. This shows that the choice of appropriate data structures can simplify an algorithm. It can make the algorithm much faster and efficient.

Technorati Tags: data structure,data structure and algorithm tutorial,ds tutorial,linked list tutorial,linked list implementation,linked list,link list,programming,linked list in c++,circular linked list,doubly linked list,double linked list.

Josephus Problem in Data Structure

Now we will see an example where circular link list is very useful. This is Josephus Problem. Consider there are 10 persons. They would like to choose a leader. The way they decide is that all 10 sit in a circle. They start a count with person 1 and go in clockwise direction and skip 3. Person 4 reached is eliminated. The count starts with the fifth and the next person to go is the fourth in count. Eventually, a single person remains.

You might ask why someone has to choose a leader in this way. There are some historical stories attached to it. This problem is also studied in mathematics. Let’s see diagrammatically.

 

We have ten numbers representing the ten persons who are in a circle. The value of M shows the count. As the value of M is three, the count will be three. N represents the number of persons. Now we start counting clockwise. After counting up to three, we have the number four. The number four is eliminated and put in the eliminated column.

Eliminated

After eliminating the number four, we will start our counting from number five. Counting up to three, we have number eight which is eliminated and so on.

The process is continued and In the end, only number five will remain intact.

 

If we have ten persons (N = 10) in a circle and eliminate after counting up to three (M = 3). If we start our count from one, who will be the leader? We have studied this earlier and know that the person who is sitting at the fifth position will become the leader.

Suppose if the value of N is 300 or 400 and the value of M is 5 or 10. Now who will be the leader? This is a mathematical problem where we can change the values of N and M. There is a formula where the values of N, M are allotted. You can calculate who should become the leader. Here we will not solve it mathematically. Rather, it will be tackled as a computer problem. If you analyze the pictures shown above, it gets clear that this can be solved with the circular link list. We arrange these numbers in a circularly-linked list, point the head pointer at the starting number and after calling the next method for three times, we will reach the node which is to be removed. We will use the remove method to remove the node. Then the next method is called thrice from there and the node is removed. We will continue this till we have only one node.

We are not concerned with the NULL pointers, internal to link list. However, if you want to solve this problem and choose the best data structure, then circular link list is the best option. We can also use the list to solve this.

Let’s see the code of the program by which we can solve this problem. The code is as under:

/*This program solves the Josephus Problem */ #include <iostream.h> #include "CList.cpp" //contains the circularly-linked list definition // The main method void main(int argc, char *argv[]) { CList list; // creating an object of list int i, N=10, M=3; for(i=1; i <= N; i++ ) list.add(i); // initializing the list with values list.start(); // pointing the pointers at the start of the list // counting upto M times and removing the element while( list.length() > 1 ) { for(i=1; i <= M; i++ ) list.next(); cout << "remove: " << list.get() << endl; list.remove(); } cout << "leader is: " << list.get() << endl; //displaying the remaining node }

We have included the “CList.cpp”. It means that we are using the circularly-linked list. In the main method, CList is called to create a circular link list as CList list; After this, we assign the values to N and M. We have used for loop to add the nodes in the list. When this loop finishes, we have ten nodes in the list having values from 1 to 10. But here a programmer may not pay attention to the internal details of the list. We have created a list and stored ten numbers in it. Then we moved the pointers of the list at the start of the list using the start method. It means that the pointers are pointing at the position from where we want to start the counting of the list.

There is a while loop that will continue executing until only one node is left in the list. Inside this loop, we have a for loop. It will execute from 1 to M. It has only one statement i.e. list.next(). This will move the pointer forward three times (as the value of M is 3). Now the current pointer is at the 4^th node. We called the remove method. Before removing the node. Again we come into the while loop, now the length of the list is 9. The ‘for loop’ will be executed. Now the list.next() is not starting from the start. It will start from the position where the current pointer is pointing. The current pointer is pointing at the next node to the node deleted. The count will start again. The list.next() will be called for three times. The current pointer will point at the 8^th node. Again the remove method will be called and the current pointer moved to the next node and so on. The nodes will be deleted one by one until the length of the list is greater than one. When the length of the list is one, the while loop will be terminated. Now only one node is left in the list i.e. the leader. We will display its value using the get method.

We can change the values of M and N. Similarly, these values can be read from the file or can use the command line arguments to get values. There are many variations of this problem. One variation is that the value of M keeps on changing. Sometimes, it is 3, sometimes 4 or 5 and so on. Due to this, it will become difficult to think that who will become leader. Make a picture in your mind that ten persons are sitting in a circle. Every time the value of M is incremented by one. Now try to ascertain which position you should sit to get chosen as a leader.

The code of the program is given below.

#include "CList.cpp" void main(int argc, char *argv[]) { CList list; int i, N=10, M=3; for(i=1; i <= N; i++ ) list.add(i); list.start(); while( list.length() > 1 ) { for(i=1; i <= M; i++ ) list.next(); cout << "remove: " << list.get() << endl; list.remove(); } cout << "leader is: " << list.get() << endl; }

In the program, we include the file of the class CList and create its object i.e. list. Then we solve the problem by using the add, start, length, next, remove and get methods of the class CList.

In the program, we have included already-defined data structure CList. After defining its different methods, we have an interface of Clist. There is no need to be worry about the nature of the list i.e. whether it is linked list, doubly linked list or an array. For us, it is only a list to be manipulated according to our requirement. You will see that a programmer may use different methods of the list object to solve the problem. We add elements to the list by a simple call of add method and go to the first element of the list by start method. Here, the length method is used in the condition of the while loop. Then we remove elements from the list and use the next, get and remove methods during this process. We get the current element by using the get method, then remove it by calling the remove method and then go to the next element by the method next. This way, all the elements are removed from the list except one element, called the leader. This one element remains there as we execute the while loop one less than the length of the list.

In singly linked list, the ‘next’ returns false when it reaches to the last node due to the fact that the next field of the last node is set to NULL. But in a circularly linked list there is no NULL. It will be there only when there is no node in the list.

Technorati Tags: data structure,data structure and algorithm tutorial,ds tutorial,linked list tutorial,linked list implementation,linked list,link list,programming,linked list in c++,josephus problem,josephus problem in data structure