Podcast
Questions and Answers
In pure ALOHA, the collision probability increases when a frame is sent at t0 and collides with other frames sent in [t0-1, t0+1]. This leads to a lower ______ compared to slotted ALOHA.
In pure ALOHA, the collision probability increases when a frame is sent at t0 and collides with other frames sent in [t0-1, t0+1]. This leads to a lower ______ compared to slotted ALOHA.
efficiency
CSMA stands for ______ sense multiple access, where nodes listen to the channel before transmitting.
CSMA stands for ______ sense multiple access, where nodes listen to the channel before transmitting.
carrier
In CSMA/CD, collisions are detected quickly, allowing colliding transmissions to be ______, thereby reducing channel wastage.
In CSMA/CD, collisions are detected quickly, allowing colliding transmissions to be ______, thereby reducing channel wastage.
aborted
The probability that a given node successfully transmits in a slot can be modeled as p(1-p)^{______-1} for N nodes.
The probability that a given node successfully transmits in a slot can be modeled as p(1-p)^{______-1} for N nodes.
Signup and view all the answers
In wireless LANs, detecting a collision is difficult because the received ______ strength can be overwhelmed by the strength of local transmissions.
In wireless LANs, detecting a collision is difficult because the received ______ strength can be overwhelmed by the strength of local transmissions.
Signup and view all the answers
If entry found for ______, then drop frame.
If entry found for ______, then drop frame.
Signup and view all the answers
When the destination is known, the frame is selectively sent on just one ______.
When the destination is known, the frame is selectively sent on just one ______.
Signup and view all the answers
If the destination location is unknown, the system will ______.
If the destination location is unknown, the system will ______.
Signup and view all the answers
The process through which switches learn to forward frames is known as ______ learning.
The process through which switches learn to forward frames is known as ______ learning.
Signup and view all the answers
To forward a frame from A to G, S1 must determine the correct path via ______ and S3.
To forward a frame from A to G, S1 must determine the correct path via ______ and S3.
Signup and view all the answers
A broadcasts ARP query packet, containing B's IP address and the destination MAC address is ______.
A broadcasts ARP query packet, containing B's IP address and the destination MAC address is ______.
Signup and view all the answers
ARP is described as 'plug-and-play,' indicating nodes create their ARP tables without ______ from a network administrator.
ARP is described as 'plug-and-play,' indicating nodes create their ARP tables without ______ from a network administrator.
Signup and view all the answers
R forwards the datagram with IP source A and destination ______.
R forwards the datagram with IP source A and destination ______.
Signup and view all the answers
Ethernet is known for being the dominant wired LAN technology due to its ______ and simplicity.
Ethernet is known for being the dominant wired LAN technology due to its ______ and simplicity.
Signup and view all the answers
In a star topology, an active ______ is placed in the center to manage the connections between nodes.
In a star topology, an active ______ is placed in the center to manage the connections between nodes.
Signup and view all the answers
The initial goal of MPLS is high-speed IP forwarding using a fixed length ______.
The initial goal of MPLS is high-speed IP forwarding using a fixed length ______.
Signup and view all the answers
MPLS uses a fixed length identifier for fast lookup rather than the shortest prefix ______.
MPLS uses a fixed length identifier for fast lookup rather than the shortest prefix ______.
Signup and view all the answers
In MPLS, IP datagrams still retain their original IP ______.
In MPLS, IP datagrams still retain their original IP ______.
Signup and view all the answers
The Tag Control Information in the VLAN frame includes a 12 bit ______ ID field.
The Tag Control Information in the VLAN frame includes a 12 bit ______ ID field.
Signup and view all the answers
MPLS capable routers are also known as ______.
MPLS capable routers are also known as ______.
Signup and view all the answers
Study Notes
Chapter 5: Link Layer
- PowerPoint slides are freely available for faculty, students, and readers.
- Slides include animations and can be modified and deleted.
- Users are asked to acknowledge the source of the slides and copyright when using or posting them online.
Link Layer: Introduction
-
Terminology:
- Hosts and routers are nodes.
- Communication channels connecting adjacent nodes are links (wired or wireless).
- Layer-2 packet is called a frame and encapsulates a datagram.
- Data-link layer is responsible for transferring datagrams between physically adjacent nodes over a link.
Link Layer: Context
- Different link protocols transfer datagrams over different links.
- Examples include Ethernet, frame relay, and 802.11 on different links.
- Each link protocol provides distinct services.
- Protocols may or may not offer reliable data transfer over the link.
- Analogy: a trip can be made by different methods (e.g., limo, plane, train) to compare data transfer by various protocols.
Link Layer Services
-
Framing and Link Access:
- Encapsulates datagram into a frame, including header and trailer.
- Channel access mechanisms for shared mediums, using MAC addresses (different from IP addresses) to identify source and destination.
-
Reliable Delivery (between adjacent nodes):
- This is covered in earlier chapters (Chapter 3).
- Seldom used on low bit-error links (e.g., fiber), but critical for wireless links with high error rates.
- Reliability concerns both link level and end-to-end reliability.
-
Flow Control:
- Pacing between adjacent sending and receiving nodes.
Link Layer Services (More)
-
Error Detection:
- Errors caused by signal attenuation and noise.
- Receiver detects errors through various methods, signaling sender for retransmission or dropping the frame.
-
Error Correction:
- Receiver identifies and corrects errors without retransmission.
-
Half-Duplex and Full-Duplex:
- Half-duplex: nodes can transmit but not simultaneously.
- Full-duplex: nodes can transmit simultaneously.
Where is the Link Layer Implemented?
- Implemented in each host's network adapter (NIC) or on a chip.
- Ethernet card, 802.11 card, and Ethernet chipset implement link and physical layer functions.
- Attaches to host system buses.
- A combination of hardware, software, and firmware.
Adaptors Communicating
- Sending side encapsulates datagram into frame, adding error-checking bits, rdt, and flow control.
- Receiving side checks for errors, performs rdt and flow control, extracts datagram, and sends it to the upper layer.
Link Layer, LANs: Outline
- Sections on introduction, services, error detection, correction, multiple access protocols, LANs (addressing, ARP, Ethernet, switches, VLANs), link virtualization (MPLS), data center networking, and a day in a web request’s life are covered.
Error Detection
- Error detection is not 100% reliable; protocols may miss some errors, although the likelihood of this is rare
- Techniques involved include cyclic redundancy checking (CRC). Longer fields improve error detection capabilities.
Parity Checking
- Single-bit parity: Detects single-bit errors.
- Two-dimensional bit parity: Detects and corrects single-bit errors.
Internet Checksum (Review)
- Goal: Detect errors in transmitted packets.
- Used solely at the transport layer.
- Sender treats segment contents as 16-bit integers, computes sum (ones' complement), and inserts value into UDP checksum field.
- Receiver computes checksum of received segment and compares to checksum field value to check for errors.
Cyclic Redundancy Check (CRC)
- Powerful error-detection coding.
- Data bits (D) treat as binary number with chosen r+1 bit pattern (generator) G.
- Receiver divides <D,R> by G to check for errors (non-zero remainder = error).
- Widely used (e.g., Ethernet, 802.11, WiFi, ATM).
CRC Example
- Demonstration of dividing D-2 by G to find remainder R.
Multiple Access Protocols (MAC protocols)
- Protocols for sharing a common broadcast channel, requiring nodes to coordinate.
- Categories include channel partitioning, random access, and "taking turns."
Channel Partitioning MAC Protocols: TDMA
- Access to the channel in "rounds".
- Each station gets a fixed-length slot.
- Unused slots remain idle.
Channel Partitioning MAC Protocols: FDMA
- Channel spectrum divided into frequency bands.
- Each station is assigned a fixed frequency band.
- Unused bandwidth goes idle.
Random Access Protocols
- Channel is not divided; collisions are possible.
- Protocols specify collision detection and recovery methods.
- Examples include slotted ALOHA, ALOHA, CSMA, CSMA/CD, CSMA/CA.
Slotted ALOHA
- Frames all the same size.
- Time is divided into equal-sized slots.
- Nodes start transmission only at slot beginnings.
- Nodes are synchronized.
Slotted ALOHA: Efficiency
- Long-run fraction of successful slots (many nodes, many frames to send)
- Probability of success for a given node in a slot (depends on N nodes/probability p).
Pure (Unslotted) ALOHA
- Simpler, but without synchronization.
- Frames transmit immediately after arrival.
- Collision probability increases as more transmissions occur.
Pure ALOHA Efficiency
- Probability of success of transmissions that are not collisions.
CSMA (Carrier Sense Multiple Access)
- Nodes listen before transmitting.
- If idle, transmits entire frame; otherwise, defers transmission.
- Human analogy: Do not interrupt others
CSMA Collisions
- Collisions can occur due to propagation delay.
- Two nodes might not hear each other, thus leading to transmission collisions.
- Entire transmission cycle is wasted if a collision happens.
CSMA/CD (Collision Detection)
- Collisions detected in short time; colliding transmissions aborted, reducing wasted channel bandwidth.
- Easy in wired LANs (measur signal strengths).
- Difficult in wireless LANs (received signal strength overwhelmed by other transmissions).
Ethernet CSMA/CD Algorithm
- NIC receives datagram from the network layer, creates frame.
- If channel idle, starts transmission; otherwise, waits until idle.
- If NIC transmits frame without collision, it is done.
- Collision detected? Aborts transmission, transmits jam signal.
- Reenters binary (exponential) backoff.
- Chooses K at random and waits K time slots, returning to step 2.
- Longer backoff interval with more collisions.
CSMA/CD Efficiency
- Transmission time vs. propagation delay; as tprop goes to 0 and ttrans goes to infinity, efficiency approaches 1/(1+5tprop/ttrans)
“Taking Turns” MAC Protocols
- Describe channel partitioning MAC protocols, random access MAC protocols, and "taking turns" protocols.
- Channel partitioning (e.g., TDMA, FDMA): Efficient at high load, but inefficient at low load.
- Random access: Efficient at low load, but inefficient at high load.
- Taking turns protocols (e.g., polling, token passing): Look for best of both worlds.
Polling
- Master node "invites" slave nodes to transmit in turn.
- Generally used for dumb slave devices.
- Concerns include polling overhead, latency, and single point of failure (master).
Token Passing
- Control token passed from one node to the next sequentially.
- Token message sent when nothing is to be sent.
- Concerns include token overhead, latency, and single point of failure (token).
Cable Access Network
- Internet frames, TV channels, downstream (broadcast) and upstream transmissions in time slots.
- 40 Mbps downstream (broadcast) channels; single CMTS transmits into channels.
- Multiple 30 Mbps upstream channels.
- Multiple access: Users contend for upstream channel time slots.
DOCSIS (Data Over Cable Service Interface Specification)
- FDM over upstream and downstream frequency channels.
- TDM upstream: some slots assigned, others have contention.
- Downstream MAP frame: assigns upstream slots and data requests.
- Implements random access (binary backoff) in selected slots.
Summary of MAC Protocols
- Channel partitioning (time/frequency/code), random access (Aloha, S-Aloha, CSMA, CSMA/CD), taking turns (polling, token passing).
MAC Addresses and ARP
- 32-bit IP address: network layer address for forwarding (layer 3).
- 48-bit MAC address (or LAN/physical address): used for local communication within a network.
- ARP (Address Resolution Protocol) maps IP addresses to MAC addresses.
LAN Addresses and ARP
- Each adapter on a LAN has a unique MAC address.
LAN Addresses (More)
- IEEE administrates MAC address allocation to ensure uniqueness.
- MAC flat address is portable; IP address is hierarchical and not portable.
ARP: Address Resolution Protocol
- Given an IP address, determines the corresponding MAC address.
- ARP table in each node (host/router) maps IP addresses to MAC addresses.
- TTL (Time To Live) is also used.
ARP Protocol: Same LAN
- Method used to find MAC address if it is not already stored in the ARP cache.
- A broadcast ARP query is used if the address isn't found.
Addressing: Routing to another LAN
- Sending a datagram from one LAN to another via a router.
- Data link layer frame created, containing the datagram.
- Includes IP source and destination addresses, and MAC addresses.
Addressing: Routing to another LAN
- Description of steps in sending a frame from one host (A) to another host (B) via a router (R).
- Creating the IP datagram including source and destination IP addresses.
- Creating the Ethernet/data-link frame, encapsulating the IP datagram.
- Forwarding the frame from A to R, and from R to B.
Ethernet
- Dominant wired LAN technology.
- Inexpensive NICs.
- Simpler than token LANs and ATM.
- Maintained pace with speed races (10 Mbps - 10 Gbps).
Ethernet: Physical Topology
- Bus: Nodes are on the same collision domain.
- Star: Active switch is central; Each spoke is a separate collision domain, avoiding collisions.
Ethernet Frame Structure
- Preamble: 7 bytes with 10101010 pattern, followed by 1 byte with 10101011 pattern. Used to synchronize sender and receiver clock rates.
- Addresses: 6-byte source and destination MAC addresses.
- Type: Indicates higher-layer protocol.
- Data (payload): Encapsulated IP datagram or other network layer protocol packet.
- CRC: Cyclic redundancy check at receiver; error detection dropped frame.
Ethernet: Unreliable, Connectionless
- Connectionless: No handshaking between sending and receiving NICs.
- Unreliable: Receiving NIC does not send acks/nacks.
- Relies on higher-layer rdt (e.g., TCP) to recover dropped frames.
802.3 Ethernet Standards: Link & Physical Layers
- Common MAC protocol and frame format
- Various speeds (2 Mbps, 10 Mbps, etc.).
- Different physical layer media (fiber, cable).
Ethernet Switch
- Active role in storing and forwarding Ethernet frames.
- Examines incoming frame's MAC address, forwarding to one or more outgoing links.
- Uses CSMA/CD to access the segment.
- Transparent operation is critical.
Switch: Multiple Simultaneous Transmissions
- Hosts have dedicated connections to the switch.
- Packets buffered on each link without collisions.
- Each link is its own collision domain.
- Switching allows simultaneous transmission without collisions on different ports.
Switch Forwarding Table
- How does a switch determine the proper output port?
- Switch table includes: MAC address of host, interface to reach host, time stamp.
Switch: Self-Learning
- Switch learns host locations and associated interfaces.
- When a frame arrives, the switch learns the sender's LAN segment and interface.
- This information is logged in the switch table.
Switch: Frame Filtering/Forwarding
- Record incoming link, MAC address of sending host.
- Index switch table using destination MAC address.
- If entry found for destination, and destination is on the same segment from which the frame arrived, drop the frame.
- Otherwise, forward the frame to the appropriate interface, excluding the incoming interface.
Self-Learning, Forwarding: Example
- If frame destination is unknown (not in the switch table), flood to all ports except input (unicast).
- If destination is known, send selectively on the appropriate port.
Interconnecting Switches
- Switches can be interconnected.
- Self-learning works in the same manner as single-switch scenarios.
Data Center Networks
- Large number of closely coupled hosts.
- Applications include e-business, content servers, search engines, data mining.
- Challenges include managing/balancing load, network bottlenecks, and data management.
Data Center Networks: Load Balancer
- Receives external client requests.
- Distributes workload within the data center.
- Returns results to the client (hide internal data).
Data Center Networks: Rich Interconnection
- Rich interconnection among switches and racks.
- Increased throughput (multiple routing paths).
- Increased reliability through redundancy.
Synthesis: A Day in the Life of a Web Request
- Journey down the protocol stack (application, transport, network, link).
- Putting it all together: Understanding scenario protocols.
- Scenario: Student requests a web page (e.g., www.google.com).
A Day in the Life... Connecting to the Internet
- Laptop needs to get IP address, router, and DNS server addresses (DHCP).
- Laptop broadcasts DHCP request, router responds with DHCP ACK, which includes IP address, router address and DNS address.
A Day in the Life... ARP
- Determining MAC addresses of network devices.
- Used to broadcast and retrieve the necessary MAC address.
A Day in the Life …Using DNS
- IP datagram that contains a DNS query is forwarded through the LAN switch to the first-hop router.
- Further forwarded by routers in the network utilizing RIP, OSPF, or BGP protocols.
- DNS server sends a reply with IP address to the client.
A Day in the Life… TCP Connection Carrying HTTP
- Client establishes TCP connection with web server.
- TCP SYN segment sent (step 1 in 3-way handshake) by client and responded with TCP SYNACK by web server.
- TCP connection is successfully established, HTTP request sent.
A Day in the Life… HTTP Request/Reply
- HTTP request sent to web server.
- Web server sends response containing web page content.
- The IP datagram carrying the HTTP reply is routed back to the client.
Chapter 5: Summary
- Principles behind data link layer services.
- Instantiation and implementation of various link layer technologies.
- Ethernet, switched LANs, and VLANs.
- Virtualized networks (MPLS).
- Synthesis: a day in the life of a web request.
Chapter 5: Let's Take a Breath
- Journey down the protocol stack, understanding networking principles, and practice.
- Possible to stop here but potential topics for further study: Wireless, multimedia, security, network management.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Test your knowledge on computer networking concepts, including ALOHA protocols, CSMA/CD, collisions, and frame forwarding techniques. This quiz covers key principles and mechanisms used in network communication, ideal for students in computer science and networking courses.
