Introduction: Network Layer

• To deliver segment from sending to receiving host/ router.
• On sending side, it encapsulates segments into datagrams.
• On receiving side, it delivers segments to transport layer.
• Network layer protocols in every host and router.
• Router examines header fields in all IP datagrams passing through it.

​

2

Key Function of Network Layer

• Role of the network layer is simple - to move packets from a sending host to a receiving host.
• Two important network layer functions can be identified:
• Forwarding
• When a packet arrives at a router’s input link, the router must move the packet to the appropriate output link.
• Routing
• It’s a process of selecting best paths in a network.
• The network layer must determine the route or path taken by packets as they flow from a sender to a receiver.
• The algorithms that calculate these paths are referred to as routing algorithms.

3

Routing and Forwarding

4

Network Service Model

• Services provided by network layer for individual datagrams.
• Guaranteed delivery
• This service guarantees that the packet will eventually arrive at its destination.
• Guaranteed delivery with bounded delay
• This service not only guarantees delivery of the packet, but delivery within a specified host-to-host delay bound.

​

5

Network Service Model – Cont…

• Services provided by network layer for a flow of datagrams.
• In-order packet delivery
• This service guarantees that packets arrive at the destination in the order that they were sent.
• Guaranteed minimal bandwidth
• This network-layer service emulates the behaviour of a transmission link of a specified bit rate (for example, 1 Mbps) between sending and receiving hosts.
• As long as the sending host transmits bits at a rate below the specified bit rate, then no packet is lost.

​

6

Network Service Model – Cont…

• Guaranteed maximum jitter
• This service guarantees that the amount of time between the transmission of two successive packets at the sender is equal to the amount of time between their receipt at the receiver.
• Security services
• Using a secret session key known only by a source and destination host, the network layer in the source host could encrypt the payloads of all datagrams being sent to the destination host.
• The network layer in the destination host would then be responsible for decrypting the payloads.

​

7

Virtual Circuit Switching

• A VC consists of
1. A path between the source and destination hosts
2. VC numbers, one number for each link along the path
3. Entries in the forwarding table in each router along the path
• A packet belonging to a virtual circuit will carry a VC number in its header.
• VC number can be changed on each link
• New VC number comes from forwarding table

​

8

VC Forwarding Table

12

22

32

1

2

3

VC number

interface

number

Incoming interface Incoming VC # Outgoing interface Outgoing VC #

1 12 3 22

2 63 1 18

3 7 2 17

1 97 3 87

… … … …

forwarding table in

router:

VC routers maintain connection state information

9

Virtual Circuit Setup

There are three identifiable phases in a virtual circuit:

1. VC setup
2. Data transfer
3. VC teardown

​

​

1. initiate call

2. incoming call

3. accept call

4. call connected

5. data flow begins

6. receive data

10

Datagram Network

• In connectionless service, packets are injected into the subnet individually and routed independently of each other.
• No advance setup is needed. The packets are frequently called datagrams and the subnet is called a datagram subnet.
• Only directly-connected lines can be used.

​

1. send datagrams

2. receive datagrams

11

Datagram Network vs. Virtual Circuit Network

12

Router Architecture

• Routers have four components:
1. Input ports
2. Switching fabric
3. Output ports
4. Routing processor

​

13

Input Port Functions

​

​

​

​

​

• It performs the physical layer function of terminating an incoming physical link at a router.
• It performs link-layer functions needed to interoperate with the link layer at the other side of the incoming link; this is represented by the middle boxes in the input and output ports.
• A lookup function is performed at the input port; this will occur in the rightmost box of the input port.

​

line

termination

link

layer

protocol

(receive)

lookup,

forwarding

​

​

queueing

switch

fabric

14

Input Port Functions – Cont…

• The forwarding table is consulted to determine the router output port to which an arriving packet will be forwarded via the switching fabric.
• Control packets (for example, packets carrying routing protocol information) are forwarded from an input port to the routing processor.

​

15

Switching Fabrics

• It connects the router’s input ports to its output ports.
• It is completely contained within the router - a network inside of a network router.
• Switching rate: A rate at which packets can be transfer from inputs to outputs.
• Also measured as multiple of input/output line rate.
• Three types of switching fabrics:

​

​

memory

memory

bus

crossbar

16

Switching via Memory

​

​

​

​

​

• Like traditional computers, with switching between input and output ports being done under direct control of the CPU (routing processor).
• Packet signalled a routing processor via an interrupt then copied from the input port into processor memory.

​

17

Switching via Memory – Cont…

