Srinivasan Keshav - Mathematical Foundations of Computer Networking

Srinivasan Keshav

Upper Saddle River, NJ Boston Indianapolis San Francisco
New York Toronto Montreal London Munich Paris Madrid
Capetown Sydney Tokyo Singapore Mexico City

Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed with initial capital letters or in all capitals.

The author and publisher have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibility for errors or omissions. No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein.

The publisher offers excellent discounts on this book when ordered in quantity for bulk purchases or special sales, which may include electronic versions and/or custom covers and content particular to your business, training goals, marketing focus, and branding interests. For more information, please contact:

U.S. Corporate and Government Sales
(800) 382-3419

For sales outside the United States, please contact:

International Sales

Visit us on the Web: informit.com/aw

Library of Congress Cataloging-in-Publication Data
Keshav, Srinivasan.
Mathematical foundations of computer networking / Srinivasan Keshav.
p. cm.
Includes index.
ISBN 978-0-321-79210-5 (pbk. : alk. paper)ISBN 0-321-79210-6 (pbk. : alk. paper) 1. Computer networksMathematicsTextbooks. I. Title.
TK5105.5.K484 2012
004.601519dc23
2011052203

Editor-in-Chief
Mark L. Taub

Senior Acquisitions Editor
Trina MacDonald

Managing Editor
John Fuller

Full-Service Production Manager
Julie B. Nahil

Copy Editor
Evelyn Pyle

Indexer
Ted Laux

Proofreader
Linda Begley

Technical Reviewers
Alan Kaplan
Abraham Matta
Johnny Wong

Publishing Coordinator
Olivia Basegio

Compositor
Rob Mauhar

Copyright 2012 Pearson Education, Inc.

All rights reserved. Printed in the United States of America. This publication is protected by copyright, and permission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, One Lake Street, Upper Saddle River, New Jersey 07458, or you may fax your request to (201) 236-3290.

ISBN-13: 978-0-321-79210-5
ISBN-10: 0-321-79210-6
Text printed in the United States on recycled paper at RR Donnelley in Crawfordsville, Indiana.
First printing, April 2012

Graduate students, researchers, and professionals in the field of computer networking often require a firm conceptual understanding of its theoretical foundations. Knowledge of optimization, information theory, game theory, control theory, and queueing theory is assumed by research papers in the field. Yet these subjects are not taught in a typical computer science undergraduate curriculum. This leaves only two alternatives: to either study these topics on ones own from standard texts or take a remedial course. Neither alternative is attractive. Standard texts pay little attention to computer networking in their choice of problem areas, making it a challenge to map from the text to the problem at hand, and it is inefficient to require students to take an entire course when all that is needed is an introduction to the topic.

This book addresses these problems by providing a single source to learn about the mathematical foundations of computer networking. Assuming only a rudimentary grasp of calculus, the book provides an intuitive yet rigorous introduction to a wide range of mathematical topics. The topics are covered in sufficient detail so that the book will usually serve as both the first and ultimate reference. Note that the topics are selected to be complementary to those found in a typical undergraduate computer science curriculum. The book, therefore, does not cover network foundations, such as discrete mathematics, combinatorics, or graph theory.

Each concept in the book is described in four ways: intuitively, using precise mathematical notation, providing a carefully chosen numerical example, and offering a numerical exercise to be done by the reader. This progression is designed to gradually deepen understanding. Nevertheless, the depth of coverage provided here is not a substitute for that found in standard textbooks. Rather, I hope to provide enough intuition to allow a student to grasp the essence of a research paper that uses these theoretical foundations.

The chapters in this book fall into two broad categories: foundations and theories. The first five chapters are foundational, covering probability, statistics, linear algebra, optimization, and signals, systems, and transforms. These chapters provide the basis for the four theories covered in the latter half of the book: queueing theory, game theory, control theory, and information theory. Each chapter is written to be as self-contained as possible. Nevertheless, some dependencies do exist, as shown in , where dashed arrows show weak dependencies and solid arrows show strong dependencies.

Figure P.1. Chapter organization

The material in this book can be completely covered in a sequence of two graduate courses, with the first course focusing on the first five chapters and the second course on the latter four. For a single-semester course, some possible alternatives are to cover

Probability, statistics, queueing theory, and information theory

Linear algebra; signals, systems, and transforms; control theory; and game theory

Linear algebra; signals, systems, and transforms; control theory; selected portions of probability; and information theory

Linear algebra; optimization, probability, queueing theory, and information theory

This book is designed for self-study. Each chapter has numerous solved examples and exercises to reinforce concepts. My aim is to ensure that every topic in the book is accessible to the perservering reader.

I have benefited immensely from the comments of dedicated reviewers on drafts of this book. Two reviewers in particular who stand out are Alan Kaplan, whose careful and copious comments improved every aspect of the book, and Johnny Wong, who not only reviewed multiple drafts of the chapters on probability and statistics but also used a draft to teach two graduate courses at the University of Waterloo.

I would also like to acknowledge the support I received from experts who reviewed individual chapters: Augustin Chaintreau, Columbia (probability and queueing theory); Tom Coleman, Waterloo (optimization); George Labahn, Waterloo (linear algebra); Kate Larson, Waterloo (game theory); Abraham Matta, Boston University (statistics; signals, systems, and transforms; and control theory); Sriram Narasimhan, Waterloo (control theory); and David Tse, UC Berkeley (information theory).