[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

JP3243613B2 - 非サイクル有向グラフに関わる固有アドレス割当て、ノード自己識別及びトポロジーマッピングの方法及び装置 - Google Patents

非サイクル有向グラフに関わる固有アドレス割当て、ノード自己識別及びトポロジーマッピングの方法及び装置

Info

Publication number
JP3243613B2
JP3243613B2 JP51531694A JP51531694A JP3243613B2 JP 3243613 B2 JP3243613 B2 JP 3243613B2 JP 51531694 A JP51531694 A JP 51531694A JP 51531694 A JP51531694 A JP 51531694A JP 3243613 B2 JP3243613 B2 JP 3243613B2
Authority
JP
Japan
Prior art keywords
node
nodes
bus
signal
address
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Lifetime
Application number
JP51531694A
Other languages
English (en)
Other versions
JPH08505722A (ja
Inventor
オプレスク，フローリン
Original Assignee
アプル・コンピュータ・インコーポレーテッド
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by アプル・コンピュータ・インコーポレーテッド filed Critical アプル・コンピュータ・インコーポレーテッド
Publication of JPH08505722A publication Critical patent/JPH08505722A/ja
Application granted granted Critical
Publication of JP3243613B2 publication Critical patent/JP3243613B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L61/00—Network arrangements, protocols or services for addressing or naming
    • H04L61/50—Address allocation
    • H04L61/5038—Address allocation for local use, e.g. in LAN or USB networks, or in a controller area network [CAN]
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F13/00—Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units
    • G06F13/14—Handling requests for interconnection or transfer
    • G06F13/36—Handling requests for interconnection or transfer for access to common bus or bus system
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs
    • G06F15/163—Interprocessor communication
    • G06F15/173—Interprocessor communication using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
    • G06F15/17337—Direct connection machines, e.g. completely connected computers, point to point communication networks
    • G06F15/17343—Direct connection machines, e.g. completely connected computers, point to point communication networks wherein the interconnection is dynamically configurable, e.g. having loosely coupled nearest neighbor architecture
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/28—Data switching networks characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks]
    • H04L12/40—Bus networks
    • H04L12/40052—High-speed IEEE 1394 serial bus
    • H04L12/40078—Bus configuration
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/48—Routing tree calculation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L61/00—Network arrangements, protocols or services for addressing or naming
    • H04L61/50—Address allocation
    • H04L61/5092—Address allocation by self-assignment, e.g. picking addresses at random and testing if they are already in use

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Computer Hardware Design (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • Small-Scale Networks (AREA)
  • Bus Control (AREA)
  • Hardware Redundancy (AREA)
  • Multi Processors (AREA)
  • Mobile Radio Communication Systems (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Computer And Data Communications (AREA)

Description

【発明の詳細な説明】 発明の背景 関連出願 本出願は、それぞれ本出願の譲受人に譲渡されており
且つ本出願と同時に出願された出願Serial No.07/994,
983、名称「Method and Apparatus for Arbitratin
g on an Acyclic Directed Graph」及びSerial N
o.07/994,117、名称「Method and Apparatus for T
ransforming an Arbitrary Acyclic Topology Col
lection of Nodes into an Acyclic Directed G
raph」に関連している。
発明の分野 本発明はコンピュータシステムに関する。さらに特定
すれば、本発明は、コンピュータシステムの複数の任意
に組立てられた要素の間に通信方式を確立し且つそれを
利用する方法及び装置に関する。
背 景 所定のコンピュータシステムの内部の構成要素は、そ
れらの要素自体の間で信号を搬送する能力を必要とす
る。非常に単純なシステムでは、システムの各要素をシ
ステムのその他の全ての部品に直接ワイヤリングさせる
ことが可能である。しかし、現実には、コンピュータを
拡張自在にし、且つ未知の数のシステム部品に対応する
ために、コンピュータ設計者はずっと以前に通信バスの
概念を開発した。
バスは、コンピュータシステム全体を通って走る１本
又は複数本のワイヤなどの通信経路である。システムの
各構成要素は、システム中のその他の構成要素の各々に
理論上接続されるべきバスにプラグインされるだけで良
い。構成要素間には単一の通信チャネルしか存在しえな
いので、各構成要素が他の構成要素と同時に通信できな
いことは言うまでもない。通信バスを利用する場合、１
つの構成要素からの重要な情報部分をバスアクセスを待
機しながらの係属状態に放置することのない効率良い方
式で他の構成要素と通信するために各構成要素がバスを
使用できるように、何らかの形態で共用構造を確定する
ことが必要である。バス上の構成要素がバスを共用する
ための方法を一般にバスアービトレーション方式とい
う。
重要な情報の流れを最大にするようにバスアービトレ
ーション方式を最適化するという重大な要求に加えて、
柔軟性をできる限り残しつつシステム遅延を最小にする
ために、バス自体の物理的（及び論理的／電気的）構成
を最適化でき、また、そのようにすべきである。
バスに付随する他の構成要素と通信するためには、各
構成要素はそのバスに関して実現された通信規約と一致
する送受信回路などのハードウェアを具備しなければな
らない。そのような通信規格の１つは、この文書に付録
Ａとして添付されている表題「High Performance Ser
ial Bus」のIEEE規格文書P1394の中に記載されてい
る。P1394に記載されている規格は同じバックプレーン
上のカード、他のバックプレーン上のカード及び外部周
辺機器の間で低コストで相互接続を実行しようとするも
のである。
従来の技術のバス又はネットワークは、どれをどこに
プラグ接続すべきかを知ることを要求していた。たとえ
ば、多くのコンピュータの背面には、特定の周辺機器に
対応する指定ポートがある。コンピュータの中には、マ
ウス及びキーボードなどの構成要素に対してADBと呼ば
れるバスを使用し、他の周辺機器に対してはSCSIバスを
使用するMacintoshのようにいくつかのバスを実現する
ものもある。これらの型のバスはディジーチェーン要素
を一体に構成するが、その接続のトポロジーは限られて
いる。他に知られているバス／ネットワークは、ネット
ワークのノードをリングとして、すなわち、動作するた
めには閉成されなければならないループに配列すること
を要求する。最後に、星状配列、すなわち、ハブ・スポ
ーク配列は各ノードを中央マスタに直接リンクすること
を必要としていた。従来の技術のシステムの各々には、
望ましい程度の柔軟性が欠けている。
コンピュータの要素を１つのバスに任意に取り付ける
ことが可能であり、それに際して、任意トポロジーをシ
ステムにより構成要素の所定の配列を要求することなく
機能システムに変更できることが望ましいであろうし、
従って、それが本発明の目的である。
発明の概要 本発明の目的は、バスのノードが非サイクル有向グラ
フに変更されているコンピュータシステムの機能性を向
上させることである。
本発明の別の目的は、非サイクル有向グラフ上のノー
ドに固有アドレスを与えることである。
本発明の別の目的は、非サイクル有向グラフ上のノー
ドの集合体に対して自己識別メカニズムを提供すること
である。
本発明のさらに別の目的は、ノードの集合体のトポロ
ジーを非サイクル有向グラフトポロジーを非サイクル有
向グラフトポロジーを有するバスへとマッピングするメ
カニズムを提供することである。
本発明のさらに別の目的は、非サイクル有向グラフに
変更されたノードの任意集合体に対してホストシステム
にリンク冗長性情報を提供することである。
本発明のこれらの目的及びその他の目的は、システム
の様々な構成要素が通信バスに沿ったノードを介して相
互に接続されているようなコンピュータシステムにおい
て実現される。ノードのトポロジーが非サイクル有向グ
ラフに変更されたならば、各ノードにあらかじめ定めら
れたのではない固有アドレスを割当てても良い。複数の
ポートを有する各々のノードは、ポート選択に際して、
演繹的に割当てられた優先順位を有する。親ノードに接
続する各子ノードは、その子ノードが親に接続されると
きに通過するポートに応じて所定のシーケンスで応答で
きる。グラフ中の各ノードは、グラフ中のその場所に従
って、その存在をアナウンスする。各々は割当てられた
先のアドレスから増分されたアドレスを受信し、それに
より、固有性を確保する。このようにして、グラフ上の
各ノードに、バス中のトポロジー上の場所以外にノード
から識別特性を全く要求することなく、単純な方法によ
って固有アドレスを割当てる。各ノードにその局所ポス
トのパラメータに関する情報をバスを介して順次同報通
信させるために、同じメカニズムを実現しても良い。同
様に、他のノードへの接続に関する追加情報を各ノード
から搬送し、それにより、冗長性を目的として使用しう
るディスエーブルされたリンクに関する情報を含む解決
トポロジーのマップをホストシステムによって生成させ
ても良い。
図面の簡単な説明 本発明の目的、特徴及び利点は以下の詳細な説明から
明白になるであろう。その中で： 図１は、本発明に従って利用されるハードウェア層実
現のブロック線図を示す。
図２（ａ）〜図２（ｂ）は、ノードの任意の組立てら
れた集合体を示し、その一方は非サイクルであり、他方
は複数のサイクルを含む。
図３（ａ）は、本発明に従ったグラフ変換プロセスを
受ける図２（ａ）のノードの任意に組立てられた集合体
である。
図３（ｂ）〜図３（ｄ）は、本発明を実現するに際し
てのノード間の代替通信交換を示す。
図３（ｅ）は、図２（ａ）のノードの任意に組立てら
れたネットワークから得られる有向グラフを図式的に示
す。
図４は、ルート競合を解決することを要求する対称グ
ラフ配列を示す。
図５は、図示されうる固有アドレス割当て順序をもつ
非サイクル有向グラフを示す。
図６（ａ）〜図６（ｅ）は、本発明の好ましい実施例
に従ってグラフ変換手続きを実行するためのプロセスの
流れを示す。
発明の詳細な説明 任意のトポロジーを有するバスを利用する方法及び装
置を説明する。以下の説明中、本発明を完全に理解させ
るために様々なコンピュータ素子などの数多くの特定の
詳細な事項を述べる。しかしながら、そのような特定の
詳細な事項がなくとも本発明を実施しうることは当業者
には自明であろう。別の場合には、本発明を無用にわか
りにくくしないために周知の制御構造やコード化技法を
詳細には説明しなかった。
この詳細な説明を通して、説明に比喩による明確性を
与えるために数多くの描写用語を導入している。たとえ
ば、所定のトポロジーの中におけるノード間の親子関係
という表現がしばしば見られる。この目的は、最終的に
導出されるグラフに至る「方向」の概念を表わすことで
ある。以下に説明するように、任意のトポロジーが非サ
イクル有向グラフに変化されたならば、１つのノードは
「ルート」ノードとして識別されることになる。ルート
ノードは親ノードをもたず、ルートノードに論理の上で
すぐ隣接している全てのノードはそのルートの子ノード
である。「ツリー」の比喩は「ブランチ（枝）」及び
「リーフ（葉）」と呼ばれるノードを取り入れることに
よって完成する。
ここで説明するバスアーキテクチャは単一のコンピュ
ータに関わる素子に関連して説明されるのであるが、一
般に、より広い範囲を有する。本発明は、バストポロジ
ーを定義するに際して、装置のネットワークにおけるよ
うに一体にリンクされたノードの任意に組立てられたど
のような集合体にも適用可能である。注意しなければな
らない１点は、ノードと物理的コンピュータ素子とを区
別する必要があるということである。バスに常駐すべき
各素子に関連して、少なくとも１つのノード物理層制御
装置がある。状況によっては、所定の１つの素子を複数
のノードと関連させると有利であろうが、通常の場合に
は、バスにある装置又は素子と、ノードとの間には１対
１の対応がある。
そこで図１を参照すると、ノード10のブロック線図が
示されている。ノードを物理的にいかに実現するかは多
少は任意である。本発明の好ましい実施例の実現形態で
は、ノードは付録Ａとして添付したIEEE P1394 High
Performance Serial Bus通信規約に準拠するように
設計されている。ノード10はアービトレーション状態機
械論理11を含む。このアービトレーション状態論理機械
論理は、ここで説明すべき技法及びアルゴリズムを実行
するためのあらゆる論理回路を取り入れている。この回
路はプログラマブルロジックアレイ（PLA）から構成さ
れていても良く、あるいはここで説明する機能を実行す
るように独自に設計されていても良い。ノード論理によ
り実行されるべき機能を説明したならば、当業者はむや
みに説明を加えなくとも本発明を実現することができる
であろう。ノードは、その論理によって、バス初期設
定、ツリー識別、自己識別及びバスアービトレーション
の機能を含む最小限のアービトレーションプロトコルを
実現するが、それら全ての機能については以下にさらに
詳細に説明する。
図１に示すノード10は送信側マルチプレクサ12及び13
と、データ送信器、受信器及び再同期装置14とをさらに
含む。図１に示すノードは局所ホスト15に結合してい
る。局所ホスト15は、システム中の他の構成要素と通信
することが必要であるディスクドライブ、CPU、キーボ
ード又は他の何らかの構成要素などの、バスに付属させ
たい何らかの装置であれば良い。ノード10は通信リンク
を介して他のノードと通信する。リンクは２つのポート
の間の接続であって、直接的、実用的な用語でいえばケ
ーブルセグメントであるが、通常は何らかの物理通信チ
ャネルとして実現されれば良い。リンクは、最低でも、
それが接続する２つのポートの間に半二重通信チャネル
を構成することが可能であるべきであろう。ポートはノ
ードとリンクとの間のインタフェースである。本発明に
従えば、ポートはデータ及びアービトレーション信号を
送受信する能力を有していなければならない。ポート
は、それがリンクを介して別のポートに接続しているか
否かを判定することもできなければならない。これを容
易にする１つの方法は、接続しているポートによってリ
ンクを介して、リンクの他端にあるポートにより検出可
能であるバイアス電圧を印加させるというものである。
すなわち、１つのポートに、他端でポートに接続してい
ないリンク、裸リンクが付属している場合には、そのポ
ートは接続ポートではないと判定するのである。図１で
は、図示されているノード10は接続リンク17,18及び19
をそれぞれ有する３つの外部ポート21,22及び23を有す
る。
本発明を実現するためのノードに関わる実現規則のい
くつかは、１つのノードが１つ又は複数のポートを有し
ていて良いということである。ノードはそのポートのい
ずれか１つでデータを送受信可能であるべきであろう。
ノードは一度にイネーブルされているポートのうち唯一
つのポートでデータを受信可能であり且つ残る全てのイ
ネーブルされたポートではこのデータを送信可能である
べきであろう。ノードはそのポートの全てを介して信号
メッセージを同時に且つ独立して送受信可能であるべき
であろう。ノードのポートごとに別個の信号トランシー
バ、エンコーダ及びデコーダが要求される。最低限の実
現ノードは局所ホスト装置を必要としない。たとえば、
そのようなノードはケーブル延長として機能しても良
い。これ以降、装置及び局所ホストを無視し、バストポ
ロジーを言うときには、常に、ノードや様々なポートを
介するバス接続に関連させて説明する。
グラフ変換 図２（ａ）及び図２（ｂ）は、任意に組立てられたノ
ードの集合体を示す。これ以降、ノードを単に円として
示すが、ノードは、それぞれ、図１に関して説明した素
子と等価の素子を含むものと思われる。ただし、各ノー
ドはその図に示した３つより多い数又は少ない数の外部
ポートを有していても良いということに注意する。それ
ぞれのノードを結合する図示されている線は、リンクを
示すための方法である。ポートは図示されていないが、
暗黙のうちに、リンクとノードを接続するインタフェー
スである。
ここで説明するバスアービトレーション技法は、任意
のトポロジーを非サイクル有向グラフへと変更すること
を要求する。任意トポロジーグラフにおいては、ノード
とリンクの集合体は１つのサイクルを形成しても良い。
グラフ中の特定のノードから始まって、リンクを２度通
ることをせずにリンクとノードを通過することによって
同じノードに戻れる場合に、サイクルは成立する。図２
（ａ）は、図示されているノードはいずれもループの中
に接続していないことから、非サイクルグラフを示して
いる。ところが、図２（ｂ）は、境界規定ボックス25の
中の領域が複数のサイクルを形成するノード40〜47の集
合体を含んでいるために非サイクルグラフではない。説
明すべきバスアービトレーション技法はサイクルが存在
しないことを要求するので、ここではサイクルを変更す
るためのユーザ介入の方法についてもさらに説明する。
グラフを非サイクルしないという必要条件に加えて、
グラフは有向グラフでなければならない。有向グラフ
は、隣接ノードの間に階層構造が成立しているようなグ
ラフである。当初は、ノード間に親子関係は成立してい
ない。すなわち、たとえば、ノード31はノード34に対し
て「親ノード」であっても良く、あるいはノード34に対
して「子ノード」であっても良い。従って、所定の任意
トポロジーグラフを取り上げて、それを非サイクル有向
グラフに変換することが必要である。ここで説明する方
法は、ノードの数、あるいはノードが物理的にどのよう
にリンクしているかということとは無関係に且つリンク
に沿った信号伝搬時間には関係なく、どのような所定の
任意トポロジーに対してもこの変換を実行するように働
く。
ノード通信 まず、非サイクル任意トポロジーグラフを有向グラフ
に変換するプロセスを説明する。次に、サイクル変更が
要求されるケースを説明する。図３（ａ）は、ノードと
リンクが状態ラベルを有し且つ通信される信号はグラフ
を有向にするためのグラフ変換プロセスを表して指示さ
れているような図２（ａ）の任意グラフを示す。この時
点で、ノード間の信号通信を説明しておくと有益であ
る。図３（ｂ）は、リンク52によって結合された２つの
ノード50及び51（以下、それぞれノードＡと、ノード
Ｂ）を示す。説明した通り、リンクは図１に関連して先
に説明したように各々のノードのトランシーバポートを
結合する通信チャネルである。グラフ変換プロセスの
間、ノードは隣接するノードとの間に親子関係を成立さ
せることが必要になる。第１のノードのポートと第２の
ノードのポートとの間に少なくとも１つのリンクが接続
していれば、それら２つのノードは隣接ノードであると
いう。図３（ｂ）〜図３（ｄ）では、変更されるべき関
係はノードＢがノードＡの親であるということであり且
つノードはその関係を成立させることが適切であると仮
定する。
方向を設定するのに先立って、ノードＡがノードＢを
その親として成立させることが適切になったとき、ノー
ドＡはリンク52が結合しているポートから信号「You A
re My Parent」（YAMP）を送信する。このメッセージ
は、ノードＡがYAMP信号を発生していることをわかり且
つノードＢは受信したメッセージがYAMPであることを理
解できるのであれば、どのような形態をとっていても良
い。YAMP信号53がノードＢにより受信されると、ノード
Ｂは「You Are My Child」（YAMC）をリンク52を介
してノードＡへ送信することによってノードＡに応答す
る。ノードＡのアービトレーション状態機械論理11はYA
MP信号53の送信と、YAMC信号54の受信との間の時間遅延
を追跡し続ける。測定される時間は、ノードＡとノード
Ｂとの間の伝搬遅延の２倍を指定する。YAMC信号を受信
すると、ノードＡは「You Are My Child Acknowled
ged」（YAMCA）信号55をもって応答する。これは、ノー
ド間の伝搬時間遅延がYAMCの送信と、YAMCAの受信との
間の時間遅延と等しいことをも確定する能力をノードＢ
に与える。半二重通信リンクの場合、YAMCAメッセージ
は通信チャネルを適正に方向付けする効果をも有する。
全二重通信リンクの場合には、３つの論理メッセージ
YAMP、YAMC及びYAMCAを代わりに２回の信号送信のみに
よって中継することができる。図３（ｃ）にはこの状況
が示されており、ノードＡは戻りYAMC信号57を受信する
までYAMP信号56を加え続ける。YAMCA信号は、論理上
は、YAMP信号が到着しなくなったと検出されたときにノ
ードＢへ送信される。
説明したこの三重非同期メッセージ交換の使用によ
り、メッセージ交換に関わる双方のノードがリンクを介
する伝搬時間遅延を確定できるようなメカニズムが構成
される。この遅延値は以下にさらに説明する競合事象を
変更するとき、並びにバス性能を最適化するための正規
のバスアービトレーションの間に使用される。このパラ
メータの動的抽出は必須である。その代わりに、最適の
バス性能は得られなくとも最大伝搬時間遅延を演繹的に
規定することができる。
ノードＡ及びＢがノードＢはノードＡの親であること
を意味するメッセージを交換した後には、リンクは有向
になったと言うことができる。ノードＡはその論理によ
って、リンク52が結合しているポートを親ポート（親ノ
ードに話し掛ける）とラベル付けし、また、ノードＢは
リンク52が結合しているポートを子ポート（子ノードに
話し掛ける）とラベル付けする。以下に説明する方法は
所定の時点でノード及びポートに割当てられるラベルに
よって説明されるため、ポートが得るラベルを維持する
ことは大切である。図３（ｄ）には速記図式表記が示さ
れており、図中の方向矢印58はノードＢがノードＡの親
として設定されており且つリンクは有向であることを指
示している。
方向確定 ここで図３（ａ）に戻ると共に、図６（ａ）〜図６
（ｅ）のプロセスを参照して、任意トポロジー全体を方
向づけするプロセスを説明する。トポロジー変換プロセ
スの説明を助けるためには、若干多彩な定義を導入する
ことが必要である。第１に、「リーフ」ノードは１つの
ポートしか接続していないノードとして定義される。パ
ワーアップ後又は他のバス初期設定後に初期設定される
と、直ちにノードはその状態をリーフノードとして認識
する。「ブランチ」ノードは少なくとも２つの接続する
ポートを有するノードである。１つを除く全ての接続ポ
ートを介して、ブランチノードはYAMP信号を受信してお
り且つそれに応答している。残るポートを介して、ブラ
ンチノードはYAMP信号を送信しており、それにより、ノ
ードが親ノードであることを確定する。ノードは、１つ
の親を有しており（ノードは親ノードを１つしかもつこ
とができない）且つ他の全てのポートは子ノードに接続
していることを確定するまで、ブランチ状態には到達し
ない。ブランチ状態に達するのに先立って、ノードがブ
ランチであると確定されるまでノードが方向の設定を不
可能にするサイクルの一部である可能性は存在している
ので、ノードは「サイクル」ノードと考えられる。
グラフ変換手続きは、ステップ60で、バス初期設定
（パワーアップ又は誘導）のときに始まり、この時点で
任意トポロジーの中のリーフノードはステップ61で認識
し、決定ボックス66でそれらのノードが接続するポート
を唯一つしかもたないことを判定することによって、ス
テップ68でそれら自身をリーフノードとしてラベル付け
する。図３（ａ）に示すグラフにおいては、ノード33,3
5,36及び37は、初期設定後、ステップ69で各々がYAMP信
号を唯一の接続ポートを介して隣接するノードへ送信す
るリーフノードである。それらの信号を受信するノード
は、次に、ステップ70でYAMC信号をリーフノードへ伝搬
して戻すことにより、YAMCA通信が完了したときにはそ
れぞれの親子ペアの間の所定のリンクについて１つの方
向が確定する。ステップ71では、各リーフノードは１つ
の接続ポートを親ポートとしてラベル付けし、親ノード
にある各受信ポートは子ポートとしてラベル付けされ
る。
当初はリーフノードでないグラフ上のノードは、初
め、先に述べた理由によって「サイクルノード」と考え
られ、サイクルノード手続き63に従って進行する。接続
するポートのうち１つを除いて全てのポートを子ポート
としてラベル付けしているサイクルノードは、いずれ
も、後のステップ85で、残ったラベル付けされていない
ポートからYAMP信号を伝搬する。リンクについてその方
向が設定されたとき、そこでサイクルノードはブランチ
ノードとラベル付けされるようになる。すなわち、リー
フノード37がそのノード34を親として確定した後は、ノ
ード34は唯一つのラベルなしポートを有するので（ノー
ド37に至るリンク接続を子ポートを介するものとしてラ
ベル付けしている）、ノード34はYAMP信号をノード31へ
同報通信し、その結果、ノード34はブランチノードにな
る。同様に、ノード31がノード33及び34はその子ノード
であると識別したならば、ノード31はYAMP信号をノード
30へ同報通信する。１つのノードが決定ボックス75でそ
の全てのポートを介してYAMP信号を受信していたとき、
そのノードはルートノードになる。図３（ａ）で、ノー
ド30がノード31及び32からYAMP信号を受信した後、その
ラベルはサイクルノードからルートノードであると変わ
る。図３（ａ）のグラフにおいては、必ずしもノード30
がルートになる必要はないであろう。ツリー中のリンク
のうちいくつかが長い伝搬遅延を生じさせるのであれ
ば、ノード30は１つのポートでYAMP信号を受信してお
り、次に別のポートを介してYAMP信号を送信していたか
もしれない。ノードのいずれもルート、さらにはリーフ
になって良く、リーフは適正に手続きをとる。図３
（ｅ）は、図３（ａ）に示す通信信号に応答して、その
結果得られた有向グラフを示し、各ノードはラベル付け
されており且つ方向は黒の矢印によって指示されてい
る。
ルート競合 状況によっては、ルート競合状態が起こりうる。これ
は、たとえば、任意トポロジーが図４に示す任意トポロ
ジーに対し対称の配列を有するような場合に起こるであ
ろう。図４に示す任意グラフでは、ノード160及び161は
それが結合している２つのリーフノードに対して親であ
ることをそれぞれ確定している。次に、各ノードはYAMP
信号をほぼ同時に他方へ伝搬している。ルート競合状態
は決定ボックス86において関連する双方のノードにより
認識される。各ノードはそれを親として指定する信号を
受信しており、その一方で同じ信号を同じポートを介し
て送信している。競合しているノードの各々はステップ
91でYAMC信号によって他方に応答し、それにより、各ノ
ードはノード間の伝搬時間の２倍に等しい「決定時限」
を確定できる。
ルート競合状態は、各ノードの各々の任意状態機械論
理装置11に組込まれているランダム決定メカニズムを利
用することによって決定される。「決定時限」が経過す
るたびに、各ノードは、ステップ92で、再び他方へYAMP
信号を送信すべきか否かを無作為に（50％の確率をもっ
て）決定する。ほぼ確実に限られた数のサイクルの中
で、一方のノードはその一方が往復することなく他方を
親として指定することを決定する。親と指定されたほう
はステップ95でルートになる。あるいは、ノードに所定
の選択基準値を割当て、その大きいほう又は小さいほう
の値が競合事象でどちらが優勢であるかを判定するよう
にしても良い。「決定時限」の動的確定は最適の性能を
与えるものではあるが、本発明を実現する上で不可欠で
はない。その代わりに、このアルゴリズムを使用するど
のようなバスにおいても生じうる最悪の場合のリンク伝
搬より長くありさえすれば、演繹的に定義された「決定
時限」を使用しても良い。ルート競合を解決するために
使用するのと同じ方法が、以下にさらに説明する他の競
合事象を解決するためにも使用される。
ルート割当て 先に説明した通り、グラフ変換プロセスの結果はグラ
フ中の唯一つのノードへのルート属性の割当てである。
ルートノードは後述するバスアービトレーション方式に
おける最終的な決定を有し、従って、特別の優先順位時
間間隔を使用せずに最大の優先順位をもってバスをアク
セスすることができる。多くの場合、所定のシステムを
最適化するために、ノードが製造されるときに、もしく
は動的に（ランタイム中に）所定のノードにルート特性
を割当てることが可能であるのが望ましい。所定のバス
は、等時性データ転送を要求するノードを含んでいるか
もしれない。等時性データは、所定の時間に何らかの値
をもつように伝送されなければならないデータである。
たとえば、コンパクトディスクから発する音楽は、断片
的に転送され、必ずしも順序通りではないデータファイ
ルとは異なり、聴取すべき順序で、大きな遅れなく転送
され且つ出力される必要がある。
ルート指定に関してノードを３つのカテゴリに分類す
ることができる。それらの指定は、製造中、装置への指
定のハードワイヤリング、アービトレーション状態機械
論理のプログラミング又は決定を実行するより高いレベ
ルのソフトウェアの使用と、その後のその決定を維持し
たままの再ブートの開始によって適用されれば良い。ル
ートを指定されるのに関してノードが割当てられうる３
つの指定は：ルートとなることを望まないノードと、ル
ートになりうる（なるべき）ノードと、ルートになるで
あろうノードである。ステップ81及び83では、それらの
指定を試験する。第１のカテゴリに指定されるノード
は、指示されたときに直ちにグラフ変換手続きを開始す
る。これは、通常、バス初期設定手続きの完了の直後で
ある。第２のカテゴリのノードは、ステップ84でグラフ
変換手続きを開始することを指示された後に、そのプロ
セスの開始を所定の長さの時間だけ遅延させる。この遅
延によって、ノードはルートになる機会を増す。（YAMP
信号はその遅延によりそのノードまでより伝搬しやす
い。）遅延の追加にもかかわらず、「ルートになりう
る」ノードがルートと指定されることで終わらない可能
性は依然としてある。これは与えられたトポロジーと、
メッセージ伝搬遅延とによって決まる。遅延の量は、設
計中、相当に複雑なグラフを通るときの最悪の場合の妥
当な伝搬遅延より多くなるように定義できる。
ルート指定の可能性のうち第３のカテゴリに入るノー
ドは、グラフを既に変換し終わり且つ全てのノードはそ
れ自体を識別した後にルートにならなければならないと
いうことを認識するのみであろう。アービトレーション
状態機能論理がこの確定を実行しても良く、ホストシス
テムでランするソフトウェアであっても良い。これが起
こると、ルートにならなければならないノードはバスに
沿った他の全てのノードと、それが唯一のルートになろ
うとしていることを承諾し、以下でさらに説明する割込
形バス初期設定信号を発信することによってグラフ変換
プロセスを再開する。次に、ノードは、ステップ82で、
ルートになるのを待ち、その全てのポートでYAMP信号を
受信するまでグラフ変換に参加せず、それにより、その
ノードは必然的にルートと指定されることになる。
ルートが確定されたならば、グラフは有向であるとい
うことができる。グラフ上の全ての隣接ノードの間に定
義された関係が存在している。
サイクル変更 先に説明したグラフを有向にする手続きは非サイクル
グラフについてのみ働く。任意トポロジーの中にサイク
ルがあれば、ステップ80で始まる手続きによってサイク
ルを破断しなければならない。ステップ79で、所定の時
間切れ周期が経過した後に、ノードが依然としてリー
フ、ブランチ又はルートではなく、サイクルノードとラ
ベル付けされているとき、サイクルの存在は検出され
る。「サイクル検出」タイミングはバス初期設定機能の
終了の直後に始まる。時間切れ周期は最悪の場合のグラ
フ変換プロセスの持続時間（「ルートになりうる」ノー
ド及び起こりうるルート競合事象に関しての遅延時間の
追加）より長くなってはならない。
あらゆるメッセージ交換は非同期事象であるので、
「サイクル検出」時間切れ事象はグラフの全てのノード
に対して同時に起こる必要はない。そのため、「サイク
ル検出」時間切れ事象にまだ到達していないノードがサ
イクル解決は進行中であることを指示するメッセージを
受信することは可能である。そのようなノードはそのサ
イクル検出時間切れ間隔を終了し、適切なサイクル解決
プロセスを開始する。
本発明に従ったサイクル解決の方法は組立て後のノー
ドの集合体のユーザが介入することを要求する。ノード
が「サイクル検出」時間切れを受けると、システムのユ
ーザは図６（ｅ）のステップ100で、サイクルが存在し
ており且つノードが次に関連しない出力装置を介して通
知されるであろう。そこで、ユーザは、どのようなサイ
クルでも存在することを排除するために、リンクを遮断
することを命令される。次に、ユーザはグラフ変換手続
きに制御を戻す。
ループの各々が破断されて、サイクルが全く残ってい
ないのであれば、先の節で説明したようなグラフを変換
する手続きを、グラフ全体が非サイクルであると共に有
向になるまで進行させて良い。
固有物理アドレスの割当て 元の任意トポロジーから非サイクル有向グラフを確定
したならば、グラフの各ノードに固有の物理アドレスを
割当てることが可能である。このプロセスは、全てのリ
ーフノードがその単一の接続ポートを介してバス要求
（BR）信号を送信することによりバスを要求することを
もって始まる。その信号を受信した親ノードは、その子
ポートの全てからBR信号を受信し終わるまで待機し、次
にBR信号をその親に伝搬する。BR信号は、ルートがその
子の全てからBR信号を受信し終わるまでグラフを通って
伝搬する。ルートがその子ポートの全てを介してバス要
求を受信したならば、ルートはバスを１つのポートを介
して許可し且つその残る子ポートを介してバス拒否（B
D）信号を伝搬するための決定を実行する。どのバス要
求を許可すべきかを選択する方法は、先に、たとえば、
ポートを左から右へと又はポート番号づけに基づいて選
択する場合などについて説明したような演繹的決定であ
っても良い。バス許可（BG）信号はルートからそれが要
求している子へ送信される。その要求中の子が、それ自
体、その子のうち１つからバス要求を伝搬した親ノード
である場合には、その子ノードはその子ポートの１つを
除く全てのポートを介して先に説明したのと同じ所定の
方式でバス拒否信号を送信する。最終的には１つのリー
フノードがバス許可信号を受信し、そのノードはバス許
可確認（BGA）信号によって応答し、BGA信号はルートノ
ードへと伝搬されて戻る。BD信号とBGA信号の伝搬は半
二重通信チャネルの場合に必要になるであろう通信リン
クの方向を定める働きをする。そこで、拒否された全て
のノードは最終的にBG信号を受信するノードによるアク
ティビティを待つ。
最終的にバスに対するアクセスを許可されるノードは
アドレス割当てパケットを送信する。ノードはこのパケ
ットをバスを介して送信し、パケットは他の全てのノー
ドにより受信されて、それらのノードは、それぞれ、受
信するアドレスパケットの数をカウントする。送信され
るアドレスパケットは何らかの任意の情報を有していて
も良い。ノードの固有物理アドレスは、ノードがアドレ
スパケットを送信する前にカウントしたアドレスパケッ
トの数に基づいている。すなわち、前もってアドレス情
報は割当てられていないにもかかわらず、２つのノード
が同じ物理アドレスを獲得することはない。アドレスパ
ケットの実際の組成は任意であって、システムにより効
率良く利用可能な何らかのビットストリームであれば良
い。物理アドレス割当てパケットを送信した後、ノード
は「子ID完了」信号（CIC）信号を送信する。子ポート
でこれを受信した親ノードは、次に、「子識別完了確
認」（CICA）信号を送信し、ポートを識別済子ポートと
してラベル付けする。次のBR信号の伝搬に応答して、自
身を識別したばかりであるノードの親は物理アドレスパ
ケットを送信すべき次の子を選択する。１つの親ノード
の子ノードの全てが自身を識別したならば、親ノードは
バスを要求し、バスを許可したとき、その物理アドレス
割当てパケットを伝搬する。この手続きは、所定の選択
基準に従って、全てのノードがカウント動作によって固
有物理アドレス割当てを確定するまで続く。図５は、左
から右への事前定義済選択基準が実現されている図３
（ｅ）のグラフを示す。ノードは固有のアドレスを割当
てられ、ノード33は第１のアドレスを受信し、前述のよ
うに、ルートノード30は第８の、そして最後のアドレス
を受信する。
この手続きが完了すると、グラフ中の各ノードは固有
物質アドレスを有することになり、そのアドレスは前も
って確定されている必要はなく、システム管理又はその
他の目的のために利用されれば良い。
ノードの自己識別 ノード自己識別プロセスは本質的には先に説明した物
理アドレス割当て手続きと同一のルーチンに従う。各ノ
ードがその物理アドレス割当てパケットを送信すると
き、そのパケットはノードに関連する局所ホストのID、
それがどれほどの量の電力を必要とするか、さらに、た
とえば、「ソフトパワーオン」属性を支援するか否か等
々の別の情報を含んでいても良い。事実、ノード自己識
別情報は、どの情報を送信するにしても、それは固有物
理アドレスを獲得するためのカウントの基礎となること
から、物理アドレス割当てパケットとして働くのであ
る。
ノード自己識別パケットに関しては、ノードに関する
特定の情報は告知しているノードの性質によって影響を
受けるノードにより「聴取」されるだけで良い。先の場
合と同様に、この手続きは全ノードがそのノード自己識
別情報を送信し終わるまで進んで行く。
トポロジーマッピング トポロジーマッピングの方法は、物理アドレス割当て
及びノード自己識別と同じラインに沿って流れる。すな
わち、この手続きでは、各ノードがアドレス割当て又は
ノード自己識別のプロセスを経過しているとき、そのノ
ードに、ノードが有している子ポートの数及びディスエ
ーブルされたポートを有しているか否かなどの全てのポ
ートに関する情報をさらに送信する。ディスエーブルさ
れたポートに関しては、どこからディスエーブルされる
かを識別できるように、ディスエーブルしようとしてい
るポートの相互間に通信規約を実現することが望ましい
であろう。従って、ポートがディスエーブルされたポー
トを識別するとき、ポートはそれ独自のIDを指示する識
別子並びにディスエーブルされる元になったポートIDを
与える。
トポロジーマッピング手続きの間に受信する全てのポ
ートに関わるあらゆるトポロジー情報を組立てることに
より、ホスト又は何らかのソフトウェアレベルアプリケ
ーションは解決したバストポロジーを論理的に再構成で
きるであろう。これは、リンクが予想外に故障した場合
に、先にディスエーブルしたリンクがどのノードに対し
ても通信チャネルの損失を阻止するように働ける冗長性
を実現することを含む数多くの目的のために有用であ
る。
公正バスアクセスアービトレーション トポロジーマッピング、ノード自己識別又は物理アド
レス割当てのルーチンが完了したならば、バスが起動
し、ラン中であると考えることができる。本発明に従っ
て実現される１つのアービトレーション方式は、正当な
バスアクセスのアービトレーション方式である。バスに
対するアクセスを望むとき、ノードはその親ポートを介
して（それがルートでない限り）バス要求（BR）信号を
送信する。親は、１つの子からBR信号を受信すると、他
の全ての子ポートを介してバス拒否信号（BD）を送信す
る。そこで、親はBR信号をその親を通って、その信号が
ルートに到達するまで上方へと伝搬する。ルートはそれ
が受信する第１のBR信号に応答してバス許可信号（BG）
を発行すると共に、その他の全ての子ポートを介してBD
信号を送信し、BD信号は下方へと伝搬することにより、
リンクの方向を定める。BG信号は要求している側のノー
ドに到達するまでグラフを通って下方へと伝搬し、その
ノードは、次に、バス確認（BA）信号を送信し、それに
続くのはノードがバスへ送信することを必要とした情報
のパケットである。パケットが完了したとき、全てのノ
ードはアイドル状態に戻るか、又はアイドル状態に入
る。
ルートがバスに対するほぼ同時の要求を受信する場
合、ノードのうち１つにバスアクセスを許可するため
に、ルートノードに関わる所定の選択基準を使用するこ
とができる。これは先に説明したのと同じ所定の優先順
位選択基準であっても良い。
公正バスアクセスアービトレーションの別の一面は、
親ノードがその子に対して優先権をもつことである。す
なわち、親ノードは、バスを要求するときに、BD信号を
その子ポートの全てを介して送信し、次にBR信号をルー
トに向かって上方へと伝搬する。このメカニズムに伴っ
て起こりうる１つの問題は、親がバスを介して送信すべ
き大量の情報を有している場合に、子ノードが適切なバ
スアクセスを獲得するのに障害を生じるかもしれないと
いうことである。従って、当該技術では広く使用され且
つ良く知られているギャップシステムが導入されてい
る。ノードはバスを利用した後に、再びバスを要求でき
るようになる前にギャップ周期１つ分待機しなければな
らない。これにより、バス上におけるノードのトポロジ
ー配列にかかわらず、バスに沿ったどのノードにもバス
を許可される均等な機会が与えられるのである。公正ア
ービトレーションプロトコルを保証するためには、ギャ
ップの長さはバスを通過するときの最悪の場合の信号伝
搬遅延より大きくなければならない。ギャップ値をあら
かじめ確定して、ノード論理にハードワイヤリングする
ことができるが、そのような方式は、結果として、最も
極端なケースを除くあらゆる場合においてバスを最適に
近い形で利用できる。トポロジーマッピング能力は、グ
ラフ変換段階の間に実行される隣接ノード間の伝搬遅延
の測定とあいまって、どの特定の実現形態に対してもバ
ス性能を最適化する最適公正ギャップの計算を可能にす
る。
優先バスアービトレーション 上述の公正バスアクセスアービトレーションに従って
実現されるバスアービトレーション方式においては、ル
ートは常にバス優先権を有していることが望ましいであ
ろう。これが実現されるとき、ルートノードはそれ自身
にいつでもバスを許可して良い。これは、まず、BD信号
をグラフ中の全てのノードを通して下方へと送信するこ
とによって実行される。ルートに関わる優先バスアクセ
スは、等時性データ転送を実行するためにルートノード
が要求されるような場合に非常に有用である。
トークンパッシングバスアービトレーション 先に説明した公正バスアクセスアービトレーション方
式及び優先バスアクセスアービトレーション方式の代わ
りに、トークンパッシングバスアービトレーション方式
を実現するに際して本発明を利用しても良い。比喩的に
いえば、トークンパッシングバスアクセスは、バスがノ
ード間を渡されているトークンを所有しているときにノ
ードはバスを介して通信して良いという概念を表わす。
各ノードがサイクル中の所定のポイントでバスを受ける
ように、トークンはノードからノードへとサイクル方式
で渡されて行く。本発明においては、トークンパッシン
グは先に説明した物理アドレス割当てルーチンと同じ方
式に従って実現される。実現される所定の選択メカニズ
ムを使用して、トークンをノードからノードへと渡して
行く順序を選択する。この順序は、固有アドレス割当て
の順序を指示する図５に示すような順序に類似してい
る。各ノードは、トークンを割当てられたとき、残るノ
ードが聴取している間にバスに沿ってその情報パケット
を伝搬する。次に、ノードは、先に説明したような所定
の順序づけ方法に基づいてトークンを次の論理ノードに
渡す。
プレエンプティブバス初期設定 本発明に従って実現しうる重要な特徴は、プレエンプ
ティブバス初期設定の概念である。各ノードに組込まれ
ている状態機械論理は、いくつかの条件に対してノード
からその全てのポートを介して伝搬されるべきバス初期
設定（BI）信号をトリガすることができる。ノードがバ
ス初期設定条件を信号で報知する必要があると確定した
とき、ノードはBI信号をその全てのポートを介して、全
ての隣接ノードがその信号を受信し、次に変更するよう
に保証するのに十分な長さの時間だけ伝搬する。そこ
で、ノードはその後に先に説明した手続きの中でグラフ
変換プロセスに至る開始手続きに入る。
プレエンプティブバス初期設定をトリガすることを必
要にするか又は望ましくするであろういくつかの状況が
ある。第１に、これは予期せぬ誤りに対するノード応答
であっても良い。加えて、ホストレベルでは、異なるノ
ードがルート属性、たとえば、等時性データ転送ノード
を獲得すべきであることを確定しても良い。この割当て
はバス初期設定ルーチンを通して維持されるので、所望
のノードはルート指定を受信するまで変換手続きの間は
待機することになる。プレエンプティブバス初期設定に
至る別の条件はリンクの破断であろうが、その場合、付
属するノードについて新たな非サイクル有向グラフを計
算することが必要であろう。最後にプレエンプティブバ
ス初期設定が起こるべき重要な状況は、周辺機器の「ホ
ットアディション」と呼ばれるような、装置がネットワ
ークに追加されるときである。新たな装置が接続される
ポートは新たなノードの有無を検出し、システムのユー
ザに対しては透明であるが、たとえば、遮断と再給電の
必要なく周辺機器の増減を可能にするバス初期設定をト
リガする。追加されたノードの存在を含む新たな非サイ
クル有向グラフを計算する。いくつかのノードを取り除
いたとき、バス初期設定をトリガする必要はなくなる、
たとえば、リーフノードを取り除いたときには、ネット
ワークに害はないということはありうる。しかしなが
ら、動作中のバスからブランチノードが指定される場合
には、グラフを再構成する必要がありそうである。
本発明を好ましい実施例によって説明したが、当業者
により本発明の趣旨から逸脱せずに様々な変形や変更を
実施しうることは理解されるであろう。従って、本発明
は続く請求の範囲によって判断されるべきである。
フロントページの続き (56)参考文献 特開 昭62−237840（ＪＰ，Ａ) 特開 平４−196641（ＪＰ，Ａ) 特開 平４−196642（ＪＰ，Ａ) 特開 平１−272248（ＪＰ，Ａ) 特開 平５−153148（ＪＰ，Ａ) 高野 誠「マルチメディアＬＡＮにお ける自動構成管理方法」、電子情報通信 学会技術報告 ＩＮ92−28〜43、1992− ９−17、Ｖｏｌ．92 Ｎｏ．219、ｐ. 33−38 (58)調査した分野(Int.Cl.7，ＤＢ名) G06F 13/362 H04L 12/44 G06F 13/14

