CS 31204: Computer Networks – History and Protocol Stack

INDIAN INSTITUTE OF TECHNOLOGY

KHARAGPUR

Department of Computer Science and Engineering

Sandip Chakraborty

sandipc@cse.iitkgp.ac.in

​

Abhijnan Chakraborty

abhijnan@cse.iitkgp.ac.in

Few slides in this presentation has been adopted from the online resources accompanying the book Computer Networking: A Top-Down Approach by Jim Kurose and Keith Ross

https://gaia.cs.umass.edu/kurose_ross/eighth.php

Indian Institute of Technology Kharagpur

Circuit Switching – the Beginning

• The concept of how telephone switching works – creates a dedicated communication links between two communication nodes (telephones)

​

• In January 1878, the first telephone switch went into operation in New Haven Connecticut.

​

​

Indian Institute of Technology Kharagpur

Circuit Switching

Source: http://comp380group4project1.web.unc.edu/technical-discussion/circuit-switching/

Indian Institute of Technology Kharagpur

Problem with Circuit Switching for Data Communication

• Data traffic is bursty – uses an on-off pattern for data communication.

​

​

Indian Institute of Technology Kharagpur

Packet Switching

• Decide data boundary from the communication of one user – data packets

Packet Multiplexing

Indian Institute of Technology Kharagpur

The First Packet Switching Network

Robert Taylor was promoted to the head of the information processing office at Defense Advanced Research Projects Agency (DARPA) in June 1966. He intended to realize Licklider's ideas of an interconnected networking system. Bringing in Larry Roberts from MIT, he initiated a project to build such a network. The first ARPANET link was established between the University of California, Los Angeles (UCLA) and the Stanford Research Institute at 22:30 hours on October 29, 1969.

​

Kleinrock said in an interview: "We typed the L and we asked on the phone,

"Do you see the L?"

"Yes, we see the L," came the response.

We typed the O, and we asked, "Do you see the O."

"Yes, we see the O."

Then we typed the G, and the system crashed ...

Yet a revolution had begun"

By December 5, 1969, a 4-node network was connected by adding the University of Utah and the University of California, Santa Barbara. 

​

Source: Wikipedia

Indian Institute of Technology Kharagpur

ARPANET – The First Packet Switching Network

Indian Institute of Technology Kharagpur

History of Computer Networks

• https://www.youtube.com/watch?v=9hIQjrMHTv4

https://www.internetsociety.org/internet/history-internet

Indian Institute of Technology Kharagpur

Internet Structure: A “network of networks”

• Hosts connect to Internet via access Internet Service Providers (ISPs)
• Access ISPs in turn must be interconnected
• so that any two hosts (anywhere!) can send packets to each other
• Resulting network of networks is very complex
• Evolution driven by economics, national policies

​

Let’s take a stepwise approach to describe current Internet structure

​

Indian Institute of Technology Kharagpur

Internet Structure: A “network of networks”

Question: given millions of access ISPs, how to connect them together?

Indian Institute of Technology Kharagpur

Internet Structure: A “network of networks”

Question: given millions of access ISPs, how to connect them together?

connecting each access ISP to each other directly doesn’t scale: O(N²) connections.

Indian Institute of Technology Kharagpur

Internet Structure: A “network of networks”

Option: connect each access ISP to one global transit ISP?

Customer and provider ISPs have economic agreement.

Indian Institute of Technology Kharagpur

Internet Structure: A “network of networks”

ISP A

ISP C

ISP B

But if one global ISP is viable business, there will be competitors ….

Indian Institute of Technology Kharagpur

Internet Structure: A “network of networks”

ISP A

ISP C

ISP B

But if one global ISP is viable business, there will be competitors …. who will want to be connected

Indian Institute of Technology Kharagpur

Internet Structure: A “network of networks”

ISP A

ISP C

ISP B

…

…

…

…

…

…

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

Indian Institute of Technology Kharagpur

