Page 1Peter A. Steenkiste, SCS, CMU1Lecture 7Datalink – Ethernet, HomePeter SteenkisteSchool of Computer ScienceDepartment of Electrical and Computer EngineeringCarnegie Mellon University15-441 Networking, Spring 2004http://www.cs.cmu.edu/~prs/15-441Peter A. Steenkiste, SCS, CMU2Datalink Layer Architecturesl Packet forwarding.l Error and flow control.l Media access control.l Scalability.Page 2Peter A. Steenkiste, SCS, CMU3Multiple Access Protocolsl Prevent two or more nodes from transmitting at the same time over a broadcast channel.» If they do, we have a collision, and receivers will not be able to interpret the signallSeveral classes of multiple access protocols.» Partitioning the channel, e.g. frequency-division or time division multiplexing– With fixed partitioning of bandwidth – not flexible» Taking turns, e.g. token-based, reservation-based protocols, polling based» Contention based protocols, e.g. Aloha, EthernetPeter A. Steenkiste, SCS, CMU4Today’s Lecturel LAN technologies: Ethernet.l Bridges and LAN switches.l Connectivity to the home.Page 3Peter A. Steenkiste, SCS, CMU5Alohal Nodes sends the message when it has data to send.l If it receives an ack, it considers the transmission completed, otherwise it retransmits after a random delay.l Simple, distributed protocol, but not very efficient» 18% maximum utilizationl Slotted Aloha: more efficient.» Reduces chances of collision» 37% maximum utilizationCentralComputerPeter A. Steenkiste, SCS, CMU6802.3 EthernetBroadcast technologyl Carrier-sense multiple access with collision detection (CSMA/CD). » MA = multiple access» CS = carrier sense» CD = collision detectionlBase Ethernet standard is 10 Mbs.» Original design was ~2 Mbs» Faster versions discussed laterhost host host hosthost host host hostHubPage 4Peter A. Steenkiste, SCS, CMU7Contention-Based Protocoll Goal: share the communication channel among multiple hosts sharing it.l Problem: how to arbitrate between the connected hosts.l Desired properties:» High bandwidth utilization» Avoid starvation, achieve fairness» Simple solutionlIdea: access the channel in a random way -when collisions occur, recover.» Collision: two or more nodes transmitting at the same timePeter A. Steenkiste, SCS, CMU8CSMA/CD Algorithml Sense for carrier.l If carrier present, wait until carrier ends.» Sending would force a collision and waste timelSend packet and sense for collision.l If no collision detected, consider packet delivered.l Otherwise, abort immediately, perform “exponential back off” and send packet again.» Start to send at a random time picked from an interval» Length of the interval increases with every retransmissionPage 5Peter A. Steenkiste, SCS, CMU9Collision DetectionTimeABCPeter A. Steenkiste, SCS, CMU10Collision Detection: Implicationsl All nodes must be able to detect the collision.» Any node can be senderl The implication is that either we must have a short wires, or long packets.» Or a combination of bothl Can calculate length/distance based on transmission rate and propagation speed.» Messy: propagation speed is media-dependent, low-level protocol details, ..» Minimum packet size is 64 bytes– Cable length ~256 bit times» Example: maximum coax cable length is 2.5 kmABCPage 6Peter A. Steenkiste, SCS, CMU11CSMA/CD: Some Detailsl Successive frames are separated by an “inter-frame” gap.» Nodes must switch from “send” to “receive” mode» Set to 9.6 µsec or 96 bit timesl When a sender detects a collision, it sends a “jam signal”.» Make sure that all nodes are aware of the collision» Length of the jam signal is 32 bit timeslExponential backoff operates in multiples of 512 bit times.» Longer than a roundtrip time» Guarantees that nodes that back off longer will notice the earlier retransmission before starting to sendPeter A. Steenkiste, SCS, CMU12Why a Minimum Packet Sizel Give a host enough time to detect a collision.l In Ethernet, the minimum packet size is 64 bytes.» 18 bytes of header and 46 data bytes» If the host has less than 46 bytes to send, the adaptor (pads) bytes to increase the length to 46 byteslWhat is the relationship between the minimum packet size and the size of LAN?l How did they pick the minimum packet size?LAN = (min frame size) * light speed / (2 * bandwidth)Page 7Peter A. Steenkiste, SCS, CMU13Ethernet Frame Formatl Preamble marks the beginning of the frame.» Also provides clock synchronizationl Source and destination are 48 bit IEEE MAC addresses.» Flat address space» Hardwired into the network interfacel Type field is a demultiplexing field.» What network layer (layer 3) should receive this packet?» Is actually a length field in the 802.3 standardl CRC for error checking.Preamble Type PadDest Source Data CRC86 62 4Peter A. Steenkiste, SCS, CMU14Ethernet Physical Layerl 10Base2 standard based on thin coax.» Thick coax no longer used» Nodes are connected using thin coax cables and “T” connectors in a bus topologyl 10-BaseT uses twisted pair and hubs.» Hub acts as a concentratorl The two designs have the same protocol properties.» Key: electrical connectivity between all nodes» Deployment is differenthost host host hosthost host host hostHubHostPage 8Peter A. Steenkiste, SCS, CMU15Traditional IEEE 802 Networks:MAC in the LAN and MANl Ethernet defined as IEEE 802.3.l The IEEE 802.* set of standards defines a common framing and addressing format for LAN protocols.» Simplifies interoperability» Addresses are 48 bit strings, with no structurel 802.3 (Ethernet)l 802.4 (Token bus)l 802.5 (Token ring)l 802.6 (Distributed queue dual bus)l 802.11 (Wireless LAN)l 802.14 (Cable Modem)l 802.15 (Wireless Personal Area networks)l 802.16 (Broadband wireless access)Peter A. Steenkiste, SCS, CMU16LAN Propertiesl Exploit physical proximity.» Often a limitation on the physical distance » E.g. to detect collisions in a contention based network» E.g. to limit the overhead introduced by token passinglRelies on single administrative control and some level of trust.» Broadcasting packets to everybody and hoping everybody (other than the receiver) will ignore the packet» Token-based protocols: everybody plays by the ruleslBroadcast: nodes can send messages that can be heard by all nodes on the network.» Almost essential for network administration» Can also be used for applications, e.g. video conferencinglBut broadcast fundamentally does not scale.Page 9Peter A. Steenkiste, SCS, CMU17How Do We Go
View Full Document
Unlocking...