Method and apparatus for avoiding starvation in computer network

• US 6,799,219 B1
• Filed: 08/31/2000
• Issued: 09/28/2004
• Est. Priority Date: 08/31/2000
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Miyoshi, Takashi, Horie, Takeshi, Larson, Jeffrey D., Sugahara, Hirohide
• Primary Examiner(s): Follansbee, John
• Assistant Examiner(s): Chang, Jungwon
• Application Number:
  US09/653,154
• Time in Patent Office: 1,489 Days
• Field of Search: 710/113, 710/306, 711/163, 711/150, 711/206, 709/250, 709/232, 370/231
• US Class Current: 709/232
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/745 Reaction in network
• CPC Class Codes: H04L 47/821 Prioritising resource allocation or reservation requests
• CPC Class Codes: H04L 47/826 Involving periods of time

Abstract

A method and apparatus for avoiding starvation at an initiator node in a computer network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from the target node. The method includes: when a request is received from the initiator node during a period that the target node is unable to provide service, returning a reject reply by attaching thereto reject time information that matches the period; when the target node is in a state capable of providing service, preferentially accepting a retry request carrying older reject time information; and when the target node is in the state capable of providing service, returning a reject reply by attaching thereto new reject time information in response to any first request received before retry requests arising from previously rejected requests are all accepted.

Claims

1. A method for avoiding starvation at an initiator node in a computer network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from said target node, said method comprising the operations of:

when a first request is received from said initiator node during a period that said target node is unable to provide service, returning a first reject reply by attaching thereto reject time information that matches said period;

when said target node is in a state capable of providing service, preferentially accepting a retry request carrying older reject time information; and

at said target node staying in the state capable of providing service, when the retry request is received, processing said retry request while when a second request is received, returning a second reject reply by attaching thereto new reject time information.

2. A method for avoiding starvation at an initiator node in a compute network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from said target node, said method comprising the operations of:

(a) when a first request is received at said target node when said target node is in a state capable of providing service, accepting said first request;

(b) when a first request is received at said target node after said target node has moved to a state incapable of providing service, returning a reject reply in response to said first request by attaching thereto reject time information comprising at least one bit;

(c) when a retry request is received at said target node after said target node is restored to the state capable of providing service, accepting said retry request depending on the reject time information attached to said retry request; and

(d) at said target node staying in the state capable of providing service, when a retry request is received, processing said retry request in the same manner as in said operation (c), while when a first request is received, returning a reject reply by attaching thereto reject time information.

3. A method for avoiding starvation at an initiator node in a computer network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from said target node, said method comprising the operations of:

(a) at said target node, initializing to 0 all of a first collect epoch (CE) parameter comprising at least one bit, a second service epoch (SE) parameter comprising the same number of bits as the number of bits of said first parameter, a third collect counter (CC) parameter comprising the number of bits as determined by the number of said plurality of initiator nodes, and a fourth service counter (SC) parameter comprising the same number of bits as the number of bits of said third parameter;

(b) at said initiator node, sending a first request to said target node;

(c) when said first request is received at said target node, if CE=SE and SC=0 and if said target node is in a state capable of providing service, accepting said first request;

(d) when said first request is received at said target node, if CE=SE and SC>

0 or if CE=SE and said target node is in a state incapable of providing service, incrementing said CE, setting said CC to 1, and returning a reject reply by attaching thereto the value of said CE in response to said first request;

(e) when said first request is received at said target node, if CE≠

SE, incrementing said CC and returning a reject reply by attaching thereto the value of said CE;

(f) at said initiator node that received said reject reply, sending a retry request to said target node by attaching thereto a fifth parameter RE whose value is equal to the value of said CE attached to said reject reply;

(g) when said retry request is received at said target node, if CE=SE and SC0 and if said target node is in the state capable of providing service, accepting said retry request;

(h) when said retry request is received at said target node, if RE=SE+1 and SC=0 and if said target node is in the state capable of providing service, incrementing said SE, setting said SC to CC-1, and accepting said retry request;

(i) when said retry request is received at said target node, if RE=SE and SC>

0 and if said target node is in the state capable of providing service, decrementing said SC and accepting said retry request; and

