RFC4063 日本語訳

Network Working Group                                          V. Manral
Request for Comments: 4063                                  SiNett Corp.
Category: Informational                                         R. White
                                                           Cisco Systems
                                                               A. Shaikh
                                                    AT&T Labs (Research)
                                                              April 2005

Manralがコメントのために要求するワーキンググループV.をネットワークでつないでください: 4063年のSiNett社のカテゴリ: 情報のR.の白いシスコシステムズA.Shaikh AT&T研究室(研究)2005年4月

      Considerations When Using Basic OSPF Convergence Benchmarks

問題、基本的なOSPF集合ベンチマークを使用します。

Status of This Memo

このメモの状態

   This memo provides information for the Internet community.  It does
   not specify an Internet standard of any kind.  Distribution of this
   memo is unlimited.

このメモはインターネットコミュニティのための情報を提供します。 それはどんな種類のインターネット標準も指定しません。 このメモの分配は無制限です。

Copyright Notice

版権情報

   Copyright (C) The Internet Society (2005).

Copyright(C)インターネット協会(2005)。

Abstract

要約

   This document discusses the applicability of various tests for
   measuring single router control plane convergence, specifically in
   regard to the Open Shortest First (OSPF) protocol.  There are two
   general sections in this document, the first discusses advantages and
   limitations of specific OSPF convergence tests, and the second
   discusses more general pitfalls to be considered when routing
   protocol convergence is tested.

このドキュメントは測定のただ一つのルータコントロール飛行機集合のための様々なテストの適用性について議論します、特にオープンShortest First(OSPF)プロトコルに関して。 2つの一般的なセクションが本書ではあって、ルーティング・プロトコル集合がテストされると考えられて、1番目は集合がテストして、2番目が、より一般的な落とし穴について議論する特定のOSPFの利点と限界について議論します。

1.  Introduction

1. 序論

   There is a growing interest in testing single router control plane
   convergence for routing protocols, and many people are looking at
   testing methodologies that can provide information on how long it
   takes for a network to converge after various network events occur.
   It is important to consider the framework within which any given
   convergence test is executed when one attempts to apply the results
   of the testing, since the framework can have a major impact on the
   results.  For instance, determining when a network is converged, what
   parts of the router's operation are considered within the testing,
   and other such things will have a major impact on the apparent
   performance that routing protocols provide.

ルーティング・プロトコルのためのテストのただ一つのルータコントロール飛行機集合への増加している関心があります、そして、多くの人々が様々なネットワークイベントが起こった後にネットワークが一点に集まるにはどれくらいかかるかの情報を提供できるテスト方法論を見ています。 1つが、枠組みが結果に強い影響を持つことができるのでテストの結果を適用するのを試みるとどんな与えられた集合テストも実行される枠組みを考えるのは重要です。 例えば、ネットワークがいつ一点に集められるかを決定して、ルータの操作の部品がテスト、および他のそのようなものの中で考えられることはルーティング・プロトコルが提供する見かけの性能に強い影響を持つでしょう。

Manral, et al.               Informational                      [Page 1]

RFC 4063          Considerations in OSPF Benchmarking         April 2005

Manral、他 OSPFベンチマーキング2005年4月の情報[1ページ]のRFC4063問題

   This document describes in detail various benefits and pitfalls of
   tests described in [BENCHMARK].  It also explains how such
   measurements can be useful for providers and the research community.

このドキュメントは詳細に[BENCHMARK]で説明されたテストの様々な利益と落とし穴を説明します。 また、それで、そのような測定値がどうプロバイダーと研究団体の役に立つ場合があるかがわかります。

   NOTE: In this document, the word "convergence" refers to single
   router control plane convergence [TERM].

以下に注意してください。 本書では、「集合」という言葉はただ一つのルータコントロール飛行機集合[TERM]について言及します。

2.  Advantages of Such Measurement

2. そのような測定の利点

   o    To be able to compare the iterations of a protocol
        implementation.  It is often useful to be able to compare the
        performance of two iterations of a given implementation of a
        protocol in order to determine where improvements have been made
        and where further improvements can be made.

o プロトコル実現の繰り返しを比較できるように。 どこで改良をするか、そして、どこでさらなる改良をすることができるかを決定するためにプロトコルの与えられた実現の2つの繰り返しの性能を比較できるのはしばしば役に立ちます。

   o    To understand, given a set of parameters (network conditions),
        how a particular implementation on a particular device will
        perform.  For instance, if you were trying to decide the
        processing power (size of device) required in a certain location
        within a network, you could emulate the conditions that will
        exist at that point in the network and use the test described to
        measure the performance of several different routers.  The
        results of these tests can provide one possible data point for
        an intelligent decision.

