MCA4th Sem /MCS-042/Solved Assignment/Data Communication and Computer Network/2016-2017 New

Q.1.

A.1.

Dijkstra’s Algorithm

Dijkstra’s algorithm solves the single source shortest path problem on a weighted, directed graph only when all edge-weights are non-negative. It maintains a set S of vertices whose final shortest path from the source has already been determined and it repeatedly selects the left vertices with the minimum shortest-path estimate, inserts them into S, and relaxes all edges leaving that edge. In this we maintain a priority-Queue which is implemented via heap.

Steps  of Dijkstra's Algorithm for finding Shortest Path:-

Step 1) First we , choose Initial Point or Starting point of the path ,i.e. A.

We have many ways to reach from path A to  Target path  F , thar are the following:-

i)   A  ----> C --->  D----> F

ii)  A ---> B ---> E ---> F

iii)  A ---> E ---> F

iv)  A --->B 

But, we choose a shortest path to reach our Target path F. i.e. 

(i)  A  ----> C --->  D----> F 

Step 2) Starting from A , we choose Shortest path to F  , i.e.  A  ----> C

Step 3) Now , after (Starting from A , we choose Shortest path to F  , i.e.  A  ----> C)  we select path from  C --->  D

Step 4)  Now , after Step 2 , we choose Shortest path to F  , i.e.  D  ----> F.

Step 4) Finish , we got our Target path in Shortest path. 

Q.2. Explain how a network congestion is controlled using slow start algorithm in TCP with help of an illustration. Is congestion control and flow control are equivalent?

A.2. Congestion control deals with adapting the source send rate to the bandwidth available to the transport connection, which varies over time in a non-predictable way because the network is shared by many applications. Consider the data flow from a TCP source to a TCP sink. The goal of TCP congestion control is three-fold:

• To reduce the source send rate when the network is congested [more precisely, when the links on the network path of the TCP connection have queues that are growing very large].
• To increase the source send rate when the network is not congested [so as to exploit bandwidth when it becomes available].
• To share the network resources (i.e., link bandwidth and buffer) with other TCP flows in a "fair" way. There are many ways to quantify fairness. For example, consider a link of bandwidth C shared by n TCP flows. For i=1,...,n, let flow i want data rate B_i(t) at time t. Fairness is achieved if, at any time t, flow i gets data rate (B_i/B)*C if B_1(t)+...+B_n(t) exceeds C and data rate B_i otherwise. In practice, one can only approximate this.

Because TCP was designed to operate over unreliable heterogenous networks, its approach to congestion control relies on minimal knowledge of the network state. In particular, a TCP entity's knowledge about the current network state is derived solely from its recent history of message sends and receptions. Initial versions of TCP (e.g., Tahoe) used roundtrip times, where a roundtrip time is the time elapsed from sending a primary message (e.g., data message) to receiving an ack for that message. Later versions of TCP make use of the presence of duplicate acks (Reno) and the variation in the time intervals between acks (Vegas). In any case, TCP's view of the current network state is, to put it kindly, not very accurate. Consequently, TCP's congestion control must be very conservative.

The smoothest way to control the send rate is to directly adjust the time between successive packet sends. But TCP (like most computer software) does not operate at such "fine" time scales. Instead, TCP sends bursts of packets and adjusts its send rate by varying the number of packets in a burst. In a similar vein, TCP does not usually maintain separate timers for every outstanding packet (which would be needed to measure the roundtrip times of all primary packets [recall that a primary packet is one that is resent until a response is received]). Instead, TCP usually uses one timer to keep track of the last primary packet sent. If a primary packet is sent when the timer is running, it usually restarts the timer.

A TCP source entity does the following:

• Maintains a running conservative estimate, called rto, of the current roundtrip time (by averaging recent roundtrip times and augmenting with some ``slack'').
• Maintains a running estimate, called congestion window size, of how many packets can be sent without overloading the network path; the congestion window size never exceeds (and is usually much smaller) than the send window size.
• Whenever a packet is acknowledged within rto, the entity increases the congestion window size and sends any new data that enters the congestion window. The increase is exponential if the congestion window is "small" (less than a so-called slow-start threshold), and linear otherwise.
• Whenever a packet is not acknowledged within rto, the entity (treats this as an indication of congestion) decreases the congestion window to the minimum (thereby entering slow-start) and resends all data in the congestion window.
• Whenever a packet loss is detected within rto, the entity decreases the congestion window by a multiplicative factor and resends the lost data.

