下载文档原格式
Data Communication and NetworksLecture 12IP MulticastDecember 8, 2005Joseph ConronComputer Science DepartmentNew York Universityjconron@ 涂塑钢管钢塑复合管衬塑复合管衬塑钢管钢塑管 *cast Definitions•Unicast -send to one destination (198.122.15.20)•General Broadcast -send to EVERY local node(255.255.255.255)•Directed Broadcast -send to subset of nodes onlan (198.122.15.255)•Multicast -send to every member of a Group of“interested” nodes (Class D address).•RFC 1112 (an easy read!)Why Multicast, why not Unicast?•Unicast:–Many applications require same message sent to many nodes (10, 100, 1000, n)–Same message transits network n times.–n messages requires n*(CPU time) as 1 message–Need to deliver “timely” information.•Message arrives at node n >> node 1Why Multicast, why not Broadcast?•Broadcast:–Send a copy to every machine on the net–Simple, but inefficient–All nodes “must” process the packet even if they don’t care –Wastes more CPU cycles of slower machines (“broadcastradiation”)–General broadcast cannot be routed–Directed broadcast is limited in scope (to machines on same sub-net or same domain)Multicast Applications•News/sports/stock/weather updates •Software distribution•Video-conferencing, shared whiteboards •Distributed interactive gaming or simulations •Email distribution lists•Database replicationIP Multicast -Concepts•Message sent to multicast “group” of receivers –Senders need not be group members–Each group has a “group address”–Groups can have any size;–End-stations (receivers) can join/leave at will–Data Packets are UDP (uh oh!)IP Multicast Benefits •Distribution tree for delivery/distribution of packets(i.e., scope extends beyond Lan)–Tree is built by multicast routing protocols. Currentmulticast tree over the internet is called MBONE•No more than one copy of packet appears on any sub-net.•Packets delivered only to “interested” receivers => multicast delivery tree changes dynamically•Non-member nodes even on a single sub-net do not receive packets (unlike sub-net-specific broadcast)Multicast addresses•Class D addresses: 224.0.0.0 -239.255.255.255•Each multicast address represents a group of arbitrary size, called a “host group”•Addresses 224.0.0.x and 224.0.1.x are reserved.See assigned numbers RFC 1700–Eg: 224.0.0.2 = all routers on this sub-net •Addresses 239.0.0.0 thru 239.255.255.255 are reserved for private network (or intranet) useLink-Layer Multicast Addresses 0000000100000000010111100111028 bits23 bits IP multicast addressGroup bit Ethernet and other LANs using 802 addresses:LAN multicast addressLower 23 bits of Class D address are inserted into the lower 23 bits of MAC address (see RFC 1112)0x01005eNIC, IP Stack, Apps Cooperate!•Idea-NIC does not accept packets unless some app on this node wants it (avoid non-productive work).•How does it know which packets to accept?–App “joins” group with Class D address–IP stack gives class D info to NIC–NIC builds “filter” to match MAC addresses–Latch on to:•Own address, MAC broadcast, or “Group” addressIP Multicast -Sending•Use normal IP-Send operation, with multicast address specified as destination•Must provide sending application a way to:–Specify outgoing network interface, if >1 available–Specify IP time-to-live (TTL) on outgoing packet–Enable/disable loop-back if the sending host is/isn’t amember of the destination group on the outgoinginterfaceIP Multicast -Receiving•Two new operations–Join-IP-Multicast-Group(group-address,interface)–Leave-IP-Multicast-Group(group-address,interface)•Receive multicast packets for joined groups via normal IP-Receive operationMulticast Scope•Scope: How far do transmissions propagate?•Implicit scope:–Reserved Mcast addresses => don’t leave subnet.•TTL-based scope:–Each multicast router has a configured TTL threshold–It does not forward multicast datagram if TTL <= TTL-threshold–Useful at edges of a large intranet as a blanket parameterIGMP•Router sends Host Membership Query to 224.0.0.1 (all multicast hosts on sub-net)•Host responds with Host Membership report for each group to which it belongs, sent to group address (224.0.0.2)•Router periodically broadcasts query to detect if groups have gone away•Hosts send reports when join or leave groupIP Multicast in Java•Java has a Multicast Socket Class •Use it to “join” a multicast group.MulticastSocket s = null;InetAddress group = null;try {group = InetAddress.getByName(“227.1.2.3”);s = new MulticastSocket(5555);s.joinGroup(group);} catch (UnknownHostException e) {} catch (IOException e) {}IP Multicast in Java •Receive DatagramPackets on a MulticastSocket DatagramPacket recv = new DatagramPacket(buf,buf.length);try {s.receive(recv);} catch (IOException e) {System.out.println("mcastReceive: " +e.toString());return;}// get messageString msg = new String(recv.getData(),recv.getOffset(), recv.getLength());IP Multicast in Java•To send, just send a DatagramPacket to the multicast address, port (no need to use a MulticastSocket, although you could)group = InetAddress.getByName(“227.1.2.3”);s = new DatagramSocket();DatagramPacket snd = new DatagramPacket(buf, buf.length,group, 5555);try {s.send(snd);} catch (IOException e) {System.out.println("mcastSend: " + e.toString());return;}Let’s See Multicast in ActionReliable Multicast•Remember: IP Multicast uses IP -it’s unreliable!•We need a “reliable” multicast•Let’s review what we mean by “reliable”–message gets to ALL receivers–sending order is preserved–no duplicates–no corruptionReliable Multicast•Problems:–Retransmission can make reliable multicast asinefficient as replicated unicast•Ack-implosion if all destinations ack at once•Nak-implosion if a all destinations ack at once–Source does not know # of destinations. Or even if alldestinations are still “up”–one bad link affects entire group–Heterogeneity: receivers, links, group sizesReliable Multicast•RM protocols have to deal with:–Scalability.–Heterogeneity.–Adaptive flow/congestion control.–Reliability.•Not all multicast applications need reliability of the type provided by TCP. Some can tolerate reordering, delay, etc •Let’s look at two very different approaches–PGM(Pragmatic General Multicast)–RMP (Reliable Multicast Protocol)Pragmatic General Multicast•Cisco’s reliable multicast protocol •Central design goal–Simplicity of operation yet provide forscalability and network efficienc y.•Not the perfect solution for all requirements, but for most, P retty G ood!Overview of PGM•Component s–Source: transport-layer originators of PGM data packets–Receiver: transport-layer consumers of PGMdata packets–Network element : network-layer entities in theintervening network –typically routers, but neednot be.•Receiver initiated repair protocol–Based on NAKPGM Packet Types •ODATA–data packets from a source•SPM(Source Path Message)–Sent by sources: used to establish reverse path from receivers tosources.•NAK–sent by receivers to ask for repairs.–Forwarded upstream along source path.•NCF(NAK Confirm)–sent by network elements to NAKers.•RDATA–data packet resent from a source in reply to a NAKPGM Transmit Window•Problem: NO Acks, so:–senders don’t know when all receivers have packets.–Therefore, how long does sender retain packet?•Solution (sort of)–Define a window (range of sequence #s)–Keep only packets in window–Update window edges periodically to receivers–Receivers can only ask for resend (NAK) of packets in the window.Source Functions•Data Transmission–Multicast ODATA packets within transmit window a given transmit rate•Source Path State–multicast SPMs to establish source path state in PGM network elements.•NAK Reliability–Sources multicast NCFs in response to any NAKs they receive.•Repairs–multicast RDATA packets in response to NAKs received for data packets within the transmit windowSource Functions (continued)•Transmit Window Advance–Sources MAY advance the trailing edge of the window according to one of a number of strategies, for example:•keeping the window at a fixed size in bytes•keeping the window at a fixed number of packets•keeping the window at a fixed real time duration.•Trailing edge is advanced in ODATA and SPM packets.•Question: What defines the leading edge?Receiver Functions•Source Path State–use SPMs to determine the last-hop PGM network element for a given TSI to which to direct their NAKs.•Data Reception–receive ODATA within transmit window and eliminate any duplicates (and order packets!)•Repair Requests–Receivers unicast NAKs to last-hop PGM network element.–receiver MUST repeatedly transmit a given NAK until it receives a matching NCF.Receiver Functions (continued)•NAK Suppression–Receivers suppress NAKs for which a matching NCF or NAK is received during the NAK transmit back-off interval.•Receive Window Advance–Receivers immediately advance their receive windows upon receipt of any PGM data packet or SPM within the transmitwindow that advances the receive window.Network Element Functions •Source Path State–Network elements intercept SPMs and use them to establish source path state for the corresponding TSI before multicast forwardingthem.•NAK Reliability–Network elements multicast NCFs to the group in response to any NAK they receive.–For each NAK received, create repair state recording the TSI, the sequence number of the NAK, and the input interface on which the NAK was received.Network Element Functions (cont’d)•Constrained NAK Forwarding–Network elements repeatedly unicast forward only the first copy of any NAK they receive to the upstream PGM network element on thedistribution path for the TSI until they receive an NCF in response.•NAK Elimination–Network elements discard exact duplicates of any NAK for which they already have repair state and respond with a matching NCF.•Constrained RDATA Forwarding–Network elements use NAKs to maintain repair state consisting ofa list of interfaces upon which a given NAK was received, andthey forward the corresponding RDATA only on these interfaces.Operation -No Errors •Sources multicast ODATA packets–Packet contains source ID, seq #, Window trailing edge, data–Network Elements forward packets to receivers (could be applications nodes or other NEs)•Sources periodically multicast SPM packets (also contain source ID, seq #, Window edges)•Network Elements use SPMs to build a reverse path to the source (keyed by Source ID, called TSI in PGM).–NE must forward SPM to downstream NE!Receiver Operation: Packet Loss •Receiver detects missing packet possibly from:–ODATA sequence number–SPM sequence number–Receipt of NCF•Start a random (bounded) timer–If missing packet arrives (ODATA or RDATA) cancel (success)–If another NCF arrives (same seq. #), restart timer–If timer expires, send NAK, restart timer–If too many retries, cancel (fail)Network Element Operation: Packet Loss•Receiver unicasts NAK to NE•NE builds a “repair state” for this request ONLY if NAK is from a local group member.•NE multicasts NCF to group (limit scope using TTL) –now all receivers in local group know.•NE unicasts NAK to next upstream PGM hop for this source (using TSI from NAK packet and SPM info)•This process is repeated at each successive upstream NESource Operation: Packet Loss•Source of requested packet gets NAK •Source multicasts NCF•Source multicasts RDATA packet (but only if the requested packet is still in the transmit window)Pragmatic General Multicast Packet 1 reaches only R1;R2, R3, R4 request resendsPacket 1 resent to R2, R3, R4; Not resent to R1R1S R3R4R21111Resent packet R1SR3R4R2211X Routers remember resend requestsResend requestRMP•Messages from multiple senders to multiple destinations.•Quality of Service (QoS) Selection on a per message basis.•Supports total ordering of all messages.•Transparent failure recovery (Reformation)•uses Post Ordering Rotating Token algorithm, extension of work by Chang & MaxemchukRMP: Quality of Service•Unreliable-same QOS as UDP.•Reliable-delivery guaranteed, but not order or 1-copy.•Source Ordered-all messages from same source ordered, 1-copy.•Totally Ordered-all receivers see exactly same sequence from all sources.About Total Ordering:•Hosts A, B, & C send messages into the group (A1, A2, B1, B2, C1, C2)•Suppose:–Host D gets A1, B1, B2, C1, A2, C2–Host E gets C1, A1, A2, B1, C2, B2–Host F gets B1, A1, C1, A2, B2, C2•What if results at Hosts D, E, F depend on order of all messages? In this case, results will be different!•Total ordering means D, E, F have to see same sequence!RMP -Concepts•Each process (an App) has an ID•Processes form groups (based on mcast Addr, Port, TTL)•All processes see “membership list”•Members agree among themselves what the “order” of messages should be (when total order QOS is selected).RMP: Token Passing•One member holds a “token”•The token holder assigns “global” sequence number to each correct packet.•Every packet has unique id (GroupID:Pid:seqno)•Token Holder “passes” token to next member in list (token pass is mcast!)•Token packet contains global sequence numbers and packet IDs.RMP: Ack,Nak•Since token pass is mcast, all members see it (usually).•The token is the Ack packet.•Since Ack packet contains ids of packets, receiving process sees what it might have missed!•If missing packets, send Nak packet to request packets (Nak is mcast!)RMP: Avoiding Nak Implosion•Before sending Nak, start random timer Tr •If see missing packets, kill Tr, accept packets.•If see Nak for same packets before Tr, kill Tr, start new timer Tn•If Tn or Tr, send NakRMP: Protocol Model Multicast Media ACB DATA (A, 1)ACK ( (A,1), C, 1)ACK ( NULL, A, 2)Event Order DATA (A, 1)ACK ( (A, 1), C, 1)ACK (NULL, A, 2)Imposed Order Timestamp Event 1ACK ( (A, 1), C, 1)DATA (A, 1)2ACK (NULL, A, 2)Initial Token Site (1) B is TS(2) A sends (1)(3) B assigns TS 1 to(A,1), passes token to C.(4) C* has nothing, sopasses token (NULL Ack)to A with TS = 2(5) Packet (A,1) can becommitted after token getsback to B * Cannot accept token token unless have all packets being assigned global timestampsPacket Reception vs. Delivery•When providing total ordering:–Cannot deliver packets to app when received.–Must wait until:•timestamp is assigned•packet is stable at all nodes (Token is passed n times in groupof size n)•When providing source ordering, can deliver packet if have all previous packets from source •Question: When can a node delete a packet?Packet Stability•Rule:you can delete a packet if no other group member will need it.•When is that?–When the site that that assigned a global time stamp to the packet becomes the token site again!–How to know this? Answer: Ordering Queue•list of all packets in order of time stamp•when list has n + 1 Ack packets, delete oldest Ack and lowernumbered packets.RMP: Observations •Good:–Use to build distributed Applications where virtualsynchrony is required.–Fault Tolerant -group reforms after network partition •Not So Good:–Does not scale well (maybe to 100 nodes)•Question: Why do you think this is so?–More complex protocol than PGM–Implementations are no longer available (except mine), but specs with FSMs are available.。
数据与计算机通信(英文)一、课程说明课程编号：090326Z10课程名称：数据与计算机通信(英文)/Data and Computer Communications课程类别：专业教育课程学时/学分：32 / 2先修课程：高等数学、模拟电子技术、数字电子技术、信号与系统、通信原理适用专业：通信工程、电子信息工程教材、教学参考书：1.Behrouz A. Forouzan, Data Communications and Networking, 5th，McGraw-Hill, 20122.William Stallings. Data and Computer Communications, 9thEdition.Prentice Hall, 2010.3.Fred Halsall. Data Communications, Computer Networks and OpenSystems, 4th Edition. Addison-Wesley, 1996.4.David Salomon. Coding for Data and Computer Communications.Springer, 2005.5.Richard Stevens . Unix Network Programming - V olume 1 (2003) andV olume 2 (1999). Prentice Hall二、课程设置的目的意义《数据与计算机通信》课程是通信工程专业的一门选修的专业基础课。
课堂采用双语教学，使用经典的原版教材。
本课程的主要任务是从数据通信、计算机网络通信的视角来理解、分析、设计分布式的通信系统，使学生了解和掌握数据通信、计算机通信区别传统电信等语音业务承载网络的原理、技术等。
系统掌握数据通信所采用的技术，同时提高英语的阅读和理解能力。
三、课程的基本要求知识：理解数据通信的基本原理；熟练掌握数据通信、计算机通信所涉及的硬件、软件相关技术；理解计算机通信与传统电信等语音业务承载网络的区别；掌握原理计算机通信的原理；掌握科学研究的基本思路和方法，能力：掌握数据通信、计算机通信网的开发设计方法，将其用于解决实际的数据网络通信问题；熟练掌握网络编程的技能；针对数据通信新技术发展前沿问题，掌握英文科技文献综述的能力；在讨论中培养创新意识和国际前沿研究视野，培养追踪数据与计算机通信网的新技术前沿问题的能力，素质：建立原理－分析－综述-设计一体的观念，通过课程学习中的分析、讨论、辩论培养分析沟通交流素质，建立从原理分析到编程设计到实际应用的思维模式，提升发现问题、寻找解决问题方法的基本素质。
Chapter 02 Data Communication Foundation (Part I) ◆数据通信的基本概念(basic concept)◆数据编码与调制技术(coding and modulating techniques)2.1 数据通信2.1.1 信息、数据、信号与信道数据通信是指通过通信系统将数据以某种信号的方式从一处安全、可靠地传输到另一处，包括数据的传输及传输前后的处理。
1．信息信息（Information）是对客观事物特征和运动状态的描述，其形式多种多样。
2．数据数据（Data）是传递信息的实体。
通信的目的是传送信息，传送之前必须先将信息用数据表示出来。
数据可分为两种：模拟数据和数字数据。
模拟数据：用于描述连续变化量的数据，如声音、温度等；数字数据：用于描述不连续变化量（离散值）的数据，如文本信息、整数等。
3．信号信号（Signal）是数据在传输过程中的电磁波表示形式。
信号可以分为模拟信号和数字信号两种。
模拟信号是一种连续变化的信号，其波形可以是一种连续性的正弦波，如图所示；数字信号是一种离散信号，最常见也是最简单的数字信号是二进制信号，用数字“1”和数字“ 0”表示，其波形是一种方波，如图2-1（b）所示。
2.1.2 数据通信系统的基本结构1．模拟通信系统传统的电话、广播、电视等系统都属于模拟通信系统，模拟通信系统的模型如图所示:2．数字通信系统计算机通信、数字电话及数字电视系统都属于数字通信系统。
数字通信系统的模型如图所示:数字通信系统通常由信源、编码器、信道、解码器、信宿及噪声源组成，发送端和接收端之间还需要时钟同步系统。
2.1.3 数据通信系统的性能指标1．有效性指标的具体表述（1）数据传输速率（Data Transfer Rate）。
数字通信系统的有效性可用数据传输速率来衡量，数据传输速率越高，系统的有效性越好。
通常可从码元速率（Symbol transmission rate）和信息速率(Information transmission rate)两个不同的角度来定义数据传输速率。
Chapter 1IntroductionOriginally made by J.F Kurose and K.W. RossModified by Mingyu LimCollaborative Computing Systems Lab (http://ccslab.konkuk.ac.kr) Department of Internet and Multimedia EngineeringKonkuk UniversityChapter 1: roadmap1.1 What is the Internet?1.2Network edgeend systems, access networks, links1.3Network corecircuit switching, packet switching, network structure1.4Delay, loss and throughput in packet-switchednetworks1.5Protocol layers, service models1.6Networks under attack: security1.7HistoryGlobal ISP Home network“Cool” internet appliancesIP picture frame/Web-enabled toaster +weather forecasterWorld’s smallest web server/~shri/iPic.htmlInternet phonesGlobal ISP Home networkWhat’s a protocol?a human protocol and a computer network protocol:Hi TCP connection request Q:Other human protocols?HiGot the time?2:00TCP connection responseGet /kurose-ross<file>timeChapter 1: roadmap1.1 What is the Internet?1.2 Network edgeend systems, access networks, links1.3 Network corecircuit switching, packet switching, network structure1.4Delay, loss and throughput in packet-switchednetworks1.5Protocol layers, service models1.6Networks under attack: security1.7HistoryAccess networks and physical media Q: How to connect endsystems to edge router?residential access netsinstitutional accessnetworks (school,company)mobile access networksKeep in mind:bandwidth (bits persecond) of accessnetwork?shared or dedicated?Residential access: point to point accessDialup via modemup to 56Kbps direct access torouter (often less)Can’t surf and phone at sametime: can’t be “always on”DSL:digital subscriber linedeployment: telephone company (typically)up to 1 Mbps upstream (today typically < 256 kbps) up to 8 Mbps downstream (today typically < 1 Mbps) dedicated physical line to telephone central officeResidential access: cable modemsHFC: hybrid fiber coaxasymmetric: up to 30Mbps downstream, 2Mbps upstreamnetwork of cable and fiber attaches homes to ISP routerhomes share access to routerdeployment: available via cable TV companiesResidential access: cable modemsCable Network Architecture: Overviewhomecable headendcable distributionnetwork (simplified)Typically 500 to 5,000 homesCable Network Architecture: Overviewserver(s)homecable headendcable distribution networkCable Network Architecture: Overviewhomecable headendcable distributionnetwork (simplified)Cable Network Architecture: OverviewV I D E O V I D E O V I D E O V I D E O V I D E O V I D E O D A T A D A T A CONTROL123456789FDM (more shortly):homecable headendcable distribution networkChannelsCompany access: local area networkscompany/univ local areanetwork(LAN) connectsend system to edge routerEthernet:10 Mbs, 100Mbps,1Gbps, 10Gbps Ethernetmodern configuration:end systems connectinto Ethernet switchLANs: chapter 5Wireless access networks shared wireless accessnetwork connects end systemto routervia base station aka “accesspoint”wireless LANs:base router802.11b/g (WiFi): 11 or 54 Mbps wider-area wireless access provided by telco operator~1Mbps over cellular system(EVDO, HSDPA)next up (?): WiMAX (10’s Mbps) over wide area stationmobilehostsHome networksTypical home network components: DSL or cable modem router/firewall/NAT Ethernetwireless access wireless access pointwireless access pointwireless laptopsrouter/firewallcable modemto/from cable headendEthernetPhysical Media: coax, fiberCoaxial cable:two concentric copper conductorsbidirectionalbaseband:single channel on cable Fiber optic cable:glass fiber carrying light pulses, each pulse a bithigh-speed operation:high-speed point-to-point single channel on cablelegacy Ethernetbroadband:multiple channels oncableHFCtransmission (e.g., 10’s-100’s Gps)low error rate: repeatersspaced far apart ; immuneto electromagnetic noisePhysical media: radiosignal carried in electromagneticspectrumno physical “wire” bidirectional Radio link types:terrestrial microwavee.g. up to 45 Mbps channels LAN(e.g., Wifi)11Mbps, 54 Mbpswide-area(e.g., cellular)propagationenvironment effects:reflectionobstruction by objectsinterference wide-area(e.g., cellular) 3G cellular: ~ 1 MbpssatelliteKbps to 45Mbps channel (or multiple smaller channels) 270 msec end-end delaygeosynchronous versus low altitudeChapter 1: roadmap1.1 What is the Internet?1.2Network edgeend systems, access networks, links1.3 Network corecircuit switching, packet switching, network structure1.4Delay, loss and throughput in packet-switchednetworks1.5Protocol layers, service models1.6Networks under attack: security1.7HistoryThe Network Core mesh of interconnectedroutersthe fundamentalquestion:how is datatransferred through net?circuit switching:dedicated circuit percall: telephone netpacket-switching:datasent thru net indiscrete “chunks”Network Core: Circuit Switchingnetwork resources (e.g., bandwidth) divided into “pieces” pieces allocated to calls dividing link bandwidth into “pieces”frequency divisiontime divisionresource piece idle if not used by owning call (no sharing)Circuit Switching: FDM and TDMFDMfrequency4 usersExample: timeTDMfrequencytimeNumerical exampleHow long does it take to send a file of 640,000 bits from host A to host B over a circuit-switched network?All links are 1.536 MbpsEach link uses TDM with 24 slots/secEach link uses TDM with 24 slots/sec500 msec to establish end-to-end circuit Let’s work it out!Network Core: Packet Switchingeach end-end data stream divided into packetsuser A, B packets share network resourceseach packet uses full link resource contention: aggregate resource demand can exceedamount availablecongestion: packetsbandwidthresources used as neededqueue, wait for link use store and forward: packets move one hopat a timeNode receives completepacket before forwardingBandwidth division into “pieces”Dedicated allocationResource reservationPacket Switching: Statistical MultiplexingA BC100 Mb/s Ethernet1.5 Mb/sstatistical multiplexingqueue of packets Sequence of A & B packets does not have fixed pattern, bandwidth shared on demand statistical multiplexing .TDM: each host gets same slot in revolving TDM frame.DEwaiting for outputlinkPacket-switching: store-and-forwardtakes L/R seconds to transmit (push out)packet of L bits on to Example:L = 7.5 MbitsR R R Llink at R bpsstore and forward:entire packet mustarrive at router before it can be transmittedon next linkdelay = 3L/R (assuming zero propagation delay) R = 1.5 Mbpstransmission delay = 15 secmore on delay shortly …Packet switching versus circuit switching1 Mb/s linkeach user:100 kb/s when “active”Packet switching allows more users to use network!active 10% of time circuit-switching:10 userspacket switching:with 35 users,probability > 10 active at same time is less than .0004N users1 Mbps linkQ: how did we get value 0.0004?Packet switching versus circuit switching Is packet switching a “slam dunk winner?”great for bursty dataresource sharingsimpler, no call setupexcessive congestion:packet delay and lossprotocols needed for reliable data transfer,congestion controlQ: How to provide circuit-like behavior?bandwidth guarantees needed for audio/video apps still an unsolved problem (chapter 7)Q: human analogies of reserved resources (circuitswitching) versus on-demand allocation (packet-switching)?Internet structure: network of networksroughly hierarchicalat center: “tier-1” ISPs (e.g., Verizon, Sprint, AT&T,Cable and Wireless), national/international coverage treat each other as equalsTier 1 ISPTier 1 ISPTier 1 ISPTier-1 providers interconnect (peer) privatelyTier-1 ISP: e.g., Sprint…peeringto/from backbone…POP: point-of-presenceto/from customers.………Internet structure: network of networks“Tier-2” ISPs: smaller (often regional) ISPsConnect to one or more tier-1 ISPs, possibly other tier-2 ISPsTier-2 ISPs Tier 1 ISPTier 1 ISPTier 1 ISPTier-2 ISPTier-2 ISPTier-2 ISPTier-2 ISPTier-2 ISPTier-2 ISP pays tier-1 ISP for connectivity to rest of Internet tier-2 ISP is c ustomer of tier-1 provideralso peerprivately with each other.Internet structure: network of networks“Tier-3” ISPs and local ISPslast hop (“access”) network (closest to end systems)local ISPlocal local local ISPTier 3ISP Local and tier-Tier 1 ISPTier 1 ISPTier 1 ISPTier-2 ISPTier-2 ISPTier-2 ISP Tier-2 ISP Tier-2 ISPISPISPlocal ISP local ISPlocal ISPlocal ISP3 ISPs are customers of higher tier ISPsconnecting them to rest of InternetInternet structure: network of networksa packet passes through many networks!local ISPlocal local local ISPTier 3ISP Tier 1 ISPTier 1 ISPTier 1 ISPTier-2 ISPTier-2 ISPTier-2 ISP Tier-2 ISPTier-2 ISPISPISPlocal ISP local ISPlocal ISPlocal ISPChapter 1: roadmap1.1 What is the Internet?1.2Network edgeend systems, access networks, links1.3Network corecircuit switching, packet switching, network structure1.4 Delay, loss and throughput in packet-switchednetworks1.5Protocol layers, service models1.6Networks under attack: security1.7HistoryHow do loss and delay occur?packets queue in router bufferspacket arrival rate to link exceeds output link capacitypackets queue, wait for turnpacket being transmitted (delay) ABpackets queueing(delay)free (available) buffers: arriving packetsdropped (loss) if no free buffersFour sources of packet delay1. nodal processing:check bit errorsdetermine output link 2. queueingtime waiting at output link for transmission depends on congestion level of routerA Bpropagation transmissionnodalprocessing queueingDelay in packet-switched networks3. Transmission delay:R=link bandwidth (bps) L=packet length (bits) time to send bits into 4. Propagation delay:d = length of physical links = propagation speed in medium (~2x108m/sec) propagation delay = d/slink = L/R propagation delay = d/sA Bpropagationtransmissionnodalprocessing queueingNote: s and R are verydifferent quantities!cars “propagate” atTime to “push” entirecaravan through toll toll boothtoll boothCars now “propagate” atAfter 7 min, 1st carat 2nd booth and 3 cars toll boothtoll boothNodal delayd proc = processing delaytypically a few microsecs or less d proptrans queue proc nodal d d d d d +++= d queue = queuing delay depends on congestiond trans = transmission delay= L/R, significant for low-speed links d prop = propagation delaya few microsecs to hundreds of msecsQueueing delay (revisited)R=link bandwidth (bps)L=packet length (bits)a=average packetarrival ratetraffic intensity = La/RLa/R ~ 0: average queueing delay smallLa/R -> 1: delays become largeLa/R > 1: more “work” arriving than can be serviced, average delay infinite!。
