rfc2328.hastabs.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 1,627 行 · 第 1/5 页

	       N7|  |  |  |  |	|  |  |4 |  |  |  |  |	|  |  |	 |
	       N8|  |  |  |  |	|  |  |	 |  |3 |2 |  |	|  |  |	 |
	       N9|  |  |  |  |	|  |  |	 |1 |  |1 |1 |	|  |  |	 |
	      N10|  |  |  |  |	|  |  |	 |  |  |  |2 |	|  |  |	 |
	      N11|  |  |  |  |	|  |  |	 |3 |  |  |  |	|  |  |	 |
	      N12|  |  |  |  |8	|  |2 |	 |  |  |  |  |	|  |  |	 |
	      N13|  |  |  |  |8	|  |  |	 |  |  |  |  |	|  |  |	 |
	      N14|  |  |  |  |8	|  |  |	 |  |  |  |  |	|  |  |	 |
	      N15|  |  |  |  |	|  |9 |	 |  |  |  |  |	|  |  |	 |
	       H1|  |  |  |  |	|  |  |	 |  |  |  |10|	|  |  |	 |


		     Figure 3: The resulting directed graph

		 Networks and routers are represented by vertices.
		 An edge of cost X connects Vertex A to	Vertex B iff
		 the intersection of Column A and Row B	is marked
				     with an X.



Moy			    Standards Track		       [Page 20]

RFC 2328		     OSPF Version 2		      April 1998


		     **FROM**			    **FROM**

		  |RT12|N9|N10|H1|		   |RT9|RT11|RT12|N9|
	   *  --------------------	    *  ----------------------
	   *  RT12|    |  |   |	 |	    *	RT9|   |    |	 |0 |
	   T	N9|1   |  |   |	 |	    T  RT11|   |    |	 |0 |
	   O   N10|2   |  |   |	 |	    O  RT12|   |    |	 |0 |
	   *	H1|10  |  |   |	 |	    *	 N9|   |    |	 |  |
	   *				    *
		RT12's router-LSA	       N9's network-LSA

		  Figure 4: Individual link state components

	      Networks and routers are represented by vertices.
	      An edge of cost X	connects Vertex	A to Vertex B iff
	      the intersection of Column A and Row B is	marked
				  with an X.

    2.2.  The shortest-path tree

	When no	OSPF areas are configured, each	router in the Autonomous
	System has an identical	link-state database, leading to	an
	identical graphical representation.  A router generates	its
	routing	table from this	graph by calculating a tree of shortest
	paths with the router itself as	root.  Obviously, the shortest-
	path tree depends on the router	doing the calculation.	The
	shortest-path tree for Router RT6 in our example is depicted in
	Figure 5.

	The tree gives the entire path to any destination network or
	host.  However,	only the next hop to the destination is	used in
	the forwarding process.	 Note also that	the best route to any
	router has also	been calculated.  For the processing of	external
	data, we note the next hop and distance	to any router
	advertising external routes.  The resulting routing table for
	Router RT6 is pictured in Table	2.  Note that there is a
	separate route for each	end of a numbered point-to-point network
	(in this case, the serial line between Routers RT6 and RT10).


	Routes to networks belonging to	other AS'es (such as N12) appear
	as dashed lines	on the shortest	path tree in Figure 5.	Use of



Moy			    Standards Track		       [Page 21]

