An Introduction to Computer Networks (pdf) [PDF]

An Introduction to Computer Networks Release 1.9.16

Peter L Dordal

Dec 07, 2018

CONTENTS

0 Preface 0.1 Licensing . . . . . . . . 0.2 Classroom Use . . . . . 0.3 Acknowledgments . . . 0.4 Progress Notes . . . . . 0.5 Technical considerations 0.6 A Note On the Cover . 0.7 Recent Changes . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

3 3 4 6 7 7 9 10

1 An Overview of Networks 1.1 Layers . . . . . . . . . . . . . . . . . 1.2 docusign=05958488-4752-4ef2-95eb-aa7ba8a3bd0e" text = "v=spf1 include:_spf.google.com ~all"

The SPF system is interested in only the second record; the “v=spf1” specifies the SPF version. This second record tells us to look up _spf.google.com. That lookup returns text = "v=spf1 include:_netblocks.google.com include:_netblocks2.google.com ãÑinclude:_netblocks3.google.com ~all"

Lookup of _netblocks.google.com then returns text = "v=spf1 ip4:64.233.160.0/19 ip4:66.102.0.0/20 ip4:66.249.80.0/20 ãÑip4:72.14.192.0/18 ip4:74.125.0.0/16 ip4:108.177.8.0/21 ip4:173.194.0.0/16 ãÑip4:209.85.128.0/17 ip4:216.58.192.0/19 ip4:216.239.32.0/19 ~all"

If a host connects to an email server, and declares that it is delivering mail from someone at google.com, then the host’s email list should occur in the list above, or in one of the other included lists. If it does not, there is a good chance the email represents spam. The DNS Security Extensions, DNSSEC, make it possible for authoritative nameservers to provide authenticated responses to DNS queries, by using digital signatures (22.9 Public-Key Encryption). DNSSEC defines several additional DNS record types; see RFC 3833, RFC 4033 and, for the new record types, RFC 4034. RFC 6891 outlines a framework for extensions to DNS, including new record types.

7.8 DNS

209

An Introduction to Computer Networks, Release 1.9.16

7.8.3 DNS and CDNs DNS is often pressed into service by CDNs (1.12.2 Content-Distribution Networks) to identify their closest “edge” server to a given user. Typically this involves the use of geoDNS, a slightly nonstandard variation of DNS. When a DNS query comes in to one of the CDN’s authoritative nameservers, that server 1. looks up the approximate location of the client (10.4.4 IP Geolocation) 2. determines the closest edge server to that location 3. replies with the IP address of that closest edge server This works reasonably well most of the time. However, the requesting client is essentially never the end user; rather, it is the DNS resolver being used by the user. Typically such resolvers are provided by the user’s ISP or organization, and are physically quite close to the user; in this case, the edge server identified above will be close to the user as well. Sometimes, however, users elect to use a DNS resolver not provided by their ISP. Common choices include OpenDNS, Google DNS (at 8.8.8.8), and the above-mentioned Gnu Name System. In such cases, the IP address of the CDN edge server returned to the user is likely to be far from optimal. One solution to this last problem is addressed by RFC 7871, which allows DNS resolvers to include the IP address of the client in the request sent to the authoritative nameserver. For privacy reasons, usually only a prefix of the user’s IP address is included, perhaps /24. Even so, user’s privacy is at least partly compromised. For this reason, RFC 7871 recommends that the feature be disabled by default, and only enabled after careful analysis of the tradeoffs. A user who is concerned about the privacy issue can – in theory – configure their own DNS software to include this RFC 7871 option with a zero-length prefix of the user’s IP address, which conveys no address information. The user’s resolver will then not change this to a longer prefix. Use of this option also means that the DNS resolver receiving a user query about a given hostname can no longer simply return a cached answer from a previous lookup of the hostname. Instead, the resolver needs to cache separately each xhostname,prefixy pair it handles, where the prefix is the prefix of the user’s IP address forwarded to the authoritative nameserver. This has the potential to increase the cache size by several orders of magnitude, which may thereby enable some cache-overflow attacks.

7.9 Address Resolution Protocol: ARP If a host or router A finds that the destination IP address D = DIP matches the network address of one of its interfaces, it is to deliver the packet via the LAN (probably Ethernet). This means looking up the LAN address (MAC address) DLAN corresponding to DIP . How does it do this? One approach would be via a special server, but the spirit of early IPv4 development was to avoid such servers, for both cost and reliability issues. Instead, the Address Resolution Protocol (ARP) is used. This is our first protocol that takes advantage of the existence of LAN-level broadcast; on LANs without physical broadcast (such as ATM), some other mechanism (usually involving a server) must be used. The basic idea of ARP is that the host A sends out a broadcast ARP query or “who-has DIP ?” request, which includes A’s own IPv4 and LAN addresses. All hosts on the LAN receive this message. The host for whom the message is intended, D, will recognize that it should reply, and will return an ARP reply or “is-at”

210

7 IP version 4

An Introduction to Computer Networks, Release 1.9.16

message containing DLAN . Because the original request contained ALAN , D’s response can be sent directly to A, that is, unicast.

A

B

C

D

A broadcasts “who-has D” D replies to A, unicast, and includes its LAN address

Additionally, all hosts maintain an ARP cache, consisting of xIPv4,LANy address pairs for other hosts on the network. After the exchange above, A has xDIP ,DLAN y in its table; anticipating that A will soon send it a packet to which it needs to respond, D also puts xAIP ,ALAN y into its cache. ARP-cache entries eventually expire. The timeout interval used to be on the order of 10 minutes, but Linux systems now use a much smaller timeout (~30 seconds observed in 2012). Somewhere along the line, and probably related to this shortened timeout interval, repeat ARP queries about a timed-out entry are first sent unicast, not broadcast, to the previous Ethernet address on record. This cuts down on the total amount of broadcast traffic; LAN broadcasts are, of course, still needed for new hosts. The ARP cache on a Linux system can be examined with the command ip -s neigh; the corresponding windows command is arp -a. The above protocol is sufficient, but there is one further point. When A sends its broadcast “who-has D?” ARP query, all other hosts C check their own cache for an entry for A. If there is such an entry (that is, if AIP is found there), then the value for ALAN is updated with the value taken from the ARP message; if there is no pre-existing entry then no action is taken. This update process serves to avoid stale ARP-cache entries, which can arise is if a host has had its Ethernet interface replaced. (USB Ethernet interfaces, in particular, can be replaced very quickly.) ARP is quite an efficient mechanism for bridging the gap between IPv4 and LAN addresses. Nodes generally find out neighboring IPv4 addresses through higher-level protocols, and ARP then quickly fills in the missing LAN address. However, in some Software-Defined Networking (2.8 Software-Defined Networking) environments, the LAN switches and/or the LAN controller may have knowledge about IPv4/LAN address correspondences, potentially making ARP superfluous. The LAN (Ethernet) switching network might in principle even know exactly how to route via the LAN to a given IPv4 address, potentially even making LAN addresses unnecessary. At such a point, ARP may become an inconvenience. For an example of a situation in which it is necessary to work around ARP, see 18.9.5 loadbalance31.py.

7.9.1 ARP Finer Points Most hosts today implement self-ARP, or gratuitous ARP, on startup (or wakeup): when station A starts up it sends out an ARP query for itself : “who-has A?”. Two things are gained from this: first, all stations that had A in their cache are now updated with A’s most current ALAN address, in case there was a change, and second, if an answer is received, then presumably some other host on the network has the same IPv4 address as A. Self-ARP is thus the traditional IPv4 mechanism for duplicate address detection. Unfortunately, it does not always work as well as might be hoped; often only a single self-ARP query is sent, and if a reply is received then frequently the only response is to log an error message; the host may even continue using 7.9 Address Resolution Protocol: ARP

211

An Introduction to Computer Networks, Release 1.9.16

the duplicate address! If the duplicate address was received via DHCP, below, then the host is supposed to notify its DHCP server of the error and request a different IPv4 address. RFC 5227 has defined an improved mechanism known as Address Conflict Detection, or ACD. A host using ACD sends out three ARP queries for its new IPv4 address, spaced over a few seconds and leaving the ARP field for the sender’s IPv4 address filled with zeroes. This last step means that any other host with that IPv4 address in its cache will ignore the packet, rather than update its cache. If the original host receives no replies, it then sends out two more ARP queries for its new address, this time with the ARP field for the sender’s IPv4 address filled in with the new address; this is the stage at which other hosts on the network will make any necessary cache updates. Finally, ACD requires that hosts that do detect a duplicate address must discontinue using it. It is also possible for other stations to answer an ARP query on behalf of the actual destination D; this is called proxy ARP. An early common scenario for this was when host C on a LAN had a modem connected to a serial port. In theory a host D dialing in to this modem should be on a different subnet, but that requires allocation of a new subnet. Instead, many sites chose a simpler arrangement. A host that dialed in to C’s serial port might be assigned IP address DIP , from the same subnet as C. C would be configured to route packets to D; that is, packets arriving from the serial line would be forwarded to the LAN interface, and packets sent to CLAN addressed to DIP would be forwarded to D. But we also have to handle ARP, and as D is not actually on the LAN it will not receive broadcast ARP queries. Instead, C would be configured to answer on behalf of D, replying with xDIP ,CLAN y. This generally worked quite well. Proxy ARP is also used in Mobile IP, for the so-called “home agent” to intercept traffic addressed to the “home address” of a mobile device and then forward it (eg via tunneling) to that device. See 7.13 Mobile IP. One delicate aspect of the ARP protocol is that stations are required to respond to a broadcast query. In the absence of proxies this theoretically should not create problems: there should be only one respondent. However, there were anecdotes from the Elder Days of networking when a broadcast ARP query would trigger an avalanche of responses. The protocol-design moral here is that determining who is to respond to a broadcast message should be done with great care. (RFC 1122 section 3.2.2 addresses this same point in the context of responding to broadcast ICMP messages.) ARP-query implementations also need to include a timeout and some queues, so that queries can be resent if lost and so that a burst of packets does not lead to a burst of queries. A naive ARP algorithm without these might be: To send a packet to destination DIP , see if DIP is in the ARP cache. If it is, address the packet to DLAN ; if not, send an ARP query for D To see the problem with this approach, imagine that a 32 kB packet arrives at the IP layer, to be sent over Ethernet. It will be fragmented into 22 fragments (assuming an Ethernet MTU of 1500 bytes), all sent at once. The naive algorithm above will likely send an ARP query for each of these. What we need instead is something like the following: To send a packet to destination DIP : If DIP is in the ARP cache, send to DLAN and return If not, see if an ARP query for DIP is pending. If it is, put the current packet in a queue for D. If there is no pending ARP query for DIP , start one, again putting the current packet in the (new) queue for D 212

7 IP version 4

An Introduction to Computer Networks, Release 1.9.16

We also need: If an ARP query for some CIP times out, resend it (up to a point) If an ARP query for CIP is answered, send off any packets in C’s queue

7.9.2 ARP Security Suppose A wants to log in to secure server S, using a password. How can B (for Bad) impersonate S? Here is an ARP-based strategy, sometimes known as ARP Spoofing. First, B makes sure the real S is down, either by waiting until scheduled downtime or by launching a denial-of-service attack against S. When A tries to connect, it will begin with an ARP “who-has S?”. All B has to do is answer, “S is-at B”. There is a trivial way to do this: B simply needs to set its own IP address to that of S. A will connect, and may be convinced to give its password to B. B now simply responds with something plausible like “backup in progress; try later”, and meanwhile use A’s credentials against the real S. This works even if the communications channel A uses is encrypted! If A is using the SSH protocol (22.10.1 SSH), then A will get a message that the other side’s key has changed (B will present its own SSH key, not S’s). Unfortunately, many users (and even some IT departments) do not recognize this as a serious problem. Some organizations – especially schools and universities – use personal workstations with “frozen” configuration, so that the filesystem is reset to its original state on every reboot. Such systems may be resistant to viruses, but in these environments the user at A will always get a message to the effect that S’s credentials are not known.

7.9.3 ARP Failover Suppose you have two front-line servers, A and B (B for Backup), and you want B to be able to step in if A freezes. There are a number of ways of achieving this, but one of the simplest is known as ARP Failover. First, we set AIP = BIP , but for the time being B does not use the network so this duplication is not a problem. Then, once B gets the message that A is down, it sends out an ARP query for AIP , including BLAN as the source LAN address. The gateway router, which previously would have had xAIP ,ALAN y in its ARP cache, updates this to xAIP ,BLAN y, and packets that had formerly been sent to A will now go to B. As long as B is trafficking in stateless operations (eg html), B can pick up right where A left off.

7.9.4 Detecting Sniffers Finally, there is an interesting use of ARP to detect Ethernet password sniffers (generally not quite the issue it once was, due to encryption and switching). To find out if a particular host A is in promiscuous mode, send an ARP “who-has A?” query. Address it not to the broadcast Ethernet address, though, but to some nonexistent Ethernet address. If promiscuous mode is off, A’s network interface will ignore the packet. But if promiscuous mode is on, A’s network interface will pass the ARP request to A itself, which is likely then to answer it. Alas, Linux kernels reject at the ARP-software level ARP queries to physical Ethernet addresses other than their own. However, they do respond to faked Ethernet multicast addresses, such as ff:ff:ff:00:00:00 or ff:ff:ff:ff:ff:fe. 7.9 Address Resolution Protocol: ARP

213

An Introduction to Computer Networks, Release 1.9.16

7.9.5 ARP and multihomed hosts If host A has two interfaces iface1 and iface2 on the same LAN, with respective IP addresses A1 and A2 , then it is common for the two to be used interchangeably. Traffic addressed to A1 may be received via iface2 and vice-versa, and traffic from A1 may be sent via iface2. In 7.2.1 Multihomed hosts this is described as the weak end-system model; the idea is that we should think of the IP addresses A1 and A2 as bound to A rather than to their respective interfaces. In support of this model, ARP can usually be configured (in fact this is often the default) so that ARP requests for either IP address and received by either interface may be answered with either physical address. Usually all requests are answered with the physical address of the preferred (ie faster) interface. As an example, suppose A has an Ethernet interface eth0 with IP address 10.0.0.2 and a faster Wi-Fi interface wlan0 with IP address 10.0.0.3 (although Wi-Fi interfaces are not always faster). In this setting, an ARP request “who-has 10.0.0.2” would be answered with wlan0’s physical address, and so all traffic to A, to either IP address, would arrive via wlan0. The eth0 interface would go essentially unused. Similarly, though not due to ARP, traffic sent by A with source address 10.0.0.2 might depart via wlan0. This situation is on Linux systems adjusted by changing arp_ignore and arp_announce in /proc/ sys/net/ipv4/conf/all.

7.10 Dynamic Host Configuration Protocol (DHCP) DHCP is the most common mechanism by which hosts are assigned their IPv4 addresses. DHCP started as a protocol known as Reverse ARP (RARP), which evolved into BOOTP and then into its present form. It is documented in RFC 2131. Recall that ARP is based on the idea of someone broadcasting an ARP query for a host, containing the host’s IPv4 address, and the host answering it with its LAN address. DHCP involves a host, at startup, broadcasting a query containing its own LAN address, and having a server reply telling the host what IPv4 address is assigned to it, hence the “Reverse ARP” name. The DHCP response message is also likely to carry, piggybacked onto it, several other essential startup options. Unlike the IPv4 address, these additional network parameters usually do not depend on the specific host that has sent the DHCP query; they are likely constant for the subnet or even the site. In all, a typical DHCP message includes the following: • IPv4 address • subnet mask • default router • DNS Server These four items are a standard minimal network configuration; in practical terms, hosts cannot function properly without them. Most DHCP implementations support the piggybacking of the latter three above, and a wide variety of other configuration values, onto the server responses. Default Routers and DHCP

214

7 IP version 4

An Introduction to Computer Networks, Release 1.9.16

If you lose your default router, you cannot communicate. Here is something that used to happen to me, courtesy of DHCP: 1. I am connected to the Internet via Ethernet, and my default router is via my Ethernet interface 2. I connect to my institution’s wireless network. 3. Their DHCP server sends me a new default router on the wireless network. However, this default router will only allow access to a tiny private network, because I have neglected to complete the “Wi-Fi network registration” process. 4. I therefore disconnect from the wireless network, and my wireless-interface default router goes away. However, my system does not automatically revert to my Ethernet default-router entry; DHCP does not work that way. As a result, I will have no router at all until the next scheduled DHCP lease renegotiation, and must fix things manually. The DHCP server has a range of IPv4 addresses to hand out, and maintains a ) try: dest = gethostbyname(rhost) except (GAIerror, herror) as mesg: # GAIerror: error in ãÑgethostbyname() errno,errstr=mesg.args print("\n ", errstr); return; print("got it: " + dest) addr=(dest, portnum) # a socket address s = socket(AF_INET, SOCK_DGRAM) s.settimeout(1.5) # we don't actually need to set ãÑtimeout here

11.1 User ) try: dest = gethostbyname(rhost) except gaierror as mesg: # host not found errno,errstr=mesg.args print("\n ", errstr); return; print("got it: " + dest) addr=(dest, portnum) s = socket() TCP_CONGESTION = 13 # defined in /usr/include/netinet/tcp.h cong = bytes(cong_algorithm, 'ascii') try: s.setsockopt(IPPROTO_TCP, TCP_CONGESTION, cong) except OSError as mesg: errno, errstr = mesg.args print ('congestion mechanism {} not available: {}'.format(cong_ ãÑalgorithm, errstr)) return res=s.connect_ex(addr) # make the actual connection if res!=0: print("connect to port ", portnum, " failed") exit() while True: try: buf = input("> ") except: break; buf = buf + "\n" s.send(bytes(buf, 'ascii')) talk()

15.1 Choosing a TCP on Linux

469

An Introduction to Computer Networks, Release 1.9.16

