15Z502 COMPUTER

NETWORKS
Unit 4 – NETWORK AND ROUTING
UNIT IV- NETWORK AND ROUTING
Circuit Switching
Packet Switching
Virtual Circuit Switching
Routing
IP
Global Address
Datagram Forwarding
Subnetting
CIDR
ARP
DHCP
ICMP
IPv6.
IP Addressing Summary
Number of Networks and Hosts
Number of AVAILABLE Networks and Hosts!!
• Class A
• Total Address Space = 2 31 = 2147483648
• Number of Networks = 2 7 = 128
• Number of Hosts =2 24 = 16777216

• 2 Network addresses ( 0 & 127) are reserved

• 2 Hosts addresses are reserved

• Hence, total number of available addresses:

• Networks = 2 7 – 2 = 126
• Hosts = 2 24 -2 = 16777214
Number of AVAILABLE Networks and Hosts!!
• Class B
• Total Address Space = 2 30 = 1073741824
• Number of Networks = 2 14 = 16384
• Number of Hosts =2 16 = 65536

• 2 Hosts addresses are reserved

• Hence, total number of available addresses:

• Networks = 2 14 = 16384
• Hosts = 2 16 -2 = 65534
Number of AVAILABLE Networks and Hosts!!
• Class C
• Total Address Space = 2 29 = 536870912
• Number of Networks = 2 21 = 2097152
• Number of Hosts =2 8 = 256

• 2 Hosts addresses are reserved

• Hence, total number of available addresses:

• Networks = 2 21 = 2097152
• Hosts = 2 8 -2 = 254
Number of AVAILABLE Networks and Hosts!!
• Class D
• Total Address Space = 2 28 = 268435456
• Number of Networks = 1
• Number of Hosts =2 28 = 268435456

• Class E
• Total Address Space = 2 28 = 268435456
• Number of Networks = 1
• Number of Hosts =2 28 = 268435456
Range of special IP addresses:
• 127.0.0.0 – 127.0.0.8 : Loop-back addresses
• 0.0.0.0 – 0.0.0.8 : used to communicate within the current network
Subnetting and Classless Addressing
• The original intent of IP addresses was that the network part would
uniquely identify exactly one physical network.
• Imagine a large campus that has lots of internal networks and decides
to connect to the Internet.
• For every network, the site needs class C network address.
• For any network with more than 255 hosts, they need a class B address.
• Class B addresses tend to be in particularly high demand
• The problem is address assignment inefficiency:
• A network with two nodes uses an entire class C network address, wasting perfectly
useful addresses;
• class B network with slightly more than 255 hosts wastes over 64,000 addresses.
• Must find some way to use the network numbers more efficiently.
• Assigning many network numbers has another drawback that becomes
apparent when you think about routing.
• The amount of state that is stored in a node participating in a routing protocol is
proportional to the number of other nodes,
• Routing in an internet consists of building up forwarding tables that tell a router how
to reach different networks.
• Thus, the more network numbers there are in use, the bigger the forwarding tables
get.
• Big forwarding tables add costs to routers, and they are potentially slower to search
than smaller tables for a given technology, so they degrade router performance.
• This provides another motivation for assigning network numbers carefully.
Subnetting
• Subnetting is used to reduce the total number of network numbers
that are assigned.
• The idea is to take a single IP network number and allocate the IP
addresses with that network number to several physical networks,
which are now referred to as subnets.
• A perfect situation in which to use subnetting is a large campus or
corporation that has many physical networks.
• From outside the campus, all you need to know to reach any subnet inside
the campus is where the campus connects to the rest of the Internet.
• This is often at a single point so one entry in your forwarding table
will suffice.
• The mechanism by which a single network
number can be shared among multiple
networks involves configuring all the
nodes on each subnet with a subnet mask.
• With simple IP addresses, all hosts on the
same network must have the same
network number.
• The subnet mask enables us to introduce a
subnet number;
• all hosts on the same physical network will
have the same subnet number, which means
that hosts may be on different physical
networks but share a single network number.
• What subnetting means to a host is that it
is now configured with both an IP address
and a subnet mask for the subnet to which
it is attached.
• For example, host H1 is
configured :
• address of 128.96.34.15
• subnet mask of 255.255.255.128.
• (All hosts on a given subnet are
configured with the same mask;
that is, there is exactly one
subnet mask per subnet.)
• The bitwise AND of these two
numbers defines the subnet
number of the host and of all
other hosts on the same subnet.
• 128.96.34.15 AND
255.255.255.128 equals
128.96.34.0
• Host wants to send a packet to a certain
IP address,
• perform a bitwise AND between its own
subnet mask and the destination IP address.
• If the result equals the subnet number of the
sending host, then it knows that the
destination host is on the same subnet and
the packet can be delivered directly over the
subnet.
• If the results are not equal, the packet needs
to be sent to a router to be forwarded to
another subnet.
• If H1 is sending to H2,
• H1 ANDs its subnet mask (255.255.255.128)
with the address for H2 (128.96.34.139) to
obtain 128.96.34.128.
• This does not match the subnet number for
H1 (128.96.34.0) so H1 knows that H2 is on a
different subnet.
• Since H1 cannot deliver the packet to H2
directly over the subnet, it sends the packet
to its default router R1.
• The forwarding table of a router also changes slightly when we introduce
subnetting.
• To support subnetting, the table must now hold entries of the form
(SubnetNumber, SubnetMask, NextHop).
• To find the right entry in the table, the router ANDs the packet’s destination
address with the SubnetMask for each entry in turn;
• if the result matches the SubnetNumber of the entry, then this is the right entry to use,
and it forwards the packet to the next hop router indicated.
• In the example network , router R1 would have the entries shown
 • R1 would AND H2’s address (128.96.34.139) with the subnet mask of the first
