맞춤기술찾기

홈으로 가기
맞춤기술찾기
이전대상기술
프린트하기

이전대상기술

파이프라인 방식의 힙 관리기 및 그의 우선순위 정렬 방법

  • 기술번호 : KST2015079472
  • 담당센터 : 대전기술혁신센터
  • 전화번호 : 042-610-2279
상담신청 PDF 받기
요약, Int. CL, CPC, 출원번호/일자, 출원인, 등록번호/일자, 공개번호/일자, 공고번호/일자, 국제출원번호/일자, 국제공개번호/일자, 우선권정보, 법적상태, 심사진행상태, 심판사항, 구분, 원출원번호/일자, 관련 출원번호, 기술이전 희망, 심사청구여부/일자, 심사청구항수의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 서지정보 표입니다.
요약 본 발명은 파이프라인 방식의 힙 관리기 및 그의 우선순위 정렬 방법에 관한 것이다. 본 발명에서는 10Gbps급 패킷 스케줄러에서 자신을 포함한 왼쪽 하위 노드들의 점유(Non-empty) 카운터를 이용하여 고속 정렬 기능을 수행한다. 구체적으로, 매 패킷 세그먼트 타임(32㎱)마다 2개의 패킷 세그먼트에 대한 우선순위 값을 받아 정렬을 수행하고, 1개의 가장 높은 우선순위 값을 가지는 패킷 세그먼트를 서비스한다. 따라서, 10Gbps 패킷 스케줄러에서 새로 입력되는 플로우의 패킷과 대기 중인 패킷을 동시에 받아 우선순위를 정렬할 수 있다. 이외에도, 연속적인 두 개의 패킷 세그먼트들 간에 메모리 충돌 없이 정렬 기능을 수행하며, 많은 우선순위 레벨에 대해 쉽게 확장할 수 있다. 또한, 작업 보존 방식과 비 작업 보존 방식으로 구성 가능하여 지연 경계(Delay Bound)나 지터(Jitter) 등 실시간 서비스 품질(QoS)의 보장을 제공할 수 있다. 파이프라인 힙 관리기, 우선순위, 패킷스케줄러, 고속 정렬
Int. CL H04L 12/865 (2014.01)
CPC H04L 47/6275(2013.01) H04L 47/6275(2013.01)
출원번호/일자 1020030092190 (2003.12.16)
출원인 한국전자통신연구원
등록번호/일자 10-0545634-0000 (2006.01.17)
공개번호/일자 10-2005-0060553 (2005.06.22) 문서열기
공고번호/일자 (20060124) 문서열기
국제출원번호/일자
국제공개번호/일자
우선권정보
법적상태 소멸
심사진행상태 수리
심판사항
구분
원출원번호/일자
관련 출원번호
심사청구여부/일자 Y (2003.12.16)
심사청구항수 23

출원인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 출원인 표입니다.
번호 이름 국적 주소
1 한국전자통신연구원 대한민국 대전광역시 유성구

발명자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 발명자 표입니다.
번호 이름 국적 주소
1 김광옥 대한민국 전라북도전주시덕진구
2 최병철 대한민국 대전광역시서구
3 박완기 대한민국 대전광역시유성구
4 곽동용 대한민국 대전광역시유성구
5 한만수 대한민국 대전광역시유성구

대리인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 대리인 표입니다.
번호 이름 국적 주소
1 유미특허법인 대한민국 서울특별시 강남구 테헤란로 ***, 서림빌딩 **층 (역삼동)

