[go: up one dir, main page]

KR20120055946A - 공평한 대역 할당 기반 패킷 스케줄링 방법 및 장치 - Google Patents

공평한 대역 할당 기반 패킷 스케줄링 방법 및 장치 Download PDF

Info

Publication number
KR20120055946A
KR20120055946A KR1020100117408A KR20100117408A KR20120055946A KR 20120055946 A KR20120055946 A KR 20120055946A KR 1020100117408 A KR1020100117408 A KR 1020100117408A KR 20100117408 A KR20100117408 A KR 20100117408A KR 20120055946 A KR20120055946 A KR 20120055946A
Authority
KR
South Korea
Prior art keywords
packet
time
arrival
flow
estimated
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
KR1020100117408A
Other languages
English (en)
Other versions
KR101737516B1 (ko
Inventor
고남석
박종대
예병호
노성기
정우석
문승진
허환조
이순석
Original Assignee
한국전자통신연구원
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 한국전자통신연구원 filed Critical 한국전자통신연구원
Priority to KR1020100117408A priority Critical patent/KR101737516B1/ko
Priority to US13/301,350 priority patent/US8929216B2/en
Publication of KR20120055946A publication Critical patent/KR20120055946A/ko
Application granted granted Critical
Publication of KR101737516B1 publication Critical patent/KR101737516B1/ko
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/52—Queue scheduling by attributing bandwidth to queues
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/56—Queue scheduling implementing delay-aware scheduling
    • H04L47/568—Calendar queues or timing rings
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/58—Changing or combining different scheduling modes, e.g. multimode scheduling
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/62—Queue scheduling characterised by scheduling criteria
    • H04L47/629—Ensuring fair share of resources, e.g. weighted fair queuing [WFQ]

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

라우터와 같은 네트워크 장치 등에서 동일한 출력 포트로의 전송을 요구하는 여러 플로우 간에 공평하게 대역폭을 사용할 수 있도록 하는 패킷 스케줄링 방법 및 장치가 제공된다. 패킷 스케줄링 방법은, 각 플로우에 균등하게 할당된 대역폭 및 현재 입력된 k번째 패킷의 길이를 이용하여 각 플로우의 다음 번 입력되는 k+1번째 패킷의 도착 예정 시간을 계산하는 단계와, k+1번째 패킷이 도착되면, k+1번째 패킷의 도착 예정 시간 및 k+1번째 패킷의 실제 도착 시간을 비교하는 단계와, 비교 결과에 따라, 각 플로우의 k+1번째 패킷을 스케줄링하는 단계를 포함한다.

Description

공평한 대역 할당 기반 패킷 스케줄링 방법 및 장치{Method and apparatus for packet scheduling based on allocating fair bandwidth}
본 발명은 패킷 스케줄링에 관한 것으로, 더욱 상세하게는, 라우터와 같은 네트워크 장치 등에서 동일한 출력 포트로의 전송을 요구하는 여러 플로우 간에 공평하게 대역폭을 사용할 수 있도록 하는 패킷 스케줄링 방법 및 장치에 관한 것이다.
다양한 응용 서비스의 출현 및 사용자의 증가와 함께 네트워크에서의 QoS(Quality of Service)를 제공하기 위한 방법으로서 호 수락 제어(Call Admission Control), 버퍼 관리(buffer management), 패킷 스케줄링(Packet Scheduling), 혼잡 제어(Congestion Control), QoS 라우팅 등 많은 방법이 연구되어 왔다.
이 중 패킷 스케줄링 방법은 네트워크 성능을 보장하기 위한 방법으로 다양한 형태로 네트워크 장치에 적용되어 있다. 그 중 가상 시간을 유지하고 그 가상 시간에 따라서 각 패킷의 가상 시작시간 및 종료시간의 계산을 기반으로 하는 WFQ (Weighted Fair Queueing) 및 유사한 페어 큐잉(Fair Queueing) 알고리즘은 각 계산 방식에 따라 계산된 가상 시작시간 또는 가상 종료시간을 패킷에 타임스탬프(time stamp)로 할당하고 그 값에 따른 정렬 구조에 따른 스케줄링을 하기 때문에 일반적으로 N개의 플로우가 존재할 때 O(logN)의 복잡도(complexity)를 갖는다.
또한, 시간 축을 프레임 단위로 나누고 패킷이 도착하는 프레임에 따른 패킷 스케줄링을 수행하는 스탑-앤드-고우(Stop-and-Go)나 계층적 라운드 로빈(Hierarchical-Round-Robin) 등의 방법은 프레임의 크기에 따라서 시스템의 성능에 많은 영향을 미치며 프레임간 동기화를 요구하기 때문에 대규모 네트워크에서는 적용하기 힘든 구조적인 문제점이 있다.
본 발명은 플로우 별로 공평하게 네트워크 대역을 할당하도록 하고 그 할당된 대역에 따라서 각 패킷 별로 도착 예상 시간(Expected Time of Arrival)을 이용하여, 각 플로우별 트래픽을 제어함으로써 각 플로우 별로 네트워크 대역을 공평하게 사용할 수 있도록 하기 위한 스케줄링 방법을 제공한다.
일 측면에 따른 패킷 스케줄링 방법은, 각 플로우에 균등하게 할당된 대역폭 및 현재 입력된 k번째 패킷의 길이를 이용하여 각 플로우의 다음 번 입력되는 k+1번째 패킷의 도착 예정 시간을 계산하는 단계와, k+1번째 패킷이 도착되면, k+1번째 패킷의 도착 예정 시간 및 k+1번째 패킷의 실제 도착 시간을 비교하는 단계와, 비교 결과에 따라, 각 플로우의 k+1번째 패킷을 스케줄링하는 단계를 포함한다.
각 플로우의 k+1번째 패킷의 도착 예정 시간 및 k+1번째 패킷의 실제 도착 시간을 비교하는 단계는, k+1번째 패킷의 도착 예정 시간을 k+1번째 패킷의 실제 도착 시간(CUR)에 버스트 허용에 따른 버스트 허용 시간(BT)을 합산한 시간과 비교하는 단계를 포함할 수 있다.
비교 결과에 따라, 각 플로우의 k+1번째 패킷을 스케줄링하는 단계는, 각 플로우의 k+1번째 패킷의 도착 예정 시간이, k+1번째 패킷의 실제 도착 시간(CUR)에 버스트 허용에 따른 버스트 허용 시간(BT)을 합산한 시간보다 늦은 경우에는, k+1번째 패킷을 폐기하는 단계를 포함할 수 있다.
비교 결과에 따라, 각 플로우의 k+1번째 패킷을 스케줄링하는 단계는, k+1번째 패킷의 실제 도착 시간에 버스트 허용에 따른 버스트 허용 시간(BT)을 합산한 시간보다 늦지 않은 경우에는, k+1번째 패킷의 도착 예정 시간을 k+1번째 패킷의 실제 도착 시간(CUR)에서 도착 예정 시간에 대한 재보정 한계 시간(LT)을 뺀 시간과의 비교하는 단계를 더 포함할 수 있다.
각 플로우의 k+1번째 패킷을 스케줄링하는 단계는, k+1번째 패킷의 도착 예정 시간이, k+1번째 패킷의 실제 도착 시간에서 재보정 한계 시간(LT)을 뺀 시간 보다 작은 경우, k+1번째 패킷의 도착 예정 시간을 현재 시간(CUR)으로 초기화하는 단계를 포함하고, k+1번째 패킷의 도착 예정 시간이, k+1번째 패킷의 실제 도착 시간(CUR)에서 재보정 한계 시간(LT)을 뺀 시간 보다 작지 않은 경우, 계산된 k+1번째 패킷의 도착 예정 시간을 기반으로 k+1번째 패킷 다음에 입력되는 k+2번째 패킷의 도착 예정 시간을 계산하는 단계를 더 포함할 수 있다.
각 플로우에는, 각 플로우에 대한 패킷이 출력되는 출력 링크를 공유하는 모든 플로우의 개수로 균등하게 분할된 대역폭이 할당된다. 출력 링크에 설정된 대역폭에서 실제 이용되지 않는 대역폭이 있는 경우, 실제 이용되지 않는 대역폭을 출력 링크를 공유하는 모든 플로우에 균등하게 배분하는 단계를 더 포함할 수 있다.
k+1번째 패킷의 도착 예정 시간을 계산하는 단계는, k번째 입력된 패킷의 도착 예정 시간에 k번째 입력된 패킷의 길이를 k번째 입력된 패킷의 플로우에 할당된 대역폭으로 나눈 값을 합산하여, k+1번째 패킷의 도착 예정 시간을 계산하는 단계를 포함할 수 있다.
패킷 스케줄링 방법은, 입력된 패킷의 플로우가, 적어도 하나의 플로우에 대한 정보를 저장하는 플로우 정보 저장부에서 검색되지 않는 새로운 플로우에 해당되는 경우, 입력된 패킷에 대한 플로우 정보를 생성하여 플로우 정보 저장부에 추가하는 단계와, 입력된 패킷의 도착 예정 시간을 입력된 패킷이 실제 도착된 시간으로 설정하는 단계와, 설정된 도착 예정 시간을 이용하여, 새로운 플로우의 다음 패킷의 도착 예정 시간을 계산하는 단계를 더 포함할 수 있다.
다른 측면에 따른 패킷 스케줄링 장치는, 각 플로우에 균등하게 할당된 대역폭 및 현재 입력된 k번째 패킷의 길이를 이용하여 각 플로우의 다음 번 입력되는 k+1번째 패킷의 도착 예정 시간을 계산하는 도착 예정 시간 계산부와, k+1번째 패킷이 도착되면, k+1번째 패킷의 도착 예정 시간 및 k+1번째 패킷의 실제 도착 시간을 비교하고, 비교 결과에 따라, 각 플로우의 k+1번째 패킷을 스케줄링하는 패킷 스케줄링부를 포함한다.
본 발명에 따르면, 각 플로우별로 공평한 대역을 결정하고 그 결정된 대역기반으로 각 패킷의 스케줄링 시간을 결정하도록 함으로써 네트워크의 트래픽 체증(traffic congestion)에 반응하지 않는 트래픽(unresponsive traffic)에 대한 효율적인 제어와 각 플로우간 공평한 대역 사용 등이 가능하다. 또한, WFQ(Weigted Fair Queuing) 등과 같이 가상 시간과 가상 시간에 의해서 계산된 각 패킷에 할당된 타임스탬프 값 기반의 정렬구조를 필요로 하지 않으며, 프레임 기반의 스케줄링알고리즘과 같이 프레임 크기의 조정 및 프레임간 동기화 등을 필요로 하지 않는다.
도 1은 본 발명의 일 실시예에 따른 패킷의 도착 예정 시간에 기반한 패킷 스케줄링 방법을 나타내는 순서도이다.
도 2는 도 1의 패킷의 도착 예정 시간에 기반한 패킷 스케줄링 처리 방법의 상세 처리 과정의 일 예를 나타내는 순서도이다.
도 3은 도 1의 패킷의 도착 예정 시간에 기반한 공평한 대역 할당 기반 패킷 스케줄링 방법을 수행하는 패킷 스케줄링 장치의 구성의 일 예를 나타내는 도면이다.
이하, 첨부된 도면을 참조하여 본 발명의 일 실시예를 상세하게 설명한다. 본 발명을 설명함에 있어 관련된 공지 기능 또는 구성에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명을 생략할 것이다. 또한, 후술되는 용어들은 본 발명에서의 기능을 고려하여 정의된 용어들로서 이는 사용자, 운용자의 의도 또는 관례 등에 따라 달라질 수 있다. 그러므로 그 정의는 본 명세서 전반에 걸친 내용을 토대로 내려져야 할 것이다.
도 1은 본 발명의 일 실시예에 따른 패킷의 도착 예정 시간에 기반한 패킷 스케줄링 방법을 나타내는 순서도이다.
본 발명에 의한 공평한 대역 할당 기반 패킷 스케줄링 방법은, 라우터와 같은 네트워크 장치 등에서 동일한 출력 포트로의 전송을 요구하는 여러 데이터 트래픽 플로우 간에 공평하게 대역폭을 사용할 수 있도록 한다. 데이터 트래픽 플로우(이하, 플로우라 함)는 데이터 패킷 헤더로부터 추출할 수 있는 필드의 동일한 조합으로 정의될 수 있는 일련의 패킷의 모음으로 정의될 수 있다. 예를 들어 인터넷 프로토콜의 헤더에서 소스 IP 주소, 목적지 IP 주소, 프로토콜 값, TCP/UDP의 소스 포트 번호, TCP/UDP의 목적지 포트 번호가 동일한 일련의 패킷을 하나의 플로우로 정의할 수 있다. 또한, 경우에 따라서는 소스 IP 주소 하나의 필드를 사용하여 하나의 플로우가 규정될 수도 있다.
이러한 플로우 간의 패킷 스케줄링을 결정하기 위하여 각 플로우에 대한 정보를 포함하는 플로우 정보 저장부(도시되지 않음)가 이용된다. 플로우 정보 저장부는 각 플로우별 메모리 블록으로 구성될 수 있다. 각 플로우별 메모리 블록에는, 플로우의 포워딩 정보 및 스케줄링 처리 정보 등의 다양한 플로우의 특징 또는 상태 변화 등이 저장되고, 유지되며, 갱신될 수 있다. 예를 들어, 각 플로우별 메모리 블록은, 플로우에 대한 패킷 스케줄링을 제공하기 위해서 필요한 플로우의 QoS 제공 유형(QoS Type), 각 플로우에 할당된 대역폭(bandwidth) 등과 같은 QoS 요구 조건 및 패킷 스케줄링을 위한 상태 정보를 포함할 수 있다.
도 1을 참조하면, 패킷 스케줄링을 위하여, 균등하게 할당된 대역폭을 가지는 각 플로우마다, 각 플로우별로 균등하게 할당된 대역 및 각 플로우의 현재 입력된 k번째 패킷의 길이를 고려하여, 다음에 입력되는 k+1번째 패킷의 도착 예정 시간(Expected Time of Arrival; ETA)이 계산된다(110).
그런 다음, 각 플로우의 k+1번째 패킷의 도착 예정 시간 및 k+1번째 패킷의 실제 도착 시간이 비교된다(120). k+1번째 패킷의 도착 예정 시간(ETA)과 k+1번째 패킷의 실제 도착 시간을 비교할 때 어느 정도의 패킷이 몰려서 들어오는 버스트를 허용하기 위한 버스트 허용에 따른 버스트 허용 시간(burst tolerance; BT)를 고려할 수 있다.
비교 결과에 따라, 각 플로우의 k+1번째 패킷이 스케줄링된다(130). 해당 플로우의 k+1번째 패킷의 도착 예정 시간(ETA)을 k+1번째 패킷의 실제 도착 시간(CUR)에 버스트 허용 시간(BT)을 합한 시간을 비교하여, k+1번째 패킷이 도착 예정 시간(ETA)이 k+1번째 패킷의 실제 도착 시간(CUR)에 버스트 허용 시간(BT)을 합한 시간(CUR+BT)보다 늦은 경우에는, k+1번째 패킷은 각 플로우에 공평하게 할당된 대역을 위배하여 전송된 것으로 폐기될 수 있다.
k+1번째 패킷이 도착 예정 시간(ETA)보다 늦거나 도착 예정 시간(ETA)에 맞춰서 도착한 경우, 해당 패킷을 스케줄링하여 전송할 수 있다. 도 1의 패킷 스케줄링 방법에는 실제 구현예에 따라서 다른 부가적인 패킷 처리 절차가 수반될 수 있다.
한편, 일 실시예에 따라 플로우들에 균등하게 할당되는 임의의 플로우(i)에 할당된 대역(
Figure pat00001
)은 다음과 같이 구해질 수 있다.
패킷의 출력 링크의 대역폭 중 다른 용도로 사용되는 등 일부 대역을 제외하고, 출력 링크를 공유하는 모든 플로우가 공평하게 나누어 쓸 수 있는 총 대역폭을
Figure pat00002
라고 가정한다. 이 경우, 어느 플로우(i)가 최소한 보장 받아야 하는 최소 대역(
Figure pat00003
)은 총 대역폭(
Figure pat00004
)을 공유하는 플로우 수(N)를 고려하여
Figure pat00005
가 된다.
이때,
Figure pat00006
이면, 즉, N개의 플로우 중 일부 플로우가 최소 대역(
Figure pat00007
) 이하의 트래픽을 사용하고 있어서 실제 사용되는 대역폭이 총 대역폭(
Figure pat00008
)보다 작은 임의의 값(
Figure pat00009
)인 경우, 사용의 효율을 높이기 위해서 사용하지 않고 있는 만큼의 대역(
Figure pat00010
)을 나머지의 플로우가 공정하게 나누어 쓸 수 있도록 할당된 대역이 조정될 수 있다.
이를 위해서 다시 N개의 플로우 각각에게
Figure pat00011
가 더 할당될 수 있다. 이와 같은 과정에 따라서, 각 플로우에게 실제 할당되는 대역(
Figure pat00012
)은
Figure pat00013
으로 조정될 수 있다.
도 2는 도 1의 패킷의 도착 예정 시간에 기반한 패킷 스케줄링 처리 방법의 상세 처리 과정의 일 예를 나타내는 순서도이다.
패킷 입력 대기 상태(210)에서, 일단 패킷이 입력되면, 플로우 정보 저장부(도시되지 않음)에 대한 정보 검색이 수행되어(220), 입력된 패킷의 플로우 정보가 플로우 정보 저장부에 이미 생성된 플로우의 연속된 패킷(subsequent packet)인지 아니면, 플로우 정보가 아직 생성되지 않은 새로운 플로우의 첫 번째 패킷인지를 확인된다(230).
입력된 패킷에 대한 플로우는 플로우 정보가 플로우 정보 저장부에 이미 생성된 플로우를 플로우(i)라고 가정한다. 현재 도착되어 입력된 패킷이 플로우(i)에 대해 손실 없이 연속되어 전송된 k 번째 패킷인 경우, 플로우 정보 저장부에 저장되어 있는 플로우(i)의 k번째 패킷의 도착 예정 시간(
Figure pat00014
)이 k번째 패킷의 실제 도착 시간(CUR)보다 큰지를 비교한다. 실제 도착 시간(CUR)은, 본 발명에 따른 패킷 스케줄링 방법을 수행하는 장치의 시스템 클럭 시간에 대응된다.
k번째 패킷의 도착 예정 시간(
Figure pat00015
)은 k-1번째 패킷이 입력된 때 플로우(i)에 균등하게 할당된 대역폭(
Figure pat00016
), 이전 패킷인 k-1번째 패킷의 도착 예정 시간(
Figure pat00017
) 및 k-1번째 패킷의 길이(
Figure pat00018
)를 이용하여 다음과 같은 수학식 1을 이용하여 계산된 값일 수 있다.
[수학식 1]
Figure pat00019
이미 생성된 플로우(i)에 대한 연속된 k번째 패킷에 대하여, 버스트 허용치(burst tolerance) 또는 버스트 허용 시간(BT)을 고려하여, k번째 패킷의 도착 예상 시간(
Figure pat00020
)을, k번째 패킷이 실제 도착 시간(CUR)에 버스트 허용 시간(BT)을 합산한 시간과 비교하여, k번째 패킷이 버스트 허용 시간(BT)을 초과하여 빨리 입력되었는지가 확인될 수 있다(242). 버스트 허용 시간(BT)는 네트워크 상황 등에 따라 0(zero)을 포함한 소정의 시간으로 설정될 수 있다.
k번째 패킷의 도착 예상 시간(
Figure pat00021
)이 실제 도착 시간(CUR)에 버스트 허용 시간(BT)을 합산한 시간(CUR+BT)보다 크다면(244), k번째 패킷은 버스트 허용 시간(BT)을 초과한 패킷으로 k번째 패킷은 폐기 처리될 수 있다(246).
k번째 패킷의 도착 예정 시간(
Figure pat00022
)이 실제 도착 시간(CUR)에 버스트 허용 시간(BT)을 합산한 시간(CUR+BT)보다 작거나 같다면(244), 다시 도착 예정 시간(ETA)에 대한 재보정 한계 시간(LT)(이하에서, 재보정 한계 시간이라 함)를 고려하여, k번째 패킷의 도착 예정 시간(
Figure pat00023
)을, k번째 패킷의 실제 도착 시간(CUR)에 ETA 재보정 한계 시간(LT)을 뺀 시간과 비교하여, k번째 패킷이 실제 도착 시간(CUR)에 ETA 재보정 한계 시간(LT)을 초과하여 늦게 입력되었는지가 확인될 수 있다(244). 재보정 한계 시간(LT)은 네트워크 상황 등에 따라 설정될 수 있다.
k번째 패킷의 도착 예정 시간(
Figure pat00024
)이 k번째 패킷의 실제 도착 시간(CUR)에 ETA 재보정 한계 시간(LT)을 뺀 시간(CUR-LT)보다 작으면(242), k번째 패킷은 재보정 한계 시간(LT)을 초과하여 늦게 도착한 패킷으로, 해당 플로우의 도착 예정 시간(ETA)이 시스템 클럭과 계속 벌어지지 않도록, 현재 시스템 클럭으로 재조정한다. 즉, k번째 패킷의 도착 예정 시간(
Figure pat00025
)을 실제 도착 시간(CUR)으로 초기화할 수 있다(250).
그런 다음, 플로우(i)의 k번째 패킷의 길이 (
Figure pat00026
)을 고려하여 수학식 2와 같이, k+1번째 패킷의 도착 예정 시간(
Figure pat00027
)을 계산할 수 있다(260).
[수학식 2]
Figure pat00028
이와 같이 계산된, 다음 전송될 k+1번째 패킷의 도착 예상 시간(
Figure pat00029
)을 플로우 정보 저장부에 저장하여, 플로우(i)에 대한 플로우 상태 정보를 업데이트할 수 있다(270). k번째 패킷은 실제 도착 시간(CUR)으로 초기화된 도착 예상 시간(
Figure pat00030
)을 기초로 스케줄링될 수 있다(280).
k번째 패킷의 도착 예정 시간(
Figure pat00031
)이 k번째 패킷의 실제 도착 시간(CUR)에 ETA 재보정 한계 시간(LT)을 뺀 시간(CUR-LT)보다 크거나 같으면(242), k번째 패킷은 도착 예정 시간(
Figure pat00032
)보다 늦게 들어왔지만 아직 재보정 한계 시간(LT)을 초과하지 않은 패킷이다. 이러한 패킷은 플로우(i)의 k번째 패킷의 길이(
Figure pat00033
)을 고려하여 수학식 2와 같이, k+1번째 패킷의 도착 예상 시간(
Figure pat00034
)이 계산될 수 있다(260). k+1번째 패킷의 도착 예상 시간(
Figure pat00035
)은 플로우 정보 저장부에 업데이트되고(270), k번째 패킷은 도착 예상 시간(
Figure pat00036
)에 기반하여 스케줄링될 수 있다(280).
입력된 패킷이, 생성되지 않은 임의의 플로우(j)에 대한 첫 번째 패킷인 경우에는 플로우 정보를 생성하여 플로우 정보 저장부에 추가한다(240). 동작 240이수행될 때, 새로운 플로우(j)에 할당될 대역 (
Figure pat00037
)이 계산될 수 있다. 새로운 플로우(j)에 할당될 대역 (
Figure pat00038
)은 전술한 바와 같이, 모든 플로우가 공평하게 나누어 쓸 수 있는 총 대역폭(
Figure pat00039
)을 출력 링크를 공유하는 모든 플로우의 수(N)로 분할하여, 플로우(j)를 포함하는 출력 링크를 공유하는 모든 플로우에 공평하게 대역폭이 할당될 수 있다.
플로우(j)의 도착 예정 시간(
Figure pat00040
)을 패킷 도착 시간인 현재의 시스템 클럭 시간(CUR)로
Figure pat00041
초기화한다(250).
그리고 플로우(j)의 첫 번째 패킷의 길이(
Figure pat00042
) 및 플로우(j)에 할당된 대역 (
Figure pat00043
)을 고려하여, 플로우(j)의 다음 패킷의 도착 예정 시간(
Figure pat00044
)을 수학식 3을 이용하여 계산할 수 있다(260).
[수학식 3]
Figure pat00045
다음 패킷의 도착 예정 시간(
Figure pat00046
)은 플로우 정보 저장부의 플로우(j)에 대한 메모리 블록에 업데이트되고(270), 플로우(j)의 첫 번째 패킷은 패킷 도착 시간으로 초기화된 패킷 도착 예정 시간(
Figure pat00047
)에 기반하여 스케줄링될 수 있다(280).
도 3은 도 1의 패킷의 도착 예정 시간에 기반한 공평한 대역 할당 기반 패킷 스케줄링 방법을 수행하는 패킷 스케줄링 장치의 구성의 일 예를 나타내는 도면이다.
도 3의 패킷 스케줄링 장치(300)는 입력 처리부(310), 플로우 정보 저장부(320), 도착 예정 시간 계산부(330) 및 패킷 스케줄링부(340)를 포함할 수 있다. 패킷 스케줄링 장치(300)는 라우터, L3 스위치 등 다양한 네트워크 장치로 구현될 수 있다. 패킷 스케줄링 장치(300)는 입력 링크(10)를 통해 패킷을 입력받고, 출력 링크(20)를 통해 스케줄링된 패킷을 출력할 수 있다.
입력 처리부(310)는 패킷을 입력받고, 입력된 패킷에 대한 플로우 정보를 생성하여 플로우 정보 저장부(320)에 저장할 수 있다. 입력 처리부(310)는 플로우 정보 저장부(320)에서 플로우 정보를 검색하고 갱신하여 관리할 수 있다.
입력 처리부(310)는 입력된 패킷에 대한 플로우 정보가 적어도 하나의 플로우에 대한 정보를 저장하는 플로우 정보 저장부(320)에서 검색되는지 여부를 확인할 수 있다. 입력 처리부(310)는 입력된 패킷에 대한 플로우가 플로우 정보 저장부(320)에서 검색되지 않는 새로운 플로우에 해당되는 경우, 입력된 패킷에 대한 플로우 정보를 생성하여 플로우 정보 저장부(320)에 추가할 수 있다.
플로우 정보 저장부(320)는 플로우의 포워딩 정보 및 스케줄링 처리 정보 등의 다양한 플로우의 특징 또는 상태 변화 등을 저장, 유지 및 갱신하도록 구성될 수 있다. 플로우 정보 저장부(320)는 도착 예정 시간 계산부(330)에서 계산되는 각 플로우의 다음 패킷의 도착 예정 시간 정보를 저장할 수 있다. 이하에서, 현재 입력된 패킷을 k번째 패킷이고, 다음 입력되는 패킷을 k+1번째 패킷이라 한다.
도착 예정 시간 계산부(330)는 각 플로우에 균등하게 할당된 대역폭 및 현재 입력된 k번째 패킷의 길이를 이용하여 각 플로우의 다음 번 입력되는 k+1번째 패킷의 도착 예정 시간을 계산한다. 도착 예정 시간 계산부(330)는, k번째 패킷의 길이를 플로우에 할당된 대역폭으로 나눈 값을 k번째 패킷의 도착 예정 시간에 합산하여, k+1번째 패킷의 도착 예정 시간을 계산할 수 있다.
도착 예정 시간 계산부(330)는 입력 링크(10) 및 출력 링크(20)의 대역폭 이용율을 관리할 수 있다. 도착 예정 시간 계산부(330)는, 출력 링크(20)에 설정된 대역폭에서 실제 이용되지 않는 대역폭이 있는 경우, 실제 이용되지 않는 대역폭을 출력 링크(20)를 공유하는 모든 플로우에 균등하게 배분할 수 있다. 출력 링크(20)를 공유하는 모든 플로우의 개수는 플로우 정보 저장부(320)에서 관리하는 모든 플로우의 개수에 대응한다.
패킷 스케줄링부(340)는 각 플로우의 패킷의 도착 예정 시간 및 패킷의 실제 도착 시간을 비교하고, 비교 결과에 따라, 각 플로우의 다음 패킷을 스케줄링한다. 패킷 스케줄링부(340)는 k+1번째 패킷이 도착되면, k+1번째 패킷의 도착 예정 시간 및 k+1번째 패킷의 실제 도착 시간을 비교하고, 비교 결과에 따라, 각 플로우의 k+1번째 패킷을 스케줄링할 수 있다. 패킷 스케줄링부(340)는 스케줄링 입력부(342), 패킷 포인터 버퍼(344) 및 스케줄링 출력부(346)를 포함할 수 있다.
스케줄링 입력부(342)는 계산된 도착 예정 시간(ETA)에 따라 패킷 포인터 버퍼(344)에 패킷을 할당한다. 스케줄링 입력부(342)는 각 패킷의 도착 예정 시간에 따라 할당된 패킷 포인터 버퍼(344)의 타임 슬롯에 다음 패킷을 할당한다.
스케줄링 입력부(342)는, 입력된 패킷이 각 플로우의 첫 번째 패킷이 아닌 경우, k+1번째 패킷의 도착 예정 시간을 k+1번째 패킷의 실제 도착 시간(CUR)에 버스트 허용에 따른 버스트 허용 시간(BT)을 합산한 시간과 비교할 수 있다. 스케줄링 입력부(342)는, 각 플로우의 k+1번째 패킷의 도착 예정 시간이, k+1번째 패킷의 실제 도착시간(CUR)에 버스트 허용에 따른 버스트 허용 시간(BT)을 합산한 시간보다 늦은 경우에는, k+1번째 패킷을 폐기할 수 있다.
또한, 스케줄링 입력부(342)는, 각 플로우의 k+1번째 패킷의 도착 예정 시간이, k+1번째 패킷의 실제 도착 시간(CUR)에 버스트 허용에 따른 버스트 허용 시간(BT)을 합산한 시간보다 늦지 않은 경우에는, k+1번째 패킷의 도착 예정 시간을 패킷의 실제 도착 시간(CUR)에서 도착 예정 시간에 대한 재보정 한계 시간(LT)을 뺀 시간과 비교할 수 있다.
스케줄링 입력부(342)는, k+1번째 패킷의 도착 예정 시간이, k+1번째 패킷의 실제 도착 시간(CUR)에서 재보정 한계 시간(LT)을 뺀 시간 보다 작은 경우, k+1번째 패킷의 도착 예정 시간을 k+1번째 패킷의 실제 도착 시간으로 초기화할 수 있다. 스케줄링 입력부(342)는, k+1번째 패킷의 도착 예정 시간이, k+1번째 패킷의 실제 도착 시간(CUR)에서 도착 예정 시간에 대한 재보정 한계 시간(LT)을 뺀 시간 보다 작지 않은 경우, k+1번째 패킷의 도착 예정 시간을 기반으로 k+1번째 패킷의 다음으로 입력되는 k+2번째 패킷의 도착 예정 시간을 계산할 수 있다.
패킷 포인터 버퍼(344)는 각 패킷의 도착 예정 시간에 따라 할당된 복수 개의 타임 슬롯을 포함할 수 있다. 패킷 포인터 버퍼(344)는, 타임 슬롯에 대응하는 큐의 처음과 끝이 연결되도록 구성된 환형 큐 방식으로 동작될 수 있다.
패킷 포인터 버퍼(344)는 메모리의 용량에 따라서 다양한 크기를 가질 수 있으며 도 3에서는 16,384개의 타임 슬롯을 가지는 경우를 도시하였다. 하나의 타임 슬롯의 크기 역시 메모리 용량에 따라서 다양한 크기를 가질 수 있다. 예를 들어 하나의 타임 슬롯은 8 마이크로 초 단위로 만들어질 수 있다. 즉, 8 마이크로 초 단위로 도착 예정 시간(ETA) 값에 따라서 스케줄링 입력부(342)는 패킷 포인터 버퍼(344)로 패킷을 할당할 수 있다.
스케줄링 출력부(346)는 출력 링크(20)의 대역에 따라서 패킷을 패킷 포인터 버퍼(344)로부터 스케줄링 입력부(342)에 의해 할당된 패킷을 하나씩 처리하여 출력 링크(20)로 전송한다.
도 3의 패킷 스케줄링 장치(300)는 일 실시예에 따른 패킷 스케줄링 방법을 수행하기 위한 구성이며, 실제 구현시는 다양한 기능 블록이 추가될 수 있다. 본 발명에 따르면, 각 플로우별로 공평한 대역을 결정하고 그 결정된 대역기반으로 각 패킷의 스케줄링 시간을 결정하도록 함으로써 네트워크의 트래픽 체증(traffic congestion)에 반응하지 않는 트래픽(unresponsive traffic)에 대한 효율적인 제어와 각 플로우간 공평한 대역 사용 등이 가능하다. 또한, WFQ(Weigted Fair Queuing) 등과 같이 가상 시간과 가상 시간에 의해서 계산된 각 패킷에 할당된 타임스탬프 값 기반의 정렬구조를 필요로 하지 않으며, 프레임 기반의 스케줄링알고리즘과 같이 프레임 크기의 조정 및 프레임간 동기화 등을 필요로 하지 않는다.
본 발명의 일 양상은 컴퓨터로 읽을 수 있는 기록 매체에 컴퓨터가 읽을 수 있는 코드로서 구현될 수 있다. 상기의 프로그램을 구현하는 코드들 및 코드 세그먼트들은 당해 분야의 컴퓨터 프로그래머에 의하여 용이하게 추론될 수 있다. 컴퓨터가 읽을 수 있는 기록매체는 컴퓨터 시스템에 의하여 읽혀질 수 있는 데이터가 저장되는 모든 종류의 기록 장치를 포함한다. 컴퓨터가 읽을 수 있는 기록 매체의 예로는 ROM, RAM, CD-ROM, 자기 테이프, 플로피 디스크, 광 디스크 등을 포함한다. 또한, 컴퓨터가 읽을 수 있는 기록 매체는 네트워크로 연결된 컴퓨터 시스템에 분산되어, 분산 방식으로 컴퓨터가 읽을 수 있는 코드로 저장되고 실행될 수 있다.
이상의 설명은 본 발명의 일 실시예에 불과할 뿐, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자는 본 발명의 본질적 특성에서 벗어나지 않는 범위에서 변형된 형태로 구현할 수 있을 것이다. 따라서, 본 발명의 범위는 전술한 실시예에 한정되지 않고 특허 청구범위에 기재된 내용과 동등한 범위 내에 있는 다양한 실시 형태가 포함되도록 해석되어야 할 것이다.
300: 패킷 스케줄링 장치 310: 입력 처리부
320: 플로우 정보 저장부 330: 도착 예정 시간 계산부
340: 패킷 스케줄링부 342: 스케줄링 입력부
344: 패킷 포인터 버퍼 346: 스케줄링 출력부

Claims (19)

  1. 각 플로우에 균등하게 할당된 대역폭 및 현재 입력된 k번째 패킷의 길이를 이용하여 각 플로우의 다음 번 입력되는 k+1번째 패킷의 도착 예정 시간을 계산하는 단계; 및
    상기 k+1번째 패킷이 도착되면, 상기 k+1번째 패킷의 도착 예정 시간 및 상기 k+1번째 패킷의 실제 도착 시간을 비교하는 단계; 및
    상기 비교 결과에 따라, 상기 각 플로우의 상기 k+1번째 패킷을 스케줄링하는 단계를 포함하는 패킷 스케줄링 방법.
  2. 제1항에 있어서,
    상기 각 플로우의 상기 k+1번째 패킷의 도착 예정 시간 및 상기 k+1번째 패킷의 실제 도착 시간을 비교하는 단계는,
    상기 k+1번째 패킷의 도착 예정 시간을 상기 k+1번째 패킷의 실제 도착 시간(CUR)에 버스트 허용에 따른 버스트 허용 시간(BT)을 합산한 시간과 비교하는 단계를 포함하는 패킷 스케줄링 방법.
  3. 제2항에 있어서,
    상기 비교 결과에 따라, 상기 각 플로우의 상기 k+1번째 패킷을 스케줄링하는 단계는,
    상기 각 플로우의 k+1번째 패킷의 도착 예정 시간이, 상기 k+1번째 패킷의 실제 도착 시간(CUR)에 버스트 허용에 따른 버스트 허용 시간(BT)을 합산한 시간보다 늦은 경우에는, 상기 k+1번째 패킷을 폐기하는 단계를 포함하는 패킷 스케줄링 방법.
  4. 제3항에 있어서,
    상기 비교 결과에 따라, 상기 각 플로우의 상기 k+1번째 패킷을 스케줄링하는 단계는,
    상기 k+1번째 패킷의 실제 도착 시간에 버스트 허용에 따른 버스트 허용 시간(BT)을 합산한 시간보다 늦지 않은 경우에는,
    상기 k+1번째 패킷의 도착 예정 시간을 상기 k+1번째 패킷의 실제 도착 시간(CUR)에서 도착 예정 시간에 대한 재보정 한계 시간(LT)을 뺀 시간과의 비교하는 단계를 더 포함하는 패킷 스케줄링 방법.
  5. 제4항에 있어서,
    상기 각 플로우의 상기 k+1번째 패킷을 스케줄링하는 단계는,
    상기 k+1번째 패킷의 도착 예정 시간이, 상기 k+1번째 패킷의 실제 도착 시간에서 상기 재보정 한계 시간(LT)을 뺀 시간 보다 작은 경우, 상기 k+1번째 패킷의 도착 예정 시간을 현재 시간(CUR)으로 초기화하는 단계를 포함하고,
    상기 k+1번째 패킷의 도착 예정 시간이, 상기 k+1번째 패킷의 실제 도착 시간(CUR)에서 상기 재보정 한계 시간(LT)을 뺀 시간 보다 작지 않은 경우, 상기 계산된 k+1번째 패킷의 도착 예정 시간을 기반으로 상기 k+1번째 패킷 다음에 입력되는 k+2번째 패킷의 도착 예정 시간을 계산하는 단계를 더 포함하는 패킷 스케줄링 방법.
  6. 제1항에 있어서,
    상기 각 플로우에는, 상기 각 플로우에 대한 패킷이 출력되는 출력 링크를 공유하는 모든 플로우의 개수로 균등하게 분할된 대역폭이 할당되는 패킷 스케줄링 방법.
  7. 제6항에 있어서,
    상기 출력 링크에 설정된 대역폭에서 실제 이용되지 않는 대역폭이 있는 경우, 상기 실제 이용되지 않는 대역폭을 상기 출력 링크를 공유하는 모든 플로우에 균등하게 배분하는 단계를 더 포함하는 패킷 스케줄링 방법.
  8. 제1항에 있어서,
    상기 k+1번째 패킷의 도착 예정 시간을 계산하는 단계는,
    상기 k번째 입력된 패킷의 도착 예정 시간에 상기 k번째 입력된 패킷의 길이를 상기 k번째 입력된 패킷의 플로우에 할당된 대역폭으로 나눈 값을 합산하여, 상기 k+1번째 패킷의 도착 예정 시간을 계산하는 단계를 포함하는 패킷 스케줄링 방법.
  9. 제8항에 있어서,
    입력된 패킷의 플로우가, 적어도 하나의 플로우에 대한 정보를 저장하는 플로우 정보 저장부에서 검색되지 않는 새로운 플로우에 해당되는 경우, 상기 입력된 패킷에 대한 플로우 정보를 생성하여 상기 플로우 정보 저장부에 추가하는 단계;
    상기 입력된 패킷의 도착 예정 시간을 상기 입력된 패킷이 실제 도착된 시간으로 설정하는 단계; 및
    상기 설정된 도착 예정 시간을 이용하여, 상기 새로운 플로우의 다음 패킷의 도착 예정 시간을 계산하는 단계를 더 포함하는 패킷 스케줄링 방법.
  10. 각 플로우에 균등하게 할당된 대역폭 및 현재 입력된 k번째 패킷의 길이를 이용하여 상기 각 플로우의 다음 번 입력되는 k+1번째 패킷의 도착 예정 시간을 계산하는 도착 예정 시간 계산부; 및
    상기 k+1번째 패킷이 도착되면, 상기 k+1번째 패킷의 도착 예정 시간 및 상기 k+1번째 패킷의 실제 도착 시간을 비교하고, 상기 비교 결과에 따라, 상기 각 플로우의 상기 k+1번째 패킷을 스케줄링하는 패킷 스케줄링부를 포함하는 패킷 스케줄링 장치.
  11. 제10항에 있어서,
    상기 k+1번째 패킷의 도착 예정 시간을 포함하는, 적어도 하나의 플로우에 대한 정보를 저장하는 플로우 정보 저장부를 더 포함하는 패킷 스케줄링 장치.
  12. 제11항에 있어서,
    상기 도착 예정 시간 계산부는, 상기 k번째 패킷의 길이를 상기 k번째 패킷의 플로우에 할당된 대역폭으로 나눈 값을, 상기 k번째 패킷의 도착 예정 시간에 합산하여, 상기 k+1번째 패킷의 도착 예정 시간을 계산하는 패킷 스케줄링 장치.
  13. 제12항에 있어서,
    입력된 패킷에 대한 플로우 정보가 적어도 하나의 플로우에 대한 정보를 저장하는 플로우 정보 저장부에서 검색되는지 여부를 확인하는 입력 처리부를 더 포함하고,
    상기 입력된 패킷에 대한 플로우가 상기 플로우 정보 저장부에서 검색되지 않는 새로운 플로우에 해당되는 경우, 상기 입력 처리부는, 상기 입력된 패킷에 대한 플로우 정보를 생성하여 상기 플로우 정보 저장부에 추가하는 패킷 스케줄링 장치.
  14. 제10항에 있어서,
    상기 패킷 스케줄링부는,
    각 패킷의 도착 예정 시간에 따라 할당된 복수 개의 타임 슬롯을 포함하는 패킷 포인터 버퍼;
    상기 각 패킷의 도착 예정 시간에 따라 할당된 상기 패킷 포인터 버퍼의 타임 슬롯에 상기 각 패킷을 할당하는 스케줄링 입력부; 및
    상기 패킷 포인터 버퍼에서 상기 할당된 패킷을 전송하는 스케줄링 출력부를 포함하는 패킷 스케줄링 장치.
  15. 제14항에 있어서,
    상기 스케줄링 입력부는,
    입력된 패킷이 각 플로우의 첫 번째 패킷이 아닌 경우, 상기 k+1번째 패킷의 도착 예정 시간을 상기 k+1번째 패킷의 실제 도착 시간(CUR)에 버스트 허용에 따른 버스트 허용 시간(BT)을 합산한 시간과 비교하고,
    상기 각 플로우의 k+1번째 패킷의 도착 예정 시간이, 상기 k+1번째 패킷의 실제 도착시간(CUR)에 버스트 허용에 따른 버스트 허용 시간(BT)을 합산한 시간보다 늦은 경우에는, 상기 k+1번째 패킷을 폐기하는 패킷 스케줄링 장치.
  16. 제15항에 있어서,
    상기 스케줄링 입력부는,
    상기 각 플로우의 상기 k+1번째 패킷의 도착 예정 시간이, 상기 k+1번째 패킷의 실제 도착 시간(CUR)에 버스트 허용에 따른 버스트 허용 시간(BT)을 합산한 시간보다 늦지 않은 경우에는,
    상기 k+1번째 패킷의 도착 예정 시간을 패킷의 실제 도착 시간(CUR)에서 도착 예정 시간에 대한 재보정 한계 시간(LT)을 뺀 시간과 비교하는 패킷 스케줄링 장치.
  17. 제16항에 있어서,
    상기 스케줄링 입력부는,
    상기 k+1번째 패킷의 도착 예정 시간이, 상기 k+1번째 패킷의 실제 도착 시간(CUR)에서 상기 재보정 한계 시간(LT)을 뺀 시간 보다 작은 경우, 상기 k+1번째 패킷의 도착 예정 시간을 상기 k+1번째 패킷의 실제 도착 시간으로 초기화하고,
    상기 k+1번째 패킷의 도착 예정 시간이, 상기 k+1번째 패킷의 실제 도착 시간(CUR)에서 도착 예정 시간에 대한 재보정 한계 시간(LT)을 뺀 시간 보다 작지 않은 경우, 상기 계산된 k+1번째 패킷의 도착 예정 시간을 기반으로 상기 k+1번째 패킷의 다음으로 입력되는 k+2번째 패킷의 도착 예정 시간을 계산하는 패킷 스케줄링 장치.
  18. 제14항에 있어서,
    상기 패킷 포인터 버퍼는, 타임 슬롯에 대응하는 큐의 처음과 끝이 연결되도록 구성된 환형 큐 방식으로 동작되는 패킷 스케줄링 장치.
  19. 제10항에 있어서,
    상기 도착 예정 시간 계산부는, 출력 링크에 설정된 대역폭에서 실제 이용되지 않는 대역폭이 있는 경우, 상기 실제 이용되지 않는 대역폭을 상기 플로우 정보 저장부에서 관리하는 모든 플로우에 균등하게 배분하는 패킷 스케줄링 장치.
KR1020100117408A 2010-11-24 2010-11-24 공평한 대역 할당 기반 패킷 스케줄링 방법 및 장치 Expired - Fee Related KR101737516B1 (ko)

Priority Applications (2)

Application Number Priority Date Filing Date Title
KR1020100117408A KR101737516B1 (ko) 2010-11-24 2010-11-24 공평한 대역 할당 기반 패킷 스케줄링 방법 및 장치
US13/301,350 US8929216B2 (en) 2010-11-24 2011-11-21 Packet scheduling method and apparatus based on fair bandwidth allocation

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020100117408A KR101737516B1 (ko) 2010-11-24 2010-11-24 공평한 대역 할당 기반 패킷 스케줄링 방법 및 장치

Publications (2)

Publication Number Publication Date
KR20120055946A true KR20120055946A (ko) 2012-06-01
KR101737516B1 KR101737516B1 (ko) 2017-05-18

Family

ID=46064293

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020100117408A Expired - Fee Related KR101737516B1 (ko) 2010-11-24 2010-11-24 공평한 대역 할당 기반 패킷 스케줄링 방법 및 장치

Country Status (2)

Country Link
US (1) US8929216B2 (ko)
KR (1) KR101737516B1 (ko)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR102217478B1 (ko) * 2019-09-05 2021-02-18 에스케이텔레콤 주식회사 패킷 처리 시간 조정방법 및 장치

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2014055680A2 (en) * 2012-10-03 2014-04-10 Spark Integration Technologies Inc. Systems and methods for adaptive load balanced communications, routing, filtering, and access control in distributed networks
US10033644B2 (en) * 2013-02-12 2018-07-24 Adara Networks, Inc. Controlling congestion controlled flows
US9237108B2 (en) * 2013-12-12 2016-01-12 Tektronix Texas, Llc Jitter buffer emulation for RTP streams in passive network monitoring systems
US10721178B2 (en) * 2016-01-22 2020-07-21 Medtronic, Inc. Systems, apparatus and methods facilitating data buffering and removal
US11510220B2 (en) * 2017-11-24 2022-11-22 Telefonaktiebolaget Lm Ericsson (Publ) Location aware scheduling

Family Cites Families (28)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CA2164546C (en) * 1995-12-06 2001-04-10 Maher Nihad Fahmi Traffic controller for cell-based transmission
US6108303A (en) * 1995-12-06 2000-08-22 Pmc-Sierra Ltd. Method and apparatus for traffic control in a cell-based network
JPH09224034A (ja) * 1996-02-19 1997-08-26 Fujitsu Ltd カウンタ値のオーバーフロー処理方式、セル流入制御方式
JP3686493B2 (ja) * 1996-03-07 2005-08-24 富士通株式会社 Ａｔｍ交換機におけるフィードバック制御方法および装置
FR2745968B1 (fr) * 1996-03-08 1998-04-03 Thomson Csf Procede d'espacement de cellules atm et dispositif pour sa mise en oeuvre
JP3435293B2 (ja) 1996-09-10 2003-08-11 株式会社東芝 パケットスケジューリング装置及びパケット転送方法
US5864540A (en) * 1997-04-04 1999-01-26 At&T Corp/Csi Zeinet(A Cabletron Co.) Method for integrated traffic shaping in a packet-switched network
DE19742378A1 (de) * 1997-09-25 1999-04-22 Siemens Ag Ringspeicher für eine TDMA-Datenübertragungsstation und entsprechende Datenübertragungsstation
CA2229577A1 (en) * 1998-02-12 1999-08-12 Newbridge Networks Corporation Method and apparatus for controlling traffic flows in a packet-switched network in order to guarantee service performance
US6563796B1 (en) * 1998-03-18 2003-05-13 Nippon Telegraph And Telephone Corporation Apparatus for quality of service evaluation and traffic measurement
US6381214B1 (en) * 1998-10-09 2002-04-30 Texas Instruments Incorporated Memory-efficient leaky bucket policer for traffic management of asynchronous transfer mode data communications
US6754182B1 (en) * 1999-10-21 2004-06-22 International Business Machines Corporation Method and apparatus for policing cell-based traffic
FR2800222B1 (fr) * 1999-10-26 2001-11-23 Mitsubishi Electric Inf Tech Procede de mise en conformite a un contrat de trafic d'un flux de paquets d'un reseau de transport de paquets a longueur variable
WO2001043347A2 (en) 1999-12-08 2001-06-14 The University Of British Columbia Weighted fair queuing scheduler
US6810031B1 (en) * 2000-02-29 2004-10-26 Celox Networks, Inc. Method and device for distributing bandwidth
US6707821B1 (en) * 2000-07-11 2004-03-16 Cisco Technology, Inc. Time-sensitive-packet jitter and latency minimization on a shared data link
US6917589B2 (en) * 2001-01-25 2005-07-12 Agere Systems Inc. Automatic quality of service assignment in ethernet switches
JPWO2003053012A1 (ja) * 2001-12-14 2005-04-28 古河電気工業株式会社 ポリシング制御方法、その制御装置およびその制御装置を用いたネットワークシステム
US6795452B2 (en) * 2002-05-31 2004-09-21 Sandbridge Technologies, Inc. Method of tracking time intervals for a communication signal
US7286624B2 (en) * 2003-07-03 2007-10-23 Navcom Technology Inc. Two-way RF ranging system and method for local positioning
WO2005065023A2 (en) * 2004-01-05 2005-07-21 Checkpoint Software Technologies Ltd. Internal network security
JP4454338B2 (ja) * 2004-02-17 2010-04-21 富士通株式会社 パケット整形装置及びパケット整形方法
US7477596B1 (en) * 2004-08-31 2009-01-13 Adtran, Inc. Policing engine providing dynamic adjustment of peak and sustained data cell rates and efficient transfer of AAL5 cells
US8503299B2 (en) * 2005-05-12 2013-08-06 Apple, Inc. Method and system for packet scheduling
JP4648833B2 (ja) * 2005-12-28 2011-03-09 富士通株式会社 帯域管理装置
JP4888396B2 (ja) * 2007-03-05 2012-02-29 ソニー株式会社 無線通信システム、無線通信装置及び無線通信方法、並びにコンピュータ・プログラム
KR20120055947A (ko) * 2010-11-24 2012-06-01 한국전자통신연구원 가입자 인지 플로우별 ＱｏＳ 제공 방법 및 장치
US9247512B2 (en) * 2011-08-25 2016-01-26 Ubiquiti Networks Adaptive synchronous protocol for minimizing latency in TDD systems

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR102217478B1 (ko) * 2019-09-05 2021-02-18 에스케이텔레콤 주식회사 패킷 처리 시간 조정방법 및 장치

Also Published As

Publication number Publication date
US20120127859A1 (en) 2012-05-24
US8929216B2 (en) 2015-01-06
KR101737516B1 (ko) 2017-05-18

Similar Documents

Publication Publication Date Title
US10764215B2 (en) Programmable broadband gateway hierarchical output queueing
US11316795B2 (en) Network flow control method and network device
JP3953819B2 (ja) スケジューリング装置およびスケジューリング方法
CN110166380B (zh) 调度报文的方法、第一网络设备及计算机可读存储介质
US7969881B2 (en) Providing proportionally fair bandwidth allocation in communication systems
US11831550B2 (en) Fine grain traffic shaping offload for a network interface card
JP2014187421A (ja) 通信装置及びパケットスケジューリング方法
US7292578B1 (en) Flexible, high performance support for QoS on an arbitrary number of queues
KR101737516B1 (ko) 공평한 대역 할당 기반 패킷 스케줄링 방법 및 장치
US10063478B2 (en) Switching device and control method of switching device
AU2002339349B2 (en) Distributed transmission of traffic flows in communication networks
US10044632B2 (en) Systems and methods for adaptive credit-based flow
KR20120055947A (ko) 가입자 인지 플로우별 ＱｏＳ 제공 방법 및 장치
EP2063580B1 (en) Low complexity scheduler with generalized processor sharing GPS like scheduling performance
JP2007013462A (ja) パケットスケジューラおよびパケットスケジューリング方法
Bruneel et al. Queueing models for the analysis of communication systems
US8467401B1 (en) Scheduling variable length packets
Liebeherr et al. Buffer management and scheduling for enhanced differentiated services
JP3783628B2 (ja) 通信システムにおけるノード装置及びその動作制御方法
JP2004320380A (ja) 帯域制御方法およびその帯域制御装置
Kogan et al. Large profits or fast gains: A dilemma in maximizing throughput with applications to network processors
Rahbar et al. LGRR: A new packet scheduling algorithm for differentiated services packet-switched networks
KR100745679B1 (ko) 적응 라운드 로빈을 이용한 패킷 스케쥴링 방법 및 장치
US12223345B1 (en) Multi-threaded traffic shaper
US8031721B2 (en) Method and apparatus for marking and scheduling packets for transmission

Legal Events

Date Code Title Description
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20101124

PG1501 Laying open of application
A201 Request for examination
PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 20150909

Comment text: Request for Examination of Application

Patent event code: PA02011R01I

Patent event date: 20101124

Comment text: Patent Application

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20160816

Patent event code: PE09021S01D

E90F Notification of reason for final refusal
PE0902 Notice of grounds for rejection

Comment text: Final Notice of Reason for Refusal

Patent event date: 20170203

Patent event code: PE09021S02D

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

Patent event code: PE07011S01D

Comment text: Decision to Grant Registration

Patent event date: 20170411

PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20170512

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20170512

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
PR1001 Payment of annual fee

Payment date: 20200427

Start annual number: 4

End annual number: 4

PC1903 Unpaid annual fee