entry (255.255.255.128) and compare the result (128.96.34.128) with the
network number for that entry (128.96.34.0).
• Since this is not a match, it proceeds to the next entry.
• This time a match does occur, so R1 delivers the datagram to H2 using
interface 1, which is the interface connected to the same network as H2.
• a default route would usually be included in the table and would be
used if no explicit matches were found.
• In passing that a naive implementation of this algorithm—one
involving repeated ANDing of the destination address with a subnet
mask that may not be different every time, and a linear table search—
would be very inefficient.
datagram forwarding algorithm
D = destination IP address
for each forwarding table entry (SubnetNumber, SubnetMask, NextHop)
D1 = SubnetMask & D
if D1 = SubnetNumber
if NextHop is an interface
deliver datagram directly to destination
else
deliver datagram to NextHop (a router)
• An important consequence of subnetting
is that different parts of the internet see
the world differently.
• From outside our hypothetical campus,
routers see a single network.
• In the example routers outside the campus
see the collection of the eg networks as just
the network 128.96, and they keep one entry
in their forwarding tables to tell them how to
reach it.
• Routers within the campus, need to be able
to route packets to the right subnet.
• Thus, not all parts of the internet see
exactly the same routing information.
Classless Addressing
• Subnetting has a counterpart, sometimes called supernetting, but
more often called Classless Interdomain Routing or CIDR, pronounced
“cider.”
• CIDR takes the subnetting idea to its logical conclusion by essentially
doing away with address classes altogether.
• Why isn’t subnetting alone sufficient?
• subnetting only allows us to split a classful address among multiple subnets,
• CIDR allows us to coalesce several classful addresses into a single “supernet.”
• This further tackles the address space inefficiency, and does so in a
way that keeps the routing system from being overloaded.
• CIDR, tries to balance the desire to minimize the number of routes that a
router needs to know against the need to hand out addresses efficiently.
• To do this, CIDR helps us to aggregate routes.
• it lets us use a single entry in a forwarding table to tell us how to reach a lot of
different networks.
• it does this by breaking the rigid boundaries between address classes.
• To understand how this works, consider our hypothetical organization with
16 class C network numbers.
• Instead of handing out 16 addresses at random, we can hand out a block of
contiguous class C addresses.
• Suppose we assign the class C network numbers from 192.4.16 through 192.4.31.
• Observe that the top 20 bits of all the addresses in this range are the same
(1100000000000100 0001).
• Thus, what we have effectively created is a 20-bit network number—something that
is between a class B network number and a class C number in terms of the number
of hosts that it can support.
• CIDR requires a new type of notation to represent network numbers,
or prefixes because the prefixes can be of any length.
• The convention is to place a /X after the prefix, where X is the prefix
length in bits.
• Eg: the 20-bit prefix for all the networks 192.4.16 through 192.4.31 is
represented as 192.4.16/20.
• if we wanted to represent a single class C network number, which is
24 bits long, we would write it 192.4.16/24.
• If we assign prefixes to the customers in such a way that many different customer
networks connected to the provider network share a common, shorter address
prefix, then we can get even greater aggregation of routes.
• Assume that eight customers served by the provider network have each been
assigned adjacent 24-bit network prefixes.
• Those prefixes all start with the same 21 bits.
• Since all of the customers are reachable through the same provider network, it
can advertise a single route to all of them by just advertising the common 21-bit
prefix they share.
• And it can do this even if not all the 24-bit prefixes have been handed out, as long
as the provider ultimately will have the right to hand out those prefixes to a
customer.
• One way to accomplish that is to assign a portion of address space to the provider
in advance and then to let the network provider assign addresses from that space
to its customers as needed.
IP Forwarding Revisited
• CIDR means that prefixes may be of any length, from 2 to 32 bits.
• Furthermore, it is sometimes possible to have prefixes in the forwarding
table that “overlap,” in the sense that some addresses may match more
than one prefix.
• For example, we might find both 171.69 (a 16-bit prefix) and 171.69.10 (a 24-bit
prefix) in the forwarding table of a single router.
• In this case, a packet destined to 171.69.10.5 clearly matches both prefixes.
• The rule in this case is based on the principle of “longest match”; that is,
the packet matches the longest prefix, which would be 171.69.10 in this
example.
• On the other hand, a packet destined to 171.69.20.5 would match 171.69
and not 171.69.10, and in the absence of any other matching entry in the
routing table 171.69 would be the longest match.
• The task of efficiently finding the longest match between an IP
address and the variable-length prefixes in a forwarding table has
been a fruitful field of research in recent years,.
• The most well-known algorithm uses an approach known as a
PATRICIA tree, which was actually developed well in advance of CIDR.
Problem
• A block of addresses is granted to a small organization. We know that
one of the addresses is 205.16.37.39/28.
• What is the first address in the block?
• Find the last address for the block.
• Find the number of addresses
Solution
• First Address
• The binary representation of the given address is
• 11001101 00010000 00100101 00100111
• If we set 32−28 =4 rightmost bits to 0, we get
• 11001101 00010000 00100101 00100000
• or
205.16.37.32
• The block representation is 205.16.37.32/28
• Another method:
Solution
• Last Address:
• The binary representation of the given address is
• 11001101 00010000 00100101 00100111
• If we set 32 − 28 rightmost bits to 1, we get
• 11001101 00010000 00100101 00101111
• or
• 205.16.37.47
• Another method:
Solution
• Number of Address
• The value of n is 28,
• The number of addresses is 2 32- 28 or 16.

