KR20020079725A

KR20020079725A - 경쟁-기반 예약을 갖는 다중 억세스 프로토콜들에서대역폭 할당을 위한 방법 및 디바이스

Info

Publication number: KR20020079725A
Application number: KR1020027002763A
Authority: KR
Inventors: 리웨이츄; 애비-내시프피래스
Original assignee: 모토로라 인코포레이티드
Priority date: 1999-09-01
Filing date: 2000-09-01
Publication date: 2002-10-19
Also published as: US6529520B1; WO2001017135A1; EP1214801A1; AU753949B2; CA2384129A1; CA2384129C; AU7110600A

Abstract

사용자 데이터의 전송을 위해 업스트림 대역폭을 예약하는데 사용되는 요청들의 경쟁-기반 전송을 위한 HFC 케이블 네트워크의 업스트림 채널에서 대역폭을 할당하는 문제점은 예약 요청들의 보급되는 제공된 로드에 동적으로 적응하는 할당 방법에 의해 해결된다. 한 실시예에서, 이는 각 프레임 내에서 데이터 전송을 위한 슬롯들의 수요 및 공급에 관련된 균형식에 대한 해에 기초하는 유동적 근사 방법을 사용하여 전반적인 가상 데이터 큐에서 사용자 데이터의 흐름 비율의 균형을 맞추도록 시도함으로서 각 업스트림 전송 프레임에서 경쟁 간격에 적절한 사이즈를 결정하여 행해진다.

Description

경쟁-기반 예약을 갖는 다중 억세스 프로토콜들에서 대역폭 할당을 위한 방법 및 디바이스{Method and device for bandwidth allocation in multiple access protocols with contention-based reservation}

통신 네트워크와 기술들은 효과적인 원격 정보 교환 및 고속 인터넷 억세스에 대한 현재와 미래의 요청을 만족시키도록 신속하게 발전되고 있다. 공유 매체 네트워크라 하는 일부 통신 네트워크에서는 다수 사용자 사이에서 전송 자원이 공유된다. 공유 매체 네트워크에서는 사용자가 스테이션(station)을 통해 독립적으로 네트워크를 억세스하고, 다른 스테이션으로부터의 비조정 전송이 서로 방해될 수 있다. 이러한 네트워크는 전형적으로 공유 채널 상에 전송하는 다수의 2차 스테이션과, 특히 공유 채널로의 2차 스테이션에 의한 억세스를 조정하도록 공유 채널의 공통 수신 단말부에 위치하는 하나의 1차 스테이션을 포함한다.

공유 채널에 대한 억세스를 조정하는데 사용되는 프로토콜은 때로MAC(Medium Access Control) 프로토콜이라 한다. MAC 프로토콜은 2가지 기본 카테고리들로 구분된다: 즉, 경쟁-기반 프로토콜 및 경쟁 없는 프로토콜이 그것이다. 경쟁-기반 프로토콜에서, 단말 사용자는 채널 자원을 억세스하기 위해 서로 경쟁한다. 충돌은 설계에 의해 피할 수 있는 것이 아니라, 재전송들이 랜덤하게 지연되도록 요구함으로써 제어되거나, 다른 다양한 경쟁 해결 전략을 사용하여 해결될 수 있다. 경쟁 없는 프로토콜에서, 단말 사용자는 충돌이 완전히 방지되도록 정적으로, 또는 적응적으로 전송이 제공되는 제어 방식으로 공유 채널에 억세스한다.

경쟁-기반 MAC 프로토콜의 한 예로는 알로하 프로토콜(Aloha protocol)이 공지되어 있다. 연속적인 시간으로 또는 비슬롯화된 시간으로 동작하는 원래의 버전은 비슬롯 알로하(Unslotted Aloha)라 한다. 비슬롯 알로하의 작용 및 성능은 널리 연구되었고, 그 최대 처리량(throughput)은 1/(2e)로 공지되어 있다. 이산적인 시간으로 또는 슬롯화된 시간으로 동작하는 나중 버전의 알로하 프로토콜은 슬롯 알로하(Slotted Aloha)라 한다. 원래의 슬롯 알로하 프로토콜로부터 많은 변형 및 확장이 유도되었다. 이 프로토콜과 대부분의 유도체에서, 각 슬롯에서의 새로운 전송의 확률과 재전송의 확률이 작으면, 슬롯에서의 처리량이 G(n)exp{-G(n)}으로 근사화될 수 있고, 여기서 G(n)는 제공된 로드 또는 시도 비율(offered load or attempt rate), 즉, 패킷 전송 기회 당 패킷 도착의 수(the number of packet arrivals per packet transmission opportunity)이고, 이는 소정의 시간 슬롯이 시작할 때 백로그(backlog)된 사용자들의 수를 나타내는 n의 함수이다. 따라서, 슬롯 알로하의 최대 처리량이 1/e = 0.368이나, 이는 G(n) = 1일 때, 즉 패킷 전송 기회당 1개의 패킷이 도착할 때 얻어진다. 상수 e는 자연로그의 밑이다. 값 1/e는 매 e개의 패킷 전송 기회 당 평균적으로 1개의 성공적인 패킷 전송이 이루어짐을 나타내므로 슬롯 알로하의 효율성을 반영함을 주목하여야 한다.

알로하 프로토콜을 포함하여 대부분의 경쟁-기반 프로토콜은 충돌과 관련된 사용자수에 대한 피드백(feedback) 정보를 사용하여 충돌을 해결한다. 이 피드백 정보에 기초하여, 백로그(backlog)된 사용자는 각각 프로토콜의 안정된 동작을 보상하도록 소정의 백오프(back off) 전략을 실행한다. 실제로, 사용되는 피드백 정보는 전형적으로 0, 1, 또는 그 이상의 전송을 나타내는 3진수이거나, 정확하게 1 전송 또는 그 외를 나타내는 2진수이다.

통상적인 슬롯 알로하는 불안정한 것으로 공지되어 있다. 슬롯 알로하를 안정화시키는 다양한 방법이 존재하고, 이들 모두는 하나 이상의 경쟁 처리 상태에 기초하여 백오프 구조의 적응적인 제어로 분류된다. 이들 상태의 실제값들이 관찰될 수 없을 때, 이들은 다양한 수단에 의해 추정된다. 슬롯 알로하의 안정성은 각 프레임이 시작할 때 백로그의 우선순위 기대값에 기초하여 동적 프레임 구조에 의해 제어될 수 있다. Rivest는 각 슬롯이 시작할 때 백로그 사용자의 수 n을 추정함으로서 1에 가까운 시도 비율 G(n)를 유지하는 의사-베이시언 알고리즘(Pseudo-Bayesian algorithm)을 제안하였다(Rivest, "베이시언 방송에 의한 네트워크 제어(Network Control by Bayesian Broadcast)", 논문 MIT/LCS/TM-287, MIT Lab. for Computer Science, 1985). 슬롯 알로하에서 채널 백로그를 추정하는 최소 평균-제곱 에러 예측기는 채널 백로그 추정의 회귀 함수에 따라 재전송 확률을 조절하도록 Thomopoulos에 의해 제안되었다(Thomopoulos, "슬롯 알로하, 예약 알로하, 및 LAN에 대한 간단한 다목적 분산 제어(A Simple and Versatile Decentralized Control for Slotted Aloha, Reservation Aloha, and Local Area Networks)", IEEE Trans. on Communications, vol.36, No.6, 1988년 6월).

시간 분할 다중 억세스(Time Division Multiple Access, TDMA) 구조와 같이 정적 스케줄링을 갖춘 경쟁 없는 다중 억세스 프로토콜에서는 소정의 전송 패턴이 주기적으로 반복된다. 사용자는 각각 지정된 시간 간격 동안에만 채널 자원을 억세스할 수 있다. 자원 할당에 대해 정적 스케줄링을 갖춘 경쟁 없는 프로토콜은 전형적으로 사용자 일부만이 임의의 시간에 활성적인 경우 많은 사용자를 지지하는데 비효과적이다. 적층적인 스케쥴링을 갖춘 경쟁 없는 다중 억세스 프로토콜에서는 예약을 통해 동적 트래픽(traffic) 요청을 수용하도록 전송 패턴이 각 사이클마다 수정될 수 있다. 예약 구조는 전형적으로 예약을 관리하는 중심 제어기를 요청한다. 채널 일부 또는 분리된 채널이 때로 예약으로 인한 오버헤드(overhead)를 지지하는데 사용된다.

요청 메시지의 경쟁-기반 전송을 갖춘 예약 프로토콜은 특히 긴 메시지를 갖는 많은 사용자가 있는 공유 매체 통신 시스템에서 적절한 것으로 공지되어 있다. 이는 다수의 케이블 모뎀에 부착된 양방향 동축 증폭기에 광학 섬유 노드를 통해 연결된 케이블 TV 헤드엔드(headend)를 갖춘 하이브리드 섬유 동축 케이블 네트워크(Hybrid Fiber Coaxial Cable Network)에서의 경우이다.

종래 기술에서는 채널이 고정 사이즈의 전송 슬롯 스트림(stream)으로 모델화된다. 채널은 프레임(frame)으로 나뉘고, 각 프레임의 전송 슬롯 수는 고정된다. 각 프레임은 경쟁 간격 및 데이터 간격으로 구성된다. 각 경쟁 간격은 슬롯 알로하 프로토콜에 따라 예약 패킷의 경쟁-기반 전송에 할당된 많은 경쟁 슬롯을 포함한다. 각 예약 패킷은 요청되는 데이터 슬롯의 수를 포함하여 적절한 제어 정보를 운반한다. 각 데이터 간격은 예약된 데이터 패킷의 전송에 할당된 다수의 데이터 슬롯을 포함한다. 전송 슬롯의 입도(granularity)에 의존하여, 경쟁 슬롯은 전송 슬롯의 분수배 또는 전송 슬롯의 정수배가 된다. 전형적으로, 전송 슬롯의 입도는 데이터 슬롯이 단일 전송 슬롯이거나 전송 슬롯의 정수배가 되도록 선택된다. 임의의 경우에서, 경쟁 슬롯은 전형적으로 데이터 슬롯 보다 훨씬 더 작다.

Szpankowski는 프레임-근거 및 경쟁-기반 예약 시스템을 지시하였고, 여기서는 슬롯 알로하가 예약 요청의 전송을 조정하는데 사용되고, 한 프레임에서 성공적인 각 예약 전송은 미리 프레임의 데이터 간격에 데이터 슬롯을 예약한다. Szpankowski의 지시에 따라, 각 프레임의 사이즈와 그 안의 두 간격이 각각 고정되면, 정상 상태의 시스템 처리량은 슬롯 알로하의 처리량인 각 프레임에서 똑같은 프레임의 경쟁 슬롯 수에 대한 데이터 슬롯수의 비율이 1/e일 때 최대화된다(Wojciech Szpankowski, "예약 다중억세스 시스템에서의 분석 및 안정성 고려(Analysis and Stability Considerations in a Reservation Multiaccess System)", IEEE Trans. Communications, Vol.COM-31, No.5, 1983년 5월). 다른 말로 하면, 한 프레임에 할당된 경쟁 슬롯의 수는 그 프레임에서 경쟁 슬롯수에 대한 할당 데이터 슬롯수의 비율이 1/e, 즉 슬롯 알로하의 효율성이 되어야 한다.

Dail 등은 통신 트래픽의 종류 또는 혼합(mix)의 함수로 시간 주기에 걸쳐 미니슬롯(mini-slot)(경쟁 슬롯에 대응하는)의 수를 동적으로 조정하는 헤드엔드에 대한 방법을 지시한다. 그러므로, 이 동적 할당은 요청 제공되는 로드를 변화시키도록 적응되지 않는다. 그러나, 동적 할당은 트래픽 혼합에 의존하고, 이는 경쟁-기반 예약을 요청하는 경쟁형 트래픽(예를 들면, 버스트 트래픽(bursty traffic)) 및 경쟁-기반 예약을 필요로 하지 않고 할당된 전송 기회인 예약형 트래픽(예를 들면, 등시성 트래픽(isochronous traffic))을 포함한다(J. Dail, C. Li, P. Magill, 및 K. Sriram, "공유 전송 매체를 위한 억세스 프로토콜에서 동적으로 조정 가능한 미니슬롯을 사용하여 증진된 처리량의 효율성을 가능하게 하는 방법 및 장치(Method and Apparatus Enabling Enhanced Throughput Efficiency by Use of Dynamically Adjustable Mini-Slots in Access Protocols for Shared Transmission Media)", 미국 특허 번호 5,953,344, 1999년 9월 14일). 특정하게, 그 방법은 고정된 사이즈의 데이터 슬롯을 갖는 프레임-기반 시스템을 고려하고, 여기서 각 프레임의 데이터 슬롯들은 경쟁형 트래픽 및 예약형 트래픽 간에 분할되어, 예약형 트래픽이 경쟁형 트래픽보다 우선순위를 갖는다. Dial 등의 방법에 따라, 각 프레임에서 예약형 데이터 패킷의 전송에 필요로 하는 데이터 슬롯의 수가 주어지면, 프레임의 나머지 데이터 슬롯의 수는 경쟁형 데이터 패킷뿐만 아니라 경쟁형 트래픽의 데이터 슬롯을 예약하는데 사용되는 경쟁-기반 요청 패킷을 전송하는데 할당된다. 요청 패킷은 전형적으로 데이터 패킷 보다 훨씬 더 작으므로, 요청 패킷의 전송에 사용되는 데이터 슬롯은 경쟁용을 위한 미니슬롯으로 변환된다. Dail 등의지시는 각 미니슬롯이 슬롯 ALOHA 시스템과 같은 효율성으로 경쟁 요청을 해결한다는, 즉 각 미니슬롯이 1/e의 처리량 효율성을 갖는다는 가정에 기초하여 한다. 실질적인 이유로, Dail 등은 또한 이 효율성이 약 90% 정도 하향 스케일 조정되어 약 1/3이 된다고 가정한다. 특정하게, Dail 등은 프레임의 경쟁 간격에 있는 미니슬롯의 수에 대한 프레임에서 할당된 데이터 슬롯인 경쟁형 메시지의 평균수의 비율이 1/3이 되도록 한 프레임에 할당된 경쟁 미니슬롯의 수가 정해져야 한다고 지시한다. Dail 등의 방법은 각 경쟁형 메시지에 예약될 수 있는 데이터 슬롯의 수가 소정의 평균값을 갖는 랜덤수가 되도록 허용한다. Dail 등의 방법은 기본적으로 상술된 바와 같은 Szpankowski의 방법의 직접적인 확장임을 주목하여야 한다.

Golmie 등은 Dail 등의 방법을 약간 변형한 것을 고려하였다(N. Golmie, "IEEE 802.14 네트워크에 대한 경쟁 해결 알고리즘의 개요(A Review of Contention Resolution Algorithms for IEEE 802.14 Networks)", IEEE Communication Surveys, 1999년). 유사하게, Golmie 등의 방법은 그들의 접근법에서 요청 제공된 로드에 동적으로 의존하지 않고 트래픽 혼합에 의존하므로, 프레임의 경쟁 간격에 있는 미니슬롯의 수에 대한 프레임의 할당 데이터 슬롯인 경쟁형 메시지의 평균수의 비율이 1/3 대신에 1/2이고, 할당이 진행중인 데이터 슬롯의 수가 프레임에 남아있는 데이터 슬롯수의 2.5배를 넘는다. Dail 등의 방법과 유사하게, Golmie 등의 방법은 경쟁형 트래픽의 변화되는 요청 제공된 로드에 초점을 맞추지 않고, 예약형 트래픽의 변화되는 데이터 제공된 로드에 초점을 맞춘다.

