CN Final Slides

Table of Contents
11 Lecture#11 (12/10) [CIDR Addressing]

1 Lecture#1 (05/09) [Course Overview]
12 Lecture#12 (17/10) [ARP, Transport layer]
2 Lecture#2 (07/09) [Encoding Schemes, Link Layer,
Framing] 13 Lecture#13 (31/10) [TCP]
3 Lecture#3 (12/09) [Error Detection] 14 Lecture#14 (02/11) [TCP]
4 Lecture#4 (14/09) [CRC, PPP Protocol] 15 Lecture#15 (07/11) [NAT, Reliable Data Transfer]
5 Lecture#5 (19/09) [MAC protocols, slotted Aloha, pure 16 Lecture#16 (14/11) [Reliable Data Transfer]
Aloha]
17 Lecture#17 (16/11) [Go-back-N (GBN), Selective Repeat
6 Lecture#6 (21/09) [Ethernet LAN] (SR)]
7 Lecture#7 (26/09) [Internetworks, network address, IP 18 Lecture#18(21/11) [DNS]
address]
19 Lecture#19(23/11) [HTTP, Proxy]
8 Lecture#8 (28/09) [Host-to-host communication in
internetwork] 20 Lecture#20(28/11) [SMTP, ICMP]
9 Lecture#9 (08/10) [IP packet structure, IP fragmentation] 21 Lecture#21 (05/12) [Intra-domain routing, link-state,
distance-vector]
10 Lecture#10 (10/10) [IP fragmentation, Router’s
Forwarding] 22 Lecture#22 (07/12) [Inter-domain routing, BGP]
Mahavir Jhawar Computer Networks Ashoka University 128 / 243

Address Resolution Protcol
N1 190.135.170.160/28
- Assume ip address of Laptop1 is 190.135.170.162

- Suppose Laptop1 wants to send an ip packet to destination 190.135.170.163
- It must first finds out whether the destination is in the same subnetwork or off the subnetwork
- It computes component-wise AND between its subnet mask 255.255.255.240 and the destination
190.135.170.163.
- The result is - 190.135.170.162/28 which is the address of its own subnetwork. Thus the destination is
in the same subnetwork
- Next, Laptop1 requires the MAC address of the destination so that a link-layer frame can carry the ip
packet to the destination
- It uses Address Resolution Protocol (ARP) to acquire the MAC address of the destination

N1 190.135.170.160/28
1 ARP Query
- Laptop1 prepares an ARP packet
- The ARP packet is put into the link layer frame
- The frame is then broadcasted into the
subnetwork
Protocol Types
0x0806 Address Resolution Protocol (ARP)

0x0800 IPv4

N1 190.135.170.160/28
2 ARP Response
- The destination host prepares an ARP response
- The ARP response packet is put into the link
layer frame
- The frame is then sent to Laptop0

ARP Tables
- Every host maintains an ARP table where they keep the

mappings between (host ip, host MAC) for different hosts
in its subnetwork
- Once Laptop1 acquire MAC of Laptop0 (using ARP), it
updates its ARP table as follows
190.135.170.163 0010.1124.A4B7 timestamp
- In the near future if Laptop1 has an ip packet to send to
190.135.170.163, it doesn’t need to run ARP.
- It can consult its ARP table and get the MAC address of
190.135.170.163

ARP-Packet Fields
- Hardware Type
- This field specifies the link-layer protocol type.
Example: Ethernet is 0x0001
- Protocol Type
- This field specifies the internetwork protocol for
which the ARP request is intended.
- For IPv4, this has the value 0x0800
- Hardware length (HLEN)
- Length (in octets) of a hardware address.
Ethernet address length is 6.
- Is ARP a link-layer protocol or a network-layer
- Protocol length (PLEN)
protocol?
- Length (in octets) of internetwork addresses.
- It can be seen as a network-layer protocol as ARP
The internetwork protocol is specified in
packets are encapsulated within a link-layer frame
PTYPE. Example: IPv4 address length is 4.
- It can be seen as a link-layer protocol as ARP
- Operation Code
packets contains link layer addresses
- Specifies the operation that the sender is
- Thus, ARP is a protocol that straddles the boundary
performing: 1 for request, 2 for reply.
between the link layer and network layers

Gateway Router
N1 121.234.218.128/26
N6 121.234.218.192/26
- Suppose, Laptop1’s address is 121.234.218.130

- When Laptop1 wants to contact 121.234.218.195, it must determine if the destination is in the same
subnetwork or off the subnetwork
- It computes component-wise AND between its subnet-mask 255.255.255.192 and 121.234.218.195
- The result is - 121.234.218.192/26, which is not the address of its own subnetwork
- Thus the destination is off its subnetwork! What next?
Every host is given the information of a router that serves as a default exit path for ip packet travelling
outside the subnetwork
- In particular, the host is given the ip address of the gateway-router interface through which the
gateway router is connected to the subnetwork of which host is a part
- In case Laptop1 has to send an ip packet to a destination which is off the subnetwork, it must first
send it to the default gateway interface

A Milestone Reached
Transport Layer

A New Layer: Extending Host-to-host delivery to
process-to-process delivery
We first discuss network applications

- Network Applications
- At the core of network application development is writing programs that run on different end-systems
and communicate with each other over the network
- Examples: Web application - the browser program running in the user’s host; and the Web server
program running in the Web server host; application; Instant messaging chat application; Remote
Login; Voice over IP etc
Network Application Architecture dictates how the application is structured over the various end
systems
- Two major paradigms: the client-server architecture or the peer-to-peer (P2P) architecture

Client-Server Architecture
Client-Server Architecture
- In a client-server architecture, there is an always-on host, called the server which services requests from
many other hosts, called clients.
- The server-host runs the server-application; client-hosts run the client-application
- A classic example is the Web application for which an always-on Web server (server-application)
services requests from browsers (client-application) running on client-hosts

Extending Host-to-host delivery to process-to-process
delivery
- Suppose you are downloading web pages from

three different web sites, and also running a - This state is kind of a door, created specifically
instant messaging application. for a process, and through this door application
- You therefore have four client processes running data travels between the process and the
- three http, and one for instant messaging network layer
- The state is formally referred to as a socket!
- As of now, the network layer in your system - Sockets are unique to processes, and they are
receives ip packets from the link layer, extracts assigned unique identifiers
IP payload, and finally hand it over to the right
client-application process
- Finally, we require protocols (running at this
- In this case, every IP payload must be handed new layer) for opening, closing and maintaining
over to one of the four client-processes! of these sockets!
- How does the network layer figure the correct
client process?
- The new layer is called Transport Layer
- Two prominent transport layer protocols are:
- We require an additional layer, sitting between TCP and UDP
Network and Application layers, who can
establish (and perhaps maintain) a ”state”
between a given client process and the network
layer

An Additional Service Feature of Transport Layer
- Reliable Communication
- the problem of reliable communication is of central importance to networking
- The Reliable Communication Goals:
- no transferred data bits are corrupted or lost, and
- all are delivered in the order in which they are sent
- Thus, we are looking for a guaranteed delivery of data to the destination

Table of Contents

Aloha]
address]
distance-vector]

Transmission Control Protocol (TCP)
- TCP ensures reliable communication between

two processes
Top-down flow: Application Layer to Physical Layer