• Another method:
• The number of addresses can be found by complementing the mask, interpreting it as a
decimal number, and adding 1 to it.
Solution
Problem
• An ISP is granted a block of addresses starting with 190.100.0.0/16
(65,536 addresses). The ISP needs to distribute these addresses to
three groups of customers as follows:
a. The first group has 64 customers; each needs 256
addresses.
b. The second group has 128 customers; each needs 128
addresses.
c. The third group has 128 customers; each needs 64
addresses.
• Assume the network addresses of IPs are sequentially assigned.
• Design host addresses and find out how many addresses are still
available after these allocations.
Solution
(a)
• Each customer needs 256 addresses.
• This means that 8 (log2 256) bits are needed to define each host.
• The prefix length is then 32 − 8 = 24.
• The addresses are
Solution
(b)
• Each customer needs 128 addresses.
• This means that 7 (log2 128) bits are needed to define each host.
• The prefix length is then 32 − 7 = 25.
• The addresses are
Solution
(c)
• Each customer needs 64 addresses.
• This means that 6 (log264) bits are needed to each host.
• The prefix length is then 32 − 6 = 26.
• The addresses are
Solution
• Number of granted addresses to the
ISP: 65,536
• Number of allocated addresses by the
ISP: 40,960
• Number of available addresses:
24,576
Solution
Address Translation (ARP)
• IP datagrams contain IP addresses, but the physical interface
hardware on the host or router to which you want to send the
datagram only understands the addressing scheme of that particular
network.
• Thus, we need to translate the IP address to a link-level address that
makes sense on this network (e.g., a 48-bit Ethernet address).
• We can then encapsulate the IP datagram inside a frame that contains
that link-level address and send it either to the ultimate destination
or to a router that promises to forward the datagram toward the
ultimate destination.
• A more general solution would be for each host to maintain a table of address
pairs;
• that is, the table would map IP addresses into physical addresses.
• Each host has to dynamically learn the contents of the table using the network.
• This can be accomplished using the Address Resolution Protocol (ARP).
• The goal of ARP is to enable each host on a network to build up a table of
mappings between IP addresses and link-level addresses.
• Since these mappings may change over time (e.g., because an Ethernet card in a
host breaks and is replaced by a new one with a new address), the entries are
timed out periodically and removed.
• This happens on the order of every 15 minutes.
• The set of mappings currently stored in a host is known as the ARP cache or ARP
table.
• ARP takes advantage of the fact that many link-level network technologies,
such as Ethernet, support broadcast.
• If a host wants to send an IP datagram to a host (or router) that it knows to
be on the same network (i.e., the sending and receiving node have the
same IP network number),
• it first checks for a mapping in the cache.
• If no mapping is found, it needs to invoke the Address Resolution Protocol over the
network.
• It does this by broadcasting an ARP query onto the network.
• This query contains the IP address in question (the target IP address).
• Each host receives the query and checks to see if it matches its IP address.
• If it does match, the host sends a response message that contains its link-layer
address back to the originator of the query.
• The originator adds the information contained in this response to its ARP table.
• The query message includes the IP address and link-layer address of the sending
host.
• Thus, when a host broadcasts a query message,
• each host on the network can learn the sender’s link-level and IP addresses and place that
information in its ARP table.
• Not every host adds this information to its ARP table.
• If the host already has an entry for that host in its table, it “refreshes” this entry;
• that is, it resets the length of time until it discards the entry.
• If that host is the target of the query, then it adds the information about the sender to its
table, even if it did not already have an entry for that host.
• This is because there is a good chance that the source host is about to send it an application-level
message, and it may eventually have to send a response or ACK back to the source;it will need the
source’s physical address to do this.
• If a host is not the target and does not already have an entry for the source in its ARP table,
then it does not add an entry for the source.
• This is because there is no reason to believe that this host will ever need the source’s link-level address;
there is no need to clutter its ARP table with this information.
ARP Packet Format
• HardwareType field,
• which specifies the type of physical network
• Eg: Ethernet - value is 1.
• ProtocolType field,
• which specifies the higher-layer protocol
• Eg: IP - value is 080016,.
• HLen (“hardware” address length)
• specify the length of the link-layer address
• PLen (“protocol” address length) fields,
• specify the length of higher-layer protocol
address,
• Operation field,
• which specifies whether this is a request or a
response.
• ARP request (1) and ARP reply (2).
ARP Packet Format
• SourceHardwareAddr
• This is a variable-length field defining the physical address of the sender.
• For example, for Ethernet this field is 6 bytes long.
• SenderProtocolAddr.
• This is a variable-length field defining the logical (for example, IP) address of the sender.
• For the IP protocol, this field is 4 bytes long.
• TargetHardwareAddr
• This is a variable-length field defining the physical address of the target.
• For example, for Ethernet this field is 6 bytes long.
• For an ARP request message, this field is alI 0 s because the sender does not know the
physical address of the target.
• TargetProtocolAddr.
• This is a variable-length field defining the logical (for example, IP) address of the target.
• For the IPv4 protocol, this field is 4 bytes long.
A host with IP address 130.23.43.20 and physical address B2:34:55:10:22:10 has a
packet to send to another host with IP address 130.23.43.25 and physical address
A4:6E:F4:59:83:AB. The two hosts are on the same Ethernet network. Show the
ARP request and reply packets encapsulated in Ethernet frames
Host Configuration (DHCP)
• It is not possible for the IP address to be configured once into a host
when it is manufactured,
• since that would imply that the manufacturer knew which hosts were going to
end up on which networks,
• it would mean that a host, once connected to one network, could never
move to another.
• For this reason, IP addresses need to be reconfigurable.
• In addition to an IP address, there are some other pieces of information a
host needs to have before it can start sending packets.
• address of a default router—the place to which it can send packets whose
destination address is not on the same network as the sending host.
• Most host operating systems provide a way for a system administrator, or
even a user, to manually configure the IP information needed by a host
• It is a lot of work to configure all the hosts in a large network directly, especially
when you consider that such hosts are not reachable over a network until they are
configured.
• The configuration process is very error prone, since it is necessary to
ensure that every host gets the correct network number and that no two
hosts receive the same IP address.
• For these reasons, automated configuration methods are required.
• The primary method uses a protocol known as the Dynamic Host
Configuration Protocol (DHCP).
• DHCP relies on the existence of a DHCP server that is responsible for providing
configuration information to hosts.
• There is at least one DHCP server for an administrative domain.
• At the simplest level, the DHCP server can function just as a centralized
repository for host configuration information.
• The configuration information for each host could be stored in the DHCP server and
automatically retrieved by each host when it is booted or connected to the network.
• the configuration information for each host is stored in a table that is indexed by some
form of unique client identifier, typically the hardware address (e.g., the Ethernet address
of its network adaptor).
• A more sophisticated use of DHCP saves the network administrator from even
having to assign addresses to individual hosts.
• In this model, the DHCP server maintains a pool of available addresses that it hands out
to hosts on demand.
• This considerably reduces the amount of configuration an administrator must do, since
now it is only necessary to allocate a range of IP addresses (all with the same network
number) to each network.
• Goal of DHCP is to minimize the amount of manual configuration required for a
host to function,
• it would rather defeat the purpose if each host had to be configured with the address of a
DHCP server.
• First problem faced by DHCP is - server discovery.
• To contact a DHCP server, a newly booted or attached host sends a DHCPDISCOVER
message to a special IP address (255.255.255.255) that is an IP broadcast address.
• This means it will be received by all hosts and routers on that network.
• In the simplest case, one of these nodes is the DHCP server for the network.
• The server would then reply to the host that generated the discovery message (all the
other nodes would ignore it).
• It is not really desirable to require one DHCP server on every network, because
this still creates a potentially large number of servers that need to be correctly
and consistently configured.
• Hence, DHCP uses the concept of a relay agent.
• There is at least one relay agent on
each network, and it is configured
with just one piece of information:
• the IP address of the DHCP server.
• When a relay agent receives a
DHCPDISCOVER message, it unicasts
it to the DHCP server and awaits the
response, which it will then send
back to the requesting client.
Format of a DHCP message.

