RECAP MIDTERM Computer Networks

History : Protocol Stack

 History : Protocol Stack

Some of the slides in this presentation has been adopted from the resources provided by the book Computer Networking: A
Top-Down Approach by Jim Kurose and Keith Ross
[Link]

History : Protocol Stack

So, what is Internet?

Internet

Inter-net

A network of networks
 4
The Internet != The Web
• The Internet is a worldwide network of interconnected computers.
• ARPANET adopted TCP/IP protocol in 1983 (birth of the modern Internet)
• The Web is a worldwide network of interconnected hypertext pages.
• Web browser app connects to web server apps.
• Web is just one of many applications built on top of the Internet and DNS.
• Uses HTTP protocol (first version, 0.9, was released in 1991)
• Invented at CERN on the France/Switzerland border.
• Apart from the Web, many other applications use the Internet:
• Email, SSH, BitTorrent, Voice-over-IP telephony, FTP, Remote Desktop,
VNC, Skype, Telnet, Snapchat, FaceTime, Netflix … you name it!
• Any smartphone app that communicate with a backend service
 5
The Internet is distributed and loosely coupled
• No one entity manages all the hosts, routers, and links on the Internet.
• Hosts join by building a physical connection to an existing host.
• Hardware and software come from many different vendors.
• Standard Internet protocols define how devices should interoperate.

• A network protocol defines proper communication patterns between

devices:
• types of messages that can be sent,
• structure of the messages (bit-level representation),
• possible responses and actions to take.
• Clearly-defined protocols allow us to create new devices that are compatible
with the existing ones, and thus expand the Internet ad-hoc.
The Internet – in practice 6

• All machines on the Internet can send and mobile network

receive messages, but there are two distinct
categories of participants: global ISP
• Network edge:
• Hosts: clients and servers home
network
• Have only one link to the Internet regional ISP

• Network core:
• Routers connecting various Internet parts
• These are like hosts with multiple links and
living only to relay others’ packets.
Machines are connected by physical media: institutional
• Wired and wireless communication links network
And links

link
phone
lines

end-system switch
fibers
wireless
cable TV links
lines

7
Transfers data

link

end-system switch
path
data

Internet Service Provider 8

8
 A federated system
• The Internet ties together different networks by the IP protocol
➢One interface to bind them all together

• The Internet ties together different

networks
Google
Fiber
➢>18,000 ISP networks

• Interoperability between users and

networks as well as between different
Comcast
AT&T networks

9
Massive Scale

• 4.47 Billion users (59% of world population)

• 1 Trillion websites
• 200 Billion emails sent per day
• 2.5 Billion smartphones
• 2.7 Billion Facebook users
• 4 Billion YouTube videos watched per day
• Routers that switch 10 Terabits/second
• Links that carry 100 Gigabits/second

10
 Component Names

Component Function Example

Application, or app, user Uses the network Skype, iTunes, Amazon
Host, or end-system, edge Supports apps Laptop, mobile, desktop
device, node, source, sink
Router, or switch, node, Relays messages Access point, cable/DSL
hub, intermediate system between links modem
Link, or channel Connects nodes Wires, wireless
 Computer network names by scale

Scale Type Example

Vicinity PAN (Personal Area Network) Bluetooth (e.g., headset)
Building LAN (Local Area Network) WiFi, Ethernet
City MAN (Metropolitan Area Network) Cable, DSL
Country WAN (Wide Area Network) Large ISP
Planet The Internet (network of all networks) The Internet!
 Networks Need Modularity

• The network does much for apps:

• Make and break connections
• Find a path through the network
• Transfers information reliably
• Transfers arbitrary length information
• Send as fast as the network allows
• Shares bandwidth among users
• Secures information in transit
• Lets many new hosts be added
• …
Protocols and Layers (2)
• Protocols are horizontal, layers are vertical
Instance of Peer
Protocol X
protocol X instance
X X
Service provided
Lower layer by Protocol Y
instance (of
protocol Y) Y Y

Node 1 Node 2

14
 Protocols and Layers (3)
• A protocol is a set of rules or conventions that allow peer layers to communicate
• The key features of a protocol are:

• Format of data
Syntax blocks

• Control
information for
Semantics coordination and
error handling

• Speed matching
Timing and sequencing

15
Layered Network Stack
 Modularity
Applications
16  Does not specify an implementation
 Instead, tells us how to organize
Layer N functionality
 Encapsulation
…

 Interfaces define cross-layer interaction

 Layers only rely on those below them
Layer 2  Flexibility
 Reuse of code across the network

Layer 1  Module implementations may change

 Unfortunately, there are tradeoffs

 Interfaces hide information
Physical
 As we will see, may hurt performance…
Media
 17
Who implements each layer?
Hardware & • Link layer: shares a physical channel
station

Switch
Base

Router
driver among several transmitters/receivers
• Network layer: routes from source to
destination, along many hops.
Operating
System
• Transport layer:
• Multiplexing (>1 connection / machine)
• Ordering, • Acknowledgement, • Pacing
Language
User- • HTTP layer:
/Libraries
level • Resource urls, • Response codes,
application • Caching, • Content-types, • Compression
The ISO OSI Model

OSI: Open Systems Interconnect Model

Host 1 Switch Host 2
Application Application
Presentation Layers communicate Presentation
All devices
Layers implement
communicate
peer-to-peer
Session thepeer-to-peer
first three layers Session
Transport Transport
Network Network Network
Data Link Data Link Data Link
Physical Physical Physical

18
Layer Features

Application
Presentation  Service
Session  What does this layer do?

Transport  Interface
 How do you access this layer?
Network
 Protocol
Data Link
 How is this layer implemented?
Physical

19
Physical Layer
 Service
Application  Move information between two
systems connected by a physical link
Presentation
 Interface
Session  Specifies how to send one bit

Transport  Protocol
 Encoding scheme for one bit
Network
 Voltage levels
Data Link  Timing of signals

Physical  Examples: coaxial cable, fiber optics,

radio frequency transmitters

20
Data Link Layer

 Service
Application  Data framing: boundaries between
packets
Presentation
 Media access control (MAC)
Session  Per-hop reliability and flow-control

Transport  Interface
 Send one packet between two hosts
Network connected to the same media
Data Link  Protocol
 Physical addressing (e.g. MAC address)
Physical  Examples: Ethernet, Wifi, DOCSIS

21
Network Layer
 Service
Application  Deliver packets across the network

 Handle fragmentation/reassembly
Presentation
 Packet scheduling

Session  Buffer management

Transport  Interface
 Send one packet to a specific
Network destination
Data Link  Protocol
 Define globally unique addresses
Physical
 Maintain routing tables

 Example: Internet Protocol (IP), IPv6

22
Transport Layer
 Service
Application  Multiplexing/demultiplexing

 Congestion control
Presentation
 Reliable, in-order delivery

Session  Interface
 Send message to a destination
Transport
 Protocol
Network  Port numbers
Data Link  Reliability/error correction

 Flow-control information
Physical
 Examples: UDP, TCP

23
Session Layer

 Service
Application
 Accessmanagement
Presentation  Synchronization

Session  Interface
Transport  It depends…

Network  Protocol
 Token management
Data Link
 Insert checkpoints
Physical
 Examples: none

