CS 31204: Computer Networks – Moving From End-to-End To Per Hop

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

What We Have Learnt So Far …

• The design of current network architecture is based on experience and requirements

Physical

Transport

Indian Institute of Technology Kharagpur

What We Have Learnt So Far …

• Protocol stack is implemented across different layers of the operating system

Software, Kernel

Firmware, Device Driver

Hardware

Indian Institute of Technology Kharagpur

Network (Internet) Layer Services

​

​

​

​

​

​

UDP

End to end packet delivery

​

​

​

​

​

​

TCP

Connection Establishment

Reliable Data Delivery

Flow and Congestion Control

Ordered Packet Delivery

Transport

Data Link

Network

Addressing

Routing

Datagram delivery (unreliable)

Indian Institute of Technology Kharagpur

Internet Architecture – Basic Principles

• Internet is organized in a hierarchical fashion.

SW Lab 1

SW Lab 2

Router

CSE Network

Indian Institute of Technology Kharagpur

Internet Architecture – Basic Principles

• Internet is organized in a hierarchical fashion.

CSE Network

EEE Network

SW Lab 1

SW Lab 2

EE Lab 1

EE Lab 2

IITKGP Network

Indian Institute of Technology Kharagpur

Internet Architecture – Basic Principles

• Internet is organized in a hierarchical fashion.

IITKGP Network

IITBBS Network

EEE

CSE

EEE

CSE

ERNET Network

Indian Institute of Technology Kharagpur

Internet Architecture – Basic Principles

• Internet is organized in a hierarchical fashion.

BSNL Network

IITKGP

IITBBS

BSNL Public

BSNL Corporate

Bharti Airtel Network

ERNET Network

Indian Institute of Technology Kharagpur

Internet Architecture

Autonomous Systems (AS) – A set of LANs for an administrative domain, identified by a unique AS number, and the routing policies are controlled by a single administrator.

​

​

Local Area Network (LAN) – A set of devices with a common layer 3 gateway

Indian Institute of Technology Kharagpur

Autonomous System Graph for India

Source: https://rex.apnic.net/welcome

Indian Institute of Technology Kharagpur

Internet Architecture

Internet Service Providers (ISP) – An AS provides Internet connectivity to another group of ASes or end users

Indian Institute of Technology Kharagpur

Peering between ISPs

Indian Institute of Technology Kharagpur

Communication between Two Nodes over ISPs

Indian Institute of Technology Kharagpur

IP Addressing – Basic Principles

• We need to forward data packets from one network to another network via different intermediate networks.

AS 10

AS 11

AS 13

AS 12

Host 1

Host 2

Indian Institute of Technology Kharagpur

IP Addressing – Basic Principles

• The address should identify a network as well as a host inside a network

AS 10

AS 11

AS 13

AS 12

Host 1

Host 2

Indian Institute of Technology Kharagpur

IP Addressing

• Divide the address space (32 bit in IPv4) among network address and host address

​

• The old age – Classful addressing: Fixed number of bits for network address and host address

Network address

Host address

Indian Institute of Technology Kharagpur

Classful Addressing

• How to identify a class – use the first few bits
• 0 – Class A, 10 – Class B, 110 – Class C, 1110 – Class D, 1111 – Class E

Indian Institute of Technology Kharagpur

Network Address and Broadcast Address

• Network address – identify a network
• All 0’s in the host address part
• Ex-1 (Class A): 01111110.00000000.00000000.00000000 (126.0.0.0)
• Ex-2 (Class B): 10111101.11101001.00000000.00000000 (189.233.0.0)

​

​

• Broadcast address – send the data to all the hosts of a network
• All 1’s in the host address part
• Ex-1 (Class A): 01111110.11111111.11111111.11111111 (126.255.255.255)
• Ex-2 (Class B): 10111101.11101001.11111111.11111111 (189.233.255.255)

​

• How many valid hosts can be there in a Class A, in a Class B and in a Class C IP address?

Indian Institute of Technology Kharagpur

Subnetting and Supernetting – Classless Inter-domain Routing (CIDR)

• You have 255 hosts in a network. Which IPv4 address class will you use – Class C or Class B ?
• Class C – not possible
• Class B – huge address space is lost (using only 255 addresses out of possible 2¹⁶-2 addresses)

​

