Last modified 3/16/95.
An earlier page described how to transfer frames of data error-free from one node to another, another described multiplexing on a shared line, while the previous page described circuit switching. To understand packet-switching, it is useful to know something about point-to-point topologies.
This page considers packet-switching and compares packet-switching with circuit-switching.
A sequence of data is to be sent from one host to another over a network. In circuit-switching, a series of dedicated lines and/or time slots and/or frequencies is set aside for the connection that is first established before any data transfer can take place. Routing decisions must be made when the circuit is first established, but there are no decisions made after that time. With packet switching, the data sequence is segmented into one or more packets, each with a header containing control information, and each packet is routed through the network. There are two flavors of packet-switching:
Regardless of the type of service, packet switching allows
Virtual circuits must be
DG service offers no real guarantees. Packets, while they may belong together logically at a higher level, are not associated with one another at the network level. There is no setup or teardown request, just the request to send the datagram packet. A datagram may
Internal VCs establish a virtual circuit identifier (VCI) that is used throughout the network rather than just the end points (as would happen if DGs were used to implement VC service). The VCI corresponds to a path or route that all the packets with that VCI will take over the lifetime of that VC. During the setup phase, this route is established and entries are made in tables at each node along the route. In addition, the nodes may allocate some resources (e.g., buffers, line capacity) to the VC so that some service guarantees may be made (e.g., minimum end-to-end capacity, maximum packet loss rate). Once the VC route is established, which requires all the nodes on the path to agree, then the VC may be used for data transmission. Packets have the VCI in their header, which may be used as a pointer to much more information stored at the nodes along the way. The VCI is usually very small compared to the network addresses used to define the endpoints of the VC, much less the additional information regarding the services requested. Usually, the VCI is used to index into a routing table that specifies over which output line (queue) the packet is to traverse next. How the route is determined varies, and is discussed below under routing.
VCIs need to be unambiguous, and since it is desirable to keep them small, care must be taken with their reuse. While globally unique VCIs would solve ambiguity problems, they would also make the VCI large or restrict the number of VCs at any location (if the VCIs are partitioned across all network nodes), or they would introduce long delays in obtaining a VCI at setup time (if the VCIs are managed either by central sites or in a distributed manner). Instead, the observation that VCIs need only be unique at each link leads to a design that allows for small VCIs managed locally. In this method, when a VC is initialized, at each node along the path there is an incoming line for the VC and an outgoing line for the VC. The node must agree with the node on the other end of each line what the VCI for that VC is to be for that line. The VCI need not be the same for both directions on the same line, so a node may manage its outgoing VCIs by itself, simply informing the receiver what VCI to use for that VC on that line. The next node on the path may then choose a VCI for the opposite direction on the same line, and inform the current node of this VCI, which is entered into the node's table for transmission on the line to the previous node. As each node receives a packet, it uses the input line and the VCI to index into its routing table, where it finds the appropriate output line and new VCI for that output line, replacing the VCI used for the incoming line in the header with the VCI for the outgoing line. The VCI may change with every hop, but at each node, the VCI is unambiguous.
All of the packets sent along a VC will follow the same path. The simpler routing attained for each packet is paid for in part by less adaptability: once a VC is established, the conditions under which the route was chosen may change, making the chosen route less desirable (e.g., a better route may become available, or the route may become congested and therefore less desirable). If there is a failure a new VC must be established and lost data must be recovered before transmission can resume. The new path may use part of the old path, or it may be established from scratch. Either way has its advantages and disadvantages.
When the VC is terminated, a teardown control packet is sent to the nodes along the VC's route (either threading them or through some multicast method) to free the resources allocated to the VC. It is important that these teardown messages be delivered reliably or else resources will be held needlessly, and at worse some confusion could result from VCI reuse.
Datagrams must be self-contained, since there is no association in the network from one DG to another. At least the full destination address must be present, and if there are any service level requests (such as priority), these must also be present in the header. Since source address is usually required, these with the control fields typically make the header larger in DGs than in VC packets.
Routing is determined either by information stored in the header or, more typically, by a routing table lookup based on the destination address. This is more expensive than the VC table indexing operation because the destination address space is usually too large to have a direct-access table with an entry for each possible destination. DGs sent to the same node from the same source may follow different routes, depending upon the nature of the routing decision at the time the packets arrive at each node along the paths they take. This allows DG implementation to adapt quickly to changing conditions, avoiding damaged components or congested areas. At the same time, it produces less predictability in end-to-end delay (and hence, ordering of packets), and indeed, delivery at all.
If DGs are used internally to implement VC service, then the end nodes of the VC must handle all the unpredictability that can occur from DGs. This means that the DG header may contain VC information that is not used as the packet is routed through the network, but is only used by the end nodes. This information would include the VCI, sequence numbers, error detection sequences, and the like.
The simple end-to-end delay for delivery of a whole message that is broken into several packets is based on the number of hops, data rates along each hop (usually assumed to be the same at each hop), propagation delay along each hop, header size, packet payload size (the amount of data a packet can carry) and message size. This analysis usually assumes that processing time at the intermediate nodes is negligible, and ignores queuing delays. Often propagation time is considered to be neglible compared to transmission time, but this is not always a safe assumption, nor is ignoring queuing delay.
Packet size has a significant effect on the efficiency of the system. Small packet sizes allow for better pipelining and have lower probability of being corrupted at a fixed bit error rate, but have higher header overhead as the header size is fixed. Larger packet sizes have better packet format efficiency, but have worse pipelining. Pipelining effects are more important as hops increase.