Transcript Document
Networks and
Distributed Systems
Sarah Diesburg
Operating Systems
COP 4610
Technology Trends
Decade Technology $ per
machine
50s
$10M
Sales
volume
100
Users per
machine
1000s
60s
Mainframe
$1M
10K
100s
70s
Mini
computers
PC
$100K
1M
10s
$10K
100M
1
Portables
<$1K
>10B
1/10
80s
90s –
00s
Distributed Systems
Allow physically separate computers to work
together
+ Easier and cheaper to mass-produce simple
computers
Off-the-shelf components
+ A company can incrementally
increase the computing power
Promises of Distributed
Systems
Higher availability
Better reliability
If one machine goes down, use another
A user is able to store data in multiple locations
More security
Each simple component is easier to make secure
Reality of Distributed Systems
Worse availability
Worse reliability
One can lose data if any machine crashes
Worse security
A system may depend on many or all machines
being up
Security is as strong as the weakest component
Coordination is difficult because machines
can only use the network medium
Network Technologies
Definitions
Network: physical connection that allows two
computers to communicate
Packet: a unit of transfer
A sequence of bits carried over the network
Protocol: An agreement between two parties as
to how information is to be transmitted
Broadcast Networks
A broadcast network uses a shared
communication medium
e.g. wireless, Ethernet, cellular phone network
The sender needs to specify the destination in the
packet header
So the receiver knows which packet to receive
If a machine were not the intended destination
Discard the packet
Arbitration
Concerns the way to share a given resource
In Aloha network (1970s)
Packets were sent through radios on Hawaiian
Islands
Aloha Network
Arbitration: blind broadcast, with a checksum at
the end of a packet
Packets might become garbled in the case of
simultaneous transmissions
Aloha Network
Arbitration: blind broadcast, with a checksum at
the end of a packet
Packets might become garbled in the case of
simultaneous transmissions
Aloha Network
Arbitration: blind broadcast, with a checksum at
the end of a packet
Packets might become garbled in the case of
simultaneous transmissions
Blind Broadcast
Receiver:
If a packet is garbled
discard
else
sends an acknowledgement
Sender:
If the acknowledgement does not arrive
resend the packet
Ethernet (introduced in the
early ‘80s)
By Xerox
First practical local area network
Uses wire (as opposed to radio)
Broadcast network
Key advance: a new way for arbitration
Ethernet’s Arbitration
Techniques
Carrier sensing: Ethernet does not send
unless the network is idle
Collision detection: sender checks if
packet is trampled
If so, abort, wait, and retry
Adaptive randomized waiting: a sender
picks a bigger wait time (plus some random
duration) after a collision
The Internet
A generalization of interconnected local area
networks
Uses machines to interconnect various
networks
Routers, gateways, bridges, repeaters
LAN 2
Act like switches
Packets are copied as they
transmitted across different
networks
LAN 1
Routing
Concerns how a packet can reach its
destination
Typically, a packet has to go through multiple
hops before getting to a destination
Each hop is a router, which directs a packet to
the next hop
Routing is achieved through routing tables
Routing Table Updates
Each routing entry contains a cost
1.
2.
3.
<destination, next hop, # hops>
Neighbors periodically exchange routing
table entries
If the neighbor has a cheaper route, use
that one instead
Point-to-Point Networks
Instead of sharing a common network
medium, all nodes in the network can be
connected directly to a router/switch
Point-to-Point Networks
+ Higher link performance (no collisions)
+ Greater aggregate bandwidth than a single
link
Point-to-Point Networks
+ Network capacity can be upgraded
incrementally
+ Lower latency (no arbitration)
Issues in Point-to-Point
Networks
Congestion occurs when everyone sends to
the same output link on a switch
Crossbar
buffers
buffers
Solutions
1. No flow control: Packets get dropped when
the receiving buffer is full
Downloading large files across the Internet can
make many people unhappy
Crossbar
buffers
buffers
Solutions
2.Flow control between switches: a switch
does not send until the buffer space is
available in the next switch
Problem: cross traffic
Crossbar
buffers
buffers
Solutions
3. Per-flow flow control: a separate set of
buffers is allocated for each end-to-end
stream
Problem: fairness
AAAA
BBBB
ABAB
CCCC
ACBC