• Routing processor extracted the destination address from the header, from forwarding table, and copied the packet to the output port’s buffers.
• If the memory bandwidth is such that B packets per second can be written into, or read from, then the overall forwarding throughput must be less than B/2.
• Two packets cannot be forwarded at the same time, even if they have different destination ports.
• Only one memory read/write over the shared system bus can be done at a time.

​

18

Switching via bus

• An input port transfers a packet to the output port over a shared bus, without intervention by the routing processor.
• The packet is received by all output ports, but only the port that matches the label will keep the packet.
• The label is then removed at the output port, and only used within the switch to cross the bus.
• Switching speed of the router is limited to the bus speed.

​

bus

19

Switching via an interconnection network

• Crossbar switch consists 2N buses.
• N input ports to N output ports.
• Its overcome the bandwidth limitation of shared bus; used to interconnect processors in a multiprocessor computer architecture.
• Cross-point connection can be opened or closed at any time by the switch fabric controller.
• Crossbar networks are capable of forwarding multiple packets in parallel.

​

20

Output Port

​

​

​

​

​

• It buffers packets received from the switching fabric and transmits these packets on the outgoing link.
• Packets can be lost due to congestions lacks of buffers.
• When a link is bidirectional, an output port will typically be paired with the input port for that link on the same line card.

​

line

termination

link

layer

protocol

(send)

switch

fabric

21

Routing Processor

• The routing processor executes the routing protocols, maintains routing tables and attached link state information and computes the forwarding table for the router.
• It also performs the network management functions.

​

22

Internet Network Layer

routing protocols

• path selection
• RIP, OSPF, BGP

ICMP protocol

• error reporting
• router “signaling”

transport layer: TCP, UDP

link layer

physical layer

network

layer

23

IPv4 Datagram format

how much overhead?

• 20 bytes of TCP
• 20 bytes of IP
• = 40 bytes + application layer overhead

24

IP Address

• IP addresses are useful in identifying a specific host in a network.
• IP addresses are 32 bit numbers which are divided into 4 octets. Each octet represents 8 bit binary number.
• Below is an example of an IP address:

​

10101100

00010000

11111110

00000001

172

16

254

1

IP addresses are divided into 2 parts:

Network ID & Host ID

<NID> <HID> = IP Address

25

Classification of IP Addresses (Classful Addressing)

Class: A

Fix

7 Bit Network ID

24 Bit Host ID

Class: B

Fix

14 Bit Network ID

16 Bit Host ID

Class: C

Fix

21 Bit Network ID

8 Bit Host ID

Class: D

Fix

Multicast address

Class: E

Fix

Reserved address

26

Class A: (0.0.0.0 to 127.255.255.255)

​

​

• Only 126 addresses are used for network address.
• All 0’s and 1’s in Network-ID are dedicated for special IP address. So, total number of IP address in class A can be represented:

7 Bit Network ID

24 Bit Host ID

27

Class B: (128.0.0.0 to 191.255.255.255)

​

​

• No special network address here. All are usable.

Fix

14 Bit Network ID

16 Bit Host ID

28

Class C: (192.0.0.0 to 223.255.255.255)

Fix

21 Bit Network ID

8 Bit Host ID

29

Class D: (224.0.0.0 to 239.255.255.255)

• Very first four bits of the first octet in Class D IP addresses are set to 1110, giving a range of:

​

​

​

• Class D has IP address rage from 224.0.0.0 to 239.255.255.255.
• Class D is reserved for Multicasting.
• In multicasting data is not destined for a particular host, that is why there is no need to extract host address from the IP address, and Class D does not have any subnet mask.

30

Class E: (240.0.0.0 to 255.255.255.255)

• This IP Class is reserved for experimental purposes only for R&D or Study.
• IP addresses in this class ranges from 240.0.0.0 to 255.255.255.254.
• Like Class D, this class too is not equipped with any subnet mask.

31

IP Addressing Summary

32

IP Addressing - Example

• IP address: It is 32-bit identifier for host, router interface
• Interface: It is a connection between host/router and physical link.
• A router’s typically have multiple interfaces
• A host typically has one or two interfaces
• IP addresses associated with each interface.

​

223.1.1.1

223.1.1.2

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

223.1.1.1 = 11011111 00000001 00000001 00000001

223

1

1

1

33

Subnet

• Subnet: high order bits defines subnet
• Host: low order bits defines host
• To determine the subnets, detach each interface from its host or router.
• Creating islands of isolated networks, with interfaces terminating the end points of the isolated networks.
• Each of these isolated networks is called a subnet.

​

Network consisting of 3 subnets

34

Type of addresses in IPv4 Network

