BRPI0621617A2

BRPI0621617A2 - primeira transmissão mais antecipada de taxa normalizada baseada em limiar (nredf) para serviços de carregamento retardado

Info

Publication number: BRPI0621617A2
Application number: BRPI0621617-0A
Authority: BR
Inventors: Yang Guo; Jun Li; Kumar Ramaswamy
Original assignee: Thomson Licensing
Priority date: 2006-05-05
Filing date: 2006-05-05
Publication date: 2011-12-13
Also published as: CN101432730A; JP4890610B2; CN101432730B; KR101353406B1; US20090113054A1; EP2016508A1; WO2007130038A1; JP2009536498A; US8650293B2; KR20090015029A

Abstract

PRIMEIRA TRANSMISSãO MAIS ANTECIPADA DE TAXA NORMALIZADA BASEADA EM LIMIAR (NREDF) PARA SERVIçOS DE CARREGAMENTO RETARDADO. Trata-se de um sistema de transmissão de conteúdo compreendendo pelo menos um servidor de conteúdo que serve um número de solicitações de cliente. O servidor de conteúdo usa um programador de Primeira Transmissão Mais Antecipada de Taxa Normalizada Baseada em Limiar (TB-NREDF). O programador TB-NREDF impõe um valor limiar, ou limite, no número de reprogramação de solicitações.

Description

"PRIMEIRA TRANSMISSÃO MAIS ANTECIPADA DE TAXA NORMALIZADA BASEADA EM LIMIAR (NREDF) PARA SERVIÇOS DE CARREGAMENTO RETARDADO"

ANTECEDENTES DA INVENÇÃO

A presente invenção refere-se, em geral, a sistemas de comunicações. Especifica- mente, esta invenção se refere à transmissão de conteúdo e redes de distribuição e compo- nentes dos mesmos, por exemplo, um servidor de conteúdo, etc.

Em um sistema de transmissão, um servidor de conteúdo pode distribuir diferentes tipos de conteúdo, por exemplo, arquivos, vídeo de fluxo contínuo, etc., para diferentes cli- entes por via de uma rede de comunicação distribuída como, por exemplo, a Internet. Tipi- camente, esse processo é iniciado por cada cliente enviando uma solicitação para conteúdo específico para o servidor de conteúdo. À medida que cada solicitação é recebida, o servi- dor de conteúdo programa a transmissão do conteúdo solicitado para o cliente solicitante, por via da por via de rede de comunicações distribuídas.

Uma abordagem para a programação de transmissão de conteúdo para um cliente (ou usuário) por via de uma rede de comunicações distribuídas é a abordagem "Primeira Transmissão Mais Antecipada de Taxa Normalizada" (NREDF) (também algumas vezes referida na forma abreviada como "NRED"). Nessa abordagem, o servidor de conteúdo computa uma taxa normalizada para a transmissão de conteúdo específico usando um "ca- minho mais curto" estimado entre o servidor de conteúdo e cada cliente solicitante. O "cami- nho mais curto" é aquele no qual o caminho através da rede de comunicações distribuídas que proporciona o tempo de transmissão mais antecipado do conteúdo solicitado para o cliente solicitante. Como parte desse processo, o servidor de conteúdo pode identificar ou- tros servidores na rede que possam fornecer o conteúdo solicitado para transmissão. O ser- vidor de conteúdo então programa a transmissão de todas as solicitações de cliente recebi- das na ordem decrescente de suas taxas normalizadas computadas associadas. Como tal, um cliente solicitante com uma taxa normalizada computada mais alta é programado para transmissão antes de um cliente solicitante com uma taxa normalizada computada mais bai- xo. Contudo, podem continuar a chegar novas solicitações de cliente mesmo após o servidor de transmissão de conteúdo ter acabado de terminar a programação das solicitações de cliente anteriormente recebidas (ou antigas). Nessa situação, à medida que as novas solici- tações de cliente chegam, aquelas solicitações de cliente antigas não terminadas são pro- gramadas juntas com quaisquer novas solicitações de cliente a fim de maximizar o número de solicitações que possam ser servidas pelo servidor de conteúdo.

Infelizmente, à medida que aumenta a taxa de solicitação de cliente, o servidor de conteúdo começa a despender cada vez mais tempo apenas computando as taxas normali- zadas e reprogramando as solicitações antigas em vez de realmente transmitir conteúdo. Esse comportamento arrisca a programabilidade da abordagem NREDF para servir grandes números de clientes.

SUMÁRIO DA INVENÇÃO

Foi observado que o servidor de conteúdo usando um programador Primeira Transmissão Mais Antecipada de Taxa Normalizada (NREDF) não programa conveniente- mente como a taxa de solicitação de cliente aumenta uma vez que o código extra de compu- tação para reprogramar solicitações antigas admitindo novas solicitações também aumenta. Portanto, e de acordo com os princípios da invenção, um servidor de conteúdo usando um programador Primeira Transmissão Mais Antecipada de Taxa Normalizada (NREDF) limita o número de solicitações antigas que são reprogramadas até um valor limiar.

