公开(公告)号：US07152113B2

公开(公告)日：2006-12-19

申请号：US10027886

申请日：2001-10-19

申请人： John V. Reynders ,  Radia J. Perlman ,  Guy L. Steele, Jr. ,  Dah Ming Chiu ,  Miriam C. Kadansky ,  Murat Yuksel

发明人： John V. Reynders ,  Radia J. Perlman ,  Guy L. Steele, Jr. ,  Dah Ming Chiu ,  Miriam C. Kadansky ,  Murat Yuksel

IPC分类号： G06F15/16 ,  G06F15/173

CPC分类号： H04L45/54 ,  H04L45/02 ,  H04L45/18 ,  H04L45/44

摘要： A system and method for adding routing information for a node to a routing table, which efficiently makes necessary changes to the routing table to support routing to and from the node, while maintaining the deadlock-free quality of the paths described by the routing table. The routing table is generated by storing routing information in the routing table that reflects and describes a deadlock-free set of paths through a network of nodes. A row of entries is added to the routing table describing how to forward data units from the node. A column of entries is added to the routing table describing how to forward data units addressed to the node. The forwarding information within each entry added to the routing table maintains the deadlock-free quality of the set of paths represented by the forwarding table.

公开(公告)号：US07096251B2

公开(公告)日：2006-08-22

申请号：US10209077

申请日：2002-07-31

申请人： Dah Ming Chiu ,  Miriam C. Kadansky ,  Radia J. Perlman ,  Murat Yuksel

发明人： Dah Ming Chiu ,  Miriam C. Kadansky ,  Radia J. Perlman ,  Murat Yuksel

IPC分类号： G06F15/16

CPC分类号： H04L45/26 ,  H04L45/02 ,  H04L45/18 ,  H04L45/40 ,  H04L45/44

摘要： A distributed system and method generate “layered routes” that reflect a layered representation of a network, which representation provides deadlock-free routes. The layered representation consists of an ordered set of layers, where each layer is a deadlock-free sub-topology of the network. In determining routes, the links used in each route are constrained to be taken from layers of non-decreasing order as the route extends from source to destination. A device that determines a better or equal cost path to a destination node with respect to its current path to that node sends a route information message to its neighbor devices. The receiver of a route information message may then accept the message and begin using the new path described by the message, or reject the message without using the new path.

摘要翻译： 分布式系统和方法生成反映网络的分层表示的“分层路由”，该表示提供无死锁路由。 分层表示由有序的一组层组成，其中每个层是网络的无死锁子拓扑。 在确定路由时，当路由从源到目的地延伸时，每个路由中使用的链路被限制为从非递减顺序的层获取。 确定目的地节点相对于其到该节点的当前路径的更好或相等的成本路径的设备向其相邻设备发送路由信息消息。 然后，路由信息消息的接收者可接受该消息并开始使用该消息描述的新路径，或拒绝该消息而不使用该新路径。

公开(公告)号：US06757843B1

公开(公告)日：2004-06-29

申请号：US09698490

申请日：2000-10-26

申请人： Joseph Wesley ,  Stephen A. Hurst ,  Miriam C. Kadansky ,  Stephen R. Hanna ,  Philip M. Rosenzweig ,  Dah Ming Chiu ,  Radia J. Perlman

发明人： Joseph Wesley ,  Stephen A. Hurst ,  Miriam C. Kadansky ,  Stephen R. Hanna ,  Philip M. Rosenzweig ,  Dah Ming Chiu ,  Radia J. Perlman

IPC分类号： G06F1100

CPC分类号： H04L45/46 ,  H04L12/185 ,  H04L12/1863 ,  H04L45/04 ,  H04L45/16

摘要： An embodiment consistent with the present invention includes a method and apparatus for forming a multicast repair tree. The methods perform by a data processor and comprises the steps of determining, for each of a plurality of potential heads in a multicast group, a ranking value associated with the potential head; advertising, by the potential heads to a plurality of potential receivers; prioritizing, by a potential receiver, the ranking values from the potential heads; and binding, by a potential receiver to the head having the highest ranking value, thereby forming a group of which the potential receiver,is a member and the potential head is the head. The ranking values may include “able”, “unable”, “willing”, and “reluctant.” The ranking value of a potential head determines in accordance with a static or a dynamic configuration. Ranking values determine dynamically based on ranges of system resource levels such as memory and available processor resources.