• Network address - The address by which we refer to the network.
• E.g.: 10.0.0.0
• Broadcast address - A special address used to send data to all hosts in the network.
• The broadcast address uses the highest address in the network range.
• E.g.: 10.0.0.255
• Host addresses - The addresses assigned to the end devices in the network.
• E.g.: 10.0.0.1

​

35

Type of addresses – Cont…

36

Classless Inter-Domain Routing(CIDR)

• CIDR is a slash notation of subnet mask. CIDR tells us number of on bits in a network address.

​

​

​

​

• A single IP address can be used to designate many unique IP addresses with CIDR.
• A CIDR IP address looks like a normal IP address except that it ends with a slash followed by a number, called the IP network prefix.
• CIDR addresses reduce the size of routing tables and make more IP addresses available within organizations.

​

11001000 00010111 00010000 00000000

subnet

part

host

part

200.23.16.0/23

37

Subnetting

• Subnetting take places when we extend the default subnet mask.
• We cannot perform subnetting with default subnet mask and every classes have default subnet mask.
• Now find the host bits borrowed to create subnets and convert them in decimal.
• For example find the subnet mask of address 188.25.45.48/20 ?
1. Class B, Default Subnet mask: 255.255.0.0
2. Borrowed 4 bit from host part so mask is now:

11111111 11111111 11110000 00000000

255 255 240 0

38

How many subnets from given subnet mask?

• To calculate the number of subnets provided by given subnet mask we use 2^N , where N = number of bits borrowed from host bits to create subnets.
• For example in 192.168.1.0/27, N is 3.
• By looking at address we can determined that this address is belong to class C and default subnet mask 255.255.255.0 [/24 in CIDR].
• In given address we borrowed 27 - 24 = 3 host bits to create subnets.
• Now 2³ = 8, so our answer is 8.

​

39

What are the valid subnets?

• Calculating valid subnet is two steps process.
• First calculate total subnet by using formula 2^N.
• In second step find the block size and count from zero in block until subnet mask value.
• For example calculate the valid subnets for 192.168.1.0/26
1. Borrowed host bits are 2 [26-24]
2. Total subnets are 2² = 4
3. Subnet mask would be 255.255.255.192
4. Block size would be 256-192 = 64
5. Start counting from zero at blocks of 64, so our valid subnets would be 0,64,128,192

40

What are the total hosts?

• Total hosts are the hosts available per subnet
• To calculate total hosts use formula 2^H = Total hosts
• H is the number of host bits
• For example in address 192.168.1.0/26
• We have 32 - 26
1. [Total bits in IP address - Bits consumed by network address] = 6
2. Total hosts per subnet would be 2⁶ = 64

​

41

Network Prefixes

• For Class C, Default subnet mask of class C is 255.255.255.0
• CIDR notation of class C is /24, which means 24 bits from IP address are already consumed by network portion.
• We have 8 host bits remain.
• Subnetting moves from left to right. So Class C subnet masks can only be the following:

​

42

Network Prefixes- Example

• /25
• CIDR /25 has subnet mask 255.255.255.128 and 128 is 10000000 in binary.
• We used one host bit in network address.
• N = 1 [Number of host bit]
• H = 7 [Remaining host bits]
• Total subnets ( 2^N ) : 2¹ = 2
• Block size (256 - subnet mask) :- 256 - 128 = 128
• Valid subnets ( Count blocks from 0) :- 0, 128
• Total hosts (2^H) :- 2⁷ = 128
• Valid hosts per subnet ( Total host - 2 ) :- 128 - 2 = 126

43

Dynamic Host Configuration Protocol - DHCP

• Dynamic Host Configuration Protocol is a protocol for assigning dynamic IP addresses to devices on a network.

​

223.1.1.0/24

223.1.2.0/24

223.1.3.0/24

223.1.1.1

223.1.1.3

223.1.1.4

223.1.2.9

223.1.3.2

223.1.3.1

223.1.1.2

223.1.3.27

223.1.2.2

223.1.2.1

DHCP

server

arriving DHCP

client needs

address in this

network

44

DHCP – Cont…

• With dynamic addressing, a device can have a different IP address every time it connects to the network.
• In some systems, the device's IP address can even change while it is still connected.
• It allows reuse of addresses (only hold address while connected “on”).
• It also support mobile users who want to join network.

​

45

DHCP Client Server Interaction

DHCP server: 223.1.2.5

arriving

client

46

Network Address Translation

• NAT is a method that is used to translate Private IP addresses to Public IP addresses.

10.0.0.1

10.0.0.2

10.0.0.3

10.0.0.4

138.76.29.7

local network

(e.g., home network)

10.0.0/24

