Network Layer

Dr. Vijay Ukani

CSE Department
Institute of Technology
Nirma University
Forwarding
Assuming that all routers and hosts are working properly and that all
software in both is free of all errors, is there any chance, however small,
that a packet will be delivered to the wrong destination?

ØYes. A large noise burst could garble a packet badly. With a k-bit
checksum, there is a probability of 2^(-k) that the error is undetected.
ØIf the destination field or, equivalently, virtual-circuit number, is
changed, the packet will be delivered to the wrong destination and
accepted as genuine.
What Are The IP Addresses
The IP address has two functions: for host and network
interface identification, as well as location addressing.

IPv4 addresses are represented in dot-decimal notation, which consists

of four decimal numbers, each ranging from 0 to 255, separated by dots
(eg. [Link]).
What Are The IP Addresses
IPv4 addresses can be divided into three categories named classes

Other classes
What Is The Subnet Mask?
A Subnet mask is a 32-bit number that masks an IP address, and
divides the IP address into network address and host address.

Subnet Mask is made by setting network bits to all "1" and setting host
bits to all "0".

The Subnet mask can be represented in two ways: one is the usual dot-
decimal notation like an IP address, and the second using the CIDR
notation.
IP Addressing
What is the default mask for class A,B and class C Networks?

Class A - [Link]
11111111.00000000.00000000.00000000
Class B - [Link]
11111111.11111111.00000000.00000000
Class C - [Link]
11111111.11111111.11111111.00000000
IP Addressing
Given the network address [Link], find the class, the network id,
and the range of the addresses

The 1st byte is between 128 and 191.

Hence, Class B The block has a network id of 132.22.
The addresses range from [Link] to [Link].
Subnetting
• Subnetting involves dividing the network into smaller portions called subnets.
• An IP address is divided in two parts, one for network identification and one for
host identification
• Using the subnet mask the main network is divided in one or more smaller
networks.
• This is performed by a bitwise AND operation between the IP address and the
(sub)network mask.
• In simple terms, this means that a part of the bits from the host number are used
for the new (sub)network identification.
IP Addressing - Subnetting
What is the subnetwork address if the destination address is
[Link] and the subnet mask is [Link]?

Ans.
IP address [Link]
Subnet Mask [Link]

11001000 00101101 00100010 00111000

AND 11111111 11111111 11110000 00000000
11001000 00101101 00100000 00000000
The subnetwork address is [Link]
IP Addressing - Subnetting
A company is granted the site address [Link] (class C). The
company needs six subnets. Design the subnets. Find the number of
addresses of each subnet.

Ans.
The number of 1s in the default mask is 24 (class C).
The company needs six subnets. This number 6 is not a power of 2. The
next number that is a power of 2 is 8 (23 ). We need 3 more 1s in the
subnet mask. The total number of 1s in the subnet mask is 27 (24 + 3).
The total number of 0s is 5 (32 - 27). The mask is 11111111 11111111
11111111 11100000 or [Link] The number of subnets is 8. The
number of addresses in each subnet is 25 (5 is the number of 0s) or 32.
IP Addressing - Subnetting
You currently use the default mask for your IP network [Link]. You
need to subnet your network so that you have 30 additional networks,
and 4 hosts per network. Is this possible, and what subnet mask should
you use?

Ans.
Yes it is possible.
The default subnet mask is 24. So 8 bits are remaining in host id
We need to 8 = bb (bits borrowed) + bl (bits left)
4 ≤ 2bl − 2 hence bl = 3
30 ≤ 2bb − 2 hence bb = 5
so the subnet mask is: 11111111.11111111.11111111.1111000
[Link].
IP Addressing - Subnetting
A small organization is given a block with the beginning address and the
prefix length [Link]/29 (in slash notation). What is the range of
the block?
Ans.
The beginning address is [Link].
To find the last address we keep the first 29 bits and change the last 3
bits to 1s.
Beginning: 11001111 00010000 00100101 00011000
Ending : 11001111 00010000 00100101 00011111
There are only 8 addresses in this block. We can argue that the length
of the suffix is 32 - 29 or 3. So there are 23 = 8 addresses in this block. If
the first address is [Link], the last address is [Link] (24 +
7 = 31).
IP Addressing - Subnetting
A small organization is given a block with the beginning address and the
prefix length [Link]/29 (in slash notation). What is the range of
the block?
Ans.
The beginning address is [Link].
To find the last address we keep the first 29 bits and change the last 3
bits to 1s.
Beginning: 11001111 00010000 00100101 00011000
Ending : 11001111 00010000 00100101 00011111
There are only 8 addresses in this block. We can argue that the length
of the suffix is 32 - 29 or 3. So there are 23 = 8 addresses in this block. If
the first address is [Link], the last address is [Link] (24 +
7 = 31).
IP Addressing
In the TCP/IP model, which layer is responsible for logical addressing of host computers and routing
messages? Say as much as you can about how the following sequences identify a particular network,
host computer and application, assuming the classfull addressing system:
•[Link]:25
•[Link]:23
•[Link]:80
Ans.
Logical addressing and routing: Internet or Network (not Network Access) layer.
[Link]:25 First two octets (decimal 129.8) identify network as class B (in range 128.n.n.n -
191.n.n.n or binary version starts with 10); two octets before colon identify host machine; final number
identifies port number of email application (SMTP)).
[Link]:25 First octet (decimal 124) identifies network as class A (in range 1.n.n.n - 126.n.n.n or
binary version starts with 0); three octets before colon identify host machine; final number identifies
port number of Telnet.
[Link]:80 First three octets (decimal 220.3.6) identify network as class C (in range 192.n.n.n -
223.n.n.n or binary version starts with 110); octet before colon identifies host machine; final number
identifies port number of WWW application (HTTP)
IP Addressing - Supernetting
We need to make a supernetwork out of 16 class C blocks. What is the
supernet mask?

