Computer network with microeconomic flow control

• US 6,055,571 A
• Filed: 11/20/1997
• Issued: 04/25/2000
• Est. Priority Date: 11/20/1997
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC USA (NEC Corporation)
• Inventors: Fulp, Errin W., Reininger, Daniel, Ott, Maximilian
• Primary Examiner(s): Meky, Moustafa M.
• Application Number:
  US08/971,127
• Time in Patent Office: 887 Days
• Field of Search: 709/200, 709/201, 709/203, 709/217, 709/218, 709/219, 709/224, 709/225, 709/226
• US Class Current: 709/224
• CPC Class Codes: H04L 12/1489 dependent on congestion
• CPC Class Codes: H04L 12/1492 negotiation of tariff
• CPC Class Codes: H04L 41/5006 Creating or negotiating SLA contracts, guarantees or penalties
• CPC Class Codes: H04L 41/5051 Service on demand, e.g. definition and deployment of services in real time
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers

Abstract

There is disclosed a decentralized flow control technique based on microeconomics. In this framework, there are three important entities: switches, network brokers and users. Switches independently price their resources to provide flow control and to encourage high utilization. A network broker, located at the entrance of the network, works as an agent for a user, monitoring the budget, prices and needs. Using this information the network broker may purchase resources to maximize the user'"'"'s quality of service. This approach has several advantages such as: decentralized control, minimal signaling, Pareto-optimal resource distribution, price stability and high network utilization.

Claims

1. A method of flow control for a network of switches connecting users, comprising:

providing a plurality of network brokers, each network broker corresponding to a respective one of a plurality of users, including a first network broker corresponding to a first user and a second network broker corresponding to a second user;

providing a quality of service profile for said first user to said first network broker;

providing route information relating to a route from said first to said second user, said route including one of said switches defining a first switch;

providing from said first user to said first network broker a present desired bandwidth value;

sending respective current price quote information from said first switch to said first network broker;

selecting, by said first network broker, of a resource utilization rate to define a selected resource utilization rate, wherein said selected resource utilization rate is selected based on;

a respective resource budget of said first user,

said quality of service profile of said first user,

said present desired bandwidth value for said first user, and

said current price quote information of said first switch; and

transmitting from said first user to said second user at said selected resource utilization rate.

2. The method of flow control as set forth in claim 1, wherein said first switch further sends updated price quote information at a timing based on changes in demand in said first switch.

3. The method of flow control as set forth in claim 2, wherein said updated price quote is defined by:

##EQU12## where;

p_n+1ⁱ is the updated price quote;

p_nⁱ is the current price for bandwidth at said switch;

BW_totalⁱ is the bandwidth capacity of said switch;

bw_recvⁱ is the total traffic entering said switch; and

c and α

are constants.

4. The method of flow control as set forth in claim 1, wherein:

said step of providing route information further comprises said route from said first to said second user being predetermined;

said route further includes another one of said switches defining a second switch; and

said selecting of said resource utilization rate by said first network broker is based also on respective current price quote information of said second switch.

5. The method of flow control as set forth in claim 4, wherein said step of sending respective current price quote information further comprises said second switch separately sending said respective current price quote information thereof to said first network broker.

6. The method of flow control as set forth in claim 4, wherein said step of sending respective current price quote information further comprises:

sending, from said second switch, respective current price quote information thereof to said first switch; and

said first switch including said respective current price quote information sent by said second switch in said respective price quote information price of said first switch sent to said first network broker.

7. The method of flow control as set forth in claim 1, further comprising:

said step of providing route information further comprising information relating to another route from said first to said second user, said another route including another one of said switches defining a second switch, said route that includes said first switch and said route that includes said second switch define a plurality of possible routes;

said selecting of said resource utilization rate by said first network broker being based also on respective current price quote information of said second switch; and

said first network broker selecting one of said plurality of possible routes based on a comparison of said current price quote information of said switches along said plurality of possible routes.

8. The method of flow control as set forth in claim 1, wherein said step of selecting said resource utilization rate further comprises:

making a pricing prediction, at said first network broker, of how said current price quote information will change in response to said first user transmitting to said second user; and

selecting said selected resource utilization rate based also on said pricing prediction.

9. A computer network, comprising:

switches, and users interfaced to said switches by respective network brokers corresponding to said users, including a first network broker corresponding to a first user and a second network broker corresponding to a second user;

