Subject: QoS Framework draft

From: dhc2 <[email-masked]>
Date: Thu, 11 Mar 1999 22:15:06 -0500 (EST)

The atached draft could not make it through the IETF i-d depositories on time, 
so I am posting it on the mailing list.

Derya

MANET Working Group                                   Derya H. Cansever
                                                      Allen H.  Levesque
INTERNET DRAFT                                   GTE Laboratories, Inc.
                                                          February  1999
Expiration Date August 1999

         A Framework for QoS Support in Mobile Ad-hoc Networks
                <draft-ietf-manet-qos-framework-00.txt>

Status of this Memo

   This document is an Internet  Draft.   Internet  Drafts  are  working
   documents  of  the Internet Engineering Task Force (IETF), its Areas,
   and its Working Groups.  Note that other groups may  also  distribute
   working documents as Internet Drafts.

   Internet Drafts are draft  documents  valid  for  a  maximum  of  six
   months.   Internet  Drafts  may be updated, replaced, or obsoleted by
   other documents at any time.  It is not appropriate to  use  Internet
   Drafts as reference material or to cite them other than as a "working
   draft" or "work in progress."

   Please  check  the  1id-abstracts.txt  listing   contained   in   the
   internet-drafts  Shadow  Directories  on  nic.ddn.mil,  nnsc.nsf.net,
   nic.nordu.net,  ftp.nisc.sri.com,  or  munnari.oz.au  to  learn   the
   current status of any Internet Draft.

Abstract

   This memo discusses  issues  related  to  Quality  of  Service  (QoS)
   support  in MANETS. In particular, it overviews MANET characteristics
   that are relevant to QoS support, identifies architectural components
   useful  in QoS support, and discusses potential QoS support solutions
   that are compatible with existing MANET routing protocols.

1. Introduction

   As real-time applications find their way into the  Internet,  efforts
   to  support  QoS  have  intensified. Approaches range from allocating
   resources to individual flows, to throwing "enough bandwidth" to  the
   problem.  MANET  Internets have very distinct characteristics that is
   likely to narrow the scope of the options. In this  memo,  we  assume
   that  applications  have  the  ability to request appropriate network
   resources, and to indicate it by generating specific  packets  and/or
   marking  the  packets  that  carry the application content. We assume

Cansever & Levesque                                         [Page 1]

  A Framework for Quality of Service Support in Mobile Ad-hoc Networks

   that the links are bi-directional and that the bandwidth available in
   the  direction  from  Node  A  to  Node  B  is roughly similar to the
   bandwidth  available  in  the  direction  from  Node  B  to  Node  A.
   Discussion  in  this  memo  is  limited  to  unicast  transmission of
   packets.

   One of the characteristics of  MANETS  is  that  they  are  bandwidth
   limited,  and the available bandwidth is subject channel impairments.
   The latter induces the use of redundant codes, which further  reduces
   the  available bandwidth. Furthermore, the channel impairments that a
   node is subject to may dependen on the channel that the node is using
   at  a  particular  time.  Thus,  available  bandwidth from a node may
   depend on the channel it is transmitting.  When  channel  impairments
   reach  beyond  a  threshold,  coding  methods alone do not suffice to
   ensure transmission. Such a threshold is identified as 10E-2  of  Bit
   Error  Rate  (BER)  in  [CANS].  When  the  BER reaches beyond such a
   threshold, it would  make  sense  to  declare  that  particular  link
   unreachable, and seek an alternate path.

   Another characteristic of MANETS is that there  is  a  random  access
   with  contention,  or  scheduling  process involved in inserting each
   packet into the transmission link. Thus, a solution that  involves  a
   large  number  of  control  packets is not likely to be desirable for
   MANETS, in that it would tend  to  increase  the  collusions,  and/or
   decrease the probability of obtaining a channel. This, in turn, would
   decrease the overall efficiency of the system.

   Nodes in a MANET send, receive and relay packets.  We  argue  that  a
   node  is  not  likely  to  serve as transit to a very large number of
   flows, as it would be the case in a backbone node  of  a  high  speed
   terrestrial network. There are two reasons for this assertion. One is
   that in the majority of proposed schemes [TORA], [DSR], [AODV], there
   is  not  an identifiable set of "backbone nodes" that provide transit
   to a majority of the packets in the network. An exception to this has
   been  proposed  in  [CEDAR],  though.  We  expect that in many cases,
   especially in high mobility environments, nodes will randomly  assume
   transit  responsibilities,  where  the  distribution will be close to
   uniform. Another reason for expecting a small number of flows relayed
   by  each  node is that, the relatively low speed links in MANETS will
   be quickly saturated when the flows have QoS  requirements.  Such  an
   analysis  is  provided  in  [GUPTA],  which identifies a bound to the
   number of nodes in a MANET when real-time applications occupy a given
   portion of the link.

