1. Explain IEEE 802.3 standard or Ethernet in detail.

(April/May 15, Nov/Dec 15, Nov/Dec

16)
Ethernet was developed by DEC, Intel and Xerox. It was standardized as IEEE 802.3
Standard Ethernet is the most successful LAN technology with a data rate of 10
Mbps.
It has evolved to Fast Ethernet (100 Mbps), Gigabit Ethernet (1 Gbps) and Ten-Gigabit
Ethernet (10 Gbps).
Physical Properties

• Hosts are tapped on to the Ethernet segment, each at least 2.5 m apart.
• Transceiver is responsible for transmitting/receiving frames and collision detection.
• Protocol logic is implemented in the adaptor.
• Ethernet can support a maximum of 1024 hosts.
• Maximum length of Ethernet is 2500 m.
• Manchester encoding scheme is used with digital signaling at 10 Mbps.
• Various forms of Standard Ethernet are 10Base5 (thick ethernet), 10Base2 (thin
ethernet), 10Base-T (twisted-pair) and 10Base-F (fiber-optic).
• Ethernet segments can be connected using repeater or a hub.

Ethernet Repeater Ethernet Hub

Media Access Control (MAC)
Ethernet MAC protocol regulates access to the shared Ethernet link.
Frame Format

• Preamble—alternating 0s and 1s that alerts the receiving node. 

Destination address—physical address of the destination host.
• Source address—physical address of the sender.
• Type—contains either type of upper layer protocol or frame length.
• Body—data (46–1500 bytes).
• CRC—error detection information (CRC-32).
Addressing
Each host on the Ethernet network has its own network interface card (NIC).
NIC provides a globally unique 6-byte physical address (in Hex for readability).
CS6551-COMPUTER NETWORKS Page 1
 If LSB of the first byte in a destination address is 0, then it is unicast else multicast.
In broadcast address, all bits are 1s (FF:FF:FF:FF:FF:FF).
Transmitter
Ethernet is a working example of CSMA/CD.
Minimum frame length of 64 bytes is required for operation of CSMA/CD.
Signals placed on the ethernet propagate in both directions and is broadcasted.
Ethernet is a 1-persistent protocol. When there is a frame to be sent: o If link is idle,
the frame is transmitted immediately. o If link is busy, it waits till it becomes idle and
then transmits immediately. When two or more nodes transmit frame simultaneously,
they collide. CSMA/CD works as follows: o Current transmission is aborted. o A 96-
bit runt frame (64-bit preamble + 32-bit jamming sequence) is sent. oOther nodes refrain
from transmission on receiving runt frame.
o Retransmission is attempted after a back-off procedure (k × 51.2µ s, k =
1,2,3,…). o After 16 attempts, retransmission is given up. Receiver
Each frame transmitted on an Ethernet is received by every adaptor on that network.
A frame is accepted if destination address: o matches its
address, o contains broadcast address, o multicast address,
if it's part of that multicast group. Frames are discarded, if it
is not meant for that host.
All frames are accepted, if configured in promiscuous mode.
Ethernet does not acknowledge received frames.
Advantages and disadvantages of Ethernet.
Easy to administer and maintain.
Relataively inexpensive.
Produces better output only when lightly loaded (< 200 hosts).
It is an unreliable medium.

2. Why the minimum frame length in Ethernet should be at least 64 bytes (512 bits)?
(May/Jun 14)
Consider the following worst case scenario in which hosts A and B are at either ends.

Host A begins transmitting a frame at time t (fig a).

It takes link latency d for the frame to reach host B. Thus, the first bit of A’s frame arrives at
B at time t + d (fig b)
Suppose an instant before host A’s frame arrives, B senses it idle and begins to transmit.
B’s frame collides with A’s frame, and this collision will be detected by host B (fig c)
Host B aborts its transmission and sends a runt frame.
Host A knows about collision only when runt frame reaches it, at time t + 2d (fig d) RTT for
Ethernet with maximum distance (2500 m) is 51.2µ s. It corresponds to 512 bits (64 bytes)
on 10 Mbps standard ethernet.

CS6551-COMPUTER NETWORKS Page 2

Thus frame length of 512 bits is required for an host to detect collision before it transmits
the last bit.

3. Explain the functioning of wireless LAN or IEEE 802.11 in detail (April/May 15,
Nov/dec15, April/May17)
Wireless LAN or WLAN or Wi-Fi is designed for use in a limited area (office, campus,
building, etc). It is standardized as IEEE 802.11
Physical Properties
WLAN runs over free space based on FHSS (frequency hopping over 79 1-MHz-wide
frequency bandwidth) and DSSS (11-bit chipping sequence) with data rate of 2 Mbps.
Variants of 802.11 are:
o 802.11b operates in 2.4-GHz frequency band with data rate of 11 Mbps.
802.11a/g runs in 5-GHz band using orthogonal FDM (OFDM) at 54 Mbps o
802.11n uses multiple antennas (multiple input/output) and offers up to
100
Mbps
Optimal bit rate for transmission is based on signal-to-noise ratio (SNR) in environment.
Distribution System
In wireless network, nodes are mobile and the set of reachable nodes change with
time. Mobile nodes are connected to a wired network infrastructure called access
points (AP) Access points are connected to each other by a distribution system (DS)
such as Ethernet.

Nodes communicate directly with each other if they are reachable (eg, A and C)
Communication between two nodes in different APs occurs via two APs (eg, A and E)
Whenever a mobile node joins a network, it selects an AP. This is called
active scanning. o Node sends a Probe frame. o All APs within reach
reply with a Probe Response frame.
o Node selects an AP and sends an Association Request frame. o
Corresponding AP replies with an Association Response frame
Access points periodically send a Beacon frame advertising its features such as
transmission rate. This is known as passive scanning.
Hidden / Exposed Node Problem
All nodes are not within the reach of each other.
Carrier sensing may fail because of hidden node and exposed node problem.
Hidden Node
• Suppose node B is sending data to A. At the same time, node C also wishes to send to
A.
• Since node B is not within the range of C, C finds the medium free and transmits to A.
• Frames from nodes B and C sent to A collide with each other.  Thus nodes B and C
are hidden from each other.