- A client application now hand over its application data to network layer with the help of a transport
layer protocol, this means
- the application process puts its data into an application-layer packet and hands it over to a
transport layer protocol
- the transport layer protocol encapsulates the application packet into a transport layer packet
(we call it segment) and hands it over to network layer
- the network layer encapsulates the segment into an IP packet and hands it over to link layer
- the link layer further encapsulates the ip packet into a link layer frame and hands it over to
physical layer, and finally
- the physical layer convert the frame into appropriate signals and transmits into the medium


- CApp2 provides two inputs to TCP:

IP address of H2, and
the port number 500, where SApp2 is listening for incoming
connections
- TCP creates a socket and assigns a unique port to it - say 345

- It then tries to connect to SApp2 (at H2) with a connection request
Connection Acceptance at SApp2
- TCP accepts the connection and opens a new socket specific to this
Server Side Application: SApp2 connection between CApp2 and SApp2
- This new socket is now identified by the following tuple
- SApp2 is running at server H2 S.P. 345 D.P. 500
- It takes help of TCP for incoming traffic S. IP H1 D. IP H2
- SApp2 runs in always-on mode This marks the end of connection establishment between CApp2 and
- TCP opens a socket for SApp2 process SApp2
and assigns a unique identifier (port
number) - say 500 I Data Transfer
- The incoming traffic for SApp2 must carry - Subsequently, the communication data between CApp2 and SApp2
along this port number - enters/leaves CApp2 through the socket with port number 345, and
- enter/leaves SApp2 through the socket having identifier as the
Client Side Application: CApp2 above 4 tuple
The well-known ports are listed at https://www.iana.org/assignments/
- CApp2 is running at client H1 service-names-port-numbers/service-names-port-numbers.txt
- It takes help of TCP for its communication
to SApp2 running at H2

TCP Sockets

TCP Sockets

TCP Segment Structure
Flag bits
- URG set to ”1” indicates presence of some
urgent data. The location is given by 16-bit
urgent data pointer field.
- ACK - used for reliable data transfer protocols.
- PSH set to ”1” indicates that the receiver
should pass the data to the upper layer
immediately
- RST, SYN, and FIN are used for TCP
connection establishment and tear down
- Sequence and Acknowledgement Number fields

are used by TCP sender and receiver to
implement reliable data transfer protocol
- Receive Window is used for flow control
- Header Length The 4-bit field specifies the
length of the TCP header in 32-bit words.

TCP Sockets

TCP Sockets
Kurose

TCP Handshake
- TCP is said to connection-oriented because before one application process can begin to send data to another, the two
process must first handshake with each other to establish the parameters of the ensuing data transfer.
- Step- 1
- The client-side first sends a special TCP segment to the
server-side TCP
- This special segment contains no application-layer data.
- One of the flag bits in this segment’s header, the SYN
bit, is set to 1
- Step- 3
- This special segment is called a SYN segment
- Upon receiving the SYNACK segment, the client also
- Step- 2 allocates buffers and variables to the connection
- Once the IP packet containing the TCP SYN segment - The client host then sends the server yet another
arrives at the server host, the server extracts the SYN segment which acknowledges the server’s
segment, allocates the TCP buffers and variables to the connection-granted segment.
connection, and sends a connection-granted segment
back to the TCP client - The SYN bit, in this segment, is set to ”0”
- The connection-granted segment (referred to as - This segment may carry client-to-server data in the
SYNACK segment) also contains no application-layer segment payload !!
data; the SYN bit is also set to 1

TCP Connection Close
src: Kurose

Socket Programming with TCP
- Because sockets play a central role in client/server applications, client/server application development is also referred to
as socket programming

À À
Client Server
import socket import socket
destHost=’ipAddress’ hostIP=’ ’
port=8728 port=8728
ClientSocket= socket.socket( ServerSocket= socket.socket(
socket.AF_INET,socket.SOCK_STREAM) socket.AF_INET,socket.SOCK_STREAM)
ClientSocket.connect((destHost, port)) ServerSocket.bind((hostIP,port))
query = int(input(”Enter a number: ”)) ServerSocket.listen(1)
ClientSocket.send((str(query)).encode()) (ClientSocket,Address) = ServerSocket.accept()
response = ClientSocket.recv(2048).decode() z = ClientSocket.recv(1024).decode()
print(”Number Squared:”, response) x = int(z)
ClientSocket.close() w = x*x
ClientSocket.send((str(w)).encode())
ClientSocket.close()
Creating Socket Socket types

import socket socket.SOCK_STREAM TCP
s = socket.socket(addr_family, type) socket.SOCK_DGRAM UDP
Address Families Example: TCP Connection

socket.AF_INET IPv4 import socket
socket.AF_INET6 IPv6 s = socket(AF_INET,SOCK_STREAM)
À À
Client Server
import socket import socket
destHost=’ipAddress’ hostIP=’ ’
port=8728 port=8728
cs= socket.socket( ss= socket.socket(
socket.AF_INET,socket.SOCK_STREAM) socket.AF_INET,socket.SOCK_STREAM)
cs.connect((destHost, port)) ss.bind((hostIP,port))
query = int(input(”Enter a number: ”)) ss.listen(1)
cs.send((str(query)).encode()) (connection,Address) = ss.accept()
response = cs.recv(2048).decode() z = connection.recv(1024).decode()
print(”Number Squared:”, response) x = int(z)
cs.close() w = x*x
connection.send((str(w)).encode())
connection.close()

Table of Contents

Aloha]
address]
distance-vector]

User Datagram Protocol (UDP)

Popular Internet applications and their underlying transport-layer protocols
Application Application-layer Underlying

Protocol Transport-layer
Protocol
Electronic mail SMTP TCP

Remote terminal access Telnet TCP
Web HTTP TCP
File transfer FTP TCP
Name translation DNS Typically UDP
Routing Protocol RIP Typically UDP
Ports for Common Services
Application-layer Protocols Ports
FTP 21
SSH 22
Telnet 23
SMTP 25
HTTP 80
HTTPS 443

A Client-Server Network Application: DHCP
- DHCP is built on a client-server model.

- DHCP Server refers to a host providing initialization
parameters through DHCP.
- DHCP Client refers to a host requesting initialization
parameters from a DHCP server.
DHCP request
Host ip address
Subnet mask
- We have learned to assign ip addresses to each Gateway ip
host/interface manually Local DNS server ip
- Can this be done on an auto mode ?
- DHCP uses UDP as its transport protocol !

- The Dynamic Host Configuration Protocol (DHCP)
provides configuration information (ip addresses, - DHCP messages from a client to a server are sent to
network addresses and additional configuration the ’DHCP server’ port 67
parameters) to hosts on a network.

DHCP Servers
- Where does a DHCP server sit ?

- Simple Case: A DHCP server in each subnetwork in the internetwork
- The Other Case: Every subnetwork need not have a DHCP server.
- In this case we have relay agents
- Routers do the role of relay agents

DHCP: Step1: DHCP Server Discovery
Laptop2 → ALL

DHCP: Step2: DHCP Server Offer
DHCP Server → ALL

DHCP: Step3: DHCP Request
Laptop2 → ALL

DHCP: Step4: DHCP ACK
DHCP Server → ALL

Table of Contents

Aloha]
address]
distance-vector]

Private IP Addressing
- The Internet has grown beyond anyone’s expectations.