2. Some Alternatives for QoS Support

   QoS support roughly means  providing  the  applications  with  enough
   network  resources,  so  that  they  can  function  within acceptable

Cansever & Levesque                                         [Page 2]

  A Framework for Quality of Service Support in Mobile Ad-hoc Networks

   performance  limits.  There  may  be  two  reasons  for  not   having
   sufficient network resources. One is due to network impairments. This
   may  be addressed using stronger coding, increasing the power  level,
   or  alternate  routing.  The  other  reason  for insufficient network
   resources is congestion. Solutions to  physical  impairment  problems
   generally  worsen  the  congestion  in  the  network. This will occur
   either by reducing  the  bandwidth  due  to  stronger  codes,  or  by
   increasing  the  traffic  at  other  nodes  due  to alternate routing
   resulting from impaired channels, or by increasing the probability of
   packet  collusions  due  to the augmented power. This memo focuses on
   resolving congestion issues so as to provide QoS support.

   Congestion management includes three broadly defined methods. One  is
   to  over-engineer the network so that resource contention is avoided.
   In general, this method is not applicable in MANETS.  Another  method
   is  to  reserve  end-to-end  resources  along  the  path  of  a  flow
   corresponding to a particular application.  A  third  method  is  not
   necessarily  to  reserve  specific  resources in the network for that
   particular flow, but to  mark  the  packets  and  provide  them  with
   special  treatment  in the nodes. Of course, an example of the second
   method is RSVP [RFC 2205], and an example  of  the  third  method  is
   Differentiated  Services  (DS) [RFC 2474],[RFC 2475]. Since both RSVP
   and Differentiated Services were designed  for  high  speed  wireline
   networks, we will discuss their applicability and possible extensions
   for MANET environments. Both RSVP and DS make use  of  network  layer
   information. Thus, in this memo, we assume that QoS related decisions
   are made at the network layer, and that a MAC mechanism is  available
   to support the scheduled processing of packets.

   Roughly speaking, Differentiated Services  consists  of  marking  the
   packets  with  particular values of the DS field [RFC 2474], and then
   configuring the nodes appropriately so that the  marked  packets  are
   treated  as intended at the nodes they transit. There are 64 possible
   values for the DS field, and it is IETF's intention to  allow  32  of
   these  values  for  experimental  use.  Of course, this number can be
   further increased by introducing a new field such that  a  particular
   value  of the DS field would refer to it. Of course, such a new field
   would result in additional processing burden at the nodes, and unlike
   high-speed  wireline  networks,  such  a  cost might be acceptable at
   relatively low speed MANET links. Differentiated  Services  does  not
   identify  individual flows, but provides a prescribed treatment to an
   aggregate of flows, as specified in the Per Hop Behavior  (PHB)  that
   corresponds to a particular value of the DS field.

   Currently, there are  two  types  of  PHB  that  are  considered  for
   standardization.  One of them is Assured Forwarding PHB [AFP]. AFP is
   concerned with the the loss of the packets in case of congestion.  As
   such,   AFP  defines  4  levels  packet  forwarding  assurances,  and

