Transcript Network Layer

Computer Networks
Network Layer
1
Where are we?
2
Will Layer 2 Networking Suffice?
3
Motivation
Connect various link technologies to form a larger
internetwork
Universal addressing scheme required
General purpose use
Hides underlying technologies from end user
Facilitate communicate between autonomous domains
Able to move packets between any host on the
internetwork
4
Connecting Heterogeneous
Networks
Computer System used
Special purpose
Dedicated
Works with LAN or WAN technologies
Known as
router
gateway
5
Illustration of a Router
Cloud denotes an arbitrary network
One interface per network
6
Important Idea
A router can interconnect networks that use
different technologies, including different
media and media access techniques,
physical addressing schemes or frame
formats.
7
The Internet Concept
8
Key Functions of the Network
Layer
Global Addressing
Fragmentation
Routing
We’ll be primarily concerned with addressing and routing
9
Example Network Layer: Internet
Protocol (IP)
Standardized by IETF as RFC 791
Most popular Layer 3 protocol
Core protocol used on the public Internet
Connectionless protocol
datagrams contain identity of the destination
each datagram sent/handled independently
Of utmost importance for this class!
10
IP Addressing
Provides an abstraction
Independent of hardware (MAC) addressing
Used by
higher layer protocols
Applications
Good IP addressing tutorial: http://www.3com.com/nsc/501302.html
11
IP Address
Virtual
only understood by software
Used for all communication across an
internetwork
32-bit integer
Unique value for each host/interface
12
IP Address Assignment
An IP address does not identify a specific
computer. Instead, each IP address
identifies a connection between a
computer and a network. A computer
with multiple network connections (e.g., a
router) must be assigned one IP address
for each connection.
13
IP Address Details
Divided into two parts
prefix identifies the network
suffix identifies the host/interface
Global authority assigns unique prefix for
the network
Local administrator assigns unique suffix for
the host/interface
14
Class of IP Addresses (Historical)
Initial bits determined the class
The class determines the boundary between prefix and suffix
15
Dotted Decimal Notation
Shorthand for IP addresses
Allows humans to avoid binary
Represents each octet in decimal separated
by dots
NOT the same as names like
www.depaul.edu
16
Examples of Dotted Decimal
Notation
Four decimal values per 32-bit address
Each decimal number
represents eight bits
is between 0 and 255 inclusive
17
Class Hierarchy and Network
Size (Historical)
Maximum size determined by class of address
Class A large
Class B medium
Class C small
18
Addressing Example
19
Illustration of Router Addresses
Address prefix identifies the network
Need one address per router connection
20
Special Addresses
Network Address not used in packets
Loopback addresses never leave the local computer
21
Getting IP Addresses
IANA has global authority for allocation
Regional registries: ARIN, RIPE, APNIC
RFC 1918 defines private address space
NOT globally unique
10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16
End users obtain address space from their
Internet Service Provider (ISP)
22
IP Addressing: Problems with
Classes
Internet growth
Routing table size
Exhaustion of addresses
Administration overhead
Misappropriation of addresses
23
IP Addressing: Solutions
Subnetting
Supernetting
Classless InterDomain Routing (CIDR)
Variable Length Subnet Mask (VLSM)
24
Subnetting
Split the suffix into a local network portion and a smaller
host id portion
25
Subnet Masks
Cannot determine prefix on first few bits
Need a 'bit mask' that specifies prefix/suffix
Dotted decimal notation used, but...
I told you binary was important!
Examples:
Network: 140.192.9.0 Subnet mask: 255.255.255.0
Network: 140.192.9.0 Subnet mask: 255.255.255.128
Network and mask: 140.192.9.0/24
26
More Subnet Examples
63.85.18.5/22 - What is the network?
32.152.6.1/26 - How many hosts possible?
219.52.33.8/20 - What is the directed
broadcast address?
How might you allocate a 10.5.0.0/16 block
for an organization with 4 offices of 500
users each?
27
Supernetting
Combine multiple smaller address classes
into a larger block
Class B was too big
Class C was too small
Combine contiguous Class C addresses
e.g. 199.242.64.0 to 199.242.67.255
28
Classless InterDomain Routing
(CIDR)
Employ supernetting style information in IP
routers
Advertise smaller CIDR blocks
Decreases the routing table size
Advertise 199.242.64.0/22 instead of 199.242.64.0,199.242.65.0,
199.242.66.0 and 199.242.67.0
The CIDR Report: http://www.employees.org/~tbates/cidr-report.html
29
Variable Length Subnet Masks
(VLSM)
Ability to use multiple subnet sizes in a single
autonomous system
Allows more efficient use of addresses
Routers must support subnets masks
e.g. RIPv1 did not support this!
For example:
May use /24 in most places, but may have a small office with only
10 users! May want to use a /28 for that network.
30
IP Packet (datagram) Format
31
IP Datagrams
Can be delayed
Duplicated
Delivered out of order
Lost
Can change routes from packet to packet
Are connectionless
32
Address Resolution Protocol
(ARP)
Resolves IP address to Layer 2 (MAC)
address
Node sends MAC broadcast looking for another node
IP src: 140.192.23.1MAC src: 0x00:80:05:1A:F0
IP dst: 140.192.23.23 MAC dst: 0xFF:FF:FF:FF:FF
Node with that IP dst address replies with its MAC
140.192.23.23 replies with 0x00:60:0A:34:AA:3C
ARP Table: contains records of learned
relationships.
33
Dynamic Host Configuration
Protocol (DHCP)
Standardized in RFC 1531
Allows hosts to obtain IP address
information upon startup from a server
Eliminates cumbersome manual
configuration
Grants IP addresses based on a predefined
"lease" period
34
IP Routing
Performed by routers
Table-driven
Forwarding on a hop-by-hop basis
Destination address used for route
determination
35
Example IP Routing Table
Table (b) is for center router in (a)
36
Routing Table Size
Since each destination in a routing table
corresponds to a network, the number of
entries in a routing table is proportional to
the number of networks in the
internetwork. Caveat: you can use a
"default" route to forward to when route
is unknown or when no route specific
information is available.
37
Routing/Forwarding Overview
Given a datagram
Extract destination address field, D
Look up D in the routing table
Find next hop address, N
Send datagram to N
38
Key Concept
The destination address in a datagram
header always refers to the ultimate
destination. When a router forwards the
datagram to another router, the address
of the next hop does not appear in the
datagram header.
39
Routing/Forwarding Overview
Strip off layer 2 information
Extract destination IP address field
Look up IP address in the routing table
Find next hop address to forward to
Send datagram to the next hop
Add on necessary layer 2 information
40
Routing Protocol Requirements
Efficient routing table size
Efficient routing control messages
Robustness and reliability
prevent loops
avoid black holes
reconvergence time is short
41
Source of Route Table
Information
Manual
Table created by hand
Useful in small networks
Useful if routes never change
Automatic
software creates/updates tables
Needed in large networks
Changes routes when failures occur
42
Compute Shortest/Best Path
Possible metric
geographic distance
economic cost
capacity
43
Algorithms for Computing
Shortest Path
Distance Vector
Exchange routing tables with neighboring
routers
e.g., RIP, RIPv2
Link State
Routers exchange link status information
e.g., OSPF, IS-IS
44
Distance Vector
Routers periodically advertise and learn
about IP networks
Cost of the route is based on hops to the
network (number of routers to pass)
Recalculation occurs when links fail
45
Count to Infinity Problem
What happens when link 1<->5 goes down?
Does 5 think it can get to 1 through 2?
46
Solving the Count to Infinity
Problem
Hold down
Wait for a period of time before switching paths. Advertise route
cost as infinity. Based on timers.
Report the entire path
Guarantees no loops, but expensive.
Split horizon
Do not advertise routes to neighbors if the route was received
from that neighbor. Not foolproof.
47
Other Distance Vector
Improvements
Triggered updates
Advertise changes as soon as you learn of them. May help
convergence time. May create routing instability for flapping
routes.
Poison reverse
Used with split horizon. Report infinity rather than nothing at all.
Diffusing Update ALgorithm (DUAL)
Somewhat like hold down, but routers are alerted of broken paths.
Complex. Not popular.
48
Example Distance Vector
Protocol: RIP
Standardized in RFC 1058 and 2453
An interior gateway protocol (IGP)
Simple
RIPv2 includes subnet mask in updates
Hop count based (> 15 = unreachable)
Widely used in small to medium sized
organizations
49
Link State
Routers distribute link cost and topology
information to all other routers in its area.
All routers have complete information about
the network.
Each router computes its own optimal path
to destinations.
Ensures loop free environments.
50
Link State Procedure
Each router is responsible for meeting its
neighbors and learning their names.
Each router advertises LSPs which contain costs to
its neighbors.
Most current LSPs are stored by all routers.
Each router now computes routes.
51
Dijkstra Algorithm: Databases
Link State Database
contains latest LSPs from all other routers
PATH (permanent) Database
Consists of ID, path cost and forwarding direction
TENT (tentative/temporary) Database
Consists of ID, path cost and forwarding direction
Forwarding Database
Contains ID and forwarding direction
52
Dijkstra Algorithm: Procedure
1. Each router starts with itself as root of the tree
by putting its ID and 0 cost and 0 forwarding
direction in PATH
2. For each node placed in PATH, examine its LSP
and place those neighbors in TENT if not
already in PATH or TENT
3. If TENT is empty, terminate, otherwise find the
ID in TENT with the lowest cost and move it to
PATH
53
Example Link State Protocol:
Open Shortest Path First (OSPF)
Standardized in RFC 2328
An interior gateway protocol (IGP)
Used in medium to large organizations
Supports internal/external routes
Supports TOS based routing, but never
implemented in practice
Two-tier hierarchy for scalability
54
Network Layer: Final Notes
Basic IP requirements on an end host
IP address, mask, gateway, DNS
BOOTP
ICMP
BGP
IPX
AppleTalk
CLNP
55