The Fibonacci number sequence {FN} is defined as: F0=0, F1=1, FN=FN−1+FN−2, N=2, 3, .... The time complexity of the function which calculates FN recursively is Θ(N!). (F)
时间复杂度：(3/2)^N，空间复杂度：求FN，需要从F0到FN的值，需要O(N)。
选择题
1 2 3 4 5 6 7 8 9 10
The recurrent equations for the time complexities of programs P1 and P2 are:
Then the correct conclusion about their time complexities is: (B) A.they are both O(logN) B.O(logN) for P1, O(N) for P2 C.they are both O(N) D.O(logN) for P1, O(NlogN) for P2
To merge two singly linked ascending lists, both with N nodes, into one singly linked ascending list, the minimum possible number of comparisons is: (B)
The number of degree 3 nodes in a ternary tree (三叉树) is only related to the number of degree 2 nodes and that of leaf nodes, i.e it has nothing to do with the number of degree 1 nodes. (T)
Using the linear algorithm to build a min-heap from the sequence {15, 26, 32, 8, 7, 20, 12, 13, 5, 19}, and then insert 6. Which one of the following statements is FALSE? (C)
A.The root is 5 B.The path from the root to 26 is {5, 6, 8, 26} C.32 is the left child of 12 D.7 is the parent of 19 and 15
Suppose that the level-order traversal sequence of a min-heap is { 2, 17, 5, 46, 22, 8, 10 }. Use the linear algorithm to adjust this min-heap into a max-heap, and then call DeleteMax. The postorder traversal sequence of the resulting tree is: ()
In a weighted undirected graph, if the length of the shortest path from b to a is 12, and there exists an edge of weight 2 between c and b, then the length of the shortest path from c to a must be no less than 10. (T)
Given an undirected graph G with 16 edges, where 3 vertices are of degree 4, 4 vertices are of degree 3, and all the other vertices are of degrees less than 3. Then G must have at least __ vertices. (B)
During the sorting, processing every element which is not yet at its final position is called a "run". To sort a list of integers using quick sort, it may reduce the total number of recursions by processing the small partion first in each run. (F)
To sort N elements by heap sort, the extra space complexity is: (A)
A.O(1) B.O(logN) C.O(N) D.O(NlogN)
用大顶堆删最大元素法，不需要额外空间。
During the sorting, processing every element which is not yet at its final position is called a "run". Which of the following cannot be the result after the second run of quicksort? ()
Suppose that the numbers {4371, 1323, 6173, 4199, 4344, 9679, 1989} are hashed into a table of size 10 with the hash function h(X)=X%10, and hence have indices {1, 3, 4, 9, 5, 0, 2}. What are their indices after rehashing using h(X)=X%TableSize with linear probing? (C)
Rehashing is required when an insertion to a hash table fails. Which of the following is NOT necessary to rehashing? ()
A.change the collision resolution strategy B.use a new function to hash all the elements into the new table C.build another table that is bigger than the original one D.scan down the entire original hash table for non-deleted elements
let labelString = "Underline Label" let textColor: UIColor = .blue let underLineColor: UIColor = .red let underLineStyle = NSUnderlineStyle.styleSingle.rawValue
let labelAtributes:[NSAttributedStringKey : Any] = [ NSAttributedStringKey.foregroundColor: textColor, NSAttributedStringKey.underlineStyle: underLineStyle,
for family in UIFont.familyNames.sorted() { let names = UIFont.fontNames(forFamilyName: family) print("Family: \(family) Font names: \(names)") }
知道所用字体的名称后，通过以下命令即可。
1 2 3 4 5 6 7 8 9 10
# label为需要改变字体的标签 guard let customFont = UIFont(name: "CustomFont-Light", size: UIFont.labelFontSize) else { fatalError(""" Failed to load the custom font. Make sure the font file is included in the project and the font name is spelled correctly. """) }
打开Xcode并点击File-New-Workspace，存放位置为上述的目录，此处为APP。完成后在左侧点击右键并选择Add Files to ...，选择所有的工程文件，此处为Interface.xcodeproj和Unity-iPhone.xcodeproj。
添加完成后左侧点击Interface工程，选择TARGETS下的APP，在General-Frameworks, Libraries, and Embedded Content下点击+号，选择Unity-iPhone下的UnityFramework.framework。若没有该文件，需要先点击Unity-iPhone工程，设置好签名后运行一次代码，使该Framework得以生成。
然后点击Unity-iPhone下的Data文件夹，在右侧的Target Membership勾选UnityFramework。然后打开Interface工程下的Info.plist，删除Application Scene Manifest一项。
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
#if UNITY_IOS
using System; using System.Linq; using System.Collections.Generic; using System.IO; using System.Text;
using UnityEngine; using UnityEditor; using UnityEditor.Callbacks; using UnityEditor.iOS.Xcode;
/// <summary> /// Adding this post build script to Unity project enables Unity iOS build output to be embedded /// into existing Xcode Swift project. /// /// However, since this script touches Unity iOS build output, you will not be able to use Unity /// iOS build directly in Xcode. As a result, it is recommended to put Unity iOS build output into /// a temporary directory that you generally do not touch, such as '/tmp'. /// /// In order for this to work, necessary changes to the target Xcode Swift project are needed. /// Especially the 'AppDelegate.swift' should be modified to properly initialize Unity. /// See https://github.com/jiulongw/swift-unity for details. /// </summary> public static class XcodePostBuild { /// <summary> /// Path to the root directory of Xcode project. /// This should point to the directory of '${XcodeProjectName}.xcodeproj'. /// It is recommended to use relative path here. /// Current directory is the root directory of this Unity project, i.e. the directory of 'Assets' folder. /// Sample value: "../xcode" /// </summary> private const string XcodeProjectRoot = <PROJECT PATH>;
/// <summary> /// Name of the Xcode project. /// This script looks for '${XcodeProjectName} + ".xcodeproj"' under '${XcodeProjectRoot}'. /// Sample value: "DemoApp" /// </summary> private const string XcodeProjectName = <PROJECT NAME>;
/// <summary> /// Directories, relative to the root directory of the Xcode project, to put generated Unity iOS build output. /// </summary> private const string ClassesProjectPath = XcodeProjectName + "/Unity/Classes"; private const string LibrariesProjectPath = XcodeProjectName + "/Unity/Libraries";
/// <summary> /// Path, relative to the root directory of the Xcode project, to put information about generated Unity output. /// </summary> private const string ExportsConfigProjectPath = XcodeProjectName + "/Unity/Exports.xcconfig";
/// <summary> /// The identifier added to touched file to avoid double edits when building to existing directory without /// replace existing content. /// </summary> private const string TouchedMarker = "https://github.com/jiulongw/swift-unity#v1";
[PostProcessBuild] public static void OnPostBuild(BuildTarget target, string pathToBuiltProject) { if (target != BuildTarget.iOS) { return; }
PatchUnityNativeCode(pathToBuiltProject);
UpdateUnityIOSExports(pathToBuiltProject);
UpdateUnityProjectFiles(pathToBuiltProject); }
/// <summary> /// Writes current Unity version and output path to 'Exports.xcconfig' file. /// </summary> private static void UpdateUnityIOSExports(string pathToBuiltProject) { var config = new StringBuilder(); config.AppendFormat("UNITY_RUNTIME_VERSION = {0};", Application.unityVersion); config.AppendLine(); config.AppendFormat("UNITY_IOS_EXPORT_PATH = {0};", pathToBuiltProject); config.AppendLine();
var configPath = Path.Combine(XcodeProjectRoot, ExportsConfigProjectPath); var configDir = Path.GetDirectoryName(configPath); if (!Directory.Exists(configDir)) { Directory.CreateDirectory(configDir); }
/// <summary> /// Enumerates Unity output files and add necessary files into Xcode project file. /// It only add a reference entry into project.pbx file, without actually copy it. /// Xcode pre-build script will copy files into correct location. /// </summary> private static void UpdateUnityProjectFiles(string pathToBuiltProject) { var pbx = new PBXProject(); var pbxPath = Path.Combine(XcodeProjectRoot, PbxFilePath); pbx.ReadFromFile(pbxPath);
/// <summary> /// Update pbx project file by adding src files and removing extra files that /// exists in dest but not in src any more. /// /// This method only updates the pbx project file. It does not copy or delete /// files in Swift Xcode project. The Swift Xcode project will do copy and delete /// during build, and it should copy files if contents are different, regardless /// of the file time. /// </summary> /// <param name="pbx">The pbx project.</param> /// <param name="src">The directory where Unity project is built.</param> /// <param name="dest">The directory of the Swift Xcode project where the /// Unity project is embedded into.</param> /// <param name="projectPathPrefix">The prefix of project path in Swift Xcode /// project for Unity code files. E.g. "DempApp/Unity/Classes" for all files /// under Classes folder from Unity iOS build output.</param> private static void ProcessUnityDirectory(PBXProject pbx, string src, string dest, string projectPathPrefix) { var targetGuid = pbx.TargetGuidByName(XcodeProjectName); if (string.IsNullOrEmpty(targetGuid)) { throw new Exception(string.Format("TargetGuid could not be found for '{0}'", XcodeProjectName)); }
// newFiles: array of file names in build output that do not exist in project.pbx manifest. // extraFiles: array of file names in project.pbx manifest that do not exist in build output. // Build output files that already exist in project.pbx manifest will be skipped to minimize // changes to project.pbx file. string[] newFiles, extraFiles; CompareDirectories(src, dest, out newFiles, out extraFiles);
foreach (var f in newFiles) { if (ShouldExcludeFile(f)) { continue; }
var projPath = Path.Combine(projectPathPrefix, f); if (!pbx.ContainsFileByProjectPath(projPath)) { var guid = pbx.AddFile(projPath, projPath); pbx.AddFileToBuild(targetGuid, guid);
Debug.LogFormat("Added file to pbx: '{0}'", projPath); } }
foreach (var f in extraFiles) { var projPath = Path.Combine(projectPathPrefix, f); if (pbx.ContainsFileByProjectPath(projPath)) { var guid = pbx.FindFileGuidByProjectPath(projPath); pbx.RemoveFile(guid);
Debug.LogFormat("Removed file from pbx: '{0}'", projPath); } } }
/// <summary> /// Compares the directories. Returns files that exists in src and /// extra files that exists in dest but not in src any more. /// </summary> private static void CompareDirectories(string src, string dest, out string[] srcFiles, out string[] extraFiles) { srcFiles = GetFilesRelativePath(src);
var destFiles = GetFilesRelativePath(dest); var extraFilesSet = new HashSet<string>(destFiles);
/// <summary> /// Make necessary changes to Unity build output that enables it to be embedded into existing Xcode project. /// </summary> private static void PatchUnityNativeCode(string pathToBuiltProject) { EditMainMM(Path.Combine(pathToBuiltProject, "Classes/main.mm")); EditUnityAppControllerH(Path.Combine(pathToBuiltProject, "Classes/UnityAppController.h")); EditUnityAppControllerMM(Path.Combine(pathToBuiltProject, "Classes/UnityAppController.mm"));
if (Application.unityVersion == "2017.1.1f1") { EditMetalHelperMM(Path.Combine(pathToBuiltProject, "Classes/Unity/MetalHelper.mm")); }
// TODO: Parse unity version number and do range comparison. if (Application.unityVersion.StartsWith("2017.3.0f") || Application.unityVersion.StartsWith("2017.3.1f") || Application.unityVersion.StartsWith("2017.4.1f") || Application.unityVersion.StartsWith("2017.4.2f")) { EditSplashScreenMM(Path.Combine(pathToBuiltProject, "Classes/UI/SplashScreen.mm")); } }
/// <summary> /// Edit 'main.mm': removes 'main' entry that would conflict with the Xcode project it embeds into. /// </summary> private static void EditMainMM(string path) { EditCodeFile(path, line => { if (line.TrimStart().StartsWith("int main", StringComparison.Ordinal)) { return line.Replace("int main", "int old_main"); }
return line; }); }
/// <summary> /// Edit 'UnityAppController.h': returns 'UnityAppController' from 'AppDelegate' class. /// </summary> private static void EditUnityAppControllerH(string path) { var inScope = false; var markerDetected = false; var markerAdded = false;
if (inScope && line.Trim() == "}") { inScope = false;
if (markerDetected) { return new string[] { line }; } else { return new string[] { " // Modified by " + TouchedMarker, " // Post a notification so that Swift can load unity view once started.", @" [[NSNotificationCenter defaultCenter] postNotificationName: @""UnityReady"" object:self];", "}", }; } }
return new string[] { line }; }); }
/// <summary> /// Edit 'MetalHelper.mm': fixes a bug (only in 2017.1.1f1) that causes crash. /// </summary> private static void EditMetalHelperMM(string path) { var markerDetected = false;
EditCodeFile(path, line => { markerDetected |= line.Contains(TouchedMarker);
if (!markerDetected && line.Trim() == "surface->stencilRB = [surface->device newTextureWithDescriptor: stencilTexDesc];") { return new string[] { "", " // Modified by " + TouchedMarker, " // Default stencilTexDesc.usage has flag 1. In runtime it will cause assertion failure:", " // validateRenderPassDescriptor:589: failed assertion `Texture at stencilAttachment has usage (0x01) which doesn't specify MTLTextureUsageRenderTarget (0x04)'", " // Adding MTLTextureUsageRenderTarget seems to fix this issue.", " stencilTexDesc.usage |= MTLTextureUsageRenderTarget;", line, }; }
return new string[] { line }; }); }
/// <summary> /// Edit 'SplashScreen.mm': Unity introduces its own 'LaunchScreen.storyboard' since 2017.3.0f3. /// Disable it here and use Swift project's launch screen instead. /// </summary> private static void EditSplashScreenMM(string path) { var markerDetected = false; var markerAdded = false; var inScope = false; var level = 0;
然后用以下仓库中的AppDelegate.swift、Main.storyboard和ViewController.swift替换掉原工程的对应文件，具体方法为先以Move to trash的方式删除原工程的文件，再通过Copy items if needed和Create groups的方式拖动加入以上文件。
# 从文件夹中读取图片集，并收集其label # label为每个图片的名称，一般需要提前对图片重命名为对应的实体，如飞机等 def load_data_from_folder(self, dir): # read all images into an image collection ic = io.ImageCollection(self.folder + dir + '*.bmp',load_func=self.imread_convert)
# create one large array of image data data = io.concatenate_images(ic) # extract labels from image names labels = np.array(ic.files) for i, f in enumerate(labels): m = re.search('_', f) labels[i] = (f[len(dir):m.start()]).split('/')[-1] return(data,labels)
(1) Imagine that you have trained your St. Bernard, Bernie, to carry a box of three 8mm tapes instead of a flask of brandy. (When your disk fills up, you consider that an emergency.) These tapes each contain 7 gigabytes. The dog can travel to your side, wherever you may be, at 18 km/hour. For what range of distances does Bernie have a higher data rate than a transmission line whose data rate (excluding overhead) is 150 Mbps?
Sol.
7 * 1024 * 8 * 3 / (d / 5) = 150 d = 5734.4m
Wrong!
1 kbps = 1000 bit/s 1024 should be 1000 d = 5600m
(2) An alternative to a LAN is simply a big timesharing system with terminals for all users. Give two advantages of a client-server system using a LAN.
(3) The performance of a client-server system is influenced by two network factors: the bandwidth of the network (how many bits/sec it can transport) and the latency (how many seconds it takes for the first bit to get from the client to the server). Give an example of a network that exhibits high bandwidth and high latency. Then give an example of one with low bandwidth and low latency.
Sol.
(1). 下载大型文件，建立连接需要很久，一旦建立下载很快 (2). 语音通话，不能有高延迟
A transcontinental fiber link might have many gigabits/sec of bandwidth, but the latency will also be high due to the speed of light propagation over thousands of kilometers. In contrast, a 56-kbps modem calling a computer in the same building has low bandwidth and low latency.
(4) Besides bandwidth and latency, what other parameter is needed to give a good characterization of the quality of service offered by a network used for digitized voice traffic?
Sol.
(1) 丢包率 (2) 安全性 (3) 断点传输 (4) 对语音通话而言，统一的传输时间也很重要
(5) A factor in the delay of a store-and-forward packet-switching system is how long it takes to store and forward a packet through a switch. If switching time is 10 μsec, is this likely to be a major factor in the response of a client-server system where the client is in New York and the server is in California? Assume the propagation speed in copper and fiber to be 2/3 the speed of light in vacuum.
Sol.
2000km / 200000km/s = 10ms
It won't be a major factor.
(6) A client-server system uses a satellite network, with the satellite at a height of 40,000 km. What is the best-case delay in response to a request?
Sol.
40,000 * 2 / 300000 = 267ms
(7) In the future, when everyone has a home terminal connected to a computer network, instant public referendums on important pending legislation will become possible. Ultimately, existing legislatures could be eliminated, to let the will of the people be expressed directly. The positive aspects of such a direct democracy are fairly obvious; discuss some of the negative aspects.
Sol.
安全性存在问题
(8) A collection of five routers is to be connected in a point-to-point subnet. Between each pair of routers, the designers may put a high-speed line, a medium-speed line, a low-speed line, or no line. If it takes 100 ms of computer time to generate and inspect each topology, how long will it take to inspect all of them?
Sol.
4 ^ (4 + 3 + 2 + 1) * 100ms = more than one day
(9) A disadvantage of a broadcast subnet is the capacity wasted when multiple hosts attempt to access the channel at the same time. As a simplistic example, suppose that time is divided into discrete slots, with each of the n hosts attempting to use the channel with probability p during each slot. What fraction of the slots are wasted due to collisions?
Sol.
P = 1 - n * p * (1 - p) ^ (n - 1) - p ^ n
(10) What are two reasons for using layered protocols?
(11) The president of the Specialty Paint Corp. gets the idea to work with a local beer brewer to produce an invisible beer can (as an anti-litter measure). The president tells her legal department to look into it, and they in turn ask engineering for help. As a result, the chief engineer calls his counterpart at the other company to discuss the technical aspects of the project. The engineers then report back to their respective legal departments, which then confer by telephone to arrange the legal aspects. Finally, the two corporate presidents discuss the financial side of the deal. Is this an example of a multilayer protocol in the sense of the OSI model?
Sol.
除了第一层（最底层，这里是engineer），高层之间不能有直接通信。
(12) What is the principal difference between connectionless communication and connection-oriented communication?
Sol.
面向连接的服务是先建立连接再通信。无连接服务是在传输时候带上目标地址，然后交由网络去通信。
(13) Two networks each provide reliable connection-oriented service. One of them offers a reliable byte stream and the other offers a reliable message stream. Are these identical? If so, why is the distinction made? If not, give an example of how they differ.
Sol.
message的话每条信息有确定边界，而byte stream则没有确定边界。
(14) What does ''negotiation'' mean when discussing network protocols? Give an example.
Sol.
协商就是建立一个双方接受的通信规则。
(15) Which of the OSI layers handles each of the following: a. (a) Dividing the transmitted bit stream into frames. b. (b) Determining which route through the subnet to use.
Sol.
Transmission Layer and Network Layer
Wrong!
Data link layer and Network layer
这里很重要，数据是在data link层被划分为帧（frame）的
(16) If the unit exchanged at the data link level is called a frame and the unit exchanged at the network level is called a packet, do frames encapsulate packets or do packets encapsulate frames? Explain your answer.
Sol.
高层的应该被封到低层里去。
(17) A system has an n-layer protocol hierarchy. Applications generate messages of length M bytes. At each of the layers, an h-byte header is added. What fraction of the network bandwidth is filled with headers?
Sol.
hn / (M + hn)
(18) List two ways in which the OSI reference model and the TCP/IP reference model are the same. Now list two ways in which they differ.
Sol.
OSI: Application Representation Session Transmission Network Data link Physical
TCP/IP: Application: HTTP, SMTP, RTP, DNS Transmission: TCP, UDP internet: IP (Internet Protocal), ICMP Link: DSL, SONET, 802.11, Ethernet
(19) What is the main difference between TCP and UDP?
Sol.
TCP is connection oriented, reliable, fast. UDP is connectionless oriented, unreliable, slow.
(20) When a file is transferred between two computers, two acknowledgement strategies are possible. In the first one, the file is chopped up into packets, which are individually acknowledged by the receiver, but the file transfer as a whole is not acknowledged. In the second one, the packets are not acknowledged individually, but the entire file is acknowledged when it arrives. Discuss these two approaches.
Sol.
If the network is reliable, use the second one.
(21) How long was a bit on the original 802.3 standard in meters? Use a transmission speed of 10 Mbps and assume the propagation speed in coax is 2/3 the speed of light in vacuum.
Sol.
802.3是以太网，这里计算出来是20米
(22) An image is 1024 x 768 pixels with 3 bytes/pixel. Assume the image is uncompressed. How long does it take to transmit it over a 56-kbps modem channel? Over a 1-Mbps cable modem? Over a 10-Mbps Ethernet? Over 100-Mbps Ethernet?
Sol.
337s, 19s, 1.9s, 0.19s
(23) Ethernet and wireless networks have some similarities and some differences. One property of Ethernet is that only one frame at a time can be transmitted on an Ethernet. Does 802.11 share this property with Ethernet? Discuss your answer.
Sol.
Wireless networks also transmit one frame at a time, but determining when one can send is more difficult. Ethernet is a broadcast bus so the sender can just listen to see if there is any traffic before sending. Due to range issues with wireless, a sender cannot be sure that there are not other transmissions just because it cannot "hear" other transmissions. Wireless senders use either a central base station or use methods discussed in Chapter 4 to avoid collisions.
(24) Wireless networks are easy to install, which makes them inexpensive since installation costs usually far overshadow equipment costs. Nevertheless, they also have some disadvantages. Name two of them.
Sol.
无法控制范围，容易被人利用。任何人可以接收到传送中的包。 此外，传输更慢。
(25) List two advantages and two disadvantages of having international standards for network protocols.
(1) Give two example computer applications for which connection-oriented service is appropriate. Now give two examples for which connectionless service is best.
Sol.
面向连接服务：SSH，文件传输
无连接服务：视频通话，游戏在线对战，需要快速应答的服务一般需要无连接服务。
(2) Are there any circumstances when connection-oriented service will (or at least should) deliver packets out of order? Explain.
(3) Datagram subnets route each packet as a separate unit, independent of all others. Virtual-circuit subnets do not have to do this, since each data packet follows a predetermined route. Does this observation mean that virtual-circuit subnets do not need the capability to route isolated packets from an arbitrary source to an arbitrary destination? Explain your answer.
Sol.
并不是如此，虚电路网络对不同方向的数据包需要建立不同的虚电路，因此也要具备这样的能力。
补充：在建立虚电路的时候需要把setup package从任意端传输到任意接收方。
(4) Give three examples of protocol parameters that might be negotiated when a connection is set up.
Sol.
IP协议，协商IP包的最大跳数，是否可以分段，还有出错时的处理方式。
(5) Consider the following design problem concerning implementation of virtual-circuit service. If virtual circuits are used internal to the subnet, each data packet must have a 3-byte header and each router must tie up 8 bytes of storage for circuit identification. If datagrams are used internally, 15-byte headers are needed but no router table space is required. Transmission capacity costs 1 cent per 106 bytes, per hop. Very fast router memory can be purchased for 1 cent per byte and is depreciated over two years, assuming a 40-hour business week. The statistically average session runs for 1000 sec, in which time 200 packets are transmitted. The mean packet requires four hops. Which implementation is cheaper, and by how much?
(6) Assuming that all routers and hosts are working properly and that all software in both is free of all errors, is there any chance, however small, that a packet will be delivered to the wrong destination?
Sol.
有可能，当有ip冲突或者传输过程中发生ip地址变更的情况。
Wrong!
答案是错误可能出在低层上，比如物理层
(7) Give a simple heuristic for finding two paths through a network from a given source to a given destination that can survive the loss of any communication line (assuming two such paths exist). The routers are considered reliable enough, so it is not necessary to worry about the possibility of router crashes.
Sol.
先找出一条最短路径，再把这条路径删除，找出另一条最短路径。只要两条路径没有公共部分即可。
(8) 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 C's new routing table? Give both the outgoing line to use and the expected delay.
Sol.
这题是距离矢量算法。
C 到 A 11 经过 B A 11 B B 6 B C 0 - D 3 D E 5 E F 8 B (9) If delays are recorded as 8-bit numbers in a 50-router network, and delay vectors are exchanged twice a second, how much bandwidth per (full-duplex) line is chewed up by the distributed routing algorithm? Assume that each router has three lines to other routers.
Sol.
每个路由器需要维护一张400bit的表，因此传输0.5s一次会浪费单个方向800bps的带宽
(10) In Fig. 5-14 the Boolean OR of the two sets of ACF bits are 111 in every row. Is this just an accident here, or does it hold for all subnets under all circumstances?
Sol.
这题讲的是链路状态路由算法。
这个永远是对的，ACK标志标志表示来自哪里，它可能由两条路线过来，而发送标志表示要发送往哪里。
(11) For hierarchical routing with 4800 routers, what region and cluster sizes should be chosen to minimize the size of the routing table for a three-layer hierarchy? A good starting place is the hypothesis that a solution with k clusters of k regions of k routers is close to optimal, which means that k is about the cube root of 4800 (around 16). Use trial and error to check out combinations where all three parameters are in the general vicinity of 16.
Sol.
这题讲的是层次路由。
层次可以分许多层，和网络中路由器的数量规模有关。
16 15 20
(12) In the text it was stated that when a mobile host is not at home, packets sent to its home LAN are intercepted by its home agent on that LAN. For an IP network on an 802.3 LAN, how does the home agent accomplish this interception?
Sol.
家乡代理拥有主机的IP地址即可截获，有什么问题吗？
Conceivably it might go into promiscuous mode, reading all frames dropped onto the LAN, but this is very inefficient. Instead, what is normally done is that the home agent tricks the router into thinking it is the mobile host by re- sponding to ARP requests. When the router gets an IP packet destined for the mobile host, it broadcasts an ARP query asking for the 802.3 MAC-level ad- dress of the machine with that IP address. When the mobile host is not around, the home agent responds to the ARP, so the router associates the mobile user’s IP address with the home agent’s 802.3 MAC-level address.
(13) Looking at the subnet of Fig. 5-6, how many packets are generated by a broadcast from B, using a. (a)reverse path forwarding? b. (b)the sink tree?
(14) Suppose that node B in Fig. 5-20 has just rebooted and has no routing information in its tables. It suddenly needs a route to H. It sends out broadcasts with TTL set to 1, 2, 3, and so on. How many rounds does it take to find a route?
(15) As a possible congestion control mechanism in a subnet using virtual circuits internally, a router could refrain from acknowledging a received packet until (1) it knows its last transmission along the virtual circuit was received successfully and (2) it has a free buffer. For simplicity, assume that the routers use a stop-and-wait protocol and that each virtual circuit has one buffer dedicated to it for each direction of traffic. If it takes T sec to transmit a packet (data or acknowledgement) and there are n routers on the path, what is the rate at which packets are delivered to the destination host? Assume that transmission errors are rare and that the host-router connection is infinitely fast.
Sol.
讲的是拥塞控制，这个方法不好，需要前一个包完全确认了才能传输下一个包。
The protocol is terrible. Let time be slotted in units of T sec. In slot 1 the source router sends the first packet. At the start of slot 2, the second router has received the packet but cannot acknowledge it yet. At the start of slot 3, the third router has received the packet, but it cannot acknowledge it either, so all the routers behind it are still hanging. The first acknowledgement can only be sent when the destination host takes the packet from the destination router. Now the acknowledgement begins propagating back. It takes two full transits of the network, 2(n − 1)T sec, before the source router can send the second packet. Thus, the throughput is one packet every 2(n − 1)T sec.
(17) Describe two major differences between the ECN and the RED method.
RED (Random Early Detection, 随机早期检测), 路由器维护一个运行队列长度的平均值，当超过阈值的时候就开始随机丢弃数据包，快速发送方发现丢包就开始降低发送速率。
主要区别是一个显式通知，一个隐式通知，一个是缓存区开始不够了才通知，另一个是提前预知。
(18) An ATM network uses a token bucket scheme for traffic shaping. A new token is put into the bucket every 5 μsec. Each token is good for one cell, which contains 48 bytes of data. What is the maximum sustainable data rate?
Sol.
With a token every 5 μsec, 200,000 cells/sec can be sent. Each packet holds 48 data bytes or 384 bits. The net data rate is then 76.8 Mbps.
(19) A computer on a 6-Mbps network is regulated by a token bucket. The token bucket is filled at a rate of 1 Mbps. It is initially filled to capacity with 8 megabits. How long can the computer transmit at the full 6 Mbps?
Sol.
8 / (6 - 1) = 1.6s
(21) The CPU in a router can process 2 million packets/sec. The load offered to it is 1.5 million packets/sec. If a route from source to destination contains 10 routers, how much time is spent being queued and serviced by the CPUs?
(22) Consider the user of differentiated services with expedited forwarding. Is there a guarantee that expedited packets experience a shorter delay than regular packets? Why or why not?
Sol.
不保证，过多包被标记为加速的，那么可能反而变慢了。
(23) Suppose that host A is connected to a router R 1, R 1 is connected to another router, R 2, and R 2 is connected to host B. Suppose that a TCP message that contains 900 bytes of data and 20 bytes of TCP header is passed to the IP code at host A for delivery to B. Show the Total length, Identification, DF, MF, and Fragment offset fields of the IP header in each packet transmitted over the three links. Assume that link A-R1 can support a maximum frame size of 1024 bytes including a 14-byte frame header, link R1-R2 can support a maximum frame size of 512 bytes, including an 8-byte frame header, and link R2-B can support a maximum frame size of 512 bytes including a 12- byte frame header.
Sol.
Link A-R1 : Length: 900 + 20 (TCP) + 20 (IP) = 940 Bytes, ID:X , DF:0 , MF:0 , Fragment offset:0 Link R1-R2: (1) Length = 500; ID = x; DF = 0; MF = 1; Offset = 0 (2) Length = 460; ID = x; DF = 0; MF = 0; Offset = 60 Link R2-B: (1) Length = 500; ID = x; DF = 0; MF = 1; Offset = 0 (2) Length = 460; ID = x; DF = 0; MF = 0; Offset = 60 不用去考虑数据链路层的成帧部分，IP协议不关心。 (24) A router is blasting out IP packets whose total length (data plus header) is 1024 bytes. Assuming that packets live for 10 sec, what is the maximum line speed the router can operate at without danger of cycling through the IP datagram ID number space?
Sol.
IP包的ID字段拥有16位，因此65536个不同编号
65536 ＊ 1024 * 8 / 10 = 54 Gbps
(25) An IP datagram using the Strict source routing option has to be fragmented. Do you think the option is copied into each fragment, or is it sufficient to just put it in the first fragment? Explain your answer.
(26) Suppose 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?
Sol.
B类地址，前缀10定死，因此18bits可以用，所以有2^18个B类网络。
(28) A network on the Internet has a subnet mask of 255.255.240.0. What is the maximum number of hosts it can handle?
Sol.
4096
(29) 为什么以太网地址不能特定于一个网络，而IP地址却可以？
Sol.
Each Ethernet adapter sold in stores comes hardwired with an Ethernet (MAC) address in it. When burning the address into the card, the manufac- turer has no idea where in the world the card will be used, making the address useless for routing. In contrast, IP addresses are either assigned either stati- cally or dynamically by an ISP or company, which knows exactly how to get to the host getting the IP address.
(30) A large number of consecutive IP address are available starting at 198.16.0.0. 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.
Sol.
A: 198.16.0.0 – 198.16.15.255 written as 198.16.0.0/20 B: 198.16.16.0 – 198.23.15.255 written as 198.16.16.0/21 C: 198.16.32.0 – 198.47.15.255 written as 198.16.32.0/20 D: 198.16.64.0 – 198.95.15.255 written as 198.16.64.0/19 (31) A router has just received the following new IP addresses: 57.6.96.0/21, 57.6.104.0/21, 57.6.112.0/21, and 57.6.120.0/21. If all of them use the same outgoing line, can they be aggregated? If so, to what? If not, why not?
(32) The set of IP addresses from 29.18.0.0 to 19.18.128.255 has been aggregated to 29.18.0.0/17. However, there is a gap of 1024 unassigned addresses from 29.18.60.0 to 29.18.63.255 that are now suddenly assigned to a host using a different outgoing line. Is it now necessary to split up the aggregate address into its constituent blocks, add the new block to the table, and then see if any reaggregation is possible? If not, what can be done instead?
Sol.
不需要，因为有最长匹配，所以单独聚合即可。
(34) Many companies have a policy of having two (or more) routers connecting the company to the Internet to provide some redundancy in case one of them goes down. Is this policy still possible with NAT? Explain your answer.
Sol.
After NAT is installed, it is crucial that all the packets pertaining to a single connection pass in and out of the company via the same router, since that is where the mapping is kept. If each router has its own IP address and all traffic belonging to a given connection can be sent to the same router, the mapping can be done correctly and multihoming with NAT can be made to work.
所以是可以的，只要网络中的每个主机发给特定router即可。
(36) Describe a way to reassemble IP fragments at the destination.
Sol.
In the general case, the problem is nontrivial. Fragments may arrive out of order and some may be missing. On a retransmission, the datagram may be fragmented in different-sized chunks. Furthermore, the total size is not known until the last fragment arrives. Probably the only way to handle reassembly is to buffer all the pieces until the last fragment arrives and the size is known. Then build a buffer of the right size, and put the fragments into the buffer, maintaining a bit map with 1 bit per 8 bytes to keep track of which bytes are present in the buffer. When all the bits in the bit map are 1, the datagram is complete.
所以就是等尾巴来，就可以确定总长度，然后等所有分段都来就可以重组了。
(37) Most IP datagram reassembly algorithms have a timer to avoid having a lost fragment tie up reassembly buffers forever. Suppose that a datagram is fragmented into four fragments. The first three fragments arrive, but the last one is delayed. Eventually, the timer goes off and the three fragments in the receiver's memory are discarded. A little later, the last fragment stumbles in. What should be done with it?
Sol.
前三段已经被discard了，那么第四段再来会被当成新的，过一段时间一样被扔。
(38) In both IP and ATM, the checksum covers only the header and not the data. Why do you suppose this design was chosen?
Sol.
其他部分的checksum可以交给上层协议，而且开销太大，此外头的错误非常严重。
(39) A person who lives in Boston travels to Minneapolis, taking her portable computer with her. To her surprise, the LAN at her destination in Minneapolis is a wireless IP LAN, so she does not have to plug in. Is it still necessary to go through the entire business with home agents and foreign agents to make e-mail and other traffic arrive correctly?
Sol.
当然需要，无线网是数据链路层和物理层的事情，和IP层无关，还是要利用家乡代理。
(41) The Protocol field used in the IPv4 header is not present in the fixed IPv6 header. Why not?
Sol.
因为在IPv6头中有一个字段叫下一个头，会说明该字段要交给哪一种上层协议处理。
(42) When the IPv6 protocol is introduced, does the ARP protocol have to be changed? If so, are the changes conceptual or technical?
(1) In our example transport primitives of Fig.6-2, LISTEN is a blocking call. Is this strictly necessary? If not, explain how a nonblocking primitive could be used. What advantage would this have over the scheme described in the text?
Sol.
The LISTEN call could indicate a willingness to establish new connections but not block. When an attempt to connect was made, the caller could be given a signal. It would then execute, say, OK or REJECT to accept or reject the con- nection. In our original scheme, this flexibility is lacking.
(7) Suppose that the clock-driven scheme for generating initial sequence numbers isused with a 15-bit wide clock counter. The clock ticks once every 100 msec, and the maximum packet lifetime is 60 sec. How often need resynchronization take place a. (a)in the worst case? b. (b)when the data consumes 240 sequence numbers/min?
(9) Imagine that a two-way handshake rather than a three-way handshake were used to set up connections. In other words, the third message was not required. Are deadlocks now possible? Give an example or show that none exist.
Sol.
有可能出问题，主机2的确认被延迟了，那么可能会建立起一个重复的连接。
(11) Consider the problem of recovering from host crashes (i.e.,Fig.6-18). If the interval between writing and sending an acknowledgement, or vice versa, can be made relatively small, what are the two best sender-receiver strategies for minimizing the chance of a protocol failure?
Sol.
If the AW or WA time is small, the events AC(W) and WC(A) are unlikely events. The sender should retransmit in state S1; the receiver’s order does not matter.
(13) Discuss the advantages and disadvantages of credits versus sliding window protocols.
Sol.
滑动窗口协议用于流量控制。
The sliding window is simpler, having only one set of parameters (the win- dow edges) to manage. Furthermore, the problem of a window being increased and then decreased, with the segments arriving in the wrong order, does not occur. However, the credit scheme is more flexible, allowing a dynamic management of the buffering, separate from the acknowledgements.
(14) 拥塞控制的公平性方面的策略，加法递增乘法递减(AIMD).
(15) Why does UDP exist? Would it not have been enough to just let user processes send raw IP packets?
Sol.
无法确认端口。
(17) A client sends a 128-byte request to a server located 100 km away over a 1-gigabit optical fiber. What is the efficiency of the line during the remote procedure call?
(19) Both UDP and TCP use port numbers to identify the destination entity when delivering a message. Give two reasons for why these protocols invented a new abstract ID (port numbers), instead of using process IDs, which already existed when these protocols were designed.
Sol.
进程id动态变化，不易管理，端口号可以被进程绑定，而且一些知名服务需要用固定端口号。
Here are three reasons. First, process IDs are OS-specific. Using process IDs would have made these protocols OS-dependent. Second, a single process may establish multiple channels of communications. A single process ID (per process) as the destination identifier cannot be used to distinguish between these channels. Third, having processes listen on well-known ports is easy, but well-known process IDs are impossible.
(23) RTP is used to transmit CD-quality audio, which makes a pair of 16-bit samples 44,100 times/sec, one sample for each of the stereo channels. How many packets per second must RTP transmit?
Sol.
Each sample occupies 4 bytes. This gives a total of 256 samples per packet. There are 44,100 samples/sec, so with 256 samples/packet, it takes 44100/256 or 172 packets to transmit one second’s worth of music.
按照标准答案的理解，RTP的一个packet只能传输1024字节，不清楚这个规定是在哪里。
(25) Would it be possible to place the RTP code in the operating system kernel, along with the UDP code? Explain your answer.
Sol.
应该要分开，RTP是基于UDP的协议，其他应用程序也要调用UDP，因此最好可以把两段代码分开。
错了！
Sure. The caller would have to provide all the needed information, but there is no reason RTP could not be in the kernel, just as UDP is.
(30) Consider the effect of using slow start on a line with a 10-msec round-trip time and no congestion. The receive window is 24 KB and the maximum segment size is 2 KB. How long does it take before the first full window can be sent?
Sol.
慢速启动是TCP协议中拥塞控制的一个算法，略看。The first bursts contain 2K, 4K, 8K, and 16K bytes, respectively. The next one is 24 KB and occurs after 40 msec.
(31) Suppose that the TCP congestion window is set to 18 KB and a timeout occurs. How big will the window be if the next four transmission bursts are all successful? Assume that the maximum segment size is 1 KB.
Sol.
也是拥塞控制的算法，TCP维护一个拥塞窗口，略看。The next transmission will be 1 maximum segment size. Then 2, 4, and 8. So after four successes, it will be 8 KB.
(33) A TCP machine is sending full windows of 65,535 bytes over a 1-Gbps channel that has a 10-msec one-way delay. What is the maximum throughput achievable? What is the line efficiency?
Sol.
One window can be sent every 20 msec. This gives 50 windows/sec, for a maximum data rate of about 3.3 million bytes/sec. The line efficiency is then 26.4 Mbps/1000 Mbps or 2.6 percent.
因此有延迟的网络传输效率和窗口大小，延迟有很大关系。
(34) What is the fastest line speed at which a host can blast out 1500-byte TCP payloads with a 120-sec maximum packet lifetime without having the sequence numbers wrap around? Take TCP, IP, and Ethernet overhead into consideration. Assume that Ethernet frames may be sent continuously.
The goal is to send 2^32 bytes in 120 sec or 35,791,394 payload bytes/sec. This is 23,860 1500-byte frames/sec. The TCP overhead is 20 bytes. The IP overhead is 20 bytes. The Ethernet overhead is 26 bytes. This means that for 1500 bytes of payload, 1566 bytes must be sent. If we are to send 23,860 frames of 1566 bytes every second, we need a line of 299 Mbps. With any- thing faster than this we run the risk of two different TCP segments having the same sequence number at the same time.
(35) 为什么那么多人在为了ipv4的局限性做努力，而对TCP的局限性却没有人这样做。
Sol.
根本原因是IP协议运行在所有路由器上。
IP is a network level protocol while TCP is an end-to-end transport level protocol. Any change in the protocol specification of IP must be incorporated on all routers in the Internet. On the other hand, TCP can works fine as long as the two end points are running compatible versions. Thus, it is possible to have many different versions of TCP running at the same time on different hosts, but not this is not the case with IP.
(36) In a network that has a maximum TPDU size of 128 bytes, a maximum TPDU lifetime of 30 sec, and an 8-bit sequence number, what is the maximum data rate per connection?
Sol.
TPDU:Transport Protocol Data Unit 协议数据单元。
2 ^ 8 * 128 * 8 / 30 = 8.7kbps
(37) Suppose that you are measuring the time to receive a TPDU. When an interrupt occurs, you read out the system clock in milliseconds. When the TPDU is fully processed, you read out the clock again. You measure 0 msec 270,000 times and 1 msec 730,000 times. How long does it take to receive a TPDU?
Sol.
27次是0ms，73次是1ms，那么平均是730us。
(38) A CPU executes instructions at the rate of 1000 MIPS. Data can be copied 64 bits at a time, with each word copied costing 10 instructions. If an coming packet has to be copied four times, can this system handle a 1-Gbps line? For simplicity, assume that all instructions, even those instructions that read or write memory, run at the full 1000- MIPS rate.
Sol.
1000M * 64 /10 / 4 = 1.6 Gbps > 1Gbps 可以.
(41) For a 1-Gbps network operating over 4000 km, the delay is the limiting factor, not the bandwidth. Consider a MAN with the average source and destination 20 km apart. At what data rate does the round-trip delay due to the speed of light equal the transmission delay for a 1-KB packet?
(43) What is the bandwidth-delay product for a 50-Mbps channel on a geostationary satellite? If the packets are all 1500 bytes (including overhead), how big should the window be in packets?
Sol.
The round-trip delay is about 540 msec, so with a 50-Mbps channel the bandwidth-product delay is 27 megabits or 3,375,000 bytes. With packets of 1500 bytes, it takes 2250 packets to fill the pipe, so the window should be at least 2250 packets.
