计算机网络分层和端到端通信的讨论

1 . 11/12/17 Why networking in a systems class? • Many of the most interesting systems today rely on the network. Networking: Layering and • Cellphone games, Siri/Alexa/…, Large data processing, MMORPGs, etc. End to End Argument • Important to understand networks. • Note: This lecture is insufficient for this purpose. Aurojit Panda [Slides heavily borrowed from Ion + Others] • The Internet is a very large system. • Survived for a few decades now. • Scaled to 47% of world population, a variety of applications, and all sorts of connections. • How? What is the Problem? Solution E-mail Browsers (http/https) ssh iTunes (DMAP) Many • Two architectural principles: Skype ftp BitTorrent Gopher applications • Layering: abstraction in another guise. • End-to-end principle: architectural on where functionality is placed. connected over • Note: these principles are not absolute. Disco Ball + • Long running debates on what both of these mean and how implemented. Ethernet Fiber Optics Cable WiFi Satellite Cellular Radio Telephone Lasers many • How they are used and what they mean is often dictated by performance. networks 1 

2 . 11/12/17 Preliminaries: Participants Preliminaries: Identity/Names Process Process TCP/UDP port (16 bit) assigned by OS. Kernel Kernel IP address (32/64 bit) network assigned. Network NIC NIC MAC addr (48 bits) burnt in hardware. Preliminaries: Goals • Delivery: Packets from Alice reach Bob • Alice and Bob can be in the same room, or in different countries. • Reliability: Packets from Alice reach Bob even when things go wrong. • For simplicity physical hardware provides best effort service. Layering • Software or protocols hide temporary errors from users. • Congestion Control: Allow different users to share the network. • Flow Control: Deal with bounded buffers on devices in the network. 2 

3 . 11/12/17 What is the Problem? How to make networked applications? E-mail Browsers (http/https) ssh iTunes (DMAP) Many • Application per physical network type doesn’t work out. Skype ftp BitTorrent Gopher applications • Too much work for developers. • Fragments the world into different types of networks. connected over • Internet interconnects networks. How? Disco Ball + • Answer through abstraction. Ethernet Fiber Optics Cable WiFi Satellite Cellular Radio Telephone Lasers many networks Layering Layering: Why? • Partition system into layers (abstractions). • Assumptions and interfaces are well specified. • Each layer expects some functionality to be implemented by layer below. • Can swap out one layer for another assuming interfaces remain constant. • Note: My layers grow upwards in this (and subsequent slide). • In networking this means: • No assumption on how functionality is implemented. • Applications assume delivery, reliability, congestion control, flow control, etc. • Each layer provides some functionality to layer above. • Application logic assumes these and is independent of how these are implemented. • Can make assumptions on how functionality will be used and restrict interface. • User/kernel gets to choose congestion control or flow control algorithms. • Network operator/owner gets to choose how to route and deliver packets. • Layers interact through some agreed upon interface. • Changing one layer does not require changes to any of the other layers. • Defined by operating system (e.g., drivers), standardization body, etc. 3 

4 . 11/12/17 Layering in Networking: OSI Model Layering in Networking • Open Systems Interconnection (OSI) model (1983/4) Application • Going to analyze three questions for each layer • ISO + CCITT developed this model in 1983-4 Presentation • Service: What functionality is implemented by the layer? • Defined seven layers. Session • Interface: How does the next layer access this functionality? • TCP/IP Transport Control Protocol/Internet Protocol Transport • Only considers five layers Network • Protocol: What messages does layer send over the network? Datalink • Rules and packet formats expected by this layer at each node. • Presentation and session functionality implemented by application. Physical • How is the service implemented between machines in the network. Application Application Layer 1: Physical Layer Present. Layer 1: Physical Layer Present. Session Session Transport Transport Network Network Datalink Datalink Physical Physical • Service: Send bits over some physical medium. • Could be electrical signals, optical signals, radio signals, … Datalink Datalink layer layer • Interface: Send and receive streams of bits. Transmission medium • The precise interface depends on the operating system (or library) and NIC. Physical Physical Layer 101010100110101110 101010100110101110 Layer • Protocol: Decides how data is encoded in the medium. • Code used for encoding bits, detecting or correcting physical errors, etc. 4 