摘要翻译： 与本发明一致的实施例包括用于形成多播修复树的方法和装置。 所述方法由数据处理器执行并且包括以下步骤：针对多播组中的多个潜在头中的每一者，确定与所述潜在头相关联的排序值; 广告，潜在的头到多个潜在的接收者; 由潜在的接收者优先考虑来自潜在负责人的排名值; 并且由潜在的接收器绑定到具有最高排名的头部，由此形成潜在的接收者是一个成员并且潜在的头部是头部的一组。 排名值可能包括“能力”，“不能”，“愿意”和“不情愿”。 潜在头的排名值根据静态或动态配置来确定。 排名值基于诸如存储器和可用处理器资源的系统资源级别的范围动态地确定。

公开(公告)号：US06275859B1

公开(公告)日：2001-08-14

申请号：US09429192

申请日：1999-10-28

申请人： Joseph S. Wesley ,  Dah Ming Chiu ,  Miriam C. Kadansky ,  Stephen A. Hurst ,  Radia J. Perlman ,  Joseph E. Provino ,  Philip M. Rosenzweig

发明人： Joseph S. Wesley ,  Dah Ming Chiu ,  Miriam C. Kadansky ,  Stephen A. Hurst ,  Radia J. Perlman ,  Joseph E. Provino ,  Philip M. Rosenzweig

IPC分类号： G06F1516

CPC分类号： H04L12/1877 ,  G06F15/16 ,  H04L9/321 ,  H04L9/3263 ,  H04L12/185 ,  H04L63/0823 ,  H04L63/104

摘要： To authenticate and authorize prospective members in a reliable multicast data distribution setup, the prospective members contact a central authority to obtain a “participation certificate” for the multicast session. The central authority authenticates each node and issues a digitally signed certificate to the node. Each certificate contains information specifying the manner in which the respective node is authorized to participate in the multicast session in addition to the respective node's public key. The nodes exchange their participation certificates with each other during session-establishment dialog to prove their identities and their authorization to participate. Each node verifies the rights of other nodes based on authorization information contained in the participation certificate received from the other node. Thus, a node is allowed to participate as a repair node only if it presents a participation certificate authorizing it to do so. Disruption in network operation is avoided by reducing the ability of malicious nodes to consume resources to the detriment of legitimate session members.

摘要翻译： 为了对可靠的组播数据分发设置中的潜在成员进行身份验证和授权，预期成员联系中央机构获取组播会话的“参与证书”。 中央机构对每个节点进行身份验证，并向节点发出数字签名的证书。 除了相应的节点的公共密钥之外，每个证书包含指定相应节点被授权参与多播会话的方式的信息。 节点在会话建立对话期间将他们的参与证书交给对方，以证明其身份和授权参与。 每个节点根据从其他节点接收到的参与证书中包含的授权信息来验证其他节点的权限。 因此，只有当一个节点呈现授权它的参与证书才可以作为修复节点参与。 通过降低恶意节点消耗资源的能力来避免网络运行中断，从而损害合法的会话成员。

公开(公告)号：US06658004B1

公开(公告)日：2003-12-02

申请号：US09473402

申请日：1999-12-28

申请人： Miriam C. Kadansky ,  Dah Ming Chiu ,  Stephen R. Hanna ,  Stephen A. Hurst ,  Radia J. Perlman ,  Joseph S. Wesley

发明人： Miriam C. Kadansky ,  Dah Ming Chiu ,  Stephen R. Hanna ,  Stephen A. Hurst ,  Radia J. Perlman ,  Joseph S. Wesley

IPC分类号： H04L1228

CPC分类号： H04L12/1827 ,  H04L47/10 ,  H04L47/31 ,  H04L67/104 ,  H04L67/1063 ,  H04L67/1074 ,  H04L69/329