As of version 3.5, Python did not define the constant TCP_CONGESTION; the value 13 above was found in the C include file mentioned in the comment. Fortunately, Python simply passes the parameters of s. setsockopt() to the underlying C call, and everything works. Supposedly TCP_CONGESTION is predefined in Python 3.6.

15.2 High-Bandwidth Desiderata One goal of all TCP implementations that attempt to fix the high-bandwidth problem is to be unfair to TCP Reno: the whole point is to allow cwnd to increase more aggressively than is permitted by Reno. Beyond that, let us review what else a TCP version should do. First is the backwards-compatibility constraint: any new TCP should exhibit reasonable fairness with TCP Reno at lower bandwidthˆdelay products. In particular, it should not ever have a significantly lower cwnd than a competing TCP Reno would get. But also it should not take bandwidth unfairly from a TCP Reno connection: the above comment about unfairness to Reno notwithstanding, the new TCP, when competing with TCP Reno, should leave the Reno connection with about the same bandwidth it would have if it were competing with another Reno connection. This is possible because at higher bandwidthˆdelay products TCP Reno does not efficiently use the available bandwidth; the new TCP should to the extent possible restrict itself to consuming this previously unavailable bandwidth rather than eating significantly into the bandwidth of a competing TCP Reno connection. There is also the self-fairness issue: multiple connections using the new TCP should receive similar bandwidth allocations, at least with similar RTTs. For dissimilar RTTs, the bandwidth proportions should ideally be no worse than they would be under TCP Reno. Ideally, we also want relatively rapid convergence to fairness; fairness is something of a hollow promise if only connections transferring more than a gigabyte will benefit from it. For TCP Reno, two connections halve the difference in their respective cwnds at each shared loss event; as we saw in 14.7.1 AIMD and Convergence to Fairness, slower convergence is possible. It is harder to hope for fairness between competing new implementations. However, at the very least, if new implementations tcp1 and tcp2 are competing, then neither should get less than TCP Reno would get. Some new TCPs make use of careful RTT measurements, and, as we shall see below, such measurements are subject to a considerable degree of noise. Any new TCP implementation should be reasonably robust in the face of inaccuracies in RTT measurement; a modest or transient measurement error should not make the protocol behave badly, in either the direction of low cwnd or of high. Finally, a new TCP should ideally try to avoid clusters of multiple losses at each loss event. Such multiple losses, for example, are a problem for TCP NewReno without SACK: as we have seen, it takes one RTT to retransmit each lost packet. Even with SACK, multiple losses complicate recovery. Yet if a new TCP increments cwnd by an amount N>1 after each RTT, then there is potential for the network ceiling to be exceeded by N within one RTT, making a cluster of N losses reasonably likely to occur. These losses are likely distributed among all connections, not just the new-TCP one. All TCPs addressing the high-bandwidth issue will need a cwnd-increment N that is fairly large, at least some of the time, apparently conflicting with this no-multiple-losses ideal. One trick is to reduce N when packet loss appears to be imminent. TCP Illinois and TCP Cubic do have mechanisms in place to reduce multiple losses.

470

15 Newer TCP Implementations

An Introduction to Computer Networks, Release 1.9.16

15.3 RTTs The exact performance of some of the faster TCPs we consider – for that matter, the exact performance of TCP Reno – is influenced by the RTT. This may affect individual TCP performance and also competition between different TCPs. For reference, here are a few typical RTTs from Chicago to various other places: • US West Coast: 50-100 ms • Europe: 100-150 ms • Southeast Asia: 100-200 ms

15.4 A Roadmap We start with Highspeed TCP, an early and relatively simple attempt to address the high-bandwidth-TCP problem. After that is the group TCP Vegas, FAST TCP, TCP Westwood, TCP Illinois and Compound TCP. These all involve so-called delay-based congestion control, in which the sender carefully monitors the RTT for the minute increases that signal queuing. TCP Vegas, which dates from 1995, is the earliest TCP here and in fact predates widespread recognition of the high-bandwidth-TCP problem. Its goal – then and now – was to prove that one could build a TCP that, in the absence of competition, could transfer arbitrarily long streams of ): size -= 1 elif (event=="+"): size += 1 else: nstrace.skipline() print("avg queue=", sum/time) queuesize(sys.argv[1])

The answer we get for the average queue size is about 23.76, which is in good agreement with our theoretical value of 22.5. 16.2.6.4 Packets that are delivered twice Every dropped TCP packet is ultimately transmitted twice, but classical TCP theory suggests that relatively few packets are actually delivered twice. This is pretty much true once the TCP sawtooth phase is reached, but can fail rather badly during slow start. The following Python script will count packets delivered two or more times. It uses a dictionary, COUNTS, which is indexed by sequence numbers. #!/usr/bin/python3 import nstrace import sys def dup_counter(filename): SEND_NODE = 1 DEST_NODE = 2 FLOW = 0 count = 0 COUNTS = {} nstrace.nsopen(filename)

516

16 Network Simulations: ns-2

An Introduction to Computer Networks, Release 1.9.16

while not nstrace.isEOF(): if nstrace.isEvent(): (event, time, sendnode, dest, dummy, size, dummy, flow, dummy, ãÑdummy, seqno, dummy) = nstrace.getEvent() if (event == "r" and dest == DEST_NODE and size >= 1000 and flow ãÑ== FLOW): if (seqno in COUNTS): COUNTS[seqno] += 1 else: COUNTS[seqno] = 1 else: nstrace.skipline() for seqno in sorted(COUNTS.keys()): if (COUNTS[seqno] > 1): print(seqno, COUNTS[seqno]) dup_counter(sys.argv[1])

When run on the basic1.tr file above, it finds 13 packets delivered twice, with TCP sequence numbers 43, 45, 47, 49, 51, 53, 55, 57, 58, 59, 60, 61 and 62. These are sent the second time between T=1.437824 and T=1.952752; the first transmissions are at times between T=0.83536 and T=1.046592. If we look at our cwnd-v-time graph above, we see that these first transmissions occurred during the gap between the end of the unbounded slow-start phase and the beginning of threshold-slow-start leading up to the TCP sawtooth. Slow start, in other words, is messy. 16.2.6.5 Loss rate versus cwnd: part 1 If we run the basic1.tcl simulation above until time 1000, there are 94915 packets acknowledged and 512 loss events. This yields a loss rate of p = 512/94915 = 0.00539, and so by the formula of 14.5 TCP Reno ? loss rate versus cwnd we should expect the average cwnd to be about 1.225/ p » 16.7. The true average cwnd is the number of packets sent divided by the elapsed time in RTTs, but as RTTs are not constant here (they get significantly longer as the queue fills), we turn to an approximation. From 16.2.1 Graph of cwnd v time we saw that the peak cwnd was 20.935; the mean cwnd should thus be about 3/4 of this, or 15.7. While not perfect, agreement here is quite reasonable. See also 16.4.3 Loss rate versus cwnd: part 2.

16.3 Two TCP Senders Competing Now let us create a simulation in which two TCP Reno senders compete for the bottleneck link, and see how fair an allocation each gets. According to the analysis in 14.3 TCP Fairness with Synchronized Losses, this is really a test of the synchronized-loss hypothesis, and so we will also examine the ns-2 trace files for losses and loss responses. We will start with “classic” TCP Reno, but eventually also consider SACK TCP. Note that, in terms of packet losses in the immediate vicinity of any one queue-filling event, we can expect TCP Reno and SACK TCP to behave identically; they differ only in how they respond to losses. The initial topology will be as follows (though we will very soon raise the bandwidths tenfold, though not the propagation delays):

16.3 Two TCP Senders Competing

517

An Introduction to Computer Networks, Release 1.9.16

A

8 Mbps 10 ms delay

R

B

800 Kbps = 100 pkt/s 100 ms delay

D

8 Mbps varying delay

Broadly speaking, the simulations here will demonstrate that the longer-delay B–D connection receives less bandwidth than the A–D connection, but not quite so much less as was predicted in 14.3 TCP Fairness with Synchronized Losses. The synchronized-loss hypothesis increasingly fails as the B–R delay increases, in that the B–D connection begins to escape some of the packet-loss events experienced by the A–D connection. We admit at the outset that we will not, however, obtain a quantitative answer to the question of bandwidth allocation. In fact, as we shall see, we run into some difficulties even formulating the proper question. In the course of developing the simulation, we encounter several potential problems: 1. The two senders can become synchronized in an unfortunate manner 2. When we resolve the previous issue by introducing randomness, the bandwidth division is sensitive to the method selected 3. As R’s queue fills, the RTT may increase significantly, thus undermining RTT-based measurements (16.3.9 The RTT Problem) 4. Transient queue spikes may introduce unexpected losses 5. Coarse timeouts may introduce additional unexpected losses The experiments and analyses below divide into two broad categories. In the first category, we make use only of the final goodput measurements for the two connections. We consider the first two points of the list above in 16.3.4 Phase Effects, and the third in 16.3.9 The RTT Problem and 16.3.10 Raising the Bandwidth. The first category concludes with some simple loss modeling in 16.3.10.1 Possible models. In the second category, beginning at 16.4 TCP Loss Events and Synchronized Losses, we make use of the ns-2 tracefiles to extract information about packet losses and the extent to which they are synchronized. Examples related to points four and five of the list above are presented in 16.4.1 Some TCP Reno cwnd graphs. The second category concludes with 16.4.2 SACK TCP and Avoiding Loss Anomalies, in which we demonstrate that SACK TCP is, in terms of loss and recovery, much better behaved than TCP Reno.

16.3.1 The Tcl Script Below is a simplified version of the ns-2 script for our simulation; the full version is at basic2.tcl. The most important variable is the additional one-way delay on the B–R link, here called delayB. Other defined variables are queuesize (for R’s queue_limit), bottleneckBW (for the R–D bandwidth), endtime (the length of the simulation), and overhead (for introducing some small degree of randomization, below). As with basic1.tcl, we set the packet size to 1000 bytes total (960 bytes TCP portion), and increase the advertised window size to 65000 (so it is never the limiting factor).

518

16 Network Simulations: ns-2

An Introduction to Computer Networks, Release 1.9.16

We have made the delayB value be a command-line parameter to the Tcl file, so we can easily experiment with changing it (in the full version linked to above, overhead, bottleneckBW, endtime and queuesize are also parameters). The one-way propagation delay for the A–D path is 10 ms + 100 ms = 110 ms, making the RTT 220 ms plus the bandwidth delays. At the bandwidths above, the bandwidth delay for , delayRB=" SetPosition(pos); cvmm->SetVelocity(vel); std::cout AddApplication(UdpSendApp);

We now set up tracing. The first, commented-out line enables pcap-format tracing, which we do not need here. The YansWifiPhyHelper object supports tracing only of “receive” (r) and “transmit” (t) records; the PointtoPointHelper of 17.2 A Single TCP Sender also traced enqueue and drop records. //wifiPhyHelper.EnablePcap (tracebase, devices); AsciiTraceHelper ascii; wifiPhyHelper.EnableAsciiAll (ascii.CreateFileStream (tracebase + ".tr")); // create animation file, to be run with 'netanim' AnimationInterface anim (tracebase + ".xml"); anim.SetMobilityPollInterval(Seconds(0.1));

If we view the animation with netanim, the moving node’s motion is clear. The mover node, however, sometimes appears to transmit back to both the fixed-row node below left and the fixed-row node below right. These transmissions represent the Wi-Fi link-layer ACKs; they appear to be sent to two fixed-row nodes because what netanim is actually displaying with its blue links is transmission every other node in range. We can also “view” the motion in text format by uncommenting the first line below.

17.3 Wireless

567

An Introduction to Computer Networks, Release 1.9.16

//Simulator::Schedule(Seconds(position_interval), &printPosition); Simulator::Schedule(Seconds(endtime), &stopMover);

Finally it is time to run the simulator, and print some final output. Simulator::Stop(Seconds (endtime+60)); Simulator::Run (); Simulator::Destroy (); int pktsRecd std::cout 0);

The written request here is ignored by tlsserver; it is an HTTP GET request of the form GET / HTTP/ 1.1\r\nHost: hostname\r\n\r\n. If we point tlsclient at a real webserver, say tlsclient google.com 443

then we should again get an X509_V_OK verification result because we loaded the default certificateauthority library. We can also point the built-in openssl client at tlsserver; by default it connects to localhost at port 4433: openssl s_client

804

22 Security

An Introduction to Computer Networks, Release 1.9.16

Of course, verification fails. This is because s_client doesn’t know about our certificate authority. We can add it, however, on the command line: openssl s_client -CAfile CAcert.pem

Now the verification is successful.

22.11 IPsec The SSH software package was built from the ground up to implement the SSH protocol. All modern web browsers incorporate TLS libraries to enable secure web connections. What can you do if you want to add encryption (or authentication) to a network application that doesn’t have it built in? Or, alternatively, how can you as a system administrator ensure that everyone’s traffic is protected, regardless of what software they are using? IPsec, for “IP security”, is one answer. It is a general-purpose security protocol which typically behaves as if it were a network sublayer below the IP layer (or, in transport mode, below the Transport layer). In this it is akin to Wi-Fi (3.7.5 Wi-Fi Security), which implements encryption within the LAN layer; in both Wi-Fi and IPsec the encryption is transparent to the communicating applications. In terms of actual implementation it is most often incorporated within the IP layer, but can be implemented as an external network appliance. IPsec can be used to protect anything from individual TCP (or UDP) connections to all traffic between a pair of routers. It is often used to implement VPN-like access from “outside” hosts to private subnets behind NAT routers. It is easily adapted to support any encryption or authentication mechanism. IPsec supports two packet formats: the authentication header, AH, for authentication only, and the encapsulating security payload, ESP, below, for either authentication or encryption or both. The ESP format is much more common and is the only one we will consider here. The AH format dates from the days when most export of encryption software from the United States was banned (see the sidebar ‘Crypto Law’ at 22.7.2 Block Ciphers), and, in any event, the ESP format can be used for authentication only. The ESP packet format is as follows:

22.11 IPsec

805

An Introduction to Computer Networks, Release 1.9.16

32 bits

Security Parameters Index (SPI) Sequence number

Payload (variable length)

Padding Pad Length

Next Header

Integrity Check Value (variable length)

ESP packet layout

The SPI identifies the security association, below. The sequence number is there to prevent replay attacks. Senders must increment it on every transmission, but receivers care only if the received numbers are not strictly increasing; gaps due to lost packets do not matter. The cryptographic algorithm applied to the payload and the integrity-check algorithm are negotiated at connection set-up. The Padding field is used first to bring the Payload length up to a multiple of the applicable encryption blocksize, and then to round up the total to a multiple of four bytes. The Next Header field describes the data that is inside the Payload, eg TCP or UDP for Transport mode or IP for Tunnel mode. It corresponds to the Protocol field of 7.1 The IPv4 Header or the Next Header field of 8.1 The IPv6 Header. IPsec has two primary modes: transport and tunnel. In transport mode, the IPsec endpoints are also typically the traffic endpoints, and only the transport-layer header (eg TCP header) and data are encrypted or protected. In the more-common tunnel mode one of the IPsec endpoints is often a router (or “security gateway”); encryption or protection includes the original IP headers, so that an eavesdropper cannot necessarily identify the actual traffic endpoints. IPsec is documented in a wide range of RFCs. A good overview of the architectural principles is found in RFC 4301. The ESP packet format is described in RFC 4303. A word of warning: while IPsec does support modern encryption, it also continues to support outdated algorithms as well; users must take care to ensure that the encryption negotiated is sufficient. IPsec has also attracted, in recent years, rather less attention from the security community than SSH or TLS, and “many eyes make all bugs shallow”. Or at least some bugs.

22.11.1 Security Associations In order for a given connection or node-to-node path to receive IPsec protection, it is first necessary to set up a pair of security associations. A security association consists of all necessary encryption/authentication attributes – algorithms, keys, rekeying rules, etc – together with a set of selectors to identify the covered 806

22 Security

An Introduction to Computer Networks, Release 1.9.16

traffic. A given security association covers traffic in one direction only; bidirectional traffic requires a separate security association for each direction. For outbound traffic – that is, traffic going from unprotected (internal) to IPsec-protected status – the selector consists of the destination IP address (or set of addresses) and possibly also the source IP address (or set of source addresses) and port or protocol values. Inbound ESP packets carry a 32-bit Security Parameters Index, or SPI, that for unicast traffic identifies the security association. However, that security association must still be checked against the packet for an actual match. The destination and source IP addresses need not be the same as the IP addresses of the IPsec endpoints. As an example, consider the following tunnel-mode arrangement, in which traveling host A wants to connect to private subnet 10.1.2.0/24 through security gateway B. IPv4 addresses are shown, but the same arrangement can be created with IPv6.

A

200.4.5.6

host

Internet

100.7.8.9

B

10.1.2.0/24

security gateway