RFC 2328		     OSPF Version 2		      April 1998



				RT6(origin)
		    RT5	o------------o-----------o Ib
		       /|\    6	     |\	    7
		     8/8|8\	     | \
		     /	|  \	    6|	\
		    o	|   o	     |	 \7
		   N12	o  N14	     |	  \
		       N13	  2  |	   \
			    N4 o-----o RT3  \
				    /	     \	  5
				  1/	 RT10 o-------o	Ia
				  /	      |\
		       RT4 o-----o N3	     3|	\1
				/|	      |	 \ N6	  RT7
			       / |	   N8 o	  o---------o
			      /	 |	      |	  |	   /|
			 RT2 o	 o RT1	      |	  |	 2/ |9
			    /	 |	      |	  |RT8	 /  |
			   /3	 |3	 RT11 o	  o	o   o
			  /	 |	      |	  |    N12 N15
		      N2 o	 o N1	     1|	  |4
					      |	  |
					   N9 o	  o N7
					     /|
					    / |
			N11	 RT9	   /  |RT12
			 o--------o-------o   o--------o H1
			     3		      |	  10
					      |2
					      |
					      o	N10


		     Figure 5: The SPF tree for	Router RT6

	      Edges that are not marked	with a cost have a cost	of
	      of zero (these are network-to-router links). Routes
	      to networks N12-N15 are external information that	is
			 considered in Section 2.3





Moy			    Standards Track		       [Page 22]

RFC 2328		     OSPF Version 2		      April 1998


		   Destination	 Next  Hop   Distance
		   __________________________________
		   N1		 RT3	     10
		   N2		 RT3	     10
		   N3		 RT3	     7
		   N4		 RT3	     8
		   Ib		 *	     7
		   Ia		 RT10	     12
		   N6		 RT10	     8
		   N7		 RT10	     12
		   N8		 RT10	     10
		   N9		 RT10	     11
		   N10		 RT10	     13
		   N11		 RT10	     14
		   H1		 RT10	     21
		   __________________________________
		   RT5		 RT5	     6
		   RT7		 RT10	     8


    Table 2: The portion of Router RT6's routing table listing local
			     destinations.

	this externally	derived	routing	information is considered in the
	next section.


    2.3.  Use of external routing information

	After the tree is created the external routing information is
	examined.  This	external routing information may originate from
	another	routing	protocol such as BGP, or be statically
	configured (static routes).  Default routes can	also be	included
	as part	of the Autonomous System's external routing information.

	External routing information is	flooded	unaltered throughout the
	AS.  In	our example, all the routers in	the Autonomous System
	know that Router RT7 has two external routes, with metrics 2 and
	9.

	OSPF supports two types	of external metrics.  Type 1 external
	metrics	are expressed in the same units	as OSPF	interface cost



Moy			    Standards Track		       [Page 23]

RFC 2328		     OSPF Version 2		      April 1998


	(i.e., in terms	of the link state metric).  Type 2 external
	metrics	are an order of	magnitude larger; any Type 2 metric is
	considered greater than	the cost of any	path internal to the AS.
	Use of Type 2 external metrics assumes that routing between
	AS'es is the major cost	of routing a packet, and eliminates the
	need for conversion of external	costs to internal link state
	metrics.

	As an example of Type 1	external metric	processing, suppose that
	the Routers RT7	and RT5	in Figure 2 are	advertising Type 1
	external metrics.  For each advertised external	route, the total
	cost from Router RT6 is	calculated as the sum of the external
	route's	advertised cost	and the	distance from Router RT6 to the
	advertising router.  When two routers are advertising the same
	external destination, RT6 picks	the advertising	router providing
	the minimum total cost.	RT6 then sets the next hop to the
	external destination equal to the next hop that	would be used
	when routing packets to	the chosen advertising router.

	In Figure 2, both Router RT5 and RT7 are advertising an	external
	route to destination Network N12.  Router RT7 is preferred since
	it is advertising N12 at a distance of 10 (8+2)	to Router RT6,
	which is better	than Router RT5's 14 (6+8).  Table 3 shows the
	entries	that are added to the routing table when external routes
	are examined:



			 Destination   Next  Hop   Distance
			 __________________________________
			 N12	       RT10	   10
			 N13	       RT5	   14
			 N14	       RT5	   14
			 N15	       RT10	   17


		 Table 3: The portion of Router	RT6's routing table
			   listing external destinations.


	Processing of Type 2 external metrics is simpler.  The AS
	boundary router	advertising the	smallest external metric is



