Transcript Network Protocols

Network Protocols
Sarah Diesburg
Operating Systems
CS 3430
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
Networking:
Physical Reality vs. Abstraction
Physical reality: packets
Abstraction:
messages
Limited size
Arbitrary size
Unordered
Ordered
Unreliable
Reliable
Machine-to-machine
Process-to-process
Only on local area network Routed anywhere
Asynchronous
Synchronous
Insecure
Secure
Arbitrary-Size Messages

Can be built on top of limited-size ones


By splitting a message into fix-sized packets
Checksum can be computed on each
fragment or the whole message
Internet Protocol (IP)

Provides unreliable, unordered, machine-tomachine transmission of arbitrary-size
messages
Process-to-Process Communications


Built on top of machine-to-machine
communications through the use of port
addresses
Each message contains the destination port
to talk to the correct process
Unreliable Data Protocol (UDP)


Provides unreliable, unordered, user-to-user
communication
Built on the top of IP
Ordered Messages


Built on top of unordered ones
Use sequence numbers to indicate the
order of arrival



Specific to a connection
If packet 3 arrives before packet 2, wait for
packet 2.
Always deliver packets in order, to user
applications
Reliable Message Delivery

Built on top of unreliable delivery

Problem: Network infrastructure can garble
messages

Packets can be dropped if network buffers are full
Solution




Checksum each message
At a receiver, discard messages with
mismatching checksums
A receiver acknowledges if a packet is
received properly
A sender resends the same message after
not hearing the acknowledgment for some
time (a timeout period)
A Minor Problem


A sender may send twice, if the first
acknowledge is lost
The receiver needs to discard duplicate
packets
Implications


A sender needs to buffer messages that are
not yet acknowledged
The receiver must track messages that could
be duplicates
Transmission Control Protocol (TCP)

Provides a reliable byte stream between two
processes on different machines over the
Internet
sequence number: 1
checksum:
fa73cd10
Transmission Control Protocol

Fragments the byte stream into packets and
hands them to IP
TCP Message Categories

Sender




Sent and acknowledged
Sent and not acknowledged
Not yet sent
Receiver



Forwarded to application
Received and buffered
Not yet received
More on the Sequence Number

Need a way to recycle sequence numbers

Each TCP packet has a time-to-live field

If the packet is not delivered in X seconds



The packet is dropped
Sequence numbers can be reused
An epoch number used to identify which set of
sequence numbers is being used


Incremented at each boot
Stored on disk
Congestion

Implications of timeout period at a sender



Too long  unnecessary waiting
Too short  a message is transmitted when an
acknowledgement is in transit
Network congestion  delayed
acknowledgement  timeout  data
retransmission  more congestion
TCP Solution

Slow start: TCP starts by sending a small
amount of data


If no timeout, more data is sent
If timeout, TCP reduces the amount of data being
sent
Distributed Transaction


Multiple machines agree to do something
atomically, but not necessarily at exactly the
same time
Mechanism: two-phase commit
Two-Phase Commit
Account X
Account Y
Phase 1: ask if each can commit
1. Begin transaction
Ask Y for $1
Enough cash
2. Write “Y = Y - $1”
Ready to commit
Phase 2: commit
3. Write “X = X + $1”
4. Commit
Ask Y to commit
5. Commit
Scenarios

If X crashes between 1 and 2



If X crashes before step 4


Y will wake up and do nothing
X will timeout and abort the transaction
X will wake up and abort the transaction
If X crashes between 4 and 5

Y will timeout and ask X for the transaction
Scenarios

If Y crashes between 2 and 5



Y will wake up and check the log
When X sends Y the commit message, Y will
commit
Y can also timeout and ask X the current status