Slow Start algorithm

Introduction

Jacobson and Karels developed a congestion control mechanism for TCP following a congestion collapse on the internet. Prior to this no congestion control mechanism was specified for TCP. Their method is based on ensuring the 'conservation of packets,' i.e., that the packets are entering the network at the same rate that they are exiting with a full window of packets in transit. A connection in this state is said to be in equilibrium. If all connections are in equilibrium, congestion collapse is unlikely The authors identified three ways for packet conservation to be violated:

1.     The connection never reaches equilibrium.

2.     A source sends a new packet before an old one exits.

3.     Congestion in the network prevents a connection from reaching equilibrium.

TCP is 'self clocking,' i.e., the source sends a new packet only when it receives an ack for an old one and the rate at which the source receives acks is the same rate at which the destination receives packets. So the rate at which the source sends matches the rate of transmission over the slowest part of the connection.

Algorithm

To ensure that the connection reaches equilibrium, i.e., to avoid failure (1), a slow-startalgorithm was developed. This algorithm added a congestion window. The minimum of the congestion windowand the destination window is used when sending packets. Upon starting a connection, or restarting after a packet loss, the congestion window size is set to one packet. The congestion window is then increased by one packet upon the receipt of an ack. This would bring the size of the congestion window to that of the destination window in RTT log ₂ W time, where RTT is the round-trip-time and W is the destination window size in packets. Without the slow start mechanism an 8 packet burst from a 10 Mbps LAN through a 56 Kbps link could put the connection into a persistent failure mode.

Violation (2) would occur if the retransmit time is too short, making the source retransmit a packet that has not been received and is not lost. What is needed is a good way to estimate the round trip time:

Err = Latest_RTT_Sample - RTT_Estimate

RTT_Estimate = RTT_Estimate + g*Err

where g is a 'gain' (0 < g < 1) which is related to the variance. This can be done quickly with integer arithmetic. This is an improvement over the previous method which used a constant to account for variance.

The authors also added exponential backoff for retransmitting packets that needed to be retransmitted more than once. This provides exponential dampening in the case where the round trip time increases faster than the RTT estimator can accommodate, and packets, which are not lost, are retransmitted.

Congestion avoidance takes care of violation (3). Lost packets are a good indication of congestion on the network. The authors state that the probability of a packet being lost due to transit is very rare. Furthermore, because of the improved round trip timer, it is a safe assumption that a timeout is due to network congestion. A additive increase / multiplicative decrease policy was used to avoid congestion.

Upon notification of network congestion, i.e., a timeout, the congestion window is set to half the current window size. Then for each ack for a new packet results in increasing the window by1/congestion_window_size. Note that if a packet times out, it is most likely that the source window is empty and nothing is being transmitted and a slow-start is required. In that case, the slow-start algorithm will increase the window (by one packet per ack) to half the previous window size, at which point the congestion avoidance algorithm takes over.

Performance

To test the effectiveness of their congestion control scheme, they compared their implementation of TCP to the previous implementation. They had four TCP conversations going between eight computers on two 10 Mbps LANs with a 230.4 Kbps link over the internet. They saw a 200% increase in effective bandwidth with the slow-start algorithm alone. The original implementation used only 35% of the available bandwidth due to retransmits. In another experiment, using the same network setup, the TCP implementation without congestion avoidance resulted in 4,000 of 11,000 packets sent were retransmitted packets as opposed to 89 of 8,281 with the new implementation.

Q.3.Describe how MACAW is an improvement over MACA ?

A.3.  A “media access protocol” is a link-layer protocol for allocating access to a shared medium (i.e. a wireless channel) among multiple transmitters. MACAW is a media access protocol for mobile pads that communicate wirelessly with base stations; each base station can hear transmission from pads within a certain range of its location, called a cell.

This is a challenging problem for several reasons:

