GROUP03_AMAK:Problems Faced For Group A Project

The group A presentation of our group was to be held on 4th november, but it got postponed to 11th due to the talents day. Some of the group members were participating in the talents day & because of the practices in the evenings after college we could not meet up to prepare presentation. The week after the talents day when our presentation was suppose to be held, we had to submit a report in File Structures. So since the group members were divided into different groups we could not meet up until the 9th of November.We somehow managed the two days time to prepare for the same.

GROUP03_AMAK:GO Back-N ARQ

Go back -N Automatic repeat request is the second protocol of the noisy channel. It is used in error control. It has an advantage over the stop and wait that it can send multiple frames while waiting for an acknowledgement from the receiver.

In the Go Back-N the size of the sender’s window is 2^m -1while the size of the receiver’s window is still 1. The sequence of frame numbers range from 0 to 2^m-1 which is the same as the size of the sender’s window. The sender’s window contain two pointers namely s_f and s_n. s_f pointer is a pointer which points to the frame in the senders window whose acknowledgement is expected next and s_n pointer is a pointer which points to the frame to be sent next.

The sender sends out multiple frames. The receiver only has a window size of one and it accepts only the frame that it was expecting next. The receiver stores a copy of these frames. Once the receiver sends an acknowledgement for this frame the sender’s window slides by one position. The receiver can however send cumulative acknowledgements i.e one acknowledgement for say 5 frames. The sender’s window will also then correspondingly slide by 5.

Now let us see what happens when the sender does not get back an acknowledgement. The acknowledgement may not be received due to the following reasons:-

• Acknowledgement sent by receiver gets lost.
• The receiver receives a corrupted frame and hence does not respond to the sender.
• The frame that the receiver is expecting gets lost due to some reason and therefore no question of the receiver sending an acknowledgement.

If the sender does not get back the acknowledgement for the frame pointed to by the s_f pointer, then it waits for the time out and resends all the frames till the frame pointed to by the s_n pointer. This is continuously carried out until it receives an acknowledgement for the frame pointed by the s_f pointer. Thus we see that the sender has to go back -N frame and resend them.

GROUP03_AMAK:Stop and Wait ARQ

Stop and wait Automatic Repeat Request is a data-link layer protocol for noisy channels. It is used for error control and detects corrupted frames. It also handles lost frames. In this protocol the sender keeps a copy of the sent frame until it receives an acknowledgement from the receiver. The size of the sender and the receiver’s window is 1.

In stop and wait ARQ the error control is established by discarding the corrupted frame and the silence of the receiver. It is also possible that a frame may get lost during transmission, this protocol provides us with a solution to this. In this protocol the sequence number of the frames can either be 0 or 1. When a sender sends a particular frame say frame0, the receiver on receiving this frame sends an acknowledgement frame1 which means that the next frame that it is expecting is frame 1. The sender only on receiving an acknowledgement will send the next frame. If the sender does not receive the acknowledgement, then it has a time out period for the frame that was sent after which the sender resends the frame till it receives an acknowledgement. The sender may not receive an acknowledgement in the following cases:-

• The acknowledgement sent by the receiver is lost.
• The frame that the receiver receives is corrupted and hence is silent and did not send an acknowledgement.
• The frame sent by the sender is itself lost so the receiver who has not received the frame cannot respond with the acknowledgement.

The sender waits for a particular time called as the time out period and if it does not receive an acknowledgement within this period then after the time out it resends the frame automatically until it receives an acknowledgement.

The sender on receiving an acknowledgement moves to the next frame.

The drawback of this protocol is that it does not support pipelining. It means that the sender can send a new frame only if it has received an acknowledgement from the receiver. Until it receives acknowledgement it must resend the frame.

GROUP03_AMAK:HAMMING CODE

Hamming code is an error detection and correction method. It is a block coding method in which the given data is divided into a number of blocks of size k bits each. This is called as the dataword. To detect and correct as we know we have to add redundant bits to the data. We add r number of redundant bits. This leaves us with a codeword which is of size n bits such that n=k+r. For each of the 2^k dataword there can be only one possible codeword so there are 2^k valid codewords. With n bit codeword it is possible to generate 2ⁿ codewords. Of the 2ⁿ codewords only 2^k are valid codewords the rest i.e. 2ⁿ-2^k are invalid.