o 1セットのパラメタ(ネットワーク状態)を考えて、特定の装置における特定の実現がどのように働くかを理解するために。 例えば、あなたが、処理能力(装置のサイズ)がネットワークの中で、ある位置で必要であると決めようとしているなら、その時ネットワークで存在する状態を見習って、いくつかの異なったルータの性能を測定するために説明されたテストは使用できるでしょうに。 これらのテストの結果は知的な決定に1つの可能なデータポイント提供されることができます。

        If the device being tested is to be deployed in a running
        network, using routes taken from the network where the equipment
        is to be deployed rather than some generated topology in these
        tests will yield results that are closer to the real performance
        of the device.  Care should be taken to emulate or take routes
        from the actual location in the network where the device will be
        (or would be) deployed.  For instance, one set of routes may be
        taken from an ABR, one set from an area 0 only router, various
        sets from stub area, another set from various normal areas, etc.

検査される装置が走行ネットワークで配備されるつもりであると、これらのテストでいくらかの発生しているトポロジーよりむしろ配備される設備がことであるネットワークから取られたルートを使用すると、より近くにある結果は装置の本当の性能に譲られるでしょう。 実際の場所から装置が配備される(または、あるでしょう)ネットワークでルートを見習うか、または取るために注意するべきです。 例えば、ABRから1セットのルートを取るかもしれなくて、領域0からルータだけで、様々な状態で設定されたのは様々な正常な領域からスタッブ領域、もう1セットなどからセットします。

   o    To measure the performance of an OSPF implementation in a wide
        variety of scenarios.

o さまざまなシナリオにおける、OSPF実現の性能を測定するために。

   o    To be used as parameters in OSPF simulations by researchers.  It
        may sometimes be required for certain kinds of research to
        measure the individual delays of each parameter within an OSPF
        implementation.  These delays can be measured using the methods
        defined in [BENCHMARK].

o 研究者によるOSPFシミュレーションにおけるパラメタとして使用されるために。 ある種類の調査がOSPF実現の中でそれぞれのパラメタの個々の遅れを測定するのにそれが時々必要であるかもしれません。 [BENCHMARK]で定義された方法を使用することでこれらの遅れを測定できます。

   o    To help optimize certain configurable parameters.  It may
        sometimes be helpful for operators to know the delay required
        for individual tasks in order to optimize the resource usage in
        the network.  For example, if the processing time on a router is

o 助けるには、ある構成可能なパラメタを最適化してください。 オペレータが、ネットワークでリソース用法を最適化して、遅れが個々のタスクに必要であることを知るのは、時々役立っているかもしれません。 例えば、aの処理時間であるなら、ルータはそうです。

Manral, et al.               Informational                      [Page 2]

RFC 4063          Considerations in OSPF Benchmarking         April 2005

Manral、他 OSPFベンチマーキング2005年4月の情報[2ページ]のRFC4063問題

        found to be x seconds, determining the rate at which to flood
        LSAs to that router would be helpful so as not to overload the
        network.

x秒になるように、そのルータへLSAsをあふれさせるのがネットワークを積みすぎないように役立っているレートを測定して、設立します。

3.  Assumptions Made and Limitations of Such Measurements

3. された仮定とそのような測定値の制限

   o    The interactions of convergence and forwarding; testing is
        restricted to events occurring within the control plane.
        Forwarding performance is the primary focus in [INTERCONNECT],
        and it is expected to be dealt with in work that ensues from
        [FIB-TERM].

o 集合と推進の相互作用。 テストは制御飛行機の中に起こる出来事に制限されます。 推進性能は[INTERCONNECT]の焦点です、そして、[FIB-TERM]から起こる仕事で対処されると予想されます。

   o    Duplicate LSAs are Acknowledged Immediately.  A few tests rely
        on the property that duplicate LSA Acknowledgements are not
        delayed but are done immediately.  However, if an implementation
        does not acknowledge duplicate LSAs immediately on receipt, the
        testing methods presented in [BENCHMARK] could give inaccurate
        measurements.

o 写しLSAsはAcknowledged Immediatelyです。 いくつかのテストがすぐに、していた状態で写しLSA Acknowledgementsは遅らせられませんが、ある特性を当てにします。 しかしながら、実現が領収書のすぐ上の写しLSAsを承認しないなら、[BENCHMARK]に提示されたテスト方法は不正確な測定値を与えるかもしれません。

   o    It is assumed that SPF is non-preemptive.  If SPF is implemented
        so that it can (and will be) preempted, the SPF measurements
        taken in [BENCHMARK] would include the times that the SPF
        process is not running, thus giving inaccurate measurements.
        ([BENCHMARK] measures the total time taken for SPF to run, not
        the amount of time that SPF actually spends on the device's
        processor.)