Internet Structure: A “network of networks”

ISP A

ISP C

ISP B

…

…

…

…

…

…

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

Indian Institute of Technology Kharagpur

Internet Structure: A “network of networks”

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

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

​

Indian Institute of Technology Kharagpur

Packet Switching: Store-and-forward

• packet transmission delay: takes L/R seconds to transmit (push out) L-bit packet into link at R bps
• store and forward: entire packet must arrive at router before it can be transmitted on next link

​

​

​

source

R bps

destination

1

2

3

L bits

per packet

R bps

Indian Institute of Technology Kharagpur

Packet Switching: Queueing

A

B

C

R = 100 Mb/s

R = 1.5 Mb/s

D

E

queue of packets

waiting for transmission over output link

Indian Institute of Technology Kharagpur

Packet Switching: Queueing

Packet queuing and loss: if arrival rate (in bps) to link exceeds transmission rate (bps) of link for some period of time:

• packets will queue, waiting to be transmitted on output link
• packets can be dropped (lost) if memory (buffer) in router fills up

​

A

B

C

R = 100 Mb/s

R = 1.5 Mb/s

D

E

queue of packets

waiting for transmission over output link

Indian Institute of Technology Kharagpur

How Do Packet Delay and Loss Occur?

• Packets queue in router buffers, waiting for turn for transmission
• Queue length grows when arrival rate to link (temporarily) exceeds output link capacity
• Packet loss occurs when memory to hold queued packets fills up

A

B

Indian Institute of Technology Kharagpur

Packet Delay: Four Sources

d_proc: nodal processing

• check bit errors
• determine output link
• Typically, < microsecs

d_queue: queueing delay

• time waiting at output link for transmission
• depends on congestion level of router

propagation

nodal

processing

queueing

d_nodal = d_proc + d_queue + d_trans + d_prop

A

B

transmission

Indian Institute of Technology Kharagpur

Packet Delay: Four Sources

propagation

nodal

processing

queueing

d_nodal = d_proc + d_queue + d_trans + d_prop

A

B

transmission

d_trans: transmission delay:

• L: packet length (bits)
• R: link transmission rate (bps)
• d_trans = L/R

d_prop: propagation delay:

• d: length of physical link
• s: propagation speed (~2x10⁸ m/sec)
• d_prop = d/s

Indian Institute of Technology Kharagpur

Caravan Analogy

• car ~ bit; caravan ~ packet; toll service ~ link transmission
• toll booth takes 12 sec to service car (bit transmission time)
• “propagate” at 100 km/hr
• Q: How long until caravan is lined up before 2nd toll booth?

​

• time to “push” entire caravan through toll booth onto highway = 12*10 = 120 sec
• time for last car to propagate from 1st to 2nd toll both: 100km/(100km/hr) = 1 hr
• A: 62 minutes

toll booth

toll booth

(aka link)

ten-car caravan

(aka 10-bit packet)

100 km

100 km

Indian Institute of Technology Kharagpur

Caravan Analogy

ten-car caravan

(aka 10-bit packet)

100 km

100 km

• Suppose cars now “propagate” at 1000 km/hr
• And suppose toll booth now takes one min to service a car
• Q: Will cars arrive to 2nd booth before all cars serviced at first booth?

​

A: Yes! after 7 min, first car arrives at second booth; three cars still at first booth

Indian Institute of Technology Kharagpur

Packet queueing delay (revisited)

• a: average packet arrival rate
• L: packet length (bits)
• R: link bandwidth (bit transmission rate)

• La/R ~ 0: avg. queueing delay small
• La/R -> 1: avg. queueing delay large
• La/R > 1: more “work” arriving is more than can be serviced - average delay infinite!

“traffic

intensity”

Indian Institute of Technology Kharagpur

“Real” Internet Delays and Routes

• What do “real” Internet delay & loss look like?
• traceroute program: provides delay measurement from source to router along end-end Internet path towards destination. For all i:

3 probes

