Wireless & Mobile Computing (CS-702 (C)) Unit 2 Notes

How unit 2 is examined

This unit covers BGP, RIP and OSPF routing, then TCP (handshake, flow and error control, silly window, congestion variants) and UDP; the marks sit in flow control and the bandwidth-delay numerical, then the routing protocols and silly window syndrome.

Routing Protocols: BGP - hidden network and autonomous system

Low weight

Definition. BGP (Border Gateway Protocol) is the exterior gateway, path-vector routing protocol that exchanges reachability between autonomous systems, and it runs over TCP port 179.

Key points.

An autonomous system (AS) is a group of networks and routers under one administration with one routing policy, identified by an AS number.
The networks inside an AS are hidden from the outside: BGP advertises only which network prefixes are reachable through which sequence of ASs, never the internal topology.
BGP is path-vector: each route carries the full AS path, so a router rejects any route that already contains its own AS, which prevents loops.
BGP is policy-based, so an AS chooses routes by business rules (prefer a customer, avoid a rival) and not by shortest distance alone.
BGP runs over TCP, so its updates are reliable and only changes are sent after the first full exchange; the Internet backbone between ISPs uses it.

Asked: [7 marks] (Dec 2020) What is BGP? Explain the characteristics of BGP?

An exterior gateway protocol

Definition. An exterior gateway protocol (EGP) routes between autonomous systems, while an interior gateway protocol (IGP) routes inside one autonomous system.

Basis	IGP	EGP
Scope	Inside one AS	Between different ASs
Examples	RIP, OSPF	BGP
Metric	Hop count, cost	Path attributes and policy
Goal	Best (shortest) path	Policy control and scalability
Hierarchy	Areas (OSPF)	AS-level, one AS is one node
Use case	Campus, enterprise, one ISP	ISP to ISP on the Internet

Asked: [7 marks] (Dec 2024) Differentiate exterior and interior gateway protocols.

Different messages of BGP

Definition. BGP peers exchange four message types over their TCP session.

Key points.

OPEN starts the session and carries the AS number, hold time and BGP identifier.
UPDATE advertises new routes with their path attributes or withdraws old ones.
KEEPALIVE is sent periodically to show the peer is alive and confirms an OPEN.
NOTIFICATION reports an error and closes the session.

Interior gateway protocol: RIP

Definition. RIP is an interior gateway protocol using distance vector routing: each router tells its neighbours its whole table of (destination, hop count) every 30 seconds, and routes are computed by the Bellman-Ford rule.

Key points.

Bellman-Ford: $d(x,y)=\min_v\{c(x,v)+d(v,y)\}$, the cost through neighbour $v$ plus $v$'s advertised cost.
The metric is hop count with maximum 15; 16 means infinity; RIP uses UDP port 520.
Example: A-B and B-C each cost 1. B advertises C=1 to A, so A adds C at cost 1+1=2 via B, and A's table becomes A=0, B=1, C=2.
Limitation: if C fails, A and B keep raising each other's cost for C (count to infinity), which slowly reaches 16.
Fixes: split horizon (never advertise a route back to the neighbour it came from), poisoned reverse and triggered updates.

Asked: [7 marks] (Jun 2025) Illustrate the principle of distance vector routing with the help of a suitable example.

OSPF

Definition. OSPF is a link-state interior gateway protocol in which every router floods the state of its directly connected links to all routers in the area, then runs Dijkstra's algorithm on the resulting map.

Key points.

A router learns its neighbours with Hello packets and describes each attached link (neighbour, cost) in a link-state advertisement (LSA).
OSPFv2 uses five messages: Hello, Database Description, Link-State Request, Link-State Update (carries LSAs) and Link-State Acknowledgement.
LSAs are flooded reliably to every router, and each acknowledges receipt, so all routers hold an identical link-state database.
Each router runs Dijkstra on that database to build a shortest-path tree, with cost inversely related to bandwidth.
Areas (backbone area 0) keep flooding local; OSPF runs directly over IP (protocol 89).

Asked: [7 marks] (Dec 2020) What is Open Shortest Path First (OSPF) protocol? How do routers use OSPFV2 message to broadcast information about the status of its directly connected link to all others routers?

Multiplexing and ports

Definition. Multiplexing lets many application processes share one IP address, and a 16-bit port number tells the transport layer which process gets each segment.

Key points.

The sender multiplexes data from many processes into segments, and the receiver demultiplexes by destination port.
Well-known ports are 0-1023 (HTTP 80, DNS 53), registered 1024-49151, dynamic 49152-65535.
TCP and UDP keep separate port spaces.

TCP: Segment format

Definition. A TCP segment is a 20-60 byte header followed by data.

Key points.

Header fields: source port and destination port (16 bits each), sequence number and acknowledgement number (32 bits each).
Then header length (4 bits), six flags (URG, ACK, PSH, RST, SYN, FIN), window size (16), checksum (16), urgent pointer (16), and options.
The sequence number counts the first data byte; the ACK number is the next byte expected.

