Datagram Networks

Datagram Networks

In a datagram network, each time an end system wants to send a packet, it stamps the packet with the address of the destination end system and then pops the packet into the network. As shown in Figure 1, this is done without any VC setup. Routers in a datagram network do not maintain any state information about VCs (because there are no VCs!).

As a packet is transmitted from source to destination, it passes through a series of routers. Each of these routers uses the packet's destination address to forward the packet. Particularly, each router has a forwarding table that maps destination addresses to link interfaces; when a packet arrives at the router, the router uses the packet's destination address to look up the appropriate output link interface in the forwarding table. The router then intentionally forwards the packet to that output link interface.

To get some more insight into the lookup operation, let's look at a specific example. Assume that all destination addresses are 32 bits (which just happens to be the length of the destination address in an lP datagram). A brute-force implementation of the forwarding table would have one entry for every possible destination address. Since there are more than 4 billion possible addresses, this option is totally out of the question - it would require a humongous forwarding table.

Datagram network

Now let's further assume that our router has four links, numbered 0 through 3, and that packets are to be forwarded to the link interfaces as follows:

humongous forwarding table

Clearly, for this example, it is not compulsory to have 4 billion entries in the router's forwarding table. We could, for instance, have the following forwarding table with just four entries:

forwarding table

With this style of forwarding table, the router matches a prefix of the packet's destination address with the entries in the table; if there's a match, the router forwards the packet to a link associated with the match. For instance, assume the packets destination address is 11001000 00010111 00010110 10100001; because the 21-bit prefix of this address matches the first entry in the table, the router forwards the packet to link interface 0. If a prefix doesnt match any of the first three entries, then the router forwards the packet to interface 3.  Although this sounds simple enough, there's an important subtlety here. You may have noticed that it is possible for a destination address to match more than one entry. For instance, the first 24 bits of the address 11001000 00010111 00011000 10101010 match the second entry in the table, and the first 21 bits of the address match the third entry in the table. When there are multiple matches, the router uses the longest prefix matching rule; that is, it finds the longest matching entry in the table and forwards the packet to the link interface associated with the longest prefix match. We'll see exactly why this longest prefix-matching rule is used when we study Internet addressing in more detail in "The Internet Protocol (IP): Forwarding and Addressing in the Internet".

Although routers in datagram networks maintain no connection state information, they nevertheless maintain forwarding state information in their forwarding tables. Nevertheless, the time scale at which this forwarding state information changes is relatively slow. Certainly, in a datagram network the forwarding tables are modified by the routing algorithms, which typically update a forwarding table every one-to-five minutes or so. ln a VC network, a forwarding table in a router is modified whenever a new connection is set up through the router or whenever an existing connection through the router is torn down. This could easily happen at a microsecond timescale in a backbone, tier-1 router.

Because forwarding tables in datagram networks can be modified at any time, a series of packets sent from one end system to another may follow different paths through the network and may arrive out of order. [Paxson 1997] and [Jaiswal 2003] present interesting measurement studies of packet reordering and other phenomena in the public Internet.

Origins of VC and Datagram Networks


The evolution of datagram and VC networks reflects their origins. The notion of a virtual circuit as a central organizing principle has its roots in the telephony world, which uses real circuits. With call setup and per-call state being maintained at the routers within the network, a VC network is arguably more complicated than a datagram network for an interesting comparison of the complexity of circuit- versus packet-switched networks). This, too, is in keeping with its telephony heritage. Telephone networks, by necessity, had their complexity within the network, since they were connecting dumb end-system devices such as rotary telephones. (For those too young to know, a rotary phone is an analog telephone with no buttons - only a dial.)

The Internet as a datagram network, on the other hand, grew out of the need to connect computers together. Given more complicated end-system devices, the Internet architects chose to make the network-layer service model as simple as possible. As we have already seen in "Application Layer" and "Transport Layer", additional functionality (for example, in-order delivery, reliable data transfer, congestion control, and DNS name resolution) is then implemented at a higher layer, in the end systems. This inverts the model of the telephone network, with some interesting consequences:

●  Since the resulting Internet network-layer service model makes minimal (no!) service guarantees, it imposes minimal requirements on the network layer. This makes it easier to interconnect networks that use very different link-layer technologies (for instance, satellite, Ethernet, fiber, or radio) and have very different transmission rates and loss characteristics. We will address the interconnection of IP networks in detail in "The Internet Protocol (IP): Forwarding and Addressing in the Internet".

●  As we saw in "Application Layer", applications such as e-mail, the Web, 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 application-layer protocol (such as HTTP) has allowed new applications such as the Web to be deployed in the Internet in a remarkably short period of time,

As we'll see in "Multimedia Networking", there is considerable debate in the Internet community about how the Internet's network-layer architecture should evolve in order to support real-time services such as multimedia. An interesting comparison of the VC-oriented ATM network architecture and a proposed next-generation Internet architecture is given in [Crowcroft 1995].

Tags

datagram network, end system, routers, forwarding table

Copy Right

The contents available on this website are copyrighted by TechPlus unless otherwise indicated. All rights are reserved by TechPlus, and content may not be reproduced, published, or transferred in any form or by any means, except with the prior written permission of TechPlus.