rest of

Internet

datagrams with source or

destination in this network

have 10.0.0/24 address for

source, destination (as usual)

all datagrams leaving local

network have same single source NAT IP address: 138.76.29.7,different source port numbers

47

NAT – Cont…

• Local network uses just one IP address as far as outside world is concerned.
• This means that only a single, unique IP address is required to represent an entire group of computers.
• The technique was originally used for ease of rerouting traffic in IP networks without readdressing every host.
• The concept of NAT as developed to solve two problems:
• Solve shortage of IPv4 IP addresses
• To Hide the Network Address

​

48

NAT Terminology

• Inside Local Address: The name of the inside source address before translation. This would be a Private IP.
• Inside Global Address: The name of the inside host after translation. This would be the Public IP.
• Outside Local Address: The name of the destination host before translation.
• Outside Global Address: The name of the destination host after translation.
• Where:
• Global Addresses → Public
• Local Addresses → Private
• Inside Hosts → Within Local Network
• Outside Hosts → Outside Local Network

​

49

NAT – Cont…

10.0.0.1

10.0.0.2

10.0.0.3

10.0.0.4

138.76.29.7

NAT translation table

WAN side addr LAN side addr

138.76.29.7, 5001 10.0.0.1, 3345

…… ……

3: reply arrives

dest. address:

138.76.29.7, 5001

4: NAT router

changes datagram

dest addr from

138.76.29.7, 5001 to 10.0.0.1, 3345

​

50

Internet Control Message Protocol - ICMP

• When something unexpected occurs, the event is reported by the ICMP, which is also used to test the Internet.
• About a dozen types of ICMP messages are defined. The most important are listed below. Each ICMP message type is encapsulated in an IP packet.

​

51

IPv6 Datagram Format

52

Difference between IPv4 & IPv6

53

Link State Routing Algorithm

• Also known as Dijkstra’s Algorithm.
• It computes the least-cost path from one node (source node) to all other nodes in the network.
• Its iterative and after the k^th least-cost paths are known to k destination nodes.
• Notation:
• c(x,y): link cost from node x to y; = ∞ if not direct neighbours
• D(v): current value of cost of path from source to destination v
• p(v): predecessor node along path from source to v
• N': set of nodes whose least cost path definitively known

​

​

​

54

Dijkstra’s Algorithm

1 Initialization:

2 N' = {u}

3 for all nodes v

4 if v adjacent to u

5 then D(v) = c(u,v)

6 else D(v) = ∞

7

8 Loop

9 find w not in N' such that D(w) is a minimum

10 add w to N'

11 update D(v) for all v adjacent to w and not in N' :

12 D(v) = min( D(v), D(w) + c(w,v) )

13 /* new cost to v is either old cost to v or known

14 shortest path cost to w plus cost from w to v */

15 until all nodes in N'

55

Dijkstra’s Algorithm – Example:1

Step

​

N'

D(v)

p(v)

0

1

2

3

4

5

D(w)

p(w)

D(x)

p(x)

D(y)

p(y)

D(z)

p(z)

u

uw

uwx

uwxv

uwxvy

12,y

uwxvyz

56

Dijkstra’s Algorithm – Example:2

Step

0

1

2

3

4

5

N'

u

ux

uxy

uxyv

uxyvw

uxyvwz

D(v),p(v)

2,u

2,u

2,u

D(w),p(w)

5,u

4,x

3,y

3,y

D(x),p(x)

1,u

D(y),p(y)

∞

2,x

D(z),p(z)

∞

∞

4,y

4,y

4,y

57

Dijkstra’s Algorithm – Example:2

resulting shortest-path tree from u:

resulting forwarding table in u:

58

Distance Vector Algorithm

• Distance-vector (DV) algorithm is iterative, asynchronous, and distributed.
• It is distributed in that each node receives some information from one or more of its directly attached neighbours, performs a calculation, and then distributes the results of its calculation back to its neighbours.
• It is iterative. so, process continues on until no more information is exchanged between neighbours.
• The algorithm is asynchronous. It does not require all of the nodes to operate with each other.

59

Distance Vector Algorithm – Cont…

• Let dx(y) be the cost of the least-cost path from node x to node y.
• Then least costs are related by the celebrated Bellman-Ford equation:

​

4-60

​

​

d_x(y) = cost of least-cost path from x to y then

d_x(y) = min {c(x,v) + d_v(y) }

​

v

cost to neighbor v

min taken over all neighbors v of x

cost from neighbor v to destination y

60

Distance Vector Algorithm – Cont…

​

wait for (change in local link cost or message from neighbor)

​