CS6551-COMPUTER NETWORKS Page 3

 Hidden Node Exposed Node
Exposed Node p Suppose node A is transmitting to node B and node C has some data
to be sent to node D. q Node C finds the medium busy, since it hears the transmission
from node A and refrains from sending to node D, even though its transmission to D
would not interfere. r Thus node C is exposed to transmission from node A to B
Multiple Access with Collision Avoidance (MACA)
Sender and receiver exchange control frames to reserve access, so that nearby nodes
avoid transmission during duration of a data frame.
Control frames used to avoid collision are Request to Send (RTS) and Clear to Send (CTS).
Sender sends RTS frame to the receiver containing sender/receiver address and
transmission duration.
Nodes that receive RTS frame are close to sender and wait for CTS to be transmitted
back.
Receiver acknowledges and sends a CTS frame containing sender address and
duration.
Nodes that receive CTS remain silent for the upcoming data transmission.
Nodes that receive RTS but not CTS, is away from the receiver and is free to transmit.
Receiver sends an ACK frame to the sender after successfully receiving data frames. If
RTS frames from two or more nodes collide, then they do not receive CTS. Each node
waits for a random amount of time and then tries to send RTS again (back-off
procedure).

Handshake for hidden node Handshake for exposed node

Handshake for Hidden node
Node B has frames for A and sends RTS to A. It reaches A, but not C.
Node A sends CTS frame to B, which is also received by node C.
Node B starts to transmit data frames to node A.
Node C knows of upcoming transmission from B to A and refrains from transmitting.
Handshake for Exposed node
 Assume that node A is transmitting to node B after exchanging control frames.
 Node C sends RTS to node D which is also sent to node A.
 Node D replies with CTS to C, whereas node A does not reply, since it is transmitting.
 Node C infers that there is no interference and transmits data frames to node D.

Frame Format

CS6551-COMPUTER NETWORKS Page 4

 Control―indicates frame type (RTS, CTS, ACK or data) and 1-bit ToDS / FromDS
Duration―specifies dura on of frame transmission.

Addresses―The four address fields depend on value ofToDSa ndFromDSsubfields.

Sequence Control―defines sequence number of the frame.

Payload―contains a maximum of 0–2312 bytes.
CRC―contains CRC-32 error detection sequence.

4. Write short notes on Bluetooth (May/Jun 16)

Bluetooth technology, standardized as IEEE 802.15.1 is a personal area network (PAN).

It is used for short-range wireless communication (maximum 10 m) between mobile
phones, PDAs, notebook and other peripheral devices.
Uses low power transmission, operates in 2.45 GHz band with data rate up to 3 Mbps.
Bluetooth Special Interest Group has specified a set of protocols for a range of
application, known as profiles. For instance, a profile synchronizes PDA and PC.
Bluetooth network configuration is known as piconet. A piconet can have up to
eight stations, one of which is called the master and the rest are called slaves. o
Slaves do not directly communicate with each other, but via the master.
o Bluetooth uses FHSS (79 channels, each 625 µs) for transmission.o
Master transmits in odd-numbered slots, whereas slave respond in even
slots. o Slaves in parked or inactive state cannot communicate, until it is
activated by the master. Maximum of 255 devices can be in parked state.
Bluetooth hardware and software is simpler and cheaper.

5. List and compare the features of any two wireless technologies. (May/Jun 16)
Bluetooth WiFi WiMax 3G
IEEE standard 802.15.1 802.11 802.16
Link length 10 m 100 m 10 km Tens of km
Bandwidth 2.1 Mbps (shared) 54 Mbps 70 Mbps 384 Kbps
(shared)
Usage Link a peripheral Link a computer Link a building Link a cell phone

CS6551-COMPUTER NETWORKS Page 5

 to a computer to a wired base to a wired tower to a wired tower
6. Discuss Internetworking Protocol in detail.(Nov/Dec 16)
 Internet Protocol (IP) is used to build scalable, heterogeneous internetworks.
 Ability of IP to run over any networking technology is its strength.
 IP Service model has two parts
o Datagram (connectionless) model of data delivery o Addressing
scheme to identify all hosts uniquely in the internetwork.

Datagram Delivery
 Best-effort, connectionless service is used by IP to deliver a datagram
 Packets can be lost or corrupted. It can also be delivered out of order.
 IP provides neither error control nor flow control. It is an unreliable service.
Packet Format
 IPv4 datagram is a variable-length packet consisting of two parts, header and data.
  Header is 20–60 bytes long and contains information essential to routing and delivery
 Minimum packet length is 20 bytes and maximum 65,535 bytes.





CS6551-COMPUTER NETWORKS Page 6

 Version―version of IPv4 protocol, i.e. 4.
 HLen―length of the header in 4-byte words. When there are no options, its value is 5.
 TOS―allows packets to be placed on separate queues based on QoS required.
 Length―total packet length (header + data), which is restricted to 65,535 bytes.
 Ident―a 16-bit identifier that uniquely identifies a datagram packet.
 Flags―3-bit field contains D (do not fragment) bit and M (more fragment) bit.
 Offset―shows relative position of the fragment in units of 8 bytes.
 TTL―defines lifetime of the datagram (default 64 hops).

 Protocol―specifies upper layer protocol (e.g., 6 for TCP, 17 for UDP).

 Checksum―16-bit internet checksum for the packet header.
 SourceAddr / DestinationAddr―32-bit IP address of source and destination host.
Global Addressing
32
 IPv4 uses 32-bit addresses, i.e., approximately 4 billion addresses (2 ).
 IP addresses are hierarchical, i.e., it corresponds to hierarchy in the internetwork.
 IP addresses consist of two parts, network id and host id. p Network id
identifies physical network to which the host is attached.
o Hosts attached to a network have the same network id in their IP
address. o Host id is used to uniquely identify a host on that network.
  Router that connects networks has a unique IP address on each of its interface.
  It is written as four octets (0–255) in dotted decimal notation. For eg,
172.16.15.161
 IPv4 address space is divided into five classes: A, B, C, D and E.
 Class of an IP address is identified by MSBs (in binary) or first byte (in decimal).