Claims (7)

    (57)【特許請求の範囲】
  1. 【請求項１】複数の通信リンクによって相互接続されて
    いる複数の構成要素を具備し、前記複数の構成要素はそ
    れぞれ少なくとも第１の通信ノードを有し、前記通信ノ
    ードはそれに関連する構成要素をノードポートを介して
    通信リンクとインタフェースし、各ノードは複数のポー
    トを有し、前記ポートはそれらのポートを介して結合さ
    れた隣接ノードに対して確定された所定の選択基準を有
    しており、前記ノードは複数のポートを有することがで
    き、ノードと通信リンクの前記構成は、１つのノードが
    ルートノードと指定され、唯一つの隣接ノードに結合す
    る全てのノードはリーフノードと指定され、グラフ中の
    他の全てのノードはブランチノードと指定されるような
    非サイクル有向グラフを構成し、全てのノードは、当
    初、未識別ノードの状態を有しており、前記非サイクル
    有向グラフはルートノードから下方の何らかのリーフノ
    ードへと進んで行く全ての隣接ノードの間の階層親子関
    係を成立させており、この親子関係では、リーフノード
    は唯一つの親ノードを有し且つルートノードに隣接する
    全てのノードはルートノードに関しては子ノードである
    が、他の隣接ノードに関しては親ノードであり、ルート
    ノードは親ノードをもたないものとして定義されるよう
    なコンピュータシステムにあって、グラフのノードに固
    有アドレスを割当てる方法において、 各々の未識別リーフノードが、初めに、「バス要求」
    （BR）信号をバスへ送信する過程と、 各ブランチノードは、全ての隣接子ノードがBR信号を伝
    搬する、すなわち、前進させるか、あるいは識別される
    まで待機し、次にBR信号を親ノードへ伝搬する過程と、 ルートノードは、全ての隣接ノードがBR信号を伝搬する
    か、あるいは識別されるまで待機し、次に、隣接ノード
    を選択するための前記所定の選択基準に基づいて隣接す
    る未識別ノードのうち１つへ「バス許可」（BG）信号を
    伝搬し、前記BG信号は、BR信号を開始させたノードがバ
    ス許可を受信するまで、隣接ノードを選択するための前
    記所定の選択基準に基づいて介入ノードを介してグラフ
    を通り下方へと伝搬されて行く過程と、 バス許可を受信したノードはバスに沿った全てのノード
    へアドレスアナウンスメントを同報通信する過程と、 バスに沿った全てのノードが同報通信されたアドレスア
    ナウンスメントの数をカウントする過程と、 各ノードは、そのノードが独自のアドレス同報通信を同
    報通信する前にカウントされたアドレス同報通信信号の
    カウントの数の関数であるノードの固有アドレスを設定
    し、次に、前記ノードは識別されたという状態を獲得す
    る過程と、 全てのノードが識別されるまで、上記の過程を繰り返す
    過程とから成り、 各ノードはそれ独自のアドレスを設定するのに先立っ
    て、異なる数のアドレス同報通信をカウントして各ノー
    ドが確実に固有アドレス割当てを獲得する方法。
  2. 【請求項２】バス許可を受信したノードは、同報通信中
    のノードと関連する構成要素に関するパラメータ情報を
    バスを介して全てのノードへ同報通信する過程をさらに
    含む請求項１記載の方法。
  3. 【請求項３】バス許可を受信したノードは、同報通信中
    のノードに関するトポロジー情報をバスを介して全ての
    ノードへ同報通信する過程をさらに含む請求項１記載の
    方法。
  4. 【請求項４】前記トポロジー情報はノード、隣接ノード
    及びリンク状態に関する情報を含む請求項３記載の方
    法。
  5. 【請求項５】複数の通信リンクによって相互接続されて
    いる複数の構成要素を具備し、前記複数の構成要素はそ
    れぞれ少なくとも第１の通信ノードを有し、前記通信ノ
    ードはそれに関連する構成要素をノードポートを介して
    通信リンクとインタフェースし、各ノードは複数のポー
    トを有し、前記ポートはそれらのポートを介して結合さ
    れた隣接ノードに対して確定された所定の選択基準を有
    しており、前記ノードは複数のポートを有することがで
    き、ノードと通信リンクの前記構成は、１つのノードが
    ルートノードと指定され、唯一つの隣接ノードに結合す
    る全てのノードはリーフノードと指定され、グラフ中の
    他の全てのノードはブランチノードと指定される非サイ
    クル有向グラフを構成し、全てのノードは、当初、未識
    別ノードの状態を有しており、前記非サイクル有向グラ
    フはルートノードから下方の何らかのリーフノードへと
    進んで行く全ての隣接ノードの間の階層親子関係を成立
    させており、この親子関係では、リーフノードは唯一つ
    の親ノードを有し且つルートノードに隣接する全てのノ
    ードはルートノードに対しては子ノードであるが、他の
    隣接ノードに対しては親ノードであり、ルートノードは
    親ノードをもたないものとして定義されているコンピュ
    ータシステムにあって、グラフのノードに固有アドレス
    を割当てる方法において、 各々の未識別リーフノードが、初めに、「バス要求」
    （BR）信号をバスへ送信する過程と、 各ブランチノードは、全ての隣接子ノードがBR信号を伝
    搬する、すなわち、前進させるか、あるいは識別される
    まで待機し、次にBR信号を親ノードへ伝搬する過程と； ルートノードは、全ての隣接ノードがBR信号を伝搬する
    か、あるいは識別されるまで待機し、次に、隣接ノード
    を選択するための前記所定の選択基準に基づいて「バス
    許可」（BG）信号を隣接する未識別ノードの中の１つへ
    伝搬し、前記BG信号は、BR信号を開始させたノードがバ
    ス許可を受信するまで、隣接ノードを選択するための前
    記所定の選択基準に基づいて介入ノードを介してグラフ
    を通り下方へと伝搬されて行く過程と、 バス許可を受信したノードはバスに沿った全てのノード
    へアドレスアナウンスメントを同報通信する過程と、 バス許可を受信したノードは、同報通信中のノードと関
    連する構成要素に関するパラメータ情報をバスに沿った
    全てのノードへ同報通信する過程と、 バスに沿った全てのノードが同報通信されるアドレスア
    ナウンスメントの数をカウントする過程と、 各ノードは、そのノードが同報通信される独自のアドレ
    スを同報通信する前にカウントされたアドレス同報通信
    信号のカウントの数の関連する固有アドレスを設定し、
    前記ノードは、次に、識別されるという状態を獲得する
    過程と； 全てのノードが識別されるまで上記の過程を繰り返す過
    程とから成り、 各ノードはそれ独自のアドレスを設定するのに先立って
    異なる数のアドレス同報通信をカウントして各ノードが
    確実に固有アドレス割当てを獲得する方法。
  6. 【請求項６】複数の通信リンクによって相互接続されて
    いる複数の構成要素を具備し、前記複数の構成要素はそ
    れぞれ少なくとも第１の通信ノードを有し、前記通信ノ
    ードはそれに関連する構成要素をノードポートを介して
    通信リンクとインタフェースし、各ノードは複数のポー
    トを有しており、前記ポートはそれらのポートを介して
    結合する隣接ノードについて確定される所定の選択基準
    を有し、前記ノードは複数のポートを有することがで
    き、ノードと通信リンクの前記構成は、１つのノードが
    ルートノードと指定され、唯一つの隣接ノードに結合す
    る全てのノードはリーフノードと指定され、グラフ中の
    他の全てのノードはブランチノードと指定される非サイ
    クル有向グラフを構成し、全てのノードは、当初、未識
    別ノードの状態を有しており、前記非サイクル有向グラ
    フはルートノードから何らかのリーフノードへ下方へと
    進んで行く全ての隣接ノードの間の階層親子関係を確定
    しており、その親子関係では、リーフノードは唯一つの
    親ノードを有し且つルートノードに隣接する全てのノー
    ドはルートノードに関しては子ノードであるが、他の隣
    接ノードに関しては親ノードであり、ルートノードは親
    ノードをもたないものとして定義されているコンピュー
    タシステムにあって、グラフのノードに固有アドレスを
    割当てる方法において、 各々の未識別リーフノードが初めに、「バス要求」（B
    R）信号をバスへ送信する過程と、 各ブランチノードは、全ての隣接子ノードがBR信号を伝
    搬する、すなわち、前進させるか、あるいは識別される
    まで待機し、次にBR信号を親ノードへ伝搬する過程と、 ルートノードは、全ての隣接ノードがBR信号を伝搬する
    か、あるいは識別されるまで待機し、次に、隣接ノード
    を選択するための前記所定の選択基準に基づいて隣接す
    る未識別ノードの中の１つへ「バス許可」（BG）信号を
    伝搬し、前記BG信号は、BR信号を開始させたノードがバ
    ス許可を受信するまで、隣接ノードを選択するための前
    記所定の選択基準に基づいて介入するノードを介してグ
    ラフを通り下方へと伝搬されて行く過程と、 バス許可を受信したノードはバスに沿った全てのノード
    へアドレスアナウンスメントを同報通信する過程と、 バス許可を受信したノードは、同報通信中のノードと関
    するトポロジー情報をバスに沿った全てのノードへ同報
    通信する過程と、 バスに沿った全てのノードは同報通信されるアドレスア
    ナウンスメントの数をカウントする過程と、 各ノードは、そのノードが同報通信される独自のアドレ
    スを同報通信する前にカウントされたアドレス同報通信
    信号のカウントの数の関数である固有アドレスを設定
    し、前記ノードは、次に識別されたという状態を獲得す
    る過程と、 全てのノードが識別されるまで上記の過程を繰り返す過
    程とから成り、 各ノードはそれ独自のアドレスを設定するのに先立って
    異なる数のアドレス同報通信をカウントして各ノードが
    確実に固有アドレス割当てを獲得する方法。
  7. 【請求項７】前記トポロジー情報は、ノード、隣接ノー
    ド及びリンク状態に関する情報を含む請求項６記載の方
    法。
