ECE 567 - Communication Network Analysis

Semesters Offered

TitleRubricSectionCRNTypeTimesDaysLocationInstructor
Communication Network AnalysisECE567C39337DIS1400 - 1520 T R  3013 ECE Building Rayadurgam Srikant

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.

Prerequisites

Credit in CS 438
Credit in ECE 534 or MATH 464 or MATH 564

Subject Area

Networking and Distributed Computing

Course Directors

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 Prerequisities

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