Computer Networking Lecture Notes

9 October 2012 • Network Layer

---

Outline

• Network services.
  • Connectionless and circuit networks.
• Connectionless Behavior.
  • Routers, operating and algorithms.
• Virtual-Circuit Networks.
• Trade-offs

Where We Were

Where We’ll Be

What

• The network layer is also an end-to-end layer.
  • The ends are closer together.
• The recursion bottoms out.
  • The hops are between atomic points.

Scope

• Network operation requires static and dynamic global knowledge.
  • Network topology.
  • Network load and congestion.
  • Possibly edge behavior.
• Accurate and complete global knowledge is a limit to growth.

Issues

• Important issues in network design and operation include
  • Services offered to the transport layer.
    • Connectionless vs connection-oriented.
  • Network topology.
    • In design, but also in operation.
• Other factors intrude.
  • Wireless networking in particular.

Context

Operation

• The sender emits a packet sequence into the network.
• The packets arrive at routers in the network.
• Each router sends packets along links to other routers, moving closer to the receiver.
• Each packet eventually arrives at the last router.
• The packets are delivered to the receiver.

Network Services

• The network offers services to the transport layer.
• The main network service is abstraction:
  • Routers are invisible.
  • Network topology is invisible.
  • Visible network features (mainly addresses) are uniform.

Network Service Function

• But what do network services do?
• Move packets from ingress to egress routers.
• Anything else?
  • Connectionless partisans: No!
  • Circuit partisans: Yes!
• The battle rages, with changing forces favoring one side or the other.

Connectionless Networks

• Networks offer an unreliable datagram service.
  • No flow control, no ordering, no error handling.
• Hosts have to do these things anyway, the network is redundant.
  • And expensive if not needed.
• The end-to-end argument and the rise of the stupid network.

Circuit Networks

• Networks offer reliable connection services.
  • Strong guarantees on everything, including quality of service.
• It is hard to impossible for hosts to provide these guarantees.
  • Near-hard real-time multi-media service.
• A hundred-plus years of telephone service.

Network History

• Early networks offered reliable connection services.
  • X.25 (1970s) and Frame Relay (1980s).
• The Internet and IP overran all in its path.
  • Including ISO OSI and later challenges like ISDN and ATM.
• The current approach seems to be change from within.
  • Too much money on the table: DiffServ and MultiProtocol Lable Switching (MPLS).

Connectionless Behavior

• Transport PDUs (segments) are encapsulated in Network PDUs (datagrams).
  • TPDUs may be fragmented to fit smaller NPDUs.
• The NPDUs enter the network.
• The NPDUs flow through the network toward the exit router.
• The NPDUs leave the network.
• The NPDUs are reassembled into TPDUs and passed up the stack.

Routers

• A router is a special-purpose computer.
  • Host-routers are conceptually separated.
• Routers send and receive NPDUs over a fixed set of connected links.
  • Wireless complicates this picture.
• Each router has a routing table, a list of (destination, out-link) pairs.
  • The destination is a host or router address.
  • The out-link is also know as the next-hop.

Router Operation

• NPDUs arrive and are disassembled.
  • Checksumned, ttl reduced, and so on.
• Consult the routing table to determine out-link (next hop).
• Reassemble NPDU and queue for output.

  

Routing Algorithms

• The two main operations on routing tables are
  • update to reflect current network topology, and
  • return a next-hop link given a destination address.
• A network uses a routing algorithm to do both these operations.
  • With algorithm structure reflecting the two operations.

Virtual-Circuit Networks

• Virtual-circuit (connection-oriented) networks simplifies per-packet, per-hop routing.
• Connection set-up establishes a path though the network.
  • A path is a router sequence.
• NPDUs flow through the virtual circuit.
• The virtual circuit is torn down once transmission ends.
  • Virtual circuits can also be nailed-up, kept open independent of traffic.

Virtual-Circuit Identifiers

• Each virtual circuit is identified by a small integer identifier.
  • Host-selected to avoid global state.
• VC identifier clashes are avoided by rewriting at the routers.
• The routing table is now pairs of pairs.

  ((link_in, VCI_in), (link_out, VCI_out))

Label Switching

• VC identifier rewriting is occasionally known as label switching.
  • MultiProtocol Label Switching (MPLS) for example.
• In addition to virtual circuits, label switching allows for quality of service control.

Set-Up Trade-Offs

• How much does it cost to set-up vs route packets?
• Datagram networks
  • require no set-up, but
  • each router does a full-address look-up.
• Virtual-circuit networks
  • expensive set-up, but
  • routers are much simplified.
• NPDU size too.

Comparison

		Datagram		Circuit
Issue		Network		Network
Circuits		None		Required
Addressing		Full		VC ids
State		None		Lots
Routing		Each		Once
Failure		Benign		Fatal
QoS		Hard		Easy
Congestion		Hard		Easy

Summary

• The network layer is the last-chance for end-to-end networking.
  • For small networks.
• Network services are circumscribed by datagram or virtual-circuit networks.
  • How much work should the network do?
• The principle internal network-layer function is routing.
  • And maintaining the routing machinery.

References

• End-To-End Arguments in System Design by Jerome Saltzer, David Reed, and David Clark in ACM Transactions in Computer Systems, November, 1984.
• The Dawn of the Stupid Network by David Isenberg in ACM netWorker, February-March, 1998.
• Tussle in Cyberspace: Defining Tomorrow’s Internet by David Clark, John Wroclawski, Karen Sollins, and Robert Braden in Transactions on Networking, June, 2005.

---

This page last modified on 2012 October 9.