---- ||''Reference - '' Hierarchically-organized-multihop-mobile-wireless-networks-quality-service-support|| Check the attached document ---- * Address wireless networks '''QoS''' * Link layer and network layer algorithms * Distributed - Real Time applications ---- ||'''1. AIM '''|| * Low cost * Rapidly Deployable * Self organizing * No prior infrastructure ( Adhoc networking) ||'''2. SYSTEM '''|| (i) Location Manager : Movement of nodes within the clusters (ii) Adaptive Link Control : Perceived and desired link quality metrics (iii) QoS manager: mean value and Expected values of cluster's quality * Parent ->child clusters (''link state information distributed by QoS manager'') * n clusters: n-1 children get link state packets from this manager (iv) Multicast Manager: controls access to multicast groups and sessions extant within cluster and that quickly joins endpoints ||'''3. ROUTING'''|| * Routing information dissemination: Link state packets a. Connectivity information b. Service information pertaining to clusters and virtual gateways * Compute one or more feasible routes for a "session" - * based on '''''link-state information''''' received from other clusters * '''''Current location of the end point''''' with respect to hierarchical structure * '''''Service requirements''''' ---- == NETWORK ARCHITECTURE == ''Nodes ---> Routers ---> clusters ----> super clusters'' ||'''Identifying network Elements'''|| * Addresses are autonomously acquired and may change with time * Every router and end point assumed to have globally unique identity ( lets say GUID) * Router ID * Node ID * Cluster ID -- sequence of router ID's indicating the hierarchical relation among clusters '''level 0 cluster Address => router ID''' * ''' Router''' * Forward packets * Source/Destination of packets * Peer border routers * Virtual gateways: connect two adjacent clusters * Virtual link (between two virtual gateways) ''Aggregation of one or more peer border router pairs: two border routers from different clusters '' * Role of router in a cluster * Border * Interior * Border router : Router that has one neighbor that does not belong to same cluster * Interior router : Router that has no neighbors in different clusters ( opposite f border router) * '''Node ''' * source/destination of packets ||'''Roaming level ''' | Refers to cluster level within which, movement of node does not trigger update || Example : If node belongs to level-k, a location update is not triggered until node moves out of level -k * level-0 => "always update" * level-n => "never update" scheme ! ---- ||'''Cluster formation '''|| * '''Node''' ------> Registers with router ( based on some link parameters) * Moves out of the reach of router >> it is affiliated with : Register with another router * '''Router''' -------> cell head ( serves more than 1 cell/ nodes) * Many nodes affiliate with this router and router becomes cell head for these * routers come together ----> Clusters *'''Cluster '''----> contains only group of routers (at lowest level) * contains one/ more clusters as well : super cluster * Every cluster has only one parent * Every router belongs to exactly one cluster ||'''Cells '''|| * formed based on connectivity * Number of endpoints limited (prevent traffic concentration) * Node has link quality vector ( based on which it decides which router to associate with ) || ''' Keep these in mind '''|| * Bound on Size of clusters fixed --> better control and routing * Limited number of hierarchical levels ---> prevent too many sub-optimal routes ; maintenance overhead * Virtual gateways must be stable -->inter cluster connection stability (change in link state distribution overhead increases ---- ||''' Affiliation protocol '''|| * End point activated * Build link vector * selection of router * Node :Affiliation request -------> Router * Router: Response ------------>Node (only if it can accommodate ) * Handshake with each of the routers in decreasing order of preference * Link quality gets low : node restarts affiliation procedure ||''' node may not be affiliated to "best " (i.e.,closest) router but the one whose link quality that may be acceptable'''|| ---- ||''' Link state topology information '''|| * Link state data collected during routing: used for clustering as well ||<< unlike other Distributed algorithms : Quick convergence of clustering algorithm || || unlike Centralized algorithms : Avoids single point of failure >>|| ---- || '''CLUSTER DYNAMICS '''|| * Router movement * Router birth * Router death ||''cluster birth /cluster death / cluster membership change /division of cluster (cluster split)''|| ---- ||[A]. Cluster split :|| * Number of routers in clusters are above acceptable threshold: requires split (checked by leader/backup) * must maintain connectivity between routers in resulting clusters * Equalize cluster sizes * Routers in a cluster are “ranked” in order of their router Ids (independent of the link state info) * Lowest id router assumes leadership (Cluster Leader) * Splitting / Merging performed by leader who sends related info to appropriate nodes (subnet of routers) to begin merge/split * Run splitting heuristic on link state database: partition into two disjoint clusters * Broadcast info about new cluster membership * Virtual gateway membership to every router in cluster * Each router that gets this info updates its cluster related state appropriately * Virtual gateways are automatically born as a result of split ||''Location manager : after split one cluster retains a LM, while other cluster elects new LM ''|| * ''''' Uses Graph Algorithm ''''' * Splits a given graph (of cluster) : S1 and S2 ---- ||[B]. Cluster Merge || * If number is less than threshold : leader checks this (Router) * find most appropriate neighboring cluster: using the data on the cluster size available because of link state packet updates * Sum of the size of cluster 1+ cluster 2 < cluster size split threshold (but as close as possible to preferred size: to attain equal size pattern) * If such cluster (candidate for merge) is found: Perform merge and inform all routers involved about the change ||''Location manager : after merge, LM's are also merged : one cluster has one LM''|| ---- || ''' VG DYNAMICS '''|| ''' Virtual Gateway: create/destroy/grow/split/merge /shrink''' 1. Create / Destroy: result of cluster split or merge 2. Distributed protocol involving handshake between routers involved in change * Periodically each router checks if it has to initiate such a procedure (how frequent indicates the sensitivity to change in network) * State consists of * router id * Role (border/interior) * VG Id if applicable * Every router checks its state and its neighbor's state and decides whether or not to initiate '''virtual gateway protocol''' * Router with lower id initiates handshake to form VG * Handshake includes selection of VG id ---- || '''******'''|| * basis for clustering ? ('' when to allow clustering'') * Boundaries for clusters ? ('' when to stop clustering '') * Kind of network hierarchy present today could be used for such boundaries ? * Gateways could be formed by multi-homed network elements ? * Layers of control required ? ||''' Advantages '''|| * Autonomous * Addresses multi-hop mobile scenarios : Vehicular/ disaster recovery/ military /sensor based networks * Control structure on top of network today * suitable with flat identifiers used for nodes/ network elements ----