24
Presentation Layer
 Service
Application  Convert data between different
representations
Presentation  E.g. big endian to little endian

Session  E.g. Ascii to Unicode

Transport  Interface
 It depends…
Network
 Protocol
Data Link  Definedata formats
Physical  Apply transformation rules

 Examples: none

25
Application Layer

Application  Service
Presentation  Whatever you want
 Interface
Session
 Whatever you want
Transport
 Protocol
Network  Whatever you want
Data Link  Examples: turn on your smartphone
Physical and look at the list of apps

26
 Encapsulation
Matryoshka dolls (stacking dolls)
Matryoshka dolls (Russian: матрёшка) are a set of wooden dolls of decreasing size, each one fitting inside the next larger one

message segment datagram frame

Credit: [Link]
 Services, Layering and Encapsulation

application message M M application

transport segment Ht M Ht M transport

network datagram Hn Ht M Hn Ht M network

Hl Hn Ht Hl Hn Ht link
link frame M M

physical physical

source destination
Encapsulation

How does data move through the layers?

Data Application
Presentation
Session
Transport
Network
Data Link
Physical Data
 LAYERED TASKS

We use the concept of layers in our daily life. As an example, let

us consider two friends who communicate through postal mail.
The process of sending a letter to a friend would be complex if
there were no services available from the post office.
Real Life Analogy- Tasks involved in sending a letter
Real Life Analogy- Tasks involved in sending a letter
Doesn’t know how the
Postal network works

Label contains
Un-packing
routing info
Doesn’t know
contents of letter

Postal Service 32
Example: organization of air travel

ticket (purchase) ticket (complain)

baggage (check) baggage (claim)
gates (load) gates (unload)
runway takeoff runway landing
airplane routing airplane routing
airplane routing

airline travel: a series of steps, involving many services

33
Introduction: 1-33
 Example: organization of air travel

ticket (purchase) ticketing service ticket (complain)

baggage (check) baggage service baggage (claim)
gates (load) gate service gates (unload)
runway takeoff runway service runway landing
airplane routing routing service airplane routing
airplane routing

layers: each layer implements a service Q: describe in words

▪ via its own internal-layer actions the service provided
▪ relying on services provided by layer below in each layer above
Layering of airline functionality

layers: each layer implements a service

▪ via its own internal-layer actions
▪ relying on services provided by layer below

Q: describe in words
the service provided
in each layer above
Network Stack in Practice

Host 1 Switch Host 2

Application Application
Presentation Presentation
Video
FTP Client
Session
Client Video Server
Session
FTP Server
UDP
Transport
TCP UDP
Transport
TCP
Network
IP Network
IP Network
IP
Data Link
Ethernet
802.11n Data Link
Ethernet
802.11n Data Link
Ethernet
802.11n
Physical Physical Physical
Encapsulation, Revisited

HTTP Web Web

Header Page Server

TCP HTTP Web

TCP
Header Header Page
TCP Segment

IP TCP HTTP Web

Header IP
Header Header Page
IP Datagram

Ethernet IP TCP HTTP Web Ethernet

Ethernet
Header Header Header Header Page Trailer

Ethernet Frame
Summary of Layers
Common functionality & problems

Application Anything you want... Reliability, flow control, ordering, ...

Process-level Reliability,flow control, ordering, congestion,

Transport ...
communication
Packets across domains Independent parties, scale,routing Addressing,
Network
Packets across networks heterogeneity, routing

Data Link Packets on a‘wire’ Framing,errors, addressing

Physical Encoding of bits Physics

Why Layering?
dealing with complex systems:
▪ explicit structure allows identification, relationship of
complex system’s pieces
• layered reference model for discussion
▪ modularization eases maintenance, updating of system
• change in layer's service implementation: transparent to rest of
system
• e.g., change in gate procedure doesn’t affect rest of system
▪ layering considered harmful?
▪ layering in other complex systems?
Addresses in TCP/IP Protocol Suite
Switching Techniques

✓Circuit Switching
✓Message Switching (Store and Forward)
✓Packet Switching (Store and Forward)
Circuit Switching

✓Control message sets up a path from origin to destination

✓Return Signal informs source to that data transmission may proceed
✓Data Transmission starts
✓Entire path remains allocated to the transmission (whether used or not)
✓When transmission is over or complete source releases the circuit/path
Circuit Switching ….
Circuit-switched Network
• a dedicated connection, called a circuit, is always available between the two
end systems; the switch can only make it active or inactive.
– E.g., Telephone Network
Message Switching
✓Each message is addressed to a destination
✓When the entire message is received at an IMP(interface message processor), the next step
in its journey is selected; if this selected channel is busy, the message waits in a queue until
the channel becomes free
✓From one node to node through a network while allocating only one channel at a time.
Thus, the message hops Control message sets up a path from origin to destination
✓Analogy: Postal Service
Message Switching…
Packet Switching
• Message divided into packets
– Header identifies the destination address
• Packets travel separately through the network
– Forwarding based on the destination address
– Packets may be buffered temporarily
• Destination reconstructs the message

✓Messages are split into smaller pieces called packets

✓These packets are numbered and addressed and sent through the network one at a time
✓Pipelining
Packet Switching…
Circuit Switching/Message Switching/Packet Switching…
 Packet Switching
• Decide data boundary from the communication of one user – data packets

Packet Multiplexing
 Internet Structure: A “network of networks”

… and regional networks may arise to connect access nets to ISPs

access access
net net
access
net
access
access net
net
IXP access
access net
net ISP A

access
net
IXP ISP B access
net

access ISP C
net
access
net

access
net regional ISP access
net
access access
net access net
net
 Internet Structure: A “network of networks”

… and content provider networks (e.g., Google, Microsoft, Akamai) may run
their own network, to bring services, content close to end users
access access
net net
access
net
access
access net
net
IXP access
access net
net ISP A

access
net
Content provider
IXP network
ISP B access
net

access ISP C
net
access
net

access
net regional ISP access
net
access access
net access net
net
 Internet Structure: A “network of networks”

Tier 1 ISP Tier 1 ISP Google

IXP IXP IXP

Regional ISP Regional ISP

access access access access access access access access

ISP ISP ISP ISP ISP ISP ISP ISP

At “center”: small # of well-connected large networks

▪ “tier-1” commercial ISPs (e.g., Level 3, Sprint, AT&T, NTT), national & international coverage
▪ content provider networks (e.g., Google, Facebook): private network that connects its data centers to
Internet, often bypassing tier-1, regional ISPs
 Network Taxonomy

Telecommunication
networks

Circuit-switched Packet-switched
networks networks

Networks Datagram
FDM TDM
with VCs Networks

❑ Datagram network is not either connection-oriented or connectionless.

❑ Internet provides both connection-oriented (TCP) and connectionless
services (UDP) to applications.
 Links: Delay and Bandwidth
❑ Delay
❑ Latency for propagating data along the link
❑ Corresponds to the “length” of the link
❑ Typically measured in seconds
❑ Bandwidth (Capacity)
❑ Amount of data sent (or received) per unit time
❑ Corresponds to the “capacity” of the link
❑ Typically measured in bits per second

Bandwidth delay x bandwidth

(Bps) (bit)

Delay
(sec)

1-56
Network Bandwidth, Throughput and Goodput

