Transcript Congestion Control Algorithm - Computer Science and Engineering

Congestion Control Algorithm
• Preallocation of Buffers
e.g.,
– Allocate Buffer to Each Virtual Circuit in Each
IMP.
Note: This May be Expensive, and Only Used
Where Low Delay & High Bandwidth are
Essential (e.g., Digitized Voice)
1
Packet Discarding
• Datagram Service: Packet Discard at Will
• Virtual Circuit Service: A Copy of Packet Must be
Kept
Note: If Congestion is to be Avoided by Discarding
Packets, A Rule is Needed
Input
Lines
Output
Lines
Free Buffer
Congestion can be reduced by putting an upper bound
on the number of buffers queued on an output file
2
Packet Discarding (cont.)
(Irland) Discovered Simple Rule of Thumb
(Not Optimal) for Determining Max Q Length, m,
for an IMP With k Buffers
m = k / s, Where s # of Output Lines
3
Internetworking
• Many Different Networks Exist
• Different Networks Have Radically Different
Technology
• Still Desirable to Connect These Networks
Examples of This Follow:
1. LAN-LAN: A Computer Scientist Downloading a File
to Engineering
2. LAN-WAN: A Computer Scientist Sending Mail to a
Distant Physicist
3. WAN-WAN: Two poets Exchanging Sonnets
4. LAN-WAN-LAN: Engineers at Different Universities
Communicating
4
Four Common Types of Relays
• Layer 1: Repeaters Copy Individual Bits Between
Cable Segments
• Layer 2: Bridges Store and Forward Frames
Between LANs
• Layer 3: Gateways Store and Forward Packets
Between Dissimilar Networks
• Layer 4: Protocol Converters Provide Interfacing
in Higher Layers
5
Network interconnection
The boxes marked B are bridges. Those marked G are gateways.
6
Gateways
Operate at The Network Level
Two Styles:
• Connection-Oriented
e.g., Virtual Circuit
• Connectionless-Oriented
e.g., Datagram
7
Internetworking
(A Full Gateway)
Network 1
Net 1 to
Internet
1
Internet
to Net 1
B
U
F
F
E
R
Net 2 to
Internet
Network 2
2
Internet
to Net 2
Machine owned jointly
by both network
8
Internetworking
(Two half-Gateways)
Communication Line
Network 1
Net 1 to
Internet
Net 2 to
Internet
1
Network 2
2
Internet
to Net 1
Internet
to Net 2
Machine
owned by
Network 1
Machine
owned by
Network 2
9
The Network Layer
Source
Host
Destination
Host
Networks
Gateway
(a) Internetworking using concatenated virtual circuits
10
The Network Layer (cont)
Source
Host
Destination
Host
(b) Internetworking using datagrams
11
A datagram moving from
network to network
12
A datagram moving from
network to network (cont.)
Frame 1 DH1 IP TH
DT1
Frame 2 DH2 IP TH
DT2
Frame 3 DH3 IP TH
DT3
DHX: Data link Header
for network X
DTX: Data link Trailer
for network X
IP : Internet Protocol
header
TH : Transport Header
Internet
packet
13
Transparent Fragmentation
Network 2
Network 1
Packet
G1
fragments
a large
packet
G2
reassembles
the
fragment
G3
G4
fragments reassembles
again
again
14
Non-transparent Fragmentation
Packet
G1 fragments
a large packet
The fragments are not
reassembled until the
final destination (a host)
is reached
15
Firewall
•A dedicated gateway machine with special
security precautions on it.
•Out-going/in-coming packets may be blocked.
•IP address and a port number may be used to
block the packets.
The IP Protocol
32 Bits
Version
IHL
Type of Service
DM
F F
Identification
Time to Live
Total Length
Protocol
Fragment Offset
Header Checksum
Source Address
Destination Address
Options (0 or more words)
The IP (Internet Protocol) header
17
The IP Addresses
32 Bits
Range of host address
Class
A 0 Network
B 10
C 110
D 1110
E 11110
1.0.0.0 to
127.255.255.255
Host
Network
128.0.0.0 to
191.255.255.255
Host
Network
Host
Multicast Address
Reserved for Future use
192.0.0.0 to
223.255.255.255
224.0.0.0 to
239.255.255.255
240.0.0.0 to
247.255.255.255
IP address formats
18
The IP Addresses
00000000000000000000000000000000
This host
00
A host on this network
…
00
Host
11111111111111111111111111111111
Network
127
1111
…
1111
(Anything)
Special IP addresses
Broadcast on the
local network
Broadcast on the
distant network
Loopback
The IP Addresses
32 Bits
Subnet
mask
10
Network
Subnet
Host
11111111 11111111 11111100 00000000
One of the ways to subnet a class B network
ARP
Provides a mapping between the two forms of addresses: 32-bit
IP addresses and data link addresses (e.g., 48-bit Ethernet addr.)
32-bit Internet Addr
ARP
RARP
48-bit Ethernet Addr
ARP Request/Reply
V
W
X
Y
Z
V
W
X
Y
Z
V
W
X
Y
Z
ARP (cont’d)
Fund. Concept: The network interface has a hardware address,
and frames exchanged at the hardware level must be addressed to
the correct interface. TCP/IP works with its own addresses (i.e.,
32-bit IP addresses). Knowing a host’s IP addresses does not let
the kernel (i.e., Ethernet driver) must know the hardware address
to send the data.
Summary
Protocol addresses cannot be used when transmitting frames
across physical network hardware, because the hardware does
not understand IP addressing.
So, a frame sent across a given physical network must use hard
ware’s frame format, and all addresses in the frame must
be hardware address
192.31.65.7
192.31.65.5
1
2
E1
E2
CS Ethernet
192.31.65.0
Router has
2IP addresses
Router has
2IP addresses
192.31.60.4
192.31.65.1
192.31.60.7
192.31.63.3
192.31.63.8
F2
F1
3
F3
E3
E4
Campus
FDDI ring
192.31.60.0
E5
4
E6
EE Ethernet
192.31.63.0
Three interconnected class C networks: two Ethernets and an FDDI ring
Ethernet
addresses
Internet Control Protocols
•
•
•
•
ICMP (Internet Control Message Protocol)
ARP (Address Resolution Protocol)
RARP (Reverse Address Resolution Protocol)
BOOTP (Bootstrap Protocol)
26
BOOTP (cont’d)
BOOTP uses UDP and is intended as an alternative to RARP
For bootstrapping a diskless system to find its IP address.
Bootp can also return additional information such as the IP
address of a router, the client’s subnet mask, and the IP address
of a name server.
BOOTP (cont’d)
BOOTP  DHCP (Dynamic Host Configuration Protocol)
Unlike BOOTP, DHCP does not require an administrator to add
an entry for each computer to the database that a server uses.
Instead, DHCP provides a mechanism that allows a computer to
join a new network and obtain an IP address without manual
intervention.
Note: An administrator can configure a DHCP server to have 2
types of addresses: Permanent addresses and a pool of
addresses to be allocated on demand.
Operation of ARP
(2)
FTP
Host
Name
(3)
TCP
establish connection
with IP address
IP
(1) addr
IP
send IP datagram
to IP address
Resolver
(5)ARP
(6)
(8)
(4)
(9)
Ethernet Driver
ARP request (Ethernet broadcast)
Ethernet Driver
Ethernet Driver
(7)
ARP
ARP
IP
TCP
Operation of ARP when user types “ftp hostname”
29
Goals: IPv6
1. Support billions of hosts, even with inefficient address
space allocation
2. Reduce the size of the routing tables
3. Simplify the protocol, to allow routers to process packets
faster
4. Provide better security (authentication and privacy) than
current IP
5. Pay more attention to type of service, particularly for realtime data
IPv6 (cont’d)
6. Aid multicasting by allowing scopes to be specified
7. Make it possible for a host to roam without changing its
address
8. Allow the protocol to evolve in the future
9. Permit the old and new protocols to coexist for years
32 Bits
Version Priority
Payload length
Flow label
Next header
Source address
(16 bytes)
Destination address
(16 bytes)
The IPv6 fixed header (required)
Hop limit
Examples of The Network Layer
7
6
Application protocol (not defined by X.25)
7
Presentation protocol (not defined by X.25)
6
5
Session protocol (not defined by X.25)
5
4
Transport protocol (not defined by X.25)
4
3
2
1
DTE
X.25 layer 3
X.25 layer 2
X.25 layer 1
3
2
1
3
2
1
3
2
1
X.25 layer 3
X.25 layer 2
X.25 layer 1
Internal protocols are not defined by X.25
3
2
1
DTE
The place of X.25 in the protocol hierarchy
33
Two Forms of Connections
• Virtual Calls --- A Connection is Established, Data
Are Transferred, & Then The Connection is
Released
• Permanent Virtual Calls --- Like A Leased Line,
DTE at Either End LAN Just Send Data Whenever
It Wants, Without Any Setup
• Note: The Choice of Circuit # on Outgoing Calls is
Determined by The DTE, and on Incoming Calls
by The DCE, May Lead to A Call Collision.
34
The Three
Phases
of an
X.25
connection
35