Transcript cpt1 - NDSU Computer Science

Computer Networks (CS 778)
• Chapter 1, Foundations
– 1.1 Requirements
• understanding the fundamental network ideas makes
understanding any new protocol easier.
• 1st step is to identify the constraints and requirements
that influence network design.
Perspective
• It is important to understand the expectations one has of
a network depending on your perspective
• Network users: services that their applications need, e.g.,
guarantee that each message it sends will be delivered without
error within a certain amount of time
• Network designers: cost-effective design e.g., network resources
are efficiently utilized and fairly allocated to different users
• Network providers: system that is easy to administer and manage
e.g., faults can be easily isolated and it is easy to account for usage
• This section attempts to distill these different perspectives into a
high-level introduction to the major considerations that drive
network design and, in doing so, identify challenges addressed
2
throughout the book.
1.1.1 Connectivity Building Blocks
• A network must provide connectivity among computers.
– a few select machines (private corporate networks).
• privacy, security concerns
– potentially all computers in world (e.g., the Internet).
• growth concerns (challenge of scalability to arbitrary size)
• Network connectivity occurs at many levels
Link: physical medium directly connecting computers(coax, fiber)
2 computers: point-to-point (pp links) link.
more than 2 computers: multiple-access link.
• limited size (geographically & #nodes) or unlimited (satellite nets)
• Node: a computers (other device?) linked by network.
– indirect connections among sets of cooperating nodes possible
3
– (without a complete set of direct physical connections)
Strategies
Node in a set of nodes can be connected to 1 or more links
– Those attached to  2 run software to forward data from 1 to next
• CIRCUIT SWITCHED networks
(carry bit streams, e.g., telephony networks)
• circuit-switched net establishes dedicated circuit across a sequence of
links, allows source to send a stream of bits.
• PACKET SWITCHED
(store-and-forward, vast majority eg, Internet)
– nodes send discrete data blocks (frames/packet/messages)
– Use "store and forward" strategy, typically:
• Each nodes receives an entire packet,
• stores it in its internal memory,
• forwards complete packet to the next node.
4
Switched Networks
Nodes can be inside the network (switches, routers, gateways) or
outside the network (hosts)
A cloud is used for any type of net (pt-to-pt or multiple access)
A generic internet (connected group of networks) will be in lower case while
the currently operational TCP/IP Internet will be indicated in upper case.
internetworking can be recursed to any number of levels.
A network = 2 or more nodes
connected by links (and a network
is the simples internet
An "internet“ consists of 2 or more networks/internets.
Signified by links interconnecting clouds. The nodes on
these links are called routers or gateways
5
Addressing and Routing
• Internetworking requires "addressing" so communication
can take place.
– Address: identifies a node
– Routing: systematic determination of how to forward a message
to destination node, based on its address (unicast assumed here)
• Types of addresses
– unicast: specific node on a network/internet
– broadcast: all nodes on a network/internet
– multicast: some subset of the nodes on a network/internet
6
Multiplexing (multiple users sharing a system resource concurrently)
• Cost-effective Resource Sharing
• Packet Switching used in computer networks
– In circuit switching, when no data is being sent, "circuit” cannot
be used by another source-destination pair).
– Collection of nodes indirectly connected by nesting of neworks,
node pairs may send messages concurrently across a link.
• Time-Division Multiplexing (TDM)
– divide time into equal quanta, round-robin among flows.
• Frequency-Division Multiplexing (FDM) (transmit flows over different frequencies)
L1
R1
L2
R2
L3
Switch 1
Switch 2
R3
7
Statistical Multiplexing (SM)
(in TDM and FDM, if a flow has nothing to send,
resource is wasted over that time or frequency)
SM Time-division, but on demand, not fixed.
– Reschedule link on a per-packet basis
– Packets of different sources interleaved on link
– Buffer packets that are contending for the link
– Packet queue processed FIFO/priority
– Buffer overflow is called congestion
Physical link shared over time (like TDM) but data transmitted on demand, not
during predetermined time slots. Flow gets to transmit without waiting (if
it's the only flow with data) and it avoids idle time.
How does SM ensure each flow gets a turn? (Upper bound packet size, rather
than arbitrary sized message) - may require "segmentation/reassembly (SAR)
Decision made on packet by packet basis as to which flow sends
if >= 1 flow has data, packets are interleaved (usually FIFO, RoundRobin)
QoS can be requested (max packet delay, etc.)
– Buffers needed when switch gets packets faster than it can send.
8
– When buffers fill up (switch congested) some packets must be dropped.
WDM and DWDM
WDM
Passive bandpass filter
Optical fiber
DWDM (Dense Wave
Division Multiplexing) uses
greater wavelength packing
densities to multiplex more
optical signals over one fiber.
Inter-Process Communication
•
•
One option: application designers build all functionality into applications.
Better option: implement "common services", for application designer’s use.
• Challenge for network designers is to identify the right set of services which hide
•
•
•
complexity without over-constraining designer. Think of logical process channels as
providing communication services: guaranteed message-delivery/correct-ordering &
secure communication (no eavesdropping)
Turn host-to-host connectivity into process-to-process communication.
Fill gap between what apps expect and what underlying technology provides.
Think of the net as more than a delivery system of packets between computers. Think of
it as providing names for sets of applic-processes to communicate over network.
Host
Host
Host
Application
Channel
Application
Host
Host
10
IPC Abstractions
Remote File Access - 1 of the earliest application classes (FTP, NFS, …)
Client (request file be sent) Server (honors request) model is used.
remote reading: client sends small "request"; server sends large "file".
remote writing: client sends large "file"; server sends small "ack".
Another class of applications is video over the net (VOD, video-conferencing)
Two types of channels (IPC entities) might be provided for these applications,
Request/Reply (for files) (guarantee delivery, protect privacy/integrity..)
Message-stream (for video)
(order-preserve, privacy/integrity protecting, supporting multicasting.
11
What Can Go Wrong in the Network?
• Bit-level errors
– single bits, burst errors (several consecutive bits)
– fairly rare (every 10^6 bits on copper; 10^13 on optical)
– there are detection/correction techniques.
• Packet-level errors (e.g., due to congestion and packet dropping?, error?)
– (packet lost/discarded due to congested switch or routing error)
•
•
•
•
Link and node failures
Messages are delayed
Messages are deliver out-of-order
Third parties eavesdrop
Key problem is to fill in the gap between what applications expect and what
underlying technology provides.
12
Bandwidth
• # of bits per second that can be sent.
Latency (delay)
• Time to send message from point A to point B
• Example: 24 ms across this continent on fiber
• Sometimes interested in round-trip time (RTT)
– E.g., in Request/Reply mode.
• Components of latency
Latency = Propagation + Transmit + Queue
Propagation = Distance / SpeedOfLight
Transmit = Size / Bandwidth
– amount of time it takes to transmit a unit of data.
– delay from when 1st bit of data arrives at dest. of link[channel]
until last bit arrives link[channel]
Queue latency (delays in switch and send queues - none for links)
13
Speed of light
2.3 x 108 meters/second in a cable
–
–
–
–
–
3.0 x 108 meters/second in a vacuum
2.0 x 108 meters/second in a fiber
no queuing delays in direct link
bandwidth not relevant if Size = 1 bit
process-to-process latency includes software overhead
software overhead can dominate when Distance is small
Terminology:
• NAME:
Deka Hecto Kilo Mega Giga Tera Peta Exa
• Power of 10: 1
2
3
6
9
12
15 18
• NAME:
Deci Centi Milli Micro Nano Pico Femto Atto
• Power of 10: -1
-2 -3
-6
-9
-12 -15 -18
•
Bandwidth versus Latency (relative importance)
•
•
•
If you’re sending 1 byte, propagation latency dominates
- Big difference between 1 ms latency and 100 ms
- Bandwidth is immaterial (1 Mbps / 1000 Mbps??)
•
•
•
If you’re sending 500 MB, bandwidth dominates
- Big difference: at 1 Mbps (500 sec transmit delay) or 1 Gbps (500 msec transmit delay)
14
- Prop latency is less material (1msec / 100 msec)
Delay x Bandwidth Product
• Delay x Bandwidth Product is often useful
– Example: 100ms x 45Mbps ~= 562KB
– #bits held by pipe at one time. (Bandwidth ~ # bits/meter)
• Whereas, delay ~ length of pipe in meters (or sec, since speed light is constant
– #bits a source must send before 1st bit appears at dest.
Delay
Bandw idth
15
Network Architecture (general blueprint for design/implementation)
• The 2 most common architectures are Open Systems Interconnection (OSI) and
Internet.
• Layering and Protocols
– When a system gets complex, designers use levels of abstraction
• encapsulation that provides an interface for higher layers,
• hides details of how the layer is implemented.
• Challenge: identify abstractions that provides useful services and can be easily
implemented in the underlying system.
• Services provided at higher layers are implemented in terms of services
provided at lower layers.
• E.g., Application Programs layer
– Process-Process layer (AKA channels)
– Host-Host layer (links)
– Underlying Hardware layer
Layering
• Use abstractions to hide complexity
• Abstraction naturally leads to layering
• Can have alternative abstractions at each layer
Types of process-to-process “channels” -->
17
Protocol
• Provides communication service that higher-layer objects
use to exchange messages.
• Protocols have:
– Service-interface used by objects to specify communication
services (e.g., request/reply versus message-stream are protocol
options for process-to-process channels)
– Peer-interface to protocol’s counterpart (peer) on another
machine
(Note, except at the hardware level where peers
communicate directly over a link, peer-to-peer communication is
indirect (each protocol communicates with a peer by passing
messages to some lower level protocol...)
Protocols
• Net architecture bldg blocks – 2 interfaces:
– service interface: operations on this protocol
– peer-to-peer interface: messages exchanged with peers
Host 1
High-level
object
Protocol
Host 2
Service
interface
Peer-to-peer
interface
High-level
object
Protocol
19
Protocol Machinery
•
•
•
•
Protocol Graph (Represents protocol levels in a hierarchical diagram)
The simple example we have used so far has 4 layers:
Application programs
Process-Process layer (transport); AKA, channels with either Request/Reply or
Message Passing protocol
• Host-Host layer (data link)
3 Protocols:
– RRP = Request/Reply Protocol
– MSP = Message Stream Protocol
– HHP = Host-to-host Protocol
E.g., A File application uses RRP/HHP protocol stack.
Host 2
Host 1
File
application
Digital
library
application
RRP
Video
application
MSP
HHP
File
application
Digital
library
application
RRP
Video
application
MSP
HHP
20
Host 1
Host 2
Application
program
Application
program
Data
Data
RRP
RRP
RRP Data
RRP Data
HHP
HHP
• Encapsulation (header/body)
HHP RRP Data
– RRP, for example, treats application message as
string of bytes (or bits).
– It doesn’t care what the message is, just where it goes and with what QoS (this info is
header info).
– Therefore the payload (body) is "encapsulated".
– Encapsulation is repeated at each level (and header info from lower level becomes part
of payload for next level).
21
– Multiplexing may occur at each level also.
Standard Architectures (Standards bodies define layers)
• Open Systems Interconnect(OSI) Architecture
– of the International Standards Organization (ISO)
• So “OSI ISO architecture”
– International Telecom Union (ITU); formerly CCITT
• European
– “X dot” series: X.25, X.400, X.500
• IEEE
22
ISO OSI Architecture
ISO was one of the 1st to formally define a
connectivity standard for computers (OSI)
OSI partitions network functionality into 7 layers
with 1 or more protocols implementing each layer.
Lower 3 implemented on all network nodes
(both switches and hosts)
End host
End host
Application
Application
Presentation
Presentation
Session
Session
Transport
Transport
Network
Network
Network
Network
Data link
Data link
Data link
Data link
Physical: transmits of raw bits over a physical link
Data Link: collects stream of bits into a larger
Physical
Physical
Physical
aggregates (called frames)
One or more nodes within the network
- makes it a "data link" not just a physical link
- Network-adapters (hardware) and device-drivers (software typically involved here.
Physical
Network: routing among nodes (packet switching) implements host-host link using eg, IP-adr
Next 4 layers run on hosts. (Session and Presentation layers are fuzzy and little used!)
Transport: implements process-to-process channel using e.g., ( IP-addr, port-# )
- Provides end-end network-independent message transport services to processes
Session: ties together different streams in same appl (eg, audio, video, data in a teleconf. Appl)
23
Presentation: resolves data format differences (16/32/64 bit int., etc.)
Application: applications (sockets are most common API)
Internet Architecture (4 layer architecture)
•
Network layer : a variety of network protocols (e.g., FDDI, Ehternet...)
•
Internet Protocol layer: (IP) interconnects multiple net technologies into single logical internetwork
•
Transport layer: (TCP=Trans Ctrl Protocol or UDP=User Datagram Protocol)
•
•
– provide alternative logical channels to applications
- TCP provides reliable byte-stream channels
- UDP provides unreliable datagram (=message) channels
• Apps: FTP, TFTP (Trivial File Transfer), Telnet (remote login), SMTP (Simple Mail Transfer
•
________________________________
• Not strict layering:
|______________Application______|
•
|_TCP_|_UDP_|_____
|
•
|_____IP__________|_____________|
•
|______________Network__________|
• IETP requirements for a new protocol: Specifications + at least 1 Implementation
• Final note: ISO protocols are largely ignored today. It is a good reference
architecture, but it is a commercial failure. Why?
• TCP/IP is good, simple, shipped free_with_BSD_since_80s
Internet Architecture (AKA TCP/IP)
• By Internet Engineering Task Force (IETF)
• Hourglass Design
• Evolved from ARPANET (DARPA funded packet net)
• Different from ISO (reconcilable, but not that informative)
• OS offers APIs (syntax for impl of layers – eg, sockets)
FTP
HTTP
NV
TFTP
UDP
TCP
IP
NET1
NET2
…
NETn
25
Reconciling OSI layers with the TCP/IP layers
• Reconciling OSI layers with the TCP/IP layers? (Peterson-Davies
say it’s not worthwihile; Other authors attempt it (Tanenbaum):
•
•
•
•
•
•
•
Application
Presentation
Session
Transport
Network
DataLink
Physical
Application
Transport (TPC/UDP; packet/frame)
Internet (IP)
Network (aka: host-net)
“
TCP/IP Model
In all Reference Models, encapsulate at each layer
ATM Architecture
• While were talking about architecture standards and
reconciling them, there is a 3rd, the ATM architecture.
• ATM is "Connection Oriented”, not connectionless like
ISO and the Internet Architectures.
– ie, there is a "setup phase” (of a virtual end-to-end connection)
– (like the telephone system - "dialing and connecting"), then a
– “transmission phase”
• ATM Layers: Apps, e.g., : VOICE VIDEO DATA
••
|
|
|
-----------------------------------•
•
•
•
•
•
|
ATM Adaptation Layer (ALL)
|
-----------------------------------|
ATM Layer
|
-----------------------------------|
Physical Layer
|
------------------------------------
Physical Layer
• Physical Layer: physical interfaces and framing protocols
• Several Standards for physical connectivity between devices:
–
–
–
–
•
•
•
•
•
•
DS-1 or T1 at 1.54 Mbps
DS-3 or T3 at 45 Mbps
100 Mbps access using FDDI standard
155 Mbps access using Fiber Channel standard on multimode fiber
Synchronous Optical NETwork (SONET) is the predominant physical layer
framing standard for optical transmission (nonUS=SDH-Synch Digital Hierarchy)
(The name sometimes also refers to a physical connection architecture – I.e.,
SONET ring)
LEVEL LINE-RATES
OC-1
51.84 Mbps
OC-3
155.52 Mbps
OC-12 622.08 Mbps
OC-48 2488.32 Mbps
ATM Layer
• Cell structure definition
•
---------------------------------------------------------------•
•
•
•
•
•
•
•
Bits
byte
GFC| VPI
|
VCI
|PT |CLP| HEC | Info Field (Payload)|
---------------------------------------------------------------| 4 |
8
|
16
| 3 | 1 | 8 |
|< - - - - - - 5 - - - - - - - - - - ->|< - - - 48
- - - ->|
GFC = Generic Flow Control. (police traffic across user-network interface)
Two levels of addressing:
– VPI Virtual Path Indetifier - size goes to 12 bits for NNIs
– VCI = Virtual Circuit Identifier - VPI VCI combo identifies the channel
PT = Payload Type (for congestion control)
– Types = user-info, connection-mgmt-info-(signaling), etc
CPL = Cell Loss Priority - indicates if cell can be discarded upon congestion
HEC = Header Error Ctrl ( Cyclic Redundancy Check on cell header –
indicates bit errors in header portion)
ATM Adaptation Layer
• Interface between user application and ATM
• Performs segmentation and reassembly into ATM cells
• also detects and handles out of order or lost cells
Protocol Implementation Issues
• Process Model
– Process-per-protocol model
• Separate process (thread) for each protocol in stack
• Much context switching (each move up/down stack results in a
context switch!)
– Simple to understand
– Process-per-message model
• OS dispatches one process for message
– Message is taken up/down stack by invoked protocol
procedures.
• No context switching
• Much faster
• Harder to understand?