Computer network coe351- part3-final

Course code: COE351
Course title : Computer Networks
PART: 3
Prof. Taymoor Mohamed Nazmy
Dept. of computer science, faculty of computer science, Ain Shams uni.
Ex-vice dean of post graduate studies and research Cairo, Egypt
1

Goals of the Network Layer
• The network layer is concerned with getting packets
from the source all the way to the destination
• the network layer must
– know the topology of the communication subnet
– choose route to avoid overloading some of the
communication lines and routers
– deal with problems when the source and destination are in
different networks

How the network layer works?
• On TCP/IP networks each computer is identified
with a unique virtual address, called IP address.
• The Internet layer is in charge of adding a header
to the data packet received from the Transport
layer where, among other control data, it will add
the source IP address and the target IP address –
i.e., the IP address of the computer that is sending
the data and the IP address of the computer that
should receive the data.
5

• The network card of each computer has a physical
address assigned to it. This address is written on
the network card read-only memory (ROM) and is
called MAC address.
• So on a local area network whenever computer A
wants to send data to computer B, it will have to
know computer’s B MAC address.
• While on a small local area network computers
can easily discover each other’s MAC address,
this isn’t an easy task on a global network like the
Internet.
6

• On every network that is connected to the Internet there
is a device called router, which makes the bridge
between the computers on your local area network and
the Internet.
• Every router has a table with its known networks and
also a configuration called default gateway pointing to
another router on the Internet.
• When your computer sends a data packet to the
Internet, the router connected to your network first
looks if it knows the target computer – in other words,
if the target computer is located on the same network or
on a network that the router knows the path to.
7

• If it doesn’t know, it will send the packet to its
default gateway, i.e., to another router. Then the
process repeats until the data packet arrives at its
destination.
• Routing is the path that a data packet should use
in order to arrive at destination.
• When requesting data from an Internet server, for
example, this data passes through several
locations (called routers) before arriving at your
computer.
8

• Then on the command prompt type in tracer
www.google.com. The output will be the path
between your computer and Google’s web server.
• See how the data packet passes through several
different routers before arriving at its destination.
• Each router in the middle of the road is also called
hop.
9

• The following protocols operate at the TCP/IP Internet layer:
• • IP provides connectionless, best-effort delivery routing of packets. IP is
not concerned with the content of the packets but looks for a path to the
destination.
• Internet Control Message Protocol (ICMP) provides control and
messaging capabilities. send error messages and operational information
indicating, for example, that a requested service is not available
• Address Resolution Protocol (ARP) determines the data link layer address,
MAC address, for known IP addresses.
• Reverse Address Resolution Protocol (RARP) determines IP addresses
when the MAC address is known.
Network layer protocols
10

What Is an Address?
• For computers to send and receive information to
each other, they must have some form of
addressing so that each end device on the network
knows what information to read and what
information to ignore.
• This capability is important both for the
computers that ultimately use the information and
for the devices that deliver information to end
stations, such as switches and routers.
11

ADDRESSING
• Four levels of addresses are used in an internet employing the
TCP/IP protocols:
•
– Physical address
• Ex. Ehternet address, machine address
– Logical address
• IP address
– Port number
Applications
– Specific
• URL, domain name
2.12

Relationship of layers and addresses in
TCP/IP
2.13

14
The Address Resolution Protocol ARP
Anytime a host or a router has an IP datagram to send to another
host or router, it has the logical (IP) address of the receiver.
But the IP datagram must be encapsulated in a frame to be able to
pass through the physical network. This means that the sender needs
the physical address of the receiver. A mapping corresponds a
logical address to a physical address.
The address resolution protocol ARP accepts a logical address from
the IP protocol, maps the address to the corresponding physical
address and pass it to the data link layer.

Physical versus Logical
• MAC addresses are considered physical addresses
• because they are assigned to pieces of hardware
by the manufacturer and cannot be reassigned.
• IP addresses are assigned by a network
administrator and have meaning only in a TCP/IP
network. These addresses are used solely for
routing purposes and can be reassigned.
15

Types of IP address
• Static address
• Dynamic address
17

Types of IP address
• Static IP address
– manually input by network administrator
– manageable for small networks
– requires careful checks to avoid duplication
18

