Netwerken - Samenvatting Tom Sandmann s4330048 01/07/2015
Contents 1
H1 1.1 1.2
1.3 2
H2 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8
3
H3 3.1 3.2
3.3
3.4
4
H4 4.1
4.2 4.3
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
2 2 3 3 4 4
Process . . . . . . . . . . . . Socket . . . . . . . . . . . . . TCP vs UDP . . . . . . . . . HTTP . . . . . . . . . . . . . 2.4.1 GET vs POST . . . . DNS . . . . . . . . . . . . . . 2.5.1 DNS Resource Record FTP . . . . . . . . . . . . . . SMTP . . . . . . . . . . . . . P2P . . . . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
4 4 5 5 5 7 7 8 9 9 9
UDP checksum . . . . . . . . . Go-Back-N (GBN) . . . . . . . 3.2.1 Sender . . . . . . . . . 3.2.2 Receiver . . . . . . . . Selective Repeat (SR) . . . . . . 3.3.1 Sender . . . . . . . . . 3.3.2 Receiver . . . . . . . . TCP . . . . . . . . . . . . . . . 3.4.1 3 Way Handshake . . . . 3.4.2 TCP Seq # . . . . . . . 3.4.3 TCP ACK Generation . 3.4.4 TCP Congestion Control 3.4.5 Fairness . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
9 9 10 10 11 12 12 12 13 13 14 15 15 17
IPv4 vs. IPv6 . . . . . 4.1.1 IPv4 addressing 4.1.2 IPv6 . . . . . . NAT . . . . . . . . . . Virtual Circuit (VC) . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
18 18 18 19 20 20
Packet switching . . . Circuit switching . . . 1.2.1 FDM . . . . . 1.2.2 TDM . . . . . Internet Protocol Stack
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
1
4.4 4.5 4.6 4.7 4.8 4.9
5
6
7
Datgram Network . . . . . . . . . . . . . . Switching . . . . . . . . . . . . . . . . . . DHCP . . . . . . . . . . . . . . . . . . . . Link-State (LS) . . . . . . . . . . . . . . . Distance Vector (DV) . . . . . . . . . . . . Intra-AS Routing . . . . . . . . . . . . . . 4.9.1 Routing Information Protocol (RIP) 4.9.2 OSPF . . . . . . . . . . . . . . . . 4.10 Broadcast Routing . . . . . . . . . . . . . 4.10.1 Reverse Path Broadcast . . . . . . . 4.10.2 Spanning-Tree Broadcast . . . . . . 4.11 Inter-AS Routing: BGP . . . . . . . . . . . 4.12 Multicast . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
21 21 23 23 25 27 27 27 28 28 28 29 29
H5 5.1 5.2 5.3 5.4 5.5 5.6 5.7 H6 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 6.10 6.11 H8 7.1
1
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
30 30 30 31 33 33 33 33
CDMA . . . . . . . . . . . . . . . . . 802.11 MAC Protocol . . . . . . . . . . Hidden Terminal Problem . . . . . . . . 802.11 Architecture . . . . . . . . . . . IEEE 802.11 Frame . . . . . . . . . . . Mobility . . . . . . . . . . . . . . . . . Bluetooth . . . . . . . . . . . . . . . . Cellular Network Architecture . . . . . Mobility Management . . . . . . . . . Agent Discovery . . . . . . . . . . . . Managing mobility in Cellular Networks 6.11.1 Routing Calls to a Mobile user .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
34 34 36 37 38 39 41 41 41 43 44 45 45
IPsec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47 47
Parity Check . . . . . . . CRC . . . . . . . . . . . Multiple Acces Protocols Switched LAN . . . . . ARP . . . . . . . . . . . Link-Layer Switches . . VLAN . . . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
1.1
H1 Packet switching
Packet switching: hiermee wordt geduid op het doorsturen van packets. store-and-forward: er wordt eerst gewacht tot alle data van het packet in de buffer zit. Wanneer vervolgens alle bits zijn ontvangen, wordt het pakketje geforward naar de juiste bestemming.
2
24
CHAPTER 1
•
COMPUTER NETWORKS AND THE INTERNET
321
Source
Figure 1.11
R bps
Front of packet 1 stored in router, awaiting remaining bits before forwarding
Destination
Store-and-forward Figure 1: Store andpacket forwardswitching
Het versturen van een packet kost tijd. Het versturen tussen twee links met een rate R (bits/sec) en een packet must first buffer (i.e., “store”) the packet’s bits. Only after the router has received van grootte L bits duurt dan L=R seconden. Dit wordt transmission delay genoemd. all of the packet’s bits can it begin to transmit (i.e., “forward”) the packet onto the outbound Delay: dnodal D dproc C dqueue C link. dtrans To C dgain prop . some insight into store-and-forward transmission, let’s now calculate the amount of time that elapses from when the source begins to send the 36 CHAPTER 1 • COMPUTER NETWORKS AND THE INTERNET packet until the destination has received the entire packet. (Here we will ignore propagation delay—the time it takes for the bits to travel across the wire at near the speed of light—which will be discussed in Section 1.4.) The source begins to transmit at time 0; at time L/R seconds, the source has transmitted the entire packet, and the entire packet has been received and stored at the router (since there is no propaA gation delay). At time L/R seconds, since the router has just received the entire B packet, it can begin to transmit the packet onto the outbound link towards the destination; at time 2L/R, the router has transmitted the entire packet, and the entire packet has been received by the destination. Thus, the total delay is 2L/R. If the switch instead forwarded bits as soon as they Propagation arrive (without first receiving the Transmission Nodal Queueing entire packet), then the total delay would be L/R since bits are not held up at processing for1.4, routers need to receive, store, and the router. But, as we will discuss (waiting in Section transmission) process the entire packet before forwarding. We hebben de volgende soorten delay: Now let’s calculate thenodal amount of time that elapses from when the source Figure 1.16 The delay at router A begins to send the first packet until the destination has received all three packets. – Queuing delay dqueue : als de transmission rate overschreden wordt, worden de packets in een queue As before, at time L/R, the router begins to forward the first packet. But also at time geplaatst, wachtend om verstuurd te worden L/R the source will begin to send the second packet, since it has just finished send– Propagation delay: hetentire daadwerkelijk versturen materiaal. Hierbij wordt rekening gehouden met de ing the first packet. Thus, over attypes time 2L/R, the destination received the first packet suffers from several of delays at each nodehas along the path. The most fysieke eigenschappen van het materiaal packetimportant and the router has received thenodal second packet. Similarly, at timedelay, 3L/R,transmisthe of these delays are the processing delay, queuing destination has received the first two packets and the router has received the third – Nodal processing dproc : het daadwerkelijk versturen over de link (rekening houden met fysieke sion delay, and propagation delay; together, these delays accumulate to give eigena total Finally, at time the destination hasInternet received all three packets! as search, Web schappen van hetpacket. materiaal). nodal delay. The4L/R performance of many applications—such Let’s now consider the general case of sending one packet from sourcegreatly to destiemail, maps, messaging, affected – Transmission delay dbrowsing, van deinstant verbinding die voorand de voice-over-IP—are vertraging tussen het verzenden en trans : de snelheid nationby over a path consisting of N links each of rate R (thus, there are N-1 routers and network delays. In order to acquire a deep understanding of packet switching ontvangen zorgt. between source networks, and destination). thethe same logic as importance above, we see that the computer we mustApplying understand nature and of these delays. delay waarmee is: Throughput: aantal end-to-end bits/tijdseenheid bits tussen verzender en ontvanger worden verstuurd. Dit is gelijk aan de meest beperkende link (kleinste R). Wordt ook wel de bottleneck genoemd. L Types of Delay dend@to@end = N (1.1) R Let’s explore these delays in the context of Figure 1.16. As part of its end-to-end 1.2 Circuit switching You may now want tosource try to determine what the delay would for Pthe packets sent node route between and destination, a packet is sentbefrom upstream Naast packet switching hebover je circuit switching. Hierbij wordt bandbreedte gereserveerd voordat er verstuurd kan athrough series ofrouter N links. A to router B. Our goal is to characterize the nodal delay at router A. worden over de verbinding. Je kanNote nooitthat meer versturen dan de gereserveerde bandbreedte. Er zijn twee methodes: router A has an outbound link leading to router B. This link is preceded by a queue (also known as a buffer). When the packet arrives at router A from the 1.2.1 FDM upstream node, router A examines the packet’s header to determine the appropriate outbound link for the packet and then directs the packet to this link. In this example, Met FDM, ofwel frequency-division multiplexing, wordt het frequency spectrum verdeeld over de connecties. Een the outbound link for the packet is the one that leads to router B. A packet can be connectie mag over de toegewezen frequency met een toegewezen bandbreedte op elk moment versturen. transmitted on a link only if there is no other packet currently being transmitted on the link and if there are no other packets preceding it in the queue; if the link is currently busy or if there are other packets already queued for the link, the newly arriving packet will then join the queue. 3
Processing Delay The time required to examine the packet’s header and determine where to direct the
tion across a link, the network dedicates one time slot in every frame to this connection. These slots are dedicated for the sole use of that connection, with one time slot available for use (in every frame) to transmit the connection’s data. Figure 1.14 illustrates FDM and TDM for a specific network link supporting up to four circuits. For FDM, the frequency domain is segmented into four bands, each of bandwidth 4 kHz. For TDM, the time domain is segmented into frames, with four time slots in each frame; each circuit is assigned the same dedicated slot in the revolving TDM frames. For TDM, the transmission rate of a circuit is equal to the frame rate multiplied by the number of bits in a slot. For example, if the link transmits 8,000 frames per second and each slot consists of 8 bits, then the transmission 1.2.2 TDM rate of a circuit is 64 kbps. Proponents of packet always argued that circuit is Met TDM, ofwel time-devision multiplexing, wordtswitching de tijdhave opgedeeld in slots. Elkeswitching connectie mag alleen iets versturen wasteful because the dedicated circuits are idle during silent periods. For example,
met de volle bandbreedte als zijn slot aan de beurt is. FDM 4KHz
Link
Frequency
4KHz
TDM 1 2
Slot
3
4 1 2
3
4
1 2
3
4 1 2
3
4
Frame Time
Key: 2
All slots labeled “2” are dedicated to a specific sender-receiver pair.
Figure 1.14 With FDM, each circuit continuously gets a fraction of the
CHAPTER 1 • COMPUTER NETWORKS AND THEgets INTERNET bandwidth. TDM,van each de circuit all of the bandwidth Figure 2: 50 Met FDM krijgt elke circuit telkens een With fractie bandbreedte. Met TDM krijgt elke circuit alle periodically during brief intervals of time (that is, during slots) bandbreedte gedurende een toegewezen periode.
1.3
Internet Protocol Stack
Application
De internet protocol stack ziet er als volgt uit:
Presentation Application
Session
Transport
Transport
Network
Network
Link
Link
Physical
Physical
a. Five-layer
b. Seven-layer
Application Layer: bevat de netwerk applicaties Internet en de volgende protocollen:ISO HTTP, OSI SMTP en FTP. protocol stack
reference model
Transport Layer: vervoert application layer messages tussen application endpoints. Er zijn twee transport protocols: TCP en UDP. Een transport-layer wordt ook wel een segment genoemd. Figure 1.23 packet The Internet protocol stack (a) and OSI reference model (b) Network Layer: Network layer is verantwoordelijk voor het versturen van datagrams van een host naar een andere. always implemented in software in the end systems; so are transport-layer protocols. Because the physical layer and data link layers are responsible for handling commu Link Layer: Biedt bepaalde zekerheden: reliable delivery. Protocollen zijn Ethernet en WiFi. nication over a specific link, they are typically implemented in a network interface (for example, or WiFi Physical Layer: Richt zichcard op het versturen vanEthernet individuele bits. interface cards) associated with a given link. The network layer is often a mixed implementation of hardware and software. Also Er vindt continu encapsulation plaats. note that just as the functions in the layered airline architecture were distributed among the various airports and flight control centers that make up the system, so too is a layer n protocol distributed among the end systems, packet switches, and other 2 H2 components that make up the network. That is, there’s often a piece of a layer n protocol in each of these network components. 2.1 Process Protocol layering has conceptual and structural advantages [RFC 3439]. As we have seen, layeringbinnen provides structured discuss system components. ModEen process is een programma dat wordt uitgevoerd eenahost. Er zijnway tweetosoorten: ularity makes it easier to update system components. We mention, however, that client process: deze start desome verbinding. researchers and networking engineers are vehemently opposed to layering [Wakeman 1992]. One potential drawback of layering is that one layer may dupli server process: deze wachtcate op de verbinding functionality. For example, many protocol stacks provide error lower-layer recovery on both a per-link basis and an end-to-end basis. A second potential drawback is that functionality at one layer may need information (for example, a timestamp value) that is present only in another layer; this violates the goal of 4 separation of layers. When taken together, the protocols of the various layers are called the protocol stack. The Internet protocol stack consists of five layers: the physical, link, network,
2.2
Socket
Sockets worden gebruikt om data te versturen en te ontvangen. Is een software interface.
2.3
TCP vs UDP
TCP service reliable transport tussen sending en receiving process flow control: sender kan de receiver niet overspoelen met data congestion control: geef aan verzender aan wanneer netwerk overbelast is biedt geen: timing, security, throughput guarantee, security connection-oriented: er is een setup nodig tussen client en server process
2.4
UDP service unreliable data transfer tussen sending en receiving process biedt geen: reliability, flow, control, congestion control, timing, throughput guarantee, security, connection setup
HTTP
Er zijn twee verschillende soorten connecties voor HTTP: persistent HTTP: meerdere objecten kunnen over e´ e´ n TCP verbinding worden verstuurd. TCP verbinding blijft dus bestaan. non-persistent HTTP: maximaal e´ e´ n object versturen over een verbinding, daarna wordt verbinding gesloten. Bij meerdere objecten worden meerdere verbindingen aangemaakt. HTTP maakt gebruik van een TCP verbinding. De round-trip time (RTT) is de tijd voor een packet om van de client naar de server, en weer terug te gaan (tijd tussen request en response). De HTTP response time: starten van TCP verbinding versturen van request (GET) (client) versturen van bestand (server) Dus dit is 2 keer de RTT (´ee´ n voor TCP request en e´ e´ n voor Request) samen met de tijd die het duurt om het bestand te versturen. Zie plaatje hieronder:
5
to initiate a TCP connection between the browser and the Web server; this involves a “three-way handshake”—the client sends a small TCP segment to the server, the server acknowledges and responds with a small TCP segment, and, finally, the client acknowledges back to the server. The first two parts of the threeway handshake take one RTT. After completing the first two parts of the handshake, the client sends the HTTP request message combined with the third part of
Initiate TCP connection
RTT
Request file
RTT Time to transmit file
Entire file received
Time at client
Time at server
Indien er geen gebruik wordt2.7 gemaakt van een persistent HTTP verbinding, moet dus telkensto de TCP verbinding Figure Back-of-the-envelope calculation for the time needed worden opgezet bij het versturen van een volgende request (als dit er meerdere zijn). Daarnaast wordt de verbinding request and receive an HTML file ook afgesloten na het ontvangen van de response (dit geeft geen extra RRT, deze informatie bevindt zich in de header van de response). Dit is e´ e´ n RTT extra voor elke request. Zie plaatjes hieronder:
6
Non-persistent HTTP suppose user enters URL: www.someSchool.edu/someDepartment/home.index 1a. HTTP client initiates TCP connection to HTTP server (process) at www.someSchool.edu on port 80! 2. HTTP client sends HTTP request message (containing URL) into TCP connection socket. Message indicates 134 CHAPTER 2 • APPLICATION LAYER that client wants object time someDepartment/ Non-persistent HTTP (cont.) home.index!
(contains text, references to 10 jpeg images)
1b. HTTP server at host www.someSchool.edu waiting for TCP connection at port 80. “accepts” connection, notifying client! 3. HTTP server receives request message, forms response message containing requested object, and sends message into its socket!
• Distant centralized database. A single DNS server cannot be “close to” all the querying clients. If we put the single DNS server in New York City, then all queries from Australia must travelserver to the other side of the globe, perhaps over 2-7 Application Layer 4. HTTP closes TCP slow and congested links. This can lead to significant delays. connection. • Maintenance. The single DNS server would have to keep records for all Internet 5. HTTP client receives hosts. Not only would this centralized database be huge, but it would have to be response message updated frequently to account for every new host.
containing html file, displays html. Parsing html file,Infinds summary, a centralized database in a single DNS server simply doesn’t scale. the DNS is distributed by design. In fact, the DNS is a wonderful 10 referenced jpegConsequently, objects example of how a distributed database can be implemented in the Internet.
time
6. Steps 1-5 repeated for each of 10 jpeg objects A Distributed, Hierarchical Database
In order to deal with the issue of scale, the DNS uses a large number of servers, organized in a hierarchical fashion and distributed around the world. No single DNS server has all of the mappings for all of the hosts in the Internet. Instead, the mappings are distributed across the DNS servers. To a first approximation, there are 2.4.1 GET vs POST three classes of DNS servers—root DNS servers, top-level domain (TLD) DNS servers, and in a hierarchy as shown in FigVoor het invullen van een formulier op authoritative het internetDNS het servers—organized je twee soorten methodes: ure 2.19. To understand how these three classes of servers interact, suppose a DNS 2-8 Application Layer client wants determine wordt the IP address for the To POST method: de input van het toformulier verstuurd inhostname de bodywww.amazon.com. van de HTTP request. a first approximation, the following events will take place. The client first contacts of the root servers, which returns IP addresses for TLD servers for the top-level GET method: de inputone wordt verstuurd in de link (bijvoorbeeld www.somesite.com/animalsearch?monkeys&banana) domain com. The client then contacts one of these TLD servers, which returns the IP address of an authoritative server for amazon.com. Finally, the client contacts one of the authoritative servers for amazon.com, which returns the IP address
2.5
DNS
DNS wordt gebruikt om van een bepaalde hostname het IP adres te vinden. DNS heeft een hi¨erarchische structuur: Root DNS servers
com DNS servers
yahoo.com DNS servers
amazon.com DNS servers
org DNS servers
pbs.org DNS servers
edu DNS servers
poly.edu DNS servers
umass.edu DNS servers
We hebben de volgende klassen van rootservers:
Figure 2.19 Portion of the hierarchy of DNS servers
Root DNS servers: Er zijn 13 root DNS servers (A t/m M). Top-level domain (TLD) servers: Deze servers zijn verantwoordelijk voor top-level domains, zoals com, org, net en alle country top-level domains (uk, fr, nl, etc.).
7
Authoritative DNS servers: Elke organisatie die publiek toegankelijke hosts heeft (zoals web servers en mail server), moet ook publiek toegankelijke DNS records2.5 hebben die de namen van deze DIRECTORY hosts mappen naar IP • DNS—THE INTERNET’S SERVICE adressen. De authoritative DNS server van deze organisatie bevat deze DNS records. Hieronder staat een voorbeeld van een DNS query: Root DNS server
2 3 4 5 Local DNS server dns.poly.edu
TLD DNS server
7
1
6
8
Authoritative DNS server dns.umass.edu Requesting host cis.poly.edu gaia.cs.umass.edu
In het bovenstaande plaatje worden verschillende soorten DNS query’s gebruikt: Figure 2.21 Interaction of the various DNS servers – recursieve query: query 1 is een recursieve query. Een recursieve query legt de last van het oplossen van de query op de gevraagde DNS server. Zoals te zien is vraagt de local DNS server in het bovenstaande plaatje iteratief aan verschillende servers als die het antwoord weten. Omdat deze queries iteratief zijn Massachusetts has a DNS server for the university, called dns.umass.edu. Also krijgt de local DNS server een antwoord dat een IP adres bevat aan wie hij het opnieuw moet gaan vragen. suppose that each of the departments at the University of Massachusetts has its own Dit gaat net zo lang door tot iemand uiteindelijk het antwoord geeft (7). DNS server, and that each departmental DNS server is authoritative for all hosts in – niet recursieve query: er een nietthe recursieve query wordt verstuurd, krijg je of het antwoord terug the department. In indien this case, when intermediate DNS server, dns.umass.edu, (indien de host de authoritative nameserver is voor de host) of je krijgt een ip adres terug. Aan dit ip adres receives a query for a host with a hostname ending with cs.umass.edu, it returns kan jetojedns.poly.edu query versturen omthe je IP zoektocht naar het antwoord te vervolgen (ik weet het antwoord niet, maar address of dns.cs.umass.edu, which is authoritavraagtive het maar aan deze server). for all hostnames ending with cs.umass.edu. The local DNS server dns.poly.edu then sends the query to the authoritative DNS server, which Wanneer een DNS query wordt opgelost, wordt de combinatie hostname-IP adres opgeslagen in een cache. returns the desired mapping to the local DNS server, which in turn returns the mapHierdoor hoeft de volgend keer niet opnieuw gezocht te worden naar het IP address van deze hostname. Deze ping to the requesting host. In this case, a total of 10 DNS messages are sent! entries zijn beperkt houdbaar. De TTL (Time To Live) geeft aan wanneer ze niet meer geldig zijn, en het ip The example shown in Figure 2.21 makes use of both recursive queries and adres van de hostname dus weer opnieuw moet worden opgezocht. Root servers zijn altijd cached, waardoor ze iterative queries. The query sent from cis.poly.edu to dns.poly.edu is a ontlast worden. recursive query, since the query asks dns.poly.edu to obtain the mapping on its 2.5.1
DNS Resource Record
Een antwoord van een DNS query heeft de structuur van een resource record (RR). Dit is een viertupel (name, value, type, ttl): – type = A
8
137
name is de hostname value is het IP address – type = NS name is domein (b.v. foo.com ) value is hostname of authoritative name server van dit domein – type = CNAME name is een alias voor een “canonical” (echte) naam. www.ibm.com is eigenlijk servereast.backup2.ibm.com. value is dus een canocial name. – type = MX value is naam van de mailserver die geassocieerd wordt met name Bij MX is er sprake van prioriteitsgetal: het laagste nummer wordt als eerst gekozen. Indien dit niet online, dan het volgende laagste nummer, enz.
2.6
FTP
FTP staat voor file transfer protocol. Een user zit op een host en wil data sturen van of naar een andere host. FTP gebruikt hiervoor twee verschillende TCP verbindingen: een control connection en een data connection. De control connection wordt gebruikt om controle informatie zoals user identificatie, password en commands over te versturen. De data connectie wordt gebruikt om een bestand te versturen. Het sturen van controle data over een aparte verbinding wordt ook wel out-of-band genoemd. HTTP daarentegen stuurt zijn controle data in-band: het heeft geen apart control connection.
2.7
SMTP
Dit protocol kan gebruikt worden berichten te versturen tussen een verzender en een ontvanger. Zie het boek blz. 124.
2.8
P2P
Hierbij wordt de data opgedeeld in chunks. Het meest zeldzame chunk van de buren wordt als eerst verstuurd. Er wordt voordeel gegeven aan de neighbors die met de hoogste rate data naar jou versturen. Deze peers worden ook wel unchoked genoemd. In totaal worden zo 4 peers berekend. Elke 30 seconden wordt er ook random een buur gekozen. Dit wordt ook wel optimistically unchocked genoemd. Iedere peer houdt zijn voorganger en opvolger bij. Dit kan effici¨enter door circular DHT te gebruiken. Hierbij wordt eerste bepaald wie van de buren het dichtst bij de key zit en aan deze buur wordt dan de vraag doorgegeven.
3
H3
3.1
UDP checksum
De UDP checksum wordt gebruikt om fouten te vinden nadat de transmissie heeft plaatsgevonden. De verzender kiest enkele 16-bit integers, en berekent de checksum als volgt: 1. Tel alle integers bij elkaar. Indien er een carry overblijft tel je die er weer bij op (dit wordt wraparound genoemd). 2. Neem de 1’s complement van het het bovenstaande resultaat (alle 1 worden een 0 en vice versa). Als de ontvanger het pakketje ontvangt, berekent hij de som van alle integers die werden meegestuurd. Vervolgens telt hij de checksum (die aanwezig was in het pakketje) op bij de som van alle integers. Indien er geen errors waren gedurende het versturen, telt dit op tot 1111111111111111. Als e´ e´ n van de bits echter 0 is, dan weten we dat er errors in het pakketje zitten. Een voorbeeld: 9
• GCA%AC3")
&C4X.A.:ACC?3"5.YC3-.5S&. -345.4(*)(=:A)5.>(5.)&&<4.53.>&.A<<&<.53.5S&.C&4"#5. • 1'A-%#&. 1 1
1 1
1 1
1 0
0 1
0 0
1 1
1 0
0 1
0 0
1 1
1 0
0 1
0 0
1 1
1 0
0 1
1 1
0
1
1
1
0
1
1
1
0
1
1
1
0
1
1
wraparound 1
sum checksum
1 1
1 0
0 1
1 0
1 0
1 0
0 1
1 0
1 0
1 0
0 1
1 0
1 0
1 0
1 0
0 1
0 1 flip bits (1s complement)
3.2
Go-Back-N (GBN)
3-25
Transport Layer
In GBN mag de sender meerdere packets gelijkertijd versturen (indien deze beschikbaar zijn). Dit aantal mag niet 220 CHAPTER 3 • waarde TRANSPORT meer zijn dan een bepaalde maximum N vanLAYER unacknowledged packets in de pipeline. Omdat elke packet een uniek nummer heeft, werken we met sequence numbers. In het figuur hieronder staat de range van sequence numbers voor de sender. base
nextseqnum
Window size N
Key: Already ACK’d
Usable, not yet sent
Sent, not yet ACK’d
Not usable
Figure 3.19 Sender’s view of sequence numbers in Go-Back-N Figure 3: Sender’s view van de sequence numbers De base is het sequence number van het oudste pakketje waarvoor er nog geen ACK is ontvangen. De nextseqnum used for packets that packet can be dat sentverzonden immediately, arrive dit from the upper is het kleinste ongebruikte sequencebenumber (het volgende gaatshould wordendata gebruikt sequence layer. Finally, sequence numbers greater than or equal to base+N cannot be used until number). Daarnaast hebben we vier intervallen an unacknowledged packet currently in the pipeline (specifically, the packet with sequencenumbers numbervan base) has been acknowledged. [0, base-1]: dit zijn alle sequence packets waarvoor we al een ACK hebben ontvangen. As suggested by Figure 3.19, the range of permissible sequence numbers for base, nextseqnum-1]: dit zijn alle sequence van packetspackets waarvoor geenasACK hebben transmitted but notnumbers yet acknowledged canwe be nog viewed a window ofontsize N vangen. over the range of sequence numbers. As the protocol operates, this window slides forward over the sequence number space. For this reason, N is often referred to as [nextseqnum, base+N-1]: dit zijn alle sequence numbers die gebruikt kunnen worden voor packets die direct the window size and the GBN protocol itself as a sliding-window protocol. You verstuurd kunnen worden. might be wondering why we would even limit the number of outstanding, unacpackets a valuegebruikt of N in tot theeen firstpacket place. met Whyeen notsequence allow annumber unlimited [> base+N]: deze sequence knowledged numbers kunnen niettoworden number of such packets? We’ll see in Section 3.5 that flow control is one reason to base wordt ACK’d. impose a limit on the sender. We’ll examine another reason to do so in Section 3.7, N wordt de window size genoemd, enwe hetstudy GBNTCP protocol zelf eencontrol. sliding-window protocol. when congestion In practice, a packet’s sequence number is carried in a fixed-length field in the packet header. If k is the number of bits in the packet sequence number field, the range 3.2.1 Sender of sequence numbers is thus [0,2k – 1]. With a finite range of sequence numbers, all De sender kent drie events: arithmetic involving sequence numbers must then be done using modulo 2k arithmetic. (That is, the sequence number canvol beis. thought of asina dat ringerofNsize 2k, where Indien we iets willen gaan versturen, kijken wek eerst of de space window Dit houdt unACK’d sequence – wordt 1 is immediately followed en bywordt sequence number 0.) Recall that packets zijn verstuurd. Indien de windownumber niet vol2is, het packet verstuurd nextseqnum verhoogd. rdt3.0 had a 1-bit sequence number and a range of sequence numbers of [0,1].en SevWe controleren ook als base gelijk is aan nextseqnum. Dit houdt in dat we alle packets hebben ontvangen eral of the problems at the end of this chapter explore the consequences of a finite range dat er dus geen timer meer loopt. In dit geval starten we dus een timer. Als de window vol is sturen we het of sequence numbers. We will see in Section 3.5 that TCP has a 32-bit sequence number pakketje niet. field, where TCP sequence numbers count bytes in the byte stream rather than packets. Figures 3.20 and n3.21 giveweanaan extended FSMcumulative description of the sender and Als we een ACK ontvangen met sequence number nemen dat dit een acknowledgement receiver sides ofnumber an ACK-based, GBN protocol. is. Dit houdt in dat alle packets met sequence tot en metNAK-free, n correct ontvangen zijn. We refer to this FSM description as an extended FSM because we have added variables (similar to programming-language variables) for base and nextseqnum, and added operations on these variables and 10conditional actions involving these variables. Note that the extended FSM specification is now beginning to look somewhat like a programminglanguage specification. [Bochman 1984] provides an excellent survey of additional extensions to FSM techniques as well as other programming-language-based tech-
3.4die•al verstuurd PRINCIPLES OFmaar RELIABLE DATAwe TRANSFER 221 Indien er een timeout optreedt, sturen we alle packets zijn, waarvoor nog geen ACK hebben ontvangen, opnieuw. We gebruiken slechts e´ e´ n timer, die altijd gelijk is aan het oudste packet dat verstuurd is. 3.4
PRINCIPLES OF RELIABLE DATA TRANSFER
•
rdt_send(data) if(nextseqnum
3.2.2
Receiver
Figure 3.20
Extended FSM description of GBN sender
De receiver is vrij eenvoudig. Indien de receiver een packet met sequence number n ontvangt, en het is in volgorde (dat houdt in dat laatst correct ontvangen packet een sequence number van n 1 had) accepteert de receiver het packet rdt_rcv(rcvpkt) en stuurt de receiver een ACK voor sequence number n. In elk ander geval stuurt de receiver een ACK voor het laatst && notcorrupt(rcvpkt) && hasseqnum(rcvpkt,expectedseqnum) correct ontvangen packet. rdt_rcv(rcvpkt) extract(rcvpkt,data) && notcorrupt(rcvpkt) deliver_data(data) && hasseqnum(rcvpkt,expectedseqnum) sndpkt=make_pkt(expectedseqnum,ACK,checksum) udt_send(sndpkt) extract(rcvpkt,data) expectedseqnum++ deliver_data(data) sndpkt=make_pkt(expectedseqnum,ACK,checksum) udt_send(sndpkt) expectedseqnum++ default
Wait
udt_send(sndpkt)
Λ expectedseqnum=1 sndpkt=make_pkt(0,ACK,checksum)
Figure 3.21
Wait
default udt_send(sndpkt)
Λ
Extended FSM description of GBN receiver expectedseqnum=1 sndpkt=make_pkt(0,ACK,checksum)
Figure 3.21
Extended FSM description of GBN receiver Figure 5: GBN automaat voor de receiver
Wat is de maximale window size voor de sender? De maximale window size voor de sender is gelijk aan het grootst mogelijke sequence number. binair: Stel we hebben een n bit sequence number, dan is het grootst mogelijke sequence number 2n 11
1. Dus
221
de maximale sending window size voor de sender wordt dan 2n 1. Een voorbeeld hiervan: stel we hebben een 3-bit window. Dan wordt MAX_SEQ = 23 1 = 7, dus de maximale window size is 7. decimaal: Stel we hebben een sequence number space van k. Dan wordt de maximale sending window k
3.3
1.
Selective Repeat (SR) 3.4
•
PRINCIPLES OF RELIABLE DATA TRANSFER
225
SR voorkomt onnodig retransmissions van packets. We moeten dus voor packets individueel ACKs gaan sturen. N staat opnieuw voor de maximale window size. De sender en receiver window zien er als volgt uit: send_base
nextseqnum
Window size N
Key: Already ACK’d
Usable, not yet sent
Sent, not yet ACK’d
Not usable
a. Sender view of sequence numbers
rcv_base
Key:
Window size N
Out of order (buffered) but already ACK’d
Acceptable (within window)
Expected, not yet received
Not usable
b. Receiver view of sequence numbers
3.3.1
Sender
Figure 3.23 Selective-repeat (SR) sender and receiver views of sequence-number space
of outstanding, unacknowledged packets in the pipeline. However, unlike GBN, the Voor de sender zijn er weer drie events:
3.3.2
sender will have already received ACKs for some of the packets in the window. Figure 3.23 shows the SR sender’s view of the sequence number space. Figure 3.24 Indien we data willen versturen, kijken webynaar volgende beschikbare sequence number. Indien dit binnen details the various actions taken the SRhet sender. Thedata SR receiver will acknowledge a correctly received packet whether or not it de window valt wordt de verstuurd. is in order. Out-of-order packets are buffered until any missing packets (that is, lower sequence numbers) are received, at which point a batch of packVoor elke packet is packets er eenwith timeout. Indien er een packet timeout wordt alleen dat packet opnieuw verstuurd. ets can be delivered in order to the upper layer. Figure 3.25 itemizes the various actions taken by the SR receiver. Figure 3.26 shows an example of SR operation in Als een ACK wordtthe ontvangen, wordt onthouden dat het packet is ontvangen. presence of lost packets. Note that in Figure 3.26, the receiver initially buffersAls de packet’s sequence number packets 3, 4, and 5,het andwindow delivers them together with packet 2 to tot the upper layer het whenpacket met het kleinste sequence gelijk is aan send_base wordt vooruit geschoven en met packet 2 is finally received. number dat nog niet ACK’d is. Als erthat packets die3.25, nogtheniet verzonden zijn en de sequence numbers vallen It is important to note in Step 2zijn in Figure receiver reacknowledges (rather thandeze ignores) already received packets with certain sequence numbers below in de window, dan worden packets verstuurd. the current window base. You should convince yourself that this reacknowledgment is indeed needed. Given the sender and receiver sequence number spaces in Figure 3.23, for example, if there is no ACK for packet send_base propagating from the Receiver receiver to the sender, the sender will eventually retransmit packet send_base, even though it is clear (to us, not the sender!) that the receiver has already received
Voor de receiver zijn er ook weer drie events:
Als een packet met een sequence number dat ligt in rcv_base, rcv_base+N-1 correct is ontvangen, dan ligt het packet in de receiver window en wordt een ACK verstuurd en het packet buffered (indien dit nog niet was gebeurd). Als het sequence number gelijk is aan rcv_base, dan wordt dit packet en alle achtereenvolgende packets (die eerder niet buffered waren) afgeleverd. Dus, neem het figuur hieronder, als een packet met sequence number van rcv_base = 2 wordt ontvangen, dan wordt dit packet samen met packets 3,4 en 5 afgeleverd. Als een packet met sequence number dat ligt in rcv_base-N, rcv_base-1 correct wordt ontvangen, dan wordt een ACK teruggestuurd, ook al is er al eerder een ACK voor dit sequence number verstuurd. In alle andere gevallen wordt het packet genegeerd.
12
3.4
•
PRINCIPLES OF RELIABLE DATA TRANSFER
Sender
227
Receiver
pkt0 sent 0 1 2 3 4 5 6 7 8 9 pkt0 rcvd, delivered, ACK0 sent
pkt1 sent 0 1 2 3 4 5 6 7 8 9 pkt2 sent 0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
X
pkt1 rcvd, delivered, ACK1 sent 0 1 2 3 4 5 6 7 8 9
(loss) pkt3 sent, window full 0 1 2 3 4 5 6 7 8 9 pkt3 rcvd, buffered, ACK3 sent 0 1 2 3 4 5 6 7 8 9
ACK0 rcvd, pkt4 sent 0 1 2 3 4 5 6 7 8 9
pkt4 rcvd, buffered, ACK4 sent 0 1 2 3 4 5 6 7 8 9
ACK1 rcvd, pkt5 sent 0 1 2 3 4 5 6 7 8 9
pkt5 rcvd; buffered, ACK5 sent 0 1 2 3 4 5 6 7 8 9
pkt2 TIMEOUT, pkt2 resent 0 1 2 3 4 5 6 7 8 9
pkt2 rcvd, pkt2,pkt3,pkt4,pkt5 delivered, ACK2 sent 0 1 2 3 4 5 6 7 8 9 ACK3 rcvd, nothing sent 0 1 2 3 4 5 6 7 8 9
Figure 3.26 SR operation
Figure 6: SR operation
Wat is de maximaleThe sending window size?between max_window_size (MAX_SEQ + 1) /2. Hier is MAX_SEQ de lack of synchronization sender and receiver=windows has imporgrootst mogelijke waarde voor een sequence number. tant consequences when we are faced with the reality of a finite range of sequence numbers. Consider what could happen, for example, with a finite range of four packet 0, 1,window, 2, 3, and adan window size of three.=Suppose 0 through binair: stel wesequence hebbennumbers, een 2-bit is MAX_SEQ 3, duspackets max_window_size = (3+1)/2 = 2. 2 are transmitted and correctly received and acknowledged at the receiver. At this
the receiver’s window is number over the fourth, sixthis packets, which=have decimaal: stelpoint, we hebben een sequence spacefifth, vanand k, dan MAX_SEQ k-1 en dus max_window_size sequence numbers 3, 0, and 1, respectively. Now consider two scenarios. In the first = ((k-1)+1)/2 = k/2. scenario, shown in Figure 3.27(a), the ACKs for the first three packets are lost and
3.4
TCP
zie boek blz. 236 (pdf) 3.4.1
3 Way Handshake
De 3 way handshake wordt gebruikt om een TCP verbinding op te zetten tussen twee hosts. Het gaat als volgt: 1. Client stuurt een TCP SYN naar de server. Het geeft het initiele Seq # aan. 2. Server ontvangt SYN, antwoord met SYN-ACK. Het geeft hierbij het initiele Seq # aan. 3. Client ontvangt SYN-ACK en antwoord met ACK.
13
CP Seq #’s and ACKs 3.4.2
TCP Seq #
Host B
Host A
K'C(DE9( User types C
P3Q9(
!0%%R5)*A'8( – P3Q( – 3)""0'9(8)2)(
host ACKs receipt of echoed C
Seq=42, ACK=79, data = C
host ACKs receipt of C, echoes Seq=79, ACK=43, data = C back C
Seq=43, ACK=80
Simple Telnet Scenario
TCP: Cumulative ACK
Stel dat er twee ACKs worden verstuurd, maar alleen de laatste komt aan. Omdat TCP werkt met cumulative ACKs weet de sender datTransport het voorgaande 3-23 Layer packet ook aangekomen moet zijn. Een voorbeeld:
Host B
Host A
SendBase=92 Seq=92, 8 bytes of data
timeout
Seq=100, 20 bytes of data ACK=100
X ACK=120
SendBase=120 Seq=120, 15 bytes of data
Transport Layer
14
3-38
acknowledgment. To understand the sender’s response to a duplicate ACK, we must look at why the receiver sends a duplicate ACK in the first place. Table 3.2 summarizes the TCP receiver’s ACK generation policy [RFC 5681]. When a TCP receiver receives a segment with a sequence number that is larger than the next, expected, in-order sequence number, it detects a gap in the data stream—that is, a missing segment. This gap could be the result of lost or reordered segments within the network. 3.4.3
TCP ACK Generation
Event
TCP Receiver Action
Arrival of in-order segment with expected sequence number. All data up to expected sequence number already acknowledged.
Delayed ACK. Wait up to 500 msec for arrival of another in-order segment. If next in-order segment does not arrive in this interval, send an ACK.
Arrival of in-order segment with expected sequence number. One other in-order segment waiting for ACK transmission.
Immediately send single cumulative ACK, ACKing both in-order segments.
Arrival of out-of-order segment with higher-than-expected sequence number. Gap detected.
Immediately send duplicate ACK, indicating sequence number of next expected byte (which is the lower end of the gap).
Arrival of segment that partially or completely fills in gap in received data.
Immediately send ACK, provided that segment starts at the lower end of gap.
Het discard out of order packets niet en werkt met cumulative Indien er drie duplicate ACKs 3.5acknowledgement. • CONNECTION-ORIENTED TRANSPORT: TCP Table 3.2 gaan TCP we ACK Recommendation 5681] worden ontvangen uitGeneration van het ergste. We sturen het [RFC segment waarvan we drie duplicate ACKS hebben ontvangen opnieuw voordat er een timeout optreedt. Dit wordt ook wel fast retransmit genoemd. Hieronder staat een voorbeeld: Host A
Host B
seq= 92, 8 by seq= tes 100, of d ata 20 b seq= ytes 120, o f 1 data 5 by seq= tes 135, o f d 6 by ata seq= tes 141, of d ata 16 b ytes of d ata
X
ack=100 ack=100 ack=100 ack=100
seq
Timeout
Time
Figure 3.37 3.4.4 TCP Congestion Control
=10
0,
20
byt
es
of
dat
a
Time
Fast retransmit: retransmitting the missing segment before the segment’s timer expires
TCP congestion control werkt als volgt: we beginnen in een state die slow start heet. Hierin verhogen we de congesby the receiver. as snelheid shown inwaarmee Figure 3.33 alsodata Figure tion window (cwnd)ACKed exponentieel. cwnd is Consequently, een limiet op de de (see sender kan 3.19), versturen. De cwnd the TCP sender need only smallest Wanneer sequence eindigt numberdeze of a transmitted wordt elke RTT verdubbeld. ssthresh is de maintain slow startthe threshold. exponenti¨elebut groei? unacknowledged byte (SendBase) and the sequence number of the next byte to be Indien er eensent timeout optreedt wordtIndethis waarde cwnd/2. protocol. De waarde van cwnd wordt (NextSeqNum). sense,ssthresh TCP looksveranderd a lot like naar a GBN-style But nu veranderdthere naar are 1 ensome het proces weer opnieuw slow state). Many TCP implestrikingbegint differences between(in TCP andstart Go-Back-N. mentations will buffer correctly received but out-of-order segments [Stevens 1994]. Indien er drie dezelfdealso ACKs er geswitched naar eenof fast recovery Consider whatbinnenkomen happens whenwordt the sender sends a sequence segments 1, 2, state. . . . , Eerst wordt N, and all of the segments arrive in order without error at the receiver. Further suppose that the acknowledgment for packet n <15 N gets lost, but the remaining N – 1 acknowledgments arrive at the sender before their respective timeouts. In this example, GBN would retransmit not only packet n, but also all of the subsequent packets n + 1, n + 2, . . . , N. TCP, on the other hand, would retransmit at most one segment, namely, seg-
249
ssthresh = cwnd/2 en daarna wordt cwnd = ssthresh + 3MSS. Wanneer de waarde van cwnd groter of gelijk is aan ssthresh gaan we naar een state die congestion avoidance wordt genoemd. Hierin verhogen we de cwnd telkens met e´ e´ n MSS. MSS staat voor Maximum Segment Size. Een voorbeeld: als MSS is 1460 bytes en cwnd is 14600 bytes, dan worden er 10 segments verstuurd in een RTT. Elke ACK vergroot de congestion window size met 1/10 MSS, dus zal de congestion window met e´ e´ n 3.7 • TCP CONGESTION CONTROL 275 MSS groter zijn geworden als alle 10 segments zijn ontvangen. Zie het figuur hieronder: duplicate ACK dupACKcount++
new ACK
new ACK
cwnd=cwnd+MSS dupACKcount=0 transmit new segment(s), as allowed
cwnd=cwnd+MSS •(MSS/cwnd) dupACKcount=0 transmit new segment(s), as allowed
Λ cwnd=1 MSS ssthresh =64 KB dupACKcount=0
cwnd ≥ ssthresh Λ
Slow start
Congestion avoidance
timeout
timeout
ssthresh=cwnd/2 cwnd=1 MSS dupACKcount=0 retransmit missing segment
ssthresh=cwnd/2 cwnd=1 MSS dupACKcount=0 retransmit missing segment
duplicate ACK dupACKcount++
timeout
dupACKcount==3
ssthresh=cwnd/2 cwnd=1 dupACKcount=0 retransmit missing segment
new ACK cwnd=ssthresh dupACKcount=0
ssthresh=cwnd/2 cwnd=ssthresh+3•MSS retransmit missing segment
dupACKcount==3 ssthresh=cwnd/2 cwnd=ssthresh+3•MSS retransmit missing segment
Fast recovery
duplicate ACK cwnd=cwnd+MSS transmit new segment(s), as allowed
Figure 3.52
Figure 7: van TCP congestion control FSM description of Automaat TCP congestion control
Hieronder staat een voorbeeld van twee verschillende implementaties: TCP Tahoe en TCP Reno:
MSS, and thus, the value of the congestion window will have increased by one MSS after ACKs when all 10 segments have been received. But when should congestion avoidance’s linear increase (of 1 MSS per RTT) end? TCP’s congestion-avoidance algorithm behaves the same when a timeout occurs. As in the case of slow start: The value of cwnd is set to 1 MSS, and the value of ssthresh is updated to half the value of cwnd when the loss event occurred. Recall, however, that a loss event also can be triggered by a triple duplicate ACK event. In this case, the network is continuing to deliver segments from sender to receiver (as indicated by the receipt of duplicate ACKs). So TCP’s behavior to this type of loss event should be less drastic than with a timeout-indicated loss: TCP halves the value of cwnd (adding in 3 MSS for good measure to account for
16
transmission rounds, Tahoe and Reno take identical actions. The congestion window climbs exponentially fast during slow start and hits the threshold at the fourth round of transmission. The congestion window then climbs linearly until a triple duplicateACK event occurs, just after transmission round 8. Note that the congestion window is 12 • MSS when this loss event occurs. The value of ssthresh is then set to
Examining the behavior of TCP
16 Congestion window (in segments)
14 12
TCP Reno
10 ssthresh
8 6
ssthresh
4 TCP Tahoe
2 0 0
Figure 3.53
1
2
3
4
5 6 7 8 9 10 11 12 13 14 15 Transmission round
Evolution of TCP’s congestion window (Tahoe and Reno) Figure 8: TCP Tahoe en TCP Reno
Zoals te zien is in het figuur hierboven, is de ssthresh initieel gelijk aan 8 MSS. Voor de eerste acht transmission rounds doen Tahoe en Reno precies hetzelfde. Vlak na transmission round 8 worden er 3 duplicate ACKs ontvangen. De congestion window was 12 MSS toen dit gebeurde. De waarde van ssthresh wordt dan gelijk aan 1=2 cwnd D 6MSS. TCP Reno zet de waarde van de congestion window nu gelijk aan cwnd D ssthresh C 3 MSS D 6 MSS C 3 MSS D 9 MSS (van congestion avoidance naar fast recovery) en groeit daarna lineair. TCP Tahoe zet de congestion window op 1 MSS en groeit dan exponentieel, totdat het de waarde van ssthresh. Daarna zal het weer lineair groeien. 3.4.5
Fairness
3.7
•
TCP CONGESTION CONTROL
281
TCP is fair. Stel dat we N TCP sessions hebben, met een link met bandbreedte R. Elke connectie moet een average rate van R/N hebben. R
Connection 2 throughput
Full bandwidth utilization line Equal bandwidth share D B
C A
Connection 1 throughput
R
Figure 3.56 Throughput realized by TCP connections 1 and 2
Figure 9: Throughput van connection 1 en connection 2 We nemen aan dat beide connecties dezelfde MSS en RTT hebben. Punt A geeft de initi¨ele throughput aan. Omdat R, no loss will occur, and both connections will increase their window by 1 MSS de throughput op dit moment kleiner is dan R zal er geen loss optreden. Beide connecties zullen dus hun window per RTT as a result of TCP’s congestion-avoidance algorithm. Thus, the joint vergroten met 1 MSS per RTT. Uiteindelijk er op punt B along packet loss op. A enincrease B halveren hun window. We throughput of thetreedt two connections proceeds a 45-degree line (equal for both connections) starting from pointkleiner A. Eventually, the R linkverhogen bandwidth jointly belandden nu op het punt C. Omdat de totale throughput weer is dan ze hun window weer. In punt consumed by the two connections will be greater than R, and eventually packet loss D zal er weer packet loss optreden, waardoor de windows gehalveerd worden. Zoals we kunnen zien nadert dit de lijn will occur. Suppose that connections 1 and 2 experience packet loss when they realize indicated by point B. Connections 1 and 2 then decrease their van 45 graden vanuit de oorsprong, diethroughputs gelijke bandbreedte aangeeft. windows by a factor of two. The resulting throughputs realized are thus at point C, halfway along a vector starting at B and ending at the origin. Because the joint bandwidth use is less than R at point C, the two connections again increase their throughputs along a 45-degree line starting from C. Eventually, loss will again occur, for example, at point D, and the two connections again decrease their window sizes by a factor of two, and so on. You should convince yourself that the bandwidth realized by the two connections eventually fluctuates along the equal bandwidth share line. You should also convince yourself that the two connections will converge to this behavior regardless of where they are in the two-dimensional space! Although a number of idealized assumptions lie behind this scenario, it still provides an intuitive feel for why TCP results in an equal sharing of bandwidth among connections. 17 In our idealized scenario, we assumed that only TCP connections traverse the bottleneck link, that the connections have the same RTT value, and that only a
4.4
4 4.1
H4
•
THE INTERNET PROTOCOL (IP)
Fragmentation: In: one large datagram (4,000 bytes) 4.4 Out: 3 smaller datagrams
IPv4 vs. IPv6
•
337
THE INTERNET PROTOCOL (IP)
333
Link MTU: 1,500 bytes
IPv4 heeft een datagram die er als volgt uitziet: 32 bits Reassembly: Header Datagram length (bytes) Version Type of service In: 3 smaller lengthdatagrams Out: one large datagram (4,000 bytes) 16-bit Identifier Flags 13-bit Fragmentation offset Time-to-live
Upper-layer protocol
Header checksum
32-bit Source IP address 32-bit Destination IP address Options (if any) Figure 4.14 IP fragmentation and reassembly Data At the destination, the payload of the datagram is passed to the transport layer only after the IP layer has fully reconstructed the original IP datagram. If one or more of the fragments does not arrive at the destination, the incomplete datagram is datadiscarded te grootand omnot inpassed 14.13 datagram te stoppen. We assplitsen de in data op in Figure IPv4 datagram format to the transport layer. But, we learned the dan previous
Soms is de fragments. We geven in de header aan wat de offset is van het fragment t.o.v. de originele data en als het het laatste fragment is. Een voorbeeld: IPv4Bytes datagram format is shown ID in Figure 4.13. The Offsetkey fields in the IPv4 datagram Flag are the following: flag 1 (meaning identification 777 offset 0 (meaning the data 1,480 bytes in 1st fragment • Version These 4 bits specify the IP should protocol version of the datagram. there is more) be inserted beginning the data fieldnumber. of By can0)determine how to interpret at byte the IPlooking datagram at the version number, the router the of the IP datagram. versions IP use data2nd fragment 1,480remainder bytes offset 185 of (meaning thedifferent data flag 1 (meaning identification Different 777 gram current version IP, IPv4, of data formats. The datagram format for the should be inserted beginningofat byte thereisis more) shown in Figure 4.13. The datagram format 1,480. for theNote new IP (IPv6) is thatversion 185 · 8 of1,480) discussed section. 777 1,020 bytes at the end of this 3rd fragment identification offset 370 (meaning the data flag 0 (meaning this ( 3,980–1,480–1,480) • Header length. Because an IPv4 datagram should can contain variable number be inserted abeginning at byte is theoflast fragment) of data (which are included in the IPv4 datagram options are needed 2,960.header), Note that these 370 · 84 bits 2,960) to determine where in the IP datagram the data actually begins. Most IP datagrams do not contain options, so the typical IP datagram has a 20-byte header. Table 4.2 IP fragments • Type of service. The type of service (TOS) bits were included in the IPv4 header to allow different types of IP datagrams (for example, datagrams particularly 4.1.1 IPv4 addressing requiring low delay, high throughput, or reliability) to be distinguished from each For example, itnotatie might beopgeschreven. useful to distinguish real-time datagrams IP adressen worden meestal inother. dotted-decimal Hierin worden de (such bytesasals decimale waardes IP telephony application) from non-real-time traffic (for examgenoteerd, gescheiden door eenthose ‘.’ used van by deanandere bytes. Een voorbeeld: 193.32.126.9. Elke decimaal staat voor 1 ple, FTP). The specific level of service to be provided is a policy issue deterbyte, ofwel 8 bits. In een subnet staatbyeen gedeelteadministrator. van de IP We’ll adressen vanthedetopic hosts in dit subnet zitten vast. Stel mined the router’s explore of die differentiated we hebben het volgende subnet:service 223.1.1.0/24, in Chapter 7./24 wordt hier het subnet mask genoemd. In dit geval geeft het aan dat Fragment
meest linker 24 bits het subnet adres aangeven. 24/8 = 3 bytes, dus de eerste 3 bytes geven het subnet aan. Hieronder staat een plaatje met subnets en computers in deze subnets:
18
Figure 4.15 provides an example of IP addressing and interfaces. In this figure, one router (with three interfaces) is used to interconnect seven hosts. Take a close look at the IP addresses assigned to the host and router interfaces, as there are several things to notice. The three hosts in the upper-left portion of Figure 4.15, and the router interface to which they are connected, all have an IP address of the form 223.1.1.xxx. That is, they all have the same leftmost 24 bits in their IP address. The four interfaces are also interconnected to each other by a network that contains no routers. This network
223.1.1.1 223.1.1.4
223.1.2.9
223.1.2.1
223.1.3.27 223.1.1.2
223.1.2.2 223.1.1.3
223.1.3.1
223.1.3.2
Figure 4.15 Interface addresses and subnets Figure 10: We zien hier drie verschillende subnets: 223.1.1.0/32, 223.1.2.0/23 en 223.1.3.0/23
4.1.2
4.4
IPv6
•
THE INTERNET PROTOCOL (IP)
Omdat het aantal mogelijke IP adressen dat we nog kunnen kiezen steeds kleiner wordt bestaan er tegenwoordig ook IPv6 adresssen. Een IPv6 address is 128 bits groot. Een IPv6 datagram heeft het volgende formaat: 32 bits
Version
Traffic class
Flow label
Payload length
Next hdr
Hop limit
Source address (128 bits) Destination address (128 bits) Data
Omdat nog niet alle nodes IPv6 capable zijn, maken we gebruik van tunneling. Stel dat twee IPv6 nodes willen FigureZe 4.24 IPv6 datagram format praten met IPv6 datagrams. zijn echter verbonden elkaar met nodes die alleen IPv4 capable zijn. In tunneling wordt het gehele IPv6 datagram in de payload van een IPv4 datagram gestopt. Dit datagram wordt dan verstuurt naar de IPv6 node. Omdat het voor de tussenliggende nodes lijkt als het een IPv4 datagram is, sturen ze het gewoon door. Als de datagram wordt ontvangen door de IPv6 het alsAhet IPv4 datagram inderdaad een IPv6 for faster processing of node the IPkijkt datagram. new encoding of options allows for datagram bevat. Indien dit het gevalmore is haalt het het IPv6 datagram eruit en verstuurd dit naar zijn IPv6 capable neighbor. flexible options processing.
• Flow labeling and priority. IPv6 has an elusive definition of a flow. RFC 1752 and RFC 2460 state that this allows “labeling of packets belonging to particular flows for which the sender requests special handling, such as a nondefault quality of service or real-time service.” For example, audio and video transmission might likely be treated as a flow. On the other hand, the more traditional applications, such as file transfer and e-mail, might not be treated as flows. It is possible that the traffic carried by a high-priority user (for example, someone paying for better service for their traffic) might also be treated as a flow. What is clear, however, is that the designers of IPv6 foresee the eventual need to be able to differentiate among the flows, even if the exact meaning of a flow has not yet been determined. The IPv6 header also has an 8-bit traffic class field. This field, like the TOS field in IPv4, can be used to give priority to certain datagrams within a flow, or it can be used to give priority to datagrams from certain applications (for example, ICMP) over datagrams from other applications (for example, network news). As noted above, a comparison of Figure 4.24 with Figure 4.13 reveals the simpler, more streamlined structure of the IPv6 datagram. The following fields are 19 defined in IPv6: • Version. This 4-bit field identifies the IP version number. Not surprisingly, IPv6
357
4.4
•
THE INTERNET PROTOCOL (IP)
Logical view IPv6
IPv6
A
Tunnel
B
IPv6
IPv6
E
F
Physical view IPv6
IPv6
IPv4
IPv4
IPv6
IPv6
A
B
C
D
E
F
Flow: X Source: A Dest: F
Source: B Dest: E
data
Source: B Dest: E
Flow: X Source: A Dest: F
Flow: X Source: A Dest: F
data
data
A to B: IPv6
4.2
data E to F: IPv6
B to C: IPv4 (encapsulating IPv6)
Figure 4.26
Flow: X Source: A Dest: F
Tunneling
D to E: IPv4 (encapsulating IPv6)
Figure 11: IPv6 tunneling
NAT
This IPv4apparaten datagram is then to the IPv6 node on the receiving side of Bij NAT zitten er 350 meerdere e´ e´ naddressed openbaar CHAPTER 4 • achter THE NETWORK LAYER ip adres. NAT schrijft alle source IP en poort nummer om the tunnel (for example, E) and sent to themapping first node in the tunnel example, naar NAT IP met een nieuw poort nummer. Het onthoudt deze in een NAT table.(for Indien er weer een pakketje C). The intervening IPv4 routers in the tunnel route this IPv4 datagram among binnenkomt, wordt de informatie weer overschreven zoals die in de NAT table stond. themselves, just as they would any other datagram, blissfully unaware that the translationIPv6 table datagram. The IPv6 node on the IPv4 datagram itself contains aNAT complete receiving side of the tunnel eventually receives the IPv4 datagram (it is the destiWAN side LAN side nation of the IPv4 datagram!), determines that the IPv4 datagram contains an 138.76.29.7, 5001 10.0.0.1, 3345 . . . IPv6 datagram, ... IPv6 datagram, extracts the and then routes the IPv6 datagram exactly as it would if it had received the IPv6 datagram from a directly connected S = 10.0.0.1, 3345 IPv6 neighbor. 10.0.0.1 D = 128.119.40.186, 80 We end this section by noting that while the adoption of IPv6 was initially 1 slow to take off [Lawton 2001], S = 138.76.29.7, 5001 momentum has been building recently. See [Hus2 D = 128.119.40.186, 80 ton 2008b] for discussion of IPv6 deployment as of 2008; see [NIST IPv6 2012] 10.0.0.4 10.0.0.2 for a snapshort of US IPv6138.76.29.7 deployment. The proliferation of devices such as IP4 enabled Sphones and 80 other portable devicesS =provides an80additional push for more 128.119.40.186, = 128.119.40.186, 3 D = 138.76.29.7, 5001
D = 10.0.0.1, 3345
10.0.0.3
Figure 4.22 Network address translation
Figure 12: NAT forwarding, S staat voor source, D voor destination
4.3
Virtual Circuit (VC)
thousands of home networks, many using the same address space, 10.0.0.0/24. Devices within a given home network can send packets to each other using Een virtual circuit bestaat uit een pad10.0.0.0/24 tussen deaddressing. source en destination Daarnaast zijn er VC numbers: e´ e´ n voor However, packetshost. forwarded beyond the home network into elke router op het pad. Als laatste zijnthe er larger entries in de forwarding table use vanthese de routers die hetapad liggen. global Internet clearly cannot addresses (asop either source or a Een packet are tussenliggende hundreds of thousands of networks using dit this VC nummer dat behoort tot een VC bevat een VCdestination nummeraddress) in de because header.there Elke router herschrijft block of addresses. That is, the 10.0.0.0/24 addresses can only have meaning within the given home network. But if private addresses only have meaning within a given network, how is addressing handled when packets are sent to or received from the global Internet, where addresses are necessarily unique? The answer lies in under20 standing NAT. The NAT-enabled router does not look like a router to the outside world. Instead the NAT router behaves to the outside world as a single device with a single IP address. In Figure 4.22, all traffic leaving the home router for the larger Internet has
361
Host A requests that the network establish a VC between itself and Host B. Suppose also that the network chooses the path A-R1-R2-B and assigns VC numbers 12, 22, and 32 to the three links in this path for this virtual circuit. In this case, when a packet in this VC leaves Host A, the value in the VC number field in the packet header is 12; when it leaves R1, the value is 22; and when it leaves R2, the value is 32. How does the router determine the replacement VC number for a packet traversing the router? For a VC network, each router’s forwarding table includes VC m.b.v. de forwarding table en forward het packet naar de juiste interface. Dit kan er als volgt uitzien: 318
CHAPTER 4
•
THE NETWORK LAYER A
R1
R2
1
2 3
4.2
1 •
B 2
VIRTUAL CIRCUIT AND DATAGRAM NETWORKS 3
Now let’s further suppose that our router has four links, numbered 0 through 3, and that packets are to be forwarded to the link interfaces as follows:
Destination Address Range table in R1 might look something Link Interface number translation; for example, the forwarding R3 R4 like this: 11001000 00010111 00010000 00000000 Figure 4.3 A simple virtual Incoming Interface Incoming VC # circuit network Outgoing Interface Outgoing 0VC # through 11001000 00010111 00010111 11111111 1 12 2 22 11001000 00010111 00011000 00000000 2 63 1 18 through 1 3 11001000 000101117 00011000 11111111 2 17 1 97 3 87 ... 11001000 00010111 ... 00011001 00000000 ... ... through 2 11001000 00010111 00011111 11111111 Voor een VC network zijn er drie fasen: setup, data transfer en teardown. Whenever a new VC is established across a router, an entry is added to the forwarding table. Similarly, whenever a VC terminates, the appropriate entries in each table otherwise 3 4.4 Datgram Network along its path are removed. You might be wondering why a packet doesn’t just keep the same VC number In een datagram netwerk wordt hetfor destination address header toegevoegd wordt het pakketje in het netwerk Clearly, this example, it isaan notdenecessary to have 4 en billion entries in the router’s on each of the links along its route. The answer is twofold. First, replacing the numverstuurd. De routers maken gebruiktable. van switching Hierinhave wordt bepaalde table delenwith van het ip forwarding We could,tables. for example, thegemachted following op forwarding ber from link to link reduces the length of the VC field in the packet header. Second, adres. Indien er een matchjust is wordt het bijbehorende link interface gebruikt om het pakketje naar te forwarden. Er is four entries: and more importantly, VC setup is considerably simplified by permitting a different sprake van longest prefix matching rule: de langst matchende entry wordt gebruikt. Een voorbeeld: VC number at each link along the path of the VC. Specifically, with multiple VC Match Interface of the VC numbers, each link inPrefix the path can choose a VC numberLink independently numbers chosen at other links along the path. If a common VC number were required 00010 would have to exchange 0 and process a subfor all links11001000 along the 00010111 path, the routers 11001000 00010111 00011000 stantial number of messages to agree on a common VC number1(e.g., one that is not 11001000 00010111 being used by any other existing00011 VC at these routers) to be used2 for a connection. otherwise 3 In a VC network, the network’s routers must maintain connection state information for the ongoing connections. Specifically, each time a new connection is across a new connection entry must be added to the router’s for-destiWith this stylea router, of forwarding table, the router matches a prefix of the packet’s 4.5 Switching established warding table; and each a connection is released, an aentry must removed nation address with time the entries in the table; if there’s match, theberouter forwards Bij switching wordt from er gekeken naar het inkomende packet For in de router geforward moet worden. Dit the packet table. Note thatpoort even if there is no translation, it is stillthe necesthe towelke a link associated with theVC-number match. example, suppose packet’s gebeurt in de switching Er zijnconnection drie vormen vaninformation switching: saryfabric. to maintain state that associates VC numbers with the out-21-bit destination address is 11001000 00010111 00010110 10100001; because put interface The matches issue of the whether or notina the router maintains connection the prefixhetofnumbers. this address first table, the router switching via memory: packet wordt gekopieerd naar hetentry geheugen. De processor haaltforwards de informatie uit de state information forinterface each ongoing connection is amatch crucialany one—one thatthree we’llentries, return then packet to link 0. If a prefix doesn’t of the first header en bepaalt waar het packet heen moet. Vervolgens wordt het packet naar de juiste output port gekopieerd. to repeatedly in forwards this book.the packet to interface 3. Although this sounds simple enough, the router switching via bus:There het packet wordt direct via phases een shared alle outputthat ports are identifiable in a bus virtual circuit: there’s anthree important subtlety here. You maynaar have noticed it isvervoerd. possible Het for akrijgt des- hierbij een label met met de juiste output De processor komt nietFor bijexample, aan te pas. ontvangt tination addressport. to match more than onehier entry. theElke firstoutput 24 bitspoort of the het packet, maar de poort diethe matched met 00011000 hetthe label houdt het packet. Het label wordt daninverwijderd. • alleen VCaddress setup. During setup phase, sending transport layer the net11001000 00010111 10101010 match thecontacts second entry the Indien er meerderework packets op specifies hetzelfde moment elk match voor een output moeten ze allemaal layer, the receiver’s address, and waits for the network set upWhen table, and the first 21 bits ofarriveren, the address theandere third entry inpoort, thetotable. wachten. Dit komtthe omdat maar e´ e´ n packet tegelijkertijd over de the bus vervoerd kanand worden. VC.are The network layer determines theuses path between sender receiver,rule; that that there multiple matches, the router longest prefix matching is,is, theit series of links andmatching routers through all packets of thethe VCpacket will travel. finds the longest entry inwhich the table and forwards to the link switching via interconnection network: een crossbar switch interconnection netwerk van 2N bussen die N The network layer also determines the VC number for each link along the path. input poorten met N output poorten verbindt. Elke horizontale bus snijdt met een verticale bus die op elk Finally, the network layer adds an entry in the forwarding table in each router geopend of gesloten kan worden. Wanneer een packet van A naar Y moet, en A stuurt het packet in de bus, dan worden de kruispunten tussen A en Y gesloten, waardoor alleen Y het packet ontvangt. Indien twee packets verschillende input en output ports gebruiken, kunnen ze op het zelfde moment verstuurd worden op de bus. 21
315
4.3
Memory
•
325
WHAT’S INSIDE A ROUTER?
Crossbar A B
X
A
Y
B
Z
C
Memory C
X
Y
Z
Bus A 330
CHAPTER 4
•
X
THE LAYER B NETWORK Y
C Z desired output queue in an FCFS manner. Multiple packets can be transferred in parallel, as long as their output ports are different. However, if two packets at the front of two input queues are destined for the same output queue, then one of the packets will be blocked and must wait at the input queue—the switching fabric can transfer only one packet to a given output port at a time. Key: Figure 4.11 shows an example in which two packets (darkly shaded) at the front ofport their input queues are Output destined for the same upper-right output port. Suppose that Input port the switch fabric chooses to transfer the packet from the front of the upper-left queue. In this case, the darkly shaded packet in the lower-left queue must wait. But Er zijnFigure verschillende waar queuing kan optreden. Indien er sneller packets arriveren op de input ports dan 4.8 plekken Three techniques not onlyswitching must this darkly shaded packet wait, so too must the lightly shaded packet de switching fabric kan verwerken, treedt er input queuing Indienqueue, de switching fabric that is queued behind that packet in theop. lower-left even though theresneller is no is dan de rate waarop de packets worden verstuurd treedt er queuing op. Een speciale soort van contention foroutput the middle-right output port (the destination for theinput lightlyqueuing shaded heet head-of-the-line the CPU (routing processor). Input and output ports functioned as traditional I/O packet). Thisopphenomenon is known as head-of-the-line (HOL) blocking an packet dat voor hem in (HOL) blocking. Stel dat een packet een input poort is gearriveerd en moet wachten op in een
devices in a traditional operating system. An input port with an arriving packet de wachtrij staat. packet hemprocessor is geblocked het moet omdat de copied ouput port niet vrij is. Echter first Het signaled thevoor routing via omdat an interrupt. Thewachten packet was then is de output port van het packet dat geblocked wordt wel vrij. Zie het figuur hieronder: from the input port into processor memory. The routing processor then extracted Output port contention at time t — the destination address from the header, looked appropriate output port in one dark packet canup be the transferred the forwarding table, and copied the packet to the output port’s buffers. In this scenario, if the memory bandwidth is such that B packets per second can be writSwitch ten into, or read from, memory, then the overall fabric forwarding throughput (the total rate at which packets are transferred from input ports to output ports) must be less than B/2. Note also that two packets cannot be forwarded at the same time, even if they have different destination ports, since only one memory read/write over the shared system bus can be done at a time. Many modern routers switch via memory. A major difference from early routers, however, is that the lookup of the address HOL andblocking the storing of the packet Lightdestination blue packet experiences into the appropriate memory location are performed by processing on the input line cards. In some ways, routers that switch via memory look very much like shared-memory multiprocessors, with the processing on a line card switching Switch (writing) packets into the memory of the appropriate output port. Cisco’s Catalyst fabric 8500 series switches [Cisco 8500 2012] forward packets via a shared memory.
Key: destined for upper output port
destined for middle output port
destined for lower output port
Figure 4.11 HOL blocking at an input queued switch Figure 13: HOL blocking at an input queued
22
switch
4.6
DHCP
DHCP zorgt ervoor dat een host automatisch een IP adres toegewezen krijgt. Eerst wordt met DHCP server discovery gekeken welke DHCP server gevraagd gaat worden. Dit gebeurt met een DHCP discovery message. Een DHCP server kan hierop reageren met een DHCP offer message. Dit bericht bevat een IP adres dat de client zou kunnen kiezen, samen met een IP address lease time: de tijdsduur die aangeeft hoelang het IP address geldig is. De client reageert met een DHCP 348 request,CHAPTER waarin 4het•aangeeft welke LAYER parameters het gaat gebruiken. Hierop reageert de server weer met een THE NETWORK DHCP ACK, waarin deze parameters worden bevestigd. De client kan het IP address nu gebruiken. DHCP server: 223.1.2.5
Arriving client
DHCP discover src: 0.0.0.0, 68 dest: 255.255.255.255,67 DHCPDISCOVER yiaddr: 0.0.0.0 transaction ID: 654
DHCP offer src: 223.1.2.5, 67 dest: 255.255.255.255,68 DHCPOFFER yiaddrr: 223.1.2.4 transaction ID: 654 DHCP server ID: 223.1.2.5 Lifetime: 3600 secs
DHCP request src: 0.0.0.0, 68 dest: 255.255.255.255, 67 DHCPREQUEST yiaddrr: 223.1.2.4 transaction ID: 655 DHCP server ID: 223.1.2.5 Lifetime: 3600 secs
DHCP ACK src: 223.1.2.5, 67 dest: 255.255.255.255,68 DHCPACK yiaddrr: 223.1.2.4 transaction ID: 655 DHCP server ID: 223.1.2.5 Lifetime: 3600 secs
Time
Time
Figure 4.21Figure DHCP client-server interaction 14: DHCP client-server
4.7
interactie
Link-State (LS)
• DHCP request. The newly arriving client will choose from among one or more server offers and respond to its selected offer with a DHCP request message, Een link-state (LS) algoritme is echoing een algoritme dat aan deparameters. hand van globale state informatie berekeningen uitvoert. back the configuration Dijkstra’s algoritme wordt gebruikt als een link-state routing de kortste te bepalen. De volgende • DHCP ACK. The server responds algoritme to the DHCPom request messageafstand with a DHCP terminologie wordt gebruikt: ACK message, confirming the requested parameters. Once receives the DHCP ACK, the interaction is complete andhuidige the D.v/: de kosten van het pad metthedeclient minste kosten van source naar destination v in de iteratie van het client can use the DHCP-allocated IP address for the lease duration. Since a client algoritme.
p.v/: vorige node in het pad met de minste kosten van source naar v N 0 : deelverzameling van nodes; v zit in N 0 als het pad van source naar v bekend is. Hieronder staat een voorbeeld van het algoritme, met de werking ervan in pseudo code:
23
368
CHAPTER 4
VideoNote Dijkstra’s algorithm: discussion and example
•
THE NETWORK LAYER
The global routing algorithm consists of an initialization step followed by a loop. The number of times the loop is executed is equal to the number of nodes in the network. Upon termination, the algorithm will have calculated the shortest paths example, consider network in Figure 4.27 and compute the fromAs theansource node let’s u to every otherthe node in the network. least-cost paths from u to all possible destinations. A tabular summary of the algorithm’s computation is shown in Table 4.3, where each line in the table gives Link-State (LS) Algorithm for Source Node u the values of the algorithm’s variables at the end of the iteration. Let’s consider the few first steps in detail. 1 Initialization: N’initialization = {u} •2 In the step, the currently known least-cost paths from u to its 3 directly forattached all neighbors, nodes v v, x, and w, are initialized to 2, 1, and 5, respectively. 4 Note in particular if v isthat a the neighbor u 5 (even though we will soon see that cost to w isof set to 5 a lesser-costthen D(v) = c(u,v) path does indeed exist) since this is the cost of the direct (one hop) 6 link from else D(v) = ∞ to y and z are set to infinity because they are not u to w. The costs 7 directly connected to u. •8 InLoop the first iteration, we look among those nodes not yet added to the set N and 9 find that find notthein that D(w) is a iteration. minimum nodew with leastN’ costsuch as of the end of the previous That node 10is x, with add awcost toofN’ 1, and thus x is added to the set N . Line 12 of the LS algo11rithmupdate D(v) for eachD(v) neighbor v of w andthenot inshown N’: is then performed to update for all nodes v, yielding results 12in the secondD(v) = min( D(v), D(w) + c(w,v) ) • unchanged. ROUTING ALGORITHMS line (Step 1) in Table 4.3. The cost of the path4.5 to v is 13The cost /* of new cost to v is either old cost to v or known the path to w (which was 5 at the end of the initialization) through 14node xleast path cost to w plus cost from w to v */ is found to have a cost of 4. Hence this lower-cost path is selected and w’s 15predecessor until N’=along N the shortest path from u is set to x. Similarly, the cost to y (through x) is computed to be 2, and the table is updated accordingly. • In the second iteration, nodes 5 v and y are found to have the least-cost paths (2), and we break the tie arbitrarily and add y to the set N so that N now contains u, x, and y. The cost to the remaining nodes 3 not yet in N , that is, nodes v, w, and z, v algorithm,w are updated via line 12 of the LS yielding the results shown in the 2 5 third row in the Table 4.3. 2 1 • And so on. . . . z u 3 1
2
When the LS algorithm terminates, we have, for each node, its predecessor x y 1 node. For each predecessor, we also along the least-cost path from the source
step N’ D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) Figure 4.27 Abstract graph model of a computer network 0 u 2,u 5,u 1,u ∞ ∞ 1 ux 2,u 4,x 2,x ∞ natu2 Given uxythat costs are 2,uassigned to the 3,yvarious edges in the graph abstraction, a 4,y ral goal of a routing algorithm is to identify the least costly paths between sources 3 uxyv 3,y 4,yand destinations. To make this problem more precise, recall that a path in a graph 4 uxyvw 4,yG = (N,E) is a sequence of nodes (x , x ,..., x ) such that each of the pairs (x 1 2 p 1,x2), 5 uxyvwz (x2,x3),...,(xp-1,xp) are edges in E. The cost of a path (x1,x2,..., xp) is simply the sum of all the edge costs along the path, that is, c(x ,x2) + c(x2,x3) + ...+ c(xp-1,xp). Given any We willen alle kortste afstanden vanaf het punt u weten.1 Initieel kijken we welke nodes directe buren zijn van two nodes y, there are paths on between the two in nodes, with each Table 4.3x and Running the typically link-statemany algorithm the network Figure 4.27 u. Voor deze nodes slaan we direct de kosten van dit pad samen met voorgaande node op. Voor alle nodes die path having a cost. One or more of these paths is a least-cost path. The least-cost niet direct met u verbonden zijn, zetten we de waarde van de tabel op 1. Dus de kortste paden van u naar v; x problem is therefore clear: Find a path between the source and destination that has en w worden respectievelijk 2,1 en 5. least cost. In Figure 4.27, for example, the least-cost path between source node u and destination w isde(u, x, y, die w) nog withniet a path of 3. Note if all edgesdeinnode the met kleinste In de eerste iteratie kijken node we naar nodes zijncost toegevoegd aanthat N 0 en zoeken theiteratie. same cost, is also the path is, pad the 1 bedragen. kortste afstandgraph in dehave vorige Dit the is inleast-cost dit gevalpath x, waarvan de shortest kosten van het (that kortste path with the smallest links between the source and thegaan destination). Dus x wordt toegevoegd aan N 0 . Nunumber we eenofnieuwe node hebben toegevoegd we de waardes in de tabel a simple try finding path nodewu (die to z eerst in Figure updaten. De kostenAsvan het padexercise, naar v verandert niet,thedeleast-cost kosten van hetfrom pad naar 5 was) door node 4.27entry and reflect moment on calculated that path. If you are like x kost nu 4. Deze wordt for dusaaangepast: 4;how x. Deyou kosten van y door x is ook kleiner danmost de waarde die we people, foundwordt the path u to z by Figure 4.27, tracing a few routes eerst hadden, dus dezeyou waarde ookfrom aangepast: 2; examining y. from u to z, and somehow convincing yourself that the path you0 had chosen had the In de tweede least iteratie kunnen wealluitpossible 2 nodespaths. kiezen(Did om toe voegen v en y. Hetpaths maakt nu niet uit cost among youtecheck alluit of NtheW 17 possible wat we kiezen, we kiezen dus maar voor y. N 0 bevat nu u; x en y. De nodes die nu niet in N 0 zitten worden between u and z? Probably not!) Such a calculation is an example of a centralized ge¨updatet: w wordt 3; y, z wordt 4; y. Deze iteraties gaan net zo lang door tot alle nodes zijn toegevoegd aan routing algorithm—the routing algorithm was run in one location, your brain, with N 0. complete information about the network. Broadly, one way in which we can classify routing algorithms is according to whether they are global or decentralized. 24 • A global routing algorithm computes the least-cost path between a source and destination using complete, global knowledge about the network. That is, the algorithm takes the connectivity between all nodes and all link costs as inputs.
365
4.8
Distance Vector (DV)
In een DV algoritme heeft elke node niet alle informatie nodig. Het werkt slechts met de informatie die het verkrijgt van zijn buren. De volgende vergelijking speelt een belangrijke rol in het DV routing algoritme: dx .y/ D minv fc.x; v/ C dv .y/ dx .y/ is de cost van het kortste pad tussen node x en node y. minv wordt over alle buren van x genomen. Hierin is c.x; v/ is de afstand van x naar v, en dv .y/ is de afstand van v naar y. Een voorbeeld, waarin we de zelfde graaf gebruiken als bij het LS algoritme. We willen de kortste afstand van source node u naar destination node z berekenen. u heeft drie buren: w; z; x. We berekenen voor al deze buren de afstand naar de destination node z: dv .z/ D 5 (via v ! x ! y ! z) dx .z/ D 3 (via x ! y ! z) dw .z/ D 3 (via w ! y ! z) We hebben ook nog de afstand van x naar deze buren nodig: c.u; v/ D 2 c.u; x/ D 1 c.u; w/ D 5 We passen nu de vergelijking toe op alle buren van x: du .z/ D minfc.u; v/ C dv .z/; c.u; x/ C dx .z/; c.u; w/ C dw .z/g D minf2 C 5; 1 C 3; 3 C 5g
4.5
•
ROUTING ALGORITHMS
373
D4 In het DV algoritme stuurt elke node informatie over de afstanden van zichzelf naar al zijn buren. Dit wordt de distance vector genoemd. In het onderstaande Distance-Vector (DV) Algorithmplaatje heeft x de buren y en z. De distance vector van x wordt dan als volgt genoteerd: Dx D ŒDx .x/; Dx .y/; Dx .z/ D Œ0; 2; 7 (initi¨ele distance vector van x). Alle nodes gebruiken dan At each node, x: de bovenstaande Bellman-Ford vergelijking om hun eigen tabel te updaten. Het algoritme ziet er als volgt uit:
1 Initialization: 2 for all destinations y in N: 3 Dx(y) = c(x,y) /* if y is not a neighbor then c(x,y) = ∞ */ 4 for each neighbor w 5 Dw(y) = ? for all destinations y in N 6 for each neighbor w 7 send distance vector Dx = [Dx(y): y in N] to w 8 9 loop 10 wait (until I see a link cost change to some neighbor w or 11 until I receive a distance vector from some neighbor w) 12 13 for each y in N: 14 Dx(y) = minv{c(x,v) + Dv(y)} 15 16 if Dx(y) changed for any destination y 17 send distance vector Dx = [Dx(y): y in N] to all neighbors 18 19 forever Hieronder staat een voorbeeld: In the DV algorithm, a node x updates its distance-vector estimate when it 25 either sees a cost change in one of its directly attached links or receives a distancevector update from some neighbor. But to update its own forwarding table for a given destination y, what node x really needs to know is not the shortest-path distance to y but instead the neighboring node v*(y) that is the next-hop router along
Figure 4.30 illustrates the operation of the DV algorithm for the simple threenode network shown at the top of the figure. The operation of the algorithm is illustrated in a synchronous manner, where all nodes simultaneously receive distance vectors from their neighbors, compute their new distance vectors, and inform their neighbors if their distance vectors have changed. After studying this example, you
y 2
1
x
7
z
Node x table
0 2 7 ∞ ∞ ∞ ∞ ∞ ∞
0 2 3 2 0 1 7 1 0
x y z
cost to x y z from
x y z
cost to x y z from
from
cost to x y z
x y z
0 2 3 2 0 1 3 1 0
Node y table
∞ ∞ ∞ 2 0 1 ∞ ∞ ∞
0 2 7 2 0 1 7 1 0
x y z
cost to x y z from
x y z
cost to x y z from
from
cost to x y z
x y z
0 2 3 2 0 1 3 1 0
Node z table
∞ ∞ ∞ ∞ ∞ ∞ 7 1 0
0 2 7 2 0 1 3 1 0
x y z
cost to x y z from
x y z
cost to x y z from
from
cost to x y z
x y z
0 2 3 2 0 1 3 1 0
Time
Figure 4.30 Distance-vector (DV) algorithm x ontvangt van y en z de volgende distance vectoren: Dy D Œ2; 0; 1 en Dz D Œ7; 1; 0. x berekent nu: – Dx .y/ D minfc.x; y/ C Dy .y/; c.x; z/ C Dz .y/g D minf2 C 0; 7 C 1g D 2. Dus de afstand van x naar y wordt nu verandert naar 2. – Dx .z/ D minfc.x; y/ C Dy .z/; c.x; z/ C Dz .z/g D minf2 C 1; 7 C 0g D 3. Dus de afstand van x naar z wordt nu verandert naar 3. y ontvangt van x en z de volgende distance vectoren: Dx D Œ0; 2; 7 en Dz D Œ7; 1; 0. y berekent nu: – Dy .x/ D minfc.y; x/ C Dx .x/; c.y; z/ C Dz .x/g D minf2 C 0; 1 C 7g D 2. Dus de afstand van y naar x wordt niet verandert, want die was al 2. – Dy .z/ D minfc.y; x/ C Dx .z/; c.y; z/ C Dz .z/g D minf2 C 7; 1 C 0g D 1. Dus de afstand van y naar z wordt niet verandert, want die was al 1. z ontvangt van x en y de volgende distance vectoren: Dx D Œ0; 2; 7 en Dy D Œ2; 0; 1. z berekent nu: – Dz .x/ D minfc.z; x/ C Dx .x/; c.z; y/ C Dy .x/g D minf7 C 0; 1 C 2g D 3. Dus de afstand van z naar x wordt verandert naar 3. – Dz .y/ D minfc.z; x/ C Dx .y/; c.z; y/ C Dy .y/g D minf2 C 2; 1 C 0g D 1. Dus de afstand van z naar y wordt niet verandert, want die was al 1.
26
Dit was slechts de eerste iteratie. Dit proces wordt telkens herhaalt als er nieuwe distance vectors binnenkomen. Indien de eigen minima van distance vectors veranderen worden deze weer opgestuurd naar de buren. Indien de kosten van een pad worden verhoogd, duurt er erg lang voordat het pad wordt aangepast (boek blz. 402). Dit komt omdat een node niet op de hoogte is van deze verhoging van de kosten en een andere node wel. Het packet zal nu telkens heen en weer worden verstuurd tussen twee nodes. Dit wordt ook wel een routing loop genoemd. Het kan opgelost worden door iets dat poisoned reverse wordt genoemd. Stel we hebben drie routers: x; y en z. Indien z packets via y naar x verstuurt, zegt z tegen y dat zijn afstand tot x oneindig is (Dv .x/ D 1). Op deze manier gelooft y dat x geen pad kent naar x zal y nooit een pakketje via z naar x sturen. Dit lost het looping op.
4.9
386 CHAPTER 4 Intra-AS Routing
•
THE NETWORK LAYER
Een intra-AS routing protocol wordt gebruikt om te bepalen hoe routing wordt gedaan in een autonomous system (AS). Destination Subnet Next Router Number of Hops to Destination w
4.9.1
Routing Information Protocol y (RIP)
A
2
B
2
z B 7 RIP gebruikt de term hop. Dit is de eenheid die wordt gebruikt om de kosten te meten. Hop is het getal dat aangeeft x — 1 hoeveel subnets we hebben doorlopen van source router naar destination subnet. De maximale kosten van een pad .. .... .... is begrensd door 15. RIP response. . messages worden gebruikt om buren te updaten. Deze worden ook wel RIP advertisements genoemd. Een RIP table wordt ook wel een routing table genoemd. Deze Figure 4.36 Routing table in router D before receiving advertisement bevat alle afstanden van de from routerworden A router tot andere386 routersCHAPTER of subnets. Advertisements gebruikt om de eigen routing table te updaten. Indien 4 • THE NETWORK LAYER de routing table ge¨updatet is, wordt naar alle buren een advertisement gestuurd die weer de aangepaste routing table Section 4.4. The table in Figure 4.36, and the subsequent tables to come, are only informatie bevat. We bekijken een voorbeeld. Hieronder staat de routing table in router D: partially complete. NowSubnet suppose that 30 secondsNext later, adverDestination Routerrouter D receives from Numberrouter of Hops Ato the Destination tisement shown in Figure 4.37. Note that this advertisement is nothing other than the routing A! This information indicates, w table information from router A 2 in particular, that subnet z is only four hops away from router A. Router D, upon receiving this y B advertisement, merges the advertisement (Figure 4.37) with the old 2routing table (Figurez 4.36). In particular, router D learns that there is now a path through router A B 7 to subnet z that is shorter than the path through router B. Thus, router D updates its x — 1 routing table to account for the shorter shortest path, as shown in Figure 4.38. How is it, you . . . .might ask, that the shortest. .path . . to subnet z has become shorter? . . . . Possibly, the decentralized distance-vector algorithm is still in the process of converging (see Section perhaps table new links and/or routers receiving were added to the AS, thus Figure4.5.2), 4.36 or Routing in router D before advertisement changing paths in the Figure 15: De routing tabletheinshortest router D voordat from router AAS. het een advertisement heeft ontvangen van router A Let’s next consider a few of the implementation aspects of RIP. Recall that RIPtabel routershet exchange advertisements approximately every 30 If aof router Zoals we kunnen zien bevat de destination subnet, next router enseconds. number hops. Next router geeft aan Section table in Figure at 4.36, theevery subsequent tables tothat come, are only does not 4.4. hearThe from its neighbor leastand once 180 seconds, neighbor is via welke routers iets verstuurd moet worden indien destination subnet gelijk is aan die entry. Stel dat router D nu een partially complete. considered to be no longer reachable; that is, either the neighbor has died or the suppose 30 seconds later, router D receives from router A the adveradvertisement krijgt van router A dieNow er als volgthatuitziet: tisement shown in Figure 4.37. Note that this advertisement is nothing other than the routing table information from router A! This information indicates, in particuDestination Nextaway Router from router A. Router Number of Hopsreceiving to Destinationthis lar, that Subnet subnet z is only four hops D, upon advertisement, merges the advertisement (Figure 4.37) with the old routing table z 4.36). In particular, router D C learns that there is now a path through 4 (Figure router A to subnet path through router B. Thus, router1D updates its w z that is shorter than the— routing table to account for the shorter shortest path, as shown in Figure 4.38. How x might ask, that the shortest — path to subnet z has become shorter? 1 is it, you Possibly, the .decentralized distance-vector. algorithm is still in the process of converging (see ... ... .... Section 4.5.2), or perhaps new links and/or routers were added to the AS, thus changing the shortest paths in the AS. Figure 4.37 Advertisement from router A Let’s next consider a few of the implementation aspects of RIP. Recall that Figureadvertisements 16: Advertisement vanevery router A If a router RIP routers exchange approximately 30 seconds. does not hear from its neighbor at least once every 180 seconds, that neighbor is Zoals we kunnen zien kent A considered een kortere naar subnetthatz (4 hops) de huidige to beroute no longer reachable; is, either thedan neighbor has died orentry the die in router D staat (7
hops). D update zijn router table aan de hand van de advertisement van A. 4.9.2
OSPF
Destination Subnet
Next Router
Number of Hops to Destination
z
C
4
Met OSPF maakt een router graaf van het gehele AS. De—router voert dan lokaal Dijkstra’s algoritme om de kortste w 1 paden naar alle subnets te bepalen. Indien er iets verandert broadcast de router de informatie naar alle andere routers x — 1 in het AS. Zie boek blz. 414. .... .... .... Figure 4.37 Advertisement from router A
27
with a given source address, it transmits the packet on all of its outgoing links (except the one on which it was received) only if the packet arrived on the link that is on its own shortest unicast path back to the source. Otherwise, the router simply discards the incoming packet without forwarding it on any of its outgoing links. Such a packet can be dropped because the router knows it either will receive or has already received a copy of this packet on the link that is on its own shortest path back to the sender. (You might want to convince yourself that this will, in fact, happen and that looping 4.10 Broadcast Routing and broadcast storms will not occur.) Note that RPF does not use unicast routing to In broadcast routing wordt een packet vanaf een source node naar alle in that het netwerk actually deliver a packet to a destination, nor andere does itnodes require a router verstuurt. know the Hiervoor zijn verschillende algoritmen: complete shortest path from itself to the source. RPF need only know the next neighbor on its unicast shortest path to the sender; it uses this neighbor’s identity only to 4.10.1 Reverse Path Broadcast determine whether or not to flood a received broadcast packet. Figure 4.44 illustrates RPF. 4.7 Suppose that the links drawn with thick lines repre• Forwarding BROADCAST ANDmet MULTICAST ROUTING 403 Als een router een broadcast packet ontvangt in Reverse Path (RPF) een gegeven source address, sent the least-cost paths from the receivers to the source (A). Node A initially broadverstuurt het het packet naar alle uitgaande links (behalve naar link waarop het packet werd ontvangen). Dit gebeurt casts a source-A packet to nodes C and B. Node B will forward the source-A packet echter onder de volgende voorwaarde: het packet wordt alleen doorgestuurd als node, van wie het packet afkomstig is, it has received from A (since A is on its least-cost path to A) to both C and D. B will ligt op het kortste pad van de node node (die het packet ontvangen heeft) naar de source. Anders negeert de router het ignorefrom (drop, without forwarding) any packets receives any other nodes (forstaat example, routers C or D). Let usafkomstig nowsource-A consider C,it which willfrom packet. Hieronder een voorbeeld waarbij het packet is vannode source A. De dikke pijlen geven de kortste receive a source-A packet directly from A as well as from B. Since B is not on C’s paden aan: own shortest path back to A, C will ignore any source-A packets it receives from B. A On the other hand, when C receives a source-A packet directly from A, it will forward the packet to nodes B, E, and F. B
Spanning-Tree Broadcast
C and RPF avoid broadcast storms, they While sequence-number-controlled flooding do not completely avoid the transmission of redundant broadcast packets. For example, in Figure 4.44, nodes B, C, D, E, and F receive either one or two redundant D broadcast packet. packets. Ideally, every node should receive only one copy of the Examining the tree consisting of the nodes connected by thick lines in Figure F E 4.45(a), you can see that if broadcast packets were forwarded only along links G Key: node would receive exactly one copy of the within this tree, each and every network pktwere will belooking forwardedfor! This tree is an example broadcast packet—exactly the solution we not and forwarded beyond router More forof a spanning tree—a tree that contains pkt each every nodereceiving in a graph. mally, a spanning tree of a graph G = (N,E) is a graph G = (N,E ) such that E is a 4.44G Reverse path forwarding subset of E, G Figure is connected, contains cycles, and G contains all the Figure 17: no Reverse forwarding met source A original nodes in G. If each link has an associated cost and the cost of a tree is the sum of the link costs, then Broadcast a spanning tree whose cost is the minimum of all of the graph’s 4.10.2 Spanning-Tree spanning trees is called (not surprisingly) a minimum spanning tree. In RPF worden tochanother nog overbodige verstuurd. Dit kunnen we oplossen met deze methode. Een spanning tree Thus, approachpackets to providing broadcast is for the network nodes to first bevat alleconstruct nodes in adespanning origineletree. graaf en bevat geennode cyckels. Alstoelke een cost heeft, When a source wants sendlink a broadcast packet,enitde som van de tree is de som van sends alle link danout is de wienslinks som that de kleinste thecosts, packet on spanning all of the tree incident belong is tode theminimum spanning spanning tree. A tree. We maken eerst een spanning Wanneer een nodepacket een packet verstuurd, packet alleen over links die liggen op de nodetree. receiving a broadcast then forwards theverstuurd packet tohet allhet its neighbors in the spanning tree. Een voorbeeld: A
A
B
B
C
C
D F
D F
E
E
G
G
a. Broadcast initiated at A
Figure 4.45
b. Broadcast initiated at D
Broadcast along spanning Figure a18: Broadcasttree m.b.v. een spanning tree
28
provide full BGP information to their customer networks. All traffic entering a stub network must be destined for that network, and all traffic leaving a stub network must have originated in that network. W and Y are clearly stub networks. X is a multihomed stub network, since it is connected to the rest of the network via two different providers (a scenario that is becoming increasingly common in practice). However, like W and Y, X itself must be the source/destination of all traffic leaving/entering X. 4.11 Inter-AS But Routing: how will thisBGP stub network behavior be implemented and enforced? How will X be prevented from forwarding traffic between B and C? This can easily be Dit is een vrij complex protocol. We leggen een voorbeeld uit. We gebruiken het onderstaande BGP scenario: Key: B A
W
Provider network
X
Customer network
C Y
Figure 4.42
A simple BGP Figure 19:scenario Een simpel BGP scenario
We nemen aan dat W,X en Y stub networks zijn en dat A,B en C backbone provider networks zijn. Al het verkeer dat op een stub network binnenkomt moet een destination zijn voor dat netwerk en al het verkeerd dat een stub network verlaat moet een source hebben vanaf dat netwerk. X is echter verbonden met zowel B als C. Hoe voorkomen we dat X informatie tussen B en C gaat forwarden? Dit kan eenvoudig opgelost worden als X zowel tegen B als C zegt dat het geen pad ander pad kent dan het pad naar zichzelf. Stel dat X een pad XCY weet, dan deelt het niet met B dat het een route weet die naar Y gaat. Omdat B niet weet dat X een pad naar Y weet, zal het ook geen verkeer sturen naar X dat bedoeld is voor Y. We focussen nu even op B. Stel dat B een pad van A heeft geleerd dat A een pad heeft AW naar W. B wil dit pad nu ook delen met zijn klant X, zodat het verkeer naar W kan routen via B. Maar moet B ook BAW delen met C? Als B dit doet dan gaat al het verkeer vanuit C dat naar W moet via B, terwijl het ook via A zou kunnen.
4.12
Multicast
In een broadcast service worden packets afgeleverd bij elke node in het netwerk. In een multicast service wordt een multicast packet maar afgeleverd aan een deelverzameling van de nodes. Hierbij werken we met een multicast group. Alle leden van een multicast group ontvangen een datagram bedoeld is voor deze group. moeten nu 4.7 dat • BROADCAST AND MULTICAST ROUTING We407 wel rekening houden met het feit dat elke host een uniek IP address heeft dat compleet onafhankelijk is van van het address van de multicast group waarin de host zit. 128.59.16.20
128.119.40.186
128.34.108.63
mcast group 226.17.30.197 128.34.108.60
Key: Router with attached group member Router with no attached group member
Thehebben multicast bekeken group: A datagram the het group Het RPF broadcast algoritmeFigure dat we4.47 eerder moetenaddressed we iets toom teislaten werken in multicast. delivered to all members of the multicast group Hosts zullen nu namelijk broadcast berichten doorsturen routers waaraan geen hosts zijn aangesloten die in de multicast group zitten. Op zich is dit niet zo erg, maar als er heel veel van deze routers zijn, ontvangen heel veel routers onnodig Internet Group Management Protocol dit bericht. Dit willen we voorkomen. Dit doen we d.m.v. pruning. Indien een multicast router een multicast packet The IGMP protocol version [RFC 3376] operates hosteen and its directlymessage naar de upstream ontvangt en het heeft geen verbonden hosts die in die 3group zitten, danbetween stuurt ahet prune attached router (informally, we can think of the directly attached router as the firstrouter. Als een router een prune message van see eenondownstream router, stuurt hop router ontvangt that a host would a path to any other host outside its het own een local prune message upstream.
network, or the last-hop router on any path to that host), as shown in Figure 4.48. Figure 4.48 shows three first-hop multicast routers, each connected to its attached hosts via one outgoing local interface. This local interface is attached to a LAN in this example, and while each LAN 29has multiple attached hosts, at most a few of these hosts will typically belong to a given multicast group at any given time. IGMP provides the means for a host to inform its attached router that an application running on the host wants to join a specific multicast group. Given that the scope of IGMP interaction is limited to a host and its attached router, another protocol is clearly required to coordinate the multicast routers (including the attached routers) throughout
Column parity
scheme, the sender simply onethe additional bit and chooses its errors value such “bursts.” Under burst error includes conditions, probability of undetected in a that the total number of 1s in the d + 1 bits (the original information plus parity frame protected by single-bit parity can approach 50 percent [Spragins a1991]. bit) is even. Forrobust odd parity schemes, thescheme parity is bitneeded value is(and, chosen such that is there Clearly, a more error-detection fortunately, usedis an odd number of 1s. Figure 5.4 illustrates an even parity scheme, with the single in practice!). But before examining error-detection schemes that are used in pracparitylet’s bit being stored in a separate field. tice, consider a simple generalization of one-bit parity that will provide us Receiver operation is also simple with a single parity bit. The receiver need with insight into error-correction techniques. onlyFigure count 5.5 the shows numbera of 1s in the received d + 1 bits. of If an numberparity of 1two-dimensional generalization theodd single-bit 5 H5 valued bits are found with an even parity scheme, the receiver knows that at least scheme. Here, the d bits in D are divided into i rows and j columns. A parity value is one bit error has occurred. More precisely, it knows that some odd number of bit 5.1 Parity Checkcomputed for each row and for each column. The resulting i + j + 1 parity bits comerrorsthe have occurred. prise link-layer frame’s error-detection bits. Met parity checks kunnen Suppose bit worden In een parity scheme de Buterrors whatnow happens if an evenbitnumber ofeven bit errors You should convince 1 extra bit thatgedetecteerd. a single error occurs in theoccur? original dkiest bits ofverzender informazodat de het totale aantal 1s in de data (samen met de parity bit) even is. In een odd parity scheme wordt yourself that this would result in an undetected error. If the probability of bitdeze bit zo tion. With this two-dimensional parity scheme, the parity of both the column gekozen zodat het totaal een oneven aantal 1s heeft. Indien er een oneven nummer van 1s wordt ontvangen errors is small and errors can be assumed to occur independently from one toin een even and the row containing the flipped bit will be in error. The receiver can thusbitnot parity scheme, weet deonly ontvanger dat er ten minste 1 bit error was. Of om preciezer te zien, dat er een oneven aantal the next, the probability of multiple bit errors in a packet would be extremely small. detect the fact that a single bit error has occurred, but can use the column bit errors zijn. Indien het aantal bit errors een even getal is wordt dit niet gedetecteerd. and row indices of the column and row with parity errors to actually identify the Parity bit that was corrupted and correct that error! Figure 5.5 shows an example in
d data bits Row parity
bit
0 1 0d 1 0 1 1 d1,1 0 1 1. .1. 0 0 0d11,1 j 1, j+1
1
...
d2,1
d2, j
d2, j+1
One-bit even parity even parity scheme 20: . . . One-bit . Figure .. ... ... We kunnen dit ook uitbreiden naar two-dimensional parity scheme. Hierin wordt de data opgesplitst in stukken di, j (afhankelijk di, j+1 . . . bepaald van gelijke grootte. Voor elke rij wordt dedi,1 parity bit van de keuze voor een even of odd parity scheme). Idem voor elke kolom. We kunnen nu niet alleen een single bit error detecteren maar ook bepalen welke bit di+1,1 di+1, j di+1, j+1 ... het precies is! Dit doen we door te kijken voor welke rij en kolom de parity niet overeenkomt. Waar deze twee elkaar kruisen zit de bit die niet correct is. We kunnen dit echter niet voor meer dan 1 bit doen. Zie het onderstaande plaatje voor een voorbeeld: Figure 5.4
No errors
Correctable single-bit error
1 0 1 0 1 1
1 0 1 0 1 1
1 1 1 1 0 0
1 0 1 1 0 0
0 1 1 1 0 1
0 1 1 1 0 1
0 0 1 0 1 0
0 0 1 0 1 0
Parity error
Parity error
Figure 5.5
5.2
Figure 21: 2D evenparity parity scheme Two-dimensional even
CRC
Een andere manier van error detection is CRC. Alle berekeningen van CRC kunnen worden beschouwd als XOR. Beide partijen (verzender en ontvanger) kiezen eerst een r C 1 bit generator G. De meest significante bit van G moet 1 zijn. De verzender kiest r extra bits R en plaatst deze achter D zodat de d C r bits precies deelbaar zijn door G (dit houdt in: geen rest) modulo 2. De ontvanger kijkt als het ontvangen bericht deelbaar is door G. Als er geen rest is, dan is er geen sprake van bit errors. Anders zitten er errors in de data. We kiezen R als volgt: D 2r (1) G De bovenstaande berekening kan uitgevoerd worden met een staartdeling. Merk op dat het vermenigvuldigen van een binair getal met 2r hetzelfde is als een bit shift van r bits naar links (ofwel, voeg rechts van het binaire getal r nullen toe). Zie de opdrachten voor een uitwerking en het volgende figuur: R D remainder
30
5.3
G 1 0 0 1
MULTIPLE ACCESS LINKS AND PROTOCOLS
•
1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 1
1 1 0 0 0 0
1 0 0 0 0 1 0 1 0 1 0 1 1
D 0 1 1 0 1 0 1 1
0 0 0 0 0 0
0 1 1 0 0 1
0 1 1 R
5.3
Figure 5.7 A sample CRC calculation Multiple Acces Protocols
Hoe regelen de toegang van meerdere versturende en ontvangende nodes naar een gedeeld broadcast channel? Dit behind CRCgenoemd. codes andHieronder even morebeschrijven powerful codes is beyond theklassen scope ofvan thischannel text. The wordt het multiple acces problem de verschillende partitioning 1980]wordt provides excellent introduction to this protocollen. CDMA istext hier[Schwartz 1 van, maar pas an later besproken. We gaan hettopic. nu hebben over random acces protocols. Iedere node verstuurt zijn data met de maximale bandbreedte. Indien er een collision optreedt, verzendt elke node die betrokken was bij de collision zijn data opnieuw totdat zijn frame wel verzonden wordt We hebben verschillende protocollen:
5.3 Multiple Access Links and Protocols
Slotted ALOHA: tijd wordt verdeeld in slots. Wanneer zijn slot begint mag een host data versturen. Indien er In theprobeert introduction to this we noted aretetwo types ofmet network links:van p. De een collision optreedt de node in chapter, de volgende slotsthat zijnthere packet versturen een kans 1 point-to-point links and heeft broadcast A point-to-point linkisconsists ofNa single kans dat een node succes met versturen als erlinks. N nodes in het totaal zijn p.1 p/ . De kans dat een willekeurige sender node succes is NP . De moeten deother p zoeken NP .1 p/N 1 at oneheeft end of the .1 link p/ andN a 1single receivereerst at the end ofwaarvoor the link. Many maximaal is. Dit link-layer doen we door de afgeleide te berekenen en point-to-point de nulpunten hiervan te point-to-point vinden. Dit geeft protocols have been designed for links; the pro-p D 1=n N 1 Vervolgens vullentocol we deze we het limiet van Np(HDLC) .1 p are / two . Dit een maximale (PPP)berekenen and high-level data link control suchgeeft protocols that we’lleffici¨entie van 1=e. cover later in this chapter. The second type of link, a broadcast link, can have multiple sending and receiving nodes all connected to the same, single, shared broadcast chan ALOHA: in ALOHA wordt een beschikbaar packet er een collision optreedt nel. The term broadcast is used heremeteen becauseverstuurd. when anyIndien one node transmits a frame, the verstuurd de node het packet meteen nadat het helemaal verzonden is. channel broadcasts the frame and each of the other nodes receives a copy. Ethernet and wireless LANs areMultiple examplesAcces) of broadcast In this section we’ll CSMA: In CSMA (Carrier Sense wacht link-layer een node technologies. totdat de transmissie van een andere node take a step back from specific link-layer protocols and first examine a problem of cenvoorbij is voordat hij zelf begint met versturen. Dit wordt ook wel carrier sense genoemd. tral importance to the link layer: how to coordinate the access of multiple sending and receiving nodes to a shared broadcast channel—the multiple access problem. Broadcast channels are often used in LANs, networks that are geographically concentrated in a single building (or on a corporate or university campus). Thus, we’ll also look at how multiple access channels are used in LANs at the end of this section.
31
445
and fundamental, characteristics of CSMA and CSMA/CD. The first question that you might ask about CSMA is why, if all nodes perform carrier sensing, do collisions occur in the first place? After all, a node will refrain from transmitting whenever it senses that another node is transmitting. The answer to the question can best be illustrated using space-time diagrams [Molle 1987]. Figure 5.12 shows a space-time diagram of four nodes (A, B, C, D) attached to a linear broadcast bus. The horizontal axis shows the position of each node in space; the vertical axis represents time. Space A
B
C
D
t0 t1
Time
Time
Figure 5.12 Space-time diagram of two CSMA nodes with colliding
Figure 22: Een voorbeeld van CSMA intransmissions werking. Op t0 en t1 versturen A en D iets. Omdat de er ruimte tussen hen zit, duurt het voordat A hoort dat D iets aan het versturen is en vice versa. De tijd die dit in beslag neemt wordt de channel propegation delay genoemd CSMA/CD: in CSMA is er nog geen sprake van collision detection. Dat is in CSMA/CD (CD staat voor collision detection) wel. Als in CSMA/CD iemand anders op het zelfde moment iets aan het versturen is terwijl jij ook iets verstuurd stop je meteen met versturen. Dit wordt gedaan door te kijken naar de signal energy van andere nodes. Indien het hele packet is verstuurd zonder dat er signal energy is gedetecteerd gedurende transmissie nemen we aan dat het versturen is gelukt. Als er sprake van een collision is wordt een random tijd gewacht en wordt daarna weer geprobeerd om het packet te versturen. Hiervoor wordt het binary exponential backoff algoritme gebruikt. Als een frame al n collisions heeft gehad, dan wordt een random waarde457 K gekozen 5.3 • MULTIPLE ACCESS LINKS AND PROTOCOLS uit f0; 1; 2:::2n 1g. Dus hoe meer collisions een frame heeft gehad, hoe langer het wacht. In Ethernet wordt er dan 512 K gewacht (de tijd om 512 K bits te versturen). n wordt begrensd door 10. Space A
B
C
D
t0 t1
Collision detect/abort time
Time
Time
Figure 5.13 CSMA with collision detection
Figure 23: CSMA met Collision Detection. Er zijn ook Taking-Turns protocols: The need to wait a random (rather than fixed) amount of time is hopefully clear—if two nodes transmitted frames at the same time and then both waited the same fixed
polling protocol: hierin is amount e´ e´ n node de they’d master node.colliding De master pollsis elke op een round-robin manier. of time, continue forever.node But what a goodnode interval of choose the random backoff time? If the interval is large Hierin wordt telkens gezegdtime datfrom de which nodetowat mag versturen. Vervolgens gaat het and door naar de volgend node. the number of colliding nodes is small, nodes are likely to wait a large amount of time (with the channel remaining idle) before repeating the sense-and-transmitwhen-idle step. On the other hand, if the interval is small and the number of colliding nodes is large, it’s likely that the32 chosen random values will be nearly the same, and transmitting nodes will again collide. What we’d like is an interval that is short when the number of colliding nodes is small, and long when the number of colliding nodes is large. The binary exponential backoff algorithm, used in Ethernet as well as in
Dit gaat zo door. Dit protocol heeft te maken met een polling delay: de tijd die nodig is om aan te geven dat een node data kan versturen. toking-passing protocol hierin wordt telkens een token doorgegeven tussen de hosts. Indien je het token in bezit hebt, mag je wat versturen. Daarna geef je het door aan de volgende node.
5.4
Switched LAN
Een link layer adres wordt ook wel een MAC adres genoemd. Deze worden meestal opgeschreven in hexadecimale notatie. Een MAC adres is 6 bytes lang. Per byte wordt dit aangegeven door een paar van hexadecimale waarden. Indien een adapter iets wil verzenden naar alle andere adapters verstuurd het het packet naar een MAC broadcast address (meestal FF-FF-FF-FF-FF). Hierdoor ontvangen alle andere adapters het packet ook.
5.5
ARP
Om de mapping tussen een MAC adres en een IP adres te bepalen bestaat er het protocol ARP (Address Resolution Protocol). Indien het ip adres nog niet gekoppeld is aan een MAC adres, wordt er ARP message met als destination address MAC broadcast address verstuurd. Alle andere andere adapters ontvangen dit pakketje. Indien het IP adres van de adapter matched met het ip dat in de ARP packet zit, dan antwoord de adapter met zijn MAC adres. Hierdoor kan van een IP het bijbehorende MAC adres gevonden worden!
5.6
Link-Layer Switches
Een switch bevat een switch table. Deze bevat een MAC address, interface en Time. Er zijn drie mogelijkheden voor switching indien er een packet wordt ontvangen met destination address DD-DD-DD-DD-DD-DD op interface x: Er is geen entry voor DD-DD-DD-DD-DD-DD in de switch table. In dit geval wordt het packet naar alle interfaces verstuurd, behalve interface x. Er is een entry in de table die x associeert met DD-DD-DD-DD-DD-DD. In dit geval komt het frame van een LAN segment die de adapter DD-DD-DD-DD-DD-DD bevat. Er is dus geen reden om de frame te forwarden. Het frame wordt discard. Er is een entry die DD-DD-DD-DD-DD-DD koppelt aan interface y ¤ x. In dit geval wordt het frame geforward naar interface y. Een switch is ook self-learning. Dit houdt in dat de tabel automatisch wordt aangepast. Dit werkt als volgt: 1. Initieel is de tabel leeg 2. Voor elk ontvangen frame op een interface slaat de switch het MAC adres in het source field (1), het interface waarvan het packet kwam (2) en de huidige tijd (3) op. 3. Als geen frames worden ontvangen met een source address dan verdwijnt na een bepaalde tijd (aging time) de entry voor dit source address.
5.7
VLAN
M.b.v. VLANs kunnen we meerdere virtual local area networks worden gemaakt over e´ e´ n physical local area network. Hosts binnen een VLAN communiceren met elkaar alsof ze waren verbonden met de switch. Broadcast traffic bereikt alleen alle andere hosts binnen een VLAN. Hoe kunnen VLANs nou data naar elkaar versturen? Een oplossing is VLAN trunking. Een speciale poort wordt geconfigureerd om twee VLANs met elkaar te verbinden. Hoe weten we nu als zo’n pakketje bedoelt is voor het andere VLAN? Hiervoor bestaat een speciaal formaat genaamd 802.1Q. Deze bevat een 4 byte extra VLAN tag. Een andere oplossing is om de twee poorten fysiek met elkaar te verbinden, maar dit schaalt niet.
33
2 to 8 belong to the EE VLAN, while ports 9 to 15 belong to the CS VLAN (ports 1 and 16 are unassigned). This VLAN solves all of the difficulties noted above— EE and CS VLAN frames are isolated from each other, the two switches in Figure 5.15 have been replaced by a single switch, and if the user at switch port 8 joins the CS Department, the network operator simply reconfigures the VLAN software so that port 8 is now associated with the CS VLAN. One can easily 1
1 8
16
5.4
a.
SWITCHED LOCAL AREA NETWORKS
• 9
15
10
16
1 2
1
8
9
1
2
4
4
8
Electrical Engineering16 10 (VLAN ports 2– 8)
485
15
1 Trunk
1
3
5
7
16
link Science Computer (VLAN ports 9–15)
2
48
6
8
Figure 5.25 A single switch with two configured VLANs
a.
Figure 24: Twee VLANs in een switch
Electrical Engineering (VLAN 1ports 2– 8) 2 4 b.
Figure 5.26
9 8
Computer Science 15 Trunk (VLAN ports 9–15)
10
16
link
1 2
Electrical Engineering 3 5 7 (VLAN ports 2, 3, 6) 4
6
Computer Science (VLAN ports 4, 5, 7)
8
Connecting two VLAN switches with two VLANs: (a) two cables (b) trunked
Electrical Engineering (VLAN ports 2– 8) b.
Electrical Engineering (VLAN ports 2, 3, 6)
Computer Science (VLAN ports 9–15)
Computer Science (VLAN ports 4, 5, 7)
Figure 5.26 Connecting two VLAN switches with two VLANs: (a) two Figure 25: VLAN trunking cables (b) trunked Type Preamble
Dest. address
Source address
Data Type
Type Preamble Preamble
Dest. Dest. address address
CRC
Source Source address
Data
address
CRC
CRC'
Data
Type
Preamble
Dest. address
Source address
Tag Control Information Tag Protocol Identifier Data
CRC'
Recomputed CRT
Recomputed Tag Control Information Figure 5.27 Original Ethernet frame (top), 802.1Q-tagged Ethernet CRT frame (onder) Tag Protocol Identifier Figure 26: Origineel Ethernet frame (boven), 802.1Q-tagged Ethernet VLAN VLAN frame (below)
6 6.1
H6
Figure 5.27 Original Ethernet frame (top), 802.1Q-tagged Ethernet VLAN frame (below)
CDMA
CDMA werkt als meerdere mensen tegelijkertijd iets versturen. Elke bit wordt gecodeerd door deze te vermenigvuldigen met een code voordat deze wordt verzonden. Een 0 wordt hierbij met een -1 gerepresenteerd. De code bestaat uit allemaal waardes van -1 of +1. De verzender berekent voor de bit di de multiplicatie met cm waarbij m 2 f0; M g met M de grootte van de code. We noteren Zi;m D di cm voor bit i . De ontvanger ontvangt Zi;m . Bit di is nu gelijk aan 1 PM di D M mD1 Zi;m cm . Zie het voorbeeld hieronder:
34
6.2
WIRELESS LINKS AND NETWORK CHARACTERISTICS
•
Sender
Channel output Zi,m Zi,m = di • cm
d0 = 1 d1 = -1
Data bits
523
-1 -1 -1 Code 1 1 1
1
Time slot 1
-1
-1
-1 -1 -1
1
1 1 1 -1 -1 -1
-1
1
1 1 1 1 1 1
1
Time slot 1 channel output
-1 -1 -1
-1
Time slot 0 channel output
Time slot 0
Receiver
M
∑ Zi,m
•
cm
m= 1
M d0 = 1
-1 -1 -1
-1
-1
-1 -1 -1
di =
1
1 1 1 1 1 1
1
d1 = -1 Time slot 1 received input Code 1 1 1
1 -1
Time slot 0 received input 1
1 1 1 -1 -1 -1
-1
-1 -1 -1
A simple CDMA example: receiver Figure 27:sender CDMAencoding, met 1 verzender decoding We voeren de berekening uit: Figure 6.5
PM di D
mD1 Zi;m cm
M 1value. 1 1 In 1 the 1 example 1 C 1 1in 1Figure 1 C 1 6.5, 1C 1 M-bit 1 C 1CDMA 1 code 8 being used by the the d1 D D D 1 8 8 sender is (1, 1, 1, –1, 1, –1, –1, –1). 1 1 C 1To 1illustrate C 1 1 1how 1CDMA C 1 1 works, 1 1 let1us focus 1 1 on1the ith 8 data bit, d . For the mth i d2 D D D1 mini-slot of the bit-transmission time of di, the output of the 8 8 CDMA encoder, Zi,m, is the value of di multiplied by the mth bit in the assigned CDMA code, cm: In het geval van meerdere verzenders wordt de data die binnenkomt bij de ontvanger gelijk aan de som van alle coderingen. De senders gebruiken verschillende codes. di1 staat voor bit i van sender 1. We kunnen toch dezelfde Zi, m = di cm (6.1) formule toepassen om de bits te achterhalen:
35
6.2
WIRELESS LINKS AND NETWORK CHARACTERISTICS
•
525
Senders 1
d0 = 1 1
Data bits
1
d1 = -1 1
1 1 1
1
1
Z i,m = di • cm 1
1 1 1
* Channel, Zi,m
Code -1 -1 -1
-1
-1 -1 -1
-1
2
2 2 2
2
2
+ -2 2 d1
Data bits
1
2 d0
=1
1 1 1
1 1 1
=1
1 1 1
1 1
2
-1
-1
2
2
Z i,m = di • cm
Code -1
-2
-1
Receiver 1
M
* ∑ Zi,m 2 2 2
2
2
1
di =
2
-2
•
1
cm
m= 1
M
Time slot 1 received input
1
1 1 1
1
d0 = 1
-2
1 d1
= -1
Time slot 0 received input
1
1 1 1
Code -1
-1 -1 -1
-1
-1 -1 -1
Figure 6.6 A two-sender CDMA example
Figure 28: CDMA met meerdere senders We voeren de berekening uit voor Receiver 1: Our discussion here of CDMA is necessarily brief; in practice a number of difficult issues must be addressed. First, in order for the CDMA receivers to be 1 to extract a particular sender’s signal, the CDMA codes must be carefully able mD1 Zi;m cm chosen. Second, our discussion has assumed that the received signal strengths
PM di1 D
M 21C01C2 1C01C0 1C2 1C2 1 8 D D D 1 8 8 8 21C01C21C0 1C21 2 1C0 1C0 1 d01 D D D1 8 8 d11
01
6.2
802.11 MAC Protocol
Wireless LANs maken gebruik van CSMA/CA, wat staat voor CSMA met collision avoidance. CSMA stond voor carrier sense multiple acces. Het werkt als volgt: 1. Als een station merkt dat de channel idle is, dan verstuurt het zijn frame na een korte tijdsperiode die DIFS wordt genoemd. Dit staat voor Distributed Inter-frame Space. 2. Anders kiest het een random backoff value m.b.v. binary exponential backoff. Deze waarde neemt af als het channel idle is. Het behoudt zijn waarde als het channel busy is. 3. Als de counter nul is, verstuurt het station het gehele frame en wacht voor een acknowledgement. 4. Als er een acknowledgement wordt ontvangen, dan weet het station dat het frame correct is ontvangen. Indien er nog meer moet worden verstuurd gaat het terug naar stap 2. Als er geen ACK werd ontvangen gaat het station terug in de backoff fase met een random value gekozen uit een groot interval. 36
2. Otherwise, the station chooses a random backoff value using binary exponential backoff (as we encountered in Section 5.3.2) and counts down this value when the channel is sensed idle. While the channel is sensed busy, the counter value remains frozen. 3. When the counter reaches zero (note that this can only occur while the channel is sensed idle), the station transmits the entire frame and then waits for an acknowledgment.
Source
Destination
DIFS
dat
a
SIFS
ack
Figure 6.10 802.11 uses link-layer acknowledgments
6.3
Hidden Terminal Problem
6.3
•
WIFI: 802.11 WIRELESS LANS
In het figuur hieronder staat een voorbeeld van het hidden terminal problem. Er zijn twee twee wireless stations en e´ e´ n acces point. Beide wireless stations zijn in het bereik van het AP en beide zijn geassocieerd met het AP. Beide wireless stations kunnen elkaar echter niet zien.
H1
AP
H2
Stel dat H1 een frame aan het versturen is, en halverwege deze transmissie wil H2 ook iets versturen. H2 hoort niet Figure 6.11 Hidden hidden H2, dat H1 iets aan het versturen is, wacht een DIFSterminal interval example: en verstuurtH1 hetisframe watfrom een collision veroorzaakt. Om dit and vice versa probleem op te lossen gebruiken Request to Send (RTS) en Clear to Send (CTS) control frames. Als een station iets wil versturen stuurt het eerst een RTS naar het AP, samen met de totale tijd die het nodig heeft om data te versturen. AP antwoordt met een CTS frame. Dit geeft het station toegang om te sturen en geeft aan andere station aan dat het niet mogen sturen. Dus in het bovenstaande voorbeeld stuurt H1 eerst een RTS. AP antwoordt met een CTS, dit wordt gehoord door H2 die nu weet het niet sturen voor de gespecificeerde tijd in het CTS frame.
interiors of the shaded circles shown in Figure 6.11. Thus, each of the wireless stations is hidden from the other, although neither is hidden from the AP. Let’s now consider why hidden terminals can be problematic. Suppose Station H1 is transmitting a frame and halfway through H1’s transmission, Station H2 wants to send a frame to the AP. H2, not hearing the transmission from H1, will first wait a DIFS interval and then transmit the frame, resulting in a collision. The channel will therefore be wasted during the entire period of H1’s transmission as well as during H2’s transmission. In order to avoid this problem, the IEEE 802.11 protocol allows a station to use a short Request to Send (RTS) control frame and a short Clear to Send (CTS) control frame to reserve access to the channel. When a sender wants to send a DATA frame, it can first send an RTS frame to the AP, indicating the total time required to 37 transmit the DATA frame and the acknowledgment (ACK) frame. When the AP receives the RTS frame, it responds by broadcasting a CTS frame. This CTS frame serves two purposes: It gives the sender explicit permission to send and also instructs the other stations not to send for the reserved duration.
535
536
CHAPTER 6
•
WIRELESS AND MOBILE NETWORKS
Source
Destination
All other nodes
DIFS
6.3
•
WIFI: 802.11 WIRELESS LANS
RTS
significantly higher bit rates, but do so at higher frequencies. By operating at a SIFS higher frequency, 802.11a LANs have a shorter transmission distance for a given power level and suffer more from multipath propagation. 802.11g LANs, operatCTS CTS ing in the same lower-frequency band as 802.11b and being backwards compatible with 802.11b (so one can upgrade 802.11b clients incrementally) yet with the SIFS higher-speed transmission rates of 802.11a, allows users to have their cake and eat it too. A relatively new WiFi standard, 802.11n [IEEE 802.11n 2012], uses multipleinput multiple-output (MIMO) antennas; i.e., two or more antennas on the DA TA sending side and two or more antennas on the receiving side that are transmitting/receiving different signals [Diggavi 2004]. Depending on the modulation Defer access scheme used, transmission rates of several hundred megabits per second are possible with 802.11n. SIFS
ACK
ACK
6.3.1 The 802.11 Architecture
6.4
Figure 6.7 illustrates the principal components of the 802.11 wireless LAN architecture. The fundamental building blockusing of the is the basic Figure 6.12 Collision avoidance the 802.11 RTS and architecture CTS frames service set (BSS). A BSS contains one or more wireless stations and a central 802.11 Architecture
The use RTS and CTS frames can improve important De basis voor de 802.11 architecture is of dethebasis service set (BSS). Een performance BSS bevatine´two e´ n of meer wireless stations en ways: een centrale base station die ook wel een acces point (AP) wordt genoemd. • The hidden station problem is mitigated, since a long DATA frame is transmitted only after the channel has been reserved. Internet Switch or router
AP
BSS 1
AP
BSS 2
Wanneer een AS wordt ge¨ınstalleerd, krijgt het een Service Set identifier (SSID) toegewezen. Een Ap stuurt Figuredie6.7 IEEE 802.11 LAN regelmatig beacon frames, het APs SSID bevat en het architecture MAC adres. Het scannen van channels en het luisteren naar beacon frames word ook wel passive scanning genoemd. Bij active scanning stuurt een wireless host een probe frame dat door alle APs die in de range van de host zitten wordt ontvangen. APs reageren hierop met een probe response 38
527
frame. Nu kan de wireless host kiezen met welke AP het zich wil associ¨eren. Nadat het een AP heeft gekozen verstuurd de wireless host een association request frame naar het AP. Het AP antwoordt met een association response frame. Wanneer de wireless host geassocieerd is met het AP, wil het lid worden van het subnet. Het stuurt een DHCP 6.3 • WIFI: 802.11 WIRELESS LANS 531 discovery message in het subnet via het AP om zo een IP address te krijgen op het subnet.
BBS 1
BBS 1
BBS 2
BBS 2
1 1 1
2
AP 1
2 2
3
AP 2
H1
Figure 6.9
4
AP 2
H1
a. Passive scanning 1. Beacon frames sent from APs 2. Association Request frame sent: H1 to selected AP 3. Association Response frame sent: Selected AP to H1
6.5
3
AP 1
a. Active scanning 1. Probe Request frame broadcast from H1 2. Probes Response frame sent from APs 3. Association Request frame sent: H1 to selected AP 4. Association Response frame sent: Selected AP to H1
Active and passive scanning for access points
IEEE 802.11 Frame
538 • Ethernet WIRELESS ANDHet MOBILE Het 802.11 frame CHAPTER lijkt erg op6 een frame. heeft NETWORKS echter ook wat velden die specifiek zijn voor wireless links. Het frame ziet er als volgt uit:
(numbers lengthdefining in bytes):security aspects of the in Section 8.8 thatFrame the new IEEEindicate 802.11ifield protocol 2 takes precisely 2 6 approach. 6 6 2 6 802.11 protocol family this Frame Duration control
Address 1
6.3.2 The 802.11 MAC Protocol
Address 2
Address 3
Seq control
Address 4
0-2312
4
Payload
CRC
Once Frame a wireless station is associated with an AP, it can start sending and receiving control field expanded (numbers indicate field length in bits): data frames to and from the4 access point. But because multiple stations may want1 to 2 2 1 1 1 1 1 1 1 transmit data frames at the same time over the same channel, a multiple access protoProtocol To From More Power More Type Subtype Retry is either a wirelessWEP col is needed a station sta- Rsvd version to coordinate the transmissions. AP AP Here, frag mgt data tion or an AP. As discussed in Chapter 5 and Section 6.2.1, broadly speaking there are three classes of multiple access protocols: channel partitioning (including 6.13 Figure The 802.11 29:by 802.11 frame CDMA), random access,Figure and taking turns. Inspired theframe huge success of Ethernet and its random access protocol, the designers of 802.11 chose a random access protoWat opvalt is dat het frame vier address fields heeft. Deze zijn als volgt gedefinieerd: col for 802.11 wireless LANs. This random access protocol is referred to as CSMA with collision avoidance, or more succinctly as frame CSMA/CA. As with Ethernet’s Address 2 is het MAC adres van het station dat het verstuurd. Als een station dus een frame verstuurd, CSMA/CD, the “CSMA” in CSMA/CA stands for “carrier sense multiple access,” stopt het zijn eigen MAC adres in address field 2. Als een AP het frame verstuurd stopt het zijn MAC adres ook that each inmeaning address field 2. station senses the channel before transmitting, and refrains from typically fewerbusy. than Although 1,500 bytes, holding an and IP datagram or an ARP packet. As with transmitting when the channel is sensed both Ethernet 802.11 use an Ethernet frame, an 802.11 frame includes a 32-bit redundancy check Address 1 is het MAC address van het wireless station dat het frame moet ontvangen. Als een station dus een carrier-sensing random access, the two MAC protocols have important differences.cyclic (CRC) receiver errors in the frame. Asbevat we’ve seen, frame verstuurd bevat address fieldso1that het the MAC adres can van detect het AP.bitAls het AP hetreceived frame verstuurd address bit destination errors are much more common in wireless LANs than in wired LANs, so the field 1 het MAc adres van het wireless station. CRC is even more useful here. Een BSS (bevat een AP en wireless stations) is onderdeel van een subnet. Het kan zijn dat dit subnet met andere subnets is verbonden via een router interface. Address 3 bevat het MAC adres van dit router interface.
Address Fields
Perhaps the most striking difference in the 802.11 frame is that it has four address 39 fields, each of which can hold a 6-byte MAC address. But why four address fields? Doesn’t a source MAC field and destination MAC field suffice, as they do for Ethernet? It turns out that three address fields are needed for internetworking pur-
nets to which it (the router) is connected. • The router, which knows the IP address of H1 (from the destination address of the datagram), uses ARP to determine the MAC address of H1, just as in an ordinary Ethernet LAN. After obtaining H1’s MAC address, router interface R1 encapsulates the datagram within an Ethernet frame. The source address field of this frame contains R1’s MAC address, the destination address Address 4 wordt gebruikt wanneer APs frames naar elkaarand forwarden in ad hoc mode.field Hiercontains gaan we verder niet H1’s MAC address. op in Hieronder staat een voorbeeld:
Internet Router
R1
H1 AP
BSS 1
AP
BSS 2
Figure 30:Figure Het gebruik van address in 802.11 frames: frames worden 6.14 The usefields of address fields in 802.11 frames:verstuurd Sendingtussen H1 en R1 Stel we willen een datagram versturen van de router interface frames between H1 andR1 R1naar H1. Dit gaat als volgt: De router weet het IP address van H1 en gebruikt ARP om het MAC adres van H1 te achterhalen. R1 encapsulates het datagram met een Ethernet frame. Het source address field van dit frame bevat het MAC adres van R1, en het destination address bevat H1’s MAC address. Wanneer het frame aankomt bij het AP, converteert het AP het 802.3 Ethernet frame naar een 802.11 frame voordat het frame weer wordt verstuurd over het wireless channel. Het AP vult voor address 1 het MAC adres van H1 in en voor address 2 zijn eigen MAC adres. Voor Address vult hij het MAC address in van R2. Op deze manier kan H1 aan de hand van address 3 bepalen welke router interface het pakketje in het subnet heeft verstuurd. Wat gebeurt er nu als H1 antwoord en dus een datagram van H1 naar R1 verstuurd. H1 maakt een 802.11 frame, vult voor address 1 het address van het AP en voor address 2 zijn eigen MAC address. Voor address 3 vult hij R1’s MAC address in. Als het AP het 802.11 frame ontvangt, wordt het frame geconverteerd naar een Ethernet frame. Het source address wordt gelijk aan H1’s MAC adres, en het destination wordt gelijk aan R1’s MAC address. Hier wordt het address 3 field gebruikt om het juiste destination address te bepalen (in dit geval het MAC adres van R1).
40
BSS2, it may keep its IP address and all of its ongoing TCP connections. If the interconnection device were a router, then H1 would have to obtain a new IP address in the subnet in which it was moving. This address change would disrupt (and eventually terminate) any on-going TCP connections at H1. In Section 6.6, we’ll see how a network-layer mobility protocol, such as mobile IP, can be used to avoid this problem.
6.6
Mobility
Hoe blijft een TCP connectie bestaan als een wireless node van BSS switched? Switch
BSS 1
AP 1
BSS 2
H1
AP 2
In het bovenstaande plaatje gaat H1 van BSS1 naar BSS2. Alle stations in de twee BSSs (ook de AP) behoren Figure 6.15H1 Mobility in thenaar sameBSS2 subnet tot hetzelfde subnet. Wanneer dus van BSS1 switched mag het al zijn IP address en openstaande TCP verbindingen houden. De switch bevat nu nog een entry die vertelt dat H1 bereikbaar is via AP1. Wanneer H1 geassocieerd is met AP2 (en dus niet meer geassocieerd is met AP1) stuurt AP2 een broadcast Ethernet frame met H1’s source address naar de switch. Wanneer de switch dit frame ontvangt, update het zijn forwarding table waardoor H1 bereikbaar is via AP2.
6.7
Bluetooth
In Bluetooth verstuurt een sender gedurende elk tijdslot iets over e´ e´ n van de 79 channels. Dit channel verandert in een voorspelbare maar pseudo-random manier. Dit wordt ook wel frequency-hopping spread centrum (FHSS) genoemd. Het is een vorm van channel hopping. Omdat er niet sprake is van een infrastructuur organiseren de apparaten zich in een piconet van acht apparaten. Een van de apparaten wordt als master benoemd en de anderen als slave. De master mag in elk oneven slot iets versturen en een slave mag alleen iets versturen als het toestemming heeft van de master. Alsnog mag de slave alleen nog maar in even slots data versturen.
6.8
Cellular Network Architecture
Elk gebied wordt opgedeeld in cells. Elke cell bevat een base transceiver station (BTS) die signalen verstuurt en ontvangt van de mobile stations in die cell. Een base station controller (BSC) biedt service aan meestal meerdere base transceiver stations. De rol van een BSC is om een BTS radio channels toe te wijzen aan mobile subscribers. Dit wordt gedaan m.b.v. paging (vindt de cell waarin de mobile user zich bevindt). Een BSC samen met zijn BTSs vormen samen een base station system (BSS) . Het mobile switching center (MSC) speel teen centrale rol in user authentication, het bepalen als een mobile device toegang heeft tot het netwerk, call establishment, teardown en handoff.
41
lar slot in the revolving frame. In combined FDM/TDM systems, the channel is partitioned into a number of frequency sub-bands; within each sub-band, time is partitioned into frames and slots. Thus, for a combined FDM/TDM system, if the channel is partitioned into F sub-bands and time is partitioned into T slots, then
G
BSC
Public telephone network
Base Station System (BSS)
MSC
Gateway MSC
Key:
Base transceiver station (BTS) Base station controller (BSC)
BSC
Mobile switching center (MSC)
Base Station System (BSS)
Mobile subscribers
Figure 6.18 Components of the cellular network network architecture Figure 31: Componenten vanGSM een 2G GSM 2G cellular architecture 6.4
•
CELLULAR INTERNET ACCESS
551
Het 3G cellular data network is weer anders. Naast het verbinden van voice users aan het publieke telefoon netwerk hebben we in dit netwerk extra functionaliteiten: email lezen, toegang tot het internet, locatie afhankelijke services etc. Het ziet er als volgt uit: Public telephone network
G
Gateway MSC
MSC
G Public Internet Radio Network Controller (RNC)
SGSN
GGSN
Radio Interface (WCDMA, HSPA) Radio Access Network Universal Terrestrial Radio Access Network (UTRAN)
Core Network General Packet Radio Service (GPRS) Core Network
Public Internet
Key: G
Serving GPRS Support Node (SGSN)
Gateway GPRS Support Node (GGSN)
Figure 6.19 3G system architecture
Figure 32: 3G system architecture
Het 3G core cellular data network verbindt radio acces networks met het publieke internet. Er bestaan twee soorten nodes in een 3G netwerk: Serving GPRS Support Nodes (SGSNs) en Gateway GPRS Support Nodes (GGSNs). GPRS staat voor Generalized Packet Radio SGSN is encountered verantwoordelijk network (in particular, theService. MSC) thatEen we previously in Figurevoor 6.18.het afleveren van datagrams van of naar mobile nodes het radio acces network waaraan het SGSN verbonden is. Het Giveninthe considerable amount of existing infrastructure (and profitable services!) in SGSN communiceert met the existing cellular voice network, the approach taken by the designers of 3G data services is clear: leave the existing core GSM cellular voice network untouched, adding additional cellular data functionality in parallel to the existing cellular voice network. The alternative—integrating new data 42 services directly into the core of the existing cellular voice network—would have raised the same challenges encountered
het MSC voor dat gebied. Het beidt de volgende functionaliteiten: user authorization and handoff, het bewaren van cell information en datagram forwarding. Het GGSN verbindt meerdere SGSNs. Boek blz 553...
6.9
Mobility Management
De permanent home van een mobile node wordt een home network genoemd. De entiteit die in dit network die het mobility management op zich neemt wordt de home agent genoemd. Het netwerk waarin de mobile node zich op dit bevindt wordt een foreign (of visited) network genoemd. De foreign agent regelt de mobiliteit voor nodes in dit netwerk. Een correspondent is een entiteit die wil communiceren met een mobile node. De rol van een foreign agent is om een care-of address (COA) voor de mobile node te maken. Er zijn dus twee adressen voor een mobile node: zijn permanent address en zijn foreign address. Er zijn twee soorten van routing: In indirect routing stuurt de correspondent het datagram naar het permanent address van de mobile node. Deze 560 opgevangen CHAPTERdoor 6 •de WIRELESS MOBILE dit NETWORKS wordt home agentAND en forward naar de foreign agent m.b.v. het COA. Hierbij wordt het datagram encapsulated en krijgt als source address de home agent en als destination address het COA. De foreign agent zorgt dat het datagram bij de mobile node aankomt. Home network: 128.119.40/24
Visited network: 79.129.13/24 Mobile node
Permanent address: 128.119.40.186
Permanent address: 128.119.40.186 Care-of address: 79.129.13.2
3
2 Home agent
Wide area network
Foreign agent
1 4
Correspondent
Figure mobilenode node Figure 6.2333: Indirect Indirectrouting routingnaar to aeen mobile In direct routing voorkomen we dat het packet eerst verstuurd moet worden naar de home agent (triangle routing problem). Een correspondent agent leert eerst het COA van de mobile node. Dit kan worden gedaan door de correspondent de agent ditimportant te vragen.function. De correspondent zouis dit ookonzelf hashome another very Its second job to be the kunnen lookout vragen. for arriv-De correspondent agent stuurt vervolgens het datagram direct naar het COA van de mobile node. Er is nu ing datagrams addressed to nodes whose home network is that of the home agent buteen extra protocol nodig tussen de correspondent agent en de home agent. Daarnaast vraagt de correspondent maar that are currently resident in a foreign network. The home agent intercepts these e´ e´ n keer naar het COA van de mobile node. Wat als deze nu van foreign network verandert? We noemen datagrams and then forwards them to a mobile node in a two-step process. The data-de anchor foreign agent degram foreign agent waar de node eerst agent, bevond. Als the de mobile vanCOA foreign network is first forwarded to thezich foreign using mobilenode node’s (step 2 in verandert, stuurt de nieuwe foreign agent het COA naar de anchor foreign agent. Als de anchor foreign Figure 6.23), and then forwarded from the foreign agent to the mobile node (stepagent 3 nu een datagram ontvangt de 6.23). mobile node, forward het dit datagram door gebruik te maken van dit nieuwe invoor Figure COA. It is instructive to consider this rerouting in more detail. The home agent will need to address the datagram using the mobile node’s COA, so that the network layer will route the datagram to the foreign network. On the other hand, it is desirable to leave the correspondent’s datagram intact, since the application receiv43 ing the datagram should be unaware that the datagram was forwarded via the home agent. Both goals can be satisfied by having the home agent encapsulate the correspondent’s original complete datagram within a new (larger) datagram. This larger
564
CHAPTER 6
•
WIRELESS AND MOBILE NETWORKS
Home network: 128.119.40/24
Visited network: 79.129.13/24 Mobile node
Permanent address: 128.119.40.186
Permanent address: 128.119.40.186
4
Home agent
Wide area network
2
3
Foreign agent
Care-of address: 79.129.13.2
1
Correspondent agent Correspondent Key: Control messages Data flow
Figure 6.25 node. Direct routing to a mobile user Figure 34: Direct routing naar een mobile De correspondent agent vraagt naar het COA565 van de mobile 6.6 • MOBILE IP node aan de home agent (1). De home agent antwoordt met het COA (2). De correspondent agent stuurt het the anchor foreign receives an encapsulated a departed mobile datagram naar het COA (3). De foreign agentagent stuurt forward het packetdatagram naar defor mobile node (4). node, it can then re-encapsulate the datagram and forward it to the mobile node (step 5) using the new COA. If the mobile node later moves yet again to a new foreign network, the foreign agent in that new visited network would then contact the Home network: Foreign network anchor foreign agent in order to set up forwarding to this new foreign network. being visited at session start:
6.6 Mobile IP Anchor
2
The Internet architecture and protocols for supportingforeign mobility, collectively known as mobile IP, are defined primarily in RFC 5944 for agent IPv4. Mobile IP is a flexible Wide area Home standard, supporting network many different modes of operation (for example, operation 1 agent 4
5
New foreign network: 3
Correspondent agent Correspondent
New foreign agent
Figure 6.26 Mobile transfer between networks with direct routing
Figure 35: Mobile transfer tussen networks met direct routing. De mobile node wisselt van foreign network (2). De new foreign agent stuurt het COA naar het anchor foreign network. Het datagram met het oude COA wordt verstuurd vanaf de correspondent agent. De anchor foreign agent stuurt het packet dor naar de nieuwe foreign agent (5). with or without a foreign agent), multiple ways for agents and mobile nodes to discover each other, use of single or multiple COAs, and multiple forms of encapsula6.10 Agent Discovery tion. As such, mobile IP is a complex standard, and would require an entire book to describe in detail; indeed one such book is [Perkins 1998b]. Our modest goal here is Als een mobile node in een nieuw netwerk arriveert (foreign network of home network), moet het de identiteit van to provide an overview of the most important aspects of mobile IP and to illustrate het dit netwerk leren Dit noemen we agent discovery. Dit kan op twee manieren worden gedaan. Met agent its kennen. use in a few common-case scenarios. The de mobile IP architecture containsmessage many of the elements have considered advertisement wordt om zoveel tijd een ICMP met type we field van 9 verstuurd op alle links met wie het above, including the concepts of home agents, foreign agents, care-of addresses, and encapsulation/decapsulation. The current standard [RFC 5944] specifies the use of indirect routing to the mobile node. 44 pieces: The mobile IP standard consists of three main • Agent discovery. Mobile IP defines the protocols used by a home or foreign agent to advertise its services to mobile nodes, and protocols for mobile nodes to solicit the services of a foreign or home agent.
verbonden is. Deze router discovery message bevat het IP address van de router. Ook bevat het het volgende: Home agent bit (H). Geeft aan als de agent een home agent is voor het netwerk waarin het zit. Foreign agent bit (F). Geeft aan als de agent een foreign agent is voor het netwerk waarin het zit. Registration required bit (R). Geeft aan dat een mobile user in dit netwerk zich moet registreren met een foreign agent. M, G encapsulation bits. Geven aan als een andere vorm van encapsulation dan IP-in-IP encapsulation wordt gebruikt. COA fields. Een lijst van e´ e´ n of meer adressen afkomstig van de foreign agent. Een andere manier is agent solicitation. Hierin stuurt de mobile node een agent solicitation message om zo meer te weten te komen over de agent. Indien een agent dit ontvangt stuurt het een agent advertisement alleen naar deze node. Als een mobile node een COA heeft gekregen, moet dit adres geregistreerd worden bij de home agent. Dit gaat als volgt: 1. De mobile node stuurt een mobile IP registration message naar de foreign agent (in de vorm van foreign agent advertisement). Dit bericht bevat het COA die de foreign agent had voorgesteld, het address van de home agent (HA), het permanent address van de mobile node (MA) en nog wat andere dingen. 2. De foreign agent ontvangt dit registration message en slaat het permanent IP van de mobile node op. Indien het nu een packet binnenkrijgt met een IP adres dat gelijk is aan het permanent IP address van de mobile node, dan forward het het packet naar de mobile node. De foreign agent stuurt dan een IP registration message naar de home agent van de mobile node. Deze message bevat COA, HA, MA ... 3. De home agent ontvangt dit bericht, bindt vervolgens de mobile node zijn permanent IP address met het COA. Pakketjes die als dest COA worden doorgestuurd naar dit address. de home agent stuurt een IP registration reply die de HA, MA ... bevat. 4. De foreign agent ontvangt de reply en stuurt deze door naar de mobile node.
6.11
Managing mobility in Cellular Networks
De manier waarop GSM mobility regelt lijk op die van IP. Het home network wordt het home public land mobile network genoemd (PLMN) ofwel home network. Het bezochte netwerk wordt het visited network genoemd. Het home location register (HLR) bevat het permanent cell phone number van elke subscriber. Een speciale switch genaamd Gateway Mobile services Switching Center (GMSC) wordt geraadpleegd door een correspondent wanneer iemand de mobile user wil bellen. We deze switch af tot home MSC. Het bezochte netwerk houdt een database bij die het visitor location register (VLR) wordt genoemd. Het VLR bevat een entry voor elke mobile user die op dit moment in dat netwerk zit. 6.11.1
Routing Calls to a Mobile user
1. De correspondent belt het nummer van de mobile user. Dit nummer wordt gebruikt om het home network van mobile user te bepalen. Het gesprek gaat van de correspondent door het PSTN naar het home MSC in het mobile home network. PSTN staat voor public switched telephone network. 2. De home MSC ontvangt het gesprek en vraagt aan het HLR wat de locatie van de mobile user. Indien het HLR het antwoord weet antwoordt het met een mobile station roaming number (MSRN) (we moeten dit vanaf nu roaming number). Dit is niet gelijk aan het telefoonnummer. Het heeft dezelfde rol als het COA (care-of address) in IP. Indien HLR het roaming nummer niet heeft, returnt het het adres van het VLR van het bezochte netwerk. Het home MSC stuurt nu een query naar het VLR om het roaming nummer te krijgen. 3. Nu het home MSC het roaming nummer heeft, wordt het gesprek gekoppeld aan het MSC waarin de mobile user zich nu bevindt. Op dit moment is het gesprek opgezet. 45
Een handoff treedt op wanneer een mobile station van base station verandert gedurende een gesprek. Dit wordt als volgt afgehandeld (indien het MSC gedeeld is): 1. Het oude base station (BS) informeert het bezochte MSC dat er een handoff gaat worden uitgevoerd en geeft aan welke BS (of meerdere) de taak van het oude BS gaat overnemen 2. Het bezochte MSC informeert het nieuwe BS dat er een handoff gaat plaatsvinden. 3. Het nieuwe BS alloceert en activeert een radio channel die de mobiel kan gebruiken. 4. Het nieuwe BS geeft zowel aan het MSC als aan het oude BS dat de mobile ge¨ınformeerd kan worden over de wisseling van BS. 5. De mobile krijgt te horen dat het een handoff moet uitvoeren. 6. De mobile en het nieuwe BS versturen e´ e´ n of meerdere berichten om het nieuwe channel in het nieuwe BS te activeren.
574
7. De mobile stuurt een handoff complete message naar het nieuwe BS, die wordt geforward naar het bezochte MSC. Het gesprek wordt nu geforward via het nieuwe BS. CHAPTER 6
•
WIRELESS AND MOBILE NETWORKS
8. De geaccordeerde resources van de voorgaande call worden vrijgemaakt in het oude BS.
VLR
2 4 1 8
Old BS
5
7
3
6
New BS
Figure 6.31 Steps in accomplishing a handoff between base stations Figure 36: Benodigde stappen in het volbrengen van een handoff tussen twee base stations met een gedeelde MSC with a common MSC Wat als het MSC hetzelfde is voor beide base stations? Een anchor MSC is het MSC dat de mobile bezocht toen het gesprek begon. Het anchor MSC verandert dus nooit gedurende een gesprek. Wanneer een mobile van MSC 7. The mobile sends a handoff complete message to the new BS, which is forverandert, wordt het gesprek rerouted van het anchor MSC naar het nieuw bezochte MSC. Op elk moment zijn er dus warded up to the visited MSC. The visited MSC then reroutes the ongoing call maar drie MSCs tussen de correspondent en de mobiel: het home MSC, het anchor MSC en het bezochte MSC. to the mobile via the new BS. 8. The resources allocated along the path to the old BS are then released. Let’s conclude our discussion of handoff by considering what happens when the mobile moves to a BS that is associated with a different MSC than the old BS, and what happens when this inter-MSC handoff occurs more than once. As shown in Figure 6.32, GSM defines the notion of an anchor MSC. The anchor MSC is the MSC visited by the mobile when a call first begins; the anchor MSC thus remains unchanged during the call. Throughout the call’s duration and regardless of the number of inter-MSC transfers performed by the mobile, the call is routed from the home MSC to the anchor MSC, and then from the anchor MSC to the visited MSC where the mobile is currently located. When a mobile moves from the coverage area of one MSC to another, the ongoing call is rerouted from the anchor MSC to the new visited MSC containing the new base station. Thus, at all times there are at most three MSCs (the home MSC, the anchor MSC, and the visited MSC) between the correspondent and the mobile. Figure 6.32 illustrates the routing of a call among the MSCs visited by a mobile user. Rather than maintaining a single MSC hop from the anchor MSC to the current MSC, an alternative approach would46 have been to simply chain the MSCs visited by the mobile, having an old MSC forward the ongoing call to the new MSC each time the mobile moves to a new MSC. Such MSC chaining can in fact occur in IS-41 cellular networks, with an optional path minimization step to remove MSCs between the
6.8
Home network
•
WIRELESS AND MOBILITY: IMPACT ON HIGHER-LAYER PROTOCOLS
Home network
Correspondent
Anchor MSC
575
Correspondent
Anchor MSC PSTN
PSTN
a. Before handoff
b. After handoff
Figure 37: Rerouting via het anchor MSC Figure 6.32 Rerouting via the anchor MSC
7
H8
7.1
IPsec Wireless and Mobility: Impact on Higher6.8
Layer Protocols IP sec beidt security op de network layer. Het beveiligt IP datagrams tussen elke twee network-layer entiteiten (ook tussen hosts en routers). Er zijn twee protocollen in IPsec: In this chapter, we’ve seen that wireless networks differ significantly from their wired counterparts Authentication Header (AH): authentication, data integritysuch maar at both the link layer AH (as abiedt resultsource of wireless channel characteristics asgeen confidentiality. fading, multipath, and hidden terminals) and at the network layer (as a result of mobile users Encapsulation Payload (ESP): to biedt source authentication, data integrity who changeSecurity their points of attachment the network). But are there important dif- en confidentiality. ferences at the transport and application layers? It’s tempting to think that these differEr zijn ook twee soorten modes: ences will be minor, since the network layer provides the same best-effort delivery both wired wirelessalsnetworks. Similarly, service tunnelmodel mode:toinupper tunnellayers modeinwordt zoweland de header de payload van hetifIPprotodatagram encrypted. cols such as TCP or UDP are used to provide transport-layer services to applications in both transport mode: in transport mode alleen delayer payload encrypted. wired and wireless networks, thenwordt the application should remain unchanged as well. In one sense our intuition is right—TCP and UDP can (and do) operate in networks Erwith zijnwireless dus vierlinks. combinaties mogelijk. De meest gebruikte is Tunnel with ESP. EEn security association On the other hand, transport protocols in general, andmode TCP in partic(AS) is een channel van een sending naar een receiving entiteit. Het is een one direction channel. Een IPsec 8.7performance • NETWORK-LAYER SECURITY: AND VIRTUAL PRIVATE NETWORKS 723 datagram ular, can sometimes have very different in wired andIPSEC wireless networks, ziet erand alsitvolgt uit: is here, in terms of performance, that differences are manifested. Let’s see why. Recall that TCP retransmits a segment that is either lost or corrupted on the path “Enchilada” authenticated between sender and receiver. In the case of mobile users, loss can result from either Encrypted
New IP header
ESP header
SPI
Original IP header
Original IP datagram payload
Seq #
Padding
ESP trailer
ESP MAC
Pad length
Next header
Figure 8.29 IPsec datagram format
Figure 38: IPsec datagram
that the ESP trailer consists of three fields: padding; pad length; and next header. Recall that block ciphers require the message to be encrypted to be an integer multi47 ple of the block length. Padding (consisting of meaningless bytes) is used so that when added to the original datagram (along with the pad length and next header fields), the resulting “message” is an integer number of blocks. The pad-length field indicates to the receiving entity how much padding was inserted (and thus needs to be removed). The next header identifies the type (e.g., UDP) of data contained in the