JP51531694A 1992-12-21 1993-12-16 非サイクル有向グラフに関わる固有アドレス割当て、ノード自己識別及びトポロジーマッピングの方法及び装置 Expired - Lifetime JP3243613B2 (ja)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US07/994,402 US5394556A (en) 1992-12-21 1992-12-21 Method and apparatus for unique address assignment, node self-identification and topology mapping for a directed acyclic graph
US07/994,402 1992-12-21
US994,402 1992-12-21

Publications (2)

Publication Number Publication Date
JPH08505722A JPH08505722A (ja) 1996-06-18
JP3243613B2 true JP3243613B2 (ja) 2002-01-07

Family

ID=25540634

Family Applications (1)

Application Number Title Priority Date Filing Date
JP51531694A Expired - Lifetime JP3243613B2 (ja) 1992-12-21 1993-12-16 非サイクル有向グラフに関わる固有アドレス割当て、ノード自己識別及びトポロジーマッピングの方法及び装置

Country Status (9)

Country Link
US (1) US5394556A (ja)
EP (2) EP1197870B1 (ja)
JP (1) JP3243613B2 (ja)
KR (1) KR100316208B1 (ja)
AU (1) AU5954094A (ja)
CA (4) CA2408532C (ja)
DE (2) DE69332778T2 (ja)
HK (1) HK1041734B (ja)
WO (1) WO1994015303A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN100402572C (zh) * 2006-01-24 2008-07-16 浙江林学院 三聚氰胺和竹木酚液化物改性酚醛树脂生产方法