(j) when said retry request is received at said target node, if any of execution conditions in said operations (g), (i), and (j) is not satisfied, returning a reject reply by attaching thereto the value of said RE in response to said retry request.

4. A method carried out at a target node for avoiding starvation at an initiator node in a computer network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from said target node, said method comprising the operations of:

(a) initializing to 0 all of a first collect epoch (CE) parameter comprising at least one bit, a second service epoch (SE) parameter comprising the same number of bits as the number of bits of said first parameter, a third collect counter (CC) parameter comprising the number of bits as determined by the number of said plurality of initiator nodes, and a fourth service counter (SC) parameter comprising the same number of bits as the number of bits of said third parameter;

(b) when a first request is received, if CE=SE and SC=0 and if said target node is in a state capable of providing service, accepting said first request;

(c) when a first request is received, if CE=SE and SC>

0 or if CE=SE and said target node is in a state incapable of providing service, incrementing said CE, setting said CC to 1, and returning a reject reply by attaching thereto the value of said CE in response to said first request;

(d) when a first request is received, if CE≠

SE, incrementing said CC and returning a reject reply by attaching thereto the value of said CE;

(e) when a retry request is received, if CE=SE and SC=0 and if said target node is in the state capable of providing service, accepting said retry request;

(f) when a retry request is received, if RE=SE+1 and SC=0 and if said target node is in the state capable of providing service, incrementing said SE, setting said SC to CC-1, and accepting said retry request;

(g) when a retry request is received, if RE=SE and SC>

0 and if said target node is in the state capable of providing service, decrementing said SC and accepting said retry request; and

(h) when a retry request is received, if any of execution conditions in said operations (e), (f), and (g) is not satisfied, returning a reject reply by attaching thereto the value of said RE in response to said retry request.

5. A method carried out at an initiator node for avoiding starvation at said initiator node in a computer network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from said target node, said method comprising the operations of:

(a) sending a first request to said target node during a period that said target node is unable to provide service; and

(b) when a reject reply is received from the target node in response to said first request, sending a retry request by attaching thereto a parameter whose value is equal to the value of a parameter of reject time information attached to said reject reply.

6. An apparatus for avoiding starvation at an initiator node in a computer network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from said target node, said apparatus comprising:

means for, when a first request is received from said initiator node during a period that said target node is unable to provide service, returning a first reject reply by attaching thereto reject time information that matches said period;

means for, when said target node is in a state capable of providing service, preferentially accepting a retry request carrying older reject time information; and

means for, when said target node staying in the state capable of providing service, when the retry request is received, processing said retry request while when a second request is received, returning a reject reply by attaching thereto new reject time information.

7. An apparatus for avoiding starvation at an initiator node in a computer network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from said target node, said apparatus comprising:

first means for, when a first request is received at said target node when said target node is in a state capable of providing service, accepting said first request;

second means for, when a first request is received at said target node after said target node has moved to a state incapable of providing service, returning a reject reply in response to said first request by attaching thereto reject time information comprising at least one bit;

third means for, when a retry request is received at said target node after said target node is restored to the state capable of providing service, accepting said retry request depending on the reject time information attached to said retry request; and

fourth means for, at said target node staying in the state capable of providing service, when a retry request is received, processing said retry request in the same manner as processed by said third means, while when a first request is received, returning a reject reply by attaching thereto reject time information.

8. (Previously Presented) An apparatus for avoiding starvation at an initiator node in a computer network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from said target node, said apparatus comprising:

first means for, at said target node, initializing to 0 all of a first collect epoch (CE) parameter comprising at least one bit, a second service epoch (SE) parameter comprising the same number of bits as the number of bits of said first parameter, a third collect counter (CC) parameter comprising the number of bits as determined by the number of said plurality of initiator nodes, and a fourth service counter (SC) parameter comprising the same number of bits as the number of bits of said third parameter;

second means for, at said initiator node, sending a first request to said target node;

third means for, when said first request is received at said target node, if CE=SE and SC=0 and if said target node is in a state capable of providing service, accepting said first request;

fourth means for, when said first request is received at said target node, if CE=SE and SC>

0 or if CE=SE and said target node is in a state incapable of providing service, incrementing said CE, setting said CC to 1, and returning a reject reply by attaching thereto the value of said CE in response to said first request;

