Top-nodes algorithm - Revision history

Bruce1ee: fixed lint errors – obsolete HTML tags

2022-10-05T13:34:00Z

fixed lint errors – obsolete HTML tags

← Previous revision		Revision as of 13:34, 5 October 2022
Line 9:		Line 9:
	==Principle==		==Principle==
	The calendar is stored as a [[binary tree]] where leaves represent elementary time periods. Other nodes represent the period of time covered by all their descendants.		The calendar is stored as a [[binary tree]] where leaves represent elementary time periods. Other nodes represent the period of time covered by all their descendants.
	~~<center>~~[[File:AlgoRayroleArbre.svg\|Example of a seven-hour calendar (with elementary periods of one hour)]]~~</center>~~		[[File:AlgoRayroleArbre.svg\|center\|Example of a seven-hour calendar (with elementary periods of one hour)]]
	<center>''Example of a seven-hour calendar (with elementary periods of one hour)''~~</center>~~		{{center\|''Example of a seven-hour calendar (with elementary periods of one hour)''}}

	The period of time covered by a reservation is represented by a set of "top-nodes". This set is the minimal set of nodes that exactly cover the reservation period of time.		The period of time covered by a reservation is represented by a set of "top-nodes". This set is the minimal set of nodes that exactly cover the reservation period of time.
Line 17:		Line 17:
	* all its descendants are inside the reservation period of time, and		* all its descendants are inside the reservation period of time, and
	* it is the root node, or at least one descendant of the parent node is outside of the reservation period of time.		* it is the root node, or at least one descendant of the parent node is outside of the reservation period of time.
	~~<center>~~[[File:AlgoRayroleResa.svg\|Top-nodes for a reservation from 1:00 to 5:59]]~~</center>~~		[[File:AlgoRayroleResa.svg\|center\|Top-nodes for a reservation from 1:00 to 5:59]]
	<center>''Top-nodes for a reservation from 1:00 to 5:59''~~</center>~~		{{center\|''Top-nodes for a reservation from 1:00 to 5:59''}}

	The following value is stored in each node:		The following value is stored in each node:

Rlink2: /* top /archive link repair, may include: archive. -> archive.today, and http->https for ghostarchive.org and archive.org (wp:el#Specifying_protocols)

2021-12-04T20:00:04Z

top: archive link repair, may include: archive.* -> archive.today, and http->https for ghostarchive.org and archive.org (wp:el#Specifying_protocols)

← Previous revision		Revision as of 20:00, 4 December 2021
Line 1:		Line 1:
	The '''top-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[https://archive.is/20120215024923/http://www.wikipatents.com/apps/20040204978.html Related US patent] (the algorithm is in the public domain since 2008)</ref> and has been improved in 2009.<ref>[https://www.researchgate.net/publication/311582722_Method_of_Managing_Resources_in_a_Telecommunication_Network_or_a_Computing_System Improved top-nodes algorithm]</ref> It is used when a resource is shared among many users (for example [[Bandwidth (signal processing)\|bandwidth]] in a [[telecommunication]] link, or [[disk capacity]] in a large [[data center]]).		The '''top-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[https://archive.today/20120215024923/http://www.wikipatents.com/apps/20040204978.html Related US patent] (the algorithm is in the public domain since 2008)</ref> and has been improved in 2009.<ref>[https://www.researchgate.net/publication/311582722_Method_of_Managing_Resources_in_a_Telecommunication_Network_or_a_Computing_System Improved top-nodes algorithm]</ref> It is used when a resource is shared among many users (for example [[Bandwidth (signal processing)\|bandwidth]] in a [[telecommunication]] link, or [[disk capacity]] in a large [[data center]]).

	The algorithm allows users to:		The algorithm allows users to:

Rogermx: Added wikilinks

2020-11-15T21:08:23Z

Added wikilinks

Jellysandwich0 at 17:55, 28 June 2020

2020-06-28T17:55:26Z

← Previous revision		Revision as of 17:55, 28 June 2020
Line 1:		Line 1:
	{{Underlinked\|date=December 2012}}		{{Underlinked\|date=December 2012}}

	The '''top-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[https://archive.is/20120215024923/http://www.wikipatents.com/apps/20040204978.html Related US patent] (the algorithm is in the public domain since 2008)</ref> and has been improved in 2009.<ref>[https://www.researchgate.net/publication/311582722_Method_of_Managing_Resources_in_a_Telecommunication_Network_or_a_Computing_System Improved top-nodes algorithm]</ref> It is used when a resource is shared among ~~lots of~~ users (for example [[Bandwidth (signal processing)\|bandwidth]] in a [[telecommunication]] link, or [[disk capacity]] in a large [[data center]]).		The '''top-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[https://archive.is/20120215024923/http://www.wikipatents.com/apps/20040204978.html Related US patent] (the algorithm is in the public domain since 2008)</ref> and has been improved in 2009.<ref>[https://www.researchgate.net/publication/311582722_Method_of_Managing_Resources_in_a_Telecommunication_Network_or_a_Computing_System Improved top-nodes algorithm]</ref> It is used when a resource is shared among many users (for example [[Bandwidth (signal processing)\|bandwidth]] in a [[telecommunication]] link, or [[disk capacity]] in a large [[data center]]).

	The algorithm allows users to:		The algorithm allows users to:
Line 11:		Line 11:
	==Principle==		==Principle==
	The calendar is stored as a [[binary tree]] where leaves represent elementary time periods. Other nodes represent the period of time covered by all their descendants.		The calendar is stored as a [[binary tree]] where leaves represent elementary time periods. Other nodes represent the period of time covered by all their descendants.
	<center>[[File:AlgoRayroleArbre.svg\|Example of a 7-hour calendar (with elementary periods of one hour)]]</center>		<center>[[File:AlgoRayroleArbre.svg\|Example of a seven-hour calendar (with elementary periods of one hour)]]</center>
	<center>''Example of a 7-hour calendar (with elementary periods of one hour)''</center>		<center>''Example of a seven-hour calendar (with elementary periods of one hour)''</center>

	The period of time covered by a reservation is represented by a set of "top-nodes". This set is the minimal set of nodes that exactly cover the reservation period of time.		The period of time covered by a reservation is represented by a set of "top-nodes". This set is the minimal set of nodes that exactly cover the reservation period of time.

Bellowhead678: time,and->time, and - Fix a typo in one click

2020-01-08T20:31:48Z

time,and->time, and - Fix a typo in one click

← Previous revision		Revision as of 20:31, 8 January 2020
Line 17:		Line 17:

	A node of the binary tree is a "top-node" for a given reservation if		A node of the binary tree is a "top-node" for a given reservation if
	* all its descendants are inside the reservation period of time,and		* all its descendants are inside the reservation period of time, and
	* it is the root node, or at least one descendant of the parent node is outside of the reservation period of time.		* it is the root node, or at least one descendant of the parent node is outside of the reservation period of time.
	<center>[[File:AlgoRayroleResa.svg\|Top-nodes for a reservation from 1:00 to 5:59]]</center>		<center>[[File:AlgoRayroleResa.svg\|Top-nodes for a reservation from 1:00 to 5:59]]</center>

Monkbot: /* External links */Task 15: language icon template(s) replaced (1×);

2020-01-02T16:28:33Z

External links: Task 15: language icon template(s) replaced (1×);

