Link Layerطبقة ربط البيانات
مقدمة الفصل
ماذا ستتعلم في هذا الفصل
- Principles behind data link layer services: error detection, correction; sharing a broadcast channel: multiple access; link layer addressing.
- Instantiation and implementation of link layer technologies: Ethernet, switched LANs.
أقسام الفصل
- 1Link layer: introduction and servicesطبقة الربط: مقدمة وخدمات
- 2Error detection: parity, checksum, CRCكشف الأخطاء: التكافؤ والمجموع الاختباري وCRC
- 3Multiple access: CSMA and CSMA/CDالوصول المتعدد: CSMA وCSMA/CD
- 4MAC addresses and ARPعناوين MAC وبروتوكول ARP
- 5Addressing: routing to another LANالعنونة: التوجيه إلى شبكة محلية أخرى
- 6EthernetEthernet
- 7Ethernet switches: self-learning and forwardingمبدّلات Ethernet: التعلم الذاتي والتمرير
- 8Switches vs routersالمبدّلات مقابل الموجّهات
تلميح: استخدم أسهم لوحة المفاتيح للتنقل بين الشرائح.
Link layer: introductionمقدمة طبقة الربط
Hosts and routers.
Communication channels that connect adjacent nodes along communication path: wired links, wireless links, LANs.
Layer-2 packet; encapsulates datagram.
Data-link layer has responsibility of transferring datagram from one node to physically adjacent node over a link.
Link layer servicesخدمات طبقة الربط
Link layer: introduction and services
- Framing, link access
Encapsulate datagram into frame, adding header, trailer; channel access if shared medium; "MAC" addresses used in frame headers to identify source, dest — different from IP address!
- Reliable delivery between adjacent nodes
Seldom used on low bit-error link (fiber, some twisted pair); wireless links: high error rates.
- Flow control
Pacing between adjacent sending and receiving nodes.
- Error detection
Errors caused by signal attenuation, noise. Receiver detects presence of errors: signals sender for retransmission or drops frame.
- Error correction
Receiver identifies and corrects bit error(s) without resorting to retransmission.
- Half-duplex and full-duplex
With half duplex, nodes at both ends of link can transmit, but not at same time.
Where is the link layer implemented?أين تُنفَّذ طبقة الربط؟
Link layer: introduction and services
- In each and every host.
- In an "adaptor" (aka network interface card NIC) or on a chip: Ethernet card, 802.11 card; Ethernet chipset.
- Implements link, physical layer; attaches into host's system buses.
- Combination of hardware, software, firmware.
Sending side
- Encapsulates datagram in frame
- Adds error checking bits, rdt, flow control, etc.
Receiving side
- Looks for errors, rdt, flow control, etc.
- Extracts datagram, passes to upper layer
Error detection and parityكشف الأخطاء والتكافؤ
Error detection: parity, checksum, CRC
Error Detection and Correction bits (redundancy).
Data protected by error checking; may include header fields.
- Error detection not 100% reliable! Protocol may miss some errors, but rarely.
- Larger EDC field yields better detection and correction.
Single bit parity
- Detect single bit errors
Two-dimensional bit parity
- Detect and correct single bit errors
Cyclic redundancy check (CRC)CRC
Error detection: parity, checksum, CRC
- 1
View data bits, D, as a binary number.
- 2
Choose an r+1 bit pattern (generator), G.
- 3
Choose r CRC bits, R, such that <D,R> is exactly divisible by G (modulo 2).
- 4
Receiver knows G and divides <D,R> by G. If non-zero remainder: error detected!
المسألة
Goal (slide 13): choose r CRC bits, R, such that <D,R> is exactly divisible by G (modulo 2).
الصيغة
R = remainder[ D·2^r / G ]
خطوات الحل
- Want: D·2^r XOR R = nG
- Equivalently: D·2^r = nG XOR R
- Equivalently: if we divide D·2^r by G, want remainder R
النتيجة
The CRC bits R are the remainder of D·2^r divided by G.
- Can detect all burst errors less than r+1 bits.
- Widely used in practice (Ethernet, 802.11 WiFi, ATM).
Multiple access links; CSMAالوصول المتعدد وCSMA
Multiple access: CSMA and CSMA/CD
Point-to-point
- PPP for dial-up access
- Point-to-point link between Ethernet switch, host
Broadcast (shared wire or medium)
- Old-fashioned Ethernet
- Upstream HFC
- 802.11 wireless LAN
If channel sensed idle: transmit entire frame. If channel sensed busy: defer transmission. Human analogy: don't interrupt others!
CSMA collisions (slide 18)
- Collisions can still occur: propagation delay means two nodes may not hear each other's transmission.
- Collision: entire packet transmission time wasted.
- Distance & propagation delay play role in determining collision probability.
CSMA/CD and the Ethernet algorithmCSMA/CD
Multiple access: CSMA and CSMA/CD
Carrier sensing, deferral as in CSMA; collisions detected within short time; colliding transmissions aborted, reducing channel wastage.
CSMA/CD figure (slide 20)
- Four nodes in a row (spatial layout of nodes), time running downward: a node starts transmitting at t0, a node farther along starts at t1 before the first signal reaches it; the two transmissions overlap, each node detects the collision and aborts — the "collision detect/abort time".
Wired LANs: easy
- Measure signal strengths, compare transmitted, received signals
Wireless LANs: difficult
- Received signal strength overwhelmed by local transmission strength
Ethernet CSMA/CD algorithm (slide 21)
- 1
NIC receives datagram from network layer, creates frame.
- 2
If NIC senses channel idle, starts frame transmission. If NIC senses channel busy, waits until channel idle, then transmits.
- 3
If NIC transmits entire frame without detecting another transmission, NIC is done with frame!
- 4
If NIC detects another transmission while transmitting, aborts and sends jam signal.
- 5
After aborting, NIC enters binary (exponential) backoff: after mth collision, NIC chooses K at random from {0,1,2, …, 2^m − 1}; NIC waits K·512 bit times, returns to Step 2.
MAC addressesعناوين MAC
| IP address | MAC address | |
|---|---|---|
| Size | 32 bits | 48 bits (for most LANs) |
| Layer / use |
| Used "locally" to get a frame from one interface to another physically-connected interface |
| Structure | Hierarchical — not portable (depends on the IP subnet) | Flat — portable (can move LAN card to another LAN) |
| Analogy | Postal address | Social Security Number |
| Assigned by | — (depends on subnet) |
|
- Example MAC address: 1A-2F-BB-76-09-AD — hexadecimal (base 16) notation; each "number" represents 4 bits.
- Each adapter on LAN has unique LAN address; the manufacturer buys a portion of the MAC address space (to assure uniqueness).
- MAC address is burned in NIC ROM, also sometimes software settable.
ARP: address resolution protocolARP
MAC addresses and ARP
How to determine an interface's MAC address, knowing its IP address?
Each IP node (host, router) on LAN has a table of IP/MAC address mappings for some LAN nodes: < IP address; MAC address; TTL >. TTL: time after which address mapping will be forgotten (typically 20 min).
ARP protocol: same LAN (A wants to send a datagram to B)
- 1
B's MAC address is not in A's ARP table.
- 2
A broadcasts an ARP query packet containing B's IP address — dest MAC address = FF-FF-FF-FF-FF-FF. All nodes on the LAN receive the query.
- 3
B receives the ARP packet and replies to A with its (B's) MAC address — frame sent to A's MAC address (unicast).
- 4
A caches (saves) the IP-to-MAC pair in its ARP table until the information becomes old (times out).
- Soft state: information that times out (goes away) unless refreshed.
- ARP is "plug-and-play": nodes create their ARP tables without intervention from net administrator.
Addressing: routing to another LANمن شبكة محلية إلى أخرى
Walkthrough: send a datagram from A to B via router R. Assume A knows B's IP address, the IP address of first hop router R, and R's MAC address.
- A
Creates IP datagram with IP source A, destination B.
- A
Creates link-layer frame with R's MAC address as dest; frame contains the A-to-B IP datagram.
- R
Frame received at R; datagram removed, passed up to IP.
- R
Forwards datagram with IP source A, destination B; creates link-layer frame with B's MAC address as dest.
| Hop | MAC src | MAC dest | IP src | IP dest |
|---|---|---|---|---|
| A → R | 74-29-9C-E8-FF-55 (A) | E6-E9-00-17-BB-4B (R, A's side) | 111.111.111.111 (A) | 222.222.222.222 (B) |
| R → B | 1A-23-F9-CD-06-9B (R, B's side) | 49-BD-D2-C7-56-2A (B) | 111.111.111.111 (A) | 222.222.222.222 (B) |
Ethernet and its topologyEthernet
"Dominant" wired LAN technology
- Cheap: $20 for NIC
- First widely used LAN technology
- Simpler, cheaper than token LANs and ATM
- Kept up with speed race: 10 Mbps – 10 Gbps
Bus
- Popular through mid 90s
- All nodes in same collision domain (can collide with each other)
- Coaxial cable
Star
- Prevails today
- Active switch in center
- Each "spoke" runs a (separate) Ethernet protocol (nodes do not collide with each other)
Ethernet: unreliable, connectionless (slide 39)
- Connectionless: no handshaking between sending and receiving NICs.
- Unreliable: receiving NIC doesn't send acks or nacks to sending NIC; data in dropped frames recovered only if initial sender uses higher layer rdt (e.g., TCP), otherwise dropped data lost.
- Ethernet's MAC protocol: unslotted CSMA/CD with binary backoff.
- 802.3 standards: common MAC protocol and frame format; different speeds and physical layer media (copper twisted pair, fiber), e.g., 100BASE-TX, 100BASE-FX.
Ethernet frame structureإطار Ethernet
Frame fields, in order
- preamble
- dest. address
- source address
- type
- data (payload)
- CRC
| Field | Size / content | Purpose |
|---|---|---|
| Preamble | 7 bytes 10101010 + 1 byte 10101011 | Synchronize receiver, sender clock rates |
| Dest. address | 6 bytes (MAC) |
|
| Source address | 6 bytes (MAC) | Sender's MAC address |
| Type | لا تذكر الشرائح شيئًا هنا. |
|
| Data (payload) | IP datagram (or other network layer packet) | The encapsulated packet |
| CRC | لا تذكر الشرائح شيئًا هنا. |
|
Ethernet switchمبدّل Ethernet
Link-layer device: takes an active role
- Store, forward Ethernet frames.
- Examine incoming frame's MAC address, selectively forward frame to one-or-more outgoing links; uses CSMA/CD to access a segment when forwarding on it.
- Transparent: hosts are unaware of presence of switches.
- Plug-and-play, self-learning: switches do not need to be configured.
Multiple simultaneous transmissions (slide 43)
- Hosts have dedicated, direct connection to switch; switches buffer packets.
- Ethernet protocol used on each incoming link, but no collisions; full duplex.
- Each link is its own collision domain: A-to-A' and B-to-B' can transmit simultaneously, without collisions.
(MAC address of host, interface to reach host, time stamp) — looks like a routing table!
Self-learning, filtering and forwardingالتعلم والتمرير في المبدّل
Ethernet switches: self-learning and forwarding
When a frame is received, the switch "learns" the location of the sender (incoming LAN segment) and records the sender/location pair in its switch table.
Frame filtering/forwarding (slide 46)
- 1
Record incoming link, MAC address of sending host.
- 2
Index switch table using MAC destination address.
- 3a
If entry found for destination: if destination on segment from which frame arrived, drop frame; else forward frame on interface indicated by entry.
- 3b
Else flood: forward on all interfaces except arriving interface.
Self-learning multi-switch example (slide 49)
- Switch S4 connects switches S1 (hosts A, B, C), S2 (hosts D, E, F) and S3 (hosts G, H, I). Suppose C sends a frame to I, and I responds to C.
- Q: show switch tables and packet forwarding in S1, S2, S3, S4. (The slide gives no answer.)
Switches vs routersالمبدّل والموجّه
| Router | Switch | |
|---|---|---|
| Layer | Network-layer device (examines network-layer headers) | Link-layer device (examines link-layer headers) |
| Operation | Store-and-forward | Store-and-forward |
| Forwarding table | Computed using routing algorithms, IP addresses | Learned using flooding, learning, MAC addresses |
- Slide 50 (institutional network): switches join hosts, a mail server and a web server in one IP subnet; a router connects it to the external network.
الخلاصة
أنهيت الدرس
الخطوة التالية: ثبّت المعلومات بالبطاقات، ثم اختبر نفسك بالأسئلة.
ما راجعته في هذا الدرس
- Link layer: introduction and servicesطبقة الربط: مقدمة وخدمات
- Error detection: parity, checksum, CRCكشف الأخطاء: التكافؤ والمجموع الاختباري وCRC
- Multiple access: CSMA and CSMA/CDالوصول المتعدد: CSMA وCSMA/CD
- MAC addresses and ARPعناوين MAC وبروتوكول ARP
- Addressing: routing to another LANالعنونة: التوجيه إلى شبكة محلية أخرى
- EthernetEthernet
- Ethernet switches: self-learning and forwardingمبدّلات Ethernet: التعلم الذاتي والتمرير
- Switches vs routersالمبدّلات مقابل الموجّهات