The redundant bits are generated using a particular set of formulae. Let us take an example of 7 bit codeword which is to be generated from a 4 bit dataword. The dataword is represented as shown below. The 3 redundant bits that are to be appended to the 4bit data word are calculated using the following formulae:-

1	0	1	0
a3	a2	a1	a0

 

R_o =a₂ + a₁ + a₀ Modulo-2

R₁= a₃ + a₂ + a₁ Modulo-2

R₂= a₁+ a₀ + a₃ Modulo-2

These redundant bits are appended to the 4bit dataword and sent as a 7 bit codeword. For the taken example 1010 the redundant bits are

R_o= 0 + 1 +0 = 1

R₁= 1 + 0 + 1 = 0

R₂=1 + 0 + 1 = 0

Thus the resultant codeword along with the notation is:-

1	0	1	0	0	0	1
a3	a2	a1	a0	r2	r1	r0

 

On the receiver side this 7 bit codeword is decoded by the calculation of the syndrome. The syndrome is used to detect the presence of error and also to identify the position of the error. Let us take for example that there occurs an error in the bit position 7 during transmission. The received codeword and the notation are shown below. The notation has been changed because there are chances of an error being introduced into the codeword. Now we calculate the syndrome using the following formulae:-

 

0	0	1	0	0	0	1
b3	b2	b1	b0	q2	q1	q0

 

s₀ = b₂ + b₁ + b₀ + q₀ modulo-2

s₁ = b₃ + b₂ + b₁ + q₁ modulo-2

s₂ = b₁ + b₀ + b₃ + q₂ modulo-2

If we get a syndrome value having all bits as zeros then there is no error in transmission or error cannot be detected since it has changed to another valid codeword. On the other hand if the syndrome is non-zero it means there is an error.

so the values of the syndrome are:-

s₀=0 + 1 + 0 + 1 = 0

s₁=0 + 0 + 1 + 0 = 1

s₂=1 + 0 + 0 + 0 = 1

From the table shown below we can find the position of the error. After finding the position of the error the corresponding bit is flipped.

SYNDROME	000	001	010	011	100	101	110	111
ERROR	None	q0	q1	b2	q2	b0	b3	b1

As we can see from the table the bit position of the error is b3. So this bit is flipped and the codeword becomes 1010001, which was the correct codeword that was sent. Hence the error has been successfully detected and corrected.

Hamming Distance: It is the number of bit changes between 2 codewords. It is obtained by XORing the two codewords and counting the number of 1’s in the result.

Minimum Hamming Distance: It is the smallest hamming distance that is obtained by finding the hamming distance between all possible pairs of codewords.

For the example, it had a hamming distance of 3. So the receiver can detect upto a maximum of only 2 errors as if there are 3 errors the codeword would have changed to another valid codeword. In the above example we can correct upto a maximum of only 1 error.

GROUP03_AMAK:PROBLEMS FACED AND SOLVED For GROUP B Project

Problem Statement:

implement the hamming code C(4,7) i.e for a 4 bit dataword and 7bit codeword which can detect upto 2 errors and correct 1 error.

Problem Faced:

while implementing the code we have generated the codeword using bitset data type. The received data was first read in a long int variable and this data was assigned to the received data bitset. But we noticed that the entire data was not taken into the bitset variable on the receivers side.

Problem Solution: we printed the long int variable and the value was being shown in exponential notation. So we thought that it was because the data being long was displayed caused a problem in copying data from the long int variable into the bitset variable. We noticed that this problem was not faced when we entered the dataword of the sender in integer format and this passed to the bitset dataword variable through the constructor we faced no such problem and the dataword was being printed as desired. So we decided to directly enter the data into the bitset variable and this solved our problem.

Problem Faced: The syndrome value that was generated such as 001,010,011 caused problem in being detected by the if-else ladder. We noticed that when the syndrome that was generated was among these three values then the program did not correct the erroneous position and also did not tell where the position of the error was.