3 probes

3 probes

• sends three packets that will reach router i on path towards destination (with time-to-live field value of i)
• router i will return packets to sender
• sender measures time interval between transmission and reply

Indian Institute of Technology Kharagpur

Real Internet Delays and Routes

1 cs-gw (128.119.240.254) 1 ms 1 ms 2 ms

2 border1-rt-fa5-1-0.gw.umass.edu (128.119.3.145) 1 ms 1 ms 2 ms

3 cht-vbns.gw.umass.edu (128.119.3.130) 6 ms 5 ms 5 ms

4 jn1-at1-0-0-19.wor.vbns.net (204.147.132.129) 16 ms 11 ms 13 ms

5 jn1-so7-0-0-0.wae.vbns.net (204.147.136.136) 21 ms 18 ms 18 ms

6 abilene-vbns.abilene.ucaid.edu (198.32.11.9) 22 ms 18 ms 22 ms

7 nycm-wash.abilene.ucaid.edu (198.32.8.46) 22 ms 22 ms 22 ms

8 62.40.103.253 (62.40.103.253) 104 ms 109 ms 106 ms

9 de2-1.de1.de.geant.net (62.40.96.129) 109 ms 102 ms 104 ms

10 de.fr1.fr.geant.net (62.40.96.50) 113 ms 121 ms 114 ms

11 renater-gw.fr1.fr.geant.net (62.40.103.54) 112 ms 114 ms 112 ms

12 nio-n2.cssi.renater.fr (193.51.206.13) 111 ms 114 ms 116 ms

13 nice.cssi.renater.fr (195.220.98.102) 123 ms 125 ms 124 ms

14 r3t2-nice.cssi.renater.fr (195.220.98.110) 126 ms 126 ms 124 ms

15 eurecom-valbonne.r3t2.ft.net (193.48.50.54) 135 ms 128 ms 133 ms

16 194.214.211.25 (194.214.211.25) 126 ms 128 ms 126 ms

17 * * *

18 * * *

19 fantasia.eurecom.fr (193.55.113.142) 132 ms 128 ms 136 ms

traceroute: gaia.cs.umass.edu to www.eurecom.fr

Indian Institute of Technology Kharagpur

Packet Loss

• Queue (aka buffer) preceding link in buffer has finite capacity

A

B

packet being transmitted

buffer

(waiting area)

Indian Institute of Technology Kharagpur

Throughput

• throughput: rate (bits/time unit) at which bits are being sent from sender to receiver
• instantaneous: rate at given point in time
• average: rate over longer period of time

server, with

file of F bits

to send to client

link capacity

R_s bits/sec

link capacity

R_c bits/sec

Indian Institute of Technology Kharagpur

Throughput

R_s < R_c What is average end-end throughput?

R_s bits/sec

R_s > R_c What is average end-end throughput?

Indian Institute of Technology Kharagpur

Throughput: Network Scenario

• per-connection end-end throughput: min(R_c,R_s,R/10)
• in practice: R_c or R_s is often bottleneck

Indian Institute of Technology Kharagpur

TCP/IP Protocol Stack

Indian Institute of Technology Kharagpur

Transport Layer Services

• Connection oriented communication
• Create a logical connection between your machine and Google server

Process to process Connection

Identify processes using port number

Indian Institute of Technology Kharagpur

Transport Layer Services

• Connection oriented communication
• Create a logical connection between your machine and Google server

​

• Ordered delivery of data packets

​

• Reliability

​

• Flow control

​

• Congestion avoidance

Indian Institute of Technology Kharagpur

Network (Internet) Layer Services

• Connectionless communication - construct messages (datagrams) from packets and route them to the next hop
• Why do transport layer packets need to be converted to datagrams at every hop?

​

• Host addressing - use IP addresses to uniquely identify a host in the network

​

• Datagram routing - decide the path to route every datagram from the network graph

​

Indian Institute of Technology Kharagpur

Data Link Layer Services

