计算机网络复习.doc

Abbreviations:LANLocal Area Network 局域网MANMetropolitan AreaNetwork 城域网PANpersonal area network个人局域网WANWide Area Network广域网VLANVirtual Local Area Network虚拟局域网OSI/RM Open System InterconnectionReference Model 开放系统互连参考模型UTPUnshielded Twisted Pair非屏蔽双绞线SNRSigal-to-Noise Ratio信噪比FDMFrequency Division Multiplexing频分多路复用TDMTime Division Multiplexing 时分多路复用WDM Wave length Division Multiplexing 波分复用CDMACode Division Multiple Access码分多址CSMA/CDCarrier Sense Multiple Access with Collision Detection载波侦听多路访问/冲突检测CSMA/CA Carrier Sense Multiple Access with Collision Avoidance 载波侦听多路访问/冲突避免RTSRequest To Send请求发送CTSClear To Send 清除发送MACMedia Access Control介质访问控制PCMPulse Code Modulation 脉冲编码调制QAM Quadrature Amplitude Modulation正交振幅调制QPSK Quadrature Phase Shift Keying正交相移键控ADSLAsymmetric Digital Subscriber Line非对称数字用户环路CRCCyclic Redundancy Check循环冗余校验VCVirtual Circuit虚电路ATMAsynchronous Transfer Mode异步传输模式PPPPoint to Point Protocol 点对点协议HLDCHigh-Level Data Link Control高级数据链路控制RIPRouting Information Protocol路由信息协议RTTRound-TripTime往返时延CIDRClassless Inter-Domain Routing无类别域间路由IPInternet Protocol网络之间互连的协议TTLTime To Live生存时间MTUMaximum Transmission Unit最大传输单元ICMPInternet Control Message Protocol网络控制报文协议UDPUser Datagram Protocol用户数据报协议ARPAddress Resolution Protocol地址解析协议DHCPDynamic Host Configuration Protocol动态主机配置协议NATNetwork Address Translation网络地址转换RPCRemote Procedure Call远程过程调用OSPFOpen Shortest Path First开放式最短路径优先BGPBorder Gateway Protocol边界网关协议TCPTransmission Control Protocol传输控制协议RTPReal-time Transport Protocol实时传输协议FTPFile Transfer Protocol文件传输协议SMTPSimple Mail Transfer Protocol简单邮件传输协议POP3Post Office Protocol - Version 3邮局协议版本3IAMPinternet message access protocol因特网信息报文存取协议?不知道对不对IMAPInternet Mail Access ProtocolInternet邮件访问协议DNSDomain Name System域名系统URLUniform Resoure Locator统一资源定位器HTTPHyper Text Transfer Protocol超文本传输协议WWW World Wide Web万维网1、 Basic and important concepts or notations l network architecture, layers, protocols l OSI/RM, TCP/IP reference model, main tasks of data link/network/transport layers, protocols at each layer of TCP/IP modell PAN, LAN, WAN, VLAN, WLANl bandwidth, link capacityl multiplexing, channel allocationl Frame, Ethernet frame format, MAC addressl framing method：character-count, byte-stuffing, bit-stuffing, flag bytel Connection/connectionless service, circuit switching/packet switching, l Error Control coding, Hamming distancel Hamming code, even-parity /odd-parityl CRC, generator polynomial, remainder l stop-and-wait protocols, sliding window, go-back-n, selective-repeat, piggyback l CSMA/CDl hidden station problem, exposed station problem, CSMA/CAl hub/repeater /switch/bridge/router/gateway.l routing algorithm, Distance vector routing, link state routingl IP address, classful and special addressing, CIDR, subnetting/aggregation, mask/prefixl routing table/forwarding, l packet, IPv4 headerl NAT, 3 reserved private IP address ranges l TCP, port/port number, TCP header, three-way handshakel congestion control, ECN/RED, AIMD/slow start, congestion window, thresholdl DNS system, domain name resolution2、 Computations l Nyquist law, Shannon law, PCMl FDM, CDMAl bit-stuffing, byte-stuffing, character-count l Hamming code, CRCl CSMA/CD，minimal frame sizel Distance vector routing algorithml CIDR, aggregationl forwarding in routers, longest matching第五版：P106 11,16,2011 What is the principal difference between connectionless communication and connection-oriented communication?Connection-oriented communication has three phases. In the establishment phase, a request is made to set up a connection. Only after this phase has been successfully completed can the data transfer phase be started and data transported. Then comes the release phase. Connectionless communication does not have these phases. It just sends the data.16 把比特流转化为帧OSI 数据链路层 TCP/IP ：链路层决定哪条路径通过子网OSI 网络层 TCP/IP 互联网层20 What is the main difference between TCP and UDP.Answer：The first one, TCP (Transmission Control Protocol), is a reliable connection-oriented protocol that allows a byte stream originating on one machine to be delivered without error on any other machine in the Internet.The second protocol, UDP (User Datagram Protocol), is an unreliable, connectionless protocol for applications that do not want TCPs sequencing or flow control and wish to provide their own.TCP是transmission control protocol传输控制协议，UDP是user data gram protocol用户数据电报协议。TCP是面向连接的协议，允许字节流无错误地从一台机器上互联到别的机器上。UDP是不可靠的，面向无连接的协议，适用于不需要TCP协议的那种流量控制和自我实现的应用程序。P207 2,3,4,26,27,28,41,442 A noiseless 4-kHz channel is sampled every 1 msec. What is the maximum data rate?If an arbitrary signal has been run through a low-pass filter of bandwidth B, the filtered signal can be completely reconstructed by making only 2B (exact) samples per second.A noiseless channel can carry an arbitrarily large amount of information, no matter how often it is sampled. Just send a lot of data per sample. For the 4 kHz channel, make 8000 samples/sec. If each sample is 16 bits, the channel can send 128 kbps. If each sample is 1024 bits, the channel can send 8.192 Mbps. The key word here is noiseless. With a normal 4 kHz channel, the Shannon limit would not allow this.PCM (Pulse Code Modulation)脉码调制它将4千赫兹的电话信道的模拟信号转化为数字信号。一条普通的电话线路带宽为4KHz，根据奈奎斯特定理：只要每秒4000*2=8000次的采样频率就能获取一个4KHz的信道中的全部信息，再高的采样频率也无意义，所以PCM的采样时间为1/8000=125us。3 If a binary signal is sent over a 3-kHz channel whose signal-to-noise ratio is 20 dB, what is the maximum achievable data rate?20dB=10lgS/N S/N=100 Shannon limit=Blog2(1+S/N)=3000*log2(1+100)= 19.975 KbpsNyquist limit=2Blog2V=2*3000*log22=6KbpsDate rate19.975Kbps and Date rate6Kbps （同时满足）4 We have a channel with a 1 MHz bandwidth. The SNR for this channel is 63; what is the appropriate bit rate and signal level?Shannon limit=Blog2(1+S/N)=106*log2(1+63)= 6 MbpsNyquist limit=2Blog2V=2*106*log2V=6MbpsV=826 What is PCM? Why has the PCM sampling time been set at 125usec?PCM means pulse code modulation. It is the analog-to-digital signal 模拟数字信号 converting technique for transmitting information from the 4-KHz telephone channel. 电话通道According to the Nyquist theorem, the sampling frequency needed to capture all the information in a 4-kHz channel is 8 KHz. That is to say, a sampling time is 1sec/8000 = 125sec.27 28 41 Suppose that A, B, and C are simultaneously transmitting 0 bits, using a CDMA system with the chip sequences of Fig. 2-45. What is the resulting chip sequence?编码方法：用要发送的bit串转化成双极性码，”1”对应”+1”, ”0”对应”-1”, 不发送的用全“0”表示，然后按顺序同各个站的码片序列相乘，最后将各站的结果序列（混合）相加，就是在空中发射的信号。A: “0”-1”, -1*(-1 -1 -1 +1 +1 -1 +1 +1) = (+1 +1 +1 -1 -1 +1 -1 -1) ; B: “0”-1”, -1 *(-1 -1 +1 -1 +1 +1 +1 -1)= (+1 +1 -1 +1 -1 -1 +1 +1); C: “0”-1”, -1 * (-1 +1 -1 +1 +1 +1 -1 -1)= (+1 -1 +1 -1 -1 -1 +1 +1) D：不发送，(0 0 0 0 0 0 0 0); 4个序列相加得：（+3 +1 +1 -1 -3 -1 -1 +1）.44 A CDMA receiver gets the following chips: (-1 +1 -3 +1 -1 -3 +1 +1). Assuming the chip sequences defined in Fig. 2-45, which stations transmitted, and which bits did each one send?解码方法：用接收到的码片同各个站的码片序列进行“点积”(又称为“内积”)，也就是按位相乘，结果序列的所有位相加，除以码片序列的长度，”1”意味着原先编码时是”1”，”-1”表示编码”0”,“0”表示没有静默，没发送。A: (-1 +1 -3 +1 -1 -3 +1 +1) (-1 -1 -1 +1 +1 -1 +1 +1) =(1-1+3+1-1+3+1+1)/8=8/8=1, 即： A发送了bit “1”;B: (-1 +1 -3 +1 -1 -3 +1 +1) (-1 -1 +1 -1 +1 +1 +1 -1) =(1-1-3-1-1-3+1-1)/8=-8/8=-1，即： B发送了bit “0”;C: (-1 +1 -3 +1 -1 -3 +1 +1) (-1 +1 -1 +1 +1 +1 -1 -1) =(1+1+3+1-1-3-1-1)/8=0/8=0，即： C没有发送信息。P272 2,7,8,14,152 A是错的 应为 000001017 An 8-bit byte with binary value 10101111 is to be encoded using an odd-parity Hamming code. What is the binary value after encoding? p1 p2 a3 p4 a5 a6 a7 p8 a9 a10 a11 a12=? ? 1 ? 0 1 0 ? 1 1 1 1P1+a3+a5+a7+a9+a11=奇 ？+1+0+0+1+1=奇P2+a3+a6+a7+a10+a11=奇 ？+1+1+0+1+1=奇P4+a5+a6+a7+a12=奇 ？+0+1+0+1=奇P8+a9+a10+a11+a12=奇 ？+1+1+1+1=奇得汉明码为011001011111。若传输后，接收方收到的为011111011111，检验：P1：0+1+1+0+1+1=偶 p2：1+1+1+0+1+1=奇P4：1+1+1+0+1=偶 p8：1+1+1+1+1=奇8 ?14 15 A bit stream 10011101 is transmitted using the standard CRC method described in the text. The generator polynomial is x3 + 1. Show the actual bit string transmitted. Suppose the third bit from the left is inverted during transmission. Show that this error is detected at the receivers end.生成式为1001。消息比特加上3个0后成为10011101000，除以1001后余式为100，因此实际传输的比特串为10011101100。左起第三比特颠倒后接收到的多项式为10111101100，除以生成式，余式为100，而不是0，这就使接收方明白发生了错误。P369 13,14,15,16,2213 14 15 A 1-km-long, 10-Mbps CSMA/CD LAN (not 802.3) has a propagation speed of 200 m/sec. Repeaters are not allowed in this system. Data frames are 256 bits long, including 32 bits of header, checksum, and other overhead. The first bit slot after a successful transmission is reserved for the receiver to capture the channel in order to send a 32-bit acknowledgement frame. What is the effective data rate, excluding overhead, assuming that there are no collisions?(长为1km的CSMA/CD局域网（不是802.3网），数据率为10Mbps，传播速度为200 m/s。系统中不用中继器。数据帧长256比特，其中包括32比特头部、检验和和其它开销。一次成功传输后的第一个时隙保留给接收方捕获信道，以便让它发送一个32比特的确认帧。假设不发生冲突，扣除开销，有效的数据率为多大？)CSMS/CD局域网是分时隙的（time slotted）。每次发送之前必须侦听信道，至少 花费一个时隙(time slot) 才能确保不冲突 ！时隙长度取决于最大往返传播延时。Single-trip takes 1km/ 200 m/sec=5usec, round-trip propagation delay is = 5X2=10usec, so the length of time slot should be 10usec.信号从电缆一端传导到另一端用时1000/ (200/10-6)=5us, 往返需5*2=10us，因此时隙长度为10us。transmitter seizes cable (10 sec): before transmission, the transmitter checks the cable, and if the cable is idle, starts to transmit at the beginning of next time slot 发前“听信道”要用一个时隙transmit data (25.6 sec) 传输延时Delay for last bit to get to the end (5.0 sec) 单程传播延时receiver seizes cable (10 sec): similar to the transmitter同1.acknowledgement sent (3.2 sec)传输延时Delay for last bit to get to the end (5.0 sec)单程传播延时The sum of these is 58.8 sec. In this period, 224 data bits are sent, for a rate of about 3.8 Mbps.16 Consider building a CSMA/CD network running at 1Gbps over 1km cable with no repeater.The signal speed in the cable is 200,000 km/secWhat is minimum frame size?22 In Fig. 4-27, four stations, A, B, C, and D, are shown. Which of the last two stations do you think is closest to A and why?Textbook：From the information provided in the RTS request, C can estimate how long the sequence will take, including the ACK, so it asserts a kind of virtual channel busy for itself, indicated by NAV (Network Allocation Vector). D does not hear the RTS, but it does hear Bs CTS, so it also asserts the NAV signal for itself. Note that the NAV signals are not transmitted; they are just internal reminders to keep quiet for a certain period of time P508 5,23,24,25,27,28,305 Consider the subnet of Fig. 5-12(a). Distance vector routing is used, and the following vectors have just come in to router C: from B: (5, 0, 8, 12, 6, 2); from D: (16, 12, 6, 0, 9, 10); and from E: (7, 6, 3, 9, 0, 4). The measured delays to B, D, and E, are 6, 3, and 5, respectively. What is Cs new routing table? Give both the outgoing line to use and the cost.来自邻居们的消息B: (A5, B0, C8, D12, E6, F2);D: (A16, B12, C 6, D0, E 9, F10);E: ( A7, B6 , C3, D9, E0, F4). 自己测量的delays from C to B, D, and E are 6, 3, and 5, Going via B gives (A11,B 6, C14, D18, E12, F8).Going via D gives (A19, B15, C9, D3, E9, F10).Going via E gives (A 12, B11, C8, D14, E5, F9).Taking the minimum for each destination except C givesC: (11, 6, 0, 3, 5, 8).(B, B, , D, E, B) These are outgoing lines.路由器C更新后的路由表说明：到A，最近距离为11，从B走；到B，距离为6，从B走；到C吗？就是自己这里；到F距离为8，从B走最近。23Suppose that instead of using 16 bits for the network part of a class B address originally, 20 bits had been used. How many class B networks would there have been?( 假设B类地址用20bit作为网络号，而不是16bit，总共有多少个B类网？)With a 2-bit prefix, there would have been 18 bits left over to indicate the network.去除2bit类别号（“10”），还有20-2=18bit代表网络号Consequently, the number of networks would have been 218 or 262,144. However, all 0s and all 1s are special, so only 262,142 are available. 218=262144,全0和全1是特殊地址，不分配给网络用，故共有262142个B类网2425 A network on the Internet has a subnet mask of . What is the maximum number of hosts it can handle?(因特网上一个子网的掩码为，它最多能容纳多少台主机？)=11111111.11111111.11110000.00000000 20个1对应网络号和子网号；12个0对应主机编号。The mask is 20 bits long, so the network part is 20 bits. The remaining 12 bits are for the host, so 212-2=4094 host addresses exist另一题：A class B network on the Internet has a subnet mask of . How many subnets in it? And What is the maximum number of hosts each subnet can handle? (Internet 上的一个B类网络的子网掩码为，问该网络划分了多少个子网？每个子网最多可以有多少台主机？) 无答案。已知一台主机的IP地址为6，子网掩码为92。求：该主机所在的网络分了多少个子网？22=4 ? 到底是2还是4?它是位于哪个子网中？编号为01的子网主机号是多少？ 这是C类网C类网前24bit为网络号，即默认掩码为 =1111111,11111111,1111111,00000000 与现在用的子网掩码比较，多的2bit“1”是子网号。22=4，减去全“0”和全“1”的组合，共2个子网（01和10）。26=64,每个子网可容纳62台主机。当前IP地址对应第2个子网的第2台主机。27 A large number of consecutive IP address are available starting at . Suppose that four organizations, A, B, C, and D, request 4000, 2000, 4000, and 8000 addresses, respectively, and in that order. For each of these, give the first IP address assigned, the last IP address assigned, and the mask in the w.x.y.z/s notation.Answer：To start with, all the requests are rounded up to a power of two. 40004096, 20002048.The starting address, ending address, and mask are as follows: A: 198.16.15. 255 written as /20B: 198. 16. 23. 255 written as /21If C start at 28 A router has just received the following new IP addresses: /21, /21, /21, and /21. If all of them use the same outgoing line, can they be aggregated? If so, to what? If not, why not?30 A router has the following (CIDR) entries in its routing table:Address/mask Next hop/22 Interface 0/22 Interface 1/23 Router 1 Default Router 2For each of the following IP addresses, what does the router do if a packet with that address arrives?(a) 0(b) 4(c) (d) (e) 3、 Concepts Exercises a) Draw the TCP/IP reference model in a table, and list two or more protocols in each layer.OSIApplicationPresentationSessionTransportNetworkData linkPhysicalTCP/IP 体系ApplicationTransportInternetLinkb) What layers are there in the OSI reference model and the TCP/IP model? Please sketch the correspondence between the layers of the two models like this:c) What is the main difference between virtual circuit network and datagram network?Answer: Virtual circuit network is connection-oriented while datagram network is connectionless. In a virtual circuit network, a path from the source router to the destination router must be established before any data packets can be sent. That path is called “virtual circuit”. It is tore down after no data is to be sent. Datagram network routes each packet as a separate unit, independent of all others. 虚拟电路网络和数据报网络的区别：虚电路网络是面向连接的而数据报网络是面向无连接的。在虚电路网络里，在传输信息包裹之前，一条路径必须在起始路由器和目标路由器之间建立。那条路径就叫做“虚电路”。数据传输结束之后，要拆除建立的连接路径。而数据报网络将信息分为多个包裹单元来传输，包裹之间相互独立。d) Which of the OSI layers divides the transmitted bit stream into frames? Do frames encapsulate packets or do packets encapsulate frames? Why?4、 帧封装包。因为帧是工作在数据链路层，而数据包工作在网络层，在数据传输时，上一层的的内容有下一层的内容传输，上层向下层进行封装。a) What is the main tasks of the 3rd layer of OSI/RM. 网络层的主要功能是控制子网的运行过程，将分组从源端送到目的端，向传输层提供两类服务：面向连接的和面向无连接的。b) What is the principal difference between connectionless communication and connection-oriented communication?面向连接通信分为三个阶段，第一是建立连接，发出一个建议连接的请求。只有在连接成功建立之后，才能开始数据传输，这里第二阶段。接着，数据传输完毕之后，必须释放连接。而无连接通信没有这么多阶段，它直接进行数据传输。面向连接通信也具有数据的保序性，而无连接通信不能保证数据的顺序与发送数据的顺序一致。c) What is PCM? Why has the PCM sampling time been set at 125usec?Answer: 脉冲编码调制PCM means pulse code modulation. It is the analog-to-digital signal 模拟数字信号 converting technique for transmitting information from the 4-KHz telephone channel. 电话通道According to the Nyquist theorem, the sampling frequency needed to capture all the information in a 4-kHzchannel is 8 KHz. That is to say, a sampling time is 1sec/8000 = 125sec.脉码调制它将4千赫兹的电话信道的模拟信号转化为数字信号。一条普通的电话线路带宽为4KHz，根据奈奎斯特定理：只要每秒4000*2=8000次的采样频率就能获取一个4KHz的信道中的全部信息，再高的采样频率也无意义，所以PCM的采样时间为1/8000=125us。d) Describe the main steps of CSMA/CD.工作原理：一旦检测到有冲突发生，就不再继续传送帧，节省时间和带宽。应用：在LAN中的MAC子层中。工作步骤：发送之前，进行载波侦听。若无载波，采用“1”坚持，立即发送。边发送边检测。若有冲突，立即停止，发送警告等待随即时长，重新开始。若数据错误则采用二元指数退避法或者选择重发送的方法。e) There are exposed terminal problem and hidden terminal problems in wireless LAN. In the case of Figure 4-1, which are exposed terminals? Which are hidden terminals? Figure 4-1Answer: When B sends to A while C sends to D, B and C are exposed stations.If A wants to send to B and C wants to send to B at the same time, C is the hidden station for A, and vice versa. Similarly, when B and D transmit to C at the same time, B and D are hidden stations 当B要发送给A而C要发送给D，B和C都是暴露站。如果A和C想同时发送给B，C对于A来说是隐藏站，反之亦然。同样的，当B和D想同时发送给C，B和D就是隐藏站。f) What is the hidden station problem?Answer： In wireless LAN, consider the figure below, where four wireless stations are illustrated. For our purposes, it does not matter which are base stations and which are notebooks. The radio range is such that A and B are within each others range and can potentially interfere with on