§  Transmitters are mobile, but location information is not communicated explicitly: a transmitter simply moves or a new transmitter comes into the area, and the media access protocol must adapt.

§  Connectivity is not transitive. For example, A and B can communicate, as can B and C, but A and C might not be able to; the protocol must be designed so that communications between B and C do not disrupt A, even though A has no direct knowledge of C.

§  Due to noise, communication may not be symmetric (A can hear B, but B cannot hear A), and transmitters may interfere with one another (A might be out of range of B, but A’s transmissions might still disrupt B’s ability to communicate).

The MACAW paper ignores both asymmetry and interference: they assume a simplified model in which two stations are either in range of one another or they aren’t; a transmission is successfully received iff there is only one active transmitter in range of the receiver; and no two base stations are within range of one another. Importantly, contention between transmissions occurs at the receiver of the transmission, not the sender: that is, two nodes can transmit different messages from the same area at once, but two nodes in the same area cannot simultaneously receive different messages. Their goal is a media access protocol that is both efficient (high utilization of the available media), and fair (each station gets its “fair share”).

MACA:-

MACAW is an improved version of an earlier wireless media access protocol called MACA. MACA proceeds as follows:

§  Before sending a message, the transmitter sends a RTS control message (“ready to send”), containing the length of the upcoming data message. The time taken to transmit a control message (~30 bytes) is called a slot.

§  If the receiver hears the RTS and is not currently “deferring,” it replies with a CTS control message (“clear to send”), which includes a copy of the length field from the RTS.

§  Any station that hears a CTS defers any transmissions for long enough to allow someone to send a data message of the specified length. This avoids colliding with the CTS sender (the receiver of the upcoming data message).

§  Any station that hears an RTS defers any transmissions for a single slot (long enough for the reply CTS to be received, but not long enough for the actual data message to be sent, because contention is receiver-local).

§  Backoff: if no CTS response is received for an RTS, the sender must retransmit the RTS. It waits an integer number of slots before retransmitting, where that integer is chosen randomly between 1 and BO, the backoff counter. BO is doubled for every retransmit, and reduced to 1 for every successful RTS-CTS pair.

IMPROVEMENT

MACAW is proposed as a series of improvements to the basic MACA algorithm. First, they suggest a less aggressive backoff algorithm: the exponential increase / reset to 1 policy of MACA leads to large oscillations in the retransmission interval. They propose increasing BO by 1.5 after a timeout, and decreasing it by 1 after a successful RTS-CTS pair.

Second, they propose that receivers should send an ACK to the sender after successfully receiving a data message. This is suggested because the minimum TCP retransmission timeout is relatively long (0.5 seconds at the time), so it takes a long time to recover from lost or corrupted messages. A link layer timeout can be more aggressive, because it can take advantage of knowledge of the latency of the individual link (rather than the end-to-end timeout in TCP).

Q.4.Explain and illustrate sliding window Protocol with window size of 5. How does the scheme improve the efficiency of transmission ?

A.4. 

• In sliding window method, multiple frames are sent by sender at a time before needing an acknowledgment.

• Multiple frames sent by source are acknowledged by receiver using a single ACK frame.
Sliding Window

• Sliding window refers to an imaginary boxes that hold the frames on both sender and receiver side.

• It provides the upper limit on the number of frames that can be transmitted before requiring an acknowledgment.

• Frames may be acknowledged by receiver at any point even when window is not full on receiver side.

• Frames may be transmitted by source even when window is not yet full on sender side.

• The windows have a specific size in which the frames are numbered modulo- n, which means they are numbered from 0 to n-l. For e.g. if n = 8, the frames are numbered 0, 1,2,3,4,5,6, 7, 0, 1,2,3,4,5,6, 7, 0, 1, ....

• The size of window is n-1. For e.g. In this case it is 7. Therefore, a maximum of n-l frames may be sent before an acknowledgment.

• When the receiver sends an ACK, it includes the number of next frame it expects to receive. For example in order to acknowledge the group of frames ending in frame 4, the receiver sends an ACK containing the number 5. When sender sees an ACK with number 5, it comes to know that all the frames up to number 4 have been received. 

Sliding Window on Sender Side

• At the beginning of a transmission, the sender's window contains n-l frames.