Em uma modalidade ilustrativa da invenção, um sistema de transmissão de conteú- do compreende pelo menos um servidor de conteúdo que sirva um número de solicitações de clientes. O servidor de conteúdo usa um programador de Primeira Transmissão Mais Antecipada de Taxa Normalizada Baseada em Limiar (TB-NREDF). O programador TB- NREDF impõe um valor limiar, ou limite, no número de solicitações de reprogramação. Por- tanto, o servidor de conteúdo é dotado da habilidade de limitar o código extra de reprogra- mação, que também permite que o servidor de conteúdo "tradeoff" (é uma expressão que define uma situação em que há conflito de escolha) programabilidade contra a execução do sistema.

Em outra modalidade ilustrativa da invenção, a abordagem Primeira Transmissão Mais Antecipada de Taxa Normalizada Baseada em Limiar (TB-NREDF) define um limiar relembrado, T, que representa o número máximo de antigas solicitações que serão repro- gramadas. Por exemplo, permita R(t) indicar um conjunto de solicitação que inclui solicita- ções de clientes antigas inacabadas em um tempo t, juntamente com quaisquer novas solici- tações de cliente que cheguem no tempo t. Permita Q ser o número total de solicitações em R(t) e K representarem o número total de antigas solicitações em R(t). A abordagem TB- NREDF reprograma no máximo antigas solicitações T, onde T < K <Q. Portanto, as progra- mações para as antigas solicitações K-T remanescentes são inalteradas.

BREVE DESCRIÇÃO DOS DESENHOS

As Figuras de 1 a 6 ilustram um sistema de transmissão do estado da técnica u- sando um processo de reprogramação de primeira transmissão mais antecipada de taxa normalizada;

A Figura 7 ilustra um diagrama em bloco ilustrativo de um sistema de transmissão de conteúdo de acordo com os princípios da invenção;

A Figura 8 ilustra um diagrama em bloco ilustrativo de um servidor de conteúdo in- corporando os princípios da invenção;

A Figura 9 ilustra um conjunto de programação ilustrativo de acordo com os princí- pios da invenção; A Figura 10 ilustra um fluxograma ilustrativo para uso em um servidor de conteúdo de acordo com os princípios da invenção; e

As Figuras de 11 a 13 ilustram outra modalidade ilustrativa para uso em um servi- dor de conteúdo de acordo com os princípios da invenção.

DESCRIÇÃO DETALHADA DA INVENÇÃO

De outra maneira, o conceito inventivo, os elementos ilustrados nas figuras são bem conhecidos e não serão descritos detalhadamente. Ainda, é suposta a familiaridade com a rede (e protocolos usados na mesma) e não descrita aqui em detalhes. Por exemplo, de outra maneira é suposta o conceito inventivo, a familiaridade com o Protocolo da Internet (PI), Protocolo de Transporte de Tempo Real (RTP), e o Protocolo de Controle de Transmis- são (TCP). Do mesmo modo, de outra maneira é suposto o conceito inventivo, a familiarida- de com a os componentes de rede como, por exemplo, servidores, nós de borda e cliente. Similarmente, de outra maneira o conceito inventivo os métodos de formatação e codifica- ção como, por exemplo, os Sistemas Padrões (ISSO/IEC 13818-1) Grupo de Especialistas em Imagens em Movimento (MPEG)-2 e H:264: União de Telecomunicação Internacional, "Recomendação ITU-T H.264: Codificação de Vídeo Avançado para Serviços Audiovisuais Genéricos", ITU-T, 2003, para gerar fluxos de bit são bem conhecidos e não estão aqui des- critos. A esse respeito, deve ser observado que está descrita abaixo nas figuras apenas a parte do concito inventivo que difere dos sistemas servidor / cliente conhecidos. Deve ser observado que o conceito inventivo pode ser executado usando técnicas de programação convencionais, que, como tal, também são serão aqui descritas. Finalmente, números seme- lhantes nas figuras representam elementos semelhantes.

