JP5201731B2

JP5201731B2 - Packet path control device, packet path control method, packet path control program, and recording medium recording the program

Info

Publication number: JP5201731B2
Application number: JP2009018399A
Authority: JP
Inventors: 賢一新井; 伸水谷; 伸一荒川; 村田　　正幸
Original assignee: Nippon Telegraph and Telephone Corp; Osaka University NUC; NTT Inc USA
Current assignee: University of Osaka NUC; NTT Inc; NTT Inc USA
Priority date: 2009-01-29
Filing date: 2009-01-29
Publication date: 2013-06-05
Anticipated expiration: 2029-01-29
Also published as: JP2010178062A

Description

本発明は、ネットワークにおける経路制御技術に関する。 The present invention relates to a route control technique in a network.

従来から、通信ネットワーク上を配送されるパケットは、そのパケットが生成された時点で、宛先ノードが決まっている。このパケットを生成したノードがネットワークトポロジの情報を持っていれば、このパケットを生成した時点で、目的とするノードまでの経路を計画することができる。しかし、インターネットでは多くの場合、途中のノードが次のノードまでの経路を決定するホップバイホップルーティングにより経路制御が行われる。各ノードでは、宛先ノードとそれに対応する経路が書き込まれた経路表を備え、受信したパケットの宛先ノードに基づき、次にパケットを配送（転送）すべき隣接ノードを決定する。各ノードはネットワーク状況に関する情報を交換しあって、必要に応じて経路表を更新する。この経路表を作成する方法としては、ＯＳＰＦ（Open Shortest Path First）が一般的である。このＯＳＰＦにおいて、各ノードは、ネットワークトポロジや、各ノード間を接続するリンクのリンクコスト（リンクでの遅延時間等）等の情報を交換する。そして、受信した情報からリンクコストを最小にする経路（最小コスト経路）を計算する。このような最小コスト経路の計算方法としてダイクストラ法が知られている（非特許文献１参照）。 Conventionally, a destination node of a packet delivered on a communication network is determined when the packet is generated. If the node that generated this packet has network topology information, the route to the target node can be planned at the time when this packet is generated. However, in the Internet, in many cases, route control is performed by hop-by-hop routing in which a halfway node determines a route to the next node. Each node has a route table in which a destination node and a corresponding route are written. Based on the destination node of the received packet, an adjacent node to which a packet is to be delivered (transferred) next is determined. Each node exchanges information regarding the network status, and updates the routing table as necessary. As a method for creating this path table, OSPF (Open Shortest Path First) is generally used. In this OSPF, each node exchanges information such as the network topology and the link cost (link delay time, etc.) of the links connecting the nodes. Then, a route that minimizes the link cost (minimum cost route) is calculated from the received information. The Dijkstra method is known as a method for calculating such a minimum cost route (see Non-Patent Document 1).

D. Bertsekas 、R.Gallager、「Data Networks(2nd Edition)」、Prentice Hall、1992D. Bertsekas, R. Gallager, "Data Networks (2nd Edition)", Prentice Hall, 1992

このダイクストラ法では、最小コスト経路を計算し、その最小コスト経路によりパケットを配送するようにする。しかし、その最小コスト経路上のノードに輻輳が発生した場合、その輻輳が発生したノードを避けた経路を再計算し、その再計算した経路によりパケットを配送するようにしなければならない。よって、輻輳に対してリアルタイムに対応することが困難であった。 In this Dijkstra method, a minimum cost route is calculated, and packets are delivered via the minimum cost route. However, when congestion occurs in a node on the minimum cost route, it is necessary to recalculate a route that avoids the node in which the congestion has occurred, and deliver a packet through the recalculated route. Therefore, it is difficult to deal with congestion in real time.

本発明は、前記した問題を解決し、ネットワーク内の輻輳に対してリアルタイムに対応し、輻輳発生に対する耐性を向上させることを目的とする。 An object of the present invention is to solve the above-described problems, to deal with congestion in a network in real time, and to improve tolerance to congestion occurrence.

前記した課題を解決するため、請求項１に記載の発明は、ネットワーク内のパケットの経路制御を行うノードにおいて、このノードｉの隣接ノードの中から、パケットの次の配送先となる隣接ノードｊを決定するパケット経路制御装置であって、記憶部に記憶されたネットワークのネットワークトポロジおよびネットワークの各ノード間を接続するリンクのリンクコストを参照して、パケットの宛先ノードｋへの最小コスト経路を計算し、最小コスト経路へ接続する隣接ノードｊを、パケットの次の配送先として選択することにより、最小コスト経路制御を行う最小コスト経路制御部と、パケットの次の配送先として、自身のノードｉに隣接する隣接ノードｊそれぞれを同じ確率で選択することにより、ランダム経路制御を行うランダムウォーク経路制御部とを備え、記憶部に記憶された隣接ノードｊそれぞれのバッファにおけるキュー長を参照して、自身のノードｉのバッファから取り出した宛先ノードｋへのパケットの次の配送先として、自身のノードｉの隣接ノードｊを選択する確率ｐ＾^ｋ _ｉｊを、以下の式（１）および式（２）により計算し、擬似乱数を発生させて、計算した確率ｐ＾ ^ｋ _ｉｊに基づいて宛先ノードｋへのパケットの次の配送先となる隣接ノードｊを決定するパケット経路制御部とを備えることを特徴とする。

δ：ｐ^ｋ _ｉｊにおけるｐ^（Ｓ）ｋ _ｉｊの混合比率
ｑ_ｊ：隣接ノードｊにおけるキュー長
ｆ（ｑ）：キュー長ｑに関する減少関数
ｐ^（Ｓ）ｋ _ｉｊ：最小コスト経路制御部による最小コスト経路制御により、宛先ノードｋへのパケットの次の配送先として、自身のノードｉの隣接ノードのうち、隣接ノードｊを選択する確率
ｐ^（Ｒ）ｋ _ｉｊ：ランダムウォーク経路制御部によるランダムウォーク経路制御により、宛先ノードｋへのパケットの次の配送先として、自身のノードｉの隣接ノードのうち、隣接ノードｊを選択する確率 In order to solve the above-described problem, the invention according to claim 1 is a node that performs routing control of a packet in a network. Among adjacent nodes of this node i , an adjacent node j that is a next delivery destination of the packet. A packet path control apparatus for determining a minimum cost path to a destination node k of a packet by referring to a network topology stored in a storage unit and a link cost of a link connecting each node of the network. the neighboring node j that computes, and connect to the minimum cost path, by selecting as the next destination of the packet, and the minimum cost path control section for minimum cost routing, as the next destination of the packet, the themselves by selecting each neighboring node j adjacent to node i with the same probability, random Wo performing random routing And a click path control unit, by referring to the queue length in the adjacent node j each buffer stored in the storage unit, as the next destination of the packet to the destination node k taken out from the buffer of its node i, the probability ^p _{^ k ij} for selecting the neighbor node j of its own node i, the following equation (1) and was calculated by the equation (2), by generating a pseudo random number, based on the calculated probability ^p _{^ k ij} And a packet path control unit that determines an adjacent node j to be a next delivery destination of the packet to the destination node k.

^[delta]: _p ^p in _{k ij} ^_(S) mixture of _{k ij} ratio q _j: queue length f in the adjacent node j (q): a decrease of the queue length q function p _{^(S) k ij:} minimum cost by minimum cost path controller Probability of selecting an adjacent node j among adjacent nodes of its own node i as a next delivery destination of a packet to the destination node k by route control p ^{(R) k} _ij : Random walk route by a random walk route control unit Probability of selecting adjacent node j among adjacent nodes of its own node i as the next delivery destination of the packet to destination node k by control

請求項７に記載の発明は、ネットワーク内のパケットの経路制御を行うノードにおいて、このノードｉの隣接ノードの中から、パケットの次の配送先となる隣接ノードｊを決定するパケット経路制御装置のパケット経路制御方法であって、パケット経路制御装置が、記憶部に記憶されたネットワークのネットワークトポロジおよびネットワークの各ノード間を接続するリンクのリンクコストを参照して、パケットの宛先ノードｋへの最小コスト経路を計算し、最小コスト経路へ接続する隣接ノードｊを、パケットの次の配送先として選択することにより、最小コスト経路制御を行う最小コスト経路制御部と、パケットの次の配送先として、自身のノードｉに隣接する隣接ノードｊそれぞれを同じ確率で選択することにより、ランダム経路制御を行うランダムウォーク経路制御部とを備え、記憶部に記憶された隣接ノードｊそれぞれのバッファにおけるキュー長を参照して、自身のノードｉのバッファから取り出した宛先ノードｋへのパケットの次の配送先として、自身のノードｉの隣接ノードｊを選択する確率ｐ＾^ｋ _ｉｊを、以下の式（１）および式（２）により計算し、擬似乱数を発生させて、計算した確率ｐ＾ ^ｋ _ｉｊに基づいて宛先ノードｋへのパケットの次の配送先となる隣接ノードｊを決定することを特徴とする。

δ：ｐ^ｋ _ｉｊにおけるｐ^（Ｓ）ｋ _ｉｊの混合比率
ｑ_ｊ：隣接ノードｊにおけるキュー長
ｆ（ｑ）：キュー長ｑに関する減少関数
ｐ^（Ｓ）ｋ _ｉｊ：最小コスト経路制御部による最小コスト経路制御により、宛先ノードｋへのパケットの次の配送先として、自身のノードｉの隣接ノードのうち、隣接ノードｊを選択する確率
ｐ^（Ｒ）ｋ _ｉｊ：ランダムウォーク経路制御部によるランダムウォーク経路制御により、宛先ノードｋへの次のパケットの配送先として、自身のノードｉの隣接ノードのうち、隣接ノードｊを選択する確率 According to a seventh aspect of the present invention, there is provided a packet path control device for determining a next node j that is a next delivery destination of a packet from among adjacent nodes of the node i in a node that performs path control of the packet in the network. A packet path control method, wherein a packet path control device refers to a network topology stored in a storage unit and a link cost of a link connecting each node of the network, and minimizes a packet to a destination node k By calculating the cost path and selecting the adjacent node j connected to the minimum cost path as the next delivery destination of the packet, the minimum cost path control unit that performs the minimum cost path control, and the next delivery destination of the packet , by selecting each neighboring node j adjacent to node i of themselves with the same probability, random routing Random walk and a path control unit, by referring to the queue length in the adjacent node j each buffer stored in the storage unit, the next destination of the packet to the destination node k taken out from the buffer of its node i to perform as the probability ^p _{^ k ij} for selecting the neighbor node j of its own node i, was calculated by the following equation (1) and (2), by generating a pseudo-random number, the calculated probability ^p _{^ k ij} and determining the neighboring node j as the next destination of the packet to the destination node k on the basis of.