Class Binary Decimal Addressing Application
A 0 0–127 Unicast WAN
B 10 128– Unicast Campus Network
191
C 110 192– Unicast LAN
223

CS6551-COMPUTER NETWORKS Page 7

 D 1110 224– Multicast
239
E 1111 240– Reserved
255
  Classes A, B and C are used for unicast addressing.
 Class D was designed for multicasting and class E is reserved.
 Classes A, B, C have certain bits for network part and rest for host part i.e., networks
 belonging to a class and number of hosts attached to it are limited
o Class A—upto 126 networks and 16 million hosts per network
14
 o Class B—upto 2 networks and 65,534 hosts per network
21 o Class C—upto 2 networks
and 254 hosts per network

Class A Class B Class C

Datagram Forwarding
  Destination address is used by routers to forward packets in a connectionless
manner.
 Forwarding table at a router is a list of (NetworkNum, NextHop) pairs.

Algorithm
if (NetworkNum of destination = NetworkNum of any of its interface)
then Deliver packet to destination over thatinterface
else
if (NetworkNum of destination is in forwarding table) then
Deliver packet to NextHop router
else
Deliver packet to default router
Example
 Suppose H5 sends a datagram to H8, then forwarding is as follows:
  H1 sends datagram to its default router R1, since it cannot deliver directly.
 R1 sends datagram over wireless network to its default router R2, since H8 network id
 does not match any of its interfaces.
 R2 forwards the datagram to R3 based on its forwarding table.
 R3 forwards the datagram directly to H8, since both are on the same network.
NetworkNum NextHop
1 R1
Interface 1
Interface 0
4 R3
R2 Forwarding Table
CS6551-COMPUTER NETWORKS Page 8
 Detail the process of determining the physical address of a destination host (ARP).
 Physical interface on a host or router understands physical addressing scheme of that
 network only. Therefore IP address has to be translated to link-level address.
  To send datagram to a host or router, both logical and physical address must be
known.  Address Resolution Protocol (ARP) enables a source host to know the
physical address
 of another node when the logical address is known.
 ARP relies on broadcast support from physical networks such as ethernet, token ring,
etc.
 ARP enables each host to build a mapping table between IP address and physical
address.
Packet Format
0 8 16 31
HardwareType Protocol Type
Hlen PLen Operation
SourceHardwareAddr
SourceProtocolAddr
TargetHardwareAddr
TargetProtocolAddr
  HardwareType―type of the physical network (e.g., 1 for ethernet).
 ProtocolType―value of upper-layer protocol (e.g., 8 for IPv4).
 HLen―length of the physical address in bytes (e.g., 6 for Ethernet address).
 PLen―length of the logical address in bytes (e.g., 4 for IPv4 address).
  Operation―type of ARP (1 for request, 2 for reply).
 SourceHardwareAddr― physical address of the sender.
  SourceProtocolAddr―logical address of the sender.
 TargetHardwareAddr―physical address of the target node.
 TargetProtocolAddr―logical address of the target node.
Address Translation
 Host checks its ARP table with destination IP address. o If an
entry exists, then corresponding physical address is used to send
datagram.
o Otherwise, source host finds physical address using ARP.
 Source host creates a ARP request packet with: o Operation field
set to 1.
o Target Physical address field is unknown and filled with 0s (broadcast address).
  ARP request is encapsulated in IP packet and broadcasted over the physical network.
 Each host takes note of sender's logical and physical address. All nodes except the
 destination host discard the packet.
CS6551-COMPUTER NETWORKS Page 9
  Destination host constructs an ARP reply packet with Operation field set to 2.
 ARP reply is unicast and sent back to the sender.
 Sender stores target logical-physical address pair in its ARP table from reply packet.


9. Discuss the automatic configuration of IP address to hosts using DHCP.

 Operating systems allow system administrator to manually configure IP address, which is
 tedious and error-prone.
 Dynamic Host Configuration Protocol (DHCP) enables auto configuration of IP address
 to hosts using DHCP server.
  DHCP server sends and receives message using UDP over ports 67 and 68
respectively.
 DHCP provides dynamic (automatic) address allocation when host connects to a
network.
Packet Format

 Operation―specifies type of DHCP packet.

 Xid―specifies the transaction id.
 ciaddr―specifies client IP address in case of DHCPREQUEST
  yiaddr― known as your IP address, filled by DHCP server.
 siaddr―contains IP address of the DHCP server.
 giaddr―contains IP address of the Gateway or relay agent.
 chaddr―contains hardware (physical) address of the client.
 options―contains information such as lease duration, default route, DNS server, etc.
Dynamic Address Allocation
  DHCP server is configured with range of addresses to be assigned to hosts on demand.
 To contact DHCP server, client broadcasts a DHCPDISCOVER message with IP address
255.255.255.255 and it's physical address placed in chaddr field
 DHCP server selects an unassigned IP address for yiaddr field and adds an entry to
 dynamic database along with client's physical address.
 DHCP server sends DHCPOFFER message containing client's IP and physical address,
 server IP address and options.
 Client sends a DHCPREQUEST message, requesting the offered address.

CS6551-COMPUTER NETWORKS Page 10

  Based on transaction id, the DHCP server acknowledges with a DHCPACK message.
 When lease period expires, client attempts to renew. It’s up to server to accept or reject
it.
DHCP relay
 DHCP is an application layer protocol, i.e., server/client need not be on the same
network

 In such case, DHCP relay agent receives broadcast message. o DHCP relay stores
relay address in giaddr before sending it to DHCP server. o DHCP server response is sent
to relay agent, which is sent back to the client.

10. Write short notes on error reporting using ICMP.

 Internet Control Message Protocol (ICMP) is used to report error messages to source host
and diagnose network problems. ICMP message is encapsulated within an IP packet.
Error reporting
 Destination Unreachable―When a router cannot route a datagram, the datagram is
discarded and sends a destination unreachable message to source host.
 Source Quench―When a router or host discards a datagram due to congestion, it sends a
