Network Layer: Introduction and Service Models

The Network Layer and Routing Introduction and Service Models

In the previous chapter, we saw that transport layer functionality provides for communication between two endpoints, with the network layer providing a logical communication between these two endpoints. In the following chapter we will see that the data link layer also involves two endpoints, in this case communicating over a single physical link. In this chapter we study the network layer. We will see that unlike the transport and data link layers, the network layer requires the coordination of each and every host and router in the network. Because of this, network layer protocols are among the most challenging (and therefore interesting!) in the protocol stack.

Figure 4.0-1 shows a simple network with two hosts (h1 and h2) and four routers (r1, r2, r3 and r4). The role of the network layer in a sending host is to begin the packet on its journey to the the receiving host. For example, if h1 is sending to h2, the network layer in host h1 transfers these packets to it nearby router, r2. At the receiving host (e.g., h2) , the network layer receives the packet from its nearby router (in this case, r3) and delivers the packet up to the transport layer at h2. The primary role of the routers is to "switch" packets from input links to output links. Note that the routers in Figure 4.0-1 are shown with a truncated protocol stack, i.e., with no upper layers above the network layer, since from a conceptual standpoint, routers do not run transport and application level protocols such as those we examined in Chapters 2 and 3.

Figure 4.0-1: The network layer

The role of the network layer is thus deceptively simple -- to transport packets from a sending host to a receiving host. To do so, three important network layer functions can be identified:

Path Determination. The network layer must determine the route or path taken by packets as they flow from a sender to a receiver. The algorithms that calculate these paths are referred to as routing algorithms. A routing algorithm would determine, for example, whether packets from h1 to h2 flow along the path r2-r1-r3 or path r2-r4-r3 (or any other path between h1 and h2). Much of this chapter will focus on routing algorithms. In section 4.2 we will study the theory of routing algorithms, concentrating on the two most prevalent classes of routing algorithms: link state routing and distance vector routing. We will see that the complexity of a routing algorithms grows considerably as the number of routers in the network increases. This motivates the use of hierarchical routing, a topic we cover in section 4.3. In sections 4.4 and 4.5 we examine the network layer protocols in today's Internet and tomorrow next generation Internet. In section 4.6 we cover multicast routing -- the routing algorithms, switching function, and call setup mechanisms that allow a packet that is sent just once by a sender to be delivered to multiple destinations.
Switching. When a packet arrives at the input to a router, the router must move it to the appropriate output link. For example, a packet arriving from host h1 to router r2 must either be forwarded towards h2 either along the link from r2 to r1 or along the link from r2 to r4. In section 4.7, we look inside a router and examine how a packet is actually switched (moved) from an input link to an output link.
Call Setup. Recall that in our study of TCP, a three-way "handshake" was required before data actually flowed from sender to receiver. This allowed the sender and receiver to setup the needed state information (e.g., sequence number and initial flow control window size). In an analogous manner, some network layer architectures (e.g., ATM) requires that the routers along the chosen path from source to destination handshake with each other in order to setup state before data actually begins to flow. In the network layer, this process is referred to as call setup." The network layer of the Internet architecture does not perform any such call setup.

Before delving into the details of the theory and implementation of the network layer, however, let us first take the broader view and consider what different types of service might be offered by the network layer.

Network Service Model

When the transport layer at a sending host transmits a packet into the network (i.e., passes it down to the network layer at the sending host), does the sending entity know that the packet will be delivered to the destination? When multiple packets are sent, will they be delivered to the receiving transport entity in the order in which they were sent? Will the amount of time between the sending of two sequential packet transmissions be the same as the amount of time between their reception? Will the network provide any feedback about congestion in the network? What is the abstract view (properties) of the channel connecting the two transport layer entities? The answers to these questions and others are determined by the service model provided by the network layer. The network service model defines the characteristics of end-to-end transport of data between one "edge" of the network and the other, i.e., between sending and receiving hosts.

Connectionless or connection-oriented?

Perhaps the most important abstraction provided by the network layer to the upper layers is whether or not the network layer is connection-oriented. A connection-oriented packet network (also often referred to as a virtual-circuit network) behaves much like a telephone network. There are three identifiable phases:

Call setup. During call setup, the sender contacts the network, specifies the receiver address, and waits for the network to establish the connection. There is a subtle but important distinction between call setup at the network layer and call setup at the transport layer (e.g., the TCP 3-way handshake we studied in section X). Call setup at the transport layer only involves the two end systems. The two end systems agree to communicate and together determine the parameters (e.g., initial sequence number, flow control window size) of their transport level connection before data actually begins to flow on the transport level connection. With a connection-oriented network layer, packet switches are involved in call setup. Typically, this will involve updating data structures in the packet switcheson a chosen source-to-destination path to reflect the fact that a "connection" is now flowing along that path.
Data transfer. Once the network level connection has been set up, data can begin to flow along the connection.
Call teardown. When the sender (or receiver) wishing to terminate a call informs the network of its desire to do so. The network layer will then typically inform the end system on the other side of the network of the call termination, and update the data structures in the packet switches on the source-to-destination path to indicate that the connection no longer exists.