- Sustained exponential growth continues to introduce new challenges.
- One challenge is a concern within the community that globally unique IP address space will be
exhausted.
- The idea of private ip-addressing means we don’t have to acquire as many ip addresses as the number
of hosts present in our network
- This idea makes it optimise the uses of globally unique ip-addresses
- You can have acquire one globally unique ip address and still can support tens of thousands hosts in
your network!!
Network Address Translation (Protocol) : allows a network administrator to use ip addresses for its
hosts in the network which are not globally unique!
- We call these ip addresses (not globally unique) - private ip addresses
- The Internet Assigned Numbers Authority (IANA) has reserved the following three blocks of the IP
address space for private ip addresses:
10.0.0.0 10.255.255.255 (10/8 prefix)

172.16.0.0 172.31.255.255 (172.16/12 prefix)
192.168.0.0 192.168.255.255 (192.168/16 prefix)

Network Address Translation (NAT)
- With the help of NAT, internetwork can assign private addresses to its hosts while still allowing them
to communicate with the hosts any where in the world
- For NAT to work, the gateway router of the internetwork must be NAT enabled
- A NAT enabled router keeps a NAT table
- NAT works as follows:
Source: Kurose

Universal Plug and Play (UPnP) Protocol
- Consider running a server application on a host B whose ip address is private.

- How do clients from outside B’s network connect to the server application?
- A Solution: Universal Plug and Play (UPnP) protocol
- Both, Host B and NAT enabled gateway router, must be UPnP enabled!!
- UPnP provides allocates B a NAT mapping between
(PrivateIP(B), PortNumber(SApplication)) and (PublicIP, PublicPortNumber)
- NAT accepts the request and creates the mapping
- A client can creates a TCP connection to (PublicIP, PublicPortNumber) to connect to server
application running on B.

Reliable Data Transfer (RDT)
The reliable data transmission goal: a guaranteed delivery of data to the destination
- no transferred data bits are corrupted or lost, and
- all are delivered in the order in which they are sent
- You might need a RDT protocol at the link layer if the source and destination in the same subnetwork !
- You might need a RDT protocol at the transport layer if the source and destination are in different
network !
- IP protocol at the network layer has not implemented any RDT!
- We discuss the problem of RDT as a standalone problem - but use link layer framework for simple
notations!
Reliable
Source Link Layer Destination
Physical Layer
Unreliable

Reliable Data Transfer
Reliable
Source Destination
rdt.send() deliver.data()
rdt.ss rdt.rs
udt.send() Link Layer rdt.rcv()

Physical Layer
Unreliable
- rdt.ss: reliable data transfer protocol (sending side)

- rdt.rs: reliable data transfer protocol (receiving side)
- udt: un-reliable data transfer protocol
- rdt.send(): accepts data from upper layer
- udt.send(): sends data to unreliable layer below
- rdt.rcv(): receives the data from layer below
- deliver.data(): Deliver data to upper layer

rdtA
Assumptions

No error in data

No frame lose

No out of order frames

Receiver is able to receive data as fast as the sender happens to send data
rdt.send(data) rdt.rcv(frame)
− − − − − − − − − − −− − − − − − − − − − − −−
frame = makeframe(data) data = Extract(frame)
udt.send(frame) deliver.data(data)
Wait from Wait from

start start
Upper Layer Layer Below
rdtA.ss rdtA.rs

rdtB : Handling Data Error
Assumptions
rdt.send(data)
− − − − − − − − − − −−
? No error in data SndFrame = MakeFrame(data, checksum)
udt.send(SndFrame)
No frame lose
No out of order rdt.rcv(RcvFrame) ∧ isNAK(RcvFrame)

Wait from Wait for
frames start
Upper Layer ACK/NAK
− − − − − − − − − − −−
udt.send(SndFrame)
Receiver is able
to receive data
rdt.rcv(RcvFrame) ∧ isACK(RcvFrame)
as fast as the − − − − − − − − − − −−
sender happens ⊥
to send data
rdtB.ss
rdt.rcv(RcvFrame) ∧ isError(RcvFrame)
Wait from − − − − − − − − − − −−
start
Layer Below SndFrame = MakeFrame(NAK)
udt.send(SndFrame)
rdt.rcv(RcvFrame) ∧ isErrorFree(RcvFrame)
− − − − − − − − − − −−
data = Extract(RcvFrame)
SndFrame = MakeFrame(ACK)
udt.send(SndFrame)
rdtB.rs
Table of Contents

Aloha]
address]
distance-vector]

rdtC : Handling Errors in ACK/NAK
rdt.send(data)
− − − − − − − − − − −−
SndFrame = MakeFrame(0,data, checksum)
udt.send(SndFrame)
rdt.rcv(RcvFrame) ∧ [isNAK(RcvFrame)
Wait for 0call Wait for k isCorrupt(RcvFrame)]
start
from ULayer ACK0/NAK0 − − − − − − − − − − −−
udt.send(SndFrame)
rdt.rcv(RcvFrame) ∧ isACK(RcvFrame) rdt.rcv(RcvFrame) ∧ isACK(RcvFrame)

∧ IsErrorFree(RcvFrame) ∧ IsErrorFree(RcvFrame)
− − − − − − − − − − −− − − − − − − − − − − −−
⊥ rdt.send(data) ⊥
− − − − − − − − − − −−
udt.send(SndFrame)
rdt.rcv(RcvFrame) ∧ [isNAK(RcvFrame)
k isCorrupt(RcvFrame)] Wait for Wait for 1call
− − − − − − − − − − −− ACK1/NAK1 from ULayer
udt.send(SndFrame)
rdtC.ss