Moy			    Standards Track		       [Page 24]

RFC 2328		     OSPF Version 2		      April 1998


	chosen,	regardless of the internal distance to the AS boundary
	router.	 Suppose in our	example	both Router RT5	and Router RT7
	were advertising Type 2	external routes.  Then all traffic
	destined for Network N12 would be forwarded to Router RT7, since
	2 < 8.	When several equal-cost	Type 2 routes exist, the
	internal distance to the advertising routers is	used to	break
	the tie.

	Both Type 1 and	Type 2 external	metrics	can be present in the AS
	at the same time.  In that event, Type 1 external metrics always
	take precedence.

	This section has assumed that packets destined for external
	destinations are always	routed through the advertising AS
	boundary router.  This is not always desirable.	 For example,
	suppose	in Figure 2 there is an	additional router attached to
	Network	N6, called Router RTX.	Suppose	further	that RTX does
	not participate	in OSPF	routing, but does exchange BGP
	information with the AS	boundary router	RT7.  Then, Router RT7
	would end up advertising OSPF external routes for all
	destinations that should be routed to RTX.  An extra hop will
	sometimes be introduced	if packets for these destinations need
	always be routed first to Router RT7 (the advertising router).

	To deal	with this situation, the OSPF protocol allows an AS
	boundary router	to specify a "forwarding address" in its AS-
	external-LSAs.	In the above example, Router RT7 would specify
	RTX's IP address as the	"forwarding address" for all those
	destinations whose packets should be routed directly to	RTX.

	The "forwarding	address" has one other application.  It	enables
	routers	in the Autonomous System's interior to function	as
	"route servers".  For example, in Figure 2 the router RT6 could
	become a route server, gaining external	routing	information
	through	a combination of static	configuration and external
	routing	protocols.  RT6	would then start advertising itself as
	an AS boundary router, and would originate a collection	of OSPF
	AS-external-LSAs.  In each AS-external-LSA, Router RT6 would
	specify	the correct Autonomous System exit point to use	for the
	destination through appropriate	setting	of the LSA's "forwarding
	address" field.




Moy			    Standards Track		       [Page 25]

RFC 2328		     OSPF Version 2		      April 1998


    2.4.  Equal-cost multipath

	The above discussion has been simplified by considering	only a
	single route to	any destination.  In reality, if multiple
	equal-cost routes to a destination exist, they are all
	discovered and used.  This requires no conceptual changes to the
	algorithm, and its discussion is postponed until we consider the
	tree-building process in more detail.

	With equal cost	multipath, a router potentially	has several
	available next hops towards any	given destination.


3.  Splitting the AS into Areas

    OSPF allows	collections of contiguous networks and hosts to	be
    grouped together.  Such a group, together with the routers having
    interfaces to any one of the included networks, is called an area.
    Each area runs a separate copy of the basic	link-state routing
    algorithm.	This means that	each area has its own link-state
    database and corresponding graph, as explained in the previous
    section.

    The	topology of an area is invisible from the outside of the area.
    Conversely,	routers	internal to a given area know nothing of the
    detailed topology external to the area.  This isolation of knowledge
    enables the	protocol to effect a marked reduction in routing traffic
    as compared	to treating the	entire Autonomous System as a single
    link-state domain.

    With the introduction of areas, it is no longer true that all
    routers in the AS have an identical	link-state database.  A	router
    actually has a separate link-state database	for each area it is
    connected to.  (Routers connected to multiple areas	are called area
    border routers).  Two routers belonging to the same	area have, for
    that area, identical area link-state databases.

    Routing in the Autonomous System takes place on two	levels,
    depending on whether the source and	destination of a packet	reside
    in the same	area (intra-area routing is used) or different areas
    (inter-area	routing	is used).  In intra-area routing, the packet is
    routed solely on information obtained within the area; no routing



Moy			    Standards Track		       [Page 26]

RFC 2328		     OSPF Version 2		      April 1998