• Split a large network or combine multiple small networks for efficient use of address space
• Subnetting – divide a large network into multiple small networks
• Supernetting – combine multiple small networks into a single large network

​

• Subnet mask – denote the number of bits in the network address field

Indian Institute of Technology Kharagpur

Divide a Network into Subnets

Indian Institute of Technology Kharagpur

CIDR – Addressing Format

• We write the IP address as 191.180.83.235/12 in CIDR notation
• The first 12 bits are the network address and rest (32-12)=20 bits are for host address

​

• The subnet mask is 255.240.0.0

​

​

​

​

Host Address

​

​

​

​

Subnet Address

10111111

10110100

01010011

11101011

11111111

11110000

00000000

00000000

IP Address

Netmask

Indian Institute of Technology Kharagpur

CIDR - Manual IP Setting in the OS

Indian Institute of Technology Kharagpur

Divide a Network into Subnets

• Let the IP address of a network is 203.110.0.0/16

​

• We want to divide this network into three subnets

​

• We need 3 bits for subnets – why not 2 bits?
• Subnet 1 – 100, Subnet 2– 101, Subnet 3 – 110

​

• Rest 13 bits are used for addressing the hosts of those subnets.

​

• The subnets are – 203.110.128.0/19, 203.110.160.0/19, 203.110.192.0/19

Indian Institute of Technology Kharagpur

All Zero and All One Subnets

192.168.0.0/16

192.168.0.0/17

192.168.128.0/17

192.168.0XXXXXXX.X

192.168.1XXXXXXX.X

The network address for the �subnet and the original network�is identical – Subnet Zero

Broadcast address for this subnet�is 192.168.255.255, broadcast�address for the original network�is also 192.168.255.255 – All-One�Subnet

We normally avoid “all zero” and “all one” subnets.

https://www.cisco.com/c/en/us/support/docs/ip/dynamic-address-allocation-resolution/13711-40.html

Indian Institute of Technology Kharagpur

CIDR Example

CSE – 2000 Hosts

VGSOM – 500 Hosts

EE – 500 Hosts

203.110.0.0/19

Indian Institute of Technology Kharagpur

CIDR Example

CSE – 2000 Hosts

VGSOM – 500 Hosts

EE – 500 Hosts

203.110.0.0/19

11 bit hosts

9 bit hosts

9 bit hosts

Indian Institute of Technology Kharagpur

CIDR Example

• Address space – 203.110.0.0/19
• 13 bits are available to serve all the hosts of IITKGP network
• We need to divide these address space among 3 subnets

​

• CSE – 11 bits, VGSOM – 9 bits, EE – 9 bits for host address

​

• We have 2 bits left for identifying three subnets – Is this possible?
• Avoid “all zero” and ”all one” subnets

​

• Let us apply CIDR – Combine VGSOM and EE Networks together

Indian Institute of Technology Kharagpur

CIDR Example

CSE – 2000 Hosts

VGSOM – 500 Hosts

EE – 500 Hosts

203.110.0.0/19

11 bit hosts

9 bit hosts

9 bit hosts

10 bit hosts

Indian Institute of Technology Kharagpur

CIDR Example

CSE – 11 bits, VGSOM+EE – 10 bits

​

• Network address – 203.110.0.0/19, 203.110.000XXXXX.XXXXXXXX

​

• CSE network address 203.110.00010XXX.XXXXXXXX (203.110.16.0/21)

​

• VGSOM+EE network address 203.110.00001XXX.XXXXXXXX (203.110.8.0/21)

​

​

Indian Institute of Technology Kharagpur

CIDR Example

CSE – 2000 Hosts

VGSOM – 500 Hosts

EE – 500 Hosts

203.110.0.0/19

11 bit hosts

9 bit hosts

9 bit hosts

10 bit hosts

203.110.16.0/21

203.110.8.0/21

Indian Institute of Technology Kharagpur

CIDR Example

VGSOM – 9 bits, EE – 9 bits

​

• Network address – 203.110.8.0/21, 203.110.00001XXX.XXXXXXXX

​

• VGSOM network address 203.110.0000110X.XXXXXXXX (203.110.12.0/23)

​

• EE network address 203.110.0000101X.XXXXXXXX (203.110.10.0/23)

​

​

​

Indian Institute of Technology Kharagpur

CIDR Example

CSE – 2000 Hosts

VGSOM – 500 Hosts

EE – 500 Hosts

