Computer Networking Lecture Notes

14 March 2013 \(\pi\) The Network Layer

---

Outline

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

Objectives

Starting from here Get to here

Local Area Networks

• We’ve already seen these.

  

• These are local area networks (LANs).
• We have networks, are we done?

LAN Characteristics

• LANs have limited capabilities.
  • Distances, population, data rates, loads.
• LAN structure is too simple.
  • All for one and one for all doesn’t scale well.
  • A department LAN fits well, a company LAN less so.
• The network layer organizes LANs into capable, scalable networks.

Combining LANs

• The network layer starts when LANs are combined.
  • Forming larger, more scalable, better structured networks.
• There are several layers at which LANs can be combined.

  Physical layer:		hubs
  Data-link layer:		bridges and switches
  Network layer:		routers

Hubs

• A hub (or repeater) is a physical-layer device for connecting LANs.

  

• A hub forms two or more LAN segments into a single LAN.

Hub Characteristics

• A hub is a passive device, providing little more than signal continuity.
  • It may regenerate the signal.
• Hubs are cheap, simple, reliable devices.
  • And easy to deploy.

  The hub can be the LAN medium. Multiple hubs can form hierarchical LANs.

Hub Observations

• Hubs bump up against LAN growth limits.
• Passive, physical-layer hubs can’t compensate for LAN differences.
• The combined LAN is as structured just like the component segments.
• Maintaining combined LANs is harder than maintaining each segment separately.
• Hubs reduce parallel LAN resources to serial LAN resources.

Requirements

• A combining device capable of doing better than hubs should
  • Combine LANs, but maintain LAN autonomy.
  • Allow for richer interconnection structures.
  • Be able to smooth over (perhaps minor) LAN differences.
  • Be scalable.
• A bridge is a data-link layer device capable of meeting these requirements.

Bridges

• A bridge copies frames from one LAN to another.
• A bridge contains
  • A small processor to manipulate frames,
  • some buffer storage to hold frames, and
  • a bridge table to direct frame copies.
• A bridge is an active device with knowledge of the MAC layer.

Bridge Table

• A bridge table is a list entries, which are three-tuples

  (MAC address, output port, access time).

  • MAC address: host X's LAN address.
  • Output port: the LAN associated with host X.
  • Access time: the last time entry was read or written.
• An entry not accessed for some time is dropped from the table.

Successful Look-up

• A frame for destination D arrives at port i.
• D's bridge-table entry has output port o.
  • D's entry access time is updated.
• If o ≠ i, the frame is forwarded to the LAN on port o.
• If o = i, the frame is dropped (filtered).

Unsuccessful Look-up

• A frame for destination D arrives at port i.
• There is no bridge-table entry for D's MAC address.
• The bridge forwards the frame on all ports other than port i.
  • The frame is broadcast by the bridge.

  

Bridge Table Discovery

• A bridge opportunistically maintains its bridge table.
• A frame from S arrives at port i.
• If S doesn’t have bridge table entry, add one.
• Otherwise, update the output port (if needed) and access time fields of S's entry.
• Old entries can be culled periodically, or when accessed.

Bridged Network Architectures

• A LAN may have several bridges attached.
  • And a bridge may be attached to several LANs.

  Useful for creating complex network structures. Redundant bridges per LAN improves reliability.

Troublesome Topology

X sends a frame to Y. Y has not sent a frame to any host for some time.

• What happens to X's frame?
• Unrestricted frame duplication results in a broadcast storm.
• Cycles in the network graph can lead to exponential frame duplication.

Avoiding Trouble

• A dilemma:
  • Efficient and reliable networks should have redundant paths.
  • Redundant paths may form cycles, which can form packet storms.
• Bridges resolve this dilemma by imposing a safe path structure on a redundant network.
• Bridges do this automatically and repeatedly in response to changing conditions.

Spanning Tree

• Bridges create a spanning tree over the network graph.
• A spanning tree over graph G is
  • A subset of graph G that
  • contains every edge (LAN) of G and
  • is a tree.
• The tree edges are LANs in the network.
• Bridges only forward frames over LANs that are part of the spanning tree.

Spanning Tree Example

Bridge Observations

• A bridge
  • maintains LAN autonomy.
  • interconnects LANs in almost arbitrary ways.
  • can modify frames in transit.
  • scales up to a point.
• However, spanning tree paths are not opportunistic, and don't load-share well.

Switches

• A bridge participates in any MAC protocols being used by the LANs.
  • For example, a bridge on a CSMA/CD MAC.
• This complicates bridges, increasing their costs.
• Adding more ports, more buffering, and more processor turns a bridge into a switch.
• Switches implement LANs as well as interconnect them.
• Switches can interconnect with bridges and hubs.

Switch Operation

With one host per port, no link contention. However: propagation-delay collisions.

• Host exchange is done in the switch
• Buffering resolves link contention in the switch.
• High-speed Ethernets simplify CSMA/CD with switching.
• Also: enhanced privacy, full-duplex traffic.

Network Structure

• The current structure of a network is

  

Network 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.

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.

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.

Summary

References

• Interconnections by Radia Perlman, Addison-Wesley, 1999.

---

This page last modified on 2013 March 14.