November 17, 2012

Inter VLAN Routing (Router on a Stick)

In this tutorial we are going apply inter vlan routing. In order to communicate between different vlans, we use this phenomenon. Let us apply vlan on the following topology, then we will apply vtp (vlan trunking protocol).  

1

Now, in order to communicate between different vlans we will have to create sub interfaces of fast ethernet interface of router. Let us do that. Note that, we will create as many sub interfaces as many vlans we are using in our topology. In this case we are using 2 vlans, so we will create two sub interfaces for both vlans.

 2

We will also apply encapsulation of sub interface.
 3

Let us create vlans and assign those vlans to switch interfaces i.e. PCs
4

And,
 5

In order to apply VTP we will have write the following commands. Apply the domain name, and trunk the ports of switch. Note, trunk only those ports that are connected to router and switches.
6

Thus, vlans are visible in other switches too after trunking.
7

Trunk the port of the switch 1 as well.

 9

Now, we see ,in the bottom right corner,  we are able to communicate in between vlans and that s what we wanted , isnt it ?
 10

November 16, 2012

ACL on packet tracer

1
Let us apply ACL (Access Control List) on the topology. First, let us assign IP addresses and change the state of the interfaces.
2
Here, the status is change as shown in the following diagram.
3
Then, we will have to assign IP addresses to the PCs.
 4
And the PC attach to the other interface. Please note the difference between default gateways. We assign fast Ethernet interface address to default gateway.
5
Thus, after applying IP addresses. We see that Packet transfer is successful.
6
Let us apply ACL and permit and deny Hosts IP’s as we want. We are going to deny and permit certain hosts as follows.
a
Let us apply ACL and permit and deny Hosts IP’s as we want.
 7
Then, we will have to tell the interface that which ACL to follow. ACL is uniquely identified with the number, in this case 1.
8
Now, you see that the denied will not be able to send the data while those who we permit can send packet.
 9
Similarly, in the bottom right corner you can see status.
10

Infix to Postfix Conversion

In order to convert infix to postfix expression, we need to understand the precedence of operators first.

Precedence of Operators

There are five binary operators, called addition, subtraction, multiplication, division and exponentiation. We are aware of some other binary operators. For example, all relational operators are binary ones. There are some unary operators as well. These require only one operand e.g. – and +. There are rules or order of execution of operators in Mathematics called precedence. Firstly, the exponentiation operation is executed, followed by multiplication/division and at the end addition/subtraction is done. The order of precedence is 

(highest to lowest):
Exponentiation ­
Multiplication/division *, /
Addition/subtraction +, -
For operators of same precedence, the left-to-right rule applies:
A+B+C means (A+B)+C.
For exponentiation, the right-to-left rule applies:
A ­ B ­ C means A ­ (B ­ C)
We want to understand these precedence of operators and infix and postfix forms of expressions. A programmer can solve a problem where the program will be aware of the precedence rules and convert the expression from infix to postfix based on the precedence rules.
 

Examples of Infix to Postfix

Let’s consider few examples to elaborate the infix and postfix forms of expressions based on their precedence order:

Infix Postfix
A + B
12 + 60 – 23
(A + B)*(C – D )
A ­ B * C – D + E/F


A B +
12 60 + 23 –
A B + C D – *
A B ­ C*D – E F/+


A programmer can write the operators either after the operands i.e. postfix notation or before the operands i.e. prefix notation. Some of the examples are as under:

Infix Postfix
A + B A B +
12 + 60 – 23 12 60 + 23 –
(A + B)*(C – D ) A B + C D – *
A ­ B * C – D + E/F A B ­ C*D – E F/+

The last expression seems a bit confusing but may prove simple by following the rules in letter and spirit. In the postfix form, parentheses are not used. Consider the infix expressions as ‘4+3*5’ and ‘(4+3)*5’. The parentheses are not needed in the first but are necessary in the second expression. The postfix forms are:
4+3*5 435*+
(4+3)*5 43+5*
In case of not using the parenthesis in the infix form, you have to see the precedence rule before evaluating the expression. In the above example, if we want to add first then we have to use the parenthesis. In the postfix form, we do not need to use parenthesis. The position of operators and operands in the expression makes it clear in which order we have to do the multiplication and addition.
Now we will see how the infix expression can be evaluated. Suppose we have a postfix expression. How can we evaluate it? Each operator in a postfix expression refers to the previous two operands. As the operators are binary (we are not talking about unary operators here), so two operands are needed for each operator. The nature of these operators is not affected in the postfix form i.e. the plus operator (+) will apply on two operands. Each time we read an operand, we will push it on the stack. We are going to evaluate the postfix expression with the help of stack. After reaching an operator, we pop the two operands from the top of the stack, apply the operator and push the result back on the stack. Now we will see an example to comprehend the working of stack for the evaluation of the postfix form. Here is the algorithm in pseudo code form. After reading this code, you will understand the algorithm.

