10 Introduction and Layered Network Architecture Chap.1 user I might send a message to user 2,user 2 might reply with a message to 1,who might then send another message to 2,and so forth until the completion of the overall transaction.The important characteristic of a message is that from the standpoint of the network users,it is a single unit of communication.If a recipient receives only part of a message,it is usually worthless. It is sometimes necessary to make a distinction between a message and the rep- resentation of the message.Both in a subnet and in a computer,a message is usually represented as a string of binary symbols,0 or 1.For brevity,a binary symbol will be referred to as a bit.When a message goes from sender to recipient,there can be several transformations on the string of bits used to represent the message.Such transformations are sometimes desirable for the sake of data compression and sometimes for the sake of facilitating the communication of the message through the network.A brief description of these two purposes follows. The purpose of data compression is to reduce the length of the bit string representing the message.From the standpoint of information theory,a message is regarded as one of a collection of possible messages,with a probability distribution on the likelihood of different messages.Such probabilities can only be crudely estimated,either a priori or adaptively.The idea,then,is to assign shorter bit strings to more probable messages and longer bit strings to less probable messages,thus reducing the expected length of the representation.For example,with text,one can represent common letters in the alphabet (or common words in the dictionary)with a small number of bits and represent unusual letters or words with more bits.As another example,in an airline reservation system,the common messages have a very tightly constrained format (date,flight number,names, etc.)and thus can be very compactly represented,with longer strings for unusual types of situations.Data compression will be discussed more in Chapter 2 in the context of compressing control overhead.Data compression will not be treated in general here, since this topic is separable from that of data networks,and is properly studied in its own right,with applications both to storage and point-to-point communication. Transforming message representations to facilitate communication,on the other hand,is a central topic for data networks.In subsequent chapters,there are many examples in which various kinds of control overhead must be added to messages to ensure reliable communication,to route the message to the correct destination,to control congestion,and so on.It will also be shown that transmitting very long messages as units in a subnet is harmful in several ways,including delay,buffer management,and congestion control.Thus,messages represented by long strings of bits are usually broken into shorter bit strings called packets.These packets can then be transmitted through the subnet as individual entities and reassembled into messages at the destination. The purpose of a subnet,then,is to receive packets at the nodes from sites outside the subnet,then transmit these packets over some path of communication links and other nodes,and finally deliver them to the destination sites.The subnet must somehow obtain information about where the packet is going,but the meaning of the corresponding message is of no concern within the subnet.To the subnet,a packet is simply a string of bits that must be sent through the subnet reliably and quickly.We return to this issue in Section 1.3
10 Introduction and Layered Network Architecture Chap. 1 user I might send a message to user 2, user 2 might reply with a message to I, who might then send another message to 2, and so forth until the completion of the overall transaction. The important characteristic of a message is that from the standpoint of the network users, it is a single unit of communication. If a recipient receives only part of a message, it is usually worthless. It is sometimes necessary to make a distinction between a message and the representation of the message. Both in a subnet and in a computer, a message is usually represented as a string of binary symbols, 0 or 1. For brevity, a binary symbol will be referred to as a bit. When a message goes from sender to recipient, there can be several transformations on the string of bits used to represent the message. Such transformations are sometimes desirable for the sake of data compression and sometimes for the sake of facilitating the communication of the message through the network. A brief description of these two purposes follows. The purpose of data compression is to reduce the length of the bit string representing the message. From the standpoint of information theory, a message is regarded as one of a collection of possible messages, with a probability distribution on the likelihood of different messages. Such probabilities can only be crudely estimated, either a priori or adaptively. The idea, then, is to assign shorter bit strings to more probable messages and longer bit strings to less probable messages, thus reducing the expected length of the representation. For example, with text, one can represent common letters in the alphabet (or common words in the dictionary) with a small number of bits and represent unusual letters or words with more bits. As another example, in an airline reservation system, the common messages have a very tightly constrained format (date, flight number, names, etc.) and thus can be very compactly represented, with longer strings for unusual types of situations. Data compression will be discussed more in Chapter 2 in the context of compressing control overhead. Data compression will not be treated in general here, since this topic is separable from that of data networks, and is properly studied in its own right, with applications both to storage and point-to-point communication. Transforming message representations to facilitate communication, on the other hand, is a central topic for data networks. In subsequent chapters, there are many examples in which various kinds of control overhead must be added to messages to ensure reliable communication, to route the message to the correct destination, to control congestion, and so on. It will also be shown that transmitting very long messages as units in a subnet is harmful in several ways, including delay, buffer management, and congestion control. Thus, messages represented by long strings of bits are usually broken into shorter bit strings called packets. These packets can then be transmitted through the subnet as individual entities and reassembled into messages at the destination. The purpose of a subnet, then, is to receive packets at the nodes from sites outside the subnet, then transmit these packets over some path of communication links and other nodes, and finally deliver them to the destination sites. The subnet must somehow obtain information about where the packet is going, but the meaning of the corresponding message is of no concern within the subnet. To the subnet, a packet is simply a string of bits that must be sent through the subnet reliably and quickly. We return to this issue in Section 1.3
Sec.1.2 Messages and Switching 11 1.2.2 Sessions Messages between two users usually occur as a sequence in some larger transaction; such a message sequence (or,equivalently,the larger transaction)is called a session. For example,updating a data base usually requires an interchange of several messages. Writing a program at a terminal for a remote computer usually requires many messages over a considerable time period.Typically,a setup procedure (similar to setting up a call in a voice network)is required to initiate a session between two users,and in this case a session is frequently called a connection.In other networks,no such setup is required and each message is treated independently;this is called a connectionless service.The reasons for these alternatives are discussed later. From the standpoint of network users,the messages within a session are typically triggered by particular events.From the standpoint of the subnet,however,these message initiation times are somewhat arbitrary and unpredictable.It is often reasonable,for subnet purposes,to model the sequence of times at which messages or packets arrive for a given session as a random process.For simplicity,these arrivals will usually be modeled as occurring at random points in time,independently of each other and of the arrivals for other sessions.This type of arrival process is called a Poisson process and is defined and discussed in Section 3.3.This model is not entirely realistic for many types of sessions and ignores the interaction between the messages flowing in the two directions for a session.However,such simple models provide insight into the major trade-offs involved in network design,and these trade-offs are often obscured in more realistic and complex models. Sometimes it will be more convenient to model message arrivals within a ses- sion by an on/off flow model.In such a model,a message is characterized by a se- quence of bits flowing into the subnet at a given rate.Successive message arrivals are separated by random durations in which no flow enters the network.Such a model is appropriate,for example,for voice sessions and for real-time monitoring types of applications.When voice is digitized (see Section 2.2).there is no need to trans- mit when the voice is silent,so these silence periods correspond to the gaps in an on/off flow model.One might think that there is little fundamental difference between a model using point arrivals for messages and a model using on/off flow.The out- put from point message arrivals,followed by an access line of fixed rate,looks very much like an on/off flow (except for the possibilitity that one message might arrive while another is still being sent on the access line).The major difference between these models,however,is in the question of delay.For sessions naturally modeled by point message arrivals (e.g.,data base queries),one is usually interested in delay from message arrival to the delivery of the entire message (since the recipient will process the entire message as a unit).For sessions naturally modeled by flow (such as digitized voice),the concept of a message is somewhat artificial and one is usu- ally interested in the delay experienced by the individual bits within the flow.It ap- pears that the on/off flow model is growing in importance and is particularly appro- priate for ISDN and broadband ISDN networks.Part of the reason for this growth is the prevalence of voice in ISDN and voice and video in broadband ISDN.An-
Sec. 1.2 Messages and Switching 11 1.2.2 Sessions Messages between two users usually occur as a sequence in some larger transaction; such a message sequence (or, equivalently, the larger transaction) is called a session. For example, updating a data base usually requires an interchange of several messages. Writing a program at a terminal for a remote computer usually requires many messages over a considerable time period. Typically, a setup procedure (similar to setting up a call in a voice network) is required to initiate a session between two users, and in this case a session is frequently called a connection. In other networks, no such setup is required and each message is treated independently; this is called a connectionless service. The reasons for these alternatives are discussed later. From the standpoint of network users, the messages within a session are typically triggered by particular events. From the standpoint of the subnet, however, these message initiation times are somewhat arbitrary and unpredictable. It is often reasonable, for subnet purposes, to model the sequence of times at which messages or packets arrive for a given session as a random process. For simplicity, these arrivals will usually be modeled as occurring at random points in time, independently of each other and of the arrivals for other sessions. This type of arrival process is called a Poisson process and is defined and discussed in Section 3.3. This model is not entirely realistic for many types of sessions and ignores the interaction between the messages flowing in the two directions for a session. However, such simple models provide insight into the major trade-offs involved in network design, and these trade-offs are often obscured in more realistic and complex models. Sometimes it will be more convenient to model message arrivals within a session by an on/off flow model. In such a model, a message is characterized by a sequence of bits flowing into the subnet at a given rate. Successive message arrivals are separated by random durations in which no flow enters the network. Such a model is appropriate, for example, for voice sessions and for real-time monitoring types of applications. When voice is digitized (see Section 2.2), there is no need to transmit when the voice is silent, so these silence periods correspond to the gaps in an on/off flow model. One might think that there is little fundamental difference between a model using point arrivals for messages and a model using on/off flow. The output from point message arrivals, followed by an access line of fixed rate, looks very much like an on/off flow (except for the possibilitity that one message might arrive while another is still being sent on the access line). The major difference between these models, however, is in the question of delay. For sessions naturally modeled by point message arrivals (e.g., data base queries), one is usually interested in delay from message arrival to the delivery of the entire message (since the recipient will process the entire message as a unit). For sessions naturally modeled by flow (such as digitized voice), the concept of a message is somewhat artificial and one is usually interested in the delay experienced by the individual bits within the flow. It appears that the on/off flow model is growing in importance and is particularly appropriate for ISDN and broadband ISDN networks. Part of the reason for this growth is the prevalence of voice in ISDN and voice and video in broadband ISDN. An-