Figure 4-2
Figure 4-3
Figure 4-4 shows an abstract
model of a network. Each vertex in the graph represents a router and the
"cost" of the link.- correct
- robust (handle failures)
- stable (maintain flow)
Algorithms may be either non-adaptive (static) or adaptive (dynamic).
Non-adaptive routing decisions are made in advance. Adaptive are made
realtime, reflecting current traffic and topology.
This is a shortest-path graph algorithm using Dijkstra's algorithm. It
calculates the shortest path from one node to all others.
The algorithm:
(i) Discover neighbors.
Send a special packet to each neighbor. Each neighbor replies with its address.
(ii) Measure line cost.
Each router must know the delay the each of its neighbors. This can be
accomplished with sending out an ECHO packet to each neighbor which they
return. The router records the delay in receiving the reply.
(iii) Calculate the shortest path for a given starting node using Dijkstra's.
Figure 4-4 - we will go
through an example of this in class.
(2) Distance Vector Routing. (DV)
Each router maintains a table providing the best known distance to each destination and the outgoing line to get there. (Distance vector routing was used in the precursor to the Internet - ARPANET.)
- messages are exchanged between neighbors either periodically (i.e. very 5 minutes) or only when the cost reaching a node changes. Once a host receives updated routing information from its neighbors, it may update its internal routing table.
Consider the following figure:
<< We will work on an in-class distance vector problem >>
Both Link State and Distance Vector algorithms are used in the contemporary Internet
Hierarchial Routing
In practice it may be too much for each router to know about every other
router in the network.
The solution is to route hierarchically, organizing routers into regions
- or autonomous systems (AS). Within each AS, all routers may use
the same routing algorithm (either LS or DV). We will call these intra-autonomous
system routing protocol.
Of course systems may wish to route to other systems in different ASes.
This requires an inter-autonomous system routing protocol. Gateway
routers connect an AS to other ASes.
Figure 4-12
The Internet Protocol (IP)
Figure 4-13
Connection-less and unreliable.
Two types of addressing (IPv4 and IPv6)
- Generally in the form A.B.C.D (i.e. 146.86.5.20) where A.B.C.D are one byte each.
- we usually think in terms of mycompany.com, but this is matched to an actual IP address.
- Each interface on a host or a router must have an IP address.
- This is known as classful addressing.
Consider the following network:
Figure 4-14
The router had three interfaces and therefore three IP addresses (223.1.1.4, 223.1.2.9, and 223.1.3.27)
Furthermore, we have broken this up into three separate networks:
223.1.1.x
223.1.2.x
223.1.3.x
where x is unique for each host on that network.
Because the left-most 24 bits are being used for the network, we would
call a network 223.1.1.0/24, 223.1.2.0/24, 223.1.3.0/24
Figure 4-15
Each "segment" could be its own Ethernet segment. (More on Ethernet in
later chapters.)
However, we can also create smaller networks of just interfaces:
Figure 4-16
Address Formats
Figure 4-17
This is known as classful addressing.
| Class A | 27 = 128 Networks 224 = 16M Hosts |
| Class B | 214 = 16,384 Networks 216 = 65K Hosts |
| Class C | 221 = 2M Networks 28 = 256 Hosts |
Problems with Classful IPv4 Addressing
A site with a class C address could have only 256 hosts. Any number of hosts > 256 would require the site get a second address. Therefore, the restrictions on the number of networks and hosts for a given class are formally no longer part of IP.
Classless Interdomain Routing (CIDR)
Another alternative is CIDR which does away with the notion of classful addressing.
- prounounced "cider"
- allows the network part of an IP address to be any number of bits rather than 8, 16, or 24.
- A CIDR address has the form
A.B.C.D/x
where x is the number of leading bits pertaining to the network address.
An Example:
Assume an organization requires 1000 IP addresses. It has a few options, it could obtain a class B address, however there are only 16K of these available. Alternatively, it could obtain a block of 4 class C addresses. Assume this block is 200.10.4.0 through 200.10.7.0. The first 22 bits of these addresses are the same and they serve as the number for the network (which in this case is 200.10.4.0). A network mask of 255.255.252.0 masks the first 22 bits of the address.
In this situation, CIDR has combined several class C addresses into a single network.
The CIDR address of this network is 200.10.4.0/22
CIDR is also used by ISPs when they assign a range of IP addresses to
small businesses. For example, a small company could be assigned the CIDR
address 200.25.17.128/26. This allows the company to have 
hosts.
Addressing/Routing/Forwarding
The important fields of an IP datagram
Figure 4-20
Routers are primarily concerned with IP addresses.
Consider the network shown in
Figure 4-21.
Consider the following:
(1) Host A wants to send a packet to host B. (Figure
4-21)
(2) Host A wants to send a packet to host E. (Figure
4-21 and Figure 4-22)
How does this work with CIDR?What if a CIDR-ized network with 4 class C addresses 200.10.4.0 through 200.10.7.0 were attached to a router. The router must know all networks it services. However, if we mask these addresses with the netmask 255.255.252.0, it translates to 200.10.4.0 for the entire network. If an external router wants to forward a packet to 200.10.5.33 (a host on this network), it masks 200.10.5.33 with 255.255.252.0 resulting in 200.10.4.0 and it forwards the datagram along to that address. |
The IPv4 Header
Figure 4-23
Some Fields:
DF = Don't Fragment
MF = More Fragments to Follow
Each network imposes limits on the size of the packets that may pass through it (we will call them big-packet and small-packet networks.)
A problem occurs when a large packet has to pass through a small-packet network.
A solution is to fragment the packets.
Figure 4-24
This is what the identification and fragment fields in the
IP header are used for.
ICMP is used by hosts, routers, and gateways to communicate network information
to each other.
Figure 4-25 shows some
of the ICMP message types.
|
(adapted from Computer Networking - A Top Down Approach Featuring the Internet) Traceroute uses ICMP. To determine the names and addresses of the routers between the source and destination, traceroute sends the destination a series of IP datagrams. The first datagram had a TTL of 1, the second 2, the third 3, and so forth. The source also starts a timer for each datagram. When the Nth datagram arrives at the Nth router, because the TTL expires, the router drops the packet and sends an ICMP warning message to the source. Included in this ICMP warning message is the IP address and name of the router. Using the timer, traceroute is able to determine the round-trip time to the router. Gnutella - the popular peer-to-peer file sharing protocol also uses ICMP. We will look at Gnutella later in this class. |
IP addresses may be obtained either statically or dynamically.
Static - the IP address is assigned to the host.
The contents of /etc/hosts:
127.0.0.1 localhost
192.168.1.15 alta.westminstercollege.edu alta
146.86.5.15 alta.westminstercollege.edu alta
192.168.1.101 carbon.westminstercollege.edu carbon
192.168.1.110 silver.westminstercollege.edu silver
192.168.1.103 silicon.westminstercollege.edu silicon
192.168.1.112 radium.westmintercollege.edu radium
192.168.1.104 sulfur.westminstercollege.edu sulfur
192.168.1.105 argon.westminstercollege.edu argon
192.168.1.106 barium.westminstercollege.edu barium
192.168.1.107 cobolt.westminstercollege.edu cobolt
192.168.1.108 copper.westminstercollege.edu copper
192.168.1.109 kripton.westminstercollege.edu kripton
Dynamic - This is assigned by a server using eitehr DHCP or NAT.
(1) DHCP (Dynamic Host Configuration Protocol)
Dynamically assigns hosts IP addresses. On Mac OS X
Figure 4-26 as well.
DHCP works in 4 steps:
(1) DHCP server discovery.
(2) DHCP server offer.
(3) DHCP request
(4) DHCP ACK
Figure 4-27
(2) NAT (Network Address Translation)
This is popular on small home networks, especially with broadband or DSL.
NAT allows a home network to assign addresses in the range of 10.0.0.0 to 10.0.0.255 to computers attached to the network. Most external cable and DSL modems support NAT.
Figure 4-28
An autonomous system is made up of one or more areas. An area
could be one or more subnets of an IP address.
All routing within an autonomous system is known as interior
routing.
Within an autonomous system, TCP/IP uses Open Shortest Path First (OSPF) and Routing Information Protocol (RIP)
RIP
A distance
vector algorithm that counts the number of hops as a metric.
Figure 4-29 illustrates an AS
Figure 4-30 shows the routing table for router D.
Routing updates are exchanged every 30 seconds. Consider if router A set
a router update to D
Figure 4-31
Router D's new table would be
Figure 4-32
Logically, RIP resides as an an application-level process that uses routing
tables at the network layer
Figure 4-33
Routing tables on a UNIX Workstation
Internet:
Destination Gateway
Flags Refs Use Netif
Expire
default
146.86.47.9 UGSc
9 47 en0
## this is the default router
localhost
localhost UH
9 3912 lo0
146.86.47/24 link#4
UCS 1
0 en0
146.86.47.9 0:0:c:7:ac:2f
UHLW 10
0 en0 1180
146.86.47.84 localhost
UHS 0
1 lo0
146.86.47.11 0:60:b0:71:a4:d6
UHLW 0
3 en0 1200 ## this is the
printer
169.254
link#4
UCS 0
0 en0
An Example
Using the following figure:
If node A wishes to deliver a packet to node F (223.1.2.2), it will consult its routing table and determine that it must go through the router. At the MAC layer it will address the packet to the router, however at the IP layer it will indicate that the destination address is 223.1.2.2. The router will receive this packet and forward it to network 223.1.2.0/24 destined for host 223.1.2.2. (Again, the router will have to get the MAC address for the destination host.)
OSPF is open, meaning that routers within an AS are free to use it. There
are also several proprietary internal routing algorithms as well.
Enhanced Internal Gateway Routing Protocol (EIGRP)
EIGRP is a proprietary routing protocol used in Cisco routers. It is a variation of distance vector routing.The Internet generally uses Border Gateway Protocol (BGP) between routers connecting autonomous systems.
Figure 4-36
BGP
BGP is essentially a distance vector protocol, however it is also considered
a path vector protocol as BGP peers exchange detailed path information
as opposed to just the cost of a path.
BGP also routes to just networks rather than specific hosts. Why
Figure 4-44 illustrates
the IPv4 header.IPv6 Addresses
IPv6 provides 16-byte addresses resulting in 2128 = 1.6043703E32 unique addresses!
Addresses are divided up into 8 groups where each group contains 4 hex
digits:
ae1f:2ef7:ab2h: . . . :9b1c
To be backwards compatible with Ipv4, old IPv4 addresses use the form
::146.86.5.20
Some fields of interest:
- Priority - (actually part of the traffic class) allows the sender to distinguish between regular data and real-time traffic (i.e. streaming audio or video). Regular data can also be prioritized, i.e. telnet packets will have a higher priority than ftp packets.
- Flow Label - IPv6 has an elusive definition of flow. It may mean streaming stock quotes to certain customers determines a flow whereas streaming audio or MP3 files are not. The flow label and priority fields work together.
Note that IPv6 does NOT have a fragmentation or checksum field. IPv6 does
not allow a small network to fragment a packet. Instead, it drops the packet
and sends an ICMP message back to the sender telling the sender to reduce
the size of the packet. There is no checksum as the designers of IPv6 decided
that the data link (i.e. Ethernet) and transport layers (i.e. TCP or UDP)
also perform a checksum.
|
Java 1.4 now allows support for both IPv4 and IPv6 addresses. The following program determines if your system is running an IPv4 pr IPv6 address [ IP.java ] |