CSE 489 Week 2 Notes
CSE 489 Week 2 Notes CSE 489
Popular in Modern Networking Concepts
Popular in Computer Science and Engineering
verified elite notetaker
verified elite notetaker
Samantha Jo Butterfield
verified elite notetaker
verified elite notetaker
verified elite notetaker
Samantha Jo Butterfield
verified elite notetaker
This 14 page Class Notes was uploaded by Winnie Liang on Sunday February 7, 2016. The Class Notes belongs to CSE 489 at University at Buffalo taught by Dimitrios Koutsonikolas in Spring 2016. Since its upload, it has received 31 views. For similar materials see Modern Networking Concepts in Computer Science and Engineering at University at Buffalo.
Reviews for CSE 489 Week 2 Notes
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/07/16
02/07/2016 ▯ ▯ ▯ 2/2/16 Lecture ▯ ▯ Internet structure: network of networks ▯ - end systems connect to Internet via access ISP’s (Internet Service Providers) Residential, company and university ISPs ▯ - Access ISPs in turn must be interconnected so that an two hosts can send packs to each other ▯ - Resulting network of networks is very complex Evolution was driven by economics and national policies ▯ ▯ Question: given millions of access ISPs, how to connect them together? ▯ - connect each access ISP to each other directly: doesn’t scale: O(N^2) connections – NOT VIABLE OPTION ▯ - connect each access ISP to a global transit ISP. Customer and provider ISPs have economic agreement. But if one global ISP is viable business, there will be competitors which must be interconnected (peering relationships amongst competitors and customer relationships) Internet exchange point (IXP) – from 3 party companies that charge two other ISPs for making relationships. ▯ - and regional networks may arise to connect access nets to ISPS ▯ - and content provider networks (eg. Google, Microsoft, Akamai) may run their own network, to bring services, content close to end users (- close to access ISP (school, homes) as much as possible so they don’t have to pay for IXP to make relations ▯ ▯ Hierarchy: ▯ Tier 1 ISP, Tier 1 ISP, Google ▯ IXP IXP IXP ▯ Regional ISP Regional ISP ▯ access ISP access ISP access ISP access ISP ▯ ▯ - at top level:small # of well connected large networks ▯ ▯ Tier 1 ISPS: commercial ISPs (Level 3, Sprint, AT&T, NTT), national international coverage ▯ - content provider network (eg. Google) private network that covers its data centers to Internet ▯ ▯ Tier 2 ISPs: smaller (regional0 ISPs ▯ - connect to one or more tier-1 (provider) ISPs each tier-1 has many tier-2 customer nets tier 2 pays tier 1 provider ▯ - tier- 2 nets sometimes peer directly with each other ▯ ▯ Tier 3 ISPS, local ISPs ▯ - customer of tier 1 or tier 2 network last hop (“Access”) network (closest to end systems) ▯ ▯ 1.5 delay, loss, throughput in networks ▯ ▯ How do loss and delay occur? ▯ - packets queue in router buffers packet arrival rate to link (temporarily) exceeds output link capacity packets queue, wait for turn congestion caused delays - packets arrived would drop, packets in queue will be delayed ▯ Four sources of packet delay ▯ Dnodal = Dproc + Dqueue + Dtrans + Dprop ▯ - Dproc: nodal processing (**typically a few microsecs or less) Check bit errors Determine output link Typically <msec IF not mentioned in question, it is usually a 0 The time required to examine the packet’s header and determine where to direct the packet is part of the processing delay. After this nodal processing, the router directs the packet to the queue that precedes the link to router B. ▯ - Dqueue: queueing delay (**depends on congestion) time waiting at output link for transmission depends on congestion level of router If the queue is empty and no other packet is currently being transmitted, then our packet’s queuing delay will be zero. On the other hand, if the traffic is heavy and many other packets are also waiting to be transmitted, the queuing delay will be long ▯ - Dtrans: transmission delay (**L/R significant for low speed links) L: packet length (bits) R: Link bandwidth (bps) Dtrans = L/R (packet length / link bandwidth) This is the amount of time required to push (that is, transmit) all of the packet’s bits into the link. ▯ - Dprop: propagation delay ( = d/s, a few microsecs to hundreds of msecs) d: length of physical link s: propagation speed in medium (~3 x 10^8 m/sec) dprop = d/s (one bit to travel over the link – depends on length of LINK) Once a bit is pushed into the link, it needs to propagate to router B. The time required to propagate from the beginning of the link to router B is the propagation delay. The propagation delay is the distance between two routers divided by the propagation speed. ▯ Dtrans and Dprop are very different – don’t confuse these two ▯ ▯ ▯ ▯ Queueing delay (revisited) ▯ - R: link bandwidth (bits/sec) ▯ - L: packet length (bits) ▯ - a: average packet arrival rate (packets/sec) ▯ ▯ let a denote the average rate at which packets arrive at the queue (a is in units of packets/sec). Recall that R is the transmission rate; that is, it is the rate (in bits/sec) at which bits are pushed out of the queue. Also suppose, for simplicity, that all packets consist of L bits. Then the average rate at which bits arrive at the queue is La bits/sec. Finally, assume that the queue is very big, so that it can hold essentially an infinite number of bits. The ratio La/R, called the traffic intensity, often plays an important role in estimating the extent of the queuing delay. ▯ ▯ ▯ Traffic intensity (bits per second) – average queueing delay ▯ - La/R ~ 0:avg. queueing delay small ▯ - La/R - >1:avg queueing delay avg ▯ - La/R > 1: more “work” arriving than can be serviced, average delay infinite ▯ ▯ “Real Internet delays and routes ▯ - What do “real” internet delay & loss look like? ▯ - traceroute program: provides delay measurement from source to router along end-end Internet path towards destination. For all i: sends three packets that will reach router i on path towards destination router i will return packets to sender sender times interval between transmission and reply. ▯ - send 3 packets / probes to be safer because you want to take the avg, out of the 4 delays, one’s constant ▯ Look at traceroute example: shows 3 delay measurements from the 3 packets ▯ Trans-oceanic link when the delays jumped ▯ ▯ Packet loss ▯ - queue (aka buffer) preceding link in buffer has finite capacity ▯ - packet arriving to full queue dropped (aka lost) ▯ - lost packet may be transmitted by previous node, by source end system, or not at all ▯ Throughput ▯ - throughput: rate(bits/time unit) at which bits transferred between sender/receiver instantaneous: rate at given point in time average: rate over longer period of time ▯ - Rs < Rc What is average end-end throughput? Thinner link to wider link - Rs bits/sec ▯ - Rs > Rc What is average end-end throughput? Wider link to thinner link (congestions)– Rc bits/sec ▯ bottleneck link – link on end-end path that constrains end-end throughput ▯ Throughput: internet scenario ▯ - per-connection end-end throughput: min(Rc, Rs, R/10 – one-tenth of R) ▯ - in practice: Rc or Rs is often bottleneck ▯ 10 connections (fairly) share backbone bottleneck link R bits/sec ▯ ▯ Delay X Bandwidth ▯ - We think the channel between a pair of processes as a pipe ▯ - Propagation delay is the length of the pipe and bandwidth is the width of the pipe ▯ - Delay-bandwidth product Maximum number of bits that can be in the link ▯ - Length of a bit Length of link/bandwidth-delay product ▯ Bandwidth – width/circumference of pipe ▯ Delay – length of pipe ▯ Network as a pipeline ▯ Pipeline request ▯ ▯ Delay vs. Bandwidth ▯ - Relative importance of bandwidth and delay depends on application For large file transfer, bandwidth is critical For small messages (HTTP, NFS, etc), delay is critical Variance in delay (jitter) can also affect some applications (eg. Audio/video conferencing) ▯ ▯ MB vs Mbps or How big is a Mega? ▯ - Network bandwidth (in Mbps) Governed by the speed of the clock that paces the transmission of the bits A clock running at 10 MHz transmits bits at 10 Mbps Here mega = 10^6, kilo = 10^3 ▯ - A message we want to transmit (in MB) Stored in computer’s memory Here Mega = 2^20, Kilo = 2^10 ▯ - Example: a 32 MB message is transmitted over a 10 Mbps link 32 * 2^20 * bits transmitted at a rate of 10 * 10^6 bits per second ▯ - Good news: It is OK to approximate Error less than 5% ▯ ▯ ▯ 2/4/16 Lecture ▯ ▯ Roadmap: Protocol “layers” ▯ - Networks are complex, with many “pieces”: hosts routers links of various media applications protocols hardware, software ▯ How to organize networks? ▯ Solution: Modularization (Layering) ▯ - key idea in computer science ▯ - To simplify network design complexity Organize protocols and hardware/software implementing protocols in layers Upper layers use services provided by lower layers The protocol layers form a protocol stack (protocol suite, protocol architecture) ▯ What does layering offer? ▯ - Dealing with complex systems (eg. Big C/C++ programs) Need structured, modular design for easy maintenance (layers = .c files) Layer n uses the services provided by layer n-1 (eg. Error/ flow control, connection set up) Change of implementation of layer’s service transparent to rest of system Interface btw. Two layers eg. Application Programmer’s Interface (API) or sockets Logical connection between two layer n entities (peers) Layering harmful? o For performance, no flexibility to use which layer you want. Layers uses services of other layers BELOW. o If packet is causing congestion, it can cause bad performance o Cross-layer design - more boundaries amongst layers or no layers at all ▯ ▯ Host/ End systems implement internet protocol stack ▯ Internet Protocol Stack: (top to bottom 1->5) -1 Application layer: Supporting network applications ex. FTP, HTTP, SMTP used for emails ▯ -2 Transport layer: Process-process data transfer ex. TCP, UDP (OUR project will focus on the TRANSPORT layer) TCP – guarantees delivery to destination in same order and congestion is controlled UDP – does not make guarantee delivery (only make ‘best’ effort’ Responsible for file transfer ▯ -3 Network layer: Routing of datagram’s from source to destination ex. IP, routing protocols Tells you which link ▯ -4 Link layers: Data transfer between neighboring network elements ex. Ethernet, MAC addresses, 802.111 (Wifi), PPP Knows what happens to the link when congestion occurs ▯ -5 Physical layer: Bits “on the wire” ▯ ▯ Usually concern about layers below you. ▯ BCP protocol finds routers of all networks to communicate. Router figures which link to send packages to. Applicati on Transport Network Link Physical ▯ ▯ ▯ ISO/OSI reference model ▯ 2 more additional layers that were removed from the Internet Protocol stack ▯ They removed them because it’s a key design decision to keep the stack SIMPLE and not add complexity by adding too many services. ▯ - presentation: allow applications to interpret meaning of data, eg. Encryption, compression, machine-specific conventions ▯ - sessions: synchronization, checkpointing, recovery of data exchange ▯ - Internet slack “missing” these layers! These services, if needed, must be implemented in application ▯ Encapsulation Message -> Segment -> Datagram ->Frame ▯ Internet Architecture: Two additional representations ▯ ▯ See all the headers and packets coming for the architecture (overpass) ▯ ▯ Internet Architecture ▯ - Defined by IETF ▯ - Three main features Does not imply strict layering. The application is free to bypass the defined transport layers and to directly use IP or other underlying networks. An hour glass shape – wide at the top, narrow in the middle and wide at the bottom. IP serves as the focal point for the architecture. ▯ The Design Philosophy of the DARPA Internet Protocols Fundamental design goal Secondary goals Are these goals met today? Interconnect networks ▯ Fundamental Goals: To develop an effective technique for multiplexed utilization of existing interconnected networks o Interconnecting existing networks vs. designing a new network o Packet switching vs. circuit switching o Store-and-forward architecture ▯ Second Level Goals Survivability in the face of failure o Internet started as a military network! o How to preserve network state? Replication of routers Gather at end-systems, fate-sharing (make fewer design choices and replications) o Advantages of fate-sharing Protects against any number of intermediate failures Easier to engineer o Consequences Stateless (dumb) core, stateful (smart) end-systems End-to-end principle for robustness Support multiple types of communication service o Reliable, guaranteed delivery vs. best-effort o Resulted in TCP and UDP transport protocols, respectively Accommodate a variety of networks o Minimum set of requirements Can transport a packet or datagram Reasonable (but not perfect) reliability Addressing o Resulted in IP Protocol o Additional services implemented at transport or application layer o End-to-end principle for innovation Permit distributed management of resources o routing decisions driven by ISP policies rather than performance o BGP extremely complex Cost-effective o Large TCP/IP headers, overhead for small packets o End-to-end transmission Permit host-attachment with low-level of effort o Difficult initially, easy now Accountability ▯ ▯ End-to-end principle summary ▯ - A mechanism should be place in the network if it can be placed at the end node, and a core of the network should provide the general service, not one that is tailored to a particular application. Advantages: Innovation, reliability & robustness. ▯ ▯ Is there any need to implement a mechanism at lower layers? ▯ - Yes, but only to improve performance ▯ - Ex. Assume a high error rate on a wireless channel ▯ - Then, a reliable communication service at link layer might help ▯ ▯ Tradeoffs ▯ - Application has more information about the data and the semantics of the service it requires (eg. Can check only at the end of each data unit) ▯ - A lower layer has more info of the constraints in data transmission ▯ - Results from the layers ▯ ▯ Summary ▯ - Add functionality . Success story: internet ▯ ▯ Two Forms of E2E Principle ▯ - Horizontal: Push complexity outside the network core, into the end systems ▯ - vertical: push complexity ▯ @@@@@@@@@@@@ ▯ ▯ Two principles that have guided the design of the internet so far: Modularization-layering End-to-end principle ▯ ▯ ▯
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'