o SPFが非割込み型であると思われます。 先取りされて、SPFが実行できるように実行されるなら(そして、あるでしょう)、中に入れられたSPF測定値[BENCHMARK]はSPFの過程が走っていないという回を含んでいるでしょう、その結果、不正確な測定値を与えます。 ([BENCHMARK]はSPFが実際に装置のプロセッサに費やす時間ではなく、SPFが走るように取られた合計時を測定します。)

   o    Some implementations may be multithreaded or use a
        multiprocess/multirouter model of OSPF.  If because of this any
        of the assumptions made during measurement are violated in such
        a model, measurements could be inaccurate.

o いくつかの実現が、マルチスレッド化されるかもしれないか、またはaを使用します。OSPFの/「マルチ-ルータ」モデルを多重処理してください。 これによる測定の間にされた仮定のどれかがそのようなモデルで違反されるなら、測定値は不正確であるかもしれません。

   o    The measurements resulting from the tests in [BENCHMARK] may not
        provide the information required to deploy a device in a large-
        scale network.  The tests described focus on individual
        components of an OSPF implementation's performance, and it may
        be difficult to combine the measurements in a way that
        accurately depicts a device's performance in a large-scale
        network.  Further research is required in this area.

o [BENCHMARK]でのテストから生じる測定値は大きいスケールネットワークで装置を配備するのに必要である情報を提供しないかもしれません。 テストはOSPF実現の性能の個々の成分の焦点について説明しました、そして、大規模なネットワークで正確にその装置の性能について表現する方法で測定値を結合するのは難しいかもしれません。 さらなる研究がこの領域で必要です。

   o    The measurements described in [BENCHMARK] should be used with
        great care when comparing two different implementations of OSPF
        from two different vendors.  For instance, there are many other
        factors than convergence speed that need to be taken into
        consideration when comparing different vendors' products.  One
        difficulty is aligning the resources available on one device to
        the resources available on another.

o OSPFの2つの2つの異なった業者と異なった実現を比較するとき、[BENCHMARK]で説明された測定は細心の注意を払って使用されるべきです。 例えば、他の多くの要素が異なった業者の製品を比較するとき、考慮に入れられる必要がある集合速度よりあります。 1つの困難が1台の装置で別のもので利用可能なリソースに利用可能なリソースを並べています。

Manral, et al.               Informational                      [Page 3]

RFC 4063          Considerations in OSPF Benchmarking         April 2005

Manral、他 OSPFベンチマーキング2005年4月の情報[3ページ]のRFC4063問題

4.  Observations on the Tests Described in [BENCHMARK]

4. 中で説明されたテストの観測[ベンチマーク]

   Some observations recorded while implementing the tests described in
   [BENCHMARK] are noted in this section.

このセクションで[BENCHMARK]で説明されたテストを実行している間に記録されたいくつかの観測が注意されます。

4.1.  Measuring the SPF Processing Time Externally

4.1. 外部的にSPF処理時間を測定します。

   The most difficult test to perform is the external measurement of the
   time required to perform an SPF calculation because the amount of
   time between the first LSA that indicates a topology change and the
   duplicate LSA is critical.  If the duplicate LSA is sent too quickly,
   it may be received before the device being tested actually begins
   running SPF on the network change information.  If the delay between
   the two LSAs is too long, the device may finish SPF processing before
   receiving the duplicate LSA.  It is important to closely investigate
   any delays between the receipt of an LSA and the beginning of an SPF
   calculation in the tested device; multiple tests with various delays
   might be required to determine what delay needs to be used to measure
   the SPF calculation time accurately.

実行する中で最も難しいテストはトポロジー変化を示す最初のLSAと写しLSAの間の時間が重要であるのでSPF計算を実行するのに必要である現代の外部の測定です。 あまりにすばやく写しLSAを送るなら、検査される装置が実際にネットワーク変化情報でSPFを走らせ始める前にそれを受け取るかもしれません。 2LSAsの間の遅れが長過ぎるなら、写しLSAを受ける前に、装置はSPF処理を終えるかもしれません。 テストされた装置でLSAの領収書とSPF計算の始まりの間で密接にどんな遅れも調査するのは重要です。 様々な遅れがある複数のテストが、どんな遅れが、正確にSPF計算時間を測定するのに使用される必要であるかを決定するのに必要であるかもしれません。

   Some implementations may force two intervals, the SPF hold time and
   the SPF delay, between successive SPF calculations.  If an SPF hold
   time exists, it should be subtracted from the total SPF execution
   time.  If an SPF delay exists, it should be noted in the test
   results.

いくつかの実現が2回の間隔、SPF保持時間、およびSPF遅れを連続したSPF計算の間に強制するかもしれません。 SPF保持時間が存在しているなら、それは総SPF実行時間から引き算されるべきです。 SPF遅れが存在しているなら、試験の成績でそれに注意するべきです。

4.2.  Noise in the Measurement Device