Application Transport Network Link Physical

Layer Layer Layer Layer layer
Bandwidth Tps, Segmant/s Packet/s Frame/s Bit/s
Throughput HTTPops/s,
Goodput …

❑ Bandwidth: The rate at which the data units can be

transmitted.
❑ Throughput: The rate at which the data units are delivered
(transferred).
❑ It is a function of load.
❑ Its upper-band is Bandwidth.
❑ Goodput: The rate at which the useful data units are
delivered (transferred).
❑ Its upper-band is the Throughput.
Throughput, Goodput vs Load

Throughput

Goodput
 Example: Network Layer Goodput

❑ Goodput:
(recieved packets - recieved replica)  payload length per packet [bit]
Goodput [b / s] =
recieving time duration [sec]

❑ Efficiency:
goodput [bps]
Efficiency = 100
optimum goodput [bps]
Optimum goodput = goodput in condition of :
no - loss packet, no - corupted packet, and no - congestion link.
 Data Link Layer

History : Protocol Stack

 History : Protocol Stack
Data Link Layer

Function:
Application ◦ Send blocks of data (frames) between
physical devices
Presentation ◦ Regulate access to the physical media
Session Key challenge:
Transport ◦ How to delineate frames?
◦ How to detect errors?
Network ◦ How to perform media access control
Data Link (MAC)?
◦ How to recover from and avoid
Physical collisions?

History : Protocol Stack

 History : of
Typical Implementation Protocol
Layers Stack

History : Protocol Stack 6

2
The Data LinkHistory
Layer : Protocol Stack

• LLC
– Logical Link Control
– Refers upward to higher layers
• MAC
– Media Access Control
– Refers downward to lower layers

History : Protocol Stack

 Every Layer Adds Up Their Own Services

Addressing Routing
Network

Framing and
Switching Flow Control Error Control
Access Control
Data Link
MAC LLC

Analog AD/DA Modulation Coding

Communication Conversion
Physical
Data Link Layer DesignHIssues
Stack
1. Framing
• Delimiting start/end of frames
2. Error detection and correction
• Handling errors
3. Retransmissions
• Handling loss
4. Multiple Access
• 802.11, classic Ethernet
5. Switching
• Modern Ethernet

History : Protocol Stack

Data Link Layer DesignHIssues
Stack
• Services Provided to the Network Layer
• Framing
• Error Control
• Flow Control
• Addressing

History : Protocol Stack

 History
Functions of the : Protocol
Data Link Layer Stack

• Provide service interface to the network layer

• Dealing with transmission errors
• Regulating data flow
• Slow receivers not swamped by fast senders
• Clearly identify receiver (link may be shared)

History : Protocol Stack

 History
Link Layer Services : Protocol Stack
(more)

 Flow Control:
 pacing between adjacent sending and receiving nodes
 Error Detection:
 errors caused by signal attenuation, noise.
 receiver detects presence of errors:
• signals sender for retransmission or drops frame
 Error Correction:
 receiver identifies and corrects bit error(s) without resorting
to retransmission
 Half-duplex and full-duplex
 with half duplex, nodes at both ends of link can transmit,
but not at same time

History : Protocol Stack

Media Access History : Protocol Stack

• Determine how to get access when there is competition

for the media.
• MAC (Medium Access Control) sub-layer takes care of
this problem
• MAC is important in LANs where broadcast channels are
used
• MAC is the lower part of the data link layer (next to
physical layer)
• Mac sub-layer does not guarantee delivery

History : Protocol Stack

Framing History : Protocol Stack

Physical layer determines how bits are encoded

Next step, how to encode blocks of data
◦Packet switched networks
◦Each packet includes routing information
◦Data boundaries must be known so headers can be read
Types of framing
◦Byte oriented protocols
◦Bit oriented protocols
◦Clock based protocols

History : Protocol Stack

DLL Design History : Protocol Stack
FRAMING

The DLL translates the physical layer's raw bit stream into discrete units
(messages) called frames. How can frame be transmitted so the receiver can
detect frame boundaries? That is, how can the receiver recognize the start and
end of a frame? We will discuss four ways:

Character Count:

Bit Stuffing:

Character stuffing:

Encoding Violations:

71
History : Protocol Stack
DLL Design History : Protocol Stack
FRAMING

• First try:
• Let’s start each frame with a length field!
• It’s simple, and hopefully good enough …
Character Count:

• Make the first field in the frame's header be the length of the frame. That way
the receiver knows how big the current frame is and can determine where the
next frame ends.

• Disadvantage: Receiver loses synchronization when bits become garbled. If

the bits in the count become corrupted during transmission, the receiver will
think that the frame contains fewer (or more) bits than it actually does.

• Although checksum will detect the frames are incorrect, the receiver will have
difficulty re-synchronizing to the start of a new frame. This technique is not
used anymore, since better techniques are available.

72
History : Protocol Stack
DLL History : Protocol Stack
Design Protocols
Multi-access FRAMING

Bit Stuffing:

IDEA: Use reserved bit patterns to indicate the start and end of a frame. For
instance, use the 4-bit sequence of 0111 to delimit consecutive frames. A frame
consists of everything between two delimiters.

Problem: What happens if the reserved delimiter happens to appear in the frame
itself? If we don't remove it from the data, the receiver will think that the
incoming frame is actually two smaller frames!

Solution: Use bit stuffing. Within the frame, replace every occurrence of two
consecutive 1's with 110. E.g., append a zero bit after each pair of 1's in the
data. This prevents 3 consecutive 1's from ever appearing in the frame.

Chap. 3- DLL 73
History : Protocol Stack
DLL History : Protocol Stack
Design Protocols
Multi-access FRAMING

Bit Stuffing:

The receiver converts two consecutive 1's followed by a 0 into two 1's, but
recognizes the 0111 sequence as the end of the frame.

Example: The frame "1 0 1 1 1 0 1" would be transmitted over the physical layer as
"0 1 1 1 1 0 1 1 0 1 0 1 0 1 1 1".

Note: When using bit stuffing, locating the start/end of a frame is easy, even when
frames are damaged. The receiver simply scans arriving data for the reserved
patterns.

The main disadvantage with bit stuffing is the insertion of additional bits into the
data stream, wasting bandwidth.

Chap. 3- DLL 74
History : Protocol Stack
DLL History : Protocol Stack
Design Protocols
Multi-access FRAMING

Character stuffing:

Same idea as bit-stuffing, but operates on bytes instead of bits.

Use reserved characters to indicate the start and end of a frame. For instance, use the two-
character sequence DLE STX (Data-Link Escape, Start of TeXt) to signal the beginning of
a frame, and the sequence DLE ETX (End of TeXt) to flag the frame's end.

Problem: What happens if the two-character sequence DLE ETX happens to appear in the
frame itself?

Solution: Use character stuffing within the frame, replace every occurrence of DLE with the
two-character sequence DLE DLE. The receiver reverses the process, replacing every
occurrence of DLE DLE with a single DLE.

Example: If the frame contained "A B DLE D E DLE", the characters transmitted over the
channel would be "DLE STX A B DLE DLE D E DLE DLE DLE ETX".

Chap. 3- DLL 75
DLL History : Protocol Stack
Design Protocols
Multi-access FRAMING

Encoding Violations:

Send a signal that doesn't conform to any legal bit representation. In Manchester
encoding, for instance, 1-bits are represented by a high-low sequence, and 0-
bits by low-high sequences. The start/end of a frame could be represented by
the signal low-low or high-high.

The advantage of encoding violations is that no extra bandwidth is required as in

bit or character stuffing. The IEEE 802.4 standard uses this approach.

Finally, some systems use a combination of these techniques. IEEE 802.3, for
instance, has both a length field and special frame start and frame end
patterns.

76
 History
Dealing with Noise : Protocol Stack

The physical world is inherently noisy

◦Interference from electrical cables
◦Cross-talk from radio transmissions, microwave ovens
◦Solar storms
How to detect bit-errors in transmissions?
How to recover from errors?

77
Error Detection History : Protocol Stack
and Correction
• Some bits will be received in error due to noise.
• What can we do?

• Detect errors with codes

• Retransmit lost frames Later
• Correct errors with codes

• Reliability is a concern that cuts across the layers

History : Protocol Stack

 History
Error Detection : Protocol Stack
and Correction

▪ Error-Detecting Codes
▪ Error-Correcting Codes

History : Protocol Stack

Parity Bits History : Protocol Stack

 Idea: add extra bits to keep the number of 1s even

 Example: 7-bit ASCII characters + 1 parity bit
0101001 1 1101001 0 1011110 1 0001110 1 0110100 1
10

Detects 1-bit errors and some 2-bit errors

Not reliable against bursty errors

80
 History
Error Correcting Codes: Protocol Stack
• Hamming code: 1-bit ECC
• How to use Hamming code to correct Data bits = m; Check bits = r
burst errors? Each code of size n = (m+r)
• Hamming distance between two codes (D1 D2) (n+1)2m 2n or (m+r+1) 2r
is the number of bit flips needed to change D1
to D2
b1 b2b3b4b5b6b7b8b9b10b11
0 0 1100 10 0 0 0
8421
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
10 1010
11 1011
 History
Error Correcting Codes: Protocol Stack

Because of the telephone company’s great interest in communications, it

has performed extensive research in finding codes that not only detect an
error but correct that error. [Link] developed a system that is
easily implemented.
Assuming four data bits must be transmitted, the word format would be
as follows:
D7 D6 D5 P4 D3 P2 P1
1 1 1 1 1 0 1

Bits 4,5,6,7 - no error 0 1 0

Bits 2,3,6,7, - error
Bits 1,3,5,7 – no error

Bit 2 is in error, and the correct code is 1111111

 History
Error Detecting Codes : Protocol Stack

▪ Polynomial code (a.k.a. CRC) Cyclic Redundancy Code checksum

computation.

The algorithm is as follows :

➢ Let r be the degree of G(x). Append r zero bits to the lower order
end of the frame, so it now contains m+r bits and corresponds to the
polynomial xrM(x).

➢ Divide the bit string corresponding to G(x) into the bit string
corresponding to xrM(x). using modulo 2 division.

➢ Subtract the remainder (which always have r or fewer bits) from

the bit string corresponding to xrM(x) using modulo 2
subtraction. The result is the checksummed frame to be
transmitted. Call this polynomial as T(x).
CRC codes History : Protocol Stack

Generator polynomial
x4+x+1

r=4
 History : Protocol Stack
CRC codes (Proof)

To encode a message polynomial M(x) using a generator polynomial G(x) of

order r, we divide XrM(x) by G(x) and add the remainder R(x) of the
division to XrM(x) to form the polynomial T(x). That is

XrM(x)=Q(x) G(x) + R(x) ………. Eq(1)

Where Q(x) is the quotient obtained by dividing XrM(x) by G(x). Also we have
T(x) defined as per our algorithm

T(x)= XrM(x) - R(x)…………… Eq(2)

Substituting value of XrM(x) from eq(1) into eq(2) we get

T(x)= Q(x) G(x) + R(x) - R(x)
= Q(x)G(x)

Hence all code polynomial are divisible by G(x)

CRC codes History : Protocol Stack
How to choose a generator polynomial
The encoded message containing error can be represented as
H(x)=T(x) + E(x)
Where E(x) is a polynomial with non-zero terms
If the received message H(x) is not divisible by G(x) that means there is
an error . On the other hand if H(x) is divisible by G(x) means either
E(x) = 0, or E(x) is divisible by G(x).

Case 1: E(x) = xi (a single bit error) at position i.

If we choose G(x) so that it has at least two non-zero terms (xn and 1)
So G(x) cannot divide xi.

Case 2 : E(x) = xi + xj
= xi(1+xj-i) where j > i.
from case 1, G(x) cannot divide xi. E(x) will be divisible
by G(x) only if G(x) divides (1+xj-i).
We are interested in having (1+xj-i) not to be divisible by G(x).
CRC codes History : Protocol Stack
If G(x) is a primitive polynomial:

It has at least three one’s. (i.e. of type xl + xk + 1).

Thus if G(x) is selected to be a primitive polynomial with degree N = n – k,
then it will detect all double errors as long as the code word length does
not exceed 2n-k – 1.
For example CRC-16 = (x16 + x15 + x2 + x + 1) can detect double errors as
long as the code word length does not exceed 215 – 1 = 32,767.

Burst error will also be of the form xid(x) where deg(d(x)) = L-1
Burst error
00000 11000…….011
L

If deg(G(x)) > deg(d(x)) then G(x) cannot divide d(x).

History : Protocol Stack

 History : Protocol Stack
CRC cont…

▪ If a generator cannot divide xt + 1 (t between 0 and n – 1), then all isolated

double errors can be detected.
▪ A generator that contains a factor of x + 1 can detect all odd-numbered
errors.
▪ All burst errors with L ≤ r will be detected.
▪ All burst errors with L = r + 1 will be detected with probability 1 – (1/2)r–1.
▪ All burst errors with L > r + 1 will be detected with probability 1 – (1/2)r.

A good polynomial generator needs to have the following characteristics:

▪ It should have at least two terms.
▪ The coefficient of the term x0 should be 1.
▪ It should not divide xt + 1, for t between 2 and n − 1.
▪ It should have the factor x + 1.

History : Protocol Stack

CRC
• codes History : Protocol Stack

Four Polynomial codes widely used are :

CRC-12 = x12+x11+x3+x2+x+1

CRC-16 = x16+x15+x2+1

CRC-CCITT = x16+x12+x5+1

CRC-32 = x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1.

Implementation of CRC is easy as we multiply the M(x) by 2n, it can be implemented

using shift left register, and modulo 2 can be implemented using XOR gates.

History : Protocol Stack

 90

Cyclic Redundancy Check (CRC)

• Error detection scheme that can be efficiently implemented using XOR circuitry.
• Very common in practice.
• Ethernet header uses CRC-32, using a specific 32-bit generator integer.
 History
Error Correction : Protocol
or Error DetectionStack
?

▪ If channel is of poor quality, use error correction

▪ If channel is of better quality, prefer error detection +
retransmission

• Error correction:
• Needed when errors are expected
• Or when no time for retransmission
• Error detection:
• More efficient when errors are not expected
• And when errors are large when they do occur
DLL Design History : Protocol Stack
ERROR CONTROL