Antes de descrever o conceito inventivo, será proporcionada uma breve descrição do processo de programação da Primeira Transmissão Mais Antecipada de Taxa Normali- zada (NREDF). A esse respeito, um sistema de transmissão coerente usando o processo de programação NREDF está ilustrado na Figura 1. O sistema de transmissão de conteúdo compreende um servidor de conteúdo 20, uma rede de comunicações 10 e um ou mais cli- entes, conforme representado pelo cliente 50-1 e 50-2. O Servidor de conteúdo 20, o cliente 50-1 e o cliente 50-2 são representativos das plataformas de processador baseado em con- trole de programa armazenado. Por exemplo, o cliente 5-1 pode ser um computador pessoal baseado em microprocessador de mesa e o cliente 50-2 pode ser um telefone celular. Ao mesmo tempo em que o servidor de conteúdo 20 é um servidor baseado em multiprocessa- dor (alto desempenho). Ilustrativamente, a rede de comunicações 10 é representativa da Internet compreende as facilidades tanto comutadas quanto não comutadas, conforme co- nhecido na técnica e inclui, por exemplo, roteadores, dispositivos de nó de borda, etc. (nem todos ilustrados na Figura 1). Nesse exemplo, e conforme pode ser observado da Figura 1, o servidor de conteúdo 20 é representado como estando situado em algum lugar na Internet com um endereço de Protocolo da Internet associado (IP). Além disso, conforme ilustrado na Figura 1, a rede de comunicações 10 pode também compreender uma rede de transmis- são de conteúdo (CDN) 15. Conforme conhecido na técnica, uma CDN é uma rede de s5uperposição de segmento (pública ou privada) projetada para transmitir seguramente con- teúdo proveniente dos servidores de conteúdo (provedores) para clientes, ao mesmo tempo em que reduz custos e aumenta as velocidades do cliente (usuário final). Como tal, os ou- tros servidores na CDN podem também fornecer conteúdo solicitado sob o controle do ser- vidor de conteúdo 20. O formato desse conteúdo pode ser conteúdo estático (por exemplo, conteúdo de site da web, arquivos) ou conteúdo dinâmico (isto é, conteúdo que muda rapi- damente) e/ou fluxo contínuo de áudio / vídeo. No contexto da Figura 1, os clientes 50-1 e 50-2 enviam solicitações para conteúdo para o servidor de conteúdo 20. Em resposta a es- sas solicitações, o servidor de conteúdo 20 programa transmissão usando o processo de programação NREDF e transmite, ou envia, o conteúdo solicitado para o cliente respectivo por via de um caminho através da rede de comunicações. Por exemplo, o conteúdo, por exemplo, um arquivo, solicitado pelo cliente 50-1 é proporcionado para o cliente 50-1 por via do caminho ilustrativo 11, que, nesse exemplo, também percorre a CDN 15. O caminho 11 representa quaisquer facilidades e dispositivos de rede de comunicações 10 através da qual o conteúdo solicitado é transportado para o cliente 50-1.

Voltando agora à Figura 2, está ilustrado um diagrama de bloco de nível alto do servidor de conteúdo 20. O Servidor de conteúdo 20 recebe solicitações de cliente 59 por via da conexão 19, que acopla o servidor de conteúdo 20 a Internet 10. O servidor de conte- údo 20 compreende um programador NREDF 60, que processa as solicitações de cliente recebidas 59 e gera um conjunto de programação, S(t), 70, para proporcionar o conteúdo solicitado para os clientes solicitantes. As Figuras 3 e 4 ilustram um fluxograma ilustrativo representando um processo de programação NREDF para ser usado pelo servidor de con- teúdo 20. Para o processo de programação NREDF, são usadas as seguintes definições:

N = {nj, j=0,...,J}-é o conjunto de nó de rede, que inclui um servidor de conteúdo (j=0), I servidores de borda (j=1,...,l) e clientes U (j=I+1,..., I+U=J);

Ci(t) - é a capacidade de cache no nó j-th, que é uma função variante de tempo;

C,(t) - é o conjunto de status de cache no nó j-th no tempo t, isto é, uma lista de conteúdo cached;

L={(j1,j2)j1,j2 € N} - é o conjunto de link de rede, onde (J1J2) é o link do nó j1 para o nó j2;

b(i,j,t) - é a capacidade de link de (ij), que é uma função variante de tempo;

B(i,j,t) - é o status de link de (i,j) no tempo t, que é uma lista de conteúdo de trans- missão;

R(t0)=(rq, q=1...Q) - é ρ conjunto de solicitação, que representa todas as solicitações feitas pelo cliente para o servidor de conteúdo por tempo t =t0. onde:

rq=(mq, dq, Uq) - é uma solicitação representada pelo conteúdo ID1 tempo devido e solicitação de cliente ID1 e

mq - é um conteúdo ID com um tamanho de conteúdo \mq\ e uma taxa de fluxo con- tínuo de tempo real ||mq,||,

dq - é um tempo devido para solicitação rq, e

Uq- é o cliente ID para o cliente que fez a solicitação, a partir da qual o local geográ- fico pode ser identificado;

S(to)=(Sq(j1,j2),j1,j2) C L)é o conjunto de programação para o conjunto de solicitação R(t0), onde,

Sqljijd - é o tempo (início) de programação para solicitação rq a ser transportada em Q1J2), isso é inicializado para um valor 0; e