4.2. 測定装置の雑音

   The device on which measurements are taken (not the device being
   tested) also adds noise to the test results, primarily in the form of
   delay in packet processing and measurement output.  The largest
   source of noise is generally the delay between the receipt of packets
   by the measuring device and the receipt of information about the
   packet by the device's output, where the event can be measured.  The
   following steps may be taken to reduce this sampling noise:

また、測定値が取られる装置(検査されないいずれの装置も)は主としてパケット処理と測定出力における、遅れの形で試験の成績に雑音を加えます。 一般に、雑音の最も大きい源は測定装置によるパケットの領収書と出来事を測定できる装置の出力によるパケットの情報の領収書の間の遅れです。 この標本抽出雑音を減少させるために以下の方法を取るかもしれません:

   o    Increasing the number of samples taken will generally improve
        the tester's ability to determine what is noise, and to remove
        it from the results.  This applies to the DUT as well.

o 一般に、取られたサンプルについて数を増やすのは何が雑音であるかを決定して、結果からそれを取り除くテスターの性能を改良するでしょう。 これはまた、DUTに適用されます。

   o    Try to take time-stamp for a packet as early as possible.
        Depending on the operating system being used on the box, one can
        instrument the kernel to take the time-stamp when the interrupt
        is processed.  This does not eliminate the noise completely, but
        at least reduces it.

o できるだけ早くパケットにタイムスタンプを取るようにしてください。 箱の上に使用されるオペレーティングシステムによって、1つは、中断が処理されるとき、タイムスタンプを取るためにカーネルに器具を取り付けることができます。 これは、完全に雑音を排除するというわけではありませんが、それを少なくとも減少させます。

   o    Keep the measurement box as lightly loaded as possible.  This
        applies to the DUT as well.

o 軽くロードされているとしての測定箱を可能に保ってください。 これはまた、DUTに適用されます。

Manral, et al.               Informational                      [Page 4]

RFC 4063          Considerations in OSPF Benchmarking         April 2005

Manral、他 OSPFベンチマーキング2005年4月の情報[4ページ]のRFC4063問題

   o    Having an estimate of noise can also be useful.

o また、雑音の見積りを持っているのも役に立つ場合があります。

   The DUT also adds noise to the measurement.

また、DUTは測定に雑音を加えます。

4.3.  Gaining an Understanding of the Implementation Improves
      Measurements

4.3. 実現の理解を獲得すると、測定値は改良されます。

   Although the tester will (generally) not have access to internal
   information about the OSPF implementation being tested using
   [BENCHMARK], the more thorough the tester's knowledge of the
   implementation is, the more accurate the results of the tests will
   be.  For instance, in some implementations, the installation of
   routes in local routing tables may occur while the SPF is being
   calculated, dramatically impacting the time required to calculate the
   SPF.

テスターが(一般に)[BENCHMARK]を使用することでテストされるOSPF実現の内部の情報に近づく手段を持ちませんが、実現に関するテスターの知識が徹底的であれば徹底的であるほど、テストの結果は、より正確になるでしょう。 例えば、SPFが計算されている間、いくつかの実現では、地方の経路指定テーブルのルートのインストールは起こるかもしれません、SPFについて計算するのに必要である時間に劇的に影響を与えて。

4.4.  Gaining an Understanding of the Tests Improves Measurements

4.4. テストの理解を獲得すると、測定値は改良されます。

   One method that can be used to become familiar with the tests
   described in [BENCHMARK] is to perform the tests on an OSPF
   implementation for which all the internal details are available.
   Although there is no assurance that any two implementations will be
   similar, this will provide a better understanding of the tests
   themselves.

[BENCHMARK]で説明されるテストになじみ深くなるのに使用できる1つの方法はすべての内部の詳細が利用可能であるOSPF実現のテストを実行することです。 どんな2つの実現も同様になるという保証が全くありませんが、これはテスト自体の、より良い理解を提供するでしょう。

5.  LSA and Destination Mix

5. LSAと目的地ミックス

   In many OSPF benchmark tests, a generator injecting a number of LSAs
   is called for.  There are several areas in which injected LSAs can be
   varied in testing:

多くのOSPFベンチマークテストでは、多くのLSAsを注入するジェネレータは求められます。 テストで注入されたLSAsを変えることができるいくつかの領域があります:

   o    The number of destinations represented by the injected LSAs

o 注入されたLSAsによって表された目的地の数

        Each destination represents a single reachable IP network; these
        will be leaf nodes on the shortest path tree.  The primary
        impact to performance should be the time required to insert
        destinations in the local routing table and handling the memory
        required to store the data.

