Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-09-29
2004-01-06
Chin, Wellington (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S389000
Reexamination Certificate
active
06674720
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to networked computer systems, and more particularly to a nonlinear system and method of aging packets traveling through a packet switching network.
BACKGROUND INFORMATION
Communication latency is a common concern in packet switching networks. Steps are taken to reduce the average latency for network traffic. At the same time, care must be taken to limit the maximum latency faced by a packet in the network. Age-based arbitration has been used to limit the length of time that packets are in transit within the network. In one such approach, each header packet includes an age field. The contents of the age field are increased by a constant at each transfer point in the system (e.g., each node or each router).
In one such approach, such as was used in the Origin 2000 system manufactured by Silicon Graphics Inc. of Mountain View, Calif., a packet is assigned an age value of zero when it gets injected into the network. At predetermined intervals, the age field is incremented by a constant. (In the Origin 2000, each router had a register that could be programmed with a constant aging increment (e.g., 100 clocks or 1000 clocks).) Preferential routing is given to the oldest packets, so that they propagate to their destination.
Such an approach works well for most instances. Packets in the network get injected into the network with a value of zero and increment in a consistent fashion as they pass through the network. As the network size increases and as the number of packets active in the network increase, however, such an approach tends to result in large numbers of packets with similar ages. What is needed is a system and method of age-based arbitration which enables one to differentiate more easily between packets within the network.
SUMMARY OF THE INVENTION
According to one aspect of the present invention, in a multiprocessor system having a plurality of nodes connected to a network, wherein communication between the plurality of nodes is in the form of packets, a system and method of aging packets is described. A packet having an age value is built and transmitted through the network. The age value is increased at predetermined intervals, wherein increasing includes determining a current age of the packet and changing the interval as a function of the current age.
According to another aspect of the present invention, in a multiprocessor system having a plurality of nodes connected by a network, wherein communication between the plurality of nodes is in the form of packets routed through a router, wherein the router includes a plurality of ports, a system and method of routing packets through the plurality of ports. Packets are built. Each packet has an age value and the age value is set to a constant. A value is added to the age value at predetermined intervals, wherein adding a value to the aging value includes determining a current age of the packet and changing the interval as a function of the current age. Packets are queued in the router and are transmitted according to a priority which examines the age value of queued packets to determine an oldest packet and routes the oldest packet to a port.
According to yet another aspect of the present invention, in a multiprocessor system having a plurality of nodes connected by a network, wherein communication between the plurality of nodes is in the form of packets routed through a router, wherein the router includes a plurality of input ports and a plurality of output ports, a system and method of routing packets through the plurality of output ports is described. Packets are received at each of the plurality of input ports. Each packet has an age value and a value is added to the age value at predetermined intervals. One or more of the packets is transmitted to output ports, wherein transmitting includes examining the age value of packets to determine an oldest packet and routing the oldest packet through one of the plurality of output ports. In determining the packet to be transferred, if a packet arriving through a first input port and a packet arriving through a second input port have equivalent ages, the packet to be routed is determined as a function of the port through which it arrived, wherein determining the packet to be routed as a function of the port through which it arrived includes applying a rotating priority to each port.
According to yet another aspect of the present invention, in a multiprocessor system having a plurality of nodes connected by a network, wherein the plurality of nodes includes a first node and a second node, wherein each node includes a response age register and a plurality of ports connected to a network, wherein the response age register includes a response age value, wherein communication between the plurality of nodes is in the form of packets, wherein each packet has a source node field, a destination node field and an age field and wherein each age field contains an aging value, a system and method of routing packets through the plurality of ports is described. A request packet is generated at the first node, wherein generating includes loading a first node identifier representative of the first node in the source node field; loading a second node identifier representative of the second node in the destination node field and setting the aging value to a constant. A value is added to the aging value at predetermined intervals. The request packet is routed through a plurality of nodes to the second node, wherein routing includes resolving port conflicts through age-based arbitration. A response packet is generated, wherein generating includes loading a first node identifier representative of the first node in the destination node field; loading a second node identifier representative of the second node in the source node field and setting the aging value to the response age value stored in the second node's response age register.
REFERENCES:
patent: RE28577 (1975-10-01), Schmidt
patent: 4330858 (1982-05-01), Choquet
patent: 4630259 (1986-12-01), Larson et al.
patent: 4771391 (1988-09-01), Blasbalg
patent: 4811214 (1989-03-01), Nosenchuck et al.
patent: 4868818 (1989-09-01), Madan et al.
patent: 4933933 (1990-06-01), Dally et al.
patent: 4974143 (1990-11-01), Yamada
patent: 4980822 (1990-12-01), Brantley et al.
patent: 4987537 (1991-01-01), Kawata
patent: 5008882 (1991-04-01), Peterson et al.
patent: 5031211 (1991-07-01), Nagai et al.
patent: 5036459 (1991-07-01), Den Haan et al.
patent: 5081623 (1992-01-01), Ainscow
patent: 5083265 (1992-01-01), Valiant
patent: 5105424 (1992-04-01), Flaig et al.
patent: 5117350 (1992-05-01), Parrish et al.
patent: 5134690 (1992-07-01), Samatham
patent: 5157692 (1992-10-01), Horie et al.
patent: 5161156 (1992-11-01), Baum et al.
patent: 5170482 (1992-12-01), Shu et al.
patent: 5175733 (1992-12-01), Nugent
patent: 5195100 (1993-03-01), Katz et al.
patent: 5197130 (1993-03-01), Chen et al.
patent: 5201044 (1993-04-01), Frey, Jr. et al.
patent: 5210705 (1993-05-01), Chauvel et al.
patent: 5218601 (1993-06-01), Chujo et al.
patent: 5218676 (1993-06-01), Ben-ayed et al.
patent: 5233618 (1993-08-01), Glider et al.
patent: 5239545 (1993-08-01), Buchholz
patent: 5260935 (1993-11-01), Turner
patent: 5274799 (1993-12-01), Brant et al.
patent: 5276899 (1994-01-01), Neches
patent: 5280474 (1994-01-01), Nickolls et al.
patent: 5297137 (1994-03-01), Ofek et al.
patent: 5303244 (1994-04-01), Watson
patent: 5313628 (1994-05-01), Mendelsohn et al.
patent: 5313645 (1994-05-01), Rolfe
patent: 5331631 (1994-07-01), Teraslinna
patent: 5333279 (1994-07-01), Dunning
patent: 5341504 (1994-08-01), Mori et al.
patent: 5345565 (1994-09-01), Jibbe et al.
patent: 5347450 (1994-09-01), Nugent
patent: 5353283 (1994-10-01), Tsuchiya
patent: 5361334 (1994-11-01), Cawley
patent: 5365228 (1994-11-01), Childs et al.
patent: 5367692 (1994-11-01), Edelman
patent: 5383191 (1995-01-01), Hobgood et al.
patent: 5390164 (1995-02-01), Kremer
patent: 5394528 (1995-02-01), Kobayashi et al.
patent: 5402428 (1995-03-01), Kakuta et al.
patent: 543
Passint Randal S.
Stremcha Timothy
Thorson Gregory M.
Chin Wellington
Pham Brenda
Schwegman Lundberg Woessner & Kluth P.A.
Silicon Graphics Inc.
LandOfFree
Age-based network arbitration system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Age-based network arbitration system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Age-based network arbitration system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3256942