Computer Networks: Cheap,

Fast, and Reliable

Communication

1
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Reference Books
• Andrew S. Tanenbaum, “Computer Networks”, 4th Edition, PHI
• Andrew S. Tanenbaum, “Computer Networks”, 3rd Edition, PHI
• W. Stallings, “Data and Computer Communications”, 8th Edition,
PHI
• D. E. Comer, “Internetworking with TCP/IP Vol. 1: Principles,
Protocols, and Architecture”, 5th Edition, PHI
• B. A. Forouzan, “Data Communications and Networking”, 4th
Edition, Tata McGraw-Hill
• James F. Kurose, W. Ross, “Computer Networking: A top-down
approach featuring the Internet”, 3rd Edition, Pearson
• M. Hassan, R. Jain, “High Performance TCP/IP Networking”, PHI
• L. Garcia, I. Widjaja, “Communication Networks”, 2nd Edition,
TMH
2
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Definition
• A collection of autonomous computers
interconnected through communication media
Autonomous
Computer
user user

Communication media
user user

user
• Autonomy: all computers are controlled by themselves
• Media: copper wire, fiber optics etc.

3
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Why Networks
• Resource Sharing
– Software
» Program, Database
– Hardware
» Printer, Disk

• Load Balancing
– Program in an overloaded computer transferred to
and executed by other computer

4
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Why Networks
• High reliability
– Effects of partial failure can be overcome by
another computer

• Location independence.
– Users can access their files from anywhere in the
network.

5
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Applications
• Railway Reservation Systems

• Digital Library

• Electronic Mail System

• Online Newspaper

6
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Before the Internet
• Postal network.
– Delivers different types of objects (letters, packages, etc.)
world-wide.
– Relatively high delay but relatively cheap.
– Sender and receiver identified by their postal address
(name, number, street, city, etc.).
• Telephone network.
– Engineered to deliver real-time voice.
– Also world-wide.
– Low delay but more expensive.
– Users identified but telephone number.

7
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Communication Subnet
• Connecting each pair of computers through
dedicated communication media is expensive

• Individual computers bear the entire burden of

managing communication with each of the
other host

• Separate communication aspect of n/w from

computation aspect of individual computers
8
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Communication Subnet

Subnet

• Subnet consists of large number of communication

links or channels and switching elements or nodes

• Nodes are properly interconnected

9
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Function of nodes
• Interfacing with the hosts

• Some amount of processing on messages

• Switching messages from one link to another

10
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Subnet Topology
1. Point-to-Point subnet (Peer-to-Peer)
2. Broadcast subnet

Star Ring Tree

Fully Connected Partially Connected Bus

11
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Subnet Topology
• Large number of hosts may be located far away
from their nearest IMP

• Terminals, printers also need to be connected in

the n/w
– Do not have adequate speed or functional
capabilities to directly access IMP efficiently

12
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Subnet Topology
• Design the subnet as two level hierarchy
– Backbone: consists of IMPS and high speed links
– Local access part: Concentrator, multiplexer etc.

Concentrator Terminal
Terminal Controller IMP
Host

13
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Classification of networks
• Local Area Network (LAN)
• Small network, covers few kilometers, owned by a
single organization

• Metropolitan Area Network (MAN)

• Medium size network, covers entire city or part of it,
owned by singe or multiple organization

• Wide Area Network (WAN)

• Large network, covers number of countries, owned by
multiple organization
14
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Traditional channel sharing
techniques
»FDM

»TDM

»Polling

»Concentrator

15
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 FDM
• Bandwidth of the channel is much higher than
bandwidth of individual signal

• Partition the channel to create a number of

logical channels

• Dedicate each logical channel to carry

individual signal

• Example: Radio Broadcasting

16
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 FDM
Frequency
B/4 Hz
Single channel of B Hz bandwidth

T0 SCM BPF SCD R0

Summer
T1 SCM BPF SCD R1
∑
T2 SCM BPF SCD R2

T3 SCM BPF SCD R3

Shared channel

17
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 TDM
• Data rate is much higher than individual device
• Create a number of logical channels by time
sharing the single available channel

T1→R1 T2→R2 T3→R3 T4→R4

T sec long slot

4T sec long frame

18
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Polling
• A polling station sends a poll message to each
station
• If the station has data to send, it starts sending
data
• If not, sends poll reject message to controller

Shared line
Controller

19
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Hub Polling
• Stations participate in polling operation
• Controller polls the remote station
• If the station has data to send
• Sends data Star
controller
• If not
• Sends poll message to next station
• Last station sends data or poll message back to
the controller to terminate polling cycle

20
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Concentrator or Statistical TDM
T0
queue
T1
T2

Message
collection
process

Message
Tn-1
transmission
process Shared link
Tn

21
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Concentrator or Statistical TDM
• Advantage over TDM
– High utilization of outgoing link
– Supports more input devices than TDM

• Disadvantage over TDM

– Increased design complexity
– Occasional loss of messages owing to buffer
overrun
– Cost is increased for buffer

22
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Message transport across the subnet

• Circuit Switching

• Message Switching

• Packet Switching

23
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Circuit Switching
• Traditional concept of circuits used in telephone
system

• Three phases
1. Connection establishment
• Connection request signal
• Connection accepted signal
• Path has been chosen (N.B. the chosen path is dedicated for
that conversation)

2. Data transfer
3. Connection release: disconnection signal by any party
24
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Circuit Switching
• No store and forward delay at intermediate
node

• Total delay=circuit setup + transmission time

+ propagation delay

• Example: Telephone system

25
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Message Switching
• No path is established

• Host sends its message to the first IMP

• IMPs store the message, do some processing,

and forward to the next IMP

• Message is transported across the subnet, one

hop at a time
26
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Message Switching
• Disadvantages:
1. No limit on message size
– Each IMP must have enough memory to store
messages
– Needs disk space
– Cost increases

2. A single message may tie up a link for minutes

• Example: Telegram
27
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Packet Switching
• Works similar to message switching
• Places an upper bound on size of each block (called
packet)
• Sender must break the message into several packets if
size of message is larger than upper limit
• Send packets one by one
• Receiver must reassemble packets to generate original
message
• Example: Fax

28
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Packet Switching
• Effect of
packet size

• Large packet
→ large delay

• Smaller packet
→ high overhead

29
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Packet Switching
Event timing

(a) Circuit switching (b) Message switching (c) Packet switching

30
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Packet Switching Vs Message
Switching
IMP
• Advantages of packet switching:

1. Reduces store and forward delay at each IMP

2. No disk space is needed at IMPs, stores packet in

main memory itself

3. Link is not tied up, making it suitable for

interactive traffic

31
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Circuit Switching Vs Packet
Switching
Circuit Switching Packet Switching
Dedicated transmission No dedicated path
path
No store and forward delay Store and forward delay at
each IMP
Each message follow same Different route for different
route packet
Bandwidth wasted Unused bandwidth may be
potentially utilized by other packets
from different sources
32
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Layering
• Building complex systems is hard!
• Approach: “Divide and conquer”
• Split job into smaller jobs, or layers
• Analogy to other fields.
• Building a house: digging, foundation, framing, etc.
• Car assembly line…
• Basic idea: each step dependent on the previous
step but does not need to be aware of how the
previous step was done.

33
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Analogy: Air Travel
• Decomposed into series of steps:

Arrival at airport Departure from airport

Check-in Baggage claim

Boarding Deplane

Takeoff Landing

Traveling

34
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Layered Architecture
• Layering model is a solution to the problem of
complexity in communication networks
• Each layer solves part of the communication
problem
• Each layer is implemented independently
• Each layer provides a service to the layer above
– Relying on services provided by the layers below

35
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Layered Architecture
• Protocol: A set of rules and
conventions governing the
communication between two or more
entities

• Interface: Defines a set of primitive

operations through which each layer
provides services to its immediate
layer

• Peer process: Entities in a particular

layer on different machine
36
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Layered Architecture

37
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 The ISO OSI Model
• ISO: International Application
Provides access to the OSI environment for users
Standards Presentation
Organization Provides Independence from data representation
Session
Establish, manage, terminate connection

• OSI: Open Systems Transport

Connection oriented service
Interconnection
Network
Routing, congestion control, connection oriented or
connectionless
Data Link
Framing, Synchronization, error control, flow control

Physical
Transmission of raw bit stream over physical medium

38
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 TCP/IP Reference Model
• TCP/IP: Transmission Control Protocol/Internet Protocol

39
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Comparison of OSI and TCP/IP
Model
OSI TCP/IP
Stack of independent protocols Stack of independent protocols