Problem Solution: We noticed if any number of 0′s were preceding a 1 these were not taken into consideration by the program. So for all syndrome values that had preceding 0′s we deleted the 0′s and tried to run the program which generated syndromes with the mentioned values we found that it worked perfectly. We noticed that when we removed the additional 0′s on the left hand side then the actual position of error was located and the corresponding bit was flipped.

GROUP03_AMAK:QUESTION AND ANSWERS

1.)Are there any other codes other than C(7,4) that you have taken??Could you give examples??

Ans: yes there we have come across C(5,4) in our 3rd semester Digital design class. Here the dataword is of zize 4 bits and the codeword of size 5 bits. The fifth bit is the parity bit.

Question By MUNAF answered by ANKITA S

2)What are the advantages of CRC over other codes??

Ans: In CRC we have the capability to detect burst errors. If  we want to detect a burst error of say 18 bits then if we take a generator polynomial of size 19 or higher it will catch the error.

Question By MAYANK SINHA answered by KRISH R B

3)Why can we detect only s errors for a hamming distance of s+1??

Ans: If there occur s+1 changes into the code then the resultant codeword that will be generated after he codeword will also be another valid codeword. This means that the error cannot be caught.

Question By Ameet G answered by ANKITA S

4) Why is error correction more difficult when compared to error detection??

Ans: In error detection the receiver only needs to find only if the codeword received is invalid or valid. If it is invalid it is discarded otherwise it is accepted. On the other hand in error correction the receiver first needs to detect the presence of error and then the position of error has to be found. To find the position of error we require more redundant bits. Hence error correction is more difficult when compared to error detection.

Question by MURGESH answered by ANKITA S

GROUP03_AMAK:MANDATORY BLOG

• Team Name: AMAK
• Team Members: Ankita Singh (1MS07IS133), Mayank Jayaswal (1MS07IS047), Krish Rajan Bathija(1MS07IS038), Anshuj Jain (1MS07IS011)
• Group A Project Chosen: Network Protocol Analysis
• Group B Project Chosen: Error Detection And Correction
• Presentation Date of Group A Project (Completed / Not Completed as on Blog Date):Completed.
• Presentation Date of Group B Project (Completed / Not Completed as on Blog Date): Completed.
• Group A PPT Uploaded(Yes or No): YES
• Group B PPT Uploaded(Yes or No): YES
• Group A Project Report Made(Yes or No): NO
• Group B Project Report Made(Yes or No): NO
• Group A Project PROBLEMS FACED and SOLVED Blog Uploaded(Yes or No): YES
• Group B Project PROBLEMS FACED and SOLVED Blog Uploaded(Yes or No): Yes

GROUP03_AMAK:ERROR DETECTION METHODS

Error detection is the ability to detect the presence of errors caused by noise or other impairments during transmission from the transmitter to the receiver. There are various error detection schemes used, all of these employ the usage of additional bits that are added to the data these additional bits added to the original data are known as check bits. These are derived from the original data by making use of some deterministic algorithms. The various methods used in the detection of errors are as follows:-
• REPETITION: In this method of error detection the original data to be is sent repeatedly a fixed number of times. For example the data we want to send is ‘01101’ and the data is sent thrice so the transmitted data will be ‘01101 01101 01101’. If in the received group one group is not the same as the other two, we can determine that an error has occurred.

• PARITY SCHEMES: in this error detection scheme one extra bit is added to the original data. This is set to 1 if the number of ones in the original data is odd else it is cleared to 0. We can identify the error if the parity bit changes value. It can detect an error only if odd number of bits changes in value.

• HAMMING CODES: If more error-correcting bits are included with a message, and if those bits can be arranged such that different incorrect bits produce different error results, then bad bits could be identified. Suppose we are using 7bit data we make use of 3 parity bits which can identify not only if there is an error but also the position of the error is identified and corrected.

• CHECKSUM SCHEME: A checksum of a message is an arithmetic sum of message code words of a certain word length, for example byte values, and their carry value. The sum is negated by means of ones-complement, transferred as an extra code word extending the message. At the receiving end the message code is added up and the extra code is negated, then both these are compared to check if they are the same. If they are different an error has occurred.

