Transcript x - WordPress.com

Computer Communication Networks
7A and 7B
PESSE
Instructor: Hari
Books


Textbook: Data Communications and
Networking (B. Forouzan)
Reference: Computer Networks (J.F. Kurose,
K.W. Ross)

Reference: Introduction to Data Communication
and Networking (W. Tomasi)
Introduction

Some terms related to networking:

Network, Telecommunication, Data communication, Jitter in
transmission, Data representation, Simplex, Half-duplex,
Full-duplex transmission

Network topology (mesh, star, bus, ring, hybrid)

Categories of networks: LAN (Local Area Network), WAN
(Wide Area Network), MAN (Metropolitan Area Network),
wireless sensor networks, RAN (Radio Area Network –
connects between UE and core network), VPN (Virtual
Private Network)

internet: when 2 or more networks are connected together
History of the Internet















History of the internet: see
http://en.wikipedia.org/wiki/History_of_the_Internet
1960s: Email, Telnet
1971: FTP
1979: Usenet
1983: Internet, based on TCP/IP protocol suite
1988: IRC
1992: WWW
1993: Blog
1994: Yahoo! Web directory
1995: Wikis were developed
1998: Google
2001: Wikipedia
2004: Facebook
2005: Youtube
2006: Twitter
The Syllabus


Networking models (OSI and TCP/IP), various
types of transmission media
Data link control: Ensuring that data is reliably
sent across physical channels

Multiple Access: Controlling simultaneous
access to the medium

IEEE Standards for wired and wireless LANs

Connecting LANs together

Network layer and addressing
Layered Tasks


The task of a communication network is to
transmit data from one point to another
Although the entire process could be
implemented in hardware, this would become
very complex and tedious

Hence there is a division of tasks into different
software “layers”, with each layer using the
services of the other layers
Layered Tasks


Layering is common even in application
software on computers.
For example, the layers might be Application,
Operating System (OS), Basic Input Output
System (BIOS), and computer hardware

The Application uses the services of the OS, the
OS uses the services of the BIOS, and the
BIOS controls the system hardware

Layering can be seen even in conventional
Layered Tasks: The Postal System
OSI model


A layered architecture for data communication
over networks
Never really became popular, because TCP/IP
overtook it

Called “International Standards Organisation
Open Systems Interconnection (ISO OSI)
model”

Allows complete interoperability between
Layers of the OSI model

Application

Presentation

Session

Transport

Network

Data link

Physical
How OSI Works

Each layer provides some “services” (routines)

On a single node (computer), each layer uses
the services of the layer below it; there is an
interface between adjacent layers

Communication across nodes can be effected at
the same layer; this is called a “peer-to-peer
process” (peer means having the same rank in
the hierarchy of layers)
How OSI Works

To actually transmit data, the data must be propagated all the
way down the stack of layers onto the physical medium
OSI: Physical Layer


Physical Layer deals with mechanical and
electrical specifications of the interface and
transmission medium
Also defines the procedures and functions that
physical devices and interfaces have to perform
for transmission to occur

Defines encodings of bits into waveforms
suitable for transmission onto the channel

Other functions: Data rate setting, bitsynchronization, network topology, transmission
OSI: Data Link Layer

The physical layer is a raw communication
facility. The Data Link Layer transforms this into
a reliable communication link that appears error
free to the higher layers
OSI: Data Link Layer


Framing: division of higher layer data into frames
suitable for transmission by the physical medium
Physical Addressing: to correctly differentiate between
destinations on the network, a header is added to the
frame

Flow Control: To ensure that data buffers don't overflow

Error control: Retransmission of lost or damaged
frames; addition of an error-control trailer to the frame

Access Control: This is also called Medium Access
Control (MAC) and decides which device has control of
OSI: Network Layer


Data link layer: responsible for data
transmission from source to destination within
the same network
Network layer: responsible for end-to-end
delivery across possibly multiple interconnected
networks

Internetworks: networks of networks

Handles logical addressing (like the IP address)

Handles routing across the network
OSI: Transport Layer


Network layer oversees source-to-destination
delivery of individual packets
The transport layer applies higher-level error
control and flow control to reassemble the
packets in the correct order into the original
message. Ensures process-to-process delivery
of entire message

Other functions: service point (port) addressing,
segmentation and reassembly, connection
OSI: Session Layer


Dialog control: allows 2 systems to enter into a
dialog, allows communication to take place in
either half or full duplex mode
Synchronization: Allows addition of
synchronization points to a data stream.
OSI: Presentation Layer

“Presentation” of data

Translation: of one machine's hardware data
format to another machine's hardware data
format (e.g. Big-Endian to Little-Endian number
representation)

Encryption

Data compression
OSI: Application Layer


Enables the user (human or software) to access
network services.
Applications: email, chat, file transfer, web
browsing, etc
TCP/IP Protocol Suite


Layers in the TCP/IP protocol suite do not
exactly match the OSI model (TCP/IP was
developed before OSI)
5 layers may be assumed: Physical, Data Link,
Network, Transport, Application

Application = Application + Presentation +
Session of the OSI model
Comparison of TCP/IP and OSI
models

Application + Presentation + Session =
Application (SMTP, FTP, HTTP, DNS, SNMP,
TELNET)

Transport = SCTP, TCP, UDP

Network = IP, ICMP, IGMP, RARP, ARP

Data Link + Physical = Protocols defined by the
underlying networks

See Figure on page 43 of Furuozan
TCP/IP: Physical and Data Link
Layers


No specific protocol defined at this level by
TCP/IP
Supports all standard and proprietary protocols
(like IEEE 802.1, 802.11)
TCP/IP: Network Layer


At the network layer, TCP/IP supports IP:
Internetworking protocol. IP depends on ARP,
RARP, ICMP, IGMP
IP: Internetworking Protocol

A “bare-bones” unreliable and connectionless protocol that
provides necessary infrastructure for the higher layers

Data is sent in packets called datagrams

Datagrams may travel along different routes and arrive out of
sequence or be duplicated

IP cannot reorder datagrams and recombine into data once the
datagrams have been received

Is a host-to-host protocol – delivers from one physical device to
TCP/IP: Address Resolution
Protocol


Every node on a network has a physical
address
Nodes on a network also have logical
addresses i.e. IP addresses that may change

A lookup needs to be performed to find out the
physical or hardware address in a network (eg.
a LAN) corresponding to a given logical or
internet address.
TCP/IP: RARP

Reverse ARP

Enables a node to determine its logical address
given its physical address.

Application: when a node is newly added to a
network, it sends a RARP request to determine
its logical address
TCP/IP: ICMP

ICMP = Internet Control Message Protocol

Chiefly used by the operating systems of
networked computers to send error messages

Not used to send data between computers

Not usually used in applications; exceptions are
Ping and TraceRoute (try these!)
TraceRoute output

hari@hari-laptop:~$ traceroute www.google.com

traceroute to www.google.com (209.85.231.104), 30 hops max, 40 byte packets

1 192.168.1.1 (192.168.1.1) 1.561 ms 2.110 ms 2.645 ms

2 117.192.224.1 (117.192.224.1) 243.950 ms 245.212 ms 248.918 ms

3 218.248.160.234 (218.248.160.234) 251.153 ms 252.183 ms *

4 ***

5 ***

6 * * 59.163.25.242.static.vsnl.net.in (59.163.25.242) 94.500 ms

7 121.240.0.5.static-Mumbai.vsnl.net.in (121.240.0.5) 485.301 ms 487.769 ms 490.202 ms

8 216.239.43.214 (216.239.43.214) 492.746 ms 495.336 ms 497.729 ms

9 72.14.232.93 (72.14.232.93) 502.103 ms 209.85.241.52 (209.85.241.52) 519.332 ms 72.14.232.93
(72.14.232.93) 507.087 ms

10 72.14.238.74 (72.14.238.74) 531.687 ms 66.249.94.90 (66.249.94.90) 510.220 ms 72.14.238.74
(72.14.238.74) 532.143 ms
TCP/IP: IGMP

IGMP = Internet Group Messaging Protocol

A mechanism for multicast (the simultaneous
transmission of data to a group of recipients)

What kind of applications would require
multicast?
TCP/IP: Transport Level Protocols

UDP: User Datagram Protocol

Process-to-process protocol

Adds port address, checksum error control and
length information to data from upper layer

TCP: Transmission Control Protocol

Is a “stream” transport protocol. This means that a
connection must be established between both ends
of a transmission before either can transmit data

TCP segments data at the transmitting end
TCP/IP: Application Layer


TCP/IP Application Layer = OSI Session +
Presentation + Application
Sample applications: SMTP (Simple Mail
Transfer Protocol), FTP (File Transfer Protocol),
HTTP (Hypertext Transfer Protocol), DNS
(Domain Name System), SNMP (Simple
Network Management Protocol), TELNET
TCP/IP: Addressing

Four levels of addressing: Physical, Logical,
Port and specific address

Why the need for a hierarchy of addressing?

Physical address: the address of the node in its
LAN or WAN; included in the frame at the data
link layer

Logical address: a universal addressing system.
Called the IP address.
TCP/IP: Addressing


Port Address: Once data arrives on a particular
node, it must be routed to the correct
application, or process. This is effected using
the port address. Eg. Port address for HTTP
transactions is 80.
Specific addressing: User-friendly address
formats used by applications; these are
converted to the lower level formats as required

Eg: [email protected]
Telephone and Cable Networks for
Data Transmission

Telephone networks: for voice communication

Digital data: transferred over telephone lines
using dial-up MODEMs (ModulatorDemodulator)

DSL: Digital Subscriber Line, a service provided
for access to the Internet through telephone
lines. Is much faster than dialup modems

Cable networks: used for providing TV signals to
Telephone networks

Telephone network: invented in 1800s

