|
|
|
|
A network is a distributed application which
delivers information between processes in a distributed system |
|
Typically provides two classes of service: |
|
reliable stream (connection-oriented): in-order
delivery of information is guaranteed (telephone system model) |
|
unreliable datagram (connectionless):
information is delivered on a best-effort basis (post office model) |
|
|
|
|
|
Receiver: |
|
While ((ch = getchar()) != EOF) putc (ch, tty); |
|
Sender: |
|
While ((ch = getc(tty)) != EOF) putchar(ch); |
|
Issues: |
|
Error control |
|
Framing |
|
Sequencing |
|
Flow control |
|
|
|
|
|
Additional issues: |
|
addressing |
|
multiplexing |
|
routing |
|
congestion control |
|
in-order delivery |
|
|
|
|
|
|
Physical Layer |
|
gets the bits across wire |
|
Data Link Layer |
|
provides interface to physical layer |
|
Network Layer |
|
lets non-adjacent machines communicate |
|
Transport Layer |
|
provides interface to network layer |
|
Session Layer |
|
structures communication |
|
Presentation Layer |
|
abstracts communication |
|
Application Layer |
|
provides end-user services |
|
|
|
|
|
Physical layer standards specify: |
|
Mechanical characteristics: for example, the
physical medium used for communication (copper wire, coaxial cable, optical
fibre, ....), types of connectors, .... |
|
Electrical characteristics: for example, voltage
levels and timing of voltages (for fibre: optical characteristics) |
|
Functional characteristics: for example, pin
assignments |
|
Procedural characteristics: sequence of events
for transmitting data based on functional
characteristics |
|
Example: RS-232 standard for connecting modems
to computers and terminals (latest version is EIA-232-D). |
|
|
|
|
|
|
Often split into two sublayers: |
|
MAC sublayer: deals with sharing a common
channel, as in Ethernet or Token Ring networks, is empty for networks build
with dedicated point-point connections |
|
Logical link control sublayer: sits on top of
MAC sublayer, assumes that adjacent machines communicate over a dedicated
physical or logical link, deals with: |
|
flow control |
|
error control |
|
framing |
|
Example standards: IEEE 802 standards |
|
802.2: Logical link control |
|
802.3: Ethernet |
|
802.5: Token ring |
|
802.8: FDDI and fiber optics advisory group |
|
802.11: Wireless Ethernet |
|
|
|
|
|
|
|
Two general approaches: |
|
scheduling: ready station transmit in orderly
fashion |
|
fixed assignment |
|
FMDA (frequency-division multiple access):
divide bandwidth into N independent subchannels, one for each station |
|
TDM (time-division multiple access): divide time
into discrete intervals, each station is exclusively allocated entire
bandwidth every N-th interval |
|
variations possible to account for different
traffic volume originating from different stations |
|
fixed assignment is efficient for constant and
predictable traffic, mean delay is N times worse than optimal when traffic
is bursty |
|
on-demand assignment: stations that want to
transmit have to wait until they are given permission to access common
channel |
|
Token ring, FDDI: token circulates on ring |
|
DQDB: FCFS queue of send requests, maintained in
a distributed fashion |
|
|
|
|
|
|
random access approach: ready stations broadcast
at will, leads to collisions that have to be resolved somehow |
|
Aloha: explicit acknowledgments of received
packets |
|
Ethernet: similar to Aloha, but tries to
minimize chance of collisions by limiting “broadcast at will”
appropriately, also stops broadcast as soon as collision is detected |
|
Scheduling approaches perform better under a
heavy load |
|
Random access approaches perform better under a
light load |
|
|
|
|
|
ALOHANET packet radio network (developed by the
University of Hawaii in 1971 to provide terminal access to a central
computer) popularized random access protocols. |
|
Two 9600 bps channels: inbound and outbound. The
inbound channel uses a MAC protocol known as (pure) ALOHA: |
|
stations transmit packets whenever they have
data to sent |
|
inbound packets are ACKed. If no ACK is received
during a random timeout interval, the packet is retransmitted |
|
Pure ALOHA is basis for many other MAC
protocols, including Ethernet |
|
Works well under light load, under heavy load,
channel utilization is only 18% |
|
|
|
|
|
Problem: the vulnerable period (length of time
in which a frame can be destroyed) for pure ALOHA is 2t, where t is the
time required to broadcast a frame |
|
Slotted ALOHA: devised by Roberts in 1972 as a
means for doubling channel utilization: |
|
divide time into discrete intervals or slots,
each slot corresponds to a frame. Stations must wait for the beginning of a
slot before broadcasting |
|
Under light load, average waiting time is
increased from zero to one-half the slot length |
|
Under heavy load, the utilization is doubled, to
about 37% (because vulnerability period dropped from 2t to t) |
|
|
|
|
|
|
Improvements in ALOHA: |
|
1-persistent CSMA: listen for idle channel
before broadcasting. Collisions can still occur: |
|
due to propagation delay |
|
two stations may wait for a third to finish and
then start broadcasting simultaneously |
|
nonpersistent CSMA: listen to the channel, if
not busy, start broadcasting. Otherwise, wait for a random interval and try
again. Utilization approaches 1 under heavy load |
|
p-persistent CSMA: listen for an idle channel.
Then with probability <p broadcast frame (otherwise, delay and try
again) |
|
Yet another improvement: abort broadcast as soon
as collision is detected (called CSMA/CD) |
|
frames must be long enough so that all
transmitting stations can detect a collision: the farther stations can be
apart, the larger the minimum packet length |
|
Ethernet: maximum network length is 2.5 km,
minimum frame length is 512 bytes |
|
|
|
|
|
Standardized in IEEE 802.3 |
|
Based on DIX (Dec/Intel/Xerox) 10 Mbps Ethernet
standard, which is based in turn on the Xerox Ethernet developed by Metcalf
and Boggs |
|
Sending station listens while sending. If data
sent differs from data received, assume collision and execute following
protocol: |
|
after i successive collisions, pick a random
number between 0 and 2**i - 1 and skip that number of slots (one slot is
512 bits times long) |
|
interval frozen after 10 collisions (at 1023) |
|
abort sending if 16 attempts failed |
|
|
|
|
|
|
|
Framing: |
|
used for multiplexing and synchronization |
|
can be done by coding violations at physical
layer or bit/char stuffing |
|
bit stuffing: special bit pattern is used to
separate frames: e.g., 01111110. Whenever the transmitter encounters 5
consecutive 1’s in the user’s data, it stuffs (inserts) a 0 bit into the
transmission. When the receiver sees five consecutive 1’s followed by a 0,
it deletes the 0 bit |
|
byte/char stuffing: two special characters are
used. One, say `”`, is used to separate frames, and the other, say ‘/’, is
used as an escape character |
|
if `”` or ‘/’ appear in the user’s data, the
sender transmits, say, ‘/a’ or ‘/b’, respectively |
|
when receiver sees ‘/a’ or ‘/b’, it delivers `”`
or ‘/’ respectively |
|
byte count can be added to protect against
insertions and deletions |
|
|
|
|
|
|
Error Control Schemes: |
|
used to increase reliability. Complete
reliability is not possible, even internal circuits are not completely
reliable |
|
must deal with (at the data link layer)
duplication, distortion, deletion, and insertion of messages |
|
work by increasing redundancy of message in some
well-defined way; consistency of received message is used to assess the
reliability of its information |
|
types of error control schemes: |
|
forward error control: uses error-correcting
codes (such as Reed-Solomon or Hamming codes) to send enough information to
allow receiver to detect and correct errors |
|
feedback error control: uses error-detecting
codes (such as parity bits, CRC) to allow receiver to detect but not to
correct errors. Requires retransmission for correction |
|
feedback error control typically superior to
forward error control (but there are exceptions....) |
|
|
|
|
|
assure that transmitting station does not
overwhelm a receiving station with data |
|
assumptions: data transmitted in frames,
sequential, variable and arbitrary delays |
|
simplest form: stop-and-wait (or stop-and-go) |
|
simple, low overhead |
|
poor utilization of channel, particular for
channels with long propagation delays (such as satellite channels) |
|
|
|
|
|
To achieve better channel utilization, employ
sliding window protocol: |
|
basic idea: allow multiple frames to be in
transit at one time |
|
each frame is assigned a sequence number, using
k bits in frame header (numbering is done module 2k) |
|
sender sends up to N frames without waiting for
ACK |
|
receiver ACKs a frame by sending sequence number
of next frame expected, does not have to ACK every single frame |
|
sender maintains a list of sequence numbers that
is is allowed to send, receiver maintains a list of sequence numbers it is
prepared to accept => sliding window |
|
different protocols differ in how they handle
errors |
|
|
|
|
|
|
|
Primary concern: routing |
|
determines path of packets from source to
destination (so that non-adjacent machines can communicate) |
|
implementations differ as to when path is
selected (static, dynamic, per packet, per circuit), where selection is
done (centralized, distributed), and what information is used (none, local,
adjacent, global) |
|
selection usually based on some least-cost
criterion: each link is assigned a cost, cost of path is sum of costs of
path traversed |
|
Routing algorithms: |
|
Djikstra’s shortest path algorithm |
|
source routing |
|
flooding |
|
random walk |
|
backward learning |
|
|
|
|
|
|
As networks grow in size, routing tables (tell
next destinations on way to receiver) grow |
|
Partial solution: use default entries |
|
Hierarchical routing: |
|
networks organized (recursively) into
subnetworks. Routing problem reduces to two smaller subproblems |
|
routing between subnetworks (with relatively
stable topology) |
|
routing with subnetwork (with dynamically
changing topology) |
|
requires identifiable structure of network
addresses (IP addresses: class A, B, C) |
|
Another problem addressed at network layer:
mobility (mobile-IP) |
|
Congestion control: ensure efficient network
usage, do not overload internal routers or links: |
|
pre-allocate buffers, discard packets, choke
packets, etc.... |
|
|
|
|
|
First layer in which end-to-end functionality
can be implemented. Issues that need to be addressed: |
|
addressing |
|
multiplexing |
|
flow control |
|
error control |
|
connection management |
|
Addresses are typically of the form (station,
port), initiating process obtains address of a target process from: |
|
configuration database |
|
“well-known” address |
|
name server |
|
from a server that starts the target process |
|
|
|
|
|
Connection-oriented services have three phases |
|
connection establishment |
|
data transfer |
|
connection termination |
|
Connection establishment: |
|
allows each end to ensure other exists |
|
allows negotiation of optional parameters |
|
triggers allocation of resources |
|
In unreliable network, connection establishment
non-trivial (2-army problem): |
|
|
|