routers

Report
Brief History of the Internet





ARPA (Advanced Research Project Agency) –
agency of the department of Defense.
In the 1960s funded universities and organizations to
research the development of communication
systems.
Let to the development of ARPANET – an
experimental network that connected computer using
packet switching.
Evolved in the Internet (capital I).
http://www.computerhistory.org/internet_history
Section 19.1 – Logical addressing



IP address is a 32-bit number usually written in the
form w.x.y.z. For example, 143.200.139.98.
There are 128-bit address (IPv6) but we’ll defer
those until later.
nslookup can be used to determine the address.


Also dig, host, named on Linux
Example: nslookup www.uwgb.edu or
nslookup www.google.com




Devices have a physical address (Ethernet) and an IP
address (logical address).
Command ipconfig /all (PC command prompt)
Your IP address is given to you by your ISP and can
change;
Network card determines the physical address.
Won’t change unless you install a new card.





An IP address consists of a Netid and Hostid
Ex: Each campus computer has IP address
143.200.x.y
143.200 is the network number.
x.y determined the device.
Advantage:


Routers outside the campus network need only know in
which direction 143.200 is located rather than tracking
every possible machine.
Once on campus, then the specific machine is
identified.
Address classes for the early Internet


x’s define the Netid
y’s define the Hostid








Class A: 0xxxxxxx.yyyyyyyy.yyyyyyyy.yyyyyyyy
Class B: 10xxxxxx.xxxxxxxx.yyyyyyyy.yyyyyyyy
Class C: 110xxxxx.xxxxxxxx.xxxxxxxx.yyyyyyyy
Class D: 1110……multicast address……………..
Class determined by the first few bits
Multicast (class D) identifies a group of hosts
Unicast identifies one (Class A, B, C)
143.200 is a class B address since 14310 =1000 11112
Table 19.1 Number of blocks and block size in classful IPv4 addressin
NOTE: Block means number of networks (globally)
Block size is the number of hosts (devices) in a network
Classless addressing




Classful addressing too coarse for today’s needs.
Need more flexibility than just class A, B, or C
addresses.
An organization needing 5000 addresses (way too
large for a class C network) would be a class B
network with ~65000 addresses.
Most would go unused.



Internet uses Classless Interdomain Routing (CIDR)
Left most n bits define the Netid, rightmost n-32 bits
define the hostid.
Question: how does a router extract the Netid for
forwarding?
Address mask



Collection of contiguous 1s followed by contiguous 0s
1’s identify bits in the Netid; 0s the hostid
Alternative way to identify the Netid
Table 19.2 Default masks for classful addressing





In general the notation x.y.z.t/n defines an IP address
in which the leftmost n bits specify the Netid.
See ipconfig /all
Subnet mask = 255.255.192.0 =
1111 1111-1111 1111-1100 0000- 0000 0000
Netid = logical AND of the IP address and mask
HostID = logical AND of the IP address and mask
complement


Note that a 16-address block means an address mask
of /28.
Host addresses differ ONLY in the rightmost 4 bits.
Supernetting


Combining smaller physical networks into a single
larger one.
Could combine several class C networks into a
single network.
Example
Class C Network
211.195.8.0
211.195.9.0
211.195.10.0
211.195.11.0
Bit Representation
11010011-11000011-00001000-xxxxxxxx
11010011-11000011-00001001-xxxxxxxx
11010011-11000011-00001010-xxxxxxxx
11010011-11000011-00001011-xxxxxxxx
Address Range
211.195.8.0 to 211.195.8.255
211.195.9.0 to 211.195.9.255
211.195.10.0 to 211.195.10.255
211.195.11.0 to 211.195.11.255
All bits the same

Address mask is 255.255.252.0
(11111111.11111111.11111100.00000000)
Subnetting (reverse of supernetting):




Dividing a network into smaller networks
All hosts in a single subnet share the same subnet
number.
Hosts and NetIDs are addressed consecutively
Number of addresses in a subnet is a power of 2.

Reasons to subnet





Separate different media (e.g. cable from optical fiber)
Separate devices that provide different functions such as
various types of servers.
Security concerns
Better reflect the structure of an organization
Better manage network traffic
example






