R. E. Newman-Wolfe
, University of Florida
Last modified 3/15/95.
Packet Switching
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.
This page considers packet-switching and compares packet-switching
with circuit-switching.
---------------------
1. Properties - Graph theory
i. Definitions
ii. Algorithms
a. Shortest Path
b. Max-Flow
c. Connectivity
2. Topopogy Design
i. Algorithms
a. MST
b. Link-deficit
ii. Switching design
a. Message-switching
b. Circuit-switching
c. Packet-switching
3. Analysis
i. Queuing Theory - delay
ii. Traffic analysis & delay
4. Services v.s. Implementation
i. Virtual Circuit
ii. Datagrams
iii. Examples
a. VC/VC - SNA
b. VC/DG - Arpanet
c. DG/DG - DNA
5. Routing
i. Objectives
ii. Classification
a. Adaptive
b. Non-adaptive
c. Centralized
d. Distributed
e. Isolated
iii. Non-adaptive Algorithms
a. Static - Directory Routing
1. Sink tree
b. Random
c. Probabilistic
d. Flooding
e. Selective Flooding
iv. Adaptive Algorithms
a. Centralized
1. Status-based
2. Delta Routing
b. Isolated
1. Hot potato
2. Combined with static routing
3. Backward Learning
c. Distributed
1. Optomistic
2. Hold-down
3. Chu's Algorithm
4. Dynamic Sink Trees
v. Hierarchical Routing
a. Need
b. Technique
c. Optimal number of levels, nodes per level
d. Costs
vi. Broadcast Routing
a. Need
b. Techniques
1. Flooding
2. Multi-casting
3. Spanning Tree
4. Reverse Path Forwarding (Approx. ST)
6. Traffic Control
Methods -
dropping, rerouting, admission control
i. Flow Control
ii. Congestion Control
a. Deadlock
1. Direct
2. Indirect
3. Reassembly Lockup
b. By Circuit
1. Flow Control
2. Pre-allocation
3. Choke Packets
c. Global
1. Isarithmic
---------------------
The
next page
describes local area network (LAN) and metropolitan area network (MAN)
protocols, and analyzes them.
This document is
copyright 1995
by Richard E. Newman-Wolfe.
Send comments to nemo@cis.ufl.edu