&qÚ'iJz)' e o tempo de programação, (término) para a solicitação rq a ser transporta- da no Q1Jz), e se o conteúdo solicitado for transmitido na taxa de ||mq|| então eq(j1,j2)=Sq(j1,j2)+(\mq\ /\\mq\\\ e

Taxa Normalizada v*q(t) da solicitação rq, onde: v*q(t) = \mq\/(dq-t).(1)

Na etapa 205 da Figura 3, para cada solicitação de cliente no tempo, to, no conjunto de solicitação R(t0), o servidor de conteúdo 20 calcula a taxa normalizada de acordo com a 20 equação (1) acima. Na etapa 210, o servidor de conteúdo 20 classifica as solicitações de cliente em ordem decrescente de suas taxas normalizadas calculadas para proporcionar uma lista de solicitação de cliente classificada. Na etapa 215, o servidor de conteúdo 20 programa o conteúdo para transmissão de acordo com a ordem ilustrada na lista de solicita- ção de cliente classificada. Referindo-se agora à Figura 4, está ilustrado um fluxograma mais detalhado da etapa 215. As etapas de 255 a 275 da Figura 4 são executadas para ca- sa solicitação rq, no conjunto de solicitação R(t0) de acordo com a lista de solicitação de cli- ente classificada na etapa 210 da Figura 3. Como resultado, o programa para uma solicita- ção específica rq, {Sq,(j,k),(j,k) C L}, é feito baseado nos vetores de programação feitos ante- riormente {sx(j,k)\ x=0,...,q-1}. Especificamente, na etapa 255 da Figura 4, o servidor de con- teúdo 20 seleciona a solicitação seguinte, rq=(mq, dq, Uq), para programação a partir da lista de solicitação de cliente classificada. Na etapa 260, o servidor de conteúdo 20 identifica um conjunto de servidores Hq que estão disponíveis para classificação no conteúdo solicitado para a solicitação, rq onde o conjunto de servidores inclui pelo menos um servidor, por e- xemplo, o servidor de conteúdo 20. (A habilidade para um servidor de conteúdo identificar um conjunto de servidores disponíveis para fornecer conteúdo para uma solicitação de clien- te é conhecida na técnica e não descrita aqui). Nesse conjunto de servidores, Hq, cada ser- vidor /' é dotado de mq C Mifti) uma fonte de conteúdo mq para a solicitação rq, onde tj=max[sP(j,i), p<q], o último tempo cache no servidor /'é atualizado. Na etapa 265, o servidor de conteúdo 20 encontra o caminho mais curto que proporciona o tempo de transmissão mais antecipada do conteúdo solicitado mq para o destino uq. Por exemplo, o servidor de conteúdo 20 usa um algoritmo de caminho mais curto de múltiplas fontes (por exemplo, al- goritmo de Dijkstra conforme conhecido na técnica) para encontrar o caminho mais curto de qualquer servidor i € Hq a uq. Na etapa 270, o servidor de conteúdo 20 encontra o programa {Sq(j,k),(j,k) C L} e atualiza o cache {Mj(t), iCN} para links e servidores no caminho seleciona- do, respectivamente, aplicando restrições na capacidade de link e capacidade cache con- forme conhecido na técnica. (Deve ser observado que, se max[sq(j,k), Q,k) C L]>dq, então a tentativa de programação falhou para encontrar um conjunto de programação para R(t0) e o processo é abortado). Finalmente, na etapa 275, é feita uma verificação se todas as solicita- ções foram ou não processadas, isto é se qf = Q. Se houver mais solicitações para progra- mar,.isto é, q<Q, o valor de q é aumentado, isto é,>q = q+1, e a execução retorna para a eta- pa 255 para a solicitação seguinte na lista de solicitação de cliente classificada. Contudo, se todas as solicitações tiverem sido programadas, então a execução termina.

Como resultado da programação das solicitações no conjunto de solicitação R(t0), o servidor de conteúdo 20 cria um conjunto de programação para transmissão de conteúdo solicitado. Uma representação ilustrativa do conjunto de programação 81 para solicitações Q a tempo, t0, está ilustrada na Figura 5. O servidor de conteúdo 20 irá então continuar a libe- rar conteúdo de acordo com o conjunto de programação 81, onde as solicitações individuais foram priorizadas em termos de taxa normalizada calculada conforme representada pela seta 84, que indica a direção da ordem descendente.

Contudo, após o tempo t0 podem chegar novas solicitações em um tempo, t. Além disso, nesse tempo, t, o servidor de conteúdo 20 pode ter terminado a transmissão de algum conteúdo solicitado anteriormente, ao mesmo tempo em que as solicitações de cliente re- manescentes ainda estão pendentes, isto é, são "antigas". Em termos de uma, ou mais, no- vas solicitações, algumas delas podem ser dotadas de um tempo devido anterior, ou um arquivo solicitado maior do que algumas outras solicitações antigas. Como tal, pode ser o caso de que as taxas normalizadas de uma, ou mais, novas solicitações no tempo t podem ser maiores do que algumas das solicitações antigas. A fim de maximizar o número de soli- citações que possam ser servidas pelo servidor de conteúdo 20, as antigas solicitações K, juntamente com quaisquer novas solicitações no tempo, t, são reprogramadas usando o processo NREDF descrito acima. Portanto, uma nova solicitação no tempo, t, R(t), é deter- minada e o processo ilustrado nas Figuras 3 e 4 é repetido para produzir um novo conjunto de programação 83 para transmissão do conteúdo. Isso está ilustrado na Figura 6, onde uma, ou mais novas solicitações 82, foram programadas, e ainda há antigas solicitações K pendentes no novo conjunto de programação 83. Apenas com propósitos ilustrativos, a transmissão de solicitações de cliente anteriormente programadas está ilustrada em forma de linha tracejada na Figura 6 uma vez que as mesmas foram soltas do novo conjunto de programação 83.