source-quench message to the source host. This message acts as flow control.
 Time Exceeded―Router discards a datagram when TTL field becomes 0 and a time-
 exceeded message is sent to the source host.
 Parameter Problem―If a router discovers ambiguous or missing value in any field of the
datagram, it discards the datagram and sends parameter problem message to source.
 Redirection―Redirect messages are sent by the default router to inform the source host to
update its forwarding table when the packet is routed on a wrong path.
Query Messages
 Echo Request & Reply―The combination of echo-request and echo-reply messages
determines whether two systems can communicate at the IP level.
 Timestamp Request & Reply―Two machines can use the timestamp request and
 timestamp reply messages to determine the round-trip time (RTT).
 Address Mask Request & Reply―A host to obtain its subnet mask, sends an address mask
request message to the router, which responds with an address mask reply message.
 Router Advertisement―A host broadcasts a router solicitation message to know about the
router. Router broadcasts its routing information with router advertisement message.

CS6551-COMPUTER NETWORKS Page 11

 Write short notes on simple demultiplexer (or) UDP. (May/Jun 16)
 User Datagram Protocol (UDP) is a connectionless, unreliable transport protocol.
 Adds process-to-process communication to best-effort service provided by IP.
 Simple demultiplexer allows multiple processes on each host to communicate.
  Does not provide flow control / reliable / ordered delivery.
 UDP is suitable for a process that requires simple request-response communication
with little concern for flow control/error control.
UDP Header
 UDP packets are known as user datagrams It has a 8-byte header.








  SrcPort and DstPort—Source and destination port number.

 Length—total length of the user datagram, i.e., header plus data.
 Checksum—computed over UDP header, data and pseudo header. Pseudo header
consist of IP fields (Protocol, SourceAddr, DestinationAddr) and UDP Length field.
UDP delivers message to the correct recipient process using checksum.
Ports
 Processes (server/client) are identified by an abstract locator known as port.
 Server accepts message at well known port. Some well-known UDP ports are 7–
 Echo, 53–DNS, 111–RPC, 161–SNMP, etc.
 < port, host > pair is used as key for demultiplexing.
 Ports are implemented as a message queue.
When a message arrives, UDP appends it to end of the queue.
o When queue is full, the message is discarded.
 When a message is read, it is removed from the queue.

Applications
 Used for management processes such as SNMP.
 Used for route updating protocols such as RIP.
  It is a suitable transport protocol for multicasting.
 UDP is suitable for a process with internal flow and error control mechanisms such
as Trivial File Transfer Protocol (TFTP).
2. List the features of TCP. Draw TCP segment format and explain its fields.(April/May 15,
Nov/Dec 16)

CS6551-COMPUTER NETWORKS Page 12

  Transmission Control Protocol (TCP) offers connection-oriented, byte-stream
service.
 Guarantees reliable, in-order delivery of message.
 TCP is a full-duplex protocol.
 Like UDP, TCP provides process-to-process communication.
 Has built-in congestion-control mechanism.
 Ensures flow control, as sliding window forms heart of TCP operation. 
 Some well-known TCP ports are 21–FTP, 23– TELNET, 25–SMTP, 80–HTTP, etc.
 Sending TCP buffers bytes in send buffer and transmits data unit as
segments.
 Segments are stored in receive buffer at the other end for application to read. 
TCP’s demux key is < SrcPort, SrcIPAddr, DstPort, DstIPAddr >

Segment Format
 Data unit exchanged between TCP peers are called segments.

  SrcPort and DstPort―port number of source and destination process.

  SequenceNum―contains sequence number, i.e. first byte of data segment.
 Acknowledgment― byte number of segment, the receiver expects next.
  HdrLen― length of TCP header as 4-byte words.  Flags―contains six control bits
known as flags.  URG—segment contains urgent data.
ACK—value of acknowledgment field is valid.
PUSH—sender has invoked the push operation. RESET—receiver
wants to abort the connection.
• SYN—synchronize sequence numbers during connection establishment.
• FIN—terminates the TCP connection.
• AdvertisedWindow―defines receiver’s window size and acts as flow
control.
• Checksum―It is computed over TCP header, Data, and pseudo header
containing
IP fields (Length, SourceAddr & DestinationAddr).
• UrgPtr―specifies first byte of normal data contained in the segment, if URG
bit is set.

CS6551-COMPUTER NETWORKS Page 13

 3. Explain TCP connection management (or) TCP architecture (or) state transition diagram.
(Nov/Dec 15)
 TCP is connection-oriented.
Client performs an active connection to establish connection with a passive open
server, prior to data communication
r Eventually connection is terminated after data transmission.
Connection Establishment
  Connection establishment in TCP is a three-way handshaking.
o Client sends a SYN segment to the server containing its initial sequence number
(Flags = SYN, SequenceNum = x) p Server responds with a segment that
acknowledges client’s segment and specifies its initial sequence number (Flags = SYN+
ACK, Ack = x + 1 SequenceNum = y).
q Finally, client responds with a segment that acknowledges server’s sequence
number (Flags = ACK, Ack = y + 1).

Connection Termination
 Connection termination or teardown can be done in two ways
  Three-way close—Both client and server close simultaneously. o Client sends a
FIN segment. The FIN segment can include last chunk of data. o Server responds with
FIN + ACK segment to inform its closing.  o Finally, client sends an ACK segment.
 Half-Close—Client stops sending but receives data. This is known as halfclose. o
Client half-closes the connection by sending a FIN segment. o Server sends
an ACK segment. Data transfer from client to the server stops.
q After sending all data, server sends FIN segment to client, which is
acknowledged by the client.

State Transition Diagram

 States involved in opening and closing a connection is shown above and below
ESTABLISHED state respectively.
 Events that trigger a state transition is:
Segments that arrive from its peer.
Application process invokes an operation on TCP
 Operation of sliding window is hidden in the ESTABLISHED state

CS6551-COMPUTER NETWORKS Page 14

 Opening s Server invokes a passive open on TCP, which causes TCP to move to