Types of IP address
• Dynamic IP address
• examples - BOOTP, DHCP
– assigned by server when host boots
– derived automatically from a range of addresses
– duration of ‘lease’ negotiated, then address
released back to server
19

IP address
• 10.128.178.46.
• The format of this address is called dotted-decimal
notation. The period separators are pronounced “dot”.
• Because of some rules with binary, the largest number
in each section is 255. Think of an IP address as being
like your home address for the post office:
state.city.street.house-number.
• Each number in the IP address provides a more and
more specific location so that the Internet can find your
computer among millions of other computers.
20

• In the figure, the first two octets (128.10) identify a company
with an Internet presence (it’s the address of the router that
accesses the Internet).
• All computers and servers within the company’s network
share the same network address.
• The next two octets identify a specific endpoint (computer,
server, printer, and so on).
• In this example the company has 65,536 addresses it can
assign (16 bits, or 216). Therefore, all devices in this network
would have an address between 128.10.0.1 and
128.10.255.255.
21

IP address
• IP address: This address is what matters most to basic networking. Unlike
a MAC address, the IP address of any device is temporary and can be
changed.
• It is often assigned by the network itself and is analogous to your street
address. It only needs to be unique within a network. Someone else’s
network might use the same IP address, much like another town might have
the same street .
• Every device on an IP network is given an IP address, which looks like this:
192.168.1.100.
• Each IP address is a 32-bit number, which means that there are about 4.3
trillion address combinations.
• For example, the binary address
• 00001010100000001011001000101110 can be
• represented in dotted decimal as 10.128.178.46.
22

23
IPAddress as a 32-Bit Binary Number
Internet Addresses
23

24
Binary and Decimal Conversion
24

25
Change the following IPv4 addresses from binary notation to
dotted-decimal notation.
a. 10000001 00001011 00001011 11101111
b. 11000001 10000011 00011011 11111111
c. 11100111 11011011 10001011 01101111
d. 11111001 10011011 11111011 00001111
Solution
We replace each group of 8 bits with its equivalent decimal
number and add dots for separation
:
a. 129.11.11.239
b. 193.131.27.255
c. 231.219.139.111
d. 249.155.251.15
Example
25

26
Find the error, if any, in the following IPv4 addresses:
a. 111.56.045.78
b. 221.34.7.8.20
c. 75.45.301.14
d. 11100010.23.14.67
Solution
a. There should be no leading zeroes (045).
b. We may not have more than 4 bytes in an IPv4 address.
c. Each byte should be less than or equal to 255.
d. A mixture of binary notation and dotted-decimal notation.
Example
26

Address Classes
• IP addresses are divided into 5 classes, each of which is designated
with the alphabetic letters A to E.
• Class A-Class A addresses are assigned to networks with a very
large number of hosts.
• Class B-Medium to Large networks
• Class C- used for small networks.
• Class D- Class D addresses are reserved for IP multicast
addresses.
• Class E- Class E is an experimental address that is reserved for
future use. 27

29
IP Classes (continued)
• Class A
– Reserved for governments and large corporations
throughout the world
– Each Class A address supports 16,777,214 hosts
• Class B
– Addresses are assigned to large- and medium-sized
companies
– Each Class B address supports 65,534 hosts
Class A Class B Class C D
IP Address Space
E
50 % 25% 12.5% 6.25%

30
• Class C
– Addresses are assigned to groups that do not meet the
qualifications to obtain Class A or B addresses
– Each Class C address supports 254 hosts
• Class D
– Addresses (also known as multicast addresses) are reserved
for multicasting
– Multicasting is the sending of a stream of data (usually
audio and video) to multiple computers simultaneously

31
• Class E
– Addresses are reserved for research, testing, and
experimentation
– The Class E range starts where Class D leaves off
• Private IP ranges
– Many companies use private IP addresses for their internal
networks
• Will not be routable on the Internet
– Gateway devices have network interface connections to the
internal network and the Internet
• Route packets between them

33
Find the class of each address:
a. 00000001 00001011 00001011 11101111
b. 11000001 10000011 00011011 11111111
c. 10100111 11011011 10001011 01101111
d. 11110011 10011011 11111011 00001111
Solution
a. The first bit is 0. This is a class A address.
b. The first 2 bits are 1; the third bit is 0. This is a class C address.
c. The first bit is 1; the second bit is 0. This is a class B address.
d. The first 4 bits are 1s. This is a class E address.
Example
33