Infelizmente, à medida que aumenta a taxa de solicitações de cliente, o servidor de conteúdo 20 começa a despender cada vez mais tempo apenas para computar as taxas normalizadas e reprogramar as solicitações antigas em vez de realmente transmitir conteú- do. Portanto, o tempo de computação requerido para admitir novas solicitações aumenta proporcionalmente. Esse comportamento arrisca a programação da abordagem NREDF pra servir grandes números de clientes. Portanto, e de acordo com os princípios da invenção, um servidor de conteúdo usando um programador de Primeira Transmissão Mais Antecipa- da de Taxa Normalizada (NREDF) limita o número de solicitações antigas que são repro- gramadas para um valor limiar.

Referindo-se agora à Figura 7, está ilustrado um sistema de transmissão de conte- údo ilustrativo de acordo com a invenção. O sistema de transmissão de conteúdo compre- ende um servidor de conteúdo 300, uma rede de comunicações 310 e um ou mais clientes, conforme representado pelo cliente 50-1 e 50-2. O servidor de conteúdo 300, o cliente 50-1 e o cliente 50-2 são representativos das plataformas de processador baseadas em controle de programa armazenado. Por exemplo, o cliente 50-1 pode ser um computador pessoal baseado em microprocessador de mesa e o cliente 50-2 pode ser um telefone celular; en- quanto o servidor de conteúdo 300 é um servidor baseado em multiprocessador (alto de- sempenho). Ilustrativamente, a rede de comunicações 310 é representativa da Internet e compreende tanto as facilidades comutadas quanto as não comutadas, conforme conhecido na técnica, e inclui, por exemplo, roteadores, dispositivos de nó de borda, etc. (nem todos ilustrados na Figura 7). Nesse exemplo, e conforme pode ser observado da Figura 7, o ser- vidor de conteúdo 300 está representado como estando situado em outro lugar na Internet com um endereço de Protocolo de Internet (IP) (não ilustrado). Além disso, e conforme ilus- trado na Figura 7, a rede de comunicações 310 pode também compreender uma rede de transmissão de conteúdo (CDN) 315. De outra maneira o conceito inventivo, uma CDN é uma rede de superposição de segmento (pública ou privada) projetada para transmitir segu- ramente conteúdo proveniente dos servidores de conteúdo (provedores) para clientes, ao mesmo tempo em que reduz custos e aumenta as velocidades do cliente (usuário final). Como tal, os outros servidores na CDN podem também fornecer conteúdo solicitado sob o controle do servidor de conteúdo 300. O formato desse conteúdo pode ser conteúdo estático (por exemplo, conteúdo de site da web, arquivos) ou conteúdo dinâmico (isto é, conteúdo que muda rapidamente) e/ou fluxo contínuo de áudio / vídeo. No contexto da Figura 7, os clientes 50-1 e 50-2 enviam solicitações para conteúdo para o servidor de conteúdo 300. Em resposta a essas solicitações, e de acordo com os princípios da invenção, o servidor de con- teúdo 300 programa transmissão usando um programador de Primeira Transmissão Mais Antecipada de Taxa Normalizada Baseada em Limiar (TB-NREDF). O programador TBNREDF impõe um valor limiar, ou limite, no número de solicitações de reprogramação. Por- tanto, o servidor de conteúdo 300 é dotado da habilidade de limitar o código extra de repro- gramação, que também permite que o servidor de conteúdo "tradeoff" a programabilidade contra a execução do sistema. De acordo com o processo de reprogramação TB-NREDF, o servidor de conteúdo 300 leva o conteúdo solicitado a ser transmitido para o cliente respec- tivo por via de um caminho através da rede de comunicações. Por exemplo,, conteúdo, por exemplo, arquivo, solicitado pelo cliente 50-1 é proporcionado para o cliente 50-1 por via do caminho ilustrativo 311, que, nesse exemplo, também percorre a CDN 315. O caminho 311 representa quaisquer facilidades e dispositivo de rede de comunicações 10 através da qual o conteúdo solicitado é transportado para o cliente 50-1.