• As the frames are sent by source, the left boundary of the window moves inward, shrinking the size of window. This means if window size is w, if four frames are sent by source after the last acknowledgment, then the number of frames left in window is w-4.

• When the receiver sends an ACK, the source's window expand i.e. (right boundary moves outward) to allow in a number of new frames equal to the number of frames acknowledged by that ACK.

• For example, Let the window size is 7 (see diagram (a)), if frames 0 through 3 have been sent and no acknowledgment has been received, then the sender's window contains three frames - 4,5,6.

• Now, if an ACK numbered 3 is received by source, it means three frames (0, 1, 2) have been received by receiver and are undamaged.

• The sender's window will now expand to include the next three frames in its buffer. At this point the sender's window will contain six frames (4, 5, 6, 7, 0, 1).

Sliding Window on Receiver Side 

• At the beginning of transmission, the receiver's window contains n-1 spaces for frame but not the frames.

• As the new frames come in, the size of window shrinks.

• Therefore the receiver window represents not the number of frames received but the number of frames that may still be received without an acknowledgment ACK must be sent.

• Given a window of size w, if three frames are received without an ACK being returned, the number of spaces in a window is w-3.

• As soon as acknowledgment is sent, window expands to include the number of frames equal to the number of frames acknowledged.

• For example, let the size of receiver's window is 7 as shown in diagram. It means window contains spaces for 7 frames.

• With the arrival of the first frame, the receiving window shrinks, moving the boundary from space 0 to 1. Now, window has shrunk by one, so the receiver may accept six more frame before it is required to send an ACK.

• If frames 0 through 3 have arrived but have DOC been acknowledged, the window will contain three frame spaces.

• As receiver sends an ACK, the window of the receiver expands to include as many new placeholders as newly acknowledged frames.

• The window expands to include a number of new frame spaces equal to the number of the most recently acknowledged frame minus the number of previously acknowledged frame. For e.g., If window size is 7 and if prior ACK was for frame 2 & the current ACK is for frame 5 the window expands by three (5-2).

Q.5.Explain the function and working model of Kerberos with the help of a diagram.

A.5. 

Kerberos is an authentication system based on private-key cryptography. In the Kerberos system, a trusted third-party issues session keys for interactions between users and services. It is mature technology which has been widely used, although it has known limitations. 

The Kerberos design is open-source, originating at MIT in the mid-1980's, and Kerberos is still freely available from MIT and other sources. Kerberos is also available in commercial software supported by vendors and has been incorporated into many widely-used products. For instance, Sun includes basic Kerberos functionality in Solaris, Cisco routers support Kerberos authentication for telnet connections, and Microsoft has announced it will use a version of the Kerberos protocol in Windows 2000. 

This paper will first list the goals and scope of the Kerberos system, followed by a brief review of concepts in private-key cryptography, and a description of the Kerberos "ticket-granting" approach. Appropriate applications, limitations, and competing technologies will be discussed, as well as the future of this technology. This brief overview of Kerberos is intended to highlight its main functionality, and does not exhaustively describe its features. For additional details on Kerberos, see the references listed at the end of this paper. 

Goals and Scope of the Kerberos system

Kerberos is designed to provide authentication of user identity in a networked computing environment consisting of workstations (used directly by one or more users) and servers (providing services such as email and shared file systems). It is, in part, a response to the current standard approach to network security, authentication by assertion, wherein a client gains access to services simply by asserting that it is who it says it is (or is acting on behalf of the user that it claims it is). 

A basic assumption is that network traffic is highly susceptible to interception and is the weak link in system security, rather than direct access to servers, which can be protected by physical means. The more often a specific cryptographic key is reused, the more susceptible it becomes to decoding. For this reason, each session of interactions between a user and a specific service should be encrypted using a short-lived "session key". To make the system usable in practice, however, it must be convenient, and to the greatest extent possible, transparent to the user. 

Starting with those assumptions, the system's key goals can be summarized as follows: 

• Never transmit unencrypted passwords over the network, i.e. "in the clear". 
• Protect against the misuse of intercepted credentials (also called "replay attacks"). 
• Do not require the user to repeatedly enter a password to access routine services.