摘要： A method and apparatus for identifying a data message that is eligible for discard. A beacon node periodically transmits a beacon message to a plurality of client nodes communicatively coupled via a network. Each beacon message includes a beacon sequence number and preferably, the beacon sequence numbers are authenticated by the beacon, node. The client nodes, upon receipt of the beacon messages, verify the authenticity of the respective received beacon sequence numbers and generate a local sequence number derived from the received beacon sequence number. When one client in the session has data to transmit to another client in the session, the sending client assembles a data message and inserts its local sequence number in the data message prior to transmission of the data message to the other client nodes in the session. The client nodes receiving the data message discard the data message if their respective local sequence number at the time of receipt of the data message exceeds the local sequence number inserted in the data message by a predetermined value. In one embodiment, the beacon node generates sequence numbers at a periodic interval P but only transmits 1 out of every m beacon sequence numbers to the client nodes in the session. The client nodes each set a local sequence counter equal to the beacon sequence number upon receipt of the beacon message and thereafter, increment the local sequence counter periodically at interval P. The local sequence counter value is employed as the local sequence number in each client node.

摘要翻译： 一种用于识别符合丢弃资格的数据消息的方法和装置。 信标节点周期性地向经由网络通信耦合的多个客户端节点发送信标消息。 每个信标消息包括信标序列号，并且优选地，信标序列号由信标节点认证。 客户端节点在接收到信标消息后，验证相应接收到的信标序列号的真实性，并生成从接收到的信标序列号导出的本地序列号。 当会话中的一个客户端具有要在会话中传送给另一个客户端的数据时，发送客户端汇集一个数据消息，并将数据消息中的本地序列号插入到数据消息中，并传送到该会话中的其他客户机节点。 接收数据消息的客户节点如果在接收数据消息时其各自的本地序列号超过插入数据消息中的本地序列号预定值，则丢弃数据消息。 在一个实施例中，信标节点以周期性间隔P生成序列号，但是仅在每个m个信标序列号中发送1个到会话中的客户端节点。 客户端节点每接收到信标消息时都设置等于信标序列号的本地序列计数器，此后，以间隔P周期性地增加本地序列计数器。本地序列计数器值被用作每个客户端节点中的本地序列号 。

公开(公告)号：US06507562B1

公开(公告)日：2003-01-14

申请号：US09336660

申请日：1999-06-18

申请人： Miriam C. Kadansky ,  Dah Ming Chiu ,  Stephen R. Hanna ,  Stephen A. Hurst ,  Joseph S. Wesley ,  Philip M. Rosenzweig ,  Radia J. Perlman

发明人： Miriam C. Kadansky ,  Dah Ming Chiu ,  Stephen R. Hanna ,  Stephen A. Hurst ,  Joseph S. Wesley ,  Philip M. Rosenzweig ,  Radia J. Perlman

IPC分类号： G06F1100

CPC分类号： H04L12/1877 ,  H04L12/185 ,  H04L12/1868

摘要： Receiver stations located close together in a computer network dynamically form a multicast repair tree by a plurality of receiver stations choosing a repair head station from among the closely located receiver stations. A receiver station calculates its distance from a repair head station by subtracting the decremented TTL value read from the IP header from the initial value of the TTL parameter carried in field TTL SCOPE of HELLO messages, transmitted by repair head stations. Using a criteria that a closer repair head station is a more optimum repair head station, receiver stations listen to each received HELLO message, calculate the distance to the repair head station, and reaffiliate with the closest repair head station.

摘要翻译： 位于计算机网络中的接收站由多个接收站动态地形成多播修复树，所述多个接收站从位于接近站的接收站中选择修复头站。 接收站通过从修复头站发送的HELLO消息的字段TTL SCOPE中携带的TTL参数的初始值中减去从IP报头读取的递减的TTL值来计算其与修复站的距离。 使用更接近的修理头站是更为优化的修复头站的标准，接收站收听每个接收到的HELLO消息，计算到维修站的距离，并且与最接近的维修站相连。

公开(公告)号：US06526022B1

公开(公告)日：2003-02-25

申请号：US09336670

申请日：1999-06-18

申请人： Dah Ming Chiu ,  Miriam C. Kadansky ,  Stephen R. Hanna ,  Stephen A. Hurst ,  Joseph S. Wesley ,  Philip M. Rosenzweig ,  Radia J. Perlman

发明人： Dah Ming Chiu ,  Miriam C. Kadansky ,  Stephen R. Hanna ,  Stephen A. Hurst ,  Joseph S. Wesley ,  Philip M. Rosenzweig ,  Radia J. Perlman