Sockets

Definition. A socket is one end of a communication, identified by an IP address plus a port number.

Key points.

A TCP connection is uniquely identified by the pair of sockets (source IP, source port, destination IP, destination port).
Server calls: socket, bind, listen, accept; client calls: socket, connect; both then send, recv and close.

Synchronization

Definition. Synchronization is the SYN exchange in which both sides agree on their initial sequence numbers before data flows.

Key points.

Each side picks an initial sequence number (ISN) from a clock, so old duplicate segments are not accepted.
A SYN consumes one sequence number, so it is acknowledged as ISN+1.
Both directions must be synchronized, which needs two SYNs and two ACKs.

Three way hand shaking

Definition. The three-way handshake opens a TCP connection with SYN, SYN+ACK, ACK.

Key points.

Step 1: client sends SYN with seq=x.
Step 2: server replies SYN+ACK with seq=y and ack=x+1.
Step 3: client sends ACK with ack=y+1, and the connection is established.
The third message stops a delayed duplicate SYN from opening a false connection.

Variable window size and flow control

Definition. TCP flow control is a sliding window whose size is advertised by the receiver (rwnd) in every ACK, so the sender never sends more than the receiver's buffer can hold.

Key points.

The window is in bytes and is variable: the receiver shrinks it as its buffer fills and grows it as the application reads data.
The sender may have at most min(rwnd, cwnd) unacknowledged bytes outstanding.
A window of 0 stops the sender, which then probes with a persist timer until the window reopens.
Error control: sequence numbers detect loss, duplication and reordering, and the checksum detects corrupt segments, which are silently discarded.
Cumulative ACKs give the next byte expected, and a segment unacknowledged before the retransmission timeout is resent.
Fast retransmit resends a segment after three duplicate ACKs, without waiting for the timeout.

Formula. To fill the pipe, window $=$ bandwidth $\times$ RTT (bandwidth-delay product).

Example. Given 2 Mbps and RTT 300 ms.

Step	Working
Bits in flight	$2\times10^{6}\times0.3=600{,}000$ bits
In bytes	$600{,}000/8=75{,}000$ bytes
In KB	$75{,}000/1024\approx73.2$ KB
In segments (MSS 1460)	$75{,}000/1460\approx51$ segments

Optimal window = 75,000 bytes (about 73 KB). A smaller window leaves the line idle while the sender waits for ACKs.

Answer frame. Numerical: write the formula, convert Mbps and ms, give bytes and segments, then say a smaller window under-uses the line. Explain: open with the definition of sliding-window flow control, then points 1-3 for flow control and 4-6 for error control, and close by saying windows, ACKs, timers and checksums together give reliable end-to-end delivery.

Pitfall: Forgetting to divide by 8 leaves the answer in bits instead of bytes.

Asked: [7 marks] (Dec 2024) If WAN link is 2 Mbps and RTT between source and destination is 300 msec, what would be the optimal TCP window size needed to fully utilize the line? Asked: [7 marks] (Jun 2025) How flow control and error control issues are handled in TCP protocol?

Timeout and retransmission algorithms

Definition. ==The retransmission timeout (RTO) is set from measured round-trip times: RTO = SRTT + 4 x RTTVAR.==

Key points.

Smoothed RTT: $SRTT=(1-\alpha)SRTT+\alpha\cdot RTT$ with $\alpha=1/8$; RTTVAR uses $\beta=1/4$ on $|SRTT-RTT|$.
Karn's algorithm ignores RTT samples from retransmitted segments.
On each timeout the RTO is doubled (exponential backoff).

Connection control

Definition. Connection control opens a TCP connection by the three-way handshake and closes it by a four-segment FIN exchange, tracked by a state machine.

Key points.

Main states: CLOSED, LISTEN, SYN-SENT, SYN-RCVD, ESTABLISHED, FIN-WAIT-1, FIN-WAIT-2, CLOSE-WAIT, LAST-ACK, TIME-WAIT.
Each direction is closed separately with FIN and ACK (half-close).
TIME-WAIT lasts 2 x MSL so the last ACK is not lost; RST aborts a connection.

Silly window syndrome

Definition. Silly window syndrome is the degradation in which tiny segments are exchanged because the sender or receiver handles very small windows, wasting bandwidth on 40-byte headers.

Key points.

Receiver-side cause: a slow application reads a few bytes, so the receiver advertises a tiny window.
Sender-side cause: a slow application produces a byte at a time and the sender transmits each in its own segment.
Clark's solution (receiver): do not advertise a window until it can hold one MSS or half the buffer.
Delayed ACK (receiver): wait up to about 500 ms to acknowledge, so the window can grow first.
Nagle's algorithm (sender): send the first byte, then buffer data until the ACK returns or a full MSS is ready.