^[delta]: _p ^p in _{k ij} ^_(S) mixture of _{k ij} ratio q _j: queue length f in the adjacent node j (q): a decrease of the queue length q function p _{^(S) k ij:} minimum cost by minimum cost path controller Probability of selecting an adjacent node j among adjacent nodes of its own node i as a next delivery destination of a packet to the destination node k by route control p ^{(R) k} _ij : Random walk route by a random walk route control unit Probability of selecting adjacent node j from among adjacent nodes of its own node i as a delivery destination of the next packet to destination node k by control

このようなパケット経路制御装置は、宛先ノードｋへのパケットの次の配送先として隣接ノードｊを選択する確率ｐ＾^ｋ _ｉｊを、最小コスト経路制御よる確率ｐ^（ｓ）ｋ _ｉｊと、ランダムウォーク経路制御による確率ｐ^（Ｒ）ｋ _ｉｊとを混合した確率として計算する。つまり、パケット経路制御装置は、パケットの次の配送先となる隣接ノードを決定するとき、最小コスト経路の隣接ノードのみならず、ランダムに選択した隣接ノードも選択範囲に含めて決定することになる。また、パケット経路制御装置は、隣接ノードのうち、キュー長の長い隣接ノードを次の配送先として選択する配送確率を低くする。よって、このようなパケット経路制御装置を備えるノードにより構成されるネットワークは、混雑している可能性の高い隣接ノードへのパケットの配送を軽減し、輻輳に対する耐性を向上させることができる。なお、各請求項における隣接ノードｊとは、自身のノードの隣接ノード群におけるｊという隣接ノードという意味であり、宛先ノードｋとは、パケットの宛先ノード群のうち、ｋというノードという意味である。 Such a packet route control apparatus uses a random walk with a probability p ^{(s) k} _ij according to the minimum cost route control and a probability p ^ ^k _ij for selecting the adjacent node j as the next delivery destination of the packet to the destination node k. The probability p ^{(R) k} _ij by the route control is calculated as a mixed probability. In other words, when the packet path control apparatus determines an adjacent node that is the next delivery destination of a packet, it determines not only the adjacent node of the minimum cost path but also the randomly selected adjacent node in the selection range. . Further, the packet path control device lowers the delivery probability of selecting an adjacent node having a long queue length as the next delivery destination among the adjacent nodes. Therefore, a network composed of nodes equipped with such a packet path control device can reduce the delivery of packets to adjacent nodes that are likely to be congested, and can improve the tolerance to congestion. The adjacent node j in each claim means an adjacent node j in the adjacent node group of its own node, and the destination node k means a node k in the destination node group of the packet. .

請求項２に記載の発明は、請求項１のパケット経路制御装置が、隣接ノードそれぞれのバッファにおけるキュー長の問い合わせを行い、記憶部に記憶された隣接ノードそれぞれのバッファにおけるキュー長を最新の情報に書き換えるキュー長取得部を備えることを特徴とする。 According to the second aspect of the present invention, the packet path control device according to the first aspect inquires about the queue length in the buffer of each adjacent node, and the queue length in the buffer of each adjacent node stored in the storage unit is the latest information. And a queue length acquisition unit for rewriting to the above.

このようにすることで、このパケット経路制御装置は、隣接ノードそれぞれのバッファにおける最新のキュー長を考慮して確率ｐ＾^ｋ _ｉｊを計算できる。よって、このようなパケット経路制御装置を備えるノードにより構成されるネットワークは、混雑している可能性の高い隣接ノードへのパケットの配送を軽減し、輻輳に対する耐性を向上させることができる。 In this way, the packet path control apparatus can calculate the probability p ^ ^k _ij in consideration of the latest queue length in the buffer of each adjacent node. Therefore, a network composed of nodes equipped with such a packet path control device can reduce the delivery of packets to adjacent nodes that are likely to be congested, and can improve the tolerance to congestion.

請求項３に記載の発明は、請求項１または請求項２に記載のパケット経路制御装置のパケット経路制御部が、確率ｐ＾^ｋ _ｉｊを、自身のノードｉの隣接ノードｊごと、宛先ノードｋごとに計算しておき、計算した確率ｐ＾^ｋ _ｉｊの計算結果を配送確率情報として、記憶部に記憶し、擬似乱数を発生させ、記憶部に記憶された配送確率情報を参照して、計算した確率ｐ＾ ^ｋ _ｉｊに基づき、宛先ノードｋへのパケットの次の配送先となる隣接ノードｊを決定することを特徴とする。 In the invention according to claim 3, the packet route control unit of the packet route control device according to claim 1 or 2 determines the probability p ^ ^k _ij for each adjacent node j of its own node i and destination node k. The calculation result of the calculated probability p ^ ^k _ij is stored in the storage unit as the delivery probability information, a pseudo random number is generated , and the calculation is performed by referring to the delivery probability information stored in the storage unit. based on the probability p ^ ^k _ij, and determining the neighboring node j as the next destination of the packet to the destination node k.

このようにすることで、パケット経路制御装置は、予め作成しておいた配送確率情報を参照して、宛先ノードへのパケットの次の配送先である隣接ノードを決定するので、パケットを受信するたびに配送確率を計算する必要がなくなる。 By doing so, the packet path control apparatus refers to the delivery probability information created in advance, and determines the adjacent node that is the next delivery destination of the packet to the destination node, and therefore receives the packet. There is no need to calculate the delivery probability each time.

請求項４に記載の発明は、請求項１から請求項３のいずれか１項に記載のパケット経路制御装置が、式（２）における、減少関数ｆ（ｑ）として、ｆ（ｑ）＝（ｑ＋１）^−２を用いたとき、式（１）における、δ＝０．９２〜０．９９とすることを特徴とする。 According to a fourth aspect of the present invention, there is provided a packet path control device according to any one of the first to third aspects, wherein f (q) = ( When q + 1) ^-2 is used, δ = 0.92 to 0.99 in the equation (1) is characterized.

このようにすることで、このパケット経路制御装置を備えるノードからなるネットワークにおいて、混雑状態（ネットワーク内のパケット総数が時間に比例して増加する状態）になりにくくすることができる。よって、このようなパケット経路制御装置を備えるノードにより構成されるネットワークにおいて、混雑している可能性の高い隣接ノードへのパケットの配送を軽減し、輻輳に対する耐性を向上させることができる。 By doing in this way, it is possible to make it difficult for a network composed of nodes having this packet path control device to become congested (a state in which the total number of packets in the network increases in proportion to time). Therefore, in a network composed of nodes equipped with such a packet path control device, it is possible to reduce the delivery of packets to adjacent nodes that are highly likely to be congested and to improve the tolerance to congestion.

請求項５に記載の発明は、請求項１から請求項４のいずれか１項に記載のパケット経路制御装置を備え、パケット経路制御装置により決定されたパケットの次の配送先となる隣接ノードｊへパケットを配送するノードとした。 The invention according to claim 5 comprises the packet path control device according to any one of claims 1 to 4, and is an adjacent node j that is the next delivery destination of the packet determined by the packet path control device. A node that delivers packets to

このようなノードにより構成されるネットワークにおいて、混雑している可能性の高い隣接ノードへのパケットの配送を軽減し、輻輳に対する耐性を向上させることができる。 In a network composed of such nodes, it is possible to reduce the delivery of packets to adjacent nodes that are likely to be congested, and to improve the tolerance to congestion.

請求項６に記載の発明は、請求項５に記載のノードが、宛先ノードｋとの間にコネクションを確立して通信を行うオーバーレイネットワーク上のノードであり、隣接ノードｊは、前記コネクションを確立して通信を行う前記宛先ノードｋであることを特徴とする。 The invention according to claim 6 is a node on the overlay network in which the node according to claim 5 establishes a connection with the destination node k and performs communication, and the adjacent node j establishes the connection. And the destination node k that performs communication.

このようにすることで、このようなパケット経路制御装置を備えるノードを備えるオーバーレイネットワークの輻輳に対する耐性を向上させることができる。 By doing in this way, the tolerance with respect to the congestion of an overlay network provided with the node provided with such a packet path control apparatus can be improved.

請求項８に記載の発明は、コンピュータを、請求項１から請求項４のいずれか１項に記載のパケット経路制御装置として機能させるためのパケット経路制御プログラムとした。 The invention according to claim 8 is a packet path control program for causing a computer to function as the packet path control apparatus according to any one of claims 1 to 4.

このようなプログラムによれば、請求項１から請求項４のいずれか１項に記載のパケット経路制御装置の機能を一般的なコンピュータにより実現できる。 According to such a program, the function of the packet path control device according to any one of claims 1 to 4 can be realized by a general computer.

請求項９に記載の発明は、請求項８に記載のパケット経路制御プログラムを記録したコンピュータに読み取り可能な記録媒体とした。 The invention described in claim 9 is a computer-readable recording medium on which the packet path control program according to claim 8 is recorded.

