Question? Leave a message!

Complete guide to Computer Networking

Complete Guide TO COMPUTER NETWORKS and lectures notes on computer networks | download free pdf
TomTheron Profile Pic
Published Date:09-07-2017
Website URL
f y a d e t m erv f ual Last updated: June 11, 2013 U T O P C E R O R E N K S W nc ncee i P ce e Ivan Marsic r r o a n Q Q i o S Chapter 1 Introduction to Computer Networks Contents 1.1 Introduction 1.1.1 The Networking Problem 1.1.2 Commu nication Protocols 1.1.3 Packets and Statistical Multiplexing 1.1 Introduction 1.1.4 Communication Protocols 1.2 Reliable Transmission via Redundancy 1.2.1 Error Detection and Correction by Channel Coding A network is a set of devices (often referred to as nodes) 1.2.2 Interleaving 1.2.3 x connected by communication links that are built using different physical media. A node can be a computer, telephone, or any 1.3 Reliable Transmission by Retransmission other device capable of sending and receiving messages. The 1.3.1 Stop- and-Wait 1.3.2 Sliding-Windo w Protocols communication medium is the physical path by which message 1.3.3 Broadcast Links travels from sender to receiver. Example media include fiber-optic 1.3.4 x cable, copper wire, or air carrying radio waves. 1.4 Routing and Addressing 1.4.1 Networks, Internets, and the IP Protocol 1.4.2 Link State Routing 1.4.3 Distance Vector Routing 1.1.1 The Networking Problem 1.4.4 IPv4 Address Structure and CIDR 1.4.5 Autonomous Systems and Path Vector Routing Networking is about transmitting messages from senders to 1.5 Link- Layer Protocols and Technologies 1.5.1 Point-to-Point Protocol (PPP) receivers (over a “communication channel”). Key issues we 1.5.2 Ethernet (IEEE 802.3) encounter include: 1.5.3 Wi-Fi (IEEE 802.11)  “Noise” damages (corrupts) the messages; we would like 1.6 Quality of Service Overview 1.6.1 Performance Bounds and Quality of to be able to communicate reliably in the presence of Service noise 1.6.2 Network Neutrality and QoS Outlook  Establishing and maintaining physical communication 1.7 Summar y and Bibliographical Notes lines is costly; we would like to be able to connect Problems arbitrary senders and receivers while keeping the economic cost of network resources to a minimum  Time is always an issue in information systems as is generally in life; we would like to be able to provide expedited delivery particularly for messages that have short deadlines 1 Ivan Marsic  Rutgers University 2 Visible network properties: Delivery Correctness Fault tolerance Timeliness Cost Customer Tunable network parameters: Network Communication Network Physical Components topology protocols architecture medium Network Engineer Figure 1-1: The customer cares about the visible network properties that can be controlled by the adjusting the network parameters. Figure 1-1 illustrates what the customer usually cares about and what the network engineer can do about it. The visible network variables (“symptoms”), easily understood by a non-technical person include: Delivery: The network must deliver data to the correct destination(s). Data must be received only by the intended recipients and not by others. Correctness: Data must be delivered accurately, because distorted data is generally unusable. Timeliness: Data must be delivered before they need to be put to use; else, they would be useless. Fault tolerance and cost effectiveness are important characteristics of networks. For some of these parameters, the acceptable value is a matter of degree, judged subjectively. Our focus will be on network performance (objectively measurable characteristics) and quality of service (psychological determinants). Limited resources can become overbooked, resulting in message loss. A network should be able to deliver messages even if some links experience outages. The tunable parameters (or “knobs”) for a network include: network topology, communication protocols, architecture, components, and the physical medium (connection lines) over which the signal is transmitted. Chapter 1  Introduction to Computer Networking 3 Node Link Centralized Decentralized Distributed (a) (b) (c) Figure 1-2: Differ ent network topologies have different robustness characteristics relative to the failures of network elements. - Connection topology: completely connected graph compared to link sharing with multiplexing and demultiplexing. Paul Baran considered in 1964 theoretically best architecture for survivability of data networks (Figure 1-2). He considered only network graph topology and 1 assigned no qualities to its nodes and links . He found that the distributed-topology network which resembles a fisherman’s net, Figure 1-2(c), has the greatest resilience to element (node or link) failures. Figure 1-3 s hows the actual topology of the entire Internet (in 1999). This topology evolved over several decades by incremental contributions from many independent organizations, without a “grand plan” to guide the overall design. In a sense, one could say that the Internet topology evolved in a “self-organizing” manner. Interestingly, it resembles more the decentralized-topology network with many hubs (Figure 1-2(b)), and to a lesser extent the distributed topology (Figure 1-2(c)). A possible reason may be that, because groups of nodes belong to different organizations (“administrative domains”), it is easier to manage cross-border issues through one or few designated nodes. If the whole Internet developed organically, all nodes had about equal capabilities, and there were enough human resources to manage each node, then one could speculate that the distributed model would have prevailed. 1 When discussing computer networks, the term “host” is usually reserved for communication endpoints and “node” is used for intermediary computing nodes that relay messages on their way to the destination. Ivan Marsic  Rutgers University 4 Figure 1-3. The map of the connections between the major Internet Service Providers (ISPs). From the Internet mapping project: - Network architecture: what part of the network is a fixed infrastructure as opposed to being ad hoc built for a temporary need - Component characteristics: reliability and performance of individual hardware components (nodes and links). Faster and more reliable components are also more costly. When a network node (called switch or router) relays messages from a faster to a slower link, a congestion and a waiting-queue buildup may occur under a heavy traffic. In practice, all queues have limited capacity of their “waiting room,” so the loss occurs when messages arrive at a full queue. A lost message will never reach its destination; if the message is important, countermeasures must be taken to prevent or mitigate the loss (Sections 1.2 an d 1.3) - Performance metrics: success rate of transmitted messages (or, message loss rate), average delay of message delivery, and delay variability (also known as “jitter”) - Different applications (data/voice/multimedia) have different requirements for network service in order to be useful to human users: some applications are impaired by message loss and others are impaired by delay or jitter There are some major problems faced by network engineers when building a large-scale network, such as the Internet that is now available worldwide. Some of these problems are non-technical: Chapter 1  Introduction to Computer Networking 5 Voltage at transmitting end Idealized voltage at receiving end Line noise Voltage at receiving end Figure 1-4: Digital signal distortion in transmission due to transients and noise associated with physical lines. - Heterogeneity: Diverse software and hardware of network components need to coexist and interoperate. The diversity results from different user needs and their economic capabilities, as well as because installed infrastructure tends to live long enough to become mixed with several new generations of technologies. - Autonomy: Different parts of the Internet are controlled by independent organizations. Even a sub-network controlled by the same multinational organization, such as IBM or Coca Cola, may cross many state borders. These independent organizations are generally in competition with each other and do not necessarily provide one another the most accurate information about their own networks. The implication is that the network engineer can effectively control only a small part of the global network. As for the rest, the engineer will be able to receive only limited information about the characteristics of others’ autonomous sub-networks. Any local solutions must be developed based on that limited information about the rest of the global network. - Scalability: Although a global network like the Internet consists of many autonomous domains, there is a need for standards that prevent the network from becoming fragmented into many non- interoperable pieces (“islands”). Solutions are needed that will ensure smooth growth of the network as many new devices and autonomous domains are added. Again, information about available network resources is either impossible to obtain in real time, or may be proprietary to the domain operator. 1.1.2 Communication Links There are many phenomena that affect the transmitted signal, some of which are illustrated in Figure 1-4. Although the effects of transients and noise are exaggerated, they illustrate an important point. The input pulses must be well separated because too short pulses will be “smeared” together. This can be observed for the short- duration pulses at the right-hand side of the pulse train. Obviously, the receiver of the signal in the bottom row of Figure 1-4 will have great difficulty figuring out whether or not there were pulses in the transmitted signal. You can also see that longer pulses are better propagation delay 101101 transmission delay 101101 Time E Elle ec cttr ro om ma ag gn ne ettiic c w wa av ve e p pr ro op pa ag ga attiio on n Ivan Marsic  Rutgers University 6 Communication link Physical setup: Sender Receiver Timeline diagram: Start of transmission End of reception Fluid flow analogy: First drop of the fluid enters the pipe Last drop of the fluid exits the pipe Fluid packet in transit Figure 1-5: Timeline diagram for data transmission from sender to receiver. Time increases down the page. separated and easier to recognize in the distorted signal. The minimum tolerable separation depends on the physical characteristics of a transmission line (e.g., copper vs. optical fiber). If each pulse corresponds to a single bit of information, then the minimum tolerable separation of pulses determines the maximum number of bits that can be transmitted over a particular transmission line. This number limits the data rate of a communication link (or transmission rate, or transmission capacity), which is the rate at which the network interface accepts data bits. The data rate of a link is measured in the units of bits per second (bps). It is common to represent data transmissions on a timeline diagram as shown in Figure 1-5. This figure also illustrates delays associated with data transmission. Although information bits are not necessarily transmitted as rectangular pulses of voltage, all transmission lines are conceptually equivalent, as represented in Figure 1-6, because the transmission capacity for every line is expressed in bits/sec or bps. The time required to transmit a single bit on a given link is known as bit time. In this book, we will always visualize transmitted data as a train of digital pulses. The reader interested in physical methods of signal transmission should consult a communications- engineering textbook, such as Haykin, 2009. Chapter 1  Introduction to Computer Networking 7 1 0 1 100 1 Link 1: 1 Mbps 1s 1011001 Time Link 2: 10 Mbps 100ns Figure 1-6: Transmi ssion link capacity determines the speed at which the link can transmit data. In this example, each bit on Link 1 is 1 s wide, while on Link 2 each bit is 100 ns wide. Hence, Link 2 can transmit ten times more data than Link 1 in the same time interval. A common characterization of noise on transmission lines is bit error rate (BER): the fraction of bits received in error relative to the total number of bits received in transmission. Given a packet n bits long and assuming that bit errors occur independently of each other, a simple approximation for the packet error rate is: nnBER PER1 (1 BER)1 e (1.1) An important attribute of a communication link is how many bitstreams can be transmitted on it at the same time. If a link allows transmitting only a single bitstream at a time, then the nodes connected to the link must coordinate their transmissions to avoid different bitstreams corrupting each other (known as data collision). Such links are known as broadcast links or multiple-access links. Point-to-point links often support data transmissions in both directions simultaneously. This kind of a link is said to be full duplex. A point-to-point link that supports data flowing in only one direction at a time is called half duplex. In other words, the nodes on each end of this kind of a link can both transmit and receive, but not at the same time—they only can do it by taking turns. It is like a one-lane road with bidirectional traffic. We will assume that all point-to-point links are full duplex, unless stated otherwise. A full-duplex link can be implemented in two ways: either the link must contain two physically separate transmission paths, one for sending and one for receiving, or the capacity of the communication channel is divided between signals traveling in opposite directions. The latter is usually achieved by time division multiplexing (TDM) or frequency division multiplexing (FDM). In TDM or FDM, the communication link transmission capacity is subdivided into m portions and each portions is assigned to a different logical stream of bits. In FDM, the channel bandwidth W is subdivided into m channels, each with bandwidth W/m (actually slightly less, to allow for guard bands between channels). If the original channel could transmit at data rate R bits/sec, each of the m sub-channels would transmit at R/m bits/sec. Therefore, the transmission of a given packet would last m times longer on an FDM sub-channel. In TDM, allocation is done by dividing the time axis into slots of fixed length, such as one bit long, or one byte long, or one packet long (assuming that all packets are equally long). As with FDM, conceptually we can view the link as consisting of m logically separate links or sub- channels. Again, the transmission of a given packet would last m times longer on a TDM sub- channel than it would on the original channel. Ivan Marsic  Rutgers University 8 Figure 1-7: Wireless transmission. Left: single point source. Right: interference of two point sources. Wireless Link Consider a simple case of a point source radiating electromagnetic waves in all directions (Figure 1-7, left). As the reader will recall from basic physics, all waves (acoustic, light, radio) behave in the same way, so it is useful to keep in mind some visible waves, such as water surface waves, while thinking about radio waves. A receiver senses the amplitude of a received wave signal to decode the message. The received signal strength decreases exponentially with the sender- receiver distance. As any other communication medium, the wireless channel is subject to thermal noise, which distorts the signal randomly according to a Gaussian distribution of noise amplitudes. As the distance between a transmitter and receiver increases, the received signal strength decreases to levels close to the background noise floor. At a certain distance from the sender, the signal strengths will become so weak that the receiver will not be able reliably to discern signal from noise. This distance, known as transmission range, is decided arbitrarily, depending on what is considered acceptable bit error rate. For example, we can define the transmission range as the sender-to-receiver distance for which the packet error rate is less than 10 %. In addition to thermal noise, the received signal may be distorted by parallel transmissions from other sources (Figure 1-7, right). This phenomenon is known as interference. Because this normally happens only when both sources are trying to transmit data (unknowingly of each other’s parallel transmissions), this scenario is called packet collision. A key observation is that collisions occur at the receiver—the sender is not disturbed by concurrent transmissions, but receiver cannot correctly decode sender’s message if it is combined with an interfering signal. If the source and receiver nodes are far away from the interfering source, the interference effect at the receiver will be a slight increase in the error rate. If the increased error rate is negligible, the source and receiver will be able to carry out their communication despite the interference. Note, however, that the interference of simultaneously transmitting sources never disappears—it only is reduced exponentially with an increasing mutual distance (Figure 1-8). The minimum distance (relative to the receiver) at which interferer’s effect can be considered negligible is called interference range. In Figure 1-8, node D is within the interference range of receiver B. Nodes C and E are outside the interference range. However, although outside the interference range defined for a single interferer, if nodes C and E are transmitting simultaneously their combined Chapter 1  Introduction to Computer Networking 9 In Int te er rfferi erin ng g C so sou urce rce Interference Interference range range D Transmission Transmission rang range e In Intte er rffer eriin ng g so source urce B Receiver A Interfering Interfering Sender E source source Transmitted Received signal Threshold signal power power from an Threshold interfering source Distance from sender 0 0 Distance from receiver Figure 1-8: Transmission range and interference range for wireless links. interference at B may be sufficiently high to cause as great or greater number of errors as a single interferer within the interference range. 1.1.3 Packets and Statistical Multiplexing The communication channel essentially provides an abstraction of a continuous stream of symbols transmitted that are subject to a certain error probability. When interacting with another person, whether face-to-face or over the telephone, we think of units of communication in terms of conversational turns: first one person takes a turn and delivers their message, then the other person takes a turn, and so on. Messages could be thought of as units of communication exchanged by two (or more) interacting persons. We note that there are benefits of slicing a long oration into a sequence of smaller units of discourse. This slicing into messages gives the other person chance to clarify a misunderstanding or give a targeted response to a specific item. In computer communication networks, messages are represented as strings of binary symbols (0 or 1), known as bits. Generally, messages are of variable length and some of them may still be considered too long for practical network transmission. There are several reasons for imposing a limit on message length. One is that longer messages stand a higher chance of being corrupted by an error (see Equation (1.1)). Another reason is to avoid the situation where a sending application seizes the link for itself by sending very long messages while other applications must wait for a long time. Therefore, messages are broken into shorter bit strings known as packets. These packets are then transmitted independently and reassembled into messages at the destination. This allows individual packets to opportunistically take alternate routes to the destination and interleave the network usage by multiple sources, thus avoiding inordinate waiting periods for some sources to transmit their information. Ivan Marsic  Rutgers University 10 City A City C (a) City B City D City A (b) City B City C City D Figure 1-9: An analogy illustrating dedicated lines (a) compared to statistical maultiplexing (b). Different network technologies impose different limits on the size of data blocks they can handle, which is known as the maximum transmission unit (MTU). For example, a regular Ethernet frame uses a frame format that limits the size of the payload it sends to 1,500 bytes. Note that the MTU value specifies the maximum payload size and does not include the header size of the header that is prepended to the payload of a packet. Statistical Multiplexing In Section 1.1.2 we mentioned tim e division multiplexing (TDM) and frequency division multiplexing (FDM) as example schemes for link sharing among multiple data streams. However, although their rigid rules for subdividing the link capacity ensure orderly and predictable data delivery, they may also incur inefficiencies. Consider the analogy in Figure 1-9 which shows traffic in multi-lane highways. In the top figure, cars are not allowed to cross over to other lanes, which corresponds to TDM or FDM schemes. An advantage is that there are no delays introduced by merging traffic or unpredictable outcomes of switching the lanes. A drawback is that some Chapter 1  Introduction to Computer Networking 11 lanes may be empty and go unused, while others may be full and cars may be prevented from entering. Restricting crossover increases travel time because some lanes may not beutilized while others are momentarily stressed. Unlike this, in the bottom of Figure 1-9 cars can change lanes, with the advantage that overall the highway is utilized more efficiently. Of course, there are disadvantages, as well, and they include delays at merging points and potential collisions. This second scenario represents statistical multiplexing using packet multiplexers Real-world systems are designed with sub-peak capacity for economic reasons. As a result, they experience congestion and delays during peak usage periods. Highways experience traffic slowdown during rush hours; restaurants or theaters experience crowds during weekend evenings; etc. Designing these systems to support peak usage without delays would not be economically feasible—most of the time they would be underutilized. 1.1.4 Communication Protocols A protocol is a set of rules agreed-upon by interacting entities, e.g., computing devices, that govern their communicative exchanges. In real world, protocols serve as mechanisms by which organizations or individuals manage the complexity of articulating their work. A protocol defines how and in what order each task must be performed. It is hard to imagine accomplishing any task involving multiple entities without relying on a protocol. For example, one could codify the rules for how a customer (C) purchases goods from a merchant (M) as follows: 1. CM Request catalog of products 2. CM Respond catalog 3. CM Make selections 4. CM Deliver selections 5. CM Confirm delivery 6. CM Issue bill 7. CM Make payment 8. CM Issue confirmation The customer and merchant may be located remote from each other and using other entities to help accomplish the purchasing task, such as a bank for credit-card transactions, or a postal service for parcel delivery. Figure 1-10 Ivan Marsic  Rutgers University 12 User-to-user interactions  obey social norms Letter (Message) Customer interaction obeys Person A Person B mail acceptance and delivery procedures (Postal Service’s Mail Manual)  Letter in Postal-vehicle service-transportation envelope (Packet) routes obey carrier-  route maps and delivery timetables Physical transport obeys transportation and traffic rules Figure 1-10: Protocol layers for conventional mail transport. Note the “layered design”— the division of labor between different layers of the “protocol stack.” An important characteristic of protocols is that the units of communication are data packets. Each data packet consists of a header that contains the packet guidance information to help guide the packet from its source to its destination, and the payload, which is the user information to be delivered to the destination address. A packet is delimited by the length information in its header, or by a special ending pattern of bits. (Of course, if the ending pattern is corrupted, the receiver will not be able to recognize the end of the packet.) In packet-switched networks, packets are transmitted at random times, and the receiver at the end of a communication link must have a means to distinguish an arriving packet from random noise on the line. For this purpose, each packet is preceded with a special sequence of bits that mark the start of the packet. This special bit pattern is usually called the preamble. Each receiver is continuously hunting for the preamble to catch the arriving packet. If the preamble is corrupted by random noise, the packet will be lost (i.e., unnoticed by the receiver). ommunication in computer networks is very complex. One effective means of dealing with C complexity is using the division of labor, known as modular design with separation of concerns. In this approach, the system is split into modules and each module is assigned separate responsibilities (“concerns”). Network designers usually adopt a restricted version of modular design, know as layered design. Each layer defines a collection of conceptually similar functions (or, services) distinct from those of the other layers. The restriction in layered design is that a module in a given layer provides services to the layer just above it and receives services from the layer just below it. Layers are ordered in that each layer can use services only of lower-level layers and not of the layers above it. The layering approach forbids the modules from using services from (or providing to) non-adjacent layers. The bottom layer does not depend on any other layer and the top layer is not used by any other layer. Each layer of the layered architecture is responsible for performing a well-defined function. A layer contains one or more software modules that offer services characteristic for this layer. Each module is called protocol. A protocol defines two application-programming interfaces (APIs): Chapter 1  Introduction to Computer Networking 13 1. Service interface to the protocols in the layer above this Layer i layer. The upper-layer protocols use this interface to “plug into” this layer and hand it data packets to send(). Each layer also defines a handle() callback operation send() handle() through which the lower layer calls this layer to handle an incoming packet. Layer i 1 2. Peer interface to the counterpart protocol on a remote machine. This interface defines the format and meaning of data packets exchanged between peer protocols to support communication. There are many advantages of layered design, primarily because it decomposes the problem of building a network into more manageable components. Each component can be developed independently and used interchangeably with any other component that complies with its service interface. However, there are some disadvantages, as well. For example, when a layer needs to make a decision about how to handle a data packet, it would be helpful to know what kind of information is inside the packet. Because of strict separation of concerns, particularly between the non-adjacent layers, this information is not available, so a more intelligent decision cannot be made. This is the reason why recently cross-layered designs are being adopted, particularly for wireless networks (see Chapter 6). Layered archit Layered architecture ecture Layer functio Layer function n Exam Examples ples Applic Applicat ation s ion sp pec ecif ific ic c co onnec nnecttiions ons • • T Tr ra ans nsmi mis ss siio on C n Co ontr ntro oll P Pr rotoc otocol ol ( (T TC CP P) ) 3: End-to-End 3: End-to-End • • R Rea eall- -ttiim me e T Tr ran ans sp po or rtt P Pr rotoc otocol ol ( (R RT TP P) ) S Se er rv viic ce in e inter terffa ac ce e b be etw twe een L en L2 2 & & L3 L3 S Sour ource- ce-tto o- -destinat destination routin ion routing g 2: Net 2: Netw work ork • • I Inter nternet Prot net Protocol ocol (IP) (IP) S Se er rv viic ce in e inter terffa ac ce e b be etw twe een L en L1 1 & & L2 L2 Pac Pack ket e et ex xc ch hang ange e • • I IEEE 8 EEE 80 02 2. .11 11 W WiiF Fii 1: Link 1: Link • • I IE EEE 8 EE 80 02 2. .3 3 E Et ther hern net et • • P PPP PP (modem (modems s,, T1 T1) ) Figure 1-11: Three-layer reference architecture for communication protocol layering. Ivan Marsic  Rutgers University 14 Three-Layer Model In recent years, the three-layer model (Figure 1-11) has emerged as reference architecture of computer networking protocols. LAYER-1 – Link layer: is at the bottom of the protocol stack and implements a packet delivery service between nodes that are attached to the same physical link (or, physical medium). The physical link may be point-to- point from one transmitter to a receiver, or it may be shared by a number of transmitters and receivers (known as “broadcast link,” Section 1.3. 3). There is the “physical layer,” which implements a digital transmission system that delivers bits. But, you would not know it because it is usually tightly coupled with the link layer by the link technology standard. Link and physical layers are usually standardized together and technology vendors package them together, as will be seen later in Section 1.5. In wireless networks, physical communication is much more complex than in wired networks. Therefore, it may be justifiable to distinguish the physical and link layers, to keep both manageable. Because this book is mainly about protocols and not about physical communication, I will consider both together as a single, Link layer. The link layer is not concerned with bridging end hosts across (many) intermediate links; this is why we need the network layer. LAYER-2 – Network layer: provides concatenation of links to connect arbitrary end hosts. It will be elaborated in Section 1. 4 where we describe the most popular network layer protocol: the Internet Protocol (IP). However, host computers are not the endpoints of communication—application programs running on these hosts are the actual endpoints of communication The network layer is not concerned with application requirements. It may provide a range of choices for an upper layer to select from. For example, the network layer may support “quality of service” through “service level agreements,” “resource reservation,” but it does not know which one of these choices is the best for a particular application program; this is why we need the end-to-end layer. LAYER-3 – End-to-end layer: this layer brings together (encapsulates) all communication- specific features of an application program. Here is the first time that we are concerned with application requirements. The figure on the right is meant to illustrate that different applications need different type of connection for optimal performance. Chapter 1  Introduction to Computer Networking 15 P Ph hy ys sical setu ical setup: p: Intermediate node (router) End host A End host B Communication link Communication link P Pr ro otocol stac tocol stack k:: Applic Applica at tiio on n Ap Appl pliic cati atio on n 3: End-to-E End-to-End nd E En nd d-to -to-E -En nd d :3 2: Netw Netwo or rk k 2: Ne Net tw wo or rk k Ne Netwo twor rk k :2 1: Li Link nk 1: Li Link nk Li Link nk :1 Physical communication Physical communication Figure 1-12: Protocol layering in end hosts and intermediate nodes (switches or routers). For example, manipulation-based applications (such as video games) require an equivalent of mechanical links to convey user’s action. Telephony applications need an equivalent of a telephone wire to carry user’s voice, etc. A most prominent example of an end-to-end protocol is TCP, described in Chapter 2. A fundamental design principle of network protocols and distributed systems in general is the end-to-end principle. The principle states that, whenever possible, communications protocol operations should occur at the end-points of a communications system, or as close as possible to the resource being controlled. According to the end-to-end principle, protocol features are only justified in the lower layers of a system if they are a performance optimization. Figure 1-12 shows the layers involved when a message is sent from an application running on one host to another running on a different host. The application on host A hands the message to the end-to-end layer, which passes it down the protocol stack on the same host machine. Every layer accepts the payload handed to it and processes it to add its characteristic information in the form of an additional header (Figure 1-13). The link layer transmits the message over the physical medium. As the message travels from A to B, it may pass through many intermediate nodes, known as switches or routers. In every receiving node (including the intermediate ones), the message is received by the bottommost (or, link) layer and passed up through their protocol stack. Because intermediate nodes are not the final destination (or, end point), they do not have the Ivan Marsic  Rutgers University 16 Sender’s Receiver’s Application data Application data protocol stack protocol stack La Laye yer r- -3 3 La Lay ye er r- -3 3 La Lay ye er r- -3 3 p pa ay ylloa oad d La Lay ye er r- -3 3 pa pay ylloa oad d h heade eader r h heade eader r Layer-2 Layer-2 La Apy pl eirc-at 2 pa ion d yloa ata d La Apy pl eirc-ation d 2 payloa ata d header header Layer-1 Layer-1 LayeA r-p 1pl pic aat yloa ion d d ata LayeA r-p 1pl pa icati ylo oa n d d ata header header Physical communication 010010110110001011100100101100000101101 010010110110001011100100101100000101101 Figure 1-13: Packet nesting across the protocol stack: an entire packet of an upper layer becomes the data payload of a lower layer. Also see Figure 1-14. complete protocol stack, but rather only the two bottommost layers: link and network layers (see Figure 1-12). Pseudo code of a generic protocol module in layer i is given in Listing 1-1. Listing 1-1: Pseudo code of a protocol module in layer i. // Definition of packet format for layer i. // Implementing the interface makes possible to serialize // a Packet object to a byte stream (which becomes the payload for the lower-layer protocol). 1 public class PacketLayer_i implements 2 // packet header 3 private String sourceAddress; 4 private String receiverAddress; 5 private String packetID; // this packet’s identifier 6 private String receivingProtocol; // upper layer protocol at receiver 7 // packet payload 8 private byte payload; 9 // constructor 10 public PacketLayer_i( 10a byte data, String recvAddr, String upperProtocol 10b ) 11 payload = data; 12 sourceAddress = address of my host computer; 13 receiverAddress = recvAddr; 14 packetID = generate unique identifier for this packet; 15 receivingProtocol = upperProtocol; 16 17 public void writeExternal(ObjectOutput out) 18 // Packet implements instead of 18a // to be able to control how the serialization stream is written, because Chapter 1  Introduction to Computer Networking 17 18a // it must follow the standard packet format for the given protocol. 19 20 public void readExternal(ObjectOutput out) 21 // reconstruct a Packet from the received bytestream 22 23 // Definition of a generic protocol module in layer i. 1 public class ProtocolLayer_i 2 // maximum number of outstanding packets at sender (zero, if NOT a persistent sender) 3 public static final int N; // (N is also called the sliding window size 4 // lower layer protocol that provides services to this protocol 5 private ProtocolLayer_iDOWN lowerLayerProtocol; 6 // look-up table of upper layer protocols that use services of this protocol 7 private HashMap upperLayerProtocols; 8 // look-up table of next-receiver node addresses based on final destination addresses 8a // (this object is shared with the routing protocol, shown in Listing 1-2) 9 private HashMap forwardingTable; 10 // list of unacknowledged packets that may need to be retransmitted 10a // (maintained only for persistent senders that provide reliable transmission) 11 private ArrayList unacknowledgedPackets = new ArrayList(); 12 // constructor 13 public ProtocolLayer_i( 13a ProtocolLayer_iDOWN lowerLayerProtocol 13b ) 14 this.lowerLayerProtocol = lowerLayerProtocol; 15 16 // sending service offered to the upper layer protocols, called in a top-layer thread 17 public void send( 17a byte data, String destinationAddr, 17b ProtocolLayer_iUP upperProtocol 17c ) throws Exception 18 // if persistent sender and window of unacknowledged packets full, then do nothing 19 if ((N 0) && (N - unacknowledgedPackets.size() = 0)) ) 20 throw exception: admission refused by overbooked sender; 21 22 // create the packet to send 23 PacketLayer_i outgoingPacket = 23a new PacketLayer_i(data, destinationAddr, upperProtocol); 24 // serialize the packet object into a byte-stream (payload for lower-layer protocol) 25 bout = 25a new ByteArrayOutputStream(); 26 outstr = 26a new ObjectOutputStream(bout); 27 outstr.writeObject(outgoingPacket); 28 // look-up the receiving node of this packet based on the destination address Ivan Marsic  Rutgers University 18 28a // (requires synchronized access because the forwarding table is shared 28b // with the routing protocol) 29 synchronized (forwardingTable) // critical region 30 String recvAddr = forwardingTable.get(destinationAddr); 31 // end of the critical region 32 // hand the packet as a byte-array down the protocol stack for transmission 33 lowerLayerProtocol.send( 33a bout.toByteArray(), recvAddr, this 33b ); 34 34 // upcall method, called from the layer below this one, when data arrives 35a // from a remote peer (executes in a bottom-layer thread) 36 public void handle(byte data) 37 // reconstruct a Packet object from the received data byte-stream 38 ObjectInputStream instr = new ObjectInputStream( 38a new ByteArrayInputStream(data) 38b ); 39 PacketLayer_i receivedFrame = 40 (PacketLayer_i) instr.readObject(); 41 // if this packet is addressed to me ... (on a broadcast medium) 42 if (receivedFrame.getReceiverAddress() == my address) 43 // ...demultiplex to upper layer protocol assigned to handle this packet's payload 44 synchronized (upperLayerProtocols) // critical region 45 ProtocolLayer_iUP upperProtocol = (ProtocolLayer_iUP) 45a upperLayerProtocols.get( 45b receivedFrame.getReceivingProtocol() 45c ); 46 // end of the critical region 47 // remove this protocol's header and 47a // hand the payload over to the upper layer protocol 48 upperProtocol.handle(receivedFrame.getPayload()); 49 50 51 // Receiver endpoint stores here the reference to an upper-layer protocol that will be used 51a // in the method handle() to demultiplex the receiving protocol to handle a packet 52 public void setHandler( 52a String receivingProtocol, ProtocolLayer_iUP upperProtocol 52b ) 53 // add a key, value entry into the look-up table to demultiplex upper layer protocol 54 upperLayerProtocols.put(receivingProtocol, upperProtocol); 55 56 // Method called by the routing protocol (running in a different thread or process) 57 public void setReceiver( 57a String destinationAddr, String receiverAddr 57b ) 58 // add a key, value entry into the forwarding look-up table 59 synchronized (forwardingTable) // critical region 60 forwardingTable.put(destinationAddr, receiverAddr); Chapter 1  Introduction to Computer Networking 19 61 // end of the critical region 62 63 Here I provide only a brief description of the above pseudocode. We will encounter and explain the details later in this chapter, as new concepts are introduced. The attribute upperProtocol is used to decide to which upper-layer protocol to deliver a received packet’s payload. This process is called protocol multiplexing and allows the protocol at a lower-level layer to serve different upper-layer protocols. The lower-layer sender protocol combines (“multiplexes”) several data streams and its counterpart at the receiver separates (“demultiplexes”) different streams for delivery to the correct upper-layer receiver protocol. Some functionality is not shown in Listing 1-1 to keep the pseudo code manageable. For example, in case of a persistent sender in the method send() we should set the retransmission timer for the sent packet and store the packet in the unacknowledgedPackets list. Similarly, in the method handle() we should check what packet is acknowledged and remove the acknowledged packet(s) from the unacknowledgedPackets list. Also, the method send() is shown to check only the forwardingTable to determine the intermediary receiver (recvAddr) based on the final destination address. In addition, we will see that different protocol layers use different addresses for the same network node (Section 9.3.1). For this reason, it is necessary to perform address translation from the current-layer address (recvAddr) to the address of the lower layer before passing it as an argument in the send() call, in Line 33. (See Section 9.3 for more about address translation.) The reader who carefully examined Listing 1-1 will have noticed that packets from higher layers become nested inside the packets of lower layers as they are passed down the protocol stack (Figure 1-13). The protocol at a lower layer is not aware of any structure in the data passed down from the upper layer, i.e., it does not know if the data can be partitioned to header and payload or where their boundary is—it simply considers the whole thing as an unstructured data payload. It is important to keep in mind how protocol layering is reflected in the packet format (Figure 1-14). Each p rotocol has its competences and does not understand the header format of protocols in other layers. A link-layer protocol does not know how to interpret the network-layer header and vice versa. This compartmentalization of competences helps keep protocols reasonably simple. In addition, when a network node receives a packet, the node’s protocols read the headers one by one, starting at the bottommost layer and going up the stack to the topmost layer. Each protocol removes its own header and passes the remaining packet up the protocol stack until the application data carried in the packet is handed over to the receiving application. The generic protocol implementation in Listing 1-1 works for all protocols in the layer stack. However, each layer will require some layer-specific modifications. The protocol in Listing 1-1 best represents a Network layer protocol for source-to-destination packet delivery. The Link layer is special because it is at the bottom of the protocol stack and cannot use services of any other layer. It runs the receiveBits() method in a continuous loop (perhaps in a separate thread or process) to hunt for arriving packets. This method in turn calls Link layer’s handle(), which in turn calls the upper-layer (Network) method handle(). Link layer’s send() method, instead of using a lower-layer service, itself does the sending by calling this layer’s own method sendBits().