Layers above transport (inclusive) Layers above transport (inclusive)

provides an end-to-end network provides an end-to-end network
independent service independent service

Seven layers Four layers

Network layer may be connection- Network layer is connectionless

oriented or connectionless

Transport layer is connection- Transport layer may be connection-

oriented oriented or connectionless
40
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Data Link Layer

41
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Functions
» Framing
» Error detection and correction
» Error control
» Flow control

• Services provides to the network layer

– Unacknowledged connectionless service
– Acknowledged connectionless service
– Acknowledged connection-oriented service
42
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Framing
• The process of encapsulating frames with special bit
pattern, character pattern, encoding to let the receiver
identify start and end of the frame

43
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Character count

(a) Without errors (b) With one error

44
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Character stuffing

(a) A frame delimited by flag bytes (b) Four examples of byte

sequences before and after stuffing.
45
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Bit stuffing

• Bit stuffing (a) The original data (b) The data as they appear on
the line (c) The data as they are stored in receiver’s memory after
destuffing.
46
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Cyclic Redundancy Check (CRC)
• Bit strings are represented as polynomial with
coefficient 0 and 1 only
• 100101
• 1.x5+0.x4+0.x3+1.x2+0.x1+1.x0
• X5+x2+x
• Use of modulo-2 arithmetic
• Generator polynomial: Predetermined divisor
• Calculate CRC and append it to the end of the frame
• Resulting polynomial is divisible by Generator
polynomial

47
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Cyclic Redundancy Check (CRC)
• Algorithm:
1. Let r be the degree of G(x). Append r zero to
low-order-end of the frame (xrM(x)), so it
contains r+m bits
2. Divide xrM(x) by G(x) using modulo-2
arithmetic
3. Subtract the reminder from xrM(x) using
modulo-2 subtraction
4. Result is the checksumed frame to be
transmitted (T(x))
48
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Cyclic Redundancy Check (CRC)
• Example (Sender):
– M(x)=110011 (x5+x4+ x+1)
– G(x)=11001 (x4+ x3+1)
– Frame after 4 zero bits appended: 1100110000
100001
11001 1100110000
11001
10000
11001
1001
So, frame to be transmitted is 1100111001
49
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Cyclic Redundancy Check (CRC)
• Example (Receiver):
100001
11001 1100111001
11001
11001
11001
00000
So, no error.
50
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Power of CRC
• Let the receiver receives T(x)+E(x)
• E(x)=error bit string
• Each 1 bit in E(x) indicates a bit that has been inverted

• Receiver performs (T(x)+E(x))/G(x)

• Gets E(x)/G(x)

• If E(x)/G(x)=0
– Error not detected
– Otherwise error will be detected
51
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Power of CRC
• Let E(x)=xi, i indicates the position of the bit
which is in error
– i.e. single bit error

• If G(x) contains two or more terms then

E(x)/G(x)≠0
– i.e. all single bit errors will be detected

52
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Power of CRC
• Let there are two isolated single bit errors
– i,.e. E(x)=xi+xj, i>j
=xj(xi-j+1)
– Assume that xj is not divisible by G(x)
– Sufficient condition for all double bit errors to be
detected => G(x) does not divide (xi-j+1)

53
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Power of CRC
• Now consider E(x) contains odd number of
error bits
– E(x) contains odd number of terms (x6+x2+1)
– No polynomial with odd number of terms has
(x+1) as a factor
– So, to detect odd number of errors G(x) must have
a factor (x+1)

54
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Error Control
• Automatic Repeat Request (ARQ):
– Detect errors at the receiving DLC layer and
request the transmitting DLC layer to retransmit
the erroneous frame
• Purpose is to turn an unreliable link into an effective
one
• ARQ has four ingredients
– Error detection
– Acknowledgement (ACK)
– Negative Acknowledgement (NACK)
– Timeout

55
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Stop and Wait ARQ
• Transmitter transmits one frame at a time
• Wait for ACK/NACK from receiver
• If ACK, transmit next frame
• If NACK, retransmit the frame
• If no ACK/NACK within timeout period
– Retransmit the frame

56
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Go-Back-N ARQ
• Frames move continuously
• Transmitter maintains buffer storage
• If receiver detects error, it sends an NACK
containing defective frame number N, discards
subsequent frames
• Transmitter goes back to frame N and
retransmits all frames starting from N
• Suitable when error rate is high

57
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Selective Repeat ARQ
• Frames move continuously
• Transmitter maintains buffer storage
• If receiver detects an error, it sends an NACK
containing defective frame number
• All subsequent frames are buffered by the
receiver
• Transmitter transmits only the defective frame
• Suitable when error rate is low

58
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Examples

(a) Go-Back-n (b) Selective Repeat

59
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Flow Control
• Sliding window protocol
– Receiver has limited buffer space
– Number of frames the transmitter is allowed to
transmit must be decided
– Window size: upper bound on the number of
frames than can be transmitted by the transmitter
– To avoid frame loss due to buffer overflow
• Number of outstanding frames <= window size

60
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Sliding Window Protocol

A sliding window of size 1, with a 3-bit sequence number.