Must insure that all frames are eventually delivered (possibly in order) to a
destination. Three components are required to do this:

Acknowledgments, Timers, and Sequence Numbers

Acknowledgments:

• Reliable delivery is achieved using the "acknowledgments with retransmission"

paradigm.
• The receiver returns a special acknowledgment (ACK) frame to the sender
indicating the correct receipt of a frame.
• In some systems, the receiver also returns a negative acknowledgment (NACK)
for incorrectly-received frames.
• This is only a hint to the sender so that it can retransmit a frame right away
without waiting for a timer to expire.

92
DLL Design History : Protocol Stack
ERROR CONTROL

Timers:
• One problem that simple ACK/NACK schemes fail to address is recovering
from a frame that is lost, and as a result, fails to solicit an ACK or NACK.
• What happens if an ACK or NACK becomes lost?
• Retransmission timers are used to resend frames that don't produce an ACK.
When sending a frame, schedule a timer to expire at some time after the ACK
should have been returned. If the timer goes off, retransmit the frame.

Sequence Numbers:
• Retransmissions introduce the possibility of duplicate frames.
• To suppress duplicates, add sequence numbers to each frame, so that a receiver
can distinguish between new frames and repeats of old frames.
• Bits used for sequence numbers depend on the number of frames that can be
outstanding at any one time.

93
DLL Design History : Protocol Stack
FLOW CONTROL

Flow control deals with throttling the speed of the sender to match that of the
receiver. Usually, this is a dynamic process, as the receiving speed depends on
such changing factors as the load, and availability of buffer space.

One solution is to have the receiver extend credits to the sender. For each credit,
the sender may send one frame. Thus, the receiver controls the transmission
rate by handing out credits.

94
DLL ProtocolsHistory : Protocol Stack
Overview

ELEMENTARY DATA LINK PROTOCOLS:

The DLL provides these services to the Network Layer above it:

Data handed to a DLL by a Network Layer on one module, are handed to the
Network Layer on another module by that DLL.

95
DLL ProtocolsHistory : Protocol Stack
AN UNRESTRICTED SIMPLEX
PROTOCOL

Assumptions:

Data transmission in one direction only (simplex).

No errors take place on the physical channel.

The sender/receiver can generate/consume an infinite amount of data.

Always ready for sending/receiving.

DLL ProtocolsHistory : Protocol Stack
SIMPLEX STOP-AND-WAIT
PROTOCOL
Assumptions:

No longer assume receiver can process incoming data infinitely fast.

Sender ships one frame and then waits for acknowledgment (stop and wait.)

The contents of the acknowledgment frame are unimportant.

Data transmission is one directional, but must have bi-directional line. Could have
a half-duplex (one direction at a time) physical channel.

97
 History
Sliding Window : srotocol Stack
Protocols
FEATURES

Assumptions:

Use more realistic Two-way communication.

We now have two kinds of frames (containing a "kind" field):

1. Data
2. ACK containing (sequence number of last correctly received frame).

Piggybacking - add acknowledgment to data frames going in reverse direction.

Piggybacking issue: For better use of bandwidth, how long should we wait for
outgoing data frame before sending the ACK on its own.

98
 History
Sliding Window : Protocol Stack
Protocols

• Sender maintains Swin

• Receiver maintains
Rwin
• Frame(s) to be sent
must have send_seq#
within Swin
• Receiver is permitted
to accept frames that
fall within its Rwin
• After every successful
send/recv, windows are
incremented.
• Number of frames in a) A sliding window of size 1, with a 3-bit sequence number.
transit = windows size b) (a) Initially.
c) (b) After the first frame has been sent.
d) (c) After the first frame has been received.
e) (d) After the first acknowledgement has been received.
 History
Sliding Window : Protocol Stack
Protocols
SLIDING WINDOW MECHANISMS

Go back n - equivalent to receiver's window size of one.

If receiver sees bad frames or missing sequence numbers, subsequent frames are discarded.
No ACKs for discarded frames.

Selective repeat - receiver's window size larger than one.

Store all received frames after the bad one.
ACK only last one received in sequence.

100
 History
Should We Error Check: in
Protocol
the Data Stack
Link?

Recall the End-to-End Argument

Cons:
◦ Error free transmission cannot be guaranteed
◦ Not all applications want this functionality
◦ Error checking adds CPU and packet size overhead
◦ Error recovery requires buffering
Pros:
◦ Potentially better performance than app-level error checking
Data link error checking in practice
◦ Most useful over lossy links
◦ Wifi, cellular, satellite

101
 History : Protocol Stack
Multi-access Protocols

History : Protocol Stack

 History : Protocol
Evolution of Contention Protocols Stack

Developed in the 1970s for a packet

Aloha radio network

◦ Improvement: Start transmission only at fixed times

Slotted (slots);
Aloha
◦ Significantly fewer collisions than ALOHA
CSMA = Carrier Sense Multiple Access
CSMA Improvement: Start transmission only if no
transmission is ongoing

CD = Collision Detection
Improvement: Stop ongoing transmission if
CSMA/CD
a collision is detected (e.g. Ethernet)

103
103
 History
Collisions in (Pure) : Protocol Stack
ALOHA

1.1 1.2 1.3

Station 1
Transmission
Time
(F)

2.1 2.2
Station 2

3.1 3.2
Station 3

Complete Partial
Collision Collision

Broadcast
channel

History : Protocol Stack 104

104
Collisions andHistory : Protocol
Vulnerable Period Stack

Frame which collides Frame which collides

with start of red frame with end of red frame

Frame

t0-F t0 t0+F

Vulnerable
Period of red frame
Time

• A frame (red frame) will be in a collision if and only if another

transmission begins in the vulnerable period of the frame
• Vulnerable period has the length of 2 frame times

History : Protocol Stack 105

105
 History
Performance of : Protocol
(Pure) ALOHA (1) Stack

• Notation:

Let t =  + r ------------------ Eq - 1
t = total number of packets received per sec over the channel
r = total number of packets rejected
 = number of packets transmitted successfully