프레임-기반 시스템에서, 경쟁-기반 예약 시스템의 각 프레임은 최소 프레임사이즈에 의해 때로 제한된다. 일부 경우에서는 이 제한이 시스템내의 최대 왕복 지연으로 인하고, 최대 왕복 지연 보다 더 큰 최소 프레임 사이즈로, 프레임에서 요청 메시지를 전송했던 모든 사용자들이 필요한 경우 다음 프레임의 경쟁 간격에서 재전송하도록 시간 내에 피드백을 수신할 수 있다. 다른 경우에는 제한이 헤드엔드에서의 처리 용량에 대한 제한 때문이므로, 최대 프레임 스케줄링 주파수를 나타낸다.

최고 사이즈의 프레임에서 이용 가능한 슬롯을 사용하기에 충분한 데이터가 없을 때는 여분 슬롯이 있을 수 있다. 또한, 프레임을 완전하게 패키지화하기 위해 패킷이 분할되도록 허용하지 않는 경우에도 여분 슬롯이 있을 수 있다. 데이터 전송에 사용될 수 없는 여분 슬롯이 있을 때, 이들은 다른 목적에 사용될 수 있다. 예를 들면, 한 프레임내의 여분 슬롯은 요청 메시지의 경쟁-기반 전송을 위해 그 프레임의 경쟁 간격에 포함될 수 있다.