• CYCLIC REDUNDANCY CHECK: The cyclic redundancy check considers a block of data as the coefficients to a polynomial. For example data to be transmitted is 0110 the equivalent polynomial is x^2+x. This polynomial is then divided by a fixed, predetermined polynomial(x^3+x+1.etc). The coefficients of the result of the division are taken as the redundant data bits and these are appended to the original data. On reception, one can recompute the CRC from the original data bits and compare this with the CRC that was received. A mismatch indicates that an error occurred.
• Hamming distance based checks: Hamming distance is the number of bits if changed in the original data cause the bit flips to become invisible. If we want to detect d bit errors in an n bit word we can map every n bit word into a bigger n+d+1 bit word so that the minimum Hamming distance between each valid mapping is d+1. This way, if one receives a n+d+1 word that doesn’t match any word in the mapping (with a Hamming distance x <= d+1 from any word in the mapping) it can successfully detect it as an erroneous word. Even more, d or fewer errors will never transform a valid word into another, because the Hamming distance between each valid word is at least d+1, and such errors only lead to invalid words that are detected correctly. Given a stream of m*n bits, we can detect x <= d bit errors successfully using the above method on every n bit word. In fact, we can detect a maximum of m*d errors if every n word is transmitted with maximum d errors.

GROUP03_AMAK:PROXY SERVERS

A proxy server is a server that acts as an intermediary for requests from clients seeking resources from other servers. A proxy server can be an application or a computer system. The client is connected to the proxy server which in turn is connected to a network. So the client has access to a network through the proxy server. Proxy servers have the ability of filtering traffic on the network. If a client requests a service such as a file, web page from another server on the internet the request is first sent to the proxy server which validates the request according to its filtering rules.

A proxy server may sometimes be configured to alter client’s requests or even the server’s response. It also does cater to the client’s requests without contacting the web server. In this case the request is catered to by the proxy server which has the web pages stored in the cache of the proxy server. Suppose clients connected to a proxy server want to access the same web page, the proxy server sends the request to the remote server and stores the reply from the server in its cache. So now when the clients request for this page the page is retrieved directly from the proxy server’s cache instead of the remote server. This increases the speed of the connection as repeated requests to the remote server are avoided. A proxy server in a special case behaves as a gateway or tunnelling proxy also when it passes network traffic unfiltered. When the proxy server takes request from the clients and sends it to remote servers it is known as a forward proxy server.

Proxy servers can be of different types depending on the function they perform, they are as follows:-

• Caching Proxy Server: this proxy server keeps a local copy of frequently used requests and stores them in the cache. This accelerates the speed of access as pages are retrieved from the cache and thereby even reduce the cost of bandwidth usage.
• Web Proxy: A proxy server that focuses on World Wide Web traffic is called a web proxy. The most common use of a web proxy is to serve as a web cache. Most proxy programs  provide a means to deny access to certain URLs in a blacklist, thus providing content filtering.
• Content Filtering Web Proxy: This proxy server provides administrative control over the data that is sent over network. It is used to allow access to only relevant web pages. The method used to block certain web sites is using URL or DNS blacklist. This blacklist when created filters traffic to and from the URL and hence prevents the client from using that particular web page.
• Anonymizing Web Proxy: this proxy server is used to maintain anonymity on the internet. Some users are merely interested in anonymity on principle, to facilitate constitutional human rights of freedom of speech, for instance. The server receives requests from the anonymizing proxy server, and thus does not receive information about the end user’s address.

• Hostile proxy: this proxy server can be used to keep a check on all the information that is sent and received. All accessed pages and forms can be captured and analysed by the operator of the proxy server.
• Intercepting Proxy Server: An intercepting proxy combines a proxy server with a gateway or router. Connections made by client browsers through the gateway are diverted to the proxy without client-side configuration. Intercepting proxies are also commonly used by ISPs in some countries to save upstream bandwidth and improve customer response times by caching.
• Transparent Proxy Server: the term can be misleading as this proxy server acts as though the client’s requests are not being proxied. It does not modify the requests and responses from clients and servers respectively.
• Non Transparent Proxy: this proxy server modifies the client requests and responses from the server. The client can easily come to know that he is being proxied.
• Suffix proxy: A suffix proxy server allows a user to access web content by appending the name of the proxy server to the URL of the requested content.
• Reverse Proxy Server: this proxy server is installed in the neighbourhood of web servers. All traffic coming to a web server is then directed to the proxy server. This is done in case of secure web sites. The reverse proxy performs encryption so that the data cannot be intercepted and leaked.