Stack s; // declare a stack
while( not end of input ) { // not end of postfix expression
e = get next element of input
if( e is an operand )
s.push( e );
else {
op2 = s.pop();
op1 = s.pop();
value = result of applying operator ‘e’ to op1 and op2;
s.push( value );
}
}
finalresult = s.pop();

We have declared a Stack‘s’. There is a ‘while loop’ along with ‘not end of input’ condition. Here the input is our postfix expression. You can get the expression from the keyboard and use the enter key to finish the expression. In the next statement, we get the next element and store it in ‘e’. This element can be operator or operand. The operand needs not to be single digit. It may be of two digits or even more like 60 or 234 etc. The complete number is stored in the ‘e’. Then we have an ‘if statement’ to check whether ‘e’ is an operand or not. If ‘e’ is an operand than we wrote s.push(e) i.e. we pushed the ‘e’ onto the stack. If ‘e’ is not the operand, it may be an operator. Therefore we will pop the two elements and apply that operator. We pop the stack and store the operand in ‘op2’. We pop the stack again and store the element in ‘op1’. Then the operator in ‘e’ is applied to ‘op1’ and ‘op2’ before storing the result in value. In the end, we push the ‘value’ on the stack. After exiting the loop, a programmer may have only one element in the stack. We pop this element which is the final result.
Consider the example of 4+3*2 having a postfix form of 432*+. Here 4, 3, and 2 are operands whereas + and * are operators. We will push the numbers 4, 3 and 2 on the stack before getting the operator *. Two operands will be popped from the stack and * is being applied on these. As stack is a LIFO structure, so we get 2 first and then 3 as a result of pop. So 2 is store in ‘op1’ and 3 in ‘op2’. Let’s have a look on the program again. On applying * on these, we will push the result (i.e. 6) on the stack. The ‘while loop’ will be executed again. In case of getting the next input as operand, we will push it on the stack otherwise we will pop the two operands and apply the operator on these. Here the next element is the operator +. So two operands will be popped from the stack i.e. 6 and 4. We will apply the operator plus on these and push the result (i.e. 10) on the stack. The input is finished. Now we will pop the stack to get the final result i.e. 10.

 Postfix Expression solved by Example

In the earlier example, we have used the stack to solve the postfix expression. Let’s see another comprehensive example. The postfix expression is:
6 2 3 + - 3 8 2 / + * 2 ­ 3 +
We want to evaluate this long expression using stack. Let’s try to solve it on paper. We have five columns here i.e. input, op1, op2, value and stack. We will run our pseudo code program. In the start, we read the input as a result we get number 6. As 6 is operand, so it will be pushed on the stack. Then we have number 2 which will also be pushed on the stack. Now 2 is the most recent element. The next element is the number 3 that will also be pushed on the stack. Now, there are three elements on the stack i.e. 3, 2 and 6. The number 3 is the most recent. On popping, we will get the number 3 first of all. The next element is ‘+’, an operator. Now the else part of our pseudo code is executed. We will pop two operands from the stack and apply the operator (+) on these. The number 3 will be stored in variable op2 and number 2 in op1. The operator (+) will be applied on these i.e. 2+3 and the result is stored in value. Now we will push the value (i.e. 5) on the stack. Now we have two numbers on the stack i.e. 5 and 6. The number 5 is the most recent element. The next element is ‘-‘. As it is also an operator, so we will pop the two elements from the stack i.e. 5 and 6. Now we have 5 in op2 and 6 in op1. On applying the operator (-), we will get the result as 1 (6-5). We can’t say op2 - op1. The result (1) will be pushed on stack. Now on the stack, we have only one element i.e. 1. Next three elements are operands so we pushed 3, 8 and 2 on the stack. The most recent element is 2. The next input is an operator in the expression i.e. ‘/’, we will pop two elements from the stack. The number 2 will be stored in op2 while number 8 in op1. We apply the operator (/) on the op1 and op2 i.e. (op1/op2), the result is 4 (i.e. 8/2). We push the result on the stack. We have, now, three elements i.e. 4, 3, and 1 on the stack. The next element is operator plus (+). We will pop the two elements i.e. 4 and 3 and will apply the operator (+). The result (7) will be pushed on the stack. The next input element is operator multiply (*). We will pop the two elements i.e. 7 and 1 and the result (7*1 = 7) is pushed on the stack. You have noted that whenever we have an operator in the input expression, we have two or more elements on the stack. As the operators we are using are binary and we need two operands for them. It will never be the case that you want to pop two elements from the stack and there is only one or no element on the stack. If this happens than it means there is an error in the program and you have popped more values than required. The next input element is 2 that is pushed on the stack. We have, now, the operator ( ­ ) in the input. So we will pop the two elements, op2 will hold 2 and op1 will have the number 7. The operator ( ­ ) will be applied on the operands i.e. (7 ­ 2) and the result (49) is pushed on the stack. We have, now, the number 3 in the element being pushed on the stack. The last element is the operator plus (+). So we pop the two elements i.e. 49 and 2 and apply the operator on these. The result (49+3 = 52) is pushed on the stack. The input expression is finished, resulting in the final result i.e. 52.
This the tabular form of the evaluation of the postfix expression.