The messages that the end systems send to the network to indicate the initiation or termination of a call, and the messages passed between routers to set up the call (i.e. modify router data structures to indicate that the call is set up) are known as signaling messages and the protocols used to exchange these messages are often referred to as signaling protocols. Call setup is shown pictorially in Figure 4.1-1. ATM is fundamentally a connection-oriented network.

Figure 4.1-1: Connection-oriented service model

In a connectionless network (also referred to as a datagram network), the packet switches (called "routers" in the Internet) are unaware of an connection between two end systems. As shown in Figure 4.1-2, there is no call setup or teardown at the network layer, and each data packet from a source to a destination is handled independently of any previous packets from that to source-to-destination pair. As a result, subsequent packets belonging to the same connection may follow different paths through the network and may arrive out of order. The current Internet architecture is connectionless.

Figure 4.1-2: Connectionless service model

The Internet and ATM Network Service Models

**Table 4.1-1: Internet and ATM Network Service Models**
Network LoArchitecture	Service Model	Bandwidth Guarantee	Loss Guarantee	Ordering	Timing	Congestion indication
Internet	Best Effort	None	None	Any order possible	Not maintained	None
ATM	CBR	Guaranteed constant rate	Yes	In order	maintained	congestion will not occur
ATM	VBR	Guaranteed rate	Yes	In order	maintained	congestion will not occur
ATM	ABR	Guaranteed minimum	None	In order	Not maintained	Congestion indication provided
ATM	UBR	None	None	In order	Not maintained	None

The key aspects of the service model of the Internet and ATM network architectures are summarized in Table 4.1-1. We do not want to delve deeply into the details of the service models here (it can be quite "dry" and detailed discussions can be found in the standards themselves [ATM Forum 1997]). A comparison between the Internet and ATM service models is, however, quite instructive.