said first network broker having, for said first user, a quality of service profile, a present desired bandwidth value, a resource budget, and route information relating to said switches including a route from said first to said second user, said route including one of said switches defining a first switch;

said first switch sending respective current price quote information to said first network broker;

said first network broker selecting a selected resource utilization rate based on;

said respective resource budget of said first user,

said quality of service profile of said first user,

said present desired bandwidth value for said first user, and

said current price quote information of said first switch; and

said first user transmitting to said second user at said selected resource utilization rate.

10. The computer network as set forth in claim 9, wherein said first switch farther sends updated price quote information at a timing based on changes in demand in said first switch.

11. The computer network as set forth in claim 10, wherein said updated price quote is defined by:

##EQU13## where;

p_n+1ⁱ is the updated price quote;

p_nⁱ is the current price for bandwidth at said switch;

BW_totalⁱ is the bandwidth capacity of the switch;

bw_recvⁱ is the total traffic entering the switch; and

C and α

are constants.

12. The computer network as set forth in claim 9, wherein:

said route information further comprises said route from said first to said second user being predetermined;

said route further includes another one of said switches defining a second switch; and

said selected resource utilization rate is based also on respective current price quote information of said second switch.

13. The computer network according to claim 12, wherein said second switch separately sends said respective current price quote information thereof to said first network broker.

14. The computer network according to claim 12, further comprising:

said second switch sending respective current price quote information thereof to said first switch; and

said respective price quote information of said first switch including said respective current price quote information sent by said second switch to said first switch.

15. The computer network as set forth in claim 9, further comprising:

said route information relating to said switches further comprising information relating to another route from said first to said second user, said another route including another one of said switches defining a second switch, said route that includes said first switch and said route that includes said second switch defining a plurality of possible routes; and

said first network broker selecting said selected resource utilization rate based also on respective current price quote information of said second switch; and

said first network broker selecting one of said plurality of possible routes based on comparing said current price quote information of said switches along said plurality of possible routes.

16. The computer network as set forth in claim 9, wherein:

said first network broker makes a pricing prediction of how said current price quote information will change in response to said first user transmitting to said second user; and

said first network broker selects said selected resource utilization rate based also on said pricing prediction.

17. A switching node of a computer network, comprising:

a network interface, a control system, and means for monitoring bandwidth;

said control system sending, via said network interface, current price quote information to network brokers on said computer network; and

said current price quote information being updated by said control system to provide an updated price quote at a timing based on switch demand as determined by said means for monitoring bandwidth.

18. The switching node as set forth in claim 17, wherein said updated price quote is defined by:

##EQU14## where;

p_n+1ⁱ is the updated price quote;

p_nⁱ is the current price for bandwidth at said switch;

BW_totalⁱ is the bandwidth capacity of the switch;

bw_recvⁱ is the total traffic entering the switch; and

c and α

are constants.

19. A computer program product, comprising:

computer readable instructions, and

a computer readable medium bearing said computer readable instructions;

said instructions being adapted to enable a computer to operate, in a network of switches connecting users, including a first and a second user, according to the steps of;

accessing a quality of service profile for said first user;

accessing route information relating to a route from said first to said second user, said route including one of said switches defining a first switch;

receiving from said first user an indication of a present desired bandwidth value;

receiving current price quote information from said first switch;

selecting a resource utilization rate to define a selected resource utilization rate based on a respective resource budget of said first user, said quality of service profile of said first user, said present desired bandwidth value for said first user, and said current price quote information of said first switch; and

indicating to said first user to transmit to said second user at said selected resource utilization rate.

20. The computer program product as set forth in claim 19, wherein said instructions enable said computer to process updated price quote information from said first switch.

21. The computer program product as set forth in claim 19, wherein said instructions enable said computer to operate according to the further steps of:

receiving, from a second switch on said route between said first and said second user, a respective current price quote sent from said second switch; and

basing said selection of said selected resource utilization rate further on said respective current price quote sent from said second switch.

22. The computer program product as set forth in claim 19, wherein said instructions enable said computer to operate according to the further step of selecting, from a plurality of possible routes between said first user and said second user, a route based on said respective current price quote information from each switch along each of said plurality of possible routes.

23. The computer program product as set forth in claim 19, wherein said instructions enable said computer to operate according to the further steps of:

making a pricing prediction of how said current price quote information will change in response to said first user transmitting to said second user; and

selecting said selected resource utilization rate based also on said pricing prediction.