Transcript TA9 - Huji cse Moodle 2014/15

Networking
1
OPERATING SYSTEMS COURSE
THE HEBREW UNIVERSITY
SPRING 2014
TA plan
2
 Protocol Stack
 The Internet suit
 Main protocols
 Link layer – MAC, CSMA, ALOHA, Wifi
 Internet layer – IP
 Transport layer – UDP and TCP
 Application layer - DNS
Communication Protocols
4
 A communications protocol is a system of digital
rules for data exchange within or between computers
 Communicating systems use well-defined formats for
exchanging messages.
 A protocol must define the syntax,
semantics, and synchronization
of communication
Sending mails
5
 Email contains
 Address
 Data
The problem of long messages
6
 Sending long messages is problematic
 HW problems
 One “wrong bit” and all the message is wrong.
 QoS (Quality of Service).
 Simple Solution - users are allowed to send
bounded size of messages (e.g. 1K)

Not practical.
Packetization of long messages
7
 Adding a “program”, in both edges, that is
responsible to break the long messages into shorter
ones.
End-to-end control
8
 After splitting to packets, two problems may occur
 A packet overtakes a previous packet
 Lost packet
 End to end control handles these problems
Routing
9
 If there is no direct link between the computers, a
routing is needed
 Routing’s information is added to each packet
Errors Correction
10
 Due to noise, not all the packets are sent
successfully.
 Additional header is added to handle that.
Protocol Stack
11
 Sending side adds headers.
 The receiving side uses the headers and removes them.
 Each layer talks directly with its counterpart on the other
machine
Internet protocol suite (TCP/IP) –
The protocol stack that is used by the Internet
12
Layer
name
Description (Layer’s goal)
Protocols
Application process-to-process communications across
HTTP/S, SSH,
FTP, DNS
Transport
End-to-end communication services for
applications
TCP, UDP
Internet
(Network )
Transport datagrams (packets) from the
originating host across network boundaries, if
necessary, to the destination host specified by
a network address
IP
Link
(Physical)
Communications protocols that only operate
on the link that a host is physically connected
to.
802.11 WiFi,
Ethernet
Internet Layer –
Internet Protocol (IP)
13
Layer
Application
Transport
Internet
Link
IP (IPV4)
14
 The IP creates an internet: a network that is
composed of networks (LANs)
 Responsible for end to end transmission
 Sends data in individual packets
 Unreliable
 Packets might be lost, corrupted, duplicated, delivered out of
order
IP addresses
15
 4 bytes (32 bits)
 The syntax is 163.1.125.98 (where each number is between
0 to 255).
 Each device normally gets one (or more)
 In theory there are about 4 billion available
Routing (local address)
16
 How does a device know where to send a packet?


All devices need to know what IP addresses are on directly attached
networks
If the destination is on a local network, send it directly there
 If the destination address isn’t local


Most non-router devices just send everything to a single local router
Routers need to know which network corresponds to each possible
IP address.


This is done by maintaining a Routing Table, which contains the next
hop for each IP device.
This router often called “Gateway”.
Gateway router
17
Internet
Gateway router
Local Area
Netweork
IP packets
18
 Source and destination addresses
 Protocol number
 6 = TCP, 17 = UDP
 Various options
 e.g. to control fragmentation
 Time to live (TTL)
 Prevent routing loops
Transport Layer
19
Layer
Application
Transport
Internet
Link
User Datagram Protocol (UDP)
20
 Thin layer on top of IP
 The receiver doesn’t send any feedback to the
sender and doesn’t have recourses allocated to him

This is called connectionless.
 Adds packet length + checksum

Guard against corrupted packets
 Also source and destination ports

Ports are used to associate a packet with a specific application
at each end
 Still unreliable:

Duplication, loss, out-of-orderness possible
UDP datagram
21
0
16
31
Source Port
Destination Port
Length
Checksum
Application data
Field
Source Port
Destination Port
Length
Checksum
Purpose
16-bit port number identifying originating application
16-bit port number identifying destination application
Length of UDP datagram (UDP header + data)
Checksum of IP pseudo header, UDP header, and data
Typical use of UDP
22
 UDP is mainly used when
 Packet loss is better handled by the application than the
network stack
 Packet loss is less important than the delay
 The overhead of setting up a connection isn’t wanted
 No enough resources at the receiver force using stateless
protocol
 Applications that use UDP:
 VOIP (Voice over Internet Protocol)
 Protocols for online games
 NFS ( Network File System)
 DNS
TCP (Transmission Control Protocol)
23
 Reliable stream transport
 Connection oriented (full duplex virtual circuit)



Conceptually place call, two ends communicate to agree on details
Provides buffering and flow control
Takes care of lost packets, out of order, duplicates, long delays
 Applications includes: HTTP, HTTPs, FTP, SMTP,
Telnet, SSH
Motivation
24
Source
Destination
Packet 1
Ack 1
The sender:
1. Send a packet.
2. Wait for
acknowledgement
3. Go back to 1.
The receiver:
1. Wait for a packet
2. Acknowledge the
sender
3. Go back to 1.
Packet 2
Ack 2
Packet 3
Application Layer
25
Layer
Application
Transport
Internet
Link
DNS: from domain names to IP
26
 Q: I want to get the web on “www.huji.ac.il”. How
my computer knows its IP address?
 A: Using DNS (Domain Name System)
 It is hierarchical distributed naming system.
 That means that there is no need to map all the names in a
single server.
 DNS Name Server is a server that have a mapping of
names to IP of the device or the next level in the hierarchy.
Top-level DNSs
27
 The number of top hierarchy DNSs is small

They represent countries
.au Australia
 .il Israel
 .it Italy
 .jp Japan
 .uk United Kingdom


Or organizations
.com companies
 .edu educational institutions
 .gov government facilities
 .org non-profit organizations

 The root DNS name servers know about all the top-
level DNSs (the last part of the name).
DNS hierarchy example
How do we find the IP of www.huji.ac.il?
28
Root
edu
com
il
jp
co
tau
ac
huji
it
org
bgu
Getting the IP of www.huji.ac.il
29




Our computer ask the root DNS name server about the IP of
the address.
The root redirects us to the DNS name server of all the
addresses in Israel
This doesn’t know the answer, but redirect us to the DNS
name server of the academic in Israel.
The last return response: “12.131.45.1”.
 Notes –
 These messages are transmitted using UDP protocol
 Often the address will be stored in the cache of a router or
name servers of the Internet Provider
Physical/Link Layer
30
Link
Application
Transport
Internet
Link
Link Layer Goals
31
 The basic networking hardware transmission
technologies of a network


How the bits are actually transmitted.
This is not relevant for us
 Identifying and transmitting to a certain device

Done by using addresses
 Media access control (MAC) - mechanisms that make it
possible for several devices to communicate within a
multiple access network that incorporates a shared
medium


Overcoming collisions
For example, Time Division Multiple Access
Ethernet
32
Ethernet
33
 Ethernet is a family of computer networking
technologies for local area networks (LANs)
 Has several physical advantages (that we won’t
speak about)
 Each Ethernet station is given a 48-bit MAC address
 For humans’ readability it is written as six groups of two
hexadecimal digits, separated by hyphens (-) or colons (:), in
transmission order (e.g. 01-23-45-67-89-ab).
 Each device recognized by its MAC address
Ethernet frame
 Preamble
Trailer consisting of the bit sequence “0101010101...” serving the bit
synchronization of the receiver.
 SFD (Start Frame Delimiter)
Start character consisting of the bit pattern “10101011” showing the recipient
that the actual information will follow now.
 DA (Destination Address)
Evaluated by the recipient‘s address filter; only data frames destined for this
recipient will be passed on to the communication software.
 SA (Source Address)