LISTEN state t Client does an active open, which causes its TCP to send a SYN
segment to the server and move to SYN_SENT state.
u When SYN segment arrives at the server, it moves to SYN_RCVD state and responds
with a SYN + ACK segment.
v Arrival of SYN + ACK segment causes the client to move to ESTABLISHED state and
sends an ACK to the server. w When ACK arrives, the server finally moves to
ESTABLISHED state.
Closing
 Client / Server can independently close its half of the connection or simultaneously.
 Transitions from ESTABLISHED to CLOSED state are:
  One side closes: ESTABLISHED→FIN_WAIT_1→FIN_WAIT_2→TIME_WAIT→CLOSED
 Other side closes: ESTABLISHED → CLOSE_WAIT → LAST_ACK → CLOSED
 Simultaneous close: ESTABLISHED→FIN_WAIT_1→CLOSING→TIME_WAIT→ CLOSED

4. Explain TCP flow control (or) adaptive flow control (or) TCP Sliding window in detail.
(April/May 17)
 TCP uses a variant of sliding window known as adaptive flow control that:
o guarantees reliable delivery of data
ensures ordered delivery of data
o enforces flow control at the sender
  Receiver advertises its window size to the sender using AdvertisedWindow field. 
Sender thus cannot have unacknowledged data greater than AdvertisedWindow.

CS6551-COMPUTER NETWORKS Page 15

 Send Buffer Receive Buffer
Send Buffer
 Sending TCP maintains send buffer which contains 3 segments, acknowledged data,
 unacknowledged data and data to be transmitted.
 Send buffer maintains three pointers LastByteAcked, LastByteSent, and
 LastByteWritten such that:
 LastByteAcked ≤ LastByteSent ≤ LastByteWritten
  A byte can be sent only after being written and only a sent byte can be
acknowledged.
 Bytes to the left of LastByteAcked are not kept as it had been acknowledged.

Receive Buffer
  Receiving TCP maintains receive buffer to hold data even if it arrives out-of-
order.
 Receive buffer maintains three pointers namely LastByteRead, NextByteExpected,
 and LastByteRcvd such that:
 LastByteRead < NextByteExpected ≤ LastByteRcvd + 1
  A byte cannot be read until that byte and all preceding bytes have been
received.
 If data is received in order, then NextByteExpected = LastByteRcvd + 1
 Bytes to the left of LastByteRead are not buffered, since it is read by the application.
Flow Control
  Size of send and receive buffer is MaxSendBuffer and MaxRcvBuffer
respectively.
  Sending TCP prevents overflowing of send buffer by maintaining

 LastByteWritten − LastByteAcked ≤ MaxSendBuffer

  Receiving TCP avoids overflowing its receive buffer by maintaining 
LastByteRcvd − LastByteRead ≤ MaxRcvBuffer
 Receiver throttles the sender by having AdvertisedWindow based on free space
 available for buffering.

 AdvertisedWindow = MaxRcvBuffer − ((NextByteExpected − 1) − LastByteRead)

 Sending TCP adheres to AdvertisedWindow by computing EffectiveWindow that

CS6551-COMPUTER NETWORKS Page 16

 limits how much data it should send.

 EffectiveWindow = AdvertisedWindow − (LastByteSent − LastByteAcked)

  When data arrives, LastByteRcvd moves to its right and AdvertisedWindow

shrinks.
  Receiver acknowledges only, if preceding bytes have arrived. 
AdvertisedWindow expands when data is read by the application. o If data is
read as fast as it arrives then AdvertisedWindow = MaxRcvBuffer o If data is read
slowly, it eventually leads to a AdvertisedWindow of size 0.
 AdvertisedWindow field is designed to allow sender to keep the pipe full.
Fast Sender vs Slow Receiver
 If sender transmits at a higher rate, receiver's buffer gets filled up. Hence,
AdvertisedWindow shrinks, eventually to 0.
  Receiver advertises a window of size 0, thus sender cannot transmit as it gets blocked.
  When receiving process reads some data, those bytes are acknowledged and
AdvertisedWindow expands.
 When an acknowledgement arrives for x bytes, LastByteAcked is incremented by x
and send buffer space is freed accordingly to send further data.
5. Explain adaptive retransmission algorithms. (or) How is timeout estimated in TCP?
 TCP guarantees reliability through retransmission when ACK arrives after timeout.
 Timeout is based on RTT, but it is highly variable for any two hosts on the internet.
 Appropriate timeout is chosen using adaptive retransmission.
Original Algorithm
 SampleRTT is the duration between sending a segment and arrival of its ACK.
 EstimatedRTT is weighted average of previous estimate and current sample.
EstimatedRTT = α × EstimatedRTT + (1 − α) × SampleRTT
(where α is known as smoothening factor with value in the range 0.8–0.9)
  Timeout is determined as twice the value of EstimatedRTT . TimeOut = 2 ×
EstimatedRTT

 In original TCP, timeout is thus computed as function of running average of RTT.

Karn/Partridge Algorithm
 Flaw discovered in TCP original algorithm was that an ACK segment,
 acknowledges receipt of data, not a transmission.
 When an ACK arrives after retransmission, it is impossible to decide, whether to
pair it with original or retransmitted segment for SampleRTT estimation. o If
ACK is associated with original one, then SampleRTT becomes too large
 o If ACK is associated with retransmission, then SampleRTT becomes too small 
Karn and Partridge proposed that
SampleRTT should be taken for segments that are sent only once, i.e, for
segments that are not retransmitted.
Each time TCP retransmits, timeout is doubled, since loss of segments is
mostly due to congestion.

CS6551-COMPUTER NETWORKS Page 17

 Large SampleRTT Small SampleRTT
Jacobson/Karels Algorithm
 Jacobson and Karel discovered that problem with original algorithm was variance in
SampleRTT was not considered.
 Mean RTT and variation in mean is calculated as: Difference