Subnetting
Subnetting is the process of segmenting a network into multiple smaller
network spaces called subnetworks or subnets.
• Large networks must be segmented into smaller subnetworks, creating
smaller groups of devices and services to:
• Control traffic by containing broadcast traffic within each subnetwork.
• Reduce overall network traffic and improve network performance.
Communication Between Subnets
• A router is necessary for devices on different networks and subnets to
communicate.
• Each router interface must have an IPv4 host address that belongs to the
network or subnet that the router interface is connected.
• Devices on a network and subnet use the router interface attached to their
LAN as their default gateway.
34

Subnetting
Subnetting
• Problem: Organizations have
multiple networks which are
independently managed
– Solution 1: Allocate an
address for each network
• Difficult to manage
• From the outside of the
organization, each network
must be addressable ie
have an identifiable
address.
– Solution 2: Add another level
of hierarchy to the IP
addressing structure
University Network
Medical
School
Library
Engineering
School
35

Subnet Mask
 With the rapid growth of the internet & the ever-
increasing demand for new addresses, the
standard address class structure has been
expanded by borrowing bits from the Host
portion to allow for more Networks.
 Under this addressing scheme, called
Subnetting, separating the Network & Host
requires a special process called Subnet
Masking.
37

SubnetApplications
Anywhere a large group of computers are
located. Example with subnet in class B

40
Subnet masks for class A, B, and C

41
Subnet Mask
• Determines which part of an IP address is the network field and which part is
the host field
• Follow these steps to determine the subnet mask:
– 1. Express the subnetwork IP address in binary form.
– 2. Replace the network and subnet portion of the
address with all 1s.
– 3. Replace the host portion of the address with all 0s.
– 4. Convert the binary expression back to dotted-
decimal notation.
41

42
Subnetting Example with AND Operation

Internet Protocol Version
4 (IPv4) vs (IPv6)
• IPv4 is 32-bit addressing scheme used as TCP/IP host addressing
mechanism. IP addressing enables every host on the TCP/IP network
to be uniquely identifiable.
• IPv4 has a theoretical maximum of 4.3 billion addresses
• Exhaustion of IPv4 addresses gave birth to a next generation
Internet Protocol version 6.
• IPv6 addresses its nodes with 128-bit wide address providing plenty
of address space for future to be used on entire planet or beyond.
• IPv6 is still in transition phase and is expected to replace between
2015 and 2020.
43

IPv4 and IPv6 Coexistence
The migration techniques can be divided into three categories:
Dual-stack, Tunnelling, and Translation.
Dual-stack: Allows IPv4 and IPv6 to coexist on the same network. Devices
run both IPv4 and IPv6 protocol stacks simultaneously.
Tunnelling: A method of transporting an IPv6 packet over an IPv4
network. The IPv6 packet is encapsulated inside an IPv4 packet.
Translation: The Network Address Translation 64 (NAT64) allows IPv6-
enabled devices to communicate with IPv4-enabled devices using a
translation technique similar to NAT for IPv4. An IPv6 packet is translated to
an IPv4 packet, and vice versa.
45

46
DNS: The IP address of
“neon.tcpip-lab.edu” is
128.143.71.21
ARP: What is the MAC
address of 128.143.137.1?
Sending a packet from Argon to Neon
DNS: What is the IP address
of “neon.tcpip-lab.edu”?ARP: The MAC address of
128.143.137.1 is 00:e0:f9:23:a8:20
128.143.71.21 is not on my local network.
Therefore, I need to send the packet to my
default gateway with address 128.143.137.1
frame
128.143.71.21 is on my local network.
Therefore, I can send the packet directly.
ARP: The MAC address of
128.143.137.1 is 00:20:af:03:98:28
ARP: What is the MAC
address of 128.143.71.21?
frame
neon.tcpip-lab.edu
"Neon"
128.143.71.21
argon.tcpip-lab.edu
"Argon"
128.143.137.144
router137.tcpip-lab.edu
"Router137"
128.143.137.1
router71.tcpip-lab.edu
"Router71"
128.143.71.1
Ethernet NetworkEthernet Network
Router