Asked: [7 marks] (Dec 2020) What are the causes of silly window syndrome? How it is avoided explain.

Example of TCP: Tahoe

Definition. ==TCP Tahoe controls congestion with slow start, congestion avoidance and fast retransmit, and after any loss it restarts from cwnd = 1 MSS.==

Key points.

Slow start doubles cwnd every RTT until it reaches ssthresh.
Congestion avoidance then adds 1 MSS per RTT.
On a timeout or three duplicate ACKs, ssthresh = cwnd/2 and cwnd = 1.

Reno

Definition. TCP Reno adds fast recovery to Tahoe, so after three duplicate ACKs it does not fall back to slow start.

Key points.

On three duplicate ACKs: retransmit, set ssthresh = cwnd/2 and cwnd = ssthresh + 3.
Each further duplicate ACK inflates cwnd by 1; the new ACK sets cwnd = ssthresh.
A timeout still sets cwnd = 1, as in Tahoe.

Sack etc.

Definition. TCP SACK (selective acknowledgement) lets the receiver report the non-contiguous blocks it has received, so the sender retransmits only the missing segments.

Key points.

SACK is negotiated in the SYN with the SACK-permitted option and reports blocks in the SACK option.
It recovers several losses in one window without waiting for timeouts, unlike Reno.

UDP: Message encapsulation

Definition. UDP is a connectionless, unreliable transport protocol whose messages travel as datagrams inside IP (protocol 17).

Key points.

Each UDP message is encapsulated in one IP datagram, with no handshake, ordering, ACK or retransmission.
It is used for DNS, streaming and voice, where speed matters more than reliability.

Format and pseudo header

Definition. The UDP header is 8 bytes: source port, destination port, length and checksum (16 bits each).

Key points.

The checksum also covers a 12-byte pseudo header: source IP, destination IP, zero byte, protocol 17 and UDP length.
The pseudo header is not transmitted; it checks that the datagram reached the right host.

Last-minute revision

BGP is a path-vector exterior protocol on TCP port 179; its messages are OPEN, UPDATE, KEEPALIVE, NOTIFICATION.
IGP works inside an AS (RIP, OSPF); EGP works between ASs (BGP).
RIP: distance vector, hop count, 16 = infinity, updates every 30 s, UDP 520; fixes are split horizon and poisoned reverse.
OSPF: link state, Dijkstra, LSAs flooded, Hello / DBD / LSR / LSU / LSAck, over IP protocol 89.
TCP header is 20-60 bytes; handshake is SYN, SYN+ACK, ACK.
Optimal window = bandwidth x RTT; 2 Mbps x 300 ms = 75,000 bytes.
RTO = SRTT + 4 x RTTVAR; Karn ignores retransmitted samples.
Silly window fixes: Clark and delayed ACK (receiver), Nagle (sender).
Tahoe resets cwnd to 1 on loss; Reno uses fast recovery; SACK reports received blocks.
UDP header is 8 bytes; pseudo header is 12 bytes and not sent.

Memory hooks

BGP = "Between Groups of Providers"; path vector means the whole AS path is carried.
RIP = "Rumour": routing by gossip from neighbours; OSPF = "Open map": everyone holds the full map.
Handshake: SYN, SYN-ACK, ACK, "Hi, Hi-back, Hi-again".
Nagle = sender waits; Clark = receiver waits.
Tahoe drops to 1, Reno halves and keeps going.

Coverage checklist

Routing Protocols: BGP- Concept of hidden network and autonomous system: covers Dec 2020 "What is BGP?"
An Exterior gateway protocol: covers Dec 2024 "Differentiate exterior and interior gateway protocols".
Different messages of BGP
Interior Gateway protocol: RIP: covers Jun 2025 distance vector example.
OSPF: covers Dec 2020 OSPF and OSPFv2 messages.
Multiplexing and ports
TCP: Segment format
Sockets
Synchronization
Three Way Hand Shaking
Variable window size and Flow control: covers Dec 2024 window size numerical and Jun 2025 flow and error control.
Timeout and Retransmission algorithms
Connection Control
Silly window Syndrome: covers Dec 2020 causes and avoidance.
Example of TCP: Taho
Reno
Sack etc.
UDP: Message Encapsulation
Format and Pseudo header

Account

Wireless & Mobile Computing (CS-702 (C)) - Unit 2 Short Notes

How unit 2 is examined

Routing Protocols: BGP - hidden network and autonomous system

An exterior gateway protocol

Different messages of BGP

Interior gateway protocol: RIP

OSPF

Multiplexing and ports

TCP: Segment format

Sockets

Synchronization

Three way hand shaking

Variable window size and flow control

Timeout and retransmission algorithms

Connection control

Silly window syndrome

Example of TCP: Tahoe

Reno

Sack etc.

UDP: Message encapsulation

Format and pseudo header

Last-minute revision

Memory hooks

Coverage checklist