Families Citing this family (124)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3194318B2 (ja) * 1993-07-19 2001-07-30 ソニー株式会社 バス管理方法
JP3318635B2 (ja) * 1994-02-24 2002-08-26 ソニー株式会社 電子機器及び通信方法
US5634004A (en) * 1994-05-16 1997-05-27 Network Programs, Inc. Directly programmable distribution element
US6763454B2 (en) * 1994-05-27 2004-07-13 Microsoft Corp. System for allocating resources in a computer system
US5577213A (en) * 1994-06-03 1996-11-19 At&T Global Information Solutions Company Multi-device adapter card for computer
EP0685803B1 (en) 1994-06-03 2001-04-18 Hyundai Electronics America Method of producing an electrical device adapter
IL110859A (en) * 1994-09-04 1999-12-31 Rit Techn Ltd Interconnection monitor system for telephone network
US5724517A (en) * 1994-09-27 1998-03-03 International Business Machines Corporation Method for generating a topology map for a serial bus
US6115764A (en) * 1994-09-27 2000-09-05 International Business Machines Corporation Acyclic cable bus having redundant path access
US5615404A (en) * 1994-10-31 1997-03-25 Intel Corporation System having independently addressable bus interfaces coupled to serially connected multi-ported signal distributors generating and maintaining frame based polling schedule favoring isochronous peripherals
US5742847A (en) * 1994-10-31 1998-04-21 Intel Corporation M&A for dynamically generating and maintaining frame based polling schedules for polling isochronous and asynchronous functions that guaranty latencies and bandwidths to the isochronous functions
US5623610A (en) * 1994-10-31 1997-04-22 Intel Corporation System for assigning geographical addresses in a hierarchical serial bus by enabling upstream port and selectively enabling disabled ports at power on/reset
US5621901A (en) * 1994-10-31 1997-04-15 Intel Corporation Method and apparatus for serial bus elements of an hierarchical serial bus assembly to electrically represent data and control states to each other
DE19581234B4 (de) * 1994-10-31 2008-03-20 Intel Corp., Santa Clara Bussteuereinrichtung und Verfahren für eine hierarchische serielle Busanordnung unter Verwendung von Kommunikationspaketen
US5634113A (en) * 1994-12-13 1997-05-27 Unisys Corporation Method for generating a preferred processing order and for detecting cycles in a directed graph used to represent system component connectivity
US7334030B2 (en) * 1994-12-19 2008-02-19 Apple Inc. Method and apparatus for the addition and removal of nodes from a common interconnect
US5875301A (en) * 1994-12-19 1999-02-23 Apple Computer, Inc. Method and apparatus for the addition and removal of nodes from a common interconnect
JP3348331B2 (ja) * 1995-04-21 2002-11-20 ソニー株式会社 電子機器及びその動作モード制御方法
US5568644A (en) * 1995-05-05 1996-10-22 Apple Computer, Inc. Method and apparatus using a tree structure for the dispatching of interrupts
DE69634500T2 (de) * 1995-06-15 2006-04-13 Koninklijke Philips Electronics N.V. Datenbussystem mit Mitteln zur Ressourcensteuerung und Übertragungsstation
US5802057A (en) 1995-12-01 1998-09-01 Apple Computer, Inc. Fly-by serial bus arbitration
US5784648A (en) * 1995-12-01 1998-07-21 Apple Computer, Inc. Token style arbitration on a serial bus by passing an unrequested bus grand signal and returning the token by a token refusal signal
FI103544B1 (fi) * 1996-03-25 1999-07-15 Nokia Telecommunications Oy Menetelmä osoitteiden määrittämiseksi tietoliikenneverkon solmuissa
US5764930A (en) * 1996-04-01 1998-06-09 Apple Computer, Inc. Method and apparatus for providing reset transparency on a reconfigurable bus
US5793366A (en) * 1996-11-12 1998-08-11 Sony Corporation Graphical display of an animated data stream between devices on a bus
US5805088A (en) * 1996-11-01 1998-09-08 International Business Machines Corporation High speed asynchronous serial to parallel data converter
US5930264A (en) * 1997-02-06 1999-07-27 Telefonaktiebolaget L M Ericsson (Publ) Inter-node signaling for protocol initialization within a communications network
US6131119A (en) * 1997-04-01 2000-10-10 Sony Corporation Automatic configuration system for mapping node addresses within a bus structure to their physical location
JP3222086B2 (ja) * 1997-04-07 2001-10-22 矢崎総業株式会社 ツリー構造のアドレス設定方法及びそのシステム
US6098067A (en) * 1997-05-02 2000-08-01 Kabushiki Kaisha Toshiba Remote computer management system
JP3247074B2 (ja) * 1997-06-26 2002-01-15 矢崎総業株式会社 アドレス設定方法、及びこのアドレス設定方法が適用される通信システム
US6421069B1 (en) 1997-07-31 2002-07-16 Sony Corporation Method and apparatus for including self-describing information within devices
JP4054451B2 (ja) * 1997-08-26 2008-02-27 キヤノン株式会社 通信装置
US6041286A (en) * 1997-10-21 2000-03-21 Sony Corporation Apparatus for and method of accurately obtaining the cycle time of completion of transmission of video frames within an isochronous stream of data transmitted over an IEEE 1394 serial bus network
US5996090A (en) * 1997-10-29 1999-11-30 International Business Machines Corporation Method and apparatus for quantitative diagnosis of performance problems using external representations
US6145018A (en) * 1997-11-24 2000-11-07 Intel Corporation Method for hindering some types of nodes from becoming a bus arbitration controller
US6041348A (en) * 1997-12-01 2000-03-21 Lsi Logic Corporation N-port algorithm for disabling a node within a network during reset
US6411628B1 (en) * 1998-02-02 2002-06-25 Intel Corporation Distributed arbitration on a full duplex bus
SG77163A1 (en) 1998-03-06 2000-12-19 John Francis Chong A method of implementing an acyclic directed graph structure using a relational database
US6233611B1 (en) 1998-05-08 2001-05-15 Sony Corporation Media manager for controlling autonomous media devices within a network environment and managing the flow and format of data between the devices
FR2779301B1 (fr) * 1998-05-26 2000-07-21 Thomson Multimedia Sa Procede d'identification d'appareils dans un reseau de communication et appareil de mise en oeuvre
US6442171B1 (en) 1998-05-26 2002-08-27 Qualcomm Incorporated Logical topology and address assignment for interconnected digital networks
US6108698A (en) * 1998-07-29 2000-08-22 Xerox Corporation Node-link data defining a graph and a tree within the graph
US7013354B1 (en) 1998-10-05 2006-03-14 Canon Kabushiki Kaisha Channel protocol for IEEE 1394 data transmission
US6438604B1 (en) 1998-10-05 2002-08-20 Canon Kabushiki Kaisha Digital video network interface
KR100272108B1 (ko) * 1998-10-13 2000-11-15 윤종용 Ieee 1394 가상 네트웍 생성방법 및 그 콘트롤러
US6173342B1 (en) 1998-10-19 2001-01-09 Hitachi Semiconductor America, Inc. High speed bus interface for peripheral devices
US6327637B1 (en) 1998-12-18 2001-12-04 Cirrus Logic, Inc. Interface tap for 1394-enabled serial bus device
JP3527649B2 (ja) 1999-02-10 2004-05-17 矢崎総業株式会社 通信方法、通信システム、及びこの通信システムに用いられるゲートウェイ
JP2000235434A (ja) 1999-02-17 2000-08-29 Toshiba Corp 電子機器および電源制御方法
US6810452B1 (en) * 1999-03-19 2004-10-26 Sony Corporation Method and system for quarantine during bus topology configuration
DE60019750T2 (de) * 1999-06-11 2005-09-29 Microsoft Corp., Redmond Allgemeines api zur gerätefernsteuerung
US6725281B1 (en) 1999-06-11 2004-04-20 Microsoft Corporation Synchronization of controlled device state using state table and eventing in data-driven remote device control model
US6910068B2 (en) 1999-06-11 2005-06-21 Microsoft Corporation XML-based template language for devices and services
US6892230B1 (en) * 1999-06-11 2005-05-10 Microsoft Corporation Dynamic self-configuration for ad hoc peer networking using mark-up language formated description messages
JP4147689B2 (ja) * 1999-06-14 2008-09-10 ソニー株式会社 情報処理装置及び情報処理方法
US6628607B1 (en) 1999-07-09 2003-09-30 Apple Computer, Inc. Method and apparatus for loop breaking on a serial bus
JP2001036549A (ja) 1999-07-15 2001-02-09 Toshiba Corp データ処理システムおよびタイムスタンプ生成方法
US6910090B1 (en) 1999-09-21 2005-06-21 Sony Corporation Maintaining communications in a bus bridge interconnect
US6691096B1 (en) 1999-10-28 2004-02-10 Apple Computer, Inc. General purpose data container method and apparatus for implementing AV/C descriptors
US6959343B1 (en) 1999-11-01 2005-10-25 Apple Computer, Inc. Method and apparatus for dynamic link driver configuration
US6671768B1 (en) 1999-11-01 2003-12-30 Apple Computer, Inc. System and method for providing dynamic configuration ROM using double image buffers for use with serial bus devices
US6813663B1 (en) 1999-11-02 2004-11-02 Apple Computer, Inc. Method and apparatus for supporting and presenting multiple serial bus nodes using distinct configuration ROM images
US8762446B1 (en) 1999-11-02 2014-06-24 Apple Inc. Bridged distributed device control over multiple transports method and apparatus
US6618750B1 (en) 1999-11-02 2003-09-09 Apple Computer, Inc. Method and apparatus for determining communication paths
US6631426B1 (en) 1999-11-02 2003-10-07 Apple Computer, Inc. Automatic ID allocation for AV/C entities
US6636914B1 (en) 1999-11-05 2003-10-21 Apple Computer, Inc. Method and apparatus for arbitration and fairness on a full-duplex bus using dual phases
US6587904B1 (en) 1999-11-05 2003-07-01 Apple Computer, Inc. Method and apparatus for preventing loops in a full-duplex bus
US6457086B1 (en) 1999-11-16 2002-09-24 Apple Computers, Inc. Method and apparatus for accelerating detection of serial bus device speed signals
US6728821B1 (en) 1999-11-29 2004-04-27 Sony Corporation Method and system for adjusting isochronous bandwidths on a bus
US6751697B1 (en) * 1999-11-29 2004-06-15 Sony Corporation Method and system for a multi-phase net refresh on a bus bridge interconnect
US6639918B1 (en) 2000-01-18 2003-10-28 Apple Computer, Inc. Method and apparatus for border node behavior on a full-duplex bus
US7266617B1 (en) 2000-01-18 2007-09-04 Apple Inc. Method and apparatus for border node behavior on a full-duplex bus
US7421507B2 (en) * 2000-02-16 2008-09-02 Apple Inc. Transmission of AV/C transactions over multiple transports method and apparatus
US6831928B1 (en) 2000-02-17 2004-12-14 Apple Computer, Inc. Method and apparatus for ensuring compatibility on a high performance serial bus
US7050453B1 (en) 2000-02-17 2006-05-23 Apple Computer, Inc. Method and apparatus for ensuring compatibility on a high performance serial bus
US6529984B1 (en) * 2000-03-29 2003-03-04 Compaq Information Technologies Group, L.P. Dual phase arbitration on a bus
US6618785B1 (en) * 2000-04-21 2003-09-09 Apple Computer, Inc. Method and apparatus for automatic detection and healing of signal pair crossover on a high performance serial bus
US6718497B1 (en) 2000-04-21 2004-04-06 Apple Computer, Inc. Method and apparatus for generating jitter test patterns on a high performance serial bus
US6757773B1 (en) 2000-06-30 2004-06-29 Sony Corporation System and method for determining support capability of a device coupled to a bus system
WO2002023827A1 (en) * 2000-09-13 2002-03-21 Koninklijke Philips Electronics N.V. Communication system and device
DE10046311B4 (de) * 2000-09-19 2004-04-08 Siemens Ag Verfahren für eine Zuweisung von Knotennummern zu Netzknoten eines Netzwerks
JP4097891B2 (ja) * 2000-11-27 2008-06-11 三菱電機株式会社 Ｉｅｅｅ１３９４を用いた同期システム
US7171475B2 (en) 2000-12-01 2007-01-30 Microsoft Corporation Peer networking host framework and hosting API
JP3523616B2 (ja) 2001-07-24 2004-04-26 松下電器産業株式会社 バス最適化方法及び通信ノード
US6957318B2 (en) * 2001-08-17 2005-10-18 Sun Microsystems, Inc. Method and apparatus for controlling a massively parallel processing environment
US7082200B2 (en) * 2001-09-06 2006-07-25 Microsoft Corporation Establishing secure peer networking in trust webs on open networks using shared secret device key
US20030084219A1 (en) * 2001-10-26 2003-05-01 Maxxan Systems, Inc. System, apparatus and method for address forwarding for a computer network
US7145914B2 (en) 2001-12-31 2006-12-05 Maxxan Systems, Incorporated System and method for controlling data paths of a network processor subsystem
US7011392B2 (en) * 2002-01-24 2006-03-14 Industrial Technology Research Institute Integrated inkjet print head with rapid ink refill mechanism and off-shooter heater
US7082135B2 (en) * 2002-02-04 2006-07-25 General Instrument Corporation Extendable slot addressing system and method
US7406038B1 (en) 2002-04-05 2008-07-29 Ciphermax, Incorporated System and method for expansion of computer network switching system without disruption thereof
US7379970B1 (en) 2002-04-05 2008-05-27 Ciphermax, Inc. Method and system for reduced distributed event handling in a network environment
US7307995B1 (en) 2002-04-05 2007-12-11 Ciphermax, Inc. System and method for linking a plurality of network switches
US7295561B1 (en) 2002-04-05 2007-11-13 Ciphermax, Inc. Fibre channel implementation using network processors
US20030195956A1 (en) * 2002-04-15 2003-10-16 Maxxan Systems, Inc. System and method for allocating unique zone membership
US20030200330A1 (en) * 2002-04-22 2003-10-23 Maxxan Systems, Inc. System and method for load-sharing computer network switch
US20030202510A1 (en) * 2002-04-26 2003-10-30 Maxxan Systems, Inc. System and method for scalable switch fabric for computer network
US20040030766A1 (en) * 2002-08-12 2004-02-12 Michael Witkowski Method and apparatus for switch fabric configuration
US7417973B1 (en) * 2002-12-31 2008-08-26 Apple Inc. Method, apparatus and computer program product for ensuring node participation in a network bus
US7457302B1 (en) 2002-12-31 2008-11-25 Apple Inc. Enhancement to loop healing for malconfigured bus prevention
US20040255338A1 (en) * 2003-06-13 2004-12-16 Apple Computer, Inc. Interface for sending synchronized audio and video data
US7353284B2 (en) * 2003-06-13 2008-04-01 Apple Inc. Synchronized transmission of audio and video data from a computer to a client via an interface
US7668099B2 (en) * 2003-06-13 2010-02-23 Apple Inc. Synthesis of vertical blanking signal
US8275910B1 (en) 2003-07-02 2012-09-25 Apple Inc. Source packet bridge
US7788567B1 (en) 2003-11-18 2010-08-31 Apple Inc. Symbol encoding for tolerance to single byte errors
US7995606B1 (en) 2003-12-03 2011-08-09 Apple Inc. Fly-by and ack-accelerated arbitration for broadcast packets
US7502338B1 (en) 2003-12-19 2009-03-10 Apple Inc. De-emphasis training on a point-to-point connection
US7237135B1 (en) * 2003-12-29 2007-06-26 Apple Inc. Cyclemaster synchronization in a distributed bridge
US7308517B1 (en) 2003-12-29 2007-12-11 Apple Inc. Gap count analysis for a high speed serialized bus
US20050231358A1 (en) * 2004-04-19 2005-10-20 Company Steven L Search engine for singles with (GPS) position data
US20050262391A1 (en) * 2004-05-10 2005-11-24 Prashant Sethi I/O configuration messaging within a link-based computing system
US7552202B2 (en) * 2005-03-10 2009-06-23 International Business Machines Corporation System and method to uniquely identify identically configured branches in a distributed enterprise
US7370135B2 (en) * 2005-11-21 2008-05-06 Intel Corporation Band configuration agent for link based computing system
US8483108B2 (en) * 2006-07-24 2013-07-09 Apple Inc. Apparatus and methods for de-emphasis training on a point-to-point connection
US8745106B2 (en) * 2006-08-30 2014-06-03 Red Hat, Inc. Numeric identifier assignment in a networked computer environment
US7610429B2 (en) * 2007-01-30 2009-10-27 Hewlett-Packard Development Company, L.P. Method and system for determining device criticality in a computer configuration
US7979449B2 (en) * 2007-08-07 2011-07-12 Atasa Ltd. System and method for representing, organizing, storing and retrieving information
JP4497184B2 (ja) * 2007-09-13 2010-07-07 ソニー株式会社 集積装置およびそのレイアウト方法、並びにプログラム
EP2263166B1 (en) * 2008-03-24 2020-02-19 D-Wave Systems Inc. Systems, devices, and methods for analog processing
US9391845B2 (en) * 2014-09-24 2016-07-12 Intel Corporation System, method and apparatus for improving the performance of collective operations in high performance computing
JP6418043B2 (ja) 2015-04-08 2018-11-07 株式会社デンソー スイッチングハブ及び通信ネットワーク
US9838571B2 (en) 2015-04-10 2017-12-05 Gvbb Holdings S.A.R.L. Precision timing for broadcast network
US10691192B2 (en) * 2017-06-29 2020-06-23 Itron Global Sarl Proxy mechanism for communications to establish routes in networks