Called POTS: Plain Old Telephone System

POTS was originally all-analog, but is now
mixed digital and analog

Components: Local loops, Trunks, Switching
offices (end offices, tandem offices, regional
offices)

Local loop: a twisted pair cable that connects
Telephone networks


Trunks: Transmission media that handle the
communication between offices. Many
connections are handled (hundreds to
thousands)
Switching office: To avoid having a permanent
physical link between subscribers, switches are
needed to set up the connection. This is done in
the switching office. A switch connects several
local loops or trunks and allows a connection
Telephone networks: Signalling


Signalling: The use of signals for controlling
communication; the information exchange
concerning the establishment and control of a
telecommunication circuit and the management
of the network
In-band signalling: Use of voice bandwidth for
signalling. Eg: Rotary dialling, DTMF

Out-of-band signalling: The voice bandwidth and
signalling bandwidth are separate (eg SS7)
Telephone networks: Signalling


Signalling system: provides dial tone, maintains
and monitors call, keeps billing information,
caller ID, voice mail, etc
Signalling System 7: Out of band system
(avoids security problems of SS5, which used
in-band multifrequency signalling)

SS7 is a layered protocol (5 layers). An example
of the physical layer is “T1” (1.544 Mbps)
carrier. T1: (24 channels/frame * 8
Dialup modem

Traditional telephone line frequency range: 300-3300 Hz

Baud rate: number of symbols per second transferred

Modem: Modulator + Demodulator. Modulator: conversion
of binary data to modulated waveforms. Demodulator:
Conversion of Waveforms to binary data.

Modem standards: V32 (Trellis coded modulation) 32 QAM,
of which 1 bit is error correcting. So 4 bits/symbol*2400
baud =9600 bps

Also: V32bis, V34bis,V90, V92
DSL


Digital Subscriber Line – supports high speed data communication
over local loops
ADSL: Asymmetric DSL (Asymmetric means unequal upstream and
downstream rates, ~ .5 Mbps and 8Mbps). Existing local loops can
actually handle upto 1.1 Mhz, but are filtered to 4 kHz at the end office
(why?). This filter is removed for ADSL

ADSL is adaptive: actual data rate depends on condition of local loop
line

ADSL Modulation: DMT (Discrete Multitone Technique) = QAM +
FDM. Here, the total bandwidth of 1.1 Mhz is divided into 256
channels or bins of 4.3125 kHz (FDM). Based on the SNR for each
channel, the data rate is set on a channel by channel basis – some of
the carriers are deleted in the bins where noise is large

ADSL uses interleaving of Datalink frames; QAM is the modulation
HDSL

HDSL, SDSL, VDSL

HDSL: High bit rate DSL. T1 uses AMI (Alternate Mark
Inversion) coding; this is susceptible to attenuation at high
frequencies. HDSL uses 2B1Q encoding to achieve greater
repeater distance at 1.544 Mbps. T1 line ~ 1km. HDSL line
~ 3.86 km. Two twisted pairs used for full-duplex
transmission (2B1Q).

SDSL: Symmetric Digital Subscriber Line. Symmetric
means same data rate in both directions (768 kbps in each
direction). Is HDSL with one twisted pair cable, but still
supports full duplex. (2B1Q).

VDSL: Very high bit rate DSL; uses coaxial, fiber-optic or
Cable TV for data transmission


DSL: uses existing unshielded twisted pair cable,
susceptible to noise. So we use cable TV (a coaxial system
from end to end)
Hybrid Fiber-Coaxial N/w used: Fiber from Regional Cable
Head (RCH) to fiber node; coaxial cable through the
neighbourhood

RCH: serves up to 400,000 subscribers

Communication in the traditional cable network is
unidirectional. But we make this bidirectional by using
bidirectional amplifiers

Bandwidth: 5 to 750 Mhz. Divided into video, upstream and
Cable TV for data transmission

Downstream: 64 QAM modulation, ~30 Mbps

Upstream: QPSK modulation, ~12 Mbps

Sharing of bandwidth needs to be done both upstream and
downstream.

Read up on cable nws from page 257 (assignment)
Unit 2: Data Link Control

Data link layer has 2 main functions:

Data link control (handles adjacent node-to-node
communication (WAN) or communication within the
same network segment (LAN))

Medium access control (how to share the data link)

Data link control: framing, flow and error control
Framing


Physical layer functions: mechanical & electrical
specifications, modulation or encoding scheme,
data rate setting, synchronization, topology,
transmission mode (simplex, half- or full-duplex)
Most important functions: modulation scheme,
synchronization

Physical layer: gets bits across the channel

Data link layer: packs bits into frames suitable
for transport across the medium
Framing


Framing: in the postal system, in the form of an
envelope
Framing: other examples of framing. Written
text?

Framing in the data link layer: a source address
and a destination address are added. Why is
the source address needed?

Basic reason for framing: error in a frame
Framing

Types of framing: Fixed-size and variable size

Fixed-size framing: ATM WAN

Variable sized framing: frame size needs to be specified

Character-oriented protocol: special characters are present
at the beginning and end of the frame. Drawback: This is OK
for text applications, but not OK when a general stream of
binary data is used, because the marker may show up as
data. To guard against this, an escape character is used to
signify that the next character (possibly marker) in the frame
is actually data (byte stuffing). The escape character is
removed from the payload. To represent Esc character in
data, Esc Esc is used in the frame. This prevents big messup
Framing

Variable-Size framing

Bit-oriented protocol: Zero-bit insertion

First used in IBM's SDLC (later called HDLC). Also used
in USB to prevent transmission of too many 1s.

Now we work with the actual bitstream rather than a
stream of characters.

The pattern 01111110 is used at the beginning and end of
the frame

If 011111 is encountered in the data, mindlessly insert 0

So: 0111111 --> 01111101

0111110-->01111100, so that receiver can distinguish
Flow and Error Control

Flow control + Error control = Data link control

Flow control

The flow of data must not be allowed to overwhelm the
receiver. How is it possible for the receiver to be
overwhelmed? (Limited processing speed, limited buffers)

How much data to send before waiting for an
acknowledgement?

If too much data: please send fewer frames or stop

Flow control: a set of procedures used to restrict the amount
of data that the sender can send before waiting for ACK.
(Remember, network congestion and congestion control are
Flow and Error Control

Error control

Error control = error detection + error correction

If error, please retransmit frame: this is called ARQ
(Automatic Repeat Request)
Flow and Error Control Protocols


Remember: The data-link layer is bidirectional.
Efficiency is improved by “piggybacking” ACKs
onto dataframes in real-world protocols.
Noiseless Channels: no frames are lost,
duplicated or corrupted. No need for error
control for this (theoretical) channel

“Simplest protocol”

Receiver has infinite processing speed, so no need
of flow control
Protocols: Simplest protocol

Network layer sends data to data link layer at
sender

Data link layer makes a frame and sends it

Data link layer at receiver receives a frame,
extracts data and provides to network layer

Both sender and receiver processes are event
driven at the data link layer. This means they
continuously wait for data to arrive from the
Protocols: Stop and wait (for
noiseless channels)

Incorporates flow control

Receiver may be overwhelmed if data frames
arrive at the receiver (possibly from multiple
sources) faster than they can be processed

Transmission is still event-driven (from the
network layer), but an additional Boolean flag is
checked. The Boolean flag is true only if the last
ACK arrived and we are clear to send.
Protocols: Noisy channels


Errors now occur. Either ignore errors, or use
error control
Stop and Wait Automatic Repeat Request
(ARQ):

Redundancy bits are added at the transmitter side
to the data frame

These redundancy bits can help detect errors

If an error is detected in a frame, the receiver
discards the frame and does not send ACK

Lost frames: cause received frames to be out of
Noisy Channels: Stop and Wait
ARQ

No ACK: Receiver retransmits

ACKs also contain redundancy bits for error
detection

ACKs also contain “sequence number” field for
tracking which frame the ACK corresponds to

Sequence number frame also added to
transmitted data. This detects lost frames at the
receiver. Remember, the data link layer expects
Choosing Sequence Numbers

3 possibilities:

Frame x arrives safe and sound; ACK transmitted by
receiver; Transmitter sends next frame, numbered x+1

Frame x arrives safe and sound; ACK transmitted by
receiver; ACK lost on channel. Transmitter times out and
sends frame x again

Frame x never arrives at receiver. Transmitter times out,
sends x again.

So only 2 consecutive frame numbers need to be
tracked at the receiver. Hence we use 1 bit, alternately 1
and 0, to represent the sequence number
Stop and Wait ARQ: Sequence
Numbers


Suppose 2 duplicate sequence number frames
arrive at the receiver. An ACK is still sent. Why?
(Because receiver reasons that previous ACK
may have been lost).
Stop and Wait ARQ is an inefficient use of the
channel (Why? Because no pipelining)

A problem about Stop and Wait ARQ:
Bandwidth = 1 Mbps, 1 bit takes 20 ms for a
round trip. If the system data frames are 1000
bits, what is the utilization percentage of the
Stop and Wait ARQ

Bandwidth: The supported data rate (in Mbps)

Delay: the round trip time of a bit

Bandwidth-delay product: How much data is in
the channel in a given time-slice (delay time)

If we send many frames before waiting for an
acknowledgement, the channel utilization goes
up (eg send 15 frames, then wait for ACK)
Sliding window protocols


Sliding window protocols are a feature of packet-based
data transmission protocols. They are used when reliable
in-order delivery of packets are required, such as in the
datalink layer (frames) and TCP layer (packets) of the
protocol stack.
Why do we use sliding windows: We add a sequence
number to the frame/packet. Now the sequence number
increases unboundedly as the amount of data sent
increases. We use sliding windows to limit the range of the
sequence numbers dealt with. So with sliding windows an
unlimited number of frames (packets) can be transmitted
using fixed-size sequence numbers.
Go Back N Automatic Repeat
Request


Several data frames can be in transition while waiting for
acknowledgements. (why? In order to keep the channel
busy while waiting for an acknowledgement)
Sender needs to keep copies of several transmitted frames
in case it needs to retransmit. (why? Because suppose 10
frames are transmitted at one go and the 5th is dropped.
Sender comes to know about this only after the 10th frame
has been sent. So needs to be able to retransmit in a
larger range)

Sliding windows: Each frame(datalink)/packet(transport) is
assigned a sequence number to track its position in the
stream. As data flows, the sequence number increases.
Go-Back-N ARQ: Sliding windows


To allow to transmit an unlimited amount of
data, with a fixed-size sequence number, a
“sliding window” is used to limit the frames in
transit at any time.
Sliding window: tracks the range of sequence
numbers that are of concern to the transmitter
and receiver.
Sliding Windows in Go-Back-N ARQ


At the tx: the sliding window tracks which frames have been
ACKnowledged, which frames have been sent but not
ACKnowledged, which frames are yet to arrive from the network layer,
and which frames cannot be sent in the current window (see fig on
page 325)
Send window size N: The sender must not transmit too fast. N should
be bounded by receivers ability to process frames. N must be smaller
than the number of sequence numbers so that retransmission is
unambiguous. N should hopefully be large enough so that amount of
data txed at one time exceeds the bandwidth-delay product, to ensure
optimal channel utilization.

Send window slides to the right when ACK arrives; can slide by more
than one slot.

Receive window: of size 1, since the receiver receives one at a time
Sliding Windows in Go-Back-N ARQ

Receive window divides the frame sequence numbers like
this: Frames already received + Next frame expected +
Frames that cannot be received yet

Slides to the right by 1 when the correct frame has arrived

Timers: In Stop and Wait ARQ, there was a retransmission
timer for every frame. Here, there is a timer attached to
every sent frame, but if one expires, all outstanding frames
are resent. Why? Because receiver has a window only of
size 1, cannot store and reorder frames. Hence all
outstanding frames (from the dropped frame onwards)
must be retransmitted.
Go-Back-N ARQ


ACKnowledgements: Sent by receiver only if the
correct frame is received. No ACK if the frame is
damaged or out of order.
Resending a frame: since many queued frames
are retransmitted in the case of a timeout, this
protocol is called “Go Back N”.

For sliding-window protocols to utilize the
channel effectively, the amount of data
transmitted before an ACK is expected must
exceed the bandwidth-delay product. If not, the
Go-Back-N ARQ vs Stop and Wait
ARQ

Stop and Wait ARQ: send window size = 1

Stop and wait ARQ: Sequence numbers modulo
2^m where m=1

So Stop and Wait ARQ is a special case of Go-
Back-N ARQ
Selective Repeat ARQ


Go-Back-N ARQ: advantages: improves
channel utilization, no need of reordering out of
order frames at the receiver, but this is very
inefficient for a noisy link
It is not sensible to send multiple frames when
just one is damaged/lost. However, to
incorporate this increases receiver complexity
(why?)
Selective Repeat ARQ

Does not retransmit multiple frames. More
efficient, but more complex receiver.

Uses 2 windows: send and receive

Send window maximum size = 2^(m-1) (smaller
maximum size means less efficiency filling the
pipe)

Receive window: also of size 2^(m-1). Receive
window size is increased so we can store out of
Selective Repeat ARQ: Receiver


All frames in the receive window must arrive before
delivery to the network layer is possible
2 signals are used by the receiver: ACK and NAK
(Negative ACKnowledgement – to reject or indicate a
problem with a previously transmitted message)

If the received frame is not corrupted and within the receive
window, we store the frame and mark the slot.

If contiguous frames starting from Rn have been marked,
data is delivered to the network layer and the window
slides to the right. An ACK is delivered in one shot for all
Selective Repeat ARQ: Receiver


If the receiver gets an out-of-order frame (i.e. An
intermediate frame is lost) then it sends NAKn
where n is the frame number that was lost.
What happens if the NAK is lost? Then the final
ACK is never received by the transmitter, which
is forced to resend all frames.
Multiple NAKs are not sent for a missing frame.
This is to conserve bandwidth.
Selective Repeat ARQ: Transmitter

Sends frames in send window

Waits for ACK or NAK from receiver

Each frame has a retransmission timeout

ACK: Acknowledges multiple frames

NAK: Indicates which frame was lost at the
receiver.

On receiving ACK for everything in the send
window, the window slides to the right.
Selective Repeat ARQ: Window
Size

To understand the limitations on the size of the
windows: Suppose all ACKs are destroyed.
Then the transmitter times out and retransmits
everything. However, the receiver window has
moved by more than 2^(m-1) and hence it is
possible to see some overlap with the
transmitter data (which is old, but which the
receiver thinks is new). This is preventable by
constraining the receive window size, and
hence the transmit window size.
HDLC

HDLC = Highlevel Datalink Control

Bit-oriented protocol for communication over
point to point and multipoint links

Implements ARQ

2 transfer modes provided: NRM (Normal
Response Mode) and ABM (Asynchronous
Balanced Mode)

NRM: A txs, B responds to A's commands/data
HDLC


ABM: The configuration is balanced. Each node
can function as primary or secondary
Asynchronous: B doesn't wait for command to
send its frames.

ABM: Command/Response piggybacked at A
and B
Framing in HDLC


3 different types of frames:

I frames (information frames)

S frames (supervisory frames)

U frames (unnumbered frames)
Frame formats: Flag + Address + Control +
Information + FCS + Flag

Flag can be repeated between frames
Framing in HDLC

Flag = 01111110

Address: Destination (primary) or Source
(secondary) address

Control field: Used for flow and error control; 1-2
bytes

Information field: Contains user data from N/W
layer or management information (link layer)

FCS: 2 byte CRC checksum
Control Field

Control Field for I-frames

Starts with “0”. Contains N(S) = sequence no of
frame, N(R) = ACK no when piggybacking is used

Control Field for S-frames

S = supervisory

Used for flow and error control when piggybacking
not possible (eg when node B runs out of data)

S frame does not contain “User information” field

First 2 bits: “10”. 2 bit Code + N(R) (ACK no)
Control Field

2 bit code in S-frame: RR, RNR, REJ, SREJ

RR = Receive ready at B

RNR = not ready to receive at B

REJ = NAK tailored for Go-Back-N flow control
(so we don't have to wait for timer expiry at tx)

SREJ = NAK tailored for Selective Repeat ARQ
Control Field

U-frames (unnumbered):

Used to exchange session management and control
information between connected devices

Do not carry user data

Code field is 5 bits wide, so 32 different types of Uframes eg SNRM (Set normal response mode), UA
(Unnumbered ACK), SABM (Set Asynchronous
Balanced Mode), DISC (Disconnect), RSET (Reset),
etc
HDLC Examples


Connection/Disconnection: Use SABM UFrame. This sets up data transfer. After transfer,
A sends DISC (disconnect) U-frame. B
acknowledges with UA (Unnumbered ACK)
Piggybacking without error: A sends 2 I-frames
0 and 1. B piggybacks ACK of both frames into
an I frame of its own. B's ACK no in its sent Iframe is 2, since it expects frame 2. Now A has
sent all data, so cannot send an I frame. Sends
S frame instead, with RR code inside.
Multiple Access


Sometimes we have a dedicated link between
nodes A and B eg in a dialup network
connection
Sometimes we don't and the link is shared eg in
cellphone networks, the channel is shared. Also
wireless networks, since we deal with an
inherently broadcast medium

Data link layer handles datalink control (framing,
flow control, error control) and multiple access
Multiple Access


So data link layer = Data link control + Multiple
access resolution
Data link control = “Logical link layer” according
to IEEE. And Multiple Acccess resolution is
handled by MAC layer (“Medium Access
Control”)

Multiple nodes, common link – called a
multipoint link
Multiple Access


Multiple Access Protocols: Random Access
Protocols (ALOHA, CSMA, CSMA/CD,
CSMA/CA), Controlled Access Protocols
(Reservation, Polling, Token Passing),
Channelization Protocols (FDMA, TDMA,
CDMA)
The most commonsense ways of sharing the
link: TDMA (disadvantage is low channel
utilization for heterogenous traffic), FDMA (low
channel utilization for bursty traffic)
Random Access


Democratic protocol. All nodes are equal. No
node controls another node's right to transmit.
Why “random” access – no preallocated time for
access. Stations compete with each other for
access. Hence called contention methods.

Collision: a medium access conflict, 2 nodes
transmitting at the same time. We want to
minimize conflict.
Random Access: Pure ALOHA


ALOHA: first multiple access system, developed in
University of Hawaii in 1970.
ALOHA is no longer used, but one of its core concepts is
still used in Ethernet. Designed for radio LAN, but can be
used for any shared medium.

Pure ALOHA: Station sends frame when it has a frame to
send. Collisions may occur with frames from different
station(s). If even 1 bit of 2 frames overlaps, both frames
are lost.

Pure ALOHA is also called “statistical multiplexing”. Avoids
the resource wastage of TDMA and FDMA systems when
Random Access: Pure ALOHA


Lost frames need to be resent. A lost frame is resent
using an ACK-based ARQ: If the receiver's ACK does
not arrive at tx, retransmit after a time-out at the
transmitter.
If the timeout is the same for all stations, re-collision is
very likely to occur.

So in Pure ALOHA, we wait for a timeout + a random
time period called the backoff time TB

If this again collides, tx tries again. Tries only a finite
number of times, Kmax (maximum number of
retransmission attempts) so as not to block the
Random Access: Pure ALOHA


Setting the timeout: It takes 1 RTT for the ACK
to reach the tx again. So take maximum RTT
between pairs of nodes to set the timeout.
Remember the ACKs can also be dropped
(including due to collision) but there is no such
thing as ARQ for ACKs.
RTT(max) = 2*Tp, where Tp is the maximal
separation time between 2 stations.
Pure ALOHA: Tx algorithm (Binary
Exponential Backoff)

Variables: K = no of attempts, Tp = maximum frame propagation time.
Tfr = average frame transmission time. We can use either Tp or Tfr to
calculate backoff, depending on system conditions

1. Start

2. K=0 (K is the number of attempts)

3. Send frame

4. Wait RTT(max) (timeout value)

5. If ACK rxed by now, we have successfully txed. End.

ACK not rxed: Increment K and if K<=Kmax then wait TB (TB =
R*Tp[conservative] or R*Tfr) where R is a random number between 0
and 2^K-1 (this increases the backoff progressively and
exponentially). If K>Kmax then give up and end.
Problem on Pure ALOHA


Stations separated by 600 km. Tp = 2 ms, the
propagation time between stations.
Now we calculate the backoff value:

Attempt 1: K=1. Choose random no in {0, 1}. TB is 0
ms or 2 ms

Attempt 2: K=2. Choose random number in
{0,1,2,3}. TB is correspondingly 0, 2, 4, 6 ms

Attempt 3: K=3. {0..7}. T_B is {0 ms, 2 ms,..14 ms}

K_max=10, for example.
Pure ALOHA: Vulnerable Time


Vulnerable time is the time period within which
there is a possibility of collision (assume all
frames are the same size)
Vulnerable time = 2*Tframe where Tframe=frame
transmission time.

If any other frame is transmitted within the
vulnerable time around a frame, the frame will
be dropped. (See fig 12.5 on page 367)
A problem on vulnerable time


Shared channel B/W = 200 kbps. Frame size =
200 bits. No txs within 2* 200 bits/200 *10^3 bps
=
2*10^-3 ms around a frame for error free
transmission.
Pure ALOHA: Throughput


Throughput is the number of good
transmissions/second. Depends on vulnerable
time and frame generation rate
Calculations: Say the frame generation rate is G
per Tframe. Say one particular node transmits,
and the rest of the nodes number N-1 (large).
These nodes need to generate no frames within
the vulnerable period Tvul, or else there will be
collision
Pure ALOHA: Throughput


Probability of this: is governed by a Poisson
distribution (N large), but we approximate and
derive from the binomial distribution
If N nodes, probability of channel being free=
(1-p)^(N-1).(1-p)^(N-1)

This is the compound event: 1 station transmits,
and for two framing periods, the other stations
do not transmit.

Here p = G/N as each node shares the load.
Pure ALOHA: Throughput

Take the limit of the formula as N->Infinity to get

Probability of succesful transmission = e^-2G

Throughput = G.e^-2G

This has a maximum at G=0.5, with a
throughput of about 18%
Problem on Pure ALOHA

BW = 200kbps

Frame size = 200 bits

Find throughput if all nodes together generate
{1000, 500, 250} frames per second.

Ans: Just use the formula Ge^-2G
Random Access: Slotted ALOHA

Now time is divided into slots of Tframe.

We transmit only at the beginning of the
synchronized time slots.

Vulnerable time is half as much, so peak
throughput goes up to 36% (maximize Ge^-G)
CSMA

Carrier Sense Multiple Access

“sense before transmit” - “listen before talk”

Possibility of collision reduced, but still possible
– if station transmits within a propagation time
of another station

Vulnerable time: the time period within which
there is a collision, = Tp, the propagation time

Look at Fig 12.9 to understand vulnerable time
CSMA: Persistance methods


1 – persistant: As soon as channel is free,
transmit
Nonpersistant: If channel free, send
immediately. If channel not free, wait a random
amount of time and re-sense. Advantages:
reduces the chance of collision within Tp.
Disadvantages: Reduces the channel utilization
during the wait period.

p-Persistant: Use a slotted approach, slot
duration should obviously exceed T ,
CSMA: Persistance methods

Just like slotted ALOHA improves efficiency, a
slotted approach improves efficiency here. So,
collision probability is reduced, and efficiency is
improved.

If line idle, station sends with probability p

With probability 1-p, we wait for the next time
slot

Check the line again – if the line is idle, go to
step 1

If line busy, then backoff
CSMA/CD


CSMA/CD = Carrier Sense Multiple Access with
Collision Detection
CSMA: No procedure specified following a
collision (no ACK-based ARQ specified, for
example)

Look at Fig 12.12 for the timing details of a
collision

In CSMA/CD, transmission and collision
CSMA/CD

Suppose node A's frame collides with node C's
frame. Once they detect the collision, both A
and C stop transmission immediately

A----B----C----D

A tx at t1, reaches C at t3

C senses and tx at t2<t3, as A's frame has not
yet reached C

C's frame reaches A at t4, obviously>t3 as C
starts transmitting later than A
CSMA/CD


At t4, C's bits reach A and A aborts
transmission. So both frames lost.
Actual collision occurs somewhere between A
and C, before either A or C detect the collision

Look at Fig 12.13: this figure includes the
partial-frames (not just the first bit).
CSMA/CD

Minimum Frame Size

Remember, collision detection is performed only so
long as the frame is being transmitted from node A.

As soon as the frame is completely transmitted, no
CD is possible at the transmitter anymore.

However, collision could occur anywhere enroute
from source to destination

So the frame size must be controlled: we must be
able to detect the collision before the last bit is
transmitted in order to correctly determine that a
CSMA/CD: Frame Size Limitations

So Tfr>2Tp

Justification: suppose node B transmits to A,
takes Tp to reach A. Takes another Tp for worst
case collision (collision at A) to reach B again.
Hence Tfr>2Tp. Write a timing diagram to clarify
this.

Collision detection is by monitoring energy level:
zero level, normal level and abnormal level (2ce
as much energy in channel)
CSMA/CD

Problem:

BW=10 Mbps, Tp=25.6 uS, Tfr(min)=?

Ans: 64 bytes
CSMA/CD: Algorithm

1. K=0 (K is no of tx attempts)

2. Apply persistance method (1-persistant, p-persistant or
nonpersistant)

3. (Tx loop) Transmission done, or collision detected? Go to
step 6

4. Transmit/receive

5. Go to step 3

6. If no collision was detected, done.

7. (Collision process) Send jamming signal

8. K=K+1
CSMA/CA

CSMA/CA: Used for wireless networks

CSMA/CD: We receive while transmitting to detect
collisions. The energy level of the sensed signal
determines if a collision has occured.

In a wired network, because of repeaters and short length,
the received signal energy is just about the same as the
txed signal energy. So CD is possible.

However, in wireless networks, signal energy drops rapidly
with distance. So we can't do CD effectively
CSMA/CA

Look at Fig 12.16 for the timing in CSMA/CA

So we need to avoid collisions on wireless networks, since
collision detection is not possible. We can still detect when
the channel is busy though (when not txing)

We use CA (Collision Avoidance) for this. CA works using:
IFS, contention window, ACKnowledgements. CSMA/CA
used in 802.11

IFS = Interframe space. We allow distant signals to
propagate (effectively we wait at least Tp(max)) so that we
can avoid collisions due to transmission at node without
having sensed distant incoming signal (this is the
CSMA/CA


If a station has lower IFS, it has higher priority in
transmission. Setting IFS too low may result in many
collisions.
After waiting out the IFS, and if the channel is still idle, we
wait an additional “contention period”. This is to be
effectively “less greedy” than CSMA and hopefully avoid
more collisions.

The contention time is slotted, choose a random number of
slots as wait time. The number of slots in the window
changes according to binary exponential backoff. If the
ACK doesn't come through, the window size is increased
exponentially for the retransmit
CSMA/CA


Remember that the channel could become busy
while waiting to tx. In this case, it is unfair if a
node has to restart its timer. So, just stop the
timer and continue when the channel becomes
idle (the IFS is more or less guaranteed by the
remaining waiting time)
To detect dropped frames, we use positive
ACKs and retransmission timers

CSMA/CA in wireless networks incorporates
CSMA/CA

Algorithm:

1. Set K=0

2. Channel Idle? If not, go to 2

3. Wait IFS

4. Channel still idle? If not, go to 2

5. Choose R in {0..2^K-1} randomly

6. Wait R slots. Remember, pause sending until channel
free (without resetting timer) if channel becomes busy

7. Transmit frame

8. Wait timeout.
Controlled Access

Controlled Access: Stations send only after authorization by all
other stations

Reservation, Polling, Token Passing

Reservation:

Reservation is a slotted system

A reservation frame is reserved after every round of data
transmission

The reservation frame contains slots, corresponding to the
stations 1..N

If station i wants to transmit in the next round, it indicates this
by filling up its slot in the reservation frame.

The data frames are then sent in order of priority once the

Polling
Controlled Access

One device called primary device

All other devices called secondary

Primary controls all transmissions on the network segment

2 types of signal sent: Poll and Select

Select: primary wants to transmit. Notifies desired secondary
of its desire to transmit by sending a SEL frame. This should
be ACKed by the secondary. SEL frame obviously contains
address of secondary. SEL notifies secondary that it has to
receive and ACK ensures receiver is ready.

Poll: primary polls each secondary node for data. Secondary
replies with NAK (no data) or with data if present. Data
Test problem

Some suggested polling to counteract the
hidden node problem in wireless networks. This
is correct and in fact has been studied in
research literature - “Poll before data multiple
access” - by Asimakis Tzamaloukas and J.J.
Garcia-Luna-Aceves from UC Santa Cruz.
Search on Google if you want to read this
paper.
Controlled Access: Token Passing

Token Passing

Stations are organised in a logical ring. There is a
predecessor and successor for every station

A special frame called the token circulates through the
ring. Only the station that last received the token (and
has not passed it on yet) has the right to transmit. Holds
on to token as long as there is data to transmit.

A station cannot send data until it receives the token

(Token passing implements “round robin” scheduling
and is conceptually identical to the way operating
Controlled Access: Token Passing


Token management

Stations hold token for a limited amount of time

Token should be monitored for loss

Token-holding time can also be used to set priorities
Logical rings

Can be made from physical ring, dual ring, bus ring
and star ring topologies (see Fig 12.20)
Token Passing: Logical Rings


Physical ring topology

Token only seen by immediate next station

If one link fails, the whole system fails
Dual ring topology

Second ring present in opposite direction

This auxiliary ring is only used for backup purposes.
If a link fails, a temporary ring is formed using both
main and auxiliary ring

High speed token networks use this – FDDI, CDDI
Token Rings: Logical Rings


Bus Ring topology: although the physical
topology is a bus, every node knows the
physical address of its successor. So a logical
ring topology can be implemented to control
access to the shared medium. Used in IEEE
Token Bus
Star Ring topology: physically, star topology.
Failure here is not catastrophic. Adding and
removing nodes is easier. Used in IBM Token
Ring LAN
Channelization

Available channel bandwidth is shared through time, frequency
or code

3 protocols are: FDMA, TDMA and CDMA

FDMA

Available bandwidth divided into bands, each band reserved
for a particular station

Guard bands are present for each station (its not really
possible to strictly bandlimit signals)

FDM and FDMA are different! FDM uses multiplexer to mix
signals after modulation of baseband signals
Channelization

TDMA: Time Division Multiple Access

Time is slotted, each station uses a preallocated slot

Synchronization between different stations needs to be tight.
This may be difficult given propagation time across the
physical layer

Synchronization is achieved by adding synchronization bits
(or preamble bits) at the begininning of each time slot

Guard times are introduced to counteract propagation delay

ISI is a big problem too

Used in mobile systems – GSM uses TDMA + frequency
hopping. TDMA on GSM phones creates “buzz” at frequency
Channelization

CDMA: Code Division Multiple Access

Each channel occupies the whole bandwidth
(frequency spectrum) of the link

Why is collision an issue in random access but not
in controlled access or channelization?

Each station is assigned a spreading code that
greatly increases the bandwidth of the actual data
signal

Code division: like using different languages

Earliest application was GPS. The earliest idea for
Channelization: CDMA


CDMA: Each channel simultaneously occupies
entire bandwidth. So not like FDMA. Also no
timesharing so not like TDMA.
CDMA: Spreading achieved by coding. Each
station is assigned a code – a sequence of
numbers called chips. So a code is a chip
sequence.

Eg: [1 1 1 1], [1 -1 1 -1], [1 1 -1 -1], [1 -1 -1 1]
CDMA


These chip sequences are not randomly
chosen. All are of same length.
Properties:

Each chip sequence has N elements, where N is
the number of stations.

These chip sequences behave like vectors. Use the
usual inner product on the vectors

So: sequences are orthonormal under the usual
inner product
CDMA

Encoding: 0 --> -1, 1-->+1

What are the intuitive explanations for sequence
addition, inner product etc?
Review questions

Do we need MAC for the following cases:

Dialup modem connection (data tx over local loop)

Internet access over one CATV channel

Ex problem 11

Ex problem 15
CDMA

Code Division Multiple Access

One channel occupies bandwidth of entire link,
unlike FDMA

Nodes can transmit all the time, unlike TDMA

Channelization is achieved by coding (assigning
orthogonal spreading codes to various
channels)
CDMA

Code = Sequence of numbers called chips

Eg: c1 = [1 1 1 1], c2 = [1 -1 1 -1], c3 =[1 1 -1 -
1], c4 = [1 -1 -1 1]. Each code is called a chip

Each sequence is made of N elements, where
N is the number of stations

Use usual scalar multiplication

Use inner product to multiply sequences. This
finds correlation of sequences
CDMA

Inner poduct of 2 different sequences =0

Inner product of a sequence with itself = 4

Data bit 0 --> +1

Data bit 1 --> -1

Silence --> 0 ?Use BPSK modulation?

What is +1 + -1 ??
CDMA

Encoding and decoding:

Example: 1 sends -1, 2 sends -1, 3 silent, 4 sends
+1

Each number is multiplied by its chip and sent onto
the channel where the signals are linearly combined

Eg: (-1 -1 0 1)* A where
A=

{[1 1 1 1], [1 -1 1 -1], [1 1 -1 -1], [1 -1 -1 1]} a 4x4 matrix
This gives the output signal: [-1 -1 -3 1]
CDMA


Remember the actual modulation scheme used
has to support this sort of linear addition. So
BPSK could be used for eg but not 8 PSK.
BPSK for {0,1} is same as ASK for {+1, -1}.
16 QAM could not be used for example.
Decoding at station

Take inner product with stations spreading code

This is correlation and returns the signal energy
for a perfect match

Walsh tables: see page 389
Connecting Devices (placeholder)

Passive hub – below physical

Repeater or Active Hub (Physical)

Bridge (Data link) – generates tables of
destination addresses reachable

Router (Network)

Gateway (Application)
Things to cover

CDMA in matrix format

Alternatives to CDMA
Connecting LANs, Backbone
Networks and Virtual LANs

Connecting devices

A

T

N
Router or three layer switch

DL
Bridge or two-layer switch

P
Repeater or hub
Gateway

A
Passive hub

Collision domain: the regions in which collision can occur

Broadcast domain: the region accesible by broadcast at
layer 2
Connecting Devices

What each of these means

Passive hub: Just a connector between devices. Eg
Star-topology Ethernet LAN

Repeater

Operates only in the physical layer

As signals propagate, they attenuate

Repeaters at the physical layer regenerate the bit pattern
as it is transmitted

Repeaters can extend the physical length of the LAN

Repeater cannot connect two LANs of different protocols
Connecting Devices

Repeaters (physical)

Does not connect 2 separate LANs; just connects 2
segments of the same LAN

Repeaters cannot connect two different LANs of
different protocols (no processing of frames)

A repeater is a 2-port node on a LAN segment.
Forwards any frames it receives to the output port
and the other LAN segment

Diagram: 2 LAN segments connected by level 1
Connecting Devices


Repeater is not amplifier. Explain this. Repeater
regenerates signal within certain noise margin
Active Hub: multiport repeater. Used in star
topology on Ethernet. Hub diagram: page 448

Bridge: used in physical and datalink layer

Physical layer: regenerates signals

Datalink layer: examines source and destination
addresses in the frame

Drops erroneous, badly formed frames

Bridges

Connecting Devices
Bridges are able to filter. Checks destination
address to decide whether to forward or drop a
frame. Bridges are not routers! Bridges operate by
flooding, not by actually locating the destination
node within the target LAN segment. Hence their
utility is limited to Local Area Networks

Bridge has multiple output ports; contains a table
that decides which port to forward the frame to

Bridge can be used to connect two LANs, or 2 LAN
segments
Connecting Devices

Bridge does not change MAC addresses in a frame

Transparent Bridge: (mostly used in Ethernet)

Called a transparent bridge because it has no physical addresses.
Just accepts and forwards frames as though it wasnt there. Uses:
Qos, traffic shaping, filtering, security, etc. Simple to make a
network bridge too – use a computer with 2 NIC cards _
bridgeutils under Debian Linux

Nodes (stations) on a LAN are completely unaware of the bridge's
existence

Reconfiguration is unnecessary if a bridge is added/removed (?)

Transparent bridge:
 Frames
must be forwarded from one station to another
 Fowarding
must be automatically learned
Connecting Devices

Transparent Bridges: Isolates collision domains while connecting network
segments (and therefore intelligently extending the broadcast domain)

Forward frames correctly

Forwarding tables:



Static – disadvantages?

Source addresses used to build forwarding table
Loop problem
Transparent bridges can theoretically be used to bridge between
incompatible LAN types. This is an area of ongoing research:

“Transparent interconnection of incompatible local area networks using
bridges” - IEEEXplore. Cisco has an interesting article at:

http://www.cisco.com/en/US/docs/internetworking/technology/handbook/Mixe
d-Media-Bridging.html
Connecting Devices


Learning: by flooding and examination of source
address. Examing destination address provides
no information on location of destination node!
Draw a diagram for learning: 3 LANs connected
by a network bridge, whose tables are initially
empty (page 450)
Bridges

Loop problem: page 450

Loop problem is avoided by setting up a
loopless logical topology on top of the physical
topology

This is achieved using the spanning tree
protocol
Spanning Tree protocol


In graph theory, a spanning tree is a graph in
which there is no loop. Every LAN (segment)
can be reached from another LAN (segment)
through one path only.
Physical topology cannot be changed, but a
logical loopless topology can be overlaid on this
physical topology by intelligently blocking bridge
ports.
Spanning Tree protocol


Draw a diagram of multiple connected LANs
and the bridges connecting them. Represent
LANs and bridges both as nodes (there are
many possible approaches to implementation of
spanning tree)
Can also show LAN as node and bridge as
connector

We need a cost associated with each
component of the path (connector between LAN
Spanning Tree Protocol


The cost can be anything: minimum hops,
minimum delay, max bandwidth etc
Choose by priority when 2 bridge ports tie in
this metric in distance from root node. Or
choose randomly

In the textbook: distance or hop count = +1 from
bridge to LAN, 0 from LAN to bridge (this counts
the number of rebroadcasts a frame would need
as it propagates through the network)
Spanning Tree Protocol

Find the spanning tree like this:

Choose root bridge by priority on MAC address or
built in ID address (choose lowest, for example)

The algorithm is a distributed algorithm that runs on
all bridges at the same time

The shortest path is found from the root bridge to
every other bridge. This is the path that will be used
for routing to target LAN

Shortest paths: form shortest tree
Spanning Tree Protocol


Bridges keep communicating with each other at
periodic intervals (usually 2s for Ethernet
switches). This allows the spanning tree to be
changed in case of bridge outage
Bridges communicate using special frames
called BPDUs (Bridge protocol data units)
Source Routing Bridges


When redundant bridges are present, source
routing is used
Frame contains addresses of bidges that the
frame must visit

Bridge addresses obtained by special frames by
node

Interconnection of different LANs: Frame
format, max data size, data rate, bit order,
Routers

3 layer device. A layer 3 switch

Connects LANs and WANs on the internet

Three-layer switch = fast and sophisticated
router that can handle thousands of
connections with fast lookup

Gateway: 5 layer switch. My wireless ADSL
modem is also a gateway from my home
network to the internet
Backbone netwoks


A LAN that connects LANs together through
bridges
Bus backbone – LANs connected through
bridges

Star backbone – LANs connected through a
multiport switch in star topology

Remote LANs may be connected over point-topoint connections like PPP or ADSL
Network Layer


Network layer communication: host-to-host
(between computers on the internet)
Global addressing scheme required for
communication between computers on
heterogenous network types

Logical address is a global address. Also called
IP address.

IP: Ipv4 or IPv6
IPv4 addresses


32 bit address. Uniquely and universally
identifies the connection of a device to the net
Unique. 2 different nodes on the internet can
never have the same IP address. This is
violated in very special cases as shown later

Routers with m connections to the net have m
internet addresses. ??Does this make sense?
IPv4


Address space: total number of addresses used
by the protocol. 2^32 in theory
Actual number of available addresses is much
less

We can write IP addresses in binary or dotted
notation.

Standard: do not write leading zeros in dotted
notation
IPv4 addressing

Classful addressing: Divide the address space
into classes

5 classes: A, B, C, D, E

First byte of each class:

A: 0xxxxxxx

B:10xxxxxx 2nd byte

C:110xxxxx 2nd byte 3rd byte

D:1110 + fill in all rest to find addresses in this block
IPv4 addressing

Class A: 128 blocks, 2^24 addresses within
each block

Class B: 64K blocks, block size = 64K

Class C: 2^21 blocks. 256 in each block

Class D: 1 block only Block size = 2^28
(multicast)

Class E: 1 block only Block size = 2^28
(reserved)
IPv4 addressing

Class A: large organisations

B: midsize organisations with tens of thousands
of attached hosts

C: small organisations

D: multicast addresses

E: reserved for future use
IPv4 addressing


Classful addressing: many addresses are
wasted
In A, B, C classes, the IP addresses may be
divided into netid and hostid

Netid: identifies group. Hostid: identifies node
within group

We can also use a mask (pattern of 1's and 0s)
to extract netID and hostid
Ipv4 addressing


Class A: 11111111 oooooooo oooooooo
oooooooo
Class B: 11111111 11111111 00000000
00000000 0000000

Class C: 11111111 11111111 111111111
000000000

We can write the address masks in dotted
decimal notation also
IPv4


Dotted decimal notation: 255.0.0.0,
255.255.0.0, 255.255.255.0
CIDR: Classless interdomain routing notation,
used in classless routing

CIDR: /8, /16, /24

Subnetting: if a large block of addresses was
granted to an organisation, it could split this into
smaller blocks called subnets
IPv4


?subnetting increases the number of 1s in the
mask
Supernetting:

A time came when A and B addresses were
depleted. Class C blocks were combined to make
larger range of addresses

?Supernetting decreases the number of 1s in the
mask? How is this?

/24 --> /22
IPv4


Classful addressing is obsolete. Replaced with
classless addressing
IANA - IANA controls numbers for protocols, the
Country Code Top Level Domains and
maintains the IP Address allotments.
ipv4

Classless addressing: gets rid of the problems
of classful addressing

Ca 1993

Addresses are still granted in blocks to
organisations

Size of block varies based on nature and size of
entity
ipv4


Eg: single house only 2 addresses, organisation
1000s of addresses
Restriction: Block is made of contiguous
addresses, Number of addresses in block is a
power of 2, First address must be evenly
divisible by number of addresses (what does
this mean?)
ipv4


First address: convert to decimal and divide by
16, should leave no remainder. Controls
granularity – 16 addresses at a time
Classless addressing: mask -Mask is a 32 bit
number with left contiguous 1s and the rest 0.
Mask represented x.y.z.t/n n between 0 and 31

Address block completely specified by first
address and /n
ipv4

Number of addresses in block = 2^(32-n)

Network address:

First address in group nomally (not always) treated
as special address

This special address is called the network address
and defines the organisation network. Defines
organisation address to rest of the world

First address is the one used by routers to direct
information sent from outside
ipv4


Router connects organisation network to the
internet. Router has 2 network addresses: One
belongs to user network, one belongs to
network on the other side.
IP addresses have hierarchy, like phone
numbers (Area code, exchange, user id)
ipv4

2 level hierarchy: no subnetting

When no subnetting, only 2 levels of hierarchy

N bits: prefix – organisation ID. 32-n bits – suffix
– host address

3 levels of hierarchy – with subnetting

If organisation possesses large numbers of
addressing – divide into subnets
ipv4


Subnets: rest of the world sees only 1 network,
internally there are many smaller networks
All messages sent to router that connects
network to internet. Router redirects to
approporate subnet

Subnets specified my masks

Eg: suppose organisation has 17.12.40.0/26. 64
addresses available
ipv4


If we want to divide into subnets of 32, 16, 16
then masks are /27, /28, /28
More levels of hierarchy obviously possible –
like for ISPs

ICANN: Internet corporation for assigned
names and numbers – this

117.192.231.1
ipv4

Address depletion

Mobile devices, always on connections, more users
and networks, inefficient address use, virtualization
Ipv4

Examples of subnets etc

Example: organisation given the block
17.12.40.0/26 – this means 64 addresses for
the whole network

Split into subnets: 32+16+16. Subnets specified
by IP address/mask

If we want 3 subnets of size 32, 16 and 16, then
do the following
Ipv4

Want to divide the network into 3 subnets:

17.12.40.0/26 is the network. Divide into 3
subnets

Size 32: n1 = 27, n2 = 28, n3 = 28

Choose addresses as follows:
Network Address Translation (NAT)


Originally, most small businesses and individual
users used dial up connections. Connection
was for a specified period of time.
Now, always on ADSL or cable connections are
being used. Many IP addresses are required
per subscriber. With the shortage of addresses,
this is a serious problem.
NAT


Network Address Translation: large set of
addresses used internally to the network, but a
small set of addresses show up on the public
Internet.
IANA, ICANN provide three address spaces for
private networks.

10.0.0.0 to 10.255.255.255 - 2^24
NAT


172.16.0.0 to 172.31.255.255 – 2^20 addresses
– larger than class B by 4 times
192.168.0.0 to 192.168.255.255 – 2^16
addresses

Everyone knows that these addresses are for
provate use only (dropped by routers on the
Internet)
NAT


How a NAT works: hides many IP addresses
inside a network while displaying only one or a
few IP addresses to the public internet.
Diagram: draw router with two ports, router
shows some external address(es), some
internal addresses exist on the network from the
provate address space.
NAT


The NAT runs software to enable this hiding to
happen
So: all outgoing packets/datagrams have their
source address changed to the NAT address.

All incoming packets have their destination
addresses changed to the appropriate provate
address.
NAT

Obviously, address translation is not trivial: how
to correctly assign the private address to the
incoming packets with the NAT address as the
destination address? Replacing source address
for outgoing packets is of course easy. So, use
a table in the NAT router.
NAT


There are many ways to implement NAT, wach
has its limitation, so we use increasingly
sophisticated techniques to implement NAT.
First technique: NAT-enabled router displays
only 1 IP address externally. When a host on
the private network connects to a host on the
Internet, an entry is made in a table with private
source address and external destination
address
NAT


When return packet comes from host, then NAT
uses table to route to the correct node on the
private network.
This has some obvious limitations: 2 hosts
cannot connect to the same external host,
outside nodes cannot initiate communication –
so “push” email servers don't work for example.
NAT

Method 2: Use a pool of IP addresses. Now
what happens is the following: use for example
four global addresses for the NAT router. If 2
nodes connect to the same external host,
assign them different external IP addresses. But
now at most 4 hosts can connect to the same
external host, so still problem
NAT

NAT: Use both IP addresses and port numbers

Port number is used to indicate which node in
the private network the incoming packets
should be routed to.

Table now contains: Private address, private
port, external address, external port, transport
protocol (TCP or UDP). Basically make your
NAT smart by using layer 4 as well!!
Network Layer: Delivery,
Forwarding, Routing


IP: unreliable service: does not inform if failure.
Just “best effort”
Packet: any data formatted as a packet.
Datagram: formatted, framed data sent over an
unreliable service

What is connection oriented and
connectionless?
Delivery, Forwarding, Routing

Delivery:

Getting packets to their destination using the
underlying networks

Direct delivery: both source and destination are on
the same physical network

Indirect delivery: source and destination are on
different networks, connected by routers

Any delivery contains 1 direct delivery and the rest
are indirect deliveries
Delivery, Forwarding, Routing

Forwarding

Forwarding means sending across a packet or
datagram from hop to hop

Forwarding techniques:

Next hop method; complete route method

Remember, every hop (router) contains a routing
table to enable it to forward packets
Delivery, Forwarding, Routing


Network specific routing: just enter the network
address in the routing table
Host specific: enter the complete host address
in the table

Default routing: use default path and default
network address for routing
Delivery, Forwarding, Routing

Forwarding process:


How forwarding works:

Mask, network address, next hop, interface, ARP etc

Draw Fig 22.6 for a network
Address aggregation

Network mask indicates routing information. For
“subnetworks” we can aggregate routing
information

Aggregate networks with matching network prefix
Deliver, Forwarding, Routing

Even if one network appears to be a
“subnetwork” of another, they many not be
geographically colocated. Still, address
aggregation is possible using longest mask
matching. Put the longest mask first in the table
for the intermediate router
Delivery, Forwarding, Routing

Hierarchical Routing

To solve the problem of gigantic routing tables

Use hierarchical routing

Actual internet structure: International and national
ISPs, regional ISPs, local ISPs. - networks - subnet
Exploit this to reduce table size (refer wiki*)

Geogaphical routing – use huge IP address space
for large geographical areas (continents)
Delivery, Forwarding, Routing

Routing table

Static routing table

Dynamic routing table: populated by RIP, OSPF,
BGP. Done dynamically whenever there is a change
in network topology or connectivity.

Mask, nw address, next hop address, interface,
flags, reference count, use

Flags: U, G, H, D, M. U = Up, G = Gateway?, H =
Host specific, D, M – redirection specific information
Unicast Routing Protocols

Routing protocol: a combination of rules and addresses
that allows routers on the internet to inform each other of
changes. Dynamic routing protocols: RIP, OSPF, BGP

Which emerging path from the router is optimum?

Metric is defined. Compare satellite, fiber optic etc.

Intra and interdomain routing – because a single routing
protocol cannot update all routers on the internet
Unicast routing protocols


So whole net is divided into autonomous
systems. Domains are under the authority of a
single administration
What is the capability difference between inter
and intradomain routing protocols?

Distance vector, link state – these are
intradomain routing protocols. Path vector:
interdomain. Distance vector: RIP. Link state:
Unicast Routing Protocols


Routing protocols: a set of rules/procedures that
allows for routing/connectivity information to be
shared among the routers on the internet
Optimization: there may be several emerging
paths from a router node to the target network.
In today's internet, multipath routing is rarely
used. We need to choose the best path based
on locally available information so we use a
metric for emerging paths
Unicast Routing Protocols


The routing tables are populated by algorithms
such as OSPF, BGP, RIP (these are open
protocols) and some proprietary protocols.
Metric: minimum delay, maximum bandwidth,
least RTT, type of link, etc

Inter and intra domain routing: AS =
autonomous system – a subdivision (of
networks and routers) under the authoity of a
single administration.
Unicast Routing Protocols


Inside an AS: use one or more intradomain
routing protocols to set up the routing tables.
Information is exchanged between AS by
interdomain routing protocols.
Intradomain protocols: Distance vector, link
state. Interdomain: path vector.

RIP: distance vector. OSPF: link state protocol.
BGP: path vector protocol.
Unicast Routing Protocols

Distance Vector Routing

Least cost = minimum “distance”. What is
distance??

Distance vector. Vector = column or table of
distances to all reachable nodes. Also next hop
address is included.

??What is the difference between distance vector
and RIP?
Unicast Routing Protocols


Size of table = number of nodes (routers) in the
internet. Easy to fill up routing tables if we have
complete information on network topology. The
purpose of routing protocol is to disseminate
this information throughout the network
Initially, every node knows only its cost to
immediate neighbours.
Unicast Routing Protocols


In reality we may not even know the names (IP
addresses) of remote routers at the start. These
entries are assumed to be unfilled in the routing
tables.
At the beginning: fill up only cost to immediate
neighbours. Next, begin an automatic process
of distibution of this information through the
network.
Unicast Routing Protocols


Transmission between routers: only first 2
columns (target router, cost). Next hop is
intelligently assigned by the receiving node.
Cost is also intelligently updated. Write
algorithm for this.
Doubts: multiple IP addresses, so how to
address routers uniquely?
Unicast Routing Protocols


??How to analyze performance of distance
vector protocol?
When to update: periodic update, triggered
update

Instability in DV protocol: 2 node loop instability
Unicast Routing Protocol

2 node instability in the Distance Vector protocol

How does this happen? Very simple if we examine
a topology that contains 3 nodes, and one node
fails (page 663)

What are the effects of this – routing tables reflect
inaccurate data. It takes a long time for the whole
network to realize that a router has gone down. A lot
of packets are lost trying to get through routes that
are dead. These packets should have been
dropped right at the source.
Unicast Routing Protocols


Interesting question – what is the energy
inefficiency caused by router failure? - How long
does it take to propagate to the rest of the
system etc.
Now we understand the problem, and the
symptoms. What are the solutions? Redefine
infinity – this constrains network size, Split
horizon – this works as follows: don't send
routing table information to nodes which are the
next hop. Why is this called split horizon?
Unicast Routing Protocols

Split Horizon + Poison Reverse:

Split Horizon disadvantages: since routing tables are updates
dynamically, routing entries are killed after a timeout by the network layer
software. This means that wen split horizon is used, if we update without
including rows from nodes with path through destination node, then
destination node has no information if the route was lost completely or if
routing table infomation was lost only because of split horizon strategy.
??So what??

As it doesn't know, it doesnt know whether to delete its own route or not.
And the other question to ask is: when will the disabled router's status
ever propagate to the rest of the network? Why isnt this a problem with
distance vectoring without split horizon? So many questions to ask
Unicast Routing Protocols


To counteract this phenomenon, we include something
called poison reverse. As the name implies, it seems
to mean, spread information about disabled routes as
quickly as possible to the rest of the network. Basically
flood through the rest of the network.
We do this by advertising the distance as infinity from
the disabled node. This is reverse broadcast by A (the
receiver) as soon as it hears it, “reverse poison”
Unicast Routing Protocols

Three node systems: stability not guaranteed.

Beautiful 3 node instability problem – how to
analyze this?

X dies, A informs B and C, C's packet lost, so
instability if the flood fails to even one node.
Interesting!
Routing Information Protocol

Is an implementation of Distance Vector
protocol.

Uses hopcount as the routing metric

Infinity is set at 16 to pevent 2-node instability
problem to some extent. Maximum hop count
also prevents routing loops from occuring

Hop count of 16 is considered infinite distance
Routing Information Protocol

RIP: initial retransmit time was 30 seconds

This caused massive traffic bursts every 30
seconds.

It was thought that randomization of timer would
minimize this. But, not possible as it was shown that
even initially randomized times would eventually
converge. Why? Read this paper!!
Routing Information Protocol


even though RIP is a layer 3 protocol, it relies
on UDP for transport at port 530!! (Runs an
application level process as well).
In practise, destination addresses are network
addresses. This changes nothing in DV
protocol. Next hop is the IP address of the
router to which to send to.
DV and RIP

Can we do a performance analysis of DV and
RIP vs flooding? Think about this!!

RIP example

RIP – 1988. Superseded by more advanced DV
protocols like EIGRP (proprietary Cisco DV
protocol), OSPF, ISIS (linkstate protocols) that
show superior scalability and convergence
times.
RIP - example

Page 666 Fig 22.19. To construct this example:

Draw a topology of some routers connected by links.

Within the links, indicate the presence of networks by bars

Draw bars to indicate networks connected only to one router.

Assign network addresses. Assign router IP addresses
based on network addresses.

Populate routing tables. Routing tables are automatically
updated and contain: destination address, hopcount (cost or
metric) and next hop

Usual DV updating occurs.
DV and RIP


We saw various kinds of instability problems with plain DV. RIP prevents 3 node
instabilities by using a holddown timer (180 seconds). Prevents 2 node instabilities
using Split Horizon and Poison Reverse.
Counting to infinity --> Redefine infinity

Lower settling time --> Split horizon (do not readvertise through the same
interface that you got some routing information).

Route poisoning: flood unreachability information through the network. But this is
costly. Split horizon: prevent count to infinity by preventing old route data from
being resent. But routing loops could still be present.

To reduce the possibility of routing loops and reduce route convergence time,
split horizon with poison reverse is introduced. If B's route to X is through A, send
metric infinity when updating A. Reason: B says to A: never route through me.

Remember: just split horizon prevents 2 node problem but not 3 node problem.
DV

Three node instability

RIP: Routing information protocol
Link State Routing

Create the whole topology at each node.
Reading

Read “End – to End Routing Behaviour in the
Internet” for an interesting discussion of routing
pathologies.
Linkstate Routing

Drawbacks of DV routing:

Why LS routing:

LS: each router tells the world about its
neighbours. DV: Each router tells its neighbours
about the world.

LS: Apply Djikstra after recovering full network
topology
Unicast Routing Protocols


Intradomain Routing Protocol: Routing
Information Protocol.
Remember, the networks are the links in the
diagrams used in Furuozan!
Unicast Routing Protocols


OSPF: Open Shortest Path First – an
intradomain outing protocol based on link state
routing. Domain is an autonomous system
AS --> divided into areas: collection of
networks, hosts and routers all within an AS.

AS can be divided into many areas
Unicast Routing Protocols

Area is flooded with routing information

Border area routers summarize (routing)
information about an area at the boundaries of
an area and pass onto other areas.

Backbone: a special area within the AS to which
all other areas are connected

Routers inside backbone – called backbone
routers
Unicast Routing Protocols

Metric = cost of each route

OSPF: 4 types of links: point to point, transient,
stub and virtual

P2p – a single link with no hosts connects 2
routers

Transient – 1 network with several routers
attached
Unicast Routing Protocol

In transient topology, one of the routers is called
“designated router” but is also a true router.
Designated router handles all the “routing
between routers” during advertisement of link
state. Now each router has only one neighbour
– the designated router (which is taken to be
the network itself)

Stub link: network connected to only one router

Virtual link: a longer link created when a link is
broken
Unicast Routing Protocol

Path Vector Routing

Interdomain routing

One (in practise could be more) node in each AS
acts as spokesman for AS – called speaker node.
Advertises to speaker nodes in adjoining AS.


Speaker node advertises path, not metric. Why?

Is PV routing compatible with both DV and LS?
Sharing: Just like in DV, sharing is done with
other speaker nodes
Unicast Routing Protocols

Some more about PV routing protocol
Unicast Routing Protocols

Border Gateway Protocol

An interdomain routing protocol

Internet is divided into Autonomous Systems

Eg of AS: local ISP – etc – a collection of networks,
hosts and routers.

Types of AS: Stub AS (connected to only one
router), Multihomed AS (connected to several
routers but still acts only as source or sink – no
transient traffic allowed)
Unicast Routing Protocols - BGP


Transit AS: multhomed AS that allows transient
traffic. Eg national and international ISPs (these
are also called internet backbones).
BGP: returned information from speaker nodes
in AS contain all sorts of information that can be
used for policy routing – eg ORIGIN (which
protocol), PATH (what is the whole path), etc

Transport to BGP is provided via TCP and
semipermanent links are formed.
Multicast Routing Protocols


Unicast – destination is a single host. Multicast
– destination is multiple hosts. Broadcast –
destination is the whole network.
Unicasting – easy to understand. Router
forwards through only one of its interfaces

Multicasting – we can do this more efficiently
than repeated unicasting. Forwarding by a
router is through several interfaces
Multicast Routing protocols


There is a difference between multicasting and
multiple unicasting. Multiple unicasting – copies
of a packet (with different destination addr.) are
presented to all routers, including the first
router.
Why would we want multicasting routing
available?

What kinds of network applications would
generate multicast traffic?
Multicast Routing Protocols


We call the groups of intended destinations a
multicast “group”
We have to optimize routing (find shortest path
tree for every group of users). Is this more
optimal than using the unicast trees? Think
about this..

In multicast routing, each router needs to
construct a tree for each group to tell it to
forward on which interfaces
Source Based Trees in Multicast
Routing


Each router has a tree for each group. The tree
is a shortest path tree
It is assumed that the members of a group are
“loyal” - do not change with time (although
network conditions can change)

To understand this, draw a figure with multiple
networks, connecting routers, and groups.
Multicast Routing Protocols


2 approaches are available: source based trees
– this means every router on the network has
trees for every multicast group, and traffic
originating at any router is sent to all
destinations in the multicast group
Group shared tree: multicast traffic is
encapsulated into a unicast packet, and sent to
a special router called the rendezvous router or
core router that possesses multicast entries for
all groups
Multicast Routing Protocols

Now we understand how the routing tables
should look for multicasting. How are these
tables generated? They are generated by
multicast routing protocols – the problem is
much more involved than unicast routing
Multicast Routing Protocols

MRP--> Source Based Tree --> MOSPF,
DVMRP, PIM-DM

MRP--> Group Shared Tree --> PIM-SM, CBT

What are the advantages or disadvantages of
group shared trees to source based tree? Why
are these called so?
MOSPF

MOSPF: multicast link state routing

Unicast link state: acquire whole network
topology, apply Djikstra's algorithm to find
minimum spanning tree with node as root.
Unsuitable for multicast: why? No path
aggregation used? Discuss this..

In multicast link state – we use a source based
tree approach
MOSPF

How multicast link state routing works: In
addition to link costs, nodes also inform of
which groups have members present on those
links. This is taken into consideration when
building the tree. Simple to build the tree:
aggregate paths of all destinations(?) The way
Djikstra's algorithm works this should already
ensure an optimal multicast spanning tree is
generated. So extension of unicast to multicast
is straightforward
Multicast Routing Protocols


A real implementation of multicast linkstate routing is called
MOSPF (multicast open shortest path first). MOSPF not used
any more – deprecated by OSPFv3.
How MOSPF works: Now every group has an internet address
(as discussed in Ipv4). Every router sends a “LSA” - link state
advertisement reflecting various aspects of the network
topology. This includes which group addresses the host on the
network is connected to. When MOSPF makes its routing
calculations, it uses the usual host address.

MOSPF: data driven – generates the spanning tree only when it
sees the data for the first time.
Multicast Routing Protocols


DVMRP: Multicast Distance Vector Routing Protocol – an
implementation of multicast distance vectoring
Multicast much harder with Distance Vectoring than with LS.
Why? Multicast Routing Tables are not exchanged at all in this
approach. Why? Instead we locally generate multicast tables
using the unicast routing tables. Why?

So the multicast routing software goes through an algorithmic
process of deciding which interfaces to forward through

Flooding: costliest but easiest to implement. Eliminate loops by
retaining packets for a while
Multicast Routing Protocols


RPF: forward only if the reverse path is shortest path.
Discuss this in detail – we consider the unicast routing
table to do this.
RPB: Reverse Path Broadcasting – Multiple copies may
anyway be received as this is still a flood, albeit a slightly
intelligent one. Now: for every network, designate a parent
router (this can be decided upon), Forwarding into network
is only done by the attached parent router

Reverse Path Multicasting – Prune and Graft from leaf
networks control the routing policy of the parent routers.
Transport

Process to proces: process address is called
port number

IANA port numbers range: Well known <1024,
Registered –49151, Dynamic – any application
can bind to these ports

IP: unreliable
udp

Connectionless, unreliable transport protocol

Many services use udp. Many dont

Only network utilities use raw ip without
transport

Udp: dest port, length, checksum

??This should be header Checksum =
pseudoheader + udp header + data
udp

Look at example in fig 23.11 for udp checksum
calculation

Lack of flow and error control

Queueing – port unreachable message sent if
queue is not set up
tcp

Connection oriented, reliable transport protocol

Tcp – stream oriented protocol – stream of
bytes is sent; sending and receiving buffers ae
used to match speeds; use a circular array as a
buffer – this is hopefully the best way to buffer

Segmentation – done at transport layer –
segment can be any size within limits
tcp

Full duplex communication – traffic flows both
ways

2 numbers used – sequence number,
acknowledge number – refers to byte number
since tcp is byte oriented stream protocol

Numbering starts randomly to prevent spoofing
tcp

So segment contains sequence number field.
Value of the sequence number for first byte is
put in the tcp packet

Acknowledgement: cumulative ack is used. This
means acked upto currently received packet

Flow control: flow and error control is byte
oriented
tcp

Tcp: also does congestion control. If you want to
learn about this read the textbook

Tcp packet is called a segment: source port,
destination port, seq no, ack no, HLEN?,
Reserved?, window size, urgent pointer?,
options, padding,

ack+data can be piggybacked together
tcp

Tcp header contains flags in control field: URG:
urgent pointer valid, ACK: acknowledge no is
valid, PSH: “push the data?”, RST: reset the
connection, SYN: synchronize sequence
numbers, FIN: terminate the connection

Window size: size of receiving window. Which
protocol is used?
tcp

Checksum: same procedure as udp. (add all,
take 1s complement)

Urgent pointer: “urgent data” to be sent. Is used
only when urgent flag is set in control field. This
pointer is an offset that must be added to
current segment sequence number to get last
urgent byte. When could this be used?
tcp

Tcp connections: tcp is connection oriented.

Tcp: data transmitted in full duplex mode. This
needs 3 way handshaking

First step: passive open: server binds to port on
a local machine

Second step: Active open: client binds to this
open port on the server
tcp

Active open: involves 3 way handshake

Only need to understand sequence number,
acknowledgement number, flags.

Client sends SYN (synchronize). SYN flag is
set, no data. Consumes 1 sequence number
(byte). SYN cannot carry data, but consumes
one byte as sequence number
tcp

Server: sends SYN+ACK back to client. SYN
and ACK bits are sent. This means open up the
reverse connection while acknowledging the
forward connection. Consumes one sequence

Client: sends ACK: ACK flag set. ACK no is the
same as the incoming SYN no. ACK consumes
no sequence.
tcp

ACKs without data carry no sequence number

Remember 2 sequence numbers are used for
bidirectional communication! Here in tcp this is
called seq and ack numbers.

SYN flooding:

Spoof source IP, SYN requests sent to a server.
Server tries to respond with SYN+ACK. Many
solutions: eg use cookies
tcp

Tcp: bidirectional data transfer

PSH flag tells TCP to “push” all data to the
server application as soon as it is received.
Server does not set PSH flag in its packets to
clients.

Examples of PSH enabled applications – chat

Urgent data: asks TCP to send data out of order
to application
tcp

Think of examples when urgent flag is needed.

Connection termination: also with 3 way
handshake (mostly)

Why 3 way handshaking: an acknowledgement
of an acknowledgement

First segment: sets FIN flag (finished)

Of course FIN can include data
tcp

FIN: consumes 1 sequence number if it does
not carry data

Server: FIN+ACK. As usual, consumes 1
sequence number if it does not consume data.

Client: ACKs the FIN+ACK.

Half close also possible – one end stops
sending but keeps receiving

Amazing: half close can be accepted by server
tcp

Half close can be accepted by server by
sending ACK and not FIN (for its own
connection). So server can still send data

Important to see how sequence numbers
change: think about this!!

Flow control: between Go Back N and Selective
Repeat protocols. Like Go back N because
doesnt use NAK. Like SR because rx window is
larger for reordering
tcp

Sliding window tcp is byte oriented. Frame
oriented at layer 2. tcp sliding window is of
variable size. Why? Discuss the tradeoffs of this
tcp

Tcp error control

Checksum, ack, timeout

Why ACK do not consume sequence numbers:
because they are not acknowledged!!

Retransmission: timeout or 3 duplicate ACKs

RTO based on RTT and is dynamic. RTO also uses
backoff similar to DLL backoff