fifth means for, when said first request is received at said target node, if CE≠

SE, incrementing said CC and returning a reject reply by attaching thereto the value of said CE;

sixth means for, at said initiator node that received said reject reply, sending a retry request to said target node by attaching thereto a fifth parameter RE whose value is equal to the value of said CE attached to said reject reply;

seventh means for, when said retry request is received at said target node, if CE=SE and SC=0 and if said target node is in the state capable of providing service, accepting said retry request;

eighth means for, when said retry request is received at said target node, if RE=SE+1 and SC=0 and if said target node is in the state capable of providing service, incrementing said SE, setting said SC to CC-1, and accepting said retry request;

ninth means for, when said retry request is received at said target node, if RE=SE and SC>

0 and if said target node is in the state capable of providing service, decrementing said SC and accepting said retry request; and

tenth means for, when said retry request is received at said target node, if any of operation conditions in said seventh, eighth, and ninth means is not satisfied, returning a reject reply by attaching thereto the value of said RE in response to said retry request.

9. An apparatus provided at a target node for avoiding starvation at an initiator node in a computer network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from said target node, said apparatus comprising:

first means for initializing to 0 all of a first collect epoch (CE) parameter comprising at least one bit, a second service epoch (SE) parameter comprising the same number of bits as the number of bits of said first parameter, a third collect counter (CC) parameter comprising the number of bits as determined by the number of said plurality of initiator nodes, and a fourth service counter (SC) parameter comprising the same number of bits as the number of bits of said third parameter;

second means for, when a first request is received, if CE=SE and SC=0 and if said target node is in a state capable of providing service, accepting said first request;

third means for, when a first request is received, if CE=SE and SC>

0 or if CE=SE and said target node is in a state incapable of providing service, incrementing said CE, setting said CC to 1, and returning a reject reply by attaching thereto the value of said CE in response to said first request;

fourth means for, when a first request is received, if CE≠

SE, incrementing said CC and returning a reject reply by attaching thereto the value of said CE;

fifth means for, when a retry request is received, if CE=SE and SC=0 and if said target node is in the state capable of providing service, accepting said retry request;

sixth means for, when a retry request is received, if RE=SE+1 and SC=0 and if said target node is in the state capable of providing service, incrementing said SE, setting said SC to CC-1, and accepting said retry request;

seventh means for, when a retry request is received, if RE=SE and SC>

0 and if said target node is in the state capable of providing service, decrementing said SC and accepting said retry request; and

eighth means for, when a retry request is received, if any of operation conditions in said fifth, sixth, and seventh means is not satisfied, returning a reject reply by attaching thereto the value of said RE in response to said retry request.

10. An apparatus provided at an initiator node for avoiding starvation at said initiator node in a computer network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from said target node, said apparatus comprising:

means for sending first request to said target node during a period that said target node is unable to provide service; and

means for, when a reject reply is received from the target node in response to said first request, sending a retry request by attaching thereto a parameter whose value is equal to the value of a parameter of reject time information attached to said reject reply.

11. A recording medium readable by an apparatus for avoiding starvation at an initiator node in a computer network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from said target node, said recording medium having stored thereon a program for implementing:

a facility for, when a first request is received from said initiator node during a period that said target node is unable to provide service, returning a first reject reply by attaching thereto reject time information that matches said period;

a facility for, when said target node is in a state capable of providing service, preferentially accepting a retry request carrying older reject time information; and

a facility for, at said target node staying in the state capable of providing service, when the retry request is received, processing said retry request while when a second request is received, returning a second reject reply by attaching thereto new reject time information.

12. A recording medium readable by an apparatus for avoiding starvation at an initiator node in a computer network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from said target node, said recording medium having stored thereon a program for implementing:

a first facility for, when a first request is received at said target node when said target node is in a state capable of providing service, accepting said first request;

a second facility for, when a first request is received at said target node after said target node has moved to a state incapable of providing service, returning a reject reply in response to said first request by attaching thereto reject time information comprising at least one bit;

a third facility for, when a retry request is received at said target node after said target node is restored to the state capable of providing service, accepting said retry request depending on the reject time information attached to said retry request; and

a fourth facility for, at said target node staying in the state capable of providing service, when a retry request is received, processing said retry request in the same manner as processed by said third facility, while when a first request is received, returning a reject reply by attaching thereto reject time information.

