Transcript Network_PPT

Network Layer
Kuang Chiu Huang
TCM NCKU
Goals of This Lecture
• Through the lecture and in-class
discussion, students are enabled to
describe role and functions of the
network layer, and compare different
routing protocols. In addition,
students can tell the differences
between Diffserv and Intserv.
2
Outline of the Class
• IP address
• Routing protocols
3
Internet Reference Model
Motivation for the Network
Layer
• How do I structure packets?
• How do I get a packet through the
network?
• How do I find a host on a local
subnet?
• How do I deal with the diversity of
subnets?
Getting a Packet Through
the Network
• Need addresses that are globally
unique
• Need network devices that know
about other network devices
• Need a routing algorithm for finding
a path
• Need a mechanism for
accommodating diverse networks
Internet (IP) Addresses
• When an organization connects to
the Internet, it obtains a set of IP
addresses for its computers
• The current addresses consist of 32
bit binary numbers (IPv4)
(theoretically up to 232 = 4.29 billion
addresses)
Internet (IP) Addresses
• Routing each address uniquely would
– require enormous routing tables
– take a lot of time
– Solution: allocate addresses in blocks
IP Addresses
• Block sizes
– Big users (Class A) - 128 available, each
for 16 million hosts
– Meduim users (Class B) - 16,384
available, each for 65,000 hosts
– Small users (Class C) - 2 million
available, each for 256 hosts
IP Addresses
Class A
0
netid
hostid
Class B
10
netid
hostid
Class C
110
netid
hostid
IP Addresses
• Binary numbers are hard to
remember, so use decimal
equivalents
• Divide decimal digit string into four
sets of numbers separated by “dots”
Example
• 136.142.185.57
• Translate into binary
– Decimal to Binary
– Convert decimal to sum of binary exponents
(0-7): 27=128, 26=64, 25=32, 24=16, 23=8,
22=4, 21=2, 20=1
– 136=128+8= 27+ 23
– 142=128+8+4+2= 27+ 23+ 22+ 21
• 10001000 10001110 10111001 00111001
Networks, Subnets &
Addresses
IP Addresses and Domain
Names
Getting Through the Network:
Routing
• Need routing strategies
– Maximum throughput
– Least cost
– Minimum delay
• Implement via routing tables in
nodes
• Routing tables must be computed by
a routing algorithm
Autonomous System
• A set of routers and networks
managed by a single organization
• That exchange information by a
common protocol and
• A path exists between any pair of
nodes
Types of Routing
• Interior router protocol
– Within an AS
– Constructs a detailed model of
interconnectivity within an AS
• Exterior router protocol
– Between ASs
• BGP
• Exchanges reachability information among
ASs
Routing Tables
Routing in the Internet
• Hierarchical and network specific
(instead of host specific) to reduce
the size of the routing tables
• Packet is first delivered to the AS
• The AS sends it to the right network
• The network sends it to the host
Routing Protocols
• Used so that routers can exchange
routing information
• Common routing protocols
– RIP
– OSPF
– BGP
Border Gateway Protocol
• Exterior protocol
• “Path vector” algorithm
• Finds a path through the collection of
autonomous systems
– Neighbor acquisition
– Neighbor reachability
– Network reachability
• Assumes the existence of an interior protocol in
each AS
• Reachability information is shared with
neighboring AS’s
Neighbor Acquisition
• Neighbors are two routers that share the
same network
• Acquisition occurs when the acquisition
procedure results in the two routers
agreeing to share routing information
• Acquisition procedure
– One router sends Open
– Other returns Keepalive if it accepts the
request
Neighbor Reachability
• Needed to maintain acquired
relationships
• Procedure: both routers periodically
send Keepalive messages to each
other
Network Reachability
• Each router maintains a database of
– Networks it can reach
– Preferred route for reaching each
network
• When this changes, and Update is
sent to the neighbor(s)
• This propagates the reachability
information through the network
Open Shortest Path First
(OSPF)
• Interior router protocol
• “Link state” algorithm
• Approach
– Each router maintains descriptions of the state
of the attached links
– Periodically broadcasts updated state
information to all routers it knows about
– OSPF computes routes that minimize “cost”
• Distributed algorithm
• Each router maintains a database of the known
topology
OSPF
Autonomous System
Directed Graph of AS
OSPF– Router 6’s view
Routing Information
Protocol
• General
– Interior protocol
– “Distance vector” protocol: minimize distance
to the destination
• Algorithm does the following
– Share is knowledge about the AS with its
neighbors
– Shares only with its neighbors
– Shares are regular intervals
– Computes shortest distance based on its
knowledge of the network
Getting an IP address
• Static
– Assigned and configured at startup
– Permanently dedicated to a device
• Dynamic
– IP Addresses are “leased” from a pool
– Use Dynamic Host Configuration
Protocol (DHCP)
The Internet Protocol
Internetworking
• Allow independently owned and
administered networks to interconnect
• This was one of the key features of IP in
the 1980s
Local
(access)
network
R
R
Internet
Local
(access)
network
Dissimilar Networks
• Problem:
– Different networks have different
maximum packet sizes
– Eg. Ethernet (1518 bytes max) and
Token Ring (65kbits max)
• How do we enable these to
communicate with each other?
Dissimilar Networks
• Solution
– Fragment the large packets
– Send each packet with its own IP header
IP (version 4) Header
Version
IHL
Type of Service
Total Length
Identification
Flags
Fragment Offset
Time to Live
Protocol
Header Checksum
Source Address
Destination Address
IPv6
• Began as an attempt in 1992 to
address address space exhaustion
• As the Internet was commercialized,
new capabilities were added
• RFC 1752 on the design was issued
in 1995
• Additional RFCs issued subsequently
Improvements over IPv4
• Expanded address space
–
–
–
–
128 bit addresses
6*1023 addresses/m2 of the earth’s surface
Support for dynamic addressing
Support for anycasting
• Improved option mechanisms
– Some not examined by routers
– Allows for expansion of supported features
• Security
• Authentication
• Support for resource allocation
– Enables QoS by labelling flows
– Support for RSVP
IPv6 Header
Challenges with IPv6
• End system conversion Accomplished with recent Linux,
Unix, Windows, Mac operating
systems
• Need cutover of intermediate
systems (eg., routers)
– Difficult coordination problem
– Interim support mechanisms for IPv4
exist
Quality of Service (QoS)
• Increasingly important on the
Internet
• Types of QoS
– Minimum throughput
– Maximum delay
– Bounds on delay variation (jitter)
– Maximum packet loss
Categories of Traffic
• Elastic
– Can adjust to changes in delay and
throughput access
– Examples: File transfer, e-mail, web
access
• Inelastic
– Does not adapt well, if at all, to changes
– Examples: Real-time voice, audio and
video
Supporting QoS in IPv4
• Differentiated services (DiffServ) approach
– Breaks traffic into different classes
– Can only provide statistical performance
guarantees
• Integrated services (IntServ) approach
– Reserves resources on the network
– Can provide absolute guarantees
– Does not scale well
DiffServ Mechanism
• Use Type of Service (TOS) field
• The value of the TOS field reflects
the precedence of the packet
• This precedence results in a “Per-Hop
Behavior” (PHB)
DiffServ Operation
DiffServ Operation
• Classifier: Sorts packets into classes
• Meter
– Measures traffic for conformance to a
user profile
– Users pay varying prices for different
profiles
DiffServ Operation
• Marker
– Mark/re-mark packets as needed, depending
on the results of the meter
– Out of bounds packets are marked as normal
– Remarking may also be necessary at the
boundary of a domain
• Shaper/Dropper
– Drop packets for a given class when it exceeds
the profile specification
DiffServ Operation
• Routers adapt to the ToS field
information by selecting the
appropriate
– Route
– Network service
– Queueing discipline
• Service providers charge based on
the ToS field parameters
IntServ Architecture
RSVP
• Used to establish reservations
• Can be initiated by the sender or
receiver
• Reservations are assigned to flows
from the sender to the receiver
IntServ Operation
• Reservations must be made before a flow
can begin (i.e., admission control)
• Traffic for a flow follows the route along
which the resources are available
• Traffic with similar requirements are
grouped into classes and sent together
• Scheduler sorts the packets into the
appropriate queues
Why Are QoS Not Offered?
• Uncertainty as to the “correct” network
architecture
• Cost of upgrading networks to QoS
capable routers in the face of uncertain
demand
• Coordination between service providers
• Different meanings for different classes
• Lack of trust
Thank you!
Q&A
56