Input op1 op2 value stack
6 6
2 2
6
3 3
2
6

+ 2 3 5 5
6
- 6 5 1 1
3 6 5 1 3
1
8 6 5 1 8
3
1

2 6 5 1 2
8
3
1


/ 8 2 4 4
3
1

+ 3 4 7 7
1
* 1 7 7 7
2 1 7 7 2
7
­ 7 2 49 49
3 7 2 49 3
49
+ 49 3 52 52

With the help of stack we can easily solve a very big postfix expression. Suppose you want to make a calculator that is a part of some application e.g. some spreadsheet program. This calculator will be used to evaluate expressions. You may want to calculate the value of a cell after evaluating different cells. Evaluation of the infix form programmatically is difficult but it can be done. We will see another data structure which being used to solve the expressions in infix form. Currently, we have to evaluate the values in different cells and put this value in another cell. How can we do that? We will make the postfix form of the expression associated with that cell. Then we can apply the above algorithm to solve the postfix expression and the final result will be placed at that cell. This is one of the usages of the stack.

Infix to postfix Conversion
We have seen how to evaluate the postfix expressions while using the stack. How can we convert the infix expression into postfix form? Consider the example of a spreadsheet. We have to evaluate expressions. The users of this spreadsheet will employ the infix form of expressions. Consider the infix expressions ‘A+B*C’ and ‘(A+B)*C’. The postfix versions are ‘ABC*+’ and ‘AB+C*’ respectively. The order of operands in postfix is the same as that in the infix. In both the infix expressions, we have the order of operands as A, B and then C. In the postfix expressions too, the order is the same i.e. A, B, followed by C. The order of operands is not changed in postfix form. However, the order of operators may be changed. In the first expression ‘A+B*C’, the postfix expression is ‘ABC*+’. In the postfix form multiplication comes before the plus operator. In scanning from left to right, the operand ‘A’ can be inserted into postfix expression. First rule of algorithm is that if we find the operand in the infix form, put it in the postfix form. The rules for operators are different. The ‘+’ cannot be inserted in the postfix expression until its second operand has been scanned and inserted. Keep the expression A+B*C in your mind. What is the second operand of the plus? The first operand is A and the second operand is the result of B*C. The ‘+’ has to wait until the ‘*’ has not been performed. You do the same thing while using the calculator. First you will multiply the B*C and then add A into the result. The ‘+’ has to be stored away until its proper position is found. When ‘B’ is seen, it is immediately inserted into the postfix expression. As ‘B’ is the operand, we will send the operand to the postfix form. Can the ‘+’ be inserted now? In case of ‘A+B*C’, we cannot insert ‘+’ because ‘*’ has precedence. To perform multiplication, we need the second operand. The first operand of multiplication is ‘B’ while the second one is ‘C’. So at first, we will perform the multiplication before adding result to ‘A’.
In case of ‘(A+B)*C’, the closing parenthesis indicates that ‘+’ must be performed first. After sending the A and B to postfix perform, we can perform the addition due to the presence of the parenthesis. Then C will be sent to the postfix expression. It will be followed by the multiplication of the C and the result of A + B. The postfix form of this expression is AB+C*. Sometimes, we have two operators and need to decide which to apply first like in this case ‘+’ and ‘*’. In this case, we have to see which operator has higher precedence. Assume that we have a function ‘prcd(op1,op2)’ where op1 and op2 are two operators. The function ‘prcd(op1,op2)’ will return TRUE if op1 has precedence over op2, FASLE otherwise. Suppose we call this function with the arguments ‘*’ and ‘+’ i.e. prcd(*, +), it will return true. It will also return true in case both op1 and op2 are ‘+’ e.g. if we have A+B+C, then it does not matter which + we perform first. The call prcd(+ , *) will return false as the precedence of * is higher than the + operator. The ‘+’ has to wait until * is performed.
Now we will try to form an algorithm to convert infix form into postfix form. For this purpose, a pseudo code will be written. We will also write the loops and if conditions. The pseudo code is independent of languages. We will be using a stack in this algorithm. Here, the infix expression is in the form of a string. The algorithm is as follows:
Stack s;
while( not end of input ) {
c = next input character;
if( c is an operand )
add c to postfix string;
else {
while( !s.empty() && prcd(s.top(),c) ){
op = s.pop();
add op to the postfix string;
}
s.push( c );
}
while( !s.empty() ) {
op = s.pop();
add op to postfix string;
}
First we will declare a stack ‘s’. The ‘while loop’ will continue till the end of input. We read the input character and store it in the ‘c’. Here the input character does not mean one character, but an operand or an operator. Then we have a conditional if statement. If ‘c’ is an operand, then we will have to add it to postfix string. Whenever we get an operand in the infix form, it will be added to the postfix form. The order of operands does not change in the conversion. However, in this case, the order of operators may change. If ‘c’ is the operator, then we will, at first, check that stack is not empty besides identifying the precedence of the operators between the input operator and the operator that is at the top of the stack. In case of the precedence of the operator that is on the stack is higher, we will pop it from the stack and send to the postfix string. For example if we have * on the stack and the new input operator is +. As the precedence of the + operator is less than the * operator, the operands of the multiplication has already been sent to the postfix expression. Now, we should send the * operator to the postfix form. The plus operator (+) will wait. When the while loop sends all such operators to the postfix string, it will push the new operator to the stack that is in ‘c’. It has to wait till we get the second operand. Then we will again get the input. On the completion of the input, the while loop will be finished. There may be a case that input may be completed even at the time when there are still some elements on the stack. These are operators. To check this, we have another while loop. This loop checks if the stack is not empty, pops the operator and put it in the postfix string. Let’s take a look at a comprehensive example to understand it. In case of the infix expression, A + B * C, we have three columns, one each for input symbol, the postfix expression and the stack respectively. Now let’s execute the pseudo code. First of all, we get the ‘A’ as input. It is an operand so we put it on the postfix string. The next input is the plus operator (+) which will be pushed on the stack. As it is an operator and we need two operands for it. On having a look at the expression, you might have figure out that the second operand for the plus operator is B*C. The next input is the operand B being sent to the postfix expression form. The next thing we get is the input element as ‘*’. We know that the precedence of * is higher than that of the +. Let’s see how we can do that according to our pseudo code. The prcd(s.top(), op) takes two operands. We will get the top element of the stack i.e. + will be used as first argument. The second argument is the input operator i.e. *. So the function call will be as prcd(+, *) while the function returns false because the precedence of the plus operator is not higher than the multiplication operator. So far, we have only one operand for multiplication i.e. B. As multiplication is also a binary operator, it will also have to wait for the second operand. It has to wait and the waiting room is stack. So we will push it on the stack. Now the top element of the stack is *. The next symbol is ‘C’. Being an operand, C will be added to the postfix expression. At this point, our input expression has been completed. Our first ‘while loop’ executes till the end of input. After the end of the input, the loop will be terminated. Now the control goes to the second while loop which says if there is something on the stack, pop it and add it the postfix expression. In this case, we have * and + on the stack. The * is at the top of the stack. So when we pop, we get * which is at the top of the stack and it will be added to the postfix expression. In the result of second pop, we get the plus operator (+) which is also added to the postfix expression. The stack is empty now. The while loop will be terminated and postfix expression is formed i.e. ABC*+.

Symbol postfix stack
A A
+ A +
B AB +
* AB *
+
C ABC *
+
ABC* +
ABC*+

If we have to convert the infix expression into the postfix form, the job is easily done with the help of stack. The above algorithm can easily be written in C++ or C language, specially, if you already have the stack class. Now you can convert very big infix expressions into postfix expressions. Why we have done this? This can be understood with the help of the example of spreadsheet programming where the value of cell is the evaluation of some expression. The user of the spreadsheets will use the infix expressions as they are used to it.
Sometimes we do need the parenthesis in the infix form. We have to evaluate the lower precedence operator before the higher precedence operator. If we have the expression (A+B) *C, this means that we have to evaluate + before the multiplication. The objective of using parenthesis is to establish precedence. It forces to evaluate the expression first of all. We also have to handle parenthesis while converting the infix expression into postfix one. When an open parenthesis ‘(‘ is read, it must be pushed on the stack. This can be done by setting prcd(op,‘(‘ ) to be FALSE. What is the reason to put the parenthesis on the stack? It is due to the fact that as long as the closing parenthesis is not found, the open parenthesis has to wait. It is not a unary or binary operator. Actually, it is a way to show or write precedence. We can handle the parenthesis by adding some extra functionality in our prcd function. When we call prcd(op, ‘(‘), it will return false for all the operators and be pushed on the stack. Also, prcd( ‘(‘,op ) is FALSE which ensures that an operator after ‘(‘ is pushed on the stack. When a ‘)’ is read. All operators up to the first ‘(‘ must be popped and placed in the postfix string. To achieve this our function prcd( op,’)’ ) should return true for all the operators. Both the ‘(‘ and the’)’ will not go to the postfix expression. In postfix expression, we do not need parenthesis. The precedence of the operators is established in such a way that there is no need of the parenthesis. To include the handling of parenthesis, we have to change our algorithm. We have to change the line s.push(c) to:
if( s.empty() || symb != ‘)’ )
s.push( c );
else
s.pop(); // discard the ‘(‘
If the input symbol is not ‘)’ and the stack is not empty, we will push the operator on the stack. Otherwise, it is advisable to pop the stack and discard the ‘(‘. The following functionality has to be added in the prcd function.
prcd( ‘(‘, op ) = FALSE for any operator
prcd( op, ‘)’ ) = FALSE for any operator other than ‘)’
prcd( op, ‘)’ ) = TRUE for any operator other than ‘(‘
prcd( ‘)’, op ) = error for any operator.

Conversion from infix to postfix
During the process of conversion, there may be need of parenthesis in the infix especially at the times when we want to give a higher precedence to an operator of lower precedence. For example, if there is a + operator and * operator in an expression and a programmer wants the execution of addition before the multiplication. To achieve this object, it is necessary to put parentheses around the operands of + operator. Suppose, there is the expression A + B * C in which we want to give the precedence to the + operator over * operator. This expression will be written as (A + B) * C. Now we are going to discuss the conversion of infix expression that includes parentheses to the postfix expression. We have defined the return values for opening ‘(‘and closing ‘)’ parentheses in the precedence function. Let’s try to understand this process with the help of an example of converting the infix expression (A + B) * C into a postfix expression. We will see how our algorithm, discussed earlier, converts this infix expression into a postfix expression. To carry out the process of conversion we have three columns symbol, postfix and stack. The column symbol has the input symbols from the expression. The postfix column has the postfix string (expression) after each step and the stack is used to put the operators on it. The whole process of converting the infix notation into a postfix is given in the following table. This process of conversion is completed in eight steps. Each of the rows of the table depicts one step.
Step No. Symbol Postfix Stack
1 ( (
2 A A (
3 + A (+
4 B AB (+
5 ) AB+
6 * AB+ *
7 C AB+C *
8 AB+C*
First of all, there is the input symbol ‘(‘(i.e. opening parenthesis). As this is not an operand, it may be put on the stack. The next input symbol is ‘A’. Being an operand it goes to the postfix string and the stack remains unchanged. Then there is + operator of binary type. Moreover, there is one operand in the postfix string. We push this + operator on the stack and it has to wait for its second operand. Now in the input symbol, there is an operand ‘B’. We put his operand in the postfix string. Then after this, there is the closing parenthesis ‘)’ in the input symbol. We know that the presence of a closing parenthesis in the input means that an expression (within the parentheses) has been completed. All of its operands and operators are present with in the parentheses. As studied in the algorithm, we discard a closing parenthesis when it comes in the input. Then the operators from the stack are popped up and put in the postfix string. We also pop the opening parenthesis and discard it as we have no need of opening as well as closing parenthesis in the postfix notation of an expression. This process is carried out in the 5th row of the table. The + operator is put in the postfix string. We also discard the opening parenthesis, as it is not needed in the postfix.
Now the next input symbol is *. We put this operator on the stack. There is one operand for the * operator i.e. AB+. The * operator being a binary operator, has to wait for the second operand. ‘C’ is the Next input symbol that is an operand. We put it in the postfix string. After this, the input string (expression) ends so we come out of the loop. We check if there is any thing on the stack now? There is * operator in the stack. We pop the operator and put it into the postfix string. This way, we get the postfix form of the given infix expression that becomes AB+C*. In this postfix expression, the + operator is before the * operator. So addition operation is done before the multiplication. This is mainly due to the fact that in the infix expression, we have put parentheses to give + operator the precedence higher than the * operator. Note that there are no parentheses in the postfix form of the given infix expression.
Now we apply the evaluation algorithm on this postfix expression (i.e. AB+C*). The two operands A and B, will go to the stack. Then operator + will pop these operands from the stack, will add them and push the result back on the stack. This result becomes an operand. Next ‘C’ will go to the stack and after this * operator will pop these two operands (result of addition and C). Their multiplication will lead to the final result. The postfix notation is simple to evaluate as compared to the infix one. In postfix, we need not to worry about what operation will be carried first. The operators in this notation are in the order of evaluation. However, in the infix notation, we have to force the precedence according to our requirement by putting parentheses in the expression. With the help of a stack data structure, we can do the conversion and evaluation of expressions easily.

November 13, 2012

Stack implementation through Linked list in C

We can avoid the size limitation of a stack implemented with an array, with the help of a linked list to hold the stack elements. As needed in case of array, we have to decide where to insert elements in the list and where to delete them so that push and pop will run at the fastest. Primarily, there are two operations of a stack; push() and pop(). A stack carries lifo behavior i.e. last in, first out. You know that while implementing stack with an array and to achieve lifo behavior, we used push and pop elements at the end of the array. Instead of pushing and popping elements at the beginning of the array that contains overhead of shifting elements towards right to push an element at the start and shifting elements towards left to pop an element from the start. To avoid this overhead of shifting left and right, we decided to push and pop elements at the end of the array. Now, if we use linked list to implement the stack, where will we push the element inside the list and from where will we pop the element? There are few facts to consider, before we make any decision:
Insertion and removal in stack takes constant time. Singly linked list can serve the purpose. Hence, the decision is to insert the element at the start in the implementation of push operation and remove the element from the start in the pop implementation.
clip_image001
clip_image002
There are two parts of above figure.On the left hand, there is the stack implemented using an array. The elements present inside this stack are 1, 7, 5 and 2. The most recent element of the stack is 1. It may be removed if the pop() is called at this point of time. On the right side, there is the stack implemented using a linked list. This stack has four nodes inside it which are liked in such a fashion that the very first node pointed by the head pointer contains the value 1. This first node with value 1 is pointing to the node with value 7. The node with value 7 is pointing to the node with value 5 while the node with value 5 is pointing to the last node with value 2. To make a stack data strcuture using a linked list, we have inserted new nodes at the start of the linked list.
We are going to implement stack through linked list. Here is the code of stack implementation in C.



#include "stdio.h"
#include "stdlib.h"
#include "conio.h"



void pop();
void push(int value);
void display();


struct node
{
    int data;
    struct node *link;
};

struct node *top=NULL,*temp;

int main()
{
    int choice,data;
  
   
    while(1) //infinite loop is used to insert/delete infinite number of elements in stack
    {
       
        printf("\n1.Push\n2.Pop\n3.Display\n4.Exit\n");
        printf("\nEnter ur choice:");
        scanf("%d",&choice);
        switch(choice)
        {
        case 1:  //To push a new element into stack
           
           
            printf("Enter a new element :");
            scanf("%d",&data);
            push(data);
            break;
           
        case 2: // pop the element from stack
            pop();
            break;
           
        case 3: // Display the stack elements
            display();
            break;
        case 4: // To exit
            exit(0);
        }
       
    }     
getch();
return 0;
}

push(int data)
{
         temp=(struct node *)malloc(sizeof(struct node)); // creating a space for the new element.
         temp->data=data;
            temp->link=top;
            top=temp;
                    
}

pop()
{
            if(top!=NULL)
            {
                printf("The poped element is %d",top->data);
                top=top->link;
            }
            else
            {
                printf("\nStack Underflow");   
            }
           
}

display()
{
         temp=top;
            if(temp==NULL)
            {
                printf("\nStack is empty\n");
            }
           
            while(temp!=NULL)
            {
                printf(" %d ->",temp->data);
                temp=temp->link;
            }
               
}





November 9, 2012

Sessional 2 Assignment

Create a network topology of your own choice. Create a rather innovative scenario in which you can apply the following:

  • DHCP
  • DNS
  • VLAN
  • STP
  • VTP

Note: This assignment must be done individually. Plagiarism will not be tolerated. Any two topologies match will get 0 marks. Your Assignment will be checked next week in your first lab. No assignment will be checked after that. All the helping material is available on this site in case you need it. Bring your assignments in .pkt format, email it to yourself so that you can access it in lab.  Have a nice weekend.

GOOD LUCK

BroadCast and Collision domains

BroadCast Domain

A broadcast domain is a logical division of a computer network, in which all nodes can reach each other by broadcast at the data link layer. A broadcast domain can be within the same LAN segment or it can be bridged to other LAN segments. A broadcast domain encompasses a set of devices for  when one of the devices sends a broadcast, all the other devices receive a copy of the broadcast. For example, switches flood broadcasts and multicasts on all ports. Because broadcast frames are sent out all ports, a switch creates a single broadcast domain.
Any computer connected to the same repeater or switch is a member of the same broadcast domain. Further, any computer connected to the same set of inter-connected switches/repeaters is a member of the same broadcast domain. Routers and other higher-layer devices form boundaries between broadcast domains.
This is as compared to a collision domain, which would be all nodes on the same set of inter-connected repeaters, divided by switches and learning bridges. Collision domains are generally smaller than broadcast domains. Broadcast domains are only divided by layer 3 network devices such as routers or layer 3 switches. However,some layer two network devices are also able to divide the collision domains. A broadcast domain is a set of NICs for which a broadcast frame sent by one NIC is received by all other NICs in the same broadcast domain 

Collision Domain

A collision domain is the set of LAN interfaces whose frames could collide with each other, but not with frames sent by any other devices in the network. The collision is happened when to computer in same time want to use bandwidth. The CSMA/CD algorithm that deals with the issue of collisions, and some of the differences between how hubs and switches operate to create either a single collision domain (hubs) or many collision domains (switches). Generally speaking in easy terms, A collision domain is a set of network interface cards (NIC) for which a frame sent by one NIC could result in a collision with a frame sent by any other NIC in the same collision domain.
Only one device in the collision domain may transmit at any one time, and the other devices in the domain listen to the network in order to avoid data collisions. Because only one device may be transmitting at any one time, total network bandwidth is shared among all devices. Collisions also decrease network efficiency on a collision domain; if two devices transmit simultaneously, a collision occurs, and both devices must retransmit at a later time.
Modern wired networks use a network switch to eliminate collisions. By connecting each device directly to a port on the switch, either each port on a switch becomes its own collision domain (in the case of half duplex links) or the possibility of collisions is eliminated entirely in the case of full duplex links.
When creating any Ethernet LAN, you use some form of networking devices—typically switches today—a few routers, and possibly a few hubs. The different parts of an Ethernet LAN may behave differently, in terms of function and performance, depending on which types of devices are used. These differences then affect a network engineer’s decision when choosing how to design a LAN. The terms collision domain and broadcast domain define two important effects of the process of segmenting LANs using various devices. 

The Importance  of Collision and Broadcast Domains on LAN Design

When designing a LAN,  when choosing the number of devices in each collision domain and broadcast domain. First, consider the devices in a single collision domain for a moment. For a single collision domain: 
  1. The devices share the available bandwidth in network.
  2. The devices may inefficiently use that bandwidth due to the effects of collisions
For example, you might have ten PCs with 10/100 Ethernet NICs. If you connect all ten PCs to ten different ports on a single 100-Mbps hub, you have one collision domain, and the PCs in that collision domain share the 100 Mbps of bandwidth.
That may work well and meet the needs of those users. However, with higher traffic loads, the hub’s performance would be worse and you need a switch . Using a switch instead of a hub, with the same topology, would create ten different collision domains, each with 100 Mbps of bandwidth. Also, with only one device on each switch interface, no collisions would occur. This means that you could enable full duplex on each interface, effectively giving each interface 200 Mbps.
Using the switches instead of hubs seems like an obvious choice given the overwhelming performance benefits. Frankly, most new installations today use switches exclusively.

November 7, 2012

VTP on Packet Tracer

VLAN Trunk Protocol (VTP) reduces administration in a switched network. When you configure a new VLAN on one VTP server, the VLAN is distributed through all switches in the domain. This reduces the need to configure the same VLAN everywhere. Let us apply VTP on packet tracer.
 1
Let us see vtp status by applying the command “show vtp status”.
 forall
Let us set domain name. In VTP there should be only one domain name through out to synchronize between all the switches.
 2
Domain name is set.
3
In order for changes made in one switch to take place in other switches as well. we will have to trunk the interfaces. Only those interfaces that are connected.
88
Or we can select a range of interfaces and trunk them.
 99
Now, when we check the status on other switches we can see that the domain name has been set on all the other switches as well.
 aftall
Let us create VLAN.
 4
This vlan is shown in other switch due to the trunking .
 5
Now, there are three modes in a vtp.
i. Server
ii. Client
iii. Transparent
We are going to apply all three modes on different switches. We can create vlan in server mode, only use them in client mode. But the changes made in transparent mode are independent and does not have affect on other modes.
jj

Let us turn the switch 7 to transparent mode and create a vlan in it.
 6
The vlan created in transparent mode is not visible in the other modes.
 7
If we change the mode of vtp from server to client , we are unable to create vlan now in the client mode as shown in the message below.
 8

November 6, 2012

Spanning Tree Protocol on Packet Tracer

Let us apply STP on packet tracer. Let us develop a basic topology like the one in the following diagram.
y
As we can see in the above diagram that some light are green while others are orange. Y is it so ? We will see that in a moment. Let us try to communicate between two Hosts. Assign IP addresses to all hosts
uu
As we can see in the figure below, the communication is successful. It is due to the spanning tree protocol applied on the switch by default. It provides us with the loop free environment. It calculates the cost of each path and provides us with the one that has the minimum cost. That is the reason that some links are up while others are down with the orange light.
uiu
So let us see what happens if we remove the spanning tree protocol from this topology.
fff
We will remove STP from all the switches one by one.
gfgf

gg
tt
After removing STP, we have observed by the following diagram, a couple of changes. i.e. all the lights are green. In fact, some are dark green. Some lights are blinking, while some are not. This is due to fact that as there is no protocol to decide that which path to choose as we have removed STP.
d
Now that if we try to communicate between any hosts it will fail and communication is disabled.
lmklkjlk

VLAN on Packet Tracer

In this tutorial, we are going to apply VLAN on packet tracer. Let us create a topology with one switch and multiple hosts like in the figure below.
1
if we go to the switch and enter the command “show vlan ”. It shows the following. 
 afadsfadsf
As we can see in the figure above all the interfaces are being displayed and they are all the part of the default vlan 1. Now let us apply vlans on the switch. We are going to create three vlans as follows.
 dsgs
Now, that we have created the vlans. Lets see if they are visible to us.
ds
In the above figure, vlans are visible. Now, we are going to assign interfaces to vlans. They are two ways to do this.
i. We can select an interface and assign that interface to a specific vlan
ii. We can select multiple interfaces (range of interfaces) at once and assign those interfaces to vlan.
In the figure below, we have done both of these.

yyy
Now, when we write “show vlan “ command and observe it. We will realize that interfaces have been assigned to desired vlans respectively.
 ggggggggg
Let us assign IP addresses to PCs. Open the PC.
 fff
Assign IP address.
 kljljk
After assigning IP addresses, when we try to communicate between two PCs belonging to two different vlans, it will fail. Thus, we have achieved our purpose.
 klj
The message sending failure status can be seen in the bottom right corner.
 uu

November 4, 2012

VLAN

VLAN or  Virtual Local Area Network is a phenomenon which is used to logically separate or combine a network. It is used to configured one or more devices, so that they can communicate, as if they were attached to the same wire, when in fact they are located on a number of different LAN segments. Because VLANs are based on logical instead of physical connections, they are extremely flexible. 

What is VLAN

VLAN is a concept of partitioning of a physical network, so that distinct broadcast domains are created. This is usually achieved on switch or router devices. Simpler devices only support partitioning on a port level, so sharing VLANs across devices requires running dedicated cabling for each VLAN.
Grouping hosts with a common set of requirements regardless of their physical location by VLAN can greatly simplify network design. A VLAN has the same attributes as a physical local area network (LAN), but it allows for end stations to be grouped together more easily even if they are not on the same network switch. Without VLANs, a switch considers all interfaces on the switch to be in the same broadcast domain.To physically replicate the functions of a VLAN would require a separate, parallel collection of network cables and equipment separate from the primary network.

 How VLAN's work

When a LAN bridge receives data from a workstation, it tags the data with a VLAN identifier indicating the VLAN from which the data came. This is called explicit tagging. It is also possible to determine to which VLAN the data received belongs using implicit tagging. In implicit tagging the data is not tagged, but the VLAN from which the data came is determined based on other information like the port on which the data arrived. Tagging can be based on the port from which it came, the source Media Access Control (MAC) field, the source network address, or some other field or combination of fields. VLAN's are classified based on the method used. To be able to do the tagging of data using any of the methods, the bridge would have to keep an updated database containing a mapping between VLAN's and whichever field is used for tagging. For example, if tagging is by port, the database should indicate which ports belong to which VLAN. This database is called a filtering database. Bridges would have to be able to maintain this database and also to make sure that all the bridges on the LAN have the same information in each of their databases. The bridge determines where the data is to go next based on normal LAN operations. Once the bridge determines where the data is to go, it now needs to determine whether the VLAN identifier should be added to the data and sent. If the data is to go to a device that knows about VLAN implementation (VLAN-aware), the VLAN identifier is added to the data. If it is to go to a device that has no knowledge of VLAN implementation (VLAN-unaware), the bridge sends the data without the VLAN identifier.

 

Why use VLAN's?

VLAN offer a number of advantages over traditional LAN.

    Physical topology independence

    VLANs provide independence from the physical topology of the network by allowing physically diverse workgroups to be logically connected within a single broadcast domain. If the physical infrastructure is already in place, it now becomes a simple matter to add ports in new locations to existing VLANs if a department expands or relocates. These assignments can take place in advance of the move, and it is then a simple matter to move devices with their existing configurations from one location to another. The old ports can then be "decommissioned" for future use, or reused by the department for new users on the VLAN.

    Performance
    In networks where traffic consists of a high percentage of broadcasts and multicasts, VLAN's can reduce the need to send such traffic to unnecessary destinations. For example, in a broadcast domain consisting of 10 users, if the broadcast traffic is intended only for 5 of the users, then placing those 5 users on a separate VLAN can reduce traffic.
    Compared to switches, routers require more processing of incoming traffic. As the volume of traffic passing through the routers increases, so does the latency in the routers, which results in reduced performance. The use of VLAN's reduces the number of routers needed, since VLAN's create broadcast domains using switches instead of routers. Switched networks by nature will increase performance over shared media devices in use today, primarily by reducing the size of collision domains. Grouping users into logical networks will also increase performance by limiting broadcast traffic to users performing similar functions or within individual workgroups. Additionally, less traffic will need to be routed, and the latency added by routers will be reduced

    Formation of Virtual Workgroups
    Nowadays, it is common to find cross-functional product development teams with members from different departments such as marketing, sales, accounting, and research. These workgroups are usually formed for a short period of time. During this period, communication between members of the workgroup will be high. To contain broadcasts and multicasts within the workgroup, a VLAN can be set up for them. With VLAN's it is easier to place members of a workgroup together. Without VLAN's, the only way this would be possible is to physically move all the members of the workgroup closer together.
    Despite this saving, VLAN's add a layer of administrative complexity, since it now becomes necessary to manage virtual workgroups.

    Reduced Cost
    VLAN's can be used to create broadcast domains which eliminate the need for expensive routers.

    Security
    Periodically, sensitive data may be broadcast on a network. In such cases, placing only those users who can have access to that data on a VLAN can reduce the chances of an outsider gaining access to the data. VLAN's can also be used to control broadcast domains, set up firewalls, restrict access, and inform the network manager of an intrusion.

    Improved manageability
    VLANs provide an easy, flexible, less costly way to modify logical groups in changing environments. VLANs make large networks more manageable by allowing centralized configuration of devices located in physically diverse locations.

C program to Read From a File

#include <stdio.h> #include <stdlib.h> void main() {     FILE *fptr;     char filename[15];     char ch;   ...