BCA 2 UNIT 3
BCA 2 UNIT 3
BCA 2 UNIT 3
Error Detection
There are many reasons such as noise, cross-talk etc., which may help data to get corrupted during
transmission. The upper layers work on some generalized view of network architecture and are not aware of
actual hardware data processing.Hence, the upper layers expect error-free transmission between the systems.
Most of the applications would not function expectedly if they receive erroneous data. Applications such as
voice and video may not be that affected and with some errors they may still function well.
Data-link layer uses some error control mechanism to ensure that frames (data bit streams) are transmitted
with certain level of accuracy. But to understand how errors is controlled, it is essential to know what types
of errors may occur.
Types of Errors
There may be three types of errors:
Single bit error
The receiver simply counts the number of 1s in a frame. If the count of 1s is even and even parity is used, the
frame is considered to be not-corrupted and is accepted. If the count of 1s is odd and odd parity is used, the
frame is still not corrupted.
If a single bit flips in transit, the receiver can detect it by counting the number of 1s. But when more than one
bits are erro neous, then it is very hard for the receiver to detect the error.
Cyclic Redundancy Check (CRC)
CRC is a different approach to detect if the received frame contains valid data. This technique involves
binary division of the data bits being sent. The divisor is generated using polynomials. The sender performs a
division operation on the bits being sent and calculates the remainder. Before sending the actual bits, the
sender adds the remainder at the end of the actual bits. Actual data bits plus the remainder is called a
codeword. The sender transmits data bits as codewords.
1
At the other end, the receiver performs division operation on codewords using the same CRC divisor. If the
remainder contains all zeros the data bits are accepted, otherwise it is considered as there some data
corruption occurred in transit.
Error Correction
In the digital world, error correction can be done in two ways:
Backward Error Correction When the receiver detects an error in the data received, it requests back
the sender to retransmit the data unit.
Forward Error Correction When the receiver detects some error in the data received, it executes
error-correcting code, which helps it to auto-recover and to correct some kinds of errors.
The first one, Backward Error Correction, is simple and can only be efficiently used where retransmitting is
not expensive. For example, fiber optics. But in case of wireless transmission retransmitting may cost too
much. In the latter case, Forward Error Correction is used.
To correct the error in data frame, the receiver must know exactly which bit in the frame is corrupted. To
locate the bit in error, redundant bits are used as parity bits for error detection.For example, we take ASCII
words (7 bits data), then there could be 8 kind of information we need: first seven bits to tell us which bit is
error and one more bit to tell that there is no error.
For m data bits, r redundant bits are used. r bits can provide 2r combinations of information. In m+r bit
codeword, there is possibility that the r bits themselves may get corrupted. So the number of r bits used must
inform about m+r bit locations plus no-error information, i.e. m+r+1.
2
If the message is not altered, then it is called as systematic code. It means, the encryption of the data should
not change the data.
Convolution Codes
So far, in the linear codes, we have discussed that systematic unaltered code is preferred. Here, the data of
total n bits if transmitted, k bits are message bits and n−kn−k bits are parity bits.
In the process of encoding, the parity bits are subtracted from the whole data and the message bits are
encoded. Now, the parity bits are again added and the whole data is again encoded.
The following figure quotes an example for blocks of data and stream of data, used for transmission of
information.
The whole process, stated above is tedious which has drawbacks. The allotment of buffer is a main problem
here, when the system is busy.
This drawback is cleared in convolution codes. Where the whole stream of data is assigned symbols and then
transmitted. As the data is a stream of bits, there is no need of buffer for storage.
Hamming Codes
The linearity property of the code word is that the sum of two code words is also a code word. Hamming
codes are the type of linear error correcting codes, which can detect up to two bit errors or they can correct
one bit errors without the detection of uncorrected errors.
While using the hamming codes, extra parity bits are used to identify a single bit error. To get from one-bit
pattern to the other, few bits are to be changed in the data. Such number of bits can be termed as Hamming
distance. If the parity has a distance of 2, one-bit flip can be detected. But this can't be corrected. Also, any
two bit flips cannot be detected.
However, Hamming code is a better procedure than the previously discussed ones in error detection and
correction.
BCH Codes
BCH codes are named after the inventors Bose, Chaudari and Hocquenghem. During the BCH code design,
there is control on the number of symbols to be corrected and hence multiple bit correction is possible. BCH
codes is a powerful technique in error correcting codes.
For any positive integers m ≥ 3 and t < 2m-1 there exists a BCH binary code. Following are the parameters of
such code.
Block length n = 2m-1
Number of parity-check digits n - k ≤ mt
Minimum distance dmin ≥ 2t + 1
This code can be called as t-error-correcting BCH code.
3
Cyclic Codes
The cyclic property of code words is that any cyclic-shift of a code word is also a code word. Cyclic codes
follow this cyclic property.
For a linear code C, if every code word i.e., C = C1,C2,......CnC1,C2,......Cn from C has a cyclic right shift of
components, it becomes a code word. This shift of right is equal to n-1 cyclic left shifts. Hence, it is invariant
under any shift. So, the linear code C, as it is invariant under any shift, can be called as a Cyclic code.
Cyclic codes are used for error correction. They are mainly used to correct double errors and burst errors.
Hence, these are a few error correcting codes, which are to be detected at the receiver. These codes prevent
the errors from getting introduced and disturb the communication. They also prevent the signal from getting
tapped by unwanted receivers. There is a class of signaling techniques to achieve this, which are discussed in
the next chapter.
FLOW CONTROL
Flow Control
o It is a set of procedures that tells the sender how much data it can transmit before the data overwhelms
the receiver.
o The receiving device has limited speed and limited memory to store the data. Therefore, the receiving
device must be able to inform the sending device to stop the transmission temporarily before the limits
are reached.
o It requires a buffer, a block of memory for storing the information until they are processed.
Two methods have been developed to control the flow of data:
o Stop-and-wait
o Sliding window
Stop-and-wait
o In the Stop-and-wait method, the sender waits for an acknowledgement after every frame it sends.
o When acknowledgement is received, then only next frame is sent. The process of alternately sending
and waiting of a frame continues until the sender transmits the EOT (End of transmission) frame.
Advantage of Stop-and-wait
The Stop-and-wait method is simple as each frame is checked and acknowledged before the next frame is
sent.
Disadvantage of Stop-and-wait
Stop-and-wait technique is inefficient to use as each frame must travel across all the way to the receiver, and
an acknowledgement travels all the way before the next frame is sent. Each frame sent and received uses the
entire time needed to traverse the link.
Sliding Window
o The Sliding Window is a method of flow control in which a sender can transmit the several frames
before getting an acknowledgement.
o In Sliding Window Control, multiple frames can be sent one after the another due to which capacity of
the communication channel can be utilized efficiently.
o A single ACK acknowledge multiple frames.
o Sliding Window refers to imaginary boxes at both the sender and receiver end.
o The window can hold the frames at either end, and it provides the upper limit on the number of frames
that can be transmitted before the acknowledgement.
o Frames can be acknowledged even when the window is not completely filled.
4
o The window has a specific size in which they are numbered as modulo-n means that they are
numbered from 0 to n-1. For example, if n = 8, the frames are numbered from
0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,0,1........
o The size of the window is represented as n-1. Therefore, maximum n-1 frames can be sent before
acknowledgement.
o When the receiver sends the ACK, it includes the number of the next frame that it wants to receive.
For example, to acknowledge the string of frames ending with frame number 4, the receiver will send
the ACK containing the number 5. When the sender sees the ACK with the number 5, it got to know
that the frames from 0 through 4 have been received.
Sender Window
o At the beginning of a transmission, the sender window contains n-1 frames, and when they are sent
out, the left boundary moves inward shrinking the size of the window. For example, if the size of the
window is w if three frames are sent out, then the number of frames left out in the sender window is w-
3.
o Once the ACK has arrived, then the sender window expands to the number which will be equal to the
number of frames acknowledged by ACK.
o For example, the size of the window is 7, and if frames 0 through 4 have been sent out and no
acknowledgement has arrived, then the sender window contains only two frames, i.e., 5 and 6. Now, if
ACK has arrived with a number 4 which means that 0 through 3 frames have arrived undamaged and
the sender window is expanded to include the next four frames. Therefore, the sender window contains
six frames (5,6,7,0,1,2).
Receiver Window
o At the beginning of transmission, the receiver window does not contain n frames, but it contains n-1
spaces for frames.
o When the new frame arrives, the size of the window shrinks.
o The receiver window does not represent the number of frames received, but it represents the number of
frames that can be received before an ACK is sent. For example, the size of the window is w, if three
frames are received then the number of spaces available in the window is (w-3).
o Once the acknowledgement is sent, the receiver window expands by the number equal to the number
of frames acknowledged.
o Suppose the size of the window is 7 means that the receiver window contains seven spaces for seven
frames. If the one frame is received, then the receiver window shrinks and moving the boundary from
0 to 1. In this way, window shrinks one by one, so window now contains the six spaces. If frames from
0 through 4 have sent, then the window contains two spaces before an acknowledgement is sent.
5
Routing algorithm
o In order to transfer the packets from source to the destination, the network layer must determine the
best route through which packets can be transmitted.
o Whether the network layer provides datagram service or virtual circuit service, the main job of the
network layer is to provide the best route. The routing protocol provides this job.
o The routing protocol is a routing algorithm that provides the best path from the source to the
destination. The best path is the path that has the "least-cost path" from source to the destination.
o Routing is the process of forwarding the packets from source to the destination but the best route to
send the packets is determined by the routing algorithm.
Classification of a Routing algorithm
The Routing algorithm is divided into two categories:
o Adaptive Routing algorithm
o Non-adaptive Routing algorithm
Routing decision Routing decisions are made based on Routing decisions are the static tables.
topology and network traffic.
Categorization The types of adaptive routing The types of Non Adaptive routing
algorithm, are Centralized, isolation algorithm are flooding and random walks.
and distributed algorithm.
Complexity Adaptive Routing algorithms are more Non-Adaptive Routing algorithms are
complex. simple.
7
Bellman Ford’s Algorithm
Dijkstra’s Algorithm
Floyd Warshall’s Algorithm
The following sections describes each of these algorithms.
Bellman Ford Algorithm
Input − A graph representing the network; and a source node, s
Output − Shortest path from s to all other nodes.
Initialize distances from s to all nodes as infinite (∞); distance to itself as 0; an array dist[] of size |
V| (number of nodes) with all values as ∞ except dist[s].
Calculate the shortest distances iteratively. Repeat |V|- 1 times for each node except s −
o Repeat for each edge connecting vertices u and v −
If dist[v] > (dist[u] + weight of edge u-v), Then
Update dist[v] = dist[u] + weight of edge u-v
The array dist[] contains the shortest path from s to every other node.
Dijkstra’s Algorithm
Input − A graph representing the network; and a source node, s
Output − A shortest path tree, spt[], with s as the root node.
Initializations −
An array of distances dist[] of size |V| (number of nodes), where dist[s] = 0 and dist[u] = ∞ (infinite),
where u represents a node in the graph except s.
An array, Q, containing all nodes in the graph. When the algorithm runs into completion, Q will
become empty.
An empty set, S, to which the visited nodes will be added. When the algorithm runs into
completion, S will contain all the nodes in the graph.
Repeat while Q is not empty −
o Remove from Q, the node, u having the smallest dist[u] and which is not in S. In the first run,
dist[s] is removed.
o Add u to S, marking u as visited.
o For each node v which is adjacent to u, update dist[v] as −
If (dist[u] + weight of edge u-v) < dist[v], Then
Update dist[v] = dist[u] + weight of edge u-v
The array dist[] contains the shortest path from s to every other node.
Floyd Warshall Algorithm
Input − A cost adjacency matrix, adj[][], representing the paths between the nodes in the network.
Output − A shortest path cost matrix, cost[][], showing the shortest paths in terms of cost between each pair of
nodes in the graph.
Populate cost[][] as follows:
o If adj[][] is empty Then cost[][] = ∞ (infinite)
o Else cost[][] = adj[][]
N = |V|, where V represents the set of nodes in the network.
Repeat for k = 1 to N −
o Repeat for i = 1 to N −
Repeat for j = 1 to N −
If cost[i][k] + cost[k][j] < cost[i][j], Then
8
Update cost[i][j] := cost[i][k] + cost[k][j]
The matrix cost[][] contains the shortest cost from each node, i , to every other node, j.
Flooding
Flooding is a non-adaptive routing technique following this simple method: when a data packet arrives at a
router, it is sent to all the outgoing links except the one it has arrived on.
For example, let us consider the network in the figure, having six routers that are connected through
transmission lines.
Distance Vector
The Distance-Vector routing algorithm is known by other names. Bellman-Ford routing algorithm and the
Ford-Fulkerson algorithm are generally distributed after the researchers create it (Bellman 1957, and Ford and
Fulkerson, 1962).
Features
Following are the features of the distance vector routing are −
The routers send the knowledge of the whole autonomous framework.
Sharing of data takes place only with the neighbours.
Sending of data holds place at constant, ordinary intervals, declared every 30 seconds.
In this algorithm, each router evaluates the distance between itself and every achievable destination. This is
accomplished by assessing the distance between a router and all of its immediate router neighbours and
adding each neighbouring routers computations for the distance between that neighbour and its close
neighbours.
Three keys to learn how this algorithm works are as follows −
Knowledge about the entire network
Each router sends its knowledge about the entire network. It communicates all of its connected knowledge
about the network to its neighbours.
Routing only to the neighbours
Each route repeatedly shares its knowledge about the network only to those routers with the explicit
connection. It transmits whatever knowledge it has about the complete network by all of its parts. This data is
taken and stored by each neighbouring router and can upgrade the routers own data about the network.
10
For router A
Network id Cost Next Hop
24 1 B
23 1 E
88 1 F
For router B
Network id Cost Next Hop
24 1 A
65 1 C
For router E
Network id Cost Next Hop
23 1 A
18 1 D
For router D
Network id Cost Next Hop
18 1 E
76 1 C
When A can send his packet or routing table information to B router, E & C directly.
Similarly, B can send routing table information to router A & C and so on.
When A receivers are routing tables from B, E & F, it can update its table. Similarly, B receives A and C
updates itself and so on, as shown in the new table.
New routing table for router A
Network id Cost Next Hop
23 1 E
11
Network id Cost Next Hop
24 1 B
88 1 F
23 2 D
38 2 C
13 2 A
24 1 A
28 1 C
35 2 C
38 2 C
Similarly, every router will update itself and so on. The updating algorithm checks that the router first adds
Hop to the Hop count field for each advertised route. The router should apply these rules.
If the displayed destination is not in the routing table, the router must insert that displayed data into the
table.
If the displayed destination is in the routing table, then two things can happen.
If the next-hop field is similar, the router must restore the table's entry with the displayed one.
If the next-hop field is not a similar
If the displayed hop count is lesser than the one on the table, the router must restore the entry in the
table with the new one.
If the displayed hop count is not lesser, the router must do nothing.
14