首页 > 代码库 > [Network]Link Layer
[Network]Link Layer
1 Introduction
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 sizetime divided same sizenode starts to transmit only slot beginning.all nodes can detect collisionsnodes are synchronized
2) Operation
If no collision: sendIf collision: retransmit in each subsequent slot with probability p until success
3) Advantagesuse full rate of channelsimple4) Disadvantagesidle slotswaste of timeclock 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 transmit2. 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 waitListen 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. Unreliable2. 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 FramesForward by the MAC addresses.Plug and Play, switch self-learningMultiple Simultaneous TransmissionBecause 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 algorithmlearn 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)