首页 > 代码库 > [Network]Link Layer

[Network]Link Layer

1 Introduction

This part explains some similar points of other layers, such as layer service, data format and link.
And link layer is a layer of combination of hardware, software and firmware.
But why both link-level and end-end systems need rdt?


2 Error Detection and Correction: EDC

2.1 SIngle Bit Parity


2.2 Two Dimensional Bit Parity


2.3 Checksum: CRC - Cylic Redundancy Check

d bits data(D) and r bits extension(R)

r+1 bits (G) a generator

divide to check if it is the same as former R




3 Multiple Access Protocols

3.1 Multiple Access Links

1. point-to-point

2. broadcast: share wire and medium


3.2 Multiple Access Protocols

Channel Partitioning:divide channel into smaller "pieces"

1. TDMA


2. FDMA



Random Access

1. Idea: When nodes has pkts to send, the end will use the whole transmission rate.

2. Problem: two ore more transmitting nodes -> collision

3. Goals: how to detect collisions and how to recover from collisions.


Examples

1. Slotted ALOHA

1) Assumption
all frame same size
time divided same size
node starts to transmit only slot beginning.
all nodes can detect collisions
nodes are synchronized
2) Operation
If no collision: send
If collision: retransmit in each subsequent slot with probability p until success
3) Advantages
use full rate of channel
simple
4) Disadvantages
idle slots
waste of time
clock synchronization

2. ALOHA

1. Idea: no synchronization. transmit immediately.
2. Problem: the collision probability increases.

3. CSMA: Carrier Sense Mutilple Access

1. Idea: listen before transmit
2. Problem: propogation delay means that two nodes may not hear each other‘s transmission. 
Look the image below the B‘s transmission is heard by A, C and D at different times with different distances.

3. Operation
Listen before transmission, busy to wait
Listen while transmitting, collision to wait


Taking Turns
Idea like the name.


4 Link Layer Addressing

4.1 MAC Address: 48 bits

4.2 ARP: Address Resolution Protocol

1. WHY: 

One node may know IP address of another node, but it may not know MAC address of the node. So we simply need to build ARP table for mapping from IP address to MAC address. And we learn that IP addresses are distrubute to a subnet with logic, and MAC address is related to an interface physically. So and IP address is just a logical defination which tell the transmission where to go, and the MAC address indicates a perticular facility.

2. Example



5 Ethernet

5.1 Star Topology

Opposed to the bus topology, star topology has a center active switch in center. Nodes do not collide with each other directly.


5.2 Frame Structure


Preamble: used to synchronize receiver sender and clock rates.
Address: adapter check it if matching. If not, the adapter will discard the frame. (6 bytes - 48 bits)
Type: Network Layer Protocol

5.3 Services

1. Unreliable
2. Connectionless

5.4 CSMA/CD

1. Sense before transmission

2. Sense while transmitting

1) If detecting another transmission, abort and send jam signal

After aborting, NIC enters exponential backoff: after mth collision, chooseK from {0, 1, 2, ..., 2^m - 1}. NIC waitK*512 bit times, and return to sense before transmission.

Jam Signal: 48 bits

Bit Time: 


6 Link Layer Switch

6.1 Hub

no frame buffering, hub does not detect collisions, host NICs detect collisions.

6.2 Switch

Store and Forwarding Ethernet Frames
Forward by the MAC addresses.
Plug and Play, switch self-learning

Multiple Simultaneous Transmission
Because hosts have dedicate connections to the switch. 
Switch buffers frames, and switch frames to outgoing links without collision. Because the ingoing links are not shared.

Self-learning: some thing like routing algorithm
learn which host can be reached through which interface. Just Plug into the switch!
If some transmission‘s dest is not known, then flood -> forward on all but the interface where the frame arrives.

Network: router and switch


7 PPP: point-to-point protocol

Error recovery, flow control, data re-ordering all relegated to higher layers.


8 Link Virtualization

8.1 WHY Virtualization 

Because there are different local network technology, cable, satellite, telephone and ATM, etc. So we need some work of virtualization to get them homogeneous.

8.2 ATM

Build Virtual Circuits. And work with IP.

8.3 MPLS: Multiprotocol Label Switching

speed up IP forwarding by using fixed length label(Instead of IP address)