---

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

1. Connectivity information
2. 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

• 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)

2. Node :
   • source/destination of packets

---

Cluster formation :

---

• Node ------> Registers with router ( based on some link parameters)

[Prob-01] only one router at any given time [we would need support for more than one router ??]

Q

possible if two routers inside cluster of clusters!!?

• 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
• Routing and location management

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

---

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

---

• Node Affiliation with router : << Affiliation protocol>>

• End point activated * Node :Affiliation request -------> Router
• Build link vector * Router: Response ------------>Node (only if it can accommodate )
• selection of router

• 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 " (closest) router but the 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 DYANMICS

• 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

• 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

---

[A]. Virtual Gateway: create/destroy/grow/split/merge /shrink

1. Create / Destroy: like above
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

• switch id
• Role (border/interior)

• Virtual gateway ID (if applicable) information carried of router sees a neighbor router (adjacent) and can form virtual gateway -
  • Router with lower id initiates handshake to form VG
  • Handshake includes selection of VG id