The Kerberos system attempts to address design tradeoffs between the level of protection provided and the user's convenience, while also considering the complexity of system administration and application development. 

Implementations of Kerberos are available from various vendors, and it is freely accessible in open-source form. The standard MIT distribution includes a basic set of applications, including telnet, POP email, and the Berkeley UNIX "R-commands" (such as rlogin). Other applications can be "Kerberized" by incorporating calls to Kerberos library functions. 

Encryption algorithms such as those used in Kerberos have long been considered munitions by the US government. The export status of Kerberos under newly liberalized regulations (October 2000) is unclear. For the time being, MIT is distributing its source only to US and Canadian citizens. Versions without encryption have been exported overseas, however. 

Q.6. Explain the process of generating a digital signature. What are its benefits ?

A.6. Digital signatures are the public-key primitives of message authentication. In the physical world, it is common to use handwritten signatures on handwritten or typed messages. They are used to bind signatory to the message.

Similarly, a digital signature is a technique that binds a person/entity to the digital data. This binding can be independently verified by receiver as well as any third party.

Digital signature is a cryptographic value that is calculated from the data and a secret key known only by the signer.

In real world, the receiver of message needs assurance that the message belongs to the sender and he should not be able to repudiate the origination of that message. This requirement is very crucial in business applications, since likelihood of a dispute over exchanged data is very high.

Model of Digital Signature

As mentioned earlier, the digital signature scheme is based on public key cryptography. The model of digital signature scheme is depicted in the following illustration −

The following points explain the entire process in detail −

·        Each person adopting this scheme has a public-private key pair.

·        Generally, the key pairs used for encryption/decryption and signing/verifying are different. The private key used for signing is referred to as the signature key and the public key as the verification key.

·        Signer feeds data to the hash function and generates hash of data.

·        Hash value and signature key are then fed to the signature algorithm which produces the digital signature on given hash. Signature is appended to the data and then both are sent to the verifier.

·        Verifier feeds the digital signature and the verification key into the verification algorithm. The verification algorithm gives some value as output.

·        Verifier also runs same hash function on received data to generate hash value.

·        For verification, this hash value and output of verification algorithm are compared. Based on the comparison result, verifier decides whether the digital signature is valid.

·        Since digital signature is created by ‘private’ key of signer and no one else can have this key; the signer cannot repudiate signing the data in future.

Importance of Digital Signature

Out of all cryptographic primitives, the digital signature using public key cryptography is considered as very important and useful tool to achieve information security.

Apart from ability to provide non-repudiation of message, the digital signature also provides message authentication and data integrity. Let us briefly see how this is achieved by the digital signature −

·        Message authentication − When the verifier validates the digital signature using public key of a sender, he is assured that signature has been created only by sender who possess the corresponding secret private key and no one else.

·        Data Integrity − In case an attacker has access to the data and modifies it, the digital signature verification at receiver end fails. The hash of modified data and the output provided by the verification algorithm will not match. Hence, receiver can safely deny the message assuming that data integrity has been breached.

·        Non-repudiation − Since it is assumed that only the signer has the knowledge of the signature key, he can only create unique signature on a given data. Thus the receiver can present data and the digital signature to a third party as evidence if any dispute arises in the future.

Q.7. What is called Constellation diagram ? Illustrate Constellation diagram of QAM – 16 and QAM – 64.

A.7. QAM, Quadrature amplitude modulation is widely used in many digital data radio communications and data communications applications. A variety of forms of QAM are available and some of the more common forms include 16 QAM, 32 QAM, 64 QAM, 128 QAM, and 256 QAM. Here the figures refer to the number of points on the constellation, i.e. the number of distinct states that can exist.

The various flavours of QAM may be used when data-rates beyond those offered by 8-PSK are required by a radio communications system. This is because QAM achieves a greater distance between adjacent points in the I-Q plane by distributing the points more evenly. And in this way the points on the constellation are more distinct and data errors are reduced. While it is possible to transmit more bits per symbol, if the energy of the constellation is to remain the same, the points on the constellation must be closer together and the transmission becomes more susceptible to noise. This results in a higher bit error rate than for the lower order QAM variants. In this way there is a balance between obtaining the higher data rates and maintaining an acceptable bit error rate for any radio communications system.

