Networking II: The Link and Network LayersAnnouncementsReview: OSI LevelsSlide 4What is purpose of this layer?Broadcast Networks DetailsPoint-to-point networksPoint-to-Point Networks DiscussionHow to connect routers/machines?Link level IssuesEncodingManchester EncodingFramingExample: HDLCBroadcast Network ArbitrationArbitrationEthernetCSMA/CDCSMASlide 20Slide 21Ethernet’s CSMA/CD (more)Packet SizeEthernet ProblemsAddressing & ARPAddressing & RARPRepeaters and BridgesBackbone BridgeSummaryThe Network LayerSlide 31Slide 32Slide 33Purpose of Network layerWhat does it involve?Network service modelTwo connection modelsVirtual circuits: signaling protocolsVirtual circuit switchingVirtual circuit forwardingVirtual Circuits: DiscussionDatagram networksDatagrams: ForwardingDatagramsDatagrams ForwardingSimple Routing AlgorithmLink State RoutingReliable floodingDiscussion: Link-State RoutingIs our routing algo scalable?Hierarchical AddressingIP has 2-layer addressingIP addressingIP addressing: CIDRInternet Protocol DatagramDatagram PortabilityIP Fragmentation & ReassemblySlide 58Networking II:The Link and Network Layers2Announcements•Prelim II will be Thursday, November 20th, in class•Homework 5 available later today, November 4th•Vote today3Review: OSI Levels•Physical Layer–electrical details of bits on the wire•Data Link Layer–sending “frames” of bits and error detection•Network Layer–routing packets to the destination•Transport Layer–reliable transmission of messages, disassembly/assembly, ordering, retransmission of lost packets•Session Layer–really part of transport, typically Not implemented•Presentation Layer–data representation in the message•Application–high-level protocols (mail, ftp, etc.)4Review: OSI LevelsPresentationTransportNetworkData LinkPhysicalApplicationPresentationTransportNetworkData LinkPhysicalApplicationNode ANode BNetworkSessionSession5What is purpose of this layer?•Invoke Physical Layer–Physically encode bits on the wire•Link = pipe to send information–E.g. point to point or broadcast•Can be built out of:–Twisted pair, coaxial cable, optical fiber, radio waves, etc•Links should only be able to send data–Could corrupt, lose, reorder, duplicate, (fail in other ways)6Broadcast Networks Details•Delivery: When you broadcast a packet, how does a receiver know who it is for? (packet goes to everyone!)–Put header on front of packet: [ Destination | Packet ]–Everyone gets packet, discards if not the target–In Ethernet, this check is done in hardware•No OS interrupt if not for particular destination–This is layering: we’re going to build complex network protocols by layering on top of the packetHeader(Dest:2)Body(Data)MessageID:1(ignore)ID:2(receive)ID:4(ignore)ID:3(sender)7Point-to-point networks•Why have a shared broadcast medium? Why not simplify and only have point-to-point links + routers/switches?–Didn’t used to be cost-effective–Now, easy to make high-speed switches and routers that can forward packets from a sender to a receiver.•Point-to-point network: a network in which every physical wire is connected to only two computers•Switch: a bridge that transforms a shared-bus configuration into a point-to-point network.•Router: a device that acts as a junction between two networks to transfer data packets among them.RouterInternetSwitch8Point-to-Point Networks Discussion•Advantages:–Higher link performance•Can drive point-to-point link faster than broadcast link since less capacitance/less echoes (from impedance mismatches)–Greater aggregate bandwidth than broadcast link•Can have multiple senders at once–Can add capacity incrementally•Add more links/switches to get more capacity–Better fault tolerance (as in the Internet)–Lower Latency•No arbitration to send, although need buffer in the switch•Disadvantages:–More expensive than having everyone share broadcast link–However, technology costs now much cheaper •Examples–ATM (asynchronous transfer mode)•The first commercial point-to-point LAN•Inspiration taken from telephone network–Switched Ethernet•Same packet format and signaling as broadcast Ethernet, but only two machines on each ethernet.9How to connect routers/machines?•WAN/Router Connections–Commercial:•T1 (1.5 Mbps), T3 (44 Mbps)•OC1 (51 Mbps), OC3 (155 Mbps)•ISDN (64 Kbps)•Frame Relay (1-100 Mbps, usually 1.5 Mbps)•ATM (some Gbps)–To your home:•DSL•Cable•Local Area:–Ethernet: IEEE 802.3 (10 Mbps, 100 Mbps, 1 Gbps)–Wireless: IEEE 802.11 b/g/a (11 Mbps, 22 Mbps, 54 Mbps)10Link level Issues•Encoding: map bits to analog signals•Framing: Group bits into frames (packets)•Arbitration: multiple senders, one resource•Addressing: multiple receivers, one wire11Encoding•Map 1s and 0s to electric signals•Simple scheme: Non-Return to Zero (NRZ)–0 = low voltage, 1 = high voltage•Problems:–How to tell an error? When jammed? When is bus idle?–When to sample? Clock recovery is difficult.•Idea: Recover clock using encoding transitions1 0 1 1 012Manchester Encoding•Used by Ethernet•Idea: Map 0 to low-to-high transition, 1 to high-to-low•Plusses: can detect dead-link, can recover clock•Bad: reduce bandwidth, i.e. bit rate = ½ baud rate–If wire can do X transition per second?011013Framing•Why send packets?–Error control•How do you know when to stop reading?–Sentinel approach: send start and end sequence–For example, if sentinel is 11111–11111 00101001111100 11111 10101001 11111 010011 11111–What if sentinel appears in the data?•map sentinel to something else, receiver maps it back–Bit stuffing14Example: HDLC•High-Level Data Link Control (HLDC)–Data link layer protocol developed by the ISO•Same sentinel for begin and end: 0111 1110•packet format:•Bit stuffing–Sender: If 5 1s then insert a 0–Receiver: if 5 1s followed by a 0, remove 0•Else read next bit•Packet size now depends on the contents 0111 1110 header data CRC 0111 11100111 1110 0111 1101 00111 1101 0 0111 111015Broadcast Network Arbitration•Arbitration: Act of negotiating use of shared medium–What if two senders try to broadcast at same time?–Concurrent activity but can’t use shared memory to coordinate! •Aloha network (70’s): packet radio within Hawaii–Blind broadcast, with checksum at end of packet. If received correctly