Ans.
We need 16 blocks. For 16 blocks we need to change four 1s to 0s in
the default mask. So the mask is
11111111 11111111 11110000 00000000

or [Link]
IP Addressing - Supernetting
Given the following IP in CIDR format [Link]/[Link] the network,
the host addresses, and the range of addresses.

Ans.
[Link]/23.

IP 11000001 10100111 0000100 00000000

Mask 11111111 11111111 11111110 00000000
network address [Link] host address 0.0[2] the range of host
addresses is between [Link] to [Link]
Routing
Distance vector routing is used, and the following vectors have just
come in to router C: from B: (5, 0, 8, 12, 6, 2); from D: (16, 12,
6, 0, 9, 10); and from E: (7, 6, 3, 9, 0, 4). The cost of the links from C to
B, D, and E, are 6, 3, and 5, respectively. What is C’s new routing table?
Give both the outgoing line to use and the cost.

Ans.
Routing
If costs are recorded as 8-bit numbers in a 50-router network, and
distance vectors are exchanged twice a second, how much bandwidth
per (full-duplex) line is chewed up by the distributed routing algorithm?
Assume that each router has three lines to other routers.

Ans. The routing table is 400 bits. Twice a second this table is written
onto each line, so 800 bps are needed on each line in each direction.
Routing
For hierarchical routing with 4800 routers, what region and cluster sizes should be
chosen to minimize the size of the routing table for a three-layer hierarchy? A good
starting place is the hypothesis that a solution with k clusters of k regions of k
routers is close to optimal, which means that k is about the cube root of 4800
(around 16). Use trial and error to check out combinations where all three
parameters are in the general vicinity of 16.

Ans. Use a convenient tool to search for three sizes with a product of at least 4800
(to be large enough to cover the entire network) and minimum sum (to have the
smallest routing table). We found six solutions of clusters, regions and routers of
sizes: (17, 17, 17), (16, 17, 18), (16, 16, 19), (15, 18, 18), (15, 17, 19), and (15, 16,
20). Of these (17, 17, 17) is the most straightforward choice. In all cases the table
size is 51.
Routing
How many packets are generated
by a broadcast from B, using
(a) reverse path forwarding?
(b) the sink tree?

Ans. (a) The reverse path forwarding algorithm takes five rounds to finish. The
packets sent on these rounds, where * denotes a recipient that received the
broadcast along the sink tree and will broadcast in the next round, are:
Round 1: B sends to A*C*
Round 2: A sends to D*F*, and C sends to I *J *
Round 3: D to G*H *I, F to HK *, I to DJ, and J to E*IN *.
Round 4: G to L, H to EFO, K to L*, E to H, and N to M *O*.
Round 5: L to GM, M to L, and O to H.
There is a total of 28 packets across the rounds.
(b) The sink tree is shown in the figure. It needs four rounds and 14 packets.
Routing
Compute a multicast spanning tree for router C for
a group with members at routers A, B, C, D, E, F, I, K.

Ans. Multiple spanning trees are possible. One of them is:

Traffic Shaping
A token bucket scheme is used for traffic shaping. A new token is put into the bucket
every 5 μsec. Each token is good for one short packet, which contains 48 bytes of
data. What is the maximum sustainable data rate?