A Figura 8 ilustra um diagrama em bloco de nível alto. do servidor de conteúdo 300 de acordo com os princípios da invenção. Ilustrativamente, o servidor de conteúdo 300 é um processador baseado em software conforme representado pelo processador 390 e a memó- ria 395 ilustrados na forma de caixas pontilhadas na Figura 8. Nesse contexto, os programas de computador, ou software, são armazenados na memória 395 para execução pelo proces- sador 390. O ultimo é representativo de um ou mais processadores de controle de programa armazenado e não precisa ser dedicado à função programadora do TB-NREDF, por exem- plo,, o processador 300 pode também controlar outras funções do servidor de conteúdo 300. A memória 395 é representativa de qualquer dispositivo de armazenamento, por exemplo,, memória de acesso aleatório (RAM), memória apenas de leitura (ROM), etc.; pode ser inter- na e/ou externa ao processador 390; e é volátil e/ou não volátil, conforme necessário. O ser- vidor de conteúdo 300 recebe solicitações de cliente 59 por via da conexão 319, que acopla o servidor de conteúdo 320 para a Internet. De acordo com os princípios da invenção, o ser- vidor de conteúdo 300 compreende um programador TB-NREDF 360, que processa as soli- citações de cliente recebidas 59 e gera um conjunto de programação, S(t), 370 para propor- cionar o conteúdo solicitado para os clientes solicitantes.

Inicialmente, em um tempo t0, o servidor de conteúdo 300 programa solicitações pa- ra transmitir de acordo com o processo NREDF descrito nos fluxogramas das Figuras 3 e 4, acima, Contudo, uma vez que tenha sido programado um conjunto inicial de solicitações, e de acordo com os princípios da invenção, o servidor de conteúdo 300 limita o número de reprogramação de solicitações. Por exemplo, no tempo t, uma ou mais novas solicitações 82 chegaram e as antigas solicitações K permanecem para serem transmitidas. O processo de Primeira Transmissão Mais Antecipada de Taxa Normalizada Baseada em Limiar (TB- NREDF) define um limiar relembrado, T, que representa o número máximo de antigas solici- tações que serão reprogramadas. Como tal, a abordagem TB-NREDF reprograma no máxi- mo antigas solicitações 7", onde T < K. Assim, as programações das antigas solicitações K-T permanecem inalteradas. Isso está ilustrado na Figura 9 para um conjunto de programação 381 em um tempo, t, onde t > t0. Os valores específicos para T podem ser determinados empiricamente dependendo do sistema específico.

A Figura 10 ilustra o fluxograma ilustrativo para um processo TB-NREDF de acordo com os princípios da invenção. Na etapa 405, o programador TB-NREDF 360 determina se o total de todas as solicitações antigas, K, em um tempo, t, excede um valor limiar, T. Se o número total de todas as solicitações antigas, K, não exceder o valor limiar, K, então, na etapa 410, o programador TB-NREDF 360 programa todas as novas solicitações no tempo, t, (isto é, aquelas solicitações de cliente que ainda não foram programadas) e reprograma o número total de todas as solicitações antigas, K. Contudo, se o número total de todas as solicitações antigas, K, no tempo, t, exceder o valor limiar, K, então, na etapa 415, o pro- gramador TB-NREDF..360 programa todas as novas solicitações no. tempo, t, e reprograma T das antigas solicitações. Como resultado, K-T das antigas solicitações não são reprogra- mados.

Outra modalidade ilustrativa de acordo com os princípios da invenção está ilustra nas Figuras 11, 12 e 13. Novamente, é suposto que em um tempo, to, um conjunto inicial de solicitações, R(t0) tenha sido programado para transmissão em um conjunto de programação associado. Em um tempo subseqüente, t, as antigas solicitações K ainda permanecem e chegaram uma ou mais novas solicitações. O número total de solicitações no conjunto de solicitação R(t) é igual a Q, que é igual ao número de novas solicitações mais as antigas solicitações K. Nesse exemplo, o servidor de conteúdo 300 usa dois parâmetros adicionais: Relembrado e ESTADOreIembrado- O PARAMETRO rreiembrado é definido para ser aquela solicitação que represente o limite no conjunto de programação além do qual as antigas solicitações serão reprogramadas, isto é, isto é aqui referido como a solicitação relembrada. As solicita- ções abaixo da solicitação relembrada são definidas como solicitações não reprogramáveis; ao mesmo tempo em que as solicitações acima da solicitação relembrada são definidas co- mo solicitações reprogramáveis. As solicitações reprogramáveis serão reprogramadas jun- tamente com as novas solicitações na chega das mesmas; ao mesmo tempo em que os programas das solicitação reprogramáveis são fixos, e os mesmos não serão novamente reprogramados. Um valor NULO para o parâmetro TreIembrado significa que nenhuma solicita- ção relembrada foi estabelecida, enquanto que um valor não NULO para esse parâmetro representa que a solicitação relembrada foi estabelecida. Em comparação, o parâmetro ES- TADOreiembrado é definido para ser associado ao estado do sistema relembrado. Especifica- mente, o parâmetro, ESTADOreiembrado, contém os estados das ligações e dos servidores de borda após rreiembrado ser executado. Portanto, ESTADOreiembrado = {{c,}, (Cj)1 {b(i,j)}, {B(i,j)}} (anteriormente definido). Voltando agora à Figura 11, essa figura ilustra um conjunto de programação 383 no tempo t. Conforme pode ser observado da Figura 11, uma das solicitações é designada co- mo relembrado que delineia um limite 86 entre aquelas solicitações que não serão reprograma- das e aquelas antigas solicitações que serão reprogramadas. Outro fluxograma ilustrativo para o processo TB-NREDF de acordo com os princípios da invenção está ilustrado na Figu- ra 12. Na etapa 505, o programador TB-NREDF 360 marca quaisquer novas solicitações como solicitações reprogramáveis. Na etapa 519, o programador TB-NREDF 360 constrói um conjunto de solicitação R(t) que inclui todas as solicitações reprogramáveis. Na etapa 515, o programador TB-NREDF 360 determina o valor atual para rreiembrado. Se o valor para o parâmetro Rrelembrado for NULO, isso significa que não foi estabelecida nenhuma solicitação relembrado. Nesse caso, o processo TB-NREDF reverte para NREDF e, na etapa 530, o programador TB-NREDF 360 programa todas as novas solicitações no tempo, t, (isto é, a- quelas solicitações de cliente que ainda não foram programadas) e reprograma o número total de todas as solicitações antigas, K. Contudo, se o valor para o parâmetro ^iembratjo não for NULO, então, na etapa 520, o programador TB-NREDF 360 determina se a solicitação relembrada designada foi transmitida, isto é, em seu serviço concluído. Se a solicitação re- lembrada designada já tiver sido transmitida então todas as novas solicitações são progra- madas e todas as antigas solicitações são reprogramadas na etapa 530. Deve ser observa- do que uma vez que a solicitação relembrada designada tiver terminado, o número de solici- tações antigas não terminadas será menor do que T. Por outro lado, se, na etapa 520, o programador TB-NREDF 360 determinar que a solicitação relembrada designada não termi- nou então o programador TB-NREDF 360 processa o conjunto de solicitação. Especifica- mente, na etapa 525, o programador TB-NREDF 360 instala o ESTADOrelembrado como o sis- tema corrente a fim de iniciar na rretemí,rado; e, na etapa 530, o programador TB-NREDF 360 programa todas as novas solicitações no tempo, t, e reprograma T das antigas solicitações. Como um resultado, K-T das antigas solicitações não são reprogramadas.

