Computer Networks Class 7: Switching and Network Layer Overview
Explore the concepts of Ethernet switching, spanning tree, ATM, and network layer protocols like Internet Protocol (IPv4). Understand the drawbacks of flooding in network communication and the solutions like Spanning Tree and VLANs to overcome loop issues and scalability challenges.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CPS-356- Computer Networks Class 7: Switching Continued+ Network Layer Theophilus Benson Based partly on lecture notes by Rodrigo Fonseca, David Mazi res, Phil Levis, John Jannotti
Todays Lecture Switching (Take II) Ethernet (datagram) Spanning-Tree ATM (Virtual Circuits) Network layer: Internet Protocol (v4) Forwarding Addressing Fragmentation ARP DHCP NATs
Ethernet Switching Hosts come preconfigured with IDs Each host has a MAC-address Network automatically determines routes Flood to discover who is connected.
Drawbacks of Flooding B3 B4 B1 Alice Brige1 A LAN 3 B Brige4 Brige3 A LAN 2 B B A B Bob A Brige5 LAN 4 B5
Drawbacks of Flooding B3 B4 B1 Bob A Alice Brige1 A LAN 3 B Brige4 Brige3 A LAN 2 B B A B Bob A Brige5 LAN 4 B5 Bob A
Drawbacks of Flooding B3 B4 B1 Bob A Alice Brige1 A LAN 3 B Brige4 Brige3 A LAN 2 B B A B Bob A Brige5 LAN 4 B5 Bob A
Drawbacks of Flooding B3 B4 B1 Bob A Alice Brige1 A LAN 3 B Brige4 Brige3 A LAN 2 B B A B Bob A Brige5 LAN 4 B5 Bob A
Drawbacks of Flooding B3 B4 B1 Alice B Alice A Bob A Alice Alice B Brige1 A LAN 3 B Brige4 Brige3 A LAN 2 B B A B Bob A Brige5 LAN 4 B5 Bob A
Drawbacks of Flooding B3 B4 B1 Alice B Alice A Bob A Alice Bob A Bob B Alice B Brige1 A LAN 3 B Brige4 Brige3 A LAN 2 B B A B Bob A Brige5 LAN 4 B5 Bob A
Drawbacks of Flooding Can not deal with loops Can not scale to a large number of devices.
Drawbacks of Flooding Can not deal with loops Solution: Spanning Tree Can not scale to a large number of devices. Solution: VLANs
Drawbacks of Flooding B3 B4 B1 Alice B Alice A Bob A Alice Bob A Bob B Alice B Brige1 A LAN 3 B Brige4 Brige3 A LAN 2 B B A B Bob A Brige5 LAN 4 B5 Bob A
Drawbacks of Flooding B3 B4 B1 Alice B Alice A Bob A Alice Bob A Bob B Alice B Brige1 A LAN 3 B Brige4 Brige3 A LAN 2 B B A B Bob A Brige5 LAN 4 B5 Bob A
Drawbacks of Flooding B3 B4 B1 Alice B Alice A Bob A Alice Bob A Bob B Alice B Brige1 A LAN 3 B Brige4 Brige3 A LAN 2 B B A B Bob A Brige5 LAN 4 B5 Bob A
Drawbacks of Flooding B3 B4 B1 Alice B Alice A Bob A Alice Bob A Bob B Alice B Brige1 A LAN 3 B Brige4 Brige3 A LAN 2 B B A B Bob A Brige5 LAN 4 B5 Bob A
Drawbacks of Flooding Can not deal with loops Solution: Spanning Tree Can not scale to a large number of devices. Solution: VLANs
Spanning-Tree Exchange BPDU messages BPDU = Bridge Protocol Data Unit Discover a routing topology free of loop Eliminates redundancy: wastes extra links root ID cost bridge ID port ID root bridge (what the sender thinks it is) root path cost for sending bridge Identifies sending bridge Identifies the sending port
Building a Spanning Tree: Time 0: Everyone thinks they are root B3 think B3 is Root B1 think B1 is Root B3 0 B3 B4 think B4 is Root B1 0 B1 Alice B4 0 B4 Brige1 A LAN 3 B Brige4 Brige3 A LAN 2 B B A B Bob A Brige5 LAN 4 B5 think B5 is Root B5 0 B5
Building a Spanning Tree: Time 1: Everyone heard from B1. B1 has a lower bridge B1 .. Must be root B3 think B1 is Root B1 think B1 is Root B3 0 B3 B4 think B1 is Root B1 0 B1 Alice B4 0 B4 Brige1 A LAN 3 B Brige4 R Brige3 R A LAN 2 B B R A B Bob A Brige5 LAN 4 B5 think B1 is Root B5 0 B5
Building a Spanning Tree: Time 2: Tell each other B1 is root B3 think B1 is Root B1 think B1 is Root B3 0 B3 B4 think B1 is Root B1 0 B1 Alice 1 B B4 0 B4 1 1 A Brige1 A LAN 3 B Brige4 R Brige3 R A LAN 2 B B R A B Bob A Brige5 LAN 4 B5 think B1 is Root B5 0 B5 1 A
Building a Spanning Tree: Time 3: Discover Duplication Turn off ports. B3 think B1 is Root B1 think B1 is Root B3 0 B3 B4 think B1 is Root B1 0 B1 Alice B1 1 B3 B B4 0 B4 B1 1 B1 B1 1 B4 A Brige1 A LAN 3 B Brige4 R Brige3 R A LAN 2 B B D R A B Bob A Brige5 LAN 4 Professors B5 think B1 is Root B5 0 B5 B1 1 B5 A
The Spanning Tree Brige1 Brige5 Brige4 Brige3 B B
The Spanning Tree Brige1 D Port Type Rules D R Accept & forward flood traffic. Don t forward BDPU LAN 3 Bob LAN 2 D Accept & Forward flood traffic. Forward BDPU R R Brige4 R Brige3 Brige5 B D B LAN 4 TWO WASTED LINKS IN THIS TOPOLOGY Alice Sent packets Packets not sent
Drawbacks of Flooding Can not deal with loops Solution: Spanning Tree Can not scale to a large number of devices. Solution: VLANs
Virtual LANs Alice Brige1 A LAN 3 B Brige4 Brige3 A LAN 2 B B A B Bob A Brige5 LAN 4 Assign switch ports to a VLAN ID (color) Isolate traffic: only same color Trunk links may belong to multiple VLANs Encapsulate packets: add 12-bit VLAN ID Easy to change, no need to rewire
Virtual LANs Alice Brige1 A LAN 3 B Brige4 Brige3 A LAN 2 B B A B Bob A Brige5 LAN 4 Assign switch ports to a VLAN ID (color) Isolate traffic: only same color Trunk links may belong to multiple VLANs Encapsulate packets: add 12-bit VLAN ID Easy to change, no need to rewire
Virtual LANs Alice Brige1 A LAN 3 B Brige4 Brige3 A LAN 2 B B A B Bob A Brige5 LAN 4 Assign switch ports to a VLAN ID (color) Isolate traffic: only same color Trunk links may belong to multiple VLANs Encapsulate packets: add 12-bit VLAN ID Easy to change, no need to rewire
Other Uses for VLANs (Virtual LANs) Finance: 1 Brige1 A LAN 3 B Brige4 Brige3 A LAN 2 B B A B A Finance: 1 Professors Brige5 LAN 4 Company network, A and B departments May not want traffic between the two departments Topology has to mirror physical locations What if employees move between offices?
Generic Switch Architecture Goal: deliver packets from input to output ports Potential performance concerns: Throughput in bytes/second Throughput in packets/second Latency
Shared Memory Switch 1st Generation like a regular PC NIC DMAs packet to memory over I/O bus CPU examines header, sends to destination NIC I/O bus is serious bottleneck For small packets, CPU may be limited too Typically < 0.5 Gbps
Shared Bus Switch 2st Generation NIC has own processor, cache of forwarding table Shared bus, doesn t have to go to main memory Typically limited to bus bandwidth (Cisco 5600 has a 32Gbps bus)
Point to Point Switch 3rd Generation: overcomes single-bus bottleneck Example: Cross-bar switch Any input-output permutation Multiple inputs to same output requires trickery Cisco 12000 series: 60Gbps
Cut through vs. Store and Forward Two approaches to forwarding a packet Receive a full packet, then send to output port Start retransmitting as soon as you know output port, before full packet Cut-through routing can greatly decrease latency Disadvantage Can waste transmission (classic optimistic approach) CRC may be bad If Ethernet collision, may have to send runt packet on output link
Cut through Store and forward
Buffering Buffering of packets can happen at input ports, fabric, and/or output ports Queuing discipline is very important Consider FIFO + input port buffering Only one packet per output port at any time If multiple packets arrive for port 2, they may block packets to other ports that are free Head-of-line blocking: can limit throughput to ~ 58% under some reasonable conditions* 2 Port 1 1 2 Port 2 * For independent, uniform traffic, with same-size frames
Head-of-Line Blocking 2 Port 1 1 2 Port 2 Solution: Virtual Output Queueing Each input port has n FIFO queues, one for each output Switch using matching in a bipartite graph Shown to achieve 100% throughput* *MCKEOWN et al.: ACHIEVING 100% THROUGHPUT IN AN INPUT-QUEUED SWITCH, 1999
Todays Lecture Switching (Take II) Ethernet (datagram) Spanning-Tree ATM (Virtual Circuits) Network layer: Internet Protocol (v4) Forwarding Addressing Fragmentation ARP DHCP NATs
ATM Cells Fixed-size packets 5 bytes header 48 bytes payload If payload smaller than 48B, uses padding If greater than 48B, breaks it
Why small, fixed-length packets? Cons: maximum efficiency 48/53=90.6% Pros: Suitable for high-speed hardware implementation Many switching elements doing the same thing in parallel Reducing priority packet latency Good for QoS Reducing transmission latency
Reduce queuing latency Transmission + propagation + queuing Reducing preemption latency
Why 48 bytes It s from the telephone technology Thought data would be mostly voice A compromise US: 64 bytes Europe: 32 bytes 64+32 = 48 bytes
Virtual paths 24-bit virtual circuit identifiers (VCIs) Discussed in our previous lecture Two-levels of VCIs 8-bit virtual path, 16-bit VCI Virtual paths shared by multiple connections
Todays Lecture Switching (Take II) Ethernet (datagram) Spanning-Tree ATM (Virtual Circuits) Network layer: Internet Protocol (v4) Forwarding Addressing Fragmentation ARP DHCP NATs
Internet Protocol Goal How to connect everybody? New global network or connect existing networks? Glue lower-level networks together: allow packets to be sent between any pair or hosts Wasn t this the goal of switching? Le Theo Net (ATM) Le Duke Net (Token Ring)
Internetworking Challenges Heterogeneity Different addresses Different service models Different allowable packet sizes Scaling Congestion control
How would you design such a protocol? Circuits or packets (datagram)? Predictability Service model Reliability, timing, bandwidth guarantees Any-to-any Finding nodes: naming, routing Maintenance (join, leave, add/remove links, ) Forwarding: message formats
How would you design such a protocol? Circuits or packets (datagram)? Predictability Service model Reliability, timing, bandwidth guarantees Any-to-any Finding nodes: naming, routing Maintenance (join, leave, add/remove links, ) Forwarding: message formats
IPs Decisions Packet switched Unpredictability, statistical multiplexing Service model Lowest common denominator: best effort, connectionless datagram Any-to-any Common message format Separated routing from forwarding Naming: uniform addresses, hierarchical organization Routing: hierarchical, prefix-based (longest prefix matching) Maintenance: delegated, hierarchical
A Bit of History Packet switched networks: Arpanet s IMPs Late 1960 s RFC 1, 1969! Segmentation, framing, routing, reliability, reassembly, primitive flow control Network Control Program (NCP) Provided connections, flow control Assumed reliable network: IMPs Used by programs like telnet, mail, file transfer Wanted to connect multiple networks Not all reliable, different formats, etc