このような記録媒体により、請求項８に記載のパケット経路制御プログラムをコンピュータにインストールすることで、このコンピュータに、請求項１から請求項４のいずれか１項に記載のパケット経路制御装置の機能を実現させることができる。 The function of the packet path control device according to any one of claims 1 to 4 is installed in the computer by installing the packet path control program according to claim 8 on the computer using such a recording medium. Can be realized.

本発明によれば、ネットワークにおいて、パケットが集中している隣接ノードへのパケットの配送を軽減し、ネットワーク全体としての輻輳に対する耐性を向上させることができる。このようにネットワーク全体の混雑を緩和することによって、混雑を起こさずに配送できるパケット数（データ量）を増やすことができる。 According to the present invention, it is possible to reduce the delivery of packets to adjacent nodes where packets are concentrated in the network, and to improve the resistance to congestion as a whole network. By reducing the congestion of the entire network in this way, the number of packets (data amount) that can be delivered without causing congestion can be increased.

本実施の形態であるパケット経路制御装置（パケット経路制御部）を備えるノードの動作概要を説明した図である。It is the figure explaining the operation | movement outline | summary of the node provided with the packet route control apparatus (packet route control part) which is this Embodiment. パケット経路制御装置（パケット経路制御部）を備えるノードのブロック図である。It is a block diagram of a node provided with a packet path control device (packet path control unit). 図２のノードの処理手順を示したフローチャートである。It is the flowchart which showed the process procedure of the node of FIG. 本実施の形態における最小コスト経路制御による配送確率の計算手順を示したフローチャートである。It is the flowchart which showed the calculation procedure of the delivery probability by the minimum cost path | route control in this Embodiment. ネットワークの構成を例示した図である。It is the figure which illustrated the structure of the network. 本実施の形態におけるランダムウォーク経路制御による配送確率の計算手順を示したフローチャートである。It is the flowchart which showed the calculation procedure of the delivery probability by the random walk route control in this Embodiment.

＜概要＞
以下、本発明を実施するための形態について説明する。まず、図１を参照して、本実施の形態であるパケット経路制御装置（パケット経路制御部）を備えるノード１０のネットワークにおける動作概要を説明する。 <Overview>
Hereinafter, modes for carrying out the present invention will be described. First, with reference to FIG. 1, the outline | summary of operation | movement in the network of the node 10 provided with the packet route control apparatus (packet route control part) which is this Embodiment is demonstrated.

ここで、ノード１０は、ネットワークにおいてパケットの経路制御を行うルータ等である。ノード２０は、ユーザ端末やＰＲＯＸＹサーバ等である。このネットワークは、ノード１０（１０Ａ，１０Ｂ，１０Ｃ，１０Ｄ，１０Ｅ，１０Ｆ，１０Ｇ，１０Ｈ）を含んで構成され、ノード１０は、例えば、ノード２０Ａから送信されたパケットの経路制御を行い、このパケットを、宛先ノードであるノード２０Ｂへ到達させる。ここで、現在着目しているノード１０をノードｉ（例えば、ノード１０Ｅ）とすると、このノードｉは、バッファから取り出した宛先ノードｋ（例えば、ノード２０Ｂ）へのパケットを次に隣接ノードｊへ配送する配送確率ｐ^ｋ _ｉｊを、隣接ノードｊとなるノード１０（ノード１０Ａ〜１０Ｄ，１０Ｆ，１０Ｇ）ごとに計算する。そして、その計算した配送確率ｐ^ｋ _ｉｊに基づき、パケットの次の配送先ノードを決定する。つまり、ネットワークのノード１０は、パケットの次の配送先ノードを確率論に基づき選択するので、必ずしも最小コスト経路上のノードを次の配送先ノードとして選択するわけではない。 Here, the node 10 is a router or the like that performs packet path control in the network. The node 20 is a user terminal, a PROXY server, or the like. This network is configured to include nodes 10 (10A, 10B, 10C, 10D, 10E, 10F, 10G, and 10H). The node 10 performs path control of packets transmitted from the node 20A, for example. To the node 20B as the destination node. Here, assuming that the node 10 currently focused on is the node i (for example, the node 10E), the node i then transfers the packet to the destination node k (for example, the node 20B) extracted from the buffer to the adjacent node j. The delivery probability p ^k _ij to be delivered is calculated for each node 10 (nodes 10A to 10D, 10F, and 10G) that is the adjacent node j. Then, the next delivery destination node of the packet is determined based on the calculated delivery probability p ^k _ij . That is, since the node 10 of the network selects the next delivery destination node of the packet based on the probability theory, the node on the minimum cost route is not necessarily selected as the next delivery destination node.

ここで、ノード１０は、前記した配送確率ｐ^ｋ _ｉｊを、（１）ＯＳＰＦによる最小コスト経路制御（宛先ノードへの最小コスト経路を選択する経路制御）に基づき、宛先ノードｋのパケットを隣接ノードｊへ配送する配送確率ｐ^（Ｓ）ｋ _ｉｊと、ランダムウォーク経路制御（隣接ノードそれぞれに同じ確率で配送する経路制御）に基づき、宛先ノードｋのパケットを隣接ノードｊへ配送する配送確率ｐ^（Ｒ）ｋ _ｉｊとを所定の割合で混合して計算する。また、ノード１０は、隣接ノードそれぞれから、その隣接ノードにおけるキュー長の情報を取得する。つまり、ノード１０は、隣接ノードそれぞれのパケットの混雑状況を把握する。例えば、ノード１０Ｅは、隣接ノード（ノード１０Ａ〜１０Ｄ，１０Ｆ，１０Ｇ）のキュー長の情報を取得する。 Here, the node 10 uses the delivery probability p ^k _ij as the neighbor node based on (1) minimum cost path control by OSPF (path control for selecting the minimum cost path to the destination node). Based on the delivery probability p ^{(S) k} _ij to be delivered to j and random walk route control (route control to deliver to each adjacent node with the same probability) delivery probability p ⁽ to deliver the packet of the destination node k to the adjacent node j ^{R) k} _ij is mixed at a predetermined ratio and calculated. Further, the node 10 acquires information on the queue length in the adjacent node from each of the adjacent nodes. That is, the node 10 grasps the congestion status of each adjacent node. For example, the node 10E acquires information on queue lengths of adjacent nodes (nodes 10A to 10D, 10F, and 10G).

（２）次に、ノード１０は、取得した隣接ノードそれぞれのキュー長をもとに、混雑しているノード１０を避けるような（つまり、混雑しているノード１０を配送先ノードとして選択する確率を低くした）、新たな配送確率ｐ＾^ｋ _ｉｊを計算する。（３）そして、ノード１０は、擬似乱数を発生させ、この計算した配送確率ｐ＾^ｋ _ｉｊに基づき、次の配送先ノードを決定する。そして、この決定した配送先ノードへパケットを配送する。このようにすることで、例えば、ノード１０Ｅは、最小コスト経路制御によれば、ノード１０Ｄを次の配送先ノードとするところ、配送確率ｐ＾^ｋ _ｉｊに基づきノード１０Ｃを次の配送先ノードとして決定する。 (2) Next, the node 10 avoids the congested node 10 based on the acquired queue length of each adjacent node (that is, the probability of selecting the congested node 10 as the delivery destination node). It was low), to calculate the new distribution probability ^p _{^ k ij.} (3) Then, the node 10 generates a pseudo-random number and determines the next delivery destination node based on the calculated delivery probability p ^ ^k _ij . Then, the packet is delivered to the determined delivery destination node. In this way, for example, according to the minimum cost path control, the node 10E sets the node 10D as the next delivery destination node, and sets the node 10C as the next delivery destination node based on the delivery probability p ^ ^k _ij. decide.

以上のような方法で、ネットワークの各ノード１０がパケットの配送先ノードを確率論に基づきに決定することで、各ノード１０は必ずしも最小コスト経路を選択しないことになる。また、各ノード１０は、隣接ノードの混雑状況を把握し、混雑しているノード１０を次の配送先ノードとして選択する確率を低くする。よって、ネットワーク内においてパケットが集中しているノードへのパケットの配送を軽減し、輻輳に対する耐性を向上させることができる。 With the above method, each node 10 of the network determines a packet delivery destination node based on probability theory, so that each node 10 does not necessarily select a minimum cost route. In addition, each node 10 grasps the congestion status of adjacent nodes, and reduces the probability of selecting the congested node 10 as the next delivery destination node. Therefore, it is possible to reduce the delivery of packets to nodes where packets are concentrated in the network and to improve the tolerance to congestion.

＜構成＞
次に、このようなノード１０の構成を説明する。図２に示すように、ノード１０の機能は、大きく、入出力部１１、処理部１２および記憶部１３に分けられる。このうち入出力部１１は、隣接ノードからパケットの入力を受け付けたり、隣接ノードへパケットを出力（配送）したりする。処理部１２は、パケットの経路制御を司り、ここでは主に、パケットの次の配送先として隣接ノードｊを選択する確率を計算し、この計算した確率に基づきパケットの次の配送先の隣接ノードを決定する。そして、この決定した隣接ノードへパケットを配送する。記憶部１３は、処理部１２が経路制御のために用いる各種情報を記憶する。 <Configuration>
Next, the configuration of such a node 10 will be described. As shown in FIG. 2, the function of the node 10 is roughly divided into an input / output unit 11, a processing unit 12, and a storage unit 13. Among these, the input / output unit 11 receives an input of a packet from an adjacent node or outputs (distributes) a packet to the adjacent node. The processing unit 12 is responsible for packet path control, and here mainly calculates the probability of selecting an adjacent node j as the next delivery destination of the packet, and based on the calculated probability, the adjacent node of the next delivery destination of the packet To decide. Then, the packet is delivered to the determined adjacent node. The storage unit 13 stores various information used by the processing unit 12 for path control.