An organization is given a block of 64 addresses
defined by 17.12.14.0/26.
This means it has 26=64 IP addresses.
It wants 3 subnets of size 16, 16, and 32.
Subnet mask for the larger subnet has twenty seven
1s followed by five 0s.
The smaller ones have a mask with twenty eight 1’s
followed by four 0s
A possible arrangement is 
Figure 19.7 Configuration and addresses in a subnetted network
19.17





Last 8 bits of the IP addresses, Net IDs underlined
0000-0000 thru 0011-1111 (64 addresses)
Subnet 1: 0000-0000 thru 0001-1111 (32 addresses)
Subnet 2: 0010-0000 thru 0010-1111 (16 addresses)
Subnet 3: 0011-0000 thru 0011-1111 (16 addresses)

Example 19.10 on page 561.
NAT (Network address translation) based
router:


If you all buy the same router from Best Buy, chances are
your computers will ALL have the same IP address given to it
by the router.
For example:
A
B
192.168.0.2
internet
24.164.37.109
192.168.0.3
NAT-based
router
C
192.168.0.4
Assigned by ISP

Addresses assigned by router
192.168.x.x is a private address space.
LAN






Book covers a couple of designs; we’ll cover just
their last one
Router has IP address
Each device behind the router has an IP address,
BUT router hides them from the Internet world.
A packet sent from a device to the router contains a
source IP address (w) and port # (x)
Router replaces them both with a fixed IP address
(y) and another port # (z) and forwards packet to the
internet.
Returning responses will be sent to y



Router maintains a table that relates (w, x) and (y, z)
Packet from Internet arrives at router; router looks
up address in the NAT table
It substitutes and forwards the packet.
Advantages:




Hides IP addresses from Internet world
allows IP addresses to be reused
eliminates some tasks associated with managing
subnets (NAT-based router does it) useful for home
networks where consumer does not want to manage
IP addresses
NAT-based router looks like a single device to the
Internet world
Disadvantages:


Purists object to using port numbers to identify
addresses (when they were designed to identify
applications). Some see it as a kludge (pronounced
klooj – nonstandard technique) to solve a problem
that should be solved via IPv6
other
IPv6 – section 19.2 but just the highlights


There are not enough IPv4 addresses
IPv6 uses a 128-bit address
Figure 19.14 IPv6 address in binary and hexadecimal colon notation
19.26
Figure 19.15 Abbreviated IPv6 addresses
19.27

Can specify





Registry: which agency registered the address
(INTERNIC for north America, RIPNIC for Europe,
APNIC for Asia and Pacific countries)
Provider: e.g. your ISP
Subscriber: e.g. a provider’s customer
Subnet: if the subscriber is an organization, it may have
multiple subnets.
Node: the device.
IPv6 also provides





Security
Streaming support
Streamlined packets and more flexible packet
headers for quicker routing
Authentication
It has been in the process of being phased in for
years.
Section 20.1 Internetworking

Not a lot here, mostly setting the context and we’ve
seen this before.
Figure 20.2 Network layer in an internetwork
20.31
Section 20.2 IPv4
Figure 20.4 Position of IPv4 in TCP/IP protocol suite
20.33
Figure 20.5 IPv4 datagram format
20.34
IP Packet (also a datagram) contents



See the book for most details but a couple of relevant
things follow.
Source & destination addresses.
Time-To-Live (TTL) field – decremented by one
each time a router forwards the packet.

When it is 0, it is discarded.

Checksum (on header only) – for error detection.



Needs to be recalculated at each router since the header
can change.
Checksumming the header only is quicker
Higher level protocols will error check the data if needed.

Fragmentation bits.




The IP protocol allows for the possibility that an IP packet
might travel a network that forces an IP packet to divided
into smaller pieces.
You can skip this section.
Priority bits – could allow a router to prioritize the
packets it has in case of congestion . It was never
really used.
Type of service (TOS) bits allow an app to request a
type of handling.
Table 20.2 Default types of service
20.38



That same field also allows differentiated services –
the ability of a router to examine this field and to
determine the quality of service (QoS) expected of
the higher layer. E.g. a file transfer or streaming
real-time data.
Bits to define the protocol above IP using its
services.
Allows the specification of a route to follow or to
record the route taken.


Sections 20.3 and 20.4 deal with IPv6 and the
transition from IPv4 to IPv6.
It’s not difficult reading but I won’t cover it. Be
aware of the issues however.
Section 21.1 Address mapping

Will cover ARP (address resolution protocol)
only – and only a general description of it.
The problem