How does a packet (IP Datagram) travel across the Internet?
A host:
• creates a packet
• places the destination address in the packet header
• sends the packet to a nearby router
A router
• receives a packet
• uses the destination address to select the next router on the
path
• forwards the packet
Eventually, the packet reaches a router that can deliver the packet
to its final destination

What is path from X to Y? this is the routing problem
49

Routing Protocol (IP routing)
• A routing protocol specifies how routers communicate
with each other, distributing information that enables them
to select routes between any two nodes on a computer
network.
• Routing algorithms determine the specific choice of route.
Each router has a priori knowledge only of networks
attached to it directly.
• A routing protocol shares this information first among
immediate neighbours, and then throughout the network.
This way, routers gain knowledge of the topology of the
network.
50

Routing Protocol Functions
• Routing Protocols: A software in the network layer that
implements routing algorithms and responsible for:
– Filling and updating routing tables (by finding the
shortest paths from each source to each destination)
This part is called Routing
– Deciding which output interface an incoming packet
should be transmitted on (by referring to the routing
table). This part is called Forwarding
51

52
Delivery of IP datagrams
• There are two distinct processes to delivering IP datagrams:
1. Forwarding: How to pass a packet from an input
interface to the output interface?
2. Routing: How to find and setup the routing tables?
• Forwarding must be done as fast as possible:
– on routers, is often done with support of hardware
– on PCs, is done in kernel of the operating system
• Routing is less time-critical
– On a PC, routing is done as a background process

54
Open Shortest Path First (OSPF)
Routing Information Protocol (RIP)
Interior Gateway Routing Protocol (IGRP)
Enhanced Interior Gateway Routing Protocol (EIGRP)]

Computer network coe351- part3-final

56
Hop Count
• A hop is defined as a passage through one router
R1 R2
R3
1 hop 1 hop
1 hop 1 hop
2 hops

5757
Routing Tables
• Routing is carried out in a router by consulting
routing table.
• No unique format for routing tables, typically
table contains:
– address of a destination
– IP address of next hop router
– network interface to be used
– subnet mask for the this interface
– distance to the destination

58
Routing tables
• Each router and each host keeps a routing table which tells the router how
to process an outgoing packet
• Main columns:
1. Destination address: where is the IP datagram going to?
2. Next hop or interface: how to send the IP datagram?
• Routing tables are set so that a datagram gets closer to the its destination
every hop
Destination Next Hop
10.1.0.0/24
10.1.2.0/24
10.2.1.0/24
10.3.1.0/24
20.1.0.0/16
20.2.1.0/28
direct
direct
R4
direct
R4
R4
Routing table of a host or router
IP datagrams can be directly delivered
(“direct”) or are sent to a router (“R4”)

Types of Routing
• Static Routing (Nonadaptive Routing)
– Routes to destinations are predetermined and are not dependent
on the current state (traffic, topology etc.) of the network. Do not
take into account actual network load.
• Dynamic Routing (Adaptive Routing)
– Routes being learned via exchange of routing information to
reflect changes in the topology and traffic. Taking into account
actual network load
• Default Routing:
– Traffic to destinations that are unknown to the router is sent to a
default “outlet”.
61

62
Learning About the Neighbors
• “HELLO” packed send on each point-to-
point line from a booted router.
• Router on the other end must reply by
sending its globally unique “name”.

63
Measuring Line Cost
• It is required by the Link State Routing algorithm
that each router not have a reasonable estimate of
the delay/cost to each of its neighbors.
– Send “ECHO” packet (ping) that the other side is
required to send back immediately.
• Measure Round Trip time; Divide by 2 to get
an estimate.
• More accurate estimate by repeating the
process several times and by averaging
estimates.

64
Measuring Line Cost (cont.)
• Including Traffic-induced Delays:
– If a router has a choice from 2 lines with the
same bandwidth, one of which is heavily loaded
all the time and one of which is not, the router
will regard the route over the unloaded line as
shorter path.
– This choice in general will result in better
performance

65
Routing Algorithms
• The routing algorithm is a part of network layer
software to decide which output line an incoming
packet should be transmitted on.
• Session routing is a route remains in force for an
entire user session.
• Routing algorithms should be correctness, simplicity,
robustness, stability, fairness, and optimality.
65