Sender‘s address
 LEN (Length)
Indicates the length of the subsequent data field in Bytes according to IEEE
802.3.
Ethernet frame
 Data and Pad
The data field may contain 46 to 1500 user data bytes. Are there less than 46
bytes the Ethernet controller independently adds padding bytes, until the
total amount (data + pad) is 46. This miminum length is crucial for the MAC
procedure (CSMA/CD, details later) to work faultlessly. The data field can be
used at will, it only has to contain complete bytes.
 FCS (Frame Check Sequence)
4 bytes of Error Checker. It is obtained by taking the rest of the division
operation from the formula representing the wide-spread cyclicredundancy-check procedure. This formula is applied to the bit sequence
including the address field through to the padding field. In case of en error
the whole frame is ignored, i.e. not passed on to the application program.
Media Access Control
Option 1 - ALOAH
36
 Send the packet.
 Listen to the line. If a collision appeared, wait
random time and try again.

Usually it is used with exponential back off.
The time is usually rand(0, 2^n), where n is the number of
attempts
Media Access Control
Option 2 - Slotted ALOAH
37
 Dividing the time the time into slots that are
synchronized between all the devices
 Each packet may be transmitted only in the
beginning of a slot.
 The rest of the details
similar to ALOAH
 Improves utilization.
Media Access Control Option 3
Carrier sense multiple access (CSMA)
38
 Probabilistic media access control protocol
 CSMA is based on the principle "sense before
transmit"


Verifies the absence of other traffic before transmitting on a
shared transmission medium
If a carrier is sensed, the station waits for the transmission
in progress to finish
 There are several common
modifications of pure CSMA

There are multiple protocols in each such modification
CSMA\CD
39
 Ethernet uses CSMA with Collision Detection
(CSMA\CD)


Improves CSMA performance by terminating transmission
as soon as a collision is detected
Improves ALOHA by sensing before transmitting.
 The algorithms is
 Wait for the line to be free.
 Send the packet.
 Listen to the line.
If a collision detected, use exponential backoff
State Diagram for CSMA\CD
40
Packet?
No
Sense
Carrier
Send
Detect
Collision
Yes
Discard
Packet
attempts < 16
attempts == 16
Jam channel
b=CalcBackoff();
wait(b);
attempts++;
Hub Concept
41
 Separate transmit and receive pair of wires.
 The repeater in the hub retransmits the signal
received on any input pair onto ALL output pairs.
 Essentially the hub emulates a broadcast channel
with collisions detected by receiving nodes.
Hub Illustration
42
hub
     
Single collision domain
Switched Ethernet
43
 Basic idea: improve on the Hub concept
 The switch learns destination locations by
remembering the ports of the associated source
address in a table.
 The switch may not have to broadcast to all output
ports. It may be able to send the frame only to the
destination port.
 A big performance advantage over a hub, if more
than one frame transfer can go through the switch
concurrently.
Switched Ethernet
44
 The advantage comes when the switched Ethernet
backplane is able to repeat more than one frame in
parallel (a separate backplane bus line for each
node).
 The frame is relayed onto the required output port
via the port’s own backplane bus line.
 Under this scheme collisions are still possible when
two concurrently arriving frames are destined for the
same station.
Switch Illustration
45
switch
High-Speed Backplane
or Interconnection fabric




Ethernet Problems
46
 Ethernet’s peak utilization is pretty low (like Aloha)
 Peak throughput worst with
 More hosts


Smaller packet sizes


More collisions needed to identify single sender
More frequent arbitration
Longer links

Collisions take longer to observe, more wasted bandwidth
Wireless
47
Wireless Communication
48
 There are many protocols that use wireless
communication



Wifi (IEEE 802.11)
Blothess (IEEE 802.15)
Cellular communication
 These protocols belong to the Link layer.