rdtC : Handling Errors in ACK/NAK
rdt.rcv(RcvFrame) ∧ [IsErrorFree(RcvFrame)
∧ HasSeq0(RcvFrame)
− − − − − − − − − − −−
rdt.rcv(RcvFrame) ∧ IsCorrupt(RcvFrame) Data = Extract(RcvFrame) rdt.rcv(RcvFrame) ∧ isCorrupt(RcvFrame)
− − − − − − − − − − −− Deliver(Data) − − − − − − − − − − −−
SndFrame = MakeFrame(NAK, Checksum) SndFrame = MakeFrame(ACK, Checksum) SndFrame = MakeFrame(NAK, Checksum)
udt.send(SndFrame) udt.send(SndFrame) udt.send(SndFrame)
Wait for 0call Wait for 1call

start
from BLayer from BLayer
rdt.rcv(RcvFrame) ∧ [isErrorFree(RcvFrame) rdt.rcv(RcvFrame) ∧ [IsErrorFree(RcvFrame) rdt.rcv(RcvFrame) ∧ [isErrorFree(RcvFrame)

∧ HasSeq1(RcvFrame) ∧ HasSeq1(RcvFrame) ∧ HasSeq0(RcvFrame)
− − − − − − − − − − −− − − − − − − − − − − −− − − − − − − − − − − −−
SndFrame = MakeFrame(ACK, Checksum) Data = Extract(RcvFrame) SndFrame = MakeFrame(ACK, Checksum)
udt.send(SndFrame) Deliver(Data) udt.send(SndFrame)
SndFrame = MakeFrame(ACK, Checksum)
udt.send(SndFrame)
rdtC.rs

rdtD : Handling Lossy Erroneous Medium
How to handle lossy frames? Medium can lose frames !!

- Imagine a situation where a sender after sending a frame is waiting for an ACK.
- If the sender doesn’t receive ACK, it could be because
1 the frame got lost, or
2 the response ACK got lost, or
3 the delivery of the frame/ACK is delayed!
What is the way out?

- A solution: Wait long enough to be certain that a frame/ACK has been lost ?
- If an ACK is not received with in this time, the packet is retransmitted.
- Looks like, this would resolve both 1 and 2 .

rdtD : Handling Lossy Erroneous Medium
Timeout: Sender to judiciously choose a time value such that frame loss/ACK is likely to have
happened (although not guaranteed).
- If ACK not received before the ”Timeout”, do retransmission!
What about case 3 ?

- Due to a large delay, the sender my retransmit
even though data packet and ACK have not
been lost!
- This introduces duplicate packets in the
medium

Stop and Wait RDT Protocol
Update our existing protocol with the following:

- Timeout: to resolve delay

rdtD : Stop and Wait Protocol
rdt.rcv(RcvFrame) rdt.send(data)
− − − − − − − − − − −− − − − − − − − − − − −−
⊥ SndFrame = MakeFrame(0,data, checksum) rdt.rcv(RcvFrame) ∧ [isCorrupt(RcvFrame)
udt.send(SndFrame) k isACK(RcvFrame, 1)]
StartTimer − − − − − − − − − − −−
⊥
timeout
Wait for 0call Wait for − − − − − − − − − − −−
start
from ULayer ACK0 udt.send(SndFrame)
StartTimer
rdt.rcv(RcvFrame) ∧ isACK(RcvFrame, 0)
rdt.rcv(RcvFrame) ∧ isACK(RcvFrame, 1) ∧ IsErrorFree(RcvFrame)
∧ IsErrorFree(RcvFrame) − − − − − − − − − − −−
− − − − − − − − − − −− rdt.send(data) StopTimer
StopTimer − − − − − − − − − − −−
udt.send(SndFrame)
StartTimer
timeout
− − − − − − − − − − −− Wait for Wait for 1call
udt.send(SndFrame) ACK1 from ULayer
StartTimer
rdt.rcv(RcvFrame) ∧ [isCorrupt(RcvFrame) rdt.rcv(RcvFrame)

k isACK(RcvFrame, 0)] − − − − − − − − − − −−
− − − − − − − − − − −− ⊥
⊥
rdtD.ss

Efficiency of Stop-and-Wait Protocol
Definitions (Recall)
Bandwidth The bandwidth of a medium is given by the number of bits that can be transmitted
(read - emitted into the medium) over the medium in one second.
- Throughput ≡ Effective Bandwidth !!
Latency of a Message Latency of a message bn . . . b1 is the amount of time that elapsed from
when b1 got emitted by sender into the medium until bn is received by the receiver
Latency = Transmission time + Propagation time + Queuing time !!
Message Size
Transmission time of a message is equal to
Bandwidth
Propagation time is the time required for a single bit to travel from sender to receiver
Queuing time is set to 0 for our case now
RTT The round trip time of a message = 2 × Latency!!
Suppose a link between A and B has bandwidth 1 Mbps and propagation delay 20 milliseconds.
Compute the latency of a 1000-bit size frame.
- Transmission delay = 1000/106 = 1/103 = 1 millisecond
- Propagation delay = 20 milliseconds.
- The latency of a 1000-bit size frame on this link is 21 milliseconds.

Delay × Bandwidth Product
Delay × Bandwidth Product

- This product measures the maximum number of bits that can fill the link!
- 4 × 5 is the maximum number of bits that can fill the link.

- There can be no more than 20 bits at any time on the link.

The Efficiency of Stop-and-Wait RDT
L
In stop-and-wait RDT, the Timeout is set to M + 2T seconds, where
- the link has M bits/second as bandwidth, frame size as L bits, and one-way propagation delay of T
seconds.
Efficiency Calculation

An Example
- A link has a transmission speed of 106 bits/sec.

- It uses frames of size 1000 bytes each.
- Assume that the acknowledgment has negligible transmission delay, and that its propagation delay is
the same as the data propagation delay.
- Also assume that the processing delay at nodes are negligible.
- It is give that the efficiency of the stop-and-wait protocol in this setup is exactly 25%.
- Compute one-way propagation delay (in milliseconds) ?.
1 1 1
- The efficiency of the Stop-and-Wait is given by = = .
1+2T (M/L) 1+2T (106 /8000) 1+0.25T ×103
1
- The later is equal to 4 in this problem.
1 1
- Thus, = 4.
1+0.25T ×103 )
- This implies, T = 12 milliseconds.

Another Example
- Suppose that the Stop-and-Wait protocol is used on a link with a bit rate (bandwidth) of 64
kilobits/sec
- Link has 20 milliseconds propagation delay.
- Assume that the transmission time for the acknowledgment and the processing time at nodes are
negligible.
- Compute the minimum frame size in bytes to achieve a link utilization of at least 50%
- We want 1
1+2T (M/L)
≥ 1
2, where T = 20/103 and M = 64 × 103 .
- Solving for L, we get L ≥ 2560 bits = 320 bytes.

Table of Contents

Aloha]
address]
distance-vector]

How to Improve Stop-and-Wait?
A solution: sender is allowed to send multiple frames without waiting for ACK/NAKs
- The technique is known as pipelining
- What are the consequences ?
At the sender’s end
- In Stop-and-wait RDT, the sender would wait for at most one unacknowledged frame
- Here, the sender will be waiting for more than one unacknowledged frames
- This requires more than two sequence numbers 0 and 1 to be used
- Managing out of order ACKs
At the receiver’s end
- Managing out of order frames
Two approaches to pipelining
1 Go-Back-N (GBN)
2 Selective Repeat (SR)

Go-Back-N (GBN)
GBN - the Sender side
- Though GBN allows a sender to transmit multiple frames without waiting for an acknowledgement
- But, the sender is constrained to have no more than some maximum allowable number, N, of
unacknowledged frames in the pipeline.
At any point in the protocol, the Sender-side view can be summarised as follows:
- base to be the sequence number of the oldest unacknowledged frame.

- nextseqnum to be the smallest unused sequence number (the sequence no of the next frame to be sent)
Four intervals in the range of sequence numbers can be identified
- [0, base − 1]: correspond to frames that have already been transmitted and acknowledged
- [base, nextseqnum − 1]: corresponds to frames that have been sent but not yet acknowledged.
- [nextseqnum, base + N − 1] can be used for frames that can be sent immediately, should data arrive
from the upper layer
- [base + N, ] cannot be used until an unacknowledged frame currently in the pipeline has been
acknowledged !!

Go-Back-N (GBN)
- Are we to run 8 ”timers” (for unacknowledged packets {6, . . . , 13}) each beginning after the
respective packets having left the sender?
- Yes, we do - but there is a constraint here !
If a timeout occurs for the timer of the base packet, then the sender resends all unacknowledged
packets with the sequence numbers lying in [base, nextseqnum − 1]
At any point in the protocol, the Receiver-side view can be summarised as follows:

Go-Back-N (GBN): The Receiver-side
A sample run:

Go-Back-N (GBN): The Receiver-side
The Receiver-side works as follows:

- When a frame with sequence number k arrives, the receiver takes
the following action.
- If k < rcv− base or k > rcv− base + N − 1, then the frame is
outside the receiver’s window and it is discarded.
- If rcv− base ≤ k ≤ rcv− base + N − 1, then the frame is within the
receiver’s window and it is accepted.
- Now the receiver needs to decide whether or not to send an ACK.
- Let ` denote the largest sequence number in
[rcv− base, rcv− base + N − 1] not yet acknowledged, such that all
frames with sequence numbers less than or equal to ` have been
received.
- The receiver acknowledges the receipt of `, even if higher-numbered
packets have been received.
- This acknowledgment is said to be cumulative.
- It then sets rcv− base = ` + 1 and adjusts receive window as
[` + 1, ` + N]