QAM applications

QAM is in many radio communications and data delivery applications. However some specific variants of QAM are used in some specific applications and standards.

For domestic broadcast applications for example, 64 QAM and 256 QAM are often used in digital cable television and cable modem applications. In the UK, 16 QAM and 64 QAM are currently used for digital terrestrial television using DVB - Digital Video Broadcasting. In the US, 64 QAM and 256 QAM are the mandated modulation schemes for digital cable as standardised by the SCTE in the standard ANSI/SCTE 07 2000.

In addition to this, variants of QAM are also used for many wireless and cellular technology applications.

Constellation diagrams for QAM

The constellation diagrams show the different positions for the states within different forms of QAM, quadrature amplitude modulation. As the order of the modulation increases, so does the number of points on the QAM constellation diagram.

The diagrams below show constellation diagrams for a variety of formats of modulation:

Q.8.Differentiate between Leaky bucket and Token bucket traffic shaper. Why is traffic shaping needed ?

A.8 .Leaky Bucket 

 • Leaky bucket: consists of a finite queue – When a packet arrives, if there is a room on the queue it is joined the queue; otherwise, it is discarded – At every (fixed) clock tick, one packet is transmitted unless the queue is empty •

 It eliminates bursts completely: packets passed to the subnet at the same rate • 

This may be a bit overdone, and also packets can get lost (when bucket is full) Faucet Leaky bucket 

Water drips out of the hole at a constant rate Host computer Packet The bucket holds packets 

Unregulated flow Regulated flow Network Interface containing a leaky bucket Water .

• Token bucket: 

Tokens are added at a constant rate. For a packet to be transmitted, it must capture and destroy one token –

 (a) shows that the bucket holds three tokens with five packets waiting to be transmitted – (b) shows that three packets have gotten through but the other two are stuck waiting for tokens to be generated Host computer Networks Host computer The bucket holds tokens Networks One token is added to the bucket .

• Unlike leaky bucket, token bucket allows saving, up to maximum size of bucket n. This means that bursts of up to n packets can be sent at once, giving faster response to sudden bursts of input 

• An important difference between two algorithms: token bucket throws away tokens when the bucket is full but never discards packetswhile leaky bucket discards packets when the bucket is full .

• Let token bucket capacity be C (bits), token arrival rate ρ (bps), maximum output rate M (bps), and burst length S (s) – During burst length of S (s), tokens generated are ρS (bits), and output burst contains a maximum of C + ρS (bits) – Also output in a maximum burst of length S (s) is M · S (bits), thus C + ρS = MS or S = C M − ρ 

• Token bucket still allows large bursts, even though the maximum burst length S can be regulated by careful selection of ρ and M 

• One way to reduce the peak rate is to put a leaky bucket of a larger rate (to avoid discarding packets) after the token bucket.

Q.9.Assume we need to download a text document at a rate of 100 pages per minute. What is required bit rate of the channel. 

Assume Page size = 24 lines

 Each line = 81 characters

A.9. 
Relationship between Bandwidth, Data Rate and Channel Capacity
This posts describes the relationship between signal bandwidth, channel bandwidth and maximum achievable data rate. Before, going into detail, knowing the definitions of the following terms would help:

Signal Bandwidth – the bandwidth of the transmitted signal or the range of frequencies present in the signal, as constrained by the transmitter.

Channel Bandwidth – the range of signal bandwidths allowed by a communication channel without significant loss of energy (attenuation).

Channel Capacity or Maximum Data rate – the maximum rate (in bps) at which data can be transmitted over a given communication link, or channel.

In general, information is conveyed by change in values of the signal in time.  Since frequency of a signal is a direct measure of the rate of change in values of the signal, the more the frequency of a signal, more is the achievable data rate or information transfer rate. This can be illustrated by taking the example of both an analog and a digital signal.
If we take analog transmission line coding techniques like Binary ASK, Binary FSK or Binary PSK, information is tranferred by altering the property of a high frequency carrier wave. If we increase the frequency of this carrier wave to a higher value, then this reduces the bit interval T (= 1/f) duration, thereby enabling us to transfer more bits per second.