5 . 11/12/17 Application Application Present. Present. Session Session Layer 2: Datalink Layer Transport Network Layer 2: Datalink Layer Transport Network Datalink Datalink Physical • Each frame has a header Physical • Service: Allow physically connected devices to exchange data frames • Specifies source and a destination MAC address • Exchange messages when connected to the same wired or wireless link. • MAC address is 48 bits, assigned by NIC manufacturer. • MAC Dest. Address • Interface: Send and receive frames addressed to a device. Network • MAC Src. Address Network Layer Layer •… • Protocols: Several protocols available, depends on physical media. Datalink Frame Frame Datalink Frame Payload Frame Payload • Examples: Ethernet, 802.11 (wireless), Point-to-Point (PPP), etc. Layer Hdr. Hdr. Layer Physical Physical Layer 101010100110101110 101010100110101110 Layer Application Application Present. Present. Layer 2: Datalink Layer Session Transport Network Layer 2: Sharing the Link Session Transport Network Datalink Datalink • Notice there are a variety of datalink layer protocols. Physical • Problem: Multiple devices share a single link. Physical • Some of these depend on the physical link connecting machines. • All devices on the same link hear any message that is transmitted. • Why depend on physical links? • If two devices transmit simultaneously message gets garbled. • Because some physical links connect exactly two devices. Called point-to-point links. • How to avoid collisions, i.e., take turn speaking on shared media? • Example: Almost all wired networks today. • Three solutions • But others are shared by many different devices. Called broadcast channels. • Partition the channel. • Example: WiFi (radio frequency shared by all users), old ethernet (10BASE-2), etc. • Take turns • When sharing physical links need to decide who gets to send data. • Random access: Detect when network is unused and try to transmit. 5 

6 . 11/12/17 Application Application Present. Present. Layer 2: Partitioning Channel Layer 2: Taking Turns Session Session Transport Transport Network Network Datalink Datalink • Split a single channel into N channels each with 1/N bandwidth. Physical • Pass a token around between active devices. Physical • Each device gets one of the channels. • Devices can send data if and only if it has token. • How to split channels • Device passes token along if no data to send. • Frequency division (FDMA), time division (TDMA), code division (CDMA) • Example: Token ring. • Problem: Wasted bandwidth when a device has no data to send. • Pros: More efficient, less wasted bandwidth. • No one can use unused bandwidth. • Cons: Susceptible to failure, what happens when token gets lost. Application Application Present. Present. Layer 2: Random Access Session Transport Network Layer 2: Sharing the Link Session Transport Network Datalink Datalink • Three steps to get multiple nodes to access link Physical • Looked at three solutions Physical • Carrier Sense (CS): First check if someone else is using the link. • Partitioning channel: FDMA/TDMA/CDMA. Used in some cellular networks. • If yes then wait until they are done, otherwise try and use the link. • Collison Detection (CD): When transmitting detect if someone else uses the link. • Taking Turns: Token ring. Popular for local networks in the 1980s and 1990s. • If collision is detected then stop transmitting. • Random Access: CSMA/CD. Used by ethernet. • Random Wait: When collision is detected wait for some random time before retry. • Other solutions exist and are used in other contexts. • Example: CSMA/CD used by ethernet. • Largely constructed from similar primitives. • Pros: Efficient at low load, not susceptible to failure. • Example: CSMA/CD in wireless networks. • Cons: High overhead during collision. 6 

7 . 11/12/17 Application Present. Session Layer 2: Local Area Network Layer 3: (Inter)Network Layer Transport Network • A set of end hosts which can communicate with each other over layer 2. Datalink Physical • Service: Deliver packet to a specified network address. • Implemented using both broadcast channels and point-to-point links. • Network address might refer to host on another data link layer. • When using point-to-point links end hosts connected using a switch. MAC Addr: D • Connect multiple layer 2 networks together. MAC Addr: B MAC Addr: A MAC Addr: B MAC Addr: C • Interface: Send packets to a remote network address. B Switch MAC Addr: C • Receive packets addressed to computer. MAC Addr: A • Protocol: Internet Protocol (IP). Define network addresses, forwarding. B B Application Application Layer 3: (Inter)Network Layer Present. Present. Session Layer 3: (Inter)Network Layer Session Transport Transport Network Network Datalink Datalink Physical Physical • End hosts are identified by IP addresses Transport • IP Dest. Address Transport Layer • IP Src. Address Layer • Each address is 32 (IPv4) or 128 (IPv6) bits. •… Network Network • Addresses are ”globally unique”. Layer Net. Hdr. Net. Paylaod Net. Hdr. Net. Paylaod Layer Frame Payload • Uniqueness necessary to ensure that end hosts all over the world can talk. Datalink Frame Net. Frame Net. Datalink Net. Payload Net. Payload Layer Hdr. Hdr. Hdr. Hdr. Layer • Assigned by network operator • Either statically configured or (more likely) configured when computer connects. Physical Physical Layer 101010100110101110 101010100110101110 Layer 7 