66
Routing Algorithms
• The Optimality Principle
• Shortest Path Routing
• Flooding
• Distance Vector Routing
• Link State Routing
• Hierarchical Routing
• Broadcast Routing
• Multicast Routing
• Routing for Mobile Hosts
• Routing in Ad Hoc Networks
66

Fixed Routing
• Single permanent route for each source to
destination pair
• Determine routes using a least cost algorithm
•
• Route fixed, at least until a change in network
topology
67

69
Flooding
• Every incoming packet is sent out every outgoing
• Retransmit on all outgoing at each node
• Simple technique, require no network information
• Generate vast numbers of duplicate packet

Properties of Flooding
• All possible routes are tried
• At least one packet will have taken minimum
hop count route
• All nodes are visited
71

Random Routing
• Node selects one outgoing path for retransmission of
incoming packet
• Selection can be random
• Can select outgoing path based on probability
calculation
• No network info needed
• Route is typically not least cost nor minimum hop
72

73
Shortest Path Routing
• Shortest Path Routing is a static routing algorithm that just
finds the shortest path.
• A graph is used to represent the network.
– Each node of the graph represents a router.
– Each arc of the graph represents a communication link.
– To choose the route between a given pair of routers, the algorithm
just finds the shortest path between them on the graph.
73

74
Dynamic routing:
1-Link State Routing
• Each router must do the following:
• The link-state protocol is performed by every routers.
The basic concept of link-state routing is that every
node constructs a map of the connectivity to the
network, in the form of a graph, showing which nodes
are connected to which other nodes.
• Each node then independently calculates the next best
logical path from it to every possible destination in the
network. Each collection of best paths will then form
each node's routing table.

76
Routing: shortest path
• Algorithm of Dijkstra: shortest path in graph
– Graph
• Node = router
• Arc = communication line
– Metric
• Number of hops
• Geographic distance
• Mean queueing and transmission delay

77
Shortest Path Routing
• Dijkstra Algorithm
– Each arc (link) is labeled with a weight (link distance).
– Each node is labeled with the distance from the source node
along the best known path and the source node.
– Initially, no paths are known, all nodes except the source are
labeled as (∞, -).
– All labels may be either tentative or permanent. Initially, the
labels are tentative. When it is discovered to be shortest
possible path, the label is made permanent and never
changed thereafter..

The Optimality Principle
• If router J is on the optimal path from router I to router
K, then the optimal path from J to K also falls along
the same route.
– the set of optimal routes from all sources to a destination
form a tree, called a sink tree, rooted at the destination.
• The goal of all routing algorithms is to discover and
use the sink trees for all routers.
I
J
Kr1
r2
78

79
d3 > d2
as
d1 + d3 > d1 + d2
Routing algorithms
• Optimality principle
I   K
J
Optimal path from I to K over J
d1
d2
distance
d1 + d2 is minimal
d3
Other path from J to K
Set of all optimal routes
• from all sources
• to a given destination
is a tree: sink tree

Optimization criterion
–Distance,
–Bandwidth,
–Average Traffic
–Communication cost,
–Mean Queue Length,
–Measured Delay,
81

82
Dijkstra’s Shortest Path First Algorithm
• Routers send out update messages whenever the
state of a link changes. Hence the name: “Link
State” algorithm.
• Each router calculates lowest cost path to all
others, starting from itself.
• At each step of the algorithm, router adds the next
shortest (i.e. lowest-cost) path to the tree.
• Finds spanning tree routed on source router.

83
Routing: shortest path
Initial node
Elements of algorithm:
• Mark all nodes as free: 
• Mark initial node as selected: 
• repeat till destination is selected:
• Label all free nodes reachable from selected nodes with shortest
distance to a selected node
• Select free node with shortest distance to a selected node and
mark it as selected

• A distance-vector routing protocol requires that a router
inform its neighbours of topology changes periodically.
• Compared to link-state protocols, which require a
router to inform all the nodes in a network of topology
changes, distance-vector routing protocols have less
computational complexity and message overhead.
• The term distance vector refers to the fact that the
protocol manipulates vectors (arrays) of distances to
other nodes in the network.
86
2-Routing: distance vector