Illustration of wireless communication
6-49
network
infrastructure
802.11 frame
50
R1 router
H1
Internet
Access
Point (AP)
R1 MAC addr H1 MAC addr
dest. address
AP MAC addr H1 MAC addr R1 MAC addr
address 1
address 2
address 3
802.11 frame
source address
802.3 frame
(wired protocol)
Wireless Link Characteristics
51
 SNR: signal-to-noise ratio
larger SNR – easier to extract
signal from noise (a good thing)
 SNR versus BER tradeoffs
 given physical layer: increase
power -> increase SNR>decrease BER
 given SNR: choose physical layer
that meets BER requirement,
giving highest throughput
10-1


SNR may change with mobility:
dynamically adapt physical layer
(modulation technique, rate)
10-2
BER
10-3
10-4
10-5
10-6
10-7
10
20
30
SNR(dB)
QAM256 (8 Mbps)
QAM16 (4 Mbps)
BPSK (1 Mbps)
40
IEEE 802.11: Media access control
52
 CSMA - sense before transmitting
 don’t collide with ongoing transmission by other node
 No collision detection!
 difficult to receive (sense collisions) when transmitting due to
weak received signals (fading)
 can’t sense all collisions in any case: hidden terminal, fading
 goal: avoid collisions: CSMA/C(ollision)A(voidance)
A
C
A
B
B
C
C’s signal
strength
A’s signal
strength
space
IEEE 802.11 MAC Protocol: CSMA/CA
53
802.11 sender
1.
2.
3.
If sense channel idle for DIFS then
transmit entire frame (no CD)
If sense channel busy then start random
backoff time timer counts down while
channel idle transmit when timer expires
If no ACK, increase random backoff
interval, repeat 2
802.11 receiver
- if frame received OK
return ACK after SIFS (ACK needed due to
hidden terminal problem)
sender
receiver
DIFS
data
SIFS
ACK
Avoiding collisions (more)
54
idea: allow sender to “reserve” channel rather than random
access of data frames: avoid collisions of long data frames
 sender first transmits small request-to-send (RTS) packets to BS
using CSMA
 RTSs may still collide with each other (but they’re short)
 BS broadcasts clear-to-send CTS in response to RTS
 CTS heard by all nodes
 sender transmits data frame
 other stations defer transmissions
avoid data frame collisions completely
using small reservation packets!
Collision Avoidance: RTS-CTS exchange
55
A
B
AP
reservation collision
DATA (A)
time
defer
Wireless communication additional features
56
 Moving between two access points
 Connection Establishment
 Additional wireless protocols
 And much more!
Code Division Multiple Access (CDMA)
57
 Used in several wireless broadcast channels (cellular,





satellite, etc) standards
Unique “code” assigned to each user; i.e., code set
partitioning
Each user has own code to encode data
Encoded signal = (original data) X (chipping sequence)
Decoding: inner-product of encoded signal and
chipping sequence
Allows multiple users to “coexist” and transmit
simultaneously with minimal interference (if codes are
“orthogonal”)
6: Wireless and Mobile Networks
CDMA Encode/Decode
58
sender
d0 = 1
data
bits
code
Zi,m= di.cm
- 1
- 1
1
1
1
1 1 1
- 1
- 1
1
slot 1
1
slot 1
channel
output
1
1
1 1 1 1 1 1
1
d1 = -1
1 1 1
channel output Zi,m
- 1
- 1
1
slot 0
1
1
- 1
- 1
1
slot 0
channel
output
M
Di = S Zi,m.cm
m=1
received
input
code
receiver
1 1 1 1 1 1
1
- 1
- 1
1
1
1 1 1
1
1
- 1
- 1
1
1
1 1 1
- 1
- 1
1
slot 1
M
1
1
1
- 1
- 1
1
slot 0
d0 = 1
d1 = -1
slot 1
channel
output
slot 0
channel
output
CDMA: two-sender interference
6-59