`
`PALO ALTO NETWORKS Exhibit 1026 Page 1
`
`
`
`Acquiring Editor: Rick Adams
`Development Editor: Nate McFadden
`Project Manager: Paul Gottehrer
`Designer: Dennis Schaefer
`
`Morgan Kaufmann is an imprint of Elsevier
`30 Corporate Drive, Suite 400, Burlington, MA 01803, USA
`
`© 2012 Elsevier, Inc. All rights reserved.
`
`No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical,
`including photocopying, recording, or any information storage and retrieval system, without permission in writing
`from the publisher. Details on how to seek permission, further information about the Publisher’s permissions policies
`and our arrangements with organizations such as the Copyright Clearance Center and the Copyright Licensing
`Agency, can be found at our website: www.elsevier.com/permissions.
`
`This book and the individual contributions contained in it are protected under copyright by the Publisher (other than
`as may be noted herein).
`
`Notices
`Knowledge and best practice in this field are constantly changing. As new research and experience broaden our
`understanding, changes in research methods or professional practices, may become necessary. Practitioners and
`researchers must always rely on their own experience and knowledge in evaluating and using any information or
`methods described herein. In using such information or methods they should be mindful of their own safety and the
`safety of others, including parties for whom they have a professional responsibility.
`
`To the fullest extent of the law, neither the Publisher nor the authors, contributors, or editors, assume any liability for
`any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from
`any use or operation of any methods, products, instructions, or ideas contained in the material herein.
`
`Library of Congress Cataloging-in-Publication Data
`Peterson, Larry L.
`Computer networks : a systems approach / Larry L. Peterson and Bruce S. Davie. – 5th ed.
`p. cm. – (The Morgan Kaufmann series in networking)
`Includes bibliographical references.
`ISBN 978-0-12-385059-1 (hardback)
`1. Computer networks. I. Davie, Bruce S. II. Title.
`TK5105.5.P479 2011
`004.6–dc22
`
`2011000786
`
`British Library Cataloguing-in-Publication Data
`A catalogue record for this book is available from the British Library.
`
`ISBN: 978-0-12-385059-1
`
`For information on all Morgan Kaufmann publications
`visit our website at www.mkp.com
`
`Typeset by: diacriTech, India
`
`Printed in the United States of America
`11 12 13 14 15 16 10 9 8 7 6 5 4 3 2
`
`PALO ALTO NETWORKS Exhibit 1026 Page 2
`
`
`
`318
`
`CHAPTER 4 Advanced internetworking
`
`autonomous systems. It is common to find that border routers are also
`BGP speakers, but that does not have to be the case.
`
`BGP does not belong to either of the two main classes of routing pro-
`tocols (distance-vector and link-state protocols) described in Section 3.3.
`Unlike these protocols, BGP advertises complete paths as an enumerated
`list of autonomous systems to reach a particular network. It is sometimes
`called a path-vector protocol for this reason. The advertisement of com-
`plete paths is necessary to enable the sorts of policy decisions described
`above to be made in accordance with the wishes of a particular AS. It also
`enables routing loops to be readily detected.
`
`To see how this works, consider the very simple example network in
`Figure 4.5. Assume that the providers are transit networks, while the
`customer networks are stubs. A BGP speaker for the AS of provider A
`(AS 2) would be able to advertise reachability information for each of
`the network numbers assigned to customers P and Q. Thus, it would say,
`in effect, “The networks 128.96, 192.4.153, 192.4.32, and 192.4.3 can be
`reached directly from AS 2.” The backbone network, on receiving this
`advertisement, can advertise, “The networks 128.96, 192.4.153, 192.4.32,
`and 192.4.3 can be reached along the path (cid:2)AS 1, AS 2(cid:3).” Similarly, it could
`advertise, “The networks 192.12.69, 192.4.54, and 192.4.23 can be reached
`along the path (cid:2)AS 1, AS 3(cid:3).”
`
`An important job of BGP is to prevent the establishment of loop-
`ing paths. For example, consider the network illustrated in Figure 4.6. It
`differs from Figure 4.5 only in the addition of an extra link between AS 2
`
`Backbone network
`(AS 1)
`
`Regional provider A
`(AS 2)
`
`Regional provider B
`(AS 3)
`
`Customer P
`(AS 4)
`
`128.96
`192.4.153
`
`Customer Q
`(AS 5)
`
`192.4.32
`192.4.3
`
`Customer R
`(AS 6)
`
`192.12.69
`
`Customer S
`(AS 7)
`
`192.4.54
`192.4.23
`
`I FIGURE 4.5 Example of a network running BGP.
`
`PALO ALTO NETWORKS Exhibit 1026 Page 3
`
`
`
`4.1 The global internet
`
`319
`
`Backbone network
`(AS 1)
`
`Regional provider A
`(AS 2)
`
`Regional provider B
`(AS 3)
`
`Customer P
`(AS 4)
`
`128.96
`
`Customer Q
`(AS 5)
`
`Customer R
`(AS 6)
`
`Customer S
`(AS 7)
`
`I FIGURE 4.6 Example of loop among autonomous systems.
`
`and AS 3, but the effect now is that the graph of autonomous systems has
`a loop in it. Suppose AS 1 learns that it can reach network 128.96 through
`AS 2, so it advertises this fact to AS 3, who in turn advertises it back to
`AS 2. In the absence of any loop prevention mechanism, AS 2 could now
`decide that AS 3 was the preferred route for packets destined for 128.96. If
`AS 2 starts sending packets addressed to 128.96 to AS 3, AS 3 would send
`them to AS 1; AS 1 would send them back to AS 2; and they would loop
`forever. This is prevented by carrying the complete AS path in the routing
`messages. In this case, the advertisement for a path to 128.96 received by
`AS 2 from AS 3 would contain an AS path of (cid:2)AS 3, AS 1, AS 2, AS 4(cid:3). AS 2
`sees itself in this path, and thus concludes that this is not a useful path for
`it to use.
`
`In order for this loop prevention technique to work, the AS numbers
`carried in BGP clearly need to be unique. For example, AS 2 can only
`recognize itself in the AS path in the above example if no other AS iden-
`tifies itself in the same way. AS numbers have until recently been 16-bit
`numbers, and they are assigned by a central authority to assure unique-
`ness. While 16 bits only allows about 65,000 autonomous systems, which
`might not seem like a lot, we note that a stub AS does not need a unique
`AS number, and this covers the overwhelming majority of nonprovider
`networks.2
`
`232-bit AS numbers have also been defined and came into use around 2009, thus
`ensuring that AS number space will not become a scarce resource.
`
`PALO ALTO NETWORKS Exhibit 1026 Page 4