13. A recording medium readable by an apparatus for avoiding starvation at an initiator node in a computer network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from said target node, said recording medium having stored thereon a program for implementing:

a first facility for, at said target node, initializing to 0 all of a first collect epoch (CE) parameter comprising at least one bit, a second service epoch (SE) parameter comprising the same number of bits as the number of bits of said first parameter, a third collect counter (CC) parameter comprising the number of bits as determined by the number of said plurality of initiator nodes, and a fourth service counter (SC) parameter comprising the same number of bits as the number of bits of said third parameter;

a second facility for, at said initiator node, sending a first request to said target node;

a third facility for, when said first request is received at said target node, if CE=SE and SC=0 and if said target node is in a state capable of providing service, accepting said first request;

a fourth facility for, when said first request is received at said target node, if CE=SE and SC>

0 or if CE=SE and said target node is in a state incapable of providing service, incrementing said CE, setting said CC to 1, and returning a reject reply by attaching thereto the value of said CE in response to said first request;

a fifth facility for, when said first request is received at said target node, if CE≠

SE, incrementing said CC and returning a reject reply by attaching thereto the value of said CE;

a sixth facility for, at said initiator node that received said reject reply, sending a retry request to said target node by attaching thereto a fifth parameter RE whose value is equal to the value of said CE attached to said reject reply;

a seventh facility for, when said retry request is received at said target node, if CE=SE and SC=0 and if said target node is in the state capable of providing service, accepting said retry request;

an eighth facility for, when said retry request is received at said target node, if RE=SE+1 and SC=0 and if said target node is in the state capable of providing service, incrementing said SE, setting said SC to CC-1, and accepting said retry request;

a ninth facility for, when said retry request is received at said target node, if RE=SE and SC>

0 and if said target node is in the state capable of providing service, decrementing said SC and accepting said retry request; and

a tenth facility for, when said retry request is received at said target node, if any of operation conditions in said seventh, eighth, and ninth facilities is not satisfied, returning a reject reply by attaching thereto the value of said RE in response to said retry request.

14. A recording medium readable by a target node in a computer network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from said target node, said recording medium having stored thereon a starvation avoiding program for implementing:

a first facility for initializing to 0 all of a first collect epoch (CE) parameter comprising at least one bit, a second service epoch (SE) parameter comprising the same number of bits as the number of bits of said first parameter, a third collect counter (CC) parameter comprising the number of bits as determined by the number of said plurality of initiator nodes, and a fourth service counter (SC) parameter comprising the same number of bits as the number of bits of said third parameter;

a second facility for, when a first request is received, if CE=SE and SC=0 and if said target node is in a state capable of providing service, accepting said first request;

a third facility for, when a first request is received, if CE=SE and SC>

0 or if CE=SE and said target node is in a state incapable of providing service, incrementing said CE, setting said CC to 1, and returning a reject reply by attaching thereto the value of said CE in response to said first request;

a fourth facility for, when a first request is received, if CE≠

SE, incrementing said CC and returning a reject reply by attaching thereto the value of said CE;

a fifth facility for, when a retry request is received, if CE=SE and SC=0 and if said target node is in the state capable of providing service, accepting said retry request;

a sixth facility for, when a retry request is received, if RE=SE+1 and SC=0 and if said target node is in the state capable of providing service, incrementing said SE, setting said SC to CC-1, and accepting said retry request;

a seventh facility for, when a retry request is received, if RE=SE and SC>

0 and if said target node is in the state capable of providing service, decrementing said SC and accepting said retry request; and

an eighth facility for, when a retry request is received, if any of operation conditions in said fifth, sixth, and seventh facilities is not satisfied, returning a reject reply by attaching thereto the value of said RE in response to said retry request.

15. A recording medium readable by an initiator node in a computer network to which are connected at least one target node which provides service and a plurality of initiator nodes which request service from said target node, said recording medium having stored thereon a starvation avoiding program for implementing:

a facility for sending a first request to said target node during a period that said target node is unable to provide service; and

a facility for, when a reject reply is received from the target node in response to said first request, sending a retry request by attaching thereto a parameter whose value is equal to the value of a parameter of reject time information attached to said reject reply.