최종권리자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 최종권리자 표입니다.
번호 이름 국적 주소
1 한국전자통신연구원 대한민국 대전 유성구
번호, 서류명, 접수/발송일자, 처리상태, 접수/발송일자의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 행정처리 표입니다.
번호 서류명 접수/발송일자 처리상태 접수/발송번호
1 특허출원서
Patent Application		 2003.12.16 수리 (Accepted) 1-1-2003-0480735-60
2 선행기술조사의뢰서
Request for Prior Art Search		 2005.05.23 수리 (Accepted) 9-1-9999-9999999-89
3 선행기술조사보고서
Report of Prior Art Search		 2005.06.16 수리 (Accepted) 9-1-2005-0035278-13
4 의견제출통지서
Notification of reason for refusal		 2005.08.26 발송처리완료 (Completion of Transmission) 9-5-2005-0414052-29
5 의견서
Written Opinion		 2005.10.25 수리 (Accepted) 1-1-2005-0605504-43
6 명세서등보정서
Amendment to Description, etc.		 2005.10.25 보정승인간주 (Regarded as an acceptance of amendment) 1-1-2005-0605505-99
7 등록결정서
Decision to grant		 2006.01.13 발송처리완료 (Completion of Transmission) 9-5-2006-0019222-19
8 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2009.08.04 수리 (Accepted) 4-1-2009-5150899-36
9 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2015.02.02 수리 (Accepted) 4-1-2015-0006137-44
번호, 청구항의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 청구항 표입니다.
번호 청구항
1 1
패킷 스케줄러에서 입력되는 패킷 세그먼트를 우선 순위에 따라 정렬하는 힙 관리기에 있어서, 제1 레벨에 형성되는 최상위 노드; 및 제2 레벨 내지 제n (n은 2보다 큰 정수) 레벨의 각 레벨에 형성되어 각각 입력 패킷 세그먼트를 받아들이는 다수의 노드를 포함하고, 하나의 패킷 세그먼트를 상기 최상위 노드로 전송하여 출력되도록 하는 제1 및 제2 서브노드 트리 를 포함하고, 상기 제1 및 제2 서브 노드 트리의 각 노드는 자신을 포함한 제1 방향의 하위 레벨 점유 노드 수를 나타내는 카운터를 포함하는 힙 관리기
2 2
제1항에 있어서, 상기 제1 및 제2 서브노드 트리의 각 노드는 각 노드들로 입력된 패킷 세그먼트의 마감시간 값을 표시하는 마감시간 카운터 필드; 각 레벨의 각 노드의 위치를 나타내는 어드레스 필드; 및 하위 레벨 점유노드 개수를 나타내는 카운터 필드 를 포함하는 데이터 필드를 가지는 힙 관리기
3 3
제2항에 있어서, 상기 각 노드는 상기 카운터의 값과 상기 어드레스 필드에 저장된 어드레스 정보에 따라 패킷 세그먼트의 입출력을 수행하는 힙 관리기
4 4
제2항에 있어서, 상기 데이터 필드는 노드의 데이터들이 유효함을 나타내는 유효(Valid) 필드; 상기 카운터 오버플로우에 따른 정렬 기능을 제공하는 순환 중복(wrap-around) 필드; 스위치 포트를 나타낸 포트 필드; 및 각 포트내의 클래스 안에서 플로우를 구분하는 큐 식별자를 나타내는 클래스필드 를 더 포함하는 힙 관리기
5 5
제4항에 있어서, 상기 마감시간 카운터 필드에 저장되는 마감시간 카운터 비트와 상기 순환 중복 필드에 저장되는 순환 중복 비트는 상기 패킷 세그먼트들 마감순위 값으로 사용되며, 상기 순환 중복 비트는 상기 카운터의 오버플로우(overflow)가 발생될 경우, 잘못된 비교로 인한 우선순위 정렬 수행을 방지하는 것을 특징으로 하는 힙 관리기
6 6
제2항에서입력 모드시, 상기 제1 및 제2 서브노드 트리는 자신의 트리안에서 최상위 노드인 서브 최상위 노드의 카운터값과 입력되는 패킷 세그먼트의 마감 시간값에 따라 패킷 세그먼트를 저장할 유효한 비점유 노드를 찾아서 상기 패킷 세그먼트를 저장하는 힙 관리기
7 7
제2항에 있어서, 출력 모드시, 상기 제1 및 제2 서브노드 트리는 자신의 노드 중에서 최상위 노드인 서브 최상위 노드에 저장된 패킷 세그먼트의 마감 시간을 서로 비교한 후, 마감 시간이 적은 패킷 세그먼트를 상기 최상위 노드로 출력하는 힙 관리기
8 8
제2항에 있어서, 입출력 모드시, 상기 제1 및 제2 서브노드 트리는 자신의 트리안에서 최상위 노드인 서브 최상위 노드의 카운터값과 입력되는 패킷 세그먼트의 마감 시간값에 따라 패킷 세그먼트를 저장할 유효한 비점유 노드를 찾아서 상기 패킷 세그먼트를 저장하고, 각 트리의 서브 최상위 노드에 저장된 패킷 세그먼트의 마감 시간을 서로 비교한 후, 마감 시간이 적은 패킷 세그먼트를 상기 최상위 노드로 출력하는 힙 관리기
9 9
패킷 스케줄러에서 입력되는 패킷 세그먼트를 우선 순위에 따라 정렬하는 힙 관리기에 있어서, 입력되는 데이터를 저장하는 제1 및 제2 서브 관리기; 상기 제1 및 제2 서브 관리기의 제1 및 제2 데이터의 값을 비교하는 비교기; 및 상기 비교기의 결과에 따라 제1 또는 제2 데이터를 선택하여 저장하고, 서비스 조건에 따라 선택된 데이터를 출력하는 최상위 노드 레지스터; 를 포함하며, 2개의 데이터를 받고 1개의 데이터를 서비스하도록 하는 2개의 레벨 단위로 이루어지는 파이프라인 방식의 힙 관리기
10 10
제9항에 있어서, 상기 제1 및 제2 서브 관리기는 큐를 구성하는 n 레벨별 메모리; 패킷 세그먼트 타임마다 설정수를 카운트하며, 연속하는 2 레벨 단위의 메모리에 대하여 카운트를 수행하는 다수의 2 레벨 카운터; 동작 모드에 따라 상기 메모리에 저장된 값들을 비교하고 비교 결과에 따라 메모리에 저장된 값을 선택적으로 출력하는 n 레벨별 비교기; 상기 2레벨 카운터의 값에 따라 상기 연속하는 2레벨 단위의 메모리에 대한 읽기/쓰기 동작을 제어하며, 입출력 동작에 따라 상기 2레벨 카운터의 값을 증감시키는 다수의 2 레벨 제어기 를 포함하는 파이프라인 방식의 힙 관리기
11 11
제10항에 있어서, 상기 비교기는 입력 모드에서는 서로 인접한 메모리에 저장된 값들을 비교하고, 출력 모드에서는 동일한 메모리에 저장된 값들을 비교하며, 그리고 입출력 모드에서는 서로 인접한 메모리에 저장된 값과 동일한 메모리에 저장된 두개의 값인 총 3개의 값들을 비교하는 파이프라인 방식의 힙 관리기
12 12
제11항에 있어서, 상기 비교기는 메모리에 저장된 패킷 세그먼트들의 마감시간 값들을 서로 비교하는 파이프라인 방식의 힙 관리기
13 13
제10항에 있어서, 상기 각 레벨별 메모리는, 출력 동작을 설정 클럭 사이클 안에 수행하도록 레지스터로 이루어지는 L1 메모리; 2개의 큐를 구성하는 DPRAM 메모리를 사용하는 L2 메모리; 4개의 큐를 구성하는 DPRAM 메모리를 사용하는 L3 메모리; 8개의 큐를 구성하는 DPRAM 메모리를 사용하는 L4 메모리; 16개의 큐를 구성하는 DPRAM 메모리를 사용하는 L5 메모리; 32개의 큐를 구성하는 DPRAM 메모리를 사용하는 L6 메모리; 64개의 큐를 구성하는 DPRAM 메모리를 사용하는 L7 메모리; 및 128개의 큐를 구성하는 DPRAM 메모리를 사용하는 L8 메모리 를 포함하는 파이프라인 방식의 힙 관리기
14 14
제13항에 있어서, 상기 2 레벨 제어기는 상기 L1 메모리 및 L2 메모리의 읽기/쓰기 동작을 제어하는 제1 제어기; 상기 L3 메모리 및 L4 메모리의 읽기/쓰기 동작을 제어하는 제2 제어기; 상기 L5 메모리 및 L6 메모리의 읽기/쓰기 동작을 제어하는 제3 제어기; 및 상기 L7 메모리 및 L8 메모리의 읽기/쓰기 동작을 제어하는 제4 제어기 로 이루어지는 파이프라인 방식의 힙 관리기
15 15
제10항에 있어서,상기 2 레벨 카운터의 카운터 값은 각 파이프라인 단계에 따라 천이되며, 10Gbps 정렬을 수행하는데 요구되는 클럭 수에 해당하는 것을 특징으로 하는 파이프라인 방식의 힙 관리기
16 16
제10항에 있어서, 상기 힙 관리기는 2레벨 단위로 우선순위를 비교하여, 메모리 충돌 없이 데이터를 정렬하는 파이프라인 방식의 힙 관리기
17 17
제1 레벨에 형성되는 최상위 노드; 및 제2 레벨 내지 제n 레벨의 각 레벨에 형성되는 다수의 노드를 포함하고, 각 노드는 자신을 포함한 제1 방향의 하위 레벨 점유 노드 수를 나타내는 카운터를 포함하는 제1 및 제2 서브노드 트리를 포함하는 구조로 이루어지는 힙 관리기의 우선 순위 정렬 방법에 있어서, a) 패킷 세그먼트의 셀 입력과 상기 제1 및 제2 서브노드 트리의 최상위 노드인 서브 최상위 노드의 상태에 따라 입력 동작, 출력 동작, 및 입출력 동작을 선택하는 동작 모드 선택 단계; b) 상기 제1 또는 제2 서브노드 트리의 서브 최상위 노드값이 존재하지 않거나 또는 존재하나 노드값이 동작 모드에 따른 조건을 만족하지 않고 패킷 세그먼트만 입력된 경우에, 패킷 세그먼트를 비점유 노드로 저장하는 입력(Enqueue) 과정을 수행하는 단계; c) 상기 힙 관리기에 입력된 패킷이 없고, 상기 제1 및 제2 서브노드 트리의 서브 최상위 노드값이 존재하고, 상기 노드값이 동작 모드에 따른 조건을 만족할 경우에, 상기 제1 및 제2 서브노드 트리의 서브 최상위 노드값을 비교하여 작은 값의 마감시간을 가진 패킷 세그먼트를 상기 최상위 노드로 전송하는 출력(Dequeue) 과정을 수행하는 단계; 및 d) 상기 힙 관리기에 입력된 패킷이 있고, 제1 또는 제2 서브노드 트리의 서브 최상위 노드값이 존재하며, 상기 노드값이 동작 모드에 따른 조건을 만족할 경우에 수행되는 입출력(En-Dequeue) 과정을 수행하는 단계 를 포함하는 우선 순위 정렬 방법
18 18
제17항에 있어서 상기 힙 관리기에 패킷 세그먼트들이 존재하면 마감시간 안에 순서적으로 정렬된 패킷 세그먼트들을 계속 전송하는 작업 보존 방식, 및 주어진 마감시간이 되는 패킷 세그먼트들만 전송하는 비 작업 보존 방식 중에서 어느 하나를 설정하는 초기화 단계를 더 포함하는 우선 순위 정렬 방법
19 19
제17항에 있어서 패킷 세그먼트 타임마다 패킷 세그먼트가 입력되는 b) 단계 또는 패킷 세그먼트가 출력되는 c) 단계 또는 패킷 세그먼트가 입출력되거나 동시에 입출력되는 d) 단계가 수행되는 우선순위 정렬 방법
20 20
제17항에 있어서 상기 b) 단계는 b-1) 제2 서브노드 트리에서 새로운 패킷 세그먼트가 입력되면, 자신의 트리내의 최상위 노드인 서브 최상위 노드의 카운터값을 판단하여 서브 최상위 노드가 비어있는지를 판단하는 단계; b-2) 상기 서브 최상위 노드가 비어있는 경우에 상기 입력된 패킷 세그먼트를 상기 서브 최상위 노드로 전송하여 저장하는 단계; b-3) 상기 서브 최상위 노드가 비어있지 않은 경우, 패킷 세그먼트를 하위 노드로 전송할 경로를 선택하는 단계; b-4) 상기 입력된 패킷 세그먼트의 마감시간과 상기 서브 최상위 노드에 저장된 패킷 세그먼트의 마감시간을 비교하여 보다 작은 마감시간을 가지는 패킷 세그먼트를 상기 서브 최상위 노드에 저장하고, 보다 큰 마감 시간을 가지는 패킷 세그먼트를 선택된 경로로 전송하여 하위 노드에 저장시키는 단계 를 포함하는 우선 순위 정렬 방법
21 21
제20항에 있어서 상기 b-4) 단계는 상기 선택된 경로가 제1 방향인 경우에만 상기 서브 최상위 노드의 카운터값을 +1 증가시켜서, 제1 방향에 위치된 하위 노드의 점유 여부를 표시하는 우선 순위 정렬 방법
22 22
제17항에 있어서 상기 c) 단계는 c-1) 제1 및 제2 서브노드 트리의 서브 최상위 노드에 저장된 패킷 세그먼트의 마감시간을 비교하여, 보다 작은 마감 시간을 가지는 패킷 세그먼트를 상기 최상위 노드로 전송하여 출력되도록 하는 단계; 및 c-2) 상기 작은 마감 시간을 가지는 패킷 세그먼트가 저장되어 있던 서브노드 트리가 비어 있는 자신이 서브 최상위 노드를 채우기 위한 재정렬을 수행하는 단계 를 포함하는 우선 순위 정렬 방법
23 23
제22항에 있어서 상기 c-2) 단계는 상기 서브노드 트리의 서브 최상위 노드를 기준으로 제1 방향 및 제2 방향에 위치된 하위 노드의 카운터값을 비교하여 하위 노드의 점유 여부를 판단하는 단계; 제1 방향 및 제2 방향에 위치한 하위 노드에 패킷 세그먼트가 존재하여 점유되어 있는 경우, 상기 제1 및 제2 방향의 하위 노드에 각각 저장된 패킷 세그먼트의 마감시간을 비교하여, 보다 적은 마감 시간을 가지는 패킷 세그먼트를 상기 서브 최상위 노드로 전송하여 저장하는 단계 를 포함하는 우선 순위 정렬 방법
24 23
제22항에 있어서 상기 c-2) 단계는 상기 서브노드 트리의 서브 최상위 노드를 기준으로 제1 방향 및 제2 방향에 위치된 하위 노드의 카운터값을 비교하여 하위 노드의 점유 여부를 판단하는 단계; 제1 방향 및 제2 방향에 위치한 하위 노드에 패킷 세그먼트가 존재하여 점유되어 있는 경우, 상기 제1 및 제2 방향의 하위 노드에 각각 저장된 패킷 세그먼트의 마감시간을 비교하여, 보다 적은 마감 시간을 가지는 패킷 세그먼트를 상기 서브 최상위 노드로 전송하여 저장하는 단계 를 포함하는 우선 순위 정렬 방법
지정국 정보가 없습니다
패밀리정보가 없습니다
국가 R&D 정보가 없습니다.