ECE 567
ECE 567 - Communication Network Analysis
Fall 2021
Title | Rubric | Section | CRN | Type | Hours | Times | Days | Location | Instructor |
---|---|---|---|---|---|---|---|---|---|
Communication Network Analysis | ECE567 | C | 29998 | DIS | 4 | 1230 - 1350 | T R | 3015 Electrical & Computer Eng Bldg | Rayadurgam Srikant |
See full schedule from Course Explorer
Official Description
Performance analysis and design of multiple-user communication systems; emphasis on rigorous formulation and analytical and computational methods; includes queuing networks, decentralized minimum delay routing, and dynamic network flow control. Course Information: Prerequisite: CS 438; one of ECE 534, MATH 464, MATH 564.
Subject Area
- Networking and Distributed Computing
Course Director
Description
First high-level course in performance analysis and design of multiple-user communication systems; emphasizes rigorous formulation and analytical and computational methods; includes queuing networks, decentralized minimum delay routing and dynamic network flow control.
Topics
- Mathematical preliminaries: discrete state Markov chains (MCs); local description of MCs in discrete time, example; continuous-time local structure; space-time structure of MCs; Poisson processes; renewal theory; classification and convergence of MCs - discrete time; classification and convergence of MCs - continuous time; Littles law, M/M/1 queues, queues modelled as birth-death processes, distribution seen by arrivals; queues modelled by birth-death processes; M/G/1 queues by transform method; M/G/1 busy periods, leads to a branching process; M/G/1 queues by renewal theory method, priority queues; G/M/1 queues; G/G/1 queues, analysis and Kingman's bound; G/G/1 queues with vacations, applications to TDMA and FDMA
- Multiple access: ALOHA multiple access; ALOHA with decentralized control; drift analysis, beginning of tree algorithms; tree algorithms; queues with periodic arrivals/ATM systems
- Routing and flow control in networks: time-reverse of Markov process and reversible Markov process; tree condition, truncation and circuit switching model; a network of queues in series and output processes; open and closed networks with random routing; throughput in closed networks with random routing (with application to input buffering in a crossbar packet switch); Norton's equivalent for closed networks, product form Markov network with multiple customer types and deterministic routes; routing and flow control issues, virtual circuit and datagram routing tables, ARPANET routing updates; basic graph concepts, Prim-Dijkstra and Kruskals algorithm for MWST, Bellman-Ford algorithm for shortest path problem; Dijkstra's shortest path algorithm, optimal static routing; flow deviation algorithm; matching problem, algorithm for bipartite matching, max-flow problem; maximum flow and network reliability; min-max fair allocation of network flows; regulation of bursty traffic - generalized round robin and leaky bucket regulators; dynamic routing - fluid model, dynamic programming, diffusion model
Detailed Description and Outline
Topics:
- Mathematical preliminaries: discrete state Markov chains (MCs); local description of MCs in discrete time, example; continuous-time local structure; space-time structure of MCs; Poisson processes; renewal theory; classification and convergence of MCs - discrete time; classification and convergence of MCs - continuous time; Littles law, M/M/1 queues, queues modelled as birth-death processes, distribution seen by arrivals; queues modelled by birth-death processes; M/G/1 queues by transform method; M/G/1 busy periods, leads to a branching process; M/G/1 queues by renewal theory method, priority queues; G/M/1 queues; G/G/1 queues, analysis and Kingman's bound; G/G/1 queues with vacations, applications to TDMA and FDMA
- Multiple access: ALOHA multiple access; ALOHA with decentralized control; drift analysis, beginning of tree algorithms; tree algorithms; queues with periodic arrivals/ATM systems
- Routing and flow control in networks: time-reverse of Markov process and reversible Markov process; tree condition, truncation and circuit switching model; a network of queues in series and output processes; open and closed networks with random routing; throughput in closed networks with random routing (with application to input buffering in a crossbar packet switch); Norton's equivalent for closed networks, product form Markov network with multiple customer types and deterministic routes; routing and flow control issues, virtual circuit and datagram routing tables, ARPANET routing updates; basic graph concepts, Prim-Dijkstra and Kruskals algorithm for MWST, Bellman-Ford algorithm for shortest path problem; Dijkstra's shortest path algorithm, optimal static routing; flow deviation algorithm; matching problem, algorithm for bipartite matching, max-flow problem; maximum flow and network reliability; min-max fair allocation of network flows; regulation of bursty traffic - generalized round robin and leaky bucket regulators; dynamic routing - fluid model, dynamic programming, diffusion model
Topical Prerequisites
CS 438; one of ECE 534, MATH 464, MATH 564.
Texts
D. Bertsekas and R.G. Gallager, Data Networks, 2nd ed., Prentice-Hall, 1992.
Collateral reading:
Material from selected journal articles and books.
Last updated
2/13/2013