Go-Back-N (GBN): The Sender-side
The Receiver-side works as follows:

The Sender-side works as follows: - When a frame with sequence number k arrives, the
- An ACK for a packet with seq. no. r will be taken to receiver takes the following action.
be a cumulative acknowledgment, indicating that all - If k < rcv− base or k > rcv− base + N − 1, then the
packets with seq. no. up to and including r have been frame is outside the receiver’s window and it is
correctly received at the receiver. discarded.
- It then adjust the window as [r + 1, r + N] - If rcv− base ≤ k ≤ rcv− base + N − 1, then the frame
Handling Timeout Event: is within the receiver’s window and it is accepted.
- If a timeout occurs for the timer of the base packet, - Now the receiver needs to decide whether or not to
then the sender resends all unacknowledged packets send an ACK.
with the sequence numbers lying in - Let ` denote the largest sequence number in
[base, nextseqnum − 1] [rcv− base, rcv− base + N] not yet acknowledged, such
that all frames with sequence numbers less than or
equal to ` have been received.
- The receiver acknowledges the receipt of `, even if
higher-numbered packets have been received.
- This acknowledgment is said to be cumulative.
- It then sets rcv− base = ` + 1 and adjusts receive
window as [` + 1, ` + N]

GBN: A sample view of Sender and Receiver Interaction
Interactive animation of GBN - https://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/cw/

content/interactiveanimations/go-back-n-protocol/index.html

GBN Receiver-side
Source: Kurose

GBN Sender-side
Mahavir Jhawar Source: Networks

Computer Kurose Ashoka University 192 / 243
Selective Repeat (SR) RDT
GBN improves on the simple stop-and-wait protocol by allowing the sender to ”fill the pipeline” and
thus avoiding the channel utilisation problem.
- However GBN suffers badly on the following account - a single packet error can cause GBN to
retransmit a large number of packets, unnecessarily.
The Selective Repeat protocol avoid unnecessary retransmission by having the sender retransmit only
those that it suspects were lost or corrupted on way to the receiver.
- This individual retransmission require that the receiver individually acknowledge correctly received
packets

Selective Repeat (SR) RDT

SR: With a Finite Range of Sequence Numbers
In stop-and-wait protocol, the maximum number of unacknowledged frames at any time was allowed to
be ”one”
- The available sequence numbers are two: ”0” and ”1”
In SR, the window-size is set to N > 1, i.e., the maximum number of unacknowledged frames at any
time was allowed to be ”N”.
- Can the available sequence numbers be limited to N + 1, say {0, 1, 2, . . . , N}??

In SR, the window-size is set to N > 1, i.e., the maximum number of unacknowledged frames at any
time was allowed to be ”N”.
- Can the available sequence numbers be limited to 2N − 1, say {0, 1, 2, . . . , 2N − 2}??
- The answer is No!
- It can be shown that the following bound is necessary
Total # of sequence numbers

N ≤
2

Total # of sequence numbers
We now show that the condition N ≤ 2 is not sufficient!
- Let’s take the available sequence numbers be limited to 2N, say {0, 1, 2, . . . , 2N − 1}??
- Consider the following:
Observation: The above situation could occur as we allowed some of the packets to be delayed long
enough before they are delivered at the receiver.
- In reality, 2N-size sequence number set, for a window of size N, provided it is taken care that a packet
cannot live in the network for longer than some fixed maximum amount of time.

Table of Contents

Aloha]
address]
distance-vector]

Next in line: Application Layer

Namespace
In your system, every file can be accessed if you know - The path to the WebFile is referred to as URI (Uniform
the path to locate it. Resource Identifier)
- For example,
- URIs are a convention for locating files globally
- As the target file exists inside a host, URIs must resolve
˜/Bob/Documents/Pictures/bob-certificate.jpg to the IP address of the host
- For this resolution to be efficient, the URIs must follow
is the path to locate the file bob-certificate.jpg in Bob’s some hierarchical structure
computer.
- Sharing path to a file over a computer network is
similar!!
- Suppose, Bob wants others to be able to access
bob-certificate.jpg and additional 10 files, from any
where, over the network

Namespace
Problem: Your system is given an URI that it wants to visit over the network to retrieve an object file
Each URI has two components

- the hostname of the server that house the object, and
- the object’s path name within the server
- Exmaple
- yourUniversity.edu.in/CS/phd.html
- host name: yourUniversity.edu.in
- object: phd.html
- object’s path: CS/phd.html
- Problem: How to find out ”yourUniversity.edu.in” ’s IP address

- You should take help of the DNS service to determine the IP address of the host
”www.yourUniversity.edu.in”
Hierarchy in host naming: in the name www.yourUniversity.edu.in we observer the following

- yourUniversity.edu.in is the domain name of the network in which this host resides
- .in suggests that the network is residing in India
- .edu suggests it is an educational institute in India

Domain Name System (DNS)
For a thorough discussion on DNS, refer to

- Lecture discussions and
- Section 2.5 (DNS - The Internet’s Directory Service) of the course reference book - Kurose and Ross
Book (Fifth Edition).

DNS
Hierarchy in host naming: in the name yourUniversity.edu.in we observer the following
- yourUniversity.edu.in is the domain name of the network in which this host resides
- .in domain suggests that the network is residing in India
- .edu domain suggests it is an educational institute in India
Top-level Domains In simpler terms, a TLD is everything that follows the final ”dot” of a domain
name.
- A list of all valid top-level domains is maintained by the IANA https://www.iana.org/ and is updated
from time to time https://data.iana.org/TLD/tlds-alpha-by-domain.txt
The DNS uses large number of servers, organised in a hierarchical fashion and distributed around the
world.
- The mapping of the corresponding IP for a given URI is present in one kind of DNS server; but to
reach that server you trace through several other DNS servers; the trace path is determined by the
hierarchy present in the host name
- There are three classes of DNS servers that are present in a typical trace path

DNS
Authoritative DNS Servers Every network must keep its DNS mapping in a DNS server - called its
authoritative DNS server (or Name server).
Top-level domain (TLD) Servers These are responsible for top-level domains. For a given DNS
mapping, an authoritative DNS server, depending on the entry’s top-level domain, would contact a
TLD server who manages a list of authoritative DNS servers who are keeping hostname-to-IP address
of specific top-level domains. Appropriate record is registered with the TLD server.
Root DNS Servers They maintain details of TLD servers.
DNS Records The DNS servers store various types of records, including records that provide
hostname-to-IP address mappings. These are called Resource Records (RRs)
Resource Records Type:
Type Name Value
A Hostname IP address
NS Domain Host name of Authoritative DNS for
the Domain
CNAME Alias host name Canonical host name
MX Alias host name of mail server Canonical host name of mail server

Table of Contents

Aloha]
address]
distance-vector]