203.110.0.0/19

11 bit hosts

9 bit hosts

9 bit hosts

10 bit hosts

203.110.16.0/21

203.110.8.0/21

203.110.12.0/23

203.110.10.0/23

Indian Institute of Technology Kharagpur

CIDR – Routing Table Construction

10.0.2.0/24

10.0.3.0/24

10.0.4.0/24

R1

R2

R3

eth0

eth1

10.0.2.1/24

10.0.3.1/24

10.0.4.1/24

172.16.1.1/24

172.16.1.2/24

172.16.2.1/24

172.16.2.2/24

Routing Table for R1

Indian Institute of Technology Kharagpur

CIDR – Routing Table Construction

10.0.2.0/24

10.0.3.0/24

10.0.4.0/24

R1

R2

R3

eth0

eth1

10.0.2.1/24

10.0.3.1/24

10.0.4.1/24

172.16.1.1/24

172.16.1.2/24

172.16.2.1/24

172.16.2.2/24

Routing Table for R1

Compaction of routing table is possible

Indian Institute of Technology Kharagpur

CIDR – Routing Table Construction

10.0.2.0/24

10.0.3.0/24

10.0.4.0/24

R1

R2

R3

eth0

eth1

10.0.2.1/24

10.0.3.1/24

10.0.4.1/24

172.16.1.1/24

172.16.1.2/24

172.16.2.1/24

172.16.2.2/24

Compact

Routing Table for R1

Indian Institute of Technology Kharagpur

CIDR – Problem of Multihoming

10.0.2.0/24

10.0.3.0/24

10.0.4.0/24

R1

R2

R3

eth0

eth1

10.0.2.1/24

10.0.3.1/24

10.0.4.1/24

172.16.1.1/24

172.16.1.2/24

172.16.2.1/24

172.16.2.2/24

eth2

172.16.3.1/24

172.16.3.2/24

10.0.4.2/24

Indian Institute of Technology Kharagpur

CIDR – Longest Prefix Match

Supernetting is not always perfect !

There is always a possibility of duplicate entries

Where to forward 10.0.4.8 ?

Indian Institute of Technology Kharagpur

Longest Prefix Matching

when looking for forwarding table entry for given destination address, use longest address prefix that matches destination address.

Longest Prefix Match

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

Longest Prefix Matching

when looking for forwarding table entry for given destination address, use longest address prefix that matches destination address.

Longest Prefix Match

Destination Address Range

11001000 00010111 00010

11001000 00010111 00011000

11001000 00010111 00011

otherwise

Link interface

0

1

2

3

11001000 00010111 00011000 10101010

examples:

which interface?

which interface?

********

***

********

***

********

11001000 00010111 00010110 10100001

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

Longest Prefix Matching

when looking for forwarding table entry for given destination address, use longest address prefix that matches destination address.

Longest Prefix Match

Destination Address Range

11001000 00010111 00010

11001000 00010111 00011000

11001000 00010111 00011

otherwise

Link interface

0

1

2

3

11001000 00010111 00011000 10101010

examples:

which interface?

which interface?

********

***

********

***

********

11001000 00010111 00010110 10100001

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

Longest Prefix Matching

when looking for forwarding table entry for given destination address, use longest address prefix that matches destination address.

Longest Prefix Match

Destination Address Range

11001000 00010111 00010

11001000 00010111 00011000

11001000 00010111 00011

otherwise

Link interface

0

1

2

3

11001000 00010111 00011000 10101010

examples:

which interface?

which interface?

********

***

********

***

********

11001000 00010111 00010110 10100001

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

CIDR – Longest Prefix Match

• Use Patricia Tree (a compact representation of trie) for matching prefixes.

0

1

00

10

11

100

101

00*

0*

11*

Indian Institute of Technology Kharagpur

IP Addresses: How to Get One?

There are two questions:

1. How does a host get IP address within its network (host part of address)?
2. How does a network get IP address for itself (network part of address)

​

How does host get IP address?

• hard-coded by sysadmin in config file (e.g., /etc/rc.config in UNIX)
• DHCP: Dynamic Host Configuration Protocol: dynamically get address from as server
• “plug-and-play”

Indian Institute of Technology Kharagpur

DHCP: Dynamic Host Configuration Protocol

Goal: host dynamically obtains IP address from network server when it “joins” network