• Encapsulation of network layer data packets into frames

​

• Frame synchronization

​

• Error control

​

• Flow control
• Why do we need flow control at the link layer?

​

• Channel access / medium access, Physical addressing

Indian Institute of Technology Kharagpur

Data Link Layer

Error control and flow control

Channel access and physical layer

addressing

Indian Institute of Technology Kharagpur

Addressing a Host in the Network

• Every host has two addresses –
• Logical address (IP address) – used to find out the path towards a host
• Physical address (MAC address) - uniquely identify a host in the Internet

​

• Logical address – Dr. Sandip Chakraborty, Room-311, Department of Computer Science and Engineering, IIT Kharagpur, Kharagpur - 721302, West Bengal, India

​

• Physical address – My Aadhar number (XXXX XXXX XXXX)

Indian Institute of Technology Kharagpur

Addressing a Host in the Network

• Every host has two addresses –
• Logical address (IP address) – used to find out the path towards a host
• Physical address (MAC address) - uniquely identify a host in the Internet

​

• Logical address (32 bit IP address) – 172.16.32.64

​

• Physical address (64 bit MAC address) – 00:00:00:14:22:01:2C:4D

Indian Institute of Technology Kharagpur

Protocol Stack Implementation in a Host

Software, Kernel

Firmware, Device Driver

Hardware

Indian Institute of Technology Kharagpur

How Application Data Passes Through Different Layers

HTTP Data

HTTP Header

HTTP Data

HTTP Header

TCP Header

HTTP Data

HTTP Header

TCP Header

IP Header

HTTP Data

HTTP Header

TCP Header

IP Header

MAC Header

HTTP Data

HTTP Header

TCP Header

IP Header

MAC Header

PHY Header

PHY Trailer

Indian Institute of Technology Kharagpur

How do you access a page at www.google.com?

1. Application Layer: Use DNS to get the IP address of the Google server - DNS returns 74.125.224.72
2. Application Layer: Construct an HTTP GET Request – �GET 74.125.224.72/index.html HTTP/1.1�Construct an HTTP packet and forward it to the transport layer

Indian Institute of Technology Kharagpur

How do you access a page at www.google.com?

3. Transport Layer: Construct the transport layer packet (TCP packet)
• Source port: 3324 (port address corresponding to your browser tab)
• Destination port: 80 (port for a HTTP server)

Indian Institute of Technology Kharagpur

How do you access a page at www.google.com?

3. Network Layer: Construct the network layer packet (IP packet)
• Source IP: 172.16.22.121 (IP of your machine)
• Destination IP: 74.125.224.72 (IP obtained from DNS query)

Indian Institute of Technology Kharagpur

How do you access a page at www.google.com?

4. Network Layer: Use the routing procedure to find out the next hop IP to reach the Google server at 74.125.224.72. Let this IP be 172.16.28.192

172.16.28.192

172.16.22.121

74.125.224.72

Indian Institute of Technology Kharagpur

How do you access a page at www.google.com?

5. Data Link Layer: Construct the data link layer frame from the IP datagram.
• How do we get destination MAC address? We need the MAC address corresponding to 172.16.28.192

172.16.28.192

172.16.22.121

Gateway

Local Area Network (LAN)

Indian Institute of Technology Kharagpur

How do you access a page at www.google.com?

6. Data Link Layer: Use ARP protocol to get the MAC address corresponding to 172.16.28.192

172.16.28.192

172.16.22.121

Gateway

Local Area Network (LAN)

Indian Institute of Technology Kharagpur

In Summary

HTTP Data

HTTP Header

HTTP Data

HTTP Header

TCP Header

HTTP Data

HTTP Header

TCP Header

IP Header

HTTP Data

HTTP Header

TCP Header

IP Header

MAC Header

HTTP Data

HTTP Header

TCP Header

IP Header

MAC Header

PHY Header

PHY Trailer

Indian Institute of Technology Kharagpur