入出力部１１は、入出力インタフェースや通信インタフェースから構成される。また、処理部１２は、このノード１０が備えるＣＰＵ（Central Processing Unit）によるプログラム実行処理や、専用回路等により実現される。さらに、記憶部１３は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ等の記憶媒体から構成される。なお、ノード１０の処理部１２の機能をプログラム実行処理により実現する場合、記憶部１３には、このノード１０の処理部１２の機能を実現するためのプログラムが格納される。なお、そのプログラムをコンピュータによる読み取り可能な記録媒体（ＣＤ−ＲＯＭ等）に記憶して提供することも可能である。 The input / output unit 11 includes an input / output interface and a communication interface. The processing unit 12 is realized by a program execution process by a CPU (Central Processing Unit) included in the node 10 or a dedicated circuit. Further, the storage unit 13 includes a storage medium such as a random access memory (RAM), a read only memory (ROM), a hard disk drive (HDD), and a flash memory. When the function of the processing unit 12 of the node 10 is realized by program execution processing, the storage unit 13 stores a program for realizing the function of the processing unit 12 of the node 10. The program can be provided by being stored in a computer-readable recording medium (CD-ROM or the like).

次に、処理部１２の構成を詳細に説明する。処理部１２は、パケット経路制御部１２１と、パケット配送部１２２と、キュー長取得部１２３とを備える。このうち、パケット経路制御部１２１は、配送確率行列１３５（配送確率情報、詳細は後記）を作成する。そして、その作成した配送確率行列１３５を参照して、宛先ノードｋのパケットの次の配送先となる隣接ノード（以下、配送先ノードと略す）を決定する。このようなパケット経路制御部１２１は、配送確率行列１３５を作成するパケット配送確率計算部１２４と、乱数発生部１２５１により乱数を発生させ、この配送確率行列１３５に示される配送確率に基づきパケットの配送先ノードを決定する配送先決定部１２５とを備える。また、パケット配送部１２２は、パケット経路制御部１２１により決定された配送先ノードへ、入出力部１１経由でパケットを配送する。さらに、キュー長取得部１２３は、隣接ノードそれぞれから、その隣接ノードのバッファのキュー長の情報を取得し、その情報を、記憶部１３のキュー長情報１３３として記録する。また、このキュー長取得部１２３は、他のノード１０（またはノード２０）から、自身のバッファ１３１のキュー長の問い合わせを受けたとき、この問い合わせ元のノード１０へ、自身のバッファ１３１のキュー長の情報を返信する。 Next, the configuration of the processing unit 12 will be described in detail. The processing unit 12 includes a packet route control unit 121, a packet delivery unit 122, and a queue length acquisition unit 123. Among these, the packet route control unit 121 creates a delivery probability matrix 135 (delivery probability information, details will be described later). Then, with reference to the generated delivery probability matrix 135, an adjacent node (hereinafter, abbreviated as a delivery destination node) that is the next delivery destination of the packet of the destination node k is determined. Such a packet route control unit 121 generates a random number by a packet delivery probability calculation unit 124 that creates a delivery probability matrix 135 and a random number generation unit 1251, and delivers a packet based on the delivery probability indicated in the delivery probability matrix 135. A delivery destination determination unit 125 that determines a destination node. The packet delivery unit 122 delivers the packet to the delivery destination node determined by the packet route control unit 121 via the input / output unit 11. Further, the queue length acquisition unit 123 acquires the queue length information of the buffer of the adjacent node from each adjacent node, and records the information as the queue length information 133 of the storage unit 13. Further, when this queue length acquisition unit 123 receives an inquiry about the queue length of its own buffer 131 from another node 10 (or node 20), the queue length of its own buffer 131 is sent to this inquiry source node 10. Reply with information.

パケット配送確率計算部１２４は、（１）最小コスト経路制御部１２４１による最小コスト経路制御に基づき、宛先ノードｋのパケットを隣接ノードｊへ配送する配送確率ｐ^（Ｓ）ｋ _ｉｊと、（２）ランダムウォーク経路制御部１２４２によるランダムウォーク経路制御（隣接ノードそれぞれに同じ確率で配送する経路制御）に基づき、宛先ノードｋのパケットを隣接ノードｊへ配送する配送確率ｐ^（Ｒ）ｋ _ｉｊとを所定の割合で混合して、宛先ノードｋのパケットを隣接ノードｊへ配送する配送確率ｐ^ｋ _ｉｊを計算する。このパケット配送確率計算部１２４は、隣接ノードそれぞれのキュー長（キュー長情報１３３）をもとに、このｐ^ｋ _ｉｊを修正して配送確率ｐ＾^ｋ _ｉｊを得る。つまり、キュー長が長い（つまり、混雑している可能性が高い）隣接ノードを次の配送先ノードとして選択する確率を低くした配送確率ｐ＾^ｋ _ｉｊを得る。パケット配送確率計算部１２４は、このようなｐ^^ｋ _ｉｊの計算を、自身のノード１０の隣接ノードそれぞれ、宛先ノードそれぞれについて実行する。そして、このときの実行結果をもとに、配送確率行列１３５を作成する。 The packet delivery probability calculation unit 124 (1) delivery probability p ^{(S) k} _ij for delivering the packet of the destination node k to the adjacent node j based on the minimum cost route control by the minimum cost route control unit 1241, and (2) Based on random walk route control by the random walk route control unit 1242 (route control for delivering to each adjacent node with the same probability), a delivery probability p ^{(R) k} _ij for delivering the packet of the destination node k to the adjacent node j is predetermined. And the delivery probability p ^k _ij for delivering the packet of the destination node k to the adjacent node j is calculated. The packet delivery probability calculation unit 124 modifies this p ^k _ij based on the queue length (queue length information 133) of each adjacent node to obtain a delivery probability p ^ ^k _ij . That is, a delivery probability p ^ ^k _ij is obtained in which the probability of selecting an adjacent node having a long queue length (that is, a high possibility of congestion) as the next delivery destination node is reduced. The packet delivery probability calculation unit 124 executes the calculation of p ^ ^k _ij for each of the adjacent nodes of the node 10 and the destination node. Based on the execution result at this time, a delivery probability matrix 135 is created.

この最小コスト経路制御部１２４１は、ネットワークトポロジ情報１３２およびリンクコスト情報１３４を参照して、最小コスト経路制御による配送確率ｐ^（Ｓ）ｋ _ｉｊを計算する。この配送確率ｐ^（Ｓ）ｋ _ｉｊの計算の詳細は、具体例を用いて後記する。また、ランダムウォーク経路制御部１２４２は、ランダムウォーク経路制御による配送確率ｐ^（Ｒ）ｋ _ｉｊを計算する。 The minimum cost route control unit 1241 refers to the network topology information 132 and the link cost information 134, and calculates a delivery probability p ^{(S) k} _ij by the minimum cost route control. Details of the calculation of the delivery probability p ^{(S) k} _ij will be described later using a specific example. The random walk route control unit 1242 calculates a delivery probability p ^{(R) k} _ij by the random walk route control.

つまり、パケット配送確率計算部１２４は、以下の式（１）により、配送確率ｐ^（Ｓ）ｋ _ｉｊと、配送確率ｐ^（Ｒ）ｋ _ｉとを所定の割合で混合して配送確率ｐ^ｋ _ｉｊを計算する。

δ：ｐ^ｋ _ｉｊにおけるｐ^（Ｓ）ｋ _ｉｊの混合比率 That is, the packet delivery probability calculation unit 124 mixes the delivery probability p ^{(S) k} _ij and the delivery probability p ^{(R) k} _i at a predetermined ratio according to the following equation (1), and delivers the delivery probability p ^k _ij. Calculate

δ: mixing ratio of p ^(S) ^k _ij in p ^k _ij

このようにパケット配送確率計算部１２４は、最小コスト経路制御の配送確率のみならず、所定割合でランダムウォーク経路制御の配送確率を混合して、配送確率ｐ^ｋ _ｉｊを計算する。そして、ネットワークのノード１０それぞれが、このようにして計算した配送確率ｐ^ｋ _ｉｊに基づき、パケットの次の配送先ノードを決定することで、ネットワークにおけるパケットの配送経路が適度に分散するようになる。つまり、ネットワーク内に輻輳が発生しにくくなる。 Thus, the packet delivery probability calculation unit 124 calculates the delivery probability p ^k _ij by mixing not only the delivery probability of the minimum cost route control but also the delivery probability of the random walk route control at a predetermined rate. Then, each of the network nodes 10 determines the next delivery destination node of the packet based on the delivery probability p ^k _ij calculated in this way, so that the delivery route of the packet in the network is appropriately distributed. . That is, congestion is less likely to occur in the network.

また、パケット配送確率計算部１２４は、記憶部１３に記憶されたキュー長情報１３３（隣接ノードそれぞれのキュー長）をもとに、以下の式（２）に基づき、配送確率ｐ^ｋ _ｉｊを修正する。

ｑ_ｊ：隣接ノードｊにおけるキュー長
ｆ（ｑ）：キュー長ｑに関する減少関数 Further, the packet delivery probability calculation unit 124 corrects the delivery probability p ^k _ij based on the following equation (2) based on the queue length information 133 (the queue length of each adjacent node) stored in the storage unit 13. To do.

q _j : queue length in adjacent node j f (q): decreasing function for queue length q