헤드엔드가 슬롯에 기초하여 한 슬롯에서 스케쥴링을 처리할 수 있으면, 슬롯화된 공유 매체 네트워크에서의 대역폭 할당은 프레임에 기초할 필요가 없음을 주목하여야 한다. 그러나, 하이브리드 섬유 동축 케이블 네트워크에서는 정보가 DOCSIS 프로토콜에 따라 프레임별로 전송된다. Sala 등은 무프레임 MAC 프로토콜(frameless MAC protocol)에 기초하는 슬롯-기반 시스템을 지시하고, 여기서는 경쟁 기회가 경쟁 억세스에 대한 추정 요청을 수용하도록 경쟁 슬롯을 할당하는 소정의 경쟁 슬롯 할당자에 기초하여, 필요에 따라 연속적으로 삽입된다(Dolors Sala, John O. Limb, 및 Sunil U. Khaunte, "케이블 모뎀 MAC 프로토콜에 대한 적응적 제어 메커니즘(Adaptive Control Mechanism for Cable Modem MAC Protocols)", Proceedings of IEEE INFOCOM'98, 1998년 3월 29일 - 4월 2일). 그 방법은 데이터 전송에 사용되고 있지 않는 모든 경쟁-기반 예약 슬롯을 할당하는 전략에 따른다. 데이터 슬롯 당 할당된 경쟁 기회의 수는 정상 상태 경쟁 처리량을 최대화함으로서 유도된다.

Sala 등의 지시에 따라, 네트워크에 무시할만한 왕복 지연이 있을 때, 경쟁 기회는 성공적인 요청 전송이 있을 때까지 계속하여 할당되고, 성공적인 각 요청 전송은 데이터 패킷의 전송으로 이어진다. 0이 아닌 왕복 지연은 요청이 성공적으로 전송되는 시간으로부터 대응하는 예약 데이터 슬롯이 할당되는 시간까지 추가 경쟁 기회가 할당되는 방법의 효율성을 낮춘다. 낮은 데이터 로드에서는 경쟁 예약에 사용될 수 있는 비사용 대역폭이 많이 있으므로, 안정된 동작에 요청되는 수 보다 더 많은 경쟁 기회가 할당된다. 경쟁 기회의 여분은 충돌 확률을 매우 낮은 레벨로 감소시키므로, 경쟁 억세스 지연을 감소시킨다. 데이터 로드가 증가됨에 따라, 그 방법은 데이터 슬롯 당 e(약 2.7183)회의 경쟁 기회 평균치를 할당하도록 수렴된다.

상기 종래 기술은 경쟁 기회 보다 예약 데이터 슬롯에 우선순위를 제공한다. 모든 예약 데이터 슬롯이 할당되지 않으면, 경쟁 기회는 할당되지 않는다. 이 방법은 데이터 제공된 로드가 높을 때 높은 경쟁 억세스를 제공할 수 있다. Sala 등은 경쟁 슬롯 할당자의 성능을 개선하는 방법을 제공하고, 여기서는 동적으로 결정된 경쟁 기회의 수가 비예약 경쟁 기회에 부가하여 데이터 슬롯 사이에 주어진다.주어진 경쟁 기회의 수는 슬롯 알로하 모델에 따라 경쟁 처리량을 최대화하는데 요청되는 경쟁 기회수의 근사치에 기초하고, 여기서 데이터 메시지 당 패킷의 평균수와 주어진 경쟁 기회의 수의 곱은 e와 같다. Sala 등의 지시는 확장된 시간 주기 내에 전송될 수 있는 데이터 메시지의 수가 똑같은 주기 내에서 주어지는 경쟁 기회에서 성공적인 요청 전송의 기대 수와 같도록 그 시간 주기에서 주어지는 경쟁 기회의 수가 정해져야 한다는 면에서 Szpankowski의 지시와 똑같은 의도에 따름을 주목하여야 하고, 소정의 주기에서 주어지는 경쟁 기회의 성공적인 요청 전송의 기대 수는 주기내의 경쟁 기회의 수와 1/e, 즉 슬롯 알로하의 효율의 곱으로 주어진다.

피기백킹(piggybacking)이라 공지된 메커니즘은 때로 시스템이 높은 데이터 로드로 동작하고 있을 때 경쟁 제공된 로드를 감소시키는데 사용된다. 피기백킹으로, 경쟁 억세스를 다른 방법으로 요청하는 요청이 부가 데이터 전송 슬롯을 예약하도록 데이터 패킷에 삽입될 수 있다. 이에 대해서는 감소된 경쟁 오버헤드로 인하여, 업스트림(upstream) 대역폭 사용이 보다 효과적이다. 피기백킹이 있을 때, 주어지는 경쟁 기회의 수는 피키백킹 로드를 설명하는 인자만큼 하향 스케일 조정된다.

상기의 모든 고정된 프레임 시스템에서는 요청 제공된 로드를 변경시키거나 다르게 하는 것을 고려하지 않는다. 요청 제공된 로드를 동적으로 고려하지 않으면, 경쟁 억세스 지연, 데이터 스케줄링 지연, 및 그들 사이의 교환을 포함하여, 특정한 성능 목적에 대해 최적화되도록 동적으로 대역폭을 할당할 수 없다. 경쟁억세스 지연은 데이터 패킷의 전송을 위해 미니슬롯을 예약하는 요청이 발생되는 시간으로부터 요청이 성공적으로 전송되어 헤드엔드에 의해 수용될 때까지의 시간이다. 데이터 스케줄링 지연은 요청이 헤드엔드에 의해 수용되는 시간으로부터 데이터 패킷이 채널에서 완전히 전송될 때까지의 지연이다.

Tasaka 및 Ishibashi는 경쟁-기반 예약 프로토콜의 성능 및 안정성 조건을 연구하였다(S. Tasaka 및 Y. Ishibashi, "위성 패킷 통신을 위한 예약 프로토콜 - 성능 분석 및 안정성 고려(A Reservation Protocol for Satellite Packet Communication - A Performance Analysis and Stability Considerations)", IEEE Trans. Communications, Vol. COM-32, No. 8, 1984년 9월). 이들은 주어진 제공된 로드에서 시스템의 안정된 동작을 위한 시스템 매개변수의 최적 세트를 결정하는 과정을 고안하여, 평균 메시지 지연이 최소화되고, 여기서 시스템 매개변수의 세트는 경쟁 간격 및 데이터 간격에서 전송 슬롯의 수를 포함한다. 주어진 제공된 로드에서, 그 과정은 경쟁 간격 및 데이터 간격내의 전송 슬롯수의 각 조합에 대해 평균 메시지 지연이 최소화되도록 각 프레임에서의 재전송 확률을 결정한다. 이 단계는 평균 메시지 지연의 전반적인 최소치가 결정될 수 있을 때까지, 경쟁 간격 및 데이터 간격내의 전송 슬롯수의 충분히 많은 조합에 대해 반복된다. 이 방법은 계산적으로 포함됨을 주목하여야 하고, 평균적인 메시지 지연의 전반적인 최소치가 실제 구해질 때를 아는 방법은 명확하지 않다.

한 공유 매체 네트워크에 대해, 경쟁-기반 예약을 갖춘 다중 억세스 프로토콜은 하이브리드 섬유-동축(Hybrid Fiber-Coaxial, HFC) 케이블 네트워크의 업스트림 채널에서 대역폭 할당에 적용될 수 있다. 때로 헤드엔드라 하는 케이블 네트워크내의 1차 스테이션은 기본적으로, 때로 케이블 모뎀이라 하는, 2차 스테이션의 그룹에 업스트림 대역폭을 할당하는 중심 제어기이다. 이는 MAP라 공지된 정보 소자를 포함하는 제어 메시지를 다운스트림 전송함으로서 이루어진다. 각 MAP는 업스트림 채널에서 인접한 슬롯의 그룹으로 구성된 전송 프레임에서 전송 기회의 할당을 지정한다. 각 프레임은 데이터를 전송하도록 경쟁-기반 예약을 위한 경쟁 간격 및 데이터 간격으로 분할된다. 전달할 데이터를 갖는 2차 스테이션은 미리 프레임의 데이터 간격에 전송 기회를 예약하도록 경쟁 간격에 요청을 전송한다. 경쟁 결과는 슬롯 당 발생된 요청 수에 대한 요청 제공된 로드에 의존한다. 경쟁 간격내의 각 전송 기회는 그에 전송될 요청이 없는 상태(Idle), 그에 전송되는 요청이 하나 있는 상태(Success), 또는 그에 전송되는 요청이 다수 있는 상태(Collision)로 종료될 수 있다. 헤드엔드는 미래 MAP에서의 긍정적인 승인을 성공적인 요청 전송으로 각 사용자에게 제공한다. 2차 스테이션으로부터의 요청을 성공적으로 전송하면, 그 2차 스테이션을 위해 미래 프레임에 데이터 전송 기회가 예약된다. 소정의 시간 이후에 미래 MAP에 요청 전송이 승인되지 않은 2차 스테이션은 요청을 전송하기 이전에 일부 시간 동안 백오프하도록 요청된다. 충돌 해결에 사용되는 전형적인 과정은 이진수 지수 백오프로 종결 지워지고, 백오프 윈도우(backoff window)는 랜덤 백오프의 범위를 제안하고, 초기 백오프 윈도우는 재전송을 위한 이어지는 시도에서 2배로 된다. 이진수 지수 백오프 접근법이 과중한 로드에서 불안정성을 일으키게 되므로, 요청에 대한 최대 재전송 회수는 그렇지않은 경우의 불확정 백오프를 종결시키도록 부여된다.

이해되는 바와 같이, 슬롯 공유 매체 통신 네트워크에 사용되는 경쟁-기반 예약 프로토콜에서 변화하는 요청 제공된 로드에 적응하도록 동적으로 대역폭을 할당하는 간단한 방법 및 디바이스에 대한 필요성이 남아있고, 여기서는 전송 슬롯이 프레임별로 할당된다. 상기에 기술된 바와 같이, 프레임-기반 시스템은 DOCSIS 프로토콜에 의해 지정되고, 경쟁 억세스 지연 및 데이터 스케줄링 지연으로 구성된 전체적인 메시지 지연을 최소화하면서, HFC 케이블 네트워크의 업스트림 채널에서 대역폭을 효과적으로 할당하는 것이 바람직하다.

본 발명은 일반적으로 통신 시스템에 관한 것으로, 보다 특정하게 채널 억세스를 조정하는 경쟁-기반 예약 메커니즘(contention-based reservation mechanism)을 사용하는 공유 매체 통신 네트워크에서 대역폭 할당에 대한 스케줄링에 관한 것이다.

도 1은 헤드엔드(headend) 시스템에 데이터를 전송하도록 탐색하는 다수의 케이블 모뎀에 연결된 케이블 TV 헤드엔드 시스템을 설명하는 하이브리드 섬유-동축 케이블 네트워크(Hybrid Fiber-Coaxial Cable Network)를 도시하는 도면.

도 2는 대역폭 예약에 대한 요청이 경쟁 모드로 전달되고, 대역폭이 경쟁 충돌을 해결하는 것에 기초하여 부여되는 경쟁 기반 예약 시스템을 도시하는 도면.

도 3은 본 발명에 따른 전송 프레임 구조를 도시하는 도면.

도 4는 본 발명에 따른 경쟁 억세스를 위한 안정 및 불안정 영역을 도시하는 도면.

도 5는 데이터 전송을 위한 슬롯들의 수요를 도시하는 도면.

도 6은 데이터 전송을 위한 슬롯들의 공급을 도시하는 도면.

도 7은 균형 해와 그 선형 문턱값들을 도시하는 도면.

도 8은 고정된 할당을 도시하는 도면.

도 9는 경쟁 슬롯들에 대한 임시적인 할당이 직선 함수인 본 발명의 제1 실시예를 도시하는 도면.

도 10은 경쟁 슬롯들에 대한 임시적인 할당이 2-세그먼트 선형 함수에 기초하는 본 발명의 제2 실시예를 도시하는 도면.

도 11은 경쟁 슬롯들에 대한 임시적인 할당이 공급 및 수요를 전체적으로 고려하는 3-세그먼트 선형 근사치에 기초하는 본 발명의 제3 실시예를 도시하는 도면.

도 12는 한정된 프레임 사이즈가 가해진 제2 실시예를 도시하는 도면.

도 13은 한정된 프레임 사이즈가 가해진 제3 실시예를 도시하는 도면.

도 14는 요청 제공된 로드에 기초하는 경쟁 스케줄링(scheduling)을 설명하는 흐름도.

도 15는 경쟁 간격 사이즈를 결정하는 방법을 설명하는 흐름도.

도 16은 오버로드(overload) 조건에 대한 문턱값을 결정하는 방법을 설명하는 흐름도.

도 17은 데이터 전송을 위한 슬롯들의 공급을 추정하는 방법을 설명하는 흐름도.

도 18은 데이터 전송을 위한 슬롯들의 수요를 추정하는 방법을 설명하는 흐름도.

도 19는 공급이 수요와 같아지도록 경쟁 간격 사이즈를 추정하는 방법을 설명하는 흐름도.

도 20은 임시적인 할당을 사용하여 경쟁 스케쥴링을 설명하는 흐름도.

도 21은 경쟁 간격 사이즈를 결정하는 제1 방법을 설명하는 흐름도.

도 22는 임시적인 경쟁 간격 사이즈를 결정하는 제2 방법을 설명하는 흐름도.

도 23은 임시적인 경쟁 간격 사이즈를 결정하는 제3 방법을 설명하는 흐름도.

도 24는 경쟁 처리량을 최대화하는 경쟁 간격 사이즈를 추정하는 방법을 설명하는 흐름도.

도 25는 비오버로드(non-overload) 영역에서 경쟁 처리량을 최대화하는데 필요한 경쟁 간격 사이즈를 결정하는 방법을 설명하는 흐름도.

도 26은 균형식에 대한 해에서 선형 하한값을 결정하는 방법을 설명하는 흐름도.

프레임(frame)-근거 및 경쟁(contention)-기반 예약 시스템인 주된 시스템에서는 각 프레임에서 경쟁 및 데이터에 할당된 슬롯(slot) 사이의 분할 선이 요청 제공된 로드뿐만 아니라 데이터 제공된 로드를 고려하여 확실시된다. 요청 제공된 로드는 슬롯 당 발생되는 요청의 수를 의미한다. 데이터 제공된 로드는 성공적으로 전송된 각 요청에 의해 예약된 슬롯의 수에 반영된다.

본 발명에 따라, 많은 사용자는 반정적(quasi-static)인 제공된 로드를 갖는 요청을 집합적이고 랜덤하게 발생한다. 즉, 요청 제공된 로드는 시간에 따라 느리게 변할 수 있다. 프레임-근거 경쟁-기반 예약 시스템의 동작시, 요청이 소정의 프레임에서 발생될 때, 이는 전송 자격이 주어지기 이전에 다음 프레임까지 대기하여야 한다. 소정의 프레임에서의 요청 제공된 로드는 다음 프레임의 경쟁 간격에서 유효한 요청 제공된 로드로 해석됨을 주목하여야 한다. 요청 제공된 로드는Abi-Nassif 등에 의한 종래 기술에서 제안된 바와 같이 연역적으로 공지되거나 추정될 수 있다(F. Abi-Nassif, W.C. Lee 및 I. Stavrakakis, "다중매체 케이블 네트워크 시스템에서 제공된 로드 추정(Offered Load Estimation in a Multimedia Cable Network System)", IEEE ICC'99, Vancouver, 1999년 6월 6-10일).

요청 제공된 로드가 정적으로 취해지는 종료 프레임-기반 시스템과 다르게, 주된 시스템에서의 요청 제공된 로드의 동적 특성은 경쟁 및 데이터 간격에 할당된 슬롯의 수를 결정한다. 그래서, 이 시스템은 경쟁 억세스 지연, 데이터 스케줄링(scheduling) 지연, 및 그들 사이의 교환을 포함하여 특정한 성능 목적에 대해 최적화되도록 각 프레임에서 경쟁 및 데이터에 대한 슬롯의 수를 할당한다.

주된 시스템이 가능하게 다른 사이즈를 갖는 각 프레임을 고려하더라도, 프레임 사이즈가 고정될 때 명확하게 적용 가능한 것으로 생각된다. 본 발명의 한 실시예에서, 시스템은 경쟁 처리량을 최대화하도록 각 프레임에서 경쟁 및 데이터에 대한 슬롯 수를 할당할 때 변화하는 요청 제공된 로드를 고려한다. 이러한 할당은 경쟁-기반 예약 시스템이 불안정해질 기회를 최소화하는 것으로, 즉 경쟁에 할당된 슬롯의 수가 모든 백로그(backlog) 요청에 서비스를 제공하기에 시간적으로 충분하지 않은 것으로 생각되고, 그에 의해 시스템은 한정된 경쟁 억세스 지연으로 동작할 수 있다.

또 다른 실시예에서, 시스템은 오버로드될 때, 즉 과도한 요청 제공된 로드가 있을 때 경쟁 처리량을 최대화하도록 각 프레임에서 경쟁 및 데이터에 대한 슬롯의 수를 할당하고, 그렇지 않은 경우에는 경쟁에 대해 고정된 최소수의 슬롯을보장한다. 이러한 할당은 경쟁-기반 예약 시스템이 불안정해질 기회를 최소화할 뿐만 아니라, 시스템이 오버로드되지 않을 때 데이터 스케줄링 지연을 최소로 소비하여 경쟁 억세스 지연을 낮추는 것으로 생각된다.

또 다른 실시예에서, 시스템은 시스템이 오버로드될 때 경쟁 처리량을 최대화하도록 각 프레임에서 경쟁 및 데이터에 대한 슬롯의 수를 할당하고, 그렇지 않은 경우에는 데이터 전송에 대한 슬롯의 공급과 수요의 균형을 맞추고, 여기서 수요는 요청 제공된 로드 및 데이터 제공된 로드의 함수이다. 이러한 할당은 경쟁-기반 예약 시스템이 불안정해질 기회를 최소화할 뿐만 아니라, 시스템이 오버로드되지 않을 때 데이터 스케줄링 지연이 한정되는 것을 보장하면서 경쟁 억세스 지연을 최소화하는 것으로 생각된다.

상기의 모든 실시예는 변화하는 요청 제공된 로드를 고려한다. 주된 시스템은 초기에 경쟁 간격에서 임시적인 할당을 이루어, 할당이 경쟁 처리량을 최대화하는 할당에 의해 아래로부터 한정되게 한다. 데이터 전송을 위해 나머지 슬롯을 할당한 이후 그 프레임에 나머지 슬롯이 있으면, 나머지 슬롯은 프레임의 경쟁 간격에 포함된다. 진행중인 할당에서 프레임의 나머지 부분을 채우기에 충분한 예약 슬롯이 없거나, 프레임의 나머지 부분에서 데이터 슬롯이 완벽하게 맞추어지지 않을 수 있기 때문에, 나머지 슬롯이 있다.

제2 및 제3 실시예는 또한 성공적으로 전송된 요청 당 예약된 슬롯의 평균수뿐만 아니라, 사용자 데이터 흐름 사이에서 데이터 간격에 슬롯을 할당하는데 사용되는 데이터 스케줄러(scheduler)의 이용을 바라는 것도 고려한다. 성공적으로 전송된 요청 당 예약된 슬롯의 수는 시스템에서 데이터 제공된 로드를 반영하고, 데이터 스케줄러의 이용을 바라는 것은 소정의 데이터 스케줄러에 대한 데이터 스케줄링 지연에서 상한값을 나타내는 것으로 생각된다. 본 발명은 특정한 데이터 스케줄러 설계에 의존하지 않고, 데이터 스케줄러의 이용을 바라는 것에 의존하는 것으로 생각된다. 일반적으로, 데이터 스케줄링 지연은 데이터 스케줄러의 이용과 함께 증가되고, 전형적으로 이용이 1에 접근함에 따라 경계 없이 증가된다. 실제로, 데이터 스케줄러의 이용은 1에 가까운 값으로 설정되지만, 데이터 스케줄링 지연이 원하는 바에 따라 한정될 수 있도록 충분한 여분을 남겨둔다.

주된 시스템은 수요가 요청 제공된 로드에 의존하는 공급 및 수요 모델을 사용한다. 이 시스템에서, 각 업스트림 전송 프레임의 경쟁 간격에 대해 최적화된 사이즈는 전반적인 가상 데이터 큐(queue)에서 사용자 데이터의 흐름 비율의 균형을 맞추도록 시도함으로서 결정되고, 슬롯의 수요 및 공급에 관련되는 균형식에 대한 해법에 기초하는 유동적인 근사 방법이 사용된다. 정상적인 비오버로드 시스템에서는 시스템이 초기에 경쟁 간격에서 임시 할당을 이루어, 할당이 균형식에 대한 해결법으로 상기로부터 한정된다. 시스템이 과도 현상의 오버로드를 겪을 때마다, 주된 시스템은 경쟁 처리량을 최대화하도록 경쟁 간격에 슬롯을 할당한다. 임의의 경우에, 데이터를 전송하도록 나머지 슬롯을 할당한 이후 프레임에 여분 슬롯이 있으면, 여분 슬롯은 프레임의 경쟁 간격에 포함된다.

요약하여, 사용자 데이터를 전송하도록 업스트림 대역폭을 예약하는데 사용되는 요청의 경쟁-기반 전송을 위한 HFC 케이블 네트워크의 업스트림 채널에서 대역폭을 할당하는 문제점은 예약 요청의 전반적인 제공된 로드에 동적으로 적응하는 할당 방법에 의해 해결된다. 바람직한 실시예에서, 이는 각 프레임 내에서 데이터 전송을 위한 슬롯의 수요 및 공급에 관련되는 균형식에 대한 해결법에 기초하는 유동적인 근사 방법을 사용하여 전반적인 가상 데이터 대역에서 사용자 데이터의 흐름 비율의 균형을 맞추도록 시도함으로서 각 업스트림 전송 프레임에서 경쟁 간격에 대해 적절한 사이즈를 결정하여 이루어진다.

주된 시스템은 경쟁-기반 예약을 포함하는 다중 억세스 프로토콜을 포함하는 임의의 시스템에서 사용될 수 있지만, 주된 응용 중 하나는 HFC 케이블 네트워크에 있다. 도 1을 참고로 한 예를 통해, HFC 케이블 네트워크(10)는 섬유 광학 케이블(14)을 거쳐 광학 섬유 노드(1) 및 동축 케이블(18)을 통해 다수의 케이블 모뎀(22)이 부착된 양방향 동축 증폭기(20)에 연결되는 케이블 TV 헤드엔드(headend) 시스템(12)을 갖는다. 방송 매체인 다운스트림(downstream) 방향은 화살표(24)로 나타내지는 반면, (26)으로 나타내지는 업스트림(upstream) 방향은 공유 매체이다. 케이블 TV 헤드엔드 시스템(12)은 케이블 모뎀 단말 시스템또는 CMTS(cable modem termication system)을 갖는다.

주된 시스템의 목적은 케이블 TV 헤드엔드 시스템에 데이터를 전송하는 전송 기회에 대해 경쟁하는 케이블 모뎀의 업스트림 채널에서 통신의 지연을 최소화하는 것으로 생각된다. 문제점은 각 케이블 모뎀이 헤드엔드와 통신하게 허용하도록 업스트림 방향에서 대역폭을 할당하는 것이다.

도 2는 일반적인 경쟁-기반 예약 시스템에서 사용자 또는 케이블 모뎀의 가능한 상태 및 상태들 사이의 전송에 대한 조건을 설명하는 상태도이다. 특정한 모뎀의 아이들(Idle) 상태(20)가 있고, 이는 모뎀이 전송할 데이터를 가지고 있지 않음을 의미한다. 데이터가 전송되어야 할 때, 모뎀의 데이터 큐(data queue)가 채워지므로 비워지지 않는다(32). 아이들 모뎀은 빈 데이터 큐에 새로운 것이 도착할 때 백로그(backlog)된다. 이를 반영하기 위해, 모뎀은 백로그 상태(34)로 이동되어, 데이터 전송을 위해 업스트림 대역폭을 예약하는 요청을 전송하는 경쟁 기회를 대기한다. 경쟁 기회가 이용 가능할 때(36), 모뎀은 경쟁 상태(38)로 이동되고, 경쟁 모드에서 요청을 전송한다.

전송된 요청이 다른 활성 모뎀으로부터의 동시 요청 전송으로 인해 충돌되면(48), 모뎀은 백오프(backoff) 상태(50)로 이동되어, 소정의 경쟁 해결 과정이 실시된다. 적절한 백오프 시간 이후에, 모뎀은 경쟁 기회가 도착하면 요청을 재전송할 수 있다(51). 시스템이 오버로드되면(52), 모뎀은 현재 요청을 포기하여 종료하고, 다시 백로그 상태(34)로 이동되어, 다음 경쟁 기회가 이용 가능할 때(34) 새로운 요청을 전송한다. 모뎀이 경쟁 상태(38)에 있을 때 요청의 전송을성공하면, 즉 예약이 헤드엔드에 의해 수용된 것으로 생각되면(40), 모뎀은 수여 진행(Grant Pending) 상태(42)로 이동되어 백로그 데이터에 대한 전송 기회를 대기한다. 이 상태에서, 타임아웃 주기 이후에 기대되는 수여가 수신되지 않으면(60), 모뎀은 이어서 백로그 상태(34)를 통해 경쟁을 재입력할 수 있다.

수여 진행 상태(42)에서, 데이터 전송 기회가 수신될 때(44), 모뎀은 전송 상태(46)로 이동된다. 전송 상태(46)에서, 할당된 대역폭이 충분하여 모뎀의 큐가 비워지면(54), 모뎀은 아이들 상태(30)로 복귀된다. 마지막으로 아이들 상태(30)에 남은 이래로 모뎀의 큐에 새로운 것이 도착하면, 즉 그 큐가 비워있지 않은 상태로 남아 있으면, 모뎀은 이어서 백로그 상태(34)를 통해 경쟁을 재입력할 수 있다. 최근 전송 기회가 부분적인 수여이거나(58), 새로운 요청이 피기백킹(piggybacking)으로 인해 진행 중이면(58), 모뎀의 대역폭에 대한 요청이 다시 경쟁을 통과할 필요가 없으므로, 모뎀은 수여 진행 상태로 복귀되어(42) 새로운 수여를 대기한다.

백로그 상태에서, 모뎀이 경쟁-기반 예약을 통해 데이터 전송을 위한 업스트림 대역폭을 예약하도록 시도하는데 너무 오래 대기하면, 모뎀은 큐의 데이터가 진부해지기 때문에, (61)에서 설명된 바와 같이, 두드러지는 요청을 중단하여 없애도록 결정할 수 있다.

보다 특정하게, HFC(Hybrid Fiber Coaxial)에서, 케이블 네트워크는 다수의 브랜치(branch)를 통해 다수의 케이블 모뎀이 부착된 양방향 동축 증폭기에 광학 섬유 노드를 통하여 연결된 케이블 TV 헤더엔드를 갖는다. 해결될 문제점은 각 케이블 모뎀이 적어도 전체적인 지연으로 헤드엔드와 통신하게 허용하도록 업스트림 방향에서 대역폭을 할당하는 것이다. 이 방법은 각 프레임의 경쟁 간격 및 데이터 간격에서 슬롯을 할당하는 구조를 사용하는 경쟁-기반 예약 시스템을 통해 이루어지고, 그 구조는 요청 제공된 로드의 함수이다.

케이블 모뎀의 관점으로부터 주된 시스템에서는 케이블 모뎀이 전송될 데이터를 가질 때 케이블 모뎀에서의 큐가 채워지므로 비워지지 않는다. 비워지지 않는 큐가 있다는 사실은 백로그를 나타내고, 사용자 또는 케이블 모뎀이 경쟁 기회를 대기하는 백로그 상태로 기록된다. 경쟁 기회는 경쟁 모드에서 요청을 전달하는 기회이다.

다수의 케이블 모뎀이 헤드엔드 시스템과 통신하려고 시도하면, 요청의 충돌이 있고, 여기서 충돌은 예약이 수용될 수 있기 이전에 해결되어야 하는 것으로 생각된다. 충돌이 있으면, 충돌이 있다는 사실로, 요청이 재전달될 수 있을 때까지 소정의 경쟁 해결 알고리즘에 따라 일정 시간량 동안 백오프된다. 요청은 경쟁 기회가 있는 것으로 나타내질 때 재전달될 수 있다.

한 실시예에서는 백오프가 랜덤한 양만큼 뒤로 미루어지는 랜덤 처리임을 주목하여야 한다. 경쟁 해결은 상술된 종결 이진수 지수 백오프 알고리즘(truncated binary exponential backoff algorithm)에 기초하는 것으로 생각된다. 그럼에도 불구하고, 다른 경쟁 해결 알고리즘이 또한 사용될 수 있다.

지시 알고리즘에 따라 요청이 이루어지므로, 이는 경쟁 간격의 한 슬롯 동안이다. 요청은 이어서 다른 요청과 경쟁하고, 일정 시간에 요청이 수용될 수 있다.예약 수여는 헤드엔드 시스템이 케이블 모뎀에 다시 통신되어 데이터 전송이 일어나는 전송 기회를 할당하므로 이러한 시간에 의존한다.

전송될 데이터가 없으면, 케이블 모뎀에서 큐가 비워지는 상태가 주어지게 된다.

케이블 모뎀이 아이들 상태에 남아있어 큐가 비워있지 않음을 나타낸 이후에, 추가 데이터가 케이블 모뎀에 도착하는 경우가 있을 수 있다. 이 추가 데이터는 앞서 요청되지 않았던 추가 대역폭을 요청하게 된다. 그러므로, 그 처리는 필요한 추가 대역폭을 수용하여야 한다.

세 번째로, 헤드엔드 시스템이 부분적으로 대역폭을 수여할 가능성이 있다. 이 사실은 전송시 알려지고, 더 많은 대역폭에 대한 요청이 경쟁 사이클을 통과할 필요가 없다.

DOCSIS 프로토콜은 또한 추가 대역폭의 요청에 대한 피기백킹을 허용하여, 요청이 경쟁 사이클을 통과할 필요가 없다.

부분적인 수여 또는 피기백킹 시나리오에 대해서는 하나가 단순하게 수여 진행 상태로 전해져 다음 전송 기회를 대기한다.

상술된 바와 같이, 헤드엔드 예상 대역폭은 할당 맵(allocation map)이고, 그 맵은 누가 언제 전송하는가를 나타낸다. 이는 업스트림 프레임에서 전송 기회를 할당함으로서 이루어진다. 각 프레임은 경쟁 간격 및 데이터 간격을 포함한다.

문제는 업스트림 대역폭을 동적으로 할당하는 방법이다. 요청 제공된 로드, 평균적인 메시지 사이즈, 피기백 로드, 및 다른 인자들이 주어지면, 시스템은 요청및 데이터 전송을 위한 할당 대역폭을 결정하여야 한다. 본 발명은 경쟁 억세스 지연, 데이터 스케줄링(scheduling) 지연, 및 그들 사이의 교환을 포함하여, 특정한 성능 목적에 대해 최적화되도록 대역폭 할당을 동적으로 결정한다. 경쟁 억세스 지연 및 데이터 스케줄링 지연은 2가지 성분의 전체적인 채널 억세스 지연으로, 두 구성성분 지연 사이의 적절한 교환을 선택하여 최소화될 수 있다.

상술된 바와 같이, 정상적인 동작 하에서, 본 발명은 데이터 스케줄링 지연에 소정의 상한값을 가하여 경쟁 간격에서의 할당을 최대화함으로서 경쟁 억세스 지연을 최소화하고, 상한값은 데이터 스케줄러의 소정의 사용에 의해 나타내진다.

또한, 상술된 바와 같이, 시스템에 과도 현상의 오버로드가 가해질 때, 본 발명은 보급되는 요청 제공된 로드에 따라 경쟁 처리량을 최대화할 필요가 있는 최소 할당에 가해진 데이터 간격에서의 할당을 최대화함으로서 경계 지워진 경쟁 억세스 지연을 유지하면서 데이터 스케줄링 지연을 최소화하므로, 시스템의 불안정성이 방지될 수 있다.

프레임-근거 경쟁-기반 예약 시스템에서, 각 프레임은 다수의 슬롯으로 구성되고, 이는 데이터 및 경쟁에 대한 2개의 간격으로 나뉜다. 상술된 Szpankowski 시스템은 특정한 제공된 로드에 대해서만 최적화되고 변화되는 제공된 로드를 고려하지 않은 것으로 생각된다. Dail 등의 시스템에서는 시스템이 예약형 트래픽에 대해 여분을 만들어 경쟁형 트래픽 및 예약형 트래픽 모두를 수용한다. 가변 제공된 로드로 예약형 트래픽에 여분을 만드는 순효과는 각 프레임에서 요청 경쟁 및 경쟁형 트래픽에 이용 가능한 슬롯의 수가 감소되어 프레임마다 변할 수 있다는 것이다. Golmie 등의 방법에 대해서는 프레임의 경쟁 간격에서의 미니슬롯(mini-slot)의 수에 대한 프레임에서 할당된 데이터 슬롯인 경쟁형 메시지의 평균수의 비율이 1/3인 한 실시예에서, 평균적인 경쟁형 메시지 사이즈가 0.5 인자만큼 하향으로 조정되고, 그 비율이 1/2인 또 다른 실시예에서는 할당 진행중인 데이터 슬롯의 수가 프레임에서 데이터 슬롯의 나머지수의 2.5배를 넘을 때 경쟁 슬롯이 할당되지 않는 점을 제외하고, Dail 등의 시스템과 매우 유사하다. Dail 등의 방법과 Golmie 등의 방법은 경쟁형 트래픽과 연관된 가변 요청 제공된 로드를 고려하지 않는 것으로 생각된다.

데이터 슬롯에 경쟁형 미니슬롯에 걸쳐 일반적으로 우선순위가 주어지는 무프레임(frameless) 프로토콜 시스템인 Sala 등의 시스템에 대해, 데이터 슬롯 사이에는 경쟁 처리량을 최대화하도록 추가 경쟁 미니슬롯이 주어진다. 높은 데이터 로드에서는 그 방법이 데이터 슬롯 당 e개의 경쟁 미니슬롯의 평균을 할당하도록 수렴된다. 그러나, Sala 등은 DOCSIS 프레임 기반 프로토콜에 반대되는 무프레임 시스템을 제공한다. Sala 등의 프로토콜은 슬롯 대 슬롯에 기초하여 슬롯을 할당할 수 있는 것으로 가정하는 반면, DOCSIS 프로토콜은 프레임 대 프레임에 기초하는 할당을 가정한다.

주된 시스템과 Sala 등의 시스템 사이의 차이는 먼저 주된 시스템이 프레임-기반 시스템이라는 점이고, 두 번째로 Sala 등에서 데이터 슬롯에 일반적으로 경쟁 미니슬롯에 걸쳐 우선순위가 주어진다는 점이다. 주된 시스템에서는 이러한 우선순위가 정해지지 않으므로, 경쟁 슬롯에 대해 데이터의 균형을 맞출 수 있는 보다기대되는 시스템을 허용하게 된다.

또한, 주된 시스템에서는 데이터 전송을 위한 미니슬롯의 공급 및 수요가 동일하게 되도록 시도한다. 과도 현상의 오버로드 하에서는 그 방법이 경쟁 처리량을 최대화하여, 남은 슬롯이 프레임의 경쟁 간격에 포함된다.

주된 시스템이 요청 제공된 로드의 변화를 고려할 수 있으므로, 요청 제공된 로드는 경쟁 기회의 수를 결정하는데 사용된다.

데이터 전송에 대한 슬롯의 공급 및 수요에 대해, 수요는 요청 제공된 로드의 함수인 것을 알 수 있다.

공급 및 수요 함수가 동작점을 설정하므로, 경쟁 및 데이터 슬롯의 할당에 대한 동작점은 이전 시스템과 다르게 요청 제공된 로드에 직접 관련된다.

주된 시스템에서는 공급 및 수요선이 교차하는 위치가 시스템의 최적 동작점이다. 일단 이 점이 설정되면, 경쟁에 대한 슬롯을 할당한 이후에 데이터를 나머지 슬롯에 공급한다. 반대로, 할당될 필요가 있는 수요 대역폭은 성공적인 예약으로 인해 데이터 전송을 요청한다. 공급선은 경쟁 기회의 수와 감소되는 선형 함수이다. 경쟁 기회가 거의 없으면, 전송될 수 있는 데이터량은 더 커지는 것으로 생각된다. 반대로, 경쟁 기회의 수가 많이 증가되면, 데이터를 전송할 기회가 감소된다.

요청에 대해, 더 많은 경쟁 기회를 할당하면, 더 성공적인 예약을 가질 수 있다. 대역폭이 예약되기 때문에, 이는 데이터 슬롯에 대한 더 많은 요청을 제공하게 된다.

공급과 수요 곡선 사이의 교차점에서 보다 더 많은 경쟁 기회로 동작하면, 요청은 공급을 능가하게 된다. 이것이 의미하는 것은 데이터 전송을 위한 슬롯에 대해 너무 많은 경쟁 기회를 할당하고 있음을 의미한다. 그래서, 데이터 스케일링 지연이 높다.

반대로, 공급과 수요 곡선 사이의 교차점에서 보다 더 적은 경쟁 기회로 동작하면, 공급은 수요를 능가하게 된다. 이것이 의미하는 것은 경쟁 기회에 대해 데이터 전송을 위한 슬롯을 너무 많이 할당하고 있음을 의미한다. 이 경우에는 경쟁 억세스 지연이 높아진다.

주된 시스템은 요청 제공된 로드에서의 변화를 고려함으로서 최적점을 설정하도록 허용하고, 이는 데이터 전송을 위해 할당된 슬롯의 수와 경쟁 기회를 위해 설정된 슬롯의 수의 균형을 맞춘다.

한 실시예에서, 정상적인 동작 하에서는 ρ에 대해 경쟁 억세스 지연을 최소화할 수 있고, ρ는 데이터 스케줄러의 사용을 나타낸다. 특정하게, ρ = 수요/공급이 되도록 공급과 사용-조정된 수요 곡선 사이의 교차점에서 할당을 넘지 않고 경쟁에 대한 최대 할당을 결정할 수 있다.

데이터 스케줄링 지연은 ρ의 함수이다. 그러므로, ρ를 고려하여, 데이터 스케줄링 지연은 데이터 스케줄링 알고리즘을 지정할 필요 없이 고려될 수 있다. 그래서, 데이터 스케줄링 알고리즘을 지정하면, ρ에 대해 데이터 스케줄링 지연을 설명할 수 있다.

한 실시예에서, 시스템이 오버로드될 때, 경계 지워진 경쟁 억세스 지연을유지하면서 데이터 스케줄링 지연을 최소화할 수 있다. 특정하게, 경쟁 억세스 지연은 보급되는 요청 제공된 로드에 따라 경쟁 처리량을 최대화하도록 프레임의 경쟁 간격에 최소 슬롯 수를 할당함으로서 경계 지워질 수 있다. 데이터 스케줄링 지연은 이어서 데이터 전송을 위해 프레임에서 나머지 슬롯을 모두 할당함으로서 최대화된다.

균형 해결법에 대해, 지정된 곡선은 소정의 요청 제공된 로드에서 원하는 수의 경쟁 기회를 결정할 수 있음을 나타낸다. 요청 제공된 로드가 매우 작을 때는 데이터 전송을 위한 슬롯에 대해 수요가 작음을 주목하여야 한다. 그러므로, 더 많은 경쟁 기회에 주어질 여분이 많다. 더 많은 경쟁 기회가 주어지면, 충돌 기회가 더 적어지므로, 경쟁 억세스 지연이 감소된다.

설명될 바와 같이, 균형을 제공하기 위한 한가지 방법에서는 균형 잡힌 할당의 선형 근사 하단 경계를 낱낱이 사용한다. 이것으로 이루어지는 것은 요청 제공된 로드가 낮을 때, 데이터 전송에 대해 요청이 많지 않아 많은 예약이 없다는 것이다. 이는 더 많은 경쟁 기회에 대한 여분이 있어 충돌 확률을 낮춘다는 것을 의미한다. 그 결과로, 경쟁 억세스 지연이 낮아진다. 실제적이거나 추정된 소정의 요청 제공된 로드에서, 프레임에 할당될 다수의 경쟁 기회를 확신할 수 있다.

본 시스템과 종래 시스템 사이의 차이는 종래 시스템의 요청 제공된 로드가 정적인 것으로 가정되는 반면, 본 시스템에서는 요청 제공된 로드에 느린 변화가 가해지는 것으로 가정된다는 점이다. 요청 제공된 로드가 정적이라 가정되면, 고정된 할당이 주어져 현재 로딩 조건을 담당하지 못한다.

보다 일반적으로, 슬롯 공유 매체 통신 네트워크에서 사용되는 경쟁-기반 예약 프로토콜에서 변화하는 요청 제공된 로드를 동적으로 적응하도록 대역폭을 할당하는 방법 및 디바이스가 필요하고, 여기서 전송 슬롯은 프레임 대 프레임에 기초하여 할당된다.

시스템 모델

본 발명은 슬롯 공유 매체 통신 네트워크에서 사용되는 경쟁-기반 예약 프로토콜에서 변화하는 제공된 로드를 동적으로 적응하도록 대역폭을 할당하는 방법 및 디바이스를 제공하고, 여기서 전송 슬롯은 프레임 대 프레임에 기초하여 할당된다.

본 발명은 공유 매체 채널에서 전송 프레임의 각 스트림이 경쟁 간격과 데이터 간격 사이에서 분할되는 방법을 결정하여, 대역폭 할당이 효과적이므로, 전송 지연을 감소시킨다. 사용자 데이터는 패킷(packet)이라 공지된 프로토콜-의존 유닛으로 네트워크를 통해 운송된다. 본 발명에 따라, 각 경쟁 요청은 전송을 위해 소정의 고정된 수의 슬롯을 요청하고, 이 고정된 수는 R로 나타내진다. 본 발명에 따라, 각 데이터 패킷은 전송을 위해 랜덤한 수의 슬롯을 요청하고, 이 랜덤수의 평균값은 H로 나타내진다. 소정의 프레임의 경쟁 간격에서 성공적으로 전송된 각 요청은 데이터 전송을 위해 하나 이상의 미래 프레임에서 평균 H 슬롯의 예약을 제공하게 된다. H는 미리 공지되거나 추정될 수 있는 것으로 가정된다. H를 추정하는 방법은 본 발명의 범위에서 벗어난다.

본 발명에 따라, 다음 변수가 프레임 k에 대해 정의된다(즉, 전송 프레임의 스트림에서 제k 프레임으로 식별되는 것). T[k] = 프레임 k에서의 슬롯 수. M[k]= 프레임 k의 경쟁 간격에서의 슬롯 수. W[k] = 프레임 k의 데이터 간격에서의 슬롯 수.

프레임 k에 할당된 경쟁 기회의 수는 M[k]/R로 주어진다. 비록 M[k]는 전형적으로 M[k]/R이 정수가 되도록 선택되지만, 이는 발견적으로 간략화된 분석을 위해 실수로 다루어진다. M[k]/R이 정수가 아닐 때, 프레임 k에 할당된 경쟁 기회의 수는 M[k]/R에 가장 가깝고 더 작은 정수값으로 설정된다.

도 3을 참고로, 각 패킷은 전송을 위해 데이터 간격(72)에서 다수의 슬롯(70)을 요청한다. 데이터 전송이 예약을 통해, 주로 경쟁 간격(74)에서의 요청의 경쟁-근거 전송을 통해 이루어진다. 여기서, 데이터 간격은 W로 나타내지고, 경쟁 간격은 M으로 나타내진다. 소정의 시간에 발생된 요청은 이전 스케줄 처리된 경쟁 간격에서 전송되지 않고, 다음 스케줄 처리된 경쟁 간격 동안 대기하여야 한다. 알 수 있는 바와 같이, 현재 프레임에서의 할당은 이전 프레임에서의 요청 제공된 로드에 기초하여 결정된다.

본 발명에 따라, 다음 변수들이 프레임 k에 대해 정의된다(즉, 전송 프레임의 스트림에서 제k 프레임으로 식별되는 것). 간략하게, 또한 일반성을 손실시키지 않고, 각 프레임은 경쟁 간격 및 데이터 간격으로 완전히 분할된 것으로 가정되므로, 프레임 k의 데이터 간격에서의 슬롯 수는 W[k] = T[k] - M[k]라 주어진다. 제어 오버헤드나 또 다른 응용을 위한 추가 간격은 본 발명의 설명에서 포함되지 않는다. 종래 기술에 숙련된 자는 이와 같이 생략된 간격들을 명확하게 고려한다. 예를 들어, Dail 등은 경쟁-기반 예약을 요청하지 않는 트래픽에 할당된 데이터 슬롯을 고려할 수 있는 방법을 지시한다.

본 발명에 따라, 각 데이터 패킷은 정수 배의 슬롯으로 맞추어지고, 임의의 슬롯 경계에서 분할될 수 있고, 그 분할은 데이터 패킷이 다수의 패킷 부분으로 나뉘어 더 작은 사이즈의 패킷으로 전송되게 하는 처리이다. 제1 가정으로, 대부분 한 슬롯으로 데이터 패킷의 사이즈를 과대 추정하게 되지만, 이 효율성은 슬롯 시스템 본래의 것이다. 제2 가정은 명확하게 고려되지 않는 분할 오버헤드를 희생시켜 프레임-기반 할당으로 인한 제한 효과를 최소화한다. 이는 본 발명의 의도에서 벗어나지 않고 종래 기술에 숙련된 자가 명확하게 상기 가정을 완화시키게 한다.

본 발명에 따라, 다수의 사용자들이 집합적이고 랜덤하게 반정적인 요청 제공된 로드의 요청을 발생한다. 즉, 요청 제공된 로드가 시간에 따라 느리게 변화될 수 있다. g[k]를 프레임 k에서의 제공된 로드, 즉 프레임 k에서 슬롯 당 발생된 요청의 수라 놓는다. 이 제공된 로드는 미리 공지되거나, Abi-Nassif 등의 상술된 지시에 의해 제안된 바와 같이 추정될 수 있다. G[k]를 프레임에서 유효한 요청 제공된 로드, 즉 프레임 k에서 경쟁 기회 당 진행중인 요청의 수라 놓는다. 요청이 소정의 프레임에서 발생될 때, 이는 전송을 위해 다음 프레임까지 대기하여야 한다. 프레임(k-1)에서 발생된 요청의 기대 수는 g[k-1]T[k-1]이다. 이는 G[k] = (g[k-1]T[k-1])/N[k]로 이어진다.

전송 요청은 헤드엔드에 의해 성공적으로 수신되거나, 다른 사용자에 의해 동시에 전송된 요청과 충돌한다. 이는 종결 이진수 지수 백오프 알고리즘과 같은 경쟁 해결 알고리즘이 사용되어 충돌을 해결하는 것으로 가정된다. 또한, 경쟁 해결 알고리즘은 각 슬롯에서의 재전송 확률이 작으므로, 요청에 대한 경쟁-기반 다중 억세스가 이미 공지된 슬롯 알로하 모델(Slotted Aloha model)에 의해 모델화될 수 있는 것으로 가정된다.

슬롯 알로하 모델에 이어서, 경쟁 간격에서의 처리량은 최대값이 1/e = 0.3679인 S[k] = G[k]exp{-G[k]}이다. 최대 처리량은 1/e이고 G[k] = 1일 때 이루어지는 것으로 확인될 수 있고, 이는 프레임 k-1의 소정의 요청 제공된 로드 g[k-1] 및 프레임 사이즈 T[k-1]에 대해, 프레임 k의 경쟁 간격에서의 M[k] 슬롯의 할당이 M[k] = g[k-1]T[k-1]R로 가정하는 경우 경쟁 간격에서 처리량을 최대화함을 의미한다. 다른 말로 하면, 최대 경쟁 처리량은 프레임에서 경쟁 기회의 수가 이전 프레임에서 발생된 요청의 기대 수와 똑같을 때 이루어진다.

도 4는 경쟁 처리량을 최대화하는 상기 할당을 도시하고, 그 할당은 요청 제공된 로드의 선형 함수이다. 특별히, 이는 할당이 요청 제공된 로드에 비례하는 것으로 나타낸다. 선 위에는 요청 제공된 로드를 수용하기에 충분한 경쟁 기회가 있음을 나타내는 안정된 경쟁 영역이 있다. 선 아래에는 요청 제공된 로드를 수용하기에 충분하지 않은 경쟁 기회가 있음을 나타내는 불안정된 경쟁 영역이 있다.

exp{-G[k]}는 프레임 k의 경쟁 기회에 요청이 성공적으로 전송될 확률임을 주목한다. 즉, 경쟁 기회에 전송되는 요청이 정확하게 1개가 있다. G[k] = 1일 때, 이 성공 확률은 1/e이다.

데이터 패킷의 전체적인 다중 억세스 지연은 데이터 패킷의 전송을 위해 슬롯을 예약하려는 요청이 발생되는 시간으로부터 요청이 성공적으로 전송되어 헤드엔드에 의해 수용되는 시간까지인 경쟁 억세스 지연과, 요청이 헤드엔드에 의해 수용되는 시간으로부터 패킷이 채널에서 완전히 전송되는 시간까지인 데이터 스케줄링 지연으로 구성된다.

제공된 로드가 낮을 때는 많은 아이들 경쟁 기회가 있으므로 경쟁 처리량을 최대화하기 위해 전송 프레임에 큰 경쟁 간격을 할당할 필요가 없다. 그럼에도 불구하고, 낮은 제공된 로드로 인하여 데이터 트래픽이 많지 않으므로, 비예약 슬롯을 거의 사용하지 않는다. 본 발명의 제1 실시예에 따라, 데이터 전송을 위해 다수의 슬롯 및 경쟁 처리량을 최대화하도록 프레임의 경쟁 간격에 다수의 슬롯을 초기에 할당한 이후 프레임에 비예약 슬롯이 남아있을 때마다, 여분 슬롯은 부가하여 경쟁 간격에 포함된다. 이 접근법은 적절한 양으로 데이터 스케줄링 지연을 증가시키지 않고 경쟁 억세스 지연을 개선함을 주목하여야 한다.

요청 제공된 로드가 높을 때, 경쟁 간격은 경쟁 처리량을 최대화하도록 그에 따라 커져야 한다. 그렇지 않으면, 많은 전송 충돌이 서로 충돌된다. 요청 제공된 로드가 높을 때 경쟁 처리량을 최대화하는 것은 업스트림 대역폭의 할당에서 데이터 전송 기회 보다 경쟁 기회에 더 높은 우선순위가 주어짐을 의미한다. 이는 한정되지 않은 데이터 스케줄링 지연을 제공할 수 있다. 적절한 허용 제어 메커니즘은 시스템이 요청 및 데이터 모두에 대해 과도한 제공된 로드로 동작할 기회를 최소화하거나 그를 방지하는데 사용된다고 가정한다. 시스템이 순간적으로 오버로드되는 경우, 과도 현상 효과는 데이터 스케줄링 지연에서 일시적으로 증가된다. 피기백킹은 또한 시스템이 다시 정상적인 제공된 로드로 동작하게 도움을 준다.

사용자로부터의 성공적인 각 요청은 사용자가 전송하고 싶어하는 패킷의 사이즈를 수용하는 데이터 전송 기회에 대한 예약에 대응한다. 요청의 사이즈에 관련된 패킷의 평균 사이즈가 크면 클수록, 더 많은 대역폭이 경쟁 간격 등에 관련된 데이터 간격에 할당되어야 한다. 이와 같이, 효과적인 대역폭 할당은 예약 요청의 제공된 로드뿐만 아니라 패킷 사이즈의 분포에도 의존한다.

데이터 전송을 위한 슬롯의 공급 및 수요

접근법의 중심 개념은 데이터 전송을 위한 슬롯의 공급 및 수요에서 균형을 맞추는 것에 기초한다.

도 5에서 설명되는 바와 같이, 데이터 전송을 위한 슬롯의 요청은 충돌 확률이 감소되기 때문에 점근값까지 할당된 경쟁 기회의 수와 함께 증가된다. 이후 볼 수 있는 바와 같이, 원래의 수요 곡선은 데이터 전송을 스케줄 처리하는데 사용되는 데이터 스케줄러의 이용을 고려하도록 상향으로 조정된다. 그 결과는 이용-조정 수요 곡선이라 하는 새로운 수요 곡선이다.

도 6에서 설명되는 바와 같이, 이용 가능한 업스트림 대역폭의 보존으로 인해, 데이터 전송을 위한 슬롯의 공급은 증가되는 수의 경쟁 기회가 할당됨에 따라 선형으로 감소된다. 이후 볼 수 있는 바와 같이, 데이터 전송을 위한 슬롯의 이러한 공급은 소정의 할당된 경쟁 기회로 데이터 전송을 위해 이용 가능한 대역폭을 나타낸다. 너무 많은 경쟁 기회가 할당되면, 데이터 스케줄링 지연은 데이터 전송을 위해 충분한 대역폭이 없으므로 높아질 수 있다.

원칙적으로, 소정의 시스템 매개변수 세트에 대해, 데이터 전송을 위한 슬롯의 공급 및 수요가 동일한 동작점이 존재한다. 이후 볼 수 있는 바와 같이, 이 동작점은 데이터 전송을 위한 슬롯의 공급 및 수요에 기초하여 경쟁 기회를 할당하기 위한 기초를 형성한다.

프레임에서 성공적으로 전송된 요청으로 인한 데이터 전송의 슬롯 수요는 그 프레임의 경쟁 간격에서 성공적으로 전송된 요청의 기대 수뿐만 아니라 성공적으로 전송된 요청 당 예약되는 슬롯의 평균수에 비례한다. 경쟁 간격에서 성공적인 요청 전송의 기대 수는 경쟁 간격에서 경쟁 기회의 수와 이루어진 경쟁 처리량의 곱이다. D[k]를 프레임(k-1)에서 성공적으로 전송된 요청으로 인한 데이터 전송의 슬롯 수요라 놓는다. 이때,

소정의 제공된 로드에 대해, 그 프레임에서 데이터 전송의 이 슬롯 수요는 0에서 점근값까지 프레임의 경쟁 간격에서의 경쟁 기회의 수와 함께 증가된다. 이 점근값은 성공적으로 전송된 요청 당 예약된 슬롯의 평균수와 이전 프레임에서 발생된 요청의 기대수의 곱이다.

데이터 스케줄러에 대해 원하는 이용률이 ρ이면, 수요 D[k]를 만족시키는데 필요한 슬롯의 유효 수는 D[k]/ρ이다. 이후로 D'[k] = D[k]/ρ이고, 이러한 이용률-조정 수요는 ρ에 대한 의존도가 고려된다는 내용이 명백할 때 간단히 요청이라 할 수 있다.

한 프레임에 유한한 수의 슬롯이 주어지는 경우, 더 많은 슬롯이 프레임의경쟁 간격에 할당되면 될수록, 더 적은 슬롯이 데이터 전송에 이용 가능하다. 그래서, 프레임에서 데이터 전송의 슬롯 공급은 그 프레임의 경쟁 간격에 할당된 슬롯의 수와 함께 선형으로 감소된다. C[k]를 프레임(k)에서 데이터 전송을 위한 슬롯의 공급이라 놓는다. 이때, C[k] = T[k] - M[k]이다.

데이터 전송의 슬롯 수요는 충돌 확률이 감소되기 때문에 경쟁 간격에 할당된 슬롯의 수와 함께 증가된다. 이용 가능한 업스트림 대역폭의 보존으로 인해, 데이터 전송의 슬롯 공급은 증가되는 수의 슬롯이 경쟁 간격에 할당됨에 따라 감소된다.

개념적으로, 헤드엔드는 데이터 전송을 위해 예약 슬롯의 큐(queue)를 유지한다. 데이터 전송의 슬롯 수요는 큐로의 내부 흐름(in-flow)을 나타내고, 데이터 전송의 슬롯 공급은 큐로부터의 외부 흐름(out-flow)을 나타낸다. 큐의 안정된 동작을 위해, 내부 흐름은 외부 흐름을 넘지 말아야 한다. 본 발명의 중심 개념은 데이터 전송의 슬롯 공급 및 수요에서 균형을 맞추는 것이고, 소정의 데이터 스케줄러는 데이터 패킷 사이에서 슬롯을 할당하는데 사용되고 데이터 스케줄러의 동작에는 소정의 이용률이 주어진다. 데이터 스케줄러의 이용은 데이터 전송의 슬롯 공급에 대한 수요의 비율에 관련된다. 이 비율이 1 보다 작다고 가정하면, 요청은 데이터 전송의 슬롯 공급을 넘지 않고, 데이터 스케줄링 지연은 한정된다.

공급 곡선 및 이용률-조정 수요 곡선은 프레임의 경쟁 간격에 할당된 유일한 수의 경쟁 기회로 동작점에서 서로 교차함을 주목하여야 한다. 이 유일한 동작점에서는 C[k] = D'[k], 즉 데이터 전송의 슬롯 공급 및 수요가 서로 균형된다. 제공된 로드가 g[k-1]일 때 데이터 전송의 슬롯 공급 및 수요의 균형을 맞추는 경쟁 할당은 M[k]의 다음 함수에 대한 해이다:

상기 식은 이후 균형식이라 하고, 균형식에 대한 해는 균형 해이라 한다. 균형 해는 데이터 전송의 슬롯 공급 및 이용률-조정 수요를 동일하게 하여 유도된 균형식에 대한 해이다. 각 요청 제공된 로드에 대해, 균형 해는 경쟁 간격 및 데이터 간격에서 원하는 수의 슬롯이 할당되도록 결정한다.

도 7은 g[k-1], 프레임(k-1)에서의 요청 제공된 로드에 대해 그려진 프레임(k)에 대한 비선형 균형 해의 그래프를 도시한다. 곡선 아래의 동작점에서는 공급이 수요를 넘어, 여분의 데이터 슬롯이 있다. 곡선 위의 동작점에서는 수요가 공급을 넘어, 데이터 전송을 위한 슬롯이 부족하다.

ρ ≤ 1이므로, C[k] = D'[k] = D[k]/ρ은 D[k]/C[k] = ρ ≤ 1을 의미하는 것으로 생각된다. 그래서, ρ ≤ 1이면, 균형식은 데이터 전송을 위해 예약된 슬롯의 헤드엔드 큐로의 내부 흐름이 큐로부터의 외부 흐름을 넘지 않으므로, 데이터 스케줄링 지연이 한정될 수 있음을 보장한다.

균형 해는 H, R, ρ, T[k], T[k-1], 뿐만 아니라 g[k-1], 요청 제공된 로드의 함수임을 주목하여야 한다. 소정의 값의 H, R, ρ, T[k], T[k-1], 및 g[k-1]에서, 균형식은 수적으로 풀려질 수 있다.

프레임(k)에 대한 균형식은 프레임(k-1)에서 요청 제공된 로드의 볼록 함수임을 확인할 수 있고, 여기서 그 함수는 1개의 잘 정의된 최소값을 갖고, 요청 제공된 로드가 없을 때 값 T[k]를 갖고, 최소값을 갖는 지점까지 요청 제공된 로드 g[k-1]에 대해 증가되지 않고, 또한 더 큰 요청 제공된 로드 g[k-1]에 대해 감소되지 않는다.

균형 해에서의 경계

균형식에 대한 해가 비선형이므로, 이 해를 결정하는데 계산적으로 포함된다. 본 발명의 다양한 실시예에서는 간단한 선형 또는 비선형 함수가 비선형 해를 근사화시키는데 사용된다.

균형식에서 M[k]의 도함수를 취하고, g[k-1]에 대해 그 도함수를 0으로 설정함으로서, G[k] = g[k-1]T[k-1]R/M[k] = 1일 때 g[k-1]에 대해 균형 해의 최소에 이른다는 결론에 이를 수 있다. 즉, M[k] = g[k-1]T[k-1]R은 균형 해가 최소화될 때 만족되어야 한다. 경쟁에 대한 이러한 할당은 경쟁 처리량을 최대화하는데 필요한 할당과 일치하는 것으로 생각된다.

슬롯 알로하 가정에 의해, 경쟁 간격에서의 처리량은 G[k] ≤ 1에서 안정될 수 있다. 다른 말로 하면, 경쟁 억세스 지연은 M[k] = g[k-1]T[k-1]R일 때 한정될 수 있다.

균형 해는 다음과 같을 때 최소화되는 것으로 확인될 수 있다.

ρe/(H + ρeR)를 b(H,R,ρ)로 나타내면, g₀= b(H,R,ρ)T[k]/T[k-1]이다.

b(H,R,ρ)의 역수는 예약 시도 당 요청되는 슬롯의 기대수로 해석되고, 여기서는 경쟁 기회에 대해 R 슬롯이 요청되고, 데이터 전송에 대해 H/(ρe) 슬롯이 기대된다. H/ρ 슬롯이 확률 1/e(즉, 성공 확률)로 요청되고 확률(1 - 1/e)로는 슬롯이 요청되지 않으므로, 예약 시도 당 데이터 전송에 요청되는 슬롯의 기대 수는 H/(ρe)이다.

g[k-1] = g₀일 때, 균형 해는 M[k] = b(H,R,ρ)T[k]R = g₀T[k-1]R을 제공하여, M[k] = g[k-1]T[k-1]R, 즉 최대화되는 경쟁 처리량에 대한 조건을 만족시키는 것으로 확인될 수 있다. 그래서, 균형 해에서 제1 하한값은 다음과 같다.

M[k] ≥ b(H,R,ρ)T[k]R g[k-1] ≥ 0에 대해.

균형 해에서 상기의 하한값은 또한 다음과 같이 유도될 수 있는 것으로 생각된다.

W[k]와 M[k] 사이의 다음 관계는 상기 하한값의 직접적인 결과인 것으로 생각된다.

도 8은 경쟁 간격의 사이즈에 대한 데이터 간격의 사이즈의 비율이 상기 관계를 만족시키도록 프레임에서 경쟁 및 데이터에 대한 슬롯을 할당하는 방법을 도시한다. 요청 제공된 로드에 독립적인 이 방법은 고정된 할당을 갖는 종래 시스템과 유사한 것으로 생각된다.

g[k-1] = g₀일 때, 프레임(k)의 데이터 간격에 할당된 슬롯의 수인 W[k] = T[k] - M[k] = T[k] - b(H,R,ρ)T[k]R이다. 이 할당은 g[k-1] = g₀일 때 균형 해가 최소값을 갖기 때문에 데이터 전송의 슬롯 공급 및 수요의 균형을 맞추면서 최대 데이터 처리량을 제공하는 것으로 생각된다. 이 최대 데이터 처리량은 H/(H + ρeR)로, H >> ρeR에서 1로 되는 경향이 있음을 확인할 수 있다.

g[k-1] > g₀일 때, 균형 해는 할당 M[k] = g[k-1]T[k-1]R을 최대화하는 경쟁 처리량에 의해 상기로부터 한정되므로, 균형 해법이 높은 경쟁 억세스 지연을 제공할 수 있음을 확인할 수 있다. 이에 대해, 특정한 제공된 로드 g₀은 오버로드 문턱값이라 한다.

이전에 논의된 바와 같이, 균형 해는 g[k-1] = 0일 때 T[k]와 같고, g[k-1] = g₀= b(H,R,ρ)T[k]/T[k-1]일 때 M[k] = b(H,R,ρ)T[k]R을 만족시킨다. 0 ≤ g[k-1] ≤ g₀에서, 균형 해는 b(H,R,ρ)T[k]R = g₀T[k-1]R ≥ g[k-1]T[k-1]R에 의해 아래로부터 한정된다. 그래서, 균형 해로 시작하여, 균형 해에 대해 상한값을 구하고,

M[k] ≤ T[k] - g[k-1]T[k-1]H/(ρe)

균형 해에서 제2 하한값을 구한다.

M[k] ≥ T[k] - g[k-1]T[k-1]H/ρ

하한값은 g[k-1] = g₀= b(H,R,ρ)T[k]/T[k-1] 및 M[k] = b(H,R,ρ)T[k]R로 유도되는 반면, 상한값은 g[k-1] << g₀= b(H,R,ρ)T[k]/T[k-1] 및 M[k] ≥ b(H,R,ρ)T[k]R로 유도된다.

g[k-1]이 0으로 됨에 따라, 균형 해에서 상기 하한값은 좁혀지는 것을 확인할 수 있다. 상기 상한값은 g[k-1] = g₀일 때 M[k] = b(H,R,ρ)T[k]R과 교차되는 반면, 하한값은 g[k-1] = g₀/e일 때 M[k] = b(H,R,ρ)T[k]R과 교차됨을 주목하여야 한다.

모든 값의 g[k-1]에 대해 M[k] ≥ b(H,R,ρ)T[k]R이므로, 하한값은 다음과 같이 수정된다. M[k] ≥ max{b(H,R,ρ)T[k]R, (T[k] - g[k-1]T[k-1]H/ρ)}. 동일하게, g[k-1] ≤ g₀/e에서, M[k] ≥ T[k] - g[k-1]T[k-1]H/ρ이고, g₀/e < g[k-1] ≤ g₀에서, M[k] ≥ b(H,R,ρ)T[k]R이다.

균형 해는 다음과 같이 제1 하한값을 만족시킴을 확인할 수 있다.

M[k] ≥ T[k] - g[k-1]T[k-1]H/ρ

상기 하한값은 요청 제공된 로드의 선형 함수이지만, 처음 것은 변질된 경우인 것으로 생각된다. 이들 두 선형 함수는 요청 제공된 로드가 g₀/e일 때 교차하는 것으로 확인될 수 있다.

도 7은 본 발명에 따른 균형 해를 도시한다. 균형 해는 요청 제공된 로드가 없을 때 프레임 사이즈로 시작되고, 요청 제공된 로드가 증가함에 따라 거의 선형으로 감소되고, 요청 제공된 로드가 오버로드 문턱값에 있을 때 최소값을 갖고, 이어서 요청 제공된 로드가 오버헤드 문턱값 이상으로 올라감에 따라 점차적으로 증가된다.

도 7은 또한 본 발명에 따른 균형 해에서 다양한 경계를 도시한다. 균형 해는 비오버로드 영역에서의 감소하는 선형 함수, 및 오버로드 영역에서 경쟁 처리량을 최대화하는 할당에 의해 상기로부터 한정된다. 균형 해는 모든 요청 제공된 로드에 대해 제1 하한값 위에 남아 있다. 요청 제공된 로드가 적을 때, 제2 하한값은 훨씬 밀접한 경계이다.

요청 제공된 로드의 영역

균형 해에서의 다양한 경계는 3가지 영역의 요청 제공된 로드를 정의하는 것으로 생각된다. 제1 영역은 더 많은 경쟁 기회가 할당될 수 있도록 데이터 전송의 슬롯 수요가 낮은 가벼운 로드 영역이다. 제2 영역은 데이터 전송의 공급 및 수요 균형을 맞추는데 요청되는 최소 할당이 접근되는 적절한 로드 영역을 나타낸다. 제2 영역에 대해 더 낮은 문턱값은 균형 해에서 제1 및 제2 하한값들의 교차점에 의해 결정된다. 제3 영역은 데이터 전송의 슬롯 공급 수요의 균형이 맞추어져 시스템의 불안정성에 이르러 불충분한 경쟁 기회가 할당되는 오버로드 영역이다.

보다 특정하게, b(H,R,ρ)T[k]/T[k-1]과 같은 오버로드 문턱값 g₀은 요청 제공된 로드를 g[k-1] ≤ g₀인 오버로드 영역과, g[k-1] > g₀인 비오버로드 영역으로 나눈다.

g[k-1] = g₀일 때, 균형 해는 최소값을 갖고, 경쟁 처리량을 최대화한다.

g[k-1] < g₀에서, 경쟁 처리량을 최대화하면, 공급이 데이터 전송 기회의 요청을 넘게 되어, 일부 전송 기회가 낭비된다. 이 경우에는 경쟁 처리량이 최대치에 있지 않더라도, 경쟁 억세스 지연을 최소화하도록 요청에 대해 더 많은 전송 기회를 할당하는 것이 바람직하고 알맞다. 균형 해는 시스템이 비오버로드 상태일 때 경쟁 처리량을 최대화하는데 필요한 것 보다 더 많은 경쟁 슬롯을 할당하는 것으로 생각된다.

g[k-1] > g₀에서, 경쟁 처리량을 최대화하면, 수요가 데이터 전송 기회의 공급을 넘게 되어, 결과적으로 데이터 스케줄링 지연이 과도하게 된다. 데이터 전송의 슬롯 공급 및 수요의 균형을 맞추는데는 경쟁 처리량을 최대화하는데 요청되는 것 보다 더 적은 수의 경쟁 기회를 할당하는 것이 요청된다. 이는 각 프레임에서 충돌의 수를 증가시키게 하여, 경쟁 억세스 지연을 증가시킨다. 결과적으로, 많은 비성공적인 요청이 백오프되어 추후 재전송된다. 이는 요청 제공된 로드를 더 증가시켜, 업스트림 대역폭을 비효율적으로 이용하게 된다. 그래서, 오버로드 영역에서 데이터 전송의 슬롯 공급 및 수요의 균형을 맞추는 것이 바람직하지 않다.

시스템이 오버로드 영역에서 동작하고 있을 때, 경쟁 간격은 내용 처리량을 최대화시키도록 커야한다. 그렇지 않으면, 많은 전송 요청이 서로 충돌된다. 그러나, 시스템이 오버로드될 때 경쟁 처리량을 최대화하는 것은 경쟁 기회에 데이터 전송 기회 보다 더 높은 우선순위가 주어짐을 의미한다. 이는 과도한 데이터 스케줄링 지연을 제공할 수 있다. 본 발명에 따라, 데이터 스케줄링 지연에서의 일시적인 증가를 희생하여 과도 현상 오버로드의 경우 경쟁 처리량을 최대화하는 것이 중요하다.

그래서, 시스템이 과도한 제공된 로드로 동작할 기회를 최소화하거나 방지하는데 적절한 허용 제어 메커니즘이 사용되는 것이 바람직하다. 시스템이 순간적으로 오버로드되는 경우, 과도 현상 효과는 데이터 스케줄링 지연을 일시적으로 증가시킨다. 피기백킹은 또한 시스템이 정상적인 제공된 로드로 다시 동작하게 하는데 도움이 될 수 있다.

오버로드 영역에서 동작할 기회를 최소화하거나 방지하는 방법은 여러 가지가 있다. 한가지 방법은 적절한 허용 제어 알고리즘에 의해 사용자의 수를 제한하는 것이다. 또 다른 방법은 최대 허용 가능한 회수까지 이미 재전송된 요청을 드롭(drop) 시키는 것이다. 또 다른 방법은 데이터 패킷을 선택적으로 드롭시키는 것이다. 명확하게, 상기 다른 방법은 서로 배타적이지 않다. 오버로드 영역에서의 동작을 방지하는 방법은 본 발명의 범위를 벗어난다.

범위 0 ≤ g[k-1] ≤ g₀/e에 있는 요청 제공된 로드에 대해, 균형 해의 제2 하한값은 특히 g[k-1]이 0에 가까울 때 밀접한 것으로 생각된다. g₀/e ≤ g[k-1] ≤ g₀에 있는 요청 제공된 로드에 대해, 균형 해는 최소값 g₀T[k-1]R에 가까운 것으로 생각된다. 요청 제공된 로드의 비로드 영역을 0 ≤ g[k-1] ≤ g₀/e인 가벼운 로드 영역, 및 g₀/e ≤ g[k-1] ≤ g₀인 적절한 로드 영역으로 나누는 것이 유용하다.

본 발명의 실시예

볼 수 있는 바와 같이, 변화하는 요청 제공된 로드가 고려되는 본 발명의 실시예는 3가지가 있다. 제1 실시예는 보급되는 요청 제공된 로드에 기초하여 배치 처리량을 최대화하는 할당 방법을 지정한다. 제2 실시예는 데이터 전송의 슬롯 공급 및 수요의 균형을 맞추는데 요청되는 최소 할당을 고려함으로서 제1 실시예를 증진시킨 방법을 지정한다. 제3 실시예는 요청 제공된 로드가 낮은 상황을 수용하도록 균형 해를 완전히 고려함으로서 제2 실시예를 더 증진시킨 방법을 지정한다.

도 9는 요청 제공된 로드에 대해 경쟁 처리량이 최대화되도록 프레임의 경쟁 및 데이터에 대해 슬롯을 할당하는 본 발명의 제1 실시예를 도시한다. 이 할당은 요청 제공된 로드의 선형 함수에 의해 관리되므로, 이는 요청 제공된 로드가 없을 때 0 값을 갖고, 다른 요청 제공된 로드에서는 비례적으로 증가된다.

제1 실시예에서는 프레임(k)의 경쟁 간격에서 초기에 할당된 슬롯의 수가 경쟁 간격에서 처리량을 최대화한다. 특정하게, M[k] = g[k-1]T[k-1]R이다. 즉, 프레임에서 경쟁 기회의 수는 이전 프레임에서 발생된 요청의 기대 수와 같다. 이 할당 함수를 설명하는 선은 M[k]의 값을 각 g[k-1] 값에 대해 안정된 경쟁 영역 및 불안정된 경쟁 영역으로 나눔을 주목하여야 한다.

데이터 전송을 위한 나머지 슬롯 및 경쟁 간격에서의 슬롯의 수를 초기에 할당한 이후 프레임에 비예약 슬롯이 남아있을 때마다, 여분 슬롯은 부가적으로 경쟁 간격에 포함된다. 나머지 프레임을 채우도록 진행중인 할당에서 예약 슬롯이 충분하지 않거나, 나머지 프레임에서 데이터 슬롯을 완벽하게 맞출 수 없으므로, 여분 슬롯이 있을 수 있다.

제1 실시예는 경쟁 처리량을 최대화하도록 각 프레임에서 경쟁 및 데이터에 대한 슬롯의 수를 할당할 때 변화하는 요청 제공된 로드를 고려하여, 그에 의해 시스템이 한정된 경쟁 억세스 지연으로 동작할 수 있는 것으로 생각된다.

도 10은 시스템이 오버로드된 영역에 있을 때 경쟁 처리량이 최대화되고, 시스템이 비오버로드 영역에 있을 때 데이터 전송의 슬롯 공급 및 수요의 균형을 맞추기 위한 최소 할당이 보장되도록 프레임에서 경쟁 및 데이터의 슬롯을 할당하는 본 발명의 제2 실시예를 도시한다. 이 할당은 2개의 선형 세그먼트(segment)를 가지고 요청 제공된 로드의 선형 함수에 의해 관리되므로, 이는 0 내지 오버로드 문턱값까지의 범위에 있는 요청 제공된 로드에 대해 0이 아닌 상수값을 갖고, 그렇지 않은 경우에는 요청 제공된 로드와 비례적으로 증가된다.

제2 실시예에서, 프레임(k)의 경쟁 간격에 먼저 할당된 슬롯의 수는 균형 해에서의 제1 하단 경계뿐만 아니라 다음과 같은 경쟁 처리량 최대화 함수의 조합으로부터 유도된다.

M[k] = max{g[k-1]T[k-1]R, b(H,R,ρ)T[k]R}

동일하게, 범위 0 ≤ g[k-1] ≤ g₀의 요청 제공된 로드에 대해서는 M[k] = b(H,R,ρ)T[k]R이고, 더 높은 요청 제공된 로드에 대해서는 M[k] = g[k-1]T[k-1]R이다. 본 발명의 제2 실시예는 요청 제공된 로드의 비오버로드 영역 및 오버로드 영역에서 각각 경쟁에 대해 다른 할당을 적응하는 것으로 생각된다.

데이터 전송을 위해 나머지 슬롯을 할당한 이후에 프레임에 여분 슬롯이 있으면, 여분 슬롯은 프레임의 경쟁 간격에 포함된다.

제2 실시예는 요청 제공된 로드의 함수인 것으로 생각된다. 이는 시스템이 오버로드일 때 경쟁-기반 예약 시스템이 불안정해지는 기회를 최소화할 뿐만 아니라, 시스템이 비오버로드 상태일 때 데이터 스케줄링 지연을 최소로 희생시켜 경쟁 억세스 지연을 낮춘다.

도 11은 본 발명의 제3 실시예를 도시하고, 이는 시스템이 오버로드 영역에 있을 때 경쟁 처리량을 최대화하고, 시스템이 적절한 로드 영역에 있을 때 데이터 전송의 슬롯 공급 및 수요의 균형을 맞추는데 최소 할당이 사용되고, 또한 시스템이 가벼운 로드 영역에 있을 때 데이터 전송의 슬롯 공급 및 수요의 균형을 대략적으로 맞추는 할당이 사용되도록 프레임에서 경쟁 및 데이터의 슬롯을 할당한다. 특정하게, 이 할당은 요청 제공된 로드의 선형 함수에 의해 지배되어, 가벼운 로드 영역에서 그 값이 선형으로 감소되고, 적절한 로드 영역에서 0이 아닌 상수값을 갖고, 오버로드 영역에서 요청 지시 로드와 비례적으로 증가된다.

제3 실시예에서, 프레임(k)의 경쟁 간격에 먼저 할당된 슬롯의 수는 균형 해에서의 제1 및 제2 하단 경계뿐만 아니라 다음과 같은 경쟁 처리량 최대화 함수의 조합으로부터 유도된다.

M[k] = max{g[k-1]T[k-1]R, b(H,R,ρ)T[k]R, (T[k]-g[k-1]T[k-1]H/ρ)}

동일하게, 범위 0 ≤ g[k-1] ≤ g₀/e의 요청 제공된 로드에 대해서는 M[k] =T[k] - g[k-1]T[k-1]H/ρ이고, 범위 g₀/e ≤ g[k-1] ≤ g₀의 요청 제공된 로드에 대해서는 M[k] = b(H,R,ρ)T[k]R이고, 더 높은 요청 제공된 로드에 대해서는 M[k] = g[k-1]T[k-1]R이다. 본 발명의 제3 실시예는 요청 제공된 로드의 가벼운 로드 영역, 적절한 로드 영역, 및 오버로드 영역에서 각각 경쟁에 대해 다른 할당을 적응하는 것으로 생각된다.

제3 실시예는 요청 제공된 로드의 함수인 것으로 생각된다. 이는 시스템이 오버로드될 때 경쟁-기반 예약 시스템이 불안정해지는 기회를 최소화할 뿐만 아니라, 시스템이 오버로드되지 않을 때 데이터 스케줄링 지연이 한정되는 것을 보장하면서 경쟁 억세스 지연을 최소화한다.

임시적인 수의 슬롯이 경쟁 간격에서 할당되는 본 발명의 모든 실시예에서, 임시적인 할당은 데이터 전송을 위한 슬롯의 공급 및 수요의 균형을 맞추는데 요청되는 할당에 대해 유지되는 것임을 주목하여야 한다. 여분 슬롯이 경쟁 간격에 포함되더라도, 데이터 전송을 위한 슬롯의 공급 및 수요의 균형을 맞추는 할당을 제공하기에 충분하지 못할 가능성이 있다. 요청 제공된 로드가 동적으로 추정된다고 가정하면, 미래 할당은 할당된 경쟁 기회의 수에서 여분 또는 부족에 응답하여 그에 따라 조정된다.

본 발명의 상기 실시예의 효율성은 분할 입도(granularity)에 의존한다. 분할 입도가 한 슬롯 보다 더 크거나, 분할이 허용되지 않으면, 진행중인 전송에서패킷 또는 패킷 일부를 수용하기에 충분하지 못한 여분 슬롯이 프레임에 있을 수 있다. 또한, 데이터 전송을 위한 슬롯의 수요를 때로 과도 추정할 가능성이 있다. 임의의 경우에는 프레임에 여분 슬롯이 있을 때마다, 여분 슬롯이 프레임의 경쟁 간격에 포함된다. 원칙적으로, 비효율성을 최소화하기 위해, 경쟁 기회의 공급에서의 여분은 미래 프레임의 경쟁 간격으로부터 공제될 수 있다. 그럼에도 불구하고, 미래 할당이 여분에 응답하여 그에 따라 조정되기 때문에, 제공된 로드가 동적으로 추정될 때, 이는 필요로 하지 않는다.

이제는 도 14를 참고로, 경쟁 스케쥴링을 설명하는 흐름도가 도시된다. 여기서, 경쟁 스케줄링은 (110)에서 초기화되어, 새로운 프레임을 할당하고(112), 이어서 이 경우 요청 제공된 로드인 제공된 로드를 구한다(114). 이어서, (116)에 설명된 바와 같이, 시스템은 경쟁 간격 사이즈를 결정하고, (118)에서는 미래 프레임에 경쟁 간격을 할당한다.

도 15를 참고로, 경쟁 간격 사이즈를 결정하는 방법을 설명하는 흐름도가 도시된다. (120)에 설명되는 단계는 경쟁 간격 사이즈의 결정을 초기화한다. 이어서, 오버로드의 문턱값이 (122)에서 결정되고, 오버로드가 없으면, (124)에 설명된 바와 같이, 시스템이 (126)에서 데이터 전송을 위한 슬롯의 공급을 추정한다. 이어서, 시스템은 (128)에서 설명된 바와 같이 데이터 전송을 위한 슬롯의 수요를 추정하고, (130)에서 공급이 수요와 같아지도록 경쟁 간격 사이즈를 추정한다.

(124)에서 오버로드 상태가 있으면, (132)에 설명된 바와 같이, 오버로드 상태에서 경쟁 처리량을 최대화하는 경쟁 사이즈의 추정이 있다.

도 16을 참고로, 오버로드의 문턱값을 결정하는 방법을 설명하는 흐름도가 도시된다. 여기서, 이는 (134)에서 초기화되고, (136)에서 시스템은 예약 시도 당 요청되는 슬롯의 기대 수와 이전 프레임에서의 슬롯수의 곱으로 나눈 현재 프레임에서의 슬롯 수와 같게 문턱값 오버로드를 설정한다.

도 17을 참고로, 데이터 전송을 위한 슬롯의 공급을 추정하는 방법을 설명하는 흐름도가 도시된다. 여기서, 처리는 (140)에서 시작되어, (142)에서 현재 프레임 사이즈가 구해진다. 이어서, (144)에 설명된 바와 같이, 시스템은 현재 프레임 사이즈 - 경쟁 간격에 할당된 슬롯 수와 같게 공급을 설정한다.

도 18을 참고로, 데이터 전송을 위한 슬롯의 수요를 추정하는 방법을 설명하는 흐름도가 도시된다. (150)에 설명된 바와 같이, 데이터 전송을 위한 슬롯의 요청 추정이 초기화된다. 이어서, (152)에 설명된 바와 같이, 시스템은 예약 요청 당 데이터 전송을 위한 슬롯의 평균수를 구한다. (154)에 설명된 바와 같이, 이는 성공적인 예약 요청의 기대 수를 결정하는 것으로 이어지고, (156)에 설명된 바와 같이, 성공적인 예약 요청의 기대 수와 예약 요청 당 데이터 전송을 위한 슬롯의 평균수의 곱과 같게 수요를 설정하는 것으로 이어진다.

도 19에 설명된 바와 같이, 공급이 수요와 같아지도록 경쟁 간격 사이즈를 추정하는 방법을 설명하는 흐름도가 주어진다. (160)에 설명된 바와 같이, 처리가 시작된다. 이어서, (162)에 설명된 바와 같이, 시스템은 균형식을 구하도록 데이터 전송을 위한 슬롯의 수요 및 공급의 추정을 똑같게 설정한다.

(164)에 설명된 바와 같이, 선형 근사치에 요청조건이 있는가 여부를 확인한다. 그렇지 않은 경우 (166)에 설명된 바와 같이, 균형식이 수적으로 풀려 경쟁 간격 사이즈를 결정한다. 선형 근사화가 필요하면, (168)에 설명된 바와 같이, 시스템은 원하는 경쟁 간격 사이즈에 대한 선형 근사치를 결정한다.

도 20을 참고로, 임시적인 할당을 사용하는 경쟁 스케쥴링을 설명하는 흐름도가 주어진다. (170)에 설명된 바와 같이, 경쟁 스케줄링이 초기화된다. 이어서, (172)에 설명된 바와 같이, 시스템은 새로운 프레임을 할당하고, (174)에서 요청 제공된 로드를 구하는 것으로 이어진다. (176)에 설명된 바와 같이, 시스템은 요청 제공된 로드 및 새로운 프레임의 할당으로부터 임시적인 경쟁 간격 사이즈를 결정한다. 이어서, (178)에 설명된 바와 같이, 시스템은 현재 프레임에 임시적인 경쟁 간격을 할당하고, (180)에서 여분 슬롯이 있는가 여부를 결정한다. 그런 경우, (182)에 설명된 바와 같이, 여분 슬롯은 경쟁 간격에 할당되고, 그 지점에서, 처리는 새로운 프레임을 할당하는 단계로 복귀된다. 여분 슬롯이 없으면, 시스템은 새로운 프레임을 할당하는 단계로 직접 복귀된다.

이제 도 21을 참고로, 임시적인 경쟁 간격 사이즈를 결정하는 제1 방법을 설명하는 흐름도가 도시된다. 이는 (184)에서 초기화되고, (186)에 제공되는 결정은 경쟁 처리량을 최대화하는 경쟁 간격 사이즈를 추정한다.

도 22를 참고로, 경쟁 간격 사이즈를 결정하는 제2 방법을 설명하는 흐름도가 도시되고, (190)에 도시된 바와 같이, 처리는 초기화되어, (192)에서 오버로드의 문턱값을 결정하는 것으로 이어진다. (194)에 설명된 바와 같이, 문턱값은 오버로드 상태인가, 비오버로드 상태인가를 결정하는데 사용되고, (196)에 설명된 바와 같이, 시스템은 비오버로드 영역에서 경쟁 처리량을 최대화하는데 필요로 최대 경쟁 간격 사이즈를 결정한다. 오버로드 상태가 감지되면, (198)에 설명된 바와 같이, 추정은 경쟁 처리량을 최대화하는 경쟁 간격 사이즈로 구성된다.

도 23을 참고로, 경쟁 간격 사이즈를 결정하는 제3 방법을 설명하는 흐름도가 도시된다. (200)에 설명된 바와 같이, 처리가 시작되어, (202)에서 오버로드의 문턱값을 결정하는 것으로 이어진다. (204)에 설명된 바와 같이 오버로드된 상태가 없으면, (206)에서 시스템은 균형식에 대한 선형 하한값을 결정한다. 오버로드 상태가 있으면, (208)에 설명된 바와 같이, 시스템은 경쟁 처리량을 최대화하는 경쟁 간격 사이즈를 추정한다.

이제 도 24를 참고로, 경쟁 처리량을 최대화하는 경쟁 간격 사이즈를 추정하는 방법을 설명하는 흐름도가 도시된다. (210)에 설명된 바와 같이, 추정 처리가 시작되어, (212)에 설명된 바와 같이, 이전 프레임에서의 요청 제공된 로드, 이전 프레임에서의 슬롯 수, 및 경쟁 기회 당 슬롯수의 곱과 같게 경쟁 간격 사이즈를 설정하는 것으로 이어진다.

도 25에 설명된 바와 같이, 비오버로드 영역에서 경쟁 처리량을 최대화하는데 필요로 하는 최대 경쟁 간격 사이즈를 결정하는 방법을 설명하는 흐름도가 도시된다. (214)에 설명된 바와 같이, 처리가 시작되어, (216)에서 시스템이 예약 시도 당 요청되는 슬롯의 기대수로 나눈 경쟁 기회 당 슬로 수와 프레임에서의 슬롯수의 곱과 같게 경쟁 간격 사이즈를 설정하는 것으로 이어진다.

이제 도 26을 참고로, 균형식에 대한 해에서 선형 하한값을 결정하는 흐름도가 도시된다. 여기서, 처리는 (220)에 설명된 바와 같이 시작되고, (222)에서 2.7183으로 나뉜 오버로드 문턱값보다 요청 제공된 로드가 더 큰가 여부를 결정하는 것으로 이어진다. 그렇지 않은 경우, (224)에 설명된 바와 같이, 경쟁 간격 사이즈는 현재 프레임에서의 슬롯 수 - 프레임에서의 성공적인 요청 전송으로 인해 데이터 전송을 위한 슬롯에서 최대로 이루어질 수 있는 이동-조정 수요와 같게 설정된다. 이어서, (226)에 설명된 바와 같이, 시스템은 예약 시도 당 요청되는 슬롯의 기대수로 나뉜 경쟁 기회 당 슬롯 수와 프레임에서의 슬롯수의 곱과 같게 경쟁 간격 사이즈를 설정된다.

요청 제공된 로드가 2.7183으로 나뉜 오버로드 문턱값보다 더 크면, 처리는 (226)에 설명된 처리로 점프된다.

ρ의 값을 적절하게 감소시킴으로서 주된 시스템에서 피기백킹 로드가 명확하게 고려될 수 있음을 주목하여야 한다. 경쟁에 대한 요청 제공된 로드는 피기백킹에 의해 감소될 수 있지만, 그 결과로 경쟁 요청 당 데이터 전송 슬롯에 대한 유효 수요가 그에 따라 증가된다. 예를 들어, 요청 당 데이터 패킷에 예약되는 슬롯의 평균수를 추정하는 특정 방법은 피기백킹의 효과를 고려하면서 Sala 등에 의해 개요가 주어졌다.

분할 오버헤드는 ρ의 값을 적절하게 감소시킴으로서 명확하게 고려될 수 있음을 주목하여야 한다. 데이터 패킷이 더 작은 패킷으로 분할될 때, 더 작은 패킷은 각각 원래 패킷내의 더 작은 패킷의 위치뿐만 아니라 원래 패킷을 특히 식별하도록 분할 헤더와 연관된다.

프레임에 대한 할당을 결정할 때 각 프레임의 사이즈가 고정되거나 공지되어 있으면, 프레임에서 경쟁 기회를 할당하는데 본 발명을 적용하는 것은 수월하다. 각 프레임의 사이즈가 미리 공지되어 있지 않지만, 소정의 최소값 T_min내지 소정의 최대값 T_max에서 변하고, T_max- T_min이 적어도 가장 큰 패킷의 사이즈이면, 본 발명은 이러한 변화를 수용하도록 수정될 수 있다. 이 경우, T[k], 현재 프레임의 사이즈는 초기에 T_min인 것으로 가정되고, 임시적인 수의 슬롯이 프레임(k)의 경쟁 간격에 먼저 할당되어, 이 임시적인 할당은 적어도 소정의 프레임 사이즈의 경우에서의 할당만큼 보존된다. 데이터 전송을 위해 나머지 슬롯을 할당한 이후에 프레임에 여분 슬롯이 있으면, 그 여분 슬롯은 프레임의 경쟁 간격에 포함된다.

T_min≤ T[k] ≤ T_max인 것으로 공지되면, 제2 실시예는 도 12에 도시된 바와 같이 수정될 수 있다. 특정하게, 프레임(k)의 경쟁 간격에 먼저 할당된 슬롯 수는 다음과 같이 주어진다.

M[k] = max {g[k-1]T[k-1]R, b(H,R,ρ)T_minR}

동일하게, 범위 0 ≤ g[k-1] ≤ g'₀= b(H,R,ρ)T_min/T[k-1]의 요청 제공된 로드에 대해서는 M[k] = b(H,R,ρ)T_minR이고, 더 높은 요청 제공된 로드에 대해서는 M[k] = g[k-1]T[k-1]R이다.

도 12에 설명된 바와 같이, 제2 실시예의 상기 변형은 제2 실시예의 특성을 많이 유지한다. 특정하게, 할당 방법은 두 선형 세그먼트를 갖는 요청 제공된 로드의 선형 함수에 기초하여, 0 내지 거의 오버로드 문턱값과 같은 범위의 요청 제공된 로드에 대해 0이 아닌 일정한 값을 갖고, 그렇지 않은 경우에는 요청 제공된 로드와 비례적으로 증가된다.

T_min≤ T[k] ≤ T_max인 것으로 공지되면, 제3 실시예는 도 13에 도시된 바와 같이 수정될 수 있다. 특정하게, 프레임(k)의 경쟁 간격에 먼저 할당된 슬롯의 수는 다음과 같이 주어진다.

M[k] = max{g[k-1]T[k-1]R, b(H,R,ρ)T_minR, (T_min- g[k-1]T[k-1]H/ρ)}

동일하게, 범위 0 ≤ g[k-1] ≤ g'₀/e의 요청 제공된 로드에 대해서는 M[k] = T_min- g[k-1]T[k-1]H/ρ이고, g'₀/e ≤ g[k-1] ≤ g'₀의 요청 제공된 로드에 대해서는 M[k] = b(H,R,ρ)T_minR이고, 더 높은 요청 제공된 로드에 대해서는 M[k] = g[k-1]T[k-1]R이다. 여기서, g'₀= b(H,R,ρ)T_min/T[k-1]이다.

도 13에 설명된 바와 같이, 제3 실시예의 상기 변형은 제3 실시예의 특성을 많이 유지한다. 특정하게, 할당 방법은 3가지 선형 세그먼트를 갖는 요청 제공된 로드의 선형 함수에 기초하여, 요청 제공된 로드가 가벼울 때 그 값은 선형으로 감소되고, 요청 제공된 로드가 적절할 때 0 아닌 일정한 값을 갖고, 시스템이 오버로드될 때 요청 제공된 로드와 비례적으로 증가된다.

제2 실시예의 변형 및 제3 실시예의 변형 모두에서, 데이터 전송을 위한 나머지 슬롯을 할당한 이후 프레임에 여분 슬롯이 있으면, 여분 슬롯은 프레임의 경쟁 간격에 포함된다.

데이터 간격에서 슬롯의 초기 할당 이후에는 진행중인 전송에서 추가 패킷 또는 패킷 일부를 수용하기에 충분하지 않은 슬롯이 프레임의 나머지 부분에 있을 가능성이 있다. 이 경우에는 프레임이 패킷 또는 패킷 부분을 수용하는데 필요한 만큼 확장된다. (T_max- T_min)가 적어도 가장 큰 패킷의 사이즈라 가정하면, 결과의 프레임 사이즈는 위에서 T_max만큼 한정된다.

지금은 본 발명의 몇 가지 실시예 및 그에 대한 수정과 변형이 설명되었지만, 종래 기술에 숙련된 자에게는 상기가 단순히 설명을 위한 것으로 제한되지 않고, 예로만 주어진 것임이 명백하다. 다양한 수정 및 다른 실시예가 종래 기술에 숙련된 자의 범위 내에 있고, 이는 첨부된 청구항 및 그에 동일한 것에 의해서만 제한되는 본 발명의 범위 내에 포함되는 것으로 생각된다.

Claims

공유 슬롯 채널(shared slotted channel)이 경쟁-기반 예약 요청들(contention-based reservation requests)의 전송을 위한 경쟁 간격 및 경쟁 없는 데이터 패킷들(contention-free data packets)의 전송을 위한 데이터 간격을 각각 포함하는 연속적인 프레임들로 분할되는 공유 매체 통신 네트워크에서 경쟁 간격 사이즈를 선택하는 방법에 있어서,

이전 지식(priori knowledge)에 기초하여 네트워크에서 요청 제공된 로드(request offered load)를 지정하는 단계 또는 경쟁 결과들의 내력에 기초하여 네트워크에서 요청 제공된 로드를 추정하는 단계와;

상기 요청 제공된 로드의 볼록 함수가 되도록 상기 경쟁 간격 사이즈를 선택하는 단계를 포함하고,

상기 볼록 함수는 단일 최소값을 갖고, 상기 함수가 최소값을 갖는 지점까지 요청 제공된 로드에 대해 증가하지 않고, 더 큰 요청 제공된 로드에 대해서 감소하지 않는, 경쟁 간격 사이즈 선택 방법.
제 1 항에 있어서,

각각의 경쟁 간격은 각각이 슬롯들의 미리 결정된 수로 구성되는 다수의 경쟁 기회들로 구성되고, 상기 경쟁 결과들은 각각의 경쟁 기회에서 전송되는 요청들의 수에 의해 결정되고, 전송되는 요청이 없는 경우에 상기 경쟁 결과는아이들(idle)이라 하고; 단일 요청이 전송되는 경우에 상기 경쟁 결과는 성공(success)이라 하고; 다수의 요청들이 전송될 때 상기 경쟁 결과는 충돌(collision)이라 하는, 경쟁 간격 사이즈 선택 방법.
제 2 항에 있어서,

상기 요청 제공된 로드의 볼록 함수인 경쟁 간격 사이즈는,

경쟁 없는 데이터 패킷들의 전송을 위한 슬롯들의 공급과;

경쟁 없는 데이터 패킷들의 전송을 위한 슬롯들의 수요의 추정들을 한 프레임씩 균형을 맞추는 방법으로부터 유도되는, 경쟁 간격 사이즈 선택 방법.
제 3 항에 있어서,

현재 프레임에서 경쟁 없는 데이터 패킷들의 전송을 위한 데이터 슬롯들의 공급의 추정은 그 프레임에서의 슬롯들의 수 -(마이너스) 상기 프레임의 경쟁 간격에 할당된 슬롯들의 수인, 경쟁 간격 사이즈 선택 방법.
제 4 항에 있어서,

현재 프레임에서 경쟁 없는 데이터 패킷들의 전송을 위한 슬롯들의 요청 추정은,

이전 지식에 기초하여 각각의 수용된 예약 요청에 의해 예약된 데이터 슬롯들의 평균 수를 지정하거나, 또는 예약 요청들의 내력에 기초하여 각각의 수용된예약 요청에 의해 예약된 데이터 슬롯들의 평균수를 추정하는 단계;

상기 현재 프레임의 경쟁 간격에서 성공적으로 전송될 예약 요청들의 기대 수를 결정하는 단계와;

각각의 수용된 예약 요청에 의해 예약된 데이터 슬롯들의 평균수와 예약 요청들의 기대 수를 곱하는 단계를 포함하는 방법으로부터 유도되는 것을 특징으로 하는 방법.
제 5 항에 있어서,

상기 현재 프레임의 경쟁 간격에서 성공적으로 전송될 예약 요청들의 기대 수는 이용 가능한 공유 대역폭의 원하는 이용률을 고려하는 인자에 의해 조정되는, 경쟁 간격 사이즈 선택 방법.
제 1 항에 있어서,

상기 볼록 함수가 그 최소값을 갖는 요청 제공된 로드의 값은 예약 시도 당 요구된 슬롯들의 기대 수와 이전 프레임에서의 슬롯들의 수의 곱으로 나눈 상기 현재 프레임에서의 슬롯들의 수와 같고, 예약 시도 당 요구된 슬롯들의 기대 수는 예약 시도 당 데이터 전송에 요청되는 슬롯들의 기대 수와 경쟁 기회 당 슬롯들의 수의 합인, 경쟁 간격 사이즈 선택 방법.
제 7 항에 있어서,

상기 볼록 함수가 그 최소값을 갖는 제공된 로드의 값은 실행할 수 있는 모든 요청 제공된 로드들의 값들의 범위를 2개의 동작 영역들로 나누고, 각각의 영역은 상기 경쟁 간격에 대역폭을 할당하기 위한 다른 방책을 갖는, 경쟁 간격 사이즈 선택 방법.
제 8 항에 있어서,

한 영역은, 비오버로드 영역(non-overload region)이고, 상기 볼록 함수가 그 최소값을 갖는 요청 제공된 로드의 값 보다 더 작은 요청 제공된 로드 값들로 구성되고, 다른 영역은, 오버로드 영역이고, 적어도 볼록 함수가 그 최소값을 갖는 요청 제공된 로드의 값만큼 큰 요청 제공된 로드 값들로 구성되는, 경쟁 간격 사이즈 선택 방법.
제 9 항에 있어서,

상기 제공된 로드가 비오버로드 영역에 들 때, 상기 경쟁 간격에 대역폭을 할당하기 위한 방책은,

경쟁 없는 데이터 패킷들의 전송을 위한 슬롯들의 수요 및 공급의 균형을 맞추는데 필요한 슬롯들의 수의 하한값에 기초하여 슬롯들의 임시적인 수를 상기 경쟁 간격에 할당하거나, 또는 데이터 전송을 위해 허용 가능한 만큼 많은 예약된 슬롯들을 상기 데이터 간격에 할당하는 단계와;

어떤 여분 슬롯들이 있으면, 경쟁 기회들로 상기 프레임의 나머지 부분을 채우는 단계 중 하나를 포함하는, 경쟁 간격 사이즈 선택 방법.
제 10 항에 있어서,

경쟁 없는 데이터 패킷들의 전송을 위한 슬롯들의 공급 및 수요의 균형을 맞추는데 필요한 슬롯들의 수의 하한값은 요청 제공된 로드가 주어진 상기 경쟁 간격에서의 경쟁 처리량을 최대화하는데 필요한 슬롯들의 수인, 경쟁 간격 사이즈 선택 방법.
제 10 항에 있어서,

경쟁 없는 데이터 패킷들의 전송을 위한 슬롯들의 공급 및 수요의 균형을 맞추는데 필요한 슬롯들의 수의 하한값은 비오버로드 영역 내의 어떤 요청 제공된 로드가 주어진 상기 경쟁 간격에서의 경쟁 처리량을 최대화하는데 필요한 슬롯들의 최대수인, 경쟁 간격 사이즈 선택 방법.
제 10 항에 있어서,

경쟁 없는 데이터 패킷들의 전송을 위한 슬롯들의 공급 및 수요의 균형을 맞추는데 필요한 슬롯들의 수의 하한값은 상기 제공된 로드의 선형 함수 및 비오버로드 영역 내에의 어떤 제공된 로드가 주어진 경쟁 간격에서의 경쟁 처리량을 최대화하는데 필요한 슬롯들의 최대수의 최대값이고, 상기 제공된 로드가 0값을 가질 때, 상기 함수는 상기 프레임 사이즈와 같은 값을 갖고;

상기 제공된 로드가 e로 나누어진, 오버로드의 문턱값에서 제공된 로드의 값과 같은 값을 가질 때, 상기 함수는 비오버로드 영역 내의 어떤 요청 제공된 로드가 주어진 경쟁 간격에서의 경쟁 처리량을 최대화하는데 필요한 슬롯들의 최대 수와 같은 값을 갖는, 경쟁 간격 사이즈 선택 방법.
공유 슬롯 채널이 경쟁-기반 예약 요청들의 전송을 위한 경쟁 간격과 경쟁 없는 데이터 패킷들의 전송을 위한 데이터 간격을 각각 포함하는 연속적인 프레임들로 분할되는 공유 매체 통신 네트워크에서 경쟁 간격 사이즈를 선택하는 방법에 있어서,

이전 프레임에서 요청 제공된 로드를 확인하는 단계와;

상기 경쟁 간격을 지정하도록 상기 이전 프레임에서 요청 제공된 로드를 확인함으로써 결정된 요청 제공된 로드를 이용하는 단계를 포함하는 경쟁 간격 사이즈 선택 방법.
제 14 항에 있어서,

상기 이전 프레임에서 요청 제공된 로드는 연역적으로 확인되는, 경쟁 간격 사이즈 선택 방법.
제 14 항에 있어서,

상기 이전 프레임에서 상기 요청 제공된 로드는 추정되는, 경쟁 간격 사이즈선택 방법.
제 14 항에 있어서,

상기 경쟁 간격을 지정하는 단계는 상기 확인된 요청 제공된 로드에 기초하여 경쟁 처리량을 최대화하는 할당을 하는 단계를 포함하는, 경쟁 간격 사이즈 선택 방법.
제 14 항에 있어서,

상기 경쟁 간격을 지정하는 단계는 상기 요청 제공된 로드의 비오버로드 영역 및 오버로드 영역을 제공하는 단계, 상기 비오버로드 영역에 대한 데이터 전송을 위한 슬롯들의 공급 및 수요의 균형을 맞추는데 요구된 최소 할당을 하는 단계와, 오버로드 영역에 대한 경쟁 처리량을 최대화하는 할당을 하는 단계를 포함하는, 경쟁 간격 사이즈 선택 방법.
제 14 항에 있어서,

상기 경쟁 간격을 지정하는 단계는 상기 요청 제공된 로드의 가벼운 로드 영역, 적절한 로드 영역, 및 오버로드 영역을 제공하는 단계, 상기 가벼운 로드 영역에 대해 요청 제공된 로드의 선형으로 감소하는 함수인 할당을 하는 단계, 상기 적절한 로드 영역에 대한 데이터 전송을 위한 슬롯들의 공급 및 수요의 균형을 맞추는데 요구된 최소 할당을 하는 단계와, 상기 오버로드 영역에 대한 경쟁 처리량을최대화하는 할당을 하는 단계를 포함하는, 경쟁 간격 사이즈 선택 방법.