= SampleRTT
EstimatedRTT = EstimatedRTT + (δ × Difference)
Deviation = Deviation + δ (|Difference|
(where δ is a fraction between 0 and 1)
  TimeOut is computed as a function of both EstimatedRTT and Deviation as:
TimeOut = μ × EstimatedRTT + φ × Deviation
(where μ = 1 and φ = 4)
 When variance is small, TimeOut is close to EstimatedRTT. If variation among
samples is small, then EstimatedRTT can be trusted.
Define Congestion.
 Congestion occurs if load (number of packets sent) is greater than capacity of the
network (number of packets a network can handle).
  When load is less than network capacity, throughput increases proportionally.

 When load exceeds capacity, queues become full and the routers discard some
packets and throughput declines sharply.
 TCP uses mechanisms to control or avoid congestion.

6. Explain TCP congestion control mechanisms in detail.(Nov/Dec 15, Nov/Dec 16,

April/May 15, May/Jun 16)
 Each source determines capacity of the network, so as to send packets without loss.
  TCP uses ACKs for further transmission of packets, i.e., self-clocking.
  TCP maintains a state variable CongestionWindow for each connection.
  A source is not allowed to send faster than network or destination host.

 MaxWindow = MIN(CongestionWindow, AdvertisedWindow)

 Congestion control mechanisms are:
Additive Increase / Multiplicative Decrease (AIMD)
Slow Start
Fast Retransmit and Fast Recovery
Additive Increase/Multiplicative Decrease (AIMD)
 TCP source initializes CongestionWindow based on congestion level in the network.
 Source increases CongestionWindow when level of congestion goes down and

CS6551-COMPUTER NETWORKS Page 18

 decreases the same when level of congestion goes up.
  TCP interprets timeouts as a sign of congestion and reduces the rate of
transmission.
 On timeout, source reduces its CongestionWindow by half, i.e., multiplicative decrease.
For example, if CongestionWindow = 16 packets, after timeout it is 8.
 Value of CongestionWindow is never less than maximum segment size (MSS).
 When ACK arrives CongestionWindow is incremented marginally, i.e., additive
 increase.
Increment = MSS × (MSS / CongestionWindow)
 CongestionWindow += Increment
 For example, when ACK arrives for 1 packet, 2 packets are sent. When ACK for
 both packets arrive, 3 packets are sent and so on.
 CongestionWindow increases and decreases throughout lifetime of the connection.
 When CongestionWindow is plotted as a function of time, a saw-tooth pattern results.

Additive Increase CongestionWindow Trace

Analysis
 AIMD decreases its CongestionWindow aggressively but increases conservatively.
  Small CongestionWindow results in less probability of packets being
dropped..
 AIMD is appropriate when source is operating close to capacity of the network.

CS6551-COMPUTER NETWORKS Page 19

 Slow Start
 Slow start is used to increase CongestionWindow exponentially from a cold start.
  Source TCP initializes CongestionWindow to one packet.
 TCP doubles the number of packets sent every RTT on successful transmission.
o When ACK arrives for first packet TCP adds 1 packet to CongestionWindow
and sends two packets.
o When two ACKs arrive, TCP increments CongestionWindow by 2 packets
and sends four packets and so on.
 Instead of sending entire permissible packets at once (bursty traffic), packets are
 sent in a phased manner, i.e., slow start.
 Initially TCP has no idea about congestion, henceforth it increases
 CongestionWindow rapidly until there is a timeout. On timeout:
CongestionThreshold = CongestionWindow /
2 CongestionWindow = 1
 Slow start is repeated until CongestionWindow reaches CongestionThreshold and
thereafter 1 packet per RTT.
Example
  Initial slow start causes increase in CongestionWindow up to 34KB,
  Congestion occurs at 0.4 seconds and packets are lost.
 ACK does not arrive and therefore trace of CongestionWindow becomes flat.
  Timeout occurs at 2 sec. CongestionThreshold=17KB,
CongestionWindow=1PKT
 Slow start is done till 17KB and additive increase thereafter till congestion occurs.

Exponential Increase CongestionWindow Trace

Analysis

  Slow start provides exponential growth and is designed to avoid bursty nature of
TCP.
 TCP loses more packets initially, because it attempts to learn the available
 bandwidth quickly through exponential increase.
 If connection goes dead while waiting for timer to expire, slow start phase is used
only up to current value of CongestionWindow.
Fast Retransmit and Fast Recovery
 TCP timeouts led to long periods of time during which the connection went dead
 while waiting for a timer to expire.


CS6551-COMPUTER NETWORKS Page 20

 
 Fast retransmit is a heuristic approach that triggers retransmission of a dropped packet
 sooner than the regular timeout mechanism. It does not replace regular timeouts.
 When a packet arrives out of order, receiving TCP resends the same
acknowledgment (duplicate ACK) it sent last time.

 When three duplicate ACK arrives at the sender, it infers that corresponding
packet may be lost due to congestion and retransmits that packet. This is called
fast
 retransmit before regular timeout.
 When packet loss is detected using fast retransmit, the slow start phase is replaced
 by additive increase, multiplicative decrease method. This is known as fast
recovery.
Instead of setting CongestionWindow to one packet, this method uses the ACKs that
 are still in pipe to clock the sending of packets.
Slow start is only used at the beginning of a connection and after regular timeout.
At other times, it follows a pure AIMD pattern.
Example
 In example, packets 1 and 2 are received whereas packet 3 gets lost. o
Receiver sends a duplicate ACK for packet 2 when packet 4 arrives.
o Sender receives 3 duplicate ACKs after sending packet 6 retransmits packet 3.
o When packet 3 is received, receiver sends cumulative ACK up to packet 6.
 In example trace, slow start is used at beginning and during timeout at 2 secs. o
Fast recovery avoids slow start from 3.8 to 4 sec.
o CongestionWindow is reduced by half from 22 KB to 11
KB. o Additive increase is resumed thereafter.

Duplicate ACK CongestionWindow Trace

Analysis
 Long periods with flat congestion window and no packets sent are eliminated.
 TCP's fast retransmit can detect up to three dropped packets per window.
 Fast retransmit/recovery increases throughput by 20%.
7. Explain in detail about TCP congestion avoidance algorithms.(April/May 17)
 Congestion avoidance mechanisms prevent congestion before it actually occurs.
 TCP creates loss of packets in order to determine bandwidth of the connection.
 Routers help the end nodes by intimating when congestion is likely to occur.
 Congestion-avoidance mechanisms are: o DECbit


CS6551-COMPUTER NETWORKS Page 21

 
Random Early Detection (RED) o
Source-based congestion avoidance
DECbit
 Each router monitors its load and explicitly notifies the end node when congestion
is likely to occur. Source reduces its transmission rate and congestion is avoided.
 A binary congestion bit called DECbit is added to the packet header.

 Router sets this bit in packets that flow through, if its average queue length is 
1. o Average queue length is measured over a time interval that includes the last
busy + last idle cycle + current busy cycle. o Calculates average queue length by
dividing the curve area with time interval.

  Destination host copies the DECbit onto ACK and sends it back to the source.
Source checks how many ACK has DECbit set for previous window packets.
If less than 50% of ACK have DECbit set, then source increases its congestion
window by 1 packet, otherwise decreases the congestion window by 87.5%.
 Increase by 1, decrease by 0.875 rule was based on AIMD for stabilization.
Random Early Detection (RED)
 Router notifies the source that congestion is likely to occur by dropping packets
before its buffer space exhausts (early drop), rather than later due to congestion.
  Source is implicitly notified by timeout or duplicate ACK.
 Each incoming packet is dropped with a probability known as drop probability
when the queue length exceeds drop level. This is called early random drop.
 Average queue length is computed as a weighted running average: AvgLen = (1 −
Weight) × AvgLen + Weight × SampleLen
  Queue length thresholds defined by RED are MinThreshold and MaxThreshold.
 When a packet arrives, gateway compares current AvgLen with these thresholds
and decides whether to queue or drop the packet as follows:

if
Queue the packet
if MinThreshold < AvgLen < MaxThreshold
Calculate probability P
Drop the arriving packet with probability P
if AvgLen ≥ MaxThreshold Drop
the arriving packet
AvgLen ≤ MinThreshold





CS6551-COMPUTER NETWORKS Page 22

 



 When AvgLen exceeds MinThreshold, a small percentage of packets are dropped. It
forces TCP to reduce CongestionWindow, which in turn reduces the rate at which
packets arrive at the router. Thus, AvgLen decreases and congestion is avoided.
 Drop probability P is computed as a function of AvgLen.
P = MaxP × (AvgLen − MinThreshold) / (MaxThreshold − MinThreshold)
 Drop probability increases slowly when AvgLen is between two thresholds. On
reaching MaxP at the upper threshold, it jumps to unity.
 MaxThreshold value is twice of MinThreshold due to bursty Internet traffic.
 RED drops packets randomly. The probability that a flow’s packet being dropped
is proportional to its share of the bandwidth.


RED thresholds Drop probability function

Source-Based Congestion Avoidance
 Source looks for signs of congestion in the network. For instance, increase in RTT
indicates queuing at a router.
Some mechanisms
1. TCP checks to see if current RTT is greater than mean RTT. If so, congestion
window is decreased by one-eighth, else normal increase.
2. TCP increases window size by one packet and compares the throughput achieved
when the window was one packet smaller.
TCP Vegas
 Throughput increases as congestion window increases. Increase in window size
beyond available bandwidth, results in packets queuing at the bottleneck router.
  TCP Vegas goal is to measure and control the right amount of extra data
in transit.
Extra data refers to amount of data that source would have refrained from sending
so as to not exceed the available bandwidth.

CS6551-COMPUTER NETWORKS Page 23

 

A flow’s BaseRTT is set to RTT of a packet when the flow is not congested. BaseRTT =
MIN(RTTs)
  Expected throughput without overflowing is:

 ExpectedRate = CongestionWindow / BaseRTT

 ActualRate, i.e., current sending rate for a packet is calculated by recording bytes
 transmitted during a RTT.

 ActualRate = ByteTransmitted / SampleRTT

 ExpectedRate and ActualRate are compared.
Diff = ExpectedRate – ActualRate
 Thresholds α and β are defined and corresponds to less data and too much extra data in
the network, such that α < β.
 TCP uses difference in rates and adjusts CongestionWindow accordingly. o If Diff <
α, CongestionWindow is linearly increased during the next RTT o If Diff > β,
CongestionWindow is linearly decreased during the next RTT o If α < Diff < β,
CongestionWindow is unchanged
 When actual and expected rates vary significantly, it indicates congestion in the
network. The β threshold triggers decrease in sending rate.
 When actual and expected rate is almost the same, there is available bandwidth that
goes wasted. The α threshold triggers increase in sending rate.
 Overall goal of TCP Vegas is to keep between α and β extra bytes in the network.



Black line (actual throughput), color line (expected throughput) α and β threshold (shaded region)

Difference between DECbit and RED.

 In DECbit, explicit notification about congestion is sent to source, whereas RED
 implicitly notifies the source by dropping a few packets.
 DECbit may lead to tail drop policy, whereas RED drops packet based on drop
probability in a random manner.
Explicit congestion notification
 RED drops packets early to notify congestion is not acceptable to applications that
 are intolerant to delay or loss of packets.
 A bit in the TOS field can be set by routers along the path when congestion is
encountered. The bit is echoed back to source. This is known as explicit congestion
notification (ECN).
 Explain WWW or HTTP protocol or URL in detail.(Nov/Dec 15)

CS6551-COMPUTER NETWORKS Page 24

 

 WWW is a distributed client/server service, in which a client (Browsers

such as IE, Firefox, etc.) can access services at a server (Web server such as
IIS, Apache).
 HyperText Transfer Protocol (HTTP) is a stateless request/response
protocol that governs client/server communication using TCP on port 80.
 Uniform Resource Locator (URL) provides information about its location
on the
 Web http://www.domain_name/filename
 When user enters URL, browser forms a request message and sends it to
the server.
 Web server retrieves the requested URL and sends back a response
message.
 Web browser renders the response in HTML or appropriate format.

 Request Message
Request Line
Request Header : Value

Body (optional)
 Request Line
 Request line contains
fields: Request type
URL HTTP version
 HTTP version specifies current version of the
protocol i.e., 1.1 Request type specifies methods that
operate on the URL. Some are:
Method Description
GET Retrieve the URL filename
HEAD Retrieve meta-information about the URL filename
PUT Store document under specified URL
POST Give information to server
TRACE Loopback request message (echoing).
DELETE Delete specified URL
CONNECT Used by proxies

CS6551-COMPUTER NETWORKS Page 25

 

 Request Header
 Headers defined for request message include:
Request Header Description
Authorization specifies what permissions the client has
From e-mail address of the user
Host host name of the server
If-modified-since server sends the URL if it is newer than specified date
User-agent name of the browser
 For example, request message to retrieve file result.html on host
annauniv.edu is:
 GET result.html HTTP/1.1
 Host : www.annauniv.edu
 Response Message
Status Line
Response Header : Value

Body
 Status Line
 Status line contains three fields:
 HTTP version Status code Status phrase.
 3-digit status code classifies HTTP result based on leading digit
(1xx–Informational, 2xx– Success, 3xx–Redirection, 4xx–Client error and
5xx–Server error). Status phrase gives brief description about status code.
Some are:
Code Phrase Description
100 Continue Initial request received, client to continue process
200 OK Request is successful
301 Moved Requested URL is no longer in use
permanently
404 Not found Document not found
500 Internal server error An error such as a crash, at the server site
 Response Header
 Provides additional information to the client. Some are:
Response Header Description
Content-type specifies the MIME type
Expires date and time up to which the document is valid
Last-modified date and time when the document was last updated
Location specifies location of the created or moved document


CS6551-COMPUTER NETWORKS Page 26

 

 For example, response for a moved page is:

 HTTP/1.1 301 Moved Permanently
 Location : http://www.princeton.edu/cs/index.html.
 TCP Connection
 HTTP 1.1 uses persistent connection, i.e., client and server exchange
multiple messages over the same TCP connection. The advantages are:
 o Eliminates connection setup overhead and additional load on
the server. o Congestion window is very efficient by avoiding slow start
phase for each page. o Server closes the connection on timeout.

 Caching
 Caching enables the client to retrieve document faster and reduces
load on the server. Caching is implemented at Proxy server, ISP router and
Browser.
 Server sets expiration date (Expires header) for each page, beyond which
it is not cached.
 Cache document is returned to client only if it is an updated copy by
checking against IfModified-Since header.
 If cache document is out-of-date, then request is forwarded to the server
and response is cached along the way.
 A web page will not be cached if no-cache directive is specified.
 Define Uniform Resource Identifiers (URI).
 URI is a string that identifies resources such as document, image, service,
etc. It is of the form scheme:scheme-specific
 Scheme identifies a resource type, such as mailto for mail address, file for file
name, etc. and scheme-specific is a resource identifier. Example is
mailto:[email protected] URI identifies a resource, whereas URL is used
to locate a resource.

Explain the role of DNS on a computer network (or) domain name resolution process.
(Nov/Dec 16, April/May 17)
DNS maps user-friendly domain names to router-friendly IP address, i.e., middle-ware.
Domain Naming System (DNS) includes:
namespace to define domain names without any collision o
binds domain names to IP address o name server to lookup
IP address for a given name.
Domain Hierarchy
DNS implements hierarchical name space for domains in the Internet.
Domain names are processed from right to left and use periods (.) as separator. DNS
hierarchy is represented as a tree, where each node is a domain and leaves are hosts.
Six top level domains (TLD) are .edu .com .gov .mil .org and .net
TLD also exists for each country, e.g., .fr (france) .in (india), etc.

CS6551-COMPUTER NETWORKS Page 27

 

Domain hierarchy is partitioned into zones. Each zone acts as central authority for that
part of the sub-tree. For example, in .edu domain, princeton is a zone.
Zones can be further sub-divided such as CS department under Princeton university.

Domain hierarchy example

Name Servers (NS)
Root NS is maintained by NIC and TLD name servers are managed by ICANN.
Name servers contain zonal information as resource records that binds name-to-value.
Name servers receive query and return IP address of domain name or another NS to client

Hierarchy of CS Nameserver

Resource record is a 5-tuple with fields <Name, Value, Type, Class, TTL> p Name—
specifies the domain/zone name. It is used as primary search key. o Type—
indicates what kind of record it is. Commonly used types are: NS Value field
contains address of a name server MX Value field contains a mail server.
A Value field contains an IP address
CNAME Canonical name or alias name for that host
Class field is always IN for internet domain names.
TTL field gives an indication of how long the resource record is valid.
Resource Records
Root name server contain a NS record for each TLD name server and an A record that
translates TLD into corresponding IP address.
edu, a3.nstld.com, NS, IN >
a3.nstld.com, 192.5.6.32, A, IN >
…
Each TLD name server has a NS record for each zone-level name server and an A record
that translates zone name into corresponding IP address.
Resource records for TLD edu name server looks like:

CS6551-COMPUTER NETWORKS Page 28

 

princeton.edu, dns.princeton.edu, NS, IN >

dns.princeton.edu, 128.112.129.15, A, IN >
…
Zone name server princeton.edu resolves some queries directly and redirects others to a
server at another layer in the hierarchy (cs.princeton.edu).
cs.princeton.edu, dns1.cs.princeton.edu, NS, IN >
dns1.cs.princeton.edu, 128.112.136.10, A, IN >
…
Third-level name server cs.princeton.edu contains A records for all hosts on that network.

penguins.cs.princeton.edu, 128.112.155.166, A, IN >

…
Name Resolution p Client does not know address of root name server, therefore it
sends query about penguins.cs.princeton.edu to the local name server in an UDP
packet.
q Local NS forwards the query to the root server.
r Root server finds no exact match. Best match is NS record for edu that points to server
a3.nstld.com. Therefore A record for a3.nstld.com is returned to local NS.
s Local NS resends the query to 192.5.6.32 since it has not got IP address for the query. t
edu server returns A record (128.112.129.15) for the best zone match princeton.edu u
Local NS resends the query to zonal NS princeton.edu and receives A record
(128.112.136.10) for cs.princeton.edu

Finally local NS resends the query to cs.princeton.edu and gets the A record
(128.112.155.166) for penguins.cs.princeton.edu
Local NS caches the response and sends it to the client. Client uses the IP address to
communicate with the server.

CS6551-COMPUTER NETWORKS Page 29

 

CS6551-COMPUTER NETWORKS Page 30