HTTP
- HyperText Transfer Protocol (HTTP): An Application Layer Sample HTTP Request Message
Protocol [https://datatracker.ietf.org/doc/html/rfc2616]
- Modelled on client-server architecture
- HTTP client side ≡ Web Browser
- HTTP server side ≡ Web Server
- HTTP defines how web-browser requests webpages from web-servers
HTTP Request
- Clienthttp −→ Serverhttp
HTTP Response
- Clienthttp ←− Serverhttp
? Structure of HTTP - Request/Response
? How Clienthttp and Serverhttp exchange messages Sample HTTP Response Message

HTTP
HTTP Methods HTTP Status Codes (selected)

- Method token indicates the method to be performed on - The Status-Code element is a 3-digit integer result code
the resource identified by the Request-URI of the attempt to understand and satisfy the request
- The first digit of the Status-Code defines the class of
response. The last two digits do not have any
categorization role.
- There are 5 values for the first digit
1xx Informational - Request received, continu-
ing process
2xx Success - The action was successfully re-
ceived, understood, and accepted
3xx Redirection - Further action must be taken
in order to complete the request
4xx Client Error - The request contains bad syn-
tax or cannot be fulfilled
5xx Server Error - The server failed to fulfill an
Request Header Lines apparently valid request
- The request-header fields allow the client to pass
additional information about the request, and about the
client itself, to the server.
request-header Accept
Accept-Charset
Accept-Encoding
Accept-Language
Authorization
If-Modified-Since Response Header Lines
Proxy-Authorization The response-header fields allow the server to pass
additional information about the response which cannot
. be placed in the Status- Line
.
.

Web Caching: Proxy Server
A proxy server is a network entity that satisfies HTTP requests on the behalf of an origin Web server.
A user’s browser can be configured so that all of the user’s HTTP requests are first directed to the
proxy server
- For a HTTP connection between user’s browser and a web server, the browser first established a TCP
connection to the Proxy server and request for the object from the web server.
- The proxy server checks to see if it has a copy of the object stored locally. If it does, it returns the
object within an HTTP response to the client browser.
How to determine if the copy of an object

residing in the proxy server is stale or not? The
object housed in the proxy server may have
been modified (at the web server) since the
copy was cached at the proxy server.
A Solution: conditional GET
- Method: GET; Header: If-Modified-Since

Proxy Server

Proxy Server

Table of Contents

Aloha]
address]
distance-vector]

Electronic Mail Infrastructure
Email
How does the following work: Alice@ucalgary.ca −→ Bob@ashoka.edu.in?
- The Internet’s email infrastructure has three major components:
1. User agents
2. Mail Servers
3. Simple Mail Transfer Protocol

Testing SMTP

ICMP
Internet Control Messaging Protocol (ICMP)

- The IP is used for host-to-host communication service in a system of interconnected networks
- The intermediate routers makes up a path from a source host to a destination host
- Occasionally an intermediate router or destination host may require to communicate with a source host
to report an error in ip packet processing.
- For such purposes this protocol, the Internet Control Message Protocol (ICMP) is used.
ICMP, uses the basic support of IP as if it were a higher level protocol, however, ICMP is actually an
integral part of IP, and must be implemented by every IP module.
- The ICMP messages typically report errors in the processing of ip packets.
- No ICMP messages are sent about ICMP messages.
- Also ICMP messages are only sent about errors in handling fragment zero of fragemented ip packets.
- ICMP does not take transport level services
- How does the host determine it is receiving an

ICMP message?
− In IP packet, Protocol Field = 1
- How to determine what type of error is reported
?
− Using (Type,Code) pairs

Different ICMP Error Reports
Type = 3 referes to Error report for

− Destination Unreachable
Different types of destinations are captured by Code
- 0 = Destination network unreachable
- 1 = Destination host unreachable
- 2 = Upper layer protocol unreachable
- 3 = Destination port unreachable
- Checksum (For error checking)
- Unused - is set to 32-bit 0’s
- Processed ip header + first 64 bits of processed ip packet’s data
- This data is used by the host to match the message to the appropriate process. If a higher level
protocol uses port numbers, they are assumed to be in the first 64 data bits of the original
datagram’s data.

Type = 11 referes to Error report for

− Time Exceeded
Different ”time exceeded” are captured by Code
- 0 = time to live exceeded
- 1 = fragment reassembly time exceeded
- If a router finds that TTL is zero it must discard the datagram. It notify the source host via the time
exceeded message.
- If a host reassembling a fragmented ip packet cannot complete the reassembly due to missing
fragments within its time limit it discards the packet, and it may send a time exceeded message.
- Code 0 may be received from a gateway. Code 1 may be received from a host.

Type = 8 for Echo message

Type = 0 for Echo reply
Code = 0
- The data received in the echo message must be returned in the echo reply message.
- The identifier and sequence number may be used by the echo sender to aid in matching the replies
with the echo requests.
- The echoer returns these same values in the echo reply.

Traceroute
- Traceroute is a program that will attempt to - This warning message includes the name of the
identify all the routers in between you and some router and its IP address.
other computer out on the internet - - When this ICMP message arrives back at the
demonstrating the hop-to-hop quality of the source, the source obtains the round-trip time
internet. from the timer and the name and IP address of
- Traceroute is implemented with ICMP the nth router from the ICMP message
messages. - One of the datagrams will eventually make it all
- Traceroute in the source sends a series of the way to the destination host.
ordinary IP datagrams to the destination. - Because this datagram contains a UDP
- Each of these datagrams carries a UDP segment with an unlikely port number, the
segment with an unlikely UDP port number. destination host sends a port unreachable ICMP
- The first of these datagrams has a TTL of 1, message (type 3 code 3) back to the source.
second of 2, the third of 3, and so on. - When the source host receives this particular
- When the nth datagram arrives at the nth ICMP message, it knows it does not need to
router, the nth router observes that the TTL of send additional probe packets.
the datagram has just expired
- According to the rules of the IP protocol, the
router discards the datagram and sends an
ICMP warning message to the source (type 11
code 0).

Table of Contents

Aloha]
address]
distance-vector]

Routing Algorithms
- So far we have learned network-layer’s - Whenever a sender host (S) sends a packet to a
forwarding function destination host (R) (S and R are present in
- When a packet arrives to a router, the router different networks), the packet is transferred to
indexes a forwarding table and determines the its default router (Source Router ).
link interface to which the packet is to be - The problem of routing a packet from source
directed. host to destination host clearly boils down to
- We now turn our attention to the network the problem of routing the packet from Source
layer’s routing function Router to Destination Router
- The job of routing is to determine good paths The purpose of a routing algorithm is then
(routes), from senders to receivers, through the simple: given a set of routers, with links
network of routers. connecting the routers, a routing algorithm
finds a good path from source router to
destination router.

Routing Algorithms
  n
OSPF (Open Shortest Path First) -
  Link-state algorithms
Routing in the Internet

 




 Intra-domain Routing
 n
Distance-vector algorithms RIP (Routing Information Protocol)


Routing =
 Routing in the Internet



 n n
Inter-domain Routing Hierarchical Routing BGP (Border Gateway Protocol)


Routing in the Internet

Routing Problem: Graph Formulation
1 Forwarding table at R7? 2 Graph Formulation 3 Forwarding Table at R7 !!
Networks Next Hop Networks Next Hop

N9 ? N9 R9
N8 ? N8 R8
N10 ? N10 R8
N11 ? N11 R8
N12 ? N12 R8