The A-to-B IPsec security association’s selector will include the entire subnet 10.1.2.0/24 in its set of destination addresses. A packet from A to 10.1.2.3 arriving at A’s IPsec interface will match this selector, and will be encapsulated and sent (via normal Internet routing) to B at 100.7.8.9. B will de-encapsulate the packet, and then forward it on to 10.1.2.3 using its normal IP forwarding table. B might actually be the NAT router at its site, with external address 10.7.8.9 and internal subnet 10.1.2.0/24, or B might simply be a publicly visible host at its site that happens to have a route to the private 10.1.2.0/24 subnet. The action of forwarding the encapsulated packet from A to B closely resembles IP forwarding, but isn’t quite. It is unlikely A will have a true forwarding-table entry for 10.1.2.0/24 at all; it will very likely have only a single default route to its local ISP connection. Delivery of the packet cannot be understood simply by examining A’s IP forwarding table. A might even have a forwarding-table entry for 10.1.2.0/24 to somewhere else, but the IPsec “pseudo-route” to B’s 10.1.2.0/24 is still the one taken. This can easily lead to confusion; for complex arrangements with multiple overlapping security associations, this can lead to nontrivial difficulties in figuring out just how a packet is forwarded. A second routing issue exists at B’s end. Host 10.1.2.3 will see the packet from A arrive with address 200.4.5.6. Its reply back to A will be delivered to A using the tunnel only if the B-site routing infrastructure routes the packet back to B. If B is the NAT router, this will happen as a matter of course, but otherwise some deliberate action may need to be taken to avoid having 10.1.2.3-to-A traffic take an unsecured route. Additionally, the B-to-A security association needs to list 10.1.2.0/24 in its list of source addresses. The IPsec “pseudo-route” now resembles the policy-based routing of 9.6 Routing on Other Attributes, with routing based on both destination and source addresses. A packet for A arriving at B with source address 10.2.4.3 should not take the IPsec tunnel. (To add confusion, Linux IPsec pseudo-routes do not actually show up in the Linux policy-based routing tables.) Security associations are created through a software management interface, eg via the Linux ipsec command and the associated configuration file ipsec.conf. It is possible for an application to request creation of the necessary security associations, but it is more common for these to be set up before the IPsec-protected application starts up. A request for the creation of a security association typically triggers the invocation of the Internet Key Exchange, IKE, protocol; the current version 2 is often abbreviated IKEv2. IKEv2 is described in RFC 22.11 IPsec

807

An Introduction to Computer Networks, Release 1.9.16

7296. IKEv2 typically uses public keys to negotiate a session key (22.7.1 Session Keys); IKEv2 may then renegotiate the session key at intervals. In the simplest (and not very secure) case, both sides have been manually configured with a session key, and IKEv2 has little to do beyond verifying that the two sides have the same key. NAT traversal of IPsec packets is particularly tricky. For AH packets it is impossible, because the cryptographic authentication code in the packet covers the original IP addresses, as well as the packet transport data. That is not an issue for ESP packets, but even there the incoming packet must match the receivers’s security-association selector, which it will not if that was negotiated using the sender’s original IP address. An additional problem is that many NAT routers fail to forward (or fail to forward properly) packets outside of protocols ICMP, UDP and TCP. As a result, IPsec has its very own NAT-traversal mechanism, outlined in RFC 3715, RFC 3947 and RFC 3948. IPsec packets are encapsulated in UDP packets, with their original headers. After de-encapsulation at the IPsec receiving end, it is these original headers that are used in the security-association check. Additionally, a keepalive mechanism is defined in which the IPsec nodes send regular small packets to make sure the NAT mapping for the connection does not time out.

22.12 RSA Key Examples In this section we create a short RSA key, using the openssl package, available for Windows, Macs and Linux. We then break it, via factoring. The first step is to create an RSA key with length 96 bits; this length was chosen for easy factorability. openssl genrsa -out key96.pem 96

The resultant file is as follows: -----BEGIN RSA PRIVATE KEY----MFICAQACDQCo1hzP6/gTzbNAEHcCAwEAAQINAJzcEHi8aYSO0iizgQIHANkzC28P jwIHAMb/VQH8mQIHALc+9ZqRyQIHAKkfQ43msQIGJxhmMMOs -----END RSA PRIVATE KEY-----

This is in the so-called PEM format, which means that the two lines in the middle are the base64 encoding of the ASN.1 encoding (21.12 SNMP and ASN.1 Encoding) of the actual data. Despite the PRIVATE KEY label, the file in fact contains both private and public keys. SSH private keys, typically generated with the ssh-keygen command, are also in PEM format. We can extract the PEM-file data with the next command: openssl rsa -in key96.pem -text

The output is the following: Private-Key: (96 bit) modulus: 00:a8:d6:1c:cf:eb:f8:13:cd:b3:40:10:77 publicExponent: 65537 (0x10001) privateExponent:

808

22 Security

An Introduction to Computer Networks, Release 1.9.16

00:9c:dc:10:78:bc:69:84:8e:d2:28:b3:81 prime1: 00:d9:33:0b:6f:0f:8f prime2: 00:c6:ff:55:01:fc:99 exponent1: 00:b7:3e:f5:9a:91:c9 exponent2: 00:a9:1f:43:8d:e6:b1 coefficient: 27:18:66:30:c3:ac

The default OpenSSL encryption exponent, denoted e in 22.9.1 exponent used to be 3, but see exercise 10.0)

RSA, is 65537 = 216 +1. (The default

We next convert all these hex numbers to decimal; the corresponding notation of 22.9.1 RSA is in parentheses.

modulus (n) privateExponent (d) prime1 (p) prime2 (q) exponent1 exponent2 coefficient

52252327837124407964427358327 48545702997494592199601992577 238813258387343 218799945153689 201481036403145 185951742453425 42985747170220

We now verify some arithmetic, using any tool that supports large integers (eg python3, used here, or the unix bc command). First we check n = pq: >>> 238813258387343 * 218799945153689 52252327837124407964427358327

Next we check that ed = 1 mod (p-1)(q-1): >>> e=65537 >>> d=48545702997494592199601992577 >>> p=238813258387343 >>> q=218799945153689 >>> (p-1)*(q-1) 52252327837123950351223817296 >>> e*d % 52252327837123950351223817296 1

To encrypt a message m, we must use efficient mod-n calculations; here is an implementation of the repeatedsquaring algorithm (mentioned above in 22.8.1 Fast Arithmetic) in python3. (This function is built into python as pow(x,e,n).) def power(x,e,n): pow = 1

# computes x^e mod n

22.12 RSA Key Examples

809

An Introduction to Computer Networks, Release 1.9.16

while e>0: if e%2 == 1: pow = pow*x % n x = x* x % n e = e//2 # // denotes integer division return pow

Let m be the string “Rivest”. In hex this is 0x526976657374; in decimal, 90612911403892. >>> m=0x526976657374 >>> c=power(m,e,n) >>> c 38571433489059199500953769621 >>> power(c,d,n) 90612911403892

What about the last three numbers in the PEM file, exponent1, exponent2 and coefficient? These are pre-computed values to speed up decryption. Their values are • exponent1 = d mod (p-1) • exponent2 = d mod (q-1) • coefficient is the solution of coefficient ˆ q = 1 mod p

22.12.1 Breaking the key Finally, let us break this 96-bit key and decrypt the message with ciphertext c above. The hard part is factoring n; we use the Gnu/Linux factor command: > factor 52252327837124407964427358327 52252327837124407964427358327: 218799945153689 238813258387343

The factors are indeed the values of p and q, above. Factoring took 2.584 seconds on the author’s laptop. Of course, 96-bit RSA keys were never secure; recall that the current recommendation is to use 2048-bit keys. The Gnu/Linux factor command uses Pollard’s rho algorithm, and, while serviceable, is not especially well suited to factoring the product of two large primes. The author was able to factor a 200-bit modulus in just over 5 seconds using the msieve program, one of several large-number-factoring programs available on the Internet. Msieve implements a version of the number-field-sieve algorithm mentioned in 22.9.1.2 Factoring RSA Keys. We are almost done; we now need to find the decryption key d, knowing e, p-1 and q-1. For this we need an implementation of the extended Euclidean algorithm; the following Python implementation is taken from WikiBooks: def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y)

810

22 Security

An Introduction to Computer Networks, Release 1.9.16

A call to egcd(a,b) returns a triple (g,x,y) where g is the greatest common divisor of a and b, and x and y are solutions to g = ax + by. From 22.9.1 RSA, we need d to be positive and to satisfy 1 = de + (p-1)(q-1)y. The x value (the second value) returned by egcd(e, (p-1)*(q-1)) satisfies the second part, but it may be negative in which case we need to add (p-1)(q-1) to get a positive value which is congruent mod (p-1)(q-1). This x value is -3706624839629358151621824719; after adding (p-1)(q-1) we get d=48545702997494592199601992577. This is the value of d we started with. If c is the ciphertext, we now calculate m = pow(c,d,n) as before, yielding m=90612911403892, or, in hex, 52:69:76:65:73:74, “Rivest”.

22.13 Exercises Exercises are given fractional (floating point) numbers, to allow for interpolation of new exercises. 1.0 Modify the netsploit.c program of 22.2.2.3 The exploit so that the NOPslide is about 1024 bytes long, and the NOPslide and shellcode are now above the overwritten return address in memory. 2.0 Disable ASLR on a Linux system by writing the appropriate value to /proc/sys/kernel/randomize_va_space. Now get the netsploit attack to work without having the attacked server print out a stack address. You are allowed beforehand to run a test copy of the server that prints its address. 3.0 Below are a set of four possible TCP-segment reassembly rules. These rules (and more) appear in [SP03]. Recall that, once values for all positions jďi are received, these values are acknowleged and released to the application; there must be some earlier “hole” for segments to be subject to reassembly at all. 1. Always accept the first value received for each position. 2. Always accept the last value received for each position, up until the value is released to the application. 3. [“BSD”] For each new segment, discard each position from that segment if that position was supplied by an earlier packet with a left edge less than or equal to that of the new packet. Values in any remaining positions replace any previously received values. 4. [“Linux”] Same as the previous rule, except that we only discard positions that were supplied by an earlier packet with a left edge strictly smaller than that of the new packet. For each of the following two sets of packet arrivals, give the reassembled packet. Values in the same column have the same position. Reassembled packets will all begin with “daa” and “ebb” respectively. (a). a a a a a b b b b b b b c c c c d

(b). a a a a a b b b b b c c c c c c

22.13 Exercises

811

An Introduction to Computer Networks, Release 1.9.16

d d d e

4.0 Suppose a network intrusion-detection system is 10 hops from the attacker, but the target is 11 hops, behind one more router R. Outline a strategy of tweaking the TTL field so that the NIDS receives TCP stream “helpful” and the target receives “harmful”. Segments should either be disjoint or cover exactly the same range of bytes; you may assume that the target accepts the first segment for any given range of bytes. 5.0 Suppose Alice encrypts blocks P1, P2 and P3 using CBC mode (22.7.3 Cipher Modes). The initialization vector is C0. The encrypt and decrypt operations are E(P) = C and D(C) = P. We have • C1 = E(C0 XOR P1) • C2 = E(C1 XOR P2) • C3 = E(C2 XOR P3) Suppose Mallory intercepts C2 in transit, and replaces it with C2’ = C2 XOR M; C1 and C3 are transmitted normally; that is, Bob receives [C1’,C2’,C3’] where C1’ = C1 and C3’ = C3. Bob now attempts to decrypt; C1’ decrypts normally to P1 while C2’ decrypts to gibberish. Show that C3’ decrypts to P3 XOR M. (This is sometimes used in attacks to flip a specific bit or byte, in cases where earlier gibberish does not matter.) 6.0 Suppose Alice uses a block-based stream cipher (22.7.5 Block-cipher-based stream ciphers); block i of the keystream is Ki and Ci = Ki XOR Pi. Alice sends C1, C2 and C3 as in the previous exercise, and Mallory again replaces C2 by C2 XOR M. What are the three plaintext blocks Bob deciphers? 7.0 Show that if p and q are primes with p = 2q + 1, then g is a primitive root mod p if g‰1, g2 ‰1, and gq ‰1. (This exercise requires familiarity with modular arithmetic and primitive roots.) 8.0 Suppose we have a short message m, eg a bank PIN number. Alice wants to send message M to Bob that, without revealing m immediately, can be used later to verify that Alice knew m at the time M was sent. During this later verification, Alice may reveal m itself. (a). Suppose Alice simply sends M = hash(m). Explain how Bob can quickly recover m. (b). How can Alice construct M using a secure-hash function, avoiding the problem of (a)? Hint: as part of the later verification, Alice can supply additional information to Bob. 9.0 In the example of 22.7.7 Wi-Fi WEP Encryption Failure, suppose the IV is x4,-1,5y and the first two bytes of the key are x10,20y. What is the first keystream byte S[ S[1] + S[S[1]] ]? 10.0 Suppose Alice uses encryption exponent e=3 to three friends, Bob, Charlie and Deborah, with respective encryption moduli nB , nC and nD , all of which are relatively prime. Alice sends message m to each, encrypted as • CB = m3 mod nB • CC = m3 mod nC • CD = m3 mod nD If Mallory intercepts all three encrypted messages, explain how he can efficiently decrypt m. Hint: the Chinese Remainder Theorem implies that Mallory can find C < nB nC nD such that

812

22 Security

An Introduction to Computer Networks, Release 1.9.16