8 . 11/12/17 Application Application Present. Present. Layer 3: Where Used? Session Transport Layer 3: Where Used? Session Transport Network Network Datalink Datalink Physical Physical • Used to connect several layer 2 (LANs) together. • When connecting a large organization (e.g., Berkeley’s network) Host A R4 Host B (IP A) • When connection a geographically spread out network (e.g., AT&T’s network). (IP B) R2 • When connecting multiple networks together (e.g., the Internet). R3 • How are LANs interconnected? Through routers. R1 • Routers bridge LANs together. Layer 3: How Impelemented? Routers Application Present. Layer 3: Packet Forwarding Application Present. Session Session Transport • How it works: Transport Network Network Datalink Datalink • Forward each packet on a link. Physical • Router waits to receive the entire packet (store and forward). Physical • Once received uses destination address to index forwarding table. • Decides how to forward a packet depending on the forwarding table. • Forwards packet along output port specified by forwarding table. incoming links Router outgoing links Memory Host A R4 Host B (IP A) IP B (IP B) R2 R3 8 

9 . 11/12/17 Application Application Present. Present. Layer 3: Why use IP addresses? Layer 3: Why use IP addresses? Session Session Transport Transport Network Network Datalink Datalink Physical Physical • Layer 2 used MAC address, why not use that at Layer 3? • Networks assign IP addresses. As a result addresses identify routes. • Scalability: IP addresses are hierarchical, MAC addresses are not. • For example: any IP address of the form 128.32.xxx.xxx belongs to Berkeley. • Any IP address of the form 128.30.xxx.xxx belongs to MIT’s CS Department. • MAC addresses are assigned by a device vendor • Uniquely identifies your hardware. Invariant as you move. • Can route traffic to 65535 Berkeley hosts by just using 16 bits of space. • Same for MIT. • IP addresses change depending on where you are connected. • For example, you get a different IP address at home vs when at Berkeley. • By contrast: MAC address varies by who manufactured computer. • Need an entry per end host to route packets. Does not scale globally. Application Application Present. Present. Session Layer 3: Internet Protocol (IP) Layer 4: Transport Layer Session Transport Transport Network Network Datalink Datalink Physical Physical • Layer 3 on the Internet. • Service: End-to-end communication between processes. • Demultiplex communication between processes running on the same end host. • Provides “best-effort” packet delivery. • Might implement: reliability, congestion control, timing, etc. • Will try its best to deliver packets to the destination. • Interface: • Packets might be lost, or corrupted. • Send message to a process. • Makes no ordering guarantees. Packets can be arbitrarily reordered. • Establish connection with a process. • Receive messages sent to a process. • Protocol: TCP and UDP: define port numbers for demultiplexing processes. 9 

10 . 11/12/17 Application Application Present. Present. Session Session Layer 4: Transport Layer Transport Network Layer 4: Port Numbers Transport Network Datalink Datalink Physical • 16-bit numbers carried in the transport layer header. Physical Transport Trans. Trans. Transport Layer Hdr. Data Hdr. Data Layer • Identifies what process sent/should receive a packet. Network Net. Trans. Net. Trans. Network • A port is only meaningful at a particular end host. Data Data Layer Hdr. Hdr. Hdr. Hdr. Layer • Assigned by the kernel (network stack). Datalink Frame Net. Trans. Frame Net. Trans. Datalink Layer Hdr. Hdr. Hdr. Data Hdr. Hdr. Hdr. Data Layer • When sending messages need to know port to use to reach a process. • Client learns this out-of-band. Many services have known port (e.g., 80 is http). Physical Physical Layer 101010100110101110 101010100110101110 Layer • Server can learn port from the initial request: all packets carry source port. Application Application Present. Present. Session Session Layer 4: Protocols Transport Network Layer 7: Application Transport Network Datalink Datalink Physical Physical • UDP: Datagram service • Send best effort messages over IP. Single IP packet with ports specified. • Service: depends on application: e-mail, HTTP, etc. • TCP: Reliable, in-order stream • Interface: depends on application: some UI, some API, etc. • Connection oriented: one process connects to another. • Protocol: depends on application: HTTP, SMTP, … • Protocol is responsible for discarding corrupted packets. • Protocol retransmits any lost packets. • Performance congestion control and flow control. 10 

11 . 11/12/17 Application Present. Session Layer 7: Application Transport Network Network Layer Summary Datalink Application Application Physical Application Application Layer Data Data Layer Transport Transport Network Network Network Transport Trans. Trans. Transport Datalink Datalink Datalink Data Data Layer Hdr. Hdr. Layer Physical Physical Physical Network Net. Trans. Net. Trans. Network Host A Router Host B Data Data Layer Hdr. Hdr. Hdr. Hdr. Layer • Physical, Datalink and Network layer are implemented on all devices. Datalink Datalink Layer Frame Hdr. Net. Hdr. Trans. Hdr. Data Frame Hdr. Net. Hdr. Trans. Hdr. Data Layer • Application and transport are implemented only on hosts. • Logically each layer interacts with the corresponding layer on other devices Physical Physical Layer 101010100110101110 101010100110101110 Layer Physical Communication Application Application Transport Transport Network Network Network Datalink Datalink Datalink Physical Physical Physical Break Host A Router Host B • When sent packets go down the layers until they reach the physical layer. • When received packets go up the layers until processed. 11 