Conforme adicionalmente ilustrado no fluxograma da Figura 12, o pseudo-código está ilustrado na Figura 13. Pode ser observado das etapas 13, 14 e 15 do pseudo-código da Figura 13 que se o número total das solicitações, Q, (novas solicitações mais antigas solicitações) for maior do que o valor limiar 7"; e o valor de solicitação atual, q, for menor, ou igual a (Q-T) então é designada uma solicitação como a solicitação relembrada na etapa 14 e o estado correspondente é armazenado na etapa 15.

Conforme descrito acima, um servidor de conteúdo limita o número de reprograma- ção de solicitações - proporcionando, assim, a habilidade para servir uma taxa de solicita- ção de cliente mais alta. Isso foi ilustrado na descrição acima no contexto de um servidor de conteúdo que use o processo TB-NREDF. Nesse exemplo, um servidor de conteúdo usando o processo TB-NREDF proporciona habilidade para servir uma taxa de solicitação de cliente mais alta do que um servidor de conteúdo usando o processo NREDF não limitado ilustrado nas Figuras de 1 a 6. Contudo, deve ser observado que o processo NREDF pode degradar o desempenho do sistema pela admissão de menores solicitações do que o processo NREDF uma vez que algumas antigas solicitações com uma taxa normalizada menor do que uma nova solicitação podem não ser reprogramadas. De qualquer maneira, o TB-NREDF possibilita que um servidor de conteúdo limite o código extra de reprogramação, que tam- bém permite que o servidor de conteúdo "tradeoff' a programabilidade contra o desempenho do sistema.

Em vista do acima exposto, o que se segue meramente ilustra os princípios da in- venção e irá, portanto, ser apreciado que aqueles versados na técnica serão capazes de planejar numerosas disposições alternativas que, apesar de não estar explicitamente aqui descrito, incorpora os princípios da invenção e estão no espírito e escopo da mesma. Por exemplo,, apesar de ilustrado no-contexto dos elementos funcionais separados, esses ele- mentos funcionais podem ser incorporados em um ou mais circuitos integrados (ICs). Simi- larmente apesar de ilustrado como elementos separados, qualquer ou todos os elementos podem ser executados em um processador controlado de programa armazenado, por e- xemplo, um processador de sinal digital, que executa software associado, por exemplo, cor- respondendo a uma ou mais das etapas ilustradas, por exemplo, nas Figuras 10, 12 e 13, etc. Além disso, os princípios da invenção são aplicáveis a outros tipos de sistemas de co- municações, por exemplo, satélite, Fidelidade Sem fio (Wi-Fi), celular, Bluetooth, etc., e combinações dos mesmos. Por exemplo, uma rede de comunicações distribuída pode incluir conexões com ou sem fio. Na verdade, o conceito inventivo é também aplicável aos servido- res de conteúdo fixos ou móveis. Portanto, deve ser compreendido que podem ser feitas numerosas modificações nas modalidades ilustrativas e podem ser planejadas outras dispo- sições sem se afastar do espírito e do escopo da presente invenção, conforme definido pe- las reivindicações em anexo.