Cansever & Levesque                                         [Page 3]

  A Framework for Quality of Service Support in Mobile Ad-hoc Networks

   allocates buffer and bandwidth  resources  for  each  class.  Assured
   forwarding  of for certain types of packets is of course an important
   consideration, be it in wireline, or wireless networks.  Thus, ARP is
   directly applicable to MANETS with the same semantics and codepoints.

   Another type of PHB is Expedited Forwarding [EFP]. EFP provides a low
   latency, low jitter point-to-point path to packets by configuring the
   nodes such that a given bandwidth is allocated to such  packets,  and
   by  policing  the  ingress  traffic  such that it does not exceed the
   pre-allocated amount. Clearly, this is a very useful tool  for  high-
   speed  wireline  networks with multiple users, and with an autonomous
   administration that has the ability to configure the nodes and police
   the   user   traffic.   In   MANETS,   there  is  neither  a  central
   administrator,  nor a fixed concatenation of nodes to  be  configured
   so as to define a "virtual private line". As such, unlike AFP, EFP is
   not directly applicable to MANETS, but a simpler and modest PHB might
   be useful.

   PHBs are implemented  using  packet  scheduling  algorithms  such  as
   Weighted  Fair  Queuing  [WFQ],  or  Start  Time Queuing [STQ]. These
   algorithms ensure that a  given  portion  of  the  bandwidth  in  the
   outgoing  link  of a queue is guaranteed to be allocated to a certain
   class of traffic. Since DS  does  not  differentiate  the  individual
   flows,  the  guaranteed  bandwidth  is  allocated  to an aggregate of
   flows, differentiated from other aggregated flows by their respective
   DS  field  value.   As such, one can define a MANET specific PHB that
   refers to a new field, where the particular class of  the  packet  is
   defined.  Each  class  may  correspond  to  a minimum bandwidth, or a
   percentage of the total bandwidth in the  node,  for  example.  Using
   this approach, one guarantees that a class of traffic obtains a given
   portion of the network  resources.  In  the  extreme  case  that  the
   portion  allocated  to  a  specific class is 100%, one faces a strict
   priority scheme.  Of course, there maybe  too  many  packets  from  a
   given  class  for the allocated resources.  In this case DS is not of
   much help. But, at least, it  insures  that  traffic  from  different
   classes do not interfere with each other.

   RSVP is a signaling protocol used in allocating end-to-end  resources
   to  each  individual  flow.  Since  it  is  also  associated  with an
   admission control element, RSVP does not face the problem of too many
   packets from the same class. However, a recognized problem in RSVP is
   that routers cannot process a large number  of  individual  flows  at
   high  speeds.  Thus,  RSVP is not recommended for use at the backbone
   nodes [RFC 2208]. In MANETS, the bandwidth is limited, and the number
   of the flows processed in a transit node is not expected to be large,
   as discussed in Section 2. Thus, packet processing  requirements  for
   RSVP in a MANET environment are more reasonable. The drawback is that
   RSVP, as currently defined, involves too many control packets  to  be

Cansever & Levesque                                         [Page 4]

  A Framework for Quality of Service Support in Mobile Ad-hoc Networks

   effectively  used  in   MANET  environment where channel access is an
   issue. In the next section,  we  discuss  an  end-to-end  reservation
   mechanism  that  makes  use  of  elements of RSVP that may be used in
   conjunction with some of the proposed MANET routing algorithms.

3. End-to-end Resource Allocation in MANETS

   Differentiated  Services  methods  prevent  traffic  from   different
   classes  to  interfere  with each other, but do not help to segregate
   traffic within the same class. A QoS support methodology  for  MANETS
   that would allocate resources to individual flows needs the following
   ingredients:

   - A QoS metric

   - A method to identify flows

   - A method to indicate QoS requirements

   - A method to identify nodes with sufficient resources (QoS routing)

   - A method to reserve resources

   - A method to release resources

3.1 A QoS metric

   There are several possible  QoS  metrics  that  are  related  to  the
   performance  requirements  of  real-time applications, such as delay,
   jitter, throughput.  The chosen metric(s) will be used in the routing
   algorithm  to  find  a  feasible  path  that satisfies the associated
   constraints. It is well known that, [RFC 2386] finding a  route  that
   satisfies  multiple  constraints  is  a computationally hard problem.
   Implementing a multi-dimensional QoS metric for MANETS, where control
   packet  exchange  is  to be minimized, and the topology is subject to
   constant change, is not advisable. Instead, we  propose  to  use  the
   minimum  bandwidth as a simple, but generally sufficient metric. With
   this metric, nodes can account for their used and  unused  resources,
   and  communicate  it  easily with their peers. Also, note that such a
   metric would approximate a circuit switched network, and  the  latter
   has been supporting real time applications for decades.

3.2 A method to identify flows

   A possible way to identify a flow is to use the  triplet  (Source  IP
   Address, Destination IP Address, DS Field). Here, a specific value of
   the DS field would indicate that this packet is  to  receive  special
   treatment.

Cansever & Levesque                                         [Page 5]

  A Framework for Quality of Service Support in Mobile Ad-hoc Networks

3.3 A method to indicate QoS requirements

   Packets that need to receive special treatment will have  a  specific
   value  value  in  their  DS  field.  The  exact nature of the special
   treatment will be indicated  in  the  resource  reservation  process,
   which will be described in the following subsections.

3.4 A method to identify nodes with sufficient resources (QoS routing)

   QoS routing in MANETS can be considerably  simplified  by  using  the
   minimum  bandwidth metric and the on-demand route creation feature of
   some of the existing proposals [TORA], [DSR], [AODV].  In  the  Query
   [TORA],  or  in the Route Request [DSR, AODV] packet, the sender also
   indicates the requested minimum bandwidth. A node that receives  this
   Query,  or Route Request packet delivers it to the next hop nodes, as
   specified in the routing algorithm, only if it has  enough  resources
   to  fulfill this request. Since the IP addresses of all the nodes are
   added to the packet, the receiving end node has  a  path  of  routers
   that  can  fulfill  the QoS requirement. Among this list, the node at
   the  receiving  end  will  identify  the  shortest  path.    Detailed
   description of this process for the proposed MANET routing algorithms
   will be provided in the future versions of this draft.