12 . 11/12/17 Back to the Beginning How Does the Internet Solve This? • Chose a single “narrow waist” HTTP, e-mail, … E-mail Browsers (http/https) ssh iTunes (DMAP) Many • Everyone agreed on IP as interconnection protocol. TCP, UDP, SCTP, … Skype ftp BitTorrent Gopher applications • Everything else could vary. connected over • Responsible for Internet’s success today. IP • Usable in planes, space station, rural areas, etc. Disco Ball + • Usable by a wide variety of applications. Ethernet Fiber Optics Cable WiFi Satellite Cellular Radio Telephone Lasers many Ethernet, 802.11, .. • Was it the right layer to standardize? networks WiFi, Optical, Radio, Layering: A Critique • Abstraction and indirection are the two hammers we use to solve problems • Except for the problems introduced by these approaches. • Layering can hurt performance if implemented naively. • Information hiding makes it hard to implement some protocols. End to End Principle • Header overheads. • Figuring out if this set of layers is even correct. For example where does TLS fit? • Reality: Layering is a powerful design tool, but not a silver bullet. 12 

13 . 11/12/17 End-to-End: Origins End-to-End: Example • End-to-End Arguments in System Design: Saltzer, Reed, Clark 1981 Alice Disney • Design principle for placement of functions in distributed computer systems. • Question from the early days of the Internet • What should the network implement to support an application? • Original challenge: Achieving reliability from an unreliable network. • How does this support impact other applications? • What services should the application provide? • Links can only be so reliable: things fail. • E2E is widely considered to be the foundation of how the Internet is designed. • How can Alice reliably download Star Wars Ep VIII from Disney? • Everyone agrees it is a good idea, people often disagree on what the idea states. End-to-End: Example End-to-End: Example Alice p p Disney Alice Disney p p p p pkt p p pkt pkt • Problems when downloading file • Hop-by-Hop reliability: Each router implements reliability mechanism. • Assume that when going through a link packet can be lost with probability p. • Keep sending packet until other router receives the packet. • How to make sure that file is eventually delivered? • End-to-End reliability: The computers implement reliability. • Two options: Hop by hop reliability, end to end reliability. • Keep sending packet until other end-host receives packet. 13 

14 . 11/12/17 End-to-End: Example End-to-End Principle • Implement functionality as high up in the stack as possible. Alice Disney • Example: Do not implement encryption in the kernel, do it at application level. • Example: No reliability or ordering in network, do it in transport layer. p p • Otherwise: might affect other applications who do not require functionality. • Which is better? • Important exception: Performance. • Observe that end-hosts need to implement reliability: last hop can loose packets. • Implement functionality lower down if necessary for performance. • Hop-by-hop reliability adds overheads even when no reliability is required. • Note: E2E is an important design principle, but not gospel. • When probability p is low, doing it at end hosts is good. • Can almost always take the performance exception. • Chance that a packet is lost is only slightly higher than when you do hop by hop. • A reasonable interpretation: Be cognizant when adding functionality to lower layers. End-to-End: Exception Summary • The Internet is one of the largest real systems. Alice Disney • Survived several decades, exponential growth, etc. with very few changes. • It just works, mostly. • Switching to wireless (from wired) medium increases loss probability. • Principles that helped: Layering, End to End • As a result most wireless protocols today support hop-by-hop reliability. • Does this violate end-to-end? • Does it matter? 14 

15 . 11/12/17 Summary: Layering Summary: End to End Principle • Abstractions that allow networks to be modularized. • Implement functionality as high up in the stack as possible. • Can change lower layers of the network without affecting application. • Avoid placing functionality in the network. • Can change applications without impacting other layers of the network. • Enables networks to support a wide range of application requirements. • Internet today has five layers: • Not an absolute principle: e.g., performance is often an exception. • Physical Layer: Send bits on a wire, over the radio, etc. • Fine to implement functionality in lower layer assuming: • Datalink Layer: Connect physically linked devices. • Higher layers don’t need to replicate functionality. • Network: Connect end hosts over a WAN or across the Internet. • Leads to improved performance. • Transport: Connect two processes across a network. • Does not place an impedement to other uses of the system. • Application: Implement interesting features that lead people to use the network. 15