つまり、パケット配送確率計算部１２４は、配送確率ｐ^ｋ _ｉｊに対し、その隣接ノードｊのキュー長と、自身のノード１０の隣接ノード（隣接ノードl）それぞれのキュー長および宛先ノードｋへのパケットを、次にその隣接ノードｌへ配送する配送確率ｐ^ｋ _ｉｌを乗算した値とを用いて重み付けを行い、配送確率ｐ^^ｋ _ｉｊを得る。ここで、ｆ（ｑ）は、キュー長ｑに関する減少関数であり、キュー長ｑが長い程、ｆ（ｑ）の値は小さいものとなる。また、ここで用いるｆ（ｑ）として、べき型、指数型等の関数を用いることができる。例えば、ｆ（ｑ）＝（ｑ＋１）^−αや、ｆ（ｑ）＝ｅｘｐ（−１０^−βｑ）等を用いることができる。ｆ（ｑ）＝（ｑ＋１）^−２を用いた場合、前記した式（１）におけるδの値は、例えば、δ＝０．９２〜０．９９とする。このときの実験結果については、後記する。 That is, the packet delivery probability calculation unit 124, for the delivery probability p ^k _ij , the queue length of the adjacent node j, the queue length of each of the adjacent nodes (adjacent node 1) of its own node 10, and the packet to the destination node k Is then weighted using a value ^obtained by multiplying the delivery probability p ^k _il to be delivered to the adjacent node 1 to obtain a delivery probability p ^ ^k _ij . Here, f (q) is a decreasing function related to the queue length q, and the longer the queue length q, the smaller the value of f (q). Further, as f (q) used here, a function such as a power type or an exponential type can be used. For example, f (q) = (q + 1) ^−α , f (q) = exp (−10− ^βq ), or the like can be used. When f (q) = (q + 1) ⁻² is used, the value of δ in the above equation (1) is, for example, δ = 0.92 to 0.99. The experimental results at this time will be described later.

また、記憶部１３は、バッファ１３１を所定領域に備え、ネットワークトポロジ情報１３２と、キュー長情報１３３と、リンクコスト情報１３４と、配送確率行列１３５とを記憶する。 The storage unit 13 includes a buffer 131 in a predetermined area, and stores network topology information 132, queue length information 133, link cost information 134, and a delivery probability matrix 135.

バッファ１３１は、パケットを一時的に蓄積する。ここで蓄積されたパケットは、他のノード１０，２０から受信したもののほか、自身のノード１０で新たに生成されたパケットを含んでいてもよい。この新たに生成されたパケットや、他のノード１０，２０から受信したパケットは、このバッファ１３１において既に蓄積されているパケットの最後尾に蓄積される。なお、バッファ１３１で配送を待っているパケットのバイト長をキュー長と呼ぶ。 The buffer 131 temporarily accumulates packets. The packets accumulated here may include packets newly generated by the own node 10 in addition to those received from the other nodes 10 and 20. The newly generated packet and the packet received from other nodes 10 and 20 are accumulated at the end of the packet already accumulated in the buffer 131. The byte length of a packet waiting for delivery in the buffer 131 is called a queue length.

ネットワークトポロジ情報１３２は、ネットワーク全体のトポロジを示した情報である。すなわち、このネットワークトポロジ情報１３２は、ネットワークにおいて、どのノード１０，２０と、どのノード１０，２０とが接続されているかを示した情報である。 The network topology information 132 is information indicating the topology of the entire network. That is, the network topology information 132 is information indicating which nodes 10 and 20 and which nodes 10 and 20 are connected in the network.

キュー長情報１３３は、隣接ノードそれぞれのバッファにおけるキュー長を示した情報である。このキュー長情報１３３は、キュー長取得部１２３により取得される最新のキュー長情報により更新される。 The queue length information 133 is information indicating the queue length in the buffer of each adjacent node. The queue length information 133 is updated with the latest queue length information acquired by the queue length acquisition unit 123.

リンクコスト情報１３４は、ネットワークトポロジ情報１３２に示される各ノード間を接続するリンクのリンクコストを示した情報である。 The link cost information 134 is information indicating the link cost of the link connecting each node indicated in the network topology information 132.

配送確率行列１３５は、宛先ノードｋごと、隣接ノードごとの配送確率ｐ＾^ｋ _ｉｊを示した情報である。この配送確率ｐ＾^ｋ _ｉｊは、配送先決定部１２５がパケットの配送先ノードを決定するときに参照される。 The delivery probability matrix 135 is information indicating the delivery probability p ^ ^k _ij for each destination node k and each adjacent node. The delivery probability p ^ ^k _ij is referred to when the delivery destination determination unit 125 determines the delivery destination node of the packet.

このようなノード１０によりネットワークを構成することで、ネットワーク内において混雑している可能性の高いノードへのパケットの配送を軽減し、輻輳に対する耐性を向上させることができる。 By configuring the network with such nodes 10, it is possible to reduce the delivery of packets to nodes that are highly likely to be congested in the network, and to improve resistance to congestion.

＜処理手順＞
次に、図２を参照しつつ、図３を用いて、ノード１０の処理手順を説明する。なお、ここでは事前に、ノード１０が配送確率行列１３５を作成して、記憶部１３に記憶しておくものとする。 <Processing procedure>
Next, the processing procedure of the node 10 will be described using FIG. 3 with reference to FIG. Here, it is assumed that the node 10 creates the distribution probability matrix 135 and stores it in the storage unit 13 in advance.

まず、図２のノード１０のパケット配送部１２２は、新規パケットをバッファ１３１から取り出し（Ｓ１０１）、このパケットの宛先ノード（宛先ノードの識別情報）を読み出す（Ｓ１０２）。ここで、この宛先ノードが隣接ノードであれば（Ｓ１０３のＹｅｓ）、パケット配送部１２２は、この宛先ノード（つまり、隣接ノード）へパケットを配送して（Ｓ１０４）、Ｓ１０１へ戻る。一方、Ｓ１０３において、宛先ノードが隣接ノードではなかったとき（Ｓ１０３のＮｏ）、キュー長取得部１２３は、キュー長情報１３３に最新のキュー長情報があるか否かを判断する（Ｓ１０５）。ここで、最新のキュー長情報がなかったとき（Ｓ１０５のＮｏ）、例えば、キュー長情報が、前回の取得から既に所定時間以上の経過したものであるとき、キュー長取得部１２３は、隣接ノードへキュー長の問い合わせを行い（Ｓ１０６）、この問い合わせの結果得られた隣接ノードのキュー長の情報を、キュー長情報１３３として記憶部１３に記録する。そして、パケット配送確率計算部１２４は、この最新のキュー長情報を用いて配送確率行列１３５を更新する。そして、Ｓ１０７へ進む。一方、最新のキュー長情報があったとき（Ｓ１０５のＹｅｓ）、Ｓ１０６をスキップして、Ｓ１０７へ進む。 First, the packet delivery unit 122 of the node 10 in FIG. 2 takes out a new packet from the buffer 131 (S101), and reads the destination node (identification information of the destination node) of this packet (S102). If the destination node is an adjacent node (Yes in S103), the packet delivery unit 122 delivers the packet to the destination node (that is, the adjacent node) (S104), and returns to S101. On the other hand, when the destination node is not an adjacent node in S103 (No in S103), the queue length acquisition unit 123 determines whether the queue length information 133 includes the latest queue length information (S105). Here, when there is no latest queue length information (No in S105), for example, when the queue length information has already passed a predetermined time since the previous acquisition, the queue length acquisition unit 123 The queue length is inquired (S106), and the queue length information of the adjacent node obtained as a result of this inquiry is recorded in the storage unit 13 as the queue length information 133. Then, the packet delivery probability calculation unit 124 updates the delivery probability matrix 135 using the latest queue length information. Then, the process proceeds to S107. On the other hand, when there is the latest queue length information (Yes in S105), S106 is skipped and the process proceeds to S107.

Ｓ１０５またはＳ１０６の後、パケット配送確率計算部１２４は、パケットの宛先ノードと、配送確率行列１３５とを参照して、このパケットの配送確率を計算する（Ｓ１０７）。つまり、配送確率行列１３５から、このパケットの配送確率を読み出す。そして、この配送確率を配送先決定部１２５へ出力する。 After S105 or S106, the packet delivery probability calculation unit 124 refers to the destination node of the packet and the delivery probability matrix 135 to calculate the delivery probability of this packet (S107). That is, the delivery probability of this packet is read from the delivery probability matrix 135. The delivery probability is output to the delivery destination determination unit 125.

Ｓ１０７の後、配送先決定部１２５は、乱数により、このパケットの配送先を決定する（Ｓ１０８）。つまり、配送先決定部１２５は、乱数発生部１２５１により乱数を発生させ、パケット配送確率計算部１２４から出力された配送確率に基づき、このパケットの配送先を決定する。 After S107, the delivery destination determination unit 125 determines the delivery destination of this packet using a random number (S108). That is, the delivery destination determination unit 125 generates a random number by the random number generation unit 1251 and determines the delivery destination of this packet based on the delivery probability output from the packet delivery probability calculation unit 124.

そして、パケット経路制御部１２２は、この配送先決定部１２５により決定された配送先ノードへパケットを配信する（Ｓ１０９）。 Then, the packet route control unit 122 distributes the packet to the delivery destination node determined by the delivery destination determination unit 125 (S109).