Similarly, if we take digital transmission techniques like NRZ, Manchester encoding etc., these signals can be modelled as periodic signals and hence is composed of an infinite number of sinusoids, consisting of a fundamental frequency (f) and its harmonics. Here too, the bit interval (T) is equal to the reciprocal of the fundamental frequency (T =  1/f). Hence, if the fundamental frequency is increased, then this would represent a digital signal with shorter bit interval and hence this would increase the data rate.

So, whether it is analog or digital transmission, an increase in the bandwidth of the signal, implies a corresponding increase in the data rate. For e.g. if we double the signal bandwidth,  then the data rate would also double.

In practise however, we cannot keep increasing the signal bandwidth infinitely. The telecommunication link or the communication channel acts as a police and has limitations on the maximum bandwidth that it would allow. Apart from this, there are standard transmission constraints in the form of different channel noise sources that strictly limit the signal bandwidth to be used.  So the achievable data rate is influenced more by the channel’s bandwidth and noise characteristics than the signal bandwidth.


Nyquist and Shannon have given methods for calculating the channel capacity (C) of bandwidth limited communication channels.

Solution 

A page is an average of 24 lines with 80 characters in each line. If we assume that one character requires 8 bits, the bit rate is:

   100 X 81 X 24 X 8 = 1555200 bps)Bit per second) = 1.555 Mbps

Q.10.Find CRC for the data polynomial x9 + x7 + x3 +x2 + 1 with generator polynomial x3 + x + 1.

A.10  

Cyclic Redundancy Check (CRC) An error detection mechanism in which a special number is appended to a block of data in order to detect any changes introduced during storage (or transmission). The CRe is recalculated on retrieval (or reception) and compared to the value originally transmitted, which can reveal certain types of error. For example, a single corrupted bit in the data results in a one-bit change in the calculated CRC, but multiple corrupt bits may cancel each other out.

A CRC is derived using a more complex algorithm than the simple CHECKSUM, involving MODULO ARITHMETIC (hence the 'cyclic' name) and treating each input word as a set of coefficients for a polynomial.

• CRC is more powerful than VRC and LRC in detecting errors.

• It is not based on binary addition like VRC and LRC. Rather it is based on binary division.

• At the sender side, the data unit to be transmitted IS divided by a predetermined divisor (binary number) in order to obtain the remainder. This remainder is called CRC.

• The CRC has one bit less than the divisor. It means that if CRC is of n bits, divisor is of n+ 1 bit.

• The sender appends this CRC to the end of data unit such that the resulting data unit becomes exactly divisible by predetermined divisor i.e. remainder becomes zero.

• At the destination, the incoming data unit i.e. data + CRC is divided by the same number (predetermined binary divisor).

• If the remainder after division is zero then there is no error in the data unit & receiver accepts it.

• If remainder after division is not zero, it indicates that the data unit has been damaged in transit and therefore it is rejected.

• This technique is more powerful than the parity check and checksum error detection.

• CRC is based on binary division. A sequence of redundant bits called CRC or CRC remainder is appended at the end of a data unit such as byte. 

Q.11.Suppose you are developing a standard for a new type of a network. You need to decide whether your network will use Virtual Circuits (VCs) or datagram routing. What are the Pros & Cons for using VCs ?

A.11.Datagrams and Virtual Circuits
Two basic approaches to packet switching are common: The most common is datagram switching (also known as a "best-effort network" or a network supporting the connection-less network service).This is what is used in the network layer of Internet.
Virtual circuit is a connection which is oriented unlike datagram switching. The source and destination identifies a suitable path for virtual circuit before the actual data communication starts. For this, it makes use of all intermediate nodes, routing table and other additional parameters. 

Once the data transmission is completed, the resources and values present for the virtual circuit are removed completely. There are two categories of virtual circuit, namely switched virtual circuit and permanent virtual circuit.

Switched virtual circuit is a virtual circuit in the connection is dynamically established based on the demand and is torn down completely once the transmission is complete. Permanent virtual circuit is one provided for continuous usage or repeated usage between the dame data terminals.

Virtual Circuit Packet Networks