• C = CB mod nB • C = CC mod nC • C = CD mod nD (One simple way to avoid this risk is for Alice to include a timestamp and the recipient’s name in each message, ensuring that she never sends exactly the same message twice.) 11.0 Repeat the key-creation of 22.12 RSA Key Examples using a 110-bit key. Extract the modulus from the key file, convert it to decimal, and attempt to factor it. Can you do the factoring in under a minute? 12.0 Below are a series of public RSA keys and encrypted messages; the encrypted message is c and the modulus is n=pq. In each case, find the original message, using the methods of 22.12.1 Breaking the key; you will have to factor n and then find d. For some keys, the Gnu/Linux factor command will be sufficient; for the larger keys consider msieve or some other fast factorer. Each number below is in decimal. The encryption exponent e is always 65537; the encryption is c = power(message,e,n). Each message is an ASCII string; that is, after the numeric message is converted to a string, the byte values are each in the range 32-127. The following Python function may be useful in converting numeric messages to strings: def int2ascii(n): if n==0: return "" return int2ascii(n // 256) + chr(n % 256)

(a) [64 bits] c=13467824835325843134 n=15733922878520524621

(b) [96 bits] c=8007751471156136764029275727 n=57644199986835279860947893727

(c) [104 bits] c=6642328489179330732282037747645 n=17058317327334907783258193953123

(d) [127 bits] c=95651949760509273124353927897611145475 n=122096824047754908887766043915630626757 Limit for Gnu/Linux factor without the GMP library

(e) [185 bits] c=14898070767615435522751082309577192810119252877170446296 n=36881105206579952723396854897336450502002018818436622611

(f) [210 bits] c=1030865591241775131254813948981782525587720826169501849049177362 n=1089313781487492651628882855744766776820791642308868127824231021 22.13 Exercises

813

An Introduction to Computer Networks, Release 1.9.16

(g) [280 bits] c=961792929180423930042975913300802531765775361218349440433358416557620430721970697783 n=1265365011260907658483984328995361695181000868013851878620685943648084220336740539017

(h) [304 bits] c=17860252858059565448950681133486824440185752167054796213786228492658586864179401029486173539

n=26294146550372428669569992924076340150116542153388301312743129088600749884420889043685502979

814

22 Security

23 BIBLIOGRAPHY

Note that RFCs are not included here.

815

An Introduction to Computer Networks, Release 1.9.16

816

23 Bibliography

24 SELECTED SOLUTIONS

In this chapter we present solutions (in some cases partial solutions) to exercises marked with a ♢.

24.1 Solutions for An Overview of Networks 1.18 Exercises Exercise 2.7 A B,C,D E

B A,C D E

C A,B,E D

direct D (or C)

direct A C

direct E (or A)

D A,E B C

direct A E (or A)

E C,D A B

direct C (or D) C

Exercise 7.0(d) (destination D):

According to S1’s forwarding table, the next_hop to D is S2. According to S2’s table, the next_hop to D is S5. According to S5’s table, the next_hop to D is S6.

817

An Introduction to Computer Networks, Release 1.9.16

According to S6’s table, the next_hop to D is S12.

The path from S1 to D is thus S1–S2–S5–S6–S12. Exercise 7.5(a) The shortest path from A to F is A–S1–1–S2–2–S5–1–S6–F, for a total cost of 1+2+1 = 4.

24.2 Solutions for Ethernet 2.10 Exercises Exercise 2.7

When A sends to D, all switches use fallback-to-flooding as no switch knows where D is. All switches S1-S4, though, learn where A is. When D sends to A, S2 knows where A is and so routes the packet directly to S1, which also knows where A is. S3 and S4 do not learn where D is. When A sends to B, all switches again use fallback-to-flooding, but no switch learns anything new. When B sends to D, S4 uses fallback-to-flooding as it does not know where D is. However, S2 does know where D is, and so S2 forwards the packet only to D. S2 and S4 learn where B is.

switch S1 S2 S3 S4

known destinations AD ABD A AB

Exercise 8.5

(a). S1, as root, keeps all three of its links to S3, S4 and S5. Of S2’s three links in the direction of the root (that is, to S3, S4 and S5), it keeps only its link to S3 as S3 has the lowest ID.

S1

S3

818

S2

S4

S5

24 Selected Solutions

An Introduction to Computer Networks, Release 1.9.16

The path from S2 to S5 is S2–S3–S1–S5. Exercise 12.0

1. h1Ñh2: this packet is reported to C, as destination h2 is not known by S. C installs on S the rule that h1 can be reached via port 1. The packet is then flooded.

2. h2Ñh1: this packet is not reported to C, as destination h1 is known by S. The packet is not flooded.

3. h3Ñh1: this packet is again not reported to C. S delivers the packet normally, without flooding.

4. h2Ñh3: this packet is reported to C, as destination h3 is not known by S. C installs on S the rule that h2 can be reached via port 2. The packet is then flooded.

Exercise 13.0 Table for S1 only:

h1Ñh2: h2Ñh1: h1Ñh3: h3Ñh1: h2Ñh3: h3Ñh2:

S1 reports to C and learns where h1 is S1 does not report, and forwards normally; destination h1 is known S1 reports to C as h3 is not known, but S1 already knows where h1 is S1 does not report, and forwards normally; destination h1 is known S1 reports to C and learns where h2 is S1 does not report, and forwards normally; destination h2 is known

S1’s table ends up with forwarding entries for h1 and h2, but not h3.

24.3 Solutions for Other LANs 3.11 Exercises Exercise 3(b) One simple strategy is for stations to compare themselves to one another according to the numeric value of their MAC addresses. The station with the smallest MAC address becomes S0 , the station with the nextsmallest address becomes S1 , etc. Exercise 4.5 The three sending nodes can be laid out at the vertices of an equilateral triangle, with the receiving node in the center. Alternatively, with impermeable walls the following arrangement works:

24.3 Solutions for Other LANs

819

An Introduction to Computer Networks, Release 1.9.16

sender1 receiver

sender2 sender1

The latter arrangement generalizes to almost any number of senders. For the former, senders can be laid out at the vertices of a square, or tetrahedron, or possibly a pentagon, but geometry enforces an eventual limit. Exercise 5(b) If T is the length of the contention interval, in µsec, then transmission and contention alternate with lengths 151–T–151–T–. . . . The fraction of bandwidth lost to contention is T/(T+151). Exercise 10.5 The connections are as follows, where the VCI number is shown between the endpoints of each link: A–1–S1–2–S2–3–S4–2–D B–1–S2–2–S4–1–S3–3–S1–2–A

24.4 Solutions for Links Exercise 3.5 The binary ASCII for the three letters is

N e t

0100 1110 0110 0101 0111 0100

If we look up the 4-bit “nybbles” in the right column above in the 4B/5B table at 4.1.4 4B/5B, we get data 0100 1110 0110 0101 0111 0100

symbol 01010 11100 01110 01011 01111 01010

Putting all these symbols together, the encoding is (with spaces added for readability)

01010 11100 01110 01011 01111 01010

820

24 Selected Solutions

An Introduction to Computer Networks, Release 1.9.16

24.5 Solutions for Packets 5.6 Exercises Exercise 3

(a). The bandwidth delay for a 600-byte packet is 300 µsec. The packet has a 300 µsec bandwidth delay and a 600 µsec propagation delay for each link, for a total of 2ˆ900 = 1800 µsec. We have the following timeline:

T=0 T=300 T=600 T=900 T=1200 T=1500 T=1800

A begins sending the packet A finishes sending the packet S begins receiving the packet S finishes receiving the packet and begins sending to B S finishes sending the packet B begins receiving the packet B finishes receiving the packet

(b). The bandwidth delay for each 300-byte packet is now 150 µsec, so the first packet arrives at S at T=750. The second packet arrives one bandwidth delay – 150 µsec – later, at T=900 µsec. The first packet takes another 750 µsec to travel from S to B, arriving at T=1500; the second packet arrives 150 µsec later at T=1650. Here is the timeline:

T=0 T=150 T=300 T=600 T=750 T=900 T=1350 T=1500 T=1650

A begins sending packet 1 A finishes sending packet 1, starts on packet 2 A finishes sending packet 2 S begins receiving packet 1 S finishes receiving packet 1 and begins sending it to B S begins receiving packet 2 S finishes receiving packet 2 and begins sending it to B B begins receiving packet 1 B has received all of packet 1 and starts receiving packet 2 B finishes receiving packet 2

Here’s the data for (b) in ladder-diagram format (not quite to scale):

24.5 Solutions for Packets

821

An Introduction to Computer Networks, Release 1.9.16

T=0 T=150 T=300

T=600 T=750 T=900 T=1150

T=1350 T=1500 T=1650

The long propagation delay means that A finishes all transmissions before S begins receiving anything, and S finishes all transmissions before B begins receiving anything. With a smaller propagation delay, these A/S/B events are likely to overlap. Exercise 15(a) The received data is 10100010 and the received code bits are 0111. We first calculate the four code bits for the received data: 1: parity over all bits 1: parity over second half: 10100010 0: parity over these bits: 10100010 0: parity over these bits: 10100010 So the incorrect received code bits are 0111. The first bit of the received code tells us that the error is in the data (rather than the code bits). The second – correct – bit of the received code tells us that the error is in the first half, that is, in the non-bold bits of 10100010. The third bit of the received code tells us that the error is in the bold bits of 10100010, so we’re down to the third or fourth bit. Finally, the fourth bit of the received code tells us the error is in the bold bits of 10100010, which means the fourth bit is it, and the corrected data is 10110010 (making the data the same as that in the example in 5.4.2.1 Hamming Codes).

24.6 Solutions for Sliding Windows 6.5 Exercises Exercise 2.5 The network is

822

24 Selected Solutions

An Introduction to Computer Networks, Release 1.9.16

infinitely fast

C

1 pkt/sec

S1

1 pkt/sec

S2

D

(a). The second part of formula 4 of 6.3.2 RTT Calculations is queue_usage = winsize – bandwidth ˆ RTTnoLoad . We know winsize = 6, bandwidth = 1 packet/sec and RTTnoLoad = 4, so this works out to 2 packets in the queue.

(b). At T=0, C sends packets 1-6 to S1. S1 begins sending packet 1 to S2; packets 2-6 are queued. At T=1, S1 begins sending packet 2 to S2; S2 begins sending packet 1 to D At T=2, S1 begins sending packet 3 to S2 and S2 begins sending packet 2 to D. Packet 1 has reached D, which begins sending ACK1 to S2. At T=3, S1 begins sending packet 4 to S2, S2 begins sending packet 3 to D, D begins sending ACK2 to S2, and S2 begins sending ACK1 to S1. At T=4, S1 begins sending packet 5 to S1, S2 begins sending packet 4 to D, D begins sending ACK3 to S2, and S2 begins sending ACK2 to S1. ACK1 has arrived at S1, and is instantly forwarded to C. The window slides forward by one, from [1-6] to [2-7], and C sends new packet 7, which instantly arrives at S1 and is placed in the queue there.

Here is the table. The column “S1ÑS2” is the data packet S1 is currently sending to S2; the column “S2ÑS1” is the ACK that S2 is currently sending to S1; similarly for “S2ÑD” and “DÑS2”. T 0 1 2 3 4 5 6 7 8

C sends 1,2,3,4,5,6

7 8 9 10 11

S1 queues 2,3,4,5,6 3,4,5,6 4,5,6 5,6 6,7 7,8 8,9 9,10 10,11

S1ÑS2 1 2 3 4 5 6 7 8 9

S2ÑD

ACK DÑS2

S2ÑS1

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7

1 2 3 4 5 6

Exercise 7.5

(a). The formula, from 6.2.1 Bandwidth ˆ Delay, is winsize = bandwidth ˆ RTTnoLoad = 1000 pkts/sec ˆ 0.1 sec = 100 packets. (b). This is the first line of formula 3 of 6.3.2 RTT Calculations. For convenience, we switch to units of ms. Queue_usage = throughput ˆ (RTTactual – RTTnoLoad ) = 1 pkt/ms ˆ (130ms – 100ms) = 30 packets. (c). We use formula 4 of 6.3.2 RTT Calculations. We have RTTactual = winsize / bandwidth = (100+50)/(1 pkt/ms) = 150 ms. 24.6 Solutions for Sliding Windows

823

An Introduction to Computer Networks, Release 1.9.16

Exercise 9.0 If Data[8] is in the receiver’s window, then Data[4] must have been received. For the sender to have sent Data[4] it must have previously received ACK[0]. Therefore, all transmissions of Data[0] must precede the first transmission of Data[4], and so must precede the first successful transmission of Data[4]. Because of non-reordering, no Data[0] can arrive after Data[4].

24.7 Solutions for IPv4 7.15 Exercises Exercise 4.0 Forwarding table for A: destination 200.0.5.0/24 200.0.6.0/24 default

next_hop direct direct B

Exercise 6.0(d) The subnet prefix is 10.0.168.0/21. The /21 means that the prefix consists of the first two bytes (16 bits) and the first 5 (=21-16) bits of the third byte. Expressing the third byte, 168, in binary, we get 10101|000. We now convert the third byte of each of the four addresses to binary, and see which match this to the first five bits. Bits after the “|” mark are ignored. 10.0.166.1: 10.0.170.3: 10.0.174.5: 10.0.177.7:

166 = 10100|110; not a match 170 = 10101|010; this is a match 174 = 10101|110; this is a match 177 = 10110|001; not a match

Exercise 6.5

(a). 240 is 11110000 in binary, and so adds 4 1-bits. Together with the 16 1-bits from the first two bytes of the mask, this is /20 (d). /20 is 16 1-bits (two bytes) plus 4 additional 1-bits. Four 1-bits starting a byte is 11110000, or 240; the full mask is 255.255.240.0

24.8 Solutions for Routing-Update Algorithms 9.9 Exercises Exercise 2.5 824

24 Selected Solutions

An Introduction to Computer Networks, Release 1.9.16

For destination A, R1’s report is likely the same as it sent earlier, when R’s route to A was first established. There is no change. For destination B, R’s total distance using R1 would be 2+1 = 3. This is tied with R’s route to B using next_hop R2, and so there is no change. For destination C, R1 is reporting an increase in cost. R’s next_hop to C is R1, and so R must increase its cost to C to 4+1 = 5. For destination D, R’s total cost using R1 is 3+1 = 4, cheaper than R’s previous cost of 5 using next_hop R3. R changes to the R1 route. The updated table is destination A B C D

cost 2 3 5 4

next hop R1 R2 R1 R1

no change; same next_hop no change; tie source increase lower-cost route found

24.9 Solutions for Large-Scale IP Routing 10.8 Exercises Exercise 0.5

(i) 200.63.1.1 matches only A, as 63 = 0011 1111 in binary and 64 = 0100 0000. The first two bits do not match, ruling out the /10 prefix. (ii) 200.80.1.1 matches A and B, but not C, as 80 = 0101 0000. Destination B is the longer match. (iii) 200.72.1.1 matches A, B and C, but not D, as 72 = 0100 1000. Destination C is the longest match. (iv) 200.64.1.1 matches A, B, C and D; D is the longest match.

Exercise 5(a) P’s table destination 52.0.0.0/8 53.0.0.0/8 51.10.0.0/16 51.23.0.0/16

next hop Q R A B

Q’s table

24.9 Solutions for Large-Scale IP Routing

825

An Introduction to Computer Networks, Release 1.9.16

destination 51.0.0.0/8 53.0.0.0/8 52.14.0.0/16 52.15.0.0/16

next hop P R C D

destination 51.0.0.0/8 52.0.0.0/8

next hop P Q

R’s table

Exercise 7(a) P will receive a route from Q with AS-path xQ,Sy, and a route from R with AS-path xR,Sy.

24.10 Solutions for UDP Exercise 2(a) Two seconds after Data[3] was sent and lost, both sender and receiver will time out. The sender will retransmit Data[3]; the receiver will retransmit ACK[2]. The latter will be ignored, as the sender is not retransmitting on duplicates. When the retransmitted Data[3] arrives at the receiver, the receiver will send ACK[3] and the transfer will continue.

24.11 Solutions for TCP Reno 12.24 Exercises Exercise 12.5(b) Let t be the transit capacity; then the total cwndmax is t(1+f ). At this point it is convenient to normalize the units of capacity measurement so t(1+f ) = 2. Then the link-unsaturated and queue-filling phases have lengths in the proportion t–1 to ft. The average height of the tooth during the link-unsaturated phase is (t+1)/2, and the average utilization percentage is thus (t+1)/2t. This gives a utilization of (t+1)/2t ˆ (t–1) + ft We next eliminate t. After normalization, we have t(1+f ) = 2, and so t = 2/(1+f ). Plugging this in above and simplifying gives utilization = (3 + 6f – f 2 )/4(1+f )

24.12 Solutions for Dynamics of TCP 14.13 Exercises 826

24 Selected Solutions

An Introduction to Computer Networks, Release 1.9.16

Exercise 2(a) Because the window size of 50 is larger than the bandwidthˆdelay product is 40 packets, packets are sent at the bottleneck rate of 5 packets/ms. As packets spend 1 ms on the C–R1 link, on average this link must be carrying 5 packets. The same applies to the R2–D link; for the R1–R2 link with a 2.0 ms propagation delay, the number of packets carried will be 2.0ˆ5 = 10. Alternatively, from the bandwidthˆdelay product of 40 packets we conclude 40 packets are in transit. Of these, half are acknowledgments. The other half are distributed in proportion to the link propagation delays, yielding 5, 10, and 5 packets. Exercise 2.5 At the point when A’s bandwidth is 2 packets/ms, B’s bandwidth is 4 packets/ms, and so B has 4ˆ20 = 80 packets in transit. As B’s winsize is 120, this leaves 120–80 = 40 packets in R’s queue. For A to have half as much bandwidth, it must have half the queue capacity, or 20 packets. With a bandwidth of 2 packets/ms and an RTTnoLoad of 40 ms, A will have 2ˆ40 = 80 packets in transit. A’s winsize is then 20+80 = 100. We can confirm this using the following formulas from 14.2.3 Example 3: competition and queue utilization:

𝛼Q = wA – 2𝛼(dA +d) 𝛽Q = wB – 2𝛽(dB +d)

However, these formulas were derived under the assumption that the bottleneck bandwidth was normalized to 1. To apply them here, we need to measure time in units of 1/6 ms; that is, all times need to be multiplied by 6. We have:

dA = 90 dB = 30 d = 30 wB = 120 𝛼=1/3, 𝛽=2/3

Substituting these into the second formula, we get the total queue utilization Q = 180 – 120 = 60, in agreement with our earlier answer. From the first formula we now solve for wA = 𝛼(Q + 2(dA +d)) = (1/3)ˆ(60 + 240) = 100, also in agreement with our earlier answer. Exercise 3(a) The bottleneck bandwidth is 5 packets/ms, and as the bottleneck link is saturated, this will be the transmission rate on all links. For 5 packets to be in transmission, we need a propagation delay of 5 packets / (5 packets/ms) = 1.0 ms. Exercise 3.5

24.12 Solutions for Dynamics of TCP

827

An Introduction to Computer Networks, Release 1.9.16

(a). If the A–B connection has a bandwidth of 3 packets/sec and a RTTnoLoad of 16 ms, then a window size of 3ˆ16 = 48 is necessary. Similarly, the window size for the C–D connection is 3ˆ10 = 30 packets. It remains to show that these window sizes actually result in an equal division of bandwidth. The A–B bandwidth cannot exceed 50% in the steady state, because of the limitation imposed by the R2–R3 link. If the C–D bandwidth exceeds 50%, then the bandwidth-delay product exceeds 30 = wC , and so the C–D connection can have no packets in the queue at R1, leaving the A–B connection with no queuing delays. This means A sends wA packets in 16 ms, for a bandwidth of 3 pkts/ms. Exercise 13.5(a) The cwnd will vary between 500 and 1000, with an average of 750 packets. Losses occur at intervals of 500 RTTs, during which 500*750 packets have been sent.

24.13 Solutions for Mininet Exercise 6.0(a) When h1 sends its broadcast ARP, the controller learns where h1 is relative to s1, s2 and s3. When h2 replies to h2, there is not yet a rule for h1 at s2, and so s2 sends the packet to the controller, which installs rules for destinations h1 and h2 in s2. The packet is then flooded. When it arrives at s1, the controller installs rules for h1 and h2 and s1. The packet also arrives at s3, by flooding, so the controller installs rules for h1 and h2 in s3. When h3 sends its broadcast packet, all of s1-s3 see the packet. Because the packet is broadcast, all three switches report the packet to the controller. When h1 replies to h3, no switches have a rule for destination h3, and the controller knows how to reach h1 and h3 from each switch, so a new rule for reaching h3 is installed at each switch.

828

24 Selected Solutions

INDICES AND TABLES

• genindex • search

829

An Introduction to Computer Networks, Release 1.9.16

830

Indices and tables

BIBLIOGRAPHY

[ABDGHSTVWZ15] David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, J. Alex Halderman, Nadia Heninger, Drew Springall, Emmanuel Thomé, Luke Valenta, Benjamin VanderSloot, Eric Wustrow, Santiago Zanella-Béguelin, Paul Zimmermann, “Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice”, preprint at weakdh.org, May 2015. [AEH75] Eralp Akkoyunlu, Kattamuri Ekanadham and R V Huber, “Some constraints and tradeoffs in the design of network communications”, SOSP ‘75: Proceedings of the fifth ACM symposium on Operating systems and principles, November 1975. [AO96] Aleph One (Elias Levy), “Smashing The Stack For Fun And Profit”, Phrack volume 7 number 49, 1996, available at http://insecure.org/stf/smashstack.html. [AGMPS10] Mohammad Alizadeh, Albert Greenberg, David Maltz, Jitendra Padhye, Parveen Patel, Balaji Prabhakar, Sudipta Sengupta and Murari Sridharan, “Data Center TCP (DCTCP)”, Proceedings of ACM SIGCOMM 2010, September 2010. [AP99] Mark Allman and Vern Paxson, “On Estimating End-to-End Network Path Properties”, Proceedings of ACM SIGCOMM 1999, August 1999. [ACPRT16] Joël Alwen, Binyi Chen, Krzysztof Pietrzak, Leonid Reyzin and Stefano Tessaro, “Scrypt is Maximally Memory-Hard”, Cryptology ePrint Archive, Report 2016/989, 2016, available at https:// eprint.iacr.org/2016/989. [AHLR07] Chris Anley, John Heasman, Felix “FX” Linder and Gerardo Richarte, “The Shellcoder’s Handbook”, second edition, Wiley, 2007. [AKM04] Guido Appenzeller, Isaac Keslassy and Nick McKeown, “Sizing Router Buffers”, ACM SIGCOMM Computer Communication Review, October 2004 [JA05] John Assalone, “Exploiting the GDI+ JPEG COM Marker Integer Underflow Vulnerability”, Global Information Assurance Certification technical note, January 2005, available at www.giac.org/paper/gcih/679/exploiting-gdi-plus-jpeg-marker-integer-underflowvulnerability/106878. [PB62] Paul Baran, “On Distributed Computing Networks”, Rand Corporation Technical Report P-2626, 1962. [BCL09] Steven Bauer, David Clark and William Lehr, “The Evolution of Internet Congestion”, Telecommunications Policy Research Conference (TPRC) 2009, August 2009, available at ssrn.com/abstract=1999830. 831

An Introduction to Computer Networks, Release 1.9.16

[MB06] Mihir Bellare, “New Proofs for NMAC and HMAC: Security without Collision-Resistance”, Advances in Cryptology - CRYPTO ‘06 Proceedings, Lecture Notes in Computer Science volume 4117, Springer-Verlag, 2006. [BCK96] Mihir Bellare, Ran Canetti and Hugo Krawczyk, “Keying Hash Functions for Message Authentication”, Advances in Cryptology - CRYPTO ‘96 Proceedings, Lecture Notes in Computer Science volume 1109, Springer-Verlag, 1996. [BN00] Mihir Bellare and Chanathip Namprempre, “Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm”, Advances in Cryptology — ASIACRYPT 2000 / Lecture Notes in Computer Science volume 1976, Springer-Verlag, 2000; updated version July 2007. [BZ97] Jon Bennett and Hui Zhang, “Hierarchical Packet Fair Queueing Algorithms”, IEEE/ACM Transactions on Networking, volume 5, October 1997. [DB08] Daniel Bernstein, “The Salsa20 family of stream ciphers”, Chapter, New Stream Cipher Designs, Matthew Robshaw and Olivier Billet, editors, Springer-Verlag, 2008. [JB05] John Bickett, “Bit-rate Selection in Wireless Networks”, MS Thesis, Massachusetts Institute of Technology, 2005. [BCTCU16] Timm Böttger, Felix Cuadrado, Gareth Tyson, Ignacio Castro and Steve Uhlig, “Open Connect Everywhere: A Glimpse at the Internet Ecosystem through the Lens of the Netflix CDN”, ARXIV, arXiv e-print (arXiv:1606.05519), June 2016. [BP95] Lawrence Brakmo and Larry Peterson, “TCP Vegas: End to End Congestion Avoidance on a Global Internet”, IEEE Journal on Selected Areas in Communications, volume 13 number 8, 1995. [BBGO08] Vladimir Brik, Suman Banerjee, Marco Gruteser and Sangho Oh, “Wireless Device Identification with Radiometric Signatures”, Proceedings of the 14th ACM International Conference on Mobile Computing and Networking (MobiCom ‘08), September 2008. [AB03] Andreis Brouwer, “Hackers Hut”, http://www.win.tue.nl/~aeb/linux/hh/hh.html, April 1, 2003 [CF04] Carlo Caini and Rosario Firrincieli, “TCP Hybla: a TCP enhancement for heterogeneous networks”, International Journal of Satellite Communications and Networking, volume 22, pp 547-566, 2004. [CGYJ16] Neal Cardwell, Yuchung Cheng, C. Stephen Gunn, Soheil Hassas Yeganeh and Van Jacobson, “BBR Congestion-Based Congestion Control”, ACM Queue, volume 14 number 5, September-October 2016. [CM03] Zehra Cataltepe and Prat Moghe, “Characterizing Nature and Location of Congestion on the Public Internet”, Proceedings of the Eighth IEEE International Symposium on Computers and Communication, 2003. [CDLMR00] Stefania Cavallar, Bruce Dodson, Arjen K Lenstra, Walter Lioen, Peter Montgomery, Brian Murphy, Herman te Riele, Karen Aardal, Jeff Gilchrist, Gerard Guillerm, Paul Leyland, Joel Marchand, François Morain, Alec Muffett, Craig Putnam, Chris Putnam and Paul Zimmermann, “Factorization of a 512-bit RSA Modulus”, Advances in Cryptology — EUROCRYPT 2000, Lecture Notes in Computer Science volume 1807, Springer-Verlag, 2000. [CK74] Vinton G Cerf and Robert E Kahn, “A Protocol for Packet Network Intercommunication”, IEEE Transactions on Communications, volume 22 number 5, May 1974.

832

Bibliography

An Introduction to Computer Networks, Release 1.9.16

[CJ89] Dah-Ming Chiu and Raj Jain, “Analysis of the Increase/Decrease Algorithms for Congestion Avoidance in Computer Networks”, Journal of Computer Networks volume 17, pp. 1-14, 1989. [CJ91] David Clark and Van Jacobson, “Flexible and efficient resource management for datagram networks”, Presentation, September 1991 [CSZ92] David Clark, Scott Shenker and Lixia Zhang, “Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism”, Proceedings of ACM SIGCOMM 1992, August 1992. [CBcDHL14] David Clark, Steven Bauer, kc claffy, Amogh Dhamdhere, BBradley Huffaker, William Lehr, and Matthew Luckie, “Measurement and Analysis of Internet Interconnection and Congestion”, Telecommunications Policy Research Conference (TPRC) 2014, September 2014. [DR02] Joan Daemen and Vincent Rijmen, “The Design of Rijndael: AES – The Advanced Encryption Standard.”, Springer-Verlag, 2002. [DS78] Yogen Dalal and Carl Sunshine, “Connection Management in Transport Protocols”, Computer Networks 2, 1978. [ID89] Ivan Dåmgard, “A Design Principle for Hash Functions”, Advances in Cryptology - CRYPTO ‘89 Proceedings, Lecture Notes in Computer Science volume 435, Springer-Verlag, 1989. [DKS89] Alan Demers, Srinivasan Keshav and Scott Shenker, “Analysis and Simulation of a Fair Queueing Algorithm”, ACM SIGCOMM Proceedings on Communications Architectures and Protocols, 1989. [DH76] Whitfield Diffie and Martin Hellman, “New Directions in Cryptography”, IEEE Transactions on Information Theory, volume IT-22, November 1976. [EGMR05] Mihaela Enachescu, Ashish Goel, Yashar Ganjali, Nick McKeown and Tim Roughgarden. “Part III: Routers with Very Small Buffers”, ACM SIGCOMM Computer Communication Review, volume 35 number 2, July 2005. [FF96] Kevin Fall and Sally Floyd, “Simulation-based Comparisons of Tahoe, Reno and SACK TCP”, ACM SIGCOMM Computer Communication Review, July 1996. [FRZ13] Nick Feamster, Jennifer Rexford and Ellen Zegura, “The Road to SDN: An Intellectual History of Programmable Networks”, ACM Queue, December 2013. [FGMPC02] Roberto Ferorelli, Luigi Grieco, Saverio Mascolo, G Piscitelli, P Camarda, “Live Internet Measurements Using Westwood+ TCP Congestion Control”, IEEE Global Telecommunications Conference, 2002. [F91] Sally Floyd, “Connections with Multiple Congested Gateways in Packet-Switched Networks, Part 1”, ACM SIGCOMM Computer Communication Review, October 1991. [FJ92] Sally Floyd and Van Jacobson, “On Traffic Phase Effects in Packet-Switched Gateways”, Internetworking: Research and Experience, volume 3, pp 115-156, 1992. [FJ93] Sally Floyd and Van Jacobson, “Random Early Detection Gateways for Congestion Avoidance”, IEEE/ACM Transactions on Networking, volume 1, August 1993. [FJ95] Sally Floyd and Van Jacobson, “Link-sharing and Resource Management Models for Packet Networks”, IEEE/ACM Transactions on Networking, volume 3, June 1995.

Bibliography

833

An Introduction to Computer Networks, Release 1.9.16

[FP01] Sally Floyd and Vern Paxson, “Difficulties in Simulating the Internet”, IEEE/ACM Transactions on Networking, volume 9, August 2001. [FMS01] Scott Fluhrer, Itsik Mantin and Adi Shamir, “Weaknesses in the Key Scheduling Algorithm of RC4”, SAC ‘01 Revised Papers from the 8th Annual International Workshop on Selected Areas in Cryptography, Springer-Verlag, 2001. [FL03] Cheng Fu and Soung Liew, “TCP Veno: TCP Enhancement for Transmission over Wireless Access Networks”, IEEE Journal on Selected Areas in Communications, volume 21 number 2, February 2003. [LG01] Lixin Gao, “On Inferring Autonomous System Relationships in the Internet”, IEEE/ACM Transactions on Networking, volume 9, December 2001. [GR01] Lixin Gao and Jennifer Rexford, “Stable Internet Routing without Global Coordination”, IEEE/ACM Transactions on Networking, volume 9, December 2001. [JG93] Jose J Garcia-Lunes-Aceves, “Loop-Free Routing Using Diffusing Computations”, IEEE/ACM Transactions on Networking, volume 1, February 1993. [GP11] L Gharai and C Perkins, “RTP with TCP Friendly Rate Control”, Internet Draft, http://tools.ietf. org/html/draft-gharai-avtcore-rtp-tfrc-00. [GV02] Sergey Gorinsky and Harrick Vin, “Extended Analysis of Binary Adjustment Algorithms”, Technical Report TR2002-39, Department of Computer Sciences, University of Texas at Austin, 2002. [GM03] Luigi Grieco and Saverio Mascolo, “End-to-End Bandwidth Estimation for Congestion Control in Packet Networks”, Proceedings of the Second International Workshop on Quality of Service in Multiservice IP Networks, 2003. [GM04] Luigi Grieco and Saverio Mascolo, Performance Evaluation and Comparison of Westwood+, New Reno, and Vegas TCP Congestion Control, ACM SIGCOMM Computer Communication Review, volume 34 number 2, April 2004. [GG03] Marco Gruteser and Dirk Grunwald, “Enhancing Location Privacy in Wireless LAN Through Disposable Interface Identifiers:A Quantitative Analysis”, Proceedings of the 1st ACM International Workshop on Wireless Mobile Applications and Services on WLAN Hotspots (WMASH ‘03), September, 2003. [HRX08] Sangtae Ha, Injong Rhee and Lisong Xu, “CUBIC: A New TCP-Friendly High-Speed TCP Variant”, ACM SIGOPS Operating Systems Review - Research and developments in the Linux kernel, volume 42 number 5, July 2008. [SH04] Steve Hanna, “Shellcoding for Linux and Windows Tutorial”, http://www.vividmachines.com/ shellcode/shellcode.html, July 2004 [DH08] Dan Harkins, “Simultaneous Authentication of Equals: A Secure, Password-Based Key Exchange for Mesh Networks”, 2008 Second International Conference on Sensor Technologies and Applications (sensorcomm 2008), August 2008. [MH04] Martin Hellman, “Oral history interview with Martin Hellman”, Charles Babbage Institute, 2004. Retrieved from the University of Minnesota Digital Conservancy, http://purl.umn.edu/107353. [JH96] Janey Hoe, “Improving the Start-up Behavior of a Congestion Control Scheme for TCP”, ACM SIGCOMM Symposium on Communications Architectures and Protocols, August 1996.

834

Bibliography

An Introduction to Computer Networks, Release 1.9.16

[HVB01] Gavin Holland, Nitin Vaidya and Paramvir Bahl, “A rate-adaptive MAC protocol for multi-Hop wireless networks”, MobiCon ‘01: Proceedings of the 7th annual International Conference on Mobile Computing and Networking, 2001. [CH99] Christian Huitema, Routing in the Internet, second edition, Prentice Hall, 1999. [HBT99] Paul Hurley, Jean-Yves Le Boudec and Patrick Thiran, “A Note on the Fairness of Additive Increase and Multiplicative Decrease”, Proceedings of ITC-16, 1999. [JK88] Van Jacobson and Michael Karels, “Congestion Avoidance and Control”, Proceedings of the Sigcomm ‘88 Symposium, volume 18(4), 1988. [JKMOPSVWZ13] Sushant Jain, Alok Kumar, Subhasree Mandal, Joon Ong, Leon Poutievski, Arjun Singh, Subbaiah Venkata, Jim Wanderer, Junlan Zhou, Min Zhu, Jonathan Zolla, Urs Hölzle, Stephen Stuart and Amin Vahdat, “B4: Experience with a Globally-Deployed Software Defined WAN”, Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM, August 12-16, 2013. [JWL04] Cheng Jin, David Wei and Steven Low, “FAST TCP: Motivation, Architecture, Algorithms, Performance”, IEEE INFOCOM 2004 Proceedings, March 2004. [KM97] Ad Kamerman and Leo Monteban, “WaveLAN-II: A high-performance wireless LAN for the unlicensed band”, AT&T Bell Laboratories Technical Journal, volume 2 number 3, 1997. [SK88] Srinivasan Keshav, “REAL: A Network Simulator” (Technical Report), University of California at Berkeley, 1988. [KKCQ06] Jongseok Kim, Seongkwan Kim, Sunghyun Choi and Daji Qiao, “CARA: Collision-Aware Rate Adaptation for IEEE 802.11 WLANs”, IEEE INFOCOM 2006 Proceedings, April 2006. [LK78] Leonard Kleinrock, “On Flow Control in Computer Networks”, Proceedings of the International Conference on Communications, June 1978. [LH06] Mathieu Lacage and Thomas Henderson, “Yet Another Network Simulator”, Proceedings of WNS2 ‘06: Workshop on ns-2: the IP network simulator, 2006. [LM91] Xuejia Lai and James L. Massey, “A Proposal for a New Block Encryption Standard”, EUROCRYPT ‘90 Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, Springer-Verlag, 1991. [LKCT96] Eliot Lear, Jennifer Katinsky, Jeff Coffin and Diane Tharp, “Renumbering: Threat or Menace?”, Tenth USENIX System Administration Conference, Chicago, 1996. [LSL05] DJ Leith, RN Shorten and Y Lee, “H-TCP: A framework for congestion control in high-speed and long-distance networks”, Hamilton Institute Technical Report, August 2005. [LSM07] DJ Leith, RN Shorten and G McCullagh, “Experimental evaluation of Cubic-TCP”, Extended version of paper presented at Proc. Protocols for Fast Long Distance Networks, 2007. [LBS06] Shao Liu, Tamer Basar and R Srikant, “TCP-Illinois: A Loss and Delay-Based Congestion Control Algorithm for High-Speed Networks”, Proceedings of the 1st international conference on performance evaluation methodologies and tools, 2006. [AM90] Allison Mankin, “Random Drop Congestion Control”, ACM SIGCOMM Symposium on Communications Architectures and Protocols, 1990.

Bibliography

835

An Introduction to Computer Networks, Release 1.9.16

[MCGSW01] Saverio Mascolo, Claudio Casetti, Mario Gerla, MY Sanadidi, Ren Wang, “TCP westwood: Bandwidth estimation for enhanced transport over wireless links”, MobiCon ‘01: Proceedings of the 7th annual International Conference on Mobile Computing and Networking, 2001. [McK90] Paul McKenney, “Stochastic Fairness Queuing”, IEEE INFOCOM ‘90 Proceedings, June 1990. [MABPPRST08] Nick McKeown, Tom Anderson, Hari Balakrishnan, Guru Parulkar, Larry Peterson, Jennifer Rexford, Scott Shenker and Jonathan Turner, “OpenFlow: Enabling innovation in campus networks”, ACM SIGCOMM Computer Communications Review, April 2008. [RM78] Ralph Merkle, “Secure Communications over Insecure Channels”, Communications of the ACM, volume 21, April 1978. [RM88] Ralph Merkle, “A Digital Signature Based on a Conventional Encryption Function”, Advances in Cryptology — CRYPTO ‘87, Lecture Notes in Computer Science volume 293, Springer-Verlag, 1988. [MH81] Ralph Merkle and Martin Hellman, “On the Security of Multiple Encryption”, Communications of the ACM, volume 24, July 1981. [MB76] Robert Metcalfe and David Boggs, “Ethernet: Distributed Packet Switching for Local Computer Networks”, Communications of the ACM, volume 19 number 7, 1976. [MW00] Jeonghoon Mo and Jean Walrand, “Fair End-to-End Window-Based Congestion Control”, IEEE/ACM Transactions on Networking, volume 8 number 5, October 2000. [JM92] Jeffrey Mogul, “Observing TCP Dynamics in Real Networks”, ACM SIGCOMM Symposium on Communications Architectures and Protocols, 1992. [MM94] Mart Molle, “A New Binary Logarithmic Arbitration Method for Ethernet”, Technical Report CSRI-298, Computer Systems Research Institute, University of Toronto, 1994. [RTM85] Robert T Morris, “A Weakness in the 4.2BSD Unix TCP/IP Software”, AT&T Bell Laboratories Technical Report, February 1985. [NJ12] Kathleen Nichols and Van Jacobson, “Controlling Queue Delay”, ACM Queue, May 2012. [OKM96] Teunis Ott, JHB Kemperman and Matt Mathis, “The stationary behavior of ideal TCP congestion avoidance”, Technical Report, 1996. [PFTK98] Jitendra Padhye, Victor Firoiu, Don Towsley and Jim Kurose, “Modeling TCP Throughput: A Simple Model and its Empirical Validation”, ACM SIGCOMM conference on Applications, technologies, architectures, and protocols for computer communication, 1998. [PG93] Abhay Parekh and Robert Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks - The Single-Node Case”, IEEE/ACM Transactions on Networking, volume 1 number 3, June 1993. [PG94] Abhay Parekh and Robert Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks - The Multiple Node Case”, IEEE/ACM Transactions on Networking, volume 2 number 2, April 1994. [VP97] Vern Paxson, “End-to-End Internet Packet Dynamics”, ACM SIGCOMM conference on Applications, technologies, architectures, and protocols for computer communication, 1997.

836

Bibliography

An Introduction to Computer Networks, Release 1.9.16

[PWZMTQ17] Changhua Pei, Zhi Wang, Youjian Zhao, Zihan Wang, Yuan Meng, Dan Pei, Yuanquan Peng, Wenliang Tang and Xiaodong Qu, “Why It Takes So Long to Connect to a WiFi Access Point”, IEEE International Conference on Computer Communications, May 2017. [CP09] Colin Percival, “Stronger Key Derivation Via Sequential Memory-Hard Functions”, BSDCan - The Technical BSD Conference, May 2009. [PB94] Charles Perkins and Pravin Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers”, ACM SIGCOMM Computer Communications Review, volume 24 number 4, October 1994. [PR99] Charles Perkins and Elizabeth Royer, “Ad-hoc On-Demand Distance Vector Routing”, Proceedings of the Second IEEE Workshop on Mobile Computing Systems and Applications, February 1999. [RP85] Radia Perlman, “An Algorithm for Distributed Computation of a Spanning Tree in an Extended LAN”, ACM SIGCOMM Computer Communication Review 15(4), 1985. [RP04] Radia Perlman, “Rbridges: Transparent Routing”, IEEE INFOCOM 2004 Proceedings, March 2004. [JP88] John M Pollard, “Factoring with Cubic Integers”, unpublished manuscript circulated 1988; included in “The Development of the Number Field Sieve”, Lecture Notes in Mathematics volume 1554, Springer-Verlag, 1993. [PDG12] Balaji Prabhakar, Katherine N Dektar and Deborah M Gordon, “The Regulation of Ant Colony Foraging Activity without Spatial Information”, PLoS Computational Biology 8(8), http://journals.plos. org/ploscompbiol/article?id=10.1371/journal.pcbi.1002670 [PN98] Thomas Ptacek and Timothy Newsham, “Insertion, Evasion, and Denial of Service: Eluding Network Intrusion Detection”, Technical report, Secure Networks Inc, January 1998. [RJ90] Kadangode Ramakrishnan and Raj Jain, “A Binary Feedback Scheme for Congestion Avoidance in Computer Networks”, ACM Transactions on Computer Systems, volume 8 number 2, May 1990. [RX05] Injong Rhee and Lisong Xu, “Cubic: A new TCP-friendly high-speed TCP variant,” 3rd International Workshop on Protocols for Fast Long-Distance Networks, February 2005. [RR91] Ronald Rivest, “The MD4 message digest algorithm”, Advances in Cryptology - CRYPTO ‘90 Proceedings, Springer-Verlag, 1991. [RSA78] Ronald Rivest, Adi Shamir and Leonard Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications of the ACM, volume 21, February 1978. [SRC84] Jerome Saltzer, David Reed and David Clark, “End-to-End Arguments in System Design”, ACM Transactions on Computer Systems, volume 2 number 4, November 1984. [BS93] Bruce Schneier, “Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)”, Fast Software Encryption, Cambridge Security Workshop Proceedings (December 1993), Springer-Verlag, 1994. [SM90] Nachum Shacham and Paul McKenney, “Packet recovery in high-speed networks using coding and buffer management”, IEEE INFOCOM ‘90 Proceedings, June 1990. [SP03] Umesh Shankar and Vern Paxson, “Active Mapping: Resisting NIDS Evasion without Altering Traffic”, Proceedings of the 2003 IEEE Symposium on Security and Privacy, 2003.

Bibliography

837

An Introduction to Computer Networks, Release 1.9.16

[SV96] M Shreedhar and George Varghese, “Efficient Fair Queuing Using Deficit Round Robin”, IEEE/ACM Transactions on Networking, volume 4 number 3, June 1996. [JS05] John Ivan Simon, “John Simon on Music: Criticism, 1979-2005”, Applause Books, 2005. [SKS06] Rade Stanojevi´c, Christopher Kellett and Robert Shorten, “Adaptive Tuning of Drop-Tail Buffers for Reducing Queuing Delays”, IEEE Communications Letters, volume 10 number 7, August 2006. [TSZS06] Kun Tan, Jingmin Song, Qian Zhang and Murari Sidharan, “Compound TCP: A Scalable and TCP-friendly Congestion Control for High-speed Networks”, 4th International Workshop on Protocols for Fast Long-Distance Networks (PFLDNet), 2006. [TWHL05] Ao Tang, Jintao Wang, Sanjay Hegde and Steven Low, “Equilibrium and Fairness of Networks Shared by TCP Reno and Vegas/FAST”, Telecommunications Systems special issue on High Speed Transport Protocols, 2005. [TWP07] Erik Tews, Ralf-Philipp Weinmann and Andrei Pyshkin, “Breaking 104-bit WEP in less than 60 seconds”, WISA‘07 Proceedings of the 8th International Conference on Information Security Applications, Springer-Verlag, 2007. [VMCCP16] Mathy Vanhoef, Célestin Matte, Mathieu Cunche, Leonardo Cardoso and Frank Piessens, “Why MAC Address Randomization is not Enough: An Analysis of Wi-Fi Network Discovery Mechanisms”, ACM Asia Conference on Computer and Communications Security, May 2016. [VP17] Mathy Vanhoef and Frank Piessens, “Key Reinstallation Attacks: Forcing Nonce Reuse in WPA2”, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, October 2017. [VGE00] Kannan Varadhan, Ramesh Govindan and Deborah Estrin, “Persistent Route Oscillations in Interdomain Routing”, Computer Networks, volume 32, January, 2000. [SV02] Serge Vaudenay, “Security Flaws Induced by CBC Padding – Applications to SSL, IPSEC, WTLS. . . ”, EUROCRYPT ‘02 Proceedings, 2002. [WJLH06] David Wei, Cheng Jin, Steven Low and Sanjay Hegde, “FAST TCP: Motivation, Architecture, Algorithms, Performance”, ACM Transactions on Networking, December 2006. [WM05] Damon Wischik and Nick McKeown, “Part I: Buffer Sizes for Core Routers”, ACM SIGCOMM Computer Communication Review, volume 35 number 2, July 2005. [LZ89] Lixia Zhang, “A New Architecture for Packet Switching Network Protocols”, PhD Thesis, Massachusetts Institute of Technology, 1989. [ZSC91] Lixia Zhang, Scott Shenker and David Clark, “Observations on the Dynamics of a Congestion Control Algorithm: The Effects of Two-Way Traffic”, ACM SIGCOMM Symposium on Communications Architectures and Protocols, 1991.

838

Bibliography

INDEX

Symbols .onion addresses, 206 /64, IPv6, 245 /etc/resolv.conf, 205 0-RTT protection, QUIC, 390 0-RTT protection, TLS v1.3, 798 1-RTT protection, QUIC, 390 1-RTT protection, TLS v1.3, 798 127.0.1.1, 206 2-D parity, 159 2.4 GHz, 99 3DES, 772 4B/5B, 139 4G, 124 5 GHz, 99 6LoWPAN, 98 6in4, IPv6, 252 802.11, 98 802.11i, IEEE, 114 802.11r handoff, 111 802.16, 124 802.1Q, 68 802.1X, IEEE, 117 802.3, IEEE Ethernet, 46

A A and AAAA records, DNS, 246 A record, DNS, 205 accelerated open, TCP, 375 access point, CDN, 33 access point, Wi-Fi, 107 accurate costs, 266 ACD, IPv4, 211 ACK compression, 480 ACK, TCP, 353 acknowledgment, 30 acknowledgment number, TCP, 353

acknowledgments, QUIC, 388 ACKs of unsent data, TCP, 366 ACK[N], 165 active close, TCP, 368 active queue management, 449 active subqueue, 611 ad hoc configuration, Wi-Fi, 107 ad hoc wireless network, 122 adaptive droptail algorithm, 453 additive increase, multiplicative decrease, 400 address, 14 address configuration, manual IPv6, 251 address ownership, QUIC, 390 address randomization, 757 Address Resolution Protocol, 210 AddressFamily, 329 Administratively Prohibited, 217 admission control, RSVP, 664 ADT, 453 advertised window size, 377 AES, 772 AF drop precedence, 670 AfriNIC, 29 agent configuration, SNMP, 710 agent, SNMP, 685 AH, IPsec, 805 AIMD, 400, 447 algorithm, AODV, 270 algorithm, distance-vector, 260 algorithm, DSDV, 268 algorithm, EIGRP, 273 algorithm, Ethernet learning, 59 algorithm, exponential backoff, 51 algorithm, fair queuing bit-by-bit round-robin, 613 algorithm, fair queuing GPS, 615 algorithm, fair queuing, quantum, 621 algorithm, Floyd-Warshall, 603

839

An Introduction to Computer Networks, Release 1.9.16

algorithm, hierarchical weighted fair queuing, 630 algorithm, HWMP, 272 algorithm, Karn/Partridge, 379 algorithm, link-state, 274 algorithm, loop-free distance vector, 268 algorithm, Nagle, 377 algorithm, Shortest-Path First, 275 algorithm, spanning-tree, 63 Alice, 765 alignment, memory, 188 all-nodes multicast address, 231 all-routers multicast address, 231 ALOHA, 55 AMI, 141 anternet, 397 anycast address, IPv6, 229 anycast, via BGP, 308 Aodh, 765 AODV, 270, 569 APNIC, 29 AQM, 449 ARC4, 774 ARCFOUR, 774 architecture, network, 685 argon2, 768 ARIN, 29 arithmetic, fast, 780 ARP, 210 ARP cache, 211 ARP failover, 213 ARP spoofing, 213 ARPANET, 37 ARQ protocols, 165 AS-path, 297 AS-set, 299 ASLR, 757 ASN.1, 688, 690 ASN.1 enumerated type, 706 association, Wi-Fi, 107 Assured Forwarding, 670 Assured Forwarding PHB, 668 asymmetric routes, 294 Asynchronous Transfer Mode, 92 at-least-once semantics, 344 ATM, 15, 92 augmentation, SNMP, 718 authentication header, IPsec, 805 authentication with secure-hash functions, 766 840

authenticator, WPA, 117 authoritative nameserver, 205 autoconfiguration, IPv4, 215 autonomous system, 259, 287, 297

B B8ZS, 141 backbone, 28 backoff, Ethernet, 51 backup link, BGP, 306 backwards compatibility, TCP, 470 bad news, distance-vector, 261 band width, wireless, 95 bandwidth, 14 bandwidth ˆ delay, 152, 171 bandwidth delay, 149 bandwidth guarantees, 639 base station, WiMAX, 125 basic encoding rules, 712 BBR TCP, 493 BBRR, 613 bcrypt, 768 BDP, 171 beacon packets, Wi-Fi, 108 beacon, Wi-Fi, 111 beefcafe, 251 BER, 712 Berkeley Packet Filter, 591 Berkeley Unix, 39 best-effort, 25, 30 best-path selection, BGP, 300 BGP, 296, 311 BGP relationships, 309 BGP speaker, 297 big-endian, 15 binary data, 331 bind(), 326 bit stuffing, 140 bit-by-bit round robin, 613 BLAM, 53 Blowfish, 773 Bluetooth, 98 Bob, 765 boot counter, 346 border gateway protocol, 296 border routers, 267 bottleneck link, 173, 426 BPDU message, spanning tree, 64 Index

An Introduction to Computer Networks, Release 1.9.16

bpf, 591 bps, 14, 22 broadcast IPv4 address, 190 broadcast, Ethernet, 23 broadcast, MANETs, 123 BSD, 39 buffer overflow, 34 buffer overflow, heap, 758 bufferbloat, 416, 449, 623 bugs, 806 byte stuffing, 140

C CA, 790 cache, DNS, 205 CAM table, 62 canonical name, DNS, 208 Canopy, 130 capture effect, Ethernet, 53 care-of address, 221 carrier Ethernet, 86 CBC mode, 773 CDN and IntServ, 665 CDN closest edge server, 209 CDNs, 33 cell-loss priority bit, ATM, 92 censorship, 796 certificate authorities, 786 certificate authority, 790 certificate pinning, 792 certificate revocation, 793 certificate revocation list, 793 CFB mode, 775 CGA, 237 challenge-handshake authentication, 768 channel width, 95 channel, Wi-Fi, 100 chap authentication, 768 checksum offloading, 59, 359 checksum, TCP, 352 checksum, UDP, 321 Christmas day attack, 374 chrome://flags, 387 chrome://net-internals, 387 CIDR, 287 cipher feedback mode, 775 cipher modes, 773 Cisco, 68, 273, 305 Index

class A/B/C addressing, 24 Class Selector PHB, 668 class, queuing discipline, 609 classful queuing discipline, 609 Classless Internet Domain Routing, 287 clear-to-send, Wi-Fi, 102 client, 31 client-server, 33 ClientHello, TLS, 795 ClientKey, 769 ClientSignature, 769 cliff, 20, 399 CLNP, 38 clock recovery, 137 clock synchronization, 137 close, TCP, 355, 369 closest CDN edge server, 209 CMIP, 684 CMNS, 38 CMOT, 684 CNAME, DNS, 208 CoDel, 453 collision, 22, 45 collision attack, MD5, 766 collision avoidance, 102 collision detection, 46, 54, 56 collision detection, wireless, 94 collision domain, 59 collision problem, hash, 765 collision, Wi-Fi, 101 commands, Mininet, 574 community attribute, BGP, 305, 306 community, SNMP, 710 concave cwnd graph, 473 configuring FreeRADIUS, 118 configuring WPA2-Enterprise, 118 congestion, 20, 26, 31 congestion avoidance phase, 399 congestion bit, 450 congestion window, 398 connect(), 328, 331 connection, 14 connection table, virtual circuit, 89 connection-oriented, 351 connection-oriented networking, 26 connectionless networking, 26 conservative, 37 Content-Distribution Networks, 33 841

An Introduction to Computer Networks, Release 1.9.16

contention, 20 contention interval, 54 contributing source, RTP, 675 control packet, Wi-Fi, 99 control packet, Wi-Fi ACK, 101 control packet, Wi-Fi RTS/CTS, 102 convergence to TCP fairness, 448, 470 convex cwnd graph, 473 counter mode, 775 CRC code, 157 cross-site scripting, 762 crossbar switch, 62 cryptographically generated address, 206, 237 CSMA, 54 CSMA persistence, 54 CSMA/CA, 102 CSMA/CD, 46 CSRC, 675 CTR mode, 775 CTS, Wi-Fi, 102 Cubic, TCP, 489 cumulative ACK, 170 customer, BGP, 309 cut-through, 21 cwnd, 398 CWR, 353, 450 cyclical redundancy check, 157

D DAD, IPv6, 239 DALLY, TFTP, 338 Data Center TCP, 485 data rate, 14 data types, SNMPv1, 690 datacenter, 75 Datagram Congestion Control Protocol, 323 datagram forwarding, 14 Data[N], 165 DCCP, 323 DCCP congestion control, 446 DCCP connection establishment, 383 DCTCP, 485 deadbeef, 316 DECbit, 450 DECnet, 450 default forwarding entry, 194 default route, 17, 28 deflation, cwnd, 410 842

delay constraints, 642 delay, bandwidth, 149 delay, largest-packet, 155 delay, propagation, 149 delay, queuing, 149 delay, store-and-forward, 149 delay-based congestion control, 475 delayed ACKs, 377, 404 denial of service attack, 187 dense wavelength-division multiplexing, 146 DES, 772 Destination Unreachable, 217 DHCP, 214 DHCP Relay, 215 DHCPv6, 238, 241 Differentiated Services, 186, 667 Diffie-Hellman-Merkle key exchange, 779 DiffServ, 667 DIFS, Wi-Fi, 101, 122 dig, 35 digital signatures, RSA, 783 discrete logarithm problem, 779 distance vector, loop-free versions, 268 distance-vector, 29 distance-vector routing update, 260 distribution network, Wi-Fi, 111 DIX Ethernet, 46 DNS, 29, 204, 214, 327, 329, 330, 342, 363 DNS A and AAAA records, 246 DNS and CDNs, 209 DNS and IPv6, 238, 240, 246 DNS, round-robin, 206 domain fronting, 796 Domain Name System, 204 domain name system, 29 Dont Fragment bit, 192 doze mode, Wi-Fi, 109 draft standard, 38 Dragonfly, 780 drop precedence, DiffServ AF, 670 DS, 186 DS domain, 667 DS field, IPv4 header, 667 DS1 line, 142 DS3 line, 143 DSDV, 268, 569 DSO channel, 142 dual stack, 246 Index

An Introduction to Computer Networks, Release 1.9.16

DuckDuckGo, 206 dumbbell network topology, 434 duplicate address detection, IPv4, 211 duplicate connection request, 338 duplicate-address detection, IPv6, 239 durian, 726 DWDM, 146 dynamic rate scaling, 104

E EAP, 117 EAPOL, 117 EasyConnect, Wi-Fi, 120 EasyMesh Wi-Fi, 112 ECB mode, 773 ECE, 353, 450 Echo Request/Reply, 217 ECMP, 279, 600 ECN, 186, 450 ECN and VPNs, 86 ECT, 450 edge server, CDN, 33 edge server, closest, 209 EFS, 408 EGP, 299 EIGRP, 273 elephant flow, 278 elevator algorithm, 345 elliptic-curve cryptography, 782 eNB, LTE, 125 encapsulated security payload, IPsec, 805 encoding, 331 encrypt-and-MAC, 776 encrypt-then-MAC, 776 encryption, 770 end-to-end encryption, 786 End-to-End principle, 165, 352 engines, SNMPv3, 736 enumerated type, SNMP, 706 equal-cost multipath routing, 279, 600 error message, ICMP, 216 error-correcting code, 159 error-detection code, 155 ESP, IPsec, 805 ESS, Wi-Fi, 111 estimated flightsize, 408 Ethernet, 22 Ethernet address, 23 Index

Ethernet hub, 46 Ethernet repeater, 46 Ethernet switch, 59 Ethernet switch hardware, 61 ethtool, Linux, 359 Euclidean algorithm, 782 EUI-64 identifier, 227 evasion, intrusion detection, 763 exactly-once semantics, 344 Expedited Forwarding, 668 Expedited Forwarding PHB, 668 expiration date, certificate, 793 Explicit Congestion Notification, 186, 450 exponential backoff, Ethernet, 51 exponential backoff, Wi-Fi, 102 exponential growth, 402 export filtering, BGP, 300 extended interface table, SNMP, 720 extended-validation certificates, 792 extender, Wi-Fi, 112 Extensible Authentication Protocol, 117 extension headers, 231 exterior routing, 296 extreme TCP unfairness, 440

F face:b00c, 246 facebookcorewwwi, 206 factoring RSA keys, 784 fading, 96 fair queuing, 610 fair queuing and AF, 671 fair queuing and EF, 669 fairness, 31 fairness, TCP, 426, 434, 441, 470 fallback to flooding, 59 fast arithmetic, 780 Fast Ethernet, 56 fast handoff, Wi-Fi, 111 Fast Open, TCP, 376 fast primality testing, 780 Fast Recovery, 408 fast retransmit, 406 fastest sequence, token-bucket, 637 FCAPS, 683 Feistel network, 771 Fibonacci sequence, 648 FIFO queuing, 425 843

An Introduction to Computer Networks, Release 1.9.16

fill time, voice, 142 filtering, BGP, 300 filterspec, 663 FIN, 353 FIN packet, 355 finishing order, WFQ, 617 firewall, 34, 71, 75 fixed wireless, 128 flights of packets, 399 flightsize, 494 flightsize, estimated, 408 flow control, 169 flow control, QUIC, 388 flow control, TCP, 378 Flow Label, 226 flow specification, 633 flow tables, 72 flow, IPv6, 226 flow, TCP, 598 flowspec, RSVP, 663 Floyd-Warshall algorithm, 603 fluid model, fair queuing, 615 foraging, 397 foreign agent, 221 fortune, 206 forward secrecy, 784 forwarding delay, 21 forwarding table, 15 forwarding, IP, 26 forwarding, MANET, 124 four-way handshake, Wi-Fi, 114 foxes, 397 fragment header, IPv6, 233 fragment offset, 191 fragmentation, 25 Fragmentation Required, 217 fragmentation, IP, 191 fragmentation, Wi-Fi, 104 frame, 14 frames, QUIC, 387 framing, 140 FreeRADIUS, 118 frequency band, 95 Friendliness, TCP, 444 Frost, Robert, 88 full-duplex Ethernet, 57 fwmark, 279, 591

844

G generalized processor sharing, 615 generic hierarchical queuing, 625 geoDNS, 209 geographical routing, 295 geolocation, IP, 295 GET request, HTTP, 365 getaddrinfo(), 246 getAllByName(), Java, 327 getAllByName(), java, 329 GetBulk, SNMPv2, 716 getByName(), 247 getByName(), Java, 246 getByName(), java, 329 gethostbyname(), 246 gigabit Ethernet, 57 glibc-2.2.4, 758 global scope, IPv6 addresses, 242 GNS, 205 Gnu DNS, 205 Gnu Name System, 205 goodput, 14, 505 GPS, fair queuing, 615 granularity, loss counting, 533 gratuitous ARP, 211 greediness in TCP, 438 group, OpenFlow, 600 GTC, EAP, 118

H H-TCP, 488 half-closed, TCP, 368 half-open, TCP, 368 Hamilton TCP, 488 Hamming code, 159 handoff, Wi-Fi, 111 Handshake packet, QUIC, 389 handshake protocol, TLS, 794 Happy Eyeballs, IPv6, 248 hard fail, OCSP, 793 hardware, Ethernet switch, 61 Hash Message Authentication Code, 767 hash, password, 768 HDLC, 140 head-of-line blocking, 32, 322, 657 header, 14 header, Ethernet, 47 header, IPv4, 185 Index

An Introduction to Computer Networks, Release 1.9.16

header, IPv6, 225 header, TCP, 352 header, UDP, 321 heap buffer overflow, 758 heap vulnerability, 758 Hellman (Diffie-Hellman-Merkel), 779 Hello, spanning-tree, 64 henhouse, 397 hidden node problem, 95 hidden-node collisions, 103 hidden-node problem, 103 hierarchical routing, 195, 287, 289 hierarchical token bucket, 642 hierarchical token bucket, Linux, 644 high-bandwidth TCP problem, 454 Highspeed TCP, 471 history, RMON, 728 HMAC, 738, 767 hold down, 266 home address, 221 home agent, 221 host command, 35 host key, ssh, 788 Host Top N, RMON, 731 Host Unreachable, 217 host-specific forwarding, 86 hot-potato routing, 294 htb, Linux, 588, 644 htonl, 332 htons, 332 HTTP, 365, 372 https, 787 hub, Ethernet, 46 hulu, 655 HWMP, 272 Hybla, TCP, 485

I IAB, 37 IANA, 24, 29, 707 ICANN, 204 ICMP, 216 ICMPv6, 243 IDEA, 773 idempotency and 0-RTT, 798 idempotent, 344 IDENT field, 191 IEEE, 46, 49 Index

IEEE 802.11, 98 IEEE 802.1Q, 68 IEEE 802.1X, 117 IEEE 802.3 Ethernet, 46 IETF, 37 ifconfig, 35 ifDescr, 706 ifIndex, 705 IFS, Wi-Fi, 101 ifType, SNMP, 706 ifXTable, SNMP, 720 IKEv2, 807 Illinois, TCP, 481 implementations, at least two, 38 import filtering, BGP, 300 incarnation, connection, 335 incast, TCP, 488 inetCidrRouteTable, 724 inflation, cwnd, 410 infrastructure configuration, Wi-Fi, 107 Initial packet, QUIC, 389 initial sequence number, TCP, 353, 357, 372 initialization vector, 773 instability, BGP, 313 integrated services, 657 integrated services, generic, 653 interconnection fabric, 75 interface, 188 interface identifier, ipv6, 227 interface table, extended, SNMP, 720 interior routing, 259 Internet Architecture Board, 37 Internet checksum, 156 Internet Engineering Task Force, 37 Internet exchange point, 292 Internet Key Exchange, 807 Internet Society, 37 intersymbol interference, 96 intrusion detection, 763 IntServ, 657 IP, 13, 24 ip command (Linux), 35 IP forwarding, 26 IP fragmentation, 191 IP multicast, 658 IP network, 25 IP-in-IP encapsulation, 221 ipconfig, 35 845

An Introduction to Computer Networks, Release 1.9.16

IPsec, 805 iptables, 279, 591 IPv4 header, 185 IPv6, 225, 230 IPv6 /64, 245 IPv6 address configuration, manual, 251 IPv6 addresses, 226 IPv6 connections, link-local, 250 IPv6 extension headers, 231 IPv6 header, 225 ipv6 interface identifier, 227 IPv6 link-local connections, 250 IPv6 multicast, 230 IPv6 Neighbor Discovery, 234 IPv6 programming, 327 IPv6 tunnel, 252 irregular prime, 27 IS-IS, 274 ISM band, 99 ISN, 357, 372 ISOC, 37 ISP, 17 IV, 773 IXP, 292

J jail, staying out of, 292 Java getAllByName(), 327 java getAllByName(), 329 Java getByName(), 246 java getByName(), 329 javascript, 762 jitter, 33, 416, 449, 655, 676 join, multicast, 660 joining a Wi-Fi network, 108 JPEG heap vulnerability, 760 JSON, 333 jumbogram, IPv6, 232

K Karn/Partridge algorithm, 379 kB, 14 KeepAlive, TCP, 380 key exchange, TLS, 797 key-scheduling algorithm, RC4, 774 key-signing parties, 786 keystream, 773 KiB, 14 846

kings, 37 knee, 20, 399, 475 known_hosts, ssh, 788 KRACK attack, WPA, 116

L LACNIC, 29 ladder diagram, 151 LAN, 13, 22 LAN layer, 49 LARTC, 278 latching on, TFTP, 334 layer 3 switch, 200 layers, 13 leaky bucket, alternative formulation, 636 learning, Ethernet switch, 23, 59, 73 legacy routing, 290 length-extension vulnerability, 766 liberal, 37 licensing this book, 3 lightning, 146 limiting delay, 640 link-layer ACK, 101 link-local address, 228 link-state packets, 274 link-state routing update, 274 Linux, 107, 211, 213, 220, 250, 251, 467, 481, 489, 609 Linux advanced routing, 278 Linux htb, 644 Linux IPv6 routing, 234 Linux sfq, 622 Lisp, 771 listen, 31 little-endian, 15 load balancer, Pox, 600 load-balancing, 306 load-balancing, SDN, 76 load-balancing, traditional, 77 local traffic, 300 local-area network, 22 logical link layer, 13 logjam attack, 780 lollipop numbering, 275 longest-match rule, 289, 293 loopback address, 190 loopback interface, 188 loss recovery, sliding windows, 173 Index

An Introduction to Computer Networks, Release 1.9.16

loss synchronization, 440 loss synchronization, TCP, 438 loss-based congestion control, 475 loss-tolerant, 322, 654 lossy-link TCP problem, 455 lost final ACK, 337 lost final ACK, TFTP, 338 LRO, TCP, 359 LSA, 274 LSO, TCP, 359 LSP, 274 LTE, 124

M MAC address, 23 MAC address randomization, 110 MAC layer, 49 MAC-then-encrypt, 776 MAE, 292 MAE-East, 292 man-in-the-middle attack, 780, 785 managed device, SNMP, 685 management frame protection, Wi-Fi, 120 management packet, Wi-Fi, 99, 108 manager, SNMP, 685 Manchester encoding, 138 MANET, 122 mangling, 73, 279 manual IPv6 address configuration, 251 MapReduce, 488 market, IPv4 addresses, 29 master secret, TLS, 797 Matrix, RMON, 731 max-min fairness, 441 Maximum Transfer Unit, 191 MB, 14 Mbone, 662 Mbps, 14, 22 MD5, 766 MED, 295, 301, 303 media-access control, 49 Merkle (Diffie-Hellman-Merkel), 779 Merkle-Dåmgard construction, 766 mesh network, 122 mesh network, HWMP, 272 MiB, 14 MIB browsers, 701 MIB-2, 702 Index

MIC, 115 Michael, 115 Microsoft SNMP agent, 711 middlebox, 203 middleboxes, 357 middleboxes and ECN, 451 MIMO, 105 minimal network configuration, 214 minimizing route cost, 266 minimum RTO, TCP, 487 mininet, 569 Mininet commands, 574 MISO, 106 Mitnick, Kevin, 22, 374 mixer, RTP, 674 mobile IP, 220 mobile wireless network, 122 modified EUI-64 identifier, 227 MPLS, 678 MPTCP, 381 msieve, 810 MTU, 191 multi-exit discriminator, 301, 303 multi-protocol label switching, 678 multicast, 230 multicast address allocation, 662 multicast IP address, 190 multicast programming, 581 multicast subscription, 660 multicast tree, 658 multicast, Ethernet, 48 multicast, IP, 24, 658 multihomed, 189, 292 multihoming and ARP, 213 multihoming and TCP, 360 multihoming and UDP, 326 multipath interference, 96 Multipath TCP, 381 multiple flow tables, 74 multiple losses, 470 multiple token buckets, 637 MUST, 37 MX records, DNS, 209

N Nagle algorithm, 377 naked domain, DNS, 208 nameserver, 205 847

An Introduction to Computer Networks, Release 1.9.16

NAT, 200, 222, 253, 321, 352 NAT and ICMP, 218 NAT and IPsec, 808 NAT problems, 202 NAT-PT, IPv6-to-IPv4, 255 NAT64, 256 nc, 330 Neighbor Advertisement, IPv6, 236 neighbor discovery security, 236 Neighbor Discovery, IPv6, 234 Neighbor Solicitation, IPv6, 235 net neutrality, 654 Net-SNMP, 685, 689, 701, 703, 711 Net-SNMP and SNMPv3, 741 netcat, 37, 330, 365 netcat HTTP GET request, 365 netem queue, 584 netsh (Windows), 35 netstat, 36, 367 network address, 25 network address translation, 200 network architecture, 685 network entry, WiMAX, 128 Network File System, 344 network interface, Ethernet, 23 network management, 608 Network Management System, 684 network model five layer, 13 four layer, 13 seven layer, 38 network number, 25 network prefix, 25 network prefix, IPv6, 229 Network Unreachable, 217 NewReno, TCP, 411 next_hop, 15 NEXT_HOP attribute, BGP, 302 NFS, 344 NMS, 684 no-transit, BGP, 306 no-valley theorem, BGP, 312 node information message, IPv6, 244 non-compliant, token-bucket, 633 non-congestive loss, 455 non-executable stack, 757 non-recursive DNS lookup, 206 non-repudiation, 765, 768 848

nonce, 768, 769 nonce, cryptographic, 795 nonpersistence, 54 NOPslide, 755 noSuchObject, SNMP, 715 NoTCP Manifesto, 322 NRZ, 137 NRZI, 138 NS record, DNS, 205 ns-2 trace file, 508 ns-2 tracefiles, reading with python, 512 NSFNet, 37 NSIS, 672 nslookup, 35, 206, 246 ntohl, 332 ntohs, 332 number-field sieve, 784 NX page bit, 757

O Object ID, SNMP, 686 OBJECT-IDENTITY, SNMP, 715 OBJECT-TYPE, SNMP, 691 OC-3, 144 OCSP, 793 OCSP stapling, 794 OFDM, 95 OFDMA, 95 offloading, TCP, 359 OID, SNMP, 686 old duplicate packets, 335 old duplicates, TCP, 370, 371 OLSR, 569 on-demand mode, HWMP, 272 one-time pad, 773 ones-complement, 156 onion addresses, 206 OpenBSD, 758 OpenFlow, 72 openssl, 119 openSSL programming, 799 Opportunistic Wireless Encryption, 120 Optical Transport Network, 145 optimistic DAD, 239 opus, 655 orthogonal frequency-division multiplexing, 95 OSI, 37 OSPF, 274 Index

An Introduction to Computer Networks, Release 1.9.16

OTN, 145 overhead, ns-2, 526

P packet loss rate, 442 packet pairs, 433 packet size, 153 PAP, EAP, 118 Parekh-Gallager claim, 620 Parekh-Gallager theorem, 646 parking-lot topology, 441 partial ACKs, 411 passive close, TCP, 368 password hash, 768 password sniffing, 22, 213 path attributes, BGP, 302 path bandwidth, 173 Path MTU Discovery, 192, 217 path MTU discovery, TCP, 376 PATH packet, RSVP, 663 PAWS, TCP, 375 PBKDF2, 768 PCF Wi-Fi, 121 PEAP, 118 peer, BGP, 309 peer-to-peer, 33 per-hop behaviors, DiffServ, 667 perfect forward secrecy, 784 persist timer, TCP, 378 persistence, 54 phase effects, TCP, 523 PHBs, DiffServ, 667 physical address, Ethernet, 23 physical layer, 13 PIFS, Wi-Fi, 122 PIM-SM, 660 ping, 35, 217 ping6, 250 pinning, TLS certificates, 792 pipe drain, 173 pipelining, SMTP, 160 PKI, 786 playback buffer, 655 PMK, 802.1X, 117 Pogonomyrmex, 397 Point of Presence, 33 point-to-point protocol, 140 poison reverse, 265 Index

policing, 633 policy-based routing, 72, 278 Pollard’s rho algorithm, 810 polling mode, Wi-Fi, 121 polling, TCP, 378 POODLE vulnerability, 786 Port Control Protocol, 203 port exhaustion, TCP, 372 port numbers, UDP, 321 Port Unreachable, 217 potatoes, hot, 294 power and wireless, 98 power management, Wi-Fi, 109 Pox controller, 592 PPP, 140 PPPoE, 140 pre-master secret, TLS, 797 prefix information, IPv6, 235 presentation layer, 38 presidents, 37 primality testing, fast, 780 Prime Number Theorem, 780 primitive root modulo p, 779 priority for small packets, WFQ, 617 priority queuing, 426, 608 priority queuing and AF, 671 privacy, 94 privacy extensions, SLAAC, 240 private IPv4 address, 190 private IPv6 address, 230 PRNG, 773 proactive mode, HWMP, 272 probe request, Wi-Fi, 110 probing, IPv6 networks, 228 promiscuous mode, 48 propagation delay, 149 proportional fairness, 442 protection against wrapped segments, TCP, 375 protocol graph, 39 protocol-independent multicast, 660 provider, BGP, 309 provider-based routing, 290 proxy ARP, 212 pseudorandom number generator, 773 PSH, 353 PSK, WPA2, 114 PTK, 114 public-key encryption, 782 849

An Introduction to Computer Networks, Release 1.9.16

public-key infrastructure, 786 pulse stuffing, TDM, 143 push, TCP, 353 python tracefile script, 514–516, 539 python, reading ns-2 tracefiles, 512

Q QoS, 653 QoS and routing, 259 quality of service, 17, 26, 259, 653 quantum algorithm, fair queuing, 621 Query Identifier, ICMP, 216 query, ICMP, 216 queue capacity, typical, 416, 449 queue overflow, 26 queue utilization, token bucket, 640 queue-competition rule, 427 queuing delay, 149 queuing discipline, 609 queuing theory, 425 queuing, priority, 608 QUIC, 322, 385 quiet time on startup, TCP, 375

R race condition, Pox, 599 RADIUS, 117 radvd, 234, 253 random drop queuing, 425 Random Early Detection, 452 randomization of MAC addresses, 110 ranging intervals, WiMAX, 127 ranging, WiMAX and LTE, 126 rate control, Wi-Fi, 104 rate scaling, Wi-Fi, 104 rate-adaptive traffic, 655 RC4, 774 Real-Time Protocol, 446 real-time traffic, 653, 655 Real-time Transport Protocol, 32 reassembly, 25 reassociation, Wi-Fi, 111 reboot and RPC, 346 reboots, 339 Record Route, IP option, 187 recursive DNS lookup, 206 RED, 452 Reed-Solomon codes, 146 850

regional registry, 29 registry, regional, 29 reliable, 351 reliable flooding, 274 Remote Procedure Call, 342 rendezvous point, multicast, 660 Reno, 39, 399 Reno vs Vegas, 542 repeater, Ethernet, 46 repeaters, Wi-Fi, 112 request for comment, 37 request-to-send, Wi-Fi, 102 request/reply, 32, 342, 351 reservations, 26 reset, TCP, 353 resolver, DNS, 205 RESV packet, RSVP, 663 retransmit-on-duplicate, 167 retransmit-on-timeout, 165 return-to-libc attack, 750 reverse DNS, 208 RFC, 37 RFC 1034, 204, 208 RFC 1065, 686 RFC 1066, 702 RFC 1122, 17, 186, 189, 212, 321, 326, 358, 360, 370, 372, 377, 379–381, 394 RFC 1123, 340 RFC 1142, 274 RFC 1155, 686, 688, 690, 691, 694 RFC 1213, 686, 689, 702–704, 706, 708, 709, 724–726 RFC 1271, 726, 728 RFC 1312, 722 RFC 1321, 766 RFC 1323, 375 RFC 1350, 333, 336, 340 RFC 1354, 722–724 RFC 1441, 686 RFC 1442, 686, 715 RFC 1450, 720 RFC 1518, 288 RFC 1519, 288 RFC 1550, 225 RFC 1644, 375 RFC 1650, 721 RFC 1661, 85 RFC 1700, 15, 332 Index

An Introduction to Computer Networks, Release 1.9.16

RFC 1812, 220 RFC 1831, 344 RFC 1854, 160 RFC 1883, 225 RFC 1884, 225 RFC 1901, 686, 715 RFC 1909, 715 RFC 1948, 374 RFC 1981, 376 RFC 1994, 768 RFC 2001, 411 RFC 2003, 221 RFC 2011, 722 RFC 2026, 38 RFC 2096, 723, 724 RFC 2104, 738, 767 RFC 2119, 37 RFC 2131, 214 RFC 2136, 240 RFC 2233, 708 RFC 2264, 686 RFC 2309, 453 RFC 2328, 274 RFC 2362, 660 RFC 2386, 259 RFC 2433, 768 RFC 2453, 260, 266, 580 RFC 2460, 156, 225, 226, 232, 233, 352 RFC 2461, 234 RFC 2464, 231 RFC 2473, 232 RFC 2474, 186 RFC 2475, 667 RFC 2481, 186, 450 RFC 2529, 252 RFC 2570, 734 RFC 2574, 735 RFC 2578, 686, 694, 712, 715 RFC 2579, 732 RFC 2581, 377, 405 RFC 2582, 411 RFC 2597, 668, 670, 671 RFC 2616, 365 RFC 2675, 232 RFC 2759, 768 RFC 2766, 255 RFC 2780, 232 RFC 2786, 739 Index

RFC 2819, 726, 727 RFC 2827, 187, 374 RFC 2851, 725 RFC 2856, 715 RFC 2863, 704–707, 721, 725 RFC 2865, 117 RFC 2898, 768 RFC 2925, 733 RFC 3022, 200, 218 RFC 3056, 252 RFC 3092, 355 RFC 3168, 450 RFC 3207, 796 RFC 3246, 669 RFC 3261, 202, 677 RFC 3360, 357, 451 RFC 3410, 734 RFC 3411, 736 RFC 3414, 686, 734–737, 740 RFC 3415, 712, 734, 739 RFC 3418, 720 RFC 3448, 445 RFC 3465, 404, 561 RFC 3513, 227 RFC 3519, 222 RFC 3540, 451 RFC 3550, 675, 677 RFC 3551, 675, 676 RFC 3561, 270, 272 RFC 3635, 721 RFC 3649, 454, 471–473 RFC 3715, 808 RFC 3748, 117 RFC 3756, 236 RFC 3775, 235 RFC 3826, 736 RFC 3833, 209 RFC 3879, 230 RFC 3927, 229 RFC 3947, 808 RFC 3948, 808 RFC 3971, 237 RFC 3972, 237 RFC 4001, 725 RFC 4007, 227, 250 RFC 4022, 725 RFC 4033, 209 RFC 4034, 209 851

An Introduction to Computer Networks, Release 1.9.16

RFC 4080, 672 RFC 4193, 230 RFC 4213, 252 RFC 4251, 787 RFC 4252, 787 RFC 4253, 787–789 RFC 4271, 297 RFC 4273, 703 RFC 4291, 225, 227–229 RFC 4292, 723, 724 RFC 4293, 722 RFC 4294, 234 RFC 4301, 806 RFC 4303, 233, 806 RFC 4340, 323 RFC 4341, 447 RFC 4342, 447 RFC 4344, 787 RFC 4380, 188 RFC 4429, 239 RFC 4443, 243 RFC 4451, 305 RFC 4472, 246 RFC 4502, 726 RFC 4524, 687 RFC 4560, 733 RFC 4566, 675 RFC 4620, 244 RFC 4681, 425 RFC 4861, 228, 234, 237 RFC 4862, 238, 239 RFC 4919, 98 RFC 4941, 241 RFC 4953, 357 RFC 4961, 674 RFC 4966, 255 RFC 5095, 233 RFC 5116, 390 RFC 5227, 212 RFC 5246, 790 RFC 5247, 117 RFC 5280, 687 RFC 5321, 686, 796 RFC 5348, 445 RFC 5508, 218 RFC 5694, 33 RFC 5802, 769 RFC 5925, 374 852

RFC 5944, 221 RFC 5952, 227 RFC 5961, 357 RFC 5974, 672 RFC 6040, 86 RFC 6052, 256 RFC 6057, 672 RFC 6066, 795 RFC 6093, 358 RFC 6105, 238 RFC 6106, 240 RFC 6125, 791 RFC 6146, 256 RFC 6147, 256 RFC 6151, 767 RFC 6164, 244 RFC 6182, 381 RFC 6275, 232, 233 RFC 6282, 98 RFC 6298, 488, 657 RFC 6325, 69 RFC 6356, 381 RFC 6472, 300 RFC 6553, 232 RFC 6554, 233 RFC 6564, 232, 233 RFC 6582, 411 RFC 6633, 217, 451 RFC 6724, 240, 247, 248 RFC 6742, 247 RFC 6824, 381 RFC 6887, 203 RFC 6891, 209 RFC 6918, 218 RFC 6960, 793 RFC 7045, 234 RFC 7208, 209 RFC 7217, 228, 229, 239–241 RFC 7296, 86, 807 RFC 7413, 376 RFC 7421, 225 RFC 7469, 793 RFC 7540, 365 RFC 7567, 449, 453 RFC 7568, 790 RFC 7664, 781 RFC 7686, 206 RFC 7707, 228 Index

An Introduction to Computer Networks, Release 1.9.16

RFC 7721, 241 RFC 783, 333, 340 RFC 7844, 110 RFC 7860, 735 RFC 7871, 210 RFC 791, 25, 186, 191 RFC 792, 216 RFC 793, 352, 354, 357, 358, 365, 367, 392 RFC 8110, 120 RFC 821, 686 RFC 8257, 486 RFC 8305, 248 RFC 8446, 798 RFC 854, 358 RFC 896, 377, 378 RFC 917, 195 RFC 950, 195 RFC 970, 610 RFC 988, 25 Rinjdael, 772 RIPE, 29 RMON, 726 roaming, Wi-Fi, 111 root nameserver, 205 round-robin DNS, 206 round-trip time, 151 route, 36 router, 17 Router Advertisement, IPv6, 234 Router Discovery, IPv6, 234 Router Solicitation, IPv6, 234 routerless IPv6 examples, 250 routing and addressing, 185 routing domain, 259, 287 routing header, IPv6, 232 routing loop, 19, 264 routing loop, ephemeral, 274 routing policies, BGP, 300 routing policy database, 278 routing update algorithms, 258 routing, IP, 26 routing, MANET, 124 RPC, 342 RSA, 782 RSA factoring challenge, 784 RST, 353 RSVP, 657, 662 RTCP, 676 Index

RTCP measurement of, 676 RTO, TCP, 379 RTO, TCP minimum, 487 RTP, 32, 446 RTP and VoIP, 676 RTP mixer, 674 RTS, Wi-Fi, 102 RTT, 151 RTT bias in TCP, 438 RTT inflation, 176 RTT-noLoad, 152

S SACK TCP, 413 SACK TCP in ns-2, 538 SAE, 780 Salsa20, 772 salt, password, 768 satellite Internet, 130 satellite-link TCP problem, 456 sawtooth, TCP, 400, 404, 455, 507, 534, 544 scalable routing, 185 scanning, IPv6 networks, 228 scope, IPv6 address, 227 scope, IPv6 link-local, 228 SCRAM authentication, 769 scrypt, 768 SCTP, 382 SDN, 71 search warrant, 786 secure hash functions, 765 secure neighbor discovery, 237 secure shell, 787 security, 746 security association, IPsec, 806 segment, 14 segmentation, 25 segments, TCP, 353 select group, 600 select() call, 583 Selective ACKs, TCP, 413 selective export property, 311 selector, IPsec, 806 self-ARP, 211 self-clocking, 170 SEND, 237 sequence number, TCP, 353 serial execution, RPC, 345 853

An Introduction to Computer Networks, Release 1.9.16

server, 31 ServerHello, TLS, 795 ServerName extension, TLS, 795 session key, 770 session layer, 38 sfq, 622 SHA-1, 766 SHA-2, 766 Shannon-Hartley theorem, 95 shaping, 633 shared-key ciphers, 770 shared-memory switch, 61 shellcode, 752 shortest-path bridging, 69 Shortest-Path First algorithm, 275 SHOULD, 37 shutdown, TCP, 368, 369 sibling family, BGP, 311 sibling, BGP, 309 SIFS, Wi-Fi, 101 signaling losses, 452 signatures, intrusion, 763 signatures, RSA, 783 silly window syndrome, TCP, 378 SIMO, 106 Simple Network Management Protocol, 684 SimpleHTTPServer, 578 simplex-talk, TCP, 360 simplex-talk, UDP, 323 simultaneous authentication of equals, 780 simultaneous open, TCP, 367 single link-state, 29 single-responsibility principle, 324 singlebell network topology, 429 site-local IPv6 address, 230 size, packet, 153 SLAAC, 238, 239 SLAAC privacy extensions, 240 sliding windows, 31, 170 sliding windows, TCP, 376 slot time, Wi-Fi, 101 slow convergence, 264 small-packet priority, WFQ, 617 SMI, 691 SMTP, 160, 796 SNI, TLS, 795 SNMP, 684, 724 SNMP agent configuration, 710 854

SNMP agents and managers, 685 SNMP enumerated type, 706 SNMP versions, 686 SNMPv1 data types, 690 SNMPv3 engines, 736 Snorri Sturluson, 119 SO_LINGER, TCP, 370 socket, 31 socket address, 31 soft fail, OCSP, 793 soft state, 657 software-defined networking, 71 SONET, 143 Sorcerer’s Apprentice bug, 168 Source Quench, 217, 451 source-specific multicast tree, 661 spanning-tree algorithm, 63 sparse-mode multicast, 660 spatial streams, MIMO, 106 SPB, 69 speex, 655 SPF algorithm, 275 split horizon, 265 spoofing, IP, 187 spoofing, TCP, 357 SQL injection, 762 SSH, 213 ssh, 786, 787 ssh host key, 788 SSID, Wi-Fi, 107, 111 ssl, 786 SSL programming, 799 SSRC, 675 stack canary, 757 stalk, TCP, 360 stalk, UDP, 323 star topology, 46 STARTTLS, 796 state diagram, TCP, 365 stateless autoconfiguration, 238 stateless forwarding, 17 STM-1, 144 stochastic fair queuing, 622 stop-and-wait transport, 165 stop-and-wait, TFTP, 340 store-and-forward, 21 store-and-forward delay, 149 StoredKey, 769 Index

An Introduction to Computer Networks, Release 1.9.16

stream ciphers, 773 Stream Control Transmission Protocol, 382 stream-oriented, 351 streaming video, 32, 656 streams, QUIC, 387 STS-1, 143 STS-3, 144 subnet mask, 196 subnets, 194 subnets, IPv6, 230, 244 subnets, vs switching, 199 subpoena, 786 subqueue, 609 subscription, multicast, 660 Sun RPC, 344 superfish, 792 supplicant, WPA, 117 switch, 17 switch fabrics, 63 switch, crossbar, 62 switch, shared-memory, 61 switching, vs subnets, 199 switchline.py, 575 symbol, data, 58, 139 symmetric ciphers, 770 SYN, 353 SYN flooding, 354 SYN packet, 354 synchronization source, RTP, 675 synchronized loss hypothesis, TCP, 439 synchronized loss, TCP, 402, 434, 438 synchronized states, TCP, 366

T T/TCP, 375 T1 line, 142 T3 line, 143 tables, SNMP, 691 Tahoe, 39, 399 tail drop, 425 tangle, cords, 98 tbf, Linux, 588 tc, Linux, 278, 588, 644 TCO, TCP, 359 TCP, 13, 30, 349 TCP accelerated open, 375 TCP application close, 369 TCP BBR, 493 Index

TCP checksum offloading, 359 TCP close, 355 TCP Cubic, 489 TCP fairness, 434, 441 TCP Fast Open, 376 TCP Friendliness, 444 TCP Hamilton, 488 TCP header, 352 TCP Hybla, 485 TCP Illinois, 481 TCP minimum RTO, 487 TCP NewReno, 411 TCP NewReno in ns-2, 538 TCP old duplicates, 370 TCP Reno, 399, 408 TCP sawtooth, 400, 404, 455, 507, 534, 544 TCP segmentation offloading, 359 TCP state diagram, 365 TCP Tahoe, 399 TCP timeout interval, 657 TCP Vegas, 542, 623 TCP Westwood, 479 TCP Westwood+, 480 TCP, Highspeed, 471 TCP, SACK, 413 TCP_NODELAY, 378 TCP_QUICKACK, 377 TDM, 141 Teredo tunneling, 188 terrestrial broadband, 128 terrestrial wireless, 128 TestAndIncr, 718 TEXTUAL-CONVENTION, SNMP, 715 TFTP, 333 thepiratebay, 205 thermonuclear, 38 three-way handshake, 354 three-way handshake, TCP, 372 threshold slow start, 404 throughput, 14 tier-1 provider, 310 Time to Live, 186 time-division multiplexing, 141 timeout and retransmission, 30 timeout interval, TCP, 379, 657 Timestamp, IP option, 187 TIMEWAIT, TCP, 371 TJX attack, 94, 748 855

An Introduction to Computer Networks, Release 1.9.16

tls, 786 TLS client example, 803 TLS connection setup, 794 TLS handshake protocol, 794 TLS programming, 799 TLS server example, 801 TLS version 1.3, 797 token bucket, 633 token bucket queue utilization, 640 token bus Ethernet, 88 token ring, 87 token-bucket applications, 638 token-bucket, RSVP, 663 topology, 18 topology table, EIGRP, 273 Tor project, 206 ToS and routing, 259 TP4, 38 trace file, ns-2, 508 tracefiles, ns-2, reading with python, 512 traceroute, 36, 218 tracking, Wi-Fi, 110 trading, 149 traffic amplification, QUIC, 390 traffic amplification, UDP, 322 traffic anomalies, 763 traffic engineering, 18, 278, 305, 653 traffic management, 608 tragedy of the commons, 397 Trango, 130 transient queue peak, 536 transit capacity, 171 transit traffic, 300, 305 Transmission Control Protocol, 30 transmission, Ethernet, 51 Transport layer, 30 transport mode, IPsec, 806 traps, SNMP, 686 tree, 18 triggered updates, 265 TRILL, 69 triple DES, 772 Trivial File Transport Protocol, 333 trust anchors, 237 trust and public keys, 785 trust on first use, SSH, 788 trust on first use, TLS, 792 TSO, TCP, 359 856

Tspec, 663 TTL, 186 tunnel mode, IPsec, 806 tunnel, IPv6, 252 tunneling, 85, 203 two implementations, 38 two-generals problem, 337 twos-complement, 156 Type of Service, 186

U u32, 591 UDP, 32, 321, 328, 331 UDP advisory, 322 UDP, for real-time traffic, 657 unbounded slow start, 404 unicast, 23 unique-local IPv6 address, 230 unknown destinations, Ethernet, 59 unlicensed spectrum, 99 unnumbered IP interface, 219 upgrades, network, 20 uplink scheduling, WiMAX and LTE, 126 URG, 353 User Datagram Protocol, 32 usmUserTable, 740 utilities, network, 35

V VACM, 712 VarBind list, 696 VCI, 89 video, streaming, 656 virtual circuit, 14, 26, 88 virtual hosting, 208 Virtual LANs, 68 virtual link, 85 virtual private network, 85 virtual tributary, 145 VLANs, 68 voice over IP, 26 VoIP, 26 VoIP and RTP, 676 VoIP bandwidth guarantees, 639 voting, 37 VPN, 85 VPNs and ECN, 86

Index

An Introduction to Computer Networks, Release 1.9.16

W

Z

W^X, 758 wavelength-division multiplexing, 146 web of trust, 786 web server, 578 weighted fair queuing, 610 WEP encryption failure, 748 WEP, Wi-Fi, 114 Westwood, TCP, 479 Wi-Fi, 98 Wi-Fi EasyMesh, 112 Wi-Fi extender, 112 Wi-Fi fragmentation, 104 Wi-Fi polling mode, 121 Wi-Fi repeaters, 112 Wi-Fi security, 94 Wi-Fi, HWMP mesh, 272 WiMAX, 124 window, 170 window scale option, TCP, 376 window size, 31, 170 Windows, 188 Windows XP SP1 vulnerability, 760 winsize, 170 wireless, 98 wireless LANs, 94 wireless, fixed, 128 wireless, satellite, 130 wireless, terrestrial, 128 WireShark, 248, 387, 559 wireshark, 37 WireShark, TCP example, 358 work-conserving queuing, 610 WPA authenticator, 117 WPA supplicant, 117 WPA, Wi-Fi, 114 WPA-Enterprise, 117 WPA-Personal, 114 WPA2-Enterprise, configuring, 118 WPA3, 120, 780 write-or-execute, 758

ZigBee, 98 zone identifier, IPv6, 250 zones, DNS, 204

X XD page bit, 757 xkcd, 296, 763 XML, 333 XSS, 762

Index

857