← Previous revision		Revision as of 16:28, 2 January 2020
Line 45:		Line 45:

	==External links==		==External links==
	* {{fr}} [http://www.developpez.net/forums/showthread.php?p=3078887 C source code]		* {{in lang\|fr}} [http://www.developpez.net/forums/showthread.php?p=3078887 C source code]

	[[Category:Scheduling algorithms]]		[[Category:Scheduling algorithms]]

Frap: /* Performance */

2019-12-18T11:59:42Z

Performance

← Previous revision		Revision as of 11:59, 18 December 2019
Line 30:		Line 30:
	The advantage of this algorithm is that the time to register a new resource reservation depends only on the calendar size (it does not depend on the total number of reservations).		The advantage of this algorithm is that the time to register a new resource reservation depends only on the calendar size (it does not depend on the total number of reservations).

	Let "n" be the number of elementary periods in the calendar.		Let {{var\|n}} be the number of elementary periods in the calendar.

	The maximal number of "top-nodes" for a given reservation is 2.log n.		The maximal number of "top-nodes" for a given reservation is 2.log n.
	* to check if an amount of resource is available during a specific period of time : O(log n)		* to check if an amount of resource is available during a specific period of time : ''O''(log ''n'')
	* to reserve an amount of resource for a specific period of time : O(log n)		* to reserve an amount of resource for a specific period of time : ''O''(log ''n'')
	* to delete a previous reservation : O(log n)		* to delete a previous reservation : ''O''(log ''n'')
	* to move the calendar forward : O(log n + M.log n)		* to move the calendar forward : ''O''(log ''n'' + M.log n)
	where M is the number of reservations that are active during the added calendar periods.		where {{var\|M}} is the number of reservations that are active during the added calendar periods.

	(M = 0 if reservations are not allowed after the end of the calendar.)		({{var\|M}} = 0 if reservations are not allowed after the end of the calendar.)

	==References==		==References==

Jabberjaw: clean up; move reflist; CE; using AWB

2018-08-16T03:37:39Z

clean up; move reflist; CE; using AWB

← Previous revision		Revision as of 03:37, 16 August 2018
Line 1:		Line 1:
	{{Underlinked\|date=December 2012}}		{{Underlinked\|date=December 2012}}

	The '''top-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[https://archive.is/20120215024923/http://www.wikipatents.com/apps/20040204978.html Related US patent] (the algorithm is in the public domain since 2008)</ref> and has been improved in 2009.<ref>[https://www.researchgate.net/publication/311582722_Method_of_Managing_Resources_in_a_Telecommunication_Network_or_a_Computing_System Improved top-nodes algorithm]</ref>		The '''top-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[https://archive.is/20120215024923/http://www.wikipatents.com/apps/20040204978.html Related US patent] (the algorithm is in the public domain since 2008)</ref> and has been improved in 2009.<ref>[https://www.researchgate.net/publication/311582722_Method_of_Managing_Resources_in_a_Telecommunication_Network_or_a_Computing_System Improved top-nodes algorithm]</ref> It is used when a resource is shared among lots of users (for example [[Bandwidth (signal processing)\|bandwidth]] in a [[telecommunication]] link, or [[disk capacity]] in a large [[data center]]).

		⚫	The algorithm allows users to:
	It is used when a resource is shared among lots of users (for example [[Bandwidth (signal processing)\|bandwidth]] in a [[telecommunication]] link, or [[disk capacity]] in a large [[data center]]).
		⚫	* check if an amount of resource is available during a specific period of time,

		⚫	* reserve an amount of resource for a specific period of time,
⚫	The algorithm allows
		⚫	* delete a previous reservation,
⚫	* to check if an amount of resource is available during a specific period of time,
		⚫	* move the calendar forward (the calendar covers a defined duration, and it must be moved forward as time goes by).
⚫	* to reserve an amount of resource for a specific period of time,
⚫	* to delete a previous reservation,
⚫	* to move the calendar forward (the calendar covers a defined duration, and it must be moved forward as time goes by).

	==Principle==		==Principle==
Line 19:		Line 17:

	A node of the binary tree is a "top-node" for a given reservation if		A node of the binary tree is a "top-node" for a given reservation if
	* all its descendants are inside the reservation period of time,		* all its descendants are inside the reservation period of time,and
	and
	* it is the root node, or at least one descendant of the parent node is outside of the reservation period of time.		* it is the root node, or at least one descendant of the parent node is outside of the reservation period of time.
	<center>[[File:AlgoRayroleResa.svg\|Top-nodes for a reservation from 1:00 to 5:59]]</center>		<center>[[File:AlgoRayroleResa.svg\|Top-nodes for a reservation from 1:00 to 5:59]]</center>
Line 43:		Line 40:

	(M = 0 if reservations are not allowed after the end of the calendar.)		(M = 0 if reservations are not allowed after the end of the calendar.)

		⚫	==References==
			{{Reflist}}

	==External links==		==External links==
	* {{fr}} [http://www.developpez.net/forums/showthread.php?p=3078887 C source code]		* {{fr}} [http://www.developpez.net/forums/showthread.php?p=3078887 C source code]

⚫	==References==
	<references/>

	[[Category:Scheduling algorithms]]		[[Category:Scheduling algorithms]]

GreenC bot: Rescued 1 archive link; reformat 1 link. Wayback Medic 2.1

2018-08-09T00:41:53Z

Rescued 1 archive link; reformat 1 link. Wayback Medic 2.1

← Previous revision		Revision as of 00:41, 9 August 2018
Line 1:		Line 1:
	{{Underlinked\|date=December 2012}}		{{Underlinked\|date=December 2012}}

	The '''top-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[http://www.wikipatents.com/apps/20040204978.html Related US patent]~~{{Dead link\|date=July 2018 \|bot=InternetArchiveBot \|fix-attempted=no }}~~ (the algorithm is in the public domain since 2008)</ref> and has been improved in 2009.<ref>[https://www.researchgate.net/publication/311582722_Method_of_Managing_Resources_in_a_Telecommunication_Network_or_a_Computing_System Improved top-nodes algorithm]</ref>		The '''top-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[https://archive.is/20120215024923/http://www.wikipatents.com/apps/20040204978.html Related US patent] (the algorithm is in the public domain since 2008)</ref> and has been improved in 2009.<ref>[https://www.researchgate.net/publication/311582722_Method_of_Managing_Resources_in_a_Telecommunication_Network_or_a_Computing_System Improved top-nodes algorithm]</ref>

	It is used when a resource is shared among lots of users (for example [[Bandwidth (signal processing)\|bandwidth]] in a [[telecommunication]] link, or [[disk capacity]] in a large [[data center]]).		It is used when a resource is shared among lots of users (for example [[Bandwidth (signal processing)\|bandwidth]] in a [[telecommunication]] link, or [[disk capacity]] in a large [[data center]]).

InternetArchiveBot: Rescuing 0 sources and tagging 1 as dead. #IABot (v2.0beta)

2018-07-05T21:13:42Z

Rescuing 0 sources and tagging 1 as dead. #IABot (v2.0beta)

← Previous revision		Revision as of 21:13, 5 July 2018
Line 1:		Line 1:
	{{Underlinked\|date=December 2012}}		{{Underlinked\|date=December 2012}}

	The '''top-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[http://www.wikipatents.com/apps/20040204978.html Related US patent] (the algorithm is in the public domain since 2008)</ref> and has been improved in 2009.<ref>[https://www.researchgate.net/publication/311582722_Method_of_Managing_Resources_in_a_Telecommunication_Network_or_a_Computing_System Improved top-nodes algorithm]</ref>		The '''top-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[http://www.wikipatents.com/apps/20040204978.html Related US patent]{{Dead link\|date=July 2018 \|bot=InternetArchiveBot \|fix-attempted=no }} (the algorithm is in the public domain since 2008)</ref> and has been improved in 2009.<ref>[https://www.researchgate.net/publication/311582722_Method_of_Managing_Resources_in_a_Telecommunication_Network_or_a_Computing_System Improved top-nodes algorithm]</ref>

	It is used when a resource is shared among lots of users (for example [[Bandwidth (signal processing)\|bandwidth]] in a [[telecommunication]] link, or [[disk capacity]] in a large [[data center]]).		It is used when a resource is shared among lots of users (for example [[Bandwidth (signal processing)\|bandwidth]] in a [[telecommunication]] link, or [[disk capacity]] in a large [[data center]]).

← Previous revision		Revision as of 21:08, 15 November 2020
Line 1:		Line 1:
	{{Underlinked\|date=December 2012}}

	The '''top-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[https://archive.is/20120215024923/http://www.wikipatents.com/apps/20040204978.html Related US patent] (the algorithm is in the public domain since 2008)</ref> and has been improved in 2009.<ref>[https://www.researchgate.net/publication/311582722_Method_of_Managing_Resources_in_a_Telecommunication_Network_or_a_Computing_System Improved top-nodes algorithm]</ref> It is used when a resource is shared among many users (for example [[Bandwidth (signal processing)\|bandwidth]] in a [[telecommunication]] link, or [[disk capacity]] in a large [[data center]]).		The '''top-nodes algorithm''' is an [[algorithm]] for managing a resource reservation calendar. The algorithm has been first published in 2003,<ref>[https://archive.is/20120215024923/http://www.wikipatents.com/apps/20040204978.html Related US patent] (the algorithm is in the public domain since 2008)</ref> and has been improved in 2009.<ref>[https://www.researchgate.net/publication/311582722_Method_of_Managing_Resources_in_a_Telecommunication_Network_or_a_Computing_System Improved top-nodes algorithm]</ref> It is used when a resource is shared among many users (for example [[Bandwidth (signal processing)\|bandwidth]] in a [[telecommunication]] link, or [[disk capacity]] in a large [[data center]]).

	The algorithm allows users to:		The algorithm allows users to:
	* check if an amount of resource is available during a specific period of time,		* check if an amount of [[resource]] is available during a specific period of time,
	* reserve an amount of resource for a specific period of time,		* reserve an amount of resource for a specific period of time,
	* delete a previous reservation,		* delete a previous reservation,
Line 16:		Line 14:
	The period of time covered by a reservation is represented by a set of "top-nodes". This set is the minimal set of nodes that exactly cover the reservation period of time.		The period of time covered by a reservation is represented by a set of "top-nodes". This set is the minimal set of nodes that exactly cover the reservation period of time.

	A node of the binary tree is a "top-node" for a given reservation if		A node of the [[binary tree]] is a "top-node" for a given reservation if
	* all its descendants are inside the reservation period of time, and		* all its descendants are inside the reservation period of time, and
	* it is the root node, or at least one descendant of the parent node is outside of the reservation period of time.		* it is the root node, or at least one descendant of the parent node is outside of the reservation period of time.
Line 25:		Line 23:
	q(node) = max(q(left child), q(right child))		q(node) = max(q(left child), q(right child))
	+ total amount of reserved resource for all reservations having this node as a "top-node"		+ total amount of reserved resource for all reservations having this node as a "top-node"
	(for code optimization, the two parts of this sum are usually stored separately.)		(for [[code optimization]], the two parts of this sum are usually stored separately.)

	==Performance==		==Performance==