(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
61
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Sliding Window with Go-Back-N
• For sender 0≤w1≤2n-1, for receiver w2=1
• Sender buffer size ≥w1, receiver buffer size=1

Frames 0-3 are sent, closed Open to receive frame 0

ACK0 sent, Open

ACK0 received, partially open
to receive frame 1

NACK1 is sent
Frames 4 sent, closed

Reopen to retransmit Frames 1-4 Open to receive frame 1

62
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Sliding Window with Selective Repeat
• For sender 0≤w1≤2n-1, for receiver 1≤w2≤2n-1
• Sender buffer size ≥w1, receiver buffer size ≥ w2

Frames 0-3 are sent, closed Open to receive frames

0-3

ACK0 sent, Open

ACK0 received, partially open
to receive frame 1-4

NACK1 is sent
Frames 4 sent, closed

Partially open to retransmit Frame 1 Open to receive frame 1

63
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Performance Analysis
• Efficiency is measured by link throughput
• Factor effecting efficiency of a protocol
– Data transmission rate
– Frame size
– Frame overhead
– Link error rate
– Retransmission strategy
– Propagation delay

64
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Notations
• C: channel capacity
• D: number of data bits per frame
• H: number of header bits per frame
• F: total number of bits per frame=D+H
• A: number of bits in ACK/NACK
• I: propagation delay in seconds
• E: probability of a bit error
• P1: Probability that a data frame is lost or
damaged
65
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Notations
• P2: probability that an ACK frame is lost or
damaged
• L: probability that a frame or its ACK is lost or
damaged
• R: average number of retransmissions per data
frame
• T: timeout interval in seconds
• W: window size
• U: channel utilization
66
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Stop and Wait ARQ
• Case 1 (Ideal Channel)
• Time required to transmit a frame=F/C Seconds
• Time required to transmit an ACK=A/C Seconds

• Total elapsed time between start of transmission of a

frame and start of transmission of next frame
• C: channel capacity
t=(F/C)+I+(A/C)+I seconds • D: number of data bits per frame
• H: number of header bits per frame
• F: total number of bits per frame=D+H
=[(F/C)+(A/C)+2I] seconds • A: number of bits in ACK/NACK
• I: propagation delay in seconds
• E: probability of a bit error
• P1: Probability that a data frame is lost or damaged
• P2: probability that an ACK frame is lost or damaged
• L: probability that a frame or its ACK is lost or damaged
• R: average number of retransmissions per data frame
• T: timeout interval in seconds
• W: window size
• U: channel utilization

67
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Stop and Wait ARQ • C: channel capacity
• D: number of data bits per frame

• Case 1 (Ideal Channel)

• H: number of header bits per frame
• F: total number of bits per frame=D+H
• A: number of bits in ACK/NACK
• I: propagation delay in seconds

• Number of data bits that could be transmitted in

t seconds= C*t bits • E: probability of a bit error
• P1: Probability that a data frame is lost or damaged
• P2: probability that an ACK frame is lost or damaged
• L: probability that a frame or its ACK is lost or damaged
= (F+A+2CI) bits • R: average number of retransmissions per data frame
• T: timeout interval in seconds
• W: window size
• U: channel utilization

• So, Channel Utilization U=(D/(F+A+2CI))

=(D/(D+H+A+2CI))
=(D/(D+O))
where O=H+A+2CI is the overhead
68
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Stop and Wait ARQ
• Case 2 (Error prone channel):
• Unsuccessful transmission uses (F+CT) bits of
channel capacity
• So, total channel capacity used for one effective
transmission B=R(F+CT)+(F+A+2CI) bits
• Probability of failure L=1-(1-P1)(1-P2)
• Probability that exactly K attempts are
necessary for successful frame transmission
X=(1-L)LK-1
69
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Stop and Wait ARQ
• C: channel capacity

• Case 2 (Error prone channel):

• D: number of data bits per frame
• H: number of header bits per frame
• F: total number of bits per frame=D+H
• A: number of bits in ACK/NACK
• Expectation of X=1/(1-L) • I: propagation delay in seconds
• E: probability of a bit error
• P1: Probability that a data frame is lost or damaged
• P2: probability that an ACK frame is lost or damaged
• L: probability that a frame or its ACK is lost or damaged
• R: average number of retransmissions per data frame

• So, expected number of retransmission per frame

R=1/(1-L)-1=L/(1-L) • T: timeout interval in seconds
• W: window size

• U: channel utilization

• Now B=(L/(1-L))(F+CT)+(F+A+2CI)

• Utilization U=D/B
=D(1-L)/(LCT+F+(1-L)(A+2CI))
70
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Stop and Wait ARQ
• Case 2 (Error prone channel): • C: channel capacity
• D: number of data bits per frame
• H: number of header bits per frame

• Let T=2I+A/C then CT=A+2CI

• F: total number of bits per frame=D+H
• A: number of bits in ACK/NACK
• I: propagation delay in seconds
• E: probability of a bit error
• P1: Probability that a data frame is lost or
damaged
• P2: probability that an ACK frame is lost or
damaged

• U=D(1-L)/(F+CT)
• L: probability that a frame or its ACK is lost or
damaged
• R: average number of retransmissions per data
frame
• T: timeout interval in seconds
=D(1-L)/(F(1+CT/F)) • W: window size
• U: channel utilization

=[D/D+H]*[(1-P1)(1-P2)]*[(1/(1+CT/F))]
=U1*U2*U3

71
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Sliding Window Protocol
• Step I (Error-free channel)
• Case 1 <large window>:
– One or more ACKs will come back before window
is totally filled up
– First ACK received after t=F/C+2I Sec
– Number of frames that could be transmitted in t
seconds=1+2CI/F
– To ensure uninterrupted transmission
W>(1+2CI/F)
– So, U=D/(D+H), ignoring ACK
72
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Sliding Window Protocol
• Case 2 <small window>
– W<(1+2CI/F)
– Sender receives first ACK after (F/C+2I) seconds
– Number of data bits transmitted=W*D
– So, U=(W*D)/(F+2CI)

73
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Sliding Window Protocol
• Step II (error prone channel)
• Case 1 <selective repeat>
– Expected number of transmission per frame=1/(1-L)

– For sliding window protocol=W/(1-L)

– So, U=[D/(D+H)]*(1-L), large window

=[(W*D)]/[(F+2CI)]*[(1-L)], small window

74
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Sliding Window Protocol
• Case 2 <Go-back-n>: 
– Expectation of X = (1 − L ) f (i )Li −1
i =1
– Where f(i)=total number of frames transmitted if the
original frame must be transmitted i times
– f(i)=1+(i-1)*N=(1-N)+N*i
– So, expectation of X=(1-L+NL)/(1-L)
– For large window N=1+2CI/F
– For small window N=W
– U=[D*(1-L)]/[(D+H)*(1-L+NL)], large window
=[(W*D)*(1-L)]/[(F+2CI)*(1-L+NL)], small window

75
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 High-Level Data Link Control
Protocol (HDLC)
• Uses bit stuffing for synchronization

• Uses sliding window with Go-back-N or

selective repeat

• Defines three types of stations

– Primary station
– Secondary station
– Combined station
76
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 High-Level Data Link Control
Protocol (HDLC)
• Defines two link configuration
– Unbalanced configuration
– Balanced configuration

• Defines two data transfer modes

– Normal Response Mode (NRM)
– Asynchronous Balanced Mode (ABM)

77
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 High-Level Data Link Control
Protocol (HDLC)

• Three types of frame

– Information frame
– Supervisory frame
– Unnumbered frame

78
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 High-Level Data Link Control
Protocol (HDLC)

(a) Information frame (b) Supervisory frame (c) Unnumbered frame

79
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Point-to-Point Protocol (PPP)
• PPP provides following services:
– Framing method
– Frame format handles error detection
– Link Control Protocol (LCP)
– Bringing lines up, testing them, negotiating options, bringing
them down
– Authentication
– Defines how two devices authenticate each other
– Network Control Protocol (NCP)
– Negotiating network layer options

80
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Point-to-Point Protocol (PPP)
• Several things are missing:
– No flow control

– No error control
– Only detects error

– No sequence numbering

– No sophisticated addressing mechanism for

multipoint configuration
81
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Point-to-Point Protocol (PPP)

Frame
format

82
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Point-to-Point Protocol (PPP)

Transition phases
83
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Point-to-Point Protocol (PPP)
• Authentication protocol:
– Password Authentication Protocol (PAP)
• User sends user name and password
• System checks for validity of user name and password, accept/deny
– Challenge Handshake Authentication Protocol
(CHAP)
• Greater security than PAP
• System sends a challenge to the user
• User applies predefined function on challenge and password, sends
the result to the system
• System does the same
– If result matches, accept otherwise deny

84
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Local Area Network

85
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 LAN overview
• Small networks, covers few kilometers

• Owned by single organization

• Shared medium

• Low propagation delay

• Low error rate

86
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 LAN overview
• Typically used to connect computers in office
or factory to share resources and exchange
information

• Traditional LANs operate at 10Mbps-100Mbps

• Newer LANs operate at up to 10Gbps

87
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Topology

Star Tree

Ring Bus

88
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Protocol Architecture
• Lower layers of OSI model

• IEEE 802 reference model

• Physical

• Media Access Control (MAC)

• Logical Link Control (LLC)

89
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 IEEE 802 vs OSI

90
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 LAN Protocols in Context

91
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 The Channel Allocation Problem
• Static channel allocation
– No interference between users
– Efficient for small, fixed number of users
– Poses problem for large and continuously varying
number of senders

• Solution: Dynamic channel allocation

92
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Dynamic Channel Allocation
• Five key assumptions
– Station model
– Single channel assumption
– Collision assumption
– Timing assumption
– Continuous time
– Slotted time
– Channel status testing
– Carrier sensing
– No carrier sensing

93
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Pure ALOHA

• Frames are transmitted at arbitrary time, Collisions possible

• Collisions are detected due to feedback property

• Wait random amount of time before retrying

94
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Pure ALOHA

Vulnerable period for the shaded frame

95
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Pure ALOHA
• Let G=offered load per frame time (mean)
• Probability that k frames are generated in a frame time
k −G
is Pk  = e
G
k!

• So, P0 = e−G

• Mean number of frames generated in the vulnerable
period=2G
• So, P0 = e −2G (in collision zone)
• Throughput S = GP[0] = Ge−2G
• Smax=1/2e, when G=0.5
96
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Slotted ALOHA
• Divide time into discrete intervals

• Each interval corresponds to one frame time

• Collision zone is now halved

collision

• So, S = GP[0] = Ge − G sender A

sender B
sender C
• Smax=1/e, when G=1.0 t

• throughput is double than Pure ALOHA

97
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Throughput vs Offered Load

98
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Carrier Sense Multiple Access
Protocol (CSMA)
• First listen for clear medium (Carrier Sensing)
• If medium is idle
– Transmit frame
– else wait
• Two stations start at the same time
– Collision
– Wait random amount of time
• Maximum utilization depends on propagation
time
– Shorter propagation gives better utilization
99
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Non-Persistent CSMA
• If medium is idle, transmit

• If not, wait random amount of time

– Random delays reduces probability of collision
– Capacity is wasted
• Medium remains idle following end of transmission

• If collision, wait random amount of time

100
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 1-Persistent CSMA
• Stations wishing transmit listens and obeys
following rules:
1. if medium is idle, transmit;

2. If medium busy, listen until it becomes idle; then

transmit immediately
– If two or more stations waiting, collision guaranteed
– Gets sorted out waiting random time after collision

101
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 p-Persistent CSMA
• Reduces collision like non-persistent and
reduce idle time like 1-persistent

• Rules
1. If medium is idle, transmit with probability p,
and defer until next slot with probability 1-p
2. If medium is busy, continue listening
3. If collision, wait random amount of time.

102
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Throughput vs offered load

103
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 CSMA/CD
• With CSMA, collision occupies medium for
duration of transmission

• Stations listen while transmitting

1. If medium is idle, transmit
2. If busy, listen for idle, then transmit
3. If collision, stop transmission immediately
4. Backoff

104
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 CSMA/CD

CSMA/CD Operation
105
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 CSMA/CD

• A station must continue transmission after 2τ time

where τ is the propagation time

106
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Reservation Protocols
• Reservation can increase efficiency to 80%
– a sender reserves a future time-slot
– sending within this reserved time-slot is possible without
collision
– reservation also causes higher delays
– typical scheme for satellite links

• Examples for reservation algorithms:

– Reservation-ALOHA
– Reservation-TDMA

107
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Reservation ALOHA
• two modes:
– ALOHA mode for reservation:
competition for small reservation slots, collisions possible
– reserved mode for data transmission within successful
reserved slots (no collisions possible)

collision

t
Aloha reserved Aloha reserved Aloha reserved Aloha

108
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Reservation TDMA
• Reservation Time Division Multiple Access
– every frame consists of N mini-slots and x data-slots
– every station has its own mini-slot and can reserve up to k
data-slots using this mini-slot (i.e. x = N * k).
– other stations can send data in unused data-slots according
to a round-robin sending scheme (best-effort traffic)
e.g. N=6, k=2
N mini-slots N * k data-slots

reservations other stations can use free data-slots

for data-slots based on a round-robin scheme
109
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Ethernet: IEEE 802.3

110
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Signal Encoding

111
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Ethernet MAC Sublayer Protocol

Frame formats. (a) DIX Ethernet, (b) IEEE 802.3

112
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Ethernet MAC Sublayer Protocol

Collision detection can take as long as 2 .

113
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Binary Exponential Backoff
• After first collision, each station waits 0 or 1
time slots
• After second collision, each station waits 0, 1,
2, or 3 time slots
• After third collision, each station picks random
numbers from 0 to 23-1
• After ith collision, each station picks random
number from 0 to 2i-1

114
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Ethernet Performance
• K stations ready to transmit
• Mean frame time = T
• Prob. of transmission during a contention slot=p
• Prob. that some station acquire the channel in
that slot A = Kp(1 − p )k −1

• Prob. That the contention interval has exactly j

slots = A(1 − A)
j −1

115
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Ethernet Performance


• Mean number of slots per contention=  jA(1 − A)

j −1

j =0

• Contention slot=2τ, mean contention interval=2τ/A

T
• Efficiency= 2
T+
A

1
=
2 BLe
1+
cF

116
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Ethernet Performance

117
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Token Ring: IEEE 802.5

118
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Token Ring Architecture
• A ring consists of a number of Ring Interface
Units (RIU)
• Stations are connected to RIU Station

• Links are unidirectional

• point-to-point subnet Unidirectional
Ring

• 1 bit delay at each RIU RIU

• Walk time=prop. Delay + 1 bit delay by each

RIU
119
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Token Ring Architecture
• Link failure → a serious problem
• Solution: Star Ring Architecture

Wiring Centre Backup Ring

Wiring Centre

Wiring Centre
Forward Ring

120
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Token Ring MAC Protocol
• Small frame (token) circulates when idle

• Stations wait for token

• If a station seizes the token

– Transmit data frames
– Frames are absorbed by transmitting station
– Transmitting station inserts new token

121
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Token Ring MAC Protocol
• Shielded twisted pair – DM encoding

• Maximum token holding time = 10 msec

122
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Token Ring Operation

123
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Frame Format
1 1 1
SD AC ED
Token Format

1 1 1 2 or 6 2 or 6 No limit 4 1 1
SD AC FC Destination Source Data Checksum ED FS
address address
Frame Format

PPPTMRRR F F rr Control A C r r ACrr

AC FC FS

124
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Listen State
• Scan passing bit stream for patterns
– Address of attached station
– Token permission to transmit

• Copy incoming bits and send to attached station

• Modify bits as it passes

– e.g. ACK

125
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Transmit State
• Station has data

• RIU has permission

• Transmit data

• May receive incoming bits

• Transmit token
126
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Bypass State
• Signal propagate past repeater with no delay
(other than prop. delay)

• Solution to reliability problem

• Improved performance

127
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Token Ring Management
• One station is designated as Active Monitor
(AM), others as Standby Monitor (SM)

• Functions of AM:
– Ring Initialization: PURGE MAC frame
– Lost Token: Timer
– Orphan removal: set M bit in AC byte

128
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 AM recovery
• AM sends AMP frame periodically

• SM has two timers -- AMP/Token

• If timer expires
– SM sends CLAIM TOKEN FRAME

• Contention resolved by station address

129
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 BEACONING
• Used to isolate faulty station/ring

• Stations send BEACON frame giving

predecessor’s address

• Predecessor isolates & check itself

• If OK, switches to backup ring

• If not, bypass relay bypasses the station

130
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Priority Management Scheme
• Real time data → high priority

• Priority schemes : PT, PD, PTR

• Stations with PD≥PT (PPP=PT) seizes the token

• Sends data frame (PPP=PD)

• Regenerates token (PTPTR)

• Stations may makes reservation (RRRPD)

131
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Neighbor Notification
• AM sends AMP frame : A=0, C=0

• 1st station notes address (M) – sets A=1, C=1

• 1st station sends SMP frame : A=0, C=0

• 2nd station notes address (1) – sets A=1, C=1

• Finally AM notes address (N-1)

132
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Token Bus: IEEE 802.4

133
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Token Bus Evolution
• Problem with Ethernet
– Probabilistic MAC protocol
– Worst case is unbounded
– No priority Schemes
– Important frames are held up for unimportant frames

• Problem with Ring

– Physical implementation
– Break in the cable !!

• Solution
– Combine robustness of Ethernet and worst case behavior
of ring
– Token Bus
134
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Token Bus Architecture
• Stations are physically connected to a linear cable but
Logically form a ring

• Each station knows address of left and right station

17 20
14

13 11 7 19

135
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Token Bus MAC Sublayer
Protocol
• Stations are added to the logical ring in order of
addresses
• To transmit a station must have the token
• Transmit for token holding time
• Pass the token to successor explicitly
• Defines four priority classes 0, 2, 4 and 6
– Each type of traffic sent for a predefined duration
– Lower priority frames can have the unused portion
of high priority traffic
136
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Frame Format

1 1 1 6 6 0-8174 4 1
Preamble Start Frame Destination Source Data Checksum End
Delimiter Control Address Address Delimiter

137
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Logical Ring Maintenance
• Joining the ring
• Token holder sends SOLICIT_SUCCESSOR frame
• The frame contains sender and its successors address
• New station bids to enter within slot time (2τ)
• If more than one station bits ----collision
– Resolved using RESOLVE_CONTENTION

• Leaving the ring

• Y has predecessor X and Successor Z
• Y sends SET_SUCCESSOR frame to X
• Z becomes successor of X

138
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Logical Ring Maintenance
• Ring initialization
• First station comes on-line
• There is no traffic for certain duration
• It sends CLAIM_TOKEN frame
• If no competitor, it creates a token and sets up the ring
containing itself

• Detecting and Removing faulty station

• After passing the token if its successor does not sends frame or
token, token is sent for second time
• If it fails again---successor is down
• Send WHO_FOLLOWS frame giving successor address
• Failed stations successor replies with SET_SUCCESSOR frame
139
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Local Internetworking

140
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Internetworking Devices

(a) Which device is in which layer (b) Frames, packets, and headers.

141
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Internetworking Devices

(a) A hub (b) A bridge (c) a switch

142
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Bridges
• Different department has different needs
– Different types of LANs
– There is a need for interaction!!!

• Departments may be geographically spread over several

buildings
• Separate LANs to accommodate load
• Physical distance between two stations is large
• Question of reliability
– Defective node sends garbage continuously
– Insert bridges at critical places; just like fire-doors

• Organization’s security
– LAN interfaces have a promiscuous mode
143
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Bridges

Multiple LANs connected by a backbone to handle a total load

higher than the capacity of a single LAN
144
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Bridges

Operation of a LAN bridge from 802.11 to 802.3

145
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Bridges
• Frame formats are different

• LANs do not run at same speed

– Timers in the higher layers

• Different maximum frame length

146
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Transparent Bridges
• Operates in promiscuous mode
• Forwarding decision is made with the help of a table
• Uses backward learning algorithm
– Look at the source address to decide which machine is on
which LAN

A configuration with four LANs and two bridges

147
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Transparent Bridges
• Routing procedure
– If destination and source LANs are the same,
discard the frame
– If the destination and source LANs are different,
forward the frame
– If the destination LAN is unknown, use flooding

148
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Transparent Bridges

Two parallel transparent bridges.

149
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Spanning Tree Bridges
• Remove loops in the graph

(a) Interconnected LANs (b) A spanning tree covering the LANs

150
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Source Routing Bridge
• High order bit of source address = 1
• Frame header includes exact path
• Route is discovered using Discovery frame
Frame Explosion Problem

1 2

151
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
IMPComparison of 802 Bridges
Issue Transparent Bridge Source Routing Bridge

Orientation Connectionless Connection-oriented

Transparency Fully transparent Not transparent

Configuration Automatic Manual

Locating Backward Learning Discovery Frames

Failure Handled by bridges Handled by hosts

152
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Virtual LANs

• Issues for VLANs are

– Security
– Traffic load
– broadcasting

153
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Virtual LANs

(a) Four physical LANs organized into two VLANs, gray and white, by
two bridges. (b) The same 15 machines organized into two VLANs by
switches
154
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Network Layer

155
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Design Issues

The environment of the network layer protocols

156
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Design Issues
• Following goals must be satisfied while
designing network layer services:
– Independent of the subnet technology

– Transport layer must be shielded from the number,

type and topology of the subnets present

– Network addresses should use a uniform numbering

plan

157
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Design Issues
• Subnets can be organized as
– Datagram Subnet
• Connectionless, packets are called datagrams
• Each packet contains full source and destination
address
– Virtual Circuit subnet
• Connection-oriented
• Virtual circuits are numbered, routers must
remember virtual circuits passing through it
• Each packet must contain virtual circuit number

158
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Design Issues

Routing within a diagram subnet

159
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Design Issues

Routing within a virtual-circuit subnet

160
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Design Issues

161
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Routing

162
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Routing Algorithms
• Properties:
1. Correctness 2. Simplicity 3. Robustness
4. Stability 5. Fairness 6. Optimality

• Types:
– Static or Non-Adaptive Algorithm
– Routes are computed in advance, offline
– Fails when topology changes frequently
– Dynamic or Adaptive Algorithm
– Reflects frequent changes in topology

163
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Shortest Path Routing
• Simple algorithm
• Basic idea:
• Build a graph of the subnet
– Node represents a router, arc represents a communication link
• Find the shortest path between nodes
– Dijkstra’s algorithm
– Metric: hops, delay

164
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Flooding
• Incoming packets retransmitted on every link
except incoming link
• Eventually a number of copies will arrive at
destination
– Each packet is uniquely marked, so duplicates can
be discarded
– Include a hop count in packets

165
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Flooding

166
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Distance Vector Routing
• Routing tables are updated by exchanging routing tables and re-computing
shortest path

(a) A subnet (b) Input from A, I, H, K, and the new routing table for J
167
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Distance Vector Routing
• The algorithm suffers from Count-to-Infinity problem

168
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Link State Routing
• Each router must do the following:
1. Discover its neighbors, learn their network
address
2. Measure the delay or cost to each of its
neighbors
3. Construct a packet telling all it has just learned
4. Send this packet to all other routers
5. Compute the shortest path to every other router

169
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Hierarchical Routing
• With growing size of networks routing table grows
proportionately
• Memory consumption becomes high
• More CPU time needed to scan the table
• More bandwidth required to exchange routing tables

• Solution:
– Divide routers into region
– Routers know the topology of its own region but knows nothing about
topology of the other regions
– For large networks divide regions into clusters, clusters
into zones, zones into groups……..
170
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Hierarchical Routing

171
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Broadcast Routing

Reverse path forwarding: (a) A subnet (b) a Sink tree (c) The
tree built by reverse path forwarding
172
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Multicast Routing

(a) A network (b) A spanning tree for the leftmost router (c) A multicast tree for
group 1 (d) A multicast tree for group 2
173
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Congestion Control

174
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Definition
• Too many packets in the subnet than its carrying
capacity results in congestion

175
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Factors Affecting Congestion
• Insufficient memory
– Even infinite memory makes thing worse

• Slow processor
– Queue build up

• Low bandwidth

• Congestion tends to feed upon itself

176
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 General Principles of Congestion
Control
• Two approaches
– Open loop
• Make sure congestion does not occur
– Closed loop
• Monitor the system
– detect when and where congestion occurs.
• Pass information to where action can be taken.
– Send a packet to the source
– Load increased
• Adjust system operation to correct the problem.

177
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Congestion Prevention Policies

178
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Congestion Control in Virtual Circuit
Subnet
• Admission control
• Allow new circuits avoiding problem area

• Negotiate an agreement
– Reserve resources

179
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 The Warning Bit
• Each router monitor utilization of outgoing line
• unew = a*uold + (1-a)*f
• If u > threshold
– The output line enters Warning state
– Each newly arrived packets are then marked
– Turn on one bit in header
– Receiver copies this information into ACK
– Sender cuts down transmission rate

180
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Choke Packets
• Tell the sender directly about congestion
• Congested router sends back choke packet
– Sender cuts down transmission rate for certain
interval
– If more choke packet received, rate is reduced
further
– If not, sender may increase the rate

181
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Hop-by-Hop Choke Packet

(a) A choke packet that affects only

the source
(b) A choke packet that affects each
hop it passes through
182
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Load Shedding
• Congested router drops packet at random
• It can do better
– Which packet to discard?
– Depends on the application
– FTP Vs Multimedia traffic
– Implement intelligent discard policy
– Sources are required to mark packets with priority
– Low priority packets are discarded when congestion occur

183
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Random Early Detection (RED)
• Take action before it is too late
• Each router maintain a running average of
queue length
• If average queue length hits threshold it starts
discarding packets randomly
– Works better when source assumes congestion for
lost packets – reduce transmission rate
– Not appropriate in wireless network

184
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Jitter Control
• Audio and video streaming require constant
transit time
• Variation in packet arrival time is called jitter
• Compute the expected transit time for each hop
• Routers check to see how much the packet is
behind or ahead of schedule
– If the packet is ahead of schedule, it is held up
– If the packet is behind of schedule, forward
immediately
185
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Quality of Service (QoS)

186
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Requirements

187
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Buffering
• To smooth out jitter, buffer packets at destination
• Increases delay

• Delay start of play as much as you can

– Commercial sites buffer for 10 sec
188
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Traffic Shaping
• Irregular output from server may cause
congestion
• Buffering is not possible for some application,
e.g. video conferencing
• To achieve good QoS use traffic shaping
– Regulate the average transmission rate
– Compare it with sliding window protocol
– Reduces congestion

189
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 The Leaky Bucket Algorithm
• Host can produce data at
rate 25MB/s
• Routers can work best
for rate 2MB/s
• Data comes in 1MB burst
• Use a leaky bucket with
ρ=2MB/s and capacity
C=1MB

(a) A leaky bucket with water

(b) A leaky bucket with packets
190
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 The Leaky Bucket Algorithm

(a) Input to a leaky bucket

(b) Output from a leaky bucket
Output from a token
bucket with capacities of
(c) 250 KB
(d) 500 KB
(e) 750 KB
(f) Output from a 500KB
token bucket feeding a 10-
MB/sec leaky bucket

191
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 The Token Bucket Algorithm
• Allows output to speedup when
needed
• Leaky bucket holds token, one
token generated every ΔT sec
• Allows saving up to maximum
bucket size n

• Token bucket capacity =C bytes

• Burst length = S sec
• Token arrival rate = ρ bytes/sec
• Max. output rate = M bytes/sec
• Then we have
C+ ρS=MS

(a) Before (b) After

192
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Packet Scheduling
• Router handles multiple flows
– One flow will hog too much of its capacity

• Processing packets in order of arrival

– Aggressive sender capture most of its capacity

• Use fair queuing algorithm

– Routers have multiple queues for each output line, one for
each flow
– Scan the queues in round robin fashion

193
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Packet Scheduling
• Fair queuing gives more bandwidth to hosts
with large packets
• Use byte-by-byte round robin

194
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Resource reSerVation Protocol
(RSVP)
• Allows multiple senders to send to multiple receiver
• Uses multicast routing using spanning tree

195
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Resource reSerVation Protocol
(RSVP)
• For better reception receivers send reservation message to the sender
• Message is forwarded using reverse path forwarding
• Packets can flow without congestion

196
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Internetworking

197
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Why internetworking
• Can we use a single network all over the world?
• Many different network exists
– TCP/IP, SNA, Satellite, Cellular
– Different protocols are in use
• Installation base of different networks is large and
growing
• Vendors do not want their customer to switch to
another vendors system
• Hardware development forces new software to be
created
– Computer, Telephone, Television may be interconnected
– You need different protocol

198
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 How networks differ

199
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Connecting networks

(a) Two Ethernets connected by a switch (b) Two Ethernets connected by routers

200
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Tunneling
• Encapsulating a packet inside another packet is
called tunneling

201
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Fragmentation
• Break packets into smaller fragments
– Each fragment is treated as a separate packet
• Reasons for fragmentation
• Hardware
• Operating system
• Protocols
• Desire to reduce error rate
• Prevent a packet from occupying channel too long

202
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Fragmentation
• Two strategies:
– Transparent fragmentation
• Subsequent networks are not
aware of fragmentation
• All packets must exit through same
gateway where they are
reassembled
• Overhead due to repeated
fragmentation and reassembly
– Non-transparent fragmentation
• Reassembly takes place only at the
receiver
• Overhead due to header for every
packet
• Overhead remains for rest of the
journey
• Multiple exit gateways can be used
203
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Fragmentation
• Fragments must be number carefully so that original packet can
be reconstructed
– Each fragment must contain original packet number, offset
within the original packet, end-of-packet marker

(a) Original packet, containing 10 data bytes (b) Fragments after passing through a
network with maximum packet size of 8 bytes (c) Fragments after passing through
a size 5 gateway
204
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
The Internet Protocol Version 4 (IPv4)

205
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 IPv4 Header

206
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 IP Options

207
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 IP Addresses
• IPv4 addresses are 32 bits long
– Unique and universal
– Contains two parts: network ID and Host ID

• Addresses are written in dotted decimal

notation
• Each byte is converted into decimal separated by dots
• Example:
– Address in binary: 10000000 00001011 00000011 00011111
– Address in Dotted decimal notation: [Link]

• Address space is divided into five classes

• class A, class B, class C, class D, and class E
208
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 IP Addresses

IP address formats
209
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 IP Addresses

Special IP addresses
210
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 IP Addresses
• Private Addresses: Some addresses are reserved for
internal use
• Packet containing private addresses are forwarded by
the routers in the Internet

Addresses for Private Networks

Range Total
[Link] to [Link] 224
[Link] to [Link] 220
[Link] to [Link] 216
211
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Subnets and Subnet Masks
• Allows a network within organization to split into
several parts
– Each part is called subnet
– host portion of address partitioned into subnet number and
host number
– each LAN or subnet assigned subnet number
– subnet mask indicates which bits are subnet number and
which are host number
• The network looks to rest of Internet like single unit
• local routers route within the subnetted network

212
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Subnets and Subnet Masks
• To get subnet mask, set all network bit and subnet bits
to 1

213
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Subnets and Subnet Masks
• To route packet routers perform boolean AND
operation of destination address with subnet mask

Binary Representation Dotted Decimal

IP address 11000000.11100100.00010001.00111001 [Link]
Subnet mask 11111111.11111111.11111111.11100000 [Link]
Bitwise AND of 11000000.11100100.00010001.00100000 [Link]
address and mask
(resultant
network/subnet
number)

Subnet number 11000000.11100100.00010001.001 1

Host number 00000000.00000000.00000000.00011001 25

214
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Subnets and Subnet Masks

215
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Network Address Translation
(NAT)
• Question: how can a site provide multiple computers
access to Internet services without assigning each
computer a globally-valid IP address?

• Answer:
– Network Address Translation (NAT)
• Extension to IP addressing
• IP-level access to the Internet through a single IP address
• Transparent to both ends
• Implementation
– Typically software
– Usually installed in IP router
– Special-purpose hardware for high speed

216
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Network Address Translation
(NAT)
• Organization
– Obtains one globally valid address per Internet connection
– Assigns private addresses internally
– Runs NAT software in router connecting to Internet

• NAT
– Replaces source address in outgoing datagram
– Replaces destination address in incoming datagram
– Also handles higher layer protocols (e.g. TCP or UDP)

217
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Network Address Translation
(NAT)

218
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Network Address Translation
(NAT)

219
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Network Address Translation
(NAT)
• Problems

– It violates the architectural model of IP

– It changes the Internet to a kind of connection-oriented

network

– It violates the most fundamental rule of protocol layering

– Applications are not required to use TCP/UDP

220
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Classless Inter-Domain Routing
(CIDR)
• Addresses are granted in blocks irrespective of classes
• Restriction:
– Addresses in block must be contiguous
– The number of addresses in a block must be a power of 2
– The first address must be divisible by the number of
addresses

First [Link] 11001101 00010000 00100101 00100000

[Link] 11001101 00010000 00100101 00100001
. .
. . 16 Addresses
. .
Last [Link] 11001101 00010000 00100101 00101111
221
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Classless Inter-Domain Routing
(CIDR)
• IP addresses in a block is defined as x.y.z.t/n
• x.y.z.t is one of the addresses and /n is the mask
• The address and the mask completely defines the
whole block
» First address, last address and number of address

• To get the first address, set rightmost 32-n bits to 0s

• To get the last address, set rightmost 32-n bits to 1s

• Number of addresses is 232-n

222
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Classless Inter-Domain Routing
(CIDR)
• Example:
• Suppose one of the address is [Link]/28
• In binary: 11001101 00010000 00100101 00100111

• First address: 11001101 00010000 00100101 00100000

» i.e. [Link]

• Last address: 11001101 00010000 00100101 00101111

» i.e. [Link]

32-28
• Number of addresses: 2 =16
223
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Classless Inter-Domain Routing
(CIDR)
• Example: An ISP is granted a block of addresses starting with
[Link]/16. The ISP needs to distribute these addresses to
three groups as follows:
– The first group has 64 customers; each needs 256 addresses
– The second group has 128 customers; each needs 128 addresses
– The third group has 128 customers; each needs 64 addresses

Group 1 Group 2
Each customer needs 256 addresses Each customer needs 128 addresses
8 bits needed to define each host 7 bits needed to define each host
Mask length 32-8=24 Mask length 32-7=25
[Link]/24 [Link]/24 [Link]/25 [Link]/25
[Link]/24 [Link]/24 [Link]/25 [Link]/25
: :
: :
[Link]/24 [Link]/24 [Link]/25 [Link]/25
224
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Classless Inter-Domain Routing
(CIDR)
• Routing table is [Link]/26
searched based on the
network address
m0
[Link]/22 m1 R1 m3 [Link]/24
• To reduce the routing
table size address m2
aggregation is used
[Link]/26

Mask Network Address Next Hop Interface

[Link]/26
/26 [Link] -- m2
Rest of the Internet
/26 [Link] -- m0
/24 [Link] -- m3
/22 [Link] -- m1
Any Any [Link] m2

225
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Classless Inter-Domain Routing
(CIDR)
• Address Aggregation
Organization 1 [Link]/26
m0
Organization 2 [Link]/26
m1 m4 m0 R2 m1
R1
Organization 3 [Link]/26
m2
m3
Organization 4 [Link]/26
Routing Table for R1
Mask Network Address Next Hop Interface
/26 [Link] --- m0
Routing Table for R2
/26 [Link] --- m1
Mask Network Address Next Hop Interface
/26 [Link] --- m2
/24 [Link] --- m0
/26 [Link] --- m3
/0 [Link] Default m1
/0 [Link] Default m4
226
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Internet Control Message Protocol (ICMP)

• IP provides best effort service

– No error control mechanism
– What happens if something goes wrong?
– Destination is unreachable, time-to-live field has a zero value
– No mechanism for management queries
– Determine if a router or host is alive
– Network administrator needs information from another host or
router
– ICMP was designed to compensate these deficiencies

227
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Internet Control Message Protocol (ICMP)

The principal ICMP message types

228
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Internet Control Message Protocol (ICMP)
• Example debugging tools:
• Ping and traceroute
• Ping:
– Uses ICMP echo-request and echo-reply message
– Calculates RTT too.
• Example:ping [Link]
• PING [Link] ([Link]) 56(84) bytes of data.
• 64 bytes from [Link]: icmp_seq=1 ttl=63 time=0.247 ms
• 64 bytes from [Link]: icmp_seq=2 ttl=63 time=0.231 ms
• 64 bytes from [Link]: icmp_seq=3 ttl=63 time=0.233 ms
• 64 bytes from [Link]: icmp_seq=4 ttl=63 time=0.237 ms
• 64 bytes from [Link]: icmp_seq=5 ttl=63 time=0.250 ms
• 64 bytes from [Link]: icmp_seq=6 ttl=63 time=0.239 ms
• --- [Link] ping statistics ---
– 6 packets transmitted, 6 received, 0% packet loss, time 4996ms
– rtt min/avg/max/mdev = 0.231/0.239/0.250/0.016 ms

229
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Internet Control Message Protocol (ICMP)

• Traceroute:
– Used to find a route to some destination
– Uses time exceeded and destination unreachable
ICMP messages
– Time exceeded is used by routers and destination
unreachable is used by receiving host (uses UDP
port 1)

230
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Internet Control Message Protocol (ICMP)

• Example:
– traceroute [Link]

traceroute to [Link] ([Link]), 30 hops max, 38 byte packets

1 [Link] ([Link]) 1.447 ms 1.347 ms 1.630 ms
2 [Link] ([Link]) 0.232 ms 0.220 ms 0.277 ms

231
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Address Resolution Protocol
(ARP)
• Motivation
– Must use hardware (physical) addresses to
communicate over network
– Applications only use Internet addresses
• Example
– Computers A and B on same network
– Application on A generates packet for application
on B
– Protocol software on A must use B’s hardware
address when sending a packet
232
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Address Resolution Protocol
(ARP)
• Consequence
– Protocol software needs a mechanism that maps
an IP address to equivalent hardware address
– Known as address resolution problem
• Standard for dynamic address resolution in the Internet
• Requires hardware broadcast
• Important idea: ARP only used to map addresses
within a single physical network, never across multiple
networks

233
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Address Resolution Protocol
(ARP)
• Example:
– Machine A broadcasts ARP request with B’s IP
address
– All machines on local net receive broadcast
– Machine B replies with its physical address
– Machine A adds B’s address information to its
table
– Machine A delivers packet directly to B

234
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Address Resolution Protocol
(ARP)

235
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Address Resolution Protocol
(ARP)
• Proxy ARP: An ARP that acts on behalf of a set of hosts

236
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Address Resolution Protocol
(ARP)
• ARP message travels in data portion of network frame
• We say ARP message is encapsulated

237
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Address Resolution Protocol
(ARP)
• Cannot afford to send ARP request for each packet
• Solution
– Maintain a table of bindings
• Effect
– Use ARP one time, place results in table, and then send
many packets
• ARP table is a cache
• Entries time out and are removed
– Avoids stale bindings
• Typical timeout: 20 minutes

238
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Reverse Address Resolution Protocol
(RARP)
• Maps Ethernet address to IP address

• Same packet format as ARP

• Intended for bootstrap

– Computer sends its Ethernet address
– RARP server responds by sending computer’s IP address

• Disadvantage:
– RARP broadcast is not forwarded by the routers

• Currently not used (replaced by DHCP)

239
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Dynamic Host Configuration Protocol
(DHCP)

240
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Routing Protocols in the Internet
• Although it is desirable for routers to exchange routing
information, it is impractical for all routers in an arbitrarily
large internet to participate in a single routing update protocol.

• Consequence: routers must be divided into groups

• Group of networks under one administrative authority is called

Autonomous Systems (AS)

• Free to choose internal routing update mechanism

• Connects to one or more other autonomous systems

241
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Routing Protocols in the Internet
• Two categories:
– Interior Gateway Protocols
– RIP, OSPF
– Exterior Gateway Protocols
– BGP

242
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Routing Information protocol
(RIP)
• Distance-vector protocol
– Uses hop count metric
• Uses split horizon and poison reverse techniques to
solve inconsistencies

• Two Forms:
– Active
– Form used by routers
– Broadcasts routing updates periodically
– Passive
– Form used by hosts
– Does not send updates

243
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Open Shortest Path First (OSPF)
• Uses Link-State Routing algorithm
• More powerful than most predecessors

• Features
– Type of service routing
– Load balancing across multiple paths
– Autonomous systems are partitioned into subsets
called areas
– Every AS has a backbone area (area 0)
– All areas are connected to area 0
– All area has an area border router
244
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Border Gateway Protocol (BGP)
• The most popular (virtually the only) EGP in use in the Internet
• Allows two autonomous systems to communicate routing
information
• Each AS designates a border router to speak on its behalf
• Uses Distance Vector Routing
• Sends path information

245
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 IP Multicasting
• Group address: each multicast group assigned an
unique class D address
– Up to 228 simultaneous multicast groups
• Dynamic group membership
– Host can join or leave at any time
• Uses hardware multicast where available
– If not, use tunneling
• Best-effort delivery semantics (same as IP)
• Arbitrary sender (does not need to be a group member)

246
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 IP Multicasting
• Class D addresses reserved for multicast
– [Link] through [Link]

• General form:

247
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 IP Multicasting
• Mapping IP Multicasting address to hardware
multicasting address
– Place low-order 23 bits of IP multicast address in low-
order 23 bits of the special Ethernet address:
• First 25 bits are 00000001 00000000 01011110 0
• 01.00.5E.00.00.0016
– Example IP multicast address [Link] becomes Ethernet
multicast address
• 01.00.5E.00.00.0216
– Example IP multicast address [Link] becomes
Ethernet multicast address
• 01:00:5E:54:18:09

248
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Internet Group Management protocol
(IGMP)
• Allows host to register participation in a group
• Four types of messages
– General Query, Special Query, Membership Report, Leave Report
• Message Format

Type Maximum Response Time Checksum

Group address (all 0’s in general query)

249
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Internet Group Management protocol
(IGMP)
• Joining a group:
– Hosts maintain a list group of membership
– When a process wants to join a group
• It sends request to host
• Host adds the process to to the requested group
• If this is the first process in the group, host sends a
membership report message
• If not, no need to send membership report message

250
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Internet Group Management protocol
(IGMP)
• Leaving a group
– Host sees that no process is interested in a group
– Host sends a leave report message
– Router sends a special query message to the group
– If no response, router purges the group and sends leave
report
• Monitoring membership
– What happens if a host is removed from the network (this
the only host in the group)
• Router do not receive leave report
– Router periodically sends a general query message
– Hosts reply with membership report (may be delayed
response)
251
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Internet Group Management protocol
(IGMP)
• Encapsulation
– IGMP packet is encapsulated in an IP packet
– Value of protocol field is 2
– TTL must be 1 IGMP Message
IP Header Data
Header Data Trailer

Type Destination IP address

Query [Link] all system on this subnet
Membership Report The multicast address of the group
Leave Report [Link] all routers on this subnet
252
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
The Internet Protocol Version 6 (IPv6)

253
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Deficiencies of IPv4
• Address depletion is a long term problem

• Lack of support for real-time audio and video

transmission

• Lack of security for some applications

254
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Advantages of IPv6 over IPv4
• Longer address space
• 128 bit address Vs 32 bit address
• Simplified header format
• 8 fields Vs 14 fields
• Better support for options
• Simplifies and speeds up the routing process
• Support for security
• Security is an integral part of IPv6
• Support for resource allocation
• Allows special treatment for some packets

255
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 IPv6 Main Header

256
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Extension Header

257
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Extension Header for Routing

258
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 General form of IPv6 Datagram

259
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 IPv6 Addresses
• Uses Hexadecimal Colon notation
• Example: dotted decimal notation
[Link].[Link].[Link].[Link]
• Becomes
68E6:8C64:FFFF:FFFF:0000:1180:096A:FFFF
• Successive zeroes are indicated by a pair of colons
• Example: FF05:0000:0000:0000:0000:0000:0000:00B3
• Becomes FF05::B3
• IPv4 addresses can be written as
– ::[Link]
260
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 IPv6 Addresses
• Entire address space is divided into several
categories
• Few leftmost bits, called prefix, identifies categories
• Unicast addresses:
– Geographic based and provider based

Subnet Prefix

Subscriber Prefix

Provider Prefix

3 5 Provider Identifier Subscriber Identifier Subnet Identifier Node Identifier

261
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 IPv6 Addresses
• Multicast addresses
8 bits 4 bits 4 bits 112 bits
11111111 Flag Scope Group ID

• Reserved addresses
8 bits 120 bits
00000000 All 0s a. unspecified

8 bits 120 bits

00000000 000000000000000………….00000000001 b. Loopback

8 bits 88 bits 32 bits

00000000 All 0s IPv4 address c. Compatible

8 bits 72 bits 16 bits 32 bits

00000000 All 0s All 1s IPv4 address d. Mapped

262
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 IPv6 Addresses
• Local Addresses
10 bits 70 bits 48 bits
1111111010 All 0s Node address a. Link Local

10 bits 38 bits 32 bits 48 bits

1111111011 All 0s Subnet address Node address b. Site Local

263
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Transmission Control Protocol (TCP)

264
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Architectural Relationship
Application Application

HTTP, FTP, SMTP, SNMP, DNS etc.

Transport
TCP UDP layer

DHCP IP Layer 3

PPP Layer 2

Physical Access Network Layer 1

265
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 PDU Flow
HTTP Request

Header contains source and TCP

destination port numbers Header

Header contains: source

and destination IP IP
addresses; transport Header
protocol type

Header contains:
source and destination
Ethernet Trailer
physical addresses;
Header
network protocol type

266
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Prime Design Goals of TCP

• Absorb the shortcomings of IP to make them

transparent to the upper layer(s)
– Interface between IP and Application

• Provide end-to-end (user-user) significance

– Lowermost user-oriented layer

267
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Limitations of Internet Protocol (IP)
• Best-effort network protocol
– Packets may be lost/dropped
– Packets may be delivered out-of-order
– Packets may be duplicated
– Limits messages to some finite size
– Messages may be delayed arbitrarily long

TCP has to take care of these limitations so that

applications do not see them
+
TCP is to provide end-to-end support

268
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 TCP is End-to-End
Machine A Machine B

Application Application
End-to-end
TCP TCP

IP IP
IP
Network Network
Network
Interface Interface
Interface

Router/
Gateway

Network 1 Network 2

269
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 TCP Overview
• Used for most Internet Applications
– FTP, TELNET etc.

• Connection Oriented
– Full duplex

• Byte Stream, not a message stream

• Provides Reliable Service

270
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 TCP Overview

• Flow control
– prevent sender from overrunning receiver

• Congestion control
– prevent sender from overrunning network

TCP PDU is conventionally known as segment

271
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 TCP Header

272
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Connection Establishment and Termination
Active participant Passive participant
(client) (server)

273
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Flow Control
• Uses Sliding Window
• Receiver advertises window size
• As ACK’s arrive window move forward

274
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Flow Control

275
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Nagle’s Algorithm
• What happens when the application does a 1 byte write?

– Interactive editor reacts on every key stroke

– For each character a TCP segment is sent

• Solution: Nagle’s algorithm

– Send the first byte

– Buffer rest of the bytes until acknowledgement comes

– Then send buffered bytes in one TCP segment

– Start buffering again

276
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Silly Window Syndrom
• What happens when application reads one byte at a time?

• Clark’s solution:
– Do not send 1 byte window update
– Wait until decent amount of space is available
277
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Acknowledgement (ACK) in TCP

• Cumulative acknowledgements

• An acknowledgement ack’s all contiguously

received previous data

• TCP assigns byte sequence numbers

See the following examples

278
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Example of Flow
• ACK[ i+1] acknowledges receipt of packets
through packet i

For simplicity, we assume following deviations

from the normal TCP syntax:-

• We will assign packet sequence numbers

– Not byte sequence numbers

279
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Example of Cumulative ACK’s
• A new cumulative acknowledgement is generated
only on receipt of a new in-sequence packet
40 39 38 37
s d
34 35 36 37
Time flows
down

41 40 39 38

35 36 37 38

i data i+1 ACK

280
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Advantage Of Cumulative ACK
• If some of the ACK’s are lost, there is no harm.

• If ACK 49, 51 and 56 are lost, but ACK 60

reaches safely
– What will happen?

281
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delayed ACK’s
• To reduce ACK traffic, it is delayed
• An ACK is delayed until
– another packet is received, or
– delayed ACK timer expires (200 ms typical)

40 39 38 37

34 36 New ACK not produced

on receipt of packet 36,
Example assumes delayed ACK –
but on receipt of 37
every alternate packet is ACK’d

41 40 39 38

36 38
282
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Duplicate ACK’s
• A DUPACK is generated whenever an
out-of-order segment arrives at the receiver
40 39 38 37
(lost)

35 37

42 41 40 39

37 37

DUPACK on receipt of 38
(Above example assumes delayed acks)

283
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Duplicate ACK
• Duplicate ACKs are not delayed
• Duplicate ACKs may be generated when
– a packet is lost, or
– a packet is delivered out-of-order (OOO)

40 39 37 38
(out-of-order)

35 37

41 40 39 37

37 37

DUPACK
On receipt of 38
284
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Congestion Avoidance and Control
• Each sender maintains two windows:

– The window the receiver has granted, rwnd

– The congestion window, cwnd

– Effective window= min ( rwnd, cwnd )

285
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Congestion Avoidance and Control
• Slow Start
– Initial cwnd is set to 1
– Each new ACK doubles cwnd by 1 Segment
• Exponential Growth

• How long exponential increase takes place?

– Until Time out occurs (Slow Start takes place)

or
– Until window reaches threshold value, ssthresh, initially 64
KB (Congestion Avoidance takes place)
286
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Congestion Avoidance and Control
• During Congestion Avoidance
– On each new ACK, increase cwnd by 1/cwnd
packets

– cwnd increases linearly with time during

congestion avoidance

287
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Congestion Avoidance and Control
25

20 Congestion Avoidance

15
ssthresh=16
cwnd

10

5
Slow Start

0
0 1 2 3 4 5 6 7 8

Time

288
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Congestion Avoidance and Control
• On a timeout
– cwnd is reduced to the initial value of 1 MSS

– ssthresh is set to half the window size before

packet loss

– Slow start is initiated

289
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Congestion Avoidance and Control
25

Timeout, cwnd=20
20

15 ssthresh
cwnd

10
ssthresh

0
0

10

12

14

16

18
Time

290
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 TCP Tahoe
• Timeouts can take too long
– how to initiate retransmission sooner?

• Implement Fast Retransmit

– Packet losses are detected via three DUPACKs

– Retransmits the lost segment immediately

– Window reduction is same, applies slow start

291
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 TCP Reno
• Implements Fast Retransmit followed by Fast Recovery
• Different from timeout : slow start follows timeout
– timeout occurs when no more packets are getting across
– fast retransmit occurs when a packet is lost, but latter
packets get through

• Observations:
– Receiver is still getting TCP segments. There can’t be overwhelming
congestion.

• Concept:
– After fast retransmit, reduce cwnd by half, and continue sending
segments at this reduced level.
292
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 TCP Reno
cwnd (initial) ssthresh
Fast Retransmit
Fast Retransmit timeout

new ACK
new ACK

Time
Slow Start Congestion Avoidance

“inflating” cwnd with DUPACKs “deflating” cwnd with a new ACK

293
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 TCP New-Reno
• Fast recovery can result in a timeout with multiple losses per
RTT

• New-Reno implements Fast Retransmit and Modified Fast

Recovery

– stay in fast recovery until all packet losses in window are

recovered

– can recover 1 packet loss per RTT without causing a

timeout

294
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 TCP Selective ACK (TCP SACK)
• TCP acknowledgements are cumulative
– go-back-n ARQ, thus wasting bandwidth

• Selective retransmission as one solution

– Receiver informs the lost packets in blocks
– sender can now retransmit only the missing packets

• Advantage:
– much higher efficiency

• Disadvantage:
– more complex software in a receiver, more buffer needed at the
receiver
295
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 User Datagram Protocol (UDP)

296
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Identifying The Ultimate Destination
• IP address only specifies a computer
• Need a way to specify an application program (process)
on a computer
• Unfortunately
– Application programs can be created and destroyed rapidly
– Each operating system uses its own identification
• TCP/IP introduces its own specification
• Destination point known as port number
• Each OS binds port number to specific application
program
297
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 UDP
• Transport-layer protocol (Layer 4)
• Connectionless service: provides application programs with
ability to send and receive messages
• Allows multiple, application programs on a single machine to
communicate concurrently
• Best-effort semantics as IP
– Message can be delayed, lost, or duplicated
– Messages can arrive out of order
• Does not provide-
– Error Control
– Flow Control

298
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 UDP Message Format

299
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 UDP Pseudo Header

300
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 De-Multiplexing

301
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Remote Procedure Call (RPC)

302
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Remote Procedure Call (RPC)
• A technology in which a program on one machine invokes
procedure residing in another machine.

• The client procedure is bound with a small library procedure, called

client stub.

• The server procedure is bound with a small library procedure,

called server stub.

• Together client and server stub are responsible for hiding the fact
that procedure call is not local.

303
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 RPC steps

304
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Problems with RPC
• Passing a pointer

– Call-by-reference is replaced by copy-restore

• It is not always possible to deduce the types of the parameters

• What about global variables??

305
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
The Real-Time Transport Protocol
(RTP)

(a) The position of RTP in the protocol stack.

(b) Packet nesting.

306
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 The RTP Header

307
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Any Doubt ?
• Please feel free to
write to me:

bhaskargit@[Link]

308
Bhaskar Sardar, Information Technology Department, Jadavpur University, India