Encaminhamento com QoS

  • View
    29

  • 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 (2 doutoramentos nessa área no DI) Artigo “Survey of QoS” de Pragyansmita Paul and S. V. Raghavan - PowerPoint PPT Presentation

Text of Encaminhamento com QoS

  • Encaminhamento com QoSSistemas TelemticosLESIGrupo de Comunicaes por Computador

  • Materiais utilizadosTema ainda objecto de I&D (2 doutoramentos nessa rea no DI)Artigo Survey of QoS de Pragyansmita Paul and S. V. RaghavanAdaptao e simplificao de apresentao dos mesmos autores

  • SumrioVantagens 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 Pedidoaceite?Fim da Transferncia dos dados?Fim da transferncia dos dadosSimSimASeleco do Percurso e transferncia dos dados (Encaminhamento com QoS)A

  • Encaminhamento com QoSFim da Transferncia dos dados?Fim daTransferncia de DadosSimB

  • 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 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 limitadoQuando 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-A-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 CrowcroftLB > 2

  • 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 E + PMC de E para HPMC de A para H = PMC de A para B + SP from B to H.PMC de A para H = PMC de A para C + SP from C to H.PMC de A para H = PMC de A para vi + SP 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 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 atavs 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

  • C