Ans. With a token every 5 µsec, 200,000 cells/sec can be sent. Each packet holds
48 data bytes or 384 bits. The net data rate is then 76.8 Mbps.
Traffic Shaping
A computer on a 6-Mbps network is regulated by a token bucket. The token bucket
is filled at a rate of 1 Mbps. It is initially filled to capacity with 8 megabits. How long
can the computer transmit at the full 6 Mbps?

Ans. The naive answer says that at 6 Mbps it takes 4/3 sec to drain an 8 megabit
bucket. However, this answer is wrong, because during that interval, more
tokens arrive. The correct answer can be obtained by using the formula
S = B /(M − R). Substituting B = 8 Mbit, M = 6 Mbps and R = 1 Mbps, we
get S = 8/(6 − 1) or 1.6 seconds.
Traffic Shaping
Imagine a flow specification that has a maximum packet size of 1000 bytes, a token
bucket rate of 10 million bytes/sec, a token bucket size of 1 million bytes, and a
maximum transmission rate of 50 million bytes/sec. How long can a burst at
maximum speed last?

Ans. Call the length of the maximum burst interval ∆t. In the extreme case, the
bucket is full at the start of the interval (1 Mbyte) and another 10∆t Mbytes
come in during the interval. The output during the transmission burst contains 50∆t
Mbytes. Equating these two quantities, we get 1 + 10∆t = 50∆t.
Solving this equation, we get ∆t is 25 msec.
Traffic Shaping
In a leaky bucket used to control liquid flow, how many gallons of liquid are left in the
bucket if the output rate is 5 gal/min, there is an input burst of 100 gal/min for 12 s,
and there is no input for 48 s?

Ans. Here we have to compute total input we have in one minute

So For 12 second input burst is 100 gallons and for 48 seconds no input.
Total Input = 100*12/60 + 0*48/60 = 20 gallons.

The output rate is 5 Gallon per minute so in one minute, 20 – 5 = 15 gallons are left.
IP Fragmentation
Suppose that host A is connected to a router R 1, R 1 is connected to another router,
R 2, and R 2 is connected to host B. Suppose that a TCP message that contains
900 bytes of data and 20 bytes of TCP header is passed to the IP code at host A for
delivery to B. Show the Total length, Identification, DF, MF, and Fragment offset
fields of the IP header in each packet transmitted over the three links. Assume that
link A-R1 can support a maximum frame size of 1024 bytes including a 14-byte
frame header, link R1-R2 can support a maximum frame size of 512 bytes, including
an 8-byte frame header, and link R2-B can support a maximum frame size of 512
bytes including a 12-byte frame header.
IP Fragmentation
Ans. We have an IP payload of 920 bytes to send. Assume a 20 byte IPv4 header.
The first link can carry IP packets up to 1010 bytes, so there will be no fragmentation.
The second link can carry IP packets up to 504 bytes, so there will
be fragmentation. There may be up to 484 bytes of data, but fragments must carry a
multiple of 8 bytes of data (except the last fragment). So the first fragment will carry
480 bytes of data, and the second fragment will carry 440 bytes. The third link can
carry IP packets up to 500 bytes, so both fragments will fit and no other
fragmentation will occur. The value of the fields is:
Link A-R1:
Length = 940; ID = x; DF = 0; MF = 0; Offset = 0
Link R1-R2:
(1) Length = 500; ID = x; DF = 0; MF = 1; Offset = 0
(2) Length = 460; ID = x; DF = 0; MF = 0; Offset = 60
Link R2-B:
(1) Length = 500; ID = x; DF = 0; MF = 1; Offset = 0
(2) Length = 460; ID = x; DF = 0; MF = 0; Offset = 60
IP Fragmentation
A 4480 octet datagram is to be transmitted and needs to be fragmented because it
will pass through an Ethernet with a maximum payload of 1500 octets. Show the
Total Length, More flag, Fragment Offset values in each of the resulting fragments.

Ans.
4480 octet datagram has 20 octets Header and 4460 octet Payload.
1500 octet Ethernet frame has 20 octets Header and 1480 octet Payload.
So, Total Number of Datagrams: 3*1480=4440 octets 4460-4440=20 octets
Last datagram that carries 20 data octets and 20 IP header.
So total Fragments=4
Header Data More Fragment Fragment Offset
20 1480 1 0
20 1480 1 185
20 1480 1 370
20 20 0 555
IP
A router is blasting out IP packets whose total length (data plus header) is 1024
bytes. Assuming that packets live for 10 sec, what is the maximum line speed the
router can operate at without danger of cycling through the IP datagram ID number
space?

Ans
If the bit rate of the line is b, the number of packets/sec that the router can emit
is b/8192, so the number of seconds it takes to emit a packet is 8192/b.

To put out 65,536 packets takes 229/b sec.