106
PerformanceHistory : Proto (col Stack
of (Pure) ALOHA(2)

Let b be the no. of bits / packet, R be the Channel capacity in bits/sec

The successful traffic ratio is referred to as the throughput
’ = b bits/sec ---------------------- Eq - 2
The traffic arriving over the channel i.e., total traffic rate
G’ = bt bits/sec --------------------- Eq – 3

Given R is the Channel capacity in bits/sec

Normalized throughput 
 = b / R bits/sec ------- Eq - 4
= ’ / R bits/sec (from Eq -2 ’ = b)
Normalized total traffic G
G = G’ / R
= bt / R ---------- Eq - 5
where 0 ≤ G ≤ 

107
 History
Performance of (Pure) ALOHA(3)
: Proto((33)col Stack

Let  be the packet transmission time = b / R sec

The collision window in case of ALOHA is given by 2 sec.
So (Eq – 4) and (Eq – 5) may be written as
 = b / R =  ---------- Eq - 6
G = bt / R = t ---------- Eq - 7
The probability of receiving k messages in T secs, is given by Poisson’s
distribution:
PT (k) = e-T (T)k k=0,1,2,3………..

k!
The traffic arrival rate over the channel
t =  + r
The probability of successful transmission T = 2
Pt 2 = e -t 2 (t2)k
k!

108
 History
Performance of : Protocol Stack
(Pure) ALOHA(4)

= e-t 2 ( for k = 0 )

Successful transmission =  / t = e-t 2

 = t e-t 2
( = / and t = G/ )
From (Eq-6 and Eq-7)

/ = G/ e - 2G
 = G e - 2G
The maximum value of throughput () would be when G = ½
 = 1/2e
  0.18
At best using ALOHA we can have the maximum channel utilization of 18%.

109
 History
Slotted ALOHA : Protocol Stack
(S-ALOHA)

• The Slotted Aloha Protocol

– Slotted Aloha - Aloha with an additional constraint
– Time is divided into discrete time intervals (=slot)
– A station can transmit only at the beginning of a frame

• As a consequence:
– Frames either collide completely or do not collide at all
– Vulnerable period = ?

110
 History
Collisions in Slotted : Protocol
ALOHA : Stack

1.1 1.2 1.3

Station 1
Transmission
Delay

2.1 2.2
Station 2

3.1 3.2
Station 3

Complete
Collision

Broadcast
channel

11
1
 History
Performance of Slotted: ALOHA
Protocol: Stack

• Total Throughput in S-ALOHA:

 = G e -G

• Maximum achievable throughput:

 max = e −1 = 0.37
• Performance gain but requires nodes to have
synchronized frame boundaries

11
2
 History
Comparison of : Protocol
Pure ALOHA Stack
& Slotted ALOHA
Protocol
◦ Same as ALOHA, except time is divided into slots
◦ Hosts may only transmit at the beginning of a slot
Thus, frames either collide completely, or not at all
◦ 37% throughput vs. 18% for ALOHA
◦ But, hosts must have synchronized clocks

Throughput

Load

History : Protocol Stack 113

Taking-Turns History
protocols: Protocol Stack

A token moves around the network.

When a computer wants to send data, it waits

for the token.

When it gets the token, it attaches the data and

How It Works sends it.

The receiver gets the data.

The token becomes free again and continues

moving.
 History
Toking-passing : Protocol Stack
protocols 115

• Like a polling protocol, but without the special leader node.

• Nodes have a designated order 1…N.
• One nodes transmits up to some maximum number of packets, then
sends a special message (a token) giving the next node a turn.
• Nodes only send packets while “holding” the token, so collisions are
avoided.
• If token-holding node crashes, the entire
network is crashed. (like crashing Shared
the leader node in a polling protocol). medium

Token Bus (802.4)/Token Ring (802.5) options

Token
Token Ring (802.5)

Token Bus (802.4)

Ethernet frame
History : Protocol Stack 116

• Adds bytes before and after an IP datagram.

type
dest. source data
• Preamble is 8 bytes, 1010…1011
preamble MAC
MAC
addres
addres
s
(IP payload) CRC Inter-packet gap
s
• Used to synchronize bit-clock of the receiver to the sender.
• Type (2 bytes) usually indicates IP payload (ARP has a different type).
• CRC (4 bytes) is added after the payload, for bit-error detection.

History : Protocol Stack

CSMA/CD History : Protocol Stack

Carrier sense multiple access with collision detection

Key insight: wired protocol allows us to sense the medium
Algorithm
1. Sense for carrier
2. If carrier is present, wait for it to end
▪ Sending would cause a collision and waste time
3. Send a frame and sense for collision
4. If no collision, then frame has been delivered
5. If collision, abort immediately
▪ Why keep sending if the frame is already corrupted?
6. Perform exponential backoff then retransmit

History : Protocol Stack 117

 History : Protocol Stack
Exponential Backoff

When a sender detects a collision, send “jam signal”

◦ Make sure all hosts are aware of collision
◦ Jam signal is 32 bits long (plus header overhead)
Exponential backoff operates in multiples of 512 bits
◦ Select k ∈ [0, 2n – 1], where n = number of collisions
◦ Wait k * 51.2µs before retransmission
◦ n is capped at 10, frame dropped after 16 collisions
Backoff time is divided into contention slots

Remember
this number

History : Protocol Stack

 History : Protocol Stack
Persistent Methods

Three persistent methods are:

▪The I-persistent method: In this method,
after the station finds the line idle, it sends its
frame immediately (with probability I).
▪The non-persistent method: If the line is idle,
it sends immediately. If the line is not idle, it
waits a random amount of time and then
senses the line again.
▪The p-persistent method: The p- persistent
method is used if the channel has time slots
with a slot duration equal to or greater than
the maximum propagation time.

Source: B. A. Forouzan, “ Data Communications and Networking ,” McGraw-

Hill Forouzan Networking Series,5E.

119
Flow DiagramHistory : Protocol
of Persistent Stack
Methods

Source: B. A. Forouzan, “ Data Communications and Networking ,” McGraw-

Hill Forouzan Networking Series,5E.

120
 History
Minimum Packet Sizes :and
Protocol Stack
Cable Length

Why is the minimum packet size 64 bytes?

◦ To give hosts enough time to detect collisions
What is the relationship between packet size and cable length?

1. Time t: Host A starts A

transmitting B
2. Time t + d: Host B Propagation Delay (d)
starts transmitting
3. Time t + 2*d: Host A A B
detects the collision

History : Protocol Stack

Exercise History : Protocol Stack

Derive the maximum cable length

◦ Min frame size: b
◦ Bandwidth: r
◦ Cable length: l
◦ Propagation delay: d
◦ Speed of light (xmit one bit): c

A B
1. Time t + 2*d: Host
A detects the Propagation Delay (d)
collision
A B
2. Must transmit bits
for longer than 2*d

History : Protocol Stack 122

 History
Minimum Packet Sizes : Protocol Stack

Why is the minimum packet size 64 bytes?

◦ To give hosts enough time to detect collisions
What is the relationship between packet size and cable length?

• 10 Mbps Ethernet
1. Time t: Host A starts Aand cable lengths change
transmitting • Packet B
2. Time t + d: Host B starts for faster Ethernet standards
Propagation Delay (d)
transmitting
3. Time t + 2*d: collision
detected

min_frame_size*light_speed/(2*bandwidth) = max_cable_length
(64B*8)*(2.5*108mps)/(2*107bps) = 6400 meters

History : Protocol Stack 123

 History
Transmission : Protocol Stack

Signal Encoding

History : Protocol Stack

 HistoryModes
Transmission : Protocol Stack
The transmission of binary data across a link can be accomplished in either
parallel or serial mode. In parallel mode, multiple bits are sent with each
clock tick. In serial mode, 1 bit is sent with each clock tick. While there is
only one way to send parallel data, there are three subclasses of serial
transmission: asynchronous, synchronous, and isochronous.

History : Protocol Stack

 History
Parallel : Protocol
Transmission Stack
Use n wires to send n bits at one time.

Source: B. A. Forouzan, “ Data Communications and Networking ,”

McGraw- Hill Forouzan Networking Series,5E.

History : Protocol Stack

 SerialHistory : Protocol
Transmission Stack
In serial transmission one bit follows another, so we need only one
communication channel rather than n to transmit data between
two communicating devices

Source: B. A. Forouzan, “ Data Communications and Networking ,”

McGraw- Hill Forouzan Networking Series,5E.

History : Protocol Stack

 History :Transmission
Asynchronous Protocol Stack
In asynchronous transmission, we send 1 start bit (0) at the beginning and
1 or more stop bits (1s) at the end of each byte.
There may be a gap between each byte.

Source: B. A. Forouzan, “ Data Communications and Networking ,”

McGraw- Hill Forouzan Networking Series,5E.

History : Protocol Stack

 HistoryTransmission
Synchronous : Protocol Stack
▪ In synchronous transmission, we send bits one after another without start
or stop bits or gaps.
▪ It is the responsibility of the receiver to group the bits.
▪ The bits are usually sent as bytes and many bytes are grouped in a frame.
▪ A frame is identified with a start and an end byte.

Source: B. A. Forouzan, “ Data Communications and Networking ,”

McGraw- Hill Forouzan Networking Series,5E.

History : Protocol Stack

 History : Protocol
From Signals Stack
to Packets

Analog Signal

“Digital” Signal

Bit Stream 0 0 1 0 1 1 1 0 0 0 1
0100010101011100101010101011101110000001111010101110101010101101011010111001
Packets
Header/Body Header/Body Header/Body

Packet
Transmission Sender Receiver

History : Protocol Stack

 HistoryModulation
: Protocol Stack
Sender changes the nature of the signal in a way that
the receiver can recognize.
» Similar to radio: AM or FM
Digital transmission: encodes the values 0 or 1 in the
signal.
» It is also possible to encode multi-valued symbols
Amplitude modulation: change the strength of the
signal, typically between on and off.
» Sender and receiver agree on a “rate”
» On means 1, Off means 0
Similar: frequency or phase modulation.
Can also combine method modulation types.

History : Protocol Stack

 History
Amplitude : Protocol
and Frequency Stack
Modulation

0011 0011000111000110001110

0 1 1 0 1 1 0 0 0 1

History : Protocol Stack

 History
Amplitude : Protocol
and Frequency Stack
Modulation

Amplitude Shift Keying

Frequency Shift Keying

Phase Shift Keying

History : Protocol Stack

 History : Protocol
Time Division Stack
Multiplexing

Different users use the wire at different points in time.

Aggregate bandwidth also requires more spectrum.

Frequency

Frequency

History : Protocol Stack

 History : Protocol
Wavelength Stack
Division Multiplexing
Send multiple wavelengths through the same fiber.
» Multiplex and demultiplex the optical signal on the fiber
Each wavelength represents an optical carrier that can carry a
separate signal.
» E.g., 16 colors of 2.4 Gbit/second
Like radio, but optical and much faster

Optical
Splitter

Frequency

History : Protocol Stack

 History
Why Do: Protocol Stack
We Need Encoding?
Meet certain electrical constraints.
» Receiver needs enough “transitions” to keep track of the transmit
clock
» Avoid receiver saturation
Create control symbols, besides regular data symbols.
» E.g. start or end of frame, escape, ...
Error detection or error corrections.
» Some codes are illegal so receiver can detect certain classes of errors
» Minor errors can be corrected by having multiple adjacent signals
mapped to the same data symbol
Encoding can be very complex, e.g. wireless.

History : Protocol Stack

 History Encoding
: Protocol Stack
Use two discrete signals, high and low, to encode 0 and 1.
Transmission is synchronous, i.e., a clock is used to
sample the signal.
» In general, the duration of one bit is equal to one or two clock ticks
» Receiver’s clock must be synchronized with the sender’s clock
Encoding can be done one bit at a time or in blocks of,
e.g., 4 or 8 bits.

History : Protocol Stack

 History
Non-Return : Protocol
to Zero (NRZ) Stack
1 → high signal, 0 → low signal
0 0 1 0 1 0 1 1 0 0

NRZ

Clock

 Problem: long strings of 0 or 1 cause desynchronization

 How to distinguish lots of 0s from no signal?
 How to recover the clock during lots of 1s?
1 -> high signal; 0 -> low signal
Long sequences of 1’s or 0’s can cause problems:
» Sensitive to clock skew, i.e. hard to recover clock
» Difficult to interpret 0’s and 1’s

History : Protocol Stack 138

 History :
Desynchronization Protocol Stack
Problem: how to recover the clock during sequences of 0’s or 1’s?

0 1 1 1 1 1 1 1 1 0

NRZ

0 1 1 1 1 1 1 1 0

Transitions Receiver
signify misses a 1
clock ticks due to skew

History : Protocol Stack 139

 History
Non-Return : Protocol
to Zero Stack
Inverted (NRZI)

1 → make transition, 0 → remain the same

0 0 1 0 1 0 1 1 0 0

NRZI

Clock

 Solves the problem for sequences of 1s, but not 0s

1 -> make transition; 0 -> signal stays the same

Solves the problem for long sequences of 1’s, but not
for 0’s.

History : Protocol Stack 140

 History
Manchester : Protocol Stack
1 → high-to-low, 0 → low-to-high

0 0 1 1 0

NRZI

Clock

 Good: Solves clock skew (every bit is a transition)

 Bad: Halves throughput (two clock cycles per bit)

Positive transition for 0, negative for 1

Transition every cycle communicates clock (but need 2
transition times per bit)

141
 History : Protocol
4B/5B EncodingStack
Data coded as symbols of 5 line bits => 4 data bits, so 100
Mbps uses 125 MHz.
» Uses less frequency space than Manchester encoding
Uses NRI to encode the 5 code bits
We convert 4bits to 5bits, ensuring at least one transition in
them. The basic idea here is that 5bit code selected must
have :
✓ one leading 0
✓ No more than two trailing 0s
Each valid symbol has at least two 1s: get dense transitions.
16 data symbols, 8 control symbols
» Data symbols: 4 data bits
» Control symbols: idle, begin frame, etc.
Example: FDDI (Fibre Distributed Data Interface)

History : Protocol Stack

 History
4-bit/5-bit Encoding: Protocol Stack
4-bit/5-bit (100 Mbps Ethernet)
Observation: NRZI works as long as no sequences of 0
Idea: encode all 4-bit sequences
8-bit / 10-bitasused
5-bitin
sequences
Gigabit with no more than
one leading 0 and two trailingEthernet
0

4-bit 5-bit 4-bit 5-bit

0000 11110 1000 10010
0001 01001 1001 10011 There will not be more than
0010 10100 1010 10110
0011 10101 1011 10111 two continuous zero (0) in
0100 01010 1100 11010 5B code
0101 01011 1101 11011
0110 01110 1110 11100
0111 01111 1111 11101
Tradeoff: efficiency drops to 80%
Other Encoding variants
8B/10B: Fiber Channel and Gigabit Ethernet
» DC balance
64B/66B: 10 Gbit Ethernet
143
 History : Protocol
Network TopologyStack
• Type of Connection
– Point-to-Point: direct link between two devices
– Multipoint: single link between three or more devices

• Physical Topology
– Bus
– Star
– Mesh
– Ring

History : Protocol Stack

 History Network
: Protocol
Types Stack
• Local Area Networks (LAN)

• Wide Area Networks (WAN)

• Internet is arguably the largest WAN ever created by mankind

History : Protocol Stack 14

 History
Data flow : Protocol
(simplex, half-duplex, Stack
and full-duplex)

History : Protocol Stack 14

 History : Protocol
Ethernet Stack

institutional link
to ISP (Internet)
institutional router

Ethernet
institutional mail,
switch
web servers

• typically used in companies, universities, etc

• 10 Mbps, 100Mbps, 1Gbps, 10Gbps transmission rates
• today, end systems typically connect into Ethernet switch

History : Protocol Stack

Figure 7.1 ARP and RARP
ARP and RARP

148
 Position of ARP and RARP in TCP/IP protocol suite

Internet Group Management Protocol

Internet control message protocol

Notice that ARP and RARP are supplemental to IP.

149
7.1 ARP
ARP associates an IP address with its physical address. On a
typical physical network, such as a LAN, each device on a link is
identified by a physical or station address that is usually imprinted
on the NIC.

150
ARP operation

151
 Figure 5 Encapsulation of ARP packet

The ARP packet is encapsulated within an Ethernet packet.

Note: Type field for Ethernet is x0806

152
ARP Request / Reply

An ARP request is broadcast;

an ARP reply is unicast.

153
Figure 6 Four cases using ARP

154
Figure 7.7 Example 1

155
 Figure 7.8 Proxy ARP

A proxy ARP, running in a router, can respond to an ARP request for any of its
proteges (supported by old entries). The proxy ARP replies with its own MAC
address. When the packet arrives, the router delivers it to the appropriate host.

156
7.2 ARP PACKAGE
In this section, we give an example of a simplified ARP software package
to show the components and the relationships between the components.
This ARP package involves five modules: a cache table, queues, an output
module, an input module, and a cache-control module.

The topics discussed in this section include:

Cache Table
Queues
Output Module
Input Module
Cache-Control Module

157
 ARP Cache
Maintain a cache of recently acquired pairs
◼ Keep IP, PhyAddr pairs to reduce comm costs
Looks in cache before sending packet
◼ If have a binding, use it
◼ If not, broadcast an ARP request
Since most communications involve multiple packets, even a small cache
helps
Mapping
◼ If have binding in cache, use it
◼ If not, send broadcast
May not get reply (lost or machine down)
Must store outgoing packets
If other programs run, must not generate multiple requests for the
same address currently waiting on
◼ When ARP reply arrives
Update ARP cache

158
 The Cache Table

◼ If ARP just resolved an IP address, chances are a few

moments later someone is going to ask to resolve the
same IP address

◼ When ARP returns a MAC address, it is placed in a

cache. When the next request comes in for the same IP
address, look first in the cache

159
Figure 7.9 ARP components

160
The Cache Table Contents(1)

◼ State: FREE, PENDING, RESOLVED

◼ Hardware type: same as ARP field
◼ Protocol type: same as ARP field
◼ Hardware length: same as ARP field
◼ Protocol length: same as ARP field
◼ Interface number: port number (m0,m1, m2)

161
 The Cache Table Contents(2)

◼ Queue number: which queue the ARP request is

sitting in
◼ Attempts: how many times have you tried to
resolve this address?
◼ Time-out: how long until this address is tossed
out (need the room in cache)
◼ Hardware address: destination hardware address
◼ Protocol address: destination IP address

162
 How Does the Cache Work?(1)

◼ The output module waits for an IP packet with a

request
◼ Checks the cache for an existing entry
◼ If entry found and state RESOLVED, we already
have this MAC address
◼ If entry found and state PENDING, packet waits
until dest hard addr found

163
 How Does the Cache Work?(2)

◼ If no entry found, output module places this request in

queue, and a new entry is placed in cache with state
PENDING and ATTEMPTS set to 1. An ARP request is
then broadcast

164
 How Does the Cache Work? (3)

◼ The input module waits until an ARP request or

reply arrives
◼ Module checks the cache for this entry
◼ If entry is found and state is PENDING, module
updates entry’s target hardware address, changes
state to RESOLVED, and sets the TIME-OUT
value

165
 How Does the Cache Work? (4)

◼ If entry is found and state RESOLVED, module still

updates the entry (target hardware address could
have changed) and the TIME-OUT value reset
◼ If entry not found, module creates a new entry.
State is set to RESOLVED and TIME-OUT is set

166
 How Does the Cache Work? (5)

◼ Now the module checks to see if arrived ARP

packet is a Request. If it is, the module
immediately creates an ARP Reply message and
sends it back to sender.

167
 How Does the Cache Work? (6)

◼ The cache-control module periodically checks each cache

entry
◼ If entry’s state is FREE, skips it
◼ If entry’s state is PENDING, Attempts field is incremented
by 1. This value greater than max? Toss this entry (and
mark entry as FREE). Less than max? Send another ARP
request

168
 How Does the Cache Work? (7)

◼ If state of entry is RESOLVED, module

decrements value of Time-out field accordingly
◼ If Time-out field < 0, then remove entry and set
state to FREE

169
 Example 2

The ARP output module receives an IP datagram (from the

IP layer) with the destination address [Link]. It checks
the cache table and finds that an entry exists for this
destination with the RESOLVED state (R in the table). It
extracts the hardware address, which is 457342ACAE32,
and sends the packet and the address to the data link layer
for transmission. The cache table remains the same.

170
Table 7.1 Original cache table used for examples

171
 Example 3

Twenty seconds later, the ARP output module receives an

IP datagram (from the IP layer) with the destination
address [Link]. It checks the cache table and does not
find this destination in the table. The module adds an
entry to the table with the state PENDING and the
Attempt value 1. It creates a new queue for this destination
and enqueues the packet. It then sends an ARP request to
the data link layer for this destination. The new cache table
is shown in Table 7.2.

See Next Slide

172
Table 7.2 Updated cache table for Example 3

173
 Example 4

Fifteen seconds later, the ARP input module receives an ARP packet
with target protocol (IP) address [Link]. The module checks the
table and finds this address. It changes the state of the entry to
RESOLVED and sets the time-out value to 900. The module then
adds the target hardware address (E34573242ACA) to the entry.
Now it accesses queue 18 and sends all the packets in this queue, one
by one, to the data link layer. The new cache table is shown in Table
7.3.

See Next Slide

174
Table 7.3 Updated cache table for Example 4

175
 Example 5

Twenty-five seconds later, the cache-control module updates

every entry. The time-out values for the first three resolved
entries are decremented by 60. The time-out value for the last
resolved entry is decremented by 25. The state of the next-to-the
last entry is changed to FREE because the time-out is zero. For
each of the three pending entries, the value of the attempts field
is incremented by 1. One entry (IP addr [Link] is over max,
so change to FREE.

See Next Slide

176
Table 7.4 Updated cache table for Example 5

177
7.3 RARP

RARP finds the logical address for a machine that only knows its physical
address.

This if often encountered on thin-client workstations. No disk, so when

machine is booted, it needs to know its IP address (don’t want to burn
the IP address into the ROM).

RARP requests are broadcast, RARP replies are unicast.

If a thin-client workstation needs to know its IP address, it probably

also needs to know its subnet mask, router address, DNS address, etc.
So we need something more than RARP. BOOTP, and now DHCP have
replaced RARP.

178
Figure 7.10 RARP operation

179
Figure 7.12 Encapsulation of RARP packet

180
Huffman Coding
Link Deficit Algorithm
Traffic Matrix Calculation, hopcount etc

181