Family Cites Families (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3693155A (en) * 1971-03-23 1972-09-19 Nat Telecommunications System Communication system
US4443866A (en) * 1975-08-27 1984-04-17 Corning Glass Works Automatic device selection circuit
US4344134A (en) * 1980-06-30 1982-08-10 Burroughs Corporation Partitionable parallel processor
US4360870A (en) * 1980-07-30 1982-11-23 International Business Machines Corporation Programmable I/O device identification
US4660169A (en) * 1983-07-05 1987-04-21 International Business Machines Corporation Access control to a shared resource in an asynchronous system
US4763329A (en) * 1986-02-10 1988-08-09 Techlan, Inc. Modular data routing system
US4860201A (en) * 1986-09-02 1989-08-22 The Trustees Of Columbia University In The City Of New York Binary tree parallel processor
US4845744A (en) * 1986-10-16 1989-07-04 American Telephone And Telegraph Company, At&T Bell Laboratories Method of overlaying virtual tree networks onto a message passing parallel processing network
US4740954A (en) * 1986-12-31 1988-04-26 Bell Communications Research, Inc. Multicast routing algorithm
US4809362A (en) * 1987-03-13 1989-02-28 Center For Innovative Technology Fiber-optic star tree network
FR2649574B1 (fr) * 1989-07-04 1991-10-18 Rce Sa Reseau de communication entre equipements utilisateurs
US5179670A (en) * 1989-12-01 1993-01-12 Mips Computer Systems, Inc. Slot determination mechanism using pulse counting

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
高野 誠「マルチメディアＬＡＮにおける自動構成管理方法」、電子情報通信学会技術報告 ＩＮ９２−２８〜４３、１９９２−９−１７、Ｖｏｌ．９２ Ｎｏ．２１９、ｐ．３３−３８

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN100402572C (zh) * 2006-01-24 2008-07-16 浙江林学院 三聚氰胺和竹木酚液化物改性酚醛树脂生产方法

Also Published As

Publication number Publication date
DE69332778D1 (de) 2003-04-24
DE69332778T2 (de) 2004-02-05
EP1197870A2 (en) 2002-04-17
DE69334267D1 (de) 2009-04-23
EP0674789A1 (en) 1995-10-04
CA2698614A1 (en) 1994-07-07
CA2151368C (en) 2004-02-10
EP1197870A3 (en) 2006-04-19
EP0674789B1 (en) 2003-03-19
CA2503597C (en) 2010-06-29
KR950704746A (ko) 1995-11-20
JPH08505722A (ja) 1996-06-18
EP1197870B1 (en) 2009-03-11
HK1041734A1 (en) 2002-07-19
CA2408532A1 (en) 1994-07-07
US5394556A (en) 1995-02-28
WO1994015303A1 (en) 1994-07-07
KR100316208B1 (ko) 2002-06-20
HK1041734B (zh) 2009-11-20
CA2151368A1 (en) 1994-07-07
CA2698614C (en) 2011-05-17
CA2408532C (en) 2005-07-26
CA2503597A1 (en) 1994-07-07
AU5954094A (en) 1994-07-19

Similar Documents

Publication Publication Date Title
JP3243613B2 (ja) 非サイクル有向グラフに関わる固有アドレス割当て、ノード自己識別及びトポロジーマッピングの方法及び装置
JP3834562B2 (ja) 非サイクル有向グラフで接続された構成要素間の通信方法
US5784557A (en) Method and apparatus for transforming an arbitrary topology collection of nodes into an acyclic directed graph
WO1994015305A1 (en) Method and apparatus for transforming an arbitrary acyclic topology collection of nodes into an acyclic directed graph

Legal Events

Date Code Title Description
R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20071026

Year of fee payment: 6

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20081026

Year of fee payment: 7

S533 Written request for registration of change of name

Free format text: JAPANESE INTERMEDIATE CODE: R313533

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20081026

Year of fee payment: 7

R350 Written notification of registration of transfer

Free format text: JAPANESE INTERMEDIATE CODE: R350

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20081026

Year of fee payment: 7

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20091026

Year of fee payment: 8

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20091026

Year of fee payment: 8

S531 Written request for registration of change of domicile

Free format text: JAPANESE INTERMEDIATE CODE: R313531

R350 Written notification of registration of transfer

Free format text: JAPANESE INTERMEDIATE CODE: R350

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20091026

Year of fee payment: 8

RD02 Notification of acceptance of power of attorney

Free format text: JAPANESE INTERMEDIATE CODE: R3D02

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20091026

Year of fee payment: 8

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20101026

Year of fee payment: 9

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20111026

Year of fee payment: 10

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20121026

Year of fee payment: 11

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20131026

Year of fee payment: 12

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

EXPY Cancellation because of completion of term