87
2-Routing: distance vector
Routing table for A
To cost via
A 0 -
B 12 B
C 25 B
D 40 B
E 14 E
F 23 E
G 18 B
H 17 J
I 21 E
J 9 J
K 24 J
L 29 J

Adaptive Routing
• Used by almost all packet switching networks
• Routing decisions change as conditions on the
network change
– Failure
– Congestion
• Requires info about network
• Decisions more complex
• Tradeoff between quality of network info and
overhead
• Reacting too quickly can cause oscillation
• Too slowly to be relevant 89

What is a Router Made of?
• A router has many of the same components as
your computer:
– CPU
– Memory
– I/O Interfaces (mostly network interfaces)
– Operating System
90

Router Hardware
• Input buffers (one for each network interface):
– Used to store incoming packets before they are processed
• Routing processor:
– This is often software running on a CPU which:
• Maintains and exchanges routing data with other
routers
• Controls the switching fabric to forward packets
– With high-end routers, each network interface may have a
local routing processor (for forwarding) so that each can
forward the packets in its own input buffer independently
91

• Switching fabric:
–A network of connections between network
interfaces (and their input and output buffers)
• Output buffers (one for each network interface):
–Used to store outgoing packets after they are
processed, but before the network is available
for transmission
92

A Router is a Computer
Router CPU and OS
1. Power
Supply
2. Shield for WIC
3. Fan
4. SDRAM
5. NVRAM
6. CPU
7. Advanced
Integration
Module (AIM)
1 2 2
6
5
4
7 94

Router Backplane
Two 4 GB Flash Card Slots
Double-Wide EHWIC slots EHWIC 0 AUX
Port
LAN
Interfaces
USB
Ports
Console
USB Type B
Console
RJ45
95

Anatomy of a Router
Router CPU and OS
96

Routers: Network Interfaces
• Often, routers have modularized network interfaces
– One can add/remove/replace network interfaces as needs
change
– Some routers can accept network interface modules of
different types (e.g. Ethernet, Token Ring)
– Each network interface would have its own:
• Input buffer
• Output buffer
• Routing processor (in high-end routers)
97

Routers: Input Buffers
• The incoming packets of a network interface are placed in input
buffers
– These are banks of very high speed memory for packet queuing prior to
processing
– The packet is stored here until the routing processor is available
• The network interface may have a routing processor, which would:
– … have a copy of the forwarding table (to prevent concurrent access)
– … lookup the destination address in this forwarding table, to determine the
correct output port
– … configure the switching fabric to forward the packet to the correct output
buffer
• Low-end routers would share one routing processor
98

Routing Processors
• Routing processors have two functions:
1. Maintain and exchange routing data with other
routers in the network
Often this involves computing the forwarding table
from data received by other routers
2. Use the forwarding table data to configure the
switching fabric to forward the packet to the
correct output port
99

Types of Routing Processors
• A routing processor is software which executes on a
CPU:
– Off-the-shelf CPU
• These are very inexpensive
• However, the performance of these CPUs is low since they are
not optimized for the types of operations a router typically needs
to perform’
– Application-Specific Integrated Circuit (ASIC)
• These are expensive to design (time and money)
• They are optimized for typical routing operations
• High-end routers use these to achieve higher performance levels
100

Routers: Switching Fabric
• Switching fabric’s job is to move packets from
the input buffer into the correct output buffer
– The routing processor determines the correct
output port, using the forwarding table
101

Routers: Switching Fabric
• Switching fabric comes in 3 major types:
– In-memory switching fabric:
• The packets are input into the routing processor’s memory,
and output into the correct output buffer
– Bus-based switching fabric:
• The packets move along a shared bus (similar to a network
bus) to the correct output buffer
– Crossbar switching fabric:
• The packets move along a grid of redundant buses
• If any bus fails, alternate paths exist so that forwarding can
continue
102

Routers: Output Buffers
• The switching fabric gets the packet to the
right output port
– However, that port’s network may not be
immediately available
– The packets are stored in the output buffer until the
network is available
103

Computer network coe351- part3-final

Recommended

More Related Content

What's hot (20)

Similar to Computer network coe351- part3-final (20)

More from Taymoor Nazmy (20)

Recently uploaded (20)

Computer network coe351- part3-final