IPC分类号： G01R3108

CPC分类号： H04L12/1868 ,  H04L1/0002 ,  H04L1/1887 ,  H04L12/185 ,  H04L47/10 ,  H04L47/15 ,  H04L47/263 ,  H04L47/27 ,  H04L2001/0092

摘要： A method of detecting congestion in a computer network uses a receiving station which determines a first number of messages missing in a first acknowledgment window. The station then determines a second number of messages missing in a subsequent acknowledgement window. The station then measures congestion on the network in response to an increase in the number of missing messages as indicated by the first number of missing messages in the first acknowledgement window and the second number of missing messages in the second acknowledgement window.

摘要翻译： 一种在计算机网络中检测拥塞的方法使用确定在第一确认窗口中丢失的第一数量的消息的接收站。 然后，站确定后续确认窗口中丢失的第二个消息数。 该站然后响应于第一确认窗口中的第一数量的丢失消息和第二确认窗口中的第二数量的丢失消息所指示的丢失消息的数量的增加来测量网络上的拥塞。

公开(公告)号：US06505253B1

公开(公告)日：2003-01-07

申请号：US09336659

申请日：1999-06-18

申请人： Dah Ming Chiu ,  Miriam C. Kadansky ,  Stephen R. Hanna ,  Stephen A. Hurst ,  Joseph S. Wesley ,  Philip M. Rosenzweig ,  Radia J. Perlman

发明人： Dah Ming Chiu ,  Miriam C. Kadansky ,  Stephen R. Hanna ,  Stephen A. Hurst ,  Joseph S. Wesley ,  Philip M. Rosenzweig ,  Radia J. Perlman

IPC分类号： G06F1300

CPC分类号： H04L47/263 ,  H04L1/1832 ,  H04L12/185 ,  H04L12/1868 ,  H04L47/10 ,  H04L47/15 ,  H04L47/27 ,  H04L2001/0093

摘要： A multicast repair tree is established, the repair tree having one sender station and a plurality of repair head stations. A repair head station has an affiliated group of member stations. A repair head station retransmits a lost message to its affiliated group of member stations upon receipt from a member station of a NACK message indicating that the selected message was not received. Acknowledgment windows (ACK windows) are established in a member station for transmission of ACK or NACK message by the member station. A number of messages transmitted by the sender station during a transmission window is established. Also a same size of ACK window is established in the receiving stations, with a slot in the ACK window corresponding to each message transmitted by the repair head station. Each receiving station is assigned a slot in the ACK window during which time that receiving station transmits its ACK or NACK messages. Thus the ACK window slots assigned to receiver stations for transmission of ACK/NACK windows are staggered so that different receiver stations transmit their ACKNACK messages at different times. The slot for a particular receiver station to use may be assigned by a random process.

摘要翻译： 建立组播修复树，修复树具有一个发送站和多个修复头站。 修理站具有附属的成员站组。 修复头站在从成员站接收到表示所选择的消息未被接收的NACK消息的情况下向其附属成员组重发丢失的消息。 成员站建立确认窗口（ACK窗口），用于成员站发送ACK或NACK消息。 在发送窗口期间由发送站发送的多个消息被建立。 在接收站中建立相同大小的ACK窗口，ACK窗口中的时隙对应于由修复站发送的每个消息。 每个接收站在ACK窗口中被分配一个时隙，在该时间内接收站发送其ACK或NACK消息。 因此，分配给用于发送ACK / NACK窗口的接收机站的ACK窗口时隙交错，使得不同的接收机站在不同时间发送它们的ACKNACK消息。 用于要使用的特定接收机站的时隙可以通过随机过程来分配。

公开(公告)号：US06185698B2

公开(公告)日：2001-02-06

申请号：US09063498

申请日：1998-04-20

申请人： Joseph Wesley ,  Stephen A. Hurst ,  Miriam C. Kadansky ,  Stephen R. Hanna ,  Philip M. Rosenzweig ,  Dah Ming Chiu ,  Radia J. Perlman

发明人： Joseph Wesley ,  Stephen A. Hurst ,  Miriam C. Kadansky ,  Stephen R. Hanna ,  Philip M. Rosenzweig ,  Dah Ming Chiu ,  Radia J. Perlman

