Transcript Internetworking - Witchita State University

Internetworking
Outline
Internetworking by IP
Routing
Global Internet
Multicast
Problem: There is more than one
network
• Two problems that must be addressed:
– Heterogeneity
– Scale
• The scaling problem:
– Routing – How to find an efficient path?
– Addressing – The task of providing suitable identifiers
for all those nodes.
Internetworking
Outline
Best Effort Service Model
Global Addressing Scheme
What is an Internetwork?
• An internetwork is an arbitrary collection of networks
interconnected to provide some sort of host-to-host packet
delivery service.
• A network is either a directly connected or a switched
network that uses one technology. An internetwork is an
interconnected collection of such networks.
• An internetwork is a logical network built out a collection
of physical networks.
• An internetwork is often referred to as a “network of
networks” as shown in Figure 4.1
IP Internet
• Concatenation of Networks
(Figure 4.1)
Network 1 (Ethernet)
H7
H2
H1
R3
H3
Network 4
(point-to-point)
Network 2 (Ethernet)
R1
R2
H4
• Protocol Stack
(Figure 4.2)
Network 3 (FDDI)
H5
H6
H1
H8
TCP
R1
ETH
R2
IP
IP
ETH
R3
IP
FDDI
FDDI
IP
PPP
H8
PPP
TCP
IP
ETH
ETH
What is an Internetwork?
• The Internet Protocol was originally known as the KahnCerf protocol. IP allows a collection of networks to
function as a single logical internetwork as shown in
Figure 4.2.
• It is possible to build an internetwork that does not use IP.
For example, Novell uses IPX (Internetwork Packet
Exchange) protocol, Appletalk uses DDP (Datagram
Delivery Protocol).
Service Model
• Connectionless (datagram-based)
• Best-effort delivery (unreliable service)
–
–
–
–
packets are lost
packets are delivered out of order
duplicate copies of a packet are delivered
packets can be delayed for a long time
• Datagram format
0
4
Version
8
HLen
16
TOS
31
Length
Ident
TTL
19
Flags
Protocol
Offset
Checksum
SourceAddr
DestinationAddr
Options (variable)
Data
Pad
(variable)
IPv4 Header
• IPv4 header format
– Version: the version of IP
– HLen: the length of the header in 32-bit words. The header is 5
words (20 bytes) long when there are no options.
– TOS: type of service
– Length: length of the datagram in bytes. The maximum size of an
IP datagram is 65,535 bytes.
– Identification: All the fragments of a datagram contain the same
identification value.
– Flags: DF (don’t fragment), MF (more fragments)
– Fragment offset: offset from the beginning of the datagram
– TTL: time to live. The default value is 64.
– Protocol: identifies the higher-level protocol to which this IP
packet should be passed. The defined values for TCP is 6 and
UDP is 17.
– Checksum: The checksum is calculated.
– SourceAddr: the source address
– DestinationAddr: the destination address
– Option: more specific control
IPv4 Header
Some of the IP options.
5-54
Fragmentation and Reassembly
• Each network has some maximum transmission unit
(MTU)
• Strategy
–
–
–
–
–
fragment when necessary (MTU < Datagram)
try to avoid fragmentation at source host
re-fragmentation is possible
fragments are self-contained datagrams
use CS-PDU (Convergence Sublayer – Protocol Data Unit) (not
cells) for ATM
– delay reassembly until destination host
– do not recover from lost fragments
Example
Start of header
Ident= x
0
Offset= 0
Rest of header
H1
R1
R2
R3
H8
1400 data bytes
ETH IP (1400)
FDDI IP (1400)
PPP IP (512)
ETH IP (512)
PPP IP (512)
ETH IP (512)
PPP IP (376)
ETH IP (376)
Start of header
Ident= x
1
Offset= 0
Rest of header
512 data bytes
• The router R2 has an MTU of 532 bytes
excluding the PPP header, which leaves 512
bytes for data after the 20-byte IP header.
Start of header
Ident= x
1 Offset= 512
Rest of header
512 data bytes
Start of header
Ident= x
0 Offset= 1024
Rest of header
376 data bytes
Global Addresses
• Properties
– globally unique
– hierarchical: network + host
• Dot Notation
– 10.3.2.4
– 128.96.33.81
– 192.12.69.77
A:
B:
C:
0
7
24
Network
Host
1 0
1 1 0
14
16
Network
Host
21
8
Network
Host
IP Addresses
IP address formats.
IP Addresses
Special IP addresses.
Datagram Forwarding
• Strategy
– every datagram contains destination’s address
– if directly connected to destination network, then forward
to host
– if not directly connected to destination network, then
forward to some router
– forwarding table maps network number into next hop
– each host has a default router
– each router maintains a forwarding table
• Example (R2)
Network Number
1
2
3
4
Next Hop
R3
R1
interface 1
interface 0
Datagram Forwarding
$ netstat -rn
Kernel IP routing table
Destination
Gateway
Genmask
Flags MSS Window irtt Iface
156.26.10.128 0.0.0.0
255.255.255.128 U
40
0
0 eth0
192.168.1.0 0.0.0.0
255.255.255.0 U
40
0
0 eth1
0.0.0.0
156.26.10.129 0.0.0.0
UG 40
0
0 eth0
$ ping kirk
PING kirk.cs.twsu.edu (156.26.10.239): 56 data bytes
Hubs, Repeaters, Bridges
• Repeaters are nodes in the physical layer.
– A repeater is a product that receives, amplifies, and retransmits
signals in both directions.
• In data communications, a hub is a place of convergence
where data arrives from one or more directions and is
forwarded out in one or more other directions.
• Bridges are nodes in the data link layer.
– A bridge is a product that connects a local area network (LAN) to
another local area network that uses the same protocol.
– Forward frames.
Switches, Routers
• Switches are nodes in the data link or the network layer.
– A switch is a network device that selects a path or circuit for
sending a unit of data (packet) to its next destination.
– Forward packets.
• Routers are nodes in the network layer (internetworklevel).
– A router connects a network to one or more other networks that
are usually part of a wide area network (WAN).
– Forward datagrams.
• A brouter is a network bridge and a router combined in a
single product.
Gateways
• Gateways are nodes in the transport layer.
– A gateway is a network point that acts as an entrance to
another network.
– A gateway is often associated with both a router, which
knows where to direct a given packet of data that
arrives at the gateway, and a switch, which furnishes
the actual path in and out of the gateway for a given
packet.
– A computer server acting as a gateway node is often
also acting as a proxy server and a firewall server.
Repeaters, Hubs, Bridges, Switches,
Routers and Gateways
(a) Which device is in which layer.
(b) Frames, packets, and headers.
Repeaters, Hubs, Bridges, Switches,
Routers and Gateways
(a) A hub. (b) A bridge. (c) a switch.
Proxy Server and Firewall
• In an enterprise that uses the Internet, a proxy
server is a server that acts as an intermediary
between a workstation user and the Internet so that
the enterprise can ensure security, administrative
control, and caching service. Routers are internetlevel nodes.
• A firewall is a set of related programs, usually
located at a network gateway server, that protects
the resources of a private network from users from
other networks.
Address Translation
• Map IP addresses into physical addresses and send the
frame to:
– the destination host
– the next hop router that promises to forward it to the destination
• Techniques
– encode physical address in host part of IP address
• For example, 128.96.33.81. 33.81 is the physical address.
• A limited solution
– table-based: (IP address physical address)
• ARP (Address Resolution Protocol)
–
–
–
–
Check for the table of IP to physical address bindings in the cache
Broadcast request if IP address not in the table
Target machine responds with its physical address
Hosts receiving the request update the ARP table if the sender in
in that table. Table entries are discarded if not refreshed to reset
the expiration time.
ARP Details
• Request Format
–
–
–
–
–
HardwareType: type of physical network (e.g., Ethernet)
ProtocolType: type of higher layer protocol (e.g., IP)
HLEN & PLEN: length of physical and protocol addresses
Operation: request or response
Source/Target-Physical/Protocol addresses
• Notes
–
–
–
–
table entries timeout in about 10 minutes
update table with source when you are the target
update table if already have an entry
do not refresh table entries upon reference
ARP Packet Format
0
8
16
Hardware type = 1
HLen = 48
PLen = 32
31
ProtocolT ype = 0x0800
Operation
SourceHardwareAddr (bytes 0 – 3)
SourceHardwareAddr (bytes 4 – 5) SourceProtocolAddr (bytes 0 – 1)
SourceProtocolAddr (bytes 2 – 3) TargetHardwareAddr (bytes 0 – 1)
TargetHardwareAddr (bytes 2 – 5)
TargetProtocolAddr (bytes 0 – 3)
ATMARP
• It is a part of the Classical IP over ATM model.
• One large ATM network is subdivided into several logical
IP subnets (LIS). Each LIS has the same IP network
address.
• An ARP server is to enable nodes on a LIS to resolve IP
address to ATM address without using broadcast.
• LIS is configured with the ATM address of the ARP server,
so that it can establish a VC to the server when booting.
• Two nodes on different subnets have to set up a VC
through the ARP server (router).
Host Configuration (DHCP)
• Dynamic Host Configuration Protocol (DHCP) is a
communications protocol that lets network administrators
manage centrally and automate the assignment of Internet
Protocol (IP) addresses in an organization's network.
• Operation of DHCP
– To contact a DHCP server, a newly booted or attached
host broadcasts a DHCPDISCOVER message.
– When a DHCP relay agent receive the message, it
unicasts it to the DHCP server and relay the response
from the remote DHCP to the booting machine.
Host Configuration (DHCP)
• DHCP is an alternative to another network IP
management protocol, Bootstrap Protocol
(BOOTP). DHCP is a more advanced protocol
• BOOTP (Bootstrap Protocol) is a protocol that lets
a network user be automatically configured
(receive an IP address) and have an operating
system booted (initiated) without user
involvement.
Internet Control Message Protocol
(ICMP)
• The Internet Control Message Protocol (ICMP) 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.
• ICMP defines messages such as
– Echo: ping - send ICMP ECHO_REQUEST packets to network
hosts
– Redirect (from router to source host)
– Destination unreachable (protocol, port, or host)
– TTL exceeded (so datagrams don’t cycle forever)
– Checksum failed
– Reassembly failed
– Cannot fragment
Virtual Private Network
• A VPN (virtual private network) is a way to use a
public telecommunication infrastructure, such as
the Internet, to provide remote offices or
individual users with secure access to their
organization's network.
• A VPN works by using the shared public
infrastructure while maintaining privacy through
security procedures and tunneling protocols.
Tunnels
• Tunneling is the transmission of data intended for use only
within a private, usually corporate network through a
public network in such a way that the routing nodes in the
public network are unaware that the transmission is part of
a private network. A VPN works by using the shared
public infrastructure while maintaining privacy through
security procedures and tunneling protocols.
• Tunneling is generally done by encapsulating the private
network data and protocol information within the public
network transmission units so that the private network
protocol information appears to the public network as data.
Routing
Outline
Algorithms
Scalability
Overview
• Forwarding vs. Routing
– forwarding: to select an output port based on
destination address and routing table
– routing: process by which routing table is built
• Network as a Graph
A
6
1
3
4
C
2
1
B
9
E
F
1
D
• Problem: Find lowest cost path between two nodes
• Factors
– static: topology (shortcomings)
– dynamic: load
Distance Vector
• Each node maintains a set of triples
– (Destination, Cost, NextHop)
• Construct the distance vector
– Initially, each node sets a cost of 1 to its directly connected
neighbors and infinity to all other nodes.
– Every node sends a message to its directly connected neighbors
containing its personal list of distances.
• Exchange updates directly connected neighbors
– periodically (on the order of several seconds)
– whenever its table changes (called triggered update)
• Each update is a list of pairs:
– (Destination, Cost)
Distance Vector
• Update local table if receive a “better” route
– smaller cost
– came from next-hop
• Refresh existing routes; delete if they time out
• When a node or a node fails:
– A node continually tests the link to another node by
sending a control packet
– A node determines that the link or the node is down if it
doesn’t receive the expected periodic routing update
• Updating the routing table when a node or a link
fails could cause the count to infinity problem.
Example
B
C
A
D
E
F
G
Destination Cost Next Hop
A
1
A
C
1
C
D
2
C
E
2
A
F
2
A
G
3
A
Failure Detection and Routing Loop
• Example 1
–
–
–
–
–
–
F detects that link to G has failed
F sets distance to G to infinity and sends update t o A
A sets distance to G to infinity since it uses F to reach G
A receives periodic update from C with 2-hop path to G
A sets distance to G to 3 and sends update to F
F decides it can reach G in 4 hops via A
• Example 2
–
–
–
–
–
–
link from A to E fails
A advertises distance of infinity to E
B and C advertise a distance of 2 to E
B decides it can reach E in 3 hops; advertises this to A
A decides it can read E in 4 hops; advertises this to C
C decides that it can reach E in 5 hops…
Loop-Breaking Heuristics
• Set infinity to 16
• Split horizon
– When a node sends a routing update to its neighbors, it does not
send those routes it learned from each neighbor back to that
neighbor
– For example, if B has the route (E, 2, A) in its table, it knows if
must have learned this route from A, and so whenever B sends a
routing to A, it doesn’t include the route (E, 2).
• Split horizon with poison reverse
– For example, B sends the route (E, infinity) to A.
Routing Information Protocol (RIP)
• RIP (Routing Information Protocol) is a widely-used
protocol for managing router information in IP networks.
– RIP is considered an effective solution for small homogeneous
networks. For larger, more complicated networks, RIP's
transmission of the entire routing table every 30 seconds may put
a heavy amount of extra traffic in the network.
• The major alternative to RIP is the Open Shortest Path
First Protocol (OSPF) .
Link State (OSPF)
• OSPF (Open Shortest Path First) is a router
protocol used within larger networks in
preference to the Routing Information Protocol
(RIP).
• Assume every node knows how to reach its
directly connected neighbors. Then the
complete map of the network can be built.
• Link-state routing protocols rely on two
mechanisms:
– reliable dissemination of link-state information
– the calculation of routers from the sum of all the
accumulated link-state knowledge
Link State
• Strategy
– send to all nodes (not just neighbors)
information about directly connected links
(not entire routing table)
• Link State Packet (LSP)
– ID of the node that created the LSP
– cost of the link to each directly connected
neighbor
– sequence number (SEQNO)
– time-to-live (TTL) for this packet
Link State
• The ID and cost are for the calculation
and the sequence number and TTL
ensures the reliable transmission.
• Reliable flooding
– store most recent LSP from each node
– forward LSP to all nodes but one that sent it
– generate new LSP periodically
• increment SEQNO
– start SEQNO at 0 when reboot
– decrement TTL of each stored LSP
• discard when TTL=0
Route Calculation
• Dijkstra’s shortest path algorithm
• Let
–
–
–
–
–
N denotes set of nodes in the graph
l (i, j) denotes non-negative cost (weight) for edge (i, j)
s denotes this node
M denotes the set of nodes incorporated so far
C(n) denotes cost of the path from s to node n
M = {s}
for each n in N - {s}
C(n) = l(s, n)
while (N != M)
M = M union {w} such that C(w)
is the minimum for all w in (N - M)
for each n in (N - M)
C(n) = MIN(C(n), C (w) + l(w, n ))
Metrics
• Original ARPANET metric
– measures number of packets enqueued on each link
– took neither latency or bandwidth into consideration
• New ARPANET metric
– stamp each incoming packet with its arrival time (AT)
– record departure time (DT)
– when link-level ACK arrives, compute
Delay = (DT - AT) + Transmit + Latency
– if timeout, reset DT to departure time for retransmission
– link cost = average delay over some time period
– The problem:
• Under heavy load, many links would be idle.
• The range of link values was much too large.
Metrics
• Revised ARPANET routing metric
– compressed dynamic range to account for the link type
• Fine Tuning
– The delay measurement was transformed to a link utilization.
– There was a hard limit on how much the metric could change.
• Observation of the Link utilization
– A highly loaded link never shows a cost of more than three times
its cost when idle.
– The most expensive link is only seven times the cost of the least
expensive.
– A high-speed satellite link is more attractive than a low-speed
terrestrial link
– Cost is a function of link utilization only a t moderate to high loads.
Mobile IP
• Dynamic Host Configuration Protocol (DHCP)
enables a newly connected computer to acquire a
temporary IP.
• If a mobile computer is to remain accessible to
client and resource-sharing applications (such as a
share-monitoring service) when moving between
networks, it must retain a single IP number, but IP
routing is subnet-based.
• Mobile IP is a solution to allow the correct routing
through different subnets.
Mobile IP
• When a mobile host is connected outside of its
home base, a home agent (HA) and a foreign
agent (FA) take responsibility of rerouting.
• The HA is responsible for holding up-to-date
knowledge of the mobile host’s current location.
• When a mobile host leaves its home site, it should
inform the HA. During the absence it will behave
as proxy for the absent host.
Mobile IP
• Once the mobile host arrives at a new site, it
informs the FA at that site. The FA allocates a
temporary IP address (care-of address) on the local
subnet and notifies the HA the mobile host’s home
IP address and the care-of address.
• The next figure illustrates the Mobile IP routing
mechanism.
• An IP packet addressed to the mobile host’s home
address is received at the home network and
routed to the HA.
The Mobile IP routing mechanism
Sender
Subsequent IP packets
tunnelled to FA
Mobile host MH
Address of FA
returned to sender
First IP packet
addressed to MH
Internet
Foreign agent FA
Home
agent
First IP packet
tunnelled to FA
Mobile IP
• The HA then encapsulates the IP packet in a
Mobile IP packet and sends it to the FA. The FA
unpacks the packet and deliver it to the mobile
host. This uses the tunnelling technique.
• The HA also send the care-of address of the
mobile host to the original sender.
• If the sender is Mobile IP enabled, the subsequent
communication will directly go the new address. If
it is not, it will ignore the change and continue to
be routed via the HA.
Comments on Mobile IP
• The Mobile IP solution is effective, but hardly
efficient.
• A best solution would be like what is achieved by
the cellular phone network. Is that possible?
• Mobile phones do not change their number as they
move between cells. Instead, they simple notify
the local cellular phone base station of their
presence from time to time.
How to Make Routing Scale
• Two related scaling issues:
– Scalability of routing: minimize the number of network
numbers in routing table
– Address utilization
• Inefficient use of Hierarchical Address Space
– class C with 2 hosts (2/255 = 0.78% efficient)
– class B with 256 hosts (256/65535 = 0.39% efficient)
• Still Too Many Networks
– routing tables do not scale
– route propagation protocols do not scale
Internet Structure
Recent Past
NSFNET backbone
Stanford
ISU
BARRNET
regional
Berkeley
PARC
MidNet
regional
Westnet
regional
UNM
NCAR
UA
UNL
KU
Internet Structure
Today
Large corporation
“Consumer ” ISP
Peering
point
Backbone service provider
“ Consumer” ISP
Large corporation
Small
corporation
“Consumer”ISP
Peering
point
Subnetting
• Add another level to address/routing hierarchy: subnet
• Subnet masks define variable partition of host part
• Subnets visible only within site
Network number
Host number
Class B address
111111111111111111111111
00000000
Subnet mask (255.255.255.0)
Network number
Subnet ID
Subnetted address
Host ID
Subnetting
• A host is configured with both an IP address and a
subnet mask.
• The bitwise AND of the IP address and the subnet
mask defines the subnet number of the host and of
all other hosts on the same subnet.
• For example, 156.26.10.239 (kirk) AND
255.255.255.128 equals 156.26.10.128.
Subnet Example
Subnet mask: 255.255.255.128
Subnet number: 128.96.34.0
128.96.34.15
128.96.34.1
H1
R1
Subnet mask: 255.255.255.128
Subnet number: 128.96.34.128
128.96.34.130
128.96.34.139
128.96.34.129
H2
R2
H3
128.96.33.14
128.96.33.1
Subnet mask: 255.255.255.0
Subnet number: 128.96.33.0
Forwarding table at router R1
Subnet Number
128.96.34.0
128.96.34.128
128.96.33.0
Subnet Mask
255.255.255.128
255.255.255.128
255.255.255.0
Next Hop
interface 0
interface 1
R2
Forwarding Algorithm
D = destination IP address
for each entry (SubnetNum, SubnetMask, NextHop)
D1 = SubnetMask & D
if D1 = SubnetNum
if NextHop is an interface
deliver datagram directly to D
else
deliver datagram to NextHop
• Use a default router if nothing matches
• Not necessary for all 1s in subnet mask to align with a byte
boundary and to be contiguous (255.255.1.0 is possible.)
• Can put multiple subnets on one physical network
• Subnets not visible from the rest of the Internet
Supernetting (CIDR)
• Assign block of contiguous network numbers to
nearby networks
• Called CIDR: Classless Inter-Domain Routing
• Represent blocks with a single pair:
– Restrict block sizes to powers of 2
– Use a bit mask (CIDR mask) to identify block size
– <base address, count> <192.15.32.0, 1024>
– base address/mask 192.15.32.0/255.255.252.0
– base address/bits of network part 192.15.32.0/20
• All routers must understand CIDR addressing
Supernetting (CIDR)
• For example, the CIDR can be used to allocate a batch of
contiguous class C addresses to a subnet requiring more
than 255 addresses.
• The CIDR scheme can also be used to subdivide a Class B
address space for allocation to multiple subnets.
• A CIDR network address looks like this:
– 192.30.250.00/18
– The "192.30.250.00" is the network address itself and the "18"
says that the first 18 bits are the network part of the address,
leaving the last 14 bits for specific host addresses.
CIDR – Classless InterDomain
Routing
A set of IP address assignments.
Route Propagation
• Know a smarter router
–
–
–
–
hosts know local router
local routers know site routers
site routers know core router
core routers know everything
• Autonomous System (AS)
– corresponds to an administrative domain
– examples: University, company, backbone network
– assign each AS a 16-bit number
• Two-level route propagation hierarchy
– interior gateway protocol (each AS selects its own)
– exterior gateway protocol (Internet-wide standard)
Popular Interior (Intradomain) Gateway
Protocols
• RIP: Route Information Protocol
–
–
–
–
developed for XNS
distributed with Unix
distance-vector algorithm
based on hop-count
• OSPF: Open Shortest Path First
–
–
–
–
recent Internet standard
uses link-state algorithm
supports load balancing
supports authentication
EGP: Exterior (Interdomain) Gateway
Protocol
• Overview
– designed for tree-structured Internet
– concerned with reachability, not optimal routes
• Protocol messages
– neighbor acquisition: one router requests that another
be its peer; peers exchange reachability information
– neighbor reachability: one router periodically tests if
the another is still reachable; exchange HELLO/ACK
messages; uses a k-out-of-n rule
– routing updates: peers periodically exchange their
routing tables (distance-vector)
BGP-4: Border Gateway Protocol
• AS Types
– stub AS: has a single connection to one other AS
• carries local traffic only
– multi-homed AS: has connections to more than one AS
• refuses to carry transit traffic
– transit AS: has connections to more than one AS
• carries both transit and local traffic
• Each AS has:
– one or more border routers sitting at the boundary
between the AS and the rest of the Internet.
– At least one node to be assigned as a BGP speaker that
advertises:
• local networks
• other reachable networks (transit AS only)
• gives path information
BGP Example
• Speaker for AS2 advertises reachability to P and Q
– network 128.96, 192.4.153, 192.4.32, and 192.4.3, can be reached
directly from AS2
Customer P
(AS 4)
128.96
192.4.153
Customer Q
(AS 5)
192.4.32
192.4.3
Customer R
(AS 6)
192.12.69
Customer S
(AS 7)
192.4.54
192.4.23
Regional provider A
(AS 2)
Backbone network
(AS 1)
Regional provider B
(AS 3)
• Speaker for backbone advertises
– networks 128.96, 192.4.153, 192.4.32, and 192.4.3 can be reached
along the path (AS1, AS2).
• Speaker can cancel previously advertised paths
IP Version 6
• Features
– 128-bit addresses (classless) (1500/square foot of the earth’s
surface)
– multicast
– real-time service
– authentication and security
– Auto-configuration
– end-to-end fragmentation
– protocol extensions
• Header
– 40-byte “base” header
– extension headers (fixed order, mostly fixed length)
•
•
•
•
fragmentation
source routing
authentication and security
other options
Why IPv6? More Addresses!
• IP address allocation history:
1981 - IPv4 protocol published
1985 ~ 1/16 total space
1990 ~ 1/8 total space
1995 ~ 1/4 total space
2000 ~ 1/2 total space
• this despite increasingly intense conservation efforts
– CIDR (classless inter-domain routing)
– PPP address sharing
– NAT (network address translation)
• theoretical limit of 32-bit space: ~4 billion devices;
practical limit of 32-bit space: ~250 million devices
How Was IPv6 Address Size
Chosen?
• some wanted fixed-length, 64-bit addresses
– easily good for 1012 sites, 1015 nodes, at .0001 allocation efficiency (3
orders of mag. more than IPng requirement)
– minimizes growth of per-packet header overhead
– efficient for software processing
• some wanted variable-length, up to 160 bits
– compatible with OSI NSAP addressing plans
– big enough for auto-configuration using IEEE 802 addresses
– could start with addresses shorter than 64 bits & grow later
• settled on fixed-length, 128-bit addresses
(340,282,366,920,938,463,463,374,607,431,768,211,456 in all!)
Benefits of IPv6 Addresses
IPv4: 32 bits
IPv6: 128 bits
• enough for stable, unique addresses for all devices
– note: stable does not mean permanent!
– allow continued growth of the Internet (for centuries to come)
– restore end-to-end transparency of the Internet
• additional benefits:
– plug-and-play (no need for configuration servers)
– verifiable end-to-end packet integrity (no need for NATs)
– simpler mobility (no need for “foreign agent” function)
Address Complexity
• IPv6 has many different kinds of addresses
– unicast, anycast, multicast, link-local, site-local,
loopback, IPv4-embedded, care-of, manually-assigned,
DHCP-assigned, self-assigned, solicited-node, and
more.
• Most of this complexity is also present in IPv4,
just never written down in one place
– a result of 20 years of protocol evolution
• one simplification: no broadcast addresses in IPv6!
– uses multicast to achieve same effects
IPv6 Addresses
3
m
n
o
p
010
Registry ID
Provider ID
Subscriber ID
Subnet ID
125-mnop
Interface ID
• Classless addressing/routing (similar to CIDR)
• Notation: x:x:x:x:x:x:x:x (x = 16-bit hex number)
– contiguous 0s are compressed: 47CD::A456:0124 =
47CD:0000:0000:0000:0000:0000:A456:0124
– IPv6 compatible IPv4 address: ::128.42.1.87
• Address assignment
– provider-based (can’t change provider easily)
– geographic
Prefix
0000 0000
0000 0001
0000 001
0000 010
0000 011
0000 1
0001
001
010
011
100
101
110
1110
1111 0
1111 10
1111 110
1111 1110 0
1111 1110 10
1111 1110 11
1111 1111
Use
Reserved
Unassigned
Reserved for NSAP Allocation
Reserved for IPX Allocation
Unassigned
Unassigned
Unassigned
Unassigned
Provider-Based Unicast Address IPV4-like
Unassigned
Reserved for Geographic-Based Unicast Addresses
Unassigned
Unassigned
Unassigned
Unassigned
Unassigned
Unassigned
Unassigned
Link Local Use Addresses no global uniqueness
Site Local Use Addresses no global uniqueness
Multicast Addresses
The Main IPv6 Header
The IPv6 fixed header (required).
IP version 6 – Future Evolution
• The next header field provides for future
evolution.
• If non-zero, it specifies an extension header type
in the packet.
• The extension header types include the services
for router information, route definition, fragment
handling, authentication, encryption information,
and destination information.
• Each extension header type has a specific size and
format and is transmitted after the basic header
and before the payload.
Extension Headers
5-69
IPv6 extension headers.
Extension Headers (2)
The hop-by-hop extension header for large datagrams
(jumbograms).
Extension Headers (3)
The extension header for routing.
IPv6 – Multicast and Anycast
• IPv6 describes rules for three types of addressing:
unicast (one host to one other host), anycast (one
host to at least one of multiple hosts), and
multicast (one host to multiple hosts).
• The introduction of an "anycast" address provides
the possibility of sending a message to the nearest
of several possible gateway hosts with the idea
that any one of them can manage the forwarding
of the packet to others.
• Anycast messages can be used to update routing
tables along the line.
IP version 6 – Security
• The advantage of implementing security at the IP
level is that it can be applied without the need for
security-aware implementations of application
programs.
• Security in IPv6 is implemented through the
authentication and encrypted security payload
extension header types , for ensuring data
integrity, and for ensuring privacy.
IPv6 Sockets programming
• New address family: AF_INET6
• New address data type: in6_addr
• New address structure: sockaddr_in6
struct in6_addr {
uint8_t s6_addr[16];
};
sockaddr_in6
struct sockaddr_in6 {
uint8_t
sin6_len;
sa_family_t
sin6_family;
in_port_t
sin6_port;
uint32_t
sin6_flowinfo;
struct in6_addr sin6_addr;
};
Transition from IPv4 to IPv6
• Gradual Transition with IPV4 and IPV6
• Dual Stack - (both supported on some nodes)
• Tunneling
– When v6 passes through v4 network
– Encapsulate v6 inside v4 packet with a v6 router as a
destination
– destination router then sends v6 packet
– lose QoS and other desirable features in v4 segment
Dual Server
• In the future it will be important to create servers
that handle both IPv4 and IPv6.
• The work is handled by the O.S. (which contains
protocol stacks for both v4 and v6):
– automatic creation of IPv6 address from an IPv4 client
(IPv4-mapped IPv6 address).
IPv4
client
IPv6
client
TCP
TCP
IPv4
IPv6
Datalink
Datalink
IPv6
server
IPv4-mapped
IPv6 address
TCP
IPv4
IPv6
Datalink
Multicast
• IPv4
– class D addresses
– demonstrated with Mbone (uses tunneling)
– Place least significant 23 bits of IP number in last 23
bits of ETH/FDDI address
– MSB on in Ethernet indicates multicast
• Integral part of IPv6
– problem is making it scale
Link-State Multicast
• Each host on a LAN periodically announces the groups it
belongs to (IGMP).
• Augment update message (LSP) to include set of groups
that have members on a particular LAN.
• Each router uses Dijkstra's algorithm to compute shortestpath spanning tree for each source/group pair.
• Each router caches tree for currently active source/group
pairs.
source
B
R1
R2
A
Example
R3
R4
C
R5
R6
R7
B
source
R1
B
R2
A
R1
R2
A
R3
R4
C
R5
R3
R4
C
R6
R5
R6
R7
R7
B
R1
R2
A
R3
R4
C
source
R6
R5
R7
Distance-Vector Multicast
Reverse Path Broadcast (RPB)
• Each router already knows that shortest path to destination S
goes through router N.
• When receive multicast packet from S, forward on all outgoing
links (except the one on which the packet arrived), iff packet
arrived from N.
• Eliminate duplicate broadcast packets by only letting “parent”
for LAN (relative to S) forward
– shortest path to S (learn via distance vector)
– smallest address to break ties
Reverse Path Multicast (RPM)
• Goal: Prune networks that have no hosts in group G
• Step 1: Determine of LAN is a leaf with no members in G
– leaf if parent is only router on the LAN
– determine if any hosts are members of G using IGMP
• Step 2: Propagate “no members of G here” information
– augment <Destination, Cost> update sent to neighbors with set of
groups for which this network is interested in receiving multicast
packets.
– only happens with multicast address becomes active.
PIM
RP
RP
Join
R3
R2
R4
R3
R2
R4
Join
R1
R5
R1
R5
(a)
(b)
RP
Join
RP
R3
R2
R4
R3
R2
Join
Join
R1
R5
(c)
RP = Rendezvous point
Shared tree
Source-specific tree for source R1
R1
R5
(d)
R4
RP
G
RP G
G
R3
R2
R4
RP G
G
R1
G
Host
R5