• can renew its lease on address in use
• allows reuse of addresses (only hold address while connected/on)
• support for mobile users who join/leave network

​

DHCP overview:

• host broadcasts DHCP discover msg [optional]
• DHCP server responds with DHCP offer msg [optional]
• host requests IP address: DHCP request msg
• DHCP server sends address: DHCP ack msg

​

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

DHCP Client-server Scenario

223.1.1.1

223.1.1.3

223.1.1.4

223.1.2.9

223.1.2.2

223.1.2.1

223.1.3.2

223.1.3.1

Typically, DHCP server will be co-located in router, serving all subnets to which router is attached

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

DHCP Client-server Scenario

DHCP server: 223.1.2.5

Arriving client

The two steps above can be skipped “if a client remembers and wishes to reuse a previously allocated network address” [RFC 2131]

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

DHCP: More than IP Addresses

DHCP can return more than just allocated IP address on subnet:

• address of first-hop router for client
• name and IP address of DNS sever
• network mask (indicating network versus host portion of address)

​

Indian Institute of Technology Kharagpur

DHCP: Example

• Connecting laptop will use DHCP to get IP address, address of first-hop router, address of DNS server.

router with DHCP

server built into

router

• DHCP REQUEST message encapsulated in UDP, encapsulated in IP, encapsulated in Ethernet

• Ethernet frame broadcast (dest: FFFFFFFFFFFF) on LAN, received at router running DHCP server

• Ethernet demux’ed to IP demux’ed, UDP demux’ed to DHCP

168.1.1.1

​

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

DHCP: Example

• DCP server formulates DHCP ACK containing client’s IP address, IP address of first-hop router for client, name & IP address of DNS server

​

• encapsulated DHCP server reply forwarded to client, demuxing up to DHCP at client

router with DHCP

server built into

router

• client now knows its IP address, name and IP address of DNS server, IP address of its first-hop router

​

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

IP Addressing: Last Words ...

Q: how does an ISP get block of addresses?

A: ICANN: Internet Corporation for Assigned Names and Numbers http://www.icann.org/

• Allocates IP addresses, through 5 regional registries (RRs) : AFRINIC (Africa), APNIC (Asia-Pacific), ARIN (North America), LACNIC (Latin America and the Caribbean), and RIPE NCC (Europe, Central Asia, and Middle East) who may then allocate to local registries
• Manages DNS root zone, including delegation of individual TLD (.com, .edu , …) management

​

Q: are there enough 32-bit IP addresses?

• ICANN allocated last chunk of IPv4 addresses to RRs in 2011
• NAT (next) helps IPv4 address space exhaustion
• IPv6 has 128-bit address space

"Who the hell knew how much address space we needed?" Vint Cerf (reflecting on decision to make IPv4 address 32 bits long)

Source: Computer Networking: A Top-Down Approach (8^th Ed) by Jim Kurose, Keith Ross

Indian Institute of Technology Kharagpur

A Practice Problem

• What would be next hop for the following destination IPs?

​

• 128.96.171.92

​

• 128.96.167.151

​

• 128.96.163.151

Problem courtesy: Computer Networks, Larry L Peterson and Bruce S Davie

Indian Institute of Technology Kharagpur

A Practice Problem

• What would be next hop for the following destination IPs?

​

• 128.96.171.92

​

171 -- 10101011

254 -- 11111110

​

Logical AND -- 10101010 -- 170

​

Destination is Eth0

Problem courtesy: Computer Networks, Larry L Peterson and Bruce S Davie

Indian Institute of Technology Kharagpur

A Practice Problem

• What would be next hop for the following destination IPs?

​

• 128.96.167.151

​

167 -- 10100111

254 -- 11111110

​

Logical AND -- 10100110 -- 166

​

Problem courtesy: Computer Networks, Larry L Peterson and Bruce S Davie

Indian Institute of Technology Kharagpur

A Practice Problem

• What would be next hop for the following destination IPs?

​

• 128.96.167.151

​

167 -- 10100111

252 -- 11111100

​

Logical AND -- 10100100 -- 164

​

Longest Match is 254. Next hop Eth1

​

Problem courtesy: Computer Networks, Larry L Peterson and Bruce S Davie

Indian Institute of Technology Kharagpur

Next, we’ll look some IP layer services for the management of Internetwork ...

Indian Institute of Technology Kharagpur