IPC分类号： G06F1100

CPC分类号： H04L45/46 ,  H04L12/185 ,  H04L12/1863 ,  H04L45/04 ,  H04L45/16

摘要： An embodiment consistent with the present invention includes a method and apparatus for forming a multicast repair tree. The method may be performed by a data processor and comprises the steps of determining, for each of a plurality of potential heads in a multicast group, a ranking value associated with the potential head; advertising, by the potential heads to a plurality of potential receivers; prioritizing, by a potential receiver, the ranking values from the potential heads; and binding, by a potential receiver to the head having the highest ranking value, thereby forming a group of which the potential receiver is a member and the potential head is the head. The head may also be the sender. There may be a plurality of heads. The ranking values may include “able”, “unable”, “willing”, and “reluctant.” The ranking value of a potential head may be determined in accordance with a static or a dynamic configuration. Ranking values may be determined dynamically based on ranges of system resource levels such as memory and available processor resources.

摘要翻译： 与本发明一致的实施例包括用于形成多播修复树的方法和装置。 该方法可以由数据处理器执行，并且包括以下步骤：针对多播组中的多个潜在头中的每一者，确定与潜在头相关联的排序值; 广告，潜在的头到多个潜在的接收者; 由潜在的接收者优先考虑来自潜在负责人的排名值; 并且通过潜在的接收器将具有最高排序值的头绑定，从而形成潜在的接收器是一个成员的组，并且潜在头是头部。 头也可能是发件人。 可以有多个头。 排名值可能包括“能力”，“不能”，“愿意”和“不情愿”。 可以根据静态或动态配置来确定潜在头的排名值。 可以基于诸如存储器和可用处理器资源的系统资源级别的范围来动态地确定排名值。

公开(公告)号：US6104695A

公开(公告)日：2000-08-15

申请号：US52201

申请日：1998-03-31

申请人： Joseph S. Wesley ,  Radia J. Perlman ,  Stephen A. Hurst ,  Stephen R. Hanna ,  Miriam C. Kadansky ,  Philip M. Rosenzweig

发明人： Joseph S. Wesley ,  Radia J. Perlman ,  Stephen A. Hurst ,  Stephen R. Hanna ,  Miriam C. Kadansky ,  Philip M. Rosenzweig

IPC分类号： H04L12/18 ,  H04L12/701 ,  H04L12/761 ,  G01R31/08 ,  H04H1/00 ,  H04L12/66

CPC分类号： H04L45/00 ,  H04L12/1868 ,  H04L45/16

摘要： Determination of a Time To Live ("TTL") hop count for repair data units transmitted from a repair head to a standard destination device in a communications network is facilitated for multicast transmission. The repair head destination device monitors the path between the repair head destination device and the standard destination devices by exchanging messages with the respective standard destination devices. The repair head transmits control messages to each destination device including a dispatched TTL value and an Internet Protocol ("IP") TTL value. If the control message fails to reach one of the standard destination devices, that standard destination device transmits a transmission failure indication to the repair head destination device. In response to the transmission failure indication the TTL value employed for the control message is increased. Following receipt of the control message, the standard destination device calculates the TTL value required to transmit a data unit from the repair head to the standard destination device by subtracting the IP TTL value from the dispatched TTL value. If the calculated TTL difference value is non-zero then an excess-TTL indication is transmitted from the standard destination device to the repair head destination device.

摘要翻译： 确定通信网络中从维修头传送到标准目的地设备的修复数据单元的生存时间（“TTL”）跳数有利于组播传输。 修理头目的设备通过与相应的标准目的地设备交换消息来监视修复头目的地设备和标准目的地设备之间的路径。 修复头向每个目的地设备发送控制消息，包括调度的TTL值和互联网协议（“IP”）TTL值。 如果控制消息未能到达标准目的地设备之一，则该标准目的地设备向修复头目的设备发送传输失败指示。 响应于传输失败指示，增加了用于控制消息的TTL值。 在接收到控制消息之后，标准目的地设备通过从调度的TTL值减去IP TTL值来计算从修复头向标准目的地设备发送数据单元所需的TTL值。 如果计算的TTL差值为非零，则从标准目的地设备向维修头目的地设备发送过量TTL指示。