Top-nodes 알고리즘

리소스 예약 달력을 관리하기 위해 그top-nodes 알고리즘은 알고리즘.이 알고리즘 먼저 2003,[1]에서 2009년 개선되었습니다가 출간되었다.[2]한 자원 많은 사용자(예를 들어 통신 링크에 대역 폭, 또는 큰 데이터 센터에서 디스크 용량)에서 공유됩니다 그것은 사용된다.

이 알고리즘에 이용자 허용한다.

• 만약 자원의 양 시간은 특정 기간 동안 사용할 수 있는지 점검한다.
• 리저브 리소스의 시간은 특정 기간에 대한 양.
• 이전 예약을 삭제하고,
• 달력 전방(달력고, 시간이 가앞으로 이동해야 한다고 정의된 기간을 덮)이동시키시오.

원리

달력이 잎 초등 기간을 나타내는 2진 트리로 저장됩니다.다른 노드 시대 그들의 모든 후손들이 덮여 있습니다.

예 새롭게 7시간의 달력(한시간의 초등 기간과).

시간의 기간 예약에 의해 싸여"top-nodes"의 집합을로 표시됩니다.정확히 시간의 예약 기간을 덮고 있는 노드의 이 세트는 최소한의 집합입니다.

바이너리 트리의 노드는 특정 예약의 "상위 노드"입니다.

• 그 후손들은 모두 예약 기간 내에 있다.
• 루트 노드이거나 상위 노드의 하위 노드 중 하나 이상이 예약 기간을 벗어났습니다.

1:00 ~ 5:59 예약의 상위 노드

각 노드에는 다음 값이 저장됩니다.

q(노드) = max(q(왼쪽 자식), q(오른쪽 자식)) + 이 노드를 "상위 노드"로 하는 모든 예약에 대해 예약된 총 리소스 양

(코드 최적화의 경우 보통 이 합계의 두 부분은 별도로 저장됩니다.)

성능

이 알고리즘의 장점은 새 자원 예약을 등록하는 시간이 달력 크기에만 의존한다는 것입니다(예약 총수에 의존하지 않음).

허락하다n달력에서 초승달의 개수입니다.

특정 예약의 최대 "top-nodes" 수는 2.log n입니다.

• 특정 기간 동안 사용 가능한 자원의 양을 확인하려면 O(log n)
• 특정 기간 동안 자원량을 예약하다: O(log n)
• 이전 예약을 삭제하려면: O(log n)
• 캘린더를 앞으로 이동하려면 : O(log n + M.log n)

어디에M는 추가된 캘린더 기간 동안 액티브한 예약 수입니다.

(M= 캘린더 종료 후 예약이 불가능한 경우 0).

레퍼런스

외부 링크

• (프랑스어) C 소스 코드