The uses of proxy servers are:-

• Proxy servers are used to censor content on the web i.e. not allowing access some web pages.
• Proxy servers are used to increase the speed of access. This is done by storing frequently accessed resources in the cache.
• Proxy servers can be used to maintain anonymity on the web. It is used to hide the address of the user.
• These  servers can be used to make a given web page secure by adding encryption to it such as SSL encryption.

GROUP03_AMAK:NETWORK PROTOCOL ANALYSIS

Capsa Network Analyzer is an easy to use Ethernet network analyser(aka packet analyser) for network monitoring and troubleshooting purposes. It performs real time packet capturing, advanced protocol analysing, in-depth decoding. In this section we will see how capsa can be used for protocol analysis. It has a very user friendly and information rich tabbed view. Below is shown the start page of the application we click on start capture now button to then we get this form and over here we have enabled the checkbox for enable detail protocol statistics of each endpoint, enable conversation statistics of each endpoint and also enable detail statistics of packet size. Then click ok to start packet capture in real time.

After we finish capturing traffic click on stop button in the tool strip.  In the summary tab we get various kinds of information like the capture time, different errors, traffic, packet size distribution,  TCP packets and connections, HTTP analysis etc. Below is a snapshot showing the summary tab.

In the diagnosis tab we can get information which may require action to be taken by us. Some packets are shown that we need to take notice of such as these may be having slow response times from the servers, then there is the warning level of diagnostics which we may have to take action like a server may no longer be reachable which could be because the computer has been disconnected from the network.

In the endpoints tab we get information like the IP, MAC address of local host the packets it sends and receives their sizes, also shows the MAC address, URL of the web page. The number and size of packets sent and received by the server.

The next tab is the protocols tab. In this like in wire shark the packets along with the protocols used in communicating are shown. The various protocols that are used during the session are listed and if we want to know the packet information of each protocols we can do so by clicking on show details. In the screenshot below the packet details of HTTP protocol are shown along with the statistics of other protocols used. The packet information below shows the source, destination, size, the protocol used.

In the conversations tab the conversation between the network computers and the web servers is shown. The conversations are categorized into Physical, IP, TCP and UDP. On selecting the appropriate conversation we can see the source and destination’s MAC address (PHYSICAL conversation selected) or the IP addresses of the source and destination. Also shown will be the packets in each of the conversations along with the details like whether the packet was sent or received, its size. Shown below are the IP conversations, here endpoint1 is the local host and endpoint2 is the web server or another computer in the network.

In the matrix tab of the network analyser are shown the nodes used in the session i.e. the various URL’s that were accessed from the particular system.

In the packets tab we get information about individual packets. The information provided in this tab is similar to the information we get when we use wireshark. Also the packet information is displayed in HEX at the bottom of the screen. In the details of each packet we can get information like the source, destination of the packet. The ports used at either end. It also shows if the packet is received correctly or contains any errors when received by the destination. Below is a screenshot of the packets tab displaying the details of individual packet as well as the list of packets received.

The logs tab shows the log that is created during the session. It maintains different logs for HTTP requests,E-mails, messenger activities, etc. It shows the client’s IP address and the port number. The server URL and whether information is to be fetched(get) or posted (POST) onto the URL. It also gives us information if the server is found or not.

The next tab is the graphs tab. As we know that graphical data is easy to interpret even by layman. Capsa Network Analyzer provides us with a variety of graphs to view depending on the session. Here is a graph that can be used in TCP analysis. It’s called a TCP connection graph. It shows the TCP traffic in intervals of time. In this manner we can view the various graphs and analyse them.

thus we see that capsa network protocol analyzer is a very powerful tool. It provides us results that any one can understand.