3.5 A method to reserve resources

   When the Reply, or the Route Reply packet traverses the  sequence  of
   nodes  derived  from  the Query, or the Route Request packet, it will
   reserve the bandwidth indicated in the  original  request  packet  in
   both   directions,  unless  indicated  otherwise.  If  the  requested
   bandwidth will be different in each direction, it will  be  indicated
   in  the  request packet, and the node that issues the reply will have
   the option to overrule it.

3.6 A method to release resources

   Since minimizing the control packet flow is a goal, a possible way to
   accomplish  this is to make use of local timers. That is, a node will
   release resources reserved for a flow if  it  does  not  receive  any
   packet  from  that  flow  within a period of T seconds, where T is an
   adjustable parameter.

   The task of maintaining the route and adjusting to  topology  changes
   will  be  handled  by the undelying routing algorithm, subject to the
   constraint that a link between two nodes will be considered  up  only
   if  both nodes have enough resources to fulfill the requested minimum
   bandwidth.

4.0 Security Considerations

Cansever & Levesque                                         [Page 6]

  A Framework for Quality of Service Support in Mobile Ad-hoc Networks

   Security considerations for QoS support in MANETS is TBD.

References

   [CANS] D. Cansever, A. Michelson and A. Levesque "Error Control
          and Resource Management in Mobile Ad-hoc Networks",
          submitted for publication, 1999.

   [TORA] V. Pak and S. Corson, "Temporally-Ordered Routing Algorithm
          (TORA) Version 1 Functional Specification", work in progress.

   [DSR] J. Broch, D. Johnson and D. Maltz, "The Dynamic Source
         Routing Protocol for Mobile Ad Hoc Networks", work in progress.

   [AODV] C. Perkins and E. Royer, "Ad Hoc On Demand Distance Vector
          (AODV) Routing", work in progress.

   [CEDAR] R. Sivakumar P. Sinha and V. Bharghavan, "Core Extraction
           Distributed Ad hoc Routing (CEDAR) Specification", work
           in progress.

   [GUPTA] P. Gupta and P.R. Kumar, "The Capacity of Wireless
           Networks", submitted for publication, available in
           http://black.csl.uiuc.edu/~prkumar.

   [AFP] J. Heinanen at al, "Assured Forwarding PHB Group",
         work in progress.

   [EFP] V. Jacobson at al, "An Expedited Forwarding PHB",
         work in progress.

   [WFQ] A. Parekh and R. Gallagher, "A generalized Processor
         Sharing Approach to Flow Control - the Single Node
         Case", ACM/IEEE Transactions on Networking, 1(3)
         344-357, June 1993.

   [STQ] P. Goyal et al., "Start-time Fair Queuing:
         A Scheduling Algorithm for Integrated Services",
         in Proceedings of the ACM-SIGCOMM 96, pp 157-168,

Cansever & Levesque                                         [Page 7]

  A Framework for Quality of Service Support in Mobile Ad-hoc Networks

         Paulo Alto CA August 1996.

Acknowledgements

   TBD

Authors' Address

   Derya H. Cansever
   GTE Laboratories Inc.
   40 Sylvan Rd. MS 51
   Waltham MA 02254

   Phone: +1 781 466 4086
   Email: [email-masked]

   Allen H. Levesque
   GTE Laboratories Inc.
   40 Sylvan Rd. MS 57
   Waltham MA 02254

   Phone: +1 781 466 2140
   Email: [email-masked]

   Expiration Date August 1999

Cansever & Levesque                                         [Page 8]

---

From: [email-masked]
Date: Fri, 12 Mar 99 15:16:30 EST

Derya,

I agree with you that MANET group needs to start addressing some of the QoS 
issues and exploring how the existing QoS efforts in IETF can be leveraged 
here.  Given the highly dynamic nature of MANET, some QoS management schemes 
may be more suited for MANET than others.
	
As the wireless technologies evolve, wireless link bandwidth is increasing 
rapidly.  Emerging wireless technologies would allow for a high speed MANET 
with high speed routers and a large number of mobile users.  Such a high
speed MANET may have a hierarchical structure possibly with more bandwidth at
higher network levels.  The high speed MANET will support real time 
applications and thus make the QoS issues even more relevant to MANET group.  

Hong Jiang

Lucent Technologies

Tel: 732 949 7431