このような処理をノード１０はバッファ１３１から新規パケットを取り出すたびに実行する。ここで、ノード１０が、パケットの配送確率の計算に用いる配送確率行列１３５は、前記したとおり、最小コスト経路制御による配送確率ｐ^（Ｓ）ｋ _ｉｊと、ランダムウォーク経路制御による配送確率ｐ^（Ｒ）ｋ _ｉｊとを所定の割合で混合して計算した配送確率であり、また、この配送確率行列１３５に示される配送確率も、隣接ノードの混雑状況を考慮したものである。よって、ネットワークにおけるパケットの配送経路が適度に分散するようになり、その結果、ネットワークに輻輳が発生しにくくなる。 The node 10 executes such processing every time a new packet is extracted from the buffer 131. Here, the delivery probability matrix 135 used by the node 10 to calculate the packet delivery probability is, as described above, the delivery probability p ^{(S) k} _ij by the minimum cost route control and the delivery probability p ^(R by the random walk route control. ⁾ A distribution probability calculated by mixing ^k _ij at a predetermined ratio, and the distribution probability shown in the distribution probability matrix 135 also considers the congestion state of the adjacent nodes. Therefore, the packet delivery route in the network is appropriately distributed, and as a result, the network is less likely to be congested.

＜最小コスト経路制御の配送確率＞
ここで、前記した最小コスト経路制御部１２４１が最小コスト経路制御により配送確率ｐ^（Ｓ）ｋ _ｉｊを計算するためのアルゴリズムを、図４を用いて、詳細に説明する。この最小コスト経路制御とは、パケットの発生した発生ノードから宛先ノードまでの経路で経由するリンクのリンクコストの和が最小になるようなノード系列の経路による経路制御のことである。なお、各リンクのリンクコストが同じであるとすると、最小コスト経路制御は、最短経路制御に一致する。また、宛先ノードまでの経路が複数ある場合、その経路は、同じ確率でランダムに選択するものとする。つまり、ここでのｐ^ｋ _ｉｊは、隣接ノードｊを通る最小コスト経路の数を、宛先ノードｋへの最小コスト経路の総数で割った値となる。 <Distribution probability of minimum cost routing>
Here, an algorithm for calculating the delivery probability p ^{(S) k} _ij by the minimum cost route control unit 1241 by the minimum cost route control will be described in detail with reference to FIG. This minimum cost route control is a route control by a route of the node series that minimizes the sum of the link costs of the links passing through the route from the node where the packet is generated to the destination node. If the link cost of each link is the same, the minimum cost route control matches the shortest route control. When there are a plurality of routes to the destination node, the routes are selected at random with the same probability. That is, p ^k _ij here is a value obtained by dividing the number of minimum cost paths passing through the adjacent node j by the total number of minimum cost paths to the destination node k.

ここで、アルゴリズム中に登場する変数は以下の通りである。
Ｖ：すべてのノード集合
Ｐ：最小コスト（またはホップ数）が確定したノード集合
Ｅ_ｊ：ノードｊから配送されるべきノード集合
Ｎ_ｊ：ノードｊから、ノードｋまでの最小コスト経路の数
ｄ_ｊ：ノードｊから、ノードｋまでのコスト（またはホップ数）
ｃ_ｉｊ：ノードｉ（自身のノード１０）から、ノードｊへのリンクコスト Here, variables appearing in the algorithm are as follows.
V: All node sets P: Node set with minimum cost (or number of hops) E _j : Node set to be delivered from node j N _j : Number of minimum cost paths from node j to node k d _j : Cost from node j to node k (or number of hops)
c _ij : Link cost from node i (own node 10) to node j

まず、図２のノード１０の最小コスト経路制御部１２４１は、前処理として、トポロジ（ネットワークトポロジ情報１３２）とリンクコスト情報１３４とを収集し（Ｓ２０１）、記憶部１３に記憶する。 First, the minimum cost path control unit 1241 of the node 10 in FIG. 2 collects the topology (network topology information 132) and the link cost information 134 as preprocessing (S201) and stores them in the storage unit 13.

そして、最小コスト経路制御部１２４１は、各変数の初期化を行う（Ｓ２０２）。つまり、最小コスト経路制御部１２４１は、各変数に以下のような値を設定する。なお、「＼」は、ある集合からある集合を取り除いた集合を示す。例えば、Ｖ＼｛Ｓ｝であれば、ＶからＳを除いた集合を示す。
ｄ_Ｓ＝０、ｄ_ｊ＝∞ for ｊ∈Ｖ＼｛Ｓ｝
Ｐ＝φ
Ｎｓ＝１、Ｎ_ｊ＝０ for j≠Ｓ
Ｅ_ｊ＝φ for ｊ∈Ｖ
ｐ_ｉｊ＝０ for ｉ，ｊ∈Ｖ Then, the minimum cost route control unit 1241 initializes each variable (S202). That is, the minimum cost route control unit 1241 sets the following values for each variable. “\” Indicates a set obtained by removing a set from a set. For example, V \ {S} indicates a set obtained by removing S from V.
d _S = 0, d _j = ∞ for jεV \ {S}
P = φ
Ns = 1, N _j = 0 for j ≠ S
E _j = φ for j∈V
p _ij = 0 for i, j∈V

次に、最小コスト経路制御部１２４１は、最小コスト確定ノードを抽出し、そのノードの配送確率を計算する（Ｓ２０３）。つまり、最小コスト経路制御部１２４１は、
Ｑ＝argmin_{ｊ∈Ｖ＼Ｐ}｛ｄ_ｊ｝
ｐ_ｉｌ＝Ｎ_ｌ／Ｎ_ｊ for ｊ∈Ｑ，ｌ∈Ｅ_ｊ
Ｐ＝Ｐ∪Ｑ
とする。 Next, the minimum cost route control unit 1241 extracts a minimum cost fixed node and calculates a delivery probability of the node (S203). That is, the minimum cost route control unit 1241
Q = argmin _j∈V \ _P {d _j }
p _il = N ₁ / N _j for jεQ, lεE _j
P = P∪Q
And

次に、最小コスト経路制御部１２４１は、未確定ノードの最小コスト（仮最小コスト）を更新する。そして、それを実現する配送先（配送先ノード）を抽出する。また、そのときの最小コスト経路数を計算する（Ｓ２０４）。つまり、最小コスト経路制御部１２４１は、
Ｅ_ｊ＝argmin_{ｊ∈Ｖ＼Ｐ}｛ｄ_ｊ＋ｃ_ｊｉ｝ for ｉ∈Ｖ＼Ｐ
ｄ_ｊ＝min_{ｊ∈Ｖ＼Ｐ}｛ｄ_ｊ＋ｃ_ｊｉ｝ for ｉ∈Ｖ＼Ｐ
Ｎ_ｊ＝Σ_ｌ∈ＥｌＮ_ｌ
とする。 Next, the minimum cost route control unit 1241 updates the minimum cost (provisional minimum cost) of the indeterminate node. And the delivery destination (delivery destination node) which implement | achieves it is extracted. Further, the minimum cost path number at that time is calculated (S204). That is, the minimum cost route control unit 1241
E _j = argmin _j∈V \ _P {d _j + c _ji } for i∈V \ P
d _j = min _j∈V \ _P {d _j + c _ji } for i∈V \ P
N _j = Σ _l∈El N _l
And

そして、最小コスト経路制御部１２４１は、最小コストがすべて確定したとき（Ｓ２０５のＹｅｓ）、処理を終了する。一方、まだ最小コストが確定していないとき（Ｓ２０５のＮｏ）、Ｓ２０３へ戻る。 Then, the minimum cost route control unit 1241 ends the process when all the minimum costs are determined (Yes in S205). On the other hand, when the minimum cost has not yet been determined (No in S205), the process returns to S203.

以上の処理を、具体例を用いて説明する。ここでは、ネットワークが図５に示す構成であった場合を例に説明する。ネットワークは、ノードＡ〜Ｉにより構成されているものとする。また、ノードＡを宛先ノードとする。ここでは説明を簡単にするために、ホップ数のみに着目するのでｃ_ｉｊ＝１とする。 The above process will be described using a specific example. Here, a case where the network has the configuration shown in FIG. 5 will be described as an example. It is assumed that the network is composed of nodes A to I. Node A is the destination node. Here, in order to simplify the explanation, since only the number of hops is focused, c _ij = 1.

最小コスト経路制御部１２４１は、Ｓ２０２において各変数の初期化の手順に従い、各変数に初期値を代入する。つまり、最小コスト経路制御部１２４１は、
ｄ_Ａ＝０、ｄ_Ｂ＝ｄ_Ｃ＝…＝ｄ_Ｉ＝∞
Ｅ_Ａ＝Ｅ_Ｂ＝…＝Ｅ_Ｉ＝０
Ｎ_Ａ＝１，Ｎ_Ｂ＝Ｎ_Ｃ＝…＝Ｎ_Ｉ＝０
Ｐ＝φ，ｐ_ｉｊ＝０
とする。 In S202, the minimum cost route control unit 1241 substitutes initial values for each variable according to the initialization procedure for each variable. That is, the minimum cost route control unit 1241
d _A = 0, d _B = d _C =... = d _I = ∞
E _A = E _B = ... = E _I = 0
N _A = 1, N _B = N _C =... = N _I = 0
P = φ, p _ij = 0
And

次に、最小コスト経路制御部１２４１は、Ｓ２０３において、最小のｄ_ｊを見つけるが、今のところ宛先ノードであるノードＡだけである。ホップ数ももちろん０である。つまり、最小コスト経路制御部１２４１は、
Ｐ＝Ｑ＝｛Ａ｝，ｄ_Ａ＝０
を得る。 Next, in S203, the minimum cost route control unit 1241 finds the minimum _dj , but only the node A that is the destination node so far. Of course, the number of hops is zero. That is, the minimum cost route control unit 1241
P = Q = {A}, d _A = 0
Get.

そして、最小コスト経路制御部１２４１は、Ｓ２０４において、ｃ_Ａｊ＝１となるノードｊ、つまり隣接ノードに関する変数を更新する。すなわち、最小コスト経路制御部１２４１は、
ｄ_Ｂ＝ｄ_Ｃ＝１，Ｅ_Ｂ＝Ｅ_Ｃ＝｛Ａ｝，Ｎ_Ｂ＝Ｎ_Ｃ＝１
とする。 Then, in S204, the minimum cost route control unit 1241 updates the variable regarding the node j where c _Aj = 1, that is, the adjacent node. That is, the minimum cost route control unit 1241
d _B = d _C = 1, E _B = E _C = {A}, N _B = N _C = 1
And

ここでは、まだすべての最小コストは確定していないので（Ｓ２０５のＮｏ）、Ｓ２０３へ戻るが、最小ホップ数のノード１０は、ノードＢ，Ｃである。よって、最小コスト経路制御部１２４１は、
Ｑ＝｛Ｂ，Ｃ｝、Ｐ＝｛Ａ，Ｂ，Ｃ｝
ｐ_ＢＡ＝Ｎ_Ａ／Ｎ_Ｂ＝１，ｐ_ＣＡ＝Ｎ_Ａ／Ｎ_Ｃ＝１
を得る。 Here, since all the minimum costs have not yet been determined (No in S205), the process returns to S203, but the nodes 10 having the minimum number of hops are nodes B and C. Therefore, the minimum cost route control unit 1241
Q = {B, C}, P = {A, B, C}
_{_{_{_{p BA = N A / N B}}}} = 1, p CA = N A / N C = 1
Get.

この後、最小コスト経路制御部１２４１は、Ｓ２０４へ進み、ノードＤ，Ｅ，Ｆ，Ｇの値を更新する。つまり、最小コスト経路制御部１２４１は、
ｄ_Ｄ＝ｄ_Ｅ＝ｄ_Ｆ＝ｄ_Ｇ＝２
Ｅ_Ｄ＝Ｅ_Ｅ＝｛Ｂ｝，Ｅ_Ｆ＝｛Ｂ，Ｃ｝，Ｅ_Ｇ｛Ｃ｝
Ｎ_Ｄ＝Ｅ_Ｅ＝Ｎ_Ｇ＝１，Ｎ_Ｆ＝２
とする。 Thereafter, the minimum cost route control unit 1241 proceeds to S204 and updates the values of the nodes D, E, F, and G. That is, the minimum cost route control unit 1241
d _D = d _E = d _F = d _G = 2
E _D = E _E = {B}, E _F = {B, C}, E _G {C}
N _D = E _E = N _G = 1, N _F = 2
And

さらに、最小コスト経路制御部１２４１は、Ｓ２０３へ戻り、
Ｑ＝｛Ｄ，Ｅ，Ｆ，Ｇ｝、Ｐ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ｝
ｐ_ＤＢ＝ｐ_ＥＢ＝ｐ_ＧＣ＝１，ｐ_ＦＢ＝Ｎ_B／Ｎ_Ｆ＝＝１／２，ｐ_ＦＣ＝Ｎ_Ｃ／Ｎ_Ｆ＝＝１／２
を得る。また、Ｓ２０４へ進み、
ｄ_Ｈ＝ｄ_Ｉ＝３
Ｅ_Ｈ＝｛Ｄ，Ｆ｝，Ｅ_ｌ＝｛Ｅ，Ｆ，Ｇ｝
Ｎ_Ｈ＝Ｎ_Ｄ＋Ｎ_Ｆ＝３，Ｎ_ｉ＝Ｎ_Ｅ＋Ｎ_Ｆ＋Ｎ_Ｇ＝４
を得る。 Further, the minimum cost route control unit 1241 returns to S203,
Q = {D, E, F, G}, P = {A, B, C, D, E, F, G}
_{_{_{p DB = p EB = p GC}}} = 1, p FB = N B / N F = = 1/2, p FC = N C / N F = = 1/2
Get. Also, go to S204
d _H = d _I = 3
E _H = {D, F}, E _l = {E, F, G}
_{_{_{_{N H = N D + N F}}}} = 3, N i = N E + N F + N G = 4
Get.

そして、最終的に最小コスト経路制御部１２４１は、
Ｑ＝｛Ｈ，Ｉ｝、Ｐ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｉ｝
ｐ_ＨＤ＝Ｎ_Ｄ／Ｎ_Ｈ＝＝１／３，ｐ_ＨＦ＝Ｎ_Ｆ／Ｎ_Ｈ＝＝２／３，ｐ_ＩＥ＝Ｎ_Ｅ／Ｎ_Ｉ＝＝１／４，
ｐ_ＩＦ＝Ｎ_Ｆ／Ｎ_Ｉ＝＝２／４＝１／２，ｐ_ＩＧ＝Ｎ_Ｇ／Ｎ_Ｉ＝１／４
を得る。 Finally, the minimum cost route control unit 1241
Q = {H, I}, P = {A, B, C, D, E, F, G, H, I}
_{_{_{_{p HD = N D / N H}}}} = = 1/3, p HF = N F / N H = = 2/3, p IE = N E / N I = = 1/4,
_{_{_{p IF = N F / N I}}} = = 2/4 = 1/2, p IG = N G / N I = 1/4
Get.

＜ランダムウォーク経路制御の配送確率＞
次に、図６を用いて、前記したランダムウォーク経路制御部１２４２がランダムウォーク経路制御により配送確率ｐ^（Ｒ）ｋ _ｉｊを計算するためのアルゴリズムを説明する。ここでは、現在着目しているノード１０をノードｉ、このノードｉ以外のノード１０をノードｊとする。 <Random walk route control delivery probability>
Next, an algorithm for the random walk route control unit 1242 to calculate the delivery probability p ^{(R) k} _ij by the random walk route control will be described with reference to FIG. Here, it is assumed that the node 10 currently focused on is the node i, and the nodes 10 other than the node i are the nodes j.

まず、ランダムウォーク経路制御部１２４２は、パケットの宛先ノードｋが、ノードｉ（自身のノード１０）でなく（Ｓ３０１のＮｏ）、かつ、この宛先ノードｋが、ノードｊでなく（Ｓ３０３のＮｏ）、ノードｊがノードｉの隣接ノードであったとき（Ｓ３０５のＹｅｓ）、ノードｉのｄｅｇｒｅｅ（ｉ）（ノードｉの次数。つまり、ノードｉの隣接ノードの数）の逆数を用いることで、ｐ^（Ｒ）ｋ _ｉｊを計算する（Ｓ３０６）。一方、宛先ノードｋが、ノードｉ（自身のノード１０）であるとき（Ｓ３０１のＹｅｓ）、ｐ^（Ｒ）ｋ _ｉｊ＝０とする（Ｓ３０２）。また、宛先ノードｋがノードｊであるとき（Ｓ３０３のＹｅｓ）、ｐ^（Ｒ）ｋ _ｉｊ＝１とする（Ｓ３０４）。なお、ノードｊがノードｉの隣接ノードでなかったとき（Ｓ３０５のＮｏ）、ｐ^（Ｒ）ｋ _ｉｊ＝０とする（Ｓ３０７）。 First, the random walk route control unit 1242 determines that the destination node k of the packet is not the node i (own node 10) (No in S301), and the destination node k is not the node j (No in S303). , When node j is an adjacent node of node i (Yes in S305), by using the inverse of node i's degree (i) (the degree of node i, that is, the number of adjacent nodes of node i), p ^{(R) k} _ij is calculated (S306). On the other hand, when the destination node k is the node i (own node 10) (Yes in S301), p ^{(R) k} _ij = 0 is set (S302). When the destination node k is the node j (Yes in S303), p ^{(R) k} _ij = 1 is set (S304). When the node j is not an adjacent node of the node i (No in S305), p ^{(R) k} _ij = 0 is set (S307).

このようにすることで、ランダムウォーク経路制御部１２４２は、自身のノードｉにリンク接続される各隣接ノードとも同じ確率のｐ^（Ｒ）ｋ _ｉｊを計算する。また、パケットの宛先ノードｋが隣接ノードであれば、ｐ^（Ｒ）ｋ _ｉｊ＝１とするので、そのパケットを確実にその隣接ノードへ配送するようにできる。 In this way, the random walk route control unit 1242 calculates p ^{(R) k} _ij with the same probability for each adjacent node linked to its own node i. If the destination node k of the packet is an adjacent node, p ^{(R) k} _ij = 1, so that the packet can be reliably delivered to the adjacent node.

なお、図１で説明したノード２０は、宛先ノードｆであるノード２０との間にコネクションを確立して通信を行うオーバーレイネットワーク上のノードであってもよい。この場合、コネクションを確立して通信を行う経路上のいずれかのノード２０を隣接ノードとして考えればよい。このようにすることで、オーバーレイネットワークの輻輳に対する耐性を向上させることができる。 The node 20 described in FIG. 1 may be a node on the overlay network that establishes a connection with the node 20 that is the destination node f and performs communication. In this case, any node 20 on the path for establishing communication and performing communication may be considered as an adjacent node. By doing in this way, the tolerance with respect to the congestion of an overlay network can be improved.

＜実験結果＞
次に、前記したノード１０を用いたシミュレーション実験の結果を説明する。ここで構築したネットワークはBarabasi−Albert（Albert-Laszlo Barabasi, Reka Albert“Emergence of Scaling in Random Networks”，Science 286, p509-512,1999参照）に従い、指数が−３の、べき次数分布になるものである。 <Experimental result>
Next, the results of a simulation experiment using the node 10 will be described. The network constructed here follows Barabasi-Albert (see Albert-Laszlo Barabasi, Reka Albert “Emergence of Scaling in Random Networks”, Science 286, p509-512, 1999) and has an exponential distribution of -3. It is.

ここで、ネットワーク内で時刻ｔ＝０からパケットが発生し始め、現在時刻ｔだとする。この場合、これまでに発生したパケット総数をＧ（ｔ）とすると、ここで用いたモデルでは、＜Ｇ（ｔ）＞=ρＮｔとなる。＜＞は期待値を示す。また、ρはパケットの発生率である。また、Ｎはネットワークのノード数である。現在ネットワーク中に滞在しているパケット数をＭ（ｔ）とする。過渡期の影響を無視できる充分大きなｔで考えると、Ｍ（ｔ）は、以下の式（３）により表される。

Here, it is assumed that a packet starts to be generated from time t = 0 in the network and is the current time t. In this case, if the total number of packets generated so far is G (t), in the model used here, <G (t)> = ρNt. <> Indicates an expected value. Further, ρ is a packet generation rate. N is the number of nodes in the network. Let M (t) be the number of packets currently staying in the network. Considering a sufficiently large t that can ignore the influence of the transition period, M (t) is expressed by the following equation (3).

ただし、ｂ_ρおよびｃ_ρはρの関数である。ρが、閾値ρ_Ｃよりも小さければ、ネットワーク中のパケット総数Ｍ（ｔ）は、時刻ｔに関係なく所定の値ｃ_ρのままとなる。Ｌｉｔｔｌｅの法則によれば、パケットのネットワーク内の平均滞在時間は、ネットワーク内の滞留パケット数に比例するので、パケットは有限時間内で宛先ノードへと到着することになる。このときのネットワークの状態を非混雑状態という。一方、ρが閾値ρ_Ｃよりも大きければ、ネットワーク中のパケット総数は、時刻ｔに比例して増加する。このときパケットの到着時間はいくらでも大きくなり、この状態を混雑状態という。ここで混雑状態の指標として、以下の式（４）により計算されるηを考える。

Where b _ρ and c _ρ are functions of ρ. If ρ is smaller than the threshold ρ _C , the total number of packets M (t) in the network remains the predetermined value c _ρ regardless of the time t. According to Little's law, the average stay time of a packet in the network is proportional to the number of staying packets in the network, so that the packet arrives at the destination node within a finite time. The network state at this time is called a non-congested state. On the other hand, if [rho is larger than the threshold value [rho _C, total number of packets in the network increases in proportion to the time t. At this time, the arrival time of the packet increases as much as possible, and this state is called a congested state. Here, η calculated by the following equation (4) is considered as an indicator of the congestion state.

式（４）において、非混雑状態では、η＝０となり、混雑状態ではη＝ｂ_ρ／（ρＮ）＞０となるので、ηの値をみていれば混雑状態か否かを判別することができる。ここで、非混雑状態から、混雑状態に変化するρ_Ｃを、臨界パケット発生率ということにする。 In Expression (4), η = 0 in the non-congested state and η = b _ρ / (ρN)> 0 in the congested state, so that it can be determined whether or not it is in the congested state by looking at the value of η. it can. Here, ρ _C that changes from a non-congested state to a congested state is referred to as a critical packet occurrence rate.

ここで、ネットワークを、ノード１０を用いて構成し、そのネットワークは、１０００個のノード１０を備えることとした。ここで、前記した式（２）におけるキュー長ｑの減少関数としてｆ（ｑ）＝（ｑ＋１）^−２を用いた。η＝０．００１を基準として、この基準値を超えるρをρ_Ｃとして求めた。ここで、式（１）におけるδの値を変えたときの臨界パケット発生率ρ_Ｃを以下の表１に示す。 Here, the network is configured using the nodes 10, and the network includes 1000 nodes 10. Here, f (q) = (q + 1) ⁻² is used as a decreasing function of the queue length q in the above-described equation (2). relative to the eta = 0.001, was determined [rho exceeds the reference value as [rho _C. Here, the critical packet generation rate ρ _C when the value of δ in the equation (1) is changed is shown in Table 1 below.

表１に示すように、各ノード１０において配送先ノードを決定するとき、前記した式（１）の配送確率ｐ^ｋ _ｉｊを、最小コスト経路制御による配送確率ｐ^（ｓ）ｋ _ｉｊのみを用いて計算した場合（δ＝１.０）に比べ、この配送確率ｐ^（ｓ）ｋ _ｉｊにランダムウォーク経路制御により配送確率ｐ^（Ｒ）ｋ _ｉｊと混合した場合の方が、臨界パケット発生率ρ_Ｃの値が約３倍向上することが分かる。特にδ＝０．９２〜０．９９とすることで、ρ_Ｃ＝０．０３４となり、臨界パケット発生率ρ_Ｃの値が極めて向上していることが分かる。以上のことから、ネットワークを構成するノードとして、パケット経路制御部１２１を備えるノード１０を用いることで、ネットワーク内の輻輳に対する耐性を向上させることが確認できた。 As shown in Table 1, when the delivery destination node is determined in each node 10, the delivery probability p ^k _ij of the above-described formula (1) is used only by the delivery probability p ^{(s) k} _ij by the minimum cost path control. when calculated compared with ([delta] = 1.0), who when mixed with distribution probability ^{p _(R)} _{k ij} by a random walk path control to the distribution probability ^{p _(s)} _{k ij} is the critical packet generation rate [rho _C It can be seen that the value of is improved about 3 times. In particular, by setting δ = 0.92 to 0.99, it can be seen that ρ _C = 0.034, and the value of the critical packet generation rate ρ _C is extremely improved. From the above, it has been confirmed that by using the node 10 including the packet path control unit 121 as a node constituting the network, the tolerance to congestion in the network is improved.

１０（１０Ａ〜１０Ｈ），２０（２０Ａ〜２０Ｃ）ノード
１１入出力部
１２処理部
１３記憶部
１２１パケット経路制御部（パケット経路制御装置）
１２２パケット配送部
１２３キュー長取得部
１２４パケット配送確率計算部
１２５配送先決定部
１３１バッファ
１３２ネットワークトポロジ情報
１３３キュー長情報
１３４リンクコスト情報
１３５配送確率行列（配送確率情報）
１２４１最小コスト経路制御部
１２４２ランダムウォーク経路制御部
１２５１乱数発生部
10 (10A to 10H), 20 (20A to 20C) Node 11 Input / output unit 12 Processing unit 13 Storage unit 121 Packet path control unit (packet path control device)
122 packet delivery unit 123 queue length acquisition unit 124 packet delivery probability calculation unit 125 delivery destination determination unit 131 buffer 132 network topology information 133 queue length information 134 link cost information 135 delivery probability matrix (delivery probability information)
1241 Minimum cost route control unit 1242 Random walk route control unit 1251 Random number generation unit

Claims

A packet path control device for determining an adjacent node j to be a next delivery destination of the packet from adjacent nodes of the node i in a node that performs packet routing in the network;
Referring to the network topology of the network stored in the storage unit and the link cost of the link connecting each node of the network, the minimum cost route to the destination node k of the packet is calculated and connected to the minimum cost route A minimum cost route control unit that performs minimum cost route control by selecting the adjacent node j to be the next delivery destination of the packet;
As the next destination of the packet, by selecting the respective neighboring nodes j which is adjacent to the node i of themselves with equal probability, and a random walk path control unit for performing random routing,
Referring to queue length in the adjacent node j each buffer stored in the storage unit, as the next destination of the packet to the destination node k taken out from the buffer of the node i of the own of the own node i the probability ^p _{^ k ij} for selecting the neighbor node j, was calculated by the following formula (1) and (2), by generating a pseudo random number, the destination node based on the probability ^p _{^ k ij} that the calculated a packet path control unit that determines an adjacent node j to be a next delivery destination of a packet to k.

^[delta]: _p mixing ratio of ^{p _(S)} _{k ij} in _{k ij} q _j: queue length f in the adjacent node j (q): a decrease of the queue length q function p _{^(S) k ij:} minimum by the minimum-cost route control unit Probability of selecting an adjacent node j among adjacent nodes of its own node i as the next delivery destination of the packet to the destination node k by cost route control p ^{(R) k} _ij : Random by the random walk route control unit Probability of selecting adjacent node j from among adjacent nodes of node i as the next delivery destination of the packet to destination node k by walk route control

Claims wherein performs queue length of the query in the adjacent node j each buffer, characterized in that it comprises a queue length obtaining unit rewrite the queue length to the latest information in the adjacent node j each buffer stored in the storage unit 2. The packet path control device according to 1.

The packet routing unit, the probability p ^{^} _{k ij,} each neighboring node j of node i of the own previously calculated for each destination node k, the distribution probability calculation results of the probability p ^{^} _{k ij} that the calculated Information is stored in the storage unit, pseudo-random numbers are generated, the delivery probability information stored in the storage unit is referred to, and the packet to the destination node k is determined based on the calculated probability p ^ ^k _ij . 3. The packet path control apparatus according to claim 1, wherein an adjacent node j to be a next delivery destination is determined.

When f (q) = (q + 1) ⁻² is used as the decreasing function f (q) in the equation (2), δ = 0.92 to 0.99 in the equation (1) is set. The packet path control device according to any one of claims 1 to 3, wherein the packet path control device is characterized in that:

5. A node comprising the packet path control device according to claim 1 and delivering a packet to an adjacent node j that is a next delivery destination of the packet determined by the packet path control device.

The own node i is a node on the overlay network that establishes communication with the destination node k and performs communication.
The node according to claim 5, wherein the adjacent node j is the destination node k that establishes the connection and performs communication.

A packet path control method of a packet path control apparatus for determining an adjacent node j that is a next delivery destination of the packet from among adjacent nodes of the node i in a node that performs packet path control in the network,
Referring to the network topology of the network stored in the storage unit and the link cost of the link connecting each node of the network, the minimum cost route to the destination node k of the packet is calculated and connected to the minimum cost route the neighboring node j to, by selecting as the next destination of the packet, and the minimum cost path control section for minimum cost routing, as the next destination of the packet, the adjacent next to node i of themselves The packet path control device including a random walk path control unit that performs random path control by selecting each node j with the same probability,
Referring to queue length in the adjacent node j each buffer stored in the storage unit, as the next destination of the packet to the destination node k taken out from the buffer of the node i of the own of the own node i the probability ^p _{^ k ij} for selecting the neighbor node j, was calculated by the following formula (1) and (2), by generating a pseudo random number, the destination node based on the probability ^p _{^ k ij} that the calculated packet routing method characterized by determining the neighboring node j as the next destination of the packet to k.

^[delta]: _p mixing ratio of ^{p _(S)} _{k ij} in _{k ij} q _j: queue length f in the adjacent node j (q): a decrease of the queue length q function p _{^(S) k ij:} minimum by the minimum-cost route control unit Probability of selecting an adjacent node j among adjacent nodes of its own node i as the next delivery destination of the packet to the destination node k by cost route control p ^{(R) k} _ij : Random by the random walk route control unit Probability of selecting adjacent node j among adjacent nodes of node i as a delivery destination of the next packet to destination node k by walk route control

A packet path control program for causing a computer to function as the packet path control device according to any one of claims 1 to 4.

A computer-readable recording medium on which the packet path control program according to claim 8 is recorded.