Click here to load reader

Encaminhamento com QoS

  • View
    35

  • Download
    0

Embed Size (px)

DESCRIPTION

Encaminhamento com QoS. Sistemas Telemáticos LESI Grupo de Comunicações por Computador. Materiais utilizados. Tema é ainda objecto de I&D Artigo “Survey of QoS” de Pragyansmita Paul and S. V. Raghavan Adaptação e simplificação de apresentação dos mesmos autores. Sumário. - PowerPoint PPT Presentation

Text of Encaminhamento com QoS

  • Encaminhamento com QoSSistemas TelemticosLESIGrupo de Comunicaes por Computador

  • Materiais utilizadosTema ainda objecto de I&D Artigo Survey of QoS de Pragyansmita Paul and S. V. Raghavan Adaptao e simplificao de apresentao dos mesmos autores

  • Sumrio

    Vantagens da Qualidade de Servio (QoS)QoS Fim-a-FimEncaminhamento com QoSQuestes em aberto no Encaminhamento com QoSAlgoritmos propostos (classificados com mtricas)

    Um-para-umSimplesDualMltiplo

    Grupo

    SimplesDualMltiplo

  • QoSA um conjunto de mtricas e restries que so usadas para especificar os requisitos das aplicaes e que devem ser satisfeitas pela rede de suporte durante a transmisso de dados.As mtricas de QoS so: Largura de Banda Atrasos Variao nos atrasos (Jitter) Perda de Pacotes (Fiabilidade) Nmero de saltos, Qualidade udio/Vdeo, etc.

  • QoS Fim-a-Fim necessria para:Disponibilizar garantias slidas necesrias pelas actuais aplicaes com temporizao crtica e com necessidades intensivas de largura de banda.Prevenir a deteriorao do desempenho da rede devido a aplicaes mal comportadas.

    Para optimizar o desempenho todas as camadas da pilha de protocolos devem suportar o QoS a disponibilizar aplicao de rede a ser executada.

  • QoS na Pilha de Protocolos

    Aplicao???

    Transporte???

    Rede???

    Ligao Lgica???Meio Fsico

  • QoS na Pilha de Protocolos

    AplicaoDiferentes Classificaes e Escalonamento dos pedidos

    TransporteAceitao/rejeio dos pedidos de conexo

    RedeSeleco de Percursos de forma a satisfazer os requisitos das aplicaes

    Ligao LgicaComunicao de Dados de forma satisfazer os requisitos das camadas superioresMeio Fsico

  • Sequncia de aces para disponibilizar a QoS fim-a-fim

  • Encaminhamento com QoS

  • Negociao de QoS e Controlo de AdmissoA negociao comea quando o sistema final envia o seu pedido de QoSO mdulo de controlo de admisso verifica se o pedido deve ser aceite ou rejeitadoFactores de deciso: LB residual, N Tx em cursoSe a aceitao levar degradao de desempenho , o pedido rejeitadoAlternativa: reencaminhamento das aplicaes existentesRenegociao do QoS

  • Negociao de QoS e Controlo de Admisso(2)O sistema final (end-host) pode fazer o controlo de admissoFaz o probe do nvel de congestoAdmite o fluxo se o nvel for baixoExperincias:Menor degradao de desempenho se o controlo de admisso for feito pelos sistemas finais em alternativa a ser feito pelos encaminhadores

  • Reserva de RecursosUma vez aceite o pedido escolhido o percurso para transmisso de dados com base em uma ou mais mtricasNecessria para satisfazer restries de QoS da aplicaoDuas alternativasFazer parte do estabelecimento do percursoSer um processo separado

  • Armazenamento e Escalonamento dos PacotesPacote recm-chegado ao encaminhador transferido para a interface de sada e armazenado num buffer descartadoObjectivo:Minimizar o descarte de pacotesAlgoritmos de gesto de filasAlgoritmos de escalonamento de pacotes

  • Algoritmos de EscalonamentoFair Queueing (FQ) 1 fila por fluxo (informao de estado por fluxo)Stochastic Fair Queueing (SFQ)Menor n de filas que FQ, uso de funo de hashCore Stateless Fair Queueing (CSFQ)2 classes de encaminhadores: De fonteira mantm informao de estado por fluxoEstimam dbito de chegada por fluxo (passam aos interiores) InterioresEm situao de congesto, descartam pacotes aleatriamente com base nessa estimao

  • Algoritmos de Gesto de FilasRED (Random Early Detection) & RIOCHOKe (CHOose and Keep for responsive flows)Considerar o buffer como uma amostra estatstica do trfegoEm situao de congesto, na chegada de pacoteEscolhe um pacote do buffer aleatoriamenteSe for do mesmo fluxo, descarta os doisSeno: o do buffer fica intacto e o chegado aceite em funo do nvel de congesto

  • Lookup da Tabela de EncaminhamentoMaior gargalo do processo de expedio dos pacotesMais crtica com tecnologias de alta velocidadeUnificao simples (tries)Unificao mais longa (PATRICIA)Multi-Protocol Label Switching (MPLS)Etiqueta de comprimento fixo Cada pacote tem uma etiqueta Etiqueta usada para busca na tabela

  • Gesto de RecursosNecessria para gerir a dinmica das conexes estabelecidasReserva esttica de recursosGR necessria para verificar utilizao eficiente de recursosReserva dinmica?? Quando no h reserva de recursos Assegurar uma partilha adequada entre as conexes e que as exigncias de cada fluxo so limitadasQuando cada servio recipiente recebe o mnimo de QoS, considera-se adequada

  • Fluxos BE num QoS RouterPara alm dos fluxos com QoS, as aplicaes BE devem ser geridas de forma apropriada. Exemplo de trabalho nesse sentidoRestrio de LB para fluxos com QoSUsa informao imprecisa para o estado de fluxosMaxMin Fair Routing para fluxos BEMaximiza a LB para fluxos que recebem menor LB entre todosEscalonamento hierrquico com WFQ para alocao de LB

  • Seleco do Percurso Mtricas e Restries Mtricaw2w3Percurso P

  • Seleco do Percurso Mtricas e RestriesMtricasSimplesDualMltiplasSimples: Custo, Largura de Banda, AtrasoDual: Custo e Atraso;LB e Atraso; LB e CustoMltiplas: ...

  • Seleco do Percurso Mtricas e RestriesComo transformar uma mtrica multiplicativa em aditiva?w1.w2.w3 => log(w1)+log(w2)+log(w3)Como transformar uma mtrica dual (mltipla) numa mtrica simples?(w1,w2) => w= w1+k w2Como transformar uma mtrica com valor real ou inteiro no limitado numa com valor inteiro limitado? w < c => w= w* x/c

  • Seleco de Percurso ME vs. QoSPercursoEscolhido ?

    PercursoMtrica 1Mtrica 2F-B37F-D-B55F-E-D-C-B76

  • Seleco de Percurso ME vs. QoSEm contextos BE mais fcil descobrir o PMCEm contextos com QoS necessrio considerar um conjunto de mtricas cada aresta do grafo tem mais que uma mtrica associadaA escolha do PMC depende deRegra de composio de mtricasPrioridade/Peso atribudos a cada mtrica

  • Seleco de Percurso no Encaminhamento com QOSWang e Crowcroft provaram que encontrar um percurso sujeito a duas ou mais restries independentes (aditivas e/ou multiplicativas) um problema NP-Completo.

  • Seleco de Percurso no encaminhamento com QoS Resultados interessantesQuando o nmero de mtricas consideradas infinito, suficiente calcular o percurso de menor nmero de saltos, sem se ter que considerar distribuio dos pesos das mtricas independentes. (resultado com interesse terico)Podem existir classes de grafos nos quais o encaminhamento com QoS no NP-Completo. (Referncia: P. Van Mieghem, F. A. Kuipers, On the Complexity of QoS Routing, na Computer Communications.).

  • Classificao de Algoritmos/Protocolos

    Largura de banda Atraso

  • Encaminhamento unicast Restrio de Largura de BandaFiltragem da TopologiaAlgoritmo de Guerin OrdaLB > 2Maximizar Probablidade (LB Residual > 2)

  • Classificao de Algoritmos/Protocolos

    Custo+AtrasoLB + AtrasoQualquer 2 mtricas aditivas

  • Encaminhamento Unicast com QoS Restries de Atraso e Largura de Banda

    Elimina todas as ligaes com largura de banda inferior requerida. A seguir, encontra o percurso mais curto relativamente ao atraso no grafo modificado usando o algoritmo de Djikstra.Algoritmo de Wang Crowcroft

  • Percurso mais curto com o Algoritmo de DjikstraDado um grafo ponderado G=(V,E), e um par de vrtices vs e vd V qual o percurso mais curto de vs para vd? Isto qual o percurso com a mnima soma dos pesos das arestas?

  • Abordagem bsicaPMC de A para H = PMC de A para B + PMC from B to H.PMC de A para H = PMC de A para C + PMC from C to H.PMC de A para H = PMC de A para vi + PMC from vi to H; " vi.A B E F H15A B E G H14A C E F H16A C E G H15A D E F H26A D E G H25

    AH2163817565

  • Algoritmo de Dijkstra para PMCsSntese:Manter uma estrutura de dados com a lista de ns e pesos dos percursos para esses nsUsar infinito para representar um no conjunto S de ns para os quais no tenha sido calculado um percursoEm cada iterao, encontrar um n em S, calcular o percurso para esse n e apag-lo de S

  • Algoritmo de Dijkstra para PMCs

    S = {0} /* Actual MST */for i = 0 to n D[i] = M[0][i] /* Shortest path length from 0 to i */end forfor i = 1 to n-1 find the smallest D[v] such that v S S = S {v} for all vertices u S if (D[u] > D[v] + M[v][u]) then D[u] = D[v] + M[v][u] end if end forend for

  • Algoritmo de DijkstraA2163817565AC2163817565S = {A}S = {A,C}Custo do Percurso mais curto de A para vi atravs de S

  • Algoritmo de Dijkstra(2)ABC2163817565ABCE2163817565S = {A,C,B,E}S = {A,C,B}ABCDEFGH--2163???ABCDEFGH--2163108?Custo do Percurso mais curto de A para vi atavs de S

  • Algoritmo de Dijkstra(3)ABDCEG2163817565ABDCEG2163817565S = {A,C,B,E,D,G}S = {A,C,B,E,D}ABCDEFGH--2163108?ABCDEFGH--216310814Custo do Percurso mais curto de A para vi atavs de S

  • Algoritmo de Dijkstra (4)ABDCEFG2163817565ABDCEFGH2163817565S = {A,C,B,E,D,G,F,H}S = {A,C,B,E,D,G,F}ABCDEFGH--216310814ABCDEFGH--216310814Custo do Percurso mais curto de A para vi atavs de S

  • Algoritmo de Dijkstra: Exemplo

  • Classificao de Algoritmos/Protocolos

    Custo +AtrasoLB + AtrasoQuaisquer 2 mtricas aditivas

  • Encaminhamento Unicast com QoS Restries de quaisquer duas mtricas aditivas

    Combinao de mtricas ponderadas de Jaffe prope a minimizao duma combinao linear de pesos w1 + dw2 onde d=1 ou d=(c1/c2). A ltima obtm melhores resultados que a primeira.Foi proposta uma estratgia de procura binria para escolher o peso. w = w1 + d w2

  • Classificao de Algoritmos/Protocolos

    Custo AtrasoMtrica no aditivaCusto +AtrasoLB + AtrasoQuaisquer 2 mtricas aditivas

  • rvore de SteinerSeja G=(V, E) um grafo indirecto com um nmero finito de vrtices V e um conjunto de arestas E, e uma funo de custo que atribui a cada aresta um valor de custo real e positivo. Dado um subconjunto S dos vrtices de V, o problema de Steiner encontrar um subgrafo G conexo e acclico de G (rvore), G' =(V', E'), que contm todos os vrtices em S, de tal forma que o custo de todas arestas em E' mnimo. Os vrtices em S so designados por especiais.

  • rvore geradora mnimaNo caso particular de todos os ns da topologia fazerem parte do grupo (ou seja quando S=V), o problema mais simples e resolve-se calculando a rvore geradora mnima:

    Algoritmo de Prim Algoritmo de Kruskall

  • Algoritmo de PrimComea por seleccionar um qualquer vrtice (no importa qual), adicionando-o soluo. Depois, iterativamente, escolhe-se a aresta de menor custo, com ligao a vrtices da soluo, que no forma ciclos e junta-se soluo: O={1} (raiz da rvore). P={2,...,n} Enquanto (P Vazio)Escolher aresta K(i,j) de menor custo, com i pertencente a O e j pertencente a P Fazer O = O U {k} Fazer P = P \ {k}

    Demo: http://students.ceid.upatras.gr/~papagel/project/prim.htm

  • Algoritmo de KruskallSelecciona a aresta de menor custo. Iterativamente adiciona sempre a aresta de menor custo ainda no seleccionada que no forme ciclos:

    A1=0,A2=A Enquanto (|A1| < n-1 arestas) && A2=0 fazerEscolher aresta a(i,j) de A2 de menor custo A2=A2-{a(i,j)} Se vrtices V(i) e V(j) no pertencem mesma rvore:Juntar as rvores de V(i) e V(j) numa nica rvore.

    Demo: http://students.ceid.upatras.gr/~papagel/project/kruskal.htm

  • Encaminhamento Multicast com QoS Restries de custoUma rvore que alcana todos membros do grupo e minimiza o custo total da rvore partilhada. Encontrar essa rvore um problema NP-Completo. Algoritmo de Kou, Markowsky e Berman (KMB)

    Criar um grafo conexo onde as arestas sejam as distncias mais curtas entre os membros do grupo.O algoritmo de Prim calcula a a rvore de menor custo deste grafo conexo.As arestas do grafo conexo so posteriormente substitudas pelos percursos mais curtos originais para obter a rvore de Steiner.

  • Abordagens para QoSAbordagem com informao de estado, com informao por fluxo. Abordagem sem informao de estado e portanto mais escalvelServio fim-a-fim garantido por fluxo. Necessidade de reserva de recursos.Diferenciao de servio mais grossa. Ns de fronteira classificam os pacotes enquanto os ns interiores os processam de acordo com a classificao.

    Servios Integrados

    Servios Diferenciados

  • Eficcia do Encaminhamento com QoSEmbora o encaminhamento com QoS aumente a computao em cada n, armazenamento de estado e custo de comunicao, tem a vantagem de aumentar a utilidade da rede e permitir uma degrao graciosa do desempenho.A presena de mecanismos com QoS assegura que mesmo as aplicaes mais convencionais e cujo QoS sempre foi esquecido obtenham um melhor desempenho do servio de rede..O encaminhamento com QoS mais eficaz quando h desajustamento entre o trfego e a capacidade da rede e existem rotas alternativas com menor carga..

  • Questes em aberto (1)Necessidade de protocolos para encaminhamento com QoS e tcnicas de negociao de QoS normalizadosMecanismos eficientes para evitar percursos com congesto, atrasos altos de propagao e instabilidade no processo de seleco de percursos.

  • Questes em aberto(2)A impreciso na informao de estado precisa de ser manipulada de forma apropriada.Ao mesmo tempo que se maximiza o nmero de fluxos com QoS, deve-se procurar optimizar o desempenho e tempo de resposta ao trfego best-effort. Necessidade dum algoritmo/protocolo de QoS genrico que use por exemplo uma nica mtrica representativa de todas as outras com um mnimo de perda de informao.

  • Resumo da AulaEncaminhamento com QoSAlgoritmos e protocolos propostos para encaminhamento com QoS em ambientes unicast e multicast.Benefcios de desenvolvimento de encaminhamento com QoS na interligao de redes actualmente.Questes em aberto no encaminhamento com QoS

    A Internet est cada vez mais a ser usada para servios em tempo real como audio/videoconferncia, webcasting, telemedecina.Isto exige que a rede fornea garantias de qualidade de servio. As necessidades da aplicao so especificadas em termos de mtricas de QoS como largura de banda, tempo de resposta, etc...The Steiner tree problem has been proved to be NP-complete, and no algorithms can solve it in polynomial time. However, in the recent decade, heuristics have been proposed to provide near-optimal solutions