Computer Networks
Computer Networks
Computer Networks
ON
COMPUTER NETWORKS
MR 18
III B. Tech I Semester
1
2018-19
MALLA REDDY ENGINEERING COLLEGE B.Tech.
Onwards
(Autonomous) V Semester
(MR-18)
Code: 80517 L T P
COMPUTER NETWORKS
Credits: 3 3 - -
TEXT BOOKS:
1. Behrouz A. Forouzan, “Data Communications and Networking”, 4thEdition,
TMH, 2006.
2. Andrew S Tanenbaum, “Computer Networks”, 4th Edition, Pearson
Education/PHI.
REFERENCES:
1. P.C .Gupta, “Data communications and computer Networks”, PHI.
2. S.Keshav, “An Engineering Approach to Computer Networks”, 2nd Edition, Pearson Education.
3. W.A. Shay, “Understanding communications and Networks”, 3rd Edition, Cengage Learning.
4. James F.Kurose & Keith W. Ross, “Computer Networking: A Top-Down Approach Featuring the
Internet”, 3rd Edition, Pearson Education.
E-RESOURCES:
1. https://www.saylor.org/site/wp-content/uploads/2012/02/Computer-Networking- Principles- Bonaventure-1-30-31-
OTC1.pdf
2. http://ebook-dl.com/downloadbook/230
3. https://doi.org/10.1016/0169-7552(89)90019-6
4. http://nptel.ac.in/courses/106105081/
Course Outcomes:
At the end of the course, students will be able to
1. Understand the Layered Architecture of Computer Networks.
2. Conceptualize the protocols of Data Link Layer and can build Local area networks.
3. Apply Subnet and Supernet concepts in the construction of computer network.
4. Summarize the protocols used in Transport Layer, QoS and Congestion control mechanisms.
5. Analyze different protocols of Application Layer and various security risks.
Introduction
Networks use Distributed processing, in which a task is divided among multiple computers.
Advantages of Distributed processing are
Security/ Encapsulation
Distributed data bases
Faster problem solving
Security through Redundancy
Collaborative processing
Network Criteria
Performance:
The performance can be measured in many ways and depends on number of factors.
Number of users
Type of transmission medium
Hardware
Software
Reliability
Frequency of failure
Recovery time of a network after a failure.
Catastrophe.
Security
Unauthorized access
Viruses
Applications
Accessing Remote databases
Accessing Remote programs
Value added communication facility
Marketing and sales
Financial services
Manufacturing
Electronic message
Directory services
Information services
Teleconferencing
Cellular telephone
Cable television
IMP
Subnet
The end systems are called the HOSTS. The hosts are connected through a
communication subnet or simply Subnet as shown in fig.
The subnet consists of two parts: a) Transmission lines b) Switching elements.
The Transmission lines transmit the raw bits. The Switching elements are specialized
computers, which switches packets. This is called Interface Message Processor (IMP) or
Router or data switching exchanges or packet switching nodes.
The data can be transmitted through the subnet in two ways. They are
a) Point to point or store and forward
b) Broad casting
Network Architecture
To reduce the design complexity, most networks are organized as a series of layers or
levels, each built upon on the one below it. The number of layers, the name of each layer
,the contents of each layer ,and the function of each layer differ from network to network
However, in all networks the purpose of each layer is to offer certain services to the higher
layers ,shielding those layers from the details of how the offered services are actually
implemented.
Layer 5 protocol
Layer 5 Layer 5
Physical Medium
The interface defines which primitive operation and services the lower layer offers to the
upper one.
a. Simplex communication:
Simplex transmission
A B
Ex: Keyboards, Monitors
A B
Ex: Two-way road, where traffic will be there in both the directions.
REFERENCE MODELS
In 1947, the International Standards Organization (ISO) proposed a network model that covers all
network communications .This model is called Open Systems Interconnection (OSI) model. An
open system is a model that allows any two different systems to communicate regardless of their
underlying architecture.
The OSI model is built of seven layers: Physical (layer 1), Data link (layer 2), Network
(layer 3), Transport (layer 4), Session (layer 5), Presentation (layer 6) and Application layers
(layer 7).
Within a single machine, each layer calls upon the services of the layer just below it.layer 3,for
example, uses the services provided by layer 2 and provides for layer 4.Between machines layer
on one machine communicates with layer x on another machine. This communication is governed
by protocols. The processes on each machine that communicate at a given layer are called peer
–to – peer processor.
At the physical layer, communicate is direct: Machine A sends a stream of bits to machine B. At
the higher layers, however, communication must move down through the layers on machine A,
over to machine B, and then back up through the layers. Each layer in the sending machine adds
its own information to the message it receives from the layer just above it and passes the whole
package to the layer just below it. This information is added in the form of headers or trailers.
Headers are added to the message at layers 6, 5, 4, 3, and 2.At layer 1 the entire message
converted to a form that can be transferred to the receiving machine. At the receiving machine,
Computer Networks S.SANDHYA
RANI
the message is unwrapped layer by layer, with each process receiving and removing the data
meant for it.
The seven layers can be thought of as belonging to three subgroups. Layers 1, 2, 3 –are the
network support layers; they deal with the physical aspects of moving data from onr machine to
another. Layers 5, 6, 7—can be thought of as user support layers: they allow interoperability
among unrelated software systems. Layer 4,the transport layer, ensures end to end reliable
transmission while layer 2 ensures reliable transmission on a single link. The upper layers are
implemented almost always in software; lower layers are a combination of hard ware and
software, where as physical layer is mostly hardware.
Name of unit
Layer exchanged
Application protocol
7 Application Application
OSI TCP/IP
Application Application
Presentation
Not present in
Session the model
Transport Transport
Network Network
Physical Physical
Switching Methods
Two different types of switching methods are used: Circuit switching and Packet switching.
Circuit Switching
Propagation delay
P1
P2
DATA
P3
Ack signal
Ack signal
1 2 3 4
1 2 3 4
1 2 3 4
P1
P2 Packet switching
P3
X.25
It is an interface between DCE and DTE for terminal operation in the packet mode on public data
networks.
It defines how a packet- mode terminal connected to a packet network for the exchange of data.
It defines how the user’s DTE communicates with the network and how packets are sent over that
network using DCE’s.
X.25 has three layers:
Physical layer
Frame layer and
Packet layer
Physical Layer:
At the physical layer, X.25 specifies a protocol called X.21.
This is similar to other physical layer protocols.
X.25 provides data link control using a bit oriented protocol called link access procedure balanced
(LAPB).
Packet Layer:
The Network layer in x.25 is called the Packet Layer Protocol (PLP).
This layer is responsible for establishing the connection, transferring data and terminating
the connection.
It is also responsible for creating the virtual circuits and negotiating network services
between two DTEs.
The Frame layer is responsible for making a connection between a DTE and DCE, the
Packet layer is responsible for making a connection between two DTEs.
End-to-End flow and error control between two DTEs are under the jurisdiction of the
Packet Layer.
Examples of Networks
NOVEL NETWARE
The most popular network in pc world system is novel netware.it was designed to be used by
companies from a mainframes to a network of PCs.
1. In this system, each user has a desk top PC functioning as a client.
2. Some number of power full PCs operate as servers providing file services ,data base
services and other services to a collection of clients it uses a proprietary protocol.
3. It is based an old Xerox network system, XNS with various modifications. Because of five-
layers, it looks much like TCP/IP than ISO OSI.
4. Physical and data link layer can choose an Ethernet, IBM token ring and ARC net protocols.
5. The network layer runs an unreliable connectionless Internet work protocol called ARC net
protocols.
6. It passes packets from source to destination transparently; even both are of different
networks.
7. Application layer uses SAP (Service Advertising protocol), to broadcast a packet and tell
what
ISDN was developed by ITU- T in 1976.It is a set of protocols that combines digital telephony and
data transport services. The whole idea is to digitize the telephone network to permit the
transmission of audio, video, and text over existing telephone lines.
The goal of isdn is to form a wide network that provides universal end –to – end connectivity over
digital media. This can be done by integrating all of the separate transmission services into one
without adding links or subscriber lines.
HISTORY
Initially, telecommunications networks were entirely analog networks and were used for the
transmission of analog information in the form of voice.
With the advent of digital processing, subscribers needed to exchange data as well as voice.
Modems were developed to allow digital exchange over analog lines.
To reduce cost and improve performance, the telephone companies gradually began to add
digital technologies while continuing their analog services to their customers.
Next, customers began to require access to a variety of networks, such as packet- switched
networks and circuit –switched networks. To meet these needs the telephone companies created
Integrated Digital Network (IDN). An IDN is a combination of networks available for different
purposes.
The ISDN integrates customer service with the IDN. With ISDN all customers’ services become
digital rather than analog and will allow the customers services to be made available on demand.
SERVICES
The purpose of the ISDN is to provide fully integrated digital services to users. These services fall
in to three categories: bearer services, teleservices, and supplementary services.
Bearer service
Bearer services provide the means to transfer information (voice, data, and voice) between users
without the network manipulating the content of information.
Tele Service
In teleservices the network may change or process the contents of the data. These services
correspond to layers 4 – 7 of the OSI ISO model. this service include telephony,telefax,videotex,
telex and teleconferencing.
Supplementary service
Supplementary services are those services that provide additional functionality to the bearer
service and teleservices. These services include call waiting, reverse charging, and message
handling.
Reverse
Telex
charging
Teleconferencing
Bearer Services
To allow flexibility, digital pipes between customers and the ISDN office are organized into
multiple channels of different sizes. The ISDN standard defines three channel types, each with a
different transmission rate: bearer channels, data channels, and hybrid channels
Channel Rates
Bearer (B) 64
Data (D) 16,64
Hybrid (H) 384,1536,1920
B Channel
A B channel is defined at a rate of 64 Kbps .It is the basic user channel and can carry any type of
digital information in full duplex mode as long as the required transmission rate does not exceed
64 Kbps. A B channel can be used to carry digital data, digitized voice, or other low data – rate
information.
D Channel
A D channel can be either 16 or 64 Kbps, depending on the need of the user. The primary
function of a D channel is to carry control signaling for the B channels. A D channel carries the
H Channel
H Channels are available with data rates of 384 Kbps (HO), 1536 Kbps (H11), or 1920(H12).
These e rates suit for high data rate applications such as video, teleconferencing and so on.
I SDN
Integrated services digital network
IDN
Packet
switched
Digital
Pipes
ISDN
Circuit
switching
Office
Subscriber loops
………….
User Interfaces
Digital subscriber loops are two types: basic rate interface (BRI ) and primary rate interface
(PRI ) .Each type is suited to a different level of customer needs .Both include one D channel and
some number of either B or H channels.
BRI
The basic rate interface specifies a digital pipe consisting of two B channels and one 16Kbps D
channel.
To ISDN office
PRI
The usual PRI specifies a digital pipe with 23 B channels and one 64 Kbps D channel.
To ISDN office
P R I 1.544 Mbps
PRI requires a digital pipe of 1.544 Mbps. Conceptually, the PRI services is like a large pipe
containing 24 smaller pipes, 23 for the B channels and for the D channel. The rest of the pipe
carries the overhead bits.
One PRI can provide full – duplex transmission between as many as 23 sources and
receiving nodes. The individual transmission are collected from their source and multiplexed on to
a single path for sending to the ISDN office.
Functional Grouping
Functional Grouping used at the subscriber’s premises includes network terminations, terminal
equipment and terminal adapters, enables users to access the services of the BRI and PRI.
An NT1 device controls the physical and electrical termination of the ISDN at user’s internal
system to the digital subscriber loop. These functions are comparable to those defined for the OSI
physical layer.
An NT1 organizes the date stream from connected subscribers into frames that can be sent
over the digital pipe, and translates the frame received from the network into a format usable by
the subscriber’s device.
A NT1 device performs functions at the physical layer, data link, and net work layers of the OSI
model.NT2 provide multiplexing (layer 1),flow control (layer 2), and packetzing (layer 3).An NT2
provides intermediate signal processing between the Data – generating devices and an
NT1.There must be a point to point connection between an NT1 and NT1 ..NT2s are used
primarily to interface between a multi-user system and an NT1 in a PRI.
NT2s can be implemented by a variety of equipment types like a private branch exchange
(digital PBX), a LAN can function as an NT2.
The TE is used by ISDN in the same manner as DTE in other protocol. Examples of TE1 are
digital telephones, integrated voice/data terminals, digital facsimiles.
To provide backward compatibility with a customer’s existing equipment, the ISDN standard
defines a second level of terminal equipment called Terminal Equipment 1 ( TE1 ).This is a non
ISDN device, such as terminal, workstation or regular telephone. This can be used with the help
of another device called a terminal adapter (TA).
Reference Points
This refers to the label used to identify individual interface between two elements of an ISDN
installation. There are four reference points that defines the interface between a subscriber’s
equipment and the network. They are R, S, T and U.
Reference Point R defines the connection between a TE2 and a Ta. Reference Point S defines
the connection between a TE1 or TA and an NT1 or NT2. Reference Point T defines the interface
between an NT2 and NT1. Reference Point U defines the interface between an NT1 and the
ISDN office.
R S U
To ISDN
TE2 TA NT1 Office
S U
TE1 To ISDN
NT1 Office
S T U
To ISDN
TE1 NT
2 NT1 Office
B channel D channel
User’s choice
Layers 4,5,6,7
***************************
15. The----- layer can use the trailer of the frame for error detection.
a. physical b. data link c. session d. presentation
16. The physical layer is concerned with the transmission of -------- over the physical medium.
a. programs b. dialogs c. protocols d.bits.
17. Which of the following is an application layer service?
a. network virtual terminal b. file transfer c. mail service d. all of the
above 18.Transmission media are usually categorized as------
a. fixed or unfixed b. guided media and unguided c. determinate or in determinate
d. metallic and nonmetallic
19. In fiber optics, the signal source is --------waves.
a. light b. radio c. infrared d. very low frequency.
20.Which of the following is not a guided medium?
a. twisted pair b. coaxial cable c. fiber optic cable d. atmosphere
21.X.25 protocol uses ----- for end to end transmission.
a. message switching b. circuit switching. C. the datagram approach to packet switching
d. the virtual circuit approach.
22. The X.25 protocol operates in the ----- of the OSI model.
a. physical layer b. data link layer c.net work layer d. all the above.
23.The physical layer protocol directly specified for the X.25 protocol is------
a. RS- 232 b. X.21 c. DB-15 d. DB- 37
24. The PLP packet is a product of the ------ layer in the X.25 standard.
a. physical b. frame c. packet d. transport
25. The PLP------ 1s used to transport data from upper layers in the X.25 standard
a. S-packet b. data packet c. C-packet d. P-packet
26. X.25 protocol requires error checking at the ----- layer.
a. Physical b. frame c. packet d. b and c
27. X.25 is -------- protocol.
a. a UNI b. an SNI c. AN NNI d. an SSN
28. ISDN is an acronym for ---------------------
a. Information services for digital network b. Internet work system for data networks
c. Integrated signals digital network d. Integrated services digital network
29.The ------ channel is used for telemetry and alarms.
a. B b. C c. D d. H
30. is a group of non—ISDN equipment.
1. Define Computer Network? Give the difference between a network and distributed system?
2. Discuss the applications and goals of the computer networks
3. Explain briefly the functions of different layers of the OSI reference model
4. Give the difference between ISO OSI and TCP /IP model.
5. Discuss the difference between connection –oriented and connections-less services.
6. Give the advantage and disadvantage of frame relay over a leased telephone line.
7. Why does ATM used small, fixed length cells? Explain ATM layers.
8. Explain ISDN design? What are the services that can be provided by the ISDN ?What are
the different ISDN phases?
9. What are the advantages of using layered architecture?
10. Briefly explain about the Novel NetWare and ARPANET
11. Explain X.21 digital interface?
12. Explain the following terms
a) HOST b) IMP c) Subnet d) Protocol e) Interface f) PEER Processor
13. Distinguish between guided and unguided transmission media.
14. Briefly explain the different types of transmission medias?
15. Give the advantages and disadvantages of using fiber optic cable over metallic cable.
********
Introduction
The Data Link Layer break the bit stream into discrete frames and compute the checksum
for each frame. When a Frame arrives at the destination, the checksum is recomputed. If
the newly computed checksum is different from one computed contained in the frame, the
data link layer knows that an error has occurred and takes steps to deal with it.
FRAMING METHODS
In this method a field in the header will be used to specify the number of
CHARACTERS in the frame. When data link layer at the destination sees the character
count, it knows how many characters follow and hence where the end of the frame is.
The trouble with this algorithm is that the count can be garbed by a transmission error
resulting the destination will get out of synchronization and will be unable to locate the
start of the next frame. There is no way of telling where the next frame starts. For this
reason this method is rarely used.
(a) 5 1 2 3 4 5 6 7 8 9 8 0 1 2 3 4 5 6 8 7 8 9 0 1 2 3
Frame 3 Frame 4
Frame 1 Frame 2
5 characters 5 characters 8 characters 8 characters
Error
5 1 2 3 4 7 6 7 8 9 8 01 2 3 4 5 6 8 7 8 9 0 1 2 3 5
Frame 1 Frame 2
(Wrong) Now a character count
In this method each frame will start with a FLAG and ends with a FLAG.
The starting flag is DLE STX ---- Data Link Escape Start of Text
The ending flag is DLE ETX ------- Data link Escape End of Text.
Dis Adv:
1.24 bits are unnecessarily stuffed.
2. Transmission delay.
BIT STUFFING METHOD
In the data if there are FIVE consecutive ONE ‘s are there then a ZERO will be
stuffed.
Ex. The given data is 01111000011111110101001111110 01111101100
Stuffed bits
Advantages:
Network designers have developed two basics strategies for dealing with errors. One way
is to include enough redundant information along with each block of data sent, to enable
the receiver to deduce what the transmitted data must have been .The other way is to
include only enough redundancy to allow the receiver to deduce that an error occurred,
but not which error, and have it request a retransmission. The former strategy uses Error
– correcting codes and the latter uses Error- detecting codes.
1. PARITY METHOD
2. LRC METHOD (Longitudinal redundancy check)
3. CRC METHOD (Cyclic redundancy check)
4. HAMMING CODE METHOD
PARITY METHOD
If one bit or any odd no bits is erroneously inverted during Transmission, the Receiver
will detect an error. How ever if two or even no of bits are inverted an undetected error
occurs.
Let both the transmitter and receiver are agreed on EVEN parity.
Now an error will be detected, since the no of ones received are ODD
The received data is wrong even though the no of ones are EVEN.
bn1 VRC
Character 1 b11 b21 R1
10110111
11010111
00111010
11110000
1
0001011 LRC
Character m Rm 01011111
Parity check b1m b2m bnm
c cn+1
character n
c1 c2 bnm
CRC Method
1. The frame is expressed in the form of a Polynomial F(x).0 1 1 1 1 1 1 0
2. Both the sender and receiver will agree upon a generator polynomial G(x) in
advance.
3. Let ‘r’ be the degree of G(x).Append ‘r’ zero bits to the lower – order end of
frame now it contains m+r bits.
4. Divide the bit string by G(x) using Mod 2 operation.
5. Transmitted frame [T(x)] = frame + remainder
6. Divide T(x) by G(x) at the receiver end. If the result is a zero, then the frame is
transmitted correctly. Ex. Frame: 1101011011
Generator: 10011
Message after appending 4 zero bits: 11010110000
10011
10011
00001
00000
00010
00000
00101
00000
01011
00000
10110
10011
01010
00000
10100
10011
01110 Remainder
00000
1110
10011
10011
00001
00000
00010
00000
00101
00000
01011
00000
10111
10011
01001
00000
10011
10011
00000 Remainder
00000
0000
Hamming codes provide another method for error correction. Error bits, called Hamming
bits, are inserted into message bits at random locations. It is believed that the
randomness of their locations reduces the odds that these Hamming bits themselves
would be in error. This is based on a mathematical assumption that because there are so
many more message bits compared with Hamming bits, there is a greater chance for a
message bit to be in error than for a Hamming bit to be wrong. Determining the
placement and binary value of the Hamming bits can be implemented using hardware,
but it is often more practical to implement them using software. The number of bits in a
message (M) are counted and used to solve the following equation to determine the
number of Hamming bits (H) to be used:
2H ≥ M + H + 1
Once the number of Hamming bits is determined, the actual placement of the bits into the
message is performed. It is important to note that despite the random nature of the
Hamming bit placements, the exact sample placements must be known and used by both
the transmitter and receiver. Once the Hamming bits are inserted into their positions, the
numerical values of the bit positions of the logic 1 bits in the original message are listed.
The equivalent binary numbers of these values are added in the same manner as used in
previous error methods by discarding all carry results. The sum produced is used as the
states of the Hamming bits in the message. The numerical difference between the
Hamming values transmitted and that produced at the receiver indicates the bit position
that contains a bad bit, which is then inverted to correct it.
Ex. The given data
10010001100101(14- bits)
The number of hamming codes
2H ≥ M + H + 1
H = ? M = 14 to satisfy this equation H should be 5 i.e. 5 hamming code
bits should be incorporated in the data bits.
1001000110H0H1H0H1H
Now count the positions where binary 1’s are present. Add using mod 2 operation (Ex-OR). The
result will give the Hamming code at the transmitter end.
This Hamming code will be incorporated at the places of ‘H’ in the data bits and the data
will be transmitted.
How to find out there is an error in the data?
Let the receiver received the 12th bit as zero. The receiver also finds out the Hamming
code in the same way as transmitter.
The decimal equivalent for the binary is 12 so error is occurred at 12th place.
Since the transmitter waits for Δt time for an Ack this protocol is called stop and wait
protocol.
A B
A B
At this situation protocol fails because the receiver receives a duplicate frame and there is
no way to find out whether the receiver frame is original or duplicate. So the protocol fails
at this situation.
Now what is needed is some way for the Rx to distinguish a frame and a duplicate. To
achieve this, the sender has to put a sequence number in the header of each frame it
sends. The Rx can check the sequence number of each arriving frame to see if it is a new
frame or a duplicate.
6. Now A thinks that the Ack received is the ack of new frame F0 and A sends next
frame F1. So a frame F0 is missed. At this situation this protocol fails.
In most practical situations there is a need of transmitting data in both directions. This can
be achieved by full duplex transmission. If this is done we have two separate physical
circuits each with a ‘forward ‘ and ‘reverse’ channel. In both cases, the reverse channel is
almost wasted. To overcome this problem a technique called piggy backing is used.
The technique of temporarily delaying outgoing acknowledgements so that they can be
hooked onto the next outgoing data frame is known as piggy backing.
However, piggybacking introduces a complication not present with separate
acknowledgements. How long should the data link layer wait longer than the sender’s
timeout period, the frame will be retransmitted, defeating the whole purpose of having
acknowledgements. Of course, the data link layer cannot foretell the future, so it must
resort to some ad hoc scheme, such as waiting a fixed number of milli seconds. If a new
packet arrives quickly, the acknowledgement is piggy backed onto it; otherwise, if no new
packet has arrived by the end of this time period, the data link layer just sends a separate
acknowledgement frame.
In all sliding window protocols, each outbound frame contains a sequence number,
ranging from 0 up to some maximum. The maximum is usually 2n –1 so the sequence
number fits nicely in an n-bit field. The stop-and-wait sliding window protocol uses n=1,
restricting the sequence numbers to 0 and 1, but more sophisticated versions can use
arbitrary n.
The essence of all sliding window protocols is that at any instant of time, the sender
maintains a set of sequence numbers corresponding to frames it is permitted to send.
These frames are said to fall with in the sending window. Similarly the receiver also
maintains a receiving window corresponding to the set of frames it is permitted to accept.
The sender’s window and the receiver’s window need not have the same lower and upper
limits, or even have the same size. In some protocols they are fixed in size, but in others
they can grow or shrink as frames are sent and received.
The sequence numbers with in the sender’s window represent frames sent but as yet not
acknowledged. Whenever a new packet arrives from the network layer, it is given the next
Sender
7 0 7 0 7 0 7 0
6 1 6 1 6 1 6 1
5 2 5 2 5 2 5 2
4 3 4 3 4 3 4 3
Receiver
7 0 7 0 7 0 7 0
6 1 6 1 1 1
6 6
5 2 5 2 5 5
2 2
4 3 4 3 3 3
4 4
(a) Initially (b) After the first frame has been sent c) After the first frame has been
received. d) After the first acknowledgement has been received.
PIPELINING
1. Upto now we made the assumption that the transmission time required for a frame to
arrive at the receiver plus the transmission time for the ack to come back is negligible.
2. Sometimes this is not true, when there is a long round trip propagation time is there.
3. In these cases round trip propagation time can have important implications for the
efficiency of the bandwidth utilization.
A B
250 ms + 20 ms
250 ms
i.e. We are wasting 96% of channel time. To overcome this problem we will go for a
technique called PIPELIING.
In this technique, the sender is allowed to transmit upto ‘w ‘ frames before blocking,
instead of just 1.With an appropriate choice of w the sender will be able to continuously
By the time it has finished sending 26 frames, at t=520 ms, the ack for frame 0 will have
just arrived. Thereafter ack will arrive every 20 ms, so the sender always gets permission
to continue just when it needs it.
Hence, we can say the sender window size is 26.
Derivation:
Due to round trip delay the time taken will be (l/b + R) Sec = l+Rb/b Sec
Ex 1. A channel has a bit rate of 4 kbps and a propagation delay of 20msec.For what
rage of frame sizes does stop and wait give an efficiency of at least 50 % ?
One way called in go back n, the receiver simply to discard all subsequent frames,
sending no acknowledgements for the discard frames. In the other words, the data link
layer refuses to accept any frame except the next one it must give to the network layer.
Selective Repeat:
The receiving data link layer store all the correct frames following the bad frame, not all its
successors. If the second try succeeds the receiving data link layer will now have many
correct frames in sequence, so they can all be handed off to the network layer quickly and
the highest number acknowledged. This strategy corresponds to a receiver window larger
than 1.
0 1 2 3 4 5 2 3 4 5 6 7 0
0 1 E D D D 2 3 4 5 6
(a) Go-back-N
Error Discarded frames
0 1 E 3 4 5 2 6
- In broadcast network, the key issue is how to share the channel among
several users.
- Ex a conference call with five people
-Broadcast channels are also called as multi-access channels or random access
channels.
-Multi-access channel belong to a sublayer at the DL layer called the MAC sublayer.
The Channel Allocation problem:
Drawbacks: -1) Channel is wasted if one or more stations do not send data.
2) If users increases this will not support.
USER
TIME
to+t to+2t
to
to+3t Time
Vulnerable
0.184
Pure ALOHA : S = Ge-G
0.5 1.0
G (attempts per packet time)
Slotted ALOHA
-In 1972, Roberts’ devised a method for doubling the capacity of ALOHA system.
-In this system the time is divided into discrete intervals, each interval corresponding to
one frame.
Protocols in which stations listen for a carrier (transmission) and act accordingly are
called carries sense protocols.
Persistent CSMA
When a station has data to send, it first listens to the channel to see if any one else is
transmitting at that moment. If the channel is busy, the station waits until it become idle.
When the station detects an idle channel, it transmits a frame. If a collision occurs, the
station waits a random amount of time and starts all over again. The protocol is called 1-
persistent also because the station transmits with a probability of 1 when it finds the
channel idle.
The propagation delay has an important effect on the performance of the protocol. The
longer the propagation delay the worse the performance of the protocol.
Even if the propagation delay is zero, there will be collisions. If two stations listen the
channel, that is idle at the same, both will send frame and there will be collision.
With persistent CSMA, what happens if two stations become active when a third station is
busy? Both wait for the active station to finish, then simultaneously launch a packet,
resulting a collision. There are two ways to handle this problem.
a) P-persistent CSMA b) exponential backoff.
P-persistent CSMA
The first technique is for a waiting station not to launch a packet immediately when the
channel becomes idle, but first toss a coin, and send a packet only if the coin comes up
heads. If the coin comes up tails, the station waits for some time (one slot for slotted
CSMA), then repeats the process. The idea is that if two stations are both waiting for the
medium, this reduces the chance of a collision from 100% to 25%. A simple
generalization of the scheme is to use a biased coin, so that the probability of sending a
packet when the medium becomes idle is not 0.5, but p, where 0< p < 1. We call such a
scheme P-persistent CSMA. The original scheme, where p=1, is thus called 1-persitent
CSMA.
Exponential backoff
The key idea is that each station, after transmitting a packet, checks whether the packet
transmission was successful. Successful transmission is indicated either by an explicit
acknowledgement from the receiver or the absence of a signal from a collision detection
circuit. If the transmission is successful, the station is done. Otherwise, the station
retransmits the packet, simultaneously realizing that at least one other station is also
contending for the medium. To prevent its retransmission from colliding with the other
station’s retransmission, each station backs off (that is, idles) for a random time chosen
from the interval
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
1 1 1 1 3 7 1 1 1 5
Since everyone agrees on who goes next, there will never be any collisions. After the last
ready station has transmitted its frame, an event all stations can easily monitor, another N
bit contention period is begun. If a station becomes ready just after its bit slot has passed
by, it is out of luck and must remain silent until every station has had a chance and the bit
map has come around again. Protocols like this in which the desire to transmit is
broadcast before the actual transmission are called reservation protocols.
Binary Countdown
A problem with the basic bit-map protocol is that the overhead is 1 bit per station. A
station wanting to use the channel now broadcasts its address as a binary bit string,
starting with the high-order bit. All addresses are assumed to be the same length. The
bits in each address position from different stations are BOOLEAN ORed together. We
will call this protocol binary countdown. It is used in Datakit.
As soon as a station sees that a high-order bit position that is 0 in its address has been
overwritten with a 1, it gives up. For example, if station 0010,0100,1001, and 1010 are all
trying to get the channel, in the first bit time the stations transmit 0,0,1, and 1,
respectively. Stations 0010 and 0100 see the 1 and know that a higher-numbered station
is competing for the channel, so they give up for the current round. Stations 1001 and
1010 continue.
0010 0---
0100 0---
1001 100-
1010 1010
Result 1010
The second cable type was 10Base2 or thin Ethernet, which, in contrast to the garden-
hose-like thick Ethernet, bends easily. Connections to it are made using industry standard
BNC connectors to form T-junctions, rather than using vampire taps. These are easier to
use and more reliable. Thin Ethernet is much cheaper and easier to install, but it can run
for only 200m and can handle only 30 machines per cable segment.
Cable breaks, bad taps, or loose connectors can be detected by a devise called time
domain reflectometry.
For 10Base5, a transceiver is clamped securely around the cable so that its tap makes
contact with the inner core. The transceiver contains the electronics that handle carrier
detection and collision detection. When a collision is detected, the transceiver also puts a
Computer Networks S.SANDHYA
RANI
special invalid signal on the cable to ensure that all other transceivers also realize that a
collision has occurred.
The transceiver cable terminates on an interface board inside the computer. The interface
board contains a controller chip that transmits frames to, and receives frames from, the
transceiver. The controller is responsible for assembling the data into the proper frame
format, as well as computing checksums on outgoing frames and verifying them on
incoming frames.
With 10Base2, the connection to the cable is just a passive BNC T-junction connector.
The transceiver electronics are on the controller board, and each station always has its
own transceiver.
With 10Base-T, there is no cable at all, just the hub (a box full of electronics). Adding or
removing a station is simple in this configuration, and cable breaks can be detected
easily. The disadvantage of 10Base-T is that the maximum cable run from the hub is only
100m, may be 150m if high-quality (category 5) twisted pairs are used. 10Base-Tis
becoming steadily more popular due to the ease of maintenance. 10Base-F, which uses
fiber optics. This alternative is expensive due to the cost of the connectors and
terminators, but it has excellent noise immunity and is the method of choice when running
between buildings or widely separated hubs.
Each version of 802.3 has a maximum cable length per segment. To allow larger
networks, multiple cables can be connected by repeaters. A repeater is a physical layer
device. It receives, amplifies, and retransmits signals in both directions. As far as the
software is concerned, a series of cable segments connected by repeaters is no different
than a single cable (except for some delay introduced by the repeater). A system may
contain multiple cable segments and multiple repeaters, but no two transceivers may be
more than 2.5km apart and no path between any two transceivers any traverse more than
four repeaters.
C
Trap
Backbone
A B C D
Repeater
Bit stream 1 0 0 0 0 1 0 1 1 1 1
Binary encoding
Manchester encoding
Destination Source
Preamble Data Pad Checksum
address address
Switched Ethernet:
- 10 Base-T Ethernet is a shared media network.
- The entire media is involved in each transmission.
- The HUB used in this network is a passive device. (not intelligent).
- In switched Ethernet the HUB is replaced with switch. Which is a active device
(intelligent )
Fast Ethernet
100 Base_x
Gigabit Ethernet
Bytes >
1 1 1 2 or 6 2 or 6 0-8182 4 1
Frame control
Start of delimiter End
delimiter
Preamble
The frame control field is used to distinguish data frames from control frames. Fro data
frames, it carries the frame’s priority. It can also carry an indicator requiring the
destination station to acknowledge correct or incorrect receipt of the frame.
For control frames, the frame control field is used to specify the frame type.
The allowed types include token passing and various ring maintenance frames,
including the mechanism for letting new stations enter the ring, the mechanism for
allowing stations to leave the ring, and so on.
Connecting devices
Connecting
devices
Networking Internetworking
devices devices
Session Session
Transport Transport
Network Network
Router
Data link Data link
Bridge
Physical Physical
Repeate
Bridges
LANS can be connected by devices called bridges, which operate in the data link layer.
Bridges do not examine the network layer header and can thus copy IP, IPX, and OSI
packets equally well.
The various reasons why the bridges are used.
1) Many university and corporate departments have their own LANS, primarily to connect
their own personal computers, workstations, and servers. Since the goals of the various
departments differ, different departments choose different LANS, without regard to what
other departments are doing. Sooner or later, there is a need for interaction, so bridges
are needed.
2) The organization may be geographically spread over several buildings separated by
considerable distances. It may be cheaper to have separate LANS in each building and
connect them with bridges and infrared links than to run a single coaxial cable over the
entire site.
3) It may be necessary to split what is logically a single LAN into separate LANS to
accommodate the load. Putting all the workstations on a single LAN- the total bandwidth
needed is far too high. Instead multiple LANS connected by bridges are used.
4) In some situations, a single LAN would be adequate in terms of the load, but the
physical distance between the most distant machines is too great (e.g., more than 2.5km
for 802.3). Even if laying the cable is easy to do, the network would not work due to the
B1 B2
LAN 1
Initial frame
Routing algorithms
The main function of the network layer is routing packets from the source machine to the
destination machine. Routing algorithm can be grouped into two major classes. Nonadaptive and
Adaptive algorithms.
3) When the network is booted the 3) The routers are not downloaded.
routers are downloaded.
4) This is a static routing. 4) This is a dynamic routing.
B(2,A) B(2,A)
C(9,B) C(9,B)
E(4,B) E(4,B)
A F(∞,-) D(∞,-) A F(6,E) D(∞,1)
B(2,A) B(2,A)
C(9,B) C(9,B)
E(4,B) E(4,B)
A F(6,E) D(∞,-) A F(6,E) D(∞,-)
A B C D E F
9 4 1 7 4
A AB ABC ABFD AE AEF
9 8 3 2 4
B C AB BC BFD BFE BF
20 B
20 10 4 8 3 3 2
Source
C CBA CB CD CE CEF
A D
20 20 1 3 3 3 4
D DFBA DFB DC DCE DF
20 10
7 2 3 3 4
F E EA EFB EC ECD EF
50 E
(a) 4 4 4 4 4
F FEA FB FEC FD FE
(b)
Distance Vector Routing:
This is a dynamic routing algorithm. This algorithm operates by having each router
maintain a table (i.e. a vector) giving the best known distance to each destination and which line
to use. These tables are updated by exchanging information with the neighbors.
The routing table indexed by and containing one entry for each router in the subnet. This
entry contains two parts: The preferred outgoing line to use for the destination and an estimate of
time or distance to that destination. The metric used might be number of hops, time delay in
msec, total number of packets queued along the path or something similar.
The router is assumed to know the distance to each of its neighbors. If the metric is hops,
the distance is just one hop. If the metric is queue length, the router examines each queue. If the
metric is delay the router can measure it directly with a special ECHO packets.
Consider an example, in which the delay is used as metric and the router knows the delay
to each of its neighbors. Once every T msec each router send to each neighbor a list of its
estimated delays to each destination. It also receives a similar list from each neighbor. Let x i
being x’s estimate of how long it takes to get router ‘i’. If the router knows that the delay to x is ‘m’
m sec. To get router i via x is (xi +m) m sec. By performing this calculation for each neighbor, a
router can find out which estimate is the best and use that estimate and the corresponding line in
its new routing table.
B 12 36 31 28 20 A
G 25 18 19 36 28 I
E C
H
F D 40 27 8 24 20 H
E 14 7 30 22 17 I
I F 23 20 19 40 30 I
J K L
G 18 31 6 31 18 H
H 17 20 0 19 12 H
Subnet
I 21 0 14 22 10 I
J 9 11 7 10 0 -
K 24 22 22 0 6 K
L 29 33 9 9 15 K
JA JI JH JK
delay delay delay delay New
is is is is routing
8 10 12 6 table for J
Region 1 Region 2
Dest. Line Hops Dest. Line Hops
1B 2A 2B 1A - - 1A - -
1B 1B 1 1B 1B 1
1A 1C 1C 1C 1 1C 1C 1
2C 2D 2A 1B 2 2 1B 2
2B 1B 3 3 1C 2
2C 1B 3 4 1C 3
3A 1C 4 5 1C 4
3B 1C 3
3C 1C 2
4A 5B 5C 4A 1C 3
3A 4B 1C 4
4B 4C 4C 1C 4
5E
3B 5A 1C 4
5B 1C 5
5C 1B 5
Region 3 Region 4 Region 5 5D 1C 6
5E 1C 5
E
F D (a)
I
G
H
L N J
K
O
M
B
A C
E
F D
I
G
H L
J
K N
O
M
I
(c)(c)
F H J N
E K G O O
A D M
E C G K
H
B L
L
B
Multicast Routing :
For some applications, it is necessary for one process to send a message to all other members of
the group. If the group is small, it can just send each other member a point-to-point message. If
the group is large this strategy is expensive. Some times broad casting is used, but using broad
casting is used, but using broadcasting to inform 1000 machines on a million node network is
inefficient because most receivers are not interested in the message. Thus it is needed to send
message to well-defined groups. Sending message to such a group is called ‘multicasting’.
To do multicasting, group management is required. Some way is needed to create and
destroy groups and for processes to join and leave groups. When process joins a group, it informs
its host of this fact. It is important that routers know which of their hosts belong to which group.
Either hosts most inform their routers about change in group membership or routers must query
their hosts periodically. Routers tell their neighbors, so the information propagates through the
subnet.
To do multicast routing, each router computes a spanning tree covering all other routers in the
subnet. When a process sends a multicast packet, to a group, the first router examines its
spanning tree and prunes it, removing all lines that do not lead to hosts that are members in the
group. Multicast packets are forwarded. Only along the appropriate spanning tree.
Computer Networks S.SANDHYA
RANI
Congestion Control Algorithms
What is Congestion?
When too many packets are present in the subnet performance degrades. This situation is called
Congestion.
The number of packets dumped into the subnet are within its carrying capacity, they are all
delivered.
However, if the traffic increases too far, the routers are unable to cope and begin losing packets.
At very high traffic, performance collapse completely and almost no packets are delivered.
What factors will lead to congestion?
1. Three or four input lines and only one output line queue will build up.
If there is insufficient memory to hold all of them, packets will lost.
Adding infinite memory congestion gets worse, because by the time packets get to the
front of the queue, the time out and duplicates have been sent.
2. Slow processors (routers) can cause congestion.
A slow processor perform the book keeping tasks very slow, queues will build up.
3. Low band-width lines also cause congestion
Upgrading lines but not changing the processor and vice-versa shifts the bottleneck.
Ex:
Consider a network with a capacity of 1000Gbps on which a super computer is trying to
transfer a file to a personal computer at 1Gbps.Here a flow control is needed.
Consider a network with 1Mbps lines and 1000 large computers, more than half are trying
to transfer files a 100kbps to the other half. The problem is here is the total offered traffic
exceeds than the network handle.
Imagine a bucket with a small hole in the bottom. No matter at what rate water enters the bucket,
the outflow is at a constant rate, , when there is any water in the bucket, and zero when the
bucket is empty. Also, once the bucket is full, any additional water entering it spills over the sides
and is lost.
Packet
Unregulated
Flow
Regulated
flow
Network
The same idea can be applied to packets, as shown in fig. Conceptually, each host is connected
to the network by an interface containing a leaky bucket, that is, a finite internal queue. If a packet
arrives at the queue when it is full, the packet is discarded. In other words, if one or more
processes within the host try to send a packet when the maximum numbers are already queued,
the new packet is unceremoniously discarded. This arrangement can be built into the hardware
interface or simulated by the host operating system.
The host is allowed to put one packet per clock tick onto the network. Again, this can be enforced
by the interface card or by the operating system. This mechanism turns an uneven flow of packets
from the user processes inside the host into an even flow of packets onto the network, smoothing
out bursts and greatly reducing the chances of congestion.
Implementing the original leaky bucket algorithm is easy. The leaky bucket consists of a finite
queue. When a packet arrives, if there is room on the queue it is appended to the queue;
otherwise, it is discarded. At every clock tick, one packet is transmitted (unless the queue is
empty).
Host Host
Computer Computer
One token
is added
to the bucket The bucket
holds
every T
tokens
Each router can easily monitor the utilization of its output lines and other resources. It can
estimate each line about the recent utilization of that line (u). Periodically a sample at the
instantaneous line utilization (f) can be mad and u updated.
unew = a uold + (1-a)f
Where a is constant determines how fast the router forgets recent history.
Whenever u moves above the threshold, the output line enters a ‘warning’ state. Each new
arriving packet is checked if its output line is warning state. If it is some action is taken.
Choke packets:
In this algorithm, the router sends a choke packet back to the source host. The original packet is
tagged so that it will not generate any more choke packets farther along the path and is then
forwarded in the usual way.
When the source host gets the choke packet, it is required to reduce the traffic sent to the
specified destination by X percent. Since other packets aimed at the same destination are
probably already under way and will generate yet more choke packets, the host should ignore
choke packets referring to that destination for a fixed time interval. After that period has expired,
the host listens for more choke packets for another interval. If one arrives, the line is still
congested, so the host reduces the flow still more and begins ignoring choke packets again. If no
choke packets arrive during the listening period, the host may increase the flow again.
The first choke packet causes the data rate to be reduced to 0.50 of its previous rate, the next
one causes a reduction to 0.25, and so on. Increases are done in smaller increments to prevent
congestion from reoccurring quickly.
Hop by Hop choke packets:
For example, let the host A is sending packets to D. as shown in fig.(1). If D runs out of buffers, it
will take sometime for a choke packet to reach A to tell it to slow down. This is shown in fig
2,3,4.In this time another packets will be sent. Only after some more time the router D will be
noticing a slower flow (fig.7).
In other approach, as soon as choked packet reaches to F it cuts down the flow to D and D will
get immediate relief. (like a headache remedy in a TV). In the next set up, when choke reaches to
E it also cuts down the flow to F which in turn gives relief to F. Finally, when the choke packet
richer A and the flow genuinely slows down.
B C B C
A D A D
Heavy
flow
E F E F
Ch Ch
Ch Ch
Reduced
flow
(b)
Flow is still at
maximum rate
Ch-choke
Flow is reduced
(a)
Internetworking
When two or more networks are connected it is called Internet. There will be a variety of different
networks will always be around, for the following reasons.
1) Different networks will use different technologies like personal computers run TCP/IP,
mainframes run on IBM’s SNA.
2) As computers and networks get cheaper, the place where decisions get made moves
downwards in organizations.
3) As new hardware developments occur, new software will be created to fit the new hardware.
The purpose of interconnecting all these networks is to allow users on any of them to
communicate with users don all the other ones to allow users on any of them to access data on
any of them.
Networks differ in many ways. In the network layer the following differences can occur (fig.5.43).
At the network layer, TCP/IP supports the internetwork protocol .IP, in turn, contains four
supporting protocols:ARP ,RARP ,ICMP,and IGMP.
IP is the transmission mechanism used by the TCP/IP protocols. It is an un –reliable and
connectionless datagram protocol – a best effort delivery service. This is like a post office service.
The post office does its best to deliver the mail but does not always succeed. If an unregistered
letter is lost. it is up to the sender or would recipient to discover the loss and rectify the problem.
The post office itself does not keep track of every letter and cannot notify a sender of loss or
damage. An example of a situation similar to pairing IP with a protocol that contains reliability
functions is a self addressed ,stamped postcard included in a letter mailed through the post office.
when the letter is delivered , the receiver mails the postcard back to the sender to indicate
success. If the sender never receives the postcard, he or she assumes the letter was lost and
sends out another copy.
Packets in IP layer are called Datagrams. A Datagram is a variable length packet(upto 65,536
bytes) consisting of two parts : Header and Data. The header can be from 20 to 60 bytes and
contains information essential to routing and delivery.
Header length (HLEN) The HLEN field defines the length of the header in multiples of four
bytes .The four bits can represent a number between 0 to 15,which,when multiplied by 4,gives a
maximum of 60 bytes.
Service Type. The service type field defines how datagram should be handled. It includes bits
that define the priority of the datagram. It also contains bits that specify the type of service the
sender desires such as the level of throughput, reliability, and delay.
Total Length The total length field defines the total length of the IP datagram. It is a two-byte
field (16 bits) and can define up to 65,535 bytes.
Identification The identification field is used in fragmentation. A datagram, when passing through
different networks, may be divided into fragments to match the network frame size. When this
happens, each fragment is identified with a sequence number in this field.
Flags The bits in the flags field deal with fragmentation (the datagram can or can not be
fragmented; can be first, middle, or last fragment; etc.).
Fragmentation offset The fragmentation offset is a pointer that shows the offset of the data in
the original datagram (if it is fragmented).
Time to live The time to live field defines the number of hops a datagram can travel before it is
discarded. The source host, when it creates the datagram, sets this field to an initial value. Then,
as the datagram travels through the Internet, router by router, each router decrements this value
by 1. If this value becomes 0 before the datagram reaches its final destination, the datagram is
discarded. This prevents a datagram from going back and forth forever between routers.
Protocol The protocol field defines which upper-layer protocol data are encapsulated in datagram
(TCP, UDP, ICMP etc.).
Header Checksum This is a 16-bit field used to check the integrity of the header, not the rest of
the packet.
Source address The source address field is a four-byte (32-bit) Internet address. It identifies the
original source of the datagram.
Destination address The destination address field is a four-byte (32-bit) Internet address. It
identifies the final destination of the datagram.
Options The options field gives more functionality to IP datagram. It can carry fields that control
routing, timing, management, and alignment.
ADDRESSING
In addition to the physical address the internet requires an additional addressing convention : an
address that identifies the connection of a host to its network.
Class A :
This can accommodate more hosts since 3 bytes are reserved for HOSTID. Class A will begin
with 0 .
Class B :
This will start with 10 and Host id will have 2 bytes length.
Class C :
This will start with 110 and Hostid will have 1 byte length.
Class D:
This will start with 1110 . This is reserved for Multicast addresses.
Class E :
This is reserved for feature use and will start with 1111 .
CLASS A :
000
0 Netid Hostid
CLASS B:
10 Netid 000
Hostid
Class C :
Class D :
Class E :
To make 32 bit form shorter and easier to read, Internet addresses are usually written in decimal
form with decimal points separating the bytes – dotted – decimal notation.
128.11.3.31
From To
From To
128.0.0.0
12 191.255.255.255 Class B
From To
From To
224.0.0.0 239.255.255.255 Class D
From To
a. 4.23.145.90
b. 227.34.78.7
c. 246.7.3.8
d. 129.6.8.4
e. 198.76.9.23
Example:
a. 4.23.145.90
b. 227.34.78.7
c. 246.7.3.8
d. 129.6.8.4
e. 198.76.9.23
TCP/IP supports four other protocols in the network layer :ARP,RARP,ICMP,and IGMP.
The address resolution Protocol associates an ip address with physical address. On a typical
physical network, such as a LAN, each device on a link is identified by a physical or station
address usually imprinted on the network interface card.(NIC)
Physical address have local jurisdiction and can be changed easily. For example, if the NIC on
a particular machine fails, the physical address changes. The IP address, on the other hand ,have
universal jurisdiction and cannot be changed. ARP is used to find the physical address of the
node when its Internet address is known.
Anytime a host or a router needs to find the physical address of another host on its
network, it formats an ARP query packet that includes the IP address and broadcast it over the
network. Every host on the network receives and processes the ARP packet, but only the
intended recipient recognizes its internet address and sends back its physical address. The host
both to its cache memory and to the datagram header, then sends the datagram on its way.
Reverse Address resolution protocol(RARP)
The RARP allows a host to discover its internet address when it knows only its physical
address. The question here is ,why do we need RARP? A host is supposed to have its internet
address stored on its hard disk !
RARP works much like ARP. The host wishing to retrieve its internet address broadcasts an
RARP query packet that contains its physical address to every host on its physical network. A
server on the network recognizes the RARP packet and returns the host’s internet address.
Internet Control Message Protocol (ICMP)
The Internet control message protocol is a mechanism used by hosts and routers to send
notification of datagram problems back to the sender.
IP is an unreliable and connectionless protocol. ICMP allows IP to inform a sender if a
datagram is undeliverable. A datagram travels from router to router until it reaches one that can
deliver it to its final destination. If a router is unable to route or deliver the datagram because of
unusual conditions or due to congestion, ICMP allows it to inform the original source.
ICMP uses echo test/reply to test whether a destination is reachable and responding. It
also handles both control and error message, but its sole function is ti\o report problems, not
correction them. A datagram carries only source and destination address. For this reason ICMP
can send message only to the source, not to an intermediate router.
Expected questions
1.What is the difference between the adaptive and non-adaptive routing algorithms.
2.Explain the shortest path routing algorithm.
3.Explain the services that are provided by the network layer.
4.Explain Flooding routing algorithm.
5.Explain the Distance Vector Routing algorithm.
6.What is the count – to – infinity problem?
7.Explain link state routing algorithm.
8.Explain the Hierarchical Routing algorithm.
9. Explain Broadcast Routing and Multicast Routing.
10. What is congestion? Give the general principles of congestion control?
11.Explain Open loop and Close loop solutions for congestion.
12.How traffic shaping will be done to control congestion?
13.Explain The Leaky Bucket algorithm.
14. Explain the Token Bucket algorithm.
15. How the congestion can be controlled in Virtual Circuits?
16.What is a Choke packet? Explain when a choke packet is used.
17.Expalin the IP protocol.
18What is meant by Load shedding and Jitter control?
19. Explain the ICMP and ARP.
20. Explain the different IP address formats. For a hierarchical routing with 4800 routers, what
region and cluster sizes should be chosen to minimize the size of routing table for a three-layer
hierarchy?
* * * * *
Quiz Questions
* * * * *
Transport layer
duties
It treats each as an independent entity. The transport layer, on the other hand, makes sure that
the entire message (not just a single packet) arrives intact. Thus, it oversees the end-to-end
(source –to-destination) delivery of an entire message.
Addressing
The transport layer interacts with the functions of the session layer. However, many protocols (or
protocol stacks, meaning groups of protocols that interact at different levels) combine session,
presentation, and application level protocols into a single packages, called an application. In these
cases, delivery to the session layer functions is, in effect, delivery to the application. In these cases,
delivery to the session layer functions is, in effect, delivery to the application. So communication
occurs not just from end machine to end machine but from end application to end application. Data
generated by an application on one machine must be received not just by the other machine but by
the correct application on that other machine.
To ensure accurate delivery from service access point to service access point, we need another
level of addressing in addition to those at the data link and network levels. Data link level
protocols need to know which two computers within a network are communicating. Network level
protocols need to know which two computers within an internet are communicating. But at the
transport level, the protocol needs to know which upper-layer protocols are communicating.
Reliable Delivery
At the transport layer, reliable delivery has four aspects: error control, sequence control, loss
control, and duplication control.
Error Control
When transferring data, the primary goal of reliability is error control.
But if we already have error handling at the data link layer, why do we need it at the transport
layer? Data link layer functions guarantee error-free delivery node-to-node for each link. However,
node-to-node reliability does not ensure end-to-end reliability.
Sequence Control
The second aspect of reliability implemented at the transport layer is sequence control. On the
sending end, the transport layer is responsible for ensuring that data units received from the
upper layers are usable by the lower layers. On the receiving end, it is responsible for ensuring
that the various pieces of a transmission are correctly reassembled.
Segmentation and Concatenation
When the size of the data unit received from the upper layer is too long for the network layer
datagram or data link layer frame to handle, the transport protocol divides it into smaller, usable
blocks. The dividing process is called segmentation. When, on the other hand, the size of the data
units belonging to a single session are so small that several can fit together into a single
datagram or frame, the transport protocol combines them into a single data unit. The combing
process is called concatenation.
Sequence Numbers
Most transport layer services add a sequence number at the end of each segment. If a longer data
unit has been segmented, the numbers indicate the order for reassembly. If several shorter units
have been concatenated, the numbers indicate the end of each submit and allow them to be
separated accurately at the destination. In addition, each segment carries a field that indicates
whether it is the final segment of a transmission or a middle segment with more still to come.
Loss Control
The third aspect of reliability covered by the transport layer is loss control. The transport layer
ensures that all pieces of a transmission arrive at the destination, not just some of them. When data
have been segmented for delivery, some segments may be lost in transit. Sequence numbers allow
the receiver’s transport layer protocol to identify any missing segments and request redelivery.
Duplication Control
The fourth aspect of reliability covered by the transport layer is duplication control. Transport layer
functions must guarantee that no pieces of data arrive at the receiving system duplicated. Just as
they allow identification of lost packets, sequence numbers allow the receiver to identify and
discard duplicate segments.
Transport 1 2 3 2 Transport
layer layer
layer
TELNET TELNET
(client) (server)
(51001) (23)
TCP or UDP TCP OR UDP
IP IP
Physical Physical
Each port is defined by a positive integer address carried in the header of a transport layer
packet. An IP datagram uses the host’s 32-bit Internet address. A frame at the transport level
uses the process port address of 16 bits, enough to allow the support of up to 65,536(0 to 65535)
ports.
Variable
8 bytes
H Data
eader
UDP provides only the basic functions needed for end-to-end delivery of a transmission. It does
not provide any sequencing or recording functions and cannot specify the damaged packet when
reporting an error (for which it must be paired with ICMP). UDP can discover that an error has
occurred; ICMP can then inform the sender that a user datagram has been damaged and
discarded. Neither, however, has the ability to specify which packet has been lost. UDP contains
only a checksum; it does not contain an ID or sequencing number for a particular data segment.
The scope of the services provided by TCP requires that the segment header be extensive. A
comparison of the TCP segment format with that of a UDP user datagram shows the differences
between the two protocols. TCP provides a comprehensive range of reliability functions but
sacrifices speed (connections must be established, acknowledgments waited for , etc.).Because
of its smaller frame size, UDP is much faster than TCP, but at the expense of reliability. A brief
description of each field is in order.
Header Data
Source port address. The source port address defines the application program in the
source computer.
Destination port address. The destination port address defines the application program
in the destination computer.
Sequence number. A stream of data from the application program may be divided into
two or more TCP segments. The sequence number field shows the position of the data in
the original data stream.
Acknowledgement number. The 32-bit acknowledgement number is used to
acknowledge the receipt of data from the other communicating device. This number is
valid only if the ACK bit in the control field(explained later) is set. In this case, it defines the
byte sequence number that is next expected.
Header Length (HLEN). The four-bit HLEN field indicates the number of 32-bit (four-byte)
words in the TCP header. The four bits can define a number up to 15.This is multiplied by
4 to give the total number of bytes in the header. Therefore, the size of the header can be
a maximum of 60 bytes (4x15).Since the minimum required size of the header is 20 bytes,
40 bytes are thus available for the options section.
Reserved. A six-bit field is reserved for future use.
Control. Each bit of the six-bit control field functions individually and independently. A bit
can either define the use of a segment or serve as a validity check for other fields. The
Network Security
Security Attacks
Attacks on the security of a computer system or network are best characterized by viewing the
function of the computer system as providing information.
In this case, the keyword is monarchy. The matrix is constructed by filling in the letters of the
keyword from left to right and from top to bottom, and then filling in the remainder of the matrix
ENCRYPTION DECRYPTION
P10
8-bit plaintext
8-bit plaintext
Shift
IP
IP-1
P8
K1 K1
fk fk
Shift
SW SW
P8
K2 K2
fk fk
IP-1 IP
10 –bit key
10
P10
5 5
LS-1 LS-1
5 5
P8
8
K1
LS-1 LS-1
5 5
P8
K2 8
This table is read from left to right; each position in the table gives the identity of the input bit that
produces the output bit in that position. So the first output bit is bit 3 of the input; the second
output bit is bit 5 of the input, and so on. For example, the key (1010000010) is permuted to
(1000001100). Next, perform a circular left shift (LS-1), or rotation, separately on the first five bits
and the second five bits. In our example, the result is (00001 11000).
Next we apply P8, which picks out and permutes 8 of the 10 bits according to the following
rule:
P8
6 3 7 4 8 5 10 9
Encryption
Plaintext: M<n
Ciphertext: C = Me(mod n)
Decryption
Plaintext: C
Ciphertext: M = Cd( mod n)
5 ciphertext 77 Plaintext
Plaintext 19 = 2476099 = 20807 with a 66 = 1.27….x 10140 1.06 …..x10138 with 19
66
119 remainder of 119 = a remainder of
66 19
KU = 5, 119 KR = 77,119
Example 3:
P = 17, q = 31, e = 7, m = 2
N = 17 X 31 = 527
z = (17-1) (31 – 1) = 16 x 30 = 480
e =7
Finding d such that e * d = 1 mod 480
and d < 480 =k*z+i
e=7
the value obtained is 343 1/7 x (480 x k +1)
publickey = { 7, 527} private key = { 343, 527 }
ciphertext = 27 mod 527
= 128 mod 527 = 0
(a) Encryption
(b) Authentication
X
Cryptanalyst
KRb
Source A Destination B
Message X Y X
Encryption Decryption
source Destination
algorithm algorithm
KUb KRb
Key pair
Source
Second level
Domains united Arab JNTU
Emirates
In-addr control
rgm
ugc aict
164
e
ece cse
vax rgm
45
Vax.ugc.control.edu ece.rmg.jntu.in
61
Generic Domain: The generic domain is also called the organization domain, divides registered
hosts according to their generic behaviour. Generic domain names, read left to the right , start
with the most specific information about the host(e.g. the name of the workstation) and become
more and more general with each label until they reach the rightmost label, which describes the
broadcast affiliation of the normal host i.e., the nature of the organization.
Each domain name corresponds to a particular IP address. To find the address, the resolution
application begins searching with the first level. As a much is found, a pointer leads to the next
level and finally to the associated IP address.
Country Domain: The country domain convention follows the same format as generic domain,
but uses two character country abbreviation in place of three character organizational
abbreviations at the first level shown in table. Second level labels can be organizational or they
can be more specific national designations.
Reverse Domain: If we have the IP address and need the domain name, you can reverse
domain the functions of DNS.
The domain can be inserted onto the tree in two ways. For example ugc.control.edu could equally
be listed under the country domain as cs.yale.ct.us.
RESOURCE RECORDS
Every domain in the DNS tree maintains a set of Resource Records, which are connected to it.
For a leaf node i.e., single host, the most common resource record is its IP address. When a
resolver gives a name to DNS, it gets back called as resource records associated with that name.
The original function of a DNS is to map domain names on to the resource records.
A resource record is a five tuple, in ASCII text they are represented as
The domain-name tells the domain to which this record belongs. This is the primary
search key used to satisfy queries.
The time-to live field gives information regarding the stability of the record. A large value
such as 86-400(number of seconds in one day) indicates that the information is highly
stable. The small value such as 60(1 minute) indicates that the information is highly
volatile.
The type of field tells what kind of record it is, some of the type records are listed in table
5.3.
1. The SOA record provides name of the primary source of information about (a) name
servers zone (b) e-mail address of its administration (c) various flags and (d) various time
outs.
2. The record A, holds a 32 bit IP address of the host. If a host connects two or more
networks, each case it has one type of a resource record per network connection.
3. The MX record specifies the name of domain prepared to accept e-mail for the specified
domain. It allows the host that is not on the internet to receive e-mail from internet sites.
4. NS record specifies Name server.
The fourth field in the general structure of resource record is the class. It may be
Internet information, used IN and for non-internet information, other codes are
used.
The value field can be number, domain name or an ASCII string.
NAME SERVERS
The Inter network Information center (Inter NIC) manages the top level domain names. The Inter
NIC delegates responsibility for assigning names to different organizations. Each organization is
responsible for a specific portion of the DNS tree structure. Internet professionals refer to these
areas of responsibilities as zones.
Alternatively, the Inter NIC delegates responsibility for assigning names with in a specific zone to
specific organizations. Each zone contains some part of the tree and also contains name servers
holding the authoritative information about the zone. Each zone contains one primary name
server and one or more secondary name servers. Primary name server and one or more
secondary name servers. Primary name server gets its information from a file on its disk, the
secondary name server and get their information from the primary name server. One or more
servers are located outside the zone, for each zone, for reliability. The number of name servers
needed in a zone depends on the zone boundaries.
Let us consider an example shown in fig connected with another domain. here a resolver on
“ece.rgm.jntu.in” wants to know the IP address of the host “rgm.aicte.control.edu” can be
explained in 8 steps.
Step 1: It sends a query to the local name server rgm.jntu.in.This query asks a record of type A
and the class IN.
Step 2: If the local name server had no such domain and knows nothing about it, it may ask a few
other near by name servers if none of them know, it sends a UDP packet to the server for “edu”
given in its database (see fig) edu.server.net.
Step 3: It forwards the request to the name server control.edu.
Computer Networks S.SANDHYA
RANI
Step 4: And in turn this forwards the request aicte.control.edu, which has authoritative resource
records.
This is the request from client to a server, the resource record requested will work its way
back in step 5 to step 8.Once these records get back to rgm.jntu.in name server, they will be
entered into a cache/memory. However this information is not authoritative, since changes made
at aicte.control.edu will not be propagated to all the memories in the world. For this reason cache
should not live too long, so time-to-live field is used in each resource record. It tells the name
server how long to cache records.
Resource record
ELECTRONIC MAIL
Electronic mail or E-mail as it is popularly called, is a system that allows a person or a group to
electronically communicate with each other through a netork. Presently people can now receive
and send e-mail to:
nearly any country in the world.
one of millions of computer users.
many users at once.
computer programs.
The first e-map systems consisted of file transfer protocols, with the convention that the first line
of each message contained the recipient address. Some of the complaints at that time were
After a decade of competition, email systems based on RFC822 are widely used, where all the
above problems are solved.
BASIC FUNCTIONS
Email systems support five basic functions, which are: Composition, Transfer, Reporting,
Displaying and Disposition.
1. Composition is a process for creating the messages and answers. This can be done by
text editor, outside the mailer, the system will provide assistance in addressing and
numerous header fields attached to each message. For eample:when answering a
message, the e mail system can extract the originator’s address from the incoming e-mail
and automatically insert it into the address space in reply.
2. Transfer refers to moving of messages from the source to the recipent. In some cases,
connection establishment is needed with the destination, outputting the message and
releasing the connection. The e-mail system should do automatically this.
3. Reporting is used to indicate the originator what happened to the message i.e.,
confirmation of the message delivery. Was it delivers successfully? Was it rejected? Was
it lost? Did errors occur?
4. Displaying It refers to read the incoming e-mail by the person. Sometimes conversion is
required or a special viewer must be invoked.
5. Disposition It concerns what the recipient does with the message after receiving it. The
possibilities are
(a) Throwing it away before reading
(b) Throwing it away after reading.
(c) Saving it and so on. It is also possible to forward them or process them in other
ways.
In addition to these basic services, most of e-mail systems provide a large variety of advanced
features such as
(a) It allows to create a mailbox to store incoming e-mail.
(b) It allows to have a mailing list, to which the e-mail messages have to send.
(c) Carbon copies, high priority email, secret email, registered email etc.
Message can be produced with a free standing text editor, a word processing
program or by using a text editor built into the user agents. The format of an e-mail
message is similar to that of a conventional letter.
There are two main parts: Header and body.
The header contains out name and address, the name and address of the person it’s
being sent to, the name and address of the person who is being sent a copy, the date of the
message and the subject when we receive an e-mail from someone, the header tells us where it
came from, what it is about, how it was sent and when.
The body is the place where we write the contents of what we want to communicate. The
message sent should be simple and direct. Body is entirely for human recipient.
The designation address must be in a format that the user agent can deal with. The basic
form of e-mail address is
User name @host name.subdomain.domain.
The text before the sign @(pronounced “at”) specifies the user name of the individual, the text
after the @ sign indicates how the computer system can locate that individual’s mailboxes.
For example
mvs@cs.colorado.edu
Here cs is a sub domain of Colorado is a sub domain of edu.the edu specifies the top-level
domain name.
The number of periods (pronounced as dots) varies from e-mail address.
Reading e-mail: On connecting to the net, the first thing a user usually does is check his mail, it’s
like checking the mailbox when we go home. The display like fig 5.28 appears on the screen.
Computer Networks S.SANDHYA
RANI
Each line refers to one message. In the fig, the mailbox contains 4 (four) messages. The display
line contains several fields, which provides user profile.
This is the solution defined in 1341 and updated in 1521 for the following problems.
1. Messages in languages with accents.
2. Messages in non Latin alphabets.
3. Messages in languages with out alphabets.
4. Messages not containing text at all.
The basic idea of MIME is to continue the use of RFC 822 format, but to add structure to the
message body defined encoding rules for non ASCII formats. The MIME messages can be sent
using the existing mail programs, and protocols.
The MIME defines five new message header
MIME-Version: It tells the use agent receiving the message that it is dealing with a MIME
message, and which version of MIME it uses.
Content-Description: It tells what is there in the message, this header helps the recipient
whether it is worth decoding and reading the message.
Let us now take closer look at how SMTP transfers a message from a sending mail server to a
receiving mail server.
We will see that the SMTP protocol has many similarities with protocols that are used for face-to-
face human interaction.
The client SMTP has TCP to establish a connection on port 25 to server SMTP.If server is
down, the clients tries again later. Once the connection is established, the server and
client perform some application layer handshaking. During this SMTP handshaking phase,
the SMTP client indicates the e-mail address of the sender and the e-mail address of the
recipient. Once the SMTP client and server have introduced themselves to each other, the
client sends the message, SMTP can count on the reliable data transfer service of TCP to
get the message to the server without errors. The client then repeats this process over the
same TCP connection if it has other message to send to the server; otherwise it instructs
TCP to close the connection.
Even though the SMTP protocol is well defined, a few problems can still arise. These are.
1. Related to the Message Length : Some older implementations cannot handle messages
exceeding 64kB.
2. Related to Time Outs : If the client and server have different time-outs, one of them may
give up while the other is still busy, unexpectedly terminating the connection.
3. Infinite mail storms can be triggered .
To get around some of these problems, extended SMTP (ESMTP) has been defined in
RFC1425.
E-mail Gateways: E-mail using SMTP works best when both the sender and receiver on the
internet and can support TCP connections between sender and receiver.However many
* * * * *
* * * * *