recompute estimates

​

if DV to any destination has changed, notify neighbors

​

each node:

61

Distance Vector Algorithm - Example

x y z

x

y

z

0 2 7

∞

∞

∞

∞

∞

∞

from

cost to

from

from

x y z

x

y

z

0

x y z

x

y

z

∞

∞

∞

∞

∞

cost to

x y z

x

y

z

∞

∞

∞

7

1

0

cost to

∞

2 0 1

∞ ∞ ∞

2 0 1

7 1 0

time

node x

table

D_x(y) = min{c(x,y) + D_y(y), c(x,z) + D_z(y)} � = min{2+0 , 7+1} = 2

D_x(z) = min{c(x,y) + � D_y(z), c(x,z) + D_z(z)}

= min{2+1 , 7+0} = 3

3

2

node y

table

node z

table

cost to

from

62

Distance Vector Algorithm - Example

x y z

x

y

z

0 2 3

from

cost to

x y z

x

y

z

0 2 7

from

cost to

x y z

x

y

z

0 2 3

from

cost to

x y z

x

y

z

0 2 3

from

cost to

x y z

x

y

z

0 2 7

from

cost to

2 0 1

7 1 0

2 0 1

3 1 0

2 0 1

3 1 0

2 0 1

3 1 0

2 0 1

3 1 0

time

x y z

x

y

z

0 2 7

∞

∞

∞

∞

∞

∞

from

cost to

from

from

x y z

x

y

z

0

x y z

x

y

z

∞

∞

∞

∞

∞

cost to

x y z

x

y

z

∞

∞

∞

7

1

0

cost to

∞

2 0 1

∞ ∞ ∞

2 0 1

7 1 0

time

node x

table

3

2

node y

table

node z

table

cost to

from

63

Difference: LS and DV Routing Algorithm

64

Hierarchical Routing

• As networks grow in size, the router routing tables grow proportionally.
• Router memory, CPU time and more bandwidth consumed to send status reports about them.
• When hierarchical routing is used, the routers are divided into what called regions.
• Each router knowing all the details about how to route packets to destinations within its own region.
• But knowing nothing about the internal structure of other regions.

​

65

Hierarchical Routing - Example

66

Broadcast Routing

• Host need to send messages to many or all other hosts.
• For example
• A service distributing weather reports
• Stock market updates
• Live radio programs
• In Short, Sending a packet to all destinations simultaneously is called broadcasting.
• First broadcasting method that simply send a distinct packet to each destination.
• So, it waste of bandwidth, but it also requires the source to have a complete list of all destinations.
• In practice this may be the only possibility, but it is the least desirable of the methods.

67

Broadcast Routing – Cont…

• Flooding is Second method. Although flooding is for ordinary point-to-point communication, for broadcasting it might rate serious consideration, especially if none of the methods are applicable.
• The problem with flooding as a broadcast technique is the same problem it has as a point-to-point routing algorithm.
• It generates too many packets and consumes too much bandwidth.
• A third algorithm is Multi Destination Routing.
• If this method is used, each packet contains either a list of destinations or a bit map indicating the desired destinations.

​

68

Broadcast Routing – Cont…

• When a packet arrives at a router, the router checks all the destinations to determine the set of output lines that will be needed.
• The router generates a new copy of the packet for each output line to be used and includes in each packet only those destinations that are to use the line.
• A fourth broadcast algorithm makes explicit use of the sink tree for the router initiating the broadcast-or any other convenient spanning tree for that matter.
• A spanning tree is a subset of the subnet that includes all the routers but contains no loops.
• If each router knows which of its lines belong to the spanning tree, it can copy an incoming broadcast packet onto all the spanning tree lines except the one it arrived on.

​

69

Multicast Routing

• Sending a message to a group is called multicasting, and its routing algorithm is called multicast routing.
• Multicasting requires group management. Need to create and destroy groups, and to allow processes to join and leave groups.
• To do multicast routing, each router computes a spanning tree covering all other routers.
• For example, in Figure (a) we have two groups, 1 and 2.
• Some routers are attached to hosts that belong to one or both of these groups, as indicated in the figure.

​

70

Multicast Routing – Cont…

• A spanning tree for the leftmost router is shown in Figure (b).
• When a process sends a multicast packet to a group, the first router examines its spanning tree and prunes it, removing all lines that do not lead to hosts that are members of the group.
• In our example, Figure (c) shows the pruned spanning tree for group 1.
• Figure(d) shows the pruned spanning tree for group 2. Multicast packets are forwarded only along the appropriate spanning tree.

​

71

Comparison between RIP OSPF and BGP

72

Thank You