In virtual circuit packet switching, an initial setup phase is used to set up a fixed route between the intermediate nodes for all packets which are exchanged during a session between the end nodes (analogous to the circuit-switched telephony network). At each intermediate node, an entry is made in a table to indicate the route for the connection that has been set up. Packets can then use short headers, since only identification of the virtual circuit rather than complete destination address is needed. The intermediate nodes (B,C) process each packet according to the information which was stored in the node when the connection was established.
Enhancements to provide reliability may also be provided. Delivery of packets in proper sequence and with essentially no errors is guaranteed, and congestion control to minimise queuing is common. Delays are more variable than they are with a dedicated circuit, however, since several virtual circuits may compete for the same resources. An initial connection setup phase and a disconnect phase at the end of data transfer are required (as in the circuit-switched network). The most common form of virtual circuit network were ATM and X.25, which for a while were commonly used for public packet data networks.
A variation of circuit-switched packet networking, called Multi-Protocol Label Switching (MPLS), is used in some Internet backbones. This uses a connection-oriented datagram service to switch packets across a network forming a path between a set of IP routers. This operates below the network-layer, so that applications are unaware of when MPLS is used.

Differences between datagram and virtual circuit networks

There are a number of important differences between virtual circuit and datagram networks. The choice strongly impacts complexity of the different types of node. Use of datagrams between intermediate nodes allows relatively simple protocols at this level, but at the expense of making the end (user) nodes more complex when end-to-end virtual circuit service is desired.
The Internet transmits datagrams between intermediate nodes using IP. Most Internet users need additional functions such as end-to-end error and sequence control to give a reliable service (equivalent to that provided by virtual circuits). This reliablility may be provided by the Transmission Control Protocol (TCP) which is used end-to-end across the Internet, or by applications such as the trivial file transfer protocol (tftp) running on top of the User Datagram Protocol (UDP).

Q.12.Why is that packet switching is said to employ statistical multiplexing ? Contrast statistical multiplexing with the multiplexing that take place in TDM.

A.12.
Statistical multiplexing is a type of communication link sharing, very similar to dynamic bandwidth allocation (DBA). In statistical multiplexing, a communication channel is divided into an arbitrary number of variable bitrate digital channels or data streams. The link sharing is adapted to the instantaneous traffic demands of the data streams that are transferred over each channel. This is an alternative to creating a fixed sharing of a link, such as in general time division multiplexing (TDM) and frequency division multiplexing (FDM). When performed correctly, statistical multiplexing can provide a link utilization improvement, called the statistical multiplexing gain.

Statistical multiplexing is facilitated through packet mode or packet-oriented communication, which among others is utilized in packet switched computer networks. Each stream is divided into packets that normally are delivered asynchronously in a first-come first-served fashion. In alternative fashion, the packets may be delivered according to some scheduling discipline for fair queuing or differentiated and/or guaranteed quality of service.

Statistical multiplexing of an analog channel, for example a wireless channel, is also facilitated through the following schemes:

Random frequency-hopping orthogonal frequency division multiple access (RFH-OFDMA)
Code-division multiple access (CDMA), where different amount of spreading codes or spreading factors can be assigned to different users.
Statistical multiplexing normally implies "on-demand" service rather than one that preallocates resources for each data stream. Statistical multiplexing schemes do not control user data transmissions.

Comparison with static TDM

Time domain statistical multiplexing (packet mode communication) is similar to time-division multiplexing (TDM), except that, rather than assigning a data stream to the same recurrent time slot in every TDM, each data stream is assigned time slots (of fixed length) or data frames (of variable lengths) that often appear to be scheduled in a randomized order, and experience varying delay (while the delay is fixed in TDM).

Statistical multiplexing allows the bandwidth to be divided arbitrarily among a variable number of channels (while the number of channels and the channel data rate are fixed in TDM).

Statistical multiplexing ensures that slots will not be wasted (whereas TDM can waste slots). The transmission capacity of the link will be shared by only those users who have packets.

Static TDM and other circuit switching is carried out at the physical layer in the OSI model and TCP/IP model, while statistical multiplexing is carried out at the data link layer and above.

Channel identification


In statistical multiplexing, each packet or frame contains a channel/data stream identification number, or (in the case of datagram communication) complete destination address information.