Transcript QoS Issues in BcN

Network Layer
- there is more than one network
염익준
A Simple Internetwork
Network 1 (Ethernet)
H7
H2
H1
R3
H8
H3
Network 4
(point-to-point)
Network 2 (Ethernet)
R1
R2
H4
Network 3 (FDDI)
H5
H6
2
A Simple Internetwork with
Protocol Layers
H1
H8
TCP
R1
IP
IP
ETH
R2
ETH
R3
IP
FDDI
FDDI
IP
PPP
PPP
TCP
IP
ETH
ETH
3
Datagram Delivery of IP Networks
• Datagram: A type of packet that happens to be sent in a connectionless
manner over a network.
• Each datagram carries enough information to let the network forward the
packet to its correct destination.
• No need for any advance setup.
• Best effort
• Unreliable.
• Run over anything
4
IP Packet Format
0
4
Version
8
HLen
16
TOS
31
Length
Ident
TTL
19
Flags
Protocol
Offset
Checksum
SourceAddr
DestinationAddr
Options (variable)
Pad
(variable)
Data
5
Fragmentation and Reassembly
H1
ETH IP (1400)
R1
R2
FDDI IP (1400)
R3
H8
PPP IP (512)
ETH IP (512)
PPP IP (512)
ETH IP (512)
PPP IP (376)
ETH IP (376)
6
Header Fields Used in IP
Fragmentation
Start of header
Ident = x
(b)
Start of header
Ident = x
(a)
0
1
Offset = 0
Rest of header
Offset = 0
512 data bytes
Rest of header
1400 data bytes
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
7
Addressing
• Ethernet address is flat.
• IP address is hierarchical.
(a)
(b)
(c)
0
1
1
7
24
Network
Host
0
1
0
14
16
Network
Host
21
8
Network
Host
8
Datagram Forwarding in IP
For a router
if (NetworkNum of destination = NetworkNum of one of my interface) then
deliver packet to destination over that interface
else
if (NetworkNum of destination is in my forwarding table) then
deliver packet to NextHop router
else
deliver packet to default router
For a host
if (NetworkNum of destination = my NetworkNum) then
deliver packet to destination directly
else
deliver packet to default router
9
Address Translation
•
•
Mapping an IP address into a physical address
ARP (Address Resolution Protocol)
– To enable each host on a network to build up a table of mappings between IP
address and link-level address.
– The entries are timed out every 15 minutes.
0
8
16
Hardware type = 1
HLen = 48
PLen = 32
31
ProtocolType = 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)
10
Routing
5
Routing protocol
Goal: determine “good” path
(sequence of routers) thru
network from source to dest.
Graph abstraction for routing algorithms:
• graph nodes are routers
• graph edges are physical links
– link cost: delay, $ cost, or
congestion level
2
A
B
3
2
1
D
C
3
1
5
F
1
E
2
• “good” path:
– typically means minimum
cost path
– other def’s possible
11
Routing Algorithm Classification
Global or decentralized information?
Global:
• all routers have complete topology,
link cost info
• “link state” algorithms
Decentralized:
• router knows physically-connected
neighbors, link costs to neighbors
• iterative process of computation,
exchange of info with neighbors
• “distance vector” algorithms
Static or dynamic?
Static:
• routes change slowly over
time
Dynamic:
• routes change more quickly
– periodic update
– in response to link cost
changes
12
Metrics
•
•
The simplest way – counting the number of hops
Other approaches
– Measuring the queue length
– Using delay as metric
• Delay = (departTime – arrivalTime) + Trans.Time + Prop.Time
– Smoothing the variation of the metric over time.
• 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.
13
Subnetting
Network number
Host number
Class B address
111111111111111111111111
00000000
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.0)
Network number
Subnet ID
Subnet mask: 255.255.255.128
Subnet number: 128.96.34.128
128.96.34.130
Host ID
128.96.34.139
128.96.34.129
H2
Subnetted address
R2
H3
128.96.33.1
128.96.33.14
Subnet mask: 255.255.255.0
Subnet number: 128.96.33.0
14
Interdomain Routing
• Autonomous system
• Border router
• BGP (Border Gateway Protocol)
15
Internet inter-AS routing: BGP
• BGP (Border Gateway Protocol): the de facto standard
• Path Vector protocol:
– similar to Distance Vector protocol
– each Border Gateway broadcast to neighbors (peers) entire
path (I.e, sequence of ASs) to destination
– E.g., Gateway X may send its path to dest. Z:
Path (X,Z) = X,Y1,Y2,Y3,…,Z
16
ICMP Features
•
•
•
•
ICMP: Used by IP to send error and control messages
ICMP uses IP to send its messages
ICMP does not report errors on ICMP messages.
ICMP message are not required on datagram checksum
errors. (Some implementations still do)
17
ICMP Message Format
8-bit type of
message
8-bit error code
16-bit checksum
(contents depends on type and code)
18
ICMP: Message Types
Type
0
3
4
5
8
9
10
11
12
13
14
15
16
17
18
description
echo reply (ping)
destination unreachable
source quench
redirect
echo request (ping)
route advertisement
router discovery
TTL expired
bad IP header
timestamp request
timestamp reply
information request
information reply
address mask request
address mask reply
19
ICMP Messages
• Source Quench: Please slow down! I just dropped one of your datagrams.
• Time Exceeded: Time to live field in one of your packets became zero. or
Reassembly timer expired at the destination.
• Fragmentation Required: Datagram was longer than MTU and “No
Fragment bit” was set.
• Address Mask Request/Reply: What is the subnet mask on this net? Replied
by “Address mask agent”
20
Destination Unreachable
code
0
1
2
3
4
5
6
7
8
9
10
11
12
Meaning
network unreachable
host unreachable
protocol unreachable
port unreachable
fragmentation needed but don’t fragment bit set
source route failed
destination network unknown
destination host unknown
source host isolated
destination network administratively prohibited
destination host administratively prohibited
network unreachable for TOS
host unreachable for TOS
21
IP version 6
- IP Next Generation (IPng)
Related RFCs
RFC
Title
Date
1752
The recommendation for the IP Next Generation Protocol
Jan 1995
1809
Using the flow label in IPv6
Jun 1995
1881
IPv6 address allocation management
Dec 1995
1883
IPv6 specification
Dec 1995
1884
IPv6 addressing architecture
Dec 1995
1885
ICMPv6 for the IPv6 specification
Dec 1995
1886
DNS extensions to support IPv6
Dec 1995
1887
An architecture for IPv6 unicast address allocation
Dec 1995
1897
IPv6 testing address allocation
Jan 1996
1924
A compact representation of Ipv6 addresses
Apr 1996
1933
Transition mechanisms for IPv6 hosts and routers
Apr 1996
23
IPng Considerations
•
•
Addressing
– the two level structure of the IP address is convenient but wasteful of address
spaces.
– it is general practice to assign a unique network number to an IP network
whether or not it is actually connected to the Internet.
– networks are proliferating rapidly.
– growth of TCP/IP usage in new areas will result in a rapid growth in the
demand for unique IP addresses.
Performance
– reduced number of fields in the IPv6 packet header
– fixed length of header – extension header
– disabling fragmentation
24
IPng Considerations
• Network service
– should be possible to associate packets with particular services classes
– flow label
• Addressing flexibility
– anycast – delivered to just one of a set of nodes
– multicast – improved scalability by a scope filed
• Security capabilities
– providing authentication and privacy
25
IPv6 Packet Header
0
4
Version
12
TrafficClass
PayloadLen
16
24
31
FlowLabel
NextHeader
HopLimit
SourceAddress
DestinationAddress
Next header/data
26
Priority Field
• One bit for two classes
– congestion controlled traffic
– non-congestion controlled traffic
• Three bits for eight priorities in each class
27
Flow Label
•
•
a flow is a sequence of packets that
– are generated from a single application instance from the source’s point of
view
– share attributes which affect how they are handled from the router’s point of
view
Rules for flow label
– hosts or routers that do not support the flow label field must
• set the field to zero when originating a packet
• pass the filed unchanged when forwarding a packet
• ignore the filed when receiving a packet
– all the packets with the same non-zero flow label must have the same
destination address, source address, priority, hop-by-hop options header
contents and routing header contents.
– the source assigns a flow label to a flow.
28
Addressing
• 128 bit address space
• Address notation: 47cd:1234:4422:ac02:0022:1234:a456:0123
3
m
n
o
p
010
RegistryID
ProviderID
SubscriberID
SubnetID
125– m– n– o– p
InterfaceID
29
Address Prefix Assignment
Prefix
Use
Prefix
Use
0000 0000
Reserved
101
Unassigned
0000 0001
Unassigned
110
Unassigned
0000 001
Reserved for NSAP
1110
Unassigned
0000 010
Reserved for IPX
11110
Unassigned
0000 011
Unassigned
1111 0
Unassigned
0000 1
Unassigned
1111 10
Unassigned
0001
Unassigned
1111 110
Unassigned
001
Unassigned
1111 1110 0
Unassigned
010
Unicast address
1111 1110 10
Link local use
011
Unassigned
1111 1110 11
Site local use
100
Unassigned
1111 1111
Multicast
30
Anycast
•
•
Delivery method:
– unicast: one-to-one
– multicast: one-to-many
– broadcast: one-to-all
– anycast: one-to-one-of-many
Anycast address: an address assigned to multiple hosts
31
Multicast Technology
• Requires group communication
– one-to-many or many-to-many
– dynamic mgmt of group subscription
• Big problem with unicast technology: bandwidth waste with multiple data
flows
32
Why Multicast?
• Typical applications
– Multimedia conference (video, audio, digital whiteboard)
– Resource discovery (e.g., auto-topology)
– War simulation
– Commercial apps (e.g., transactions, news distribution)
– Routing protocols (e.g., both EIGRP and OSPF use multicast to send
updates to neighbors)
– Games (e.g., distributed arcades)
– Physics apps
33
Principles of Multicasting
• Special IP addresses are used to identify multicast
groups
• Hosts notify multicast routers about the multicast
groups to which they (want to) belong
• Multicast groups are managed by the routers using
multicast routing protocols
34
Multicast Addresses
• Multicast packets are identified by Class D IP addresses
• Global range from 224.0.0.0 to 239.255.255.255
– Reserved: 224.0.0.0-224.0.0.255
– Internet-wide addresses: 224.0.1.0-238.255.255.255
– Local addresses: 239.0.0.0-239.255.255.255
• Some special addresses
– 224.0.0.1: all multicast systems on a subnet
– 224.0.0.2: all multicast routers on a subnet
35
Multicast Groups
• IGMP - Internet Group Management Protocol (RFC 1112)
– defines how hosts tell routers which groups they are part of; available
on Unix, PCs, Mac
– routers query directly connected hosts sending an IGMP query to
224.0.0.1 (i.e., all multicast systems)
• when there is more than one multicast router on a LAN, only one
has to send the query
• access lists can be applied to restrict the multicast groups hosts
can receive
– hosts send a single reply per group per LAN
36
Multicast Routing Protocols
•
•
Forwarding decisions: different from unicast protocols
– multicast protocols use the source address instead of the destination address
to make their forwarding decisions
Two main protocols
– DVMRP (Distance Vector Multicast Routing Protocol)
• Distance vector (RIP-like) algorithm
• Static configuration based on tunnels between DVMRP routers (often Sun
workstations)
• Not easily scalable (e.g., max hops < 32)
– PIM (Protocol Independent Multicast)
• Typically installed on routers
• Independent from the unicast routing protocols used by the router
• Scalable (Dense-mode & Sparse-mode)
37
Flooding
• When a router receives a packet that is addressed to a multicast group, it
determines whether this is the first time the router has seen this
particular packet.
• If so, it forwards the packet on all the interfaces except the one on which
it arrived.
• Simple to implement.
• Does not scale well because of the large number of duplicate messages.
38
RPF
•
Reverse Path Forwarding (RPF)
– A router accepts a multicast packet from a source if and only if the packet has
been received over the interface used to send unicast packets to the source
– If the RPF test succeeds, the packet is forwarded to all the interfaces included
in the router’s OIF (Outgoing Interface List)
– If the RPF test fails, the multicast packet is discarded
– A packet should never be re-sent over the RPF interface (to avoid loops)
39
DVMRP



DVMRP constructs source-rooted multicast delivery trees using RPF
algorithm.
Basic operations follow:.
 The first datagram for any (source, group) pair is forwarded across
the entire internetwork.
 The leaf routers transmit prune messages back toward the source if
there are no group members on their directly attached leaf
subnetworks.
 Periodically the prune state times out, and the next datagram for the
(source, group) pair is forwarded across the entire internetworks.
Implements a “graft” operation for quickly establishing a new branch.
 if a router that previously sent a prune message for a (source, group)
pair discovers new group members on a leaf network, it sends a “graft
message” to the group’s previous-hop router.
 When an upstream router receives a “graft” message, it cancels the
previously received prune message. Graft messages may cascade back
towards the source to establish the branch to the multicast tree.
40