Claims

1. Método para uso no provimento de um serviço, CARACTERIZADO pelo fato de que compreende: receber pelo menos uma nova solicitação para o serviço; e programar a pelo menos uma nova solicitação e quaisquer solicitações antigas para entrega de maneira que o número de solicitações antigas que são reprogramadas seja limi- tado a um valor limite.

2. Método, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que a etapa de programar compreende: programar a pelo menos uma nova solicitação para entrega; determinar um número de solicitações antigas, K; e reprogramar no máximo o valor limite das solicitações antigas para entrega se o número de solicitações antigas for maior do que o valor limite.

3. Método, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que a pelo menos uma nova solicitação e quaisquer solicitações antigas formem um conjunto de solicitação e a etapa de programar compreende: determinar se uma solicitação relembrada foi estabelecida no conjunto de solicita- ção; se não tiver sido ajustada nenhuma solicitação relembrada, então determinar um conjunto de programação de maneira que todas as antigas solicitações sejam reprograma- das; se tiver sido ajustada uma solicitação relembrada e a solicitação relembrada não ti- ver sido transmitida, então reprogramar no máximo o valor limite de solicitações antigas para entrega.

4. Método, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que a etapa de programar realiza Primeira Entrega Mais Antecipada de Taxa Normalizada Basea- da em Limite (TB-NREDF).

5. Método, de acordo com a reivindicação 1, CARACTERIZADO pelo fato de que o serviço entrega conteúdo.

6. Método, de acordo com a reivindicação 5, CARACTERIZADO pelo fato de que o conteúdo é um arquivo.

7. Método, de acordo com a reivindicação 5, CARACTERIZADO pelo fato de que o conteúdo é um fluxo de vídeo.

8. Aparelho para uso no provimento de serviços para clientes solicitantes, CARACTERIZADO pelo fato de que compreende: um processador para proporcionar um conjunto de programação para entregar ser- viços para clientes solicitantes pela programação de pelo menos uma nova solicitação para o serviço e reprogramar quaisquer solicitações antigas para entrega de maneira que o nú- mero de solicitações antigas que estão reprogramadas sejam limitadas a um valor limite; e uma memória para armazenar o conjunto de programação proporcionado.

9. Aparelho, de acordo com a reivindicação 8, CARACTERIZADO pelo fato de que o processador (a) programa a pelo menos uma nova solicitação para entrega, (b) determina um número de solicitações antigas, K, e (c) reprograma no máximo o valor limite das solici- tações antigas para entrega se o número de solicitações antigas for maior do que o valor limite.

10. Aparelho, de acordo com a reivindicação 8, CARACTERIZADO pelo fato de que a pelo menos uma nova solicitação e quaisquer solicitações antigas formem um conjunto de solicitação e o processador (a) determina se uma solicitação relembrada foi estabelecida no conjunto de solicitação, (b) se nenhuma solicitação relembrada tiver sido estabelecida, de- termina um conjunto de programação de maneira que todas as solicitações antigas sejam reprogramadas, e (c) se uma solicitação relembrada tiver sido estabelecida e a solicitação relembrada não tiver sido transmitida, então reprograma no máximo o valor limite de solici- tações antigas para entrega.

11. Aparelho, de acordo com a reivindicação 8, CARACTERIZADO pelo fato de que o processador realiza Primeira Entrega Mais Antecipada de Taxa Normalizada Baseada em Limite (TB-NREDF).

12. Aparelho, de acordo com a reivindicação 8, CARACTERIZADO pelo fato de que os serviços entregam conteúdo.

13. Aparelho, de acordo com a reivindicação 12, CARACTERIZADO pelo fato de que o conteúdo é um arquivo.

14. Aparelho, de acordo com a reivindicação 12, CARACTERIZADO pelo fato de que o conteúdo é um fluxo de vídeo.

15. Meio legível de computador, CARACTERIZADO por possuir instruções execu- táveis de computador para um sistema baseado em processador de maneira que quando executado o sistema baseado em processador realize um método para programar entrega em resposta às solicitações para um ou mais serviços, o método compreendendo: receber pelo menos uma nova solicitação para o serviço; e programar a pelo menos uma nova solicitação e quaisquer solicitações antigas para entrega de maneira que o número de solicitações antigas que são reprogramadas seja limi- tado a um valor limite; em que a pelo menos uma nova solicitação e quaisquer solicitações antigas formam um conjunto de solicitação e a etapa de programar compreende: determinar se uma solicitação relembrada foi estabelecida no conjunto de solicita- ção; se não tiver sido estabelecida nenhuma solicitação relembrada, então determinar um conjunto de programação de maneira que todas as solicitações antigas sejam reprogra- madas; se tiver sido estabelecida uma solicitação relembrada e a solicitação relembrada não tiver sido entregue, então reprogramar no máximo o valor limite das solicitações antigas para entrega.