Sender sends an IP packet across the Internet to a
remote device.
Intermediate routers will route based solely on
destination IP address.
The last router must deliver the IP packet directly to
the device, most likely by embedding the IP packet
into an Ethernet frame and sending it over the
underlying LAN.
How does it determine the physical address?
ARP (Address Resolution Protocol).




Router sends a broadcast (containing the IP address)
to all devices on a LAN.
Device associated with that IP address responds by
sending its MAC address.
Router stores that info and then embeds the IP
packet in a MAC frame and sends it.
The following diagram illustrates but I will not go
into detail with regard to the ARP packet format or
variations of this. It’s accessible to you based on
what we’ve covered.
Figure 21.1 ARP operation
21.44
Chapter 22: Delivery, Forwarding, and Routing
Network Layer: Routing and IP

Problem

A network may be visualized as a graph
Find a route from S (source address) to D (destination
address)

Does it matter which you choose?


An edge may have costs


Cost of a route = sum of edge costs
May just treat all edges the same (cost=1)

Cost of route = number of edges (number of hops)
Delivery: Section 22.1

Direct delivery


Packet goes from one device to a destination located on
the same physical network
Indirect delivery


Packet goes through multiple devices on its way to its
destination. Devices are routers.
Last router is on the same physical network as the
destination. From there, it’s direct delivery.
Forwarding: Section 22.2


A router will: receive a packet and send it to some
other router or to the destination.
Route method:



Either the router or packet contains the complete route
Can be used by some maintenance protocols to test routes,
but not common.
Next Hop method


Router knows ONLY the next router (hop) in a path
Analogies to the US mail



In this case, the next node is along a “cheapest path”.
If all costs are 1, then cheapest is shortest.
Other criteria might be used
Method of forwarding

Host specific



Router has one table entry for every possible destination
Not realistic
Network specific


Router has one table entry for each physical network that
is reachable. It identifies the network number.
One entry for all destinations on the same physical
network.
Figure 22.3 Host-specific versus network-specific method
22.52
Router actions




Get packet and extract IP address
If source route is specified, extract info and route,
otherwise
Determine Netid from the IP packet and search the
routing table
If Netid found and router attached to that network 
determine physical address via ARP. Embed packet
into an Ethernet frame and send. Otherwise


If Netid found and router not attached to that
network  send over link specified in the routing
table
If Netid is not found  send to default router.
Figure 22.6 Configuration for Example 22.1
22.55
Table 22.1 Routing table for router R1 in Figure 22.6
22.56

Skip the rest of 22.3 after the previous
example
Routing

Discuss Dijkstra shortest path
algorithm.[http://www.dgp.toronto.edu/people/JamesStewart/
270/9798s/Laffra/DijkstraApplet.html]
Routing protocols



Autonomous system (AS): collection of networks
and routers under a single administration.
Intradomain routing: routing inside an AS
Interdomain routing: routing between AS’s
Routing Information Protocol (RIP)



An implementation of a distance vector
protocol.
Route with minimum distance
Minimum is shortest if all edge costs are 1. In
that case the cost is the hop count.
Bellman-Ford (also Distance vector). Based on the principle
of optimality
Distance vector algorithm




Routing table contains possible destinations, costs to
get there, and the next node in the route.
Get information from each neighbor’s routing table.
Is it cheaper to get to a node by going through that
neighbor first?
If so, update the entry in the current routing table.

Example:

Each row is a routing table for the node at the left end



Linux traceroute command
DOS tracert command on australia.net, hawaii.net,
alaska.net
See
[http://www.uwgb.edu/serverstatus/netmanagement/
wiscnet.htm]


Distance Vector Routing has some problems when
routers are connected in a loop but there are ways to
deal with them.
That would be for a second class.
Link State Routing





Each router shares its routing table with all others.
Over time, each router learns the network topology
Can apply algorithms such as Dijkstra’s algorithm to
find the cheapest path to any destination.
Neither Link State nor distance vector routing scale
well to LARGE numbers of routers.
Again – they are intradomain routing
Border Gateway Protocol




Based on a path vector routing algorithm
Interdomain routing
Routes among speaker nodes (one that acts for an
entire AS); there is one for each AS
Speaker nodes communicate, indicating accessibility
to nodes within their domain.
Figure 22.30 Initial routing tables in path vector routing
22.69
Figure 22.31 Stabilized tables for three autonomous systems
22.70

similar documents