各目的地はただ一つの届いているIPネットワークを代表します。 これらは最短パス木の上で葉のノードになるでしょう。 性能への第一の影響は、地方の経路指定テーブルに目的地を挿入するのに必要である時間とメモリがデータを格納するのを必要とした取り扱いであるべきです。

   o    The types of LSAs injected

o LSAsのタイプは注入しました。

        There are several types of LSAs that would be acceptable under
        different situations; within an area, for instance, types 1, 2,
        3, 4, and 5 are likely to be received by a router.  Within a
        not-so-stubby area, however, type-7 LSAs would replace the
        type-5 LSAs received.  These sorts of characterizations are
        important to note in any test results.

異なった状況の下で許容できるLSAsのいくつかのタイプがあります。 領域の中では、1、2は、例えば、3、4、および5がルータによって受け取られそうであるのをタイプします。 しかしながら、したがって、短く太くない領域の中では、タイプ-7LSAsが受け取られたタイプ-5LSAsを取り替えるでしょう。 これらの種類の特殊化は、どんな試験の成績でも注意するために重要です。

Manral, et al.               Informational                      [Page 5]

RFC 4063          Considerations in OSPF Benchmarking         April 2005

Manral、他 OSPFベンチマーキング2005年4月の情報[5ページ]のRFC4063問題

   o    The number of LSAs injected

o 注入されたLSAsの数

        Within any injected set of information, the number of each type
        of LSA injected is also important.  This will impact the
        shortest path algorithm's ability to handle large numbers of
        nodes, large shortest path first trees, etc.

また、どんな注入されたセットの情報の中ではも、注入されたLSAのそれぞれのタイプの数も重要です。 これは多くのノード、最短パスの大きい第1木などを扱う最短パスアルゴリズムの能力に影響を与えるでしょう。

   o    The order of LSA injection

o LSA注射の注文

        The order in which LSAs are injected should not favor any given
        data structure used for storing the LSA database on the device
        being tested.  For instance, AS-External LSAs have AS wide
        flooding scope; any type-5 LSA originated is immediately flooded
        to all neighbors.  However, the type-4 LSA, which announces the
        ASBR as a border router, is originated in an area at SPF time
        (by ABRs on the edge of the area in which the ASBR is).  If SPF
        isn't scheduled immediately on the ABRs originating the type-4
        LSA, the type-4 LSA is sent after the type-5 LSA's reach a
        router in the adjacent area.  Therefore, routes to the external
        destinations aren't immediately added to the routers in the
        other areas.  When the routers that already have the type 5s
        receive the type-4 LSA, all the external routes are added to the
        tree at the same time.  This timing could produce different
        results than a router receiving a type 4 indicating the presence
        of a border router, followed by the type 5s originated by that
        border router.

LSAsが注入されるオーダーは、LSAデータベースを装置に格納するのに使用されるどんな与えられたデータ構造もテストされるのを支持するべきではありません。 例えば、AS外部のLSAsには、ASの広い氾濫範囲があります。 LSAが溯源したどんなタイプ-5もすぐに、すべての隣人へあふれます。 しかしながら、タイプ-4LSA(境界ルータとしてASBRを発表する)はSPF時に領域で溯源されます(領域の縁のASBRがそうであるABRs)。 すぐタイプ-4LSAを溯源するABRsでSPFを予定していないなら、タイプ-5LSAのものが隣接している領域でルータに達した後にタイプ-4LSAを送ります。 したがって、外部の目的地へのルートはすぐに、他の領域のルータに加えられません。 タイプ5sが既にあるルータが同時にタイプ-4LSAを受けるとき、すべての外部経路が木に加えられます。 このタイミングはその境界ルータによって溯源されたタイプ5sによって後をつけられた境界ルータの存在を示すタイプ4を受けるルータと異なった結果を生むかもしれません。

        The ordering can be changed in various tests to provide insight
        into the efficiency of storage within the DUT.  Any such changes
        in ordering should be noted in test results.

DUTの中で格納の効率に関する洞察を提供するために様々なテストで注文を変えることができます。 試験の成績で注文におけるどんなそのような変化にも注意するべきです。

6.  Tree Shape and the SPF Algorithm

6. 木の形とSPFアルゴリズム

   The complexity of Dijkstra's algorithm depends on the data structure
   used for storing vertices with their current minimum distances from
   the source; the simplest structure is a list of vertices currently
   reachable from the source.  In a simple list of vertices, finding the
   minimum cost vertex would then take O(size of the list).  There will
   be O(n) such operations if we assume that all the vertices are
   ultimately reachable from the source.  Moreover, after the vertex
   with minimum cost is found, the algorithm iterates through all the
   edges of the vertex and updates the cost of other vertices.  With an
   adjacency list representation, this step, when iterated over all the
   vertices, would take O(E) time, with E being the number of edges in
   the graph.  Thus, the overall running time is:

ダイクストラのアルゴリズムの複雑さをソースからそれらの現在の最小の距離で頭頂を格納するのに使用されるデータ構造に依存します。 最も簡単な構造は現在ソースから届いている頭頂のリストです。 そして、頭頂に関する単純並びでは、最低費用頂点を見つけると、O(リストのサイズ)は取るでしょう。 私たちが、すべての頭頂が結局ソースから届いていると思うと、O(n)のそのような操作があるでしょう。 そのうえ、最低費用がある頂点が見つけられた後にアルゴリズムは頂点とアップデートのすべての縁を通って他の頭頂の費用を繰り返します。 隣接番組リスト表現で、すべての頭頂の上で繰り返されると、このステップはO(E)時間がかかるでしょう、グラフで縁の数であるEで。 したがって、総合的な実行時間は以下の通りです。

   O(sum(i:1, n)(size(list at level i) + E).

O、((i: 1、n)(サイズ(レベルiでは、記載する)+E)をまとめてください。

Manral, et al.               Informational                      [Page 6]

RFC 4063          Considerations in OSPF Benchmarking         April 2005

Manral、他 OSPFベンチマーキング2005年4月の情報[6ページ]のRFC4063問題

   So everything boils down to the size(list at level i).

それで、詰まるところ、すべてがサイズになります(レベルiでは、記載してください)。

   If the graph is linear,

グラフが直線的であるなら

      root
       |
       1
       |
       2
       |
       3
       |
       4
       |
       5
       |
       6

根| 1 | 2 | 3 | 4 | 5 | 6

   and source is a vertex on the end, then size(list at level i) = 1 for
   all i.  Moreover, E = n - 1.  Therefore, running time is O(n).

そして、ソースはすべてのiのための1終わりの頂点、当時のサイズ(レベルiでは、記載する)=歳です。 そのうえ、Eはnと等しいです--1。 したがって、実行時間はO(n)です。

   If the graph is a balanced binary tree,

グラフがバランスのとれている2進の木であるなら

       root
      /    \
     1      2
    / \    / \
   3   4  5   6

根/\1 2/\/\3 4 5 6

   size(list at level i) is a little complicated.  First, it increases
   by 1 at each level up to a certain number, and then it goes down by
   1.  If we assume that the tree is a complete tree (as shown above)
   with k levels (1 to k), then size(list) goes on like this: 1, 2, 3,

サイズ(レベルiでは、記載する)は少し複雑です。 まず最初に、各レベルで、ある数まで1つ増加します、そして、次に、1時までには、落ちます。 私たちが、kレベル(kへの1)で木が完全な木であると思うなら(上に示されるように)、サイズ(リスト)はこのように先へ進みます: 1, 2, 3,

   Then the number of edges E is still n - 1.  It then turns out that
   the run-time is O(n^2) for such a tree.

そして、それでも、縁Eの数はn--1です。 そして、ランタイムがそのような木のためのO(n^2)であると判明します。

   If the graph is a complete graph (fully-connected mesh), then
   size(list at level i) = n - i.  Number of edges E = O(n^2).
   Therefore, run-time is O(n^2).

グラフが完全なグラフ(メッシュを完全に接続する)であるなら、サイズ(レベルiでは、記載する)はnと等しいです--i。 縁Eの数はO(n^2)と等しいです。 したがって、ランタイムはO(n^2)です。

   Therefore, the performance of the shortest path first algorithm used
   to compute the best paths through the network is dependent on the
   construction of the tree.  The best practice would be to try to make
   any emulated network look as much like a real network as possible,
   especially in the area of the tree depth, the meshiness of the

したがって、最初のアルゴリズムがネットワークを通して最も良い経路を計算するのに使用した最短パスの性能は木の工事に依存しています。 どんな見習われたネットワークも可能であるとしての本当のネットワークのように特に木の深さ、meshinessの領域で見えさせるトライには最も良い習慣があるでしょう。

Manral, et al.               Informational                      [Page 7]

RFC 4063          Considerations in OSPF Benchmarking         April 2005

Manral、他 OSPFベンチマーキング2005年4月の情報[7ページ]のRFC4063問題

   network, the number of stub links versus transit links, and the
   number of connections and nodes to process at each level within the
   original tree.

ネットワーク、スタッブの数はトランジットリンク、ポートの数、およびオリジナルの木の中で各レベルで処理するノードに対してリンクされます。

7.  Topology Generation

7. トポロジー世代

   As the size of networks grows, it becomes more and more difficult to
   actually create a large-scale network on which to test the properties
   of routing protocols and their implementations.  In general, network
   emulators are used to provide emulated topologies that can be
   advertised to a device with varying conditions.  Route generators
   tend to be either a specialized device, a piece of software which
   runs on a router, or a process that runs on another operating system,
   such as Linux or another variant of Unix.

ネットワークのサイズが成長するのに従って、実際に、ルーティング・プロトコルと彼らの実現の特性をテストする大規模なネットワークを創設するのはますます難しくなります。 一般に、ネットワークエミュレータは、装置に広告に掲載できる見習われたtopologiesを異なった状態に提供するのに使用されます。 ルートジェネレータは、専門化している装置である傾向があります、ルータで動くソフトウェア、または別のオペレーティングシステムで動く過程の1つの断片、Unixのリナックスや別の異形のように。

   Some of the characteristics of this device should be as follows:

この装置の特性のいくつかは以下の通りであるべきです:

   o    The ability to connect to several devices using both point-to-
        point and broadcast high-speed media.  Point-to-point links can
        be emulated with high-speed Ethernet as long as there is no hub
        or other device between the DUT and the route generator, and the
        link is configured as a point-to-point link within OSPF
        [BROADCAST-P2P].

o ポイントとポイントから放送への両方の高速メディアを使用することで数台の装置に接続する能力。 DUTとルートジェネレータの間には、どんなハブも対向機器もない限り、高速イーサネットでポイントツーポイント接続を見習うことができます、そして、リンクはポイントツーポイント接続としてOSPF[BROADCAST-P2P]の中で構成されます。

   o    The ability to create a set of LSAs that appear to be a logical,
        realistic topology.  For instance, the generator should be able
        to mix the number of point-to-point and broadcast links within
        the emulated topology and to inject varying numbers of
        externally reachable destinations.

o 論理的で、現実的なトポロジーであるように見えるLSAsの1セットを創設する能力。 例えば、ジェネレータは、見習われたトポロジーの中でポイントツーポイントと放送リンクの数を混ぜて、異なった数の外部的に届いている目的地を注入できるはずです。

   o    The ability to withdraw and add routing information into and
        from the emulated topology to emulate flapping links.

o 引き下がって、ばたつくことを見習うためにトポロジーの中と、そして、見習われたトポロジーからルーティング情報を加える能力はリンクされます。

   o    The ability to randomly order the LSAs representing the emulated
        topology as they are advertised.

o 手当たりしだいに彼らが広告に掲載されているので見習われたトポロジーを表すLSAsを注文する能力。

   o    The ability to log or otherwise measure the time between packets
        transmitted and received.

o 送信されて、受け取られたパケットの間で時間を登録するか、またはそうでなければ測定する能力。

   o    The ability to change the rate at which OSPF LSAs are
        transmitted.

o OSPF LSAsが伝えられるレートを変える能力。

   o    The generator and the collector should be fast enough that they
        are not bottlenecks.  The devices should also have a degree of
        granularity of measurement at least as small as is desired from
        the test results.

o ジェネレータとコレクタはそれらがボトルネックでない速いはずです。 また、装置で、測定の1段階の粒状はそのままで少なくとも同じくらい小さく試験の成績から必要な状態でなるはずです。

Manral, et al.               Informational                      [Page 8]

RFC 4063          Considerations in OSPF Benchmarking         April 2005

Manral、他 OSPFベンチマーキング2005年4月の情報[8ページ]のRFC4063問題

8.  Security Considerations

8. セキュリティ問題

   This document does not modify the underlying security considerations
   in [OSPF].

このドキュメントは[OSPF]の基本的なセキュリティ問題を変更しません。

9.  Acknowledgements

9. 承認

   Thanks to Howard Berkowitz (hcb@clark.net) and the rest of the BGP
   benchmarking team for their support and to Kevin Dubray
   (kdubray@juniper.net), who realized the need for this document.

おかげに、ハワード・バーコウィッツ( hcb@clark.net )とBGPベンチマーキングの残りは彼らのサポートと、そして、ケビンDubray( kdubray@juniper.net )と組になります。Dubrayはこのドキュメントの必要性がわかりました。

10.  Normative References

10. 引用規格

   [BENCHMARK]     Manral, V., White, R., and A. Shaikh, "Benchmarking
                   Basic OSPF Single Router Control Plane Convergence",
                   RFC 4061, April 2005.

[ベンチマーク]Manral、V.、ホワイト、R.、およびA.Shaikh、「基本的なベンチマーキングのOSPFただ一つのルータコントロール飛行機集合」、RFC4061、2005年4月。

   [TERM]          Manral, V., White, R., and A. Shaikh, "OSPF
                   Benchmarking Terminology and Concepts", RFC 4062,
                   April 2005.

[用語]Manral、V.、ホワイト、R.、A.Shaikh、および「OSPFベンチマーキング用語と概念」、RFC4062、4月2005日

   [OSPF]          Moy, J., "OSPF Version 2", STD 54, RFC 2328, April
                   1998.

[OSPF]Moy、J.、「OSPF、バージョン2インチ、STD54、RFC2328、1998インチ年4月。

11.  Informative References

11. 有益な参照

   [INTERCONNECT]  Bradner, S. and J. McQuaid, "Benchmarking Methodology
                   for Network Interconnect Devices", RFC 2544, March
                   1999.

[内部連絡します] ブラドナーとS.とJ.McQuaid、「ネットワーク内部連絡装置のためのベンチマーキング方法論」、RFC2544、1999年3月。

   [FIB-TERM]      Trotter, G., "Terminology for Forwarding Information
                   Base (FIB) based Router Performance", RFC 3222,
                   December 2001.

[FIB-TERM]速足の馬、G.、「Forwarding Information基地(FIB)への用語はRouterパフォーマンスを基礎づけた」RFC3222、2001年12月。

   [BROADCAST-P2P] Shen, Naiming, et al., "Point-to-point operation over
                   LAN in link-state routing protocols", Work in
                   Progress, August, 2003.

[BROADCAST-P2P] シン、Naiming、他、「LinkState方式プロトコルのLANの上の二地点間操作」、Progress、2003年8月のWork。

Manral, et al.               Informational                      [Page 9]

RFC 4063          Considerations in OSPF Benchmarking         April 2005

Manral、他 OSPFベンチマーキング2005年4月の情報[9ページ]のRFC4063問題

Authors' Addresses

作者のアドレス

   Vishwas Manral
   SiNett Corp,
   Ground Floor,
   Embassy Icon Annexe,
   2/1, Infantry Road,
   Bangalore, India

Vishwas Manral SiNett Corp、1階、大使館アイコン別館、2/1、歩兵道路、バンガロール、インド

   EMail: vishwas@sinett.com

メール: vishwas@sinett.com

   Russ White
   Cisco Systems, Inc.
   7025 Kit Creek Rd.
   Research Triangle Park, NC 27709

ラス白いシスコシステムズInc.7025キットCreek通り NC リサーチトライアングル公園、27709

   EMail: riw@cisco.com

メール: riw@cisco.com

   Aman Shaikh
   AT&T Labs (Research)
   180 Park Av, PO Box 971
   Florham Park, NJ 07932

ニュージャージー Aman Shaikh AT&T研究室(研究)180公園Av、私書箱971Florham公園、07932

   EMail: ashaikh@research.att.com

メール: ashaikh@research.att.com

Manral, et al.               Informational                     [Page 10]

RFC 4063          Considerations in OSPF Benchmarking         April 2005

Manral、他 OSPFベンチマーキング2005年4月の情報[10ページ]のRFC4063問題

Full Copyright Statement

完全な著作権宣言文

   Copyright (C) The Internet Society (2005).

Copyright(C)インターネット協会(2005)。

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

このドキュメントはBCP78に含まれた権利、ライセンス、および制限を受けることがあります、そして、そこに詳しく説明されるのを除いて、作者は彼らのすべての権利を保有します。

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
   ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
   INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
   INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

このドキュメントと「そのままで」という基礎と貢献者、その人が代表する組織で提供するか、または後援されて、インターネット協会とインターネット・エンジニアリング・タスク・フォースはすべての保証を放棄します、と急行ORが含意したということであり、他を含んでいて、ここに含まれて、情報の使用がここに侵害しないどんな保証も少しもまっすぐになるという情報か市場性か特定目的への適合性のどんな黙示的な保証。

Intellectual Property

知的所有権

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

IETFはどんなIntellectual Property Rightsの正当性か範囲、実現に関係すると主張されるかもしれない他の権利、本書では説明された技術の使用またはそのような権利の下におけるどんなライセンスも利用可能であるかもしれない、または利用可能でないかもしれない範囲に関しても立場を全く取りません。 または、それはそれを表しません。どんなそのような権利も特定するためのどんな独立している努力もしました。 BCP78とBCP79でRFCドキュメントの権利に関する手順に関する情報を見つけることができます。

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

IPR公開のコピーが利用可能に作られるべきライセンスの保証、または一般的な免許を取得するのが作られた試みの結果をIETF事務局といずれにもしたか、または http://www.ietf.org/ipr のIETFのオンラインIPR倉庫からこの仕様のimplementersかユーザによるそのような所有権の使用のために許可を得ることができます。

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at ietf-
   ipr@ietf.org.

IETFはこの規格を実行するのに必要であるかもしれない技術をカバーするかもしれないどんな著作権もその注目していただくどんな利害関係者、特許、特許出願、または他の所有権も招待します。 ietf ipr@ietf.org のIETFに情報を記述してください。

Acknowledgement

承認

   Funding for the RFC Editor function is currently provided by the
   Internet Society.

RFC Editor機能のための基金は現在、インターネット協会によって提供されます。

Manral, et al.               Informational                     [Page 11]

Manral、他 情報[11ページ]