The current Internet architecture provides only one service model, known as "best effort service." From Table 4.1-1, it might appear that best effort service is a euphemism for "no service at all." With best effort service, timing between packets is not guaranteed to be preserved, packets are not guaranteed to be received in the order in which they were sent, nor is the eventual delivery of transmitted packets guaranteed. Given this definition, a network which delivered no packets to the destination would satisfy the definition best effort delivery service (Indeed, today's congested public Internet might sometimes appear to be an example of a network that does so!). As we will discuss shortly, however, there are sound reasons for such a minimalist network service model. The Internet's best-effort only service model is currently being extended to include so-called "integrated services" and "differentiated service." We will cover these still evolving service models later in Chapter 6.

Let us next turn to the ATM service models. As noted in our overview of ATM in chapter 1, there are two ATM standards bodies (the ITU and The ATM Forum) . Their network service model definitions contain only minor differences and we adopt here the terminology used in the ATM Forum standards. The ATM architecture provides for multiple service models (that is, each of the two ATM standards each has multiple service models). This means that within the same network, different connections can be provided with different classes of service.

Constant bit rate (CBR) network service was the first ATM service model to be standardized, probably reflecting the fact that telephone companies were the early prime movers behind ATM, and CBR network service is ideally suited for carrying real-time, constant-bit-rate, streamline audio (e.g., a digitized telephone call) and video traffic. The goal of CBR service is conceptually simple -- to make the network connection look like a dedicated copper or fiber connection between the sender and receiver. With CBR service, ATM cells are carried across the network in such a way that the end-end delay experienced by a cell (the so-called cell transfer delay, CDT), the variability in the end-end delay (often referred to as "jitter" or "cell delay variation, CDV)"), and the fraction of cells that are lost or deliver late (the so-called cell loss rate, CLR) are guaranteed to be less than some specified values. Also, an allocated transmission rate (the peak cell rate, PCR) is defined for the connection and the sender is expected to offer data to the network at this rate. The values for the PCR, CDT, CDV, and CLR are agreed upon by the sending host and the ATM network when the CBR connection is first established.

A second conceptually simple ATM service class is Unspecified Bit Rate (UBR) network service. Unlike CBR service, which guarantees rate, delay, delay jitter, and loss, UBR makes no guarantees at all other than in-order delivery of cells (that is, cells that are fortunate enough to make it to the receiver). With the exception of in-order delivery, UBR service is thus equivalent to the Internet best effort service model. As with the Internet best effort service model, UBR also provides no feedback to the sender about whether or not a cell is dropped within the network. For reliable transmission of data over a UBR network, higher layer protocols (such as those we studied in the previous chapter) are needed. UBR service might be well suited for non-interactive data transfer applications such as email and newsgroups.

If UBR can be thought of as a "best effort" service, then Available Bit Rate (ABR) network service might best be characterized as a "better" best effort service model. The two most important additional features of ABR service over UBR service are:

A minimum cell transmission rate (MCR) is guaranteed to a connection using ABR service. If, however, the network has enough free resources at a given time, a sender may actually be able to successfully send traffic at a higher rate than the MCR.

Congestion feedback from the network. An ATM network provides feedback to the sender (in terms of a congestion notification bit, or a lower rate at which to send) that controls how the sender should adjust its rate between the MCR and some peak cell rate (PCR). ABR senders must decrease their transmission rates in accordance with such feedback.

ABR provides a minimum bandwidth guarantee, but on the other hand will attempt to transfer data as fast as possible (up to the limit imposed by the PCR). As such, ABR is well suited for data transfer where it is desirable to keep the transfer delays low (e.g., WWW browsing).

The final ATM service model is Variable Bit Rate (VBR) network service. VBR service comes in two flavors (and in the ITU specification of VBR-like service comes in four flavors -- perhaps indicating a service class with an identity crisis!). In real-time VBR service, the acceptable cell loss rate, delay, and delay jitter are specified as in CBR service. However, the actual source rate is allowed to vary according to parameters specified by the user to the network. The declared variability in rate may be used by the network (internally) to more efficiently allocate resources to its connections, but in terms of the loss, delay and jitter seen by the sender, the service is essentially the same as CBR service. While early efforts in defining a VBR service models were clearly targeted towards real-time services (e.g., as evidenced by the PCR, CDT, CDV and CLR parameters), a second flavor of VBR service is now targeted towards non-real-time services and provides a cell loss rate guarantee. An obvious question with VBR is what advantages it offers over CBR (for real-time applications) and over UBR and ABR for non-real-time applications. Currently, there is not enough (any?) experience with VBR service to answer this questions.

An excellent discussion of the rationale behind various aspects of the ATM Forum's Traffic Management Specification 4.0 [ATM Forum 1996] for CBR, VBR, ABR and UBR service is [Garret 1996].

Origins of Connectionless and Connection-Oriented Service

The evolution of the Internet and ATM network service models reflects their origins. With the notion of a connection as a central organizing principle, and an early focus on CBR services, ATM reflects its roots in the telephony world. The subsequent definition of UBR and ABR service classes acknowledges the importance of the types of data applications developed in the data networking community. Given the connection-oriented architecture and a focus on supporting real-time traffic with guarantees about the level of received performance (even with data-oriented services such as ABR), the network layer is significantly more complex than the best effort Internet. This too, is in keeping with the ATM's telephony heritage. Telephone networks, by necessity, had their "complexity' within the network, since they were connecting "dumb" end-system devices such as a rotary telephone (For those too young to know, a rotary phone is a non-digital telephone with no buttons - only a dial).

The Internet, on the other hand, grew out of the need to connect computers (i.e., more sophisticated end devices) together. With sophisticated end-systems devices, the Internet architects chose to make the network service model (best effort) as simple as possible and to implement any additional functionality (e.g., reliable data transfer), as well as any new application level network services at a higher layer, at the end systems. This inverts the model of the telephone network, with some interesting consequences:

The resulting network service model which made minimal (no!) service guarantees (and hence posed minimal requirements on the network layer) also made it easier to interconnect networks that used very different link layer technologies (e.g., satellite, Ethernet, fiber, or radio) which had very different characteristics (transmission rates, loss characteristics). We will address the interconnection of IP networks in detail section 4.4.
As we saw in Chapter 2, applications such as email, the WWW, and even a network-layer-centric service such as the DNS are implemented in hosts (servers) at the edge of the network. The ability to add a new service simply by attaching a host to the network and defining a new higher layer protocol (such as HTTP) has allowed new services such as the WWW to be adopted in a breathtakingly short period of time.

As we will see in Chapter X, however, there is considerable debate in the Internet community about how the network layer architecture must evolve in order to support the real-time services such a multimedia. An interesting comparison of the ATM and the proposed next generation Internet architecture is given in [Crowcroft 95].

References

[ATM Forum 1996] ATM Forum, "Traffic Management 4.0," ATM Forum document af-tm-0056.0000. On-line
[ATM Forum 1997] ATM Forum. "Technical Specifications: Approved ATM Forum Specifications." On-line.
[Crowcroft 1995] J. Crowcroft, Z. Wang, A. Smith, J. Adams, "A Comparison of the IETF and ATM Service Models," IEEE Communications Magazine, Nov./Dec. 1995, pp. 12 - 16. Compares the Internet Engineering Task Force int-serv service model with the ATM service model. On-line.
[Garrett 1996] M. Garett, "A Service Architecture for ATM: From Applications to Scheduling," IEEE Network Magazine, May/June 1996, pp. 6 - 14. A thoughtful discussion of the the ATM Forum's recent TM 4.0 specification of CBR, VBR, ABR and UBR service.