• The message is actually sent

using a protocol called the User
Datagram Protocol (UDP) that
runs over IP
• DHCP is derived from an earlier
protocol called BOOTP,
• Some of the packet fields are
thus not strictly relevant to host
configuration.
• When trying to obtain configuration information,
• the client puts its hardware address (e.g., its Ethernet address) in the chaddr field.
• The DHCP server replies by filling in the yiaddr (“your” IP address) field and sending
it to the client.
• Other information such as the default router to be used by this client can be included
in the options field.
• In the case where DHCP dynamically assigns IP addresses to hosts, it is clear that
hosts cannot keep addresses indefinitely, as this would eventually cause the server to
exhaust its address pool.
• At the same time, a host cannot be depended upon to give back its address, since it
might have crashed, been unplugged from the network, or been turned off.
• Thus, DHCP allows addresses to be leased for some period of time.
• Once the lease expires, the server is free to return that address to its pool.
• A host with a leased address clearly needs to renew the lease periodically if in fact it is still
connected to the network and functioning correctly.
• That DHCP may also introduce some more complexity into network
management, since it makes the binding between physical hosts and IP
addresses much more dynamic.
• This may make the network manager’s job more difficult if, for example, it
becomes necessary to locate a malfunctioning host.
Error Reporting (ICMP)
• The next issue is how the Internet treats errors.
• While IP is perfectly willing to drop datagrams
• IP is always configured with a companion protocol, known as the
Internet Control Message Protocol (ICMP), that defines a collection of
error messages that are sent back to the source host whenever a
router or host is unable to process an IP datagram successfully.
• For example, ICMP defines error messages indicating
• that the destination host is unreachable (perhaps due to a link failure),
• that the reassembly process failed, that the TTL had reached 0,
• that the IP header checksum failed,
• and so on.
• One of the most useful control messages, called an ICMP-Redirect, tells the
source host that there is a better route to the destination.
• ICMP-Redirects are used in the following situation.
• Suppose a host is connected to a network that has two routers attached to it, called R1
and R2, where the host uses R1 as its default router.
• Should R1 ever receive a datagram from the host, where based on its forwarding table it
knows that R2 would have been a better choice for a particular destination address,
• it sends an ICMP-Redirect back to the host, instructing it to use R2 for all future datagrams
addressed to that destination.
• The host then adds this new route to its forwarding table.
• ICMP also provides the basis for two widely used debugging tools,
• ping and traceroute.
• ping uses ICMP echo messages to determine if a node is reachable and alive.
• traceroute uses a slightly non-intuitive technique to determine the set of
routers along the path to a destination, which
Types of Error Reporting Message
Types of Query Message