Link-State Routing (Dijkstra’s Algorithm)
0 Initialization
1 V 0 = {u}
2 for all nodes v
3 if v ∈ NB(u)
4 then Du (v ) = c(u, v )
5 else Du (v ) = ∞
6
7 Loop
8 Find w ∈ V\V0 s.t. Du (w ) is minimum
Input 9 V 0 ← V 0 ∪ {w }
- G = (V , E ), u ∈ V = {v1 , . . . , vn } 10 For each v ∈ NB(w )\V0 , update:
11 Du (v ) ← min Du (v ), Du (w ) + c(w , v )
Output
- [(lcpu→v , Du∗ (v1 )), · · · , (lcpu→vn , Du∗ (vn ))], where 12 untill V0 = V
1
lcpu→v is a least-cost-path from u to vi , and
i
Du∗ (vi ) = cost(lcpu→v ).
i Claim: Du (v ) = Du∗ (v ) if v ∈ V0 .
It runs for (n − 1) iterations satisfying the following:
Step Partial Output
1 [(lcpu→v , Du∗ (vi1 ))]
i1
2 [(lcpu→v , Du∗ (vi1 )), (lcpu→v , Du∗ (vi2 ))]
i1 i2
. .
. .
. .
n-1 [(lcpu→v , Du∗ (vi1 )), . . . , (lcpu→v , Du∗ (vin−1 ))]
i 1 i n−1

Link-State Routing (Dijkstra’s Algorithm)
0 Initialization
1 V 0 = {u}
2 for all nodes v
3 if v ∈ NB(u)
4 then Du (v ) = c(u, v )
5 else Du (v ) = ∞
6
7 Loop
8 Find w ∈ V\V0 s.t. Du (w ) is minimum
9 N 0 ← N 0 ∪ {w }
10 For each v ∈ NB(w )\V0 , update:
11 Du (v ) ← min Du (v ), Du (w ) + c(w , v )
12 untill V0 = V
N0 Du (v ) Du (w ) Du (x ) Du (y ) Du (z)
u 2 5 1 ∞ ∞
ux 2 4 1 2 ∞
uxy 2 3 1 2 4
uxyv 2 3 1 2 4
uxyvw 2 3 1 2 4
uxyvwz 2 3 1 2 4

Distance-Vector Algorithm
The distance vector algorithm is distributed in that

– each node receives some information from one or more of its directly
attached neighbours,
– performs a calculation (Bellman-Ford equation), and
– then distributes the results of its calculation back to its neighbours
It is iterative, asynchronous and self-terminating

Distance-Vector Algorithm
I The following is running at each node x
0 Initialization
1 For all y ∈ V
2 Dx (y ) = c(x , y ) if y ∈ NB(x )
3 Dx (y ) = ∞ if y ∈ / NB(x )
4 Set D[x ] = [Dx (y )]y ∈V
4 For each w ∈ NB(x )

5 Set D[w ] = [Dw (y ) =?]y ∈V
6 For each w ∈ NB(x )

7 Send D[x ] to w
8
9 Loop
10 Wait (Until (detect a change in c(x , w ) for any

w ∈ NB(x )) or (receive D[w ] from some w ∈ NB(x )))
11 For each y ∈ V, update:

12 Dx (y ) = minv ∈NB(x ) {c(x , v ) + Dv (y ))}
13 Update D[x ]
14 If D[x ] changed
15 Send D[x ] to all w ∈ NB(x )
12 Forever

Routing Information Protocol (RIP)
- RIP operates in a manner very close to the idealized distance-vector algorithm.

- Goal: Shortest path from source router to destination subnet (including the destination subnet)
- Path-cost: Number of subnets traversed along the path (each link cost is set to 1)
- RIP’s input and final output at R7 is given below

D[R7 ] = DR7 (N7) DR7 (N9) DR7 (N10) DR7 (N8) DR7 (N11) DR7 (N12)
Initial= 1 ∞ ∞ ∞ ∞ ∞
. . . . . . .
. . . . . . .
. . . . . . .
Once stabilized = 1 2 2 2 3 3

Routing Information Protocol (RIP)
- Neighbouring routers exchange distance vectors with each other

- The distance vector for any one router is the current estimate of the shortest path distances from that
router to the subnets in the domain.
- In RIP, routing updates are exchanged between neighbours approximately every 30 seconds using RIP
request/response messages
- Routers send RIP request and response messages to each other over UDP using port number 520.
- RIP is implemented as an application-layer protocol running over UDP

Table of Contents

Aloha]
address]
distance-vector]

Inter-domain Routing
AS1, AS2, and AS3 are three different domains

- Given AS2 is an ISP for networks 138.16.64/24 − 138.16.67/24
AS3 is an ISP for network188.25.12/24
Goal: All routers in these three AS’s must update their routing table with this info.
- Routers in AS3 learn about 188.25.12/24 using Intra-domain routing

Router Network NextHop Router Network NextHop
3Rc 188.25.12/24 3Rb 3Ra 188.25.12/24 3Rb
- Routers’ in AS2 similarly learn following
Router Network NextHop Router Network NextHop
138.16.64/24 2Rb 138.16.64/24 2Rb
2Rc 138.16.66/24 2Rb 2Ra 138.16.66/24 2Rb
138.16.67/24 2Rb 138.16.67/24 2Rb
2Rb 138.16.65/24 2Rc 138.16.65/24 2Rc

- AS3 and AS2 must reach out to AS1

- AS3 shares that ”188.25.12/24 is reachable via AS3” - After learning these info, 1Rc and 1Rb subsequently
- For AS2, it makes sense to aggregate and share - share the same with the other routers in their respective
”138.16.64/22 is reachable via AS2” domain.
- Gateway routers of AS3 and AS2 communicate this - Internal BGP Sessions (over TCP):
info to AS1 via appropriate gateway routers of AS1

iBGP iBGP
- In this case, 3Ra ←→ 1Rc and 1Rb ←→ 2Ra. 1Rc ← → 1Ra 1Rb ←→ 1Ra
- External BGP Session (over TCP): iBGP iBGP
1Rc ←→ 1Rd 1Rb ←→ 1Rd
eBGP
3Ra ←→ 1Rc  iBGP
. 1Rc ←→ 1Rb
eBGP
1Rb ←→ 2Ra

BGP Advertisement Structure

- Before we learn the structure, first define Autonomous System Number
- In BGP, an AS (domain) is identified by its globally unique autonomous system number (ASN)
- Not every AS has an ASN
- An AS that carries only traffic for which it is a source or destination
(also called - stub AS) will not typically have an ASN
- ASN, like IP addresses, are assigned by ICANN regional registries.

BGP Advertisement Structure
Network AS-PATH NEXT-HOP

−→
X=188.25.12/24 ? ?
3Ra 1Rc
AS-PATH : It contains the ASNs of ASs through which the received BGP-route has passed!!

NEXT-HOP provides a critical link between the inter-AS and intra-AS routing protocols
Network AS-PATH NEXT-HOP
- The NEXT-HOP attribute in a received BGP-route is the
X ASk, . . . , AS2, AS1 ?
ip-address of the ASk-interface from which the BGP-route exited

How BGP advertisements, received over eBGP/iBGP, - An AND operation between NEXTHOP in BGP
cause routing/forwarding tables in Routers to update advertisement and the subnetmask in the forwarding
- e.g., what happens when 1Rd receive the following BGP table entry tells that the NEXTHOP interface is
advertisement from 1Rb (over an iBGP session) present in 110.15.0.0/24
138.16.64.0/22 AS2 110.15.0.2 - The router 1Rd finally adds the following entry in its
forwarding table
- The following is an entry in the forwarding table of 1Rd
as a result of the intra-domain routing (say RIP) Dest. Net. Add. Subnet Mask Next Hope IP
110.15.0.0 255.255.0.0 110.13.0.2
Dest. Net. Add. Subnet Mask Next Hope IP 138.16.64.0 255.255.252.0 110.13.0.2
110.15.0.0 255.255.0.0 110.13.0.2
**refer to the link-costs