Equating this to the maximum packet lifetime, we get 229/b = 10. Then, b is about
54 Mbps.
IP
Suppose that instead of using 16 bits for the network part of a class B address
originally, 20 bits had been used. How many class B networks would there have
been?

Ans
With a 2-bit prefix, there would have been 18 bits left over for the network.
Consequently, the number of networks would have been 218 or 262,144. However,
all 0s and all 1s are special, so only 262,142 are available.
IP
While IP addresses are tried to specific networks, Ethernet addresses are not. Can
you think of a good reason why they are not?

Ans
Each Ethernet adapter sold in stores comes hardwired with an Ethernet (MAC)
address in it. When burning the address into the card, the manufacturer has no
idea where in the world the card will be used, making the address useless for
routing. In contrast, IP addresses are either assigned either statically or dynamically
by an ISP or company, which knows exactly how to get to the host getting the IP
address.
IP
A large number of consecutive IP addresses are available starting at [Link].
Suppose that four organizations, A, B, C, and D, request 4000, 2000, 4000, and
8000 addresses, respectively, and in that order. For each of these, give the first IP
address assigned, the last IP address assigned, and the mask in the w.x.y.z/s
notation.

Ans
To start with, all the requests are rounded up to a power of two. The starting
address, ending address, and mask are as follows:
A: [Link] – [Link] written as [Link]/20
B: [Link] – [Link] written as [Link]/21
C: [Link] – [Link] written as [Link]/20
D: [Link] – [Link] written as [Link]/19
IP
A router has just received the following new IP addresses: [Link]/21,
[Link]/21, [Link]/21, and [Link]/21. If all of them use the same
outgoing line, can they be aggregated? If so, to what? If not, why not?

Ans
They can be aggregated to [Link]/19.
IP
The set of IP addresses from [Link] to [Link] has been aggregated to
[Link]/17. However, there is a gap of 1024 unassigned addresses from
[Link] to [Link] that are now suddenly assigned to a host using a
different outgoing line. Is it now necessary to split up the aggregate address into its
constituent blocks, add the new block to the table, and then see if any reaggregation
is possible? If not, what can be done instead?

Ans
It is sufficient to add one new table entry: [Link]/22 for the new block. If an
incoming packet matches both [Link]/17 and [Link]./22, the longest one
wins. This rule makes it possible to assign a large block to one outgoing line but
make an exception for one or more small blocks within its range.
````
IP
A router has the following (CIDR) entries in its routing table:
Address/mask Next hop
[Link]/22 Interface 0
[Link]/22 Interface 1
[Link]/23 Router 1
default Router 2
For each of the following IP addresses, what does the router do if a packet with that
address arrives?
(a) [Link]
(b) [Link]
(c) [Link]
(d) [Link]
(e) [Link]

Ans
The packets are routed as follows:
(a) Interface 1
(b) Interface 0
(c) Router 2
(d) Router 1
(e) Router 2
Switching
Consider an application that transmits data at a steady rate (for example the sender
generates an N-bit unit of data every K time units, where K is small and fixed). Also,
when such an application starts, it will continue running for a relatively long period of
time. Answer the following questions, briefly justifying your answers.
a) Would a packet-switched network or a circuit-switched network be more
appropriate for this application? Why?
b) Suppose a packet-switched network is used and the only traffic in this network
comes from this application as described above. Furthermore, assume that the
sum of the application data rates is less than the capacities of each and every
link. Is some form of congestion control needed? Why?
IP
Ans.
a) A circuit-switched network would be well suited to the application, because the
application involves long sessions with predictable smooth bandwidth
requirements. Since the transmission rate is known and not bursty, bandwidth
can be reserved for each application session without significant waste. In
addition, the overhead costs of setting up and tearing down connections are
amortized over the lengthy duration of a typical application session.
b) In the worst case, all the applications simultaneously transmit over one or more
network links. However, since each link has sufficient bandwidth to handle the
sum of all of the applications' data rates, no congestion (very little queuing) will
occur. Given such generous link capacities, the network does not need
congestion control mechanisms
Circuit Switching
Consider the Parameters:
N = Number of Hops between two given system = 4
L = Message Length in bits = 3200
B = Data rate in BPS = 9600
P = Fixed Packet size in Bits = 1024
H = Overhead Bits per Packet = 16
S = Call setup time in Second = 0.2
D = Propagation Delay per hop in second. = 0.001
Find End to End Delay For circuit switching only.

Ans:
T = C1 + C2 where C1 = Call Setup Time C2 = Message Delivery Time
C1 = S = 0.2
C2 = Propagation Delay + Transmission Time = N * D + L/B = 4 * 0.001 + 3200/9600
= 0.337
T = 0.2 + 0.337 = 0.537 sec