Wireless Networks
Wireless Local Area Network - Physical Layer : In a wired LAN (such as Ethernet)
- Wireless LAN is another LAN technology signals traveled in a guided media
- For Wireless LAN, like any other LAN, we will learn its
physical and link layer technology
- MAC problem in Ethernet
- Our focus: IEEE 802.11

- A rough topology of IEEE 802.11
- In wireless LAN, the media is uniquely defined by a

frequency band
- The two-fold problem:

Wireless Networks
- The media is wireless, and it is uniquely defined by a - Also assume, data bits are represented as {−1, 1}
frequency band - Transmit data = d1 d2 . . . dn using FB1 as follows
- The two-fold problem:
data bits Encoding di , (c11 , c12 , . . . , c1m )
d1 (z11 , . . . , z1m ) = (d1 c11 , . . . , d1 c1m )
d2 (z21 , . . . , z2m ) = (d2 c11 , . . . , d2 c1m )
. .
. .
. .
dn (zn1 , . . . , znm ) = (dn c11 , . . . , dn c1m )
- D = (d1 d2 . . . dn ) → Z =
(z11 . . . z1m z21 . . . z2m · · · zn1 . . . znm )
- Encode Z using FB1 and transmit the resulting signal
- Problem#1 - MAC problem - If no interference, the receiver gets correct signal,
- Problem#2 - Media Interference Problem (not an issue extracts Z and finally extracts D as follows:
for wired LANs) Encoded bits Decoding
- Addressing Problem#2 z11 c11 +···+z1m c1m
- Assume hosts are transmitting in one of the three (z11 , . . . , z1m ) m
= d1
z21 c11 +···+z2m c1m
distinct frequency bands FB1, FB2, and FB3 (z21 , . . . , z2m ) m
= d2
- We therefore have three media in place. . .
- To each band, associate the following: . .
. .
FB1 C1 = (c11 , c12 , . . . , c1m ) zn1 c11 +···+znm c1m
FB2 C2 = (c21 , c22 , . . . , c2m ) where (zn1 , . . . , znm ) m
= dn
FB3 C3 = (c31 , c32 , . . . , c3m )
cij ∈ {−1, 1}
- Assume that hCi , Cj i = 0

Wireless Networks
The case of the Interference - A receiver in FB1 band will reconstruct the original
data D from Z ∗ as follows:
- Some other host, at the same time, happens to transmit
data D 0 = (d10 , . . . , dn0 ) using the frequency band FB2 - Reconstruction of the bit d1
- Encoding: z ∗ c11 +···+z ∗ c1m
11 1m
D 0 → Z 0 = (z11
0 0
. . . z1m 0
z21 0
. . . z2m 0
· · · zn1 0
. . . znm ) m
z 0 c11 +···+z 0 c1m
where Zij0 = di0 c2j z c +···+z c
= 11 11 m 1m 1m + 11 1m
m
- Signals for both Z and Z 0 are in propagation and 0 0
d c21 c11 +···+d c2m c1m
suppose they collide = d1 + 1 m
1
- Assumption: The resulting signal are a addition of the 0

d ×hC2 ,C1 i
two interfering signals = d1 + 1 m
- Suppose the resulting signal decodes to Z ∗ , then d1
Z ∗ = Z + Z 0 (component wise addition)

The 802.11 Architecture

The 802.11 Architecture: Channel and Association

The 802.11 MAC Protocol

The 802.11 Link-layer Reliable Transmission (+ MAC)
Kurose & Ross
Kurose & Ross

The 802.11 Frame Structure
Kurose & Ross

CN Final Slides

Uploaded by

Copyright:

Available Formats

CN Final Slides

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CN Final Slides

Uploaded by

Copyright:

Available Formats

Table of Contents

11 Lecture#11 (12/10) [CIDR Addressing]

Mahavir Jhawar Computer Networks Ashoka University 128 / 243

- Assume ip address of Laptop1 is 190.135.170.162

Mahavir Jhawar Computer Networks Ashoka University 129 / 243

0x0806 Address Resolution Protocol (ARP)

Mahavir Jhawar Computer Networks Ashoka University 130 / 243

Mahavir Jhawar Computer Networks Ashoka University 131 / 243

- Every host maintains an ARP table where they keep the

Mahavir Jhawar Computer Networks Ashoka University 132 / 243

Mahavir Jhawar Computer Networks Ashoka University 133 / 243

- Suppose, Laptop1’s address is 121.234.218.130

Mahavir Jhawar Computer Networks Ashoka University 134 / 243

Mahavir Jhawar Computer Networks Ashoka University 135 / 243

We first discuss network applications

Mahavir Jhawar Computer Networks Ashoka University 136 / 243

Mahavir Jhawar Computer Networks Ashoka University 137 / 243

- Suppose you are downloading web pages from

Mahavir Jhawar Computer Networks Ashoka University 138 / 243

Mahavir Jhawar Computer Networks Ashoka University 139 / 243

11 Lecture#11 (12/10) [CIDR Addressing]

Mahavir Jhawar Computer Networks Ashoka University 140 / 243

- TCP ensures reliable communication between

Top-down flow: Application Layer to Physical Layer

Mahavir Jhawar Computer Networks Ashoka University 141 / 243

Mahavir Jhawar Computer Networks Ashoka University 142 / 243

- CApp2 provides two inputs to TCP:

- TCP creates a socket and assigns a unique port to it - say 345

Connection Acceptance at SApp2

Mahavir Jhawar Computer Networks Ashoka University 143 / 243

Mahavir Jhawar Computer Networks Ashoka University 144 / 243

Mahavir Jhawar Computer Networks Ashoka University 145 / 243

- Sequence and Acknowledgement Number fields

Mahavir Jhawar Computer Networks Ashoka University 146 / 243

Mahavir Jhawar Computer Networks Ashoka University 147 / 243

Mahavir Jhawar Computer Networks Ashoka University 148 / 243

Mahavir Jhawar Computer Networks Ashoka University 149 / 243

Mahavir Jhawar Computer Networks Ashoka University 150 / 243

Mahavir Jhawar Computer Networks Ashoka University 151 / 243

Creating Socket Socket types

Address Families Example: TCP Connection

Mahavir Jhawar Computer Networks Ashoka University 153 / 243

11 Lecture#11 (12/10) [CIDR Addressing]

Mahavir Jhawar Computer Networks Ashoka University 154 / 243

Mahavir Jhawar Computer Networks Ashoka University 155 / 243

Application Application-layer Underlying

Electronic mail SMTP TCP

Ports for Common Services

Application-layer Protocols Ports

Mahavir Jhawar Computer Networks Ashoka University 156 / 243

- DHCP is built on a client-server model.

- DHCP uses UDP as its transport protocol !

Mahavir Jhawar Computer Networks Ashoka University 157 / 243

- Where does a DHCP server sit ?

Mahavir Jhawar Computer Networks Ashoka University 158 / 243

Mahavir Jhawar Computer Networks Ashoka University 159 / 243

DHCP Server → ALL

Mahavir Jhawar Computer Networks Ashoka University 160 / 243

Mahavir Jhawar Computer Networks Ashoka University 161 / 243